Jaejun Yoo's Playground: 초짜 대학원생의 입장에서 이해하는 f-GAN (3)

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

자 오늘은 f-GAN의 main theorem을 증명하고 저자가 NIPS 2016 workshop에서 발표할 때 전해줬던 insight 하나를 소개하는 것으로 f-GAN에 대한 설명을 마무리하겠습니다. 먼저 설명의 편의를 위해 오늘 증명할 Theorem 1과 그 조건을 다시 가져와보겠습니다.

지난 글에서 f-GAN 저자들이 Single-Step 알고리즘을 제안하였던 것을 기억하실겁니다:

우리가 풀고자 하는 GAN objective 함수 $F$에 대하여, 우리가 찾고 싶은 saddle point의 근방(neighborhood)에서 $F$가 strongly convex in $\theta$ 그리고 strongly concave in $w$일 때, 이 알고리즘이 실제로 그 saddle point $(\theta^t,w^t)$에 수렴한다는 것을 확인해보겠습니다. 이 조건들을 수식으로 나타내면 다음과 같습니다:
\begin{equation}\nabla_\theta F(\theta*,w*)=0, \nabla_w F(\theta*,w*)=0, \nabla^2_\theta F(\theta,w) \succeq \delta I, \nabla^2_w F(\theta,w)\preceq -\delta I.\label{cond}\end{equation}
이 가정들은 "strong"하다는 부분만 빼면 f-GAN 형태로 도출된 saddle point를 정의하기 위해서 필수적인 조건들입니다. 따라서 deep networks의 구조로 인해 생기는 수많은 saddle point들이 있습니다만 대부분이 이 조건을 만족하지 않습니다.

저는 이 부분을 GAN이 원하는 saddle point가 독특하고 GAN objective를 알고리즘을 적용하여 풀어서 나오는 solution들은 이러한 조건을 만족하는 point로 수렴한다는 것을 말하고자한 것으로 해석했습니다.

이제 이 조건이 성립한다는 가정하에 다음 정리가 성립하게 됩니다.

Suppose that there is a saddle point $\pi^*=(\theta^t,w^t)$ with a neighborhood that satisfies conditions \ref{cond}. Moreover, we define $J(\pi)=\frac{1}{2}||\nabla F(\pi)||^2_2$ and assume that in the above neighborhood, $F$ is sufficiently smooth so that there is a constant $L>0$ such that $||\nabla J(\pi')-\nabla J(\pi)||_2 \leq L||\pi'-\pi||_2$ for any $\pi,\pi'$ in the neighborhood of $\pi^*$. Then using the step-size $\eta=\delta/L$ in Algorithm 1, we have
$$J(\pi^t)\leq \left(1-\frac{\delta^2}{2L}\right)^t J(\pi^0).$$
That is, the squared norm of the gradient $\nabla F(\pi)$ decreases geometrically.

(우와 어려워보인다...) 아닙니다! 생각보다 쉬워요!

본격적인 증명에 앞서 이 복잡해보이는 정리가 의미하는 바를 좀 정리해보겠습니다. 이 정리는 알고리즘의 "local" convergence를 증명해주고 있습니다.

$J(\pi) \overset{\Delta}{=}\frac{1}{2}||\nabla F(\pi)||^2_2$로 정의한 것을 곰곰히 생각해보면 됩니다. 결국 이 정리에서 결론으로 내리는 부등호가 하고자 하는 말은 우리가 구하고자 하는 GAN objective $F$의 gradient인 $\nabla F(\pi)$의 크기가 점차점차 줄어든다는 것입니다. 즉, 수렴한다는 것이죠.

"어때요 참 쉽죠?"

다만, 우리가 saddle point의 근방에 있다면 언제나 saddle point로 수렴한다는 것을 증명한 것이지 global convergence를 증명해주진 못했습니다. 그러면 자연스럽게 떠오르는 의문이 있죠? "어떻게 그 근방에 갈껀데?" 네...그건 뭐 저자들도 "일단 practically 잘 되니까 쓰자"고 하네요 -_-ㅎㅎ (이전 글에서 두 가지 예를 보여드렸었죠?)

먼저 몇 가지 notation을 정하고 가겠습니다. 편의상 $\pi=(\theta^t,w^t)$라 정의하고 각각의 편미분을 다음과 같이 나타내겠습니다:
$$\nabla F(\pi) = \begin{pmatrix} \nabla_\theta F(\theta,w) \\ \nabla_w F(\theta,w) \end{pmatrix}, \tilde{\nabla} F(\pi) = \begin{pmatrix} -\nabla_\theta F(\theta,w) \\ \nabla_w F(\theta,w) \end{pmatrix}.$$
그러면 Algorithm 1은 다음과 같이 쓸 수 있게 됩니다:
\begin{equation}\pi^{t+1} = \pi^t + \eta \tilde{\nabla} F(\pi^t)\label{eq2}\end{equation}

이제 본격적으로 증명을 시작해보겠습니다. 기본적으로 증명에 쓰이는 가장 어려운 수준의 수학은 Taylor series 전개입니다. Taylor series를 이용하면,
\begin{equation}J(\pi')\approx J(\pi)+<\nabla J(\pi),\pi'-\pi>+\frac{1}{2}(\pi'-\pi)^T H(J(\pi))(\pi'-\pi). \label{eq3}\end{equation}
여기서 $H$는 Hessian matrix를 뜻합니다. 주어진 조건을 바탕으로 다음과 같은 부등호를 얻을 수 있고:
$$||\nabla J(\pi')-\nabla J(\pi)||_2 \leq L||\pi'-\pi||_2 $$
$$\lim_{\pi'\rightarrow \pi}\frac{||\nabla J(\pi')-\nabla J(\pi)||_2}{||\pi'-\pi||_2} \leq L $$
\begin{equation}\therefore H(J(\pi)) \leq L \label{eq4}\end{equation}
이렇게 얻은 부등호 eq.\ref{eq4}을 eq.\ref{eq3}에 적용하면,
\begin{equation}J(\pi')\leq J(\pi)+<\nabla J(\pi),\pi'-\pi>+\frac{L}{2}(\pi'-\pi)^T (\pi'-\pi). \label{eq5}\end{equation}
여기서 $J(\pi) \overset{\Delta}{=}\frac{1}{2}||\nabla F(\pi)||^2_2$이므로, $\nabla J(\pi)=\nabla^2 F(\pi)\nabla F(\pi)$입니다.

따라서, 다음과 같은 전개가 가능해집니다:

자, 이걸 곰곰히 생각해보시면 Algorithm 1이 해주는 일이란 것이 결국 $||\nabla F(\pi)||_2^2$에 비례하는 양으로 $J$를 줄여주고 있는 것이란 것을 아실 수 있습니다.

안 되요 안 되요! 정신줄 놓아버리시면 안 됩니다!! ㅋㅋ 뜬금없이 뭔소리냐 위에 부등식은 왜 갑자기 푸는가?가 궁금하시죠? Eq.\ref{eq2}와 eq.\ref{eq3}를 조금만 바꾸면 아래 과정을 왜 하는지 이해할 수 있습니다.

Algorithm 1이 eq. \ref{eq2}로 나타내진다고 했었죠? 이를 $\pi^{t+1} - \pi^t = \eta \tilde{\nabla} F(\pi^t)$로 조금만 바꾸고 eq.\ref{eq3}에 대입하면 이 짓을 왜 하는지 이해하실 수 있습니다:

$$J(\pi^{t+1})\leq J(\pi^t)+<\nabla J(\pi^t),\eta\tilde{\nabla} F(\pi^t)>+\frac{L\eta^2}{2}\tilde{\nabla} F(\pi^t)^T \tilde{\nabla} F(\pi^t). $$

자, 이렇게 하고 나니 아래의 수식 전개에서 두번째 부등호가 위에서 구한 부등호 때문이란 것을 알 수 있게 되는 것입니다:

여기서 마지막 equality는 $\eta = \delta/L$일 때 성립합니다. 그래서 step size $\eta$를 이렇게 정하면 위 부등식에 의해 local convergence가 보장되는 것이죠.

드디어 증명이 끝났군요 (에고 힘들다).

Discussion

그래요 이제 증명도 되었고 (local이긴 하지만), 여러가지 함수로 divergence를 바꿔가며 GAN을 해보면 그 때마다 새로운 녀석이 나올 것이고, 수학적으로는 어떤 divergence가 어떤 녀석보다 더 나은지 등등이 연구가 되어있기 때문에 이제 내 상황에서 가장 적절한 f-divergence를 만들어서 쓰기만 하면 될 것 같습니다.

그런데...대다수의 divergence가 잘 동작하긴 하는데....결과를 일단 먼저 보여드리자면:
(* LSUN dataset의 classroom에 대해서 학습을 시킨 것이고 각각 Jensen-Shannon, Hellinger, Kullback-Leibler divergence를 사용한 결과입니다)

GAN (Jensen-Shannon)

Hellinger

Kullback-Leibler

생각보다 결과가 그놈이 그놈이더라...하는 것입니다.

왜?!! 어째서?!!!

Insights from the Authors

자연스래 아래와 같은 질문이 나올 수 밖에 없죠.

"Does the divergence REALLY matter?"

그래서 저자가 한 가지 추측을 내놓는데 다음과 같습니다:

각각의 색으로 나타낸 점이 서로 다른 divergence로 학습한 수렴점이라고 생각하시면 됩니다. 이와 같이 우리가 세운 모델의 공간과 실제 확률 분포 $P$가 이렇게 꽤나 가까이에 있을 때는 divergence 간에 수렴점이 차이가 있습니다. 그런데 이게 아니라 다음과 같이 멀리 떨어져 있다고 해봅시다:

이러면 마치 태양에서 오는 빛은 직선이라고 생각할 수 있듯이 divergence 간에 차이가 매우 적어집니다. 즉, 저자들은 우리의 모델이 생각보다 실제 분포와 매우 멀리 떨어져 있는 것이 아닌가 하는 추측을 내놓는 것입니다.

매우 직관적이고 그럴 듯하죠? 이에 대한 토론이 NIPS 2016 Workshop 영상에서 보이듯이 발표 이후로도 이어졌습니다. 실제도 이런 추측이 최근 GAN에 대한 연구 결과들과도 어느 정도 부합하는 것 같습니다.

이로써 f-GAN에 대한 설명을 모두 마쳤네요. 슬슬 그래도 제가 생각한 골격을 하나하나 따라 올라가고 있습니다. 다음은 EBGAN을 리뷰할 생각입니다. EBGAN까지 하면 어느 정도 제가 구상했던 커다란 틀이 80% 정도는 완성되는 것입니다. 참 오래 걸리네요. 역시 이론 위주의 논문은 글을 쓰기가 힘듭니다. 수식도 많고...-_-;; 아무쪼록 이 글이 읽는 분들께도 많은 도움이 되었길 기대합니다. 다음 글에서 뵙겠습니다.

다음 읽을거리

참고문헌:

[1] f-GAN: Training Generative Neural Samplers using Variational Divergence Minimization, Sebastian Nowozin et al. 2016
[2] [video] NIPS 2016 Workshop on Adversarial Training - Sebastian Nowozin - f-GAN
[3] [slide] NIPS 2016 Workshop on Adversarial Training - Sebastian Nowozin - f-GAN

Jaejun Yoo's Playground

2017년 7월 1일 토요일

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

Discussion

Insights from the Authors

다음 읽을거리

댓글 6개: