强化学习的数学原理-第6课
2025年11月28日
10:05
随机近似和随机梯度下降
增量式的算术平均
════════════════════════════════════════════════════════════════════════════════════════════════════
标准的算术平均是：
核心思想：
- 等权重：最终，每个数据点 x_i 在平均值 w_k 中的权重都是 1/k。第一个点和最后一个点同样重要。
- 衰减的学习率：增量更新中的步长 1/k 会随着时间 k 的增加而不断减小。当 k 很大时，新来的数据点 x_k 对现有平均值的影响微乎其微。
- 收敛性：w_k 最终会收敛到真实的均值（如果数据是平稳的）。
适用场景：当你需要计算一个固定数据集的精确平均值，或者数据流是平稳的，并且你认为所有历史数据都具有同等重要性时。
这种形式的好处是它是增量的，w_k作为E[X]的估计，不需要等待k个数据全部到达，才能得到w_k，
A mean estimate can be obtained immediately once a sample is received. Then, the mean
estimate can be used for other purposes immediately.
虽然刚开始数据很少的情况下，这个估计是不准的，但是随着数据的增加，
The mean estimate is not accurate in the beginning due to insucient samples (that is wk ≠E[X]). However, it is better than nothing. As more samples are obtained, the estimate can be improved gradually，当k趋于无穷时，wk趋于E[X]
|
那么我们可以把增量式算术平均这个式子中的1/k，换成更宽泛的α_k，并仍能满足wk收敛到E[X]吗？答案是可以的，但需要α_k满足一些条件。
Robbins-Monro algorithm
════════════════════════════════════════════════════════════════════════════════════════════════════
Stochastic approximation (SA):
SA refers to a broad class of stochastic iterative algorithms solving root finding or optimization problems.
Compared to many other root-finding algorithms such as gradient-based
methods, SA is powerful in the sense that it does not require to know the expression of the objective function nor its derivative.
随机近似是一系列随机、迭代式算术的统称，可以用来求解方程和最优化问题。SA不需要知道目标函数的表达式。
Robbins-Monro (RM) algorithm:
The is a pioneering work in the field of stochastic approximation.
The famous stochastic gradient descent algorithm is a special form of the RM algorithm.随机梯度下降是一种特殊的RM算法
Robbins-Monro algorithm { Problem statement}
也就是，我们想要求解g(w)=0这个等式，root finding problem。
root finding problem有很多应用，假设我们要最小化J（w)，相当于求dJ(w)=0。
如何来求g(w)=0呢，当我们不知道g(w)的具体表达式时，可以用RM算法：
其中，是对g(w_k)的第k次带有噪音的观测。
这个算法依赖于观测数据，不需要知道模型的表达式，g(w)可以认为是个黑盒。
为什么这个式子可以收敛到w*呢，g(w*)=0，可以通过一个例子说明：
假设g(w)=tanh(w-1），g(w)=0时，w*=1
从直觉上看，wk+1比wk更接近于w*，因此会最终收敛到w*。但是上面这个函数是个
单调递增函数，所以wk才会越来越接近w*，如果是个单调递减函数，wk会越来越
远离w*，所以g(w)其实是需要满足某些条件的。
进一步，RM算法收敛的前提是需要满足下面3个条件：
分别来看这3个条件：
- 条件1表示 ，
- g(w)是个单调递增函数，这可以保证g(w)=0有解并且唯一
- g(w)的梯度是有界的
- 乍一看这个条件很严格，因为它要求g(w)单调递增，但是其实不严格，因为一般情况下，
g(w)是J(w)的导数，g(w)单调递增等价于J(w)是个凸函数
- 条件2表示 ，a_k会逐渐收敛到0，但不要收敛得太快
- 为什么需要a_k趋向于0，因为：a_k趋于0，等价于w_k+1 - wk趋于0，这是我们所需要的。
- 为什么需要a_k不要收敛到0太快？因为：我们需要对任意的initial guess w1，都
能收敛到w*，所以w1-w_∞不能是bounded有界的。
- 条件3表示，
- {η_k}是个独立同分布的序列，并且满足E[η_k]=0 , E[]<∞，
那么回到刚才的问题，也就是，对于增量式的算术平均，我们想知道
wk作为对序列xk平均值的估计，能否收敛到E[X]
这个问题其实就可以用RM算法来回答，g(w)=w-E[X],其中E[X]是X的期望，其实就是一个常数，
那么RM算法的第一个条件（g(w)单调递增）就满足了，只要满足RM的第2个条件，即对α_k的
要求，就能保证wk收敛到E[X]
Stochastic gradient descent algorithm
════════════════════════════════════════════════════════════════════════════════════════════════════
SGD其实是一种RM算法。
w可以理解为神经网络中的参数，
X是一个随机变量，可以理解为数据点，X有一个分布，也就是数据有一个分布（比如人脸图像数据）
这个分布我们通常是不知道的，J（w)是一个期望，为什么是期望的形式呢？
因为期望对应的就是X这个随机变量。
如何来求解这个让J(w)最小的w呢？？
方法一：梯度下降 GD
|
因为期望其实就是求和，所以在上图式子中，可以把求导算子移到期望表达式内部，
但是这种方法需要我们知道X的分布，才能求得期望
方法二：批量梯度下降
用采样得到的批量样本的平均梯度，作为梯度期望的估计值。
但是需要很多个样本才能准确地估计期望值。
方法三：随机梯度下降
只用单次采样的梯度值，代替梯度期望值。
相当于BGD中的样本数量等于1。
这种方法肯定是不准确的，那么具体有多不准确 呢？SGD能不能收敛呢？
答案是可以的，SGD就是一种RM算法
SGD中的单次采样得到的随机梯度，可以看成是真实梯度+噪音，噪音就对应RM算法中的η
当然了，RM算法中，需要满足3个前提条件，那么SGD也需要满足3个条件，才能保证wk收敛到能让
J（w)最小的w*，如下图所示
SGD的收敛性已经确定了，但是SGD会不会收敛的很慢呢，比如绕了很大的弯才接近w*呢？其实
是不会的。
通过上图中的实验可以发现，当w离w*很远时，SGD是一直朝着w*的方向进行，没有
绕圈的情况；当w离w*较近时，才出现一定的随机性。
SGD为什么有这种比较好的性质呢？
从上式可以看出，SGD的误差是和当前wk与w*的距离成反比 的，距离越远，误差越小，
距离越近，误差越大。
|
BGD, MBGD, and SGD
════════════════════════════════════════════════════════════════════════════════════════════════════
MBGD就是介于BGD和SGD之间。
假设我有一批共n=100个采样数据{xi}，BGD是用全部这100个数据的平均梯度，MBGD是用这
100个数据中的一部分数据（比如10个）的平均梯度，SGD是只用一个点。
MBGD的好处就是：和SGD相比，随机性小一些；和BGD相比，不需要那么多样本，效率高，更灵活。
⚠⚠⚠需要注意的是，MBGD中，Ⅰ_k是从数据集D={xi}中独立m次采样得到的，也就是有放回采样
，所以当m=n时，MBGD并不完全等同于BGD，因为是有放回采样，所有MBGD的n个样本有可能有重复的。
但实际应用时，比如Pytorch 的dataloader都是无放回采样 ，二者差别不大。
对于SGD来说，xk这个样本也是从数据集D={xi}中采样得到的，而不是从X分布中采样的。但我觉得二者
应该是等价的。
|
总结：
