機械学習、たまにゲーム

情報科学に関する記事や経験談等を不定期に投稿します．

機械学習とデータサイエンスに興味がある大学院生が今年前半に勉強したこと

1月から7月までに勉強したことと，これから勉強したいことを書いていきます．

目次と概要

はじめに

最初に，簡単な自己紹介です．

  • 学年：修士1年
  • 専攻：東工大 情報理工学院(学部，修士とも)．機械学習を扱う研究室に所属しています．
  • 就職：データサイエンティストや機械学習エンジニアに興味があります．機械学習を使ってデータ分析をするようなお仕事をしたいと思っています．

タイトルの通り，私はデータサイエンスに関心があります．ただ，今のところは，「データサイエンティストになりたいから～をやる」みたいなモチベーションで何かに取り組むというよりも，面白そうだと思ったことや，勉強したいと思ったことに手を付けています．

1月から7月までやったこと

1月～春休み前 研究の日々

研究で忙しかったので，それ以外のことはやっていません．

春休み 確率論と応用情報技術者試験

確率論

はじめての確率論測度から確率へ / 佐藤 坦 著 | 共立出版を読んで勉強しました． www.kyoritsu-pub.co.jp この本は確率論の入門書で，全3章から成っています．1章を読み終えたところで新学期が始まったのでそこで止まってしまっています．1章の内容は測度論の基礎事項と期待値の定義，確率変数列の収束，直積確率空間とフビニの定理，ラドンニコディムの定理などです(盛りだくさん！)．時間をかけて行間を埋めることを意識していて，1日中読んでいても1ページも読み進められない日もありました．夏休みに入ったら1章の復習をしつつ先に進めたいです．

応用情報技術者試験

大学に入学してから資格を1つも取得したことがなくて，応用情報技術者試験の勉強をきっかけに情報分野の色々な知識を吸収しつつ資格も取れたらいいなと思い，2カ月ほど勉強しました．自分は一応情報系の人間ですが，正直勉強したことのない分野の方が全然多かったです．残念ながら4月の応用情報は新型コロナ流行のために中止となり，春に受験をすることができませんでしたが，それでも今まで知らなかった分野に多少なりとも手を出せたので良かったです．

4月~6月：第1Q 講義，Discord Bot作り

講義

大学の講義が始まりました．3つの専門科目と1つのキャリア科目(修了のために必要な科目)を履修しました．*1専門科目の概要は以下のとおりです．

  • 応用関数解析：偏微分方程式への応用を目標とした関数解析の講義です．前半は超関数やフーリエ変換，ソボレフ空間や弱微分などの関数解析の基礎事項を学び，それらを使って様々な偏微分方程式(熱，波動，楕円型，非線形，...)の解の性質や滑らかさを解析するという内容でした．終盤の講義ではバーガース方程式やナビエストークス方程式などの非線形方程式を扱ったりして，関数解析を応用すると色んなことがわかるんだな～と思いました．多分今までに受けた大学の専門科目の中で一番面白かったです．

  • 微分方程式：常微分方程式，特に自励系(力学系)と呼ばれるタイプの微分方程式について扱いました．微分方程式に興味があってこの講義を履修しましたが，前半の講義で(リプシッツ条件等を仮定したときの)常微分方程式の解の一意存在性の証明をしたところらへんで満足してしまった感があります() 後半の講義は解の安定性や中心多様体定理や分岐の基礎について勉強しました．

  • 数理統計学：前半はカーネル法や再生核ヒルベルト空間の数理，後半は統計的学習理論を勉強しました．ここでいう統計的学習理論というのは，汎化誤差を最小にする関数と，モデルがデータから学習することにより得た関数の距離をRademacher Complexity等の確率変数や確率の各種集中不等式(一様大数の法則，...)を用いて解析するというようなものです．

どれも内容が濃くて，復習に多大な時間が掛かりましたし，理解不足な箇所もあってレポートで苦戦したことも少なくありませんでしたが，受けていて楽しかったです．*2

Discord Bot作り

Pythonとdiscord.pyを利用してDiscordのBotを作りました． Discord Developer PortalでBotのアカウントを作成して，PythonでBotのコーディングして，ローカルPC上でプログラムを動かして遊びました．

一番最初に作成したBotは，Discordのチャット欄で/tenkiと入力すると「わからん」と返すやる気ゼロ天気Botで，Twitterでたくさん反応を頂きました．

それから，天気Botを改善して天気APIを叩いて明日の東京都の天気を取得するものにしたり， 大人気ゲームSplatoon2の現在のルールやステージを返すものや，現在から24時間後までのガチマッチやリーグマッチのルールやステージを返すBotも作成しました． discord.pyを活用すれば比較的簡単にBotを作ることができて，一時期没頭していました．勉強というよりかは趣味の一環という意識でやっていたのでこの記事に載せるべきかは怪しいですが，結果的にPythonによるBot作成技術を知ることができたり，今までしたことがなかったことができて楽しかったので書きました．この記事とは別にBot制作に関する記事を書ければいいなと思っています．

7月 第2Q 線形代数, SQL, Julia

7月から第2Qに入りました．第2Qは授業を1つも履修していないので，第1Qよりも自分の時間を多く確保できています．

線形代数

なんとなく線形代数の勉強をちゃんと勉強し直そうと思い，数研講座シリーズ 大学教養 線形代数｜チャート式の数研出版 を購入して読み進めました． www.chart.co.jp この本の定義や定理を追って，練習問題や章末問題も解きながら1ページずつ読み進めました．いまは9章あるうちの5章目(ベクトル空間)を勉強している最中です．線形代数を一通りおさらいしたいと思っていた自分にぴったりの本でした，1冊通して読むつもりです．

SQL

SQLZOOというサイトでSQLの演習をしながらSQLの基礎知識を身に着けようとしています． sqlzoo.net こちらはブラウザ上でSQLを実行できるサイトで，練習問題を解きながら文法を理解できるようなつくりになっています．このサイトには解答は載っていないので，分からない箇所はググって文法を確認したりして，少し時間が掛かることもありますが調べることによって色々分かることもあっていい感じです．難しそうな問題は飛ばし飛ばしやっています．今月中に一通り問題を解き終えられそう．

Julia

つい数日前にJuliaをインストールしました．Jupyter notebookにJuliaを追加してHello Worldを出力した程度のことしかまだやれていないので，何をやったかと聞かれるとほとんどやれていません．文法を調べながら他人が書いたコードを解読しようとしています．今までプログラミング言語はPythonを主に用いていましたが，Juliaの方が断然速いという噂を耳にしてインストールしました．Juliaがどんな言語なのか，なぜPythonに比べて計算速度が速いと言われているのかは何1つとして理解できていませんが，とりあえずPythonで書いているコードをJuliaで表現してみて，計算速度にどれほどの差があるのかを確かめてみようと思っています．

その他今年勉強した書籍等

上で述べるほど時間をかけて勉強していませんが，この本をちょっと読みましたよっていうのを書いていきます．

これから勉強したいこと

何をしたいかと聞かれるとあれもこれもやりたいとなってしまうので，後述したものの中からどれか選んで今年の後半に取り組めればいいなと思っています．

おわりに

以上が今回の記事の内容になります．同じ大学院や研究室の方や，Twitterでつながっている方々には自分よりも遥かに優秀な方ばかりでとても刺激を受けていますが，勉強や研究は自分のペースでやっていけたらと思っています．

また，私と同じように機械学習やデータ分析，統計学などに関心のある大学生や大学院生の方や，実際にそれらを用いた業務をされている方は大勢いらっしゃることと思いますが，そのような方々が，どんなことを勉強・研究・お仕事をされているのかとても気になっています．また，今は興味のあるものを中心に勉強していますが，データサイエンティストや機械学習エンジニアになるためにはどんな技術を習得していると良いかも知りたいです．もしそれらに関して話してくださる方がいらっしゃれば，この記事にコメントをしていただくか，Twitter(https://twitter.com/Mina10Y)宛てにDMしていただけると嬉しいです．どんなことでもお話しましょう！

記事を読んで下さり，ありがとうございました．

謝辞

色んな本を読んでいて，分からない内容を同じ大学出身の同期やTwitterのFF内の方に何度もリプライで教えて頂きました．特に数学を勉強しているときは，勉強不足ゆえ1人で長い時間かけても分からないことも多く，いつも助けられています．また，FF内の方からAtCoderのお話をしていただいたり，データサイエンス系の就職のお話を聞いたり，自然言語処理に関するとても面白いお話をして下さったりと，大変貴重なお話をお聞きしております．お名前を出していいのか分からないのでこちらにはお出ししませんが，関わってくださった皆さまに感謝しております...！いつか自分も誰かに有益なことを伝えられるような人になれるように成長していきたいです．

f:id:optzard:20200726124343j:plain

*1:講義はZoomを用いてオンラインで行われました．オンライン講義は賛否両論あるみたいですが，私は講義のオンライン化による不便さをほとんど感じず，むしろ通学時間がなくなったことで自分の時間も増えてとても嬉しいです．個人的には，新型コロナが終息しても，オンラインで講義を受講できるようなシステムがあると嬉しいなあと思います．

*2:同じ授業を受けている友達とZoomでオンライン勉強会を開いて，講義内容やレポート問題に関する議論をたびたびしていました．講義を受けるにあたって，教え合ったりしてくれる友達や，講義内容や成績について教えて下さる先輩に恵まれていたことが非常に大きかったです．今の大学1年生や他大学院に入学した方は知り合いをつくることに中々苦労されている方が少なくないようで，復習やレポート作成も本当に大変だと思います．新型コロナが流行しているこの状況下で友達をつくったり，オンラインで円滑に勉強会をしたりするにはどうしたらいいのでしょうか．

レーティングについてと，グリコ2レーティング(Glicko-2 System)におけるレーティング算出方法

概要

オンラインゲームやチェスなどのボードゲームで使われているレーティングに関する記事です．

レーティングの算出方法は何種類かありますが，その中でSplatoon2やシャドウバースなど，様々な対戦ゲームで使われているグリコ2レーティング(Glicko-2 System)というレーティングアルゴリズムについて説明します．

  • 「アルゴリズムの中身をはやく知りたい！」という方は，下の『本題：グリコ2レーティングのしくみ』からご覧ください．

  • アルゴリズムの説明には数式が登場します．「数式なんて見たくない！」という方は，この記事の前半でレーティング全般およびその歴史について書いたので，そちらでレーティングに対するイメージ・理解を深めていただければ嬉しいです．

はじめに：レーティングとは

　みなさんは「レーティング」という言葉を聞いて，どんなものが思い浮かびますか．

　国語辞書でレーティングを調べてみると，次のような意味が載っています．

１ 段階や等級による格付け。

２ 定まった数式にあてはめて算出した、競技者の実力の評定。「ヨットレースのレーティング」

３ テレビ・ラジオなどの視聴率。

４ 証券会社や格付け機関などが行う、株式や債券などの騰落予想、信用格付け。「大手証券会社がA社のレーティングを上げた」

　レーティングの語源であるrateには，「評価する」「見積もる」のような意味があり，そこから派生して色々な意味でレーティングという言葉が使われています．

　今回の記事は，ゲームのレーティング対戦で使われるレーティングシステムに関するものです．上で言うと2番目の意味になります．

ところで，みなさんはゲームでレーティング対戦をしたことがありますか？

　レーティング対戦をご存じでない方や，あまり馴染みがない方のために簡単な説明をしておきますと，レーティングとは，プレイヤーのゲームの実力を数値化し、客観的に実力を判断する指標の1つです．2人のプレイヤーがゲームの対戦をした時，勝利したプレイヤーのレーティングは上がり，敗北したプレイヤーのレーティングは下がります．

　たとえば，ポケットモンスターサン・ムーンの通信対戦では，レート対戦とフリー対戦という2つのモードがあります．レート対戦では，各プレイヤーに「レートポイント」という数値が与えられます．レートポイントは1500から始まり，バトルに勝てば増加し，バトルに負けると減少します．このようなレーティング対戦を導入しているゲームはポケモンだけでなく，将棋・チェスなどのボードゲームや，サッカーのような2チームが対戦する形式のスポーツでも導入されることもあるようです．

　今回の記事の内容は，レーティングの計算方法についてです．現在ではさまざまなレーティングシステムがありますが，その中でGlicko-2 System(以下グリコレーティング2)というレーティングシステムについて説明します．

レーティングシステムの歴史

　いきなりグリコ2の説明に入る前に，Wikipediaの記事を参考しつつ，レーティングシステムの歴史を簡単に振り返ってみます．

　チェスなどの2人制ゲームにおいて，プレイヤーのゲームの実力を数値化する考え方は少なくとも1900年代からありました．レーティングの算出方法として，1948年にIngo systemというアルゴリズムがAnton Hoesslingerによって考えられ，その後1956年にHarkness systemが Kenneth Harknessによって考えられました．それから1960年頃，アメリカの物理学者・チェスプレイヤーのArpad Eloによって，イロレーティング (Elo rating)が提案されました．イロレーティングは非常に広く知られているレーティングシステムであり，現在でも将棋，チェスのようなボードゲームや，対戦型オンラインゲームのランキングやマッチング，サッカーのようなスポーツなど，様々なところで取り入れられています．

　その後，1995年にMark Glickmanはイロレーティングを改良したレーティングアルゴリズムとしてグリコレーティング(Glicko rating system)を発明し，2013年にこのグリコレーティングをさらに改良したグリコ2レーティング(Glicko-2 ratingSystem)を発明しました．

　イロレーティングと同様に，グリコレーティングおよびグリコ2レーティングは様々なオンラインゲームのレーティング対戦で導入されています．たとえば，シャドウバースはグリコ2レーティングに基づいてレーティングを算出しているようです．さらに，Nintendo Switch用ソフトSplatoon2でも，正式な発表はされていませんが，グリコレーティングのWikipediaや海外サイトで，ガチパワーなどのレーティングの算出にグリコ2レーティングが使われているという情報がありました．

What is "Power" anyway? ---"Power" is actually a Glicko2 rating.

oatmealdome.me

　また，イロレーティングやグリコレーティング，グリコ2レーティングは1対1のチェスを想定したレーティングシステム(グリコレーティング，グリコ2レーティングも1対1，1チーム対1チームを想定したものです)ですが，Microsoftは2007年に3人以上でプレイするゲームでも適用できるTrueSkillというレーティングアルゴリズムを開発しました．

www.microsoft.com

本題：グリコ2レーティングのしくみ

世界中のオンラインゲームで利用されているグリコ2レーティングですが，このレーティングシステムについて日本語の解説されている記事が見当たりませんでした(調査不足だったらごめんなさい...)．そこで，グリコ2レーティングについての論文Example of the Glicko-2 systemを読み，自分なりにアルゴリズムの内容を理解し，Pythonでプログラムを実装して数値計算をしてみました．今回の記事では，グリコ2レーティングの仕組みをできる限り丁寧に説明していきます．

注意：本記事では，グリコ2レーティングのアルゴリズムの説明だけにとどめました．アルゴリズムに出てくるパラメータの直感的な意味は，論文に書かれていますので，興味のある方はそちらをご覧ください(後日この記事にも追記するかも...？)．また，アルゴリズムの背後にあるレーティングシステムの数理・理論的な背景については論文にもあまり書かれていなかったのと，私自身の知識不足のため，説明を省かせていただきます．

ゲームの状況設定・表記法

  • 1対1，あるいは1チーム対1チームの対戦ゲームを対象とします．
  • ゲームに参加している各プレイヤーは，レーティング(rating) {r} ，レーティング偏差(ratings deviation) {\mathrm{RD}} ，レーティング変動率(rating volatility) {\sigma} というパラメータをもっています．
  • プレイヤーPのレーティングが {r} ，レーティング偏差が {\mathrm{RD}} ，レーティング変動率が {\sigma} であったとき，{\mathrm{P} = (r, \mathrm{RD}, \sigma)} と表記することにします．
  • プレイヤーがもつ3つのパラメータの値は，試合をするたびに更新されます．このアルゴリズムのゴールは，試合後のレーティング {r'} ，レーティング偏差 {\mathrm{RD'}} ，レーティング変動率 {\sigma'} を計算することです．
  • パラメータの更新方法はグリコレーティングの方法をベースとしています．ただ，各パラメータの値のスケールがグリコレーティングとグリコ2レーティングで異なるので，スケールの変換を2回行う必要があります．

ステップ1：３つのパラメータの初期値と，定数τの値の決定

プレイヤーPのもつパラメータ{(r, \mathrm{RD}, \sigma)}の初期値を設定する．

  • 各パラメータの標準的な初期値
    • レーティング {r} は1500．
    • レーティング偏差 {\mathrm{RD}} は350．
    • レーティング変動率 {\sigma} は0.06(実際に使われる場面に応じて適切な値に設定しておく必要がある)．

また，定数 {\tau} を，(基本的には)0.3から1.2までのどれかの値にする．

ステップ2：スケール変換

プレイヤーPのレーティング {r} とレーティング偏差 {\mathrm{RD}} のスケールを変換し，変換後の値 {\mu, \phi} を計算する．レーティング変動率 {\sigma} にはスケール変換を施さないことに注意する．

\mu = \frac{r - 1500}{173.7178}, \ \phi = \frac{\mathrm{RD}}{173.7178}

これ以降，プレイヤーPが {m} 人の対戦相手 {\mathrm{P}_1, \mathrm{P}_2, \cdots, \mathrm{P}_m } と試合をしたとし，試合後にパラメータ {(\mu, \phi, \sigma)} を更新する．ここで， {i} 番目( {i = 1, 2, \cdots, m} )の相手 {\mathrm{P}_i} のレーティング(のスケール変換後の値)を {\mu_i} ，レーティング偏差(のスケール変換後の値)を {\phi_i} とおく．また，プレイヤーと各対戦相手 {\mathrm{P}_i} の対戦結果を {s_i} とおく．ただし，プレイヤーPが対戦相手 {\mathrm{P}_i} に勝利したとき {s_i = 1} ，引き分けであったとき {s_i = 0.5} ，敗北したとき {s_i = 0} とする．

ステップ3： {v} の計算

以下で表される量 {v} を計算する．

\displaystyle{ v = \Bigl[ \sum_{j=1}^{m}g({\phi_j})^2 E(\mu, \mu_j, \phi_j) \{1 - E(\mu, \mu_j, \phi_j) \} \Bigr]^{-1} }

ただし，

\displaystyle{ g(\phi) = \frac{1}{\sqrt{1 + 3\frac{\phi^2}{\pi^2}}} }
\displaystyle{ E(\mu, \mu_j, \phi_j) = \frac{1}{1 + \exp(-g(\phi_j))(\mu - \mu_j)} }

とおいた．

ステップ4： {\Delta} を計算する．

\displaystyle{ \Delta = v \sum_{j=1}^{m} {g(\phi_j)\{s_j - E(\mu, \mu_j, \phi_j) } \} }

ステップ5：更新後のレーティング変動率 {\sigma'} を反復により求める．

①{a} を {a =\log( \sigma ^2 )} (ただし対数の底は {e} )とし，関数 {f(x)} を次のように定義する．

\displaystyle{ f(x) = \frac{e^x(\Delta^2 - \phi^2 - v - e^x) }{2(\phi ^2 + v + e^x)^2} - \frac{(x-a)}{\tau^2} }

また， {\varepsilon = 0.000001}を非常に小さな正数とする．

② 以下のように反復アルゴリズムを設計する．

  • {A} = a = \log( \sigma ^2 ) とする．
  • もし {\Delta^2 > \phi^2 + v} ならば， {B} = \log( \Delta^2 - \phi^2 -v ) とする．

  • もし {\Delta^2 \leq \phi^2 + v} ならば， 次のような反復を行う．

    (a) {k=1} とする．

    (b) もし {f(a - k \tau ) \lt 0} ならば，{k \leftarrow k + 1} として (b)へ．

    その後， {B = a - k \tau} とする．

③ {f_A = f(A), f_B = f(B)} とする．

④ {|B - A| > \varepsilon} のとき，次の反復を行う．

　(a) {C = A + (A - B) \frac{f_A}{f_B - f_A}, f_C = f(C) } とする．

　(b) もし {f_C f_B \lt 0} ならば，{A \leftarrow B, f_A \leftarrow f_B} とする．

　(c) もし {f_C f_B \geq 0} ならば，{f_A \leftarrow \frac{f_A}{2}} とする．

　(d) {B \leftarrow C, f_B \leftarrow f_C} とする．

　(e) もし {|B - A| \leq \varepsilon} ならば反復をストップして⑤へ．そうでなければ(a)へ．

⑤一度でも {|B - A| \leq \varepsilon} が成り立ったならば， {\sigma' \leftarrow e^{\frac{A}{2}}} とする．

ステップ6： {\phi^*} の計算

次のように表される {\phi^*} を計算する．

\displaystyle{ \phi^* = \sqrt{\phi^2 + \sigma'^2} }

ステップ7：レーティング，レーティング偏差の更新

次のようにレーティング，レーティング偏差を更新する．

\displaystyle{ \phi' = \frac{1}{\sqrt{\frac{1}{{\phi^*}^2} + \frac{1}{v} } } }
\displaystyle{ \mu' = \mu + {\phi'}^2 \sum_{j=1}^{m} {g(\phi_j)\{s_j - E(\mu, \mu_j, \phi_j) } \} }

ステップ8：元のスケールに変換し，レーティングとレーティング偏差の更新

試合後のプレイヤーのレーティング {r'} とレーティング偏差 {\mathrm{RD}'} を次の更新式にしたがって計算する．

\displaystyle{ r' = 173.7178\mu' + 1500 }
\displaystyle{ \mathrm{RD}' = 173.7178 \phi' }

以上より，プレイヤーPのもつ3つのパラメータ {(r, \mathrm{RD}, \sigma)} を {(r', \mathrm{RD}', \sigma')}に更新することができました．

数値実験

グリコ2レーティングの論文に書かれている数値実験の例を載せておきます．

  • プレイヤーPが，3人の対戦相手 {\mathrm P_1, \mathrm P_2, \mathrm P_3} と対戦します．
  • 試合前の各プレイヤーのパラメータを次のように設定します．
    • {\mathrm{P} = (r, \mathrm{RD}, \sigma) = (1500, 200, 0.06)}
    • {\mathrm{P_1} = (r_1, \mathrm{RD}_1, \sigma_1) = (1400, 30, \sigma_1)}
    • {\mathrm{P_2} = (r_2, \mathrm{RD}_2, \sigma_2) = (1550, 100, \sigma_2)}
    • {\mathrm{P_3} = (r_3, \mathrm{RD}_3, \sigma_3) = (1700, 300, \sigma_3)}
    • (プレイヤーPの試合後のパラメータの値を知りたいので，対戦相手のレーティング変動率は不要です．)
  • 定数 {\tau} を {\tau} = 0.5とします．

　グリコ2レーティングを用いて試合後のプレイヤーPのパラメータ {(r', \mathrm{RD'}, \sigma')} を 計算すると，{(r', \mathrm{RD'}, \sigma') = (1464.06, 151.52, 0.05999)}という結果になります．アルゴリズムの各ステップの計算結果( {v, E, \Delta, A, B, C}の値など)は論文の後半に詳しく書かれているので，それらの値を知りたい方はそちらをご覧ください．

　上の結果は論文に書かれていたものですが，僕がPythonで実装して数値計算をしたところ，{(r', \mathrm{RD'}, \sigma') = (1464.05, 151.51, 0.05999)}になりました．2つのパラメータの小数第二位が1だけズレていますが，概ね論文通りの結果になったと言えるでしょう...．

おわりに

グリコ2レーティングのアルゴリズムの説明をしました．何度か見直しましたが，もし誤字や分かりづらい箇所があったら申し訳ありません．

次回は，このグリコ2レーティングを用いて，Splatoon2のリーグパワーの算出をしてみたり，プライベートマッチにプラベパワーというレーティングを導入してプラベ内でレート戦を再現してみた，という記事を書こうと考えています．

参考文献