概要
Modeling Intransitivity in Matchup and Comparison Data (WSDM 2016)(pdf)
二人のプレイヤーが戦い，勝敗が決まるゲームのモデリングにおいては通常，各プレイヤーの強さは一元的である．よって，推定されたモデルでは推移律が成立する(aがbより，bがcより強いならば，aはcより強い，といった関係)．
この研究では，intransitivity(反推移性) を導入し，3すくみの関係をモデリングする(例 : じゃんけんの手)．
提案手法 : blade-chest-dist-model
モデルは非常にシンプル．
まず，ベースとして Bradley-Terry model (BTモデル) を用いる．
これは，プレイヤーa，bについて
とする．
これは，プレイヤーごとの強さがあり，一方が勝つ確率は強さの差に比例する，というモデル．
このモデルを発展させるために次の例を考える．
今，二人のプレイヤー a，b が剣 (blade) を持って戦っているとする．この時，剣だけでなく，「胸 (chest) 」を導入する．そして，各プレイヤーは胸を攻撃されたら負ける，という状況を考える．
すると，勝敗は「a の剣から b の胸までの距離」と「b の剣から a の胸までの距離」のどちらが短いかによって決定されることになる．
これを式で表すと
となる．これが提案する blade-chest-dist-model．
あとはユークリッド距離と内積，2つのモデル
を提案する．ここで，などのベクトルは好きな次元で表現する．
あとはSGDで尤度最大化．
実験
データが面白い．
まず人工データでじゃんけん(rock-paper-scissors game) と，もう少し複雑な Rock-paper-scissors-lizard-Spock で実験．推定したベクトルを可視化すると3すくみの関係が見える．
続いて Video Game でこの関係が成立するかどうかを示すために Starcraft2 Wings of Liberty，Starcraft2 Heart of the Swarm，DotA2で実験．
前者2ではBTモデルより有意に改善．DotA2で改善しなかったのはチーム対チームのゲームだからではないか，という考察．
プロスポーツで再現するか，ということでテニスのデータで実験するもBTモデルと大して変わらず．理由として (1) プロは弱点を作らずオールラウンドに強くなるから， (2) 試合形式がトーナメントだから，という考察．
続いて，プレイヤー間の強さの関係性 を推定する実験．スト4のキャラクター間の matchup を正解データとするとこちらも有意に改善．
最後にpariwiseなデータではなくランキング全体を推定する(並び替える)実験．BTモデルより(幅は小さいものの)改善．
去年の夏頃，「3すくみのモデルがあると面白いのでは」と人と話をしていて，「ではどうやってその3すくみの関係を定式化するのか」というところで話が止まっていた．2つの要素の比較で解くという，シンプルなモデルであり，読んでいて楽しかった．
