연금술사

요약

Cyclic learning rate (CLR) 은 learning rate을 수동으로 조절해갈 필요없이, 자동으로 최적의 값을 찾는 과정의 스케쥴링입니다. CLR은 LearningRateReduceOnPlatue와 같이 감소하는 방향으로만 학습율을 조절하는 것이 아니라, 특정 영역에서 증감을 반복합니다. 그리고 이를 실험적으로 증명했습니다.

문제는 학습률이 너무 작으면 학습의 수렴이 느려지고, 너무 큰 경우는 학습의 수렴을 보장할 수 없습니다. 이를 해결하기위해서, CLR이 나오기 전까지는 단순히 학습율을 줄여나가는 방식등을 사용했습니다. 

Cyclic learning rate (CLR)

CLR을 사용하는 경우는 아래의 그림(Figure 1)과 같이 더 적은 iteration내에 빠른 수렴을 실험적으로 할 수 있음을 보여주었습니다. CLR은 학습율을 증가시키는 것이 짧게는 학습에 부정적인 영향을 끼치지만, 학습의 긴 추이에서는 더 나은 최적화를 보여준다는 것을 경험적으로 확인해서 제안된 것입니다.

Cyclic learning rate은 최조값(minimum bound, base_lr), 최대값(Maximum bound, max_lr)을 지정해서 주기적으로 학습율을 증/감시키면서 학습합니다. 학습율을 어떻게 증감시킬지의 방법(policy)을 3가지로 제안합니다. 아래의 3가지 방법이 가능하며, 어떤 것을 사용하더라도 큰 차이없다고 합니다. 

1. Triangular window (linear)
2. Welch window (parabolic)
3. Hann window (sinusoidal)

아래는 triangular window (linear)의 방법입니다. 최대학습률, 최소 학습률, 스텝수(stepsize)의 3가지 파라미터를 사용자가 지정했을 떄, 최대최소율에 맞추어 증가, 감소하며 학습률이 변경됩니다. stepsize 반복할때까지 maxmum bound까지 올라가고, 이후 그 다음 stepsize까지 반복해서 최소학습률에 도달하는 식입니다. 파이토치에는 이를 구분하여 구현되어있습니다.(step_size_up, step_size_down) 

CLR이 효과적인 이유(주장)

1. Saddle point에서 학습률을 크게해서 탈출이 가능: Dauphin et al 연구팀의 주장에 따르면  학습이 제대로 안되는 이유는 로컬미니멈(local mimima)에 빠져서라기보단, 안장점(saddle point, gradient가 0 또는 거의0 지점)때문이라는 주장이 있습니다. 아래의 그림과 같이 saddle point인 경우, 평평하기 떄문에 gradient값이 작아 학습이 느리게 됩니다. 이때 학습률을 크게 증가시키면 이 saddle point을 탈출할 수 있다는 것입니다. 

2. 최소/최대값의 범위를 진동하며 사용하니, 최적의 학습률이 사용이 된다는 것

pytorch implementation. base_lr, max_lr, step_size 정하기

pytorch에서는 아래와 같이 torch.optim.lr_schedular.CyclicLR로 CLR이 구현되어있습니다. 논문에서 언급했던 것과 같이 base_lr, max_lr, stepsize을 지정해야합니다. pytorch에서는 step_size가 up구간, down구간으로 나눠져있습니다. 이 인자들을 어떻게 전달해야하는지 알아보겠습니다.

torch.optim.lr_scheduler.CyclicLR(
	optimizer, 
    base_lr, 
    max_lr, 
    step_size_up=2000, 
    step_size_down=None, 
    mode='triangular', 
    ...,
    verbose='deprecated'
)

1. base_lr (minimum lr), maximum lr 구하기

• LR range test: 모델을 적은수의 에폭만 미리 돌려보는것입니다. 예를 들어, 2에폭정도에 learning rate을 0부터 0.02까지 바꿔본다고 생각해보겠습니다. 2에폭정도 돈 후에, learning rate, accuracy의 라인플롯을 그립니다. accuracy가 나오게되는데, 0부터 증가했다가 감소하는 구간을 보입니다. 저자들은 증가하는 시점의 learning rate과 감소하는 시점의 learning rate이 base_lr, max_lr로 선택하는 것이 좋다고 주장합니다. 또는 최적의 학습율을 보이는 수의 2배 내에 있기 때문에, base_lr과 max_lr의 크기가 3~4배정도 주게 하면 좋다고합니다. 

또 다른 예시로, AlexNet의 LR range test의 결과를 보여드리겠습니다. 학습율(x축, learning rate)이 0.006이전까지는 학습이없다가 0.006정도부터 학습이 되기에, base_lr은 0.006으로 셋팅하면됩니다. 그리고, 이 그레프에서 0.015부터 학습률이 지속적으로 감소하기에 max_lr은 0.015으로 학습하는게 합리적이라고 합니다.

2. stepsize (cycle length) 구하기. stepsize은 배치사이즈를 구하면 1에폭당 얼마의 step으로 갈지 계산할 수 있습니다. CIFAR-10같은 경우 학습데이터가 50,000장의 이미지가 있는데, 배치사이즈가 100이라면, 500step(iteration)을 하게됩니다. CLR은 stepsize에 따라 성능차이가 크게 없다고는하지만, 보통 iteration(step)수의 2배 ~ 10배정도 설정하면 좋다고합니다. (*주의 논문에서는 하나의 배치사이즈를 학습한 것을 epoch)이라고 합니다. 논문에서 제시한 것과 같으면, 위의 예시에서 CIFAR-10의 배치사이즈가 100이었으면, 총 스텝수가 500이므로, CLR의 step으로 들어가는 것은 4,000정도 (=8*500)가 좋은 선택이라고합니다.

Introduction

NLP분야에서는 masked language라는 사전학습 전략으로 Transformer가 매우 인기를 끌었습니다. 반면, 비전테스크에서는 CNN의 대안으로 ViT가 쓰이는 것 같지만, 아직까지는 계산비용도 크고, 데이터도 많이필요해서 큰 이점을 못 얻고 있었습니다. 이 논문은 자기지도학습(Self-supervised learning)이라는 사전학습을 방법론을 이용해서, 비전테스크에서도 성공적인 사전학습을 할 수 있을지, 그리고 그 방법을 제시합니다. 

언어문제에서는 self-supervised learning의 pretext task로 masked language 을 진행합니다. 반면, 이미지 분류문제에서는 풍부한 이미지의 정보(예, 형태, 컬러 등)이 이미지에 포함되어 있습니다. 그리고, 이 풍부한 이미지의 몇몇으로 특징을 잘 추출해서 N개의 분류를 하는 문제를 풀게됩니다. 풍부한 이미지에 오직 사전에 정의한 N개의 분류문제만 풀기에, 더 작은 특징만 추출하여 학습한 다는 것 입니다.  그렇기에, 더 많은 정보를 학습할 수 있다면, Vision 문제를 더 잘 이해할 수 있는 향상점(room)이 아직 있다고 생각합니다.

Methods: DINO (knowledge distillation with no label)

DINO을 이해하기 위한 주요 내용은 아래와 같습니다

1. self-distiallation의 전체적인 구조(overview)
2. objective function 및 data augmentation 방법 (SSL을 위한)
3. Teacher network의 학습

1. Self-distillation의 전체적인 구조

DINO을 이해하기 위해서는 knowledge distillation에 대해서 먼저 이해해야합니다. 지식증류(knowledge distillation)의 이전 글(URL)을 보시면, 더 자세한 내용을 이해할 수 있습니다. 간략하게 지식증류를 요약하면, "큰 모델(teacher model)의 결과(output)은 큰 모델의 파라미터들의 정보들의 집약체이기에, 이 결과값(output)을 학습하는 작은 모델로 큰 모델을 성능/파라미터를 답습할 수 있다"라는 것입니다. 

이 지식증류 방법중에 DINO은 teacher-student model에 해당됩니다.

DINO을 가정은 2가지 모델이 있다고 가정합니다. 일반적인 student, teacehr모델은 크기가 다른 반면, DINO에서는 두 모델의 아키텍처는 동일합니다.

• teacher model($g_{\theta_{t}}$): 큰 모델을 의미하며, 이 모델의 파라미터는 $\theta_{t}$입니다.
• student model($g_{\theta_{s}}$): 작은 모델을 의미하며, 이 모델의 파라미터는 $\theta_{s}$입니다.
• input image($x$): 입력 이미지
• output probablity distribution ($P_{t}, P_{s}$): teacher model의 output($P_{t}$), student model의 output($P_{s}$) 입니다. 분포는 K개의 클레스의 분류라고 가정하여 K 차원의 크기입니다. 확률값처럼 해석하기위해서 softmax로 정규화한 값입니다. 좀 더 자세하게는 아래와 같이 표현할 수 있습니다. softmax함수의 입력값으로 전달하기전에 temperature scale을 주어, 분포의 뾰족한 정도(sharpness)을 조절할 수 있습니다. 분포를 평평하게 또는 클레스별로 차이가 심하게 나도록 조절한 후에 계산하는 값입니다. 아래의 식은 $P_{s}$인 student 모델의 확률분포값이고, t도 마찬가지로 그 아래의 식처럼 표현 가능합니다.

$P_{s}(x)^{(i)}=\frac{exp(g_{\theta_{s}}(x)^{(i)}/\tau_{s})}{\sum_{k=1}^{K}exp(g_{\theta_{s}}(x)^{(i)}/\tau_{s})}$

$P_{t}(x)^{(i)}=\frac{exp(g_{\theta_{t}}(x)^{(i)}/\tau_{t})}{\sum_{k=1}^{K}exp(g_{\theta_{t}}(x)^{(i)}/\tau_{t})}$

DINO은 teacher network($g_{\theta_{t}}$)은 주어진 것처럼 생각하여(no label에서 teacher model을 만들 수 없습니다. no label임에도 teacher model이 주어진것처럼 하는 이유는 아래에서 설명), teacher network의 결과분포와 student network의 결과 분포를 유사하게 만들도록합니다. 식으로는 아래와 같이 표현합니다. 즉, student 모델을 학습하도록 조절하는 것입니다.

$min_{\theta_{s}}H(P_{t}(x), P_{s}(x))$, where  $H(a,b)=-alog(b)$ (2)

2. objective function 및 data augmentation 방법

DINO은 student모델은 국소적인 이미지만 학습하고, teacher 모델은 전역적인 이미지를 학습해서, 국소적인 이미지만 보더라도 전역을 예상할 수 있게끔 학습을 유도합니다. 좀 더 자세히는, DINO방법으로 자기 지도 학습시에는 이미지를 여러 방법에 따라 증강시키는데요(본문내에서는 view라고 표현). 이 증강의 방법을 2가지로 분류합니다. 한 이미지로 부터 아래의 증강된 이미지를 만듭니다(view)

• global views: $x_{1}^{g}, x_{2}^{g} $  -> teacher model에만 학습
• local views: 여러개의 더 작은 패치(smaller resolution) -> student model에만 학습

주의할 것은 global view라고 하나의 이미의 전체를 쓰는 것이 아니라, 일부 영역(50%이상)의 영역을 쓰는 것을 의미합니다. 반면 local view은 50%미만의 픽셀만 넣은 것입니다.

이를 "local-to-global" correspondences라고 합니다. 이에 대한 목적함수는 아래와 같습니다.

$min_{\theta_{s}}\sum_{x\in\{x_{1}^{g},x_{2}^{g}\}}\sum_{~x'\in V,~ x'!=x} H(P_{t}(x),P_{s}(x'))$ (3)

• $V$: 모든 증강된 이미지의 집합(global view + local view)을 의미합니다.
• $x'$: $V$의 원소인, 하나의 증강된 이미지를 의미합니다. 단 $ x'!=x $의 조건식이 있으니, global view은 아니어야합니다.
• $P_{t}(x)$: global view 이미지를 입력으로 받은 teacher 모델이 반환한 확률분포입니다.
• $P_{s}(x')$: local view 이미지를 입력으로 받은 student모델이 반환한 확률분포입니다.
• $min_{\theta_{s}}$: student모델의 파라미터를 최적화해서 global view을 입력으로한 결과를 유사하게 만듭니다.

3. Teacher network의 학습

지식증류를 하려면 결국에서는, 학습이 완료된 모델인 teacher model ($g_{\theta_{t}}$)가 있어야합니다. teacher model이 있을리 없죠. 그렇게 각 iteration을 진행하면서, 이전 iteration의 student model을 teacher model로 활용하려고합니다 (지식증류를 no label로 쓰기위한 기술적인 하이라이트입니다.). 이때, teacher model은 지수평활(exponential moving average, EMA)을 이용하여 다음과 같이 학습합니다.

$\theta_{t}\leftarrow \lambda \theta_{t} +(1-\lambda)\theta_{s}$, where $\lambda$ cosine schedule from 0.996 to 1 

즉, student model parameter의 일부 영향과, teacher model의 parameters 일부을 조합하여 teacher model로 화용하겠다는 것입니다. 이걸 momentum encoder라고 하고 MoCO라는 contrastive learning 방법에서 사용되었던 방법입니다.

4. Avoiding collapse

추가로, 자기지도학습을 하는 모델들은 features collapse라는 모델의 특징값이 한쪽에만 쏠리거거나, 하나의값으로만 내뱉어져서, 다른 차원들의 값이 없는 경우가 발생하는데, centering과 sharpening(temperature scaling)을 이용하여 이를 해결할 수 있습니다. centering은 teacher model과 student model이 결과값이 균등분포로 나오는것막을 수 있습니다. 예를 들어, student model이 $p_{t}(x)$가 1.0이 한 벡터의 원소, 나머지는 0이라면 mode collapse가 발생할 수 있습니다. 내가 원하는 벡터의 차원이 N개인데, 1개의 벡터의 원소로만 변화가 지배되는 것입니다. 그렇기에 centering과 sharpening을 진행합니다. 

• Centering은 배치의 효과를 조금 줄여, 다양한 차원으로 학습되게끔합니다. 단점은 균등분포로 나올수도 있습니다. centering할때의 중심값 (c)은 아래와 같이 계산합니다 (식 4).

$c \leftarrow mc  +  (1-m)\frac{1}{B}\sum_{i=1}^{B}g_{\theta_{t}}(x_{i})$

• sharpening: 모델의 출력값의 분포가, 균등분포로 나오게 하는 것을 방지합니다. 즉, 한 차원에 학습이 될 수 있도록 합니다. 단점은 한 차원으로만 학습될 수도 있습니다 (centering과 반대)

요약

- 이미지 분류, 언어모델, 번역, 등의 다양한 문제에서의 이 방법론을 적용하여 해소됨을 보임.

사전지식(Preliminary)

방법론(method)

실험으로는 이미지 분류를 진행했고 MNIST에서는 오차율이 약간 크게나왔습니다. (Table 1). 하지만 그레디언트의 크기자체는 다른 방법론보다 작아진 것을 볼 수 있는데요.이는 더 빨리 수렴했음을 의미합니다.(FIgure 1)

요약

일반적으로 딥러닝이 텍스트나, 이미지 데이터셋에서의 고성능을 보이지만, 정형데이터(Tabular dataset)에서 성능이 우월한지는 잘 밝혀지지 않았습니다. 오히려 안좋은 경우도 있습니다. 이 논문은 실제로 그런지 딥러닝과 트리기반모델(RF / XGBoost)을 비교했고, 뉴럴넷(NN)이 성능이 그렇지 좋지 못하였다는 실험결과를 보여줍니다. 그리고, 이 이유에 대해서는 아래와 같이 설명합니다.

1. 정보량이 별로 없는 특징값에 대해서도 강건하다는 것(robust)
2. 데이터 방향(orientation을 유지해서) 학습이 잘 되도록 한다는 것
3. 비정형적인 함수도 쉽게 학습이 된다는 것입니다(딱딱 끊기는 함수도 학습이 잘됨).

Preliminary

• Inductive bias: 훈련되어지지 않은 입력에 출력을 예측하는 것. 학습을 한적이 없지만, 그간 보아왔던(학습했던)데이터를 이용하여(=귀납적 추론), 알고리즘이 예측하도록하는 가정입니다. 예를 들어, CNN은 Locality & Translational invariance, RNN은 Sequntial & temporal invariant, GNN은 permutational invariant 입니다.

도입

트리기반 모델은 대체로, 인공신경망보다 정형데이터에서 많이 성능의 우월함을 보였습니다. 아쉽지만, 이렇게 좋은 트리 기반모델은 미분이 불가능하기 때문에, 딥러닝과 혼합하여 사용하기 어렵습니다. 이 논문은 왜 트리기반 모델이 정형데이터에서 딥러닝 보다 우월한지를 보여주는 논문입니다.

방법론: 45개의 데이터셋에서, 딥러닝모델과 Tree기반 모델의 비교

OpenML에서 총 45개의 데이터셋을 만들었습니다. 이 데이터셋은 다음과 같은 선정기준으로 뽑혔습니다.

• Heterogenous columns: 컬럼이 매우 이질적일 것.
• Not high demiensional: 컬럼수가 행수에 비해서 1/10미만일것
• Undocumented dataset: 너무 정보가 없는 경우는 제외.
• IID: 이전 데이터가 직전데이터의 예측에 연관된 경우(예, 타임시리즈 제외)
• Realworld data: 합성데이터 아닐 것 6. Not too small: 너무 적지 않을 것 (특징값 <4 , 행수 <3,000)
• Not too easy: linear만해도 오차율 5%미만인경우는 제외
• Not deterministic: 변수 몇가지에 직접적으로 정해지지 않을 것.

모델은 아래와 같이 준비했습니다.

• MLP
• Resnet: MLP에 dropout, batch norm, skip connection을 추가한 형태입니다.
• FT-Transformer: 정형데이터에서 꽤 성능이 좋았던 네트워크
• SAINT: 이 네트워크도 정형데이터에서 성능이 좋았던 네트워크.

결과: Tree기반 모델이 더 고성능

• 벤치마크에서 분류든, 예측이든 트리기반모델이 더 고성능을 보였습니다. (Figure 1, Figure 2). Figure 1은 연속데이터만 있는 경우, Figure 2은 연속+카테고리데이터 둘다 있는 데이터입니다. 두 종류의 여러 데이터에서도 트리기반이 더 우수했습니다.

Dicussion:왜 Tree 모델이 Tabular데이터에서는 더좋은가? 3가지 이유

Discussion왜 더 좋을까? 크게 3가지 이유 때문에 좋다고 주장합니다.

• 뉴럴넷은 smooth solution 을 inductive bias을 갖기 때문에: 연구자들이 훈련데이터를 가우시안 커널을 이용하여 조금더 soothing하게 펼친 데이터를 만들고, 트리기반모델과 신경망모델을 비교했습니다. 신경망모델은 성능이 적게 떨어지는 반면, 트리기반모델은 급격히 떨어집니다 (Figure3). 이는 트리 기반모델이 예측시에 비선형 if, else등으로 자잘하게 쪼개는 반면, 뉴럴넷은 부드럽게 예측구분을 나눠주기 때문이라는 근거의 결과가 됩니다 (Figure 20).

•  인공신경망은 별로 정보량없는 데이터에대해 영향을 많이 받음: 정형데이터는 꽤 정보량없는 특징값이 많습니다. 랜덤포레트를 이용하여, Feature importance가 작은순으로 특징값을 제외시켜나가면서, GBT(Gradient boosting Tree)을 학습시켜나갔더니, 특징값이 꽤 많이 없어질때까지 좋은 성능을 냅니다 (Figure 4).인공신경망에서도 비슷한 패턴이보이긴합니다 (Figure 5). 하지만, 불필요한 정보를 특징값으로 넣는 비율이 클수록, 트리기반 모델보다 급격히 성능이 하락합니다 (Figure 6) 

• 인공신경망은 데이터를 rotation해도 비슷한 성능을 낸다고 합니다. [Andre Y. Ng, 2004]. 딥러닝자체가 rotationally invariant하다는 것인데, 데이터를 회전시켜도 학습이 잘된다는 말입니다. 즉, 메트릭스 중에 행 또는 열을 일부를 제거한다고해도 , 딥러닝알고리즘은 rotation에 맞게 학습한다는것입니다. Tabular 데이터는 실제로 돌리면 다른 데이터인데, 인공신경망은 학습을 이렇게 해왔기 때문에, 성능이 감소한다는 것입니다. 실제로 데이터를 돌려서 학습시켜도 다른 모델에 비해서 성능이 하락하지 않습니다 (Figure 6).

요약

DERT(Detection TRansofmer, 2020)은 객체검출(=Object detection)을 시항 할 때, 복수의 객체를 동시에(=페러렐하게) 예측하는 방법론을 고안한 모델입니다. DERT은 모델이 고정되어 있는 것이 아닌, 하나의 파이프라인으로 동작할 수 있고, 이 파이프라인에서는 NMS와 같은 후처리 공정이 들어가지 않게 고안된 파이프라인이라는 점이 특징입니다. 이 DERT은 Anchor free로 동작하고, 복수의 오브젝트를 예측하고, 각각의 실제 객체에 할당할 수 있도록 하도록 고안한 손실함수(Set-based global loss)을 이용하여 학습합니다.

사전 개념(Preliminary): Anchor-free, Set prediction

1. Anchor base vs Anchor free: 앵커는 이미 정의된 오브젝트의 중앙점 또는 박스를 의미합니다. 영어로는 Pre-defined bounding box라고도 합니다. 이를 이용하여 예측을 하는 경우, Anchor based object dection이라고 합니다. 예를 들어, 아래의 그림과 같이 파란색이 앵커라고하면,  사실 이런 파란색 앵커들이 훨씬 이미지에 많습니다. 그 다음에 가장  IOU가 높은 앵커를 찾고, 이 앵커를 조정하여 객체인식을 하는 방식입니다. 아래의 그림(Figure 1의 좌측 그림)은 여러 앵커중에, IOU가 높은 앵커를 선택하고, 이 앵커를 조정하여 ground truth을 조정하는 방식입니다. [1], [2]. 반면 Anchor free 은 이러한 사전정의된 박스없이, 오브젝트의 중앙점, 가로, 세로를 바로 예측하는 접근 방법론을 의미합니다.

2. Set prediction: 복수의 객체를 동시에 예측하는 것을 의미합니다. 객체를 하나하나 예측하는 방법과 대비되는 개념입니다.

Introduction (도입부): 여태까지는 Set prediction을 할 때, 후처리 성능의 의존적이 었음 => 후처리 없애고, End-to-End로 예측하는 모델을 만들어봄

Set prediction이 없던 것은 아니었습니다. 다만, 여태까지는 Set prediction을 간접적인 방법으로 예측 또는 분류를 하고 있었는데, 이러한 방법들은 오브젝트에 바운딩박스가 여러 개가 예측될 때, 후처리하는 방식에 성능이 영향을 많이 받았습니다. 본 모델은 이러한 후처리 방식을 없애고 End-to-End로 이미지를 입력받아, 객체검출을 하는 방식의 파이프라인입니다. 파이프라인이라 한 것은 이 모델에 백본(backbone)으로 쓰이는 모델들을 충분히 변경하며 다양한 아류들을 만들어 낼 수 있기 때문입니다. 

Method: 1) 백본으로 이미지 특징값을 뽑아, Transformer 전달하여 이미지의 객체를 예측, 2) 오브젝트와 실제오브젝트를 매칭하기 위한 Bipartite matching

아래는 DERT가 Set predcition을 진행하는 과정의 전체적인 파이프라인을 보여줍니다. 한 이미지가 들어오면, Pretrained model(본문에서는 Backbone 등으로 표현)모델로 추론을 합니다. 그렇게 얻어진 이미지 특징값들을 Transformer에 전달합니다. 이 transformer 내의 decoder에서 반환되는 예측치가 오브젝트의 예측치로 생각하는 것입니다.

위의 그림을 보면, 크게 1) Backbond, 2) encoder, 3)decoder, 4) Feedforward network(prediction)으로 구성됩니다.

1. Backbone: CNN(convolution neural network)으로 이미지의 특징값을 압축합니다. 보통 3채널의 이미지가 들어오면, CNN을 통과시킨다음에, feature 채널수가 2,048개, 가로, 세로는 원래 H/32, W/32만큼으로 축소하여 전달합니다.

2. Transformer encoder: 1x1 CNN을 이용해서 2,048의 특징값채널을 d채널로 까지 압축시킵니다. 그렇게 만들어낸 특징은 z0입니다. (d,H,W)의 차원을 갖습니다. 이렇게보면, 이미지가 3 x H, W을 넣어서 d x H x W가 되었습니다. 이렇게 된 H, W은 각각 의미가 있습니다. 각 픽셀이 원래 위치하고 있는 위상들이 각각 의미가 있다는 의미입니다. 따라서, Positional encoding을 더합니다. 이는 Transformer에서 위상정보를 추가로 덫대어 학습시키기 위한 전략인데, 이미지에서도 마찬가지로 쓰일 수 있습니다. 트렌스포머 아키텍처는 입력의 순서에 상관이 없는 (Permuational invariant)하기 떄문에, 포지셔널 인코딩을 더한다라고 생각하시면 됩니다. 

3. Tansformer decoder: 디코더는 인코더의 출력과, 오브젝트 쿼리(Object queries), 포지셔널 인코딩을 입력으로 받습니다. 오브젝트쿼리가 좀 생소한데, 0,0,0,0값을 넣는것은 아니고, N개의 오브젝트를 무조건 반환한다고 했듯이, N x 임베딩(d)의 차원을 가진 traininable parameter에 해당합니다. 이를 입력 값으로 받아, 멀티헤드어텐션을 이용하여 각 N개의 상호작용을 함게 학습합니다. 이전 Transformer와의 차이점도 있는데, 주요 차이점은 원래 Transformer은 반환되는 값을 다시 Transformer decoder에 넣는다는 점인데, 본 DERT은 그렇지 않습니다.  (*쿼리 오브젝트는 Embedding 레이어의 weight을 사용하여 구현합니다.)

4. FNN(feed forward networks): 마지막레이어에 해당됩니다. Fully connected layer 3개와 각각 ReLU을 중첩하여 사용합니다. 각각은 아래의 그림과 같이 Class 라벨예측, Bounding box예측에 사용됩니다.

Transformer을 사용하는 이유? 이 파이프라인은 Transformer을 썼는데, Self-attention을 모든 Sequence에 대해서 NxN으로 계산하여, 상호작용을 다 계산할 수 있듯(all pairwise interaction) 이미지에서도 각 객체의 예측치가 중복되지 않을 것이다라는 예상을 하고 Transormer을 사용하는 것입니다. 저자들도 이 점을 방점으로찍습니다.

DERT의 가장 중요한 점은 1) set predition loss을 이용해서, 학습당시에 예측치의 객체가 실측치의 객체에 중복할당되지 않도록 유도하는 것이고, 2) 하나의 파이프라인으로 오브젝트끼리 관계를 학습해서, 한번에 오브젝트를 예측하는 것입니다. 아래와 같이 정확한 기술사항을 작성해봤습니다.리 정의되어야하는 것은 N입니다. N은 예측할 오브젝트의 개수. DERT은 어떤이미지가 주어지더라도 N개의 오브젝트를 반환합니다. 다만 N개 중에 confidence가 낮은 것만 제거하면 됩니다. 통상, 예측하고자하는 오브젝트보다 큰 숫자를 설정하면 됩니다.

Bipartite matching cost

- 필요성: 위의 사항은 한 문제를 야기하는데, 예측하는 오브젝트의 개수가 무조건 N개만 반환되고, 실제 오브젝트가 이보다 작은 K개라면, 중복이 될 수도 있고, 남는 예측치는 어떻게 할 것인가에 관한 문제입니다. 이를 해결하기위해서 Bipartite matching cost을 정의합니다.

Notations:

• y: ground truth 오브젝트의 집합. 이 집합이 N보다 작으면 패딩($\phi$ = 오브젝트가 없음을 의미)할 수 있음
• $\hat{y}$: 모델이 예측하는 N개의 오브젝트의 집합

다시 식을 보면, 앞에 $\sigma$ 은 예측치에 대한 순열이며, N개니까 N!만큼 순서가 의미가있는 조합이 생깁니다. 가장 이상적인 예측치는 아래 그림과 같습니다. 각 원은 실제 벡터입니다. 단순히 벡터라고 생각하지않고, 모델이 예측한 예측치1이 실측치1에 상응하게되면, 둘의 차이가 가장 줄고, 예측치K이후부터는 모든 값이 0인 경우가 오차가 가장 적을 것입니다. 이러한 조합을 여러번 계산하는 이유는 Transformer에서 반환되는 오브젝트의 순서가 의미가 없기 때문입니다. 이 의미없는 오브젝트의 예측에서, 실측치에 하나씩 상응시키기위해 이러한 작업을 합니다. 이 작업은 앞서 경우의수가 N!이나 된다고 했습니다. 컴퓨터로도 계산하기 너무 많은 양이지만, 다행스럽게 헝가리안 알고리즘(Hungarian algorithm)을 이용하면 계산식의 부담을 줄일 수 있습니다. 이 알고리즘은 본 포스팅에서 다루지 않습니다.

식은 위와 같습니다. L matching은 클레스라벨, 오브젝트의 중앙부, 폭, 높이가 얼마나 차이나는 지를 계산하는 것입니다. y 및 $\hat{y}$ 내의 원소에 해당하는  값들은 실제 튜플 또는 벡터로 표현해볼 수 있고, 총 값은 5개로 표현됩니다. $y_{1}=(c_{i}, b_{i})$. c은 라벨을 의미하며, b은 중심점의 x,y, 높,너이입니다. 그리고 L_match의 앞에텀은 클레스가 맞았는지, L_box은 예측한 오브젝트가 실측의 오브젝트와 거리가 가까운지를 측정하는 손실함수입니다. 당연히 ground truth가 패딩된 것이 아닌 것에 대해서만 계산합니다. Bounding box loss은 GIOU을 사용합니다.

결과(Results)

첫 번째 결과로는 Faster R-CNN과 2개의 백본으로 실험한 DERT와의 성능비교입니다. 데이터셋은 COCO이며, DC은 Dilate C5입니다. DERT-DC5-R101의 아키텍처가 가장 우수한 성능으보이며, 파라미터수도 적었습니다.

2) 인코딩레이어가 어느정도 성능을 내고있음. 인코딩레이어의 수를 0으로하면, 추론속도를 빠르게할 수있지만 AP가 감소함.

3) 디코더 레이어도 어느정도 성능에 필요함: 디코딩레이어의 수를 없앨수록 성능이 저하됨.

4) 인코더부분의 self-Attention시각해보니, 각객의 개별인스턴스를 잘 예측하도록 Attention map이 구성되어있었다. = 각 인스턴스를 예츠갛도록 Attention이 동작하고있다는 것을 보여줍니다. 언어학에서 중요한 토큰을 보여주듯, 각 인스턴스에 대해서 토큰을 보여주는 형태라고 생각하면 됩니다.

5) GIOU + L1로스를 같이 쓰는 경우가 성능이 제일 좋았다는 결과입니다.

6) 디코어의 attention을보면 각각의 attention score(=attention weight * features)가 경계면에 가중치를 두는 것을 볼 수 있습니다. 즉 바운딩박스를 만들기에 중요한 경계를 보고잇다라고 주장하는 근거입니다.

7) 각각의 예측하고자하는 오브젝트쿼리에 따라서, 주로 보는 영역들이 다르다는 것을 보여주는 그림입니다. 해석: 녹색점은 각 예측치에 해당하는 점입니다. 작은 점은 매우 넓은 분포를 가지고있습니다. 반면, 빨간점은 가로로 긴 박스의 예측치의 중앙부입니다. 가로로 길기 때문에, 이미지내에서는 보통 중앙부에 있을 것입니다. 각 예측치의 크기에따라 어느부분을 중점적으로 관찰하는지에 대한 시각화라고 볼 수있습니다.

참조(References)

[1] Wang, C., Luo, Z., Lian, S., & Li, S. (2018, August). Anchor free network for multi-scale face detection. In 2018 24th International Conference on Pattern Recognition (ICPR) (pp. 1554-1559). IEEE.

[2] https://learnopencv.com/centernet-anchor-free-object-detection-explained/

요약

CenterNet은 기존의 Two stage detection방법(=한 객체에 대해서 여러 bounding box을 찾고, bounding box이 겹치는 영역을 줄이는 방법)이 비효율적인 것에 Motivaiton이 있습니다. 따라서, CenterNet은 효율적은 예측을 위해서 한 객체에는 하나의 Anchor(=center point, keypoint)만 있다고 가정하고, 이를 예측하는 문제로 바꿉니다. 일단 Anchor 을 찾고난 다음, 문제가 3D size, pose estimation이면 Anchor로부터 사이즈가 얼마인지 등을 추가로 예측하는 문제를 추가로 도입합니다. 모델 구조는 1) Heatmap: 각 객체의  Centerpoint 예측하는 출력층, 2) offset: Heatmap을 만드는 단계에서 Anchor와 원래사이즈에서의 Anchor을 보정하기위한 출력층, 3) size 예측: 각 객체의 Centerpoint으로부터, 객체의 사이즈를 예측하는 출력층으로 구성되어있습니다. [1] 

Motivation (introduction): Two stage detection방법에 제한이 있어,  One stage dection으로

현재 컴퓨터 비전에서 쓰는 대부분의 개체인식(Object detection)은 각 개체에 bounding box로 표현하는 것입니다. 보통 하나의 bounding box로 표현하기보다는 잠재적으로 될만한 bounding box을 다 찾습니다. 이 과정을 거치고나면, 하나의 객체에는 여러 bounding box가 생깁니다. 따라서, 최적의 bounding box(개체와 가장 근접하도록 작은 사이즈의 bounding box만 남김)을 만드는 작업을 합니다. 이러한 방법은 "Two stage dectecor"라고 합니다. 계산을 여러 번 하게되는 작업들을 아래와 같이 진행합니다 (Figure 3).

• recompute image feature for each potential box: 잠재적으로 개체가 될만한 박스들을 다 계산하여 그립니다.
• then, classify those feature: 이 박스들이 background일지 object일지 분류를합니다.
• Post-processing (Non maximal supression): 최적의 박스만 남기는 작업을 진행합니다. bounding box의 IoU값을 계산하여 한 개체에 겹치는 부분이 있으면 해당 내용만 씁니다. 특히 이러한 후처리는 미분도, 학습도 어려워서 end-to-ent 모델에 담기가 어렵습니다. 

그래서 나온것이 "One stage detection"입니다. 말 그대로 위의 단계를 하지않고, 하나의 단계로만 진행합니다. 이 단계는 가능한 하나의 bounding box을 만드는 것입니다. 이 하나의 bounding box의 중심을 anchor라고도 부릅니다. 일단 각 개체에 대해서 Anchor을 찾고나면, bounding box을 어디까지 그려야할지(size), 3D extent, orientation, post등은 중심점으로 부터 다 예측하겠다는 것입니다. 각 개체에 Anchor 만 찾고나면, 나머지는 부수적으로 예측하여 얻어낼 수 있다는 것을 상정하고 만든 모델입니다.

CenterNet은 어떤 로직? (method) : Heatmap, Offeset, Sizes 을 예측하기위해서 end-to-end로모델을 결합

CenterNet은 단순히 CNN으로만 이뤄져 있습니다. 구성은 인코더-디코더로 되어있는데, 디코더가 3개로 되어있습니다. 우선, 문제의 정의를 아래와 같이합니다.

• 입력 이미지: $ I \in \mathbb{R}^{W\times H\times 3}$. 가로의 크기가 W, 세로의 크기가 H인 이미지가 입력으로 주어진다고 가정합니다. 
• 결과물 (heatmap): $\hat{Y} \in [0, 1]^{W/R \times H/R \times C}$. R은 stride, C은 키포인트 타입(클레스 타입)을 의미합니다. 즉 이미지가 STRIDE 떄문에 좀 작아지더라고 각 개체가 C클레스에 중심점이 될만한지 heamap을 찍는 것을 의미합니다. 예를 들어, C은 human pose 라면 관절 개수인 17개을 씁니다. stride인 R은 기본적으로 4을 씁니다. 그렇게되면 이미지가 작아지는(=downsampling)됩니다.  만일 예측치 $\hat{Y}_{x,y,c}=1$라면 keypoint을 의미합니다(=예측된 x좌표, y좌표에서 c클레스일 확률이 1이라면 그 부분이 중심점일 것이다) 반대로 0이라면 배경을 의미합니다(Figure 1).

각 디코더의 역할을 아래와 같이 기술합니다.

1. Heatmap 예측을 위한 decoder: CNN은 heatmap이라는 것을만드는데, heatmap에서의 중앙부가 개체의 중심부가 되도록 예측합니다. 즉 개체가 3개라면 가장 높은 점수가 3개(=본문 내 피크)가 있어야하는 것입니다. 그리고 각 이미지의 피크를 이용하여 bounding box의 가로, 세로도 예측합니다. 그리고 keypoint을 예측하는 과정에서 Stacked hourglass, up-convolutional residula network(ResNet0, deep layer aggregation (DLA)을 dencoder-decoder로 묶어서 사용합니다.

C 클레스가 될만한, heatmap의 정답은 [x, y]좌표로 2차원의 데이터로 표현할 수 있을 것입니다. 원래 이미지 사이즈를 heatmap에 맞추어야합니다. 이 과정을 위해서 원좌표 [x.y]을 아래와 같이 R로 나누어 floor만 씁니다. 예를들어 중심점의 좌표가 512, 512을 4로 나눴다면 딱 나눠떨어져서 128, 128이되겠지만, 중심점의 좌표가 총 512,512이미지의 중심점의 좌표가 111,111, R=4이라면 [27, 27] (27.75에서 0.75버림)으로 만든다는 것입니다. 

$\tilde{p}\ = \left \lfloor \frac{p}{R} \right \rfloor$ 

이렇게 각 클레스 C에 맞춰 라벨을 heatmap에 맞춰 만듭니다. $Y \in [0, 1]^{\frac{W}{R}\times\frac{H}{R}\times{C}}$

그리고, 히트맵에 가우시안 커널을 적용하는데, 이는 keypoint가 단일의 점 [x,y]인 것에 비해서 예측치점이 $\hat{x}, \hat{y}$이기 때문에, 딱 하나의 점으로는 표현하자면 너무 예측이 어렵기에, ground truth keypoint주변으로 예측치가 어느정도 맞으면 가만할 수 있게끔 뿌려주는 역할을합니다. 가우시안 커널의 공식은 다음과 같습니다. 아래의 가우시안 커널에서 $\sigma^{2}_{p}$은 오브젝트 사이즈에 따라서 달라질 수 있다고합니다.

$Y_{x,y,z}=exp(-\frac{(x-\tilde{p_{x}})^{2} + (y-\tilde{p_{y}})^{2}}{2\sigma^{2}_{p}})$

정리하면, 예측할 heatmap은 STRIDE R이 적용된 리사이즈된 heatmap($\hat{Y} \in [0, 1]^{W/R \times H/R \times C}$), 예측치도 같은 사이즈의 가우시안 커널이 적용된 이미지($Y \in [0, 1]^{\frac{W}{R}\times\frac{H}{R}\times{C}}$)입니다. 그럼 로스만 적용하면됩니다.

로스는 아래의 (식 1)과 같이 작성합니다. Focal loss을 적용합니다. 흔히 focal loss은 클레스불균형이 심할때 사용합니다. 예를 들어, 보험사기자, 신용사기자처럼 다수의 정상적인 사용자가 있고, 가끔 발생할 수 있는 사기의심자를 한 둘을 맞춰야할 때, 이 사기의심자를 틀린 경우에 많은 패널티를 주기위해서 제곱항을주는 방식입니다 [2].

2. Discretization error 보정: Local offset

- 위의 예시와 같이 keypoint가 STRIDE (R)로 나눴을 때 나눠떨어지지 않는 경우, 약간의 오차가 발생했습니다(예, 111,111, R=4이라면 [27, 27] (27.75에서 0.75버림)). 이 에러를 보정하기위해서  Local offset이라는 개념을 만듭니다. 오프셋의 정의는 아래와 같습니다.

$\hat{O} \in \mathbb{R}^{\frac{W}{R}\times \frac{H}{R}\times 2}$

O은 예측해야할 좌표를 의미하며, 원본이미지에서 STRIDE을 주어 리사이즈된(=downsampling)이미지에서 단 2개의  채널의 값만 가집니다. 그리고 원래 중심좌표 p와 최대한 떨어지지 않게 만들기위해서 아래와 같이 L1 loss을 주어 학습합니다.

3. 오브젝트의 사이즈 예측: size

오브젝트의 사이즈는 2개의좌표만 알면됩니다. 좌상단, 우하단만 알면, bounding box을 그릴 수 있기 때문입니다 (Figure 3.). 따라서, 좌표2개를 아래와 같이 정의합니다. k은 카테고리를 의미합니다. 

그리고 더 중요한 것은 keypoint 을 예측하고, 오브젝트의 사이즈를 구해야하기 때문에, kepoint와 오브젝트의 관계식을 얻을 수 있습니다.

$p_{k} = (\frac{x_{1}^{k} + x_{1}^{k}}{2}, \frac{y_{1}^{k} + y_{1}^{k}}{2})$

그리고, 오브젝트 사이즈는 각 x좌표, y좌표의차이만 구하면됩니다. 

$s_{k} = (x_{2}^{k} - x_{1}^{k}, y_{2}^{k} - y_{1}^{k})$

각 오브젝트가 어떤 클레스가 될지에 따라서 k가 달라질 수 있다는 것입니다. 하지만, 이 예측치를 계산하는데는 연산이 오래걸려서 그냥 단일의 개체의 사이즈로만 판단하도록 변경합니다. 그래서 사이즈을 의미하는 값의 차원이 다음과 같이 바뀝니다. $\hat{S} \in \mathbb{R}^{\frac{W}{R}\times\frac{H}{R}\times2}$. 

그리고 아래와 같은 L1 로스를 줍니다. 실제 bounding box의 x,y, 가 중심점일때의 가로,세로의 길이를 예측하는 문제로 정의하는 것입니다.

그리고, 이를 joint learning하기위해서 모든 로스를 다음과 같이 합칩니다.

Anchor로부터 Bounding box예측하기

bounding box예측은 heatmap과 offset, size prediciton을 다 이용하면됩니다.

1. 일단 Anchor을 찾습니다. Anchor가 될만한것은 Heatmap에서 비교적 높은 값들을 찾으면 되거나, 일단 Anchor포인트로부터 8개의 좌표값들을 비교했을때 anchor보다 크거나 같은 경우 그부분을 중심점이라고 둡니다. 그리고 기본적으로 CenterNet은 100개의 피크값을 뽑아냅니다. 최대 오브젝트가 100개라고 보는것이죠. 몇 개인지까지는 예측을 못하니...

2. 그리고 각 예측치를 아래와 같이 구합니다. $\delta\hat{x}_{i}, \delta\hat{y}_{i} $은 offset prediction의 결과입니다. 예측한 heatmap의 좌표가 stride R때문에 실제 이미지에서 약간 이동될 수 있으니, 이를 보정하해줍니다. $\hat{w}_{i}, \hat{h}_{i}$은  사이즈 예측치입니다. 사이즈 예측을 위해서 중심점으로부터 좌측하단, 우측상단을 구하는 공식입니다. 총 4개의 좌표가 나옵니다. 이렇게 진행하면 딱히 non-maxima suppresion 또는 후처리가 필요가 없습니다.  그렇기에 one-stage detection입니다.

CenterNet 성능(Result)

Table 1은 backbone 모델을 어떤것을 쓰냐에따라서, 성능, 계산시간을 보여줍니다. AP(average precision)은 hourglass-104가 제일 성능이 좋았으나, 추론시간은 좀 오래걸린다. 초당 detection, 추론성능은 ResNet-18이 가장 빠릅니다. augmentation , flpi, multi-scale등을 추가로해볼 수 있는데 각각에 대한 성능표입니다.

Table 2: coco dataset에서 대부분 알려진 모델들에서의 성능입니다. 위의 5개의 모델은 two-stage, 아래 모델들은 one-stage입니다. two-stage중에서는 MaskRCNN이 빠르내요. AP성능이 가장좋은것은 TridentNet입니다. 반면 one-stage에서는 Hourglass을 쓴 CenterNet이내요.

정리

엄청 월등한 성능의 예측력 또는 엄청난 계산효율은 둘다 보여준 것은 아니지만, one-stage 모델중에서는 준수한 성능과 빠른 계산량을 보여주는 모델이라고 할 수 있을 것 같습니다. key point estimation을 3가지 방식으로 loss을 주어 최적화하는 모델이어서 꽤 좋은 모델링인 것 같습니다.

Reference:

[1] https://arxiv.org/pdf/1904.07850.pdf

[2] T.-Y. Lin, P. Goyal, R. Girshick, K. He, and P. Dollar. ´ Focal loss for dense object detection. ICCV, 2017.

요약

Swin Transformer은 ViT(Vision Transformer)와 유사하게 이미지를 패치로 나누어, 각 패치를 토큰처럼 취급하여Transfomer에 전달하는 모델이다. ViT와의 차이점은 ViT은 패치를 레이어를 통과시키면서, 고정크기로만 연산하는 것에 반해, Swin Transformer은 레이어를 지나면서 각 패치들을 합쳐서, 패치의 크기를 크게 만들고, Self-attention의 범위를 확장시키는데 그 차이가 있다(Figure 1).  추가적인 주요 특징으로는 윈도우 내 영역내 여러 패치가 존재할 때, Attention을 줄 영역을 윈도우 내로만 주는 것이 아니라, 이전 레이어의 Window영역을 가로지를 수 있게 다음 레이어에서 Attention할 영역의 Window을 매번 달리하는 것이 있다.

모델 설명: 1) 패치의 분리, 2) 패치의 임베딩, 3) 트렌스포머(어텐션 + Shifted window 파티셔닝), 4) 패치 병합과정의 연속

 

 

Window 영역 내에서만 attention을 적용하는 이유? 계산 복잡도 때문에...

한 윈도우에, 패치가 M x M이 있다고 가정하고, 일반적인 global self-attention을 하는 경우(1)와 widnow내 h x w개의 패치가 있는 경우를 계산복잡도를 구하면 아래와 같다. 중요한건 총 패치수인 h x w 수가 증가할 때, (1)의 식은 제곱으로 복잡도가 증가하지만, (2)의 식은 선형적으로 증하한다는 것이다. 윈도우 내에만 self attention하는 것이 컴퓨터비전에서 계산 복잡도를 낮출 수 있기 때문에, 이 방법을 저자들은 생각했다.

Shift window 을 구현하는 방법과 그 이유: 윈도우 내에서만 attention을 계산하면, 윈도우 넘어 연결성이 부족하기에... 윈도우 영역을 돌려가며(cyclic) 윈도우를 정의

Shift attention을 적용하기위해서 각 attention을 적용하는 단계를 본 논문에서는 module이라고 부른다. 논문에서는 2개의 모듈을 사용하는데, 첫번째는 왼쪽 상단에서 규칙적인 모양을 가진 window로 attention을 하고, 두 번째 모듈에서는 규칙적으로 분할된 윈도우에서 $(\lfloor\frac{M}{2}\rfloor,\lfloor\frac{M}{2}\rfloor)$ 만큼 떼어냏어 옮긴 후에 attention을 적용하는 것이다.

요약

ViT(Vision Transofmer)은 자연어처리(NLP)분야에서는 성공적인 성능을 보이는 트랜스포머(Transfomer)을 컴퓨터 비전까지 적용하기에는 제한이 있어왔는데, 이를 시도한 사례이다. 트랜스포머에서 각 토큰을 임베딩하여 샐프 어텐션(Self-attention)하는 것과 같이, 각 토큰을 이미지로 생각하여 트랜스포머의 인코딩에 전달하는 것이 이 모델의 골자이다.

모델 아키텍처 설명

본문에서는 별 다른 수정없이(with the fewest posiible modification) NLP에 쓰이던 트랜스포머를 영상처리에도 쓸 수 있다고 소개한다. 그림은 아래와 같다. 큰 순서는 다음과 같다. 1) 이미지를 잘게 자른 패치(Patch)로 N개의 패치를 만든다. 2) 패치를 Flatten하게 벡터화한다. 3) 벡터화한 이미지를 선형으로 결합하여 임베딩한다. 4) 임베딩된 결과에 클레스를 예측하는 클래스 토큰을 더해준다. 그리고, 포지셔널인 임베딩을 더해주어 패치의 위치를 더해 연산한다. 

자세히는 아래와 같다.

1) 이미지를 잘게 자른 패치(Patch)로 N개의 패치를 만든다. 원래 이미지가 H, W에 C채널 이미지인 것으로 고려한다. 컬러가 R, G, B였다면 C는 3이고, (1024, 1024)의 HD 이미지면 H는 1024, W은 1024값을 갖는다. 이런 이미지를 겹치지 않게(Not overlapping) N개의 정사각형 패치로 나눈다. 패치의 크기는 P이고, 개수는 N개이다. 이 때, 당연히, N개의 개수가 정수형이어야하고, 이미지와 맞아떨어져야하므로, $N=HW/P^{2}$으로 계산해야한다. C개의 채널을 가진 가로,세로가 각각 P인 패치를 그러면 N개를 생성하게 된다. 이렇게 만든 패치를 Flatten하여 원소의 길이가 $P*P*C$인 벡터를 얻는다. 이 벡터가 그리고 N개가 있다.

2) 각각의 패치를 각각 선형결합하여 임베딩시킨다: 각 패치를 선형결합시켜서(Dense layer을 통과시켜) 원소의 길이가 D인 벡터를 만든다. 이 단계가 $\mathbb{R}^{P^{2}C} \cdot \mathbb{R}^{P^{2} C \times D}->\mathbb{R}^{D}$에 해당한다. Linear projection을 해서 원소의 개수가 D개인 벡터를 만드는 단계이다.

3) 각 임베딩한 원소를 concat하고 포지션임베딩을 더해준다.: 각 원소의 길이가 D개인 벡터를 모두 concat해서 길게 만든다. 가령 N개의 패치에 D개의 원소의개수를 가진 벡터로 패치를 선형결합시킨 결과를 얻었다고하면 $N \times D$의 차원의 메트릭스를 얻게된다. 거기에 하나를 더해서 클레스임베딩($x_{class}$)을 정의하여(\mathbb{R}^{D}) 더 concat해준다. 결과적으로 $\mathbb{R}^{(N+1)\timesD}$의 메트릭스를 얻게된다. 거기에 포지셔넝임베딩을 하나 정의하여 함께 더해준다. 이 포지셔널 임베딩의 크기는 $\mathbb{R}^{(N+1)\timesD}$ 와 같다.

4) Self-attention 및 정규화 단계(NL): Transformer와 같이 진행한다. 이미 위의 단계에서 충분히 이미지를 임베딩하였으니 Transformer의 일반적인 연산과정을 거친다.

CNN과의 비교?

위의 연산과정을보면, ViT도 CNN과 유사한 방식을 사용한다. 패치사이즈인 16x16, stride 16의 convolution을 하는것과 같이 진행한다.

1. 가장 큰 차이는 CNN은 국소성(locality)가 있어서 각 특징값들을 픽셀 단위에서 특징값으로 잘 표현되는데, ViT은 Transformer이다보니, 이미지의 패치의 시리즈간의 연결성도 강조할 수 있다. 즉 좌측상단의 패치와 우측상단의 패치가 연관성을 이어줄 수 있다는 것이다. 이러한 분석방법이 더욱 픽셀단위의 중요성을 강조할 수 있다고 소개되어있다[1]. 
2. 하지만 CNN별로 데이터가 엄청나게 많지 않아도 잘 학습되는 반면, Vision Transformer은 꽤 많은 양의 데이터를 필요로한다. 
3. Inductive bias을 줄일 수 있다. CNN은 이미지를 다루기 위한 Inductive bias을 갖고있다. 가령 CNN은 학습해야하는 커널이 각 이미지영역을 훑고 지나가면서, 근소한 이미지 연관성이 크게 학습되도록 꾸며져있고(=이를  Locality(근접 픽셀끼리의 종속성)라 함). 또한, 패치가 여러 영역을 훑기 때문에, Translation Invariance(사물의 위치가 바뀌어도 사물을 인식)의 이 된다. 하지만, 이러한 CNN의 가정들(메커니즘 방식)보다 각 패치의 연관성을 글로벌하게 연관지어 학습하기 때문에 Inductive bias을 줄일 수 있다고 한다[2][3].

[1] https://en.wikipedia.org/wiki/Vision_transformer

[2] Raghu, Maithra; Unterthiner, Thomas; Kornblith, Simon; Zhang, Chiyuan; Dosovitskiy, Alexey (2021-08-19). "Do Vision Transformers See Like Convolutional Neural Networks?". arXiv:2108.08810.

[3] Coccomini, Davide (2021-07-24). "Vision Transformers or Convolutional Neural Networks? Both!". Towards Data Science.

[4] https://arxiv.org/pdf/2010.11929.pdf

요약

흔히, 딥러닝모델을 예측치에 대한 설명이 되지않아 블랙박스 모델이라고 한다. Influnence function은 특정 테스트 데이터포인트를 예측하는데 도움을 주었던, 도움을 주지 않았던 훈련데이터를 정량적으로 측정할 수 있는 방법이다. 즉, 훈련데이터에서 특정데이터가 빠진 경우, 테스트데이터를 예측하는데 어느정도 영향이 있었는지를 평가한다. 이를 쉽게 측정할 수 있는 방법은 모델에서 특정 데이터를 하나 뺴고, 다시 훈련(Re-training)하면 된다. 하지만 딥러닝 학습에는 너무 많은 자원이 소모되므로, 훈련후에 이를 influence function으로 추정하는 방법을 저자들은 고안을 했다.

Influence function 계산을 위한 가정

훈련데이터에 대한 정의를 다음과 같이 한다. 예를 들어, 이미지와 같이 입력값을 $z$라고 한다.

• 훈련데이터 포인트(개별 하나하나의 데이터)를 $z_{n}$라고 한다.
• 이 훈련 데이터 포인트에 개별 관측치는 입력값 x와 라벨y로 이루어져 다음과 같이 표기한다 $z_{i}=(x_{i}, y_{i})$
• 그리고, 모델의 학습된 파라미터를 $\theta$라고 한다.
• 주어진 파라미터한에서, 데이터포인트 z를 주었을 때의 loss 값을 $L(z,\theta)$ 라고한다.
• 훈련데이터 1부터 n개까지의 총합 로스를 emprical loss라고 정의한다 $1/n \sum_{i=1}^{n}L(z_{i},\theta)$
• 학습과정을 통해 얻어진 파라미터가 위의 empirical loss을 가장 줄일 수 있게 학습된 파라미터를 $\hat{\theta}=argmin_{\theta\in\Theta}1/n\sum_{i=1}^{n}L(z_{i}\theta)$

Influence function 의 종류

Influence functiond은 training point가 모델의 결과에 어떤 영향을 주었는지 이해하기위해서 3가지 방법론을 고안했다.
1. 해당 훈련데이터포인트가 없으면, 모델의 결과가 어떻게 변화하냐? (=가중치가 어떻게 바뀌어서 결과까지 바뀌게 되나?)
= 이 방법론은 loss가 얼마나 변화하냐로도 확인할 수 있다.
연구에서는 이를 up-weighing 또는, up,params이라는 표현으로 쓴다. up-weighting이라는 표현을 쓰는 이유는 특정 훈련데이터가 매우작은 $\epsilon$ 만큼 가중치를 둬서 계산된다고하면, 이 $epsilon$을 0으로 고려해서 계산하기 때문이다. 또는 이를 loss에 적용하면 "up,loss"라는 표현으로 기술한다.
2. 해당 훈련데이터포인트가 변경되면(perturnbing), 모델의 결과가 어떻게 변경되나?

Influence function 의 계산(up,loss)

아래의 계산식에서 좌측($I_{up,loss}(z,z_{test})$)은 예측값 $z_{test}$을 예측하는데있어, 특정 훈련데이터포인트 $z$가 얼마나 영향을 주었나(=loss을 얼마나 변화시켰나)를 의미한다. 마지막줄의 각 계산에 들어가는 원소는 다음 의미를 갖는다.

• $-\nabla_{\theta}L(z_{test},\hat{\theta})^{T}$: 특정 테스트 z포인트를 넣었을 때, 나오는 loss을 학습파라미터로 미분한 값이다. 즉
• $H_{\hat{\theta}}^{-1}$: 학습된 파라미터의 hessian의 inversed matrix이다.
• $\nabla_{\theta}L(z,\hat{\theta})^{T}$: 특정 훈련데이터포인트 z를 넣었을 때, 나오는 loss을 학습파라미터로 미분한 값이다.

위의 세 값을 다 계산하여 곱해주기만하면 특정 훈련데이터z가 테스트데이트를 예측하는데 로스를 얼마나 변화시켰는지 파악할 수 있다.

여기서 문제는 해시안 메트릭스($H_{\hat{\theta}}^{-1}$)를 계산하는 것이 매우 오래걸린다는 것이다. 따라서 저자들은 아래와 같이 추정방법으로 해시안메트릭스의 역행열을 구한다.

Influence function 계산의 어려움(비용)

Influence function 계산이 어려운 부분(계산비용이 큰 이유) 2부분 때문이다.

1. 해시안 메트릭스의 역행렬을 구해야함: 해시안 메트릭스는 각 행렬에 파라미터의 개수가 p개라고 하면, $O(np^{2}+p^{3})$의 계산량이 든다는 것이다.
2. 훈련 데이터 포인트에 대해서 모든 데이터포인트를 다 찾아야한다는 것. 예측에 도움이 안되는 데이터포인트를 찾으려면 훈련데이터가 n개면 n개의 데이터포인트를 찾아야한다.

다행이도 첫 번째 문제인 해시안 메트릭스이 역행렬을 그하는 것은 잘 연구가 되어있어서 해결할 수 있다. 명시적으로 해시안의 역행렬을 구하는것 대신에 해시안 역행렬과 손실값을 곱한 Heissan-vector product(HPV) 을  구하는 것이다



Inversed hessian matrix 구하기(HPV구하기, 중요)

조금더 구체적으로는 저자들은 해시안메트릭스의 역행열을 구하기보다는, 해시안메트릭스의 역행렬과 loss에 해당하는 vector($\nabla_{\theta}L(z_{test},\hat{\theta})^{T}$)을 한번에 구하는 방법을 소개한다. 이는 책 또는 github코드에서 주로 Inversed hessian vector product (inversed HVP)라고 불린다.

이를 구하는 2가지 방법이 있다.

1. Conjugate gradient (CG)
2. Stocahstic estimtation

저자들은 주로 Stocahstic estimation 방법으로 이를 해결하려고 한다. 

다음의 서술은 위의 HVP을 구하는 방법에 관한 것이다.

1. 훈련 데이터 포인트 전체 n개에서 매번 t개만을 샘플링 한다.
2. HVP의 초기값은 v을 이용한다 (이 때, v은 $\nabla_{\theta}L(z_{test}, \hat{\theta})^{T}$을 사용한다. 테스트세트에 대한 로스값의 gradient이다.)
3. $\tilde{H_{j}}^{-1}v=v+(I-\nabla_{\theta}^{2}L(z_{s_{j}, \hat{\theta}})\tilde{H}_{j-1}^{-1}v$ 을 계속한다.
4. 위의 과정(1-3)을 반복한다.

위와 과정을 충분히 반복하고, t을 충분히 크게 뽑는 경우 HVP값이 안정화되고 수렴된다고 한다. 이 방법이 CG방법보다 빠르다고 언급이 되어있다.

하이라이트 결과

Leave one out 방법과 유사하게 Influence function이 loss값의 변화를 추정한다.

개인적으로 아래의 Figure 2가 제일 중요해보인다. 훈련데이터를 하나 뻈을때(leave-one-out)의 방법과 Inlfuence function으로 예측한 예측값이 거의 정확하다면 선형을 이룰것이다. 아래의 그림은 이를 뒷받침하는 결과로 사용된다.

손실함수를 미분할 수 없는 경우도, 손실함수를 대략적으로 추정(Smooth approximation)  한 경우 추정할 수 있다.

아래의 결과는 Linear SVM을 이용하여 예측한 loss의 값과, 실제 retraining한 경우의 예측값을 보여주고 있다. Linear SVM 자체에서는 Hinge 값이 쓰이는데 (ReLU와 유사하게) 미분이 불가능하다. 따라서, 저자들은 0에서 미분불가능할 때 smooth하게 변경하기위해서 아래와 같이 smooth hinge라는 것을 만들어서 어느정도 추정한 값을 쓰고 있다($smooth ~hinge(s,t)=tlog(1+exp((1-s)/t)$). 즉 이 함수는 t가 0이되면 0이될수록 미분이 불가능한 hinge loss와 동일해진다. 이렇게 적용했을 때 결과가 (b)와 같다. 미분불가능한 함수를 미분 가능하게 조금 수정한다면, (b) 와 같이 t=0.001인 경우, t=0.1인 경우와 같이 어느정도 influence function이 데이터를 빼고 재학습한 것과 같이 추정이 가능하다는 것이다)

Influence function의 유즈케이스

아래는 influence function을 언제 쓰는지에 관한 것이다. 

1. 모델이 어떤 방식으로 행동하는지를 알 수 있다.: 아래의 그림 (Figure 4)은 SVM과 Inception(CNN기반)에서의 물고기 vs 개의 분류문제이다. 이 Figure 은 여러가지를 우리에게 알려준다.

1. 우리의 직관은 "SVM은 딱히 이미지의 위상정보을 이용하지 않으니, 이미지의 거리(L2 dist)가 클수록 분류에 도움이 안될 것"으로 생각할 수 있다. Figure 4을보면 x축이 Euclidean dist인데, 400이상인경우 influcen function의 크기가 0에 가까워지는 것을 볼 수 있다.
2. 녹색의 데이터포인트는 물고기의 학습데이터이다. 물고기를 예측하는데 있어, 물고기의 이미지만 도움을 주는 것으로 파악할 수 있다.
3. 반대로, Inception 은 딱히 위상정보가 아니어도, 이미지의 외형(contour)을 잘 학습하기 때문에, 거의 모든 이미지가 분류에 영향을 주는 것을 알 수 있다. 즉 물고기의 예측하는데 있어서, 일부 강아지 이미지가 도움을 줄 수 있다는 것이다.

요약

RandomForest 의 Feature importance은 여러가지가 있을 수 있지만 크게는 대표적으로 1) 불순도 기반 방식(Impurity based): tree을 나눌 때, 쓰이는 특징값으로 나눴을 때, 클레스가 잘 나뉘는 가 얼마나 변화하는지 측정하는 방식. 불순도의 변화가 크면 클수록 트리를 잘 나눴다는 것을 의미중요한 특징 값이라는 것, 2) 순열 기반 방식(Permutation based): 각 특징값을 데이터 포인터에 대해서 랜덤하게 순서를 바꿔서, 정확도가 떨어지는지 확인하는 방식. 정확도가 크게 떨어질 수록 중요한 특징값임을 가정하는 방식이 있다.

선행

랜덤포레스트는 이 포스팅에서 깊게 다루지는 않지만, 트리구조를 만들 때, 배깅(bagging) 중복을 포함해서 임의로 데이터를 N개씩 뽑고, Feature bagging (속성을 뽑을 때도 랜덤하게 K)만큼 뽑아서 각각의 트리를 만든다. 그렇게 만들어진 약한 분류기(Tree)을 여러개 만들고 분류모델이면 Voting하여 얻은 값을 반환한다.

Gini importance / Mean Decrease in Impurity (MDI)

이 방식은 Gini importance라고도 불리고, MDI라고도 불리는 방식이다. 의미하는 것은 모든 랜덤포레스트의 각각의 트리에서 해당 특징값으로 트리를 나눌 때, 감소한 불순도의 평균을 의미한다(For each feature we can collect how on average it decreases the impurity. The average over all trees in the forest is the measure of the feature importance[1]).

Gini impurity은 아래와같이 계산한다 (주의: Gini coefficient와 다른 내용이다).

$Gini impurity = 1 - Gini$

$Gini = p_{1}^{2}+p_{2}^{2}+...+p_{n}^{2}$

n은 데이터의 각 클레스를 의미한다. 가령 아래와 같이 주황색 데이터와, 파란색데이터를 구분하는 문제라면 n은 2가된다. 노드를 나누기전을 부모노드라고하면, 부모노드에서의 Gini은 파란색공이 5개중에 3개, 노란색이 5개중에 2개이므로 $Gini=(3/5)^{2}+(2/5)^{2}$가 된다. 따라서, Gini impurity은 $Gini impurity=1-(3/5)^{2}+(2/5)^{2}$이다. 그리고 나눈 후를보면, 좌측은 $Gini imputiry = 1- ((2/3)^{2}+(1/3)^{2}$. 우측은 $Gini imputiry = 1-((1/2)^{2}+(1/2)^{2})$ 이다. Gini impurity의 변화량이 얼마나 변화했는지를 파악하는 것이기 때문에, 다음과 같이 부모의 impurity - (자식노드의 imputiry의합)과 같이 계산한다.

$1-(3/5)^{2}+(2/5)^{2} - [(1- ((2/3)^{2}+(1/3)^{2}) - 1-((1/2)^{2}+(1/2)^{2})]$

위의 계산에서 중요한 것을 빠뜨렸는데 특징값 A에 대해서 위와 같은 과정을 진행했다고하면, 모든 노드 중에서 A을 이용한 분기에를 모든 트리에서 찾은다음에 평균낸 값이 Gini importance이다. 혹은, 어떤 방식에서는 나누려는 노드의 가중치를 곱해서 많이 나눴던 노드에서는 더 가중치를 주기도 한다.

아래의 그림을 보면 feature importances (MDI)라는 것이 표시되어있다. 이는 위의 과정(Gini importance)을 이용해서 각 노드를 나눴을때 불순도가 크게 변화하는 정도의 평균을 계산했다는 의미이다. (이 데이터셋은 타이타닛 데이터셋). 생존자와 사망자를 구분할 때, sex을 이용해서 구분했을 때, sex을 안썼을 때보다 평균적으로 더 트리구조가 깔끔하게 나뉘어져나갔다는 것을 의미한다. 

[1] https://mljar.com/blog/feature-importance-in-random-forest/#:~:text=Random%20Forest%20Built%2Din%20Feature%20Importance&text=It%20is%20a%20set%20of,sets%20with%20similars%20responses%20within.

Permutational importance / Mean Decrease in Accuracy (MDA)

Permutation importance은 트리를 만들때 사용되지 않았던 데이터들 OOB(Out of bagging, 랜덤포레스트의 각 트리를 만들 때, 랜덤으로 N개의 데이터를 중복을 포함하여 뽑는데, 그 때 사용되지 않았던 데이터들)을 이용하여, OOB인 데이터들에 대해서 해당 특징값을 랜덤하게 섞은후에 예측력을 비교한다.

아래와 같이 a,b,c,d,e,의 특징값을 가진 1,2,3,4,5번 데이터가 있다고하자. 모델을 빌딩할 때, 랜덤으로 뽑은 데이터가 1,3,5였고, 안타깝게 2,4번은 중복을 포함혀어 뽑았지만 뽑히지 않았던 데이터라고 하자. 

이 때, 특징값 a에 대해서 1,2,3,4,5번의 a특징값의 순서를 랜덤하게 바꿔버리고 원래 데이터셋으로 만든 모델과 성능을 비교한다. 성능차이가 크면 클수록 랜덤으로 돌리지 말았어야할 중요한 별수라는 것이다. 또는 2번과 4번의 데이터 또는 바꿔서 차를 계산해도 이론상 큰 차이는 안날 것이다. 이렇게 특징값a에 대해서, 순서변경 전후의 성능을 비교하고, b,c,d,e,f에 대해서도 비교하면 permutation feature importance가 계산된다.

아래와 같이 permuation importance을 계산하면 성별이 나온다. boxplot으로 나온 이유는 random forest의 각 tree에서의 틀린정도의 분포를 그렸기 때문이다. 해석은 다음과 같다. 테스트 세트에서 생존여부를 맞추는 정도는 sex을 랜덤하게 바꿀 경우 가장 많이 성능이 떨어졌다는 것을 의미한다. 각 트리별로 고려했을 때, 평균적으로 0.25정도 성능이 떨어졌음을 의미한다.반대로 random_num, age등은 어떤 tree에서는 빼나 안빼나 구별력차이가 없었던 것을 의미하기도 한다 (box plot에 0에 맞닿아있다 (이는 랜덤으로 뽑은 데이터셋이 운이 안좋게 구별을 못한 경우일 수도 어서 0이 나왔을 수도있다.