基于自適應(yīng)步長搜索的弱估計器算法

摘要：強估計器，即依據(jù)收斂概率為1的穩(wěn)定估計方法，因其優(yōu)秀的計算特性已經(jīng)成功地應(yīng)用于多種應(yīng)用領(lǐng)域。但此類方法的優(yōu)點基于一個假設(shè)，即所接收的數(shù)據(jù)需要保持分布不變。隨著計算能力的提升、需要解決的問題日趨復(fù)雜、處理的數(shù)據(jù)日益龐大多變，單純地將問題抽象為使用底層分布穩(wěn)定的數(shù)據(jù)流已難以滿足日常應(yīng)用的需要。弱估計器在強估計器的基礎(chǔ)上，放寬了對底層分布的限制，使其可以估計動態(tài)變化的目標(biāo)參數(shù)。而目標(biāo)參數(shù)的動態(tài)變化要求弱估計器可以迅速地反應(yīng)、快速地追蹤。為了提高弱估計器應(yīng)對目標(biāo)參數(shù)的動態(tài)追蹤能力，本文提出了基于自適應(yīng)步長搜索（ASS）的弱估計器方法，實驗表明本文提出的算法顯著地提高了弱估計器的性能，并有效地平衡了參數(shù)的追蹤速度與估計精度。

關(guān)鍵詞：弱估計器;分布;動態(tài)變化;自適應(yīng)步長搜索

中圖分類號：TP3

文獻標(biāo)識碼：A

文章編號：1009-3044（2020）04-0244-03

收稿日期：2019-11-21

作者簡介：王春輝，同濟大學(xué)，碩士。

A Novel Weak Estimator Based on Adaptive Step Search

WANG Chun-hui

（Department of Computer Science and Technology，College of Electronics and Information Engineering，Tongji University，Shanghai 201804，China）

Abstract：Strong estimators，i.e.，those with stable properties of converence with probability 1，have been applied to many fields success-fully due to its outstanding computational capability，which，however，is Based on the hypothesis that the underlying data remains the same distribution.With the tremendously increasing capability of computation，the problems to be solved growing more complex and da-ta to be processed varying largely，simply abstracting the problems to be ones using stable data distribution can not satisfy the requirements of applications.Weak estimators release the restriction of the underlying data to make it possible to estimate dynamically changing parameters.To react to the change quickly and track the change of parameters swiftly requires weak estimators to respond quickly.This paper proposes a scheme Based on the currently best performer，SSLDE，by the inspiration of Adaptive Step Search.Experimental results shows better performance compared to other methods and better balance between the tracking speed and estimation accuracy.

Key words：Weak Estimator;Distribution;Dynamic Change;Adaptive Step Search

1 弱估計器簡介

在機器學(xué)習(xí)、統(tǒng)計學(xué)等領(lǐng)域中，對待解決問題的數(shù)據(jù)進行分布參數(shù)估計經(jīng)常作為深入挖掘數(shù)據(jù)特性、預(yù)測推斷新數(shù)據(jù)特征的重要基礎(chǔ)?；跇O大似然估計、貝葉斯估計等傳統(tǒng)方法的參數(shù)估計器因其優(yōu)秀的統(tǒng)計特性和計算性能被廣泛應(yīng)用，但同時，該類估計器也受到較強的限制，即需要數(shù)據(jù)本身分布的長期穩(wěn)定性，要求數(shù)據(jù)的底層分布是不變的、分布的參數(shù)是不隨時間變化的。我們將這樣的參數(shù)估計器稱為強估計器。強估計器的條件不僅限制了其應(yīng)用的場景，更是對其可使用的數(shù)據(jù)做了過強的規(guī)范。

然而隨著計算資源性能的提升以及基礎(chǔ)網(wǎng)絡(luò)設(shè)施的發(fā)展，應(yīng)用需要解決越來越復(fù)雜、多變的問題是難以避免的趨勢，其中也包括應(yīng)用處理的數(shù)據(jù)分布保持動態(tài)的變化。需要估計變化分布的估計器，稱為弱估計器[1]。

滑動窗口作為較為直觀的算法，可以用作弱估計器，適應(yīng)分布底層參數(shù)變化的情景，通過最近的數(shù)據(jù)得到當(dāng)前時刻參數(shù)的預(yù)估值。滑動窗口采用固定大小的空間N sw 存儲最近得到的數(shù)據(jù)用，但其性能也極大地受限于窗口的大小。當(dāng)滑動窗口過大時，窗口內(nèi)數(shù)據(jù)過多，分布發(fā)生變化時，窗口內(nèi)大多為舊分布的數(shù)據(jù)，滑動窗口難以做出迅速的反應(yīng)，導(dǎo)致追蹤分布變化的速度慢、時間長;當(dāng)滑動窗口過小時，雖然可以較好地跟蹤參數(shù)變化，但可存儲的數(shù)據(jù)量有限，很難達到精度的要求，且受數(shù)據(jù)的影響，估計值波動較大。

一些不依靠滑動窗口的弱估計器[1-3]表現(xiàn)出比滑動窗口更加優(yōu)秀的性能，其中SSLDE[3]擁有最好的精度和追蹤速度。以二項分布為例，SSLDE算法使用一個學(xué)習(xí)機制（Learning Mechnism，LM）在[0，1]區(qū)間的位置r（t）表示對t時刻該分布的估計，LM更新自己的位置時，不僅根據(jù)該時刻接收到的數(shù)據(jù)，同時也依據(jù)自身位置，而一個虛擬的環(huán)境（Oracle）根據(jù)這兩個條件、以固定的步長來更新LM位置。假設(shè)空間被等分為N部分，N即LM固定的步長，則更新公式如下：

其中，x（）為t時刻所接收的數(shù)據(jù)，x（）∈{0，1}，rand為均勻分布的隨機數(shù)，r（t）∈[0，N]且為整數(shù)。

2 自適應(yīng)步長搜索

同樣使用1/0信號作為環(huán)境與LM的交互，隨機點定位（Stochastic Point Location，SPL）問題旨在找到給定區(qū)間內(nèi)最優(yōu)的參數(shù)。不失一般性，我們可以將所有問題的給定區(qū)間投影到[0，1]區(qū)間中。SPL 問題同樣使用一個LM表示當(dāng)前對該區(qū)間內(nèi)最優(yōu)值的估計，通過環(huán)境的反饋確定LM向左移動還是向右移動來逼近最優(yōu)點。大量行之有效的算法[4-9]被用于解決該問題，其中性能最為突出的為自適應(yīng)步長搜索[9]（AdaptiveStepSearch，ASS）。

最早的算法[4]將[0，1]區(qū)間離散化為N個等間距區(qū)間，亦稱為LM的步長，而算法在啟發(fā)性（informative）環(huán)境下，即環(huán)境指引正確方向的概率p>0.5時，LM根據(jù)環(huán)境指引即可收斂到最接近最優(yōu)值的區(qū)間。但該算法同樣面對著參數(shù)選擇的問題，當(dāng)區(qū)間數(shù)N過大，算法收斂的速度過慢，而較少的區(qū)間數(shù)給出的結(jié)果則精度難以達到要求。

ASS算法基于以上算法做出改進，保留當(dāng)前以及最近兩次的方向信息，作為調(diào)整步長的依據(jù)，決策表見表1：

其基本思想是：當(dāng)最近三次的方向信息都是同一方向時，以方向信息組合為111為例，有大概率說明最優(yōu)點存在于LM的右方，且LM還未到達最優(yōu)點，同時暗示當(dāng)前的步長較小，所以可以適當(dāng)增加步長，加快搜索速度;而當(dāng)LM趨向于在一個區(qū)間迂回時，即方向信息組合為010或101時，很可能代表LM已經(jīng)找到最優(yōu)區(qū)間，此時將步長減小可以提升找到最優(yōu)點的精度。

3 對弱估計器的改進

SSLDE雖然在性能上優(yōu)于滑動窗口的方法，但同樣需要指定其步長來平衡搜索速度與精度之間的關(guān)系。受到自適應(yīng)步長搜索的啟發(fā)，我們將類似的方法應(yīng)用于弱估計器中，在SSL-DE的基礎(chǔ)上保留三次最近的移動方向，采用與ASS相同的決策表來自適應(yīng)地調(diào)整步長，讓算法根據(jù)自身狀態(tài)自動平衡搜索速度與精度的關(guān)系：在距離目標(biāo)較遠時，可以用大步長盡快接近估計值，而在估計值附近時可以調(diào)小步長，達到高精度。偽代碼如下：

在各類應(yīng)用中，對精度的要求十分常見。若使用滑動窗口或者SSLDE等方法，可以通過增大窗口大小、步長等參數(shù)達到要求。但高精度的要求往往導(dǎo)致相關(guān)參數(shù)的值過大，而這兩種弱估計器無法自適應(yīng)地調(diào)整，從而會限制追蹤目標(biāo)參數(shù)的速度，且應(yīng)對目標(biāo)參數(shù)變化的反應(yīng)不夠靈敏。

本文中提出的改進算法，通過增加類似ASS算法中的兩位最近方向信息以及步長決策表，實現(xiàn)了在遠離估計值時能使用大步長快速定位區(qū)間、在估計值附近時可以減小步長提升精度要求的效果。

4 實驗比較

在本部分，我們將滑動窗口、SSLDE和本文提出的方法.IWE進行對比，將窗口大小值Nsw、SSLDE的步長N以及IWE的最小步長Nmin設(shè)置為相等的值用以控制變量，模擬使用三種算法獲得相同精度的要求。每組實驗重復(fù)10000次，取平均值來減小隨機產(chǎn)生的誤差。

實驗一通過改變步長值，來探究不同步長值對算法追蹤性能的影響。實驗二則固定了三種算法的步長為64，模擬參數(shù)在固定周期內(nèi)隨機變化的情景。

圖1（a）、（b）、（c）分別為Nmin及對比方法相應(yīng)變量設(shè)置為32，64和128時三種算法效果的對比試驗圖。估計值的真值取為0.85與0.15，固定時間周期進行參數(shù)改變來模擬快速、變化差異巨大的情況。圖2的參數(shù)設(shè)置為[0.35，0.7，0.2，0.8，0.31，0.91，0.25，0.8，0.4，0.9]，每40個周期變化一次，與[3]保持一致。

可以觀察到，在不同的步長設(shè)定的情況下，除了最開始的部分，滑動窗口可以較好地追蹤參數(shù)以外，當(dāng)參數(shù)開始變化后，IWE的效果明顯優(yōu)于滑動窗口以及SSLDE：IWE在變化開始時反應(yīng)更為迅速，而滑動窗口由于數(shù)據(jù)的冗余，對于變化的反應(yīng)最慢;而在精度方面，IWE也可以在短時間內(nèi)達到更好的精度，而其余兩種方法在較短周期內(nèi)還無法達到。

5 總結(jié)

估計器在實際應(yīng)用中非常普遍，但依靠概率收斂的強估計器對數(shù)據(jù)分布的要求十分苛刻，數(shù)據(jù)需保持不變、穩(wěn)定的分布。本文首先介紹了兩種性能優(yōu)良的弱估計器，用以適應(yīng)分布隨時間改變的數(shù)據(jù)。接著介紹了一種在隨機點定位中效果優(yōu)秀的啟發(fā)式算法一自 適應(yīng)步長搜索。而本文通過將自適應(yīng)步長搜索的思想加入到弱估計器中，獲得了性能更為優(yōu)秀的弱估計器IWE，從而更好地適應(yīng)了動態(tài)變化環(huán)境。

參考文獻：

[1]B.J.Oommen and L.Rueda.Stochastic learning-based weak estimation of multinomial random variables and its applica-tions to pattern recognition in non-stationary environments[J].Pattern Recognition，2006，39（3）：328-341.

[2] A.Yazidi，B.J.Oommen，and 0.C.Granmo.A novel stochastic discretized weak es timator operating in non-stationary environments[C].International Conference on Computing，NETWORKING and Communications，2012：364-370.

[3] A.Yazidi and B.J.Oommen.Novel discretized weak estimators Based on the principles of the stochastic search on the line problem[J].IEEE Transactions on Cybernetics，2016，46（l 2）：2732-2744，2016.

[4]B.J.Oommen.Stochastic searching on the line and its applications to parameter learning in nonlinear optimization[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics，1997，27（4）：733.

[5]B.J.Oommen and G.Raghunath.Automata learning and intelligent tertiary searching for stochastic point location[J].IEEETransactions on Systems Man & Cybernetics Part B Cybernet ics，1998，28（6）：947.

[6]B.J.Oommen，G.Raghunath，and B.Kuipers.Parameter learning from stochastic teachers and stochastic compulsive liars[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics，2006，36（4）：820.

[7]D.S.Huang and W.Jiang.A general cpl-ads methodology for fixing dynamic parameters in dual environments[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics，2012，42（5）：1489-1500.

[8]A.Yazidi，O.C.Granmo，O.B.John，and M.Goodwin.A novel strategy for solving the stochastic point location problem using a hierarchical searching scheme[J].IEEE Transactions on Cybernetics，2014，44（1 1）：202-2220.

[9]T.Tao，H.Ge，G.Cai，and S.Li.Adaptive step searching for solving stochastic point location problem[C].International Conference on Intelligent Computing Theories，2013：192-198.

[通聯(lián)編輯：梁書]