西電人工智能15確定性推理part8

ArtificialIntelligence(AI)

人工智能主講：戚玉濤Email：qi_yutao@163.com第三章：確定性推理內(nèi)容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結(jié)演繹繹推理5.基于規(guī)則則的演繹繹推理6.產(chǎn)生式系系統(tǒng)基于規(guī)則則的演繹繹推理規(guī)則演繹繹系統(tǒng)規(guī)則正向向演繹系系統(tǒng)規(guī)則逆向向演繹系系統(tǒng)規(guī)則雙向向演繹系系統(tǒng)規(guī)則逆向向演繹系系統(tǒng)規(guī)則逆向向演繹推推理過(guò)程程：規(guī)則逆向向演繹推推理過(guò)程程是從待待證明的的問(wèn)題，，即目標(biāo)標(biāo)公式的的與/或樹(shù)出發(fā)發(fā)，通過(guò)過(guò)逆向地地使用蘊(yùn)蘊(yùn)含式（（B規(guī)則），，對(duì)目標(biāo)標(biāo)公式的的與/或樹(shù)進(jìn)行行變換，，直到得得出包含含已知事事實(shí)的終終止條件件為止。。規(guī)則逆向向演繹系系統(tǒng)目標(biāo)公式式的表示示：與/或形變換換，與/或樹(shù)表示示B規(guī)則的表表示形式式已知事實(shí)實(shí)的表示示形式規(guī)則逆向向演繹推推理過(guò)程程目標(biāo)公式式的與/或形變換換在與/或形逆向向演繹推推理中，，要求目標(biāo)公式式采用與與/或形表示示，其化簡(jiǎn)簡(jiǎn)采用與與正向系系統(tǒng)中對(duì)對(duì)事實(shí)表表達(dá)式處處理的對(duì)偶形式式。轉(zhuǎn)化步驟驟要用存在量詞詞約束變?cè)腟kolem函數(shù)來(lái)替替換由全稱量詞詞約束的相相應(yīng)變?cè)?，消去去全稱量量詞。（隱含著著變量受受存在量量詞的約約束））再消去存在量詞詞，并進(jìn)行行變?cè)獡Q換名，使使主析取取元之間間具有不不同的變變?cè)?。。目?biāo)公式式的與/或形變換換例如，有有如下目目標(biāo)公式式：(?y)(?x)(P(x))→(Q(x))∧?(R(x)∧S(y))))))Skolem化后為?P(f(y)))∨(Q(f(y),y)∧((?R((f(y)))∨?S(y)))變?cè)獡Q名名后為?P(f(z)))∨(Q(f((y),y)∧((?R((f(y))∨∨?S((y)))關(guān)于為何何需用對(duì)對(duì)偶方式式消去量量詞，這這里不作作形式證證明，僅僅通過(guò)與與歸結(jié)反反演方法法作對(duì)比比來(lái)加以以直觀說(shuō)說(shuō)明：在歸結(jié)反反演中，，需將目目標(biāo)公式式取反，，存在量量詞約束束變量就就成為全全稱量詞詞約束變變量。目標(biāo)公式式的與/或樹(shù)表示示目標(biāo)公式式的與/或形也可可用與/或樹(shù)表示示出來(lái)，，其表示示方法與與正向演演繹推理理中事實(shí)實(shí)的與或或樹(shù)表示示略有不不同：子表達(dá)式式之間的的析取關(guān)系用單單一連接接符連接接，表示示稱或的關(guān)系；；子表達(dá)式式之間的的合取關(guān)系則用用k線連接符符連接，，表示為為與的關(guān)系。。例如：對(duì)上述目目標(biāo)公式式的與/或形，可可用如下下的與/或樹(shù)表示示。目標(biāo)公式式的與/或樹(shù)表示示?P(f(z))∨Q(f(y),y)∧(?R(f(y))∨?S(y))?P(f(z))Q(f(y),y)∧(?R(f(y))∨?S(y))Q(f(y),y)?R(f(y))∨?S(y)?R(f(y))?S(y)若把葉節(jié)節(jié)點(diǎn)用它它們之間間的合取取及析取取關(guān)系連連接起來(lái)來(lái)，就可可得到原原目標(biāo)公公式的三三個(gè)子目目標(biāo)：?P(f((z))；Q(f((y),y)∧?R(f((y))；Q(f((y),y)∧??S(y)子目標(biāo)是是文字的的合取式式B規(guī)則的表表示形式式B規(guī)則的表表示形示示形式W→L其中，前前項(xiàng)W為任一與/或形公式式，后項(xiàng)L為一單文字。這里要求求B規(guī)則的右右邊為文文字，是是因?yàn)橥仆评頃r(shí)要要用它與與目標(biāo)與與或樹(shù)中中的葉節(jié)節(jié)點(diǎn)進(jìn)行行匹配（（合一）），而目目標(biāo)與或或樹(shù)中的的葉節(jié)點(diǎn)點(diǎn)是文字字。如果已知知的B規(guī)則不是是要求的的形式，，可用與與轉(zhuǎn)化F規(guī)則類似似的方法法把它轉(zhuǎn)轉(zhuǎn)化為規(guī)規(guī)定的形形式。特別地，，當(dāng)B規(guī)則為W→L1∧L2時(shí)，則可可化件為為兩條規(guī)規(guī)則W→L1和W→L2進(jìn)行處理理。已知事實(shí)實(shí)的表示示形式已知事實(shí)實(shí)的表示示形式反向演繹繹系統(tǒng)的的事實(shí)表表達(dá)式限限制為文字合取形式式，如：：F1∧F2∧…∧∧Fn其中，每每個(gè)Fi（i=1,,2,……,n）都為單文字，且都可可單獨(dú)起起作用，，因此可可表示為為如下集集合形式式{F1，F(xiàn)2，…，F(xiàn)n}規(guī)則逆向向演繹推推理過(guò)程程規(guī)則逆向向演繹推推理從目標(biāo)公公式的與與/或樹(shù)出發(fā)發(fā)，通過(guò)過(guò)運(yùn)用B規(guī)則最終終得到了了某個(gè)終終止在事事實(shí)節(jié)點(diǎn)點(diǎn)上的一一致解圖圖，推理理就可成成功結(jié)束束推理過(guò)程程1）首先用用與/或樹(shù)把目目標(biāo)公式式表示出出來(lái)；2）用B規(guī)則的右右部和與與/或樹(shù)的葉葉節(jié)點(diǎn)進(jìn)進(jìn)行匹配配，并將將匹配成成功的B規(guī)則加入入到與/或樹(shù)中；；3）重復(fù)進(jìn)進(jìn)行步驟驟2，直到產(chǎn)產(chǎn)生某個(gè)個(gè)終止在在事實(shí)節(jié)節(jié)點(diǎn)上的的一致解解圖為止止。這里里的“一一致解圖圖”是指指在推理理過(guò)程中中所用到到的代換應(yīng)該該是一致致的。規(guī)則逆向向演繹推推理過(guò)程程例：設(shè)有有如下事事實(shí)及規(guī)規(guī)則事實(shí)：f1:DOG((Fido)Fido是一只狗狗f2:?BARKS(Fido)Fido是不叫的的f3:WAGS-TAIL(Fido)Fido搖尾巴f4:MEOWS(Myrtle)貓咪的名名字叫Myrtle規(guī)則逆向向演繹推推理過(guò)程程規(guī)則：r1:((WAGS-TAIL(x1)∧DOG(x1))→FRIENDLY((x1)搖尾巴的的狗是溫溫順的狗狗r2:((FRIENDLY((x2)∧?BARKS(x2))→?AFRAID((y2,x2)溫順又不不叫的東東西是不不值得害害怕的r3:DOG((x3)→ANIMAL(x3)：狗為動(dòng)物物r4:CAT((x4)→ANIMAL(x4)：貓為動(dòng)物物r5:MEOWS(x5)→CAT(x5)：喵喵叫的的是貓規(guī)則逆向向演繹推推理過(guò)程程問(wèn)題：是否存在在這樣的的一只貓貓和一條條狗，使使得這只只貓不害害怕這只只狗？該問(wèn)題的的目標(biāo)公公式為：：(?x)((?y)((CAT(x))∧DOG(y)∧?AFRAID((x,y)))改目標(biāo)公公式經(jīng)變變換后得得到CAT((x)∧∧DOG(y))∧?AFRAID((x,y))用逆向推推理求解解該問(wèn)題題的演繹繹過(guò)程如如下圖所所示：規(guī)則逆向向演繹推推理過(guò)程程CAT(x)∧DOG(y)∧?

AFRAID(x,y)CAT(x)DOG(y)?AFRAID(x,y)CAT(x5)MEOWS(x)MEOWS(Myrtle)DOG(Fido)?AFRAID(y2,x2)?BARKS(y)?BARKS(Fido)FRIENDLY(y)FRIENDLY(x1)WAGS-TAIL(y)DOG(y)WAGS-TAIL(Fido)DOG(Fido){Fido/y}{x5/x}{y2/x,x2/y}r5r2r1{Myrtle/x}{Fido/y}{x1/y}{Fido/y}該圖有8條匹配弧弧，每條條弧上都都有一置置換。其其中終止在事事實(shí)節(jié)點(diǎn)點(diǎn)上的置置換為{Myrtle/x}}和{Fido/y}。把它們應(yīng)應(yīng)用到目目標(biāo)公式式，就得得到該問(wèn)問(wèn)題的解解：CAT(({Myrtle}∧∧DOG(Fido))∧?AFRAID(({Myrtle,Fido}基于規(guī)則則的演繹繹推理規(guī)則演繹繹系統(tǒng)規(guī)則正向向演繹系系統(tǒng)規(guī)則逆向向演繹系系統(tǒng)規(guī)則雙向向演繹系系統(tǒng)規(guī)則雙向向演繹系系統(tǒng)規(guī)則雙向向演繹系系統(tǒng)與/或形正向向演繹推推理要求求目標(biāo)公式式是文字字的析取?。繕?biāo)公公式用子子句表示示，每一一個(gè)子句句是文字字的析取?。┡c/或形逆向向演繹推推理要求求事實(shí)公式式是文字字的合取取正向和逆逆向的演演繹推理理都存在在一定的的局限性性。為了克服服這些局局限，充充分發(fā)揮揮各自的的長(zhǎng)處，，可進(jìn)行行雙向演演繹推理理。規(guī)則雙向向演繹系系統(tǒng)與/或形雙向向演繹推推理是建建立在正正向演繹繹推理和和逆向演演繹推理理基礎(chǔ)上上的，它它由表示示目標(biāo)及及表示一一直事實(shí)實(shí)的兩個(gè)個(gè)與/或樹(shù)結(jié)構(gòu)構(gòu)組成，，這些與與/或樹(shù)分別別由正向向演繹的的F規(guī)則和逆逆向演繹繹的B規(guī)則進(jìn)行行操作，，并且仍仍然限制制F規(guī)則為單單文字的的左部，，B規(guī)則為單單文字的的右部。。雙向演繹繹推理的的難點(diǎn)在于于終止條條件，只有當(dāng)當(dāng)正向和和逆向推推理的與與/或樹(shù)對(duì)應(yīng)應(yīng)的葉節(jié)節(jié)點(diǎn)都可可合一時(shí)時(shí)，推理理才能結(jié)結(jié)束。其其時(shí)機(jī)與與判斷都都難于掌掌握。更實(shí)用化化的方式式是將復(fù)復(fù)雜的問(wèn)問(wèn)題求解解任務(wù)劃劃分為相相對(duì)簡(jiǎn)單單的若干干子任務(wù)務(wù)，然后后根據(jù)子子任務(wù)的的特點(diǎn)選選用正向向或逆向向演繹推推理方式式，以便便充分發(fā)發(fā)揮兩種種方式各各自的優(yōu)優(yōu)勢(shì)。內(nèi)容提要要第三章：：確定性性推理1.推理的基基本概念念2.搜索策略略3.自然演繹繹推理4.歸結(jié)演繹繹推理5.基于規(guī)則則的演繹繹推理6.產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)產(chǎn)生式表表示法事實(shí)的表表示確定性知知識(shí)，事事實(shí)可用用如下三三元組表表示：（對(duì)象，，屬性，，值）或（關(guān)系，，對(duì)象1，對(duì)象2）如:（雪，顏顏色，白白）或（熱愛(ài)，，王峰，，祖國(guó)））非確定性性知識(shí)，，事實(shí)可可用如下下四元組組表示：：（對(duì)象，，屬性，，值，可可信度因因子）其中，““可信度度因子””是指該該事實(shí)為為真的相相信程度度?？捎糜肹0,1]之間的一一個(gè)實(shí)數(shù)數(shù)來(lái)表示示。產(chǎn)生式系系統(tǒng)產(chǎn)生式表表示法規(guī)則的表表示：P→Q或者IFPTHENQP是產(chǎn)生式式的前提提，也稱稱為前件件，它給給出了該該產(chǎn)生式式可否使使用的先先決條件件，由事實(shí)的邏邏輯組合合來(lái)構(gòu)成。。Q是一組結(jié)結(jié)論或操操作，也也稱為產(chǎn)產(chǎn)生式的的后件，，它指出出當(dāng)前題題P滿足時(shí)，，應(yīng)該推推出的結(jié)論或應(yīng)該執(zhí)行的動(dòng)動(dòng)作。產(chǎn)生式的的含義：：如果前提提P滿足，則則可推出出結(jié)論Q或執(zhí)行Q所規(guī)定的的操作產(chǎn)生式系系統(tǒng)產(chǎn)生式與與蘊(yùn)涵式式的主要要區(qū)別：：(1)蘊(yùn)涵式表表示的知知識(shí)只能能是精確確的，產(chǎn)產(chǎn)生式表表示的知知識(shí)可以以是不確確定的。。(2)蘊(yùn)含式的的匹配一一定要求求是精確確的，而而產(chǎn)生式式的匹配配可以是是不確定定的。產(chǎn)生式與與條件語(yǔ)語(yǔ)句的主主要區(qū)別別：(1)前件結(jié)構(gòu)構(gòu)不同：：產(chǎn)生式式的前件件可以是是一個(gè)復(fù)復(fù)雜的的的結(jié)構(gòu)，，而程序序設(shè)計(jì)語(yǔ)語(yǔ)言中條件語(yǔ)句句的左部是是布爾表表達(dá)式。。(2)控制流程程不同：：產(chǎn)生式式系統(tǒng)中中滿足前前提條件件的規(guī)則則被激活活后，不不一定被被立即執(zhí)執(zhí)行，能能否執(zhí)行行將取決決于沖突突消解策策略，而而條件語(yǔ)句句嚴(yán)格執(zhí)行行。產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的基基本結(jié)構(gòu)構(gòu)控制策略產(chǎn)生式規(guī)則總數(shù)據(jù)庫(kù)總數(shù)據(jù)庫(kù)庫(kù)：存放求解解問(wèn)題的的各種當(dāng)當(dāng)前信息息，如：：?jiǎn)栴}的的初始狀狀態(tài)，輸輸入的事事實(shí)，中中間結(jié)論論及最終終結(jié)論等等。推理過(guò)程程中，當(dāng)當(dāng)規(guī)則庫(kù)庫(kù)中某條條規(guī)則的的前提可可以和總總數(shù)據(jù)庫(kù)庫(kù)的已知知事實(shí)匹匹配時(shí)，，該規(guī)則則被激活活，由它它推出的的結(jié)論將將被作為為新的事事實(shí)放入入總數(shù)據(jù)據(jù)庫(kù)，成成為后面面推理的的已知事事實(shí)。產(chǎn)生式規(guī)規(guī)則：是一個(gè)規(guī)規(guī)則庫(kù)，，也稱知知識(shí)庫(kù)。用于存存放與求求解問(wèn)題題有關(guān)的的所有規(guī)規(guī)則的集集合產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的基基本結(jié)構(gòu)構(gòu)控制策略產(chǎn)生式規(guī)則總數(shù)據(jù)庫(kù)控制策略略：亦稱推理理機(jī)，用用于控制制整個(gè)產(chǎn)產(chǎn)生式系系統(tǒng)的運(yùn)運(yùn)行，決決定問(wèn)題題求解過(guò)過(guò)程的推推理線路路?？刂葡到y(tǒng)統(tǒng)的主要要任務(wù)包包括：選擇匹配配沖突消解解執(zhí)行操作作終止推理理路徑解釋釋產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的推推理正向推理理：從一組表表示事實(shí)實(shí)的謂詞詞或命題題出發(fā)，，使用一一組產(chǎn)生生式規(guī)則則，用以以證明該該謂詞公公式或命命題是否否成立。。設(shè)有規(guī)則則集合R1至R3R1：P1→P2R2：P2→P3R3：P3→P4正向推理理過(guò)程產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的推推理逆向推理理：從表示目目標(biāo)的謂謂詞或命命題出發(fā)發(fā)，使用用一組產(chǎn)產(chǎn)生式規(guī)規(guī)則證明明事實(shí)謂謂詞或命命題成立立，即首首先提出出一批假假設(shè)目標(biāo)標(biāo)，然后后逐一驗(yàn)驗(yàn)證這些些假設(shè)。。逆向推理理過(guò)程產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的推推理雙向推理理：雙向推理理的推理理策略是是同時(shí)從從目標(biāo)向向事實(shí)推推理和從從事實(shí)向向目標(biāo)推推理，并并在推理理過(guò)程中中的某個(gè)個(gè)步驟，，實(shí)現(xiàn)事事實(shí)與目目標(biāo)的匹匹配。雙向推理理過(guò)程產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的例例子：動(dòng)物識(shí)別別系統(tǒng)該系統(tǒng)可可以識(shí)別別老虎、、金錢豹豹、斑馬馬、長(zhǎng)頸頸鹿、企企鵝、信信天翁這這6種動(dòng)物。。其規(guī)則庫(kù)庫(kù)包含如如下15條規(guī)則：：r1:IF該動(dòng)物有有毛發(fā)THEN該動(dòng)物是是哺乳動(dòng)動(dòng)物r2:IF該動(dòng)物有有奶THEN該動(dòng)物是是哺乳動(dòng)動(dòng)物r3:IF該動(dòng)物有有羽毛THEN該動(dòng)物是是鳥(niǎo)r4:IF該動(dòng)物會(huì)會(huì)飛AND會(huì)下蛋THEN該動(dòng)物是是鳥(niǎo)r5:IF該動(dòng)物吃吃肉THEN該動(dòng)物是是食肉動(dòng)動(dòng)物r6:IF該動(dòng)物有有犬齒AND有爪AND眼盯前方方THEN該動(dòng)物是是食肉動(dòng)動(dòng)物產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的例例子：動(dòng)物識(shí)別別系統(tǒng)r7:IF該動(dòng)物是是哺乳動(dòng)動(dòng)物AND有蹄THEN該動(dòng)物是是有蹄類類動(dòng)物r8:IF該動(dòng)物是是哺乳動(dòng)動(dòng)物AND是嚼反芻芻動(dòng)物THEN該動(dòng)物是是有蹄類類動(dòng)物r9:IF該動(dòng)物是是哺乳動(dòng)動(dòng)物AND是食肉動(dòng)動(dòng)物AND是黃褐AND身上有暗暗斑點(diǎn)THEN該動(dòng)物是是金錢豹豹r10:IF該動(dòng)物是是哺乳動(dòng)動(dòng)物AND是食肉動(dòng)動(dòng)物AND是黃褐色色AND身上有黑黑色條紋紋THEN該動(dòng)物是是虎r11:IF該動(dòng)物是是有蹄類類動(dòng)物AND有長(zhǎng)脖子子AND有長(zhǎng)腿AND身上有暗暗斑點(diǎn)THEN該動(dòng)物是是長(zhǎng)頸鹿鹿產(chǎn)生式系系統(tǒng)產(chǎn)生式系系統(tǒng)的例例子：動(dòng)物識(shí)別別系統(tǒng)r12:IF動(dòng)物是有有蹄類動(dòng)動(dòng)物AND身上有黑黑色條紋紋THEN該動(dòng)物是是斑馬r13:IF該動(dòng)物是是鳥(niǎo)AND有長(zhǎng)脖子子AND有長(zhǎng)腿AND不會(huì)飛AND有黑白二二色THEN該動(dòng)物是是鴕鳥(niǎo)r14:IF該動(dòng)物是是鳥(niǎo)AND會(huì)游泳AND不會(huì)飛AND有黑白二二色THEN該動(dòng)物是是企鵝r15:IF該動(dòng)物是是鳥(niǎo)AND善飛THEN該動(dòng)物是是信天翁翁初始總數(shù)數(shù)據(jù)庫(kù)包包含的事事實(shí)有：：動(dòng)物有暗暗斑點(diǎn)，