正則化多任務(wù)學(xué)習(xí)的快速算法*

史熒中，汪菊琴，許 敏，王士同

1.江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122

2.無錫職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)學(xué)院，江蘇 無錫 214121

正則化多任務(wù)學(xué)習(xí)的快速算法*

史熒中1,2+，汪菊琴1,2，許 敏1，王士同1

1.江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無錫 214122

2.無錫職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)學(xué)院，江蘇 無錫 214121

SHI Yingzhong,WANG Juqin,XU Min,et al.Fast algorithm for regularized multi-task learning.Journal of Frontiers of Computer Science and Technology,2017,11(6)：988-997.

正則化多任務(wù)學(xué)習(xí)（regularized multi-task learning，rMTL）方法及其擴(kuò)展方法在理論研究及實(shí)際應(yīng)用方面已經(jīng)取得了較好的成果。然而以往方法僅關(guān)注于多個任務(wù)之間的關(guān)聯(lián)，而未充分考慮算法的復(fù)雜度，較高的計算代價限制了其在大數(shù)據(jù)集上的實(shí)用性。針對此不足，結(jié)合核心向量機(jī)（core vector machine，CVM）理論，提出了適用于多任務(wù)大數(shù)據(jù)集的快速正則化多任務(wù)學(xué)習(xí)（fast regularized multi-task learning，F(xiàn)rMTL）方法。FrMTL方法有著與rMTL方法相當(dāng)?shù)姆诸愋阅?，而基于CVM理論的FrMTL-CVM算法的漸近線性時間復(fù)雜度又能使其在面對大數(shù)據(jù)集時仍然能夠獲得較快的決策速度。該方法的有效性在實(shí)驗(yàn)中得到了驗(yàn)證。

多任務(wù)學(xué)習(xí)；大數(shù)據(jù)集；核心向量機(jī)；快速分類

1 引言

近期的研究[1-6]表明，較之于單獨(dú)學(xué)習(xí)各個子任務(wù)，對多個相關(guān)子任務(wù)同時學(xué)習(xí)能有效地提升預(yù)測性能。事實(shí)上，當(dāng)同時學(xué)習(xí)多個復(fù)雜的任務(wù)時，從其他任務(wù)中獲取的信號能作為非常有益的歸納信息[1-2]。學(xué)者們從多任務(wù)分類[2-7]、聚類[8-10]、回歸[11-13]、特征選擇[14-15]等方面展開了研究，并在網(wǎng)頁標(biāo)注、人臉識別、年齡估計、語音與圖像處理、疾病預(yù)測、生物醫(yī)學(xué)等[16-18]多個應(yīng)用領(lǐng)域都取得了豐富的成果。一致性原理[19-20]又對此現(xiàn)象給出了理論保障，即若最大化各相關(guān)子學(xué)習(xí)機(jī)的一致性，則能使各子學(xué)習(xí)機(jī)的性能得到改善[19-22]。

多任務(wù)學(xué)習(xí)研究的角度之一，是子任務(wù)之間的相關(guān)結(jié)構(gòu)。Evgeniou等人提出了正則化多任務(wù)學(xué)習(xí)（regularized multi-task learning，rMTL）[6]方法，其核心思想是多個子任務(wù)呈團(tuán)狀分布，共享同一個中心。隨后，學(xué)者們從實(shí)踐應(yīng)用的角度出發(fā)，研究了在應(yīng)用領(lǐng)域特別是生物醫(yī)學(xué)方面，當(dāng)子任務(wù)之間呈現(xiàn)出較清晰的圖狀關(guān)聯(lián)和樹狀關(guān)聯(lián)時的多任務(wù)學(xué)習(xí)方法。Friedman等人依據(jù)實(shí)際應(yīng)用中蛋白質(zhì)組之間存在特定的圖狀結(jié)構(gòu)，對蛋白質(zhì)組的信號進(jìn)行了分析[16]。Chen等人基于子任務(wù)之間的圖結(jié)構(gòu)，進(jìn)行了果蠅基因表示圖的自動標(biāo)記[17]。Widmer等人利用了生物之間特定的樹狀及圖狀關(guān)聯(lián)進(jìn)行了真核生物的生物序列分析[18]。也有學(xué)者將多任務(wù)學(xué)習(xí)方法推廣到其他方面，如多類多任務(wù)學(xué)習(xí)方法[7]等。其中，rMTL方法以其模型的簡潔性而成為多任務(wù)學(xué)習(xí)理論研究的基礎(chǔ)，并擴(kuò)展出許多其他方法。

雖然各種多任務(wù)學(xué)習(xí)方法在理論及實(shí)踐中都已經(jīng)取得了較好的成果，但當(dāng)前社會信息化的發(fā)展對多任務(wù)學(xué)習(xí)提出了新的挑戰(zhàn)。隨著大數(shù)據(jù)時代的來臨，社交信息及生物基因信息越來越龐大，多任務(wù)學(xué)習(xí)算法的時間及空間復(fù)雜度也越來越彰顯其重要性。作為其他多任務(wù)學(xué)習(xí)方法的基石，rMTL方法的對偶問題等價于核空間中的另一支持向量機(jī)（support vector machine，SVM）問題，其算法時間復(fù)雜度一般情況下為O(n3)，其中n為問題空間中的樣本容量。即使采用序貫最小化[23]方法來求解rMTL的對偶問題，使其復(fù)雜度降為O(n2.3)，rMTL在面對大數(shù)據(jù)集時仍有很大的局限性。而最近面向數(shù)據(jù)流的研究[24]雖然能快速求解多個子任務(wù)，但其模型并不能直接應(yīng)用于多任務(wù)學(xué)習(xí)領(lǐng)域。如何尋找出一種新的多任務(wù)學(xué)習(xí)方法，既能保持rMTL方法良好的特性，又能在面對大數(shù)據(jù)集時有較好的時間性能，正是本文的出發(fā)點(diǎn)。

結(jié)合前期在數(shù)據(jù)流領(lǐng)域的研究基礎(chǔ)[24]，本文提出了快速正則化多任務(wù)學(xué)習(xí)（fast regularized multi-task learning，F(xiàn)rMTL）方法，并基于核心向量機(jī)[25]（core vector machine，CVM）理論給出了FrMTL方法的快速算法（fast regularized multi-task learning core vector machine，F(xiàn)rMTL-CVM）。所提FrMTL方法及其快速算法FrMTL-CVM具有以下特點(diǎn)：

（1）FrMTL方法采用了與rMTL方法相同的理念，即在特征空間中共享同一個矢量。在分類性能上，F(xiàn)rMTL方法與rMTL方法相當(dāng)。

（2）FrMTL方法可依據(jù)CVM理論[25]設(shè)計出快速算法FrMTL-CVM，以應(yīng)對多任務(wù)大數(shù)據(jù)集問題，其漸近時間復(fù)雜度與樣本總?cè)萘縩呈近線性關(guān)系。

本文組織結(jié)構(gòu)如下：第2章介紹rMTL方法及其他相關(guān)工作；第3章研究FrMTL方法；第4章討論核心向量機(jī)及FrMTL方法的快速算法；第5章為實(shí)驗(yàn)結(jié)果與分析；第6章總結(jié)全文。

2 相關(guān)工作

多任務(wù)學(xué)習(xí)：假設(shè)有T個學(xué)習(xí)任務(wù)，每個任務(wù)中的樣本點(diǎn)取自于空間X×Y，X??d,Y??。每個任務(wù)中包含m個樣本點(diǎn){(x1t,y1t),(x2t,y2t),…,(xmt,ymt)}，其概率分布Pt是不同的。多任務(wù)學(xué)習(xí)的核心思想是同時求解T個任務(wù)，利用其他相關(guān)任務(wù)中的有效信息來提高學(xué)習(xí)所得模型的泛化能力。

Evgeniou等人在2004年提出了正則化多任務(wù)學(xué)習(xí)方法[6]，在保持各個子學(xué)習(xí)機(jī)局部優(yōu)化的同時，使多個學(xué)習(xí)機(jī)之間的全局差異最小化。他們認(rèn)為，多個子任務(wù)的決策模型應(yīng)該是相似的，并共享核空間中的某個公共矢量，每個子任務(wù)的決策模型wt由公共矢量w0與偏差量vt構(gòu)成，即wt=w0+vt。rMTL方法的目標(biāo)函數(shù)如下：

參照文獻(xiàn)[6]，rMTL方法原始問題的對偶問題為如下二次規(guī)劃問題：

其中，i∈{1,2,…,m}，t∈{1,2,…,T}，K(x,·)為擴(kuò)展核空間中的某個核函數(shù)。其決策函數(shù)為：

由式（2）可知，rMTL方法的對偶問題為核空間中的SVM問題，求解的時間復(fù)雜度為O(n3)，其中n為問題空間中的樣本容量。即便采用序貫最小化[23]（sequential minimal optimization，SMO）方法來求解rMTL的對偶問題，使其復(fù)雜度降為O(n2.3)，也很難適應(yīng)大數(shù)據(jù)時代的算法性能需求。

為了將rMTL方法推廣到更多的實(shí)踐應(yīng)用上，Widmer[18]和Chen[17]等人依據(jù)子任務(wù)之間呈現(xiàn)不同的結(jié)構(gòu)，設(shè)計出了Tree-MTL方法及Graphical-MTL方法。其中Tree-MTL方法是為了更好地進(jìn)行生物序列分析，利用了第t個模型wt與它的父模型wparent(t)之間的相關(guān)性，假設(shè)可以通過最小化它們的差異||wt-wparent(t)||使子模型與父模型相互增益[18]：

Friedman等人依據(jù)實(shí)際應(yīng)用中蛋白質(zhì)組之間存在特定的圖狀結(jié)構(gòu)，對蛋白質(zhì)組的信號進(jìn)行了分析[16]。2013年，Chen等人提出了改進(jìn)型交互結(jié)構(gòu)優(yōu)化（improved alternating structure optimization，iASO）方法[17]，利用果蠅基因之間呈圖狀結(jié)構(gòu)的特性，對基因進(jìn)行自動標(biāo)記。

樹狀多任務(wù)學(xué)習(xí)模型及圖狀多任務(wù)模型向?qū)嵱梅较蜃兓?，但子任?wù)之間存在的復(fù)雜關(guān)聯(lián)給計算帶來了一定的麻煩，因而在面向較大規(guī)模數(shù)據(jù)集時，計算時間得不到保障。iASO雖然解決了局部最優(yōu)化問題，但只適用于小樣本數(shù)據(jù)集[17]。

Shi等人在針對數(shù)據(jù)流的分類研究中，提出了ITA-SVM方法[24]。該方法能同時求解多個子任務(wù)，當(dāng)應(yīng)用于較大規(guī)模數(shù)據(jù)集時，算法的漸近時間復(fù)雜度接近于O(n)。但該方法只適用于多個子任務(wù)呈序列狀分布的情形，并不能直接應(yīng)用于傳統(tǒng)的多任務(wù)學(xué)習(xí)情形。

3 快速正則化多任務(wù)學(xué)習(xí)方法FrMTL

鑒于以往MTL方法在針對較大規(guī)模數(shù)據(jù)集時的復(fù)雜度瓶頸，本文結(jié)合ITA-SVM[24]的思路，提出了與rMTL方法分類能力相當(dāng)，且具有快速處理多任務(wù)大數(shù)據(jù)集能力的FrMTL方法。對子任務(wù)之間具有樹狀及圖狀結(jié)構(gòu)的場景，由于子任務(wù)之間的耦合帶來了模型及計算上的較大差異，將另文表述其快速算法。

FrMTL方法有著與rMTL方法及ITA-SVM方法相同的策略，即基于共享矢量協(xié)同求解多個子任務(wù)。為使FrMTL方法能進(jìn)一步用快速算法求解，本文按文獻(xiàn)[24-27]的方法對式（1）略作改變，引入分類間隙ρ，通過推導(dǎo)可得到適于對多任務(wù)大數(shù)據(jù)集進(jìn)行快速求解的對偶形式。FrMTL方法的目標(biāo)函數(shù)為：

通過推導(dǎo)，不難得到式（5）的對偶問題如下：

其中：

K=[Kis,jt]N×N,Kis,jt=φ(xis)Tφ(xjt)，φ為核函數(shù)

I為單位矩陣，α=(α11,α21,…,αm1,…,α1T,α2T,…,αmT)T

由式（6）、（7）可知，F(xiàn)rMTL問題的對偶形式等價于核空間中的另一SVM問題，其時間復(fù)雜度為O(n3),采用SMO方法求解的時間復(fù)雜度為O(n2.3)，與rMTL方法相比，其時間性能并無本質(zhì)的變化。但當(dāng)借助核心向量機(jī)技術(shù)快速求解時，式（6）的時間復(fù)雜度及空間復(fù)雜度可降為O(n)。

4 核心向量機(jī)及FrMTL方法的快速算法

4.1 核心向量機(jī)

最小包含球（minimum enclosing ball，MEB）問題[28]可以轉(zhuǎn)化為二次規(guī)劃問題的矩陣形式：

其中，α=[α1,α2,…,αn]T為Lagrange乘子；Kn×n=[k(xi,xj)]=[?(xi)T?(xj)]為核矩陣。diag(K)表示由核矩陣K的主對角線元素組成的向量。

考察核函數(shù)中的特殊情形，即核矩陣對角元素恒為常數(shù)：

Tsang等人在文獻(xiàn)[25]中指出，形如式（8）且滿足式（9）的二次規(guī)劃問題，均等價于求解MEB問題。他們在此基礎(chǔ)上開發(fā)了核心向量機(jī)（core vector machine，CVM），CVM算法對于處理大規(guī)模數(shù)據(jù)集發(fā)揮了驚人的效果。對不滿足式（9）的形如式（8）的二次規(guī)劃問題，也可以使用核心集方法進(jìn)行快速求解，給核空間中任意樣本點(diǎn)?(xi)附加一維新特征δi∈R，形成新特征空間中的新樣本使其滿足MEB問題的式（9）條件，然后求解在新特征空間中的最小包含球。對該最小包含球增加一個約束條件，即最小包含球中增加的特征維對應(yīng)的中心固定在原點(diǎn)，即中心為這里c為原特征空間中的最小包含球球心。該問題的標(biāo)準(zhǔn)形式如下：

4.2 FrMTL-CVM算法描述

FrMTL方法的求解是一個普通的二次規(guī)劃問題，其求解時間復(fù)雜度為O(n2)~O(n3)，對于大數(shù)據(jù)集來說應(yīng)是相當(dāng)可觀的計算開銷。仔細(xì)觀察式（6），它可以轉(zhuǎn)化為形如式（11）的MEB問題。因此，F(xiàn)rMTL方法可以利用核心向量機(jī)技巧來求解。并且MEB問題的求解過程中，只需要計算核心集之外的點(diǎn)到核心集的距離，無需計算所有點(diǎn)之間的相互距離，因此不必預(yù)先計算核矩陣H，這就使FrMTL方法能用快速算法求解。

可以將式（6）等價地改寫如下：

這是一個MEB問題，其中Δ=-diag(H)+η1，通過調(diào)節(jié)常數(shù)η的值，使Δ≥0。

FrMTL-CVM算法的輸入為大數(shù)據(jù)集S，核心集逼近精度ε及η、Δ等參數(shù)；輸出為核心集St和權(quán)重系數(shù)α。下面給出實(shí)現(xiàn)步驟：

（1）初始化核心集S0，最小包含球中心c0，半徑R0，迭代次數(shù)t=1。

（3）在擴(kuò)展的特征空間中找到離ct最遠(yuǎn)的點(diǎn)x,加入核心集，使得St+1=St?x。

（4）對新的CCMEB進(jìn)行求解，得到新的球心ct+1和半徑Rt+1，權(quán)重系數(shù)α；計算新的球心到其他各點(diǎn)的距離；t=t+1，轉(zhuǎn)（2）。

（5）終止訓(xùn)練，返回核心集St，權(quán)重系數(shù)α。

在實(shí)踐中發(fā)現(xiàn)，如果η取值較大，則FrMTLCVM算法收斂速度就非?？?，所得到的核心集數(shù)量較少，實(shí)驗(yàn)精度也隨之而降低。對FrMTL-CVM算法而言，如果選用高斯核作為核函數(shù)，可以更容易預(yù)估η的合理取值。

從本質(zhì)上來講，F(xiàn)rMTL-CVM算法是基于MEB近似算法的一個特例，因此在衡量系統(tǒng)開銷時，有關(guān)核心集的結(jié)論適用于FrMTL-CVM算法。本文根據(jù)參考文獻(xiàn)[24-27]，直接給出相似的性質(zhì)。

性質(zhì)1對于給定的近似誤差ε，由FrMTL-CVM算法求得的核心集數(shù)量的上界為O(1/ε)，算法迭代次數(shù)的上界為O(1/ε)，求得的支持向量數(shù)量上界為O(1/ε)。

性質(zhì)2對于給定的誤差ε，F(xiàn)rMTL-CVM算法的時間復(fù)雜度的上界為O(N/ε2+1/ε4)。

5 實(shí)驗(yàn)結(jié)果與分析

鑒于rMTL方法[6]的良好性能，且它是眾多擴(kuò)展方法的基礎(chǔ)，本文將其作為實(shí)驗(yàn)參照，以評估FrMTL方法及FrMTL-CVM快速算法。實(shí)驗(yàn)將從兩方面進(jìn)行：首先需要驗(yàn)證FrMTL方法的分類性能是否與rMTL方法相當(dāng)，因FrMTL方法保持良好的分類性能是其快速算法有效的前提；其次需要驗(yàn)證FrMTL-CVM在面對大數(shù)據(jù)集時是否具有較好的時間效率，且其時間性能是否與CVM理論相符。

人生就是一條路，在起跑線的起點(diǎn)，所有的人都整裝待發(fā)，但能跑到最后的那些人都是最能堅持的，他們才是最成功的。在奔跑的路上，我失掉了堅持，迷茫、無助都向我逼近，我?guī)缀踅咏罎⒌倪吘?。找回堅持，是一個嶄新的開始。

5.1 實(shí)驗(yàn)設(shè)置

5.1.1 實(shí)驗(yàn)平臺信息

實(shí)驗(yàn)環(huán)境：操作系統(tǒng)為WindowsXP；處理器為奔騰1.87 GHz；內(nèi)存為4 GB；主要應(yīng)用軟件為Matlab R2010a。

5.1.2 所用方法

表1列出了下文實(shí)驗(yàn)的各個算法名，并列出了相關(guān)算法中的主要參數(shù)。表1中的參數(shù)ε僅指CVM算法中的近似程度，而求解二次規(guī)劃問題時的精度參數(shù)不再列出，都取默認(rèn)值ε′=1E-6。

Table 1 Methods and parameters in experiments表1 實(shí)驗(yàn)中各種算法及主要參數(shù)

5.1.3 實(shí)驗(yàn)數(shù)據(jù)

為了驗(yàn)證FrMTL方法的適應(yīng)能力，本文將在模擬數(shù)據(jù)集及真實(shí)數(shù)據(jù)集上展開實(shí)驗(yàn)。模擬數(shù)據(jù)集以數(shù)據(jù)集DS0為基礎(chǔ)來生成，DS0包含3個子任務(wù)，共300個樣本點(diǎn)，每個子任務(wù)正負(fù)類樣本均為50。其中子任務(wù)T1的正類中心(0,0)，方差為1，負(fù)類中心(2.5, 0)，方差為1；子任務(wù)T2的正類中心(0,0)，方差為1，負(fù)類中心(2.5,0)，方差為1；子任務(wù)T3的正類中心(0, 0)，方差為1.1，負(fù)類中心(2.5,0)，方差為1.1。模擬數(shù)據(jù)集基于DS0生成，由DS0中的子任務(wù)經(jīng)過不同程度的旋轉(zhuǎn)、平移來模擬子任務(wù)之間不同的相關(guān)性。數(shù)據(jù)集DS1中的Task1直接采用DS0中的T1，Task2為T2進(jìn)行一定的旋轉(zhuǎn)（Rotate=5°）而生成，Task3為T3進(jìn)行一定的平移（Move=0.05）而生成。DS2~DS6中的子任務(wù)Task1都取為DS0中的T1，Task2、Task3則由DS0中的T2加大旋轉(zhuǎn)量，T3增加平移量而生成。模擬數(shù)據(jù)集DS1~DS6，以及用于評估算法時間性能的數(shù)據(jù)集DS7的具體描述如表2所示。

5.1.4 實(shí)驗(yàn)參數(shù)的設(shè)置

為了客觀地評估各種方法的分類性能，在每個數(shù)據(jù)集上，本文除訓(xùn)練樣本外，還獨(dú)立生成了相同分布的測試樣本。訓(xùn)練樣本和測試樣本各有10組，共進(jìn)行10次重復(fù)實(shí)驗(yàn)，以盡量減少因模擬數(shù)據(jù)的隨機(jī)性而帶來的不客觀性。實(shí)驗(yàn)分為兩個階段：第一階段是針對訓(xùn)練樣本，優(yōu)化各方法的系統(tǒng)參數(shù)；第二階段是根據(jù)前一階段得到的參數(shù)設(shè)置對訓(xùn)練樣本建模，使用測試樣本來評估各方法的分類性能。優(yōu)化系統(tǒng)參數(shù)時采用網(wǎng)格遍歷法，其中參數(shù)C的遍歷范圍是10[-2,…,2]；參數(shù)λ的遍歷范圍是10[-2,…,2]；本文選取使用最廣泛的高斯核，其核帶寬取值為2[-2,…,5]。

Table 2 Description of artificial datasets表2 實(shí)驗(yàn)所用人工數(shù)據(jù)集

5.2 FrMTL方法的分類能力

本階段將對FrMTL方法進(jìn)行分類準(zhǔn)確率的評估。用于實(shí)驗(yàn)對比的其他方法分別為：（1）對每個任務(wù)分別用SVM方法獨(dú)立求解，記為SVMs；（2）rMTL方法。其中FrMTL-CVM指的是用核心向量機(jī)求解FrMTL相應(yīng)的二次規(guī)劃問題。

在數(shù)據(jù)集DS1~DS6上，按照實(shí)驗(yàn)流程，對每個對比方法都進(jìn)行10次重復(fù)實(shí)驗(yàn)。在每個數(shù)據(jù)集上，求得對各個子任務(wù)的分類準(zhǔn)確率及標(biāo)準(zhǔn)差，如表3所示。圖1顯示的是當(dāng)子任務(wù)之間的偏移量逐漸變大時，也即在數(shù)據(jù)集DS1~DS6上，各個對比方法在每個數(shù)據(jù)集上3個子任務(wù)的平均準(zhǔn)確率。

由表3和圖1可以得到如下結(jié)論：

（1）從表3中可以看出，當(dāng)采用多任務(wù)方式同時求解3個相關(guān)子任務(wù)時，rMTL方法和FrMTL方法及其快速算法FrMTL-CVM的分類性能遠(yuǎn)優(yōu)于用普通SVM方法單獨(dú)求解各個子任務(wù)。

（2）對比表3中的rMTL方法和FrMTL方法及其快速算法FrMTL-CVM，在6個數(shù)據(jù)集的共18個子任務(wù)的求解中，rMTL方法在7個子任務(wù)的求解中取得了較好的效果，F(xiàn)rMTL方法在10次子任務(wù)的求解中取得了較好的效果，而快速算法FrMTL-CVM在求解3個子任務(wù)時有較好的效果。因而FrMTL方法的分類能力與rMTL方法是可比較的。而FrMTL-CVM方法與rMTL方法也是相當(dāng)?shù)摹?/p>

Table 3 Classification accuracy and deviation on DS1~DS6表3 在數(shù)據(jù)集DS1~DS6上各方法的平均準(zhǔn)確率及標(biāo)準(zhǔn)差

Fig.1 Accuracy with different rotations in sub-task圖1 隨子任務(wù)之間偏移程度的增加各方法的準(zhǔn)確率

（3）由圖1可知，隨著子任務(wù)之間偏移量變大，rMTL方法和FrMTL方法的分類性能緩慢下降，但仍然優(yōu)于采用SVM方法單獨(dú)求解各子任務(wù)。另外，當(dāng)子任務(wù)之間關(guān)聯(lián)較強(qiáng)時，rMTL方法和FrMTL方法的分類性能完全相當(dāng)，而當(dāng)子任務(wù)之間關(guān)聯(lián)較弱時，這兩個方法的分類能力仍然是相當(dāng)?shù)摹？焖偎惴‵rMTLCVM的分類能力與rMTL方法及FrMTL方法總體上是相當(dāng)?shù)摹?/p>

5.3 FrMTL方法的時間性能

鑒于在數(shù)據(jù)集DS2上，rMTL方法和FrMTL方法的分類性能非常接近，本文以數(shù)據(jù)集DS2為基礎(chǔ)，逐漸增加訓(xùn)練樣本及測試樣本的容量，以此來評估各方法的時間效率。各數(shù)據(jù)的容量依次為300，600，1 500，3 000，6 000，15 000，30 000。同樣獨(dú)立生成10組訓(xùn)練樣本及測試樣本，并將各方法在不同容量樣本上的平均準(zhǔn)確率與標(biāo)準(zhǔn)差、平均訓(xùn)練時間及標(biāo)準(zhǔn)差分別報告在表4及表5中（其中—表示在本文實(shí)驗(yàn)環(huán)境中無法得到相應(yīng)結(jié)果）。為了能更清晰地分析隨數(shù)據(jù)量增加各方法的時間性能，以lgn（n為樣本量）為橫坐標(biāo)，lgS（S為運(yùn)行時間，單位為s）為縱坐標(biāo)繪制各方法的時間性能圖，將指數(shù)曲線轉(zhuǎn)化為近線性曲線，斜率代表指數(shù)量級，如圖2所示。

Table 4 Classification accuracy and deviation with different dataset sizes表4 各方法在不同數(shù)據(jù)量下的平均分類準(zhǔn)確率及標(biāo)準(zhǔn)差

Table 5 Training time and deviation with different dataset sizes表5 各方法在不同數(shù)據(jù)量下的平均訓(xùn)練時間及標(biāo)準(zhǔn)差

Fig.2 Training time with different dataset sizes圖2 隨訓(xùn)練樣本量的增加各方法的訓(xùn)練時間

從表4、表5及圖2可以得到如下結(jié)論：

（1）從表4中可以看出，隨著訓(xùn)練數(shù)據(jù)量的增加，各方法的分類性能逐漸增高，其中FrMTL方法及其快速算法FrMTL-CVM的分類性能與rMTL相當(dāng)，都優(yōu)于用普通的SVM方法單獨(dú)求解各個子任務(wù)。同時，普通的SVM方法及rMTL方法、FrMTL方法都需要預(yù)先計算核矩陣，因此相應(yīng)方法受硬件約束較大，當(dāng)數(shù)據(jù)量較大時，相應(yīng)方法無法繼續(xù)求解。而FrMTLCVM無需預(yù)先計算核矩陣，能對較大容量的數(shù)據(jù)集進(jìn)行訓(xùn)練，因而能得到泛化能力更強(qiáng)的模型。

（2）從表5中可以看出，在數(shù)據(jù)量較小時，F(xiàn)rMTLCVM方法在求解時間上并無優(yōu)勢，但隨著數(shù)據(jù)量的增加，F(xiàn)rMTL-CVM的求解時間緩慢增加，明顯優(yōu)于普通二次規(guī)劃的求解。

（3）由圖2可知，當(dāng)采用普通SVM方法求解時，隨著數(shù)據(jù)量的變化，SVMs及FrMTL方法所用時間具有相同的趨勢，準(zhǔn)直線的斜率接近于3，顯示出用普通方法求解二次規(guī)劃問題時的O(n3)時間復(fù)雜度。當(dāng)用SMO方法求解rMTL問題時，斜率略大于2，與其O(n2.3)的理論時間復(fù)雜度一致。而采用CVM方法求解的FrMTL-CVM算法所用時間的準(zhǔn)直線的斜率趨勢略大于1，與其理論上的近線性時間復(fù)雜度相符，時間性能遠(yuǎn)優(yōu)于SMO方法。當(dāng)然，F(xiàn)rMTL-CVM方法訓(xùn)練所用時間的穩(wěn)定性并不算好，其原因是當(dāng)用CVM方法求解時，不同數(shù)據(jù)集上求解所得的支持向量數(shù)目可能有較大差異，由此造成了求解時間的波動性較大。但總體而言，F(xiàn)rMTL-CVM算法的時間性能得到保障，其時間復(fù)雜度的上界為O(n/ε2+1/ε4)，ε為設(shè)定的近似誤差。

由實(shí)驗(yàn)可知，F(xiàn)rMTL方法的分類性能與rMTL方法相當(dāng)，采用快速方法求解的FrMTL-CVM方法在分類性能上并無很大變化，仍然與rMTL方法相當(dāng)。而當(dāng)數(shù)據(jù)量較大時，F(xiàn)rMTL-CVM方法的處理能力及其時間性能遠(yuǎn)優(yōu)于其他方法。

6 結(jié)束語

本文提出了面向多任務(wù)學(xué)習(xí)的快速正則化多任務(wù)學(xué)習(xí)方法FrMTL。由于借鑒了rMTL方法及ITASVM方法中共享矢量的思想及兼顧局部優(yōu)化和全局優(yōu)化的優(yōu)點(diǎn)，F(xiàn)rMTL方法的分類性能與rMTL方法是等價的。而FrMTL-CVM方法良好的時間性能使面對多任務(wù)大數(shù)據(jù)集時仍能獲得相對較快的決策速度。當(dāng)然FrMTL方法仍需要進(jìn)一步研究以適應(yīng)更多的應(yīng)用場景，特別是當(dāng)多個子任務(wù)呈網(wǎng)狀分布或樹狀分布時，如何解決此類更復(fù)雜耦合關(guān)系帶來的矩陣求逆問題，將是更有意義的挑戰(zhàn)。

[1]Caruana R.Multitask learning[J].Machine Learning,1997, 28(1):41-75.

[2]Baxter J.A model of inductive bias learning[J].Journal of Artificial Intelligence Research,2000,12(1):149-198.

[3]Sun Shiliang.Multitask learning for EEG-based biometrics [C]//Proceedings of the 19th International Conference on Pattern Recognition,Tampa,USA,Dec 8-11,2008.Washington:IEEE Computer Society,2008:1-4.

[4]Yuan Xiaotong,Yan Shuicheng.Visual classification with multi-task joint sparse representation[J].IEEE Transactions on Image Processing,2012,21(10):4349-4360.

[5]Parameswaran S,Weinberger K.Large margin multi-task metric learning[C]//Advances in Neural Information Processing Systems 23:Proceedings of the 24th Annual Conference on Neural Information Processing Systems,Vancouver,Canada,Dec 6-9,2010.Red Hook,USA:Curran Associates,2011:1867-1875.

[6]Evgeniou T,Pontil M.Regularized multi-task learning[C]// Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Seattle, USA,Aug 22-25,2004.New York:ACM,2004:109-117.

[7]Ji You,Sun Shiliang.Multitask multiclass support vector machines:model and experiments[J].Pattern Recognition, 2013,46(3):914-924.

[8]Zhang Zhihao,Zhou Jie.Multi-task clustering via domain adaptation[J].Pattern Recognition,2012,45(1):465-473.

[9]Xie Saining,Lu Hongtao,He Yangcheng.Multi-task coclustering via nonnegative matrix factorization[C]//Proceedings of the 21st International Conference on Pattern Recognition,Tsukuba,Japan,Nov 11-15,2012.Washington:IEEE Computer Society,2012:2954-2958.

[10]Kong Shu,Wang Donghui.A multi-task learning strategy for unsupervised clustering via explicitly separating the commonality[C]//Proceedings of the 21st International Conference on Pattern Recognition,Tsukuba,Japan,Nov 11-15, 2012.Washington:IEEE Computer Society,2012:771-774.

[11]Wang Hua,Nie Feiping,Huang Heng,et al.A new sparse multi-task regression and feature selection method to identify brain imaging predictors for memory performance[C]//Proceedings of the 2011 IEEE International Conference on Computer Vision,Barcelona,Spain,Nov 6-13,2011.Washington:IEEE Computer Society,2011:557-562.

[12]Solnon M,Arlot S,Bach F.Multi-task regression using minimal penalties[J].Journal of Machine Learning Research, 2011,13(3):2773-2812.

[13]Zhou Jiayu,Yuan Lei,Liu Jun,et al.A multi-task learning formulation for predicting disease progression[C]//Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,San Diego, USA,Aug 6-13,2011.New York:ACM,2011:814-822.

[14]Gong Pinghua,Ye Jieping,Zhang Changshui.Robust multi-task feature learning[C]//Proceedings of the 18th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Beijing,Aug 12-16,2012.New York:ACM,2012:895-903.

[15]Liang Yixiong,Liu Lingbo,Xu Ying,et al.Multi-task GLOH feature selection for human age estimation[C]//Proceedings of the 18th IEEE International Conference on Image Processing,Brussels,Belgium,Sep 11-14,2011.Washington:IEEE Computer Society,2011:565-568.

[16]Friedman J,Hastie T,Tibshirani R.Sparse inverse covariance estimation with the graphical lasso[J].Biostatistics, 2008,9(3):432-441.

[17]Chen Jianhui,Tang Lei,Liu Jun,et al.A convex formulation for learning a shared predictive structure from multiple tasks[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2013,35(5):1025-1038.

[18]Widmer C,Leiva J,Altun Y,et al.Leveraging sequence classification by taxonomy-based multitask learning[C]// LNCS 6044:Proceedings of the 14th Annual International Conference,Lisbon,Portugal,Apr 25-28,2010.Berlin,Heidelberg:Springer,2010:522-534.

[19]Luo Ping,Zhuang Fuzhen,Xiong Hui,et al.Transfer learning from multiple source domains via consensus regularization [C]//Proceedings of the 17th ACM Conference on Information and Knowledge Management,Napa Valley,USA,Oct 26-30,2008.New York:ACM,2008:103-112.

[20]Zhuang Fuzhen,Luo Ping,Xiong Hui,et al.Cross-domain learning from multiple sources:a consensus regularization perspective[J].IEEE Transactions on Knowledge and Data Engineering,2010,22(12):1664-1678.

[21]Jiang Yizhang,Chung F L,Ishibuchi H.Multi-task TSK fuzzy system modeling by mining inter-task common hidden structure[J].IEEE Transactions on Cybernetics,2015, 45(3):548-561.

[22]Zhang Minling.Research on multi-task learning[EB/OL]. (2011-08-10)[2016-01-30].http://www.paper.edu.cn/releasepaper/content/201108-156.

[23]Platt J C.Fast training of support vector machines using sequential minimal optimization[M]//Advances in Kernel Methods-Support Vector Learning.Cambridge,USA:MIT Press,1999: 185-208.

[24]Shi Yingzhong,Chung F L,Wang Shitong.An improved TA-SVM method without matrix inversion and its fast implementation for non-stationary datasets[J].IEEE Transactions on Neural Networks&Learning Systems,2015,25 (9):2005-2018.

[25]Tsang I W H,Kwok J T Y,Zurada J A.Generalized core vector machines generalized core vector[J].IEEE Transactions on Neural Networks Machines,2006,17(5):1126-1139.

[26]Qian Pengjiang,Wang Shitong,Deng Zhaohong,et al.Fast spectral clustering for large data sets using minimal enclosing ball[J].Acta Electronica Sinica,2010,38(9):2036-2041.

[27]Qian Pengjiang,Chung F L,Wang Shitong,et al.Fast graphbased relaxed clustering for large data sets using minimal enclosing ball[J].IEEE Transactions on Systems Man& Cybernetics:Part B Cybernetics,2012,42(3):672-687.

[28]Kumar P,Mitchell J S B,Yildirim E A.Approximate minimum enclosing balls in high dimensions using core-sets[J]. Journal of ExperimentalAlgorithmics,2003,8:1-29.

附中文參考文獻(xiàn)：

[22]張敏靈.多任務(wù)學(xué)習(xí)的研究[EB/OL].(2011-08-10)[2016-01-30].http://www.paper.edu.cn/releasepaper/content/201108-156.

[26]錢鵬江,王士同,鄧趙紅,等.基于最小包含球的大數(shù)據(jù)集快速譜聚類算法[J].電子學(xué)報，2010,38(9):2036-2041.

SHI Yingzhong was born in 1970.He is a Ph.D.candidate at School of Digital Media,Jiangnan University,associate professor at Wuxi Institute of Technology,and the member of CCF.His research interests include artificial intelligence,pattern recognition,intelligent modeling methods and their applications.

史熒中（1970—），男，江南大學(xué)數(shù)字媒體學(xué)院博士研究生，無錫職業(yè)技術(shù)學(xué)院副教授，CCF會員，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識別，智能建模及其應(yīng)用。

WANG Juqin was born in 1982.She is an M.S.candidate at Department of Computer Science,Jiangnan University, and lecturer at Wuxi Institute of Technology.Her research interests include intelligent modeling methods and their applications.

汪菊琴（1982—），女，江蘇吳江人，江南大學(xué)計算機(jī)系碩士研究生，無錫職業(yè)技術(shù)學(xué)院講師，主要研究領(lǐng)域?yàn)橹悄芙＜捌鋺?yīng)用。

XU Min was born in 1981.She is a post-doctor researcher at School of Digital Media,Jiangnan University.Her research interests include artificial intelligence,pattern recognition and their applications.

許敏（1981—），女，江蘇無錫人，江南大學(xué)數(shù)字媒體學(xué)院博士后，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識別及其應(yīng)用。

WANG Shitong was born in 1964.He is a professor at School of Digital Media,Jiangnan University.His research interests include artificial intelligence,pattern recognition and bioinformatics.

王士同（1964—），男，江蘇揚(yáng)州人，江南大學(xué)數(shù)字媒體學(xué)院教授，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識別，生物信息。

FastAlgorithm for Regularized Multi-Task Learning*

SHI Yingzhong1,2+,WANG Juqin1,2,XU Min1,WANG Shitong1
1.School of Digital Media,Jiangnan University,Wuxi,Jiangsu 214122,China
2.College of Internet of Things,Wuxi Institute of Technology,Wuxi,Jiangsu 214121,China
+Corresponding author:E-mail:shiyz@wxit.edu.cn

Regularized multi-task learning(rMTL)method and its extensions have achieved remarkable achievement in theoretical research and applications.However,previous research focuses on the relationship of tasks instead of the complexity of algorithms,the high computational cost of these methods are impractical for large scale datasets.In order to overcome this shortcoming,this paper proposes a fast regularized multi-task learning(FrMTL) based on core vector machine(CVM)theory.FrMTL is competitive with rMTL in classification accuracy while FrMTLCVM can make a decision rapidly for large scale datasets because of the merit of asymptotic linear time complexity. The effectiveness of the proposed classifier is also experimentally confirmed.

multi-task learning;large scale dataset;core vector machine;fast classification

2016-03,Accepted 2016-06.

A

TP391

*The National Natural Science Foundation of China under Grant No.61170122(國家自然科學(xué)基金面上項(xiàng)目);the New Century Excellent Talents Foundation from Ministry of Education of China under Grant No.NCET-120882(教育部新世紀(jì)優(yōu)秀人才支持計劃); the Top-Notch Academic Program of Jiangsu Higher Education Institutions under Grant No.PPZY2015C240(江蘇省高校品牌專業(yè)建設(shè)工程資助項(xiàng)目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2016-06-23,http://www.cnki.net/kcms/detail/11.5602.TP.20160623.1401.016.html