神经网络的Lipschitz连续性

Lipschitz 连续性

实值函数情形

定义：设有函数 $f:D\subset {\mathbb{R}}^n\to \mathbb{R}$，若存在常数 $K$ 使得： $$|f(\mathbf{x})-f(\mathbf{y})|\le K\Vert \mathbf{x}-\mathbf{y}\Vert ,\mathrm{\forall }\mathbf{x},\mathbf{y}\in D$$ 则称 $f$ 在 $D$ 上是 $K$-Lipschitz 连续的，其中 $\Vert \cdot \Vert$ 表示欧式范数。称最小的常数 $K$ 为 Lipschitz 常数，记作 $\Vert f{\Vert }_{\text{Lip}}$，即： $$\Vert f{\Vert }_{\text{Lip}}=\underset{\mathbf{x},\mathbf{y}\in D,\mathbf{x}\ne \mathbf{y}}{sup}\frac{|f(\mathbf{x})-f(\mathbf{y})|}{\Vert \mathbf{x}-\mathbf{y}\Vert }$$ 需要注意的是，函数的定义域对 Lipschitz 连续很重要，下面几个例子说明了这一点。

例：$f(x)=|x|$ 在 $\mathbb{R}$ 上是 1-Lipschitz 连续的。

例：$f(x)=x^2$ 在区间 $[-1,1]$ 上是 Lipschitz 连续的，但在 $\mathbb{R}$ 上不是 Lipschitz 连续的。

例：$f(x)=\sqrt{x}$ 在区间 $[1,\mathrm{\infty })$ 上是 Lipschitz 连续的，但在区间 $[0,\mathrm{\infty })$​​ 上不是 Lipschitz 连续的。

下面的定理说明，Lipschitz 连续是比一致连续更强的条件。事实上，我们有 Lipschitz 连续 $\Rightarrow$ 一致连续 $\Rightarrow$ 连续。

定理：Lipschitz 连续的函数是一致连续的。

证明：设 $f:D\to \mathbb{R}$ 是 $K$-Lipschitz 连续的，则对任意 $ϵ>0$，存在 $\delta =ϵ/K$，使得对任意 $\mathbf{x},\mathbf{y}\in D$ 且 $\Vert \mathbf{x}-\mathbf{y}\Vert <\delta$，有： $$|f(\mathbf{x})-f(\mathbf{y})|\le K\Vert \mathbf{x}-\mathbf{y}\Vert <\delta K=ϵ$$ 故 $f$ 在 $D$ 上一致连续。证毕。

在实际应用场景中，$f$ 常常是可微的，因此我们下面特别关注可微函数的 Lipschitz 连续性。为此，首先给出一个引理。

引理（多元实值函数的中值定理）：设 $D\subset {\mathbb{R}}^n$ 是一个凸的开集，$f:D\to \mathbb{R}$ 在 $D$ 上可微，那么对 $\mathrm{\forall }\mathbf{x},\mathbf{y}\in D$，$\mathrm{\exists }{t}_0\in (0,1)$ 使得： $$f(\mathbf{y})=f(\mathbf{x})+\mathrm{\nabla }f((1-t_0)\mathbf{x}+t_0\mathbf{y}{)}^T(\mathbf{y}-\mathbf{x})$$ 下面的定理告诉我们，对于可微函数，其 Lipschitz 连续性与梯度有界是等价的。

定理：设 $D\subset {\mathbb{R}}^n$ 是一个凸的开集，$f:D\to \mathbb{R}$ 在 $D$ 上可微，那么: $$\underset{\text{Lipschitz continuity}}{\underbrace{|f(\mathbf{x})-f(\mathbf{y})|\le K\Vert \mathbf{x}-\mathbf{y}\Vert ,\mathrm{\forall }\mathbf{x},\mathbf{y}\in D}}⟺\underset{\text{bounded gradient}}{\underbrace{\Vert \mathrm{\nabla }f(\mathbf{x})\Vert \le K,\mathrm{\forall }\mathbf{x}\in D}}$$

证明：

$$：对于任意 $$，取 $$ 且 $$，由于 $$ 是开集，所以存在充分小的 $$ 使得 $$. 由于 $$ 是 $$-Lipschitz 连续的，有： $$ 两边除以 $$ 并令 $$，得： $$ 取 $$，得： $$ $$：根据引理，对 $$，$$​ 使得： $$ 两边取绝对值得： $$ 证毕。

向量值函数情形

实值函数下对 Lipschitz 连续性的定义可以自然拓展到向量值函数下。

定义：设有函数 $$，若存在常数 $$ 使得： $$ 则称 $$ 在 $$ 上是 $$-Lipschitz 连续的，其中 $$ 表示欧式范数。称最小的常数 $$ 为 Lipschitz 常数，记作 $$​.

下面的定理考虑复合函数的 Lipschitz 常数。

定理：设有函数 $$ 和 $$，则： $$

证明： $$ 证毕。

上一小节关于实值可微函数的结论也可以拓展到向量值可微函数情形。同样我们需要先给出一个引理。

引理（多元向量值函数的“中值定理”）：设 $$ 是一个凸的开集，$$ 在 $$ 上可微，那么对 $$，$$ 使得： $$ 定理：设 $$ 是一个凸的开集，$$ 在 $$​ 上可微，那么： $$ 其中 $$ 表示 $$ 的 Jacobian 矩阵，$$ 表示其谱范数。

证明：

$$​：对于任意 $$，取 $$ 且 $$，由于 $$ 是开集，所以存在充分小的 $$ 使得 $$. 由于 $$ 是 $$-Lipschitz 连续的，有： $$ 两边除以 $$ 并令 $$，得： $$ 于是谱范数： $$ $$​：根据引理，对 $$，$$​ 使得：

$$ 证毕。

推论：设 $$ 是一个凸的开集，$$ 在 $$ 上可微，那么 $$ 的 Lipschitz 常数为： $$ 又由于矩阵的谱范数等于其最大奇异值，因此上式也可写作： $$ 其中 $$ 表示矩阵 $$ 的最大奇异值。

一般度量空间情形

事实上，在一般的度量空间下，我们也可以类似地定义 Lipschitz 连续性。

定义：设 $$ 是两个度量空间，$$，若存在常数 $$ 使得： $$ 则称 $$ 是 $$-Lipschitz 连续的。称最小的常数 $$ 为 Lipschitz 常数，记作 $$.

一般度量空间下 Lipschitz 连续性的性质不在本文的讨论范围之内，读者可自行参阅相关书籍。

神经网络的 Lipschitz 常数

一个神经网络往往由多个线性层和激活函数堆叠而成（卷积层也可以视为线性层）： $$ 其中 $$ 表示线性层，$$ 表示激活层。若假设激活层都是 1-Lipschitz 连续的（这对 ReLU, leaky ReLU 成立，而对于其他常见的激活函数，它们一般都是 $$-Lipschitz 连续的），那么根据上文的结论，有： $$ 因此，只要我们能控制每一层的 Lipschitz 常数，就能控制整个神经网络的 Lipschitz 常数。

考虑一个线性层 $$，其中 $$，其 Jacobian 矩阵为： $$ 因此根据上文的结论，线性层的 Lipschitz 常数就是权重 $$ 的谱范数： $$

下面我们介绍几种控制神经网络 Lipschitz 常数的方法，包括权重裁剪、梯度惩罚、谱范数正则和谱归一化。

权重裁剪

WGAN^[1]提出使用权重裁剪 (weight clipping) 来控制网络的 Lipschitz 常数，即在每一步更新权重后手动将其裁剪到 $$ 之间，其中 $$ 为超参数： $$ 为什么权重裁剪可以控制 Lipschitz 常数呢？考虑线性层 $$，其中 $$，容易知道权重裁剪控制了 $$ 矩阵的 Frobenius 范数： $$ 根据矩阵论的知识，Frobenius 范数等于矩阵所有奇异值平方和开根，因此自然控制了谱范数： $$ 因此权重裁剪可以控制网络的 Lipschitz 常数。

但是权重裁剪容易导致大多数权重集中在 $$ 和 $$ 处，并且裁剪超参数选取不当容易导致梯度消失或优化困难。就连 WGAN 作者都在论文里直言：“权重裁剪无疑是一种糟糕的控制 Lipschitz 常数的方式”。

梯度惩罚

为了解决权重裁剪的问题，WGAN-GP^[2]提出了梯度惩罚 (gradient penalty)，即在优化目标中加入正则项： $$ 注意在 WGAN-GP 的背景下网络的输出是一个常数，即 $$ 是一个实值函数，所以上式中的 $$ 是梯度。

梯度惩罚控制 Lipschitz 常数的原理基于上文的结论：可微函数的 Lipschitz 连续性与梯度有界是等价的，因此只要控制了梯度的界，就控制了网络的 Lipschitz 常数。另外，梯度惩罚是一种“软”的约束，即鼓励网络的梯度接近 1 而并没有硬性约束梯度必须小于 1，因此并不能保证网络是 1-Lipschitz 连续的，但在合适的超参数下能有足够好的效果。

梯度惩罚也有如下形式的变种，仅在梯度大于 1 时作惩罚： $$ 那种形式更好并没有定论，以实验效果为准。

需要说明的是，原则上梯度惩罚要在整个 $$ 空间上做，这显然是不合适的。由于数据分布是 $$ 中的低维流形，所以我们只需要在数据流形上实施梯度惩罚即可。特别地，在 GAN 的问题背景下，数据流形不仅包含真实数据，还包含生成数据，所以 WGAN-GP 的做法是先随机采样真实数据和生成数据，然后在二者之间随机插值，以保证在真实数据、生成数据及二者之间的区域都有 Lipschitz 常数约束。当然，在其他只有真实数据的问题背景下，只需要从数据集中采样即可。

谱范数正则

梯度惩罚直接考虑一整个网络，但根据第一节的结论，其实只需要考虑每一层就行了。对于线性层 $$，为了限制其 Lipschitz 常数，只需要限制 $$ 的谱范数，因此在优化目标中加入正则项^[3]： $$ 同梯度惩罚一样，谱范数正则是一种软的约束，鼓励但不能保证网络的 Lipschitz 连续性。

有趣的是，谱范数正则可以看作常用的 L2 正则的弱化版本。注意 L2 正则相当于限制了矩阵的 Frobenius 范数： $$ 由于 Frobenius 范数能控制谱范数，所以 L2 正则也能达到控制网络 Lipschitz 常数的效果。但是相比谱范数正则，L2 正则鼓励不止是最大奇异值、而是所有奇异值都缩小，因此过分地限制了网络的表达能力。从这个角度来说，谱范数正则是比 L2 正则更好的选择。

最后，与梯度惩罚相比，谱范数正则不依赖于输入数据，因此并没有梯度惩罚中只能在数据流形上限制 Lipschitz 常数的缺点。

谱归一化

谱范数正则是一种软的约束，但我们完全可以将其变成硬的约束。对于线性层 $$，谱归一化^[4]在权重更新后除以其谱范数： $$ 根据范数的正齐次性容易知道，操作后矩阵 $$ 的谱范数保证为 1，因此该线性层是 1-Lipschitz 连续的。于是在第一节的假设（激活层都是 1-Lipschitz 连续的）下，整个网络就是 1-Lipschitz 连续的。谱归一化既有谱范数正则的所有优点，又能保证网络的 Lipschitz 连续性，因此基本上是最好的方法。

如何计算谱范数

对于谱范数正则和谱归一化，一个问题是如何计算谱范数。由于谱范数等于最大奇异值，所以最直接的方法就是对权重矩阵 $$ 做奇异值分解，然后取出最大奇异值。但是奇异值分解的计算量巨大，因此这个方法并不实用。事实上，谱归一化采用的是幂迭代法 (power iteration).

根据矩阵论的知识，$$ 的最大奇异值就是 $$ 的最大特征值的平方根，所以问题变成如何快速求解实对称矩阵 $$ 的特征值。幂迭代法的基本思想是建立如下的迭代格式： $$ 反复迭代，最终 $$ 就会收敛到 $$ 的最大特征值对应的特征向量，此时 $$​​ 就是最大特征值。

证明：设 $$ 为一个实对称矩阵，其特征值和对应特征向量分别为 $$ 和 $$. 假设 $$ 是唯一最大的特征值，且 $$ 线性无关，那么对随机初始化的向量 $$，将其分解为特征向量的线性组合： $$ 由于 $$ 是随机选取的，所以几乎不可能正好与 $$ 正交。换句话说，$$ 以概率 1 不为 0. 上式乘以 $$ 得： $$ 归一化得： $$ 其中 $$ 为归一化系数。以此类推，有： $$ 其中 $$ 为归一化系数。注意对 $$，有 $$，所以当 $$ 时，$$ 这些方向的分量就趋于 0，只留下 $$ 方向： $$ 证毕。

事实上，幂迭代法有着非常直观的几何解释——每次迭代乘以 $$，就是将 $$ 向最大特征值对应的特征向量方向旋转一点，因此最终收敛到 $$ 的最大特征向量。

References

1. Arjovsky, Martin, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017. ↩︎
2. Gulrajani, Ishaan, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C. Courville. Improved training of wasserstein gans. Advances in neural information processing systems 30 (2017). ↩︎
3. Yoshida, Yuichi, and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint arXiv:1705.10941 (2017). ↩︎
4. Miyato, Takeru, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:1802.05957 (2018). ↩︎
5. Lebl, Jiří. Basic analysis: Introduction to real analysis. https://www.jirka.org/ra/ ↩︎
6. 萌萌憨. Lipschitz连续性和导数有界的等价性证明（前提：函数可微）. https://blog.csdn.net/weixin_42128655/article/details/138209570 ↩︎