GAN 的谱归一化(Spectral Norm)和矩阵的奇异值分解(SVD)
在文献 [2] 中作者分析了 GAN [1] 难以训练的原因在于原生 GAN 的目标函数等价于优化生成数据的分布 pgpg 和真实数据的分布 prpr 之间的 J-S 散度 (Jensen–Shannon Divergence)。
接着作者提出 WGAN [3]，使用性质优良的 Wasserstein distance 代替原生 GAN 中的 J-S 散度。 然后利用KR对偶原理将 Wasserstein distance的求解问题转换为求解最优的利普希茨连续函数的问题。 为了使得判别器 D 满足利普希茨连续性，作者使用“梯度裁剪”将过大的参数直接裁剪到一个阈值以下。
本文要介绍的这篇文章 “Spectral normalization for generative adversarial network” (以下简称 Spectral Norm) 使用一种更优雅的方式使得判别器 D 满足 利普希茨连续性。
由于知乎的编辑器对公式的输入和交叉引用不太友好，我只手动的把一部分公式转换到合适的格式，有一部分行内公式和公式引用有格式问题。这部分公式通过“脑补” \LaTeX 代码应该能够看懂。如果想看比较清晰完整的版本，请阅读原文。
WGAN 和 Wasserstein distance
为了说明 Spectral Norm背后的动机，我们从 Wasserstein distance (以下简称 W distance)开始说起。 W distance的定义为：
\begin{equation} \begin{split} \text{Was}(p_r, p_g) &= \inf_{\gamma \in \prod(p_r, p_g)} \int_{x, y} \gamma(x, y) \cdot \lVert x-y \rVert \\ &= \inf_{\gamma \in \prod(p_r, p_g)} \mathbb{E} [\lVert x - y\rVert] \end{split} \label{eq:wasserstein} \end{equation} (1)
上式 的定义看起来比较难懂。 其中 $\inf$ 可以简单地理解为 取最小值， \gamma \in \prod_{p_r, p_g} 表示边缘分布分别为为 $p_r$ 和 $p_g$ 的一个联合分布。
当然这样解释仍然让很多人难以理解，这里举一个简单的例子：
假设有五个工厂生产食品，产量分别为 A_1, ..., A_5 ， 另外有五个城市消费食品，所需的食 B_1, ..., B_5 品量分别是，假设 \sum_i A_i = \sum_j B_j 。 现在制定了供应方案：从 $A_i$ 运输到 $B_j$ 的食品量为 \gamma_{i, j} ， 显然有:
\begin{equation} \begin{cases} \sum_j \gamma_{i, j} = A_i \\ \sum_i \gamma_{i, j} = B_j \end{cases} \end{equation} (2)
这也就是所谓的 "\gamma 是边缘分布分别为 $A$ 和 $B$ 的联合分布”。 假设从 $i$ 地每运输一份食品到 $j$ 地的成本是 \lVert i-j \rVert ， 那么运输方案的总成本即为：
\begin{equation} \begin{split} & \sum \gamma(i, j) \lVert i-j \rVert \\ &= \mathbb{E} \lVert i-j \rVert \end{split}\label{eq:total-cost} \end{equation} (3)
求解 上式式的最小运输成本，其实就是求解离散情况下的 Wasserstein Distance，而最小运输 成本所对应的运输方案 \gamma ，就是最优传输。 这类问题被称为最优传输问题 (optimal transport)。
然而 Wasserstein distance 的求解并不那么直接。 式 $\ref{eq:total-cost}$ 所描述的问题一般可以通过线性规划 (Linear programming) 求解，因为问题中的求解目标以及约束条件均为线性。 即便如此，在每一次训练的迭代去求解一个线性问题仍然是非常耗时的，而且我们并不需要得到最优传输，我们只需要得到最优传输对应的 最小传输代价，以及该代价的导数。 在文献 [3] 中作者使用了 K-R 对偶将 wasserstein distance 求解的问题转换为求解最优函数的问题。 K-R 对偶指出，当测度 \lVert i-j \rVert = (i-j)^2 的时候，(1)式所对应的问题可以转换为寻找一个满足利普希茨连续的函数 $f(x)$， 使得下式取得最大值：
\begin{equation} \text{Was}(p_r, p_g) = \sup\_{\lVert f \rVert\_{L \leq 1}} \mathbb{E}\_{x \sim p_r} f(x) - \mathbb{E}\_{x \sim p_g} f(x) \label{eq:dual-problem} \end{equation} (4)
至于 (4) 式的结论为什么成立可以参考这篇文章。 本文关注另外一个问题，就是如何让函数 f满足“利普希茨连续性” (Lipschitz continuity)。
利普希茨连续性 (Lipschitz Continuity)
利普希茨连续性 (Lipschitz continuity) 的定义很简单，他要求函数 $f(x)$ 满足对任意 $x, y$ 都有:
\begin{equation} \frac{f(x) - f(y)}{x - y} \leq K \label{eq:lipschitz} \end{equation} (5)
实际上式(5)甚至都没有要求函数 $f(x)$ 可导。 在 K-R 对偶中，要求 $k=1$，也即：
\frac{f(x) - f(y)}{x - y} \leq 1 (6)
在 WGAN[3] 中作者使用一个神经网络来逼近函数 $f(x)$，并且使用一个简单的 trick 使得函数 $f(x)$ 满足利普希茨连续性： 在每一次更新网络参数之后，如果参数大于某个阈值，则强行将参数剪裁到这个阈值。 这样这个神经网络的每一层的梯度都不会大于这个阈值，总体上这个神经网络的就一定满足利普希茨连续性。
但这样的做法似乎有些暴力，因为这样强行更改网络参数可能会影响到网络的收敛。 于是在文献[4]中作者提出了 Spectral Norm，对网络参数进行谱归一化使得网络满足利普希茨连续条件。
矩阵的奇异值分解 (Singular Value Decomposition)
为了方便大家理解 Spectral Norm ，我们先介绍一下 SVD 分解。
假设有 $m\times n$ 的方阵 $A$，对矩阵 $A$ 存在这样一种分解：
\begin{equation} \mathbf{A} = \mathbf{U} \mathbf{\Sigma} \mathbf{V^T} \label{eq:svd} \end{equation} (7)
当矩阵 $W$ 是一个实数阵的时候，
- \mathbf{U} 是一个 m \times m 的正交矩阵 (orthogonal matrix)；
- \mathbf{\Sigma} 是一个 m \times n 的对角阵，对角线上的元素为非负实数，这些数称为矩阵A 的“奇异值”；
- \mathbf{V} 是一个 n \times n 的正交矩阵 (orthogonal matrix)。
矩阵 $A$ 的奇异值计算起来也不麻烦，只需要求得 n\times n 的方阵 A^TA 的特征值，然后把特征值开平方根，即为矩阵 A 的奇异值，因为：
\begin{equation*} \begin{split} \mathbf{A}^T \mathbf{A} &= (\mathbf{U} \mathbf{\Sigma} \mathbf{V^T})^T \cdot (\mathbf{U} \mathbf{\Sigma} \mathbf{V^T}) \\ &= (\mathbf{V} \mathbf{\Sigma}^T \mathbf{U}^T)(\mathbf{U} \mathbf{\Sigma} \mathbf{V}^T) \\ &= \mathbf{V} (\mathbf{\Sigma}^T \mathbf{\Sigma}) \mathbf{V}^T。 \end{split} \end{equation*}
关于奇异值的计算并不是本文的重点，我们仔细研究一下(7)式所表达的几何意义。 我们知道，每一个矩阵对应着一个线性变换。而正交矩阵对应的线性变换很特殊，叫旋转变换 (rotation)。 而对角阵对应的变换，叫做拉伸变换 (scale)。 也就是说式 (7) 把矩阵 A 分解为三个变换：
- 旋转；
- 拉伸；
- 旋转。
这里就很有意思了。假设神经网络的某一层权重W为一个 m \times n 的矩阵，对于输入的特征 x，输出为:
y = W \cdot x = \mathbf{U} \cdot \mathbf{\Sigma} \cdot \mathbf{V^*} \cdot x (8)
也相当于对输入做了三次变换。 如果将输入视为一个向量的话，之后 \Sigma 对应的拉伸变换才会改变输入的长度；其他两次旋转变换都不会。
Spectral Normalization
介绍完 SVD 以及几何意义之后，Spectral Normalization的做法就很简单了： 将神经网络的每一层的参数 $W$ 作 SVD 分解，然后将其最大的奇异值限定为1， 具体地，在每一次更新 $W$ 之后都除以 $W$ 最大的奇异值。 这样，每一层对输入$x$最大的拉伸系数不会超过 1。
经过 Spectral Norm 之后，神经网络的每一层 $g_l(x)$，都满足
\frac{g_l(x) - g_l(y)}{x - y} \leq 1。
对于整个神经网络 f(x) = g_N(g_{N-1}(...g_1(x)...)) 自然也就满足利普希茨连续性了。
然而，在每一次训练迭代中都对神经网络的每一层作 SVD 分解也是很不现实的，特别是当网络权重维度很大的时候。 因此作者采用了一种叫做 power iteration[5] 的方法去迭代得到奇异值的近似解。
Power iteration 首先初始化一个随机的 \hat{u} 然后根据以下公式迭代 \hat{u} 和 \hat{v} ：
\hat{v} \leftarrow \frac{W^T\hat{u}}{\lVert W^T\hat{u} \rVert_2}, \ \\ \hat{u} \leftarrow \frac{W^T\hat{v}}{\lVert W^T\hat{v} \rVert_2}。 \label{eq:power-iter} (9)
最后矩阵 W 的最大奇异值 \sigma(W) 可以根据u和 v 求得：
\begin{equation} \sigma{W} \approx \hat{u}W^T\hat{v}。 \label{eq:sigma_w} \end{equation}
在得到 \sigma(W) 之后，网络每更新一次参数，都对参数 $W$ 进行谱归一化：
\begin{equation} W \leftarrow \frac{W}{\sigma(W)}。 \end{equation}
值得注意的是，(9) 式的迭代算法通常需要迭代多次才能比较好的逼近 \sigma(W) ，但是Spectral Normal[4] 在神经网络的每一次更新过程中只进行一次 power iteration 迭代，仍然能取得不错的效果。 这是因为神经网络的每次迭代中参数 W 是在缓慢更新的，因此每两次迭代过程中可以认为 W的奇异值是近似相等的。 因此虽然在网络的每一次迭代中，只进行一次power iteration，但是随着网络的训练，power iteration 对奇异值的估计会越来越准。这种做法其实十分巧妙，因为神经网络的优化本身也是个迭代的过程，因此对 \sigma(W) 的逼近就可以利用神经网络的迭代逐渐来逼近，在网络参数的每一次更新过程中对 \sigma(W) 的迭代不必太准确。
参考文献
[1] Goodfellow, Ian, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. "Generative adversarial nets." In Advances in neural information processing systems, pp. 2672-2680. 2014. [PDF]
[2] Arjovsky, Martin, and Léon Bottou. "Towards principled methods for training generative adversarial networks." arXiv preprint arXiv:1701.04862 (2017). [PDF]
[3] Arjovsky, Martin, Soumith Chintala, and Léon Bottou. "Wasserstein generative adversarial networks." In International Conference on Machine Learning, pp. 214-223. 2017. [PDF]
[4] Miyato, Takeru, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. "Spectral normalization for generative adversarial networks." arXiv preprint arXiv:1802.05957 (2018). [PDF]
[5] Gulrajani, Ishaan, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C. Courville. "Improved training of wasserstein gans." In Advances in Neural Information Processing Systems, pp. 5767-5777. 2017. [PDF]
[6] Yoshida, Yuichi, and Takeru Miyato. "Spectral Norm Regularization for Improving the Generalizability of Deep Learning." arXiv preprint arXiv:1705.10941 (2017).
