强化学习-随机近似与随机梯度下降

强化学习-数学理论

1. 强化学习-基本概念
2. 强化学习-贝尔曼公式
3. 强化学习-贝尔曼最优公式
4. 强化学习-值迭代与策略迭代
5. 强化学习-蒙特卡洛方法
6. 强化学习-随机近似于随机梯度下降

一、前言

  本篇博客主要包含如下内容：1️⃣ 新的角度再看mean eatimation；2️⃣ Robbins-Monro Algorithm；3️⃣ 随机梯度下降以及它的各种变体（GD、BGD、SGD、MBGD）。

二、再谈mean eatimation

2.1 回顾蒙特卡洛法

  上一篇蒙特卡洛章节关于mean eatimation problem是这么求解的：$\mathbb{E}[X]\approx \overline{x}:=\frac{1}{N}\underset{i=1}{\stackrel{N}{\Sigma }}{x}_i$，其含义是：抽样多个关于X的样本序列${x_i}_{i=1}^N$，然后对采样的数据进行求平均去最终去近似的等于$\mathbb{E}[X]$。这种方法有一个弊端，就是要等所有的采样数据都结束才能去计算均值，这无疑是不高效的。

2.2 新角度解决求均值问题

  基于上述的问题，本篇讲从一个新的角度再去求解mean eatimation problem。为了避免等待，我们采用增量式（迭代式）的方式去求解，即来几个先求几个的方式进行计算。推理过程如下所示：

假设：$w_{k+1}=\frac{1}{k}\underset{i=1}{\stackrel{k}{\Sigma }}{x}_i,k=\mathrm{1.2.3...}$
那么，$w_k=\frac{1}{k-1}\underset{i=1}{\stackrel{k-1}{\Sigma }}{x}_i,k=2,3,...$
然后，我们用$w_k$去表示$w_{k+1}$，可得：
$$\begin{array}{rl}{w}_{k+1}& =\frac{1}{k}\underset{i=1}{\stackrel{k}{\Sigma }}{x}_i\\ & =\frac{1}{k}(\underset{i=1}{\stackrel{k-1}{\Sigma }}{x}_i+x_k)\\ & =\frac{1}{k}((k-1)w_k+x_k)=w_k-\frac{1}{k}(w_k-x_k)\end{array}$$
最后，可以得到一个迭代的公式：$w_{k+1}=w_k-\frac{1}{k}(w_k-x_k)$，这样我们在计算第k步的时候就不需要等前面所有的$x_i$了，下面我们利用该等式求解mean eatimation problem，求解过程如下图所示：

2.3 新方法的优势及推广

  算法优势： 在计算第k步时，不需要把前面所有的$x_i$全部加起来再求平均，只需要通过一步的计算就可以得到一个新的正确的平均数。
  算法推广： $w_{k+1}=w_k-{\alpha }_k(w_k-x_k)，{\alpha }_k\ge 0$。

三、RM算法（Robbins-Monro Algorithm）

3.1 Stochastic Approximation的定义

  在本小节开始前，我们先说一下Stochastic approximation(SA)随机近似理论的定义，它代表了一类算法，是指使用随机迭代的算法去解决方程求解问题以及优化问题的这类算法。有很多的方法可以求解上述的问题，但SA算法的优点在于：它不需要知道这个方程或者是目标函数的表达式。

3.2 RM算法

  RM算法是SA的一个开创性的工作，下面进行详细的讲解：

问题定义：求解$g(w)=0$，假设$w^{\ast }$是方程 g 的最优解，注意这里的方程 g 的表达式我们是不知道，大家可以联想一下神经网络，即：我们给一系列的输出，中间过程是个网络结构，最后输出我们想要的值。
RM算法表达式：$w_{k+1}=w_k-a_k\tilde{g}(w_k,{\eta }_k),k=1，2，\mathrm{3...}$
这里的$w_k$表示的是对最优解$w^{\ast }$的第k次估计；$\tilde{g}(w_k,{\eta }_k)=g(w_k)+{\eta }_k，\eta 表示噪音$，$\tilde{g}$是g的一个带噪音的观测。$a_k$是一个系数。
RM算法求解方程的过程：输入 { w k } \{w_k\} {wk​}的一个序列，输出是一个含噪音的序列 { g ~ ( w k , η k ) } \{\tilde{g}(w_k,\eta_k)\} {g~​(wk​,ηk​)}

RM为什么能找到最优？这里用一个具体的例子来阐述，如下所示：

$g(w)=tanh(w-1)$，$g(w)=0$的解$w^{\ast }=1$，假设：$w_1=3，a_k=\frac{1}{k}，{\eta }_k=0(没有噪音)$。
那么RM算法的表达式为：$w_{k+1}=w_k-a_{k}g(w_k)$，求解过程仿真图如下所示：

由图示可得，$w_{k+1}$比$w_k$更接近最优解$w^{\ast }$。
当$w_k>w^{\ast }$，我们有$g(w_k)>0$。那么，$w_{k+1}=w_k-a_{k}g(w_k)<w_k$，因此$w_{k+1}$比$w_k$更接近$w^{\ast }$；
当$w_k<w^{\ast }$，我们有$g(w_k)<0$。那么，$w_{k+1}=w_k-a_{k}g(w_k)>w_k$，因此$w_{k+1}$比$w_k$更接近$w^{\ast }$；

3.3 RM算法收敛性分析数学理论（3个条件）

  RM算法成立的3个条件：


  这里只给出数学理论，感兴趣的朋友们可以直接去观看视频RM算法的数学理论支撑

3.4 RM算法求解mean eatimation

  问题描述：假如我们要估计某个随机变量的$\mathbb{E}[X]$，假设有一个方程$g(w)\stackrel{\cdot }{=}w-\mathbb{E}[X]$，那么我们只要找到一个$w$使得方程$g(w)=0$，这样我们就可以估计出这个随机变量X的$\mathbb{E}[X]$。注意：这里我们并不知道$g(w)$的表达式（上述等式只是一个用于显示化推理的假设），但我们可得到观测值，即：$\tilde{g}(w,x)\stackrel{\cdot }{=}w-x$。
  推导过程：

$$\begin{array}{rl}\tilde{g}(w,\eta )& =w-x\\ & =w-x+\mathbb{E}[X]-\mathbb{E}[X]\\ & =(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)\\ & \stackrel{\cdot }{=}g(w)+\eta \end{array}$$
因此我们可以通过 RM 算法来进行求解：
$w_{k+1}=w_k-{\alpha }_k\tilde{g}(w_k,{\eta }_k)=w_k-{\alpha }_k(w_k-x_k)$

四、Stochastic gradient descent（随机梯度下降）

4.1 SGD算法介绍

  SGD算法是RM算法的一个特殊情况，而mean estimation算法又是一个特殊的SGD算法。SGD算法解决的是一个优化问题，详细内容如下所示：

我们的目标是去求解优化问题，如方程：$\stackrel{min}{w}J(w)=\mathbb{E}[f(w,X)]$，这里的$w$是我们要优化的参数，$X$是一个随机变量，这里要求的也是关于$X$的期望，求解该问题我们有如下3种方法：
第一种：gradient descent（GD），该方法的使用条件是：已知了X的分布，换句话说就是知道了X的表达式。

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_w\mathbb{E}[f(w_k,X)]\\ & =w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]\end{array}$$

第二种：batch gradient descent（BGD），还是我们老生常谈的事情，没有模型要有数据，该方法使用的条件是：我有很多的数据采样，下面等式中的$x$表示$X$的采样，具体的计算如下所示：

假如我们有了：$$\mathbb{E}[{\nabla }_{w}f(w_k,X)]\approx \frac{1}{n}\underset{i=1}{\stackrel{n}{E}}{\nabla }_{w}f(w_k,x_i)$$
借助蒙特卡洛（MC）的思想，我们就可以得到下述等式：
$$w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\underset{i=1}{\stackrel{n}{E}}{\nabla }_{w}f(w_k,x_i)$$

第三种：Stochastic gradient descent（SGD），第二种方案的缺点在于：我在每一次去更新$w_k$的时候，需要采样很多次才能够去计算，在实际中这算法是低效的。

SGD的计算公式：$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$
与GD的方法对比，这里使用随机梯度${\nabla }_{w}f(w_k,x_k)$去替代了真实的梯度$\mathbb{E}[{\nabla }_{w}f(x_k,X)]$

4.2 使用SGD求解（一个例子）

  这里有一个例子，我们需要求解该的优化问题：$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]=\mathbb{E}[\frac{1}{2}||w-X|{|}^2]$，这里的$f(w,X)=||w-X|{|}^2/2，{\nabla }_{w}f(w,X)=w-X$。

练习一：证明最优解是$w^{\ast }=\mathbb{E}[X]$。

$J(w)$最小的必要条件是${\nabla }_{w}J(w)=0$，根据这个条件以及上面的方程，我们可以到的如下的推理过程：
$$\begin{array}{rl}{\nabla }_{w}J(w)& ={\nabla }_w\mathbb{E}[\frac{1}{2}||w-X|{|}^2]\\ & =\mathbb{E}[{\nabla }_w\frac{1}{2}||w-X|{|}^2]\\ & =\mathbb{E}[w-X]\\ & =0\end{array}$$
由于$w$本身不是一个随机变量所以它的expectation就是它自己，因此，我们可以得到：$w=\mathbb{E}[X]$。
练习二：写出解决这个问题的GD算法。

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_{w}J(w_k)\\ & =w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]\\ & =w_k-{\alpha }_k\mathbb{E}[w_k-X]\end{array}$$
练习三：写出解决这个问题的SGD算法。

$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)\\ & =w_k-{\alpha }_k(w_k-x_k)\end{array}$$

4.3 SGD收敛性分析

  这里我们来分析SGD的一个收敛性，分析过程如下所示：

GD的算法表达式：$w_{k+1}=w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]$，而SGD算法表达式为：$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$。与GD的方法对比，这里使用随机梯度${\nabla }_{w}f(w_k,x_k)$去替代了真实的梯度$\mathbb{E}[{\nabla }_{w}f(x_k,X)]$
因此，就会存在一个误差$\eta$，那么随机梯度等于真实梯度加上一个误差，如下式所示：
$${\nabla }_{w}f(w_k,x_k)=\mathbb{E}f(w,X)+\underset{\eta }{\underbrace{{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(x,X)]}}$$
因为，随机梯度是不等于真实梯度的，因此，在这种情况下使用SGD是否能够找到那个最优解呢？即使用 SGD 时$w_k\to w^{\ast }ask\to \infty$ 是否成立。

  这里我们的基本思想是：证明SGD是一个特殊的RM算法，然后就可以根据RM算法的收敛性推断出SGD算法也是收敛的，具体过程如下：

SGD算法的目标是：最小化$J(w)=\mathbb{E}[f(w,X)]$，
而最小值问题，可以转化为求方程解的问题，即${\nabla }_{w}J(w)=\mathbb{E}[{\nabla }_{w}f(w,X)]=0$
此时，我们便可以参考RM算法，那么我们便可以得到下列等式：
$g(w)={\nabla }_{w}J(w)=\mathbb{E}[{\nabla }_{w}f(w,X)]=0$，
SGD的问题就变成了如何求解$g(w)=0$这个方程。
接着，我们可以得到观测值$\tilde{g}$的表达式：
$$\begin{array}{rl}\tilde{g}(w,\eta )& ={\nabla }_{w}f(w,x)\\ & =\underset{g(w)}{\underbrace{\mathbb{E}[{\nabla }_{w}f(w,X)]}}+\underset{\eta }{\underbrace{{\nabla }_{w}f(w,x)-\mathbb{E}[{\nabla }_{w}f(w,X)]}}\end{array}$$
因此，我们便可以使用RM算法来求解$g(w)=0$了，可得：
$$w_{k+1}=w_k-a_k\tilde{g}(w_k,{\eta }_k)=w_k-a_k{\nabla }_{w}f(w_k,x_k)$$
而上述等式就是SGD算法，因此可得SGD是一个特殊的RM算法，其收敛性自然随之而来，SGD的收敛性理论如下所示，这里不在证明，感兴趣的朋友们可以查阅相关资料。

4.4 SGD算法随机性分析

  问题：SGD它是把GD当中的ture gradient用stochastic gradient来代替，由于stochastic gradient是随机的，那会不会造成SGD的收敛性也存在较大的随机性？下面给出推理过程。

我们通过考虑两者之间的相对误差（relative error）来回答这个问题，下面给出ture gradient和stochastic gradient之间相对误差的计算等式：
$${\delta }_k\stackrel{\cdot }{=}\frac{|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]||}{|\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}$$
而，上面的等式可以被证明得到如下的等式的（这里不进行证明，只给出结论）：
$${\delta }_k\le \frac{|{\nabla }_{w}f(w_k,x_k)-\mathbb{E}[{\nabla }_{w}f(w_k,X)]|}{c|w_k-w^{\ast }|}$$
上面等式的含义是：${\delta }_k\le \frac{|stochasticgradient-truegradient|}{w_k与w^{\ast }之间的距离}$，因此我们就可以得到如下的结论：

  一个例子去看SGD算法的收敛情况。

4.4 BGD、MBGD、SGD

4.4.1 算法介绍

  假设我们有一个目标函数$J(w)=\mathbb{E}[f(w,X)]$，还有一组关于$X$的采样 { x i } i = 1 n \{x_i\}_{i=1}^n {xi​}i=1n​，我们要用这样的数据去优化目标函数，有三种解法如下所示：

BGD： $$w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\underset{i=1}{\stackrel{n}{\Sigma }}{\nabla }_{w}f(w_k,x_i)$$
MBGD：$$w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\underset{j\in I_k}{\stackrel{n}{\Sigma }}{\nabla }_{w}f(w_k,x_j)$$
SGD：$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$$

4.4.2 算法异同点

• BGD中的B指的是batch，BGD每次都要用到n个所有的采样，然后在这个基础上求平均。
• MBGD（mini-bath）的意思是我不用所有的采样，我将所有的采样分成$I$组，随机的从这$I$组中选取一组进行计算，然后在这一组数上进行求平均。
• SGD就很简单了，我从n个采样中随机采样一个出来。
• 注意：从MBGD等式入手，当$m=1$时，MBGD=SGD；当$m=n$时，MBGD$\ne$BGD，虽然此时MBGD和BGD都用到了n个采样，但BGD用的是所有的n个采样，而MBGD是在n个采样中随机抽取的，因此对于MBGD而言会存在有的采样没有被抽到的可能性。

总结

内容小结

• RM算法公式：$w_{k+1}=w_k-a_k\tilde{g}(w_k,{\eta }_k),k=1，2，\mathrm{3...}$
• GD算法公式：$w_{k+1}=w_k-{\alpha }_k\mathbb{E}[{\nabla }_{w}f(w_k,X)]$
• BGD算法公式： $w_{k+1}=w_k-{\alpha }_k\frac{1}{n}\underset{i=1}{\stackrel{n}{\Sigma }}{\nabla }_{w}f(w_k,x_i)$
• SGD算法公式：$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f(w_k,x_k)$
• MBGD算法公式：$$w_{k+1}=w_k-{\alpha }_k\frac{1}{m}\underset{j\in I_k}{\stackrel{n}{\Sigma }}{\nabla }_{w}f(w_k,x_j)$$

参考资料

1、随机近似与随机梯度下降视频讲解