2017년 6월 22일 목요일

[PR12-Video] 13. Domain Adversarial Training of Neural Networks


TensorFlowKR facebook comunity에서 모인 12명의 paper readers (PR12)가 읽어주는 Deep learning paper awesome list 100선 by Terry Um.

#13. Domain Adversarial Training of Neural Nets


여전히 매주 일요일마다 12명이 돌아가며 두 명씩 두 편의 논문을 40분 동안 발표하고 있습니다. 벌써 한 번 순서가 다 돌아서 다시 제 차례가 되어 이번에는 GAN과도 관련이 있지만 또 다른 커다란 분야인 Domain Adaptation 연구를 소개하였습니다. 아직도 이런 경험이 부족하고 전달하고픈 내용은 많고 하필 논문에는 수식이 많아 발표 시간이 부족하네요. 그래도 이번에는 끝까지 다 발표를 마쳤습니다.

슬라이드: https://www.slideshare.net/thinkingfactory/pr12-dann-jaejun-yoo

동영상이 너무 길다 싶으신 분은 아래 링크에서 DANN 포스팅을 읽으셔도 됩니다 :)
다음에 또 다른 주제로 뵈어요~!

다른 분들의 발표도 보고 싶다면: PR12 딥러닝 논문읽기 모임

다음 읽을거리






초짜 대학원생의 입장에서 이해하는 f-GAN (2)

* f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization, Sebastian Nowozin et al. 2016을 바탕으로 한 리뷰

지난 글에서 f-divergence를 estimate하기 위해 시작한 전개로부터 일반적인 GAN objective까지 전개하는 것을 따라가 보았습니다. 이제는 이를 풀 알고리즘과 convergence를 증명하는 부분이 남았는데요. 본격적으로 들어가기 전에 지난 내용을 리뷰하고 GAN formulation과의 관계에 대해 약간 더 구체적으로 이해하기 위해 조금 더 설명을 해보도록 하겠습니다.

먼저 설명의 편의를 위해 지난 글에서 전개했던 variational representation을 가져오면 다음과 같고:

여기서 우리는 맨 마지막 식을 사용하여 true distribution $P$를 generative model $Q$로 estimate할 것입니다.




2017년 6월 18일 일요일

초짜 대학원생의 입장에서 이해하는 f-GAN (1)

* f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization, Sebastian Nowozin et al. 2016을 바탕으로 한 리뷰

오랜만에 다시 GAN으로 돌아와서 포스팅을 해봅니다. 요즘은 너무 GAN쪽 연구가 많이 그리고 빨리 발전하고 있어서 글을 리뷰하는 것이 민망할 지경입니다. 심지어 응용뿐 아니라 이론적인 부분에서도 꽤나 많은 부분이 연구되고 바뀌고 있기에 따라가기가 벅찹니다. 

이 논문만 해도 작년 6월 arXiv에 올라왔고 NIPS 2016 워크샵에서 발표하는 것을 직접 들었었는데 이게 한~~~~~~참 전 논문으로 취급되고 있는 것을 보면 머신러닝 분야는 참 짧은 시간에 격세지감 느끼기 좋은 분야인 것 같습니다...orz

WGAN 이전에는 f-GAN 논문이 다른 연구들을 모조리 잡아먹는? 느낌을 주었으나 이제는 이 말도 무색할 지경입니다. 그래도 f-GAN 논문은 여러모로 GAN 분야에서 매우 중요한 milestone이기 때문에 사실 다른 것보다 더 먼저 리뷰했어야 하는데 여러 이유로 블로그 글로 정리하지 못해서 항상 마음에 걸렸습니다.

아무튼 이 논문이 마치 어제 나온 것인양! 한 문장으로 요약해보자면 다음과 같습니다:

"앞으로 너희가 어떤 divergence를 사용해서 GAN을 구성하든지 모두 다 나의 하위 호환(special case)일 따름이다."

...패기롭다....ㅋㅋ

이 때만 해도 vanilla GAN objective가 JSD를 이용해서 $p_{model}$과 $p_{data}$의 차이를 계산하는 것이란 분석을 바탕으로, 조금씩 네트워크의 구조를 바꾸거나 regularization term을 새로 붙여본다거나 하는 등 약간의 변화만 주고 있던 때라는 점을 생각해보시면...

이렇게 근간을 쥐고 흔드는 내용을 NIPS 2016 워크샵에서 얘기해줄 때 이제 막 혹시 다른 divergence는 어떨까 하면서 새로운 GAN 형태를 연구해보던 사람들은 어떤 느낌이었을까요? 저는 그 때서야 갓 GAN을 접하던 시기(사실 처음 그곳에서 GAN이란 게 있단 것을 알았습니다ㅎㅎ)라 잘 못 느꼈습니다만 기존에 연구를 하던 사람들에게는 꽤나 충격적이었을 것으로 보입니다.

아무튼 오늘은 이 f-GAN에 대해 차근차근 알아보도록 하겠습니다.




2017년 6월 11일 일요일

초짜 대학원생의 입장에서 이해하는 The Marginal Value of Adaptive Gradient Methods in Machine Learning (2)

* The Marginal Value of Adaptive Gradient Methods in Machine Learning, Ashia C. Wilson et al. 2017을 바탕으로 한 리뷰

글이 나누어 져서 보시기가 불편하실까봐 한 번 더 우리가 풀 문제를 정리해보겠습니다.

Previously,


지난 시간에 $\tilde{\nabla}f(w_k):=\nabla f(w_k;x_{i_k})$가 data batch $x_{i_k}$에 대한 loss function $f$의 gradient일 때, non-adaptive, adaptive methods들을 다음과 같이 일반화했었습니다:
\begin{equation*}w_{k+1}=w_k-\alpha_kH_k^{-1}\tilde{\nabla}f(w_k+\gamma_k(w_k-w_{k-1}))+ \beta_kH_k^{-1}H_{k-1}(w_k-w_{k-1}).\end{equation*}
이 때, $H_k:=H(w_1,\cdots,w_l)$는 positive definite matrix이며, 필수적인 것은 아니지만 문제를 좀 단순화하기 위해 $H_k$를 다음과 같이 놓습니다: $$H_k=diag\left(\left\{\sum_{i=1}^k\eta_ig_i\circ g_i\right\}^{1/2}\right).$$ 여기서 $\circ$는 Hadamard product이고 $g_k=\tilde{\nabla}f(w_k+\gamma(w_k-w_{k-1}))$이며, $\eta_k$는 각 알고리즘마다 특화된 coefficients set이라고 생각하시면 됩니다.

Preconditioning의 문제점


이 논문에서는 AdaGrad, RMSProp, Adam 등의 adaptive methods가 사용하는 여러 방식의 변주들을 preconditioning이라는 단어로 묶어서 표현합니다.

Non-adaptive methods와 비교할 때 multiple global minima를 갖는 문제에서 adaptive methods는 알고리즘에 따라 서로 완전히 다른 해들이 나올 수 있다는 것을 보여주는데요. 이 때 보다 간단히 문제를 이해하기 위해 다음과 같은 binary least-square classification 문제로 설정하여 이를 확인해보고자 합니다: \begin{equation}\min_w R_S[w]:=||Xw-y||^2_2.\label{eq4}\end{equation} 위의 문제에서 $X$는 $d$ dimensional feature들이 $n$개 sample에 대해 있는 $n \times d$ matrix이며 $y$는 $\{-1,1\}$를 label set으로 갖는 $n$ dimensional vector입니다. 우리는 이제 가장 적합한 linear classifier $w$를 찾기만 하면 되는 것이죠.

이전 글에서 Non-adaptive methods는 식 \ref{eq4}에 대해 minimum $l_2$ norm 을 갖는 해 $$w^{SGD}=X^T(XX^T)^{-1}y$$로 동일하게 수렴을 하는 반면, adaptive methods는 특별한 경우에 한하여 분석한 것이긴 합니다만 lemma 1에서 얘기한 조건이 맞는 경우, 앞서 소개한 모든 adaptive methods는 언제나 $w\propto sign(X^Ty)$인 해로 수렴한다는 것을 보여줍니다.

이번 글에서는 이 lemma에 대한 증명을 시작으로 "Adaptivity can overfit"에 대한 내용을 다뤄보도록 하겠습니다.
Suppose $X^Ty$ has no components equal to $0$ and there exists a scalar $c$ such that $X sign(X^Ty)=cy$. Then, when initialized at $w_0=0$, AdaGrad, Adam, and RMSProp all converge to the unique solution $w\propto sign(X^Ty)$.
증명이 생각보다 매우 쉽습니다. 먼저 이 lemma를 증명하기 위해 어떤 전략을 사용할 것인지 설명드리겠습니다. 위에 lemma에서 설정한 $Xsign(X^Ty)=cy$인 scalar 값 $c$가 존재한다는 조건이 성립한다는 것을 전제로 다음식에 대해 귀납법을 통해 증명을 할 것입니다: $$w_k = \lambda_k sign (X^Ty).$$ 먼저 이 식이 $k=0$일 때, $w_0=0$으로 initial 값을 주면 $\lambda_k=0$로 성립을 합니다. 귀납법의 첫째 단계는 통과했으니 다음 단계로 $k\leq t$일 때 assertion이 holds한다면  어떻게 되는지 확인해보시죠:
\begin{align*} \nabla R_S(w_k+\gamma_k(w_k-w_{k-1})) &= X^T(X(w_k+\gamma_k(w_k-w_{k-1}))-y) \\ &= X^T\{(\lambda_k+\gamma_k(\lambda_k-\lambda_{k-1}))Xsign(X^Ty)-y\}  \\
&= \{\lambda_k +\gamma_k(\lambda_k-\lambda_{k-1}))c-1\}X^Ty \\
&= \mu_k X^Ty. \end{align*}
첫번째 등호에서 두번째 등호로 넘어가는 것은 $w_k = \lambda_k sign (X^Ty)$를 대입한 것이므로 간단합니다. 세번째 등호로 넘어가는 것 역시 가정에 의해 $Xsign(X^Ty)=cy$를 만족하는 $c$가 있으므로 이를 대입합니다. 남아 있는 것은 상수들뿐이기 때문에 여기서 $\mu_k$는 마지막 식에 의해 자연스럽게 정의됩니다.

따라서 $g_k=\nabla R_S(w_k+\gamma_k(w_k-w_{k-1}))$로 놓으면,
\begin{align*} H_k &= diag\left( \left\{ \sum_{s=1}^k \eta_s g_s \circ g_s \right\}^{1/2} \right)= diag\left( \left\{ \sum_{s=1}^k \eta_s \mu_s^2 \right\}^{1/2} |X^Ty| \right) \\&= \nu_k diag(|X^Ty|) \end{align*} 여기서 $|\cdot|$는 component-wise 절대값입니다 그리고 역시 마지막 식으로 $\nu_k$를 정의됩니다.

따라서 앞서 정의했던 $w$ update 식에 의해
\begin{align*}  w_{k+1}&=w_k-\alpha_kH_k^{-1}\tilde{\nabla}f(w_k+\gamma_k(w_k-w_{k-1}))+ \beta_kH_k^{-1}H_{k-1}(w_k-w_{k-1}) \\
&= \left\{ \lambda_k - \frac{\alpha_k \mu_k}{\nu_k} + \frac{\beta_k\nu_{k-1}}{\nu_k}(\lambda_k-\lambda_{k-1}\right\} sign(X^Ty) \end{align*} 가 되고 $\tilde{\nabla}f$는 위에서 구한 $\nabla R_S$를 대입한 것입니다. 이로써 마지막 줄이 결국 $k+1$에 대해서도 식이 성립하는 것을 보였으므로 증명이 끝납니다.  

이 lemma에 의해 $X sign(X^Ty)=cy$를 만족하는 상수 $c$가 존재하고 $Xw = y$의 문제에 대해 $sign(X^Ty)$에 비례하는 해 $w$가 있을 경우, adaptive methods는 언제나 그 해로 수렴한다는 것입니다. 이렇게 간단한 해가 새로운 데이터에 대해 일반화가 잘 된다면 그게 더 신기한 일이겠죠. 실제로 이런 해들이 일반화에 관점에서 상당히 좋지 않다는 것을 다음 단락에서 보여줍니다.

Adaptivity can overfit


이제 생각보다 범용적인 상황의 간단한 예제에서 위에 lemma 1의 조건이 성립하는 경우 실제로 AdaGrad가 좋은 해(일반화가 잘 되는)를 찾지 못하는 것을 보여드리겠습니다. 

이 예제는 간단하게 설명을 하기 위해 infinite dimensions를 사용합니다만 $n$개의 sample들에 대해 parameter dimension이 $6n$개를 만족하기만 하면 됩니다. 보통 실제 상황에서는 parameter의 수가 보통 $25n$이나 그 이상임을 생각하면, 이 예제의 설정이 이상한 것이 아닙니다.

Sample $i=1,\cdots,n$개에 대해  label $y_i$가 $p>1/2$인 확률 $p$로 $y_i=1$, $1-p$의 확률로 $y_i=-1$이고 $x$가 다음과 같은 infinite dimensional vector라고 해보겠습니다:
$$x_{ij} =\left\{\begin{array}{lll} y_i\hspace{10pt}j = 1 \\
1 \hspace{10pt}j = 2,3 \\
1 \hspace{10pt}j = 4+5(i-1),\cdots,4+5(i-1)+2(1-y_i) \\
0 \hspace{10pt} otherwise  \end{array}\right.$$ $x$의 구조를 잘 살펴보시면 $x_i$의 feature라고 할만한 것은 class label을 갖는 첫번째 element뿐입니다. 다음 두 element들은 항상 1이고 그 이후로는 $x_i$에 대해 unique하기 때문에 sample의 label을 구별하는데 전혀 도움이 되지 않습니다. 예를 들어 sample $x_i$의 class가 1이면 한 slot만 1이고 class가 $-1$이면 5개 slot에 1이 들어가 마치 $x_i$에 대한 code와 같이 값이 들어가 있는 형태입니다.

즉, 첫번째 element만을 잘 뽑아내면 완벽한 classification이 가능합니다. 다만 이런 선행 정보가 전혀 없다면 adaptive methods가 $arg\min_w||Xw-y||^2$ 문제를 풀 때 이러한 classifier를 전혀 찾지 못한다는 것을 확인해보겠습니다.

먼저 이 문제가 lemma에서 얘기한 조건들을 만족한다는 것부터 보여야겠죠. $b=\sum_{i=1}^ny_i$이고 편의상 $b>0$라 할 때 (상당히 높은 확률로 large enough $n$에 대해 그럼직하죠),  $u=X^Ty$라고 정의하면 $u$의 구조는 아래와 같습니다:



따라서 일단 $u$의 elements 중 값이 0인 원소가 존재하지 않아 lemma의 첫번째 조건을 만족하며, 두번째 조건 역시  *$<sign(u),x_i>=y_i+2+y_i(3-2y_i)=4y_i$이므로 scalar $c=4$가 존재합니다. 그러므로 lemma에 의해 AdaGrad의 해는 $w^{ada}\propto sign(u)$가 됩니다.
* paper에는 $<sign(u),x_i>$가 아닌 $<u,x_i>$로 되어있는데 잘못으로 보입니다.

따라서 임의의 양의 상수 $\tau$에 대해 $w^{ada}$는 언제나 0 혹은 $\pm \tau$를 원소로 갖습니다. 이제 새로운 데이터 $x^{test}$에 대해 이렇게 구한 해가 어떤 식으로 반응하는지 생각해봅시다. $x^{test}$와 $w^{ada}$ 둘 다 0이 아닌 유일한 features는 첫 3개 dimensions뿐입니다. 나머지는 서로 unique한 위치에 값을 갖기 때문에 곱하면 0일뿐이죠. 따라서 $w^{ada}$는 다음과 같이 처음 보는 데이터에 대해 항상 positive class로 분류하게 됩니다!!:
$$<w^{ada},x^{test}>=\tau(y^{test}+2)>0.$$
그럼 minimum norm solution은 어떤지 확인해볼까요? $\cal{P}$와 $\cal{N}$이 각각 positive 그리고 negative 예제들의 집합을 나타낼 때, $n_+=|\cal{P}|$이고 $n_-=|\cal{N}|$라 합시다. 이 때, symmetry에 의해  우리는 minimum norm solution이 아래와 같은 음이 아닌 상수 $\alpha_+$와 $\alpha_-$에 대해 $w^{SGD}=\sum_{i\in\cal{P}} \alpha_+ x_i -\sum_{j\in\cal{N}} \alpha_{-}x_j$ 와 같은 형태를 갖는 다는 것을 알 수 있습니다:


이 수식과 상수들을 계산하는 법은 논문의 Appendix를 참고하시면 됩니다 (논문의 주안점이 아니기 때문에 굳이 설명하지 않겠습니다).

우리가 원하는 것은 이런 해가 새로운 데이터에 대해 어떻게 반응하냐는 것이었죠? 위와 마찬가지로 $x^{test}$가 들어왔을 때, $x^{test}$와 $w^{SGD}$ 둘 다 0이 아닌 유일한 features는 첫 3개 dimensions뿐입니다:
$$<w^{SGD},x^{test}>=y^{test}(n_+\alpha_++n_-\alpha_-) + 2(n_+\alpha_+-n_-\alpha_-).$$
앞서 계산한 상수 $\alpha_+$와 $\alpha_-$에 의해 $n_+>N_-/3$일 때는 SGD는 언제나 제대로 분류를 한다는 것을 알 수 있습니다.

물론 이 예제가 약간 극단적이라 생각할 수 있습니다만, 생각보다 우리가 마주하는 기계학습 예제들의 상황과 상당히 비슷한 특징들을 잘 보여주고 있습니다. 보통 몇몇 feature들만을 사용하면 상당히 좋은 predictor를 만들 수 있지만 이를 처음부터 딱 알기는 쉽지 않습니다 (마치 첫번째 원소만 사용하면 되지만 선행지식이 없어 그렇게 classifier를 구성하지 못한 것과 같이). 게다가 많은 경우, 데이터의 feature들이 매우 sparse합니다. Training data가 finite할 경우 이런 feature들이 training data를 구별하는 것에는 매우 좋아 보일 수 있으나 사실 그 값들이 artifact로 인한 noise일 수도 있고 이에 맞춰 classifier를 만들 경우 over-fitting 현상이 생길 우려도 있기에 좋다고 할 수는 없습니다.

이 논문에서는 앞서 설명한 이론적 분석에 더불어서 실험적으로도 adaptive methods들로 구한 해들이 generalization performance가 non-adaptive methods로 구한 해에 비해 좋지 않다는 것을 확인해주는데요. 이 부분은 결과를 보시면 되기 때문에 이 글에서는 굳이 더 설명하지 않도록 하겠습니다.

내 멋대로 정리 및 결론


다시 한 번 이 논문에서 저자들이 주장하는 내용을 요약해보자면 아래와 같습니다:

  1. 같은 수의 hyperparameter tuning을 할 때, SGD와 SGD+momentum이 여타 adaptive methods들보다 모든 모델과 task들에 대해 dev/test set에서 우월한 결과를 보여줌.
  2. Adaptive methods들이 초기 학습 속도는 빠른 모습을 종종 보이긴 하지만 dev/test set에서 성능이 증가하는 것 역시 더 빠르게 더뎌지는 모습을 보임.
  3. Adaptive methods들이 주장하는 장점인 "less tuning needed"와는 다르게 모든 methods들에 동일한 정도의 tuning이 필요했음.

다만 GAN이나 Reinforcement Learning 분야의 경우 Adam이나 RMSProp과 같은 adaptive methods가 매우 잘 들어맞는 경우가 있고 이런 경우에 대해서는 저자들도 정확히 이유를 알지 못하겠다고 결론을 내립니다. 다음과 같이 추측을 할뿐인데요 이 부분은 뉘앙스가 애매할 수 있으므로 원문을 그대로 가져와 보겠습니다.
In our conversations with other researchers, we have surmised that adaptive gradient methods are particularly popular for training GANs [5, 18] and Q-learning with function approximation [9, 13]. Both of these applications stand out because they are not solving optimization problems. It is possible that the dynamics of Adam are accidentally well matched to these sorts of optimization-free iterative search procedures.
이 부분들은 사실 좀 애매한데요 GAN은 아마도 saddle 문제이기 때문에 이렇게 얘기하는 것 같습니다. Q-learning의 경우에도 전원석님이 답변해주신 내용을 여기에 정리해보자면 다음과 같습니다.
Deep reinforcement learning에서 RMSProp을 쓰는 주된 이유 중에 하나는 현재의 gradient update로 policy가 크게 바뀌면 앞으로 들어올 data가 망가지고 다음 policy에 악영향을 미쳐 전체 학습을 망치게 되는데 이를 방지하기 위함으로 알고 있습니다. 논문에서 최적화 문제가 아니라고 함은 아마 주어진 데이터셋이 있고 loss minimization을 하는 상황이 아니라는 걸 의미하지 않나 생각합니다.
결국 제가 보기에는 이 논문의 캐치 프레이즈였던 "SGD를 써라!"는 역시 case by case인 것으로 생각됩니다. 여전히 우리가 예측하지 못하는 혹은 보지 못하는 dark matter가 DL에는 남아있고 (물론 저자들은 자신들이 설정한 예제가 꽤나 broad한 설정이라고 주장하고 있지만) 항상 장님 코끼리 만지고 있는 것과 같이 매우 일부분의 degenerate한 경우일 수 있기에 이 논문만을 믿고 SGD만 사용하기보다는 역시 여러 시도를 해보는 수 밖에 없다는 어찌보면 싱거운? 결론에 이릅니다. 

DARK MATTER IN DEEP LEARNING

하지만 여전히 이렇게 이론적으로 Deep learning의 요소들을 파헤쳐 설명하고자 하는 theoretical machine learning 분야는 참 매력적인 분야입니다. 왜 DL이 잘 working하는가를 설명하면서 새로운 디자인 방식과 같은 내용을 제안하는 연구들을 보면 매우 멋지죠. 제 꿈 중 하나가 이렇게 DL의 working principle을 이론적으로 파헤치는 것인데요 아직은 내공이 매우 부족하여 꿈으로만 그치고 있습니다. 느리더라도 거북이 같이 공부를 하다보면 언젠가는 닿을 수 있길 기대하고 있습니다. 

다음 읽을거리



참고문헌:



2017년 6월 9일 금요일

RNN implementation using only Numpy (.ipynb with ENG, KOR explanations / Binary operation: addition)


Anyone can Learn To Code an LSTM-RNN in Python

[Refercence]
If you want more detailed background with explanations about RNN:
원문 링크 (Eng): https://iamtrask.github.io/2015/11/15/anyone-can-code-lstm/
번역 링크 (Kor): http://jaejunyoo.blogspot.com/2017/06/anyone-can-learn-to-code-LSTM-RNN-Python.html
깃헙 레포 (Kor, Eng): https://github.com/jaejun-yoo/RNN-implementation-using-Numpy-binary-digit-addition

[목표]

  • 간단한 toy code로 RNN을 이해한다.
  • RNN을 사용하여 이진수 더하기 연산을 학습시킨다.

[objective]

  • Understand RNN with a simple numpy implementation.
  • Train RNN for a binary opperation, e.g. addition.
  • Check if the trained RNN can be extended for the unseen data with longer digits (e.g. 8 bytes digits training -> 10 bytes digit test)




2017년 6월 7일 수요일

(한글 번역) Anyone Can Learn To Code an LSTM-RNN in Python (Part 1: RNN)

: Baby steps to your neural network's first memories.

* This is the Korean translation of the original post by @iamtrask under his permission. You can find the English version at his blog: here저자의 허락을 득하고 번역하여 옮깁니다. 

# 여기 나오는 예제에 제가 조금 더 내용을 추가한 것을 ipynb으로 만들어 정리해보았습니다.
* github 링크: https://github.com/jaejun-yoo/RNN-implementation-using-Numpy-binary-digit-addition
* blog 링크: http://jaejunyoo.blogspot.com/2017/06/rnn-implementation-using-only-numpy.html

요약: 저는 제가 다루기 쉬운 toy code를 가지고 놀 때 가장 잘 배우는 것 같습니다. 이 튜토리얼은 매우 쉬운 예제와 짧은 파이썬 코드를 바탕으로 Recurrent Neural Networks (RNN)에 대해 설명을 진행합니다. 

(원작자: Part2: LSTM에 대해서는 작성이 완료되는대로 @iamtrask에 트윗할 것이니 팔로우 해주세요. 어떤 피드백이든 환영입니다.)