发布网友 发布时间:2023-04-01 17:20
共1个回答
热心网友 时间:2023-11-22 06:11
主要介绍SGD算法,以及贾蓉、金池、黄芙蓉撰写的两篇分析其逃离鞍点的论文《:逃离鞍点——张量分解的在线病理梯度》和金池、贾蓉等人的最新力作《如何高效逃离鞍点》。
如果要优化一个函数,也就是求它的最小值,常用的方法叫做梯度下降(GD),也就是最速下降法。简单来说,你每沿着当前位置的导数方向走一小步,就一定能走到好的地方。
如上图所示,就像你下山,每走一步都走最陡的路。如果最后没有摔死,一般很快就能到山脚下。从数学上来说,是的
这是步长t的位置,导数,和步长。所以这个算法很简单,就是重复这条线迭代。
虽然简单美观,但GD算法至少有两个明显的缺陷(其实更多,不过今天先说这两个)。
首先,当我们使用它的时候,尤其是在机器学习的使用中,我们都会面对一个非常庞大的数据集。这时候,如果我们坚持要计算精确导数(别管是什么,反正每个机器学习算法里都有这么一个东西),往往意味着我们要扫描整个数据集好几个小时,然后只能走一小步。一般GD收敛需要几千上万步,根本完成不了。
其次,如果我们不小心陷入鞍点,或者局部最优不佳,GD算法也不会用完,因为这些点的导数都是0。什么是鞍点:
当地的最佳优势是什么(在下图的右侧):
有意思的是,这两个缺陷可以用同一个方法解决,就是我们今天要讲的随机梯度下降(SGD)算法。
SGD算法的表达式类似于GD:
这里是所谓的随机梯度,它满足
也就是说,虽然它包含了一些随机性,但它等于从期望出发的正确导数。其实SGD就像喝醉了的GD。它模模糊糊的认路,最后还能自己走回家,但是歪歪扭扭的。(红色的是GD的路线,粉色的是s GD的路线)。
如果你仔细观察,实际上SGD需要更多的步骤来收敛。毕竟是醉了。但由于它对导数的要求非常低,可以包含很多噪声,只要期望是正确的(有时期望是错误的),所以导数可以非常快地计算出来。就拿我刚才说的机器学习举例,比如神经网络。在训练中,我们一次只从数百万个数据点中取128或256个数据点,计算一个不太精确的导数,然后用SGD走一步。想想看,这样计算时间每次都快一万倍。就算要多走几趟,算下来也挺值的。
所以可以完美解决GD的第一个问题。3354慢。这也是当初人们使用SGD的主要目的。而且,你也不用担心导数中包含的噪声的负面影响。大量的理论工作表明,只要噪声不离谱(至少在f是凸函数的情况下),SGD就能很好地收敛。
虽然理论家这么说,但许多完美主义者仍然对使用带有随机噪声的导数来训练他们的神经网络感到不安。他们必须使用最精确的导数。所以他们经常尝试用GD再次运行它,并与SGD获得的结果进行比较。
结果如何?因为我经常做这样的事情,所以我可以负责任的告诉你,即使GD有成百上千倍的时间去训练,最后的结果也是SGD的网络性能比GD好很多!
惊喜吧?有噪声的算法更好,就像说“让路上的司机多喝点,交通会更顺畅”一样让人无法接受。
但事实就是如此。在实践中,人们发现SGD除了计算速度快之外,还有许多优良的性质。它能自动逃离鞍点和局部最优。而且最终找到的答案有很强的泛化能力,就是在从未见过但服从相同分布的数据集上也能表现非常好!
这是为什么呢?今天我们就简单说说它为什么能逃出鞍点。有机会后我再详细介绍一下SGD的其他优秀性质,——。这些性质也是优化和机器学习领域的热点问题。
那么我们先来了解一下鞍点的数学表达式是什么。
首先,我们考虑导数为零的情况。这些点称为驻点,即稳定点。如果这个点是稳定的,它可以是一个(局部)最小值,一个(局部)最大值或一个鞍点。如何判断?我们可以计算它的海森矩阵h。
如果h为负,则所有特征值都为负。这时候不管你往哪个方向走,导数都会变成负值,也就是说函数值会减小。所以,这是(局部)最大值。
如果h是正的,则所有特征值都是正的。这时候不管你往哪个方向走,导数都会变成正的,也就是说函数值会上升。所以,这是(局部)最小值。
如果h同时包含正负特征值,那么这个稳定点就是鞍点。具体参考之前的图片。也就是说,有些方向函数值会上升,有些方向函数值会下降。
虽然看起来包含了所有的信息,但其实不然!另一个很重要的情况是H可能包含特征值为0的情况。在这种情况下,我们无法判断属于哪种稳定点,往往需要参考更高维的导数。想想看,如果特征值是
0,就说明有些方向一马平川一望无际,函数值一直不变,那我们当然不知道是怎么回事了:)
我们今天讨论的情况只包含前三种,不包含第四种.第四种被称为退化了的情况,所以我们考虑的情况就叫做非退化情况。
在这种非退化的情况下面,我们考虑一个重要的类别,即 strict saddle 函数。这种函数有这样的特点:对于每个点 x
要么 x 的导数比较大
要么 x 的 Hessian 矩阵包含一个负的特征值
要么 x 已经离某一个(局部)最小值很近了
为什么我们要 x 满足这三个情况的至少一个呢?因为
如果 x 的导数大,那么沿着这个导数一定可以大大降低函数值(我们对函数有光滑性假设)
如果 x 的 Hessian 矩阵有一个负的特征值,那么我们通过加噪声随机扰动,跑跑就能够跑到这个方向上,沿着这个方向就能够像滑滑梯一样一路滑下去,大大降低函数值
如果 x 已经离某一个(局部)最小值很近了,那么我们就完成任务了,毕竟这个世界上没有十全十美的事情,离得近和精确跑到这个点也没什么区别。
所以说,如果我们考虑的函数满足这个 strict saddle 性质,那么 SGD 算法其实是不会被困在鞍点的.那么 strict saddle 性质是不是一个合理的性质呢?
实际上,有大量的机器学习的问题使用的函数都满足这样的性质。比如 Orthogonal tensor decomposition,dictionary learning, matrix completion 等等。而且,其实并不用担心最后得到的点只是一个局部最优,而不是全局最优。因为实际上人们发现大量的机器学习问题,几乎所有的局部最优是几乎一样好的,也就是说,只要找到一个局部最优点,其实就已经找到了全局最优,比如 Orthogonal tensor decomposition 就满足这样的性质,还有小马哥 NIPS16 的 best student paper 证明了 matrix completion 也满足这样的性质。我觉得神经网络从某些角度来看,也是(几乎)满足的,只是不知道怎么证。
下面讨论一下证明,主要讨论一下第二篇。第一篇论文其实就是用数学的语言在说"在鞍点加扰动,能够顺着负的特征值方向滑下去"。第二篇非常有意思,我觉得值得介绍一下想法。
首先,算法上有了一些改动。算法不再是 SGD,而是跑若干步 GD,然后跑一步 SGD。当然实际上大家是不会这么用的,但是理论分析么,这么考虑没问题。什么时候跑 SGD 呢?只有当导数比较小,而且已经很长时间没有跑过 SGD 的时候,才会跑一次。也就是说,只有确实陷在鞍点上了,才会随机扰动一下下。
因为鞍点有负的特征值,所以只要扰动之后在这个方向上有那么一点点分量,就能够一马平川地滑下去。除非分量非常非常小的情况下才可能会继续陷在鞍点附近。换句话说,如果加了一个随机扰动,其实大概率情况下是能够逃离鞍点的!
虽然这个想法也很直观,但是要严格地证明很不容易,因为具体函数可能是很复杂的,Hessian 矩阵也在不断地变化,所以要说明"扰动之后会陷在鞍点附近的概率是小概率"这件事情并不容易。
[原文 Figure 1 画得很漂亮,推荐一下]
热心网友 时间:2023-12-14 07:08
主要介绍SGD算法,以及贾蓉、金池、黄芙蓉撰写的两篇分析其逃离鞍点的论文《:逃离鞍点——张量分解的在线病理梯度》和金池、贾蓉等人的最新力作《如何高效逃离鞍点》。
如果要优化一个函数,也就是求它的最小值,常用的方法叫做梯度下降(GD),也就是最速下降法。简单来说,你每沿着当前位置的导数方向走一小步,就一定能走到好的地方。
如上图所示,就像你下山,每走一步都走最陡的路。如果最后没有摔死,一般很快就能到山脚下。从数学上来说,是的
这是步长t的位置,导数,和步长。所以这个算法很简单,就是重复这条线迭代。
虽然简单美观,但GD算法至少有两个明显的缺陷(其实更多,不过今天先说这两个)。
首先,当我们使用它的时候,尤其是在机器学习的使用中,我们都会面对一个非常庞大的数据集。这时候,如果我们坚持要计算精确导数(别管是什么,反正每个机器学习算法里都有这么一个东西),往往意味着我们要扫描整个数据集好几个小时,然后只能走一小步。一般GD收敛需要几千上万步,根本完成不了。
其次,如果我们不小心陷入鞍点,或者局部最优不佳,GD算法也不会用完,因为这些点的导数都是0。什么是鞍点:
当地的最佳优势是什么(在下图的右侧):
有意思的是,这两个缺陷可以用同一个方法解决,就是我们今天要讲的随机梯度下降(SGD)算法。
SGD算法的表达式类似于GD:
这里是所谓的随机梯度,它满足
也就是说,虽然它包含了一些随机性,但它等于从期望出发的正确导数。其实SGD就像喝醉了的GD。它模模糊糊的认路,最后还能自己走回家,但是歪歪扭扭的。(红色的是GD的路线,粉色的是s GD的路线)。
如果你仔细观察,实际上SGD需要更多的步骤来收敛。毕竟是醉了。但由于它对导数的要求非常低,可以包含很多噪声,只要期望是正确的(有时期望是错误的),所以导数可以非常快地计算出来。就拿我刚才说的机器学习举例,比如神经网络。在训练中,我们一次只从数百万个数据点中取128或256个数据点,计算一个不太精确的导数,然后用SGD走一步。想想看,这样计算时间每次都快一万倍。就算要多走几趟,算下来也挺值的。
所以可以完美解决GD的第一个问题。3354慢。这也是当初人们使用SGD的主要目的。而且,你也不用担心导数中包含的噪声的负面影响。大量的理论工作表明,只要噪声不离谱(至少在f是凸函数的情况下),SGD就能很好地收敛。
虽然理论家这么说,但许多完美主义者仍然对使用带有随机噪声的导数来训练他们的神经网络感到不安。他们必须使用最精确的导数。所以他们经常尝试用GD再次运行它,并与SGD获得的结果进行比较。
结果如何?因为我经常做这样的事情,所以我可以负责任的告诉你,即使GD有成百上千倍的时间去训练,最后的结果也是SGD的网络性能比GD好很多!
惊喜吧?有噪声的算法更好,就像说“让路上的司机多喝点,交通会更顺畅”一样让人无法接受。
但事实就是如此。在实践中,人们发现SGD除了计算速度快之外,还有许多优良的性质。它能自动逃离鞍点和局部最优。而且最终找到的答案有很强的泛化能力,就是在从未见过但服从相同分布的数据集上也能表现非常好!
这是为什么呢?今天我们就简单说说它为什么能逃出鞍点。有机会后我再详细介绍一下SGD的其他优秀性质,——。这些性质也是优化和机器学习领域的热点问题。
那么我们先来了解一下鞍点的数学表达式是什么。
首先,我们考虑导数为零的情况。这些点称为驻点,即稳定点。如果这个点是稳定的,它可以是一个(局部)最小值,一个(局部)最大值或一个鞍点。如何判断?我们可以计算它的海森矩阵h。
如果h为负,则所有特征值都为负。这时候不管你往哪个方向走,导数都会变成负值,也就是说函数值会减小。所以,这是(局部)最大值。
如果h是正的,则所有特征值都是正的。这时候不管你往哪个方向走,导数都会变成正的,也就是说函数值会上升。所以,这是(局部)最小值。
如果h同时包含正负特征值,那么这个稳定点就是鞍点。具体参考之前的图片。也就是说,有些方向函数值会上升,有些方向函数值会下降。
虽然看起来包含了所有的信息,但其实不然!另一个很重要的情况是H可能包含特征值为0的情况。在这种情况下,我们无法判断属于哪种稳定点,往往需要参考更高维的导数。想想看,如果特征值是
0,就说明有些方向一马平川一望无际,函数值一直不变,那我们当然不知道是怎么回事了:)
我们今天讨论的情况只包含前三种,不包含第四种.第四种被称为退化了的情况,所以我们考虑的情况就叫做非退化情况。
在这种非退化的情况下面,我们考虑一个重要的类别,即 strict saddle 函数。这种函数有这样的特点:对于每个点 x
要么 x 的导数比较大
要么 x 的 Hessian 矩阵包含一个负的特征值
要么 x 已经离某一个(局部)最小值很近了
为什么我们要 x 满足这三个情况的至少一个呢?因为
如果 x 的导数大,那么沿着这个导数一定可以大大降低函数值(我们对函数有光滑性假设)
如果 x 的 Hessian 矩阵有一个负的特征值,那么我们通过加噪声随机扰动,跑跑就能够跑到这个方向上,沿着这个方向就能够像滑滑梯一样一路滑下去,大大降低函数值
如果 x 已经离某一个(局部)最小值很近了,那么我们就完成任务了,毕竟这个世界上没有十全十美的事情,离得近和精确跑到这个点也没什么区别。
所以说,如果我们考虑的函数满足这个 strict saddle 性质,那么 SGD 算法其实是不会被困在鞍点的.那么 strict saddle 性质是不是一个合理的性质呢?
实际上,有大量的机器学习的问题使用的函数都满足这样的性质。比如 Orthogonal tensor decomposition,dictionary learning, matrix completion 等等。而且,其实并不用担心最后得到的点只是一个局部最优,而不是全局最优。因为实际上人们发现大量的机器学习问题,几乎所有的局部最优是几乎一样好的,也就是说,只要找到一个局部最优点,其实就已经找到了全局最优,比如 Orthogonal tensor decomposition 就满足这样的性质,还有小马哥 NIPS16 的 best student paper 证明了 matrix completion 也满足这样的性质。我觉得神经网络从某些角度来看,也是(几乎)满足的,只是不知道怎么证。
下面讨论一下证明,主要讨论一下第二篇。第一篇论文其实就是用数学的语言在说"在鞍点加扰动,能够顺着负的特征值方向滑下去"。第二篇非常有意思,我觉得值得介绍一下想法。
首先,算法上有了一些改动。算法不再是 SGD,而是跑若干步 GD,然后跑一步 SGD。当然实际上大家是不会这么用的,但是理论分析么,这么考虑没问题。什么时候跑 SGD 呢?只有当导数比较小,而且已经很长时间没有跑过 SGD 的时候,才会跑一次。也就是说,只有确实陷在鞍点上了,才会随机扰动一下下。
因为鞍点有负的特征值,所以只要扰动之后在这个方向上有那么一点点分量,就能够一马平川地滑下去。除非分量非常非常小的情况下才可能会继续陷在鞍点附近。换句话说,如果加了一个随机扰动,其实大概率情况下是能够逃离鞍点的!
虽然这个想法也很直观,但是要严格地证明很不容易,因为具体函数可能是很复杂的,Hessian 矩阵也在不断地变化,所以要说明"扰动之后会陷在鞍点附近的概率是小概率"这件事情并不容易。
[原文 Figure 1 画得很漂亮,推荐一下]