基本上 Database Semantics 講,又做三個假設。 第一個假設叫做 Closed-World,Closed-World 是意思就是說,所有沒有提的就全都是錯的。 我們進入 user,我們打一下,譬如說, 我假設說,我已知的我的是 a 到 b 有連接,然後 b 到 c 有個連線。 這是我們自己想的。 好這邊我們就結束了,好那你 listing 也 ok。 它就是,因為這都是常數,所以基本上你就只能都這個樣,它不會替換因為沒有變數。 好,那如果我問它 譬如說,c 跟 a 之間有沒有,有沒有連接。 那這個其實我們沒有在我們的 database 裡面 它其實應該是不知道的。 但它,但在 database mantics裡面,就是你沒有講的就是沒有 ok,所以它的回答是 no。 它會很明確,你沒有跟我講 c 跟 a 之間有連線,那就是沒有。 ok 這是第一個叫做 Closed- World 的假設。 那第二個假設叫做 Unique-names。 就是在我們講 [iii]的時候我們一開始就講到,就是說,我們講 John 有兩個 brother,是 Mark and David,那我們還要特別,在 FOL 裡面,你必須要,還要特別聲明, John 跟 Mark and David,這三個名字所代表的人都是不一樣的。 它並沒有特別說不一樣的名字就是不一樣。 那 在 Database mantic 裡面只要不一樣的名字就是不同。 譬如說我們會很容易的知道,如果 a 等於 c,那它就會跟你說不。 我還要知道 a 跟 c 這兩個,你用不同的名字,那就是不同的東西。 就這樣。 那最後有一個就是 是叫做 Domain Closure。 也就是說,你只要在 [iii] base 裡面,你沒有,被你選到的任何,不管是常數,或是 function,只要 你沒有提到的它都不存在。 好,這是最後一個,Domain Closure。 好。 那如果我們透漏使用 Database 裡面 Semantics 的話,那有很多,就可以把它講的很簡單。 你比如說它polo,裡面講說,OK 我們有 4 門課,那是,分別是 在美國,基本上課程我們都是這樣定,(CS,101),那 101 通常是一個最基礎的課程,出國去唸書的同學大家都知道。 那假設我們還有一個課,課號是(CS,102),那(CS,106),還有一個(EE,- 101)。 那 這是,用 Prolog 寫的話你就直接這樣寫就可以了,那就是代表這 4 個為 True,哪個在,在事件中 就只有這 4 個。 那如果用 FOL 來寫的話,其實還蠻複雜的。 因為你必須要講說 [iii] 就這 4 門課嘛,對不對,那你要講 at most 4 門, 而且要,最,也就 at least 4 門課。 所以你必須要寫說,類似這樣,如果有 Couse(d,n),那就 imply 了 代表 [iii] 它就是(CS,101),或是(CS,102),或者 (EE,101)。 那接下來這是 at most。 接下來你還要說 就,就是至少有這 4 門課,也就是說,你還要說等於 如果 x = y,那就是代表了,要,要,x 必須是 CS 和 y 是 CS,就是,你要說,他們必須都是一樣的。 然後 102 要和 102 106 和 106 一樣。 這些都是你用 FOL 裡面所要定,因為你沒有所謂 不同的名字代表的,不同的東西。 好那我們,提過了 forward chaining 以及 backward chaining,那我們,最後再來提我們在[iii]上所 [iii]第一個講的 resolution。 那 resolution 一樣在 FOL 是可以使用的。 那 那它基本上一樣要,因為有變數的關係,一樣一樣要走 substitution,那如果你找到UNIFY,使得 某兩個 clause 裡面的 [iii]他們互為一個 complement 的關係的話,那你就可以使用。 譬如說如果我們這句話 說,ok,就是,有錢人都不快樂。 這個這個當然不一定是真實的事情,它只是給你舉個例子,那我們又知道 Ken 是有錢的。 那我們可以利用 UNIFY 的方法去 UNIFY 這兩個 部分。 那你可以 UNIFY 出來 x 其實就是 Ken。 這個 substitution。 那你就可以得到,結果就是 Unhappy(x) x 用 Ken 來替換。 好這就是一樣的東西,是 resolution。 那你要使用 resolution 的時候,那你所使用的就是,額, 你用,你先把整個邏輯式都轉為 CNF,[iii]。 然後,之後你要做的事情就是 KB 而且你不要的那個結論,就是 反證法嘛,矛盾證法,那,你就說,而且,不要那個結論的話呢,你可以導出矛盾的結果。 好那我們 forward chaining 和 backward chaining 呢就只能使用在 FOL裡面[iii]clause。 那它不是整個 FOL 的全部,它只是一個小小的 subject。 那resolution 的話呢可以 apply 在 FOL。 那基本上是 complete 的。 那,不過我們要提一下它 complete 其實rotation of complete。 就是如果是不對的,它是可以說出不對的。 那我們先看一下 我們怎麼把,任何一個式子轉成 CNF。 其實很單純,那我們 [iii]它跟 [iii] 差不多只是有多了一些變數的問題,我們看一下怎麼處理。 譬如說我們這裡舉個例子 這個語義是說,任何人,他只要喜歡,所有的動物它都被某人所喜愛。 好那我們寫下這樣的邏輯式,把它寫成這樣,就是只要 ∀y,y 是個 animal。 然後, 就 imply,我們講 y for all 的話,你要用,你要配合這個 imply,那這個 x 就 喜歡 y,就是喜歡所有動物的這個人。 那對所有這樣的 x,這樣的人呢,都會存在 一個 y,這個 y 跟前面的 animal 當然就不一樣,存在存在一個人,相當於一個y,那個 y love x。 好這是我們上面的這個英文的邏輯式,用 CNF 給大家寫的翻譯。 好。 那第一件事情我們要先把,要變 CNF 的第一件事情就是要把這個 CNF 裡面沒有的這個 implication,或是你如果是雙箭頭。 如果你有雙箭頭的話就是先把它變成兩個單箭頭。 就是 A 和 B 全等就把它改寫成 A imply B,B imply A,好先把它改掉。 改的方法就是 A imply B 就改成 [iii]A or B。 ok。 那你改掉後的這個式子變這一句 那這一句的話接下來就是你要把 ﹃ 引進來,就是把 [iii]引進來,那 如果對,針對於他們的[iii],就是 for all 的話,你就 ﹃ for all 存在,﹃存在。 你就改成 for all。 那你就可以吧 ﹃ 引進來,這是我們之前就舉過這些例子了。 我們就可以看到,這邊就是你如果把 用這個把 ﹃ 引進來然後就變成一個 double negation,那 double negation 我們再同樣 apply 這個 double negation 的這個 rule。 就是雙重否定就等於肯定。 你們就可以把 ﹃ 都引進 [iii]的裡面,你自己再[iii]外面。 好經過這個第二個步驟以後,那是我就得到 [iii]本身,接下來我們要做的就是 [iii]那個 variable,因為我們 在處理 variable 要小心,我們剛剛有講過我們在原式裡面我們有兩個 y,第一個 y 是指某個 animal。 那第二個 y 指的是 someone,love,who loves x,所以這兩個 y 其實是不一樣的,那我們應該 應該把它分開。 我們又有新的一個,新的一個 variable z 好,那在處理變數的時候,我們接下來要是,就是套 u,uy 我們就是要留著,所以我們接下來 變數,希望處理到最後所有的變數都是 for all,那和我們[iii]需要處理。 那存在這個東西我們需要處理。 那存在我們是需要替換 Ey,但是當 這邊要換的是我們之前提過的 Skolem variable,但是如果你要配合上 另外一個變數的時候,其實我們所需要的是 Skolem function。 為什麼呢因為像這個地方對於 你如果 z 你用只替換一個[iii] 的話,那等於說你是說某一個固定的 人他[iii] 這樣的 x,那這是不對的語義嘛。 那我們在語義 的時候說熱愛動物的這樣人都會被某人所喜歡,那這個 不需要是同一個人就是針對不同的 x,他有一個相對應喜歡的 x 的這個人。 所以我們,我使用這個,我們稱為 Skolem function。 就是我們定的這個 G(x),就是會這樣 喜歡 x 的這一個人。 那同樣,這邊 animal 我們也是類似的做法。 好,就是被 x 所喜歡的 animal,好那我們就定為 F。 那這個 F 和 G 都是我們裡面都是大寫的。 當然指的就是常數。 好那接下來我們 Ei 已經搞定了麼,就 Ei 就是說我的 existence 我們就是全都把它換成 Skolem function 之後,那剩下的 variable 就是全都是 universally quantified for all。 那既然是 for all 我們就可以把所有的 for all 全部都抓捕掉。 好那我們就得到這一個式子。 好那現在就只剩下最後一步,就是我們要,已經要,既然在這個式子已經都所有的 ﹃ 都只,直接跟在 [iii]的前面,而且所有的 for all 和 iii 全部都已經被丟掉了,那隻剩下最後一步就是 end all,只要把它改成 CNF,那你就利用 交換結合這些分配率,你把它換回 CNF 的過程。 好那這個部分就跟 [iii] 提到的一模一樣。 好接下來,那這樣你就得到一個完整的 CNF 的一個邏輯式子。 那我們看一下 resolution 的,resolution 應用在 FOL 其實跟 [iii] 是一樣的。 就是一樣,就是,差別只是你用的是一個比較簡單的 resolution,就是你不是 existed complete,但是你是要找到 UNIFY 的使得這個 clause 裡面的[iii]可以是,互為反述就可以了。 那我們看一下用這個東西怎麼來證明,那個 [iii] 是有罪的怎麼來證明。 那我要證明他有罪首先你就是假設他無罪 那我們希望找到矛盾,那這個矛盾一定要是一個 [iii]。 在這種情況下,我們把它 highlight 出來,這個出題的其實就是可以被 UNIFY 的。 你要 UNIFY [iii],那你得到的結果 x 就是[iii]。 好那你得到 x 等於[iii]的時候,你就可以把這兩個拿掉,這兩個一起拿掉,那接下來這是你kb,那- 這是你知道的。 東西就是West American,那你這邊一樣,這兩個互為 Compliment就可以拿掉,那這邊的,你說y、 那它Weapon(y)跟Weapon(x),那你能做到就是x是y, 好是y的話就可以。 然後,接下來我們又可以,這個一樣,Missle(M1)跟 跟Missle(y),我可以只要y是M1,這兩個就可以拿掉,你依照這個步驟一直做下- 去,那你最後就可以得到, 得到一個Ø,那Ø的意思就是說原句就是整個KB ︿α, α是我們想要得到的結論,它是[iii]viable的,也就是代表了 KB entail α,好,也就等於說你只要得到這個Ø clause就代表了你已經證明了,呃,[iii] 是有罪的。 那他其實 resolution是蠻強力的一個證明法,它在propositional logic的時候,我們有說過它sound and complete, 呃,他的sound 當然還是一樣,就是沒有,沒有什麼變化,那他 在first order logic 裡面一樣是complete,但是這個我們通常會 會加一個名詞叫作refutational,就是refutational complete。 就是如果是拒絕的話, 是complete的。 原因當然很明顯,因為我們講過first order logic 裡面的entailment,它是semi-decidable 也就是說如果是yes,對,那你可以說, 對,但是,如果是no的話,你沒辦法在有限的時間內,知道它是no,這沒辦法。 這是已經被證明做不到的事情。 好,那,refutation complete的意思就是說,反正, 原句 KB ︿ α 它如果是unsatisfiable的話,那它是, 可以在有限的時間內跟你說,導出Ø clause。 那如果不是,也就是說如果,我不知道KB有沒有,如果原本KB其實不entail α的話,你要找到結論,那, resolution可以一直做,做不完,就這樣,而且沒辦法知道, 沒辦法知道結論,那這是沒有辦法的事。 好那它,呃,我們課本如果,對於resolution證明其實有簡單的描述,那它其- 實描述的 也就大致上就是這個樣子。 也就是說,其實它真正證明的重點就是,如果, 我有就這邊S當然就是,這邊S當然一樣,就是KB︿α, 如果我想要導入整個,整個sentence,它如果是 unsatisfiable的話,那,只要你在有限的 resolution的步驟內,你應該可以導得出, Ø clause,它證明的形式就是這樣子。 那這個其實,證明其實,呼應到之前我們提過,就是, 你在 propositionalize,我們在一個first order logic 的 knowledge base,我們可以做propositionalize 嘛,那其實是類似 的,如果,如果你可以entail α 的話,我可以在有限 的步驟內,就是你 propositionalize 可以到無窮大,但是又基本上又不需要,你在有限的一個subset 我就應該可以找到KB entail α,這是可以被證明的。 也就,這是呼應的,也就是說我在用resolution的過程中, 我只要apply有限,有限的步驟,應該就可以證明KB entail α。 那當然如果KB不entail α的話,那這是沒有辦法的事。 好,那,總結我們這一講,我們整個針對的就是在邏輯上我們把它推廣 從 propositional logic 我們推廣到first order logic的時候怎麼做,那first order logic可以 很容易描述現實生活中的所有問題,所以它的應用範圍非常廣。 那針對first order logic的話,首先,第一個, 如果你的懂面不大的話,也就是說你的,整個世界,已知的concern是不大的情況下, 你的確可以直接用UI還有EI把這些concern全部換完,然後你可以把一個first order logic的 knowledge base換成一個,propositional 的logic base,那我們之前在上一講,所提到,說forward-chaining, backward-chaining以及,resolution都可以直接apply。 那如果不行的話,如果你懂的面非常大的話,那這樣做會很沒效率。 那我們就可以用first order logic的做法:那首先有一個概念就是unification,那unifica- tion 做的事就是,找到一個正確的substitution,使得左邊等於右邊。 好,那,如果你,我們只, focus在first order logic的一個比較小的subset,就是definite clause的話,那我們可以直接用,generalized Modus Ponens 那這裡面就是,給前提得到結論嘛,那我們一樣可以使用forward-chaining- ,backward-chaining的技術。 那,generalized Modus Ponens基本上complete的,當然也上那個complete在definite clause上面。 那,那當然entailment本身它是semi-decidable的,那我們有提- 過,那, 在,如果你是一個Datalog,就是如果你沒有function,沒有functio- n的definite clause的話,那, 其實在P-time也是可以搞定的,那我們,因為提過嘛,就是你要無窮的,一直,你會,- 一直沒辦法, 決定下來,是因為你有function的情況下,你function可以無窮地,一直套- 上去,譬如說這樣的,發展的發展的發的 使得你的 object 有無窮多個。 所以你沒辦法在有限的時間內套完。 但是你如果沒有function的時候,就沒有這樣的問題的, object 其實能替換的,有限。 那,呃,所以你在P-time裡面可以做完。 好,那backward chaining呢,在logic program裡面會常被用的,譬如說像 [iii]system裡面它基本上, 呃,是,可以蠻快的。 它為了效率,那它, 沒有去省略accurate check,所以它的導入結論可能unsound,那因為用DFS 是記憶體,所以它的導入結論也可能是incomplete。 但是即使,它可能是unsound又complete的,但是它在大部分我們所需要、 所使用的, 問題上,大部分都可以work得不錯,好這是,那效率非常非常好。 那這是一個[iii],一些犧牲 一些正確性。 有些時候會給你不正確,但是得到很大部分的效能的提升。 那最後就是,如果, 你如果沒有那麼care效能的話,那你可以使用resolution,那其實上的又是c- omplete,那在 first order logic, 那當然要做一件事情,你要先把你的knowledge base換成整個 [iii] normal form,那之後我們就可以用resolution把它證完。 那以上是這一整講的內容。 以上我們AI的課程到此告一段落,謝謝各位同學的參與。 課程中我們簡單介紹了,有關 search還有logic上的技巧,而人工智慧裡面還有很多其他部分,由其他,與 新倫理有密不可分的關係。 那相關的內容,大家可以參考課本、 網路,或是自行到 coursera上搜尋相關課程,做 進一步的學習。 而大家如果對本課程有任何的想法與建議,歡迎大家在coursera的討論區提出,和我- 們分享,謝謝。 [音樂] [音樂] [音樂]