「スキル」を計算するということ

このブログポストは、Jeff Moser氏のComputing Your Skill(2010)を、原著者の許可を得て翻訳・公開したものです。全ての権利は、原著者にあります。

要約: TrueSkillのアルゴリズムをわかりやすく解説しよう。TrueSkillはXBox Liveで、プレイヤーのランキングとマッチングを行うのに使われている。また今日どのように統計的アプローチによる機械学習で実際に応用されているかを理解する、とてもよい題材にもなっている。これまでTrueSkillを実装したオープンソースのプロジェクトを三回行っている。そのたびに、アルゴリズムの複雑さとそれが出来ることを徐々に増やしていった。さらに、このブログポストで注釈をつけている数式について、数学的な詳細についても補遺を作った。興味を持ったセクションから見始めても、つまらなそうなところは飛ばしたりしてもいい。気軽に読んでほしい。このブログポストが少し長いと感じても、__たくさん__図や写真があるから心配しないで。

イントロダクション

最初はとても簡単にできると思った。同僚達のチェスやテーブルサッカーのスキルレベルをトラッキングするデータベースを作りたかった。自分はテーブルサッカーがとても上手いわけではないが、「そこそこ上手」くらいのプレイヤーであれば勝てることもあると知っていた。同じくらいの強さ同士をマッチングさせるアルゴリズムに興味が沸いた。またチェスの腕が上達したらそれを確かめたかった。全員の試合の結果を簡単に集められるようにしないといけないし、より 多く のデータがあればあるほど結果がよくなることも知っていた。そのようなデータ全てを圧縮し、人々がどのようなスキルを持っているかを簡潔にまとめた何らかの情報に落とす方法を探していた。聞いたことのある先行 研究に照らし合わせて、"機械学習“がこの目的にちょうど良いのではないかと思った。

しかし問題がある。

コンピューターサイエンスの中で機械学習は旬な分野ではあるが、一方で恐ろしく感じるものでもある。多くの研究分野がそうであるように、この分野で専門家になるにはたくさん 学ばないといけない。しかし深い部分まで行く必要は無かった。目の前の問題が解けさえすればいいのだ。TrueSkillのアルゴリズムについて記述している論文へのリンクを見つけ、何回か読んでみた。全く理解できなかった。たったの8ページしかなかったが、自分が理解できるレベルを超えていると思えた。自分が愚かな人間であるように感じた。しかしそれでも、根を上げなかった。Jamie Zawinskiは次のように言った。

“知らないというのは愚かということではなくて、単に知らないというだけだ”

つまり問題はこのアルゴリズムそのものが難しいということではなく、学校で 習うような 数学からとても大きな飛躍があるということなのだ。美しい概念が下に眠っているというのに、見かけの上では複雑というのは悲しいことだ。一回理解してしまえば、アルゴリズムそのものは比較的単純だ。しかしその結論に到達するのに私は数ヶ月かかった。私が経験した行き当たりばったりで時間のかかった学習の過程ではなく、近道を教える。TrueSkillアルゴリズムという宝石の中がどうなっているかを理解したときに見ることができる美しい景色まで、あなたを一気に送り届けたいと思う。

スキル ≈ 勝つ確率

スキルというものは計測が難しい。物事を上手になるには、計画的な練習がいるし、ときには少しの運も関係している。一個人でこれを計測するには一体どうしたらいいのだろうか？一人ひとりにどれほど熟達しているかを直接尋ねることもできるが、これでも大雑把な近似しか得られない。なぜなら人間というのは自分の能力に対して自信過剰になる傾向があるからだ。たぶんもっと良い質問は「スキルの単位は何なのか？」だ。100m走のようなものでは、直近数回のタイムを平均すればよい。しかしチェスのような勝敗のみが重要なゲームではこの質問に答えることは難しい。

勝敗をカウントするのが良さそうだが、たくさん勝負をしている人とほとんどしていない人の間で不公平が生じそうだ。勝った試合の割合を記録したほうがましになりそうだが、これでも公平にはならなそうだ。つまりずっと自分より下手なプレイヤーを負かしているプレイヤーと、負けてはいるが多くの物事を学んでいるプレイヤーとの間では公平では無いのだ。大半のゲームの目標は勝つことであるが、勝ちすぎたとしていたら、おそらく挑戦的な試合はしていということになるだろう。理想的には、全てのプレイヤーが半分の試合に勝利していれば、バランスが取れている状態だということができるだろう。このような理想的なシナリオでは、全員が50%の勝率であり、勝率ではスキルの優劣を決めることは不可能になる。

スキルの汎用的な単位を見つけることはとても難しいので、それはあきらめ__どのような__単位も使わないことにする。おおよそ誰が誰よりも上位であり、そしてそれはどの程度差があるのかということにだけに注目する。技能の優劣を表す単位の無いレーティングが一つの方法だろう。プレイヤーが他のプレイヤーよりも高いレーティングであれば、そのプレイヤー同士が勝負した場合、レーティングが高いほうのプレイヤーが勝つことを期待するのだ。

この考え方のキモは「スキルを表す一つの数値」というのは意味がないということだ。重要なことは、どうやって他のプレイヤーと比較をするかということだ。これは重要なので繰り返して書く。他のプレイヤーと比較がなされることで初めてスキルというのは意味をなす。 個人のスキルを比較するのに使える数値が得られるシステムが欲しいのだ。特に、数値的なレーティングに基づいて、勝率(勝ち負け引き分け)を予測することができるスキルを評価するシステムが欲しいのだ。

スキルなるものは計算ができて、更新ができて、それまでの勝敗から今後の勝敗の確率を決められるであろうという仮定に基づいて、そのシステムを見つけることに、この記事の残りの部分を使う。

ところで確率とは厳密には何なのだろうか？

確率を学ぶにはコインを投げればいい…ただしたくさん。何回か投げてみよう。



表、表、裏！

それぞれの試行の結果はランダムであるように見える。しかし"ランダム"というのはパターンが見えてくるまで十分行っていない場合が多い。表が出た回数を投げた回数で割れば、確定したパターンが現れる。

長い時間を経て半々の確率になることはご存知だろう。また「ランダムだ」と言っているとき、その範囲が決まっていることを指す場合もよくある。

弓矢の的の青い目を狙っているときと言った方がいいかもしれない。ほとんどの矢は中心に近いところに刺さる。しかし一方でど真ん中にはなかなか刺さらない。ほとんどの矢はその周りをランダムに散らしたようなように見えるだろう。しかし"ランダム"であったとしても、木々の中に飛んでいくよりも的の近くに刺さることの方が多い(たとえ私がアーチェリーの選手でなかったとしても)。

これは新しいメタファーではない。ギリシャ語のστόχος(stochos)は、目標に向けてセットされた棒を意味する。ここから統計の専門家が統計(stochastic)という言葉を作り出した。面白いが"ランダム"という言葉よりもより現実に即している。刺さった矢の分布は、次の重要なポイントを提示する。

何でも起こりうるが、すべてが起こりやすいわけではない。

「確率」というのは普通の人々の考え方を変えた、数学の歴史上の偉業だ。未来に起こるどんなことでもわかるようになるが、歴史的にも指折りの数学者であるブレーズ・パスカルですら挫折するくらい考え方に大きな飛躍がある。

1654年の夏、パスカルは、また別の才能ある数学者ピエール·ド·フェルマーと"まだ終わっていないゲーム"の考察に関していくつかの手紙を交わしていた。ゲームを終える前にギャンブラーたちが金を分けなかればいけなかったとして、どのようにお金を分けるのが妥当なのかをパスカルは知りたがっていた。ゲームが「もし最後まで行われていた場合の結果の確率」という概念がお金を分けるには必要だ。この問題は確率という分野を生み出し、それは保険、カジノでのゲーム、そして世にも恐ろしいデリバティブのような、たくさんの面白いものの基礎になっている。

しかし確率は単に未来を予測するという以上にもっと一般的な概念だ。あなたが(何かを)どれほど知らないかを測ることができるのだ。ある出来事が未来に起こるか、一ヶ月前に起こるかは問題ではないのだ。どちらの場合も「何か知らないことがある」ということなのだから。何かを知らないからといって、何もできなくなるわけではないが、確率について知るためにもっとコインを投げてみよう。

観測データをまとめる

たくさんの観測結果をまとめると、奇跡が起こる。1000回コインを投げ、表が出る回数を数えたら何が起こるだろうか？いろんな場合があるだろうが、試しにやってみたら505回表が出た。これはおおよそ半数ということで、驚くべき結果ではない。横軸を可能性のある結果全て(表は0から1000までとることができる)に、縦軸に表に特定の回数がなった回数を取るような棒グラフを描いてみる。505回表という結果が1回あったので次のようになる。

あまり面白くもないが、同じ事をもう一回行ったら？今回は518回表が出た。これを図に追加する。

同様の事を8回行ったら、489回、515回、468回、508回、492回、475回、511回となり、最後に505回となった。これで図は次のようになる。

同じことを10億回、つまり1兆回コインを投げたら次のようになる。

表の回数が407回未満になることも、600回を超えることも一度もなかった。この範囲を拡大してみる。

もっと投げれば、ギザギザの部分は滑らかになり、おそらくあなたも見たことがあるであろう”ベルカーブ(鐘形曲線)“として知られているものになる。ドイツ人の数学者カール・ガウスが1809年に天文学に関するデータの誤差について調査していたときに使ったことから、数学をしている人たちはこれを”ガウシアン“曲線と好んで呼ぶ。彼は無限回コインを投げればどうなるかの正確な形を数式思いついたので、無限回コインを投げなくてすんだ。曲線や公式がこれほど有名なので、10マルク紙幣の中央にはガウスの顔が印刷されている。

コインを投げる個々の試行(木)からこのような全体的な結果(森)が得られていることを忘れてはいけない。ありえる結果の密度をこのカーブは図示している。密度とはつまり特定の位置においてのそのカーブがどれほど高いところにあるのかということだ。例えば、1000回投げた後に表の総数を数えたとする。500がもっとも起こりえることを期待するし、実際にそうなる。一億回の試行のうち25,224,637回で表がぴったり500回であった。これは全体の2.52%に相当する。対照的に、450回表が出るところに注目してみれば、たったの168,941回しかでておらず、これは全体のおおよそ0.016%に相当する。これらの事実はこのカーブが曲線であることを裏付ける。つまり、真ん中の500の方が、端の450よりも密度があり、高いということだ。

これは次のキーポイントも裏付ける。__全てのことは起こりうるが、全てが平等に起こるわけではない。__これはロングショットだ。プロのアスリートがパニックを起こしたり窒息したりしたようなものだ。世界で最も強いチェスのプレイヤーでも最悪の日が起こることもある。弱小プレイヤーがにっこりさせてくれるようなこともある。しかし予想だにしないことが起きたとしても、大半のことは予想ができるのだ。

コイン投げだけではない。ベルカーブは、カジノでのゲーム、樹皮の厚さ、人々のIQなど色々なところで出てくる。たくさんの人々が世界でそれを見て、そしてガウスのモデルに気がついたことだろう。世界を一つの大きなベルカーブからなっていると考えることだってできる。

しかし現実世界ではいつもガウシアンとは限らないのだ。歴史にはいつも”ブラックスワン“と呼べる出来事がたくさんあったのだ。株式市場の暴落や、コンピューターの発明などは、ガウシアンのモデルが予測する範囲からは統計的に大幅に外れているが、これらの出来事は世界を揺るがし、そして変えたのだ。この手の現実での出来事はベルカーブでは説明できない。“Black Swan"の著者Nassim Telebはこれを”偉大なる知的詐欺“とまで言っている。これらの出来事は、たしかにだれも現実に起こるとは思わないほどの低い確率だ。Benoît Mandelbrotと彼のフラクタルは、このようなランダムさの中にあるに予想外の出来事に関して、魅力的な全く異なる考え方を示したが、物事を簡略化するためにこれらの考え方を無視する。世界をガウシアンだと考えるのは__常には__正しいとは限らないことは認めるが、ただの世界地図でもまた現実の山岳とは違うのだ。

ガウシアンの考え方は、全てのものは平均値があると仮定している。そしてその平均値からの"誤差”、つまり中央から離れれば離れるほど指数関数的に起きづらくなっていくことも仮定している(結局のところガウスも天文学データの__誤差__を計測するためにそのカーブを使っていた)。しかし「男性と女性の半々からなる"平均的人類"からみたら、人間は"誤差"がある」というのも正しくない。同じような問題は、人間をガウシアン分布のようなスキルを持つ人と扱うときも生じる。言い訳はさておき、George Boxの"すべてのモデルは間違っているが、使うことができるものもある"という考え方に従うことにしよう。

ガウシアンの基礎

正規分布の曲線は次の二つの値によって記述される

  1. 平均値。ギリシャ文字のμとして記述されることが多い
  2. 標準偏差。ギリシャ文字のσ として記述される。この値はどの程度、数値が散らばっているかを表している。

1000回コインを投げたうちのいくつが表になるかをカウントすると、平均は500となり、標準偏差はおおよそ16となる。一般的に標本の68%が標準偏差の±1の範囲に収まり(つまりこの試行では68%の確率で484回から516回が表となる)、99.7%は標準偏差が3の中(452回から548回の間)に収まる。

覚えておくべきことは、ベルカーブは全てのことが起こりえるとしているが、それらの蓋然性は決して同じ程度にはなっていないといことだ。平均値とちらばり具合がどの程度になるべきかということが、ベルカーブから得られる。値が散らばっていなければ平均値から遠く離れた値を得てしまう確率が低くなるということを気に留めておいて欲しい。

ガウシアンカーブを見るときは、平均値から左へ-3σのところをみるのが重要だ。これまでに見てきたように、カーブの面積の大部分はこの点より右に存在する。なぜこのようなことをわざわざ言うかというと、TrueSkillのアルゴリズムがスキルの(とても)保守的な見積もりの基準として-3σを用いるからだ。これ以上に保守的に見積もることも出来るが、-3σを下回ることはまずない。スキルを比較するときに使う値としてはこの値は堅牢だ。そのためリーダーボードのソートのようなところで使えるのだ。

3次元のベルカーブ: 多変量ガウシアン

これまで見てきたような二次元のガウス分布ではなく、それ以上の次元でもガウス分布は発生する。ガウシアンを三次元の山の形のように考えることもできる。次の図がその例だ。

このプロットでは、標高が高い領域が高い確率を表している。見ての通り、全ての事象が同じ確率で起こっているわけではないことがわかるだろう。もっとも起こりやすい事象は平均値で、それは中心にあり、そこから離れると急激に落ち込む。

現実世界での地図では、二次元の等高線図としてよく見るだろう。これはそこに引かれているそれぞれの線が違った標高(例えば100フィート毎)を表している。

線同士が近い場合には、傾斜が急であることになる。同じように3次元のガウシアンを2次元で表せる。教科書では、次のように二次元で表現されたものをよくみるだろう。

これは"等値線図”(isoprobability contour plot)と呼ばれる。「同じ確率で起こることが同じ色になる」と聞くとわかりやすい。注意点として、図は2次元だが、表しているものは3次元だということだ。今回の場合では、3次元目は先に見た表面プロットのような高さではなく色の強さだ。等値線図を「暖かくなってきた」ゲームの宝の地図と考えるのが好きだ(訳注:“Hot or Cold"と呼ばれるゲームのことで、物を隠す側と探す側に分かれ、隠しているものの距離のヒントとして「暖かさ」を教える…らしいです)。この場合では、黒は「寒くなってきた」、赤は「暖かくなってきた」、黄は「火の中にいる！」ということになる。これは確率の高さと一致する。

簡単でしょ？これであなたはガウシアンと”多変量ガウシアン“は言葉の響きほど恐ろしくはないとわかったでしょう。

チェスについて話そう

まだ知るべきことがあるけれども、それについては必要になったときに取り上げることにする。もうすでに何か便利な使い方が出来るツールを手に入れているのだ。肩慣らしとして、チェスについてついて話そう。チェスはレーティングについて厳密に定義されているからだ。

チェスでは、「賢い初心者」がレーティングで1000点付近をとるようにされている。レーティングには単位がないことに気を付けて。これはただの数値で、他のプレイヤーと比較することで初めて意味をなす数値だ。 伝統的に、レーティングに200点の差があれば、レーティングが高い方の勝率が75%になるようになっている。繰り返しになるが、200点という数値そのものには何も特別なものはない。75%の勝率を出すために算出されたもので、プレイヤーの"クラス"を効率的に定義できる。

私が練習を重ね、レーティングが1200あたりになっているとする。このとき、レーティング1000の賢い初心者と勝負したら4ゲーム中3回で勝つことになる。

1000と1200の平均値で、標準偏差が200の二つのベルカーブを使って、私とその賢い初心者の勝負を可視化できる。

上のグラフは、レーティングがどのように表現されるかを示している。 このグラフは勝敗がどのようになるかを__期待されているか__ を示している。 もっともあり得る結果は、レーティングの大小(平均値の大小)と全く同じだ。 あまり自明ではないが、この二つのベルカーブを引き算すると別のベルカーブが出来上がる。新しい中心は元のベルカーブのどちらの平均値とも違い、裾も広がっている。私のスキルのカーブ(赤)と引き算をする初心者のカーブ(青)として、新しいカーブ(紫)が得られる。

1200と1000が中心なので、その差は200だということに注意してほしい。この情報には意味がある。このカーブは、私と初心者とのゲームの結果の蓋然性を表しているのだ。中央の位置が、「私が200点だけ上」であることを意味している。左の端は、「私よりも初心者が700点上」になるわずかな蓋然性を示している。右の端は、「私が1100点上」になるわずかな蓋然性を示している。このカーブは、両端とも無限遠までいくが、そのような可能性はほとんどないので、実際的には0とみなせる。

プレイヤーとしての視点であれば、この中のたった一つの点にとても注目しているはずだ。ゼロだ。私の方が高いレーティングを持っているので、値が正になる結果に興味があるわけだ。この値をとるとき、初心者に勝っているのだから。一方で、初心者は、0よりも左の部分に注目しているはずだ。この値をとるとき、レーティングの差が反転し、彼が勝つことになるのだから。

何個かの数字を計算機に入力することで、レーティングの差が覆る、つまり初心者が勝つという出来事が24%の確率で起こることが分かる。一方76%の確率でレーティングの差そのままの結果になる、つまり私が勝つ。これは大体75%となり、200ポイント差に対して期待していたことと同じになる。

この例は私と初心者という少し具体的過ぎた例だった。一般化して、横軸をレーティングの差、縦軸をそのレーティング差の時の勝率としたカーブを作る。

同じレーティング、つまりレーティングの差が0の場合は、期待通り勝率は50%になる。同様に、-200のところを見れば、先ほど計算したのと同じ24%になっている。また+200であれば76%となる。このグラフは、左の端や右の端がめったに起こらないことも示している。例えば、レーティングがリーダーボードでトップの2813あるMagnus Carlsenに私が勝つ確率は-1613の点の差(1200 - 2813)なので、約10億分の1というになる。あまり気にしてはいないが。(実際には、大半のチェスのグループではもっと違ったカーブを使っている。詳細は数学的な部分の補遺を参照)

これらのカーブは全て「何が起こりうるか」の確率を表している。「何が起こったか」ではない。実際に、私が馬鹿なミスで勝負に負けたとしよう。初心者が知りたがっていることは、どのくらいレーティングを上げることができるかだ。私のレーティングが勝負に負けることによってどれほど落ちるのかについても同様だ。この「どれほどレーティングを変更するべきなのか」というのは難問だ。

勝利したことで、初心者が実際の勝率は25%よりも高い可能性があることを示している。レーティングの更新の一つの方法に、各プレイヤーがゲーム毎に自分たちのレーティングの一部を賭けるようなイメージで行う方法があるだろう。どの程度ベットするかは、推定される勝率から決定する。加えて、ゲーム毎にどれほど劇的にレーティングを変化させるかは、決めておかないといけない。その係数を100%だとするなら、私のレーティングは凄く下がるし、彼のレーティングは凄く上がってしまう。チェスをやっている人たちはその係数を、“K値"と呼んでいる。

K値は勝敗の確率に乗算され、交換されるレーティングが計算される。これは最大でどれほどレーティングが変化するかも表している。このウェイトの妥当な値は、「前回の勝負が7%のことを説明する」というもので、これはK値では24となる。長年プレイしているプレイヤーよりも、最近始めたプレイヤーの方がよりレーティングが変動しやすい傾向があるので、そのようなプレイヤーはK値は32だし、グランドマスターのK値は10あたりになっている。下のグラフが、前回のゲームがどれだけのことを説明するかと、K値の変化量の関係を示している。

K値が24であったなら、私のレーティングは1182になり、初心者のレーティングは1018に上がることになる。二つのカーブの距離はゲームの前よりも近くなった。

私と初心者、両方のカーブの標準偏差は決して変わらないことに注意してほしい。 もしここで再度ゲームをした場合の勝率のグラフは下のグラフのようになる。

ここで紹介した方法は、この方法を発明し自身もチェスの熱狂的なファンであるArpad Eloにちなんでイロレーティングと呼ばれている。

TrueSkillについて話すと言っていなかった？

これからのメインイベントを理解するのに必要なことをこれまでやってきた。TrueSkillの論文はこれらのことを当然理解しているものとしていたが、私にとっては全てが初めて聞いたことであったし、イロレーティングの考え方に納得がいるまでに時間がかかった。イロのモデルを理解するのに飛躍があったが、これでもなおちゃんと扱えていいないことを記しておく。

  1. 新参者(Newbies) - イロシステムでは、最初の20ゲームは、“暫定的"なレーティングを設定される。その間は、高いK値が設定され、素早くスキルを変動させる。新参者でなくなったら、暫定的ではない小さなK値が設定される。プレイヤーの真のスキル(True Skill)に収束させるアルゴリズムが欲しいので、力量がアンバランスな対戦を設定して時間を無駄にしたくはないのだ。つまり、妥当な近似を最初の5から10ゲームの間に算出できないといけない。

  2. チーム(Teams) - イロは二人で対戦するゲームに対してデザインされている。これを複数人で構成されたチームが複数あるようなものに適用させようとするのはあまり洗練された方法ではない。このようなアプローチをする方法として、一つのチームを一つのプレイヤーに見立てるというのがある。チーム内のプレイヤーの平均値をチームの値として用いるのだ。これをTrueSkillの論文では"duelling heuristic"の方法と呼んでいる。これを私はこのプロジェクトで実装している。これでもよいのだが、ハックであることは否めないし、収束が遅い。

  3. 引き分け(Draws) - イロは引き分けを「半分勝ちで半分負け」として扱っている。引き分けにはもっと情報が含まれているのだから、このように扱うのはあまり適切ではないように思われる。 引き分けであるということは、公平にマッチングされたということなのに、あなたは勝ったということになる。どれほど勝っているのかということがわからないのに。同様に負けたということになるが、どれほど負けていたということも知りようがない。引き分けというのは明示的に扱ったほうがいいように思われる。

イロを一般化したTrueSkillアルゴリズムは二つの変数をトラッキングする。スキルの平均値と、システムの推定値に対する不確かさ(標準偏差)だ。これをK値のような定数に依存することなく行う。本質的には、動的なK値を得ることになる。 これにより、新参者に関する問題を"暫定的な"ゲームをさせることなく処理できるし、他の問題も統計的な方法で対処できるようになる。この二つの値をトラッキングすることは、このアルゴリズムの基礎的な部分なので、マーケティングの人たちがTrueSkillと名付ける前に、Microsoftのリサーチャーはこれをμσ システムと呼んでいた。

まもなくこのアルゴリズムの詳細に入るが、その前にTrueSkillを図解で外観を軽くつかむのも意味がある。経験豊富で、レーティングが固まっているプレイヤーとしてエリックを、初心者としてナターリアを使って解説してみよう。

ゲームをする前のスキルのカーブは次のようになる。

ナターリアが勝った後は次のようになる。

ナターリアのスキルカーブがより狭くより高くなったことがわかるだろう(つまり大きな更新があったのだ)。一方で、エリックのカーブはわずかに動いただけだ。TrueSkillのアルゴリズムが「エリックよりもナターシャの方が優れているかもしれないが、どれほど優れているかわからない」ということを考えていることを示している。またTrueSkillはナターリアのスキルに関して、ゲームの後に少しだけ確信を強めていることもわかる(つまりカーブの中央がゲーム前よりも少し高くなっているのだ)が、依然としてまだ不確かなままだ。この更新によって、ナターリアのスキルが15から50の間にあるであろうことがわかる。

このブログポストの残りは、これをどのようにして計算したかと、起こりうるもっと複雑なシナリオについての解説になる。実装ができるようになる位まで理解するにはまだ知らないといけないことがたくさんあるのだ。

ベイズ確率

最も基礎的な統計の授業では、出来事の頻度について学ぶだろう。 例えば、赤のビー玉が3つ、青のビー玉が7つ入っている壺からランダムに一つのビー玉を引いたときに、赤のビー玉を引く確率は30%だとか。 他の例では、二つのサイコロを振ったとに、その合計値が7になる確率が17%になるだとか。このどちらの例も重要なことは、すべての起こる出来事を数え上げることができ、頻度を直接計算できてしまうということだ。カジノでオッズを計算するのにも役に立つが、これらの頻度主義の考え方は現実の適用例、例えば「チーム内のスキルを計算する」といったようなことには役に立たないのだ。

これと異なる考え方のアプローチとして、確率を何らかの確度だととらえることだ。基本的な考え方は、__事前信念(prior belief)__とこの確信の度合いを、観測された__証拠(evidence)__で更新し、__事後信念(posterior belief)__を得るということだ。ご想像の通り、新しい証拠を得ればより確信の度合いは高まる。

地図の中から宝物を見つけることを想像してみよう。宝物は地図の上のどこにでもあり得る。ここで勘が働いて、地図の中心にあるような気がしてきて、端にいけばいくほど無さそうな気がしてきたとする。前にみた3Dの多変量ガウシアンを使うことで、確率を得ることができる。

宝物に関する書物を読んだことで、宝物は対角線の上にありやすいということを学んだ。 これは秘密の手掛かりによるものかもしれない。 この手掛かりの情報は、宝物が__実際に__その線の上にある必要はないが、その近くにあるのが尤もらしいということになる。 この__尤度関数(likelihood function)__は3Dでは次のようになる。

事前情報と新しい尤度情報を使って宝物の位置の事後推定を得たい。この二つを単に乗算することで、事後分布を得ることができ、次のようになる。

これにより、探す場所の範囲がより小さく、より集中した範囲になった。

この分野の教科書を読んでいるなら、先に書いた二次元の等値線図(isoprobability contour plot)を見たかもしれない。次の図が同じ情報を二次元にしたものだ。

事前分布

尤度

事後分布

面白くするために、さらに追加で宝物はもう一方の対角線の上にもありそうだということがわかったとする。

前回の事後分布を次の事前分布とし、この情報と合わせることで、更新された事後分布が得られる。

確信度合いが、当初の比べてもっと集中した範囲に狭まった！これまでの処理を繰り返すことで、より狭い範囲にできる可能性がある。

そしてこれがやりたいことなのだ。TrueSkillでは、埋蔵された宝物はある人のスキルだ。 確率に対するこのようなアプローチを__ベイジアン__と呼ぶ。1700年代の長老教会の牧師で数学の愛好家であったThomas Bayesによって発見されたからだ。

ベイズ統計のアイデアの核は、「事前分布」、「尤度」、「事後分布」だ。数学的な詳細はこれからの解説と補遺にあるが、アイデアそのものを理解する方がもっと大切だ。

何かを理解したときに、初めて数学的に説明ができるようになる。数学的な説明が理解をさせてくれるわけではない。 - Lamport

ベイズ法は、コンピューターが発展した近年になって注目されるようになった。コンピューターが大量の事前分布と事後分布の更新を行えるからだ。ベイズ法は、Microsoft Reserach(True Skillはここで開発された)内で歴史的に有名になった。1996年を振り返ると、Bill Gatesはベイズ統計がMicrosoft Reserachの秘伝のものだと考えていた。

後にみるように、ベイズのアプローチをスキルの計算に使うことができる。それまでの証拠(例えば前回のゲームでの強さのように)を元に確信の度合いを更新するという考え方は一般的にも役に立つ考え方だ。これは大抵の場合うまくいくが、時々”ブラックスワン“が現れる。 例えば、ベイズ推論を七面鳥に対して使ってみる。サンクスギビングの日でしか七面鳥を食べない人が、1000日毎日七面鳥を育てている農家の人の厚意で七面鳥をもらったとしたら、七面鳥を食べる分布の平均値から、何標準偏差も離れたところのイベントということになるので、その事後分布はかなり特殊なものになる。スキルというのはこのサンクスギビングのイベントのように潜在的になりうる。例えば、平均的なプレイヤーが、世界一のプレイヤーを打ち負かした場合のように。それはとても小さい確率で起こることはわかっているが、簡単のため無視する(そしてたまたま勝ってしまった勝者はその後の人生での語り草を得ることになる)

True Skillが、「ベイジアンだ！」と言っているのだから、そういうことにして、事前分布と尤度の解説に行こう。だいぶ近づいてきたが、もう少し詳細を知らないといけないことがある。

重要視はしない(Marginalized)が、完全に忘れはしない分布

次は、周辺分布(Marginal distribution)について学ばなくてはならない。これはよくマージナル(marginals)と呼ばれる。周辺分布は何に注目しているかにフォーカスしている分布の情報だ。昨年の毎月の売り上げの表を想像してほしい。電卓を取り出して、すべてを足し合わせれば、その年の総売り上げを計算できる。この新しい数値は、元のレポートにはないので表の余白(margin)に書き込める。これが"margin-al"の由来だ。

このトピックに関して、Wikipediaでは素晴らしい例を上げている。 ある男がいる。その男は母親のアドバイスを聞かずに、クルマの往来を確認せずに道を横断しようとしている。 さらに悪いことに、iPodから流れる音楽に夢中になっているので、どこも見ていない。単に横断する。

交差点で彼がクルマに当たってしまう確率はどのくらいになるだろうか？簡単のため、信号の色のみに依存する話だとする。

信号の状態 赤 黄色 緑
事故が起きる確率 1% 9% 90%

これはこれでありがたいが、これだけでは知りたいことを知ることはできない。

信号の色 赤 黄色 緑
その色になっている時間の割合 60% 10% 30%

たくさんの確率データを得られたが、少し情報が多い。確率をつなげたら、同時分布(joint distribution)がえられるが、 これは大きくて複雑なシステムで、情報を伝えすぎてしまう。

この情報を各々の信号の状態の時の確率に落とすことができる。

赤 黄色 緑 事故にあう確率
1% * 60% = 0.6% 9% * 10% = 0.9% 90% * 30% = 27% 28.5%

このテーブルの右の余白が、この男にとって本当に重要な値となる。クルマの往来をみることなく、横断することで事故にあう周辺確率は28.5%となる。各々の因子を"足し合わせて"この値を得た。つまり、部分ではなく全体に注目したことで変数を減らし、変数を減らすことで問題を簡単にしたのだ。

周辺化(Marginalization)の概念はとても一般的だ。このブログポストの疑問の中心は、“スキルを計算すること"だ。しかしスキルというのは複雑だ。ベイズ統計を使うとき、何かを直接観測することはできないことがあるので、確率分布を示す必要がありこれはもっと複雑だ。先の無謀な男の例のように、“足し上げる"ようなことをしてスキルを周辺化する必要がある。

それを行う前に、計算を簡単にするテクニックについて知らないといけない。

因子グラフと、なぜそれを気にしないといけないのか

代数学の授業で次のような式を扱っていたことを思い出して。

教師がwで因数分解(factor-ing)ことで次のように出来ると教えてくれただろう。

このようにすることで、理解しやすく計算もしやくなる。これらの変数をw=4,x=1,y=2,z=3と数値に置き換えてみよう。

数は円で、演算は四角で表し、式木のように計算を表現すると次のようになる。

11のボタンを押さないといけない計算は退屈でしょう。これを因数分解すると次のようになる。

因数分解によって、ボタンは7つになり、4つのボタンが省略できた。たいしたことじゃないように見えるかもしれないが、これは素晴らしいアイデアなのだ。

複雑な確率分布を単純にするときに、因数分解のときと同じような問題に直面する。スキルというのが、同時分布の中でいかにいくつかの"因子(factor)“から構成されているかということを見ていく。それらの因子が変数にどれほど関連づけらているかに基づき、計算を簡略化できる。同時分布を、それらのたくさんの因子からなるグラフに分割していく。この因子と変数からなるグラフを"因子グラフ(factor graph)“と呼ぶ

因子グラフの核になるアイデアは、周辺条件付き確率を変数とし、主な関数の変数を"因子"とすることだ。グラフの因数分解をどのようにするかを利用する。それぞれの因子をネットワーク中のノードとみなす。このネットワークは効率化のために最適化される。効率化のためのトリックは、因子のノードは他のノードに"メッセージ"を送るということだ。このメッセージにより、周辺化の計算をより簡略化させることができる。“メッセージパッシング"はとても重要で、この後に出てくるグラフでは矢印になっている。灰色の矢印は、メッセージがグラフ中をを"降下"しているのを表し、黒色の矢印はグラフ中を"上昇"しているメッセージを表している。

付録のコードと、補遺はここで何をやっているかの詳細を記している。しかしまずは先に本質的な部分を理解することが大事なので、勝敗から個人のスキルを更新する尤度関数を生成するための全ての因子を見ていこう。これらの情報を因子グラフで表現することで、どのようにこれらの因子が関連付けられているかがわかりやすくなる。

メインイベントの準備に必要な基礎的なコンセプトがすべてそろった。メインイベントとはTrue Skillの因子グラフだ！

チェスはもういいので、もっと難しいものをランキングしよう！

TrueSkillのアルゴリズムは尤度(Likelihood)によって乗算された事前分布(Prior)からなるのでベイジアンにのっとっていると言える。TrueSkillの論文中のサンプルの因子グラフの図から、この二つの因子を強調してみた。私はこの図を最初に観たとき、とてもおどろおどろしく感じたものだ。

この因子グラフは、3チームがお互いに総当たり戦をした結果を表している。最初のチーム(左)は一人しかプレイヤーがいないが、残りのチームを負かしている。二つ目のチーム(中央)は二人のプレイヤーがいて、一人しかない三つ目のチーム(右)を打ち負かしている。

TrueSkillでは、プレイヤーの周辺化されたスキルにのみ注目している。しかしベイジアンモデルにはよくあることだが、注目している変数に影響を与える他の因子については明確にモデル化しないといけない。それらの因子は概要をつかむにとどめる(より詳しい説明はコードと補遺を参照)。

因子1： すでにわかっているスキルはどれだけか

最初の因子は、全体の処理のスタート地点だ。前回までのスキルレベルをどこからか取得する(例えばプレイヤーのデータベースなど)。この時点で、スキルに標準偏差として不確かさを追加する。この不確かさは、ゲームのダイナミックスを面白くするためだったり、標準偏差が0になることでこの後のアルゴリズムの処理が縮退させられることを回避するために、導入される(処理全体では、スキルがどのくらいで、その確かさを高める計算なのではあるが)。

因子と値は各々のプレイヤーに与えられている。それぞれの因子は、前回までのプレイヤーのスキルを記憶するための関数だ。それぞれの値のノードは現在のプレイヤーのスキルの値を保持している。“現在の"と言ったのは、これから述べる全ての処理が終わった時に得たい値だからだ。因子の上にあるメッセージの矢印は一方通行であることに注意してほしい。決して、前の因子には戻らず、ただ進むだけだ。しかしそれでも変数に戻ってくる。ちょっとこれは先走りした内容だけれど。

因子2: 各個人はどれだけパフォーマンスを上げるか

次に、ベータ(β)に入る。ベータは、80%の勝率を保証するスキルポイントと考えればいい。TrueSkillの発案者は、ベータを"スキルの鎖"の長さと言及している。

スキルの鎖では、最も下手なプレイヤーが一番左に、最も上手なプレイヤーが一番右につながれている。この間にいるプレイヤー間で、強い方のプレイヤーが弱いの方のプレイヤーに80％の勝率となるように"ベータ"が設定される。つまりこのベータが小さい値であれば、勝敗が80%対20%になる差が小さいということになり、高度な技術が必要なゲームということになる(例えば碁)。同様に、運への依存が大きく技術はあまり必要ではないゲーム(例えばウノ)は、ベータが大きくなり、スキルの鎖は小さくなる。

因子3: チームはどれだけパフォーマンスをあげるか

さて、ここでTrueSkillでよく論争を引き起こすところまできた。チームのパフォーマンスをチームとして計算する部分だ。TrueSkillでは、チームのパフォーマンスはチームのメンバーのパフォーマンスの合計値だと仮定している。なぜこれを"議論を引き起こす"と言ったかというと、メンバーの一部が他のメンバーよりもずっと忙しく働く可能性があるからだ。加えて、時と場合によっては、単なるメンバーのスキルの足し上げよりも高いパフォーマンスをチーム全体として発揮することもあるだろう。しかしこの物事を複雑にしてしまう衝動と戦い、Makridakisの助言を心に留めよう。

統計学的に洗練されていたり複雑な方法というのが簡潔な方法よりも正確な予測をするとは限らない

この因子が素晴らしいのは、各プレイヤーのプレイ時間によってチーム内のそのプレイヤーの重みを設定することができるということだ。例えば、二人からなるチームの各プレイヤーが全体の時間の半分しかプレイしなかった(例えばタッグを組んだ場合)と、二人のチームが全ての時間を通してプレイした場合と、別の扱いをすることができるのだ。これは公式的には"部分的なプレイ(artial play)“と呼ばれている。XBoxのゲームであれば、各プレイヤーがゲーム中でどのくらいの割合でプレイしていたかをX_PROPERTY_PLAYER_PARTIAL_PLAY_PERCENTAGEプロパティで取得できる(デフォルトで100%)。この情報はTrueSkillの更新をより妥当にする。私はこの機能を付録のコードで実装した。

因子4: どのようにしてチームを比較するのか

次に、チームのパフォーマンスをペアで比較する。これは比較する対象のチームとチームのパフォーマンスを減算すればいい。

このブログポストの最初の方で、イロレーティングでやったことに似ており、カーブからカーブを引いて新しいカーブを得ているのだ。

因子5: チーム間の差をどのように解釈する？

因子グラフの一番下では、チーム間のパフォーマンス差に対する比較の因子がある。

パフォーマンスの差が"勝利"か"引き分け"かどちらと解釈できるかによってこの比較因子の動作は変わってくる。ゲームのルールに依存するのは明白だ。TrueSkillがこの"勝利"か"引き分け"かの二つしか扱わない点は重要だ。TrueSkillは、圧勝したか僅差で勝ったかではなく、勝ったか引き分けだったかのみに注目する。さらに、TrueSkillでは、“引き分けマージン"と呼ばれる、パフォーマンスが等しいとみなすためのバッファーが存在する。例えば、オリンピックの水泳では、二人の水泳選手が"引き分ける"ことがあり得る。0.01秒単位までで等しければ、1000分の一秒の違いがあっても等しいとみなされるのだ。このような場合、“引き分けマージンは比較的小さな0.005秒となる。グランドマスターレベルのチェスでは引き分けはとてもよくあることで、引き分けマージンはこれよりもずっと大きくなる。

比較因子の出力は、スキルの平均と標準偏差の変更と直接関係している

これに関する正確な数学はとても複雑なのだが、核になるアイデアは単純だ。

「勝負の結果が期待通りであれば、アルゴリズムはすでにかなりよい近似を得られているので、スキルの更新は小さくなる。予想外の結果(番狂わせ)であれば大幅なスキルの更新を行い、将来の予測精度を高める」

補遺では詳細を記しているが、本質的にはパフォーマンスの差を、次の図の下の数字(x軸)だと思えばいい。これは、期待される勝者と期待される敗者の間の差を表している。大きな負の値は大番狂わせ(つまり格下が勝つ)を表し、大きな正の値は期待された通り方が勝つことを表す。スキルの平均値の正確な更新は、引き分けの確率に依存する。だいたいどういうことかはグラフを見てつかんでほしい。

同じように、スキルの標準偏差(不確かさ)の更新は、勝敗がどうなるかがどれほど期待されていたかに依存する。期待された通りの結果であれば、不確かさは減少し、小さな値になる(つまり過去にあったことはこれからも起こりやすい)。同じように、予期されていないような結果であれば、それは今までにない新しい情報なので、標準偏差はさきほどよりもさらに小さくさせる。

この比較因子に関する問題はいくつかの面白い数学を使って近似をする(いい近似ではあるが、近似でしかない)。この近似を次のステップで洗練させる。

内部的なスケジュール: 反復、反復、反復！

チーム間の差の因子の近似はその因子の後に続くループでメッセージを渡しまわることで、もっといい精度にできる。

何回かこのループを反復させると、更新される差が劇的に少なくなっていき、それぞれの周辺確率の値が安定してくる。

もうたくさんだ！新しいレーティングをくれ！

内部的なスケジュールが因子グラフの一番下にある値を安定化させたら、それぞれの因子の方向を逆方向にし、グラフをさかのぼる形で伝播させる。この逆方向に伝播しているメッセージは因子グラフ中の黒い矢印で表されている。それぞれのプレイヤーの新しいスキルのレーティングは因子グラフの一番上に到達した値で、それはプレイヤーのスキルを周辺化した値だ。

通常、全プレイヤーに対してこのスキルを更新する処理を行う。 しかしゲームタイトルによっては、プレイ環境が不適切だった場合に勝敗を考慮にいれたくないこともありえる(ネットワークのラグがあるときなど)。このようなときに、“部分的な"更新を行える。これは全更新の一部を行うようなものだ。XBoxではX_PROPERTY_PLAYER_SKILL_UPDATE_WEIGHTING_FACTOR変数によってこれを設定することができる。この機能を実装し、補遺に詳細を記載した。

結果

まだ書いていない詳細な部分が残っているが、ここまでにする。補遺とコードがその残っている部分の穴埋めになるだろう。TrueSkillの詳細を学習する最もよい方法は実装することだ。遠慮なくこのプロジェクトをポートを好きな言語で作って、世界にシェアしよう。自分で実装を書けば、ここで書かれたコンセプトの理解が深まるはずだ。

TrueSkillアルゴリズムを実装する中で、最も価値があるのは実践投入されたそれを見ることだ。“気味が悪いほどに"ほぼ正確に全員の相対的なスキルを計算していたと、同僚がコメントしていた。何カ月かテーブルサッカーをプレイしたら、リーダーボードのトップ(TrueSkillが出したμ-3σによってよってソートされている)はとても安定した。最近始めた上手いプレイヤーが、今では2位のプレイヤーになっている。次の図は、テーブルサッカーの最近40ゲームのトップ5のプレイヤーのTrueSkillのグラフだ。

(注意: 二番手のプレイヤーがどれだけ優れたプレイヤーであるかを検出したのがどれだけ早いか見てほしい。彼の勝率は50%でしかない。)

TrueSkillを実装することの面白い他の側面としては、プレイヤー自身が自分がどれほどの腕前なのかを自覚できるということだ。互いに一緒にプレイしたことのないプレイヤー同士が同じ程度のレーティングであると知り、よいマッチングに繋がるということがある。TrueSkillの一つの利点として少し上手い程度のプレイヤーに敗れたとしても一大事にはならないという点がある。そのため多少バランスが悪いマッチングを行っても問題がないのだ。加えて、レーティングがあることで、テーブルサッカーで新しいショットの仕方を覚えたり、チェスの新しい理論を習ったことでどれほど能力が向上したかを判定することができるのだ。

次の方向性

次の方向性として明らかなものは、システムにもっと多くのゲームを追加して、TrueSkillが同じようにそれらを扱えるかを見ていくことだ。 TrueSkillがXbox liveのデフォルトのランキングシステムであるので、たぶんどのようなゲームであってもうまく動くのだろう。他の方向性としては、チーム内の役割、ポジションによってTrueSkillが大きく変わるのかということだ(テーブルサッカーでいえば、ミッドフィールドなのかキーパーなのか)。TrueSkillが統計に基づきおおよそのランキングやマッチングを与えてくれたら、いくつかのオプションからどれを使っても成功を得られるかもしれない。その日の気まぐれでポジションやマッチングを決められるかもしれない。何はともあれ、次に行く行楽地や子供の名前を選ぶ面白い方法にはなるだろう。

視野を広げると、ここまで学んだことを色々なものに当てはめられる。MicrosoftのAdPredictor(Bingに表示される妥当な広告を見つける)は、TrueSkillのチームによって開発され、同じような数学を使っている。しかしアプローチが違う。

さて、面白い旅であった。このブログポストを読んだことでアルゴリズムを理解できたならうれしい。特に私のコードを更新してくれたり、他の言語にフォークしてくれたら感謝する。

リンク

  • The Math Behind TrueSkill
    　数学に関する論文で、このブログポストで記されなかった詳細が書かれている。
  • Moserware.Skills
    　GithubにあるプロジェクトEloとTrueSkillの完全な実装がC#で書かれている。
    　遠慮なく他の言語にフォークしてくれ。
  • Microsoft’s online TrueSkill Calculators
    　何かをダウンロードしなくてもこのアルゴリズムを試すことができる。
    　私の実装はこの結果と同じ出力をする。

この魅力的なアルゴリズムに対して、たくさんの子細な質問に答えてくれたことに、Microsoft Research CambridgeのTrueSkillチームのRalf Herbrich、Tom Minka、Thore Graepelに謝辞を送る。