摘要:尋找?guī)д`差的量測(cè)到的未知回歸函數(shù)的零點(diǎn)或極值，是系統(tǒng)辨識(shí)、適應(yīng)控制、模式識(shí)別、適應(yīng)濾波和神經(jīng)元網(wǎng)絡(luò)等領(lǐng)域中都要遇到的問(wèn)題。隨機(jī)逼近提供了解決這一問(wèn)題的遞推方法。本文對(duì)隨機(jī)逼近算法作了較為深入的研究。其主要內(nèi)容為:①概括的介紹了隨機(jī)逼近算法的研究目的和發(fā)展方向;②概括介紹了隨機(jī)逼近理論的發(fā)展史;③研究分析隨機(jī)逼近理論主要算法;④概括的介紹隨機(jī)逼近的某些實(shí)際應(yīng)用。

關(guān)鍵詞:隨機(jī)逼近算法;發(fā)展方向;實(shí)際應(yīng)用

中圖分類號(hào):O174.41 文獻(xiàn)標(biāo)識(shí)碼:A 文章編號(hào):1000-8136(2009)33-0051-03

1隨機(jī)逼近的研究目的

在許多理論課題或?qū)嶋H應(yīng)用中，經(jīng)常要求一個(gè)函數(shù)的零點(diǎn)或極值，如果函數(shù)有已知的解析表達(dá)式，那么在理論上解決這個(gè)問(wèn)題并不困難;如果雖不知函數(shù)的表達(dá)式，但它在任一點(diǎn)的取值可以無(wú)誤差的測(cè)量到，那么有不少行之有效的數(shù)值方法可供選用;當(dāng)既不知函數(shù)的表達(dá)式，又不能無(wú)誤差的測(cè)量到函數(shù)值時(shí)，如何求函數(shù)的零點(diǎn)或極值，正是隨機(jī)逼近要解決的問(wèn)題。

2隨機(jī)逼近理論的發(fā)展

隨機(jī)逼近創(chuàng)始于50年代初，Robbins-Monrn[1]首先提出了求未知函數(shù)f(#8226;)零點(diǎn)x0的一個(gè)遞推算法。在Robbins-Monro的奠基性工作后，隨機(jī)逼近取得蓬勃發(fā)展。主要的研究目標(biāo)是考察各種相關(guān)的測(cè)量噪聲[2]及拓廣可適用的回歸函數(shù)范圍，[3]而收斂類型，除了最初的均方收斂，更多的是研究概率1收斂及弱收斂。從研究方法講，文獻(xiàn)[2]是用鞅收斂方法研究隨機(jī)逼近算法概率1收斂的有代表性的專著，其基本特點(diǎn)是討論獨(dú)立噪聲，它對(duì)20世紀(jì)70年代以前的工作做了一個(gè)很好的總結(jié)，之后，文件[3]把遞推算法的收斂性和微分方程的穩(wěn)定性建立了聯(lián)系，從而使得考察的測(cè)量誤差的范圍有實(shí)質(zhì)性的擴(kuò)大。但這種方法要事先假定算法給出的估計(jì)值有界。

經(jīng)過(guò)半個(gè)多世紀(jì)的發(fā)展歷程，隨機(jī)逼近思想已經(jīng)得到了不斷的進(jìn)步和完善。到目前為止，隨機(jī)逼近控制方法有RM法、KW法。其中基于KW方法上的變形情況有:有限微分隨機(jī)逼近算法(FDSA)、隨機(jī)方向的隨機(jī)逼近算法(RDSA)和同時(shí)擾動(dòng)隨機(jī)逼近算法(SPSA)。

3隨機(jī)逼近算法簡(jiǎn)介

3.1隨機(jī)逼近問(wèn)題

對(duì)許多實(shí)際問(wèn)題和理論問(wèn)題的研究，常常歸結(jié)為一個(gè)非線性方程組的求根問(wèn)題，長(zhǎng)期以來(lái)，人們發(fā)展了不少逐次逼近的數(shù)值解法。但是，在很多實(shí)際問(wèn)題中，人們并不知道方程中非線性函數(shù)的形式，只可以對(duì)給定的自變量值，帶隨機(jī)誤差地測(cè)量到函數(shù)值。在這種情況下，怎樣去求這個(gè)未知的非線性函數(shù)的零點(diǎn)，是一個(gè)從實(shí)踐到理論都很重要的問(wèn)題。

設(shè)未知函數(shù)為 ，它的零點(diǎn)為x0，即

h(x0)=0 (1)

對(duì)h(#8226;)可以在任意點(diǎn)x進(jìn)行測(cè)量，但測(cè)量帶有誤差，若xn為第n次測(cè)量時(shí)所取定的自變量值，則函數(shù)的觀測(cè)值為:

yn+1=h(xn)+ζ n+1(2)

{ζ n }是測(cè)量誤差序列，可以依賴于xn。h(#8226;)稱為回歸函數(shù)。

用實(shí)際得到的序列{ xn }和{yn }，去求回歸函數(shù)的根x0，這就是隨機(jī)逼近問(wèn)題。下面用朱允文所舉的一個(gè)例子說(shuō)明隨機(jī)逼近的實(shí)際性。

假設(shè)發(fā)明了一種新藥，必須確定它的最佳劑量，設(shè)劑量為x，人服藥后的反應(yīng)為f(x)，而人們希望達(dá)到的最佳反應(yīng)為α，定義h(x)=f(x)-α。顯然，這里的f(#8226;)和h(#8226;)都只是一種形式上的寫(xiě)法，人們無(wú)法精確的知道藥物劑量與藥物反應(yīng)之間的對(duì)應(yīng)關(guān)系h(#8226;)，但是可以帶隨機(jī)誤差地測(cè)量它，得到:

yn+1=h(xn)-α+ζ n+1

解決這一實(shí)際問(wèn)題就要求助于某種隨機(jī)逼近算法。

3.2RM算法的提出

1951年，Robbins和Monro首次提出并研究了一種隨機(jī)逼近算法，[1]他們?nèi)?shù)列{ai}為增益系數(shù):

(3)

對(duì)x0的第n+1次逼近為:

xn+1=xn+an yn+1 (4)

其中yn如式(2)所定義，這就是著名的Robbins-Monro(RM)算法。當(dāng)時(shí)，他們討論了ζ n為相互獨(dú)立的情況，并且#8467;=1，在h(#8226;)嚴(yán)格單調(diào)的時(shí)候，他們證明了xn對(duì)x0的平方收斂性:

顯然上面的結(jié)果是在比較強(qiáng)條件下得到的，但這標(biāo)志著人們找到了對(duì)理論和實(shí)際都很重要的這類問(wèn)題的一種處理方法。

3.3KW算法的提出

在RM算法提出后的第二年，出現(xiàn)了Kiefer-Wolfowitz(KW)算法，[4]也就是求h(x)極值的算法。如果能直接測(cè)量h(#8226;)的導(dǎo)數(shù)，那么問(wèn)題就歸結(jié)為上面的RM算法。但有時(shí)只能測(cè)量h(#8226;)本身，只好利用h(#8226;)的測(cè)量值的差商去估計(jì)h(#8226;)的導(dǎo)數(shù)值，這就是KW算法的基本思想。因此，KW算法與RM算法比較，除了在測(cè)量點(diǎn)上有一些變化外，算法的基本形式以及理論研究的基本思想都是一致的。

增益系數(shù){a1}又稱步長(zhǎng)因子，它所具有的性質(zhì)(3)，對(duì)隨機(jī)逼近算法和其他某些隨機(jī)逼近遞推算法都是必要的。條件

的實(shí)質(zhì)是ai必須趨于0，也就是每步的修正量越來(lái)越小，

直到把測(cè)量誤差的影響慢慢壓制下去，使ai yi中的 。

但是 又說(shuō)明，ai趨于0的速度不能太快。因?yàn)槿绻?/p>

，這時(shí)即使 ，h(#8226;)一致有界，║h(#8226;)║≤c，那么

這表明增量║xi+1-xi║之和與初值x0無(wú)關(guān)地一致有界，因而當(dāng)初值x0與x0相距很遠(yuǎn)時(shí)，xi不可能逼近x0。即使有極限也不

是x0。這當(dāng)然不是我們所希望的，所以必須有 。

3.4“Lyapunov函數(shù)”方法

對(duì)任何一種遞推算法，收斂性是首要問(wèn)題。到70年代初，在測(cè)量誤差為鞅差序列時(shí)，證明了各種意義下的多維算法的收斂性，如均方收斂和幾乎處處收斂。文獻(xiàn)[5]比較全面地總結(jié)了20年的進(jìn)展。鞅差序列是一種不相關(guān)列，由鞅差序列{ω}生成的滑動(dòng)平均(MA)列εn=A0ωn+A1ωn-1+…+Arωn-r是一種有限相關(guān)列，而實(shí)際問(wèn)題中的測(cè)量誤差(噪聲)列可能是無(wú)窮相關(guān)的，如工程上常常用到的自回歸滑動(dòng)平均(ARMA)列:

εn+B1 ε n-1+…+Bqε n-q=A 0ωn+A 1ωn-1+…+A r ω n-r (5)

直到20世紀(jì)70年代中，對(duì)相關(guān)噪聲下的隨機(jī)逼近收斂性分析，還沒(méi)有合適的方法。究其原因，人們主要用鞅差收斂定理來(lái)證明算法的收斂性，而當(dāng)測(cè)量誤差無(wú)窮相關(guān)時(shí)就破壞了應(yīng)用鞅收斂性的前提。此外，很多學(xué)者都認(rèn)為隨機(jī)收斂性問(wèn)題自然應(yīng)采用概率方法，沒(méi)有意識(shí)到可以借助隨機(jī)收斂性以外的數(shù)學(xué)方法。

1977年，瑞典學(xué)者Ljung L在對(duì)隨機(jī)遞推算法作收斂性分析時(shí)，想到形式如(4)一類的算法的收斂性，與下面的常微分方程的穩(wěn)定性有關(guān)。

(6)

粗略地說(shuō)，記 ，把算法(4)寫(xiě)成:

(7)

由于隨an趨于0，εn的作用被壓制下去，于是得到方程(6)。Ljung提出的利用常微分方程穩(wěn)定性定理來(lái)證明算法收斂性的方法，簡(jiǎn)稱為常微分方程(ODE)方法。[6]對(duì)隨機(jī)逼近算法的進(jìn)一步研究表明，證明算法收斂的本質(zhì)不在于把數(shù)據(jù)內(nèi)插成連續(xù)函數(shù)，也不在于尋找這些函數(shù)的“尾函數(shù)”所滿足的微分方程，而在于存在和h(#8226;)相應(yīng)的Lyapunov函數(shù)v(#8226;)，不必做數(shù)據(jù)的內(nèi)插函數(shù)，可以證明v(xn)不可能無(wú)窮次穿越任一非零區(qū)間，從而可簡(jiǎn)潔的證明算法的大范圍收斂性，同時(shí)，還可得到穩(wěn)健型結(jié)果。我們稱這種方法為“Lyapunov函數(shù)”方法。

3.5SPSA算法

同時(shí)擾動(dòng)隨機(jī)逼近算法簡(jiǎn)稱(SPSA)，這個(gè)算法是Spall根據(jù)Kiefer-Wolforwitz隨機(jī)逼近算法于1987年改進(jìn)而成。Kiefer-Wolforwitz算法是以有限差分梯度逼近為基礎(chǔ)的，它在每次梯度逼近中需要利用目標(biāo)函數(shù)的2P個(gè)測(cè)量值(其中P為向量的維數(shù))。Spall改進(jìn)后的SPSA算法在每次梯度逼近中只利用了目標(biāo)函數(shù)的2個(gè)測(cè)量值，這與Kiefer-Wolforwitz算法形成明顯的對(duì)比。1992年，Spall又對(duì)SPSA算法進(jìn)行了全面深入的分析與論證。[9]他證明了雖然SPSA算法在每次迭代的梯度逼近中僅利用了Kiefer-Wolforwitz隨機(jī)逼近算法的1/p倍的目標(biāo)函數(shù)的估計(jì)值，但在一般情況下，當(dāng)?shù)螖?shù)相同時(shí)，兩種算法可以達(dá)到同樣的精度。因而，SPSA算法在解決多變量的問(wèn)題中，有其獨(dú)特的優(yōu)越性。此后，SPSA 算法引起了著名科學(xué)家Cauwenberghs、Chin、Maeda等的關(guān)注，并被廣泛研究與應(yīng)用于排隊(duì)系統(tǒng)、模式識(shí)別、神經(jīng)網(wǎng)絡(luò)訓(xùn)練、動(dòng)態(tài)系統(tǒng)的自適應(yīng)控制等方面。正是由于上面的這些特性，SPSA算法現(xiàn)已成為一個(gè)新的學(xué)科分支。

SPSA算法特別適用于多維變量系統(tǒng)，同其他隨機(jī)優(yōu)化方法(如遺傳算法)比較，更易于實(shí)現(xiàn)，不但適用于連續(xù)系統(tǒng)也適合離散系統(tǒng)。

4小結(jié)

從Robbins. H與Monro.S的RM算法到Kiefer J和Wolfowitz J的KW算法，接著由KW算法發(fā)展而來(lái)的SPSA算法無(wú)不顯示出工程實(shí)踐及社會(huì)、經(jīng)濟(jì)實(shí)踐將越來(lái)越多地需要用到隨機(jī)逼近。

對(duì)隨機(jī)逼近算法理論與應(yīng)用的研究，近年來(lái)已成為工程領(lǐng)域的一個(gè)重要課題。與大部分的自適應(yīng)算法一樣，隨機(jī)逼近算法是大規(guī)模的線性系統(tǒng)，但又具有隨機(jī)系統(tǒng)的特性?？捎糜趧?dòng)態(tài)系統(tǒng)控制、統(tǒng)計(jì)參數(shù)估計(jì)等。而動(dòng)態(tài)系統(tǒng)控制則需要引進(jìn)具有噪聲的估計(jì)值。可以預(yù)計(jì)隨機(jī)逼近算法能迅速地用于動(dòng)態(tài)系統(tǒng)等隨機(jī)運(yùn)算領(lǐng)域，特別是在對(duì)于隨機(jī)性要求很高的控制領(lǐng)域，將有極為廣闊的應(yīng)用前景。[10]

參考文獻(xiàn)

1 Robbins.H，Monro.S.A stochastic approximation method. Ann.

Math.Stat[M]. USA:Ann Math. Stat， 1951(22):400～407

2 Dvoresky A. On stochastic approximation[M]. USA: Proc. Third Berkeley Symp. On math.Stat.and Prob， 1956(1):39～45

3 陳翰馥、朱允明.變界截尾的隨機(jī)逼近算法[J].中國(guó)科學(xué)(A輯)，1986(6):561～570

4 Kiefer J，Wolfowitz J. Stochastic estimation of the modulus of a regression function[M]. USA:Ann.Math.Stat， 1952(23):462～466

5 Nevelson M B， Hasminskii R Z. Stochastic Approximation and Recursive Estimation[M]. USA:AMS Translations of Math. Monographs， 1976(20):47

6 Ljung L. Analysis of recursive stochastic algorithms[M].USA:IEEE

Trans， on Automatic Control， 1977， AC-22(4):551～575

7 Kushner H J， Clark D S. Stochastic Approximation for Constrained

and Unconstrained Systems[M]. USA:Springer-Verlag， 1978(20):500～520

8 Payman Sadegh. Constrained Optimization Via Stochastic Approxim

-ation with Simultaneous Perturbation Gradient Approximation Elsevier Science[M]. USA:Automatica， 1997(33):889～892

9 J.C.Spall.Multivariate Stochastic Approximation Using a Simulta

-neous Perturbation Gradent Approximation[M]. USA:IEEE Trans on Automatic Control， 1992(37):332～341

10 李容萍.梯度平均的同時(shí)擾動(dòng)算法分析[J].電子科技大學(xué)碩士學(xué)位論文，2006:10

Approach the Brief Introduction of Algorithm at Random

Xie Ni

Abstract: The zero point of unknown return function of looking for the quantity with error to examine or extreme value， distinguish ， adapt to controlling systematically， pattern-recognition， meeting and straining the question met in such domain Zhongdu as waves and neuron network， etc.. Have approached and offered and solved this at random passing the method of pushing away of the question. This text has done comparatively deep research in approaching the algorithm at random. Its main content is: ①Ones that summarize have introduced research purpose and developing direction of approaching the algorithm at random; ②Have introduced the development history of approaching the theory at random briefly; ③research and analyse and approach the main algorithm of the theory at random; ④Some practical application that the introduction summarized approached at random.

Key words: approach the algorithm at random; developing direction; practical application