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

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

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

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

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

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

2.無(wú)錫職業(yè)技術(shù)學(xué)院 物聯(lián)網(wǎng)學(xué)院，江蘇 無(wú)錫 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)注于多個(gè)任務(wù)之間的關(guān)聯(lián)，而未充分考慮算法的復(fù)雜度，較高的計(jì)算代價(jià)限制了其在大數(shù)據(jù)集上的實(shí)用性。針對(duì)此不足，結(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ù)姆诸?lèi)性能，而基于CVM理論的FrMTL-CVM算法的漸近線(xiàn)性時(shí)間復(fù)雜度又能使其在面對(duì)大數(shù)據(jù)集時(shí)仍然能夠獲得較快的決策速度。該方法的有效性在實(shí)驗(yàn)中得到了驗(yàn)證。

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

1 引言

近期的研究[1-6]表明，較之于單獨(dú)學(xué)習(xí)各個(gè)子任務(wù)，對(duì)多個(gè)相關(guān)子任務(wù)同時(shí)學(xué)習(xí)能有效地提升預(yù)測(cè)性能。事實(shí)上，當(dāng)同時(shí)學(xué)習(xí)多個(gè)復(fù)雜的任務(wù)時(shí)，從其他任務(wù)中獲取的信號(hào)能作為非常有益的歸納信息[1-2]。學(xué)者們從多任務(wù)分類(lèi)[2-7]、聚類(lèi)[8-10]、回歸[11-13]、特征選擇[14-15]等方面展開(kāi)了研究，并在網(wǎng)頁(yè)標(biāo)注、人臉識(shí)別、年齡估計(jì)、語(yǔ)音與圖像處理、疾病預(yù)測(cè)、生物醫(yī)學(xué)等[16-18]多個(gè)應(yīng)用領(lǐng)域都取得了豐富的成果。一致性原理[19-20]又對(duì)此現(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]方法，其核心思想是多個(gè)子任務(wù)呈團(tuán)狀分布，共享同一個(gè)中心。隨后，學(xué)者們從實(shí)踐應(yīng)用的角度出發(fā)，研究了在應(yīng)用領(lǐng)域特別是生物醫(yī)學(xué)方面，當(dāng)子任務(wù)之間呈現(xiàn)出較清晰的圖狀關(guān)聯(lián)和樹(shù)狀關(guān)聯(lián)時(shí)的多任務(wù)學(xué)習(xí)方法。Friedman等人依據(jù)實(shí)際應(yīng)用中蛋白質(zhì)組之間存在特定的圖狀結(jié)構(gòu)，對(duì)蛋白質(zhì)組的信號(hào)進(jìn)行了分析[16]。Chen等人基于子任務(wù)之間的圖結(jié)構(gòu)，進(jìn)行了果蠅基因表示圖的自動(dòng)標(biāo)記[17]。Widmer等人利用了生物之間特定的樹(shù)狀及圖狀關(guān)聯(lián)進(jìn)行了真核生物的生物序列分析[18]。也有學(xué)者將多任務(wù)學(xué)習(xí)方法推廣到其他方面，如多類(lèi)多任務(wù)學(xué)習(xí)方法[7]等。其中，rMTL方法以其模型的簡(jiǎn)潔性而成為多任務(wù)學(xué)習(xí)理論研究的基礎(chǔ)，并擴(kuò)展出許多其他方法。

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

（2）FrMTL方法可依據(jù)CVM理論[25]設(shè)計(jì)出快速算法FrMTL-CVM，以應(yīng)對(duì)多任務(wù)大數(shù)據(jù)集問(wèn)題，其漸近時(shí)間復(fù)雜度與樣本總?cè)萘縩呈近線(xiàn)性關(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個(gè)學(xué)習(xí)任務(wù)，每個(gè)任務(wù)中的樣本點(diǎn)取自于空間X×Y，X??d,Y??。每個(gè)任務(wù)中包含m個(gè)樣本點(diǎn){(x1t,y1t),(x2t,y2t),…,(xmt,ymt)}，其概率分布Pt是不同的。多任務(wù)學(xué)習(xí)的核心思想是同時(shí)求解T個(gè)任務(wù)，利用其他相關(guān)任務(wù)中的有效信息來(lái)提高學(xué)習(xí)所得模型的泛化能力。

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

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

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

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

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

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

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

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

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

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

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

通過(guò)推導(dǎo)，不難得到式（5）的對(duì)偶問(wèn)題如下：

其中：

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

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

4.1 核心向量機(jī)

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

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

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

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

4.2 FrMTL-CVM算法描述

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

可以將式（6）等價(jià)地改寫(xiě)如下：

這是一個(gè)MEB問(wèn)題，其中Δ=-diag(H)+η1，通過(guò)調(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）對(duì)新的CCMEB進(jìn)行求解，得到新的球心ct+1和半徑Rt+1，權(quán)重系數(shù)α；計(jì)算新的球心到其他各點(diǎn)的距離；t=t+1，轉(zhuǎn)（2）。

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

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

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

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

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

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

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

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

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

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

實(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)的各個(gè)算法名，并列出了相關(guān)算法中的主要參數(shù)。表1中的參數(shù)ε僅指CVM算法中的近似程度，而求解二次規(guī)劃問(wèn)題時(shí)的精度參數(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ù)集上展開(kāi)實(shí)驗(yàn)。模擬數(shù)據(jù)集以數(shù)據(jù)集DS0為基礎(chǔ)來(lái)生成，DS0包含3個(gè)子任務(wù)，共300個(gè)樣本點(diǎn)，每個(gè)子任務(wù)正負(fù)類(lèi)樣本均為50。其中子任務(wù)T1的正類(lèi)中心(0,0)，方差為1，負(fù)類(lèi)中心(2.5, 0)，方差為1；子任務(wù)T2的正類(lèi)中心(0,0)，方差為1，負(fù)類(lèi)中心(2.5,0)，方差為1；子任務(wù)T3的正類(lèi)中心(0, 0)，方差為1.1，負(fù)類(lèi)中心(2.5,0)，方差為1.1。模擬數(shù)據(jù)集基于DS0生成，由DS0中的子任務(wù)經(jīng)過(guò)不同程度的旋轉(zhuǎn)、平移來(lái)模擬子任務(wù)之間不同的相關(guān)性。數(shù)據(jù)集DS1中的Task1直接采用DS0中的T1，Task2為T(mén)2進(jìn)行一定的旋轉(zhuǎn)（Rotate=5°）而生成，Task3為T(mén)3進(jìn)行一定的平移（Move=0.05）而生成。DS2~DS6中的子任務(wù)Task1都取為DS0中的T1，Task2、Task3則由DS0中的T2加大旋轉(zhuǎn)量，T3增加平移量而生成。模擬數(shù)據(jù)集DS1~DS6，以及用于評(píng)估算法時(shí)間性能的數(shù)據(jù)集DS7的具體描述如表2所示。

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

為了客觀地評(píng)估各種方法的分類(lèi)性能，在每個(gè)數(shù)據(jù)集上，本文除訓(xùn)練樣本外，還獨(dú)立生成了相同分布的測(cè)試樣本。訓(xùn)練樣本和測(cè)試樣本各有10組，共進(jìn)行10次重復(fù)實(shí)驗(yàn)，以盡量減少因模擬數(shù)據(jù)的隨機(jī)性而帶來(lái)的不客觀性。實(shí)驗(yàn)分為兩個(gè)階段：第一階段是針對(duì)訓(xùn)練樣本，優(yōu)化各方法的系統(tǒng)參數(shù)；第二階段是根據(jù)前一階段得到的參數(shù)設(shè)置對(duì)訓(xùn)練樣本建模，使用測(cè)試樣本來(lái)評(píng)估各方法的分類(lèi)性能。優(yōu)化系統(tǒng)參數(shù)時(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方法的分類(lèi)能力

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

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

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

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

（2）對(duì)比表3中的rMTL方法和FrMTL方法及其快速算法FrMTL-CVM，在6個(gè)數(shù)據(jù)集的共18個(gè)子任務(wù)的求解中，rMTL方法在7個(gè)子任務(wù)的求解中取得了較好的效果，F(xiàn)rMTL方法在10次子任務(wù)的求解中取得了較好的效果，而快速算法FrMTL-CVM在求解3個(gè)子任務(wù)時(shí)有較好的效果。因而FrMTL方法的分類(lèi)能力與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方法的分類(lèi)性能緩慢下降，但仍然優(yōu)于采用SVM方法單獨(dú)求解各子任務(wù)。另外，當(dāng)子任務(wù)之間關(guān)聯(lián)較強(qiáng)時(shí)，rMTL方法和FrMTL方法的分類(lèi)性能完全相當(dāng)，而當(dāng)子任務(wù)之間關(guān)聯(lián)較弱時(shí)，這兩個(gè)方法的分類(lèi)能力仍然是相當(dāng)?shù)?。快速算法FrMTLCVM的分類(lèi)能力與rMTL方法及FrMTL方法總體上是相當(dāng)?shù)摹?/p>

5.3 FrMTL方法的時(shí)間性能

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

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

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

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

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

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

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

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

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

6 結(jié)束語(yǔ)

本文提出了面向多任務(wù)學(xué)習(xí)的快速正則化多任務(wù)學(xué)習(xí)方法FrMTL。由于借鑒了rMTL方法及ITASVM方法中共享矢量的思想及兼顧局部?jī)?yōu)化和全局優(yōu)化的優(yōu)點(diǎn)，F(xiàn)rMTL方法的分類(lèi)性能與rMTL方法是等價(jià)的。而FrMTL-CVM方法良好的時(shí)間性能使面對(duì)多任務(wù)大數(shù)據(jù)集時(shí)仍能獲得相對(duì)較快的決策速度。當(dāng)然FrMTL方法仍需要進(jìn)一步研究以適應(yīng)更多的應(yīng)用場(chǎng)景，特別是當(dāng)多個(gè)子任務(wù)呈網(wǎng)狀分布或樹(shù)狀分布時(shí)，如何解決此類(lèi)更復(fù)雜耦合關(guān)系帶來(lái)的矩陣求逆問(wè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]錢(qián)鵬江,王士同,鄧趙紅,等.基于最小包含球的大數(shù)據(jù)集快速譜聚類(lèi)算法[J].電子學(xué)報(bào)，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é)院博士研究生，無(wú)錫職業(yè)技術(shù)學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識(shí)別，智能建模及其應(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ì)算機(jī)系碩士研究生，無(wú)錫職業(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—），女，江蘇無(wú)錫人，江南大學(xué)數(shù)字媒體學(xué)院博士后，主要研究領(lǐng)域?yàn)槿斯ぶ悄?，模式識(shí)別及其應(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)槿斯ぶ悄?，模式識(shí)別，生物信息。

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(國(guó)家自然科學(xué)基金面上項(xiàng)目);the New Century Excellent Talents Foundation from Ministry of Education of China under Grant No.NCET-120882(教育部新世紀(jì)優(yōu)秀人才支持計(jì)劃); the Top-Notch Academic Program of Jiangsu Higher Education Institutions under Grant No.PPZY2015C240(江蘇省高校品牌專(zhuān)業(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