为什么机器学习中的优化问题很少用到牛顿法?

  数学 数值计算 最优化 开放问题    浏览次数:8495        分享
14

机器学习中最常用到的就是梯度下降法,为什么很少用到收敛速度更快的牛顿法?


 

起个好名字   2017-09-28 20:47



   5个回答 
25

牛顿法需要计算二阶导数,也就是说要计算一个Hessian矩阵

  • 有些时候,损失函数的二阶导数的显式方程未必那么好求。机器学习不同于传统的优化问题,前者的目标函数可能是自己的定义的,未必是光滑的。
  • 机器学习问题与传统优化的另外一个区别是,前者的维数通常会很大,经常会上百或者上千乃至上万。如果数据集有n个特征,那么这个Hessian矩阵就是n x n的,我们需要求n平方个点,而sgd只需要求n个点。
  • 当n很大的时候,我们需要存一个n x n的矩阵,在空间也会是一个负担。

其次,牛顿法的步长是通过导数计算而来的。所以当临近鞍点的时候,步长会变得越来越小,这样牛顿法就很容易陷入鞍点之中。而sgd的步长是预设的固定值,相对容易跨过一些鞍点。


SofaSofa数据科学社区DS面试题库 DS面经

Lydia   2017-10-05 23:11

谢谢!解释得很清楚! - 起个好名字   2017-10-13 22:08
18

首先我先说说梯度下降。

其实梯度下降法在机器学习中也极小被直接使用。通常使用的也是梯度下降的改进版本,比如随机梯度下降、小批量梯度下降、随机平均梯度下降等等。


下面说说牛顿法。

  • 牛顿法需要二阶导数,也就是Hessian矩阵。
  • 牛顿法需要Hessian矩阵正定,如果是非正定的话,牛顿法会陷在鞍点。
  • 最重要的是,牛顿法的迭代中需要对Hessian矩阵求逆,$$x_{i+1} = x_i - H^{-1} \nabla_x J(x_{i})$$熟悉矩阵计算的朋友一定知道这件事有多昂贵。


败也萧何,败也萧何。牛顿法的优势也正是二阶收敛速度。所以就不少拟牛顿法,既保留二阶收敛速度,又尽量避免上面的缺陷。其中比较出名的,在机器学习中经常出现的有Broyden–Fletcher–Goldfarb–Shanno(BFGS)算法,它用低秩分解来代替求逆。后来还有的L-BFGS算法,降低了算法对内存的需求。对于很多多维机器学习问题,这个优势是很重要的。

所以说牛顿法的思想在机器学习的优化问题中依然是很常见的。


SofaSofa数据科学社区DS面试题库 DS面经

清风   2017-10-16 09:20

6

我觉得主要是因为牛顿法是二阶的,求二阶导数在大规模计算中应该是个很昂贵(费时间)的事情吧。


SofaSofa数据科学社区DS面试题库 DS面经

道画师   2017-10-04 10:41

谢谢! - 起个好名字   2017-10-13 22:08
4

虽然牛顿法不常用,但是各种拟牛顿法还是层出不穷的呀


SofaSofa数据科学社区DS面试题库 DS面经

Nagozi   2017-10-15 21:40

0

架不住计算量

SofaSofa数据科学社区DS面试题库 DS面经

wqtang   2019-03-04 15:34



  相关讨论

利用牛顿法求一个凸函数的最小值有可能出现发散的情况么?

用SGD时陷入局部最优解的解决方法

nesterov’s momentum和momentum的区别?

RMSProp的直白解释

对于小批量随机剃度下降法(mini-batch SGD),如何选择每批样本的数量?

随机梯度下降(sgd)的收敛问题

随机平均梯度法(Stochasitc Average Gradient)和随机梯度下降(SGD)有什么区别

最速下降法与梯度下降法

牛顿法到底是一阶优化算法还是二阶优化算法?

为什么梯度的反方向是函数下降最快的方向?

  随便看看

怎么让DataFrame按照某一列绝对值从小到按排列?

python里怎么计算曼哈顿距离?

二元分类问题中经常提到的TP,TN,FN,FP都是什么意思?

pandas同时返回一个dataframe的前几行(head)和后几行(tail)

numpy array里怎么用fillna填充nan的值?