吳瓊

摘要：近年來眾包學習在機器學習和計算機視覺方面?zhèn)涫荜P注，但是存在不可靠標注者導致標注標簽包含大量噪聲。本文提出一種低秩矩陣填充算法（LRMC）來捕獲標注者之間潛在相關性，并去除存在于識別標注之間的特定噪聲。LRMC通過標簽的低秩結構來利用存在于標簽中潛在的相關信息，其中還可以獲得標注者與問題的潛在的特征向量。實驗結果表明，LRMC不但提高了眾包學習的標注精度，并且與現有算法相比，在優(yōu)化時間上也存在相應優(yōu)勢。

關鍵詞：低秩近似；矩陣填充；眾包學習

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2019）08-0145-03

開放科學（資源服務）標識碼（OSID）：

1 引言

近年來，在機器學習和計算機視覺方面眾包學習收集標簽的高效性備受關注。

眾包學習提供了一種新的工作方式，雇主發(fā)布任務，自由工作者幫助雇主完成任務，最大化地利用了自由工作者的智慧。然而，不同的專家或標注者的出發(fā)點不同，導致收集到的標簽包含大量噪聲，不利于進一步的結果分析。提高完成任務的質量，是一項挑戰(zhàn)性的工作。如何對標注者的精度進行有效評估，提高眾包學習結果質量是眾包研究中面臨的重要問題。

眾包學習研究一般假設每個標簽是潛在不可靠的，且噪聲在所有標注者之間隨機出現。事實上，大多數噪聲標簽僅出現在不可靠的標注者當中，而不是所有的標注者。此外，傳統的眾包學習方法通常使用生成模型單獨處理每個標注者產生的標簽，卻忽略標注者之間的相關性。

本文提出一種矩陣填充方法：低秩矩陣填充算法（Low Rank Matrix Completion，LRMC）該方法從一個新的角度對標簽進行優(yōu)化。LRMC通過標簽的低秩結構來利用存在于標簽中潛在的相關信息，其中還可以獲得標注者與問題的潛在的特征向量。更重要的是，該方法將眾包學習任務中的標簽噪聲定義為標注噪聲，即不可靠的標注者使得觀察到的標簽存在特定偏差，可以通過[l2，1]范數進行刻畫。最后，實驗結果表明，LRMC不但提高了眾包學習的標注精度，并且與現有算法相比，在優(yōu)化時間上也存在相應優(yōu)勢。

2 眾包學習面臨的挑戰(zhàn)

眾包學習是一種高效和小成本的方式來收集諸多應用領域中的標簽數據，比如計算機視覺和自然語言處理領域[1]。諸如Amazon Mechanical Turk[2]和Crowd Flower[3]等平臺提供了眾包服務，發(fā)布者可以在其中發(fā)布相關任務，并可從在線的標注者當中收集相應任務標簽。Amazon Mechanical Turk中的眾包學習任務包括標記圖像，評估搜索結果以及標記機器學習數據。眾包學習的優(yōu)點是可以用較低的成本下在短時間內獲得大量的標簽。盡管在效率以及成本方面具有一定優(yōu)勢，但觀察到的標簽質量可能較低，這是因為眾包學習標注者通常并非是該領域的專家且有時不可靠。傳統上，研究人員采用冗余機制來保證標注的質量，也就是將各個問題分配給不同的標注者，然后在對標簽進行聚合。因此，眾包學習存在的第一個問題是：如何從這些不可靠的標注者提供的噪聲標簽中推斷真正的標簽。第二個問題是：現有工作中一般對所有標注者根據生成模型處理單獨建模，從而忽略了標注者之間的相關性[7]。即使在實際中從統計模型中得到令人滿意的性能，標注結果可能也不是局部或者全局最優(yōu)的。

近幾年，低秩近似方法[4-6]給標注任務帶來處理問題的新視角，同時此類方法為提升標注準確率提供了可能。本文提出一種有效的低秩矩陣填充方法從帶噪聲的標簽中推斷真正的標簽。觀察到的標簽矩陣包含標注者對眾包學習問題給出的對應標簽，并且將觀察到的矩陣分解為低秩分量和特定的標注噪聲，如圖1所示。觀察到的標簽矩陣被分解為兩部分：無惡意噪聲標簽和噪聲。注釋器之間的基礎相關性被指定為具有低秩結構的精化標簽。假設存在一部分惡意標注者，他們往往提供一些隨意甚至錯誤的標注結果，這些噪聲具有稀疏和噪聲值任意的特點，滿足[l2，1]的范數約束。當標注者的惡意噪聲被去除后，可以認為標簽是有大部分可靠標注者提供的。標簽矩陣的潛在低秩結構說明由大部分可靠標注者提供的標簽之間存在著潛在相關信息。此外，低秩成分可以表示成無惡意噪聲的低秩標簽，這極大簡化了后續(xù)的標簽聚合過程。

本文的主要貢獻如下：

1） 利用低秩模型為眾包任務提供了一個新的視角，低秩成分可以挖掘不同標注者之間的潛在關系并且抽取出對應標注者帶來的噪聲。定義標注者噪聲為稀疏噪聲，即不可靠的標注者會導致任意的噪聲偏差，可以被形式化為[l2，1]范數。在標注者之間的關系可以被形式化為低秩結構，這個結構可以充分描述不同標簽之間的關系并簡化后續(xù)的處理過程。

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在不同問題規(guī)模下得到的不同結果。利用二元投票眾包對算法進行測試，二元投票法廣泛應用于生活中的各種場景，例如，給兩個選項，投票者只能給出是或者否。

通過實驗生成三個眾包任務，問題規(guī)模分別為100，500以及1000。5和20個標注者對每個問題進行標注，每個問題只有兩個選項：[{1，+1}]，并且真是的標簽依照概率0.5的方式從伯努利分布[{1，+1}]中進行采樣。模擬了兩種不同類型的標注者：可靠的標注者和不可靠的標注者。標注者的準確率隨機地從0.8和1中選取。而不可靠的標注者采用不同的策略，他們生成帶噪聲的標簽[8]。模擬兩種不可靠的標注者：（a）對每個問題隨機的標注1或者[-1]，隨機選擇每個選項的概率為0.5。（b）估計對每個標注進行錯誤的逆向標注。問題的標注者變化幅度從5到35，對每個標簽矩陣采用十折交叉驗證，并取平均。

觀察到標簽的質量對聚合的準確率至關重要，但是在實際應用中，觀察到的標簽經常缺失或者帶有噪聲。為了測試噪聲帶來的影響，通過改變缺失和噪聲的程度，采用三個不同規(guī)模的矩陣進行測試，如圖2。在圖2（a）和2（c）中，不可靠的標注者固定為30%，期望在100個標注者當中存在30個不可靠的標注者，圖2（a）描述了在每個問題下不同數目的標注者帶來的誤差對于三個不同規(guī)模的標簽矩陣，誤差率隨著問題標注者的增多而減小，這是因為每個問題由更多的標注者進行標注，所以標注更可靠。和500個問題以及1000個問題比較時，即使標注者減少時，LRMC算法可以得到針對200個問題規(guī)模較高的準準確率。這三個標記矩陣誤差的間距逐漸縮小至0.02，在同等條件下圖2（a）展示了由ROLA算法得到了不同時間對比。很明顯，隨著標簽矩陣規(guī)模的增長，時間也隨著增長，但是和每個問題標注者的數目無關，因此對所有三個矩陣而言本章算法比較穩(wěn)定。

固定不可靠標注者數目變動噪聲程度，得到LRMC算法的性能如圖2（b）和2（d）所示。每個問題的標注者數目設置為30。很明顯，由LRMC算法得到的準確率隨著不可靠標注者的增多而減少。LRMC采用[l2，1]范數來對標注矩陣中的稀疏的噪聲項進行規(guī)范。當不可靠標注者的數目增多時，和標注者相關的噪聲矩陣不再是稀疏矩陣，因此對LRMC算法造成一定的影響。圖2（d）展示了對1000個標簽任務的LRMC算法運行時間，從中可看出執(zhí)行該任務的時間比500個標簽任務快30%，以及比200個標簽任務的快了60%。

5 總結

本文提出一種新的基于矩陣流形的優(yōu)化算法，即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.

【通聯編輯：梁書】