一種結(jié)合眾包的排序?qū)W習(xí)算法

王小平 奚凌然

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

一種結(jié)合眾包的排序?qū)W習(xí)算法

王小平 奚凌然

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

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

排序?qū)W習(xí) 眾包 眾包質(zhì)量控制 排序支持向量機(jī)

0 引 言

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

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

圖1 眾包工作流程示意圖

本文提出一種結(jié)合眾包的排序?qū)W習(xí)方法，利用眾包解決訓(xùn)練數(shù)據(jù)的標(biāo)注難題。

1 基于Pairwise的排序?qū)W習(xí)模型RankingSVM

LTR使用機(jī)器學(xué)習(xí)的方法基于有標(biāo)注訓(xùn)練數(shù)據(jù)集學(xué)習(xí)得到一個(gè)排序模型，并用該排序模型計(jì)算某查詢下所有結(jié)果文檔和該查詢keyword之間的關(guān)聯(lián)程度，稱該關(guān)聯(lián)程度為排序分?jǐn)?shù)，最后以排序分?jǐn)?shù)為依據(jù)將所有查詢結(jié)果文檔降序排列。根據(jù)不同的輸入表示以及損失函數(shù)，LTR可分為基于Pointwise、基于Pairwise和基于Listwise三類模型方法：

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

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

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

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

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

考慮到RankingSVM目標(biāo)函數(shù)為求線性函數(shù)f使得總的錯(cuò)誤偏序?qū)?shù)量最少，基于支持向量機(jī)的分類器優(yōu)化模型可以用下列二次規(guī)劃表示為：

(1)

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

(2)

式中, Pi為查詢Qi中所有偏序關(guān)系對構(gòu)成的集合，ζ為松弛因子，C為懲罰參數(shù)，w為特征權(quán)向量，M為總偏序?qū)?shù)目，yixy為縮放處理后取值1或者-1。求解上述問題的最優(yōu)解即最優(yōu)特征權(quán)向量w，從而得到分類器模型f。然后根據(jù)得到的分類器模型，即可計(jì)算每個(gè)查詢結(jié)果的排序分?jǐn)?shù)，最后按得分大小對文檔集合進(jìn)行排序。

2 眾包在訓(xùn)練集標(biāo)注中的應(yīng)用

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

2.1 眾包質(zhì)量控制方法概述

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

圖2 個(gè)人分類器能力分?jǐn)?shù)示意圖

2.2 優(yōu)化迭代的個(gè)人分類器

個(gè)人分類器模型基于邏輯回歸實(shí)現(xiàn)，LogisticRegression公式為：

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

(3)

其中π(x)是sigmod函數(shù)：

(4)

對于眾包所得樣本，將正確標(biāo)注結(jié)果對應(yīng)的參數(shù)向量記作ω0，為了克服過擬合，假設(shè)其服從以0為均值的Gaussian分布：

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

(5)

其中η是超參數(shù)，I是一個(gè)單位矩陣。其協(xié)方差矩陣表達(dá)式如下：

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

(6)

針對第j個(gè)標(biāo)注者，參考文獻(xiàn)[18]中假設(shè)該標(biāo)注者的眾包工作結(jié)果由其對應(yīng)的參數(shù)ωj來決定，并作為其對應(yīng)的分類器，則其標(biāo)注結(jié)果可表示為：

(7)

綜上分析結(jié)果，得到目標(biāo)函數(shù)，是一個(gè)負(fù)對數(shù)似然函數(shù)：

(8)

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

(9)

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

(10)

其中α是學(xué)習(xí)速率，H是Hessian矩陣：

(11)

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

(12)

經(jīng)過上述兩個(gè)步驟，即可得到最佳參數(shù)W和ω0。

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

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

輸出 W，ω0。

While iter_num < iter_max：

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

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

iter_num++;

if(iter_num%iter_gap)

對所有標(biāo)注者按照分類器能力分?jǐn)?shù)排名;

剔除排名最后p%的標(biāo)注者;

endwhile

2.3 多分類支持個(gè)人分類器

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

DAGSVM是一種基于有向無環(huán)圖的多分類算法(DAG)[19]，有完善的理論基礎(chǔ)。在訓(xùn)練階段，DAGSVM通過將樣本兩兩組合的方式進(jìn)行訓(xùn)練得到子分類器；在分類階段，DAGSVM將所有子分類器作為節(jié)點(diǎn)構(gòu)造一個(gè)有向無環(huán)圖，測試樣本將從根節(jié)點(diǎn)開始，由其當(dāng)前所在節(jié)點(diǎn)分類器的計(jì)算結(jié)果來決定其下一步走向哪個(gè)分類器節(jié)點(diǎn)，如此迭代經(jīng)過k-1步達(dá)到葉子節(jié)點(diǎn)時(shí)即完成分類。實(shí)驗(yàn)結(jié)果表明，用于決策的有向無環(huán)圖中節(jié)點(diǎn)的排列順序?qū)ψ罱K結(jié)果影響不大，具有較好的分類性能且訓(xùn)練速度較快。圖3展示了一個(gè)三元分類的DAGSVM分類示例。

圖3 DAGSVM分類過程示意圖

由于DAGSVM基于SVM實(shí)現(xiàn)，其需要解決如下最優(yōu)化問題：

(13)

(14)

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

(15)

3 實(shí)驗(yàn)結(jié)果分析

3.1 實(shí)驗(yàn)方案設(shè)計(jì)

本文實(shí)驗(yàn)分為兩個(gè)階段，首先針對提出的優(yōu)化迭代個(gè)人分類器和基于DAGSVM的多分類支持個(gè)人分類器驗(yàn)證其眾包質(zhì)量控制性能，再基于OHSUMED數(shù)據(jù)集[20]驗(yàn)證結(jié)合眾包的排序?qū)W習(xí)算法性能，具體方案如下：

1) 數(shù)據(jù)集

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

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

2) 衡量標(biāo)準(zhǔn)

本文通過對眾包標(biāo)注的準(zhǔn)確率和機(jī)器學(xué)習(xí)領(lǐng)域廣泛使用的AUC指標(biāo)來衡量個(gè)人分類器眾包質(zhì)量控制性能；通過信息檢索領(lǐng)域經(jīng)典的NDCG指標(biāo)衡量最終所得排序模型的性能。

3) 參數(shù)設(shè)置

本實(shí)驗(yàn)需要控制的參數(shù)如表1所示。

表1 優(yōu)化迭代個(gè)人分類器實(shí)驗(yàn)參數(shù)含義

3.2 實(shí)驗(yàn)結(jié)果分析

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

表2 仿真數(shù)據(jù)集AUC對比

對本文提出的優(yōu)化個(gè)人分類器方法影響最大的兩個(gè)參數(shù)是iter_gap和filter_num，本文分別將這兩個(gè)參數(shù)作為自變量進(jìn)行實(shí)驗(yàn)和優(yōu)化分析。

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

圖4 iter_gap參數(shù)對優(yōu)化迭代個(gè)人分類器AUC指標(biāo)的影響

由圖4可見，當(dāng)每次都過濾掉一個(gè)認(rèn)為是不良的標(biāo)注者時(shí)，AUC指標(biāo)低于傳統(tǒng)的個(gè)人分類器方法，因?yàn)樽畛醯膸状蔚袑τ诓涣紭?biāo)注者的判斷不夠準(zhǔn)確，容易出現(xiàn)誤判的情況，對結(jié)果造成影響。當(dāng)iter_gap從2增加到4時(shí)，AUC指標(biāo)也呈上升趨勢，因?yàn)殡S著迭代次數(shù)的增多，分類器也越準(zhǔn)確，進(jìn)一步提高了過濾不良標(biāo)注者的效果。當(dāng)iter_gap為5時(shí)，AUC指標(biāo)出現(xiàn)了略微的下降，因?yàn)閕ter_num為10，此時(shí)只進(jìn)行了兩次過濾過程，過濾力度相對不足。綜上，在實(shí)際應(yīng)用中推薦使用iter_gap=能獲得較好的性能。

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

圖5 filter_num參數(shù)對優(yōu)化迭代個(gè)人分類器AUC指標(biāo)的影響

圖6給出了三種眾包質(zhì)量控制方法下眾包最終得到的標(biāo)簽正確率對比。其中J=100，橫軸為不良標(biāo)注者數(shù)量，縱軸為最終得到的標(biāo)簽正確率。由圖6可見，本文提出的方法性能優(yōu)于個(gè)人分類器和多數(shù)投票法，且當(dāng)不良標(biāo)注者增多時(shí)優(yōu)勢越來越明顯，當(dāng)100個(gè)標(biāo)注者均為不良標(biāo)注者時(shí)，三種方法的正確率都為50%，因?yàn)榇藭r(shí)所有的標(biāo)注者都隨機(jī)給出標(biāo)簽結(jié)果，符合實(shí)際情況。

圖6 仿真數(shù)據(jù)集整體標(biāo)注正確率對比

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

圖7 不良標(biāo)注數(shù)量對標(biāo)注正確率的影響

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

圖8 過濾不良標(biāo)注者的個(gè)數(shù)對正確率的影響

排序?qū)W習(xí)階段使用RankingSVM作為排序模型訓(xùn)練算法，使用DAGSVM個(gè)人分類器作為眾包質(zhì)量控制方法，并設(shè)置最優(yōu)的drop_num參數(shù)，重點(diǎn)驗(yàn)證在使用了個(gè)人分類器的前提下不良標(biāo)注者個(gè)數(shù)即s_num參數(shù)對最終所得排序模型性能的影響情況。由前文實(shí)驗(yàn)結(jié)果可知此時(shí)drop_num=200，本文以傳統(tǒng)RankingSVM算法作為比較的baseline。圖9是當(dāng)s_num=100和200時(shí)結(jié)合眾包的排序?qū)W習(xí)方法在NDCG指標(biāo)下的實(shí)驗(yàn)結(jié)果，圖中縱軸是NDCG得分，橫軸是結(jié)果列表中的不同位置，分別從NDCG@1至NDCG@10。

圖9 不同s_num下結(jié)合眾包的LTR在NDCG指標(biāo)下的性能

由圖9可知，當(dāng)s_num=200時(shí)，此時(shí)不良標(biāo)注占比為24.6%，此時(shí)結(jié)合眾包的排序?qū)W習(xí)方法在NDCG指標(biāo)下從第1個(gè)位置到第10個(gè)位置的性能結(jié)果都低于傳統(tǒng)的RankingSVM算法，在NDCG@6和NDCG@8這兩個(gè)位置的性能接近于RankingSVM算法，可以認(rèn)為是排序支持向量機(jī)本身的性能原因造成。當(dāng)s_num=100時(shí)，此時(shí)不良標(biāo)注占比為12.3%，由圖9可見，此時(shí)結(jié)合眾包的排序?qū)W習(xí)方法性能相比s_num=200的情況有了明顯提升，基本接近了基于全量標(biāo)注訓(xùn)練集的傳統(tǒng)RankingSVM的排序性能，在實(shí)際應(yīng)用中能夠達(dá)到較好的排序效果，以提升搜索引擎整體性能。

4 結(jié) 語

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

[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].電子情報(bào)通信學(xué)會技術(shù)研究報(bào)告.ibisml,情報(bào)論的學(xué)習(xí)理論と機(jī)械學(xué)習(xí),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。王小平，教授，主研領(lǐng)域：分布式智能系統(tǒng)，自然計(jì)算和社會計(jì)算。奚凌然，碩士生。

TP181

A

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