ブログのとさか

技術的な話をしたりしなかったり

ロジスティック回帰とElo Ratingの関係

はじめに

対戦ゲームのレーティングシステムとして多く採用されているElo Ratingですが， その計算式を見ると内部で行っていることはロジスティック回帰とほとんど一致することがわかります． この記事ではロジスティック回帰とElo Ratingについて簡単に説明し，それらの関係について見ていきます．

また，ついでにこの事実を応用した格闘ゲームのキャラ相性解析のアイデアについて紹介したいと思います．

ロジスティック回帰

ロジスティック回帰は2値分類問題の推論や分析に利用される一般化線形モデルの一つです． ロジスティック回帰ではロジット（対数オッズ）を線形モデルで予測します．*1

このことは予測確率をp，線形モデルの出力をy，ロジスティック回帰の重みベクトルをw，バイアスをb，入力ベクトルをxとした時以下の式で表されます．

y=logit(p)=\log{\dfrac{p}{1-p}}=w^T x+b

予測確率の計算

予測確率pは以下の式で求まります．*2

p=logit^{-1}(y)=\dfrac{1}{1+e^{-y}}

更新式

ロジスティック回帰のパラメータw,bは一般的に最尤推定によって決定します． 最尤推定に勾配法を用いる場合，更新式は予測確率をp，正解ラベルをt，学習率（定数）を\etaとして以下のようになります．

w\leftarrow w - \eta(p-t)x

Elo Rating

Elo Ratingは結果が勝敗で表される対戦競技においてプレイヤーの相対的な実力を表す指標の一つです． チェスや将棋のような古典的なゲームや，スポーツ，デジタルゲームにおいてレーティングシステムとして利用されています． 強さを表す単純な指標としては勝率がありますが，勝率と異なりElo Ratingは対戦相手の強さを考慮して決定する数値のためより正確に実力を評価できます．*3

以下では概要のみ説明して詳しい導出等は行わないので，気になる方は以下のサイトを参考にしてください．

イロ・レーティングの意味と求め方を完全解説 | ワイズ

Elo Ratingは内部レートと表示レートに分けて解釈することができます． 内部レートはレートを計算するための数値で，表示レートは内部レートを人間が解釈しやすいように変換した数値です．*4 これは内部レートをr，表示レートをRとして以下の式で表せます．

R = 400 r + 1500

さて，内部レートrが計算しているものは，平均的強さのプレイヤーと対戦した時の勝率の常用対数オッズです． このことは平均的強さのプレイヤーとの勝率をpとした時以下の式で表せます．

r = \log_{10} \dfrac{p}{1-p}

なお，平均的強さのプレイヤーとは内部レートが0のプレイヤーのことを指します．

勝率の計算

まず，勝敗比は積によって推移するという仮定を置きます． つまり，プレイヤーXがプレイヤーYに勝率する確率をp_{XY}のように表し，プレイヤーX,Y,Zがいる時，以下の式が成り立つということです．

\dfrac{p_{XZ}}{1-p_{XZ}} = \dfrac{p_{XY}}{1-p_{XY}}\dfrac{p_{YZ}}{1-p_{YZ}}

この仮定と内部レートの定義を合わせると，プレイヤーAの内部レートをr_A，プレイヤーBの内部レートをr_Bとした時プレイヤーAの勝率p_{AB}は以下の式で計算できます．*5

p_{AB} =\dfrac{1}{1+10^{r_B-r_A}}

更新式

Elo Ratingの更新式はレートから予想される勝率をp，実際の勝敗をt（勝利時1，敗北時0），適当な定数をKとした時，プレイヤーAの内部レートr_Aの更新は以下の式で行われます．

r_A\leftarrow r_A + K(t_{AB}-p_{AB})

ロジスティック回帰とElo Ratingの関係

さて，ここまで読んだ方はお気づきでしょうが，ロジスティック回帰とElo Ratingの内部レートは対数オッズを計算しているという点で非常によく似ています．

実際ロジスティック回帰においてA,Bを自然数としてプレイヤーAとプレイヤーBの対戦結果p_{AB}を予測するとき，バイアスb=0かつベクトルxを以下のように設定すると，両者はほとんど同じものになります．

x_i = \left\{ \begin{array}{ll} 1 & (i=A)\\ -1 & (i=B)\\ 0 & (otherwise) \end{array} \right.

ロジスティック回帰の予測勝率は\dfrac{1}{1+e^{w_B-w_A}}，Elo Ratingによる予測勝率は\dfrac{1}{1+10^{r_B-r_A}}なので，重みwがレートを表すベクトルであるとみなすと，両者の違いは指数の底（eまたは10）のみです． またロジスティック回帰のとElo Ratingの更新式は予測勝率と勝敗結果が等しく，K=\etaの時完全に一致します．

以上のことをまとめると，（指数の差は定数倍の差でしかないので無視した場合）Elo Ratingが本質的に行なっていることはロジスティック回帰による勝敗予測であり，強さの指標として重みを用いていると解釈できます．*6

格闘ゲームのキャラ相性解析

バイアス0のロジスティック回帰はElo Ratingの拡張としてみなせることがわかりました． このことを利用して格闘ゲームのキャラクター相性の解析とその解釈を行う方法を考えたいと思います． 具体的にはP,Q,X,Yを自然数として，プレイヤーPがキャラクターXを用い，プレイヤーQがキャラクターYを用いて対戦した場合，入力xを以下のように設定することでバイアス0のロジスティック回帰で勝率予測を行います． なお，Cをキャラクターの総数を表す定数とします．

x_i = \left\{ \begin{array}{ll} 1 & (i=X\times C + Y)\\ 1 & (i=C\times C + P)\\ -1 & (i=C\times C + Q)\\ 0 & (otherwise) \end{array} \right.

これらの重みは以下のように解釈できます．

  • w_{C\times C+P}：キャラクター性能と分離したプレイヤーPの強さ
  • w_{C\times C+Q}：キャラクター性能と分離したプレイヤーQの強さ
  • w_{X\times C+ Y}：キャラクターXとキャラクターYの相性

ここで重要なのはキャラクター相性の数値w_{X\times C+ Y}です． この数値の大小や勝率への変換により相性表を作ることも可能ですが，ユーザーがElo Ratingに馴染み深いという前提では以下の変換により相性値を表現することが直感につながると思われます．

M_{XY} = \dfrac{400}{\log_{e} 10}w_{X\times C+ Y}

この式では底の変換公式によりElo Ratingの内部レートと同じスケールに変換し，Elo Ratingと同様に表示レートに変換しています． これにより「同等の実力のプレイヤー同士の場合キャラクターX,Yの相性はレート差M_{XY}分である」という解釈が可能になります．*7

おわりに

この記事ではロジスティック回帰とElo Ratingの関係について説明し，それを応用したアイデアについて説明しました． 実は今回解説した内容について思いついたのはスマブラSPの対戦サイトの統計分析をしようと思ったことがきっかけだったので， 対戦データが手に入り次第実際に説明したアイデアで分析した結果についても紹介したいと思います．

*1:確率ではなく対数オッズを予測する理由は，確率が0から1の値に収まらなければいけないのに対して，対数オッズは-∞から+∞の値を取って良いため線形モデルにとって都合が良いからです．

*2:このロジット関数の逆関数のことをロジスティック関数と言います．NNでお馴染みのシグモイド関数と同じものです．

*3:勝率は実力が高い相手と多く対戦するプレイヤーと実力が低い相手と多く対戦するプレイヤーの強さを比較しようとした場合に不正確な結果を招きます．

*4:内部レートや表示レートという言い方はこの記事で説明しやすいように便宜的に名付けたものであることに注意してください．

*5:ちなみによく強者の指標として用いられるレート2000はレート1500に対して95%程度の勝率となります．

*6:なお，Elo Ratingでは一度の勝敗結果によって一度だけレートを更新するので，勾配法で1エポック更新しているとみなせます．

*7:同じ変換でキャラクター性能と分離したプレイヤーの強さの表示もできますが，この数値については議論の余地があります．