课程内容回顾与随机梯度下降讲解

到目前为止，已介绍完课程的前两部分内容，现简单回顾：

1. 第一部分：给出了mean estimation（均值估计）的算法，通过迭代的方式去求一个expectation（期望）。
2. 第二部分：给出了rm算法，此算法想法简单且有用，第一部分介绍的均值估计算法实际上是rm算法的一个特殊情况。

接下来进入第三部分，讲解stochastic gradient descent（简称sgd，随机梯度下降）算法。该算法在强化学习以及很多机器学习领域有非常广泛的应用，十分重要。并且，前面介绍的rm算法中，sgd实际上是rm算法的一个特殊情况，同时，均值估计算法也是sgd的一个特殊情况，这三部分关系密切。

随机梯度下降算法

1. 算法要解决的问题：是一个优化问题。目标函数为$J$，是关于$w$（参数或变量）的函数，要优化$w$使目标函数达到最小。目标函数$J(w)=E[f(w,X)]$，其中$f$是关于$w$和随机变量$X$的函数，$X$的概率分布已给定但未知，目标是找到最优的$w$使目标函数最小。
2. 求解问题的三种方法：
   • gradient descent（梯度下降，简称gd）：因为目标是最小化目标函数，所以用梯度下降（若目标是最大化则用梯度上升）。假设最优解是$w^{\ast }$，在第$k$次对$w^{\ast }$有一个估计$w_k$（可能不准确），在$w_{k+1}$时改进$w_k$，公式为$w_{k+1}=w_k-{\alpha }_k\nabla E[f(w,X)]$，其中${\alpha }_k$为步长，控制在梯度方向下降的快慢。由于涉及expectation，梯度符号可以移到期望内部，即$\nabla E[f(w,X)]=E[\nabla f(w,X)]$ 。此算法简单，但问题是对梯度求expectation时，若没有模型，用数据难以求解。
   • batch gradient descent（批量梯度下降，简称bgd）：思路是对目标函数中随机变量进行采样（采$n$次），求平均值来近似expectation，这是蒙特卡罗方法的基本思想。将数据得到的平均值代入目标函数进行计算。但该算法的问题是在每次更新$w_k$时，都要采样很多次，实际中可能不可行。
   • stochastic gradient descent（随机梯度下降，简称sgd）：算法公式为$w_{k+1}=w_k-{\alpha }_k\nabla f(w_k,x_k)$，其中$x_k$是随机变量$X$的一个采样。
3. 三种方法比较：
   • 与gradient descent相比，gradient descent用的是真实的梯度$E[\nabla f(w,X)]$，但由于未知，所以用stochastic gradient descent中的$\nabla f(w_k,x_k)$来代替，因为有随机采样$x_k$在其中，所以称为随机梯度下降。
   • 与batch gradient descent相比，batch gradient descent中对随机变量采样多次（$n$次），采样越多对expectation估计越准，但需要很多数据；而随机梯度下降相当于把batch gradient descent中的采样次数$n$设为1，用一个数据来估计，其问题是估计不精确，但后续会详细分析随机梯度下降不精确的程度以及它能否解决最优化问题。