开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

社区首页 >专栏 >[机器学习必知必会]牛顿法与拟牛顿法

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

作者头像

TOMOCAT

发布于 2020-06-09 18:08:44

9060

发布于 2020-06-09 18:08:44

举报

文章被收录于专栏：懂点编程的数据分析师懂点编程的数据分析师

前言

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

需要提前了解的知识

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_12}}\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_22}}\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

上述两个式子就是拟牛顿条件。

2.常见的拟牛顿法

根据拟牛顿条件，我们可以构造不同的

G_k

，这里仅列出常用的几种拟牛顿法，可根据需要再学习具体实现。

DFP算法（Davidon-Fletcher-Powell）
BFGS算法（Broydeb-Fletcher-Goldfarb-Shanno）
Broyden类算法

Reference

[1] 统计学习方法

本文参与?腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客?前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ，欢迎热爱写作的你一起参与！

评论

登录后参与评论

0 条评论

热度

最新

LV.

目录

前言
需要提前了解的知识
- 1.泰勒展开
- 2.海森矩阵
牛顿法
- 1.首先讨论单自变量情况
- 2.多自变量的情况
拟牛顿法
- 1.拟牛顿条件
- 2.常见的拟牛顿法
Reference