导读
特别声明:本文仅有的一点贡献就是用自己的理解翻译了 Leon Bottou 等人的论文 <Optimization Methods for Large-Scale Machine Learning>,初窥门径,才疏学浅,疏漏之处,望不吝指教。
引子
大家都知道,训练深度网络一般用的是 SGD (Stochastic Gradient Descent | 随机梯度下降)而不是 GD (Gradient Descent | 梯度下降),但是有没有考虑过 SGD 为什么比 GD 更受大家宠爱,SGD 是如何在用较低的 Computational Complexity (一般可以大概理解成,达成目标需要计算 Gradient 的次数)的同时还能保证比较好的训练效果。
本文主要给出几个特殊的例子,给大家一个从直觉性,实验上和理论上认知,为什么有时候,相对于GD 我们更宠爱 SGD?
我们主要从以下三个方面,一起看一看 SGD 相对于 GD 的优势。
Prat I: 直觉上 ( Intuitive Motivation)
Prat II: 实验上 ( Practical Motivation )
Prat III: 理论上 (Theoretical Motivation)
背景知识
我们一般想要优化的函数形式如下
我们知道梯度下降每一次迭代都需要出所有的梯度,即每一次算n个梯度,进行下面的迭代
而随机梯度下降,每一次选一个
计算梯度,然后迭代
Part I: 直觉上 ( Intuitive Motivation)
结论是:相对于非随机算法,SGD 能更有效的利用信息,特别是信息比较冗余的时候。
Prat II: 实验上 ( Practical Motivation )
结论是:相对于非随机算法, SGD 在前期迭代效果卓越。
我直接截论文上面的图,大家观赏一下
L-BFGS是一种需要算所有梯度,还要拟合Hessian 的一个优化算法.。不过既然是要算 full gradient, 大家直接理解成一种像 GD 一样的非随机的算法吧。 x 轴可以看成计算的梯度的数量,y轴可以看成是和真实最小值的误差。(个人理解哈,可能有偏差,大家会个意呗,想精确了解的,自己去看看原论文呗~~)
比较上图可得,随机算法 SGD 前期每个 iteration 找到的迭代点,可以显著的接近最小值点。
这里又有一个特别好玩的小例子来解释为什么 SGD 前期表现好,后期就水了现象。
这是我最想翻译的部分!!其他可以跳过,这里要认真听了哈~~。
假设我们需要优化的函数全部是二次函数,形式如下
其中
是常数,并且满足
我们求导,令导数等于零得到
其实这就是一堆sample, 在平方距离公式下,离他们最近的点就是他们的均值。
结合我们的假设公式(2.2)我们得到,最小值点在0处,也就是
所以函数的最小值点在0处。我们现在看看 SGD 的表现,假设我们最开始的初始点在最左边,然后无论你选到那个二次函数的分支,沿着梯度,都能向靠近最小值点的方向移动。所以SGD 前期效率很高。
我们假设选中最左边那个
,举个例子。
而到了后期,我们的
足够靠近我们的最小值点
,那么单纯靠选择一个二次函数的导数方向移动,便不能达到很好的效果,时而远离最小值点 “0”,时而接近最小值点,我们的前进方向开始犹豫徘徊,这时候便需要计算更多的梯度信息来进行决策了。你看下图,选
会背离,选
会接近,就如同诗经《蒹葭》里面描述你追求你心爱的姑娘一样,溯洄从之,宛在水中央。 溯游从之,宛在水中坻。 朦朦胧胧不知方向,忽近忽远~~。这个时候你需要更多的信息了。
多好的例子啊!!!奇美无比~~~。
我突然意识到,随机梯度下降怎么和与女生相处那么相似。刚开始,离的远的时候,不经意间便能产生好感,慢慢靠近。等靠的近了,好感想转换成爱情的时候,便开始茫然失措,不知方向,忽远忽近~~。
忽近忽远后怎么办?
所以对于随机梯度下降,我其实不太清楚如何解决忽近忽远,但是如果想随机梯度下降收敛的比较好,我知道的方法有,一是采取递减的 stepsize,原理是什么我还没搞清楚,二就是 Variance reduction 的一些方法吧,比如采用更多的样本算梯度,或者用SAGA, SVRG这种方法吧。个人猜测,这些做法是不是为了解决忽近忽远的问题,其实我不太清楚,当个讨论题,希望有大牛能帮我们解答一下。
Prat III: 理论上 (Theoretical Motivation)
结论是:如果样本数量大,那么 SGD的Computational Complexity 依然有优势。
我们知道, GD 在强凸的情况下收敛速度是 Linear Convergence, 最差的情况下,至少需要迭代
次,才能达到
的精度,加上 GD 每一次需要计算 n 个梯度,所以总的 Computational Complexity 是
。
至于 SGD, 结论是 为了达到
, 在最差的情况下,我们需要迭代次数是
,但是因为 SGD 每一次就算一个梯度,所以它的 Computational Complexity 也是
。这些复杂度的证明我看看以后有时间写一下好了,当个小练习,但是不是今天的重点,故略去。
放在表格里面就是这样子的了
对比与 GD 的
,SGD 的
受所需的精度
的影响较大, 但是如果是在 Large Large Data 的设定下,n 会特别特别大, 这样 SGD 的Computational Complexity 依然是可以小于 GD 的Computational Complexity,换就换就是,如果n特别大,那么 SGD 在Computational Complexity 上依然有优势。
总结
好了总结一下, SGD 相比与 GD 优势如下:
Prat I: 相对于非随机算法,SGD 能更有效的利用信息,特别是信息比较冗余的时候。
Prat II: 相对于非随机算法, SGD 在前期迭代效果卓越。
Prat III: 如果样本数量大,那么 SGD的Computational Complexity 依然有优势。
以上三条,吹牛必背。
每日一题
下列哪个不属于CRF模型对于HMM和MEMM模型的优势( )
A、特征灵活
B、速度快
C、可容纳较多上下文信息
D、全局最优
正确答案:B
解析:
HMM模型是对转移概率和表现概率直接建模,统计共现概率。而MEMM模型是对转移概率和表现概率建立联合概率,统计时统计的是条件概率。CRF是在给定需要标记的观察序列的条件下,计算整个标记序列的联合概率分布,而不是在给定当前状态条件下,定义下一个状态的状态分布。MEMM容易陷入局部最优,是因为MEMM只在局部做归一化。CRF模型中,统计了全局概率,在做归一化时,考虑了数据在全局的分布,而不是仅仅在局部归一化,这样就解决了MEMM中的标记偏置的问题。
CRF没有HMM那样严格的独立性假设条件,因而可以容纳任意的上下文信息,特征设计灵活。CRF需要训练的参数更多,与MEMM和HMM相比,它存在训练代价大、复杂度高的缺点。
IELTS a bit
hectares n. 公顷
typo n. 打印错误;打字或文稿小错误