李 嬋， 楊文元， 趙 紅

(閩南師范大學(xué) 粒計(jì)算重點(diǎn)實(shí)驗(yàn)室 福建 漳州 363000)

DOI: 10.13705/j.issn.1671-6841.2017081

基于最小二乘法的標(biāo)記分布學(xué)習(xí)

李 嬋， 楊文元， 趙 紅

(閩南師范大學(xué) 粒計(jì)算重點(diǎn)實(shí)驗(yàn)室 福建 漳州 363000)

多標(biāo)記學(xué)習(xí)在一定程度上解決了標(biāo)記多義性問(wèn)題，它主要關(guān)注實(shí)例對(duì)應(yīng)的相關(guān)標(biāo)記或者無(wú)關(guān)標(biāo)記，而標(biāo)記分布能夠反映相關(guān)標(biāo)記對(duì)于實(shí)例的重要程度．從重構(gòu)標(biāo)記分布的思想出發(fā)，利用最小二乘法建立模型，提出基于最小二乘法的標(biāo)記分布學(xué)習(xí)(lsm-LDL)．首先用特征重構(gòu)標(biāo)記，通過(guò)變換矩陣使得每一個(gè)標(biāo)記能夠表示為特征的一個(gè)線性組合；然后用最小二乘法建立優(yōu)化模型；最后引入L2范數(shù)規(guī)則化項(xiàng)，防止過(guò)擬合，保證泛化能力．在4個(gè)實(shí)際的數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并與3種已有的標(biāo)記分布學(xué)習(xí)算法在5種評(píng)價(jià)指標(biāo)上進(jìn)行比較，實(shí)驗(yàn)結(jié)果表明提出的lsm-LDL算法是有效的．

標(biāo)記分布； 最小二乘； 規(guī)則化項(xiàng)； L2范數(shù)

DOI: 10.13705/j.issn.1671-6841.2017081

0 引言

在機(jī)器學(xué)習(xí)中，雖然多標(biāo)記學(xué)習(xí)已經(jīng)能處理很多標(biāo)記模糊問(wèn)題[1]．但現(xiàn)實(shí)中有著更多的關(guān)于每個(gè)標(biāo)記對(duì)實(shí)例準(zhǔn)確描述度的數(shù)據(jù). 例如，人臉年齡估計(jì)[2]、圖像識(shí)別問(wèn)題[3]以及基因在不同時(shí)間點(diǎn)上的表達(dá)水平[4]，這些數(shù)據(jù)并不是多標(biāo)記學(xué)習(xí)能夠完善處理的．為了準(zhǔn)確地反映每個(gè)標(biāo)記對(duì)實(shí)例的描述程度，文獻(xiàn)[4]提出了針對(duì)標(biāo)記分布的學(xué)習(xí)算法和學(xué)習(xí)范式．圖1為包含天空、水、建筑和云的多標(biāo)記自然場(chǎng)景圖像[5]，如圖2中表示一個(gè)概率分布的數(shù)據(jù)形式即為標(biāo)記分布.

圖1 包含天空、水、建筑和云的多標(biāo)記自然場(chǎng)景圖像Fig.1 A multiple labels natural scene image which has been annotated with sky, water, building and cloud

圖2 自然場(chǎng)景圖像相應(yīng)的標(biāo)記分布圖像Fig.2 Label distribution of the natural scene image

標(biāo)記分布學(xué)習(xí)是一種新型學(xué)習(xí)范式，近幾年來(lái)成為機(jī)器學(xué)習(xí)中的熱點(diǎn)研究問(wèn)題之一[6-10]．最初研究者們基于標(biāo)記分布的思想設(shè)計(jì)了相應(yīng)的IIS-LLD算法和CPNN算法[6]．這兩種算法由于在訓(xùn)練過(guò)程中能夠利用更多的樣本信息，因此取得了更好的效果．文獻(xiàn)[7]提出完整的標(biāo)記分布學(xué)習(xí)框架，該框架不僅形式化地定義了標(biāo)記分布學(xué)習(xí)，而且設(shè)計(jì)了標(biāo)記分布學(xué)習(xí)算法，還給出了衡量標(biāo)記分布學(xué)習(xí)算法性能的指標(biāo)．

根據(jù)算法設(shè)計(jì)策略的不同，標(biāo)記分布學(xué)習(xí)分為問(wèn)題轉(zhuǎn)換法、算法適應(yīng)法和專門(mén)的算法三種[7]，問(wèn)題轉(zhuǎn)換法是指將標(biāo)記分布學(xué)習(xí)轉(zhuǎn)換為多實(shí)例學(xué)習(xí)或者多實(shí)例多標(biāo)記學(xué)習(xí)，例如PT-Bayes算法和PT-SVM算法．算法

適應(yīng)法是指自然擴(kuò)展某些已有的有標(biāo)記學(xué)習(xí)算法，使擴(kuò)展后的算法能夠處理標(biāo)記分布問(wèn)題，例如AA-KNN算法和AA-BP算法．專門(mén)的算法是指直接通過(guò)條件概率或者邏輯回歸等概率思想建立模型，例如SA-IIS算法和LDLogitBoost算法[11]．相對(duì)于問(wèn)題轉(zhuǎn)換和算法適應(yīng)，標(biāo)記分布學(xué)習(xí)中的專門(mén)算法在實(shí)際應(yīng)用中有更好的表現(xiàn)．目前，標(biāo)記分布學(xué)習(xí)中的專門(mén)算法主要是通過(guò)KL散度(kullback-leibler divergence)建立參數(shù)模型[3-4]，并利用最大熵[12]和邏輯回歸[13]等不同模型為參數(shù)模型進(jìn)行推導(dǎo)，這個(gè)過(guò)程在某種程度上忽略了特征與標(biāo)記之間的函數(shù)關(guān)系．

針對(duì)標(biāo)記分布的特性，利用最小二乘法建立標(biāo)記分布學(xué)習(xí)模型[14-15]．最小二乘法是通過(guò)最小化誤差的平方和尋找數(shù)據(jù)的最佳函數(shù)匹配[16-19]．針對(duì)標(biāo)記分布學(xué)習(xí)中標(biāo)記的特點(diǎn)，并受最小二乘法的啟發(fā)，本文提出了基于最小二乘的標(biāo)記分布學(xué)習(xí)方法(lsm-LDL)．首先用特征信息通過(guò)線性重構(gòu)的方式重構(gòu)標(biāo)記分布，以重構(gòu)標(biāo)記與原始標(biāo)記的最小誤差建立模型；然后引入最小二乘法，通過(guò)最小化誤差的平方和優(yōu)化模型；最后為了防止訓(xùn)練過(guò)程中的過(guò)擬合問(wèn)題，并考慮到稀疏解還能夠有效地減小噪聲的影響[20-21]，所以聯(lián)合L2范數(shù)正則化項(xiàng)求解重構(gòu)矩陣，從而得到預(yù)測(cè)標(biāo)記分布．為了驗(yàn)證提出算法的有效性，分別在4個(gè)公開(kāi)數(shù)據(jù)集上進(jìn)行算法效果評(píng)估實(shí)驗(yàn)，結(jié)果表明提出的標(biāo)記分布學(xué)習(xí)算法具有較好的效果．

1 相關(guān)工作

標(biāo)記分布學(xué)習(xí)算法使用KL散度作為概率分布之間的距離標(biāo)準(zhǔn)進(jìn)行建模，建立優(yōu)化模型[7]

其中：p(y/x;θ)是參數(shù)模型；θ是參數(shù)向量數(shù)；θ*是最優(yōu)參數(shù)向量.通過(guò)最大熵模型或邏輯回歸模型輸出標(biāo)記分布[6，8]，現(xiàn)有多種基于式(1)的標(biāo)記分布學(xué)習(xí)算法[3，4，6]，這些算法通過(guò)條件概率建立參數(shù)模型，利用現(xiàn)有的模型作為參數(shù)模型求解參數(shù)．但這些方法沒(méi)有從函數(shù)的角度考慮特征與標(biāo)記間的緊密關(guān)聯(lián)．

2 基于最小二乘的標(biāo)記分布學(xué)習(xí)算法

其中：T=[tjk]∈Rm×c是特征對(duì)標(biāo)記的重構(gòu)矩陣；tjk表示第j個(gè)特征對(duì)第k個(gè)標(biāo)記的重構(gòu)系數(shù)．

對(duì)于給定的數(shù)據(jù)集S，其中X的維度ngt;m.顯然，對(duì)于式(2)，一般情況下是無(wú)解的[21].所以引入最小二乘法，為了選取最合適的T，基于最小二乘式(3)中引入殘差平方和函數(shù)L

其中γ為規(guī)則化項(xiàng)參數(shù)．式(5)中L2范數(shù)可通過(guò)導(dǎo)數(shù)求解[25]．將函數(shù)L(T)對(duì)T求導(dǎo)并令其為零，有

由式(6)可得

基于上述分析，提出的lsm-LDL算法具體步驟如下：

輸入： 規(guī)則化參數(shù)D″，訓(xùn)練集D.輸出： 測(cè)試集的預(yù)測(cè)標(biāo)記分布D″.

步驟1： 通過(guò)式(7)計(jì)算T.步驟2： 用D′=X′T計(jì)算預(yù)測(cè)標(biāo)記.步驟3： 計(jì)算式(8)，有歸一化標(biāo)記分布D″.

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

通過(guò)實(shí)驗(yàn)驗(yàn)證提出的基于最小二乘的標(biāo)記分布學(xué)習(xí)(lsm-LDL)算法，相對(duì)于其他的對(duì)比算法具有更好的實(shí)驗(yàn)效果．利用評(píng)價(jià)標(biāo)記分布間的相似性或者距離的評(píng)價(jià)方式，作為標(biāo)記分布的評(píng)價(jià)指標(biāo)[5]．文獻(xiàn)[26]中提出8個(gè)不同族的41種評(píng)價(jià)方法，都能用于這樣的評(píng)價(jià)．用凝聚單聯(lián)動(dòng)與平均聚類方法建立關(guān)系值[27]，根據(jù)文獻(xiàn)[6]提出的篩選規(guī)則及實(shí)驗(yàn)條件選出5種評(píng)價(jià)方法．分別是切比雪夫距離(Cheb)、克拉克距離(Clark)、堪培拉量度(Canber)、余弦系數(shù)(Cosine)以及交叉相似性(Intersec)．具體的評(píng)價(jià)方法的計(jì)算公式如表1所示．前3個(gè)指標(biāo)是距離指標(biāo)，值越小表示效果越好,后2個(gè)指標(biāo)是相似指標(biāo)，值越大表示算法效果越好．

表1 5種評(píng)價(jià)指標(biāo)的名稱、公式 Tab.1 Name and formula of five evaluation indexes

表2 實(shí)驗(yàn)數(shù)據(jù)集描述

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

實(shí)驗(yàn)過(guò)程，用4個(gè)公開(kāi)數(shù)據(jù)(http://cse.seu.edu.cn/PersonalPage/xgeng/LDL/index.htm)進(jìn)行實(shí)驗(yàn)：分別是數(shù)據(jù)集Yeast-alpha、Yeast-cold、Human Gene和Moive．lsm-LDL算法的平衡參數(shù)設(shè)置為{103,102,101,1,10-1,10-2,10-3}，記錄算法最好的結(jié)果所對(duì)應(yīng)的參數(shù)，以最佳參數(shù)作為下文參數(shù)的取值[23]．上述4個(gè)數(shù)據(jù)集的簡(jiǎn)要信息及對(duì)應(yīng)的最好結(jié)果的參數(shù)值，如表2所示．

實(shí)驗(yàn)采用十折交叉驗(yàn)證進(jìn)行，測(cè)試結(jié)果用3種距離和2種相似指標(biāo)進(jìn)行評(píng)價(jià)，最終結(jié)果為測(cè)試集標(biāo)記分布的均值．與3種現(xiàn)有經(jīng)典標(biāo)記分布學(xué)習(xí)算法在公開(kāi)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)．對(duì)比算法[6]分別是問(wèn)題轉(zhuǎn)換算法PT-Bayes、算法適應(yīng)算法AA-kNN和專門(mén)的算法IIS-LDL.

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

表3～6分別列出在4個(gè)不同數(shù)據(jù)集上，每種算法在不同評(píng)價(jià)指標(biāo)的衡量下的值．表中的值用粗體表示最優(yōu)結(jié)果，下劃線表示次優(yōu)結(jié)果．

表3列出數(shù)據(jù)集Yeast-alpha在5種不同指標(biāo)下對(duì)應(yīng)的4種算法的表現(xiàn)，從表中可看到提出的lsm-LDL算法在該數(shù)據(jù)集上明顯比其他3種對(duì)比算法有更好的結(jié)果．另外，算法AA-kNN在該數(shù)據(jù)集上也有較好的結(jié)果．表4和表5列出不同算法在數(shù)據(jù)集Yeast-cold和數(shù)據(jù)集Movie上對(duì)應(yīng)5種不同指標(biāo)的結(jié)果，從表中可以看到提出的lsm-LDL算法在該數(shù)據(jù)集上明顯比其他3種對(duì)比算法有更好的結(jié)果．在這兩個(gè)數(shù)據(jù)集上仍然是AA-kNN算法有第二好的結(jié)果，同時(shí)可看到IIS-LDL算法在這2個(gè)數(shù)據(jù)集上有個(gè)別指標(biāo)具有第二好的結(jié)果．表6列出各個(gè)算法在數(shù)據(jù)集Human Gene上不同指標(biāo)對(duì)應(yīng)的結(jié)果，lsm-LDL算法在該數(shù)據(jù)集上仍然明顯比其他3種對(duì)比算法有更好的結(jié)果．另外，IIS-LDL算法在該數(shù)據(jù)集上的結(jié)果僅次于我們提出的lsm-LDL算法．

綜上所述，從表3到表6可以看出，提出的lsm-LDL算法不僅在5種評(píng)價(jià)指標(biāo)下都有較好的效果，而且在各個(gè)數(shù)據(jù)集上都能夠保持較好的性能，相對(duì)于其他3種算法有更強(qiáng)的適應(yīng)性和穩(wěn)定性．我們提出的算法比傳統(tǒng)的概率模型不僅求解快速，而且具有更強(qiáng)的適應(yīng)能力和更好的穩(wěn)定性．

表3 數(shù)據(jù)集Yeast-alpha的實(shí)驗(yàn)結(jié)果

表4 數(shù)據(jù)集Yeast-cold的實(shí)驗(yàn)結(jié)果

表5 數(shù)據(jù)集Moive的實(shí)驗(yàn)結(jié)果

表6 數(shù)據(jù)集Human Gene的實(shí)驗(yàn)結(jié)果

圖3呈現(xiàn)不同算法學(xué)習(xí)得來(lái)的某一實(shí)例的預(yù)測(cè)標(biāo)記分布和原始標(biāo)記分布的趨勢(shì)．縱坐標(biāo)代表標(biāo)記分布，橫坐標(biāo)表示標(biāo)記數(shù)．其中圖(a)、(b)和(c)分別表示數(shù)據(jù)集Yeast-alpha、Yeast-cold和Moive的測(cè)試集中的最中間一個(gè)實(shí)例的標(biāo)記分布圖，每個(gè)圖中包括原始標(biāo)記分布，以及4種算法學(xué)習(xí)獲得的預(yù)測(cè)標(biāo)記分布，分別用不同的折線表示．由于數(shù)據(jù)集Human Gene標(biāo)記較多，所以將標(biāo)記分為3部分，由圖(d)、(e)和(f)共同表示數(shù)據(jù)集Human Gene的測(cè)試集中的最中間一個(gè)實(shí)例的標(biāo)記分布．從圖3中可以看出lsm-LDL算法獲得的標(biāo)記分布與原始標(biāo)記分布較為接近，說(shuō)明lsm-LDL算法在這4個(gè)數(shù)據(jù)集上相對(duì)于對(duì)比算法有更好的效果．

圖3 不同標(biāo)記分布學(xué)習(xí)算法預(yù)測(cè)的標(biāo)記分布及原始標(biāo)記分布Fig.3 Label distribution of different label distribution learning algorithms and original label distribution

綜合表3～表6和圖3的分析，提出的算法相較于其他3種對(duì)比算法能夠得到更加接近于原始標(biāo)記分布的預(yù)測(cè)標(biāo)記分布，并且在3種距離評(píng)價(jià)指標(biāo)和2種相似評(píng)價(jià)指標(biāo)上都有較好的表現(xiàn)．

4 總結(jié)

標(biāo)記分布學(xué)習(xí)不僅能夠處理一個(gè)示例有多個(gè)標(biāo)記的問(wèn)題，而且還能得到各個(gè)標(biāo)記對(duì)示例的重要程度．文中提出的lsm-LDL算法，根據(jù)訓(xùn)練集的原始標(biāo)記分布與通過(guò)線性重構(gòu)的預(yù)測(cè)標(biāo)記分布之間最小誤差建立模型，利用最小二乘法并聯(lián)系規(guī)則化項(xiàng)L2范數(shù)優(yōu)化求解．通過(guò)訓(xùn)練集學(xué)習(xí)獲得一個(gè)重構(gòu)矩陣，重構(gòu)矩陣和測(cè)試集特征數(shù)據(jù)以矩陣相乘的方式重構(gòu)測(cè)試集標(biāo)記分布，從而獲得測(cè)試集的預(yù)測(cè)標(biāo)記．lsm-LDL算法在4個(gè)公開(kāi)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，比較于傳統(tǒng)的概率模型，不僅求解過(guò)程速度快，而且具有更強(qiáng)的適應(yīng)能力和更好的穩(wěn)定性．

[1] WANG J, YANG Y, MAO J, et al. CNN-RNN: a unified framework for multi-label image classification[C]//IEEE Computer Society, Proceeding of the IEEE Conference on Computer Vision and Pattern Recognition. Las Vegas, 2016:2285-2294.

[2] GENG X, ZHOU Z H, SMITH-MILES K. Automatic age estimation based on facial aging patterns[J]. IEEE transactions on pattern analysis and machine intelligence, 2007, 29(12): 2234-2240.

[3] ZHANG Z, WANG M, GENG X. Crowd counting in public video surveillance by label distribution learning[J]. Neuro computing, 2015, 166(C): 151-163.

[4] 季榮姿. 標(biāo)記分布學(xué)習(xí)及其應(yīng)用 [D]. 南京：東南大學(xué), 2014.

[5] LI Y K, ZHANG M L, GENG X. Leveraging implicit relative labeling-importance information for effective multi-label learning[C]//IEEE International Conference on Data Mining. Atlantic City, 2015，6(2): 251-260.

[6] GENG X, YIN C, ZHOU Z H. Facial age estimation by learning from label distributions[J]. IEEE transactions on pattern analysis and machine intelligence, 2013, 35(10): 2401-2412.

[7] GENG X. Label distribution learning[J]. IEEE transactions on knowledge and data engineering, 2016, 28(7): 1734-1748.

[8] BOUTELL M R, LUO J, SHEN X, et al. Learning multi-label scene classification[J]. Pattern recognition, 2004, 37(9): 1757-1771.

[9] ZHANG M L, ZHOU Z H. A review on multi-label learning algorithms[J]. IEEE transactions on knowledge and data engineering, 2014, 26(8): 1819-1837.

[10] MEERBERGEN K, ROOSE D. Matrix transformations for computing rightmost eigenvalues of large sparse non-symmetric eigenvalue problems[J]. IMA journal of numerical analysis, 1996, 16(3): 297-346.

[11] XING C, GENG X. Logistic boosting regression for label distribution learning[C]. IEEE International Conference on Computer Vision and Pattern Recognition. Las Vegas, 2016: 4489-4497.

[12] BERGER A, PIETRA V, PIETRA S. A maximum entropy approach to natural language processing[J]. Computational linguistics, 2002, 22(1): 39-71.

[13] COLLINS M, SCHAPIRE R E, SINGER Y. Logistic regression, adaboost and bregman distances[J]. Machine learning, 2002, 48(1): 253-285.

[14] TSOUMAKAS G, KATAKIS I, DAVID T. Multi-label classification: an overview[J]. International journal of data warehousing amp; mining, 2007, 3(3): 1-13.

[15] RUST B W. Fitting nature′s basic functions part Ⅲ: exponentials, sinusoids, and nonlinear least squares[J]. Computing in science and engineering, 2002, 4(4): 72-77.

[16] 賈小勇, 徐傳勝, 白欣. 最小二乘法的創(chuàng)立及其思想方法[J]. 西北大學(xué)學(xué)報(bào) (自然科學(xué)版), 2006, 36(3): 507-511.

[17] 陸健. 最小二乘法及其應(yīng)用[J]. 中國(guó)西部科技, 2007(19): 19-21.

[18] SUYKENS J A K, GESTEL VT, BRABANTER J D. Least square support sector machine[J]. Euphytica, 2002, 2(2): 1599-1604.

[19] VAPNIK V. The nature of statistical learning theory [M]. New York: Springer Science and Business Media, 2013.

[20] NIE F, HUANG H, CAI X, et al. Efficient and robust feature selection via joint2, 1-norms minimization[C]∥Advances in Neural Information Processing Systems 23. Vancouver, 2010: 1813-1821.

[21] 脫倩娟, 趙紅. 基于局部鄰域嵌入的無(wú)監(jiān)督特征選擇[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2016, 48(3):57-62.

[22] 馬麗, 董唯光, 梁金平,等. 基于隨機(jī)投影的正交判別流形學(xué)習(xí)算法[J]. 鄭州大學(xué)學(xué)報(bào)(理學(xué)版), 2016, 48(1):102-109.

[23] ZHU P, ZUO W, ZHANG L,et al. Unsupervised feature selection by regularized self-representation[J]. Pattern recognition, 2015, 48(2): 438-446.

[24] 何秀麗. 多元線性模型與嶺回歸分析[D]. 武漢：華中科技大學(xué), 2005.

[25] YU S, FALCK T, DAEMEN A,et al. L2norm multiple kernel learning and its application to biomedical data fusion[J]. BMC bioinformatics, 2010, 11(1):1-24.

[26] CHA S H. Comprehensive survey on distance/similarity measures between probability density functions[J]. International journal of mathematical models and methods in applied sciences, 2007, 1(4): 300-307.

[27] DUDA R, HART P, STORK D. Pattern classification[M]. 2nd edition. The United States: John Wiley, 2000.

(責(zé)任編輯：方惠敏)

LabelDistributionLearningBasedonLeastSquareMethod

LI Chan, YANG Wenyuan, ZHAO Hong

(LabofGranularComputing,MinnanNormalUniversity,Zhangzhou363000,China)

The importance of the labels relative to the instance can be reflected by label distribution. Multi-label learning could solve ambiguity problems of label by focusing on the corresponding related or unrelated labels of the instance. The label distribution learning based on least square method (lsm-LDL) was proposed. Firstly, Some features were used to reconstruct the label, and then the transformation matrix was used to have each label expressed as a linear combination of features. Secondly, the least square method was applied to establish the optimization model. Finally, the L2norm regularization term was introduced to prevent overfitting, and to ensure the generalization ability. Experiments were carried out on four actual data sets, and the lsm-LDL algorithm was compared with three other existing labeled distribution learning algorithms with five evaluation indices. The results showed that the proposed lsm-LDL algorithm was effective.

label distribution learning; least square; regularization term; L2norm

2017-04-17

國(guó)家自然科學(xué)基金項(xiàng)目(61379049，61379089)；陜西省教育廳專項(xiàng)科研項(xiàng)目(16JK2015).

李嬋(1992—)，女，四川資陽(yáng)人，主要從事機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘研究，E-mail:lc_chanzi@163.com；通信作者：楊文元(1967—)，男，福建漳州人，副教授，主要從事機(jī)器學(xué)習(xí)、粒計(jì)算研究，E-mail:yangwy@xmu.edu.cn.

TP181

A

1671-6841(2017)04-0022-06