目录
Robbins-Monro algorithm
迭代式求平均数的算法
\(Stochastic \; approximation \;(SA)\)：是指随机迭代的一类算法,进行求解方程或者优化的问题,\(SA\)的优势是不需要知道方程或目标函数的表达式,自然也不知道导数、梯度之类的信息.
\(R0bbin-Monro \; algorithm\)
- 是\(stochastic \; approximation(SA)\)领域具有开创性的工作
- 大名鼎鼎的\(stochastic \; gradient \; descent\)是\(RM\)算法的一种特殊情况
下面看一个求解方程问题
\[g(w)=0, where \; w \in \mathbb{R} \; is \; the \; variable \; to \; be \; solved ,g \; is \;\mathbb{R} \rightarrow \mathbb{R} \; function \]- 如果\(g\)的表达式已知,那么就有很多种算法可以求解
- 另一种是表达式未知的情况，就比如神经网络,这样的问题就可以用RM算法求解
下面就看一下RM算法如何解决上面的问题
我们的目标是求解\(g(w)=0,\)最优解\(w^*\)
\[w_{k+1}=w_k-a_k\tilde{g}(w_k,\eta),k=1,2,3,... \]- \(w_k\)是对方程根的第\(k\)次估计
- \(\tilde{g}(w_k,\eta)=g(w_k)+\eta_k\)，\(\tilde{g}\)是对\(g\)的一个有噪音观测，\(\eta_k\)是一个噪音
- \(a_k\)是一个正系数
函数\(g(w)\)就是作为一个黑盒\((black \; box)\)，这个算法求解依赖于数据\(data\)
- \(input \;sequence:{w_k}\)
- \(Noisy \; output \; sequence:{\tilde{g}(w_k,\eta_k)}\)
下面是关于\(RM\)算法收敛性的一些数学解释
下面看如何把\(RM\)算法应用到\(mean \; estimation\)里面
\[\mathbb{E}_n = \frac{\sum_{i=1}^nx_i}{n}=\frac{\sum_{i=1}^{n-1}x_i+x_n}{n}=\frac{(n-1)\mathbb{E_{n-1}} + x_n}{n}=\mathbb{E}_{n-1}+\frac{x_n-\mathbb{E}_{n-1}}{n} \]这是最开始介绍的\(mean \; estimation\)
\[w_{k+1} = w_k + \alpha(x_k-w_k) \]当时\(\alpha=\frac{1}{k}\)，最开始当\(\alpha=\frac{1}{k}\)时，可以显示的写出\(w_{k+1}=\frac{1}{k}\sum_{i=1}^{k}x_i\),但当\(\alpha \neq \frac{1}{k}\)时,当时无法分析\(w_{k+1}\)的收敛性，根据\(RM\)算法可以知如果这个\(mean \; estimation\)是一种特殊的\(RM\)算法，那么\(w_{k+1}\)就会收敛
下面就看一下这个\(mean \; estimation\)是不是一个\(RM\)算法
考虑这样一个函数\(g(w)=w-\mathbb{E}[X]\),我们的目标是求\(g(w)=0\)，如果能解决这个问题，就能得到\(\mathbb{E}[X]\)
\(\mathbb{E}[X]\)显示我们是不知道的（也是我们想要去求解的），但是我们可以对\(X\)进行采样也就是可以获得\(\tilde{g}(w,x)=w-x\)
\(\tilde{g}(w,\eta)=w-x=w-x+\mathbb{E}[X]-\mathbb{E}[X]=(w-\mathbb{E}[X])+(\mathbb{E}[X]-x)=g(w)+\eta\)
相对应的\(RM\)算法
\[w_{k+1}=w_k-\alpha_k\tilde{g}(w_k, \eta_k)=w_k-\alpha_k(w_k-x_k) \]上面的这个式子就是所给出的\(mean \; estimation\)的算法
Stochastic gradient descent
\(SGD\)算法主要是去解决优化问题
\[\min_w J(w)=\mathbb{E}[f(w,X)] \]- \(w\)是一个待优化的参数
- \(X\)是一个随机变量,期望\((expection)\)是对\(X\)求的
求解这个问题下面给出3种方法，这三种方法是逐渐递进的
\(Method \; 1:gradient \; descent(GD) \; 梯度下降\)
如果要最大化一个函数可以用梯度上升
\[w_{k+1}=w_k-\alpha_k\nabla_w\mathbb{E}[f(w_k, X)]=w_k-\alpha_k\mathbb{E}[\nabla_wf(w_k,X)] \]- \(\alpha_k\)被称为步长，是用来控制在梯度方向下降的快还是慢的
- 这里要对梯度求期望，我们就需要模型或者数据两者其中之一
\(Method \; 2:batch \;gradient \; descent(BGD) \; 批量梯度下降\)
\[\mathbb{E}[\nabla_wf(w_k,X)] \approx \frac{1}{n}\sum_{i=1}{n}\nabla f(w_k,x_i) \]\[w_k+1=w_k-\alpha_k \frac{1}{n}\sum_{i=1}{n}\nabla f(w_k,x_i) \]这个其实就是我们之前学习的蒙特卡洛的思想,思想比较简单，但是缺点是在每次更新\(w_k\)时，都需要采样很多次
\(Method \; 3:stochastic \;gradient \; descent(SGD) \; 随机梯度下降\)
\[w_{k+1}=w_k-\alpha_k\nabla_wf(w_k,x_k) \]注意\(GD\)公式中的\(X\)变成了对\(X\)的一次采样\(x_k\)
- 在\(GD\)中用的是\(true \; gradient \; \mathbb{E}[\nabla_wf(w_k,X)]\)，但是这个真正的梯度是不知道的，所以就用一个\(stochastic \; gradient \; \nabla_w f(w_k, x_k)\)来代替,，之所以被称为\(stochastic\)是因为这里面有一个对\(X\)随机的采样
- 和\(BGD\)相比，\(SGD\)就是把\(BGD\)中的\(n\)变成了\(1\)
下面是一个用\(SGD\)优化的例子
\[\min_w J(w)=\mathbb{E}[f(w,X)]=E\left[ \frac{1}{2}\mid\mid \mid w - X \mid \mid^2 \right] \]\[where \; f(w,X)=\frac{1}{2}\mid\mid \mid w - X \mid \mid^2 \quad \nabla f(w,X)=w-X \]这个问题的解\(w^* =\mathbb{E}[X]\)
下面是推导：
我们知道\(J(w)\)要达到最小值，有一个必要条件,就是对\(J(w)\)求梯度应该等于\(0\),也就是
\[\nabla J(w) = \nabla \mathbb{E}[f(w,X)]= \mathbb{E}[\nabla f(w,X)]=\mathbb{E}[w-X]=w-\mathbb{E}[X]=0 \]于是
\[w^*=\mathbb{E}[X] \]\(GD算法：\)
\[\begin{align} w_{k+1} &= w_k - \alpha_k \nabla_w J(w_k) \\ &= w_k - \alpha_k \mathbb{E}[\nabla_wf(w_k,X)] \\ &= w_k - \alpha_k\mathbb{E}[w_k-X] \end{align} \]\(SGD算法：\)
\[w_{k+1}=w_k-\alpha_k \nabla_wf(w_k,x_k)=w_k-\alpha (w_k - x_k) \]从\(GD\)到\(SGD\)
\[w_{k+1}=w_k-\alpha_k \mathbb{E}[\nabla_wf(w_k),X] \]\[w_{k+1}=w_k-\alpha_k \nabla_wf(w_k),x_k \]直接用\(stochastic \; gradient\)去近似\(true \; gradient\)
既然是近似两者之间存在有误差,那么两者之间的关系如下
\[\nabla_w f(w_k,x_k) = \mathbb{E}[\nabla_w f(w,X)] +\nabla_w f(w_k,x_k) - \mathbb{E}[\nabla_wf(w,X)] \]\[\nabla_w f(w_k,x_k) \neq \mathbb{E}[\nabla_w f(w,X)] \]那么\(SGD\)能否找到最优解呢？也就是\(SGD算法\)能否收敛
可以通过证明\(SGD算法\)是\(RM算法\)解决这个问题
于是我们可以用\(RM\)算法的收敛性来分析\(SGD\)算法的收敛性
结论：当\(w_k\)和\(w^*\)距离比较远时，\(SGD\)和\(GD\)的行为是比较类似的
BGD、MBGD、 and SGD
可以认为\(MBGD\)包括了\(SGD\)和\(BGD\)
当\(mini-batch\)为\(1\)的时候就变成了\(SGD\)
当\(mini-batch\)比较大的时候就变成了\(BGD\)
相比于\(SGD\),\(MBGD\)的随机性比较小，因为用了更多的数据去代替一个数据.
相比于\(BGD\),\(MBGD\)的随机性会比较大，需要的数据又比较少，效率和性能是比较高的.
Summary
- \(mean \; estimation：\)使用一组数\({x_k}\)计算\(\mathbb{E}[X]\)，\(w_{k+1} = w_k + \frac{1}{k}(w_k-x_k)\)
- \(RM算法\)：\(solve \; g(w)=0 \; using \; {\tilde{g}(w_k,\eta_k)}\)，\(w_k{k+1}=w_k-a_k{\tilde{g}(w_k,\eta_k)}\)
- \(SGD算法：minimize \; J(w)=\mathbb{E}[f(w_k, X)]，using \; {\nabla_wf(w_k,x_k)}, \; w_{k+1}=w_k-\alpha_k \nabla_w f(w_k, x_k)\)