이번에는 ICLR 2021에 oral session에 accept 된 Co-MixUp: Saliency Guided Joint Mixup with Supermodular Diversity을 리뷰하려고 합니다. 자세한 내용은 원문을 참고해주세요.
Introduction
딥러닝 분야가 발전함에 따라 놀라운 성능을 보여주고 있지만, 가장 큰 문제는 excessive representation capability로 인한 overfitting이었다. 관찰하지 못한 데이터에 대해서 large generalization gap을 보여온 것이 문제였습니다.
Generalization을 향상시키기 위해서 research는 regularizer위주로 진행되어 왔습니다. (Ex batchnorm, dropout) 또한 prior나 augmentation을 통해서 task-dependent한 transform을 시도했고, CutMix나 MixUp처럼 augmentation방법들이 제시되어왔다.
Mixing ratio을 적절하게 조절하기 위해서 PuzzleMix의 경우 mixup을 기반으로 saliency와 주어진 데이터의 local statistics를 활용해왔습니다. 하지만 supervisory signal(적절하게 부여하는 신호)를 최대한 사용하지 않았고, 이러한 것을 개선하기 위해서 Co-MixUp이라는 방법론을 제시하면서 모든 input data에 대해서 가능한 한 많은 salient region을 갖도록 하면서 diversity를 보장하는 알고리즘을 제안하고자 한다고 합니다. (optimization problem)
Related work
MixUp
데이터 augmentation은 최근 널리 사용되어 overfitting을 막는 데에 주로 사용되어 왔습니다. 뒤이어서 input이 아닌 feature level에서 mixup을 하는 manifold mixup이 제시되었고, CutMix는 spatial copy and paste기반 mixup strategy를 제시해왔습니다.
Saliency
Saliency map은 개체를 배경과 분리하여 나타내는 것을 말합니다. neural network로도 구할 수 있으며, object segmentation이나 speech recognition domain에서도 사용되어 왔고 널리 쓰이고 있습니다.
Submodular-Supermodular optimization
Submodular function은 diminishing returns property를 갖는 set function입니다. wikipedia에 따르면 단일 요소가 입력 집합에 추가될 때 만드는 함수의 증분 값의 차이가 감소하는 속성을 갖는 set function입니다. 즉 제가 더 많은 input값을 가지고 있으면, 더 적게 return 받는 함수라고 생각하면 됩니다.
Supermodular function의 경우 increasing returns property를 갖는 set function으로 submodular와 정 반대로 생각하시면 될 것 같습니다.
Sub/supermodular function의 합으로 어떤 set function이든 표현이 가능하며 이를 BP function이라고 부릅니다. 하지만 NP-hard 문제여서 approximate algorithm으로 문제를 푸는데, sub/supermodular function을 modular approximation을 하는 방법입니다.
본 논문에서도 formulation은 BP function이어서 optimization 을 approxmiation으로 진행하게 됩니다.
(supermodular의 경우 diversity function에서 나타나고, submodular의 경우, smoothness function에서 나타남)
Preliminary
MixUp method는 $h(x_1,x_i(1))$ 로 주어진 input data ${x_1,...,x_m}$로부터 input data를 받음(h는 mixup function)
PuzzleMix 는 h(x,x')을 discrete mask인 z와 transport plan인 $\pi$를 사용하여 나타냈습니다. 본 논문에서는 $h(x_B)=(g(z_1 \odot x_B),...,g(z_m' \odot x_B))$ 로 나타내고 있습니다. $x_B$는 input의 mini-batch상에서의 data입니다.
$z_{j,k} \in L^m$ 의 경우 j는 input index이고 k는 $z_j$의 k 번째 column값입니다. z는 m inputs들에 대한 k location에서의 mixing ratio라고 보시면 되고 k에 대한 $|z_{j,k}|$=1 로서 input batch에 대해 주어진 overall statistics를 유지하게 하였습니다. (동일 k에 대한 모든 j에서 z의 합이 1입니다)
Mixing label은 $y_B$가 one-hot target label이라고 할 때, $y_B \in {0,1}^{m \times C}$라고 정의되며, 이를 soft target label로 변형 시킬 때 notation은 $y^{\top}_B \hat{o}_j$ where $\hat{o}_j=1/n \sum^n_{k=1} {z_j,k \in [0,1]^m}$ 입니다. 이를 crossentorpy loss를 minimizing 시켜서 정확하게 soft target label을 estimate할 수 있도록 하고 있습니다.
Method
Local smoothness data를 유지하면서 saliency measure를 극대화하는 mixup data를 만들기 위한 목적을 갖고 만들었다고 합니다. CutMix의 경우 Saliency와 상관 없이 supervisory signal을 leading하여 target soft label을 만들었습니다. 또한 기존의 method들은 2개의 input만가지고 해당과정을 진행해왔습니다. 본 모델에서는 m개의 candidate sources from the input을 통해서 k th location에 할당될 수 있게 만들었습니다.
unary labeling cost를 negative value of the saliency(intput의 backward 결과물인 gradient에 음수를 취한 값)으로 모델링하고 $c_k \in R^m$를 k th location의 cost vector라고 할 때, saliency는 training loss로 부터 얻은 gradient loss를 각각의 input에 대해서 l2 norm을 input channel에 대해 구합니다. (no additional architecture of neural network)
정리하면 다음과 같습니다.
1번째 항은 각 k th location에 대한 unary cost vectord와 one-hot mask와의 곱이고 이를 줄이는 방향으로 update합니다. 2번째 항은 $z_{j,k}$과 $z_{j,k'}$값을 키워서 2번째 항의 값을 줄이는 것이 목적입니다. 마지막 항의 경우, z_{j,k}로 부터 주어진 prior p term이고, mixing ratio distribution의 generalization term이다.
해석해보면 1번째 항은 gradient가 크게 발생하는 곳은 z를 1로 만들어 saliency measure를 키우는 것이고, 두번째 항의 경우 $z_{j,k}$가 옆의(w,h) pixel또한($z_{j,k(w+\epsilon,h+\epsilon)}$) 동일한 이미지로부터 오기를 바라게 설계한 항입니다.(smoothness) 마지막 항의 경우 prior p를 사용하여 적절한 location에 z_{j,k}값이 1로 존재하도록 하는 것을 목표로 sampling되도록 유도하는 것입니다. (log p값이 0일 수록 objective가 작기때문)
Diversity(다양성) 측면에서 위의 식을 살펴보면 identical outputs를 return 하게 됩니다 왜냐하면 objective 는 separable하고 각 output에 대해서 identical하기 때문입니다. 다양한 mixup output을 얻기 위해서 outputs끼리 similarity penalty를 부여합니다. j th output에 대한 input source information을 나타낼 때, assigned labels(z_{j,k})을 모아서 나타냅니다.
$o_j=\sum^n_{k=1} {z_{j,k}}$로 notation하게 되면 $o_j$끼리의 similarity를 내적으로 구하게 됩니다. Compatibility는 $A_c \in R^{m \times m}$으로 나타낼 수 있게되고, $A_c$를 통해서 input i1, i2가 섞여도 적절한지 판단하게 됩니다. $A=(1-w)I+wA_c$ 로 supermodular penalty term을 구성할 수 있고 $<o_j, o_{j'}>_a=o^{\top}_j A o_{j'}$를 최소화함으로써 output mixup examples을 유사한 input sources를 통해서 만들지 않도록 penalize하고 high compatibility를 갖도록 할 수 있습니다. 본 논문에서는 $A_C[i,j]= ||argmax_{k}{s_{i}[k]}-argmax_{k}{s_{j}[k]}||_1$ 를 사용하였습니다. ($s_i$는 i input의 saliency map)
Over-penalization 측면에서 conventional mixup method는 mixup을 주어진 mini-batch에 대해서 많은 수의 example을 만들어 낼 수 있습니다. 본 논문에서 m=m'일 때 가능합니다. 하지만 outputs(generated mixup images)들 끼리의 compatibility penalty는 pigeonhole principle에 의해 영향을 받게 됩니다.
Pigeonhole principle (비둘기집 원리)는 n개의 입력에 대해서 n-1개의 상자가 존재할 때, 어느 하나의 상자에는 2개의 입력이 존재한다는 것입니다.
본 논문에서의 compatibility term은 over-penalize하는 최적화로 인해 generated output에 mixup을 진행하지 않고 하나의 이미지로만 출력되는 현상을 발견했다고 합니다. 그래서 over-penalization이슈를 없애기 위해서 compatibility penalty term에 clipping을 적용했다고 합니다. (최대 섞임 ratio에 clipping)
Objective를 구성할 때 compatibility가 일정이하일 때 no extra penalty가 나타나게 한 것입니다.
f(z)를 objective라 할 때, f_c(z)가 over penalization을 막아 compatibility를 상승시킴으로서 하나의 이미지로 generated image output를 구성하지 않게 막는 term입니다.
해당 내용은 figure 2에 나와있는데 $f_{c}(z)$ term에서의 $\tau$를 1로 두고 생각해보면 compatibility term을 clipping하지 않는 경우가 되는데, diversity가 baseline보다 떨어지는 현상이 발견되었고, 이에 0.81~0.86을 tau의 hyperparameter값을 사용하여 diversity를 올리기 위해 노력하였다고 합니다.
object는 그래서 (unary, prior)의 modular, (smoothness)의 submodular, (compatibility)의 supermodular term이 되어 BP function이 된다. 이를 최적화하기 위해서 iteratively modular function으로 supermodular term을 approximating 하는 방식을 사용했다.
$f_{c}(z)$는 증명에 의해서 clipping term이 없을 때, $v^{\top}_{-j_0}+c$로 변환이 가능하고 $z_{j_0}$의 modular function이 됩니다. 이러한 objective에 대해서 submodular minimization algorithm을 적용 가능합니다.
(objective가 modular와 submodular term으로만 구성되므로)
그래서 clipping 없이 coordinate descent할 수 있게 됩니다. clipping과 함께일 때는 supermodular compatibility term을 아래의 기준으로 modularize해서 진행했습니다.
1. Modularized function value는 outputs들에 영향을 끼치는 compatibility가 증가함에 따라 증가해야 한다.
2. Modularized function은 특정 level아래에서는 extra penalty가 적용되어서는 안된다.
Notation에 따르면 $f_{c} (z)=max{{\tau,v^{\top}_{-j} o_{j}+c}}$에서 $o_j=\sum^n_{k=1} {z_{j,k} }$는 j번째 output에서 input source information이고, $v_{-j} $ $= 2 \sum^{m'}_{j'=1,j \neq j'}{A_{o_{j'}} }$ 은 다른 outputs들의 상태를 encoding한 정보라고 할 수 있습니다. 그러므로 supermodular term(compatibility)은 $o_j$의 각 label에서의 penalization이라고 할 수 있다. 하지만, max term에 의해 $\tau-c$이 되는 경우에는 penalization을 진행하지 않습니다. (tau-c아래에서는 적절하게 섞였다고 판단하여 진행 x)
이러한 $f_c$의 modular approximation으로 인해서 iteratively submodular minimization algorithm을 적용할 수 있게 되었습니다. 해당 알고리즘은 algorithm 1에서 나온 내용으로 z_j를 최소화하는 값을 구하는 문제입니다. 해당알고리즘은 Narasimhan and Bilmes가 제안한 modularization strategy로서 supermodular set function에 대해서 사용가능하며 sub modula miniminzation algorithm을 적용함으로서 original BP objective를 monotonically decrease시킬 수 있다고 말합니다. 하지만, compleity와 randomness에 의한 modularization variance로 mini-batch size정도의 크기에만 적용시킬 수 있는게 단점이라고 합니다.
Experiment
Generalization을 평가하기 위해서 weakly supervised object localization과 calibration, robustness task에서 성능을 확인했습니다. classifier는 cifar100, tiny-imagenet, imagenet,등에서 보편적으로 평가하는 걸로 진행했습니다.
Confidence-Accuray plot에서는 cifar100에 대해서 진행했을 때 가장 기울기가 1에 가까워서 적절한 confidence로 test set을 prediction하는 모습을 보여주었습니다.
Calibration error는 confidence와 accuracy의 차의 절댓값에 weighted avg를 진행하였고 이를 통해서 다른 method와 확인한 결과 좋은 성능을 보여주었습니다.
Multiple input에 의한 효과도 관찰했는데 cifar100에서 cutmix와 manifold mixup, input mixup과 비교할 때 input의 수에 변화에 대해서 성능이 떨어지는 다른 mix method에 비해서 적절하게 mix하는 숫자를 정하는 co-mixup이 좋은 성능을 보여주었습니다.
섞은 결과물은 아래와 같습니다.
Conclusion
본 논문은 지금까지 method가 어떻게 섞을 것인지에 대한 고민을 했다면 무엇을 섞을지에 대한 고민도 같이 들어있다고 볼 수 있습니다. (Compatibility term)그래서 이러한 method를 새로운 appllication에 적용할 수 있으면 좋을 것 같다는 생각이 들었습니다. Complexity를 많이 줄이려고 노력했지만, (Bruteforce대비 optimization problem 적용으로 감소) 직전 논문인 PuzzleMix보다 늘어 감소할 수 있는 여지가 있을지 고려해보면 좋을 것 같다는 생각이 들었습니다.
댓글