作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程

• 开发研究与工程应用 • 上一篇    下一篇

基于K武装决斗土匪问题的排序器在线评估算法

邓晓军,满君丰,欧阳旻   

  1. (湖南工业大学计算机与通信学院,湖南 株洲 412007)
  • 收稿日期:2014-10-28 出版日期:2015-09-15 发布日期:2015-09-15
  • 作者简介:邓晓军(1974-),男,副教授、硕士,主研方向:信息检索;满君丰,教授、博士;欧阳旻,讲师、硕士。
  • 基金资助:
    国家自然科学基金资助项目(61350011);湖南省自然科学基金资助项目(2015JJ2046,2014JJ2115);湖南省教育厅科研基金资助项目(12C0068)。

Online Evaluation Algorithm of Sorting Device Based on K-armed Dueling Bandits Problem

DENG Xiaojun,MAN Junfeng,OUYANG Min   

  1. (College of Computer and Communication,Hunan University of Technology,Zhuzhou 412007,China)
  • Received:2014-10-28 Online:2015-09-15 Published:2015-09-15

摘要: 对各种不同的排序器进行评估可以选出较优的排序器,从而为用户的个性化检索提供更好的排序结果。因此,为提高排序器评估结果的性能,根据现有研究结果将排序器评估形式化描述为K武装决斗土匪问题,提出一种基于采样的高效K武装决斗土匪算法,并分析2种模式下的求解目标。通过采样的方式模拟赛事并选出获胜者,根据置信上界在剩余排序器中选出挑战者,并将获胜者与挑战者进行交错比较,得出评分矩阵。实验结果表明,与SAVAGE算法及RUCB算法相比,该算法不仅准确性高,累计失望值小,而且具有较好的稳定性。

关键词: 信息检索, 排序器, 失望最小化, K武装决斗土匪检测, 在线评估算法

Abstract: 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 improve the performance of evaluation of sorting devices,this paper proposes a sampling-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 explore-then-exploit and ongoing regret minimization models.The algorithm simulates tournament based on sampling and chooses the winner,then chooses challenger according to upper confidence bound,and at last,compares the winner and the challenger using interleaved comparison,and gets the score matrix.Experimental results show that,compared with SAVAGE algorithm and RUCB algorithm,the proposed algorithm has higher detection accuracy,less cumulative regret,and better stability.

Key words: information retrieval, sorting device, regret minimization, K-armed dueling bandits, online evaluation method

中图分类号: