在閱讀GAN相關paper之前，可能會有一些基礎的知識要先了解，這邊我整理一些李宏毅老師在課堂上的內容筆記。
在此之前，先整理一些數學基礎：
KL Divergence vs Cross Entropy
1. Entropy:
\[S = - \sum_i p(x_i)log_b(x_i)\]2. Cross Entorpy
事件集合ㄧ事件 $x_i$，相對於真實分佈 A 而言， 分佈B編碼分佈A的平均bit長度（因為分佈機率不均勻，故為期望值）。
\[H(A, B) = - \sum_i P_A(x_i)log P_B(x_i)\]在二分問題中:
\[P_A(x = 1) = a \implies P_A(x = 0) = 1 - a\]其中A為真實分佈，故a = 1。
\[P_B(x = 1) = b \implies P_B(x = 0) = 1 - b\]若計算 $H(A, B)$ ：
\[x_i = 1 \implies P_A(x_i)log P_B(x_i) = alogb\] \[x_i = 0 \implies P_A(x_i)log P_B(x_i) = (1 - a)log(1 - b)\]綜合上二式剛好與二分類問題的Maximun Likelihood相同 :
\[\sum_i alogb + (1 - a) log(1-b)\]3. Divergence:
計算分佈差距：
\[KLDiv(A||B) = \sum_i P_A(x_i) log \bigg(\frac {P_A(x_i)} {P_B(x_i)} \bigg)\] \[= \sum_i P_A(x_i) log \big(P_A(x_i) \big) - \sum_i P_A(x_i) log \big(P_B(x_i) \big)\]由上可觀察出若 $P_A$ = $P_B$ ，則 $KLDiv(A||B) = 0$
且 $KL Divergence = S(A) ＋ H(A, B)$，而在訓練時 $A$ 為訓練集已給定，故可用 H(A, B)等價於分布差異而做訓練。
Introduction of Generative Adversarial Network (GAN)
Discriminator
- In each training iteration:
Discriminator
- Sample m examples { $x^1, x^2,…., x^m$} from database.
- Sample m noise samples { $z^1, z^2,…., z^m$ } from a distribution.
- Obtaining generated data { $\tilde x^1,…, \tilde x^m$ }, 其中 \(\tilde x^i = G(z^i)\)
Update discriminator parameters $\theta_d$ to maximize $\tilde V$
- \[\tilde V = \frac 1 m \sum_{i=1}^{m} logD(x^i) + \frac 1 m \sum_{i=1}^{m} log(1 - D(\tilde x^i))\]
- \[\theta_d \gets \theta_d + \eta\nabla\tilde V(\theta_d)\]
Generator
- Sample m noise samples { $z^1, z^2,…., z^m$ } from a distribution.
Update generator parameters $\theta_g$ to maximize $\tilde V$
- \[\tilde V = \frac 1 m \sum_{i=1}^{m} log(D(G(z^i)))\]
- \[\theta_g \gets \theta_g + \eta\nabla\tilde V(\theta_g)\]
Basic Theory
Maximun Likelihood Estimation
- 給定一real data的distribution $P_{data}(x)$
- generator的分佈為 $P_G(x;\theta)$
- 目標是找出一組參數 $\theta$ 使得 $P_{data}$ 和$P_G$ 越相近越好。
從真實資料分布 $P_{data}$ 取樣出{ $x^1,…,x^m$ }，將取樣出的 $x^i$ 代入 $P_G$ 之後相乘，可得到：
\[L = \prod_{i=1}^{m}P_G(x^i;\theta)\]最後找出可以使 \(L\) 越大越好的\(\theta\)。
Maximun Likelihood Estimation = Minimize KL Divergence
從真實資料分布 $P_{data}$ 取樣出{ $x^1,…,x^m$ }。
\[\theta^* = \operatorname*{arg\,max}_{\theta} \prod_{i=1}^{m} P_G(x^i;\theta)\] \[= \operatorname*{arg\,max}_{\theta} \sum_{i=1}^{m} logP_G(x^i;\theta)\]上式可解讀為：欲找到一個 $\theta$ ，使得從 $P_{data}$ 隨機取樣到的 $x_i$ 計算其在 $P_G$ 中的機率取log後相加可以越大越好。由於在data中要取到某個 $x_i$ 也有一對應的機率， 故上式可以視為一種期望值的逼近:
\[\approx \operatorname*{arg\,max}_{\theta} E_{x\sim P_{data}}[logP_G(x;\theta)]\] \[= \operatorname*{arg\,max}_{\theta} \int\limits_x P_{data}(x)logP_G(x;\theta) \mathrm d x\] \[= \operatorname*{arg\,max}_{\theta} ( \int\limits_x P_{data}(x)logP_G(x;\theta) \mathrm d x - \int\limits_x P_{data}(x)logP_{data}(x) \mathrm d x)\]上式最後一項跟 $\theta$ 無關，故可視為常數不影響求值，目的是要導入KL Divergence:
\[= \operatorname*{arg\,min}_{\theta} KL(P_{data}||P_G)\]Generator:
假設G是一個network，我們利用G來定義一個機率分佈\(P_G\)，如下圖（圖片來自李宏毅老師上課講義）
而我們的目標是：
\[G^* = \operatorname*{arg\,min}_G Div(P_G, P_{data})\]其中 $Div(P_G, P_{data})$ 代表兩個分部之間的Divergence。
Discriminator
Objective Function for Discriminator:
\[V(G, D) = E_{x\sim P_{data}}[logD(x)] + E_{x\sim P_G}[log(1 - D(x))]\]Training:
\[D^* = \operatorname*{arg\,max}_D V(D, G)\] \[V = E_{x\sim P_{data}} [logD(x)] + E_{x\sim P_G} [log(1 -D(x))]\] \[= \int\limits_x P_{data}(x)logD(x) \mathrm d x + \int\limits_x P_G (x)log(1- D(x)) \mathrm d x\] \[= \int\limits_x [ P_{data}(x)logD(x) + P_G (x)log(1- D(x))] \mathrm d x\]以下討論：
\[\operatorname*{max}_D V(D, G) = V(D^*,G)\] \[V = E_{x\sim P_{data}} [logD(x)] + E_{x\sim P_G} [log(1 -D(x))]\] \[= \int\limits_x P_{data}(x)logD(x) \mathrm d x + \int\limits_x P_G (x)log(1- D(x)) \mathrm d x\] \[= \int\limits_x [ P_{data}(x)logD(x) + P_G (x)log(1- D(x))] \mathrm d x\]找一個 $ D^* $ 可以使得上述 $V$ 最大。其中假設 $D(x)$ 可為任意function。故可視為：給定一 $x$ ，找一個 $D^*$ 使得:
\[P_{data}(x)logD(x) + P_G (x)log(1- D(x))\]有最大值。求最大值，故令 $f(D) = alog(D) + blog(1-D)$
\[\frac {\mathrm d f(D)} {\mathrm d D} = a \times \frac 1 D + b \times \frac 1 {1-D} \times (-1) = 0\] \[\implies a \times \frac 1 {D^*} = b \times \frac 1 {1-D^*}\] \[\implies D^* = \frac a {a+b}\] \[\implies D^*(x) = \frac {P_{data}(x)} {P_{data}(x) + P_G(x)}\]接著，將 $ D^* (x) = \frac {P_{data}(x)} {P_{data}(x) + P_G(x)}$ 帶入 $V(D^*, G) $ :
\[V(D^*, G)\] \[= 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)}]\] \[= \int\limits_x \bigg[ P_{data}(x)log \frac {P_{data}(x)} {P_{data}(x) + P_G(x)} + P_G (x)log\frac {P_G (x)} {P_{data}(x) + P_G(x)}\bigg] \mathrm d x\] \[= \int\limits_x \bigg[ P_{data}(x)log \frac {\frac 1 2 P_{data}(x)} {\frac 1 2 [P_{data}(x) + P_G(x) ]} + P_G (x)log\frac {\frac 1 2 P_G (x)} {\frac 1 2 [P_{data}(x) + P_G(x)]}\bigg] \mathrm d x\] \[= -2log2 + \int\limits_x \bigg[ P_{data}(x)log \frac {P_{data}(x)} {\frac 1 2 [P_{data}(x) + P_G(x) ]} + P_G (x)log\frac {P_G (x)} {\frac 1 2 [P_{data}(x) + P_G(x)]}\bigg] \mathrm d x\] \[= -2log2 + KL(P_{data}|| \frac {P_{data}+ P_G} 2) + KL(P_G|| \frac {P_{data}+ P_G} 2)\] \[= -2log2 + 2JSD(P_{data}||P_G)\]Jensen-Shannon divergence $JSD$ :
\[JSD(P||Q) = \frac 1 2 D(P||M) + \frac 1 2 D(Q||M), \quad M = \frac 1 2 (P+Q)\]Discriminator + Generator
前面提到，在Generator要解的目標函數式
\[G^* = \operatorname*{arg\,min}_G Div(P_G, P_{data})\]因為也提到，在Discriminator的目標函數：
\[D^* = \operatorname*{arg\,max}_D V(D, G)\]且已推導出：
\[\operatorname*{max}_D V(D, G) = V(D^*,G)\] \[= -2log2 + 2JSD(P_{data}||P_G)\]則可把 $Div(P_G, P_{data}) 代換成：
\[\operatorname*{max}_D V(D, G)\]得到：
\[G^* = \operatorname*{arg\,min}_G \operatorname*{max}_D V(D, G)\]
In Practice
Sample m examples { $x^1, x^2,…., x^m$} from database.
Generated data { $\tilde x^1,…, \tilde x^m$ }
實作上無法以積分計算期望值，故 $V = E_{x\sim P_{data}} [logD(x)] + E_{x\sim P_G} [log(1 -D(x))]$會用下式：
\[\tilde V = \frac 1 m \sum_{i=1}^{m} logD(x^i) + \frac 1 m \sum_{i=1}^{m} log(1 - D(\tilde x^i))\]觀察發現 Maximize $\tilde V$ 可等價於 Minimize 二元分類的 Cross Entropy。D為一Binary Classifier，sigmoid output 0~1之間。一類為real一類為fake。
Algorithm
