start

2017 10-03

start

优化主要有一阶优化（如，梯度下降）和二阶优化（如，牛顿法和拟牛顿法）。

二阶优化相当于用二阶函数去拟合目标函数，
一阶优化相当于用一阶函数去拟合目标函数，

因此一阶优化只看当下，二阶优化看得更远，效率更高。

一阶优化的优点是计算方便，缺点是只看当下，效率不够高，而且优化的时候，需要特别调节学习速率，这一点非常不容易，因此才有了momentum、adagrad、rmsprop、adam这些自动调节学习速率的算法。

二阶优化的优点是看得更远，方向更准，而且不要确定学习速率，缺点是：

1、求海森矩阵逆的时候，内存和计算的需求十分大，甚至有时候海森矩阵没有逆矩阵，拟牛顿法就是为了解决这些问题，比如l-bfgs降低了内存需求，不需要直接计算海森矩阵的逆；
2、优化的时候需要计算整个训练集，如果想在一个batch里面计算，几乎无法成功优化，这一点和梯度下降不一样，梯度下降只计算一个batch的梯度也可以优化。

梯度下降沿着整个训练集的梯度方向下降。可以使用随机梯度下降很大程度地加速，沿着随机挑选的小批量数据的梯度下降。

批量算法和小批量算法

梯度下降的框架主要分三种：
1，全量梯度下降。每次使用全部的样本来更新模型参数，优点是收敛方向准确，缺点是收敛速度慢，内存消耗大。
2，随机梯度下降。每次使用一个样本来更新模型参数，优点是学习速度快，缺点是收敛不稳定。
3，批量梯度下降。每次使用一个batchsize的样本来更新模型参数，平衡了全量梯度下降和随机梯度下降的方法

1、batch gradient descent（BGD 批量梯度下降）

所谓的梯度下降方法是无约束条件中最常用的方法。假设f(x)是具有一阶连续偏导的函数，现在的目标是要求取最小的f(x) : min f(x)
核心思想：负梯度方向是使函数值下降最快的方向，在迭代的每一步根据负梯度的方向更新x的值，从而求得最小的f(x)。因此我们的目标就转变为求取f(x)的梯度。
优点：

当f(x)是凸函数的时候，用梯度下降的方法取得的最小值是全局最优解

缺点：

在计算的时候，需要在每一步（xk处）计算梯度，它每更新一个参数都要遍历完整的训练集，不仅很慢，还会造成训练集太大无法加载到内存的问题，此外该方法还不支持在线更新模型。

所以，为了提高速度，减少计算量，提出了SGD随机梯度下降的方法，该方法每次随机选取一个样本进行梯度计算，大大降低了计算成本。

2、stochastic gradient descent（SGD随机梯度下降）

随机梯度下降算法和批量梯度下降的不同点在于其梯度是根据随机选取的训练集样本来决定的，其每次对theta的更新，都是针对单个样本数据，并没有遍历完整的参数。当样本数据很大时，可能到迭代完成，也只不过遍历了样本中的一小部分。
优点:

训练速度快,避免了批量梯度更新过程中的计算冗余问题，对于很大的数据集,也能够以较快的速度收敛。

缺点:

不能保证每次的优化方向不一定是全局最优的。（虽然BGD可以让参数达到全局最低点并且停止，而SGD可能会让参数达到局部最优，但是仍然会波动，甚至在训练过程中让参数会朝一个更好的更有潜力的方向更新。但是众多的实验表明，当我们逐渐减少学习速率时，SGD和BGD会达到一样的全局最优点。）
由于是抽取,因此不可避免的,得到的梯度肯定有误差.因此学习速率需要逐渐减小，否则模型无法收敛
因为误差，所以每一次迭代的梯度受抽样的影响比较大,也就是说梯度含有比较大的噪声,不能很好的反映真实梯度.并且SGD有较高的方差，其波动较大

考虑到每次只选择一个样本进行梯度更新存在较大的噪声，学者们开始尝试每次选择一小批样本进行梯度更新，在降低噪声的同时提高速度，因此就有了下面的MBGD小批量梯度下降法。

3、mini-batch gradient descent（MBGD小批量梯度下降）

为了综合上述两种方法，提出了小批量梯度下降。它：（1）降低在SGD中高方差的问题，能使得收敛更加稳定；（2）可以利用深度学习中最先进的库进行矩阵优化的操作，加速操作；（3）一般的小批量介于50～256，但是当适用很小的批量时，有时也统称为SGD。
核心思想：在每次迭代时考虑一小部分样本，比如考虑10个样本，同时计算在这10个样本点上的每个参数的偏导数，对于每个优化参数，将该参数在这10个样本点的偏导数求和。
但是，需要注意的是因为这里也存在样本选择的随机性，学习速率应该要逐渐减小，同时上述方法并不能保证好的收敛性。主要存在的挑战有：

选择适当的学习率可能很困难。太小的学习率会导致收敛性缓慢，而学习速度太大可能会妨碍收敛，并导致损失函数在最小点波动。
使用学习率计划：尝试在训练期间调整学习率。比如根据预先制定的规则缓慢的降低学习速率，或者当每次迭代之间的偏导差异已经低于某个阈值时，就降低学习速率。但是这里面的学习速率更新规则，以及阈值都是需要预先设定的，因此不适应于所有的数据集。
此外，使用梯度更新的方法会导致所有参数都用学习速率更新。但是当训练集数据是稀疏的，或者特征的频率是不同的，我们可能不希望它们更新到同样的程度，因此使用相同的学习速率会导致那些很少出现的特征有较大的变化。
在求取那些高度非凸的误差函数的最小值时，我们应该避免陷入局部最优解，实验表明，最困难的不是从局部最优而是鞍点，鞍点就是沿着某一个方向他是稳定的，沿着另一个方向不稳定，既不是最小点也不是最大点。这会使得该点在所有维度上梯度为0，让SGD难以逃脱。

使用小批量的原因
n个样本均值的标准差是，其中是样本值真实的标准差。分母表明使用更多的样本来估计梯度的方法的回报是低于线性的。
另一个促使从小数目样本中获得梯度的统计估计的动机是训练集的冗余。大量样本可能对梯度做出了非常相似的贡献。
可能是由于小批量在学习过程中加入了噪声，它们会有一些正则化效果。
其他原因
鲁棒性
不同的算法使用不同的方法从小批量中获取不同的信息。有些算法对采样误差比其他算法更敏感，这通常有两个原因。一个是它们使用了很难在少量样本上精确估计的信息，另一个是它们以放大采样误差的方式使用了信息。
基于梯度g gg的更新方法通常相对鲁棒，并能使用较小的批量获得成功，如100。使用Hessian矩阵H HH，计算如H − 1 g H^{-1}gH
−1
g更新的二阶方法通常需要更大的批量，如10000。

随机顺序

小批量是随机抽取的这点也很重要。从一组样本中计算出梯度期望的无偏估计要求这些样本是独立的。在数据集中的顺序有很大影响的情况下，有必要在抽取小批量样本前打乱样本顺序。
不以某种方式打乱样本顺序会极大地降低算法的性能。

异步并行

在计算小批量样本X XX上最小化J ( X ) J(X)J(X)的更新时，同时可以计算其他小于样本上的更新。

无重复样本，遵循真实泛化误差的梯度

很多小批量随机梯度下降方法的实现都会打乱数据顺序一次，然后多次遍历数据来更新参数。第一次遍历，每个小批量样本都用来计算真实泛化误差的无偏估计。第二次遍历，估计将会是有偏的，因为重新抽取了已经用过的样本，而不是从和原先样本相同的数据生成分布中获取新的无偏的样本。

在线学习中的SGD

在线学习中，样本永远不会重复，每次更新的样本是从分布中采样获得的无偏样本。

实际使用

在实际使用中，除非训练集特别大，通常还是多次遍历训练集，额外的遍历会由于减小训练误差而得到足够的好处，以抵消其带来的训练误差和测试误差差距的增加。

基本算法

随机梯度下降SGD—-Vanilla SGD

SGD及其变种是深度学习中应用最多的优化算法。按照数据生成分布抽取m个小批量（独立同分布）样本，通过计算它们的梯度均值，我们可以得到梯度无偏估计。
深度学习中的优化算法 - 图6

SGD算法中的一个关键参数是学习率。在实践中，有必要随着时间的推移逐渐降低学习率。
将第k步迭代的学习率记作。一般会线性衰减学习率直到第τ 次迭代：

其中。在τ次迭代之后，一般使保持常数。通常应设为大约的1%。
对于足够大的数据集，SGD可能会在处理整个训练集之前就收敛到最终测试集误差的某个固定容差范围内。
批量梯度下降在理论上比随机梯度下降有更好的收敛率。可以在学习过程中逐渐增大批量大大小，以此权衡批量梯度下降和随机梯度下降两者的优点。
SGD 的缺点在于收敛速度慢，可能在鞍点处震荡。并且，如何合理的选择学习率是 SGD 的一大难点。

带动量的SGD—Momentum

SGD 在遇到沟壑时容易陷入震荡。为此，可以为其引入动量 Momentum[3]，加速 SGD 在正确方向的下降并抑制震荡。
深度学习中的优化算法 - 图12 图 1(a): SGD
深度学习中的优化算法 - 图13
图 1(b): SGD with momentum
从图 1 中可以看出，引入动量有效的加速了梯度下降收敛过程。

指数加权平均数

偏差修正

深度学习中的优化算法 - 图16

另一种形式
深度学习中的优化算法 - 图17
在实践中，动量参数一般取值为0.5,0.9和0.99。和学习率一样，α \alphaα也会随着时间不断调整。一般初始值是一个较小的值，随后会慢慢变大。随着时间调整α \alphaα没有收缩ϵ \epsilonϵ重要。

Nesterov动量

Nesterov动量中，梯度计算在施加当前速度之后。因此，Nesterov动量可以解释为往标准动量方法中添加了一个校正因子。
深度学习中的优化算法 - 图18

标准的动量方法（由Nesterov在1983年提出）是在当前位置计算梯度，然后在累积的更新梯度方向上做一个大的跳跃。下面给出了一种更好地动量方法（由IIya Sutskever在2012年提出），其先在先前累积的梯度方向上做一个大的跳跃，再计算新的梯度并修正错误。
下面对两种方法做了比较，图中蓝色箭头是做两次标准动量方法得到的；而图中棕色箭头是改进动量方法先做的一次大跳跃得到的，红色箭头是修正，绿色箭头是进行一次改进动量方法得到的。可以看到，改进的比标准的要快很多。

深度学习中的优化算法 - 图19

自适应学习率算法

习率算法

AdaGrad

AdaGrad独立地适应所有模型参数的学习率，缩放每个参数反比于其所有梯度历史平方值总和的平方根。
深度学习中的优化算法 - 图20

在凸优化中，AdaGrad算法具有一些令人满意的理论性质。然而，经验上对于训练深度神经网络模型而言，从训练开始时积累梯度平方会导致有效学习率过早和过量减小。

AdaDelta

AdaGrad主要存在三个问题

其学习率是单调递减的，训练后期学习率非常小
其需要手工设置一个全局的初始学习率
更新θ \thetaθ时，左右两边的单位不同一

我们令每一个时刻的r rr随之时间按照ρ \rhoρ指数衰减，这样就相当于仅使用离当前时刻比较近的g gg信息，不会使得r rr增加过快，分母过大而导致参数更新减缓。在AdaDelta中，累积平方梯度定义为

在计算更新时，用梯度历史该变量平方值期望的平方根代替学习率深度学习中的优化算法 - 图22 ,则得到Adadelta更新规则：
深度学习中的优化算法 - 图23
由此看出，甚至不需要设定缺省学习率，因为更新规则已经不受它影响了

RMSProp

RMSProp算法修改AdaGrad以在非凸设定下效果更好，改变梯度累积为指数加权的移动平均。
AdaGrad旨在应用于凸问题时快速收敛。AdaGrad根据平方梯度的整个历史收缩学习率，可能使得学习率在达到这样的凸结构前就变得太小了。
RMSprop使用指数衰减平均来丢弃遥远过去的历史，使其在找到凸结构后快速收敛，就像一个初始化于该碗装结构的AdaGrad算法实例。
相比于AdaGrad，使用移动平均引入了一个新的超参数ρ \rhoρ，用来控制移动平均的长度范围。
深度学习中的优化算法 - 图24
深度学习中的优化算法 - 图25

Adam

派生自短语”adaptive moments”
Adam被看作结合RMSProp和具有一些重要区别的动量的变种。
首先，Adam中动量直接并入梯度一阶矩（指数加权）的估计。
其次，Adam包括偏置修正，修泽和那个从原点初始化的一阶矩（动量项）和（非中心的）二阶矩的估计。RMSProp也采用了（非中心的）二阶矩估计，然而缺失了修正因子。因此，RMSProp二阶矩估计可能在训练初期有很高的偏置。

Adam通常被认为对超参数的选择相当鲁棒，尽管学习率有时需要遵从建议的默认参数0.001。
深度学习中的优化算法 - 图26

二阶近似方法

牛顿法

深度学习中的优化算法 - 图28
深度学习中的优化算法 - 图29

共轭梯度

共轭梯度是一种通过迭代下降的共轭方向以有效避免Hessian矩阵求逆计算的方法。
在共轭梯段法中，我们寻求一个和先前线性搜索方向共轭的搜索方向，即它不会撤销该方向上的进展。在训练迭代t时，下一步的搜索方向d t
深度学习中的优化算法 - 图31 深度学习中的优化算法 - 图32

BFGS

L-BFGS

批标准化

批标准化是一种自适应重参数化的方法，试图解决训练非常深的模型的困难。批标准化主要解决的是训练极深网络时梯度消失的问题。
深度学习中的优化算法 - 图35
##BN起作用的原因

通过使得批量数据归一化具有0均值1方差的统计分布，避免数据处于激活函数的饱和区，具有较大的梯度，从而加速网络的训练过程。
减少了网络输入变化过大的问题，使得网络的输入稳定，减弱了与前层参数关系之间的作用，使得当前层独立于整个网络

BN具有轻微正则化的效果，可以和 dropout 一起使用
主要是归一化激活值前的隐藏单元来加速训练，正则化是副作用
##BN具有正则化效果的原因

每个批量的数据仅根据当前批量计算均值和标准差，然后缩放
这就为该批量的激活函数带来了一些噪音，类似于dropout向每一层的激活函数带来噪音
若使用了较大的batch_size如512，则减小了噪音，减少了正则化带来的效果

训练过程中的算法

由于BN在最后重参数化过程中会学习得到一个γ，所以神经网络中的bias可以省略掉。
##推断时算法
由于在推断的时，batch的大小不能确定，很有可能1次只有一个样本，不通过对当前批量的数据的归一化来加速训练。作者提出使用训练数据集上的全部数据来计算均值和方差。通常出与计算效率考虑，使用滑动平均的方法来计算

tensorflow实现

使用tf.layers.batch_normalization可以快速实现BN算法。注意使用该API时在优化器调用时要加入以下代码：

update_ops = tf.get_collection(tf.GraphKeys.UPDATE_OPS)
  with tf.control_dependencies(update_ops):
    train_op = optimizer.minimize(loss)

这里还有一个我看到知乎匿名用户的实现，感觉比较清晰

from tensorflow.python.training.moving_averages import assign_moving_average
def batch_norm(x, train, eps=1e-05, decay=0.9, affine=True, name=None):
    with tf.variable_scope(name, default_name='BatchNorm2d'):
        params_shape = tf.shape(x)[-1:]
        moving_mean = tf.get_variable('mean', params_shape,
                                      initializer=tf.zeros_initializer,
                                      trainable=False)
        moving_variance = tf.get_variable('variance', params_shape,
                                          initializer=tf.ones_initializer,
                                          trainable=False)
        def mean_var_with_update():
            mean, variance = tf.nn.moments(x, tf.shape(x)[:-1], name='moments')
            with tf.control_dependencies([assign_moving_average(moving_mean, mean, decay),
                                          assign_moving_average(moving_variance, variance, decay)]):
                return tf.identity(mean), tf.identity(variance)
        mean, variance = tf.cond(train, mean_var_with_update, lambda: (moving_mean, moving_variance))
        if affine:
            beta = tf.get_variable('beta', params_shape,
                                   initializer=tf.zeros_initializer)
            gamma = tf.get_variable('gamma', params_shape,
                                    initializer=tf.ones_initializer)
            x = tf.nn.batch_normalization(x, mean, variance, beta, gamma, eps)
        else:
            x = tf.nn.batch_normalization(x, mean, variance, None, None, eps)
        return x

优化策略和元算法

坐标下降

————————————————
版权声明：本文为CSDN博主「浅梦s」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/u012151283/article/details/78154917

可视化分析

深度学习中的优化算法 - 图38
图 3: SGD optimization on loss surface contours
深度学习中的优化算法 - 图39
图 4: SGD optimization on saddle point
图 3 和图 4 两张动图直观的展现了不同算法的性能。(Image credit: Alec Radford)
图 3 中，我们可以看到不同算法在损失面等高线图中的学习过程，它们均同同一点出发，但沿着不同路径达到最小值点。其中 Adagrad、Adadelta、RMSprop 从最开始就找到了正确的方向并快速收敛；SGD 找到了正确方向但收敛速度很慢；SGD-M 和 NAG 最初都偏离了航道，但也能最终纠正到正确方向，SGD-M 偏离的惯性比 NAG 更大。
图 4 展现了不同算法在鞍点处的表现。这里，SGD、SGD-M、NAG 都受到了鞍点的严重影响，尽管后两者最终还是逃离了鞍点；而 Adagrad、RMSprop、Adadelta 都很快找到了正确的方向。
关于两图的讨论，也可参考[2]和[8]。
可以看到，几种自适应算法在这些场景下都展现了更好的性能。

深度学习中的优化算法