人工智能與專家系統,研究生課程,第一章 緒論,1.1 人工智能的定義和發展 1.2 人類智能和人工智能 1.3 人工智能的各種認知觀 1.4 人工智能的研究與應用領域 1.5 課程概要,1.1.1 人工智能的定義,幾種定義 智能機器（intelligent machine） 人工智能（學科） 人工智能（能力） 人工智能（擬人思維、行為 ） 人工智能（理性思維、行為 ）,1.1 定義和發展,1.1.2 人工智能的起源與發展,孕育期（1956年前） 數理邏輯學科（弗雷治、維納等 ） 計算的新思想（丘奇、圖靈 等） 形成期（1956-1970年） 1956年，第一次人工智能的研討會 1969年，第一屆國際人工智能聯合會議 1970年，人工智能國際雜志創刊,1.1 定義和發展,1.1.2 人工智能的起源與發展,發展期（1970年） 進一步研究AI基本原理方法和技術 進行實用化研究 專家系統與知識工程 機器定理證明 智能機器人 智能控制等 從“一枝獨秀”到“百花齊放”,1.1 定義和發展,1.2 人類智能和人工智能,1.2.1 智能信息處理系統的假設 人是一種智能信息處理系統 物理符號系統的六種基本功能 物理符號系統的假設 推論一 推論二 推論三,1.2.1 智能信息處理系統的假設,人類的認知行為具有不同層次 認知生理學 認知心理學 認知信息學 認知工程學,1.2 人類智能和人工智能,1.2.2 人類智能的計算機模擬,機器智能可以模擬人類智能 智能計算機 下棋 定理證明 語言翻譯 新型智能計算機 神經計算機 量子計算機,1.2 人類智能和人工智能,1.2.3 人工智能的研究目標,近期目標 建造智能計算機代替人類的部分智力勞動 遠期目標 用自動機模仿人類的思維過程和智能行為,1.2 人類智能和人工智能,1.3 人工智能的各種認知觀,符號主義（Symbolicism） 基于物理符號系統假設和有限合理性原理 連接主義（Connectionism） 基于神經網絡及其間的連接機制與學習算法 行為主義（Actionism） 基于控制論及感知動作型控制系統,1.4 人工智能的研究及應用領域,人工智能的基本技術 知識表示（Knowledge Representation） 狀態空間法、問題歸約法、謂詞邏輯法 推理搜索（Searching & Reasoning） 啟發式搜索、消解原理、不確定性推理 計算智能（Computational Intelligence） 模糊計算、神經計算、進化計算 構成技術（系統與語言） 產生式系統、LISP語言、Prolog語言,1.4.1 問題求解,問題的表示、分解、搜索、歸約等 進行復雜的數學公式符號運算求解 1.4.2 邏輯推理與定理證明 通過對事實數據庫的操作來證明定理 多種證明方法 幾何定理證明的“吳氏方法”,1.4 研究及應用,1.4.3 自然語言理解,語言 自然語言、人造語言、機器語言 “理解”的標準 1.4.4 自動程序設計 根據不同目的描述來編寫的計算機程序 促進人工智能系統的發展,1.4 研究及應用,1.4.5 專家系統,是一個智能化的計算機程序系統 和傳統的計算機程序之間有本質區別 1.4.6 機器學習 是機器獲取智能的途徑 學習是一個有特定目的的知識獲取過程 學習的本質是對信息的理解與應用 有多種學習方法,1.4 研究及應用,1.4.7 神經網絡,神經計算機 在其它領域中的廣泛應用 1.4.8 機器人學 操作機器人 智能機器人 機器人的廣泛應用 促進人工智能的發展,1.4 研究及應用,1.4.9 模式識別,是計算機對環境識別的需要 是對人類環境的感知模擬 1.4.10 機器視覺 人類80以上的外部信息來自視覺 低層視覺與高層視覺 前沿研究領域 廣泛應用,1.4 研究及應用,1.4.11 智能控制,驅動智能機器自主地實現其目標的過程 是一個定性和定量的混合控制過程 是當今自動控制的最高水平 1.4.12 智能檢索 是信息時代來臨的需要 智能檢索系統所面臨的三大問題,1.4 研究及應用,1.4.13 智能調度與指揮,尋找最佳調度和組合 NP完全類問題的求解 軍事指揮系統等領域 1.4.14 分布式人工智能與Agent 是傳統人工智能的延伸和擴展 研究目標是創建一種能描述自然系統和社會系統的精確概念模型,1.4 研究及應用,1.4.15 計算智能與進化計算,計算智能 包括神經計算、模糊計算、進化計算等 進化計算的理論基礎是生物進化論 1.4.16 數據挖掘與知識發現 知識獲取 數據庫知識挖掘 數據庫中知識發現的四個特征,1.4 研究及應用,1.4.17 人工生命,人工生命概念的提出 理論基礎與研究方法 研究內容 1.4.18 系統與語言工具 計算機系統的一些概念得到發展 新的編程語言與專用開發工具,1.4 研究及應用,1.5 課程概要,簡述人工智能的起源與發展 概括地論述知識表示的各種主要方法 討論常用的搜索原理和推理求解技術 介紹近期人工智能技術和方法的熱點 詳細地分析人工智能的主要應用領域 敘述人工智能的爭議與展望,第二章 知識表示方法,2.1 狀態空間法 2.2 問題歸約法 2.3 謂詞邏輯法 2.4 語義網絡法 2.5 其他方法 2.6 小結,2.1狀態空間法 （State Space Representation）,問題求解技術主要是兩個方面： 問題的表示 求解的方法 狀態空間法 狀態（state） 算符（operator） 狀態空間方法,2.1.1 問題狀態描述,定義 狀態：描述某類不同事物間的差別而引入的一組最少變量q0，q1，qn的有序集合。 算符：使問題從一種狀態變化為另一種狀態的手段稱為操作符或算符。 問題的狀態空間：是一個表示該問題全部可能狀態及其關系的圖，它包含三種說明的集合，即三元狀態（S，F，G）。,2.1 狀態空間法,2. 狀態空間表示概念詳釋,例如下棋、迷宮及各種游戲。,Middle State,Goal State,2.1 狀態空間法,例:三數碼難題 （3 puzzle problem）,初始棋局,目標棋局,2.1 狀態空間法,有向圖 路徑 代價 圖的顯示說明 圖的隱示說明,2.1.2 狀態圖示法,A,B,2.1 狀態空間法,2.1.3 狀態空間表示舉例,產生式系統（production system） 一個總數據庫：它含有與具體任務有關的信息隨著應用情況的不同，這些數據庫可能簡單，或許復雜。 一套規則：它對數據庫進行操作運算。每條規則由左部鑒別規則的適用性或先決條件以及右部描述規則應用時所完成的動作。 一個控制策略：它確定應該采用哪一條適用規則，而且當數據庫的終止條件滿足時，就停止計算。,2.1 狀態空間法,狀態空間表示舉例,例：猴子和香蕉問題,2.1 狀態空間法,解題過程,用一個四元表列（W，x，Y，z）來表示這個問題狀態.,這個問題的操作（算符）如下： 2 goto（U）表示猴子走到水平位置U 或者用產生式規則表示為 （W，0，Y，z） goto（U） （U，0，Y，z）,2.1 狀態空間法,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 狀態空間法,grasp猴子摘到香蕉，即有 （c，1，c，0） grasp （c，1，c，1）,該初始狀態變換為目標狀態的操作序列為 goto(b),pushbox(c),climbbox,grasp,2.1 狀態空間法,2.1 狀態空間法,猴子和香蕉問題自動演示：,2.1 狀態空間法,2.2 問題歸約法 （Problem Reduction Representation）,問題歸約表示的組成部分： 一個初始問題描述； 一套把問題變換為子問題的操作符； 一套本原問題描述。,問題歸約的實質： 從目標(要解決的問題)出發逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。,2.2 問題規約法,2.2.1 問題歸約描述 （Problem Reduction Description）,梵塔難題,2.2 問題規約法,解題過程（3個圓盤問題）,2.2 問題規約法,多圓盤梵塔難題演示,2.2 問題規約法,2.2.2與或圖表示,1.與圖、或圖、與或圖,2.2 問題規約法,2.2 問題規約法,2.一些關于與或圖的術語,2.2 問題規約法,3.定義,2.2 問題規約法,不可解節點的一般定義 沒有后裔的非終葉節點為不可解節點。 全部后裔為不可解的非終葉節點且含有或后繼節點，此非終葉節點才是不可解的。 后裔至少有一個為不可解的非終葉節點且含有與后繼節點，此非終葉節點才是不可解的。 與或圖構成規則,2.2 問題規約法,梵塔問題歸約圖,（322） （333）,2.2 問題規約法,2.3 謂詞邏輯法,邏輯語句 形式語言,2.3.1 謂詞演算 1. 語法和語義 基本符號 謂詞符號、變量符號、函數符號、 常量符號、括號和逗號 原子公式,連詞和量詞(Connective &Quantifiers) 連詞 與及合取（conjunction) 或及析?。╠isjunction） 蘊涵（Implication） 非（Not） 量詞 全稱量詞（Universal Quantifiers) 存在量詞 (Existential Quantifiers),2.3 謂詞邏輯法,2.3.2 謂詞公式 原子公式的的定義： 用P(x1，x2，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,，xn為客體變量或變元。通常把P(x1,x2,xn)叫做謂詞演算的原子公式，或原子謂詞公式。 分子謂詞公式 可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。,2.3 謂詞邏輯法,合適公式（WFF，well-formed formulas） 合適公式的遞歸定義 合適公式的性質 合適公式的真值 等價（Equivalence),2.3 謂詞邏輯法,2.3.3 置換與合一,置換 概念 假元推理 全稱化推理 綜合推理 定義 就是在該表達式中用置換項置換變量 性質 可結合的 不可交換的,2.3 謂詞邏輯法,合一（Unification) 合一：尋找項對變量的置換，以使兩表達式一致。 可合一：如果一個置換s作用于表達式集Ei的每個元素，則我們用Ei s來表示置換例的集。我們稱表達式集Ei是可合一的。,2.3 謂詞邏輯法,2.4 語義網絡法 （Semantic Network Representation）,語義網絡的結構 定義 組成部分 詞法 結構 過程 語義,表示占有關系和其它情況 例： 小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。,選擇語義基元 試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復雜的知識。,2.4 語義網絡法,2.4. 1 二元語義網絡的表示,2.4.2 多元語義網絡的表示,謂詞邏輯與語義網絡等效,2.4 語義網絡法,多元語義網絡表示的實質 把多元關系轉化為一組二元關系的組合，或二元關系的合取。,2.4 語義網絡法,2.4.3 連接詞和量化的表示,合取 三元變為二元組合 析取 加注析取界限，并標記DIS，以免引起混淆。 否定 兩種表示方式：或標注NEG界限。,2.4 語義網絡法,蘊涵 在語義網絡中可用標注ANTE和CONSE界限來表示蘊涵關系。ANTE和CONSE界限分別用來把與先決條件(antecedent)及與結果(consequence)相關的鏈聯系在一起。 量化 存在量化ISA鏈 全稱量化分割法,2.4 語義網絡法,2.5其他方法（Others),框架（Frame）表示 框架是一種結構化表示法，通常采用語義網絡中的節點-槽-值表示結構。 劇本（Script）表示 劇本是框架的一種特殊形式，它用一組槽來描述某些事件的發生序列。 過程（Procedure）表示 過程式表示就是將有關某一問題領域的知識，連同如何使用這些知識的方法，均隱式地表達為一個求解問題的過程。,2.6 小結（Summary）,本章所討論的知識表示問題是人工智能研究的核心問題之一。知識表示方法很多，本章介紹了其中的7種，有圖示法和公式法，陳述式表示和過程式表示等。,第三章 搜索推理技術,3.6 產生式系統 3.7 系統組織技術 3.8 不確定性推理 3.9 非單調推理 3.10 小結,3.1 圖搜索策略 3.2 盲目搜索 3.3 啟發式搜索 3.4 消解原理 3.5 規則演繹系統,3.1 圖搜索策略,圖搜索控制策略 一種在圖中尋找路徑的方法。 圖中每個節點對應一個狀態，每條連線對應一個操作符。這些節點和連線(即狀態與操作符)又分別由產生式系統的數據庫和規則來標記。求得把一個數據庫變換為另一數據庫的規則序列問題就等價于求得圖中的一條路徑問題。 圖搜索過程圖,開始,把S放入OPEN表,OPEN表為空表？,把第一個節點(n)從OPEN表移至CLOSED表,n為目標節點嗎？,把n的后繼節點放入OPEN表的末端，提供返回節點n的指針,修改指針方向,重排OPEN表,失敗,成功,圖3.1 圖搜索過程框圖,是,是,否,否,3.1 圖搜索策略,3.2 盲目搜索,特點：不需重排OPEN表 種類：寬度優先、深度優先、等代價搜索等。,開始,把S放入OPEN表,OPEN表為空表？,把第一個節點(n)從OPEN表移至CLOSED表,是否有后繼節點 為目標節點？,擴展n，把n的后繼節點放入OPEN表的末端，提供返回節點n的指針,失敗,成功,圖3.2 寬度優先算法框圖,是,否,是,否,3.2 盲目搜索,例子 八數碼難題（8-puzzle problem）,（初始狀態）,規定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節點。 從圖可見，要擴展26個節點，共生成46個節點之后才求得解（目標節點）。,3.2 盲目搜索,1,圖3.4 八數碼難題的寬度優先搜索樹,3.2 盲目搜索,3.2.2 深度優先搜索,定義,首先擴展最新產生的(即最深的)節點。,算法,防止搜索過程沿著無益的路徑擴展下去，往往給出一個節點擴展的最大深度深度界限。 與寬度優先搜索算法最根本的不同在于：將擴展的后繼節點放在OPEN表的前端。（算法框圖見教材）,3.2 盲目搜索,3.2.3 等代價搜索,定義,是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。 搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。,算法,若所有連接弧線具有相等代價，則簡化為寬度優先搜索算法。,3.2 盲目搜索,開始,把S放入OPEN表,OPEN表為空表？,把具有最小g(i)值的節點i從OPEN表移至CLOSED表,是否有后繼節點 為目標節點？,失敗,成功,圖3.2 等代價搜索算法框圖,是,否,是,否,令g(s)=0,S是否目標節點？,是,成功,擴展i，計算其后繼節點j的g(j)，并把后繼節點放入OPEN表,否,3.2 盲目搜索,3.3 啟發式搜索,特點：重排OPEN表，選擇最有希望的節點加以擴展 種類：有序搜索、A*算法等,3.3.1 啟發式搜索策略和估價函數,盲目搜索可能帶來組合爆炸 啟發式信息 用來加速搜索過程的有關問題領域的特征信息。,估價函數 為獲得某些節點“希望”的啟發信息，提供一個評定侯選擴展節點的方法，以便確定哪個節點最有可能在通向目標的最佳路徑上 。 f(n)表示節點n的估價函數值 應用節點“希望”程度（估價函數值）重排OPEN表,3.3.2 有序搜索,實質,選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點。,3.3 啟發式搜索,開始,把S放入OPEN表，計算估價函數 f (s),OPEN表為空表？,選取OPEN表中f值最小的節點i放入CLOSED表,i為目標節點嗎？,擴展i，得后繼節點j，計算f(j)，提供返回節點i的指針，利用f(j)對OPEN表重新排序，調整親子關系及指針,失敗,成功,圖3.9 有序搜索算法框圖,是,否,是,否,3.3 啟發式搜索,算法,例子,八數碼難題（8-puzzle problem）,八數碼難題的有序搜索樹見下圖：,3.3 啟發式搜索,5,7,1,4,5,6,3,2,圖3.10 八數碼難題的有序搜索樹,3.3 啟發式搜索,3.3.3 A*算法,估價函數的定義： 對節點n定義f*(n)=g*(n)+h*(n) ,表示從S開始約束通過節點n的一條最佳路徑的代價。 希望估價函數f 定義為：f(n)=g(n)+h(n) g是g*的估計 ，h是h*的估計 A*算法的定義： 定義1 在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據f(x)=g(x)+h(x)進行的，則稱該過程為A算法。 定義2 在A算法中，如果對所有的x存在h(x)h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。 定義3 采用h*(x)的下界h(x)為啟發函數的A算法，稱為A*算法。當h=0時，A*算法就變為有序搜索算法。,3.3 啟發式搜索,3.4 消解原理,回顧： 原子公式（atomic formulas） 文字一個原子公式及其否定。 子句由文字的析取組成的合適公式。 消解對謂詞演算公式進行分解和化簡，消去一些符號，以求得導出子句。,例子:,將下列謂詞演算公式化為一個子句集 (x)P(x)(y)P(y)P(f(x,y) (y)Q(x,y)P(y),開始： 消去蘊涵符號 只應用和符號，以AB替換AB。,(1) (x)P(x)(y)P(y)P(f(x,y)(y)Q(x,y)P(y),3.4 消解原理,(2) 減少否定符號的轄域 每個否定符號最多只用到一個謂詞符號上，并反復應用狄摩根定律。 (3) 對變量標準化 對啞元（虛構變量）改名，以保證每個量詞有其自己唯一的啞元。,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函數代替存在量詞內的約束變量，然后消去存在量詞 化為前束形 把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。 前束形=前綴 母式 全稱量詞串 無量詞公式,(4) (x)P(x)(y)P(y)P(f(x,y)Q(x,g(x)）P(g(x) 式中，w=g(x)為一Skolem函數。,(5) (x)(y)P(x)P(y)P(f(x,y)Q(x,g(x)P(g(x),3.4 消解原理,把母式化為合取范式 任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。 (7) 消去全稱量詞 所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現的全稱量詞。,3.4 消解原理,(6) (x)(y)P(x)P(y)P(f(x,y)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代替(AB)，消去符號。最后得到一個有限集，其中每個公式是文字的析取。 (9) 更換變量名稱 可以更換變量符號的名稱，使一個變量符號不出現在一個以上的子句中。,3.4 消解原理,(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)Pf(x1,y) P(x2)Qx2,g(x2) P(x3)Pg(x3),3.4.2 消解推理規則,消解式的定義 令L1，L2為兩任意原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1和L2,如果L1和L2具有最一般合一，那么通過消解可以從這兩個父輩子句推導出一個新子句()。這個新子句叫做消解式。,消解式求法,取各子句的析取，然后消去互補對。,3.4 消解原理,3.4.3 含有變量的消解式,3.4 消解原理,3.4.4 消解反演求解過程,消解反演 給出S，L 否定L，得L； 把L添加到S中去； 把新產生的集合L，S化成子句集； 應用消解原理，力圖推導出一個表示矛盾的空子句,例子儲蓄問題 前提：每個儲蓄錢的人都獲得利息。 結論：如果沒有利息，那么就沒有人去儲蓄錢,3.4 消解原理,(1）規定原子公式： S(x,y) 表示 “x儲蓄y” M(x) 表示 “x是錢” I(x) 表示 “x是利息” E(x，y) 表示 “x獲得y”,(2）用謂詞公式表示前提和結論： 前提： (x)(y)(S(x,y)M(y)(y)(I(y)E(x,y) 結論： (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),把結論化為子句形： 3) I(z) 4) S(a,b) 5) M(b),(4) 消解反演求NIL,圖3.12 儲蓄問題反演樹,3.4 消解原理,反演求解過程 從反演樹求取答案步驟 把由目標公式的否定產生的每個子句添加到目標公式否定之否定的子句中去。 按照反演樹，執行和以前相同的消解，直至在根部得到某個子句止。 用根部的子句作為一個回答語句。 實質 把一棵根部有NIL的反演樹變換為根部帶有回 答語句的一棵證明樹。,3.4 消解原理,3.5 規則演繹系統,定義 基于規則的問題求解系統運用IfThen規則來建立，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內存，then部分用于規定放入工作內存的新斷言。這種基于規則的系統叫做規則演繹系統。在這種系統中，通常稱每個if部分為前項，稱每個then部分為后項。,3.5.1 規則正向演繹系統,定義 正向規則演繹系統是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。 求解過程 事實表達式的與或形變換 在基于規則的正向演繹系統中，我們把事實表示為非蘊涵形式的與或形，作為系統的總數據庫。,3.5 規則演繹系統,事實表達式的與或圖表示,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 規則演繹系統,與或圖的F規則變換 這些規則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。我們把允許用作規則的公式類型限制為下列形式： L W 式中：L是單文字；W為與或形的唯一公式。,3.5 規則演繹系統,3.5.2 規則逆向演繹系統,定義 逆向規則演繹系統是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。 求解過程 目標表達式的與或形式 與或圖的B規則變換 作為終止條件的事實節點的一致解圖,3.5 規則演繹系統,正向和逆向組合系統是建立在兩個系統相結合的基礎上的。此組合系統的總數據庫由表示目標和表示事實的兩個與或圖結構組成。這些與或圖結構分別用正向系統的F規則和逆向系統的B規則來修正。,3.5.3 規則雙向演繹系統,3.5 規則演繹系統,3.6 產生式系統,定義：用來描述若干個不同的以一個基本概念為基礎的系統。這個基本概念就是產生式規則或產生式條件和操作對的概念。 實質：在產生式系統中，論域的知識分為兩部分：用事實表示靜態知識，如事物、事件和它們之間的關系；用產生式規則表示推理過程和行為。由于這類系統的知識庫主要用于存儲規則，因此又把此類系統稱為基于規則的系統。,3.6.1 產生式系統的組成,控制策略,圖3.22 產生式系統的主要組成,總數據庫,產生式規則,3.6 產生式系統,選擇規則到執行操作的步驟 1 匹配 把當前數據庫與規則的條件部分相匹配。 2 沖突 當有一條以上規則的條件部分和當前數據庫相匹配時，就需要決定首先使用哪一條規則，這稱為沖突解決。 3 操作 操作就是執行規則的操作部分。,3.6 產生式系統,3.6.2 產生式系統的推理,正向推理：從一組表示事實的謂詞或命題出發，使用一組產生式規則，用以證明該謂詞公式或命題是否成立。 逆向推理：從表示目標的謂詞或命題出發，使用一組產生式規則證明事實謂詞或命題成立，即首先提出一批假設目標，然后逐一驗證這些假設。 雙向推理：雙向推理的推理策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現事實與目標的匹配。,3.6 產生式系統,3.7 系統組織技術,3.7.1 議程表,系統組織技術首先將一個大系統或復雜系統中的知識劃分為一組相對獨立的模塊，然后考慮各子模塊間在求解時的合作問題。,議程表是一個系統能夠執行的任務表列。與每個任務有關的有兩件事，即提出該任務的理由和表示對該任務是有用的證據總權的評價。,3.7.2 黑板法,黑板法由一組稱為知識資源(KS)的獨立模塊和一塊黑板組成求解系統。知識資源含有系統中專門領域的知識，而黑板則是一切KS可以訪問的公用數據結構。,3.7 系統組織技術,3.7.3 -極小搜索法,提供了一種選擇最有希望假設的技術。,3.8 不確定性推理,以模糊集理論為基礎的方法 以概率為基礎的方法,3.8.1 關于證據的不確定性,不確定性推理是研究復雜系統不完全性和不確定性的有力工具。有兩種不確定性，即關于證據的不確定性和關于結論的不確定性。,3.8.2 關于結論的不確定性,關于結論的不確定性也叫做規則的不確定性，它表示當規則的條件被完全滿足時，產生某種結論的不確定程度。,3.8.3 多個規則支持同一事實時的不確定性,基于模糊集理論的方法 基于概率論的方法,3.8 不確定性推理,3.9 非單調推理,定義 非單調推理用來處理那些不適合用謂詞邏輯表示的知識。 它能夠較好地處理不完全信息、不斷變化的情況以及求解復雜問題過程中生成的假設，具有較為有效的求解效率。,3.9.1 缺省推理,定義1：如果X不知道，那么得結論Y。 定義2：如果X不能被證明，那么得結論Y。 定義3：如果X不能在某個給定的時間內被證明，那么得結論Y。,3.9 非單調推理,3.9.2 非單調推理系統 正確性維持系統用以保持其它程序所產生的命題 之間的相容性。一旦發現某個不相容，它就調出 自己的推理機制，面向從屬關系的回溯，并通過 修改最小的信念集來消除不相容。,3.10 小結,經典搜索推理技術 圖搜索技術 消解反演 高級搜索推理技術 規則演繹系統 產生式系統 系統組織技術 不確定性推理 非單調推理,第四章 計算智能(1),神經計算 模糊計算,4.1 概述,信息科學與生命科學的相互交叉、相互滲透和相互促進是現代科學技術發展的一個顯著特點。 計算智能涉及神經網絡、模糊邏輯、進化計算和人工生命等領域，它的研究和發展正反映了當代科學技術多學科交叉與集成的重要發展趨勢。,什么是計算智能,把神經網絡（NN）歸類于人工智能（AI）可能不大合適，而歸類于計算智能（CI）更能說明問題實質。進化計算、人工生命和模糊邏輯系統的某些課題，也都歸類于計算智能。 計算智能取決于制造者（manufacturers）提供的數值數據，不依賴于知識；另一方面，人工智能應用知識精品（knowledge tidbits）。人工神經網絡應當稱為計算神經網絡。,4.1 概述,計算智能與人工智能的區別和關系,輸入,人類知識 ()傳感輸入,知識 ()傳感數據,計算 ()傳感器,C數值的,A符號的,B生物的,輸入,復雜性,復雜性,BNN,BPR,BI,ANN,APR,AI,CNN,CPR,CI,4.1 概述,AArtificial，表示人工的（非生物的）；BBiological，表示物理的化學的 （？）生物的； CComputational，表示數學計算機 計算智能是一種智力方式的低層認知，它與人工智能的區別只是認知層次從中層下降至低層而已。中層系統含有知識（精品），低層系統則沒有。,4.1 概述,當一個系統只涉及數值（低層）數據，含有模式識別部分，不應用人工智能意義上的知識，而且能夠呈現出： （1）計算適應性； （2）計算容錯性； （3）接近人的速度； （4）誤差率與人相近， 則該系統就是計算智能系統。 當一個智能計算系統以非數值方式加上知識（精品）值，即成為人工智能系統。,4.1 概述,1960年威德羅和霍夫率先把神經網絡用于自動控制研究。 60年代末期至80年代中期，神經網絡控制與整個神經網絡研究一樣，處于低潮。 80年代后期以來，隨著人工神經網絡研究的復蘇和發展，對神經網絡控制的研究也十分活躍。這方面的研究進展主要在神經網絡自適應控制和模糊神經網絡控制及其在機器人控制中的應用上。,4.2 神經計算 4.2.1 人工神經網絡研究的進展,人工神經網絡的特性,并行分布處理 非線性映射 通過訓練進行學習 適應與集成 硬件實現,4.2 神經計算,圖4.2 神經元模型,4.2.2 人工神經網絡的結構,圖4.2中的神經元單元由多個輸入xi，i=1,2,.,n和一個輸出y組成。中間狀態由輸入信號的權和表示，而輸出為 （4.1） 式中，j為神經元 單元的偏置，wji為 連接權系數,4.2 神經計算,圖4.3 神經元中的某些變換（激發）函數,(a) 二值函數 (b) S形函數 (c) 雙曲正切函數,n為輸入信號數目，yj為神經元輸出，t為時間，f(_)為輸出變換函數，如圖4.3。,4.2 神經計算,人工神經網絡的基本特性和結構,人工神經網絡是具有下列特性的有向圖： 對于每個節點 i 存在一個狀態變量xi ； 從節點 j 至節點 i ，存在一個連接權系統數wij； 對于每個節點 i ，存在一個閾值 i； 對于每個節點 i ，定義一個變換函數fi ；對于最一般的情況，此函數取 形式。,4.2 神經計算,圖4.4 反饋網絡 圖4.5 前饋網絡,遞歸（反饋）網絡:在遞歸網絡中，多個神經元互連以組織一個互連神經網絡，如圖5.3。 前饋網絡:前饋網絡具有遞階分層結構，由同層神經元間不存在互連的層級組成，如圖5.4。,4.2 神經計算,人工神經網絡的主要學習算法,有師學習算法：能夠根據期望的和實際的網絡輸出（對應于給定輸入）間的差來調整神經元間連接的強度或權。 無師學習算法：不需要知道期望輸出。 強化學習算法：采用一個“評論員”來評價與給定輸入相對應的神經網絡輸出的優度（質量因數）。強化學習算法的一個例子是遺傳算法（GA）。,4.2 神經計算,人工神經網絡的典型模型,4.2 神經計算,續前表：,4.2 神經計算,4.2.4 基于神經網絡的知識表示與推理,基于神經網絡的知識表示 在這里，知識并不像在產生式系統中那樣獨立地表示為每一條規則，而是將某一問題的若干知識在同一網絡中表示。例如，在有些神經網絡系統中，知識是用神經網絡所對應的有向權圖的鄰接矩陣及閾值向量表示的。,4.2 神經計算,基于神經網絡的推理,基于神經網絡的推理是通過網絡計算實現的。把用戶提供的初始證據用作網絡的輸入，通過網絡計算最終得到輸出結果。 一般來說，正向網絡推理的步驟如下： 把已知數據輸入網絡輸入層的各個節點。 利用特性函數分別計算網絡中各層的輸出。 用閾值函數對輸出層的輸出進行判定，從而得到輸出結果。,4.2 神經計算,定義4.1 模糊集合(Fuzzy Sets),論域U到0,1區間的任一映射 ， 即 ，都確定U的一個模糊子集F； 稱為F的隸屬函數或隸屬度。在論域U中，可把模糊子集表示為元素u與其隸屬函數 的序偶集合，記為： (4.7),4.3 模糊計算 4.3.1 模糊集合、模糊邏輯及其運算,定義4.2 模糊支集、交叉點及模糊單點,若模糊集是論域U中所有滿足 的元素u構成的集合，則稱該集合為模糊集F的支集。 當u滿足 ，稱為交叉點。 當模糊支集為U中一個單獨點，且u滿足 則稱模糊集為模糊單點。,4.3 模糊計算,定義4.3 模糊集的運算,設A和B為論域U中的兩個模糊集，其隸屬函數分別為 和 ，則對于所有 ，存在下列運算： A與B的并（邏輯或）記為 ，其隸屬函數定義為： (4.10) A與B的交（邏輯與）記為 ，其隸屬函數定義為： (4.11) A的補（邏輯非）記為 ，其傳遞函數定義為： (4.12),4.3 模糊計算,定義4.4 直積（笛卡兒乘積，代數積）,若 分別為論域 中的模糊集合，則這些集合的直積是乘積空間 中一個模糊集合，其隸屬函數為： (4.13),定義4.5 模糊關系,若U，V是兩個非空模糊集合，則其直積UV中的模糊子集R稱為從U到V的模糊關系，表示為： (4.14),4.3 模糊計算,定義4.6 復合關系,若R和S分別為UV和VW中的模糊關系，則R和S的復合是一個從U到W的模糊關系，記為： (4.15),其隸屬函數為： (4.16),式(4.9)中的 * 號可為三角范式內的任意一種算子，包括模糊交、代數積、有界積和直積等。,4.3 模糊計算,定義4.7 正態模糊集、凸模糊集和模糊數,以實數R為論域的模糊集F，若其隸屬函數滿足 則F為正態模糊集；若對于任意實數x，axb，有 則F為凸模糊集；若F既是正態的又是凸的，則稱F為模糊數。,定義4.8 語言變量,一個語言變量可定義為多元組 。其中，x為變量名； 為x的詞集，即語言值名稱的集合；U為論域；G是產生語言值名稱的語法規則；M是與各語言值含義有關的語法規則。,4.3 模糊計算,4.1.2 模糊邏輯推理,模糊邏輯推理是建立在模糊邏輯基礎上的不確定性推理方法，是在二值邏輯三段論基礎上發展起來的。這種推理方法以模糊判斷為前提，動用模糊語言規則，推導出一個近似的模糊判斷結論。已經提出了Zadeh法，Baldwin法、Tsukamoto法、Yager法和Mizumoto法等方法。 廣義取式假言推理法(GMP)推理規則可表示為： 前提1：x為A 前提2：若x為A，則y為B 結 論：y為B,4.3 模糊計算,廣義拒式假言推理法(GMT, Generalized Modus Tollens) 的推理規則可表示為： 前提1：y為B 前提2：若x為A，則y為B 結 論：x為A 模糊變量的隱含函數基本上可分為三類，即模糊合取、模糊析取和模糊蘊涵。,4.3 模糊計算,4.1.3 模糊判決方法,在推理得到的模糊集合中取一個相對最能代表這個模糊集合的單值的過程就稱作解模糊或模糊判決（Defuzzification）。模糊判決可以采用不同的方法：重心法、最大隸屬度方法、加權平均法、隸屬度限幅元素平均法。 下面介紹各種模糊判決方法，并以“水溫適中”為例，說明不同方法的計算過程。這里假設“水溫適中”的隸屬函數為： = X: 0.0/0 + 0.0/10 + 0.33/20 + 0.67/30 + 1.0/40 + 1.0/50+ 0.75/60 + 0.5/70 + 0.25/80 + 0.0/90 + 0.0/100 ,4.3 模糊計算,重心法就是取模糊隸屬函數曲線與橫坐標軸圍成面積的重心作為代表點。理論上應該計算輸出范圍內一系列連續點的重心，即 (4.35) 但實際上是計算輸出范圍內整個采樣點的重心，用足夠小的取樣間隔來提供所需要的精度，即：,=48.2,4.3 模糊計算,1. 重心法,這種方法最簡單，只要在推理結論的模糊集合中取隸屬度最大的那個元素作為輸出量即可。要求這種情況下其隸屬函數曲線一定是正規凸模糊集合（即其曲線只能是單峰曲線）。,例如，對于“水溫適中”，按最大隸屬度原則，有兩個元素40和50具有最大隸屬度1.0，那就對所有取最大隸屬度的元素40和50求平均值，執行量應?。?4.3 模糊計算,2. 最大隸屬度法,3. 系數加權平均法,系數加權平均法的輸出執行量由下式決定： (4.36) 式中，系數的選擇要根據實際情況而定，不同的系統就決定系統有不同的響應特性。,4.3 模糊計算,用所確定的隸屬度值對隸屬度函數曲線進行切割，再對切割后等于該隸屬度的所有元素進行平均，用這個平均值作為輸出執行量，這種方法就稱為隸屬度限幅元素平均法。,例如，當取為最大隸屬度值時，表示“完全隸屬”關系，這時1.0。在“水溫適中”的情況下，40和50的隸屬度是1.0，求其平均值得到輸出代表量：,4.3 模糊計算,4. 隸屬度限幅元素平均法,4.4 小結,計算智能 神經計算 模糊計算 進化計算 人工生命 神經計算：人工神經網絡 模糊計算：模糊邏輯,第5章 計算智能(2):,進化計算 人工生命,進化計算包括： 遺傳算法(genetic algorithms，GA) 進化策略(evolution strategies) 進化編程(evolutionary rogramming) 遺傳編程(genetic programming) 人類不滿足于模仿生物進化行為，希望能夠建立具有自然生命特征的人造生命和人造生命系統。 人工生命是人工智能和計算智能的一個新的研究熱點。,5.1 遺傳算法,遺傳算法是模仿生物遺傳學和自然選擇機理，通過人工方式所構造的一類優化搜索算法，是對生物進化過程進行的一種數學仿真，是進化計算的最重要的形式。 遺傳算法為那些難以找到傳統數學模型的難題指出了一個解決方法。 進化計算和遺傳算法借鑒了生物科學中的某些知識，這也體現了人工智能這一交叉學科的特點。,5.1.1 遺傳算法的基本機理,霍蘭德的遺傳算法通常稱為簡單遺傳算法（SGA）?，F以此作為討論主要對象，加上適應的改進，來分析遺傳算法的結構和機理。 編碼與解碼 適應度函數 遺傳操作,5.1 遺傳算法,5.1.2 遺傳算法的求解步驟,1. 遺傳算法的特點 (1) 遺傳算法是對參數集合的編碼而非針對參數本身進行進化； (2) 遺傳算法是從問題解的編碼組開始而非從單個解開始搜索； (3) 遺傳算法利用目標函數的適應度這一信息而非利用導數或其它輔助信息來指導搜索； (4) 遺傳算法利用選擇、交叉、變異等算子而不是利用確定性規則進行隨機操作。,5.1 遺傳算法,2. 遺傳算法的框圖(圖5.2),(1) 初始化群體; (2) 計算群體上每個個體的適應度值; (3) 按由個體適應度值所決定的某個規則選 擇將進入下一代的個體; (4) 按概率Pc進行交叉操作; (5) 按概率Pc進行突變操作; (6) 若沒有滿足某種停止條件，則轉第(2)步， 否則進入下一步。 (7) 輸出群體中適應度值最優的染色體作為問題的 滿意解或最優解。,5.1 遺傳算法,圖5.2 算法框圖,5.1 遺傳算法,一般遺傳算法的主要步驟如下： (1) 隨機產生一個由確定長度的特征字符串組成的初始群體。 (2) 對該字符串群體迭代的執行下面的步和 ，直到滿足停止標準： 計算群體中每個個體字符串的適應值； 應用復制、交叉和變異等遺傳算子產生下一代群體。 (3) 把在后代中出現的最好的個體字符串指定為遺傳算法的執行結果，這個結果可以表示問題的一個解。,5.1 遺傳算法,產生初始群體,是否滿足停止準則,計算每個個體的適應值,i=M?,GEN:=GEN+1,依概率選擇遺傳操作,執行復制,選擇一個個體,i:=i+1,選擇兩個個體,選擇一個個體,執行變異,i:=0,GEN:=0,復制到新群體,i:=i+1,將兩個后代插入新群體,插入到新群體,執行雜交,指定結果,結束,是,否,是,否,變異,復制,交叉,5.1 遺傳算法,遺傳算法的一般結構表示,Procedure: Genetic Algorithms begin t 0; initialize P(t);evaluate P(t); while (not termination condition ) do begin recombine P(t) to yield C(t); evaluate C(t); select P(t+1) from P(t) and C(t); t t+1; end end,5.1 遺傳算法,3. 遺傳算法求解舉例,例1：用遺傳算法求解函數 (5.1) 的最大值，其中 。,5.1 遺傳算法,遺傳算法歸納為五個基本組成部份,方案表示 群體初始化 適應度函數 遺傳操作 算法參數,5.1 遺傳算法,5.2 進化策略,進化策略(Evolution Strategies，ES)是一類模仿自然進化原理以求解參數優化問題的算法。 它是由雷切伯格（Rechenberg）、施韋費爾（Schwefel）和彼得比納特（Peter Bienert）于1964年提出的，并在德國共同建立的。,5.2.1 進化策略的算法模型,尋求與函數極值關聯的實n維矢量x。 隨機選擇父矢量的初始群體。 父矢量xi, i=1,p產生子代矢量xi。 對誤差 (i=1,p)排序以選擇和決定保持哪些矢量。 繼續產生新的試驗數據以及選擇最小誤差矢量。,5.2 進化策略,5.2.2 進化策略和遺傳算法的區別,進化策略和遺傳算法有著很強的相似性，它們都是一類模仿自然進化原理的算法。 兩者也存在著區別，其中最基本的區別是它們的研究領域不同。 進化策略是一種數值優化的方法，它采用一個具有自適應步長和傾角的特定爬山方法。 遺傳算法從廣義上說是一種自適應搜索技術。,5.2 進化策略,5.3 進化編程,進化編程(Evolutionary Programming，EP)，又稱為進化規劃（Evolutionary Planning），是由福格爾（Fogel）在1962年提出的一種模仿人類智能的方法。 進化編程根據正確預測的符號數來度量適應值。通過變異，為父代群體中的每個機器狀態產生一個子代。父代和子代中最好的部分被選擇生存下來。 它的提出是受自然生物進化機制的啟發。,5.3.1 進化編程的機理與表示,進化編程的過程，可理解為從所有可能的計算機程序形成的空間中，搜索具有高的適應度的計算機程序個體。 進化編程設計強調群體行為的變化。進化編程系統的表示自然地面向任務級。一旦選定一種適應性表示，就可以定義依賴于該