牛顿法、拟牛顿法

作者: yi_cloud | 来源:发表于2019-01-21 16:00 被阅读0次

梯度优化算法
牛顿法、拟牛顿法
牛顿法、拟牛顿法
Newton's method and Quasi Ne
最优化方法
【转】常见的几种最优化方法
Logistic回归(Logistic Regression)算
2018-08-23
[机器学习必知必会]牛顿法与拟牛顿法
PyTorch基础知识

牛顿法：

根据二阶泰勒展开，用一阶和二阶倒数确定参数迭代步长和方向

设初始向量 $\vec{x}$ ，它在 $\vec{x_k}$ 处的泰勒展开如下：

$f(\vec{x})=f(\vec{x_k})+\nabla f(\vec{x}_k)^T(\vec{x}-\vec{x}_k) +\frac{1}{2} (\vec{x}-\vec{x}_k)^T \nabla^2 f(\vec{x}_k)(\vec{x}-\vec{x}_k)+o(x)$ ，当 $\vec{x}_k\rightarrow \vec{x}$ 时

注：矩阵求导公式：

$X^TAX=2AX$ $a^TX=a$

对上式相对于 $\vec{x}$ 求导：

$\frac{\partial f(\vec{x})}{\partial \vec{x}} = \nabla f(\vec{x}) = \nabla f(\vec{x}_k)+\nabla^2 f(\vec{x}_k)(\vec{x}-\vec{x}_k)$ ①

因此可以得到 $\vec{x}_k$ 处的迭代方程：

$\vec {x}_{k+1} = \vec {x}_k - \frac{\nabla f(\vec{x}_k)}{\nabla^2 f(\vec{x})}$

对应 $\vec {x}_{k+1} = \vec {x}_k + \lambda_kd_k$ 这种形式，步长 $\lambda_k=\nabla f(\vec{x_k})$ ，方向 $d_k=-\frac{1}{\nabla^2 f(\vec{x})}$

拟牛顿法：

从上述公式可以知道，牛顿法的每一次迭代都需要计算二阶海塞矩阵，当特征和数据非常多时，时间和空间开销都会比较大。

拟牛顿法只是一种方法的统称，即用一个近似矩阵B去替代逆海塞矩阵 $H^{-1}$ ，然后在每一轮迭代中更新B

怎样找到逆海塞矩阵的替代矩阵？

对上一节中的①式做一下变换：

$\nabla f(\vec{x}_{k+1}) - \nabla f(\vec{x}_k)=\nabla^2 f(\vec{x}_k)(\vec{x}_{k+1}-\vec{x}_k)$

令 $g_k=\nabla f(\vec{x_k})$ , $H_k= \nabla^2 f(\vec{x_k})$ ，上式变成：

$g_{k+1}-g_k=H_k(\vec{x}_{k+1}-\vec{x}_k)$

再令 $g_{k+1}-g_k=y_k$ ， $S_k=\vec{x}_{k+1}-\vec{x}_k$ ，得到：

$H_k=\frac{y_k}{S_k}$ ①

也就是说，第k步迭代的海塞矩阵可以通过第k步的迭代步长和一阶导数差值拟合。

BFGS(Broyden–Fletcher–Goldfarb–Shanno):
https://blog.csdn.net/itplus/article/details/21897443

BFGS算法

用 $B_k$ 表示 $H_k$ 的近似， $D_k$ 表示 $H^{-1}_k$ 的近似：

那么 $B_{k+1}$ 的迭代公式为 $B_{k+1}=B_k+\Delta B_k$

设 $\Delta B_k= \alpha uu^T+\beta vv^T$ ②，再根据①式得到的 $y_k=B_kS_k$ :

$y_k=B_k\cdot S_k +\alpha \boldsymbol{u u^T} S_k +\beta \boldsymbol{v v^T} S_k$

交换 $u^TS_k$ 和 $u$ 的位置： $y_k=B_k\cdot S_k +\alpha \boldsymbol{ u^T} S_k \boldsymbol{u} +\beta \boldsymbol{v^T} S_k \boldsymbol{v}$

令： $\alpha u^T S_k=1, \beta v^T S_k=1$ ，以及 $u=y_k,v=S_k$

解出： $\alpha=\frac{1}{y_k^TS_k},\beta=\frac{-1}{v^T S_k}=\frac{-1}{S_k^TB_k^TS_k}$

再带入到②中：

$\Delta B_k = \frac{y_k y_k^T}{y_k^T S_k} -\frac{B_k S_k S_k^T B_K^T}{S_K^T B_K^T S_k}$

L-BFGS:

BFGS中B矩阵的每次更新都需要nXn的空间开销，L-BFGS不会直接存储B，而是①只存取需要用到的n个向量，并且②只保存了最近的m次迭代的结果，所以L-BFGS算法又做了近似。

梯度优化算法
梯度下降，共轭梯度法；牛顿法，拟牛顿法；信赖域方法，罚函数法。
牛顿法、拟牛顿法
摘抄：https://blog.csdn.net/lilong117194/article/details/781...
牛顿法、拟牛顿法
牛顿法：根据二阶泰勒展开，用一阶和二阶倒数确定参数迭代步长和方向设初始向量，它在处的泰勒展开如下：，当时注...
Newton's method and Quasi Ne
Welcome To My Blog 牛顿法和拟牛顿法是求解无约束最优化问题的常用方法,优点是收敛速度快.牛顿法...
最优化方法
常见最优化方法 1.梯度下降法 2.牛顿法 3.拟牛顿法 4.共轭梯度法
【转】常见的几种最优化方法
转自Poll 的笔记阅读目录梯度下降法（Gradient Descent）牛顿法和拟牛顿法（Newton's...
Logistic回归(Logistic Regression)算
本节不仅介绍了Logistic回归在sklearn中模型应用，还介绍了liblinear、牛顿法、拟牛顿法(DFP...
2018-08-23
1.gbdt,xgboost,lgbm的区别(阿里，头条) 2.梯度下降法，牛顿法，拟牛顿法区别(阿里) 3.SG...
[机器学习必知必会]牛顿法与拟牛顿法
前言同梯度下降法一样，牛顿法和拟牛顿法也是求解无约束最优化问题的常用方法。牛顿法本身属于迭代算法，每一步需要求解...
PyTorch基础知识
一. 常用优化方法最小二乘法，牛顿法，拟牛顿法，梯度下降法二. tensor和numpy array的相互转换...