隨機逼近的問題背景：

設因素x的值可由試驗者控制,x的“響應”的指標值為Y,當取x之值x進行試驗時，響應Y可表為Y=h(x)+ε，式中h(x)為一未知函數，ε為隨機誤差。設目標值為A,要找這樣的x,使h(x)=A。分別以Y-A和h(x)-A代替Y和h(x)。不妨設A=0，問題就在于找方程h(x)=0的根x。例如若x為施藥量，Y為衡量藥物反應的某種生理指標,則問題在于找出施藥量x,以使該生理指標控制于適當的值A。

算法分析：

若隨機誤差 ε=0，且h(x)為已知函數，則數值分析中提供了許多近似解法。例如可用牛頓迭代法求解：從一適當選擇的初始值x0出發，用迭代公式x{i+1}=x{i}-h(x{i})/h'(x{i})；但當h(x)未知且有隨機誤差干擾時,α{i}和h(x{i})無法算出。仔細觀察這個迭代公式，不難發現，其核心思想就是利用當前函數的取值位置去推算函數的0點位置。假如我們將函數限定為非降函數，那么我們知道0點右邊的一定是大于0的，左邊的則是小于0的。那么如果我們取到一個大于0的值，我們就知道下一次取值要往左修正，反之如果是小于0，那么就要往右修正。為了不讓一次左修正加一次右修正以后又回到原來的點，我們必須要讓每次修正的步長有所遞減（最后必須趨于0），這也是算法會收斂的關鍵所在——你不能讓它遞減的太快，否則在抵達0點前就收斂了，但是也不能過慢，否則雖然最后會收斂，但是時間會很長。

為了能夠處理一開始的那種隨機情況，Robbins-Monro將牛頓法稍作修改，利用以上的思想，引進迭代程序x{i+1}=x{i}-a{i}Y{xi},式中a{i}為適當選定的常數序列，用以嚴格控制收斂的速度。為什么這個算法是正確的，即使觀測到的數據具有隨機性？直觀的解釋，由于ε為隨機誤差，所以必定有E[Y]=E[h(x)+ε]=h(x), 也就是說，所取得的值雖然不準確，確實在準確值附近波動的。那么如果準確值大于0，波動以后的值也大于0，最終修訂的方向就沒有錯誤，所以波動在這種情況所造成的影響只是稍微改變了一點步長，這對于收斂性本身毫無影響；但是如果波動以后的值是小于0的，最終就會向相反的方向修訂，這樣就是遠離0點的了，這必然是和收斂方向相違背的！但是，注意到，如果越是遠離0點，波動的平均值（也就是準確值）也是遠離0點的，這樣如果想要產生一個波動點，這個點的取值符號和當前準確值取值符號相反的概率會越來越小！也就是說，函數的非降性在這里發揮了關鍵作用——它使得即使會由于隨機波動造成錯誤的修訂方向，但是最后這種錯誤不會無限延續下去，必定在一定的時候被修正回正確的方向，而且犯的錯誤越大，得到修正的可能性也就越大。

序列學習：

那么， 這和序列學習有什么關系呢？比如我們有一個函數f(x), 我現在不知道這個函數的準確形式，但是我手上有對應的取值數據，我要通過這些數據把函數還原出來（這個過程叫做回歸）。但是我的數據不是一次性獲得的，可能我用完第一個數據以后要等一段時間第二個數據才會出來。我不想浪費時間等數據，而想通過已有的數據動態的去估計這個函數，如果有了新的數據，我就可以利用前面估計的結果結合這個新數據得到新的估計結果。。。這個過程就叫做序列學習。現在，如果我不關注函數的具體形式，但是對函數在什么數據下取0點特別感興趣，那么我就要用到Robbins-Monro算法了：每次讀入一個新的數據，把這個數據帶入已有的估計中就會得到一個修正量，用這個修正量就可以得到新的估計：

對于某個統計量ti = t(x1,x2...,x_{i-1}) 以及關于這個統計量的未知函數f(t). 如何盡可能的準確求出f(t)=0的解？

t_{i+1}=ti - ai F(xi;ti)

F(xi;ti) = f(ti)+ε (E[F(xi;ti)]=f(ti))

在當前統計量ti下，F(xi;ti)為基于當前觀測值xi的估計(具有隨機波動性),?f(ti)為準確函數取值。 注意到t_{i+1}在計算時已經包括了xi這點的信息，所以下一次迭代直接從x_{i+1}開始。換句話說?F(xi;ti)這個估計值包含了x1,x2...,xi的全部信息。

總結

以上是生活随笔為你收集整理的Robbins-Monro 随机逼近算法和序列学习（Sequential Learning）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。