一種基于極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)方法

唐 曉 亮， 韓 敏

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

0 引 言

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

針對(duì)上述問題，本文提出一種基于極端學(xué)習(xí)機(jī)[9、10]的半監(jiān)督學(xué)習(xí)方法.其基本思想是將極端學(xué)習(xí)機(jī)從監(jiān)督學(xué)習(xí)模式擴(kuò)展到半監(jiān)督學(xué)習(xí)模式，再利用輸出閾值向量控制標(biāo)記樣本的擴(kuò)充程度，采用“換位”策略評(píng)估擴(kuò)充樣本中不確定性的影響.

1 極端學(xué)習(xí)機(jī)的學(xué)習(xí)模式

傳統(tǒng)前饋神經(jīng)網(wǎng)絡(luò)多采用梯度下降算法調(diào)整權(quán)值參數(shù)，學(xué)習(xí)速度緩慢、泛化性能差等問題是制約前饋神經(jīng)網(wǎng)絡(luò)應(yīng)用的瓶頸[11].最近 Huang等[9、10]摒棄了梯度下降算法的迭代調(diào)整策略，提出了極端學(xué)習(xí)機(jī)算法.該算法對(duì)單隱層神經(jīng)網(wǎng)絡(luò)的輸入權(quán)值和隱層節(jié)點(diǎn)偏移量進(jìn)行隨機(jī)賦值，并且只通過一步計(jì)算即可解析求出網(wǎng)絡(luò)的輸出權(quán)值.極端學(xué)習(xí)機(jī)能夠極大地提高網(wǎng)絡(luò)學(xué)習(xí)速度和泛化能力.本章首先介紹極端學(xué)習(xí)機(jī)的監(jiān)督學(xué)習(xí)模式，在此基礎(chǔ)上推導(dǎo)出極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)模式.

1.1 極端學(xué)習(xí)機(jī)的監(jiān)督學(xué)習(xí)

單隱層神經(jīng)網(wǎng)絡(luò)監(jiān)督學(xué)習(xí)的代價(jià)函數(shù)E0可表示為

式中：N0為標(biāo)記樣本總數(shù)；為隱層節(jié)點(diǎn)總數(shù)，表示第j個(gè)標(biāo)記樣本向量（下標(biāo)n表示每個(gè)樣本向量的維數(shù)，n等于輸入層節(jié)點(diǎn)數(shù)，表示樣本向量的類別標(biāo)記向量（下標(biāo)C表示類別數(shù)目，C等于網(wǎng)絡(luò)的輸出節(jié)點(diǎn)數(shù)）；wi＝ （wi1…win），表示連接網(wǎng)絡(luò)輸入層節(jié)點(diǎn)與第i個(gè)隱層節(jié)點(diǎn)的輸入權(quán)值向量；bi表示第i個(gè)隱層節(jié)點(diǎn)的偏移量；g（·）表示隱層節(jié)點(diǎn)的激活函數(shù)；βi＝ （βi1…βiC）T，表示連接第i個(gè)隱層節(jié)點(diǎn)與網(wǎng)絡(luò)輸出層節(jié)點(diǎn)的輸出權(quán)值向量.

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

式中：H0表示網(wǎng)絡(luò)關(guān)于標(biāo)記樣本的隱層輸出矩陣；β表示輸出權(quán)值矩陣；T0表示標(biāo)記樣本集的類別標(biāo)記矩陣.H0、β、T0分別定義如下：

Huang等[9、10]嚴(yán)格地證明了當(dāng)網(wǎng)絡(luò)隱層節(jié)點(diǎn)的激活函數(shù)無窮可微時(shí)，網(wǎng)絡(luò)的輸入權(quán)值和偏移量可直接隨機(jī)賦值而不必采用梯度下降算法迭代調(diào)整.因此單隱層神經(jīng)網(wǎng)絡(luò)的監(jiān)督學(xué)習(xí)過程可等價(jià)為求取線性系統(tǒng)H0β＝T0的范數(shù)最小的最小二 乘 解 （minimum norm least－squares solution），如式（5）所示：

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

（1）對(duì)網(wǎng)絡(luò)的輸入權(quán)值向量wi和隱層節(jié)點(diǎn)偏移量bi進(jìn)行隨機(jī)賦值

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

1.2 極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)

關(guān)于極端學(xué)習(xí)機(jī)的已有研究均是在監(jiān)督學(xué)習(xí)模式下進(jìn)行的[9、10]，本節(jié)將極端學(xué)習(xí)機(jī)的學(xué)習(xí)模式擴(kuò)展到半監(jiān)督領(lǐng)域.首先考慮單隱層網(wǎng)絡(luò)半監(jiān)督學(xué)習(xí)的代價(jià)函數(shù)[9]：

式（7）右邊第2項(xiàng)為擴(kuò)充的標(biāo)記樣本誤差累加項(xiàng)；Ne表示擴(kuò)充的標(biāo)記樣本的數(shù)目，表示第j個(gè)擴(kuò)充的標(biāo)記樣本向量，表示的類別標(biāo)記向量.

最小化半監(jiān)督學(xué)習(xí)的代價(jià)函數(shù)等價(jià)于找到滿足下式的特殊解：

其中He表示網(wǎng)絡(luò)關(guān)于擴(kuò)充標(biāo)記樣本的隱層輸出矩陣，Te表示擴(kuò)充標(biāo)記樣本集的類別標(biāo)記矩陣，分別定義如下：

式（8）的右邊可進(jìn)一步推導(dǎo)如下：

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

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

其中

除了計(jì)算輸出權(quán)值矩陣，極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)過程還涉及如何擴(kuò)充標(biāo)記樣本以及評(píng)估不確定性等操作，第2章將對(duì)所有相關(guān)步驟進(jìn)行詳細(xì)描述.

2 基于極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)方法流程

基于極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)方法主要包括4個(gè)步驟：初始訓(xùn)練、標(biāo)記樣本擴(kuò)充、不確定性的換位評(píng)估和輸出權(quán)值計(jì)算.

2.1 方法流程歸納

初始輸入：初始標(biāo)記樣本集L0，無標(biāo)記樣本集U，單隱層神經(jīng)網(wǎng)絡(luò)的隱層節(jié)點(diǎn)數(shù).

步驟1 初始訓(xùn)練

（1）對(duì)網(wǎng)絡(luò)的輸入權(quán)值矩陣W＝（wi）和隱層節(jié)點(diǎn)偏移向量B＝ （bi）進(jìn)行隨機(jī)賦值，i＝1，2，…，；

（2）按照式（3）計(jì)算關(guān)于初始標(biāo)記樣本集L0的網(wǎng)絡(luò)隱層輸出矩陣H（W，B，L0）；

（3）按照式（5）和（6）計(jì)算網(wǎng)絡(luò)的隱層輸出權(quán)值矩陣；

（4）計(jì)算輸出閾值向量Θ：

①計(jì)算網(wǎng)絡(luò)輸出層的初始輸出矩陣

其中O0表示網(wǎng)絡(luò)關(guān)于集合L0的輸出層輸出矩陣，具體形式為N0表示集合L0的樣本總數(shù).

②計(jì)算網(wǎng)絡(luò)的輸出閾值向量

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

（5）存儲(chǔ)輸入權(quán)值矩陣W＝ （wi）、偏移向量B＝ （bi）和初始輸出權(quán)值矩陣

步驟2 標(biāo)記樣本擴(kuò)充

（1）計(jì)算關(guān)于無標(biāo)記樣本集U的輸出層輸出矩陣：

其中H（W，B，U）表示網(wǎng)絡(luò)關(guān)于無標(biāo)記樣本集U的隱層輸出矩陣，OU表示網(wǎng)絡(luò)關(guān)于無標(biāo)記樣本集U的輸出層的輸出矩陣，具體定義如下：H（W，B，U）＝

xU1，…，xUNU為集合U中的無標(biāo)記樣本向量，下標(biāo)NU表示集合U中無標(biāo)記樣本向量的總數(shù).

（2）構(gòu)建擴(kuò)充標(biāo)記樣本集合Le

步驟3 不確定性的換位評(píng)估

因?yàn)闊o法直接評(píng)估擴(kuò)充樣本中的不確定性對(duì)分類結(jié)果的影響，所以采用標(biāo)記樣本集與擴(kuò)充標(biāo)記樣本集交換位置的策略間接評(píng)估不確定性的影響.

（1）僅以擴(kuò)充標(biāo)記樣本集Le為學(xué)習(xí)樣本集，計(jì)算對(duì)應(yīng)的輸出權(quán)值矩陣：

其中為利用Le訓(xùn)練的網(wǎng)絡(luò)輸出權(quán)值矩陣，表示Le的類別標(biāo)記矩陣，H（W，B，Le）是網(wǎng)絡(luò)隱層輸出矩陣H（W，B，Le）的 Moore－Penrose廣義逆，H（W，B，Le）的計(jì)算過程可參照式（6）.

（2）以初始標(biāo)記樣本集L0為測(cè)試對(duì)象，檢驗(yàn)擴(kuò)充標(biāo)記樣本集的不確定性：

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

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

轉(zhuǎn)到步驟2重新擴(kuò)充標(biāo)記樣本.

步驟4 輸出權(quán)值計(jì)算

（1）針對(duì)樣本集合L0和Le，以W為輸入權(quán)值矩陣、B為偏移向量，計(jì)算網(wǎng)絡(luò)的輸出權(quán)值矩陣

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

（2）判斷

極端學(xué)習(xí)機(jī)的分類過程如下：

（1）根據(jù)學(xué)習(xí)結(jié)果（W，B，），計(jì)算網(wǎng)絡(luò)關(guān)于測(cè)試樣本集合Ω的輸出層輸出矩陣OΩ：

其中

NΩ為測(cè)試樣本的數(shù)目，C為類別數(shù)目.

2.2 關(guān)鍵參數(shù)的作用和選擇策略

在半監(jiān)督學(xué)習(xí)過程中，式（17）的輸出裕量參數(shù)Δ和式（23）的不確定性閾值ρ對(duì)算法的成績(jī)影響較大.其中Δ影響無標(biāo)記樣本向標(biāo)記樣本轉(zhuǎn)化的難易程度，Δ越大無標(biāo)記樣本越容易轉(zhuǎn)化為標(biāo)記樣本，反之越難；ρ控制換位評(píng)估過程中的分類誤差上限，ρ越小表示算法允許的誤差上限越低，算法對(duì)不確定性的敏感性就越高，算法的重復(fù)次數(shù)也越多.

Δ與ρ的取值范圍均為（0，1），仿真實(shí)驗(yàn)采用基于交叉檢驗(yàn)（cross validation）[13]的網(wǎng)格搜索法對(duì)這兩個(gè)參數(shù)進(jìn)行選擇，交叉檢驗(yàn)方法可以保證參數(shù)的無偏估計(jì).具體過程如下：（1）Δ與ρ取離散值（例如，Δ＝ …，10－4，10－3，…，10－1，…；ρ＝ …，10－4，10－3，…，10－1，…）構(gòu)成網(wǎng)格；（2）計(jì)算在網(wǎng)格對(duì)應(yīng)的每個(gè)參數(shù)對(duì)（如（Δ，ρ）＝ （10－1，10－1））處的交叉檢驗(yàn)值在最大交叉檢驗(yàn)值對(duì)應(yīng)的參數(shù)對(duì)附近區(qū)域進(jìn)行更為精細(xì)的網(wǎng)格搜索.例如，初始得到的最優(yōu)參數(shù)對(duì)為（Δ，ρ）＝ （10－1，10－1），則在（10－1，10－1）周圍進(jìn)行精細(xì)網(wǎng)格搜索（Δ＝ …，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，…），直至確定最優(yōu)參數(shù)值.

3 仿真實(shí)驗(yàn)

為驗(yàn)證本文所提方法的有效性，對(duì)扎龍自然保護(hù)區(qū)遙感數(shù)據(jù)集[14]、UCI機(jī)器學(xué)習(xí)數(shù)據(jù)庫[15]中的3組數(shù)據(jù)集以及2組半監(jiān)督學(xué)習(xí)基準(zhǔn)數(shù)據(jù)集[1]進(jìn)行分類仿真.每組樣本的個(gè)數(shù)、類別數(shù)等相關(guān)信息如表1所示.為了全面檢驗(yàn)半監(jiān)督學(xué)習(xí)方法的學(xué)習(xí)速度和泛化能力，將每組訓(xùn)練樣本中的標(biāo)記樣本和無標(biāo)記樣本的比例按1∶1、1∶2和1∶3進(jìn)行分配，分別求取半監(jiān)督學(xué)習(xí)方法在不同分配比例條件下的學(xué)習(xí)時(shí)間和分類精度.

采用改進(jìn)型 TSVM 方法（NTSVM）[4]、EMGMMs方法[5]和本文提出的基于極端學(xué)習(xí)機(jī)的半監(jiān)督學(xué)習(xí)方法（下文簡(jiǎn)稱ssELM）對(duì)實(shí)驗(yàn)數(shù)據(jù)進(jìn)行分類.所有程序均在Matlab 7平臺(tái)上運(yùn)行，計(jì)算機(jī)CPU為Pentium IV 2.0 GHz，內(nèi)存512 MB.3種方法的半監(jiān)督學(xué)習(xí)時(shí)間和分類精度分別如表2和3所示.

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

表1 實(shí)驗(yàn)樣本相關(guān)信息Tab.1 Information of experimental samples

表2 三種方法對(duì)6組實(shí)驗(yàn)數(shù)據(jù)的半監(jiān)督學(xué)習(xí)時(shí)間Tab.2 Semi－supervised learning time of three methods for six experimental data sets s

表3 三種方法對(duì)6組實(shí)驗(yàn)數(shù)據(jù)的分類精度Tab.3 Classification accuracies of three methods for six experimental data sets %

如表3所示，在標(biāo)記樣本與無標(biāo)記樣本比例為1∶1和1∶2時(shí)，ssELM方法對(duì)數(shù)據(jù)集g241d的分類精度比NTSVM方法稍低.這是因?yàn)槌跏紭?biāo)記樣本集中包含的異常點(diǎn)較多，導(dǎo)致ssELM方法對(duì)不確定性檢測(cè)的精度有所下降.減少標(biāo)記樣本集中的異常點(diǎn)影響是半監(jiān)督學(xué)習(xí)方法性能穩(wěn)定的關(guān)鍵.實(shí)驗(yàn)結(jié)果證明本文所提方法能夠有效地發(fā)掘無標(biāo)記樣本中的有用信息，并在一定程度上抑制樣本擴(kuò)充帶來的不確定性增加等問題.

4 結(jié) 論

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

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

[2]孫廣玲，降 龍.基于分層高斯混合模型的半監(jiān)督學(xué)習(xí)算 法 [J].計(jì) 算 機(jī) 研 究 與 發(fā) 展，2004，41（1）：156－161

[3]張博鋒，白 冰，蘇金樹.基于自訓(xùn)練EM算法的半監(jiān)督文本分類[J].國防科技大學(xué)學(xué)報(bào)，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īng)網(wǎng)絡(luò)的快速并行算法[J].自動(dòng)化學(xué)報(bào)，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īng)網(wǎng)絡(luò)在土地覆蓋分類中的應(yīng)用研究 [J].中國圖象圖形學(xué)報(bào)，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