【最优化理论】4.1无约束最优化

  无约束最优化问题是机器学习中最普遍、最简单的优化问题。$x^*=\min _xf\left( x \right) ,x\in R^n$x∗=xmin​f(x),x∈Rn

1.梯度下降法

  损失函数计算等同于m次预测的结果和真实的结果之间的差的平方和。
$L\left( \hat{\omega} \right) =\frac{1}{2}\sum_{j=1}^m{\left( y_i-H_w\left( x_j \right) \right) ^2}=\frac{1}{2}\sum_{j=1}^m{\left( y_i-\hat{\omega}^Tx \right) ^2}$L(ω^)=21​j=1∑m​(yi​−Hw​(xj​))2=21​j=1∑m​(yi​−ω^Tx)2
线性回归的目的是寻找最佳的 $\omega _0,\omega _1,\cdots ,\omega _n$ω0​,ω1​,⋯,ωn​，使得损失函数$L\left( \hat{\omega} \right)$L(ω^)的值最小。寻找最优参数通常采用梯度下降法，该方法计算损失函数在当前点的梯度，然后沿负梯度方向(即损失函数值下降最快的方向)调整参数，通过多次迭代就可以找到使L(w)的值最小的参数。
  具体过程为，首先给定初始参数向量动，如随机向量，计算损失函数对的偏导(即梯度)，然后沿负梯度方向按照一定的步长(学习率)，调整参数的值，如下式，
$\hat{\omega}\gets \hat{\omega}-\eta \frac{\partial L\left( \hat{\omega} \right)}{\partial \hat{\omega}}$ω^←ω^−η∂ω^∂L(ω^)​
并进行迭代使更新后的$L\left( \hat{\omega} \right)$L(ω^))不断变小，直至找到使$L\left( \hat{\omega} \right)$L(ω^)最小的$\hat{\omega}$ω^值，从而得到合适的回归模型的参数。

2.随机梯度下降法

2.1批量梯度下降法（Batch Gradient Descent）

  批量梯度下降法，是梯度下降法最常用的形式，具体做法也就是在更新参数时使用所有的样本来进行更新。

$\theta_{i}=\theta_{i}-\alpha \sum_{j=1}^{m}\left(h_{\theta}\left(x_{0}^{(j)}, x_{1}^{(j)}, \ldots x_{n}^{(j)}\right)-y_{j}\right) x_{i}^{(j)}$θi​=θi​−αj=1∑m​(hθ​(x0(j)​,x1(j)​,…xn(j)​)−yj​)xi(j)​

2.2 随机梯度下降法（Stochastic Gradient Descent）

  随机梯度下降法，其实和批量梯度下降法原理类似，区别在与求梯度时没有用所有的m个样本的数据，而是仅仅选取一个样本j来求梯度。对应的更新公式是：
$\theta_{i}=\theta_{i}-\alpha\left(h_{\theta}\left(x_{0}^{(j)}, x_{1}^{(j)}, \ldots x_{n}^{(j)}\right)-y_{j}\right) x_{i}^{(j)}$θi​=θi​−α(hθ​(x0(j)​,x1(j)​,…xn(j)​)−yj​)xi(j)​
  随机梯度下降法，和2.1的批量梯度下降法是两个极端，一个采用所有数据来梯度下降，一个用一个样本来梯度下降。自然各自的优缺点都非常突出。对于训练速度来说，随机梯度下降法由于每次仅仅采用一个样本来迭代，训练速度很快，而批量梯度下降法在样本量很大的时候，训练速度不能让人满意。对于准确度来说，随机梯度下降法用于仅仅用一个样本决定梯度方向，导致解很有可能不是最优。对于收敛速度来说，由于随机梯度下降法一次迭代一个样本，导致迭代方向变化很大，不能很快的收敛到局部最优解。

2.3小批量梯度下降法（Mini-batch Gradient Descent）

  小批量梯度下降法是批量梯度下降法和随机梯度下降法的折衷，也就是对于m个样本，我们采用x个样子来迭代，1<x<m。一般可以取x=10，当然根据样本的数据，可以调整这个x的值。对应的更新公式是：
$\theta_{i}=\theta_{i}-\alpha \sum_{j=t}^{t+x-1}\left(h_{\theta}\left(x_{0}^{(j)}, x_{1}^{(j)}, \ldots x_{n}^{(j)}\right)-y_{j}\right) x_{i}^{(j)}$θi​=θi​−αj=t∑t+x−1​(hθ​(x0(j)​,x1(j)​,…xn(j)​)−yj​)xi(j)​

3.牛顿法

  并不是所有的方程都有求根公式，或者求根公式很复杂，导致求解困难。利用牛顿法，可以迭代求解。
求出函数$f(x)$f(x)切线方程，
$y-f\left( x_n \right) =f'\left( x_n \right) \left( x-x_n \right)$y−f(xn​)=f′(xn​)(x−xn​)令$y=0$y=0，得到：
$x_{n+1}=x_n-\frac{f'\left( x_n \right)}{f''\left( x_n \right)}$xn+1​=xn​−f′′(xn​)f′(xn​)​那么$x_{n+1}$xn+1​可认为是$f(x)=0$f(x)=0的近似根，通过不断的迭代，必然存在$x^*$x∗使得$f(x^*)=0$f(x∗)=0的时候收敛。

多维的情况为：$x_{n+1}=x_{n}-H^{-1} \nabla f\left(x_{n}\right)$xn+1​=xn​−H−1∇f(xn​)，其中$H$H为海塞矩阵。

缺点:牛顿法的收敛新依赖于初值$x_0$x0​的选择，如果初值$x_0$x0​离根$x^*$x∗比较远，则牛顿法可能发散。不能离最小值太远的地方拟合，要接近极小值再拟合收敛的效果越好。因此经常是先用梯度下降法，到了局部极小值附近后再用牛顿法。

4.牛顿法的收敛速度

$\left|x_{n}-x_{0}\right|\left|\left(x_{n}-\xi\right)\right| M<\left(x_{n}-x_{0}\right)^{2} M$∣xn​−x0​∣∣(xn​−ξ)∣M<(xn​−x0​)2M，由于M的分子分母都是导数，导数都是有界的，所以M是有界的，用$\overline M$M表示其上界。
$\left|x_{n}-x_{0}\right|\left|\left(x_{n}-\xi\right)\right| M<\left(x_{n}-x_{0}\right)^{2} M<\left(x_{n}-x_{0}\right)^{2} \bar{M}$∣xn​−x0​∣∣(xn​−ξ)∣M<(xn​−x0​)2M<(xn​−x0​)2Mˉ所以
$\left|x_{n+1}-x_{0}\right|<\left(x_{n}-x_{0}\right)^{2} \bar{M}$∣xn+1​−x0​∣<(xn​−x0​)2Mˉ当$x_n$xn​和$x_0$x0​的距离小于1：$(x_n-x_0)<1$(xn​−x0​)<1，则$\left( x_n-\text{x}_0 \right) \ll 1$(xn​−x0​)≪1 说明是按照平方的速度进行收敛的，注意这里有条件：$x_n$xn​和$x_0$x0​的距离小于1，如果距离大于1，上界会越来越大，发散。

参考

1.梯度下降（Gradient Descent）小结
2.梯度下降法、牛顿法和拟牛顿法