TIM Labs

2017年12月アーカイブ

覆面算 SEND + MORE = MONEY を解くsugarプログラムを、いきなりだが見てみよう。

sendmoremoney.csp
; S E N D + M O R E = M O N E Y
(domain range 0 9)
(int S range)
(int E range)
(int N range)
(int D range)
(int M range)
(int O range)
(int R range)
(int Y range)
(!= S 0)
(!= M 0)
(alldifferent S E N D M O R Y)
(= 
  (+ (+ (* (+ (* (+ (* S 10) E) 10) N) 10) D)
     (+ (* (+ (* (+ (* M 10) O) 10) R) 10) E))
  (+ (* (+ (* (+ (* (+ (* M 10) O) 10) N) 10) E) 10) Y))
これだけで、覆面算をやってくれる。 これだけ見ると括弧だらけで、まるでLispみたいだと思うだろう。
とりあえず走らせてみて、どうなるか考えよう。
sugarの次に、sugarファイルを書くだけだ。
$ sugar sendmoremoney.csp 
s SATISFIABLE
a S	9
a E	5
a N	6
a D	7
a M	1
a O	0
a R	8
a Y	2
a
SATISFIABLEと出ているので、解が存在したことを知らせており、その後ろに書く変数の名前と値がペアになって表示されている。
もし解が存在しないと、UNSATISFIABLEと表示され、変数の値は示されない。
なお、解があったからといって、唯一解である保証はない。

この簡単なプログラムは説明不要と思うが、以下に説明を試みる。

制約充足問題(Constraint satisfaction problem, CSP)というのをご存知だろうか?
まったく文字通りの意味で、たくさんの制約が与えられて、それらの制約を全部充たす(充足する)解を求める問題だ。
まず、Wikipediaへのリンク(制約充足問題)を示しておく。

制約は、要請、必須条件とか、ルールという言葉に置き換えても良い。
言葉で説明しているだけだと難しいが、実例があればわかりやすいので、1つ例をあげる。

   S E N D
 + M O R E
------------------
  M O N E Y

文字には0〜9の数字を入れます。
同じ文字には同じ数字、異なる文字には異なる数字を入れます。
また、最上位桁の文字には、0は入りません。
例は覆面算であり、色々な制約(といっても小学生でも説明不要なような制約なんだが)があって、それらを全て満足するように文字に数字を当てはめる。

各英大文字には、0〜9の数字が入る。
同じ英大文字は同じ数字になり、異なる英大文字は異なる数字となる。
最上位桁の数字は0にはならない。
さて、これをどうやって解こうか。
条件をいちいち調べれば解けるはずだが、そんな面倒なことをプログラマがやるようではまずい。プログラマたるもの、横着でなければいけない。 と
いうことで、条件だけ書けば解いてくれる便利なプログラムはないものかと以前探した時に見つけてつかったことがあるのが、sugarというものだ。
昔使っていたのだが、最近また制約充足問題関連の話があって、使おうとしたら、パソコンから消滅していた。
 ということで、まずはインストールだ。

 神戸大学の田村先生が用意してくれている Sugar: a SAT-based Constraint Solverに説明があるので、この通にやればインストールできる。
実際にインストールしてみるには、SATソルバーMiniSatとSugarを導入の方が分かりやすい。
日本語だし。

sugarの実行ファイルはperlになっていて、その先頭部分をインストールした環境に合わせるようになっている。
インストールしたものは、以下のように変更した。
SATソルバーは色々世の中というか、世界には転がっているのだが、前回も使ったminisatを使うことにしたので、もちろんこれもインストールしておかないといけない。
 
my $version = "v2-3-2";
my $java = "java";
my $jar = "/usr/local/lib/sugar/sugar-$version.jar";
## my $solver0 = "glucose";
my $solver0 = "/usr/local/bin/minisat";
my $solver0_inc = "minisat-inc";
my $tmp = "/tmp/sugar$$";
インストールが済んだら、とりあえず動かしてみよう。
sugarをインストールしたとき、/example/ の下にsugarのサンプルコードが入っている。
拡張子は .csp である。

examples$ sugar nqueens-8.csp
s SATISFIABLE
a q_1	4
a q_2	2
a q_3	8
a q_4	6
a q_5	1
a q_6	3
a q_7	5
a q_8	7
a
これは8クィーンで、8x8のチェス盤上に、どのクィーンも他のクィーンに取られない(利き筋にない)ように置く配置を求める問題である。 答えは、各列の何マス目に置けば良いかを示している。
sugarのプログラムnqueens-8.cspは以下であるが、説明は略す。
; 8-Queens Problem
(int q_1 1 8)
(int q_2 1 8)
(int q_3 1 8)
(int q_4 1 8)
(int q_5 1 8)
(int q_6 1 8)
(int q_7 1 8)
(int q_8 1 8)
(alldifferent q_1 q_2 q_3 q_4 q_5 q_6 q_7 q_8)
(alldifferent (+ q_1 1) (+ q_2 2) (+ q_3 3) (+ q_4 4) (+ q_5 5) (+ q_6 6) (+ q_7 7) (+ q_8 8))
(alldifferent (- q_1 1) (- q_2 2) (- q_3 3) (- q_4 4) (- q_5 5) (- q_6 6) (- q_7 7) (- q_8 8))
; END
あ、長くなったので、SEND+MORE=MONEYを解くsugarのプログラムは次回に説明しよう。
Chainerで学ぶディープラーニング入門
DEEP LEARING WITH Chainer

Chainerで学ぶディープラーニング入門


B5変形判/208ページ


定価(本体2,760円+税)


ISBN 978-4-7741-9186-7


Chainerの本が出ると、とりあえず入手するようにしている。

Chainerは日本初のDeep Learningフレームワークで、これで書くと短くなるし分かりやすい。そして、プログラムの柔軟性も高い。

ということで、応援しているのだが、なかなか本が出ないのだ。


本書は、Chainer の勉強と、Deep Learning の勉強が同時にできる入門書という雰囲気である。

しかし、どうも不思議な構成になっており、入門書という作りになっていない。


個々の技術解説は、それなりにページを割いているわけなのだが、そこからプログラミングへの繋がりがどうにも悪いのだ。

プログラムの解説は、メソッド単位とかで、かなり細かい単位にいきなり入ってしまう。

つまり、プログラムの全体像がないまま、いきなり詳細に入ってしまうのだ。

これでは、初心者は ??? となってしまうしかないのではなかろうか。


要するに、本書は、ディープラーニングの部品の説明で終わっている。


本書は、ちょっと見ると300頁くらいありそうな厚さがあるのだが、実際は200頁で、紙がかなり厚い。

個別技術については説明が詳しいところもあるのだが、全体を貫くような説明がされていないのが残念だ。

ページ数の制約や、出版を急ぐ必要でもあったのだろうか?


本書で使用されているソースコードは、GitHubに存在する。

https://github.com/ghmagazine/chainerbook

ソースコードとメモはあるが、解説がある訳ではない。


はやり、期待が大き過ぎたかな。

しかし、しっかりした本が出るかどうかは、普及に大いに影響しよう。


組合せ最適化-600.jpg
今日から使える!

組合せ最適化

離散問題ガイドブック

著者  穴井 宏和、斉藤 努

発行  2015年6月22日

サイズ  A5, 142頁  

ISBN  978-4-06-156544-9

価格  2,800(本体)  



組み合わせ数学、組み合わせ爆発、離散数学という言葉を聞いたことがあるだろうか。
最近は、ディープラーニング、機械学習という言葉がやたらに流行っていて、これこそが人工知能と思われていたりするようだ。

しかし、人工知能とは、そんなに狭くはない。ディープラーニング、機械学習などが人工知能であることには違いないが、それ以外にも人工知能はいっぱい存在する。
そもそも、何とか学習とかいうものは、十分な量の学習データが存在するとき機能するのだが、そもそもデータなどないけれど賢い解決方法はないか、何とかしたいという事柄、問題はいっぱいあって、それらも当然人工知能と呼ぶべきだ。

高校数学でも順列・組合せが今もあるのだろうか。
問題だけ見ると、なんだか問題のための問題、パズルと感じるものの、社会で必要としている数学と思われていないような気がする。
組み合わせ的な作業というのは、とても面倒で、人手でするのは大変なものが多い。
たとえば、

訪問先がたくさんあった場合、どの順番で回ってくるのが効率が良いか。(巡回セールスマン問題)
試合の対戦はどのように組み合わせると、より公平になるか。
倉庫や工場はどこに配置すればよいか。
服を作るのに布をどう裁断すれば無駄が減るか。
結婚のペアは、どの組み合わせが一番トラブルが減るか。(安定結婚問題)
水道管網、電力網は、どのようにすればよいか。
列車、飛行機、貨物船、、、、の運航スケジュール。
コンテナ船の積み下ろし。
学校の時間割をもっと簡単に作れないものか。
スタッフのスケジュールも同じだ。
。。。。。。


1997年にチェスで、Deep Blueがカスパロフを破った。
それから20年が経った。
去年あたりから、将棋や囲碁も、人間よりプログラムの方が強いと認識されるようになった。
そして、2017年12月5日に、同じアルゴリズムで、チェス、将棋、囲碁がプレイできるものができたと。

いつものように、DeepMind社からの発表である。
すでに、学習用の大量のデータを用意しなくても、学習だけで強くなるプログラムは発表されていて、たった数日でプロに圧勝したAlphaGoよりも強い AlphaGo Zero が発表されている。

今回の発表は、チェスも、将棋も、囲碁も、それぞれのゲームのルールなどを用意するだけで、同じアルゴリズムで(たぶん同じプログラムでかつ同じハードで)ゼロから学習して強くなってしまうことに成功したようだ。
次のグラフは学習曲線を示している。(以下の論文より引用)

AlphaZero_LearningGraph.png
チェスや将棋は数時間の学習で世界最強になり、囲碁でも数日で十分なのである。

これについて紹介している論文がこれだ。
細かい理論や技術について書いているわけではなく、概要がざっと書いていて、最後にチェスの棋譜も載っている。
チェスの棋譜については、論文で見るより、ネットで動画になったもの、さらに解説までついたものがいっぱいあるので、そちらを見た方がよいだろう。
たとえば、YouTubeにこんなのがある。Stockfishというのは、最強のチェスプログラム(だった)。

今回の AlphaZero ではなく、AlphaGo Zero についての、楽しく分かりやすい説明がある。まあ、英語だが、このくらいは大丈夫かも。

論文の内容の解説はネットにいっぱい出ているようなので、ここでは省略する。

それより、全然違う3つのゲームが、同じアルゴリズム、同じプログラムで学習して強くなってしまったことだ。
大量の学習データがなくても、このようなゲームに関しては自己学習だけで最強になれることを示したのは大きい。

つまり、二人零和有限確定完全情報ゲームは、同じプログラムで学習だけで強くなってしまうことができるのだろうか?
ここまでできると、汎用人工知能に一歩前進は間違いないだろう。

深層学習による自然言語処理.jpg
機械学習プロフェショナルシリーズ

深層学習による自然言語処理

著者  坪井裕太、海野裕也、鈴木潤

出版社 講談社

発売日 2017/5/25

サイズ A5, 239頁

ISBN-13: 978-4061529243

定価  3000円(本体)

深層学習の本というと、やたらに画像処理の本が多いのだが、深層学習の対象は相当広く、自然言語処理にも及んでいるのだが、なぜか本が少ない。
そう思いながら、「深層学習+自然言語処理」という条件で探していて見つけたのがこの本だ。
というのとで、そもそも本自体がまだ少ない分野なので、中身をほとんど確認せずに入手してしまった。

印象を手短にまとめると、最近の技術動向、研究紹介も多く、今現在の深層学習による自然言語処理の状況を概観するにはとても良い本であった。
しかし、技術を身に着けたり、勉強しようという場合には、なかなか大変な本である。
まず、深層学習、自然言語処理などについて、ある程度の知識があることが前提になっているし、また1冊200頁程度で多数のことを紹介しようとしているので、丁寧な解説には全然なっていないのは紙面の制約でどうにもならないだろう。

数式も結構出てくるのだが、とりあえずこの分野の状況が知りたかっただけなので、大部分の式は飛ばして読んだ。
きちんと数式も説明の図も理解するには、かなり高いレベルの基礎知識が必要である。

深層学習+自然言語処理 は、ここ数年で急に立ち上がった分野で、まだまだ問題だらけ、つまり研究分野としても若い分野でやることがいっぱいあるという感じである。
しかし、言語処理は、そもそもデータを用意するのが大変だし、さらに結果が良いのか悪いのかの判定もあいまいな部分があり、画像処理などと比べると、とてもぼやっとしていると感じた。

このアーカイブについて

このページには、2017年12月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2017年11月です。

次のアーカイブは2018年1月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。