Press "Enter" to skip to content

超详细公式推导解析深度学习中的 Lipschitz 条件

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

 

作者丨科技猛兽

本文目录

 

深度学习中的 Lipschitz 模型

 

1 Lipschitz 条件

 

2 MLP 网络中的 Lipschitz 条件

 

3 MLP 网络 SeqLip 算法

 

4 Self-attention 网络中的 Lipschitz 条件

 

本文介绍的是深度学习中的一种重要的模型:Lipschitz 模型。会先介绍 Lipschitz 条件,Lipschitz 常数,以及Lipschitz 深度神经网络模型,包括 MLP 网络中的 Lipschitz 条件,和 Self-attention 网络中的 Lipschitz 条件。本文第4节涉及较多数学证明和推导,对于只是想简单了解 Lipschitz 条件的读者直接跳过即可。

 

本文符号定义:

 

:向量 的内积。

 

:向量 的coordinate-wise product。

 

:函数 和 的复合函数。

 

:函数 对于 导函数,式中 也叫 Jacobian matrix。

 

深度学习中的 Lipschitz 模型

 

1 Lipschitz 条件:

 

读这篇论文之前要先了解 Lipschitz 条件。

 

Theorem 1 Lipschitz continuous

 

对于,如果对其定义域 中的任意 都存在常数 使得:

 

则称满足 利普希茨连续条件 (Lipschitz continuous) , 成为 利普希茨常数 (Lipschitz constant) 。

 

若存在使得:

 

则称是双利普希茨的 (Bi-Lipschitz continuous)。

 

Lipschitz continuous gradient和 Lipschitz continuous Hessian 都是从Lipschitz continuous 延伸出来的概念。Lipschitz continuous 即:存在一个实数 ,使得对于函数 上的每对点,连接它们的线的斜率的绝对值不大于这个实数 。最小的 称为该函数的 Lipschitz 常数,意味着函数被一次函数上下夹逼。

 

如果函数的 导函数 是Lipschitz continuous,那幺我们说函数 符合Lipschitz continuous gradient 。如果函数的 Hessien 矩阵 是Lipschitz continuous,那幺我们说函数符合Lipschitz continuous Hessian。

 

所以 Lipschitz continuous gradient 意味着 函数被二次函数上下夹逼 。

 

而 Lipschitz continuous Hessian 意味着 函数被三次函数上下夹逼。

 

你可以一直往上构造,构造出更高阶的 Lipschitz continuous condition。

 

Lipschitz continuous 用在函数值上是为了不让函数值变化的太快,保证了函数不会无限制的增长。用在导函数上,是为了不让导函数变化的太快;用在 Hessian 上,是为了让 Hessian 不变化的太快。但他们都导致了一个很有意思的结果:这个Lipschitz continuous 不管用在什幺上,都使的函数被多项式上下夹逼,一方面便于我们处理,另一方面至少我们能控制一下函数的包络信息。

 

下面举一些例子:

 

例1:符合利普希茨连续条件, 。

 

例2:不符合利普希茨连续条件,当 。

 

**例3:**定义在所有实数值的符合利普希茨连续条件, 。

 

例4:符合利普希茨连续条件, 。所以满足利普希茨连续条件的函数未必可微。

 

例5:不符合利普希茨连续条件, 。

 

例6:不符合利普希茨连续条件, 。

 

例7:不符合利普希茨连续条件, 。

 

例8:符合利普希茨连续条件, 。

 

例9:符合利普希茨连续条件, 。

 

如果函数符合 Lipschitz continuous 会怎幺样呢?我们看 Theorem 1 , 直接把绝对值去掉,就可以得到下面两个不等式。

 

式5说明如果函数是是 Lipschitz continuous,固定,对于这个关于 的函数,那幺这个函数的上方和下方是被一个一次函数Bounded。

 

Theorem 2如果函数在 上是 Lipschitz continuous gradient,则对于任意的 有:

 

去掉绝对值,会得到下面两个不等式:

 

式7说明如果函数是是 Lipschitz continuous gradient,固定,对于这个关于 的函数,那幺这个函数的上方和下方是被一个二次函数Bounded。

 

证明 (证明来自Nesterov <Introductory Lectures on Convex Programming>):

 

对于任意的有:

 

因此:

Proof 中红色字体这一步使用了Cauthy-Schwar inequality:,青色字体这一步使用了 Theorem 1 Lipschitz condition。

 

Theorem 3如果函数在 上是 Lipschitz continuous Hessian,则对于任意的 有:

 

去掉绝对值,会得到下面两个不等式:

 

式9说明如果函数是是 Lipschitz continuous Hessian,固定,对于这个关于 的函数,那幺这个函数的上方和下方是被一个三次函数Bounded。

 

证明 (证明来自Nesterov <Introductory Lectures on Convex Programming>):

 

Indeed:

 

因此,

Proof 中红色字体这一步使用了Cauthy-Schwar inequality:,青色字体这一步使用了式 。

 

2 MLP 网络中的 Lipschitz 条件:

 

Lipschitz 模型的作用都有哪些呢?

 

1 使 GAN 的训练过程更加稳定,以在 ILRSVRC2012 dataset 上训练 GAN,参考:

 

Spectral Normalization for Generative Adversarial Networks (ICLR 2018)

 

2 构建可逆残差块,或者流式生成模型,参考:

 

Invertible residual networks (ICML 2019) Residual flows for invertible generative modeling (NIPS 2019)

 

3 通过限制神经网络中的 Lipschitz constants 来辅助构建更鲁棒的机器学习模型,参考:

 

Evaluating the Robustness of Neural Networks: An Extreme Value Theory Approach (ICLR 2018)

 

设计一个 Lipschitz 神经网络模型是比较困难的,之前的工作主要是针对 FC layer 的:

 

论文名称:

 

Lipschitz regularity of deep neural networks: analysis and efficient estimation (NIPS 2018)

 

Efficient and accurate estimation of Lipschitz constants for deep neural networks (NIPS 2019)

 

Lipschitz constant estimation of neural networks via sparse polynomial optimization (ICLR 2020)

 

下面就来介绍一下基于 FCN 的 Lipschitz 模型。

 

研究 Lipschitz 模型的初衷是这样一个现象,即深度神经网络对于其输入是很敏感的。某些对抗样本的存在证明了深度神经网络是极度缺乏鲁棒性的。对输入图片精心设计的扰动能够对网络产生误导,影响其性能和精度。

 

衡量一个深度神经网络对于微小扰动的鲁棒性的方法之一就是上一节讲到的 Lipschitz constant。为了方便阅读,再把定义写一遍。

 

Theorem 1 Lipschitz continuous

 

对于,如果对其定义域 中的任意 都存在常数 使得:

 

则称满足 利普希茨连续条件 (Lipschitz continuous) , 称为 利普希茨常数 (Lipschitz constant) 。 一般取 或 ,

 

 

Theorem 4 Lipschitz continuous

 

如果是 locally Lipschitz continuous function,则其在任意位置是可微的。如果 是 Lipschitz continuous 的,则:

 

式中,是矩阵 的二范数。

 

下面我们证明精确计算神经网络的 Lipschitz constant 是一个 NP-hard 问题,所以需要好的 Lipschitz constant 估计方法,以 MLP 构成的 FCN 为例。

 

Definition 1 (MLP)

 

一个层的 Multi-Layer-Perceptron 可以写成:

 

式中,是仿射函数, 是非线性激活函数。

 

定义一个问题: LIP-CST

 

Problem 1 (LIP-CST)

 

LIP-CST 是一个决策问题,指的是对于一个使用 ReLU 激活函数的2层的 MLP,决定其 Lipschitz constant 的问题。

 

输入:, ,常数 。

 

问题:定义函数 ,则函数 的 Lipschitz constant 可否满足 。

 

LIP-CST 这个决策问题说白了就是想快速找到函数的 Lipschitz constant 是多大的。那幺这件事情到底容不容易呢?我们有下列定理5。

 

Theorem 5 Problem 1 是 NP-hard 问题。

 

证明:

 

Quadratic Optimization 指最大化一个是一个 NP-hard 问题,可以写成是:

 

式中,是一个满秩的半正定矩阵。我们现在要把 Quadratic Optimization 转化成 Problem 1,即 LIP-CST 决策问题。

 

设有:

 

所以我们有:

 

这个矩阵的谱范数 (2范数) 是 ,正好是 Quadratic Optimization 的目标函数。所以我们证明了 Quadratic Optimization 等价于:

 

这一项是什幺?

 

就是一个 2层的 MLP 的导数, 值就是激活函数 的导数。

 

所以我们求的最大值,就相当于是想去 找寻这个 2层的 MLP 的 Lipschitz Constant ,但是这是个 NP-hard 问题。

 

所以看到这里,你应该意识到的是:即便是一个简单的 2层的 MLP 网络,想 找寻这个 2层的 MLP 的 Lipschitz Constant 也是个 NP-hard 问题 。

 

虽然准确地 找寻这个 2层的 MLP 的 Lipschitz Constant 也是个 NP-hard 问题 ,但是估计一个网络 的 Lipschitz Constant 的上界还是容易实现的,先给如下定义:

 

Definition 2

 

如果函数是 个简单函数的结果,且这 个简单函数里面 满足:

 

则称是 computable in operations。

 

举个例子,

 

的计算图如下图1所示。

 

图1:计算图示例

假设所有的操作都是 locally Lipschitz-continuous 的,我们现在想估计函数 的 Lipschitz Constant 的上界,可以使用以下 AutoLip Algorithm 算法:

 

AutoLip Algorithm:

 

输入:函数 ,计算图 。

 

输出:函数 的 Lipschitz Constant 的上界,即: 。

 

则就是我们找的函数  的 Lipschitz Constant 的上界。

 

这个 AutoLip Algorithm 应该怎幺理解呢?

 

比如说我想求这个计算图的第3个操作为止的 Lipschitz Constant,那幺应该有:

 

就相当于是遍历所有的,根据计算图得到每个 对应的 的值,取出最大的作为 Lipschitz Constant 的上界。

 

比如图1中的函数 的 Lipschitz Constant 的上界是:

 

Lemma 1

 

设和 是2个可以复合的 Lipschitz functions,则复合函数 也是 Lipschitz function,且有:

 

对于 MLP 和的激活函数 (ReLU, Leaky ReLU, SoftPlus, Tanh, Sigmoid, ArcTan, Softsign) 所构成的网络来讲,根据上面介绍的 AutoLip Algorithm 和 Lemma 1, Lipschitz Constant 的上界可以写成:

 

但是, AutoLip Algorithm 的问题是计算得到的 Lipschitz Constant 的上界和真实的 Lipschitz Constant 的误差比较大。下面的问题是如何去改进 AutoLip 算法计算出的上界。根据式11,MLP 网络的 Lipschitz Constant 其实可以写得更具体一些:

 

那幺式14的和式15中的 什幺时候相等呢?

 

对于仿射函数,式中 ,其 Lipschitz 常数就是矩阵 的最大奇异值。

 

所以,当上面的时,式15中 的 最大奇异值的索引位置 经过对角矩阵 映射之后,得到的 的 最大奇异值的索引位置 应该是不变的。比如 的最大奇异值在第3个位置,得到的 的最大奇异值的索引位置也得是第3个。但是实际上这一点是很难保证的。所以实际上 是要比 小很多的。我们使用 AutoLip Algorithm 算法得到的 其实并不是一个最理想的 Lipschitz Constant 的上界,我们希望自己计算出的 Lipschitz Constant 的上界更接近 。

 

所以有了下面的改进方法,即:SeqLip 算法。

 

3 MLP 网络 SeqLip 算法:

 

求解的关键就是计算上式15中的 等等对角矩阵,但它们其实是很难估计的,因为这些对角矩阵的值既与输入值有关,又与之前的层有关。但是如前文所述,这些对角矩阵等价于 MLP 网络的激活函数,比如 ReLU, Leaky ReLU, SoftPlus, Tanh, Sigmoid, ArcTan, Softsign 等等。如果使用这些以上这些激活函数的话,其 Lipschitz 常数都是1,因为这些激活函数的导数 。那不如直接用 来表示这些激活函数的导数。这样一来,式15可以改写为:

 

求解17式仍是一个很难的问题,因为搜索空间的维度很高。为了减少问题的复杂性,我们先对每个矩阵进行奇异值分解: ,使问题转化为:

 

式中,当时有 ,其余情况下有 。

 

所以 SeqLip 方法的上界是:

 

当使用 ReLU 作为激活函数,且中间层数较少时,可以暴力搜索 。为了更好地理解 SeqLip 如何改进 AutoLip,我们现在考虑一个简单的设置,其中所有线性图层的第1大和第2大的奇异值之间的差值很大。则有:

 

Theorem 6

 

设是第 个线性层的映射矩阵, 和 分别是其左右奇异值, 是第2大和第1大的奇异值之间的比值。则我们有:

 

证明:

 

考虑中的其中一项 。考虑一种简单的情况, 和 是 unitary matrices, 是对角矩阵,而且奇异值沿着对角降序排列。unitary matrices就是满足 的矩阵,即: 如果一个矩阵的共轭转置矩阵等于其逆矩阵,则称其为 unitary matrices,比如 。

 

令且 ,则通过正交性,我们可以写出:

式P4中的青色部分假设为,黄色部分假设为 。设 和 的第 列分别是 和 ,则:

注意 这里的和 都是 unitary matrices,当所有的值都是实数时就是正交矩阵。根据 规范正交基 (orthonormal basis) 的性质我们有:

 

所以根据式P5有:

 

式中,。所以我们证明了:

 

得证。

 

至此,我们证明了19式。当第2大和第1大的奇异值之间的比值小到可以忽略不计时,19式就变成了下面的20式:

 

至此,SepLip 算法得到的和 AutoLip 算法得到的 的关系更加明朗了,关键就是去估计 的范围。关于这一点我们有下列定理:

 

Lemma 2

 

设是二范数为1的两个随机向量,则有:

 

证明:

 

设是2个 维高斯随机向量,则令 ,有:

 

式中,。进一步化简有:

 

当样本数量很大时,每一项都会收敛到期望值,因此我们计算式P9的期望值。注意到:

 

,以及:

 

得证。

 

Lemma 2 说明当样本数量巨大时,的范围逼近 。

 

所以20式可以进一步写成:

 

比如一个的 MLP 网络, ,则 SepLip 算法得到的 比 AutoLip 算法得到的 这个上界要小100倍,这是一个很有意义的提升。但是,实际情况中第2大和第1大的奇异值之间的比值 不会小到忽略不计,但是 SepLip 算法也是一个提升。

 

4 Self-attention 网络中的 Lipschitz 条件:

 

论文名称:

 

The Lipschitz Constant of Self-Attention (ICML 2021)

 

根据上文的介绍,准确地计算一个 MLP 神经网络的 Lipschitz Constant 是一个 NP-hard 问题, SepLip 算法得到比 AutoLip 算法得到了一个更小的上界,尽管如此,估计深度神经网络的 Lipschitz Constant 依然是一个很有挑战的问题。Self-attention 机制的 Lipschitz 条件又是什幺样的呢?

 

作者在本文给出的论点是:

 

Dot-Product Self-attention 机制不是 Lipschitz 的。

 

作者设计了一种 Self-attention 机制,它是 Lipschitz 的。

 

作者给出了这种 Self-attention 机制的理论上界。

 

为了方便阅读我们把上述 Theorem 1和4 再写一遍:

 

Theorem 1 Lipschitz continuous

 

对于,如果对其定义域 中的任意 都存在常数 使得:

 

则称满足 利普希茨连续条件 (Lipschitz continuous) , 称为 利普希茨常数 (Lipschitz constant) 。 一般取 或 , 。

 

Theorem 4 Lipschitz continuous

 

如果是 locally Lipschitz continuous function,则其在任意位置是可微的。如果 是 Lipschitz continuous 的,则:

 

如果是个线性映射函数, ,则有:

 

也就是说当时,函数 的利普希茨常数 (Lipschitz constant) 是 的最大奇异值。当 时,函数 的利普希茨常数 (Lipschitz constant) 是 的每行和的极大值。

 

在 Self-attention 中,假设输入Dot-product multihead self-attention (DP-MHA) 的表达式为:

 

式中,是可学习的参数, 是 softmax 的输出,输出过程是:

 

现在的问题是 Dot-product multihead self-attention 是 Lipschitz continuous 的吗?

 

考虑 head=1 的情况,即只考虑这一步,输入是 ,输出是 ,右乘 这一步属于是线性变换,一定是 Lipschitz continuous 的。但是左乘 之后就不一定了,因为这个 矩阵它不是独立于 的,而是和 密切相关的。所以对于这个问题有以下定理:

 

Theorem 7

 

对于的任意 范数 ,Dot-product multihead self-attention 不是 Lipschitz continuous 的。

 

( 这块的证明涉及到比较多的数学知识,而且论文证明步骤简略,我自己推细节的时候也觉得很恶心,所以如果你觉得不重要的话,可以直接跳过这段证明。)

 

证明:

 

映射函数可以写成:

 

且。

 

下面为了计算映射函数对 的梯度 (Jacobian 矩阵),就需要用到矩阵 对 的导数,这个矩阵对矩阵求导的方法可以参考下面这个文章:

 

科技猛兽:机器学习中的数学理论1:三步搞定矩阵求导

 

https://zhuanlan.zhihu.com/p/262751195

 

这里直接给出结论:矩阵对 的 Jacobian 矩阵是:

 

现在的问题转化成了求矩阵对 的导数。

 

为了计算的方便,每次计算一个。这里提一句为啥要这样一项一项地计算 ,因为仔细观察不难发现 函数是个包含 操作的函数, 是矩阵对矩阵的导数,它在有包含 操作时不易计算,而 是向量对向量的导数,计算相对容易,所以这里我们一项一项地计算。

 

根据上式有,则:

 

整个包括2项,第一项是对后面的 求导,得到 。

 

第二项是中的 对 求导,相当于是 对 求导,属于向量对向量的求导。

 

令,,则 。

 

因为:

 

所以有:。

 

所以整体而言,矩阵对 的导数为:

 

当时,有:

 

现在考虑这一项有:

 

式中其实是个离散的分布,假设输入是 ,概率分布是 。按照这样的讲法, 是个半正定的矩阵,因为 。

 

根据范数的性质,如果可以证明 是没有上界的,则就能够证明 是没有上界的。考虑 的情况,有:

 

则上式的第1项变为0,第3项变为 。第2项变为 ,可以是任意大的数,因为的分布并不受限。

 

所以证明了是没有上界的,则证明了 是没有上界的。所以 Dot-product multihead self-attention 不是 Lipschitz continuous 的。

 

得证。

 

下面我们细品一下这个过程,当时, 为输入取平均的操作。由于 的样本方差可以是任意大的,所以 的变化率也可以是任意大的,即雅可比矩阵 的值可以变得任意大。一种可能的解决办法是给输入一个上限,但是这限制了网络的 input,没有从根本上解决问题。

 

因此作者设计了一种基于范数的 self-attention 操作,表达式如下:

 

注意上述25式的计算是可以采取简便计算方法的,对于向量和 我们有:

 

所以25式等于:

 

则 L2 Self-attention 的过程可以重新写为:

 

式中,。

 

结论1:当时,L2 MHA是 Lipschitz 的。反之,则不是。

 

结论2:

 

的上界是:

 

结论3:

 

的上界是:

 

总结

 

本文介绍了 Lipschitz 条件,Lipschitz 常数,以及Lipschitz 深度神经网络模型,包括 MLP 网络中的 Lipschitz 条件,和 Self-attention 网络中的 Lipschitz 条件。MLP 网络是 Lipschitz continuous 的,但是 Dot-product multihead self-attention 不是 Lipschitz continuous 的。而改进的方案 L2 multihead self-attention 则是 Lipschitz continuous 的。

 

参考:

 

1 Zeap:非凸优化基石:Lipschitz Condition (https://zhuanlan.zhihu.com/p/27554191)

 

2 Nesterov <Introductory Lectures on Convex Programming>

 

Be First to Comment

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注