浅谈随机梯度下降&小批量梯度下降

机器学习三要素

上次的报告中，我们介绍了一种用于求解模型参数的迭代算法——梯度下降法。首先我认为需要明确一点，即“梯度下降算法”在一个完整的统计学习流程中，属于什么？根据《统计学习方法》这本书，统计学习一般有三个要素，即模型、策略和算法（目前以笔者的浅见，统计学习和机器学习没有太大的差别）。

所谓模型，我们可以简单理解为数据的组织形式。换句话说，就是输入数据与输出数据之间可能存在的关系。机器学习的主要任务是预测任务，根据预测值的取值情况，我们可以分为“分类任务”（预测值是离散的），“回归任务”（预测值是连续的），“聚类任务”（预测值是空白的，对输入数据进行自动分组）。因此，我们分别可以提出相应的模型，即分类模型，回归模型和聚类模型。继续向下细分，分类模型有二分类模型，多分类模型；回归模型有线性回归，非线性回归模型；聚类模型还有Kmeans，DBSCAN等。当我们抛开这些术语，回到初始的情况，其实就是输入数据，经过某种机制的加工，得到了预测输出数据。这个加工数据的机制，就是所谓的模型。上次提到的一元线性回归模型，y=ax+b，其实就是“x”经过“ax+b”的处理，得到了“y”。

image.png

策略，可以简单理解为模型的评价标准。例如同样是1000组(x,y)的数据，我们选择什么样的模型更能表达它们之间的关系呢？线性模型y=ax+b，还是二次函数模型y=ax²+bx+c (a !=0)？这里，我们就要引入某种准则，对每种模型进行评价。通常，我们把损失函数作为我们的评价函数。常用的损失函数有0-1损失函数、平方损失函数、绝对损失函数，对数损失函数等等，在上次的分析报告中，我们使用的就是平方损失函数，也就是我们想要最小化的目标函数。显然，当模型中的参数取值不同，损失函数的值也不同。我们便可以通过损失函数的值，来衡量不同模型的优劣。这便是所谓的策略。当然，对于机器学习的模型而言，评价其能力的最重要的指标应该是它的泛化能力，也就是预测未知数据的能力，但归根到底，还是通过选择合适的损失函数或者策略函数，来量化这种能力。

image.png

最后，就是算法啦。无论是我们已经确定了某种模型，想要求解参数。亦或是我们希望比较两种或多种模型的优劣，我们都需要通过算法，去找到损失函数的全局最小值，以确定相关的参数，以及模型的最优拟合效果。对于参数的求解，就是算法需要做到的。所以说到这里，我们就知道算法的重要性了，即使你提出了好的模型和好的策略，但如果你找不到合适的算法去求解你的模型参数，那么你的模型就无法发挥功能，最终也只是一文不值。现在十分火热的神经网络模型，曾经一度处于低谷状态，就是因为当时没有找到合适的算法对模型进行求解。而它的复苏，也是源于某位数学家提出了“每层局部最优最终达到全局近似最优”的想法并取得了很不错的效果。上次提到的梯度下降算法，就是目前业界最为常用的机器学习优化算法之一。同时，经典梯度下降算法还衍生出一系列算法，例如随机梯度下降、小批量梯度下降、动量梯度下降法等等。此外，还有拉格朗日乘数法、Adam算法、牛顿法及相关延申、分治法及相关延申等等。启发式算法也是一类不错的算法，例如模拟退火、遗传算法、粒子群优化等等，针对某些问题也会有很不错的效果。

随机梯度下降

下面进入正题，随机梯度下降算法。显而易见，随机梯度算法是引入了随机性的梯度下降算法。如果理解了经典的梯度下降算法，随机梯度下降就很简单啦。

在经典的随机梯度下降算法中，我们的迭代下降公式是 $x_{t+1}=x_t-\alpha \nabla f(x_t)$ 以一元线性回归的目标函数 $\sum_{i=1}^n(ax_i+b-y_i)^2$ 为例，其梯度可以表达为 $(\frac{\partial g}{\partial a},\frac{\partial g}{\partial b})=(2\sum_{i=1}^nx_i(ax_i+b-y_i)\ , \ \ 2\sum_{i=1}^n(ax_i+b-y_i))$

显然我们可以看到，这里的梯度计算，使用了所有的样本数据。倘若我们的数据集有1000组数据，那就需要计算1000次才可以得到梯度，倘若数据集有1亿组数据，就需要计算一亿次，其时间复杂度是O(n)。当我们面对的样本数据较多时，毫无疑问，模型的求解，学习一次的过程是很浪费时间的。因此，我们可以在所有的样本数据中选择随机的一个实例，用这个实例所包含的数据计算我们的“梯度”。此时的梯度为 $(\frac{\partial g}{\partial a},\frac{\partial g}{\partial b})=(2x_i(ax_i+b-y_i)\ , \ \ 2(ax_i+b-y_i))$ 其中 $(x_i,y_i)$ 是一个随机选中的样本。

到了这里，可能会存在一定的疑问，因为对于 $\sum_{i=1}^n(ax_i+b-y_i)^2$ 这个目标函数，其梯度并不是 $(\frac{\partial g}{\partial a},\frac{\partial g}{\partial b})=(2x_i(ax_i+b-y_i)\ , \ \ 2(ax_i+b-y_i))$ 既然如此，这个方向还是不是可以使函数值下降的方向？只能说，对于一次迭代而言，不一定，但是站在宏观的角度去考虑，最后还是很有机会收敛到近似最优解的。

事实上，我们的目标函数可以写成 $\sum_{i=1}^nS(i),\ \ S(i)=(ax_i+b-y_i)^2$ 所以我们的梯度则是 $\sum_{i=1}^n \nabla S(i)$ 这个时候，我们的优化目标是所有样本的损失函数之和，所以在梯度下降时，自然而然是朝着使总的偏差缩小的方向去移动的。而对于随机梯度下降，我们每一步迭代的优化目标函数不是始终不变的，其变化的范围就是 $\{S(i),\ i=1,2,3...\}$ 在第 $i$ 步，我们随机地选中了 $S(i)$ 作为我们的优化目标，其梯度便是 $(\frac{\partial g}{\partial a},\frac{\partial g}{\partial b})=(2x_i(ax_i+b-y_i)\ , \ \ 2(ax_i+b-y_i))$ 而在第 $i+1$ 步，我们的优化目标可能就变成了 $min\ S(j)$ 此时，梯度也自然变成了 $(\frac{\partial g}{\partial a},\frac{\partial g}{\partial b})=(2x_j(ax_j+b-y_j)\ , \ \ 2(ax_j+b-y_j))$ 显然，随机梯度下降迭代过程中，我们考虑到下降方向并不是全局下降方向，而是使得某个随机选中的样本的损失函数下降的方向。在一步迭代中，这种局部样本的下降未必会导致全局损失的下降，但是当迭代次数足够的时候，绝大部分样本都会被考虑到，最终一步一步走向全局最优解。

所以，随机梯度下降相对于梯度下降而言，其根本区别在于每一步迭代时需要优化的目标函数不同。对于经典的梯度下降，其每一步的目标函数（损失函数）是一样的，即所有样本的（平均）损失函数之和。而对于随机梯度下降而言，其每一步的目标函数是被随机选中的某个样本的损失函数，并不是一直不变的。

下面这个视频可以直观的感受一下随机梯度下降。
简书好像看不到视频……那可以直接在我的知乎回答里看：

浅谈随机梯度下降&小批量梯度下降 - 小白的文章 - 知乎
https://zhuanlan.zhihu.com/p/277709879

上面的每个小球，我们可以将其理解为随机梯度下降过程中由于随机性而带来的迭代情况的分支。正是由于这种随机性的存在，每个球可以较为自由地选择其运动方向，有些就停在某个位置，有些则一路向下。当迭代的次数足够多时，总会有某个球的路径十分顺畅，最终到达全局最优解的附近。我们甚至可以猜测，随机梯度下降相对于经典梯度下降，其逃离局部最优的能力更强。因为一旦到达了某个样本的局部最优，随着目标函数的更换，很可能不再是另一个样本的局部最优，迭代就可以继续进行。

当然，随机梯度下降的缺点也是存在的，即它很可能无法收敛到全局最优解。什么是全局最优，是 $\sum_{i=1}^n(ax_i+b-y_i)^2$ 达到最小嘛？还是每一个 $S(i)$ 都无法继续下降？一般而言，前者可能更容易衡量一些，我们也更偏向于使用总体的最优作为全局最优，而非每一个样本的最优。而对于随机梯度下降，即使我们已经达到了总体全局最优，对于某些样本而言，其可能依然可以继续下降，所以一旦选中了这些样本，我们就要偏离全局最优点了。所以随机梯度下降最终的收敛性确实值得考虑。

但总的来说，随机梯度下降还是很不错的，特别是对于大样本的处理情况，每一次迭代中O(1)的计算开销无疑会轻松很多，至于最终的收敛问题，则要根据迭代次数，终止准则等进行一个衡量取舍啦。

代码基本上是差不多的，只是参数的选择上要多花时间调整了……

clear;clc;
load a1data.mat
a=[0;0];% 初始值，a(1)=a;   a(2)=b; y=ax+b
alpha=1e-5; %学习率 alpha
eps=1e-12; %终止准则 eps
[q,s,num]=SGD(a,x,y,alpha,eps); %q是最终的解，s的均方误差的变化向量，num是迭代次数
figure(1);
plot(1:length(s),s);
disp("迭代了"+num+"次"+"   收敛结果是"+q)
title("均方误差下降曲线")
xlabel("迭代次数")
ylabel("均方误差")
y1=q(1)*x+q(2);
figure(2);
plot(x,y,'or',x,y1,'b');

function [q,s,num,daa]=SGD(a,x,y,alpha,eps)
i=1; %迭代序号
s=1:10;  %MSE向量
num=0; %迭代次数
q=[inf;inf]; %返回结果的初值
daa=1:10; % 梯度对a的分量向量
while 1
    disp(i);
    ch=unidrnd(length(x));
    da=2*x(ch)*(a(1)*x(ch)+a(2)-y(ch));
    db=2*(a(1)*x(ch)+a(2)-y(ch));%梯度对b的分量
    a1=a-alpha*[da;db]; %迭代格式
    %disp(a1);
    num=i; 
    s(i)=sum((a1(1)*x+a1(2)-y).^2)/length(x); %计算MSE
    disp(s(i));
    if i>500 && abs(s(i)-s(i-1))<eps  %终止准则
        q=a1;
        break;
    end
    if i>200000000
        disp("迭代了20000次也没有收敛，停下来改一下最大迭代次数试试")
        break;
    end
    a=a1;
    daa(i)=da;
    i=i+1;
end
end

untitled1.png

由于一次只计算一个样本的损失函数，所以其迭代次数肯定更多啦。但是除以样本数目1000，其计算开销也就相当于经典梯度下降迭代了200次。而之前的梯度下降700多次才收敛。当然啦，经典梯度下降更加稳定，随机梯度下降的结果相对而言还是差了点。

image.png

最优结果：

image.png

确实有些差距，如果多花点时间调节参数，修改修改终止准则，结果应该会好些。

小批量梯度下降

我们现在了解了经典的梯度下降和随机梯度下降，并且知道其不同之处主要在于迭代过程中目标函数选择的不同。同时，我们知道经典梯度下降虽然稳定性比较强，但是大样本情况下迭代速度较慢；随机梯度下降虽然每一步迭代计算较快，但是其稳定性不太好，而且实际使用中，参数的调整往往更加麻烦。

所以，为了协调稳定性和速度，小批量梯度下降应运而生啦。其实很简单，小批量梯度下降法和前面两种梯度下降的主要区别就是每一步迭代过程中目标函数的选择不同。小批量梯度下降是从 $n$ 个样本中随机且不重复地选择 $m$ 个进行损失函数的求和 $\sum_{i=1}^m(ax_i+b-y_i)^2$ 并将其作为每一步迭代过程中的目标函数。此时，迭代公式中的梯度也就变成了 $(\frac{\partial g}{\partial a},\frac{\partial g}{\partial b})=(2\sum_{i=1}^mx_i(ax_i+b-y_i)\ , \ \ 2\sum_{i=1}^m(ax_i+b-y_i))$

显然，m=1时，小批量梯度下降就是随机梯度下降，m=n时，小批量梯度下降就是经典梯度下降。同时，我们也把经典的梯度下降方法称之为全批量梯度下降。这里的m一般称之为批量尺寸，其值的选择对于收敛的稳定性和速度有着较大的影响，也是一个技术活。

其他的也没什么好分析的了，基本上和随机梯度下降差不多。

以上。