CV总复习–深度学习机器学习基础篇（一）

优化算法

深度学习优化学习方法（一阶、二阶）

一阶方法：随机梯度下降（SGD）、动量（Momentum）、牛顿动量法（Nesterov动量）、AdaGrad（自适应梯度）、RMSProp（均方差传播）、Adam、Nadam。

二阶方法：牛顿法、拟牛顿法、共轭梯度法（CG）、BFGS、L-BFGS。

自适应优化算法有哪些？（Adagrad（累积梯度平方）、RMSProp（累积梯度平方的滑动平均）、Adam（带动量的RMSProp，即同时使用梯度的一、二阶矩））。

**梯度下降陷入局部最优有什么解决办法？**可以用BGD、SGD、MBGD、momentum，RMSprop，Adam等方法来避免陷入局部最优。

1.梯度下降法原理

梯度下降法又称最速下降法，是求解无约束最优化问题的一种最常用的方法，在对损失函数最小化时经常使用。梯度下降法是一种迭代算法。选取适当的初值x(0)，不断迭代，更新x的值，进行目标函数的极小化，直到收敛。由于负梯度方向时使函数值下降最快的方向，在迭代的每一步，以负梯度方向更新x的值，从而达到减少函数值的目的。

我们首先确定损失函数：
J ( Θ ) = 1 2 m ∑ j = 1 m [ h Θ ( x i ) − y i ] 2 J(\Theta)=\frac{1}{2 m} \sum_{j=1}^{m}\left[h_{\Theta}\left(x^{i}\right)-y^{i}\right]^{2} J(Θ)=2m1​j=1∑m​[hΘ​(xi)−yi]2
其中，J(θ)是损失函数，m代表每次取多少样本进行训练，如果采用SGD进行训练，那每次随机取一组样本，m=1；如果是批处理，则m等于每次抽取作为训练样本的数量。θ是参数，对应（1式）的θ1和θ2。求出了θ1和θ2，h(x)的表达式就出来了：

h ( Θ ) = ∑ Θ j x j = Θ 1 x 1 + Θ 2 x 2 h(\Theta)=\sum \Theta_{j} x_{j}=\Theta_{1} x_{1}+\Theta_{2} x_{2} h(Θ)=∑Θj​xj​=Θ1​x1​+Θ2​x2​
我们的目标是让损失函数J(θ)的值最小，根据梯度下降法，首先要用J(θ)对θ求偏导：

σ J ( Θ ) σ Θ j = 2 1 2 m ∑ i = 1 m [ h Θ ( x i ) − y i ] x j i = 1 m ∑ i = 1 m [ h Θ ( x i ) − y i ] x j i \frac{\sigma J(\Theta)}{\sigma \Theta_{j}}=2 \frac{1}{2 m} \sum_{i=1}^{m}\left[h_{\Theta}\left(x^{i}\right)-y^{i}\right] x_{j}^{i}=\frac{1}{m} \sum_{i=1}^{m}\left[h_{\Theta}\left(x^{i}\right)-y^{i}\right] x_{j}^{i} σΘj​σJ(Θ)​=22m1​i=1∑m​[hΘ​(xi)−yi]xji​=m1​i=1∑m​[hΘ​(xi)−yi]xji​
由于是要最小化损失函数，所以参数θ按其负梯度方向来更新：

Θ ′ = Θ j − σ J ( Θ ) σ Θ j = Θ j − α 1 m ∑ m i = 1 ( y i − h Θ ( x i ) ) x j i \Theta^{\prime}=\Theta_{j}-\frac{\sigma J(\Theta)}{\sigma \Theta_{j}}=\Theta_{j}-\alpha \frac{1}{m} \sum_{m}^{i=1}\left(y^{i}-h_{\Theta}\left(x^{i}\right)\right) x_{j}^{i} Θ′=Θj​−σΘj​σJ(Θ)​=Θj​−αm1​m∑i=1​(yi−hΘ​(xi))xji​
①批量梯度下降（BGD）

批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新

θ j : = θ j + α ∑ i = 1 m ( y i − θ i T x i ) x j \theta_{j}:=\theta_{j}+\alpha \sum_{i=1}^{m}\left(y_{i}-\theta_{i}^{T} x_{i}\right) x_{j} θj​:=θj​+αi=1∑m​(yi​−θiT​xi​)xj​
写成伪代码如下：

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

优点：（1）一次迭代是对所有样本进行计算，此时利用矩阵进行操作，实现了并行。（2）由全数据集确定的方向能够更好地代表样本总体，从而更准确地朝向极值所在的方向。当目标函数为凸函数时，BGD一定能够得到全局最优。

缺点：（1）当样本数目 m 很大时，每迭代一步都需要对所有样本计算，训练过程会很慢。（2）不能投入新数据实时更新模型。

②随机梯度下降（SGD）

随机梯度下降法求梯度时选取一个样本j来求梯度。

θ j : = w j + α ( y i − θ i T x i ) x j \theta_{j}:=w_{j}+\alpha\left(y_{i}-\theta_{i}^{T} x_{i}\right) x_{j} θj​:=wj​+α(yi​−θiT​xi​)xj​
写成伪代码如下：

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）由于不是在全部训练数据上的损失函数，而是在每轮迭代中，随机优化某一条训练数据上的损失函数，这样每一轮参数的更新速度大大加快。

缺点：（1）准确度下降。由于即使在目标函数为强凸函数的情况下，SGD仍旧无法做到线性收敛。（2）可能会收敛到局部最优，由于单个样本并不能代表全体样本的趋势。（3）不易于并行实现。 SGD 因为更新比较频繁，会造成 cost function 有严重的震荡。

③小批量梯度下降算法（mini-batch GD）

小批量梯度下降法是是对于m个样本，我们采用x个样子来迭代，1<x<m。一般可以取x=10，当然根据样本的数据，可以调整这个x的值。

θ = θ − η ⋅ ∇ θ J ( θ ; x ( i : i + n ) ; y ( i : i + n ) ) \theta=\theta-\eta \cdot \nabla_{\theta} J\left(\theta ; x^{(i: i+n)} ; y^{(i: i+n)}\right) θ=θ−η⋅∇θ​J(θ;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

优点：（1）通过矩阵运算，每次在一个batch上优化神经网络参数并不会比单个数据慢太多。（2）每次使用一个batch可以大大减小收敛所需要的迭代次数，同时可以使收敛到的结果更加接近梯度下降的效果。(比如上例中的30W，设置batch_size=100时，需要迭代3000次，远小于SGD的30W次)（3）可实现并行化。

缺点(解释1)：

1.不过 Mini-batch gradient descent 不能保证很好的收敛性，learning rate 如果选择的太小，收敛速度会很慢，如果太大，loss function 就会在极小值处不停地震荡甚至偏离。（有一种措施是先设定大一点的学习率，当两次迭代之间的变化低于某个阈值后，就减小 learning rate，不过这个阈值的设定需要提前写好，这样的话就不能够适应数据集的特点。）对于非凸函数，还要避免陷于局部极小值处，或者鞍点处，因为鞍点周围的error是一样的，所有维度的梯度都接近于0，SGD 很容易被困在这里。（会在鞍点或者局部最小点震荡跳动，因为在此点处，如果是训练集全集带入即BGD，则优化会停止不动，如果是mini-batch或者SGD，每次找到的梯度都是不同的，就会发生震荡，来回跳动。）

2.SGD对所有参数更新时应用同样的 learning rate，如果我们的数据是稀疏的，我们更希望对出现频率低的特征进行大一点的更新。LR会随着更新的次数逐渐变小。

缺点(解释2)：：

（1）batch_size的不当选择可能会带来一些问题。

batcha_size的选择带来的影响：在合理地范围内，增大batch_size的好处：a. 内存利用率提高了，大矩阵乘法的并行化效率提高。b. 跑完一次 epoch（全数据集）所需的迭代次数减少，对于相同数据量的处理速度进一步加快。c. 在一定范围内，一般来说 Batch_Size 越大，其确定的下降方向越准，引起训练震荡越小。

（2）盲目增大batch_size的坏处：

a. 内存利用率提高了，但是内存容量可能撑不住了。b. 跑完一次 epoch（全数据集）所需的迭代次数减少，要想达到相同的精度，其所花费的时间大大增加了，从而对参数的修正也就显得更加缓慢。c. Batch_Size 增大到一定程度，其确定的下降方向已经基本不再变化。

2.梯度下降算法改进

①动量梯度下降法（Momentum）

Momentum 通过加入 γ*vt−1 ，可以加速 SGD， 并且抑制震荡。momentum即动量，它模拟的是物体运动时的惯性，即更新的时候在一定程度上保留之前更新的方向，同时利用当前batch的梯度微调最终的更新方向。这样一来，可以在一定程度上增加稳定性，从而学习地更快，并且还有一定摆脱局部最优的能力。动量法做的很简单，相信之前的梯度。如果梯度方向不变，就越发更新的快，反之减弱当前梯度。r一般为0.9。

v t = γ v t − 1 + η ∇ θ J ( θ ) θ = θ − v t \begin{aligned} v_{t} &=\gamma v_{t-1}+\eta \nabla_{\theta} J(\theta) \\ \theta &=\theta-v_{t} \end{aligned} vt​θ​=γvt−1​+η∇θ​J(θ)=θ−vt​​
缺点：这种情况相当于小球从山上滚下来时是在盲目地沿着坡滚，如果它能具备一些先知，例如快要上坡时，就知道需要减速了的话，适应性会更好。

②Nesterov accelerated gradient法（NAG）

用 θ−γv_t−1 来近似当做参数下一步会变成的值，则在计算梯度时，不是在当前位置，而是未来的位置上。仍然是动量法，只是它要求这个下降更加智能。这个算法就可以对低频的参数做较大的更新，对高频的做较小的更新，也因此，对于稀疏的数据它的表现很好，很好地提高了 SGD 的鲁棒性。

v t = γ v t − 1 + η ∇ θ J ( θ − γ v t − 1 ) θ = θ − v t \begin{aligned} v_{t} &=\gamma v_{t-1}+\eta \nabla_{\theta} J\left(\theta-\gamma v_{t-1}\right) \\ \theta &=\theta-v_{t} \end{aligned} vt​θ​=γvt−1​+η∇θ​J(θ−γvt−1​)=θ−vt​​
esterov 的好处就是，当梯度方向快要改变的时候，它提前获得了该信息，从而减弱了这个过程，再次减少了无用的迭代。超参数设定值: 一般 γ 仍取值 0.9 左右。

③Adagrad

这个算法就可以对低频的参数做较大的更新，对高频的做较小的更新，也因此，对于稀疏的数据它的表现很好，很好地提高了 SGD 的鲁棒性，例如识别 Youtube 视频里面的猫，训练 GloVe word embeddings，因为它们都是需要在低频的特征上有更大的更新。

梯度更新规则:

θ t + 1 , i = θ t , i − η G t , i i + ϵ ⋅ g t , i \theta_{t+1, i}=\theta_{t, i}-\frac{\eta}{\sqrt{G_{t, i i}+\epsilon}} \cdot g_{t, i} θt+1,i​=θt,i​−Gt,ii​+ϵ ​η​⋅gt,i​
其中g为：t时刻参数θ_i的梯度

g t , i = ∇ θ J ( θ i ) g_{t, i}=\nabla_{\theta} J\left(\theta_{i}\right) gt,i​=∇θ​J(θi​)
如果是普通的 SGD， 那么 θ_i 在每一时刻的梯度更新公式为：

θ t + 1 , i = θ t , i − η ⋅ g t , i \theta_{t+1, i}=\theta_{t, i}-\eta \cdot g_{t, i} θt+1,i​=θt,i​−η⋅gt,i​
但这里的learning rate η也随t和i而变：

θ t + 1 , i = θ t , i − η G t , i i + ϵ ⋅ g t , i \theta_{t+1, i}=\theta_{t, i}-\frac{\eta}{\sqrt{G_{t, i i}+\epsilon}} \cdot g_{t, i} θt+1,i​=θt,i​−Gt,ii​+ϵ ​η​⋅gt,i​
其中 Gt 是个对角矩阵， (i,i) 元素就是 t 时刻参数 θi 的梯度平方和。

Adagrad 的优点是减少了学习率的手动调节。超参数设定值：一般η选取0.01。

缺点：它的缺点是分母会不断积累，这样学习率就会收缩并最终会变得非常小。

④Adadelta

这个算法是对 Adagrad 的改进，和Adagrad相比，就是分母的 G 换成了过去的梯度平方的衰减平均值，指数衰减平均值

Δ θ t = − η E [ g 2 ] t + ϵ g t \Delta \theta_{t}=-\frac{\eta}{\sqrt{E\left[g^{2}\right]_{t}+\epsilon}} g_{t} Δθt​=−E[g2]t​+ϵ ​η​gt​
这个分母相当于梯度的均方根 root mean squared (RMS)，在数据统计分析中，将所有值平方求和，求其均值，再开平方，就得到均方根值 ，所以可以用 RMS 简写：

Δ θ t = − η R M S [ g ] t g t \Delta \theta_{t}=-\frac{\eta}{R M S[g]_{t}} g_{t} Δθt​=−RMS[g]t​η​gt​
其中 E 的计算公式如下，t 时刻的依赖于前一时刻的平均和当前的梯度：

E [ g 2 ] t = γ E [ g 2 ] t − 1 + ( 1 − γ ) g t 2 E\left[g^{2}\right]_{t}=\gamma E\left[g^{2}\right]_{t-1}+(1-\gamma) g_{t}^{2} E[g2]t​=γE[g2]t−1​+(1−γ)gt2​
梯度更新规则:此外，还将学习率η换成了RMS[Δθ]，这样的话，我们甚至都不需要提前设定学习率了：

Δ θ t = − R M S [ Δ θ ] t − 1 R M S [ g ] t g t θ t + 1 = θ t + Δ θ t \begin{array}{l} \Delta \theta_{t}=-\frac{R M S[\Delta \theta]_{t-1}}{R M S[g]_{t}} g_{t} \\ \theta_{t+1}=\theta_{t}+\Delta \theta_{t} \end{array} Δθt​=−RMS[g]t​RMS[Δθ]t−1​​gt​θt+1​=θt​+Δθt​​
超参数设定值: γ 一般设定为 0.9

⑤RMSprop

RMSprop 是 Geoff Hinton 提出的一种自适应学习率方法。RMSprop 和 Adadelta 都是为了解决 Adagrad 学习率急剧下降问题的。

梯度更新规则:RMSprop 与 Adadelta 的第一种形式相同：（使用的是指数加权平均，旨在消除梯度下降中的摆动，与Momentum的效果一样，某一维度的导数比较大，则指数加权平均就大，某一维度的导数比较小，则其指数加权平均就小，这样就保证了各维度导数都在一个量级，进而减少了摆动，允许使用一个更大的学习率η）。
E [ g 2 ] t = 0.9 E [ g 2 ] t − 1 + 0.1 g t 2 θ t + 1 = θ t − η E [ g 2 ] t + ϵ g t \begin{array}{l} E\left[g^{2}\right]_{t}=0.9 E\left[g^{2}\right]_{t-1}+0.1 g_{t}^{2} \\ \theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{E\left[g^{2}\right]_{t}+\epsilon}} g_{t} \end{array} E[g2]t​=0.9E[g2]t−1​+0.1gt2​θt+1​=θt​−E[g2]t​+ϵ ​η​gt​​
超参数设定值:Hinton 建议设定 γ 为 0.9, 学习率 η 为 0.001。

⑥Adam：Adaptive Moment Estimation

Adam 算法和传统的随机梯度下降不同。随机梯度下降保持单一的学习率（即 alpha）更新所有的权重，学习率在训练过程中并不会改变。而 Adam 通过计算梯度的一阶矩估计和二阶矩估计而为不同的参数设计独立的自适应性学习率。这个算法是另一种计算每个参数的自适应学习率的方法，相当于 RMSprop + Momentum。

除了像 Adadelta 和 RMSprop 一样存储了过去梯度的平方 vt 的指数衰减平均值 ，也像 momentum 一样保持了过去梯度 mt 的指数衰减平均值：

m t = β 1 m t − 1 + ( 1 − β 1 ) g t v t = β 2 v t − 1 + ( 1 − β 2 ) g t 2 \begin{array}{l} m_{t}=\beta_{1} m_{t-1}+\left(1-\beta_{1}\right) g_{t} \\ v_{t}=\beta_{2} v_{t-1}+\left(1-\beta_{2}\right) g_{t}^{2} \end{array} mt​=β1​mt−1​+(1−β1​)gt​vt​=β2​vt−1​+(1−β2​)gt2​​
如果mt和vt被初始化为0向量，那它们就会向0偏置，所以做了偏差校正，通过计算偏差校正后的mt和vt来抵消这些偏差：

m ^ t = m t 1 − β 1 t v ^ t = v t 1 − β 2 t \begin{array}{l} \hat{m}_{t}=\frac{m_{t}}{1-\beta_{1}^{t}} \\ \hat{v}_{t}=\frac{v_{t}}{1-\beta_{2}^{t}} \end{array} m^t​=1−β1t​mt​​v^t​=1−β2t​vt​​​
梯度更新规则:

θ t + 1 = θ t − η v ^ t + ϵ m ^ t \theta_{t+1}=\theta_{t}-\frac{\eta}{\sqrt{\hat{v}_{t}}+\epsilon} \hat{m}_{t} θt+1​=θt​−v^t​ ​+ϵη​m^t​
超参数设定值:建议 β1 ＝ 0.9，β2 ＝ 0.999，ϵ ＝ 10e−8。

实践表明，Adam 比其他适应性学习方法效果要好。

Adam 和 SGD 区别：Adam = Adaptive + Momentum，顾名思义Adam集成了SGD的一阶动量和RMSProp的二阶动量。

3.牛顿法

利用二阶导数，收敛速度快；但对目标函数有严格要求，必须有连续的一、二阶偏导数，计算量大。利用牛顿法求解目标函数的最小值其实是转化成求使目标函数的一阶导为0的参数值。这一转换的理论依据是，函数的极值点处的一阶导数为0.其迭代过程是在当前位置x0求该函数的切线，该切线和x轴的交点x1，作为新的x0,重复这个过程，直到交点和函数的零点重合。此时的参数值就是使得目标函数取得极值的参数值。

简述梯度下降法和牛顿法的优缺点？梯度下降法和牛顿法区别

1.牛顿法：是通过求解目标函数的一阶导数为0时的参数，进而求出目标函数最小值时的参数。①收敛速度很快。②海森矩阵的逆在迭代过程中不断减小，可以起到逐步减小步长的效果。③缺点：海森矩阵的逆计算复杂，代价比较大，因此有了拟牛顿法。

2.梯度下降法：是通过梯度方向和步长，直接求解目标函数的最小值时的参数。越接近最优值时，步长应该不断减小，否则会在最优值附近来回震荡。

参考链接

https://blog.csdn.net/google19890102/article/details/69942970

https://www.cnblogs.com/guoyaohua/p/8542554.html

https://blog.csdn.net/qq_39852676/article/details/86529995