Learning to Learn

hamait.tistory.com/823

Paper

arxiv.org/abs/1904.05068

Code

github.com/lenscloth/RKD

Introduction

그동안의 knowledge distilation은 teacher model과 student model의 feature value를 point to point로 KL-divergence를 이용해 같아지도록 매칭시켰다. (softmax output , KL-divergence)

본 논문에서는 point-to-point matching이 아닌, feature같의 relationship을 distillation하는 방법을 제안한다. 

이는 아래 그림과 같다.

Relational knowledge distillation

논문에서 제안한 Relational knowledge distillation의 형태는 다음과 같다.

ψ는 feature vector간의 relation을 표현하는 함수이다. (relational potential function)

l은 둘간의 차이를 줄이는 loss function이다.

기존 distillation과 차이점은 아래와 같다.

본 논문에서는 relational potential function으로 distance-wise, angle-wise 2가지를 제안한다.

Distance-wise distillation loss

distance-wise potential function는 다음과 같다.

μ는 distance의 normalization factor로서 다음과 같이 정의된다.

(mini-batch에 있는 모든 pair들의 L2 distance의 평균)

normalization term은 teacher model의 distance의 scale과 student model의 distance의 scale을 맞추어주는 역할을 한다.

결과적으로 distance-wise distillation loss는 아래와 같이 정의된다.

Angle-wise distillation loss

Angle-wise potential function는 다음과 같다.

j image sample에 대한 embedding vector를 기준으로 i, k에 대해 angle을 계산한다.

loss function은 다음과 같다.

teature 모델과 student 모델의 embedding vector가 형성하는 각도를 같게 만들어준다.

Training with RKD

RKD는 여러형태로 적용될 수 있다. RKD만 단독으로 적용할 수도 있고, task-specific loss를 함께 사용하는 것도 가능하다. 

classification task의 경우 다음과 같이 표현될 수 있다.

Experiments

RKD에 대한 실험은 다음 3가지 task에 대해서 수행되었다.

: metric learning, classification, few-shot learning

용어는 다음과 같다.

RKD-D : distance-wise loss

RKD-A : angle-wise loss

RKD-DA : distance-wise, angle-wise together.

실험은 metric learning, classification, few-shot 3가지 분야에서 이루어졌다.

1) Metric learning

Metric learning은 유사한 이미지끼리는 가깝게 embedding하고, 다른 이미지끼리는 멀게 embedding되도록 obejective function을 정의하고 학습시키는 방식이다.

이러한 metric learning을 통해 학습된 embedding 모델은 image retrieval 방식으로 주로 평가된다. 

본 논문에서는 CUB-200-2011, Cars 196, Stanford Online Products에서 평가되었다.

evaluation metric으로는, recall@K가 사용되었다. 먼저 test image들을 모두 embedding 시킨다. 

그리고 각 test image들을 query로 사용하고 KNN 기법으로 query에 대한 이미지들을 retrieval한다.

(retrival할떄, query는 제외)

이때 query에 대해서 K개의 nearest neighbor중 같은 category의 image가 하나라도 포함되어 있으면

그 query에 대한 recall은 1이 된다. 즉 Recall@K는 모든 test set에 대해서 이 recall 값을 계산해서 평균값을 낸 것이다.

이때, loss는 Triplet loss를 사용하였다.

이때 최종 embedding vector에 대해서 l2 normalization을 수행한다. 

일반적으로 deep metric learning에서 embedding space를 제한하기 위해 l2 normalization은 많이 사용된다.

RKD는 teacher model과 student model의 final embedding ouput을 대상으로 적용된다.

이때, RKD의 경우 embedding space를 tripplet loss와 같이 normalization하지 않았으며, 

RKD-DA의 경우 RKD-D는 1, RKD-A는 2의 비율로 loss를 적용하였다.

RKD를 사용할 때, 추가적인 task loss(ex triplet loss)는 사용하지 않았다. 즉, teacher model의 embedding 정보를 통해서만 student model은 학습이 되었으며, 기존의 gt label은 student 모델을 학습하는데 사용되지 않았다.

self-distillation도 효과 있었다.

이때 self-distilation은 teacher model과 student model이 동일한 backbone network를 사용하였음을 의미하며,

generation은 distillation을 통해 생성된 student model을 다시 teacher model로 사용하여 distiallation을 다시 수행했다는 것을 의미한다. 

결과적으로 self-distillation을 한번만 했을때, 가장 효과가 좋았고, 그 이후로는 오히려 성능이 떨어지는 현상을 보였다.

또한 RKD는 특정 dataset에 특화되어 학습되는 경향을 보였다. (adaptation)

Cars 196이나 CUB-200-2011은 fine-grained dataset으로서, domain의 특징에 잘 맞추어서 학습되는 것이 중요하다.

RKD가 이러한 adaptation이 잘되는 학습방법임을 증명하기 위해서 Car196에 학습시킨 모델을 다른 dataset에 대해서 test해 보았다.

결과적으로 RKD-DA는 Cars196에 대한 성능이 좋은 반면에 다른 dataset에 대한 generalization 성능은 떨어지는 것을 확인할 수 있었다. 즉, 해당 데이터셋에 대한 discriminative한 feature를 더 잘 추출하는 경향이 있음을 알 수 있다. (왜?)

2) Image classification

classification에서는 기존에 사용되던 KD들과 성능을 비교하였다.

RKD 단독으로 사용했을 때는 오히려 HKD(Hinton's KD)가 더 높았으나, RKD와 다른 기존의 KD를 조합했을때, 모두 성능이 더 향상되었으며, 또한, 가장 높은 성능을 보였다. 

Paper

arxiv.org/abs/1910.05872

Code

github.com/hankook/SLA

Introduction

그동안의 self-supervised task를 이용한 방법은 multi-task learning의 형태가 많았다.

(Multi task learning은 아래 그림 참고) 

그러나 multi task learning 방식은 단순히 supervised 방식을 사용했을 때 보다 acc gain은 없다. 

그렇다면 어떻게 self-supervision을 fully supervised classfication task에 적용하는 것이 가장 좋은 방법일까? 

Contribution

먼저 multi task learning의 경우 primary network에 대해서 self-supervision task (transformation)에 대해서 invariant하게 만든다. 예를들어 Rotnet의 경우 rotation에 대해 invariant하게 만들어주는 방식이다.

그러나 이러한 invariance는 오히려 task에 대한 난이도 및 복잡도를 증가시킬 수 있다.

예를들어 {6 vs 9} 와 {bird vs bat} 같은 경우 회전때문에 오히여 두 클래스가 더 헷갈릴수도 있기 때문이다.

그리고 이러한 이유 때문에 오히려 multi-task learning이 성능이 더 저하되는 경우가 생긴다.

(아래 그림 baseline과 MT(Multi-Task) accuracy 비교)

이러한 문제를 해결하기 위해서, 저자들은 기존의 label과 self-supervision label을 조합한 joint distribution을 제안한다.

예를들어 cifar10 dataset과 Rotnet을 조합하는 경우 10 label * 4label (0, 90, 180, 270) 총 40 label이다. 

이렇게 하면 multi task learning의 경우 class에 대한 label 없이 Rotation에 해당하는 label을 맞추어야 하기 때문에 오히려 classificaition 성능이 떨어지는 상황이 발생하나, joint의 경우 각 input으로 들어오는 image가 어떤 class에 대한 정보를 rotation과 함께 부여하기 때문에 이러한 문제가 해결할 수 있다.

또한 아래 그림과 같이 특정 class에 대한 self-supervision prediction에 대한 결과들을 aggregation하여 앙상블 효과 또한 얻을 수 있다. 

본 논문에서는 self_supervision task로서 Rotation과 Color Permutation 방법을 사용했으며, fully-supervised, few-shot, imbalanced dataset에서 성능향상을 볼 수 있었다.

Self-supervised Label Augmentation

* notation

input :

label : (N은 class의 수)

cross entropy loss function:

softmax classifier :

embedding vector of x :

augmented sample using transformation t 

the embedding of the augmetnted sample x:

Aggregated inference

label을 joint하여 learning한 이후에 inference의 경우는 다음과 같이 한다.

class에 해당하는 self-supervision transformation의 logit을 모두 더한다.

그렇게 하면 class별 logit이 새롭게 산출되고 이를 softmax를 이용해서 prediction한다.

이러한 방식은 앙상블 방식으로 해석할 수 있는데, 

실제로 independent한 여러개의 모델을 앙상블 한 것 보다 더 높은 성능이 나왔다.

Self-distillation from aggregation

aggrregation이 성능향상에 큰 도움을 주기는 하지만, inference과정에서 기존의 label보다 훨씬 많은 label에 대한 

summation 계산과정이 있기 때문에, computation cost가 존재한다. 

이러한 inference과정에서 computational cost를 줄이기 위해서 본 논문에서는 self-distillation방법을 사용한다. 

그래서 aggregated된 knowledge

를 다른 classifier에 distillation한다.(그림참고)

즉 feature extractor에 n*m (label 개수 10*4)의 classifier와 n(label 개수 10) classifier 2개를 놓고, n*m classifier는 label을 통해 학습시키고 n classifier의 경우, distilation을 통해 학습시킨다.

그리고 inference 단계에서는 self-distilation을 통해 학습된 classifier를 이용해 inference한다.

최종적인 loss function은 다음과 같다.

Comparison with DA and MT

본 논문에서는 data-augmentation과 Self-supervised Multi-task learning이 유사한 성격을 지닌다고 주장하고 있다.

또한 rotation 기반으로 생각했을 때, unnecessary한 invariant 속성을 학습하기 때문에 오히려 성능이 떨어진다고 주장한다. 

이때, test에 대해서 DA와 MT가 낮은 것은 앞선 unnecessary한 부분을 invariant하게 만들기 때문이다.

MT가 train 및 test 모두 성능이 안좋은 이유는 optimization 자체가 hard하기 때문이라고 말하고 있다.

위의 그래프에 대한 성능은 아래와 같다.  

이때 DA가 Baseline보다도 성능이 낮은데, 둘의 차이는 rotation based augmentation이 있냐 없냐의 차이이다.

내 생각엔 Baseline에 다른 augmentation이 분명 포함되어 있을거라고 생각한다.

Imbalanced classification

Imbalanced classification에도 큰 성능향상을 보임 (왜?)

Paper

arxiv.org/abs/2011.00178

Introduction

대부분의 현재 classfication method들은 "What is a cat"에 집중한다. 그래서 cat의 가장 representative한 feature을 찾도록 학습한다.   본 논문에서는 "What is not a cat" 에 집중하는 학습방법을 사용한다. 그래서 non-cat data에 대한 새로운 representation Point를 찾도록 학습한다. 그리고 그것을 Reciprocal Point라고 명명한다.

그래서 본 논문에서 제안하는 method를 Reciprocal Point Learning (RPL) 이라고 한다. 

RPL은 open space risk를 줄이는 방법이다. 이때, open space란 다음과 같다.

(분모는 위의 그림 참고)

즉, embedding space에서  known data가 embedding되는 공간을 제외한 space를 open space라고 한다.

그리고 open space risk는 embedding space의 모든 공간 중에서 open space가 차지하는 비중이다.

RPL은 이 open space risk를 줄이기 위한 방법이다. 이때, known class에 대한 reciprocal point를 학습시킴으로서 open space risk를 줄일 수 있다.

상세한 과정은 다음과 같다. 

reciprocal point를  현재 학습하는  known class와 다른 extra-class를 이용해서 학습을 하고, input의 구분은 embedding feature와 reciprocal point의 차이를 이용해 구분한다.

학습과정에서는 reciprocal point를 이용해 all known class들이 reciprocal point에 push되고 pull되는 과정이 반복되게 된다. 

결과적으로 embedding space는 bounded range에 갇히게 된다.

이러한 방법을 통해 기존의 딥러닝 모델의 문제였던 unknown input에 대한 high confidcence가 나오는 문제를 boundary를 제한함으로써 해결할 수 있다.

이러한 방법으로 known sample만 traing stage때 사용할 수 있지만, reciprocal point를 이용해 known과 unknown을 분리할 수 있다.

Reciprocal Point Learning

1) Preliminaries

Open set recognition problem definition

labeled data D_L이 N known classes들과 있다고 생각해보자. 이때, 특정 category k에 해당하는 positive training data를 

특정 category k를 제외한 다른 class들에 대한 training data를 

potential unknown data를

1-class open set recognition probelm 은 다음과 같은 optimization식을 optimization 하는 것이다.

이때 R^k는 expected error이다. α는 regularization parameter이다.

R_ε 는 known data의 empirical classfication risk이다.  

R_o 는 open space risk이다.

multi class classification에서는 위와 같이 표현할 수 있다.

Reciprocal Points for Classification

category k의 reciprocal point는 다음과 같이 표현할 수 있다.

이때 M은 각 class의 reciprocal point의 수이다. 이때 P^k는 sub-dataset

k  class가 아닌 dataset 및 unknown dataset에 대한 latent representation의 set 이라고 생각될 수 있다.

이때, 특정 category k에 대해 기준으로 learninig하는 prototype or center loss와 달리,

위의 기준에 따라 reciprocal point를 설정하는 것은  S_k보다는 O_k에 있는 sample로 설정하는 것이 적절하다.

(S_k는 특정 class k의 sample이 차지하는 space, O_k는 특정 class k를 제외한 나머지 class에 대한 embedding space 및 unknown class들의 embedding space를 합친 공간이다.)

이는 다음과 같이 표현이 가능하다.

이때 ,

는 two sets의 모든 sample에 대한 distances들의 set이다.

즉 위의 식을 해석하면 다음과 같다. 

특정 class k data와 k에 대한 reciprocal point P에 대한 모든거리를 d라고 표현할때, 

class k의 reciprocal point와 class k의 제외한 데이터 및 unknown data간의 distance들의 max값을

d보다 작게 하는 것을 의미한다.

즉 한마디로 reciprocal point를 특정 class k에 대한 data들의 거리보다 k가 아닌 data들간의 거리가 가까운 점이어야 한다는 것이다.

어찌되었든 openset learning은 known space와 unknown space를 최대한 분리시키는 것이다. 

이를 위해서 class k와 reciprocal point에 대한 공간을 최대한 분리시킨다.

이를 위해서 sample x가 있고, reciprocal point P_k가 있을 때,  둘간의 거리는 sample x가 embedding 된 위치와 M개의 reciprocal point와의 distance의 평균으로 정의한다.

이때, sample x가 category k 속할 확률인 reciprocal 간의 거리에 비례하게 된다.

즉 거리가 클수록 class k에 속할 확률이 높으므로 다음과 같이 정의가 가능하다.

γ는 hyper parameter이다. γ 는 probability의 assign되는 정도를 뜻한다. (클수록 크고 급격한 확률로 속하게 됨)

Loss function은 다음과 같다.

이러한 방법을 통해 closed space와 open space의 interval을 크게 만들 수 있으며, 

또한 아래 empirical classfication risk 또한 줄일 수 있다. 

Reducing Open Space Risk

open set recognition 문제를 풀기 위해서, reciprocal loss를 open space risk를 줄이기 위해서도 같이 사용한다.

open space는 category k를 제외한 다른 class sample이 embedding되는 space

unknown sample들이 embedding되는 space

두개로 나누어 생각할 수 있다.

그러므로 모든 known class의 open space를 고려한 global open space 다음과 같다.

이때, maximum entropy 이론에 따르면, 따로 prior 조건을 주지 않은 unknown sample x_u는 

well-trained closedset disciriminant function에는 equal probability를 가지게 된다.

(최종 softmax 확률값 uniform하게 나온다.)

이것의 의미는 embedding space상에서 unknown sample은 중앙에 위치하는 경향을 가진다는 의미이다.

이는 다음과 같은 실험 결과에서 확인 가능하다.

이때, open space를 직접적으로 어떠한 공간으로 bounding 시키는 것은 어려운일이다. 왜냐하면 unknown sample의 범위가 너무나도 넓기 때문이다.

그러나 class k에 대한 space S_k와 나머지 space O_k를 상호보완적(complementary)라고 생각하면, 다음과 같이 간접적으로(indirectly) bounding이 가능하다.

이때, R_k는 learnable margin이다. 이때 위 식을 minimizing하는 것은 다음 두식을 최대한 같게 만드는 것과 같은 의미이다.

이유는 위 식에서 x의 embedding된 위치와 reciprocal point와의 거리가 바로 

이 식이기 때문이다. (집합 인 것만 다름)

그러므로 다음과 같이 된다.

위 식때문에,

와 같이 된다. (d와 R^k가 최대한 가까워지므로)

이렇게 하면 reciprocal point P_k를 중심으로 margin R^k를 가지는 boundary가 형성된다.

이 bounded space를 이용해 global unknown space를 최대한 bounded할 수 있다.

Learning Open Set Network

결론적으로 loss식은 다음과 같이 된다.

위 식의 의미는 classfication loss식에서는 k class의 reciprocal point랑 k class에 대한 sample의 거리를 크게 만드는 역할을 한다.  open space에 대한 regularization 식은 단순히 거리를 크게 만드는 것이 아니라 특정 boundary로 embedding space를 제한하는 역할을 한다.

loss 식을 통해 아래 그림과 같이 embedding space가 형성된다.

이때까지 설명한 내용을 알고리즘으로 나타내면 다음과 같다.

Experiments

RPL++은 RPL training을 위해 GCPL을 같이 사용한 경우를 말한다.

1) Experiments for Open Set Identification

2) Experiments for Open Long-Tailed Recognition

Evaluation metric

AUROC 및 AUPR을 사용, AUPR-Known과 AUPR-Unknown은 각각 known과 unknown을 positive로 놓았을때, precision-recall 값을 말한다. 

Further Analysis

1) RPL vs Softmax

Reciprocal의 classification loss term만 사용할 경우, 일반적인 cross entropy loss term과 큰 차이가 없다.

그러나 open space에 대한 loss term을 추가하는 경우, high confidence를 발생시키는 unknown sample에 대한

risk를 감소시키고 known sample이 embedding space의 중앙에 위치하여 발생하는 known sample과 unknown sample간의 overlap 또한 막을 수 있다.

2) RPL vs GCPL

GCPL경우 center loss처럼 prototype loss를 적용한 방법이다. 이러한 loss를 적용하는 경우 각 class의 sample들이 한 곳으로 뭉치는 효과가 있으나, embedding space의 주변부로 최대한 멀어지는 효과는 가지지 못한다. known class sample들을 최대한 주변부로 밀어내는 RPL에 비해 known class sample과 unknown class sample이 겹치는 것을 볼 수 있다.

3) Margin & λ.

open space loss를 λ를 통해 조절이 가능하다. 이를 통해서 margin 또한 조절이 가능하다. 

dataset 마다 적절한 margin은 다르며, 너무 작게 margin을 설정할 경우 classificaiton 성능이 떨어진다.

4) Experiments with Multiple Reciprocal Points.

Reciprocal point의 수에 대한 변화이다.

Paper

arxiv.org/abs/1905.02175

Introduction

그동안 adversarial example에 대한 여러가지 해석이 있었다.

본 논문에서는 사실 adversarial example은 deep learning model이 학습하는 featrue는

robust-feature와 non-robust feature 2가지로 나뉘게 되며,

adversarial example은 non-robust feature를 이용한 것이란 것을 증명한다.

Paper

arxiv.org/abs/2004.00431

Code

github.com/alinlab/M2m

Introduction

Imbalanced data를 다루는 방법에는 여러가지 방법이 있지만 그중에서 re-sampling 방법이 있다.

re-sampling 방법은 minority class의 sample을 생성하여, minority class의 수가 부족한 것을 해결하는 방법이다.

대표적인 re-sampling 방법으로는 SMOTE가 있다.

SMOTE는 minority class의 sampling이 feature space상에 embedding되면 sample들의 linear combination을 하여

새로운 feature space상에 sample들을 생성하는 방법이다.

그러나 minority class의 sample이 아주 작은 경우 sample을 생성하더라도 다양한 sample이 생성되지 않기 때문에,

poor performance를 보여주는 경우가 많다.

Contribution

본 논문에서는 minority sample을 생성하는 새로운 방법을 제시한다. : Major-to-minor Translation (M2m) 

기존 SMOTE 계열 방법들은 minority sample을 추가로 생성하기 위해서 minorrity class의 sample들을 이용했다.

그러나 본 논문에서는 minority sample을 생성하기 위해 majority sample을 이용한다.

M2m: Major-to-minor translation

data imbalanced 문제는 보통 다음과 같이 귀결된다.

일반적인 classification 문제는 train data distribution과 test data distribution이 동일하다고 가정한다.

그러나 imbalnced data 문제는 train data distribution과 test data distribution이 동일하지 않다. 

train data 의 경우 highly imbalanced , test data의 경우 uniform distribution을 가진다.

그래서 imbalanced된 train data를 학습하여, uniform인 test data에 잘 동작하는 것이 목표이다.

M2m method의 경우, 이를 행하기 위해 sythetic sample을 majority class로 부터 생성하여 minority sample에 추가한다. 

이러한 방법에는 image to image translation을 통한 minority image를 생성하는 방법도 존재하겠지만,

추가적인 학습 및 복잡한 방법론이다.

본 논문에서는 majority sample을 target minority sample에 대한 confidence를 maximize하는 형태로 

새롭게 minority sample을 생성한다.

이때 another baseline classifier g를 사용하는데, 이는 기존의 imblanced training data에 대해 standard ERM training을 통해 학습한 classifier이다.

때문에 classifier g는 minority class에 overfitting되어 있으며, balanced test dataset에는 generalize가 잘 되어있지는 않은 classifier이다.

이때 우리는 g를 이용해서 minority sample을 생성할 것이다. 그러므로 g는 majority class의 sample들을 이용해 minority sample들을 잘 생성할 수 있다고 가정한다.

그리고 생성된 sample들을 이용해 classifier f를 balanced testing criterion에 맞추어 새로 학습한다.

이때 g를 이용해 sample을 생성할 때, 사용하는 optimization problem 수식은 다음과 같다.

이때, L은 cross entropy loss이고, λ는 hyper parameter이다.

본 식의 의미는 다음과 같다.

major class의 sample x_0에다가 noise δ를 더해서 minority class sample x를 생성하는데,

이때, g classifier에 input으로 넣어서 target minority class k 에 대한 loss가 최소가 되도록 한다.

그리고 생성된 sample x^*를 f classifier를 학습시키는 데 이용한다. 

이때, 생성된 sample의 경우 f classifier에서 기존 class인 k_0로 분류되지 않도록 regularization term을 넣어준다.

이렇게 하는 경우, x_0에서 생성된 sample x가 f_classifier에서 기존 class인 k_0로 분류되는 것은 막으면서

x_0의 주요한 feature는 남길 수 있다고 저자는 말하고 있다. 

(f_classifier에서도 k_class로 바로 prediction하도록 optimization 수식을 세우면, 주요한 feature가 사라질 가능성 있음)

그림으로 나타내면 아래와 같다.

Underlying intuition on M2m

결론적으로 M2m은 다음 논문에서 제시한 방법을 이용한다.

-> Adversarial examples are not bugs, they are features.

결국 majority class에서 minority class에 대한 non-robust feature을 더하여 sample을 생성하는 형태이다.

Detailed components of M2m

1) Sample rejection criterion

synthetic sample을 생성할 때 중요한 것은, g classifier가 기존 class k_0에 대한 feature는 잘 제거하는 것이다.

그래야 k class의 sample을 제대로 생성했다고 판단할 수 있기 때문이다. 

그러나 g classifier는 완벽하지 않기 때문에, k_0를 이용해 k class의 sample을 완벽하게 생성하지는 못한다.

그러므로 생성된 sample이 오히려 방해가 될 가능성이 있다. 

(k_0에 대한 diciriminative한 feature가 남아있을 가능성이 있음)

이러한 risk는 특히 생성을 위해 사용하는 k_0의 sample수가 작을 경우 더 심해진다. 

이러한 risk를 줄이기 위해서 저자는 synthetic sample을 일정 확률로 rejecting하는 방식을 제안한다.

위 식의 의미는 N_k_0 - N_k의 max 값을 B의 exponential 값으로 이용하겠다는 것이며,

B의 값이 작을수록 classifier g의 reliability가 더 높다는 것을 의미한다.

예를 들어 B=0.999이면, sample을 accepted하는 probability가 N_k_0 - N_k > 4602일때, 99% 이상이다.

B=0.9999이면, N_k_0 - N_k > 4602일때 99% 이상이다. 

이러한 모델링은 effective number 논문에서 참고한것이다.

위 논문에서, larger dataset에서 sample이 하나 추가될 경우 실제로 적용되는 효과는 exponentially하게 decrease된다고 한다.

(그냥 확률적으로 rejection 한다는 것이 불분명함)

만약 synthetic sample이 reject되는 경우, original dataset에 있는  minority sample을 대신 추가해준다.

2) Optimal seed sampling

그 다음 고려해볼만한 사항은 class k_0에 대한 majority seed sample x_0를 어떻게 선정할 것인가에 대한 내용이다.

이를 위해서 저자는 다음과 같은 Q(k_0 | k) 를 design 했다.

이때 2가지를 고려한다.

(a) Q는 acceptance probability P_accept(k0_|k)를 maximize 하도록 정한다.

(b) Q는 가능한 diverse class를 정하도록 한다. 즉 entropy H(Q)를 maximize하도록 한다.

결국 다음과 같이 식을 세울 수 있다.

이 optimization을 최대화하는 Q는 P_accept이다. (why?)

그래서 Q(k_0|k)는 다음과 같다.

위의 Q를 이용해 k_0가 결정되면 x_0는 uniform하게 random sampling 한다.

전 과정을 나타내면 다음과 같다.

sudo reboot

Paper

arxiv.org/abs/1901.05555

Code

github.com/vandit15/Class-balanced-loss-pytorch

Introduction

imbalanced-data 문제에서는 re-sampling, re-weighting 방법이 주로 적용된다. 

이러한 방법은 주로 class frequency의 inverse하게 weighting을 적용했었다.

그러나 최근 연구에서 이러한 방법이 poor performance를 보였었고, 

때문에 square root에 inverse 하여 weighting 하는 smoothed version이 제안되었다.

이러한 발견은 다음과 같은 의문을 낳게 되었다.

"다양한 imbalanced data에 따라 어떻게 class balanced weighting을 하는 것이 좋은 것일까?"

위 그림과 같이 highly imbalanced data에 바로 sample 수에 inverse하게 re-weighting 방법을 적용하는 것은 좋은 성능을 내지 못한다. 

일반적으로 생각하기에는 data가 많을 수록 성능이 좋아지는 것이 맞지만, 비슷한 data가 추가되는 경우, 실제로 반영되는 효과는 낮다. 그렇기 때문에 각 class마다 'effective number'를 구하고 effective number를 기준으로 하여 re-weighting을 진행한다.

그래서 이 논문의 main contribution은 다음과 같다.

(1) long-tailed dataset을 다루기위한 effective number of sample의 이론적 분석 및 loss function에 적용하는 class balanced term을 design

(2) class balanced term을 기존의 loss function에 추가함으로써, 높은 성능 향상을 가져옴 (cross entropy, focal loss) 

Effective Number of Samples

1) Data Sampling as Random Covering

먼저 sample들의 effective number를 E_n으로 정의한다. 이때 n은 sampling된 example의 수이다.

수학적으로 너무 복잡해지는 것을 막기 위해 partially overlapped 되는 상황은 제외한다.

기존에 있던 data와 overlapped 되는 확률을 p, overlapped 되지 않는 경우를 1-p로 정의하며,

sampling을 진행할 수록 overlapped 될 확률이 커지기 때문에 p는 커지게 된다.

이때, effective number를 수식으로 나타내면 다음과 같다.

이 수식을 증명하는 과정은 다음과 같다.

먼저 E_1=1이다.  (sample이 단 하나이므로 overlapping이 전혀 이루어지지 않기 때문에 당연한 결과이다.)

그러므로 다음과 같이 수식을 먼저 쓸 수 있다.

그리고 n-1개의 example을 sample하고 n번째 example을 sampling하는 경우를 생각해보자.

n-1개의 sample을 sampling했을 때, expected volume은 E_n-1이 된다. 이때, 새롭게 sample된 데이터가 

overlapped될 확률은 다음과 같다.

그러므로 n번째 example이 sampling되었을 때, expected volume은 

와 같이 된다.

이때, E_n-1을 다음과 같이 가정하면

즉, 처음에 가정했던 식이 맞게 된다. (점화식 형태)

이는 samples의 effective number가 n의 exponential function이라는 것을 알려준다.

B는 0~1사이의 값을 가진다. E_n을 다른 형태로 표현하면 다음과 같다.

이 수식의 의미는 j번째 sample이 effective number에 영향을 주는 정도가 B^(j-1)이라는 것이다.

그래서 all possible data의 total volume은 다음과 같이 계산이 가능하다.

위 식을 토대로 다음과 같은 점근적 성질을 발견할 수 있다.

내용을 해석하면, all possible data N이 커질수록, effectve number of sample의 값은, 실제로 sampling된 숫자 n과 같게 된다.

즉, N이 커질수록 data overlap이 사라지고, 모든 sample이 unique해진다는 것을 의미하며, N=1인 경우는 오직 하나의 prototype만 존재하는 상황을 의미한다.

Class-Balanced Loss

input sample을 x , label을

라고 정의하자. 이때 model이 각 class에 대해 prediction한 probability를 다음과 같이 정의한다.

위의 정의에 따라 loss를 L(p,y) , class i의 number of samples를 n_i라고 하자.

그러면 effective number of samples for class를 다음과 같이 나타낼 수 있다.

이때, N_i 를 특정하게 좋은 값으로 설정하는 건 어려운 일이기 때문에 다음과 같이 dataset에 맞게 설정한다.

class-balanced loss를 적용하기 위해서 weighting vector a를 적용한다. 

이때 weighting은 class i에 대한 effective number of samples에 inverse하게 적용한다.

weighting을 적용했을 loss값의 scale이 달라지기 때문에 아래 식으로 나눠줌으로써, 다시 normalize해준다.

결론적으로 본 논문에서 제시하는 CB (class-balanced) loss는 다음과 같다.

이 loss function을 B를 변화시키며 나타내면 다음과 같다.

B가 1에 가까워질수록 inverse class frequncy에 맞게 re-weighting 된 것을 의미한다.

이러한 class-balanced loss는 모델이나 loss function에 general하게 적용이 가능한 장점이 있다.

본 논문에는 이를 증명하기 위해서 softmax cross-entropy loss, sigmoid cross-entropy loss, focal loss에 적용하였다.

Class-Balanced Softmax Cross-Entropy Loss

Class-Balanced Sigmoid Cross-Entropy Loss

Class-Balanced Focal Loss

Experiments

Imbalance factor는 가장 sample수가 많은 class의 sample 수와 가장 sample수가 작은 class의 sample을 나눈 값이다.