人工智能第5章產(chǎn)生式系統(tǒng)

人工智能第5章產(chǎn)生式系統(tǒng)第一頁，共25頁。第5章產(chǎn)生式系統(tǒng)

5.1產(chǎn)生式規(guī)則5.2產(chǎn)生式系統(tǒng)5.3產(chǎn)生式系統(tǒng)與圖搜索5.4產(chǎn)生式系統(tǒng)的應用5.5產(chǎn)生式系統(tǒng)的程序實現(xiàn)第二頁，共25頁。5.1產(chǎn)生式規(guī)則5.1.1產(chǎn)生式規(guī)則產(chǎn)生式(Production)一詞，首先是由美國數(shù)學家波斯特（E.Post）提出來的。波斯特根據(jù)替換規(guī)則提出了一種稱為波斯特機的計算模型，模型中的每一條規(guī)則當時被稱為一個產(chǎn)生式。后來，這一術語幾經(jīng)修改擴充，被用到許多領域。例如，形式語言中的文法規(guī)則就稱為產(chǎn)生式。產(chǎn)生式也稱為產(chǎn)生式規(guī)則，或簡稱規(guī)則。第三頁，共25頁。

產(chǎn)生式的一般形式為前件→后件其中，前件就是前提，后件是結論或動作，前件和后件可以是由邏輯運算符AND、OR、NOT組成的表達式。產(chǎn)生式規(guī)則的語義是:如果前提滿足，則可得結論或者執(zhí)行相應的動作,即后件由前件來觸發(fā)。所以，前件是規(guī)則的執(zhí)行條件，后件是規(guī)則體。第四頁，共25頁。

例如，產(chǎn)生式規(guī)則：

(1)如果銀行存款利率下調，那么股票價格上漲。

(2)如果爐溫超過上限，則立即關閉風門。

(3)如果鍵盤突然失靈，且屏幕上出現(xiàn)怪字符，則是病毒發(fā)作。

(4)如果膠卷感光度為200，光線條件為晴天，目標距離不超過5米，則快門速度取250，光圈大小取f16。第五頁，共25頁。5.1.2基于產(chǎn)生式的推理模式由產(chǎn)生式的涵義可知，利用產(chǎn)生式規(guī)則可以實現(xiàn)有前提條件的指令性操作，也可以實現(xiàn)邏輯推理。實現(xiàn)操作的方法是當測試到一條規(guī)則的前提條件滿足時，就執(zhí)行其后部的動作。這稱為規(guī)則被觸發(fā)或點燃。利用產(chǎn)生式規(guī)則實現(xiàn)邏輯推理的方法是當有事實能與某規(guī)則的前提匹配（即規(guī)則的前提成立）時，就得到該規(guī)則后部的結論（即結論也成立）。第六頁，共25頁。

實際上，這種基于產(chǎn)生式規(guī)則的邏輯推理模式，就是邏輯上所說的假言推理（對常量規(guī)則而言）和三段論推理（對變量規(guī)則而言），即：

A→BAB

這里的大前提就是一個產(chǎn)生式規(guī)則，小前提就是證據(jù)事實。第七頁，共25頁。

5.2產(chǎn)生式系統(tǒng)

5.2.1產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)由三部分組成：產(chǎn)生式規(guī)則庫、推理機和動態(tài)數(shù)據(jù)庫，其結構如圖所示。產(chǎn)生式規(guī)則庫亦稱產(chǎn)生式規(guī)則集，由領域規(guī)則組成，在機器中以某種動態(tài)數(shù)據(jù)結構進行組織。推理機亦稱控制執(zhí)行機構，它是一個程序模塊，負責產(chǎn)生式規(guī)則的前提條件測試或匹配，規(guī)則的調度與選取，規(guī)則體的解釋和執(zhí)行。即推理機實施推理，并對推理進行控制，它也就是規(guī)則的解釋程序。產(chǎn)品式規(guī)則庫推理機動態(tài)數(shù)據(jù)庫第八頁，共25頁。5.2.2產(chǎn)生式系統(tǒng)的運行過程產(chǎn)生式系統(tǒng)運行時，除了需要規(guī)則庫以外，還需要有初始事實(或數(shù)據(jù))和目標條件。

目標條件是系統(tǒng)正常結束的條件，也是系統(tǒng)的求解目標。產(chǎn)生式系統(tǒng)啟動后，推理機就開始推理，按所給的目標進行問題求解。推理機的一次推理過程，可如圖所示。一個實際的產(chǎn)生式系統(tǒng)，其目標條件一般不會只經(jīng)一步推理就可滿足，往往要經(jīng)過多步推理才能滿足或者證明問題無解。從規(guī)則庫中取一個條規(guī)則，將其前提同當前動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)進行模式匹配匹配成功否把該規(guī)則的結論放入當前動態(tài)數(shù)據(jù)庫：或執(zhí)行規(guī)則所規(guī)定的動作NY第九頁，共25頁。5.2.3控制策略與常用算法產(chǎn)生式系統(tǒng)的推理可分為正向推理和反向推理兩種基本方式。1.正向推理正向推理算法一：步1將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；步2用動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)，匹配/測試目標條件，若目標條件滿足，則推理成功，結束。步3用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)，將匹配成功的規(guī)則組成待用規(guī)則集；步4若待用規(guī)則集為空，則運行失敗，退出。步5將待用規(guī)則集中各規(guī)則的結論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，轉步2；可以看出:隨著推理的進行，動態(tài)數(shù)據(jù)庫的內容或者狀態(tài)在不斷變化。動態(tài)數(shù)據(jù)庫推理第十頁，共25頁。

例5.1動物分類問題的產(chǎn)生式系統(tǒng)描述及其求解。設由動物識別規(guī)則組成規(guī)則庫，推理機采用上述正向推理算法。該產(chǎn)生式系統(tǒng)就是一個小型動物分類知識庫系統(tǒng)。規(guī)則：

r1：若某動物有奶，則它是哺乳動物。

r2：若某動物有毛發(fā)，則它是哺乳動物。

r3：若某動物有羽毛，則它是鳥。

r4：若某動物會飛且生蛋，則它是鳥。

r5：若某動物是哺乳動物且有爪且有犬齒且目盯前方，則它是食肉動物。r6：若某動物是哺乳動物且吃肉，則它是食肉動物。r7：若某動物是哺乳動物且有蹄，則它是有蹄動物。r8：若某動物是有蹄動物且反芻食物，則它是偶蹄動物。r9：若某動物是食肉動物且黃褐色且有黑色條紋，則它是老虎。r10：若某動物是食肉動物且黃褐色且有黑色斑點，則它是金錢豹。r11：若某動物是有蹄動物且長腿且長脖子且黃褐色且有暗斑點，則它是長頸鹿。r12：若某動物是有蹄動物且白色且有黑色條紋，則它是斑馬。r13：若某動物是鳥且不會飛且長腿且長脖子且黑白色，則它是駝鳥。r14：若某動物是鳥且不會飛且會游泳且黑白色，則它是企鵝。r15：若某動物是鳥且善飛且不怕風浪，則它是海燕。第十一頁，共25頁。再給出初始事實：f1：某動物有毛發(fā)。f2：吃肉。f3：黃褐色。f4：有黑色條紋。目標條件：該動物是什么？易見，該系統(tǒng)的運行結果為：該動物是老虎。其推理樹如圖所示。動物分類正向推理樹老虎食肉動物哺乳動物有毛發(fā)吃肉黃褐色有黑色條紋第十二頁，共25頁。2.反向推理步1將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫，將目標條件置入目標鏈；步2若目標鏈為空，則推理成功，結束。步3取出目標鏈中第一個目標，用動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)同其匹配，若匹配成功，轉步2；步4用規(guī)則集中的各規(guī)則的結論同該目標匹配，若匹配成功，則將第一個匹配成功且未用過的規(guī)則的前提作為新的目標，并取代原來的父目標而加入目標鏈，轉步3；步5若該目標是初始目標，則推理失敗，退出。步6將該目標的父目標移回目標鏈，取代該目標及其兄弟目標，轉步3；可以看出，上述反向推理算法的推理過程也是一個圖搜索過程，而且一般是一個與或樹搜索。第十三頁，共25頁。

例5.2對于上例的產(chǎn)生式系統(tǒng)，改為反向推理算法，則得到圖所示的推理樹。圖5—5動物分類反向推理樹第十四頁，共25頁。

可以看出，與正向推理不同，這次的推理樹是從上而下擴展而成的，而且推理過程中還發(fā)生過回溯。反向推理也稱為后向推理、反向鏈、目標驅動的推理等。從上面的兩個算法可以看出，正向推理是自底向上的綜合過程，而反向推理則是自頂向下的分析過程。除了正向推理和反向推理外，產(chǎn)生式系統(tǒng)還可進行雙向推理。雙向推理就是同時從初始數(shù)據(jù)和目標條件出發(fā)進行推理，如果在中間某處相遇，則推理搜索成功。第十五頁，共25頁。3.沖突消解策略上述正向推理算法中，對所有匹配成功的規(guī)則都同時觸發(fā)啟用。所以，它實現(xiàn)的搜索是窮舉式的樹式盲目搜索。下面給出一個正向推理的啟發(fā)式線式搜索:。正向推理算法二：步1將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；步2用動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)，匹配/測試目標條件，若目標條件滿足，則推理成功，結束。步3用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)，將匹配成功的規(guī)則組成待用規(guī)則集；步4若待用規(guī)則集為空，則運行失敗，退出。步5用某種策略，從待用規(guī)則集中選取一條規(guī)則，將其結論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，撤消待用規(guī)則集，轉步2；可以看出，該算法與前面的算法僅在步5有所差別。第十六頁，共25頁。5.3產(chǎn)生式系統(tǒng)與圖搜索

分析前面給出的兩個正向推理算法，可以看出，它們只能用于解決邏輯推理問題:(1)記錄動態(tài)數(shù)據(jù)庫狀態(tài)變化的歷史，這就需要增設一個CLOSED表。

(2)若要回溯，則還需保存與每個動態(tài)數(shù)據(jù)庫狀態(tài)對應的可用規(guī)則集。因為動態(tài)數(shù)據(jù)庫狀態(tài)與可用規(guī)則集實際是一一對應的。

(3)要進行樹式搜索，還需設置一個OPEN表，以進行新生動態(tài)數(shù)據(jù)庫的狀態(tài)保存和當前動態(tài)數(shù)據(jù)庫狀態(tài)的切換。

(4)還要考慮一條規(guī)則是否只允許執(zhí)行一次。若是，則要對已執(zhí)行了的規(guī)則進行標記。第十七頁，共25頁。表5.1產(chǎn)生式系統(tǒng)與圖搜索對比

可以看出，二者實際是一回事。要說差別的話，圖搜索技術描述了問題求解的方法，而產(chǎn)生式系統(tǒng)則給出了實施這種方法的一種計算機程序系統(tǒng)的結構模式。這樣，問題求解、圖搜索和產(chǎn)生式系統(tǒng)三者的關系是：問題求解是目的，圖搜索是方法，產(chǎn)生式系統(tǒng)是形式。第十八頁，共25頁。5.4產(chǎn)生式系統(tǒng)的應用

由上述產(chǎn)生式系統(tǒng)與圖搜索的關系可見，產(chǎn)生式系統(tǒng)完全可以作為問題求解的表示模型和求解模型，而且可作為人工智能問題求解系統(tǒng)的通用模型。用產(chǎn)生式系統(tǒng)也可實現(xiàn)基于謂詞邏輯的演繹推理和證明。由于產(chǎn)生式系統(tǒng)既可用于操作性問題求解，也可用于推理性問題求解。因此，產(chǎn)生式系統(tǒng)也是專家系統(tǒng)的基本結構形式。用它既可實現(xiàn)規(guī)劃型專家系統(tǒng)，也可實現(xiàn)結論型專家系統(tǒng)。產(chǎn)生式系統(tǒng)在人工智能技術中占有重要地位。第十九頁，共25頁。5.5產(chǎn)生式系統(tǒng)的程序實現(xiàn)

5.5.1產(chǎn)生式規(guī)則的程序語言實現(xiàn)討論產(chǎn)生式規(guī)則的形式結構:

產(chǎn)生式規(guī)則的前提和結論部分可以是一個復雜的邏輯表達式，為使表達簡單規(guī)范，便于推理，往往把規(guī)則的前提部分作成形如:

條件1AND條件2AND…AND條件n或者條件1OR條件2OR…OR條件m

把規(guī)則結論部分作成形如斷言1/動作1AND斷言2/動作2AND…AND斷言k/動作k

或者斷言1/動作1OR斷言2/動作2OR…OR斷言k/動作k

或者進一步簡化成:斷言/動作(即僅有一項)

由于含OR關系的規(guī)則也可以分解為若干不含OR關系的規(guī)則，所以，產(chǎn)生式規(guī)則也可僅取下面的一種形式：條件1AND條件2AND…AND條件n→斷言/動作第二十頁，共25頁。前例：DOMAINSname=string.PREDICATESanimal_is(name).it_is(name).it_is1(name).fact(name).GOALanimal_is(Y),write(“Y=”,Y).CLAUSESfact(“有爪”).fact(“吃肉”).fact(“有奶”).fact(“黃褐色”).fact(“有黑色斑點”).it_is(“哺乳動物”):-fact(“有奶”).it_is(“哺乳動物”):-fact(“有毛發(fā)”).it_is1(“食肉動物”):-it_is(“哺乳動物”),fact(“有爪”),fact(“有犬齒”).it_is1(“食肉動物”):-it_is(“哺乳動物”),fact(“吃肉”).it_is1(“有蹄動物”):-it_is(“哺乳動物”),fact(“有蹄”).animal_is(“老虎”):-it_is1(“食肉動物”),fact(“黃褐色”),fact(“有黑色條紋”).animal_is(“金錢豹”):-it_is1(“食肉動物”),fact(“黃褐色”),fact(“有黑色斑點”).animal_is(“長頸鹿”):-it_is1(