隨機逼近：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_n$ 是收斂的。

所以，極限 $\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 成立。

至此，定理證畢