常用的梯度下降优化算法

梯度下降是常用的优化方式，具体的算法有：

• 梯度下降法
  • 批梯度下降(Batch Gradient Descent, BGD)
  • 随机梯度下降(Stochastic Gradient Decent, SGD)
  • 小批量梯度下降(Mini-Batch Gradient Decent, MBGD)
• 梯度下降优化
  • 动量梯度下降(Gradient Descent with Momentum)
  • 均方根支(Root Mean Square Prop, RMSprop)
  • 自适应矩估计(Adaptive Moment Estimation, Adam)

本文主要简单介绍上述优化方法

梯度下降法

梯度下降法(gradient descent)是求解无约束最优化问题的一种最常用方法，它是一种迭代算法，每一步需要求解目标函数的梯度向量。它的优点是实现简单，缺点是一般情况下不能保证解是全局最优的

方向导数定义： 如上图, p′ 沿着 l 趋于 p 时，如果函数的增量 f(x+Δx,y+Δy)−f(x,y) 与 pp′ 两点间的距离 ρ=(Δx)2+(Δy)2 的比值的极限存在，则称此极限为 p 沿着 l 方向的导数，记作

(1)∂f∂l=limρ→0f(x+Δx,y+Δy)−f(x,y)ρ

更一般的，对于函数 f(x) , 在 x0 处的导数为

f′(x0)=limx→x0f(x)−f(x0)x−x0=limΔx→0f(x0+Δx)−f(x0)Δx

函数在某点的梯度的方向与取得最大方向导数的方向一致，而它的模为方向导数的最大值

定义： 设函数 z=f(x,y) 在平面区域D内，具有一阶连续偏导数，则对于每一点 p(x,y)∈D , 都可定义一个向量 ∂f∂x→i+∂f∂y→j 满足梯度的条件，则这向量称为 z=f(x,y) 在点 p(x,y) 的梯度，记作

gradf(x,y)=∂f∂x→i+∂f∂y→j

牛顿法和拟牛顿法

牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法，它的优点是收敛速度快。一般用来求解大规模数据的优化问题

海森矩阵(Hessian Matrix)

海森矩阵是一个多变量实值函数的二阶偏导数组成的方块矩阵,假设有一实数函数 f(x1,x2,...,xn) ，如果 f 所有的二阶偏导数都存在，那么海森矩阵为对称矩阵， f 的海森矩阵的第 ij 项即为 H(f)ij(x)=DiDjf(x) ，其中 x=(x1,x2,...,xn) 即

更一般的海森矩阵也可表示为

H(x)=[∂2f∂xi∂xj]n×n

正定半正定矩阵

• 正定矩阵：所有特征值大于0 (>0)
• 负定矩阵：所有特征值小于0 (<0)
• 半正定矩阵： 所有特征值为非负（>=0）
• 半负定矩阵：所有特征值为非正（<=0）
• 不定矩阵：特征值有正有负

牛顿法是迭代算法，每一步需要求解目标函数的海森矩阵的逆矩阵，计算方法比较复杂，这里不详细叙述，具体可阅读Newton's method in optimization

拟牛顿法是通过正定矩阵近似的海森矩阵的逆矩阵来简化牛顿法的计算过程，常用算法有 DFP, BFGS

在几何上 z=f(x,y) 表示一个曲面，当曲面被平面 z=c 所截，得到的曲线 {z=f(x,y)z=c 在 xoy 面上的投影方程 f(x,y)=c 称为等值线，几何上称为等高线

梯度下降法

批梯度下降(Batch Gradient Descent, BGD)

批梯度下降法在更新参数时使用所有样本来进行更新

J(w,b)=1m∑i=1mL(y(i)^,y(i))+λ2m∑∥w∥F2wj:=wj−α∂J(w,b)∂wjbj:=bj−α∂J(w,b)∂bj

其中 λ2m∑∥w∥F2 是L2正则项, α 是学习速率 learning rate

BGD的梯度下降图

BGD的优缺点

• 优点：最小化所有训练样本的损失函数得到全局最优
• 缺点：当样本数目很多时，训练过程很慢

Python伪代码

for epoch in range(epochs):
    # 是对每个epoch的所有数据进行计算的
    grad = loss_fn(*args, **kwargs)
    params = params - learning_rate * grad

随机梯度下降(Stochastic Gradient Decent, SGD)

每次通过一个样本来迭代更新

J(w,b)=L(y(i)^,y(i))+λ2∑∥w∥F2wj:=wj−α∂J(w,b)∂wjbj:=bj−α∂J(w,b)∂bj

SGD的梯度下降图

SGD的优缺点

• 优点：训练速度快
• 缺点：不易找到全局最优

Python伪代码

for epoch in range(epochs):
    shuffle(data)
    for example in data:
        grad = loss_fn(*args, **kwarga)
        params = params - learning_rate * grad 

小批量梯度下降算法(Mini-Batch Gradient Decent, MBGD)

对随机梯度下降和批梯度下降进行了折衷， 每次用 t(1<t<m) 个样本进行更新

J(w,b)=1k∑i=1kL(y(i)^,y(i))+λ2k∑∥w∥F2wj:=wj−α∂J(w,b)∂wjbj:=bj−α∂J(w,b)∂bj

MBGD的梯度下降图

Python伪代码

for epoch in range(epochs):
    shuffle(data)
    for batch in next_batch(data, batch_size):
        grad = loss_fn(*args, **kwargs)
        params = params - learning_rate * grad

梯度下降优化

优化的方式一般有两种：

• 优化方法的选择，比如大数据量下采用牛顿法/拟牛顿法进行优化

指数加权平均

是一种常用的序列数据处理方式

St={Y1 if t=1βSt−1+(1−β)Yt if t>1

Yt 为 t下的实际值， St 为 t 下加权平均后的值， β 为权重

动量梯度下降（Gradient Descent with Momentum）

是计算梯度的指数加权平均数，并利用该值来更新参数值

υdw=βυdw+(1−β)dwυdb=βυdb+(1−β)dbw:=w−αυdwb:=b−αυdb

SGD 在局部沟壑中很容易发生振荡，所以在这种情况下下降速度会很慢，而动量能在一定程度上抑制这种震荡，使得SGD的下降更平稳

如下图为不加Momentum和加了Momentum的区别

未加Momentum的SGD

加了Momentum的SGD

特点：当前后梯度方向一致时，Momentum梯度下降能够加速学习；前后梯度方向不一致时,Momentum梯度下降能够抑制震荡

均方根支(Root Mean Square Prop, RMSProp)

在梯度进行指数加权平均的基础上引入了平方和平方根

Sdw=βSdw+(1−β)dw2Sdb=βSdb+(1−β)db2w:=w−αdwSdw+ϵb:=b−αdwSdb+ϵ

ϵ 一般值很小，主要是用来提高数值稳定性，防止分母过小

特点： 当 dw 或 db 较大时，dw2 和 db2 也会较大，因此 Sdw Sdb 也是较大的，最终使得 dwSdw+ϵ dbSdb+ϵ 较小，这也减少了振荡

自适应矩估计(Adaptive Moment Estimation, Adam)

可以认为是 Momentum 和 RMSProp 的结合

υdw=β1υdw+(1−β1)dw,υdb=β1υdb+(1−β1)dbSdw=β2Sdw+(1−β2)dw2,Sdb=β2Sdb+(1−β2)db2υdwcorrect=υdw1−β1t,υdbcorrect=υdb1−β1tSdwcorrect=Sdw1−β2t,Sdbcorrect=Sdb1−β2tw:=w−αυdwcorrectSdwcorrect+ϵb:=b−αυdbcorrectSdbcorrect+ϵ

β1为第一阶矩，β2 为第二阶矩

各优化算法的比较

Reference

[1]李航《统计学习方法》

[2] https://wenku.baidu.com/view/d3dbe40903d8ce2f00662358.html

[3] https://wenku.baidu.com/view/23aca9eab8f67c1cfad6b84f.html

[4] https://zh.wikipedia.org/wiki/%E6%B5%B7%E6%A3%AE%E7%9F%A9%E9%98%B5

[5] http://binweber.top/2017/10/06/deep_learning_4/

[6] http://ruder.io/optimizing-gradient-descent/