【强化学习的数学原理】第六课：随即近似与随机梯度下降_rm算法 随机近似

【例子】

问题：如何计算均值$\bar{x}$

回答：

• 第一种方法：
  $$\mathbb{E}[X]\approx \bar{x}:=\frac{1}{N}\sum _{i=1}^N{x}_i$$
  问题：需要等，将所有数据收集到一起后再求平均

• 第二种方法：增量式与迭代式的方法

  $w_{k+1}和$$w_k$分别表示前$k+1$个求平均和前$k$个求平均
  w k + 1 = 1 k ∑ i = 1 k x i , k = 1 , 2 , … w k = 1 k − 1 ∑ i = 1 k − 1 x i , k = 2 , 3 , …

  $$\begin{aligned} & w_{k+1}=\frac{1}{k} \sum_{i=1}^k x_i, \quad k=1,2, \ldots \\ & w_k=\frac{1}{k-1} \sum_{i=1}^{k-1} x_i, \quad k=2,3, \ldots \end{aligned}$$ ​wk+1​=k1​i=1∑k​xi​,k=1,2,…wk​=k−11​i=1∑k−1​xi​,k=2,3,…​
  我们发现前$k+1$个求平均和前$k$个求平均是有关系的：
  $$\begin{array}{rl}{w}_{k+1}=\frac{1}{k}\sum _{i=1}^k{x}_i& =\frac{1}{k}\left(\sum _{i=1}^{k-1}{x}_i+x_k\right)=\frac{1}{k}\left((k-1)w_k+x_k\right)=w_k-\frac{1}{k}\left(w_k-x_k\right).\\ & w_{k+1}=w_k-\frac{1}{k}\left(w_k-x_k\right).\end{array}$$
  例子验证：发现可以表征，我们就得到了一个求平均数的迭代式的算法
  $$\begin{array}{rl}{w}_1& =x_1,\\ w_2& =w_1-\frac{1}{1}\left(w_1-x_1\right)=x_1,\\ w_3& =w_2-\frac{1}{2}\left(w_2-x_2\right)=x_1-\frac{1}{2}\left(x_1-x_2\right)=\frac{1}{2}\left(x_1+x_2\right),\\ w_4& =w_3-\frac{1}{3}\left(w_3-x_3\right)=\frac{1}{3}\left(x_1+x_2+x_3\right),\\ ⋮& \\ w_{k+1}& =\frac{1}{k}\sum _{i=1}^k{x}_i.\end{array}$$

【Robbins-Monro算法（RM算法）】

Stochastic approximation(SA 随机近似)：

• 代表了一大类随机迭代的算法，涉及到对随机变量的采用，主要用于方程求解和优化问题
• 它不需要方程或目标函数的表达式

Robbins-Monro算法（RM算法）

• 属于Stochastic approximation领域
• 随机梯度下降方法式该方法的一种情况

求解的问题：
$$g(w)=0$$

• 很多问题可以用这个来进行表征，比如优化问题 $g(w)={\nabla }_{w}J(w)=0$
• 加入我们要求$g(w)=c$，我们可以将其转变为$g(w)-c=0$这样的问题

计算过程：

• 第一种情况：$g$ 的表达式知道
• 第二种情况：$g$ 的表达式不知道（类似于神经网络）

✨RM算法：

$$w_{k+1}=w_k-a_k\tilde{g}\left(w_k,{\eta }_k\right),k=1,2,3,\dots$$

• $w_k$：是对$w^{\ast }$第$k$次的观测
• $\tilde{g}\left(w_k,{\eta }_k\right)=g\left(w_k\right)+{\eta }_k$ 是第$k$次的带噪音观察
• $a_k$：是常数

这个里面中$g(w)$是个黑盒，输入 { w k } \left\{w_k\right\} {wk​}，输出 { g ~ ( w k , η k ) } \left\{\tilde{g}\left(w_k, \eta_k\right)\right\} {g~​(wk​,ηk​)}

✨RM算法例子：

$$g(w)=\tanh (w-1)=0$$

参数：$w_1=3,a_k=1/k,{\eta }_k\equiv 0$

RM算法：$w_{k+1}=w_k-a_{k}g\left(w_s\right)$

仿真结果：

我们发现$w_{k+1}$ 更接近于 $w^{\ast }$ 相比于 $w_k$，因为$w_{k+1}=w_k-a_{k}g\left(w_k\right)<w_k$，所以$w_{k+1}$比$w_k$小更接近$w\ast$

【随机梯度下降】

✨解决的优化问题：

$$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]$$

• $w$：是最优的参数
• $X$：随机变量

✨解决方法1：gradient descent (GD) 梯度下降

$$w_{k+1}=w_k-{\alpha }_k{\nabla }_w\mathbb{E}\left[f\left(w_k,X\right)\right]=w_k-{\alpha }_k\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]$$

• ${\alpha }_k$：步长表示快还是慢下降
• $\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]==J(w)$

问题：对期望求梯度如何计算：

• 有模型对模型求梯度
• 没有模型，用数据求也就是方法2

✨解决方法2：batch gradient descent (BGD)梯度下降

E [ ∇ w f ( w k , X ) ] ≈ 1 n ∑ i = 1 n ∇ w f ( w k , x i ) w k + 1 = w k − α k 1 n ∑ i = 1 n ∇ w f ( w k , x i ) .

$$\begin{aligned} & \mathbb{E}\left[\nabla_w f\left(w_k, X\right)\right] \approx \frac{1}{n} \sum_{i=1}^n \nabla_w f\left(w_k, x_i\right) \\ & w_{k+1}=w_k-\alpha_k \frac{1}{n} \sum_{i=1}^n \nabla_w f\left(w_k, x_i\right) . \end{aligned}$$ ​E[∇w​f(wk​,X)]≈n1​i=1∑n​∇w​f(wk​,xi​)wk+1​=wk​−αk​n1​i=1∑n​∇w​f(wk​,xi​).​

问题：在每一次更新采样k的时候都要采集n次

✨解决方法3：stochastic gradient descent (SGD)梯度下降

$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f\left(w_k,x_k\right),$$

• 相比GD：替换真梯度 $\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]$ 为随机梯度 ${\nabla }_{w}f\left(w_k,x_k\right)$
• 相比BGD：将n=1

✨例子：

$$\underset{w}{\min }J(w)=\mathbb{E}[f(w,X)]=\mathbb{E}\left[\frac{1}{2}\Vert w-X{\Vert }^2\right],$$

其中：$f(w,X)=\Vert w-X{\Vert }^2/2{\nabla }_{w}f(w,X)=w-X$

【问题1】：最优解是否是 $w^{\ast }=\mathbb{E}[X]$？
∇ w J ( w ) = 0 ⇒ E [ ∇ w f ( w , X ) ⏟ w − x ] = 0 ⇒ E [ w − x ] = 0 ⇒ w = E [ x ]

$$\begin{gathered} \nabla_w J(w)=0 \Rightarrow E[\underbrace{\nabla_w f(w, X)}_{w-x}]=0 \Rightarrow E[w-x]=0 \Rightarrow w=E[x] \end{gathered}$$ ∇w​J(w)=0⇒E[w−x ∇w​f(w,X)​​]=0⇒E[w−x]=0⇒w=E[x]​
【问题2】：写出解决次问题的GD算法
$$\begin{array}{rl}{w}_{k+1}& =w_k-{\alpha }_k{\nabla }_{w}J\left(w_k\right)\\ & =w_k-{\alpha }_k\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]\\ & =w_k-{\alpha }_k\mathbb{E}\left[w_k-X\right]\end{array}$$
【问题3】：写出解决此问题的SGD算法
$$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f\left(w_k,x_k\right)=w_k-{\alpha }_k\left(w_k-x_k\right)$$

✨SGD算法的收敛性：

w k + 1 = w k − α k E [ ∇ w f ( w k , X ) ] ⇓ w k + 1 = w k − α k ∇ w f ( w k , x k )

$$\begin{gathered} w_{k+1}=w_k-\alpha_k \mathbb{E}\left[\nabla_w f\left(w_k, X\right)\right] \\ \Downarrow \\ w_{k+1}=w_k-\alpha_k \nabla_w f\left(w_k, x_k\right) \end{gathered}$$ wk+1​=wk​−αk​E[∇w​f(wk​,X)]⇓wk+1​=wk​−αk​∇w​f(wk​,xk​)​

从随机梯度来的，由于模型不知道所以通过随机采样来近似E，这个采样叫随机梯度，前面的叫真实梯度
$${\nabla }_{w}f\left(w_k,x_k\right)=\mathbb{E}\left[{\nabla }_{w}f(w,X)\right]+\underset{\eta }{\underbrace{{\nabla }_{w}f\left(w_k,x_k\right)-\mathbb{E}\left[{\nabla }_{w}f(w,X)\right]}}$$
由于是用随机梯度来近似真实梯度所以不准确的存在误差 $\eta$

问题：由于${\nabla }_{w}f\left(w_k,x_k\right)\ne \mathbb{E}\left[{\nabla }_{w}f(w,X)\right]$，所以使用SGD是否当$k\to \infty$ 时 $w_k\to w^{\ast }$ ?

回答：由于SGD是特殊的RM算法，那么前面RM算法的收敛性就可以应用到SGD的收敛性当中

✨SGD算法收敛行为：

问题：随机梯度是个随机的，逼近会不会不准确，SGD收敛是慢还是随机的

回答：
$${\delta }_k\doteq \frac{\left|{\nabla }_{w}f\left(w_k,x_k\right)-\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]\right|}{\left|\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]\right|}$$

• 分子为差的绝对值

由于$\mathbb{E}\left[{\nabla }_{w}f\left(w^{\ast },X\right)\right]=0$，我们将上面的式子进行修正为：
$${\delta }_k=\frac{\left|{\nabla }_{w}f\left(w_k,x_k\right)-\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]\right|}{\left|\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]-\mathbb{E}\left[{\nabla }_{w}f\left(w^{\ast },X\right)\right]\right|}=\frac{\left|{\nabla }_{w}f\left(w_k,x_k\right)-\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]\right|}{\left|\mathbb{E}\left[{\nabla }_w^{2}f\left({\tilde{w}}_k,X\right)\left(w_k-w^{\ast }\right)\right]\right|}$$
其中左边的式子将上面的带了进去，右边的式子对左边的式子使用中值定理进行化简，我们假设其中${\nabla }_w^{2}f\ge c>0$，对于所有的$w,X$
∣ E [ ∇ w 2 f ( w ~ k , X ) ( w k − w ∗ ) ] ∣ = ∣ E [ ∇ w 2 f ( w ~ k , X ) ] ( w k − w ∗ ) ∣ = ∣ E [ ∇ w 2 f ( w ~ k , X ) ] ∣ ∣ ( w k − w ∗ ) ∣ ≥ c ∣ w k − w ∗ ∣

$$\begin{aligned} \left|\mathbb{E}\left[\nabla_w^2 f\left(\tilde{w}_k, X\right)\left(w_k-w^*\right)\right]\right| & =\left|\mathbb{E}\left[\nabla_w^2 f\left(\tilde{w}_k, X\right)\right]\left(w_k-w^*\right)\right| \\ & =\left|\mathbb{E}\left[\nabla_w^2 f\left(\tilde{w}_k, X\right)\right]\right|\left|\left(w_k-w^*\right)\right| \geq c\left|w_k-w^*\right| \end{aligned}$$ ​E[∇w2​f(w~k​,X)(wk​−w∗)] ​​= ​E[∇w2​f(w~k​,X)](wk​−w∗) ​= ​E[∇w2​f(w~k​,X)] ​∣(wk​−w∗)∣≥c∣wk​−w∗∣​
将其分母进行带入得到：
$${\delta }_k\le \frac{\left|{\nabla }_{w}f\left(w_k,x_k\right)-\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]\right|}{c\left|w_k-w^{\ast }\right|}$$
我们再来分析这个式子：
$${\delta }_k\le \frac{|\stackrel{\text{stochastic gradient }}{\overbrace{{\nabla }_{w}f\left(w_k,x_k\right)}}-\stackrel{\text{true gradient }}{\overbrace{\mathbb{E}\left[{\nabla }_{w}f\left(w_k,X\right)\right]}}|}{\underset{\text{distance to the optimal solution }}{\underbrace{c\left|w_k-w^{\ast }\right|}}}.$$

• 分子是它的绝对误差
• 分母是$w_k$距离$w^{\ast }$的距离
• 当$w_k$距离$w^{\ast }$非常远的时候，SGD的行为和普通的梯度下降类似，

✨SGD收敛例子：

假设我们有20x20的范围，其最终收敛效果如下所示：

【BGD，MBGD，SGD】

目标函数：$J(w)=\mathbb{E}[f(w,X)]$ 随机变量： { x i } i = 1 n \left\{x_i\right\}_{i=1}^n {xi​}i=1n​
w k + 1 = w k − α k 1 n ∑ i = 1 n ∇ w f ( w k , x i ) , ( B G D ) w k + 1 = w k − α k 1 m ∑ j ∈ I k ∇ w f ( w k , x j ) , ( M B G D ) w k + 1 = w k − α k ∇ w f ( w k , x k ) . ( S G D )

$$\begin{aligned} & w_{k+1}=w_k-\alpha_k \frac{1}{n} \sum_{i=1}^n \nabla_w f\left(w_k, x_i\right),&(BGD) \\ & w_{k+1}=w_k-\alpha_k \frac{1}{m} \sum_{j \in \mathcal{I}_k} \nabla_w f\left(w_k, x_j\right), &(MBGD)\\ & w_{k+1}=w_k-\alpha_k \nabla_w f\left(w_k, x_k\right) .&(SGD) \end{aligned}$$ ​wk+1​=wk​−αk​n1​i=1∑n​∇w​f(wk​,xi​),wk+1​=wk​−αk​m1​j∈Ik​∑​∇w​f(wk​,xj​),wk+1​=wk​−αk​∇w​f(wk​,xk​).​(BGD)(MBGD)(SGD)​

• BGD：用到所有的采用在其基础上求平均
• MBGD：用到一组上随机抽取的采样求平均
• SGD：在其实随机采样一个求随机梯度

✨BGD，MBGD，SGD比较

MBGD囊括了BGD和SGD，当比较小的时候接近SGD，当比较大的时候接近BGD

如果m=1，MBGD是SGD

如果m=n，MBGD不等于BGD，MBGD是在所以采样时随机抽取可能抽不到

【总结】

• Mean estimation：使用一组数 { x k } \left\{x_k\right\} {xk​}来求平均$\mathbb{E}[X]$
  $$w_{k+1}=w_k-\frac{1}{k}\left(w_k-x_k\right).$$

• RM 迭代：用含有噪音的测量进行估计 { g ~ ( w k , η k ) 1 } \left\{\tilde{g}\left(w_k, \eta_k\right)_1\right\} {g~​(wk​,ηk​)1​}，$g(w)=0$
  $$w_{k+1}=w_k-a_k\tilde{g}\left(w_k,{\eta }_k\right)$$

• SGD迭代：利用梯度采样 { ∇ w f ( w k , x k ) } \left\{\nabla_w f\left(w_k, x_k\right)\right\} {∇w​f(wk​,xk​)}求解$J(w)=\mathbb{E}[f(w,X)]$
  $$w_{k+1}=w_k-{\alpha }_k{\nabla }_{w}f\left(w_k,x_k\right)$$