MATHGRAM

主に数学とプログラミング、時々趣味について。

AlphaGoの論文を日本語に訳してまとめてみた!(まだまだ未完成)

こんにちは。
今回はAlphaGoの論文を日本語に訳してまとめてみました。
本論文はこちらにございます。
Mastering the game of Go with deep neural networks and tree search : Nature : Nature Research

もしバンバン論文読みまくってるエンジニアさんやマスターの学生さんに読んでもらえ、なおかつ間違っている部分や詳しい理論部分の説明をコメントで残してくれますと泣いて喜びます。

またdeep learningやAlphaGoに少し興味があるけどエンジニアでもないし論文とかちょっと無理・・・って方や、機械学習に興味ある高校生などに少しでも理解を深めるきっかけを与えることができたら、それも泣いて喜びます。そういう人たちのためになるべくわかりやすい説明も加えていくつもりです。こんな上から目線の発言をできる立場じゃないですけど・・・。

ここでモチベーションがぶれないように、目的をまとめておきますね。

目的

  • 曖昧な部分を明確にしたい。

正直、まだまだ論文を読むのに慣れていなくて英語のまま読んでいるとどうしても内容が入ってこない部分が出てきてしまいます。なので、本当に隅々まで理解したいこの論文を、しっかり訳すことで全貌を把握したい!というモチベーションです。もちろんいずれは英語のままスラスラ理解できるように練習していくつもりです。

  • 友人のため

機械学習に興味ある友人がめっちゃ英語嫌いなので、とりあえず全訳しとく。

  • フィードバックが欲しい・・・

心優しい有識者に間違ってる部分を指摘して欲しいです・・・

目的は以上です!!

まとめ方として、訳は意味が伝わればおk。くらいの軽いノリで書くのでラフな感じで読んでくれると助かります。もちろん理論部分は厳格に訳していきます。
章ごとに簡単なまとめを加えるので、そこも読んでくださると嬉しいです。(是非ここを指摘して欲しい・・・)
あと、いい感じの日本語訳が付いていない専門用語はそのまま英語で書きます。
それでは早速まとめていきますね。

Mastering the game of Go with deep neural networks and tree search

Abstract

長い間、AI(人工知能)にとって囲碁は古典的なゲームのなかで最も困難な問題とされてきた。それは膨大な手の候補数や、局面評価の困難さに起因している。ここで私たち(Googleの天才たち)は、囲碁AIの新たな手法として、局面評価のための"value networks"と次の手を選択するための"policy networks"を組み合わせたアプローチを提案する。これらのDeep neural networkはプロの棋譜を教師データとして教師あり学習(supervised learning)させた後、自らと戦わせることで強化学習(reinforcement leraning)させることにより学習を行った。この際"lookahead search"は使わずに、最新のモンテカルロ木探索(Monte-Carlo Tree Search)を用いて、何千もの対戦を行わせた。また私たちは新たな探索アルゴリズムとして、"value networks"と"policy networks"、さらにモンテカルロ木探索を組み合わせたものを導入した。このアルゴリズムを用いることで、AlphaGoの勝率は他のコンピュータ囲碁ソフトに対して99.8%に達し、またヨーロッパチャンピオンをボコボコにした。これはフルサイズの囲碁盤面におけるプロとの対局で、初めてAIが勝利したという事実であり、今後10年はかかるであろうと考えられていた偉業である。

Abstractのまとめ

ポイントは3つでしょうか?
1つ目は盤面評価のネットワーク(value networks)と、最善手を選択するためのネットワーク(policy networks)が別々に構築されているという点。
2つ目は教師あり学習のあとに、自分と戦わせて強化学習を行っているという点。
3つ目はボードゲームのAIでよく用いられているらしいモンテカルロ木探索も使っている点。現在、僕はこのアルゴリズムを理解していないので勉強してきます。

ここで全く機械学習などに関する知識を持っていない方のために、教師あり学習と強化学習について簡単な説明をしておきます。

教師あり学習とは正解を与えてネットワークを学習をさせる方法で、ネットワークが持っている何十万のパラメータを、こっちが与えた正解に合わせて調整していくという方法です。画像処理を例に挙げると、ライオンの画像をネットワークに読み込ませた後(この時点ではまだライオンとわかっていない)に、"これはライオンなんだぞ"とネットワークに教えてあげることでパラメータを調整していきます。ちなみにパラーメータを調整すること"学習"と呼びます。

また強化学習とは、現在の状態から一番報酬がうまい選択をするように学習をしていくという方法です。ある状態にいるAI(通常エージェントと呼ばれます)がランダムに行った行動の結果、"なにこれ!めっちゃ気持ちええwww"と感じたら、次その状態(もしくは似た状態)にエージェントが行き当たった場合、過去に気持ち良かった記憶を頼りに、かつてランダムに取った行動と同じ行動を取るように学習していく、というイメージですね。もちろんどんな行動(強化学習では方策"policy"と呼ばれます)をしたら気持ちいいのかは、実装する人間が設定をします。多分AlphaGoの場合は、ある局面で取った行動の結果、勝利に繋がったら"気持ちええww"と定義しているのだと思います。まだただの予想ですけど。

とりあえず上の二点に注目しながら読み進めていきます。
まだabstractしかまとめてないけど記事投稿しちゃいますね。まとめ次第どんどん更新していきます!!

4/29:Introduce更新しました。

イントロから少し難しくなってきますが、最後のまとめでできるだけわかりやすくします!

Introduce

全ての完全情報ゲーム(games of perfect information)はある一つの最適値関数v^*(s)を持っていて、それはゲームの結果を決定づけるものである。これらのゲームは約b^d通り存在する手を考慮した探索木における最適値関数を、再帰的に計算することにより解くことができる。ここでbとは"breadth"、つまりは幅のことであり、dは"depth"、深さのことである。幅はその局面でルールに則った手を指せる"幅"のことであり、深さはそのゲームが何手まで続くかを表したものである。例として、チェスの場合はb \approx 35,d\approx 80程度である。特に囲碁の場は組み合わせ数が爆発的に多くなり、b \approx 250,d\approx 150である。この場合、完全な探索は実行不可能とほぼ同値であるが、一般的に知られている二つの方法をとることで、この組み合わせ数を減らすことができる。まず第一に、局面の見積もりを行うことで深さを軽減することができる。これはつまり状態sのにおける探索木の浅い部分を切り取ることを意味していて、その切り取った後の木を新たにsとおくことで深さを軽減するという手法である。このアプローチはチェスや、オセロなどでは成功を収めてきたが、囲碁ではゲームの複雑さから大きな前進にはならなかった。二つ目は、状態sからの行動aを、p(a|s)とする確率分布からサンプリングすることで幅を減らすという方法である。例えばモンテカルロ木探索では、ある方策p全ての枝を通ることなくもっとも深い部分まで到達することができる。この方法により、バックギャモンスクラブルでは人間を超える成果を出し、囲碁においてはアマチュアレベルまで到達することができた。

まだintro一段落ですが。眠いのでここまで。

5/1:Introduce追記しました。

モンテカルロ木探索(以下MCTS)は、探索木に含まれているそれぞれのstate(局面)を評価するためにMonte Carlo rolloutsを用いるアルゴリズムである。探索が進むにつれて探索木は大きくなっていき、局面評価も正確に行えるようになっていく。より価値の高い子(探索木において現在のノードを親とする時、そこから深い方に伸びるノードを子と呼びます。)を選択することにより、次のノードを選択する方策もまた改善されていく。この方策(次の一手を選ぶこと)は漸近的に、最適な一手に収束していき、局面評価も最適値関数に収束していく。最近のコンピュータ囲碁は、よりプロに近い手を価値が高いものとして学習された方策によって強化された、MCTSベースのものが主流であった。この方法は探索する幅を狭めるために有効であり、アマ強豪レベルまで達した。しかし、探索が可能な深さなどに限界があるために、それ以上の成果を伸ばすことはできなかった。

今日、畳み込みニューラルネットワーク(以下CNN)は視覚的な分野で大きな進歩を遂げている。例えば、画像分類、画像認識、顔認識などである。こららのタスクでは、膨大なニューロンにより構成された厚い層を用いていて、画像の局所的な特徴をうまくとらえることにより高いパフォーマンスを実現している。我々は、これらに似た設計を囲碁にも適用させた。盤面と同じ大きさである19×19の画像をネットワークに与え、駒の配置の情報をとらえるためにCNNを用いた。そして結果的に探索の幅や深さを軽減させることに成功した。またネットワークは二種類使っていて、局面評価にはvalue networkを、次の手の選択にはpolicy networkを使っている。

我々は、これらのネットワークをいくつかのステージに分けて学習させた。その概略を図1に示す。 論文より抜粋。
f:id:ket-30:20160501203250j:plain
図1,Neural network training pipeline and architecture.

まず、policy networkをプロの棋譜から教師あり学習をするところから始める。この方法は、効率的に高いクオリティの勾配計算を可能にする。また今までの方法に似たように、rolloutsの間に素早く手を選択できるfast policyも学習させた。(すみません、今はここよくわかりません。)その次に、policy networkを強化学習させた。これは自分自身と戦わせて、最終的な結果を報酬と考えることで学習を進めていくものである。これによりプロと同じ手を指す確率を上げることよりも、直接的に勝利に近い手を指せるようにネットワークを学習することが可能となる。最後に、value networkを学習させた。これは局面からゲームの勝者を確率的に計算するネットワークであり、教師データは自らと戦わせることによって得た棋譜を用いている。我々のAlpha Goは、効果的にMCTSと、value network, policy network を結合させているのである。

Introduceのまとめ

以上でintroは終わりです。まだまだ見えてこない部分が多いですね。ほとんどabstractで得られた情報の詳細となっていますが特筆すべきは以下の点でしょうか。

  • value networkの教師データは自らと戦わせた棋譜を用いている。

読んでいて、なるほど。と思いました。まず教師あり学習ではプロの棋譜を教師としていて、いかにプロに近い手を指せるかを求めています。しかし、これは人間を真似ているだけであり、将来的に強さが頭打ちになるのは想像に容易いですね。そりゃ真似ごとだけじゃ一番にはなれません。そのため、より勝利に近い手を指せるように学習されるのが強化学習ということになります。

計算コストがとんでもないような気がしますが、" 勝利"というものを報酬として強化学習することにより、プロが指す手よりも勝利に近い手を指そうとしているというわけです。しかし、強化学習をいきなり手当たり次第にやっていたら恐らく一生かかっても学習は終わらないでしょう。そのために教師あり学習で、ある程度勝利が保証されている手を指すようにしていたということですね。プロの棋譜を用いる教師あり学習は前座に過ぎなかったと。

結果的には自分と戦わせた棋譜がメインの教師データになっているわけで、"お前らのデータじゃ強くなれねーよ"という人類に対する煽りを感じます。笑

後々出てきますが、プロがある座標に75パーセントの確率で指す局面で、別の座標をAlphaGoは選択していたりします。恐らく教師あり学習のみでは75%の手を選択していたことでしょう。まあこういう局面だったら大体こうじゃん?みたいなバイアスがかかった局面というのは例えプロでも存在するんだと思います。AlphaGoはそういう"お決まり"("定石"は研究の上に成り立っているので、ここでは区別しています。)にとらわれない、より勝利に近い手だけを選択するようになっていくんですね。

ここからネットワークの中身の部分、つまり理論の部分に移ります。恐らく僕の能力じゃ理解できない部分が多々出てくるでしょう。そういう部分はとりあえず訳しておいて理解し次第訂正していくことにします。