loggerJK.log

[Paper] DETR : End-to-End Object Detection with Transformers

Wed, 07 Sep 2022 02:43:38 GMT

Abstract

Object Detection 문제를 Direct Set Prediction Problem으로 접근 → detection pipeline을 이전보다 간소화
- 세부적으로는 NMS (Non-Maximum Suppression)이나 Anchor Generation과 같은 hand designed 요소들을 제거했음
모델의 주요 요소 : 이분 매칭 (bipartite matching), set-based global loss, Transformer Encoder-Decoder 아키텍처
모델 자체가 개념적으로 매우 단순하기 때문에 구현과 (Panoptic Segmentation과 같은) 다른 분야로의 응용이 굉장히 쉬움.
COCO object detection 데이터셋을 기준으로, Faster R-CNN과 수준의 성능을 보임.

1. Introduction

DETR의 Main Feature
- 이분 매칭과 Parrael decoding Transformer의 결합
- 이분 매칭 알고리즘이 예측 결과를 ground truth object에 uniquely assign 해주기 때문에, 예측 결과 중 나타나는 object들의 순서에 영향을 받지 않는다.
  - 따라서 DETR은 병렬적으로 예측을 수행하는 것이 가능하다.
  - 병렬적으로 수행한다는 의미는, 기존의 RNN이나 auto-regressive Transformer(= Attention Is All You Need에서 제안한 초기 버전의 Transformer)처럼 결과를 하나씩 출력하지 않고, 모든 결과를 한번에 출력한다는 의미
Transformer 기반의 모델이기 때문에 역시 매우 긴 훈련 시간을 필요로 하며 (extra-long training schedule)
디코딩 레이어에서의 보조 손실 함수 (auxiliary decoding loss)를 통해 이득을 얻을 수 있다

Set Predciton

이전까지는 직접적으로 집합을 예측하는 표준적인 딥러닝 모델은 존재하지 않았음
기존에는 인접-중복 (near-duplicate) 문제를 NMS와 같은 후처리를 통해서 제거 BUT direct set prediction은 후처리 필요 X
Direct Set Prediction을 위해서는 모든 predicted element를 다루는 global inference 계획이 필요하다
- 1) Fully Connected Layer → 충분하지만 연산량이 많이 듦
- 2) Auto-regressive Sequence Model (e.g. RNN)
무엇을 쓰던지 간에 loss는 예측 결과의 순서에 영향을 받지 않아야 한다. 보통 이를 위해 쓰는 방법이 헝가리안 알고리즘에 기반을 둔 이분 매칭을 통해 ground-truth와 예측 결과를 서로 매칭하는 방법이다.
논문에서는 기존의 Auto-Regressive 기반 모델에서 한발 더 나아가, Transformer 구조를 이용한다

Transformers and Parallel Decoding

Attention의 장점
- Global Computation, Perfect Memory
  - → Long Sequence 기준 RNN보다 적합
  - NLP, Speech-processing, Vision 등 여러 분야에서 RNN을 빠르게 대체하는 중
초기 Transformer는 Auto-regressive 모델
- output length가 길어질수록 덩달아 추론 시간도 비례해서 늘어난다는 단점
- 이를 해결하기 위해 오디오, 기계 번역, 단어 표현 학습, 음성 인식 등 분야에서 parallel decoding Transformer 모델이 등장
우리도 그래서 parallel Transformer 쓸꺼다~

Object Detection

Two Stage Detector든, One Stage Detector 모델이든 Initial Guess가 존재
- Two Stage Detector : Proposal을 통해 box를 예측
- One Stage Detector : Anchor 또는 가능한 물체 중심에 대한 Grid를 이용헤 예측을 수행
최근의 연구 결과에 따르면 모델의 최종 성능은 이러한 Initial Guess에 의해 상당한 영향을 받는다고 함 (Zhang,S.,Chi,C.,Yao,Y.,Lei,Z.,Li,S.Z.:Bridging the gap between anchor-based and anchor-free detection via adaptive training sample selection, 2019)
그래서 논문에서는 이러한 것들을 (hand-crafted process) 싹 다 제거하고 이미지 기반으로만 예측을 수행
이분 매칭 + Parallel Decoding Transformer 조합 + non hand-crafted feature 조합은 이 논문이 최초

3. The DETR model

Object Detection set prediction loss

DETR은 디코더를 한번만 통과하여, N이라는 고정된 크기의 prediction 결과를 도출한다.
- 이때, N은 이미지에 있는 일반적인 물체의 개수보다 훨씬 큰 값이다.
1단계: 예측 결과에 대해 ground truth와 관련 있는 만큼 점수 매기기
변수 설명
- $y = {y_1, y_2, y_3, ..., \varnothing }$ : ground truth set of objects
  - 크기가 $N$으로 고정되어 있어야 하므로, $\varnothing$으로 padding 되어 있다.
- $\hat{y} = {\hat{y_1}, \hat{y_2}, \hat{y_3}, ..., \hat{y_N} }$ : set of $N$ predictions
- $\varnothing$ : no object
두 집합 $y, \hat{y}$ 사이에 이분 매칭을 해야 한다. 따라서 N개 원소들의 순열 $\sigma \in \mathfrak{S}_N$ 중, pair-wise matching cost가 최소가 되도록 하는 $\hat{\sigma}$를 찾는다.

$$\hat{\sigma} = \underset{\sigma \in \mathfrak{S}N}{\text{argmin}} \sum^N \mathcal{L}_\text{match} (y_i, \hat{y}{\sigma(i)})$$

$\mathcal{L}\text{match} (y_i, \hat{y}{\sigma(i)})$ : Pair-wise matching cost
- $y_i$ : ground truth
- $\hat{y}_{\sigma(i)}$ : $\sigma$에서 i번째 예측값 (prediction with index $\sigma(i)$)
Matching cost $\mathcal{L}\text{match} (y_i, \hat{y}{\sigma(i)})$는 1) class prediction 2) bounding box 유사도를 둘 다 고려한다.
변수 설명
- $y_i = (c_i, b_i)$
  - $c_i$ : true target class label
  - $b_i \in [0,1]^4$ : bounding box 좌표 (중심좌표1, 중심좌표2, height, width)
- 예측 값 $\hat{y}_{\sigma (i)}$에 대해
  - $\hat{p}_{\sigma(i)}c(i)$ : target class $c(i)$에 대한 확률
  - $\hat{b}_{\sigma(i)}$ : bounding box 예측값
이러한 표기를 이용해, 논문에서는 $\mathcal{L}\text{match} (y_i, \hat{y}{\sigma(i)})$를 다음과 같이 정의한다
- $\mathcal{L}\text{match} (y_i, \hat{y}{\sigma(i)}) = -\mathbb{1}{{c_i \not= \varnothing}} \hat{p}{\sigma (i)}(c_i) + 1_{{c_i \not= \varnothing}} \mathcal{L}{\text{box}} (b_i, \hat{b}{\sigma(i)})$
  - 해당, true target class label에 대한 확률이 높을수록, 해당 object와의 bounding box loss가 낮을수록 matching cost가 낮아진다.
- 클래스 예측 항에 로그를 사용하지 않은 이유는, bounding box loss와 같은 단위를 사용하기 위함이고, 실제 실험에서도 이 방법이 더 좋은 결과를 얻었다.
최적 순열 $\sigma$를 찾는 계산은 Hungarian Algorithm을 이용해 수행된다.
2단계 : Loss Function 계산하기
- 이전 단계에서 매칭된 모든 짝(pair)에 대해 Hungarian Loss를 계산
- 정의 : Linear combination of negative log-likelihood for class prediction and a box loss (defined later)
  - $\mathcal{L}{\text{Hungarian}}(y,\hat{y}) = \sum^{N}{i = 1} [ -\log\hat{p}{\hat{\sigma}(i)}(c_i) + 1{{c_i \not= \varnothing }} \mathcal{L}{\text{box}}(b_i, \hat{b}{\hat{\sigma}(i)}) ]$
  - $\hat{\sigma}$ : 이미 계산된 optimal assignment
  - 실제로는 $c_i \not= \varnothing$인 경우가 훨씬 많기 때문에 클래스 불균형 문제가 발생한다
    - 따라서 $c_i \not= \varnothing$ 인 경우의 로그-확률 항은 10으로 나눠주어 이를 해결한다

Bounding box loss

$\mathcal{L}{\text{box}} (b_i, \hat{b}{\sigma(i)}) = \lambda_{\text{iou}}\mathcal{L}{\text{iou}} (b_i, \hat{b}{\sigma(i)}) + \lambda_{\text{L1}} ||b_i - \hat{b}_{\sigma(i)}||_1$
- $\lambda_{\text{iou}}, \lambda_{\text{L1}} \in \mathbb{R}$ : 하이퍼파라미터
- small box와 large box간의 상대적인 오차가 비슷한 경우에도, L1 loss는 서로 다른 scale을 가지게 된다는 단점이 있다.
- 이 문제를 완화하기 위해 GIoU 항을 함께 사용한다
- 두 loss는 배치 안에서 object의 개수로 normalize된다.

DETR architecture

3가지 주요 요소
- 1) CNN backbone : Feature Representation을 학습
- 2) Encoder-Decoder Transformer
- 3) (Simple) Feed Forward Network (FFN)

Backbone

CNN을 통해 저해상도의 activation map을 생성
Initial image : $x_0 \in \mathcal{R}^{3 \times H_0 \times W_0}$
Activation Map : $f \in \mathcal{R}^{C \times H \times W}$
논문에서 사용한 값은 $C = 2048, H,W = \frac{H_0}{32}, \frac{W_0}{32}$

Transformer encoder

$1\times1$ Convolution
1. Input : High-level activation map $f$
2. 차원 축소 : $C$ → $d$
3. Output : $z_0 \in \mathcal{R}^{d \times H \times W}$
Encoder는 Input이 Sequence임을 기대하므로, $z_0$의 Spatial dimension을 1차원으로 압축 → $d \times HW$ feature map
각각의 Encoder 레이어는 표준적인 구조를 가지고 있고, MSA(Multi-head Self Attention) 모듈과 FFN(Feed Forward Network)로 이루어짐
Transformer 구조는 순서에 영향을 받지 않으므로, 고정된 Positioinal Encoding을 사용, 각 attention 레이어의 입력마다 더해준다.

Transformer Decoder

기본적으로 Decoder는 Transformer의 표준적인 구조를 따른다
- 크기가 $d$인 N개의 임베딩을 MSA와 Encoder-Decoder 어텐션 메커니즘을 이용해 변환
기존 모델과의 차이점
- 각 Decoder 레이어에서 N개의 예측 결과를 병렬적으로 출력
Decoder가 순서에 의존적이지 않으므로, N개의 Input Embedding 또한 서로 다른 결과를 출력하기 위해서는 서로 달라야 한다
- 이러한 Input Embedding은 학습된 Positional Encoding → 논문에서는 Object Query로 지칭한다.
- 자세한 설명은 Supplementary Material
N개의 Object Query들은 디코더를 통해 Output Embedding으로 변환
- 이후에는 각각 FFN을 거쳐 독립적으로 class label + box coordinate로 변환 → N개의 최종 예측 도출
이러한 과정속에서, 모델은 물체간의 pair-wise 관계를 이용해 모든 물체에 대해서 전체적으로 추론하고, 추론 과정 속에서 전체 이미지를 맥락으로써 활용한다.

Prediction Feed-froward networks (FFNs)

ReLU, hidden dimesion $d$, linear projection의 3개 레이어로 이루어짐
FFN은 bounding box의 (정규화된) 중심좌표, height, width를 예측하고 linear layer가 softmax 함수를 이용해 class label을 예측
물체가 없을 때는 $\varnothing$을 쓴다.
- 일반적인 Object Detection 접근법에서의 'background' 클래스와 같은 역할

Auxiliary decoding losses

논문의 저자들은 훈련 중 Decoding Layer에 Auxiliary loss를 사용하는 것이 도움이 됨을 발견함
- 특히 모델이 각 class 마다 정확한 개수의 물체를 인식하도록 도와줌
각각의 Decoding Layer마다 prediction FFN과 Hungarian loss를 추가
- 모든 prediction FFN들은 파라미터를 공유
- 서로 다른 Decoder Layer prediction FFN으로 들어가는 input을 정규화히기 위해 추가적인 shared layer-norm을 사용함

4. Experiments

COCO의 quantitative evaluation에서 Faster R-CNN과 대등한 성능
전반적으로 DETR이 확장성 있는 모델임을 보임

4.1 Comparison with Faster R-CNN

Faster R-CNN이 나온지 꽤 오래되어서, 논문에서는 Faster R-CNN을 DETR과 대등한 조건으로 다시 훈련해서 비교
- GIoU loss, Random Crop Augmentation, Long training
사진의 하이라이트처럼, 동일한 파라미터 개수의 DETR이 Faster R-CNN과 대등한 성능을 보이는 것을 확인할 수 있음
그러나 여전히 작은 물체를 탐지하는 데에서는 어려움을 겪음 (APs)

4.2 Ablations

Number of encoder layers

Encoder layer가 전무한 경우
- Overall AP는 3.9 하락
- 특히 $AP_L$ (large object)는 6.0 하락
논문 저자들의 추론 : Global scene reasoning을 이용함으로써, Encoder가 물체를 구별하는데 중요한 역할을 수행

특정 픽셀에 대해, 가장 마지막 Encoder Layer의 Attention map을 시각화한 모습
Encoder가 이미 물체를 구별하고 있는 것을 볼 수 있음
- Decoder의 object extraction / localization 작업이 더욱 쉽도록 도와줌

Number of decoder layers

각 Decoding Layer에서 예측하는 object를 평가함으로써, 각 Decoder Layer의 중요성을 평가해보고자 함.
- 각 Decoder Layer마다 auxiliary loss, prediction FFN이 붙어 있다는 점을 이용
Layer를 거칠 때마다 $AP, AP_{50}$ 점수가 상승
- 첫 레이어와 마지막 레이어의 점수 차이는 각각 $+8.2/9.5AP$로 상당한 차이를 보임
DETR은 설계 구조상 NMS를 필요로 하지 않음. 논문 저자들은 이를 증명하기 위해 각 decoder layer의 output마다 NMS를 적용해봄
- 첫 Decoder Layer에서는 NMS를 통해 유의미한 성능 향상이 있음
  - 이는 Transformer의 Single Decoding Layer는 output element들 간에 상관 관계를 계산하는 것이 불가능하기 때문
  - 따라서, 같은 물체에 대해 여러번 예측하는 경향성을 보이기도 함
- 하지만 2번째와 이후의 Layer에는 그렇지 않음. Activation 이후의 Self-Attention 메커니즘은 이러한 중복 예측 문제를 해결하도록 도움
- Depth가 깊어질수록 NMS를 통한 성능 향상률이 작아지는 것을 관찰할 수 있었음
- 마지막 Layer에서는 오히려 NMS가 true postive prediction을 제거하기도 하는 부작용도 관찰됨

Fig.6에서 Decoder Attention을 시각화한 모습을 볼 수 있음
주로 다리, 머리 등 상당히 국소적인 부위에 집중되는 양상
논문 저자들의 설명
- Encoder가 Global Attention을 통해 물체를 분리했기 때문에, Decoder는 class 추출 / bounding box prediction을 위해 주로 경계 부분에 집중하는 것으로 보임

Importance of FFN

Transformer 구조 안의 FFN은 $1\times1$ Convolutional Layer로 생각할 수 있음 → Encoder가 Attention augmented convolutional network와 비슷해지도록 함
FFN을 제거하면 $2.3AP$ 하락 → FFN이 중요하다는 결과

Importance of positional encodings

DETR에서 사용하는 두가지 Positional Encoding
- Spatial Positional Encoding
- Output Positional Encoding (Object Queries) : 제거 불가능, 학습된 인코딩

중간 요약

Transformer components (Global Self Attention in encoder, FFN, Multiple decoder layers, positional encodings) 모두 성능에 결정적인 요소임을 알 수 있음.

Loss ablations

GIoU가 상당히 결정적인 역할을 하는 것을 볼 수 있음

4.3 Analysis

Decoder output slot analysis

DETR은 각각의 (object) query slot은 서로 다르게 특화하는 방법을 배운다
- 즉, 각각의 slot은 서로 다른 영역, box size에 집중하는 모습을 볼 수 있다.

Generalization to unseen numbers of instances

COCO가 제공하는 데이터셋에서는, 한 이미지에 같은 클래스인 오브젝트가 다수 등장하는 경우는 잘 나타나지 않는다
- 예를 들어, COCO의 Training Set에는 한번에 13개 이상의 기린이 등장하는 이미지는 없다
논문에서는 DETR의 성능을 검증하기 위해 합성 이미지로 DETR을 테스트 했고, 24개의 기린까지 인식하는 모습을 보였다.
- 이는 각각의 object query에 강한 class-specialization은 존재하지 않음을 의미한다

4.4 DETR for panoptic segmentation

다른 Faster R-CNN, Mask R-CNN 모델과 마찬가지로, DETR은 decoder output에 mask head를 추가하는 방식을 통해 자연스럽게 확장 가능
Transformer Decoder 각각의 Output을 Input으로 받아, Encoder Output과 함께 Multi-head attention score를 계산, object마다 저해상도의 M attention heatmap을 계산
최종 예측을 위해서는, 각 픽셀의 mask score에 argmax를 적용

Main Result

COCO-val 2017에 대한 published result를 압도하는 결과
DETR은 Stuff 클래스에 강세를 보임
- Encoder의 Global Reasoning 덕분이라고 봄

5. Conclusion

Transformer, direct set prediction을 위한 이분매칭 기반의 Object Detection System을 제안
COCO Dataset 기준으로, 최적화된 Faster R-CNN에 필적하는 성과를 거둠
구현하기 쉽고, 확장성 있는 유연한 구조, 상당한 성능
Attention 메커니즘 덕에 Faster R-CNN보다 큰 물체를 더 잘 탐지함.
단, 작은 물체 탐지에서는 여전히 어려움을 겪는 중

[백준] 1865 웜홀 : 문제의 논란 정리

Mon, 11 Jul 2022 11:30:53 GMT

주의 : 해당 문제 질문 게시판의 풀이 및 논란 완전 정리합니다. 라는 글에 대한 보충 설명을 스스로 이해할 수 있도록 정리한 글입니다.

이 문제에서 핵심 의문은 다음 2가지였다.

시작 정점이 어디인가?

연결 그래프 여부가 왜 표시되어 있지 않은가?

결론적으로 말하면 다음과 같다.

시작 정점의 여부는 필요하지 않다. 또한, 단절된 그래프가 주어지는 경우도 생각해야 한다. 그리고 이 두 부분은 의도된 것이다.

코드 1
INF = 2000000000
모든 dist[v] = INF
dist[1] = 0
N-1번 반복:
  모든 v에 대해:
    모든 간선에 대해 최단거리 갱신
모든 v에 대해:
  모든 간선에 대해 최단거리 갱신
  갱신이 한 번이라도 일어났으면 true

===

코드 2
INF = 2000000000
모든 dist[v] = INF
dist[1] = 0
N-1번 반복:
  dist[v] != INF인 모든 v에 대해:
    모든 간선에 대해 최단거리 갱신
dist[v] != INF인 모든 v에 대해:
  모든 간선에 대해 최단거리 갱신
  갱신이 한 번이라도 일어났으면 true

코드1은 이번 문제가 요구하는 코드, 코드2는 원래 벨만포드 알고리즘이다.

Case 1에 해당하는 예시 그래프가 위와 같이 주어졌다고 생각해보자. 이때, 위 그래프는 전체 그래프 중 시작 정점에서 도달할 수 없는 단절된 그래프를 나타낸 것이다.

코드 1의 경우를 생각해보자.

Case 1. 정점이 2개이므로 밸만 포드 알고리즘은 모든 간선에 대해 1회의 Relaxation을 수행한다. 그렇다면 오른쪽 정점은 INF-4의 값을 가지게 된다. 이후에 더 이상 Relaxation 가능한 간선은 존재하지 않는다. 따라서 음수 사이클이 없다고 판단한다. 이는 옳은 판단이다.

Case 2. 이제 오른쪽 → 왼쪽 -5 간선이 있다고 생각해보자. 정점이 2개이므로 밸만 포드 알고리즘은 모든 간선에 대해 1회의 Relaxation을 수행한다. 그렇다면 오른쪽 정점은 INF-4의 값을 가지게 된다. 왼쪽 정점 역시 INF-5의 값을 가지게 된다. 여전히 Relaxation 가능한 간선이 존재하므로 음수 사이클이 존재한다고 판단한다. 그리고 이는 옳은 판단이다.

단절된 그래프임에도, 두 case에 대해서 코드1은 음수 사이클의 존재 여부를 정확히 판단해 내고 있는 것을 볼 수 있다.

원래 벨만포드 알고리즘은 INF가 숫자가 아닌 (무한대라는) 상태를 나타낸다. 다시 말해, 원래의 벨만 포드 알고리즘은 INF-4로 오른쪽 정점의 값을 갱신하지 않는다. 코드1이 이처럼 동작하는 이유는, 구현 상 INF가 어떠한 숫자로 지정되어 있기 때문이다. 그렇기 때문에, 코드1을 파이썬의 float('inf')를 이용해 구현한다면 틀린 코드가 된다. 파이썬에서 float('inf') - 4는 여전히 float('inf')로 취급하기 때문이다. 따라서 아예 처음부터 Relxation이 불가능하다고 판단해 아무것도 갱신하지 않는 코드로 작동한다.

사실 코드1에서 시작 정점 초기화 조건(dist[1] = 0)은 아예 존재하지 않아도 된다. 어차피 도달할 수 없는 그래프이기 때문이다. 또는 다음과 같이도 생각할 수 있다. '모든 정점이 INF인 그래프에서 임의의 정점을 시작 정점으로 하여 벨만 포드 알고리즘을 수행한다.' 그래도 알고리즘은 음수 사이클을 성공적으로 찾아낸다는 것을 우리는 이미 위에서 보았다.

단순히 음수 사이클을 찾고 싶다면, 시작 정점은 고려하지 않아도 된다!

코드 2의 경우를 생각해보자.

애초에 시작 정점에서 도달하는 것이 불가능하다.
간선의 시작 정점 (u→v 애서 u)이 INF라면 Relaxation을 수행하지 않는다.

이 두가지 특성때문에, 단절된 그래프에서는 무조건 음수 사이클이 없다고 동작함을 알 수 있을 것이다.

[알고리즘] 트리의 지름 증명

Sun, 10 Jul 2022 09:44:31 GMT

링크의 글을 보충 설명한 글입니다.

트리에서 지름이란, 가장 먼 두 정점 사이의 거리 혹은 가장 먼 두 정점을 연결하는 경로를 의미한다. 선형 시간안에 트리에서 지름을 구하는 방법은 다음과 같다:

트리에서 임의의 정점 x를 잡는다.
정점 x에서 가장 먼 정점 y를 찾는다.
정점 y에서 가장 먼 정점 z를 찾는다.

트리의 지름은 정점 y와 정점 z를 연결하는 경로다.

증명) 트리에서 정점 u와 정점 v를 연결하는 경로가 트리의 지름이라고 가정하자. 임의의 정점 x를 정하고, 정점 x에서 가장 먼 정점 y를 찾았을 때, 아래와 같이 경우를 나눌 수 있다.

x가 u 혹은 v인 경우
y가 u 혹은 v인 경우
x, y, u, v가 서로 다른 경우

자명하게 1., 2.에 대해서 위 알고리즘이 트리의 지름을 올바르게 구한다는 것을 알 수 있다. 이제 3. 경우에 대해서 알고리즘이 트리의 지름을 올바르게 구한다는 것을 증명하면 된다. 3. 경우일 때 아래와 같이 두 가지 경우가 가능하다.

(a) 정점 x와 정점 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 한 점 이상 공유하는 경우

(b) 정점 x와 정점 y를 연결하는 경로가 정점 u와 정점 v를 연결하는 경로와 완전히 독립인 경우

(a)의 경우를 살펴보자. 그림으로 나타내면 다음과 같다.

x애서 가장 먼 정점이 y이므로 $(t,y)$는 $(t,u), (t,v)$보다 크다. 수식으로는 $(t,y) > max( (t,u), (t,v) )$라고 쓸 수 있다. $(u,v) = (u, t) + (u, v)$는 지름이다. 그런데 새로운 경로 $(t,y) + max((t,u), (t,v))$를 생각해보자. 지름보다 해당 경로가 더 길다는 결론이 나오고, 이는 $(u,v)$가 트리의 지름이라는 가정에 모순이다.

b.의 경우 아래 그림과 같은 상황이 된다는 것인데 u에서 제일 먼 점이 v가 아니라 y가 되어 u와 v를 연결하는 경로가 트리의 지름이 된다는 가정에 모순된다. 때문에 b.의 경우는 불가능하다는 것을 알 수 있다.

때문에 소개한 알고리즘은 트리의 지름을 올바르게 구한다는 것을 증명했다.

출처: https://blog.myungwoo.kr/112 [PS 이야기:티스토리]

[백준] 2206 : 벽 부수고 이동하기

Sat, 09 Jul 2022 12:42:04 GMT

용어정리

벽을 한번 뚫고 온 상태를 depth 1, 벽을 뚫고 오지 않은 상태를 depth 0라고 정의합니다.
(0,0) → (N-1, M-1) 경로라고 생각합니다.
생각하지 못한 Case

같은 정점을 서로 다른 depth로 방문할 수 있다. 그러므로 방문 체크가 '독립적으로' 진행되어야 한다

다음과 같은 3 X 3케이스를 생각해보자

0 ─── 0 ─── 1
│     │     │
1 ─── 0 ─── 1
│     │     │
1 ─── 1 ─── 0

(0,0)에서 (2,2)를 방문하기 위해서는, 반드시 다음의 2가지 케이스 밖에 없다.

이때, (1,1)에 집중하자. 원래 (1,1)에 도달하는 방법은 2가지 경로가 있다.

(1,0)을 거치는 경우
(0,1)을 거치는 경우

0 ─── 0     1
│     │     
1 ─── 0     1

1     1     0

depth를 고려하지 않고 int visit = [1001][1001]과 같이 선언한 경우를 가정해보자. (방문체크가 독립적으로 이루어지지 않는 상태) 이때 (1)번 경로를 먼저 탐색한다고 가정한다. 그렇다면 (1,1)에 최단거리 2(depth 1 경로)를 갱신할 것이다. 문제는 여기서 발생한다. 이 경로로는 (1,2)나 (2,1)에 있는 벽을 뚫고 (2,2)에 도달하는 것이 불가능하다.

그러나, (2)번 경로를 먼저 탐색한다고 가정하자. 그렇다면 (1,1)에 최단거리 2 (depth 0) 경로가 갱신될 것이다. 이 경로로는 (2,2)에 도달하는 것이 가능하다.

위의 케이스에서 보듯, 방문 채크는 독립적으로 진행되어야 한다.

마찬가지의 원리로, 최단 경로 배열 또한 독립적으로 구성되어야 한다. 해당 정점에서 depth 1 최단거리 < depth 0 최단거리인데, 결론적으로는 depth 0 경로를 통해서만 도달 가능한 경우가 있을 수 있기 때문이다. 이때 두 경로의 최단거리가 구분되어야 제대로 된 결괏값이 나온다. (구분되지 않으면 경로는 depth 0인데, depth 1 최단거리를 이용한 값이 나올 수 있다.)

예를 들면 다음과 같다.

0 ─── 0 ─── 0 ─── 1 ─── 1
│     │     │     │     │
1 ─── 1 ─── 0 ─── 1 ─── 1
│     │     │     │     │
1 ─── 0 ─── 0 ─── 1 ─── 1
│     │     │     │     │
1 ─── 0 ─── 1 ─── 1 ─── 1
│     │     │     │     │
1 ─── 0 ─── 0 ─── 1 ─── 0

(3,2)에 위치한 1이 (4,2)의 0 정점이 최단거리를 갱신하는 것이 가능하다. 실제 최단 거리는 이 경로를 이용하지 않지만, 최단 경로 배열이 구분되지 않으면 (3,2)가 (4,2)에 갱신한 최단 거리가 (4,4) 까지의 최단 거리 계산에 이용될 위험이 있다.

따라서 코드는 다음과 같아야 한다.

int dist[1001][1001][2];
int visit_arr[1001][1001][2];

코딩 테스트 대비 정리

Sat, 11 Jun 2022 16:29:05 GMT

C++ STL

vector : 배열(array)와 비슷하게 사용가능
map
- 파이썬의 Dictionary와 비슷함
```
map m;
m['jiwon'] = 1;
```
unordered_map
- map에서 정렬이 되어 있지 않은 버전 -> 더 빠르다
set
- unique한 원소들을 정렬된 상태로 보관
queue
- priority queue

알고리즘 종류

DFS, BFS
- DFS : stack or 반복문
- BFS : queue
Binary Search
- C++ lower_bound, upper_bound
Dynamic Programming
Greedy
Priority queue
Hash Map
Union Find
Trie
Kruskal (Minimum Spanning Tree)
Shortest Path(최단 경로)
- Dijkstra
- Bellman-Ford
- Floyd-Warshall
조합(Combination)
- next_permutation() or prev_permutation()

TIP

1억(10^8) == 1초로 알고리즘의 속도를 판별해 볼 수 있다.
틀리는 경우에는 자료형의 크기 / 특이값 input 등에 대해 생각해보자
오름차순 정렬 코드

// `priority_queue`
struct compare
{
    bool operator()(pii a, pii b)
    {
        return a.second > b.second;
    }
};

/* 클래스를 정의하는 경우 */
// 오름차순
bool operator<(edge &e)
{
    return this->dist < e.dist;
}

// sort()의 custom compare 함수
bool compare(edge a, edge b)
{
    return a.dist < b.dist;
}

C++에서의 클래스 선언 및 사용

class edge
{
public:
    // 멤버 변수 선언
    int node[2];
    int dist;
    // 생성자 선언
    edge(int a, int b, int dist)
    {
        this->node[0] = a;
        this->node[1] = b;
        this->dist = dist;
    }
};

vector.push_back(edge(a, b, dist));

주의

에라토스테네스의 체는 여러 개의 숫자에 대해서 소수를 판별해야 할 때 유용하다. 하지만 지나치게 큰 숫자의 경우 (ex - 10^12)에는 배열이 너무 커지기 때문에 메모리 초과가 발생할 수 있다는 점을 염두에 두어야 한다.
- 관련 문제 : k진수에서 소수 개수 구하기 (2022 KAKAO BLIND RECRUITMENT)

[Paper] YOLO : You Look Only Once

Sat, 12 Mar 2022 07:28:54 GMT

Abstract

기존 : classifier를 detection을 수행하도록 바꾸는 방식 ➡️ YOLO는 object detection을 regression 문제로 접근함.
단일 네트워크가 bounding box와 class probability 예측을 한번에 수행
모든 pipeline이 단일 네트워크이고, 따라서 end-to-end 학습이 가능함
빠르다
- base모델은 초당 45프레임, fast 모델은 초당 150프레임 (NVIDIA TITAN X 기준)
- fast모델마저 다른 real-time detector보다 두배 높은 mAP 성능
Localization error는 타 모델에 비해 더 많지만, background에 대한 false positive (배경을 물체로 검출하는 에러)는 더 적다.
물체의 일반적인 표현을 학습한다
- 예술작품과 같은 다른 도메인에 일반화할 때도 다른 모델들 (DPM, R-CNN, ...)을 압도하는 성능을 보인다.

1. Introduction

YOLO는 기존의 모델에 비해 매우매우(!) 간단하다. Single Convolution Network가 여러개의 bounding box를 예측하고 이에 대한 class probability까지 예측한다. 기존에 각 부분을 따로 따로 학습해야 했던 DPM, R-CNN에 비하면 엄청난 장점이다.

장점 1.(다시 한번) YOLO는 빠르다. 25ms 이하의 레이턴시로 동영상 실시간 스트리밍이 가능할 정도이다. 게다가 다른 real-time 시스템에 비해서 mAP는 두배가 더 높다. 이는 데모 사이트에서 확인할 수 있다.

장점 2. YOLO는 training과 prediction을 진행할 때 이미지 전체를 본다. 그렇기 때문에 (sliding window 방식과 다르게) 이미지의 contextual 정보까지 얻을 수 있다. Fast R-CNN은 배경을 물체로 인식하는 실수를 잘 범하는데, larger context를 못봐서 그렇다. YOLO는 Fast R-CNN에 비해서 배경 실수가 절반밖에 안된다.

장점 3. 일반화가 잘된다. 일반적인 (natural)이미지로 학습하고 artwork로 테스트 했을때, YOLO는 다른 DPM, R-CNN 등의 모델을 큰 차이로 이겼다. 결과적으로 다른 도메인이나 예상치 못한 입력에도 잘 대응할 수 있다는 말이 된다.

단점. YOLO는 여전히 (당시의) SOTA 모델들보다 정확도가 떨어진다. 또한 어떤 물체를 정확히 localize하는 것에는 어려움을 겪고, 작은 물체일수록 심하다.

2. Unified Detection

먼저 이미지를 $S \times S$ grid로 나눈다. 먄약 object의 중심 좌표가 어떠한 grid cell에 위치한다면, 그 grid cell은 object를 검출해야 한다.

각각의 grid cell은 (1) B개의 bounding box (2) 각각의 bounding box에 대한 confidence score를 에측한다. Confidence score는 다음을 반영한다. (1) 모델이 box 안에 object가 있음을 확신하는 정도 (2) 예측한 bounding box가 ground truth bounding box와 얼마나 일치하는가. 따라서 confidence는 다음과 같이 정의된다.

$$\text{confidence = Pr(Object)} \ * \text{IOU}_{\text{pred}}^{\text{truth}}$$

만약 object가 cell 안에 없다면, confidence score는 0이어야 한다. 반대로 object가 cell 안에 있다면, confidence score는 예측한 box와 ground truth box 간의 IoU 값이 될 것이다.

결과적으로 각각의 bounding box는 5개의 예측값 $(x,y,w,h,\text{confidence})$를 가진다. $(x,y)$는 grid cell에 대한 중심 좌표의 상대적 위치를 나타낸다. $(w,h)$는 각각 이미지 전체에 대해 상대적인 width와 height 값을 나타낸다. 마지막으로 conficence는 예측 box와 ground-truth box 간의 IOU 값을 예측한다.

Bounding box의 개수 $B$와는 상관 없이, 각각의 grid cell은 $C$개의 조건부 클래스 확률 $\text{Pr(class}_i | \text{Object})$을 계산한다. Test time에서는 조건부 클래스 확률과 box confidence 값을 곱해서 box마다 클래스별 confidence score를 얻는다. 이 confidence score는 (1) 해당 box 안에 해당 class의 물체가 있을 확률 (2) 에측한 bounding box가 정확할 확률을 의미한다.

Bounding Box는 단순히 물체가 있을 확률만을 고려한 confidence score를 가진다. 어느 class일지는 각각의 grid cell이 고려한다.

결과적으로, prediction은 $S \times S \times (B * 5 + C)$ 텐서로 인코딩된다.

PASLCAL VOC 데이터셋에서 YOLO는 $S = 7, B = 2, C = 20$으로, 결과적으로는 $7 \times 7 \times 30$의 텐서를 가진다

2.1 Network Design

GoogLeNet에서 영감을 받은 네트워크 디자인. 24개의 convolutional layer와 2개의 fully connected layer로 구성된다. GoogLeNet의 Inception 모듈 대신 $1 \times 1$ reduction layer와 $3 \times 3$ convolutional layer의 조합을 사용한다. 전체 네트워크 디자인은 다음과 같다.

Fast YOLO는 24개 대신 9개의 convolutional layer만 사용하고, 레이어의 filter 가 더 적다.

2.2 Training

1k ImageNet 데이터로 처음 20개 convolution network의 pretraining을 진행한다. (저자들은 일주일동안 학습을 진행해서 GoogLeNet에 필적하는 single crop top-5 accuracy를 달성했다.) 이후 4개의 convolutional layer와 2개의 fully connected layer를 이어붙인다. Detection에서는 이미지 품질이 중요하므로 input resolution을 $224 \times 224$에서 $448 \times 448$로 끌어올렸다.

마지막 layer는 class probability와 bounding box 좌표를 둘 다 예측한다. 이 때, width와 height는 normalize하여 [0,1]이 되도록 한다. 또한 $(x,y)$는 특정 grid cell location의 offset이 되도록 하기 위해서 역시 [0,1]의 값이 되도록 한다.

마지막 layer에 대한 linear activation function으로는 leaky rectified linear activation을 사용한다.

$$\phi(x) = \begin{cases} x, & \text{if}\quad x > 0 \ 0.1x, & \text{otherwise} \end{cases}$$

YOLO는 최적화하기가 쉽기 때문에 loss 함수로 sum-squared error를 사용한다. 하지만 이 loss 함수가 'AP 최대화'라는 우리의 목표와 완전히 일치하는 것은 아니다. 왜냐면 localization error와 classification error를 동일하게 취급하기 때문이다. 대다수의 object를 포함하지 않는 cell에서 confidence score는 0일 것이고, object를 포함하는 다른 cell들의 gradient 영향력이 지나치게 크도록 하는 문제를 낳는다. 이는 모델의 불안정성 및 발산으로 이어진다.

이를 해결하기 위해, 우리는 bounding box 좌표에 대한 loss는 증가시키는 한편, object를 포함하지 않는 box의 confidence 예측에 대한 loss는 감소시킨다. 이를 위해서 $\lambda_{\text{coord}} = 5, \lambda_{\text{noobj}} = 0.5$라는 파라미터를 이용한다.

같은 small deviation이더라도, large box보다는 small box에서의 small deviation이 더 영향이 크다. 하지만 sum-squared error는 이러한 특성을 제대로 반영하지 못한다. 논문에서는 이 문제를 커버하기 위해서 width와 height 값에 루트를 취하는 방식으로 접근을 시도했다.

YOLO는 그리드 셀마다 여러개의 bounding box를 예측하는데, 학습 시에는 오직 하나의 bounding box만이 하나의 object를 예측하도록 한다.(이때, 이 boudning box가 해당 object에 대해 Responsible 하다고 한다.) 이것은 predictor의 specialization으로 이어지고 각각의 predictor는 어떠한 크기, 비율, 물체의 클래스 등등으로 더 잘 예측하게 되어 결과적으로는 전체적인 재현율(recall)을 높인다.

Loss function은 다음과 같다.

$$ \displaystyle \lambda_{\text{coord}} \sum_{i=0}^{S^2} \sum_{j=0}^{B} \mathbb{1}_{ij}^{\text{obj}} \left[ (x_i - \hat{x}_i)^2 + (y_i - \hat{y}_i)^2 \right] \

\lambda_{\text{coord}} \sum_{i=0}^{S^2} \sum_{j=0}^{B} \mathbb{1}_{ij}^{\text{obj}} \left[ (\sqrt{w_i} - \sqrt{\hat{w}_i})^2 + (\sqrt{h_i} - \sqrt{\hat{h}_i})^2 \right] \
\sum_{i=0}^{S^2} \sum_{j=0}^{B} \mathbb{1}_{ij}^{\text{obj}} (C_i - \hat{C}_i)^2 \
\lambda_{\text{noob}} \sum_{i=0}^{S^2} \sum_{j=0}^{B} \mathbb{1}_{ij}^{\text{noobj}} (C_i - \hat{C}_i)^2 \
\sum_{i=0}^{S^2} \mathbb{1}i^{\text{obj}} \sum{c \ \in \ \text{classes}} (p_i(c) - \hat{p}_i(c))^2 $$
$\mathbb{1}_i^{\text{obj}}$ : object가 cell $i$에 있는 경우
$\mathbb{1}_{ij}^{\text{obj}}$ : cell $i$의 bounding box $j$가 해당 예측에 Responsible 한 경우
line 1~4는 bounding box에 대한 loss
- line 1~3 : object를 포함하는 bounding box인 경우
  - line 1~2 : localization error
  - 3 : confidence error
- line 4 : object를 포함하지 않는 boudning box인 경우, confidence error

Loss function에 두가지 특징이 있다. (1) line 4를 보면, grid cell에 object가 위치한 경우에만 페널티를 주고 있다. (2) line 1~2에서는 ground-truth box에 대해 Responsible한 (예를 들어, IoU가 제일 높은) box의 좌표 error에만 페널티를 주고 있다.

2.4 Limitations of YOLO

Spatial Constraints

YOLO는 하나의 grid cell이 2개의 bounding box, 하나의 class만 예측할 수 있다는 단점을 가지고 있다. 이러한 spatial constraint로 인해 물체가 서로 근접해 있는 경우, 물체가 작은 경우에 잘 검출하지 못하는 경우가 있다.

Generalization

모델이 데이터로부터 bounding box를 학습하기 때문에, 새로운 비율에 일반화하는 능력은 떨어진다. 또한 bounding box를 예측할 때 downsampling layer를 통해 얻어진 저품질의 feature를 이용한다는 것도 모델의 전체적인 능력을 저하한다.

Loss Function

손실 함수가 bounding box의 크기와 관계없이 모두 error를 동일하게 대한다. large box에서의 small error는 일반적으로 무시할만한 반면, small box에서의 small error는 IOU에서 훨씬 영향이 크다. YOLO의 error의 대부분은 부정확한 localization 때문이다.

[Paper] R-CNN(2013)

Wed, 09 Mar 2022 09:09:54 GMT

용어 정리

Non-maximum suppression(NMS, 최대 억제)
- 한 물체에 여러 bounding box가 있을 때, 한 bounding box만을 남기도록 하는 기술.
- 가장 점수(confidence)가 높은 bounding box 기준으로 나머지 bounding box를 제거한다.
- 관련 블로그 링크
agnostic detection : 물체의 종류(class)를 모르는 상태에서도 object를 detect한다는 것을 의미함
Hard Negative Mining : Object Detection에서 배경인데 사람이라고 잘못 예측하는 경우(Hard Negative, False Positive)가 있다. 이러한 사례들을 모아서(Mining) 데이터셋에 추가하고 재학습하면 오류에 강해지게 된다.
Object Detection에 이용되는 Metric(IoU, mAP ...) 설명

요약

simple and scalable detection 알고리즘
mean average precision(mAP) 53.3% 달성. 이전 VOC 2012 베스트 모델보다 약 30% 향상
인사이트
- object를 localize, segment하기 위한 bottom-up region proposal에 CNN을 사용
- 레이블링된 훈련 데이터가 부족할때, supervised pre-training for an auxiliary task ➡️ domain specific fine-tuning이 굉장한 성능 향상을 보여줌.
Region Proposal에 CNN을 사용하기 때문에 이름을 R-CNN이라고 붙임 : Regions with CNN features
비슷하게 OverFeat이라는 CNN 기반 sliding-window dector가 최근에 나옴. R-CNN은 ILSVRC2013 200 class detection dataset에서 큰 차이로 OverFeat을 압도함

1. Introduction

대충 이전 모델들 이야기를 나열한다. SIFT, HOG ... 그리고 CNN의 등장. CNN localization 문제를 "recognition using region" 패러다임으로 접근. 이 패러다임은 object detection과 semantic segmentation 둘 다 성공적이었다.

위 그림은 R-CNN의 전체적인 동작 과정을 한눈에 보여주고 있다. Test time에서는 (1) 2000개의 category independent region porposal을 진행 (2) 각각의 proposal에서 CNN을 이용해 고정된 크기의 feature vector를 뽑아낸다 (3) 카테고리 별로 liner SVM을 이용해서 classification을 진행한다. 과정 (2)에서 CNN의 input 크기를 고정하기 위해서 affine image warping을 진행한다.

이전까지의 문제 중 하나는 레이블링 된 데이터의 양이 CNN을 훈련하기에 충분하지 않다는 것이었다. 전통적인 해결방법은 (1) unsupervised pre-training ➡️ suervised fine-tuning이었다. 이 논문에서는 (1) auxiliary dataset(ILSVRC)에 대해서 supervised pre-training ➡️ 작은 dataset (PASCAL)에 domain-specific fine-tuning 방법론을 제시함.

논문은 R-CNN이 계산량 면에서도 효과적임을 주장. 클래스마다 합리적일만큼 작은 행렬-벡터 곱(SVM weight $\times$ feature) 과 greedy non-maximum suppression(최대 억제)를 사용하기 때문.

2. Object Detection with R-CNN

크게 3가지 모듈로 구성됨

Region Proposal : detector에서 제공되는 후보 지역들을 선별함 (selective search)

CNN : 각 region에서 fixed-length feature를 추출

Linear SVM : 클래스별로 classification

2.1 Module Design

Region Proposal

많은 방법이 있지만 그 중 selective search를 사용. Test time일때는 항상 fast mode를 이용한다.

Feature Extraction

Bounding box를 $p$ 픽셀만큼 확장하여, 이미지 주변의 컨텍스트가 포함될 수 있도록 한다.
$227 \times 227$ 사이즈로 이미지를 변형한다.
CNN에 이미지를 넣는다. CNN은 5개의 Convolutional 레이어와 2개의 Fully Connected 레이어로 구성된다. 결과물로 4096 feature 벡터를 얻는다.

2.3 Training

Supervised pre-training

Large auxiliary dataset(ILSVRC2012 classification)을 이용해 CNN을 pre-training.

Domain-specific fine-tuning

SGD를 이용해 새로운 task(detection)와 새로운 domain(warepd proposal window)에 대해서 CNN을 학습한다. ImageNet을 위한 1000-way classification layer 대신 랜덤하게 초기화된 $(N+1)$-way classification layer를 사용한다. ($N$은 object class의 개수, $1$은 background) Ground-box와의 IoU 점수가 0.5 이상인 모든 region proposal을 참(positive)로 간주하며 나머지는 거짓(negative)으로 처리한다. pre-training에서 사용했던 값의 $1/10$인 0.001의 learning rate를 사용하며, 이는 pre-training으로 얻은 초기 값을 망치지 않고 fine-tuning하기 위함이다. 각각의 SGD iteration에서 논문은 32개의 (모든 클래스를 포함한) positive window, 96개의 background window를 샘플링하여 128의 배치 사이즈가 구성된다. background에 비해 positive window의 개수가 훨씬 적기 때문에, 샘플링을 postive window를 더 많이 뽑도록 편향시킨다.

Object category classifier

Background region이 negative라는 것은 명확하다. 그러면 일부분만을 포함하고 있는 region은 어떻게 대처해야 하나? 논문은 IoU Overlap Threshold라는 개념을 통해서 이를 해결한다. IoU 점수가 Threshold보다 낮으면 negative로 간주하겠다는 것이다. 논문은 validation set에서 grid search를 통해 탐색한 결과, 최적값으로 0.3을 선택했다.

feature가 추출되면, 클래스당 하나의 linear SVM을 학습시킨다. 훈련 데이터가 메모리에 담기에 너무 크기 때문에 standard hard negative mining method를 사용한다.

Results

VOC2010 테스트. 당시의 다른 모델들보다 훨씬 높은 성능을 보여준다. 특히 같은 region proposal 방식을 사용한 UVA와 비교하면, R-CNN의 구조의 성능이 당대의 모델들보다 훨씬 뛰어나다는 것을 볼 수 있다.

ILSVRC2013에서도 역시 우수한 성능을 보인다. 비슷한 성능을 보이는 모델들은 모두 CNN을 사용했다는 점에서 CNN의 능력 역시 엿볼 수 있다.

Appendix C. Bounding-box regression

논문은 localization 향상을 위해서 bounding-box regression을 사용한다. 입력으로는 (1) CNN을 통해서 얻은 feature vector (2) selective search가 예측한 bounding-box이다. 수식적인 설명은 다음과 같다.

N개의 training sample에 대해서, ${(P^i, G^i)}_{i=1,...,N}$이 있을 것이다. (이후 표시에서 윗 첨자 $i$는 생략한다.) $P = (P_x, P_y, P_w, P_z)$이다. 각각 중심 좌표 $(x,y)$, width, height를 나타내는 값들이다. $G$는 이 값들에 대한 ground-trugh $(G_x, G_y, G_w, G_z)$이다. 목표는 $P$를 $G$로 변환하는 것이다. 이는 다음의 과정을 통해 얻을 수 있다.

$$\hat{G}_x = P_wd_x(P)+ P_x$$ $$\hat{G}_y = P_hd_y(P)+ P_y$$ $$\hat{G}_w = P_w\text{exp}(d_w(P))$$ $$\hat{G}_h = P_h\text{exp}(d_h(P))$$

각각의 $d_(P)$는 다음 수식을 통해 얻을 수 있다. 이때, $\mathbf{w}^T$는 학습 가능한 모델 파라미터에 해당한다.

$$d(P) = \mathbf{w}^T\phi_5(P)$$

$\mathbf{w}$는 다음과 같은 regularized least square objective를 통해 학습한다.

$\displaystyle \mathbf{w} = \argmin_{\hat{\mathbf{w}}} \sum_i^N(t^i - \hat{\mathbf{w}}^T\phi_5(P^i))^2 + \lambda ||\mathbf{\hat{w}}||^2$

$(P,G)$에 대한 regression target $t$는 다음과 같이 정의된다.

$$t_x = (G_x - P_x)/P_w$$ $$t_y = (G_y - P_y)/P_h$$ $$t_w = log(G_w / P_w)$$ $$t_h = log(G_h / P_h)$$

논문에서는 두가지 이슈가 있었음을 밝히고 있다. (1) regularization은 중요했다. 저자들은 validation set에서 $\lambda = 1000$으로 설정했다. (2) 만약 $P$가 ground-truth box $G$로부터 너무 멀리 떨어져 있다면 transformation은 의미가 없다. 따라서 저자들은 proposal $P$가 최소한 하나의 ground-truth box와 근접해 있을 경우에만 학습을 진행했다. "근접성"이라는 개념을 구현하기 위해서, overlap이 threshold보다 큰 경우에만, $P$를 가장 IoU가 높은 ground-truth box인 $G$에 할당했다. 할당되지 않은 모든 propsal은 사용되지 않았다. 저자들은 클래스마다 bounding-box regressor를 학습하기 위해 각 object class마다 한번씩 진행하였다.

Test time에서, 저자들은 각각의 propsal에 점수를 매긴 다음, 새로운 window detection을 한번 진행했다. (새로운 window에 대해 점수를 얻고 새 bounding box를 예측하는 것처럼) 이 과정을 반복할 수도 있었지만 결과 향상에 도움이 되진 않았다.

[번역]NeRF : Representing Scenes as Neural Radiance Fields for View Synthesis

Sat, 05 Mar 2022 13:39:31 GMT

글쓴이의 당부

NeRF : Representing Scenes as Neural Radiance Fields for View Synthesis 논문을 공부용으로 번역한 글입니다. 고작 학부 재학생 수준의 제멋대로인 번역으로 가독성은 별로 좋지 않습니다. 5절까지 번역되어 있습니다. 웬만하면 원문을 읽으시거나 유튜브에서 관련 동영상을 찾아보시길 권장드립니다.

Abstract

우리는 입력 시점의 sparse set을 이용하는 continuous volumetric scene function을 학습하여, 복잡한 장면에 대한 새 시점을 합성하는 태스크(synthesizing novel niew)에 SOTA를 달성하는 새 방법을 제시한다. 우리의 알고리즘은 단일한 5D 좌표를 입력으로 이용하고, 공간상 한 지점에서의 volume density와 view-dependent emitted radiance(역자 - 밀도와 빛에 따라 달라지는 빛)을 출력하는 fully connected network(non-convolutional)를 이용해 장면을 표현한다. 우리는 카메라 빛을 따라서 5D 좌표의 출력값을 이용해 시점을 합성하고(synthesize views), 전통적인 volume rendering 기법을 이용해 색과 밀도를 이미지로 사영(project)한다. Volume rendering 기법은 미분 가능하므로, 학습할 유일한 입력은 카메라 위치가 알려진 이미지들의 집합이다. 우리는 photorealistic novel view of scene 렌더링하기 위해 어떻게 NeRF(neural radiance field)를 최적화해야 하는지를 설명한다. 그리고 neural rendering과 시점 합성 태스크에서 이전의 결과들을 뛰어넘는 성능을 보여줌을 입증한다. 시점 합성의 결과물은 비디오를 통해서 제일 잘 확인할 수 있으므로, 설득력 있는 비교를 위해서 보충 비디오를 보는 것을 독자분들께 촉구하는 바이다.

키워드 : scene representation, view synthesis, image-based rendering, volume rendering, 3D deep learning

1. Introduction

이 연구에서, 우리는 캡처 이미지들의 집합을 렌더링 할때의 에러를 줄이기 위해 연속적인 5D 장면 표현의 파라미터들을 직접 최적화(학습)하는 새로운 방법으로 시점 합성의 오래된 문제를 다룬다.

우리는 정적인 장면을 (1)공간상의 점 $(x,y,z)$마다 방향 $(\theta, \phi)$로 방출하는 빛, (2) 각 점 $(x,y,z)$마다 빛이 얼마나 통과할 것인지를 결정하는 불투명처럼 행동하는 밀도(density)를 출력으로 하는 연속적인 5D 함수로 표현한다. 우리의 방법은 컨볼루션 레이어 없이 오직 fully connected neural network(= multilayer perceptron, MLP)만을 이용한다. 그리고 5D 좌표 $(x,y,z,\theta,\phi)$를 이용해 밀도(single volume density)와 색(view-dependet RGB color)를 회귀(regress)함으로써 이 함수를 표현한다. 이 NeRF(neural radiance field)를 특정 시점에서 렌더링 하기 위해서 (1) 장면의 카메라 빛들을 따라가며 공간상의 3D 포인트들을 샘플링하고 (2) 이 포인트들과 대응하는 2D 시점 방향을 신경망의 입력으로 사용해 (각 포인트들의) 색과 밀도를 얻어낸 후, (3) 전통적인 volume rendering 방식을 이용해 색과 밀도를 누적하는 방식으로 2D 이미지를 만들어낸다. 이 과정 모두 미분 가능하기 때문에, 우리는 관찰한 이미지와 이에 대응되는 렌더링된 결과물의 간의 차이(에러)를 줄여나가며 모델을 최적화하는(학습하는) 과정에서 그래디언트 경사하강법을 사용할 수 있다. 다양한 시점에 걸쳐 에러를 줄여나가는 것은 결국 네트워크로 하여금 장면에 대해 일관성 있고 정답에 가까운 모델링이 가능하도록 한다. (Minimizing this error across multiple views encourages the network to predict a coherent model of the scene by assigning high volume densities and accurate colors to the locations that contain the true underlying scene content.) 그림2는 전체적인 과정을 보여주고 있다.

우리는 복잡한 장면에 대한 NeRF의 기초적인 구현체는 고해상도의 결과물을 낼 만큼 충분히 수렴하지 못하고, 카메라 빛당 요구 샘플 개수 측면에서 비효율적인 것을 확인했다. 우리는 이 문제를 5D 입력을 positional encoding으로 변환하는 방법으로 접근한다. 이는 MLP가 higher frequency function을 표현할 수 있도록 한다. 또한 우리는 hirearchial sampling을 제안한다. 이는 high-frequency scene representation을 위해 샘플링하는 과정에서 요구되는 적정 샘플의 개수를 줄이는 역할을 한다.(we propose a hierarchical sampling procedure to reduce the number of queries required to adequately sample this high-frequency scene representation.)

우리의 접근은 volumetric representation의 장점을 공유한다. 두가지 모두 실제 세계의 복잡한 모양을 표현할 수 있고, projected image를 이용한 그래디언트 기반 학습에 적합하다. 특히 복잡한 장면을 고해상도로 모델링 할 때 discretized voxel grid는 지나치게 큰 저장 공간을 요구하는데, 우리의 방법은 이를 극복할 수 있다는 점이 중요하다. 요약하자면 우리의 기술적 기여는 다음과 같다.

기본적인 MLP를 이용한 5D NeRF를 이용해, 복잡한 모양과 재질의 연속적인 장면을 표현하는 방법 제시
표준적인 RGB 이미지로부터 scene representation을 학습하기 위해 사용하는 전통적인 volume rendering 기법 기반의 미분 가능한 렌더링 방식 제시. 이는 MLP의 능력을 향상시키는 hirearchial sampling도 포함한다.
5D 좌표를 더 고차원의 공간으로 매핑하는 positional encoding 제시. NeRF를 high-frequency scene content를 표현할 수 있을만큼 성공적으로 학습하는 것이 가능케 함.

최근의 연구 동향은 3D 공간을 signed distance와 같은 잠재적인(implicit) shape representation으로 맵핑하는 MLP를 이용하여, object와 scene을 인코딩하는 것이다. 그러나 이러한 방법들은, triangle meshes / voxel grids와 같은 이산적인(discrete) representation을 사용한 방법만큼 정교하게 현실 세계를 재현(reproduce)하는 것에는 실패했다. 이 섹션에서는 이러한 두 갈래의 연구들과 우리의 연구를 비교한다. 우리의 접근법은 복잡한 현실 세계를 렌더링하는 SOTA 모델에 사용되는 neural scene representation의 능력을 진일보시켰다.

Neural 3D shape representation

최근의 연구는 xyz 좌표를 singed distance 함수나 occupancy field로 매핑하는 DNN을 이용한, 연속적인 3D shape의 잠재 표현(implicit representation of continuous 3D shapes as level sets)를 조사했다. 그러나 이러한 모델들은 ShapeNet과 같이 합성 3D shape 데이터셋에서 얻어지는 ground truth 3D geometry에만 한정되는 문제가 있었다. 이후의 연구는 미분가능한 렌더링 함수를 이용해 이 문제를 완화했다. 이는 2D 이미지만을 이용해 신경망적 잠재 모양 표현 (neural implicit shape representation)을 최적화할 수 있도록 해주었다. Niemeyr은 표면을 3D occupancy field로 표현하고, 각 ray마다 surface intersection을 수학적인 방법으로 찾은 후에, 음함수 미분(implicit diffrentiation)을 이용해 정확한 미분값(exact derivative)를 계산하는 방법을 제시한다. 각각의 ray intersection 위치는 그 점에 대해 diffuse color를 예측하는 neural 3D texture field의 input이다. Sitzmann은 각각의 연속적인 3D 좌표에서 단순히 feature vector와 RGB 컬러를 출력하는 덜 직접적인(less direct) neural 3D representation을 제안한다. 또한 표면 위치를 결정하기 위해, ray를 따라서 동작하는 RNN으로 구성된 미분 가능한 렌더링 함수도 제안한다.

이러한 기술들이 복잡하고 고해상도인 기하학을 표현할 수 있는 잠재성이 있긴 하지만, 지금까지 낮은 기하학적 복잡도를 가진 단순한 물체에 제한되어 왔고 지나치게 부드러운(oversmoothed) 결과물들을 보여주었다. 우리는 5차원의 radiance field(x, y, z + 2D view-dependent appearance)를 인코딩하는 네트워크를 최적화하는 전략이 더 고해상도의 기하학과 모습을 나타낼 수 있고, 복잡한 장면에서 실사에 가까운 novel view를 렌더링 할 수 있음을 보인다.

View synthesis and image-based rendering (시점 합성과 이미지 기반 렌더링)

특정 시점에서의 dense sampling을 가정하면, 실사에 가까운 새 시점 (photorealistic novel view)은 간단한 light field sample interpolation 기법을 이용해 만들어질 수 있다. Sparser view sampling 을 위해, 컴퓨터 비전 및 그래픽 커뮤니티는 관찰 이미지에서 전통적인 기하학 및 모양 (geometry and appearnce) 표현을 예측함으로써 상당한 발전을 이루었다. 유명한 접근법 중 하나는 diffuse 혹은 view-dependent apperacne를 가지는 mesh-based representation을 사용한다. 미분가능한 래스터라이저와 pathtracer가 경사하강법을 이용하여 mesh representation을 최적화할 수 있다. 그러나 image reprojection 기반의 경사하강법 mesh 최적화는 힘든 경우가 대부분이다. 지역 최소값 문제나 최적화 표면 (loss landscape)의 나쁜 환경 때문이다. 게다가 이러한 전략은 최적화 이전의 초기화에 있어서 고정된 방식(topology)의 template mesh를 요구한다. 그러나 이것은 실제 세계에서는 일반적으로 불가능하다.

3. Neural Radiance Field Scene Representation

우리는 입력이 3D 좌표 $\mathbf{x} = (x,y,z)$와 2D 시점(viewing direction) $(\theta, \phi)$이고, 출력이 RGB 컬러 $\mathbf{c} = (r,g,b)$와 volume density $\sigma$인 5D 벡터 함수로 연속적인 장면 (continuous scene)을 표현한다. 실제로는, 방향(direction)은 3D 카테시안 단위 벡터 $\mathbf{d}$로 표시한다. 우리는 MLP 네트워크 $F_\Theta : (\mathbf{x,d}) \rightarrow (\mathbf{c}, \sigma)$로 이 연속적인 5D 장면 표현 (scene representation)을 추정한다. 그리고 MLP 네트워크의 가중치 $\Theta$를 최적화함으로써 각각의 5D 좌표 입력을 대응하는 volume desnity와 directional emitted color(RGB 컬러 $\mathbf{c} = (r,g,b)$)으로 매핑한다.

핵심적인 공식 $F_\Theta : (\mathbf{x,d}) \rightarrow (\mathbf{c}, \sigma)$

우리는 표현(representation)이 multiview consistent하도록 할 필요가 있다. 따라서 volume density $\sigma$는 좌표 $\mathbf{x}$의 함수로만 정의되고, RGB 컬러 $\mathbf{c}$는 $\mathbf{x}$와 $\mathbf{d}$의 함수로 정의되도록 하였다. 이러한 구조를 달성하기 위해, MLP 네트워크 $F_\Theta$는 먼저 8개의 FC(Fully Connected) 레이어에 3D 좌표 $\mathbf{x}$를 통과시켜서 $\sigma$와 256차원의 feature vector를 얻는다. (이때, 활성화 함수는 ReLU를 사용하고 각 레이어의 출력은 256 차원이다.) 이때 얻은 feature vector를 camrea ray의 viewding direction $\mathbf{d}$와 concat하여 벡터를 얻은후, 다시 하나의 FC 레이어에 넘겨주고, view-dependent한 RGB 컬러 $\mathbf{c}$를 얻는다. (이때 FC 레이어의 활성화 함수는 ReLU, 128차원이다)

Fig.3는 우리의 방법이 non-Lambertain 효과를 위해서 어떻게 시점(viewing direction)을 활용하는지 보여준다. Fig.3 : 시점을 고려한 빛(view-dependent emitted radiance)의 시각화. NeRF는 공간적 위치 $\mathbf{x}$와 시점 $\mathbf{d}$를 고려한 5차원 함수를 이용해 RGB 컬러를 얻는다. 이 그림에서, 우리는 배의 두가지 점에서 시점에 따른 색 분포를 비교해보고자 한다. (a)와 (b)는 두 고정된 3D 점에서 카메라 위치에 따른 차이를 보여준다. NeRF는 두 점에서 바뀌는 반사광(specular apperance)을 예측할 수 있으며, (c)는 모든 시점에 걸친 색 분포를 보여준다.

Fig.4는 시점에 대한 고려 없이 ($\mathbf{x}$만을 입력으로 사용함으로써) 훈련된 모델이 반사성(specularities)를 표현하는데 어려움이 있음을 보이고 있다. Fig.4 : 위 사진은 입력 좌표를 넘겨줄 때 고차원의 positional encoding을 이용하는 우리의 방법이 시점을 고려한 빛을 표현하는데 얼마나 효과적인지를 보여준다. 시점 고려를 제거한 모델은 불도저 타이어 부분의 반사광을 재현하는데 실패하고 있다. Poistional encoding을 제거하는 것은 결과물에서 정교함을 심각하게 저해하여 지나치게 부드러운 모양(oversmoothed appearance)을 생성한다.

4. Radiance Field와 Volume Rendering

5D NeRF는 어떤 장면을 volume desnity와 directional emitted radiance(역주 - 간단하게 말해서 $\mathbf{(\sigma, c)}$)를 가지는 공간상의 점들로 표현한다. NeRF는 전통적인 볼륨 렌더링 (classical volume rendering) 원리를 이용해서 장면을 지나는 빛의 색을 렌더링한다. volume density $\mathbf{\sigma(x)}$는 특정 위치 $\mathbf{x}$의 아주 작은 입자에서 빛이 멈출 차분 확률(differential probability)를 의미한다.(역주 - 간단하게 말하면, 얼마나 빛을 멈추게 할만큼 밀도가 높고 딱딱한가). $t_n$부터 $t_f$까지, 카메라의 빛 $\mathbf{r(t) = o + td}$에 대한 예상 컬러 $\mathbf{C(r)}$은 다음의 수식으로 표현할 수 있다.

$\mathbf{C(r)} = \displaystyle\int_{t_n}^{t_f} T(t) \sigma(\mathbf{r}(t))\mathbf{c(r}(t),\mathbf{d})dt \quad\quad(1)\ \text{where } T(t) = \text{exp}\left(-\displaystyle\int_{t_n}^{t_f} \sigma(\mathbf{r}(s))ds\right)$

(역주 - 간단하게 $T(t)\sigma\mathbf(r(t))$를 weight로 해석하여 각 컬러에 대한 가중합 정도로 생각할 수 있다.)

$T(t)$는 $t_n$부터 $t$까지 빛을 따라서 누적된 투과도를 의미한다. 즉, $t_n$부터 $t$까지 빛이 진행할 때 어떤 입자에도 부딪히지 않을 확률이다 (역주 - volume density $\sigma$에 반비례 하는 개념). 연속적인 neural radiance field에서 시점을 렌더링 하는 하는 것은 곧 어떤 가상 카메라의 각 픽셀을 통과하는 카메라 빛들에 대한 적분 값 $C\mathbf{(r)}$을 추정하는 작업을 의미한다.

우리는 이 연속적인 적분값을 구적법(quadrature)를 이용하여 수학적으로 근사(estimate)할 것이다. MLP는 위치의 고정된 이산 집합에서만 동작하기 때문에 (be quried at a fixed discrete set of locations), 이산적인 voxel grid의 렌더링에 흔히 사용되는 deterministic quadrature는 해상도에 있어서 제약이 있을 수 밖에 없다. 대신, 우리는 다음과 같은 stratifed sampling 접근법을 사용한다 : [$t_n, t_f$]를 N개의 칸(bin)으로 균등하게 나눈 다음, 각 칸에서 균등 분포를 이용하여 하나의 샘플을 뽑는다.

$t_i \sim \mathcal{U} \left[t_n + \frac{i-1}{N}(t_f - t_n), t_n + \frac{i}{N}(t_f - t_n)\right]\quad\quad(2)$

비록 적분값을 근사하기 위해서 샘플들의 이산 집합을 이용하지만, 최적화 과정에서 MLP가 연속적인 위치에서 평가되는 결과를 가져오기 때문에 (reuslts in the MLP being evaluated at continuous postions over the course of optimization) stratified sampling은 결국 연속적인 장면의 표현을 가능하게 한다. 우리는 이렇게 뽑힌 샘플들을 이용하여 $C\mathbf(r)$을 근사하기 위해 Max의 volume rendering review에서 논의된 quadrature rule을 사용한다.

$\hat {C}(\mathbf{r}) = \displaystyle\sum_{i=1}^{N}T_i\left(1-\text{exp}(-\sigma_i\delta_i)\right)\mathbf{c}i, \quad\quad (3) \ \text{where} \quad T_i = \text{exp} \left(-\displaystyle\sum{j=1}^{i-1}\sigma_j\delta_j\right)$

$\delta_i = t_{i+1} - t_i$는 인접 샘플 간의 거리를 의미한다. $(\mathbf{c}_i, \sigma_i)$ 집합에서 $C(\mathbf{r})$을 계산하는 함수는 미분 가능하고, 알파 값 $\alpha_i = 1 - \text{exp}(-\sigma_i\delta_i)$에 대한 전통적인 알파 합성 문제로 회귀된다.

5. Optimizing a Neural Radiance Field

이전 섹션에서 우리는 neural radiance field를 이용해 장면을 모델링하고, 이를 통해 새로운 시점(novel view)를 렌더링하는데 필요한 중요 요소를 설명했다. 그러나 Section 6.4에서 보인 것처럼, 이러한 요소들만으로는 SOTA를 달성하기 어려웠다. 그래서 우리는 고해상도의 복잡한 장면을 표현하기 위해 두가지 개선점을 제시한다. 첫번째는 입력 좌표에 대한 Positional Encoding이다. 이는 MLP가 고해상도 함수를 더 잘 표현하도록 보조하는 역할을 한다. 두번째는 Hirearchial Sampling이다. 이는 고해상도 표현(high-frequency sampling)을 더 효과적으로 샘플링하도록 도와주는 과정이다.

5.1 Positional Encoding

비록 neural network이 함수 근사에 일반적으로 잘 사용되지만, 우리는 네트워크 $F_\Theta$를 바로 입력좌표 $xyz\theta\phi$로만 운영하는 것은 잘 작동하지 않는 다는 것을 확인할 수 있었다. 이는 Rahaman의 최근 연구에서도 동일하게 나타나는데, 깊은 네트워크가 lower-frequency function을 학습하는 것에만 편항되어 있다는 것을 보여주었다. (역주 - 전반적으로 네트워크의 표현력이 낮다는 이야기) 그들은 또한 high frequency function을 이용하여 입력을 고차원으로 변환하면, 네트워크가 데이터를 더 잘 학습하고 표현력도 좋아진다는 것을 보였다.

우리는 이러한 발견을 neural scene representation 측면에서 레버리지(leverage)하여, $F_\Theta$를 다음과 같이 두 함수의 합성으로 변형한다. $F_\Theta = F_\Theta' \circ \gamma$. (전자는 학습되지만 후자는 학습되지 않는 함수이다.) 그리고 이 방법이 성능을 상당히 개선함을 보인다. $\gamma$는 $\mathbb{R}$에서 $\mathbb{R}^2$으로의 매핑 함수이고, $F_\Theta'$는 일반적인 MLP이다. 우리가 사용하는 인코딩 형식은 수식적으로 다음과 같다 :

$\displaystyle\gamma(p) = \left(\sin(2^0\pi p), ; \cos(2^0 \pi p), ; \cdots ; \sin(2^{L-1} \pi p), ; \cos(2^{L-1}\pi p)\right) \quad\quad (4)$

함수 $\gamma(\cdot)$은 ([-1,1]로 정규화된) 세개의 좌표 값 $\mathbf{x}$와 ([-1,1]의 값을 가지는) Cartesian 시점 방향 단위 벡터 $\mathbf{d}$에 적용된다. 우리는 실험에서 $\gamma(\mathbf{x})$에 대해서 $L = 10$, $\gamma(\mathbf{d})$에 대해서 $L = 4$를 적용했다.

비슷한 maaping이 유명한 Transformer 아키텍처에도 적용되는데, 그쪽에서도 역시 Positional encoding이라고 부른다. 하지만 Transformer에서는 목적이 조금 다른데, 순서를 포함하지 않고 있는 구조의 입력으로 사용하여 시퀀스의 토큰마다 이산적인 위치를 부여하도록 사용된다. 이와 대조적으로, 우리는 연속적인 입력 좌표를 좀 더 고차원으로 매핑하여 MLP가 higher frequency function을 더 잘 근사하도록 하기 위해 사용한다. 사영(projection)에서 3D 단백질 구조를 모델링 하는 문제의 과제에서도 비슷한 입력 좌표 매핑을 이용한다.

5.2 Hirearchial volume sampling

카메라 빛을 따라 N개의 지점에서 neural radiance field network의 값을 구해 렌더링 하는 전략은 사실 비효율적이다. 렌더링 이미지에 별 기여를 하지 않는 빈 공간과 차광된 공간이 여전이 반복해서 샘플링되기 때문이다. 우리는 volume rendering에 대한 이전의 연구에서 영감을 받아, 최종 렌더링에 대한 예상 기여도에 비례하여 샘플들을 할당하는 방법을 통해 렌더링 효율을 증가시키는 hirearchial representation을 제안한다.

장면을 표현하기 위해 단순히 하나의 네트워크만을 사용하는 대신, 우리는 두가지 네트워크를 동시에 최적화한다. 하나는 coarse 네트워크, 다른 하나는 fine 네트워크이다.

우리는 먼저 stratified sampling을 통해 $N_c$개의 지점에서 샘플링을 하여 첫번째 위치 집합을 얻고, 이 지점에서 방정식(2)와 (3)대로 coarse network의 값을 구한다. Coarse network의 출력값이 주어졌을 때, 우리는 각 volume에 상관 있는 방향으로 샘플이 편향되도록 샘플링을 진행한다. 이렇게 하기 위해, 우리는 coarse 네트워크의 알파 합성된 컬러 $\hat{C}_c(\gamma)$를 모든 샘플된 컬러 $c_i$에 대한 가중합으로 재작성한다:

$\hat{C}c(\gamma) = \displaystyle\sum{i=1}^{N_c}w_ic_i, \quad\quad\quad\quad (5) \ w_i = T_i(1-\text{exp}(-\sigma_i\delta_i))$

가중치들을 $\hat{w}i = w_i / \sum{j=1}^{N_c}w_j$로 정규화하면, 빛을 따라 piecewise-constant PDF(조각마다 상수 확률밀도함수)를 얻을 수 있다. Inverse transform sampling을 이용해 이 분포로부터 다시 두번째 위치 집합 $N_f$개의 위치를 샘플링한다. 그리고 첫번째 집합과 두번째 집합의 합집합으로 fine 네트워크의 값을 얻는다. 그리고 방정식 (3)과 $N_c + N_f$개의 샘플들을 이용하여 최종적으로 렌더링된 빛의 색 $\hat{C}_f(\mathbf{r})$를 얻는다. 이 과정은 색이 뚜렷할 것으로 예상되는 지점에서 더 많은 샘플링을 하도록 한다. 이는 importance sampling과 목표가 비슷하다. 하지만 우리는 각 샘플을 전체 적분에 대한 독립적인 확률 추정치로 생각하는 대신, 샘플된 값을 모든 정의역에 대한 비균등 이산화로 사용한다. (We use the sampled values as a nonuniform discretization of the whole integration domain rather than treating each sample as an independent probabilistic estimate of the entire integral)(역주 - 뭔소린지 모르겠다...)

5.3 구현 과정의 세부사항

우리는 장면마다 서로 다른 네트워크를 최적화한다. 이 작업은 장면을 촬영한 RGB 이미지들의 데이터셋, 대응하는 카메라 위치, 고유한 파라미터, 장면 경계(scene bounds)를 필요로 한다. 각각의 최적화 iteration에서, 우리는 데이터셋의 모든 픽셀의 집합으로부터 카메라 빛을 배치 단위로 샘플링 한다. 그 후 5.2절에 묘사된대로 hirearchial sampling을 진행하여 coarse 네트워크에서 $N_c$개의 샘플을 뽑고, fine 네트워크에서 $N_c + N_f$개의 샘플을 뽑는다. 그 후에는 두 샘플 집합으로부터 빛의 색을 렌더링 하기 위해 4절의 volume rendering을 진행한다. 손실 함수는 단순히 coarse와 fine 네트워크가 렌더링한 색과 true 픽셀 색간의 전체 squared error이다.

$\displaystyle\mathcal{L} = \sum_{r \in \mathcal{R}} \left[\left|\left| \hat{C}_c(\mathbf{(r)} - C(\mathbf{r})\right|\right|_2^2 + \left|\left| \hat{C}_f(\mathbf{(r)} - C(\mathbf{r})\right|\right|_2^2\right]\quad\quad$ (6)

$\mathcal{R}$은 은 각 배치에서 ray 집합을 의미한다. 그리고 $C(\mathbf{r}), \hat{C}_c(\mathbf{r}), \hat{C}_f(\mathbf{r})$은 각각 ray $\mathbf{r}$에 대한 정답, coarse 네트워크의 예측값, fine 네트워크의 예측값(RGB 컬러)이다. 물론 최종 렌더링은 $\hat{C}_f(\mathbf{r})$를 이용해 진행하지만, coarse 네트워크가 fine 네트워크에 샘플 할당에 이용되기 때문에 $\hat{C}_c(\mathbf{r})$의 값 또한 minimize한다.

우리의 실험에서, 4096 ray 배치, $N_c=64$, $N_f=128$의 값을 사용했다. Adam optimizer를 사용하였으며, $5 \times 10^{-4}$의 초기 learning rate 값을 사용하고, 학습 과정에서 $5 \times 10^{-5}$로 exponentially decay 하도록 설정했다. (다른 Adam optimizer의 값들은 기본값으로 놔두었다 : $\beta_1 = 0.9$, $\beta_2 = 0.999$, $\epsilon = 10^{-7}$). NVIDIA V100 GPU에서 한 장면을 학습 및 수렴하는 데에는 100k-300k iteration (약 하루~이틀)이 요구되었다.

[PyTorch] Transformer 구현

Fri, 14 Jan 2022 10:19:27 GMT

계기

작년부터 Transformer가 성능이 그렇게 좋다더라... 이제 RNN이고 LSTM이고 다 필요없고 이미 NLP는 저걸로 천하통일이라더라... 하는 소식을 듣고 있었다. 중간에 강화학습 공부 좀 찍먹해보다가 다시 캐글에서 PetFinder 이미지 비전 태스크 공부로 선회한 상태였는데, 내가 주로 참고했던 노트북은 [Pytorch] Hybrid Swin Transformer + CNN 이었다.

이 노트북에서 사용된 Hybrid Swin Transformer는 CNN (EfficeintNet)을 이용해서 패치를 뽑아낸 다음, Swin Transformer의 입력으로 넣어주는 방식이다. 그런데 이때까지도 나는 Transformer의 이름만 들어봤지 아직 제대로는 공부해보지 못한 상태여서, Trnasformer라는 구조에 대해서 제대로 공부해봐야겠다고 생각했다.

Youtube 강의 + 논문

나동빈이라는 분이 유튜브에 업로드한 [딥러닝 기계 번역] Transformer: Attention Is All You Need (꼼꼼한 딥러닝 논문 리뷰와 코드 실습) 유튜브 강의가 큰 도움이 되었다. 먼저 논문을 읽기 전에 이 유튜브를 들었는데, 덕분에 큰 그림을 잡을 수 있었다. 그리고 논문 읽어본 거, 처음이었는데 생각보다 별거 아니라는 생각이 들었다. 영어가 좀 빡세다는 점, 그리고 이게 뭐지 싶은 구조들이 참조 논문으로 우수수 튀어나오는 것만 제외하면... 사실 논문 하나 대충 읽는 건 별로 안걸리지만 만약 대학원생이 되어서 참조 논문까지 싹 다 이해하면서 논문을 읽고 그 분야를 섭렵해나가야 한다? 진짜 쉽지 않을 것 같다는 생각을 했다.

아무튼 논문까지 읽고, PyTorch 라이브러리에 대한 복습도 좀 할 겸 Transformer 자체를 코드로 구현해봐야겠다는 생각이 들었다. 사실 그때까지 이해가 좀 가지 않는 부분도 있어서 코드로 구현하면 확실히 이해가 될 것 같다는 생각도 들었고, 이 구조를 베이스로 한 모델들이 지금 NLP랑 Vision 분야를 휩쓸고 있는 상태에서, 베이스를 이해하지 않으면 쉽지 않겠다는 생각이 들어서이다.

Transformer 구현

링크는 Github에 올려놓았다. 주요 코드는 아래와 같다.

Mask Function

코드 보기

Transformer를 구현하며 배운 것들

Fri, 14 Jan 2022 10:18:29 GMT

Pytorch Layer Initialization

첫번째 : apply() 함수 이용하기

def apply_xavier(layer):
    if hasattr(layer, 'weight'):
        print(layer)
        torch.nn.init.xavier_uniform_(layer.weight)

encoder_layer=EncoderLayer(128,8,2048)
encoder_layer.apply(apply_xavier)

Output:

Linear(in_features=128, out_features=128, bias=True)
Linear(in_features=128, out_features=128, bias=True)
Linear(in_features=128, out_features=128, bias=True)
Linear(in_features=128, out_features=128, bias=True)
Linear(in_features=128, out_features=2048, bias=True)
Linear(in_features=2048, out_features=128, bias=True)
LayerNorm((128,), eps=1e-05, elementwise_affine=True)

두번째 : named_parameters() 함수 이용하기

named_parameters() 함수는 (param_name, param_weight) 형태의 튜플을 반환한다.

for param in encoder_layer.named_parameters():
  print(param[0])

Output:

multiheadattention.fcQ.weight
multiheadattention.fcQ.bias
multiheadattention.fcK.weight
multiheadattention.fcK.bias
multiheadattention.fcV.weight
multiheadattention.fcV.bias
multiheadattention.fcOut.weight
multiheadattention.fcOut.bias
ffn.fc1.weight
ffn.fc1.bias
ffn.fc2.weight
ffn.fc2.bias
layerNorm.weight
layerNorm.bias

Xavier Uniform Initilization을 이용하고자 한다면 다음과 같이 조건식을 추가하여 초기화하면 된다. (bias와 nn.layerNorm()은 초기화 대상이 아니므로 제외해준 모습을 볼 수 있다.)

for layer in encoder_layer.named_parameters():
    if 'weight' in layer[0] and 'layerNorm' not in layer[0]:
        print(layer[0])
        torch.nn.init.xavier_uniform_(layer[1])

Output:

multiheadattention.fcQ.weight
multiheadattention.fcK.weight
multiheadattention.fcV.weight
multiheadattention.fcOut.weight
ffn.fc1.weight
ffn.fc2.weight

Pytorch에서 List 형식으로 layer 선언하기

처음에 작성했던 코드는 다음과 같다.

class Decoder(nn.Module):
    def __init__ (self, N, hidden_dim, num_head, inner_dim):
        super().__init__()

        self.dec_layers = []
        for i in range(N):
            self.dec_layers.append(DecoderLayer(hidden_dim, num_head, inner_dim))

이 코드는 문제가 있는 코드이다. 왜일까? 저렇게 단순히 Python 리스트에 레이어를 집어넣어서 사용하면 Pytorch가 layer를 제대로 인식하지 못하는 상황이 벌어지기 때문이다. 이 말인 즉, 상위 layer에서 children()을 호출해도 저 self.dec_layers안의 layer들은 호출되지 않는다는 이야기이다. 당연히 model.parameters()를 호출해도 저 layer들의 parameter들은 누락되게 되고, 학습을 해도 optimizer가 최적화하지 않는 치명적인(!) 상태가 된다. (당연하다, optimizer에 parameter가 등록되어 있지 않으니까.)

그러면 어떻게 해야할까?

nn.ModuleList

이를 위해서, Python은 nn.ModueList를 제공한다. 사용법은 다음과 같다

self.dec_layers = nn.ModuleList([DecoderLayer(hidden_dim, num_head, inner_dim) for _ in range(N)])

그러면 Pytorch에서 정상적으로 layer들을 인식한다. 쓸 때는 일반적인 반복문처럼 for layer in self.dec_layers:으로 사용하면 된다.

Pytorch에서 += 연산자의 위험성

참고 사이트

Pytorch에서 layer를 짤 때 다음과 같은 코드는 조심해야 한다.

    def forward(self, input, mask = None):

        # input : (bs, seq_len, hidden_dim)

        # encoder attention
        # uses only padding mask
        output = self.multiheadattention(srcQ= input, srcK = input, srcV = input, mask = mask)
        output = self.dropout1(output)
        output += input
        output = self.layerNorm(output)

        output_ = self.ffn(output)
        output_ = self.dropout2(output_)
        output += output
        output = self.layerNorm(output)

        # output : (bs, seq_len, hidden_dim)
        return output

왜냐? 이 += 연산자가 바로 inplace 연산자이기 때문이다. 따라서 이를 이용해서 layer를 짜고 loss.backward()를 하면 Pytorch가 One of the variables needed for gradient computation has been modified by an inplace operation 에러를 내뿜게 된다. 디버깅하기 힘드니까 조심하자.... Pytorch를 사용하면서 느끼는 건 잘 모르면 진짜 그냥 안전하게 짜는게 에러 안나고 베스트라는 것이다. 코드 길이 줄이겠다고 += 썼다가 에러 잡느라 몇시간을 날렸다....

모델 코드가.... detach()...?

class Transformer(nn.Module):
    def __init__(self, N = 3, hidden_dim = 256, num_head = 8, inner_dim = 512):
        super().__init__()
        self.encoder = Encoder(N, hidden_dim, num_head, inner_dim)
        self.decoder = Decoder(N, hidden_dim, num_head, inner_dim)

    def forward(self, enc_src, dec_src):
        # enc_src : (bs, seq_len)
        # dec_src : (bs, seq_len)

        # print(f'enc_src : {enc_src.shape}')
        # print(f'dec_src : {dec_src.shape}')

        enc_output = self.encoder(enc_src)
        output, logits = self.decoder(dec_src, enc_src, enc_output.detach())
        # logits = (bs, seq_len, VOCAB_SIZE)

        return output, logits

문제의 코드(17).... enc_output.detach()가 보이는가? 도대체 무슨 생각을 저 코드를 넣었던 건지 모르겠다.... 저러면 당연히 encoder가 학습이 될리가 없는데 진짜 멍청함을 느끼는 순간이었다.

파란색 곡선이 보이는가...? 아 어이없어... 저거 떼자마자 귀신같이 학습이 잘된다 ^^ 마스크 수정하러 가자

Masking Function

막판까지 속썩였던 애들 중 한명이다.... 논문에서는 query_len과 key_len을 동일하게 놓고 진행한다. 그래서 처음에 padding mask와 lookahead mask 둘 다 input (bs, seq_len)을 받으면 (bs, 1, seq_len, seq_len)을 반환하도록 구현했다. (중간에 1 부분은 num_head broadcasting을 위한 것). Training 할때도 어차피 encoder와 seq_len과 decoder의 seq_len이 같기 때문에 문제가 되지 않았다.

문제는 Inference할 때의 padding mask였다. Inference할 때에는 decoder의 입력으로 토큰 하나만 들어가기 때문에, decoder의 입력은 1이다. 반대로 encoder는 문장 하나가 input으로 들어가기 때문에 일정한 seq_len을 가진다. Encoder-Decoder Self Attention 부분을 살펴보자. decoder의 입력이 srcQ가 되고, encoder의 출력이 srcK가 된다. 따라서 query_len과 key_len이 다른 상황을 마주하게 되는데, 이를 고려하지 못했던 것이다.

batch size = 1
dec_src의 seq_len = 2
enc_src, enc_ouput의 seq_len = 10
num_head = 8
hidden_dim = 256을 고려하면 다음과 같다

아무튼 그래서

pading mask : (bs, 1, 1, k_len)
lookahead mask : (bs, 1, k_len, k_len)

이렇게 수정하는 것으로 원만한 합의를 볼 수 있었다.

[강화학습] Tensorflow를 이용한 DQN 구현 (cartpole_v0)

Thu, 23 Sep 2021 14:43:00 GMT

1. 계기

Kaggle에서 도대체 내가 참여할만한 competition이 무엇이 있을까 하고 찾아보던 중 Lux AI Challenge라는 competition을 발견하게 되었었다. 강화학습과 주어진 파이썬 API를 이용해 참여해야 했는데, 이 당시(8월 말)의 나는 강화학습에 대해서는 정말 아무것도 몰라서 이론부터 시작해야 하는 입장이었다. 그래서 에라이 모르겠다 아주 간단한 것부터 구현해 보면서 감을 잡아야겠다고 느꼈고, cartpole 환경에서 제일 기본적인 이론인 DQN을 구현해보아야겠다고 생각했다

2. 시작

처음 개발은 Deep Q-learning으로 뱀 게임 인공지능 만들기 블로그 사이트를 참조했다. DQN을 코드로 아주 자세하게 정리해두셔서 코드를 통째로 VSCode에 붙여넣고 한줄한줄 주석 달고 뜯어가면서 공부했다. 고등학생 시절부터 책에 하이라이트 치고 옆에 작은 글씨로 주석 달듯이 필기하면서 공부하던 습관이 있었는데 비슷한 공부법이라서 잘 먹히는 것 같다. 시간은 좀 많이 걸리지만...

3. 개발 과정

사실 전체적인 구조는 Deep Q-learning으로 뱀 게임 인공지능 만들기의 구조를 거의 베끼다시피 해서 만들었다. 다만, 코드를 무작정 베끼기보다는 먼저 블로그에 나온 코드 구현을 이해한 후, 스스로 만들어볼려고 노력했다. 사실 구조 자체는 엄청 간단하다.

DQNAgent

from tensorflow import keras
from keras import models
from keras import layers
from tensorflow.python.keras.backend import relu, sigmoid
from tensorflow.python.keras.models import Sequential
from ReplayMemory import ReplayMemory
import numpy as np
from ReplayMemory import ReplayMemory


class DQNAgent(object):
    def __init__(self, batch_size=100, gamma=0.9):
        # 학습에 사용할 model과 target_model을 설정한다
        self.model = self._create_model()
        self.target_model = self._create_model()
        # 처음에는 두 모델을 동일 weight로 설정해준다
        self.target_model.set_weights(self.model.get_weights())
        self.replayMemory = ReplayMemory()
        self.gamma = gamma  # 감마, 클수록 미래의 이익을 고려한다
        self.batch_size = batch_size
        self.callbacks = [
            keras.callbacks.TensorBoard(
                log_dir="my_log_dir",
                histogram_freq=1,
                embeddings_freq=1,
            )
        ]

    def _create_model(self) -> Sequential:
        model = models.Sequential()
        model.add(layers.Dense(10, activation=relu, input_shape=(4,)))
        model.add(layers.Dense(10, activation=relu))
        model.add(layers.Dense(2))
        model.compile(optimizer="rmsprop", loss="mse")
        return model

    def forward(self, data):
        return self.model.predict(data)

    # replayMemory를 이용해 Agent를 학습
    def train(self):

        # replayMemory에 저장된 experience의 개수는 2000개 이상이어야 함
        if 2000 > len(self.replayMemory):
            return

        # batch_size만큼 샘플링한다
        # (cur_state, action, reward, done, info, next_state) : list
        samples = self.replayMemory.sample(self.batch_size)
        # batch data를 생성한다

        current_states = np.stack([sample[0] for sample in samples])
        current_q = self.model.predict(current_states)
        next_states = np.stack([sample[5] for sample in samples])
        next_q = self.target_model.predict(next_states)

        for i, (cur_state, action, reward, done, info, next_state) in enumerate(
            samples
        ):
            if done:
                next_q_value = reward
            else:
                next_q_value = reward + self.gamma * np.max(next_q[i])
            current_q[i][action] = next_q_value

        # 학습!!
        self.model.fit(
            x=current_states,
            y=current_q,
            batch_size=self.batch_size,
            verbose=False,
        )

    # target model의 가중치를 model의 가중치로 update 한다
    def _update_target_model(self):
        self.target_model.set_weights(self.model.get_weights())

    def save(
        self,
        path: str,
        model_name: str,
        version: str,
        num_trained: int,
        target_model_name: str = None,
    ):
        """
        모델 저장 이름 예시
        /path/cartpole_v5_300_trained.h5

        """
        save_name = f"{path}/{model_name}_{version}_{num_trained}_trained.h5"
        target_model_name = f"target_{model_name}"
        target_save_name = (
            f"{path}/{target_model_name}_{version}_{num_trained}_trained.h5"
        )
        self.model.save(save_name)
        self.target_model.save(target_save_name)

    def load(
        self,
        path: str,
        model_name: str,
        version: str,
        num_trained: int,
        target_model_name: str = None,
    ):
        save_name = f"{path}/{model_name}_{version}_{num_trained}_trained.h5"
        target_model_name = f"target_{model_name}"
        target_save_name = (
            f"{path}/{target_model_name}_{version}_{num_trained}_trained.h5"
        )
        self.model = keras.models.load_model(save_name)
        self.target_model = keras.models.load_model(target_save_name)

DQNTrainer

self.agent = DQNAgent()로 DQNAgent를 불러온 후, Agent로 Episode를 반복하면서 학습을 진행하도록 하는 것이 주된 목적이다. 학습을 담당하는 코드는 다음과 같다.

from sys import version
from DQNAgent import DQNAgent
import numpy as np
import gym
from tqdm import tqdm
import os
import matplotlib.pyplot as plt


class DQNTrainer(object):
    def __init__(
        self,
        env: gym.Env,
        max_episode=500,
        step_size=2000,
        epsilon=0.99,
        epsilon_decay=0.995,
        temp_save_freq=100,
        model_path=os.path.join(os.getcwd(), "model"),
        model_name="model",
        version="test",
        min_epsilon=0.01,
        temp_save=True,
        save_on_colab=False,
    ):
        self.agent = DQNAgent()
        self.max_episode = max_episode
        self.env = env
        self.step_size = step_size
        self.epsilon = epsilon
        # 학습할때 임시로 저장할 빈도
        self.temp_save_freq = temp_save_freq
        # 모델을 저장할 경로
        self.model_path = model_path
        # 저장할 모델의 경로
        self.model_name = model_name
        # 저장할 최종 모델의 버전
        self.version = version
        self.target_model_path = "target_" + model_path
        # epsilon greedy
        self.min_epsilon = min_epsilon
        self.epsilon_decay = epsilon_decay
        # 임시 저장 여부
        self.temp_save = temp_save
        # colab에서 저장할지 여부
        self.save_on_colab = save_on_colab
        # episode별로 sum of reward를 저장
        self.save_epi_reward = []
        self.save_epi_step_num = []

    def train(self):
        pbar = tqdm(initial=0, total=self.max_episode, unit="episodes")

        for episode in range(self.max_episode):
            cur_state = self.env.reset()
            step, episode_reward, done = 0, 0, False

            while not done:
                if (np.random.randn(1)) <= self.epsilon:
                    # 0, 1 중에서 무작위로 수를 하나 뽑는다
                    action = np.random.randint(2)
                else:
                    # Q(cur_state,a)중에서 가장 값이 높도록 하는 a를 action으로 고른다
                    output = self.agent.forward(cur_state.reshape(-1, 4))
                    output = np.argmax(output)
                    action = output

                next_state, reward, done, info = self.env.step(action)

                # replayMemory에 결과를 저장한다
                self.agent.replayMemory.add(
                    (cur_state, action, reward, done, info, next_state)
                )

                # replayMemory를 이용해 학습을 진행한다
                self.agent.train()

                # 상태 업데이트
                cur_state = next_state
                episode_reward += reward
                step += 1

                if done:
                    break

            # target_model의 가중치를 model과 동기화
            self.agent._update_target_model()

            # epsilon decay
            self.epsilon = max(self.epsilon * self.epsilon_decay, self.min_epsilon)

            # 설정한 빈도에 따라서 임시 저장
            if self.temp_save == True:
                if (episode % self.temp_save_freq) == 0:
                    if self.save_on_colab:
                        self.colab_save(
                            model_name=self.model_name,
                            version=self.version,
                            num_trained=episode,
                        )
                    else:
                        self.agent.save(
                            path=self.model_path,
                            model_name=self.model_name,
                            version=self.version,
                            num_trained=episode,
                        )

            pbar.update(1)

            self.save_epi_reward.append(episode_reward)
            self.save_epi_step_num.append(step)

            ####### 한 EPISODE 종료 #########

        # --------------모든 에피소드 종료---------------- #

        # 모든 학습이 끝나면 모델을 저장한다
        if self.save_on_colab:
            self.colab_save(
                model_name=self.model_name,
                version=self.version,
                num_trained=self.max_episode,
            )
        else:
            self.agent.save(
                path=self.model_path,
                model_name=self.model_name,
                version=self.version,
                num_trained=self.max_episode,
            )

        # episode에 따른 학습결과 (reward의 총합)을 그래프로 표시한다.
        plt.plot(self.save_epi_reward)

    def colab_save(self, model_name: str, version: str, num_trained: int):
        from google.colab import drive
        import os

        mount_path = "/content/drive"
        drive.mount(mount_path)

        model_path = os.path.join(mount_path, "MyDrive", "model")

        # save model on google drive
        self.agent.save(
            path=model_path,
            model_name=model_name,
            version=version,
            num_trained=num_trained,
        )

    def colab_load(self, model_name: str, version: str, num_trained: int):
        from google.colab import drive
        import os

        mount_path = "/content/drive"
        drive.mount(mount_path)

        model_path = os.path.join(mount_path, "MyDrive", "model")

        # load model on google drive
        self.agent.load(
            path=model_path,
            model_name=model_name,
            version=version,
            num_trained=num_trained,
        )

RL을 학습하기 위해서는 먼저 environment에서 직접 행동을 해보며 데이터를 쌓아야한다. 이 부분을 구현한 코드가 위의 def train(self)이다. 최대 max_episode만큼 episode를 진행하면서 경험을 하고, ReplayMemory에 결과를 저장한다. self.agent.train()부분이 ReplayMemory에 저장된 학습 결과들을 이용해서 학습을 수행하는 코드이다. 이 부분은 DQNAgent.py에 따로 구현해놓았다.

주된 학습 환경으로는 Google의 Colab을 이용했다. 학습 중간 중간 self.temp_save_freq마다 임시 저장을 진행한다. self.save_on_colab이 True이면 Colab상에서 학습한다고 가정하고 모델을 Google Drive에 임시 저장한다. False인 경우에는 학습이 로컬 환경에서 진행된다고 가정하고 모델을 로컬에 임시 저장한다.

4. 첫번째 구현 시도와 실패, 그리고 완성

위에서 구현한 코드들은 완성 버전의 코드들이다. 첫번째 구현은 30000번의 Episode를 플레이해도 도무지 학습이 제대로 진행되지 않는 문제점이 있었다. 그래서 내 코드를 고쳐보면서 참고한 블로그가 바로 Tensorflow2로 만든 DQN 코드: CartPole-v1였다. 비교해본 결과, 전반적으로 내 코드의 문제점이 보였다.

학습에는 항상 충분한 양과 질의 데이터가 필요하다는 점을 명심할 것 (둘 다 중요!)

ReplayMemory의 문제 처음에는 아무 생각 없이, 데이터가 batch_size보다 많으면 ReplayMemory를 이용한 학습이 진행될 수 있도록 했었다. batch_size의 기본값은 100이었는데, 그러다보니까 충분한 양의 데이터가 모이지 못했음에도 학습을 진행하게 되어서, 결과적으로 모델이 올바르게 학습하지 못했던 것 같다. 학습이 잘 진행되지 못했던 주 원인.
Episode Play 단계에서의 문제 처음에는 한 Episode를 플레이할때 특정 step(2000정도)까지만 반복하고 Episode를 종료하게 했었다. CartPole environmnet에서는 action을 취할때마다 +1, 쓰러지지 않도록 성공할 때 (done == True) +200의 reward를 지급한다. step 수의 제한때문에 done == True 성공할 수 있는 상태임에도 성공 상태에 도달하지 못할 수도 있을 것 같아서 반복문을 while not done :으로 수정했다. 다만 나중에 체크했을때, 이렇게 해놔도 step이 2000이상 반복되는 경우는 없어서 크게 영향은 없었던 것으로 추정한다

학습 결과 : Episode 별 Reward

대충 200 Episode가 넘어가면서 200 이상의 Reward를 엄청 자주 찍는 것을 볼 수 있다. Pole이 넘어지지 않고 똑바로 서있는 '성공'을 달성시 200의 Reward가 주어지므로, 모델이 아주 잘 훈련되었다는 의미이다. 다만, 왜 이렇게 그래프가 좀 왔다리갔다리 하는지는 잘 모르겠다. 실제로 훈련한 모델을 이용해 실행시켜 보면 Pole이 무너지지 않고 아주 잘 서있다.

5. 주저리주저리

사실 Target Network를 업데이트할 때에는 원래는 freq를 설정해서 일정 빈도로 업데이트한다. 이것도 하이퍼 파라미터인데 귀찮아서 그냥 한 Episode마다 업데이트하도록 설정했다 ㅎㅎ...
이번 Project를 진행하면서 대충 Colab에서 어떻게 안정적으로 임시 저장을 반복하면서 학습을 진행할 수 있는가를 깨달았다는 건 좀 좋은거 같다. 돈 없는 학생 입장에서 최대한 굴려먹어야 하는데 나중에 캐글할때 대충 이런 프로세스는 유용하게 써먹을 수 있을 것 같다.
PS하면서 주석 쓰는 습관을 들였는데 (이렇게 안하면 내가 다음날 봤을때 저게 뭔 코드인지 못 알아먹기 때문에) 습관 좀 잘 들은 거 같아서 좀 뿌듯하다

6. 실습 이론

Deep Q Network
- Epsilon Decay
  - Replay Buffer
- Target Network

loggerJK.log

[Paper] DETR : End-to-End Object Detection with Transformers

Abstract

1. Introduction

2. Related Work

Set Predciton

Transformers and Parallel Decoding

Object Detection

3. The DETR model

Object Detection set prediction loss

Bounding box loss

DETR architecture

Backbone

Transformer encoder

Transformer Decoder

Prediction Feed-froward networks (FFNs)

Auxiliary decoding losses

4. Experiments

4.1 Comparison with Faster R-CNN

4.2 Ablations

Number of encoder layers

Number of decoder layers

Importance of FFN

Importance of positional encodings

중간 요약

Loss ablations

4.3 Analysis

Decoder output slot analysis

Generalization to unseen numbers of instances

4.4 DETR for panoptic segmentation

Main Result

5. Conclusion

[백준] 1865 웜홀 : 문제의 논란 정리

[알고리즘] 트리의 지름 증명

[백준] 2206 : 벽 부수고 이동하기

용어정리

생각하지 못한 Case

코딩 테스트 대비 정리

C++ STL

알고리즘 종류

TIP

주의

[Paper] YOLO : You Look Only Once

Abstract

1. Introduction

2. Unified Detection

2.1 Network Design

2.2 Training

2.4 Limitations of YOLO

Spatial Constraints

Generalization

Loss Function

[Paper] R-CNN(2013)

용어 정리

요약

1. Introduction

2. Object Detection with R-CNN

2.1 Module Design

Region Proposal

Feature Extraction

2.3 Training

Supervised pre-training

Domain-specific fine-tuning

Object category classifier

Results

Appendix C. Bounding-box regression

[번역]NeRF : Representing Scenes as Neural Radiance Fields for View Synthesis

글쓴이의 당부

Abstract

1. Introduction

2. Related Work

Neural 3D shape representation

View synthesis and image-based rendering (시점 합성과 이미지 기반 렌더링)

3. Neural Radiance Field Scene Representation

4. Radiance Field와 Volume Rendering

5. Optimizing a Neural Radiance Field

5.1 Positional Encoding

5.2 Hirearchial volume sampling

5.3 구현 과정의 세부사항

[PyTorch] Transformer 구현