基于局部標記相關性的標記分布學習算法

黃 俊，田佳洪

(1.安徽工業大學 計算機科學與技術學院，安徽 馬鞍山 243032； 2.合肥綜合性國家科學中心人工智能研究院，安徽 合肥 230088)

0 引 言

在機器學習[1]的研究中，標記多義性問題受到廣泛關注。單標記學習(single-label learning，SLL)和多標記學習(multi-label learning，MLL)[2,3]是解決此問題比較成熟的兩種機器學習范式。二者雖然能解決“示例可以被哪個/些標記描述”的問題，但是卻不能解決“每個標記可以在多大程度上描述示例”的問題。為了解決這一問題，Geng等[4]提出了標記分布學習(label distribution learning，LDL)。LDL在描述每一個示例時，給描述此示例的每個標記一個描述度，準確地表示出每個標記在示例的描述程度上的差異，強化了標注信息的能力。現有的LDL專用方法大多僅關注學習模型的設計，將模型建立在原始高維特征空間上，并且從全局的角度探索和利用標記相關性。這樣做只是簡單的讓所有特征被所有標記共享，忽略了實際分類學習任務中無關和冗余特征對算法性能的影響。并且，在現實世界的任務中，不同組示例間大多共享不同的標記相關性，很少有標記相關性能全局適用。因此本文提出一種基于局部標記相關性的標記分布學習算法(LDL-LLC)，給LDL模型同時引入特征選擇和局部標記相關性，試圖挖掘出每組局部訓練示例中的標記相關性，并學習每個標記的私有特征和所有標記的共享特征，最終達到提高LDL算法性能的目的。

1 相關知識介紹

1.1 標記分布學習

LDL的形式化表述如下。令X∈n×d為訓練數據特征空間，D∈n×c為訓練數據標記分布空間，LDL是通過建立的目標函數學得一個從X到D的映射，基于該映射可以預測未見示例的標記分布。xi∈X為第i個示例的特征向量，與其對應的為第i個示例的標記分布，其中為第j個標記對第i個示例的描述程度，且每個示例的描述程度總和

為了更好地標注出示例的標記分布，研究者們提出了許多LDL算法。目前，已有的LDL算法主要分為以下3類：①問題轉換方法：將LDL問題轉換為多個SLL問題，然后利用已有的SLL算法去處理這些SLL問題。這類算法包括PT-SVM和PT-Bayes算法[4]。②算法適應方法：直接修改已有SLL和MLL算法的一些約束條件，使其可以處理LDL問題。這類算法包括AA-kNN和AA-BP算法[4]。③專用方法：直接聚焦標記分布的預測問題，通常由輸出模型、目標函數和優化求解3部分組成。這類算法的典型代表包括SA-IIS[4]和CPNN算法[5]。

1.2 特征選擇

現有的LDL專用方法大多僅關注學習模型的設計，將模型直接建立在原始高維特征空間上，忽略了實際分類學習任務中無關和冗余特征的存在。當訓練數據特征空間維度較高時，示例的標注結果就可能會受到無關和冗余特征的影響而變差。

LSE-LDL算法[6]和LDLSF算法[7]是兩種將學習模型和特征選擇結合起來的算法。LSE-LDL算法為減少噪音特征的干擾，將具有鑒別性的特征編碼為潛在語義特征。同時，為了消除無關和冗余特征，對權重參數矩陣采用l2,1范數正則化約束來選擇一些與潛在語義特征空間最相關的原始特征。LDLSF算法利用l1和l2,1范數對權重參數進行正則化約束，來學習每個標記的私有特征和所有標記的共享特征。

1.3 局部標記相關性

現有的LDL算法大多從全局角度利用標記間的相關性[9]。然而，在現實世界的任務中，不同的示例大多共享不同的標記相關性，并且標記間的相關性很少能全局適用。GD-LDL-SCL算法[10]將訓練數據聚類為m組，并為每組示例設計一個局部相關向量作為每組數據的附加特征部分，在附加特征部分引入局部相關性信息。EDL-LRL算法[11]將訓練數據聚類為m組，并利用低秩結構去約束每組示例的預測標記分布矩陣，來捕獲局部標記相關性。LDL-LCLR算法[12]對聚類后的每組數據使用流形正則化器約束，來探索和利用局部標記相關性。

上述3種利用局部標記相關性的LDL算法，GD-LDL-SCL算法和EDL-LRL算法沒有將標記輸出和標記間的相關性緊密的聯系起來。LDL-LCLR算法雖然將標記相關性約束在標記輸出上，但聚類后的每組訓練數據仍使用統一的全局標記相關性矩陣作為度量。

2 基于局部標記相關性的標記分布學習算法

本文提出的基于局部標記相關性的標記分布學習算法(LDL-LLC)屬于解決LDL問題的專用方法。在第2節中，2.1將介紹LDL-LLC算法的輸出模型，2.2介紹目標函數，2.3介紹優化求解。

2.1 輸出模型

假設特征空間和標記分布空間是線性相關的，則輸出模型表示為

(1)

2.2 目標函數

LDL-LLC算法的目標函數由3部分組成：2.2.1損失函數、2.2.2共享和私有特征建模和2.2.3局部標記相關性建模。

2.2.1 損失函數

將損失函數定義為最小二乘損失函數形式，來度量預測標記分布和真實標記分布之間的差距。損失函數表示為

(2)

式中：D∈n×c是真實標記分布矩陣， 1c×1和1n×1為元素都是1的列向量， 0n×c∈n×c為元素都是0的矩陣。

2.2.2 共享和私有特征建模

對W采用l1范數正則化約束來增強W的稀疏性，以學習標記私有特征。同時，對W采用l2,1范數正則化約束來確保W的每一行是稀疏的，以學習所有標記的共享特征。為了避免兩種范數正則化對變量W進行約束時，會相互干擾，影響了特征選擇的效果。將W拆分為M和V兩個部分，一部分采用l1范數正則化進行約束，另一部分采用l2,1范數正則化進行約束。最后，將M和V的求和約束為W。 共享和私有特征建模表示為

(3)

式中：M∈d×c為選擇每個標記私有特征的權重參數矩陣，V∈d×c為選擇所有標記共享特征的權重參數矩陣。

2.2.3 局部標記相關性建模

現實世界的任務中，不同的示例大多共享不同的標記相關性，并且很少有標記相關性是全局適用的。假設訓練數據可以被劃分為m組 {G(1),G(2),…,G(m)}。 為了便于實現，使用k-means作為聚類方法，將訓練數據聚為m組。同一組示例共享相同的標記相關性，并引入局部流形正則化器將每組示例間的標記相關性直接約束在標記輸出上[13]。局部標記相關性建模表示為

(4)

(5)

式中：Lk=P(k)-R(k)∈c×c為第k組訓練數據的拉普拉斯矩陣，其中，R(k)∈c×c為第k組訓練數據的標記相關性矩陣，P(k)∈c×c為對角矩陣，對角線元素是R(k)×1c×1， 1nk×1∈nk×1為元素都是1的列向量， 0nk×c∈nk×c為元素都是0的矩陣。

(6)

2.2.4 目標函數總式

LDL-LLC算法的目標函數由損失函數L(W)、 共享和私有特征建模F(W) 和局部標記相關性建模R(W) 組成。表示如下

(7)

式中：λ1、λ2和λ3是平衡參數。

LDL-LLC算法的目標函數總式共有4項。第一項是損失函數，用來測量預測的標記分布和真實標記分布之間的距離；第二項用來學習每個標記的私有特征；第三項用來學習所有標記的共享特征；最后一項探索和利用了局部標記相關性。

2.3 優化求解

目標函數式(7)有多個變量，采用交替迭代的方法求解。每次迭代只更新一個變量，其它變量固定為它們每次迭代后的最新值。

2.3.1 更新變量Z

將將變量W,M,V固定，式(7)可簡化為m個優化問題，其中第k個問題表示為

(8)

利用MANOPT工具箱[13]對式(8)在歐幾里得空間上用線性搜索實現梯度下降求解，來對Zk進行更新。式(8)的梯度表示如下

(9)

(10)

2.3.2 更新變量W

將變量M,V,Z固定，通過增廣拉格朗日乘子法[7]構造出含有變量W的增廣拉格朗日函數，使得目標函數總式中含有變量W的約束條件轉換為無約束的形式。對于非負約束XW≥0n×c， 使用投影算子將XW中不滿足條件的元素轉換為0。轉換形式后，求解問題表示為

(11)

式中： 〈·,·〉 為兩個矩陣的點積， Γ1∈d×c和Γ2∈n×1為拉格朗日乘子，ρ>0為正項的懲罰標量。

使用有限內存擬牛頓法(L-BFGS)[14]對式(11)進行求解。L-BFGS的計算主要與一階梯度有關，式(11)一階梯度表示如下

(12)

2.3.3 更新變量M

將變量W,V,Z固定，通過增廣拉格朗日乘子法構造出含有變量M的增廣拉格朗日函數，使得目標函數總式中含有變量M的約束條件轉換為無約束的形式。求解問題表示為

(13)

式(13)可以改寫為

(14)

改寫后的式(14)有一個閉合解，可以直接進行求解。

2.3.4 更新變量V

將變量W,M,Z固定，通過增廣拉格朗日乘子法構造出含有變量V的增廣拉格朗日函數，使得目標函數總式中含有變量V的約束條件轉換為無約束的形式。求解問題表示為

(15)

式(15)可以改寫為

(16)

改寫后的式(16)有一個閉合解，可以直接進行求解。

2.3.5 更新乘子Γ1和Γ2

拉格朗日乘子Γ1和Γ2可以直接更新，更新公式表述如下

(17)

(18)

本文提出的LDL-LLC算法的總體過程見表1。

表1 LDL-LLC算法

3 實 驗

在7個LDL真實數據集上，使用6種評價指標將本文提出的LDL-LLC算法與6種現有LDL算法進行比較。

3.1 數據集

采用7個LDL真實數據集：S-JAFFE、S-BU_3DFE、Emotion6、M2B、SCUT-FBP、Natural Scene和Movie。其中，S-JAFFE、S-BU_3DFE和Emotion6是面部表情識別數據集，M2B和SCUT-FBP是面部美容評估數據集，Natural Scene是自然場景識別數據集，Movie是電影評級數據集。7個LDL真實數據集詳細信息見表2。

表2 實驗選用的標記分布數據集描述

前兩個數據集S-JAFFE和S-BU_3DFE是對兩種廣泛使用的面部表情圖像數據庫JAFFE和BU_3DFE的擴展。S-JAFFE包含213張特征維度為243的表情灰度圖。60個人根據6種基本情緒標記(即：快樂、悲傷、驚訝、恐懼、憤怒和厭惡)，用5個級別的分數對每張圖像打分。每個情緒標記的平均得分作為其描述程度來生成一個標記分布。同樣，SBU 3DFE包含2500張表情灰度圖，每一張圖像由23個人以相同的方式打分。

第三個數據集Emotion6是包含1980張人臉圖像，采用梯度直方圖法同時提取人臉圖像的特征，并采用PCA技術將其特征維度降到168維[15]。Emotions6數據集中有7種情緒標記，除了S-JAFFE和S-BU_3DFE數據集中的6種基本情緒標記外，進一步引入中立情緒標記，用對7種情緒的投票來生成標記分布。

第四個數據集M2B和第五個數據集SCUT-FBP分別包含1240張像素大小為128×128的面部圖像和1500張像素大小為350×350的面部圖像，每次隨機顯示一張面部圖像，評估者被要求從5個不同層次評估其面部美麗的吸引力，最后，由每個層次吸引力水平的百分比生成每張面部圖像的標記分布。

第六個數據集Natural Scene包含2000幅自然場景圖像，每一張圖像有9個場景標記(即：植物、天空、云、雪、建筑、沙漠、山、水和太陽)。10位人工標注員根據每張圖像與9個場景標記的相關度進行獨立決策降序排序，最后，通過非線性規劃過程轉化為標記分布。

第七個數據集Movie包含7755部電影，每一部電影包含從1星到5星的5個電影評級，相當于5個標記。將每部電影各評級上評分人數占總評分人數的比值作為各標記上的描述程度，來生成每部電影示例的標記分布。

3.2 評價指標

表3 標記分布學習的評價指標

3.3 實驗設置

為了驗證本文提出的LDL-LLC算法的性能，將其與6種常用的LDL算法進行對比，分別是：問題轉換方法PT-Bayes，算法適應方法AA-BP，專用方法SA-IIS、CPNN、LDL-LCLR和LDLSF，6種對比算法的參數設置和搜索范圍均與原文一致。其中，LDL-LCLR算法的參數λ1、λ2、λ3、λ4、k和ρ分別被設為10-4、10-3、10-3、4和1。LDLSF算法的參數λ1、λ2和λ3從 {10-6,10-5,…,10-1} 中搜索選取，正項的懲罰標量ρ設置為10-3。

本文提出的LDL-LLC算法的參數λ1， 它的作用是約束l1范數正則化對權重參數的影響，λ1取值越大，意味著模型會更注重擬合l1范數正則化學習每個標記特有特征的特性。為了防止過擬合，λ1從 {10-6,10-5,…,10-1} 中搜索選取。同理，約束LDL-LLC的參數λ2和λ3也從 {10-6,10-5,…,10-1} 中搜索選取，令使用最小二乘法度量真實標記分布和預測標記分布間距離的損失函數占據主導地位。參數m是k-means方法對訓練數據進行聚類后的組數，m從 {1,2,3,4,…,9} 中搜索選取。正項的懲罰標量ρ設置為10-3，變量Z的列數u設置為3。W初始化為單位矩陣，M和V都初始化為對角矩陣，所有對角元素都為0.5，其它變量初始化為0。

3.4 實驗結果與分析

在每個數據集上，都進行10次5折交叉驗證。具體來說，就是將數據集隨機劃分為10份，選取其中的8份作為訓練集，剩下的2份作為測試集，重復10次該過程。表4和表5分別展示了Chebyshev和Cosine評價指標上本文提出的LDL-LLC算法和6種對比算法在7個LDL真實數據集上的實驗結果，并對表中每一行的最優數據進行加粗。

表4 標記分布方法Chebyshev距離比較

表5 標記分布方法Cosine相似度比較

為了更直觀分析7種算法在性能的差異，表6展示了每種評價指標的Friedman統計量FF和相應的臨界值，每種評價指標在α=0.05顯著水平下的Friedman檢驗都拒絕“全部對比的算法具有相等的預測性能”這一原假設。

表6 Friedman檢驗統計值和臨界值

圖1繪制了每種評價指標上顯著性水平α=0.05的臨界差分圖。在每張臨界差分圖中，每個算法的位置表示它在對應評價指標上性能的平均排名，位置靠右的算法性能越好。如果兩種算法在所有數據集上的平均排名相差至少一個臨界值域(CD=3.4014)，則兩種算法之間的性能就會顯著不同。反之，兩種算法之間性能差異不顯著，使用粗線連接。由圖1可得到如下結論：

圖1 每個評價指標下所有算法的臨界差分

(1)7種LDL算法總排名為：LDL-LLC>LDLSF>LDL-LCLR>SA-IIS>AA-BP>CPNN>PT-Bayes。本文提出的LDL-LLC算法始終處于臨界差分圖的最右端，表明了LDL-LLC算法性能的優越性。

(2)LDL-LLC、LDLSF、LDL-LCLR、SA-IIS算法的平均排名優于AA-BP和PT-Bayes算法，原因在于算法適應方法AA-BP是直接修改BP算法的一些約束條件來擴展BP算法，用神經網絡的輸出作為標記的描述程度。問題轉換方法PT-Bayes將處理單標記學習問題的貝葉斯算法計算出每個標記上的后驗概率作為對應標記的描述程度。AA-BP和PT-Bayes算法通過改造現有的BP算法和貝葉斯算法后，雖然能處理LDL問題，但是效果不如直接聚焦標記分布的預測問題設計的專用方法：LDL-LLC、LDLSF、LDL-LCLR和SA-IIS算法。

(3)LDL-LLC、LDLSF、LDL-LCLR算法的平均排名優于CPNN和SA-IIS算法，原因在于LDL-LLC、LDLSF、LDL-LCLR算法對標記相關性進行了挖掘和利用，借助這些隱藏在標記空間中的額外信息，來提升LDL算法的性能。

(4)LDL-LLC算法的平均排名優于LDLSF和LDL-LCLR算法，原因在于：①LDLSF算法挖掘和利用的是全局標記相關性，但是在現實世界的任務中，不同的示例大多共享不同的標記相關性，很少有標記相關性是全局適用的。并且LDLSF算法在計算標記間的相關性時，直接計算訓練標記矩陣各列之間的皮爾遜相關系數，用計算出的系數來衡量兩兩標記間的相關性。但是一些標記在訓練數據中可能只有很少的正面示例，因此由訓練標記矩陣求出的標記相關性可能會不可靠。②LDL-LCLR算法雖然將訓練數據進行了分組，在每組數據上挖掘和利用標記間的相關性。但是LDL-LCLR算法用全局標記相關性來度量每組訓練數據標記間的相關性。并且LDL-LCLR算法的模型建立在原始高維特征空間上，忽略了實際分類學習任務中存在無關和冗余特征的事實。③本文提出的LDL-LLC算法通過引入局部流形正則化器，不去預先指定任何標記相關性矩陣來生成流形正則化器中的拉普拉斯矩陣，而是將每組訓練數據的拉普拉斯矩陣當成變量去迭代更新，更全面的挖掘和利用了局部標記相關性。同時，利用l1和l2,1范數對權重參數進行正則化約束，來學習每個標記的私有特征和所有標記的共享特征，減少了無關和冗余特征干擾。

4 結束語

本文提出一種基于局部標記相關性的標記分布學習算法(LDL-LLC)，該算法將特征選擇和局部標記相關性結合起來。通過引入局部流形正則化器，不去預先指定任何標記相關性矩陣來生成流形正則化器中的拉普拉斯矩陣，而是將拉普拉斯矩陣當成變量去迭代更新，探索和利用局部標記相關性。同時，利用l1和l2,1范數對權重參數矩陣進行正則化約束，來學習每個標記的私有特征和所有標記的共享特征，以減少無關和冗余特征干擾。最后，用求得的權重參數矩陣去預測未見示例的標記分布。在多個真實標記分布數據集上的對比實驗結果表明本文提出的算法是有效且可行的。