机器学习中的最优化方法（一）——梯度下降法

机器学习 最优化方法 梯度下降法

---

  最优化方法是一种数学方法，它是研究在给定约束之下如何寻求某些因素（的量)，以使某一(或某些)指标达到最优的一些学科的总称。大部分的机器学习算法的本质都是建立优化模型，通过最优化方法对目标函数（或损失函数）进行优化，从而训练出最好的模型。常见的最优化方法有梯度下降法、牛顿法和拟牛顿法、共轭梯度法等等。

1 梯度下降法

  梯度下降法是最早、最简单、最常用的最优化方法。
  当目标函数是凸函数时，梯度下降法的解是全局解。
  凸函数是一个定义在某个向量空间的凸子集C（区间）上的实值函数f，而且对于凸子集C中任意两个向量，f((x1+x2)/2)≤(f(x1)+f(x2))/2,则f(x)是定义在凸子集c中的凸函数（该定义与凸规划中凸函数的定义是一致的，下凸）。判定方法可利用定义法、已知结论法以及函数的二阶导数。对于实数集上的凸函数，一般的判别方法是求它的二阶导数，如果其二阶导数在区间上非负，就称为凸函数（向下凸）。如果其二阶导数在区间上恒大于0，就称为严格凸函数。此外，可以通过分析目标函数的结构，就能在一些情况下判断函数是否是凸函数。下面给出一些结论：

• 指数函数是凸函数；
• 对数函数是凹函数，然后负对数函数就是凸函数；
• 对于一个凸函数进行仿射变换，可以理解为线性变换，结果还是凸函数；
• 二次函数是凸函数（二次项系数为正）；
• 高斯分布函数是凹函数；
• 多个凸函数的线性加权，如果权值是大于等于零的，那么整个加权结果函数是凸函数。

  梯度下降法优化思想：用当前位置负梯度方向作为搜索方向，因为该方向为当前位置的最快下降方向，所以也被称为是“最速下降法”。最速下降法越接近目标值，步长越小，前进越慢，即在接近最优解的区域收敛速度明显变慢，该方法需要很多次的迭代。

  在机器学习中，发展了两种梯度下降方法，分别为批量梯度下降法和随机梯度下降法。
  例：以线性回归（Linear Logistics）模型为例，假设下面的$h(\theta)$是要拟合的函数，$J(\theta)$为损失函数，$\theta$ 是参数，要迭代求解的值，$\theta$求解出来了那最终要拟合的函数$h(\theta)$就出来了。其中$m$是训练集的样本个数，$n$是特征的个数。

$$h(\theta)=\sum_{j=1}^n \theta_j x_j$$
$$J(\theta)=\frac{1}{2m}\sum_{i=1}^m (y^i-h_\theta(X^i))^2$$

1.1 批量梯度下降法（Batch Gradient Descent，BGD）

  （1）将$J(\theta)$对$\theta$求偏导，得到每个$theta$对应的的梯度：

$$\frac{\partial J(\theta)}{\partial \theta_j}=-\frac{1}{m}\sum_{i=1}^m (y^i-h_\theta(X^i))x_{j}^{i}$$
  （2）由于是要最小化风险函数，所以按每个参数theta的梯度负方向，来更新每个theta：
$$\theta_{j}^{'}=\theta+\frac{1}{m}\sum_{i=1}^m (y^i-h_\theta(X^i))x_{j}^{i}$$
  （3）从上面公式可以注意到，它得到的是一个全局最优解，但是每迭代一步，都要用到训练集所有的数据，如果m很大，那么可想而知这种方法的迭代速度会相当的慢。所以，这就引入了另外一种方法——随机梯度下降。

1.2 随机梯度下降法（Random Gradient Descent，RGD）

  RGD为对每个样本的损失函数，对$\theta$求偏导得到对应梯度，来更新$\theta$：
  即：

$$\theta_{j}^{'}=\theta+(y^i-h_\theta(X^i))x_{j}^{i}$$
  随机梯度下降是通过每个样本来迭代更新一次，如果样本量很大的情况（例如几十万），那么可能只用其中几万条或者几千条的样本，就已经将theta迭代到最优解了，对比上面的批量梯度下降，迭代一次需要用到十几万训练样本，一次迭代不可能最优，如果迭代10次的话就需要遍历训练样本10次。但是，SGD伴随的一个问题是噪音较BGD要多，使得SGD并不是每次迭代都向着整体最优化方向。
　　BGD和RGD两者的关系可以这样理解：随机梯度下降方法以损失很小的一部分精确度和增加一定数量的迭代次数为代价，换取了总体的优化效率的提升。增加的迭代次数远远小于样本的数量。

$\color{red}{总结}$

　　批量梯度下降---最小化所有训练样本的损失函数，使得最终求解的是全局的最优解，即求解的参数是使得风险函数最小，但是对于大规模样本问题效率低下。
　　随机梯度下降---最小化每条样本的损失函数，虽然不是每次迭代得到的损失函数都向着全局最优方向，但是大的整体的方向是向全局最优解的，最终的结果往往是在全局最优解附近，适用于大规模训练样本情况。
　　
参考：
https://blog.csdn.net/faith_binyang/article/details/78724632