Sunforger

Sunforger

ホームアーカイブ

ランダム近似：ロビンズ - モンロアルゴリズム

#数学781
AI 翻訳
この記事はAIを通じて英語から日本語に翻訳されました。原文を表示
AI が生成した要約
Robbins-Monro算法是一种迭代求根算法，适用于无法使用牛顿法的情况。该算法利用观测值来推算函数的零点位置，解决方程求根问题。迭代步长序列应为非负序列，并满足一定条件，算法才能有效。切比雪夫不等式被用来保证算法的收敛性。根据引理1，如果满足一定条件的非负常数序列，迭代得到的根会以概率收敛到真实根。

参考論文は以下の通りです：
Robbins, Herbert, and Sutton Monro. "A stochastic approximation method." The annals of mathematical statistics (1951): 400-407.

問題定義#

関数 M(x)M(x) の表現は不明です。与えられた xx 値に対して、対応する M(x)M(x) の正確な値を観測することはできません。なぜなら、私たちの観測にはしばしばノイズが含まれているからです。これをランダムと呼びます：

y=M(x)+εy = M(x) + \varepsilon

私たちは、ノイズがあっても得られた観測値 yy には追跡可能なパターンがあると考えています。これは確率分布 Y=Y(x)Y=Y(x) に従います。その累積分布関数（または確率分布関数、分布関数）は次のように表されます：

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

そして、確率変数 Y(x)Y(x) の期待値は真の値 M(x)M(x) と等しいことが満たされます：

M(x)=∫−∞∞y dH(y∣x)M(x) = \int_{-\infty}^\infty y~{\rm d}H(y|x)

関数 M(x)M(x) の正確な表現が不明であるにもかかわらず、私たちはしばしば方程式 M(x)=αM(x)=\alpha の根（ここで α\alpha は定数）を求める必要があります。

便宜上、関数 M(x)M(x) が単調であると仮定します。これにより、方程式 M(x)=αM(x)=\alpha には唯一の根が存在し、これを x=θx=\theta と記します。 M(x)M(x) が不明であるため、θ\theta も私たちにとっては未知です。

Robbins - Monro アルゴリズムは、既存の観測値を利用して、逐次的な反復近似を通じて「曲線救国」を実現し、根を求める最終目的を達成します。

方程式の根を求める問題は、関数の零点問題に容易に変換できます。
Robbins - Monro アルゴリズムの核心的な考え方は、現在の関数の値を利用して関数の零点の位置を推測することです。

Robbins - Monro アルゴリズム#

Robbins - Monro アルゴリズムは反復的な根を求めるアルゴリズムです。M(x)M(x) が不明であるため、ニュートン法を使用することはできません。たとえ M′(x)M^\prime(x) の表現がわかっても、ニュートン法を適用しても収束するとは限りません。

アルゴリズムの結論を紹介する前に、重要な前提を示します：観測値 yy は有界であること。これはアルゴリズムが成立する基礎です。実際の使用において、この前提は一般的に満たされます。
数学的に表現すると、確率分布 Y(x)Y(x) に対して、Pr(∣Y(x)∣≤C)=∫−cc dH(y∣x)=1{\rm Pr}(|Y(x)|\leq C) = \int_{-c}^c ~{\rm d}H(y|x) = 1 が常に成り立ちます。

Robbins - Monro アルゴリズムの反復公式を直接示します

xn+1=xn+an(α−yn)x_{n+1} = x_n + a_n(\alpha - y_n)

注意すべきは、定数 α=0\alpha = 0 の場合、反復公式は xn+1=xn−anynx_{n+1} = x_n-a_ny_n と書けることです。

では、反復系列 {an}\{a_n\} はどのように選択すべきでしょうか？

反復ステップ長系列 {an}\{a_n\} は非負の系列であるべきで、次の条件を満たす必要があります：

lim⁡i→∞ai=0,∑i=1∞ai=∞，∑i=1∞ai2<∞\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

これにより、アルゴリズムが収束し、誤差が制御可能であることが保証されます。

私たちは an=1na_n = \frac1n を上記の条件を満たす系列として選びます。実際、すべての形が c′n≤an≤c′′n\frac{c^\prime}{n}\leq a_n\leq \frac{c^{\prime\prime}}{n} である系列も条件を満たします。ここで c′, c′′c^\prime, ~c^{\prime\prime} は正の実数定数です。このような系列を、1n\frac1n 型系列と呼びます。

定理：もし系列 {an}\{a_n\} が 1n\frac1n 型系列であり、M(x)M(x) が単調非減少で、方程式 M(x)=αM(x) = \alpha が唯一の根 θ\theta を持ち、導関数 M′(θ)>0M^\prime(\theta)>0 が成り立つならば、Robbins-Monro アルゴリズムは有効です。反復近似によって得られた根 xnx_n は確率的に真の根 θ\theta に収束します。

直感的理解#

前述のように、方程式の根を求める問題は関数の零点問題に変換でき、Robbins - Monro アルゴリズムは現在の関数の値を利用して関数の零点の位置を推測します。

もし関数が非減少関数で、関数の値が正であれば、次の反復では負の修正が必要です（関数の値が 0 に近づくように）。逆に、関数の値が負であれば、正の修正が必要です。

関数の値は最終的に 0（零点）に近づく必要があるため、反復ステップも徐々に小さくなり、最終的には 0 に近づく必要があります。また、収束を確保するために、累積の分散は有限であるべきです。

アルゴリズムの証明#

アルゴリズムが成立するためには、反復で得られた根 xnx_{n} が確率的に真の根 θ\theta に収束する必要があります。
数学的に表現すると、n→∞n\rightarrow \infty のとき、P(∣xn−θ∣<ε∣xn−1)→1\mathbb P(|x_n-\theta|\lt\varepsilon|x_{n-1})\rightarrow 1 または P(∣xn−θ∣>ε∣xn−1)→0\mathbb P(|x_n-\theta|\gt\varepsilon|x_{n-1})\rightarrow 0 であり、ここで ε\varepsilon は任意の正の実数です。

確率的収束の十分条件から始めます。 lim⁡n→∞E(xn−θ)2=0\lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0 は確率的収束の一つの十分条件です。

二次モーメントの極限が 0 であるとき、分散の非負性と結びつけると、Var(xn−θ)=E(xn−θ)=0Var(x_n-\theta) = \mathbb E(x_n-\theta) = 0 となります。そしてチェビシェフの不等式により、確率的収束の条件が成立することが保証されます。

十分条件と必要条件：
A があれば B がある、したがって A は B の十分条件です。
A がなければ B がない、したがって A は B の必要条件です。

チェビシェフの不等式 Chebyshev's Inequality

P(∣X−E[X]∣≥b)≤Var[X]b2\mathbb P(|X-\mathbb E[X]|\geq b)\leq \frac{Var[X]}{b^2}

したがって、私たちはただ lim⁡n→∞E(xn−θ)2=0\lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0 を証明すればよいのです。

反復方程式に基づいて、次のように列挙します：

E[(xn+1−θ)2]=E[E[(xn+1−θ)2∣xn]]=E[∫−∞∞(xn+an(α−y)−θ)2 dH(y∣xn)]=E[∫−∞∞((xn−θ)2+2(xn−θ)an(α−yn)+an2(α−yn)2) dH(y∣xn)]=E[(xn−θ)2]−2anE[(xn−θ)(M(xn)−α)]+an2E[∫−∞∞(α−y)2 dH(y∣xn)]\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(E(X))=E(X)\mathbb E(\mathbb E(X)) = \mathbb E(X)

上式の記号をいくつか置き換え、式を簡略化します。

bn=E[(xn−θ)2]dn=E[(xn−θ)(M(xn)−α)]en=E[∫−∞∞(α−y)2 dH(y∣xn)]\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*}

したがって、上式は bn+1−bn=2andn−an2enb_{n+1}-b_n = 2a_nd_n - a_n^2e_n と書けます。

私たちは M(x)M(x) が単調であると仮定しました。さらに進めて、単調非減少であるとしましょう。
容易に得られます：

dn=E[(xn−θ)(M(xn)−α)]=(xn−θ)(M(xn)−α)>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*}

観測値 yy は有界であるため、ene_n も有界です。

en≤(C+∣α∣)2<∞\begin{align*} e_n \leq (C+|\alpha|)^2 \lt\infty \end{align*}

bn+1−bn=2andn−an2enb_{n+1}-b_n = 2a_nd_n - a_n^2e_n を合計すると、次のようになります。

bn+1=b1+∑j=1naj2ej−2∑j=1najdjb_{n+1} = b_1+\sum_{j=1}^n a_j^2e_j-2\sum_{j=1}^n a_j d_j

bn+1=E[(xn+1−θ)2]≥0b_{n+1} = \mathbb E [(x_{n+1}-\theta)^2] \geq0 であるため、

∑j=1najdj≤12(b1+∑j=1nan2en)<∞\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*}

したがって、正項級数 ∑1∞andn\sum_1^\infty a_nd_n は収束します。

したがって、極限 lim⁡n→∞bn=lim⁡n→∞E(xn−θ)2\lim_{n\rightarrow\infty} b_n = \lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2 は必ず存在します。

補題 1 非負定数系列 {kn}\{k_n\} が dn≥knbn,∑n=1∞ankn=∞d_n\geq k_nb_n, \sum_{n=1}^\infty a_nk_n=\infty を満たすならば lim⁡n→∞E(xn−θ)2=0\lim_{n\rightarrow\infty}\mathbb E(x_n-\theta)^2=0 が成り立ちます。

すでに証明したように、 ∑n=1∞andn\sum_{n=1}^\infty a_nd_n は収束し、また ∑n=1∞andn≥∑n=1∞anknbn\sum_{n=1}^\infty a_nd_n \geq \sum_{n=1}^\infty a_nk_nb_n が成り立つため、級数 ∑n=1∞anknbn\sum_{n=1}^\infty a_nk_nb_n は収束するはずです。しかし、 ∑n=1∞ankn\sum_{n=1}^\infty a_nk_n は発散するため、必ず lim⁡n→∞bn=0\lim_{n\rightarrow\infty}b_n=0 となります。

Robbins-Monro アルゴリズムの再帰公式 xn+1−xn=an(α−yn)x_{n+1} - x_n = a_n(\alpha - y_n) に基づき、観測値が有界であることを考慮し、再帰公式を結びつけて定義します。

∣xn−θ∣≤An=∣x1−θ∣+(C+∣α∣)(a1+a2+⋯+an−1)|x_n-\theta| \leq A_n = |x_1-\theta| + (C+|\alpha|)(a_1+a_2+\cdots+a_{n-1})

得られるのは Pr(∣xn−θ∣≤An)=1{\rm Pr}(|x_n-\theta|\leq A_n) = 1 です。次に

k‾n=inf⁡{M(x)−αx−θ}，for0<∣x−θ∣≤An\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≥0\overline k_n\geq0 が成り立ちます。したがって

dn=∫∣x−θ∣≤An(x−θ)(M(x)−α) dPn(x)≥∫∣x−θ∣≤Ank‾n(x−θ)2 dPn(x)=k‾nbnd_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

仮定：正常数 KK に対して、nn が十分大きいとき

  1. k‾n≥KAn\overline k_n\geq\frac K{A_n}，かつ
  2. ∑n=2∞an(a1+⋯+an−1)=∞\sum_{n=2}^\infty \frac{a_n}{(a_1+\cdots+a_{n-1})} = \infty

明らかに得られるのは：∑1∞an=∞\sum_1^\infty a_n = \infty したがって、nn が十分大きいとき：

An=∣x1−θ∣+(C+∣α∣)(a1+a2+⋯+an−1)≤2(C+∣α∣)(a1+a2+⋯+an−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})

証明できますが、nn が十分大きいとき

ank‾n≥anKAn≥anK2(C+∣α∣)(a1+a2+⋯+an−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})}

すなわち ∑n=1∞ankn=∞\sum_{n=1}^\infty a_nk_n=\infty が発散します。補題 1 から導きます：

補題 2 もし正常数 KK が存在し、nn が十分大きいとき、{k‾n}\{\overline k_n\} と {an}\{a_n\} が次の仮定を満たすならば

  1. k‾n≥KAn\overline k_n\geq\frac K{A_n}，かつ
  2. ∑n=2∞an(a1+⋯+an−1)=∞\sum_{n=2}^\infty \frac{a_n}{(a_1+\cdots+a_{n-1})} = \infty

必ず lim⁡n→∞bn=0\lim_{n\rightarrow\infty}b_n=0 が成り立ちます

前述のように、an=1na_n = \frac1n は条件を満たす {an}\{a_n\} 系列です。私たちはただ仮定条件を満たす {kn}\{k_n\} が存在することを証明すればよいのです。

直感的に言えば、反復式中に knk_n の表現形式は存在しませんが、結論が明示的に knk_n に依存しないようにすることが重要です。補題 2 の導出過程で、knk_n を M(x)M(x) と関連付けたため、自然に M(x)M(x) の性質に要求を提出することになります。

定理 1 {an}\{a_n\} が 1n\frac 1n 型系列であり、M(x)M(x) が次の条件を満たすとき：

M(x){≤α−δfor  x<θ≥α+δfor  x>θfor some δ>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.

必ず lim⁡n→∞bn=0\lim_{n\rightarrow\infty}b_n=0 が成り立ちます

補題 2 を用いてこの結論を証明できます。なぜなら

M(x)−αx−θ≥δAn,for  0<∣x−θ∣≤An \frac{M(x)-\alpha}{x-\theta} \geq \frac\delta{A_n},\quad {\rm for}~~0\lt|x-\theta|\leq A_n

したがって k‾n≥δAn\overline k_n\geq \frac\delta{A_n} となり、K=δK=\delta を取ると補題 2 が成立します。

定理 1 における M(x)M(x) の制限条件は比較的強い（満たすのが難しい）ため、より緩やかな条件（満たしやすい条件）を得たいと考えています。

定理 2 関数 M(x)M(x) が次の条件を満たすとき：

  1. M(x)M(x) は単調非減少である
  2. M(θ)=αM(\theta) = \alpha
  3. M′(θ)>0M^\prime(\theta)\gt 0

必ず lim⁡n→∞bn=0\lim_{n\rightarrow\infty}b_n=0 が成り立ちます

私たちは同様に補題 2 を用いて証明します。
まず：

M(x)−α=(x−θ)(M′(x)+o(x−θ))M(x)-\alpha = (x-\theta)(M^\prime(x) + o(x-\theta))

ここで o(x−θ)o(x-\theta) は高次の無限小であり、仮定条件に基づき、関数のグラフを考慮すると容易に理解できます： o(x−θ)≥0o(x-\theta) \geq 0。明らかに、∣x−θ∣≤δ|x-\theta|\leq\delta のとき、常数 δ>0\delta\gt0 が存在し、 o(x−θ)≥−12M′(θ)o(x-\theta) \geq -\frac12M^\prime(\theta) となります。

したがって：

M(x)−αx−θ{≥M(θ+δ)−αAn≥δM′(θ)2Anfor θ+δ≤x≤θ+An=α−M(x)θ−x≥α−M(θ−δ)An≥δM′(θ)2Anfor θ−An≤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.

K=δM′(θ)2>0K=\frac{\delta M^\prime(\theta)}{2}\gt0 を取ると、補題 2 が成立します。

これにより、定理が証明されました。

読み込み中...
文章は、創作者によって署名され、ブロックチェーンに安全に保存されています。