Machine Learning 学习笔记 (2) —— 另一种寻找极值的方法：牛顿法

【总目录】http://www.cnblogs.com/tbcaaa8/p/4415055.html

1. 用牛顿法解方程

牛顿法是一种求解方程的迭代算法，也可以用于方程组的求解。其思想是利用方程（尤其是非线性方程）的线性部分，对原方程进行近似。不失一般性，考虑方程f(x)=0。对f(x)在x=t处进行泰勒展开，可得f(x)=f(t)+f‘(t)(x-t)+...

取线性部分代替f(x)，带入方程f(x)=0，可得f(t)+f‘(t)(x-t)=0 ，进而解出x=t-f(t)/f‘(t)。将方程的解写为迭代形式，可以得到牛顿法的迭代公式：

[例]使用牛顿法解方程x³+x=2

第一步：求f(x)及f‘(x)，即f(x)=x³+x-2, f‘(x)=3x²+1

第二步：选择迭代初始值。初始值一般应选在解的附近，以防算法不收敛。这里选择x⁽⁰⁾=2

第三步：根据迭代公式和初始值迭代求解。迭代过程如下：

结论：经过4次迭代后，函数取值变为0，即原方程的根已找到。

牛顿法的收敛条件及收敛速度略去。在机器学习的应用中，可以采用尝试不同初始值的方法减少不收敛现象的发生；若牛顿法收敛，一般可以达到二次收敛的收敛速度，与梯度下降法相比，迭代次数明显减少。

2. 用牛顿法解方程组

在本系列上一篇文章中，我们使用梯度下降法求解损失函数J的极小值；而从上面的描述来看，牛顿迭代只是用来求解方程的根，这与多元函数的极小值又有什么联系呢？其实，要求多元函数的极小值，只需令多元函数对每一个自变量的偏导数为0，并解出此时每一个自变量的取值即可。于是，多元函数极小值问题，被转化为多元非线性方程组求解问题。

首先考虑多元函数的泰勒展开。不失一般性，以f₁(x₁,x₂,...,x_n)为例，在点(t₁,t₂,...,t_n)的泰勒展开式如下：

取线性部分代替f₁(x)，并令其为0，有：

将其整理为向量形式，并分离出自变量，可以得到：( 为了简便，以下使用f₁代替f₁(t₁,t₂,...,t_n) )

假定方程组由一系列方程{f₁=0, f₂=0, ..., f_n=0}组成，可以将上式整理为矩阵形式：

上式中的n*n矩阵为雅可比矩阵(Jacobian Matrix)，简记为J(F)。同时，将自变量(x₁,...,x_n)记为X，将(t₁,...,t_n)记为T，将(f₁,...,f_n)记为F，则有：

化简后可得：

将方程组的解写为迭代形式，即可得到适用于方程组求解的牛顿法迭代公式：

至此可以发现，虽然牛顿法的迭代次数比梯度下降法小得多，但是在每一次迭代过程中，都需要重新计算J(F)的逆矩阵。若n为特征维数，则通常逆矩阵的计算需要Θ(n³)的时间复杂度。使用Strassen方法可以使逆矩阵计算的时间复杂度降至Θ(n^log₂7)，也可以使用数值方法近似求解逆矩阵，但当特征维数较大时，这两种方法仍然很慢。因此，仅在特征维数较小时，牛顿法才能够快速收敛。特殊地，当取n=1时，上式可退化为本文第1节推导出的，用于求解单个方程的牛顿迭代公式。

3. 使用牛顿法求函数的极值

若用▽f(X)表示函数f(X)的梯度向量，带入普通牛顿法迭代公式中，即可得到用于求函数极值的迭代公式：

考虑到：

迭代公式可以在形式上进一步化简：

其中，H(f)表示函数f(x₁,...,x_n)的海森矩阵(Hessian Matrix)。

就具体问题而言，本系列上一篇文章需要求损失函数的极小值。除了之前介绍的梯度下降法之外，还可以使用本文章介绍的牛顿法。对应的迭代公式为：