鄧曉軍，滿君豐，歐陽旻

（湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院，湖南株洲412007）

·開發(fā)研究與工程應(yīng)用·

基于K武裝決斗土匪問題的排序器在線評(píng)估算法

鄧曉軍，滿君豐，歐陽旻

（湖南工業(yè)大學(xué)計(jì)算機(jī)與通信學(xué)院，湖南株洲412007）

對(duì)各種不同的排序器進(jìn)行評(píng)估可以選出較優(yōu)的排序器，從而為用戶的個(gè)性化檢索提供更好的排序結(jié)果。因此，為提高排序器評(píng)估結(jié)果的性能，根據(jù)現(xiàn)有研究結(jié)果將排序器評(píng)估形式化描述為K武裝決斗土匪問題，提出一種基于采樣的高效K武裝決斗土匪算法，并分析2種模式下的求解目標(biāo)。通過采樣的方式模擬賽事并選出獲勝者，根據(jù)置信上界在剩余排序器中選出挑戰(zhàn)者，并將獲勝者與挑戰(zhàn)者進(jìn)行交錯(cuò)比較，得出評(píng)分矩陣。實(shí)驗(yàn)結(jié)果表明，與SAVAGE算法及RUCB算法相比，該算法不僅準(zhǔn)確性高，累計(jì)失望值小，而且具有較好的穩(wěn)定性。

信息檢索；排序器；失望最小化；K武裝決斗土匪檢測(cè)；在線評(píng)估算法

1 概述

排序器評(píng)估是在給定的若干個(gè)排序器中確定哪個(gè)性能是最優(yōu)的，是信息檢索領(lǐng)域的重要研究?jī)?nèi)容之一［1］。離線排序器評(píng)估可以追溯到早期的Cranfield實(shí)驗(yàn)［2］。該實(shí)驗(yàn)通過人工的方式對(duì)排序器進(jìn)行評(píng)估，評(píng)價(jià)的標(biāo)準(zhǔn)基于一個(gè)固定的查詢和文檔集合。這種人工判別的方式代價(jià)高，并且容易出錯(cuò)。由于評(píng)估者沒有對(duì)查詢進(jìn)行形式化描述，他們的評(píng)估并不能準(zhǔn)確地反映這些文檔在何種程度上滿足真實(shí)用戶的需求［3］。

排序器在線評(píng)估通過真實(shí)用戶的點(diǎn)擊反饋來評(píng)價(jià)排序器的性能，可以有效地解決上述問題。排序器在線評(píng)估通常采用交錯(cuò)比較法［4］，即對(duì)于給定的查詢，將2個(gè)候選排序器的結(jié)果交錯(cuò)在一起構(gòu)成一個(gè)文檔列表展現(xiàn)給用戶，通過用戶的點(diǎn)擊反饋來推導(dǎo)2個(gè)排序器的性能［5］。交錯(cuò)比較法面臨的一個(gè)關(guān)鍵問題是如何通過成對(duì)比較在多個(gè)排序器中選出最優(yōu)的，該問題可以形式化地描述為K武裝土匪問題［6］。在K武裝土匪問題中，最優(yōu)的排序器預(yù)計(jì)在與其他排序器的成對(duì)比較中都會(huì)勝出。

在探索后開發(fā)模式中，在線評(píng)估算法在一個(gè)固定的時(shí)間段（稱為horizon）內(nèi)完成，并評(píng)價(jià)出最優(yōu)的排序器［7］。這種方法的評(píng)價(jià)指標(biāo)為算法選出的最優(yōu)排序器的準(zhǔn)確性和horizon時(shí)間段內(nèi)累計(jì)的失望（regret）值。失望是交錯(cuò)比較中排序器的次最優(yōu)（相對(duì)于最優(yōu)）的度量標(biāo)準(zhǔn)。在探索后開發(fā)模式中，排序器在線評(píng)估采用的方法有交錯(cuò)過濾法［6］、打敗均值法［8］、通用探索變量的敏感性分析［9］等。在持續(xù)失望最小化（ongoing regretm inim ization）模式中，不需要預(yù)先指定固定的時(shí)間段，通過最小化累計(jì)失望值進(jìn)行排序器的評(píng)估，如RUCB算法［10］。

本文基于采樣方法，提出一種高效的排序器在線評(píng)估算法。通過采樣的方式模擬賽事并選出獲勝者，根據(jù)置信上界在剩余排序器中選出挑戰(zhàn)者，并將獲勝者與挑戰(zhàn)者進(jìn)行交錯(cuò)比較。

2 問題描述

K武裝土匪問題中存在K個(gè)排序器｛ρ1，ρ2，…，ρK｝，每一個(gè)時(shí)間步根據(jù)未知穩(wěn)態(tài)分布的期望值μi（即用戶的點(diǎn)擊率）對(duì)排序器ρi進(jìn)行測(cè)試，并產(chǎn)生相應(yīng)的收益值。K武裝決斗土匪問題是K武裝土匪問題的變體形式，通過交錯(cuò)比較法對(duì)排序器進(jìn)行評(píng)估，并對(duì)用戶的反饋進(jìn)行建模。

K武裝決斗土匪是一個(gè)比較概率矩陣P=［Pij］。在每一個(gè)時(shí)間步中，通過交錯(cuò)比較法對(duì)2個(gè)排序器ρi和ρj進(jìn)行比較，得到ρi打敗ρj的概率Pij。本文假設(shè)K個(gè)排序器中存在Condorcet獲勝者［9］：存在排序器ρi，使得將Condorcet獲勝者與任意一個(gè)排序器進(jìn)行交錯(cuò)比較，Condorcet獲勝者都將獲勝。

K武裝決斗土匪問題的目標(biāo)可以通過多種方式進(jìn)行形式化描述，不同的目標(biāo)形式化方法決定不同的求解算法。本文考慮如下2個(gè)目標(biāo)：

（1）explore-then-exploit［6］：在該模式下，算法需要預(yù)先指定探索的時(shí)間段，在探索時(shí)間段結(jié)束后，探索過程選取一個(gè)最優(yōu)的排序器，該排序器在后續(xù)階段被使用。算法的準(zhǔn)確性通過指定時(shí)間段內(nèi)找出Condorcet獲勝者的概率來評(píng)估，以及探索過程累積的失望值。在每一步探索過程中，失望值的定義為：如果在時(shí)間t選取ρi和ρj進(jìn)行比較，那么失望值為：

（2）ongoing regret minimization［11］：該模式下并不需要指定探索的時(shí)間段，評(píng)估過程連續(xù)執(zhí)行，因而算法的評(píng)價(jià)指標(biāo)不再是指定時(shí)間段后最大化準(zhǔn)確性和最小化失望值。該模式的目標(biāo)可以形式化為最小化隨時(shí)間變化的累積失望值。

3 排序器在線評(píng)估方法

本文提出了一種基于采樣的高效K武裝決斗土匪算法，該算法在通過競(jìng)爭(zhēng)移除排序器時(shí)可以明顯減少累積失望值，可同時(shí)應(yīng)用于explore-then-exploit和ongoing regret minimization2種模式。

本文提出的算法與RUCB算法都適用于ongoing regret minimization模式，其區(qū)別在于本文算法通過循環(huán)賽選取獲勝者時(shí)進(jìn)行采樣操作。該采樣操作的目的是：維護(hù)每個(gè)排序器期望值的后驗(yàn)分布，并對(duì)這些后驗(yàn)分布進(jìn)行采樣來選取最優(yōu)的排序器。通過采用Thompson采樣［12］，該算法的性能明顯優(yōu)于RUCB算法。RUCB算法依賴于期望值的估計(jì)，該估計(jì)值可能與真實(shí)值有很大偏差，然而采樣方法依賴于后驗(yàn)分布，并且后驗(yàn)分布不會(huì)導(dǎo)致期望值趨向極值，因而不會(huì)導(dǎo)致可能的選項(xiàng)經(jīng)常被選取。

在排序器評(píng)估中對(duì)后驗(yàn)分布的采樣更加合理，并且會(huì)提高算法的效率。RUCB算法在候選獲勝者的選擇中很保守，除非確認(rèn)ρi明顯低于其他排序器外，否則ρi仍有可能為潛在的獲勝者。本文提出的采樣方法認(rèn)為，一個(gè)排序器打敗其他排序器的概率越高，那么這個(gè)排序器成為獲勝者的概率越大。

本文提出的基于采樣的K武裝決斗土匪算法的基本思想如下：根據(jù)K武裝決斗土匪規(guī)則應(yīng)用采樣方法在排序器之間進(jìn)行賽事模擬，依據(jù)采樣得到的結(jié)果判斷每2個(gè)排序器獲勝的概率大小；當(dāng)某個(gè)排序器打敗其他所有的排序器時(shí)，認(rèn)為該排序器為獲勝者，如果不存在獲勝者，那么令獲勝者為上述選取過程中選為獲勝者次數(shù)最少的排序器；根據(jù)采樣次數(shù)的增加逐漸移除性能較弱的排序器，最終用Condorcet獲勝者作為最優(yōu)的排序器。算法詳細(xì)描述如下：

算法 基于采樣的K武裝決斗土匪算法

輸入 排序器集合｛ρ1，ρ2，…，ρK｝；交錯(cuò)比較器C

該算法的輸入為排序器集合｛ρ1，ρ2，…，ρK｝和交錯(cuò)比較器C，交錯(cuò)比較器對(duì)任意2個(gè)排序器進(jìn)行比較并選出獲勝者以及獲勝的概率。由于算法沒有預(yù)先指定時(shí)間段，因此該算法沒有輸出結(jié)果，最優(yōu)排序器的頻率會(huì)隨著時(shí)間的推移越來越大。該算法包含一個(gè)參數(shù)α（第1行）控制算法的探索行為的能力，α值越大，算法落在單個(gè)排序器上的速度越慢。該算法同時(shí)維護(hù)一個(gè)評(píng)分矩陣W（第2行）用于保存排序器之間的兩兩比較結(jié)果。

算法的初始化部分為第1行～第2行，循環(huán)體部分為第3行～第11行。循環(huán)體內(nèi)部可以分為如下3個(gè)部分：

（1）賽事模擬部分（第4行～第7行）。基于當(dāng)前的評(píng)分矩陣W進(jìn)行賽事模擬。對(duì)于任意一對(duì)排序器ρi和ρj，令維護(hù)的后驗(yàn)概率Pij符合參數(shù)為Wij+ 1和Wji+1的β分布，并對(duì)Θij（t）進(jìn)行采樣。由于Pji=1-Pij，令Θji（t）=1-Θij（t）。對(duì)于所有的排序器，其與自身的比較勝率為所以在得到上述采樣結(jié)果后，如果那么ρi打敗ρj。在獲勝者的選取過程中存在以下2種情況（第7行）：

2）如果不存在獲勝者c，那么令c為上述選取過程中選為獲勝者次數(shù)最少的排序器，即c=

在上述賽事模擬過程中，一旦Condorcet獲勝者與其他排序器進(jìn)行比較的次數(shù)足夠多時(shí)，就會(huì)將其與的排序器移除。隨著時(shí)間的推移，該Condorcet獲勝者被選為獲勝者的概率會(huì)越來越大。

（2）根據(jù)c尋找置信上界（第8行～第9行）。本文應(yīng)用置信上界算法來解決K武裝分子問題。對(duì)于任意一個(gè)j∈｛1，2，…，K｝，計(jì)算如下樂觀估計(jì)：

其中，第1項(xiàng)為比較概率Pjc的估計(jì)值；第2項(xiàng)為置信區(qū)間。該置信區(qū)間允許其他排序器與c進(jìn)行樂觀比較，從而保證足夠的探索空間。然后，選取排序器d，并且使得Udc＞Ujc（c∈｛1，2，…，K｝）。

（3）更新比較結(jié)果（第10行）。最后，將獲勝者c與挑戰(zhàn)者d進(jìn)行交錯(cuò)比較，并將比較結(jié)果更新到評(píng)分矩陣W中。

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

4.1 數(shù)據(jù)集與實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)采用2個(gè)公開的學(xué)習(xí)排序數(shù)據(jù)集Microsoft［13］和Yahoo?。?4］，其中Yahoo！數(shù)據(jù)集包含2個(gè)不同的數(shù)據(jù)集，實(shí)驗(yàn)選取了較大的數(shù)據(jù)集。數(shù)據(jù)集的基本信息如表1所示。在這2個(gè)數(shù)據(jù)集上，應(yīng)用BM 25［15］算法對(duì)每個(gè)特征進(jìn)行排序，并將每個(gè)排序結(jié)果視為一個(gè)排序器。

表1 數(shù)據(jù)集基本信息

在explore-then-exploit模式中，應(yīng)用準(zhǔn)確率和累積失望值作為評(píng)價(jià)指標(biāo)。在ongoing regret minimization模式中，應(yīng)用累積失望值作為評(píng)價(jià)指標(biāo)。準(zhǔn)確率為得到最優(yōu)排序器的比例。失望值的定義如式（1）所示，累積失望值為給定時(shí)間內(nèi)算法的失望值之和。當(dāng)排序器評(píng)估算法進(jìn)行次最優(yōu)選擇時(shí)，會(huì)累積失望值，這意味著最優(yōu)排序器并沒有和自身進(jìn)行交錯(cuò)比較。在實(shí)驗(yàn)中，令RUCB算法和本文提出的采樣算法的參數(shù)α=0.501，這可以確保RUCB算法不必進(jìn)行太多的探索就可以得到可行解。

4.2 實(shí)驗(yàn)結(jié)果

首先，在Exp lore-then-exploit模式下，將本文提出的采樣算法與SAVAGE算法進(jìn)行對(duì)比。2種算法在Microsoft和Yahoo！數(shù)據(jù)集下的準(zhǔn)確率和累計(jì)失望值對(duì)比如圖1所示。圖1（a）和圖1（b）為2種算法的準(zhǔn)確性對(duì)比，隨著時(shí)間的推移，2種算法的準(zhǔn)確性都逐漸提高，然而本文算法的準(zhǔn)確性始終高于SAVAGE算法，并且很快就收斂到1。圖1（c）和圖1（d）為2種算法的累計(jì)失望值對(duì)比，隨著時(shí)間的推移，2種算法的累計(jì)失望值都逐漸增大，并且本文算法的累計(jì)失望值要小于SAVAGE算法。當(dāng)時(shí)間達(dá)到103s時(shí)，本文算法的累計(jì)失望值增長(zhǎng)緩慢，然而SAVAFE算法卻在時(shí)間超過104時(shí)才增長(zhǎng)緩慢，這說明本文采用的采樣算法不僅能快速確定最優(yōu)排序器，而且具有更小的累計(jì)失望值。

圖1 本文算法與SAVAGE算法的性能對(duì)比

然后，在ongoing regretm inim ization模式下，將本文提出的采樣算法與RUCB算法進(jìn)行對(duì)比。2種算法在Microsoft和Yahoo！數(shù)據(jù)集下的累計(jì)失望值對(duì)比如圖2所示。該模式下算法連續(xù)運(yùn)行，通過設(shè)置時(shí)間間隔來觀察不同時(shí)間下算法的累計(jì)失望值。從這2個(gè)圖中可以看出，雖然本文算法和RUCB算法的收斂時(shí)間相近，但是本文算法卻具有更小的累計(jì)失望值，因而在評(píng)估排序器時(shí)具有更高的準(zhǔn)確性。

圖2 本文算法與RUCB算法的累計(jì)失望值對(duì)比

最后，對(duì)比了RUCB算法和本文算法的穩(wěn)定性，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 本文算法與RUCB算法的穩(wěn)定性對(duì)比

在該組實(shí)驗(yàn)中，取參數(shù)α=0.1，采用Microsoft數(shù)據(jù)集中的10個(gè)特征作為排序器集合，算法重復(fù)運(yùn)行30次并且取結(jié)果的平均值。從該圖可以看出，本文算法在多次運(yùn)行過程中始終保持收斂的趨勢(shì)，并且收斂的時(shí)間仍為103s；然而RUCB算法經(jīng)過多次運(yùn)行取平均值后，算法的累計(jì)失望值處于線性增長(zhǎng)的趨勢(shì)。由此可以認(rèn)定，RUCB算法在評(píng)估排序器時(shí)具有一定的隨機(jī)性，算法的穩(wěn)定性不好，而本文算法的穩(wěn)定性明顯優(yōu)于RUCB算法。

5 結(jié)束語

在信息檢索中，隨著用戶需求的不同需要不同的排序方法。當(dāng)用戶提出個(gè)性化檢索需求時(shí)，系統(tǒng)往往需要對(duì)多個(gè)排序器進(jìn)行評(píng)估，從而使用最優(yōu)的排序器為用戶服務(wù)。本文研究了多個(gè)排序器的在線評(píng)估方法。根據(jù)現(xiàn)有研究結(jié)果將排序器評(píng)估形式化描述為

K武裝決斗土匪問題，并分析了explore-then-exploit和ongoing regret m inim ization 2種模式下的求解目標(biāo)，提出了一種基于采樣的高效K武裝決斗土匪算法。該算法通過采樣的方式模擬賽事并選出獲勝者，根據(jù)置信上界在剩余排序器中選出挑戰(zhàn)者，并將獲勝者與挑戰(zhàn)者進(jìn)行交錯(cuò)比較。實(shí)驗(yàn)結(jié)果表明，本文算法的檢測(cè)準(zhǔn)確性高，累計(jì)矢望值小，穩(wěn)定性也較好。

［1］ 鄧 輝.網(wǎng)頁學(xué)習(xí)排序算法研究［D］.武漢：華中科技大學(xué)，2013.

［2］ Cleverdon C W，Mills J，Keen E M.Factors Determining the Performance of Indexing System s［J］.Cranfield，UK：College of Aeronautics，1966.

［3］ 楊 子，唐 杰，李涓子.異構(gòu)網(wǎng)絡(luò)學(xué)習(xí)排序模型及應(yīng)用［J］.中國科技論文在線，2011，6（4）：273-279.

［4］ Chuklin A，Schuth A，Hofmann K，et al.Evaluating Aggregated Search Using Interleaving［C］//Proceedings of the 22nd ACM International Conference on Information&Know ledge Management.New York， USA：ACM Press，2013：669-678.

［5］ 吳佳金，楊志豪，林 原，等.基于改進(jìn)Pairwise損失函數(shù)的排序?qū)W習(xí)方法［C］//第六屆全國信息檢索學(xué)術(shù)會(huì)議論文集.牡丹江：［出版者不詳］，2010：96-103.

［6］ Yue Yisong，Broder J，Kleinberg R，et al.The K-armed Dueling Bandits Problem［J］.Journal of Computer and System Sciences，2012，78（5）：1538-1556.

［7］ 花貴春，張 敏，劉奕群，等.基于查詢聚類的排序?qū)W習(xí)算法［J］.模式識(shí)別與人工智能，2012，25（1）：118-123.

［8］ Yue Yisong，Joachim s T.Beat the Mean Bandit［C］// Proceedings of the 28th International Conference on Machine Learning.Haifa，Israel：［s.n.］，2011：241-248.

［9］ Urvoy T，Clerot F，F(xiàn)éraud R，et al.Generic Exploration and K-arm ed Voting Bandits［C］//Proceedings of the 30th International Conference on Machine Learning. Berlin，Germany：Springer，2013：91-99.

［10］ Zoghi M，Whiteson S，Munos R，et al.Relative Upper Confidence Bound for the K-arm ed Dueling Bandit Problem［Z］.2013.

［11］ Lai T L，Robbins H.Asymptotically Efficient Adaptive Allocation Rules［J］.IEEE Transactions on Automatic Control，1985，6（1）：4-22.

［12］ Agrawal S，Goyal N.Analysis of Thompson Sampling for the Multi-arm ed Bandit Problem［C］//Proceedings of Conference on Learning Theory，Washington D.C.，USA：IEEE Press，2012：1-26.

［13］ Microsoft Learning to Rank Datasets［EB/OL］.（2012-06-27）.http：//research.m icrosoft.com/en-us/projects/ m slr/default.aspx.

［14］ Chapelle O，Chang Y.Yahoo！Learning to Rank Challenge Overview［J］.Journal of Machine Learning Research，2011，14：1-24.

［15］ Robertson S，Zaragoza H，Taylor M.Simple BM 25 Extension to Multiple Weighted Fields［C］//Proceedings of the 13th ACM International Conference on Information and Know ledge Management.New York，USA：ACM Press，2004：42-49.

編輯顧逸斐

On line Evaluation Algorithm of Sorting Device Based on K-arm ed Dueling Bandits Problem

DENG Xiaojun，MAN Junfeng，OUYANG Min
（College of Computer and Communication，Hunan University of Technology，Zhuzhou 412007，China）

According to evaluate various sorting devices，one can choose optimal sorting devices，and provide users with better ordered results for personalized retrieval requests based on these optimal sorting devices.In order to im prove the performance of evaluation of sorting devices，this paper proposes a sam p ling-based efficient K-armed dueling bandits algorithm.According to current researches，it formalizes the evaluation of sorting devices as the problem of K-armed dueling bandits，and analyzes the goals of the problem under both exp lore-then-exploit and ongoing regret minimization models.The algorithm simulates tournament based on sampling and chooses the w inner，then chooses challenger according to upper confidence bound，and at last，com pares the w inner and the challenger using interleaved comparison，and gets the score matrix.Experimental results show that，com pared with SAVAGE algorithm and RUCB algorithm，the proposed algorithm has higher detection accuracy，less cumulative regret，and better stability.

information retrieval；sorting device；regret minimization；K-armed dueling bandits；online evaluation method

鄧曉軍，滿君豐，歐陽旻.基于K武裝決斗土匪問題的排序器在線評(píng)估算法［J］.計(jì)算機(jī)工程，2015，41（9）：271-275.

英文引用格式：Deng Xiaojun，Man Junfeng，Ouyang M in.Online Evaluation Algorithm of Sorting Device Based on K-armed Dueling Bandits Problem［J］.Computer Engineering，2015，41（9）：271-275.

1000-3428（2015）09-0271-05

A

TP319

10.3969/j.issn.1000-3428.2015.09.050

國家自然科學(xué)基金資助項(xiàng)目（61350011）；湖南省自然科學(xué)基金資助項(xiàng)目（2015JJ2046，2014JJ2115）；湖南省教育廳科研基金資助項(xiàng)目（12C0068）。

鄧曉軍（1974-），男，副教授、碩士，主研方向：信息檢索；滿君豐，教授、博士；歐陽旻，講師、碩士。

2014-10-28

2014-11-25 E-m ail：xiaojundengls@163.com