【勉強】レーティングシステム Massey's Method

レーティング

チェスやアメフト、ネットフリックスの映画おすすめ度など、世の中はレーティングに溢れている。
常に競争を続けてきた人類にとってレーティングは、知っておいて損のない知識であると思う。そこで、レーティングシステムの基本であるMasseyの方法について解説していこうと思う。

Massey's Method

Masseyの方法の基本原理は、試合の得点差を予想できるようなレーティングを作ろうというものである。
例えば、チーム$i$のレーティングを$r_i$としよう。この時、2つのチームiとjが対戦した時の得点差を$y_k$とすると

$$ r_i - r_j = y_k \tag{1}$$

となるようにレートを設定するのがこのMasseyの方法である。
m個のチームがn回試合を行った場合、この(1)を行列で表現して

$$ X r = y$$

とする事ができる。この時、Xは$ m \times n $の行列であり、$\pm1,0$を要素に持つ。
これをrについて解ければレートが求まるが、Xが正方行列でないので、正則にならず解くことができない。

そこで、rを次のように$r^*$に変換することを考える。

$$ r^* = \underset{r}{arg \space min} || X r - y ||^2$$

これを求めるには、$ || Xr - y ||^2$のr微分が0になる点を探せば良いので、

$$ \frac{d}{dr} (Xr - y)^T (Xr -y) = \frac{d}{dr} [r^T X^T X r - y^T X r - r^T X^T y + y^T y ] = 2 (X^T X r - X^T y ) = 0 $$

方程式は次のように変換される。

$$ M r = p \tag{2}$$
$$M = X^T X = T - P $$
$$p = X^T y = f - a$$

(2)には解が存在し、Masseyの方法ではこれを解いてレーティングを出せばよい。ここで、行列Mとベクトルpを新しく定義してある。MとpはT,P,f,aによって表すと簡単で、それぞれ次のような行列とベクトルである。

• Tは対角行列で対角要素 $ T_{ii} $はチームiの総試合数
• Pは非対角にのみ要素を持つ行列で非対角要素 $ P_{ij} $はチームiとチームjが戦った試合数
• ベクトルfの要素 $ f_i $はチームiが取った得点の合計
• ベクトルaの要素 $ a_i $はチームiが取られた失点の合計

ここで、$rank(M) < n$の為、これの解を一意に定めるために次の条件(3)を入れるのが通例である。

 r_1 + r_2 + ... + r_n = 0 \tag{3}

Masseyの方法　例題

Masseyの方法を使って私の大好きなゲーム(ロケットリーグ)のレートを求めてみる。
ロケットリーグは車でサッカーを行うゲームなのでサッカーだと思っていただいて結構である。RLCS(ロケットリーグチャンピオンシリーズ)のシーズン10の情報を使って試合結果を予想してみようと思う。グループAのラウンド1の試合結果をまとめると次のようになる。

teamA	teamB	score
RGE	VOLT	4-2
RGE	VOLT	4-1
RGE	VOLT	4-0
SQ	OXG	1-3
SQ	OXG	4-1
SQ	OXG	0-3
SQ	OXG	3-1
SQ	OXG	1-2

今回はラウンド1~4までの結果を利用してラウンド5の結果を予想してみようと思う。

はじめに、(2)に出てくる行列Mを求める、それぞれの試合数より行列Mは次のようになる

/	RGE	VOLT	SQ	OXG	V1
RGE	12	-3	0	-4	-5
VOLT	-3	9	-3	-3	0
SQ	0	-3	12	-5	-4
OXG	-4	-3	-5	15	-3
V1	-5	0	-4	-3	12

また、チームの得失点・総得点・総失点は

team	得失点 p	総得点 f	総失点 a
RGE	5	28	23
VOLT	-18	9	27
SQ	-1	25	26
OXG	1	30	29
V1	13	30	17

である。ここで条件(3)で適当な行を置き換えて(今回は1行目を置き換えた) 次の方程式を作る

\begin{pmatrix} 
  12 & -3 & 0 & -4 & -5 \\ 
  -3 & 9  & -3 & -3 & 0 \\
  0  & -3 & 12 & -5 & -4 \\
 -4  & -3 & -5 & 15 & -3 \\
  -5 & 0  & -4 & -3 & 12 
\end{pmatrix}
p
=
\begin{pmatrix}
5 \\ -18 \\ -1 \\ 1 \\ 13
\end{pmatrix}

これを解くと次のようにレートが求まる。

team	rate
RGE	0.53
VOLT	-1.82
SQ	-0.08
OXG	0.08
V1	1.30

これからシーズン5での得点差を予想すると次のようになる

試合	予想得点差	実際の得点差平均	勝敗予想	実際の勝敗
V1 vs VOLT	3.1	2.0	V1	V1
RGE vs SQ	0.61	1.0	RGE	RGE

得点差についてはピッタリ合っているわけではないが勝敗について予想できていることがわかる。
しかし、最も優勝に近かったのはOXGの3-4位であったにもかかわらず、レートでは V1 > RGE > OXG の順に強い事が分る。

Masseyの方法の改良

Masseyは先ほどのレートrから攻撃に関してのレートo、防御に関してのレートdを求める方法を提案した。
まず、レートrを次のように分解する。

$$ r = o + d $$

これを(2)式に代入して整理すると

$$ T o - P o + T d - P d = f - a $$

これより、$To - P d = f$ 、$ Po - Td = a$とする。
一つ目の式に$o = (r -d )$を代入して整理すると

$$ (T+P)d = Tr-f \tag{4}$$

これより、dが求まりoも求まる。

改良版Masseyの方法　例題

先ほどのロケットリーグの試合でのオフェンスレートとディフェンスレートを調べてみよう。

まず、ディフェンスレートを調べるために、(4)式を立てると

\begin{pmatrix} 
  12 & 3 & 0 & 4 & 5 \\ 
  3 & 9  & 3 & 3 & 0 \\
  0  & 3 & 12 & 5 & 4 \\
  4  & 3 & 5 & 15 & 3 \\
  5 & 0  & 4 & 3 & 12 
\end{pmatrix}
d
=
\begin{pmatrix} 
  12 & 0 & 0 & 0 & 0 \\ 
  0 & 9  & 0 & 0 & 0 \\
  0  & 0 & 12 & 0 & 0 \\
  0  & 0 & 0 & 15 & 0 \\
  0 & 0  & 0 & 0 & 12 
\end{pmatrix}
\begin{pmatrix}
0.53 \\ -1.82 \\ -0.08 \\ 0.08 \\1.3
\end{pmatrix}
-
\begin{pmatrix}
28 \\ 9 \\ 25 \\ 30 \\ 30
\end{pmatrix}

また、dが求まったら$o = r - d$であるので、オフェンスレートとディフェンスレートは次のようになる。

team	オフェンスレート	ディフェンスレート
RGE	1.57	-1.04
VOLT	-0.07	-1.76
SQ	1.26	-1.34
OXG	0.90	-0.82
V1	1.41	-0.12

これより、OXGが最もディフェンスとオフェンスのバランスがいいことが分った。
それに対してSQやRGEのディフェンスとオフェンスのレート差が大きい事が見て取れる。

さいごに

以上がMasseyの方法を使ったレートの決定方法である。
Masseyはこの方法を卒業論文で出したというので驚きである。

次回はColleyの方法というレーティングシステムについて解説しようと思う。