基于最小二乘法的標記分布學習

李 嬋， 楊文元， 趙 紅

(閩南師范大學 粒計算重點實驗室 福建 漳州 363000)

DOI: 10.13705/j.issn.1671-6841.2017081

基于最小二乘法的標記分布學習

李 嬋， 楊文元， 趙 紅

(閩南師范大學 粒計算重點實驗室 福建 漳州 363000)

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

標記分布； 最小二乘； 規則化項； L2范數

DOI: 10.13705/j.issn.1671-6841.2017081

0 引言

在機器學習中，雖然多標記學習已經能處理很多標記模糊問題[1]．但現實中有著更多的關于每個標記對實例準確描述度的數據. 例如，人臉年齡估計[2]、圖像識別問題[3]以及基因在不同時間點上的表達水平[4]，這些數據并不是多標記學習能夠完善處理的．為了準確地反映每個標記對實例的描述程度，文獻[4]提出了針對標記分布的學習算法和學習范式．圖1為包含天空、水、建筑和云的多標記自然場景圖像[5]，如圖2中表示一個概率分布的數據形式即為標記分布.

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

圖2 自然場景圖像相應的標記分布圖像Fig.2 Label distribution of the natural scene image

標記分布學習是一種新型學習范式，近幾年來成為機器學習中的熱點研究問題之一[6-10]．最初研究者們基于標記分布的思想設計了相應的IIS-LLD算法和CPNN算法[6]．這兩種算法由于在訓練過程中能夠利用更多的樣本信息，因此取得了更好的效果．文獻[7]提出完整的標記分布學習框架，該框架不僅形式化地定義了標記分布學習，而且設計了標記分布學習算法，還給出了衡量標記分布學習算法性能的指標．

根據算法設計策略的不同，標記分布學習分為問題轉換法、算法適應法和專門的算法三種[7]，問題轉換法是指將標記分布學習轉換為多實例學習或者多實例多標記學習，例如PT-Bayes算法和PT-SVM算法．算法

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

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

1 相關工作

標記分布學習算法使用KL散度作為概率分布之間的距離標準進行建模，建立優化模型[7]

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

2 基于最小二乘的標記分布學習算法

其中：T=[tjk]∈Rm×c是特征對標記的重構矩陣；tjk表示第j個特征對第k個標記的重構系數．

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

其中γ為規則化項參數．式(5)中L2范數可通過導數求解[25]．將函數L(T)對T求導并令其為零，有

由式(6)可得

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

輸入： 規則化參數D″，訓練集D.輸出： 測試集的預測標記分布D″.

步驟1： 通過式(7)計算T.步驟2： 用D′=X′T計算預測標記.步驟3： 計算式(8)，有歸一化標記分布D″.

3 實驗與結果分析

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

表1 5種評價指標的名稱、公式 Tab.1 Name and formula of five evaluation indexes

表2 實驗數據集描述

3.1 實驗設置

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

實驗采用十折交叉驗證進行，測試結果用3種距離和2種相似指標進行評價，最終結果為測試集標記分布的均值．與3種現有經典標記分布學習算法在公開數據集上進行對比實驗．對比算法[6]分別是問題轉換算法PT-Bayes、算法適應算法AA-kNN和專門的算法IIS-LDL.

3.2 實驗結果分析

表3～6分別列出在4個不同數據集上，每種算法在不同評價指標的衡量下的值．表中的值用粗體表示最優結果，下劃線表示次優結果．

表3列出數據集Yeast-alpha在5種不同指標下對應的4種算法的表現，從表中可看到提出的lsm-LDL算法在該數據集上明顯比其他3種對比算法有更好的結果．另外，算法AA-kNN在該數據集上也有較好的結果．表4和表5列出不同算法在數據集Yeast-cold和數據集Movie上對應5種不同指標的結果，從表中可以看到提出的lsm-LDL算法在該數據集上明顯比其他3種對比算法有更好的結果．在這兩個數據集上仍然是AA-kNN算法有第二好的結果，同時可看到IIS-LDL算法在這2個數據集上有個別指標具有第二好的結果．表6列出各個算法在數據集Human Gene上不同指標對應的結果，lsm-LDL算法在該數據集上仍然明顯比其他3種對比算法有更好的結果．另外，IIS-LDL算法在該數據集上的結果僅次于我們提出的lsm-LDL算法．

綜上所述，從表3到表6可以看出，提出的lsm-LDL算法不僅在5種評價指標下都有較好的效果，而且在各個數據集上都能夠保持較好的性能，相對于其他3種算法有更強的適應性和穩定性．我們提出的算法比傳統的概率模型不僅求解快速，而且具有更強的適應能力和更好的穩定性．

表3 數據集Yeast-alpha的實驗結果

表4 數據集Yeast-cold的實驗結果

表5 數據集Moive的實驗結果

表6 數據集Human Gene的實驗結果

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

圖3 不同標記分布學習算法預測的標記分布及原始標記分布Fig.3 Label distribution of different label distribution learning algorithms and original label distribution

綜合表3～表6和圖3的分析，提出的算法相較于其他3種對比算法能夠得到更加接近于原始標記分布的預測標記分布，并且在3種距離評價指標和2種相似評價指標上都有較好的表現．

4 總結

標記分布學習不僅能夠處理一個示例有多個標記的問題，而且還能得到各個標記對示例的重要程度．文中提出的lsm-LDL算法，根據訓練集的原始標記分布與通過線性重構的預測標記分布之間最小誤差建立模型，利用最小二乘法并聯系規則化項L2范數優化求解．通過訓練集學習獲得一個重構矩陣，重構矩陣和測試集特征數據以矩陣相乘的方式重構測試集標記分布，從而獲得測試集的預測標記．lsm-LDL算法在4個公開數據集上進行實驗，比較于傳統的概率模型，不僅求解過程速度快，而且具有更強的適應能力和更好的穩定性．

[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] 季榮姿. 標記分布學習及其應用 [D]. 南京：東南大學, 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] 賈小勇, 徐傳勝, 白欣. 最小二乘法的創立及其思想方法[J]. 西北大學學報 (自然科學版), 2006, 36(3): 507-511.

[17] 陸健. 最小二乘法及其應用[J]. 中國西部科技, 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] 脫倩娟, 趙紅. 基于局部鄰域嵌入的無監督特征選擇[J]. 鄭州大學學報(理學版), 2016, 48(3):57-62.

[22] 馬麗, 董唯光, 梁金平,等. 基于隨機投影的正交判別流形學習算法[J]. 鄭州大學學報(理學版), 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]. 武漢：華中科技大學, 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.

(責任編輯：方惠敏)

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

國家自然科學基金項目(61379049，61379089)；陜西省教育廳專項科研項目(16JK2015).

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

TP181

A

1671-6841(2017)04-0022-06