参考论文如下：
问题定义#
函数 M ( x ) M(x) M ( x ) x x x M ( x ) M(x) M ( x ) 此谓随机 ：
Copy y = M ( x ) + ε y = M(x) + \varepsilon y = M ( x ) + ε 我们认为，虽有噪声，所得观测值 y y y Y = Y ( x ) Y=Y(x) Y = Y ( x )
Copy H ( y ∣ x ) = P r ( Y ( x ) ≤ y ) H(y|x) = {\rm Pr}(Y(x)\leq y) H ( y ∣ x ) = Pr ( Y ( x ) ≤ y ) 并且满足随机变量 Y ( x ) Y(x) Y ( x ) M ( x ) M(x) M ( x )
Copy M ( x ) = ∫ − ∞ ∞ y d H ( y ∣ x ) M(x) = \int_{-\infty}^\infty y~{\rm d}H(y|x) M ( x ) = ∫ − ∞ ∞ y d H ( y ∣ x ) 尽管不知道函数 M ( x ) M(x) M ( x ) M ( x ) = α M(x)=\alpha M ( x ) = α α \alpha α
为方便起见，我们假设函数 M ( x ) M(x) M ( x ) M ( x ) = α M(x)=\alpha M ( x ) = α x = θ x=\theta x = θ 由于 M ( x ) M(x) M ( x ) θ \theta θ
Robbins - Monro 算法利用现有的观测值，通过一次接一次的迭代逼近 实现 “曲线救国”，达到求根的最终目的。
方程求根问题可以很容易转化为函数零点问题。
Robbins - Monro 算法#
Robbins - Monro 算法是迭代求根算法。由于 M ( x ) M(x) M ( x ) M ′ ( x ) M^\prime(x) M ′ ( x )
在介绍算法结论前，我们给出一个重要前提：观测值 y y y Y ( x ) Y(x) Y ( x ) P r ( ∣ Y ( x ) ∣ ≤ C ) = ∫ − c c d H ( y ∣ x ) = 1 {\rm Pr}(|Y(x)|\leq C) = \int_{-c}^c ~{\rm d}H(y|x) = 1 Pr ( ∣ Y ( x ) ∣ ≤ C ) = ∫ − c c d H ( y ∣ x ) = 1
我们直接给出 Robbins - Monro 算法的迭代公式
Copy x n + 1 = x n + a n ( α − y n ) x_{n+1} = x_n + a_n(\alpha - y_n) x n + 1 = x n + a n ( α − y n ) 注意到，当常数 α = 0 \alpha = 0 α = 0 x n + 1 = x n − a n y n x_{n+1} = x_n-a_ny_n x n + 1 = x n − a n y n
那么迭代序列 { a n } \{a_n\} { a n }
迭代步长序列 { a n } \{a_n\} { a n }
Copy lim i → ∞ a i = 0 , ∑ i = 1 ∞ a i = ∞ ， ∑ i = 1 ∞ a i 2 < ∞ \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 i → ∞ lim a i = 0 , i = 1 ∑ ∞ a i = ∞ ， i = 1 ∑ ∞ a i 2 < ∞ 以保证算法能够收敛，且误差可控。
我们取 a n = 1 n a_n = \frac1n a n = n 1 c ′ n ≤ a n ≤ c ′ ′ n \frac{c^\prime}{n}\leq a_n\leq \frac{c^{\prime\prime}}{n} n c ′ ≤ a n ≤ n c ′′ c ′ , c ′ ′ c^\prime, ~c^{\prime\prime} c ′ , c ′′ 这样的序列，我们称作 1 n \frac1n n 1
定理：如果序列 { a n } \{a_n\} { a n } 1 n \frac1n n 1 M ( x ) M(x) M ( x ) M ( x ) = α M(x) = \alpha M ( x ) = α θ \theta θ M ′ ( θ ) > 0 M^\prime(\theta)>0 M ′ ( θ ) > 0 x n x_n x n θ \theta θ
直观理解#
上文曾提到，方程求根问题可以转化为函数零点问题，Robbins - Monro 算法利用当前函数的取值去推算函数的零点位置。
如果函数是非降函数，函数取值为正，那么意味着下一次迭代需要负向修正（使得函数取值能够向 0 靠近），反之如果函数取值为负，则需要正向修正。
由于函数取值最终需要趋向于 0（零点），迭代步长也需要逐渐减小且须保证最终趋于 0。且为确保收敛，累积的方差应当有穷。
算法证明#
要保证算法成立，迭代得到的根 x n x_{n} x n θ \theta θ 。n → ∞ n\rightarrow \infty n → ∞ P ( ∣ x n − θ ∣ < ε ∣ x n − 1 ) → 1 \mathbb P(|x_n-\theta|\lt\varepsilon|x_{n-1})\rightarrow 1 P ( ∣ x n − θ ∣ < ε ∣ x n − 1 ) → 1 P ( ∣ x n − θ ∣ > ε ∣ x n − 1 ) → 0 \mathbb P(|x_n-\theta|\gt\varepsilon|x_{n-1})\rightarrow 0 P ( ∣ x n − θ ∣ > ε ∣ x n − 1 ) → 0 ε \varepsilon ε
从依概率收敛的充分条件入手。 lim n → ∞ E ( x n − θ ) 2 = 0 \lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0 lim n → ∞ E ( x n − θ ) 2 = 0
当二阶矩极限为 0 时，结合方差的非负性，可得 V a r ( x n − θ ) = E ( x n − θ ) = 0 Var(x_n-\theta) = \mathbb E(x_n-\theta) = 0 Va r ( x n − θ ) = E ( x n − θ ) = 0 切比雪夫不等式可保证依概率收的敛条件成立 。
充分条件和必要条件：
切比雪夫不等式 Chebyshev's Inequality
Copy P ( ∣ X − E [ X ] ∣ ≥ b ) ≤ V a r [ X ] b 2 \mathbb P(|X-\mathbb E[X]|\geq b)\leq \frac{Var[X]}{b^2} P ( ∣ X − E [ X ] ∣ ≥ b ) ≤ b 2 Va r [ X ]
因此，我们只需要能够证明 lim n → ∞ E ( x n − θ ) 2 = 0 \lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0 lim n → ∞ E ( x n − θ ) 2 = 0
根据迭代方程 ，我们列出：
Copy E [ ( x n + 1 − θ ) 2 ] = E [ E [ ( x n + 1 − θ ) 2 ∣ x n ] ] = E [ ∫ − ∞ ∞ ( x n + a n ( α − y ) − θ ) 2 d H ( y ∣ x n ) ] = E [ ∫ − ∞ ∞ ( ( x n − θ ) 2 + 2 ( x n − θ ) a n ( α − y n ) + a n 2 ( α − y n ) 2 ) d H ( y ∣ x n ) ] = E [ ( x n − θ ) 2 ] − 2 a n E [ ( x n − θ ) ( M ( x n ) − α ) ] + a n 2 E [ ∫ − ∞ ∞ ( α − y ) 2 d H ( y ∣ x n ) ] \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*} E [( x n + 1 − θ ) 2 ] = E [ E [( x n + 1 − θ ) 2 ∣ x n ]] = E [ ∫ − ∞ ∞ ( x n + a n ( α − y ) − θ ) 2 d H ( y ∣ x n ) ] = E [ ∫ − ∞ ∞ ( ( x n − θ ) 2 + 2 ( x n − θ ) a n ( α − y n ) + a n 2 ( α − y n ) 2 ) d H ( y ∣ x n ) ] = E [( x n − θ ) 2 ] − 2 a n E [( x n − θ ) ( M ( x n ) − α )] + a n 2 E [ ∫ − ∞ ∞ ( α − y ) 2 d H ( y ∣ x n ) ]
其中 E ( E ( X ) ) = E ( X ) \mathbb E(\mathbb E(X)) = \mathbb E(X) E ( E ( X )) = E ( X )
我们对上式中的记号，做一些替换，简化式子。
Copy b n = E [ ( x n − θ ) 2 ] d n = E [ ( x n − θ ) ( M ( x n ) − α ) ] e n = E [ ∫ − ∞ ∞ ( α − y ) 2 d H ( y ∣ x n ) ] \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 = E [( x n − θ ) 2 ] d n = E [( x n − θ ) ( M ( x n ) − α )] e n = E [ ∫ − ∞ ∞ ( α − y ) 2 d H ( y ∣ x n ) ] 所以，上式也可以写成 b n + 1 − b n = 2 a n d n − a n 2 e n b_{n+1}-b_n = 2a_nd_n - a_n^2e_n b n + 1 − b n = 2 a n d n − a n 2 e n
我们曾假设 M ( x ) M(x) M ( x ) 。
Copy d n = E [ ( x n − θ ) ( M ( x n ) − α ) ] = ( x n − θ ) ( M ( x n ) − α ) > 0 \begin{align*}
d_n &= \mathbb E[(x_n-\theta)(M(x_n)-\alpha)] \\
&= (x_n-\theta)(M(x_n)-\alpha) \\
&\gt 0
\end{align*} d n = E [( x n − θ ) ( M ( x n ) − α )] = ( x n − θ ) ( M ( x n ) − α ) > 0 由于观测值 y y y e n e_n e n
Copy e n ≤ ( C + ∣ α ∣ ) 2 < ∞ \begin{align*}
e_n \leq (C+|\alpha|)^2 \lt\infty
\end{align*} e n ≤ ( C + ∣ α ∣ ) 2 < ∞ 将 b n + 1 − b n = 2 a n d n − a n 2 e n b_{n+1}-b_n = 2a_nd_n - a_n^2e_n b n + 1 − b n = 2 a n d n − a n 2 e n
Copy b n + 1 = b 1 + ∑ j = 1 n a j 2 e j − 2 ∑ j = 1 n a j d j 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 = b 1 + j = 1 ∑ n a j 2 e j − 2 j = 1 ∑ n a j d j 因为 b n + 1 = E [ ( x n + 1 − θ ) 2 ] ≥ 0 b_{n+1} = \mathbb E [(x_{n+1}-\theta)^2] \geq0 b n + 1 = E [( x n + 1 − θ ) 2 ] ≥ 0
Copy ∑ j = 1 n a j d j ≤ 1 2 ( b 1 + ∑ j = 1 n a n 2 e n ) < ∞ \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*} j = 1 ∑ n a j d j ≤ 2 1 ( b 1 + j = 1 ∑ n a n 2 e n ) < ∞ 因此，正项级数 positive-term series ∑ 1 ∞ a n d n \sum_1^\infty a_nd_n ∑ 1 ∞ a n d n
所以，极限 lim n → ∞ b n = lim n → ∞ E ( x n − θ ) 2 \lim_{n\rightarrow\infty} b_n = \lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2 lim n → ∞ b n = lim n → ∞ E ( x n − θ ) 2 。
引理 1 若非负常数序列 { k n } \{k_n\} { k n } d n ≥ k n b n , ∑ n = 1 ∞ a n k n = ∞ d_n\geq k_nb_n, \sum_{n=1}^\infty a_nk_n=\infty d n ≥ k n b n , ∑ n = 1 ∞ a n k n = ∞ lim n → ∞ E ( x n − θ ) 2 = 0 \lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0 lim n → ∞ E ( x n − θ ) 2 = 0 。
已经证明， ∑ n = 1 ∞ a n d n \sum_{n=1}^\infty a_nd_n ∑ n = 1 ∞ a n d n ∑ n = 1 ∞ a n d n ≥ ∑ n = 1 ∞ a n k n b n \sum_{n=1}^\infty a_nd_n \geq \sum_{n=1}^\infty a_nk_nb_n ∑ n = 1 ∞ a n d n ≥ ∑ n = 1 ∞ a n k n b n ∑ n = 1 ∞ a n k n b n \sum_{n=1}^\infty a_nk_nb_n ∑ n = 1 ∞ a n k n b n ∑ n = 1 ∞ a n k n \sum_{n=1}^\infty a_nk_n ∑ n = 1 ∞ a n k n lim n → ∞ b n = 0 \lim_{n\rightarrow\infty}b_n=0 lim n → ∞ b n = 0
根据 Robbins-Monro 算法的递推公式 x n + 1 − x n = a n ( α − y n ) x_{n+1} - x_n = a_n(\alpha - y_n) x n + 1 − x n = a n ( α − y n )
Copy ∣ x n − θ ∣ ≤ A n = ∣ x 1 − θ ∣ + ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) |x_n-\theta| \leq A_n = |x_1-\theta| + (C+|\alpha|)(a_1+a_2+\cdots+a_{n-1}) ∣ x n − θ ∣ ≤ A n = ∣ x 1 − θ ∣ + ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) 可得 P r ( ∣ x n − θ ∣ ≤ A n ) = 1 {\rm Pr}(|x_n-\theta|\leq A_n) = 1 Pr ( ∣ x n − θ ∣ ≤ A n ) = 1
Copy k ‾ n = inf { M ( x ) − α x − θ } ， f o r 0 < ∣ x − θ ∣ ≤ A n \overline k_n = \inf\left\{ \frac{M(x)-\alpha}{x-\theta} \right\}， \quad {\rm for} \quad 0 \lt|x-\theta|\leq A_n k n = inf { x − θ M ( x ) − α } ， for 0 < ∣ x − θ ∣ ≤ A n 由于前面假设了函数单调不减，所以 k ‾ n ≥ 0 \overline k_n\geq0 k n ≥ 0
Copy d n = ∫ ∣ x − θ ∣ ≤ A n ( x − θ ) ( M ( x ) − α ) d P n ( x ) ≥ ∫ ∣ x − θ ∣ ≤ A n k ‾ n ( x − θ ) 2 d P n ( x ) = k ‾ n b n 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 d n = ∫ ∣ x − θ ∣ ≤ A n ( x − θ ) ( M ( x ) − α ) d P n ( x ) ≥ ∫ ∣ x − θ ∣ ≤ A n k n ( x − θ ) 2 d P n ( x ) = k n b n 假设：对正常数 K K K n n n
k ‾ n ≥ K A n \overline k_n\geq\frac K{A_n} k n ≥ A n K ∑ n = 2 ∞ a n ( a 1 + ⋯ + a n − 1 ) = ∞ \sum_{n=2}^\infty \frac{a_n}{(a_1+\cdots+a_{n-1})} = \infty ∑ n = 2 ∞ ( a 1 + ⋯ + a n − 1 ) a n = ∞
很显然可得：∑ 1 ∞ a n = ∞ \sum_1^\infty a_n = \infty ∑ 1 ∞ a n = ∞ n n n
Copy A n = ∣ x 1 − θ ∣ + ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) ≤ 2 ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) 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}) A n = ∣ x 1 − θ ∣ + ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) ≤ 2 ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) 可以证明，当 n n n
Copy a n k ‾ n ≥ a n K A n ≥ a n K 2 ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) 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})} a n k n ≥ a n A n K ≥ 2 ( C + ∣ α ∣ ) ( a 1 + a 2 + ⋯ + a n − 1 ) a n K 即 ∑ n = 1 ∞ a n k n = ∞ \sum_{n=1}^\infty a_nk_n=\infty ∑ n = 1 ∞ a n k n = ∞
引理 2 若存在正常数 K K K n n n { k ‾ n } \{\overline k_n\} { k n } { a n } \{a_n\} { a n }
k ‾ n ≥ K A n \overline k_n\geq\frac K{A_n} k n ≥ A n K ∑ n = 2 ∞ a n ( a 1 + ⋯ + a n − 1 ) = ∞ \sum_{n=2}^\infty \frac{a_n}{(a_1+\cdots+a_{n-1})} = \infty ∑ n = 2 ∞ ( a 1 + ⋯ + a n − 1 ) a n = ∞
那么必有 lim n → ∞ b n = 0 \lim_{n\rightarrow\infty}b_n=0 lim n → ∞ b n = 0
前文我们提到，a n = 1 n a_n = \frac1n a n = n 1 { a n } \{a_n\} { a n } { k n } \{k_n\} { k n }
直观来讲，迭代式中不存在 k n k_n k n k n k_n k n k n k_n k n M ( x ) M(x) M ( x ) M ( x ) M(x) M ( x )
定理 1 当 { a n } \{a_n\} { a n } 1 n \frac 1n n 1 M ( x ) M(x) M ( x )
Copy M ( x ) { ≤ α − δ f o r x < θ ≥ α + δ f o r x > θ f o r s o m e δ > 0. 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. M ( x ) { ≤ α − δ ≥ α + δ for x < θ for x > θ for some δ > 0. 那么必有 lim n → ∞ b n = 0 \lim_{n\rightarrow\infty}b_n=0 lim n → ∞ b n = 0
可根据引理 2 证明这个结论。由于
Copy M ( x ) − α x − θ ≥ δ A n , f o r 0 < ∣ x − θ ∣ ≤ A n \frac{M(x)-\alpha}{x-\theta} \geq \frac\delta{A_n},\quad {\rm for}~~0\lt|x-\theta|\leq A_n x − θ M ( x ) − α ≥ A n δ , for 0 < ∣ x − θ ∣ ≤ A n 因此 k ‾ n ≥ δ A n \overline k_n\geq \frac\delta{A_n} k n ≥ A n δ K = δ K=\delta K = δ
定理 1 中对于 M ( x ) M(x) M ( x )
定理 2 当函数 M ( x ) M(x) M ( x )
M ( x ) M(x) M ( x ) M ( θ ) = α M(\theta) = \alpha M ( θ ) = α M ′ ( θ ) > 0 M^\prime(\theta)\gt 0 M ′ ( θ ) > 0
必有 lim n → ∞ b n = 0 \lim_{n\rightarrow\infty}b_n=0 lim n → ∞ b n = 0
我们同样根据引理 2 进行证明。
Copy M ( x ) − α = ( x − θ ) ( M ′ ( x ) + o ( x − θ ) ) M(x)-\alpha = (x-\theta)(M^\prime(x) + o(x-\theta)) M ( x ) − α = ( x − θ ) ( M ′ ( x ) + o ( x − θ )) 其中 o ( x − θ ) o(x-\theta) o ( x − θ ) o ( x − θ ) ≥ 0 o(x-\theta) \geq 0 o ( x − θ ) ≥ 0 δ > 0 \delta\gt0 δ > 0 ∣ x − θ ∣ ≤ δ |x-\theta|\leq\delta ∣ x − θ ∣ ≤ δ o ( x − θ ) ≥ − 1 2 M ′ ( θ ) o(x-\theta) \geq -\frac12M^\prime(\theta) o ( x − θ ) ≥ − 2 1 M ′ ( θ )
因此：
Copy M ( x ) − α x − θ { ≥ M ( θ + δ ) − α A n ≥ δ M ′ ( θ ) 2 A n f o r θ + δ ≤ x ≤ θ + A n = α − M ( x ) θ − x ≥ α − M ( θ − δ ) A n ≥ δ M ′ ( θ ) 2 A n f o r θ − A n ≤ x ≤ θ − δ \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. x − θ M ( x ) − α ⎩ ⎨ ⎧ ≥ A n M ( θ + δ ) − α ≥ 2 A n δ M ′ ( θ ) = θ − x α − M ( x ) ≥ A n α − M ( θ − δ ) ≥ 2 A n δ M ′ ( θ ) for θ + δ ≤ x ≤ θ + A n for θ − A n ≤ x ≤ θ − δ 取 K = δ M ′ ( θ ) 2 > 0 K=\frac{\delta M^\prime(\theta)}{2}\gt0 K = 2 δ M ′ ( θ ) > 0
至此，定理证毕