2018年3月

迭代优化算法

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

这些算法本身是用来求解方程解的,不过不难想到可以用他们来计算极值:求解导数为0的点。下面的内容首先从求解方程
$$ f(x)=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) \approx f(x_0) + f'(x_0)(x-x_0)
$$
方程 $ f(x) $ 在点 $ x_0 $附近可以近似表示为
$$
f(x_0) + f'(x_0)(x-x_0) = 0
$$
然后进行迭代
1.令
$$
x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}
$$
2.迭代
$$
x_{k+1} = x_0 - \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) + f'(x_k)(x-x_k) + \frac{1}{2}f''(x_0)(x-x_0)^2
$$
两边取导数,这一步计算要细心,记住$f(x)$是函数,$f(x_0)$是数,求导的时候不要乱套。
$$
f'(x) = f'(x_k) + f''(x_k)(x-x_k)
$$
假如在$x_{k+1}$点可以取得极小值,那么有$f'(x_{k+1}) = 0$。对于上式,两边带入$x_{k+1}$,有
$$
f'(x_{k+1}) = 0 = f'(x_k) + f''(x_k)(x_{k+1} - x_k)
$$
整理一下得到递推式
$$
x_{k+1} = x_k - \frac{f'(x_{k+1})}{f''(x_k)}
$$

推广

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

牛顿法

仿照着一元函数的牛顿法推导过程,先在 $ x_k $上进行泰勒展开。其中,$ g_k $是在$ x_k $点的梯度向量,$ H_k $是在 $ x_k $点的海塞矩阵。
$$
f(x) = f(x_k) + g_k^T(x - x_k) + \frac{1}{2}(x - x_k)^T H_k (x - x_k)
$$
两边求梯度
$$
\nabla f(x) = g_k + H_k(x - x_k)
$$
若在 $ x_{k+1} $ 点取极值,两边带入 $ x_{k+1} $得到
$$
\nabla f(x_{k+1}) = g_{k+1} = 0 = g_k + H_k(x_{k+1} - x_k)
$$
整理一下就得到了迭代共识
$$
x_{k+1} = x_k - H_k^{-1}g_k
$$
在这里可以看出牛顿法推广到多元函数之后的一个缺陷:求解海塞矩阵的逆矩阵很复杂。为了解决这个问题,拟牛顿法被提出了。

拟牛顿法

拟牛顿法的核心思路就是用一个矩阵 $ G_k $ 替代海塞矩阵的逆 $ H_k^{-1} $
在 $ 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
$$
这两个式子称作拟牛顿条件
简而言之,只要保证拟牛顿条件成立,算法依然是“正确”的(具体来说,可以保证牛顿法的搜索方向正确,证明略去)。
进一步地,拟牛顿条件可以记作
$$
G_{k+1}y_k = \delta_k
$$
而更新 $ G_k $ 的形式是
$$
G_{k+1} = G_k + \Delta G_k
$$
最后,问题就只剩下一个:如何构造符合拟牛顿条件的 $ G_k $。对于这一步有很多种具体实现方法,常用的就是Broyden类拟牛顿法。