초짜 대학원생의 입장에서 이해하는 Domain-Adversarial Training of Neural Networks (DANN) (2)

* Domain-Adversarial Training of Neural Networks -  Yaroslav Ganin 2016 논문을 기본으로 작성한 리뷰. 

저번 글에 이어 오늘 포스팅에서는 Domain Adaptation을 뒷받침하는 이론에 대해 살펴보고, 가능하다면 간단한 예제를 직접 코딩하여 풀어보는 것까지 해보겠습니다.

[Domain Adaptation 이론]

좀 더 구체적으로 문제를 정의해볼까요.

$X$ : input space, $Y = \{0,\cdots, L-1\}$ : set of $L$ possible labels일 때, $L$개의 class를 분류하는 문제를 생각해보겠습니다. DA 문제는 여기에 더하여 다음과 같이
$$\mathbb{D}_S: source~domain~~~~\mathbb{D}_T: target~domain$$
two different distributions over $X\times Y$이 추가로 있는 경우입니다.
따라서 비지도 DA 학습일 경우 우리는 $S$에 대해서는 label이 존재하지만 $T$에 대해서는 label이 전혀 없습니다.
$$ S = \{ (x_i,y_i) \}_{i=1}^n  \overset{i.i.d.}{\sim} (\mathbb{D}_S)^n;~~T=\{x_i\}_{i=n+1}^N  \overset{i.i.d.}{\sim} (\mathbb{D}_T^X)^{n'}$$
with $N = n+n'$ being the total number of samples.

따라서 이 논문에서 소개하는 알고리즘의 목표는 분류기(classifier) $\eta: X\rightarrow Y$를 만드는 데, $\mathbb{D}_T$의 label에 대한 정보가 전혀 없이도 target risk:
$$R_{\mathbb{D}_T}(\eta)=\Pr_{(x,y)\sim\mathbb{D}_T}\left( \eta(x) \neq y \right),$$ 가 낮도록 학습시키는 것입니다. 즉, test time에서도 잘 되는 classifier를 만들자는 것이죠.

Q) 어떻게?

[Domain Divergence]

Domain divergence는 source와 target 분포 간의 거리(distance)를 구하는 measure입니다. 보통 DA 문제를 푸는 전략이 target error를 source error와 domain divergence의 합으로 upper bound 시키는 방식이기 때문에 꼭 알아두어야할 개념 중 하나입니다.

생각해보면 매우 직관적인 전략이죠. source risk가 target risk의 good indicator가 되려면 일단 두 분포들이 비슷해야할테니 말입니다.

따라서 궁극적으로 A) source에 대한 classification error와 source와 target domain 간의 divergence가 동시에 작아지도록 할 수 있다면, source domain에서 학습한 feature로 target domain의 data 역시도 분류를 잘 할 수 있을 것이라 기대할 수 있겠습니다.

이렇게 거리를 측정하는 방법 중, 이 논문에서 사용한 것은 Ben-David가 제시한 $\cal{H}$-divergence로써 정의는 다음과 같습니다.

(Ben-David et al.,2006,2010; Kifer et al.,2004) Given two domain distributions $\mathbb{D}_S^X$ and $\mathbb{D}_T^X$ over $X$, and a hypothesis class $\mathcal{H}$, the $\mathcal{H}$-divergence between $\mathbb{D}_S^X$ and $\mathbb{D}_T^X$ is $$ \hat{h}_{\mathcal{H}}(\mathbb{D}_S^X,\mathbb{D}_T^X) = 2\sup_{\eta\in\mathcal{H}}\left| \Pr_{x\sim \mathbb{D}_S^X}\left[ \eta(x_i)=1\right] - \Pr_{x\sim \mathbb{D}_T^X}\left[ \eta(x_i)=1\right]\right|. $$
단, 여기서 the hypothesis class $\cal{H}$는 이진 classifiers $\eta : X \rightarrow\{0,1\}$들의 집합.

오 이건 또 무슨 수식의 향연이란 말인가...하시는 분을 위해 정리해보겠습니다.

(대학원생의 풀이)
$\cal{H}$라는 hypothesis class가 있어서 그 공간에는 여러 $\eta$(classifier)들이 살고 있습니다. 모든 $\eta$에 대해 $\mathbb{D}_S^X$와 $\mathbb{D}_T^X$로부터 나온 sample들을 건내주고 위의 절대값 안의 수식을 계산해서 가장 큰 값이 무엇인지를 확인하면 그 값을 $\cal{H}$-divergence라고 정의하겠다는 말이죠.

언제 저 값이 작아지는지를 생각해보겠습니다. 예를 들어 $\cal{H}$ class에서 놀고있는 $\eta$ 한 녀석은 Domain이 어디든 간에 상관 없이 둘 다 1(class label)이라 할 확률이 1(즉, 100%)이라고 해보겠습니다. 그렇단 말은 적어도 이 $\eta$에 대해서는 Domain들이 구별이 안 된다는 얘기입니다. 우리가 원하는 방향이죠.

그런데 하필 모든 $\eta\in \cal{H}$에 대해 확인해보아도 다 위와 같이 구별을 못 한다고 생각해보면 결과적으로 supremum 값이 0입니다. 즉 이럴 경우, 두 domain $\mathbb{D}_S^X$와 $\mathbb{D}_T^X$의 $\cal{H}$-divergence 값이 0이 됩니다.

절대값이 씌워져 있기 때문에 지금 고려한 경우 외의 다른 경우들에 대해서는 당연히 모두  divergence 값이 양수가 되겠습니다.

이와 같이 theorem의 수식 그대로 보아도 이해가 크게 어렵지는 않습니다만 좀 더 쉽게 이해하려면 다음과 같이 풀어 생각하는 것이 편합니다:
$$ \begin{align} \hat{h}_{\mathcal{H}}(\mathbb{D}_S^X,\mathbb{D}_T^X) &= 2\sup_{\eta\in\mathcal{H}}\left| \Pr_{x\sim \mathbb{D}_S^X}\left[ \eta(x_i)=1\right] - \Pr_{x\sim \mathbb{D}_T^X}\left[ \eta(x_i)=1\right]\right| \\ &=2\sup_{\eta\in\mathcal{H}}\left| \Pr_{x\sim \mathbb{D}_S^X}\left[ \eta(x_i)=1\right] + \Pr_{x\sim \mathbb{D}_T^X}\left[ \eta(x_i)=0\right]-1\right| \end{align}$$

|1-잘못 구별할 확률|이므로 잘 구별할 확률의 maximum이 곧 divergence 값과 같다고 생각하면 되겠습니다. 

어때요 참 쉽죠?

이 때, 한 가지 염두에 둘 점이 있습니다. 위의 divergence는 class $\cal{H}$ 안에서만 $\eta$를 찾아보기 때문에 $\cal{H}$의 capacity가 매우 중요합니다. 우리가 고려한 class $\cal{H}$에 divergence 값이 0가 되도록 해줄 수 있는 $\eta$가 없을지라도, 다른 공간에 있는 $\eta$는 이를 만족할 수도 있단 말입니다. 이렇게 $\cal{H}$가 무엇이냐에 따라 divergence의 값이 바뀔 수 있기 때문에 굳이 $\cal{H}$-divergence라고 이름 붙여준 것이라 생각됩니다.

그러면 그냥 $\cal{H}$의 capacity를 무한으로 하여 모든 경우에 대해 해보면 되지 않겠는가?....
.....음 그러면 안 됩니다. 사실 이 부분을 잘 이해하려면 기계 학습 분야에서도 이론 부분인 statistical learning theory에 대한 지식이 좀 필요합니다.

Statistical Learning Theory와 SVM의 아버지

* 아는 분은 다 아는 우리 Vapnik 선생님...괜히 머신러닝하면 만나는 사람의 분류 중 하나에 joke인 듯 아닌 듯 "The Russian"이 들어가는 것이 아니라는...

아주 간단히 소개를 하자면, 우리가 구하고자 하는 (하지만 실제로 구하거나 알 수는 없는) true minimum risk 값의 upper bound를 (우리가 계산할 수 있는) empirical risk + model complexity로 나타낼 수 있는데 만약 capacity를 무한하도록 하면 empirical risk가 0인 model을 구할 수도 있겠지만 반대급부로 model complexity가 매우 커져서 결과적으로 원하는 upper bound가 커지기 때문에 true minimum risk에 가까운 모델을 구하기는 어려워집니다.

Overfitting의 문제도 이와 아주 큰 관계가 있습니다. 많이들 드는 예로 복잡한 모델을 쓰면 어떤 training data에 대해서도 완벽히 classify or fitting을 할 수 있는 모델을 찾을 수 있지만(empirical error is zero) 대신 test data에 대해서는 working poorly 하는 것을 볼 수 있죠. 따라서 complexity가 매우 큰 모델까지도 포괄하도록 hypothesis space의 capacity를 잡는 것보다 오히려 적절한 trade-off를 통해서 empirical error를 조금 허용하더라도 단순한 모델들을 사용하는 것이 더 좋은 결과를 얻을 수 있다는 얘기입니다.

이런 theoretical machine learning 분야도 상당히 재미있고 신기한 내용이 많은데 여력이 닿는다면 다음 기회에 글로 정리를 해보겠습니다. 연구실에서는 이미 발표를 다섯 번에 걸쳐서 했지만 이걸 글로 정리하려면 하세월일 것 같아서요...ㅎㅎ

아무튼 사족이 길었습니다만, Ben-David et al. 2010 논문 lemma 2를 확인해보시면 symmetric hypothesis class $\cal{H}$에 대해서는 아래와 같이 empirical estimate $\hat{d}_{\cal{H}}(S,T)$를 구할 수 있고:
$$ \hat{d}_{\mathcal{H}}(S,T) = 2\left(1-\min_{\eta\in\mathcal{H}} \left[\frac{1}{n}\sum_{i=1}^n I \left[ \eta(x_i)=1\right] + \frac{1}{n'}\sum_{i=n+1}^N I \left[ \eta(x_i)=0\right]\right]\right), $$
true $\cal{H}$-divergence $d_{\cal{H}}(\mathbb{D}_S^X,\mathbb{D}_T^X)$가 이렇게 구한 $\hat{d}_{\cal{H}}(S,T)$와 model complexity에 따라 정해지는 상수 값으로 upper bound 된다는 것을 보여줬습니다(여기서 $I\left[a \right]$는 $a$가 true면 1 아니면 0인 indicator function). 해당 논문 Appendix에 아주 상세히 증명이 나와있고 straight-forward하기 때문에 여기서는 증명을 생략하겠습니다.
(* 한 가지 체크해보셔야 할 점이 있긴 합니다. Ben-David et al. 2010 논문도 그렇고 DANN 논문도 그렇고 모두 $\frac{1}{n}\sum_{i=1}^n I \left[ \eta(x_i)=1\right] + \frac{1}{n'}\sum_{i=n+1}^N I \left[ \eta(x_i)=0\right]$ 부분에서 Indicator function 안의 binary 값을 $\frac{1}{n}\sum_{i=1}^n I \left[ \eta(x_i)=0\right] + \frac{1}{n'}\sum_{i=n+1}^N I \left[ \eta(x_i)=1\right]$과 같이 제가 써둔 것과는 반대로 적어두었는데요 이러면 수식의 의미가 반대로 꼬이기 때문에 아.마.도. typo가 아닌가 싶습니다. 원 논문 수식대로 생각해서 보면 classifier가 완벽히 working할 때 $\cal{H}$-divergence가 작아지는데...이상하지 않나요?)
(** 아래 참고문헌으로 넣은 poster에는 또 제가 설명한 방식대로 적혀 있습니다...)
(*** 만약 내가 맞다면....아 이렇게 논문에서 critical한 부분에 typo가 있으면 어쩌란거냐!)

저기 수식의 minimization 부분을 보면 classification error $\epsilon$과 같다는 것을 알 수 있습니다;
$$\hat{h}_{\mathcal{H}}(S,T) = 2\left(1-2\epsilon \right)$$
항상 그렇듯이 수식을 이해하려면 극단적 예시를 대입해 보는 것이 최고입니다. 만약 classifier가 sample이 source domain과 target domain 중 어느 domain에서 비롯하였는지 정확히 구별을 할 수 있다면, $\epsilon =0$입니다. 따라서 $\hat{h}_{\mathcal{H}}(S,T) =2$로 source domain과 target domain의 차이가 매우 커서 classifier가 두 domain을 구별하기가 쉬웠다는 것이죠. 반대의 경우는 $\hat{h}_{\mathcal{H}}(S,T) = -2$로 값이 최소가 되겠네요.

이제 슬슬 수확을 할 때 입니다. 앞서 "어떻게?" 에 대한 답을 다시 상기해보겠습니다. Domain adaptation을 잘 하기 위해서는 empirical classification error $R_{S}(\eta)$를 줄이고 동시에 $\hat{d}_{\cal{H}}(S,T)$+model complexity로 이루어진 $\cal{H}$-divergence 역시 줄여야합니다.  이를 정리하면 다음과 같습니다:

(Ben-David et al.,2006) Let $\mathcal{H}$ is a hypothesis class of VC dimension $d$. With probability $1-\delta$ over the choice of samples $S\sim(\mathbb{D}_S)^n$ and $T \sim (\mathbb{D}_T^X)^n$, for every $\eta\in\mathcal{H}$: $$ \begin{align} R_{\mathbb{D}_T}(\eta) \leq &R_{S}(\eta) + \sqrt{\frac{4}{m}(d\log\frac{2em}{d}+\log\frac{4}{\delta})}\\ &+ \hat{d}_{\mathcal{H}}(S,T) + 4 \sqrt{\frac{1}{m}( d\log\frac{2m}{d}+\log{4}{\delta})}+ \beta, \end{align}$$ with $\beta \geq \inf_{\eta^*\in\mathcal{H}}\left[ R_{\mathbb{D}_S}(\eta^*) + R_{\mathbb{D}_T}(\eta^*) \right]$, and $$R_{S}(\eta) = \frac{1}{m}\sum_{i=1}^m I\left[ \eta(x_i) \neq y_i \right]$$ is the empirical source risk.

음 여기 나오는 VC dimension 역시도 위에 그림에서 나오는 Vapnik 교수님의 V를 따서 나온 개념인데, 여기서 소개하는 것은 범위를 넘어가므로 hypothesis class의 capacity를 나타내는 값이라 생각하고 넘어가시면 되겠습니다.
(이 부분도 역시 statistical learning theory 이야기를 할 때 같이 풀어보겠습니다. 어떻게 글을 쓰는데 점점 더 쓸 것들이 늘어가는 느낌이지;;)

(대학원생의 풀이)
앞서 언급한 바와 같이, $R_{\mathbb{D}_T}(\eta)$가 작으려면 $R_{S}(\eta)$와 $d_{\cal{H}}(\mathbb{D}_S^X,\mathbb{D}_T^X)$이 동시에 작아야하는데 $d_{\cal{H}}(\mathbb{D}_S^X,\mathbb{D}_T^X)\leq\hat{d}_{\cal{H}}(S,T)$ + $\cal{O}(\sqrt{d\log d})$이므로 위와 같은 수식이 나옵니다.
재미있는 것은 $\beta$를 잘 보시면 $S$와 $T$에서 모두 잘 분류하는 classifier $\eta^*$가 $\cal{H}$에 존재할 때 최소값을 갖는 것을 알 수 있습니다. 따라서 $\cal{H}$의 capacity가 적절히 커서 $\eta^*$을 포함하되  $d_{\cal{H}}(\mathbb{D}_S^X,\mathbb{D}_T^X)$의 upper bound에 $\cal{O}(\sqrt{d\log d})$가 있으므로 너무 커서도 안 됩니다. 원래 인생에 거저먹기란 없고 trade-off가 항상 있는 법이죠.

이로써 논문에서 얘기하고자하는 Domain Adaptation의 개념과 문제 설정 그리고 문제를 풀 전략과 배경 이론까지 살펴보았습니다! 

사실 이 정도면 논문의 거의 모든 내용을 리뷰한 것인데요 원래 목표는 간단한 예시 문제(two moon data)를 MATLAB으로 짠 코드와 함께 푸는 것까지 소개하는 것이었으나.............

orz... 제 잉여력의 부족과 분량 조절을 위해서 오늘은 이 정도에서 마치겠습니다. 다음 번에 진짜로! MATLAB 코드와 함께 pseudo code에 대한 내용을 올리겠습니다.

언제나 그렇듯이 이해가 안 가는 내용이 있거나 오류가 있는 부분을 발견하신다면 댓글로 피드백을 주세요 감사합니다.

다음 읽을거리

• 초짜 대학원생의 입장에서 이해하는 Domain-Adversarial Training of Neural Networks (DANN) (3)
• 초짜 대학원생 입장에서 이해하는 Generative Adversarial Nets (1)
• 초짜 대학원생 입장에서 이해하는 Generative Adversarial Nets (2)

참고문헌:

[1] Domain-Adversarial Training of Neural Networks -  Yaroslav Ganin 2016

[2] A Survey on Transfer Learning - SJ Pan et al. 2010

[3] Analysis of Representations for Domain Adaptation - S Ben-David et al. NIPS 2004 

[4] A theory of learning from different domains - S Ben-David et al. 2010  (long version)

다 읽은 후 정리할 때 좋을 자료: 

[1] DANN 발표 슬라이드

[2] DANN poster