blog

Stochastic Approximation, SA, 随机近似

在不知道方程表达式的情况下，通过随机采样来求解或优化方程。

RM 的思想是用函数输出值控制调参幅度。要想求解包含未知函数的方程 $g (w) = 0$ ，可以对 $w$ 进行迭代逼近：

w_{k + 1} = w_{k} - α_{k} \tilde{g} (w_{k}, η_{k}), k = 1, 2, 3, \dots \tilde{g} (w_{k}, η_{k}) = g (w_{k}) + η_{k}

其中 $α_{k}$ 表示学习率， $η_{k}$ 表示噪音。该算法使用条件：

$η_{k}$ 期望值为 0 且 $η_{k}$ 不为无穷。其对应的噪音分布可以不是高斯分布。
对于任意 $w$ ， $0 < c_{1} \leq \nabla_{w} g (w) \leq c_{2}$ 。说明 $g (w)$ 需要单调递增且导数不趋近无穷大。
$\sum_{k = 1}^{\infty} α_{k}^{2} < \infty$ 表示 $α_{k} \to 0$ ，否则 $w$ 不会收敛。
$\sum_{k = 1}^{\infty} α_{k} = \infty$ 表示 $α_{k}$ 不应收敛太快，以保证从任意初始值开始都能收敛。

梯度下降的思想是用函数梯度控制调参幅度。其目的是找到参数 $w$ 使 $J (w) = E [f (w, X)]$ 达到最小值，其中 $X$ 是已知分布的随机变量。

考虑基本梯度下降 GD：

w_{k + 1} = w_{k} - α_{k} \nabla_{w} J (w_{k}) = w_{k} - α_{k} \nabla_{w} E [f (w, X)] = w_{k} - α_{k} E [\nabla_{w} f (w, X)]

可以发现这里需要求 $f (w, X)$ 函数梯度的期望值，即需要知道函数表达式。如果表达式未知，则进行多次采样求均值作为梯度期望估计值。考虑批量梯度下降 BGD：

w_{k + 1} = w_{k} - α_{k} \frac{1}{n} i = 1 \sum n \nabla_{w} f (w_{k}, x_{i})

如果从已有样本中进行二次采样，则得到小批量梯度下降 MBGD：

w_{k + 1} = w_{k} - α_{k} \frac{1}{m} j = 1 \sum m \nabla_{w} f (w_{k}, x_{j})

如果只采样一次，采样得到的梯度称为随机梯度，则得到随机梯度下降 SGD：

w_{k + 1} = w_{k} - α_{k} \nabla_{w} f (w_{k}, x_{k})

w_{k}

与真值

w^{*}

相距较远时，随机梯度更接近

w_{k}

的梯度期望值；相距较近时，随机梯度表现出更大的随机性。

考虑随机梯度与实际梯度的相对误差：

δ_{k} = \frac{∣ \nabla _{w} f ( w _{k} , x _{k} ) - E [ \nabla _{w} f ( w _{k} , X )] ∣}{∣ E [ \nabla _{w} f ( w _{k} , X )] ∣}

因为 $E [\nabla_{w} f (w^{*}, X)] = 0$ ，所以：

∣ E [\nabla_{w} f (w_{k}, X)] ∣ = ∣ E [\nabla_{w} f (w_{k}, X)] - E [\nabla_{w} f (w^{*}, X)] ∣ = ∣ E [\nabla_{w}^{2} f (\tilde{w_{k}}, X) (w_{k} - w^{*})] ∣, \tilde{w_{k}} \in [w_{k}, w^{*}] = ∣ E [\nabla_{w}^{2} f (\tilde{w_{k}}, X)] ∣ \cdot ∣ w_{k} - w^{*} ∣ \geq c ∣ w_{k} - w^{*} ∣, when \nabla_{w}^{2} f (\tilde{w_{k}}, X) \geq c > 0

代入相对误差公式，得到：

δ_{k} \leq \frac{∣ \nabla _{w} f ( w _{k} , x _{k} ) - E [ \nabla _{w} f ( w _{k} , X )] ∣}{c ∣ w _{k} - w ^{*} ∣}

其中 $∣ w_{k} - w^{*} ∣$ 表示当前 $w$ 估计值到真值的距离，由公式可知这个距离与相对误差 $δ_{k}$ 近似成反比。