AlphaGo の論文をざっくり紹介

ある程度機械学習を知ってる人向けです。
わかりやすさ重視でざっくり書くので、詳しいことは本論文をあたって下さい。
ちなみに私は囲碁のルールは知りません。


元ネタはNature論文です。
http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html
とても読みやすい論文だと思います。
オープンアクセス版もどっかに転がってたと思います。

構成要素

AlphaGOは主に、教師あり方策ネットワークp_\sigma, 強化学習方策ネットワークp_\rho, 状態評価関数ネットワークv(s), からなっており、これらをうまく組み合わせて、モンテカルロ法による指し手評価を効率的に行っているようです。


教師あり方策ネットワークp_\sigma

状態s(盤面の石配置など)を入力とし、次の手a(どこに石を置くか)を確率としてp(a|s)の形で返す関数です。
具体的には、13層の畳み込みニューラルネットワーク(CNN)を使い、最終層の出力結果を
ソフトマックス関数にかけて確率解釈しています。
KGSという碁の棋譜が保存されているサーバがあるそうで、そこから3千万のサンプルを教師として使い、
ネットワークをトレーニングしました。
つまり人間の指し手を教師とし、いかに模倣するかというネットワークですね。

結果、57.0%の確率で、人間の指し手を模倣できるCNNができました。
一見低いような気がしますが、それ以前の手法では44.4%の正解にとどまっていたようですし、
実際人間の指し手も多様なので57.0%はすごいみたいです。

このCNNは計算に3msかかるのですが、より精度を落として高速化を狙ったネットワーク
p_\piも用意されています。
p_\piは24.2%の再現度ですが、1回の推論が2マイクロ秒です。
p_\piはモンテカルロ計算の時に良い働きをします。

強化学習方策ネットワークp_\rho

教師ありネットワークp_\sigmaの重みを初期値とし、自分自身と対戦させ、より勝利できるようパラメータを
更新していってできたCNNがp_\rhoです。


強化学習としても手法はかなりシンプルで、ある局面sで行動aを行った時、その方策CNNが勝利した場合、
aから終局までの行動系列の確率が大きくなるように、p_\piの勾配を利用してパラメータを更新します。
敗北の場合は、同様に確率が小さくなるように勾配を使ってパラメータの更新を行います。


こうしてできたCNN p_\rhoはそれ自身強く、教師ありCNNのp_\sigmaと戦わせて8割以上勝ち越し、
アマ2段にランクされるプログラムPachiに対して85%で勝ったようです。

状態価値関数ネットワークv(s)

vはp_\rhoと良く似ていますが、指し手を返すのではなく、局面sに対してその価値を返します。
理想的には、ある局面sに対し、p_\piに従った手を指し続けた場合の勝利の期待値がAlphaGO流のv(s)です。
しかしその計算は大変なので、実際には、p_\pi 同士を戦わせて得られた3000万の局面と勝敗データを利用して学習を行いました。


モンテカルロ探索

以上の構成要素を元に、実際に局面sに対してどのように手aを出すかはモンテカルロ法に基づきます。
状態sに対し、手aはQ(s,a)+u(s,a)の大きさで評価されます。
Q(s,a)はモンテカルロ計算の度にアップデートされる評価関数(後述)で、uはボーナス項と呼ばれています。

u\propto p_{a|\sigma}/(1+N(s,a))という形をしており、教師あり学習CNNの出力p_\sigma*1に比例して、
手aが選ばれやすくなっており、妥当な事前確率分布になっています。
一方N(s,a)は、探索中に局面sでaを打つという状況に遭遇した回数であり、
なるべく広く探索を行うようにバイアスをかける項になっています。


Q(s,a)は、シミュレーション中に(s,a)の組に対して与えられた評価V(s,a)を算術平均して求めます。
具体的には、状態sから、有限の深度Lまで、最も評価関数(Q+u)の大きくなる手を打ち続けます。深度Lで辿り着いた局面をs_Lとしましょう。
s_Lは2つの異なる方法で評価されます。
まずは状態評価CNN v(s)です。v(s_L)がs_Lの評価値を与えます。
もう1つは、状態s_Lからスタートし、高速な方策CNNであるp_\piを用いて主局までゲームを行い、
勝ったか負けたかで評価値z_Lを得る方法です。
実際にAlphaGoが採用したのは、それらの平均、 V(s,a)=1/2 v(s_L) + 1/2 z_L です。
このようにして、シミュレーションの度にQ関数をアップデートし、時間の許す限りtree searchを行います。
(実際にはもう少し、探索深度を動的に伸ばすなどの工夫もありますが、この解説ではパスします。)


感想

CNNによって高速に価値観数vと、終局までの擬似対戦が計算できる(高速方策p_\piによって)、
というのが、いままでの囲碁プログラムと本質的に違う所なのだと思います。


しかし、CNNというのは基本的に画像認識を行うニューラルネットワークであるというのが私の(世界中の?)認識だったので、
ボードゲームの局面評価に使えて、しかもこんなに上手く行くというのは驚きです。
もちろん、DeepMindは昨年、CNNにアタリの評価関数を覚えさせていたので、その延長なのかもしれませんが。


一方、Deep learning業界はずっとCNNだけで良いのだろうか、というのが少し懸念でもあります。
CNNはもともと初期視覚野を工学的に模倣したネットワークであり、全結合ニューラルネットワークと比較して
表現力は落ちているはずなのですが、、、その分勾配消失や過学習には強かったりしますし、まだまだ未知の潜在能力があるのかもしれません。
ただ、この論文からは、CNNを用いたエンジニアリングは上手く行ったと読めるものの、
サイエンスとして何を得られたのかがわからないのが、少し不満です。
しかしまあ、性能出したもの勝ちの世界なのでしょうね。

(余談ですが、囲碁では石を大局的に「紋」と言って模様のように捉えたりするようですが、AlphaGoはパターンマッチングと類似の手法で紋を見ていたのかもしれませんね。)


すぐに思い浮かぶのは、この手法はかなり汎用性がありそうだということです。
チェスや将棋などでも、類似の手法は使えるでしょうし、うまくパラメータチューニングすれば
既存のものより圧倒的にパフォーマンスが出そうです。


強い囲碁AI出現に動揺している記事も見ましたが、そもそもAlphaGoが最初に参考にしたのは人間の指し手でした。
AlphaGoの強さが人間に裏打ちされているという事実は、囲碁の歴史3000年(だっけ?)を誇って良いと思います。
また、AlphaGoの研究で囲碁界にも飛躍的な発展があるんじゃないでしょうかね。
まあ、動かすのに相当リソースを食うみたいですけどね(1202CPU, 176GPU)。

*1:本来ならp_\sigma ではなく強化学習版のp_\rhoの方が強そうなものですが、 最終的にここはp_\sigma の方が強いのだそうです。 論文ではpresumablyとしながらも、人間の打ち手に近いp_\sigmaの方が、 手の広い指し方をしているからではないか、と指摘されています。