梯度下降法

对于函数$f:R^n\rightarrow R$，输入为$\vec x = (x_1, x_2, x_3, \dots,x_n)^T$

梯度

定义函数的梯度为：

$$\nabla_{\vec x} f(\vec x) = \left(\frac{\partial f(\vec x)}{x_1}, \frac{\partial f(\vec x)}{x_2},\dots, \frac{\partial f(\vec x)}{x_n}\right)^T$$

方向导数

方向导数：一个标量场在某点沿着某个向量方向上的方向导数，描绘了该点附近标量场沿着该向量方向变动时的瞬时变化率。
沿着方向$\vec u$的方向导数表示在$\vec x$处，沿着方向$\vec u$，函数的增长率，定义为：

$$\lim_{\alpha \rightarrow 0}\frac{f(\vec x + \alpha \vec u) - f(\vec x)}{\alpha},其中\vec u为单位向量 \\ =\vec u^T \nabla_{\vec x}f(\vec x)$$

梯度为一个矢量，方向导数为一个标量

梯度下降法

为了最小化$f$，则需要寻找一个方向$\vec u$，沿着该方向，函数减少的速度最快，即：

$$\max \limits_{\vec u}-\vec u^T \nabla_{\vec x}f(\vec x) \\ s.t.||\vec u||_2=1$$

即：

$$\min \limits_{\vec u}\vec u^T \nabla_{\vec x}f(\vec x) \\ s.t.||\vec u||_2=1$$

设$\vec u$与梯度的夹角为$\theta$，则所求的$\theta$为：

$$\theta ^*=\min \limits_\theta||\vec u||_2||\nabla_{\vec x}f(\vec x)||_2cos\theta$$

又因为$||\vec u||_2=1$,且夹角$\theta$与梯度的模长无关

$$\theta ^*=\min cos\theta$$

则当$\theta=π$时，即当$\vec u$为沿着梯度的反方向时，函数值减小的速率最快。

梯度下降求解过程：

学习率的选择方法:

• 选择一个小的正常数
• 线性搜索，给定一个学习率集合，每次迭代选择使得目标函数下降最大的学习率
• 最速下降法。

当目标函数为凸函数时，梯度下降法的解为全局最优解

牛顿法

海森矩阵

当函数的输入为多维时，定义海森矩阵：

观察矩阵结构可以看出，当函数的二阶偏导数连续时，海森矩阵是对称的。

梯度下降法的缺点

将$f(\vec x)$在$x_0$出泰勒展开：

$$f ( \vec { \mathbf { x } } ) \approx f \left( \vec{ \mathbf { x } } _ { 0 } \right) + \left( \vec{ \mathbf { x } } - \vec{ \mathbf { x } } _ { 0 } \right) ^ { T } \vec{ \mathbf { g } } + \frac { 1 } { 2 } \left( \vec{ \mathbf { x } } - \vec{ \mathbf { x } } _ { 0 } \right) ^ { T } \mathbf { H } \left( \vec{ \mathbf { x } } - \vec{ \mathbf { x } } _ { 0 } \right)$$

其中$\vec g$为$\vec x_0$处的梯度，$H$为$\vec x_0$处的海森矩阵。
根据梯度下降法：$\vec{ \mathbf { x } } ^ { k+1 } = \vec{ \mathbf { x } }^{k} - \epsilon \vec g$
根据泰勒公式：

$$f ( \vec { \mathbf { x } }^{<K+1>} ) \approx f \left( \vec{ \mathbf { x } } ^ { k } \right) - \epsilon \vec{ \mathbf { g } } ^ { T } \vec{ \mathbf { g } } + \frac { 1 } { 2 } \epsilon ^ { 2 } \vec{ \mathbf { g } } ^ { T } \mathbf { H } \vec{ \mathrm { g } }$$

观察上式，若$\frac { 1 } { 2 } \epsilon ^ { 2 } \vec{ \mathbf { g } } ^ { T } \mathbf { H } \vec{ \mathrm { g } }$很大时，$f ( \vec { \mathbf { x } }^{ K+1 } ) > f ( \vec { \mathbf { x } }^{ K } )$，此时沿着负梯度，函数值反而在增大，则：

• 如果 $\epsilon ^ { 2 } \vec{ \mathbf { g } } ^ { T } \mathbf { H } \vec{ \mathrm { g } } < 0$，则无论$\epsilon$取多大的值，函数值都是持续减小的
• 如果 $\epsilon ^ { 2 } \vec{ \mathbf { g } } ^ { T } \mathbf { H } \vec{ \mathrm { g } } > 0$，则只有当$\epsilon$很小时，函数值才会持续减小。

牛顿法

牛顿法就是在梯度下降中加入和目标函数二阶导数的信息。
设$\vec x$第k次的迭代值为$\vec x ^ { k }$,第k+1次的迭代值为$\vec x^{ k+1 }$同样对目标函数在$\vec x_k$泰勒展开：

$$f ( \vec { \mathbf { x } } ) \approx f \left( \vec{ \mathbf { x } } ^ { \ <k> } \right) + \left( \vec{ \mathbf { x } } - \vec{ \mathbf { x } } ^ { \ <k> } \right) ^ { T } \vec{ \mathbf { g }_{k} } + \frac { 1 } { 2 } \left( \vec{ \mathbf { x } } - \vec{ \mathbf { x } } ^ { \ <k> } \right) ^ { T } \mathbf { H }_{k} \left( \vec{ \mathbf { x } } - \vec{ \mathbf { x } } ^ { \ <k> } \right)$$

当$\vec x$为极值，则满足$\frac{\partial f(\vec x)}{\partial \vec x}=\vec 0$，若经过k+1次迭代后求得极值，则满足$\frac{\partial f(\vec x^{,k+1})}{\partial \vec x^{k+1}}=\vec 0$，带入上式有：

$$\vec g_k + \vec H_k \left(\vec x^{\ <k+1>}-\vec x^{\ <k>}\right)=\vec 0$$

最后求得:

$$\vec x^{\ <k+1>} = \vec x^{\ <k>} - \vec H_k^{-1} \cdot \vec g_k$$

牛顿法迭代过程

牛顿法的缺点：

• 计算海森矩阵的逆开销较大
• 当位于鞍点附近时，牛顿法效果很差，因为牛顿法会主动跳入鞍点。

拟牛顿法

在牛顿法的迭代中，需要计算海森矩阵的逆矩阵$H^{-1}$，这一计算比较复杂。可以考虑用一个矩阵$G$来代替海森矩阵的逆矩阵。
矩阵$G$需要满足的条件:

• 正定
• 满足拟牛顿条件
  $\lfet( \vec g{k+1} - \vec g{k} \right) = H_k \cdot \left(\vec x^{ k+1 }-\vec x^{ k }\right)$

常见的逆牛顿算法

• DFP算法
• BFGS算法
• Broyden类算法

参考：
《统计学习方法》