簡易エキスパートシステムの作成 (4)
●実行例 -- 家系図
それでは、プログラムが完成したので実際に動かしてみましょう。具体的な例題として、次のような家系図を考えてみます。
この家系図は、次のような事実で表すことができます。
List 1 : 家系図の定義 ((男性 太郎)) ; 太郎は男性である。 ((男性 一郎)) ; 一郎は男性である。 ((男性 次郎)) ; 次郎は男性である。 ((男性 三郎)) ; 三郎は男性である。 ((女性 花子)) ; 花子は女性である。 ((女性 友子)) ; 友子は女性である。 ((女性 幸子)) ; 幸子は女性である。 ((女性 洋子)) ; 洋子は女性である。 ((父親 太郎 一郎)) ; 太郎は一郎の父親である。 ((父親 太郎 次郎)) ; 太郎は次郎の父親である。 ((父親 太郎 友子)) ; 太郎は友子の父親である。 ((母親 花子 一郎)) ; 花子は一郎の母親である。 ((母親 花子 次郎)) ; 花子は次郎の母親である。 ((母親 花子 友子)) ; 花子は友子の母親である。 ((父親 一郎 三郎)) ; 一郎は三郎の父親である。 ((父親 一郎 洋子)) ; 一郎は洋子の父親である。 ((母親 幸子 三郎)) ; 幸子は三郎の母親である。 ((母親 幸子 洋子)) ; 幸子は洋子の母親である。 ; 規則の定義 ((両親 ?x ?y) (父親 ?x ?y)) ((両親 ?x ?y) (母親 ?x ?y)) ((息子 ?x ?y) (両親 ?y ?x) (男性 ?x)) ((娘 ?x ?y) (両親 ?y ?x) (女性 ?x)) ((祖父 ?x ?y) (両親 ?z ?y) (父親 ?x ?z))
性別の定義は簡単ですね。男性、女性という述語を使っています。父親と母親ですが、(父親 ?x ?y) は「?x は ?y の父親」という関係を表していることにします。
それでは、定義した事実を使って規則を作ってみましょう。まず「両親」という規則を定義します。両親は、父親か母親という事実を満たせばいいですね。このような場合、次のように定義します。
List 2 : 両親の定義 (?x は ?y の両親である) ((両親 ?x ?y) (父親 ?x ?y)) ((両親 ?x ?y) (母親 ?x ?y))
「両親は父親である」と「両親は母親である」という規則を定義しただけですが、最初の節が失敗したら次の節が選択されるので、「両親は父親または母親である」という条件を満たしています。
ほかのプログラミング言語では、「～または～」という条件は OR を使って表現するのが一般的です。ところが、今回のようなエキスパートシステムでは、Prolog の場合も同様ですが、複数の規則を定義するだけで OR を実現することができるのです。それでは実行してみましょう。一郎の両親は誰か質問してみます。
(Q '(両親 ?x 一郎)) ?x = 花子 ?x = 太郎 nil
正解は太郎と花子です。うまく動作していますね。それでは、この規則を使って「息子」という規則を定義しましょう。?x が ?y の息子であるならば、?y は ?x の両親でかつ ?x は男性のはずです。したがって、規則は次のようになります。
List 3 : 息子の定義 (?x は ?y の息子である) ((息子 ?x ?y) (両親 ?y ?x) (男性 ?x))
「かつ」は規則でゴールを順番に並べれば実現できましたね。まず (両親 ?y ?x) を満たす関係を求めます。そのあと、(男性 ?x) で ?x が男性であることを確かめます。(男性 ?x) で失敗しても、(両親 ?y ?x) に戻って次の候補を見つけてくれるので大丈夫です。それでは実行してみましょう。
(Q '(息子 ?x 花子)) ?x = 次郎 ?x = 一郎 nil
花子の息子は一郎と次郎である、と答えが出ました。この節で (男性 ?x) を (女性 ?x) に変更すると「娘」の関係を表すことができます。
List 4 : 娘の定義 (?x は ?y の娘である) ((娘 ?x ?y) (両親 ?y ?x) (女性 ?x))
最後に「祖父」の関係を求める規則を定義しましょう。これは今までと違ってちょっと面倒です。?x の祖父 ?y を求めるには、まず ?x の両親を求め、さらにその父親を求めます。母方と父方に祖父がいますから、父親の父親を求めるのでは母方の祖父がわかりません。そこで、?x の両親を求めるときに ?x と ?y 以外の新しい変数を用意して、?x の両親をその変数とマッチングさせることにします。
List 5 : 祖父の定義 (?x は ?y の祖父である) ((祖父 ?x ?y) (両親 ?z ?y) (父親 ?x ?z))
(両親 ?z ?y) で変数 ?z に ?y の両親が代入されます。そして、次のゴール (父親 ?x ?z) で ?z の父親が ?x に代入されます。変数を使うことで実行結果を保持し、次のゴールへ値を渡すことができるのです。それでは実行してみましょう。
(Q '(祖父 ?x ?y)) ?y = 洋子 ?x = 太郎 ?y = 三郎 ?x = 太郎 nil
祖父と同じように「祖母」の関係も定義できます。
●実行例 -- 簡単なリスト操作
今回作成したエキスパートシステムは、簡単なリスト操作も行うことができます。ユニフィケーション unify は、ドット対を使うと面白い動作をします。次の例を見てください。
(unify '(春 夏 秋 冬) '(?x . ?y) nil) => (?y ?x)
ユニフィケーションは成功しましたが、?x と ?y にはどんな値がセットされているでしょうか。
?x => 春 ?y => (夏 秋 冬)
リストとドット対をマッチングすると、ドットの後ろの変数は「残りのリストすべて」とマッチングします。この場合、?x が先頭の要素とマッチングし、春を取り除いた残りのリストと ?y がマッチングします。
これは、unify の仕組みから考えると当然の動作です。まず、春と ?x がマッチングしますね。次は、CDR 部が取り出されますが、この場合、(夏 秋 冬) と ?y を照合することになります。したがって、?y の値は (夏 秋 冬) となるのです。もう少し例を見てみましょう。
(unify '(春 夏 秋 冬) '(?x ?y . ?z) nil) => (?z ?y ?x) ?x => 春 ?y => 夏 ?z => (秋 冬)
この例では、?x が春、?y が夏にマッチングし、残りのリストと ?z がマッチングします。Lisp では、car でリストの先頭の要素を、cdr で先頭を取り除いた残りのリストを求めることができますが、今回のシステムでは、パターンマッチングを行うことでリストを分解することができるのです。実は、Prolog でも同じようにリストを操作することができます。
それでは具体的にリスト操作を行う規則を作ってみましょう。先頭の要素を求めることと、先頭の要素を取り除いた残りのリストを求めることは、リストのパターンマッチングを使えば簡単に実現できます。
List 6 : リスト操作 ; 先頭の要素を取り出す ((first (?x . ?y) ?x)) ; 先頭の要素を取り除いたリストを求める ((rest (?x . ?y) ?y))
Ｃ言語や Lisp などのプログラミング言語では、実行結果を関数の返り値として出力させます。ところが、今回のエキスパートシステムでは、第 1 引数にリストを与え、第 2 引数の変数で解を取り出すように定義します。簡単な実行例を示しましょう。
(Q '(first (a b c d) ?z)) ?z = a nil (Q '(rest (a b c d) ?z)) ?z = (b c d) nil
first も rest もリストと (?x . ?y) をマッチングします。?x には a が、?y には (b c d) がセットされます。first の場合は変数 ?z と変数 ?x がマッチングするので、?z の値は a となります。rest の場合は変数 ?y とマッチングするので、?z の値は (b c d) となるのです。
次に、リストの先頭にデータを追加する規則を作ります。
List 7 : リストの先頭にデータを追加 ((add_to_list ?x ?l (?x . ?l)))
では、実行例を見てください。
(Q '(add_to_list a (b c d) ?z)) ?z = (a b c d) nil
第 1 引数に追加するデータ、第 2 引数にリスト、第 3 引数で結果を受け取ります。Lisp では cons でリストの合成を行いますが、このシステムではパターンマッチングで行うことができるのです。
次は、2 つのリストを 1 つのリストに結合する規則を作りましょう。Lisp の関数 append と同じ働きします。Lisp は再帰を使って簡単に作ることができました。今回作成したエキスパートシステムでも、再帰を使って簡単に作ることができます。
List 8 : リストの結合 ((append nil ?x ?x)) ((append (?u . ?x) ?y (?u . ?z)) (append ?x ?y ?z))
append は、第 1 引数と第 2 引数のリストを結合した結果が、第 3 引数にセットされます。最初の規則は、空リストと ?x を結合すると ?x である、ということを表しています。これが再帰呼び出しの停止条件になります。次の規則では、頭部で第 1 引数のリストを ?u と ?x に分解して、?x と ?y を append したリスト ?z の先頭に ?u を追加します。
実際の動作は、再帰呼び出しによって第 1 引数のリストが分解され、停止条件で第 2 引数が第 3 引数とマッチングします。この間 ?z はずっと自由変数のままであることに注意してください。再帰呼び出しから戻るときに ?z は束縛されるのです。
停止条件から戻ってきた直後に、?z は第 2 引数のリストに束縛されています。あとは、(?u . ?z) によって第 1 引数の要素が追加され、その値が呼び出し元の ?z の値となります。けっきょく、再帰呼び出しから戻っていくときに、第 1 引数の要素が ?z に追加されていって、リストが連結されるのです。
なにか騙されているように思われるかもしれませんが、これで正常に動作します。それでは実行してみましょう。
(Q '(append (a b c) (d e f) ?z)) ?z = (a b c d e f) nil (Q '(append ((a b) (c d)) ((e f) (g h)) ?z)) ?z = ((a b) (c d) (e f) (g h)) nil
プログラムの動作を考えると頭が混乱するかもしれません。このようなエキスパートシステムでは、「矛盾しないように規則を定義する」ことを心がけた方がよいのでしょう。
ところで、append はリストを結合するだけでなく、リストを分解する動作を行うことができます。
(Q '(append ?z (c d) (a b c d))) ?z = (a b) nil (Q '(append (a b) ?z (a b c d))) ?z = (c d) nil
もっと凄いのが、第 1 引数と第 2 引数を変数にすることです。
(Q '(append ?x ?y (a b c d))) ?y = nil ?x = (a b c d) ?y = (d) ?x = (a b c) ?y = (c d) ?x = (a b) ?y = (b c d) ?x = (a) ?y = (a b c d) ?x = nil nil
このように、2 つのリストに分解できるすべての組み合わせを求めることができます。ひとつの規則で複数の使い方ができるのが、ほかの言語にはマネのできない面白い特徴です。
今度は、リストの中から要素をひとつ選ぶ規則を作ってみます。
List 9 : 要素の選択 ((select ?x (?x . ?l) ?l)) ((select ?x (?y . ?l) (?y . ?z)) (select ?x ?l ?z))
select は第 2 引数のリストから要素を選んで第 1 引数の変数にセットし、第 3 引数に残りのリストをセットします。最初の規則は簡単ですね。第 2 引数のリストを分解して先頭の要素を選びます。そして 2 番目の規則では、先頭要素を取り除いた残りのリストの中から要素を選びます。頭部の第 2 引数 (?y . ?l) でリストを分解し、select を再帰呼び出しします。要素 ?y は取り除いたリスト ?z に追加することをお忘れなく。
それでは実行してみましょう。
(Q '(select ?x (a b c) ?y)) ?y = (a b) ?x = c ?y = (a c) ?x = b ?y = (b c) ?x = a nil
この select を使って順列を求めることができます。
List 10 : 順列を求める ((perm nil nil)) ((perm ?x (?z . ?l)) (select ?z ?x ?y) (perm ?y ?l))
perm は第 1 引数のリストに格納されている要素の順列を第 2 引数の変数に求めます。2 番目の規則を見てください。?x から select で要素をひとつ選び ?z にセットします。次に、残ったリスト ?y の順列を perm で求め、その結果 ?l に ?z を追加すれば ?x の順列は完成します。再帰の停止条件は、リストの要素が無くなった場合です。
再試行するたびに select は新しい要素を返すので、これですべての順列を求めることができるのです。では、実行してみましょう。
(Q '(perm (a b c) ?y)) ?y = (c b a) ?y = (c a b) ?y = (b c a) ?y = (b a c) ?y = (a c b) ?y = (a b c) nil
正常に動作していますね。パターンマッチングとバックトラックだけで、ここまでリスト操作ができるとは驚きです。ただし、変数の使い方がＣ言語や Lisp と大きく異なるので、慣れるまでちょっと苦労しそうですね。
これまで作成したリスト操作は Prolog でも同じように行えます。参考までに、Prolog で書かれたプログラムを示します。
List 11 : Prolog のプログラム % 先頭の要素を取り出す first( [X|Y], X ). % 先頭の要素を取り除いたリストを求める rest( [X|Y], Y ). % リストの先頭にデータを追加 add_to_list( X, L, [X | L] ). % リストの結合 append( [], X, X ). append( [U | X], Y, [U | Z] ) :- append( X, Y, Z ). % 要素の選択 select( X, [X | L], L). select( X, [Y | L], [Y | Z]) :- select( X, L, Z ). % 順列を求める perm( [], [] ). perm( X, [Z | L] ) :- select( Z, X, Y ), perm( Y, L ).
Prolog では、リストを [ X, Y, Z ] のように [ ] で表します。要素がない [ ] は空リストを表していて、ドット対のドット ( . ) に対応するのが | です。エキスパートシステムの規則とほとんど同じですね。このシステムに数値演算、条件分岐、入出力などの機能を組み込むことで、よりいっそう Prolog インタプリタに近づけることができます。
●おわりに
パターンマッチングとバックトラックを用いて、規則の中から答えを導き出す簡易エキスパートシステムを作成しました。ドキュメントの分量は多くなりましたが、プログラム自体は約 7 k byte です。記号処理が得意な Lisp だからこそ、ここまでコンパクトに記述できたと思います。ほかの言語ではパターンマッチングを作るだけでも大変でしょう。
今回作成したプログラムは簡易システムとはいいながら、その動作は Prolog とほぼ同じです。もっとも、これより複雑な規則を作るのであれば、このシステムでは力不足です。これに対し Prolog はプログラミング言語です。Lisp と同様に、データ型を判定する述語、算術演算、プログラムを制御するための述語や入出力が組み込まれているので、本格的なプログラムを作成することができます。
一時期、第五世代プロジェクトの影響で Prolog の人気が沸騰しましたが、最近は鎮静化してしまったようです。ですが、Prolog は面白い特徴を持ったプログラミング言語です。事実と規則を定義していく、つまり、物事の関係を記述していくプログラミングスタイルは、ほかの言語にはない独自なものです。M.Hiroi が初めて Prolog でプログラミングしたときは、Ｃ言語や Lisp との違いが大きすぎて、とても困惑してしまいました。かえって、ほかの言語を知らない方が、Prolog を簡単にマスターできるかもしれません。
このエキスパートシステムに興味を持たれた方は、ぜひ Prolog にも挑戦してみてください。よろしければ拙作のページ Prolog Programming もお読みくださいませ。
