不確定性推理之證據理論

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

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

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

證據理論

概述

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

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

求解過程事實表達式的與或形變換

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

u)(

v){Q(v,u)∧~[(R(v)∨P(v))∧S(A,v)]}表示為非蘊涵形式的與或形：{A/u}Q(v,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}1.1規(guī)則正向演繹系統(tǒng)2024/3/6青島理工大學通信學院92.事實表達式的與或圖表示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一個事實表達式的與或樹表示子句集：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青島理工大學通信學院10與或圖的F規(guī)則變換

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

L

W

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

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

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

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

(x){[(

y)(

z)~P(x,y,z)]∨(u)Q(x,u)}3)進行Skolem標準化：

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

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

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

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

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

C∧D,B

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

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

L,L是單文字；W為與或形的公式作為終止條件的事實節(jié)點的一致解圖2024/3/6青島理工大學通信學院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))目標子句是文字的合?。簙P(f(z))Q(f(y),y)∧~P(f(y))Q(f(x),x)∧~S(x)2024/3/6青島理工大學通信學院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青島理工大學通信學院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青島理工大學通信學院19

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

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

1匹配

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

2沖突

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

3操作

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

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

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

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

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