人工智能6 不确定推理人工智能课程中国海洋大学

1、人工智能教案第五章 不精确推理海洋大学计算机系 陈勇不确定信息n在日常生活和科学研究中,人们一直在追求用某一确定的数学模型或Conm集合理论来解决问题或描述现象。然而,真实世界是不断变化的、不完全的、不精确的,充满着矛盾的、复杂相关的信息世界。这就是说,用确定的概念描述事物往往是有局限性的。正如著名的逻辑学家Russell所说自俨所有的传统逻辑都习惯地假设所使用的符号是精确的,所以它就不能适用于我们这个人间的世界,而只能适应于一个理想中的天堂,逻辑研究比别的任何研究都使我们更接近上帝。不确定信息n现实世界中任务和环境常常只有不确定的信息。到目前为止所讨论的技术对不确定知识的表示和推理能力十分有

2、限。一条语句如PQ允许我们表示不确定性P和Q哪一个是真的，但是还没有描述如何表示关于P或Q不确定的程度。不确定信息n在现实世界中,包含有大量的柔性信息,表征出模糊性、复杂性和不精确性,因而不精确推理、非单调推理和模糊推理就变得十分重要了。在这一章,将讨论几种基本的不确定知识表示及推理的方法。第一节 不确定推理概述n当代冯诺依曼计算机具有强大的计算能力,在数值计算、数据处理、文档处理、工业控制乃至知识工程中的逻辑推理方面发挥出来的本领已远远超过人类。不过,计算机在这些应用领域中所解决的问题都是良性设定问题,即求解问题的前提条件明确,求解的算法存在,并且可以用某种程序设计语言进行明确地描述。第一节

3、 不确定推理概述n然而,在真实的世界中,存在有大量求解算法难以描述的非良性设定问题需要解决。一般说来,问题的不确定性来自知识的客观现实和对知识的主观认识水平。现实世界中,几乎没有什么事情是完全确定的,处理不确定性问题的目的是希望得到对某一命题的尽可能精确的判断。对于不确定性推理来说,不确定性的描述和不 确定性的传播是两个主要问题。一、不确定性问题的代数模型n一个问题的代数模型是由论域、运算和公理三部分所组成的。所以,我们讨论各种不确定性推理方法时应符合某种代数结构。比如,在某种意义下构成半群,即在不确定性值域上,不确定性度量的合成运算具有封闭性并满足结合律。按照这种方法建立起来的不确定性问题模

4、型需要涉及下面的三个问题。一、不确定性问题的代数模型n(一)不确定性知识的表示n 不确定性知识的表示主要解决用什么方法来描述知识的不确定性问题。常用的方法有数值法和非数值法。数值法以概率方法、确定因子法、DS证据理论和可能性理论为代表；非数值法则以批注理论和非单调逻辑为代表。数值法表示便于计算、比较,非数值法表示便于定性分析,两种方法的结合是描述不确定性知识的好办法。一、不确定性问题的代数模型n(二)不确定性知识的推理n 不确定性知识的推理是指知识不确定性的传播和更新,即新的不确定性知识的获取过程。这个过程是在公理比如领域专家给出的规则强度和用户给出的原始证据的不确定性度)的基础上,定义一组函

5、数,计算出定理(非原始数据的命题的不确定性度量。也就是说,根据原始证据的不确定性和知识的不确定性,求出结论的不确定性。一、不确定性问题的代数模型一个不确定性知识推理包括如下的算法:n 算法1：根据规则前提E的不确定性C(E)和规则强度f(H,E,求出假设H的不确定性C(H),即定义函数g1,使得：C(H)=g1C(E),f(H,E)n 算法2: 根据分别由独立的证据E1和E2所求得的假设H的不确定性Cl(H)和C2(H),求出证据E1和E2的组合所导致的假设H的不确定性C(H),即定义函数g2,使得：C(H)=g2Cl(H),C2(H)一、不确定性问题的代数模型n算法3: 根据两个证据E1和E

6、z的不确定性C(EI)和C(E2),求出证据E1和E2的合取的不确定性,即定义函数g3,使得：C(EInE2=g2C(E1),C(E2)n算法4: 根据两个证据E1和E2的不确定性C(El)和C(E2),求出证据EI和E2的析取的不确定性,即定义函数g4,使得:C(EIVE2)=g4C(E1),C(E2)一、不确定性问题的代数模型n观察下图所示的推理网络。设A1、A2、A3和A4为原始证据,即已知证据A1、A2、A3和A4的不确定性分别为C(A1)、C(A2)、C(A3)和C(A4)。求A5、A6和A7的不确定性。问题的求解过程为:n1.由证据Al和A2的不确定性C(A1)和C(A2),根据算

7、法4求出A1和A2析取的不确定性C(A1VA2)。n2.由A1和A2析取的不确定性C(A1VA2)和规则R1的规则强度f1,根据算法1求出A5的不确定性C(A5)。n3.由证据A3和A4的不确定性C(A3)和C(A4),根据算法3求出A3和A4合取的不确定性C(A3nA4)。n4.由A3和A4合取的不确定性C(A3nA4)和规则R2的规则强度f2,根据算法1求出A6的不确定性C(A6)。n5.由A5的不确定性C(A5)和规则R3的规则强度f3,根据算法1求出A7的其中的一个不确定性C(A7)。n6由A6的不确定性C(A6)和规则R4的规则强度F4,根据算法1求出A7的另外一个不确定性C(A7)

8、。n7.由A7的两个根据独立证据分别求出的不确定性C(A7)和 C(A7),根据算法2求出A7最后的不确定性C(A7)。一、不确定性问题的代数模型n(三)不确定性知识的语义：n 综上所述，对于一个不确定推理应指出不确定性表示和推理的含义。基于概率的方法较好的解决这个问题。n 如规则强度f(B,A)可理解为当证据A为真时,对假设B为真的一种影响程度;而C(A)可理解为A为真的程度,即对于f(B,A)和C(A),应给出:一、不确定性问题的代数模型对于f(B,A)而言:n(1)A为真则B为真,这时f(B,A)=?n(2)A为真则B为假,这时f(B,A)=?n(3A对B没有影响时,这时f(B,A)=?

9、n对于C(A)而言:n(1A为真时,C(A)=?n(2) A为假时,C(A)=?n(3) 对A一无所知时,C(A)=?二、几种主要的不确定性推理方法n不确定性推理方法是70年代提出并开展研究的。比如Shortliffe等人1975年在MYCIN专家系统开发中,提出了确定因子法;Duda等人1976年在PROSPECTOR专家系统开发中给出了主观贝叶斯法;Dempster和Shafer1976年提出了证据理论;Zadeh在1978年提出了可能性理论,1983年又提出了模糊理论;Cohen在1985年也论述了一种称为批注理论的非数值方法等。下面简要地介绍这几种方法。1.确定因子法n确定因子法是MY

10、CIN专家系统中使用的不确定性推理方法。该方法以确定性理论为基础,采用可信度来刻画不确定性。其优点是简单、实用,在许多专家系统中得到了应用,取得了较好的效果。2.主观贝叶斯方法n主观贝叶斯方法是PROSPECTOR专家系统中使用的不确定性推理方法。它是基于贝叶斯(Bayes)公式修正后而形成的一种不确定性推理方法。该方法的优点是具有较强的数学基础,计算工作量也较为适中。3.DS证据理论nDS证据理论是由Dempster提出,由他的学生Shafer发展起来的。该理论引进了信任函数,这些函数可以满足比概率函数的公理还要弱的公理,因而可以用来处理由不知道所引起的不确定性。4.可能性理论n可能性理论的

11、基础是Zadeh本人的模糊集合理论。正如概率论处理的是由随机性引起的不确定性一样,可能性理论处理的是由模糊性引起的不确定性。5.批注理论n批注理论(Endorsement)是一种非数值方法。它将系统所使用的推理规则和议程中的任务都加以批注。规则的批注提出前提条件与规则结论的关系,任务的批注指出该任务的结论与议程中另一任务的结论之间的协同、冲穷、潜在冲突及冗余情况。这些批注与数据源、数据类型和数据的精度有关。该理论的优点是可以表示出用数值难以表达的较复杂的关系。缺点是系统每步规则推理都要将前提的批注转移到结论中,从而使得结论中的批注迅速增长,对于结论的选择变得困难。第二节 不确定推理方法下面详细

12、讨论几种主要的不确定推理方法。n一、确定性因子法n一知识的不确定性n 在MYCIN中,知识是由规则表示的。它的一般形式为:IF E1 AND E2 AND AND En THEN H(X)一知识的不确定性n其中Ei(i=1,2,.,n)是证据,H可以是一个或多个结论。具有此规则形式的解释为当证据E1、E2、En都存在时,结论H具有X确定性因子CFCertainty Factor)。z的具体值由领域专家主观地给出,z的取值范围为-1,1内。z0表示证据存在,增加结论为真的确定性程度,z越大结论越真,z=1表示证据存在结论为真。相反,z0表示因证据E的出现而增加对假设H为真的信任增长度,即P(H|

13、EPH,而MD(H,E0表示因证据E的出现而增加对假设H为真的不信任增长度,即P(H|E)0时,MD(H,E)=0 当MD(H,E)0时,MB(H,E)=0 MB与MD的互斥性表明对于同一个证据E,不可能同时既增加对H的信任增长度,又增加对H的不信任增长度,即不可能因为证据E的出现,既使P(H|E)P(H)又使 P(H|E)P(H)。一知识的不确定性n2.假设的互斥性 若对于同一证据有n个互不相容的假设Hi(i=1,2,n),则仅当证据E在逻辑上蕴含某个假设Hi时,上式的等式才成立。根据性质(1)可以直接用概率值来表示:一知识的不确定性n3.值域 MB、MD和CF的值域为:0=MB(H,E)=

14、10=MD(H,E)=1-1=CF(H,E)=1n4.证实的情况一知识的不确定性n5.不证实的情况 若MB(H,E)=0,说明E的存在证实不了H,或者是E与H独立,或者是E否认H。 若MD(H,E)=0,说明E的存在不否认H,或者是H与E独立,或者是E证实H。 若CFH|E)=0,表示E与H独立。一知识的不确定性n6.CF不同于概率P 从上面的定义可以看出,确定性因子法中的CF与概率P有一定的对应关系,但又有所区别,因为对于概率恒有:P(H|E)+P(H|E)=1 而CF(H|E)+CF(H|E)=0 由此可见,确定性因子法的CF的概念与概率P的概念是不同的。二证据的不确定性n在MYCIN系统

15、中,证据的不确定性是用证据的确定性因子CF(E)表示的。原始证据的确定性因子由用户主观地给出,非原始证据的确定性因子由不确定性推理获得。n证据的不确定性有下面的几个性质: 1.值域 当证据E以某种程度为真时,有0=CF(E)=1。 当证据E以某种程度为假时,有一1=CF(EO(i=1,2,n),P(B)0,那么按乘法定理有:P(B)P(Ai|B)=P(Ai)P(B|Ai)n所以:二、主观Bayes方法n又由全概率公式,可得到:因此有: 我们称这个公式为Bayes公式,同时称P(A1) P(A2), , P(An)的值为先验概率;P(A1|B),p(A2|B), P(An|B)的值为后验概率。B

16、ayes公式就是从先验概率推导出后验概率的公式。n在基于规则的专家系统中,Bayes公式可以写成为: 在直接使用Bayes公式描述不确定性时,计算后验概率P(H|E)需要知道先验概率P(E|H),而因为先验概率又是难以给出的量,为了克服这一困难,所以就提出了主观Bayes方法。下面我们介绍主观Bayes方法对规则不确定性的描述。先给出几个定义:n1.几率函数 几率函数定义为O(x)=P(x)/1-P(x)。它表示证据x的出现概率与不出现概率之比,从定义可知,随着P(x)的增大, O(x)也增大,而且 当P(x)=0时,有O(x)=O 和 当P(x)=1时,有O(x)= 这样,取值为0,1的P(

17、x)被放大为取值为0,)的O(x)。n2.充分性度量 充分性度量定义为:n3.必要性度量 必要性度量定义为: 对于证据确定的情况,此时P(E)=1或P(E)=0,现在假定有规则:IF E THEN H 根据Bayes公式有:将上述两式相除,得n再利用几率函数和LS,上式可表示为 从这个式子可以看出,LS越大,0(H|E)就越大,而P(H|E)越大,说明E对H的支持越强。当LS时,0(H|E),从而有P(H|E)1,说明E的存在导致H为真。因此,我们说E对H是充分的,且称LS为充分性度量。n 同理,可以得到LN反映了H的出现对H的支持程度。当LN=0时,将导致O(H|E)=0,说明E不存在导致H

18、为假。因此,我们说E对H是必要的,且称LN为必要性度量。n 在主观Bayes方法中,一条规则变成了如下的形式:IF E THEN (LS,LN) H 其中参数LS,LN和先验几率O(H)要由领域专家主观给出,先计算出后验几率,再计算出后验概率。n在主观Bayes方法中,证据的不确定性是采用概率P的等价形式一一几率函数0(x)来描述的。下面就证据E确定和不确定时的情况分别进行讨论。n1.当证据E确定必出现时,可直接使用公式 以求得使用规则E-H后,0(H)的更新值O(H|E), O(H|E)。若需要以概率的形式表示,再由公式:计算出P(H|E)和P(HlE)。n2.当证据E不确定时,即P(E)1

19、,这时需要作如下的工作。 设E是与E有关的所有观察,对规则EH来说有公式(1976年由Duda给出)P(H|E)=P(H|E)P(E|E)+P(H|E)P(E|E) 当P(E|E)=1时,证据E必然出现,有我们不难验证此公式的正确性。证明如下。证毕.n当P(E|E)=0时,证据E必然不出现,同理有:n当P(E|E)=P(E)时,即观察E对E无影响,有: 这样,我们可以从P(E |E)分别为0,P(E)和1确定与其相应的P(H|E)值。主观Bayes方法采用分段线性插值的方法,由P(E |E)的任意取值,可得到相应的P(H | E)值,如下图所示。n3.证据合取情况 设在观察E之下,证据E1,E

20、2,En的概率为P(E1|E)、P(E2|E)、P(En|E),那么有:n4.证据析取情况 设在观察E之下,证据E1,E2,En的概率为P(E1|E)、P(E2|E)、P(En|E),那么有:n5.相互独立的证据导出同一假设情况 例 设一组相互独立的证据E1、E2、En的观察分别为E1、Ez、En并且有规则E1H,E2H,EnH。 假定由这些规则得到的假设H的后验几率分别是0(H|E1)、0(H|E2)、0(H|En),那么由这些独立证据的组合相应得到的假设H的后验几率为:(三) 举例n例 PROSPECTOR专家系统中的部分推理网络如下图所示。图中各结点的先验概率标在结点的右上方,规则的LS

21、和LN值标在该规则连线的一侧。用户给出的各原始证据在各自的观察之下概率为:P(FMGS|S1)=0.7,P(FMGS AND PT|S2)=0.6,P(STIR |S3)=0.02现要求计算假设HYPE的后验概率P(HYPE|S1 AND S2 AND S3)。 以上计算表明,经推理后假设HYPE的概率已从先验概率0.01增大到后验概率0.1245264。 另见教材P140 例5.2主观Bayes方法的优点n1.基于Bayes规则的计算方法具有公理基础和易于理解的数学性质,它提供了两个规则强度,恰当地处理了证据存在和不存在两种情况对假设的影响,以及分段线性插值方法较好地处理了主观概率的数学不一致性。n2.该方法的计算工作量适中。主观Bayes方法的缺点n1.要求具有指数级的先验概率,可能导致组合爆炸。另外,由于概率的分派具有主观