统计机器学习-牛顿法

作者: 又双叒叕苟了一天 | 来源:发表于2020-06-16 18:01 被阅读0次

统计机器学习-牛顿法
统计机器学习-拟牛顿法
局部搜索之牛顿法
机器学习入门之 — 梯度下降，牛顿法，拟牛顿法
[机器学习必知必会]牛顿法与拟牛顿法
统计机器学习-k近邻法
第一章统计学习方法概论
梯度优化算法
机器学习基础-梯度下降方法与牛顿法
牛顿法和最速下降法的Python实现

假设 $f(x)$ 是 $\textbf R^n$ 上具有二阶连续偏导数的函数，要求解的无约束最优化问题是
$\min_{x\in\textbf R^n}f(x)\tag1$
$x^*$ 表示目标函数 $f(x)$ 的极小点。

函数 $f(x)$ 有极值的必要条件是在极值点的一阶导数为0，特别是当海塞矩阵是正定矩阵时，函数 $f(x)$ 的极值为极小值。（因为当海塞矩阵是正定矩阵时函数为凸函数）

所以牛顿法的目标是通过迭代的方式找到一个 $x$ 的点使得
$\nabla f(x)=0\tag2$
假设在第 $k$ 次迭代时，找到的点是 $x^{(k)}$ ，让 $f(x)$ 在点 $x^{(k)}$ 附近进行二阶泰勒展开：
$f(x)=f(x^{(k)})+g_k^T(x-x^{(k)})+\frac12(x-x^{(k)})^TH(x^{(k)})(x-x^{(k)})\tag3$
其中 $g_k=g(x^{(k)})=\nabla f(x^{(k)})$ 是 $f(x)$ 在点 $x^{(k)}$ 的梯度， $H(x^{(k)})$ 是 $f(x)$ 的海塞矩阵（类似于二阶导数）在点 $x^{(k)}$ 的值：
$H(x)=\bigg[\frac{\partial^2f}{\partial x_i\partial x_j}\bigg]_{n\times n}\tag4$
假设在第 $k+1$ 次迭代时，找到的点是 $x^{(k+1)}$ ，满足(2)的要求，即：
$\nabla f(x^{(k+1)})=0\tag5$
公式(3)两边对 $x$ 求导：
$\nabla f(x)=g_k+H(x^{(k)})(x-x^{(k)})=g_k+H_k(x-x^{(k)})\tag6$
然后将点 $x^{(k+1)}$ 代入公式(6)并通过公式(5)得到：
$\nabla f(x^{(k+1)})=g_k+H(x^{(k)})(x^{(k+1)}-x^{(k)})=0\tag7$
所以
$x^{(k+1)}=x^{(k)}-H_k^{-1}g_k\tag8$
记
$H_kp_k=-g_k\tag9$
则公式(7)为
$x^{(k+1)}=x^{(k)}+p_k\tag{10}$
其中
$p_k=-H_k^{-1}g_k\tag{11}$
这样就得到了牛顿法的迭代方式，即公式(8)或公式(10)。

算法

输入：目标函数 $f(x)$ ，梯度 $g(x)=\nabla f(x)$ ，海塞矩阵 $H(x)$ ，精度要求 $\varepsilon$ ；

输出： $f(x)$ 的极小点 $x^*$ 。

取初始点 $x^{(0)}$ ，置 $k=0$
计算 $g_k=g(x^{(k)})$
若 $||g_k||\lt\varepsilon$ ，则停止计算，得近似解 $x^*=x^{(k)}$
计算 $H_k=H(x^{(k)})$ ，并求 $p_k$

$p_k=-H_k^{-1}g_k$

置 $x^{(k+1)}=x^{(k)}+p_k$
置 $k=k+1$ ，转(2)

步骤4中需要计算 $H_k^{-1}$ ，其计算比较复杂，所以有了拟牛顿法来进行改进。

统计机器学习-牛顿法
假设是上具有二阶连续偏导数的函数，要求解的无约束最优化问题是表示目标函数的极小点。函数有极值的必要条件是在极值点...
统计机器学习-拟牛顿法
假设是上具有二阶连续偏导数的函数，要求解的无约束最优化问题是表示目标函数的极小点。在牛顿法的迭代中，需要计算海塞...
局部搜索之牛顿法
除了前面说的梯度下降法，牛顿法也是机器学习中用的比较多的一种优化算法。牛顿法求方程解牛顿法又称为牛顿-拉弗森方...
机器学习入门之 — 梯度下降，牛顿法，拟牛顿法
梯度下降法梯度下降法用来求解目标函数的极值。这个极值是给定模型给定数据之后在参数空间中搜索找到的。迭代过程为： ...
[机器学习必知必会]牛顿法与拟牛顿法
前言同梯度下降法一样，牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法，每一步需要求解...
统计机器学习-k近邻法
k近邻法既可以用于分类，也可以用于回归，这里只讨论分类的k近邻法。k近邻法的思路是：给定一个输入，在训练集中找出个...
第一章统计学习方法概论
1.1 统计学习 a. ~概念: 又叫统计机器学习,人们提到的机器学习往往指统计机器学习, 它是利用计算机对数据构...
梯度优化算法
梯度下降，共轭梯度法；牛顿法，拟牛顿法；信赖域方法，罚函数法。
机器学习基础-梯度下降方法与牛顿法
相关概念：步长(learning rate):步长决定了梯度下降过程中，每一步沿梯度负方向前进的长度特征(fe...
牛顿法和最速下降法的Python实现
1 牛顿法 1.1 牛顿法的Python程序 1.2 牛顿法的结果分析程序执行的结果如下：经过...

统计机器学习-牛顿法

算法

相关文章

统计机器学习-牛顿法

统计机器学习-拟牛顿法

局部搜索之牛顿法

机器学习入门之 — 梯度下降，牛顿法，拟牛顿法

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

统计机器学习-k近邻法

第一章统计学习方法概论

梯度优化算法

机器学习基础-梯度下降方法与牛顿法

牛顿法和最速下降法的Python实现

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读