强化学习——随机近似理论（六）

随机近似理论（Stochastic Approximation）

1 平均近似（Mean Estimation）

与 MC 的方法相同，对于独立同分布随机变量的期望，用采样值的平均值去近似。但是平均值的计算方法不再是所有样本相加后再求平均，而是对每一个采样都对这个近似值进行更新。
MC 的方法：$E(X) \approx \frac{1}{N} \displaystyle \sum_{i=1}^N x_i$
ME 的方法：$w_{k+1} = w_k - \frac{1}{k}(w_k - x_k),k \rightarrow \infty$

2 Robbin Monro Algorithm

这是随机近似理论的一种算法，在不知道方程$g(w)$形式的情况下，求解出$g(w) = 0$的根。
核心：$w_{k+1} = w_k - \alpha_k \tilde{g}(w_k,\eta_k),k \rightarrow \infty$
条件：1、$0<c_1 \le \nabla_w g(w) \le c_2$，该函数是单调递增的。
2、$\displaystyle \sum_k \alpha_k \rightarrow \infty,\displaystyle \sum_k \alpha_k^2 < \infty$
3、$E(\eta_k|{\cal H_k})=0,E(\eta_k^2|{\cal H_k})<\infty$
其中第二项条件保证了$\alpha$不会以很快的速度收敛到0，同时一定会收敛到0。

2.1 Mean Estimation 是 RM 算法的特殊情况

g(w) = w - E(X)\ \ w_{k+1} = w_k - \alpha_k \tilde{g}(w_k,\eta_k) = w_k- \alpha_k (w_k-x_k)

最后一项当$\alpha_k = \frac{1}{k}$就变成了 mean estimation。

3 随机梯度下降（Stochastic Gradient Descent）

RM 算法解决的是求根问题，而 SGD 解决优化问题，但本质是相通的。
问题：$\min J(w) = E[f(w,X)]$(X是随机变量)或者$\min J(w) = \frac{1}{n} \displaystyle \sum_{i=0}^{n} f(w,x_i)$（$x_i$是序列$\{x_i\}_{i=1}^n$的抽样，而且$\{x_i\}_{i=1}^n$符合均匀分布）
核心：$w_{k+1} = w_k - \alpha_k\nabla_{w_k} f(w_k,x_i)$
条件：1、$0<c_1 \le \nabla_w^2 f(w,X) \le c_2$，该函数是单调递增的。
2、$\displaystyle \sum_k \alpha_k \rightarrow \infty,\displaystyle \sum_k \alpha_k^2 < \infty$
3、$\{x_k\}_{k=1}^\infty$is iid.

3.1 SGD 与 RM 算法互通

$\min J(w) = E[f(w,X)]$可以转换成$g(w) = E[\nabla_w f(w,X)] = 0$
$\tilde{g}(w,\eta) = \nabla_w f(w,x) = E[\nabla_w f(w,X)] + (\nabla_w f(w,x) - E[\nabla_w f(w,X)])$
$w_{k+1} = w_k- \alpha_k \tilde{g}(w,\eta) = w_k- \alpha_k \nabla_{w_k} f(w_k,x_k)$，$x$是随机变量$X$的一次采样。
当$f(w,x) = \frac{1}{2}\Vert w-x \Vert^2$，就SGD变成了$w_{k+1} = w_k- \alpha_k(w_k - x_k)$

3.2 小批量梯度下降、随机梯度下降、批量梯度下降（MBGD、SGD、BGD）

MBGD：$w_{k+1} = w_k - \alpha_k \frac{1}{m} \sum_m \nabla_{w_k} f(w_k,x_i)$（在总共n个样本中再次随机采样m个）
SGD：$w_{k+1} = w_k - \alpha_k \nabla_{w_k} f(w_k,x_i)$（在总共n个样本中再次随机采样1个）
BGD：$w_{k+1} = w_k - \alpha_k \frac{1}{n} \sum_n \nabla_{w_k} f(w_k,x_i)$（总共n个样本中全部采用）