基于被動-主動的特征演化流學習

劉艷芳 李文斌 高 陽

1(計算機軟件新技術國家重點實驗室(南京大學) 南京 210023) 2(龍巖學院數學與信息工程學院 福建龍巖 364012)

在線學習[1-3]作為一種增量式的機器學習技術，能夠對模型進行實時增量更新，學習過程中隨時都可以使用當前學到的模型對未知樣本進行預測，一旦對樣本處理完畢，不需要對其進行存儲和再訪問.在線學習非常適用于處理大規模流數據，不僅可以處理流數據帶來的樣本無限量和實時分析的挑戰，還不依賴于樣本獨立同分布的假設[4-5].正因為如此，此研究領域得到快速發展，涌現出豐富的算法.

在線梯度下降(online gradient descent, OGD)[6]是最簡單也是最流行的一階在線學習方法，在學習的每一輪總是沿著瞬時損失函數的負梯度方向修正模型，然后再將修正后的模型投影到可行域內.被動-主動算法(passive-aggressive learning, PA)[7]采用了OGD中根據瞬時損失函數的負梯度方向更新模型，同時，在學習過程中考慮了預測的置信水平，即樣本到當前決策邊界的間距，更新模型時每個樣本上的學習步長與該樣本被分類的置信水平相關.作為PA的一種拓展算法，置信度加權學習(confidence-weighted, CW)[8-9]是一個二階在線學習方法，不僅使用了瞬時損失函數的函數值和次梯度信息，還使用了瞬時損失函數的二階導數信息，即Hessian矩陣信息.自適應權重正則化方法(adaptive regularization of weights, AROW)[10]將CW算法中的約束放松，轉換為正則化項加到KL散度函數中，從而算法在每次學習中只需求解一個無約束的優化問題，從而提高了對噪聲的魯棒性.

然而，已有的在線學習往往假設每個流數據擁有相同且固定不變的特征空間.在實際應用中，流數據的特征空間往往是隨時間變化的，具有動態性和未知性.因此，梯形特征空間的在線學習、演化特征空間的在線學習和任意特征空間的在線學習被相繼提出和研究.

梯形特征空間(trapezoidal feature space)[11]是隨著數據的到來特征空間呈遞增狀態，同時滿足新到來的樣本中至少擁有前一個樣本的特征空間.例如，在文本分類和聚類中的無限詞匯主題模型[12]，文檔和文本詞匯的數量都隨著時間的推移而增加，從而需要更新模型以便捕獲新增加術語的重要性.稀疏梯形流數據學習(sparse trapezoidal streaming data， STSD)[11,13]，將特征空間分為2部分：已有特征(existing features)和新特征(new features)，根據PA的原則，如果預測錯誤則更新分類器，使得損失最小化，并且接近當前的分類器；如果在學習過程中出現了新的特征，也根據結構風險最小化原則更新新特征對應的分類器權值.

在現實應用中，原有的特征空間(又稱舊特征集)消失，新的特征空間出現，這種現象稱為特征演化，即演化特征空間(evolvable feature space)[14].例如，已有傳感器因為電池壽命、硬件損壞等原因被新的傳感器取代，傳感器收集的數據特征將發生變化.假設傳感器電池用完的時間是可以預先知道的，則通常會在舊傳感器用完之前放置一組新的傳感器，因此就會有重疊時間段：舊特征集和新特征集共同存在.那么如何利用重疊周期挖掘新舊特征之間的關系，并且在只有新特征可用的情況下如何利用舊特征學習的模型？特征演化流學習(feature evolvable streaming learning, FESL)[14-15]運用OGD作為模型更新策略，通過重疊時期的樣本來學習新特征到舊特征的映射，即從新特征中重建出舊特征，從而繼續利用舊特征學習的模型，進而針對新舊模型提出了組合預測和當前最優預測2種集成方法.一遍增量和遞減學習(one-pass incremental and decremental learning， OPID)[16]將演化特征空間分為2個階段：壓縮階段(C-階段)和擴展階段(E-階段)，并在C-階段提出了一遍壓縮學習方法，在E-階段提出了一種新的學習方法來繼承C-階段的分類結果.在線演化度量學習(online evolving metric learning, EML)[17]在度量學習領域來研究演化特征空間.值得說明的是，文獻[16-17]處理的是沒有重疊時期但有重疊特征的情況.對于有重疊時期的特征演化空間，特征演化可能是不可預測的，這意味著特征可能會消失或任意出現，從而導致重疊時期參差不齊.為了解決這個問題，具有不可預測特征演化的預測學習(prediction with unpredictable feature evolution, PUFE)[18]通過矩陣補全的方法來修補重疊時期的特征.同時，在演化特征空間中，數據分布有可能發生變化，針對這個問題，特征和分布演化流學習(feature and distribution evolving stream learning， FDESL)[19]提出了一種針對特征空間和數據分布均發生變化的數據差異度量方法——演化差異(evolving discrepancy)，并給出了良好的理論保證，特別是對泛化性能的理論保證.已有的演化特征學習中往往假設每個樣本預測后都會揭示其真實的類別標簽，而在實際應用中這個假設大都不滿足，因為大多數樣本是沒有類別標簽的，同時人工標注類別標簽是非常耗時且昂貴.為了解決這一問題，適宜存儲的演化特征學習(storage-fit feature-evolvable streaming learning， SF2EL)[20]運用流形正則化技術，利用以往相似的數據，協助改進在線模型.

現有的在線學習方法假設的固定特征空間、梯形特征空間和演化特征空間都遵循著明確的規律而變化，這都限制了在動態環境中的適用性，因為在動態環境中流數據的特征空間是反復無常、任意變化的，即任意特征空間(capricious feature space)[21].基于任意特征流的在線學習(online learning from capricious data streams， OCDS)[21-22]在全局性的特征空間上提出了一個生成圖模型(generative graphical model)來建立已有特征和新特征的關系，使在已有特征空間上學習的模型可以應用到新特征空間.與此同時，基于多樣化特征空間的在線學習(online learning from varying feature spaces， OLVF)[23]對樣本和特征空間分別進行分類，其中，為了對樣本進行分類，動態地將樣本分類器和訓練集投影到它們的共享特征子空間上，特征空間分類器預測給定特征空間的投影置信度，最后，樣本分類器根據投影置信度對約束強度進行縮放，進而根據經驗風險最小化原則進行分類器更新.

無論是固定特征空間、梯形特征空間、演化特征空間，還是任意特征空間，在現實應用中均有對應的應用場景.因此，基于這4種類型的在線學習方法研究均具有很大的應用意義.

在本文中，我們將重點放在演化特征空間的在線學習方法研究上.文獻[14-15]提出的特征演化流學習(FESL)算法運用了最簡單的OGD作為模型更新策略，同時，在新舊特征重疊階段只研究了重建舊特征.本文提出了一種基于被動-主動更新策略的特征演化學習算法(passive-aggressive learning with feature evolvable streams, PAFE).該算法采用了PA作為模型更新策略，其中，PA在學習過程中不僅采用了OGD中根據瞬時損失函數的負梯度方向更新模型，同時考慮了與樣本相關的置信水平.在新舊特征重疊階段，本文不僅從新特征重建了舊特征，同時從舊特征表示了新特征，為新特征的模型學習提供了合理的模型初始化.繼而該算法從新特征空間和被恢復的舊特征空間中學習了2個基模型，并研究了2種集成算法：組合預測和當前最優預測.最后，在合成數據集和真實數據集上的實驗結果驗證了所提算法的有效性.

1 相關背景

本文主要研究演化特征空間下的在線二分類任務.在每一輪的學習中，分類器會接收到一個樣本并給出預測結果，一旦給出預測結果，則揭示該樣本的真實標簽，進而得到分類器的瞬時損失，該損失反映了預測標簽與真實標簽之間的差異，根據該損失信息，算法可以改進其分類器模型，以便在下一輪中做出更好的預測.

在本文中，采用大寫粗體表示矩陣，小寫粗體表示向量.其中，對于任意的矩陣M∈d×n，矩陣的轉置表示為MT.對于任意的方陣A∈n×n，可逆矩陣表示為A-1.表示向量v∈d的2-范數，向量v的轉置表示vT.

用(xt,yt)表示每輪接收到的數據實例，其中xt∈d是具有d維特征空間的樣本，yt∈{-1,+1}是其對應的真實標簽.PA算法[7]將預測模型約束為線性模型wt∈d，通過預測當前樣本的標簽，表示為與樣本相關的置信度，并采用hinge損失作為損失函數，即(wTx,y)=max(0,1-ywTx).PA算法的目標函數具體為

(1)

其中，ξ≥0是松弛變量，(ft,yt)≤ξ，且C≥0是平衡松弛項對目標函數的影響.式(1)擁有閉式解：

wt+1=wt+τtytxt，

(2)

Fig. 1 Illustration that how data stream comes圖1 演化流數據產生過程說明圖

演化特征空間表現為原有的特征空間消失，新的特征空間出現，也就是說每一個周期過程中僅包含2個特征空間，因此，我們只需要關注一個周期，就很容易拓展到很多周期的情況.圖1展現了文獻[15]中給出的一個周期內的演化流數據產生過程，可以總結如下：

將PA算法應用到演化特征空間中，則有：

(3)

2 基于PA的特征演化流學習算法

在本節中，我們首先介紹所提基于PA更新策略的特征演化學習算法PAFE的基本思想，然后引入到2個集成方法中.

基于演化特征空間的在線學習主要局限性[14-15]是在新特征空間S2的情況下，無法再接收具有特征空間S1的數據，從而會忽略S1中已經學習得到的模型，同時，忽略了已學到的模型對S2中模型的初始化.為了解決這個問題，假設新舊特征空間存在2種映射關系φ:d2→d1,ψ:d1→d2，即其中，來恢復S1中的數據，d2用S1來模擬S2中的數據，M1,M2是線性映射的系數矩陣.我們繼續沿用文獻[14-15]中提出的線性映射來近似這2種關系.則在新舊特征重疊時刻T1-B+1,T1-B+2,…,T1有：

(4)

(5)

式(4)和(5)的最優解為

(6)

(7)

① 初始化：隨機初始化w1,1∈d1,A1=A2=B1=B2=0;

② fort=1:T1

⑤ 揭示樣本真實標簽：yt∈{-1,+1}；

⑧ 用式(3)更新模型；

⑨ end if

⑩ ift>T1-B

組合預測即在第t輪的預測是基模型預測的加權平均值，如式(8)所示：

pt=a1,tf1,t+a2,tf2,t，

(8)

其中，ai,t是第i個基模型預測的權重.權重的更新如式(9)所示：

ai,t+1=vi,t/(v1,t+v2,t),i=1,2,

(9)

其中，vi,t=ai,te-η (fi,t,yt)，且具體來說，當時，定理1[14-15]給出了組合預測的損失界限，繼而說明在舊特征空間的幫助下性能將得到改善.首先，我們給出在T1+1,T1+2,…,T1+T2階段中的3種累積損失LS1,LS2,LS12，其中是2個基模型下的累積損失，是組合預測模型下的累積損失.

關于基模型的組合預測具體過程如算法2所示.

算法2.組合預測(PAFE-c).

① 初始化：a1,T1=a2,T1=1/2,η=(8(ln 2)/T2)1/2;

④w1,T1+1=w1,T1；

⑥ fort=T1+1:T1+T2

⑨ 用式(8)計算pt；

⑩ 揭示樣本真實標簽：yt∈{-1,+1}；

通常情況下，組合預測比只選擇一個基模型的效果好[24]，但要求每個基模型的性能不能太差[25].而在PAFE問題中w1,t在特征空間S2下可能會變得越來越差.因此，本文引用另一個集成方法：當前最優預測[14-15]，它以較高的概率選擇權重較大的基模型.我們通過權重的分布來選擇當前最優的基模型，具體表示為

ui,t+1=ai,t/(a1,t+a2,t),i=1,2.

(10)

權重的更新如式(11)所示：

ai,t+1=δΔt/2+(1-δ)vi,t,i=1,2,

(11)

其中，H(x)=-xlnx-(1-x)ln(1-x)是在x∈(0,1)下的熵函數，η=(8/T2(2ln 2+(T2-1)H(1/(T2-1))))1/2，vi,t=ai,te-η (fi,t,yt),i=1,2,Δt=v1,t+v2,t,δ=1/(T2-1).為了從理論上保證所提算法當前最優預測的性能，定理2[14-15]給出了其累積損失的上界.

定理2[14-15].對于T2>1，在t=T1+1,T1+2,…,T1+T2下，當η=(8/T2(2ln 2+(T2-1)H(1/(T2-1))))1/2,δ=1/(T2-1),則當前最優預測模型下的累積損失LS12滿足如下性質：

選擇當前最優預測的過程具體如算法3所示.

算法3.當前最優預測(PAFE-s).

① 初始化：a1,T1=a2,T1=1/2,η=(8/T2(2ln 2+(T2-1)H(1/(T2-1))))1/2;

④w1,T1+1=w1,T1；

⑥ fort=T1+1:T1+T2

⑨ 用式(10)選擇當前最優模型wi,t；

⑩ 計算：pt=fi,t；

3 實驗與結果分析

本節我們首先介紹對比算法，其次給出實驗數據集并分析其結果.

3.1 對比算法

我們將本文所提算法PAFE-c,PAFE-s和過程中產生的4個算法進行對比，同時與文獻[15]中所提算法FESL-c,FESL-s進行對比，并和其過程中涉及的3個算法進行對比.值得說明的是，對比的時間段為在舊特征空間已經消失，新特征空間出現到消失，即被最新特征空間出現之前.

① NOGD[15].只考慮新特征空間的模型通過OGD進行更新；

② ROGD-u[15].通過線性映射，得到舊特征空間，進而繼續用OGD更新原有舊特征空間學習到的模型；

③ ROGD-f[15].盡管通過新特征空間恢復得到舊特征空間，但用已經學習到的舊模型，且不再更新；

④ FESL-c[15].2個基模型NOGD和ROGD-u的組合預測；

⑤ FESL-s[15].2個基模型NOGD和ROGD-u的選擇當前最優預測；

⑥ NPA-r.只考慮新特征空間的模型通過PA進行更新，模型的初始化為隨機數值；

⑦ NPA-d.盡管只考慮新特征空間的模型通過PA進行更新，但模型的初始化是通過重疊時刻舊特征到新特征的映射得到的；

⑧ RPA-u.通過恢復得到舊特征空間，繼續用PA更新原有舊特征空間已學習到的模型；

⑨ RPA-f.舊特征空間已學到的模型不再更新，直接應用至恢復的舊特征空間；

⑩ PAFE-c.2個基模型NPA-d和RPA-u的組合預測；

3.2 實驗設置及結果分析

實驗選用了和文獻[15]中相同的24個二分類數據集，包含8個合成數據集和16個來自Reuters的數據集(1)http://www.lamda.nju.edu.cn/code_FESL.ashx，其中，合成數據集是通過隨機高斯矩陣將原始數據集人為地映射到另一個特征空間，然后獲得來自特征空間S1和S2的數據；Reuters的每個數據集都有2個視圖，分別代表2種不同的語言，將2個視圖視為2個特征空間.24個數據集的詳細信息如表1所示，其中，前4行的數據集是合成數據集，剩余8行的數據集是來自Reuters的數據集.

Table 1 Detail Description of Datasets

我們將本文所提算法與文獻[15]中所提算法進行對比，其中文獻[15]所提算法的結果是直接使用文獻中的結果.因此，為了算法對比的公平性，本文中設置的和文獻[15]中的設置是一樣的：對于合成數據集，所有算法的分類精度是通過10次獨立運行的平均結果得出的，重疊時刻B的大小設置為5或者10，新舊特征空間的交替時刻T1和T2均設置為樣本個數的二分之一.本文所提算法PAFE-c,PAFE-s中的超參C設置如下：

① Australian,Credit-g,German:C=0.02；

② Credit-a,Svmguide3:C=0.05；

③ Diabetes:C=0.09；

④ Kr-vs-kp,Splice:C=0.005.

表2給出了在合成數據集上所有對比算法的分類精度，其中，表2用“·”標記每個網格中較好的結果，用粗體標注最好的結果.

Table 2 Accuracy of the Compared Algorithms on Synthetic Datasets表2 在合成數據集上所有對比算法的分類精度對比

從表2可以看出，所提算法PAFE-c和PAFE-s均在5個數據集上優于其他對比算法，尤其是在Kr-vs-kp數據集上，分類精度比FESL-c和FESL-s高出0.102，而在數據集Credit-g和Splice上，FESL-c和FESL-s僅比本文所提算法高出0.008以內.NPA-d是用了舊特征空間已學到的模型進行初始化，所以分類精度比NPA-r的高，甚至高出0.105.同時，用恢復的舊特征空間繼續更新的模型RPA-u的分類精度比RPA-f的高.然而，NOGD在6個數據集上的效果優于NPA-d，而RPA-u/RPA-f在6個數據集上的效果優于ROGD-u/ROGD-f，這個現象說明了PA更新策略更適合于數量較多的流數據.

對于數據規模較大的Reuters數據集，所有算法的分類精度是通過3次獨立運行的平均結果得出的，重疊時刻B的大小均設置為50，新舊特征空間的交替時刻T1和T2也設置為樣本個數的二分之一.本文所提算法PAFE-c，PAFE-s中的超參C設置如下：

① r.EN-FR,r.EN-GR,r.EN-IT,r.EN-SP,r.FR-IT,r.FR-SP,r.IT-FR,r.IT-SP:C=10-3；

② 剩余的8個Reuters數據集:C=10-4.

表3給出了在Reuters數據集上所有對比算法的分類精度，其中，表3用“·”標記每個網格中較好的結果，用粗體標注最好的結果.從表3可以看出，所提算法PAFE-s在15個數據集上優于其他對比算法，PAFE-c的分類精度均不高于PAFE-s，但在14個數據上優于其他對比算法.基本與表2的結果一致，RPA-u的分類精度比RPA-f的高，而NPA-d在大部分Reuters數據集上的分類精度比NPA-r僅高出0.005以內，這說明隨著流數據的增多，模型的初始值對基于PA策略的模型更新影響越小.與表2表現不同的是，NPA-d在15個數據集上的效果優于NOGD，而ROGD-u在11個數據集上的效果優于RPA-u，這個現象再次驗證了PA更新策略更適合演化特征空間中的模型學習.表3給出了在Reuters數據集上所有對比算法的分類精度.從表3可以看出，所提算法PAFE-s在15個數據集上優于其他對比算法，PAFE-c的分類精度均不高于PAFE-s，但在14個數據上優于其他對比算法.基本與表2的結果一致，RPA-u的分類精度比RPA-f的高，而NPA-d在大部分Reuters數據集上的分類精度比NPA-r僅高出0.005以內，這說明隨著流數據的增多，模型的初始值對基于PA策略的模型更新影響越小.與表2表現不同的是，NPA-d在15個數據集上的效果優于NOGD，而ROGD-u在11個數據集上的效果優于RPA-u，這個現象再次驗證了PA更新策略更適合演化特征空間中的模型學習.

Table 3 Accuracy of the Compared Algorithms on Reuters Datasets表3 在Reuters數據集上所有對比算法的分類精度對比

圖2中(a)～(d)和(e)～(i)分別是所提算法在合成數據集和Reuters數據集上的平均累積損失趨勢，且平均累積損失越小越好.從圖2可以看出，隨著到來樣本數量的增加，平均累積損失收斂到一個相對穩定的數值.同時，從圖2中的結果中可以再次驗證如下結論：1)在合成數據集上NPA-d的趨勢是迅速下降，而在數據規模較大的Reuters數據集上，NPA-r的下降趨勢比NPA-d更快，說明在較大的數據集上通過重疊階段的映射用已學的舊特征模型為新特征模型初始化是非常有意義的.2)基于PA更新策略的演化特征空間學習，在數據規模較小時，組合預測PAFE-c比當前最優預測的下降趨勢更為明顯，相對于規模較大的數據集Reuters，當前最優預測PAFE-S的下降趨勢則更為明顯.

Fig. 2 The trend of loss with four baseline methods and the proposed methods on some synthetic and Reuters data圖2 4個基模型與所提算法在部分合成和Reuters數據集上的平均累積損失趨勢

4 總 結

本文提出了一種基于PA更新策略的特征演化學習算法(PAFE).PA在學習過程中不僅采用了OGD中根據瞬時損失函數的負梯度方向更新模型，同時考慮了與樣本相關的置信水平.尤其，在新舊特征重疊階段，本文不僅重建了舊特征，同時通過已獲得的舊特征模型來初始化新特征的模型，進而獲得更高的算法性能.繼而從新特征空間和被恢復的舊特征空間中學習了2個基模型，并研究了2種集成算法：組合預測和當前最優預測.實驗表明，本文所提算法可以得到更好的分類效果.而無論本文還是文獻[15]都是用一階在線學習方法更新的模型，接下來可以從二階信息的角度研究演化特征空間下的學習，也許可以獲得更高的分類性能或者加速平均累積損失的下降速度.