一種多核集成的在線半監督學習方法

在許多實時預測問題中，傳感器和其他數據采集設備從環境中不斷收集數據，并不斷地將數據發送給學習系統。學習系統應該根據到達的訓練數據實時學習，并根據任意時間實時為新數據提供預測。傳統的機器學習方法難以滿足訓練數據先存儲和再學習的實際需求，因此在線學習（在線學習）是處理大規模實時預測問題的方法已引起研究人員的興趣。在線學習中,每個時刻學習器都會從訓練數據流中接收到一個訓練樣本.通常,學習器需要首先對該樣本進行預測,然后根據該預測輸出與樣本真實標記的比對結果來確定如何更新當前模型,以期通過這種模型的順序更新方式學得泛化能力強的模型.在整個學習過程中,學習器不需要使用任何數據的分布信息,因此學習器可以不存儲或者僅存儲少量訓練數據.此外,學習過程分散在不同時刻進行,故模型更新較為迅速.這使得對于任意時刻的預測請求,學習器總可以使用最新的模型進行預測.最近已出現了不少針對在線學習的研究,包括采用被動-主動(passive-aggressive)方式來設計在線學習的更新方式;在RKHS(reproducingkernelhilbertspace)中進行在線學習;在有限圖上進行在線學習;在RKHS中導出更有效的更新準則.此外,在線學習的思想還被成功用于自然語言處理、互聯網搜索中.然而,以往對在線學習的研究均在監督學習的框架下進行,即假設所有訓練數據都具有標記.事實上,在真實的實時應用中,為大規模數據流中的每個樣本都提供標記是相當困難的.很多實時系統全天候運行,為每個樣本提供標記意味著需要人員24小時不間斷地為所有樣本進行標記.即使能夠負擔這樣大的人力物力,在數據積累非常迅速的應用中,也來不及為數據流中每個樣本提供標記.例如網絡入侵檢測中,網絡管理員難以迅速地判斷流經網關的數據是否屬于入侵攻擊.因此,在絕大多數實際問題中,往往僅有少量的數據能夠被人工標記.如果僅利用這些少量的有標記數據進行在線學習,不僅造成數據資源的浪費,而且還因沒有使用最新收集到的未標記數據更新模型而降低模型預測的時效性.因此,如果能夠自動而有效地利用數據流中未標記的樣本進行在線學習,有望提高在線學習方法在實際的實時應用中的可用性.半監督學習是利用未標記數據學習的主流技術之一,它能夠在不加外界干預的情況下,自動地利用少量已標記數據和大量未標記數據進行學習.目前半監督學習方法大致可分為以下4類:基于生成式模型的方法、基于低密度劃分的方法、基于圖和流形正則化的方法以及基于disagreement的方法.這些方法已經被廣泛用于自然語言處理、計算機輔助醫療診斷、互聯網搜索、基于內容的圖像檢索等應用中.由于半監督學習方法往往需要假設數據分布與標記之間存在某種聯系,并且往往需要在所有樣本上進行全局優化,因此并不能直接在不考慮數據分布信息且要求實時響應的在線學習中使用.最近,Goldberg等人在在線半監督學習方面進行了嘗試,提出了基于流形正則化的在線半監督學習方法.但是由于流形正則化需要考慮數據分布的全局信息,因此需要利用一些特殊技術在在線學習環境下獲取數據流形的近似信息.事實上,數據分布的全局信息在在線半監督學習中并非必需.如果能同時在線學習多個有差異的函數,則可利用它們在概念層面上的相容性來幫助縮小學習的搜索空間.此時,未標記數據實際上僅提供了相容性的測試平臺.學習算法可逐個考察在未標記樣本上的相容性,并不需要利用數據的分布信息.顯然,這一做法更加符合在線學習不考慮數據分布這一特性.據此,本文提出了一種基于多核集成的在線半監督學習方法OMike(onlinemultI-kernelensemble).該方法同時在多個核(kernel)對應的RKHS中學習一組預測函數,并使用這些函數對未標記樣本預測的一致程度來正則化在線學習的即時風險.基于正則化后的即時風險,借助在線凸優化技術對其進行求解,最后使用多數投票結合所有預測函數.OMike不僅不需要借助特殊方法增量式地獲取數據分布的近似信息,同時還可通過集成多個有差異函數來獲得強泛化性能.在UCI數據集上的實驗測試以及在網絡入侵檢測上的應用表明,OMike方法能夠有效利用大量未標記數據提升在線學習性能.本文其余部分安排如下:第1節給出基于多核集成的在線半監督學習方法OMike算法;第2節提供實驗結果;第3節為結束語.1在線學習性能的優化設訓練數據流為(x1,y1,δ1),(x2,y2,δ2),…,(xt,yt,δt),…,其中xt∈Rd為時刻tOMike接收到的d維特征向量,yt∈{+1,-1}為xt的潛在概念標記,當且僅當δt=1時該標記可見.給定V個核k1,k2,…,kV,相應的RKHS分別為H1,H2,…,HV.OMike同時從接收到的訓練數據流中在線地學習V個預測函數f1∈H1,…,fV∈HV.在學習過程的任意時刻,均可采用多數投票(式(1))對V個預測函數進行集成:?y=argmaxy∈{+1,-1}∑v:sign(fv(x))=y1.(1)在線學習過程中,學習器往往需要利用當前時刻T∈N接收到的訓練樣本xT來更新現有模型,使其在xT上的損失降低,以期通過該方式獲得較優的模型.事實上,如果不考慮計算和存儲開銷,也不考慮學習系統的實時響應,當不存在概念漂移(conceptdrift)時,在時刻T的最佳模型可通過最小化定義在訓練集x1,x2,…,xT上的風險函數來獲得.為了與在線學習區分,稱這種可同時利用x1,x2,…,xT學習的方式為批量學習(batchlearning).由于在線學習僅能根據當前樣本來優化當前模型的性能,其學習效果和批量學習仍可能存在差距.為獲得較優性能,在設計在線學習的更新準則時,應使得在線學習在任意時刻T的效果盡可能地逼近在x1,x2,…,xT上批量學習的效果.以下部分,本文從風險函數最小化的角度出發,建立OMike的平均即時風險(instantaneousrisk)和相應批量學習的批量風險(batchrisk)之間的逼近關系,并從中導出OMike方法的模型更新準則.類似方法已在文獻中被用于推導在線流形正則化方法的模型更新準則.設截止到時刻T,學習器共從數據流中接收到n個有標記樣本和m個未標記樣本,其中T=m+n.在批量模式下,基于多核集成的半監督學習方法通過最小化定義在有標記數據和未標記數據上的批量風險函數來進行半監督學習:R(f)=1nV∑v=1(n∑i=1l(fv(xi),yi)+12λ1∥fv∥2Η)+λ22mV∑u,v=1m∑j=1(fu(xj)-fv(xj))2?(2)其中,f=(f1,f2,…,fV),l(a,b)為損失函數(例如:HingeLoss),‖·‖2H表示在RKHS中元素的二范數,λ1,λ2為正則化參數.若要在線學習的最終效果和批量學習的效果一致,則在線學習過程須等效于對式(2)進行最小化.將式(2)進行改寫,可得:R(f)=1ΤΤ∑t=1Rt(f)?(3)其中,Rt(f)=ΤnV∑v=1δtl(fv(xt),yt)+12λ1V∑v=1∥fv∥2Η+λ2Τ2mV∑u,v=1m∑j=1(1-δt)(fu(xt))-fv(xt))2.(4)從式(3)可以看出,Rt(f)僅與時刻t的訓練樣本(xt,yt,δt)相關,故可視為時刻t的即時風險函數,分配到在線學習過程中的時刻t進行最小化.由于在時刻t僅有一個樣本,因此在線學習器可簡單地根據式(5)進行一步梯度下降(gradientdescent),以減小時刻t的即時風險Rt(f),從而得到時刻t+1的預測函數ft+1.fv,t+1←fv,t-ηt?Rt(f)?fv|f=ft?(5)其中,ηt為時刻t的學習速率,且:?Rt(f)?fv=Τnδtl′(fv(xt),yt)kv(xt,?)+λ1fv+λ2Τ2mV∑u=1(1-δt)(fv(xt))-fu(xt))kv(xt,?).(6)這樣,整個在線學習過程實際上就是依照時間順序,逐一使用相應的即時風險函數進行一步梯度下降.該過程對應的平均即時風險為Rair=1ΤΤ∑t=1Rt(ft).設通過最小化式(3)所求得的最優解為f*.將最優解代入式(3)可以看出,其最小的風險值和平均即時風險仍存在差異.該差異可能導致OMike學得的最終預測函數與在相同數據上直接最小化式(3)所學得的預測函數存在差異,從而有可能造成性能不佳.所幸的是,由于Rt(f)(t=1,…,T)為一組凸函數,根據Zinkevich對梯度下降與在線凸規劃的分析可知,當T→∞時,在Rt(f)(t=1,…,T)上順序地采用學習速率遞減的梯度下降所導出的平均即時風險1ΤΤ∑t=1Rt(ft)收斂于min1ΤΤ∑t=1Rt(f*).因此,在漸進意義下,OMike采用上述梯度下降方式進行在線學習的性能與直接優化式(3)來進行批量學習的性能相當.上述基于梯度下降的在線學習過程似乎并不需要保存任何訓練樣本,各時刻接收到的樣本被用來計算梯度后即可丟棄.但事實上由于預測函數均定義于RKHS中,根據表示定理,預測函數表示為fv,t=Τ∑t=1αv,tkv(xi,?),因此需要保存所有的樣本點以生成用于表示fv,t的基{kv(xi,·)}ti=1.然而,在大多數大規模實時預測問題中不可能保存數據流中的所有訓練樣本.在此,本文對其作了近似,僅緩存數據流中的s個樣本,用于表示預測函數.當選取的s不是非常小時,對預測函數的近似表示所造成的截斷誤差可以控制在一個較小的范圍內.由于數據緩存大小有限,當數據緩存填滿后,需要利用新接收到的樣本替換緩存中一個舊樣本.這樣的替換直接導致用于表示預測函數的基發生了變化.因此,OMike的模型更新過程不應僅簡單依照式(5)進行,還應該設法減小由于表示預測函數的基發生變化而造成的影響.具體來說,時刻t第v個核對應的預測函數為fv,t=t-1∑i=t-sαv,ikv(xi,·);如果不考慮緩存溢出,經過梯度下降后對應的預測函數應更新為?fv,t=t∑i=t-sβv,ikv(xi,·),其中,?fv,t使用所有緩存中的舊樣本以及當前樣本所對應的基表示,βv,i(i=t-s,…,t)通過如下基于梯度下降的更新公式求解:{βv,i←αv,i(1-ηtλ1)?i<t?βv,t←-ηt(Τnδtl′(fv(xt),yt)+λ2ΤmV∑u=1(1-δt)(fv(xt)-fu(xt)))?i=t.(7)在進入時刻t+1前,將緩存中的一個舊樣本用當前樣本進行替換,以保證數據緩存的容量不變.設時刻t+1第v個核對應的預測函數表示為fv,t+1=t∑i=t-s+1γv,ikv(xi,·).在此,本文通過求解式(8)所示的優化問題來尋找距離?fv,t最近的fv,t+1:minγv12∥fv,t+1-?fv,t∥2=minγv12∥t∑i=t-s+1γv?ikv(xi,?)-t∑i=t-sβv?ikv(xi,?)∥2.(8)對式(8)進行求解可得:γv=A-1vCvβv?(9)其中,Av={kv(xi,xj)}ti,j=t-s+1,Cv={kv(xi,xj)}ti=t-s+1,j=t-s,γv=(γv,t-s+1,…,γv,t)為時刻t+1表示預測函數的基的系數.OMike算法流程的偽碼表示詳見算法1.算法1.OMike算法偽代碼.輸入:訓練數據流D={(x1,y1,δ1),…,(xt,yt,δt),…};正則化參數λ1,λ2;損失函數l(a,b);視圖個數V;V個視圖的對應的核k1,…,kV,數據緩存大小s.①初始化所有視圖的預測函數f1←0,f2←0,…,fV←0.②初始化時間計數器t←1;數據緩存B←?.③當D中有數據,循環執行步驟④～(11).④按照式(7)求解更新后的預測函數?f1,?f2,?,?fV.⑤把當前樣本xt加入數據緩存B.⑥如果|B|<s,則執行步驟⑦.⑦采用更新后的預測函數覆蓋當前預測函數f1←f?1,?,fV←f?V.⑧否則,執行步驟⑨～⑩.⑨從B中刪除停留時間最長的未標記樣本.⑩采用式(9)對更新后的預測函數進行修正后,覆蓋預測函數f1,f2,…,fV.(11)t←t+1.輸出:在任意時刻t,可按照式(1)中多數投票原則集成f1,f2,…,fV.2測試測試2.1未標記樣本在線監督系統的分析本文選取了4個規模較大的UCI數據集進行實驗測試,以驗證OMike方法的有效性.由于OMike僅能處理數值型屬性,本文將數據集中所有列名屬性進行二值化.此外,OMike處理的是二類分類問題,對于多類別的數據集,本文從中挑選出兩個類別的樣本進行實驗.經過預處理后的實驗數據集的相關信息如表1所示:針對每個數據集,隨機挑選75%的數據作為訓練數據,其余25%用做測試集.在訓練數據中,隨機挑選10%的數據作為有標記數據,其余90%作為未標記數據.將所有有標記和未標記數據隨機排成數據流形式,提交給在線學習算法進行學習.實驗中OMike采用3個參數不同的RBF核,對應的RBF核參數分別設為0.5,1,2.根據文獻,為保證平均即時風險收斂于批量風險,梯度下降中采用的學習速率需隨時間遞減.在此,梯度下降的學習速率設為ηt=1/t.為模擬有限存儲空間,學習過程中數據緩存大小固定為s=100.當緩存被填滿后,在每個時刻需要用當前樣本去代替緩存中的一個舊樣本.直觀地說,在線學習過程中有標記數據對模型的調整作用通常比未標記樣本大,從而所攜帶的有用信息較多.因此,更新數據緩存時刪除的樣本是在緩存中停留時間最長的未標記樣本,如緩存中無未標記樣本,則刪除停留時間最長的有標記樣本.本文使用了兩種在線監督學習方法與OMike方法進行對比,以考察未標記數據在在線學習中的效用.第1種方法為監督的多核集成方法,簡記為OnlineL-3.該方法使用和OMike相同的3個核來構造預測函數.在學習過程中,OnlineL-3忽略數據流中所有未標記樣本,僅利用有標記樣本進行學習,最終采用與OMike相同的多數投票機制進行集成.另一種方法為僅使用一個預測函數的在線監督學習方法,簡記為OnlineL-1.該方法采用的核以及核參數與OnlineL-3中性能居中的預測函數的參數相同.與OnlineL-3相同,該方法僅使用有標記數據進行學習.在實驗中,兩種監督學習方法的參數和OMike中的參數保持一致,并采用在即時風險函數上的梯度下降來進行在線學習.不同的是,監督學習方法的即時風險中沒有在未標記數據上的正則化項.在實驗中,采用兩種指標來評估在線學習算法的性能.第1種指標是學習器的累積錯誤率(accumulatederrorrate),它反映了從開始在線學習到當前時刻學習器所提供實時預測的累積性能.具體計算方式如下:在時刻t學習器更新模型前,可先對該樣本的類別標記進行預測.時刻t的累積錯誤率為從學習開始到t為止的t次預測中錯誤預測所占的比例.除累積錯誤率外,實驗中還考察算法學得的最終模型在測試集上的錯誤率.為與前者區別,稱該指標為泛化錯誤率(generalizationerrorrate).在各數據集上重復25次隨機實驗,記錄3種算法的累積錯誤率及訓練停止后學得模型的泛化錯誤率.各數據集上的平均累積錯誤率如圖1所示,其中橫軸代表訓練時間,縱軸代表累積錯誤率.值得注意的是,在實驗中各算法使用的正則化參數均通過交叉驗證進行設置.從圖1中可以看出,除在satellite_1vs2上優勢不明顯外,在kr-vs-kp,waveform_0vs1兩個數據集上OMike的曲線都始終位于OnlineL-1與OnlineL-3曲線的下方;在sick上經過一定時間后,OMike的累積錯誤率也降低到OnlineL-1與OnlineL-3的曲線以下.這說明在OMike在學習過程中能夠利用兩種監督學習方法所不能利用的未標記數據的信息,幫助自身更快地學得性能較優的預測函數,使得在隨后的訓練過程中能夠提供比監督學習更好的實時預測.各數據集上不同在線學習方法停止時學得的最終模型的平均泛化錯誤率如表2所示,其中最低錯誤率采用粗體標出.從表中可以看出,OMike在所有數據集上均取得最低的錯誤率.相對于不利用任何未標記數據的監督多核集成方法OnlineL-3而言,利用未標記數據學習的OMike性能平均提升了38.3%.顯著水平為0.05的成對雙側t檢驗表明,OMike相對于OnlineL-3的所有性能提升具有顯著性.此外,對比兩種監督在線學習方法可發現,在kr-vs-kp和waveform_0vs1兩個數據集上采用多核集成的OnlineL-3算法學得模型的性能明顯優于僅使用單學習器的OnlineL-1所學得模型的性能,在其余兩個數據集上二者性能相當.顯著水平為0.05的成對雙側t檢驗表明,OnlineL-3與OnlineL-1在kr-vs-kp和waveform_0vs1上存在顯著的性能差異.實驗結果表明,在線學習環境下,采用多核集成可取得比單個學習器更優的性能.在此基礎上,在學習過程中對未標記數據進行有效利用,還可顯著提升多核集成的泛化性能.在實驗中,3種在線學習方法均采用數據緩存中的數據來近似表示學得的預測函數.緩存大小直接影響到對預測函數的表達能力.因此,本文還進一步考察了緩存大小s對OMike算法性能的影響.在實驗中取s∈{50,100,150,200}4種不同的緩存大小,其余實驗設置保持不變.圖2中給出了在4個數據集上選擇不同緩存大小所對應測試的錯誤率.從圖2可以清楚看出,學得模型的錯誤率隨著緩存大小的增加而降低.當s=50時,其性能明顯差于其他緩存大小.為提高性能可以增加緩存大小.然而,當緩存大小為100時,雖然繼續增加緩存可得到相對更好的性能,但是性能改善幅度相當有限.因此,緩存大小設為100,可同時兼顧性能和存儲開銷.2.2實驗結果與分析網絡入侵檢測在網絡安全中占有十分重要的地位.入侵檢測系統可部署在網關或路由器上,用于對網絡入侵進行實時偵測.為了適應入侵形式的多樣性和動態性,入侵檢測系統需要不斷根據流經網關的數據進行在線的學習.由于網絡管理員不可能隨時監控網絡并實時指出當前是否發生了網絡入侵,故入侵檢測系統從網關收集到的大部分數據缺少標記.所以,網絡入侵檢測成為一個典型的在線半監督學習問題.為驗證本文提出的基于多核集成的在線半監督學習方法OMike在網絡入侵檢測中的有效性,本文在KDD-99網絡入侵檢測的部分數據上進行實驗.原始數據集包含超過500萬條網絡連接記錄,其中包含正常的網絡連接以及DOS,R2L,U2R和probing四類惡意的網絡入侵攻擊,每條連接記錄使用TCP基本屬性、連接內容屬性、TCP連接屬性3方面共41維屬性描述.本文實驗中針對