一種結合眾包的排序學習算法

王小平 奚凌然

(同濟大學電子與信息工程學院 上海 200092)

一種結合眾包的排序學習算法

王小平 奚凌然

(同濟大學電子與信息工程學院 上海 200092)

針對有監督排序學習所需帶標記訓練數據集不易獲得的情況，引入眾包這種新型大眾網絡聚集模式來完成標注工作，為解決排序學習所需大量訓練數據集標注工作耗時耗力的難題提供了新的思路。首先介紹了眾包標注方法，著重提出兩種個人分類器模型來解決眾包結果質量控制問題，同時考慮標注者能力和眾包任務的難度這兩個影響眾包質量的因素。再基于得到的訓練集使用RankingSVM進行排序學習并在微軟OHSUMED數據集上衡量了該方法在NDCG@n評價準則下的性能。實驗結果表明該眾包標注方法能夠達到95%以上的正確率，所得排序模型的性能基本和RankingSVM算法持平，從而驗證了眾包應用于排序學習的可行性和優越性。

排序學習 眾包 眾包質量控制 排序支持向量機

0 引 言

在當今大數據時代，搜索引擎是人們獲取所需信息的重要手段，搜索引擎經過信息爬取、索引、搜索結果排序這幾步工作最終將結果返回給用戶，在這個過程中搜索結果的排序技術是結果處理的核心技術，其排序算法的性能在很大程度上影響了整個搜索引擎的效率和用戶體驗。傳統的排序模型使用人工擬合的方式處理各種對排序產生影響的因子，但隨著互聯網的飛速發展，一方面排序影響因子的數量飛速增加，另一方面用戶對更加精準排序結果的需求大大提高，這兩方面原因促使基于機器學習的排序方法得到了業界的重視，排序學習LTR(Learning to Rank)就是這種使用機器學習的方法進行排序模型訓練的新技術。作為一種監督學習方法，排序學習依賴大量有標記訓練數據集，而訓練數據集的標注質量、數據量大小和多樣性都會對最終所得排序模型的效果產生重要的影響。若標注質量差會對排序結果造成較大的偏差，而數據量大小和多樣性也會影響排序模型的泛化性能。因此，用于訓練目的的數據集標注工作是制約排序學習應用效果的關鍵問題。而傳統的訓練數據集處理方式是依靠專業團隊人工標注，耗時耗力，且沒有充分利用查詢結果之間的相關性，故LTR所需訓練數據集的標注工作不僅關系到效率問題，而且影響到學習模型的性能。

眾包最早由美國的Howe Jeff于2006年在《連線》雜志上提出。Howe Jeff對眾包的定義為：一個公司或機構把過去由員工執行的工作任務以自由自愿的形式外包給非特定大眾網絡的做法[1]，即眾包是一種新型的大眾網絡聚集模式，眾包項目的發起者能夠以向廣大互聯網用戶公開招標的方式將大規模眾包任務分包并發給每一個眾包工作者去完成。眾包的優點是能夠利用大眾智慧去完成計算機算法難以勝任的大規模工作。眾包從其被提出開始在許多領域都得到了學界和業界廣泛的關注和研究，這些領域包括人機交互[2-3]、數據庫[4-5]、機器學習和人工智能[6]、信息檢索[7]等。眾包工作流如圖1所示，一個眾包任務涉及眾包任務發布者、眾包工作者、眾包平臺三種角色，眾包任務發布者完成任務設計并在平臺上發布任務，眾包工作者在平臺上接受并完成眾包任務，而眾包平臺則負責將所有眾包工作成果整合并返還給眾包任務發布者。眾包平臺的關鍵作用之一是采取手段對眾包工作質量進行控制，發現并過濾不良工作者的工作成果以盡量提高最終眾包結果的質量。眾包為LTR所需大量訓練數據的標注工作提供了新的解決思路。

圖1 眾包工作流程示意圖

本文提出一種結合眾包的排序學習方法，利用眾包解決訓練數據的標注難題。

1 基于Pairwise的排序學習模型RankingSVM

LTR使用機器學習的方法基于有標注訓練數據集學習得到一個排序模型，并用該排序模型計算某查詢下所有結果文檔和該查詢keyword之間的關聯程度，稱該關聯程度為排序分數，最后以排序分數為依據將所有查詢結果文檔降序排列。根據不同的輸入表示以及損失函數，LTR可分為基于Pointwise、基于Pairwise和基于Listwise三類模型方法：

(1) Pointwise方法單獨針對每一個查詢結果文檔進行訓練，將某查詢下的每一個結果文檔的特征和標注值作為訓練樣本。基于Pointwise的LTR算法有Prank[8]、SubsetRegression[9]等，這類LTR算法的缺點是忽視了樣本間蘊涵的偏序關系，割裂了某查詢下的所有結果文檔之間并將其視為獨立個體進行訓練，其得到的排序模型在實際應用中性能較低。

(2) Pairwise方法針對Pointwise方法的不足考慮了某查詢下所有結果文檔之間的偏序關系，將其中具有不同相關度的兩個文檔組成“文檔對”的形式作為訓練樣本。在訓練數據集中標注出每一對“文檔對”之間相關度偏序關系，該偏序關系取值只可能為“大于”或者“小于”，從而巧妙地將問題轉化為分類問題，可用分類的機器學習工具解決，代表算法有RankingSVM[10]和RankNet[11]。

(3) Listwise方法理想化地以某查詢所對應的所有結果文檔作為訓練樣本，這樣做的好處是能夠公平地對待每一個結果文檔，理論上排序性能更好。但在實際環境中由于文檔特征值分布的稀疏性易產生某一特征缺失的情況，對排序模型的性能造成影響。代表方法有ListNetp[12]、SVMMAP[13]等。

綜上，本文選擇Pairwise模型進行排序學習研究。基于Pairwise的排序學習過程包含四個步驟：訓練數據標注、文檔特征抽取、排序模型訓練和文檔排序[6]。其中文檔特征抽取步驟將所有文檔樣本表示成數值化的特征向量。訓練數據集標注步驟將所有待標注樣本表示為如下三元組格式：，其中qid是查詢號，charactors是文檔特征向量，一般具有較高維度，mark是相關度標注結果，可以分為多個相關性等級，例如{0,1,2,3}四個等級。同理測試集也要表示為相同的三元組，測試集中的mark值由基于訓練集得到的排序模型計算而出，最終將查詢結果按照所得排序模型計算的排序分數降序排列返回給用戶即完成整個LTR過程。

RankingSVM是一種基于Pairwise模型的排序學習算法[10]。它將排序問題轉化為二元分類問題，應用支持向量機模型進行訓練學習得到分類器模型[14]。在查詢集合Q中的某查詢Qi對應Ni個查詢結果文檔{Di1,Di2,…,DiNi}，其中，每個查詢結果文檔的相關度為Ri，利用兩個結果文檔之間相關度存在的偏序關系，即對于x∈{1,2,…,Ni}，y∈{1,2,…,Ni}，構造訓練樣本對S={Dix, Diy, Ri}。具體而言，若Rix>Riy，則得到一個正相關樣本S1={Dix, Diy, 1}，反之，則得到一個負相關樣本對S2={Dix,Diy, -1}。通過該算法可以獲得一個學習模型f，使得對訓練集的任意查詢Qi，若其對應的兩個結果文檔相關度滿足Rix>Riy，則f(Dix)>f(Diy)。

考慮到RankingSVM目標函數為求線性函數f使得總的錯誤偏序對數量最少，基于支持向量機的分類器優化模型可以用下列二次規劃表示為：

(1)

s.t. ?(x,y)∈Pi:yixy≥1-ξi

(2)

式中, Pi為查詢Qi中所有偏序關系對構成的集合，ζ為松弛因子，C為懲罰參數，w為特征權向量，M為總偏序對數目，yixy為縮放處理后取值1或者-1。求解上述問題的最優解即最優特征權向量w，從而得到分類器模型f。然后根據得到的分類器模型，即可計算每個查詢結果的排序分數，最后按得分大小對文檔集合進行排序。

2 眾包在訓練集標注中的應用

眾包的出現和發展為大規模標注工作提供了新的解決方案，它利用廣大大眾智慧“眾人拾柴火焰高”，特別適合于人工完成并且僅依靠計算機很難完成的工作。但同時眾包也有缺點，即眾包工作的質量難以控制。相比于傳統的專家團隊標注模式，眾包工作者的工作能力和工作態度是未知的，在實際眾包應用中可能出現眾包工作結果質量低下的情況。本文研究眾包在LTR所需訓練數據集標注中的應用，重點關注眾包質量控制問題，即通過質量控制手段發現并過濾不良標注結果，提高整體標注質量。

2.1 眾包質量控制方法概述

目前領域內學者已經針對眾包質量控制方法進行了相關研究，研究重點集中于準確對眾包工作者的工作能力進行衡量，最大限度地發現眾多工作者中的不良標注者。傳統的眾包質量控制方法主要有黃金數據法[15]和多數投票法[16]。其中黃金數據法基于數據驅動的冗余思想，通過在待標注樣本中加入已知正確結果的樣本作為黃金數據，以眾包工作者對黃金數據的標注結果來評判該工作者的工作能力。其優點是簡單易行很早就被使用，缺點是未考慮樣本難度的區別，對所有難度的樣本對結果的影響沒有進行區分從而影響了最終的準確率。多數投票法基于機制驅動思想，基于重復標注的思想，令多個標注者對同一樣本多次標注，以最多的答案作為標準答案，這種方法同樣簡單易行，但其平等對待了所有的標注者未考慮到不同標注者工作能力的區別。針對這兩種經典眾包質量控制方法的缺點有學者提出使用機器學習的方法來解決，Raykar等[17]提出了一種基于EM算法的分類器模型和能力分數的概念來評估眾包工作者的能力，通過區分不同能力標注者的工作結果來找出不良標注者。Kajino等[18]基于Raykar等人的研究工作對該分類器模型進行了優化，提出了個人分類器的概念，即以每個標注者所對應的個人分類器參數距離基于所有標注者個人分類器參數平均值的真實值的距離作為其能力分數，示意如圖2所示。這種方法使用某眾包任務下所有工作者的眾包工作結果作為訓練集訓練出一個適用于該眾包任務的個人分類器對所有工作者進行能力評估，同時考慮了不同眾包工作者能力的區別和不同眾包任務難度的區別從而更準確、客觀地衡量眾包工作者的能力。

圖2 個人分類器能力分數示意圖

2.2 優化迭代的個人分類器

個人分類器模型基于邏輯回歸實現，LogisticRegression公式為：

P(y=1|x)=π(x)

(3)

其中π(x)是sigmod函數：

(4)

對于眾包所得樣本，將正確標注結果對應的參數向量記作ω0，為了克服過擬合，假設其服從以0為均值的Gaussian分布：

O(ω0|η)=N(μ,η-1I)

(5)

其中η是超參數，I是一個單位矩陣。其協方差矩陣表達式如下：

P(ωj|ω0,λ)=N(ω0,λ-1I)

(6)

針對第j個標注者，參考文獻[18]中假設該標注者的眾包工作結果由其對應的參數ωj來決定，并作為其對應的分類器，則其標注結果可表示為：

(7)

綜上分析結果，得到目標函數，是一個負對數似然函數：

(8)

其中W={ωj|j∈{1,2,…,J}}。該目標函數為凸函數，可以使用迭代的算法進行參數估計，迭代步驟分為兩個步驟。第一步將W固定來更新并得到解：

(9)

第二步固定ω0來更新W，采用Newton迭代法來更新每一個參數：

(10)

其中α是學習速率，H是Hessian矩陣：

(11)

其中梯度g(ωj,ω0)為：

(12)

經過上述兩個步驟，即可得到最佳參數W和ω0。

本文考慮到眾包實際進行中會存在的欺詐工作者，他們的工作結果和正確結果大相徑庭，他們的存在會對個人分類器均值造成較大影響，大大降低了分類器的準確性。針對這個問題，本文對迭代過濾的方法進行了優化，在迭代求解真實分類器的過程中就先剔除這些明顯的垃圾標注者。具體做法是在每一步迭代過程中將所有標注者按照各自的分類器能力分數排名，將排名最后的若干標注者進行過濾，算法如下：

輸入 迭代次數iter_max，超參數η， 過濾不良標注者的迭代次數間隔iter_gap，每次剔除標注者百分比p。

輸出 W，ω0。

While iter_num < iter_max：

將W固定來更新并得到解;

固定W0來更新W，采用Newton迭代法來更新每一個;

iter_num++;

if(iter_num%iter_gap)

對所有標注者按照分類器能力分數排名;

剔除排名最后p%的標注者;

endwhile

2.3 多分類支持個人分類器

上節中提出的個人分類器模型適用于二元分類問題，而LTR所需訓練數據集一般有多相關度等級的需求，例如微軟提出的OHSUMED數據集就包含了“相關”、“部分相關”、“不相關”三個相關度等級，故本節提出了一種基于DAGSVM的多分類支持個人分類器。

DAGSVM是一種基于有向無環圖的多分類算法(DAG)[19]，有完善的理論基礎。在訓練階段，DAGSVM通過將樣本兩兩組合的方式進行訓練得到子分類器；在分類階段，DAGSVM將所有子分類器作為節點構造一個有向無環圖，測試樣本將從根節點開始，由其當前所在節點分類器的計算結果來決定其下一步走向哪個分類器節點，如此迭代經過k-1步達到葉子節點時即完成分類。實驗結果表明，用于決策的有向無環圖中節點的排列順序對最終結果影響不大，具有較好的分類性能且訓練速度較快。圖3展示了一個三元分類的DAGSVM分類示例。

圖3 DAGSVM分類過程示意圖

由于DAGSVM基于SVM實現，其需要解決如下最優化問題：

(13)

(14)

對于多分類支持個人分類器，由于其分類超平面有多個，故能力分數的定義改進。若有k個分類超平面，某樣本S其到k個超平面的距離分別為{Ds1,Ds2,…,Dsk}，則其能力分數Q_mark可以定義為：

(15)

3 實驗結果分析

3.1 實驗方案設計

本文實驗分為兩個階段，首先針對提出的優化迭代個人分類器和基于DAGSVM的多分類支持個人分類器驗證其眾包質量控制性能，再基于OHSUMED數據集[20]驗證結合眾包的排序學習算法性能，具體方案如下：

1) 數據集

針對優化迭代的個人分類器實驗，本文采用計算機生成的仿真數據集模擬出眾包中好的和壞的標注者，考慮到LTR所需樣本的標注難度較低，按照80%到100%的正確率生成他們的標注結果；考慮到不良標注者會隨機給出標注值，故以50%的概率隨機生成0或者1作為他們的標注結果。實驗設置樣本維度為10，特征值區間設置為[-0.5，0.5]。樣本的真實標簽根據Logistic模型公式生成。實驗以0為均值的使用Gaussian分布生成分類器參數。

針對多分類支持的個人分類器實驗，本文使用微軟亞研院的Letor3.0 OHSUMED數據集[15]，OHSUMED數據集包含106個查詢共16 140個查詢-文檔對，每個查詢-文檔對都被標注為相關、部分相關、不相關三種不同的相關度，分別對應于標注值2、1、0。每個文檔都由45維特征向量進行表示。本文通過選取其中s_num條樣本修改其相關度值為標注值區間內隨機值的方法來模擬不良標注者的標注結果。

2) 衡量標準

本文通過對眾包標注的準確率和機器學習領域廣泛使用的AUC指標來衡量個人分類器眾包質量控制性能；通過信息檢索領域經典的NDCG指標衡量最終所得排序模型的性能。

3) 參數設置

本實驗需要控制的參數如表1所示。

表1 優化迭代個人分類器實驗參數含義

3.2 實驗結果分析

優化迭代個人分類器和多數投票法、經典個人分類器在AUC指標下的性能對比如表2所示，本實驗依次設置total_num={100，200,300}，g_num=5，s_num={10，50，90}，iter_num=10進行實驗，固定iter_gap=2，filter_num=1。從表中數據可知，在不同參數前提下經典個人分類器的性能都較多數投票法有大幅提升，而優化迭代的個人分類器在此基礎上又能將性能提高約2.5%。

表2 仿真數據集AUC對比

對本文提出的優化個人分類器方法影響最大的兩個參數是iter_gap和filter_num，本文分別將這兩個參數作為自變量進行實驗和優化分析。

圖4為隨著iter_gap的增加AUC指標的變化情況，此時iter_gap的取值范圍為{1,2,3,4,5}，g_num=5，s_num=10，filter_num=1。

圖4 iter_gap參數對優化迭代個人分類器AUC指標的影響

由圖4可見，當每次都過濾掉一個認為是不良的標注者時，AUC指標低于傳統的個人分類器方法，因為最初的幾次迭代中對于不良標注者的判斷不夠準確，容易出現誤判的情況，對結果造成影響。當iter_gap從2增加到4時，AUC指標也呈上升趨勢，因為隨著迭代次數的增多，分類器也越準確，進一步提高了過濾不良標注者的效果。當iter_gap為5時，AUC指標出現了略微的下降，因為iter_num為10，此時只進行了兩次過濾過程，過濾力度相對不足。綜上，在實際應用中推薦使用iter_gap=能獲得較好的性能。

為了驗證filter_num參數對實驗結果的影響，以filter_num為變量，令total_num=300，g_num=5，s_num=50，iter_gap=2。因為設置了iter_num=10，故會過濾5次，故filter_num變化范圍為[1，10]，實驗結果如圖5所示。從圖中可見，當filter_num在[1，4]區間內呈上升趨勢，在[5，10]區間內呈下降趨勢，其中在filter_num=4時達到最高，當filter_num位于[7，9]區間時性能介于傳統個人分類器和多數投票法之間，而當filter_num=10時性能甚至低于多數投票法，因為當每次過濾過多標注者也容易誤將好的標注者也過濾掉從而對最后的結果造成較大影響，這也符合實際情況。

圖5 filter_num參數對優化迭代個人分類器AUC指標的影響

圖6給出了三種眾包質量控制方法下眾包最終得到的標簽正確率對比。其中J=100，橫軸為不良標注者數量，縱軸為最終得到的標簽正確率。由圖6可見，本文提出的方法性能優于個人分類器和多數投票法，且當不良標注者增多時優勢越來越明顯，當100個標注者均為不良標注者時，三種方法的正確率都為50%，因為此時所有的標注者都隨機給出標簽結果，符合實際情況。

圖6 仿真數據集整體標注正確率對比

本文選擇高斯核函數進行基于DAGSVM的多分類支持個人分類器實驗，需要控制的影響因子包括s_num和drop_num。圖7給出了隨著不良標注結果數量的增加眾包標注整體正確率的變化情況。從圖7中可以看出，當不良標注者占比小于20%時，基于多分類支持個人分類器的眾包標注正確率較高，基本達到了DAGSVM分類正確率，當不良標注者占比在30%到70%區間內，正確率緩慢下降，當不良標注者占比大于70%時，正確率下降曲線斜率陡增，最終當全部都是不良標注者時達到30%左右的正確率，基本符合三元分類的隨機概率。實驗結果表明，當不良標注者占比小于20%時，基于多分類支持的個人分類器眾包標注準確率能達到95%左右。

圖7 不良標注數量對標注正確率的影響

為了驗證按照質量分數排序后過濾的不良標注結果個數drop_num對最終眾包結果正確率的影響，本文以OHSUMED數據集中qid={85,1,22,43,64}的實驗數據集進行實驗，共812個樣本。為了讓實驗結果更加明顯，設置了較多的不良標注結果，設置s_num=200。x軸為drop_num，y軸為正確率，實驗結果如圖8所示。由圖可知，當drop_num從0增長到200時最終標注正確率一直在提高，符合實際情況，其中drop_num從20到40的變化范圍內正確率提高的速度最快，當drop_num在60到160的范圍內增加時，正確率的增長基本保持線性同步增長；當drop_num大于200時，理論上分類器能夠將所有的不良標注數據都分類出來并刪除，此時的正確率達到95%左右；但隨著drop_num的增加，在200到300的范圍內變化時正確率出現震蕩，因為此時分類器在對不良標注樣本的判定上存在誤判，有可能過濾掉一部分好的標注結果從而對最終的正確率造成不良影響，由此可見drop_num過小會影響整體標注正確率，而drop_num過大對最終正確率的提升并沒有實質性的幫助，反而會浪費更多的有效標注樣本。綜上，在多分類支持的個人分類器的實際應用中尋找合適的drop_num時，可以通過抽取一部分樣本驗證的方式確定大概的不良標注結果比例從而找到合適的drop_num值。

圖8 過濾不良標注者的個數對正確率的影響

排序學習階段使用RankingSVM作為排序模型訓練算法，使用DAGSVM個人分類器作為眾包質量控制方法，并設置最優的drop_num參數，重點驗證在使用了個人分類器的前提下不良標注者個數即s_num參數對最終所得排序模型性能的影響情況。由前文實驗結果可知此時drop_num=200，本文以傳統RankingSVM算法作為比較的baseline。圖9是當s_num=100和200時結合眾包的排序學習方法在NDCG指標下的實驗結果，圖中縱軸是NDCG得分，橫軸是結果列表中的不同位置，分別從NDCG@1至NDCG@10。

圖9 不同s_num下結合眾包的LTR在NDCG指標下的性能

由圖9可知，當s_num=200時，此時不良標注占比為24.6%，此時結合眾包的排序學習方法在NDCG指標下從第1個位置到第10個位置的性能結果都低于傳統的RankingSVM算法，在NDCG@6和NDCG@8這兩個位置的性能接近于RankingSVM算法，可以認為是排序支持向量機本身的性能原因造成。當s_num=100時，此時不良標注占比為12.3%，由圖9可見，此時結合眾包的排序學習方法性能相比s_num=200的情況有了明顯提升，基本接近了基于全量標注訓練集的傳統RankingSVM的排序性能，在實際應用中能夠達到較好的排序效果，以提升搜索引擎整體性能。

4 結 語

本文提出了一種結合眾包的排序學習方法，創新地將眾包這種大眾網絡聚集新模式應用于有監督排序學習所需大量訓練數據集耗時耗力的標注工作中。針對眾包可能出現的質量不良問題提出了個人分類器模型，使用機器學習的方法訓練出可同時考慮眾包工作者能力和眾包任務難度的眾包質量評估模型。在實驗部分第一階段，本文首先驗證了優化迭代的個人分類器模型和適用于排序學習應用場景的多分類支持個人分類器模型，重點驗證了個人分類器在迭代過程中的迭代次數、過濾人數等參數對其性能的影響情況。在實驗部分的第二階段，本文基于OHSUMED數據集和多分類支持個人分類器模型進行了仿真實驗，驗證了在不同的不良標注者占比的情況下結合眾包的排序學習方法在NDCG指標下的性能，得到了結論：當不良標注者在眾包總參與者中的占比為12.3%時本文所提出的方法能夠基本達到傳統RaningSVM算法的排序性能，證明了將眾包和排序學習進行結合的可行性。考慮到在實際眾包應用中，不良標注者數量占比經過對眾包參與人員的基本的篩選過濾可較容易地低于12.3%這個比例，故本文的方法具有一定的實際指導意義。如何進一步提高眾包質量控制能力，從而能在不良標注者占比更高的情況下依然獲得良好的排序性能，在未來值得進行進一步的研究。

[1]HoweJeff.TheRiseofCrowdsourcing[J].06JenkinsHConvergenceCultureWhereOld&NewMediaCollide,2006,14(14):1-5.

[2]GuyI,PererA,DanielT,etal.Guesswho?:enrichingthesocialgraphthroughacrowdsourcinggame[C]//InternationalConferenceonHumanFactorsinComputingSystems,CHI2011,Vancouver,Bc,Canada,May.2011:1373-1382.

[3]SakamotoY,TanakaY,YuL,etal.Thecrowdsourcingdesignspace[C]//FoundationsofAugmentedCognition.DirectingtheFutureofAdaptiveSystems-,InternationalConference,Fac2011,HeldAs.2011:346-355.

[4]ParameswaranAG,Garcia-MolinaH,ParkH,etal.CrowdScreen:algorithmsforfilteringdatawithhumans[J].Sigmod,2011:361-372.

[5]MarcusA,WuE,MaddenSR,etal.CrowdsourcedDatabases:QueryProcessingwithPeople[C]//CIDR2011,FifthBiennialConferenceonInnovativeDataSystemsResearch,Asilomar,CA,USA,January9-12,2011,OnlineProceedings.2011:211-214.

[6]BrewA,GreeneD,CunninghamP.UsingCrowdsourcingandActiveLearningtoTrackSentimentinOnlineMedia[J].SentimentAnalysis,2010:145-150.

[7]KazaiG.Insearchofqualityincrowdsourcingforsearchengineevaluation[C]//EuropeanConferenceonAdvancesinInformationRetrieval.Springer-Verlag,2011.

[8]CrammerK,SingerY.PrankingwithRanking[J].AdvancesinNeuralInformationProcessingSystems,2002,14:641-647.

[9]CossockD,ZhangT.SubsetRankingUsingRegression[C]//ConferenceonLearningTheory.Springer-Verlag,2006:605-619.

[10]JoachimsT.TraininglinearSVMsinlineartime[C]//ACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.ACM,2006:217-226.

[11] Burges,Chris,Shaked,et al.Learning to rank using gradient descent[J].Inproceedings,2005:89-96.

[12] Cao Z,Qin T,Liu T Y,et al.Learning to rank:from pairwise approach to listwise approach[C]//Machine Learning,Proceedings of the Twenty-Fourth International Conference.2007:129-136.

[13] Yue Y,Finley T,Radlinski F,et al.A support vector method for optimizing average precision[C]//SIGIR 2007:Proceedings of the,International ACM SIGIR Conference on Research and Development in Information Retrieval,Amsterdam,the Netherlands,July.2007:271-278.

[14] Joachims T,Finley T,Yu C N J.Cutting-plane training of Structural SVMs[J].Machine Learning,2009,77(1):27-59.

[15] Joglekar M,Garcia-Molina H,Parameswaran A.Evaluating the crowd with confidence[J].Computer Science,2014:686-694.

[16] Liu X,Lu M,Ooi B C,et al.CDAS:a crowdsourcing data analytics system[J].Proceedings of the Vldb Endowment,2012,5(10):1040-1051.

[17] Raykar V C,Yu S,Zhao L H,et al.Learning From Crowds[J].Journal of Machine Learning Research,2010,11(2):1297-1322.

[18] Kajino H,Kashima H.A Convex Formulation of Learning from Crowds[J].電子情報通信學會技術研究報告.ibisml,情報論的學習理論と機械學習,2011,111(275):231-236.

[19] Platt J C,Cristianini N,Shawe-Taylor J.Large Margin DAGs for Multiclass Classification[J].Advances in Neural Information Processing Systems,2000,12(3):547-553.

[20] Liu T Y,Xu J,Qin T,et al.LETOR:Benchmark Dataset for Research on Learning to Rank for Information Retrieval[J].Proceedings of Sigir Workshop on Learning to Rank for Information Retrieval,2007,41(2):76-79.

A RANK LEARNING ALGORITHM COMBINED WITH CROWDSOURCING

Wang Xiaoping Xi Lingran

(SchoolofElectronicsandInformationEngineering,TongjiUniversity,Shanghai200092,China)

Aiming at the situation that it is difficult to obtain the large scale training data set with labels for supervised learning to rank, this paper introduces crowdsourcing, a new public network aggregation model, to complete the labeling work. It provides a new way to solve the problem of time consuming and labor consuming in the training dataset. We first introduce the crowdsourcing labeling method, and put forward two personal classifiers model to solve the problem of crowdsourcing quality control. At the same time, we consider the two factors that affect the quality of the crowdsourcing, including the marker ability and the difficulty of crowdsourcing tasks. Ranking SVM is used to rank learning based on the training set, and the performance of the method is evaluated on Microsoft OHSUMED data set under the NDCG@n criterion. The results show that the proposed crowdsourcing labeling method can achieve more than 95% correctness, and the performance of the ranking model is equal to Ranking SVM algorithm, which verifies the feasibility and superiority of crowdsourcing in ranking learning.

Learning to rank Crowdsourcing Crowdsourcing quality control Ranking SVM

2016-05-24。王小平，教授，主研領域：分布式智能系統，自然計算和社會計算。奚凌然，碩士生。

TP181

A

10.3969/j.issn.1000-386x.2017.06.050