引言

本节将介绍随机梯度下降$\text{(Stochastic Gradient Descent,SGD)}$

回顾：梯度下降法

从最速下降法的角度观察，下降方向${\mathcal{P}}_k$的判定逻辑是：满足目标函数$f(x_{k+1})=f(x_k+{\alpha }_k\cdot {\mathcal{P}}_k)$的一阶泰勒展开式与$f(x_k)$之间存在严格的单调性；
其中$\mathcal{O}(\Vert {\alpha }_k{\mathcal{P}}_k\Vert )$表示关于${\alpha }_k{\mathcal{P}}_k$的高阶无穷小;
f ( x k + 1 ) − f ( x k ) = α k ⋅ ( P k ) T ∇ f ( x k ) + O ( ∥ α k P k ∥ ) ≈ α k ⋅ ( P k ) T ∇ f ( x k ) < 0 ⇒ ( P k ) T ∇ f ( x k ) < 0 f(xk+1)−f(xk)=αk⋅(Pk)T∇f(xk)+O(‖αkPk‖)≈αk⋅(Pk)T∇f(xk)<0⇒(Pk)T∇f(xk)<0

由于$\cos \theta \in [-1,1]$，因而当 θ = π 2 θ=π2

• 其中最左侧的是欧式范数$\Vert \mathcal{P}{\Vert }_2\le ϵ$,可以看出，特征空间原点到范数边界的距离均相等，这使得上式唯一的可变信息取决于$\theta$的取值；
• 中间与右侧分别是${\mathcal{L}}_1$范数$\Vert \mathcal{P}{\Vert }_1\le ϵ$与矩阵$2$-范数$\Vert \mathcal{A}{\Vert }_2\le ϵ$,可以看出：由于特征空间原点到范数边界之间的距离可能不相等，这使得上式的可变信息取决于$\theta$、范数长度的共同作用,最终可能导致:某方向即便不是负梯度方向，但它有可能使$({\mathcal{P}}_k{)}^T\nabla f(x_k)$达到最小。
  

梯度下降法在机器学习中的问题

在本节中，这里暂时模糊掉最速下降法与梯度下降法之间的区别。在无约束优化问题——最速下降法以及梯度下降法在强凸函数的收敛性分析中介绍过，如：

• 梯度下降法收敛速度慢，即便目标函数是强凸函数最快也仅能达到线性收敛；
• $\text{Hessian Matrix}\Rightarrow {\nabla }^{2}f(\cdot )$以及条件数$(\text{Condition Number})$对收敛速度的影响。当条件数越大时，收敛速度随之减缓，极限时可退化至次线性收敛；
• 关于收敛方向：可能出现$\text{ZigZag}$现象。底层原因在于：每次迭代过程，负梯度方向只是当前迭代步骤的最优解；再宽泛一点：负梯度方向只是某迭代位置小范围内的局部最优解。
• 不具备二次终止性：在凸二次函数的凸优化问题，仅通过有限次迭代步骤，无法收敛至最优解。

在机器学习过程中，梯度下降法的时间复杂度同样不低。例如：

• 已知数据集 D = { x ( i ) , y ( i ) } i = 1 N \mathcal D = \{x^{(i)},y^{(i)}\}_{i=1}^N D={x(i),y(i)}i=1N​，使用极大似然估计作为目标函数进行描述，具体表示为：
  其中$\mathcal{L}(\cdot )$表示关于样本的损失函数;而$\mathcal{J}(\cdot )$才是最终的目标函数结果。
  $$\{\begin{array}{l}\mathcal{L}[x^{(i)},y^{(i)};\theta ]=-\log \mathcal{P}(y^{(i)}\mid x^{(i)};\theta )\\ \\ \begin{array}{rl}\mathcal{J}(\theta )& ={\mathbb{E}}_{(x^{(i)},y^{(i)})\in \mathcal{D}}\mathcal{L}[x^{(i)},y^{(i)};\theta ]\\ & =\frac{1}{N}\sum _{i=1}^N-\log \mathcal{P}(y^{(i)}\mid x^{(i)};\theta )\end{array}\end{array}$$
• 对目标函数$\mathcal{J}(\theta )$使用梯度下降法进行运算：
  牛顿-莱布尼兹公式~
  $$\begin{array}{rl}{\nabla }_{\theta }\mathcal{J}(\theta )& ={\nabla }_{\theta }\left[\frac{1}{N}\sum _{i=1}^N-\log \mathcal{P}(y^{(i)}\mid x^{(i)};\theta )\right]\\ & =\frac{1}{N}\sum _{i=1}^N{\nabla }_{\theta }\left[-\log \mathcal{P}(y^{(i)}\mid x^{(i)};\theta )\right]\end{array}$$
  很明显，可以发现：需要对每一个样本的目标函数结果对参数$\theta$计算梯度。该公式计算的时间复杂度为$\mathcal{O}(N)$，其中$N$表示数据集内样本数量。
• 但样本数量自身同样也是不可忽视的重要条件。机器学习反复出现的一个问题是：好的泛化需要大的训练集，但大的训练集的计算代价也很大。
  上述红色部分抄自《深度学习(花书)》$P_{94}$下端。

这明显出现了矛盾：既然想要降低梯度下降法的时间复杂度，就需要减少训练集样本数量$N$；但训练集样本数量的减少，也会导致该数据集对概率模型的泛化效果较差。

随机梯度下降

随机梯度下降方法的思想

随机梯度下降的核心在于，目标函数的梯度${\nabla }_{\theta }\mathcal{J}(\theta )$自身同样也是期望：
∇ θ J ( θ ) = 1 N ∑ i = 1 N ∇ θ [ − log ⁡ P ( y ( i ) ∣ x ( i ) ; θ ) ] = E ( x ( i ) , y ( i ) ) ∈ D [ − log ⁡ P ( y ( i ) ∣ x ( i ) ; θ ) ] ∇θJ(θ)=1NN∑i=1∇θ[−logP(y(i)∣x(i);θ)]=E(x(i),y(i))∈D[−logP(y(i)∣x(i);θ)]

随机梯度下降方法的步骤描述

关于随机梯度下降在第$k$个训练迭代的更新步骤表示如下：

初始化步骤：学习率${ϵ}_k$；初始参数$\theta$；

迭代过程：

• 事先判断准则是否满足条件(如目标函数结果小于某阈值$\delta$)$?$是，则算法终止；
• 从训练集$\mathcal{D}$中采出包含$m$个样本的小批量，记作${\mathcal{D}}^{\prime }$：
  $${\mathcal{D}}^{\prime }=\{(x^{(j)},y^{(j)}){\}}_{j=1}^m$$
• 针对该小批量的梯度$\mathcal{G}$进行估计：
  其中$f(\cdot )$则表示模型，那么$f(x^{(j)};\theta )$则表示模型关于$x^{(i)}$预测结果。
  $$\begin{array}{rl}\mathcal{G}& \Leftarrow {\mathbb{E}}_{(x^{(j)},y^{(j)})\in {\mathcal{D}}^{\prime }}\left[{\nabla }_{\theta }\mathcal{L}[f(x^{(j)};\theta ),y^{(j)}]\right]\\ & =\frac{1}{m}\sum _{j=1}^m{\nabla }_{\theta }\mathcal{L}[f(x^{(j)};\theta ),y^{(j)}]\end{array}$$
• 对参数$\theta$进行更新：
  $$\theta \Leftarrow \theta -ϵ\cdot \mathcal{G}$$
• 返回步骤$1$重新进行判断，直到算法终止为止。

关于学习率

一般情况下，随机梯度下降算法使用使用固定的学习率，在真实迭代过程中：有必要随着迭代步骤的推移逐渐降低学习率。我们记第$k$次迭代步骤的学习率结果为${ϵ}_k$；在实践过程中，给定初始学习率${ϵ}_0$，学习率衰减的迭代次数$\tau$；衰减系数$\alpha$，第$k$次迭代步骤的学习率${ϵ}_k$可表示为：
在该公式中，迭代步骤$k<\tau$；
$${ϵ}_k=(1-\alpha ){ϵ}_0+\alpha \cdot {ϵ}_{\tau }\alpha =\frac{k}{\tau }$$
这样得到学习率的效果是：在$\tau$次迭代步骤之前，学习率会呈现线性衰减；当迭代步骤$k>\tau$时，学习率呈现稳定状态。