[机器学习必知必会]牛顿法与拟牛顿法

前言

同梯度下降法一样，牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法，每一步需要求解目标函数的海赛矩阵的逆矩阵，计算比较复杂。拟牛顿法通过正定矩阵近似海赛矩阵的逆矩阵或海赛矩阵，简化了这一计算过程。

需要提前了解的知识

1.泰勒展开

当 $f(x)$ 在 $x=x_0$ 处具有 $n$ 阶连续导数，我们可以用 $x-x_0$ 的 $n$ 次多项式逼近函数

公式：
$f(x) = \frac{f(x_0)}{0!}+\frac{f'(x_0)}{1!}(x-x_0)+\frac{f''(x_0)}{2!}(x-x_0)^2+...+\frac{f^{(n)}(x_0)}{n!}(x-x_0)^n+R^n(x)$
其中 $R^n(x)$ 表示泰勒余项，它是 $(x-x_0)^n$ 的高阶无穷小。

2.海森矩阵

Hessian Matrix，是一个多元函数的二阶偏导数构成的方阵，描述了函数的局部曲率

以二元函数 $f(x_1,x_2)$ 为例，它在 $X^{(0)}(x_1^{(0)},x_2^{(0)})$ 点处的泰勒展开式为：
$$
f(x_1,x_2) =
f(x_1^{(0)},x_2{(0)})

\frac{\partial{f}}{\partial{x_1}}\Big|_{X^{(0)}} \triangle x_1
\frac{\partial{f}}{\partial{x_2}}\Big|_{X^{(0)}} \triangle x_2
\frac{1}{2} \bigg[
\frac{\partial ^{2{f}}{\partial{x_1}2}}\Big|_{X^{(0)}} \triangle x_1^2
\frac{\partial ^{2{f}}{\partial{x_1}\partial{x_2}}\Big|_{X}{(0)}} \triangle x_1 \triangle x_2
\frac{\partial ^{2{f}}{\partial{x_2}2}}\Big|_{X^{(0)}} \triangle x_2^2
\bigg]
...
$其中$\triangle x_1 = x_1 - x_1^{(0)}, \triangle x_2 = x_2 - x_2^{(0)}$ 改写成矩阵形式：$
f(X) = f(X^{(0)}) +
\bigg [
\frac{\partial f}{\partial x_1} + \frac{\partial f}{\partial x_2}
\bigg ] \bigg|{X^{(0)}}
\begin{pmatrix}
\triangle x_1
\
\triangle x_2
\end{pmatrix} +
\frac{1}{2} (\triangle x_1 , \triangle x_2)
\begin{pmatrix}
\frac{\partial ^2f}{\partial x_1^2} & \frac{\partial ^2f}{\partial x_1 \partial x_2}
\
\frac{\partial ^2f}{\partial x_2 \partial x_1} & \frac{\partial ^2f}{\partial x_2^2}
\end{pmatrix} \bigg |{X^{(0)}}
\begin{pmatrix}
\triangle x_1
\
\triangle x_2
\end{pmatrix}
...
$即：$
f(X) = f(X^{(0)}) +
\triangledown f(X^{(0)})T \triangle X +
\frac{1}{2} \triangle X^T H(X^{(0)}) \triangle X +
...
$$
其中 $H(X^{(0)})$ 即二元函数 $f(x_1,x_2)$ 在 $X^{(0)}$ 点处的海森矩阵，即二阶偏导数组成的方阵； $\triangledown f(X^{(0)})$ 是函数在该点处的梯度。

牛顿法

考虑无约束最优化问题：
$\min_{x}f(x)$

1.首先讨论单自变量情况

假设 $f(x)$ 具有二阶连续导数，运用迭代的思想，我们假设第 $k$ 次迭代值为 $x^{(k)}$ ，将 $f(x)$ 进行二阶泰勒展开：
$f(x)=f(x^{(k)})+f'(x^{(k)})(x-x^{(k)})+\frac{1}{2}f''(x^{(k)})(x-x^{(k)})^2+R_2(x)$

其中 $R_2(x)$ 是 $(x-x^{(k)})^2$ 的高阶无穷小，也叫做泰勒余项。

由于二阶可导，函数 $f(x)$ 有极值的必要条件是极值点处一阶导数为0，令 $f'(x)$ 为0解出 $x^{(k+1)}$ ：
$f'(x^{(k)})+f''(x^{(k)})(x-x^{(k)})=0$
$x^{(k+1)} = x^{(k)} - \frac{f'(x^{(k)})}{f''(x^{(k)})}$
至此，当数列满足收敛条件时我们可以构造一个初始值 $x^{(0)}$ 和上述递推公式得到一个数列 $\{x^{(k)}\}$ 不停地逼近极小值点

2.多自变量的情况

按照前面海森矩阵的介绍，在多自变量情况下，二阶泰勒展开式可写为：
$f(X) = f(X^{(k)}) + \triangledown f(X^{(k)})^T \triangle X + \frac{1}{2} \triangle X^T H(X^{(k)}) \triangle X + ...$
函数 $f(X)$ 极值必要条件要求它必须是 $f(X)$ 的驻点，即：
$\triangledown f(X) = 0$
由于 $\triangledown f(X^{(k)})$ 和 $H(X^{(k)}) = \triangledown ^2f(X^{(k)})$ 分别表示函数 $f(X)$ 的梯度和海森矩阵取值为 $X^{(k)}$ 的实值向量和实值矩阵，我们分别将其记为 $g_k$ 和 $H_k$ ，根据驻点解出 $X^{(k+1)}$ ：
$g_k + H_k(X-X^{(k)}) = 0$
$X^{(k+1)} = X^{(k)} - H_k^{-1}g_k$
同样我们可以构造一个迭代数列不停地去逼近函数的最小值点。

拟牛顿法

在牛顿法的迭代过程中，需要计算海森矩阵 $H^{-1}$ ，一方面有计算量大的问题，另一方面当海森矩阵非正定时牛顿法也会失效，因此我们考虑用一个 $n$ 阶矩阵 $G_k = G(X^{(k)})$ 来近似替代 $H^{-1}_k = H^{-1}(X^{(k)})$ `。

1.拟牛顿条件

根据前面的迭代式子：
$\triangledown f(X) = g_k + H_k(X-X^{(k)}) = 0$
取 $X = X^{(k+1)}$ ，我们可以得到：
$g_{k+1} - g_k = H_k(X^{(k+1)} - X^{(k)})$
记 $y_k = g_{k+1} - g_k$ , $\delta_k = X^{(k+1)} - X^{(k)}$ ，那么可以得到：
$y_k = H_k \delta_k$
或
$H_k^{-1} y_k = \delta _k$
上述两个式子就是拟牛顿条件。