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

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

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

1. 梯度下降法的推导

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

一元函数的泰勒展开大家应该都知道，公式如下：
$$ f(x)=f(x_0)+\frac{f’(x_0)}{1!}(x-x_0)+\frac{f’’(x_0)}{2!}(x-x_0)^2+\frac{f’’’(x_0)}{3!}(x-x_0)^3+… $$

不妨只取右边式子的前两项，也就是一个“约等于”的结果：
$$ f(x)=f(x_0)+\frac{f’(x_0)}{1!}(x-x_0) $$

记：$ \Delta x=x-x_0 $，上式变为：
$$ f(x)=f(x_0)+\frac{f’(x_0)}{1!}\Delta x $$

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

容易想到，应该构造：
$$ \Delta x=-f’(x_0) $$

此时：
$$ f(x)=f(x_0)-f’(x_0)^2 $$

写成迭代形式：
$$ f(x_{n+1})=f(x_{n})-f’(x_{n})^2 $$

由于$ f’(x)^2\geq 0 $，我们就完成了对于梯度下降有效性的证明。从上述步骤归纳出来的参数迭代更新的公式如下：
$$ x_{n+1}=x_{n}-\alpha \Delta x_{n} $$

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

2. 牛顿法

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

继续看泰勒展开：
$$ f(x)=f(x_0)+\frac{f’(x_0)}{1!}(x-x_0)+\frac{f’’(x_0)}{2!}(x-x_0)^2+\frac{f’’’(x_0)}{3!}(x-x_0)^3+… $$

依旧，我们取右式的前2项：
$$ f(x)=f(x_0)+\frac{f’(x_0)}{1!}(x-x_0) $$

对等式两边取导数：
$$ f’(x)=f’(x_0)+\frac{f’’(x_0)}{1!}(x-x_0) $$
$$ f’(x)=f’(x_0)+\frac{f’’(x_0)}{1!}\Delta x $$

根据微积分的性质，$ f(x) $取最小值时，有$ f’(x)=0 $，我们把这个性质代入上面的式子，有：
$$ 0=f’(x_0)+\frac{f’’(x_0)}{1!}\Delta x $$
$$ \Delta x=-\frac{f’(x_0)}{f’’(x_0)} $$

这样我们就得到了牛顿法的参数迭代更新公式如下：
$$ x_{n+1}=x_{n}-\frac{f’(x_n)}{f’’(x_n)} $$

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

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

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

4. 拟牛顿法

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