多义性学习在机器学习研究中一直是一个热门的领域. 单标记学习(single-label learning, SLL)和多标记学习(multi-label learning, MLL)^{[1, 2]}是目前解决标记多义性问题(label ambiguity problem)的两种成熟的学习范式: 前者假设每个实例只能与一个预定义的标记相关联, 而后者假设每个实例可能具有一组类标记. 大量研究^[3-5]表明: 多标记学习是一种应用更广泛的学习范式, 能够解决更复杂的标记多义性问题. 然而, 单标记学习和多标记学习都无法回答更进一步的问题, 即标记以多大的程度描述样本. 现实世界中, 数据的标记往往带有对样本的描述程度, 比如歌曲评分预测, 由于对歌曲的喜爱程度评分由多个个体进行标注, 不同的分数表达了评分者对歌曲的不同感受, 对这些分数取平均得到最终评分并不恰当, 因为歌曲在不同人群中的评分可能存在两极分化, 比如青少年和老年人对于嘻哈歌曲的不同态度, 平均得分不能全面反映人们对于歌曲的真实评价. 为了解决这一问题, Geng等人^[6]提出了一种新的多义性学习范式——标记分布学习(LDL), 正式给出了标记分布学习的定义, 总结了标记分布学习在处理标记多义性问题上的优势. 作为多标记学习的自然延伸, 标记分布学习可以更加广泛地应用到更多解决标记多义性问题的场景中.

假定有n个样本, 每个样本由一个d维特征向量表示, 则所有样本组成样本集X=[x₁; x₂; …; x_n]∈R^n×d. 使用l个标记对每个样本进行标注, 所有标记组成有限标记集Y={y₁, y₂, …, y_l}. 使用描述度$d_\mathit{\boldsymbol{x}}^y(d_\mathit{\boldsymbol{x}}^y \in [0, 1]且\sum\nolimits_y {d_\mathit{\boldsymbol{x}}^y} = 1)$来量化表示标记y对样本x_i的描述程度, 则所有标记对样本的描述度组成样本的标记分布${\mathit{\boldsymbol{D}}_i} = [d_{{\mathit{\boldsymbol{x}}_i}}^{{y_1}}, d_{{\mathit{\boldsymbol{x}}_i}}^{{y_2}}, ..., d_{{\mathit{\boldsymbol{x}}_i}}^{{y_l}}],$所有样本的标记分布组成样本集对应的标记分布空间D=[D₁; D₂; …; D_n]∈R^n×l.

给定一个训练集T={(x₁, D₁), (x₂, D₂), …, (x_n, D_n)}, 其中, x_i∈X表示一个样本, D_i∈D为样本x_i对应的标记分布, 寻找一个从输入特征空间X到标记分布空间D的映射的过程称为标记分布学习. 假设X经过映射得到的最终标记分布预测空间为$\mathit{\boldsymbol{\hat D}},$则标记分布学习的目标是使$\mathit{\boldsymbol{\hat D}},$和D尽可能相似.

由于标记分布可以看作是一种标记关系, 因此在学习过程中, 不应该忽略标记之间的相关性. 例如在图像注释中, 假设沙漠和太阳是强相关的, 则当一张图像与沙漠强相关时, 图像有很大可能与太阳相关. 基于此, 近年来, 一些关于标记分布学习的研究考虑了标记间的相关性. Wang等人^[7]用二进制编码样本后使用调整余弦相似度(the adjusted cosine similarity, ACS)来计算标记相关性. 在文本情感识别领域, Zhou等人^[8]使用普鲁契克情感色轮(Plutchik’s wheel of motions)^[9]得到基于情感先验信息的标记相关性. Zhou等人^[10]、Jia等人^[11]应用Pearson相关系数计算标记相关性. Ren等人^[12]通过低秩约束获得标记间的相关性, 提出了LDL- LCLR算法. 在Zhang等人^[13]提出的COS-LDL算法中, 使用基于余弦的距离映射来度量标记相关性. Zhao等人^[14]通过将LDL问题转换为最优传输(optimal transport, OT)问题, 将OT问题中的ground metric用于刻画标记相关性. 然而, 以上研究中, 标记相关性大都只是通过常用的相似性度量来量化标记两两之间的相似性, 可能无法反映标记之间的复杂关系; 此外, 这些方法只在训练过程中利用标记相关性, 在最终的标记预测中并没有显式利用此相关性. 但在预测某一标记的分布时, 考虑此标记和其他标记间的相关关系是很有必要的, 因为采用一些标记描述某一个体时, 所有标记都不是互不相关的, 标记空间中每个标记的状态都会对整个标记分布产生影响. 标记相关性信息在训练阶段辅助模型训练, 在标记分布预测时也能够辅助模型预测. 直接使用训练学习到的模型参数将测试样本从样本空间(原始样本空间或经过空间变换的潜在样本空间)映射到标记分布空间, 只是单纯地将标记看作样本空间特征的线性组合, 标记之间各自独立. 但是标记间的相关信息是我们获取到的关于标记的有利信息, 利用此信息可以辅助预测. 例如: 在图 1所示的图像注释任务中, 我们收集到了很多风景图, 选择标记瀑布(y₁)、岩石(y₂)、树木(y₃)、青苔(y₄)对这些图像进行描述, 所有图像与其对应的标记分布组成了图像注释训练集. 假定利用此训练集我们获取到了标记间的相关关系矩阵G=[g₁, g₂, g₃, g₄]和特征映射矩阵W=[w₁, w₂, w₃, w₄], 其中, 列向量g_i(i=1, 2, 3, 4)表示每个标记与标记y_i的相关性, 列向量w_i(i=1, 2, 3, 4)为求样本描述度$d_\mathit{\boldsymbol{x}}^{{y_i}}$时样本特征向量x对应的特征映射向量. 对于测试样本, 图像中存在大面积的岩石、部分青苔、一条瀑布和一小棵树, 由于树在整个图像中所占比例很小且整张图片色调偏暗, 图像特征向量x_test中与y₃相关的特征值会很小, 在不考虑标记间的相关关系时, 直接对样本x_test经过特征映射W求标记分布, 求得的y₃对应的描述度很小甚至为0, 如图 1中d_before所示. 若在预测时考虑标记间的相关信息G, 则得到调整后的标记分布为d_after. 可以看出: 由于考虑了每个标记对标记y₃的影响, 使得y₃对应的描述度由0上升至0.18; 同样地, 其他标记的描述度也因为考虑了标记间的相关关系发生了改变. 调整后的标记分布d_after更全面、细致地描述了图片内容, 使标记分布预测更加准确并且贴合真实情况.

为了解决上述问题, 我们提出了一种新的关键假设: 对于每一个独立的标记, 它的最终预测涉及到其自身的预测和其他标记的预测之间的协作. 基于此假设, 我们提出了一个新的标记学习方法——考虑标记间协作的标记分布学习(label distribution learning with collaboration among labels, LDLCL). 我们首先通过标记空间中的稀疏重构来学习标记相关性矩阵, 得到相关性矩阵后, 在训练和预测阶段均使用学习到的标记相关性矩阵实现标记间的协作. 具体来讲, 我们在训练阶段引入了标记独立嵌入作为潜在的标记分布空间, 目的是在训练模型参数的同时, 用学习到的标记相关性拟合最终预测. 我们在14个标记分布学习中广泛使用的数据集上对LDLCL算法的有效性进行了验证, 实验结果表明, 我们的方法优于同类方法.

本文主要贡献如下:

(1)      提出在计算标记相关性时考虑标记间的协同作用来获得标记相关性矩阵;

(2)     使用核函数度量样本间的相似性, 同时, 在计算相似性时考虑了样本标记个数的影响. 在训练过程中考虑了训练样本间的相似性, 在标记预测时考虑了测试样本与训练样本间的相似性;

(3)     在标记分布学习模型训练和样本标记预测两个阶段都显式使用了标记相关性.

1 相关工作 1.1 标记分布学习

标记分布学习范式提出后, 已被广泛应用到各种解决标记多义性问题的研究中. 为了解决年龄估计问题, Geng等人^[15]首次提出了IIS-LDL方法. 基于该方法, 一张人脸图像可以在训练过程中不但提供其对应的确切年龄, 同时还能够提供与确切年龄相近的年龄区间, 从而有效提高了样本包含的信息量, 进而提高了年龄估计的准确度. 为了进一步提高年龄估计的准确性, 文献[16]提出了基于条件概率的神经网络算法CPNN. 该方法构造了一个简单的3层网络, 将样本特征和目标年龄同时作为输入变量, 利用网络隐藏层自动选择特征完成年龄估计. 在文献[16]首次使用神经网络后, Yang等人^[17]通过将标记分布学习和深度学习相结合, 提出了深度标记分布学习(deep label distribution learning, DLDL)算法. Gao等人^[18]对DLDL算法进行了改进, 使深度标记分布学习不仅可以应用到年龄估计, 还可以用于头部姿态估计, 并且能够提高多标记分类和语义分割任务的识别性能. 针对标记分布学习训练过程计算量大、时间复杂度高的问题, Wang等人^[7]提出的BC-LDL算法使用定长二进制串编码样本, 通过计算二进制码间的海明(Hamming)距离, 选择最近邻k个样本的二进制码生成测试样本的标记分布. 之后, 为了解决BC-LDL算法中采用二进制编码样本带来的量化误差和长二进制码导致的模型训练耗时问题, Wang等人^[19]设计了一个有效的离散二进制编码框架对样本编码. 该框架集成了样本间语义相似度信息和原始标记分布用于学习具有高度区分性的二进制码, 形成了DBC-LDL算法. Wang等人^[20]提出的KELM-LDL算法通过高斯核函数将特征映射到高维空间, 然后对原标记空间建立核极限学习机回归模型求得输出权值, 以此减少计算量. 与大多数LDL算法中直接使用样本的全部特征进行模型训练不同, 为了减少冗余和不相关特征对算法性能的影响, Ren等人^[21]提出对样本特征进行选择, 通过对样本特征映射权重矩阵W进行L1范数约束选择标记特定属性(label-specific features), 同时, 用L2范数约束特征映射权重矩阵M选择共有特征, 使用选择到的特征完成LDL模型训练和样本标记分布预测. Xu等人^[22]提出的LSE- LDL算法直接将样本空间映射到一个潜在语义空间中, 使模型在学习标记分布映射的同时进行特征选择. 此外, Zhao等人^[23]对标记分布学习中选择什么样的距离度量作为目标函数进行了实验, 并基于实验结果提出了一些建议.

现有的LDL算法可以分为3类: 基于问题转换(problem transformation, PT)策略的算法、算法自适应(algorithm adaption, AA)方法和专门为解决LDL问题设计的专用算法(specialized algorithm, SA). 问题转换算法将LDL问题转换为多个SLL问题, 然后利用现有的SLL方法来解决. 例如, 将SVM转换为PT-SVM和将Bayes转换为PT-Bayes. 算法自适应的主要思想是: 将传统算法修改为适用于LDL的学习范式, 如AA-KNN算法^[6]和LogitBoost算法^[24]. 近些年来, 专门针对LDL问题设计的算法通过直接模拟每个标记对特定实例的相对重要性, 取得了很好的效果.

1.2 标记分布学习中的标记相关性

近几年内, 陆续有文献针对LDL中标记之间的相关性进行了研究. Jia等人^[11]提出的LDLLC算法中, 使用每个标记对应的特征映射权重矩阵W中列向量之间的欧式距离表示标记两两间的相似性, 同时使用Pearson相关系数约束标记之间的相似度. Ren等人^[12]提出的LDL-LCLR算法同时利用标记之间的全局相关性和局部相关性为训练模型提供更多的信息. 具体来说, 基于低秩近似的标记相关性矩阵被应用于捕获全局标记相关性, 同时采用局部样本间的标记相关性来修正标记相关性矩阵. Jia等人^[25]提出的LDL-SCL算法考虑了标记间的局部相关性, 为了在局部样本上使用标记相关性, 对局部样本的影响进行编码, 并基于不同的样本集群设计一个局部相关向量作为每个样本的附加特征, 通过同时利用样本的原始特征和附加特征来预测样本的标记分布. 以上关于LDL的研究都考虑了标记相关性且取得了不错的效果, 但都只是关注了标记两两之间的相关性, 并且只在训练过程中利用了标记相关性. 受到多标记学习领域Feng等人^[26]考虑标记间协作关系的启发, 在标记分布学习问题中, 我们提出考虑每个标记与其他标记间的协作关系来完成标记分布学习任务.

2 考虑标记间协作的标记分布学习

首先对下文中要使用的符号进行说明. 为了与相关工作部分符号统一, 我们使用X=[x₁; x₂; …; x_n]∈R^n×d表示输入特征空间, Y={y₁, y₂, …, y_l}表示有限标记集, D=[D₁; D₂; …; D_n]∈R^n×l表示输入空间对应的标记分布空间. 其中, n为样本个数, d为样本的特征维数, l为标记空间中包含的标记个数. 除此之外, 我们使用D^j∈Rⁿ表示矩阵D的第j列向量并称D^j为一个标记向量, 标记向量D^j中每个元素$\mathit{\boldsymbol{D}}_i^j(i = 1, 2, ..., n)$表示标记y对样本x_i的描述度, D^-j=[D¹, D², …, D^j-1, D^j+1, …, D^l]∈R^n×(l-1)表示标记分布空间D除标记向量D^j外剩余标记向量组成的矩阵.

2.1 标记相关性矩阵

在LDLCL方法中, 我们首先需要学习一个标记相关性矩阵${\mathit{\boldsymbol{S}}^*} = [\mathit{\boldsymbol{S}}_1^*, \mathit{\boldsymbol{S}}_2^*, ..., \mathit{\boldsymbol{S}}_l^*] \in {R^{l \times l}}$用来描述标记之间的协作关系, S^*中的元素$s_{ij}^*$反映第i个标记对第j个标记的贡献程度, 对角线元素$s_{ii}^* = (1 - \alpha )/\alpha = 1/\alpha - 1$表示第i个标记对自身的贡献程度. 在假设每个标记的最终预测涉及到其自身预测和其他标记预测之间的协作的前提下, 我们将给定的标记矩阵D作为最终预测, 并通过以下方式学习标记相关矩阵S^*:

$\mathop {\min }\limits_{{{\mathit{\boldsymbol{S}}}^*}} \frac{1}{2}||\alpha \mathit{\boldsymbol{D}}{\mathit{\boldsymbol{S}}^*} - \mathit{\boldsymbol{D}}||_F^2$

(1)

其中, α∈[0, 1]为折衷参数, 用来控制每个标记与其他标记间协作的程度. 对公式(1)中αDS^*做因式分解, 同时引入新的标记相关性矩阵S=S^*-diag(S^*), 得到公式(2):

$\alpha \mathit{\boldsymbol{D}}{\mathit{\boldsymbol{S}}^*} = \alpha \mathit{\boldsymbol{D}}(\mathit{\boldsymbol{S}} + (1/\alpha - 1)\mathit{\boldsymbol{I}}) = (1 - \alpha )\mathit{\boldsymbol{D}} + \alpha \mathit{\boldsymbol{DS}}$

(2)

其中, S为不关注每个标记自身, 只考虑其他标记对此标记的贡献程度的标记相关性矩阵. 公式(2)表示: 每个标记可以由其自身和其他标记共同协作表示, 两者协作时各自的贡献程度分别为(1-α)和α. 将公式(2)代入公式(1), 得到关于标记相关性矩阵S的优化问题:

$\mathop {\min }\limits_\mathit{\boldsymbol{S}} \frac{1}{2}||\alpha \mathit{\boldsymbol{D}}(\mathit{\boldsymbol{S}} - \mathit{\boldsymbol{I}})||_F^2$

(3)

由于矩阵S中的对角线元素固定为0, 所以需要去掉对角线元素求解S. 对每个标记, 使用列向量s_j∈ R^l-1(j=1, 2, …, l)来表示其他(l-1)个标记对此标记的贡献程度, 对每个标记分别求解其对应的s_j, 可将公式(3)改写为如下公式(4):

$\mathop {\min }\limits_{{\mathit{\boldsymbol{s}}_j}} \frac{1}{2}||\alpha {\mathit{\boldsymbol{D}}^{ - j}}{\mathit{\boldsymbol{s}}_j} - \alpha {\mathit{\boldsymbol{D}}^j}||_2^2$

(4)

考虑到每个标记只会与其他标记中的几个标记有关, 而不会与大部分标记都相关, 因此, 标记之间的协作关系应该满足稀疏约束. 加入稀疏约束后, 公式(4)可扩展为公式(5):

$\mathop {\min }\limits_{{\mathit{\boldsymbol{s}}_j}} \frac{{{\alpha ^2}}}{2}||{\mathit{\boldsymbol{D}}^{ - j}}{\mathit{\boldsymbol{s}}_j} - {\mathit{\boldsymbol{D}}^j}||_2^2 + \hat \lambda ||{\mathit{\boldsymbol{s}}_j}|{|_1}$

(5)

其中, $\hat \lambda$为权衡参数, 控制s_j的稀疏程度. 为了清晰地说明标记间的协作关系, 我们在图 2中给出了标记相关性示例. 图 1中假设样本集中共有5个样本, 每个样本使用6个标记描述, 组成标记分布集合D∈R^5×6, 那么每个标记向量{D¹, D², …, D⁶}都可以由此标记向量本身和其他标记向量集合两个因素协作表示. 图 2中, 不同色块组成的矩阵为构成此矩阵的数值元素可视化的结果, 数值元素范围为[0, 1], 对应颜色范围由红过渡到蓝(0对应深蓝色, 1对应正红色). 从图 2中可以看出: 标记相关性矩阵S中的对角元素均为深蓝色, 表示对角线元素均为0, 同时, S中相同或相近颜色的色块较多, 表明S为稀疏矩阵.

公式(5)中, 未知变量s_j单独存在L1范数(L1-norm)约束, 同时以(D^-js_j-D^j)的形式受L2范数约束, 直接求解s_j比较困难. 为了方便求解, 参照范数相关问题的求解方法, 我们引入新的变量z_j, 同时令$\lambda = \hat \lambda /{\alpha ^2},$将公式(5)转化为公式(6):

$\left. \begin{array}{l} \mathop {\min }\limits_{{\mathit{\boldsymbol{s}}_j}, {\mathit{\boldsymbol{z}}_j}} \frac{1}{2}||{\mathit{\boldsymbol{D}}^{ - j}}{\mathit{\boldsymbol{s}}_j} - {\mathit{\boldsymbol{D}}^j}||_2^2 + \lambda ||{\mathit{\boldsymbol{z}}_j}|{|_1}\\ {\rm{s}}{\rm{.t}}{\rm{.}}{\kern 1pt} {\kern 1pt} {\kern 1pt} {\mathit{\boldsymbol{s}}_j} - {\mathit{\boldsymbol{z}}_j} = 0 \end{array} \right\}$

(6)

公式(6)为含有两个变量的等式约束优化问题, 可以使用交替方向乘子法(alternating direction method of multipliers, ADMM)^[27]求解得到每一个s_j. 使用ADMM算法的关键是写出该问题对应的增广拉格朗日函数, 如公式(7)所示:

$L({\mathit{\boldsymbol{s}}_j}, {\mathit{\boldsymbol{z}}_j}, \rho , \mathit{\boldsymbol{Y}}) = \frac{1}{2}||{\mathit{\boldsymbol{D}}^{ - j}}{\mathit{\boldsymbol{s}}_j} - {\mathit{\boldsymbol{D}}^j}||_2^2 + \lambda ||{z_j}|{|_1} + \frac{\rho }{2}||{\mathit{\boldsymbol{s}}_j} - {\mathit{\boldsymbol{z}}_j} + \mathit{\boldsymbol{Y}}/\rho ||_2^2$

(7)

其中, ρ是惩罚参数, 控制s_j与z_j的相近程度; Y是拉格朗日乘子. 引入缩放对偶变量μ=Y/ρ, 根据ADMM算法的更新规则, 求得3个变量s_j、z_j、μ的更新公式如下:

$\left. \begin{array}{c} \mathit{\boldsymbol{s}}_j^{k + 1} = {(({\mathit{\boldsymbol{D}}^{ - j}})'{\mathit{\boldsymbol{D}}^{ - j}} + \rho \mathit{\boldsymbol{I}})^{ - 1}}(({\mathit{\boldsymbol{D}}^{ - j}})'{\mathit{\boldsymbol{D}}^j}{\mathit{\boldsymbol{D}}_j} + \rho (\mathit{\boldsymbol{z}}_j^k - {\mathit{\boldsymbol{\mu }}^k})), \\ z_j^{k + 1} = {S_{\lambda /\rho }}(\mathit{\boldsymbol{s}}_j^{k + 1} + {\mathit{\boldsymbol{\mu }}^k}), \\ {\mathit{\boldsymbol{\mu }}^{k + 1}} = {\mathit{\boldsymbol{\mu }}^k} + \mathit{\boldsymbol{s}}_j^{k + 1} - \mathit{\boldsymbol{z}}_j^{k + 1} \end{array} \right\}$

(8)

其中, (·)’为转置操作, S为L1范数的近邻算子(proximity operator), S_ω(t)=max(t-ω)+min(t+ω). 按照公式(8)更新3个变量至满足算法的迭代收敛条件, 得到最终的s_j. 对每个s_j, 在第j个位置插入0对其进行扩展, 得到S_j∈R^l, 0元素表示在标记相关性求解时不考虑标记自身产生的影响. 将得到的所有S_j=[S₁, S₂, …, S_l]按j的数值由小到大排列, 得到标记相关性矩阵S=[S₁, S₂, …, S_l]∈R^l×l, 其中, s_ii=0(i=1, 2, …, l).

2.2 标记分布学习模型训练

本节, 我们提出一种新的标记学习方法——考虑标记间协作的标记分布学习(LDLCL), 将第2.1节中学习到的标记相关性S加入到期望的预测模型中. 假设f(X)=[f₁(X), f₂(X), …, f_l(X)]∈R^n×l为标记分布映射函数, f₁(X), f₂(X), …, f_l(X)表示l个独立的标记分布预测算子, 同时考虑全部l个标签的预测结果, 根据公式(2), 我们得到如下公式(9):

$(1 - \alpha )f(\mathit{\boldsymbol{X}}) + \alpha f(\mathit{\boldsymbol{X}})S = f(X)((1 - \alpha )I + \alpha \mathit{\boldsymbol{S}})$

(9)

由公式(9)可以看出, 考虑标记间协作的标记分布学习问题可以看作两个独立的子问题: 训练原始的模型f(X), 利用标记相关性矩阵和模型的输出拟合最终预测结果.

为了将两个子问题结合起来, 我们引入一个标记独立的标记分布空间矩阵Z∈R^n×l. 令G=(1-α)I+αS, G表示标记整体的协作关系, 则考虑标记协作的预测结果为ZG, 并且预测的标记分布ZG要满足标记分布中描述度$d_\mathit{\boldsymbol{x}}^y \in [0, 1]且\sum\nolimits_y {d_\mathit{\boldsymbol{x}}^y} = 1$的约束, 由此可得如下目标函数:

$\left. \begin{array}{l} \mathop {\min }\limits_{Z, f} \frac{1}{2}||f(\mathit{\boldsymbol{X}}) - \mathit{\boldsymbol{Z}}||_F^2 + \frac{{{\lambda _1}}}{2}||\mathit{\boldsymbol{ZG}} - \mathit{\boldsymbol{D}}||_F^2 + \frac{{{\lambda _2}}}{2}\Omega (f)\\ {\rm{s}}{\rm{.t}}{\rm{. }}\mathit{\boldsymbol{ZG}} \times {{\bf{1}}_{l \times 1}} = {{\bf{1}}_{n \times 1}}\\ \mathit{\boldsymbol{ZG}} \ge {{\bf{0}}_{n \times l}} \end{array} \right\}$

(10)

其中, 第1项为模型训练项, 使训练得到的模型尽可能地接近标记分布空间Z; 第2项为预测拟合项, 目的是使利用了标记间协作的预测结果更接近真实的标记分布; 第3项为模型参数控制项, 防止模型过拟合. λ₁、λ₂为权重参数, 用于权衡模型训练和预测拟合的重要程度. 两个约束条件保证预测拟合得到的标记分布满足对每个样本所有描述度都非负, 且描述度之和为1.

假设映射函数f(X)=φ(X)W, 其中, φ(·)表示对输入数据进行空间变换, W为特征映射的权重矩阵. 采用标记分布学习中常用的L2范数来约束模型参数W, 即:

$\Omega (f) = ||\mathit{\boldsymbol{W}}||_F^2$

(11)

将f(X)=φ(X)W和公式(11)代入公式(10), 得到最终的目标函数:

$\left. \begin{array}{l} \mathop {\min }\limits_{\mathit{\boldsymbol{Z}}, \mathit{\boldsymbol{W}}} \frac{1}{2}||\varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{Z}}||_F^2 + \frac{{{\lambda _1}}}{2}||\mathit{\boldsymbol{ZG}} - \mathit{\boldsymbol{D}}||_F^2 + \frac{{{\lambda _2}}}{2}\Omega (f)\\ {\rm{s}}{\rm{.t}}{\rm{. }}\mathit{\boldsymbol{ZG}} \times {{\bf{1}}_{l \times 1}} = {{\bf{1}}_{n \times 1}}\\ \mathit{\boldsymbol{ZG}} \ge {{\bf{0}}_{n \times l}} \end{array} \right\}$

(12)

2.3 优化

接下来, 我们对第2.2节标记分布学习模型训练的目标函数公式(12)的求解进行具体说明. 公式(12)为含有两个未知变量Z和W的约束优化问题, 采用迭代更新法求解公式(12). 具体步骤如下.

1) 固定W更新Z

在W为定值时, 关于Z的函数为

$\mathop {\min }\limits_\mathit{\boldsymbol{W}} \frac{1}{2}||\varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{Z}}||_F^2 + \frac{{{\lambda _2}}}{2}||\mathit{\boldsymbol{W}}||_F^2$

(13)

直接对公式(13)关于W求导令导数为0, 可以求得最佳的未知变量W^*, 并且在之后的标记分布预测中使用f(X_test)=φ(X_test)W^*求得测试样本的标记分布. 但这样做需要显式地计算特征映射φ(X). φ(·)将特征从低维空间映射到高维空间, 直接计算映射结果计算量很大; 同时, 我们也不希望关注特征映射的具体形式. 因此, 为了进一步简化一般非线性情形下的核扩展, 我们引入一个新的变量E=φ(X)W-Z, 使得可以使用核方法处理此问题, 把高维空间的计算通过低维空间的计算外加一些线性变换完成.

引入变量E后, 公式(12)转化为有3个未知变量的约束优化问题:

$\left. \begin{array}{l} \mathop {\min }\limits_{\mathit{\boldsymbol{Z}}, \mathit{\boldsymbol{W}}, \mathit{\boldsymbol{E}}} \frac{1}{2}||\mathit{\boldsymbol{E}}||_F^2 + \frac{{{\lambda _1}}}{2}||\mathit{\boldsymbol{ZG}} - \mathit{\boldsymbol{D}}||_F^2 + \frac{{{\lambda _2}}}{2}||\mathit{\boldsymbol{W}}||_F^2\\ {\rm{s}}{\rm{.t}}{\rm{. }}\mathit{\boldsymbol{Z}} - \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{E}}\\ \mathit{\boldsymbol{ZG}} \times {{\bf{1}}_{l \times 1}} = {{\bf{1}}_{n \times 1}}\\ \mathit{\boldsymbol{ZG}} \ge {{\bf{0}}_{n \times l}} \end{array} \right\}$

(14)

固定Z更新W和E. 当Z为定值时, 关于W和E的拉格朗日函数为

$L(\mathit{\boldsymbol{E}}, \mathit{\boldsymbol{W}}) = ||\mathit{\boldsymbol{E}}||_F^2 + {\lambda _2}||\mathit{\boldsymbol{W}}||_F^2 + \langle \mathit{\boldsymbol{A}}, \mathit{\boldsymbol{Z}} - \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{E}}\rangle$

(15)

对E、A、W分别求导, 得:

$\left. \begin{array}{c} \frac{{\partial L}}{{\partial \mathit{\boldsymbol{E}}}} = 0 \Rightarrow \mathit{\boldsymbol{E}} = \mathit{\boldsymbol{A}}, \\ \frac{{\partial L}}{{\partial \mathit{\boldsymbol{A}}}} = 0 \Rightarrow \mathit{\boldsymbol{Z}} - \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{E}}, \\ \frac{{\partial L}}{{\partial \mathit{\boldsymbol{W}}}} = 0 \Rightarrow \mathit{\boldsymbol{W}} = \frac{1}{{{\lambda _2}}}\varphi (\mathit{\boldsymbol{X}})'\mathit{\boldsymbol{A}} \end{array} \right\}$

(16)

由公式(16)可得, E和W两个变量都是关于A的函数. 定义$\mathit{\boldsymbol{H}} = \frac{1}{{{\lambda _2}}}\mathit{\boldsymbol{K}} + \mathit{\boldsymbol{I}}$, 可以得到A=H^-1Z. 其中, K=φ(X)φ(X)’为核函数, I为单位阵. 本文中, 我们选高斯核函数计算K, 也就是说, ${k_{ij}} = K({\mathit{\boldsymbol{x}}_i}, {\mathit{\boldsymbol{x}}_j}) = \exp ( - ||{\mathit{\boldsymbol{x}}_i} - {\mathit{\boldsymbol{x}}_j}||_2^2/(2{\sigma ^2})).$核函数使我们无需显式计算每一个φ(x_i), 直接求出φ(x_i)φ(x_i)’的值. 关于本文中所选高斯核函数中参数σ的取值, 将在第4.3节参数设置中详细说明.

2) 固定W更新Z

令模型输出$f(\mathit{\boldsymbol{X}}) = \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} = \frac{1}{{{\lambda _2}}}\varphi (\mathit{\boldsymbol{X}})\varphi (\mathit{\boldsymbol{X}})'\mathit{\boldsymbol{A}} = \frac{1}{{{\lambda _2}}}\mathit{\boldsymbol{KA}} = \mathit{\boldsymbol{T}},$用T替换公式(12)中的φ(X)W, 当W为定值时, 关于Z的目标函数可写为公式(17):

$\mathop {\min }\limits_{\mathit{\boldsymbol{Z}}, {\mathit{\boldsymbol{Y}}_1}, {\mathit{\boldsymbol{Y}}_2}} ||\mathit{\boldsymbol{Z}} - \mathit{\boldsymbol{T}}||_2^2 + {\lambda _1}||\mathit{\boldsymbol{ZG}} - \mathit{\boldsymbol{D}}||_F^2 + \langle {\mathit{\boldsymbol{Y}}_1}, \mathit{\boldsymbol{Z}} - \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{E}}\rangle + \langle {\mathit{\boldsymbol{Y}}_2}, \mathit{\boldsymbol{ZG}} \times {{\bf{1}}_{l \times 1}} - {{\bf{1}}_{n \times 1}}\rangle$

(17)

使用对偶梯度法更新变量Z、Y₁和Y₂:

$\left. \begin{array}{c} \mathit{\boldsymbol{Z}} = (\mathit{\boldsymbol{T}} + {\lambda _1}\mathit{\boldsymbol{DG'}} - {\mathit{\boldsymbol{Y}}_1}{{{\bf{1'}}}_{l \times 1}}\mathit{\boldsymbol{G'}} - {\mathit{\boldsymbol{Y}}_2}\mathit{\boldsymbol{G'}}){(\mathit{\boldsymbol{I}} + {\lambda _1}\mathit{\boldsymbol{GG'}})^{ - 1}}, \\ \mathit{\boldsymbol{Y}}_1^{k + 1} = \mathit{\boldsymbol{Y}}_1^k + \alpha (\mathit{\boldsymbol{Z}} - \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} - \mathit{\boldsymbol{E}}), \\ \mathit{\boldsymbol{Y}}_2^{k + 1} = \mathit{\boldsymbol{Y}}_2^k + \alpha (\mathit{\boldsymbol{ZG}} \times {{\bf{1}}_{l \times 1}} - {{\bf{1}}_{n \times 1}}) \end{array} \right\}$

(18)

其中, α为梯度上升的步长, Y₁和Y₂为拉格朗日乘子.

根据公式(16)、公式(18)迭代更新变量W、E、Z值, 直到满足终止条件, 最后得到变量A的最优值.

3 标记分布预测

训练阶段得到最终的拉格朗日乘子A后, 根据$f(\mathit{\boldsymbol{X}}) = \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} = \frac{1}{{{\lambda _2}}}\varphi (\mathit{\boldsymbol{X}})\varphi (\mathit{\boldsymbol{X}})'\mathit{\boldsymbol{A}} = \frac{1}{{{\lambda _2}}}\mathit{\boldsymbol{KA}}$计算得到模型输出, 再根据f(X)((1-α)I+αS)=f(X)G得到最终的预测结果, 即公式(19)所示:

$f({\mathit{\boldsymbol{X}}_{test}}) = \frac{1}{{{\lambda _2}}}{\mathit{\boldsymbol{K}}_{test}}\mathit{\boldsymbol{AG}}$

(19)

我们使用X_train表示训练集样本, X_test表示测试集样本. 需要注意的是: 在训练阶段, K=φ(X)φ(X)’中的X为训练集样本X_train, 用以度量训练集样本间的相似度. 在标记预测过程中, K_test=φ(X_test)φ(X_train)’∈R^m×n, 用来度量测试集和训练集样本间的相似度. 其中, m为测试集样本个数, n为训练集样本个数. 通过使用核函数, 使我们可以不用关心特征映射空间φ(·)的具体形式, 直接计算样本间的相似度.

图 3给出了LDLCL算法训练和测试过程的整体流程图(样本相似度¹为训练集样本间的相似度矩阵K, 样本相似度²为训练集和测试集样本间的相似度矩阵K_test).

4 实验 4.1 数据集

我们的14个数据集来自标记分布学习网站(http://LDL.herokuapp.com/download). Yeast_xx系列10个数据集(Yeast-alpha, Yeast-cdc, Yeast-elu, Yeast-diau, Yeast-heat, Yeast-cold, Yeast-dtt, Yeast-spo, Yeast-spo5和Yeast-spoem)来自酿酒酵母上的生物学实验, 数据集一共包含2 465个酵母菌基因样本, 每个基因通过24个特征表示, 每个样本对应的标记分布是不同时间点上基因的表达水平. Natural Scene数据集由2 000幅自然场景图像组成, 研究人员要求10个标注者用9种可能的标签给这些图像贴上标签, 即植物、天空、云、雪、建筑、沙漠、山、水和太阳. 对于每个图像, 每个人选择相关的标签并独立地按降序排列, 因此多标记排序的结果高度不一致. 使用非线性规划过程将不一致的排序转换为标记分布^[28], 最后利用文献[29]中提出的方法, 为每个图像提取294维特征向量作为图像的特征表示. 数据集S-JAFFE和SBU_3DFE是人类表情图像数据集, 分别包含213张面部表情图像和2 500张3D面部表情图像, 每张图像共有243个特征, 标记数6代表人类的6种表情, 包括快乐、悲伤、惊讶、恐惧、愤怒和厌恶. 多个不同的人根据图片中的人脸表情对6种表情进行打分, 最后对分数进行归一化得到标记分布. 数据集Movie是关于电影的用户评分, 一共包含7 755部电影, 每部电影共有1 869个特征, 每部电影的评分有5个级别, 相当于有5个标记. 将每个级别的评分人数占总评分人数的比例作为对应标记的描述度, 生成一个标记分布. 表 1中总结了这14个数据集的一些简要统计信息.

4.2 评价指标

标记分布学习算法的输出是标记分布, 评价算法表现的一个自然指标就是预测的标记分布与真实分布之间的平均距离或相似度. 根据文献[6]中的建议, 本实验中采用6种代表性的标记分布评价指标对算法性能进行验证, 包含两个分布之间的4个距离度量: Chebyshev距离(Chev↓)、Clark距离(Clark↓)、Canberra距离(Canberra↓)、Kullback-Leibler散度(KL-div↓)和两个分布之间的两个相似性度量: 余弦相关系数(Cosine↑)和交叉相似度(Intersec↑). ↓表示评价指标度量值越低性能越好, ↑表示评价指标度量值越高性能越好.

4.3 实验设置

我们将提出的LDLCL算法与7种算法进行了比较: PT-SVM算法、PT-Bayes算法、AA-BP算法、SA-IIS算法、SA-BFGS算法、LDLLC算法^[11]和LDL-LCLR算法^[12]. 其中, 前5种算法为经典的LDL算法, 后两种算法(LDLLC和LDL-LCLR)是近期LDL领域考虑标记间相关性的算法. 所有算法的代码均来自于原作者共享, 实验中参数取值均按照相应文献中的建议.

下面对LDLCL中使用核函数计算样本间相似度时参数的取值给出详细说明.

本文中, 我们使用高斯核函数计算样本间相似度, 也就是说, 两个样本x_i和x_j间的相似度按照k_ij=K(x_i, x_j)= exp(-‖x_i-x_j‖₂²/(2σ²))计算. 在使用高斯核函数时, σ控制样本间的分离程度/差别. σ越小, 核函数对x的衰减越快, 意味着放大了数据x之间的差别, 即高斯核K(x)对x值的变化很敏感. 大多数研究中, 对σ简单取值为所研究样本间欧式距离的平均值, 即公式(20)所示:

${\sigma _1} = \frac{{n(n - 1)}}{2}\sum\nolimits_{i = 1}^n {\sum\nolimits_{j = i + 1}^n {\sqrt {\sum\nolimits_{k = 1}^d {{{(\mathit{\boldsymbol{x}}_i^k - \mathit{\boldsymbol{x}}_j^k)}^2}} } } }$

(20)

其中, n为样本个数, d为样本特征维数, $\mathit{\boldsymbol{x}}_i^k$表示样本x_i对应的第k维特征.

对数据集Natural Scene、S-JAFFE、SBU_3DFE和Movie, 参照大多数研究, 我们取σ=σ₁.

对Yeast_xx系列10个数据集, 考虑到它们是相同样本的不同标记分布表示, 在计算样本间相似度时, 我们加入了标记个数对样本相似度的影响. 具体来讲, 我们取σ=σ₁×ω×num_labels, 其中, ω为权重参数, 用来控制标记个数对σ的影响程度; num_labels对应不同数据集包含的标记个数, 本文中我们取ω=0.5. 对具有不同标记个数的相同样本计算相似度时考虑标记个数是合理的, 样本的标记个数越少, 样本间相同标记的数目相应也会越少, 样本间的差别就会越明显, 样本间的相似度值对样本变化也就越敏感, 所需要的σ值就越小. 表 2列出了在10个数据集上是否考虑标记个数的实验结果, 对每个数据集, 第1行为考虑标记个数的实验结果, 第2行为不考虑标记个数的实验结果, 我们用粗体标记每个度量的最佳结果. 由表 2可知: 在计算具有不同标记个数的相同样本间相似性时, 考虑标记个数的影响是很有必要的.

4.4 实验结果

对于每一个数据集, 本文中, 我们都采用了十折交叉验证(ten-fold cross validation)进行实验. 具体来说, 实验中, 每个数据集中的实例都被随机地分为10部分: 一部分用于测试, 其余部分用于训练, 共进行10次实验. 我们记录了每个算法在6个评价指标的结果, 实验结果以“平均值±标准差(等级)(mean±std. (rank))”的形式给出, 等级是指所有LDL算法对每个度量的预测效果的排序. 此外, 在每个表中, 我们用粗体标记每个度量的最佳结果. 由第4.2节可知, 6个评价指标可分为两类: 4个距离度量评价指标(Chev↓, Clark↓, Canberra↓, KL-div↓)和两个相似性度量评价指标(Cosine↑, Intersec↑), 相同类型的评价指标实验结果相似. 因此, 本文在每一类中选择一半评价指标共3个评价指标(Clark↓, Canberra↓, Intersec↑)列出实验结果. 实验结果见表 3-表 5, 每个表展示一个评估度量的比较结果.

4.5 对比实验

为了验证LDLCL算法中考虑标记相关性的必要性, 我们不考虑标记间的相关性, 即令S=I, 其他实验参数设置保持不变, 进行了对比实验. 若在标记分布学习模型训练过程中不考虑标记间相关性, 公式(9)可写为

${(1 - \alpha )f(\mathit{\boldsymbol{X}}) + \alpha f(\mathit{\boldsymbol{X}})\mathit{\boldsymbol{S}} = f(\mathit{\boldsymbol{X}})}$

(21)

此时, 训练阶段的目标函数应去掉参数Z改写为

$\left. \begin{array}{l} \mathop {\min }\limits_{\mathit{\boldsymbol{E}}, \mathit{\boldsymbol{W}}} \frac{1}{2}||\mathit{\boldsymbol{E}}||_F^2 + \frac{{{\lambda _2}}}{2}||\mathit{\boldsymbol{W}}||_F^2\\ {\rm{s}}{\rm{.t}}{\rm{. }}D - \varphi (\mathit{\boldsymbol{X}})\mathit{\boldsymbol{W}} = \mathit{\boldsymbol{E}} \end{array} \right\}$

(22)

与第2.3节优化中类似, 关于E、W的拉格朗日函数为$L(\mathit{\boldsymbol{E}}, \mathit{\boldsymbol{W}}) = \frac{1}{2}||\mathit{\boldsymbol{E}}||_F^2 + \frac{{{\lambda _2}}}{2}||\mathit{\boldsymbol{W}}||_F^2 + \langle \mathit{\boldsymbol{Y}}, \mathit{\boldsymbol{D}} - \varphi (\mathit{\boldsymbol{X}})W - \mathit{\boldsymbol{E}}\rangle .$

对变量E、W、A分别求导, 可以得到A=H^-1D. 得到A后, 标记预测方式和第3节相同, 其中, G=(1-α)I+αS=I. 表 6为是否考虑标记相关性的实验结果, 对每个数据集, 第1行为考虑标记相关性的实验结果, 第2行为不考虑标记相关性的实验结果, 我们用粗体标记每个度量的最佳结果. 由表 6可知: 对大多数数据集, 考虑标记相关性可以提高算法性能.

4.6 参数影响

为了研究折衷参数α对实验结果的影响, 我们将α在[0, 1]范围内以0.1步长取值, 即α=[0, 0.1, 0.2, 0.3, …, 1]. 在不同数据集上运行LDLCL算法, 得到α不同取值下相应的6个评价指标的结果. 图 4所示为在S-JAFFE数据集上α不同取值下6个评价指标的结果. 由图 4可以看出, α∈[0.4, 0.6]时, 算法性能较稳定.

为了检验算法的鲁棒性, 我们分析了权衡参数λ₁和λ₂对算法性能的影响. 我们在[0.2, 2]范围内以0.2步长对λ₁进行选择, 即λ₁=[0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0]; 在[0.0002, 2]范围内以10倍间隔对λ₂进行选择, 即λ₁=[0.2, 0.4, 0.6, 0.8, 1.0, 1.2, 1.4, 1.6, 1.8, 2.0], λ₂=[0.0002, 0.002, 0.02, 0.2, 2]. 对所有的λ₁、λ₂, 在不同数据集上运行LDLCL算法, 得出相应取值下的结果. 图 5、图 6所示分别为在S-JAFFE、Yeast-dtt和Yeast-spo5这3个数据集上, λ₁、λ₂不同取值下6个评价指标的实验结果.

在图 5中, 令λ₂=0.02, 只改变λ₁的取值. 由图 5可以看出: 当λ₂固定、λ₁在[0.2, 2]范围内改变时, 算法在6个评价指标上的结果只在很小的范围内改变, 说明算法对λ₁的取值鲁棒. 在图 6中, 令λ₁=1, 只改变λ₂的取值. 由图 6可以看出: 当λ₁固定, 对S-JAFFE数据集, λ₂=0.02时, 算法在6个评价指标上的实验结果最好; 对Yeast-dtt和Yeast-spo5这两个数据集, λ₂的改变对实验结果影响很小, 在λ₂=0.02时, 可以取得很好的实验结果.

实验中, 对所有数据集, 我们选择λ₁=1, λ₂=0.02, α=0.5.

5 总结和展望

本文中, 我们将对于每个标记, 最终的预测涉及到它自己的预测和其他标记的预测之间的协作这一关键假设用于标记分布学习中. 基于这一假设, 我们通过稀疏重构得到了标记相关性矩阵, 并进一步将标记相关性用于标记分布学习模型的训练中, 在训练和预测中都显式利用了标记间的协作关系. 最后, 通过实验验证了我们这一方法的有效性. 如前所述, 标记间的相关性包含局部相关性和全局相关性, 本文中, 我们只考虑了标记间的全局相关性, 如何进一步利用标记间的局部相关性提高标记分布学习算法的性能, 有待后续研究.