レイティングアルゴリズム入門
- 2015.12.08
- Go language
- by Masashi Salvador Mitsuzawa
はじめまして。pairsのサーバサイドエンジニアの@MasashiSalvadorと申します。エウレカには8月にジョインしました。現在はGoフルスクラッチプロジェクトのデータベースマイグレーションのテストを担当しています。マイグレーションに関しては弊社エンジニア鉄本の記事がすでに掲載されていると思いますので、僕の方は最近調査しているレイティングのアルゴリズムについてざっくりと紹介したいと思います。
レイティング=スコアリングとは？
並び順の問題とよくある例
アプリケーション内で何かを表示する際、どういう表示順にするかは重要な問題です。並び替えることとはつまり、並び替えのキーを決めることといえます。よくある単純な例としては、並び替えのキーとして日付（新着順）やお気に入り登録数（人気順）が用いる例が挙げられます。こういったケースでは並び替えのキーをアルゴリズムでわざわざ計算する必要はありません。そして、仕様としてはそれで十分な場合も多々あります。一方で、アルゴリズムを用いて計算されたスコアを用いた方がユーザの利便性を向上する場合もあります。例としては
- webページの検索結果の表示順
- 広告に表示される商品の表示順
- 通販サイトに表示されるおすすめ商品の表示順
などを挙げることができます。例えば1.に関しては、Googleはかの有名なPageRankアルゴリズムを用いています。これは、ウェブページを数学的構造のグラフの頂点、ウェブサイト間のリンクを枝と見なし、そのグラフ構造から決定される数学的な量をランキングのスコアとして用いる方法です。PageRankに関してはウェブ上には言語を問わず多くの解説記事が存在します。将来的にはAuthorRankという別のランキングアルゴリズムを用いるという話も挙がっていますね（そしてそれは今回紹介するレイティングアルゴリズムを突き詰めていくと潜んでいます)。2.や3.に関しては、ユーザの行動履歴を利用した協調フィルタリングや、バンディットアルゴリズム、クリック率の予測アルゴリズムなどがよく用いられます。
レイティングの実例と参考書籍
ウェブの発達と共にレイティングやランキングをどう決定するかは注目を浴びるようになりました。ビッグデータという単語がバズワードになったり、機械学習系の記事がバズっていることはそれをよく表しているでしょう。スコアリング/ランキングの問題自体は実は古くから研究されています。例えば、世界大学ランキング、FIFAのランキング、チェスのレイティング、国別の幸福度ランキングなどです。本記事ではGoogleのPageRankの解説本も書いているAmy N. Langville, and Carl D. D. Meyeによる Who's #1?: The Science of Rating and Ranking
で紹介されている基礎的なスコアリングのアルゴリズムに関して紹介し、実データを用いて軽く実験してます。
Kindle版が安かったので洋書で読んでいましたが…日本語訳も出ているようですね。割りと平易な英語で書かれており、大変面白い本なのでおすすめです。
スコアリング基礎(Massey’s Algorithm)
アメリカの大学アメリカンフットボールチームをレイティングするために作られた、非常に平易であるがある程度強力なMasseyのアルゴリズムを紹介します。Masseyのアルゴリズムは全nチームが全m試合を行う時のk番目の試合の点差を元に各チームのスコアを決め、ランキングを決定するアルゴリズムです。
表記について
本記事ではWho's #1?: The Science of Rating and Rankingにならい、下記表記を採用します。
考え方(モデル)
ある試合の点差は対戦するチームのレイティングで決定される/予測できるという考え方を用います。
これを数式で表すと、
となります。k試合目の点差は、その試合で対戦するチームiとチームjのレイティングによって決定されるということをシンプルに表しています。試合が実際に行われると、右辺のyは既知の値となるので、求めたいチームのレイティングを未知数とした方程式系を得ることができます。
例えば、5チームあるとして…
となります。同様に、一般の場合も
のように表すことができます。この線形方程式を解いて、各チームの未知のレイティングを並べたベクトルrを求めることができれば良いわけです。
数値解とその解釈
ここで、解くべき方程式に関して、変数の数と式の数を考えてみます。大抵の場合、チーム数nに対して試合数mはかなり大きいです。リーグ戦と考えると納得できると思います。つまり、大抵の場合は n << mであると言えます。つまり、大抵の場合変数の数よりも、方程式の数が圧倒的に多いと言えます。高校数学を思い出してみると、こういう場合は理論解は存在しません。
方程式の解は要するに代入して式が成り立てばいいわけですから、数値的に最も近い解を探すことにします。この際によく用いられるのが最小二乗法です。つまり、代入した時の値と0の差の二乗が最も小さくなるような解を求めます。
つまり、最小化問題
をとけばよいわけです。rを変数と思って微分するなどすると、この最小化問題の解、つまり元の方程式の最小二乗解は、方程式
を満たすことがわかります。ここで、右辺について、
と定義し、Xの転置の各行について考えると、各行は各チームに対応しk列目はk試合目に対応し、i行目とj行目に関して
k試合目でチームiとチームjが対戦していない = i行k列/j行i列共に0
k試合目でチームiとチームjが対戦している = i行k列/j行i列は1/-1
であることがわかります。このことを考えると、Mのi行j列要素は、Xの転置のi行目とXのj列目の掛け算で求められるので、
i行i列はチームiの総試合数
(i行j列はチームiとチームjの総試合数) x (-1)
となることがわかります。定義に試合が使われているため、このようにMを解釈可能で、実際に計算しなくとも値を決められるのがMessayの着眼点の良いところです。
右辺を考えると…右辺の各行はチームの総得点差になるのでこれをpとおいて、求めるrは、
を満たすrとなる。
ところが、少し考えると分かるのですが、この方程式はrank(M) < nであるため、解が一意に定まらない方程式であることがわかります。解が存在しなかったり定まらなかったりと、苦悩は続きます。Messayはworkaroundとして、上記の方程式において、Mの適当な行をすべて1、対応するyを0にすることを提案しました。これは、方程式に
つまり、「すべてのチームのスコアを足すと1になる」という制約を付すのに対応しています。これにより方程式が解けるようになるので、あとは解くことで各チームのレイティングが求まります。
実データを用いた例(セ・リーグのスコアリング)
さて、僕はプロ野球が大好きなので今シーズンの試合データを用いてセリーグの各球団のスコアリングを行ってみたいと思います。web上から集めてきたスコアリングデータ(*)を用います。
解くべき方程式は（添字をチーム名の頭文字にしてます、ヤクルト~ベイスターズまでセ・リーグ6球団)
ここに先ほどお話したworkaroundを実施して、
これを解きます。
解として、
を得ることができますが、得点差とうまいこと一致しません。
workaroundを行う際に変更している行にどれくらい依存しているかを調べるため、
6行目でなく5行目にworkaroundを適用すると
を得ることができます。
workaoundを実施する行に結果が依存するのがいけてないですが、
スコアリング同士を比較する手法も知られているため、いいやり口を探せば良さそうです。
サンプルコード
Goでの数値計算は発展途上です(python使えよという話はあります)
そもそもそういう用途に向く言語なのか（多分向かない)…という問題はありますが、
トライ精神が大事なので、数学ライブラリを用いて軽く上記の例の計算例を書いておきます。
向くかどうか?という議論に関してはgo numerical computingとかでググるとスレッドが色々出てきます。
package main
import (
'fmt'
'github.com/davecgh/go-spew/spew'
// Goでの数学演算はgonumが良いらしい
// LU分解 / cholesky分解など各種行列の分解
// 条件数
// Solve(逆行列を使わない)
// など、基本的な機能が備わっています。
'github.com/gonum/matrix/mat64'
//github.com/skelterjohn/go.matrixはMatlabっぽく書けますが、
//まったくメンテされていないようなのでおすすめしません(おそらく実験的なライブラリです
)
func main() {
M := mat64.NewDense(6, 6, []float64{
5.0, -1.0, -1.0, -1.0, -1.0, -1.0,
-1.0, 5.0, -1.0, -1.0, -1.0, -1.0,
-1.0, -1.0, 5.0, -1.0, -1.0, -1.0,
-1.0, -1.0, -1.0, 5.0, -1.0, -1.0,
1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
-1.0, -1.0, -1.0, 1.0, -1.0, 5.0,
})
p := mat64.NewDense(6, 1, []float64{
2.24, 1.84, -4.60, 1.28, 0.0, -3.4,
})
r := mat64.NewDense(6, 1, []float64{
0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
})
err := r.Solve(M, p)
if err != nil {
fmt.Println('error in solve Mr = p')
}
spew.Dump(r)
}
補足(攻撃レイティング/守備レイティング)
書き損なってしまったのですが、Messayのレイティングには、応用編として攻撃レイティング/守備レイティングという概念を導入することができ、上記で求めたレイティングと同様に簡単な計算で求めることができます。こちらは解説とサンプルを追記できたらしたいと思います。
webへの応用
例にはスポーツの試合を挙げてしまいましたが、Messayの考え方の良い所は対象物同士の関連性を「試合」とみなすことができ、その「試合」における「得点差」の概念との対応関係を考えることができれば、どんな事象にも応用可能である所です。例えば、少々乱暴なモデル化ですが
上記の様にどれがクリックされるかが人気度を表すようなケースにおいて、
各要素のレイティングを考える場合にシンプルに応用できそうです。例えばナイーブな例として試合に関しては、
表示され、いづれかの要素がクリックされるたびに、クリックされた要素と他の要素が試合をする
図の左の例では、2がクリックされた時は、2と1、2と3、2と4が試合をして2が勝ったとみなし、
右の例で3がクリックされた場合は3と1、3と2、3と4、3と5がそれぞれ試合をしたとみなせば良さそうです。「得点差」に関しては
1. (良い場所)=(左上や上部)に表示されているのにクリックされなかった場合は失点したとみなす
2. クリックされた要素は表示位置に応じてX点で勝っているものとする
などとすると「得点差」の概念を導入できそうです。
例えば右の例で、「得点」を
クリックされた要素 ... 自分より上に要素の数 + 1点
クリックされなかった要素 ... 自分より上がクリックされた場合 → 0点
... 自分より下がクリックされた場合 → (-クリックされた要素までの位置差)
などと定義できそうです。この場合、3がクリックされたとすると、
3 VS 1 # スコア 3 対 -2
3 VS 2 # スコア 2 対 -1
3 VS 4 # スコア 1 対 0
3 VS 5 # スコア 1 対 0
のように「試合」を行い、「得点差」がついたと考えることができます。
もちろん
- インプレッションの数による正規化(数が多いほど影響を受けやすそう）
- 「得点」の定義調整
等の細かな調整が運用にのせるためには必要でしょう。
人工データで実験して結果を載せようと思ったのですが…やはり実データを用いたほうが良さそうなので別途検討することにしました。
レイティングの深みへ
本記事ではごく初歩的な内容を紹介しましたが、紹介した書籍を読み進めると数学的にもお話としてもかなり面白くなってきます。例えば、
- スプレッド(賭け事のオッズ等に関連するレイティング)
- スポーツのレイティング(その他色々なアルゴリズム)
- ユーザの好みのレイティング(レコメンデーションなどに用いる)
- ランキングの集約(複数のランキングの統合方法)
などトピックは尽きません。今後更に調べを進め、色々と実装ができたらブログにしたいと思います!
奥深いジャンルなので、深みを極めればきっとサービス改善にも繋げられるはず!
僕自身詳しい方と勉強会など開いてみたいなと思うジャンルではあるので、勉強会興味あります!という方は
@MasashiSalvadorまでご連絡ください!
スペースに関してはご心配なく弊社オフィスのイベントスペースをお貸し出しします!
https://www.doorkeeper.jp/%E4%BC%9A%E5%A0%B4/eureka
データを見ながらサービスを圧倒的に改善したいエンジニアの方も積極採用しています。
一緒にサービス成長の夢を遂げませんか？ジョイナース！！！
- 2015.12.08
- Go language
- by Masashi Salvador Mitsuzawa
はじめまして。pairsのサーバサイドエンジニアの@MasashiSalvadorと申します。エウレカには8月にジョインしました。現在はGoフルスクラッチプロジェクトのデータベースマイグレーションのテストを担当しています。マイグレーションに関しては弊社エンジニア鉄本の記事がすでに掲載されていると思いますので、僕の方は最近調査しているレイティングのアルゴリズムについてざっくりと紹介したいと思います。
レイティング=スコアリングとは？
並び順の問題とよくある例
アプリケーション内で何かを表示する際、どういう表示順にするかは重要な問題です。並び替えることとはつまり、並び替えのキーを決めることといえます。よくある単純な例としては、並び替えのキーとして日付（新着順）やお気に入り登録数（人気順）が用いる例が挙げられます。こういったケースでは並び替えのキーをアルゴリズムでわざわざ計算する必要はありません。そして、仕様としてはそれで十分な場合も多々あります。一方で、アルゴリズムを用いて計算されたスコアを用いた方がユーザの利便性を向上する場合もあります。例としては
- webページの検索結果の表示順
- 広告に表示される商品の表示順
- 通販サイトに表示されるおすすめ商品の表示順
などを挙げることができます。例えば1.に関しては、Googleはかの有名なPageRankアルゴリズムを用いています。これは、ウェブページを数学的構造のグラフの頂点、ウェブサイト間のリンクを枝と見なし、そのグラフ構造から決定される数学的な量をランキングのスコアとして用いる方法です。PageRankに関してはウェブ上には言語を問わず多くの解説記事が存在します。将来的にはAuthorRankという別のランキングアルゴリズムを用いるという話も挙がっていますね（そしてそれは今回紹介するレイティングアルゴリズムを突き詰めていくと潜んでいます)。2.や3.に関しては、ユーザの行動履歴を利用した協調フィルタリングや、バンディットアルゴリズム、クリック率の予測アルゴリズムなどがよく用いられます。
レイティングの実例と参考書籍
ウェブの発達と共にレイティングやランキングをどう決定するかは注目を浴びるようになりました。ビッグデータという単語がバズワードになったり、機械学習系の記事がバズっていることはそれをよく表しているでしょう。スコアリング/ランキングの問題自体は実は古くから研究されています。例えば、世界大学ランキング、FIFAのランキング、チェスのレイティング、国別の幸福度ランキングなどです。本記事ではGoogleのPageRankの解説本も書いているAmy N. Langville, and Carl D. D. Meyeによる Who's #1?: The Science of Rating and Ranking
で紹介されている基礎的なスコアリングのアルゴリズムに関して紹介し、実データを用いて軽く実験してます。
Kindle版が安かったので洋書で読んでいましたが…日本語訳も出ているようですね。割りと平易な英語で書かれており、大変面白い本なのでおすすめです。
スコアリング基礎(Massey’s Algorithm)
アメリカの大学アメリカンフットボールチームをレイティングするために作られた、非常に平易であるがある程度強力なMasseyのアルゴリズムを紹介します。Masseyのアルゴリズムは全nチームが全m試合を行う時のk番目の試合の点差を元に各チームのスコアを決め、ランキングを決定するアルゴリズムです。
表記について
本記事ではWho's #1?: The Science of Rating and Rankingにならい、下記表記を採用します。
考え方(モデル)
ある試合の点差は対戦するチームのレイティングで決定される/予測できるという考え方を用います。
これを数式で表すと、
となります。k試合目の点差は、その試合で対戦するチームiとチームjのレイティングによって決定されるということをシンプルに表しています。試合が実際に行われると、右辺のyは既知の値となるので、求めたいチームのレイティングを未知数とした方程式系を得ることができます。
例えば、5チームあるとして…
となります。同様に、一般の場合も
のように表すことができます。この線形方程式を解いて、各チームの未知のレイティングを並べたベクトルrを求めることができれば良いわけです。
数値解とその解釈
ここで、解くべき方程式に関して、変数の数と式の数を考えてみます。大抵の場合、チーム数nに対して試合数mはかなり大きいです。リーグ戦と考えると納得できると思います。つまり、大抵の場合は n << mであると言えます。つまり、大抵の場合変数の数よりも、方程式の数が圧倒的に多いと言えます。高校数学を思い出してみると、こういう場合は理論解は存在しません。
方程式の解は要するに代入して式が成り立てばいいわけですから、数値的に最も近い解を探すことにします。この際によく用いられるのが最小二乗法です。つまり、代入した時の値と0の差の二乗が最も小さくなるような解を求めます。
つまり、最小化問題
をとけばよいわけです。rを変数と思って微分するなどすると、この最小化問題の解、つまり元の方程式の最小二乗解は、方程式
を満たすことがわかります。ここで、右辺について、
と定義し、Xの転置の各行について考えると、各行は各チームに対応しk列目はk試合目に対応し、i行目とj行目に関して
k試合目でチームiとチームjが対戦していない = i行k列/j行i列共に0 k試合目でチームiとチームjが対戦している = i行k列/j行i列は1/-1
であることがわかります。このことを考えると、Mのi行j列要素は、Xの転置のi行目とXのj列目の掛け算で求められるので、
i行i列はチームiの総試合数 (i行j列はチームiとチームjの総試合数) x (-1)
となることがわかります。定義に試合が使われているため、このようにMを解釈可能で、実際に計算しなくとも値を決められるのがMessayの着眼点の良いところです。
右辺を考えると…右辺の各行はチームの総得点差になるのでこれをpとおいて、求めるrは、
を満たすrとなる。
ところが、少し考えると分かるのですが、この方程式はrank(M) < nであるため、解が一意に定まらない方程式であることがわかります。解が存在しなかったり定まらなかったりと、苦悩は続きます。Messayはworkaroundとして、上記の方程式において、Mの適当な行をすべて1、対応するyを0にすることを提案しました。これは、方程式に
つまり、「すべてのチームのスコアを足すと1になる」という制約を付すのに対応しています。これにより方程式が解けるようになるので、あとは解くことで各チームのレイティングが求まります。
実データを用いた例(セ・リーグのスコアリング)
さて、僕はプロ野球が大好きなので今シーズンの試合データを用いてセリーグの各球団のスコアリングを行ってみたいと思います。web上から集めてきたスコアリングデータ(*)を用います。
解くべき方程式は（添字をチーム名の頭文字にしてます、ヤクルト~ベイスターズまでセ・リーグ6球団)
ここに先ほどお話したworkaroundを実施して、
これを解きます。
解として、
を得ることができますが、得点差とうまいこと一致しません。
workaroundを行う際に変更している行にどれくらい依存しているかを調べるため、
6行目でなく5行目にworkaroundを適用すると
を得ることができます。
workaoundを実施する行に結果が依存するのがいけてないですが、
スコアリング同士を比較する手法も知られているため、いいやり口を探せば良さそうです。
サンプルコード
Goでの数値計算は発展途上です(python使えよという話はあります)
そもそもそういう用途に向く言語なのか（多分向かない)…という問題はありますが、
トライ精神が大事なので、数学ライブラリを用いて軽く上記の例の計算例を書いておきます。
向くかどうか?という議論に関してはgo numerical computingとかでググるとスレッドが色々出てきます。
package main
import (
'fmt'
'github.com/davecgh/go-spew/spew'
// Goでの数学演算はgonumが良いらしい
// LU分解 / cholesky分解など各種行列の分解
// 条件数
// Solve(逆行列を使わない)
// など、基本的な機能が備わっています。
'github.com/gonum/matrix/mat64'
//github.com/skelterjohn/go.matrixはMatlabっぽく書けますが、
//まったくメンテされていないようなのでおすすめしません(おそらく実験的なライブラリです
)
func main() {
M := mat64.NewDense(6, 6, []float64{
5.0, -1.0, -1.0, -1.0, -1.0, -1.0,
-1.0, 5.0, -1.0, -1.0, -1.0, -1.0,
-1.0, -1.0, 5.0, -1.0, -1.0, -1.0,
-1.0, -1.0, -1.0, 5.0, -1.0, -1.0,
1.0, 1.0, 1.0, 1.0, 1.0, 1.0,
-1.0, -1.0, -1.0, 1.0, -1.0, 5.0,
})
p := mat64.NewDense(6, 1, []float64{
2.24, 1.84, -4.60, 1.28, 0.0, -3.4,
})
r := mat64.NewDense(6, 1, []float64{
0.0, 0.0, 0.0, 0.0, 0.0, 0.0,
})
err := r.Solve(M, p)
if err != nil {
fmt.Println('error in solve Mr = p')
}
spew.Dump(r)
}
補足(攻撃レイティング/守備レイティング)
書き損なってしまったのですが、Messayのレイティングには、応用編として攻撃レイティング/守備レイティングという概念を導入することができ、上記で求めたレイティングと同様に簡単な計算で求めることができます。こちらは解説とサンプルを追記できたらしたいと思います。
webへの応用
例にはスポーツの試合を挙げてしまいましたが、Messayの考え方の良い所は対象物同士の関連性を「試合」とみなすことができ、その「試合」における「得点差」の概念との対応関係を考えることができれば、どんな事象にも応用可能である所です。例えば、少々乱暴なモデル化ですが
上記の様にどれがクリックされるかが人気度を表すようなケースにおいて、
各要素のレイティングを考える場合にシンプルに応用できそうです。例えばナイーブな例として試合に関しては、
表示され、いづれかの要素がクリックされるたびに、クリックされた要素と他の要素が試合をする
図の左の例では、2がクリックされた時は、2と1、2と3、2と4が試合をして2が勝ったとみなし、
右の例で3がクリックされた場合は3と1、3と2、3と4、3と5がそれぞれ試合をしたとみなせば良さそうです。「得点差」に関しては
1. (良い場所)=(左上や上部)に表示されているのにクリックされなかった場合は失点したとみなす 2. クリックされた要素は表示位置に応じてX点で勝っているものとする
などとすると「得点差」の概念を導入できそうです。
例えば右の例で、「得点」を
クリックされた要素 ... 自分より上に要素の数 + 1点 クリックされなかった要素 ... 自分より上がクリックされた場合 → 0点 ... 自分より下がクリックされた場合 → (-クリックされた要素までの位置差)
などと定義できそうです。この場合、3がクリックされたとすると、
3 VS 1 # スコア 3 対 -2 3 VS 2 # スコア 2 対 -1 3 VS 4 # スコア 1 対 0 3 VS 5 # スコア 1 対 0
のように「試合」を行い、「得点差」がついたと考えることができます。
もちろん
- インプレッションの数による正規化(数が多いほど影響を受けやすそう）
- 「得点」の定義調整
等の細かな調整が運用にのせるためには必要でしょう。
人工データで実験して結果を載せようと思ったのですが…やはり実データを用いたほうが良さそうなので別途検討することにしました。
レイティングの深みへ
本記事ではごく初歩的な内容を紹介しましたが、紹介した書籍を読み進めると数学的にもお話としてもかなり面白くなってきます。例えば、
- スプレッド(賭け事のオッズ等に関連するレイティング)
- スポーツのレイティング(その他色々なアルゴリズム)
- ユーザの好みのレイティング(レコメンデーションなどに用いる)
- ランキングの集約(複数のランキングの統合方法)
などトピックは尽きません。今後更に調べを進め、色々と実装ができたらブログにしたいと思います!
奥深いジャンルなので、深みを極めればきっとサービス改善にも繋げられるはず!
僕自身詳しい方と勉強会など開いてみたいなと思うジャンルではあるので、勉強会興味あります!という方は
@MasashiSalvadorまでご連絡ください!
スペースに関してはご心配なく弊社オフィスのイベントスペースをお貸し出しします!
https://www.doorkeeper.jp/%E4%BC%9A%E5%A0%B4/eureka
データを見ながらサービスを圧倒的に改善したいエンジニアの方も積極採用しています。
一緒にサービス成長の夢を遂げませんか？ジョイナース！！！
Recommend
これだけは気をつけたい！WordPressプラグインを選定する際の注意点3つ
- 2015.12.04
- Event
- by Shuhei Katori
多言語・マルチデバイス対応のpairsを、チームでデザインするためのデザインデータ管理方法とは？
- 2015.12.06
- Design
- by Takanori Hara