教學課件-《人工智能基礎》蔡自興

人工智能基礎第一章緒論1.1人工智能的定義和發(fā)展1.2人類智能和人工智能1.3人工智能的學派及其爭論1.4人工智能的研究與應用領域1.5人工智能對人類的影響1.6對人工智能的展望幾種定義智能（intelligence）智能機器（intelligentmachine）人工智能人工智能（學科）人工智能（能力）31.1.1人工智能的定義1.1.2人工智能的起源與發(fā)展

孕育時期（1956年前）數(shù)理邏輯學科（弗雷治、維納等）

計算的新思想（丘奇、圖靈等）擬腦機器（麥卡洛克、皮茨）

形成時期（1956－1970年）

1956年，第一次人工智能的研討會

1969年，第一屆國際人工智能聯(lián)合會議

1970年，《人工智能》國際雜志創(chuàng)刊41.1.2人工智能的起源與發(fā)展暗淡時期（1966－1974年）一些人工智能研究者盲目樂觀科學技術的發(fā)展對人工智能提出新的要求甚至挑戰(zhàn)知識應用時期（1970－1988年）專家系統(tǒng)與知識工程迅速發(fā)展人工智能系統(tǒng)是一個知識處理系統(tǒng)知識表示知識利用知識獲取51.1.2人工智能的起源與發(fā)展集成發(fā)展時期（1986年至今）進一步研究AI基本原理方法和技術深入滲透到其他學科和科學技術領域三大學派綜合集成，優(yōu)勢互補，共同發(fā)展61.2人工智能的各種認知觀1.2.1人工智能的主要學派符號主義（Symbolicism）基于物理符號系統(tǒng)假設和有限合理性原理

連接主義（Connectionism）基于神經(jīng)網(wǎng)絡及其間的連接機制與學習算法行為主義（Actionism）基于控制論及感知—動作型控制系統(tǒng)

7符號主義（Symbolicism）又稱：邏輯主義、心理學派或計算機學派原理：物理符號系統(tǒng)(即符號操作系統(tǒng))假設和有限合理性原理起源：源于數(shù)理邏輯學派代表：紐厄爾、西蒙和尼爾遜等8連接主義（Connectionism）又稱：仿生學派或生理學派原理：神經(jīng)網(wǎng)絡及神經(jīng)網(wǎng)絡間的連接機制與學習算法起源：源于仿生學，特別是人腦模型的研究學派代表：卡洛克、皮茨、Hopfield、魯梅爾哈特等9行為主義（Actionism）又稱：進化主義或控制論學派原理：控制論及感知—動作型控制系統(tǒng)起源：源于控制論學派代表作：布魯克斯(Brooks)的六足行走機器人，一個基于感知—動作模式的模擬昆蟲行為的控制系統(tǒng)101.2.2人工智能的爭論對人工智能理論的爭論符號主義認為人的認知基元是符號，認知過程即符號操作過程；認為人是一個物理符號系統(tǒng)，計算機也是一個物理符號系統(tǒng)，因此，能用計算機來模擬人的智能行為；認為知識是信息的一種形式，是構成智能的基礎。人工智能的核心問題是知識表示、知識推理和知識運用。11對人工智能理論的爭論連接主義認為思維基元是神經(jīng)元，而不是符號處理過程；認為人腦不同于電腦，并提出連結主義的大腦工作模式，用于取代符號操作的電腦工作模式。12對人工智能理論的爭論行為主義認為智能取決于感知和行動(所以被稱為行為主義)，提出智能行為的“感知—動作”模式；認為智能不需要知識、不需要表示、不需要推理；人工智能可以象人類智能一樣逐步進化(所以稱為進化主義)；智能行為只能在現(xiàn)實世界中與周圍環(huán)境交互作用而表現(xiàn)出來。13對人工智能方法的爭論符號主義功能模擬連接主義結構模擬行為主義行為模擬141.2.2人工智能的爭論1.3人類智能和人工智能心理活動的最高層級是思維策略，中間一層是初級信息處理，最底層級是生理過程。研究認知過程的主要任務是探求高層次思維決策與初級信息處理的關系，并用計算機程序來模擬人的思維策略水平，而用計算機語言模擬人的初級信息處理過程。151.3.1研究認知過程的任務

1.3.2智能信息處理系統(tǒng)的假設人是一種智能信息處理系統(tǒng)物理符號系統(tǒng)的六種基本功能物理符號系統(tǒng)的假設推論一推論二推論三161.3.3智能信息處理系統(tǒng)的假設

人類的認知行為具有不同層次認知生理學認知心理學認知信息學認知工程學171.3.3人類智能的計算機模擬

機器智能可以模擬人類智能智能計算機下棋定理證明語言翻譯新型智能計算機神經(jīng)計算機量子計算機181.4人工智能的研究目標和內(nèi)容1.4.1人工智能的研究目標一般研究目標更好地理解人類智能

通過編寫程序來模仿和檢驗有關人類智能的理論。創(chuàng)造有用的靈巧程序，該程序能夠執(zhí)行一般需要人類專家才能實現(xiàn)的任務。近期研究目標的遠期研究目標近期研究目標是建造智能計算機應以代替人類的某些智力活動。遠期目標是用自動機模仿人類的思維活動和智力功能。191.4.2人工智能研究的基本內(nèi)容認知建模知識表示知識推理知識應用機器感知機器思維機器學習機器行為智能系統(tǒng)構建201.5人工智能研究的主要方法功能模擬法結構模擬法行為模擬法集成模擬法211.6人工智能的研究和應用領域

人工智能的基本技術知識表示（KnowledgeRepresentation）狀態(tài)空間法、問題歸約法、謂詞邏輯法…

推理搜索（Searching&Reasoning）啟發(fā)式搜索、消解原理、不確定性推理…

計算智能（ComputationalIntelligence）模糊計算、神經(jīng)計算、進化計算…

構成技術（系統(tǒng)與語言）產(chǎn)生式系統(tǒng)、LISP語言、Prolog語言…221問題求解與博弈

問題的表示、分解、搜索、歸約等進行復雜的數(shù)學公式符號運算求解2邏輯推理與定理證明通過對事實數(shù)據(jù)庫的操作來證明定理多種證明方法幾何定理證明的“吳氏方法”231.6人工智能的研究和應用領域3計算智能計算智能包括神經(jīng)計算、模糊計算、進化計算、粒群計算、自然計算、免疫計算和人工生命等進化計算的理論基礎是生物進化論4分布式人工智能與Agent是傳統(tǒng)人工智能的延伸和擴展研究目標是創(chuàng)建一種能描述自然系統(tǒng)和社會系統(tǒng)的精確概念模型241.6人工智能的研究和應用領域5自動程序設計根據(jù)不同目的描述來編寫的計算機程序促進人工智能系統(tǒng)的發(fā)展6專家系統(tǒng)

是一個智能化的計算機程序系統(tǒng)和傳統(tǒng)的計算機程序之間有本質區(qū)別251.6人工智能的研究和應用領域7機器學習是機器獲取智能的途徑學習是一個有特定目的的知識獲取過程學習的本質是對信息的理解與應用有多種學習方法8自然語言理解

語言自然語言、人造語言、機器語言“理解”的標準261.6人工智能的研究和應用領域9機器人學操作機器人智能機器人機器人的廣泛應用促進人工智能的發(fā)展10模式識別是計算機對環(huán)境識別的需要是對人類環(huán)境的感知模擬271.6人工智能的研究和應用領域11機器視覺人類80％以上的外部信息來自視覺低層視覺與高層視覺前沿研究領域廣泛應用12神經(jīng)網(wǎng)絡

神經(jīng)計算機在其它領域中的廣泛應用281.6人工智能的研究和應用領域13智能控制驅動智能機器自主地實現(xiàn)其目標的過程是一個定性和定量的混合控制過程是當今自動控制的最高水平14智能調(diào)度與指揮

尋找最佳調(diào)度和組合

NP完全類問題的求解軍事指揮系統(tǒng)等領域291.6人工智能的研究和應用領域15智能檢索是信息時代來臨的需要智能檢索系統(tǒng)所面臨的三大問題16系統(tǒng)與語言工具計算機系統(tǒng)的一些概念得到發(fā)展新的編程語言與專用開發(fā)工具301.6人工智能的研究和應用領域1.7人工智能對人類的影響人工智能對經(jīng)濟的影響人工智能對社會的影響人工智能對文化的影響311.7.1人工智能對經(jīng)濟的影響專家系統(tǒng)的效益人工智能推動計算機技術發(fā)展321.7.2人工智能對社會的影響勞務就業(yè)問題思維方式與觀念的變化技術失控的危險（美國科幻作家阿西莫夫提出了“機器人三守則”）社會結構變化心理上的威脅1.7.3人工智能對文化的影響改善人類知識改善人類語言改善文化生活331.8對人工智能的展望人工智能的近期研究目標：在于建造智能計算機，用以代替人類從事腦力勞動，即使現(xiàn)有的計算機更聰明更有用。人工智能的遠期研究目標：探究人類智能和機器智能的基本原理，研究用自動機(automata)模擬人類的思維過程和智能行為。341.8.1更新的理論框架人工智能尚存在的問題：宏觀與微觀隔離全局與局部割裂理論和實際脫節(jié)351.8.2更好的技術集成人工智能技術是其它信息處理技術及相關學科技術的集成。要集成的信息技術除數(shù)字技術外，還包括計算機網(wǎng)絡、遠程通信、數(shù)據(jù)庫、計算機圖形學、語音與聽覺、機器人學、過程控制、并行計算、光計算、生物信息處理等。未來的智能系統(tǒng)還要集成認知科學、心理學、社會學、語言學、系統(tǒng)學和哲學等。361.8.3更成熟的應用方法期望研究出通用而有效的人工智能開發(fā)方法：更高級的AI通用語言；更有效的AI專用語言與開發(fā)環(huán)境或工具。37人工智能基礎第二章知識表示2.1概述2.2狀態(tài)空間法2.3問題歸約法2.4謂詞邏輯法2.5語義網(wǎng)絡法2.6其他方法392.1

概述知識及知識表示人工智能系統(tǒng)所關心的知識及其分類知識表示應該注意的問題402.2狀態(tài)空間法問題求解技術包括問題的建模與表示求解的方法狀態(tài)空間法三要點狀態(tài)（state）算符（operator）狀態(tài)空間方法412.2.1

問題狀態(tài)描述定義狀態(tài)：描述某類不同事物間的差別而引入的一組最少變量q0，q1，…，qn的有序集合。算符：使問題從一種狀態(tài)變化為另一種狀態(tài)的手段稱為操作符或算符。問題的狀態(tài)空間：是一個表示該問題全部可能狀態(tài)及其關系的圖，它包含三種說明的集合，即三元狀態(tài)（S，F(xiàn)，G）。4243OriginalStateMiddleStateGoalState狀態(tài)空間表示概念詳釋三數(shù)碼難題44123123123312312312初始棋局目標棋局有向圖路徑代價圖的顯示說明圖的隱示說明45AB2.2.2狀態(tài)圖示法產(chǎn)生式系統(tǒng)（productionsystem）一個總數(shù)據(jù)庫（globaldatabase）

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

用一個四元表列（W，x，Y，z）來表示這個問題狀態(tài)。這個問題的操作（算符）如下：2goto（U）表示猴子走到水平位置U或者用產(chǎn)生式規(guī)則表示為 （W，0，Y，z）goto（U）（U，0，Y，z）48pushbox（V）猴子把箱子推到水平位置V，即有

（W，0，W，z）pushbox（V）（V，0，V，z）climbbox猴子爬上箱頂，即有

（W，0，W，z）climbbox（W，1，W，z）49grasp猴子摘到香蕉，即有

（c，1，c，0）grasp（c，1，c，1）

該初始狀態(tài)變換為目標狀態(tài)的操作序列為

{goto(b),pushbox(c),climbbox,grasp}5051(b，1，b，0)（U，0，b，0）（V，0，V，0）（c，1，c，0）（U，0，V，0）（c，1，c，1）（a，0，b，0）目標狀態(tài)goto（U）goto（U）U=b，climbboxgoto（U）U=bpushbox（V）goto（U）U=V圖2.4猴子和香蕉問題的狀態(tài)空間圖522.3問題歸約法子問題1子問題n原始問題子問題集本原問題問題歸約表示的組成部分：一個初始問題描述；一套把問題變換為子問題的操作符；一套本原問題描述。問題歸約的實質：從目標(要解決的問題)出發(fā)逆向推理，建立子問題以及子問題的子問題，直至最后把初始問題歸約為一個平凡的本原問題集合。532.3問題歸約法2.3.1問題歸約描述梵塔難題54123CBA解題過程（3個圓盤問題）551231231231231231231231232.3.2與或圖表示與圖、或圖、與或圖56ABCD與圖ABC或圖57BCDEFGAHMBCDEFGAN一些關于與或圖的術語58HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點終葉節(jié)點與或圖定義59與或圖例子ttttttttt（a）（b）有解節(jié)點無解節(jié)點終葉節(jié)點不可解節(jié)點的一般定義沒有后裔的非終葉節(jié)點為不可解節(jié)點。全部后裔為不可解的非終葉節(jié)點且含有或后繼節(jié)點，此非終葉節(jié)點才是不可解的。后裔至少有一個為不可解的非終葉節(jié)點且含有與后繼節(jié)點，此非終葉節(jié)點才是不可解的。與或圖構成規(guī)則60與或圖定義梵塔問題歸約圖61（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

2.3.3問題歸約機理關鍵算符具有決定性作用的算符叫做關鍵算符差別尋找候選關鍵算符的一種方法涉及計算某個問題（S，F(xiàn)，G）的差別。粗略地說，問題（S，F(xiàn)，G）的差別就是用S的元對由集合G規(guī)定的目標進行測試失敗原因的部分表列62合適公式（WFF，well-formedformulas）合適公式的遞歸定義合適公式的性質合適公式的真值等價（Equivalence)邏輯語句形式語言632.3.3問題歸約機理2.4.1謂詞公式原子公式的的定義：用P(x1，x2，…，xn)表示一個n元謂詞公式，其中P為n元謂詞，x1,x2,…，xn為客體變量或變元。通常把P(x1,x2,…,xn)叫做謂詞演算的原子公式，或原子謂詞公式。分子謂詞公式可以用連詞把原子謂詞公式組成復合謂詞公式，并把它叫做分子謂詞公式。642.4謂詞邏輯法語法和語義基本符號謂詞符號、變量符號、函數(shù)符號、常量符號、括號和逗號原子公式652.4.2謂詞演算連詞和量詞(Connective&Quantifiers)連詞與及合取（conjunction)或及析?。╠isjunction）蘊涵（Implication）非（Not）量詞全稱量詞（UniversalQuantifiers)存在量詞(ExistentialQuantifiers)662.4.2謂詞演算2.4.3置換與合一置換概念假元推理全稱化推理綜合推理定義就是在該表達式中用置換項置換變量性質可結合的不可交換的67合一（Unification)合一：尋找項對變量的置換，以使兩表達式一致。可合一：如果一個置換s作用于表達式集{Ei}的每個元素，則我們用{Ei}s來表示置換例的集。我們稱表達式集{Ei}是可合一的。682.4.3置換與合一2.5產(chǎn)生式表示法產(chǎn)生式的基本形式通常用下列的形式表示： IFPTHENQ（如果P則Q） 或者 P→Q產(chǎn)生式推理如果已有產(chǎn)生式規(guī)則：P→Q并且觀察到P，或者知識庫中已有P，則可得到結論Q，或執(zhí)行操作Q。692.6語義網(wǎng)絡法語義網(wǎng)絡的結構定義組成部分詞法結構過程語義702.6.1二元語義網(wǎng)絡的表示表示占有關系和其它情況例：小燕是一只燕子，燕子是鳥；巢-1是小燕的巢，巢-1是巢中的一個。選擇語義基元試圖用一組基元來表示知識，以便簡化表示，并可用簡單的知識來表示更復雜的知識。712.6.2多元語義網(wǎng)絡的表示謂詞邏輯與語義網(wǎng)絡等效72LIMINGMANISAISA（LIMING，MAN）或MAN（LIMING）（語義網(wǎng)絡）（謂詞邏輯）多元語義網(wǎng)絡表示的實質把多元關系轉化為一組二元關系的組合，或二元關系的合取。73R(X1，X2，…，Xn)R12(X1，X2)∧R13(X1，X3)∧…∧R1n(X1，Xn)......Rn-1n(Xn-1，Xn)可轉換為2.6.3基于語義網(wǎng)絡的知識推理繼承在語義網(wǎng)絡中所謂的繼承是把對事物的描述從概念節(jié)點或類節(jié)點傳遞到實例節(jié)點。匹配

加注析取界限，并標記DIS，以免引起混淆。742.7框架表示框架理論及特點框架理論概述框架的特點自然性結構性繼承性752.7框架表示框架的構成框架通常由描述事物的各個方面的槽組成，每個槽可有若干個側面，而每個側面又可有若干個值框架的推理框架包含它所描述的情況或物體的多方面的信息框架包含物體必須具有的屬性框架描述它們所代表的概念的典型事例762.8面向對象表示面向對象的概念一切事物都是對象任何系統(tǒng)都是由對象構成的，系統(tǒng)本身也是對象系統(tǒng)的發(fā)展和進化過程都是由系統(tǒng)的內(nèi)部對象和外部對象之間（也包括內(nèi)部對象與內(nèi)部對象之間）的相互作用完成的面向對象表示中的類繼承772.8面向對象表示面向對象表示的推理實例說明面向對象程序設計中實現(xiàn)封裝性的例子說明面向對象程序設計中實現(xiàn)繼承性的例子說明面向對象程序設計中實現(xiàn)多態(tài)性的例子782.9劇本表示劇本的構成開場條件角色道具場景結果劇本的推理792.10過程表示過程式（procedure）表示就是將有關某一問題領域的知識，連同如何使用這些知識的方法，均隱式地表達為一個求解問題的過程。從程序求解問題的效率上來說，過程式表達要比陳述式表達高得多。8081方法初始問題算符目標結果

狀態(tài)空間法

歸約法

謂詞邏輯法

語義網(wǎng)絡法狀態(tài)節(jié)點合適公式節(jié)點算符弧子句集（setofclause）置換合一消解反演鏈目標狀態(tài)節(jié)點根節(jié)點目標網(wǎng)絡解答路徑（path）解答樹（tree）nil語義網(wǎng)絡知識表示方法間的關系人工智能基礎82第三章搜索原理3.1盲目搜索3.2

啟發(fā)式搜索3.3博弈樹搜索3.4遺傳算法3.5模擬退火算法3.6免疫算法3.1盲目搜索3.1.1圖搜索策略一種在圖中尋找路徑的方法

圖中每個節(jié)點對應一個狀態(tài)，每條連線對應一個操作符。這些節(jié)點和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標記。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。OPEN表和CLOSED表圖搜索過程框圖8485開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表n為目標節(jié)點嗎？把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針修改指針方向重排OPEN表失敗成功圖3.2圖搜索過程框圖是是否否3.1.1圖搜索策略盲目搜索特點：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價搜索等。啟發(fā)式搜索特點：重排OPEN表，選擇最有希望的節(jié)點加以擴展。種類：有序搜索、A*算法等。863.1.2寬度優(yōu)先搜索定義以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它。算法8788開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針失敗成功圖3.4寬度優(yōu)先算法框圖是否是否3.1.2寬度優(yōu)先搜索八數(shù)碼難題（8-puzzleproblem）891238456712384567（目標狀態(tài)）（初始狀態(tài)）規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節(jié)點。901238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖3.5八數(shù)碼難題的寬度優(yōu)先搜索樹1456123845671238456712384567123845671238456723242526272378221238456712384567123845671238456712384567123845671238456714151617181920211238456743.1.3深度優(yōu)先搜索定義首先擴展最新產(chǎn)生的(即最深的)節(jié)點。算法防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度——深度界限。與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。91

3.1.4等代價搜索定義是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。算法若所有連接弧線具有相等代價，則簡化為寬度優(yōu)先搜索算法。9293開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？失敗成功圖3.9等代價搜索算法框圖是否是否令g(s)=0S是否目標節(jié)點？是成功擴展i，計算其后繼節(jié)點j的g(j)，并把后繼節(jié)點放入OPEN表否3.2啟發(fā)式搜索3.2.1啟發(fā)式搜索策略盲目搜索可能帶來組合爆炸啟發(fā)式信息用來加速搜索過程的有關問題領域的特征信息，按其用途分為：用于決定要擴展的下一個節(jié)點，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。在擴展一個節(jié)點的過程中，用于決定要生成哪一個或哪幾個后繼節(jié)點，以免盲目地同時生成所有可能的節(jié)點。用于決定某些應該從搜索樹中拋棄或修剪的節(jié)點。943.2.1啟發(fā)式搜索策略估價函數(shù)獲得某些節(jié)點“希望”的啟發(fā)信息f(n)——表示節(jié)點n的估價函數(shù)值重排OPEN表3.2.2有序搜索實質選擇OPEN表上具有最小f值的節(jié)點作為下一個節(jié)點。95

96開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目標節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關系及指針失敗成功圖3.10有序搜索算法框圖是否是否3.2.2有序搜索八數(shù)碼難題（8-puzzleproblem）9712384567（目標狀態(tài)）12384567（初始狀態(tài)）985714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖3.11八數(shù)碼難題的有序搜索樹123846（4）73.2.3A*算法估價函數(shù)對節(jié)點n定義f*(n)=g*(n)+h*(n),表示從S開始約束通過節(jié)點n的一條最佳路徑的代價。希望估價函數(shù)f定義為：f(n)=g(n)+h(n)

——g是g*的估計，h是h*的估計A*算法的定義定義3.3定義3.4定義3.5993.3博弈樹搜索3.3.1博弈概述對壘的MAX、MIN雙方輪流采取行動，博弈的結果只有三種情況。在對壘過程中，任何一方都了解當前的格局及過去的歷史。任何一方在采取行動前都要根據(jù)當前的實際情況，進行得失分析，選取對自已為最有利而對對方最為不利的對策。1003.3.2極小極大分析法設博弈的雙方中一方為MAX，另一方為MIN。找到當前的最優(yōu)行動方案。定義一個估價函數(shù)，用來估算當前博弈樹端節(jié)點的得分。當端節(jié)點的估值計算出來后，再推算出父節(jié)點的得分(倒推值)。獲得較大的倒推值的方案，是最好的行動方案。1013.3.3

α-β剪枝技術α剪枝對于一個與節(jié)點MIN，若能估計出其倒推值的上界β，并且這個β值不大于MIN的父節(jié)點(一定是或節(jié)點)的估計倒推值的下界α，即α≥β，則就不必再擴展該MIN節(jié)點的其余子節(jié)點了（因為這些節(jié)點的估值對MIN父節(jié)點的倒推值已無任何影響了）。1023.3.3

α-β剪枝技術β剪枝對于一個或節(jié)點MAX，若能估計出其倒推值的下界α，并且這個α值不小于MAX的父節(jié)點（一定是與節(jié)點）的估計倒推值的上界β，即α≥β，則就不必再擴展該MAX節(jié)點的其余子節(jié)點了（因為這些節(jié)點的估值對MAX父節(jié)點的倒推值已無任何影響了）。1033.4遺傳算法遺傳算法的基本原理編碼與譯碼適應度函數(shù)遺傳操作控制參數(shù)1043.4.2遺傳算法的結構簡單遺傳算法的求解步驟初始化群體;計算群體上每個個體的適應度值;按由個體適應度值所決定的某個規(guī)則選擇將進入下一代的個體;按概率Pc進行交叉操作;按概率Pc進行突變操作;沒有滿足某種停止條件，則轉第②步，否則進入⑦。輸出種群中適應度值最優(yōu)的染色體作為問題的滿意解或最優(yōu)解。1053.4.3遺傳算法的性能遺傳算法性能的影響因素種群的規(guī)模要適當適應度函數(shù)的構造交叉和變異操作1063.5模擬退火算法3.5.1模擬退火算法的模型解空間目標函數(shù)初始解模擬退火的基本思想模擬退火算法新解的產(chǎn)生和接受的幾個步驟1073.5.2模擬退火算法的簡單應用旅行商問題解空間解空間S是遍訪每個城市恰好一次的所有回路，是{1，……，n}的所有循環(huán)排列的集合，S中的成員記為(w1,w2,……，wn)，并記wn+1=w1。初始解可選為(1，……，n)。目標函數(shù)此時的目標函數(shù)即為訪問所有城市的路徑總長度，或稱為代價函數(shù)。1083.5.2模擬退火算法的簡單應用模擬退火算法求解TSP問題的偽程序：

begin

init-of-T;{T為初始溫度}

S={1，……，n};{S為初始值}

termination=false;

whiletermination=false

begin

fori=1toLdo

begin

generate(S′formS);{從當前回路S產(chǎn)生新回路S′}

Δt:=f(S′))-f(S);{f(S)為路徑總長}

IF(Δt<0)OR(EXP(-Δt/T)>Random-of-[0,1])

S=S′;

IFthe-halt-condition-is-TRUETHEN

termination=true;

End;

T_lower;

End;

End1093.5.3模擬退火算法參數(shù)控制問題模擬退火算法應用廣泛，可解NP完全問題，但參數(shù)難以控制，表現(xiàn)為以下三點：溫度T的初始值設置問題。退火速度問題。溫度管理問題。

1103.6免疫算法3.6.1免疫計算概述人工免疫系統(tǒng)（artificialimmunesystem）基于生物免疫機制尋找解決科學和工程中實際問題的智能方法免疫計算與人工免疫系統(tǒng)相應的計算方法1113.6.2免疫算法的基本原理免疫算法（ImmuneAlgorithm）在模仿生物免疫機制的基礎上，綜合基因進化機理，人工地構造的一類優(yōu)化算法，它實現(xiàn)了類似于免疫系統(tǒng)的自我調(diào)節(jié)功能和生成不同抗體的功能。人工免疫算法（ArtificialImmuneAlgorithm）是針對人體免疫系統(tǒng)而言，因為人體免疫系統(tǒng)已經(jīng)發(fā)展到了相當完美的程度，其中的“玄機”必是蘊涵著重大的科研價值。1123.6.2免疫算法的基本原理抗原（antigen）在免疫算法中抗原是指非最佳個體的基因，或者是可能錯誤的基因疫苗（vanccine）在免疫算法中疫苗是指根據(jù)已有的先驗知識得到的關于對最佳個體的一個估計值抗體（antibody）在免疫算法中抗體是指根據(jù)疫苗修正某個個體基因所得到的新個體（新基因）1133.6.2免疫算法的基本原理114圖3.17人工免疫算法流程圖抗原識別產(chǎn)生初始抗體群計算親和力和排斥力產(chǎn)生新抗體并計算其親和力和排斥力滿足結束條件？利用免疫算子產(chǎn)生新的抗體群結束更新記憶單元是否3.6.3幾種免疫算法基于信息熵的免疫算法反向選擇算法免疫遺傳算法克隆選擇算法基于疫苗的免疫算法基于免疫網(wǎng)絡的免疫算法115人工智能基礎第四章推理技術4.1消解原理4.2規(guī)則演繹系統(tǒng)4.3產(chǎn)生式系統(tǒng)4.4定性推理4.5不確定性推理4.6非單調(diào)推理4.1消解原理原子公式（atomicformulas）文字—一個原子公式及其否定。子句—由文字的析取組成的合適公式。消解—對謂詞演算公式進行分解和化簡，消去一些符號，以求得導出子句。1184.1.1化為子句集步驟消去蘊涵符號減少否定符號轄域對變量標準化消去存在量詞化為前束形把母式化為合取范式消去全稱量詞消去連詞符號∧更換變量名稱119舉例：(

x)｛P(x)

｛(

y)［P(y)

P(f(x,y))］∧～(

y)［Q(x,y)

P(y)］｝｝120消去蘊涵符號只應用∨和～符號，以～A∨B替換A

B。(1)(

x)｛～P(x)∨{(

y)［~P(y)∨P(f(x,y))］∧～(

y)［~Q(x,y)∨P(y)］}}4.1.1化為子句集(2)

減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上，并反復應用狄·摩根定律。(3)對變量標準化對啞元（虛構變量）改名，以保證每個量詞有其自己唯一的啞元。121(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)的約束變量，然后消去存在量詞化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形={前綴}{母式}

全稱量詞串無量詞公式122(4)(

x)｛～P(x)∨{(

y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x)）∧～P(g(x))］｝｝式中，w=g(x)為一Skolem函數(shù)。(5)(

x)(

y)｛～P(x)∨｛［～P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝(6)把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(7)消去全稱量詞所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。123(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}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。124(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)］4.1.2消解推理規(guī)則消解式的定義令L1，L2為兩任意原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β，如果L1和L2具有最一般合一σ，那么通過消解可以從這兩個父輩子句推導出一個新子句(α∨β)σ。這個新子句叫做消解式。消解式求法取各子句的析取，然后消去互補對。1254.1.2消解推理規(guī)則假言推理合并重言式空子句（矛盾）鏈式（三段論）1264.1.3含有變量的消解式含有變量的子句之消解式要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個作用于父輩子句的置換，使父輩子句含有互補文字。127P[x,f(y)]∨Q(x)∨R[f(a),y] ～P[f(f(a)),z]∨R(z，w)Q[f(f(a))]∨R(f(a)，y)∨R(f(y)，w)σ={f(f(a))/x,f(y)/z}4.1.4消解反演求解過程消解反演給出{S}，L否定L，得～L；把～L添加到S中去；把新產(chǎn)生的集合｛～L，S｝化成子句集；應用消解原理，力圖推導出一個表示矛盾的空子句

例子—儲蓄問題前提：每個儲蓄錢的人都獲得利息。結論：如果沒有利息，那么就沒有人去儲蓄錢。128(1)規(guī)定原子公式：

S(x,y)表示“x儲蓄y”M(x)表示“x是錢”

I(x)表示“x是利息”

E(x，y)表示“x獲得y”證明：129(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)化為子句形130(4)消解反演求NIL圖4.2儲蓄問題反演樹子句（1）子句（3）f(x)/z～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}～S(x,y)∨～M(y)子句（6）4.1.4消解反演求解過程反演求解過程從反演樹求取答案步驟把由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定之否定的子句中去。按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。實質把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。1314.2規(guī)則演繹系統(tǒng)

定義基于規(guī)則的問題求解系統(tǒng)運用If→Then規(guī)則來建立，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項。1324.2.1正向規(guī)則演繹系統(tǒng)定義正向規(guī)則演繹系統(tǒng)是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。

求解過程事實表達式的與或形變換在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實表示為非蘊涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。1334.2.1正向規(guī)則演繹系統(tǒng)事實表達式的與或圖表示134Q(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)圖4.5一個事實表達式的與或樹表示4.2.1正向規(guī)則演繹系統(tǒng)與或圖的F規(guī)則變換這些規(guī)則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。我們把允許用作規(guī)則的公式類型限制為下列形式：

L

W

式中：L是單文字；W為與或形的唯一公式。1354.2.2逆向規(guī)則演繹系統(tǒng)定義逆向規(guī)則演繹系統(tǒng)是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。

求解過程目標表達式的與或形式與或圖的B規(guī)則變換作為終止條件的事實節(jié)點的一致解圖1364.2.3雙向規(guī)則演繹系統(tǒng)正向和逆向規(guī)則演繹系統(tǒng)各有利弊結合正向和逆向規(guī)則演繹系統(tǒng)的優(yōu)點建立在正向和逆向規(guī)則演繹系統(tǒng)相結合的基礎上總數(shù)據(jù)庫由表示目標和表示事實的兩個與或圖結構組成分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正1374.3產(chǎn)生式系統(tǒng)定義用來描述若干個不同的以一個基本概念為基礎的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。實質論域的知識分為兩部分：用事實表示靜態(tài)知識，如事物、事件和它們之間的關系；用產(chǎn)生式規(guī)則表示推理過程和行為。1384.3.1產(chǎn)生式系統(tǒng)的結構產(chǎn)生式規(guī)則總數(shù)據(jù)庫控制策略139控制策略圖4.12產(chǎn)生式系統(tǒng)的組成結構總數(shù)據(jù)庫產(chǎn)生式規(guī)則4.3.1產(chǎn)生式系統(tǒng)的結構選擇規(guī)則到執(zhí)行操作的步驟匹配把當前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。沖突當有一條以上規(guī)則的條件部分和當前數(shù)據(jù)庫相匹配時，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。操作操作就是執(zhí)行規(guī)則的操作部分。1404.3.2產(chǎn)生式系統(tǒng)的表示事實的表示樹狀結構網(wǎng)狀結構規(guī)則的表示單個規(guī)則的表示規(guī)則間的關系規(guī)則按參數(shù)分類網(wǎng)狀結構1414.3.3產(chǎn)生式系統(tǒng)的推理

正向推理從一組表示事實的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。

逆向推理從表示目標的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實謂詞或命題成立，即首先提出一批假設目標，然后逐一驗證這些假設。

雙向推理雙向推理的推理策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標的匹配。1424.3.4產(chǎn)生式系統(tǒng)示例143圖4.20

網(wǎng)上產(chǎn)生式系統(tǒng)4.4定性推理4.4.1定性推理概述定性推理（qualitativereasoning）是從物理系統(tǒng)（包括自然系統(tǒng)和人造系統(tǒng)）的結構描述出發(fā)，以定性方法研究系統(tǒng)的結構、行為、功能以及它們之間的因果關系等，目的是預測系統(tǒng)的行為并給出合理的解釋。符合人類的常識推理，可實現(xiàn)對不完備、不一致、不精確知識的推理。降低問題求解的代價，提高問題求解的效率。1444.4.2定性模型推理定性變量對數(shù)軸的區(qū)間劃分而得到的離散集合，一般是將整個數(shù)軸(-∞,+∞)劃分為三個區(qū)間(-∞,0)、[0,0]、(0,+∞)。定性方程（不等式）145圖4.21

彈簧振動系統(tǒng)木塊(m)4.5不確定性推理不確定性推理研究復雜系統(tǒng)不完全性和不確定性的有力工具。有兩種不確定性，即關于證據(jù)的不確定性和關于結論的不確定性。如果在推理過程中所使用的知識、證據(jù)等具有不確定性，那么這種推理就屬于不確定性推理。1464.5.1概率推理Bayes公式及主觀Bayes方法證據(jù)的不確定性描述基于主觀Bayes方法的不確定性推理結論不確定性的合成算法1474.5.2貝葉斯推理貝葉斯網(wǎng)絡亦稱信念網(wǎng)絡，是因果關系的不確定性處理模型，其網(wǎng)絡拓樸結構是一個有向無環(huán)圖(DAG)。4.5.3模糊邏輯推理語言變量證據(jù)模糊性及模糊規(guī)則的表示模糊推理1484.6非單調(diào)推理

定義非單調(diào)推理用來處理那些不適合用謂詞邏輯表示的知識。它能夠較好地處理不完全信息、不斷變化的情況以及求解復雜問題過程中生成的假設，具有較為有效的求解效率。1494.6.1缺省推理定義1如果X不知道，那么得結論Y。定義2如果X不能被證明，那么得結論Y。

定義3如果X不能在某個給定的時間內(nèi)被證明，那么得結論Y。

1504.6.2非單調(diào)推理系統(tǒng)正確性維持系統(tǒng)(TruthMaintenaneSystem,TMS)用以協(xié)助其它推理程序維持系統(tǒng)的正確性。支持表(SupportList)條件證明(ConditionProve)151人工智能基礎第五章機器學習5.1機器學習概述5.2機器學習的主要策略與基本結構5.3常用的幾種學習方法5.4基于神經(jīng)網(wǎng)絡的學習5.1機器學習概述5.1.1機器學習的定義和發(fā)展

機器學習的定義機器學習是研究如何使用機器來模擬人類學習活動的一門學科。稍為嚴格的提法是：機器學習是一門研究機器獲取新知識和新技能,并識別現(xiàn)有知識的學問。1545.1.1機器學習的定義和發(fā)展機器學習的發(fā)展分為4個時期第一階段是在50年代中葉到60年代中葉，屬于熱烈時期。第二階段在60年代中葉至70年代中葉，被稱為機器學習的冷靜時期。第三階段從70年代中葉至80年代中葉，稱為復興時期。機器學習的最新階段始于1986年。1555.1.1

機器學習的定義和發(fā)展機器學習進入新階段的表現(xiàn)機器學習已成為新的邊緣學科并在高校形成課程。綜合各種學習方法機器學習與人工智能問題的統(tǒng)一性觀點正在形成。各種學習方法的應用范圍不斷擴大。數(shù)據(jù)挖掘和知識發(fā)現(xiàn)的研究已形成熱潮。與機器學習有關的學術活動空前活躍。1565.2機器學習的主要策略和

基本結構機器學習所采用的策略大體上可分為4種機械學習傳授學習策略類比學習系統(tǒng)通過事例學習策略157環(huán)境學習知識庫執(zhí)行圖5.1學習系統(tǒng)的基本結構5.2機器學習的主要策略和

基本結構影響學習系統(tǒng)設計的重要要素環(huán)境向系統(tǒng)提供的信息知識庫表達能力強易于推理容易修改知識庫知識表示易于擴展執(zhí)行部分復雜性反饋透明性1585.3常見的幾種機械學習5.3.1機械學習機械學習的模式及主要問題機器學習模式機器學習是最簡單的學習方法。機器學習就是記憶，即把新的知識存儲起來，供需要時檢索調(diào)用，而不需要計算和推理。機械學習又是最基本的學習過程。任何學習系統(tǒng)都必須記住它們獲取的知識。1595.3.1機械學習機械學習模式Lenat，Hayes-Roth和Klahr等人于1979年關于機械學習提出一種有趣的觀點。160存儲計算推導歸納算法與理論機械記憶搜索規(guī)則圖5.2數(shù)據(jù)化簡級別圖5.3.1機械學習機械學習的主要問題3個重要的問題：存儲組織，穩(wěn)定性和存儲與計算之間的權衡。存儲組織信息環(huán)境的穩(wěn)定性與存儲信息的適用性問題存儲與計算之間的權衡1615.3.2基于解釋的學習基于解釋的學習，簡稱為解釋學習，是20世紀80年代中期開始興起的一種機器學習方法。解釋學習根據(jù)任務所在領域知識和正在學習的概念知識，對當前實例進行分析和求解，得出一個表征求解過程的因果解釋樹，以獲取新的知識。在獲取新的知識過程中，通過對屬性、表征現(xiàn)象和內(nèi)在關系等進行解釋而學習到新的知識。1625.3.2基于解釋的學習解釋學習過程和算法利用基于解釋的方法對訓練實例進行分析與解釋，以說明它是目標概念的一個實例。對實例的結構進行概括性解釋，建立該訓練實例的一個解釋結構，以滿足對所學概念的定義；解釋結構的各個葉節(jié)點應符合可操作性準則，且使這種解釋比最初的例子適用于更大的一類例子。從解釋結構中識別出訓練實例的特性，并從中得到更大一類例子的概括性描述，獲取一般控制知識。1635.3.2基于解釋的學習1986年米切爾（Mitchell）等人為基于解釋的學習提出了一個統(tǒng)一的算法EBG。164訓練例子操作準則知識庫新規(guī)則目標概念圖5.3

EBG問題5.3.2基于解釋的學習EBG求解問題的形式給定：目標概念描述TC；訓練實例TE；領域知識DT；操作準則OC。求解：訓練實例的一般化概括，使之滿足目標概念的充分概括描述TC；操作準則OC。1655.3.2基于解釋的學習EBG算法分為解釋和概括兩步：解釋，即根據(jù)領域知識建立一個解釋，以證明訓練實例如何滿足目標概念定義。目標概念的初始描述通常是不可操作的。概括，即對上一步證明樹進行處理，對目標概念進行回歸，包括用變量代替常量以及必要的新項合成等工作，從而得到所期望的概念描述。1665.3.3基于事例的學習當無法建立好的模型時，通過記錄事例進行學習是一種可取的方法。任何時候都可以應用相容啟發(fā)（consistencyheuristic）方法，把某個預先觀察過的事物的特性賦予另一個從未見過的新事物。學會如何應用k-維樹結構迅速地找到特征空間內(nèi)的最鄰近物體。1675.3.3基于事例的學習原經(jīng)驗的記錄與檢索相容啟發(fā)使事例支持特性相容啟發(fā)解決動力學難題最近鄰物體的尋求快速串行過程以對數(shù)次數(shù)求得最鄰近物體并行硬件更快求得最鄰近物體1685.3.4基于概念的學習對概念學習（conceptlearning）的研究遵循兩條不同的路線：基于工程方法的概念學習，它從可能的學習機理出發(fā)，試圖試驗并確定概念學習的工程方法?；谡J知建模的概念學習，極力開發(fā)出人類概念學習的計算理論。1695.3.5基于類比的學習類比（analogy）能夠清晰簡潔地描述對象間的相似性，同時也把某些測試相似性質的任務由演講者（或教師）轉移到聽者（或學生）。基于類比的學習的步驟類比學習的表示類比學習的求解170類比學習的表示假若關于對象的知識表達為框架集，那么，用類比法學習可描述為從一個框架（源框架）的槽值傳送到另一框架（目標框架）的槽，此種傳送分為兩步：利用源框架產(chǎn)生推薦槽，這些槽的值可傳送到目標框架利用目標框架中已有的信息來篩選由第一步推薦的相似性171類比學習的求解在從源框架被選擇的槽建立一組可能的傳遞框架之后，必須用目標框架的知識來篩選它們。問題求解：采用生成測試法，首先生成可能類似物，再挑選最佳物知識表示和推理的標準技術使用框架來表示要比較的對象ISA分層結構，以便找出被比較對象的密切關系1725.3.6基于決策樹的歸納學習決策樹的概念決策樹是一種樹結構，其節(jié)點分為兩類，一類是內(nèi)節(jié)點，另一類是葉節(jié)點。內(nèi)節(jié)點一般用一個屬性名來標記，代表對該屬性的測試；與內(nèi)節(jié)點連接的邊表示對該屬性（該內(nèi)節(jié)點對應的屬性）測試的輸出。每個類節(jié)點表示分類結果，一般用類標號屬性值來標識。1735.3.6基于決策樹的歸納學習決策樹學習決策樹學習是一種歸納學習特征是由若干個具體的實例表現(xiàn)出來的特征、屬性中，通過比較、概括等方法而得出一般性規(guī)律和結論。決策樹學習的過程就是由空樹開始從訓練集中不斷選擇測試屬性、逐步創(chuàng)建決策樹的過程。1745.3.6基于決策樹的歸納學習從決策樹提取分類規(guī)則一顆決策樹實際上相當于一個分類規(guī)則集，樹中的樹葉和分類規(guī)則是一一對應的，從樹根到樹葉路徑上的屬性-值對的合取成為分類規(guī)則的前件，標號屬性和葉節(jié)點中的標記構成的屬性-值對作為分類規(guī)則的后件，這樣得到的規(guī)則就是該葉節(jié)點對應的分類規(guī)則。規(guī)則一般用蘊涵式的形式來表示。1755.3.7強化學習強化學習的概念強化學習就是智能系統(tǒng)從環(huán)境到行為映射的學習，以使獎勵信號（強化信號）函數(shù)值最大。強化學習的基本模型和原理176圖5.13強化學習的基本模型5.3.7強化學習機器人強化學習系統(tǒng)實現(xiàn)方法177圖5.14

基于進化強化學習的網(wǎng)絡結構5.3.7強化學習強化學習的應用在游戲比賽中的應用在控制系統(tǒng)中的應用在機器人中的應用基于進化強化學習的網(wǎng)絡模型設計行動網(wǎng)絡評估網(wǎng)絡1785.4基于神經(jīng)網(wǎng)絡的學習5.4.1神經(jīng)網(wǎng)絡的組成與特性生理神經(jīng)元的結構與功能生理神經(jīng)元的結構179圖5.15

生理神經(jīng)元的組成5.4.1神經(jīng)網(wǎng)絡的組成與特性生理神經(jīng)元的功能神經(jīng)元通過突觸形成的網(wǎng)絡，傳遞神經(jīng)元間的興奮與抑制。人工神經(jīng)元的組成與分類人工神經(jīng)元的組成模擬神經(jīng)元處理單元PE（processingelement）有向弧則1805.4.1神經(jīng)網(wǎng)絡的組成與特性ANN的數(shù)學描述非線性特性激發(fā)函數(shù)閾值型分段線性強飽和型Sigmoid型激發(fā)函數(shù)（S型函數(shù)）典型人工神經(jīng)網(wǎng)絡181圖5.17常用NN輸入輸出特性5.4.2基于BP網(wǎng)絡的學習反向傳播（back-propagation,BP）算法是一種計算單個權值變化引起網(wǎng)絡性能變化值的較為簡單的方法。BP算法過程包含從輸出節(jié)點開始，反向地向第一隱含層傳播由總誤差引起的權值修正。1825.4.2基于BP網(wǎng)絡的學習反向傳播網(wǎng)絡的結構輸入節(jié)點輸出節(jié)點隱（層）節(jié)點183圖5.18

BP網(wǎng)絡5.4.2基于BP網(wǎng)絡的學習反向傳播公式梯度法（gradientascent）連鎖法（chainrule)第一，性能對權值的偏導數(shù)取決于性能對下一個輸出的偏導數(shù)；第二，性能對輸出的偏導數(shù)取決于性能對下一層輸出的偏導數(shù)。1845.4.2基于BP網(wǎng)絡的學習反向傳播學習算法反向傳播學習示例識別單個概念的學習問題識別兩個概念的學習問題185186圖5.19反向傳播算法框圖5.4.3基于Hopfield網(wǎng)絡的學習Hopfield網(wǎng)絡模型Hopfield網(wǎng)絡是一種具有正反相輸出的帶反饋人工神經(jīng)元，如圖5.24(a)所示。187圖5.24

Hopfield網(wǎng)絡原型及模擬電路5.4.3基于Hopfield網(wǎng)絡的學習Hopfield網(wǎng)絡算法188圖5.25

Hopfield算法框圖5.4.4基于神經(jīng)網(wǎng)絡的推理NN（Neuralnets）技術的一個主要特點是能從有關領域的樣本集自動獲取(學習)該領域的知識。NN技術的一個弱點是它所獲取的知識是分布于網(wǎng)絡中的隱式知識，難于與推理網(wǎng)絡相一致，難于具有可解釋性。1891905.4.4基于神經(jīng)網(wǎng)絡的推理神經(jīng)網(wǎng)絡結構模型有關定義語義框架的具體化和詞匯表初始NN的構造相應的學習算法前向計算后向計算5.4.4基于神經(jīng)網(wǎng)絡的推理神經(jīng)網(wǎng)絡到推理網(wǎng)絡的轉換算法將全連接的NN轉換成部分連接的NN去掉隱含層中的某個性節(jié)點去掉隱含層共性節(jié)點中的冗余節(jié)點從神經(jīng)網(wǎng)絡到推理網(wǎng)絡和產(chǎn)生式規(guī)則集191圖5.30

獲取多級推理的產(chǎn)生式規(guī)則人工智能基礎第六章專家系統(tǒng)6.1專家系統(tǒng)概述6.2基于規(guī)則的專家系統(tǒng)6.3基于框架的專家系統(tǒng)6.4基于模型的專家系統(tǒng)6.5專家系統(tǒng)的設計、評價與開發(fā)6.6專家系統(tǒng)設計舉例6.7新型專家系統(tǒng)6.8知識發(fā)現(xiàn)

6.1專家系統(tǒng)概述專家系統(tǒng)(expertsystem)是人工智能應用研究最活躍和最廣泛的課題之一定義：是一個含有大量的某個領域專家水平的知識與經(jīng)驗智能計算機程序系統(tǒng)，能夠利用人類專家的知識和解決問題的方法來處理該領域問題。1946.1.1專家系統(tǒng)的一般特點專家系統(tǒng)具有一些共同的特點和優(yōu)點專家系統(tǒng)的特點啟發(fā)性透明性靈活性專家系統(tǒng)的優(yōu)點1956.1.2專家系統(tǒng)的結構與類型專家系統(tǒng)的簡化結構指專家系統(tǒng)各組成部分的構造方法和組織形式。

圖6.1專家系統(tǒng)簡化結構圖1966.1.2專家系統(tǒng)的結構與類型理想專家系統(tǒng)的結構知識庫綜合數(shù)據(jù)庫推理機解釋器接口圖6.2理想專家系統(tǒng)結構圖1976.1.2專家系統(tǒng)的結構與類型專家系統(tǒng)的類型解釋專家系統(tǒng)診斷專家系統(tǒng)規(guī)劃專家系統(tǒng)控制專家系統(tǒng)教學專家系統(tǒng)預測專家系統(tǒng)設計專家系統(tǒng)監(jiān)視專家系統(tǒng)調(diào)試專家系統(tǒng)修理專家系統(tǒng)1986.1.3專家系統(tǒng)的建造步驟設計初始知識庫問題知識化知識概念化概念形式化形式規(guī)則化規(guī)則合法化原型機（prototype）的開發(fā)與試驗知識庫的改進與歸納199圖6.3專家系統(tǒng)設計與建立步驟6.2基于規(guī)則的專家系統(tǒng)6.2.1基于規(guī)則的專家系統(tǒng)的基本結構200圖6.4專家系統(tǒng)的基本結構6.2.2基于規(guī)則專家系統(tǒng)的特點基于規(guī)則專家系統(tǒng)的優(yōu)點自然表達知識模塊性智能成比例增長從嚴格語法獲取解釋啟發(fā)性知識的使用可以合用變量201控制與知識分離易于擴展相關知識的使用一致性檢查不確定知識的使用6.2.2基于規(guī)則專家系統(tǒng)的特點基于規(guī)則專家系統(tǒng)的缺點必需精確匹配有不清楚的規(guī)則關系具有大量規(guī)則的專家系統(tǒng)可能慢對一些問題不適用2026.2.3基于規(guī)則的專家系統(tǒng)舉例EMYCIN中，采用的是逆向推理的深度優(yōu)先的控制策略，它提供了專門的規(guī)則語言來表示領域知識，基本的規(guī)則形式是：(IF<前提>THEN<行為>[ELSE<行為>])當前提為真時，該規(guī)則把前提與一個行為結合起來，否則與另一個行為結合起來，并且可以用一個-1到+1之間的數(shù)字來表示在該前提下行為的可信程度。2036.2.3基于規(guī)則的專家系統(tǒng)舉例一條判斷細菌類別的規(guī)則可表示如下：PREMISE:［＄AND(SAMECNTXTSITEBLOOD)(NOTDEFINITECNTXTIDENT)(SAMECNTXTSTAINGRAMNEG)(SAMECNTXTMORPHROD)(SAMECNTXTBURNT)]ACTION:(CONCLUDECNTXTIDENTPSEUDOMONASTALLY0.4)其含意如下：如果培養(yǎng)物的部位是血液細菌的類別確不知道細菌的染色是革藍氏陰性細菌的外形是桿狀病人被嚴重地燒傷那么以不太充分的證據(jù)（可信程度0.4）說明細菌的類別是假單菌。2046.3基于框架的專家系統(tǒng)6.3.1基于框架的專家系統(tǒng)的概念基于框架的專家系統(tǒng)的推理和語義網(wǎng)絡一樣遵循匹配和繼承的原則，而且框架中如ifneeded、ifadded等槽的槽值是附加過程，在推理過程中起重要作用。若將一個子框架視作知識單位，有如一條產(chǎn)生式規(guī)則，這樣可將一個問題的求解，通過匹配分散為各有關的子框架的協(xié)調(diào)過程，當然實現(xiàn)起來較為困難。2056.3.2基于框架專家系統(tǒng)的繼承、槽和方法基于框架專家系統(tǒng)的繼承繼承：后輩框架呈現(xiàn)其父輩框架的特征的過程。后輩框架通過這個特征繼承其父輩框架的所有特征。實例繼承其父輩的所有屬性、屬性值和槽。異常處理多重繼承2066.3.2基于框架專家系統(tǒng)的繼承、槽和方法基于框架專家系統(tǒng)的槽槽：框架屬性有關的擴展知識。槽提供對屬性值和系統(tǒng)操作的附加控制。類型：定義和屬性相關值的類型;默認：定義默認值;文檔：提供屬性文檔;約束：定義允許值;最小界限：建立屬性的下限;最大界限：建立屬性的上限;如果需要：指定如果需要屬性值時采取的行為;如果改變：指定如果屬性值改變時采取的行為。2076.3.3基于框架的專家系統(tǒng)舉例船舶裝載專家系統(tǒng)樹的每一個節(jié)點是如下形式的框架結構：框架名AKOVALUE<值>PEOPDEFAULT<表1>SFIF-NEEDED<算術表達式>CONFLICTADD<表2>其中框架名用類名表示。208圖6.6一個框架系統(tǒng)6.3.2基于框架專家系統(tǒng)的繼承、槽和方法基于框架專家系統(tǒng)的方法方法：附加到對象中需要時執(zhí)行的過程。在一些應用程序中“如果需要”方法只有當需要時才獲取屬性值?！叭绻淖儭辈蹐?zhí)行一些方法的情況下屬性值改變事件中的函數(shù)。2096.4基于模型的專家系統(tǒng)6.4.1基于模型的專家系統(tǒng)的概念采用基于模型的推理方法?；谀Ｐ偷耐评矸椒ㄊ歉鶕?jù)反映事物內(nèi)部規(guī)律的客觀世界的模型進行推理。多種模型表示系統(tǒng)各部件的部分/整體關系的結構模型表示各部件幾何關系的幾何模型表示各部件的功能和性能的功能模型表示各部件因果關系的因果模型淺層推理與深層推理2106.4.2基于模型的專家系統(tǒng)舉例汽車啟動211圖6.9汽車啟動部分的因果網(wǎng)絡6.5專家系統(tǒng)的設計、評價與

開發(fā)6.5.1專家系統(tǒng)的設計專家系統(tǒng)的設計技巧準則設計系統(tǒng)時，首先集中精力研究一小部分假設，先不要考慮那些不十分確定的事物。挑選那些最有利于區(qū)別各個假設的觀測?？梢杂性S多方式來組合觀測。在把那些并不具有很強的預測或區(qū)