[TOC]
https://www.bilibili.com/video/BV1sd4y167NS
以计算采样数据的平均数为例
- 采样大量数据，最后一次性计算平均值
- 采样一个算一次，迭代计算，手上的均值最终会趋向真实
我们采样第二种方法，记：
$$ w_{k+1} = \frac{1}{k}\sum_{i=1}^k x_i $$则：
$$ \begin{split} w_{k+1} &= \frac{1}{k}\sum_{i=1}^k x_i = \frac{1}{k}(\sum_{i=1}^{k-1}x_i+x_k)\\ &= \frac{1}{k}\left [ (k-1)w_k + x_k \right ] = w_k - \frac{1}{k}(w_k-x_k) \end{split} $$Robbins-Monro Algorithm
对于一个方程：
$$ g(w) = 0 $$我们希望求出解$w^$，使得$g(w^) = 0$
为了简化问题，$g(w)$是一个单调递增的函数
如果函数已知，我们可以通过牛顿迭代法求解
但是如果函数未知，我们通过采样：
$$ y_k = g(w_k) $$往往带有噪声：
$$ \widetilde{g}(w_k,\eta_k) = g(w_k) + \eta_k $$我们定义一个迭代过程：
$$ w_{k+1} = w_k - a_k\widetilde{g}(w_k,\eta_k) $$- 当$w_k>w^*$时，$g(w_k)>0$时
- $w_{k+1} = w_k - a_k\widetilde{g}(w_k,\eta_k) < w_k$
- 所以会往$w^*$走一步
- 当$w_k<w^*$时，$g(w_k)<0$时
- $w_{k+1} = w_k - a_k\widetilde{g}(w_k,\eta_k) > w_k$
- 所以会往$w^*$走一步
但其实这个非常理想，条件也比较苛刻，需要满足
-
$0<c_1\leq \nabla g(w)\leq c_2,\text{ for all } w$
- $c_1$保证函数单调递增，且必然存在0解
- $c_2$保证梯度有界，防止垂直
-
$\sum a_k = \infty, \sum a_k^2 < \infty$
-
促进探索：$a_k$是步长，若不趋近无穷，代表调整幅度与范围是有限的
-
抑制噪声：噪声的方差大致是$\sum a_k^2 \mathbb{E}\left| \eta_k^2\right |$，$\sum a_k^2 < \infty$保证方差不会发散
- 同时暗含了$a_k\to 0$，使得最后的$w^*$趋于定值
-
-
$\mathbb{E}(\eta_k|\mathcal{H}_k) =0, \text{ and }\mathbb{E}(\eta_k^2|\mathcal{H}_k < \infty)$
- 噪声条件期望为0，可以保证噪声是不依赖于历史的（不会随着采样步数增加而增加/减少，即不存在系统性偏移）
- 条件方差不会无穷大，从而避免出现极端大的扰动，保证理论分析（如大数定律、中心极限定理）可用
懒得纠结太多了
Stochastic Gradient Descent
随机梯度下降的目标是：
$$ \min_w \mathcal{J}(w) = \mathbb{E}\left[f(w,X)\right] $$是一个含有随机变量的式子，需要优化一个参数$w$
- Method1：Gradient Descent，沿梯度的反方向走一个步长
但是实际上我们很难获得所有样本分布$X$（数据是收集不完的）
所以这是一个理想的情况
- Method2：Batch Gradient Descent
- 考虑使用一个Batch进行近似
但是每次迭代，都需把每一个Batch进行扫描，并不是很轻松
- Method3：Stochastic Gradient Descent
- 其实就是batch变成1了
为了证明SGD算法是收敛的，我们可以尝试构造一个方程：
$$ g(w) = \mathbb{E}\left[\nabla_w f(w,X)\right] = 0 $$我们使用RM算法求解，则有：
$$ \widetilde{g}(w,\eta) = g(w) + \eta = \mathbb{E}\left[\nabla_w f(w,X)\right] + \eta $$则有迭代式：
$$ w_{k+1} = w_k - a_k\widetilde{g}(w_k,\eta_k) = w_k - a_k\nabla_wf(w_k,x_k) $$所以事实上SGD就是一个RM
截止到此，后续内容我应该不会继续深入，理论性比较强
之后如果有涉猎到的话再进行学习