优化理论之非线性方法-梯度法与牛顿法

Nov 4, 2019 · 优化理论 ·

分享到:

梯度下降法(gradient descent)与牛顿法(newton’s method)求解最小值

梯度下降法与牛顿法是求解最小值/优化问题的两种经典算法。本文的目标是介绍两种算法的推导思路与流程，并且从初学者的角度就一些容易混淆的话题如：梯度下降法(gradient descent)与最速下降法(steepest descent)的联系与区别、牛顿求根迭代方法(Newton–Raphson method) 与牛顿法求解最小值算法的联系(来自 Andrew Ng 机器学习课程第四讲)进行说明。本文的内容将对高斯牛顿法(Gauss–Newton algorithm) ,Levenberg-Marquardt算法(LM算法)等非线性最小二乘问题解法起到引出作用。

梯度下降法

已知多元函数\(f(x_1,x_2,\dots,x_n)\)在定义域上可微，如果将\(f(\mathbf{x})\)在\(\mathbf{x}\)处一阶泰勒展开(tayler expansion),可得到：(说明：为了编辑方便下文中统一以\(x={\begin{bmatrix} x_1,x_2,\dots,x_n \end{bmatrix}}^T\)代替\(\mathbf{x}\) )。 \[f(x+\epsilon) = f(x)+\epsilon ^T\nabla_x f + O(||\epsilon||)\approx f(x)+\epsilon ^T\nabla_x f\] 其中\(\nabla_x f={\begin{bmatrix} \frac{\partial f}{\partial x_1},\dots,\frac{\partial f}{\partial x_n} \end{bmatrix}}^T\)为\(f\)在\(x\)处的梯度向量。

这个式子我们可以解读为当\(x\)增加\(\epsilon\)时，\(f(x)\)增加\(\epsilon ^T\nabla_x f\)，即\(\epsilon\)与梯度\(\nabla_x f\)的內积。如果我们限定\(\epsilon\)的模长为定值，其方向怎样才能获得\(f(x+\epsilon)\)的最小值呢？答案当然是与\(\nabla_x f\)方向相反的时候，此时\(\epsilon ^T\nabla_x f\)获得最小值。

我们也可以利用直觉上较好理解的爬山的例子来解释梯度下降法。假设你位于山上某一点坐标为\(\mathbf{\theta}(\theta_1,\theta_2)\)，那么在此处(注意，是在这一点)下山最快的方向当然是沿着此处的梯度方向。

steepest_descent_1.png

所以说，将整个故事串起来，梯度下降法的思路可以总结如下：欲求多元函数\(f(x)\)的最小值，可以采用如下步骤：

给定初始值\(x_0\)。按照如下方式“下山”：\(x_{i+1} = x_i-\eta\nabla_{x_i} f\)。其中\(\eta>0\)，在机器学习领域，\(\eta\)也被称之为学习率(learning rate)。直到\(x\)满足收敛条件为止。如\(\|f(x_{i+1}) – f(x_i)\|<\epsilon\)或\(||\nabla_{x_i}f||\approx 0\)。

学习率的重要性：

学习率作为控制下降步长的参数，影响函数下降的速度。学习率是我们根据经验确定的一个参数，因此在机器学习领域中这样的参数也被成为超参数(hyperparameter)。学习率的选取不能过大或者过小，如下图，不同的学习率导致函数不同的收敛速度，甚至可能导致函数不收敛。

different_learning_rate.png

梯度下降法的优势

时间复杂度低，在每一个迭代中，只需要计算梯度，不需要对二阶导数矩阵（即海森矩阵(Hessian Matrix)）进行计算。
空间复杂度低，因为梯度向量为一个\(n\times 1\)的向量，比起Hessian Matrix来，占用存储空间小n倍。在实际应用中，\(\mathbf{x}\)的维度可能非常高。

梯度下降法的局限

对于部分求解函数，梯度下降法可能会出现下降非常缓慢的情形。其收敛速度也较其他方法低（其他文献分析其收敛速度为线性，本文不作推导）。如下图，梯度下降法的路径出现了z字型。

Banana-SteepDesc.gif

究其原因，我认为，某一点的梯度只能作为这一点的一个极小的领域处的最快下降方向，一旦梯度变化较快，梯度下降法会出现因为学习率不合适而出现”zigzag”现象。而且，如果我们将梯度下降法与下文的牛顿法做对比，你会发现，一直沿着梯度方向下降的速度不一定是最快的。如下图：

Newton_optimization_vs_grad_descent

最速下降法(steepest decent) 与梯度下降法(gradient descent)的联系

总结一下就是梯度下降法是最速下降法的一种特例。在最速下降法中，对于某一范数下\(\epsilon\)的取值根据以下原则：

\[\bigtriangleup \epsilon_{nsd}=argmin_v(\nabla f(x)^T\epsilon\mid \|\epsilon\|=1)\]

当我们指定的范数为欧几里得范数时，最速下降法给出的下降方向就是梯度的负方向，即梯度下降法给出的方向。

在wikipedia中说明，梯度下降法也被称为最速下降法(Gradient descent is also known as steepest descent )。

牛顿法

如同根据一阶泰勒展开推导出梯度下降法一样，根据二阶泰勒展开可以推导出牛顿优化法(newton’s method in optimization)。将\(f(\mathbf{x})\)在\(\mathbf{x}\)处一阶泰勒展开(tayler expansion),可得到： \[f(x+\epsilon) = f(x)+\epsilon ^T\nabla_x f + \frac{1}{2}\epsilon ^TH\epsilon +O(||\epsilon||^2)\\ \approx f(x)+\epsilon ^T\nabla_x f + \frac{1}{2}\epsilon ^TH\epsilon\]

如果我们将\(x\)看做固定的已知量，将\(f\)看做关于\(\epsilon\)的函数，那么欲求\(f(\epsilon | x)\)的最小值，必要条件(注意：不是充要条件)是\(\frac{\partial f}{\partial \epsilon}=0\)其中 \[H = \begin{bmatrix}\frac{\partial^2f}{\partial x_1 \partial x_1} & \cdots & \frac{\partial^2f}{\partial x_1 \partial x_n} \\ \vdots & \ddots & \vdots \\ \frac{\partial^2f}{\partial x_n \partial x_1} & \cdots & \frac{\partial^2f}{\partial x_n \partial x_n}\end{bmatrix}\] 称之为\(f\)的\(Hessian\)矩阵。因为二阶连续混合编导数具备性质 \[\frac{\partial^2f}{\partial x_i \partial x_j} = \frac{\partial^2f}{\partial x_j \partial x_i}\] 因此\(Hessian\)矩阵为对称矩阵。根据矩阵求导法则，可以得到 \[\frac{\partial f}{\partial \epsilon}={\nabla_x f}^T+\epsilon^TH=0\\ \epsilon = -H^{-1}{\nabla_x f}\]

可见，牛顿法的思路是将函数f在x处展开为多元二次函数，再通过求解二次函数最小值的方法得到本次迭代的下降方向\(\epsilon\)。那么问题来了，多元二次函数在梯度为0的地方一定存在最小值么？直觉告诉我们是不一定的。以一元二次函数\(g(x)=ax^2+bx+c\)为例，我们知道当\(a>0\)时，\(g(x)\)可以取得最小值，否则\(g(x)\)不存在最小值。

shape-of-the-graph.png

推广到多元的情况，可以得出二次项矩阵必须是正定(positive definite)的，对应上式即\(Hessian\)为正定矩阵时，函数\(f(\epsilon | x)\)的最小值才存在。

因此，牛顿法首先需要计算\(Hessian\)矩阵并且判断其正定性，当\(Hessian\)矩阵正定，此时其所有特征值均>0,当然\(Hessian\)矩阵也是可逆的，最小值存在。

需要指出的是，当多元函数 f 本身就是二次函数并且存在最小值时，牛顿法可以一步解出最小值。

牛顿法的优点

因为目标函数在接近极小值点附近接近二次函数，因此在极小值点附近，牛顿法的收敛速度较梯度下降法快的多。其他文献分析其收敛速度为2次收敛，本文不给出推导。下图是牛顿法应用在Rosenbrock函数上的效果：

Rosenbrock_newton.png

牛顿法的缺点

\(Hessian\)矩阵的计算难度非常的大。因此在高维度应用案例中，通常不会计算\(Hessian\)矩阵。因此牛顿法也产生了很多变种，主要的思想就是采用其他矩阵近似\(Hessian\)矩阵，降低计算复杂度。
牛顿法当\(Hessian\)矩阵为正定矩阵时，最小值才存在。牛顿法经常会因为\(Hessian\)矩阵不正定而发散(diverage)。因此牛顿法并不是非常的稳定。

牛顿法求根公式与牛顿优化法之间的联系

在说道牛顿优化方法的时候，上过《计算方法》这门课的同学经常会说，牛顿法不是用来求根的么？实际上，牛顿优化法还真可以用牛顿求根法推导得出。我看到的材料是 Andrew Ng在《机器学习课程》中给出的一种推导。在牛顿求根公式中，\(f(x)=0\)的解由迭代式 \[x_{i+1}=x_{i}-\frac{f(x_i)}{f\prime(x_i)}\] 给出。在牛顿优化法中，我们欲求得梯度\(g(x)=f'(x)=0\)对应的\(x\)。

因此\(x\)可以根据求根公式 \[x_{i+1}=x_{i}-\frac{f\prime(x_i)}{f\prime\prime(x_i)}\] 求出。推广到多元函数上，\({1}/{f\prime\prime(x_i)}\)演变为\(H^{-1}\)，\(f\prime(x_i)\)演变为\(\nabla_x f(x_i)\)因此 \[x_{i+1}=x_{i}-H^{-1}{\nabla_x f(x_i)}\] 与根据二阶泰勒展开并求\(f(\epsilon | x)\)的最小值得到的结论一致。