Gradient Descent, Newton Method and Quasi-Newton Method

Posted on 2021-10-15 Edited on 2022-07-26 In Machine Learning

Gradient Descent

Gradient

Derivative

针对一元函数 \(y=f(x)\)，导数 \(f'(x_0)\) 表示了该函数在\(x_0\)处的函数斜率/增加速率。

Partial Derivative--偏导数，部分的导数

针对多元函数（此处考虑二元函数\(z=f(x,y)\)），导数 \(f'(x_0, y_0)\) 就有些模糊不清了，为此我们先简化到一元的情况：固定 \(y=y_0\)，\(z=f(x,y)\)，二元函数便降纬为\(z=f(x, y_0)\) ，此时我们可以定义在 \(x\) 方向上的偏导数 \(f'_x(x_0, y_0)\)，其表示该函数在\((x_0, y_0)\)点处沿 \(x\) 方向函数斜率/增加速率。类似的我们可以得到在 \(y\) 方向的偏导数。

Directional Derivative

由偏导数，我们已经可以得到 \(z\) 在 \(x=x_0\) 或 \(y=y_0\) 方向上的函数速率变化了。

现在基于这两个偏导数我们已经可以求出 \(x-y\) 平面任何方向的导数了：假设求 \(z\) 在 \(u=cos\theta \ \vec{i}+sin\theta \ \vec{j}\) 方向的导数（其中\(\theta\)表示该向量方向与\(x\)轴正方向的夹角，\(\vec{i}\)表示\(x\)轴正方向，\(\vec{j}\)表示\(y\)轴正方向） \[ D_uf(x,y)=\lim_{x \to \infty}\frac{f(x_0+tcos\theta,y_0+tsin\theta)}{t} \] 本质上方向导数是偏导数的一种推广，通过调整方向导数中 \(\theta\) 的值也能够简化为偏导数形式。

但是如果我们观察 \(u\) 本身，在 \(u\) 方向求导，其实相当于在 \(x\)，\(y\) 方向分别求偏导之后的线性组合： \[ D_uf(x,y)=cos\theta f'_x(x,y)+sin\theta f'_y(x,y) \] ### Gradient

由偏导数，我们已经可以得到 \(z\) 在 \((x_0, y_0)\) 点上在方向 \(u=cos\theta \ \vec{i}+sin\theta \ \vec{j}\) 方向上的函数变化速率了。

那么梯度是什么呢？梯度就是 \(z\) 在 \((x_0, y_0)\) 点上函数变化速度最快的方向，也就是方向向量最大的方向。

什么时候方向向量能取到最大呢？

\(D_uf(x,y)=\begin{bmatrix}f'_x(x,y)&f'_y(x,y)\end{bmatrix}\begin{bmatrix}cos\theta \\ sin\theta\end{bmatrix}=\pmb A*\pmb I\)，当 \((cos\theta, sin\theta) // (f'_x(x,y), f'_y(x,y))\) 时能够取到最大值，此时在 \((x_0,y_0)\) 的梯度 \(\pmb I=\begin{bmatrix}\frac{\partial f}{\partial x_0} \\ \frac{\partial f}{\partial y_0}\end{bmatrix}\)

梯度本质是矢量，在其方向上该点的方向向量最大。

Gradient Descent

Local optimum

由于机器学习应用梯度下降一般是为了最小化loss，因此实际上我们想要找到的是一个多元函数的最小值。从一个点出发，如果我们连续地在这个函数表面移动，一直往当前梯度最大的负方向（梯度本身定义指向函数值增加方向），这样我们最终一定会停留在函数谷底，也就是得到局部最优解。

Algorithm

首先我们先定义一下问题：

函数 \(f(x)\) 为在 \(R^n\) 上具有一阶连续偏导数的函数（note：这里 \(x\) 其实是 \(n\) 维向量 \(x=(x_1,x_2,\cdots,x_n)\)）

在无约束的情况下我们希望得到目标函数 \(f(x)\) 的极小值。

具体实现算法：

初始化 \(x\) 数值，记作 \(x^0\)

第k+1轮迭代：\(x^{k+1} = x^k+\lambda_kp_k\) 其中 \(p_k\) 为函数更新方向，取第k轮函数的负梯度（函数值下降最快的方向）：\(p_k=-\nabla f(x^k)\) 其中 \(\lambda_k\) 为函数更新的步长，由一维搜索得到：\(\lambda_k=\underset{\lambda}{\operatorname{argmin}}f(x^k+\lambda p_k)=\underset{\lambda}{\operatorname{argmin}}f(x^k-\lambda\nabla f(x^k))\) 具体实现：预先定义多个值进行计算，需要多次尝试。

当 \(\nabla f(x^k)<\epsilon\) 时（即梯度下降缓慢时）停止迭代注意此算法本身只能保证达到local optimum，不能保证全局最优，因此需要多次重新初始化尝试。

对于上述的梯度更新规则可以写成 \(x^{k+1} = x^k-\lambda_k\nabla f(x^k)\)，这里的 \(f(x)\) 只是一个一般性的简写，对于机器学习的问题而言一般是loss function，对于一般的线性回归问题，其业已写成 \(Loss=f(w)=(\sum _{j=0}^pw_jx_j-y)^2\)其中 \(w=(w_1, w_2, \cdots, w_p)\) 是我们希望更新的参数，它和输出/feature \(x=(x_1, x_2, \cdots, x_p)\) 一样是p纬度的向量，\(y\) 为该feature的实际label。（注意上述都是仅针对单个样本点的操作）

那么具体的梯度求解如下： \[ \begin{aligned} \frac{\partial Loss}{w_i} &=\frac{\partial(\sum _{j=0}^pw_jx_j-y)^2}{\partial w_i}\\ &=2(\sum _{j=0}^pw_jx_j-y)\frac{\partial(\sum _{j=0}^pw_jx_j-y)}{\partial w_i}\\ &=2(\sum _{j=0}^pw_jx_j-y)x_i \end{aligned} \] 假设我们用单个样本 \(x\) 计算梯度下降，求出的Loss导数为 \(\begin{bmatrix}\frac{\partial Loss(x)}{\partial w_1} \\ \vdots \\ \frac{\partial Loss(x)}{\partial w_p}\end{bmatrix}\)

BGD--Batch Gradient Descent

为了加速参数的更新，往往不会对每一个样本都计算梯度进行更新，事实上是一次性传入一个batch的数据，在更新参数时使用整个batch的数据结果进行更新。

假设我们用 \((x^1,\cdots,x^i,\dots,x^n)\) 一起计算梯度下降，求出的Loss导数为 \(\frac{1}{n}\begin{bmatrix}\sum_{i=1}^n\frac{\partial Loss(x^i)}{\partial w_1} \\ \vdots \\ \sum_{i=1}^n\frac{\partial Loss(x^i)}{\partial w_p}\end{bmatrix}\)。

SGD--Stochastic Gradient Descent

在数据量相当大的时候，BGD的开销也过于庞大了，为此数学家们考虑每次更新随机采样一个样本来控制梯度方向--这样做梯度的变化可能会出现较大的波动，但是数据量足够，数学上期望与BGD相同。SGD训练速度最快。

此外由于SGD本身受离群样本影响大，因此可能会难以收敛，实际应用中往往采用中折--即每次更新采用样本的部分数据进行训练--MBGD--Mini-batch Gradient Descent。

Newton Method

Solve Equation

牛顿法最早使用来求解方程实数根的。问题很简单：求方程 \(f(x)\) 的实数根。

我们将 \(f(x)\) 在 \(x_0\) 处Taylor一阶展开：\(f(x)=f(x_0)+f'(x_0)(x-x_0)\)

令 \(f(x)=0\)，则 \(f(x_0)+f'(x_0)(x-x_0)=0\)，\(x_1=x_0-f(x_0)/f'(x_0)\)

再将 \(f(x)\) 在 \(x_1\) 处Taylor一阶展开，迭代直到 \(||f(x)||<\epsilon\)。

简单解释一下：如果一个方程连续且有正值有负值，那么就一定有根，牛顿法可以从任意起点开始，每次迭代都是沿点的斜率方向向 \(x\) 轴做直线，相交得到下一个迭代点，由此理论上必能收敛。

Optimization Problem

回顾一下问题

我们所面对的是无约束的优化问题，希望得到 \(minf(x)\)，注意这里对于机器学习问题而言 \(x\) 很有可能是多维的，\(x\in R^{p*1}\)

梯度下降法里面我们需要假设 \(f(x)\) 一阶可导，在牛顿法中需要加强为二阶可导。

我们将 \(f(x)\) 在 \(x_k\) （此处假设已经迭代了 \(k\) 轮）处进行二阶Taylor展开： \[ f(x)=f(x^k)+g_k^T(x-x^k)+\frac{1}{2}(x-x^k)^TH(x^k)(x-x^k) \] 其中 \(g_k=\nabla f(x^k) \in R^{p*1}\) 是 \(f(x)\) 在 \(x^k\) 处的梯度；\(H(x^k)=\begin{bmatrix}\frac{\partial ^2f(x^k)}{\partial x_i \partial y_i}\end{bmatrix} \in R^{p*p}\) 为 \(f(x)\) 在 \(x^k\) 处的Hessian矩阵/二阶导数。

求解 \(f(x)\) 极值的必要条件是什么呢？\(f(x)\) 的一阶导数，也就是 \(g_k=\nabla f(x^k)=0\)；并且 \(H(x^k)\) 为正定矩阵时，得到最小值（可以理解为此点所有方向的二次导数均大于0 FYI）

那么这个问题就再次转化为了对 \(g_k=0\) 的牛顿法求根：

求 \(f(x)\) 在 \(x^0\) 处的梯度 \(g_0=\nabla f(x^0)\)，进行一阶Taylor展开：\(\nabla f(x)=\nabla f(x^0)+H(x^0)(x-x^0)=0\)

则 \(x^1=x^0-H^{-1}(x^0)\nabla f(x)\)，令 \(p(x^k)=-H^{-1}(x^k)\nabla f(x^k)\)，可以简化写为 \(x_1=x_0+p(x^0)\)

不断迭代直到 \(||\nabla f(x)||<\epsilon\)

其中迭代方程为 \(x^{k+1}=x^k-H^{-1}_kg_k=x^k+p_k\)

Comparation with Gradient Descent

梯度下降时一阶收敛，而牛顿法是二阶收敛，总的说牛顿法收敛速度更快，但是因为需要计算Hessian矩阵的逆，所以每次迭代速度更慢。

由于梯度下降法是求梯度，在wiki上解释为用一个平面拟合当前点（所在局部）；但是牛顿法相当于是对梯度进行一阶Taylor展开，所以可以理解为是用一个曲面拟合当前点。

或者从每次迭代的角度看：梯度下降只考虑了当前点哪个方向梯度最小（函数值下降最快），而牛顿法加入了Hessian矩阵，相当于还考虑了每次迭代后的梯度的变化（而不单单是函数值变化）。

但是要意识到牛顿法本质是对函数值进行了二阶Taylor展开，所以如果初始值距离极值点太远，那么Taylor近似效果就会很差，所以可以考虑先用梯度下降再用牛顿法。

对于梯度下降法往往在最后极值点处会出现反复震荡（这也是会什么梯度下降中往往会让步长逐渐缩短），对于牛顿法而言也是如此，因此也需要对步长进行衰减，称之为“阻尼牛顿法”：\(x^{k+1}=x^k-\lambda _kH^{-1}_kg_k=x^k+\lambda _kp_k\)

牛顿法是二次收敛（二阶导数收敛）：对于二次函数，Hessian函数退化为常数（二阶导数为常数），因此可以一步到达；对于非二次函数，如果有好的二次性或已经临近收敛，则效果很好。

Quasi-Newton Method

Basic Idea

牛顿法已经很好了，但是有一个很大的问题--由于input的feature可能会非常多维度，因此Hessian矩阵可能会很大，继而计算Hessian矩阵的逆就会很困难。

牛顿法的迭代公式（第 \(k\) 轮）为：\(\nabla f(x)=\nabla f(x^k)+H(x^k)(x-x^k)=0\)

令 \(x=x^{k+1}\)，带入原式： \(\nabla f(x)=\nabla f(x^k)+H(x^k)(x-x^k)\)，则得到 \(\nabla f(x^{k+1})=\nabla f(x^k)+H(x^k)(x^{k+1}-x^k)\)

变形本式得到：\(\nabla f(x^{k+1})-\nabla f(x^k)=H(x^k)(x^{k+1}-x^k)\)

令 \(y_k=\nabla f(x^{k+1})-\nabla f(x^k)\)，\(\delta_k=x^{k+1}-x^k\)，则上式又可以写作 \(y_k=H(x^k)\delta_k\)，亦可以写作 \(H^{-1}(x^k)y_k=\delta_k\)

此式即为拟牛顿条件（quasi-Newton condition），所有对Hessian矩阵近似的方法都应该满足次条件。

常用的近似方法有：DFP (Davidon-Fletcher-Powell) Algorithm，BFGS (Broyden-Fletcher-Goldfard-Shano) Algorithm，L-BFGS (Limited-memory BFGS) Algorithm

Q&A

既然牛顿法收敛会快很多，那么为什么深度学习依然使用梯度下降（一阶收敛）呢？

计算复杂度高--\(Hessian \in R^{n*n}\)，Hessian矩阵大小为参数的平方。
拟牛顿法对Hessian的近似由于神经网络的不确定性导致其近似方差不确定，会使优化算法本身不稳定
牛顿法要求目标函数为凸，Hessian才能保证正定。
牛顿法可以快速得到高精度的参数，但是深层网络对单个参数的精度并不敏感，甚至于不精确的参数对网络的泛化能力有帮助。