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

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

中圖分類號：TP3

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

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

收稿日期：2019-11-21

作者簡介：王春輝，同濟(jì)大學(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 弱估計(jì)器簡介

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

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

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

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

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

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

同樣使用1/0信號作為環(huán)境與LM的交互，隨機(jī)點(diǎn)定位（Stochastic Point Location，SPL）問題旨在找到給定區(qū)間內(nèi)最優(yōu)的參數(shù)。不失一般性，我們可以將所有問題的給定區(qū)間投影到[0，1]區(qū)間中。SPL 問題同樣使用一個LM表示當(dāng)前對該區(qū)間內(nèi)最優(yōu)值的估計(jì)，通過環(huán)境的反饋確定LM向左移動還是向右移動來逼近最優(yōu)點(diǎn)。大量行之有效的算法[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é)果則精度難以達(dá)到要求。

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

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

3 對弱估計(jì)器的改進(jìn)

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

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

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

4 實(shí)驗(yàn)比較

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

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

圖1（a）、（b）、（c）分別為Nmin及對比方法相應(yīng)變量設(shè)置為32，64和128時三種算法效果的對比試驗(yàn)圖。估計(jì)值的真值取為0.85與0.15，固定時間周期進(jìn)行參數(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)達(dá)到更好的精度，而其余兩種方法在較短周期內(nèi)還無法達(dá)到。

5 總結(jié)

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

參考文獻(xià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)編輯：梁書]