比較バンディット問題における最適なアルゴリズム～ランキング手法比較や選好情報学習を目的として～

• Item type: SIG Technical Reports(1)
• 公開日: 2015-06-16
• タイトル: 比較バンディット問題における最適なアルゴリズム～ランキング手法比較や選好情報学習を目的として～
• タイトル / 言語: en
• タイトル: Optimal Algorithms in Dueling Bandit Problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学
• 著者所属: 東京大学
• 著者所属: 京都大学
• 著者所属: 東京大学
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者所属(英): en
• 著者所属(英): Kyoto University
• 著者所属(英): en
• 著者所属(英): The University of Tokyo
• 著者名: 小宮山, 純平; 本多, 淳也; 鹿島, 久嗣; 中川, 裕志
• 著者名(英): Junpei, Komiyama; Junya, Honda; Hisashi, Kashima; Hiroshi, Nakagawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: バンディット問題 （multi-armed bandit problem） は，情報の活用と探索の間のトレードオフをモデル化した問題である．バンディット問題にはいくつかの亜種があるが，そのうち比較バンデイット問題 （dueling bandit problem） と呼ばれるものは，一対比較によるフィードバックを用いて最適化を行う．比較バンディット問題の枠組みを用いることによって，検索エンジンのランキング手法の比較や，人間の選好抽出の問題に対して，効率的な最適化を行うことができる．本研究では，比較バンディット問題における理論的な性能限界およびそれを達成するアルゴリズムを提案する．このアルゴリズムは，経験尤度を用いた通常のバンディット問題におけるアルゴリズム （本多，竹村，2010） の比較バンデイット問題への拡張である．提案手法を評価するため，検索エンジンの実データにおけるランキング手法の比較や，寿司データセット （神嶌，2003） などによる人間の選好抽出における性能を既存手法と比較する．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: We study the K-armed dueling bandit problem, a variation of the standard stochastic bandit problem where the feedback is limited to relative comparisons of a pair of arms. Algorithms that are inspired by the Deterministic Minimum Empirical Divergence algorithm (Honda and Takemura, 2010) are proposed. The proposed algorithms are found to have a regret upper bound that matches the lower bound. Experimental comparisons of dueling bandit algorithms show that the proposed algorithms significantly outperform existing ones.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10505667
• 書誌情報: 研究報告数理モデル化と問題解決（MPS）; 巻 2015-MPS-103, 号 14, p. 1-8, 発行日 2015-06-16
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8833
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会