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

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

中圖分類號(hào)：TP3

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

文章編號(hào)：1009-3044（2020）04-0244-03

收稿日期：2019-11-21

作者簡(jiǎn)介：王春輝，同濟(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ì)器簡(jiǎn)介

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結(jié)

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