老饼教你深入浅出理解-《牛顿法求极值》-EW帮帮网

本站原创文章，转载请说明来自 《老饼讲解-机器学习》 ml.bbbdata.com

01.牛顿法求根

问题

迭代方法

牛顿法求极值是一种机器学习中常见的方法，

由于它利用了二阶导信息，它的迭代速度比梯度下降法要更加快，

但往往由于计算量较为复杂，它的使用往往没有梯度法广泛。

本文介绍什么是牛顿法求极值，并给出相关理论思路与推导。

本文思路介绍

牛顿求极值方法的思想来源于牛顿求根法，

因此，本文的讲解思路为：

牛顿求根法 --> 一维牛顿求极值 --> 多维牛顿求极值

01.牛顿法求根

问题

函数求根，即求函数 $f(x) = 0$ 时 x 的取值.😳

迭代方法

(1) 设置一个初始解 $x_0$
（2）按公式 $x_{n+1} =x_n-\dfrac{f(x_n)}{f'(x_n)}$ 进行迭代，直到满足退出条件
退出条件：f(x)已极度近似0，或者达到最大迭代次数。

推导思路

(1) 设初始点为 $x_0$
(2) 在该点附近函数可用该点切线 $f_2(x) = f(x_0)+f'(x_0)(x-x_0)$ 近似替代,
(3) 用该近似函数 (直线 $f_2$    ) 的解    $x = x_0-\dfrac{f(x_0)}{f'(x_0)}$   作为新的解.
即迭代公式为:    $x_{n+1} =x_n-\dfrac{f(x_n)}{f'(x_n)}$

02.牛顿法求极值

问题

函数求极值，即求函数f(x)取得极值时 x 的取值😳

思路1：直接化为牛顿求根法

求 f(x)f(x) 的极值,即求 f'(x) = 0
套用牛顿求根法,可得迭代公式： $x_{n+1} = x_n - \dfrac{f'(x_n)}{f''(x_n)}$

思路2：借用牛顿求根法思路

现在我们要求取  f(x)的极值,
借用牛顿求根法思路如下：
(1) 设初始点为  x_0

(2) 在该点附近函数可用该点的近似二次曲线替代：
$f(x_0+h) \approx g(h) = f(x_0)+f'(x_0)h+\dfrac{1}{2}f''(x_0)h^2$

(3) 用该近似函数g(h)   ( 二次曲线) 的极小解作为新的解.
$x= x_0-\dfrac{f'(x_0)}{f''(x_0)}$
即迭代公式为:   $x_{n+1} = x_n- \dfrac{f'(x_n)}{f''(x_n)}$

✍️附：近似二次曲线的解推导

该曲线的极值点为其一阶导为0处：
$g(h)' = \left [ f(x_0)+f'(x_0)h+\dfrac{1}{2}f''(x_0)h^2 \right ] ' = f'(x_0)+f''(x_0)h = 0$

得： $h = -\dfrac{f'(x_0)}{f''(x_0)}$ ，即 $x = x_0+h = x_0-\dfrac{f'(x_0)}{f''(x_0)}$

03.多维牛顿求极值

问题

求 $F(\textbf{x})$ 的极值,
其中， $\text{x}$ 为多维向量

牛顿求极值-多维迭代方法

(1)  设置一个初始解 $\textbf{x}_0$
(2)  按以下公式迭代，直到满足终止条件
$\textbf{x}_{n+1}= \textbf{ x}_n -H^{-1}G$
其中：
G为梯度(Gradient)（F的一阶偏导）
H为Hession矩阵（F的二阶偏导矩阵）

推导过程

多维情况下是类似的
$F(\textbf{x})$ 在 $\textbf{x}_0$ 处的近似二次曲面为:

$F(\textbf{x}_0+\textbf{h}) \approx F(\textbf{x}_0)+F'(\textbf{x}_0)\textbf{h}+\dfrac{1}{2} \textbf{h}^TF''(\textbf{x}_0)\textbf{h}$

该曲面极值点为其一阶导为 0 处:

$\left [ F(\textbf{x}_0)+F'(\textbf{x}_0)\textbf{h}+\dfrac{1}{2} \textbf{h}^TF''(\textbf{x}_0)\textbf{h} \right ]' = F'(\textbf{x}_0)+F''(\textbf{x}_0)\textbf{h} = 0$

即得:

$\textbf{h} = \left [ F''(\textbf{x}_0) \right ]^{-1} \left [ -F'(\textbf{x}_0) \right ]$

一阶导称为梯度(Gradient),记为G
二阶导称为Hession矩阵,记为H

则简记为:
$\textbf{h} = -H^{-1}G$