人工智能人工智能17-28

1、第17章 基于知識的系統(tǒng) 面對現(xiàn)實世界 用Horn子句進行推理 動態(tài)知識庫的維持 基于規(guī)則的專家系統(tǒng) 規(guī)則學習 補充讀物和討論17.1 面對現(xiàn)實世界 邏輯推理系統(tǒng)有三個主要的理論特性：合理性、完備性和易處理 性。為了確信一個推導的結(jié)論是真的，需要合理性。為了確信推論最終將產(chǎn)生真的推論，需要完備性。為了確信推論是可行的， 需要易處理性。 關于謂詞演算，歸結(jié)反駁是合理的和完備的。歸結(jié)反駁能被用來證明，如果一個合式公式被一個合式公式集邏輯涵蘊，那么它是完備的；否則，歸結(jié)反駁過程可能永不能終止。因此，我們不能用歸結(jié)作為一個完全的決策過程（decision procedure）。 可以證明沒有其他方法總

2、能告訴我們什么時候一個合式公式不是由合式公式集合邏輯地派生，什么時候是。因此，我們說謂詞演算是不完全決策的。當然，不完全決策性導致了謂詞演算固有的不易于處理性。 即使對那些歸結(jié)反駁終止的問題，那個過程是NP難題就像對一階謂詞演算的任何合理和完備推理過程一樣。雖然有很多推理問題能被公式化為歸結(jié)反駁問題，但對非常大的問題，該方法是不易處理的，這個事實導致很多人對在大規(guī)模推理問題中使用正式的邏輯方法感到失望。 然而，由于人類進行復雜推理，一定有啟發(fā)性的和特定的公式允許易處理的計算。 第一，我們能在堅持推理規(guī)則的合理性前，使用那些偶爾會“證明”一個不正確的公式過程。 第二，在堅持完備性前，使用不能保證

3、找到正確公式證據(jù)的過程。 這兩種修改可以使推理更有效。 第三，我們能使用一種比完全謂詞演算表達力弱的語言。 一個表達力弱的語言的例子僅僅使用了Horn子句。使用Horn子 句的推理典型地講更有效，它們可以滿足很多應用。17.2 用Horn子句進行推理 Horn子句定義為至多有一個正文字的子句。如果有至少一個負文字和一個正文字，Horn子句就能被寫為一個蘊涵，它的前項是正文字的合取，它的后項是單個正文字，這樣的子句被稱為一個規(guī) 則。h :- b1, bn 在子句中可以沒有負文字，在這種情況下，我們把它記為一個蘊含，它的前項為空，后項是一個單一正文字，這樣的子句被叫做一個事實。h :- 或者在子句

4、中可能沒有正文字，在這種情況下，我們記作后項為 空，前項是一個正文字列表的蘊含，這樣的子句稱為一個目標。:- b1, bn 在PROLOG語言中，這些子句用作該語言的語句，寫成如下格式： 規(guī)則： h :- b1, bn這是表示蘊含b1, bn h 的一種特殊形式，每個i是一個正文字。文字h叫做子句的頭，文字b1, bn叫做子句的體。事實： h :-目標：:- b1, bn 目標和規(guī)則體中的文字是有序列表，這個順序在一個PROLOG語言的執(zhí)行中起到重要的作用 在方框中的節(jié)點集對應程序語句（目標、規(guī)則及事實）。節(jié)點用程序中的文字標識。有兩種?。浩ヅ浠『鸵?guī)則弧。匹配弧把一個規(guī)則（或一個目標節(jié)點）的一

5、個體節(jié)點連向一個等價的另一個規(guī)則的標識頭節(jié)點（或到一個事實）。 在“與或”證明樹中，體節(jié)點被稱為AND節(jié)點，因為它們必須被全部證明。 如果有另一個可能的歸結(jié)，通過一個匹配弧對一個證明樹的搜索會產(chǎn)生另外的節(jié)點，稱為OR節(jié)點。 這些PROLOG程序說明了如何將Horn子句規(guī)則用于推理問題。在PROLOG語言中，推理“向后”進行，從要建立的目標開始，順 著規(guī)則鏈，最后錨定在事實上。與歸結(jié)反駁類似 使用目標規(guī)則和事實執(zhí)行這類向后推理的AI系統(tǒng)被稱為執(zhí)行反向鏈。也可用正向鏈，在這種情況下，推理向前進行，從事實開始， 順著規(guī)則鏈，最后產(chǎn)生目標。 有一種計算機語言OPS5是基于正向鏈的。已經(jīng)用OPS5寫出了

6、幾個實際有效的推理系統(tǒng)。 在正向鏈系統(tǒng)中，如果一個規(guī)則的前項文字的每一個都能與一個 相應的事實（用一致的置換）合一，那么它是可應用的。由于事 實是基本原子，變量僅出現(xiàn)在可被合一的一對表達式中。這種受 限的合一形式常叫做模式匹配。 當可應用多于一個規(guī)則時，某些外部沖突歸結(jié)被用來決定將應用 哪個規(guī)則。 當有大量的規(guī)則和事實時，必須被嘗試的合一數(shù)量成為障礙。OPS5使用一個叫RETE的算法過程。17.3 動態(tài)知識庫的維持 我們能延伸擴展行以包含任何數(shù)量的前提和規(guī)則，這樣一個結(jié)構(gòu) 可作為一種動態(tài)知識庫。推理過程被機制化，與顯示的單元值無關。 考慮一個命題演算原子知識庫。用原子“前提”（premiss）

7、代替事實，因為我們想能夠推理各種“假設分析”的可能性。 一個規(guī)則的正向推理鏈允許我們把R和S作為新原子加到KB中?？紤]到這個知識庫的方式之一是它像一個只有一行和幾列的一維電子表格，我們稱之為一個“擴展行” 它們能用來回答“假設分析”問題。某一個人（或一個agent）可能想知道，如果前提在一定的方式下改變，各種原子值將怎么改變。在AI中，這種擴展行叫做推理維持系統(tǒng)（reason maintenance）。它們和后面要討論的結(jié)構(gòu)是所謂的真值維持系統(tǒng)(TMS)的實例。17.4 基于規(guī)則的專家系統(tǒng) 使用事實和規(guī)則的AI推理技術的最成功的應用之一是建立專家系統(tǒng)，專家系統(tǒng)包含了人類努力探索的一個專門領域的

8、知識，如醫(yī)療、工程和商業(yè)。 嚴格地講，任何具有專家功能的程序都被稱為是一個專家系統(tǒng)。 在解決問題中，通過運用知識體達到專家級水平的AI程序叫做知識庫系統(tǒng)或?qū)＜蚁到y(tǒng)。經(jīng)常，術語“專家系統(tǒng)”被約定用于知識庫中包含人類專家使用的知識而不是從課本或非專家那里收集來的知識的程序。 兩個術語專家系統(tǒng)和知識庫系統(tǒng)更經(jīng)常被同義使用。 在本書中，主要討論基于規(guī)則的專家系統(tǒng)。 主要部分是知識庫和推理引擎。知識庫由謂詞演算事實和有關討論主題的規(guī)則構(gòu)成。推理引擎由所有操縱知識庫來演繹用戶要求的信息的過程構(gòu)成如歸結(jié)、前向鏈和反向鏈。 用戶接口包括某些自然語言處理系統(tǒng)，它允許用戶用一個有限的自然語言形式與系統(tǒng)交互。也可使

9、用帶有菜單的圖形接口界面。解釋子系統(tǒng)分析被系統(tǒng)執(zhí)行的推理機構(gòu)，并把它解釋給用戶。知識采集子系統(tǒng)用戶接口專家用戶解釋子系統(tǒng)知識庫、事實或啟發(fā)式推理引擎 知識工程師一個專家系統(tǒng)的基本結(jié)構(gòu)17.5 規(guī)則學習 有兩種類型的學習方法，歸納法和演繹法。兩 種類型都能用于學習規(guī)則。例如，神經(jīng)網(wǎng)絡學 習就是歸納法，因為學習的函數(shù)是對潛在的、未知的函數(shù)的假設。 演繹規(guī)則學習通過從以前知道的領域規(guī)則和事 實推理附加的規(guī)則來擴展一個系統(tǒng)的性能效率。不用附加規(guī)則，系統(tǒng)也能推出使用附加規(guī)則推 出的結(jié)論。但是使用附加規(guī)則，系統(tǒng)可以更有 效地學習。對演繹附加規(guī)則，將解釋一個基于 解釋的廣義化（EBG）技術。17.5.1 學

10、習命題演算規(guī)則 從訓練集中，我們希望歸納出如下規(guī)則：1 2 n OK 其中i是集合APP, RATING, INC, BAL中的命題原子。如果一規(guī)則的前項在訓練集中有T 值，我們就說那個規(guī)則覆蓋（cover）那個實例。我們通過給規(guī)則的前項加一個原子來改變 任何現(xiàn)存的規(guī)則，使之覆蓋更少的實例。此改 變使那個規(guī)則更特殊。兩個規(guī)則比單個規(guī)則能 覆蓋更多的實例。增加一個規(guī)則使得使用這些規(guī)則的系統(tǒng)更為通用。 我們尋找一個規(guī)則集合，它僅能覆蓋訓練集中的所有正實例。對于一個規(guī)則集合的搜索在計算上是困難的。 這里描述了一個“ ”方法，又稱為分治法（separate and conquer）。首先設法找到一個規(guī)

11、則，它僅僅覆蓋正例盡管它不覆蓋所有的正例。 首先從覆蓋所有實例的臨時規(guī)則T OK 現(xiàn)在，必須加一個原子使它包含較少的反例。 有幾個標準可用來做這個選擇。為簡單起見， 決定一個易于計算的比率ra=na+/na 其中na是將a原子加到規(guī)則的前項后，被新的前項覆蓋的（正的和反的）實例的總和。 na+ 是將a原子加到規(guī)則的前項后，被新的前項覆蓋的正例的總量。 我們將選擇產(chǎn)生最大ra值的a值。選BAL， 產(chǎn)生如下規(guī)則： BAL OK 該規(guī)則覆蓋了正例，也覆蓋了反例，因此必須把它進一步特殊化。用同樣的技術選擇另一個原子。 規(guī)則BAL RATING OK僅覆蓋正例， 故不必在加原子到這個規(guī)則的前項。但是這個

12、規(guī)則沒有覆蓋所有的正例，尤其它不覆蓋正例6，因此，我們必須增加另一個規(guī)則。 為了學習下一個規(guī)則，首先從表中刪去被第一個規(guī)則覆蓋的所有正例。從這個精簡的表開始，重復上述的所有過程。 對學到的規(guī)則和專家給出的規(guī)則進行比較，揭示了學到的規(guī)則不會提到專家沒有估量或問到的任何謂詞，他們沒有被數(shù)據(jù)中的特征表示。中間謂詞通過封裝更原始謂詞的一般出現(xiàn)組簡化了知識表示和推理。 學習這些中間謂詞是一個重要的研究課題。關于“謂詞發(fā)明”已經(jīng)作了一些初步的工作。17.5.2 學習一階邏輯規(guī)則 雖然許多專家系統(tǒng)建立在命題邏輯的基礎上，但是更全面的專家系統(tǒng)是通過使用量化變量的規(guī)則而得到的。 歸納邏輯編程（ILP）的子領域集

13、中于FOPC中Horn子句的歸納學習算法。17.5.3 基于解釋的一般化 現(xiàn)在轉(zhuǎn)向演繹學習，一種從以前的規(guī)則和事實推導規(guī)則的方法。用一個積木世界的例子解釋這個方法。假定關于這個世界的一般知識包括下述規(guī)則：Green(x) Heavy(x) Heavy(x) Pushable (x)關于這個世界的事實之一是：Green(A)假定要出我們證明Pushable (A)。 把常量用變量代替使解釋一般化，產(chǎn)生Green(x)。這個過程的結(jié)果，即我們稱為基于解釋的一般化（EBG）的結(jié)果是生成規(guī)則。 在執(zhí)行EBG的過程中，我們假定一般規(guī)則對其他相似的情況也是有用的，因此值得推導和保存。當然，更多的規(guī)則會隨著分枝因子的增加而