「NCAAバスケットトーナメント試合結果予測コンテスト」2014年優勝者のモデルをまとめてみる
１．コンテスト概要
さて今回は、最近知人に教わって始めた、「kaggle」というデータ解析系のプログラミングコンテストに関するお話です。「kaggle」についてざっくり説明すると、主催者が問題とデータを与えて、参加者が与えられたデータをもとにその問題を解決するアルゴリズムやモデルを開発する、というコンテストです。一番良いモデルを作った人は賞金を受け取るかわりに、主催者にモデルを提供する、といった感じです。
今回はその中でも、「March Machine Learning Mania 2015 - Predict the 2015 NCAA Basketball Tournament -」に参加してみようと思います。こちらもざっくり説明すると、「NCAA男子バスケットボールトーナメント」という、毎年３月に開催される全米大学対抗バスケットボール大会のトーナメント試合結果を予測する、というもので、今年の３月に実際に行われる試合結果を最も良く予測した参加者が優勝となります。つまり、コンテストの結果がわかるのは、今年のトーナメントの試合が全て終わってからとなります。
ということで今回はこのコンテストに参加してみようかと思います。が、その前に、これ毎年やってるんだったら去年もやってるんじゃないか？と思ったので調べてみたら、案の定やってて、しかも 、昨年の優勝者のモデルに関する論文「Building an NCAA mens basketball predictive model and quantifying its success」まであったので、実際に参加する前に、この論文のモデルについてまとめてみようと思いました。ちなみに、「優勝者インタビュー」なんてのもありました。余談ですが、優勝チームのMichael J. LopezさんとGregory Matthews さんは大学の教員みたいです。
２．問題設定
モデルの内容に実際に入る前に、まずは問題設定を明確にしたいと思います。トーナメントの参加チーム数は６８チームで、８チームは１回戦があり、残りの60チームは２回戦から(128チームのトーナメントで６０チームがシード)となります。全部で６７試合(頭の体操とかでよくある問題で、優勝チーム以外が試合で負けるので、全試合数 = 敗者数 = ６８－１) あるので、この試合の結果を最も良く予測できたチームが優勝となります。では、モデルの良さはどうやって評価するのでしょうか？Team1対Team2の試合の予測の良さは以下の「Log Loss」と呼ばれる損失関数によって評価します。
(Log loss) = -(yt log(yp) + (1 - yt) log(1 - yp))
yt:Team1がTeam2に勝つ真の確率、yp:Team1がTeam2に勝つ予測確率であり、yt は真の確率なので、Team1が勝つか負けるかで{1,0}の２値のどちらかをとります。式をみてもパッと入ってきませんが、 yt = 1 (Team1が勝つ)の場合を考えてみると、
(Log loss) = - log(yp)
となります。yp = 1、つまり正しく予測をしたときは(Log loss) = 0 となり、yp = 0、つまり間違った予測をしたときは、(Log loss) = ∞となります。y = - log(x) ( 0 ≦ x ≦ 1)を見てみるとわかりますが、Team1が勝つ自信があるのであれば、yp を限りなく１に近づけるべきですが、もし外れると物凄いペナルティを受ける、といった関数になっています。yt = 0 のときも確率が反対になるだけで、基本的に考え方は同じになります。
この(Log Loss) の値を全67試合に対して合計して、一番損失が少なかったコンテスト参加チームが優勝となります。ただし、トーナメントが始まる前にはどの67試合が実際に行われるのかわからないので、コンテスト参加チームは、全試合パターン 68*67/2 = 2278 の試合結果の予測確率を提出することになります。実際に使われるのは67/2278 という悲しい現実ですが、全パターンに対してうまくモデルを立てる必要があります。。。
３．2014年優勝者のモデル
では、実際に2014年優勝者のモデルについて説明したいと思います。「kaggle」から過去のトーナメントの勝敗結果や詳細なスコアデータが与えられていますが、コンテストのルールとしては、外部から自由にデータを持ってきても良いとのことです。とうことで、データの選択がまず第一の肝となります。今回、優勝者は2つのデータを利用しています。
1つ目のデータは、「Las Vegas point spread」というものです。「Las Vegas point spread」はスポーツギャンブルで使われる値で、ある試合における（Las Vegas point spread）= -5.5である場合、（１）ホームチームが5.5点以上差をつけて勝つ、あるいは、（２）ホームチームが5.5以下で勝つ or 負ける、のどちらかに賭ける、というものです。この値が適切であれば、（１）と（２）の確率が5分5分となるので、この値は、チームの勝利確率に関する情報を統合したものであると考えることができます。
2つ目のデータは、「 Efficiency metrics」というもので、過去の試合結果の得失点とボール保有率をもとに算出された値で、データに基づいたそのチームの強さを表しています。このデータはKen Pomeroy さんが作成したウェブサイトから入手できます(有料っぽいけど。。。)。
これら2つのデータをもちいて、2つのモデルを作成しています。それぞれのモデルは、ロジスティック回帰という「Log Loss」と関連性のある（ロジスティック回帰の尤度関数を最大化する確率＝Log Lossを最小化する確率）シンプルなモデルを用いて作成します。そして、それら2つのモデルを重みづけして組み合わせたモデルを最終的なモデルとして提出しています。モデルを作成する際に訓練データとして、過去のトーナメント結果のみでなく、トーナメント参加者を決めるレギュラーシーズンの結果も用いることで、訓練データ数を増やしていることも特徴の一つです。
４．シミュレーション結果
このモデルによって、彼らは見事に優勝を勝ち取ることができましたが、実際の試合結果がたまたまよかっただけかもしれない、ということで、論文では実際にシミュレーションも行っています。自分たちの作成したモデルによる予測確率分布Pが正しかったとして、その予測確率分布Pから10000通りの試合結果を生成したときに、それぞれの試行でその予測確率分布Pがコンテストで何位になるかを検証する、というシミュレーションです。結果としては、
- コンテスト平均順位：14位
- コンテストで1位になる確率：11.65パーセント
- コンテストで10位以内に入る確率：44.47パーセント
で、たとえ正しく確率分布を予測できていたとしても、コンテストで1位になる確率は10パーセント近くしかないのだとか。。。結局、これだけ大量なパターンのなかから１つのパターンを予測するので、優勝するにはある程度運要素が必要である、と結論付けています。
５．まとめ
インタビューや論文で、彼らは以下のように述べています。
- モデルの精巧さよりも、どのデータを使うかが重要
- 訓練データとして、トーナメント結果に加えてレギュラーシーズンのデータも使うのは重要（使えるデータは使おう）
- なんやかんやで、コンテストに勝つためには、運も必要。
ということで、昨年の優勝モデルについて勉強したので、締切の3月中旬ごろまでに、実際にモデルを作ってみようと思います。kaggleのコンテスト参加自体がほぼ初めてなので、最初は半分より上ぐらいを目指したいですね。
"Neural Turing Machines"
さて今回は、冬休みの時間のあるうちにと思い、MIT Technology Review 誌でもBest of 2014 の１つとして選ばれていた、「"Neural Turing Machines"」についてまとめました。紹介する論文は、Google の Deep Mind の方々によって書かれたものです。
簡単に要約すると、
・"Neural Turing Machines" とは、チューリングマシンのように外部記憶装置を持ったニューラルネットワークである。（そう考えるとある意味で、リカレントニューラルネットワークは、内部記憶装置をもったニューラルネットワークといえる。）
・外部記憶装置はN×M行列（N行のM列データ）であり、記憶装置の読み書きヘッダは各行へのアクセスを調節する重み{w1,w2,w3, ... , wn: w1+w2+w3... +wn = 1}をもつ。
・重みは、調整パラメータによって調整される。
・調整パラメータは、ニューラルネットの中に埋め込まれており、大量データによって学習され、所望の外部記憶装置へのアクセスを実現するための重みを調整する。
・このようにして学習する外部記憶へのアクセスによって、コピー、繰り返しコピー、連想呼び出し、Nグラム法、ソート、などの動作をある程度実現できる。また、外部記憶装置への読み書きも、理にかなった方法で実現されている。
といった感じです。ざっくりまとめたので、詳細が気になる方は、是非、原論文を読んで頂ければと思います。
とりあえず、論文まとめたりするのはこの辺にして、今後はプログラムを勉強して、実際に色々と実装してみる習慣をつけていきたいです。
Neural Network の Universality について
今回は、最近勉強していた本の内容の紹介です。復習もかねて、スライドとしてまとめてみました。「Slide Share」 を使ってみたかったので、「Slide Share」に内容をアップロードしました。
紹介する本は、「Neural networks and deep learning」 という Michael Nielsen 著のフリーのオンラインブックです。まだ、Deep Learing の章は全てアップロードされていないので、Neural Network の章についてのみ、まとめました。
本自体も初学者向けなので、他分野の方でも、「人口知能ってなんや？」「ニューラルネットワークってなんや？」ということについてなるべく伝わるようにまとめたつもりなので、興味がありましたらスライドをご参照いただければと思います。
また、Nielsen がもともと量子情報処理分野の研究者なので、かなり理論的に直観的にNeural Network について説明していたという意味で、本は普通の教科書と違う視点で書かれていました。そういう意味で、Neural Network について精通しているかたにも参考となる本だったので、英語に抵抗がないかたにはぜひおすすめしたい本でした。特に、今回まとめた Universality の話は、直観的で分かりやすかったです。まぁそれよりも、なんといっても無料というところが肝ですね（笑）。英語が苦手なかたも、本の部分的な内容について一応まとめたつもりなので、興味がありましたらスライドをご参照いただければと思います
「Human Computation」 -歪み文字による画像認証に隠されたもう１つのお話-
今回は論文の研究内容について、まとめてみようかと思います。論文の研究内容と言っても、皆さんも一度はみかけたことのある歪み文字による画像認証に関してのお話で、私が初めてこの話題を知ったのも日経新聞の記事ですので、数式ガリガリの専門バリバリな感じではないので、取っつきやすくて分かりやすい内容かなと思います。そして何より、初めてこの内容を知ったとき純粋にそのアイディアの美しさに感動を覚えました。本気で感動しました。
さて、前振り十分なところで、早速本題に入りたいと思います。「歪み文字による画像認証」と聞いてもピンと来ない人もいるかと思います。そんな方でも、下の画像(Wikipediaより引用)を見たら、「あっ見たことあるやつだ！」となるのではないでしょうか？
そうです。よくgmailなどのWebメールでアカウントを作成する時などに見かける、あの歪んだ文字の画像です。この画像は、「人間とコンピュータを区別するため」のもので、例えば、Webメールでフリーアカウントを"ボット"（要するにコンピュータプログラム）で自動で大量に作成して、迷惑メールを大量送信するのを防ぐために使われるものです。アカウントを取得するまえにこの画像を表示して、アカウント作成者に画像の歪んだ文字を入力させることで、入力文字が正しいかどうかでアカウント作成者が人間かコンピュータかを判断し、人間ならばアカウント作成を許可するというものです。この方法が成立するのは、人間（より正しくいうと目に障害を持っていない人間）は歪んだ文字を読み取ることが出来るが、コンピュータ（より正しくいうと現在のコンピュータによる画像認識技術）は歪んだ文字を読み取ることが出来ない、という人間とコンピュータの特性をうまく利用しているからです。ちなみに、この「歪み文字による画像認証」の正式名称は「CAPTHA」で、"Completely Automated Public Turing test to tell computers and Humans Apart" の略で、あるコンピュータが知的かどうか？を人間とコンピュータの見分けがつくかどうかで判断する "Turing Test" にその語源をもっています。
さて、この「CAPTHA」自体が十分に実用性があり、それ単体でもgmailなどの様々な企業のサービスで利用されている素晴らしい技術なのですが、実はこの「CAPTHA」には、もう１つの隠されたお話があります。
この「CAPTHA」の実用化が浸透して、現在、２億人以上のユーザーがこの認証に１０秒ほどの時間を費やしています。これは、計算すると毎日５０万時間も無駄にしていることになります。この無駄に気付いた「CAPTHA」の開発者の１人であるLuis Von Ahh(ルイス・フォン・アーン)氏は、この無駄な時間を上手く利用できないか？ということで「reCAPTHA」というプロジェクトを立ち上げました。このプロジェクトは、認証に使用する文字画像とその入力テキストを本の電子化に利用するというものです。
本の電子化は、本のページを写真で撮影して、その写真を各文字の画像に分割し、その分割画像中の文字をＯＣＲ(光学文字認識)と呼ばれる機械でスキャンして認識することで行われます。しかし、文字がかすんだりした古い本などでは、ＯＣＲでも認識できないような文字が沢山存在します。そこで、「CAPTHA」を利用します。「CAPTHA」に使用する文字画像としてＯＣＲで認識できなかった画像を使用して、その認証によって入力されたテキストをその画像の文字として認識します。こうすれば、コンピュータによって認識できなかった文字も、人間の力を利用することによって認識することが出来ます。
あれ？どうやってその入力テキストの文字が正しいかどうかを判断するの？コンピュータが認識出来なかった画像に対する正解の文字のテキストは分からないんじゃないの？と思った勘の鋭い方がいるかもしれませんが、実は最初に紹介した下の歪み文字の画像のように、２つの文字を表示することでこの問題を回避しています。例えばこの図の、左側をＯＣＲで認識できた正解が分かっている画像、右側をＯＣＲで認識できなかった画像、とすることで、左側の画像に対して正しくテキストが入力された場合にだけ右側も正しくテキストが入力されているだろうと判断します。もちろん、左側の入力が正しいからといって、右側の入力も正しいとは限らないので（人間でも間違えることはあるので）、左側に正解した何十人かが右側に同じテキストを入力した場合に、右側の画像に対して入力されたテキストが正しいということを判断します（もちろん、何人入力したら正解といえるのか？自体がそもそも研究対象になりそうですが・・・）。これで、右側の画像の正解も判明したので、以降は、この右側の画像を先の左側の画像のように正解が分かっている画像として使用することができるようになります。そんなわけで、「そいえば最近、歪み文字による画像認証で、２つ文字が表示される場合があったなぁ」と思ったかもしれませんが、実はその背景にはこのようなお話があったのです。
この「reCAPTHA」のように、コンピュータが解くのが得意でない問題を人間の情報処理能力を利用することで解く、という考え方を「Human Computation」と言います。「reCAPTHA」の開発者であるLuis Von Ahh氏はこの考え方を応用して、現在「Duolingo」という無料の語学学習アプリをリリースしています。こちらについての詳細は割愛させていただきますが、Web上のニュース記事などを教材にして語学学習をすることで、語学を学習すると同時に、Web記事の翻訳に貢献する、というものです。ユーザーは翻訳に貢献することで、無料で語学を学習できるというわけです。
この「Human Computation」は最近流行りのクラウドソーシングの一部としても考えられています。ただ、個人的には、取り上げた題材のように、「～しながら実は～していた」というところに美しさがあるのではないかと考えています。人間の情報処理力を利用するために、人間に他のモチベーションを与えるところに美しさを感じています。３年前ほど前に記事などでも話題となった、「Fold it」 と呼ばれるタンパク質構造予測のためのゲームなども、この「Human Computation」の例となります。
最後に詳細の資料紹介ですが、Luis Von Ahh氏は MIT technology Review 誌の young innovator under 35 にも選ばれており、TEＤでのスピーチもあります。彼の博論もご参考になるかとおもいます（ちなみにお供に持ってきたのがこの博論）。
いやはや、世界には素晴らしい研究者がいるものですね。
「学ぶこと」について
２１日ぶりの更新ということで、目標より早いペースで進んでいます。有言実行とは、まさしくこのことですね。
さて、前回、「勉強とか研究とか～中心に、～まとめていこうと思います」とか書いていたので、まず手始めに今回は、「学ぶこと」について書こうと思います。
数学なんて普段使わないし、世界史の勉強なんてなんの役にもたたない。大学の授業で学んだことなんか仕事で使わないし、卒論・修論の内容なんて社会の役に立たない。このような話をよく聞きます。確かにそうですね笑。もちろん、今まで学んできたことを直接的に仕事に生かせている恵まれた方もいらっしゃるかと思いますが、少数派だと思います。大半の方は、結局今まで学んできたことを直接的に使う機会がほとんどないような職業について、仕事を覚えるために職業現場で苦労する日々を送っているかと思います。では、なぜ、職に就いてから苦労してまで、高校や大学などの教育現場で、そのような ”役に立たない” ことを我々は学んでいるのでしょうか？
この疑問の答えとして、僕がしっくり来ている言葉があります。それは、”Head Fake ( 頭のフェイント )”です。僕がこの言葉を知ったのは、というか、おそらくこの言葉の発祥は、ランディパウッシュの「最後の授業」です。（参考：https://www.youtube.com/watch?v=jyyzWRp_VpM）「最後の授業」自体は、すい臓がんを患ったランディが行った最終講義であり、彼の人生から得られた生き方についての約７５分の講義であり、下手な映画を見るよりも面白いので、ぜひ見ていただきたいのですが、その中で使用された”Head Fake ( 頭のフェイント )”という言葉がとても印象に残っています。この講義の中で、”Head Fake ( 頭のフェイント )”という言葉は、彼が幼少期に習っていたフットボールから学んだこと（動画８分あたりからの話）の要約の中で以下（和訳）のように使われています。
「実は子供たちにスポーツを習わせるということは、”頭のフェイント”なのです。スポーツを習えば技術やルールなど多くのことが身につきます。でも、もっと重要なことは、チームワーク、忍耐力、スポーツマンシップなどです。子供たちは、それらを間接的に学べるのです。それが、”頭のフェイント”です。」
もう大体何を言わんとしているか想像できるかと思います。つまり、僕が思っているのは、高校や大学の教育というのも、”頭のフェイント”から「学ぶこと」が重要だ、ということです。数学では「論理的に問題を整理して、順序立てて解決していく方法」、世界史では「栄枯盛衰の中で自己や組織が長く存続し続けるための意思決定の方法」あたりが、個人的には、学べることじゃないかなと思います。高校や大学で教えているその他のことにも、必ず”頭のフェイント”を通して「学べること」があるはずですし、それを「学ぶこと」こそ教育の目的なのだと思います。
勉強が面白くないと感じるのは、この”頭のフェイント”の存在に気付かずに、勉強する内容に必要性を感じないからだと思います。意識的に、”頭のフェイント”を通して、今「学べることは何か？」を常に考えることで、勉強することは格段に面白くなるような気がします。企業研修とか、つまらないと思われる雑務とかも同じことで、そこから「何か学べることはないかな？」と考えることで、つまらないことが、どんどん面白いことに変わっていくような気がします。（というか、そうでもしないとつまらないことなんてやっていられない笑）
ということで、今回は「学ぶこと」について、より具体的には”頭のフェイント”について書きました。僕もこのブログを読んでもらうことで、”頭のフェイント”で何かを学んでもらうはおこがましいですが、何かを感じとって貰えるような文章を書くことを心掛けていきたいです。
ということで、次回は、自分が研究生活から”頭のフェイント”を通して学んだこと、についてでも書こうと思います。
ブロクを始めようと思った理由
皆さんはどういう理由でブログを始めようと思うのでしょうか？ブログをやったことない人でも、twitter や facebook などの SNS サイトを利用されている人は多くいるかと思います。では、どうして SNSサイトを利用しようと思うのでしょうか？
おそらく、人間誰しも、自分の周りで起こった出来事や自分が考えていることを発信して人に伝えることに、無意識のうちに何かしらの喜びを感じているのだと思います。僕自身も SNS を利用するときというのは、大体、なにか面白いことが自分の周りで起こったり、何か変わったことを考えたりしたときです。ブログを始めようと思ったのも、結局はその延長線上で、何か自分について発信して伝えたいと、どこかで何となく思っているからだと思います。
もう一つ、ブログを始めようと思った理由があります。それは、自分の考えを「明文化」することが、自分のためになると思ったからです。「明文化」とは、「はっきりと文章で書き示すこと」です。文章で書き示す際には、必ず情報の取捨選択があります。自分の頭の中でもやっとしている考えから重要な部分のみを取り出してまとめることで、自分も気がつかなかった新たな考えが出てくるのではないかとちょっと期待しています。また、他人に読んでもらう可能性がある文章として「明文化」することで、分かりやすく面白く伝えるために新たな語彙や知識を収集して、自分の見識を広げられるのではないかとも期待しています。
そんなわけでブログを始めようと思います。じゃあ、何を書くんだ？という話ですが、勉強とか研究とかが結構好きなので、そういうことを中心に、なにか思ってることとか考えてることについて、徒然なるままに、ちょくちょくまとめていこうと思います。特にアフェリエイトとかの営利目的で書くわけではないので、趣味として、月１回を目標とするぐらいののんびりペースで、時にはどーでもよいことも交えながら、書いていこうと思います。何となくですが、「有り体」という言葉を意識して書こうと思います。とりあえず、これが最初で最後の記事にならないように次回頑張ります。
