裴 樂，劉 群，舒 航

(重慶郵電大學(xué) 計算智能重慶市重點實驗室，重慶 400065)

0 引 言

隨著互聯(lián)網(wǎng)的不斷發(fā)展，生產(chǎn)生活的各個領(lǐng)域都會產(chǎn)生大量的實時的形態(tài)各異的在線流數(shù)據(jù)，例如，人們可以通過社交網(wǎng)絡(luò)隨時隨地和朋友分享自己拍攝的各種圖片或視頻；當(dāng)網(wǎng)購成為人們必不可少的一種生活方式時，對電子商務(wù)(淘寶、亞馬遜等)網(wǎng)站的頻繁訪問和交易也會不斷地產(chǎn)生大量的瀏覽和消費數(shù)據(jù)等等。傳統(tǒng)的機器學(xué)習(xí)算法無法勝任這些海量在線流數(shù)據(jù)的學(xué)習(xí)，大量學(xué)者開始對在線學(xué)習(xí)算法進行研究，希望研究更高效且簡單的機器學(xué)習(xí)。

對于特征簡單、穩(wěn)定的流數(shù)據(jù)來說，通常線性模型就能夠進行較好地數(shù)據(jù)分析與處理[1-2]。然而大多數(shù)流數(shù)據(jù)的特征都比較復(fù)雜，簡單的基于線性模型的在線學(xué)習(xí)算法無法取得好的學(xué)習(xí)效果，對非線性模型在線學(xué)習(xí)算法的研究應(yīng)運而生。目前大多數(shù)學(xué)者通過引入核函數(shù)的方式進行非線性模型的研究[3-4]，雖然有助于非線性模型的研究，但是隨著數(shù)據(jù)量的不斷產(chǎn)生和增大，其數(shù)據(jù)特征變得越來越復(fù)雜，僅僅使用單個核函數(shù)無法較好地表達數(shù)據(jù)間的特征規(guī)律，文獻[5-6]介紹了在線多核的方法，并通過經(jīng)驗方法證明了多核的有效性。O. Dekel等[7]為了優(yōu)化多核方法，提出了一種基于支持向量移除策略的預(yù)算式算法，該算法能夠限制支持向量的個數(shù)，但是卻需要迭代檢查哪些支持向量應(yīng)該接下來被移除，同時在計算每個支持向量的決策函數(shù)時也要遍歷每一個支持向量，因此，每次模型更新的代價是昂貴的。

盡管以上文獻所提到的方法能夠獲得較好的數(shù)據(jù)分析效果，但是其應(yīng)用場景主要針對單任務(wù)學(xué)習(xí)問題，而存在于現(xiàn)實生活中的很多應(yīng)用場景更偏向于多任務(wù)問題，比如對智能交通的研究，通過對車輛管理、交通檢測和旅行信息等多個任務(wù)的同時研究，才能保證整體上實現(xiàn)智能交通的效果；同樣在自然語言處理領(lǐng)域中，在線推薦系統(tǒng)的研究需要同時考慮廣告推薦、電影推薦和路線推薦等多個任務(wù)，這些都可以看作是多任務(wù)問題。文獻[8-9]中提出了一種多任務(wù)特征選擇算法，在每次迭代時用計算閉式解的方式更新模型，但這種方法計算有些復(fù)雜。為了優(yōu)化上述方法，H. Yang等[10]使用正則化對偶平均的方法進行特征選擇，使得計算更為簡單?？紤]到目前大多數(shù)方法都是僅基于車輛的單一屬性進行研究，而忽視了不同種類屬性間的關(guān)聯(lián)性，文獻[11]采用了多任務(wù)聯(lián)合求解的方式對車輛的屬性進行識別，該方法使用多任務(wù)的方法將車輛的多個屬性聯(lián)合學(xué)習(xí)，以達到最優(yōu)的車輛判別結(jié)果。然而多任務(wù)方法雖然計算簡單但收斂速度慢。因此，很多學(xué)者嘗試將核方法引入到多任務(wù)學(xué)習(xí)中，以提高算法的收斂性，這一模型的研究受到在線學(xué)習(xí)領(lǐng)域大量學(xué)者的青睞。文獻[12-13]提出了基于預(yù)算量的多核在線學(xué)習(xí)算法，通過更新最小二乘支持向量機來進行預(yù)測，獲得了較好的效果。

對于多任務(wù)問題，僅僅使用單核的方式來描述任務(wù)特征是不全面的，單核函數(shù)往往只描述任務(wù)個體的特征，而無法描述任務(wù)之間的相關(guān)性，但是對于多任務(wù)問題，任務(wù)間的相關(guān)性也是十分重要的，因此，可以考慮引入多核的方法來同時描述多任務(wù)的數(shù)據(jù)特征。多核方法的主要問題是隨著核函數(shù)個數(shù)的增加，算法復(fù)雜度也會增加，因此，如何選擇合適的核函數(shù)個數(shù)，在盡可能描述任務(wù)特征的基礎(chǔ)上控制算法復(fù)雜度，是迫切需要解決的問題。本文提出一種多任務(wù)多核的算法，采用閾值限定的方法來控制核函數(shù)的個數(shù)，通過去掉權(quán)重小于閾值的核函數(shù)，來降低算法的復(fù)雜度。

由上述分析可知，對于多任務(wù)多核在線學(xué)習(xí)算法來說，影響算法時間效率的兩大重要因素分別是算法的計算方式和模型的更新所要花費的時間，因此，本文主要從這兩方面進行考慮。本文的創(chuàng)新點表現(xiàn)在：①通過減少核函數(shù)的使用個數(shù)來提高模型計算方法的效率。通常的模型計算方法最主要的影響是對于核矩陣的計算，當(dāng)基本核函數(shù)選擇的數(shù)量越多時，核矩陣的計算復(fù)雜度越高，進而所花費的時間就越多。本文通過引入閾值的方法對核函數(shù)進行遺忘，進而減少核函數(shù)的個數(shù)，以提高算法的時間效率；②降低模型的更新代價。通常的在線學(xué)習(xí)方法中，模型更新不僅需要更新每個任務(wù)固有特征的權(quán)重，還要更新所有任務(wù)共有特征的權(quán)重，如何有效地更新權(quán)重以提高算法的時間效率，本文通過引入一個遺忘變量，從對偶的角度優(yōu)化權(quán)重更新過程。最終實現(xiàn)了一個新的結(jié)合遺忘特性的多任務(wù)多核在線學(xué)習(xí)算法。

1 數(shù)據(jù)的處理與分析

對于復(fù)雜的在線流數(shù)據(jù)而言，其不僅是特征種類繁多，而且數(shù)據(jù)的特征會隨著時間的推移發(fā)生相應(yīng)的變化。除此之外，這類數(shù)據(jù)通常會包含多個相關(guān)的任務(wù)，這些任務(wù)之間不僅擁有某些相同的特征，并且還具備各自獨有的特征，如果采用傳統(tǒng)的方法將每個任務(wù)獨立學(xué)習(xí)，會導(dǎo)致任務(wù)間共有的特征丟失，而采用多個任務(wù)同時學(xué)習(xí)的方法，既可以學(xué)到任務(wù)間共有的特征，又保留了其固有的特征，這樣學(xué)習(xí)到的模型更加吻合數(shù)據(jù)的特性。但是如果采用直接學(xué)習(xí)特征規(guī)律的方式是比較困難的，引入多核的思想會更加有助于數(shù)據(jù)特征的學(xué)習(xí)。多任務(wù)多核在線學(xué)習(xí)模型則是結(jié)合多任務(wù)學(xué)習(xí)方式和多核思想，將多核方法應(yīng)用于在線多任務(wù)學(xué)習(xí)框架中，通過迭代的方式確定一個最適合于當(dāng)前數(shù)據(jù)產(chǎn)生規(guī)律的組合核函數(shù)，避免直接通過數(shù)據(jù)樣本分析對核學(xué)習(xí)器進行更新，使得計算方式更為簡單，同時又發(fā)揮了核方法收斂速度快以及多任務(wù)聯(lián)合學(xué)習(xí)能夠?qū)W習(xí)更完整數(shù)據(jù)特征的優(yōu)點，使得在線流數(shù)據(jù)的分析更加充分和準(zhǔn)確。

Ω(w1,w2,…,wQ)

i∈(1,2,…,Ng),q∈(1,2,…,Q)

(1)

(1)式中：C是懲罰因子；L(fq(xi,q),yi,q)為第q個任務(wù)中第i個樣本的損失，對于分類問題本文采用Hinge損失函數(shù)，對于回歸算法本文采用最小二乘損失函數(shù)進行計算；為消除該模型產(chǎn)生的過擬合的影響，引入權(quán)重的正則化項Ω(w)。

該模型是通過最小化經(jīng)驗風(fēng)險以及權(quán)重的正則化項來聯(lián)合求解的，對于多任務(wù)模型來說，其信息共享策略包括兩方面：①學(xué)習(xí)每個任務(wù)的固有特征；②學(xué)習(xí)所有任務(wù)的共同特征。因此，每個任務(wù)的權(quán)重部分被分為固有權(quán)重wq,m和共有權(quán)重θ，為避免模型過擬合，需要求解2個權(quán)重的正則化項。引入正則化項Ω的目的就是為了最大化任務(wù)之間的間隔，盡量擴大任務(wù)間的區(qū)分度，使得模型能夠進行更加準(zhǔn)確地預(yù)測，Ω的表示方式為

(2)

對于分類算法來說，引入Hinge損失函數(shù)，結(jié)合(2)式，將(1)式可以改寫為如(3)式的最小化問題，即通過最優(yōu)化權(quán)重θ，使得損失函數(shù)J(W)最小。

(3)

(3)式中，xi,q∈Rn,yi,q∈{-1,1} 。對于回歸算法來說，引入最小二乘損失函數(shù)，則(1)式可以改寫為如下最小化問題

(4)

就在線學(xué)習(xí)算法而言，算法基本上是逐一處理新樣本的，由于數(shù)據(jù)到來的速度很快，這就要求算法有很強的實時性，不僅需要滿足數(shù)據(jù)處理的實時要求，而且也不能造成數(shù)據(jù)的丟失。為此，本文模型采用了以空間換性能的方法來實現(xiàn)上述需求。為解決數(shù)據(jù)到來速度太快，可能會存在新樣本到來后處理不及時的情況，本文提出輸入窗口的概念以避免丟失新的數(shù)據(jù)樣本。在本模型中每個任務(wù)的輸入窗口大小是固定的，其作用就是暫時存儲無法立即處理的新樣本。由于支持向量機模型的優(yōu)勢，本文中的分類模型采用的是支持向量機模型，以保證輸入窗口的引入不會造成時間因素的增多。但是由于它需要額外占用一定的內(nèi)存，因此，窗口數(shù)的選擇非常重要。

多任務(wù)多核在線學(xué)習(xí)算法中另一個最需要解決的問題是算法模型的更新代價，由于模型本身需要通過不斷迭代的方式接近數(shù)據(jù)最優(yōu)的特征表示，因此，只有采用簡單有效的策略才能使算法的收斂速度變得更快。由于SVM方法會將所有預(yù)測錯誤的樣本作為支持向量保存下來，并僅對支持向量進行模型的更新。顯然對于不斷到來的流數(shù)據(jù)，其支持向量的個數(shù)是在不斷增長的，因此，隨著支持向量個數(shù)的增長，計算量會顯著增大，導(dǎo)致算法運行時間增大。為解決這個問題，本文提出了一種限定最大支持向量個數(shù)的方法，將支持向量的個數(shù)限制在一個固定的區(qū)間內(nèi)，以此保證算法的計算量不會過大過快地增長。

支持向量的保存意味著訓(xùn)練樣本集合的更新，因此，我們借鑒操作系統(tǒng)中內(nèi)存頁面的調(diào)度算法，提出了一種先進先出(first in first out, FIFO)策略進行樣本集更新[15]，其算法描述如下。

輸入：訓(xùn)練樣本集D；基本核函數(shù)集K={k1,k2,…,kM}。

輸出：預(yù)測結(jié)果和更新后的模型。

1: fort=1,2,…,Tdo %學(xué)習(xí)周期數(shù)

2: 依次給每個任務(wù)一個樣本xq或一組樣本D3%D3表示保持大小為3的輸入窗口

4: if 預(yù)測值==真實值

6: else

7: 用(xq,yq)更新訓(xùn)練樣本集的最后一行和一列Dqt={(x2,q,y2,q),(x3,q,y3,q),…,(xN,q,yN,q),(xq,yq)} %將預(yù)測錯誤的樣本放入樣本集中

9: 根據(jù)新來的樣本為該任務(wù)計算相應(yīng)的核矩陣 %由M個核函數(shù)組合而成

11: end if

12: end for

流數(shù)據(jù)不斷生成不僅帶來了很強的時間特征，而且其數(shù)據(jù)生成規(guī)律及固有特征都有可能隨時間變化而變化，最早進入樣本集中的數(shù)據(jù)在一定程度上不完全符合后期生成數(shù)據(jù)的特征，因此，使用FIFO策略替換存在時間最長樣本來更新數(shù)據(jù)集是合理的。算法所引入的FIFO策略，對訓(xùn)練樣本集的更新方法如下：每次把新加入的樣本放在最下行和最右列，然后去掉第1行和第1列即可完成訓(xùn)練樣本集的更新[16]。雖然這種更新策略會減小支持向量集，造成算法預(yù)測性能的一定下降，但是在計算條件和存儲資源都有限的條件下，追求計算效率是一個比較可行的折中策略。由于本模型對支持向量集的縮減程度可以調(diào)整，因此，隨著計算設(shè)備計算和存儲能力的增強，可以根據(jù)需要改變支持向量的減少數(shù)目，從而更好地提高預(yù)測性能。

根據(jù)上面的分析，上述算法詳細地給出了多任務(wù)多核在線學(xué)習(xí)算法的計算流程[17]。

2 模型優(yōu)化

本文主要是從對偶理論的角度對算法模型的時間效率進行優(yōu)化。為使得核函數(shù)的線性組合權(quán)重值更加符合數(shù)據(jù)特征，引入一個遺忘變量使用對偶的方式更新權(quán)重；接著使用閾值限定的方法對核函數(shù)的個數(shù)進行遺忘，以提高算法的時間效率；最后還給出了本文算法的時空復(fù)雜度分析。

2.1 在線學(xué)習(xí)的對偶理論

對于在線學(xué)習(xí)問題來說，人們希望得到一個非遞增的分類器序列w1,w2,…,wT，使模型生成過程中損失函數(shù)不斷最小化，表示為

J(W1)≥J(W2)≥…≥J(WT)

(5)

(5)式中，J(W)表示每個分類器的損失函數(shù)。(5)式表示隨著學(xué)習(xí)周期t的增加，損失函數(shù)不斷減小，形成收斂保證算法模型越來越趨于穩(wěn)定。根據(jù)上面的分析可知，原問題(primal problem)是一個凸規(guī)劃問題[18-19]，可以使用現(xiàn)成的優(yōu)化計算包進行求解，但是當(dāng)樣本量比較大而且形式比較復(fù)雜時，直接用優(yōu)化包計算量過大，會使算法收斂速度變慢，因此，需要首先對其進行計算優(yōu)化，于是使用對偶的方式進行優(yōu)化求解。

為了書寫方便，這里使用定義gt(wt)=L(ft(xi,t),yi,t)來代替損失函數(shù)，將以上定義代入(1)式，可以將其改寫為

s.t. ?i∈1,2,…,T,wi=w0

(6)

使用Lagarange對偶定理可將(5)式重新表示為

(7)

(7)式中，(α1,α2,…,αT)為對偶系數(shù)。根據(jù)(7)式可知，對偶函數(shù)為

(8)

因此，(1)式的最小化問題可以重新描述為最大化對偶問題

(9)

研究表明，對偶問題中的對偶向量和原問題中的邊界向量是一一對應(yīng)的[20-21]。對于在線學(xué)習(xí)問題來說，它的每次迭代更新相當(dāng)于一個學(xué)習(xí)周期，對于學(xué)習(xí)周期t，其邊界向量可表示為

(10)

從以上邊界向量的定義可以看出，新舊樣本對分類器的影響是一樣的。然而實際的在線流數(shù)據(jù)分析中，隨著數(shù)據(jù)的越來越多，其特征會發(fā)生或多或少的變化，歷史樣本對分類器的影響將會逐漸變小，所以需要采用新的方式對以往樣本的影響進行削弱，使得舊樣本對分類器的影響逐步減小。

2.2 一種帶有遺忘特性的在線學(xué)習(xí)框架

在對偶問題中模型更新的關(guān)鍵步驟就是對對偶系數(shù)(α1,α2,…,αT)的更新，在其更新過程中需要滿足以下條件[16]

D(αt)≥D(αt-1) s.t.t

(11)

(11)式中：t為學(xué)習(xí)周期，即對于還未獲得的樣本，其對偶系數(shù)為0，不會影響當(dāng)前的對偶函數(shù)值；D(αt)為對應(yīng)的對偶函數(shù)，由于對偶向量的更新是個非遞減的過程，也是在線學(xué)習(xí)的過程。

本文在對偶函數(shù)的更新過程中引入了一個新的變量η，對偶系數(shù)的更新方式可以改為

(αi)t=(1-ηt)·(αi)t-1

(12)

(12)式中：α∈[0,1]；ηt∈[0,1]ηt∈[0,1]。根據(jù)(8)式和(10)式，學(xué)習(xí)周期t中需要提升的對偶函數(shù)形式可以改寫為

(13)

ηt的初始值為0，可見ηt的引入并沒有違反對偶函系數(shù)變量的取值范圍。這更新策略下，可得到帶有遺忘變量的邊界向量的表達方式，將(12)式代入(10)式中，得到

wt=(1-ηt)·wt-1+C(at)tytxt

(14)

由(14)式可見，當(dāng)ηt>0時，歷史樣本在新得到的邊界向量中所占的比重會不斷減小，由此降低了它對分類器的影響。同樣地，對于多任務(wù)間共有特征的固有權(quán)重系數(shù)θ來說，其更新公式表示為

θt=(1-ηt)·θt-1

(15)

基于此，本文將新引入的變量ηt稱作遺忘變量，因為它的引入可以降低舊樣本對分類器的影響。對于流數(shù)據(jù)來說，數(shù)據(jù)的不斷變化會造成其特征隨時間的微小變化，因此，歷史樣本對分類器的影響是逐漸顯現(xiàn)的，所以將η稱作遺忘變量是合理的，表示它能將歷史樣本逐步遺忘。

基于上述分析，下面詳細地給出了一種具有遺忘特性的多任務(wù)多核在線學(xué)習(xí)算法框架。

輸入：訓(xùn)練樣本集D；基本核函數(shù)集K={k1,k2,…,kM}。

輸出：預(yù)測結(jié)果和更新后的模型。

1: fort=1,2,…,Tdo %學(xué)習(xí)周期數(shù)

2: 依次給每個任務(wù)一個樣本xq或一組樣本D3%D3表示保持大小為3的輸入窗口

3: 獲得已有的該任務(wù)訓(xùn)練模型modelqt-1%用SVM為每個任務(wù)訓(xùn)練模型

4: if 預(yù)測值==真實值

5: 輸出模型modelqt-1預(yù)測的結(jié)果

6: else

7: 用(xq,yq)更新訓(xùn)練樣本集的最后一行和一列Dqt={(x2,q,y2,q),(x3,q,y3,q),…,(xN,q,yN,q),(xq,yq)} %將預(yù)測錯誤的樣本放入樣本集中

8: 根據(jù)式(13)選擇一個系數(shù)組合(αt,ηt)，使得D(αt,ηt)≥D(αt-1,ηt-1)

9: 更新公共權(quán)重系數(shù)wt=(1-ηt)·wt-1+C(at)tytxt

10: 更新核組合系數(shù)θt=(1-ηt)·θt-1

11: 根據(jù)新來的樣本為該任務(wù)計算相應(yīng)的核矩陣；

12: 得到新的向量wt和θt，根據(jù)SVM算法為該任務(wù)訓(xùn)練新模型modelqt%更新模型

13: end if

14: end for

2.3 核函數(shù)選擇

對于本文的多任務(wù)多核在線學(xué)習(xí)算法，核函數(shù)的選擇也是一個需要考慮的問題。就現(xiàn)有的多核方法而言，目前沒有成熟的理論可以為基本核函數(shù)的選擇提供標(biāo)準(zhǔn)，大部分算法都是通過實驗的方式來選取符合樣本特征的核函數(shù)組合[22]。本文主要通過實驗來選擇核函數(shù)的組合方式。

我們知道，SVM適合數(shù)據(jù)量較小的數(shù)據(jù)集，當(dāng)數(shù)據(jù)較少時，SVM計算速度極快，因此，其對于時間的損耗基本上是忽略不計的。但是當(dāng)數(shù)據(jù)量變大時，SVM的計算就比較復(fù)雜，對于時間的花費也比較大，因此，本文采用降低核函數(shù)個數(shù)的方式來提高算法計算效率。主要從2個方面實現(xiàn)：①通過采樣的方式利用數(shù)量大小不同的數(shù)據(jù)集對算法所需的基本核函數(shù)進行選擇；②對于數(shù)據(jù)量大的數(shù)據(jù)集，在模型基本穩(wěn)定的情況下，迭代更新對模型的改變不是很大，因此，可以通過減少核函數(shù)的個數(shù)來提高算法的計算效率，以找到一個符合大數(shù)據(jù)流的核函數(shù)集。

通過文獻[23-25]可知，線性核主要用于線性模型，多項式核主要體現(xiàn)非線性模型中的全局特性，高斯核主要體現(xiàn)非線性模型中的局部特性。因此，本文將選取多項式、線性核和高斯核3種核函數(shù)作為本文模型的基本核函數(shù)，其中，多項式核和線性核的個數(shù)為1，高斯核的數(shù)量通過實驗來確定。實驗所選用的數(shù)據(jù)集為robot和Covertype Data，從準(zhǔn)確率和運行時間兩方面對給定的數(shù)據(jù)集進行實驗。隨著高斯核個數(shù)的逐漸增多，算法預(yù)測效果的變化情況如表1。

表1 不同高斯核所對應(yīng)分類準(zhǔn)確率及運行時間情況

如表1所示，對于robot數(shù)據(jù)集來說，算法的分類準(zhǔn)確率和運行時間都產(chǎn)生了比較大的波動，其中準(zhǔn)確率最高的點為高斯核個數(shù)為7的時候，這時它的收斂速度慢，運行時間長；而用時最短的點為高斯核個數(shù)為5的時候，它的準(zhǔn)確率只比最高準(zhǔn)確率低0.25%，基本接近最高的準(zhǔn)確率，并且它的收斂速度快，運行時間很短，所以綜合考慮，本文選取5個高斯核作為基本核函數(shù)；對于大數(shù)據(jù)集 Covertype Data來說，算法的分類準(zhǔn)確率都比較接近，其中高斯核個數(shù)為5和7時，算法的運行時間也都比較接近，因此，折中考慮，本文模型選擇5個高斯核來進行實驗，因為它的計算量小，對計算能力的要求不高。

表1中是對本文中提出的算法進行了實驗，但是沒有和其他算法進行一個對比。接下來會對不同算法進行實驗，以查看本文算法與其他算法在不同大小數(shù)據(jù)集上，各算法的準(zhǔn)確率與運行時間之間的比較情況。其中對比文獻有3個：MTMKO L(multi-task multi-kernel online learning)[17]提出的多任務(wù)多核在線學(xué)習(xí)算法；ADA-MTOL(accelerated dual averaging method for multi-task learning)[26]提出的基于正則化對偶平均方法的多任務(wù)在線學(xué)習(xí)算法，使用微批量技術(shù)提高收斂速度；BMKOL(budget multi-kernel online learning)[12]提出的預(yù)算量的多核在線學(xué)習(xí)算法，更新最小二乘支持向量機來進行預(yù)測。表2展示了在不同數(shù)據(jù)集上，不同算法的準(zhǔn)確率與運行時間之間的比較。

表2 不同算法的準(zhǔn)確率與運行時間

從表2中可以看出，在robot和letter數(shù)據(jù)集中，本文的算法(FP-MTMKOL)在準(zhǔn)確率和運行時間上都有一定的優(yōu)越性，這是由于這2個數(shù)據(jù)集比較小。對于準(zhǔn)確率來說，F(xiàn)P-MTMKOL使用的基本學(xué)習(xí)模型是SVM模型，SVM模型對分類的效果一直都是最優(yōu)的，因此，其分類準(zhǔn)確率要比其他算法高；對于運行時間來說，數(shù)據(jù)集較小時，SVM方法的收斂速度比較快，算法可以比較快地得到預(yù)測正確的模型，進而模型更新的次數(shù)就會相應(yīng)減少，因此，盡管在初始訓(xùn)練時SVM耗費的時間比較多，但是由于它的收斂率高，F(xiàn)P-MTMKOL的整體運行時間比其他3個算法都要少，而其他算法，尤其是BMKOL算法，它的收斂速度比較慢，所以在數(shù)據(jù)量較小的數(shù)據(jù)集中，算法所花費的時間比較多。

而在Covertype Data數(shù)據(jù)集中，F(xiàn)P-MTMKOL的準(zhǔn)確率依舊是比較好的，但運行時間不如ADA-MTOL算法，因此，在數(shù)據(jù)集的數(shù)量非常大的情況下，使用上述核函數(shù)選擇方式的算法在時間上沒有顯示出優(yōu)勢。其原因是，盡管在開始時FP-MTMKOL的收斂時間要小于其他3種算法的收斂時間，但是在算法模型趨于穩(wěn)定后，當(dāng)FP-MTMKOL需要進行模型更新時，核函數(shù)的計算就會占用大量的時間，然而在算法模型穩(wěn)定后，模型的更新只需要小幅度的調(diào)整，最初選擇核函數(shù)的種類及個數(shù)就顯得有些冗余，因此，借鑒本文中的遺忘思想，對核函數(shù)進行遺忘。由于所有核函數(shù)的權(quán)重總和為1，本文通過設(shè)置一個閾值0.1，當(dāng)核函數(shù)的權(quán)重衰減到小于閾值的情況時，將這個核函數(shù)刪除，以減少核函數(shù)的個數(shù)進而以減少算法的計算量，節(jié)約算法所需的運行時間，表3展示了遺忘變量引入后，算法的準(zhǔn)確率及運行時間。

表3 優(yōu)化算法的準(zhǔn)確率及運行時間

從表3可以看出，將核函數(shù)遺忘的方法應(yīng)用到本文算法FP-MTMKOL中，可以在保證算法預(yù)測準(zhǔn)確率的基礎(chǔ)上，更好地降低算法的運行時間，從而可以更好地處理大數(shù)據(jù)流的情況。

2.4 時空復(fù)雜度分析

數(shù)據(jù)流的產(chǎn)生是實時的、不穩(wěn)定的，這就要求算法能夠?qū)Φ絹淼牧鲾?shù)據(jù)進行實時的處理分析，需要算法的時間、空間復(fù)雜度都相對較小。由于本文在數(shù)據(jù)到來時為每個任務(wù)準(zhǔn)備了一個輸入窗口，可以將未能及時處理的數(shù)據(jù)暫時存儲起來，不會造成數(shù)據(jù)的丟失，因此，在流數(shù)據(jù)處理過程中，通過對算法實時性性能的稍微降低，確保了算法準(zhǔn)確性的提升。下面將對本文提出的算法時間和空間復(fù)雜度做一個簡單的分析。

假設(shè)有如下問題：有一個在線流數(shù)據(jù)分析場景，其中，有Q個任務(wù)，每個任務(wù)有n個d維的訓(xùn)練樣本，總共包含N個樣本，其中，N?n，設(shè)計使用M個核函數(shù)。

對于本文提出的算法模型，每一個學(xué)習(xí)周期最需要花費時間步驟有2處：①權(quán)重向量的更新，其更新方法參見(11)式和(12)式，由于它們的更新需要花費的時間是線性關(guān)系，因此，這一處時間復(fù)雜度為O(n) ；②SVM算法的計算，SVM的主要計算時間都集中在對核矩陣的計算中，核矩陣是通過核函數(shù)和支持向量聯(lián)合求解得到，本文中支持向量最大個數(shù)也就是訓(xùn)練樣本集的大小，其最壞的時間開銷為O(Mn2)，所以每個學(xué)習(xí)周期的時間復(fù)雜度為O(Mn2+n)。當(dāng)所有樣本運行完畢后，算法的時間復(fù)雜度近似為O(NMn2)。由于N?n，且核函數(shù)的個數(shù)M有限，因此，算法的時間復(fù)雜度近似為O(N)，是數(shù)據(jù)分析場景中的訓(xùn)練樣本總數(shù)的線性關(guān)系。

對于本文算法模型中的空間復(fù)雜度而言，需要占用內(nèi)存空間的地方有2處：①支持向量的保存，也就是訓(xùn)練樣本集的大小，其所占內(nèi)存空間為O(nQd)；②輸入窗口保存的訓(xùn)練樣本數(shù)，算法中為每個任務(wù)設(shè)置了一個大小為3的輸入窗口[17]，其所占內(nèi)存空間為O(3Qd)，所以該算法的空間復(fù)雜度為O(nQd)。

從以上分析來看，本文算法FP-MTMKOL的時間復(fù)雜度為O(NMn2)，只與支持向量個數(shù)和核函數(shù)個數(shù)有關(guān)，而這2個參數(shù)的值都是固定的，所以其時間復(fù)雜度近似為O(N)。從對比算法的文獻中可知，算法MTMKOL的時間復(fù)雜度為O(NMn2)，算法ADA-MTL的時間復(fù)雜度為O(NQd)，算法BMKOL的時間復(fù)雜度為O(NQd)，都是與任務(wù)數(shù)和數(shù)據(jù)的特征維度有關(guān)，因此，其時間復(fù)雜度也同樣近似為O(N)。本文算法時間復(fù)雜度在最壞情況下與對比算法基本相當(dāng)?；诖?，本文的算法有很好的時間優(yōu)勢，可以較好地滿足流數(shù)據(jù)的實時處理的需求。

3 實驗仿真結(jié)果分析

3.1 實驗設(shè)置

本文算法所有實驗的運行環(huán)境是i3處理器，2 GByte運行內(nèi)存，64位windows操作系統(tǒng)，MATLAB的版本為R2010b；所有實驗值都是通過10次交叉實驗所求的平均值。

實驗分別從分類和回歸2個方面進行算法性能分析，接下來將首先介紹實驗中所用到的評價指標(biāo)。

對于分類問題而言，本文使用分類準(zhǔn)確率和運行時間2個指標(biāo)來評估算法性能。運行時間是指整個數(shù)據(jù)集全部實驗完成的時間，時間越短，證明算法的實時性越好。分類準(zhǔn)確率是指對于給定的測試數(shù)據(jù)集，分類器正確分類的樣本數(shù)與總樣本數(shù)之比，其計算公式如(16)式，顯然準(zhǔn)確率越大，則算法的分類效果越好。

(16)

對于回歸問題而言，本文使用預(yù)測誤差值和數(shù)據(jù)吞吐量2個指標(biāo)來評估算法的性能。預(yù)測誤差采用均方根誤差(root mean square error, RMSE)，即預(yù)測值與真實值差值的平方和觀測次數(shù)N比值的平方根。顯然值越小，則預(yù)測值和真實值之間的差距越小，其計算公式為

(17)

(17)式中：xobj,i為第i個樣本的真實值；xmodel,i為第i個樣本的預(yù)測值。

數(shù)據(jù)吞吐量是指每秒鐘能夠處理的數(shù)據(jù)樣本數(shù)量，顯然吞吐量越大，則算法的實時性能越好。其計算公式為

(18)

實驗中使用的多任務(wù)分類問題數(shù)據(jù)集來自UCI機器學(xué)習(xí)數(shù)據(jù)集[27]，為驗證算法的可擴展性，分別使用了小數(shù)據(jù)集robot、較大數(shù)據(jù)集letter和Covertype Data，3個數(shù)據(jù)集的詳細信息如表4。其中，robot是一個關(guān)于機器人導(dǎo)航的數(shù)據(jù)， Letter是一個關(guān)于字母識別的數(shù)據(jù)集， Covertype Data是一個關(guān)于森林植被覆蓋類型的數(shù)據(jù)集。

表4 3個數(shù)據(jù)集信息

為評估本文算法的回歸性能情況，本次實驗中所用到的多任務(wù)回歸數(shù)據(jù)集是機場客流量數(shù)據(jù)[28]，數(shù)據(jù)集是2016年阿里舉辦的天池大賽中對機場客流預(yù)測的初賽數(shù)據(jù)集，該數(shù)據(jù)集中包含海量的機場WIFI數(shù)據(jù)，機場的不同區(qū)域存在不同的WIFI連接點，根據(jù)這些WIFI點的連接人數(shù)來預(yù)測該時間點不同區(qū)域的旅客人數(shù)，機場可以通過旅客人數(shù)的多少來增減機場基礎(chǔ)設(shè)施的使用，以提高設(shè)備的使用率，達到節(jié)能的效果。

表5中所給的樣本都是最原始的樣本，平均每分鐘有1個樣本產(chǎn)生，對于這些以分為單位的樣本，本文將它們整合后得到新的樣本。

表5 原始數(shù)據(jù)信息表

對于機場中的旅客來說，除了在候機室等待的時間，旅客在機場其他區(qū)域停留的時間一般不超過半個小時，因此，本文將原始樣本以每10 min作為一個時間間隔，重新整理為時間間隔為10 min的數(shù)據(jù)樣本。對于機場中每個區(qū)域來說，預(yù)測它的客流量就需要預(yù)測當(dāng)前該區(qū)域中所有WIFI點的連接人數(shù)，(本文假設(shè)所有旅客有且僅有一臺無線設(shè)備接入機場WIFI)，將各個WIFI點看作一個預(yù)測任務(wù)，該機場共有749個WIFI連接點，也就有749個任務(wù)。旅客在機場中停留的時間都比較長，因此，對于某一時間點而言，它一般會延續(xù)此前半小時的機場客流量的情況；另外航班每天的時間基本上是固定的，機場中旅客的人數(shù)也基本是穩(wěn)定的，所以某一時間的客流量可以參考前2天中該時刻的旅客人數(shù)。

根據(jù)以上分析，選擇4個參數(shù)作為任務(wù)的特征屬性，如表6。

表6 機場數(shù)據(jù)特征信息表

3.2 窗口數(shù)選擇

在本文模型中輸入窗口的引入會占用額外的內(nèi)存空間，因此，本小節(jié)通過實驗來選取最優(yōu)的窗口數(shù)以達到最好的計算效率。實驗選用的數(shù)據(jù)集是robot，每個任務(wù)的初始訓(xùn)練集中樣本數(shù)為75。圖1給出了隨著輸入窗口大小的逐漸增多，相應(yīng)預(yù)測效果的變化情況。

由圖1可見，算法的分類準(zhǔn)確率和運行時間隨著窗口數(shù)的變化產(chǎn)生了比較大的波動，分析圖1后發(fā)現(xiàn)，準(zhǔn)確率整體呈現(xiàn)一個先穩(wěn)定后下降的趨勢，其原因是隨著窗口數(shù)的增多，可存儲的數(shù)據(jù)量變大，意味著可出錯的樣本也會增加，所以準(zhǔn)確率會有所下降；而運行時間整體呈現(xiàn)一個先下降后上升的趨勢，其原因是預(yù)測錯誤的樣本增多，模型的更新次數(shù)就會變多，所以花費的時間就會相應(yīng)的變長。從二者性能折中，選擇2條曲線的交叉點，即窗口數(shù)為3的點為最優(yōu)的窗口數(shù)，因此，本文所有實驗值選用的輸入窗口大小為3。

圖1 算法性能隨輸入窗口數(shù)的變化情況

3.3 對偶函數(shù)值與原函數(shù)值的對比分析

根據(jù)第2節(jié)的理論分析，使用最大化對偶函數(shù)值來代替原本最小化的原函數(shù)值。為了進一步確認引入遺忘變量后的對偶函數(shù)和原函數(shù)之間的關(guān)系，我們將對偶函數(shù)和原函數(shù)的函數(shù)值進行了進一步的實驗分析對比，如圖2。

圖2 對偶函數(shù)值與原函數(shù)值的對比曲線

從圖2可以看出，對偶函數(shù)值始終小于或等于原函數(shù)值。隨著學(xué)習(xí)周期的增加，也就是迭代數(shù)增多，對偶函數(shù)整體呈現(xiàn)上升的趨勢，而原函數(shù)則整體呈現(xiàn)下降的趨勢，并且對偶函數(shù)值在不斷地逼近原函數(shù)值。由于對偶問題中的對偶向量和原問題中的邊界向量是一一對應(yīng)的，顯然對于邊界向量的求解，可以通過提升對偶函數(shù)值的方法來獲得，從而減少算法的運行時間。

3.4 算法分類性能分析

對于在線流數(shù)據(jù)而言，最開始產(chǎn)生的樣本會很少，但仍然需要利用現(xiàn)有數(shù)據(jù)進行分析預(yù)測，因此，這就需要算法在訓(xùn)練樣本集很少時也能得到很好的計算效果，也就是算法應(yīng)該具有可伸縮性。對于這種情況，實驗所選的數(shù)據(jù)集分別為robot、letter和Covertype Data，它們的數(shù)據(jù)集大小滿足規(guī)模不同的要求。另外，實驗需要分析訓(xùn)練樣本不斷增多情況下算法的預(yù)測效果情況，因此，通過設(shè)置訓(xùn)練樣本占總樣本不同比例程度來達到數(shù)據(jù)集大小不同的效果，即訓(xùn)練樣本占總樣本的比例分別為{5%，10%，15%，20%，25%，30%，35%，40%，45%，50%}，剩余的樣本作為測試樣本來驗證算法的性能。圖3分別展示了隨著訓(xùn)練樣本數(shù)的增多，算法分類準(zhǔn)確率的變化情況。

圖3 不同算法的準(zhǔn)確率變化情況

圖3a使用robot數(shù)據(jù)集進行準(zhǔn)確率比較，圖3b使用letter數(shù)據(jù)集進行準(zhǔn)確率比較，圖3c使用Covertype Data數(shù)據(jù)集進行準(zhǔn)確率比較。從這3個圖可以明顯看出，本文提出的FP-MTMKOL算法的準(zhǔn)確率較高，基本穩(wěn)定在0.96～0.98，由于實驗所用的這3個數(shù)據(jù)集大小各不相同，因此，在一定程度上可以說明FP-MTMKOL能夠較好地適應(yīng)流數(shù)據(jù)規(guī)模的變化，算法準(zhǔn)確率對于規(guī)模不同的數(shù)據(jù)集沒有太大的區(qū)別。對于MTMKOL算法來說，其準(zhǔn)確率基本上穩(wěn)定于0.958～0.978，隨著訓(xùn)練樣本數(shù)的不斷流入和增大，造成算法原來使用的數(shù)據(jù)特征可能發(fā)生改變，因此，算法準(zhǔn)確率在有些時候會有較明顯的下降，由此說明算法不能根據(jù)流數(shù)據(jù)的變化捕捉到特征的變化。對于ADA-MTOL算法來說，其準(zhǔn)確率整體呈緩慢上升的趨勢，因為隨著樣本數(shù)的增多，算法的預(yù)測結(jié)果越來越準(zhǔn)確，其準(zhǔn)確率也在提高。對于BMKOL算法，它的準(zhǔn)確率在整個數(shù)據(jù)不斷增多的過程中會有比較大的波動，在robot數(shù)據(jù)集中，樣本的個數(shù)偏少，算法的準(zhǔn)確率就比較低，隨著樣本數(shù)的增多，算法的準(zhǔn)確率也在逐步提高，對于大數(shù)據(jù)集Covertype Data，它的準(zhǔn)確率比其他2個數(shù)據(jù)集都要高許多，其原因是隨著數(shù)據(jù)量的增多，算法模型越來越接近真實值，所以其預(yù)測更加準(zhǔn)確。

對于4種算法的對比，由數(shù)據(jù)集robot實驗結(jié)果圖3a可見，F(xiàn)P-MTMKOL和MTMKOL算法的準(zhǔn)確率基本接近，這是由于FP-MTMKOL是對MTMKOL算法的優(yōu)化，是在多任務(wù)多核在線學(xué)習(xí)的基礎(chǔ)上引入遺忘特性得到的。因此，當(dāng)數(shù)據(jù)量很小時，F(xiàn)P-MTMKOL中對核函數(shù)使用的遺忘變量沒有起到比較大的效果；BMKOL算法準(zhǔn)確率比其他3個都低0.4%左右，最主要的原因是數(shù)據(jù)量太小，算法對于小數(shù)據(jù)集的收斂性不太好，導(dǎo)致準(zhǔn)確率偏低。本文算法FP-MTMKOL整體效果接近其他3種算法的最好情況。

由數(shù)據(jù)集letter實驗結(jié)果圖3b可見，F(xiàn)P-MTMKOL和MTMKOL算法的準(zhǔn)確率呈現(xiàn)出差別。這是因為隨著數(shù)據(jù)集規(guī)模的增大，F(xiàn)P-MTMKOL中引入遺忘變量使算法的更新更接近真實模型，使得算法的準(zhǔn)確率有所提高； BMKOL算法準(zhǔn)確率基本上是穩(wěn)步上升的，隨著算法的收斂，準(zhǔn)確率也在不斷提高。本文算法FP-MTMKOL整體效果好于其他3種算法。

由數(shù)據(jù)集Covertype Data實驗結(jié)果圖3c可見，數(shù)據(jù)規(guī)模越大，F(xiàn)P-MTMKOL中的遺忘變量的作用越明顯，通過逐步降低歷史樣本在分類器中的權(quán)重，分類器的效果變得更好，其準(zhǔn)確率比其他3個都高。MTMKOL算法和ADA-MTOL算法的準(zhǔn)確率基本接近，這是由于當(dāng)數(shù)據(jù)規(guī)模增大后，ADA-MTOL算法收斂后，預(yù)測準(zhǔn)確率也在提高，因為數(shù)據(jù)量之大基本上忽視了算法未收斂時造成的錯誤預(yù)測樣本，因此，這2個算法的準(zhǔn)確率相近。BMKOL算法準(zhǔn)確率也有一定的提升。

3.5 回歸性能分析

回歸問題需要算法預(yù)測出一個具體數(shù)值，能否減小預(yù)測值與真實值之間的差距，以達到收斂是衡量回歸算法的主要指標(biāo)。本文對這類問題的實驗選用3.1節(jié)中介紹的機場客流量數(shù)據(jù)，通過預(yù)測不同人流密集區(qū)域的連接WIFI人數(shù)作為本實驗中的任務(wù)，在此共選擇了100個任務(wù)點。每個任務(wù)總共有接近11天的數(shù)據(jù)樣本，實驗中選取了前12 h的數(shù)據(jù)作為初始的訓(xùn)練樣本，剩余的作為測試樣本。圖4比較了和3.4節(jié)一樣的4個不同算法的回歸性能。

圖4 選定數(shù)據(jù)集上的RMSE值

從圖4中可以看出，算法的RMSE值有高有低。對于本文提出的FP-MTMKOL來說，其RMSE值為1.8，比其他3個算法都要小，主要原因是在使用SVM模型的基礎(chǔ)上引入了遺忘變量，收斂速度更快，進而使得預(yù)測誤差值變得很?。粚τ谒惴∕TMKOL，其RMSE值只比FP-MTMKOL低一點，因為其算法的收斂性較好，可以很快得到穩(wěn)定的算法，所以其誤差值比較??；對于算法ADA-MTOL和算法BMKOL，它們的RMSE值相對大一些，原因是這2個模型在開始運行時，由于使用的樣本數(shù)據(jù)量偏少，無法很好地獲得數(shù)據(jù)的特征，導(dǎo)致算法的結(jié)果偏差較大，隨著樣本數(shù)據(jù)量的增多，算法的RMSE也有所降低。

3.6 不同任務(wù)數(shù)回歸性能分析

本文認為將多個相關(guān)任務(wù)的聯(lián)合學(xué)習(xí)方式會優(yōu)于單個任務(wù)獨立學(xué)習(xí)的方式，因為其具有提取其他相關(guān)任務(wù)內(nèi)部信息的能力，因此，能夠極好地發(fā)揮輔助信息資源的作用。為了驗證該說法的準(zhǔn)確性，通過給出不同數(shù)量的任務(wù)個數(shù)對本文算法進行性能測試，并評估相應(yīng)的RMSE值，用于判斷多任務(wù)聯(lián)合學(xué)習(xí)的有效性，同時統(tǒng)計在任務(wù)個數(shù)不同時算法的吞吐量情況，以此判斷任務(wù)個數(shù)對算法吞吐量的影響。實驗仍然選用機場客流量數(shù)據(jù)，將所有WIFI點作為本實驗中所用的任務(wù)，共749個任務(wù)點。在所有的任務(wù)中，分別選取1，100，200，300，400，500，600，749個不同數(shù)量的任務(wù)數(shù)，對應(yīng)的WiFi點進行隨機選取。實驗中依然使用每個任務(wù)接近11天的數(shù)據(jù)樣本，同時用前12 h的數(shù)據(jù)作為初始訓(xùn)練樣本，剩余的作為測試樣本。圖5給出了隨著任務(wù)數(shù)的增多預(yù)測結(jié)果的變化情況。

圖5 不同任務(wù)數(shù)的算法性能變化情況

由圖5可知，算法的RMSE值和吞吐量隨著任務(wù)數(shù)的增加產(chǎn)生了一定的波動，其中RMSE值呈現(xiàn)一個平穩(wěn)下降的趨勢，原因是隨著任務(wù)數(shù)的增多，預(yù)測誤差值逐步減??；而吞吐量整體呈現(xiàn)一個先上升后平穩(wěn)的趨勢，原因是隨著任務(wù)數(shù)的增加，算法的誤差值越來越小，模型更新的次數(shù)也逐漸減少，因此，每秒可以處理的樣本數(shù)就越來越多。顯然多任務(wù)共同學(xué)習(xí)的效果要明顯優(yōu)于單任務(wù)學(xué)習(xí)方式。

4 總 結(jié)

本文提出了一種帶有遺忘特性的多任務(wù)多核在線算法，主要創(chuàng)新點表現(xiàn)在減小算法的計算復(fù)雜度和模型更新次數(shù)的設(shè)計上。首先，對于模型的計算復(fù)雜度而言，基本核函數(shù)選擇的數(shù)量直接影響到模型的計算復(fù)雜程度，因此，當(dāng)數(shù)據(jù)量增大、訓(xùn)練模型穩(wěn)定時，通過閾值限定的方法對核函數(shù)進行遺忘，從而減少基本核函數(shù)的使用個數(shù)，使得計算更加簡單快捷；其次，在減少模型更新迭代次數(shù)上，通過引入一個遺忘變量，對權(quán)重更新過程進行了優(yōu)化并進行了理論分析，實驗結(jié)果表明，本文算法具有一定的理論參考價值。但是算法在進行核函數(shù)計算時，會將所有的核函數(shù)依次進行疊加運算，就使得算法的計算量變得很大，從而導(dǎo)致所用時間的增長，對于這個問題，未來可以從獲取算法的稀疏解這一方面進行考慮，對數(shù)據(jù)的特征進一步壓縮，使得算法的計算變得簡單，以減少算法的時間。