초짜 대학원생 입장에서 이해하는 Generative Adversarial Nets (2)

앞서 초짜 대학원생 입장에서 이해하는 Generative Adversarial Nets (1)에 이어서 큰 줄기 두 가지 중 하나였던 이론적 증명 부분을 정리해보겠습니다.

[Theoretical Results]

이론적 결과 부분도 크게는 두 가지로 나뉘는데 먼저 앞서 소개한 minimax problem이 $p_g = p_{data}$에서 global optimum을 갖는다는 것을 보이고, 이어서 이 논문에서 소개하는 알고리즘이 global optimum을 찾는다는 것을 보여줍니다.

이 때, 지금까지 잘 사용하던 Multilayer perceptron을 사용하여 내용을 이어가는 것이 아니라 이론적 증명을 편하게 하기 위해 약간의 기믹?을 사용합니다. 저자는 non-parametric setting을 사용했다고 표현하는데, 좀 더 풀어 말하면 MLP를 사용하는 것은 결국 parameter $\theta$를 학습하는 것이므로 직접적으로 probability density function을 학습하는 것과는 차이가 있다는 것이죠.

즉, 앞으로 나올 이론적 증명 등은 model이 infinite capacity를 가지고 있으며, 수렴에 관해 애기할 때도 probability density function 공간에서 얘기한다는 것을 염두에 두면 되겠습니다.

그러면 실제로 MLP를 사용할 때는 지금 하려고 하는 증명들이 정확히 적용되는 것은 아니지 않나?......

...맞습니다. 사실 앞서 글에서 나중에 소개하겠다고 하던 MLP를 이용한 것의 장단점이 이로부터 비롯됩니다.

실용적인 측면에서 실제로 학습시킬 때, MLP를 model로 사용하면 성능이 잘 나오기도 하고 MLP를 사용하면 직관적이고 단순하고 강력한 backpropagation을 사용하는 것이 가능하기 때문에 inference를 위한 별도의 가정 등이 필요하지 않다는 장점이 있습니다.
다른 방법들이 많이 사용하듯 굳이 probability distribution을 학습하기 위해 Markov Chain Monte Carlo (MCMC)와 같은 무식한? 방법을 사용하지 않아도 되기 때문에 빠르기도 하죠.

원래도 MCMC 방식은 High dimensional vector space에서 잘 되기 어렵다는 얘기들이 있는데 (어디서 읽었더라...) 사실 직관적으로도 그렇습니다. MCMC를 이용하여 probability distribution를 찾는다고 생각해보면 점을 여러 개?를 뽑아서 distribution을 유추하겠다는 것인데 사실 거의 불가능에 가깝죠 (고차원으로 갈 수록 천문학적인 점들이 필요할테니...).

아무튼 본 주제로 넘어가보겠습니다. 여기서부턴 이 문제를 위해 사용된 알고리즘에 대한 증명 두 가지를 좀 더 쉽게 풀이하려 해보겠습니다.

앞선 글에서 정의했듯이 GAN은 다음과 같은 minimax problem 풀고자 합니다;

$$\min_G \max_D V(D,G) = \mathbb{E}_{x\sim p_{data}~(x)}[log D(x)] + \mathbb{E}_{z\sim p_z(z)}[log(1-D(G(z)))]$$

1. Global Optimality of $p_g = p_{data}$

일단, 첫 번째 주제인 Global Optimality에 관한 얘기를 하기 위해서는 먼저 배우고 넘어가야 할 도구가 하나 있습니다. 

For $G$ fixed, the optimal discriminator $D$ is $$D^*_G(x) = \frac{p_{data}~(x)}{p_{data}~(x)+p_{g}(x)}.$$

The training criterion for the discriminator $D$, given any generator G, is to maximize the quantity $V(G,D)$ $$\begin{align}V(G,D) &= \int_x p_{data}~(x)log(D(x))dx + \int_z p_z(z)log(1-D(G(z)))dz \\ &= \int_x p_{data}~(x)log(D(x)) + p_g(x)log(1-D(x))dx \end{align}$$ For any $(a,b) \in \mathbb{R}^2 \setminus \{0,0\}$, the function $y \rightarrow {\rm a} log(y) + {\rm b} log(1-y)$ achieves its maximum in $[0,1]$ at $\frac{a}{a+b}$. The discriminator does not need to be defined outside of $Supp(p_{data}) \cup Supp(p_g)$, concluding the proof.

(대학원생의 풀이)
앞서 $\frac{a}{a+b}$ 부분을 증명하는 것은 단순한 $y$에 대한 고등학교 수준 미분이므로 어렵지 않습니다. 한 가지 주의점은 (paper에서는 굳이 짚고 넘어가지는 않았지만) $log(\cdot)$ 안의 값이 0이 될 수는 없으므로 미분할 때 $y=0~or~1$인 경우는 따로 빼서 생각해줘야합니다. 두 번째 문장의 $Supp(p_{data}) \bigcup Supp(p_g)$ 부분이 무엇을 의미하는지는 저도 아직 좀 아리송한데...아마도 $V(G,D)$ 전개에서 두 번째 등호로 넘어가며 수식이 모두 $\int_x \cdot~dx$ 안으로 들어갈 때, $p_z(z)\rightarrow p_g(x)$로 바뀌는 부분을 짚은 것인가 싶습니다.

개념적으로 생각해보면 결국, $\mathbb{E}_{z\sim p_z(z)}(log(1-D(G(z))) = \mathbb{E}_{x\sim p_g(x)}(log(1-D(x))$으로 기대값이 같다고 할 수 있기 때문에, 등호가 성립하면서 $\int_x \cdot~dx$로 범위가 $x$로 한정지어져도 된다는 것에 당위성에 대해 얘기하려고 한 것 같네요.

결국  $\min_G \max_D V(G,D)$에서 안 쪽의 max 문제부터 풀어주면 문제가 다음과 같이 reformulate 됩니다:
$$\begin{align} C(G) & = \max_D V(G,D) \\
&= \mathbb{E}_{x \sim p_{data}} \left[ log D^*_G(x) \right] + \mathbb{E}_{z\sim p_z}\left[ log(1-D^*_G(G(z))) \right] \\
&= \mathbb{E}_{x \sim p_{data}} \left[ log D^*_G(x) \right] + \mathbb{E}_{x\sim p_g}\left[ log(1-D^*_G(x)) \right] \\
&= \mathbb{E}_{x \sim p_{data}} \left[ log \frac{p_{data}~(x)}{p_{data}~(x)+p_{g}(x)} \right] + \mathbb{E}_{x\sim p_g} \left[ log \frac{p_{g}(x)}{p_{data}~(x)+p_{g}(x)} \right] \end{align}$$
이제 이 도구를 이용해서 main theorem을 증명해봅시다!

The global minimum of the virtual training criterion $C(G)$ is achieved if and only if $p_g=p_{data}.$ At that point, $C(G)$ achieves the value $-log(4)$.

For $p_g = p_{data}, D^*_G(x)=\frac{1}{2}$ 임은 자명하고 다음 수식도 자연히 따라옵니다; $$C(G) = \mathbb{E}_{x \sim p_{data}} \left[ -log(2)\right] + \mathbb{E}_{x \sim p_{g}} \left[ -log(2)\right]=-log(4).$$ 이 값이 best possible value of $C(G)$란 것을 알기 위해서는 다음과 같이 $C(G)$를 표현하는 것이 증명의 키 입니다: $$\begin{align}C(G) &= -log(4) + KL \left( p_{data} || \frac{p_{data}~+ p_g}{2}\right) + KL \left( p_g|| \frac{p_{data}~+ p_g}{2}\right) \\ &= -log(4) + 2\cdot JSD(p_{data}||p_g) \end{align}$$ 여기서 KL은 Kullback-Leibler divergence이고 JSD는 Jensen-Shannon divergence입니다. JSD는 항상 양수이고 두 distribution이 일치할 때만 $0$이므로 $C^*=-log(4)$가 $C(G)$의 global minimum이며 그 유일한 해가 $p_g = p_{data}$임을 알 수 있습니다.

(대학원생의 풀이)
원래 논문을 보면 증명 사이사이에 논리의 건너뜀이 약간 있고 KL이나 JSD 등 생소할 수 있는 개념이 사용되기 때문에 여기서 잠시 멈칫할 수 있습니다. 하지만 시간을 조금만 투자해서 생각해보면 그리 어렵지 않다는 것을 알 수 있다는 것!
먼저 KL이 뭔지 wiki님께 물어보자(오오 위키가 없었으면 난 어떻게 살았을까..세상의 공돌이들을 위해 기부도 간간히 합니다ㅋㅋ위키의 설립 때 이야기랑 경제 이론 얘기도 썰이 정말 재미있는데 언제 한 번 풀어볼까...).

위키님 가라사대:
$$D_{KL}(P||Q) = \sum_i P(i) log\frac{P(i)}{Q(i)} $$
라십니다. 그냥 $P$라는 distribution이 있을 때, (보통은 estimate한) Q가 P랑 얼마나 다른 지를 측정하는 값입니다.
위에 증명에서 $KL$을 이용해 나타내기 전에 두 단계를 추가해주기만 하면 이해가 상당히 쉬워집니다;
 $$\begin{align}C(G) &= C(G) + log(4) -log(4) \\ &= -log(4) + KL \left( p_{data} || \frac{p_{data}~+ p_g}{2}\right) + KL \left( p_g|| \frac{p_{data}~+ p_g}{2}\right) \\ &= -log(4) + 2\cdot JSD(p_{data}||p_g) \end{align}$$ 
이렇게 $log(4)$를 더하고 빼준 후 $C(G)+log(4)$를 잘 보면;
$$\mathbb{E}_{x \sim p_{data}} \left[ log \frac{p_{data}~(x)}{p_{data}~(x)+p_{g}(x)} \right] + \mathbb{E}_{z\sim p_x(z)} \left[ log \frac{p_{g}(x)}{p_{data}~(x)+p_{g}(x)} \right] + log(2) + log(2)$$
이렇게 각 expectation 안으로 $log(2)$씩 넣어주면 두 번째 등호의 수식에서 나오는 $KL$ 형태로 나오는 것을 알 수 있습니다.

$JSD$ 역시 wiki님께 여쭤보면:
$${\rm JSD}(P \parallel Q)= \frac{1}{2}D_{KL}(P \parallel M)+\frac{1}{2}D_{KL}(Q \parallel M)$$
where $M=\frac{1}{2}(P+Q)$이므로 그대로 원 수식에 비교 대조해보면, 마지막 세 번째 등호의 수식으로 넘어가는 것 역시 자연스럽게 따라옵니다.

좋아! 이제 앞서 정의한 minimax problem을 잘 풀기만 하면 (즉, global optimal을 찾으면), generator가 만드는 probability distribution($p_g$)이 data distribution($p_{data}$)과 정확히 일치하도록 할 수 있다는 것을 알았습니다. 결국, Generator로 부터 뽑은 sample을 Discriminator가 실제와 구별할 수 없게 된다는 것이죠.

다만, "어떤 모델을 사용하고 어떤 알고리즘을 사용해야 이 문제를 "잘" 풀어줄 것이냐?"는 또 별개의 문제인데...

Convergence of Algorithm 1

이 논문에서는 이미  신경망 모델(MLP)을 사용하여 G와 D를 정의하고 각각을 fix한 상태에서 번갈아가며 문제를 풀어주는 전략을 제시했기 때문에 이제 남은 것은 제시한 알고리즘이 문제를 잘 풀어주는가? 혹은 Global Optimum인 $p_g = p_{data}$로 수렴하는가?를 확인하는 것입니다. (알고리즘의 pseudo code를 여기에 넣는 것은 굳이 필요할 것 같지 않아 논문으로 갈음합니다.)

If $G$ and $D$ have enough capacity, and at each step of Algorithm 1, the discriminator is allowed to reach its optimum given G, and $p_g$ is updated so as to improve the criterion $$\mathbb{E}_{x \sim p_{data}} \left[ log D^*_G(x) \right] + \mathbb{E}_{x\sim p_g}\left[ log(1-D^*_G(x)) \right]$$ then $p_g$ converges to $p_{data}$.

Consider $V(G,D)=U(p_g,D)$ as a function of $p_g$ as done in the above criterion. Note that $U(p_g,D)$ is convex in $p_g$. The subderivatives of a supremum of convex functions include the derivative of the function at the point where the maximum is attained. This is equivalent to computing a gradient descent update for $p_g$ at the optimal $D$ given the corresponding $G$. $\sup_D U(p_g,D)$ is convex in $p_g$ with a unique global optima as proven in Thm 1, therefore with sufficiently small updates of $p_g$, $p_g$ converges to $p_{data}$, concluding the proof.

(대학원생의 풀이)
(* 2017.06.05, 이 부분은 약간의 수정이 들어갈 예정입니다. 큰 줄기에서는 틀리지 않습니다만 좀 더 정확한 풀이는 convex conjugate에 대한 이해가 필요합니다. 시간 나는대로 수정하겠습니다.)
일단, 증명에서 얘기한 convex function의 한 가지 성질을 이해해야힙니다.

"The subderivatives of a supremum of convex functions include the derivative of the function at the point where the maximum is attained."

이 문장을 우리의 상황에 맞게 변수를 넣고 수식으로 바꿔 적으면 다음과 같습니다:

If $f(p_g)=\sup_{D\in \cal{D}}f_{D}(p_g)$ and $f_{D}(p_g)$ is convex in $p_g$ every $D$, then $\partial f_{D^*}(p_g) \in \partial f$ if $D^* = arg\sup_{D \in \cal{D}}f_{D}(p_g).$

원래 증명에 써있는 것은 괜히 변수가 다르게 적혀있어서 헷갈릴 수 있는데, 위와 같이 정리해두고 여기서 함수 $f_{D}(p_g)$를 $U(p_g,D)$라 생각하고 찬찬히 고민해보면 그리 어려운 얘기가 아니란 것을 알 수 있습니다.

하나하나 차근차근 뜯어보겠습니다. 위에 본 증명에서 언급한대로 $U(p_g,D)$는 $p_g$에 대해 convex 함수입니다. 그리고 이 함수의 supremum의 subderivatives라 함은 $\partial \left(\sup_D U(p_g,D)\right)$이며 단순하게는 $\partial f$로 나타낼 수 있습니다.
Subderivatives는 집합이기 때문에 $\partial f_{D^*}(p_g) \in \partial f$ 이 될 수 있는 것은 자명합니다. 그런데 하필이면 우리가 앞서 증명한 Thm 1에 의해 "$\sup_D U(p_g,D)$ is convex in $p_g$ with a unique global optima"이므로 $p_g$에 대한 적은 업데이트만으로도 $p_g\rightarrow p_{data}$ 한다는 것을 얘기할 수 있겠습니다.

이제 우리는 여기서 제시한 알고리즘이 실제로 global optimal을 찾아준다는 것까지도 증명했습니다.

단! 글 중간중간 언급하긴 했으나 이 논리에는 약~간 느슨한 부분이 하나 있지요 그 부분에 대해 마지막으로 본문의 글을 인용하여 내용을 정리하면,

"In practice, adversarial nets represent a limited family of $p_g$ distributions via the function $G(z;\theta_g)$, and we optimize $\theta_g$ rather than $p_g$ itself."

이 부분이 아까 전에 짚고 넘어간 부분입니다. 즉, MLP를 model로 사용하면 $G$가 parameter space에서 multiple critical points를 가지기 때문에 완전히 증명한 바와 합치하지는 않다는 것입니다. 다만 성능이 잘 나오는 것으로 미루어봤을 때, MLP가 이론적 보장이 좀 부족할지라도 실용적으로 쓰이기에는 reasonable한 model이라고 할 수 있겠습니다.

이로써 요즘 hot하다는 GAN에 대해 original paper에서 나온 이론적 배경까지 다 살펴보았습니다. 생각보다 쉬운 개념에 수학도 친절하게 나와있어서 굳이 설명이 필요한가도 싶었으나 스스로 정리하며 공부했다는 것에 의의를 둡니다. (하지만 이 이상으로 긴 논문은 review하려면 한 세월이겠구나 싶네요...ㅋㅋ 그런건 안 해야지...그런 의미에서 NIPS 2016 GAN tutorial은 너무 길어...)

다음에는 뭘 해볼까요.. Domain Adaptation Adversarial Network는 toy code도 MATLAB으로 짜보긴 했는데 코드나 정리해서 올려볼까..

다음 읽을거리

• [PR12-Video] 1. Generative Adversarial Nets (동영상 설명)
• 초짜 대학원생의 입장에서 이해하는 Deep Convolutional Generative Adversarial Network (DCGAN) (1)
• 초짜 대학원생의 입장에서 이해하는 Domain-Adversarial Training of Neural Networks (DANN) (1)
• 초짜 대학원생의 입장에서 이해하는 Unrolled Generative Adversarial Networks (1)

참고문헌:
[1] Generative Adversarial Nets - Ian Goodfellow et al. 2014 논문, 
[2] NIPS 2016 Tutorial: Generative Adversarial Networks