一種基于極端學習機的半監督學習方法

唐 曉 亮， 韓 敏

（大連理工大學 信息與通信工程學院，遼寧 大連 116024）

0 引 言

半監督學習方法是近年來提出的一類能夠同時利用標記樣本和無標記樣本的機器學習方法[1～3]，其主要目標是通過發掘無標記樣本的信息來彌補標記樣本不足帶來的影響.很多學者在不同領域提出了較為成功的半監督學習模型.例如，Bruzzone等[4]提出了直推式支持向量機（TSVM）用于遙感影像的半監督分類；Nigam等提出基于EM 算法的高斯混合模型（EM－GMMs）[5]，該模型通過 EM 算法的迭代計算實現了利用無標記樣本和標記樣本共同調節高斯混合模型參數的目的；Zhou等提出基于3個分類器的循環訓練方法（tri－training）[6]，該方法彌補了協同訓練（co－training）[7]對標記樣本數量要求苛刻的不足，能夠更好地提高分類器的半監督學習能力.當前半監督學習方法的研究中主要存在兩個問題：（1）學習速度緩慢.例如，直推式支持向量機的學習過程實質上是一個NP問題[4]，需要消耗大量的運算時間；基于EM算法的半監督分類方法[5]迭代次數過多也會導致學習速度下降.學習速度緩慢造成半監督分類方法難以適應大數據量的分類要求.（2）不確定性遞增.半監督學習方法主要通過擴充標記樣本數量達到增加學習樣本信息量的目的，但學習樣本的不確定性也隨著自身的擴充而逐步增加[8].例如，基于自訓練的EM算法[3]對無標記樣本進行臨時標記，并將標記結果用于下次迭代訓練，被錯誤標記的學習樣本會引起學習過程中的誤差傳遞，影響學習效果.

針對上述問題，本文提出一種基于極端學習機[9、10]的半監督學習方法.其基本思想是將極端學習機從監督學習模式擴展到半監督學習模式，再利用輸出閾值向量控制標記樣本的擴充程度，采用“換位”策略評估擴充樣本中不確定性的影響.

1 極端學習機的學習模式

傳統前饋神經網絡多采用梯度下降算法調整權值參數，學習速度緩慢、泛化性能差等問題是制約前饋神經網絡應用的瓶頸[11].最近 Huang等[9、10]摒棄了梯度下降算法的迭代調整策略，提出了極端學習機算法.該算法對單隱層神經網絡的輸入權值和隱層節點偏移量進行隨機賦值，并且只通過一步計算即可解析求出網絡的輸出權值.極端學習機能夠極大地提高網絡學習速度和泛化能力.本章首先介紹極端學習機的監督學習模式，在此基礎上推導出極端學習機的半監督學習模式.

1.1 極端學習機的監督學習

單隱層神經網絡監督學習的代價函數E0可表示為

式中：N0為標記樣本總數；為隱層節點總數，表示第j個標記樣本向量（下標n表示每個樣本向量的維數，n等于輸入層節點數，表示樣本向量的類別標記向量（下標C表示類別數目，C等于網絡的輸出節點數）；wi＝ （wi1…win），表示連接網絡輸入層節點與第i個隱層節點的輸入權值向量；bi表示第i個隱層節點的偏移量；g（·）表示隱層節點的激活函數；βi＝ （βi1…βiC）T，表示連接第i個隱層節點與網絡輸出層節點的輸出權值向量.

Huang等[9、10]指出最小化E0等價于找到滿足下式的特殊解和

式中：H0表示網絡關于標記樣本的隱層輸出矩陣；β表示輸出權值矩陣；T0表示標記樣本集的類別標記矩陣.H0、β、T0分別定義如下：

Huang等[9、10]嚴格地證明了當網絡隱層節點的激活函數無窮可微時，網絡的輸入權值和偏移量可直接隨機賦值而不必采用梯度下降算法迭代調整.因此單隱層神經網絡的監督學習過程可等價為求取線性系統H0β＝T0的范數最小的最小二 乘 解 （minimum norm least－squares solution），如式（5）所示：

其中是矩陣H0的 Moore－Penrose廣義逆[12]，在rank（H0）＝N珦的條件下可由正交投影方法求得.

（1）對網絡的輸入權值向量wi和隱層節點偏移量bi進行隨機賦值

（2）按照式（3）計算隱層輸出矩陣H0；

1.2 極端學習機的半監督學習

關于極端學習機的已有研究均是在監督學習模式下進行的[9、10]，本節將極端學習機的學習模式擴展到半監督領域.首先考慮單隱層網絡半監督學習的代價函數[9]：

式（7）右邊第2項為擴充的標記樣本誤差累加項；Ne表示擴充的標記樣本的數目，表示第j個擴充的標記樣本向量，表示的類別標記向量.

最小化半監督學習的代價函數等價于找到滿足下式的特殊解：

其中He表示網絡關于擴充標記樣本的隱層輸出矩陣，Te表示擴充標記樣本集的類別標記矩陣，分別定義如下：

式（8）的右邊可進一步推導如下：

與式（5）同理，可以求出滿足式（11）的范數最小的最小二乘解

與式（6）同理，可以進一步推出的具體形式：

其中

除了計算輸出權值矩陣，極端學習機的半監督學習過程還涉及如何擴充標記樣本以及評估不確定性等操作，第2章將對所有相關步驟進行詳細描述.

2 基于極端學習機的半監督學習方法流程

基于極端學習機的半監督學習方法主要包括4個步驟：初始訓練、標記樣本擴充、不確定性的換位評估和輸出權值計算.

2.1 方法流程歸納

初始輸入：初始標記樣本集L0，無標記樣本集U，單隱層神經網絡的隱層節點數.

步驟1 初始訓練

（1）對網絡的輸入權值矩陣W＝（wi）和隱層節點偏移向量B＝ （bi）進行隨機賦值，i＝1，2，…，；

（2）按照式（3）計算關于初始標記樣本集L0的網絡隱層輸出矩陣H（W，B，L0）；

（3）按照式（5）和（6）計算網絡的隱層輸出權值矩陣；

（4）計算輸出閾值向量Θ：

①計算網絡輸出層的初始輸出矩陣

其中O0表示網絡關于集合L0的輸出層輸出矩陣，具體形式為N0表示集合L0的樣本總數.

②計算網絡的輸出閾值向量

其中θk表示關于類別k的網絡輸出閾值，θk＝為初始標記樣本集L0中屬于類別k的樣本數目；表示O0中第j行第k列元素值；Δ∈（0，1），表示輸出裕量參數；分段函數定義如下：

（5）存儲輸入權值矩陣W＝ （wi）、偏移向量B＝ （bi）和初始輸出權值矩陣

步驟2 標記樣本擴充

（1）計算關于無標記樣本集U的輸出層輸出矩陣：

其中H（W，B，U）表示網絡關于無標記樣本集U的隱層輸出矩陣，OU表示網絡關于無標記樣本集U的輸出層的輸出矩陣，具體定義如下：H（W，B，U）＝

xU1，…，xUNU為集合U中的無標記樣本向量，下標NU表示集合U中無標記樣本向量的總數.

（2）構建擴充標記樣本集合Le

步驟3 不確定性的換位評估

因為無法直接評估擴充樣本中的不確定性對分類結果的影響，所以采用標記樣本集與擴充標記樣本集交換位置的策略間接評估不確定性的影響.

（1）僅以擴充標記樣本集Le為學習樣本集，計算對應的輸出權值矩陣：

其中為利用Le訓練的網絡輸出權值矩陣，表示Le的類別標記矩陣，H（W，B，Le）是網絡隱層輸出矩陣H（W，B，Le）的 Moore－Penrose廣義逆，H（W，B，Le）的計算過程可參照式（6）.

（2）以初始標記樣本集L0為測試對象，檢驗擴充標記樣本集的不確定性：

其中ρ＞0，表示不確定性閾值.

如果能夠滿足式（23），證明擴充樣本的不確定性不足以影響分類結果，轉到步驟4；否則，將Le中的樣本清除，并增大輸出閾值Θ，

轉到步驟2重新擴充標記樣本.

步驟4 輸出權值計算

（1）針對樣本集合L0和Le，以W為輸入權值矩陣、B為偏移向量，計算網絡的輸出權值矩陣

具體計算過程可參照式（12）～（14）.

（2）判斷

極端學習機的分類過程如下：

（1）根據學習結果（W，B，），計算網絡關于測試樣本集合Ω的輸出層輸出矩陣OΩ：

其中

NΩ為測試樣本的數目，C為類別數目.

2.2 關鍵參數的作用和選擇策略

在半監督學習過程中，式（17）的輸出裕量參數Δ和式（23）的不確定性閾值ρ對算法的成績影響較大.其中Δ影響無標記樣本向標記樣本轉化的難易程度，Δ越大無標記樣本越容易轉化為標記樣本，反之越難；ρ控制換位評估過程中的分類誤差上限，ρ越小表示算法允許的誤差上限越低，算法對不確定性的敏感性就越高，算法的重復次數也越多.

Δ與ρ的取值范圍均為（0，1），仿真實驗采用基于交叉檢驗（cross validation）[13]的網格搜索法對這兩個參數進行選擇，交叉檢驗方法可以保證參數的無偏估計.具體過程如下：（1）Δ與ρ取離散值（例如，Δ＝ …，10－4，10－3，…，10－1，…；ρ＝ …，10－4，10－3，…，10－1，…）構成網格；（2）計算在網格對應的每個參數對（如（Δ，ρ）＝ （10－1，10－1））處的交叉檢驗值在最大交叉檢驗值對應的參數對附近區域進行更為精細的網格搜索.例如，初始得到的最優參數對為（Δ，ρ）＝ （10－1，10－1），則在（10－1，10－1）周圍進行精細網格搜索（Δ＝ …，0.8×10－1，0.9×10－1，10－1，1.1×10－1，1.2×10－1，…；ρ＝ …，0.8×10－1，0.9×10－1，10－1，1.1×10－1，1.2×10－1，…），直至確定最優參數值.

3 仿真實驗

為驗證本文所提方法的有效性，對扎龍自然保護區遙感數據集[14]、UCI機器學習數據庫[15]中的3組數據集以及2組半監督學習基準數據集[1]進行分類仿真.每組樣本的個數、類別數等相關信息如表1所示.為了全面檢驗半監督學習方法的學習速度和泛化能力，將每組訓練樣本中的標記樣本和無標記樣本的比例按1∶1、1∶2和1∶3進行分配，分別求取半監督學習方法在不同分配比例條件下的學習時間和分類精度.

采用改進型 TSVM 方法（NTSVM）[4]、EMGMMs方法[5]和本文提出的基于極端學習機的半監督學習方法（下文簡稱ssELM）對實驗數據進行分類.所有程序均在Matlab 7平臺上運行，計算機CPU為Pentium IV 2.0 GHz，內存512 MB.3種方法的半監督學習時間和分類精度分別如表2和3所示.

通過仿真結果可以看出，NTSVM方法雖然能夠取得較高的分類精度，但仍需消耗大量的學習時間，而且隨著無標記樣本比例的上升學習時間明顯增加.EM－GMMs方法對標記樣本的依賴程度較高，其分類精度隨標記樣本比例的減小而大幅度下降.與其他兩種半監督學習方法相比，本文所提方法能夠顯著提高半監督學習的速度；同時受無標記樣本比例變化的影響較小，在無標記樣本比例增大的情況下仍能取得較高的分類精度.

表1 實驗樣本相關信息Tab.1 Information of experimental samples

表2 三種方法對6組實驗數據的半監督學習時間Tab.2 Semi－supervised learning time of three methods for six experimental data sets s

表3 三種方法對6組實驗數據的分類精度Tab.3 Classification accuracies of three methods for six experimental data sets %

如表3所示，在標記樣本與無標記樣本比例為1∶1和1∶2時，ssELM方法對數據集g241d的分類精度比NTSVM方法稍低.這是因為初始標記樣本集中包含的異常點較多，導致ssELM方法對不確定性檢測的精度有所下降.減少標記樣本集中的異常點影響是半監督學習方法性能穩定的關鍵.實驗結果證明本文所提方法能夠有效地發掘無標記樣本中的有用信息，并在一定程度上抑制樣本擴充帶來的不確定性增加等問題.

4 結 論

學習速度緩慢、不確定性遞增是半監督學習方法存在的兩大問題，針對這些問題本文提出一種基于極端學習機的半監督學習方法.該方法主要包括初始訓練、標記樣本擴充、不確定性的換位評估和輸出權值計算4個步驟.該方法將極端學習機從監督學習模式擴展到半監督學習模式，極大地提高了半監督學習的速度.在半監督學習過程中，該方法利用輸出閾值向量控制標記樣本的擴充程度，以標記樣本和擴充樣本之間的換位策略評估不確定性對學習效果的影響.仿真結果證明了本文所提方法在提高半監督學習速度、抑制不確定性增加以及提高分類精度等方面的有效性.

[1]CHAPELLE O， SCHLKOPF B， ZIEN A.Semi－supervised Learning [M]. Cambridge：MIT Press，2006

[2]孫廣玲，降 龍.基于分層高斯混合模型的半監督學習算 法 [J].計 算 機 研 究 與 發 展，2004，41（1）：156－161

[3]張博鋒，白 冰，蘇金樹.基于自訓練EM算法的半監督文本分類[J].國防科技大學學報，2007，29（6）：65－69

[4]BRUZZONE L，CHI M M，MARCONCINI M.A novel transductive SVM for semisupervised classification of remote－sensing images [J].IEEE Transactions on Geoscience and Remote Sensing，2006，44（11）：3363－3373

[5]NIGAM K，MCCALLUM A K，THRUN S，etal.Text classification from labeled and unlabeled documents using EM [J].Machine Learning，2000，39（2－3）：103－134

[6]ZHOU Z H，LI M.Tri－training：Exploiting unlabeled data using three classifiers[J].IEEE Transactions on Knowledge and Data Engineering，2005，17（11）：1529－1541

[7]WANG W，ZHOU Z H.Analyzing co－training style algorithms[C]//Proceedings of the 18th European Conference on Machine Learning （ECML′07）.Poland：Springer－Verlag，2007：454－465

[8]COHEN I， COZMAN F G，SEBE N，etal.Semisupervised learning of classifiers：theory，algorithms，and their application to human－computer interaction [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（12）：1553－1566

[9]HUANG G B，ZHU Q Y，SIEW C K.Extreme learning machine：Theory and applications [J].Neurocomputing，2006，70（1－3）：489－501

[10]HUANG G B，ZHU Q Y，MAO K Z，etal.Can threshold networks be trained directly？[J].IEEE Transactions on Circuits and Systems II－Express Briefs，2006，53（3）：187－191

[11]李鴻儒，顧樹生.一種遞歸神經網絡的快速并行算法[J].自動化學報，2004，30（4）：516－522

[12]SERRE D.Matrices：Theory and Applications[M].New York：Springer－Verlag，2002：145－147

[13]SUNDARARAJAN S，SHEVADE S，KEERTHI S S.Fast generalized cross－validation algorithm for sparse model learning [J].Neural Computation，2007，19（1）：283－301

[14]韓 敏，程 磊，唐曉亮.Fuzzy ARTMAP神經網絡在土地覆蓋分類中的應用研究 [J].中國圖象圖形學報，2005，10（4）：415－419

[15]ASUNCION A，NEWMAN D J.UCI machine learning repository[DB/OL].[2008－03－26].http：//www.ics.uci.edu/ ～ mlearn/ MLRepository.html