传统的单标记学习假设每个样本只与单个类别相关, 而在真实世界的任务中, 一个样本可以同时与多个概念类别相关.例如, 在图片分类中, 一张图片中可以有多个对象, 如城市、道路[1]; 在生物信息学中, 每个基因序列有多种功能, 如新陈代谢、转录、蛋白质合成[2].为了处理这样的任务, 多标记学习成为机器学习领域的重要研究方向, 并被广泛应用于各个领域[3, 4].
经典的多标记学习方法要求训练样本拥有完整或者至少部分的真实标记, 对多标记任务而言, 真实标记是代价昂贵且不容易获取的资源.一方面, 标注真实标记需要领域专家知识, 而专家资源是昂贵且有限的; 另一方面, 标注多标记样本需要逐个检查候选标记是否与当前样本相关, 当标记数量比较多时, 标记正确的类别非常耗时耗力.随着众包平台比如AMT(Amazon mechanical turk), Crowdsflower的出现, 众包提供了一种新的更容易获取标记的方式.不同于要求领域专家标注, 众包将标注任务分配容易访问的非专家, 收集大量的监督信息[5, 6].由于非专家的标注可能犯错, 为了获得高质量的标记, 众包通常将任务分配给多个标注者, 然后融合多个标注结果以估计样本的真实标记.
本文考虑众包环境下的多标记学习, 不同于由代价昂贵的专家标注真实标记, 任务被分配给多个容易获取的非专家标注, 学习目标是从可能犯错的非专家标注中估计样本的真实标记.这一问题的关键在于如何融合非专家标注.以往的众包相关工作主要集中在单标记问题上[7-15], 将多标记任务分解成多个单标记任务, 单标记众包学习方法可以直接应用.但是这种方法忽略了标记的相关性, 而合理地利用标记关系有助于提高学习效果.多标记学习中众包的研究工作还很少, 文献[16-18]考虑通过众包方式收集标记及标记间关系, 估计多个标记间层次结构关系的问题; 文献[19, 20]则分别考虑从标注中估计标记共同出现的概率及标记间条件相关性, 以恢复样本真实标记, 其问题在于这两种局部标记相关性的估计结果很敏感地受到标注数量和质量的影响.
本文则从张量的概念出发, 考虑标注的全局结构关系, 使用张量低秩近似的工具来解决多标记众包学习问题.考虑到以下两点:1)对于多标记任务来说, 真实标记矩阵可能存在低秩结构; 2)在标注者好意标注的前提下, 多个标注者标注同样的任务, 其标注结果会互相接近.因此, 多个非专家的标注结果整体上存在低秩的结构关系.同时考虑真实标记间和多个标注者标注结果间的低秩结构, 我们提出一种基于低秩张量近似的思路.首先, 我们将标注结果组织成三维的张量(样本, 标记, 标注者), 用低秩张量补全的方法对收集到的标注做预处理, 以同时达到两个目的:1)优化已有的标注; 2)补全标注者在其未标注的样本上的标注结果.之后, 我们对优化补全之后的标注融合, 测试了3种不同的融合方法.在真实多标记众包数据集上, 在不同的标注数目情形下, 与多个对比方法的实验结果表明, 通过考虑全局的低秩结构信息, 本文的方法在多种评价指标上都显著优于对比方法.
本文第1节介绍多标记众包学习的相关工作.第2节提出本文的方法.第3节给出实验结果.最后总结全文.
1 相关工作本节中, 我们简要介绍多标记众包学习的相关工作, 主要包括多标记学习、众包学习、低秩张量近似.
● 多标记学习
过去的10多年, 很多方法被提出来, 以处理多标记学习问题.最直接的策略是将多标记任务分解为多个独立的二分类问题, 然后应用单标记的学习方法[21].这个策略忽略了显式或隐含的标记间关系, 而标记间关系被广泛认为有助于提升学习效果.在文本分类任务中, 标签通常按层次结构组织, 这启发了多标记学习中利用标记间外部结构的方法, 如文献[22]考虑标记间树形结构, 文献[23]考虑标记间树形和有向无环图结构.除了显式的标记结构之外, 也有探索利用隐含标记关系的工作, 如标记排序的思路[2, 24], 将多标记任务转化为标记排序问题, 要求各个样本的正标记排在负标记之前; 样本表示增强的思路[25, 26], 使用标记信息构造样本的元特征, 以使样本的表示融合隐式的标记间关系.经典的多标记学习方法要求训练样本具有真实标记, 在实际应用中真实标记是昂贵不易获取的资源.
● 众包学习
随着众包平台如AMT(Amazon mechanical turk), Crowdflower等的出现, 众包成为一种获取监督信息的便捷收集方式.由于众包标注来自可能犯错的非专家, 因此从标注中估计真实标记成为众包学习的重要关注点.以往的工作主要集中在单标记任务上, 通过对标注者的标注能力建模, 在用户标注和真实标记间建立关联, 通过概率图模型的方法同时估计标注者的标注能力和真实标记[8-12, 14, 15].多标记任务方面, 文献[13, 18]收集样本所有可能的标记, 利用标记共同出现的概率以估计标记层次结构关系; 文献[16, 17]通过询问标记间父子关系重构标记层次结构.至于估计样本真实标记, 相关工作主要通过扩展单标记众包学习方法, 加入标记间关系的利用.文献[18]提出一种考虑标记共同出现的概率关系估计真实标记的方法, 文献[19]探索了3种标记关系, 通过将标记分组, 或者学习标记间的条件相关性将多标记问题转化为多分类问题, 以估计样本真实标记.类似于文献[18], 文献[20]也提出了一种利用标记共同出现概率关系的方法.以上工作的标记关系主要集中在标记间局部关系, 其估计质量很敏感地受到标注的数量和质量的影响.本文则从标注整体上存在低秩结构关系来考虑标记相关性.
● 低秩张量近似
在数据科学中, 矩阵是最常见的数据组织形式, 作为矩阵的重要概念, 矩阵的秩刻画了数据的一种全局相似性结构信息.当数据集合可以由其子集线性组合重构时, 矩阵被称为具有低秩结构.文献[27]从理论上证明, 通过将矩阵的数据恢复问题形式化为最小化秩的优化目标, 只需要很少的观测值, 低秩矩阵就可以被高概率地恢复补全.这个工作启发了一系列利用矩阵低秩结构做信息重构/数据近似的工作, 包括各种低秩矩阵补全的算法类工作[28, 29]及推荐系统、图像补全等方面的应用工作[30, 31].但在很多实际应用中, 由于数据收集方式的丰富、数据维度的增长, 使得张量, 也就是多维的矩阵, 成为更自然的数据表示.相比于矩阵, 张量能够保持数据多个维度上更丰富的自然结构信息.尽管矩阵低秩近似的工作很多, 但利用张量的整体结构信息来帮助数据近似并不那么直接, 主要原因在于张量的低秩结构难以直观刻画.为了解决这一问题, 文献[32-34]提出使用张量各个维度展开的矩阵的低秩来近似表达张量的低秩结构, 通过最小化矩阵的秩做张量的低秩近似/补全.此外, 基于张量分解的思路, 比如Tucker张量分解[35]、Parafac张量分解[36]、展开矩阵分解[37]的方式也被尝试用来做张量的近似/补全.到目前为止, 关于张量近似/补全的方法的理论保证仍然是开放式问题, 文献[34]中的实验表明, 其所提的LRTC方法表现更为稳定.我们注意到, 文献[38]将张量补全的方法用于单标记分类任务, 通过在张量上增加一层真实标记层, 首先通过先验知识估计真实标记的初值, 然后利用张量补全的方法补全真实标记层.这个方法的问题在于, 真实标记的质量依赖于估计初值, 而估计初值需要从额外的信息中获取.
本文将多标记任务的所有标注者的标注结果组织成一个三维张量(样本, 标记, 标注者), 考虑到样本的真实标记存在低秩结构, 且多个标注者对同一任务的标注结果相近, 采用文献[34]的想法对张量各维度的展开矩阵做低秩约束, 利用低秩张量近似/补全的方法补全标注张量, 然后使用3种标注融合方法估计样本的真实标记.
2 基于低秩张量矫正的多标记众包方法 2.1 符号表示我们首先说明本文出现的符号表示含义.我们用大写字母表示矩阵, 如X; 用小写字母表示矩阵中的元素, 如xij.矩阵X的Frobenius范数被定义为
在多标记众包问题中, 给定N个样本、L个候选标记、M个标注者, 每个标注者的标注结果可以表示成N×L的矩阵X∈{+1, -1, 0}N×L, 其中, xij=+1(-1)表示第i个样本的第j个标记被标注为正(负)标记, xij=0表示第i个样本的第j个标记没有被标注, 即标注缺失.在众包标记收集方式下, 标注结果通常都不是完整的, 即不是所有的标注者都标注了所有样本的所有标记.我们的学习目标是给定收集的标注结果, 估计样本的真实标记矩阵Z, 其中, zij=0表示第i个样本在j个标记上的结果.
使用张量的数据组织形式, 将M个标注者的标注结果叠起来, 我们得到N×N×L的三维标注张量χ∈{+1, -1, 0}M×N×L, 其中, χtij表示第t个标注者在第i个样本第j个标记上的标注.由于标注结果来自非专家, 与真实标记相比, χ中一方面有缺失的标注, 另一方面含有部分的错误标记.若要估计样本的真实标记, 则需要对标注结果做矫正.考虑到如下的因素:1)相似样本的标记也应该相似, 因此样本集的真实标记矩阵Z可能存在低秩结构; 2)由于多个标注者标注的是同一任务, 在标注者质量可靠的情况下, 多个标注者的标注结果也是相似的, 因此, 标注张量χ整体上应该存在低秩的结构关系.我们提出了一种基于低秩张量补全的思路.首先, 用低秩张量补全的方法对收集到的标注做预处理, 以同时达到两个目的:1)矫正已有的可能会犯错的标注; 2)补全各标注者缺失的标注结果.之后, 我们对矫正补全之后的标注做融合, 尝试了3种标注融合方法, 最终估计样本的真实标注.
2.3 低秩张量矫正我们首先介绍矩阵的低秩补全, 然后基于此给出张量低秩近似的实现.在低秩矩阵补全问题中, 最常用的方法是最小化矩阵秩.由于矩阵的秩最小化是非凸问题, 文献[27]证明了矩阵的迹范数是矩阵秩的最紧的凸闭包, 放松到凸问题, 矩阵补全被形式化为最小化矩阵的迹范数:
$\mathop {\min }\limits_X \parallel X{\parallel _ * }\;\;{\rm{s}}{\rm{.t}}{\rm{.}}\;\;{X_\mathit{\Omega} } = {A_\mathit{\Omega} }$ | (1) |
其中, ||X||*表示目标矩阵X的迹范数, Ω表示观测到的元素的下标集合, A表示观测矩阵.
作为矩阵的高维扩展, 张量的低秩结构不像矩阵可以写出直观的优化目标, 通常的实现都是通过启发式的优化目标设计, 实现对张量低秩的约束.到目前为止, 关于张量补全的各种算法还缺乏类似矩阵低秩恢复的理论保证, 即以某种优化目标, 在何种观测样本复杂度下能够以较高的概率恢复真实的张量.考虑到文献[34]中所提方法SiLRTC(simple low rank tensor completion)简单易实现, 并且其文中的多种实验对比也表明SiLRTC方法表现更为稳定, 本文中我们采用SiLRTC方法作为多标记众包标记标注矫正/补全的方法.
以下简单介绍一下SiLRTC方法.文献[34]定义张量χ的迹范数为
$ \parallel \mathcal{X}{\parallel _ * } = \sum\limits_{l = 1, \ldots , n} {{\alpha _l}\parallel {\mathcal{X}_{(l)}}{\parallel _ * }} {\text{ s}}{\text{.t}}{\text{. }}\sum\limits_{l = 1, \ldots , n} {{\alpha _l}} = 1, {\text{ }}{\alpha _l} \geqslant 0, l = 1, ..., n $ | (2) |
这里, αl为预先设定的参数.类似矩阵补全的优化目标, 张量补全的目标可以被形式化为
$ \mathop {\min }\limits_\mathcal{X} \sum\limits_{l = 1, \ldots , n} {{\alpha _l}\parallel {\mathcal{X}_{(l)}}{\parallel _ * }} \;\;{\text{s}}{\text{.t}}{\text{.}}\;\;{\mathcal{X}_\mathit{\Omega} } = {\mathcal{T}_\mathit{\Omega} } $ | (3) |
由于各个维度展开的矩阵χ(l)并不互相独立, 为了能够分别独立地求解χ(l), 同样数目的矩阵Ml被引入到优化问题中, 上述的优化问题被转化为如下的形式.
$ \mathop {\min }\limits_{\mathcal{X}, {M_l} } \sum\limits_{l = 1, \ldots , n} {{\alpha _l}\parallel {M_l}{\parallel _ * }\; + \;\frac{{{\beta _l}}}{2}||{\mathcal{X}_{(l)}} - {M_l}||_F^2} \;\;{\text{s}}{\text{.t}}{\text{.}}\;\;{\mathcal{X}_\mathit{\Omega} } = {\mathcal{T}_\mathit{\Omega} } $ | (4) |
将优化变量分解成χ, M1, M2, …, Mn共n+1个组, 可以采用分块坐标下降法求解上述优化问题, 优化其中一组变量时固定其他变量.
● 优化χ
固定M1, M2, …, Mn为已知变量, 关于χ的优化问题为
$\mathop {\min }\limits_{\mathcal{X} } \sum\limits_{l = 1, \ldots , n} {\frac{{{\beta _l}}}{2}||{\mathcal{X}_{(l)}} - {M_l}||_F^2} \;\;{\rm{s}}{\rm{.t}}{\rm{.}}\;\;{\mathcal{X}_\mathit{\Omega} } = {\mathcal{T}_\mathit{\Omega} }$ | (5) |
因此, χ存在闭式解:
${\mathcal{X}_{{i_1}, {i_2}, ..., {i_n}}} = \left\{ {\begin{array}{*{20}{l}} {{{\left( {\frac{{\sum\nolimits_i {{\beta _i}fol{d_i}({M_i})} }}{{\sum\nolimits_i {{\beta _i}} }}} \right)}_{{i_1}, {i_2}, ..., {i_n}}}, }&{({i_1}, {i_2}, ..., {i_n}) \notin \mathit{\Omega} } \\ {{\mathcal{T}_{{i_1}, {i_2}, ..., {i_n}}}, }&{({i_1}, {i_2}, ..., {i_n}) \in \mathit{\Omega} } \end{array}} \right.$ | (6) |
● 优化Mi
固定χ, M1, M2, …, Mi-1, Mi+1, …, Mn为已知变量, 关于Mi的优化问题为
$\mathop {\min }\limits_{{M_i} } \frac{{{\beta _i}}}{2}||{M_i} - {\chi _{(i)}}||_F^2 + {\alpha _i}\parallel {M_i}{\parallel _{\; * }}$ | (7) |
上述优化问题存在闭式解[31].最优解的形式为Mi=Dτ(χ(i)), τ=αi/βi.这里, Dτ(X)表示对X的奇异值分解X=UΣVT的收缩算子, 其定义为Dτ(X)=UΣτVT, 其中, Στ=diag(max(σi-τ, 0)).
由于公式(4)为凸优化问题, 并且非光滑项是可以分别独立优化的, 由文献[39]可知, 使用分块坐标下降法可以保证收敛到最优解.
2.4 3种标注融合方法通过使用上面的低秩张量补全方法对标注张量做预处理, 利用标注整体上存在的低秩结构关系作为约束, 我们得到了处理之后的标注结果:1)在每个样本的每个标记上, 我们获得了所有标注者的可能标注值预测; 2)相比原本收集的离散取值为{+1, -1, 0}(分别表示正标记、负标记、无标记)的标注, 处理之后的标注为有符号的实值, 其范围在连续的实数范围内.在本节中, 我们对处理之后的标注结果做融合, 尝试了3种标注融合方法来估计样本的真实标注.
将处理之后的标注张量表示为
1) Signed Voting
不考虑标注的值信息, 只利用标注结果的符号信息.在每个样本的每个标记上, 对其标注结果的符号做投票, 即
${\tilde z_{ij}} = \sum\nolimits_t {sign({{{\tilde \chi }}_{tij}})} /M$ | (8) |
2) Valued Voting
考虑到标注的值可以反映标注者的置信度信息, 比如对比两个标注者t, t', 在同一个样本的同一标记上, 如果
${\tilde z_{ij}} = \sum\nolimits_t {{{{\tilde \chi }}_{tij}}} /M$ | (9) |
3) Entropy Voting
借鉴文献[40]中的无监督集成方法, 在每个标记上, 对每个标注者估计一个基于信息熵的权重, 使用加权投票的方法估计
首先, 对每个标记任务j, 对标注者t, 将其标注结果转化为[0, 1]范围的标注概率:
${\tilde P_{tij}} = {{({{{\tilde \chi }}_{tij}} - \min {{{\tilde \chi }}_{:, :, :}})} \mathord{\left/ {\vphantom {{({{{\tilde \chi }}_{tij}} - \min {{{\tilde \chi }}_{:, :, :}})} {(\max \min {{{\tilde \chi }}_{:, :, :}}{{{\tilde \chi }}_{:, :, :}} - \min {{{\tilde \chi }}_{:, :, :}})}}} \right. } {(\max \min {{{\tilde \chi }}_{:, :, :}}{{{\tilde \chi }}_{:, :, :}} - \min {{{\tilde \chi }}_{:, :, :}})}}$ | (10) |
然后在每个标记j上计算标注者t的标注熵:
$H_j^t = - (1/N)\sum\nolimits_i {{{\tilde P}_{tij}}\log ({{\tilde P}_{tij}}) + (1 - {{\tilde P}_{tij}})\log (1 - {{\tilde P}_{tij}})} $ | (11) |
则标记j上, 标注者t的系数为
$c_j^t = \frac{{1 - \kappa {{\rm{e}}^{H_j^t}}}}{{\sum\nolimits_t {1 - \kappa {{\rm{e}}^{H_j^t}}} }}$ | (12) |
最终标记的预测结果为
${\tilde z_{ij}} = \sum\nolimits_t {(c_j^t{{{\tilde \chi }}_{tij}})} /M$ | (13) |
结合张量补全, 分别使用这3种标记融合方法, 我们得到3种方法:TencSign、TencVal和TencEnt.
注意到本文算法的输出
本文算法的流程图如下所示.
算法. TencSign, TencVal, TencEnt.
输入:M个标注者在N个样本L个标记上的标注张量χ∈{+1, -1, 0}M×N×L, 参数α=[1/3, 1/3, 1/3], β=[0.1, 0.1, 0.1].
输出:真实标记预测矩阵
//基于低秩张量补全的标注矫正
(1) ε=1e-5;
(2) While
(3) Mi=Dτ(χ(i)) for i=1, 2, …, n
(4)
(5) End
//标注融合
(6) TencSign:
(7) TencVal:
(8) TencEnt:
为了获得真实世界的多标记众包数据, 我们在AMT平台上发布了样本和标记数目不同的两个图像标注任务, 随机分配图片给标注者, 要求标注者从候选标记集中给图片标记类别.这两项任务的详细信息如下.
● Image1:Image1数据集包含700张图片, 6个类别{沙漠、沙滩、海、山、树、日出/日落}.平均每张图片有1.24个标记.共有18名标注者, 每人标记的图片数目不少于70张.平均每个人标注了267张图片, 每张图片被标注了7次.共收集到28 878个标注.
● Image2:Image2数据集包含1 695张图片, 16个类别{沙漠、沙滩、海、山、树、日出/日落、船、花、瀑布、建筑、城市、花园、车、人、室内、天空}.平均每张图片有1.80个标记.共有15名标注者标, 每人标记的图片数目不少于100张.平均每个人标注了397张图片, 每张图片被标注了10次.共收集到96 640个标注.
对于每个数据集, 其真实标记由本文作者标注.为了对收集到的众包标记质量有所了解, 我们做了一些初步的标记质量分析.对每个标注者的标注结果, 我们对其标注的样本的标注和真实标记做对比, 用Macro F1衡量其标注准确度.Macro F1是一种常用的多标记分类性能评价指标, 计算方式为每个类别上F1 score的平均, 其取值范围为[0, 1].Macro F1越大, 说明标注结果越接近真实标记.两个数据集上各个标注者的Macro F1结果统计如下:Image1上, 18名标注者的Macro F1值分别为{0.616, 0.6880, 0.758, 0.765, 0.781, 0.785, 0.796, 0.797, 0.801, 0.821, 0.826, 0.829, 0.829, 0.833, 0.835, 0.847, 0.851, 0.911};在Image2上, 15名标注者的Macro F1值分别是{0.597, 0.705, 0.7530, 0.7550, 0.7570, 0.760, 0.761, 0.765, 0.777, 0.777, 0.780, 0.794, 0.779, 0.827, 0.847}.由此我们可以看到, 各个标注者的Macro F1结果各不相同, 但主要分布在[0.700, 0.800]之间, 说明大部分人的标注水平比较接近, 标注质量也比较好.
3.2 对比方法及评价准则我们对比了4种考虑标记间关系的多标记众包方法D-DS、P-DS、ND-DS[19]、MLNB[18].其中, D-DS、P-DS使用标记子集(label powerset)、标记对(label pair)的分组方式将多个标记的组合当做单个类别, 将多标记问题转化为多分类问题, 然后使用单标记众包方法DS来学习; ND-DS从收集到的标记集合中学习标记间的条件相关性以估计样本真实标记; MLNB在单标记众包方法DS中加入标记共同出现的概率信息作为标记关系.此外, 我们还与4种最常用效果最稳定的单标签众包方法MV、KOS[11]、DS[14]、MaxEn[12]做了比较.我们将多标记任务看作多个独立的单标记任务, 在每个标记上分别使用单标记众包方法.对于各个方法的参数, 对比方法的参数设置依照其对应文献的推荐参数设置.对于本文所提方法的参数αl设置为1/3, βl设置为0.1.之后, 我们会详细讨论本文所提方法的参数影响.
多标记学习的性能可以从多个不同的角度评价.为了综合评价各个方法的效果, 本文选用Hamming loss、Macro F1、Average precision和Ranking loss这4种常用的多标记评价指标来衡量学习性能, 其中, Hamming loss、Macro F1为分类指标, Average precision、Ranking loss为排序指标.Macro F1、Average precision(Hamming loss、Ranking loss)的值越大(小), 表明预测结果越接近真实标记.这些指标的具体定义参见文献[4].由于各个众包方法的预测结果是每个类别为正标记的概率, 为了获得分类评价指标, 需对概率预测做阈值划分.以往的众包工作简单地以0.5作为阈值, 而在多标记学习中, 分类结果受划分阈值的影响很大.本文中, 为了获得相对公平的分类结果对比, 在计算各方法的分类指标时, 我们将每个样本的各个标记的预测值做排序, 将预测值最大的k个标记预测为正标记, 其他的预测为负标记, 其中, k为该样本的真实正标记的个数.这里, 为了计算分类指标, 我们用到了真实标记信息.而这在实际应用中是不可行的, 在以后的工作中, 我们将考虑把阈值确定也放到学习过程中.
3.3 实验结果类似于之前的众包工作[9, 28], 我们考察了标注量对众包学习方法效果的影响.我们从收集到的标注集合中随机采样一定比例的标注p, 在这部分标注上学习, 估计数据集的真实标记.以0.1为间隔, 我们测试了p在[0.1, 1]的实验.为了缓解采样对学习算法的随机影响, 我们在每种情形下进行了10次重复实验, 记录下实验均值和标准差.两个数据集的实验结果分别如图 1~图 4所示.
由实验结果可以看出, 对比TencSign、TencVal、TencEnt这3种使用不同融合策略的方法, 在两个数据集上, TencEnt和TencVal都明显优于TencSign; 而在Image1数据集上, TencVal和TencEnt的差别并不明显; 在Image2数据集上, TencEnt略微优于TenVal.由此可以看出, 通过张量补全方法对标注预处理之后, 实值的标注结果包含了每个标注者的置信度信息, 简单地使用标注符号而不考虑标注者置信度, 忽视了各个标注者标注质量的差异.
由图 1~图 4可知, 随着标注数量由少到多增加, 各个方法整体上都呈现出性能提升的趋势; 在标注数量增长到一定程度之后, 学习效果趋于稳定.与对比方法相比, TencEnt和TencVal在各个指标上的结果都显著最优, 并且更快地收敛.在标注数量比较少时, 如p < 40%时, 对比方法与TencEnt、TencVal之间存在明显的差距.这说明为了达到同样好的学习效果, TencEnt和TencVal所需的标注更少.
对比4种多标记众包方法D-DS、P-DS、ND-DS、MLNB, 由图 1和图 3可以看出, MLNB的效果最差.其可能的原因有两个.一个原因是, MLNB提出的目的是学习标记深层结构关系, 主要通过加入标记共同出现的概率来考虑标记关系.对于标记集合巨大并且存在深层标记结构关系的数据, 这种标记关系常见并且容易准确地计算.而对于缺乏这样深层标记结构关系的数据, 这种类型的标记关系并不明显.另一个原因是, MLNB算法的实现中, 对所有的标注者使用了同样的参数, 从而忽略了标注者标注质量的不同.对比D-DS、P-DS、ND-DS, 考虑所有标记间关系的P-DS、ND-DS的效果更优.
对比4种单标记众包方法MV、DS、KOS、MaxEn, 由图 2和图 4可知, 简单的MV效果最差, 而考虑各个标注者在各个样本上的标注能力, 并且采用最优化最坏熵的MaxEn效果最好.对比图 1和图 2、图 3和图 4中的多标记众包方法和单标记众包方法, 我们可以看出, 考虑标记间关系的4种多众包标记方法并不一定优于将多个标记独立学习的单标记众包方法.这是因为这些方法考虑标记间关系时主要集中在标记间的局部关系, 其估计依赖于收集到的标注, 很敏感地受到标注质量和数量的影响.而本文提出的基于低秩张量矫正的方法则从标注整体存在结构关系来同时考虑标记相关性和标注者的相似性, 从而更可靠地估计样本真实标记.
此外, 我们还考察了另外一种情形的标注数量对各种方法学习效果的影响.我们依次增加各个数据集上的标注者数量, 加入其对应的标注结果, 测试各个方法的学习效果.类似前面, 我们记录了10次重复实验的均值和标准差.两个数据集上的实验结果分别见表 1和表 2.加粗的结果表明, 其在配对检验(95%置信度)中显著优于其他结果, 或与最优结果之间无显著性差异.
与前面的实验结果类似, 从表 1、表 2中可以看到, TencVal, TencEnt的结果都显著优于对比方法.而在Image2数据集上, 表 2中TencVal与TencEnt的对比与前面图 3(图 4)的实验对比略有不同.在图 3(图 4)中, TencEnt略优于TencVal, 而在表 2的结果中, TencVal略优于TencEnt.在实际应用中, 推荐使用TencVal、TencEnt方法.如果考虑计算简便性, 可以采用TencVal的融合方法.
3.4 参数讨论在上面的实验中, 本文所提的方法使用了固定参数.本节中, 我们讨论参数对所提方法的影响.由上面的实验结果可知, TencVal、TencEnt明显优于TencSign, 并且TencVal、TencEnt效果差别不大.考虑到TencVal计算简便, 本节中给出TencVal的结果.限于篇幅, 只给出随机采样部分样本情形的结果, 标注者数目变化的结果类似.
首先固定βl=0.1, 我们考察参数α=[α1, α2, α3]/(α1+α2+α3)不同取值的结果.由于α1, α2, α3分别对应标注张量在{样本, 标记, 标注者}这3个维度的相对重要程度, 我们测试了7种极端取值, [α1, α2, α3]={[1, 0, 0], [0, 1, 0], [0, 0, 1], [1, 1, 0], [1, 0, 1], [0, 1, 1], [1, 1, 1]}, 分别对应3个维度的不同重要程度.在Image1、Image2两个数据集上的Macro F1结果如图 5所示.
由图 5可以看出, 在标注比例p=10%的情况下, [α1, α2, α3]=[0, 0, 1]时, 即只考虑标注者维度展开的情形, 学习效果比其他参数设定差很多.而同时考虑多个维度, 包括只考虑2个维度和同时考虑3个维度, 学习效果更鲁棒.因此对于参数α的取值, 可以设为3个维度同等重要, 即α=[1/3, 1/3, 1/3].
固定α=[1/3, 1/3, 1/3], 我们考察参数βl不同取值的结果.由于βl对应优化问题(4)中低秩目标和逼近观测值目标的权衡折中, 取βl=αl/γ, 我们测试了7种γ的取值, γ=[1e-3, 1e-2, …, 1e3].在Image1、Image2两个数据集上的Macro F1结果如图 6所示.
由图 6可以看出, 当γ > 10时, Image1和Image2上的学习性能明显下降; 当γ≤10时, 学习效果比较稳定.也就是说, 参数βl的值不能太小, 否则恢复出来的标注张量会偏离原本的标注太多, 从而影响学习效果.在实际使用中, 参数βl可以设置为0.1~10范围的常数.
4 结束语本文考虑多标记众包学习问题, 将多标记任务分配给多个容易访问的非专家, 收集标注信息, 以便从可能犯错的标注中估计样本的真实标记.以往的单标记众包方法忽略了多标记任务中标记之间的相关性, 而多标记众包方法主要集中在局部的标记关系学习利用上, 其估计依赖于收集到的标注, 很敏感地受到标注质量和数量的影响.本文从标注整体存在低秩结构关系来考虑标记间相关性和标注者的相似性, 提出基于低秩张量矫正的方法, 并提出3种标注融合策略.实验结果表明, 本文所提的方法TencVal、TencEnt在多种标注数量情形下都显著优于对比方法.在后续工作中, 我们将加入对标注收集过程的控制, 设计更有针对性的标注收集机制, 从而以更少的标记代价收集更可靠、更有利于学习的标注.
[1] |
Boutell MR, Luo J, Shen X, Brown CM. Learning multilabel scene classification. Pattern Recognition, 2004, 37(9): 1757-1771.
[doi:10.1016/j.patcog.2004.03.009] |
[2] |
Elisseeff A, Weston J. A kernel method for multi-labelled classification. In: Dietterich TG, Becker S, Ghahramani Z, eds. Proc. of the Advances in Neural Information Processing Systems 14. 2001. 681-687.
|
[3] |
Tsoumakas G, Katakis I, Vlahavas I. Mining Multi-label Data. Oded M, Lior R, eds. Data Mining and Knowledge Discovery Handbook. Berlin: Springer-Verlag, 2010. 667-685.
|
[4] |
Zhang ML, Zhou ZH. A review on multi-label learning algorithms. IEEE Trans. on Knowledge and Data Engineering, 2014, 26(8): 1819-1837.
|
[5] |
Horvitz E. Reflections on challenges and promises of mixedinitiative interaction. AI Magazine, 2007, 28(2): 13-22.
|
[6] |
Weld D, Lin C, Bragg J. Artificial Intelligence and Collective Intelligence. In: Malone T, Bernstein M, eds. Collective Intelligence Handbook. 2015.
|
[7] |
Snow R, O'Connor B, Jurafsky D, Ng A. Cheap and fast-but is it good? Evaluating non-expert annotations for natural language tasks. In: Proc. of the Conf. on Empirical Methods in Natural Language Processing. Honolulu, 2008. 254-263.
|
[8] |
Whitehill J, Ruvolo P, Wu T, Bergsma J, Movellan J. Whose vote should count more: Optimal integration of labels from labelers of unknown expertise. In: Bengio Y, Schuurmans D, Lafferty JD, Williams CKI, Culotta A, ed. Proc. of the Advances in Neural Information Processing Systems 22. 2009. 2035-2043.
|
[9] |
Raykar V, Yu S, Zhao L, Valadez G, Florin C, Bogoni L, Moy L. Learning from crowds. Journal of Machine Learning Research, 2010, 11: 1297-1322.
http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ0232655774/ |
[10] |
Welinder P, Branson S, Belongie S, Perona P. The multidimensional wisdom of crowds. In: Lafferty J, Williams CI, Shawe-Taylor J, Zemel R, Culotta A, eds. Proc. of the Advances in Neural Information Processing Systems 23. 2010. 2024-2432.
|
[11] |
Karger DR, Oh S, Shah D. Iterative learning for reliable crowdsourcing systems. In: Shawe-Taylor J, Zemel RS, Bartlett PL, Pereira FCN, Weinberger KQ, eds. Proc. of the Advances in Neural Information Processing Systems 24. 2011. 1953-1961.
|
[12] |
Zhou D, Basu S, Mao Y, Platt JC. Learning from the wisdom of crowds by minimax entropy. In: Bartlett PL, Pereira FCN, Burges CJC, Bottou L, Weinberger KQ, eds. Proc. of the Advances in Neural Information Processing Systems 25. 2012. 2195-2203.
|
[13] |
Chilton L, Little G, Edge D, Weld D, Landay J. Cascade: Crowdsourcing taxonomy creation. In: Proc. of the SIGCHI Conf. on Human Factors in Computing Systems. 2013. 1999-2008.
|
[14] |
Dawid AP, Skene AM. Maximum likeihood estimation of observer error-rates using the em algorithm. Journal of the Royal Statistical Society, 1979, 28(1): 20-28.
|
[15] |
Sheng VS, Provost FJ, Ipeirotis PG. Get another label? Improving data quality and data mining using multiple, noisy labelers. In: Proc. of the 14th ACM SIGKDD Int'l Conf. on Knowledge Discovery and Data Mining. Las Vegas, 2008. 614-622.
|
[16] |
Sun Y, Singla A, Fox D, Krause A. Building hierarchies of concepts via crowdsourcing. In: Proc. of the 24th Int'l Joint Conf. on Artificial Intelligence. 2015. 844-853.
|
[17] |
Duan L, Oyama S, Kurihara M, Sato H. Crowdsourced semantic matching of multi-label annotations. In: Proc. of the 24th Int'l Joint Conf. on Artificial Intelligence. 2015. 3483-3489.
|
[18] |
Bragg J, Mausam, Weld DS. Crowdsourcing multi-label classification for taxonomy creation. In: Proc. of the 1st AAAI Conf. on Human Computation and Crowdsourcing. 2013.
|
[19] |
Duan L, Oyama S, Sato H, Kurihara M. Separate or joint? Estimation of multiple labels from crowdsourced annotations. Expert Systems with Applications, 2014, 41(13): 5723-5732.
[doi:10.1016/j.eswa.2014.03.048] |
[20] |
Tam NT, Viet HH, Hung NQV, Weidlich M, Yin H, Zhou X. Multi-label answer aggregation for crowdsourcing. Technical Report, 2016.
|
[21] |
Comite FD, Gilleron R, Tommasi M. Learning multi-label altenating decision tree from texts and data. In: Proc. of the 3rd Int'l Conf. on Machine Learning and Data Mining in Pattern Recognition. Leipzig, 2003. 35-49.
|
[22] |
Cesa-Bianchi N, Gentile C, Zaniboni L. Hierarchical classification: Combining bayes with SVM. In: Proc. of the 23rd Int'l Conf. on Machine Learning. Pittsburgh, 2006. 177-184.
|
[23] |
Bi W, Kwok J. Multi-label classification on tree- and dagstructured hierarchies. In: Proc. of the 28th Int'l Conf. on Machine Learning. Bellevue, 2011. 17-24.
|
[24] |
Schapire RE, Singer Y. BoosTexter: A boosting-based system for text categorization. Machine Learning, 2000, 39(2-3): 135-168.
http://d.old.wanfangdata.com.cn/NSTLQK/NSTL_QKJJ021532080/ |
[25] |
Yang Y, Gopal S. Multilabel classification with meta-level features in a learning-to-rank framework. Machine Learning, 2012, 88(1-2): 47-68.
[doi:10.1007/s10994-011-5270-7] |
[26] |
Zhang ML. Lift: Multi-label learning with label-specific features. In: Proc. of the 22nd Int'l Joint Conf. on Artificial Intelligence. Barcelona, 2011. 1609-1614.
|
[27] |
Candès EJ, Recht B. Exact matrix completion via convex optimization. In: Proc. of the Foundations of Computational Mathematics. 2009. 717-772.
|
[28] |
Candès EJ, Tao T. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. on Information Theory, 2010, 56(5): 2053-2080.
|
[29] |
Recht B. A simpler approach to matrix completion. Journal of Machine Learning Research, 2011, 12: 3413-3430.
http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_0910.0651 |
[30] |
Rennie J, Srebro N. Fast maximum margin matrix factorization for collaborative prediction. In: Proc. of the 22nd Int'l Conf. on Machine Learning (ICML). 2005. 713-719.
|
[31] |
Ma S, Goldfarb D, Chen L. Fixed point and bregman iterative methods for matrix rank minimization. Mathematical Programming, 2009, 128(1): 321-353.
http://d.old.wanfangdata.com.cn/OAPaper/oai_arXiv.org_0905.1643 |
[32] |
Gandy S, Recht B, Yamada I. Tensor completion and low-nrank tensor recovery via convex optimization. Inverse Problem, 2011, 27(2): Article No.025010.
|
[33] |
Signoretto M, Lathauwer LD, Suykens JAK. Nuclear norms for tensors and their use for convex multilinear estimation. In: Proc. of the Submitted to Linear Algebra and Its Applications. 2010.
|
[34] |
Liu J, Musialski P, Wonka P, Ye JP. Tensor completion for estimating missing values in visual data. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2013, 35(1): 208-220.
[doi:10.1109/TPAMI.2012.39] |
[35] |
Tucker LR. Some mathematical notes on three-mode factor analysis. Psychometrika, 1966, 31: 279-311.
[doi:10.1007/BF02289464] |
[36] |
Harshman RA. Foundations of the parafac procedure: Models and conditions for an "explanatory" multi-modal factor analysis. UCLA Working Papers in Phonetics, 1970, 16: 1-84.
|
[37] |
Xu Y, Hao R, Yin W, Su Z. Parallel matrix factorization for low-rank tensor completion. In: Proc. of the CoRR. 2013.
|
[38] |
Zhou Y, He J. Crowdsourcing via tensor augmentation and completion. In: Proc. of the 25th Int'l Joint Conf. on Artificial Intelligence. New York, 2016. 2435-2441.
|
[39] |
Tseng P. Convergence of block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory Application, 2001, 109: 475-494.
[doi:10.1023/A:1017501703105] |
[40] |
Zhou Y, Ying L, He J. MultiC2: An optimization framework for learning from task and worker dual heterogeneity. In: Proc. of the 2017 SIAM Int'l Conf. on Data Mining. Houston, 2017. 579-587.
|