遺伝的プログラミングの続き
2週間前に書いてた遺伝的プログラミングの続き。前は、構文木を構成するクラスとしてParamLeaf, ConstLeaf, EvalNodeを定義した。
書いたコード
前のコードにもdisplayメソッドとか付け加えた。後、rubyのオブジェクトはデフォルトではdeepcopyが出来ないので、childrenを持つEvalNodeにはinitialize_copyメソッドを持たせてdeepcopy時にchildのcopyを持たせる処理を書いた。
とりあえず、これがTreeのNode。
1 module GeneticProgramming 2 class Node 3 def display(indent = 0) 4 print "\s" * indent 5 end 6 end 7 8 class ParamLeaf < Node 9 def initialize(index) 10 @index = index 11 end 12 13 def eval(*params) 14 params[@index] 15 end 16 17 def display(indent = 0) 18 super(indent) 19 print "param#{@index}\n" 20 end 21 end 22 23 class ConstLeaf < Node 24 def initialize(const) 25 @const = const 26 end 27 28 def eval(*params) 29 @const 30 end 31 32 def display(indent = 0) 33 super(indent) 34 print "#{@const}\n" 35 end 36 end 37 38 class EvalNode < Node 39 def initialize(func_wrapper, *children) 40 @func_wrapper = func_wrapper 41 @children = children 42 end 43 44 def initialize_copy(obj) 45 @children = obj.children.map { |child| child.dup } 46 end 47 48 attr_accessor :children 49 50 def eval(*params) 51 results = @children.map { |e| e.eval(*params) } 52 @func_wrapper.call(*results) 53 end 54 55 def display(indent = 0) 56 super(indent) 57 print "#{name}\n" 58 @children.each { |child| child.display(indent + 1) } 59 end 60 61 def name 62 @func_wrapper.class.method_defined?(:name) ? @func_wrapper.name : 'no name' 63 end 64 end 65 end
EvalNodeにはprocオブジェクトを渡せるけど、display時に名前とか表示する為にFuncWrapperクラスを作った。後、FuncWrapperオブジェクトとして実際に使用するものを事前にまとめてFuncList moduleにした。
1 module GeneticProgramming 2 module FuncList 3 class FuncWrapper 4 def initialize(func_proc, name, arity = nil) 5 @proc = func_proc 6 @name = name 7 @arity = arity || func_proc.arity 8 end 9 10 attr_reader :name, :arity 11 12 def call(*args) 13 @proc.call(*args) 14 end 15 end 16 17 All = { 18 add: FuncWrapper.new(:+.to_proc, 'add', 2), 19 sub: FuncWrapper.new(:-.to_proc, 'sub', 2), 20 mul: FuncWrapper.new(:*.to_proc, 'mul', 2), 21 if: FuncWrapper.new(lambda { |pred, cons, alter| (pred > 0) ? cons : alter }, 'if', 3), 22 greater: FuncWrapper.new(lambda { |left, right| (left > right) ? 1 : 0 }, '>', 2) 23 } 24 25 def self.[](method_name) 26 All[method_name] 27 end 28 end 29 end
arityメソッドは引数の数を返すメソッドで、+とか*みたいな任意の数をとれるやつは任意の数をとれる形にしようかとも思ったけど、面倒だったのでとりあえず二引数扱いにしてる。FuncList::Allにこちらで事前に生成したFuncWrapperオブジェクトが入れてある。
それから、遺伝的プログラミングで問題を解くSolverクラスを作った。
1 require_relative './func_list' 2 require_relative './node' 3 4 module GeneticProgramming 5 class Solver 6 def initialize(score_obj, max_gen = 500, mutate_rate = 0.1, crossover_rate = 0.1, p_exp = 0.7, p_new = 0.5) 7 @score_obj = score_obj 8 @max_gen = max_gen 9 @mutate_rate = mutate_rate 10 @crossover_rate = crossover_rate 11 @p_exp = p_exp 12 @p_new = p_new 13 end 14 15 def select_index 16 Math.log(Math.log(rand) / Math.log(@p_exp)).to_i 17 end 18 19 def evolve(param_size, pop_size) 20 population = Array.new(pop_size) { |i| make_random_tree(param_size) } 21 scores = [] 22 @max_gen.times do |count| 23 scores = rank_func(population) 24 p scores[0][0] 25 break if scores[0][0] == 0 26 27 population[0] = scores[0][1] 28 population[1] = scores[1][1] 29 (2..pop_size).each do |i| 30 if rand > @p_new 31 tree1 = scores[select_index][1] 32 tree2 = scores[select_index][1] 33 population[i] = mutate(crossover(tree1, tree2, @crossover_rate), param_size, @mutate_rate) 34 else 35 population[i] = make_random_tree(param_size) 36 end 37 end 38 end 39 scores[0][1].display 40 scores[0][1] 41 end 42 43 def rank_func(population) 44 population.map { |tree| [@score_obj.get_score(tree), tree] }.sort_by { |score, tree| score } 45 end 46 47 def make_random_tree(param_size, max_depth = 4, f_prob = 0.5, p_prob = 0.6) 48 if rand < f_prob && max_depth > 0 49 func = FuncList::All.values.sample 50 childs = Array.new(func.arity) { |i| make_random_tree(param_size, max_depth - 1, f_prob, p_prob) } 51 EvalNode.new(func, *childs) 52 elsif rand < p_prob 53 ParamLeaf.new(rand(param_size)) 54 else 55 ConstLeaf.new(rand(10)) 56 end 57 end 58 59 def mutate(tree, param_size, change_prob = 0.1) 60 if rand < change_prob 61 make_random_tree(param_size) 62 else 63 result = tree.dup 64 if tree.class.method_defined?(:children) 65 result.children = tree.children.map { |child| mutate(child, param_size, change_prob) } 66 end 67 result 68 end 69 end 70 71 def crossover(tree1, tree2, swap_prob = 0.7, top = true) 72 if rand < swap_prob && !top 73 tree2.dup 74 else 75 result = tree1.dup 76 if tree1.class.method_defined?(:children) && tree2.class.method_defined?(:children) 77 result.children = tree1.children.map { |child| crossover(child, tree2.children.sample, swap_prob, false) } 78 end 79 result 80 end 81 end 82 end 83 end
これは、
solver = GenericProgramming::Solver.new(score_obj) solver.evolve(2, 500)
みたいな感じで使う。treeを引数としてとるget_obj(tree)メソッドを持つscore_objを渡してinitializeすると、そのscoreを遺伝的プログラミングで改善していって、最終的にscrore:0を返す様なtreeを表示してくれる。
score_objとしては、今回はこちらで用意した関数に対してrandomeに引数与えてデータセットを作って、そのデータセットとのズレの総和をscoreとして返す様なものを作った。
1 require_relative './solve' 2 3 class TestSet 4 def initialize(hidden_proc) 5 @hidden_proc = hidden_proc 6 @test_set = build_test_set 7 end 8 9 def build_test_set 10 [*0..200].map do |i| 11 x = rand(40) 12 y = rand(40) 13 [x, y, @hidden_proc.call(x, y)] 14 end 15 end 16 17 def get_score(tree) 18 @test_set.map { |x, y, test_value| 19 (tree.eval(x, y) - test_value).abs 20 }.reduce(:+) 21 end 22 end 23 24 if __FILE__ == $0 25 test_set = TestSet.new(lambda { |x, y| x ** 2 + 3 * y }) 26 GeneticProgramming::Solver.new(test_set).evolve(2, 500) 27 end
26行目にあるように、こちらで与えた関数でtest_setオブジェクトを作ってる。get_scoreメソッドにtreeを渡してやると、そのtreeがどれだけ良いものになってるかがscoreとして返る。
実際の実行結果はこんな感じになった。最初の数字の並びはscoreの変化で、その後にtree.displayの結果を表示してる。
$ ruby test_set.rb 11018 5594 0 add mul sub if param0 param0 > param0 0 0 param0 add mul param1 if > param1 param1 > param0 param0 2 param1
複雑に見えるけど> param1 param1(必ず0が返る)みたいなバカみたいな事をやってるだけで、ちゃんとx ** 2 + 3 * yにはなってる。こういった自明な部分を 枝刈り してやると、もっと綺麗な解になるらしい。
所感
大体は集合知プログラミングにのってたコードをrubyに置き換えただけだったけど、ちゃんと動いて問題を解くのに使えて楽しかった。
ちょこちょこ心残りはあって、solverは書いてて途中で力つきちゃってevolveが雑な実装になってしまった(ほぼ写経になってしまった)から、後でもうちょいリファクタリングしときたい。「遺伝的プログラミング」に載ってた定義だと引数が多すぎてイラッとしたからinitializeとevolveに分けたけど、特にinitializeの必要は無かったかもしれない。
後、mutate(突然変異)やcrossover(交叉)はTreeのクラスにメソッドとして持たしても良かったかもしれないし、make_random_treeはSolverクラスに入れたけどGeneticProgrammingモジュールの直下にあっても良い気がした。
眠くて辛いので今日はここまで。
追記
所感で書いた点を書き直してgithubにあげた。
south37/genetic_programming · GitHub
param_sizeメソッドとscoreメソッドが定義されたオブジェクトを渡してGeneticProgramming::Solverをinitializeすると、そのscoreを最小化するようなプログラム(構文木)の発見を目指して遺伝的アルゴリズムで探索してくれる。
require './solve.rb' GeneticProgramming::Solver.new(score_obj).evolve(500) # 遺伝的アルゴリズム開始
何らかの学習用のデータセットがあるとして、それをラップする形でscore_objオブジェクトを定義してやれば一応は動くはず。引数の数は任意だけど、score_objはparam_sizeメソッドで引数の数を返さなければならない。
ちゃんと正しい結果を返してくれるのかのテスト用に、こちらで正解の関数を与える事でデータセットを、さらにはそれを元にscore_objを作ってくれるTestSetクラスも用意されてる。
今日は遺伝的プログラミングの話ではなく、ポエムを書く
実はこのブログは焼き肉ブログという名前の「はてなブロググループ」に属してて、毎日順番にブログを書いてく取り決めをしていたりする。で、今グループを作ってからちょうど1年が経ったみたいで、振り返りをしようという流れがやってきている。
乗るしかない このビッグウェーブに！
って事で、振り返る。
4月にも振り返りっぽい事してた
ってことで、4月から今日までの6ヶ月について考えてみる。
といってもあんま大したことしてなくて、変わらず本読んでそれについてブログ書いてた。
ただ、最近はただ情報をまとめるだけじゃ良く無いなと思って、自分の体験や考えた事なんかを積極的に残す様にしてた。Web上にあんま落ちてない情報をまとめるならそこそこ価値はあるけど、多くの人が既にブログに書いてる様な事をほとんどコピペみたいな事しても情報としてそんなに価値は無くて、じゃあどうしたらいいかって言うとやっぱり自分の意見とか体験とかを残した方が良いのかなと思った。
エンジニアのブログとか読んでて一番価値を感じるのは「試行錯誤して問題解決した結果を分かり易くまとめてくれてる事」だったりするんだけど、業務とかしてなくてあんまり問題解決の知見を貯めたりは出来ないので、せめてインプットの際に考えた事なんかを残したい。
ちょっと困ってる事
ブログ書くとけっこう時間とられて一度にあんまり量書けないんだけど、技術書を読む事は隙間時間さえあれば四六時中やれちゃうので、結果としてアウトプットがインプットに追いついてない形になってる。まあ、学んだ事全てを書き残す必要は無いのかもしれないけど、このへんもうちょい上手くやれると良い。
あと、最近は昔から名著って呼ばれてるような本をちゃんと読みたいなと思ってるんだけど、「オブジェクト指向入門」とか「リファクタリング」とか大抵むっちゃ高いので、買えない。早くお金を稼ぎたい。
やりたい事
もっとポエムを書きたい。
自分はけっこうエンジニアブログとか読むの好きで、オブジェクト指向がどうとか関数型がどうとか盛り上がってるのを見ていろいろ自分で考えたりして楽しんでるんだけど、そこで考えた事とかを書き残しても良いんだと思う。
特に、僕はグレアムのポエム(エッセイとも言う)にかなり影響を受けている口なので、そういったWebポエムの影響力は理解してるつもりだし、そういった影響力のある存在には憧れる。
あとエンジニアリング以外のトピックについてもいろいろ考えてて、「リーダーの資質とは」とか「努力について」とか「環境が行動を左右する」とかそのへんについては、いつか考えてる事を書きたい。
時代はポエムなのかもしれない。
学びたい事
自分が乗っかってるものの事をもっとちゃんと理解したい。特に最近は、Unixとか計算機の低レイヤーの仕組みとか由緒正しきオブジェクト指向の考え方とかについてちゃんと学ぼうと思ってる。ちょろちょろとは勉強してるけど、まだまだ全然詳しくはなれてない。理解を深めて行きたい。
心がけてる事
自戒をこめてなんだけど、自分が今手にしてるものを過大評価し過ぎちゃダメだと思ってる。例えば、自分は言語としてはRubyが好きでWAFとしてはRuby on Railsが大好きなんだけど、これらが最もクールで他は全部クソみたいな事は絶対言っちゃいけないと思ってる。
特に、新しい言語やライブラリ、フレームワーク、ツールなんかが生まれ続けてる現状の中で、自分が今知っている知識を不当に評価するあまり新しいものを頭ごなしに否定するようではいけないと思う。人は心理的に自分の行動を正当化するバイアスが働くらしく、特定の技術にお金や時間を費やす程それを高く評価してしまう。これは「酸っぱいブドウ」とかと同じ話で、「認知的不協和」として知られている。
こういった事は頭に入れておいて、理性でバイアスを抑えつける様にしたい。
ちなみに、「認知的不協和」とかの話は「Hooked ハマるしかけ」に載ってた。けっこう面白かったので、良い本だと思う。
まとめ
振り返りは一瞬で終えて、ほぼポエムを書いてしまった。やはり時代はポエムなのかもしれない。
遺伝的プログラミングを学ぶ
積読されてた「集合知プログラミング」を引っ張りだして読んだ。面白そうなとこから読んでたからまだちょこちょこ抜けはあるけど、機械学習のいろんな手法を分かり易く説明してくれてて楽しく読めた。 その中でも、遺伝的プログラミングの考え方が特に面白く感じた。
遺伝的プログラミングとは?
機械学習によって「プログラム」を構築する手法。ランダムに作られたプログラムの中から、良いものを選んで「突然変異」させたり「交配」させたりしながら進化させていく。
最適化手法の一つである「遺伝アルゴリズム」を「プログラム」自体に適用したものとも言えて、「プログラム」を生成するプログラムを考えようっていうメタな感じが面白い。
実際どうやんの?
ランダムに「プログラム」を作ろうって時、原理的には適当に作った文字列をevalするとかでも良いんだろうけど、そういった方法ではちゃんと動くコードになる確率は限りなく小さい。そこで、通常は「構文木」に着目する。
「構文木」というのは再帰的に評価可能なツリー構造の事で、例えば通常のプログラミング言語においてはコンパイルの際にコードはいったん構文解析によって「構文木」(より正確には抽象構文木)に変換され、その後で実行可能なバイナリの生成が行われる。
このページの図11みたいなイメージを持ってもらえればOK。
この構文木を「遺伝アルゴリズム」で進化させていこうというのが、遺伝的プログラミング。
構文木を作ってみる
より正しくは構文木と一対一で対応する様なツリー構造を、オブジェクトとして表現してみる。
まず、ツリーを構成するノード(および末端のリーフ)として、パラメータに対応するParamLeaf、定数に対応するConstLeaf、そして子ノードに対して適用されて値を返すEvalNodeの3種類を考える。特に、EvalNodeは関数の場合もあればifのような制御構造の場合もある事に注意する。
例えば、rubyでは次の様にParamLeafクラス, ConstLeafクラス, EvalNodeクラスを定義出来る。
1 class ParamLeaf 2 def initialize(index) 3 @index = index 4 end 5 6 def eval(*params) 7 params[@index] 8 end 9 end 10 11 class ConstLeaf 12 def initialize(const) 13 @const = const 14 end 15 16 def eval(*params) 17 @const 18 end 19 end 20 21 class EvalNode 22 def initialize(eval_ploc, *children) 23 @eval_ploc = eval_ploc 24 @children = children 25 end 26 27 def eval(*params) 28 results = @children.map { |e| e.eval(*params) } 29 @eval_ploc.call(*results) 30 end 31 end
これで、例えば次の様にツリー構造を作って、それをevalする事が出来るようになった。
[1] pry(main)> tree = EvalNode.new(lambda { |a, b| a + b }, ConstLeaf.new(1), ConstLeaf.new(2)) => #<EvalNode:0x007fe7f04a4360 @children=[#<ConstLeaf:0x007fe7f04a43b0 @const=1>, #<ConstLeaf:0x007fe7f04a4388 @const=2>], @eval_ploc=#<Proc:0x007fe7f04a43d8@(pry):17 (lambda)>> [2] pry(main)> tree.eval => 3
上記の例では、「1 + 2」というコードに対応する構文木を作った事になる。一部をパーツとして取り替え可能な「データ構造」の形でプログラムを表現した事で、遺伝的アルゴリズムが適用出来る様になった。
ちなみにどうでも良い話だけど、単純な演算ならlambda式では無くsymbolのto_procメソッド使うとちょっとオシャレになる。
tree = EvalNode.new(:+.to_proc, ConstLeaf.new(1), ConstLeaf.new(2))
時間が無くなった
めちゃくちゃ中途半端だけど時間が無くなったので、今日はここまで。続きとしては、構文木を「交配」させたり「突然変異」させたりする方法を定義して、実際に「遺伝的プログラミング」を試してみる予定。
TCP/IPをマスタリングしたい
最近、ネットワークの事ちゃんと理解したいなーと思って、積読されてた「マスタリングTCP/IP」という本を読んでみた。TCP/IPを言いつつそれより下のレイヤーのイーサネットとか上のレイヤーのSMTPとかHTTPとかまで解説してくれてるので、親切な本だと思う。いろんなとこでオススメされてるし、良さげ。
とりあえず、内容をざっくりとまとめてみる。
ネットワークの階層構造
僕らは普段当然の様にネットワークを利用して様々な情報をやり取りしてる訳だけど、実はその背後には様々な複雑な仕組みがある。 例えば、僕らが最も頻繁に行うであろう「ブラウザを使用してのWebブラウジング」を考えてみても、HTTPのリクエストを送る為にまずTCPのコネクションを張る必要があって、TCPのコネクションを張る為にIPアドレスで宛先指定する必要があって、IPでパケット送るには物理層(LANケーブルとか光ファイバーとか無線とか)で繋がっててかつMACアドレスが割り振られたネットワークインターフェースを持ってる必要があって、って感じで階層下された沢山の仕組みを使って通信を行う事になる。 URLからIPアドレスを取得するにしてもDNSサーバにUDPで通信する必要があって、UDPはやっぱりIPやそれより下位のレイヤーに依存する事になる。
こういった階層化は一見複雑に見えるけど、むしろ適切な抽象化をもたらして全体の理解を容易にしてくれる。関心事を分離してレイヤー毎に自分の仕事に専念させる事で、上位のレイヤーからは下位のレイヤーのプロトコルの詳細を知らなくてもその役割だけを理解してれば良い事になる。一度に考える事を減らせるので、複雑性を減らす事が出来る。とっても良い。
TCP/IPとOSI参照モデル
ネットワークの階層はよく「OSI参照モデル」で説明される。
の7つの層から構成されてるとか言うやつ。下に行く程上位になっている。
これらは実際の実装との対応付けを行う事が出来て、例えば1の物理層はLANケーブルや無線みたいな物理的な送信路(と電気や電磁波による信号をビットに直す仕組み)に対応してる。2のデータリンク層は同じLAN内にある機器(PCやルータ)同士の、MACアドレス(ネットワークインターフェースに個別に割り振られた番号)を用いた通信に対応してる。3のネットワーク層が多くの人によっておそらく一番馴染みが深いIPを用いた通信に対応してて、IPアドレスによる宛先の指定なんかはこのレイヤーが責任を持っている。4のトランスポート層はTCPやUDPに対応してて、何をする為の通信なのか(サーバーへのHTTPリクエストなのかSSH通信なのかFTPによるファイル転送なのか)を管理してる。5~7はアプリケーションプログラムの責任としてひとまとめにされる。
マスタリングTCP/IPでは、これらの各レイヤーについて説明がなされてた。特に、IP(というかIPアドレス)については何となく知っててもデータリンク層やトランスポート層については意識しないとあんま触れる機会は無いと思うので、勉強する良いきっかけになった。
それぞれのレイヤーの詳細な説明は、機会があればまた後日する。だいぶ短くなっちゃったけど眠いので許して欲しい。
Go言語触ってみた その3
今週も、Goを触ってみて気になった点とかについてまとめてみる。
先週の振り返り
先週はGoの型システムについてブログを書いた。新しい型を定義する際に、
- 既存の型に別名(?)をつける場合
- struct型を定義する場合
- interface型を定義する場合
の3通りの方法があると述べた。
今週は、先週ちょろっと触れながら詳しくは説明しなかったembedding typeについて触れる。
Go言語触ってみた その2
昨日は眠さに負けて寝ちゃったので、続きを書く。
Go言語の特徴的な点
印象に残った点を書いて行く。
Goはオブジェクト指向???
Goには、現代的なオブジェクト指向言語の大半に存在する「クラス」というものが存在しない。というか、今サラッと「オブジェクト指向言語」と書いたがそもそもGoがオブジェクト指向言語かどうかは微妙なところで、公式のFAQでも「Goはオブジェクト指向言語か？」という問いに対して「Yes and no.」と答えている。
参考: The Go Progrraming Frequently Asked Questions (FAQ)
続きを読む