基于學習自動機的容噪模式分類

摘要：在模式分類學習問題中，訓練數據中的標注差錯（也稱類別噪聲）對分類器的性能有很大的影響。本文將一種新近提出的連續動作學習自動機（即聚焦區間學習自動機）應用于針對類別噪聲的容噪學習問題。分類器采用簡單的單隱層前饋神經網絡，利用一個由這種學習自動機組成的自動機團隊，對神經網絡的權值參數進行學習。通過廣義異或問題和Iris數據集的仿真試驗，將該算法與兩種基于群體搜索的優化算法——粒子群優化（PSO）和差分進化（DE）進行了比較研究。結果表明，新算法具有更好的容噪學習性能。

關鍵詞：模式分類；類別噪聲；容噪學習；學習自動機；連續動作學習自動機

中圖分類號：TP181文獻標識碼：ADOI：10.19452/j.issn1007-5453.2020.10.012

模式分類是機器學習領域中的一個重要課題，相關研究非常活躍。以航空領域為例，無人機的目標檢測、飛機部件的故障診斷等都屬于模式分類問題[1-2]。分類器的構造可以視為一種學習過程，即通過對一個經標注的數據集（訓練集）的學習，建立從特征空間到類別空間的映射關系。顯然，訓練數據的質量對最終的學習結果會有影響。在傳統的學習理論中，用于訓練的數據是不含噪聲的。但實際應用中的訓練數據未必都這樣理想，當其中含有噪聲時，訓練出的分類器的性能有可能大打折扣。訓練數據中的噪聲可分為屬性噪聲和類別噪聲兩大類[3-5]。屬性噪聲也稱特征噪聲，是指訓練樣本中的特征參數受到了噪聲的干擾。類別噪聲也稱標注噪聲，是指一個樣本被賦予了不正確的類別標簽。

研究表明[3-5]，相對于特征噪聲，類別噪聲通常具有更大的潛在危害。許多著名的分類方法（如支持向量機及AdaBoost等）對類別噪聲都很敏感。由于獲取可靠的標注數據昂貴而費時，故標注工作不一定總由領域專家來完成，尤其在互聯網和大數據背景下，經常是由非專業人員甚至計算機自動完成的。這就有可能引入標注噪聲。在某些場合，如疾病或設備故障的診斷等，因問題的復雜性，即使專家標注的數據也不能保證100%的準確。因此，研究針對類別噪聲的容噪學習技術，具有十分重要的意義。

應對類別噪聲的最常用的一種方法是先通過某種技術，識別并過濾掉訓練數據中被錯誤標注的數據樣本，再用正確無誤的數據集進行學習。參考文獻[6]提出一種基于距離的檢測方法，以發現異常數據樣本。參考文獻[7]采用模型過濾法，剔除錯標的數據。參考文獻[8]利用交叉驗證的方法，對數據中的孤立點進行鑒別和篩選。對付類別噪聲的另一種方法，是采用具有容噪能力的學習算法。參考文獻[9]針對多核學習問題，提出一種基于復合梯度映射的學習算法，但其中有一個假設，即標注差錯的概率是已知的。這會限制其實用性，因為在實際中該概率很難預先知道。參考文獻[10]提出一種基于混合模型的穩健判別方法，其中也有個假設，即樣本總體是正態分布的。參考文獻[11]和參考文獻[12]在不對訓練樣本做特別假設的情況下，將一類連續動作學習自動機應用于類別噪聲下的容噪學習，取得了很好的結果，不過其學習對象僅限于線性的二分類問題。

本文嘗試將一種較新的連續動作學習自動機，即基于窗口-獎勵的聚焦區間學習自動機[13-15]，應用于非線性多分類問題的容噪學習。

1學習自動機

學習自動機（learning automata，LA）是一類自適應決策算法。自動機通過與一個隨機環境的不斷交互，學習最佳的輸出動作[16]。在任一時刻，LA根據某種概率分布，從其動作集里選擇一個動作并輸出給環境；環境則反饋一個強化信號，作為對LA所選動作的評價。根據該評價，LA更新其概率分布，以期下次能選出更合適的動作。作為一種隨機優化方法，LA很適合處理具有非線性及不確定性的優化問題。

根據動作集的性質，LA可以分為有限動作學習自動機（finite-action learning automata，FALA）和連續動作學習自動機（continuous-action learning automata， CALA）兩大類。FALA適合處理組合優化問題，CALA則適合處理連續型的數值優化問題，如神經網絡權值的訓練。

2 FILA/WR

現有的幾種CALA都是采用高斯分布作為其動作選擇的概率模型，自動機通過不斷調整高斯分布的均值和標準差實現學習[16]。與此不同，本文作者提出一種新的CALA[13-15]，其利用一個可變區間作為動作集，并按照均勻分布方式產生輸出動作。學習算法根據一個滑動窗口內的最佳的歷史動作，對區間的兩個端點進行更新。由于該自動機對動作區間的更新類似于一種調焦或對焦，故稱之為聚焦區間學習自動機（focused interval learning automaton， FILA）。

記動作區間為[xL，xR]。為對其進行更新，算法保持一個滑動窗口W={（x（i）， J（i））|i=k-M+1，…， k}，其中（x（i）， J（i））為最近的自動機與環境交互的歷史記錄（輸出的動作參數及相應的目標函數值），x（i）代表在i時刻自動機選出的動作參數，J（i）是x（i）的目標函數J（x（i））的簡寫。為高效實現，W采用環形隊列的方式存儲最近的M對x和J。M為窗口大小。

在任一時刻k，自動機以均勻分布方式在當前的區間上隨機選擇一個實數x（k），稱為動作，并從環境得到對應的目標函數J（k）。將x（k）和J（k）放入W中。然后，找出其中具有最小J（x）值的動作（針對最小化問題），將其記為xb。再根據xb對區間的兩個端點進行更新。

因該算法總關注一個滑動窗口，并將動作區間朝窗口內最佳的動作xb的方向調整，相當于對xb進行獎勵，故可進一步將其記做FILA/WR，其中W與R分別代表窗口（window）和獎勵（reward）。我們曾將該算法應用于不同的問題，如被噪聲污染的多模態函數的全局優化[13]、非線性系統辨識與建模[14]以及動態不確定性環境下的在線學習[15]。在這些應用中，FILA/WR在學習精度、運行結果的一致性尤其是最差情況下的性能表現，都有明顯的優勢。

3仿真試驗

本文嘗試將上述FILA/WR應用于針對類別噪聲的容噪模式分類問題。分類器采用單隱層前饋神經網絡，利用該算法對網絡的權值參數進行學習。訓練前饋神經網絡的經典方法是誤差反傳（BP）算法。這是一種梯度下降方法，很容易陷入局部最優。近些年來，以遺傳算法（GA）、粒子群優化（PSO）以及差分進化（DE）為代表的基于群體計算的智能優化算法，被廣泛應用于神經網絡的訓練。為檢驗FILA/WR的學習性能，本文選擇目前流行的PSO[17]和DE[18]進行對比試驗。DE有多個版本，本文采用的是DE/rand/1/ bin版本，其在工程優化問題中應用最為廣泛。

我們選取了兩個測試問題，一個是廣義異或問題，一個是鳶尾花數據集。前者屬于二分類問題，后者則屬于多分類問題。對每個問題，分別在訓練樣本中人為地引入不同強度的類別噪聲，以測試學習算法的容噪性能。

3.1廣義異或問題的試驗

廣義異或問題是一個2特征、2類別的人造分類問題。設模式空間為x-y平面內的矩形區域[-1，1]×[-1，1]。該區域內的任一點p（x，y）屬于兩個類別之一：位于第一、第三象限內的點為A類，位于第二、第四象限內的點為B類。即A類點的x、y坐標同號，B類點的x、y坐標異號。這是一個典型的非線性可分問題，其可以看作是二值的異或（XOR）問題在連續域的推廣。參考文獻[19]曾利用基于PSO和BP混合訓練的神經網絡來解決該問題，但其訓練數據不含噪聲，且網絡結構比較復雜，為雙隱層。

本文采用一個單隱層的前饋神經網絡，網絡結構為2-8-1。其中有兩個輸入節點，分別對應待分類模式的x和y坐標；一個輸出節點，代表類別標簽：1表示A類，-1表示B類；一個隱藏層，包含8個節點。整個網絡一共有33個需要確定的權值參數（包括閾值）。所有節點的激活函數均采用雙曲正切函數。由于一個自動機只處理一個參數，故使用33個FILA，每個自動機負責一個參數。33個自動機構成一個LA團隊[14]，以合作博弈的方式學習網絡的最佳權值。

在區域[-1，1]×[-1，1]中隨機抽取2000個點作為訓練樣本，再在同一區域以x、y坐標均按0.02的間隔均勻抽取10000個點作為測試樣本。為檢驗學習算法的容噪性能，對訓練樣本中的類別標記進行人為翻轉（即A變B、B變A），以引入類別噪聲。其中噪聲強度（錯誤標簽在訓練樣本中所占的比例）分別取0（即無噪聲），10%，20%，30%和40%。訓練采用批次方式，即對于PSO、DE或FILA團隊產生的每一組權值參數，計算所有訓練樣本下網絡輸出節點的均方誤差，以此作為該組權值參數的目標函數。一次仿真，總共評估10000個目標函數值。

FILA的內部參數設置如下：M=20，λ=0.005，δ=0.01。對于PSO和DE，先分別進行若干次試探性試驗，然后取效果較好的參數組合，具體情況如下：PSO中粒子群的規模為50，慣性權重w為0.5，加速度常數（學習因子）c1和c2均為1.5，每一維的最大速度取vmax_ratio*di，其中di為相應維初始搜索區間的長度，vmax_ratio為0.2。對于DE，群體規模NP取25，縮放因子F取0.3，交叉概率CR取0.8。對每種算法，33個待優化權值的初始搜索區間均取[-2，2]。

訓練結束后，PSO和DE取群體中的最優解（即目標函數最小的權值參數），FILA則取最終每個動作區間的中點所構成的權值參數。再利用權值參數分別為這三組值的神經網絡對測試集進行分類，當輸出節點的激活值大于0時判定為1（即A類），否則判定為-1（即B類）。

為獲得可靠的結論，在每一種噪聲水平下，分別用三種算法各做100次獨立試驗（每次訓練集及標注噪聲都重新產生，但各算法相同），統計訓練好的神經網絡在測試集上的分類結果。表1給出了不同噪聲水平下三種算法得到的識別率的平均值及標準差。

由表1可以看出，在不含噪聲的情況下，三種算法均獲得了98%左右的平均識別率（FILA最好，DE最差）。參考文獻[19]中，5次試驗的平均識別率為99.55%，但其所用的神經網絡為較復雜的雙隱層結構，且采用PSO和BP結合的訓練方法；該文也沒有研究訓練樣本含有噪聲的情況。

由表1可知，當訓練數據含有標注噪聲時，三種算法訓練出的神經網絡的性能會有所下降，但下降幅度比樣本差錯的比率要小得多。即使在40%的噪聲水平下（訓練樣本的標注正確率只有60%），DE也有超過86%，PSO和FILA則有超過88%的平均識別率。這說明，神經網絡本身就具有較好的噪聲容忍能力，其“記住”的是訓練集的整體特征。由表1還可看出，5種情況下，FILA的平均識別率有三次高于PSO，兩次低于PSO，而標準差則有4次小于PSO，僅有一次大于PSO，這表明其性能更穩定，結果的一致性更好。相比之下，DE的效果最差，其不僅平均分類正確率低，標準差也比較大。

其實，我們還曾利用經典的誤差反傳（BP）算法訓練上述網絡，但其效果極不穩定。僅就不含噪聲的情況而言，BP有時很快就找到了識別率高達100%的網絡權值，但有時卻僅得到50%的識別率（此時神經網絡對輸入樣本的反應完全是隨機的）。仔細分析發現，這是由于訓練陷入了誤差曲面的平坦區域，因梯度過小（<10-10）而導致訓練提前中止，網絡權值沒有收斂。鑒于此，后文將不再考慮BP，僅對FILA、PSO和DE進行仿真。

3.2 Iris數據集的試驗

鳶尾花（Iris）分類是模式識別和數據挖掘領域中一個被廣泛引用的經典問題。有三種鳶尾屬植物，分別稱作iris-setosa，iris-versicolor和iris-virginica。每一品種各采集了50個樣本，每個樣本包含4個特征參數：萼片的長度和寬度、花瓣的長度和寬度。我們的任務是構造一個分類器，用以識別任一給定的數據樣本屬于三個品種中的哪一個。這是一個4特征、3類別的分類問題，其中iris-setosa與另兩個類別是線性可分的，后兩者則不是線性可分的。參考文獻[19]～[21]曾用不同的方法對該問題做過試驗研究，其中參考文獻[21]還考慮了訓練數據中含有屬性噪聲的問題，但都沒有考慮類別噪聲。參考文獻[11]和參考文獻[12]采用一種基于高斯分布的CALA來解決類別噪聲下Iris數據集的容噪學習問題，但其工作僅限于線性的二分類問題（將iris-setosa作為一類，另外兩類則合并為一個大類）。

本文采用一個4-5-3結構的神經網絡，解決上述Iris數據集的三分類問題，分別利用PSO、DE和FILA來學習網絡的43個權值參數。試驗所用的數據來自UCI數據集。因該數據集的特征參數未歸一化，故網絡權值的初始搜索區間取得小一些，為[-0.5，0.5]。訓練時，從150個數據樣本中隨機抽取90個（每一品種各30個）作為訓練集。訓練結束后，用所有數據樣本（包括訓練樣本，但不加噪聲）進行測試。測試時，網絡的三個輸出采用“高勝”邏輯。

試驗發現，前面針對廣義異或問題設置的DE的那一組參數，對Iris數據集的學習效果相當差。為此，我們重新試探了其參數組合，最終選用的是：NP=20，F=0.4，CR=0.8。PSO和FILA的內部參數仍沿用前一試驗的設置。試驗結果見表2。

由表2可以看出，在訓練數據不含噪聲的情況下，三種算法的平均分類正確率均在96%左右（FILA略高于97%）。參考文獻[20]采用交叉驗證K近鄰算法，得到的識別率為96.67%。參考文獻[19]的5次試驗的平均識別率為98.53%，但其網絡有兩個隱藏層，結構較復雜，且其訓練方法同時使用了PSO和BP。這些文獻均未考慮訓練數據含有噪聲的問題。

再看訓練數據包含類別噪聲的情況。由表2可以看出，對于Iris數據集，FILA在每種噪聲水平下的平均識別率都比PSO和DE的高。在訓練數據含有40%的標注噪聲的情況下，FILA仍可獲得接近92%的分類精度（PSO和DE則不到89%）。另外，與PSO和DE相比，FILA的標準差更小，這說明其魯棒性更好。與第一個試驗不同的是，對Iris數據集，除噪聲水平為40%的情況外，PSO的結果總差于DE。這說明，在這兩種算法中，沒有哪個更具優勢。

前面說過，在Iris數據集的試驗中，對DE的內部參數進行了重新設置。如果沿用第一個試驗中的參數，則學習結果明顯差于表2中的數據。反過來，上述的對于Iris數據集效果較好的這組參數，當應用于廣義異或問題時，效果也遠差于表1中的結果。這說明DE對于要解決的問題較為敏感，不同的問題需要不同的算法參數。

4結束語

訓練樣本中的標注噪聲對分類器的學習構成很大的挑戰。本文研究了神經網絡分類器的容噪學習問題，其中的訓練數據允許存在類別噪聲。我們將一種新近提出的FILA/WR算法應用于神經網絡權值的學習。該方法既不需要對訓練數據進行預處理，也無須樣本噪聲的任何先驗知識。

通過廣義異或問題和Iris數據集，對該算法和兩種流行的群體優化算法——PSO和DE算法進行了試驗比較。結果表明，在各種噪聲水平下，由新算法訓練出的神經網絡具有更好的分類性能。該算法容噪能力強，結果穩定性好。另外，與DE相比，新算法的內部參數對于待求解的問題不敏感，因而更易于使用。下一步，我們擬將該算法應用于航空領域中的一些機器學習問題，如基于神經網絡的發動機故障診斷和壽命預測等。

參考文獻

[1]王曉華，張聰，李聰，等.基于仿生視覺注意機制的無人機目標檢測[J].航空科學技術， 2015， 26（11）： 78-82. Wang Xiaohua， Zhang Cong， Li Cong， et al. Unmanned aerial vehicles target detection based on bio-inspired visual attention[J]. Aeronautical Science & Technology， 2015， 26（11）： 78-82.（in Chinese）

[2]熊天旸，張先輝，李新民，等.基于BP神經網絡的自動傾斜器軸承故障診斷[J].航空科學技術， 2017， 28（11）： 69-73. Xiong Tianyang， Zhang Xianhui， Li Xinmin， et al. Fault diagnosis method of swash-plate bearing based on BP neural networks[J]. Aeronautical Science & Technology， 2017， 28（11）： 69-73. （in Chinese）

[3]Zhu Xingquan，Wu Xindong. Class noise vs. attribute noise：a quantitative study[J]. Artificial Intelligence Review，2004，22（3）：177-210.

[4]Fréncy B，Verleysen M. Classification in the presence of label noise：a survey[J]. IEEE Transactions on Neural Networks and Learning Systems，2014，25（5）：845-869.

[5]宮辰，張闖，王啟舟.標簽噪聲魯棒學習算法研究綜述[J].航空兵器， 2020， 27（3）： 20-26. Gong Chen， Zhang Chuang， Wang Qizhou. A survey of label noise robust learning algorithms[J]. Aero Weaponry， 2020， 27（3）： 20-26. （in Chinese）

[6]Knorr E M，Ng R T，Tucakov V. Distance-based outliers：algorithms and applications[J]. VLDB Journal，2000，8（3）：237-253.

[7]Brodley C E，Friedl M A. Identifying mislabeled training data[J]. Journal of Artificial Intelligence Research，2011，11（1）：131-167.

[8]張健沛，楊顯飛，楊靜.交叉驗證容噪分類算法有效性分析及其在數據流上的應用[J].電子學報， 2011， 39（2）： 378-382. Zhang Jianpei， Yang Xianfei， Yang Jing. Effectiveness analysis and application in data streams of cross validation noisetolerance classification algorithm[J]. Acta Electronica Sinica， 2011， 39（2）： 378-382. （in Chinese）

[9]龍文光，劉益和.多核學習中基于復合梯度映射的學習算法研究[J].計算機應用研究， 2015， 32（4）： 1019-1023. Long Wenguang， Liu Yihe. Research on learning algorithm based on composite gradient mapping in multiple kernel learning[J]. Application Research of Computers， 2015， 32（4）： 1019-1023. （in Chinese）

[10]朱德剛.一個穩健判別方法及應用[J].數學的實踐與認識， 2019， 49（6）： 161-165. Zhu Degang. A robust discriminant approach and its application[J]. Mathematics in Practice and Theory， 2019， 49（6）： 161-165.（in Chinese）

[11]Sastry P S，Nagendra G D，Manwani N. A team of continuousaction learning automata for noise-tolerant learning of halfspaces[J].IEEETransactionsonSystems，Man，and Cybernetics，Part B，2010，40（1）：19-28.

[12]Manwani N，Sastry P S. Noise tolerance under risk minimization[J]. IEEE Transactions on Cybernetics，2013，43（3）：1146-1151.

[13]劉曉.一種魯棒的連續動作學習自動機[C]//全國抗惡劣環境計算機第二十五屆學術年會， 2015： 266-271. Liu Xiao. A robust continuous-action learning automaton [C]// CCF TCSEC. Proceedings of 25th Severe Environment Computer Conference， 2015： 266-271. （in Chinese）

[14]劉曉.基于智能計算的非線性系統辨識與建模[C]//全國抗惡劣環境計算機第二十五屆學術年會， 2015： 251-255. Liu Xiao. Nonlinear system identification and modeling based on intelligent computation[C]//CCF TCSEC. Proceedings of 25th Severe Environment Computer Conference， 2015： 251-255. （in Chinese）

[15]劉曉.一種求解動態及不確定性優化問題的新方法[J].微電子學與計算機， 2016， 33（7）： 83-88. Liu Xiao. A new method for solving dynamic and uncertain optimization problems[J]. Microelectronics & Computer， 2016， 33（7）： 83-88. （in Chinese）

[16]Thathachar M A L，Sastry P S. Varieties of learning automata：an overview[J]. IEEE Transactions on Systems，Man，and Cybernetics，Part B，2002，32（6）：711-722.

[17]Kennedy J，Eberhart R C. Particle swarm optimization[C]// Proceedings of IEEE Internal Conference on Neural Networks. Piscataway：IEEE，1995.

[18]Das S，Suganthan P N. Differential evolution：a survey of the state-of-the-art[J]. IEEE Transactions on Evolutionary Computation，2011，15（1）：27-54.

[19]田雨波，潘朋朋.混合粒子群算法優化神經網絡的研究[J].微電子學與計算機， 2011， 28（6）： 156-159. Tian Yubo， Pan Pengpeng. The research of neural network based on hybrid particle swarm optimization[J]. Microelectronics& Computer， 2011， 28（6）： 156-159. （in Chinese）

[20]汪慶華，劉江煒，張蘭蘭.交叉驗證K近鄰算法分類研究[J].西安工業大學學報， 2015， 35（2）： 119-124. Wang Qinghua， Liu Jiangwei， Zhang Lanlan. Study on the classification of K-nearest neighbor algorithm[J]. Journal of Xian Technological University， 2015， 35（2）： 119-124. （in Chinese）

[21]蔣雯，陳運東，湯潮，等.基于樣本差異度的基本概率指派生成方法[J].控制與決策， 2015， 30（1）： 71-75. Jiang Wen， Chen Yundong， Tang Chao， et al. Determination of basic probability assignment based on sample difference degree[J]. Control and Decision， 2015， 30（1）： 71-75. （in Chinese）

（責任編輯王為）

作者簡介

劉曉（1965-）男，高級工程師。主要研究方向：動力控制和智能計算。

Tel：029-89186505

E-mail：xiao.liu@163.com

Noise-Tolerant Pattern Classification Based on Learning Automata

Liu Xiao*

AVIC Xian Aeronautics Computing Technique Research Institute，Xian 710065，China

Abstract： In the learning problem of pattern classification， the label error （also called class noise） in the training data can severely impact the performance of the classifiers. A recently proposed continuous-action learning automaton， i.e.， the focused interval learning automaton is applied to the noise-tolerant learning for the class noise. The classifiers adopt simple single hidden-layer feed-forward neural networks. A team of such learning automata is used to learn the weight parameters of the network. Simulations are carried out which employ the new algorithm and two populationbased optimization algorithms， particle swarm optimization （PSO） and differential evolution （DE）， respectively， on the generalized XOR problem and the Iris dataset. The simulation results indicate that the new algorithm can obtain better noise-tolerant learning performance compared with the PSO and DE.

Key Words： pattern classification； class noise； noise-tolerant learning； learning automata； continuous-action learning automata