梯度下降法

导数与梯度

驻点（疑似极值点）：梯度为 0 的点

梯度为 0 的点 <==·≠≠> 极值点，梯度为0只是函数取极值的必要条件而不是充分条件。

极大值 or 极小值？ 通过二阶导数/Hessian矩阵判定。

• 如果Hessian矩阵正定，函数有极小值

• 如果Hessian矩阵负定，函数有极大值

• 如果Hessian矩阵不定，则需要进一步讨论

推导过程

如何确保每一步都是往山下走的

一元函数的泰勒展开公式为：

\[f ( x + \Delta x ) = f ( x ) + f ^ { \prime } ( x ) \Delta x + \frac { 1 } { 2 } f ^ { \prime } ( x ) ( \Delta x ) ^ { 2 } + \ldots + \frac { 1 } { n ! } f ^ { ( n ) } ( x ) ( \Delta x ) ^ { n } \ldots\]

如果 x 的变化很小，并且变化值与导数值反号，则函数值下降。

推广到多元函数，多元函数 f(x) 在 x 点处的泰勒展开为：

\[f ( \mathrm { x } + \Delta \mathrm { x } ) = f ( \mathrm { x } ) + ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } + o ( \Delta \mathrm { x } )\]

忽略二次及更高的项，$( \nabla f ( x ) ) ^ { T } \Delta x \cong f ^ { \prime } \left( x _ { 0 } \right) \Delta x$。

\[\therefore f ( \mathrm { x } + \Delta \mathrm { x } ) - f ( \mathrm { x } ) = ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } + o ( \Delta \mathrm { x } )\]

$if \quad \Delta x \rightarrow 0$ ，则在 x 的某一邻域内，可以忽略二次及以上的项。

\[\Rightarrow f ( \mathrm { x } + \Delta \mathrm { x } ) - f ( \mathrm { x } ) \approx ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x }\] \[if \quad ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } < 0 \Rightarrow f ( \mathrm { x } + \Delta \mathrm { x } ) < f ( \mathrm { x } ) 即函数值递减，这就是下山的正确方向。\] \[\because ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } = \| \nabla f ( \mathrm { x } ) \| \| \Delta \mathrm { x } \| \cos \theta\] \[\therefore \; if \quad \cos \theta \leq 0 \Rightarrow ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } \leq 0\]

即选择合适的增量 $\Delta x$，就能保证函数值下降，要达到这一目的，只要保证梯度和$\Delta x$ 的夹角的余弦值小于等于 0 就可以了。

由于有 $\cos \theta \geq - 1$，只有当 $\theta = \pi$ 时 $cos\theta$ 有极小值 -1，此时梯度和 $\Delta x$ 反向，即夹角为180度。

因此当向量 $\Delta x$ 的模大小一定时，当 $\Delta \mathrm { x } = - \alpha \nabla f ( \mathrm { x } )$ 即在梯度相反的方向函数值下降的最快。

此时有 $\cos \theta = - 1$ 函数的下降值为

\[( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } = - \| \mathrm { V } f ( \mathrm { x } ) \| \Delta \mathrm { x } \| = - \alpha \| \nabla f ( \mathrm { x } ) \| ^ { 2 }\]

只要梯度不为0，往梯度的反方向走函数值一定是下降的。

直接用可能会有问题，因为$ x + \Delta x$ 可能会超出 x 的邻域范围之外，此时是不能忽略泰勒展开中的二次及以上的项的，因此步伐不能太大。

一般设 $\Delta \mathrm { x } = - \alpha \nabla f ( \mathrm { x } )$ 其中 $\alpha$ 为一个接近于0的正数，称为步长，由人工设定，用于保证 $x+ \Delta x$ 在 x 的邻域内，从而可以忽略泰勒展开中二次及更高的项，则有：

\[( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } \Delta \mathrm { x } = - \alpha ( \nabla f ( \mathrm { x } ) ) ^ { \mathrm { T } } ( \nabla f ( \mathrm { x } ) ) \leq 0\]

从初始点 $x_{0}$ 开始，使用如下迭代公式：

\[\mathbf { x } _ { k + 1 } = \mathbf { x } _ { k } - \alpha \nabla f \left( \mathbf { x } _ { k } \right)\]

只要没有到达梯度为0的点，则函数值会沿着序列 $x_{k}$ 递减，最终会收敛到梯度为0的点，这就是梯度下降法。迭代终止的条件是函数的梯度值为0（实际实现时是接近于0），此时认为已经达到极值点。注意我们找到的是梯度为0的点，这不一定就是极值点，后面会说明。梯度下降法只需要计算函数在某些点处的梯度，实现简单，计算量小。

实现细节问题

初始值的设定

一般的，对于不带约束条件的优化问题，我们可以将初始值设置为0，或者设置为随机数，对于神经网络的训练，一般设置为随机数，这对算法的收敛至关重要。

学习率的设定

学习率设置为多少，也是实现时需要考虑的问题。最简单的，我们可以将学习率设置为一个很小的正数，如0.001。另外，可以采用更复杂的策略，在迭代的过程中动态的调整学习率的值。比如前1万次迭代为0.001，接下来1万次迭代时设置为0.0001。

面临的问题

梯度下降法可能会遇到一些问题，典型的是局部极小值和鞍点问题。但对于凸优化问题，不会遇到上面的局部极小值与鞍点问题，即梯度下降法一定能找到全局最优解。

局部极小值

有些函数可能有多个局部极小值点

鞍点

鞍点是指梯度为 0，Hessian矩阵既不是正定也不是负定，即不定的点。如函数 $x^{2} - y^{2}$ 在（0, 0）处梯度为 0，但并不是极值点。

变种

方式：利用之前迭代时的梯度信息来构造每次的更新值。

最直接的改进是为迭代公式加上动量项，动量项累积了之前的权重更新值，加上此项之后的参数更新公式为：

\[\mathrm { x } _ { t + 1 } = \mathrm { x } _ { t } + \mathrm { V } _ { t + 1 }\]

其中 $V_{t+1}$ 是动量项，它取代了之前的梯度项。动量项的计算公式为：

\[\mathbf { V } _ { t + 1 } = - \alpha \nabla f \left( \mathbf { x } _ { t } \right) + \mu \mathbf { v } _ { t }\]

动量项累积了之前的梯度信息，类似于保持行走时的惯性，以避免来回震荡，加快收敛速度。

AdaGrad算法

AdaGrad 根据前几轮迭代时的历史梯度值来调整学习率，参数更新公式为：

\[\left( \mathrm { x } _ { t + 1 } \right) _ { i } = \left( \mathrm { x } _ { t } \right) _ { i } - \alpha \frac { \left( \mathrm { g } _ { t } \right) _ { i } } { \sqrt { \sum _ { j = 1 } ^ { t } \left( \left( \mathrm { g } _ { j } \right) _ { i } \right) ^ { 2 } + \varepsilon } }\]

其中 $\alpha$ 是学习因子，$g_{t}$ 是第 t 次迭代时的参数梯度向量，$\varepsilon $ 是一个很小的正数，为了避免除 0 操作，下标 i 表示向量的分量。

与标准梯度下降法唯一不同的是多了分母中的这一项，它累积了到本次迭代为止梯度的历史值信息用于生成梯度下降的系数值。

AdaDelta算法

在每次迭代时也利用梯度值构造参数的更新值。

假设要优化的参数为x，梯度下降法第t次迭代时计算出来的参数梯度值为 $g_{t}$。算法首先初始化如下两个向量为 0 向量：

\[\begin{aligned} \mathrm { E } \left[ \mathrm { g } ^ { 2 } \right] _ { 0 } & = 0 \\ \mathrm { E } \left[ \Delta \mathrm { x } ^ { 2 } \right] _ { 0 } & = 0 \end{aligned}\]

其中 $E \left[ g ^ { 2 } \right]$ 是梯度平方（对每个分量分别平分）的累计值，更新公式为：

\[\mathrm { E } \left[ \mathrm { g } ^ { 2 } \right] _ { t } = \rho \mathrm { E } \left[ \mathrm { g } ^ { 2 } \right] _ { t - 1 } + ( 1 - \rho ) \mathrm { g } _ { t } ^ { 2 }\]

在这里 $g^{2}$ 是向量每个元素分别计算平方，后面所有的计算公式都是对向量的每个分量进行。接下来计算如下 RMS 量：

\[\operatorname { RMS } [ \mathrm { g } ] = \sqrt { \mathrm { E } \left[ \mathrm { g } ^ { 2 } \right] _ { t } + \varepsilon }\]

这也是一个向量，计算时分别对向量的每个分量进行。然后计算参数的更新值：

\[\Delta \mathrm { x } _ { t } = - \frac { \operatorname { RMS } [ \Delta \mathrm { x } ] _ { - 1 } } { \mathrm { RMS } [ \mathrm { g } ] } \mathrm { g } _ { t }\]

$\operatorname { RMS } [ \Delta \mathrm { x } ] _ { \mathrm { t } - 1 }$ 的计算公式和这个类似。这个更新值同样通过梯度来构造，只不过学习率是通过梯度的历史值确定的。更新公式为：

\[\mathrm { E } \left[ \Delta \mathrm { x } ^ { 2 } \right] _ { t } = \rho \mathrm { E } \left[ \Delta \mathrm { x } ^ { 2 } \right] _ { t - 1 } + ( 1 - \beta ) \Delta \mathrm { x } _ { t } ^ { 2 }\]

参数更新的迭代公式为：

\[\mathrm { x } _ { t + 1 } = \mathrm { x } _ { t } + \Delta \mathrm { x } _ { t }\]

和带动量项的梯度下降法不同的是这里用历史梯度值来构造学习率，包括了梯度的平方值。

Adam算法

由梯度项构造了两个向量 m 和 v，它们的初始值为 0，更新公式为：

\[\begin{array} { c } { \left( \mathrm { m } _ { t } \right) _ { i } = \beta _ { 1 } \left( \mathrm { m } _ { t - 1 } \right) _ { i } + \left( 1 - \beta _ { 1 } \right) \left( \mathrm { g } _ { t } \right) _ { i } } \\ { \left( \mathrm { v } _ { t } \right) _ { i } = \beta _ { 2 } \left( \mathrm { v } _ { t - 1 } \right) _ { i } + \left( 1 - \beta _ { 2 } \right) \left( \mathrm { g } _ { t } \right) _ { i } ^ { 2 } } \end{array}\]

其中 $\beta _ { 1 }, \beta _ { 2 }$ 是人工指定的参数，i 为向量的分量下标。依靠这两个值构造参数的更新值，参数的更新公式为：

\[\left( \mathrm { x } _ { t + 1 } \right) _ { i } = \left( \mathrm { x } _ { t } \right) _ { i } - \alpha \frac { \sqrt { 1 - \left( \beta _ { 2 } \right) _ { i } ^ { \prime } } } { 1 - \left( \beta _ { 1 } \right) _ { i } ^ { \prime } } \frac { \left( \mathrm { m } _ { t } \right) _ { i } } { \sqrt { \left( \mathrm { v } _ { t } \right) _ { i } } + \varepsilon }\]

在这里，用 m 代替梯度，用 v 来构造学习率。

NAG算法

一种凸优化方法, 和标准梯度下降法的权重更新公式类似，NAG算法构造一个向量v，初始值为0。v的更新公式为：

\[\mathrm { v } _ { t + 1 } = \mu \mathrm { v } _ { t } - \alpha \nabla L \left( \mathrm { x } _ { t } + \mu v _ { t } \right)\]

参数的更新公式为：

\[\mathrm { X } _ { t + 1 } = \mathrm { X } _ { t } + \mathrm { V } _ { t + 1 }\]

与带动量项的 SGD 相比 NAG 只是计算梯度时用的参数值不同，NAG 计算误差梯度时考虑了动量项，使用的是 $x _ { t } + \mu v _ { t }$，其它都是一样的。

RMSProp算法

由梯度值构造一个向量 MS，初始化为 0，更新公式为：

\[\operatorname { MS } \left( \left( \mathrm { x } _ { t } \right) _ { i } \right) = \delta \mathrm { MS } \left( \left( \mathrm { x } _ { t - 1 } \right) _ { i } \right) + ( 1 - \delta ) \left( \mathrm { g } _ { t } \right) _ { i } ^ { 2 }\]

参数更新公式为：

\[\left( \mathrm { x } _ { t + 1 } \right) _ { i } = \left( \mathrm { x } _ { t } \right) _ { i } - \alpha \frac { \left( \mathrm { g } _ { t } \right) _ { i } } { \sqrt { \mathrm { MS } \left( \left( \mathrm { x } _ { t } \right) _ { i } \right) } }\]

其中 $\delta$ 是人工设定的参数。这种方法通过梯度的历史信息来生成参数更新值的权重系数。

随机梯度下降法

对于有些机器学习问题，我们的目标函数是对样本的损失函数。假设训练样本集有 N 个样本，训练时优化的目标是这个数据集上的平均损失函数：

\[L ( \mathrm { w } ) = \frac { 1 } { N } \sum _ { i = 1 } ^ { N } L \left( \mathrm { w } , \mathrm { x } _ { i } , \mathrm { y } _ { i } \right)\]

其中 $L(w,x_{i},y_{i})$ 是对单个训练样本 $(x_{i},y_{i})$ 的损失函数，w是需要学习的参数。如果训练时每次都用所有样本计算梯度并更新，成本太高，作为改进可以在每次迭代时选取一批样本，将损失函数定义在这些样本上。

批量随机梯度下降法在每次迭代中使用上面目标函数的随机逼近值，即只使用 $M\ll N$ 个样本来近似计算损失函数。在每次迭代时要优化的目标函数变为：

\[L ( \mathrm { w } ) \approx \frac { 1 } { M } \sum _ { i = 1 } ^ { M } L \left( \mathrm { w } , \mathrm { x } _ { i } , \mathrm { y } _ { i } \right)\]

已经证明，随机梯度下降法在数学期望的意义下收敛，即随机采样产生的梯度的期望值是真实的梯度。因为每次迭代时的目标函数实际上是不一样的，因此随机梯度下降法并不能保证每次迭代时函数值一定下降。