迭代优化算法

机器学习训练过程和各种迭代优化算法密不可分，像梯度下降法、牛顿法等迭代式子随手都能写出来。但是对它们背后的数学原理却渐渐淡忘了。所以写一篇学习笔记，重新整理一下。

这些算法本身是用来求解方程解的，不过不难想到可以用他们来计算极值：求解导数为 0 的点。下面的内容首先从求解方程

开始说起。

基础

不动点迭代法

由于我本科学习的是计算数学，其中有数值计算这门课，所以在接触到机器学习之前就对牛顿法之类不陌生。为了将逻辑衔接的更紧密，首先就从不动点迭代法开始说起吧。

不动点迭代过程：

1. 首先将方程改写成：

   $$x = \phi(x)$$

   如果 $\dot{x}$ 满足 $f(\dot{x}) = 0$，那么显然有 $\dot{x} = \phi(\dot{x})$，这个 $\dot{x}$ 就称作不动点，同时也可以看出，不动点就是方程的解。

2. 选取一个解附近的点 $x_0$ 带入：

   $$x_1 = \phi(x_0)$$

3. 执行迭代过程：

   $$x_{k+1} = \phi(x_k)$$

4. 当 $|x_{k+1} - x_k| < \epsilon$ 时停止迭代，其中 $\epsilon$ 为定义的精度阈值。

Newton-Raphson 方法（牛顿法、牛顿切线法）

用一阶泰勒展开式近似 $f(x)$，有：

方程 $f(x)$ 在点 $x_0$ 附近可以近似表示为：

然后进行迭代：

1. 令：

   $$x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$

2. 迭代：

   $$x_{k+1} = x_k - \frac{f(x_k)}{f'(x_k)}$$

3. 当 $|x_{k+1} - x_k| < \epsilon$ 时终止，其中 $\epsilon$ 为定义的精度阈值。

个人理解，其实无论是梯度下降法还是牛顿法，本质思想都是不动点迭代，不同的是这个不动点针对的是函数本身还是函数的导数。

引申

用牛顿法求解函数极值点

有了上面的基础内容支撑，不难想出一个求解函数极值的方法。因为导数为 0 是函数极值的必要条件，所以，我们可以用牛顿法求解 $f'(x)$ 的零点。

首先考虑 $f(x)$ 在 $x_k$ 点的二阶泰勒展开式：

两边取导数，这一步计算要细心，记住 $f(x)$ 是函数，$f(x_k)$ 是数，求导的时候不要乱套：

假如在 $x_{k+1}$ 点可以取得极小值，那么有 $f'(x_{k+1}) = 0$。对上式两边带入 $x_{k+1}$，有：

整理一下得到递推式：

推广

在机器学习中，我们的输入往往不是标量，而是多组特征组成的向量。在这一节，我们将上面的内容推广到多元函数上。

牛顿法

仿照着一元函数的牛顿法推导过程，先在 $x_k$ 上进行泰勒展开。其中，$g_k$ 是在 $x_k$ 点的梯度向量，$H_k$ 是在 $x_k$ 点的海塞矩阵：

两边求梯度：

若在 $x_{k+1}$ 点取极值，两边带入 $x_{k+1}$ 得到：

整理一下就得到了迭代公式：

在这里可以看出牛顿法推广到多元函数之后的一个缺陷：求解海塞矩阵的逆矩阵很复杂。为了解决这个问题，拟牛顿法被提出了。

拟牛顿法

拟牛顿法的核心思路就是用一个矩阵 $G_k$ 替代海塞矩阵的逆 $H_k^{-1}$。

在 $x_{k+1}$ 不为极值点的时候，满足等式：

记 $y_k = g_{k+1} - g_k$，$\delta_k = x_{k+1} - x_k$。

那么有：

或：

这两个式子称作拟牛顿条件。

简而言之，只要保证拟牛顿条件成立，算法依然是”正确”的（具体来说，可以保证牛顿法的搜索方向正确，证明略去）。

进一步地，拟牛顿条件可以记作：

而更新 $G_k$ 的形式是：

最后，问题就只剩下一个：如何构造符合拟牛顿条件的 $G_k$。对于这一步有很多种具体实现方法，常用的就是 Broyden 类拟牛顿法。