不确定性推理之证据理论

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

由于客观世界的复杂，多变性和人类自身认识的局限，主观性，致使我们所获得、所处理的信息和知识中，往往含有不肯定、不准确、不完全甚至不一致的成分2024/3/6青岛理工大学通信学院2不确定性推理的概念不确定性推理泛指除精准推理以外的其他各种推理问题，包括不完备、不精准知识的推理，模糊知识的推理，非单调推理等。

不确定性推理实际上是一种从不确定的初始证据出发，通过运用不确定性知识，最终推出具有一定不确定性但却又是合理或基本合理的结论的思维过程。2024/3/6青岛理工大学通信学院3不确定性推理方法分类2024/3/6青岛理工大学通信学院4不确定性推理数值方法非数值方法框架推理语义网络推理常识推理模糊推理基于概率的方法主观Bayes方法证据理论可信度方法证据理论1形式化描述2不确定性推理模型2024/3/6青岛理工大学通信学院61、

证据理论

概述

由Dempster首先提出，并由他的学生Shafer发展起来，也称D-S理论。在专家系统的不精准推理中已得到广泛的应用。2024/3/6青岛理工大学通信学院71.1规则正向演绎系统定义

正向规则演绎系统是从事实到目标进行操作的，即从状况条件到动作进行推理的，也就是从if到then的方向进行推理的。

求解过程事实表达式的与或形变换

在基于规则的正向演绎系统中，我们把事实表示为非蕴涵形式的与或形，作为系统的总数据库。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规则正向演绎系统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规则变换

这些规则是建立在某个问题辖域中普通陈述性知识的蕴涵公式基础上的。我们把允许用作规则的公式类型限制为下列形式：

L

W

式中：L是单文字；W为与或形的唯一公式。下面的证明限定：目标是可以证明的，目标是析取关系1.1规则正向演绎系统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规则得到的与或图SX∧YZXYP∨Q∨X∨ZP∨Q∨Y∨ZR∨X∨ZR∨Y∨Z2024/3/6青岛理工大学通信学院14(A∨B)事实:A∨B规则:A

C∧D,B

E∧G目标:C∨G(析取)CDCAABBEGG~A∨C~C~G~B∨GA∨B~A~B~BNIL结论：以目标节点作为终止解图时，系统成功终止。2024/3/6青岛理工大学通信学院151.2规则逆向演绎系统定义逆向规则演绎系统是从then向if进行推理的，即从目标或动作向事实或状况条件进行推理的。

求解过程目标表达式的与或形式与或图的B规则变换,W

L,L是单文字；W为与或形的公式作为终止条件的事实节点的一致解图2024/3/6青岛理工大学通信学院161.2规则逆向演绎系统例如：(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

正向和逆向组合系统是建立在两个系统相结合的基础上的。此组合系统的总数据库由表示目标和表示事实的两个与或图结构组成。这些与或图结构分别用正向系统的F规则和逆向系统的B规则来修正。1.3规则双向演绎系统2024/3/6青岛理工大学通信学院202产生式系统定义：用来描述若干个不同的以一个基本概念为基础的系统。这个基本概念就是产生式规则或产生式条件和操作对的概念。实质：在产生式系统中，论域的知识分为两部分：用事实表示静态知识，如事物、事件和它们之间的关系；用产生式规则表示推理过程和行为。由于这类系统的知识库主要用于存储规则，因此又把此类系统称为基于规则的系统。2024/3/6青岛理工大学通信学院212.1产生式系统的组成控制策略图3.22产生式系统的主要组成总数据库产生式规则一个产生式系统由下列3部分组成：一个总数据库(globaldatabase)，它含有与具体任务有关的信息。一套规则，它对数据库进行操作运算。每条规则由左右两部分组成，左部鉴别规则的适用性或先决条件，右部描述规则应用时所完成的动作。应用规则来改变数据库。一个控制策略，它确定应该采用哪一条适用规则，而且当数据库的终止条件满足时，就停止计算。

2024/3/6青岛理工大学通信学院22选择规则到执行操作的步骤

1匹配

把当前数据库与规则的条件部分相匹配。

2冲突

当有一条以上规则的条件部分和当前数据库相匹配时，就需要决定首先使用哪一条规则，这称为冲突解决。

3操作

操作就是执行规则的操作部分。2024/3/6青岛理工大学通信学院232.2产生式系统的推理

正向推理：从一组表示事实的谓词或命题出发，使用一组产生式规则，用以证明该谓词公式或命题是否成立。

逆向推理：从表示目标的谓词或命题出发，使用一组产生式规则证明事实谓词或命题成立，即首先提出一批假设目标，然后逐一验证这些假设。

双向推理：双向推理的推理策略是同时从目标向事实推理和从事实向目标推理，并在推理过程中的某个步骤，实现事实与目标的匹配。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)。此外，还建立了一些非单调推理系统及基于非单调逻辑的知识表示语言，如多伊尔设计的正确性维持系统TMS(TruthMaintenanceSystem)，罗伯特等建立的知识表示语言FRL等3.2缺省理论缺省理论又称为缺省逻辑，它是在知识不完全的情况下使推理得以继续下去的一种非单调推理的理论。基本思想：在知识不完全的情况下，为了使推理得以进行下去，假设某些命题成立，并在此基础上进行推理。作出“假设”的原则是：如果没有足够的证据能证明某个命题不成立，则认为该命题是成立的。这样的推理又称为默认推理。2024/3/6青岛理工大学通信学院27赖特的缺省理论1）缺省理论的核心是缺省规则，形式如下：其中，A(x)表示缺省规则的先决条件，Bi(x)表示默认条件，C(x)表示结论。M称为模态算子，表示“假定…是相容的”，即其否定不可证明。（2）上述缺省规则表示：如果先决条件A(x)成立，而且假定默认条件Bi(x)相容，则可推出结论C(x)成立。例如：2024/3/6青岛理工大学通信学院28缺省规则的分类缺省规则按其形式可分为规范缺省、半规范缺省及不规范缺省三类。规范缺省如果默认条件为B(x)，且B(x)=C(x)，则称为规范的缺省规则缺省规则通常表示“大部分…一般…