1. Introduction

현 딥러닝 모델들은 새로운 시각적 개념을 배우는 데에 있어서 한계를 지니고 있다. 반대로, 인간의 시각은 단지 몇개의 라벨들을 통해서 새로운 클래스를 잘 분류해낼 수 있다. 이러한 이유로, 새로운 클래스를 구분해내는데에 있어 한정된 자원만을 이용하는 연구가 활발히 진행되고 있다.

Limitation

다만 이러한 퓨삿 분류 알고리즘은 두가지의 challenge가 있다. 첫번째로는, 구현 세부 사항의 불일치가 알고리즘들간의 상대적인 비교를 불가능하게 만든다. 그래서, 베이스라인 모델들이 상당수 과소평가되었을 가능성도 존재한다. 두번째로는, 현재의 평가지표는 제한된 학습 데이터로 새로운 클래스를 예측하는 것에 중점을 두었는데, 이러한 새로은 클래스는 사실 크게 보면 같은 데이터셋에서 등장했을 가능성이 크다. 예를 들어, 개, 고양이를 분류하는 모델로 여우를 분류하는 모델을 학습시킬 수 있는데, 동일하게 '동물' 데이터에서 등장하였다고 가정할 수 있다. 이 모델로 갑자기 차를 분류하는 모델로 학습시키면 어떻게 될까? 도메인이 급격하게 바꼈으므로 잘 학습이 되지 않을 가능성이 크다. 이런 식으로 도메인이 바뀌는 경우에 대한 평가지표가 불분명하다.

Our work & contributions

저자는 이를 해결하기 위해 여러가지 연구를 진행했다. 1) 여러 퓨삿 메소드를 동일한 환경에서 성능을 테스트 해보았다. 그 결과 깊은 백본 모델일수록 다른 여러 메소드 들간의 성능 차이가 줄어든다는 점을 볼 수 있다. 두번째로는, 선형 분류기를 거리 기반 분류기로 바꿈으로써 베이스라인 모델이 일반 소타모델과 비교하여 훨씬 경쟁력 있어졌다는 것을 볼 수 있다. 세번째로는, 기존 클래스와 새로운 클래스간의 domain shift가 발생하였을 때 실용적으로 평가할 수 있는 환경을 제안하였다. (예를 들어, 일반적인 카테고리에서 베이스 클래스를 샘플링하고, 새로운 클래스는 fine-grained(미세한?) 카테고리에서 샘플링을 하는 방법이다.) 이러한 세팅 하에서는 정교한 퓨삿러닝 알고리즘이 베이스라인에 비해 성능 측면에서의 발전을 제공하지 못한다는 점을 발견하였다.

1) 공정한 비교를 위해 알고리즘들간의 통합된 테스트배드를 제공한다. 2) 거리기반 베이스라인 모델이 훨씬 좋은 성능을 낸다. 3) 새로운 클래스와 베이스 클래스가 각각 다른 도메인에서 뽑혔을 때 공정하게 평가할 수 있는 환경 세팅을 제안하였다. 그 결과 현 퓨삿 알고리즘들은 domain shift가 발생하는 환경에서는 베이스라인 성능에 뒤쳐진다는 결과를 도출했다.

2. Related work

Initialization based methods: "learning to fine-tune"

이 접근법은 좋은 모델 초기화방법을 배우는 데에 목표를 둔다. 이를 통해 분류기가 적은 업데이트 스텝과 적은 라벨 데이터로도 효과적으로 학습할 수 있게끔 해주는 것이다. 다른 것은 optimizer 자체를 학습하는 것이다.

Distance metric learning based methods: "learning to compare"

해당 방법론은 두 이미지들의 유사성을 모델이 결정할 수 있다면, 이는 관찰되지 않은 이미지와 라벨링된 이미지들을 구분해낼 수 있다는 직관에서 비롯되었다. 이를 위해 distance나 metric을 고려하여 예측을 진행하도록 학습을 시켰다. 그 결과, 거리 기반 분류기 + 베이스라인 모델이 다른 정교한 알고리즘과 비교하였을 때 꽤 경쟁력있는 결과를 도출해냈다.

Hallucination based methods: "learning to augment"

이 방법은 모델의 베이스 클래스로부터 generator를 생성하고, 이러한 generator를 이용해 새로운 클래스 데이터에 적용하여 data augmentation하는 방법을 일컫는다. 하나는 베이스 클래스에 존재하는 모든 variation을 잘학습하는 것을 목표로 한다.(GAN) 다른 접근법은 무엇을 transfer할지는 명시하지 않았지만, 메타러닝 알고리즘에 generator를 통합한 방법이 있다고 한다. 다만 이 논문에서는 해당 접근법에 대해 따로 다루지 않았다.

3. Overview of few-shot classification algorithms

3.1 Baseline

Training stage

저자는 feature extractor인 $f_{\theta}$와 classifier인 $C(.|W_b)$를 cross entropy loss를 이용해 학습을 시켰다. 이때 인코딩된 feature은 d, output class의 개수는 c라고 지정하였다. classifier인 $C(.|W_b)$은 $W_b^{T}f_{\theta}(x_i)$로 구성되었다.

Fine-tuning stage

새로운 클래스에 대해 모델을 학습시키기 위해, pretrained network인 $f_{\theta}$는 fix시키고, 새로운 classifier인 $C(.|W_n)$을 학습시켰다.

3.2 Baseline++

더불어 학습 중 클래스 내 변이를 명시적으로 줄이는 모델인 Baseline++를 구현했다. 기존 모델과 유사하게 base class를 구분하는 weight인 $W_{b}$와 새로운 클래스를 구분하는 weight인 $W_{n}$을 지니고 있다. 이러한 디자은 베이스라인과는 사실 다른 형태를 띄고 있다. $W_b$를 만약 $[w_1,w_2, .., w_c]$로 적어보았을 때, 각 class는 d차원의 weight을 지니고 있다. 학습 단계에서는 input feature$f_{\theta}(x_i)$과 각 클래스들의 weight vector들간의 유사도를 구한다. $[s_{i,1},s_{i,2}, .., s_{i,3}]$처럼 구해지고, softmax 함수를 이용해 각 클래스에 속할 확률을 구해낸다. 이때 유사도로는 코사인 유사도를 사용한다.

3.3 Meta-learning Algorithms

저자는 여러개의 메타러닝 메소드를 사용하였는데, mathingnet, protonet, relationnet 그리고 maml을 사용하였다. meta-learning training stage에서는, 1) 우선 랜덤하게 n개의 클래스를 뽑는다. 그리고, 해당 클래스를 바탕으로 supprt set와 query set을 만든다. 이때 목표는 N-way Prediction loss를 줄이는 것을 목표로 하였다. 사이즈가 작은 support set을 기반으로 학습이 진행되었기 때문에, 모델은 적은 데이터가 주어졌을 경우 어떻게 학습을 해야하는지 자체를 배웠다고 볼 수 있다. meta-learning testing stage에서는 새로운 클래스에 대한 support set의 클래스를 예측하도록 adapt시킨다. 그리고, 사용한 각 메소드들간의 설명은 아래와 같다.

1. MatchingNet (Cosine distance)
2. ProtoNet (클래스 간 평균의 유클리드 거리)
3. RelationNet (Relation Module을 통해 자동으로 연산)
4. MAML (support set이 몇번의 그래디언트 업데이트를 통해 파라미터를 초기화하는데 사용된다. 여러 support set의 loss를 통해 gradient update를 한다.)

4. Experimental results

4.1 Experimental setup

Datasets and scenarios

총 3가지 시나리오에서 few-shot classification 문제를 다뤄보았다.

1) generic object recognition

• ImageNet에서 추출한 100개의 클래스, 클래스당 600장의 이미지 포함 2) fine-grained image classification
• 200개의 클래스, 총 11788 이미지 3) cross-domain adaptation
• mini-ImageNet으로 pretrain, CUB으로 fine-tuning 및 validation

4.2 Evaluation using the standard setting

테스팅 환경을 동일화하고 난 후에는 모델들간의 성능 차이가 크지 않음을 알 수 있다. 성능 차이가 존재하는 부분은 Augmentation의 적용 혹은 Meta Learning에서 구현 디테일 차이에 의해 비롯됐다고 한다.

4.3 Effect of increasing the network depth

4.4 Effect of domain differences between base and novel classes

4.5 Effect of further adaptation

5. Conclusion

Baseline++ 모델이 경쟁력이 있고, Baseline 모델이 더 깊은 특징 백본을 사용할 때 CUB와 mini-ImageNet 벤치마크 데이터셋에서 좋은 성능을 발휘함을 알 수 있었다. 또한, 현실적인 시나리오(기존 클래스와 새로운 클래스 간에 도메인 이동이 존재하는 경우)에서는 Baseline 모델이 평가된 모든 메타 학습 알고리즘보다 우수한 성과를 보임을 알 수 있었다. 코드 github

거대 데이터로 학습된 모델은 이전에는 존재하지 않았던 새로운 카테고리를 분류하고자 할 때, 대용량의 데이터로 학습해야 하는 경우가 존재한다. 적은 데이터로는 fine-tuning을 진행시키기 힘들고, 증강 기법은 overfitting의 위험성이 존재하기 때문이다. 이때 Few shot learning은 적은 라벨 데이터로 새로운 카테고리를 잘 학습하도록 한다. 현 meta learning 접근 방법으로는 initial condition, embedding, optimisation 전략을 선택함으로써 최적화하는 방법을 택하고 있다.

그러나 이러한 few-shot learning도 문제점이 존재한다. network weight을 업데이트하지 못하는 경우도 존재하고, 데이터가 불충분할 경우 gradient descending이 어려워지기 때문이다. 이에 대한 해결책으로 저자는 one-shot learning에 쓰일 수 있는, 효율적인 metric을 제공한다. 이러한 metric은 이미지들 사이에 관계를 비교할 수 있도록 transferable한, 즉 변할 수 있는 deep metric을 제공한다. 이전에 유클리디안 distance와 같은 fixed metric을 사용하는 것과는 다른 양상이다. 또한, deeper solution을 위해 inductive bias를 도입했다고 한다.(임베딩과 relation 모듈간의 여러 비선형적인 관계를 도입하는 것.) 여기서 inductive bias의 개념을 확실히 짚고 넘어갈 필요가 있어서 아래의 글을 첨부한다.

Inductive bias란 무엇일까?

Inductive bias에 대해 간단하게 설명하자면, 기존 모델의 오차에 bias와 variance가 동시에 등장하는 것을 알고 있을 것이다. 이때 bias란, 주어진 학습데이터에 잘못된 가정을 하여 발생한 오차에 해당한다. 근데bias가 낮다고 하여 무조건 좋은 모델은 아니다. 모델이 그럴듯하게 bias가 낮게 모델을 학습시켰다 하더라고, 주어진 데이터가 아닌 새로운 데이터에 대해서는 오차가 높게 발생할 수도 있기 때문이다. 이를 보완하기 위해 등장한 개념이 바로 inductive bias이다. 주어지지 않은 입력에 대해서도 출력을 잘 예측할 수 있도록, 일반화의 성능을 높일 수 있도록 만일의 상황에 대해 추가적인 가정을 두는 것이라고 생각하면 된다. (inductive bias는 보지 못한 데이터에 대해서는 귀납적 추론이 가능하도록 하는 알고리즘을 가지고 있는 가정의 집합) 이 가정들 중 relational 가정에 대해 설명을 하자면, 입력 요소와 출력 요소의 relation 관계가 있음을 가정하는 것이다. CNN을 예시를 들어보겠다. 기존의 fully connected layer는 각 입력 요소가 모든 출력요소와 관계가 있음을 가정하고 모두 연결을 시킨다. 이미지로 예시를 들면 하나의 픽셀 값 하나하나가 출력에 연관이 있다고 생각하는 것이다. 반면 CNN은 특정 출력을 내뱉기 위해서는 globally하게 모든 이미지 파트를 집중할 필요가 없고, 이미지의 일부만 보고 판단할 수 있다고 가정하여 locality를 반영한 모델이다. 즉 입력들간의 관계가 존재하고, 이러한 관계를 반영할 수 있을 때 좋은 출력이 나온다는 것이다. 이때 이 locality 가정을 relational 가정이라고 생각하면 된다.

저자는 최종적으로 two branch relation network를 제안하였고, 이러한 network는 query images와 few-shot labeled sample images의 비교를 통해 학습을 진행한다. 자세한 과정은 아래와 같다. 1) embedding module이 query과 학습 이미지의 representation을 생성한다. 2) 이러한 임베딩은 카테고리 소속 여부를 판단하는 relation module을 통해 비교된다.

2. Related work

기존의 few-shot learning 기법은 적은 데이터를 fine tuning하면 생기는 overfitting 문제를 피하면서 meta learning & learning to learn 전략을 통해 transferrable knowledge를 효과적으로 추출한다. 뒤에서는 이러한 기법에 대해 소개하도록 하겠다.

2-1. Learning to Fine-Tune

MAML approach은 fine-tuning에 적절한 initial condition을 배우는 것을 목표로 한다. (sparse data가 주어졌음에도, 적은 gradient 업데이트 단계를 통해 적절한 weight configuration을 찾는 등) 많은 task training set에서 다양한 target problem이 샘플링 되고, base model은 각각을 해결하기 위해 fine-tuning을 진행한다. 그리고 few-shot optimisation approach 또한 optimizer와 좋은 초기 condition을 학습하려한다. 다만 이러한 접근법 모두 target problem에 fine tuning을 진행해야한다는 문제점이 존재한다. 반면 저자의 접근법은 target problem에 모델 업데이트가 필요없는, feed foward 방식을 통해 해결하려고 한다.

2-2. RNN Memory Based

다른 방법으로는 RNN with memory 접근법이 존재한다. 새로운 데이터를 memory에 저장된 정보와 비교를 함으로써 분류하는 방법에 해당한다. 다만 이러한 접근법도 데이터를 잊지 않고, 과거 모든 정보를 저장하려고 한다는 문제점이 존재한다. 저자의 접근은 이러한 복잡성을 피하기 위해 간단한 feed-foward CNN을 제공한다.

2-3. Embedding and Metric Learning Approaches (보충 필요)

위의 방법들은 학습 시 약간의 복잡성을 수반한다. 다른 방법으로는, query와 이미지를 feed forward 방법으로 분류하는, projection function을 학습시키는 것을 목표로 한다. 하나의 방법은 sample set 관점에서 feed foward classifer의 가중치를 parameterise하는 것이다. metric based 접근법은 projection function을 학습시킨다. 이를 통해 이미지들이 임베딩 될 때, 이미지들은 쉽게 인식되어질 수 있따. 이때 meta-learned transferrable knowledge는 projection function이고, target problem은 simple feed-forward computation이다.

2-4. Zero-shot Learning

few-shot learning과 다르게 zero-shot learning은 몇 샘플 이미지 대신 카테고리의 설명을 입력으로 사용하여 학습을 진행한다. ZSL을 적용시 이미지와 카테고리 임베딩을 정렬하고, 이미지와 카테고리 임베딩 쌍이 일치하는지 예측하여 인식하는 방법과 관련이 있다. 이전 방법과 유사하게 이미지와 카테고리 임베딩을 결합한 후 fixed metric이나 linear classifier를 적용한다. 반면, 저자는 non-linear metric을 사용한다는 점에서 차이점이 존재한다.

3. Methodology

3-1. problem definition

본격적으로 문제 정의를 해보겠다. 총 세가지의 데이터셋을 우선 만들어야 한다. 1) training set 2) support set 3) testing set이다. 이때 support set과 test set은 동일한 label space를 공유하고, training set은 이러한 label space와는 동떨어진 별개의 label space를 지니고 있다. 그리고 각 support set이 c개의 classes에 대해 k개의 label 데이터를 지니고 있다면 이것을 C-way K-shot 문제라고 부른다. 만약 support set를 지니고 있다면, 우리는 test set의 입력데이터을 분류할 수 있는 classifer를 학습시킬 수 있다. 다만, support set에 라벨 데이터가 부족하다면, 이 분류기의 성능은 만족스럽지 못할 것이다. 그래서 저자는 meta learning을 학습데이터에도 적용하려 한다.

학습데이터를 효과적으로 사용하는 방법은, 바로 episode based learning을 통해 few shot learning의 방법을 모방하는 것이다. 각 학습 iteration에서, episode는 randomly하게 C개의 classes를 고르고, 각 C개의 클래스에 대해 K개의 label sample을 뽑는다. 이를 sample set이라 칭하겠다. 그리고 이러한 C 클래스의 sample에서 남은 부분을 Query set이라 칭하고, 각각을 아래와 같이 표기를 하겠다. $S={(x_i,y_i)}^m_{i=1} \quad ,(m=K*C)$ $Q={(x_j,y_j)}^n_{j=1}$ 이러한 sample,query set은 test time에 support, test set처럼 작용한다. 이렇게 학습된 모델은 추후 support set을 통해서 fine-tuning되어질 수 있다. 저자는 이러한 episode 방식의 학습 전략을 선택하였다. 논문에서는 one-shot, five-shot, zero-shot 각각을 테스팅하였다.

3-2. model

One-Shot

Relational Network는 총 2가지 모듈로 구성되어져 있다. 첫번째로는 embedding module $f_\phi$, 두번째로는 relation module $g_\phi$로 구성되어져 있다. Query set $x_i$의 sample과 sample set의 sample$x_j$은 임베딩 모듈인 $f_\phi$에 활용되게 되고, 이는 $f_\phi(x_i)$와 $f_\phi(x_j)$를 생성한다. 그리고 이러한 feature map은 operator $C(f_\phi(x_i),f_\phi(x_j))$와 결합된다. 이때, $C(.,.)$은 feature map의 concatenation에 해당이 된다. 이렇게 결합된 feature map은 relation module $g_\phi$에 들어가게 된다. 이는 $x_i$와 $x_j$ 간의 유사성을 0-1사이 숫자로 표현한다. 이를 relation score라고 한다. 그러므로, C-way one shot setting에서는, 하나의 쿼리 이미지에 대해 training sample set인 $x_i$간의 관계를 구하여 C개의 relation score인 r_{i,j}를 생성한다.

$r_{i,j}=g_\phi(C(f_\phi(x_i),f_\phi(x_j)))\quad, i=1,2,...C$

k-shot

• 각 클래스에 대해 참고하는 이미지가 k개일 때 만약 K>1인 경우, K-shot problem에서는 각 샘플들의 embedding module의 ouputs를 element-wise sum을 구한다. 이 feature map을 query set feature map과 결합한다. one-shot과 동일하게 C개의 score가 등장한다.

Objective function

우리는 모델을 학습시키기 위해 (relation score를 regressing 하기 위해) MSE를 사용한다. matched pair에 관해서는 1, mismatched pair에 한해서는 0으로 예측하려 한다.

$\phi, \Phi \leftarrow argmin \sum^m_{i=1}\sum^n_{j=1}(r_{i,j}-1(y_i==y_j))^2$

MSE를 고른 이유는, 분류 문제임에도 relation-score를 예측해야하는 회귀문제기 때문에 이를 사용했다.

3-3. zero-shot learning

기존에는 support set에서 k 개의 sample 뽑아냈다면, zero shot에서는 대신 각 클래스에 대한 semantic class embedding vector인 $v_c$를 활용한다. 즉 이미지 대신 다른 modality인 $v_c$를 사용한다는 말이다. 대신 $v_c$를 입력으로 넣을 $f_{\phi_2}$r가 추가로 필요로 되어진다. 그 다음 relation module에 입력으로 넣는 과정 모두 동일한다. objective function 또한 동일하다. $r_{i,j}=g_\phi(C(f_{\phi 1}(v_c),f_{\phi 2}(x_j)))\quad, i=1,2,...C$

3-4. Network Architecture

Few shot learning Network 각각의 convolutional block은 64개, 3 x 3 filter를 사용하였고, 이후 batch normalization과 relu를 거쳤다. 첫 두개 block은 2 x 2 max-pooling later를 사용하였는데 이는 output을 relation module의 convolution layer에 입력하기 위해서이다. relation module은 2개의 convolutional block과 2개의 fully connected layer를 사용하였다.

Zero shot learning Network 위 그림에서, DNN subnet은 ImageNet의 pretrained 된 network이다.

4. Experiments

Ominglot과 miniImageNet 각각에 relation net을 적용하였고, 결과는 아래와 같다.

4-1. Few-shot Recognition

Adam optimizer를 사용하였고, 100,000 episodes를 사용했다.

1) Ominglot: Dataset, training, result

Dataset 50개 종류의 알파벳을 묘사한 1623개의 Characters를 지니고 있고, 각 class 마다 총 20개의 sample을 지니고 있는 데이터이다. 이를 회전 등과 같은 증강 기법을 통해 데이터를 변형시키고, 1200개는 training, 463개는 testing에 할당하였다.

Training For each of the C sampled classes in each training episode,

1) 5-way 1-shot: 19 query images → 19(query image) x 5(5개의 random class) + 1(1개의 sample image) x 5 = 100 per one episode 2) 5-way 5-shot: 15 query images 3) 20-way 1-shot: 10 query images 4) 20-way 5-shot: 5 query images

Result Testing set에서 1000개의 random episode를 만들고, 각 episode의 정확도를 평균으로 하여 성능을 산출하였다. 5-shot 실험에서는, 각 클래스별로 5개의 query image를 뽑았고 (즉, 새로운 하나의 클래스를 판단하는데 고작 5개의 이미지만을 활용한다는 뜻이다. 근데 이 이미지들로 모델의 weight가 바뀌는 것은 아닌 듯하다. fine tuning과는 다른 개념?) 그 결과 5-way 5-shot를 제외하고는 모두 더 높은 정확도를 보였다고 한다.

2) miniImageNet: Dataset, training, result

Dataset 100개의 클래스에 대해 60,000개의 이미지를 지니고 있고, 64, 16, 20개의 class를 각각 train, validation, testing에 할당했다.

Training 5-way 1-shot: 15 query images → 15(query image) x 5(5개의 random class) + 1(1개의 sample image) x 5 = 80 per one episode 5-way 5-shot: 10 query images

Result test set으로부터 600개의 episode를 형성하였고, 각 클래스별로 15개의 query 이미지를 형성하였다. 5-way 1-shot에서 굉장히 좋은 성능을 내었지만, 5-way 5-shot에서는 다른 모델인 prototypical network의 성능이 더 좋다고 나왔다. 다만 확인해본 결과, 해당 모델은 30-way 15 queries로 학습되어야지만 이런 결과를 낼 수 있다고 한다. 동일한 환경인 5-way 5-shot으로 학습시키면 relation net의 결과가 더 좋다고 한다.

4-2) Zero-shot Recogntion

imageNet 1K 데이터를 사용했고, 해당 이미지들의 임베딩 데이터를 vector sample data로 사용하여 학습한 결과가 위와 같다.

5. why does relation Network work?

5-1. relationship to existing models

(Distance metric learning) 기존의 few-shot 논문에서는 주로 fixed metric인 유클리디안 혹은 코사인 distance를 사용했다. 다만 이러한 경우, 모든 학습은 feature map 생성 단계에서만 발생하고, 이미지들간의 관계를 따로 학습하지는 않는다. 이미 관계를 나타내는 metric이 고정되어있기 때문이다. (Conventional metric learning approaches) 해당 접근법은 마할라노비스 metric을 사용하지만, feature representation이 고정되어져 있다. 해당 논문은, 고정된 metric을 relation module로 대체하여 사용했다는 점, 그리고 feature representation을 생성하는 부분도 학습하도록 구성했다는 점에서 해당 논문의 의의를 찾아볼 수 있겠다. 이를 통해, 인간이 정의한 metric이 아닌 실제 데이터의 유사도를 나타내는 true metric을 배울 수 있다. fixed metric은 eleent-wise하고 embedding 이후 linear separability를 가정한다.

[참고] Fixed metrics like assume that features are solely compared element-wise, and the most related assumes linear separability after the embedding. These are thus critically dependent on the efficacy of the learned embedding network, and hence limited by the extent to which the embedding networks generate inadequately discriminative representations. In contrast, by deep learning a nonlinear similarity metric jointly with the embedding, Relation Network can better identify matching/mismatching pairs.

5-2. Visualisation

[논문에서] To illustrate the previous point about adequacy of learned input embeddings, we show a synthetic example where existing approaches definitely fail and our Relation Network can succeed due to using a deep relation module. Assuming 2D query and sample input embeddings to a relation module, Fig. 4(a) shows the space of 2D sample inputs for a fixed 2D query input. Each sample input (pixel) is colored according to whether it matches the fixed query or not. This represents a case where the output of the embedding modules is not discriminative enough for trivial (Euclidean NN) comparison between query and sample set. In Fig. 4(c) we attempt to learn matching via a Mahalanobis metric learning relation module, and we can see the result is inadequate. In Fig. 4(d) we learn a further 2-hidden layer MLP embedding of query and sample inputs as well as the subsequent Mahalanobis metric, which is also not adequate. Only by learning the full deep relation module for similarity can we solve this problem in Fig. 4(b).

실제로 임베딩을 잘 학습했는지 확인하기 위해 저자는 embedding을 직접 시각화를 진행하였다. 2d query와 sample이 존재한다고 가정하고, 이를 학습시켜보았다고 가정하자. 위의 (a)는 2d sample input의 space를 실제로 묘사한 결과이다. 각각의 샘플은 fixed query와 매치되었는지 아닌지로 coloring이 되어져 있다. 그림에서 보이듯이 relation net이 가장 잘 묘사한 것을 발견할 수 있다.

실제 문제에서, embedding을 비교하는 문제는 그렇게 어렵진 않지만, 여전히 도전적인 과제이다. 저자는 2개의 ominglot query image embedding을 matching하였고 위 그림이 그 결과다. 시각화한 결과, fixed metric을 사용한 경우 match하는 쿼리와 mismatch하는 쿼리가 모두 한 곳에 모여져 있다. relataion net내에서의 embedding은 그림의 오른쪽 표와 같이 match와 mismatch가 명확하게 구분되어져 있는 것을 볼 수 있다.

[논문에서] In a real problem the difficulty of comparing embeddings may not be this extreme, but it can still be challenging. We qualitatively illustrate the challenge of matching two example Omniglot query images (embeddings projected to 2D, Figure 5(left)) by showing an analogous plot of real sample images colored by match (cyan) or mismatch (magenta) to two example queries (yellow). Under standard assumptions the cyan matching samples should be nearest neighbours to the yellow query image with some metric (Euclidean, Cosine, Mahalanobis). But we can see that the match relation is more complex than this. In Figure 5(right), we instead plot the same two example queries in terms of a 2D PCA representation of each query-sample pair, as represented by the relation module’s penultimate layer. We can see that the relation network has mapped the data into a space where the (mis)matched pairs are linearly separable.

6. Conclusion

relation network는 임베딩과 쿼리셋과 sample set간의 비선형적인 distance metric을 학습한다. 이러한 접근법은 기존의 방법들보다 간단하고 효율적이고, sota 성능을 이끌어냈다는 점에서 의미를 찾을 수 있다.

7. Relation Net Code

FSL github

해당 논문을 읽어보면 매 매소드마다 다양성을 부여하면서 실험을 하고, 정당성을 부여하는데, 추후 연구를 진행할 때 무지성으로 그냥(?)이라는 것은 없다는 것을 깨달았다(...)

1. Introduction

지금껏 수많은 visual representation 연구가 진행되었었다. 대표적으로 generative approach, 그리고 discriminative approaches가 존재한다. 전자의 경우는 pixel-level에서 이미지를 생성해내면서 패턴을 배운다는 의미인데, 픽셀레벨이라는 것자체가 computaitonal cost가 상당히 많이 들어가고, 또한 generalized한 패턴을 배우는게 중요한 representation learning 분야에서는 그렇게 좋은 선택이 아닐수도 있다. Discriminative approach에서는 지도학습과 유사한 목적함수를 지니지만, 라벨링되지 않은 데이터로부터 라벨(pretest)과 input을 생성하여 학습하는 기법이다. 이러한 기법은 pretest task를 어떻게 설정하냐에 따라 성능이 달라지고, 이는 generality를 제한시킬 수 있다. 저자는 simCLR라는 representation 기법을 제안하는데, 이는 더 쉽고, 특별한 구조와 memory bank를 요구하지 않는다는 점에서 장점이 존재한다.

2. Method

2-1. The Contrastive learning framework

simCLR는 contrastive loss를 통해 x라는 데이터와 x를 augmented 이미지(similar pair)사이의 agreement를 최대함으로써 representation을 학습한다. 아래의 그림을 참고하며 설명해보겠다. 1) 우선 stochastic data augmentation을 통해 $$x$$라는 데이터를 각각 $$x_i$$, $$x_j$$으로 transform한다. 이 두 데이터를 positive pair, 즉 유사한 데이터 페어라고 생각하면 된다. 데이터 변형 시에 적용되는 transformation으로는 random cropping, color distortions, gaussian blur등 여러가지 방법들이 있다. 이때 augmentaion의 조합에 따라 성능이 다르게 나오는데, 실험 결과 crop + color distortion 조합이 가장 좋았다고 한다. 개인적으로 이렇게 성능이 나온 이유로는, 아무래도 crop하고 color값을 바꾸는 augmentation이 상대적인 픽셀 변화가 크므로 학습이 다양성이 커져서 더더욱 학습을 잘하는 것이 아닐까라고 생각을 하였다. (회전과 같은 경우는 피쳐의 위치만 달라진 것이기 때문에)

2) 𝑓(.)가 augmented된 데이터에서 representation vector를 뽑아낸다. $$h_i=f(x_i)=ResNet(x_i)$$ base encoder f(.)로써 다양한 architecture를 선택할 수 있다. 저자는 가장 많이 사용되는 ResNet을 기본 인코더로 채택하였다. 위 수식에서 h_i는 average pooling layer 이후의 결과에 해당된다.

*3) Projection head g(.)가 representation을 contrastive loss 값을 계산할 수 있는 공간으로 맵핑을 시킨다. *

$$z_i=g(h_i)=W^{(2)}\sigma(W^{(1)}h_i)$$ 저자는 MLP를 사용하여 representation을 한번 더 매핑한다. 이때, contrastive loss값을 $$z_i$$보다 이전 단계에서 구해진 representation인 $$h_i$$에서 구하는 것이 효과적임을 찾았다고 한다.

4) contrastive loss를 계산하고 f를 업데이트를 한다. 추후 downstream task에서는 f(.)만을 사용한다. contrastive loss는 $$x_i$$가 주어졌다고 가정할 때, $${x_k}_{k!=i}$$로부터 positive pair인 $$x_j$$를 인식하도록 계산이 되어진다.

위의 과정을 차례대로 설명하자면, 미니 배치안에 n개의 이미지들을 각각 augmentation을 진행하고, 이미지 $$x_i$$에서 파생된 $$x_j$$는 positive pair, 나머지 2(N-1)개의 미니배치 안 이미지를 negative pair라고 가정을 하고 위와 같은 학습 방법을 진행한다. 아래는 contrastive loss의 수식에 해당한다.

위의 수식에서 similarity $$sim(u,v)$$는 cosine similartiy로 계산되었다. softmax 수식과 유사한 형식을 띄는게 특징이다.

위의 그림은 SimCLR 의 간략한 pseudo 코드이다.

2-2. Training with Large Batch Size

Memory bank(MoCo 논문에서 등장한다.)는 모든 데이터의 representation을 memory bank에 담아 랜덤하게 샘플링하여 dictionary를 구성하는 방식이다. 다만, 예전에 업데이트된 encoder로부터 추출된 것이므로 일관성이 매우 떨어진다는 단점이 있다.

저자는 모델 구조를 심플하게 만들기 위해 메모리 뱅크를 사용하지 않았다. 대신, negative pair의 개수를 늘려 효율적으로 학습하기 위해, batch size를 256 - 8192까지 다양하고 훨씬 더 큰 범위로 만들었다. 다만 큰 범위의 배치사이즈로 학스비을 하는 것은 매우 불안정적이고 컴퓨팅적으로 비용이 많이 든다는 단점이 있어, 저자는 이를 개선하기 위해 linear learning rate를 지닌 표준 SGD, momentum optimizer보다 LARS optimizer를 사용하였다. (어떤 차이점이 있는지는 다른 논문을 통해 확인해봐야할 듯.) TPU를 사용했고, 코어를 배치 사이즈에 따라 32-128개 사이로 설정할 수 있도록 다양성을 주었다.

Global BN 표준적인 ResNet은 batch normalization을 사용한다. data parallelism을 활용하여 distributed training을 진행하면, 디바이스별 배치들의 평균과 분산을 사용하기 때문에 local information leakage에 빠질 수 있다. (이렇게 되면 representation 성능을 높이지 않은 채 예측 정확도만 올리려고 하게 될 수 있다.) 이를 해결하기 위해 전체 디바이스들의 BN mean과 분산을 사용하여 학습을 진행하였다.

3. Data Augmentation for Contrastive Representation learning

3-1. Composition of data augmentation operations is curical for learning good representations

Data augmentation에 따른 성능을 측정하기 위해,

• spatial/geometric transformation: cropping and resizing, rotaton, cutout
• apperance transformation: color distortion, gaussian blur, sobel filtering

등을 적절히 조합하여 사용하였고, 위의 그림은 그 조합들에 대한 각각의 모델 성능을 나타낸다. 그 결과 random cropping + color distortion의 조합이 가장 큰 성능을 보여주었다. 이때, 랜덤하게 데이터를 cropping하는 것은 위험하다. 대부분의 이미지 패치들이 비슷한 색깔 분포를 공유하기 때문이다.

3-2. Contrastive learning needs stronger data augmentation than supervised learning

color augmentation의 중요성을 말하기 앞서, 해당 변화의 힘을 측정하였다. color augmentation이 더 강할 수록 더욱더 성능이 향상되는 것을 발견하였다. 그렇지만 supervised learning에서는 이러한 데이터 augmentation이 제 힘을 발휘하지 못하는 경우가 많다.

4. Architecture for Encoder and Head

4-1. Unsupervised contrastive learning benefits from bigger models

위의 그림에서 보이듯이, 당연하게도 모델의 depth와 width를 높이면 성능이 향상하게 된다. supervised learning에서도 이와 유사하다. 저자는 supervised model과 unsupervised model로 학습된 linear classifier간의 갭이 모델 사이즈가 커질수록 줄어든다는 것을 발견했다. 즉 unsupervised learning을 사용할거면 큰 모델을 사용하는 것이 좋다라고 생각하면 된다.

4-2. A nonlinear projection head improves the representation quality of the layer before it

저자는 이후 projection head인 g(h)의 종류와 차원을 달리하며 성능을 측정하였다. 그림에서 보이듯, 차원과는 대부분 상관없이 non-linear한 projection head가 성능이 좋다는 것을 찾을 수 있다. 또한, 최적의 representation은 projection head 전 layer에서 뽑힌 representation이 제일 최적이다. 이에 대한 이유로, contrastive loss로 인해 발생하는 정보의 손실을 그 이유로 뽑았다. 구체적으로 설명해보자면, $$z=g(h)$$는 data transformation에 따라 다르게 표현이 된다. 그래서, g는 downstream task에 중요하게 쓰일 색깔과 같은 정보를 없앨 가능성이 크다. g를 활용함으로써, h에는 오히려 더. 유용한 정보들이 남게 된다. h에서 이러한 정보를 대신 없애주기 때문이다. 이러한 가정을 확인하기 위해 h 혹은 g(h)만을 활용하여 예측 task를 해결하는 실험을 진행하였고, 그 결과 h가 더 유용한 정보를 포함하고 있음을 위 표에서 확인할 수 있다.

5. Loss functions and Batch Size

5-1. Normalized cross entropy loss with adjustable temperature works better than alternatives

해당 모델에서 사용된 NT-Xent loss를 다른 loss function 값과 비교하여 실험을 진행하였다. 실험에 대한 결과는 위와 같다. 저자는 gradient의 추이를 보며 1) temperature에 따른 l2 noramlization(코사인 유사도)이 다양한 예제들에 효과적으로 가중치를 부여한다는 것, 2) 그리고 적절한 temperature값은 학습에 도움이 된다는 점, 3) cross entropy와 다르게 다른 목적함수들은 상대적 hardness를 이용하여 negative pair에 효과적으로 가중치를 부여한다는 점을 알아내었다.

5-2. Contrastive learning benefits from larger batch sizes and longer training

constrastive learning을 사용 시에는 더 큰 batch size와 더 큰 epoch를 지닐 때 성능이 올라감을 위에서 확인할 수 있다.

6. Comparision with SoTA

도표를 참고하길 바란다.

코딩테스트 관련 알고리즘은 아래와 같다. 주로 이 아래의 알고리즘들 아래에서 문제가 출제된다 생각하고 확실하게 학습하고 지나가야 한다.

• DFS/BFS
• 이진 탐색
• DP (Dynamic Programming)
• 최단 경로: 다익스트라/플루이드 워셜
• 유니온 파인드/크루스칼/부분합/투 포인터

다이나믹 프로그래밍

다이나믹 프로그래밍은 규칙을 찾아내는 것에 집중해야 한다. 그러기 위해서는 특정 몇개의 입력값에 대한 출력값이 도출되는 과정들을 하나하나씩 적어보면서 규칙을 찾아낼 필요가 있다.

백준 9251번

문제 링크

LCS 참고: 최장공통문자열과 최장공통부분수열(문자열간 공백 존재 가능)

LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

문자열의 길이가 1000이라 가정하고 모든 부분 문자열 조합을 만들어본다면, ${1000\choose 1} + {1000\choose 2} + {1000\choose 3} + .. {1000\choose 1000} = 2^{1000}$의 문자열 경우의 수가 나온다. 입력된 두 문자열로 만들 수 있는 부분 문자열의 조합을 모두 생각해낸 뒤, 겹치는 것 주 길이가 가장 긴 공통 부분 문자열을 뽑아내는 방법도 존재하겠지만, 상당히 비효율적으로 보인다. 우선 조합을 만들어내는 시간 복잡도 또한 굉장히 높을 것으로 예상된다. 그렇다면 어떻게 효율적으로 해결할 수 있을까?

이를 DP를 통해 해결해나갈 수 있다. 해당 파트는 설명이 길어 꼭 참고자료를 확인하길 바란다.

위의 정답 형태를 관찰하면 알겠지만, 마치 점화식의 꼴, 즉 이전의 정답값을 활용해 다음의 정답값을 도출해내는 것을 발견할 수 있다. 다만, 점화식을 세우기 위해서는 총 2가지 조건을 세워야 한다.

*1) 초기값은 무엇인지 (= 탈출 조건은 무엇인지) 2) 점화식은 무엇인지 *

이때 초기값으로는 0을 입력한다. 즉, 이 문자열 이전으로 최장의 공통부분수열이 없었음을 의미한다. 이후의 점화식은 다음과 같다.

1. 문자열A, 문자열B의 한글자씩 비교해본다.
2. 두 문자가 다르다면 LCS[i - 1][j]와 LCS[i][j - 1] 중에 큰값을 표시한다.
3. 두 문자가 같다면 LCS[i - 1][j - 1] 값을 찾아 +1 한다.
4. 위 과정을 반복한다.

코드 풀이

항상 생각하자. 중요한 것은 문제를 어떻게 해결할 것인지에 대한 논리이고, 코드는 그저 이를 옮겨적는 언어일 뿐이다!

import sys

string_a = ' ' + sys.stdin.readline().rstrip()
string_b = ' ' + sys.stdin.readline().rstrip()
dp = [[0] * len(string_b) for _ in range(len(string_a))]

for i in range(1, len(string_a)):
    for j in range(1, len(string_b)):
        if string_a[i] == string_b[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

print(dp[-1][-1])

Metric learning이란 objects들간의 distance function을 배우는 학습 방법론이다. 이때, distance의 정의는 이미지 픽셀 값들의 유사도가 될 수도 있고 각 상황마다 다르게 정의될 가능성이 있다.

추가적으로 언급해보자면, 0과 1 과 같이 직접적인 label이 아닌 간접적인 label이라고 할 수 있는 distance를 가지고 학습을 진행하는 방법론이다. 이러한 이유로 우리는 metric learning을 weak-supervised learning이라 일컫는다. 이러한 metric learning에 어떠한 종류가 있는지를 지금부터 살펴보겠다.

2. learning to rank

해당 task의 데이터로는 아이템들의 list와 물건들의 상대적인 순위인 partial order(전체 순위가 아닌)가 주어진다. 해당 모델이 하고자 하는 바는 아이템들의 순위를 학습 데이터에 존재하는 순위를 반영하여 최대한 가깝게 출력해내는 것이다. 실제** document retrieval(text query가 주어지면 웹페이지들의 순위를 매기기), **collaborative filtering, online advertising (유저의 정보를 바탕으로 해당 유저가 특정 광고를 클릭할 확률을 예측하고, 각 회사들이 해당 공간에 광고를 하겠다고 배팅한 가격을 합산하여 광고를 띄어주는 task)분야에서 활용되곤 한다.

2-1. problem formulation

metric learning 분야에서의 문제를 아래와 같이 정의내릴 수 있다.

1) point wise

각 (query - item) pair에 score가 붙여진 데이터를 주고, score를 예측한다. 이는 일반적인 regression이나 classification task라 생각하여 해결 가능한다.

2) pair wise

각 query에 대해서 순위가 붙여진 두 개의 쌍의 데이터를 준다. 모델은 주어진 query를 기반으로 두 개의 아이템 임배딩이 뽑아내고 이렇게 도출된 임배딩을 이용하여 우선순위를 예측한다. objective는 학습데이터 내의 두 아이템 선호 관계가 최대한 보존되도록 설계되어야 한다. 해당 순위를 학습하는 과정에서 모델은 아이템들에 대한 임베딩을 학습하고, 이러한 임베딩이 generalized 되기 때문에 unseen 데이터에서도 효과적으로 순위를 예측하는데 도움이 된다.

3) list wise

후보를 이제 두 개가 아닌 여러 개의 아이템의 순서를 맞추는 것이다. 그냥 계산하면 모든 permutation에 대해, 즉 모든 아이템 조합에 대해 우선순위를 모두 구해야 하기 때문에 계산량이 기하급수적으로 늘어날 수 밖에 없다. 이에 대한 접근법으로 pairwise의 기법을 간접적으로 사용한다.

2-2. evaluation metrics

• Normalized Discounted Cumulative Gain (NDCG) $$DCG_p=\sum_{i=1}^{p} \frac{rel_i}{\log_{2}(i+1)}$$ (relevance가 숫자일때) $$DCG_p=\sum_{i=1}^{p} \frac{2^{rel_i}-1}{\log_{2}(i+1)}$$ (relavance가 실수값일때) 모델이 각 페이지를 1 - p위까지 순서를 매기면, 1위에 있는 것이 정말로 relevance(예를 들어, 실제 유저가 이 페이지를 클릭하였는지)가 있는가를 의미한다. rel이 1이면 실제 클릭을 한 것이고, 아니면 클릭을 하지 않은 것이다. 이때 분모의 i는 예측한 순위인데, 즉 예측한 순위가 높을수록 relevance값이 더 크게 측정되어 반영된다는 말이다. NDCG는, 만약 특정 세션에서 클릭된 페이지가 다른 경우보다 적을 경우 애초에 구해지는 DCG값이 작을 수 밖에 없기 때문에 이를 보완하고자 DCG에 각 세션별 클릭된 페이지 수를 나누어 구하는 metric 값이다.

3. metric learning

3-1. triplet loss

참고문헌

training 데이터가 anchor, positive, negative 총 3가지로 나뉘어질 때, anchor-postive 간의 거리와 anchor-negative간의 거리를 이용하여 학습하는 방법이다. 이때 anchor와 positive간의 거리는 가깝게, negative간의 거리는 멀게끔 학습되어지는 것이 일반적이다.

$$L=\sum_{i}^{N}[\Vert f(x_i^a)-f(x_i^p)\Vert^2-\Vert f(x_i^a)-f(x_i^n)\Vert^2+\alpha]_+$$ (hinge loss처럼 양수일 때만 제 loss 값을 갖고 음수면 0으로 바뀐다. 만약 anchor와 postive 간의 거리가 negative간의 거리보다 짧을 경우, 잘 예측했음에도 불구하고 음수가 나오기 때문에 이를 0으로 설정하기 위한 방법이다. 음수 loss로 backprop을 하는 경우 잘 예측했음에도 gradient가 움직이는 경우가 존재하기 때문에, loss는 양수여야 한다.)

$$\alpha$$는 'margin'의 개념으로, anchor와 positive가 가깝게 설정되더라도 이정도는 더 좁혀야한다는 추가적인 조건을 주기 위해 넣은 요소이다.

아까와 같은 추천시스템의 task에서, positive와 anchor는 유저가 선택한 아이템들에서 선택되고, negative는 유저가 선택하지 않은 임의의 아이템들에서 선택이 된다. 그렇지만 이런 경우 예측이 너무 쉬워지기 때문에 더 예측하기 어려운 pair를 선택할 필요가 존재한다.

이를 위해 negative pair를 잘 선택하기 위한 방법들이 고안되었다. online negative mining이 그 예시이다. hard negative를 뽑아내기 위해, 이를 전체 데이터셋에서가 아닌 mini batch에서 뽑아내는 방법을 선택했다. 일단 mini batch에서 데이터를 뽑아냈기 때문에 컴퓨팅적으로 효율적이고, 또한 batch의 하나의 positive 데이터가 batch 내의 모든 negative 데이터와 멀어지도록 학습이 되어지기 때문에 성능이 더 높아질 수 밖에 없다. 그래서 batch 사이즈가 더 커야 한다는 요구사항이 존재한다.

이후에는 semi hard negative mining 개념도 등장하였다. 우선 개념은 아래와 같다.

• Easy negatives: d(a,p)+margin < d(a,n) 이미 충분히 거리가 먼 negative의 경우

• Hard negatives: d(a,n) < d(a,p) 거리가 positive보다 가까워 명백하게 위해되는 경우

• Semi-hard triplets: d(a,p) < d(a,n) < d(a,p) + margin 거리가 애매하게 먼 경우

만일 그냥 hard negative만을 뽑게 되는 경우 문제가 발생할 수 있다. $$L=\sum_{i}^{N}[\Vert f(x_i^a)-f(x_i^p)\Vert^2-\Vert f(x_i^a)-f(x_i^n)\Vert^2+\alpha]_+$$에서 모델의 이상적인 학습방향은 앵커와 negative간의 거리를 멀게 만드는 것이지만, alpha가 굉장히 작은 값이기 때문에 모델이 그냥 f(x)에 대한 결과값이 모두 0으로 출력되게끔 할 수 있다. 이러한 경우 학습이 제대로 이뤄지지 않는다. 그래서, 현재의 anchor - negative distance가 anchor - positive distance를 아슬아슬하게 넘는 negative를 선택하여 해당 경우들을 잘 학습시키는 것이 중요하다. 추가적으로 alpha값들을 잘 설정하는 것도 중요하다.

실제 이를 활용하는 분야로는 FaceNet, CDML 등이 존재한다. 그 중 collaborative deep metric learning에 대해 살펴보자.

프레임과 오디오의 피쳐를 뽑아 anchor와 negative는 멀도록, anchor와 positive는 가깝도록 임베딩 모델 학습을 진행한다. 이때 특정 비디오를 보고 선택한 비디오들을 연관이 있다고 생각하여 postive pair라 여기고 인근 노드에 배치한다. 아닌 것들은 거리가 먼 노드에 배치함으로써 비디오 연결 관계를 그래프 형식으로 빌드하고 이를 통해 각 데이터셋을 마련한다. 이를 통해 비디오 임베딩을 뽑아내고 Nearest neighbor search, user modeling, classifier 등 다양한 곳에서 활용 가능하다. 한계점은 negative pair를 효과적으로 뽑아내기 위해서 batch size를 크게 잡아야 한다는 점이 있다.

3-2. Contrastive learning

0) pairwise loss function

Input examples pair $$(x_1,x_2)$$에 대해, 두 데이터가 유사할 때 ground truth distance y는 0, 유사하지 않을 때는 1로 생각한다. 어떤 대상이 유사할 땐 가깝게, 유사하지 않은 대상은 멀게 배치되게끔 학습시키기 위해 아래와 같은 loss값이 설계되었다.

$$\mathcal{L}(W)=\sum_{i=1}^{p}L(W,(Y,X_1,X_2)^i)$$ 이때, $$L(W,(Y,X_1,X_2)^i)=(1-Y)L_s(D^i_W)+YL_D(D^i_W)$$이다.

해당 loss값의 예시는 아래와 같다. 실제 유사한 데이터인 경우(Y=0)는 $$\frac{1}{2}(Dw)^2$$, 반대의 경우는 $$\frac{1}{2}{max(0,m-D_w)}^2$$을 loss값으로 채택하는 것이다.

$$L(W,(Y,X_1,X_2)^i)=(1-Y)\frac{1}{2}(Dw)^2+Y\frac{1}{2}{max(0,m-D_w)}^2$$

다만 이러한 loss function에는 어떠한 문제가 존재한다.

• normalization problem 우리는 classification task에서 어떠한 값을 예측을 할 때, 주로 softmax 함수를 이용하곤 한다. $$Softmax function = p(y=c_i|x) = \frac{e^{s_i}}{e^{s_1}+e^{s_2}+... e^{s_n}}$$ 이때, softmax값으로 하나 클래스에 대한 확률을 계산하려고 할때, 모든 클래스에 대한 score 점수도 모두 구해야한다. 즉, 분류할 수 있는 클래스의 수가 많을수록 더 많은 계산이 요구된다는 것이다. 또한 매번 특정 클래스를 도출해내기 위한 모든 파라미터들을 업데이트를, 그리고 이 과정을 모든 클래스에 대해 적용한다는 것이다.

그래서, 어느정도 학습이 완료된 후에는 negative를 다 쓰지말고, softmax 분모의 $${e^{s_1}+e^{s_2}+... e^{s_n}}$$에서 일부만 랜덤으로 선택하여 쓰자는 아이디어가 등장하였다. 이를 negative sampling이라고 한다.

1) SimCLR

논문

simCLR의 구조는 아래와 같다. Data Augmentation을 통해 하나의 이미지를 여러 유사한 이미지로 만든 후 인코더에 집어넣는다. 이렇게 만들어진 1차적인 임베딩을 projection을 시켜 2차 임베딩을 뽑는다. 같은 이미지로부터 나온 2차 임베딩들은 유사하도록 학습이 된다(positive pair). 그 이외 negative pair로는 batch에 있는 나머지 이미지들을 사용한다.

아래는 simCLR의 알고리즘이다. 여기서 loss는 분자에 유사한 이미지 pair $$(x_i, x_j)$$의 점수, 분모는 자기자신을 제외한 나머지 이미지들, 즉 유사하지 않는 pair들의 점수 $$(x_i,x_{k(k!=j)})$$가 오게 된다.

논문에서는 이미지들에 적용되는 augmentation에 따라, 그리고 이 augmentation의 조합에 따라 성능이 다르게 나온다고 한다. 다만 마찬가지로, simCLR 또한 negative pair가 많을수록, 즉 batch size가 커야지만 학습이 잘 이루어진다는 단점이 존재해서, 이러한 단점을 보완한 MoCo라는 후속 논문도 등장하였는데 이는 추후 다른 글로 정리해보도록 하겠다.

2) NCE: Noise Contrastive Estimator

NCE 논문 논문 참고자료

해당 모델에서는 softmax 대신에 binary classifier를 사용하였다. 두 개의 input word가 어울릴 수 있냐 없냐는 판단하는 것이다. True pair와 Fake pair를 만들어서, true인지 pair인지 예측하는 방법이다.

만약 training data가 $$x_1, x_2, .. x_m$$개까지 있다고 가정해보자. 이때 이 데이터들이 샘플링되었다고 가정되는 $$p_m$$이라는 확률 분포가 존재한다고 생각하자. 우리는 이 $$p_m$$을 최적화하는 것이 목표이다. ($$p=p(y=c_i|x),i=1,...,C$$) 원래는 지금까지 모든 클래스에 대한 $$p(y=c_i|x)$$를 최적화하는 것이 목표였다. NCE는 여기서 fake인 probability distribution도 도입한다. 그리고 N개 $${Y_1, .. Y_n}$$ 를 랜덤하게 sampling 한다. 이때 $$p_m$$과 $$p_n$$에서 나온 데이터들이 구분되도록 학습을 한다. 마치 가짜인지 진짜인지 구분하는 binary classification 문제가 된 것이다.

추후 자주 등장할 InfoNCE에서도 사용되는 개념이므로 잘 이해하고 넘어가야 한다.. 이 부분도 논문을 참고하여 좀 더 명확히 이해를 해보자

** 아래의 강의를 참고하여 작성하였습니다. https://www.youtube.com/watch?v=cv_iOJ_OaUM&list=PL0E_1UqNACXDTwuxUzCl5AeEjXBfWxCwc&index=18**

1. Introduction

-> 기존 ViT는 이미지에. globally하게 self-attention을 적용하여ㅑ 이미지 사이즈에 따라 quadratic complexity를 지니고 있다. swin transformer는 이미지 패치들을 merging함으로써 hierarchical feature map을 만든다. 그리고self-attention을 이미지 전체에 적용하는 것이 아닌, 일부분에 적용함으로써 image size에 따른 linear complexity를 지니고 있다.

해당 논문은 transformer를 backbone 모델의 역할을 할 수 있게 새로 제안하였다. 우선 이미지와 텍스트 모달리티 사이에는 큰 차이점들이 존재하여 자연어에 사용되는 트랜스포머를 그대로 적용할 수 없다. 우선 이미지는 토큰의 scale 측면에서 다양성을 띄게 된다. 기존 비전 트랜스포머들은 이러한 점들을 고려하지 않고 고정된 사이즈의 토큰들을 사용한다. 또 다른 차이점은, 이미지가 더 큰 resolution(여기서는 데이터 정보의 크기?라고 생각해야 할 것같다.)을 지니고 있다. quadratic complexity를 띄고 있는 transformer에게는 치명적인 문제로 작용한다. 저자는 hierarchical feature map와 image size에 비례한 complexity를 보장하는 transformer를 선보임으로써 해당 문제들을 효과적으로 해결하였다. hierarchical feature map에서는 작은 사이즈의 patch들에서 layer가 깊어짐에 따라 patch size를 키워가는 구조를 세웠다. linear complexity는 locally non-overlapping window에 self-attention을 적용함으로써 해결하였다. patch의 개수 자체는 window마다 fix되어져 있기 때문에 linear complexity를 띄는 것이다.

shifting approach vs sliding approach 또한, window를 sliding하는 대신 다음 layer의 window 크기를 shift함으로써 latency도 줄이고, 다른 patch들간의 연관성 또한 반영할 수 있다. shift window를 만드는 방법은 아래에서 자세하게 설명하겠다.

2. Related Work

Self-attention/Transformers to complement CNNS

CNN에 attention layer를 추가하는 방향으로 학습하는 연구도 진행되었다. self-attention은 distant dependencies와 heterogeneous interactions를 인코딩하면서 backbone과 head network를 보충해준다.(기존 cnn은 locality를 최우선으로 하는 모델이었기 때문에 이러한 self-attention의 도입은 globality를 고려해줄 수 있는 좋은 method이다.)

Transformer based vision backbones

transformer를 backbone으로 사용하는 모델은 ViT, 그리고 적은 데이터로 학습할 수 있는 DeiT 등이 존재한다. ViT는 제 성능을 발휘하려면 수많은 데이터로 학습을 해야 제 성능을 발휘할 수 있다는 단점이 존재하고, 또한 고화질 이미지에 대해서는 patch size가 상대적으로 큰 편이라 feature map이 low-resolution 특징을 띌 수 있다는 단점이 존재한다. 이를 해결하기 위해 direct upsampling하거나, deconvolution하는 방향도 존재하지만, 이는 낮은 성능을 띈다는 문제점이 존재한다.

3. Method

3.1 Overall architecture

우선 이미지를 non-overlapping patch를 이용해서 나눈다. 각 patch들을 토큰이라고 생각하고, 토큰들의 feature를 픽셀값의 concatenation이라고 생각하였다. 해당 논문에서는 4 x 4 사이즈의 패치를 이용한다. (즉 각 patch의 차원을 4 x 4 x 3 = 48이라 생각한다.) 여기에 linear embedding을 거쳐 C dimension으로 만든다. Stage 1 단계에서는 C dimension으로 표현된 각 patches를 입력으로 받는다. 이때, patch의 개수는 ($$\frac{H}{4}\times\frac{W}{4}$$) 이다. Stage 2 단계에서는 hierarchical representation을 만들기 위해서, layer가 깊어질수록 patch를 합침으로써 토큰의 개수를 줄인다. 첫 layer에서는 2 x 2 개의 이웃 패치를 합친다. 이렇게 만들어진 4C dimension을 downsampling을 통해 2C로 바꾼다. 그 이후에 swin transformer block이 적용된다. 이후 resolution은 $$\frac{H}{8}\times\frac{W}{8}$$로 바뀐다. Stage 3($$\frac{H}{16}\times\frac{W}{16}$$), 4($$\frac{H}{32}\times\frac{W}{32}$$)도 동일 과정을 반복한다. 이러한 resolution은 기존 VGG나 ResNet 모델과 유사하다.

Swin Transformer block

Swin transformer는 기존 multi-head attention에 shifted windows module을 추가하였다. 2-layer MLP with GELU 이후 shifted window module이 첨가된 multi-head attention layer를 지나게 된다. MLP layer와 MSA layer를 지나기 전에는 LayerNorm layer를 지나게 되고, 모듈 하나를 지날때마다 residual connection을 지나게 된다.

3.2 Shifted Window based self-Attention

표준적인 transformer은 global self-attention을 적용하는데, 이러한 점이 토큰의 개수에 따라 복잡도가 quadratic하게 증가하게 된다는 문제점이 존재하고, 이는 dense prediction을 요하거나 이미지가 고해상도인 경우에 큰 문제점들을 야기한다.

1) self-attention in non-overlapped windows

효율적인 모델링을 위해 local window 안에서 self-attention을 계산한다. window는 non-overlapping한 방법으로, 짝수 개수로 나뉘어진다. 각 window는 M x M 개의 패치를 포함하고 있다. h x w 개의 패치들의 computational complexity는 아래와 같다.

기존 복잡도 $$\Omega(MSA)=4hwC^2 + 2(hw)^2C$$ 수정된 복잡도 $$\Omega(W-MSA)=4hwC^2 + 2M^2hwC$$ 기존 복잡도는 이미지의 높이와 너비에 quadratic한 형태를 띄었지만, 제안한 모델에서는 M이 fixed size인 7에 해당되기 때문에 이미지 사이즈에 대해 linear한 복잡도를 띈다고 말할 수 있는 것이다. 저 식이 정확히 어떠한 식으로 유추되는지는 자세하게 파악하진 못했지만, 한번 설명해보도록 하겠다.

우선 original transformer은 $$\frac{H}{patch,size}\times\frac{W}{patch,size}$$ 개의 patches들은 전체 patches인 $$\frac{H}{patch,size}\times\frac{W}{patch,size}$$ 에 대해 각각의 attention value를 구하는 연산 과정이 존재한다. 즉, 약 $$\frac{H}{patch,size}\times\frac{W}{pathch,size} \times \frac{H}{patch,size}\times\frac{W}{patch,size}\fallingdotseq(hw)^2$$ 의 연산 과정을 거쳐야 하기 때문에 이미지 사이즈에 quadratic한 복잡도를 띄는 것이다. 그렇지만 해당 모델은 하나의 patch에 대해 attention value를 구할 때. 전체 이미지 patch를 참고하는 것이 아닌 neighboring한 patches들을 이용하여 계산하기 때문에 $$\frac{H}{patch,size}\times\frac{W}{pathch,size} \times (local,neighbor, patches)\fallingdotseq(hw)$$ 아래와 같은 복잡도를 띄게 된다.

2) Shifted window partitioning in successive blocks

window-based self-attention 모듈은 window간의 연관성을 반영시켜주지 못할 수 있기 때문에, 기존의 sliding window 대신 shifted window approach를 택하였다. 이 접근법은, swin transformer block 내 2개의 연속된 attention layer에 다른 window를 적용하는 기법이다.

위 사진처럼, 첫 모듈은 일반적인 partitioning strategy를 사용한다. 8x8 featrue map을 4 x 4 크기의 2 x 2 개의 window로 분할한다. 다음 모듈에서는 ($$\frac{H}{2},\frac{W}{2}$$) pixels만큼 윈도우를 displace(밀어낸다?)하고 계산을 진행한다. 이러한 shifted window approach에서는 block이 아래와 같이 계산된다. 여기서 $$\hat{z}^l$$과 $$z^l$$은 각각 W-MSA와 MLP 모듈의 output이다. 그리고 W-MSA와 SW-MSA는 각각 일반적인 윈도우를 사용한 멀티헤드와 shifted window partitioning을 사용한 멀티헤드 어텐션이다.

3) Efficient batch computation for shifted configuration

shifted window partitioning는 만일 ($$\frac{H}{M},\frac{W}{M}$$) 에서 ($$\frac{H}{M}+1,\frac{W}{M}+1$$)로 window를 shift할 때, 몇개의 window가 MxM보다 사이즈가 작아지는 경우 문제가 발생한다. 가장 기본적인 해결책은 padded 값을 첨가하는 것이다. 하지만 이 방법은 윈도우 개수도 동시에 증가시키게 만들기 때문에 computation cost가 증가된다. 저자는 이러한 점을 보안하기 위해 cyclic-shifting 방법을 사용하기로 했다. 이러한 shift 이후에는 batched window가 여러개의 sub-window로 구성된다. cyclic-shifting을 이용하면 윈도우 개수는 그대로 유지된다는 장점이 있다. 원리는 위의 그림과 같다. (정확힌 원리는 코드를 뜯어봐야지 알 수 있을 것 같다.)

4) Relative position bias

self-attention을 계산함에 있어, 각 헤드에 대해 relative position bias $$B\in R^{M^2\times M^2}$$가 존재한다.

$$Attention(Q,K,V)=SoftMax(QK^(T)/\sqrt{d}+B)V$$

이때 position의 range는 각 axis에 따라 [-M+1,M-1]이기 때문에, 더 작은 bias인 $$B\in R^{(2M-1)\times(2M-1)}$$을 채택한다.

4. Experiments

실험은 classification부터 시작하여 object detection까지 다양한 분야에서 진행되었다.

• classification

  

• object detection

  

• Ablation Study 해당 논문에서는 key method인 shifted windows와 relative position bias의 유무에 따라 모델 성능을 테스팅하였다. 논문을 참고하길 바란다.

Model-structure Code

Introduction

Video moment localization란, 영상 내에서 highlight 혹은 쿼리와 관련된 짧은 순간을 특정하는 task에 해당된다. 해당 논문은 유사 task인 moment retrieval, highlight detection task들의 문제점을 지적하는 것으로부터 시작한다.

우선 moment retrieval task의 데이터셋들은 1) annotaion이 video의 앞과 끝에만 이루어져 있는 bias 문제가 존재한다. 2) 그리고 한 비디오에 한 개의 annotation만 이루어져 있다는 문제점이 존재한다. Highlight detection는 query agnostic, 즉 쿼리와는 관계없이 진행되는 task로써 비디오 내에 highlight 부분을 찾아내는 task이다. 하지만 데이터 수가 현저히 적다는 문제점이 존재한다.

이러한 문제점으로부터 본 논문은 기존 2개의 task(moment retrieval & highlight detection)를 하나의 task에서 처리하도록 새로운 데이터셋인 QVHIGHLIGHTS를 제작하였고, 새로운 모델 구조인 Moment-DETR를 제안하였다.

Data collection and analysis

해당 논문은 단순히 새로운 모델 구조만을 제안한 것이 아닌, 데이터셋 생성 또한 진행하였다. (개인적으로 연구에 있어서는 데이터를 논리적으로 구축하는 것도 중요한 능력이라 생각하여, 해당 논문에서 참고할 점들이 많았다.) 저자는 본 논문에서 1) 하나의 비디오에 대해 여러개의 annotation을 진행하였다는 점, 2) 5개의 Likert-scale 를 기준으로 각 moment에 대해 saliency score를 매기는 annotation까지 진행하였다는 의미가 존재한다. 이때 saliency score는, 해당 moment가 얼마나 깔끔한지? (query와 관계없는 타 물체나 action이 없는) 를 나타내는 score라고 생각하면 될 듯 하다.

1) Data Collection

Collecting videos and quries

다양한 topic의 video를 선정하였는데, 우선 전세계 event를 포착하기 쉽고, 다양한 앵글로 촬영된 vlog, 심각한 topic을 담고있는 재난 관련 뉴스 데이터를 선정하였다. 이후 각 video에 tagging을 진행하였는데, 1) 비디오를 2초 단위로 클리핑하고, 각 클립들과 관련된 쿼리를 태깅하도록 하였다. 2) 이후, 특정 쿼리와 관련된 클립들을 모두 선정하도록 하였다. 이러한 데이터셋의 품질을 검증하기 위해 태깅을 진행하지 않았던 다른 작업자들로 하여금 각 쿼리에 대해 연관성이 높아보이는 클립을 선정하였다. 이후 IoU, 즉 생성한 데이터셋과 타 작업자들이 관련성있다고 선정한 클립들이 겹치는 정도로 정확성을 검증하였다.

Annotating saliency scores

특정 쿼리와 클립들이 관련되어져 있다고 하여도, 각 클립들의 품질은 각양각색이기 때문에, query와 클립이 얼마나 연관되어져 있는지를 점수로 태깅하였다. (카메라 앵글은 똑바른지, 비디오가 모호하게 찍히진 않았는지)

• 여기서 의문점. 비디오 클립 범위의 다양성을 증가시키면 computation cost가 많이 들기 때문도 있고, 찾고자 하는 moment가 짧은 경우가 많아 비디오를 2초로 클리핑 진행한 것이 효과적이라고 하였는데, 이는 추가적인 검증이 필요할 듯 싶었다. 마지막에 선정된 moment들이 contiguous하게 연결되어있으면 합치는 과정도 넣어주면 좋지 않을까 셍각헸다.

Methods: Moment-DETR

1) Architecture

Moment-DETR model architecture는 다음과 같다.

Input

우선 Transformer encoder에 들어갈 input을 정의내려야 한다. input은 하나의 비디오 projection값과 하나의 쿼리가 concat되어 들어간다. (이때 하나의 비디오가 한번에 들어갈 수 있는 이유는, 비디오의 길이가 150초 가량으로 그렇게 길지는 않다.)

우선, SlowFast과 video encoder(ViT)를 사용하여 매 2초마다 feature $$f_{slowfast}$$, $$f_{ViT}$$를 뽑아내었다. 이후 normalize하고 concat하여 $$E_v\in\mathbb{R}^{L_v\times2816}$$를 만들어낸다. 비슷한 과정으로 query는 CLIP text encoder를 지나면서, $$E_q\in\mathbb{R}^{L_q\times512}$$를 만든다. 추후 CLIP에 관한 논문도 정리해보도록 하겠다.

• 코드

  # 1. Video and txt embedding
  # 애초에 embedding되어 데이터가 제공됨. 그래서 이미 embedding 된 feature를 불러오기만 함.
  # start_end_dataset.py 참고
  def _get_query_feat_by_qid(self, qid):
    q_feat_path = join(self.q_feat_dir, f"qid{qid}.npz")
    q_feat = np.load(q_feat_path)[self.q_feat_type].astype(np.float32)
    if self.q_feat_type == "last_hidden_state":
        q_feat = q_feat[:self.max_q_l]
    if self.normalize_t:
        q_feat = l2_normalize_np_array(q_feat)
    if self.txt_drop_ratio > 0:
        q_feat = self.random_drop_rows(q_feat)
    return torch.from_numpy(q_feat)  # (D, ) or (Lq, D)
  
  def _get_video_feat_by_vid(self, vid):
    v_feat_list = []
    for _feat_dir in self.v_feat_dirs:
        _feat_path = join(_feat_dir, f"{vid}.npz")
        _feat = np.load(_feat_path)["features"][:self.max_v_l].astype(np.float32)
        if self.normalize_v:
            _feat = l2_normalize_np_array(_feat)
        v_feat_list.append(_feat)
        # some features are slightly longer than the others
    min_len = min([len(e) for e in v_feat_list])
    v_feat_list = [e[:min_len] for e in v_feat_list]
    v_feat = np.concatenate(v_feat_list, axis=1)
    return torch.from_numpy(v_feat)  # (Lv, D)
  

이후, $$E_q$$와 $$E_V$$를 같은 dimension인 d로 projection하고 concat하여  $$E_{input}\in\mathbb{R}^{L\times d},L=L_v+L_q$$를 만들어낸다.

```python
# 2. separate 2-layer perceptrons with layer norm and dropout to project into a share embedding size d
self.input_txt_proj = nn.Sequential(*[
            LinearLayer(txt_dim, hidden_dim, layer_norm=True, dropout=input_dropout, relu=relu_args[0]),
            LinearLayer(hidden_dim, hidden_dim, layer_norm=True, dropout=input_dropout, relu=relu_args[1]),
            LinearLayer(hidden_dim, hidden_dim, layer_norm=True, dropout=input_dropout, relu=relu_args[2])
        ][:n_input_proj])
self.input_vid_proj = nn.Sequential(*[
            LinearLayer(vid_dim, hidden_dim, layer_norm=True, dropout=input_dropout, relu=relu_args[0]),
            LinearLayer(hidden_dim, hidden_dim, layer_norm=True, dropout=input_dropout, relu=relu_args[1]),
            LinearLayer(hidden_dim, hidden_dim, layer_norm=True, dropout=input_dropout, relu=relu_args[2])
        ][:n_input_proj])

# 3. concatnate video and query representation
src_vid = self.input_vid_proj(src_vid)
src_txt = self.input_txt_proj(src_txt)

src = torch.cat([src_vid, src_txt], dim=1)  # (bsz, L_vid+L_txt, d)

# transfomer를 학습할 때는 masking을 통해 학습을 진행. 
mask = torch.cat([src_vid_mask, src_txt_mask], dim=1).bool()  # (bsz, L_vid+L_txt)

Transfomer encoder-decoder

Encoder 인코더에는 t개의 encoder layer가 스택 형식으로 쌓여있다. 통상적인 transformer와 동일하게 multihead attention과 FFN으로 구성되어져있다.

Decoder 디코더는 multihead self attention과 encoder의 output이 반영되도록 하는 cross-attention이 들어가 있다. 이때 디코더의 input으로 Moment Queries가 들어가는데, 이때 text queries와 moment queries는 다르다. Decoder에 들어가는 moment quries가 도대체 뭔지 헷갈려서 찾아보니, "self.query_embed = nn.Embedding(num_queries, hidden_dim)"였다. 즉 text query 그 자체는 아니고, query의 positional embedding 그 자체였다. 내 생각엔 찾고자 하는 input영상과 text quries는 이미 인코더에서 입력되었기 때문에 query의 position을 학습할 layer를 decoder 앞전에 배치한 듯하다. 해당 구조의 정확한 이유는 차차 알아봐야겠다.

• 코드

########## 모델 구조를 이해하기 쉽게 축약한 코드이다. 원본 코드는 깃헙을 참고하자 #################

model.py

pos_vid = self.position_embed(src_vid, src_vid_mask) # (bsz, L_vid, d) pos_txt = self.txt_position_embed(src_txt) if self.use_txt_pos else torch.zeros_like(src_txt) # (bsz, L_txt, d)

pad zeros for txt positions

Moment-DETR input들 모음

pos = torch.cat([pos_vid, pos_txt], dim=1) # (#layers, bsz, #queries, d), (bsz, L_vid+L_txt, d)

src = torch.cat([src_vid, src_txt], dim=1) # (bsz, L_vid+L_txt, d)

여기서 mask는 여러 의미로 받아들일 수 있지만, masked self-attention에서의 mask는 아니고

query의 token 개수가 최댓값보다 작을 때 해당 포지션은 의미없는 값인 0으로 padding하기 위해 만든 input이다.

mask = torch.cat([src_vid_mask, src_txt_mask], dim=1).bool() # (bsz, L_vid+L_txt)

moment queries의 정체

query_embed = nn.Embedding(num_queries, hidden_dim) hs, memory = self.transformer(src, ~mask, self.query_embed.weight, pos)

transformer.py 축약 코드

class Transformer(nn.Module):

def __init__(self, d_model=512, nhead=8, num_encoder_layers=6,
             num_decoder_layers=6, dim_feedforward=2048, dropout=0.1,
             activation="relu", normalize_before=False,
             return_intermediate_dec=False):

def forward(self, src, mask, query_embed, pos_embed):
    """
    Args:
        src: (batch_size, L, d)
        mask: (batch_size, L)
        query_embed: (#queries, d)
        pos_embed: (batch_size, L, d) the same as src
    """
    # flatten NxCxHxW to HWxNxC
    bs, l, d = src.shape
    src = src.permute(1, 0, 2)  # (L, batch_size, d)
    pos_embed = pos_embed.permute(1, 0, 2)   # (L, batch_size, d)
    # query_embed = nn.Embedding(num_queries, hidden_dim)
    query_embed = query_embed.unsqueeze(1).repeat(1, bs, 1)  # (#queries, batch_size, d)

    tgt = torch.zeros_like(query_embed)
    memory = self.encoder(src, src_key_padding_mask=mask, pos=pos_embed)  # (L, batch_size, d)
    hs = self.decoder(tgt, memory, memory_key_padding_mask=mask,
                      pos=pos_embed, query_pos=query_embed)  # (#layers, #queries, batch_size, d)
    hs = hs.transpose(1, 2)  # (#layers, batch_size, #qeries, d)
    memory = memory.transpose(0, 1)  # (batch_size, L, d)
    return hs, memory

class TransformerEncoderLayer(nn.Module):

def __init__(self, d_model, nhead, dim_feedforward=2048, dropout=0.1,
             activation="relu", normalize_before=False):

def with_pos_embed(self, tensor, pos: Optional[Tensor]):
    return tensor if pos is None else tensor + pos

def forward(self, src,
                src_mask: Optional[Tensor] = None,
                src_key_padding_mask: Optional[Tensor] = None,
                pos: Optional[Tensor] = None):
    src2 = self.norm1(src) ## forward_pre일 때만 넣기!!!
    q = k = self.with_pos_embed(src2, pos)
    src2 = self.self_attn(q, k, value=src2, attn_mask=src_mask,
                          key_padding_mask=src_key_padding_mask)[0]
    src = src + self.dropout1(src2)
    src2 = self.norm2(src)
    src2 = self.linear2(self.dropout(self.activation(self.linear1(src2))))
    src = src + self.dropout2(src2)
    return src

class TransformerDecoderLayer(nn.Module):

def __init__(self, d_model, nhead, dim_feedforward=2048, dropout=0.1,
             activation="relu", normalize_before=False):
    super().__init__()

def with_pos_embed(self, tensor, pos: Optional[Tensor]):
    return tensor if pos is None else tensor + pos

def forward(self, tgt, memory,
                tgt_mask: Optional[Tensor] = None,
                memory_mask: Optional[Tensor] = None,
                tgt_key_padding_mask: Optional[Tensor] = None,
                memory_key_padding_mask: Optional[Tensor] = None,
                pos: Optional[Tensor] = None,
                query_pos: Optional[Tensor] = None):
    tgt2 = self.norm1(tgt)
    q = k = self.with_pos_embed(tgt2, query_pos)

    #### self-attention
    tgt2 = self.self_attn(q, k, value=tgt2, attn_mask=tgt_mask,
                          key_padding_mask=tgt_key_padding_mask)[0]
    tgt = tgt + self.dropout1(tgt2)
    tgt2 = self.norm2(tgt)

    #### cross attention
    tgt2 = self.multihead_attn(query=self.with_pos_embed(tgt2, query_pos),
                               key=self.with_pos_embed(memory, pos),
                               value=memory, attn_mask=memory_mask,
                               key_padding_mask=memory_key_padding_mask)[0]
    tgt = tgt + self.dropout2(tgt2)
    tgt2 = self.norm3(tgt)
    tgt2 = self.linear2(self.dropout(self.activation(self.linear1(tgt2))))
    tgt = tgt + self.dropout3(tgt2)
    return tgt

#### Prediction heads
모델 구조는 transformer encoder에 $$E_{input}$$을 집어넣어 saliency score와 representation을 뽑아내고, 이후 Decoder 파트에 moment queries를 넣어 moment의 normalized center와 width를 예측한다. 그리고 각 moment들의 foreground, background 여부(찾고자 하는 moment인지 아닌지) 또한 예측한다. 
- 코드

```python
# model.py: transformer output값들

outputs_class = self.class_embed(hs)  # (#layers, batch_size, #queries, #classes)
outputs_coord = self.span_embed(hs)  # (#layers, bsz, #queries, 2 or max_v_l * 2)
if self.span_loss_type == "l1":
    outputs_coord = outputs_coord.sigmoid()
out = {'pred_logits': outputs_class[-1], 'pred_spans': outputs_coord[-1]}

txt_mem = memory[:, src_vid.shape[1]:]  # (bsz, L_txt, d)
vid_mem = memory[:, :src_vid.shape[1]]  # (bsz, L_vid, d)
if self.contrastive_align_loss:
    proj_queries = F.normalize(self.contrastive_align_projection_query(hs), p=2, dim=-1)
    proj_txt_mem = F.normalize(self.contrastive_align_projection_txt(txt_mem), p=2, dim=-1)
    proj_vid_mem = F.normalize(self.contrastive_align_projection_vid(vid_mem), p=2, dim=-1)
out.update(dict(
                proj_queries=proj_queries[-1],
                proj_txt_mem=proj_txt_mem,
                proj_vid_mem=proj_vid_mem
            ))

out["saliency_scores"] = self.saliency_proj(vid_mem).squeeze(-1)  # (bsz, L_vid)
if self.aux_loss:
            # assert proj_queries and proj_txt_mem
            out['aux_outputs'] = [
                {'pred_logits': a, 'pred_spans': b} for a, b in zip(outputs_class[:-1], outputs_coord[:-1])]
            if self.contrastive_align_loss:
                assert proj_queries is not None
                for idx, d in enumerate(proj_queries[:-1]):
                    out['aux_outputs'][idx].update(dict(proj_queries=d, proj_txt_mem=proj_txt_mem))
return out

데이터 구조는 아래와 같고, 참고하자.

{
    "qid": 8737, 
    "query": "A family is playing basketball together on a green court outside.", 
    "duration": 126, 
    "vid": "bP5KfdFJzC4_660.0_810.0", 
    "relevant_windows": [[0, 16]],
    "relevant_clip_ids": [0, 1, 2, 3, 4, 5, 6, 7], 
    "saliency_scores": [[4, 1, 1], [4, 1, 1], [4, 2, 1], [4, 3, 2], [4, 3, 2], [4, 3, 3], [4, 3, 3], [4, 3, 2]]
}

2) Matching and Loss Functions

loss 관련 코드는 model.py에 있으니 참고하자.

(loss 구하기 전) Set prediction via biapartite matching

$$\mathcal C_\text{match} (y_i, \hat y_{sigma(i)}) = -\mathbb {1}{ {c_i \neq \varnothing } }\hat p{\sigma (i)}(c_i) + \mathbb 1_{{ c_i\neq\varnothing }}\mathcal L_\text{moment}(m_i, \hat m_{\sigma(i)})$$

Moment queries에 대한 $N$개의 예측을 $\hat y={ \hat y_i }^N_{i=1}$로 나타내고, foreground와 background를 구분하는 ground truth 값을 $y={ y_i }^N_{i=1}$과 같이 나타낸다. 이때 moment queries의 개수는 실제 정답값들보다 더 많다는 것에 착안하여, 정답값의 개수와 예측값의 개수는 일대일 대응이 되지 않을 수 있다. 이를 해결하기 위해 각 예측값과 정답값들을 매칭 시켜줄 필요가 있고, 그 매칭 식이 위에서 보이는 식이다. 헝가리안 알고리즘을 통해서 가장 최적의 매칭 조합을 찾게 된다.

moment localization loss

$$\mathcal L_\text{moment}(m_i, \hat m_{\hat\sigma(i)})=\lambda_{L1}|| m_i - \hat m_{\hat\sigma(i)} || + \lambda_\text{iou}\mathcal L_\text{iou}(m_i, \hat m_{\hat\sigma(i)})$$ prediction과 ground truth moments 들간의 모순을 계산한다. 이때, L1 loss와 IoU loss를 사용한다.

saliency loss

$$\mathcal L_\text{saliency}(S) = \max(0, \Delta + S(t_\text{low}) - S(t_\text{high})) + \max(0, \Delta+S(t_\text{out}) - S(t_\text{in}))$$ positive와 negative clips간의 hinge loss로 구하게 된다. GT moments 내부의 높은 score의 clip $t_\text{high}$와 낮은 score의 clip $t_\text{low}$로 구성된 첫 번째 쌍과 GT 내부의 clip $t_\text{in}$, GT 외부의 clip $t_\text{out}$로 구성된 두 번째 쌍을 이용해 loss를 계산하며 $\Delta$는 마진을 의미한다.

overall loss

$$\mathcal L = \lambda_\text{saliency}\mathcal L_\text{saliency}(S) + \sum^N_{i=1}[-\lambda_\text{cls}\log\hat p_{\hat \sigma(i)}(c_i) + 1_{c_i\neq\varnothing}\mathcal L_\text{moment}(m_i, \hat m_{\hat\sigma(i)})]$$

Experiments and Results

학습결과는 아래와 같다. r1, mAP(mean average precision) 등의 평가지표를 활용하여 moment retrieval과 highlight detection을 평가하였다.

추후 읽어볼 논문

1. QD-DETR : Query-Dependent Video Representation for Moment Retrieval and Highlight Detection https://github.com/wjun0830/QD-DETR

2. Correlation-guided Query-Dependency Calibration in Video Representation Learning for Temporal Grounding https://github.com/wjun0830/CGDETR

Attention function은 Attention(Q, K, V) = Attention value 이렇게 구성되어져 있다. 이때 attention value는 values들의 weighted average라고 생각을 하면 된다. Step 0에서의 값들을 정리해보자면

• Query (context): Decoder hidden state $$S_0$$
• Key, Value (reference): Encdoer hidden states $${h_0, h_1,.., h_k}$$

기본적은 구성 요소는 다음과 같고, 지금부터는 위 요소들을 이용해 attention score와 value들을 어떻게 구하는지 설명해보도록 하겠다.

• Attention scores: Decoder hidden states와 Encoder value간의 relevance $$e_0=[S_0^\top h_1, ...S_0^\top h_k]$$
• Attention coefficients: $$\alpha_0=softmax(e_0)=\frac{exp(e_0)}{\sum_i exp(e_{ti})}=[\alpha_{01},\alpha_{02},..\alpha_{0k}]$$
• Attention value: weighted average of encoder hidden states $$a_0=\sum_{i=1}^k \alpha_{0i}h_0$$
  • 각 encoder의 value가 사전이라 생각하면, 입력된 context에 가장 유사도가 높은 value값을 추출한다고 생각할 수 있다. 또한 context는 이전 decoder의 hidden states 값과 새로운 입력값에서 도출된다는 점에서, 시간이 globally 하게 고려되고 있다고 생각할 수 있다.
  • Weight: similarity between query and key

1-1. MultiLSTM

MultiLSTM

기본적인 LSTM 모델에 attention method를 추가한 것이다.

• Query (context): previous hidden state h_{t-1} of LSTM. 여기서 Query는 t-1 번째 hidden states와 t번째 text token이 반영된 값이라고 생각하면 편리하다.
• Key, Value (reference): Encoder의 값 대신, N recent input frame features를 본다.
• Attention value: weighted average of N recent frame features, 즉 현재 context에서 가장 의미가 있는 frame의 features 조합을 추출한다.
• Multiple output: N frames를 참고한 prediction 값.

1-2. Visual Attention

Action Recognition using Visual Attention

위에서는 시간적인 측면에서 Attention을 적용했다만, 공간적 측면에서 Attention을 적용하는 방법도 존재한다. Spatial attention은 이미지의 어느 파트에 집중해야 이미지 분류의 도움이 되는지를 반영하여 다음 hidden states값을 도출해낸다. 이때의 Query, Key, Value 값들의 의미를 살펴보자면,

• Query (context): input image $$X_{t-1}$$ 의 $${t-1}$$번째 representation(hidden states) $$h_{t-1}$$
• Key, Value (reference): t번째 input frames의 regional features

와 같고, attention value는 아래와 같다.

• Attention value: weighted sum of region featues. t번째 input frame 과 query간의 similarity를 구하고, 이 coefficients를 t번째 input frame에 element wise로 곱해주면서 attention이 적용된 t번째 representation이 등장한다.
  • weights: $$l_{t}$$ ($$h_{t-1}$$와 $$X_T$$간의 공간적 relevance)

2. Transformer

Transformer의 핵심은 위에서 계속 설명했던 attention이 있다. Transformer를 다루기 전에 해당 개념을 다시 살펴보겠다. 참고로, 앞으로 대부분의 코드에서 transformer를 구현할 시 해당 layer code를 이용하게 될 것이다. nn.Multiheadattention code 설명

2-1. Self-Attention

일단 Attention 자체는 query(문맥)와 key 간의 유사도를 구하고, 이를 가중치로 이용하여 value의 weighted sum을 구하는 method이다. 이때, query, value, key가 무엇이냐에 따라 attention의 종류들이 달라진다. Self-Attention은 말그대로 나 자신과 관련된 attention, 즉, 나 자신의 어느 부분에 집중하여 값을 예측할 것인가와 관련된 말이다. 그래서 Self-Attention은 query값도 자기 자신, key - Value도 자기 자신에 해당된다. 이에 반해 차후 등장할 cross-attention 등은 key, value 값이 자기 자신에게서 비롯되지 않는데, 이는 밑에서 설명하도록 하겠다. 일단 self-attention의 간략한 로직이다.

• Input tokens으로 $$x_1,x_2,...,x_N$$이 주어졌다고 가정하자.

• 각 token $$x_i$$에 linear transformation을 적용하여 $$Q_i, K_i, V_i$$를 만든다. 이때 각각의 값들은 $$x_i$$를 $$W_{Q^ i},W_{K^i},W_{V^i}$$) 로 linear transforamtion하는 것이다.

• $$x_i$$가 query라면, 자기 자신을 포함한 모든 토큰이 reference인 key, value값이 된다.

위 그림과 같이 query와 모든 key 값들 간의 similarity를 구하고, 이를 weight라고 가정한다. 이러한 weight에 각 value값을 곱하여 weighted sum을 구하고, 이것이 바로 $$z_i$$이다. 즉, $$x_i$$를 다른 문맥들과의 연관성으로 표현된 vector $$z_i$$로 변환된다. (이때, 임베딩 자체도 각 단어들이 연관되어져 있게끔 임베딩이 되어져야 한다.)

다시 설명하자면 $$z_i$$는** 1) 자기 자신인 $$query_i$$와 $$key_{1..n}$$까지의 유사도를 구하고, 2) 각각을 $$value_{1..n}$$과 곱하여 만들어진 weighted sum**이다.

이러한 과정을 아래의 그림처럼 모든 input token에 대해 진행해주고, 하나의 transformer block을 지날 때마다 input token 개수와 동일한, 변형된 ouput vector $$z_{i..n}$$가 산출된다.

즉, 결론적으로 transformer는 자기 자신을 문맥을 고려한 어떠한 vector로 변환시켜주는 모델이라고 생각하면 된다.

하지만 우리에겐 여전히 남아있는 질문들이 있다. 이러한 $$z$$ value들로 우리가 무엇을 할 수 있나? 여러가지 접근법들이 있을텐데, 예를 들어 attention을 활용하여 분류 task를 해결하는 상황이라고 생각해보자.

1) value들로 mean으로 계산하여 분류를 진행하는 방법이 존재할 것이다. 다만, 이런 방법들은 token이 많지 않을 때만 효과적으로 적용가능하다.

2) input token에 dummy token인 classification token을 추가한다. [cls] token은 기존 input token과 어떠한 연관성도 없기 때문에 비교적 균등하게 $$z_1, z_2, z_3, z_4$$를 대신하여 표현할 수 있다.

2-2. Details about Transformer

Transformer는 하단의 그림과 같이 인코더와 디코드 구조로 이루어져 있다. 각각에 대해 설명해보도록 하겠다.

*1) Encoder *

• Step 1. Input Embedding Input은 token들의 sequence이다. 이때 각각의 token들은 같은 사이즈들로 표현되는데, text는 pretrained된 word embedding으로 표현되던가, 이미지는 고정된 사이즈의 작은 이미지 patches로 표현되던가, 비디오는 frame embedding으로 표현된다. 단어들을 토큰으로 임베딩하는데에는 word2vec등 다양한 방법들이 존재한다.

• Step 2. Positional Encoding 기존 RNN은 토큰들의 순서를 반영하지 못한다는 단점이 있다. transformer는 이를 보안하기 위해 sinusoidal encoding을 사용하게 된다. 식은 아래와 같다. $$PE_{(pos,2i)}=sin(pos/10000^{2i/d_{model}})$$ $$PE_{(pos,2i+1)}=cos(pos/10000^{2i/d_{model}})$$ 사진을 참고하자면, positional encoding은 단어와 단어 사이간의 거리가 멀어짐에 따라 값들의 차이가 커져 내적값은 작아지고, 거리가 가까울수록 내적값은 커지게 된다. 또한, 각 위치를 고유한 벡터로 표현가능해진다는 장점이 있다. positional encoding이 등장하게 된 배경까지 알면 이해하기 쉬운데, 이는 링크로 첨부하겠다. https://pongdangstory.tistory.com/482

• Step 3. Contextualizing input embedding 위의 과정은 attention을 구했던 과정과 굉장히 유사하다. 하단의 그림을 참고하자. 우선 query, key, value 값들을 구하고,

query와 key값을 product한 값을 softmax layer에 지나게 한 후, 이를 value와 곱한다. 그러면 input과 동일한 size의 z가 산출되게 된다.

• Multi-head attention Multi-head attention을 쓰는 이유는, 매 z값을 산출할 때마다 어느 부분에 attention을 주느냐, 즉 (Q, K, V)에 따라 결과값이 달라진다. 이러한 다양성을 고려하기 위해 여러 head를 쓰는 것이다.

• Encoder attention 총 정리

• Step 4. Feed-Foward layer $$FFN(x) =max(0,xW_1+b_1)W_2+b_2$$ 해당 layer도 지나가게 된다. output은 여전히 동일한 사이즈의 contextualized token embedding이 나올 것이다. 추가적으로, residual connection을 추가하여 해당 layer가 필요해질때만 학습되도록 하였고(이를 통해 층수를 다양하게 쌓을 수 있다), normalization layer 또한 추가하였다.

2) Decoder Decoder part에서는 decoder의 input이 self-attention을 지나고, 이후 cross-attention을 지나는 과정을 이루어져있다.

• Step 1. Masked multi-head attention 맨 처음 input이 들어갈 때, encoder와는 다르게 자기 자신 순번까지의 token들만 활용하여 contextualize한다.

• Step 2. Cross attention cross attention은 query는 자기 자신, 나머지 key와 value는 encoder에서 온다. cross attention 관련 추가적 자료: Cross Attention

• Step 3. FFN & linear & softmax 위의 layer들을 모두 지난 후 하고 싶은 task에 따라 특정 layer들을 추가한다.

3. Transformer in Vision

1) 이미지

image patches를 토큰처럼 입력한다. 대신, 이미지 패치들은 순서가 중요하지 않기 때문에 바로 입력해도 된다. 기존 transformer와의 차이점은, patches(token이라고 생각하자)를 linear projection을 통해 patch embedding을 진행하고, postional embedding을 fixed 상태로 두지 말고, 아무런 값도 입력하지 않은 빈 layer로 냅두어 학습가능한 상태로 만든다. 이후의 학습과정은 모두 동일하다! input의 형태가 조금씩 변하면서 ViT가 발전 중이라고 한다.

문제점은, ViT는 컴퓨팅 파워가 무지막지하게 좋아야지만 제 성능을 발휘할 수 있다는 점이다. 그 이유로는 비교군이었던 CNN은 spatial locality와 positional invariance를 담고 있는데, ViT는 나를 표현하기 위해 그저 다른 모든 패치들로 표현해보려는 것이기 때문에, locality가 존재하지 않기 때문이다. 다만 해당 논문의 저자는, 데이터 크기만 크면 전체를 보아도 어느 부분에 집중해야 하는지 배우게 된다고 주장하지만, 정말 많은 데이터를 학습해야한다는 단점이 있다. ViT는 데이터가 많다는 가정하에 locality와 globality를 모두 보장할 수 있다는 장점이 있다.

(DeiT) 이후 연구는 computing cost를 줄이는 과정으로 진행되었다. 추가적으로 비디오 분야에서도 transformer가 적용되는데, 이 경우는 frame을 sequence 별로 입력한다. ViViT등의 논문을 참고하자.

아래의 강의를 참고하여 작성하였습니다. https://www.youtube.com/watch?v=NIFnKN2tWsE&list=PL0E_1UqNACXDTwuxUzCl5AeEjXBfWxCwc&index=14

코딩테스트 관련 알고리즘은 아래와 같다. 주로 이 아래의 알고리즘들 아래에서 문제가 출제된다 생각하고 확실하게 학습하고 지나가야 한다.

• DFS/BFS
• 이진 탐색
• DP (Dynamic Programming)
• 최단 경로: 다익스트라/플루이드 워셜
• 유니온 파인드/크루스칼/부분합/투 포인터

다이나믹 프로그래밍

다이나믹 프로그래밍은 규칙을 찾아내는 것에 집중해야 한다. 그러기 위해서는 특정 몇개의 입력값에 대한 출력값이 도출되는 과정들을 하나하나씩 적어보면서 규칙을 찾아낼 필요가 있다.

백준 1463번

https://www.acmicpc.net/problem/1463

오늘 풀어볼 문제도 위와 같은 방법으로 접근이 가능하다.

a(1) = 0 a(2) = 1 + a(1) # 2로 나누고 a(1) 값 사용 a(3) = 1 + a(1) # 3으로 나누고 a(1) 값 사용 a(4) = 1 + a(2) # 2로 나누고 a(2) 값 사용 a(5) = 1 + a(4) # 1빼면 4. 즉 4의 값을 사용하면 된다.

위의 정답 형태를 관찰하면 알겠지만, 마치 점화식의 꼴, 즉 이전의 정답값을 활용해 다음의 정답값을 도출해내는 것을 발견할 수 있다. 다만, 점화식을 세우기 위해서는 총 2가지 조건을 세워야 한다.

*1) 초기값은 무엇인지 (= 탈출 조건은 무엇인지) 2) 점화식은 무엇인지 *

해당 문제에서 1) 초기값은 n=1일 때이다. 이때의 정답은 1이다. 2) 점화식은 n을 3으로 나누기/2로 나누기/1 빼기를 순서대로 실행해보고, 실행가능한 연산을 실행한 결과 중 가장 최솟값을 최종값으로 입력하면 된다.

# 1을 뺐을 때
d[i] = 1 + d[i - 1]
if i%3==0: # 3으로 나눴을 때
    d[i] = min(d[i],1 + d[i//3])
if i%2==0: # 2로 나눴을 때
    d[i] = min(d[i],1 + d[i//2])

이렇게 점화식과 초기겂을 설정한 후에는, a(1)부터 a(최댓값)까지 미리 계산하여 dictionary를 만든 후 특정 n값을 입력하면 바로 결과가 출력되게끔 코드를 구현하면 된다.

코드 풀이

항상 생각하자. 중요한 것은 문제를 어떻게 해결할 것인지에 대한 논리이고, 코드는 그저 이를 옮겨적는 언어일 뿐이다!

n = int(input())

d = [0] * (n+1)

for i in range(2,n+1):
    # 확실하게 가능한 연산
    d[i] = 1 + d[i - 1]
    if i%3==0:
        d[i] = min(d[i],1 + d[i//3])
    if i%2==0:
        d[i] = min(d[i],1 + d[i//2])

print(d[n])