[1Z2] 機械学習-機械学習基礎(2)

[1Z2-05] 順位相関係数を保証するノイズありソートアルゴリズム

〇小宮山 純平¹ (1. 東京大学)

キーワード：PAC学習、ソート、確率的アルゴリズム

推薦，ランキング学習やAIゲームプログラムなどへの応用を念頭に置いて，本研究では動的に要素がクエリ可能な下でのペア比較による要素の選好順序の決定を考える．つまり，順序決定のアルゴリズムが、順序を効率的に決定するために次に比較するペアを選べるというものである．このような問題に対する完全な順序付けは比較回数が非常に大きくなるため，本研究は「大雑把な順序付け」を少ない比較回数，理論的な保証ありで行うことを目指した．アルゴリズムを提案しその性能を検証した．