読者です 読者をやめる 読者になる 読者になる

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の方が、 手の広い指し方をしているからではないか、と指摘されています。

Ubuntu14LTSにffmpegを入れてh264でエンコードする

動機

これを再現したかったgithub.com

問題

スクリプトの中でffmpegでもって動画を生成するのだが、Ubuntu14の標準リポにはもうffmpegがないみたい。

やり方

ソースからコンパイルしてインストールした。

$ git clone git://source.ffmpeg.org/ffmpeg.git ffmpeg
$ cd ffmpeg
$ ./configure --disable-yasm --enable-gpl --enable-libx264
$ make
$ sudo make install

解説

configure のオプション、 --disable-yasm はつけないとなんかエラーになったのでつけた。 --enable-gpl --enable-libx264 は、h264のコーデックを使うのに必要。
ffmpegのオプション類はここが参考になった。
CompilationGuide/Ubuntu – FFmpeg

klatexformula -- latexitのlinux alternative

普段macを使ってるのだが、mac環境にはあまりソフトウェアをインストールしないようにしている。
あまりメインの環境を汚したくない。再インストールも面倒だし。
latexや開発系のソフトは仮想マシンubuntuを入れて作業している。
これなら環境を破壊してしまっても仮想マシンを作りなおせば良いので楽である。

さて一方、プレゼン資料はmackeynoteで作っている。
ここで困るのは数式入力である。
mac で数式の画像を作るならlatexitだろ、と諸兄は思うだろうが、こいつは
maclatexをインストールしないとつかえないので、私の哲学に反する。
今まではtexclipというウェブサービスを使っていた。
TeXclip
これは非常にすばらしいサービスなのだが、なにぶんオンラインでないと使えないのと、
もしも向こうのサーバが落ちてしまったら使えないので不安が残る。
そこで、linuxで使える、latexitみたいなソフトがないかと探してみた。

klatexformulaというのがそれである。
software recommendation - LaTeXit alternative for ubuntu - Ask Ubuntu
しかし、普通にインストールしたところ、sqliteのDBが作れないなどと泣き言を言う。
以下のやりとりを参考にして、
#712019 - klatexformula: error message at startup - Debian Bug report logs

$ sudo apt-get install libqt4-sql-sqlite 

したところ、正常に動いてくれた。
依存関係はしっかりしておいて欲しいものである。

klatexformulaの使い勝手などは、もっと使い込んでから報告する。

gitのサーバを建てた

機械音痴なので今までコードはドロップボックス経由で同期していたのだが、
職場、自宅、持ち出しPCでもコードするようになってさすがに管理(コピペ)が面倒になったのでいい加減git覚えることにした。
遊んでいたサーバ(さくらのレン鯖)があったので、こいつをgitのサーバにする。
OSはubuntu 14LTS.

以下のURLを参考に、まずgit本体とデーモンを入れる。
server - Ubuntu上にgitサーバの構築 - Qiita

$ sudo apt-get install git
$ sudo apt-get install git-daemon-sysvinit
$ sudo apt-get install sysv-rc-conf

これで

$ sudo service gitdaemon start

すればデーモンさんが立ち上がるかと思いきやうんとも言わない。
不信に思って設定ファイルを見ると、

vim /etc/default/git-daemon
...
GIT_DAEMON_ENABLE=false

とかなってるので

GIT_DAEMON_ENABLE=true

に直したら動いた。
(ほんとはdefaultなんてディレクトリに入ってるから、こいつをどこかにコピーして書き換えるべきなのだろうが、実験なので気にしない)
また、同じファイルに

GIT_DAEMON_BASE_PATH=/var/lib
GIT_DAEMON_DIRECTORY=/var/lib/git

という項目があって、両方ともgitdaemonの所有物にしないといけないみたい。
とはいえ/var/libをgitdaemonさんのものにするわけにはいかないので、

GIT_DAEMON_BASE_PATH=/var/lib/git
GIT_DAEMON_DIRECTORY=/var/lib/git

として、/var/lib/gitにだけ所有権を与えた(このやり方が本当に良いのかは知らない。man読もう。)
しまたろうの備忘録 : ubuntu14.04lts32bitにgitをインストール


この作業ディレクトリ以下で、試しにリポジトリを作り、ローカルにクローンしてみる。

$ sudo mkdir hoge.git
$ sudo cd hoge.git
$ sudo git init --bare

実際はhoge.gitとそれ以下のファイルの所有権をgitdaemonに変更した。
んで、ローカルから

git clone git://REMOTEADDRESS/hoge.git

したのだが接続がタイムアウトしてしまう。
おかしいなぁと思ったらgitはポート9418を使うみたい。
ssh通信を行うから 22が空いていれば良いのかと思ったがそうではないのね。
リモートでポートを開ける

$ sudo ufw allow 9418

これでローカルにクローンできて、一応gitサーバはできたことになる。


次はローカルで作ったリポジトリをリモートに上げて、それに異なる環境からアクセスして共用する、というのをやる。
これはgithubの使い方みたいなのがネットにいっぱい転がってるしなんとかなると思う。

Bookscanの感想

要約

  • スキャンしたい本が、2,3冊ならOK
  • 10冊を超えるようなら1万払ってひと月プレミアム会員になることを検討すべき
  • そもそも競合他社のサービスと比較すべき

本文

今更bookscanを初めて利用したので書く。
1冊100円から(OCR込みだと200円で)本を電子化できるサービスの走りだ。
bookscanを選んだ理由は、単純に老舗でそれほど悪い評判も聞かないからである。
あと、iPadなどのデバイス個別向けのチューニングを無料でやってくれる部分にも惹かれた

私の場合、書籍を50冊ほどで、OCRのオプションをつけたので1冊あたり200円、
ざっくり1万円くらい費用がかかった。
引っ越しのたびにかさばる荷物がこの値段で圧縮できるなら安いもんである。

で、電子化された書籍pdfなのだが、これはブックスキャンのウェブからダウンロードできる。
まずこのダウンロードに期限があるようで、速やかに(3ヶ月以内らしい)ダウンロードしないといけないらしい。
ダウンロードできるpdfの名前はシリアルナンバーで、書籍のタイトルではない。
まあ、これは説明があって知ってたので良い。ちなみにpdf名をわかりやすく変えてくれるサービスは+100円/冊である。
また、ダウンロードページにサムネイルのような生易しいものはなく、完全に数字で書かれたリンクしかない。

さて、一つ目の問題は、この速やかにダウンロードしなければからないpdfファイルが一括でダウンロードできない点である。
リンクを一つ一つクリックしてダウンロードする必要がある。
1つのpdfは数十~百MBほど容量があり、ダウンロードするのも、開いて内容を確認し、
ファイル名を変更するのにも、私のしょぼいPCだとなかなか厄介である。

100MB近くあるpdfは実際上かなり扱いにくい(特にタブレット端末)ので、
チューニングを依頼したいのだが、ここでも一括選択はできないようである。
さらに言えば、ローカルに保存して、内容を確認し、ファイル名を変更して、
その本だけチューニングしてほしいと思った時、
ブックスキャンのウェブ上には変更する前のファイル名しか載っていないので、
どのファイルが依頼したい書籍なのかチェックするのはかなり面倒である。

面白い(皮肉ではなく)のは、これらの面倒事が、
決してブックスキャンのシステムがしょぼいから発生しているわけではない点である。
じっさい、ウェブだけ見てみても、軽いしよく出来てて、じゅうぶん投資して作ってるのが使っていてわかる。
そしてなんと言っても、プレミアム会員になると
これらの面倒な作業からまったく開放されるのが何よりの証拠だ。

つまり、書籍データは無期限でブックスキャンのウェブ上においておけるし、
無料でOCRもpdfの名前変更もやってくれるし、
書籍を一括で選択してダウンロードできるし、
同様に一括で選択してチューニングすることができる。

結局、bookscanのビジネスモデルは、いわゆるフリーミアムなのである。
1冊100円と安値で宣伝し、実際その価格でもスキャンはできるが、不便は大きい。
しかし、ひとたびプレミアム会員になれば、不便の解消が保証されている。
そして、ブックスキャンを金銭的に支えているのは、そのような不便から解消されたいプレミアム会員なのである。


プレミアム会員費1万円/月は、まあ、いきなり言われたら高いと思ってしまう金額だと思う。
しかし、お試しでサービスを使っているうちに、あ、これが解消されるならありかも、と思ってしまう。

ブックスキャンは、長続きしているスマホゲームと同じようなものである。
廉価な価格からサービスを利用できるが、そこには「廃課金」への魅力的な罠がたくさん仕掛けられている。

残念ながら私は、毎月50冊も本を買うような本の虫ではないので、今回はプレミアム入会を見送るが、
フリーミアム型のビジネスモデルが、スマホゲーム以外でも意外な場所で活用されてるのが知れて面白かったです。

プログラミング覚書

  • 最小要件で作れ

後の拡張性を~などと考えず、まずはミニマルに動くものを書く
動けばテストができ、テストができると足りないものが分かって次のステップが見える
言い換えると、コードを書いているうちに最終的な仕様が固まってくる
コードドリブンで仕様を決めるのは複数人数で大規模プログラミングするには良くないかもしれないが、
一人でプロトタイピングする分には良いだろう

クラス、関数などをエレガントに作るには仕様が固まってないといけないが、
仕様を固めつつコードするぶんには雑になってしまう。
これは仕方ないので諦めるべき


最近無駄に時間を食った気がしたので

Ubuntuでグラフィクドライバ入れなおしたらスプラッシュスクリーンから進まなくなった

cuda使いたくて、ゲーミングノートにubuntu入れたあと、グラフィクドライバをアンインストールして最新のに入れ替えて再起動したらスプラッシュスクリーンから進まなくなった。
一応画面は写ってるわけで、まったくGPUを認識できないわけではない。
困ってググったらドンピシャの回答発見

askubuntu.com

grubに解像度を教えてあげれば良いみたい。
hwinfoは14.04LTSのリポには入ってないようなので、xrandrで解像度を調べる。

ubuntuforums.org

$ xrandr

解像度がわかったら、grubの設定を書き換え

sudo vim /etc/default/grub
行追加
GRUB_GFXPAYLOAD_LINUX=1024x768 <--対応してる解像度を入れる

最後におまじない

echo FRAMEBUFFER=y | sudo tee /etc/initramfs-tools/conf.d/splash
sudo update-grub2
sudo update-initramfs -u