TIM Labs
 数理最適化の実践ガイド-600.jpg
数理最適化の実践ガイド

著者  穴井 宏和

発行  2013年3月1日

サイズ  A5, 150頁  

ISBN  978-4-06-156510-4

価格  2,800(本体)  

本書は、以前紹介した『今日から使える!組合せ最適化』(以下前書と書く)の姉妹書である。
内容的には、前書が最適化の入門の入門書で、本書がその続きのような内容になっている。
しかし、発行日を見ると、本書が先に出され、後からよりわかりやすい入門の入門が出されたようである。

本書も前書同様にかなり薄い本である。

内容的には、最適化について離散最適化を除き、連続最適化に限っている。
内容は2部にわかれていて、前半は最適化全般の話である。
ただし、このページ数であるので、証明とか、詳しい説明については、巻末に参考書のリストがあり、より詳しく知りたい場合に読むと良い本が紹介されている。
要するに、きちんと知りたければ、別の本を読むべきである。

後半は、個々のアルゴリズムの紹介である。
多目的最適化の章があり、いくつかの具体的なアルゴリズムの概略が示されているのは、これだけ薄い本では珍しいことではないかと思う。
具体的なアルゴリズムの紹介に入ってから、手順の紹介だけに終わることが多くなり、最適化がうまく行く根拠の説明などがどんどん省略され、参考文献の紹介に終わることが多い。

ということで、本書を読むと、実際にどんなアルゴリズムが使われるかの概要が分かるようになる。
でも、実際に使おうと思ったら、相当情報が足りないので、巻末に紹介されている本を読み、しっかりと理解する必要がある。

なので、まさに「実践のガイド」であった。
今まで、2点間の距離は整数としてきたが、2点間の距離を有理数でも良いことにしよう。
全ての2点間の距離が有理数であれば、全ての距離の分母の最小公倍数を掛けてしまえば、全ての2点間の距離を整数にできる。
ということで、「任意の2点間の距離が整数」でも「任意の2点間の距離が有理数」でも同じことである。
intpolygon8.png
そこで、円をどんどん大きくしていくことを中止しよう。
つまり、円の大きさを一度決めたら、固定しても良いのだ。

まず、右図のように、3:4:5 の直角三角形が2つ、長さ3の辺でつながったものを考えてみよう。

すると、辺の長さが 5:5:8 の二等辺三角形ができ、この三角形に外接する円を考える。
また、各頂点を図のように P1、P2、P3 とする。
つまり、P1ーP2 、P2ーP3 の距離は5である。
今回は、この距離5に注目する。


intpolygon9.png

今までは、2点間の距離が整数にこだわっていたのだが、円の大きさをこのままにして、P3から距離5の頂点をP4とする。

すると、P1 P2 P3 P4 で決まる四角形(台形)ができる。
このとき、 d4 = P1ーP4の距離はいくらになるであろうか。

トレミーの定理.jpg ここで突然だが、「トレミーの定理」を使う。 円周に内接する四角形に関する定理で、辺と対角線の長さに関する等式
 
  AC・BD = AD・BC + AB・DC

が成り立つ。(トレミーの定理/Wikipedia)

これを使うと、

 8*8 = 5*5 + 5*d4
 d4 = 39 / 5

となり、d4は有理数である。
まだ3点が円周上にある場合しか求まっていなかった。intpolygon5.png
まず、3点から4点に1点だけ増やすことを考えよう。

右図のように、y軸を中心に反転した3:4:5の三角形を考えてみよう。
つまり、(-7, 24)を追加してみよう。

この点から既存の3点への距離は、30、40と14になる。
30、40の2つの距離は、図形がy軸で反転しただけであるので、以前から存在する距離でしかない。
新しく発生したのは、(-7,24)と(7,24)の距離であるが、y座標値は同じで14であることがすぐに分かる。

これで4点の場合が済んだ。
5点と6点の場合を考えよう。
intpolygon6.png3点から4点にしたとき、y軸に対称な位置に点を取った。

今度は、x軸に対象な位置に点をとってみよう。
すると、6点の場合が右図のようになる。

中央に幅14、高さ48の長方形が見えている。
この4頂点は円周上の点であり、対角線は円の直径になっているので、計算するまでもなく50である。

上下反転した位置にコピーすると頂点は2点増えた。
任意の2点間の距離で、新たな距離は上下の2頂点を結ぶものだけなので、48が増えただけである。

したがって、6頂点の場合は、右図に記入されている6つの座標値が求めるものである。

さあ、もっと頂点を増やしていこう。

まだまだ正月気分だと思うので、コンピュータやAI、高尚な数学はじっくり取り組むこととして、簡単な小中学生向けの問題に取り組んでみよう。
intpolygon3.png
【問題】

円周上に5点を取り、任意の2点間の距離が整数になる場合の5点の座標を求めよ。
ただし、1点は、半径をrとしたとき、 (r,0) とする。

5点が簡単と思った場合は、点数を増やそう。
たとえば、10点の場合を考えてみよう。

それもさっさとできたら、もっとたくさんの点の場合を考えよう。
そして、一般化してみよう。


ヒントは、「ピタゴラスの定理」である。intpolygon1.png
もし、5点ではなく、3点の場合には、3辺の長さが3, 4, 5 の正三角形を考えると良い。
長さ5の辺の端点の1つを(r,0)、つまり(2.5,0)とし、もう一方の端点を(-2.5)とすると、長さ5の辺は、半径2.5の円の直径となる。
そして、もう1つの頂点は、正三角形なのだから、当然円周上になる。
だから、このもう1点の座標を求めれば、3点の場合は決まる。

右の図は、5点の場合を求めるとても良いヒントになっている。
この図をいじっていると、それだけで5点、さらには6点の場合が自然に分かるだろう。

ということで、ぜひ手作業で、あるいはプログラムで解いてみよう。

さらに、もう少しヒントを追加しておこう。
新年明けましておめでとうございます。
今年は、さらにAIなどで大きな変化がありそうな年になるでしょう。
そのために、ますます新しい技術の習得が必要になるでしょう。
でも、色々なシステムを作るためのツール類が充実するだろうし、さらにハードウェアの性能も向上するので、より高度なこと、より複雑なことができるようになるでしょう。

AIに関しては、全脳シミュレーションがどうなるでしょうか?
ポスト京では、全脳シミュレーションを目標の1つに挙げているようですが、昨年末からいろいろあって、開発が順調に進むか微妙なところがあるようです。

さて、正月ですから、あまり社会のことを考えるのは休止し、年賀のために作成したナンプレを解いてください。

nenga2018-hard-np.png

ナンプレのルール

  1. 縦と横の各列9マスには、1?9の数字が1つずつ入ります。
  2. 3×3の太枠の中の9マスにも、1?9の数字が1つずつ入ります。
  3. したがって、縦、横、太枠内のいずれにも同じ数字は入りません。

本問題の難易度は、まあまあです。


この問題が難しいと思った場合には、次へ。


覆面算 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つのゲームが、同じアルゴリズム、同じプログラムで学習して強くなってしまったことだ。
大量の学習データがなくても、このようなゲームに関しては自己学習だけで最強になれることを示したのは大きい。

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

最近のコメント