[実験]アルゴリズム化学
抽象化学反応系、ルールダイナミクス
s/a/b/
s/b/c/
s/c/a/
この３つが、他のsedスクリプトを書き換えながら、増殖します。
オートポイエーシスにまでは到達してないけど、ハイパーサイクルには到達したかも。
（実行に当たってはパーミッションに注意）
- init.sh
#!/bin/bash
rm -f $(seq 0 153)
echo "s/a/b/" > ./0
echo "s/b/c/" > ./1
echo "s/c/a/" > ./2
for i in $(seq 3 52) ; do
echo "s/a/a/" > ./$i;
done
for i in $(seq 53 102) ; do
echo "s/b/b/" > ./$i
done
for i in $(seq 103 152) ; do
echo "s/c/c/" > ./$i
done
- reactor.sh
#!/bin/bash
for i in $(seq 1 100000); do
target=`expr $RANDOM % 150 + 3`
sed -f `expr $RANDOM % 153` ./$target > ./tmp
cp ./tmp ./$target
cat ./$target
done
試した結果
今回のような遺伝的プログラミングの応用は、かなり無理があると言わざるを得ないです。
今回の方法についていろいろ考えましたが、仮に学習用データを10与えて、それを再現できるプログラムが、遺伝的プログラミングの手法により実現できるか？というと、それはおそらく可能です。しかし、10データをまねできたとしても、11番目のデータは結局ランダムになり、それが学習用の10データを反映したものとはなりえないと言う結論になります。
やっぱり、自然言語処理は難しかったです。
(この分野へは、遺伝的プログラミングより強化学習の方が適しているかもしれません。)
学習用データ作成
【内部主要記事】
【本文】
ランダムなアルファベット小文字のリスト＝学習用データ 作成。
学習用データ作成に当たって使用した関数interpretはこの本を参考にしました。
- 作者: R.ケントディヴィグ,R.Kent Dybvig,村上雅章
- 出版社/メーカー: ピアソンエデュケーション
- 発売日: 2000/05
- メディア: 単行本
- 購入: 2人 クリック: 71回
- この商品を含むブログ (20件) を見る
以下、学習用データ作成プログラム
;; http://d.hatena.ne.jp/ufo23/20060802
(load "./random-tree.scm")
;; 書籍「プログラミング言語SCHEME」参照
;; ここでは、ランダムに作成されたプログラムを実行するのに使用
;; (applyやevalではうまくいかなかったため)
(load "./interpret.scm")
;; リストの平坦化
;; http://d.hatena.ne.jp/ufo23/20060812/1155376475
(define (flatten ls)
(cond ((null? ls) '())
((pair? ls)
(append (flatten (car ls)) (flatten (cdr ls))))
(else (list ls))))
;; 学習用データ作成
(define make-study-data
(lambda (data-num)
(let loop ((n 0) (sd '()))
(cond ((>= n data-num) sd)
(else (set! sd
(cons
(flatten
(interpret
(create-individual-program
allowable-depth
top-node-p
full-p)))
sd))
(loop (+ n 1) sd))))))実行(学習用データ作成)
gosh> (make-study-data 10)
結果(ランダムなので毎回異なる)
*1
<<<この部分を求める>>>
データは10回の対話モデルです。GPでこの10回の対話を再現できる個体を探し、11回目の<<<この部分を求める>>>のところを出力します。これを対話における返答とみなします。
次は、各個体がこのデータにどの程度適合するかをレーベンシュタイン距離を用いて求めます。
*1:#\d) (#\z #\f #\k #\s #\x #\i #\e #\n) (#\t) (#\l #\t #\v #\c #\v #\h #\w #\n #\t #\l #\x #\n #\v #\k #\p #\l #\k) (#\p #\r #\p #\y #\g #\g #\k #\m #\h) (#\j) (#\c #\f #\x #\v #\l #\k #\e #\p #\s) (#\s #\t #\l #\h #\d #\b #\y #\e #\w #\v #\n #\b #\v #\t #\v) (#\z) (#\h
レーベンシュタイン距離を求める
【内部主要記事】
【本文】
レーベンシュタイン距離を使って個体の適合度を求めます。
gaucheの配列に関する資料
http://www.shiro.dreamhost.com/scheme/gauche/man/gauche-refj_71.html
レーベンシュタイン距離に関する資料
http://ja.wikipedia.org/wiki/%E3%83%AC%E3%83%BC%E3%83%99%E3%83%B3%E3%82%B7%E3%83%A5%E3%82%BF%E3%82%A4%E3%83%B3%E8%B7%9D%E9%9B%A2
http://www-06.ibm.com/jp/developerworks/java/041217/j_j-jazzy.html#figure1
; 以下の2つのリストのレーベンシュタイン距離を求める (define str1 '(#\p #\z #\z #\e #\l)) (define str2 '(#\p #\u #\z #\z #\l #\e)) ; 解は 3 となる ; 補足：最終的な配列の状態 ; gosh> d ; #,(<array> (0 6 0 7) 0 1 2 3 4 5 6 ; 1 0 1 2 3 4 5 ; 2 1 1 1 2 3 4 ; 3 2 2 1 1 2 3 ; 4 3 3 2 2 2 2 ; 5 4 4 3 3 2 3)
【レーベンシュタイン距離を求めるコード】
ファイル loewenstein-distance.scm
; 配列を使えるようにする
(use gauche.array)
; テスト用リスト
; 文字のリスト文字列ではないが str1 str2 という表現で扱う
(define str1 '(#\p #\z #\z #\e #\l))
(define str2 '(#\p #\u #\z #\z #\l #\e))
(define loewenstein-distance
(lambda (str1 str2)
; length str1 + 1 行 length str2 + 1 列のテーブル d を用意する
(define d (make-array (shape 0 (+ (length str1) 1) 0 (+ (length str2) 1)) 0))
; #,(<array> (0 6 0 7) 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0
; 0 0 0 0 0 0 0)
; 配列dの初期化
; (do を使えば init1 と init2 に分ける必要はない。
; ループは再帰で行う方が望ましいと考え2つに分けたが
; こういう場合は下で定義してある calc-LD のように
; do でループしたほうがいいのだろうか？)
(define init1
(lambda (i1 len)
(cond ((> i1 len) d)
(else (array-set! d i1 0 i1) (init1 (+ i1 1) len)))))
(define init2
(lambda (i2 len)
(cond ((> i2 len) d)
(else (array-set! d 0 i2 i2) (init2 (+ i2 1) len)))))
;#,(<array> (0 6 0 7) 0 1 2 3 4 5 6
; 1 0 0 0 0 0 0
; 2 0 0 0 0 0 0
; 3 0 0 0 0 0 0
; 4 0 0 0 0 0 0
; 5 0 0 0 0 0 0)
; str1 と str2 のレーベンシュタイン距離を求める
(define calc-LD
(lambda ()
(let ((cost 0) (i1 1) (i2 2) (len1 (length str1)) (len2 (length str2)))
(do ((i1 1 (+ i1 1))) ((> i1 len1))
(do ((i2 1 (+ i2 1))) ((> i2 len2))
; array-refではないので -1 する必要がある
(if (eq? (list-ref str1 (- i1 1)) (list-ref str2 (- i2 1)))
(set! cost 0)
(set! cost 1))
(array-set! d i1 i2
(min (+ 1 (array-ref d (- i1 1) i2) )
(+ 1 (array-ref d i1 (- i2 1)) )
(+ cost (array-ref d (- i1 1) (- i2 1)) )))))
(array-ref d len1 len2))))
;#,(<array> (0 6 0 7) 0 1 2 3 4 5 6
; 1 0 1 2 3 4 5
; 2 1 1 1 2 3 4
; 3 2 2 1 1 2 3
; 4 3 3 2 2 2 2
; 5 4 4 3 3 2 3)
(init1 0 (length str1))
(init2 0 (length str2))
(calc-LD)))実行
gosh> (load "./loewenstein-distance.scm")
#t
gosh> (loewenstein-distance str1 str2)
3
次は、学習用とするアルファベット小文字のリストの集合(10〜20程度)の用意します(各リストはチャットなどでの1単位の発話とみなす)。ただ、自然言語は10〜20回程度の対話を見ると、その中に同じ単語が出てくるので、完全にランダムなアルファベット小文字のリストでは問題があるかとも考えました。しかし、アルファベット小文字の数の語しか登場しない特性は、ある特定のテーマのみを扱った対話のモデルとみなせるのではないかと考え、ランダムなアルファベット小文字のリストを学習用データとして採用する方向です。
配列に関してのメモ
使用例
gosh> (use gauche.array) #<undef> gosh> (define A #,(<array> (0 3 0 3) 8 3 4 1 5 9 6 7 2)) A gosh> A #,(<array> (0 3 0 3) 8 3 4 1 5 9 6 7 2) ; [0] [1] [2] ;[0] 8 3 4 ;[1] 1 5 9 ;[2] 6 7 2 gosh> (array? A) #t gosh> (array-size A) 9 gosh> (array-set! A 0 0 0) #<undef> gosh> A #,(<array> (0 3 0 3) 0 3 4 1 5 9 6 7 2) ;↓配列は 0 3 0 3 の場合 0〜2 0〜2 までが実質使える。 gosh> (array-set! A 2 2 0) #<undef> gosh> A #,(<array> (0 3 0 3) 8 3 4 1 5 9 6 7 0) gosh> (array-ref A 2 0) 6 ;0で初期化したい場合 gosh> (make-array (shape 0 2 0 3) 0) #,(<array> (0 2 0 3) 0 0 0 0 0 0)
詳しくは↓
gauche.array - 配列
リストの平坦化
http://www.geocities.jp/m_hiroi/func/scheme01.html
リストの平坦化(記法はlambdaを使ったものに変更してあります)
(define flatten
(lambda (ls)
(cond ((null? ls) '())
((pair? ls) (append (flatten (car ls)) (flatten (cdr ls))))
(else (list ls)))))平坦化するリスト
((((#\h #\t #\u . #\v) . #\t) (((#\o . #\d) #\m . #\w) (#\z . #\j) #\w . #\g) *1
実行
gosh> (flatten '((((#\h #\t #\u . #\v) . #\t) (((#\o . #\d) #\m . #\w) (#\z . #\j) #\w . #\g) *2
平坦化されたリスト
(#\h #\t #\u #\v #\t #\o #\d #\m #\w #\z #\j #\w #\g #\l #\c #\r #\x #\c #\o #\c #\k #\l #\y #\z #\t #\a #\h #\h #\g #\n)
なるほどねぇ、appendで繋がないとダメというわけですか。
半日自分で考えて答えが出なかった。
午前中からぐぐって見ればよかったなぁ。
それから、個体の適合度を評価するにはハミング距離ではなく、レーベンシュタイン距離を実装する必要がありそう。
言語学に触れてみる
さて、この手の研究のメインストリートを知らなすぎるので言語学の本を読んでみました。
- 作者: 畠山雄二
- 出版社/メーカー: 丸善
- 発売日: 2003/08
- メディア: 単行本
- クリック: 32回
- この商品を含むブログ (7件) を見る
そもそも、なんでこのようなのことを調べたかは、
１．作成中のGPの出力をリスト構造にすべきか、それともベクターにすべきか判断が付かなかったため。
２．ツリー構造を陽に表現しない(自然言語の記述に近い)ベクターで表現しても大丈夫か判断するため。
でした。結局、言語学のアプローチは現時点でGPに反映させることが困難です。
たしかに、リスト構造を使うと統語構造に近いツリーが表現可能のように思います。
しかし
１．個体が統語構造を意識したリストを出力するようにはなっていない。
２．リスト構造の出力「(e (d f (k g)))」等では個体の出力の評価を例文「(a f d p)」等とハミング距離で行うことが困難。
３．GPにおいて優秀な個体がいつまでたっても発生しないと予測される。
と言うわけで、(e (d f (k g)))は(e d f k g)と表現を変更したほうが、とにかく動くものを作ることができそうです。ですので個体の出力は(e (d f (k g)))をベクター表現もしくはネストしないリストに変換し(e d f k g)のような表現を採用しようと思います。
【基本的用語】
統語構造
語＞句＞文
文(Sentence : S)
句(Phrase)
語([Word|Term|Vocable]?)
例文「太郎が大きい梨を食べた」
「太郎」名詞 (Noun : N)
「が」格助詞 (Case Particle : C)
「大きい」形容詞 (Adjective : A)
「食べ」動詞 (Verb : V)
「た」時制 (Tense)
名詞句 (目的語) (Noun Phrase : NP)
「梨を」
動詞句 (Verb Phrase : VP)
「梨を食べた」
形容詞句(Adjective pharase : AP)
「かわいい」「寒い」AP->A
「怖い」「うまい」AP->NP A
後置詩句(Postposition Phrase : PP)
「研究室で」PP->NP P
【Web資料】
形態素解析・構文解析入門
http://www.unixuser.org/~euske/doc/nlpintro/index.html
現在、「言語学」という分野は、次の 5つの階層に分けられた諸分野全体のことをいう。最初のほうに出てくる分野はすでによく研究されており、下に行くほど問題のレベルが高くなっていき、まだ謎が解けていない部分が多くなってくる :
1. 音韻論 phonology
2. 形態論 morphology
3. 構文論 (統語論) syntax
4. 意味論 semantics
5. 語用論 pragmatics
http://ja.wikipedia.org/wiki/%E8%A8%80%E8%AA%9E%E5%AD%A6
いかなる言語も一定程度の複雑さを有していることが明らかとなり、言語の進化といった見解は現在は否定されている
【気になった本】
心のパターン
http://www.iwanami.co.jp/moreinfo/0053860/top.html
私がこの本を書くことになったのは，生成言語学を導いている考え方が，生成言語学が心と脳の研究に影響を及ぼしたにもかかわらず，一般の人にわかるようになっていないからです．（…）言語学の概念上の基礎は，どの点から見ても進化論，遺伝学，宇宙論，カオス理論，量子電磁力学などと同じくらい刺激的です．もしかすると私たちに心のいちばん奥にある自我について教えてくれるものがあるために一層刺激的なのかもしれません．
単語と辞書
http://www.iwanami.co.jp/moreinfo/0069030/top.html
2.3 単語辞書の実装法
(a) 単語辞書を表現するためのデータ構造 (b) 疎行列の表現法に基づく単語辞書の実装法
2.4 Nグラムの平滑化
(a) 最尤推定法 (b) 加算法 (c) 線形補間法 (d) バックオフ法
