Clustering - Learning Discrete Representations via Information Maximizing Self-Augmented Training

Deep neural networks 는 데이터의 복잡한 비선형 관계를 잘 모델링할 수 있다는 점에서 머신러닝의 다양한 분야에 채택되어 왔고 clustering 이나 hash learning 과 같은 discrete representation이 필요한 태스크에도 응용되어 왔습니다. 하지만 deep neural networks은 모델의 복잡도가 크고 clustering과 같은 비지도학습은 타겟 단에서의 라벨이 없기 때문에 모델에 대한 적절한 정규화 (regularization)이 필수적입니다.

이번 포스트에서 다룰 내용은 데이터를 discrete representation 으로 매핑하는 deep neural networks를 data augmentation 에 대해서도 결과가 변하지 않도록 (invariant) 하는 정규화 항으로 훈련시키는 IMSAT (Information Maximizing Self-Augmented Training) 알고리즘입니다. Figure 1에서와 같이 deep neural networks의 출력은 discrete representation이 되는데, data augmentation 한 입력에 대한 출력과 차이가 나지 않도록 정규화하면서 입력과 출력의 mutual information 를 최대화하는 방향으로 훈련하게 됩니다.

IMSAT

먼저 IMSAT은 다음 목적함수를 최소화하는 방향으로 $\theta$로 이루어진 deep neural networks를 훈련합니다.

$R(\theta) - \lambda I(X;Y)$

$R(\theta)$는 deep neural networks에 대한 정규화 항이고 $I(X;Y)$는 입력 $X$와 출력 $Y$의 mutual information입니다. Mutual information은 $Y$를 관측하였을 때 알 수 있는 $X$의 정보량으로 두 변수 $X,Y$가 서로 얼마나 의존적인지를 나타내는 통계치이며 두 변수가 독립일 경우 0이 되게 됩니다. 직관적으로 $Y$는 $X$가 deep neural networks 를 거친 출력 representation 이므로 $X$에 대한 정보를 최대한 많이 가져야 한다고 생각할 수 잇습니다.

Mutual Information

$Y$가 $m$ 차원의 discrete representation 이라면 deep neural networks 는 $y_1, ..., y_M$의 확률을 출력하는 classifier $p_\theta (y_1, ..., y_M|x)$ 가 되고 입력 $x$에 대해 각 $y_1, ..., y_M$ 가 조건부 독립을 만족하게 됩니다. 따라서 $p_\theta$를 $I(X;Y)$가 최대화하는 방향으로 훈련합니다.

Regularization

비지도학습은 타겟 단의 라벨과 같은 제약조건이 주어지지 않은 상태로 학습하기 때문에 deep neural networks 모델를 원하는 방향으로 제어하는 정규화 항이 필수적입니다. IMSAT 에서는 SAT (Self-Augmented Training) 기법을 사용하여 $p_\theta$를 훈련합니다. SAT 의 Self-Augmented 라는 단어에서 볼 수 있듯이 본래 데이터 $x$에서 augment 한 $T(x)$를 유도하며, 정규화는 $x$의 출력 $p(y|x)$와 $T(x)$의 출력 $p(y|T(x))$의 차이가 줄어들도록 동작합니다.

Equation 1

Equation 1의 $\hat{\theta}$는 현재 네트워크의 파라미터를 나타내며 $p_{\hat{\theta}}(y|x)$는 고정된 값이고 $p_\theta (y|T(x))$를 통해 정규화 항으로 인해 파라미터가 업데이트됩니다. Equation 1은 기본적으로 cross entropy 모양으로 고정된 $p_{\hat{\theta}}(y|x)$ 분포에 대한 $p_\theta (y|T(x))$ 분포의 차이를 줄이도록 설계되어 있습니다. 즉, augmentation $T$에 따른 출력의 변화가 최소화되도록 정규화를 적용한다는 것이죠. $R_{SAT}$는 전체 데이터 $N$에 대해 평균을 취하여 적용하게 됩니다.

그렇다면 augmentation $T$는 어떻게 정의할까요? 이미지에 대해서는 회전, 비율 변화, 전이 등 미리 정의된 고정된 augmentation을 사용할 수 있겠지만 IMSAT 에서는 주어진 데이터 $x$에 대해 지역적인 perturbation $r$을 적용한 $T(x)=x+r$ 을 augmentation 으로 사용합니다. 즉, $x$에 대한 representation이 지역적인 변화에 무감하도록 하겠다는 것이죠. $r$은 local perturbation의 범위 $\epsilon$에 따라 1) $\Vert r\Vert_2=\epsilon$을 만족하는 랜덤한 $r$을 사용하는 RPT (Random Perturbation Training)나 2) 출력이 변하는 최대한의 $r$을 구하는 VAT (Virtual Adversarial Training) 두 가지를 사용합니다. (VAT의 저자가 이 논문의 2저자입니다.)

Virtual Adversarial Training

Clustering

정리하면 IMSAT은 deep neural networks 를 $I(X;Y)$를 최대화하고 $R_{SAT}$를 최소화하는 방향으로 훈련합니다. 이때, mutual information 의 정의에 의해 $I(X;Y)=H(Y)-H(Y|X)$로 표현할 수 있습니다. ($H$는 entropy)

IMSAT의 목적함수

$H(Y)$는 출력 $Y$의 entropy, $H(Y|X)$는 $Y$의 $X$에 대한 conditional entropy로 다음과 같이 정의됩니다.

Entropy, Conditional entropy

$H(Y)$가 최대화된다는 것은 discrete representation $Y$가 uniform distribution에 가깝도록 훈련된다는 것으로 clustering이 특정 몇 군집에 쏠리는 것이 아닌 최대한 다양한 군집에 퍼져 있도록 동작한다는 것이고, 반대로 $H(Y|X)$가 최소화된다는 것은 $Y$가 $X$에 대해 확실히 결정되도록 훈련된다는 것으로 특정 입력에 대해서는 특정한 한 군집이 도출되도록 동작한다는 것입니다. 정리하면, $H(Y)$는 데이터 전체에 대한 정규화, $H(Y|X)$는 개별 데이터에 대한 정규화로 이해할 수 있습니다.

---

$H(Y)$는 $-KL(p(y)|uniform)$ 으로 표현할 수 있습니다. $H(Y)$가 최대화된다는 것은 출력단의 확률분포 $p(y)$가 uniform distribution과 가깝게 된다는 것이니까요. 각 군집 분포가 미리 정의되어 있지 않다면 uniform distribution 을 사용해도 무방하지만 우리가 사전 지식으로 군집 분포 $q(y)$를 알고 있다면 uniform distribution 대신 $q(y)$를 사용하여 $KL(p(y)|q(y))$가 줄어들도록 훈련시킬 수 있습니다.

Equation 2

Equation 2는 $KL$ 제약조건을 풀어 쓴 penalty 방법으로 풀이할수가 있습니다. Equation 3과 같이 풀어쓰고 $\mu$를 작은 값부터 설정한 이후에 점차 증가시켜 $KL(p(y)|q(y))\leq \delta$를 만족하는 최소한의 $\mu$를 찾으면 됩니다.

Equation 3

Hash learning

Hash learning은 각 데이터가 $D$ bit를 가진 이진 코드로 매핑하는 것으로 $I(Y_1, ..., Y_D;X)$를 최대화시킵니다. 하지만 이는 $D$가 커질 수록 계산 상으로 불가하며 이를 여러 개의 interaction information 항으로 쪼개 더해서 계산합니다.

Interaction information

Equation 4

Equation 4는 mutual information $I(Y_1, ..., Y_D;X)$ 을 여러 개의 interaction information $I(C\bigcup X)$의 합으로 나타낸 것으로 $S_Y={Y_1, ..., Y_D}$입니다. Interaction information 은 두개 이상의 변수에 대한 mutual information의 일반화된 개념으로 mutual information과 달리 음수의 형태를 가질 수 있습니다. IMSAT을 이용한 hash learning 에서는 Equation 4에서 $|C| \leq 2$를 만족하는 항만 추려내어 $I(Y_1, ..., Y_D;X)$를 계산합니다.

Equation 5

Equation 5는 $D$ bit 중 2개씩만 뽑아내어 interaction information을 계산하고 3개 이상의 interaction은 고려하지 않습니다. 이는 일반적으로 hash bits가 2개의 쌍에 대해서만 직교가 되도록 강제되기 때문에 이런 approximation을 취했다고 합니다. Equation 5의 우측 항은 interaction information의 정의와 위에 언급한 조건부 독립 (conditional mutual information $I(Y_d;Y_{d'}|X)=0$)에 의해 Equation 6으로 유도되고 최종적으로는 Equation 7의 목적함수가 hash learning에 사용됩니다.

Equation 6

Equation 7

---

IMSAT 은 deep neural networks를 mini-batch 단위로 훈련시키에 mini-batch 안에서 conditional entropy, entropy를 계산하게 됩니다. Conditional entropy는 각 데이터 별로 계산되므로 mini-batch 상에 적용하는데 문제없지만 entropy 같은 경우는 전체 데이터에 대한 marginal distribution 을 알아야하기 때문에 mini-batch 상에서의 계산을 부정확할 수밖에 없습니다. 따라서 IMSAT 에서는 mini-batch 에 대하여 marginal distribution을 근사해서 사용합니다.

 

Experiment

실험은 일반적인 deep neural networks 를 사용하고 차원은 $d-1200-1200-M$을 사용합니다. ($d, M$은 각각 입출력 차원) 또한 매 layer 마다 ReLU와 batch normalization을 적용하고 Adam optimizer를 사용합니다. VAT를 위한 perturbation 범위 $\epsilon$은 각 데이터마다 10번째로 가까운 데이터와의 거리 $\sigma_{10}$에 $\alpha=0.4, 2.5, 0.25$를 곱해 사용합니다. ($\epsilon(x) = \alpha \cdot \sigma_{10}(x)$)

Clustering 벤치마크 데이터에 대한 결과는 다음과 같습니다. Linear IMSAT에 비해 deep neural networks를 사용한 IMSAT이 더 좋은 성능을 거두었고 IMSAT (VAT)가 거의 모든 데이터셋에 대해 우수한 성능을 거두었습니다.

결과 metric은 ground-truth $l_n$과 cluster $c_n$의 hungarian matching algorithm으로 구한 accuracy를 사용합니다. 즉, $c_n$에 할당된 번호는 불분명하므로 $l_n$ 번호와의 가능한 모든 one-to-one 매핑 $m$에 대해서 accuracy가 최대가 되는 $m$을 사용합니다.

Omniglot 

Omniglot 데이터는 옛날 상형문자 데이터로 구분하기 어려운 데이터 중에 하나입니다. IMSAT의 $R_{SAT}$에 VAT와 더불어 랜덤 affine transformation을 적용한 $R_{SAT}$를 사용하였을 때 결과가 더 좋았다고 합니다.

 

참조

• arxiv.org/pdf/1702.08720.pdf
• en.wikipedia.org/wiki/Interaction_information#:~:text=The%20interaction%20information%20is%20a,information%2C%20and%20simply%20mutual%20information.