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

  数学 数值计算 最优化 开放问题    浏览次数: 1861
13

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


 

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



   4个回答 
22

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

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

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


SofaSofa数据科学社区 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面经 问答 实战

清风   2017-10-16 09:20

6

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


SofaSofa数据科学社区 DS面经 问答 实战

道画师   2017-10-04 10:41

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

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


SofaSofa数据科学社区 DS面经 问答 实战

Nagozi   2017-10-15 21:40



  相关主题

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

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

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

RMSProp的直白解释   1回答

梯度上升算法是什么?   2回答

Adam优化算法   1回答

最速下降法与梯度下降法   1回答

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

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

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

学习率不当会导致sgd不收敛吗?   3回答

线性回归有精确的解析解为什么还要用梯度下降得到数值解?   4回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!