梯度下降及其优化

目录

一、梯度与方向导数

二、梯度下降

三、Jacobian和Hessian函数

四、随机梯度下降

一、梯度与方向导数

偏导数刻画了函数沿坐标轴方向的变化率，但有些时候还不能满足实际需求。为了研究函数沿着任意方向的变化率，就需要用到方向导数。

设函数$z=f(x, y)$ 在点$P(x, y)$ 的某一个邻域$U(p)$ 内有定义。自点$P$ 引射线$l$ ，设$x$ 轴正向到射线$l$ 的转角为$\varphi$ ，并设$P^{\prime}(x+\Delta x, y+\Delta y)$ 为$l$ 上的另一点，且$P^{\prime}(P)$ 。这里规定，逆时针方向旋转生成的角是正角$P^{\prime}(P)$ ，顺时针方向生成的角为负角$(\varphi<0)$ 。此时，再考虑函数的增量$f(x+\Delta x, y+\Delta y)$ 与$P$ 和$P^{\prime}$ 两点间的距离$\rho=\sqrt{(\Delta x)^{2}+(\Delta y)^{2}}$ 的比值。当点$P^{\prime}$沿着射线$l$ 逐渐趋近于$P$ 时，如果这个比的极限存在，则称该极限为函数$f(x,y)$ 在点$P$ 沿着方向$l$ 的方向导数，记作

$\frac{\partial f}{\partial l}=\lim _{\rho \rightarrow+\infty} \frac{f(x+\Delta x, y+\Delta y)-f(x, y)}{\rho}$

从定义可知，当函数$f(x, y)$ 在点$P(x,y)$ 的偏导数$f_x$ 、$f_y$ 存在时，函数$f(x,y)$ 在点$P$ 沿着$x$ 轴正向$e_1=(0,1)$ ，$y$ 轴正向$e_2=(0,1)$ 的方向导数存在其值依次为$f_x$ 、$f_y$ ，函数$f(x,y)$ 点$P$ 沿着$x$ 轴负向$e_{1}^{\prime}=(-1,0)$ ，$y$ 轴负方向$e_{2}^{\prime}=(0,-1)$ 的方向导数也存在其值一次为$-f_x$ 、。

如果函数$z=f(x, y)$ 在点$P(x, y)$ 处可微，那么函数在该点沿任意一个方向$l$ 的方向导数都存在，且有

$\frac{\partial f}{\partial l}=\frac{\partial f}{\partial x} \cos \varphi+\frac{\partial f}{\partial y} \sin \varphi$

其中，$\varphi$ 为$x$ 轴到方向$l$ 的转角。

与方向导数有关的一个重要概念是梯度。对于二元函数而言，设函数$z=f(x,y)$ 在平面区域$D$ 内具有一阶连续偏导数，则对于没一点$P(x, y) \in D$ ，都可以给出一个向量$\frac{\partial f}{\partial x} i+\frac{\partial f}{\partial y} j$ 这个向量称为函数$z=f(x, y)$ 在点$P(x,y)$ 的梯度，记作$\text { gradf }(x, y)$ ，或符号$\nabla f(x, y)$ ，即$\operatorname{gradf}(x, y)=\frac{\partial f}{\partial x} i+\frac{\partial f}{\partial y} j$ 需要说明的是，$\nabla$ 是一个偏微分算子，它又称为哈密尔顿算子(Hamilton)算子，它定义为：

$\nabla=\left(\frac{\partial}{\partial x}, \frac{\partial}{\partial y}, \frac{\partial}{\partial z}\right)$ 或写成$\nabla=\frac{\partial}{\partial x} i+\frac{\partial}{\partial y} j+\frac{\partial}{\partial z} k$ 。

求一个函数$u=f(x, y, z)$ 的梯度，就可以看成是将哈密尔顿算子与函数$f$ 做乘法，即$\nabla f_{x}$ 。可见对一个函数求梯度，其实是从一个标量得到一个矢量的过程。

如果设$e=\cos \varphi i+\sin \varphi j$ 是与方向$l$ 同方向的单位向量，则由方向单数的计算公式可知

$\begin{aligned} & \frac{\partial f}{\partial l}=\frac{\partial f}{\partial x} \cos \varphi+\frac{\partial f}{\partial y} \sin \varphi \\ =&\left\{\frac{\partial f}{\partial x}, \frac{\partial f}{\partial y}\right\} \cdot\{\cos \varphi, \sin \varphi\} \\ =& \operatorname{gradf}(x, y) \cdot e \\ =&|\operatorname{gradf}(x, y) \cos (\operatorname{gradf}(x, y), e)| \end{aligned}$

这里$(\operatorname{gradf}(x, y), e)$ 表示向量$\operatorname{gradf}(x, y)$ 与$e$ 的夹角。由此可见，方向导数就是梯度在$l$ 上的投影，当方向$l$ 与梯度方向一致时，有$\cos (\operatorname{gradf}(x, y), e)=1$ 从而方向导数有最大值。所以，沿着梯度方向的方向导数达到最大值，也就是说梯度方向是函数$f(x, y)$ 在这点增长最快的方向。从梯度的定义中可知，梯度的模为

$|\operatorname{gradf}(x, y)|=\sqrt{\left(\frac{\partial f}{\partial x}\right)^{2}+\left(\frac{\partial f}{\partial y}\right)^{2}}$

总而言之，函数在某点的梯度是这样一个向量，它的方向与方向导数取得最大值的方向一致，而它的模为方向导数的最大值。

二、梯度下降

大多数深度学习算法都涉及某种形式的优化。优化指的是改变x以最小化或最大化某个函数f(x)的任务。通常以最小化f(x)指代大多数优化稳如。最大化可以经由最小化$-f(x)$ 来实现。

我们把要最小化或最大化的函数称为目标函数(object function)或准则(criterion)。当我们对其进行最小化是时，也把它称为代价函数(cost function)、损失函数(loss function)。

假设有一个函数$y=f(x)$ ，其中$x$ 和$y$ 都是实数。这个函数的导数(derivation)记为$f^{\prime}(x)$ 或$\frac{\partial y}{\partial x}$ 。导数$f^{\prime}(x)$ 代表$f(x)$ 在点$x$ 出的斜率。换句话说，它表明如何缩放输入的小变化才能在输出获得相应的变化： $f(x+\varepsilon) \approx f(x)+\varepsilon f^{\prime}(x)$ 。

因此导数对于最小化一个函数很有用，因为它告诉我们如何更改$x$ 来略微地改善$y$ 。例如，我们知道对于足够小的$\varepsilon$ 来说，$f\left(x-\operatorname{sig} n\left(f^{\prime}(x)\right)\right)$ 是比$f(x)$ 小的。因此我们可以将$x$往梯度的方向移动一小步来减少$f(x)$ 。这种技术称为梯度下降(gradient descent)。

当$f'(x)$ 小于0时，导数无法提供往哪个方向移动的信息。f'(x)=0的点称为临界点(critical point)或驻点(stationary point)。一个局部极小点(local minimum)意味着这个点的f(x)小于所有邻近点，因此不可能通过移动无穷小的步长来减小f(x)。一个局部极大值点(local maximum)意味着这个点的f(x)大于所有邻近点，因此不可能通过移动无穷小的步长来增大f(x)。有些临界点既不是最小点也不是最大点，这些点称为鞍点(saddle point)

使f(x)取得绝对的最小值(相对所有其他值)的点是全局最小点(global minimum)。函数可能只有一个全局最小点或存在多个全局最小点，还可能存在不是全局最优的局部极小值点。在深度学习的背景下，我们要优化的函数可能包含许多不是最优的局部极小点，或者还有很多处于非常平摊的区域内的鞍点。尤其当输入时多维的时候，所有这些都将使优化变得困难。因此，我们通常寻找使f非常小的点，但这在任何形式意义下并不一定最小。

我么经常使用最小化具有多维输入的函数：$f: R^{n} \rightarrow R$ 。为了使“最小化”的概念有意义，输出必须是一维的(标量)。

针对具有多维输入的函数，我们需要用到偏导数(partial derivation)的概念。偏导数$\frac{\partial f(x)}{\partial x_{i}}$ 衡量点$x$处只有$x_i$ 增加时$f(x)$如何变化。梯度(gradient)是相对一个向量求导的导数：f的梯度是包含所有偏导数的向量，记为$\nabla_{x} f(x)$ 。梯度的第$i$个元素时$f$关于$x_i$ 的导数。在多维情况下，临界点是梯度中所有元素都为零的点。

在$u$(单位向量)方向的方向导数(directional derivation)是函数$f$在$u$方向的斜率。换句话说，方向导数是函数$f(x+\alpha u)$ 关于$\alpha$ 的导数(在$\alpha = 0$ 时取得)。使用链式法则，我们可以看到当$\alpha = 0$ 时，$\frac{\partial f(x+\alpha u)}{\partial \alpha}=u^{T} \nabla x f(x)$ 。

为了最小化$f$，我们希望找到使$f$下降最快的方向。计算方向导数：$\min _{u, u^{u}=1}\|u\|_{2} \nabla_{x} f(x) \cos \theta$ 其中$\theta$ 是$u$与梯度的夹角。将$\|u\|_{2}=1$ 代入，并忽略与u无关的项，就能简化得到$\min _{u} \cos \theta$ 。这在u与梯度方向相反时取得最小值。换句话说，梯度向量指向上坡，负梯度方向指向下坡。我们在负梯度方向上移动可以减少f。这被称为最速梯度下降法(method of steepest descent)或梯度下降(gradient descent)。

最速下降建议新的点为$x^{\prime}=x-\varepsilon \nabla x f(x)$ 其中$\epsilon$ 为学习率(learning rate)，是一个确定步长大小的正标量。可以通过集中不同的方式选择$\varepsilon$ 。普遍的方式是选择一个小常数。有时我们通过计算，选择使用方向导数消失的步长。还有一种方法是根据几个$\varepsilon$ 计算$f(x-\varepsilon \nabla x f(x))$ ，并选择其中能产生最小目标函数值的$\varepsilon$ 。这种策略称为在线搜索。

最速梯度下降在梯度的每一个元素为零时收敛(或在实践中，很接近零时)。在某些情况下，我么也许能够避免运行该迭代算法，并通过解方程$\nabla_{x} f(x)=0$ 直接跳到临界点。

虽然最速梯度下降限制在连续空间中的优化问题，但不断向更好的情况移动一小步(即邻近最佳的小移动)的一般概念可以推广到离散空间。递增带有离散参数的目标函数称为爬山(hill climbing)算法。

三、Jacobian和Hessian函数

有时我们需要计算输入和输出都为向量的函数的所有偏导数。包含所有这样的偏导数的矩阵被称为Jacobian矩阵。具体来说，如果，我们有一个函数$f: R^{m} \rightarrow R^{n}$ ，$f$的$Jacobian$矩阵$J \in R^{n \times m}$ 定义为$J_{i, j}=\frac{\partial f(x)_{i}}{\partial x_{j}}$ 。

有时也会导数的导数感兴趣，即二阶导数(second derivative)。例如，有一个函数$f: R^{m} \rightarrow R$ ，$f$的一阶导数(关于$x_j$)关于$x_i$ 的导数记为$\frac{\partial^{2} f}{\partial x_{i} x_{j}}$ 。在一维情况下，可以将$\frac{\partial^{2} f}{\partial x_{i} x_{j}}$ 为$f^{\prime \prime}(x)$ 。二阶导数告诉我们，一阶导数将如何随着输入的变化而变化。它表示只基于梯度信息下降步骤是否会产生我们预期的那样大的改善，因此它是重要的。我们可以认为，二阶导数是对曲率的衡量。假设我们有一个二次函数(虽然很多实践中的函数都可以认为，二阶导数至少在局部可以很好地用二次近似）,如果这样的函数具有零二阶导数，那就没有曲率，也就是一条完全平坦的线，仅用梯度就可以预测它的值。我么使用沿负梯度方向大小为$\varepsilon$ 的下降步，当该梯度是1时，代价函数将下降$\varepsilon$ 。如果二阶导数是负的，函数曲线向下凹陷(向上凸出)，因此代价函数将下降的比$\varepsilon$ 多。如果二阶导数是正的，函数曲线是向上凹陷(向下凸出)，因此代价函数将下降得比$\varepsilon$ 少。

当我们的函数具有多维输入时，二阶导数也有很多。我们可以将这些导数合并成一个矩阵，称为Hessian矩阵。Hessian矩阵H(f)x定义为：

$H(f)(x)_{i, j}=\frac{\partial^{2}}{\partial x_{i} \partial x_{j}} f(x)$

Hessian矩阵等价于梯度的Jacobian矩阵。

微分算子在任何二阶偏导数连续的点处可交换，也就是它们的顺序可以互换：

$\frac{\partial^{2}}{\partial x_{i} \partial x_{j}} f(x)=\frac{\partial^{2}}{\partial x_{j} \partial x_{i}} f(x)$

这意味着$H_{i, j}=H_{j, i}$ ，因此Hessian矩阵在这些点上是对称的。在深度学习背景下，我们遇到的大多数函数的Hessian矩阵几乎处处都是对称的。因为Hessian矩阵是实对称的，我们可以将其分解成一组是特征值和一组特征向量的正交基。在特定方向d上的二阶导数可以写成$d^{T} H d$ 。当d时H的一个特征向量时，这个方向的二阶导数就是对应的特征值。对于其他方向d，方向的二阶导数是所有特征值的加权平均，权重在0到1之间，且与d夹角越小的特征向量的权重越大。最大特征值确定最大二阶导数，最小特征值确定最小二阶导数。

我们可以通过(方向)二阶导数预期一个梯度下降步骤能表现得多好。我们在当前点$x^{(0)}$ 处做函数$f(x)$的近似二阶泰勒级数：

$f(x) \approx f\left(x^{(0)}\right)+\left(x-x^{(0)}\right)^{T} g+\frac{1}{2}\left(x-x^{(0)}\right)^{T} H\left(x-x^{(0)}\right)$

其中$g$是梯度，$H$是$x^{(0)}$ 点的$Hessian$。如果我们使用学习率$\varepsilon$ ，那么新的点$x$ 将会是$x^{(0)}-\varepsilon g$ 。代入上述的近似，可得

$f\left(x^{(0)}\right) \approx f\left(x^{(0)}\right)-\varepsilon g^{T} g+\frac{1}{2} \varepsilon^{2} g^{T} H g$

其中有3项：函数的原始值，函数斜率导致的预期改善和函数曲率导致的校正。当最后一项太大时，梯度下降实际上是可能向上移动的。当$g^{T} H g$ 为正时，通过计算可得，使近似泰勒级数下降最多的最优步长为：

$\varepsilon^{*}=\frac{g^{T} g}{g^{T} H g}$

最坏的情况下，$g$与$H$最大特征值$\lambda_{\max }$ 对应的特征向量对齐，则最优步长是$\frac{1}{\lambda_{\max }}$ 。当我们要最小化的函数能用二次函数很好地近似的情况下，Hessian的特征值决定了学习率的量级。

二阶导数还可以用于确定一个临界点是都是局部极大点、局部极小点或鞍点。回想一下，在临界点处$f^{\prime}(x)=0$ 。而$f^{\prime \prime}(x)>0$ 意味着f'(x)会随着我们移向右边而增加，移向左边而减小，也就是$f^{\prime}(x-\varepsilon)<0$ 和$f^{\prime}(x+\varepsilon)<0$ 对足够小的$\varepsilon$ 成立。换句话说，当我们移向右边，斜率开始指向右边的上坡；当我们移向左边，斜率开始指向左边的上坡。因此我们得出结论，当$f^{\prime}(x)=0$ 且$f^{\prime \prime}(x)>0$ 时，$x$是一个局部极小值点。同理，当$f^{\prime}(x)=0$ 且$f^{\prime \prime}(x)<0$ 时，$x$是一个局部极大点。这就是所谓的二阶导数测试。不幸的是，当$f^{\prime \prime}(x)=0$ 时，测试是不确定的。在这种情况下，x可以是一个鞍点或平坦区域的一部分。

在多维情况下，我们需要检测函数的所有二阶导数。利用Hessian的特征分解，我们可以将二阶导数测试扩展到多维情况。在临界点处($\nabla_{x} f(x)=0$ )，我们通过检测Hessian的特征值来判断该临界点是一个局部极大值点、局部极小值点还是鞍点。当Hessian是正定的(所有特征值都是正的)，则该临界点是局部极小点。因为方向二阶导数在任意方向都是正的，参考单变量的二阶导数测试就能得出此结论。同样的，当Hessian时负定的(所有特征值都是负的)，这个点就是局部极大点。在多维情况下，实际上我么可以找到确定该点是否为鞍点的积极迹象(某些情况下)。如果Hessian的特征值中至少有一个是正的且至少一个是负的，那么x是f某个截面的局部极大点，却是另一个截面的局部极小点。最后，多维二阶导数测试可能像单变量版本那样是不确定的。当所有非零特征值是同号的且至少有一个特征值是0时，这个函数就是不确定的。这是因为单变量的二阶导数测试在零特征值对应的横截面上是不确定的。

多维情况下，单个点处每个方向上的二阶导数是不同的。Hessian的条件数衡量这些二阶导数的变化范围。当Hessian的条件数很差时，梯度下降法也会表现得很差，这是因为一个方向上的导数增加得很快，而在另一个方向上的增加得很慢。梯度下降不知道导数的这种变化，所以它不知道应该优化探索导数长期为负的方向。病态条件也导致很难选择适合的步长。步长必须足够小，以免冲过最小而向具有较强正曲率的方向上升。这通常意味着步长太小，以至于在其他较小曲率的方向上进展不明显。

可以使用Hessian矩阵的信息来指导搜索，以解决这个问题。其中最简单的方法是牛顿法(Newton's method)。牛顿法基于一个二阶泰勒展开来近似$x^{(0)}$ 附近的$f(x)$ ：

$f(x) \approx f\left(x^{(0)}\right)+\left(x-x^{(0)}\right)^{T} \nabla x f\left(x^{(0)}\right)+\frac{1}{2}\left(x-x^{(0)}\right)^{T} H(f)\left(x^{(0)}\right)\left(x-x^{(0)}\right)$

接着通过计算，可以得到这个函数的临界点：

$x^{*}=x^{(0)}-H(f)\left(x^{(0)}\right)^{-1} \nabla x f\left(x^{(0)}\right)$

如果$f$是一个正定二次函数，牛顿法只要应用一次就能直接跳到函数的最小点。如果f不是一个真正二次但能在局部近似为正定二次，牛顿法则需多次迭代。迭代地更新近似函数和跳到近似函数的最小点可以比梯度下降更快地到达临界点。这在接近局部极小值点时是一个特别有用的性质，但是在鞍点附近是有害的。仅使用梯度信息的优化算法称为一阶优化算法，如梯度下降。使用Hessian矩阵的优化算法称为二阶最优化算法。

四、随机梯度下降

梯度下降沿着整个数据集的梯度方向下降，这可以使用随机梯度下降很大程度地加速。

随机梯度下降(SGD)及其变种很可能是一般机器学习中应用最多的优化算法，特别是在深度学习中。按照数据分布生成抽取m个小批量(独立同分布的)样本，通过计算它们的梯度均值，我们可以得到梯度的无偏估计，下面是梯度随机梯度下降的伪代码：

Require: 学习率$\varepsilon_{k}$ Require: 初始化参数$\theta$ while 停止准则为满足 do 从训练集中采包含m个样本$\left\{x^{(1)}, \ldots, x^{(m)}\right\}$ 的小批量，其中$x^{(i)}$ 对应的目标函数为$y^{(i)}$ 计算梯度估计：

$\hat{g} \leftarrow+\frac{1}{m} \sum_{i} L\left(f\left(x^{(i)} ; \theta\right), y^{(i)}\right)$

应用更新：

$\theta \leftarrow \theta-\varepsilon \hat{g}$

end while

SGD算法中一个关键参数是学习率。之前，我们介绍的SGD使用固定的学习率。在实践中，有必要随着时间的推移逐渐降低学习率，因此我们将第k步迭代的学习率记作$\varepsilon_{k}$ 。

这是因为SGD中梯度估计引入了噪声源(m个训练样本的随机采样)并不会在极小点处消失。相比之下，当我们使用批量梯度下降达到极小点时，整个代价函数的真实梯度会变得很小，之后为0，因为批量梯度下降可以使用固定的学习率。保证SGD收敛的一个充分条件是$\sum_{k=1}^{\infty} \varepsilon_{k}=\infty$ 且$\sum_{k=1}^{\infty} \varepsilon_{k}^{2}<\infty$ 实践中，一般会线性衰减学习率直到第$\tau$ 次迭代：

$\varepsilon_{k}=(1-\alpha) \varepsilon_{0}+\alpha \varepsilon_{\tau}$

其中$\alpha=\frac{k}{\tau}$ 。在$\tau$ 不迭代之后，一般使$\varepsilon$ 保持常数。