机器学习基础-梯度下降方法与牛顿法

相关概念：

步长(learning rate):步长决定了梯度下降过程中，每一步沿梯度负方向前进的长度

特征(feature):样本输入

矩阵求导的链式法则：

公式一： $\frac{\partial(XX^T)}{\partial X} =2X$

公式二： $\frac{\partial X}{\partial x} = X^T$

假设函数(hypothesis function):监督学习中，为拟合输入样本，使用的假设函数，记为 $h_\theta(x)$

损失函数(loss function):为评估模型拟合好坏，用损失函数度量拟合程度。损失函数极小化意味着拟合程度最好，对应的模型参数即为最优。线性回归中，损失函数通常为样本输出和假设函数的欧式距离(L2距离)，即 $J(\theta) = \sum_{i=0}^m(h_\theta(x_i)-y_i)^2$

梯度下降法（gradient descent）是求解无约束最优化问题的一种最常用方法，实现简单，梯度下降法是迭代算法，每一步需要求解目标函数的梯度。

1.确定优化模型的假设函数和损失函数

2.算法相关参数初始化：主要对象 $\theta_i(i=1,2,...,N)$ ,算法终止距离 $\varepsilon$ 和步长 $\eta$ 。

3.算法过程

1）确定当前位置的损失函数梯度，对于 $\theta_i$ 其梯度表达式如下：

$\frac{\partial}{\partial{\theta_i}} J(\theta_0,\theta_1,...,\theta_n)$ ，也可直接对损失函数在 $\theta_i$ 处进行一阶泰勒展开。

2)步长乘损失函数梯度，得到当前位置下降的距离，即 $\theta_i=\theta_i-\eta \frac{\partial}{\partial{\theta_i}} J(\theta_0,\theta_1,...,\theta_n)$

3)确定是否所有 $\theta$ 梯度下降距离都小于 $\varepsilon$ ，如果小于则算法终止，当前所有 $\theta$ 即为最终结果，否则进入步骤4

4)更新所有 $\theta$ ，对 $\theta_i$ 其更新表达式如下，更新完毕继续转入步骤1

$\theta_i^{k+1}\leftarrow \theta_i^k-\eta \frac{\partial}{\partial{\theta_i^k}} J(\theta_0^k,\theta_1^k,...,\theta_n^k)$

向量表示为

$\theta_i^{k+1}\leftarrow \theta_i^k-\eta G_k$

SGD(随机梯度下降算法)

现在随机梯度下降算法一般指小批量梯度下降法(mini-batch gradient descent)

采用小批量样本更新 $\theta$ ，选择n个训练样本（n<m，m为总训练集样本数），在这n个样本中进行n次迭代，每次使用1个样本，对n次迭代得出的n个gradient进行加权平均再并求和，作为这一次mini-batch下降梯度。

梯度下降算法与其他无约束优化算法比较

与最小二乘相比，梯度下降法迭代求解，最小二乘法计算解析解，样本小且存在解析解则最小二乘法比梯度下降更有优势，计算速度快，样本大则需要解一个超大的逆矩阵，难解且耗时。

与牛顿法相比，两者均为迭代求解，梯度下降法是梯度求解，牛顿法用二阶梯度或海森矩阵的逆矩阵或伪逆矩阵求解。牛顿法收敛更快但每次迭代时间比梯度下降法长。

牛顿法

牛顿法和梯度下降法示意图如下：

左图为梯度下降法，右图为牛顿法

由上图可知牛顿法每次迭代希望找到 $\theta_i$ 处切线与横轴的交点，即为所求的更新值

在 $\theta_i^k$ 处对损失函数进行二阶泰勒展开

$J(\theta) = J(\theta^k)+G_k^T(\theta-\theta^k)+\frac{1}{2} (\theta-\theta^k)^T(\theta-\theta^k)H(\theta^k)$

其中一阶导 $G_k^T$ 对应雅可比矩阵，二阶导 $H(\theta^k)$ 对应海森矩阵

$G_0^T = \begin{bmatrix} \frac{\partial f_1}{\partial x_1} & ... &\frac{\partial f_1}{\partial x_n} \\ ... & ...& ....\\ \frac{\partial f_m}{\partial x_1} & ... &\frac{\partial f_m}{\partial x_n}\end{bmatrix}\quad$ $H = \begin{bmatrix} \frac{\partial^2 f}{\partial x_1^2} & \frac{\partial^2 f}{\partial x_1\partial x_2}&... &\frac{\partial^2 f}{\partial x_1\partial x_n} \\ \frac{\partial^2 f}{\partial x_2\partial x_1}& ...& ....&...\\ ...&...&...&...\\\frac{\partial^2 f}{\partial x_n\partial x_1} & ... &...& \frac{\partial^2 f}{\partial x_n^2}\end{bmatrix}\quad$