算法面试|SGD,Adam,momentum等优化算法比较算法面试|优化算法

文章目录

SGD,Adam,momentum等优化算法总结

一、最基本的优化算法

1.SGD
2.Momentum

二、自适应参数的优化算法

1.Adagrad
2.RMSprop
3.Adam

三、二阶近似的优化算法

5.牛顿法及拟牛顿法

SGD,Adam,momentum等优化算法总结

1.选择哪种优化算法并没有达成共识
2.具有自适应学习率（以RMSProp 和AdaDelta 为代表）的算法族表现得相当鲁棒，不分伯仲，但没有哪个算法能脱颖而出。
3.对于当前流行的优化算法包括括SGD、具动量的SGD、RMSProp、具动量的RMSProp、AdaDelta 和Adam而言，选择哪一个算法似乎主要取决于使用者对算法的熟悉程度（以便调节超参数）
4.基本不用二阶近似优化算法

一、最基本的优化算法 1.SGD
Batch Gradient Descent
Θ = Θ ? α ? ? Θ J ( Θ ) \Theta = \Theta - \alpha\cdot\nabla_\Theta J(\Theta) Θ=Θ?α??Θ?J(Θ)
优点:
cost fuction若为凸函数，能够保证收敛到全局最优值；若为非凸函数，能够收敛到局部最优值
缺点:
由于每轮迭代都需要在整个数据集上计算一次，所以批量梯度下降可能非常慢
训练数较多时，需要较大内存
批量梯度下降不允许在线更新模型，例如新增实例。
Stochastic Gradient Descent
Θ = Θ ? α ? ? Θ J ( Θ ; x ( i ) , y ( i ) ) \Theta = \Theta - \alpha\cdot\nabla_\Theta J(\Theta; x^{(i)},y^{(i)}) Θ=Θ?α??Θ?J(Θ; x(i),y(i))
优点:
算法收敛速度快(在Batch Gradient Descent算法中, 每轮会计算很多相似样本的梯度, 这部分是冗余的)
可以在线更新
有几率跳出一个比较差的局部最优而收敛到一个更好的局部最优甚至是全局最优
缺点:
容易收敛到局部最优，并且容易被困在鞍点
Mini-batch Gradient Descent
Θ = Θ ? α ? ? Θ J ( Θ ; x ( i : i + n ) , y ( i : i + n ) ) \Theta = \Theta - \alpha\cdot\nabla_\Theta J(\Theta; x^{(i:i+n)},y^{(i:i+n)}) Θ=Θ?α??Θ?J(Θ; x(i:i+n),y(i:i+n))
上述三个方法面临的主要挑战如下：
选择适当的学习 α \alpha α较为困难。太小的学习率会导致收敛缓慢，而学习速度太块会造成较大波动，妨碍收敛。
目前可采用的方法是在训练过程中调整学习率大小，例如模拟退火算法：预先定义一个迭代次数m，每执行完m次训练便减小学习率，或者当cost function的值低于一个阈值时减小学习率。然而迭代次数和阈值必须事先定义，因此无法适应数据集的特点。
上述方法中, 每个参数的 learning rate 都是相同的，这种做法是不合理的：如果训练数据是稀疏的，并且不同特征的出现频率差异较大，那么比较合理的做法是对于出现频率低的特征设置较大的学习速率，对于出现频率较大的特征数据设置较小的学习速率。
近期的的研究表明，深层神经网络之所以比较难训练，并不是因为容易进入local minimum。相反，由于网络结构非常复杂，在绝大多数情况下即使是 local minimum 也可以得到非常好的结果。而之所以难训练是因为学习过程容易陷入到马鞍面中，即在坡面上，一部分点是上升的，一部分点是下降的。而这种情况比较容易出现在平坦区域，在这种区域中，所有方向的梯度值都几乎是 0。
2.Momentum
SGD方法的一个缺点是其更新方向完全依赖于当前batch计算出的梯度，因而十分不稳定。
v d W [ l ] = β v d W [ l ] + ( 1 ? β ) d W [ l ] W [ l ] = W [ l ] ? α v d W [ l ] v_{dW^{[l]}} = \beta v_{dW^{[l]}} + (1-\beta)dW^{[l]}\\ W^{[l]} = W^{[l]} - \alpha v_{dW^{[l]}} vdW[l]?=βvdW[l]?+(1?β)dW[l]W[l]=W[l]?αvdW[l]? v d b [ l ] = β v d b [ l ] + ( 1 ? β ) d b [ l ] b [ l ] = b [ l ] ? α v d b [ l ] v_{db^{[l]}} = \beta v_{db^{[l]}} + (1-\beta)db^{[l]}\\ b^{[l]} = b^{[l]} - \alpha v_{db^{[l]}} vdb[l]?=βvdb[l]?+(1?β)db[l]b[l]=b[l]?αvdb[l]?
其中 β 是动量，一般设置为0.9， α 是学习速率。该公式蕴含这一种思想——指数加权平均。
特点：

下降初期时，使用上一次参数更新，下降方向一致，乘上较大的\mu能够进行很好的加速
下降中后期时，在局部最小值来回震荡的时候， g r a d i e n t → 0 gradient\to0 gradient→0， μ \mu μ使得更新幅度增大，跳出陷阱
在梯度改变方向的时候， μ \mu μ能够减少更新总而言之，momentum项能够在相关方向加速SGD，抑制振荡，从而加快收敛

二、自适应参数的优化算法 1.Adagrad
r t = r t ? 1 + g t 2 r_t = r_{t-1}+g_t^2 rt?=rt?1?+gt2? θ t = θ t ? 1 ? α r t + ? g t \theta_t = \theta_{t-1}-\frac{\alpha}{\sqrt{r_t+\epsilon}}g_t θt?=θt?1??rt?+? ?α?gt?
2.RMSprop
E [ g 2 ] t = 0.9 E [ g 2 ] t ? 1 + 0.1 g t 2 E[g^2]_t = 0.9E[g^2]_{t-1}+0.1g_t^2 E[g2]t?=0.9E[g2]t?1?+0.1gt2? θ t + 1 = θ t ? α E [ g 2 ] t + ? ? g t \theta_{t+1} = \theta_t-\frac{\alpha}{\sqrt{E[g^2]_t+\epsilon}}\cdot g_t θt+1?=θt??E[g2]t?+? ?α??gt?
RMSprop将学习率分解成一个平方梯度的指数衰减的平均。Hinton建议将γ设置为0.9，对于学习率 α \alpha α，一个好的固定值为0.01。
适合处理非平稳目标 - 对于RNN效果很好
3.Adam
Adam(Adaptive Moment Estimation)是另一种自适应学习率的方法。它利用梯度的一阶矩估计和二阶矩估计动态调整每个参数的学习率。Adam的优点主要在于经过偏差校正后，每一次迭代学习率都有个确定范围，使得参数比较平稳。
m t = β 1 m t ? 1 + ( 1 ? β 1 ) g t m ^ t = m t 1 ? β 1 t m_t=\beta_1m_{t-1}+(1-\beta_1)g_t\\ \hat m_t = \frac{m_t}{1-\beta_1^t} mt?=β1?mt?1?+(1?β1?)gt?m^t?=1?β1t?mt?? v t = β 2 v t ? 1 + ( 1 ? β 2 ) g t 2 v ^ t = v t 1 ? β 2 t v_t=\beta_2v_{t-1}+(1-\beta_2)g_t^2\\ \hat v_t = \frac{v_t}{1-\beta_2^t} vt?=β2?vt?1?+(1?β2?)gt2?v^t?=1?β2t?vt?? Θ t + 1 = Θ t ? α v ^ t + ? m ^ t \Theta_{t+1} = \Theta_t - \frac{\alpha}{\sqrt{\hat v_t}+\epsilon}\hat m_t Θt+1?=Θt??v^t? ?+?α?m^t?
Adam算法的提出者建议 α \alpha α默认值0.001,β 1 \beta_1 β1?的默认值为0.9， β 2 \beta_2 β2?的默认值为.999， ? \epsilon ?默认为 1 0 ? 8 10^{?8} 10?8
关于偏差修正的推导

文章图片

文章图片
我们希望知道时间步 t 上指数移动均值的期望值E [ v t ] E[v_t] E[vt?] 如何与真实的二阶矩 g t 2 g_t^2 gt2?相关联，所以我们可以对这两个量之间的偏差进行修正。下面我们同时对表达式(1)的左边和右边取期望，即如下所示：

文章图片

如果 g t 2 g_t^2 gt2?是静态的, 则 ζ = 0 \zeta=0 ζ=0,v ^ t = v t 1 ? β 2 t \hat v_t = \frac{v_t}{1-\beta_2^t} v^t?=1?β2t?vt??
Adams问题

Adam二阶动量是固定时间窗口内的累积，随着时间窗口的变化，遇到的数据可能发生巨变，使得V t V_t Vt?可能会时大时小，不是单调变化。这就可能在训练后期引起学习率的震荡，导致模型无法收敛。
Adams可能错失全局最优解.
自适应学习率算法可能会对前期出现的特征过拟合，后期才出现的特征很难纠正前期的拟合效果。

三、二阶近似的优化算法 5.牛顿法及拟牛顿法
牛顿法
考虑无约束最优化问题
min ? x ∈ R n f ( x ) \min_{x\in R^n} f(x) x∈Rnmin?f(x)假设f(x)具有二阶连续偏导,f(x)在 x ( k ) x^{(k)} x(k)附近进行二阶泰勒展开:
f ( x ) = f ( x k ) + g k T ( x ? x ( k ) ) + 1 2 ( x ? x ( k ) ) T H ( x ( k ) ) ( x ? x ( k ) ) f(x)=f(x^{k})+g_k^T(x-x^{(k)})+\frac12(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)}) f(x)=f(xk)+gkT?(x?x(k))+21?(x?x(k))TH(x(k))(x?x(k))牛顿法利用极小点的必要条件
? f ( x ) = 0 \nabla f(x)=0 ?f(x)=0假设 ? f ( x ( k + 1 ) ) = 0 \nabla f(x^{(k+1)})=0 ?f(x(k+1))=0, ? f ( x ( k + 1 ) ) = g k + H k ( x ( k + 1 ) ? x ( k ) ) = 0 \nabla f(x^{(k+1)})=g_k+H_k(x^{(k+1)}-x^{(k)})=0 ?f(x(k+1))=gk?+Hk?(x(k+1)?x(k))=0 x ( k + 1 ) = x ( k ) ? H k ? 1 g k x^{(k+1)} = x^{(k)}-H_k^{-1}g_k x(k+1)=x(k)?Hk?1?gk?
拟牛顿法
海塞矩阵的逆矩阵 H ? 1 H^{-1} H?1不好求,考虑使用一个n阶矩阵 G k = G ( x ( k ) ) G_k=G(x^{(k)}) Gk?=G(x(k))代替
【算法面试|SGD,Adam,momentum等优化算法比较】参考链接