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

鄧曉軍，滿君豐，歐陽旻

（湖南工業大學計算機與通信學院，湖南株洲412007）

·開發研究與工程應用·

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

鄧曉軍，滿君豐，歐陽旻

（湖南工業大學計算機與通信學院，湖南株洲412007）

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

信息檢索；排序器；失望最小化；K武裝決斗土匪檢測；在線評估算法

1 概述

排序器評估是在給定的若干個排序器中確定哪個性能是最優的，是信息檢索領域的重要研究內容之一［1］。離線排序器評估可以追溯到早期的Cranfield實驗［2］。該實驗通過人工的方式對排序器進行評估，評價的標準基于一個固定的查詢和文檔集合。這種人工判別的方式代價高，并且容易出錯。由于評估者沒有對查詢進行形式化描述，他們的評估并不能準確地反映這些文檔在何種程度上滿足真實用戶的需求［3］。

排序器在線評估通過真實用戶的點擊反饋來評價排序器的性能，可以有效地解決上述問題。排序器在線評估通常采用交錯比較法［4］，即對于給定的查詢，將2個候選排序器的結果交錯在一起構成一個文檔列表展現給用戶，通過用戶的點擊反饋來推導2個排序器的性能［5］。交錯比較法面臨的一個關鍵問題是如何通過成對比較在多個排序器中選出最優的，該問題可以形式化地描述為K武裝土匪問題［6］。在K武裝土匪問題中，最優的排序器預計在與其他排序器的成對比較中都會勝出。

在探索后開發模式中，在線評估算法在一個固定的時間段（稱為horizon）內完成，并評價出最優的排序器［7］。這種方法的評價指標為算法選出的最優排序器的準確性和horizon時間段內累計的失望（regret）值。失望是交錯比較中排序器的次最優（相對于最優）的度量標準。在探索后開發模式中，排序器在線評估采用的方法有交錯過濾法［6］、打敗均值法［8］、通用探索變量的敏感性分析［9］等。在持續失望最小化（ongoing regretm inim ization）模式中，不需要預先指定固定的時間段，通過最小化累計失望值進行排序器的評估，如RUCB算法［10］。

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

2 問題描述

K武裝土匪問題中存在K個排序器｛ρ1，ρ2，…，ρK｝，每一個時間步根據未知穩態分布的期望值μi（即用戶的點擊率）對排序器ρi進行測試，并產生相應的收益值。K武裝決斗土匪問題是K武裝土匪問題的變體形式，通過交錯比較法對排序器進行評估，并對用戶的反饋進行建模。

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

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

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

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

3 排序器在線評估方法

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

本文提出的算法與RUCB算法都適用于ongoing regret minimization模式，其區別在于本文算法通過循環賽選取獲勝者時進行采樣操作。該采樣操作的目的是：維護每個排序器期望值的后驗分布，并對這些后驗分布進行采樣來選取最優的排序器。通過采用Thompson采樣［12］，該算法的性能明顯優于RUCB算法。RUCB算法依賴于期望值的估計，該估計值可能與真實值有很大偏差，然而采樣方法依賴于后驗分布，并且后驗分布不會導致期望值趨向極值，因而不會導致可能的選項經常被選取。

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

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

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

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

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

算法的初始化部分為第1行～第2行，循環體部分為第3行～第11行。循環體內部可以分為如下3個部分：

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

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

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

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

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

（3）更新比較結果（第10行）。最后，將獲勝者c與挑戰者d進行交錯比較，并將比較結果更新到評分矩陣W中。

4 實驗結果與分析

4.1 數據集與實驗設置

實驗采用2個公開的學習排序數據集Microsoft［13］和Yahoo！［14］，其中Yahoo！數據集包含2個不同的數據集，實驗選取了較大的數據集。數據集的基本信息如表1所示。在這2個數據集上，應用BM 25［15］算法對每個特征進行排序，并將每個排序結果視為一個排序器。

表1 數據集基本信息

在explore-then-exploit模式中，應用準確率和累積失望值作為評價指標。在ongoing regret minimization模式中，應用累積失望值作為評價指標。準確率為得到最優排序器的比例。失望值的定義如式（1）所示，累積失望值為給定時間內算法的失望值之和。當排序器評估算法進行次最優選擇時，會累積失望值，這意味著最優排序器并沒有和自身進行交錯比較。在實驗中，令RUCB算法和本文提出的采樣算法的參數α=0.501，這可以確保RUCB算法不必進行太多的探索就可以得到可行解。

4.2 實驗結果

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

圖1 本文算法與SAVAGE算法的性能對比

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

圖2 本文算法與RUCB算法的累計失望值對比

最后，對比了RUCB算法和本文算法的穩定性，實驗結果如圖3所示。

圖3 本文算法與RUCB算法的穩定性對比

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

5 結束語

在信息檢索中，隨著用戶需求的不同需要不同的排序方法。當用戶提出個性化檢索需求時，系統往往需要對多個排序器進行評估，從而使用最優的排序器為用戶服務。本文研究了多個排序器的在線評估方法。根據現有研究結果將排序器評估形式化描述為

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

［1］ 鄧 輝.網頁學習排序算法研究［D］.武漢：華中科技大學，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］ 楊 子，唐 杰，李涓子.異構網絡學習排序模型及應用［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］ 吳佳金，楊志豪，林 原，等.基于改進Pairwise損失函數的排序學習方法［C］//第六屆全國信息檢索學術會議論文集.牡丹江：［出版者不詳］，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］ 花貴春，張 敏，劉奕群，等.基于查詢聚類的排序學習算法［J］.模式識別與人工智能，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é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武裝決斗土匪問題的排序器在線評估算法［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

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

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

2014-10-28

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