人工智能_知識(shí)表示.ppt

1、第二章 知識(shí)表示,知識(shí)就是力量,2,第2章 知識(shí)表示,2.1 知識(shí)表示與知識(shí)表示的概念 2.2 一階謂詞邏輯表示法 2.3 產(chǎn)生式表示法 2.4 語(yǔ)義網(wǎng)絡(luò)表示法 2.5 框架表示法 2.6 狀態(tài)空間表示法 2.7 問(wèn)題規(guī)約表示法 2.8 劇本表示法 2.9 面向?qū)ο蟊硎痉?3,2.1.1 知識(shí)的概念-何謂知識(shí)（一）,知識(shí)的一般概念 知識(shí)是人們?cè)诟脑炜陀^世界的實(shí)踐中積累起來(lái)的認(rèn)識(shí)和經(jīng)驗(yàn) 認(rèn)識(shí)：包括對(duì)事物現(xiàn)象、本質(zhì)、屬性、狀態(tài)、關(guān)系、聯(lián)系和運(yùn)動(dòng)等的認(rèn)識(shí) 經(jīng)驗(yàn)：包括解決問(wèn)題的微觀方法，如步驟、操作、規(guī)則、過(guò)程、技巧等 宏觀方法，如戰(zhàn)略、戰(zhàn)術(shù)、計(jì)謀、策略等 知識(shí)、信息、數(shù)據(jù)及其關(guān)系 原因：認(rèn)識(shí)客觀世界

2、的前提是能對(duì)其描述，而描述由數(shù)據(jù)和信息來(lái)實(shí)現(xiàn)的 解釋：數(shù)據(jù)是為描述客觀事物而引入的一些數(shù)字、符號(hào)、文字等 信息是對(duì)客觀事物的一般性描述，它還不是知識(shí)。數(shù)據(jù)組成結(jié)構(gòu)。 關(guān)系：數(shù)據(jù)是信息的載體，本身無(wú)確切含義，其關(guān)聯(lián)構(gòu)成信息 信息是數(shù)據(jù)的關(guān)聯(lián)，賦予數(shù)據(jù)特定的含義，僅可理解為描述性知識(shí) 知識(shí)可以是對(duì)信息的關(guān)聯(lián)，也可以是對(duì)已有知識(shí)的再認(rèn)識(shí) 例如：(1) if 計(jì)算機(jī)能聽懂人類語(yǔ)言 then 可直接與計(jì)算機(jī)對(duì)話 (2) if 計(jì)算機(jī)能聽懂人類語(yǔ)言就可直接與計(jì)算機(jī)對(duì)話 then 人類將努力研究自然語(yǔ)言理解問(wèn)題,4,2.1.1 知識(shí)的概念-何謂知識(shí)（二）,“知識(shí)”有代表性的定義 （1）知識(shí)是經(jīng)過(guò)剪裁、塑造、

3、解釋、選擇和轉(zhuǎn)換了的信息 （2）知識(shí)由特定領(lǐng)域的描述、關(guān)系和過(guò)程組成 （3）知識(shí)=事實(shí)+信念+啟發(fā)式 “信息”與“關(guān)聯(lián)”是構(gòu)成知識(shí)的兩個(gè)要素。信息之間關(guān)聯(lián)的形式可以多種多樣，最常見的一種形式是： “如果。，則?！?5,2.1.1 知識(shí)的概念-知識(shí)的屬性,真假性與相對(duì)性 真假性：可以通過(guò)實(shí)踐和推理來(lái)證明知識(shí)是真的還是假的 相對(duì)性：非絕對(duì)性。知識(shí)的真與假是相對(duì)于條件、環(huán)境、事件而言的 不確定性 不完備性：解決問(wèn)題時(shí)不具備解決該問(wèn)題的全部知識(shí) 不精確性：知識(shí)本身有真假之分，但由于認(rèn)識(shí)水平限制說(shuō)不清其真假 這時(shí)可由可信度、概率等進(jìn)行描述。 模糊性：知識(shí)的邊界本身就是不清楚的(人的相貌) 用可能性、隸屬

4、度來(lái)描述（模糊搜索） 矛盾性和相容性 矛盾性：同一知識(shí)集中的知識(shí)之間相互對(duì)立或不一致（保健專家系統(tǒng)） 相容性：一個(gè)知識(shí)集中的所有知識(shí)之間相互不矛盾 可表示性與可利用性 可表示性：知識(shí)可用適當(dāng)?shù)男问奖硎境鰜?lái)。如語(yǔ)言、文字、圖形等 可利用性：知識(shí)可用來(lái)解決各種各樣的問(wèn)題,6,2.1.1 知識(shí)的概念-知識(shí)的類型（一）,按知識(shí)的性質(zhì) 概念、命題、公理、定理、規(guī)則和方法 按知識(shí)的作用域 常識(shí)性知識(shí)：通用通識(shí)的知識(shí)。人們普遍知道的、適應(yīng)所有領(lǐng)域的 領(lǐng)域性知識(shí)：面向某個(gè)具體專業(yè)領(lǐng)域的。該領(lǐng)域?qū)＜也胖赖?如：專家經(jīng)驗(yàn)。專家系統(tǒng)擁有的是此類知識(shí) 按知識(shí)的作用效果 事實(shí)性知識(shí)：（敘述性知識(shí)）描述事物的概念、定義

5、、屬性等 （神5實(shí)現(xiàn)了中華民族的飛天夢(mèng)想） 問(wèn)題的狀態(tài)、環(huán)境、條件等（氣溫逐漸下降） 過(guò)程性知識(shí)：用于問(wèn)題求解過(guò)程的操作、演算和行為的知識(shí) 用來(lái)指出如何使用那些與問(wèn)題有關(guān)的事實(shí)性知識(shí)的知識(shí) 由與求解問(wèn)題有關(guān)的規(guī)則、定律、定理及經(jīng)驗(yàn)所構(gòu)成 例如：AX2+BX+C=0 控制性知識(shí)：即元知識(shí)或超知識(shí) 如何使用知識(shí)的知識(shí)，也稱為關(guān)于知識(shí)的知識(shí)。 例如：推理策略、搜索策略(深度優(yōu)先、廣度優(yōu)先、啟發(fā)式) 不確定性的傳播策略,7,2.1.1 知識(shí)的概念-知識(shí)的類型（二）,按知識(shí)的層次 表層知識(shí)：客觀事物的現(xiàn)象及這些現(xiàn)象與結(jié)論之間關(guān)系的知識(shí) 他描述簡(jiǎn)單，但不反映事物的本質(zhì)。 如：經(jīng)驗(yàn)、感性、事實(shí)性知識(shí)（專家系

6、統(tǒng)） 深層知識(shí)：客觀事物本質(zhì)、因果關(guān)系內(nèi)涵、基本原理之類的知識(shí) 如：理論知識(shí)、理性知識(shí)(數(shù)據(jù)挖掘) 按知識(shí)的確定性 確定性知識(shí)：可以說(shuō)明其真值為真或?yàn)榧俚闹R(shí) 不確定性知識(shí)：不能確切說(shuō)明其真假或不能完全知道的知識(shí) 包括：不精確、模糊、不完備 按知識(shí)的等級(jí) 零級(jí)知識(shí)：敘述性知識(shí)。描述事物的屬性，問(wèn)題的狀態(tài)等 一級(jí)知識(shí)：過(guò)程性知識(shí)。經(jīng)驗(yàn)型、啟發(fā)性的知識(shí) 二級(jí)知識(shí)（元知識(shí)、超知識(shí)）：如何使用一級(jí)知識(shí) 三級(jí)知識(shí)（元元知識(shí)）,8,2.1.2 知識(shí)表示的概念-知識(shí)表示的含義及要求,什么是知識(shí)表示 是對(duì)知識(shí)的描述，即用一組符號(hào)把知識(shí)編碼成計(jì)算機(jī)可以接受的某種結(jié)構(gòu)。其表示方法不唯一。(請(qǐng)對(duì)比計(jì)算機(jī)如何了解5V

7、電壓信號(hào)？) 知識(shí)表示的要求（難度很大） 表示能力：能否正確、有效地將問(wèn)題求解所需的各種知識(shí)表示出來(lái) 表示范圍的廣泛性 領(lǐng)域知識(shí)表示的高效性 對(duì)非確定性知識(shí)表示的支持程度 可利用性：利用這些知識(shí)進(jìn)行推理，可以求得待解決問(wèn)題的解 對(duì)推理的適應(yīng)性：推理是根據(jù)已知事實(shí)利用知識(shí)導(dǎo)出結(jié)果的過(guò)程 對(duì)高效算法的支持程度：知識(shí)表示要有較高的處理效率 可實(shí)現(xiàn)性：要便于計(jì)算機(jī)直接對(duì)其進(jìn)行處理 可組織性：可以按某種方式把知識(shí)組織成某種知識(shí)結(jié)構(gòu) 可維護(hù)性：便于對(duì)知識(shí)的增、刪、改等操作（知識(shí)的一致性） 自然性：符合人們的日常習(xí)慣 可理解性：知識(shí)應(yīng)易讀、易懂、易獲取等,9,2.1.2 知識(shí)表示的概念-知識(shí)表示的觀點(diǎn)及方法

8、,知識(shí)表示的觀點(diǎn) 陳述性觀點(diǎn)：知識(shí)按某種結(jié)構(gòu)存儲(chǔ)，知識(shí)的使用由過(guò)程來(lái)實(shí)現(xiàn) 優(yōu)點(diǎn)：靈活、簡(jiǎn)潔，演繹過(guò)程完整、確定，知識(shí)維護(hù)方便 缺點(diǎn)：推理效率低、推理過(guò)程不透明（1965歸結(jié)定理） 過(guò)程性觀點(diǎn)：知識(shí)寓于使用知識(shí)的過(guò)程中，表示與運(yùn)用相結(jié)合（P38） 。 優(yōu)點(diǎn)：推理效率高、過(guò)程清晰 缺點(diǎn)：靈活性差、知識(shí)維護(hù)不便 知識(shí)表示的方法 邏輯表示法：一階謂詞邏輯 產(chǎn)生式表示法：產(chǎn)生式規(guī)則 結(jié)構(gòu)表示法：語(yǔ)義網(wǎng)絡(luò)，框架，腳本 過(guò)程表示法： 面向?qū)ο蟊硎痉ǎ?10,2.2 一階謂詞邏輯表示法,本節(jié)主要討論： 一階謂詞邏輯表示的邏輯基礎(chǔ) 僅與知識(shí)表示有關(guān)的，推理有關(guān)的在下一章 命題和真值；論域和謂詞；連詞和量詞； 項(xiàng)

9、與合式公式；自由變?cè)c約束變?cè)?謂詞邏輯表示的方法 謂詞邏輯表示的應(yīng)用 謂詞邏輯表示的特性,11,一階謂詞邏輯表示的邏輯基礎(chǔ)-命題與真值,命題的定義： 斷言：一個(gè)陳述句稱為一個(gè)斷言 命題：具有真假意義的斷言成為命題 可以用大寫字母表示命題，如： A: 天在下雨。 B: 天晴 C: 人是會(huì)死的 D: 他在哭 命題的真值： T：表示命題的意義為真 F：表示命題的意義為假 表達(dá)單一意義的命題稱為“原子命題”。 命題邏輯就是研究命題和命題之間關(guān)系的符號(hào)邏輯系統(tǒng)。,12,一階謂詞邏輯表示的邏輯基礎(chǔ)-論域和謂詞（一）,論域：由所討論對(duì)象的全體構(gòu)成的集合。也稱為個(gè)體域 個(gè)體：論域中的元素。 謂詞：在謂詞邏輯

10、中命題是用形如P(x1,x2,xn)的謂詞來(lái)表示的 謂詞名：是命題的謂語(yǔ)，表示個(gè)體的性質(zhì)、狀態(tài)或個(gè)體之間的關(guān)系 個(gè)體：是命題的主語(yǔ)，表示獨(dú)立存在的事物或概念 定義2.2 設(shè)D是個(gè)體域，P：DnT，F(xiàn)是一個(gè)映射，其中 則稱P是一個(gè)n元謂詞，記為 P(x1,x2,xn) 其中，x1,x2,xn為個(gè)體，可以是個(gè)體常量、變?cè)秃瘮?shù)。 例如：GREATER(x,6) x大于6 STUDENT(wanghong ) 王紅是一名學(xué)生 TEACHER(father(zhang) 張的父親是一位教師,13,一階謂詞邏輯表示的邏輯基礎(chǔ)-連詞,連詞： ：稱為“非”或者“否定”。它表示對(duì)其后面的命題的否定 ：稱為“析

11、取”。它表示所連結(jié)的兩個(gè)命題之間具有“或” ：稱為“合取”。 它表示所連結(jié)的兩個(gè)命題之間具有“與”的關(guān)系。 ：稱為“條件”或“蘊(yùn)含”。表示“若則”的語(yǔ)義。讀作“如果P，則Q”。 其中，P稱為條件的前件，Q稱為條件的后件。 ：稱為“雙條件”。它表示“當(dāng)且僅當(dāng)”的語(yǔ)義。即讀作“P當(dāng)且僅當(dāng)Q”。 例如，對(duì)命題P和Q，PQ表示“P當(dāng)且僅當(dāng)Q”，,14,蘊(yùn)含關(guān)系的困惑 ?-例子,蘊(yùn)含詞“若P則Q”與自然語(yǔ)言中的“若P則Q(同屬)”既有相似之處，也有本質(zhì)上的區(qū)別。 如果P是真的，Q是假的，那么復(fù)合命題“若P則Q”是假的。 如果P是假的，那么不管Q是真是假，復(fù)合命題“若P則Q”都是真的。 “如果今天下雨，那

12、么我們就呆在家里” （1）如果今天下雨了，我們呆在家里了，那么復(fù)合命題顯然是真的。 （2）如果今天下雨了，我們卻沒(méi)有呆在家里，那么這顯然違背了原命題，即復(fù)合命題是假的。 （3）如果今天沒(méi)有下雨，那么不管我們是否呆在家里都不能認(rèn)為我們違背了復(fù)合命題的要求，即復(fù)合命題是真的。,15,一階謂詞邏輯表示的邏輯基礎(chǔ)-量詞,量詞： ：全稱量詞，意思是“所有的”、“任一個(gè)” 命題( x)P(x)為真，當(dāng)且僅當(dāng)對(duì)論域中的所有x，都有P(x)為真 命題( x)P(x)為假，當(dāng)且僅當(dāng)對(duì)論域中的所有x，都有P(x)為假 ：存在量詞，意思是“至少有一個(gè)”、“存在有” 命題( x)P(x)為真，當(dāng)且僅當(dāng)至少存在一個(gè)xi

13、 D，使得P(xi)為真 命題( x)P(x)為假，當(dāng)且僅當(dāng)至少存在一個(gè)xi D，使得P(xi)為假,16,一階謂詞邏輯表示的邏輯基礎(chǔ)-項(xiàng)與合式公式,合法的謂詞表達(dá)式稱為合式公式（即謂詞公式） 。由“項(xiàng)” 來(lái)定義。 個(gè)體常量、個(gè)體變量和函數(shù)稱為項(xiàng)。 定義2-5 原子謂詞公式的含義為： 若t1，t2，tn是項(xiàng)，P是謂詞符號(hào)，則稱P(t1，t2， ，tn ) 為原子謂詞公式。 定義2-6 滿足如下規(guī)則的謂詞演算可得到合式公式： 單個(gè)原子謂詞公式是合式公式； 若A是合式公式，則A也是合式公式； 若A，B是合式公式，則AVB，AB，AB，AB也都是合式公式； 若A是合式公式，x是項(xiàng)，則( x)A和(

14、x)A也都是合式公式。 根據(jù)以上是合式公式的形成規(guī)則，可以形成任意復(fù)雜的合式公式。 例如，P(x，y)VQ(y)，( x)(A(x)B(x)，都是合式公式。 連詞的優(yōu)先級(jí)： ， ， V，,17,一階謂詞邏輯表示的邏輯基礎(chǔ)-自由變?cè)c約束變?cè)?轄域：指位于量詞后面的單個(gè)謂詞或者用括弧括起來(lái)的合式公式 約束變?cè)狠犛騼?nèi)與量詞中同名的變?cè)Q為約束變?cè)?自由變?cè)翰皇芗s束的變?cè)Q為自由變?cè)?例子：( x)(P(x，y)Q(x，y)VR(x，y) 其中，(P(x，y)Q(x，y)是(x)的轄域 轄域內(nèi)的變?cè)獂是受( x)約束的變?cè)?R(x，y)中的x和所有的y都是自由變?cè)?變?cè)膿Q名： 謂詞公式中的變?cè)?/p>

15、的名字是無(wú)關(guān)緊要的，可以換名。但需注意兩點(diǎn) 第一，當(dāng)對(duì)量詞轄域內(nèi)的變?cè)麜r(shí)，必須把同名的約束變?cè)冀y(tǒng)一換成另外一個(gè)相同的名字，且不能與轄域內(nèi)的自由變?cè)?。例如，?duì)公式( x(P(x，y)，可把約束變?cè)獂換成z，得到公式( z)(P(z，y)。 第二，當(dāng)對(duì)轄域內(nèi)的自由變?cè)麜r(shí)，不能改成與約束變?cè)嗤拿?。例如，?duì)公式( x)(P(x，y)，可把自由變?cè)獃換成t（但不能換成x），得到公式( z)(P(z，t)。,18,謂詞邏輯表示方法（一）,表示步驟：先根據(jù)表示的知識(shí)定義謂詞 再用連詞、量詞把這些謂詞連接起來(lái)（事實(shí)、因果） 例2.1 表示“每個(gè)人都有父親” 定義謂詞：P(x) 表示x是人

16、HF(x,y) 表示x有父親y 表示知識(shí)：( x)( y)(P (x) HF (x, y) P (y) 例2.2 表示知識(shí)“所有教師都有自己的學(xué)生”。 定義謂詞：T (x)：表示x 是教師。 S (x)：表示x是學(xué)生。 TS(x, y)：表示x是y的老師。 此時(shí)，該知識(shí)可用謂詞表示為： ( x)( y)(T (x) TS(x, y) S (y) 可讀作：對(duì)所有x，如果x是一個(gè)教師，那么一定存在一個(gè)個(gè)體y，y的老師是x，且y是一個(gè)學(xué)生。,19,謂詞邏輯表示方法（二）,例2.3 表示知識(shí)“所有的整數(shù)不是偶數(shù)就是奇數(shù)”。 定義謂詞：I(x)：x是整數(shù)， E(x)：x是偶數(shù)， O(x)：x是奇數(shù) 知識(shí)

17、的謂詞表示為： ( x)(I(x) E(x) O(x) 例2.4 表示如下知識(shí)： 王宏是計(jì)算機(jī)系的一名學(xué)生。 李明是王宏的同班同學(xué)。 凡是計(jì)算機(jī)系的學(xué)生都喜歡編程序。 定義謂詞： COMPUTER(x)：表示x是計(jì)算機(jī)系的學(xué)生。 CLASSMATE(x,y)：表示x是y的同班同學(xué)。 LIKE(x,y)：表示x喜歡y。 上述知識(shí)表示為： COMPUTER(Wanghong) CLASSMATE(Liming, Wanghong) ( x)(COMPUTER(x) LIKE(x, programing),20,練習(xí),用一階謂詞邏輯表示下面的句子： 自然數(shù)都是大于零的整數(shù)。 所有整數(shù)不是偶數(shù)就是奇數(shù)

18、。 并不是所有的學(xué)生都選修了歷史和生物。 歷史考試中只有一個(gè)學(xué)生不及格。 除了選修人工智能的學(xué)生外，都去舞會(huì)了。,21,謂詞邏輯表示的應(yīng)用-機(jī)器人移盒子問(wèn)題（一）智能規(guī)劃NP旅行規(guī)劃、自動(dòng)武器等,謂詞可用來(lái)描述狀態(tài)、動(dòng)作:機(jī)器人從c點(diǎn)出發(fā)，將盒子從a桌拿到b桌，然后再回到c處。 研究的對(duì)象： 桌子x的個(gè)體域是a, b 機(jī)器人y的個(gè)體域是robot 位置z的個(gè)體域是a, b, c 物體w的個(gè)體域是box 描述狀態(tài)的謂詞： TABLE(x)：x是桌子 EMPTY(y)：y手中是空的 AT(y, z)：y在z的附近 HOLDS(y, w)：y拿著w ON(w, x)：w在x桌面上,22,謂詞邏輯表示

19、的應(yīng)用-機(jī)器人移盒子問(wèn)題（二）,問(wèn)題的初始狀態(tài) AT(robot, c) EMPTY(robot) ON(box, a) TABLE(a) TABLE(b) 問(wèn)題的目標(biāo)狀態(tài) AT(robot, c) EMPTY(robot) ON(box, b) TABLE(a) TABLE(b) 機(jī)器人行動(dòng)的目標(biāo)把問(wèn)題的初始狀態(tài)轉(zhuǎn)換為目標(biāo)狀態(tài)，而要實(shí)現(xiàn)問(wèn)題狀態(tài)的轉(zhuǎn)換需要完成一系列的操作,23,謂詞邏輯表示的應(yīng)用-機(jī)器人移盒子問(wèn)題（三）,操作的表示方法 由條件和動(dòng)作兩部分 條件部分用來(lái)說(shuō)明執(zhí)行該操作必須具備的先決條件 可用謂詞公式來(lái)表示 動(dòng)作部分給出了該操作對(duì)問(wèn)題狀態(tài)的改變情況 動(dòng)作部分則是通過(guò)在執(zhí)行該操作前

20、的問(wèn)題狀態(tài)中刪去和增加相應(yīng)的謂詞來(lái)實(shí)現(xiàn)的 機(jī)器人需要執(zhí)行的操作 Goto(x, y)：從x處走到y(tǒng)處。 Pickup(x)：在x處拿起盒子。 Setdown(x)：在x處放下盒子。,24,謂詞邏輯表示的應(yīng)用-機(jī)器人移盒子問(wèn)題（三）,操作對(duì)應(yīng)的條件和動(dòng)作如下 Goto(x，y) 條件：AT(robot，x) 動(dòng)作：刪除：AT(robot，x) 添加：AT(robot，y) Pickup(x) 條件：ON(box，x)，TABLE(x)，AT(robot，x)，EMPTY(robot) 動(dòng)作：刪除：EMPTY(robot)，ON(box，x) 添加：HOLDS(robot，box) Setdown

21、(x) 條件：AT(robot，x)，TABLE(x)，HOLDS(robot，box) 動(dòng)作：刪除：HOLDS(robot，box) 添加：EMPTY(robot)，ON(box，x) 機(jī)器人在執(zhí)行每一操作之前，都需要檢查當(dāng)前狀態(tài)是否可以滿足該操作的先決條件。如果滿足，就執(zhí)行相應(yīng)的操作，否則就檢查下一個(gè)操作所要求的先決條件。(歸結(jié)理論),25,謂詞邏輯表示的應(yīng)用-機(jī)器人移盒子問(wèn)題（四）,這個(gè)機(jī)器人行動(dòng)規(guī)劃問(wèn)題的求解過(guò)程如下： 狀態(tài)1(初始狀態(tài)) AT(robot, c) 開始 EMPTY(robot) = ON(box, a) TABLE(a) TABLE(b) 狀態(tài)2 AT(robot,

22、a) Goto(x, y) EMPTY(robot) = ON(box, a) 用c代換x TABLE(a) a代換y TABLE(b) 狀態(tài)3 AT(robot, a) Pickup(x) HOLDS(robot,box) = TABLE(a) 用a代換x TABLE(b),26,謂詞邏輯表示的應(yīng)用-機(jī)器人移盒子問(wèn)題（五）,狀態(tài)4 AT(robot, b) Goto(x, y) HOLDS(robot,box) = TABLE(a) 用a代換x TABLE(b) b代換y 狀態(tài)5 AT(robot, b) Setdown(x) EMPTY(robot) = ON(box, b) 用b代換x

23、TABLE(a) TABLE(b) 狀態(tài)6(目標(biāo)狀態(tài)) AT(robot, c) Goto(x, y) EMPTY(robot) = ON(box, b) 用b代換x TABLE(a) c代換y TABLE(b),27,謂詞邏輯表示的應(yīng)用-機(jī)器人摞積木問(wèn)題（一）,描述狀態(tài)的謂詞(看圖找謂詞，TABLEEMPTY) CLEAR(x)：積木x上面是空的 ON(x, y)：積木x在積木y的上面 ONTABLE(x)：積木x在桌子上 HOLDING(x)：機(jī)械手抓住x HANDEMPTY：機(jī)械手是空的 其中，x和y的個(gè)體域都是A, B, C 問(wèn)題的初始狀態(tài) CLEAR(B), ON(C, A), ON

24、TABLE(A) , CLEAR(C) HANDEMPTY , ONTABLE(B) 問(wèn)題的目標(biāo)狀態(tài)是 ON(B, C), ON(A, B) , ONTABLE(C) CLEAR(A) , HANDEMPTY,A,B,C,28,謂詞邏輯表示的應(yīng)用（續(xù)）,29,謂詞邏輯表示的應(yīng)用-機(jī)器人摞積木問(wèn)題（二）,需要的4個(gè)操作 Pickup(x)：從桌面上揀起一塊積木x Putdown(x)：將手中的積木x放到桌子上 Stack(x, y)：把積木x摞在積木y上 Upstack(x, y)：把積木x從積木y上面揀起 操作對(duì)應(yīng)的先決條件及動(dòng)作 Pickup(x) (從桌面上揀起一塊積木x) 條件：ONTA

25、BLE(x)，HANDEMPTY，CLEAR(x) 動(dòng)作：刪除表：ONTABLE(x)，HANDEMPTY ，CLEAR(x) 添加表：HOLDING(x) Putdown(x) （將手中的積木x放到桌子上） 條件：HOLDING (x) 動(dòng)作：刪除表：HOLDING (x) 添加表：ONTABLE(x) ，HANDEMPTY ，CLEAR(x),30,謂詞邏輯表示的應(yīng)用-機(jī)器人摞積木問(wèn)題（三）,Stack(x, y) （把積木x摞在積木y上） 條件：HOLDING (x)，CLEAR(y) 動(dòng)作：刪除表：HOLDING (x)，CLEAR(y) 添加表：HANDEMPTY，ON(x, y)

26、，CLEAR(x) Upstack(x, y) （把積木x從積木y上面揀起） 條件：HANDEMPTY，CLEAR(x) ，ON(x, y) 動(dòng)作：刪除表：HANDEMPTY，ON(x, y) 添加表：HOLDING (x)，CLEAR(y) 利用上述謂詞和操作，即可完成積木世界的求解問(wèn)題。至于其求解過(guò)程，和前述機(jī)器人搬盒子問(wèn)題類似，這里從略。,31,謂詞邏輯表示的練習(xí)-猴子摘香蕉問(wèn)題（一）,描述狀態(tài)的謂詞 AT(x, y)：x在y處 ONBOX：猴子在箱子上 HB：猴子得到香蕉 其中，x 的個(gè)體域是 Monkey, Box, Banana Y 的個(gè)體域是 a, b, c 問(wèn)題的初始狀態(tài) AT

27、(Monkey, a) AT(Box, b) ONBOX ， HB 問(wèn)題的目標(biāo)狀態(tài) AT(Monkey, c) ，AT(Box, c) ONBOX ， HB,32,謂詞邏輯表示的應(yīng)用-猴子摘香蕉問(wèn)題（二）,需要的操作 Goto(u, v)： 猴子從u處走到v處 Pushbox(v, w)：猴子推著箱子從v處移到w處 Climbbox： 猴子爬上箱子 Grasp： 猴子摘取香蕉,33,謂詞邏輯表示的應(yīng)用-猴子摘香蕉問(wèn)題（二）,操作對(duì)應(yīng)的先決條件及動(dòng)作 Goto(u, v) 條件：ONBOX ，AT(Monkey, u)， 動(dòng)作：刪除表：AT(Monkey, u) 添加表：AT(Monkey, v

28、) Pushbox(v, w) 條件：ONBOX ，AT(Monkey, v)，AT(Box, v) 動(dòng)作：刪除表：AT(Monkey, v)，AT(Box, v) 添加表：AT(Monkey, w)，AT(Box,w) Climbbox 條件：ONBOX ，AT(Monkey, w)，AT(Box,w) 動(dòng)作：刪除表：ONBOX 添加表：ONBOX Grasp 條件：ONBOX，AT(Box, c) 動(dòng)作：刪除表：HB 添加表：HB,請(qǐng)寫出猴子摘香蕉的求解過(guò)程,34,謂詞邏輯表示的特征,主要優(yōu)點(diǎn) 自然：一階謂詞邏輯是一種接近于自然語(yǔ)言的形式語(yǔ)言系統(tǒng)，謂詞邏輯表示法接近于人們對(duì)問(wèn)題的直觀理解，

29、易于被人們接受 明確：人們都可以按照一種標(biāo)準(zhǔn)的方法去解釋知識(shí)，因此用這種方法表示的知識(shí)明確、易于理解 精確：謂詞邏輯的真值只有“真”與“假”，其表示、推理都是精確的 靈活：知識(shí)和處理知識(shí)是分開的，無(wú)須程序中考慮處理知識(shí)的細(xì)節(jié) 模塊化：各條知識(shí)都是相對(duì)獨(dú)立的，它們之間不直接發(fā)生聯(lián)系，因此添加、刪除、修改知識(shí)的工作比較容易進(jìn)行 主要缺點(diǎn) 知識(shí)表示能力差：只能表示確定性知識(shí)，而不能表示非確定性知識(shí)、過(guò)程性知識(shí)和啟發(fā)式知識(shí) 知識(shí)庫(kù)管理困難：缺乏知識(shí)的組織原則，知識(shí)庫(kù)管理比較困難 存在組合爆炸：由于難以表示啟發(fā)式知識(shí)，因此只能盲目地使用推理規(guī)則，這樣當(dāng)系統(tǒng)知識(shí)量較大時(shí)，容易發(fā)生組合爆炸 系統(tǒng)效率低：它把

30、推理演算與知識(shí)含義截然分開，拋棄了表達(dá)內(nèi)容中所含有的語(yǔ)義信息，往往使推理過(guò)程冗長(zhǎng)，降低了系統(tǒng)效率,35,2.3 產(chǎn)生式表示法,是目前人工智能中使用最多的一種知識(shí)表示方法 2.3.1 產(chǎn)生式表示的基本方法 事實(shí)的表示 規(guī)則的表示 產(chǎn)生式與蘊(yùn)含式的區(qū)別 產(chǎn)生式與條件語(yǔ)句的區(qū)別 2.3.2 產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程 2.3.3 產(chǎn)生式系統(tǒng)的控制策略 2.3.4 產(chǎn)生式系統(tǒng)的類型 2.3.5 產(chǎn)生式系統(tǒng)的特性,36,產(chǎn)生式表示的基本方法-事實(shí)的表示,事實(shí)的定義 事實(shí)是斷言一個(gè)語(yǔ)言變量的值或斷言多個(gè)語(yǔ)言變量之間關(guān)系的陳述句. 語(yǔ)言變量的值或語(yǔ)言變量之間的關(guān)系可以是數(shù)字、詞等. 例如：“雪是白的”，其中

31、“雪”是語(yǔ)言變量，“白的”是語(yǔ)言變量的值 ； “王峰熱愛(ài)祖國(guó)”，其中，“王峰”和“祖國(guó)”是兩個(gè)語(yǔ)言變量 “熱愛(ài)”是語(yǔ)言變量之間的關(guān)系。 事實(shí)的表示 確定性知識(shí)，事實(shí)可用如下三元組表示： （對(duì)象，屬性，值）或（關(guān)系，對(duì)象1，對(duì)象2） 其中，對(duì)象就是語(yǔ)言變量。例如： (Snow, color, White) 或（雪，顏色，白） (Love, Wangfeng, Country) 或（熱愛(ài)，王峰，祖國(guó)） 非確定性知識(shí)、事實(shí)可用如下四元組表示： （對(duì)象，屬性，值，可信度因子） 其中，“可信度因子”是指該事實(shí)為真的相信程度。例如 （Like, Liming, Computer, 0.9）,產(chǎn)生式表示的基

32、本方法-規(guī)則知識(shí)的表示,知識(shí)的表示方法 1.確定性規(guī)則知識(shí)的產(chǎn)生式表示 PQ 或 IF P THEN Q 其中，P是產(chǎn)生式的前提；Q是一組結(jié)論或操作，用于指出前提P所指示的條件被滿足時(shí),應(yīng)該得出的結(jié)論或應(yīng)該執(zhí)行的操作。 2.不確定性規(guī)則知識(shí)的產(chǎn)生式表示 PQ （置信度） 或 IF P THEN Q（置信度） 其中，P是產(chǎn)生式的前提；Q是一組結(jié)論或操作。已知事實(shí)與前提中所規(guī)定的條件不能精確匹配時(shí)，只要按照“置信度”的要求達(dá)到一定的相似度，就認(rèn)為已知事實(shí)與前提條件相匹配，再按照一定的算法將這些可能性（或不確定性）傳遞到結(jié)論。,38,產(chǎn)生式表示的基本方法-產(chǎn)生式與條件語(yǔ)句的區(qū)別,前件結(jié)構(gòu)不同 產(chǎn)生式

33、的前件可以是一個(gè)復(fù)雜的的結(jié)構(gòu) 傳統(tǒng)程序設(shè)計(jì)語(yǔ)言中的左部?jī)H僅是一個(gè)布爾表達(dá)式 控制流程不同 滿足前提條件的規(guī)則被激活，但不一定被立即執(zhí)行，能否執(zhí)行將取決于沖突消解策略 傳統(tǒng)程序設(shè)計(jì)語(yǔ)言中是嚴(yán)格地從一個(gè)條件語(yǔ)句向其下一個(gè)條件語(yǔ)句傳遞。,39,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-系統(tǒng)結(jié)構(gòu)及其說(shuō)明（一）,1.綜合數(shù)據(jù)庫(kù)（亦稱事實(shí)庫(kù)） (1) 存放求解問(wèn)題的各種當(dāng)前信息 如：?jiǎn)栴}的初始狀態(tài) 輸入的事實(shí) 中間結(jié)論及最終結(jié)論等 (2) 用于推理過(guò)程的規(guī)則匹配 推理過(guò)程中，當(dāng)規(guī)則庫(kù)中某條 規(guī)則的前提和綜合數(shù)據(jù)庫(kù)的已知事實(shí)匹配時(shí)，該規(guī)則被激活，由它推出的結(jié)論將被作為新的事實(shí)放入綜合數(shù)據(jù)庫(kù)，成為后面推理的已知事實(shí)。 2.

34、規(guī)則庫(kù) 用于存放與求解問(wèn)題有關(guān)的所有規(guī)則的集合 規(guī)則庫(kù)包含了問(wèn)題領(lǐng)域中的一般性知識(shí)，是產(chǎn)生式系統(tǒng)問(wèn)題求解的基礎(chǔ)，須重視知識(shí)的完整性、一致性、準(zhǔn)確性、靈活性和知識(shí)組織的合理性,控 制 系 統(tǒng),規(guī) 則 庫(kù),綜合數(shù)據(jù)庫(kù),40,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-系統(tǒng)結(jié)構(gòu)及其說(shuō)明（二）,3.控制系統(tǒng) 控制系統(tǒng)的主要作用： 亦稱推理機(jī)構(gòu)。是規(guī)則的解釋程序，用于控制整個(gè)產(chǎn)生式系統(tǒng)的運(yùn)行，決定問(wèn)題求解過(guò)程的推理線路。 控制系統(tǒng)的主要任務(wù)： (1) 匹配：按一定策略從規(guī)則庫(kù)種選擇規(guī)則與綜合數(shù)據(jù)庫(kù)中的已知事實(shí)進(jìn)行匹配。所謂匹配是指把所選規(guī)則的前提與綜合數(shù)據(jù)庫(kù)中的已知事實(shí)進(jìn)行比較，若事實(shí)庫(kù)中存的事實(shí)與所選規(guī)則前提一致，則

35、稱匹配成功，該規(guī)則可被使用；否則，稱匹配失敗，該規(guī)則不可用于當(dāng)前推理。 (2)沖突消解：對(duì)匹配成功的規(guī)則，按照某種策略從中選出一條規(guī)則執(zhí)行。 (3)執(zhí)行操作：對(duì)所執(zhí)行的規(guī)則，若其后件為一個(gè)或多個(gè)結(jié)論，則把這些結(jié)論加入綜合數(shù)據(jù)庫(kù)；若其后件為一個(gè)或多個(gè)操作時(shí)，執(zhí)行這些操作。 檢查綜合數(shù)據(jù)庫(kù)中是否包含有問(wèn)題的目標(biāo)，若有，則停止推理。 (4)路徑解釋：在問(wèn)題求解過(guò)程中，記住應(yīng)用過(guò)的規(guī)則序列，以便最終能夠給出問(wèn)題的解的路徑。,41,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-系統(tǒng)結(jié)構(gòu)及其說(shuō)明（三）,控制系統(tǒng)的基本過(guò)程 (1) 初始化綜合數(shù)據(jù)庫(kù)，即把欲解決問(wèn)題的已知事實(shí)送入綜合數(shù)據(jù)庫(kù)中； (2) 檢查規(guī)則庫(kù)中是否有未使用

36、過(guò)的規(guī)則，若無(wú)轉(zhuǎn) (7)；（FOR） (3) 檢查規(guī)則庫(kù)的未使用規(guī)則中是否有其前提可與綜合數(shù)據(jù)庫(kù)中已知事實(shí)相匹配的規(guī)則，若有，形成當(dāng)前可用規(guī)則集；否則轉(zhuǎn)(6)； (4) 按照沖突消解策略，從當(dāng)前可用規(guī)則集中選擇一個(gè)規(guī)則執(zhí)行，并對(duì)該規(guī)則作上標(biāo)記。把執(zhí)行該規(guī)則后所得到的結(jié)論作為新的事實(shí)放入綜合數(shù)據(jù)庫(kù)；如果該規(guī)則的結(jié)論是一些操作，則執(zhí)行這些操作； (5) 檢查綜合數(shù)據(jù)庫(kù)中是否包含了該問(wèn)題的解，若已包含，說(shuō)明解已求出，問(wèn)題求解過(guò)程結(jié)束；否則，轉(zhuǎn)(2)； (6) 當(dāng)規(guī)則庫(kù)中還有未使用規(guī)則，但均不能與綜合數(shù)據(jù)庫(kù)中的已有事實(shí)相匹配時(shí)，要求用戶進(jìn)一步提供關(guān)于該問(wèn)題的已知事實(shí)，若能提供，則轉(zhuǎn)(2)；否則，執(zhí)行下

37、一步； (7) 若知識(shí)庫(kù)中不再有未使用規(guī)則，也說(shuō)明該問(wèn)題無(wú)解，終止問(wèn)題求解過(guò)程。 說(shuō)明：從第(3)步到第(5)步的循環(huán)過(guò)程實(shí)際上就是一個(gè)搜索過(guò)程,42,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-產(chǎn)生式系統(tǒng)的例子（一）,動(dòng)物識(shí)別系統(tǒng) 該系統(tǒng)可以識(shí)別老虎、金錢豹、斑馬、長(zhǎng)頸鹿、企鵝、信天翁這6種動(dòng)物。其規(guī)則庫(kù)包含如下15條規(guī)則： r1 IF 該動(dòng)物有毛發(fā) THEN 該動(dòng)物是哺乳動(dòng)物 r2 IF 該動(dòng)物有奶 THEN 該動(dòng)物是哺乳動(dòng)物 r3 IF 該動(dòng)物有羽毛 THEN 該動(dòng)物是鳥 r4 IF 該動(dòng)物會(huì)飛 AND 會(huì)下蛋 THEN 該動(dòng)物是鳥 r5 IF 該動(dòng)物吃肉 THEN 該動(dòng)物是食肉動(dòng)物 r6 IF 該動(dòng)物

38、有犬齒 AND 有爪 AND 眼盯前方 THEN 該動(dòng)物是食肉動(dòng)物 r7 IF 該動(dòng)物是哺乳動(dòng)物 AND 有蹄 THEN 該動(dòng)物是有蹄類動(dòng)物 r8 IF 該動(dòng)物是哺乳動(dòng)物 AND 是嚼反芻動(dòng)物 THEN 該動(dòng)物是有蹄類動(dòng)物 r9 IF 該動(dòng)物是哺乳動(dòng)物 AND 是食肉動(dòng)物 AND 是黃褐色 AND 身上有暗斑點(diǎn) THEN 該動(dòng)物是金錢豹,43,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-產(chǎn)生式系統(tǒng)的例子（二）,r10 IF 該動(dòng)物是哺乳動(dòng)物 AND 是食肉動(dòng)物 AND 是黃褐色 AND 身上有黑色條紋 THEN 該動(dòng)物是虎 r11 IF 該動(dòng)物是有蹄類動(dòng)物 AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 身上有暗斑

39、點(diǎn) THEN 該動(dòng)物是長(zhǎng)頸鹿 r12 IF 動(dòng)物是有蹄類動(dòng)物 AND 身上有黑色條紋 THEN 該動(dòng)物是斑馬 r13 IF 該動(dòng)物是鳥 AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是鴕鳥 r14 IF 該動(dòng)物是鳥 AND 會(huì)游泳 AND 不會(huì)飛 AND 有黑白二色 THEN 該動(dòng)物是企鵝 r15 IF 該動(dòng)物是鳥 AND 善飛 THEN 該動(dòng)物是信天翁 其中，ri(i=1,2,.,15)是規(guī)則的編號(hào) 初始綜合數(shù)據(jù)庫(kù)包含的事實(shí)有： 動(dòng)物有暗斑點(diǎn)，有長(zhǎng)脖子，有長(zhǎng)腿，有奶，有蹄 這些規(guī)則的部分推理網(wǎng)絡(luò)如下圖所示,44,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-產(chǎn)生式系統(tǒng)的

40、例子（三）,圖中最上層的結(jié)點(diǎn)稱為“假設(shè)”或“結(jié)論” 中間結(jié)點(diǎn)稱為“中間假設(shè)”；終結(jié)點(diǎn)（葉結(jié)點(diǎn)）稱為“證據(jù)”或“事實(shí)” 每個(gè)“結(jié)論”都是本問(wèn)題的一個(gè)目標(biāo)，所有“假設(shè)”構(gòu)成了本問(wèn)題的目標(biāo)集合,長(zhǎng)頸鹿,斑馬,長(zhǎng)脖子,長(zhǎng)腿,暗斑點(diǎn),有蹄類,黑條紋,有蹄,哺乳動(dòng)物,嚼反芻動(dòng)物,有毛,r2,r7,r8,r11,r12,有奶,r1,45,產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)及過(guò)程-產(chǎn)生式系統(tǒng)的例子（四）,推理機(jī)的工作過(guò)程 (1) 先從規(guī)則庫(kù)中取出第一條規(guī)則r1，檢查其前提是否可與綜合數(shù)據(jù)庫(kù)中的已知事實(shí)相匹配。r1的前提是“有毛發(fā)”，但事實(shí)庫(kù)中無(wú)此事實(shí)，故匹配失敗。然后取r2，該前提可與已知事實(shí)“有奶”相匹配，r2被執(zhí)行，并

41、將其結(jié)論“該動(dòng)物是哺乳動(dòng)物”作為新的事實(shí)加入到綜合數(shù)據(jù)庫(kù)中。此時(shí)，綜合數(shù)據(jù)庫(kù)的內(nèi)容變?yōu)椋?動(dòng)物有暗斑，有長(zhǎng)脖子，有長(zhǎng)腿，有奶，有蹄，是哺乳動(dòng)物 (2) 再?gòu)囊?guī)則庫(kù)中取r3，r4，r5，r6進(jìn)行匹配，均失敗。接著取r7，該前提與已知事實(shí)“是哺乳動(dòng)物”相匹配，r7被執(zhí)行，并將其結(jié)論“該動(dòng)物是有蹄類動(dòng)物” 作為新的事實(shí)加入到綜合數(shù)據(jù)庫(kù)中。此時(shí)，綜合數(shù)據(jù)庫(kù)的內(nèi)容變?yōu)椋?動(dòng)物有暗斑，有長(zhǎng)脖子，有長(zhǎng)腿，有奶，有蹄，是哺乳動(dòng)物，是有蹄類動(dòng)物 (3) 此后，r8，r9，r10均匹配失敗。接著取r11，該前提 “該動(dòng)物是有蹄類動(dòng)物 AND 有長(zhǎng)脖子 AND 有長(zhǎng)腿 AND 身上有暗斑” 與已知事實(shí)相匹配，r11

42、被執(zhí)行，并推出“該動(dòng)物是長(zhǎng)頸鹿”。由于“長(zhǎng)頸鹿”已是目標(biāo)集合中的一個(gè)結(jié)論，即已推出最終結(jié)果，故問(wèn)題求解過(guò)程結(jié)束。 說(shuō)明：上述規(guī)則僅是一種直接表示方式，用三元組表示r15如下： r15：IF（動(dòng)物，類別，鳥）AND（動(dòng)物，本領(lǐng)，善飛） THEN（動(dòng)物，名稱，信天翁）,46,產(chǎn)生式系統(tǒng)的控制策略,分為不可撤回(Irrevocable)方式、試探性(Tentative)方式 1. 不可撤回方式（爬山法） 是一種“一直往前走”不回頭的方式，類似于中國(guó)象棋中為過(guò)河卒子的規(guī)定。 它利用問(wèn)題給定的局部知識(shí)來(lái)決定選用那條規(guī)則的。即根據(jù)當(dāng)前已知的局部知識(shí)選取一條規(guī)則作用于當(dāng)前綜合數(shù)據(jù)庫(kù)，接著再根據(jù)新狀態(tài)繼續(xù)選取

43、規(guī)則，搜索過(guò)程一直進(jìn)行下去，不必考慮撤回用過(guò)的規(guī)則。 不理想規(guī)則的應(yīng)用會(huì)多用了一些規(guī)則，但仍能找到解。 優(yōu)點(diǎn)是控制過(guò)程簡(jiǎn)單，缺點(diǎn)是當(dāng)問(wèn)題有多個(gè)解時(shí)不一定能找到最優(yōu)解 2. 試探性方式 可分為回溯(Backtracking)方式和圖搜索(Graph-search)方式。 (1) 回溯方式 是一種碰壁回頭的方式。即在問(wèn)題求解過(guò)程中，允許先試一試某條規(guī)則，如果以后發(fā)現(xiàn)這條規(guī)則不合適，則允許退回去，再另選一條規(guī)則來(lái)試。 需要解決兩個(gè)主要問(wèn)題，一是如何確定回溯條件，二是如何減少回溯次數(shù) 是一種完備而有效的策略，它容易實(shí)現(xiàn)且占內(nèi)存容量較小。 (2) 圖搜索方式 圖搜索方式是一種用圖或樹把全部求解過(guò)程記錄下

44、來(lái)的方式。由于它記錄了已試過(guò)的所有路徑，因此便于從中選取最優(yōu)路徑。 圖搜索方式與回溯方式的主要區(qū)別在于，回溯方式抹去了所有引起失敗的試探路徑，而圖搜索方式則記住了已試過(guò)的所有路徑。,產(chǎn)生式系統(tǒng)的推理方式有正向推理、反向推理和雙向推理三種： 1. 正向推理：也稱為數(shù)據(jù)驅(qū)動(dòng)方式或自底向上的方式；從已知事實(shí)出發(fā)，通過(guò)規(guī)則庫(kù)求得結(jié)論，便于寬度優(yōu)先搜索 。其推理過(guò)程是： 1）規(guī)則庫(kù)中的規(guī)則的前件與綜合數(shù)據(jù)庫(kù)中的事實(shí)進(jìn)行匹配，得到匹配的規(guī)則集合。 2）使用沖突解決算法，從匹配規(guī)則集合中選擇一條規(guī)則作為啟用規(guī)則。 3）執(zhí)行啟用規(guī)則的后件，將該啟用規(guī)則的后件送入綜合數(shù)據(jù)庫(kù)并對(duì)綜合數(shù)據(jù)庫(kù)進(jìn)行必要的修改。 重復(fù)這

45、個(gè)過(guò)程直至達(dá)到目標(biāo)。正向推理的典型系統(tǒng)：CLIPS （C語(yǔ)言集成產(chǎn)生式系統(tǒng)） 優(yōu)點(diǎn)是簡(jiǎn)單明了且能求出所有解 缺點(diǎn)是執(zhí)行效率較低，原因是它驅(qū)動(dòng)了一些與問(wèn)題無(wú)關(guān)的規(guī)則，具有一定的盲目性。,產(chǎn)生式系統(tǒng)的類型-按推理方向,2.反向推理：也稱為目標(biāo)驅(qū)動(dòng)方式或自頂向下的方式；從目標(biāo)（作為假設(shè)）出發(fā)，反向使用規(guī)則，求得已知事實(shí)；便于深度優(yōu)先搜索；其推理過(guò)程是： 1）規(guī)則庫(kù)中的規(guī)則后件與目標(biāo)事實(shí)進(jìn)行匹配，得到匹配的規(guī)則集合。 2）使用沖突解決算法，從匹配規(guī)則集合中選擇一條規(guī)則作為啟用規(guī)則。 3）將啟用規(guī)則的前件作為子目標(biāo)。 重復(fù)這個(gè)過(guò)程直至個(gè)子目標(biāo)均為已知事實(shí)，則反向推理過(guò)程成功結(jié)束。 反向推理的典型系統(tǒng)：P

46、ROLOG 優(yōu)點(diǎn)是不尋找無(wú)用數(shù)據(jù)，不使用與問(wèn)題無(wú)關(guān)的規(guī)則。因此，對(duì)那些目標(biāo)明確的問(wèn)題，使用反向推理方式是一種最佳選擇。,產(chǎn)生式系統(tǒng)的類型-按推理方向,3. 雙向推理：推理從兩個(gè)方向同時(shí)進(jìn)行，直至某個(gè)到達(dá)相同的中間事實(shí)則成功結(jié)束。這種推理方式較正向或反向推理所形成的推理網(wǎng)絡(luò)小，從而推理效果更高。,產(chǎn)生式系統(tǒng)的類型-按推理方向,產(chǎn)生式表示法,正向推理 If A Then B ， If B Then C ， If C Then D 反向推理：規(guī)則重寫為 If D Then C ， If C Then B ， If B Then A,51,產(chǎn)生式系統(tǒng)的類型-按規(guī)則庫(kù)的性質(zhì)及結(jié)構(gòu)（一）,可交換的產(chǎn)生式系

47、統(tǒng) 是一種對(duì)規(guī)則的使用次序無(wú)關(guān)的產(chǎn)生式系統(tǒng) 可交換性是指任意交換規(guī)則的使用次序而不會(huì)影響對(duì)問(wèn)題的求解 假設(shè)DB是綜合數(shù)據(jù)庫(kù)，RB是規(guī)則庫(kù)，DBi (i=1,2,)是第i次使用規(guī)則后得到的新的綜合數(shù)據(jù)庫(kù)，RS RB是一個(gè)可作用于DBi的規(guī)則集合。若一個(gè)產(chǎn)生式系統(tǒng)可交換，則其RB和每一個(gè)DBi都應(yīng)具有如下性質(zhì)： 對(duì)任一規(guī)則rj RS (j=1,2,)，它作用于DBi得到新的綜合數(shù)據(jù)庫(kù)DBi+1，RS仍然是DBi+1的可用規(guī)則集。 如果DBi滿足目標(biāo)條件，則用RS中的任一規(guī)則rj作用于DBi，得到的DBi+1仍然滿足目標(biāo)條件。 若對(duì)DBi使用某一規(guī)則序列r1,r2,rk得到一個(gè)新的綜合數(shù)據(jù)庫(kù)DBk，

48、則當(dāng)改變這些規(guī)則的使用次序后，仍然可得到DBk。 從可交換產(chǎn)生式系統(tǒng)的上述性質(zhì)可以看出，其綜合數(shù)據(jù)庫(kù)的內(nèi)容是遞增的，即對(duì)任何規(guī)則序列r1,r2,rg，其作用于DB 后所得到的綜合數(shù)據(jù)庫(kù)DB1 ，DB2，DBg之間存在如下關(guān)系： DB1 DB2 DBg 這說(shuō)明在可交換產(chǎn)生式系統(tǒng)中，其規(guī)則的結(jié)論部分總是包含著新的內(nèi)容，一旦執(zhí)行該規(guī)則就會(huì)把這些新的內(nèi)容添加到綜合數(shù)據(jù)庫(kù)中。,52,產(chǎn)生式系統(tǒng)的類型-按規(guī)則庫(kù)的性質(zhì)及結(jié)構(gòu)（二）,例2.6 設(shè)給定一個(gè)整數(shù)集合a，b，c，可通過(guò)把集合中任意一對(duì)元素的乘積作為新元素添加到集合中的辦法來(lái)擴(kuò)大該整數(shù)集，要求通過(guò)若干次操作后能生成所需的整數(shù)集合。 用產(chǎn)生式求解這個(gè)問(wèn)

49、題時(shí)，綜合數(shù)據(jù)庫(kù)DB可用集合來(lái)表示， 初始狀態(tài)為a，b，c 目標(biāo)狀態(tài)為a，b，c，ab，bc，ac 規(guī)則庫(kù)中包含的規(guī)則有： r1: IF a，b，c THEN a，b，c，ab r2: IF a，b，c THEN a，b，c，bc r3: IF a，b，c THEN a，b，c，ac 顯然，無(wú)論先使用哪一條規(guī)則都可由初始狀態(tài)達(dá)到目標(biāo)狀態(tài)。因此，上述由DB和RB所構(gòu)造的產(chǎn)生式系統(tǒng)是一個(gè)可交換的產(chǎn)生式系統(tǒng)，并具有可交換產(chǎn)生式系統(tǒng)三個(gè)性質(zhì)。 可交換產(chǎn)生式系統(tǒng)的可交換性，使得其求解過(guò)程只需要搜索其中的任意一條路經(jīng)，就能達(dá)到目標(biāo)，而不必進(jìn)行回溯。 這種系統(tǒng)的求解過(guò)程可采用不可撤回的控制方式。,53,產(chǎn)生

50、式系統(tǒng)的類型-按規(guī)則庫(kù)的性質(zhì)及結(jié)構(gòu)（三）,可分解的產(chǎn)生式系統(tǒng) 這種方法把一個(gè)較大或較復(fù)雜的問(wèn)題分解成若干個(gè)較小或較簡(jiǎn)單的問(wèn)題，然后通過(guò)對(duì)這些較小或較簡(jiǎn)單問(wèn)題的求解來(lái)得到整個(gè)問(wèn)題的解。 可分解的產(chǎn)生式系統(tǒng)是把一個(gè)整體問(wèn)題分解成若干個(gè)子問(wèn)題，然后再通過(guò)對(duì)這些子問(wèn)題的求解來(lái)得到整個(gè)問(wèn)題解的一種產(chǎn)生式系統(tǒng)。 例2.7 設(shè)綜合數(shù)據(jù)庫(kù)的初始狀態(tài)為C，B，Z，目標(biāo)狀態(tài)為 M，M，M ，規(guī)則庫(kù)中有如下規(guī)則： r1：CD，L r2：CB，M r3：BM，M r4：ZB，B，M 解決該問(wèn)題時(shí)，可先把初始綜合數(shù)據(jù)庫(kù)分為三個(gè)子庫(kù)，然后對(duì)這三個(gè)子庫(kù)分別應(yīng)用規(guī)則庫(kù)中的相應(yīng)規(guī)則進(jìn)行求解。其求解過(guò)程如下圖所示。,54,產(chǎn)生式

51、系統(tǒng)的類型-按規(guī)則庫(kù)的性質(zhì)及結(jié)構(gòu)（三）,C,B,Z,C,B,Z,D,L,B,M,M,M,B,B,M,D,L,B,M,M,M,B,M,B,M,M,M,M,M,M,M,M,M,M,M,M,r1,r2,r3,r4,r3,r3,r3,55,產(chǎn)生式系統(tǒng)的類型-按規(guī)則庫(kù)的性質(zhì)及結(jié)構(gòu)（四）,可恢復(fù)的產(chǎn)生式系統(tǒng) 是指那種采用回溯控制方式的產(chǎn)生式系統(tǒng) 其求解問(wèn)題的方法是：當(dāng)執(zhí)行某條規(guī)則后，如果發(fā)現(xiàn)所得到的新的綜合數(shù)據(jù)庫(kù)不可能求出問(wèn)題的解，就立即撤消由該規(guī)則所產(chǎn)生的結(jié)果，使綜合數(shù)據(jù)庫(kù)恢復(fù)到先前的狀態(tài)，然后再另選別的規(guī)則繼續(xù)求解。 它既可以向綜合數(shù)據(jù)庫(kù)中添加新的內(nèi)容，又可以從綜合數(shù)據(jù)庫(kù)中刪除或修改老的內(nèi)容。這種求解

52、問(wèn)題的方法，更符合人們的一般習(xí)慣。,練習(xí),針對(duì)猴子摘香蕉問(wèn)題，給出產(chǎn)生式系統(tǒng)描述。,57,產(chǎn)生式系統(tǒng)的特點(diǎn),主要優(yōu)點(diǎn) 自然性 產(chǎn)生式表示法用“如果，則”的形式表示知識(shí)，這種表示形式與人類的判斷性知識(shí)基本一致，既直觀、自然，又便于進(jìn)行推理。 模塊性 產(chǎn)生式規(guī)則是規(guī)則庫(kù)中最基本的知識(shí)單元，各規(guī)則之間只能通過(guò)綜合數(shù)據(jù)庫(kù)發(fā)生聯(lián)系，而不能相互調(diào)用，從而增加了規(guī)則的模塊性，有利于對(duì)知識(shí)的增加、刪除、修改和擴(kuò)充。 有效性 產(chǎn)生式知識(shí)表示法既可以表示確定性知識(shí)，又可以表示不確定性知識(shí)，既有利于表示啟發(fā)性知識(shí)，又有利于表示過(guò)程性知識(shí)。 一致性 規(guī)則庫(kù)中的所有規(guī)則都具有相同的格式，并且綜合數(shù)據(jù)庫(kù)可被所有規(guī)則訪問(wèn)，

53、不存在只屬于某些規(guī)則的局部數(shù)據(jù)庫(kù)，因此規(guī)則庫(kù)中的規(guī)則可以統(tǒng)一處理。,58,產(chǎn)生式系統(tǒng)的特點(diǎn),主要缺點(diǎn) 效率較低 在產(chǎn)生式表示中，各規(guī)則之間的聯(lián)系必須以綜合數(shù)據(jù)庫(kù)為媒介。并且，其求解過(guò)程是一種反復(fù)進(jìn)行的“匹配沖突消解執(zhí)行”過(guò)程。即先用規(guī)則前提與綜合數(shù)據(jù)庫(kù)中的已知事實(shí)進(jìn)行匹配，從規(guī)則庫(kù)中選擇可用規(guī)則，當(dāng)有多條規(guī)則可用時(shí)還需要按一定策略進(jìn)行“沖突消解”，然后才能執(zhí)行選中的規(guī)則。這樣的執(zhí)行方式將導(dǎo)致執(zhí)行的低效率。 不能表示結(jié)構(gòu)性知識(shí) 由于產(chǎn)生式表示中的知識(shí)具有一致格式，且規(guī)則之間不能相互調(diào)用，因此那種具有結(jié)構(gòu)關(guān)系或?qū)哟侮P(guān)系的知識(shí)則很難以自然的方式來(lái)表示。 實(shí)際上，產(chǎn)生式系統(tǒng)除作為一種獨(dú)立的知識(shí)表示方式

54、外，還常常和其它方法結(jié)合起來(lái)使用。,2.4 語(yǔ)義網(wǎng)絡(luò)表示法,語(yǔ)義網(wǎng)絡(luò)是J.R.Quillian于1968年在他的博士論文中作為人類聯(lián)想記憶的一個(gè)心理模型最先提出的。語(yǔ)義網(wǎng)絡(luò)最初主要用于自然語(yǔ)言理解的研究，Quillian主張應(yīng)當(dāng)把語(yǔ)義放在第一位，一個(gè)詞的含義只有根據(jù)它所處的上下文環(huán)境才能準(zhǔn)確的把握，一個(gè)句子中相關(guān)單詞的語(yǔ)義或意思可以通過(guò)這種網(wǎng)絡(luò)來(lái)表示。 基于Quillian的工作，Simon于1970年正式提出了語(yǔ)義網(wǎng)絡(luò)的概念。,2.4 語(yǔ)義網(wǎng)絡(luò)表示法,2.4.1 語(yǔ)義網(wǎng)絡(luò)的概念及其結(jié)構(gòu) 1. 語(yǔ)義網(wǎng)絡(luò)的概念及結(jié)構(gòu) 語(yǔ)義網(wǎng)絡(luò)是通過(guò)概念及其語(yǔ)義關(guān)系來(lái)表示知識(shí)的一種網(wǎng)絡(luò)圖，它是一個(gè)帶標(biāo)記的有向圖。

55、其中有向圖的各節(jié)點(diǎn)用來(lái)表示各種概念、事物、屬性、情況、動(dòng)作、狀態(tài)等，節(jié)點(diǎn)上的標(biāo)注用來(lái)區(qū)分各節(jié)點(diǎn)所表示的不同對(duì)象，每個(gè)節(jié)點(diǎn)可以帶有若干個(gè)屬性，以表示其所代表的不同對(duì)象的特性；弧是有方向、有標(biāo)注的，方向用來(lái)體現(xiàn)節(jié)點(diǎn)間的主次關(guān)系，而其上的標(biāo)注則表示被聯(lián)接的兩個(gè)節(jié)點(diǎn)間的某種語(yǔ)義聯(lián)系或語(yǔ)義關(guān)系。,2.4 語(yǔ)義網(wǎng)絡(luò)表示法,一個(gè)最簡(jiǎn)單的語(yǔ)義網(wǎng)絡(luò)可由一個(gè)三元組表示： （節(jié)點(diǎn)1，弧，節(jié)點(diǎn)2） 可用如下圖所示的有向圖表示，稱作基本網(wǎng)元。,A,B,R,其中，A和B分別代表節(jié)點(diǎn)，而R則表示A和B之間某種語(yǔ)義聯(lián)系。,2.4 語(yǔ)義網(wǎng)絡(luò)表示法,2. 與謂詞邏輯表示法和產(chǎn)生式表示法的聯(lián)系 從謂詞邏輯表示法來(lái)看，一個(gè)基本網(wǎng)元相

56、當(dāng)于一組一階二元謂詞。產(chǎn)生式表示法是以一條產(chǎn)生式規(guī)則作為知識(shí)的單位，各條產(chǎn)生式規(guī)則之間沒(méi)有直接的聯(lián)系。 而語(yǔ)義網(wǎng)絡(luò)則不同，它不僅將基本網(wǎng)元視作一種知識(shí)的單位，而且各個(gè)基本網(wǎng)元之間又是相互聯(lián)系的。每一條產(chǎn)生式規(guī)則可以表示為語(yǔ)義網(wǎng)絡(luò)的形式。,2.4 語(yǔ)義網(wǎng)絡(luò)表示法,2.4.2 語(yǔ)義網(wǎng)絡(luò)中常用的語(yǔ)義聯(lián)系 1.類屬關(guān)系 類屬關(guān)系是指具有共同屬性的不同事物間的分類關(guān)系、成員關(guān)系或?qū)嵗P(guān)系。它體現(xiàn)的是“具體與抽象”、“個(gè)體與集體”的層次關(guān)系。具體層節(jié)點(diǎn)位于抽象層節(jié)點(diǎn)的下層。類屬關(guān)系的一個(gè)最主要的特征是屬性的繼承性，處在具體層的節(jié)點(diǎn)可以繼承抽象層節(jié)點(diǎn)的所有屬性。常用的類屬關(guān)系有： AKO：“是一種”（a kind of），表示一事物是另一事物的一種類型。 AMO：“是一員”（a member of），表示一事物是另一事物的一個(gè)成員。 ISA：“是一個(gè)”（is a ），表一事物是另一事物的一個(gè)實(shí)例。 類屬關(guān)系具有屬性的繼承性。,2.4 語(yǔ)義網(wǎng)絡(luò)