众包学习模型研究

吴琼

摘要：近年来众包学习在机器学习和计算机视觉方面备受关注，但是存在不可靠标注者导致标注标签包含大量噪声。本文提出一种低秩矩阵填充算法（LRMC）来捕获标注者之间潜在相关性，并去除存在于识别标注之间的特定噪声。LRMC通过标签的低秩结构来利用存在于标签中潜在的相关信息，其中还可以获得标注者与问题的潜在的特征向量。实验结果表明，LRMC不但提高了众包学习的标注精度，并且与现有算法相比，在优化时间上也存在相应优势。

关键词：低秩近似；矩阵填充；众包学习

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2019）08-0145-03

开放科学（资源服务）标识码（OSID）：

1 引言

近年來，在机器学习和计算机视觉方面众包学习收集标签的高效性备受关注。

众包学习提供了一种新的工作方式，雇主发布任务，自由工作者帮助雇主完成任务，最大化地利用了自由工作者的智慧。然而，不同的专家或标注者的出发点不同，导致收集到的标签包含大量噪声，不利于进一步的结果分析。提高完成任务的质量，是一项挑战性的工作。如何对标注者的精度进行有效评估，提高众包学习结果质量是众包研究中面临的重要问题。

众包学习研究一般假设每个标签是潜在不可靠的，且噪声在所有标注者之间随机出现。事实上，大多数噪声标签仅出现在不可靠的标注者当中，而不是所有的标注者。此外，传统的众包学习方法通常使用生成模型单独处理每个标注者产生的标签，却忽略标注者之间的相关性。

本文提出一种矩阵填充方法：低秩矩阵填充算法（Low Rank Matrix Completion，LRMC）该方法从一个新的角度对标签进行优化。LRMC通过标签的低秩结构来利用存在于标签中潜在的相关信息，其中还可以获得标注者与问题的潜在的特征向量。更重要的是，该方法将众包学习任务中的标签噪声定义为标注噪声，即不可靠的标注者使得观察到的标签存在特定偏差，可以通过[l2，1]范数进行刻画。最后，实验结果表明，LRMC不但提高了众包学习的标注精度，并且与现有算法相比，在优化时间上也存在相应优势。

2 众包学习面临的挑战

众包学习是一种高效和小成本的方式来收集诸多应用领域中的标签数据，比如计算机视觉和自然语言处理领域[1]。诸如Amazon Mechanical Turk[2]和Crowd Flower[3]等平台提供了众包服务，发布者可以在其中发布相关任务，并可从在线的标注者当中收集相应任务标签。Amazon Mechanical Turk中的众包学习任务包括标记图像，评估搜索结果以及标记机器学习数据。众包学习的优点是可以用较低的成本下在短时间内获得大量的标签。尽管在效率以及成本方面具有一定优势，但观察到的标签质量可能较低，这是因为众包学习标注者通常并非是该领域的专家且有时不可靠。传统上，研究人员采用冗余机制来保证标注的质量，也就是将各个问题分配给不同的标注者，然后在对标签进行聚合。因此，众包学习存在的第一个问题是：如何从这些不可靠的标注者提供的噪声标签中推断真正的标签。第二个问题是：现有工作中一般对所有标注者根据生成模型处理单独建模，从而忽略了标注者之间的相关性[7]。即使在实际中从统计模型中得到令人满意的性能，标注结果可能也不是局部或者全局最优的。

近几年，低秩近似方法[4-6]给标注任务带来处理问题的新视角，同时此类方法为提升标注准确率提供了可能。本文提出一种有效的低秩矩阵填充方法从带噪声的标签中推断真正的标签。观察到的标签矩阵包含标注者对众包学习问题给出的对应标签，并且将观察到的矩阵分解为低秩分量和特定的标注噪声，如图1所示。观察到的标签矩阵被分解为两部分：无恶意噪声标签和噪声。注释器之间的基础相关性被指定为具有低秩结构的精化标签。假设存在一部分恶意标注者，他们往往提供一些随意甚至错误的标注结果，这些噪声具有稀疏和噪声值任意的特点，满足[l2，1]的范数约束。当标注者的恶意噪声被去除后，可以认为标签是有大部分可靠标注者提供的。标签矩阵的潜在低秩结构说明由大部分可靠标注者提供的标签之间存在着潜在相关信息。此外，低秩成分可以表示成无恶意噪声的低秩标签，这极大简化了后续的标签聚合过程。

本文的主要贡献如下：

1） 利用低秩模型为众包任务提供了一个新的视角，低秩成分可以挖掘不同标注者之间的潜在关系并且抽取出对应标注者带来的噪声。定义标注者噪声为稀疏噪声，即不可靠的标注者会导致任意的噪声偏差，可以被形式化为[l2，1]范数。在标注者之间的关系可以被形式化为低秩结构，这个结构可以充分描述不同标签之间的关系并简化后续的处理过程。

2） 为众包学习任务提出一种新的低秩流形方法，即低秩矩阵填充算法（LRMC），该算法可以对提出的低秩模型有效的求解，根据黎曼梯度算法获得最终的标签。

3 低秩矩阵填充模型

为了形式化问题，假设众包任务中有m个标注者，n个问题，其中观测到的标记矩阵为[m× n]的观测矩阵Z，其中[zij]表示由标记者j给问题i做的标记。第i行[Zi：∈R1×n]表示所有从标记者i得到的n个标记。

考虑到标记可能会丢失，[zij=0]表示标记者i对问题j没有任务标注，并且Z中的非零元素表示已知的标记。令Ω为观测矩阵Z的标识，以及[PΩ（?） ]表示矩阵Z的映射，并满足：

[PΩ（Z）ij=zij， （i，j）∈Ω 0 ， otherwise] （3-1）

令X为低秩矩阵，表示从不同标记者中标记的数据中抽取的标签，E是和标记者有关的稀疏噪声。观测的标记Z可以表示为X和E之和，即，

[minX，EX*+λE2，1 s.t. PΩZ=PΩ（X+E）] （3-2）

其中[λ>0]是给定的正则参数，[PΩ（?）]是线性算子，对观测到的数据进行标识，核范数为[?*]，它是秩函数的松弛，用来刻画低秩标记矩阵X并且表示了不同标记者对同问题的标注的线性关系。[l2，1]范数定义为[?2，1]正则项，噪声E表示为标注者间的特殊噪声。为了导出标记之间的低秩信息，问题（3-2）需要对秩最小化问题进行求解，由于秩函数是非凸函数并且是NP问题，本章算法用核范数[?*]对问题进行松弛，它是对凸函数的近似。和标注者相关的噪声可以被认为是行相关的，由[l2，1]范数进行刻画，其中[Zi：∈R1×n]表示从第i个标注者得到的第n个标记。通过定义[l2，1]范数，[?2，1]刻画了行相关的稀疏噪声，如图1所示，也就是说某些行是包含噪声的，而其他行没有噪声。此外，由于标注的初衷不同，一些噪声可能是任意大的，因此最小化[l2，1]范数也导致E的列为零，即该范数对每个问题的噪声尽可能地进行约减。至此，通过分析观测到的标记矩阵中的低秩结构，已经推断出众包模型（3-2）。

4 实验

为了更好地理解LRMC在不同参数下的性能，首先在人工数据集上进行实验，对比LRMC在不同问题规模下得到的不同结果。利用二元投票眾包对算法进行测试，二元投票法广泛应用于生活中的各种场景，例如，给两个选项，投票者只能给出是或者否。

通过实验生成三个众包任务，问题规模分别为100，500以及1000。5和20个标注者对每个问题进行标注，每个问题只有两个选项：[{1，+1}]，并且真是的标签依照概率0.5的方式从伯努利分布[{1，+1}]中进行采样。模拟了两种不同类型的标注者：可靠的标注者和不可靠的标注者。标注者的准确率随机地从0.8和1中选取。而不可靠的标注者采用不同的策略，他们生成带噪声的标签[8]。模拟两种不可靠的标注者：（a）对每个问题随机的标注1或者[-1]，随机选择每个选项的概率为0.5。（b）估计对每个标注进行错误的逆向标注。问题的标注者变化幅度从5到35，对每个标签矩阵采用十折交叉验证，并取平均。

观察到标签的质量对聚合的准确率至关重要，但是在实际应用中，观察到的标签经常缺失或者带有噪声。为了测试噪声带来的影响，通过改变缺失和噪声的程度，采用三个不同规模的矩阵进行测试，如图2。在图2（a）和2（c）中，不可靠的标注者固定为30%，期望在100个标注者当中存在30个不可靠的标注者，图2（a）描述了在每个问题下不同数目的标注者带来的误差对于三个不同规模的标签矩阵，误差率随着问题标注者的增多而减小，这是因为每个问题由更多的标注者进行标注，所以标注更可靠。和500个问题以及1000个问题比较时，即使标注者减少时，LRMC算法可以得到针对200个问题规模较高的准准确率。这三个标记矩阵误差的间距逐渐缩小至0.02，在同等条件下图2（a）展示了由ROLA算法得到了不同时间对比。很明显，随着标签矩阵规模的增长，时间也随着增长，但是和每个问题标注者的数目无关，因此对所有三个矩阵而言本章算法比较稳定。

固定不可靠标注者数目变动噪声程度，得到LRMC算法的性能如图2（b）和2（d）所示。每个问题的标注者数目设置为30。很明显，由LRMC算法得到的准确率随着不可靠标注者的增多而减少。LRMC采用[l2，1]范数来对标注矩阵中的稀疏的噪声项进行规范。当不可靠标注者的数目增多时，和标注者相关的噪声矩阵不再是稀疏矩阵，因此对LRMC算法造成一定的影响。图2（d）展示了对1000个标签任务的LRMC算法运行时间，从中可看出执行该任务的时间比500个标签任务快30%，以及比200个标签任务的快了60%。

5 总结

本文提出一种新的基于矩阵流形的优化算法，即LRMC算法（Low Rank Matrix Completion），从一种全新的角度推理学习众包标注，快速得到精确的众包标注结果。将标签噪声定义为标注者特定的稀疏噪声，可以用[l2，1]范数进行约束。具体来说，LRMC算法利用众包收集的标签矩阵的所特有的潜在低秩结构，基于这一低秩学习模型进而去除标注者特定的噪声。当标注者的恶意噪声被去除后，可以认为剩余的标签是有大部分可靠标注者提供的。标签矩阵的潜在低秩结构说明由大部分可靠标注者提供的标签之间存在着潜在相关信息。换句话说，这种无恶意噪声的标签矩阵代表了大部分可靠标注者提供标注结果，因此可以认为这些标签是趋向于一致性的，即大部分可靠的标注者提供的标签更接近于真实的结果。因此，基于这种无恶意噪声的标签矩阵的推理结果则会使得众包学习更加精确有效。

参考文献：

[1] Li Q， Wang Z， Li G， et al. Learning Robust Low-Rank Approximation for Crowdsourcing on Riemannian Manifold[J]. Procedia Computer Science， 2017， 108： 285-294.

[2] Kees J， Berry C， Burton S， et al. An analysis of data quality： Professional panels， student subject pools， and Amazon's Mechanical Turk[J]. Journal of Advertising， 2017， 46（1）： 141-155.

[3] Mubarak H， Darwish K. Demographic surveys of arab annotators on crowdflower[C]//Weaving Relations of Trust in Crowd Work： Transparency and Reputation across Platforms Workshop. 2016.

[4] Shen Y， Wen Z， Zhang Y. Augmented Lagrangian alternating direction method for matrix separation based on low-rank factorization[J]. Optimization Methods and Software， 2014， 29（2）： 239-263.

[5] Zhang Y， Shi D， Gao J， et al. Low-rank-sparse subspace representation for robust regression[C]//Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition. 2017： 7445-7454.

[6] Hu E L， Kwok J T. Scalable nonparametric low-rank kernel learning using block coordinate descent[J]. IEEE transactions on neural networks and learning systems， 2015， 26（9）： 1927-1938.

[7] Mnih A， Salakhutdinov R R. Probabilistic matrix factorization[C]//Advances in neural information processing systems. 2008： 1257-1264.

[8] Vuurens J， de Vries A P， Eickhoff C. How much spam can you take？ an analysis of crowdsourcing results to increase accuracy[C]//Proc. ACM SIGIR Workshop on Crowdsourcing for Information Retrieval （CIR11）. 2011： 21-26.

【通联编辑：梁书】