Sabrou-mal サブロウ丸

主にプログラミングと数学

レイティング・ランキングの数理

レイティング・ランキングの数理の各章の概要をまとめたものです。本当に概要をまとめただけなので, より詳しく知りたい方は書籍を参考にしてください。

[商品価格に関しましては、リンクが作成された時点と現時点で情報が変更されている場合がございます。]

レイティング・ランキングの数理 No.1は誰か?
価格：5400円（税込、送料別) (2018/12/2時点)

楽天で購入

用語ですが, レイティングとは, 各チームに強さを表す数値(基本的には実数)を割り当てることで, ランキングとは各チームに順位を割り当てることです。

第2~7, 10章では, レイティングを計算する手法がメインで説明されています。そして, その結果からランキングを計算できるという筋立てですが, 第8章では, レイティングを計算せずに, 直接ランキングを計算する手法が説明されています。

目次

第2章 Masseyの手法
第3章 Colleyの手法
第4章 Keenerの手法
第5章 Eloのシステム
第6章 Markovの手法
第7章攻撃力/守備力レイティング手法
第8章再順序化によるランキング
第9章ポイントスプレッド
第10章ユーザープレファンスのレイティング
第11章引き分けの扱い
第12章重み付けを組み込む
第13章「もしも」シナリオと感応度
第14章ランキング集約 - その1
第15章ランキング集約 - その2
第16章比較の方法

第2章 Masseyの手法

[ 概要 ]

チームのレイティング差が対戦した時の得点差になるようにする
正規方程式を解く問題に帰着させる
上記のレイティングから, 攻撃/守備レイティングを計算する

第3章 Colleyの手法

[ 概要 ]

勝率に若干の修正を加えたものをレイティングとする
対戦相手への勝率の和が $\frac{1}{2} \times$ (対戦数)と仮定して, 線型方程式を解く問題に帰着させる
引き分けの試合は, 事実上試合なしとして無視される

第4章 Keenerの手法

[ 概要 ]

チームのレイティング $r_i$ は, そのチームの強さ $s_i$ に一様に比例する $s_i =\lambda r_i$ と仮定する
チーム $i$ の強さを他チームのレイティングの線形和によって表す
行列の固有ベクトルを求める問題に帰着
必要であれば行列に簡単な操作を加えることで, 反復計算で固有ベクトルを求めることができる

第5章 Eloのシステム

[ 概要 ]

試合結果によってレイティングを逐次更新する
$r^{new} = r^{old} + K(S-\mu)$ $K:$ 定数, $S:$ 勝敗, $\mu :$ 勝率
勝率がレイティングの差を説明変数とするロジスティック関数に従うと仮定する

第6章 Markovの手法

[ 概要 ]

ノードレイティングアルゴリズム
試合結果から投票グラフを作成し, それから確率遷移行列に変形する
確率遷移行列に従って動くお天気ファンの滞在時間をレイティングとする
支配的固有ベクトルを求める問題に帰着

第7章攻撃力/守備力レイティング手法

[ 概要 ]

大きいほど強い攻撃力を表すレイティング $o$ と小さいほど強い守備力を表すレイティング $d$ を同時に求める
$o$ を $d$ の逆数の線形和で, $d$ を $o$ の逆数の線形和で定義する
条件を満たす行列による反復計算により, $o, d$ を求めることができる
相互に影響し合う二種類のレイティングを同時に求めることができる

攻撃力/守備力

ウェブにおけるハブ/オーソリティー

映画の評価/ユーザーの質

第8章再順序化によるランキング

[ 概要 ]

レイティングを介さずに, ランキングを出力する
基本ランキング差分行列に近くなるように, 置換行列を求める
二次整数問題として定式化されるが, 遺伝的最適化が推奨される

第9章ポイントスプレッド

[ 概要 ]

あるチーム同士の対戦の得点差を予測したい
レイティングの差がチーム同士の得点差になるようにしたい
Masseyとの違いは任意のチームの一回の対戦結果しか用いないこと

第10章ユーザープレファンスのレイティング

[ 概要 ]

ユーザーの評価から, アイテムのレイティングを与える
ポイントスプレッド(第9章)やMarkov(第6章)が使えるような, アイテム間の比較を与える (アイテム間の比較を行うことは対戦に相当)

第11章引き分けの扱い

[ 概要 ]

引き分けが多数存在するような場合(映画のレビューなど)は, 引き分けを考慮に入れるかどうかで最終的なレイティングに影響を受ける
スポーツのオーバータイムやサドンデス決着もほぼ引き分けとみなせる

第12章重み付けを組み込む

[ 概要 ]

シーズンを通して, 試合の重要度をレイティングに組み込む
勝数, 得点差を重要な試合ほど水増しする

第13章「もしも」シナリオと感応度

[ 概要 ]

感応度: 入力の変化が出力に与える影響度

第14章ランキング集約 - その1

[ 概要 ]

いくつかのランキングを統合して, 一つのランキングを作る
ランキングの結果から模擬試合を作成し, その勝敗を用いてレイティング/ランキングを行う
ランキング集約後に局所Kemeny最適を用いて, ランキングを修正することができる
レイティング距離行列を規格化することで, レイティングを集約することもできる

第15章ランキング集約 - その2

[ 概要 ]

BILP(二値整数線形計画法)により, 順序変数を用いてランキングを求める
$O(n)$ 程度の簡単なテストで, いくつかの最適な別解を見つけることは可能である
レイティング差分行列を丘形状に並び替えることで, ランキングを獲得する方法もある

第16章比較の方法

[ 概要 ]

ランキングリスト同士の比較を行う
比較するランキングリストは完全に一致している必要がない
ランキングリストの質の判定方法