机器猫爱学习

越努力，越幸运

首页 归档 标签 关于

梯度下降 Gredient decent

2020-03-11 14 min read # 梯度下降

梯度下降是一种最小化目标函数的迭代算法，通过在目标函数梯度相反方向上更新参数，误差就像是山，我们希望走到山下。下山最快的路应该是最陡峭的那个方向，因此我们也应该寻找能够使误差最小化的方向。我们可以通过计算梯度来找到这个方向。

梯度下降的数学

梯度是一个向量，一个函数在某点的梯度表示该函数在该点处沿着梯度的方向变化最快。

微分

微分思想是“散塔为沙”来源于极限，把某个物体分成无数份，每一份无线趋向于零。

y=f(x)dy=f′(x)dxy=f(x) dy=f'(x)dx

dy是y的微分或者是f(x)的微分

积分

积分的思想是“聚沙为塔”，分为定积分和不定积分。
几何意义是函数与x轴围城的面积，定积分可以用来计算面积、体积、概率。

偏导

导数就是函数的变化率。
偏导数的几何意义是曲面与x轴、y轴方向垂直切面的切线的斜率，物理意义就是试探。

梯度下降的数学意义：
如果有一个曲面 w=w(x,y,z)w=w(x,y,z)，设 ∇ w\nabla\ w 是一个综合了w所有偏导数的向量：

∇w=(∂w∂x,∂w∂y,∂w∂z)\nabla w = (\frac{\partial w}{\partial x}, \frac{\partial w}{\partial y}, \frac{\partial w}{\partial z})

∇w\nabla w 就是一个梯度向量，简称梯度

梯度下降的变体

梯度下降的变体有三钟，它们在计算目标函数的梯度时使用多少数据不同，根据数据量不同，我们在参数更新的准确性和执行更新所需的时间之间进行权衡。

批量梯度下降Batch Gradient Descent

批量梯度下降每一次更新需要计算整个数据集的梯度，因此会非常缓慢。无法在线更新。批梯度下降可以保证收敛到全局最小值，对于非凸面曲面，可以保证收敛到局部最小值。

Θ=Θ−η⋅∇ΘJ(Θ)\Theta=\Theta - \eta \cdot \nabla{_\Theta} J(\Theta) 

for i in range(nb_epochs):
        params_grad = evaluate_gradient(loss_function, data, params)
        params = params - learning_rate * params_grad

随机梯度下降Stochastic gradient descent

随机梯度下降对每个训练样本xix^{i} yiy^{i}执行参数更新

Θ=Θ−η⋅∇ΘJ(Θ;xi;yi)\Theta=\Theta - \eta \cdot \nabla{_\Theta} J(\Theta; x^{i}; y^{i}) 

for i in range(nb_epochs):
        np.random.shuffle(data)
        for example in data:
        params_grad = evaluate_gradient(loss_function, example, params)
        params = params - learning_rate * params_grad

下降速度更快，适合大型数据
每次选择1个样本，计算梯度。导致每次的梯度变化比较大，梯度的方差比较大。loss下降的不是很平滑，随机梯度下降永远都不会降到最低，可以逐步降低lr

小批量梯度下降 Mini-batch gradient descent

小批量梯度下降综合利用了batch和stochastic的优点。

Θ=Θ−η⋅∇ΘJ(Θ;x(i:i+n);y(i:i+n)\Theta=\Theta - \eta \cdot \nabla{_\Theta} J(\Theta; x^{(i:i+n)}; y^{(i:i+n}) 

for i in range(nb_epochs):
        np.random.shuffle(data)
        for batch in get_batches(data, batch_size=50):
        params_grad = evaluate_gradient(loss_function, batch, params)
        params = params - learning_rate * params_grad

减少了参数更新的方差，收敛更稳定，loss下降更平滑
能利用矩阵计算达到降低计算复杂度的问题

下面时三种梯度下降的对比：

梯度下降法的缺点

1、学习速率很难确定，需要交叉验证(CV)
2、梯度下降可能会陷入局部最小值或鞍点，所有参数的学习速率是一致的。特征稀疏程度不一样，需要不同的学习速率，对于较少出现的特征，需要增加学习速率，对于较多的特征，需要降低学习速率

梯度下降优化算法

冲量算法Momentum

动量是一种有助于在相关方向上加速SGD并抑制振荡的方法。这一部分可以参考吴恩达老师的视频，基本的想法就是计算梯度的指数加权平均数。

在纵轴上，你希望学习慢一点，因为你不想要这些摆动，但是在横轴上，你希望加快学习，你希望快速从左向右移，移向最小值，移向红点。

前进的步伐有两部分组成，一是学习速率乘以当前估计的梯度，二是带衰减的前一起步伐。收敛速度更快，loss的变化的方差更小。

vt=γvt−1+η∇ΘJ(Θ)v_t = \gamma v_{t-1} +\eta \nabla{_\Theta} J(\Theta)

Θ=Θ−vt\Theta = \Theta - v_t 

v_now = rho * v_prev + lr * d_now(params)
params = params - v_now
v_prev = v_now

Nesterov accelerated gradient

我们的动量将带我们到达绿色箭头的尖端，而不是评估当前位置（红色圆圈）处的梯度。因此，利用Nesterov accelerated gradient，我们可以在“前瞻”位置评估梯度。

vt=γvt−1+η∇ΘJ(Θ−γvt−1)v_t = \gamma v_{t-1} +\eta \nabla{_\Theta} J(\Theta - \gamma v_{t-1})

Θ=Θ−vt\Theta = \Theta - v_t 

v_now = rho * v_prev + lr * d_now(params - rho * v_prev)
params = params - v_now

Adagrad

上述方法解决的是，学习方向的问题，可以动态调整学习速率,下面介绍解决动态调整学习速率的问题

Adagrad是一种基于梯度的优化算法，采用“历史梯度平方和”来衡量不同参数的梯度稀疏性：它使学习速率适应参数，对与频繁出现的特征相关的参数执行较小的更新，而对不频繁特征的参数进行较大的更新。对于稀疏特征，能得到较大的学习更新；对于非稀疏特征，能得到较小的学习更新。因此适合处理稀疏数据。
gtg_t表示时间t处的梯度，gt,ig_{t,i}是目标函数对应参数Θi\Theta_{i}在时间t的偏导数

gt,i=∇ΘJ(Θt,i)g_{t,i} = \nabla{_\Theta} J(\Theta_{t,i})

对应每个参数在时间t的梯度更新

Θt+1,i=Θt,i−ηgt,i\Theta_{t+1,i} = \Theta_{t,i} - \eta g_{t,i}

ϵ是避免被零除的平滑项, G是对角矩阵，每个对角线上的元素是过去梯度的平方和

Θt+1=Θt−ηGt+ϵ⊙gt\Theta_{t+1} = \Theta_{t} - \frac{\eta}{\sqrt{G_t+\epsilon}}\odot g_t 

g_t_i = d(theta_t-1_i)
theta_t_i = theta_t-1_i - lr / (math.sqrt(G_t-1_ii) + epsilon) * g_t_i
G_t_ii = sigma_k=0^t g_k_i * g_k_i

Adagrad的主要好处之一是，它无需手动调整学习速度。Adagrad的主要弱点是分母中平方梯度的累加：由于每个加法项都是正数，所以累加和在训练期间不断增长。反过来，这会导致学习率下降，并最终变得无限小，这时算法将不再能够获取其他知识。以下算法旨在解决此缺陷。

Adadelta

Adadelta 是Adagrad的扩展，旨在降低其激进的，单调降低学习率。 Adadelta不会累计所有过去的平方梯度，而是将累计过去的梯度的窗口限制为某个固定大小w

RMSprop

RMSprop和Adadelta都是在同时解决方案的基础上独立开发的，这是因为需要解决Adagrad的学习率急剧下降的问题。RMSprop实际上与我们上面得出的Adadelta的第一个更新向量相同

RMSprop和Adadelta都是在同时解决Adagrad的学习率急剧下降的问题。

E[g2]t=0.9E[g2]t−1+0.1gt2E[g^2]_t = 0.9E[g^2]_{t-1}+0.1g^2_t

Θt+1=Θt−ηE[g2]t+ϵ⊙gt\Theta_{t+1} = \Theta_{t} - \frac{\eta}{\sqrt{E[g^2]_t+\epsilon}}\odot g_t 

#对G矩阵做指数加权平均，G_t = gamma * G_t-1 + (1 - gamma) * g_t * g_t

RMSprop也将学习率除以平方梯度的指数衰减平均值。建议γ设置为0.9，而学习率η的默认值是0.001

Adam

自适应矩估计Adam是为每个参数计算自适应学习率的另一种方法。除了存储过去平方梯度vtv_t的指数衰减平均值外像Adadelta和RMSprop一样，Adam还保留了过去梯度mtm_t的指数衰减平均值。，类似于动量。动量可以看作是一个顺着斜坡滑下的球，而Adam的行为就像是一个带有摩擦的沉重的球，因此，它更喜欢在误差表面上保持平坦的最小值。我们计算过去和过去平方梯度mtm_t的衰减平均值和vtv_t分别如下：

mt=β1mt−1+(1−β1)gtm_t = \beta_1m_{t-1}+ (1-\beta_1)g_t

vt=β2vt−1+(1−β2)gt2v_t = \beta_{2}v_{t-1} + (1-\beta_2)g^2_t

mtm_t vtv_t分别是梯度的第一阶矩（平均值）和第二阶矩（无中心方差）的估计值，由于mt和vt被初始化为0的向量，Adam的作者观察到它们偏向零，尤其是在初始时间步长，尤其是在衰减率较小时（即β1和β2接近1）。他们通过计算偏差校正的第一和第二矩估计值来抵消这些偏差：Adam公式：

数学上，“矩”是一组点组成的模型的特定的数量测度。
在力学和统计学中都有用到“矩”。

如果这些点代表“质量”，那么：
零阶矩表示所有点的 质量；
一阶矩表示 质心；
二阶矩表示 转动惯量。

如果这些点代表“概率密度”，那么：
零阶矩表示这些点的 总概率（也就是1）；
一阶矩表示 期望；
二阶（中心）矩表示 方差；
三阶（中心）矩表示 偏斜度；
四阶（中心）矩表示 峰度；

这个数学上的概念和物理上的“矩”的概念关系密切。

mt^=mt1−β1t\hat{m_t} = \frac{m_t}{1-\beta^t_1}

vt^=vt1−β2t\hat{v_t} = \frac{v_t}{1-\beta^t_2}

Θt+1=Θt−ηvt^+ϵmt^\Theta_{t+1} = \Theta_{t} - \frac{\eta}{\sqrt{\hat{v_t}}+\epsilon}\hat{m_t} 

#将冲量法和自适应学习速率法结合
#方向g_t = beta1 * g_t-1 + (1 - beta1) * d_now(theta)
#学习速率衰减银子G_t = beta2 * G_t-1 + (1 - beta2) * d_now(theta) * d_now(theta)
#g_t = g_t / (1 - beta1 ** t) 偏差修正，原因：因为如果beta取值较大的情况下，g和G会取趋向于0的值，除以1-beta**t是为了使得g_t是梯度的无偏估计，对G同理
#G_t = G_t / (1 - beta2 ** t)
#theta_t = theta_t-1 - lr / (math.sqrt(G_t-1_ii) + epsilon) * g_t
#推荐值：lr=0.002 beta1 = 0.9 beta2=0.999, eps=1e-8

AdaMax

该方法是基于Adam方法的一个变种方法，对梯度平方的处理由指数衰退平均改为指数衰退求最大值。

vt=β2pvt−1+(1−β2p)∣gt∣pv_t = \beta^p_{2}v_{t-1} + (1-\beta^p_2)\left| g_t \right|^p

vt=β2∞vt−1+(1−β2∞)∣gt∣∞=max(β2⋅vt−1,∣gt∣)v_t = \beta^\infty_{2}v_{t-1} + (1-\beta^\infty_2)\left| g_t \right|^\infty = max(\beta_2 \cdot v_{t-1}, \left| g_t \right|)

Θt+1=Θt−ηutmt^\Theta_{t+1} = \Theta_{t} - \frac{\eta}{u_t}\hat{m_t} 

#将学习速率衰减的2次方换成p次方，p越大，数值会越不稳定,why?
#p->无穷大时，数值稳定
#G_t = beta2 ** p * G_t-1 + (1 - beta2 ** p) * d_now(theta) ** p
#p->无穷大时,上式等于下式
#G_t = max(beta2 * G_t-1, math.abs(d_now(theta)))
#theta_t = theta_t-1 - lr / G_t * g_t
#推荐值：lr=0.002 beta1 = 0.9 beta2=0.999

Nadam

Adam可以看成是RMSprop和Momentum的组合：RMSprop贡献了过去平方梯度vtv_t的指数衰减平均值，而Momentum是过去梯度mtm_t的指数衰减平均值。

Nadam可以看成是Nesterov accelerated gradient的Adam，它结合了Adam和NAG。

AMSGrad

AMSGrad使用过去平方梯度vtv_t的最大值而不是指数平均值来更新参数

mt=β1mt−1+(1−β1)gtm_t = \beta_1m_{t-1}+ (1-\beta_1)g_t

vt=β2vt−1+(1−β2)gt2v_t = \beta_{2}v_{t-1} + (1-\beta_2)g^2_t

vt^=max(v^t−1,vt)\hat{v_t} = max(\hat{v}_{t-1}, v_t)

Θt+1=Θt−ηvt^+ϵmt^\Theta_{t+1} = \Theta_{t} - \frac{\eta}{\sqrt{\hat{v_t}}+\epsilon}\hat{m_t}

在小型数据集和CIFAR-10上，与Adam相比，性能有所提高。但是，其他实验显示的性能与Adam相似或更差。

Visualization of algrorithm

如何选择

总而言之，RMSprop是Adagrad的扩展，用于处理其学习率急剧下降的问题。它与Adadelta相同，除了Adadelta在numinator更新规则中使用参数更新的RMS。最后，Adam为RMSprop添加了偏差校正和动量。就此而言，RMSprop，Adadelta和Adam是非常相似的算法，在相似的情况下效果很好。，随着梯度变得稀疏，它的偏差校正有助于Adam在优化结束时略胜于RMSprop。就目前而言，Adam能是最好的整体选择。

参考链接：
https://blog.csdn.net/libing_zeng/java/article/details/74905378
http://www.redcedartech.com/pdfs/Select_Optimization_Method.pdf

Powered by Gridea RSS