1、Artificial Intelligence第二章知識表示Knowledge Representation1內容提要2.6 狀態空間2.7 面向對象的知識表示2.8 劇本2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/162什么是知識數據一般指單獨的事實，是信息的載體，數據項本身沒有什么意義，除非在一定的上下文中，否則沒有什么用處。信息由符號組成，如文字和數字，但是對符號賦予了一定的意義，因此有一定的用途或價值。知識也是由符號組成，但是還包括了符號之間的關系以及處理這些符號的規則或過程。知識在信息的基礎上增加了上下文信息，提供

2、了更多的意義因此也就更加有用和有價值。知識是隨著時間的變化而動態變化的，新的知識可以根據規則和已有的知識推導出來。 2022/7/163什么是知識因此可以認為知識是經過加工的信息（Feigenbaum），它包括事實、信念和啟發式規則（Hayes-Roth）。關于知識的研究稱為認識論（Epistemology），它涉及知識的本質、結構和起源。 2022/7/164知識的特性相對正確性在一定的條件及環境下，知識一般是正確的，可信任的不確定性由隨機性引起的不確定性由模糊性引起的不確定性由不完全性引起的不確定性由經驗性引起的不確定性可表示性和可利用性知識是可以表示出來的知識是可以利用的2022/7/1

3、65知識表示知識表示就是研究用機器表示知識的可行性、有效性的一般方法，可以看作是將知識符號化并輸入到計算機的過程和方法。知識表示在智能系統的建造中起到關鍵的作用。可以說正是以適當的方法表示了知識，才導致智能系統展示出了智能行為。 2022/7/166知識類型知識類型有三種：陳述性知識：也稱為描述性知識，是描述客觀事物的特點及其關系的知識。陳述性知識主要包括三個層次：符號表征、概念、命題。過程性知識：也稱為程序性知識，是關于問題求解的操作步驟和過程的知識。這類知識主要用來解決“做什么”和“如何做”的問題，可用來進行操作和實踐。控制性知識：也稱為元知識、控制策略，是有關各種處理過程的策略和結構的知

4、識，用于選擇問題求解的方法和技巧，協調整個問題求解的過程。2022/7/167知識表示方法的要求充分表示領域知識:首先考慮能不能充分表示領域知識.要能反應出領域的特點有利于知識的利用:表示的目的是為了利用知識,求解問題便于對知識的組織,維護和管理:便于今后的更新,維護,保證其一致性和完整性便于理解和實現:容易讓人理解并符合人的習慣.還有容易在計算機上實現2022/7/168內容提要2.6 狀態空間2.7 面向對象的知識表示2.8 劇本2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/169謂詞邏輯法邏輯在知識的形式化表示和機器自動

5、定理證明方面發揮了重要的作用，其中最常用的邏輯是謂詞邏輯，命題邏輯可以看做謂詞邏輯的一種特殊形式。謂詞邏輯嚴格地按照相關領域的特定規則，以符號串形式描述該領域有關客體的表達式能夠把邏輯論證符號化，并用于證明定理，求解問題。2022/7/1610謂詞演算語法與語義基本符號：謂詞符號、變量符號、函數符號、 常量符號、括號和逗號謂詞演算的解釋：謂詞符號對應關系，常量符號論域實體，函數符號對應函數；原子公式：由若干謂詞符號和項組成的謂詞演算。原子公式是謂詞演算基本積木塊。項包括常量符號、變量符號、函數符號等。定義原子公式為真值或假值就表示了某種語義。無變量的原子公式取值確定，包含變量的原子公式取值不定

6、。2022/7/1611連詞與、合取（conjunction)：用連詞把幾個公式連接起來而構成的公式。合取項是合取式的每個組成部分。 例：LIKE(I，MUSIC)LIKE(I，PAINTING) （我喜愛音樂和繪畫。）或、析取（disjunction）：用連詞把幾個公式連接起來而構成的公式。析取項是析取式的每個組成部分例：PLAYS(LILI，BASKETBALL)PLAYS(LILI，FOOTBALL) （李力打籃球或踢足球。）蘊涵（Implication）:“=”表示“如果那么”（IFTHEN）關系，其所構成的公式叫做蘊涵。非（Not）表示否定，、均可表示謂詞演算2022/7/1612量

7、詞 若一個原子公式P（x），對于所有可能變量 x都具有T值，則用 （ x）P（x）表示例如: 所有的機器人都是灰色的（ x ） ROBOT(x) = COLOR(x,GRAY) 存在量詞（Existential Quantifier） 若一個原子公式P（x），至少有一個變元x，可使P （x）為T值，則用（ x）P（x）表示。 例：(x)INROOM(x,r1)（1號房間內有個物體）謂詞演算全稱量詞（Universal Quantifier）2022/7/1613謂詞公式原子公式的的定義： 用P(x1，x2，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,，xn為客體變量或變元。通常把

8、P(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。謂詞公式 可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做謂詞公式。謂詞演算2022/7/1614合式公式（WFF，well-formed formulas）合式公式的遞歸定義(1)原子謂詞公式是合式公式。(2)若A為合適公式，則A也是一個合式公式。(3)若A和B都是合式公式，則(AB)，(AB)，(AB)和(AB)也都是合式公式。(4)若A是合式公式，x為A中的自由變元，則(x)A和(x)A都是合式公式。(5)只有按上述規則(1)至(4)求得的那些公式，才是合式公式。例題：試把下列命題表示為謂詞公式：任何整數，或者為整數或者為

9、負數。謂詞演算2022/7/1615合式公式的性質合式公式的真值表等價（Equivalence) 如果兩個合式公式，無論如何解釋，其真值表都是相同的，那么我們就稱此兩合式公式是等價的。T F T F F FP Q PQ P Q PQ PT T T T T FF T T F T TF F F F T T謂詞演算2022/7/1616謂詞邏輯的推理將推理規則應用于一定的合式公式（集），以產生新的合式公式。置換(Substitution) ：在表達式中用置換項置換變量，例如用項（A）替換函數表達式中的變量（x）。一個表達式E（Expression）用一個置換S（Substitution）而得到的表達

10、式的置換，記為ES。 例題：表達式E：Px,f(y),B；置換：s1=z/x,w/y,s2=A/y, s3=q(z)/x,A/y,s4=c/x,A/y Solution:ES1 = Pz,f(w),B; ES2 = Px,f(A),B;ES3 = Pq(z),f(A),B; ES4 = Pc,f(A),B; ES1S2 = Pz,f(w),B; ES2S1 = Pz,f(A),B 2022/7/1617合一（Unification)：合一：尋找項對變量的置換，以使多個表達式一致的操作稱為合一。如果一個置換s作用于表達式集Ei的每個元素，則我們用Ei s來表示置換例的集。可合一：如果存在置換s使

11、得表達式集Ei置換后有：E1S E2S E3S,則我們稱表達式集Ei是可合一的， s 稱為Ei 的合一者。 例題：表達式集Px,f(y),B,Px,f(B),B 的合一者：s A/x,B/y 說明： Px,f(y),Bs Px,f(B),Bs PA,f(B),B謂詞邏輯的推理2022/7/1618最通用的合一者：如果對表達式集Ei的任一合一者s，都存在某一s，使得Eis Eigs，則稱g為Ei的最通用合一者。置換與合一的作用：謂詞邏輯推理的基本方法，就是尋找簡單有效置換合一，采用消解原理利用消解反演方法求解問題。謂詞邏輯的推理2022/7/1619內容提要2.6 狀態空間2.7 面向對象的知識

12、表示2.8 劇本2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/1620產生式系統產生式系統 (production system)的概念，最早是由帕斯特（Post E）于1943年提出的產生式規則得來的。他用這種規則對符號串作替換運算。1965年美國的紐厄爾和西蒙利用這種原理建立了人類的認知模型。同年，斯坦福大學設計第一個專家系統 DENDRAL時，就采用產生式系統的結構。產生式系統是目前已建立的專家系統中知識表示的主要手段之一，如 MYCIN、CLIPS/JESS系統等。在產生式系統中，把推理和行為的過程用產生式規則表示，所

13、以又稱基于規則的系統。2022/7/1621產生式系統的基本結構產生式規則 條件 行動前提 結論“if P then Q” 注意：P和Q不一定總是用謂詞表示謂詞邏輯中的蘊含式和產生式基本形式相同蘊含式是產生式的一種特殊情況蘊涵式知識產生式規則的特殊形式 2022/7/1622產生式系統的基本結構解釋器沖突集/沖突消解器工作區規則庫匹配器2022/7/1623產生式系統的基本結構工作區 綜合數據庫是用于存放問題求解過程中各種當前信息的數據結構,包括原有信息,中間結果,最終結果等.規則的激活:當規則庫中某條產生式的前提可與綜合數據庫中的某些已知事實匹配時,該產生式就被激活綜合數據庫是不斷更新和變化

14、的,是動態的綜合數據庫也稱為：上下文、黑板、工作區等2022/7/1624產生式系統的基本結構控制子系統 控制子系統負責整個產生式系統的運行匹配器判斷規則條件是否成立，沖突消解器負責選擇可調用的規則，解釋器負責執行規則的動作，并在滿足結束條件時終止產生式系統的運行。 具體有：匹配規則條件部分；多于一條規則匹配成功時，選擇哪條規則執行(點燃)；如何將匹配規則的結論部分放入綜合數據庫（是直接添加到數據庫中，還是替換其中的某些東西）；決定系統何時終止；2022/7/1625產生式系統的基本結構識別-動作循環 （1）從規則庫中尋找所有能夠和工作區中已有事實相匹配的規則，并將這些規則加入到沖突集中（2）

15、若有多個規則存在，則根據沖突消解策略由沖突集中選擇一條規則執行。（3）執行規則中的動作，根據動作向工作區中加入新的事實或刪除舊的事實。2022/7/1626例1八數碼游戲(eight puzzle)23751486123847652022/7/1627例1游戲說明：一個棋盤有9個方格，放了8個數（1-8）；初始時，8個數隨機放置；數字移動規則：空格周圍的數字可移動到空格中；如果通過移動數字，達到一個目標狀態，則游戲成功結束；求一個走步序列;問題：怎樣用一個產生式系統描述并解決上述問題？2022/7/1628例1產生式系統的描述:綜合數據庫：存放棋盤的狀態。棋盤的狀態：8個數字在棋盤上的位置分布

16、。每走一步，狀態就會發生變化；存放棋盤的當前狀態；規則：規則是數字移動的方法。空格的移動:如果空格左邊有數字，則將左邊的數字移到空格上；如果空格右邊有數字，則將右邊的數字移到空格上；如果空格上邊有數字，則將上邊的數字移到空格上；如果空格下邊有數字，則將下邊的數字移到空格上；2022/7/1629例2問題：設字符轉換規則ABCACDBCGBEFDE已知：A，B求：F2022/7/1630一、綜合數據庫x，其中x為字符二、規則集1，IF AB THEN C2，IF AC THEN D3，IF BC THEN G4，IF BE THEN F5，IF D THEN E例22022/7/1631三、控制

17、策略順序排隊四、初始條件A，B五、結束條件Fx例22022/7/1632產生式系統的推理正向推理:從已知事實出發,通過規則庫求得結論.也稱為數據驅動方式,或從底向上的方式反向推理:從目標出發.反向使用規則,求得已知事實,或稱目標驅動,自頂向下.雙向推理:既自頂向下,又自底向上相結合得方法.直至某個中間界面兩方向結果相符便成功結束.2022/7/1633正向推理推理過程正向推理推理過程(1)規則庫中的規則與數據庫中的事實進行匹配,得到匹配成功的規則集合(2)從匹配規則集中選擇一條規則作為使用規則(3)執行使用規則的后件,將該規則的后件送入數據庫.重復上述過程直到達到目標2022/7/1634反向

18、推理推理過程反向推理推理過程(1)規則集合中的規則后件與目標事實進行匹配,得到匹配的規則集合(2)從匹配規則集合中選擇一條規則作為使用規則(3)將使用規則的前件作為子目標 重復上述過程,直到各子目標均為已知事實成功結束2022/7/1635產生式系統的特點優點(1)自然性(2)模塊性(3)有效性既可表示確定性知識,又可表示非確定性知識,既可表示啟發式知識,又可表示過程性知識(4)清晰性:格式固定,結構簡單,便于一致性,完整性檢查不足之處效率不高:匹配-沖突消解-執行,并且可能產生組合爆炸不能表達具有結構性的知識2022/7/1636內容提要2.6 狀態空間2.7 面向對象的知識表示2.8 劇本

19、2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/1637語義網絡基本概念語義網絡是通過概念及其語義關系來表達知識的一種網絡圖,是一種“帶標識”的有向圖.節點表示各種事物,概念,情況,屬性,動作,狀態等.弧表示各種語義關系(節點1 , 弧, 節點2)也可表示為: 當把多個基本的網絡通過相應的語義關聯在一起時,就得到一個語義網絡ABR2022/7/1638常用的語義聯系ISA,AKO,Part-of,Infer等A-Member-of:表示個體與集體之間的關系.Composed-of: 表示“構成”聯系,是一種一對多的聯系Have:

20、 表示屬性或事物的“占用”關系.如鳥有翅膀Before, After, At: 表示事物之間的時間先后順序Located-on(-at,-under,-inside,outside):表示事物之間的位置關系Similar-to,Near-to:表示事物之間的相似或接近的關系2022/7/1639(1) 能把實體的結構、屬性與實體間的因果關系顯式并簡明地表達出來 , 與實體相關的事實、特征和關系可以通過相應的節點弧線推導出來。這樣便以聯想方式實現對系統 的解釋。(2) 由于與概念相關的屬性和聯系被組織在一個相應的節點中 , 因而使概念易于受訪和學習。(3 ）表現問題更加直觀 , 更易于理解 ,

21、適于知識工程師與領域專家的溝通。語義網絡中的繼承方式也符合人類的思維習慣。(4) 語義網絡結構的語義解釋依賴于該結構的推理過程而沒有結構的約定 , 因而得到的推理不能保證像謂詞邏輯法那樣有效。(5 ）節點間的聯系可能是線狀、樹狀或網狀的 , 甚至是遞歸狀的結構 , 使相應的知識存儲和檢索可能需要比較復雜的過程。 語義網絡的特點2022/7/1640表示一些簡單事實，如占有關系和其它情況：以節點表示實體與概念，節點間關系以有向鏈關聯。例： 小燕是一只燕子，燕子是一種鳥，鳥有翅膀；巢-1是小燕的巢，巢-1是巢中的一個。問題：上述的語義網絡為二元關系，無法表示復雜事實，如：小燕從春天到秋天占有巢1。

22、如果采用謂詞邏輯表示為一個四元謂詞演算：Owns（XIAOYAN,NET-1,SPRING,FALL）二元語義網絡的表示SWALLOWBIRDXIAOYANNEST-1NESTISAISAISAOWNSHAS-PARTWINGS2022/7/1641 - 允許節點既可以表示一個物體或一組物體，也可以表示情況與動作。每一情況節點成為事例框，有一組向外的弧，用以說明與該事例有關的各種變量。SWALLOWBIRDXIAOYANNEST-1NESTISAISAISAOWNEEOWN-1OWNERSPRINGFALLSITUATIONTIMEOWNERSHIPISAISAISAISASTARTTIMEE

23、NDTIMESimmons與Slocum的擴展2022/7/1642問題：如果語義網絡只表示一個特定的物體或概念，那么當有更多不直接相關的同類實體與概念時，需要很多獨立的語義網絡，使得語義網絡圖復雜化。Solution：通常需要把有關的一組物體或概念的知識用一個語義網絡表示出來，否則會造成網絡過多，使問題復雜化。試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復雜的知識，稱為選擇語義基元。REDMYCARCOLORGREENLIHUACARCOLOR選擇語義基元2022/7/1643FURNITURECHAIRMYCARLEATHERSEATBROWNPERSONXISAOWN

24、ERISAISAISA PARTCOLORCOVERING椅子的語義網絡2022/7/1644語義網絡的推理過程語義網絡表示知識，沒有形式語義，沒有統一的語義表示法。為了便于下面的敘述 , 對所用符號作進一步的規定。區分在鏈的頭部和在鏈的尾部的節點 , 把在鏈的尾部的節點稱為值節點。另外 , 還規定節點的槽相當于鏈 , 不過取不同的名字而已。如磚塊12(BRICK12)有3個鏈,構成兩個槽。其中一個槽只有一個值,另外一個槽有兩個值。顏色槽(COLOR)填入紅色(RED) ISA槽填入了磚塊 (BRICK)和玩具(TOY) 。2022/7/1645所謂繼承就是對事物的描述從概念節點或類節點傳遞到

25、實例節點，例如下圖。語義網絡的繼承推理2022/7/1646三種繼承模式值繼承：ISA鏈與 AKO（A Kind Of）鏈，常用知識傳遞方法；放入值側面中。“如果需要”（Ifneeded）鏈：有時對不知道的槽值，可以計算得到，通過此計算程序得到知識的模式稱為ifneeded鏈，如通過體積與密度在需要時可以計算其質量。 ifneeded程序放入IFNEEDED側面中。“缺省”繼承：在對事務所作假設無十分把握時，可以加上“可能”字樣，這種不肯定的值稱為“缺省”值，放入槽的DEFAULT側面中。語義網絡的繼承推理2022/7/1647當解決涉及由幾部分組成的事物時 ,必須制定把值從類部件傳遞到實例部

26、件的路徑，稱為匹配推理。 例如, 由于 TOY-HOUSE77 是 TOY-HOUSE 的一個實例 , 所以它必須有兩個部件 , 一個是磚塊 , 另一個是模塊 (wedge) 。另外 , 作為玩具房的一個部件的磚塊必須 支撐模塊。在下圖中 , 玩具房 -77 部件以及它們之間的鏈 , 都用虛線畫的節點和箭頭 來表示。因為這些知識是通過繼承而間接知道的 , 并不是通過實際的節點和鏈直接知道 的。因此 , 虛線所表示的節點以及箭頭所表示的鏈是虛節點和虛鏈。語義網絡的匹配推理2022/7/1648內容提要2.6 狀態空間2.7 面向對象的知識表示2.8 劇本2.9 本體2.10 小結2.1 概述2.

27、2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/1649框架表示框架：框架是一種結構化表示法，通常采用語義網絡中的節點-槽-值表示結構，以通用數據結構的形式存儲以往的經驗知識。框架與語義網絡的關系：框架可以定義為一組語義網絡的節點與槽，這組節點與槽可以描述格式固定的事務、行為和事件；語義網絡是節點和弧線的集合，也可以看作框架的集合。思考：框架與語義網絡的區別？2022/7/1650框架的構成框架通常由描述事務的各個方面的槽組成，每個槽可以擁有若干個側面，而每個側面可以擁有若干個值。框架的一般結構： 2022/7/1651賓館房間的框架描述2022/7/1652框架系統的

28、基本推理方法特性繼承，例如：燕子鳥部分匹配，例如TOYHOUSE從描述中直接引用，例如：ROOM的例子各槽值的相關信息可以指導進行該槽值的描述，思考：框架是一種規定格式描述的事務、行為與事件。那么對于具體的應用，當直接套用框架知識推理不順利時，框架推理的策略？框架的推理2022/7/1653選擇與當前情況對應的框架片斷，與其他候選框架相匹配，選擇最佳匹配；（知識的合成、交叉）允許部分不相匹配的信息，如漏失某項特性比多了某項特性更合理，比如只有一條腿的人比有三條腿的人更合理；（合理推斷）查詢框架之間保存有關的連接，指出應用此框架不合理的情況下，可以下一步試探的建議框架；沿著框架系統的層次向上搜索

29、，知道找到足夠通用、與事實不矛盾的框架，或直接使用，或者建立新的下一層框架。（類型匹配與新類生成）框架推理的選擇方法2022/7/1654內容提要2.6 狀態空間2.7 面向對象的知識表示2.8 劇本2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/1655狀態空間表示問題求解技術主要是兩個方面：問題的表示求解的方法狀態空間法狀態（state）:表示問題解法中每一步問題狀況的數據結構算符（operator):把問題從一種狀態變換為另一種狀態的手段狀態空間方法:基于解答空間的問題表示和求解方法，它是以狀態和算符為基礎來表示和求解問題

30、的2022/7/1656問題狀態描述狀態(State)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。算符(Operate)：使問題從一種狀態變化為另一種狀態的手段稱為操作符或算符。問題的狀態空間(State Space)：是一個表示該問題全部可能狀態及其關系的圖，它包含三種說明的集合，即三元狀態（S，F，G）。2022/7/1657狀態空間法：從某個初始狀態開始，每次加一個操作符，遞增的建立起操作符的實驗序列，直到達到目標狀態止。例如下棋、迷宮及各種游戲。Original StateMiddleStateGoalState狀態空間描述2022/7/1658例:三數碼

31、難題123123123312312312初始棋局目標棋局2022/7/1659狀態空間也可以用一個賦值的有向圖來表示， 該有向圖稱為狀態空間圖。在狀態空間圖中包含了操作和狀態之間的轉換關系，節點表示問題的狀態，有向邊表示操作。路徑 某個節點序列（ni1，ni2，nik）當 j = 2，3，k時，如果對于每一個ni，j-1都有一個后繼節點ni，j存在，那么就把這個節點序列叫做從節點ni1至節點nik的長度為k的路徑代價 用c（ni，nj）來表示從節點ni指向節點nj的那段弧線的代價。兩點間路徑的代價等于連接該路徑上各節點的所有弧線代價之和.狀態空間圖2022/7/1660內容提要2.6 狀態空間

32、2.7 面向對象的知識表示2.8 腳本2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/1661認為世界由各種“對象”組成，每個對象類都定義了所謂“方法”（method），它們實際上可視為允許作用于該類對象上的各種操作。面向對象知識表示方法與框架表示方法有許多相似之處，如層次分類和特性繼承機制等。但由于應用目標不同，實現和使用方式有較大區別。框架表示法旨在支持知識的陳述性表示，強調事物的結構化描述和對人思維方式的模擬。面向對象表示法則強調信息的結構化處理，注重信息和信息處理的封裝和程序設計的模塊化。面向對象的知識表示2022/7/

33、1662內容提要2.6 狀態空間2.7 面向對象的知識表示2.8 劇本2.9 本體2.10 小結2.1 概述2.2 謂詞邏輯2.3 產生式系統2.4 語義網絡2.5 框架2022/7/1663劇本（Script）表示提問：框架中對事件的描述有什么不足？定義：劇本是框架的特殊形式，它用一組槽值描述事件發生的序列。劇本的構成：（1）開場條件 （事件發生的前提條件）（2）角色 （有關人物的槽值）（3）道具 （有關物體的槽值）（4）場景 （事件的順序，場景可以是其他劇本）（5）結果 （事件發生后的結果）2022/7/1664(1) 開場條件(a) 顧客餓了 , 需要進餐。 (b) 顧客有足夠的錢。(2) 角色： 顧客 , 服務員 , 廚師 , 老板。(3) 道具： 食品 , 桌子 , 菜單 , 錢。(4) 場景場景 l 進入餐廳 (a) 顧客走入餐廳 (b) 尋找桌子 (c) 在桌子旁坐下。場景 2 點菜 (a) 服務員給顧客菜單 (b) 顧客點菜 (c) 顧客把菜單還給服務員 (d) 顧客