基于自適應步長搜索的弱估計器算法

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

關鍵詞：弱估計器;分布;動態變化;自適應步長搜索

中圖分類號：TP3

文獻標識碼：A

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

收稿日期：2019-11-21

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

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 弱估計器簡介

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

然而隨著計算資源性能的提升以及基礎網絡設施的發展，應用需要解決越來越復雜、多變的問題是難以避免的趨勢，其中也包括應用處理的數據分布保持動態的變化。需要估計變化分布的估計器，稱為弱估計器[1]。

滑動窗口作為較為直觀的算法，可以用作弱估計器，適應分布底層參數變化的情景，通過最近的數據得到當前時刻參數的預估值?；瑒哟翱诓捎霉潭ù笮〉目臻gN sw 存儲最近得到的數據用，但其性能也極大地受限于窗口的大小。當滑動窗口過大時，窗口內數據過多，分布發生變化時，窗口內大多為舊分布的數據，滑動窗口難以做出迅速的反應，導致追蹤分布變化的速度慢、時間長;當滑動窗口過小時，雖然可以較好地跟蹤參數變化，但可存儲的數據量有限，很難達到精度的要求，且受數據的影響，估計值波動較大。

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

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

2 自適應步長搜索

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

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

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

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

3 對弱估計器的改進

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

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

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

4 實驗比較

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

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

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

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

5 總結

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

參考文獻：

[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.

[通聯編輯：梁書]