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」
一種の疑問文となる。
正確に言うと、否定疑問文に対応。
・では、何が無いのか？２つある。
普通の否定平叙文がない！
ちなみに、≠は否定ではない。≠は違う人だ、と宣言しているだけ。
つまり、肯定的に二つのものが異なると解釈する。
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とは否定疑問文で解釈している？
正確に書くと、
∧∀Ｘ∀Ｙ(￢add(0, s(0), X) ∨ add(X, X, Y))
= 全てのＸに対して、いないので、
・教科書の例
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 という前提が付いていた。
試験問題では、∀Ｘ∀Ｙは書く？
∀＝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という手続きが呼ばれたので、Ｐという手続きが呼ばれたと考える。
どちらも、下記のルールの特殊な場合に過ぎない。
A⇒B B⇒C
------------
A⇒C
となる。
・prologの実行メカニズムの基本
知識として、二つの方法を使っている
P :- Q,R.
P :- S,T.
↑の2通りについて調べる。
1と折り目で間違っていた場合は、
Ｓ、Ｔに展開して、"やり直す"！
↑これはprolog独自のアルゴリズム。
このようなアルゴリズムを決定性アルゴリズムという？
反対を、非決定性のアルゴリズムという？
最初にやって、駄目だったら次の方法を試してみる。
このような振る舞いをbacktrackを使うという。
つまり、試行錯誤するということ！
普通のprologの処理系は、書いた順番に実行する。逐次的に実行する。
論理値だと思ったときには、規則の中の条件の順序はどうでも良いが、
基本的には、上に書いた文から、左に書いてる節から評価していく。
一般ruleというものがある。
・帰納的定義
nの階乗定義の場合、
n! = 1 (n=0) ----- base case
= n(n-1)! (n>0)
base caseを先に書く！
一個のルールのときには、条件を絞っていく。
なるべくさきに、条件を絞っていった方がよい。
計算に時間のかかるものは、後にやった方がよい！
例：
条件を4つ書いたとき、XもＹも女兄弟ですか？というとき、
親はせいぜい二人しかいないのだから、まず共通の親を見つけたほうが良い！
ＸとＹは別人だ、といいたいとき。
もし、誰かの女兄弟を探してくるとき。
Ｉは与えられた人物の女今日はを探してくる。
女の人を探してくる。
Ｙさんと違う人を探す。
↑コレはnaive
Ｘという人を探すんだとしたら、
確立1/2になるようなものは後に探した方がよい。
なるべきたくさんある可能性を速く絞らせた方がよい。
・問20
(2,2)のような場所でも、;を打ってたら、そのうち出てくるものでなくてはいけない。
(0,X)を最初に出力しようとしていくと、(2,2)は出てこない。
⇒実現するためには
論理式を入れたら、自動的に証明してくれる。
・prolog
他の言語に比べたら、知能的っぽいけど、そこまで万能ではない。
・まとめ
今までは、ifとか条件否定とかやってきたが、
whoとかwhatが引数としてきた場合、
どうやって変数に代入するのか、という話はまだやっていない。
論理式を弄くりながら、学んでいく。
一階述語論理の三段論法だと、
human(socrates) ∀X(～以下略
＋と－でキャンセルできる。
prologでは =は"=="の意味になる。
来週はbacktrackに基づいて、unificationは何をやっているかを調べる。
0 件のコメント:
コメントを投稿