第5章-產生式表示與專家系統(tǒng)

2023/2/281第5章產生式表示與專家系統(tǒng)2023/2/282內容5.1產生式與產生式系統(tǒng)5.2專家系統(tǒng)概述5.3專家系統(tǒng)結構及工作過程5.4專家系統(tǒng)的開發(fā)5.5專家系統(tǒng)的實例5.6新型專家系統(tǒng)2023/2/2835.1產生式與產生式系統(tǒng)（1）產生式1943年美國數學家Post，最早提出產生式系統(tǒng)并把它作為計算手段。同一時期，Chomsky在探討自然語言結構時，提出了文法分層的概念，并提出了文法的重寫規(guī)則，即語言生成規(guī)則，語言生成規(guī)則實際是特殊的產生式。1960年，Backus提出了著名的BNF，用以描述計算機語言的文法。后來發(fā)覺，BNF范式事實上就是Chomsky的上下文無關文法。2023/2/2845.1產生式與產生式系統(tǒng)（2）5.1.1產生式表示5.1.2產生式系統(tǒng)結構5.1.3產生式系統(tǒng)工作過程2023/2/2855.1.1產生式表示（1）產生式的一般形式為：前件后件（狀況行為）前件是前提，規(guī)則的執(zhí)行條件。后件是結論或動作，規(guī)則體。產生式規(guī)則的語義：假如前提滿足，則可得結論或者執(zhí)行相應的動作，即后件由前件觸發(fā)。產生式也可以表示前面探討過的各種操作在形式語言中的文法規(guī)則也稱為產生式在推理系統(tǒng)中產生式的前件就是前提，后件就是結論，所以，產生式又是一個前提-結論對。2023/2/2865.1.1產生式表示（2）產生式規(guī)則的例子：（1）假如電視機聲音太大引起鄰居埋怨，則將音量調小一點兒。（2）假如申請人有良好的金融聲譽和良好的資產負債表，那么貸款應當被批準。（3）IF當前環(huán)境安排設備給總線組件，并且有一個未安排的雙端口磁盤驅動器，并且已知所需限制器類別，并且每個限制器沒有任何設備安排給它，并且這些限制器能夠支持的設備數目已知THEN安排磁盤驅動器給每一個限制器，并且登記相關的限制器對，其中每一個限制器支持一個驅動器第（3）條規(guī)則用在配置DECVAX計算機系統(tǒng)的XCON/R1專家系統(tǒng)中。2023/2/2875.1.1產生式表示（3）例5.1三個聰慧人問題。古代有個國王想知道他的三個大臣中誰最聰慧，就在他們每個人前額上都畫了一個點，他們都能看到別人點的顏色，但看不到自己點的顏色。國王說，你們中間至少有一個人的點是白色的。于是重復地問他們：“誰知道自己點的顏色？”三位大臣們頭兩次都回答說不知道。題目要求證明下一次他們全都會說“知道”，并且全部的點都是白色。2023/2/2885.1.1產生式表示（4）分析：這類問題的特點是有有限個受試者，每個人對問題都只有部分了解，無法干脆求解。但在推理過程中每個人又可以從別人那里獲得新的學問，重新進行推理。可以用產生式來表達推理過程中所用到的各種學問。2023/2/2895.1.1產生式表示（5）狀態(tài)集合表示：用x1,x2,x3表示三個人點的顏色，1表示白色，0表示非白色。X＝(x1,x2,x3)表示顏色分布狀態(tài)。全部可能的狀態(tài)集合(可能界PW0)：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}實際給定的狀態(tài)為現實界X0＝(x10,x20,x30)用解除法找尋X0。2023/2/28105.1.1產生式表示（6）解除過程：第一次，大臣只知道至少有一個人是白點，解除(0,0,0)狀態(tài)。這時假如有人看到兩個非白點，依據解除的狀態(tài)可推知自己是白點。其次次大臣依據沒有一個人知道自己點顏色的事實推知至少兩人為白點。解除(0,0,1)、(0,1,0)、(1,0,0)狀態(tài)。這時假如有人看到一個非白點，依據解除后得到的狀態(tài)可推知自己的點是白的。第三次，大臣們依據仍無人知道自己點顏色的新事實推知沒有一個非白點出現，即X0=(1,1,1)。于是三人都知道自己點的顏色是白的。2023/2/28115.1.1產生式表示（7）引入一些中介狀態(tài)，并定義下述符號：Si——i大臣看到的非白點數；Wi——i大臣猜出自己點的顏色否。假如他宣布已知道自己點的顏色，為1，否則為0；n——X0中白點的個數?？蓪η懊娴姆治鲞^程形式化。

2023/2/28125.1.1產生式表示（8）第一次，大臣只知道至少有一個人是白點，解除X0={(0,0,0)}狀態(tài)。(n>=1)<=>X0{(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}；其次次大臣依據沒有一個人知道自己點顏色的事實推知至少兩人為白點。(2)(n>=1)(Si=2)=>(Wi=1),(i=1,2,3,下同)；(3)(i)(Wi=1)(n>=1)=>(n=1)；(4)(n=1)=>(i)(Wi=1)；(5)(i)(Wi=0)(n>=1)=>(n>=2);(6)(n>=2)<=>X0{(0,1,1),(1,0,1),(1,1,0),(1,1,1)}；第三次，大臣們依據仍無人知道自己點顏色的新事實推知沒有一個非白點出現。(7)(n>=2)(Si=1)=>(Wi=1);(8)(i)(Wi=1)(n>=2)=>(n=2);(9)(n=2)=>(i)(Wi=1);(10)(i)(Wi=0)(n>=2)=>(n=3);(11)(n=3)<=>X0{(1,1,1)}；(12)(n=3)=>(i)(Wi=1).2023/2/28135.1.1產生式表示（8）上述結果可以推廣到更一般的狀況：設有m個大臣，國王說至少有l(wèi)個人的點是白色的，則有下述產生式：(1)(n>=l)<=>X0{x|x中的白點數>=l}；(2)(n>=l)(Si=m-l)=>(Wi=1),(i=1,2,…,m,下同)；(3)(i)(Wi=1)(n>=l)=>(n=l)；(4)(n=l)=>(i)(Wi=1)；(5)(i)(Wi=0)(n>=l)(l<m-1)=>(n>=l＋1);(6)(i)(Wi=0)(n>=l)(l＝m-1)=>(n＝m)。2023/2/28145.1.2產生式系統(tǒng)結構（1）問題求解框架與產生式系統(tǒng)對應：敘述性學問——動態(tài)（全局）數據庫過程性學問——產生式規(guī)則庫限制性學問——推理機產生式規(guī)則庫推理機動態(tài)數據庫2023/2/28155.1.2產生式系統(tǒng)結構（2）三個組成部分：動態(tài)數據庫——人工智能系統(tǒng)的數據結構中心。是一個動態(tài)數據結構，用來存放初始事實數據、中間結果和最終結果。相當于人的短期記憶功能。產生式規(guī)則庫——作用在全局數據庫上的一些規(guī)則的集合。每條規(guī)則都有確定的條件，若全局數據庫中內容滿足這些條件可調用這條規(guī)則。一般可形成一個稱為推理網絡的結構圖。相當于人的長期記憶功能。推理機——負責產生式規(guī)則的前提條件測試或匹配，規(guī)則的調度和選取，規(guī)則體的說明和執(zhí)行。即推理機實施推理，并對推理進行限制，它也是規(guī)則的說明程序。相當于人的認知處理器。2023/2/28165.1.2產生式系統(tǒng)結構（3）例5.2猴子摘香蕉問題。如圖5-2所示，一個房間里，天花板上掛著一串香蕉。房間里有一只猴子，還有一只可被猴子推移的箱子，而且，當猴子登上箱子時剛好可以摘到香蕉。設猴子在房間的a處，箱子在b處，香蕉在c處。問猴子如何行動可以摘取香蕉？建立產生式系統(tǒng)。解：（1）全局數據庫中表達問題在求解過程中所處的各種狀態(tài)：用四元組（w，x，y，z）表示。其中：w：猴子的水平位置，w

｛a，b，c｝；x：是否在箱子上，0表示不在箱頂，1表示在箱頂；y：箱子的水平位置，y｛a，b，c｝；z：猴子是否拿到香蕉，0表示沒有拿到香蕉，1表示拿到香蕉。初始事實是（a，0，b，0），目標位置為（c，1，c，1）

2023/2/28175.1.2產生式系統(tǒng)結構（4）（2）規(guī)則集：規(guī)則動作條件動態(tài)數據庫事實變更R1goto（u）（w，0，y，z）（u，0，y，z）R2pushbox（v）（w，0，w，z）（v，0，v，z）R3climbbox（w，0，w，z）（w，1，w，z）R4grasp（c，1，c，0）（c，1，c，1）其中，u,v｛a，b，c｝（3）推理結果：R2（c）R1（b）（a，0，b，0）（b，0，b，0）（c，0，c，0）2023/2/28185.1.3產生式工作過程（1）推理機在工作過程中須要完成的工作主要可以分為三個階段：高效模式匹配沖突消解推理常用提高匹配效率的方法：（1）索引匹配（2）分層匹配（3）過濾匹配2023/2/28195.1.3產生式工作過程（2）沖突消解策略馬爾科夫算法：按優(yōu)先級排序消退沖突Rete算法：不是用事實去匹配每一條規(guī)則，僅考察有變更的規(guī)則。其他：規(guī)模排序：對全部匹配成功的產生式中選擇前提條件最多或者狀況元素最多者作為優(yōu)先執(zhí)行的規(guī)則加權排序：給初始事實或中間結論以不同的優(yōu)先權，與優(yōu)先權較高的事實匹配的產生式優(yōu)先運用2023/2/28205.1.3產生式工作過程（3）產生式系統(tǒng)推理正向推理反向推理雙向推理2023/2/28215.1.3產生式工作過程（4）正向推理過程2023/2/28225.1.3產生式工作過程（5）反向推理過程2023/2/28235.1.3產生式工作過程（6）例5.35.4汽車輪胎故障診斷及實行相應措施的產生式系統(tǒng)及其求解。r1：IF輪胎癟了AND空氣很快泄出THEN確認故障：輪胎沒有氣r2：IF輪胎變形了AND你的輪胎邊緣有凹入THEN確認故障：變形了的輪胎。r3：IF輪胎被磨損AND磨損嚴峻THEN確認故障：磨損了的輪胎r4：IF變形了的輪胎AND你要更換輪胎THEN輪胎須要更換r5：IF磨損了的輪胎AND你要更換輪胎THEN輪胎須要更換r6：IF輪胎沒有氣AND你要更換輪胎THEN輪胎須要更換r7：IF輪胎沒有氣AND你要修理輪胎THEN輪胎須要修理r8：IF輪胎須要修理AND你有一個扳手AND你有一個千斤頂AND你的狀態(tài)良好THEN實行措施：自己修理它2023/2/28245.1.3產生式工作過程（7）r9：IF輪胎須要更換AND你離電話很近THEN實行措施：呼叫馬路服務獲得幫助r10：IF輪胎須要修理AND你要給這個輪胎充氣AND你有一個泵AND你知道如何運用它THEN實行措施：自己給輪胎充氣r11：IF輪胎須要修理AND你知道某人有這個技術AND他能夠做這個事情THEN實行措施：懇求他的幫助r12：IF輪胎須要更換AND你知道某人有這個技術AND他能夠做這個事情THEN實行措施：懇求他的幫助r13：IF輪胎須要更換AND你有一個扳手AND你有一個千斤頂AND你的狀態(tài)良好THEN實行措施：自己更換它2023/2/28255.1.3產生式工作過程（8）規(guī)則集形成的部分推理網絡：2023/2/28265.1.3產生式工作過程（9）已知初始事實：F1：輪胎癟了F2：空氣很快泄出F3：你要更換輪胎F4：你離電話很近目標條件：實行什么樣的措施處理故障？接受正向推理回答實行的措施來處理故障。2023/2/28275.1.3產生式工作過程（10）反向推理過程：2023/2/28285.2專家系統(tǒng)概述5.2.1什么是專家系統(tǒng)5.2.2專家系統(tǒng)的類型5.2.3專家系統(tǒng)的發(fā)展補充學問2023/2/28295.2.1什么是專家系統(tǒng)（1）專家系統(tǒng)應當具備四個特征：（1）應用于某特地領域。（2）擁有專家級學問。（3）能模擬人類專家思維和決策過程。（4）達到專家級水平。2023/2/28305.2.1什么是專家系統(tǒng)（2）專家系統(tǒng)的特點解決那些不確定性的、非結構化的、沒有算法解或雖有算法解但在現有的機器上無法實施的困難問題；強調學問與推理的分別，因而系統(tǒng)具有很好的敏捷性和可擴充性；還具有“自學習”實力，即不斷對自己的學問進行擴充、完善和提煉專家系統(tǒng)不會像人那樣簡潔疲憊、遺忘，易受環(huán)境、心情等的影響。2023/2/28315.2.2專家系統(tǒng)的類型（1）按解決問題性質分類說明型預料型設計型診斷型規(guī)劃型監(jiān)視型限制型調試型教學型修理型2023/2/28325.2.2專家系統(tǒng)的類型（2）按應用分類典型化學專家系統(tǒng)。典型電子學專家系統(tǒng)。典型醫(yī)學專家系統(tǒng)。典型工程學專家系統(tǒng)。典型地質學專家系統(tǒng)。典型計算機專家系統(tǒng)。2023/2/28335.2.2專家系統(tǒng)的類型（3）

按系統(tǒng)的體系結構分類集中式專家系統(tǒng)分布式專家系統(tǒng)人工神經網絡專家系統(tǒng)按學問表示形式基于規(guī)則的專家系統(tǒng)基于一階謂詞的專家系統(tǒng)基于框架的專家系統(tǒng)基于語義網的專家系統(tǒng)按接受的技術符號推理專家系統(tǒng)神經網絡專家系統(tǒng)2023/2/28345.2.3專家系統(tǒng)的發(fā)展（1）1.專家系統(tǒng)發(fā)展歷史第一代：這些專家系統(tǒng)具有高度專業(yè)化、求解特地問題的實力強等特點，但在體系結構的完整性、可移植性等方面存在缺陷，求解問題的實力弱；其次代：專家系統(tǒng)屬單學科專業(yè)型、應用型系統(tǒng)，其體系結構較完整，移植性方面也有所改善，而且在系統(tǒng)的人機接口、說明機制、學問獲得技術、不確定推理技術、增加專家系統(tǒng)的學問表示和推理方法的啟發(fā)性、通用性等方面都有所改進；第三代：多學科綜合型系統(tǒng)，接受多種人工智能語言，綜合接受各種學問表示方法和多種推理機制及限制策略，并起先運用各種學問工程語言、骨架系統(tǒng)及專家系統(tǒng)開發(fā)工具和環(huán)境來研制大型綜合專家系統(tǒng)；第四代：多專家協作、綜合學問庫、接受人工智能最新技術實現多Agent專家系統(tǒng)。2023/2/28355.2.3專家系統(tǒng)的發(fā)展（2）2.專家系統(tǒng)技術的發(fā)展20世紀，50、60年頭，產生式系統(tǒng)框架的提出；20世紀70年頭，領域學問的重要性，學問庫與推理機的分別，MYCIN、EMYCIN出現；20世紀80年頭，各種開發(fā)語言應用于專家系統(tǒng)，出現各種開發(fā)工具。2023/2/28365.3專家系統(tǒng)結構及工作過程5.3.1專家系統(tǒng)的結構5.3.2專家系統(tǒng)工作過程2023/2/28375.3.1專家系統(tǒng)的結構（1）1.專家系統(tǒng)的概念結構2023/2/28385.3.1專家系統(tǒng)的結構（2）2.專家系統(tǒng)實際結構圖5-10專家系統(tǒng)實際結構示例

圖5-11黑板模型

2023/2/28395.3.2專家系統(tǒng)工作過程（1）工作過程：步1依據用戶供應的證據以及問題對學問庫進行搜尋，找尋可匹配的學問片段或學問網絡；步2對同一問題可能會有多處學問片段或網絡與之匹配，即形成學問操作算子序列，構成一個假設集合；步3依據推理機供應的限制策略對形成的假設集合進行排序進入到推理機的議程中，并選擇其中在某些準則下為最優(yōu)的假設方案；步4依據推理機供應的推理機制進行推理，求解具體問題；步5假如該推理過程不能解決問題，則回溯到假設方案序列中的下一個，重復求解問題；步6上述過程循環(huán)執(zhí)行，直到問題已經解決或全部可能的求解方案都不能解決問題即本問題無解。2023/2/28405.3.2專家系統(tǒng)工作過程（2）圖5-12基于規(guī)則的專家系統(tǒng)的相關技術2023/2/28415.3.2專家系統(tǒng)工作過程（3）PROSPECTOR中的不確定性處理：斑銅巖模型2023/2/2842PROSPECTOR中的不確定性處理正向推理：將證據的不確定性傳遞給最終結論的不確定性：用戶輸入證據E，確定性因子[-5，5]；用證據匹配規(guī)則R計算組合證據的不確定性利用CP公式或EH公式計算結論H的不確定性計算組合結論的不確定性反向推理：系統(tǒng)依據評判函數確定目標、子目標，依據用戶供應的證據的可信度，轉向正向推理，進行概率傳播，直到到達可以由用戶回答的證據為止。2023/2/28435.3.2專家系統(tǒng)工作過程（4）MYCIN中的不確定性處理：在專家系統(tǒng)MYCIN中接受的推理方式就是反向鏈和深度優(yōu)先的搜尋策略。當MYCIN系統(tǒng)啟動后，系統(tǒng)會自動生成一個包含（姓名，年齡，性別，治療方案）的病人信息，其中前三項由系統(tǒng)向用戶提出詢問，要求用戶輸入，并存入數據庫中。而治療方法則是須要由系統(tǒng)自動推理得到，也是系統(tǒng)進行推理的最終目標。

2023/2/28445.3.2專家系統(tǒng)工作過程（5）為了得到治療方案，系統(tǒng)推理時，首先運用一條規(guī)則是RULE092(目標規(guī)則)，其內容為：假如：（1）有一種須要治療的病原體，且（2）可能還有其他須要治療的病原體，盡管它們還沒有從當前的培育物中被分別出來。那么：（1）給出能有效始終需治療的病原體的治療方案（2）選擇出最佳治療方案否則：指出病人不須要治療要退出的目標須要的條件，可以干脆詢問用戶，可以由其他的推理得到。2023/2/28455.4專家系統(tǒng)的開發(fā)5.4.1開發(fā)步驟和方法5.4.2學問獲得5.4.3推理機及說明機構設計5.4.4開發(fā)工具及開發(fā)環(huán)境2023/2/28465.4.1開發(fā)步驟和方法2023/2/28475.4.2學問獲得1.學問獲得方式人工學問獲得半自動學問獲得自動學問獲得2.學問獲得任務抽取學問學問的轉換學問的輸入學問的檢測2023/2/28485.4.3推理機及說明機構設計1.推理機的設計推理機的設計就是依據學問表達、學問推理方法和推理限制策略，設計具有求解特地領域的問題和自行推理的計算機軟件系統(tǒng)。2.說明結構的設計預置本文方法路徑跟蹤法，回答HOW和WHY問題策略說明法自動程序員說明方法2023/2/28495.4.4開發(fā)工具及開發(fā)環(huán)境（1）1.智能程序設計語言LISPPROLOGOPS5、FRL……2.專家系統(tǒng)外殼EMYCINKASEXPERT……2023/2/28505.4.4開發(fā)工具及開發(fā)環(huán)境（2）3.開發(fā)環(huán)境AGETEIRESIASCLIPSVPEXPERTESTA2023/2/28515.5專家系統(tǒng)的實例（1）1學問表示2023/2/28525.5專家系統(tǒng)的實例（2）2023/2/28535.5專家系統(tǒng)的實例（3）2.專家系統(tǒng)處理過程不同的問題轉向不同的問題節(jié)點，依據事實選擇要執(zhí)行的動作3.推理的限制策略及說明汽車故障診斷專家系統(tǒng)接受的是正向推理的方式，在學問庫的節(jié)中的規(guī)則依據確定的依次排列，當任一規(guī)則的條件得到滿足后，則執(zhí)行相應的動作2023/2/28545.6新型專家系統(tǒng)5.6.1分布式專家系統(tǒng)5.6.2協同式專家系統(tǒng)5.6.3模糊專家系統(tǒng)5.6.4神經網絡專家系統(tǒng)2023/2/28555.6.1分布式專家系統(tǒng)分布式專家系統(tǒng)具有分布處理的特征，是把一個專家系統(tǒng)的功能分解到各個處理機上并行工作，以縮短問題求解的時間，提高專家系統(tǒng)的效率，設計一個分布式專家系統(tǒng)一般要考慮以下三方面的問題：功能分布學問分布驅動分布限制驅動數據驅動目標驅動事務驅動2023/2/28565.6.2協同式專家系統(tǒng)（1）協同式專家系統(tǒng)也稱為群專家系統(tǒng)，能夠綜合若干相近領域或一個領域的多個方面的分專家系統(tǒng)的相互協作，共同解決一個更廣領域的問題。協同式專家系統(tǒng)與分布式專家系統(tǒng)有相像性，但協同式專家更強調各子專家系統(tǒng)之間的協同合作，它可以在同一個處理機上實現各子專家系統(tǒng)。1.協同方法多智能體規(guī)劃方法功能化有效協同方法談判方法2023/2/