人工智能和專家系統(tǒng)

1、人工智能與專家系統(tǒng),研究生課程,第一章 緒論,1.1 人工智能的定義和發(fā)展1.2 人類智能和人工智能 1.3 人工智能的各種認知觀 1.4 人工智能的研究與應(yīng)用領(lǐng)域 1.5 課程概要,1.1.1 人工智能的定義,幾種定義 智能機器（intelligent machine） 人工智能（學科） 人工智能（能力） 人工智能（擬人思維、行為 ）

2、 人工智能（理性思維、行為 ）,1.1 定義和發(fā)展,1.1.2 人工智能的起源與發(fā)展,孕育期（1956年前） 數(shù)理邏輯學科（弗雷治、維納等 ） 計算的新思想（丘奇、圖靈 等） 形成期（1956--1970年） 1956年，第一次人工智能的研討會 1969年，第一屆國際人工智能聯(lián)合會議 1970年，《人工智能》國際雜志創(chuàng)刊,1.1 定義和發(fā)展,1.1.2 人工智能的起源與發(fā)展,發(fā)展期（1970年~） 進一步研究AI基本原

3、理方法和技術(shù) 進行實用化研究 專家系統(tǒng)與知識工程 機器定理證明 智能機器人 智能控制等 從“一枝獨秀”到“百花齊放”,1.1 定義和發(fā)展,1.2 人類智能和人工智能,1.2.1 智能信息處理系統(tǒng)的假設(shè) 人是一種智能信息處理系統(tǒng) 物理符號系統(tǒng)的六種基本功能 物理符號系統(tǒng)的假設(shè) 推論一 推論二 推論三,1.2.1 智能信息處理系統(tǒng)的假設(shè),人類的認知行為具有不同層次 認知生理學 認知心理學 認知信息學

4、 認知工程學,1.2 人類智能和人工智能,1.2.2 人類智能的計算機模擬,機器智能可以模擬人類智能 智能計算機 下棋 定理證明 語言翻譯 新型智能計算機 神經(jīng)計算機量子計算機,1.2 人類智能和人工智能,1.2.3 人工智能的研究目標,近期目標建造智能計算機代替人類的部分智力勞動 遠期目標用自動機模仿人類的思維過程和智能行為,1.2 人類智能和人工智能,1.3 人工智能的各種認知觀,符號主義（Symbolici

5、sm）基于物理符號系統(tǒng)假設(shè)和有限合理性原理 連接主義（Connectionism）基于神經(jīng)網(wǎng)絡(luò)及其間的連接機制與學習算法 行為主義（Actionism）基于控制論及感知—動作型控制系統(tǒng),1.4 人工智能的研究及應(yīng)用領(lǐng)域,人工智能的基本技術(shù) 知識表示（Knowledge Representation）狀態(tài)空間法、問題歸約法、謂詞邏輯法… 推理搜索（Searching & Reasoning）啟發(fā)式搜索、消解

6、原理、不確定性推理… 計算智能（Computational Intelligence）模糊計算、神經(jīng)計算、進化計算… 構(gòu)成技術(shù)（系統(tǒng)與語言）產(chǎn)生式系統(tǒng)、LISP語言、Prolog語言…,1.4.1 問題求解,問題的表示、分解、搜索、歸約等 進行復雜的數(shù)學公式符號運算求解1.4.2 邏輯推理與定理證明 通過對事實數(shù)據(jù)庫的操作來證明定理 多種證明方法 幾何定理證明的“吳氏方法”,1.4 研究及應(yīng)用,1.4.3 自然語

7、言理解,語言 自然語言、人造語言、機器語言 “理解”的標準1.4.4 自動程序設(shè)計 根據(jù)不同目的描述來編寫的計算機程序 促進人工智能系統(tǒng)的發(fā)展,1.4 研究及應(yīng)用,1.4.5 專家系統(tǒng),是一個智能化的計算機程序系統(tǒng) 和傳統(tǒng)的計算機程序之間有本質(zhì)區(qū)別1.4.6 機器學習 是機器獲取智能的途徑 學習是一個有特定目的的知識獲取過程 學習的本質(zhì)是對信息的理解與應(yīng)用 有多種學習方法,1.4 研究及應(yīng)用,1.4.7 神

8、經(jīng)網(wǎng)絡(luò),神經(jīng)計算機 在其它領(lǐng)域中的廣泛應(yīng)用1.4.8 機器人學 操作機器人 智能機器人 機器人的廣泛應(yīng)用 促進人工智能的發(fā)展,1.4 研究及應(yīng)用,1.4.9 模式識別,是計算機對環(huán)境識別的需要 是對人類環(huán)境的感知模擬1.4.10 機器視覺 人類80％以上的外部信息來自視覺 低層視覺與高層視覺 前沿研究領(lǐng)域 廣泛應(yīng)用,1.4 研究及應(yīng)用,1.4.11 智能控制,驅(qū)動智能機器自主地實現(xiàn)其目標的過程 是一個

9、定性和定量的混合控制過程 是當今自動控制的最高水平1.4.12 智能檢索 是信息時代來臨的需要 智能檢索系統(tǒng)所面臨的三大問題,1.4 研究及應(yīng)用,1.4.13 智能調(diào)度與指揮,尋找最佳調(diào)度和組合 NP完全類問題的求解 軍事指揮系統(tǒng)等領(lǐng)域1.4.14 分布式人工智能與Agent 是傳統(tǒng)人工智能的延伸和擴展 研究目標是創(chuàng)建一種能描述自然系統(tǒng)和社會系統(tǒng)的精確概念模型,1.4 研究及應(yīng)用,1.4.15 計算智能與進化計

10、算,計算智能包括神經(jīng)計算、模糊計算、進化計算等 進化計算的理論基礎(chǔ)是生物進化論1.4.16 數(shù)據(jù)挖掘與知識發(fā)現(xiàn) 知識獲取 數(shù)據(jù)庫知識挖掘 數(shù)據(jù)庫中知識發(fā)現(xiàn)的四個特征,1.4 研究及應(yīng)用,1.4.17 人工生命,人工生命概念的提出 理論基礎(chǔ)與研究方法 研究內(nèi)容1.4.18 系統(tǒng)與語言工具 計算機系統(tǒng)的一些概念得到發(fā)展 新的編程語言與專用開發(fā)工具,1.4 研究及應(yīng)用,1.5 課程概要,簡述人工智能的起源與發(fā)展

11、 概括地論述知識表示的各種主要方法 討論常用的搜索原理和推理求解技術(shù) 介紹近期人工智能技術(shù)和方法的熱點 詳細地分析人工智能的主要應(yīng)用領(lǐng)域 敘述人工智能的爭議與展望,第二章 知識表示方法,2.1 狀態(tài)空間法2.2 問題歸約法2.3 謂詞邏輯法2.4 語義網(wǎng)絡(luò)法2.5 其他方法2.6 小結(jié),2.1狀態(tài)空間法（State Space Representatio

12、n）,問題求解技術(shù)主要是兩個方面：問題的表示求解的方法狀態(tài)空間法狀態(tài)（state）算符（operator）狀態(tài)空間方法,2.1.1 問題狀態(tài)描述,定義狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合。算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。問題的狀態(tài)空間：是一個表示該問題全部可能狀態(tài)及其關(guān)系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。,2.1 狀態(tài)空間法

13、,2. 狀態(tài)空間表示概念詳釋,例如下棋、迷宮及各種游戲。,MiddleState,GoalState,,,2.1 狀態(tài)空間法,例:三數(shù)碼難題（3 puzzle problem）,,,,,,,初始棋局,目標棋局,2.1 狀態(tài)空間法,有向圖路徑代價圖的顯示說明圖的隱示說明,2.1.2 狀態(tài)圖示法,A,,B,2.1 狀態(tài)空間法,2.1.3 狀態(tài)空間表示舉例,產(chǎn)生式系統(tǒng)（production system）一個總數(shù)據(jù)庫：它含有

14、與具體任務(wù)有關(guān)的信息隨著應(yīng)用情況的不同，這些數(shù)據(jù)庫可能簡單，或許復雜。一套規(guī)則：它對數(shù)據(jù)庫進行操作運算。每條規(guī)則由左部鑒別規(guī)則的適用性或先決條件以及右部描述規(guī)則應(yīng)用時所完成的動作。一個控制策略：它確定應(yīng)該采用哪一條適用規(guī)則，而且當數(shù)據(jù)庫的終止條件滿足時，就停止計算。,2.1 狀態(tài)空間法,狀態(tài)空間表示舉例,例：猴子和香蕉問題,2.1 狀態(tài)空間法,解題過程,用一個四元表列（W，x，Y，z）來表示這個問題狀態(tài).,這個問題的操作（算符）如下

15、：2 goto（U）表示猴子走到水平位置U或者用產(chǎn)生式規(guī)則表示為（W，0，Y，z） goto（U） （U，0，Y，z）,,2.1 狀態(tài)空間法,pushbox（V）猴子把箱子推到水平位置V，即有（W，0，W，z） pushbox（V） （V，0，V，z）,climbbox猴子爬上箱頂，即有（W，0，W，z） climbbox （W，1，W，z）,,,2.1

16、狀態(tài)空間法,grasp猴子摘到香蕉，即有（c，1，c，0） grasp （c，1，c，1）,該初始狀態(tài)變換為目標狀態(tài)的操作序列為{goto(b),pushbox(c),climbbox,grasp},,2.1 狀態(tài)空間法,2.1 狀態(tài)空間法,猴子和香蕉問題自動演示：,2.1 狀態(tài)空間法,2.2 問題歸約法（Problem Reduction Representation）,問題歸

17、約表示的組成部分：一個初始問題描述；一套把問題變換為子問題的操作符；一套本原問題描述。,問題歸約的實質(zhì)：從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。,2.2 問題規(guī)約法,2.2.1 問題歸約描述 （Problem Reduction Description）,梵塔難題,2.2 問題規(guī)約法,解題過程（3個圓盤問題）,2.2 問題規(guī)約法,多圓盤梵塔難題演示,2

18、.2 問題規(guī)約法,2.2.2與或圖表示,1.與圖、或圖、與或圖,2.2 問題規(guī)約法,,2.2 問題規(guī)約法,2.一些關(guān)于與或圖的術(shù)語,2.2 問題規(guī)約法,3.定義,2.2 問題規(guī)約法,不可解節(jié)點的一般定義沒有后裔的非終葉節(jié)點為不可解節(jié)點。全部后裔為不可解的非終葉節(jié)點且含有或后繼節(jié)點，此非終葉節(jié)點才是不可解的。后裔至少有一個為不可解的非終葉節(jié)點且含有與后繼節(jié)點，此非終葉節(jié)點才是不可解的。與或圖構(gòu)成規(guī)則,2.2 問題規(guī)約法,梵塔問題歸

19、約圖,,（322） （333）,,,,,,,,,,,,,,2.2 問題規(guī)約法,2.3 謂詞邏輯法,邏輯語句形式語言,2.3.1 謂詞演算 1. 語法和語義基本符號謂詞符號、變量符號、函數(shù)符號、 常量符號、括號和逗號原子公式,連詞和量詞(Connective &Quantifiers)連詞與及合?。╟onjunction)或及析?。╠isjunction）蘊涵（Implication）非（Not）量詞

20、全稱量詞（Universal Quantifiers)存在量詞 (Existential Quantifiers),2.3 謂詞邏輯法,2.3.2 謂詞公式原子公式的的定義：用P(x1，x2，…，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,…，xn為客體變量或變元。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式

21、。,2.3 謂詞邏輯法,合適公式（WFF，well-formed formulas）合適公式的遞歸定義合適公式的性質(zhì)合適公式的真值等價（Equivalence),2.3 謂詞邏輯法,2.3.3 置換與合一,置換概念假元推理全稱化推理綜合推理定義就是在該表達式中用置換項置換變量性質(zhì)可結(jié)合的不可交換的,2.3 謂詞邏輯法,合一（Unification)合一：尋找項對變量的置換，以使兩表達式一致?？珊弦唬喝绻粋€

22、置換s作用于表達式集{Ei}的每個元素，則我們用{Ei} s來表示置換例的集。我們稱表達式集{Ei}是可合一的。,2.3 謂詞邏輯法,2.4 語義網(wǎng)絡(luò)法 （Semantic Network Representation）,語義網(wǎng)絡(luò)的結(jié)構(gòu)定義組成部分詞法結(jié)構(gòu)過程語義,表示占有關(guān)系和其它情況例： 小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。,選擇語義基元試圖用一組基元來表示知識，以便簡化表示，并

23、可用簡單的知識來表示更復雜的知識。,2.4 語義網(wǎng)絡(luò)法,2.4. 1 二元語義網(wǎng)絡(luò)的表示,2.4.2 多元語義網(wǎng)絡(luò)的表示,謂詞邏輯與語義網(wǎng)絡(luò)等效,2.4 語義網(wǎng)絡(luò)法,多元語義網(wǎng)絡(luò)表示的實質(zhì)把多元關(guān)系轉(zhuǎn)化為一組二元關(guān)系的組合，或二元關(guān)系的合取。,2.4 語義網(wǎng)絡(luò)法,2.4.3 連接詞和量化的表示,合取三元變?yōu)槎M合析取加注析取界限，并標記DIS，以免引起混淆。否定兩種表示方式：～或標注NEG界限。,2.4 語義網(wǎng)絡(luò)法,蘊

24、涵在語義網(wǎng)絡(luò)中可用標注ANTE和CONSE界限來表示蘊涵關(guān)系。ANTE和CONSE界限分別用來把與先決條件(antecedent)及與結(jié)果(consequence)相關(guān)的鏈聯(lián)系在一起。量化存在量化—ISA鏈全稱量化—分割法,2.4 語義網(wǎng)絡(luò)法,2.5其他方法（Others),框架（Frame）表示框架是一種結(jié)構(gòu)化表示法，通常采用語義網(wǎng)絡(luò)中的節(jié)點-槽-值表示結(jié)構(gòu)。劇本（Script）表示劇本是框架的一種特殊形式，它用一組槽來

25、描述某些事件的發(fā)生序列。過程（Procedure）表示過程式表示就是將有關(guān)某一問題領(lǐng)域的知識，連同如何使用這些知識的方法，均隱式地表達為一個求解問題的過程。,2.6 小結(jié)（Summary）,本章所討論的知識表示問題是人工智能研究的核心問題之一。知識表示方法很多，本章介紹了其中的7種，有圖示法和公式法，陳述式表示和過程式表示等。,第三章 搜索推理技術(shù),3.6 產(chǎn)生式系統(tǒng)3.7 系統(tǒng)組織技術(shù)3.8 不確定性推理3.9 非單調(diào)推

26、理3.10 小結(jié),3.1 圖搜索策略3.2 盲目搜索3.3 啟發(fā)式搜索3.4 消解原理3.5 規(guī)則演繹系統(tǒng),3.1 圖搜索策略,圖搜索控制策略一種在圖中尋找路徑的方法。圖中每個節(jié)點對應(yīng)一個狀態(tài)，每條連線對應(yīng)一個操作符。這些節(jié)點和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標記。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。圖搜索過程圖,開始,把S放入OPEN表,OPEN表為空表

27、？,把第一個節(jié)點(n)從OPEN表移至CLOSED表,n為目標節(jié)點嗎？,把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針,修改指針方向,重排OPEN表,失敗,成功,,,,,,,,,圖3.1 圖搜索過程框圖,是,是,否,否,,3.1 圖搜索策略,3.2 盲目搜索,特點：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價搜索等。,開始,把S放入OPEN表,OPEN表為空表？,把第一個節(jié)點(n)從OPEN表移至CLOSED表,是否

28、有后繼節(jié)點為目標節(jié)點？,擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針,失敗,成功,,,,,,,,圖3.2 寬度優(yōu)先算法框圖,是,否,是,否,3.2 盲目搜索,例子八數(shù)碼難題（8-puzzle problem）,（初始狀態(tài)）,規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉(zhuǎn)。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解（目標節(jié)點）。,3.2 盲目搜索,1,圖3.4

29、八數(shù)碼難題的寬度優(yōu)先搜索樹,3.2 盲目搜索,3.2.2 深度優(yōu)先搜索,定義,首先擴展最新產(chǎn)生的(即最深的)節(jié)點。,算法,防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度——深度界限。 與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。（算法框圖見教材）,3.2 盲目搜索,3.2.3 等代價搜索,定義,是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑

30、斷層進行擴展。 搜索樹中每條連接弧線上的有關(guān)代價,表示時間、距離等花費。,算法,若所有連接弧線具有相等代價，則簡化為寬度優(yōu)先搜索算法。,3.2 盲目搜索,開始,把S放入OPEN表,OPEN表為空表？,把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED表,是否有后繼節(jié)點為目標節(jié)點？,失敗,成功,,,,,,,圖3.2 等代價搜索算法框圖,是,否,是,否,令g(s)=0,S是否目標節(jié)點？,,,是,成功,擴展i，計算其后

31、繼節(jié)點j的g(j)，并把后繼節(jié)點放入OPEN表,,,否,3.2 盲目搜索,3.3 啟發(fā)式搜索,特點：重排OPEN表，選擇最有希望的節(jié)點加以擴展種類：有序搜索、A*算法等,3.3.1 啟發(fā)式搜索策略和估價函數(shù),盲目搜索可能帶來組合爆炸啟發(fā)式信息 用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。,估價函數(shù) 為獲得某些節(jié)點“希望”的啟發(fā)信息，提供一個評定侯選擴展節(jié)點的方法，以便確定哪個節(jié)點最有可能在通向目標的最佳路徑上 。

32、 f(n)——表示節(jié)點n的估價函數(shù)值 應(yīng)用節(jié)點“希望”程度（估價函數(shù)值）重排OPEN表,3.3.2 有序搜索,實質(zhì),選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。,3.3 啟發(fā)式搜索,開始,把S放入OPEN表，計算估價函數(shù) f (s),OPEN表為空表？,選取OPEN表中f值最小的節(jié)點i放入CLOSED表,i為目標節(jié)點嗎？,擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新

33、排序，調(diào)整親子關(guān)系及指針,失敗,成功,,,,,,,,圖3.9 有序搜索算法框圖,是,否,是,否,3.3 啟發(fā)式搜索,算法,例子,八數(shù)碼難題（8-puzzle problem）,八數(shù)碼難題的有序搜索樹見下圖：,3.3 啟發(fā)式搜索,5,7,1,4,5,6,3,2,圖3.10 八數(shù)碼難題的有序搜索樹,3.3 啟發(fā)式搜索,3.3.3 A*算法,估價函數(shù)的定義：對節(jié)點n定義f*(n)=g*(n)+h*(n) ,表示從S開始約束通過節(jié)點n的一條

34、最佳路徑的代價。希望估價函數(shù)f 定義為：f(n)=g(n)+h(n) —— g是g*的估計 ，h是h*的估計A*算法的定義：定義1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進行的，則稱該過程為A算法。 定義2 在A算法中，如果對所有的x存在h(x)≤h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保

35、守的估計。 定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?3.3 啟發(fā)式搜索,3.4 消解原理,回顧：原子公式（atomic formulas）文字—一個原子公式及其否定。子句—由文字的析取組成的合適公式。消解—對謂詞演算公式進行分解和化簡，消去一些符號，以求得導出子句。,例子:,將下列謂詞演算公式化為一個子句集(?x)｛P(x)?｛(?y

36、)［P(y)?P(f(x,y))］∧～(?y)［Q(x,y)?P(y)］｝｝,,,開始：消去蘊涵符號 只應(yīng)用∨和～符號，以～A∨B替換A?B。,(1) (?x)｛～P(x)∨{(?y)［~P(y)∨P(f(x,y))］∧～(?y)［~Q(x,y)∨P(y)］}},3.4 消解原理,(2) 減少否定符號的轄域 每個否定符號～最多只用到一個謂詞符號上，并反復應(yīng)用狄·摩根定律。(3) 對變量標準化

37、 對啞元（虛構(gòu)變量）改名，以保證每個量詞有其自己唯一的啞元。,3.4 消解原理,(2) (?x)｛～P(x)∨｛(?y)［～P(y)∨P(f(x,y))］∧(?y)［Q(x,y)∧～P(y)］｝｝,(3) (?x)｛～P(x)∨｛(?y)［～P(y)∨P(f(x,y))］∧(?w)［Q(x,w)∧～P(w)］｝｝,(4) 消去存在量詞 以Skolem函數(shù)代替存在量詞內(nèi)的約束變量，然后消去存在量詞化為前束形

38、把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。 前束形={前綴} {母式} 全稱量詞串 無量詞公式,(4) (?x)｛～P(x)∨{(?y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x)）∧～P(g(x))］｝｝式中，w=g(x)為一Skolem函數(shù)。,(5

39、) (?x)(?y)｛～P(x)∨｛［～P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝,3.4 消解原理,把母式化為合取范式 任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(7) 消去全稱量詞 所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。,3.4 消解原理,(6) (?x)(?y)｛［～P(x)∨～P(y)∨P(f(x,y)

40、)］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝,(7) ｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝,(8) 消去連詞符號∧ 用{A,B}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9) 更換變量名稱 可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。,3.4 消解原

41、理,(8) ～P(x)∨～P(y)∨P(f(x,y))～P(x)∨Q(x,g(x))～P(x)∨～P(g(x)),(9) ～P(x1)∨～P(y)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］,3.4.2 消解推理規(guī)則,消解式的定義令L1，L2為兩任意原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那

42、么通過消解可以從這兩個父輩子句推導出一個新子句(α∨β)σ。這個新子句叫做消解式。,消解式求法,取各子句的析取，然后消去互補對。,3.4 消解原理,3.4.3 含有變量的消解式,3.4 消解原理,3.4.4 消解反演求解過程,消解反演 給出{S}，L否定L，得～L；把～L添加到S中去；把新產(chǎn)生的集合｛～L，S｝化成子句集；應(yīng)用消解原理，力圖推導出一個表示矛盾的空子句,例子—儲蓄問題 前提：每個儲蓄錢的人都獲得

43、利息。 結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢,3.4 消解原理,(1）規(guī)定原子公式： S(x,y) 表示 “x儲蓄y” M(x) 表示 “x是錢” I(x) 表示 “x是利息” E(x，y) 表示 “x獲得y”,(2）用謂詞公式表示前提和結(jié)論：前提：(?x)[(?y)(S(x,y))∧M

44、(y)]?[(?y)(I(y)∧E(x,y))]結(jié)論：～(?x)I(x)? (?x)(?y)(M(y)→～S(x,y)),(3) 化為子句形,證明：,3.4 消解原理,把前提化為子句形：1) ～S(x,y)∨～M(y)∨I(f(x))2) ～S(x,y)∨～M(y)∨E(x,f(x)),把結(jié)論化為子句形：3) ～I(z)4) S(a,b)5) M(b),(4) 消解反演求NIL,圖3.12 儲蓄問題反演樹,3.4 消解原

45、理,反演求解過程從反演樹求取答案步驟把由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定之否定的子句中去。按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。實質(zhì)把一棵根部有NIL的反演樹變換為根部帶有回 答語句的一棵證明樹。,3.4 消解原理,3.5 規(guī)則演繹系統(tǒng),定義 基于規(guī)則的問題求解系統(tǒng)運用If→Then規(guī)則來建立，每個if可能與某斷言(assertion)

46、集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項。,3.5.1 規(guī)則正向演繹系統(tǒng),定義 正向規(guī)則演繹系統(tǒng)是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。 求解過程事實表達式的與或形變換 在基于規(guī)則的正向演繹系統(tǒng)

47、中，我們把事實表示為非蘊涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。,3.5 規(guī)則演繹系統(tǒng),事實表達式的與或圖表示,Q(w,A)∧{[～R(v)∧～P(v)]∨～S(A,v)},Q(w,A),[～R(v)∧～P(v)]∨～S(A,v),,,～R(v)∧～P(v),～S(A,v),～R(v),～P(v),,,圖3.15 一個事實表達式的與或樹表示,3.5 規(guī)則演繹系統(tǒng),與或圖的F規(guī)則變換 這些規(guī)則是建立在某個問題轄域中普

48、通陳述性知識的蘊涵公式基礎(chǔ)上的。我們把允許用作規(guī)則的公式類型限制為下列形式： L ? W 式中：L是單文字；W為與或形的唯一公式。,3.5 規(guī)則演繹系統(tǒng),3.5.2 規(guī)則逆向演繹系統(tǒng),定義 逆向規(guī)則演繹系統(tǒng)是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。 求解過程目標表達式的與或形式與或圖的B規(guī)則變換作為終止條件的事實節(jié)點的一致解

49、圖,3.5 規(guī)則演繹系統(tǒng),正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標和表示事實的兩個與或圖結(jié)構(gòu)組成。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。,3.5.3 規(guī)則雙向演繹系統(tǒng),3.5 規(guī)則演繹系統(tǒng),3.6 產(chǎn)生式系統(tǒng),定義：用來描述若干個不同的以一個基本概念為基礎(chǔ)的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。實質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：用事實表

50、示靜態(tài)知識，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)則，因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)。,3.6.1 產(chǎn)生式系統(tǒng)的組成,控制策略,,,,圖3.22 產(chǎn)生式系統(tǒng)的主要組成,總數(shù)據(jù)庫,產(chǎn)生式規(guī)則,3.6 產(chǎn)生式系統(tǒng),選擇規(guī)則到執(zhí)行操作的步驟 1 匹配 把當前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。 2 沖突 當有一條以上規(guī)則的條件部分和

51、當前數(shù)據(jù)庫相匹配時，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。 3 操作 操作就是執(zhí)行規(guī)則的操作部分。,3.6 產(chǎn)生式系統(tǒng),3.6.2 產(chǎn)生式系統(tǒng)的推理,正向推理：從一組表示事實的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。 逆向推理：從表示目標的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實謂詞或命題成立，即首先提出一批假設(shè)目標，然后逐一驗證這些假設(shè)。 雙向推理：雙向推理的推理

52、策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標的匹配。,3.6 產(chǎn)生式系統(tǒng),3.7 系統(tǒng)組織技術(shù),3.7.1 議程表,系統(tǒng)組織技術(shù)首先將一個大系統(tǒng)或復雜系統(tǒng)中的知識劃分為一組相對獨立的模塊，然后考慮各子模塊間在求解時的合作問題。,議程表是一個系統(tǒng)能夠執(zhí)行的任務(wù)表列。與每個任務(wù)有關(guān)的有兩件事，即提出該任務(wù)的理由和表示對該任務(wù)是有用的證據(jù)總權(quán)的評價。,3.7.2 黑板法,黑板法由一組稱為知識資源(K

53、S)的獨立模塊和一塊黑板組成求解系統(tǒng)。知識資源含有系統(tǒng)中專門領(lǐng)域的知識，而黑板則是一切KS可以訪問的公用數(shù)據(jù)結(jié)構(gòu)。,3.7 系統(tǒng)組織技術(shù),3.7.3 Δ-極小搜索法,提供了一種選擇最有希望假設(shè)的技術(shù)。,3.8 不確定性推理,以模糊集理論為基礎(chǔ)的方法以概率為基礎(chǔ)的方法,3.8.1 關(guān)于證據(jù)的不確定性,不確定性推理是研究復雜系統(tǒng)不完全性和不確定性的有力工具。有兩種不確定性，即關(guān)于證據(jù)的不確定性和關(guān)于結(jié)論的不確定性。,3.8.2 關(guān)于結(jié)論

54、的不確定性,關(guān)于結(jié)論的不確定性也叫做規(guī)則的不確定性，它表示當規(guī)則的條件被完全滿足時，產(chǎn)生某種結(jié)論的不確定程度。,3.8.3 多個規(guī)則支持同一事實時的不確定性,基于模糊集理論的方法基于概率論的方法,3.8 不確定性推理,3.9 非單調(diào)推理,定義 非單調(diào)推理用來處理那些不適合用謂詞邏輯表示的知識。 它能夠較好地處理不完全信息、不斷變化的情況以及求解復雜問題過程中生成的假設(shè)，具有較為有效的求解效率

55、。,3.9.1 缺省推理,定義1：如果X不知道，那么得結(jié)論Y。定義2：如果X不能被證明，那么得結(jié)論Y。 定義3：如果X不能在某個給定的時間內(nèi)被證明，那么得結(jié)論Y。,3.9 非單調(diào)推理,3.9.2 非單調(diào)推理系統(tǒng)正確性維持系統(tǒng)用以保持其它程序所產(chǎn)生的命題 之間的相容性。一旦發(fā)現(xiàn)某個不相容，它就調(diào)出 自己的推理機制，面向從屬關(guān)系的回溯，并通過 修改最小的信念集來消除不相容。,3.10 小結(jié),經(jīng)典搜索推理技術(shù)圖搜索技

56、術(shù)消解反演 高級搜索推理技術(shù)規(guī)則演繹系統(tǒng)產(chǎn)生式系統(tǒng)系統(tǒng)組織技術(shù)不確定性推理非單調(diào)推理,第四章 計算智能(1),神經(jīng)計算模糊計算,4.1概述,信息科學與生命科學的相互交叉、相互滲透和相互促進是現(xiàn)代科學技術(shù)發(fā)展的一個顯著特點。 計算智能涉及神經(jīng)網(wǎng)絡(luò)、模糊邏輯、進化計算和人工生命等領(lǐng)域，它的研究和發(fā)展正反映了當代科學技術(shù)多學科交叉與集成的重要發(fā)展趨勢。,什么是計算智能,把神經(jīng)網(wǎng)絡(luò)（NN）歸類于人工智能（AI）可能不大合適

57、，而歸類于計算智能（CI）更能說明問題實質(zhì)。進化計算、人工生命和模糊邏輯系統(tǒng)的某些課題，也都歸類于計算智能。 計算智能取決于制造者（manufacturers）提供的數(shù)值數(shù)據(jù)，不依賴于知識；另一方面，人工智能應(yīng)用知識精品（knowledge tidbits）。人工神經(jīng)網(wǎng)絡(luò)應(yīng)當稱為計算神經(jīng)網(wǎng)絡(luò)。,4.1 概述,計算智能與人工智能的區(qū)別和關(guān)系,,,,,,輸入,人類知識(＋)傳感輸入,知識(＋)傳感數(shù)據(jù),計算(＋)傳感器,C－數(shù)值的,

58、A－符號的,B－生物的,輸入,復雜性,,復雜性,,BNN,BPR,BI,ANN,APR,AI,CNN,CPR,CI,,,,,,,,,,,,,4.1 概述,A－Artificial，表示人工的（非生物的）；B－Biological，表示物理的＋化學的＋ （？）＝生物的； C－Computational，表示數(shù)學＋計算機 計算智能是一種智力方式的低層認知，它與人工智能的

59、區(qū)別只是認知層次從中層下降至低層而已。中層系統(tǒng)含有知識（精品），低層系統(tǒng)則沒有。,4.1 概述,當一個系統(tǒng)只涉及數(shù)值（低層）數(shù)據(jù)，含有模式識別部分，不應(yīng)用人工智能意義上的知識，而且能夠呈現(xiàn)出：（1）計算適應(yīng)性；（2）計算容錯性；（3）接近人的速度；（4）誤差率與人相近， 則該系統(tǒng)就是計算智能系統(tǒng)。當一個智能計算系統(tǒng)以非數(shù)值方式加上知識（精品）值，即成為人工智能系統(tǒng)。,4.1 概述,1960年威德羅和霍夫率先把神經(jīng)網(wǎng)絡(luò)用于自

60、動控制研究。60年代末期至80年代中期，神經(jīng)網(wǎng)絡(luò)控制與整個神經(jīng)網(wǎng)絡(luò)研究一樣，處于低潮。 80年代后期以來，隨著人工神經(jīng)網(wǎng)絡(luò)研究的復蘇和發(fā)展，對神經(jīng)網(wǎng)絡(luò)控制的研究也十分活躍。這方面的研究進展主要在神經(jīng)網(wǎng)絡(luò)自適應(yīng)控制和模糊神經(jīng)網(wǎng)絡(luò)控制及其在機器人控制中的應(yīng)用上。,4.2 神經(jīng)計算4.2.1 人工神經(jīng)網(wǎng)絡(luò)研究的進展,人工神經(jīng)網(wǎng)絡(luò)的特性,并行分布處理非線性映射通過訓練進行學習適應(yīng)與集成硬件實現(xiàn),4.2 神經(jīng)計算,,圖4.2

61、 神經(jīng)元模型,4.2.2 人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu),圖4.2中的神經(jīng)元單元由多個輸入xi，i=1,2,...,n和一個輸出y組成。中間狀態(tài)由輸入信號的權(quán)和表示，而輸出為（4.1） 式中，?j為神經(jīng)元 單元的偏置，wji為

62、 連接權(quán)系數(shù),4.2 神經(jīng)計算,圖4.3 神經(jīng)元中的某些變換（激發(fā)）函數(shù),(a) 二值函數(shù)(b) S形函數(shù) (c) 雙曲正切函數(shù),n為輸入信號數(shù)目，yj為神經(jīng)元輸出，t為時間，f(_)為輸出變換函數(shù)，如圖4.3。,4.2 神經(jīng)計算,人工神經(jīng)網(wǎng)絡(luò)的基本特性和結(jié)構(gòu),人工神經(jīng)網(wǎng)絡(luò)是具有下列特性的有向圖： 對于每個節(jié)點 i 存在一個狀態(tài)變量

63、xi ； 從節(jié)點 j 至節(jié)點 i ，存在一個連接權(quán)系統(tǒng)數(shù)wij； 對于每個節(jié)點 i ，存在一個閾值? i；對于每個節(jié)點 i ，定義一個變換函數(shù)fi ；對于最一般的情況，此函數(shù)取 形式。,4.2 神經(jīng)計算,圖4.4 反饋網(wǎng)絡(luò) 圖4.5 前饋網(wǎng)絡(luò),遞歸（反饋）網(wǎng)絡(luò):在遞歸網(wǎng)絡(luò)中，多個神經(jīng)元互連以組織一個互連神經(jīng)網(wǎng)絡(luò)，如圖5.3。前饋網(wǎng)絡(luò):前饋網(wǎng)絡(luò)具有遞階

64、分層結(jié)構(gòu)，由同層神經(jīng)元間不存在互連的層級組成，如圖5.4。,4.2 神經(jīng)計算,人工神經(jīng)網(wǎng)絡(luò)的主要學習算法,有師學習算法：能夠根據(jù)期望的和實際的網(wǎng)絡(luò)輸出（對應(yīng)于給定輸入）間的差來調(diào)整神經(jīng)元間連接的強度或權(quán)。無師學習算法：不需要知道期望輸出。強化學習算法：采用一個“評論員”來評價與給定輸入相對應(yīng)的神經(jīng)網(wǎng)絡(luò)輸出的優(yōu)度（質(zhì)量因數(shù)）。強化學習算法的一個例子是遺傳算法（GA）。,4.2 神經(jīng)計算,人工神經(jīng)網(wǎng)絡(luò)的典型模型,4.2 神經(jīng)計算,續(xù)前表

65、：,4.2 神經(jīng)計算,4.2.4 基于神經(jīng)網(wǎng)絡(luò)的知識表示與推理,基于神經(jīng)網(wǎng)絡(luò)的知識表示 在這里，知識并不像在產(chǎn)生式系統(tǒng)中那樣獨立地表示為每一條規(guī)則，而是將某一問題的若干知識在同一網(wǎng)絡(luò)中表示。例如，在有些神經(jīng)網(wǎng)絡(luò)系統(tǒng)中，知識是用神經(jīng)網(wǎng)絡(luò)所對應(yīng)的有向權(quán)圖的鄰接矩陣及閾值向量表示的。,4.2 神經(jīng)計算,基于神經(jīng)網(wǎng)絡(luò)的推理,基于神經(jīng)網(wǎng)絡(luò)的推理是通過網(wǎng)絡(luò)計算實現(xiàn)的。把用戶提供的初始證據(jù)用作網(wǎng)絡(luò)的輸入，通過網(wǎng)絡(luò)計算最終得到輸

66、出結(jié)果。 一般來說，正向網(wǎng)絡(luò)推理的步驟如下：把已知數(shù)據(jù)輸入網(wǎng)絡(luò)輸入層的各個節(jié)點。利用特性函數(shù)分別計算網(wǎng)絡(luò)中各層的輸出。用閾值函數(shù)對輸出層的輸出進行判定，從而得到輸出結(jié)果。,4.2 神經(jīng)計算,定義4.1 模糊集合(Fuzzy Sets),論域U到[0,1]區(qū)間的任一映射 ，即 ，都確定U的一個模糊子集F； 稱為F的隸屬函數(shù)或隸屬度。在論域U中，可把模糊

67、子集表示為元素u與其隸屬函數(shù) 的序偶集合，記為： (4.7),4.3 模糊計算4.3.1 模糊集合、模糊邏輯及其運算,定義4.2 模糊支集、交叉點及模糊單點,若模糊集是論域U中所有滿足 的元素u構(gòu)成的集合，則稱該集合為模糊集F的支集。當u滿足 ，

68、稱為交叉點。當模糊支集為U中一個單獨點，且u滿足 則稱模糊集為模糊單點。,4.3 模糊計算,定義4.3 模糊集的運算,設(shè)A和B為論域U中的兩個模糊集，其隸屬函數(shù)分別為 和 ，則對于所有 ，存在下列運算：A與B的并（邏輯或）記為 ，其隸屬函數(shù)定義為：

69、 (4.10)A與B的交（邏輯與）記為 ，其隸屬函數(shù)定義為： (4.11)A的補（邏輯非）記為 ，其傳遞函數(shù)定義為：