- GAN의 value function은 global optimum이 존재하고 이 때의 유일한 solution은 $\mathbf{P_g = P_{data}}$라는 것
- 논문의 Algorithm 1에서 제시한 GAN의 학습 방법은 수렴한다는 것
이렇게 두 가지입니다. 각각 논문의 4.1과 4.2에 해당하는 내용입니다. GAN을 한 번 정리할 겸 우선 Algorithm 1을 먼저 훑어보고 넘어가도록 하겠습니다. 이어지는 내용은 Algorithm 1의 순서 그대로입니다.
<Algorithm 1>
for number of training iterations do
for $k$ steps do
- 먼저 $D$를 $k$번 먼저 학습시키고자 합니다. 이는 뒤에 나오겠지만 GAN의 value function의 global optimum과 유일한 solution에 관한 증명이 $D$가 optimal 함을 가정으로 하기 때문입니다.
- noise prior $P_g(z) = N(0, 1)$에서 $m$개의 $z$를 sampling 합니다.
- Training data에서 $m$개의 $x$를 가져옵니다.
- $\bigtriangledown_{\theta_d}\frac{1}{m}\sum_{i=1}^m [\log D(x^{(i)}) + \log (1-D(G(z^{(i)})))] ]$ 을 gradient로 해서 gradient ascending 방법으로 $D$를 학습시킵니다. 이 식이 복잡해 보이지만 ${\partial{V(D, G)}\over\partial{\theta_d}}$ 과 똑같습니다. gradient ascending으로 하는 이유는 $D$는 $V(D, G)$를 maximize 해야하기 때문입니다. 이는 $-V(D, G)$를 minimize 하는 것과 동일합니다.
end for
1. noise prior $P_g(z) = N(0, 1)$에서 $m$개의 $z$를 sampling 합니다.
2. $\bigtriangledown_{\theta_g}\frac{1}{m}\sum_{i=1}^m \log(1-D(G(z^(i))))]$ 을 gradient로 해서 gradient descending 방법으로 $G$를 학 습시킵니다. 이유는 위의 4번과 유사하게 $G$는 $V(D, G)$를 minimize 해야하기 때문입니다.
end for
4.1 Global optimality of $p_g = p_{data}$
여기서 이전부터 계속 나왔던 optimal discriminator에 대한 내용이 나옵니다. 우선 any given generator $G$에 대해 optimal discriminator $D$를 가정합니다. 이 때 이 $D$에 대해 아래의 Proposition 1. 이 성립합니다.
Proposition 1. For $G$ fixed, the optimal discriminator $D$ is
$D^*_G(x) = \frac{P_{data}(x)}{P_{data}(x) + P_g(x)} \tag{2}$
이 증명은 사실 굉장히 간단합니다. $D$는 $V(D, G)$를 maximize 시킵니다. 따라서 optimal $D$는 $V(D, G)$를 maximize 하는 $D$를 의미합니다. 이를 구하기 위해선 미분을 해야하므로 우선 $V(D, G)$를 풀어 써보도록 하겠습니다.
$\begin{align}
V(D, G) &= E_{x\sim p_{data}(x)}[\log D(x)] + E_{z\sim p_z(z)}[\log(1-D(G(z)))] \nonumber \\
&= \int_{x} p_{data}(x)\log(D(x)) + \int_{z} p_{z}(z)\log(1-D(G(z))) \nonumber \\
&= \int_{x} p_{data}(x)\log(D(x)) + p_{g}(x)\log(1-D(x)) \nonumber \\ \tag{3}
\end{align}$
식 (3)에서 첫 번째 줄의 식에서 두 번째 줄의 식으로 넘어가는 과정은 그저 expectation의 정의로 한 것이고 두 번째에서 세 번째 줄로 넘어가는 과정은 논문의 Figure 1과 함께 보면 좀 더 쉽게 이해할 수 있습니다. (논문의 Figure 1에 대한 설명은 Generative Adversarial Network(GAN) - part.3에 있습니다) 논문의 Figure 1을 보면 각 $z$는 $x$의 어느 한 점으로 mapping이 됩니다. $p_z(z)$에서 sample 된 $z$가 그대로 $x$에 mapping 되어 $p_g(x)$를 이루게 되므로 $\int_z{p_z(z)}$를 $\int_x{p_g(x)}$로 표현할 수 있습니다. 이렇게 해서 식 (3)이 나오게 됩니다.
논문의 식 (3)의 아래쪽에 The discriminator does not need to be defined outside of $Supp(p_{data}) \cup \, Supp(p_g)$ 라는 문장이 있습니다. $Supp(p_{data})$란 $p_{data}(x) \neq 0$인 $x$의 영역을 의미합니다. 따라서 outside of $Supp(p_{data}) \cup \, Supp(p_g)$ 는 data distribution 와 generative distribution 모두에서 값으로 0을 갖는 이미지 $x$들은 고려할 필요가 없다는 것을 의미하고 직관적으로도 납득이 되는 말입니다.
이제 이 $V(D, G)$의 값을 최대로 하는 $D$를 찾고자 합니다. 이는 적분 안쪽의 식을 $D(x)$로 편미분 하는 과정을 통해 얻을 수 있습니다. 이 과정은 아래와 같습니다.
이러한 $D$의 training objective는 $D$의 parameter를 잘 조절해서 $x \sim p_{data}(x) \mapsto y=1$과 $x \sim p_g(x) \mapsto y=0$이라는 observation 이 나올 가능성(likelihood)인 $P(Y=y | x)$를 최대화 하는 방법이므로 maximizing log-likelihood로 해석이 가능합니다.
지금까지는 optimal한 $D$는 $D_G^*(x) = \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}$에 대한 증명이었습니다. 이제부터는 이 사실을 이용해 GAN의 training objective는 global optima를 갖고 이 global optima는 $p_g = p_{data}$가 되었을 때만 얻을 수 있다는 것에 대한 증명을 알아보도록 하겠습니다. 논문의 Theorem 1에 해당합니다.
Theorem 1. 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 $-\log4$
위에서 $\max_D V(D, G)$는 이미 해결했습니다. 따라서 Proposition 1을 이용해 $\max_D V(D, G)$를 다시 써보도록 하겠습니다.
$\begin{align}
C(G) &= \max_D V(G, D) \nonumber\\
&= E_{x \sim p_{data}}[\log D_G^*(x)] + E_{z \sim p_z}[\log(1-D_G^*(G(z)))] \nonumber\\
&= E_{x \sim p_{data}}[\log D_G^*(x)] + E_{x \sim p_g}[\log(1-D_G^*(x))] \nonumber\\
&= E_{x \sim p_{data}}[\log \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}] + E_{x \sim p_g}[\log \frac{p_g(x)}{p_{data}(x) + p_g(x)}] \tag{4}
\end{align}$
optimal $G$는 이 $C(G)$를 minimize 하는 $G$를 의미합니다. $C(G)$의 minimum 값은 $C(G)$의 식을 조금 변형한 뒤 $KL Divergence$를 사용해 구할 수 있습니다. 아래의 식들이 이것을 구하는 과정입니다.
$\begin{align}
C(G) &= C(G) + \log4 - \log4 \nonumber\\
&= E_{x \sim p_{data}(x)} [\log \frac{p_{data}(x)}{p_{data}(x) + p_{g}(x)}] + \log2 + E_{x \sim p_{g}(x)} [\log \frac{p_g(x)}{p_{data}(x) + p_g(x)}] + \log2 - \log4\nonumber\\
&= \int_x p_{data}(x) \log \frac{2p_{data}(x)}{p_{data}(x) + p_g(x)} + \int_x p_g(x) \log \frac{2p_g(x)}{p_{data}(x) + p_g(x)}dx - \log4 \nonumber\\
&= \int_x p_{data}(x) \log \frac{p_{data}(x)}{\frac{p_{data}(x) + p_g(x)}{2}} dx + \int_x p_{g}(x) \log \frac{p_{g}(x)}{\frac{p_{data}(x) + p_g(x)}{2}} dx - \log4 \nonumber\\
&= -\log4 + KL(p_{data} \parallel \frac{p_{data} + p_g}{2}) + KL(p_g \parallel \frac{p_{data} + p_g}{2}) \tag{5}
\end{align}$
여기서 다음 단계로 넘어가기 전에 Jensen-Shannon divergence라는 것에 대해 알아보고 넘어가겠습니다. Jensen-Shannon divergence는 아래와 같이 정의됩니다.
눈치 빠르신 분들은 눈치 채셨겠지만 식(5)에서 저 고생을 한 이유가 바로 바로 $p_{data}$와 $p_g$ 사이의 Jensen-Shannon divergence 꼴을 만들기 위함이었습니다. 이제 식(5)는 아래와 같이 쓸 수 있습니다.
Kullback-Leibler divergence와 Jensen-Shannon divergence는 모두 두 분포 사이의 차이를 측정하는데 사용됩니다. 하지만 Kullback-Leibler divergence 는 distance metric이 될 수 없지만 Jensen-Shannon divergence는 distance metric입니다. 왜냐하면 $KL(P|Q) \neq KL(Q|P)$, $JSD(P|Q) = JSD(Q|P)$이기 때문입니다. 이제 $P$와 $Q$ 사이의 거리인 $JSD(P|Q)$는 오로지 P와 Q가 같을 때 최소값으로 0을 갖습니다. 따라서 $C(G)$는 오로지 $p_{data} = p_g$ 일 때 $-\log 4$의 global minimum을 갖게 됩니다.
이야기가 너무 길었으므로 짧게 정리해보도록 하겠습니다. $C(G)$는 $D$가 optimized 되었다고 가정할 때 $G$의 objective function입니다. $G$는 이 $C(G)$를 minimize 시켜야합니다. Theorem 1. 에서 증명하고자 하는 것은 $C(G)$가 minimize 되어 optimized $G$를 얻을 수 있는 경우는 오로지 하나, $p_{data} = p_g$의 경우일 때라는 것입니다.
이를 증명하기 위해 $C(G)$를 Jensen-Shannon divergence로 나타내는 과정을 거쳤고 $JSD(P|Q)$는 오로지 $P = Q$일 때 최소값으로 0을 갖는다는 성질을 이용해 $C(G)$는 $p_{data} = p_g$일 때 global minimum을 갖는다는 것을 증명하였습니다.
V(D, G) &= E_{x\sim p_{data}(x)}[\log D(x)] + E_{z\sim p_z(z)}[\log(1-D(G(z)))] \nonumber \\
&= \int_{x} p_{data}(x)\log(D(x)) + \int_{z} p_{z}(z)\log(1-D(G(z))) \nonumber \\
&= \int_{x} p_{data}(x)\log(D(x)) + p_{g}(x)\log(1-D(x)) \nonumber \\ \tag{3}
\end{align}$
식 (3)에서 첫 번째 줄의 식에서 두 번째 줄의 식으로 넘어가는 과정은 그저 expectation의 정의로 한 것이고 두 번째에서 세 번째 줄로 넘어가는 과정은 논문의 Figure 1과 함께 보면 좀 더 쉽게 이해할 수 있습니다. (논문의 Figure 1에 대한 설명은 Generative Adversarial Network(GAN) - part.3에 있습니다) 논문의 Figure 1을 보면 각 $z$는 $x$의 어느 한 점으로 mapping이 됩니다. $p_z(z)$에서 sample 된 $z$가 그대로 $x$에 mapping 되어 $p_g(x)$를 이루게 되므로 $\int_z{p_z(z)}$를 $\int_x{p_g(x)}$로 표현할 수 있습니다. 이렇게 해서 식 (3)이 나오게 됩니다.
논문의 식 (3)의 아래쪽에 The discriminator does not need to be defined outside of $Supp(p_{data}) \cup \, Supp(p_g)$ 라는 문장이 있습니다. $Supp(p_{data})$란 $p_{data}(x) \neq 0$인 $x$의 영역을 의미합니다. 따라서 outside of $Supp(p_{data}) \cup \, Supp(p_g)$ 는 data distribution 와 generative distribution 모두에서 값으로 0을 갖는 이미지 $x$들은 고려할 필요가 없다는 것을 의미하고 직관적으로도 납득이 되는 말입니다.
이제 이 $V(D, G)$의 값을 최대로 하는 $D$를 찾고자 합니다. 이는 적분 안쪽의 식을 $D(x)$로 편미분 하는 과정을 통해 얻을 수 있습니다. 이 과정은 아래와 같습니다.
${\partial\over\partial{D(x)}} \, p_{data}(x) \log(D(x)) + p_g(x) \log(1-D(x)) = 0$
$\frac{p_{data}(x)}{D(x)}-\frac{p_g(x)}{1-D(x)} = 0$
$\therefore \, D(x) = \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}$
따라서 optimal $D$인 $\mathbf{D_G^*(x) = \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}}$가 되는 것입니다.
이러한 $D$의 training objective는 $D$의 parameter를 잘 조절해서 $x \sim p_{data}(x) \mapsto y=1$과 $x \sim p_g(x) \mapsto y=0$이라는 observation 이 나올 가능성(likelihood)인 $P(Y=y | x)$를 최대화 하는 방법이므로 maximizing log-likelihood로 해석이 가능합니다.
지금까지는 optimal한 $D$는 $D_G^*(x) = \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}$에 대한 증명이었습니다. 이제부터는 이 사실을 이용해 GAN의 training objective는 global optima를 갖고 이 global optima는 $p_g = p_{data}$가 되었을 때만 얻을 수 있다는 것에 대한 증명을 알아보도록 하겠습니다. 논문의 Theorem 1에 해당합니다.
Theorem 1. 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 $-\log4$
위에서 $\max_D V(D, G)$는 이미 해결했습니다. 따라서 Proposition 1을 이용해 $\max_D V(D, G)$를 다시 써보도록 하겠습니다.
$\begin{align}
C(G) &= \max_D V(G, D) \nonumber\\
&= E_{x \sim p_{data}}[\log D_G^*(x)] + E_{z \sim p_z}[\log(1-D_G^*(G(z)))] \nonumber\\
&= E_{x \sim p_{data}}[\log D_G^*(x)] + E_{x \sim p_g}[\log(1-D_G^*(x))] \nonumber\\
&= E_{x \sim p_{data}}[\log \frac{p_{data}(x)}{p_{data}(x) + p_g(x)}] + E_{x \sim p_g}[\log \frac{p_g(x)}{p_{data}(x) + p_g(x)}] \tag{4}
\end{align}$
optimal $G$는 이 $C(G)$를 minimize 하는 $G$를 의미합니다. $C(G)$의 minimum 값은 $C(G)$의 식을 조금 변형한 뒤 $KL Divergence$를 사용해 구할 수 있습니다. 아래의 식들이 이것을 구하는 과정입니다.
$\begin{align}
C(G) &= C(G) + \log4 - \log4 \nonumber\\
&= E_{x \sim p_{data}(x)} [\log \frac{p_{data}(x)}{p_{data}(x) + p_{g}(x)}] + \log2 + E_{x \sim p_{g}(x)} [\log \frac{p_g(x)}{p_{data}(x) + p_g(x)}] + \log2 - \log4\nonumber\\
&= \int_x p_{data}(x) \log \frac{2p_{data}(x)}{p_{data}(x) + p_g(x)} + \int_x p_g(x) \log \frac{2p_g(x)}{p_{data}(x) + p_g(x)}dx - \log4 \nonumber\\
&= \int_x p_{data}(x) \log \frac{p_{data}(x)}{\frac{p_{data}(x) + p_g(x)}{2}} dx + \int_x p_{g}(x) \log \frac{p_{g}(x)}{\frac{p_{data}(x) + p_g(x)}{2}} dx - \log4 \nonumber\\
&= -\log4 + KL(p_{data} \parallel \frac{p_{data} + p_g}{2}) + KL(p_g \parallel \frac{p_{data} + p_g}{2}) \tag{5}
\end{align}$
여기서 다음 단계로 넘어가기 전에 Jensen-Shannon divergence라는 것에 대해 알아보고 넘어가겠습니다. Jensen-Shannon divergence는 아래와 같이 정의됩니다.
$JSD(P \mid Q) = \frac{1}{2}KL(P \mid M) + \frac{1}{2}KL(Q \mid M) \, where \, M = \frac{P+Q}{2}$
$C(G) = -\log4 + 2 JSD(p_{data} \parallel p_g)$
Kullback-Leibler divergence와 Jensen-Shannon divergence는 모두 두 분포 사이의 차이를 측정하는데 사용됩니다. 하지만 Kullback-Leibler divergence 는 distance metric이 될 수 없지만 Jensen-Shannon divergence는 distance metric입니다. 왜냐하면 $KL(P|Q) \neq KL(Q|P)$, $JSD(P|Q) = JSD(Q|P)$이기 때문입니다. 이제 $P$와 $Q$ 사이의 거리인 $JSD(P|Q)$는 오로지 P와 Q가 같을 때 최소값으로 0을 갖습니다. 따라서 $C(G)$는 오로지 $p_{data} = p_g$ 일 때 $-\log 4$의 global minimum을 갖게 됩니다.
이야기가 너무 길었으므로 짧게 정리해보도록 하겠습니다. $C(G)$는 $D$가 optimized 되었다고 가정할 때 $G$의 objective function입니다. $G$는 이 $C(G)$를 minimize 시켜야합니다. Theorem 1. 에서 증명하고자 하는 것은 $C(G)$가 minimize 되어 optimized $G$를 얻을 수 있는 경우는 오로지 하나, $p_{data} = p_g$의 경우일 때라는 것입니다.
이를 증명하기 위해 $C(G)$를 Jensen-Shannon divergence로 나타내는 과정을 거쳤고 $JSD(P|Q)$는 오로지 $P = Q$일 때 최소값으로 0을 갖는다는 성질을 이용해 $C(G)$는 $p_{data} = p_g$일 때 global minimum을 갖는다는 것을 증명하였습니다.
0 coment�rios:
댓글 쓰기