随机逼近：Robbins - Monro算法

参考论文如下：
Robbins, Herbert, and Sutton Monro. "A stochastic approximation method." The annals of mathematical statistics (1951): 400-407.

问题定义#

函数 $M(x)$ 表达式未知。给定一个 $x$ 值，我们无法观测到其对应 $M(x)$ 的准确值，因为我们的观察往往还包含有噪声，此谓随机：

y = M(x) + \varepsilon

我们认为，虽有噪声，所得观测值 $y$ 还是有迹可循的，它服从概率分布 $Y=Y(x)$ 。其累积分布函数（或称概率分布函数、分布函数） Cumulative Distribution Function (CDF) 为：

H(y|x) = {\rm Pr}(Y(x)\leq y)

并且满足随机变量 $Y(x)$ 的期望与真实值 $M(x)$ 相等：

M(x) = \int_{-\infty}^\infty y~{\rm d}H(y|x)

尽管不知道函数 $M(x)$ 确切的表达式，我们经常要求方程 $M(x)=\alpha$ 的根（其中 $\alpha$ 是常数）

为方便起见，我们假设函数 $M(x)$ 单调，这样我们能保证方程 $M(x)=\alpha$ 只有唯一的根，记作 $x=\theta$ 。 由于 $M(x)$ 未知， $\theta$ 对于我们来说，也是未知的。

Robbins - Monro 算法利用现有的观测值，通过一次接一次的迭代逼近实现 “曲线救国”，达到求根的最终目的。

方程求根问题可以很容易转化为函数零点问题。
Robbins - Monro 算法的核心思想就是利用当前函数的取值位置去推算函数的零点位置。

Robbins - Monro 算法#

Robbins - Monro 算法是迭代求根算法。由于 $M(x)$ 未知，我们无法使用牛顿法。即便我们能够得知 $M^\prime(x)$ 的表达式，应用牛顿法也未必会收敛。

在介绍算法结论前，我们给出一个重要前提：观测值 $y$ 有界，这是算法能够成立的基石。在实际使用中，这个前提一般是能够满足的。
用数学语言描述，就是对于概率分布 $Y(x)$ 来说， ${\rm Pr}(|Y(x)|\leq C) = \int_{-c}^c ~{\rm d}H(y|x) = 1$ 恒成立。

我们直接给出 Robbins - Monro 算法的迭代公式

x_{n+1} = x_n + a_n(\alpha - y_n)

注意到，当常数 $\alpha = 0$ 时，迭代公式可以写作 $x_{n+1} = x_n-a_ny_n$

那么迭代序列 $\{a_n\}$ 该如何选取呢？

迭代步长序列 $\{a_n\}$ 应当是非负序列，并且满足：

\lim\limits_{i\rightarrow\infty} a_i = 0, \quad\sum\limits_{i=1}^\infty a_i = \infty，\quad\sum\limits_{i=1}^\infty a_i^2 \lt \infty

以保证算法能够收敛，且误差可控。

我们取 $a_n = \frac1n$ 是满足上述条件的一个序列。实际上，所有形似 $\frac{c^\prime}{n}\leq a_n\leq \frac{c^{\prime\prime}}{n}$ 都是满足条件的序列。其中 $c^\prime, ~c^{\prime\prime}$ 都是正实数常量。这样的序列，我们称作 $\frac1n$ 型序列。

定理：如果序列 $\{a_n\}$ 是 $\frac1n$ 型序列， $M(x)$ 单调不减，方程 $M(x) = \alpha$ 存在唯一的根 $\theta$ 且满足导数 $M^\prime(\theta)>0$ 则 Robbins-Monro 算法有效。迭代逼近得到的根 $x_n$ 依概率收敛到真实根 $\theta$ 。

直观理解#

上文曾提到，方程求根问题可以转化为函数零点问题，Robbins - Monro 算法利用当前函数的取值去推算函数的零点位置。

如果函数是非降函数，函数取值为正，那么意味着下一次迭代需要负向修正（使得函数取值能够向 0 靠近），反之如果函数取值为负，则需要正向修正。

由于函数取值最终需要趋向于 0（零点），迭代步长也需要逐渐减小且须保证最终趋于 0。且为确保收敛，累积的方差应当有穷。

算法证明#

要保证算法成立，迭代得到的根 $x_{n}$ 须要依概率收敛到真实根 $\theta$ 。
用数学语言描述就是：当 $n\rightarrow \infty$ 时， $\mathbb P(|x_n-\theta|\lt\varepsilon|x_{n-1})\rightarrow 1$ 或 $\mathbb P(|x_n-\theta|\gt\varepsilon|x_{n-1})\rightarrow 0$ 其中， $\varepsilon$ 是任意正实数。

从依概率收敛的充分条件入手。 $\lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0$ 是依概率收敛的一个充分条件。

当二阶矩极限为 0 时，结合方差的非负性，可得 $Var(x_n-\theta) = \mathbb E(x_n-\theta) = 0$ 然后根据切比雪夫不等式可保证依概率收的敛条件成立。

充分条件和必要条件：
有 A 必有 B，则 A 是 B 的充分条件。
无 A 比无 B，则 A 是 B 的必要条件。

切比雪夫不等式 Chebyshev's Inequality

$\mathbb P(|X-\mathbb E[X]|\geq b)\leq \frac{Var[X]}{b^2}$

因此，我们只需要能够证明 $\lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0$ 即可。

根据迭代方程，我们列出：

\begin{align*} \mathbb E [(x_{n+1}-\theta)^2] &= \mathbb E[\mathbb E[(x_{n+1}-\theta)^2|x_n] ]\\ &=\mathbb E\left[\int_{-\infty}^\infty (x_n+a_n(\alpha-y)-\theta)^2 ~{\rm d}H(y|x_n) \right] \\ &=\mathbb E\left[\int_{-\infty}^\infty \left((x_n-\theta)^2 +2(x_n-\theta)a_n(\alpha-y_n) + a_n^2(\alpha-y_n)^2 \right) ~{\rm d}H(y|x_n) \right] \\ &= \mathbb E[(x_n-\theta)^2]-2a_n\mathbb E[(x_n-\theta)(M(x_n)-\alpha)] + a_n^2\mathbb E\left[\int_{-\infty}^\infty (\alpha-y)^2~{\rm d}H(y|x_n)\right] \end{align*}

其中 $\mathbb E(\mathbb E(X)) = \mathbb E(X)$

我们对上式中的记号，做一些替换，简化式子。

\begin{align*} & b_n = \mathbb E[(x_n-\theta)^2]\\ & d_n = \mathbb E[(x_n-\theta)(M(x_n)-\alpha)]\\ & e_n = \mathbb E\left[\int_{-\infty}^\infty(\alpha -y)^2~{\rm d}H(y|x_n)\right] \end{align*}

所以，上式也可以写成 $b_{n+1}-b_n = 2a_nd_n - a_n^2e_n$

我们曾假设 $M(x)$ 是单调的。不妨更进一步，令其单调不减。
易得：

\begin{align*} d_n &= \mathbb E[(x_n-\theta)(M(x_n)-\alpha)] \\ &= (x_n-\theta)(M(x_n)-\alpha) \\ &\gt 0 \end{align*}

由于观测值 $y$ 有界， $e_n$ 也有界。

\begin{align*} e_n \leq (C+|\alpha|)^2 \lt\infty \end{align*}

将 $b_{n+1}-b_n = 2a_nd_n - a_n^2e_n$ 求和，得到

b_{n+1} = b_1+\sum_{j=1}^n a_j^2e_j-2\sum_{j=1}^n a_j d_j

因为 $b_{n+1} = \mathbb E [(x_{n+1}-\theta)^2] \geq0$ ，

\begin{align*} \sum_{j=1}^n a_jd_j \leq \frac12\left( b_1+\sum_{j=1}^n a_n^2 e_n \right) \lt \infty \end{align*}

因此，正项级数 positive-term series $\sum_1^\infty a_nd_j$ 是收敛的。

所以，极限 $\lim_{n\rightarrow\infty} b_n = \lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2$ 必定存在。

引理 1 若非负常数序列 $\{k_n\}$ 满足 $d_n\geq k_nb_n, \sum_{n=1}^\infty a_nk_n=\infty$ 则 $\lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0$ 成立。

已经证明， $\sum_{n=1}^\infty a_nd_n$ 收敛，又有 $\sum_{n=1}^\infty a_nd_n \geq \sum_{n=1}^\infty a_nk_nb_n$ ，因此级数 $\sum_{n=1}^\infty a_nk_nb_n$ 理应收敛。但 $\sum_{n=1}^\infty a_nk_n$ 发散，所以必有 $\lim_{n\rightarrow\infty}b_n=0$

根据 Robbins-Monro 算法的递推公式 $x_{n+1} - x_n = a_n(\alpha - y_n)$ ，由于观测值有界，结合递推公式，我们定义

|x_n-\theta| \leq A_n = |x_1-\theta| + (C+|\alpha|)(a_1+a_2+\cdots+a_{n-1})

可得 ${\rm Pr}(|x_n-\theta|\leq A_n) = 1$ ，取

\overline k_n = \inf\left\{ \frac{M(x)-\alpha}{x-\theta} \right\}， \quad {\rm for} \quad 0 \lt|x-\theta|\leq A_n

由于前面假设了函数单调不减，所以 $\overline k_n\geq0$ 成立。因此

d_n=\int_{|x-\theta|\leq A_n}(x-\theta)(M(x)-\alpha)~{\rm d}P_n(x)\geq \int_{|x-\theta|\leq A_n}\overline k_n(x-\theta)^2~{\rm d}P_n(x) = \overline k_n b_n

假设：对正常数 $K$ ，当 $n$ 足够大时

$\overline k_n\geq\frac K{A_n}$ ，且
$\sum_{n=2}^\infty \frac{a_n}{(a_1+\cdots+a_{n-1})} = \infty$

很显然可得： $\sum_1^\infty a_n = \infty$ 因此，当 $n$ 足够大时：

A_n = |x_1-\theta| + (C+|\alpha|)(a_1+a_2+\cdots+a_{n-1}) \leq 2(C+|\alpha|)(a_1+a_2+\cdots+a_{n-1})

可以证明，当 $n$ 足够大时

a_n\overline k_n\geq a_n\frac K{A_n}\geq \frac{a_nK}{2(C+|\alpha|)(a_1+a_2+\cdots+a_{n-1})}

即 $\sum_{n=1}^\infty a_nk_n=\infty$ 发散。根据引理 1 推出：

引理 2 若存在正常数 $K$ ，当 $n$ 足够大时，若 $\{\overline k_n\}$ 和 $\{a_n\}$ 满足以下假设

$\overline k_n\geq\frac K{A_n}$ ，且
$\sum_{n=2}^\infty \frac{a_n}{(a_1+\cdots+a_{n-1})} = \infty$

那么必有 $\lim_{n\rightarrow\infty}b_n=0$

前文我们提到， $a_n = \frac1n$ 是满足条件的一个 $\{a_n\}$ 序列。我们只需证明存在符合假设条件的 $\{k_n\}$ 即可。

直观来讲，迭代式中不存在 $k_n$ 的表达形式，我们也应当避免结论显式依赖于 $k_n$ 才对。在引理 2 的推导过程中，我们将 $k_n$ 与 $M(x)$ 联系在了一起，于是很自然地，我们转而对 $M(x)$ 的性质提出要求。

定理 1 当 $\{a_n\}$ 是 $\frac 1n$ 型序列，且 $M(x)$ 满足

M(x)\left\{ \begin{align*} &\leq \alpha - \delta && {\rm for}~~ x\lt\theta\\ &\geq \alpha+\delta && {\rm for}~~x\gt\theta \end{align*}\right. \quad {\rm for~some~}\delta\gt 0.

那么必有 $\lim_{n\rightarrow\infty}b_n=0$

可根据引理 2 证明这个结论。由于

\frac{M(x)-\alpha}{x-\theta} \geq \frac\delta{A_n},\quad {\rm for}~~0\lt|x-\theta|\leq A_n

因此 $\overline k_n\geq \frac\delta{A_n}$ ，取 $K=\delta$ 引理 2 成立。

定理 1 中对于 $M(x)$ 的限制条件比较强（难以满足），我们希望能够得到一个较宽松的条件（不那么难满足的条件）。

定理 2 当函数 $M(x)$ 满足条件：

$M(x)$ 单调不减
$M(\theta) = \alpha$
$M^\prime(\theta)\gt 0$

必有 $\lim_{n\rightarrow\infty}b_n=0$

我们同样根据引理 2 进行证明。
首先：

M(x)-\alpha = (x-\theta)(M^\prime(x) + o(x-\theta))

其中 $o(x-\theta)$ 是高阶无穷小，根据假设条件，结合函数图像容易理解： $o(x-\theta) \geq 0$ 。显然存在常数 $\delta\gt0$ 使得 $|x-\theta|\leq\delta$ 时 $o(x-\theta) \geq -\frac12M^\prime(\theta)$

因此：

\frac{M(x)-\alpha}{x-\theta} \left\{\begin{align*} &\geq \frac{M(\theta+\delta)-\alpha}{A_n} \geq \frac{\delta M^\prime(\theta)}{2A_n} && {\rm for}~\theta+\delta\leq x\leq \theta+A_n \\ & = \frac{\alpha-M(x)}{\theta-x}\geq \frac{\alpha-M(\theta-\delta)}{A_n}\geq \frac{\delta M^\prime(\theta)}{2A_n} && {\rm for}~\theta-A_n\leq x\leq \theta-\delta \end{align*} \right.

取 $K=\frac{\delta M^\prime(\theta)}{2}\gt0$ 引理 2 成立。

至此，定理证毕