发表于

2018-06-29

| 分类于 机器学习

| 评论数：

| 阅读次数：

本文原载于https://imlogm.github.io，转载请注明出处~

摘要：梯度下降法是机器学习中用到比较多的一种求解方法，一般大家会通过形象化的图像来理解为什么梯度下降法有效。本文用数学推导的方式来证明梯度下降法有效，同时也介绍下牛顿法。

关键字：机器学习, 梯度下降, 牛顿法

1. 梯度下降法的推导

梯度下降法在机器学习和深度学习里用的非常多，一般教程或者教材在解释梯度下降法的时候会用形象化的方式（二次曲线、下凸面等），想必大家都知道如何用形象化的方式来说明梯度下降法的有效性。这里，我就不再赘述这种形象化的解释了。我这里使用数学推导来证明梯度下降法的有效性。

一元函数的泰勒展开大家应该都知道，公式如下：

不妨只取右边式子的前两项，也就是一个“约等于”的结果：

记：Δx=x−x0Δx=x−x0，上式变为：

我们的目标是在迭代过程中让下式恒成立，也就是说希望迭代过程中函数值会逐渐减小，用数学语言描述就是：f(xn+1)≤f(xn)f(xn+1)≤f(xn)

容易想到，应该构造：

此时：

写成迭代形式：

由于f′(x)2≥0f′(x)2≥0，我们就完成了对于梯度下降有效性的证明。从上述步骤归纳出来的参数迭代更新的公式如下：

以上步骤是在一元函数上证明了梯度下降的有效性。容易推广到多元函数。另外，在多元函数中，还可以补充证明梯度方向是下降最快的方向。详见：为什么梯度下降能找到最小值？-root的回答

2. 牛顿法

说完了梯度下降法，顺便介绍下牛顿法的推导。因为牛顿法也是通过泰勒展开推导出来的。

继续看泰勒展开：

依旧，我们取右式的前2项：

对等式两边取导数：

根据微积分的性质，f(x)f(x)取最小值时，有f′(x)=0f′(x)=0，我们把这个性质代入上面的式子，有：

这样我们就得到了牛顿法的参数迭代更新公式如下：

3. 梯度下降法和牛顿法的异同

从上面的证明过程可以看出，梯度下降法和牛顿法虽然都可以用泰勒展开推导，但推导所依据的思想还是有一点不一样的。

在实际运用中，牛顿法和梯度下降法都是广泛应用于机器学习中的。两者的区别其实很多博客都有写，比如：梯度下降or拟牛顿法？-过拟合的回答

4. 拟牛顿法

在上面牛顿法的参数迭代更新公式中，我们可以看到f′′(x0)f″(x0)是位于分母部分的。记住，上面的数学推导是用的一元函数，对于多元函数，这个分母存在相当于要计算Hessian矩阵的逆矩阵，这是非常困难且耗费时间的。因此，很多牛顿算法的变形出现了，这类变形统称拟牛顿算法。BFGS是用迭代法去近似计算海森矩阵。而BFGS需要额外储存近似的那个海森矩阵，所以有了改进版L-BFGS。