学习资料：bilibili 西湖大学赵世钰老师的【强化学习的数学原理】课程。链接：强化学习的数学原理 西湖大学 赵世钰

---

一、通过例子介绍 Iterative mean estimation

首先，先回顾一下 mean estimation problem 是什么。假设有一个随机变量X，目标是要求其期望 E(X)。我们有一些采样数据 $x_1,x_2,...,x_N$。期望可以用这N个采样值的平均来近似。

那么，该如何计算这N个采样值的平均呢？有两种方法。

第一种是先收集好所有的sample，再对这些sample求平均值。这种方法的缺陷是：所有的sample需要一段时间才能被采样完，所以需要等待一段时间。

第二种方法采用了增量式的思想。基本思路是：来几个sample，就先算几个sample。这样效率会高一些。

下面具体来看一看如何用增量式的思想来计算均值。对采样到的样本 $x_1,x_2,...,x_k$，先求一个均值 $w_{k+1}$。再对样本 $x_1,x_2,...,x_{k-1}$求均值，得到样本 $w_k$。通过推导发现 $w_{k+1}$ 和 $w_k$ 之间存在一定的关系（如下图蓝色公式所示）。利用这个式子，算均值就变得更加简单了。当得到一个新的采样 $x_k$ 时，不必再对 $x_1,x_2,...,x_k$ 求和从而求其均值，而是直接套蓝色的公式，在 $w_k$ 的基础上就可以得到 $w_{k+1}$ 了。

这样我们就得到了如下图所示的，一个求平均数的迭代式/增量式算法。该算法的优点是，在求平均数时，不需要从头开始把数据加起来计算。当x的样本比较少的时候，所得到的结果和期望相差较大，但当x的样本越来越多的时候，所得到的结果越来越接近期望值。

把上述公式继续进行泛化，把 $1/k$ 改成 ${\alpha }_k$。如果 ${\alpha }_k$ 能够满足一定的条件，计算所得到的结果 $w_{k+1}$ 仍然可以近似为X的期望。此外，该算法也是一种特殊的SA algorithm、一种特殊的SGD算法。

二、Robbins-Monro 算法介绍与例子

关于SA算法：

（1）SA算法（sochastic approximation algorithm）代表一类随机的、迭代的算法，会涉及到对随机变量的采样，
这类算法被用来进行方程求解，或进行优化问题。
（2）相比于其他方程求解方法、优化算法，SA 算法不需要知道方程/目标函数的表达式。

关于Robbins-Monro 算法：
（1）该算法是随机近似领域中一个非常重要的工作。
（2）随机梯度下降算法（SGD）是 Robbins-Monro 算法的一种特殊情况。
（3）上一节提到的mean estimation实际上也是一种特殊的 Robbins-Monro 算法。

问题陈述：假设我们要求解方程 $g(w)=0$，现在要求解该方程。为什么设计 $g(w)=0$这个例子呢？因为这个例子在不同场景中均能广泛地用到。比如在下面的优化场景中，如果要优化方程 $J(w)$，则需要计算 $J(w)$的梯度等于0的解。再比如要求 $g(w)=c$的解，可以把 $g(w)=c$转换成 $g(w)-c=0$ 的形式进行求解。

我们要解决的核心问题是：如何在不知道 $g(w)$ 表达式的情况下，求解方程 $g(w)=0$ 。 这其实相当于一个神经网络，比如神经网络的输入是w，输出是y，我们要做的就是在不知道函数 $g(w)$ 表达式的情况下，去求解/拟合这个函数 $g(w)$。

这种问题可以用RM算法来求解。我们的目标是求解 $g(w)=0$，最优解是 $w^{\ast }$。在迭代式算法中，$w_k$ 是对 $w^{\ast }$ 的第 k 次估计，$a_k$ 是一个系数，$\tilde{g}(w_k,{\eta }_k)=g(w_k)+{\eta }_k)$，其中${\eta }_k$是一个噪音。$\tilde{g}(w_k,{\eta }_k)$ 是g的一个带有噪音的观测。

在算法中，把 $g(w)$ 当做一个黑盒，依赖于数据（$w_k$ 序列和 $\tilde{g}(w_k,{\eta }_k)$ 序列）来求解。看下图红色手绘部分，每输入一个w就输出一个 $\tilde{g}$。一开始输入 $w_1$ 得到 ${\tilde{g}}_1$，然后计算出 $w_2$ ，输入 $w_2$得到 ${\tilde{g}}_2$……不断迭代下去。最后得到了一个序列 { $w_k$} 和序列 {${\tilde{g}}_1$}。RM算法就是采用这种思路求解的。

为什么RM算法能求出方程 $g(w)=0$ 的解？

要求解的方程是 $g(w)=tanh(w-1)=0$，方程的图像如下图所示，最大值和最小值分别逼近 $\pi /2$ 和 $-\pi /2$ ，函数最优解$w^{\ast }=1$。初始化假设 $w_1=3$，$a_k=1/k$，${\eta }_k=0$。

下图展示了函数的求解过程和结果。通过这个例子可以直观地看到， $w_{k+1}$ 总是比 $w_k$ 更接近 $w^{\ast }$。

三、Robbins-Monro 算法收敛性及应用

（1）RM算法的收敛性证明
下图给出了RM算法的收敛性证明，具体证明过程请见赵老师课程视频。这里我就跳过了。

（2） 把RM算法应用到 mean estimation 问题中
下图给出的是这节课第一节中讲到的 mean estimation 的式子，当时我们令 ${\alpha }_k=1/k$。当${\alpha }_k$不等于$1/k$的时候，实际上最后的结果仍然能够收敛到E(X)。现在我们可以通过证明该方法是一个特殊的RM算法，从而证明该方法的收敛性。

1）考虑要求解一个方程 $g(w)=w-E[X]$。我们不知道 $E[X]$ 具体是多少，但是我们有 $E[X]$ 的观测值 $x$。
2）我们不知道 $E[X]$ 具体是多少，但是我们有 $E[X]$ 的观测值 $x$。所以我们测量的是 $\tilde{g}(w,x)$，其中x是对X的一个采样。 $\tilde{g}(w,x)$ 可以进一步写成 $g(w)+\eta$。
3）把 $\tilde{g}(w,x)$ 的值代入进去，自然得到了结果。这个结果就是RM算法的形式。所以我们证明了证明该方法是一个特殊的RM算法，从而证明该方法的收敛性。

四、 随机梯度下降算法介绍

SGD要解决的问题是一个优化问题，优化目标函数$J(w)$使其达到最小。目标函数是关于函数$f$的expectation，$f$又是关于w和X的一个函数。w是参数，X是随机变量，所以我们的目标是求出一个w使得$J(w)$最小。

方法一：gradient descent (GD)
假设最优解是$w^{\ast }$，$w_k$是在第k次对$w^{\ast }$的估计，在第k+1次对$w^{\ast }$进行改进。$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}E[f(w_k,X)]=w_k-{\alpha }_k{\nabla }_{w}J(w)$。相当于对目标函数求梯度，沿着梯度的方向下降，来优化当前的解。但该方法也存在问题，即：期望值很难准确获取。

方法二：batch gradient descent (BGD)
因为期望很难求得，所以通过多次采样，用多次采样的结果来近似期望。但这种方法也存在问题，即：更新$w_k$时需要采样很多次，实际效率很低。

方法三：stochastic gradient descent (SGD)
在下式中，在梯度的计算过程中，使用了一个X的采样x来代替X。和BGD相比，BGD是采样n次，而SGD只采样1次。

五、随机梯度下降例子与收敛性

考虑对下面的式子进行优化，求其最小值。

使用梯度下降算法（GD）和随机梯度下降算法（SGD）解决上述问题的过程如下所示。在SGD中，用一个随机的采样来代替期望。

下面讨论SGD算法的收敛性。
从GD到SGD的过程，其实就是用 stochastic gradient 去近似 true gradient 的过程。但这两者之间肯定是存在一个误差的，用下图中的$\eta$来表示两者之间的误差（stochastic gradient = true gradient + error）。在这种情况下，用SGD是否能找到最优解呢？

分析的基本思想是，证明SGD是一个特殊的RM算法。如果得证，因为RM算法具有收敛性，所以SGD就自然收敛。可以把SGD的最小化问题转换成方程求解问题（如下图所示），因为$J(w)$达到最优的时候，一定是梯度等于0。所以，最小化问题被转换成求解梯度=0的问题。

根据前面所讲的，该方程可以用RM算法求解。目前我不知道$g(w)$的准确表达式，但我可以通过观测求得$\tilde{g}(w,\eta )$。这里的$\tilde{g}(w,\eta )$就是stochastic gradient，等于$g(w)$加上噪音$\eta$。经过一些推导，发现使用RM算法可以把这个问题推导成推成SGD的形式。所以，SGD是一个特殊的RM算法，SGD具有收敛性。

六、随机梯度下降的有趣性质

Question：既然stochastic gradient是随机的，因此它的估计是不准确的。那么这会不会导致SGD的收敛也是比较慢且随机的呢？（直白点说，就是我知道它能收敛到最优值，但是会不会绕了一大圈、或者走过完全相反的方向，最终才达到了最优）

用stochastic和batch gradient的relative error（相对误差）来分析问题。假设$w^{\ast }$是最优解，$w^{\ast }$代入到式子中的值就是0。因此可以把$w^{\ast }$代入到式子中，加入到relative error中。利用中值定理对式子进行转换。

假设f的二阶梯度一定是大于0的。在这个假设基础上，继续推导。

下面对求得的结果进一步分析。可得到下面的结论：
当$w_k$距离$w^{\ast }$比较远时，分母比较大，在分子大小有限的情况下，relative error比较小，SGD所呈现出来的行为和GD是非常类似的。
当$w_k$距离$w^{\ast }$比较近时，分母比较小，在分子大小有限的情况下，relative error比较大，此时SGD才会呈现出比较大的随机性。

另一个例子。
在二维平面上有一个以原点为中心，边长为20的正方形。在正方形中随机采样（取点），在采样的过程中运行之前讲的mean estimation 算法。观察算法的收敛过程是什么样的。

下面呈现了算法的收敛过程。左图里面那根红色的线是SGD的轨迹。可以发现：
（1）最开始的时候$w_k$距离$w^{\ast }$比较远，但SGD没有呈现出朝着随机方向收敛的样子，而是朝着目标的方向快速收敛，
（2）$w_k$距离$w^{\ast }$比较近，快要接近目标的时候，呈现出一些随机性。

A deterministic formulation.
下面针对一个新的目标函数来求解优化问题。其中 f 是关于 w 和 x 的参数。有很多x，需要对n个这样的值求平均。这个目标函数和之前的区别在于，这个目标函数中没有随机变量，x是一些给定的实数。所以，这是一个 deterministic formulation。

下图中的第一个公式使用了GD算法来解决这个问题。但是在实际情况中，有可能{$x_i$}集合非常大，所以每次从集合里取一个数来进行求解（如下图中第二个式子所示）。这种求解方法算是SGD吗？不算是，因为它不包含任何 random variables 或者 expected values。

下面就想一个办法，把随机变量引入到该问题的求解中，使其成为一个SGD。引入一个随机变量X，令 $p(X=x_i)=1/n$，取任何一个随机变量的概率都是 1/n 。所以目标函数可以被转换成一个求期望的函数。

七、随机梯度下降对比BGD、MBGD、SGD

1. 回顾一下BGD、MBGD、SGD
BGD 每次用到 n 个采样，然后在此基础上求平均。
MBGD (mini batch gradient descent) 不使用所有的采样，仅从 n 个采样中取 m 个样本进行计算。比如从一万个数中，选取一百个样本。
SGD 每次只用到1个采样。

2. 简单比较
比较：
（1）相比于SGD，MBGD的随机性更小，因为它用到的样本更多。
（2）相比于GD，MBGD的随机性更大，因为它用到的样本更少。但它的优势就在于高效、灵活。
（3）当m=1时，MBGD就变成了SGD。
（4）当m=n时，严格意义上来说，MBGD不完全是BGD。 因为虽然两者都用了n个采样，但BGD用了所有的n个样本，MBGD是在n个采样中随机抽取的，有可能某些样本被抽中了好几次，某些样本却一次也没被抽到。

3. 一个例子
下图呈现了要求解的目标问题。先对目标函数求梯度，令梯度等于0。


下图中，BGD直接求出了平均数；MBGD每次先在m个数中求平均，然后再求一次平均（k）；SGD每次只对一个数求平均。

下图是仿真的结果。发现mini batch=50时，MBGD能很快地接近目标；而mini batch=5时，MBGD接近目标的速度要慢一些。

八、本节课summary