白话机器学习数学——梯度下降与牛顿迭代

• 导言
• 预备知识

多元函数的泰勒展开式
梯度的概念
Hessian矩阵

• 梯度下降法
• 牛顿法
• 拓展-坐标下降法

总结

1. 导言

机器学习中，我们为了得到最优结果，需要寻找函数的最值这。由微积分的基础知识我们可知，即寻找函数在某一领域内的极值点。由于机器学习的模型涉及多个函数的变量及参数值，我们无法通过简单的多元函数求导找到函数的极值点。因此通常我们采用迭代法，从一个初始点$x_0$开始，反复使用某种规则从$x_k$移动到下一个点$x_{k+1}$，直到到达函数的极值点。即达成寻找到函数极小值的目标
$$mi{n}_{x}f(\vec{x})$$
其中$\vec{x}$称为优化变量，$f$称为目标函数。极大值问题可通过将目标值函数冠以负号转化为极小值问题。当然，有时也会对优化变量有约束。

2. 预备知识
   2.1多元函数的泰勒展开式
   由微积分知识我们可知，一元函数$f(x）$在某一点$x_0$处可展开为
   $$f(x)=\frac{f(x_0)}{0!}+\frac{f^{\prime }(x_0)}{1!}(x-x_0)+\frac{f^{\prime \prime }(x_0)}{2!}(x-x_0{)}^2+...+\frac{f^n(x_0)}{n!}(x-x_0{)}^n+o(x)$$
   类似地，我们可得到多元函数的泰勒展开公式（此处忽略了二次及以上的项）
   $$f(\vec{x}+\Delta \vec{x})=f(\vec{x})+(\nabla (\vec{x}{)}^T\Delta \vec{x})+o(x)$$
   其中$df$表示$f(\vec{x})$的全导数。
   2.2梯度
   如果将多元函数的自变量用一组n维向量
   $$\vec{x}=(x_1,x_2,...,x_n{)}^T$$
   表示出来，那么梯度身的概念即是对向量的偏导数，即
   $$gradf=\sum _{i=1}^n\frac{\partial f}{\partial x_i}$$
   或者说，梯度是一个向量，表示某一函数在该点处的方向导数沿着该方向取得最大值，即函数在该点处沿着该方向（此梯度的方向）变化最快，变化率最大（为该梯度的模）。
   2.3Hessian矩阵
   当函数有多输入时，若对函数求二阶导数，由链式求导法则可知，会产生多个二阶导数。通过将这些二阶导数合并成一个矩阵，称为Hessian矩阵，且有如下定义
   $$\mathbf{H}(f)({\vec{x}}_i{,}_j)=\frac{{\partial }^2}{\partial x_j\partial x_i}f(\vec{x})$$
   且由于微分算子在任何二阶偏导数连续的点处可交换，即
   $${\mathbf{H}}_{\mathbf{i}}{,}_{\mathbf{j}}={\mathbf{H}}_{\mathbf{j}}{,}_{\mathbf{i}}$$
   且Hessian矩阵是实对称矩阵。
   3.梯度下降法
   梯度下降法即沿着梯度向量的反方向进行迭代以达到函数的极值点。由前文所提及的忽略二次以上的项的多元函数泰勒展开式，可作如下变形
   $$f(\vec{x}+\Delta \vec{x})-f(\vec{x})=(\nabla f(\vec{x}{)}^T\Delta \vec{x})+o(x)$$
   用以描述函数的增量与自变量的增量$\Delta x$、函数梯度间的关系。如果
   $$(\nabla (\vec{x}{)}^T\Delta \vec{x})<0$$
   恒成立，则有
   $$f(\vec{x}+\Delta \vec{x})<f(\vec{x})$$
   即函数递减。因此，我们需要选择适合的$\Delta \vec{x}$来保证函数值的下降，设
   $$\Delta \vec{x}=-\gamma \nabla f(\vec{x})$$
   其中，$\gamma$为一个趋近0的常数（亦称之为学习率，Learning Rate），由人工设定，保证在$\vec{x}+\Delta \vec{x}$在$\vec{x}$的领域内，从而忽略泰勒展开式中二次及更高项。在梯度反方向有
   $$(\nabla f(\vec{x}{)}^T\Delta \vec{x})=-\gamma (\nabla f(\vec{x}){)}^T(\nabla f(\vec{x})\le 0$$
   从初始点$\overrightarrow{x_0}$开始，使用如下迭代公式
   $$\overrightarrow{x_{k+1}}={\vec{x}}_k-\gamma \nabla f({\vec{x}}_k)$$
   只要没有到达梯度为$\vec{0}$的点，函数值会沿着序列${\vec{x}}_k$递减，最终收敛到梯度为$\vec{0}$的点，此乃梯度下降法。
   4.牛顿法
   由前文所提及的Hessian矩阵、忽略了二次以上项的泰勒展开式，令函数梯度为$\vec{0}$我们可以得到
   $$\nabla f({\vec{x}}_0)+{\nabla }^{2}f({\vec{x}}_0)(\vec{x}-\overrightarrow{x_0})=\vec{0}$$
   解这个线性方程组可得，
   $$\vec{x}={\vec{x}}_0-({\nabla }^{2}f({\vec{x}}_0){)}^{-1}\nabla f({\vec{x}}_0)$$
   由于在泰勒展开中忽略了高阶项，因此，这个点并不一定是函数的驻点，需要反复用公式进行迭代
   $${\vec{x}}_{k+1}={\vec{x}}_k-({\nabla }^{2}f({\vec{x}}_k){)}^{-1}\nabla f({\vec{x}}_k)$$
   最终方可抵达驻点。其中，$-({\nabla }^{2}f({\vec{x}}_k){)}^{-1}\nabla f({\vec{x}}_k)$称为牛顿方向。
   迭代终止条件：梯度模接近于$\vec{0}$，或者函数值下降小于制定阈值。下面用一段伪代码表示这一流程:

while(1){
var x_0,k;
k=0;
cal(g_k,H_k);//计算梯度和矩阵
if (||g_k||<阈值) return ;
else{
cal(-H_k^(-1)g_k);//计算搜索方向
x_k+1=x_k+γd_k;//计算新的迭代点
k++;
cal(g_k,H_k);
}
}

与梯度下降一样，$\gamma$是一个步长。
如果目标函数为二次函数，则牛顿迭代可一步便收敛到极值点。
由于牛顿迭代不能保证每一步函数下降和一定收敛，因此常采用直线搜索。具体做法为让$\gamma$取一些典型的离散值，例如：
0.0001,0.001,0.01
比较取哪个时函数下降最快。
相比梯度下降的方法，牛顿法显然速度较快，但每一步迭代的代价也是很高的。在实际运用中，一般不直接求矩阵的逆，而是求解如下方程组：
$$H_{k}d=-g_k$$
当然，求解这个方程组还是使用迭代方法，比如共轭梯度法。
还有一个问题是，如果Hessian矩阵没有逆矩阵，那么上面那句话也就gg了。
5.拓展–最速下降法
在梯度下降中，为计算最优步长$\gamma$，记搜索方向为
$${\vec{d}}_k=-\nabla f({\vec{x}}_k)$$
则最小步长为
$${\gamma }_k=argmi{n}_{\gamma }f({\vec{x}}_k+\overrightarrow{\gamma d_k})$$
当然，这是一个一元函数极值问题，唯一优化变量是$\gamma$。
6.总结
梯度下降和牛顿法都是机器学习中求解最优化问题的常见方法。二者都基于泰勒展开和Hessian矩阵进行计算，且都有一定程度上的精度损失。当然，相比梯度下降算法，牛顿迭代法速度更快，损失也更大。
参考资料：
雷明，《机器学习与应用》，清华大学出版社
（美）Ian Goodfellow等，《深度学习》，人民邮电出版社
(第一次写博客，给个赞呗~）