本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
7-4 Inference (iii) - Unification, Inference (iv) - Forward chaining
Loading...
來自 National Taiwan University 的課程
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
153 個評分
從本節課中
First Order Logic
與講師見面
于天立副教授 (Associate Professor)
電機工程學系 (Department of Electrical Engineering)
我們剛講的要能apply generalize的Modus Ponens 裡面有個重要步驟其實就是
其實就是把，找一個substitution，使得這個substitute完以後， p1
p1’會等於p1，然後對於每一個前提都能找到這樣的substitution。
好，找一個substitution使左邊等於右邊這件事情其實不是一個很trivial的work，
那這個概念我們稱它為unification。這個unify
概念其實就是我們return一個，我們稱它為unifier，其實unifier就是一種
眾多substitution裡面，其中一種可以讓左邊等於右邊的。例如，概念上就是說
我call這個unify，然後把p,q丟進去，那它return這個值就是一個substitution， Theta是個substitution。
那它能得到目的就是你p1用qsubstitute完以後 跟q用theta去substitute完，結果會一模一樣。
好我們來看一下譬如說，這是我的一個例子，這是我的p，這是我的q，
這兩個式子，那這是我，這邊Theta是我可以的，可能能拿到的unifier，
那譬如說像這邊的話像左邊等於右邊，那你可以基本上是一種比對的方式，
然後就是knows 跟knows，然後John跟John，然後你就知道x等於Jane。
好那所以我們拿到的substitution就是x替換成這個。
好，那有一些你可以同時unify兩個變數，兩個以上的變數，
像這個例子的話你可以是John是y嘛，那x是Bill這樣， 所以你就得到這個substitution。
好這幾個都OK,那我們substitute也可以替換function， 像這裡這個例子的話我們知道John要
替換成y，然後你的x要換成Mother(y)，
那我們又已知，通常我們會進一步做，因為我們已經知道y是
這個y，剛我們在前一步substitution我們知道是John，所以應該可以 直接把，就是x換成Mother
of John， 這個樣子。好，那如果我們要，再看最後一個例子。
如果我們要unify這兩個式子， 其實你看John要是x，然後
Eliza要是x，那這一般而言我們應該要會fail， 就是你x不可以又是John又是Eliza，那如果是是的話你得apply了John
=Eliza， 可是在我們的knowledgebase裡面並沒有給你這樣的資訊，就是
John跟Eliza你沒有特別聲明，或是你沒有正常的推論，你不應該 假設他們倆是同一個人。
好，那這樣所以這邊會fail，好，可是其實 fail剛這個例子fail，並不是一個
就是我們如果直接看到式子，應該是得不到正確的結論，因為x既要是John又是Eliza
那會，John跟Eliza是同一個人，可是，如果我們回頭思考那個x這個變數是怎麼來的的話， 這其實不是一件，就是
應該讓它unify出來，為甚麼呢，因為這邊的x其實是
不代表它指的是同一個東西。就是我們剛這個式子的p的x，
好這個變數，因為我們省略了東西，但這東西可能可以是for all x的， 可以是存在x，
這是變數來源。好那在這種情況跟下面我們已知這一個就是for all x跟存在x 這兩個x不需要是同一個。
好，也就是說我們在做unification的時候其實前面之前要先做一件事情 叫standardization，
也就是說，像我們剛那個例子，基本上你應該先把p，
這是p，這是q，你應該先把p,q的變數先standardize，
使得它們不一樣就不需要，就不需要一樣的就不要一樣，就像這個x跟這個x是不需要一樣的， 那通常做法是一個流水好的變數一直下去，
這是x1，下一次看到x2，再看到x3等等。如果把這兩個變數 定為不一樣的，那你unify結果當然可以是x是Eliza，
x17是John。OK。
好，那其實在一些case裡面，unifier會不止一個。好， 譬如說我們看一下下面這個例子。
譬如說如果我們要unify這兩個， 好，這個是我的p，還有這個是我的q，這個東西，
那這個，你當然可以做一件事，就是x,y,z它都是John， 這是第二個，這個unifier，這樣的話左邊會等於右邊，就是John
knows John，John knows John， 就左右都長得一模一樣，但是這不是一個最generalize的unifier，那一般-
來說我們希望unifier 這個function能return的， 我們指的是most general unifier。
好，我們簡稱MGU，那在這個例子裡面它的MGU就是應該是
我只要y是John，那接下來x是z就可以了。
OK,那剩下的，就是不過多的去綁定這個sentence， 這個sentence也就是在術語來說，
一般而言我們一個sentence裡面的只要是變數，就是事實我們習慣叫ground
truth，好，這個大家應該聽過，所以ground就是一個弟弟， 那在邏輯上我們常常講說如果是一個變數的話我們就float，
或說lifted，就是把一個ground的term把它舉起來， 並一個變數叫lifted，這是我們常用的講法。也就說反正你在一個
unifier我們最好的事情是不要把一個sentence綁的太死， 就不要把它bind的，盡量不要去ground它，
除非必要。好那這樣的話return回來就是一個我們most general的unifier。
好，那你要得到
你要怎麼得到most general unifier我們在這一講，這算比較advance的差別，就不再繼續， 其實它用的技巧是跟
我們前幾講講的search algorithm其實類似，它是一個樹狀結構， 然後兩邊就是等於從p和q，
兩邊同時用 樹狀結構去展開，然後展到直到某一層兩邊是長一樣的， 那我們就把它們match在一起。那這時候就是如果用
的是那種bread-first search，也就是說你用盡量不要往下伸進去，
也就你return的是最短層數的那一個話通常那一個就是most
general的unifier。好，那另外一個我們提到， 因為在這個search
unifier的過程，其實就是一個搜尋的過程， 那在搜尋的過程我們提到，我們這邊提到一個名詞叫occur check，
那這個occur check做事情其實是說 某個東西，某個term出現多少次，好，
這個地方我沒有要打算講的過於詳細，有同學對這個有興趣的同學可能要查， 要接觸一下比較advance的進階的人工智慧的課程
接著搜尋技巧，但是一般而言譬如說 像我們假設說這是p，好這是q，
這兩個sentence，基本上這兩個sentence是不存在unifier，也就說 這兩個sentence你不管x帶甚麼東西，它都應該左邊都永遠不會等於右邊因為
右邊的式子永遠多一個s，對不對，但是如果你做 occur check的話， 你就可以瞭解p不能跟q
unify，但是， occur check要做其實不是一件簡單的事情，它類似於 要做occur check這件事情
類似於在搜尋的過程中你要去check某兩個state是不是repeat， 是不是已經重覆了。
那這件事情我們之前在搜尋的時候就講過，你如果沒有足夠的記憶體不見得能夠做好這件事
而且寫起來，就算你有足夠的記憶體寫起來你的algorithm的效率會比較慢一點點。
好，所以其實現在大部分，其實我們晚點就會講到prologue這個system， 大部分邏輯演繹的system
其實很多時候是略過occur check的。也就說，很多system我們在實做的時候，
會使得這個p和這個q這樣的會使他們unify，會成立。
這當然結果不是正確的，但是為了一些現實的resource的問題我們不得不這樣做。
接下來是一樣的事情我們就是我們可以定義一個definite clause， 就是first-order definite clause，如果希望我們的inference
更有效率一些的話，那也就是definite clause， 也就是我們之前提的generalize的Modus Ponens可以apply的
一個KB， 好，那原則上我們要提醒大家 就是exactly one positive literal，
你可以有variable，好我們看一下怎麼用definite clause 和generalize Modus Ponens來 演繹這個問題。
好，這個問題就是這句話蠻長的，大家可以看一下the law says it
is a crime for an American to sell weapons to hostile nations.
the national Nono, Nono是一個假想的一個國家吧， 沒有真的這個國家。OK, anyway，The country Nono,
an enemy of America, has some missile,有一些飛彈， 然後all of its missiles
were sold to it by Colonel West,好就Colonel West上校賣給他的， 然後Colonel West又是American，
好但是這整段英文跟我們講的，我們想要用這一段話試著證明Colonel West是有罪的。
好我們看一下用first-order logic怎麼做。好， 首先第一件事情當然是我們要把那一句話把它
先把他transfer成first-order logic的sentence。好， 那我們來看一下基本上像這句話
the law says，前面省略的……就是the law says， it is a crime for an American
to sell weapons to hostile nations,好那基本上就是 你對任何一個人，只要是American，好像我這邊其實省略了就是for all拉。
好，習慣性， 習慣性是這樣接下來我們要做的，所有的例子 是對一個first-order logic KB
因為如果有existence的時候我們都會把它用 EI搞定，好，那for
all的情況下呢，你一樣可以用EI全部弄完，不過那樣就回到 propositionalize的過程，所以基本上對for all我們
是保留。existence我們就用EI把變數換成常數，那也就是說 現在接下來我們的first-order
logic KB裡面所有的變數都是for all， 那既然說所有變數都是for all我們就不再寫for
all這個東西，就大家記得一件事，現在只要看到變數， 我們就是for
all的意思。好，對任何一個x，只要是x是American， 然後對任何一個y，只要y是weapon， 然後x是American
sell了weapon to z，而且z是跟美國是敵對的， 則x就criminal。
好，x就是有罪的。好，那就是基本上你可以看一下就差不多是上面這一句英文的翻譯。
就寫成邏輯式。好。然後我們接下來有一句senten說 Nono這個country有一些missiles，
那也就說，存在，你直接寫的話是這樣，存在某一個x， 然後nono有x，而且x是missile，
好，大家還是注意下，existence我們對應的是and， 好這我們之前前面有提過。好，到這邊你是第一次轉換，但到這邊時候我們就立刻apply
EI， existential instantiation，把x換成某一個東西。那我們現在換的話， 就譬如說我們用流水號。我們就換成M1，
把x換成M1，那接下來這個就是真正到我們KB裡面的東西。就已經 把它換成Skolen的constant了。
好，那接下來是對所有的missile賣給他的都是， Ｎono所有的missile全都是Colonel
West賣給他的，所以基本上只要 對for
all，所有的x，假如x是missile，然後Ｎono又擁有這個x， 則就是West賣x給Ｎono的。
OK,然後，我們的，這是我們基本上的knowledge，就是
missile是weapon，飛彈是一種武器，所以只要for all x，對任何的x，
只要x是missile，他就是weapon，大家還是可以注意一下 我們這邊用的for all 對應的是imply。
好，這是這個樣子過程。好，那接下來就是任何跟美國敵對的
country我們都認為它有敵意hostile的，所以任何x 只要x是跟American是enemy，就imply它是hostile。
然後，West是American，好這就是我們已知的事實。
然後接下來，country Ｎono是 美國的敵人，這個也是已知的事實。好到這邊我們就把整個，
我們上面那一段話以及我們所有知道的knowledge 換成一個first-order logic的過程，那接下來就上我們
就可以apply forward chaining， 然後用generalized 的Modus Ponens 去做forward chaining。
那forward chaining其實這邊大家看到是個pseudo code， 那其實看這個還好啦，你可以看到這邊其實就是Modus Ponens的過程在這邊。
這邊其實就是你只要找到一個substitution，使得它的前提都可以對上的情況下，- 我就直接得到這個結論。
OK，然後我們就一直試著去做這件事， 然後在過程中我們要會需要call
到這個unify，去找那個substitution，好的，只要找得到 substitution我們就可以試試看。
那接下來我們可以看一下這個forward chaining怎麼證明，我們剛轉換完了以後 我們最後目的 是要證明Colonel
West是criminal的嘛，那我們把我們剛才所有的這幾個式子， 大家可以看到這邊有8,
這邊有8個式子。好那我們把它換成就寫在這邊，寫在我們現在的knowledge base， 好那我們是一樣， 就是在forward
chaining常常會這樣說有implication，他們都，這些列的8個 全都是whole clause，那或者你要講definite clause也可以，
那前面這邊的，一般來說我們就相當於true，imply, owns，Nono,
M1， 好，那只是通常我們習慣上，就是讓他知道 這其實還是一個definite clause，
但是習慣上我會把這個就，但我們不會無聊這樣寫， 就把這個拿掉，那這一類形式我們通常把它稱為fact，
那通常你還有，你裡面還有implication的，這個東西我們稱為， 就裡面寫成implication那有時候也把它稱為
rules都可以。好，那基本上我們就 回到那forward chaining分為已知的事實還有我們的
規則。好那接下來我們要做forward chaining要做的事情就是把所有可能的， 其實就一樣，就把所有可能的事實都導出來，那基本上我們會看一下，
譬如說，如果大家還記得，propositional那邊的時候 我們就是看一個前提有多少沒有被滿足，
譬如說第一個generation可以看，就是R5一個check，
這邊還有沒滿足的，premise，OK，這邊是就這一個，這個，這個，這個，
然後你去看一下然後發現，你可以找得到一些，可是你沒法全部同時找到， 所以這個我們就等到下一個
iteration來做。但現在像R6其實還蠻簡單的，R6你看一下。這是我們的p1， p2，這是前提，然後下面得到結論這是Q。
那我們看一下，我們已知的事實你會發現這個很像，這是p1‘。 對，然後你看一下，這是
Ｏwn(Nono,M1)，所以這邊是p2’， 然後接下來你就找unifier，然後call unifier他應該就會得到這件事，
就是x就是M1，好，x是M1，這個x就一樣，可以套到，就是M1，
OK，這邊，好，那就是這個部分。
好，那你就會得到一個結論，結論就是把x換成M1。
得到這個結論， 好，那這個結論一旦得到以後，你就把它加入已知的事實。就是把這個加到已知的事實裡面。
然後繼續，接下來你看啊，R7也很簡單，R7這個missile跟這個很像
missile跟這個很像，就直接把他換成M1，好你就得到這個結論， M1是個weapon。
好，那類似我們可以做R8，R8這個enemy跟這個enemy很像， 你要替換的就是Ｎono，
所以你會得到nono是hostile的，ok。
好，那接下來就第二個generation。第二個generation這個
演繹蠻簡單的，因為你得到了這三個，就會發現你得到這一個 然後你會發現這個跟這個很像。
然後，你知道這個結論，這個跟這個很像，
然後你還得到這一個，那這個跟這個很像， 好，接下來最後一個，American呢，是這一個。
這個跟這個很像。
好，你就去call unifier，看能不能找到合適的substitution， 那實際上是可以找到，
你找到的結果就是x換成West，然後y換成M1，Z換成Nono就可以搞定。 那你這些前提都知道以後你就把這個substitution一樣
套到它的結論，那這個結論裡面就是把x換成West。
所以你就得到了criminal west。
好，我們來看一下圖。那其實這是我們剛， 其實有講完的啦，其實就這只是用圖像來表達一下，這是第一個，
這是第一個，一開始我們知道在non-fact，一開始在KB裡面。 好這是我的第一個iteration，
第一個iteration，那我們就能做的事情就是我們剛剛講的就是這一個，
從這邊你會得到這是某一個rule得到的，然後接下來這兩個rule， 你可以得到這個結論，
好這一個又得到這個結論，所以，第一個iteration裡面我會得到新的三個
已知的事實，好接下來就是靠這三個已知的事實來配上 我knowledge base裡面已經知道
Colonel West是American，就會直接得到 West是criminal的，好，在這過程中-
我們這畫圖不是全部的啦， 只是因為forward chaining它基本上 所有導出來的事實她全部都會導出來，那我們這邊畫的就是我們可以證出
West是criminal的那一個圖。
