5章-產(chǎn)生式系統(tǒng)課件

1、第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)的應(yīng)用5.5 產(chǎn)生式系統(tǒng)的程序?qū)崿F(xiàn)第5章 產(chǎn)生式系統(tǒng) 5.1 產(chǎn)生式規(guī)則5.1 產(chǎn)生式規(guī)則 5.1.1 產(chǎn)生式規(guī)則 產(chǎn)生式(Production)一詞，首先是由美國數(shù)學(xué)家波斯特（E.Post）提出來的。波斯特根據(jù)替換規(guī)則提出了一種稱為波斯特機(jī)的計算模型，模型中的每一條規(guī)則當(dāng)時被稱為一個產(chǎn)生式。后來，這一術(shù)語幾經(jīng)修改擴(kuò)充，被用到許多領(lǐng)域。例如，形式語言中的文法規(guī)則就稱為產(chǎn)生式。產(chǎn)生式也稱為產(chǎn)生式規(guī)則，或簡稱規(guī)則。5.1 產(chǎn)生式規(guī)則 5.1.1 產(chǎn)生式規(guī)則 產(chǎn)生式的一般形式為 前件后件 其中，前件

2、就是前提，后件是結(jié)論或動作，前件和后件可以是由邏輯運(yùn)算符AND、OR、NOT組成的表達(dá)式。 產(chǎn)生式規(guī)則的語義是:如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動作,即后件由前件來觸發(fā)。所以，前件是規(guī)則的執(zhí)行條件，后件是規(guī)則體。 產(chǎn)生式的一般形式為 例如，產(chǎn)生式規(guī)則： (1)如果銀行存款利率下調(diào)，那么股票價格上漲。 (2)如果爐溫超過上限，則立即關(guān)閉風(fēng)門。 (3)如果鍵盤突然失靈，且屏幕上出現(xiàn)怪字符，則是病毒發(fā)作。 (4)如果膠卷感光度為200，光線條件為晴天，目標(biāo)距離不超過5米，則快門速度取250，光圈大小取f16。 例如，產(chǎn)生式規(guī)則： 5.1.2 基于產(chǎn)生式的推理模式 由產(chǎn)生式的涵義可知，利用產(chǎn)生式

3、規(guī)則可以實(shí)現(xiàn)有前提條件的指令性操作，也可以實(shí)現(xiàn)邏輯推理。實(shí)現(xiàn)操作的方法是當(dāng)測試到一條規(guī)則的前提條件滿足時，就執(zhí)行其后部的動作。這稱為規(guī)則被觸發(fā)或點(diǎn)燃。利用產(chǎn)生式規(guī)則實(shí)現(xiàn)邏輯推理的方法是當(dāng)有事實(shí)能與某規(guī)則的前提匹配（即規(guī)則的前提成立）時，就得到該規(guī)則后部的結(jié)論（即結(jié)論也成立）。 5.1.2 基于產(chǎn)生式的推理模式 實(shí)際上，這種基于產(chǎn)生式規(guī)則的邏輯推理模式，就是邏輯上所說的假言推理（對常量規(guī)則而言）和三段論推理（對變量規(guī)則而言），即： AB A B 這里的大前提就是一個產(chǎn)生式規(guī)則，小前提就是證據(jù)事實(shí)。 實(shí)際上，這種基于產(chǎn)生式規(guī)則的邏輯推理5.2 產(chǎn)生式系統(tǒng) 5.2.1 產(chǎn)生式系統(tǒng)的組成 產(chǎn)生式系統(tǒng)由

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

5、所給的目標(biāo)進(jìn)行問題求解。 推理機(jī)的一次推理過程，可如圖所示。 一個實(shí)際的產(chǎn)生式系統(tǒng)，其目標(biāo)條件一般不會只經(jīng)一步推理就可滿足，往往要經(jīng)過多步推理才能滿足或者證明問題無解。從規(guī)則庫中取一個條規(guī)則，將其前提同當(dāng)前動態(tài)數(shù)據(jù)庫中的事實(shí)/數(shù)據(jù)進(jìn)行模式匹配匹配成功否把該規(guī)則的結(jié)論放入當(dāng)前動態(tài)數(shù)據(jù)庫：或執(zhí)行規(guī)則所規(guī)定的動作NY 5.2.2 產(chǎn)生式系統(tǒng)的運(yùn)行過程從規(guī)則庫中取一個條規(guī) 5.2.3 控制策略與常用算法 產(chǎn)生式系統(tǒng)的推理可分為正向推理和反向推理兩種基本方式。 1.正向推理 正向推理算法一： 步1 將初始事實(shí)/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫； 步2 用動態(tài)數(shù)據(jù)庫中的事實(shí)/數(shù)據(jù)，匹配/測試目標(biāo)條件，若目標(biāo)條件滿足，則

6、推理成功，結(jié)束。 步3 用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實(shí)/數(shù)據(jù)，將匹配成功的規(guī)則組成待用規(guī)則集；步4 若待用規(guī)則集為空，則運(yùn)行失敗，退出。步5 將待用規(guī)則集中各規(guī)則的結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，轉(zhuǎn)步2； 可以看出:隨著推理的進(jìn)行，動態(tài)數(shù)據(jù)庫的內(nèi)容或者狀態(tài)在不斷變化。動態(tài)數(shù)據(jù)庫推理 5.2.3 控制策略與常用算法動態(tài)數(shù)據(jù)庫推理 例5.1 動物分類問題的產(chǎn)生式系統(tǒng)描述及其求解。 設(shè)由動物識別規(guī)則組成規(guī)則庫，推理機(jī)采用上述正向推理算法。該產(chǎn)生式系統(tǒng)就是一個小型動物分類知識庫系統(tǒng)。規(guī)則： r1：若某動物有奶，則它是哺乳動物。 r2：若某動物有毛發(fā)，則它是哺乳動物。 r3：若某動物有

7、羽毛，則它是鳥。 r4：若某動物會飛且生蛋，則它是鳥。 r5：若某動物是哺乳動物且有爪且有犬齒且目盯前方，則它是食肉動物。r6：若某動物是哺乳動物且吃肉，則它是食肉動物。r7：若某動物是哺乳動物且有蹄，則它是有蹄動物。r8：若某動物是有蹄動物且反芻食物，則它是偶蹄動物。r9：若某動物是食肉動物且黃褐色且有黑色條紋，則它是老虎。r10：若某動物是食肉動物且黃褐色且有黑色斑點(diǎn)，則它是金錢豹。r11：若某動物是有蹄動物且長腿且長脖子且黃褐色且有暗斑點(diǎn)，則它是長頸鹿。r12：若某動物是有蹄動物且白色且有黑色條紋，則它是斑馬。r13：若某動物是鳥且不會飛且長腿且長脖子且黑白色，則它是駝鳥。r14：若某動

8、物是鳥且不會飛且會游泳且黑白色，則它是企鵝。r15：若某動物是鳥且善飛且不怕風(fēng)浪，則它是海燕。 例5.1 動物分類問題的產(chǎn)生式系統(tǒng)描述及其求解。再給出初始事實(shí)：f1：某動物有毛發(fā)。f2：吃肉。f3：黃褐色。f4：有黑色條紋。目標(biāo)條件：該動物是什么？易見，該系統(tǒng)的運(yùn)行結(jié)果為：該動物是老虎。其推理樹如圖所示。動物分類正向推理樹 老虎食肉動物哺乳動物有毛發(fā)吃肉黃褐色有黑色條紋再給出初始事實(shí)：動物分類正向推理樹 老虎食肉動物哺乳動物有毛 2. 反向推理 步1 將初始事實(shí)/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫，將目標(biāo)條件置入目標(biāo)鏈； 步2 若目標(biāo)鏈為空，則推理成功，結(jié)束。 步3 取出目標(biāo)鏈中第一個目標(biāo)，用動態(tài)數(shù)據(jù)庫中的事

9、實(shí)/數(shù)據(jù)同其匹配，若匹配成功，轉(zhuǎn)步2； 步4 用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配成功，則將第一個匹配成功且未用過的規(guī)則的前提作為新的目標(biāo)，并取代原來的父目標(biāo)而加入目標(biāo)鏈，轉(zhuǎn)步3； 步5 若該目標(biāo)是初始目標(biāo)，則推理失敗，退出。 步6 將該目標(biāo)的父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄弟目標(biāo)，轉(zhuǎn)步3； 可以看出，上述反向推理算法的推理過程也是一個圖搜索過程，而且一般是一個與或樹搜索。 2. 反向推理 例5.2 對于上例的產(chǎn)生式系統(tǒng)，改為反向推理算法，則得到圖所示的推理樹。圖55 動物分類反向推理樹 例5.2 對于上例的產(chǎn)生式系統(tǒng)，改為 可以看出，與正向推理不同，這次的推理樹是從上而下擴(kuò)展而成的

10、，而且推理過程中還發(fā)生過回溯。 反向推理也稱為后向推理、反向鏈、目標(biāo)驅(qū)動的推理等。 從上面的兩個算法可以看出，正向推理是自底向上的綜合過程，而反向推理則是自頂向下的分析過程。 除了正向推理和反向推理外，產(chǎn)生式系統(tǒng)還可進(jìn)行雙向推理。雙向推理就是同時從初始數(shù)據(jù)和目標(biāo)條件出發(fā)進(jìn)行推理，如果在中間某處相遇，則推理搜索成功。 可以看出，與正向推理不同，這次的推理 3. 沖突消解策略 上述正向推理算法中，對所有匹配成功的規(guī)則都同時觸發(fā)啟用。所以，它實(shí)現(xiàn)的搜索是窮舉式的樹式盲目搜索。下面給出一個正向推理的啟發(fā)式線式搜索:。 正向推理算法二： 步1 將初始事實(shí)/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫； 步2 用動態(tài)數(shù)據(jù)庫中的事實(shí)

11、/數(shù)據(jù)，匹配/測試目標(biāo)條件，若目標(biāo)條件滿足，則推理成功，結(jié)束。 步3 用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實(shí)/數(shù)據(jù)，將匹配成功的規(guī)則組成待用規(guī)則集； 步4 若待用規(guī)則集為空，則運(yùn)行失敗，退出。 步5 用某種策略，從待用規(guī)則集中選取一條規(guī)則，將其結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，撤消待用規(guī)則集，轉(zhuǎn)步2； 可以看出，該算法與前面的算法僅在步5有所差別。 3. 沖突消解策略5.3 產(chǎn)生式系統(tǒng)與圖搜索 分析前面給出的兩個正向推理算法，可以看出，它們只能用于解決邏輯推理問題: (1)記錄動態(tài)數(shù)據(jù)庫狀態(tài)變化的歷史，這就需要增設(shè)一個CLOSED表。 (2)若要回溯，則還需保存與每個動態(tài)數(shù)據(jù)庫狀態(tài)對應(yīng)

12、的可用規(guī)則集。因?yàn)閯討B(tài)數(shù)據(jù)庫狀態(tài)與可用規(guī)則集實(shí)際是一一對應(yīng)的。 (3)要進(jìn)行樹式搜索，還需設(shè)置一個OPEN表，以進(jìn)行新生動態(tài)數(shù)據(jù)庫的狀態(tài)保存和當(dāng)前動態(tài)數(shù)據(jù)庫狀態(tài)的切換。 (4)還要考慮一條規(guī)則是否只允許執(zhí)行一次。若是，則要對已執(zhí)行了的規(guī)則進(jìn)行標(biāo)記。5.3 產(chǎn)生式系統(tǒng)與圖搜索 分析前面表5.1 產(chǎn)生式系統(tǒng)與圖搜索對比 可以看出，二者實(shí)際是一回事。要說差別的話，圖搜索技術(shù)描述了問題求解的方法，而產(chǎn)生式系統(tǒng)則給出了實(shí)施這種方法的一種計算機(jī)程序系統(tǒng)的結(jié)構(gòu)模式。這樣，問題求解、圖搜索和產(chǎn)生式系統(tǒng)三者的關(guān)系是：問題求解是目的，圖搜索是方法，產(chǎn)生式系統(tǒng)是形式。表5.1 產(chǎn)生式系統(tǒng)與圖搜索對比 5.4 產(chǎn)生式

13、系統(tǒng)的應(yīng)用 由上述產(chǎn)生式系統(tǒng)與圖搜索的關(guān)系可見，產(chǎn)生式系統(tǒng)完全可以作為問題求解的表示模型和求解模型，而且可作為人工智能問題求解系統(tǒng)的通用模型。用產(chǎn)生式系統(tǒng)也可實(shí)現(xiàn)基于謂詞邏輯的演繹推理和證明。 由于產(chǎn)生式系統(tǒng)既可用于操作性問題求解，也可用于推理性問題求解。因此，產(chǎn)生式系統(tǒng)也是專家系統(tǒng)的基本結(jié)構(gòu)形式。用它既可實(shí)現(xiàn)規(guī)劃型專家系統(tǒng)，也可實(shí)現(xiàn)結(jié)論型專家系統(tǒng)。 產(chǎn)生式系統(tǒng)在人工智能技術(shù)中占有重要地位。5.4 產(chǎn)生式系統(tǒng)的應(yīng)用 由上述產(chǎn)生式系統(tǒng)與5.5 產(chǎn)生式系統(tǒng)的程序?qū)崿F(xiàn) 5.5.1 產(chǎn)生式規(guī)則的程序語言實(shí)現(xiàn) 討論產(chǎn)生式規(guī)則的形式結(jié)構(gòu): 產(chǎn)生式規(guī)則的前提和結(jié)論部分可以是一個復(fù)雜的邏輯表達(dá)式，為使表達(dá)簡單

14、規(guī)范，便于推理，往往把規(guī)則的前提部分作成形如: 條件1AND條件2ANDAND條件n 或者 條件1OR條件2OROR條件m 把規(guī)則結(jié)論部分作成形如 斷言1/動作1AND斷言2/動作2ANDAND斷言k/動作k 或者 斷言1/動作1OR斷言2/動作2OROR斷言k/動作k 或者進(jìn)一步簡化成: 斷言/動作 ( 即僅有一項(xiàng)) 由于含OR關(guān)系的規(guī)則也可以分解為若干不含OR關(guān)系的規(guī)則，所以，產(chǎn)生式規(guī)則也可僅取下面的一種形式： 條件1AND條件2ANDAND條件n斷言/動作5.5 產(chǎn)生式系統(tǒng)的程序?qū)崿F(xiàn) 5.5.1 產(chǎn)生式前例：DOMAINS name=string.PREDICATES animal_is

15、(name). it_is(name). it_is1(name). fact(name).GOAL animal_is(Y),write(“Y=”,Y).CLAUSES fact(“有爪”). fact(“吃肉”). fact(“有奶”).fact(“黃褐色”).fact(“有黑色斑點(diǎn)”). it_is(“哺乳動物”):-fact(“有奶”). it_is(“哺乳動物”):-fact(“有毛發(fā)”).it_is1(“食肉動物”):-it_is(“哺乳動物”),fact(“有爪”), fact(“有犬齒”).it_is1(“食肉動物”):-it_is(“哺乳動物”),fact(“吃肉”).it_

16、is1(“有蹄動物”):-it_is(“哺乳動物”),fact(“有蹄”).animal_is(“老虎”):- it_is1(“食肉動物”), fact(“黃褐色”),fact(“有黑色條紋”).animal_is(“金錢豹”):- it_is1(“食肉動物”), fact(“黃褐色”),fact(“有黑色斑點(diǎn)”).animal_is(“長頸鹿”):- it_is1(“有蹄動物”), fact(“長腿”),fact(“長脖”), fact(“有暗斑點(diǎn)”).animal_is(“斑馬”):- it_is1(“有蹄動物”), fact(“有黑色條紋”).前例： it_is(“哺乳動物”):-fact(“有奶”) 5.5.2 規(guī)則庫的程序?qū)崿F(xiàn) 規(guī)則庫的程序?qū)崿F(xiàn)分為內(nèi)存和外存兩個方面。在內(nèi)存中規(guī)則庫可用鏈表實(shí)現(xiàn)，在外存則就是以規(guī)則為基本單位的數(shù)據(jù)文件。 若用PROLOG程序，規(guī)則庫就是程序的一部分；對于事實(shí)表示的規(guī)則，則規(guī)則庫在內(nèi)存就是動態(tài)數(shù)據(jù)庫，在外存就是數(shù)據(jù)庫文件。 還需說明的是，對于規(guī)則庫實(shí)際上還需配一個管理程序，即知識庫管理系統(tǒng)，專門負(fù)責(zé)規(guī)則及規(guī)則庫