基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法研究

曾曉勤，趙倩倩，何嘉晟

(河海大學(xué)計(jì)算機(jī)與信息學(xué)院，江蘇南京 210098)

近年來(lái)，主動(dòng)學(xué)習(xí)成為機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)。傳統(tǒng)的監(jiān)督學(xué)習(xí)算法多是被動(dòng)學(xué)習(xí)，即只能被動(dòng)接受指定的數(shù)據(jù)，要求訓(xùn)練樣本中含有標(biāo)注數(shù)據(jù)。然而，在很多實(shí)際問(wèn)題中，如文本分類(lèi)、圖像檢索、語(yǔ)音識(shí)別等往往含有大量的未標(biāo)注數(shù)據(jù)，只有少量的標(biāo)注數(shù)據(jù)，這使得監(jiān)督學(xué)習(xí)算法在應(yīng)用上存在很大的局限性［1］。另外，對(duì)樣本進(jìn)行數(shù)據(jù)標(biāo)注常常比較困難，甚至代價(jià)十分昂貴，而獲取未標(biāo)注數(shù)據(jù)的樣本則相對(duì)容易。如針對(duì)基因序列的測(cè)試，標(biāo)注一段基因序列需要進(jìn)行代價(jià)昂貴的實(shí)驗(yàn)，相反，獲取基因片段代價(jià)則相對(duì)小的多［2］。在有大量標(biāo)注數(shù)據(jù)的情況下，選擇盡可能少的、有代表性的樣本進(jìn)行學(xué)習(xí)，將大幅度提高學(xué)習(xí)效率。

主動(dòng)學(xué)習(xí)一般分為兩部分:學(xué)習(xí)器和選擇器。學(xué)習(xí)器可以是一個(gè)分類(lèi)器，用于學(xué)習(xí)標(biāo)注數(shù)據(jù)的樣本，算法也多是監(jiān)督學(xué)習(xí)中常見(jiàn)的算法。選擇器用于選擇未參加學(xué)習(xí)的、標(biāo)注或未標(biāo)注數(shù)據(jù)樣本，是主動(dòng)學(xué)習(xí)的核心。主動(dòng)學(xué)習(xí)與傳統(tǒng)被動(dòng)學(xué)習(xí)最本質(zhì)的區(qū)別是多了一個(gè)主動(dòng)選擇的過(guò)程，可以自主地選擇最有“價(jià)值”的樣本(對(duì)于未標(biāo)注數(shù)據(jù)的，需交由專(zhuān)家進(jìn)行標(biāo)注)，然后再帶回學(xué)習(xí)。顯然，對(duì)適用于少量標(biāo)注數(shù)據(jù)與大量未標(biāo)注數(shù)據(jù)共存情況的主動(dòng)學(xué)習(xí)進(jìn)行研究既具有學(xué)術(shù)研究的意義，也具有實(shí)際應(yīng)用的價(jià)值。根據(jù)獲得未標(biāo)注數(shù)據(jù)樣本方式的不同，可以將主動(dòng)學(xué)習(xí)算法分為2種類(lèi)型:基于流的主動(dòng)學(xué)習(xí)［3-5］和基于池的主動(dòng)學(xué)習(xí)［6-8］。

Madaline網(wǎng)絡(luò)是一種通用的前饋離散型多層網(wǎng)絡(luò)。理論上，離散問(wèn)題可作為連續(xù)問(wèn)題的特例，所以可以用連續(xù)前向網(wǎng)絡(luò)代替離散前向網(wǎng)絡(luò)。但是，對(duì)于那些本質(zhì)為離散，且連續(xù)技術(shù)難以適用的領(lǐng)域，如邏輯運(yùn)算、分類(lèi)以及聚類(lèi)等，離散前向網(wǎng)絡(luò)直接突顯出簡(jiǎn)單和高效的優(yōu)勢(shì)。激活函數(shù)的不連續(xù)性使得離散前向網(wǎng)絡(luò)不能再使用成熟的BP算法［9-10］。Winter等［11-12］對(duì)Madaline網(wǎng)絡(luò)訓(xùn)練算法進(jìn)行了研究，提出了著名的MRII算法。MRII算法把對(duì)網(wǎng)絡(luò)的訓(xùn)練轉(zhuǎn)化為對(duì)每個(gè)Adaline的訓(xùn)練，以最小擾動(dòng)原則為依據(jù)，通過(guò)不斷的翻轉(zhuǎn)與迭代找到最佳的權(quán)值。近些年，Zhong等［13］在MRII算法的基礎(chǔ)上，利用Madaline網(wǎng)絡(luò)的敏感性技術(shù)，對(duì)Madaline網(wǎng)絡(luò)訓(xùn)練算法進(jìn)行了進(jìn)一步的研究和改進(jìn)。

一般而言，神經(jīng)網(wǎng)絡(luò)敏感性是研究因網(wǎng)絡(luò)參數(shù)的擾動(dòng)而引起網(wǎng)絡(luò)輸出發(fā)生變化的情況［14］，需找出網(wǎng)絡(luò)輸出變化與網(wǎng)絡(luò)參數(shù)擾動(dòng)之間的依賴關(guān)系。若考慮參數(shù)僅為輸入情況，由于不同輸入樣本的擾動(dòng)可能引起輸出的不同變化，所以針對(duì)樣本擾動(dòng)的網(wǎng)絡(luò)敏感性可以用來(lái)衡量網(wǎng)絡(luò)輸出對(duì)于不同輸入樣本的敏感程度。以網(wǎng)絡(luò)敏感性為尺度，不難給出如下2種解釋和推論:(a)那些使得網(wǎng)絡(luò)輸出敏感性大的樣本(稱為敏感樣本)離網(wǎng)絡(luò)已建立起的判定邊界一定相對(duì)較近，因而類(lèi)似支持向量在支持向量機(jī)中扮演的角色，敏感樣本值得挑選出來(lái)進(jìn)行進(jìn)一步精化訓(xùn)練;(b)那些使得網(wǎng)絡(luò)輸出敏感性小的樣本(稱為不敏感樣本)離網(wǎng)絡(luò)已建立的判定邊界一定相對(duì)較遠(yuǎn)，如果不敏感樣本與已參加訓(xùn)練的所有樣本距離都較遠(yuǎn)，說(shuō)明網(wǎng)絡(luò)前期訓(xùn)練中缺失了這種樣本所代表的信息，因而也需挑選出來(lái)進(jìn)行進(jìn)一步全面訓(xùn)練。所以，在處理分類(lèi)問(wèn)題的主動(dòng)學(xué)習(xí)中，Madaline網(wǎng)絡(luò)敏感性可以作為一個(gè)合適的尺度，用來(lái)主動(dòng)挑選尚未訓(xùn)練的樣本參加訓(xùn)練，顯然，策略是挑選那些對(duì)當(dāng)前Madaline網(wǎng)絡(luò)敏感性大或小的樣本。

由以上所述可見(jiàn)，主動(dòng)學(xué)習(xí)過(guò)程中，關(guān)鍵是如何從大量的未標(biāo)注數(shù)據(jù)樣本中挑選最有“價(jià)值”的樣本進(jìn)行學(xué)習(xí)。本文提出一種新的主動(dòng)學(xué)習(xí)算法，即基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法。

1 Madaline網(wǎng)絡(luò)模型及符號(hào)約定

神經(jīng)元Adaline是神經(jīng)網(wǎng)絡(luò)Madaline的基本構(gòu)成單元，組成網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)。

圖1 Adaline結(jié)構(gòu)示意圖Fig.1 Sketch map of Adaline structure

1.1 Adaline模型及符號(hào)

圖1為一個(gè)神經(jīng)元Adaline的結(jié)構(gòu)示意圖。

輸入向量為

權(quán)向量為

偏置為w0，激活函數(shù)為對(duì)稱硬極限函數(shù)，即

就功能而言，神經(jīng)元Adaline實(shí)現(xiàn)了一種從多維空間向一維空間的邏輯映射關(guān)系。

1.2 Madaline網(wǎng)絡(luò)模型及符號(hào)

Adaline是Madaline網(wǎng)絡(luò)的最簡(jiǎn)單形式，Madaline網(wǎng)絡(luò)可由Adaline根據(jù)一定的規(guī)則連接而成。圖2是Madaline網(wǎng)絡(luò)模型結(jié)構(gòu)示意圖，Xi、Yi(1≤i≤L)分別表示網(wǎng)絡(luò)第i層的輸入和輸出。由本文介紹可知，Yk-1=Xk(2≤k≤L)。Madaline網(wǎng)絡(luò)第一層輸入X1是整個(gè)網(wǎng)絡(luò)的輸入，由樣本的輸入提供;最后一層輸出YL作為整個(gè)網(wǎng)絡(luò)的輸出。為方便表達(dá)，用n0-n1-…-nL表示一個(gè)有L層的網(wǎng)絡(luò)，n0為網(wǎng)絡(luò)的輸入維數(shù)，ni(1≤i≤L)為第i層上所包含的神經(jīng)元個(gè)數(shù)。

圖2 Madaline網(wǎng)絡(luò)模型Fig.2 Madaline network model

從功能上看，Madaline網(wǎng)絡(luò)是在訓(xùn)練中通過(guò)一定的調(diào)整規(guī)則調(diào)整自身的參數(shù)(包括權(quán)值、偏置值或網(wǎng)絡(luò)結(jié)構(gòu))來(lái)實(shí)現(xiàn)給定訓(xùn)練數(shù)據(jù)中輸入與輸出間的對(duì)應(yīng)關(guān)系，建立從n0維空間到nL維空間某種特定的映射關(guān)系。

2 網(wǎng)絡(luò)敏感性定義及計(jì)算

2.1 Adaline敏感性定義

影響Adaline輸出變化的參數(shù)主要是權(quán)和輸入。權(quán)決定輸入與輸出之間的映射關(guān)系，因而它的擾動(dòng)必然會(huì)對(duì)輸入和輸出關(guān)系產(chǎn)生影響，進(jìn)而使輸出受到影響。權(quán)固定之后，輸入決定了輸出，輸入擾動(dòng)也勢(shì)必會(huì)對(duì)輸出產(chǎn)生影響。本文只考慮給定輸入點(diǎn)的擾動(dòng)對(duì)于輸出的影響，因此，Adaline敏感性定義為:因某一給定輸入點(diǎn)的可能變化而導(dǎo)致輸出的變化，表示為

其中，輸入點(diǎn)Xj和權(quán)值W都是固定的。顯然，這個(gè)定義最自然和直接地表示了因輸入點(diǎn)擾動(dòng)ΔX而導(dǎo)致的輸出變化Δy。

2.2 Madaline網(wǎng)絡(luò)敏感性定義

設(shè)Madaline網(wǎng)絡(luò)輸入為Xn×1∈Rn，輸出為Ym×1∈{-1，1}m，訓(xùn)練后的網(wǎng)絡(luò)在輸入和輸出間建立的映射為G(X)=Y，又可表示為G(X)=(g1(X)，g2(X)，…，gm(X))T。對(duì)Madaline網(wǎng)絡(luò)敏感性進(jìn)行研究，已有文獻(xiàn)［15-16］針對(duì)不同的網(wǎng)絡(luò)參數(shù)擾動(dòng)情況進(jìn)行了討論。本文在Adaline敏感性定義的基礎(chǔ)上，定義Madaline網(wǎng)絡(luò)敏感性為:因網(wǎng)絡(luò)在某一給定輸入點(diǎn)的可能變化而導(dǎo)致網(wǎng)絡(luò)輸出變化的概率P，表示為

其中，ΔX∈［-a，a］n(a＞0)視為一統(tǒng)計(jì)量，是鄰近輸入點(diǎn)Xj周?chē)目赡茏兓俊Ｊ?6)將Madaline網(wǎng)絡(luò)敏感性定義為在給定的輸入點(diǎn)Xj處，由于ΔX而導(dǎo)致網(wǎng)絡(luò)輸出變化的概率。

2.3 Madaline網(wǎng)絡(luò)敏感性計(jì)算

由式(6)可得

式中:E——期望值。則第i個(gè)分量的計(jì)算公式為

對(duì)Madaline網(wǎng)絡(luò)敏感性計(jì)算，筆者給出一個(gè)簡(jiǎn)潔的近似計(jì)算方法，基本思路是，對(duì)輸入擾動(dòng)的每一個(gè)分量，在連續(xù)區(qū)間［-a，a］n內(nèi)離散取點(diǎn)，然后計(jì)算輸入擾動(dòng)在所有可能離散點(diǎn)處的均值作為式(8)的近似值。顯然，離散點(diǎn)取的越多越精確，但是計(jì)算復(fù)雜度將會(huì)呈指數(shù)級(jí)上升。

設(shè)第i個(gè)分量以步長(zhǎng)h在區(qū)間［-a，a］均勻取k=2a/h+1個(gè)值，則式(8)可近似計(jì)算為:對(duì)于輸入樣本為Xj，輸入變化范圍為［-a，a］的網(wǎng)絡(luò)G()=(g1()，g2()，…，gm())T，其第i個(gè)輸出分量敏感性的計(jì)算，則為第i個(gè)輸出分量的敏感性，其網(wǎng)絡(luò)輸出敏感性S(Xj，G，a)即S=(s1，s2，…，sm)T為網(wǎng)絡(luò)在Xj的敏感性。

3 基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法

主動(dòng)學(xué)習(xí)的基本思想是:(a)根據(jù)初始的標(biāo)注數(shù)據(jù)樣本集生成基礎(chǔ)分類(lèi)器，也就是利用監(jiān)督學(xué)習(xí)算法對(duì)初始樣本進(jìn)行訓(xùn)練，得到一個(gè)粗分類(lèi)器;(b)設(shè)計(jì)一個(gè)樣本選擇算法，該算法根據(jù)一定標(biāo)準(zhǔn)對(duì)提供的未參與訓(xùn)練的樣本(已標(biāo)注或未標(biāo)注數(shù)據(jù)樣本)進(jìn)行評(píng)價(jià)，從中挑選一個(gè)或幾個(gè)樣本(未標(biāo)注數(shù)據(jù)樣本需交由專(zhuān)家進(jìn)行標(biāo)注)加入到訓(xùn)練數(shù)據(jù)集中，繼續(xù)對(duì)基礎(chǔ)分類(lèi)器進(jìn)行訓(xùn)練。學(xué)習(xí)器和選擇器重復(fù)交替工作，逐步使分類(lèi)器性能提高，直到達(dá)到預(yù)定目標(biāo)停止。

基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法以Madaline網(wǎng)絡(luò)為學(xué)習(xí)器，首先根據(jù)部分標(biāo)注數(shù)據(jù)樣本進(jìn)行學(xué)習(xí)，得到一個(gè)基礎(chǔ)Madaline網(wǎng)絡(luò)，然后以該Madaline網(wǎng)絡(luò)在那些給定但未參與訓(xùn)練樣本點(diǎn)的敏感性為評(píng)價(jià)尺度，挑選敏感性大的樣本(對(duì)未標(biāo)注數(shù)據(jù)樣本需先進(jìn)行標(biāo)注)加入初始訓(xùn)練樣本集中繼續(xù)訓(xùn)練，循環(huán)往復(fù)該過(guò)程，直到最終滿足學(xué)習(xí)器的性能目標(biāo)。算法中之所以沒(méi)有挑選敏感性小的樣本，是因?yàn)樵诖_定初始訓(xùn)練樣本集時(shí)，可先把所有給定的訓(xùn)練樣本進(jìn)行聚類(lèi)，挑選每個(gè)類(lèi)中的樣本作為初始訓(xùn)練樣本集，這樣就可避免感性值小的樣本與參加訓(xùn)練樣本的距離較遠(yuǎn)的情況?；贛adaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法具體步驟如下。

a.將訓(xùn)練樣本集X(其中有少量標(biāo)注數(shù)據(jù)樣本和大量未標(biāo)注數(shù)據(jù)樣本)聚類(lèi)。

b.挑選每個(gè)類(lèi)中的樣本構(gòu)成初始訓(xùn)練樣本集^X(未標(biāo)注樣本需進(jìn)行標(biāo)注)。

c.循環(huán)執(zhí)行以下操作直到滿足終止條件:(a)用^X訓(xùn)練分類(lèi)器G;(b)對(duì)所有未參與初始訓(xùn)練的樣本Xj∈(X-^X)，計(jì)算其敏感性值S(Xj，G，a);(c)按敏感性值遞減的方法對(duì)樣本排序;(d)選取前k個(gè)樣本加入到^X中(k值可視具體應(yīng)用而定)。

d.返回G。

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)以VC++6.0為實(shí)驗(yàn)平臺(tái)進(jìn)行，使用UCI數(shù)據(jù)庫(kù)中的Pima數(shù)據(jù)集(兩分類(lèi))和Iris數(shù)據(jù)集(三分類(lèi))。對(duì)于兩分類(lèi)，在構(gòu)建分類(lèi)器時(shí)輸出層含有1個(gè)Adaline神經(jīng)元;對(duì)于三分類(lèi)，在構(gòu)建分類(lèi)器時(shí)輸出層含有2個(gè)Adaline神經(jīng)元。把每組數(shù)據(jù)集分成兩部分:75%的訓(xùn)練樣本集和25%的測(cè)試樣本集。在X中，首先將X進(jìn)行聚類(lèi)，然后挑選每個(gè)類(lèi)中的樣本構(gòu)成 ^X，這些^X直接用于訓(xùn)練出一個(gè)粗分類(lèi)器。根據(jù)主動(dòng)學(xué)習(xí)的特性，在訓(xùn)練的過(guò)程中按照不同的挑選策略挑選參加訓(xùn)練的樣本:(a)隨機(jī)挑選策略，隨機(jī)挑選未參與初始訓(xùn)練的樣本加入到^X中繼續(xù)對(duì)基礎(chǔ)分類(lèi)器進(jìn)行訓(xùn)練;(b)基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)挑選策略，用該策略挑選未參與初始訓(xùn)練的樣本加入到 ^X中繼續(xù)對(duì)基礎(chǔ)分類(lèi)器進(jìn)行訓(xùn)練。針對(duì)Pima數(shù)據(jù)集和Iris數(shù)據(jù)集，分別利用2種挑選策略進(jìn)行了5組實(shí)驗(yàn)，每組實(shí)驗(yàn)針對(duì)相同的實(shí)驗(yàn)環(huán)境又做了10次，表1為每組實(shí)驗(yàn)的平均結(jié)果。

可以看出多數(shù)情況下本文提出的基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法比隨機(jī)挑選的方法具有更高的準(zhǔn)確率。

表1 基于Pima數(shù)據(jù)集和Iris數(shù)據(jù)集2種挑選策略實(shí)驗(yàn)結(jié)果Table 1 Experimental results of two methods based on Pima and Iris datasets

5 結(jié) 語(yǔ)

針對(duì)如何從大量的未標(biāo)注數(shù)據(jù)樣本中挑選最有價(jià)值的樣本進(jìn)行學(xué)習(xí)問(wèn)題，本文提出了一種基于Madaline網(wǎng)絡(luò)敏感性的主動(dòng)學(xué)習(xí)算法。算法的核心是打造一種合適的Madaline網(wǎng)絡(luò)敏感性尺度，有的放矢地選擇需要的訓(xùn)練樣本，從而實(shí)現(xiàn)主動(dòng)學(xué)習(xí)的功能。實(shí)驗(yàn)結(jié)果驗(yàn)證了基于Madaline網(wǎng)絡(luò)敏感性主動(dòng)學(xué)習(xí)算法的有效性和可行性。

［1］趙秋煥.兩種主動(dòng)學(xué)習(xí)方法［D］.石家莊:河北大學(xué)，2010.

［2］崔寶今.基于半監(jiān)督和主動(dòng)學(xué)習(xí)的蛋白質(zhì)關(guān)系抽取研究［D］.大連:大連理工大學(xué)，2008.

［3］FREUND Y，SEUNG H S，SHAMIR E，et al.Selective sampling using the query by committee algorithm［J］.Machine Learning，1997，28(2/3):133-168.

［4］DAGON I，ENGELSON S.Committee-based sample selection for probabilistic classifiers［C］//Proceedings of 12th Int’l Confon Machine Learning.San Francisco，CA:Morgan Kaufmann，1995:150-157.

［5］ARGAMON-ENGLESON S，DAGAN I.Committee-based sample selection for probabilistic classifiers［J］.Journal of Artificial Intelligence Research，1999，11:335-360.

［6］LEWIS D D，GAIL W A.A sequential algorithm for training text classifiers:corrigendum and additional data［J］.Sigir Forum，1995，29(2):13-19.

［7］MCCALLUM A K，NIGAM K.Employing EM and pool-based active learning for text classification［C］//Proceedings of the Fifteenth International Conference.Madison，WI，USA:Morgan Kaufmann Publishers，1998:350-358.

［8］MUSLEA I，MINTON S，KNOBLOCK C A.Active learning with multiple view［J］.Journal of Artificial Intelligence Research，2006，27:203-233.

［9］RUMELHART D E，HINTON G E，WILLIAMS R J.Learning representations by back propagation errors［J］.Nature，1986，323: 533-536.

［10］RUMELHART D E，MCCLELLAND J L.Parallel distributed processing:explorations in the microstructure of cognition，vol.l［M］.Cambridge:MIT Press，1986.

［11］WINTER R，WIDROW B.Madaline ruleⅡ:a training algorithm for neural networks［C］//IEEE International Conference on Neural Networks.San Diega，CA，USA:IEEE Publishrs，1988:401-408.

［12］WINTER R.Madaline ruleⅡ:a new method for training networks for Adalines［D］.Stanford:Standford University，1989.

［13］ZHONG Shuiming，ZENG Xiaoqin，WU Shengli，et al.Sensitivity-based adaptive learning rules for BFNNs［J］.IEEE Transactions on Neural Networks and Learning Systems，2012，23(3):480-491.

［14］曾曉勤，何嘉晟.單隱層感知機(jī)神經(jīng)網(wǎng)絡(luò)對(duì)權(quán)擾動(dòng)的敏感性計(jì)算［J］.河海大學(xué)學(xué)報(bào):自然科學(xué)版，2013，41(4):360-364. (ZENG Xiaoqin，HE Jiasheng.Computation the sensitivity of perceptrons with one hidden layer to weight perturbation［J］. Journal of Hohai University:Natural Sciences，2013，41(4):360-364.(in Chinese))

［15］WANG Yingfeng，ZENG Xiaoqin，YEUNG D，et al.Computation of Madalines’sensitivity to input and weight perturbations［J］. Neural Computation，2006，18(11):2854-2877.

［16］ZHONG Shuiming，ZENG Xiaoqin，LIU Huiyi，et al.Approximate computation of Madaline sensitivity based on discrete stochastic technique［J］.Science China:Information Science，2010，53(12):2399-2414.