不確定性推理之證據(jù)理論

人工智能ArtificialIntelligence程雷雷不確定性推理不確定性：

由于客觀世界的復(fù)雜，多變性和人類自身認(rèn)識的局限，主觀性，致使我們所獲得、所處理的信息和知識中，往往含有不肯定、不準(zhǔn)確、不完全甚至不一致的成分2024/3/6青島理工大學(xué)通信學(xué)院2不確定性推理的概念不確定性推理泛指除精準(zhǔn)推理以外的其他各種推理問題，包括不完備、不精準(zhǔn)知識的推理，模糊知識的推理，非單調(diào)推理等。

不確定性推理實(shí)際上是一種從不確定的初始證據(jù)出發(fā)，通過運(yùn)用不確定性知識，最終推出具有一定不確定性但卻又是合理或基本合理的結(jié)論的思維過程。2024/3/6青島理工大學(xué)通信學(xué)院3不確定性推理方法分類2024/3/6青島理工大學(xué)通信學(xué)院4不確定性推理數(shù)值方法非數(shù)值方法框架推理語義網(wǎng)絡(luò)推理常識推理模糊推理基于概率的方法主觀Bayes方法證據(jù)理論可信度方法證據(jù)理論1形式化描述2不確定性推理模型2024/3/6青島理工大學(xué)通信學(xué)院61、

證據(jù)理論

概述

由Dempster首先提出，并由他的學(xué)生Shafer發(fā)展起來，也稱D-S理論。在專家系統(tǒng)的不精準(zhǔn)推理中已得到廣泛的應(yīng)用。2024/3/6青島理工大學(xué)通信學(xué)院71.1規(guī)則正向演繹系統(tǒng)定義

正向規(guī)則演繹系統(tǒng)是從事實(shí)到目標(biāo)進(jìn)行操作的，即從狀況條件到動作進(jìn)行推理的，也就是從if到then的方向進(jìn)行推理的。

求解過程事實(shí)表達(dá)式的與或形變換

在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實(shí)表示為非蘊(yùn)涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。2024/3/6青島理工大學(xué)通信學(xué)院81.事實(shí)表達(dá)式的與或形變換例如：(

u)(

v){Q(v,u)∧~[(R(v)∨P(v))∧S(A,v)]}表示為非蘊(yùn)涵形式的與或形：{A/u}Q(v,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}1.1規(guī)則正向演繹系統(tǒng)2024/3/6青島理工大學(xué)通信學(xué)院92.事實(shí)表達(dá)式的與或圖表示Q(v,A)∧{[~R(v)∧~P(v)]∨~S(A,v)}Q(v,A)[~R(v)∧~P(v)]∨~S(A,v)~R(v)∧~P(v)~S(A,v)~R(v)~P(v)圖2.8一個事實(shí)表達(dá)式的與或樹表示子句集：Q(v,A)~R(v)∨~S(A,v)~P(v)∨~S(A,v)換名：Q(w,A)~R(v)∨~S(A,v)~P(x)∨~S(A,x)2024/3/6青島理工大學(xué)通信學(xué)院10與或圖的F規(guī)則變換

這些規(guī)則是建立在某個問題轄域中普通陳述性知識的蘊(yùn)涵公式基礎(chǔ)上的。我們把允許用作規(guī)則的公式類型限制為下列形式：

L

W

式中：L是單文字；W為與或形的唯一公式。下面的證明限定：目標(biāo)是可以證明的，目標(biāo)是析取關(guān)系1.1規(guī)則正向演繹系統(tǒng)2024/3/6青島理工大學(xué)通信學(xué)院11例如：

(x){[(y)(z)P(x,y,z)]

(u)Q(x,u)}1)暫時消去蘊(yùn)涵符號：

(x){~[(y)(z)P(x,y,z)]∨(u)Q(x,u)}2)減小否定符號的轄域：

(x){[(

y)(

z)~P(x,y,z)]∨(u)Q(x,u)}3)進(jìn)行Skolem標(biāo)準(zhǔn)化：

(x){[(y)~P(x,y,f(x,y))]∨(u)Q(x,u)}4)換名并消去全稱量詞：

~P(x,y,f(x,y))∨Q(x,u)5)恢復(fù)蘊(yùn)涵式：

P(x,y,f(x,y))

Q(x,u)/lingol/archive/2009/08/05/92252.html2024/3/6青島理工大學(xué)通信學(xué)院12[(P∨Q)∧R]∨[S∧(T∨U)]P∨Q(P∨Q)∧RT∨UPQRS∧(T∨U)STU圖2.9不含變量的與或圖2024/3/6青島理工大學(xué)通信學(xué)院13[(P∨Q)∧R]∨[S∧(T∨U)]P∨Q(P∨Q)∧RT∨UPQRS∧(T∨U)STU圖2.10應(yīng)用L

W規(guī)則得到的與或圖SX∧YZXYP∨Q∨X∨ZP∨Q∨Y∨ZR∨X∨ZR∨Y∨Z2024/3/6青島理工大學(xué)通信學(xué)院14(A∨B)事實(shí):A∨B規(guī)則:A

C∧D,B

E∧G目標(biāo):C∨G(析取)CDCAABBEGG~A∨C~C~G~B∨GA∨B~A~B~BNIL結(jié)論：以目標(biāo)節(jié)點(diǎn)作為終止解圖時，系統(tǒng)成功終止。2024/3/6青島理工大學(xué)通信學(xué)院151.2規(guī)則逆向演繹系統(tǒng)定義逆向規(guī)則演繹系統(tǒng)是從then向if進(jìn)行推理的，即從目標(biāo)或動作向事實(shí)或狀況條件進(jìn)行推理的。

求解過程目標(biāo)表達(dá)式的與或形式與或圖的B規(guī)則變換,W

L,L是單文字；W為與或形的公式作為終止條件的事實(shí)節(jié)點(diǎn)的一致解圖2024/3/6青島理工大學(xué)通信學(xué)院161.2規(guī)則逆向演繹系統(tǒng)例如：(y)(x){P(x)

[Q(x,y)∧~[P(x)∧S(y)]]}化成與或形：~P(f(y))

∨{Q(f(y),y)∧[~P(f(y))∨~S(y)]}~P(f(y))∨{Q(f(y),y)∧[~P(f(y))∨~S(y)]}{Q(f(y),y)∧[~P(f(y))∨~S(y)]}~P(f(y))[~P(f(y))∨~S(y)]Q(f(y),y)~S(y)~P(f(y))目標(biāo)子句是文字的合?。簙P(f(z))Q(f(y),y)∧~P(f(y))Q(f(x),x)∧~S(x)2024/3/6青島理工大學(xué)通信學(xué)院17例：

F1:DOG(FIDO)；狗的名字叫Fido F2:~BARKS(FIDO)；Fido不叫的

F3:WAGS-TAIL(FIDO)；Fido搖尾巴

F4:MEOWS(MYRTLE)；貓咪的名字叫Myrtle R1:[WAGS-TAIL(x1)∧DOG(x1)]FRIENDLY(x1)；

搖尾巴的狗是溫順的狗

R2:[FRIENDLY(x2)∧~BARKS(x2)]~AFRAID(y2,x2)；

溫順而不叫的東西是不值得害怕的

R3:DOG(x3)ANIMAL(x3)；狗是動物

R4:CAT(x4)ANIMAL(x4)；貓是動物

R5:MEOWS(x5)

CAT(x5)；貓咪是貓問題：是否存在一只貓和一條狗，使得這只貓不怕這條狗（找到一只不怕狗的貓）？

(x)(y)[CAT(x)∧DOG(y)∧~AFRAID(x,y)]2024/3/6青島理工大學(xué)通信學(xué)院18CAT(x)∧DOG(y)∧~AFRAID(x,y)CAT(x)DOG(y)~AFRAID(x,y)WAGS-TAIL(FIDO)DOG(FIDO)DOG(y)~AFRAID(y2,x2)FRIENDLY(y)~AFRAID(x,y)WAGS-TAIL(y){FIDO/y}{FIDO/y}~BARKS(FIDO)MEOWS(MYRTLE){y/x1}{FIDO/y}{MYRTLE/x}R1DOG(FIDO){FIDO/y}~BARKS(y){x/y2,y/x2}R2MEOWS(x)CAT(x5){x/x5}R52024/3/6青島理工大學(xué)通信學(xué)院19

正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標(biāo)和表示事實(shí)的兩個與或圖結(jié)構(gòu)組成。這些與或圖結(jié)構(gòu)分別用正向系統(tǒng)的F規(guī)則和逆向系統(tǒng)的B規(guī)則來修正。1.3規(guī)則雙向演繹系統(tǒng)2024/3/6青島理工大學(xué)通信學(xué)院202產(chǎn)生式系統(tǒng)定義：用來描述若干個不同的以一個基本概念為基礎(chǔ)的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則或產(chǎn)生式條件和操作對的概念。實(shí)質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：用事實(shí)表示靜態(tài)知識，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)則表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)則，因此又把此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)。2024/3/6青島理工大學(xué)通信學(xué)院212.1產(chǎn)生式系統(tǒng)的組成控制策略圖3.22產(chǎn)生式系統(tǒng)的主要組成總數(shù)據(jù)庫產(chǎn)生式規(guī)則一個產(chǎn)生式系統(tǒng)由下列3部分組成：一個總數(shù)據(jù)庫(globaldatabase)，它含有與具體任務(wù)有關(guān)的信息。一套規(guī)則，它對數(shù)據(jù)庫進(jìn)行操作運(yùn)算。每條規(guī)則由左右兩部分組成，左部鑒別規(guī)則的適用性或先決條件，右部描述規(guī)則應(yīng)用時所完成的動作。應(yīng)用規(guī)則來改變數(shù)據(jù)庫。一個控制策略，它確定應(yīng)該采用哪一條適用規(guī)則，而且當(dāng)數(shù)據(jù)庫的終止條件滿足時，就停止計算。

2024/3/6青島理工大學(xué)通信學(xué)院22選擇規(guī)則到執(zhí)行操作的步驟

1匹配

把當(dāng)前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。

2沖突

當(dāng)有一條以上規(guī)則的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。

3操作

操作就是執(zhí)行規(guī)則的操作部分。2024/3/6青島理工大學(xué)通信學(xué)院232.2產(chǎn)生式系統(tǒng)的推理

正向推理：從一組表示事實(shí)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。

逆向推理：從表示目標(biāo)的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實(shí)謂詞或命題成立，即首先提出一批假設(shè)目標(biāo)，然后逐一驗(yàn)證這些假設(shè)。

雙向推理：雙向推理的推理策略是同時從目標(biāo)向事實(shí)推理和從事實(shí)向目標(biāo)推理，并在推理過程中的某個步驟，實(shí)現(xiàn)事實(shí)與目標(biāo)的匹配。3.非單調(diào)推理2024/3/6青島理工大學(xué)通信學(xué)院243.1非單調(diào)推理的概念單調(diào)推理：S1：已有的知識集

S2：增加新知識后的知識集采用經(jīng)典邏輯的演繹推理，則有下式成立：顯然，在這種推理中，推出的結(jié)論是隨著知識的增加而單調(diào)增多的。這樣的推理就是單調(diào)推理。2024/3/6青島理工大學(xué)通信學(xué)院25非單調(diào)推理：假設(shè)已有的知識集S1，當(dāng)知識由S1增加至S2時，盡管有，則不一定有這樣的推理稱為非單調(diào)推理。人類的思維推理在很多情況下是非單調(diào)的。非單調(diào)推理產(chǎn)生的一個主要原因是，在知識不完全的情況下，為了使推理得以進(jìn)行下去，而采用了某些假設(shè)。3.非單調(diào)推理關(guān)于非典調(diào)推理的代表性理論2024/3/6青島理工大學(xué)通信學(xué)院26R.Reiter等人提出的缺省理論(DefaultTheories)。J.McCarthy等人提出的界限理論(CircumscriptionTheories)。D.McDermott與J.Doyle提出的非單調(diào)邏輯(Non-monotonicLogic)。此外，還建立了一些非單調(diào)推理系統(tǒng)及基于非單調(diào)邏輯的知識表示語言，如多伊爾設(shè)計的正確性維持系統(tǒng)TMS(TruthMaintenanceSystem)，羅伯特等建立的知識表示語言FRL等3.2缺省理論缺省理論又稱為缺省邏輯，它是在知識不完全的情況下使推理得以繼續(xù)下去的一種非單調(diào)推理的理論?；舅枷耄涸谥R不完全的情況下，為了使推理得以進(jìn)行下去，假設(shè)某些命題成立，并在此基礎(chǔ)上進(jìn)行推理。作出“假設(shè)”的原則是：如果沒有足夠的證據(jù)能證明某個命題不成立，則認(rèn)為該命題是成立的。這樣的推理又稱為默認(rèn)推理。2024/3/6青島理工大學(xué)通信學(xué)院27賴特的缺省理論1）缺省理論的核心是缺省規(guī)則，形式如下：其中，A(x)表示缺省規(guī)則的先決條件，Bi(x)表示默認(rèn)條件，C(x)表示結(jié)論。M稱為模態(tài)算子，表示“假定…是相容的”，即其否定不可證明。（2）上述缺省規(guī)則表示：如果先決條件A(x)成立，而且假定默認(rèn)條件Bi(x)相容，則可推出結(jié)論C(x)成立。例如：2024/3/6青島理工大學(xué)通信學(xué)院28缺省規(guī)則的分類缺省規(guī)則按其形式可分為規(guī)范缺省、半規(guī)范缺省及不規(guī)范缺省三類。規(guī)范缺省如果默認(rèn)條件為B(x)，且B(x)=C(x)，則稱為規(guī)范的缺省規(guī)則缺省規(guī)則通常表示“大部分…一般…