机器学习笔记1——常用优化算法1—GD、BGD、SCD、MBGD

1、梯度下降（Gradient Descent，GD）

梯度下降

梯度下降是最流行的优化算法之一并且目前为止是优化神经网络最常见的算法,具有实现简单的优点。

梯度下降是一种以通过在目标函数梯度 的反向上更新模型参数，来最小化模型参数的目标函数$J(\theta)$J(θ)的方法。

梯度

梯度实际上就是多变量微分的一般化。
下面这个例子：

我们可以看到，梯度就是分别对每个变量进行微分，然后用逗号分割开，梯度是用<>包括起来，说明梯度其实一个向量。

梯度是微积分中一个很重要的概念，

• 在单变量的函数中，梯度其实就是函数的微分，代表着函数在某个给定点的切线的斜率
• 在多变量函数中，梯度是一个向量，向量有方向，梯度的方向就指出了函数在给定点的上升最快的方向

梯度下降的思想：

开始时我们随机选择一个参数的组合，计算目标函数，然后我们寻找下一个能让目标函数值下降最多的参数组合。我们持续这么做直到找到一个局部最小值（local minimum），因为我们并没有尝试完所有的参数组合，所以不能确定我们得到的局部最小值是否便是全局最小值（global minimum），选择不同的初始参数组合，可能会找到不同的局部最小值。

梯度下降的直观理解：

梯度下降算法如下：

• 初始化参数$\Theta_j$Θj​

• 迭代，更新参数$\Theta_j$Θj​：

  $\Theta_j:=\Theta_j-\alpha\frac{\partial J(\Theta)}{\partial \Theta_j}$Θj​:=Θj​−α∂Θj​∂J(Θ)​

  其中，$J(\Theta)$J(Θ)为所求目标函数，$\Theta_j$Θj​为参数。

描述：对$\Theta$Θ更新，使得$J(\Theta)$J(Θ)按梯度下降最快方向进行，一直迭代下去，最终得到局部最小值。其中$\alpha$α是学习率（learning rate），它决定了我们沿着能让代价函数下降程度最大的方向向下迈出的步子有多大。

例子：如果目标函数$J(\Theta)$J(Θ)只有两个参数，如下图所示

参数$\Theta_1$Θ1​的更新：
如果导数即此点的斜率为负，负负得正，在原来的基础上增加。
如果导数即此点的斜率为正，负正得负，在原来的基础上减少。

增加或减少的程度不仅仅取决于导数，还取决于学习率$\alpha$α。

学习率$\alpha$α 对移动幅度的影响:

• 学习率$\alpha$α如果太小了，只能这样像小宝宝一样一点点地挪动，去努力接近最低点，这样就需要很多步才能到达最低点，所以如果太小的话，可能会很慢，达到收敛所需的迭代次数就会非常高。

• 学习率$\alpha$α如果太大，那么梯度下降法可能会越过最低点，甚至可能无法收敛，下一次迭代又移动了一大步，越过一次，又越过一次，一次次越过最低点，直到你发现实际上离最低点越来越远，所以，如果太大，它会导致无法收敛，甚至发散。
  

• 即使学习速率$\alpha$α保持不变时，梯度下降也可以收敛到局部最低点。因为如果你的参数已经处于局部最低点，也就是说导数为0，那么梯度下降法更新其实什么都没做，它不会改变参数的值。

因此，学习率$\alpha$α的选择也是很重要的。

$J(\Theta)$J(Θ)随着迭代次数的增加变化如下图

图1，2意味着模型应该选择较小的$\alpha$α值。

$\alpha$α值的尝试一般为0.001，0.003，0.01，0.03，0.1，0.3，1…

梯度下降算法的种类

有以下三种梯度下降，他们不同之处在于我们在计算目标函数梯度时所用数据量的多少。依据数据的规模，我们在更新参数的准确性和执行一次更新所用时间之间进行一种折中。

假设线性模型：

其中θ是参数。
损失函数为：

2、 批量梯度下降（Batch Gradient Descent，BGD）

BGD是最原始的形式也就是GD，它是指在每一次迭代使用所有样本(m个）求梯度并更新参数。

伪代码：

for i in range(nb_epochs):
  params_grad = evaluate_gradient(loss_function, data, params)
  params = params - learning_rate * params_grad

我们要不断重复这一步直到算法收敛，也就是参数不断更新，直到梯度为0。但是，我们的每次迭代更新，都要对所有的m个样本数据进行求和。

那么我们如何检测参数是否已经收敛了呢？一种是检验两次迭代，如果两次迭代中，是否改变了很多，如果在两次迭代中没怎么改变，我们或许就可以说算法有可能收敛了。另一种，更常用的方法是，检验的值，如果你试图最小化的量不再发生很大的改变时，你也许就可以认为它收敛了。

优点：

• 一次迭代是对所有样本进行计算，此时利用矩阵进行操作，实现了并行。
• 由全数据集确定的方向能够更好地代表样本总体，从而更准确地朝向极值所在的方向。当目标函数为凸函数时，BGD一定能够得到全局最优。

缺点：

• 当样本数目 m很大时，每迭代一步都需要对所有样本计算，训练过程会很慢。

那么，当我们遇到这样非常大的数据集的时候怎么办呢？我们应该使用另一种梯度下降算法——随机梯度算法。

3、随机梯度下降（Stochastic Gradient Descent，SGD）

SGD仅仅选取一个样本j来求梯度并更新参数。

伪代码：

for i in range(nb_epochs):
  np.random.shuffle(data)
  for example in data:
    params_grad = evaluate_gradient(loss_function, example, params)
    params = params - learning_rate * params_grad

随机梯度下降法不同于批量梯度下降，它的具体思路是：算法中对T参数$\Theta$Θ的每次更新不需要再全部遍历一次整个样本，只需要随机选择一个样本进行更新，之后再用下一个样本进行下一次更新，像批量梯度下降一样不断迭代更新。

随机梯度下降相当于在批量梯度下降的梯度上引入了随机噪声。

优点：

• 由于不是在全部训练数据上的损失函数，而是在每轮迭代中，随机优化某一条训练数据上的损失函数，这样每一轮参数的更新速度大大加快，收敛速度也非常快。
    
  缺点：
• 准确度下降。在非凸优化问题中，随机梯度下降更容易逃离局部最优点。
• 可能会收敛到局部最优，由于单个样本并不能代表全体样本的趋势。
• 无法充分利用计算机的并行计算能力

解释一下为什么SGD收敛速度比BGD要快：
  答：这里我们假设有30W个样本，对于BGD而言，每次迭代需要计算30W个样本才能对参数进行一次更新，需要求得最小值可能需要多次迭代（假设这里是10）；而对于SGD，每次更新参数只需要一个样本，因此若使用这30W个样本进行参数更新，则参数会被更新（迭代）30W次，而这期间，SGD就能保证能够收敛到一个合适的最小值上了。也就是说，在收敛时，BGD计算了 10×30W 次，而SGD只计算了 1×30W 次。

SGD算法的收敛图：

4、 小批量梯度下降（Mini-Batch Gradient Descent, MBGD）

小批量梯度下降法是批量梯度下降和随机梯度下降的折中。

MBGD随机选取一小部分训练样本j来求梯度并更新参数。

比如采取10个样本则参数的更新如下：

伪代码：

for i in range(nb_epochs):
  np.random.shuffle(data)
  for batch in get_batches(data, batch_size=10):#batch_size为选取的样本数量
    params_grad = evaluate_gradient(loss_function, batch, params)
    params = params - learning_rate * params_grad

优点：

• 通过矩阵运算，每次在一个batch上优化神经网络参数并不会比单个数据慢太多。

• 每次使用一个batch可以大大减小收敛所需要的迭代次数，同时可以使收敛到的结果更加接近梯度下降的效果。(比如上例中的30W，设置batch_size=100时，需要迭代3000次，远小于SGD的30W次)

• 可实现并行化。
    
  缺点：

• batch_size的不当选择可能会带来一些问题。

  batcha_size的选择带来的影响：

  • 在合理地范围内，增大batch_size的好处：
    a. 内存利用率提高了，大矩阵乘法的并行化效率提高。
    b. 跑完一次 epoch（全数据集）所需的迭代次数减少，对于相同数据量的处理速度进一步加快。
    c. 在一定范围内，一般来说 Batch_Size 越大，其确定的下降方向越准，引起训练震荡越小。
  • 盲目增大batch_size的坏处：
     a. 内存利用率提高了，但是内存容量可能撑不住了。
     b. 跑完一次 epoch（全数据集）所需的迭代次数减少，要想达到相同的精度，其所花费的时间大大增加了，从而对参数的修正也就显得更加缓慢。
    c. Batch_Size 增大到一定程度，其确定的下降方向已经基本不再变化。

下图显示了三种梯度下降算法的收敛过程：

参考资料：
https://ruder.io/optimizing-gradient-descent/index.html#shufflingandcurriculumlearning
机器学习课程

https://www.jianshu.com/p/c7e642877b0e