随机梯度下降
- 几乎所有的深度学习算法都用到了一个非常重要的算法：随机梯度下降（stochastic gradient descent,SGD)
- 随机梯度下降是梯度下降算法的一个扩展
机器学习中一个反复出现的问题：
好的泛化需要大的训练集，但是大的训练集的计算代价也更大
机器学习算法中的代价函数通常可以分解成每个样本的代价函数的总和。
训练数据的负条件对数似然函数可以写成：
\[
J(\theta)=E_{x,y}L(x,y,\theta)=\frac1m\sum_{i=1}^{m}L(x^{(i)},y^{(i)},\theta)
\]
其中\(L\)是每个样本的损失\(L(x,y,\theta)=-log\ p(y|x;\theta)\)
对于这些相加的代价函数，梯度下降需要计算
\[
\bigtriangledown_{\theta}J(\theta)=\frac1m\sum_{i=1}^{m}\bigtriangledown_{\theta}L(x^{(i)},y^{(i)},\theta)
\]
这个运算的计算代价是\(O(m)\)
随机梯度下降的核心：梯度是期望
期望可以使用小规模的样本近似估计
具体操作步骤
在算法的每一步，我们从训练样本集中均匀抽出一小批量（minibatch）样本\(B=\{x^{(1)},x^{(2)},x^{(3)},...,x^{(m^{'})}\}\)。小样本批量的数目\(m^{’}\)通常是一个相对较小的数，从一到几百。重要的是，当训练集大小\(m\)增长时，\(m^{’}\)通常是固定的。我们可能在拟合几十亿的样本时，每次更新计算只用到几百个样本。
梯度的估计可以表示成：
\[
g = \frac{1}{m^{'}}\sum_{i=1}^{m^{'}}\bigtriangledown_{\theta}L(x^{(i)},y^{(i)},\theta)
\]
使用来自小批量\(B\)的样本。然后，随机梯度下降算法使用如下的梯度下降估计：
\[
\theta \leftarrow \theta-\varepsilon g
\]
其中，\(\varepsilon\)是学习率。
梯度下降往往被认为很慢或不可靠。以前，将梯度下降应用到非凸优化问题被认为很鲁莽或没有原则。优化算法不一定能保证在合理的时间内达到一个局部最小值，但它通常能及时地找到代价函数一个很小的值，并且是有用的。
随机梯度下降在深度学习之外有很多重要的应用。它是在大规模数据上训练大型线性模型的主要方法。对于规定大小的模型，每一步随机梯度下降更新的计算量不取决于训练集的大小\(m\)。在实践中，当训练集大小增长时，我们通常会随训练集规模增大而增加。然而，当m趋向于无穷大时，该模型最终会在随机梯度下降抽样完训练集上的所有样本之前收敛到可能的最优测试误差。继续增加\(m\)不会延长达到模型可能的最优测试误差的时间。从这点来看，我们可以认为用SGD训练模型的渐进代价是关于\(m\)的函数的\(O(1)\)级别。
在深度学习兴起之前，学习非线性模型的主要方法是结合核技巧的线性模型。很多核学习算法需要构建一个\(m\times m\)的矩阵\(G_{i,j}=k(x^{(i)},x^{(j)})\)。构建这个矩阵的计算量是\(O(m^2)\)。当数据集是几十亿个样本时，这个计算量是不能接受的。在学术界，深度学习从2006年开始受到关注的原因是，在数以万计样本的中等规模数据集上，深度学习在新样本上比当时很多热门算法泛化得更好。不久后，深度学习在工业界收到了更多的关注，因为其提供了一种训练大数据集上的非线性模型的可扩展方式。