第34卷第2期2021年2月
模式识别与人工智能
Pattern Recognition and Artificial Intelligence
Vol.34No.2
Feb.2021基于低秩表示的标记分布学习算法
刘睿馨1刘新媛1李晨1
摘要针对标记分布学习算法忽略标记相关性信息及数据存在异常和噪声值的情况，文中提出基于低秩表示的标记分布学习算法（LDL-LRR）.利用特征空间的基线性表示样本信息，实现对原始特征空间数据的降维.将低轶表 示（LRR）迁移至标记空间，对模型施加低秩约束，把握数据的全局结构.分别使用增广拉格朗日乘子法和拟牛顿法求解LRR和目标函数，再通过最大熵模型预测标记分布.在10个数据集上的对比实验表明，LDL-LRR性能良好，效果稳定.
关键词标记多义性，单标记学习（SLL），多标记学习（MLL），标记分布学习（LDL），低秩表示（LRR）
引用格式刘睿馨，刘新媛，李晨.基于低秩表示的标记分布学习方法.模式识别与人工智能，2021,34（2）:146156.
DOI10.16451/jki.issn1003-6059.202102006中图法分类号TP181
Label Distribution Learning Method Bad on
Low-Rank Reprentation
LIU Ruixin1,LIU Xinyuan1,LI Chen1
ABSTRACT Label correlations,nois and corruptions are ignored in label distribution learning algorithms.Aiming at this problem,a label distribution learning method bad on low-rank reprentation (LDL-LRR)is propod.The ba of the feature space is leveraged to reprent the sample information, and conquently dimensionality reduction of the data in the original feature space is achieved.To capture the global structure of the data,low-rank reprentation is transferred to the label space to impo low-rank constraint to the model.Augmented Lagrange method and quasi-Newton method are employed to solve the LRR and objective function,respectively.Finally,the label distribution is predicted by the maximum entropy model.Experiments on10datats show that LDL-LRR produces good performance and stable effect.
Key Words Label Ambiguity,Single-Label Learning,Multi-label Learning(MLL),Label Distribution Learning(LDL),Low-Rank Reprentation(LRR)
Citation LIU R X,LIU X Y,LI C.Label Distribution Learning Method Bad on Low-Rank Reprentation.Pattern Recognition and Artificial Intelligence,2021,34(2):146-156.
收稿日期：2020-08-03；录用日期：2020-12-09
Manuscript received August3,2020；设计英文
accepted December9,20208年级上册英语
国家自然科学基金项目(No.61573273)资助
Supported by National Natural Science Foundation of China(No. 61573273)
本文责任编委于剑
Recommended by Associate Editor YU Jian
1.西安交通大学软件学院西安710049
1.School of Software Engineering,Xi'an Jiaotong University,
Xi'an710049
单标记学习（Single-Label Learning,SLL）和多标记学习（Multi-label Learning,MLL）是目前常用于数据标注的机器学习模型[']，二者都关注标记是否描述实例，当数据语义信息丰富⑴时MLL更有效.但是标记描述实例的程度往往不同，基于均匀标记分布假设的MLL无法区分多个标记的主次关系，不适用于需要定性考虑标记是否描述实例且定量考虑标记对于实例的相对重要性的问题.
Geng[2]提出标记分布学习（Label Distribution Learning,LDL），解决标记描述实例的程度问题.标记分布学习给每个描述实例的标记分配一个描述
第2期刘睿馨等：基于低秩表示的标记分布学习算法147
度，并假设所有标记的描述度之和为1.这种方式概念简洁，可准确区分标记对于实例的重要程度差异，适用于复杂问题，应用场景广泛.
Geng等［3-4］提出改进迭代尺度-标记分布学习算法(Improved Iterative Scaling-Learning from Label Distributions,IIS-LLD)、条件概率神经网络(Conditional Probability Neural Network,CPNN)、自适应标记分布学习算法(Adaptive Label Distribution Learning,ALDL)，解决面部年龄估计问题.Zhou等⑸提出
recommend是什么意思情绪分布学习(Emotion Distribution Learning, EDL)，解决面部表情识别问题.Ling等⑷提出软视频解析算法(Soft Video Parsing,SP)，解决软视频解析问题.但是，上述算法都忽略标记间的相关性，阻碍方法性能提升.因此,Xu等［7］提出批注不完整的标记分布学习算法(LDL with Incomplete Annotation, IncomLDL)，假设均匀随机丢失标记分布矩阵的兀素，并引入迹范数作为正则化项，利用标记相关性深入学习标记空间的隐藏信息.Jia等［8］提出利用标记相关性的标记分布学习方法(LDL Method by Exploiting the Label Correlation,LDL-LC)，引入距离函数计算标记间的全局相关性信息.Zheng等⑼提出局部利用样本相关性的标记分布学习算法(LDL Algorithm by Exploiting Sample Correlations Locally, LDL-SCL)，对数据进行聚类，保证类内的实例共享相同的标记相关性信息.
已有的标记分布学习方法大多为监督信息完整的数据设计，然而为实例分配真实的标记分布需要花费大量的人力和时间成本［7］，当数据中存在噪声或异常值时，无法保证标记信息的完整性，且标记间相关性的获取难度增加.因此，本文提出基于低秩表示(Low-Rank Reprentation,LRR)［l0-ll］的标记分布学习算法(LDL Method Bad on LRR,LDL-LRR).LRR充分考虑样本间的相关性信息和子空间结构［l2］，保证所有数据在其自表达下构成的系数矩阵的秩最小，并获取数据集的全局相关性信息.由于系数矩阵遵循最低秩准则，在对有噪声和异常值的原始数据进行重构时具有鲁棒性.通过增广拉格朗日乘子法(Augmented Lagrange Method,ALM)求解LRR，并使用拟牛顿法(BFGS)对优化问题进行求解.在10个真实世界数据集上的实验表明，LDL-LRR在常用的评估指标上都取得一定提升，这验证本文算法的有效性和优越性.
1相关工作
为了方便介绍，本节预先给出主要的符号定义.实例的特征空间X=:X1,X2「・,x”］T沂R""，维度为q，第i个实例X沂X.标记集Y={y，兀，…,y c},c 表示标记集的大小，即描述实例的标记个数必表示第j个标记.町表示标记比描述实例x i的程度，记作描述度•每个标记的描述度都应满足
d X j沂［0,1］，移d X j i=1，
j=1
X i的标记分布d i=:d X;；d X2；•••；/：：］T，所有实例的标记分布构成的标记分布矩阵
D*=:d「，d2,…,d”］T沂R"".
Geng等卩-4］在解决面部年龄估计问题时给出标记分布学习的形式化定义，认为标记分布是一种类似概率分布的数据结构，与概率分布具有相同的约束条件，可使用条件概率的形式表示描述度，即
d X i=P(j x,).
给定训练集
s={(X1,d1),(X2M2),•••,(X",d")},
标记分布学习的目标是求解参数向量兹，使参数模型P(y X,；兹)生成与给定实例X，的真实标记分布d，尽可能相似的标记分布.
目前常见的标记分布学习算法主要基于如下3种设计策略［2，13］.
策略1是问题转化(Problem Transformation, PT)［13］，即将每个标记分布学习训练样本(X,,d,)转化成c个带有权重的单标记学习训练样本(X,,y,)，权重由标记的描述度硝给出，经过重采样的训练样本集可使用单标记学习算法处理.基于此策略设计的算法有PT-Bayes(PT:Bayes)［13］和PT-SVM(PT: Support V ector Machine)［13］.
策略2是算法改造(Algorithm Adaptation, AA)［13］，即将传统的单标记学习算法或多标记学习算法改造成可处理标记分布学习问题的算法.基于该策略设计的算法有基于k近邻(k Nearest Neighbor,kNN)改造的AA-kNN［13］和基于反向传播(Back Propagation,BP)神经网络改造的AA-BP［13］.
策略3是根据标记分布学习的特点设计专用算法(Specialized Algorithm,SA)［13］.专用算法的设计通常涵盖输出模型、目标函数和优化方法三部分.标记分布学习算法的输出模型常选取最大熵模型［14］，目标函数常采用Kullback-Leibler(KL)散度［15］度量真实标记分布与预测标记分布之间的相
似性，优化方法各有不同，SA-IIS［13］、SA-BFGS［13］分别选取改进迭代尺度算法(Improved Iterative
148模式识别与人工智能(PR&AI)第34卷
Scaling,IIS)［I6］和BFGS［i7］优化目标函数.实验表明策略3优于前两种策略⑵，因此基于策略3形成由输出模型、目标函数和优化方法构成的标记分布学习算法设计的泛化框架.
部分现有的专用算法在目标函数中引入标记间的相关性度量，提高标记分布学习模型的性能. LDL-LC⑻使用度量不同标记间的欧氏距离获取标记间的全局相关信息.LDL-SCL⑼使用k-means［I8］对训练数据进行聚类，位于同类内的实例共享相同的标记相关性信息，即标记间的局部相关性信息.将最大熵模型拆分为原始特征部分和附加特征部分，在附加特征部分及惩罚项引入局部相关性信息.基于低秩近似的标记相关性标记分布学习(LDL with Label Correlations via Low-Rank Approximation, LDL-LCLR)［I9］通过核范数近似获取全局相关性，通过k-means聚类获取局部相关性，并通过交替方向乘子法(Alternating Direction Method of Multipliers,ADMM)求解目标函数.算法为目标函数引入秩函数的凸包核范数，但未考虑对真实标记分布与预测标记分布之间差异的控制.
2基于低秩表示的标记分布学习算法
2.1低秩表示
数据集矩阵X=:X|,X2,-,x…］可以被字典矩阵(基矩阵)A=［a|,a2，…,a m］线性表示为
X=AC,(1)其中C=:C|,C2,-,c…］为线性组合表达系数矩阵.数据集X中每个数据样本都可由其它数据样本的线性组合表示为
x=移C x
将所有数据样本及其表达系数C j按一定方式排成矩阵，则式(1)等价于：
X=XC,(2)并且C应满足当x和x，属于不同子空间时，有C j= 0.式(2)使用数据集本身表示数据，称为数据的自表达(Self-reprentation)［20］.
为了提高算法对噪声或异常值的鲁棒性，本文以低秩表示作为基本假设，增强矩阵C各行(列)间的相关性，通过特征空间的基线性表示所有样本信息及其全局关系，将原始数据投影至更低维的线性子空间上，凸显数据的类内相似性和类间差异性［|0-1|，2|］.基于自表达子空间的特性，选取X本身作为字典矩阵，构造如下低秩优化问题：
min rank(C),s.t.X=XC.(3)考虑数据样本存在噪声和异常值，并且现实世
界的数据点大多位于仿射子空间而非线性子空间中，故假设
全免费英语学习网站X=XC+E,
则式(3)重写为
min rank(C)+姿||E椰2o,
C，E(4)
其中,E为数据样本的噪声和异常值,rank(C)为C 的秩函数，椰・椰2,0为l2,0范数，姿为平衡两部分影响程度的低秩系数.
由于秩函数的离散性，式(4)得到的低秩优化问题是一个非凸的NP-hard问题［22］.为了易于求出唯一最优解，需要对式(4)进行凸松弛.Fazel［23］已经证明矩阵核范数是秩函数在矩阵谱范数意义下单位球上的最佳凸逼近，因此可利用凸核范数近似替代非凸秩函数［24-25］，同时将〈0范数松弛为其凸包Z2j|范数［II］，得到如下凸优化问题：
min II C椰*+姿II E椰2I,
C,E2,1
其中，椰•椰*为矩阵的核范数，椰-椰2,1为l2,I范数，姿〉0为平衡两项权重的噪声系数.由于12」范数迫 使E的列趋于0，因此本文假设异常值是样本特定(Sample-Specific)［I0］的，即只有部分向量受到异常值干扰.引入J作为辅助变量：
min椰J椰*+姿椰E椰2|,
C，E(5)
解决凸优化问题的方法有牛顿法、最速下降法和增广拉格朗日乘子法［26-27］等，本文采用增广拉格朗日乘子法.构造式(5)的增广拉格朗日函数：min椰J椰*+姿椰E椰2|+
C,E,J,Y|』2，“
〈Y|,X-XC-E〉+〈Y2,C-J〉+
滋(I X-XC-E|+II C-J I F),
⑹其中，〈•，•〉为两个矩阵的点积，丫|、丫2为拉格朗日乘子，滋>0为正项的惩罚标量.为了方便求解，将式(6)表述为矩阵的迹的形式：
min椰J椰*+姿椰E椰2I+
C,E,J,Y|』2，“
tr(X-XC-E))+tr(Y T(C-J))+
滋(I X-XC-E|+II C-jii F).
(7)
第2期刘睿馨等：基于低秩表示的标记分布学习算法149
由于式（7）无约束条件，可将该优化问题划分 为如下子问题，通过交替方向乘子法对变量进行 优化.
1）更新J .固定变量C 和E ，保留式（7）中有关J
的项：
||J||* + tr[ Y T ( C - J )]+份求得J 的更新公式：丄椰J 椰 I /滋
II C -JII F .
1+ 21 Y 1
J -C + 321
1 滋丿
F 丿
J = arg min 2）更新C .固定变量J 和E ，保留式（7）中有关C
的项：
-tr （ Y T XC ） + tr （ Y T C ） +
滋[tr( - 2X t XC + C T X T XC + 2E t XC ) +tr( C T C - J T C - C T J )].
求关于C 的偏导，并令其偏导等于0，可得C 的更新 公式：
C = (I + X T X )-| -
X T X - X T E + J + 丄(X T Y 1 - Y 2).
I “ 丿
3)更新E .固定变量C 和J ，保留式(7)中有关E
的项：
l|E |2,1 - tr( Y T E ) +
滋 [tr( - 2E t X + 2E t XC + E t E )].
求得E 的更新公式:
E = arg min
姿椰弘
+
2 1
F 丿
E - [X - XC + 儿 1
1
2
4）更新乘子.对于拉格朗日乘子Y 1、丫2，可通过
karmin阶跃为/滋的梯度上升进行更新［28 - 29］:
Y 1 = Y 1 + “(X - XC - E ) , Y 2 = Y 2 + “(C - J ).
通过
/滋 = min （ n 滋 , /滋max ）roamer
更新/滋.选择合适的初始值，依照上述求解过程交替
迭代，直至满足收敛条件
II X - XC - E
椰 ¥ < 着 ,|| C - J 椰 ¥ < 着
或达到最大迭代次数，即可获取最优解J 、C 和E .
2.2 标记分布学习算法
基于低秩表示的标记分布学习算法（LDL-
LRR ） 符合专用算法［13］的设计策略，由输出模型、hercules
目标函数和优化方法构成.
第1节已经提出，描述度可使用条件概率的形
式表示，假设P （y x ）为参数模型，记作P （y x ；兹）.
本文采用最大熵模型作为输出模型：
1
（ 1
P （y ； x i ；兹）=歹ex p 移兹1，民-
（8）
i I k 丿
其中:
1 1
Z 、=移exp 移兹1，民
1 I k 丿
为归一化项，保证描述实例的所有标记描述度之和
为1；兹为描述原始特征和标记分布之间关系的系数
矩阵，兹“为兹中的元素；賠为训练集x 中的第i 个实
例X ，的第k 个原始特征.为了获取模型的最优参数
，构造如下目标函数表达式：
M （兹）=min （ L （兹）+ 姿 1 赘（兹）+ 姿 2 追（兹）），（9）
其中,L （兹）为定义在训练数据上的损失函数，赘（兹）
dade为控制模型复杂度的正则化项，追（兹）为表征原始
特征空间信息及标记间相关性信息的函数，姿1、姿2
为调节这3项重要性的非负参数.
损失函数L 用于度量真实标记分布D ，与预测标
记分布P （y x ,；兹）之间的相似性，常用的度量函数
有欧氏距离Jeffrey 分歧、KL 散度等［30］.多个对比 实验［31］表明KL 散度的表现最稳定，即
p - 1Q 1
KL ,（ Q I Q ）=移 Q l n Q ,
j I Q 丿
其中，E 、Q，分别为标记分布的第J 个元素• 本文基于KL 散度构造损失函数：
二専1 1 必 11
L （兹）=移移 R ln ［^T xT 「（10）
其中,d ：为标记y 对实例x ，的真实描述度,
P （刃x ,）为标记刃对实例x ，的预测描述度.
式（9）的第2项为关于兹的正则化项：blued是什么
赘（兹）=11^ I F ,
（11）
其中，椰• I f 为矩阵的Frobenius 范数，作用是控制 模型的复杂度，防止模型因过拟合导致算法泛化能
力的下降.
此外，根据平滑假设［32］，可将从特征空间得到
的低秩特性迁移到标记空间，使标记空间获得相似
的低秩结构.故式（9）的第3项表示为
八 2
追（兹）=P （y x ；兹）-P （y x ；兹）C
=
2
F （12）
II （I - C T ） P （ y x ；兹）t ||F ，
其中,P （y x ；兹）为预测的标记分布,e 为特征空间
150模式识别与人工智能(PR&AI)第34卷
的最低秩表示，通过控制P(y x；兹)与其自表达P(y x；兹)C之间的距离可有效地对标记分布进行预测.
将式(10)~式(12)代入式(9)，利用2.1节求得最优解C，得到待优化的最终目标函数：
M(兹)=叩［移移［心1n［八7+
姿i||0I F+姿2〔(I-C)P(y x；兹)=
丿
(n c((护))
叩〔移移［心1n［P^xJ J J+姿|tr(兹T兹)+
姿2tr(P(y x；兹)(I-C)(I-C T)P(y x；兹)T).
丿本文选取拟牛顿法L-BFGS(Limited-BFGS)［i7］求解目标函数M(兹)，主要思想是根据伪Hessian矩阵的递归关系式得到最优的搜索方向，有效节约内存空间.求取M(兹)关于兹的二阶泰勒展开式：
M(兹”+|)抑M(兹)+V M(兹”)T驻+押H(兹r)驻，
(13)其中，V M(兹”)为目标函数M(兹)在兹”处的梯度, H(0r)为目标函数M(兹)在0r处的Hessian矩阵，驻=(0r+|-0”)为参数变化量•假设M(0)为凸函数，则H(0r)为正定的，对式(13)关于驻求导并令其导数等于0，可得到全局极值点：
驻”=-H-I(0r)V M(0r).
以解出的驻”作为搜索方向向量，并选择满足Wolfe 准则的琢r作为步长，则0的迭代公式为
0r+I=0r+琢九
求解-H-|(0r)需要先计算目标函数M(0)的梯度V M(0):
鄣M=_移+移(%k p(y i x J)+2姿i兹以+
姿2{(x T(I-C)(I-C T)X+
(X T(I-C)(I-C T)X)T)0}啓
由于拟牛顿法仅需满足
V M(0r)-V M(0r-|)=H(0r)(0”-0”-|),
且尽量确保H(0r)与H(0r-|)接近，因此可得出H-I(0r)的迭代公式：
H-I(0r)=
—(0r-0r-|)(V M(0”)-V M(0”-|))T'
、-(V M(0r)-V M(0r-|))T(0r-0r-|)”.
H-1(0r-|)•
(,(V M(0r)-V M(0r-|))(0r-0”-|)丁］
l(V M(0r)-V M(0r-|))T(0r-0”-|)丿
(0”-0r-|)(0r-O r-I^
(V M(0r)-V M(0r-|))T(0r-0”-|)'
L-BFGS通过存储最近的m个(0r-0r-|)和(V M(0r)-V M(0r-i))，近似估计H-I(0r)，直到满足收敛条件或是达到最大迭代次数.最优解代入式(8)，求得标记分布P(y x；0).
由于标记分布定义每个标记的描述度
硝沂［0,1］，移=1,
因此最终输出的标记分布Output需满足
移d;=1.
n =I
而归一化指数函数softmax可将模型的预测结果映射至指数函数上，保证实数输出的映射结果在［0,+ 8)内，再对映射后的预测结果进行归一化，既保证每个标记的描述度吐沂［0,1］，又保证
移d；=1，
=1
故采用softmax对标记分布P(y x；0)进行归一化处理，得到最终输出的标记分布D ou tp u t.
3实验及结果分析
3.1实验数据集
this is the end选取10个现实世界数据集，前8个数据集为Yeast系列数据集，数据来自基于出芽的酿酒酵母进行的生物学实验［33］，共计2465个酵母基因实例.每个酵母基因与一个长度为24的描述程度向量关联，向量中的兀素表示一天24h内不同时刻的基因表达水平，归一化后组成相应基因的标记分布.Yeast 系列数据集共有10个，本文仅选用标记数目大于等于4的数据集，原因是LDL-LRR通过标记间的相关性信息可提高预测的性能表现，标记不足会导致相关性缺失.最后2个数据集是基于面部表情数据集jaffe［34］和BU-3DFE［35］改造的标记分布数据集SJAFFE和SBU-3DFE，各包含213幅和2500幅具有243维特征的灰度图像，每幅图像分别由60人和23人在6个基本情绪标记(快乐、悲伤、惊讶、恐惧、愤怒和厌恶)上进行5级评分，情绪强度由每种情绪的平均得分定义，归一化后得到情绪标记对图像样本的描述度.数据集特征如表1所示.
