本文主要整理下Batch、Online场景下,各种常用的最优化算法。内容上大部分是参考其他博客,并无太多原创成分,目的是梳理知识点,加深理解。
因此会尽量在必要的地方添加来源信息,如有遗漏或者错误之处,请不吝指出!
谈及机器学习问题的参数最优化求解算法,两大应用场景(训练方式)——Batch、Online占据了相当重要的地位。借助本博文,作者出于知识整理、逻辑疏剪的目的,简单叙述下Batch和Online场景下,多种常用最优化算法的异同之处。
一般机器学习参数优化问题,都使用Batch方式进行训练。此时在全量数据上进行训练的成本,尚在可接受范围之内,因此讨论更多的,是如何更高效、更准确地得到「全局最优解」。
我们从随机梯度下降(SGD)开始。
博文1有提到,SGD以及一系列基于SGD演变而来的算法,都可以使用一个统一的框架来描述。各个算法的不同,也不过是对框架中某个步骤的改动而已。
即:
给定一个优化目标参数$w$,以及目标函数$f(w)$,初始学习率$\alpha$,在t+1时刻,基于SGD的最优化算法以如下步骤进行迭代:
- 计算梯度值$g_t=\nabla f(w_t)$
- 计算一阶动量$m_t=\phi(g_1,g_2,…,g_{t}), V_t=\varphi(g_1,g_2,…,g_{t})$
- 计算下降梯度$\eta_{t}=\alpha * \frac{m_t}{\sqrt{V_t}} $
- 更新权重$w_{t+1} = w_{t} - \eta_t$
后续提到的算法(如SGD-M、AdaGrad、Adam等,无非就是在修改上述4个步骤中的一或者多个,框架依然保持一致。
1. SGD
SGD算法直接使用梯度作为一阶动量,同时未引入二阶动量参与学习率的调整,一般直接使用一个随当前时刻$t$严格递减的函数调整学习率。具体来说,是更改步骤2
的计算方法,如下:
这样的话,第三步下降梯度
计算可得:$\eta_t=\alpha \frac{g_t}{\sqrt{t}}$
SGD算法比较简明,有如下几个特点:
- 无须计算高阶动量
- 不用记忆任何数据的历史结果,内存消耗低
但由于SGD的下降梯度方向,完全由上一个时刻的梯度
决定,导致此算法容易在局部最优的鞍点处持续震荡,无法跳出,同时由于其学习率随着时刻严格递减,一定程度上加剧了「鞍点处震荡」的可能性。
2. SGD-Momentum
针对SGD由于下降梯度计算依据的单一性所导致的问题,SGD-Momentum(SGD-M)算法在计算下降梯度时,同时加权地
结合了当前时刻梯度
以及历史上累积梯度(动量)
,在持续快速变化的参数上,加速其更新过程,以此「抑制」SGD算法所遇到的「容易在鞍点处震荡」的情况发生。具体来说,SGD-M算法是更改了上述框架中的步骤2
中一阶动量的计算方法,如下:
上式中$\beta$一般经验值取0.9。这个参数意味着某个时刻的下降梯度,主要由其历史的指数移动平均动量
决定(经验参数$\beta=0.9$),同时也小程度($1-\beta$)
地参考当前时刻梯度值,以此,SGD-M算法能够在持续变化较快的参数上,加速其更新过程,从而在一定程度上「抑制」了SGD算法「鞍点处震荡」的问题。
3. N-SGD
同样是为了解决SGD中遇到的「容易在鞍点处震荡」问题,Nesterov Accelerated SGD(N-SGD)采用了与SGD-M不同的角度切入,直接修改框架中步骤1
中梯度的计算。具体来说,是梯度的计算,从只考虑上一个时刻目标参数的梯度,修改为基于「根据已有累积动量
更新后的目标参数」。具体如下:
感官上来讲,N-SGD算法,是先根据已有累积动量
更新一次目标参数,然后在此基础之上,结合Momentum的计算方法,同时考虑累积动量
和当前梯度
,得出最终的下降梯度。以此,N-SGD算法相对于正常的SGD或者SGD-M,在计算下降梯度时,预先地往前看一步
,极大地加速了优化问题的收敛过程。
4. AdaGrad
1.1-1.3中涉及的三个算法,都未引入二阶动量,它们只是使用了不同的一阶动量生成方法,其学习率的变化,并不会依据任何与某时刻的参数变化情况而定,一般是采用与当前时刻呈严格递减的函数
作为学习率确定方法。
上述算法无法根据各个参数情况的不同,做适应性的调整,即:不论参数变化多寡,都是采用统一的学习率,不利于某些展现规模较低特征(反而可能更有用)的更新优化。
AdaGrad方法针对此情况,修改了算法框架中的步骤2
,引入二阶动量
的计算,一般采用$V_t=\sum^{t}_{r=1}{g_r^{2}}$的经验式,以此,对一些经常展现、更新的参数(也就是累积二阶动量比较大),学习率变得更小,更新更加缓慢、谨慎,而对一些变动较少的参数(累积动量较小),算法为其分配了更大的学习率,期望能从少量样本中学到更多信息。
具体来说,
可以看到,学习率从$\alpha/\sqrt{t}$变成了$\alpha/\sqrt{\sum_{r=1}^{t}g_r^2}$,在稀疏数据上,此算法有比较好的表现,但对于比较稠密的数据,大部分参数都会更新比较频繁,上述学习率随着迭代次数的增加,愈发趋近于0,从而导致算法提前结束或者只能得到局部最优。因此,上述方法在迭代轮数足够长的情况下,很容易导致算法在一个局部最优处震荡,无法提供足够的变动,让参数跳出,得到全局最优的可能较低。
5. AdaDelta
针对AdaGrad上述问题,AdaDelta将全局的二阶累积动量,修改为固定窗口的受限二阶累积动量,以此抑制「学习率因为迭代次数的累加,而趋近于0」的问题。具体来说,
这样,累积的二阶动量,可以通过参数$\beta$的调整,仅仅基于最新几次(约等于$1/(1-\beta)$个时刻)迭代得到,从而避免AdaGrad中的问题。
6. Adam
既然有了AdaDelta动态的根据二阶累积动量,为不同情况的特征(参数)调整不同的学习率,也有SGD-M根据一阶累积动量,调整梯度的方向,加速算法收敛,那Adam算法便是同时结合了这两种算法,采各家之所长,「既能加速收敛,亦能灵活地根据参数不同情况,得到更优的结果」。具体来说,Adam算法修改了上述算法框架中的步骤2
:
兼具加速收敛
以及更优结果
的长处之外,Adam算法也有一些隐忧2。
首先,Adam算法可能没办法收敛。这个问题,是由于采用了与AdaDelta相同的二阶累积梯度
作为学习率的策略,我们没办法保证$V_{t} = \beta_{2} * V_{t-1} + (1-\beta_{2})*g_{t}^{2}$所计算出来的$V_{t}$一定是随着t严格单调递增的
,所以学习率也没有办法保证是严格递减的。因此在持续迭代的过程中,存在着一定可能性会出现算法无法正常收敛的情况。
针对这个问题,文章3提出了一个remedy。将上述二阶累积动量的更新方式,修改为$V_{t} = max(\beta_{2}V_{t-1} + (1-\beta_{2})g_{t}^{2}, V_{t-1})$,以此保证$V_{t}$是随着t单调递减
的,保证算法一定能够收敛。
其次,Adam算法得到的结果,不一定是最优结果。这个情况更多可能出现在深度学习模型的优化
场景下,在此类模型中,参数维度极高,相对于正常较低维度的参数空间,非凸目标函数
更大可能会出现很多局部最优点,坑坑洼洼
,由于采用了与SGD-M一致的累积一阶动量移动平均
作为梯度计算策略,Adam算法在计算梯度方向时,会参考历史的累积动量,在某些高峰处,很容易直接越过;而在某些高原平面,容易陷入无法跳出,结束训练。
7. N-Adam
既然Adam同时采AdaDelta和SGD-M之所长,那么N-SGD所使用的加速收敛方法,也可以合入Adam算法,这就是Nesterov Accelerated Adam(N-Adam)算法。具体来说,在Adam算法的基础之上,N-Adam如果N-SGD之于SGD的修改一样,对算法框架中的步骤1
做了调整:
至此,我们使用一个统一的优化算法框架,整理了Batch场景下,SGD类的几个主要优化算法以及它们各自的优缺点。
接下来,我们转向Online场景,看看在大规模数据下,为了增加模型(参数)的稀疏性,各种层出不穷的算法所做出的努力。