2008-05-12

Computational Intelligence 3

essayはほぼ終了。あとはresumeとcover letter(多分今回は必要ないっぽい)書いて糸冬了かな。さっさと終わらせて、言語処理系と回路理論の課題やって、hardware記述言語の勉強+状態遷移図の復習しよう。あとそろそろJudeとprologのprogrammingも出来るようにならんとな。でもOSが大分遅れ気味なのも痛いなぁ。

orz

反省しなくては。

こんな事態になった原因は、俺の脳内処理能力+課題解決能力が糞なせいに他ならない。いつでもどこでもtoggle switch一つで脳をフル稼働させられる人間になりたいわ。


----- Computational Intelligence note May 12th, 2008 -----
[Computational Inteligence]
・述語とは
あるものがカテゴリへの所属しているとか student(bob)
性質を持っているとか tall(bob)
動作をするとか runs)bob)
関係とか loves(bob,liz)
述語に引数として与えると原始論理式(atomic formula)となる。

・prologと一階述語論理で扱う記号
定数、変数、関数を一階述語論論理で扱う
定数 bob, 0, june, nil
変数は大文字
数学と情報では変数の概念が違う
⇒単一代入変数
一回決まったら、他の値にはならない
k=3としたら、途中でk=6とかにはしない。

逆の振る舞いを"破壊的代入"という
⇒一回与えた変数を書き換えること

関数 s(X),date(dec,31)
ものからものを作る

"一階"とは、遠陬にはものを表す変数しか入らないということ!
⇒変数にはものしか入らないということ!

・記号 vs. 記号の意味
記号は何らかの意味を担っている。
計算機の中で閉じた意味を作ることが出来る

計算機の中といっても計算機の外とも関係がある。
計算機の中のbobというシンボルと
計算機の外のbobという実在する人物は
人間が結び付けている。

結びつけは全て人間が行っている。
記号の意味はプログラマが決める。

論理式が言及している集合のことを、対象領域という。

・記号による知識表現の例
例えば、生死を扱うとき

定数:socrates
述語:Human, mortal

あらゆるものに名前をつけるということは大変なこと
⇒monthは別々でもいいが、dayにいちいち名前をつけることは大変!
5 = s(s(s(s(s(0))))) means 0の次の次の次の次の次の数

rectangle()関数を使えば、
(x0, y0)と(x1,y1)を貰うことで
長方形を作ることが出来る。

⇒関数と考えるよりもデータ構造と考えた方が自然な場合もある。
書いたものが何を表すかというと、ある複素数を表す"つもり"になっている。

prologでは、f()は定数の親戚と考えても構わない。

・解釈
知識には宣言的と手続き的がある。
prolgにはその両方が備わっている。

prologはどうやって与えられた質問に答えているのか?

例えば、
宣言的な顔:兄弟とか足し算の概念を宣言的に定義している。
⇒何回やっても答えが同じでなくてはならない。
⇒証明をする必要がある。

・宣言的な解釈
基本的には論理学の復習
プログラムとは、ruleを書き並べたもの。
個々のruleがandかorでつながっている。
⇒programではandで繋がっている。

とりあえずデータベースみたいなプログラムを考える。
cf.家族関係(2) - 用語の意味の定義

個々のruleはprogrammerは正しいと思って書かれている。
どれか一個が正しいのではなく、全て正しいと思って書かれている。

では、個々のruleはどうなっているのか?
規則(rule) --- 節とかclauseとか言う。

自然言語で言うと条件文に対応している
factとは肯定平叙文!

質問(query) --- も「clause」
一種の疑問文となる。
正確に言うと、否定疑問文に対応。

・では、何が無いのか?2つある。
普通の否定平叙文がない!
ちなみに、≠は否定ではない。≠は違う人だ、と宣言しているだけ。
つまり、肯定的に二つのものが異なると解釈する。

ORでつながった複文もない。

・演習
is_parent_of(pam, bob)
femail(pam)
is_mother_of(X, Y) :- is_parent_of(X, Y), femail(X)

↑全体はandで繋がっていると考えて、書き直すと、

is_parent_of(pam, bob)
∧ femail(pam)
∧ ∀X∀( Yis_mother_of(X, Y) (is_parent_of(X, Y) ∧ femail(X)) )

となる。さらに三行目は、別の書き方をすると

is_mother_of(X, Y) ∨¬is_parent_of(X, Y) ∨ ¬femail(X)

となる。また、↑のことをclauseという。

・ここまでのまとめ
つまり、節とは、原始論理式やその否定をorで繋げたもの。
原子論理式はばらすことが出来ない論理式。
これ以上バラスと、論理式ではなくなってしまう論理式のこと。

基本的に、if文は可能
結論にはnotは付かない。

条件は一般には0個以上ある。
条件の数にはたくさんあってもよい。
しかしながら、結論は一個でなければならない。
これが、prologの特徴となっている。

?- add(0, s(0), X), add(X, X, Y)
?- means :- または "←"

基本的には、まず"or"でバラす。
つまり、¬add(0, s(0), X) ∨ add(X, X, Y)
orで繋がっていない分はfalseであるといえる!
false ← ¬add(0, s(0), X) ∨ add(X, X, Y)?
つまり、矛盾であることを言っている。

つまり、prologとは否定疑問文で解釈している?

正確に書くと、

∧∀X∀Y(¬add(0, s(0), X) ∨ add(X, X, Y))
= 全てのXに対して、いないので、

・教科書の例
false :- is_ancestor_of(X,jim)
⇒for all X, X is not an ancewstor of jim
⇒is there no ancestor of jim?
Yes! pat is an ancestor!
yes! ann is an ancestor!

・もう一つの解釈の可能性
条件文の略記。

左辺にyes(x)は
If X is an ancesstor of jim, say "yes" and answer C.
⇒yes, pat is an answer.
⇒yes, ann is an answer
否定疑問文が入ったらyesと答えようとして、証明手続きが機能
P⇒yes, not Pは非常に近いといえる。

・変数の役割
もう一つ大事なことは、変数というのはfor all という前提が付いていた。
試験問題では、∀X∀Yは書く?
∀=universal con~~? ⇒ 全称記号

who is ancestor of jimと聞くところを、prologでは
is there ancestor of jimと聞いている。

質問の中の変数ではどうなっているのか?
例:is_ancestor_of(X, jim)という変数があったとすると、
¬(ヨX is_ancestor(X, jim))

XがYのgrandfatherだというとき、その中にzさんの記号を書くと、
zさんの存在記号となる?

つまり、
∀X∀Y∀Z(g_father(X, Y) ← (father(X,Z)∧father(Z,Y)))

∀X∀Y(g_father(X,Y) ← ヨZ(father(x,Z)∧father(Z,Y)))
は、同じことを言っている。
↑情報数学の復習

条件文に入れてしまうと存在記号に化ける!

・三段論法について
bottom-up
⇒ P  P⇒Q
-------------
⇒Q

prologでは、ちょっと違う。
⇒top-down

Q⇒ P⇒Q
----------
P⇒

↑Qという手続きが呼ばれたので、Pという手続きが呼ばれたと考える。

どちらも、下記のルールの特殊な場合に過ぎない。

A⇒B B⇒C
------------
A⇒C

となる。

・prologの実行メカニズムの基本
知識として、二つの方法を使っている
P :- Q,R.
P :- S,T.
↑の2通りについて調べる。
1と折り目で間違っていた場合は、
S、Tに展開して、"やり直す"!
↑これはprolog独自のアルゴリズム。

このようなアルゴリズムを決定性アルゴリズムという?
反対を、非決定性のアルゴリズムという?

最初にやって、駄目だったら次の方法を試してみる。
このような振る舞いをbacktrackを使うという。
つまり、試行錯誤するということ!

普通のprologの処理系は、書いた順番に実行する。逐次的に実行する。
論理値だと思ったときには、規則の中の条件の順序はどうでも良いが、
基本的には、上に書いた文から、左に書いてる節から評価していく。

一般ruleというものがある。

・帰納的定義
nの階乗定義の場合、
n! = 1 (n=0) ----- base case
= n(n-1)! (n>0)
base caseを先に書く!

一個のルールのときには、条件を絞っていく。
なるべくさきに、条件を絞っていった方がよい。
計算に時間のかかるものは、後にやった方がよい!

例:
条件を4つ書いたとき、XもYも女兄弟ですか?というとき、
親はせいぜい二人しかいないのだから、まず共通の親を見つけたほうが良い!
XとYは別人だ、といいたいとき。

もし、誰かの女兄弟を探してくるとき。
Iは与えられた人物の女今日はを探してくる。

女の人を探してくる。
Yさんと違う人を探す。
↑コレはnaive

Xという人を探すんだとしたら、
確立1/2になるようなものは後に探した方がよい。

なるべきたくさんある可能性を速く絞らせた方がよい。

・問20
(2,2)のような場所でも、;を打ってたら、そのうち出てくるものでなくてはいけない。
(0,X)を最初に出力しようとしていくと、(2,2)は出てこない。

⇒実現するためには
論理式を入れたら、自動的に証明してくれる。

・prolog
他の言語に比べたら、知能的っぽいけど、そこまで万能ではない。

・まとめ
今までは、ifとか条件否定とかやってきたが、
whoとかwhatが引数としてきた場合、
どうやって変数に代入するのか、という話はまだやっていない。

論理式を弄くりながら、学んでいく。

一階述語論理の三段論法だと、
human(socrates) ∀X(~以下略
+と-でキャンセルできる。

prologでは =は"=="の意味になる。

来週はbacktrackに基づいて、unificationは何をやっているかを調べる。

0 件のコメント: