人工智能第二章49

知識表示知識是一切智能行為的根底，也是軟件智能化的重要研討對象。要使軟件具有智能，就必需使它具有知識，而要使軟件具有知識，首先必需處理知識的表示問題。所謂知識表示實(shí)踐上就是對知識的一種描畫，即用一些商定的符號把知識編碼成一組計(jì)算機(jī)可以接受的數(shù)據(jù)構(gòu)造。所謂知識表示過程就是把知識編碼成某種數(shù)據(jù)構(gòu)造的過程。普通來說，同一知識可以有多種不同的表示方式，而不同表示方式所產(chǎn)生的效果又能夠不一樣。12/25/20231常用的知識表示方法非構(gòu)造化方法邏輯表示法QA3,STRIPS,DART,MOMO產(chǎn)生式系統(tǒng)DENDRAL，MYCIN構(gòu)造化方法框架語義網(wǎng)絡(luò)過程式知識表示法12/25/20232第二章產(chǎn)生式系統(tǒng)2.1產(chǎn)生式系統(tǒng)概述一、產(chǎn)生式系統(tǒng)的定義產(chǎn)生式系統(tǒng)是人工智能系統(tǒng)中常用的一種程序構(gòu)造，是一種知識表示系統(tǒng)。通常由以下三部分組成：綜合數(shù)據(jù)庫產(chǎn)生式規(guī)那么集控制系統(tǒng)12/25/20233綜合數(shù)據(jù)庫：存放問題的形狀描畫的數(shù)據(jù)構(gòu)造。Note:綜合數(shù)據(jù)庫不是常規(guī)意義的數(shù)據(jù)庫，是一種數(shù)據(jù)構(gòu)造。普通數(shù)據(jù)庫所存數(shù)據(jù)的構(gòu)造很簡單，通常只需數(shù)值與字符串；綜合數(shù)據(jù)庫的數(shù)據(jù)可以很復(fù)雜，其中形狀描畫可以為常規(guī)的各種數(shù)據(jù)構(gòu)造，如表、數(shù)組、字符串、集合、矩陣、樹、圖等等。綜合數(shù)據(jù)庫是動態(tài)變化的。一、產(chǎn)生式系統(tǒng)的定義12/25/20234產(chǎn)生式規(guī)那么方式：IF前提條件THEN操作當(dāng)規(guī)那么的前提條件被某一形狀描畫滿足時，就對該形狀施行規(guī)那么所指出的操作。一、產(chǎn)生式系統(tǒng)的定義12/25/20235控制系統(tǒng)：〔1〕選擇規(guī)那么：對同一個形狀的多個可用規(guī)那么排序?！?〕檢驗(yàn)形狀描畫能否滿足終止條件。假設(shè)滿足終止條件，那么終止產(chǎn)生式系統(tǒng)的運(yùn)轉(zhuǎn)，并用運(yùn)用過的規(guī)那么序列構(gòu)造出問題的解。一、產(chǎn)生式系統(tǒng)的定義12/25/20236二、產(chǎn)生式系統(tǒng)的例八數(shù)碼難題由8個標(biāo)有1－8的棋子和一個3×3的棋盤組成。把8個棋子放在棋盤里，構(gòu)成一個初始形狀，然后挪動棋子，想方法到達(dá)規(guī)定的目的形狀。在挪動棋子時，只能把棋子移進(jìn)相鄰的空格中。圖2.1八數(shù)碼難題的初始形狀與目的形狀283164751238476512/25/20237八數(shù)碼難題的產(chǎn)生式系統(tǒng)表示綜合數(shù)據(jù)庫：以形狀為節(jié)點(diǎn)的有向圖。形狀描畫：3×3矩陣產(chǎn)生式規(guī)那么：IF<空格不在最左邊>Then<左移空格>；IF<空格不在最上邊>Then<上移空格>；IF<空格不在最右邊>Then<右移空格>；IF<空格不在最下邊>Then<下移空格>?？刂葡到y(tǒng)：選擇規(guī)那么:按左、上、右、下的順序挪動空格。終止條件：匹配勝利。12/25/20238三、產(chǎn)生式系統(tǒng)的根本過程ProcedurePRODUCTIONDATA←初始形狀描畫untilDATA滿足終止條件，do：begin在規(guī)那么集合中，選出一條可用于DATA的規(guī)那么RDATA←把R運(yùn)用于DATA所得的結(jié)果End12/25/20239步驟4是不確定的，只需求選出一條可用的規(guī)那么R，至于這條規(guī)那么如何選取，卻沒有詳細(xì)闡明。選取規(guī)那么所根據(jù)的原那么稱為控制戰(zhàn)略。多數(shù)人工智能系統(tǒng)控制戰(zhàn)略的信息并缺乏以在第4步選出最合用的規(guī)那么，因此，控制戰(zhàn)略便成了一個搜索過程。高效的系統(tǒng)需求被求解問題足夠的知識，以便在步驟4選出一條最合用的規(guī)那么。第三章，第四章三、產(chǎn)生式系統(tǒng)的根本過程12/25/202310產(chǎn)生式系統(tǒng)的特點(diǎn)一、模塊性強(qiáng)。綜合數(shù)據(jù)庫、規(guī)那么集和控制系統(tǒng)相對獨(dú)立，程序的修正更加容易。二、各產(chǎn)生式規(guī)那么相互獨(dú)立，不能相互調(diào)用，添加一些或刪去一些產(chǎn)生式規(guī)那么都非常方便。三、產(chǎn)生式規(guī)那么的方式與人們推理所用的邏輯方式非常接近，人們具有的知識轉(zhuǎn)換成產(chǎn)生式規(guī)那么很容易，產(chǎn)生式規(guī)那么也容易被人們讀懂。DENDRAL和MYCIN都采用了產(chǎn)生式系統(tǒng)的構(gòu)造。12/25/2023112.2控制戰(zhàn)略產(chǎn)生式系統(tǒng)的控制戰(zhàn)略分為兩類：不可撤回的控制戰(zhàn)略試探性控制戰(zhàn)略：回溯方式和圖搜索方式12/25/202312一、不可撤回的控制戰(zhàn)略〔瞎子爬山法〕根本思想采用不可撤回控制方式的解題過程類似于盲人爬山過程，是利用關(guān)于每一個形狀的部分知識構(gòu)造全局性解的過程。在盲人爬山過程中，無論爬到哪一點(diǎn)，他總沿著坡度最陡的方向向上爬，這是部分性的知識，雖然他事先對爬山道路并不了解，但只需按照這個原那么向上爬，就一定能爬到某一山頂，于是確定了一條從山腳到山頂?shù)呐郎降缆罚部梢哉f構(gòu)造出一個具有某種意義下全局性的解。12/25/202313一、不可撤回的控制戰(zhàn)略爬山函數(shù)：定義在整個綜合數(shù)據(jù)庫上的實(shí)數(shù)值函數(shù)，目的形狀有最大的函數(shù)值。目標(biāo)：爬到山頂?？刂茟?zhàn)略：運(yùn)用爬山函數(shù)選一規(guī)那么，使得所選下一形狀的爬山函數(shù)值不減少且最大〔有兩個一樣的最大值時任選一個；假設(shè)無這樣的規(guī)那么，那么終止爬山過程〕。12/25/202314設(shè)爬山函數(shù)CF(S)：不在目的位的數(shù)碼個數(shù)的負(fù)值。初始形狀S0目的形狀SgCF(S0)＝-4CF(Sg)＝0形狀描畫S：3階方陣4條產(chǎn)生式規(guī)那么運(yùn)用順序：空格左、上、右、下移。2831647512384765例：八數(shù)碼難題，不可撤回式控制12/25/202315控制戰(zhàn)略：處于任一形狀S，系統(tǒng)根據(jù)爬山函數(shù)選擇一條規(guī)那么使得這條規(guī)那么作用于S時，獲得的下一形狀爬山函數(shù)不減少且最大〔亦即間隔目的形狀最少〕。例：八數(shù)碼難題，不可撤回式控制12/25/202316

283164752831476523184765231847651238476512384765例：八數(shù)碼難題不可撤回式控制-4-3-3-1-2012/25/202317不可撤回控制戰(zhàn)略的優(yōu)點(diǎn)1.只記錄當(dāng)前一個節(jié)點(diǎn)，空間復(fù)雜性很低。2.假設(shè)能找到解，那么速度很快。12/25/202318不可撤回控制戰(zhàn)略的局限性多數(shù)情況下找不到解。緣由：(a)爬山函數(shù)有多個部分極大值例如：目的0初始-2(b)爬山函數(shù)具有“平頂值〞處理方法：設(shè)計(jì)更好的爬山函數(shù)；選多余規(guī)那么123748651257486312/25/202319二、回溯控制戰(zhàn)略回溯方式是一種試探性的控制戰(zhàn)略?！差愃粕疃葍?yōu)先〕根本思想控制系統(tǒng)先選用一條規(guī)那么，假設(shè)發(fā)現(xiàn)這條規(guī)那么的選用不能導(dǎo)致產(chǎn)生解，那么系統(tǒng)“忘掉〞選用規(guī)那么所涉及的步驟和產(chǎn)生的形狀，然后選用另外一條規(guī)那么，重新進(jìn)展試探。

12/25/202320回溯方法特點(diǎn)1.只存儲初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的途徑，占用空間較小。2.總的時間復(fù)雜性無法定論:最好情況復(fù)雜性很低：當(dāng)控制系統(tǒng)掌握較多的有關(guān)解的知識時，那么回溯次數(shù)大為減少，效率高。最壞情況復(fù)雜性很高：當(dāng)控制系一致點(diǎn)也沒掌握有關(guān)解的知識時，那么規(guī)那么選取是恣意的，回溯次數(shù)高，效率低。為了防止進(jìn)入無限的境地，設(shè)置回溯深度限制強(qiáng)行回溯，問題：太深：效率低；太淺：能夠找不到解。3.當(dāng)深度限制可變時，通常能找到解，是實(shí)踐用得多、運(yùn)用最廣的一種搜索戰(zhàn)略。

12/25/202321四條規(guī)那么運(yùn)用順序：左、上、右、下〔可參與啟發(fā)式信息，如運(yùn)用爬山函數(shù)安排規(guī)那么的順序〕

深度：6

控制戰(zhàn)略：回溯式

回溯條件：

⑴產(chǎn)生了一個上溯到初始形狀的途徑上出現(xiàn)過的形狀時〔產(chǎn)生了祖先節(jié)點(diǎn)〕。

⑵無可用的規(guī)那么。

⑶達(dá)深度未得解。2831647512384765八數(shù)碼難題的初始形狀與目的形狀例：八數(shù)碼難題回溯式12/25/20232228316475832641758326417528316475832641758342617583264175863241752836417583264175863241758326417583264175八數(shù)碼問題回溯控制83264175

〔1〕〔5〕〔6〕〔5〕〔2〕〔6〕〔7〕〔6〕

〔3〕〔7〕〔7〕

〔4〕〔5〕

〔6〕12/25/202323三、圖搜索控制戰(zhàn)略根本思想：從初始形狀開場，運(yùn)用全部可用規(guī)那么序列。對一切的下一步形狀每一個再用全部可用的規(guī)那么，直到目的形狀為止?！差愃茝V度優(yōu)先搜索戰(zhàn)略〕搜索樹：記錄規(guī)那么的運(yùn)用和所產(chǎn)生的形狀的樹構(gòu)造。樹根：初始形狀有向?。阂?guī)那么的運(yùn)用除根以外的其它各節(jié)點(diǎn)：規(guī)那么運(yùn)用的結(jié)果圖搜索控制方式不斷地?cái)U(kuò)展搜索樹，直到它包括了滿足終止條件的節(jié)點(diǎn)為止。12/25/202324圖搜索控制戰(zhàn)略的特點(diǎn)1.不再選擇規(guī)那么，而是運(yùn)用一切可用的規(guī)那么，下一步選擇節(jié)點(diǎn)來擴(kuò)展。2.存儲一切產(chǎn)生的節(jié)點(diǎn)，占用空間大。3.有解一定能找到〔相當(dāng)于窮舉〕。4.平均時間復(fù)雜性高，系統(tǒng)效率低。12/25/202325

例：八數(shù)碼難題圖搜索式2831647512384765八數(shù)碼難題的初始形狀與目的形狀書中圖：按照深度小的排在前面、優(yōu)先選擇左節(jié)點(diǎn)。12/25/202326四、產(chǎn)生式系統(tǒng)的任務(wù)方式1.正向產(chǎn)生式系統(tǒng)〔數(shù)據(jù)驅(qū)動控制〕：綜合數(shù)據(jù)庫：用形狀描畫產(chǎn)生式規(guī)那么：F規(guī)那么--形狀產(chǎn)生新形狀從初始形狀出發(fā)，不斷地運(yùn)用F規(guī)那么，直到產(chǎn)生目的形狀為止。適用條件：初始節(jié)點(diǎn)數(shù)≤目的節(jié)點(diǎn)數(shù)12/25/2023272.反〔逆〕向產(chǎn)生式系統(tǒng)〔目的驅(qū)動控制〕：綜合數(shù)據(jù)庫：用目的描畫產(chǎn)生式規(guī)那么：B規(guī)那么目的產(chǎn)生子目的從目的形狀出發(fā)，利用反向的產(chǎn)生式規(guī)那么〔B規(guī)那么〕不斷地產(chǎn)生子目的，直到產(chǎn)生出與初始形狀一樣的子目的為止。適用條件：初始節(jié)點(diǎn)數(shù)≥目的節(jié)點(diǎn)數(shù)12/25/2023283.雙向產(chǎn)生式系統(tǒng)：正向產(chǎn)生式系統(tǒng)和反向產(chǎn)生式系統(tǒng)結(jié)合.綜合數(shù)據(jù)庫：既有初始形狀描畫，又有目的形狀描畫。產(chǎn)生式規(guī)那么集：既有F規(guī)那么，又有B規(guī)那么。正向產(chǎn)生式規(guī)那么用在初始方向的形狀描畫上，反向產(chǎn)生式規(guī)那么用在目的描畫上?？刂葡到y(tǒng):判別選F規(guī)那么還是B規(guī)那么；判別曾經(jīng)產(chǎn)生的形狀和目的能否能以某種方式匹配，從而滿足終了條件。終了條件：中間集合時的形狀。適用條件：初始節(jié)點(diǎn)數(shù)與目的節(jié)點(diǎn)數(shù)都很多。特點(diǎn)：效率高；復(fù)雜。12/25/2023292.3特殊的產(chǎn)生式系統(tǒng)一、可交換產(chǎn)生式系統(tǒng)在某些產(chǎn)生式系統(tǒng)中。規(guī)那么運(yùn)用的次序?qū)Ξa(chǎn)生的形狀無影響，即從初始形狀到目的形狀不依賴規(guī)那么次序，因此可運(yùn)用不可撤回式控制戰(zhàn)略，從而提高了產(chǎn)生式系統(tǒng)的效率，這類產(chǎn)生式系統(tǒng)就是可交換的產(chǎn)生式系統(tǒng)。例：基于歸結(jié)方法的產(chǎn)生式系統(tǒng)12/25/202330一個產(chǎn)生式系統(tǒng)稱為可交換的，假設(shè)對恣意形狀描畫D具有如下性質(zhì)：(a)設(shè)RD是可運(yùn)用于D的規(guī)那么集，任取r∈RD，r作用于D得D’，設(shè)為D’=r(D)，那么r對D’可用(即：設(shè)D’的可用規(guī)那么集為RD’，那么r∈RD’，即RDRD’)；〔每一條對D可運(yùn)用的規(guī)那么，對于對D運(yùn)用一條可運(yùn)用的規(guī)那么后所產(chǎn)生的形狀描畫仍是可運(yùn)用的〕〔可運(yùn)用性〕可交換產(chǎn)生式系統(tǒng)定義12/25/202331(b)設(shè)D滿足目的條件，D的可用規(guī)那么集為RD，任取r∈RD，用r作用到D產(chǎn)生形狀D’，D’滿足目的條件。〔假設(shè)D滿足目的條件，那么對D運(yùn)用任何一條可運(yùn)用的規(guī)那么所產(chǎn)生的形狀描畫也滿足目的條件〕〔可滿足性〕。12/25/202332〔c〕設(shè)D的可用規(guī)那么集為RD，任取r1,r2,…,rn∈RD，根據(jù)〔a〕將r1,r2,…,rn依次作用到D及產(chǎn)生的形狀上，得形狀Dn；設(shè)r1’,r2’,…,rn’是r1,r2,…,rn的恣意一個陳列，用r1’,r2’,…,rn’依次作用到D及產(chǎn)生的形狀上，得形狀Dn’，那么Dn’=Dn〔對D運(yùn)用一個由可運(yùn)用于D的規(guī)那么所構(gòu)成的規(guī)那么序列所產(chǎn)生的形狀描畫不因序列的次序不同而改動〕(無次序性〕。12/25/202333R1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交換的產(chǎn)生式系統(tǒng)例R2R3R2R112/25/202334可交換產(chǎn)生式系統(tǒng)優(yōu)點(diǎn)：從初始形狀到目的形狀不依賴規(guī)那么次序，不用探查等價(jià)途徑，可以運(yùn)用不可撤回戰(zhàn)略。Note：產(chǎn)生式系統(tǒng)的可交換性并不意味著整個規(guī)那么序列的次序可以改動。只是最初作用于給定形狀的那些規(guī)那么運(yùn)用起來與次序無關(guān)。12/25/202335設(shè)產(chǎn)生式系統(tǒng)P：綜合數(shù)據(jù)庫，一組規(guī)那么，圖搜索戰(zhàn)略造另一可交換的產(chǎn)生式系轉(zhuǎn)換P’如下：綜合數(shù)據(jù)庫：初始形狀：P的整個搜索樹目的形狀：只剩解路轉(zhuǎn)換可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：12/25/202336轉(zhuǎn)換可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：規(guī)那么Ri：假設(shè)綜合數(shù)據(jù)庫中第i層節(jié)點(diǎn)n不是解路P上的點(diǎn)，那么從綜合數(shù)據(jù)庫中刪除節(jié)點(diǎn)n?？刂茟?zhàn)略：不可撤回式將P轉(zhuǎn)換為P’，P’是可交換的產(chǎn)生式系統(tǒng)

綜合數(shù)據(jù)庫變復(fù)雜；規(guī)那么數(shù)目少，但操作復(fù)雜〔如何判別n不是解路P上的點(diǎn)〕；控制戰(zhàn)略簡單。12/25/202337二、可分解的產(chǎn)生式系統(tǒng)可交換產(chǎn)生式系統(tǒng)可以防止搜索多余途徑，可以運(yùn)用不可撤回戰(zhàn)略。防止搜索多余途徑的另一種方法是可分解的產(chǎn)生式系統(tǒng)。12/25/202338可分解的產(chǎn)生式系統(tǒng)例:字符串重寫綜合數(shù)據(jù)庫：串節(jié)點(diǎn)的有向圖形狀：字符串〔或用表〕初始形狀：(C,B,Z)產(chǎn)生式規(guī)那么：R1:IF<(*1,C,*2)>THEN<(*1,D,L,*2)>〔重寫規(guī)那么〕R2:IF<(*1,C,*2)>THEN<(*1,B,M,*2)>R3:IF<(*1,B,*2)>THEN<(*1,M,M,*2)>R4:IF<(*1,Z,*2)>THEN<(*1,B,B,M,*2)>控制系統(tǒng)：選擇規(guī)那么：用圖搜索控制戰(zhàn)略終止條件：形狀描畫僅有M組成的符號串。

12/25/202339重寫問題的解序列〔不完好〕R3R3R3R3R3R4R4R3R3R3R2R1R4〔C，B，Z〕(M,M,M,B,Z)(M,M,M,M,M,Z)(M,M,M,M,M,B,B,M)(M,M,M,M,M,M,M,B,M)(M,M,M,M,M,M,M,M,M,M)(C,B,B,B,M)(B,M,B,B,B,M)(M,M,M,B,B,B,M)(D,L,B,Z)(D,L,M,M,Z)(D,L,M,M,B,B,M)(D,L,M,M,M,M,B,M)(D,L,M,M,M,M,M,M,M)R2R3(B,M,B,Z)12/25/202340Note:按照圖搜索控制方式在產(chǎn)生終止形狀時能夠會探求許多完全等價(jià)的途徑,導(dǎo)致系統(tǒng)的低效。從失敗途徑上浪費(fèi)很多任務(wù)。節(jié)點(diǎn)的內(nèi)容之間存在著大量的符號冗余。12/25/202341察看：該產(chǎn)生式系統(tǒng)的初始形狀可以分解成C,B和Z，然后把產(chǎn)生式規(guī)那么分解使得可運(yùn)用于這些組成部分：R1:(C)→(D,L)R2:(C)→(B,M)R3:(B)→(M,M)R4:(Z)→(B,B,M)運(yùn)用規(guī)那么后所得的結(jié)果形狀又可以進(jìn)一步分裂，這樣不斷地分解，不斷地運(yùn)用規(guī)那么，直到所產(chǎn)生的形狀是M字符為止，即終止條件分解為一個M字符作成的形狀。12/25/202342重寫問題的與/或樹(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLBM(M,M)MMMMBMB(M,M)(M,M)MMMMR1R2R3R4R3R3R312/25/202343定義可以把產(chǎn)生式系統(tǒng)綜合數(shù)據(jù)庫的形狀描畫分解為假設(shè)干組成部分，產(chǎn)生式規(guī)那么可以分別用在各組成部分上，并且整個系統(tǒng)的終止條件可以用在各組成部分的終止條件表示出來的產(chǎn)生式系統(tǒng)，稱為可分解的產(chǎn)生式系統(tǒng)。可分