随机梯度下降

随机梯度下降（stochastic gradient descent, SGD）处理形如 $F(\theta )=\frac{1}{n}\sum _{i=1}^n{\ell }_i(\theta )$ 的目标：每次随机抽取一条样本，用这一项的梯度更新参数，而不等全部 $n$ 条样本的梯度算完。它的收益是每次更新便宜，代价是更新方向有抽样噪声。与梯度下降中“沿整个目标的梯度走一步”相比，随机性改变了轨迹，也改变了收敛解释。

两条数据的完整一轮

用无截距直线 $\hat{y}=\theta x$ 拟合两条教学数据 $(x_1,y_1)=(1,1)$、$(x_2,y_2)=(2,2)$。单条样本的平方损失取 ${\ell }_i(\theta )=\frac{1}{2}(\theta x_i-y_i{)}^2$，所以 $${{\ell }_i}^{\prime }(\theta )=(\theta x_i-y_i)x_i,F^{\prime }(\theta )=\frac{{{\ell }_1}^{\prime }(\theta )+{{\ell }_2}^{\prime }(\theta )}{2}.$$ 从 ${\theta }_0=0$ 出发，步长 $\alpha =0.1$。若本轮先抽到样本 1，梯度为 $(0\cdot 1-1)\cdot 1=-1$，更新成 ${\theta }_1=0.1$。接着用样本 2，梯度是在新参数上算的：$(0.1\cdot 2-2)\cdot 2=-3.6$，于是 ${\theta }_2=0.1-0.1(-3.6)=0.46$。如果起点直接用全量梯度，$F^{\prime }(0)=(-1-4)/2=-2.5$，只走一步得到 $0.25$。两种结果不可直接当成同样计算量的一步来比较；SGD 已经更新了两次。

随机方向的条件

若在给定当前参数 $\theta$ 后，从 $1,\dots ,n$ 均匀且独立地抽取索引 $I$，则 $$𝔼[{{\ell }_I}^{\prime }(\theta )\mid \theta ]=\frac{1}{n}\sum _{i=1}^n{{\ell }_i}^{\prime }(\theta )=F^{\prime }(\theta ).$$ 这就是随机梯度在该条件下“无偏”的准确含义：许多次抽样的平均方向等于全量方向，不是每一步都降低 $F$。上例如果先取第二条、后取第一条，得到 ${\theta }_1=0.4,{\theta }_2=0.46$，一轮结果仍为 $0.46$。这是因为两条样本各自都在 $\theta =1$ 处达到最小：两次更新把误差 $\theta -1$ 分别乘以 $0.9$ 和 $0.6$，乘法次序不影响结果。若两条样本偏好的参数不同，更新顺序通常会改变一轮终点。若根据样本难度偏向抽样却不按抽样概率重新加权，上述期望等式也会失效。

每次独立抽取 $b$ 条样本并平均其梯度，称小批量梯度下降。固定 $\theta$ 时，若单条梯度方差有限且抽样独立，平均梯度的方差是单条的 $1/b$；批量越大方向通常越稳定，但每次更新需要更多计算。从有限数据中不放回地洗牌，单步的边际平均仍可解释，但连续步骤并不独立，不能机械套用这个方差式。

顺序确实会影响一般问题。把两条损失改成 ${\ell }_1(\theta )=\frac{1}{2}(\theta -1{)}^2$ 与 ${\ell }_2(\theta )=\frac{1}{2}(\theta +1{)}^2$，仍从零出发且步长为 $0.1$。先取第一条，位置 $0\to 0.1\to -0.01$；先取第二条，位置 $0\to -0.1\to 0.01$。两种顺序末点不同，尽管全量目标的最优点都在零。小批量方差公式也可直接复核：若独立单样本梯度的方差为 ${\sigma }^2$，则 $b$ 个梯度平均值的方差为 $b{\sigma }^2/b^2={\sigma }^2/b$，独立性正是中间等号需要的条件。

Python 3 实现

下面的函数每轮可选择洗牌，示例关闭洗牌以重现上面的两步。输入为等长、非空的数值序列；返回最后的参数和每次更新后的历史，不改写输入序列。损失按 $\frac{1}{2}(\theta x_i-y_i{)}^2$ 定义。

Python 3

import random


def sgd_one_parameter(xs, ys, theta=0.0, rate=0.1,
                      epochs=1, shuffle=True, seed=0):
    if not (len(xs) == len(ys)) or not xs:
        raise ValueError("xs and ys must be nonempty and equally long")
    if rate <= 0 or epochs < 0:
        raise ValueError("rate must be positive; epochs nonnegative")
    order = list(range(len(xs)))
    rng = random.Random(seed)
    history = []
    for _ in range(epochs):
        if shuffle:
            rng.shuffle(order)
        for i in order:
            gradient = (theta * xs[i] - ys[i]) * xs[i]
            theta -= rate * gradient
            history.append(theta)
    return theta, history


if __name__ == "__main__":
    answer, steps = sgd_one_parameter([1, 2], [1, 2],
                                      shuffle=False)
    assert all(abs(a - b) < 1e-12
               for a, b in zip(steps, [0.1, 0.46]))
    assert abs(answer - 0.46) < 1e-12

本实现每条样本只含一个特征，运行 $E$ 轮、每轮 $n$ 次更新，时间为 $O(En)$；索引顺序和历史分别占 $O(n)$ 与 $O(En)$ 空间。若只需最终参数，可以去掉历史，把额外空间降到 $O(n)$。固定步长可能使参数在最优点附近继续摆动；减小步长或使用合适的衰减计划可以改善收敛，但步长太小又会令学习很慢。数据不是独立同分布、损失非凸或梯度异常大时，需要更谨慎地检查训练轨迹与验证误差。

参考资料

• Google Machine Learning Crash Course：Hyperparameters，说明单样本与小批量更新及噪声。
• MIT 6.7220 第15讲《Stochastic Gradient Descent》，讨论无偏梯度估计、小批量与迭代。