第三章问题求解技术精选PPT.ppt

第三章问题求解技术1第1页，本讲稿共98页第第3章章 问题求解技术问题求解技术智能信息处理与仪器研究室学习要求学习要求：1.了解命题逻辑与谓词逻辑的区别与联系，掌握谓词公式的概念及可满足性的定义，弄清置换与合一的概念，掌握求取最一般合一置换的方法。2.掌握归结原理及归结推理方法。激扬SKOLEM标准式和子句集的求取方法，理解谓词公式和子句集在不可满足意义下的一致性，弄懂HERBRAND定理，掌握H域、原子集、H域上的解释的求法，掌握命题逻辑和谓词逻辑中的归结原理。3.掌握利用归结原理进行定理证明的方法。4.掌握应用归结原理进行问题求解的方法。5.掌握归结过程中的控制策略。第2页，本讲稿共98页第第3章章 问题求解技术问题求解技术智能信息处理与仪器研究室学习要求：6.理解不确定推理的基本概念和意义，了解不确定推理方法的种类，充分认识不确定推理中的基本问题，即不确定性的表示问题（包括证据不确定性和知识不确定性的表示）、不确定性的推理计算问题以及不确定性的度量问题。7.可信度方法又称确定性方法，是目前常用的不确定推理方法之一。要求充分理解可信度的概念，理解CF的含义，掌握利用可信度表示知识（规则）和证据的方法，掌握计算结论可信度的推理计算方法，并熟记各种推理计算公式。第3页，本讲稿共98页第第3章章 问题求解技术问题求解技术智能信息处理与仪器研究室学习要求：8.主观BAYES方法是常用的不确定性推理方法之一。要求理解主观BAYES方法与基本BAYES概率公式之间的关系，了解主观BAYES方法的推理网络；掌握主观BAYES方法中知识（规则）不确定性和证据不确定性的表示方法，充分理解(LS,LN)的含义；掌握各种情况下的结论不确定性的推理计算方法，熟记各种情况下的推理计算公式。9.证据理论又称D-S理论，是常用的第三种不确定性推理计算方法。要求充分了解与前两种不确定性推理方法在证据和结论表示方面的不同；理解概率分配函数、信任函数及似然函数的定义以及它们之间的相互关系；掌握概率分配函数正交和的计算方法；理解定义特定概率分配函数的意义，掌握基于该特定概率分配函数的不确定性推理方法，包括知识（规则）和证据的不确定性表示及结论不确定性的推理计算。第4页，本讲稿共98页命题逻辑命题逻辑智能信息处理与仪器研究室命题逻辑与谓词逻辑是最先应用于人工智能的两种逻辑，对于知识的形式化表示，特别是定理的自动证明发挥了重要作用。谓词逻辑是在命题逻辑的基础上发展起来的命题命题 定义定义1 能够分辨真假的语句能够分辨真假的语句,称做称做命题命题。定义定义2 一个语句如果不能再进一步分解成更简单的语句，并且本身是一个一个语句如果不能再进一步分解成更简单的语句，并且本身是一个 命题，则称此命题为命题，则称此命题为原子命题原子命题。原子命题是命题中的最基本的单位，一般用大写字母P、Q、R表示，而命题的真与假分别用“T”与“F”表示。命题一般是一个陈述句，如 太阳从东边升起，雪是白色的 (是命题)真漂亮啊！，请站起来！，你到哪里去？（不是命题）1+1=10 (条件命题，在二进制情况下)这盘菜太咸（是命题，但真假不能唯一确定，因人而异）第5页，本讲稿共98页命题公式命题公式智能信息处理与仪器研究室连接词连接词:在命题逻辑中用连接词将一些原子命题连接起来形成复合命题。在命题逻辑中用连接词将一些原子命题连接起来形成复合命题。：“非非”或或“否定否定”。：析取，表示两个连接的命题具有析取，表示两个连接的命题具有“或或”关系。关系。：合取，表示两个连接的命题具有合取，表示两个连接的命题具有“与与”关系。关系。：条件或蕴含，条件或蕴含，PQPQ表示表示P P蕴含蕴含Q,Q,即即“如果如果P P则则Q”,Q”,其中，其中，P P称为条件称为条件 的前件，的前件，Q Q称为条件的后件。称为条件的后件。：双条件，双条件，PQ表示表示“P当且仅当当且仅当Q”.表表1 命题逻辑真值表命题逻辑真值表P QPQPQPQPQP T T T F F T F FTTTFTFFFTFTTTFFTFFTT第6页，本讲稿共98页命题公式命题公式智能信息处理与仪器研究室定义定义3:以下面的递归形式给出命题公式的定义：以下面的递归形式给出命题公式的定义：原子命题是命题公式原子命题是命题公式 A A是命题公式，则是命题公式，则A A也也是命题公式。是命题公式。若若A和和B都是命题公式，则都是命题公式，则AB,AB,AB,AB,AB,AB,AB也都是命题公式也都是命题公式。只有按只有按得到的公式才是命题公式。得到的公式才是命题公式。命题公式就是按照上述规则由原子命题、连接词及圆括号所形成的字符串。有时也称命题公式就是按照上述规则由原子命题、连接词及圆括号所形成的字符串。有时也称命题演算公式。命题演算公式。连接词的优先级别为：连接词的优先级别为：,.,.命题逻辑虽然可以用来表示知识，但它有较大的局限性，无法把所描述的客观事命题逻辑虽然可以用来表示知识，但它有较大的局限性，无法把所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物的共同特征表示出来。物的结构及逻辑特征反映出来，也不能把不同事物的共同特征表示出来。张三是李四的老师，用张三是李四的老师，用P表示，反映不出关系。表示，反映不出关系。贝多芬是作曲家和柴可夫斯基是作曲家，用命题逻辑表示时，是作曲家的共同贝多芬是作曲家和柴可夫斯基是作曲家，用命题逻辑表示时，是作曲家的共同特征无法形式化表示出来。特征无法形式化表示出来。第7页，本讲稿共98页谓词逻辑谓词逻辑智能信息处理与仪器研究室谓词与个体谓词与个体 在谓词逻辑中，将原子命题分解为在谓词逻辑中，将原子命题分解为谓词谓词与与个体个体两部分。两部分。如，李白是诗人，如，李白是诗人，POET(LIBAI)53,GREATER(5,3)一元谓词：一个谓词与一个个体相关联。一元谓词：一个谓词与一个个体相关联。多元谓词：一个谓词与多个个体相关联。多元谓词：一个谓词与多个个体相关联。谓诩的一般形式：谓诩的一般形式：P(x1，x2，xn)其中其中P是谓词，是谓词，x1，x2，xn是个体，谓词通常用大写字母，个体用小写字母表是个体，谓词通常用大写字母，个体用小写字母表示。示。P(x)是一元谓词，是一元谓词，P(x,y)是二元谓词，是二元谓词，P(x1，x2，xn)是是N元谓词。元谓词。在谓词在谓词P(x1，x2，xn）中，若中，若x都是个体常量，变元或函数，称都是个体常量，变元或函数，称一阶谓词一阶谓词，如果如果x本身又是一个一阶谓词，则称本身又是一个一阶谓词，则称二阶谓词二阶谓词。第8页，本讲稿共98页谓词公式谓词公式智能信息处理与仪器研究室连接词连接词，与命题逻辑中的连接词相同，复合谓词公式的真值表同复合命题逻辑的，与命题逻辑中的连接词相同，复合谓词公式的真值表同复合命题逻辑的真值表。真值表。量词量词，全称量词（，全称量词（xx）,它表示它表示“对个体域中的所有（或任一个）个体对个体域中的所有（或任一个）个体x”x”存在量词（存在量词（xx）,它表示它表示“在个体域中存在个体在个体域中存在个体x”x”(x)(yx)(y)F(x,y):)F(x,y):个体域中的任何个体个体域中的任何个体x x都存在一个个体都存在一个个体y y，x x与与y y是朋友是朋友 (x)(y)F(x,y):个体域中的任何两个个体个体域中的任何两个个体x x和和y y，x x与与y y都是朋友都是朋友谓词演算公式谓词演算公式 定义4 谓词演算中，由单个谓词构成的不含任何连接词的公式，称为原子谓词公式谓词演算中，由单个谓词构成的不含任何连接词的公式，称为原子谓词公式,一般地一般地,形如形如F(x1,x2,xn)F(x1,x2,xn)的谓词公式称为原子谓词公式的谓词公式称为原子谓词公式,或简称为原子或简称为原子,其中其中F F为为n n元谓词元谓词,而而x1,x2,xnx1,x2,xn为个体变元为个体变元.第9页，本讲稿共98页谓词公式谓词公式智能信息处理与仪器研究室由原子谓词公式、连接词、量词及圆括号所组成的字符串，按由原子谓词公式、连接词、量词及圆括号所组成的字符串，按照上述规则构成谓词演算公式。照上述规则构成谓词演算公式。由原子公式的定义出发可定义谓词演算的合式公式如下：例如：第10页，本讲稿共98页谓词公式的永真性和可满足性谓词公式的永真性和可满足性智能信息处理与仪器研究室谓词公式的解释谓词公式的解释 定义定义：设：设D D为谓词公式为谓词公式P P的个体域，若对的个体域，若对P P中的个体常量、函数和谓词按照如下规定赋值：中的个体常量、函数和谓词按照如下规定赋值：为每个个体常量指派为每个个体常量指派D D中的一个元素中的一个元素;为每个为每个n n元函数指派一个从元函数指派一个从DnDn到到D D的映射，的映射，其中其中Dn=(x1,x2,xn)|Dn=(x1,x2,xn)|x1,x2,xnDD 为每个为每个n n元谓词指派一个从元谓词指派一个从DnDn到到F,TF,T的映射的映射.则称这些指派为公式则称这些指派为公式P P在在D D上的一个解释。上的一个解释。谓词公式的永真性谓词公式的永真性 定义定义：如果谓词公式：如果谓词公式P P对于个体域对于个体域D D上的任何一个解释都取得真值上的任何一个解释都取得真值T,T,则称则称P P在在D D上是永真的，如上是永真的，如是是P P在每个非空个体域上均永真，则称在每个非空个体域上均永真，则称P P永真。永真。定义：定义：如果谓词公式如果谓词公式P P对于个体域对于个体域D D上的任何一个解释都取得真值上的任何一个解释都取得真值F,F,则称则称P P在在D D上上是永假的，如是是永假的，如是P P在每个非空个体域上均永假，则称在每个非空个体域上均永假，则称P P永假。永假。谓词公式的永假性又称为不可满足性或不相容性。谓词公式的永假性又称为不可满足性或不相容性。第11页，本讲稿共98页谓词公式的永真性和可满足性谓词公式的永真性和可满足性智能信息处理与仪器研究室谓词公式的可满足性谓词公式的可满足性 定义定义：对于谓词公式对于谓词公式P,P,如果存在至少一个解释，使得公式如果存在至少一个解释，使得公式P P在此在此解释下的真值为解释下的真值为T,T,则称公式则称公式P P是可满足的。是可满足的。对谓词公式对谓词公式P，如果不存在任何解释使得，如果不存在任何解释使得P的取值的取值为为T则称公式则称公式P是不可满足的。不存在任何解释可是不可满足的。不存在任何解释可使使P的取值为的取值为T，即可理解为对于所有的解释都使公，即可理解为对于所有的解释都使公式式P取值为取值为F(因为谓词公式要么为因为谓词公式要么为T，要么为，要么为F)，谓，谓词公式词公式P永假与不可满足是等价的。若永假与不可满足是等价的。若P为永假，则为永假，则也可称也可称P不可满足的。不可满足的。第12页，本讲稿共98页智能信息处理与仪器研究室例例1第13页，本讲稿共98页谓词公式的等价性谓词公式的等价性智能信息处理与仪器研究室定义：设P与Q是两个谓词公式，D是它们共同的个体域，若对D上的任何一个解释，P与Q的取值都相同，则公式P和Q在域D上是等价的。如果D是任意个体域，则称P和Q是等价的，记做PQ.常用的等价式第14页，本讲稿共98页谓词公式的永真蕴含谓词公式的永真蕴含智能信息处理与仪器研究室定义：对于谓词公式P和Q,如果PQ永真，则称P永真蕴含Q,且称Q为P的逻辑结论，称P为Q的前提，记作PQ.一些永真蕴含式第15页，本讲稿共98页置换与合一置换与合一智能信息处理与仪器研究室 要使计算机模拟人类智能，就必须使计算机具有推理的功能，在用各种知识表示法对知识进行表示以后，这些知识就可以输入计算机了。在基于这些知识进行推理时，模式匹配是必须要进行的一项工作。因为只有经过模式匹配，才能从知识库中选出当前适用的知识，才能进行推理。例如，在产生式系统中，为了由已知的初始事实推出相应的结论，就必须从知识库中选出与初始事实相匹配的产生式规则，然后才能运用这些产生式规则进行推理，逐步推出结论。基于谓词逻辑的归结推理方法是一种确定性的推理方法，所以它所做的知识模式匹配也是一种确定性的匹配。为了使己知事实与知识库中的知识完全匹配，需要作某种变元置换，这里涉及到置换与合的有关概念及方法。第16页，本讲稿共98页置换置换智能信息处理与仪器研究室第17页，本讲稿共98页合一合一智能信息处理与仪器研究室第18页，本讲稿共98页智能信息处理与仪器研究室例例2第19页，本讲稿共98页智能信息处理与仪器研究室例例2第20页，本讲稿共98页智能信息处理与仪器研究室例例2第21页，本讲稿共98页归结推理方法归结推理方法智能信息处理与仪器研究室人工智能的目的之一就是使计算机能够模拟人的智能，解决实际中遇到的问题。研究自动定理证明，不仅使许多数学问题可以通过定理证明得以解决，而且可以使得许多如机器人规划等非数学的问题，归结为定理证明问题而得到解决。研究用计算机实现定理证明的机械化，已是人工智能研究的一个重要领域。对于定理证明问题，如果用一阶谓词逻辑表示的话就是要求对前提P和结论Q证明PQ是永真的。然而，要证明这个谓词公式的永真性必须对所有个体域上的每一个解释进行验证，这是极其困难的。为了化简问题，同数学上常采用的方法一样，可以考虑反证法。即，先否定逻辑结论Q，再由否定后的逻辑结论Q及前提条件P出发推出矛盾，即可证明原问题。换一句话说，为了证明PQ，只要从公式PQ中推出矛盾即可，也就是说，只要证明PQ是不可满足的即可。第22页，本讲稿共98页谓词公式与子句集谓词公式与子句集智能信息处理与仪器研究室 对于定理证明问题，最终可以通过一阶谓词逻辑表示为对于定理证明问题，最终可以通过一阶谓词逻辑表示为PPQ Q的不可满足性问题，这里前提条件的不可满足性问题，这里前提条件P P和结论和结论Q Q又都是以谓词公又都是以谓词公式表示的。当然，根据谓词公式的定义，式表示的。当然，根据谓词公式的定义，PPQ Q也是一个谓词公也是一个谓词公式。所以，要解决的问题是要证明谓词公式的不可满足性。然而，式。所以，要解决的问题是要证明谓词公式的不可满足性。然而，由于谓词公式的形式干变万化，给谓词演算的研究带来一定的困由于谓词公式的形式干变万化，给谓词演算的研究带来一定的困难。难。先介绍两种谓词演算公式的标准型，也就是范式。因而对谓词演算先介绍两种谓词演算公式的标准型，也就是范式。因而对谓词演算的研究就可以化归为对范式的研究。的研究就可以化归为对范式的研究。第23页，本讲稿共98页谓词公式与子句集谓词公式与子句集智能信息处理与仪器研究室第24页，本讲稿共98页谓词公式与子句集谓词公式与子句集智能信息处理与仪器研究室第25页，本讲稿共98页谓词公式与子句集谓词公式与子句集智能信息处理与仪器研究室第26页，本讲稿共98页谓词公式与子句集谓词公式与子句集智能信息处理与仪器研究室第27页，本讲稿共98页智能信息处理与仪器研究室例例3第28页，本讲稿共98页子句与子句集子句与子句集智能信息处理与仪器研究室 HerbrandHerbrand理论和理论和RobinsonRobinson的归结原理都是以子句集为背景开展研究的。的归结原理都是以子句集为背景开展研究的。第29页，本讲稿共98页不可满足意义下的一致性不可满足意义下的一致性智能信息处理与仪器研究室公式公式G与其子句集与其子句集S并不等值，但它们并不等值，但它们在不可满足的意义下是在不可满足的意义下是致的。致的。定理 设有谓词公式G，而其相应的子句集为S，则G是不可满足的充分必要条件是S是不可满足的。第30页，本讲稿共98页Herbrand理论理论智能信息处理与仪器研究室对于一个谓词公式来说，要证明它的不可满足性是困难的。对于一个谓词公式来说，要证明它的不可满足性是困难的。所以，需要考虑它的子句集的不可满足性。然而，对子句集所以，需要考虑它的子句集的不可满足性。然而，对子句集的不可满足性的判定仍然是困难的，因为要判断子句集的不的不可满足性的判定仍然是困难的，因为要判断子句集的不可满足性就要对于句集中的每一个子句逐个进行判定。由于可满足性就要对于句集中的每一个子句逐个进行判定。由于个体变元域个体变元域D D的任意性以及解释个数的无限性，这实际上是一的任意性以及解释个数的无限性，这实际上是一项难以完成的工作。能否针对某一个具体的谓词公式，找到项难以完成的工作。能否针对某一个具体的谓词公式，找到一个比较简单的特殊域，只要使谓词公式在该特殊域上是不一个比较简单的特殊域，只要使谓词公式在该特殊域上是不可满足的，就能保证它在任一域上也是不可满足的呢可满足的，就能保证它在任一域上也是不可满足的呢?HerbrandHerbrand理论构造了这样的一个域，称为理论构造了这样的一个域，称为Herbrand(HHerbrand(H域域)。只。只要对要对H H域上的所有解释进行判定域上的所有解释进行判定,即可得知谓词公式是否是不即可得知谓词公式是否是不可满足的。可满足的。第31页，本讲稿共98页Herbrand理论理论智能信息处理与仪器研究室第32页，本讲稿共98页Herbrand理论理论智能信息处理与仪器研究室第33页，本讲稿共98页Herbrand理论理论智能信息处理与仪器研究室第34页，本讲稿共98页智能信息处理与仪器研究室例例4第35页，本讲稿共98页智能信息处理与仪器研究室例例5第36页，本讲稿共98页智能信息处理与仪器研究室例例6第37页，本讲稿共98页智能信息处理与仪器研究室例例7第38页，本讲稿共98页智能信息处理与仪器研究室例例8第39页，本讲稿共98页Herbrand定理定理智能信息处理与仪器研究室第40页，本讲稿共98页消解原理（归结原理）消解原理（归结原理）智能信息处理与仪器研究室 Herbrand定理只是从理论上给出证明子句集不可满足性的可行性和方法。但要在计算机上实现其证明过程却是非常困难的。1965年，Robinson提出了归结原理,这是对自动推理的重大突破，使得机器定理证明变为现实。归结原理又称为消解原理，是Robinson提出的证明子句集不可满足性，从而实现了定理证明的一种理论和方法。子句集中各子句间的关系是合取关系，因此，只要有一个子句是不可满足的，则子句集就是不可满足的。另外，在前面已经指出，空子句是不可满足的，所以只要子句集中包含一个空子句，则此子句集就一定是不可满足的。Robinson的归结原理正是基于这一认识提出来的，其基本思想是：检查子句集S中是否有空子句，若有，则表明S是不可满足的；若没有，就在子句集中选择合适的子句对其进行归结推理，如果能推出空子句，就说明子句集S是不可满足的。第41页，本讲稿共98页命题逻辑中的归结原理命题逻辑中的归结原理智能信息处理与仪器研究室定义 若P是原子谓词公式或原子命题，则称P与P为互补文字互补文字。第42页，本讲稿共98页命题逻辑中的归结原理命题逻辑中的归结原理智能信息处理与仪器研究室第43页，本讲稿共98页命题逻辑中的归结原理命题逻辑中的归结原理智能信息处理与仪器研究室第44页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室第45页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室第46页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室第47页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：在谓词逻辑中，对子句进行归结推理时，要注意以下几个问题：第48页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室第49页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室第50页，本讲稿共98页一阶谓词逻辑中的归结原理一阶谓词逻辑中的归结原理智能信息处理与仪器研究室在命题逻辑推理中所结出的归结推理过程，在一阶谓词逻辑的在命题逻辑推理中所结出的归结推理过程，在一阶谓词逻辑的归结推理中仍然适用。归结推理中仍然适用。第51页，本讲稿共98页利用归结原理进行定理证明利用归结原理进行定理证明智能信息处理与仪器研究室第52页，本讲稿共98页利用归结原理进行定理证明利用归结原理进行定理证明智能信息处理与仪器研究室应用归结原理进行定理证明的步骤如下：第53页，本讲稿共98页应用归结原理进行问题求解应用归结原理进行问题求解智能信息处理与仪器研究室第54页，本讲稿共98页智能信息处理与仪器研究室例例9第55页，本讲稿共98页智能信息处理与仪器研究室例例10第56页，本讲稿共98页智能信息处理与仪器研究室例例11第57页，本讲稿共98页智能信息处理与仪器研究室例例12第58页，本讲稿共98页智能信息处理与仪器研究室例例13第59页，本讲稿共98页智能信息处理与仪器研究室例例13第60页，本讲稿共98页智能信息处理与仪器研究室例例13第61页，本讲稿共98页智能信息处理与仪器研究室例例14第62页，本讲稿共98页智能信息处理与仪器研究室例例14第63页，本讲稿共98页智能信息处理与仪器研究室例例14第64页，本讲稿共98页智能信息处理与仪器研究室例例15第65页，本讲稿共98页智能信息处理与仪器研究室例例15第66页，本讲稿共98页智能信息处理与仪器研究室例例15第67页，本讲稿共98页智能信息处理与仪器研究室例例15第68页，本讲稿共98页智能信息处理与仪器研究室例例16第69页，本讲稿共98页智能信息处理与仪器研究室例例16第70页，本讲稿共98页智能信息处理与仪器研究室例例16第71页，本讲稿共98页智能信息处理与仪器研究室例例16第72页，本讲稿共98页智能信息处理与仪器研究室例例16第73页，本讲稿共98页智能信息处理与仪器研究室例例16第74页，本讲稿共98页智能信息处理与仪器研究室例例16第75页，本讲稿共98页不确定推理不确定推理智能信息处理与仪器研究室 基于一阶谓词逻辑的归结推理方法所依据的证据是确定性的即谓词所表示的知识要么为“真”，要么为“假”，其推理过程也是以数理逻辑为基础推理过程是严密的，所推出的结论也是确定的，即结论要么成立，要么不成立。所以，基于一阶谓词逻辑的归结推理方法是一种确定性的推理方法。但是，在日常生活中。人们通常所遇到的情况是信息不够完善、不够精确，即所掌握的知识具有不确定性。人们就是运用这种不确定性的知识进行思维、推理、进而求解问题。所以，为了解决实际问题，必须对不确定知识的表示、推理过程等进行研究。第76页，本讲稿共98页不确定推理的概念不确定推理的概念智能信息处理与仪器研究室 所谓推理就是从已知事实出发，运用相关的知识(或规则)逐步推出结论或者证明某个假设成立或个成立的思维过程。其中，已知事实和知识(规则)是构成椎理的两个基本要素。巳知事实是推理过程的出发点及推理中使用的知识，将其称为证据，而知识(或规则)则是推理得以向前推进、并逐步达到最终目标的根据。个人工智能系统由总数据库、知识库和推理机构成。其中，总数数据库就是已知事实的集合，而知识库即是规则库，是一些人们总结的规则的集合，推理机则是由些推理算法构成，这些算法将依据知识库中的规则和总数据库中的事实进行推理计算。基中，知识库是人工智能系统的核心。由于现实世界中的事物以及事物之间的关系极其复杂，再加上客观上存在的随机性、模糊性以及某些事物或现象暴露的不充分性，从而导致了人们对它们认识的不精确和不完全，具有一定的不确定性。不确定性推理就是从具有不确定性的证据出发，运用不确定性的知识不确定性推理就是从具有不确定性的证据出发，运用不确定性的知识(或规则或规则)库中的知识，最终推出具有一定程度的不确定性，但却是合库中的知识，最终推出具有一定程度的不确定性，但却是合理的或近乎合理的结论的思维过程。理的或近乎合理的结论的思维过程。第77页，本讲稿共98页不确定推理方法的分类不确定推理方法的分类智能信息处理与仪器研究室模型方法模型方法:模型方法的特点是把不确定的证据和不确定的知识分别与某种度量标准对应起来，并给出更新结论不确定性的合适的算法，从而构成相应的不确定性推理模型。不同的结论不确定性更换算法就对应不同的模型。后面介绍的几种不确定性推理方法都属于模型法。控制方法控制方法:控制方法的特点是通过识别领域中引起不确定性的某些特征及相应的控制策略来限制或减少不确定性系统产生的影响，这类方法没有处理不确定性的统一模型，其效果极大地依赖于控制策略，控制策略的选择和研究是这类不确定性推理方法的关键：启发式搜索、相关性制导问题等是目前常见的几种控制制方法。第78页，本讲稿共98页不确定推理方法的分类不确定推理方法的分类智能信息处理与仪器研究室模型方法又分为模型方法又分为数值方法数值方法和和非数值方法非数值方法两大类两大类.数值方法是对不确定性的一种定量表示和处理方法，目前对它的研究数值方法是对不确定性的一种定量表示和处理方法，目前对它的研究及应用都比较多，形成了多种应用模型。它又可以按其所依据的理论及应用都比较多，形成了多种应用模型。它又可以按其所依据的理论不同分为基于概率的方法和模糊推理方法。基于概率的方法所依据的不同分为基于概率的方法和模糊推理方法。基于概率的方法所依据的理论是概率沦，而模糊推理方法所依据的理论则是模糊理论。理论是概率沦，而模糊推理方法所依据的理论则是模糊理论。非数值方法是指除数值方法外的其他各种处理不确定性的方法，它非数值方法是指除数值方法外的其他各种处理不确定性的方法，它又包括很多方法。逻辑法就是一种非数值方法，它采用多值逻辑、又包括很多方法。逻辑法就是一种非数值方法，它采用多值逻辑、非单调逻辑来处理不确定性。非单调逻辑来处理不确定性。第79页，本讲稿共98页三种不确定推理方法三种不确定推理方法智能信息处理与仪器研究室 在各类不确定性推理方法中，由于概率论有着完善的理论，同时还为不确定性的合成与传递提供了现成的公式，因而被用来表示和处理知识的不确定性，成为度量不确定性的重要手段。这种纯粹依靠概率模型来表示和处理不确定性的方法称为纯概率方法或概率方法。纯概率方法虽然有严密的理论依据，但它却要求给出事件的先验概率和条件概率，而这些数据又不易获得，因而使其应用受到限制。为此人们经过多年的研究，在概率沦的基础上，发展了一些新的处理不确定性的方法，这些方法包括：可信度方法可信度方法、主观主观BAYESBAYES方法方法和证据理论方证据理论方法法。第80页，本讲稿共98页可信度方法可信度方法智能信息处理与仪器研究室 可信度方法是美国斯坦福大学E.H.Shortliffe等人在确定性理论(Theory of confirmation)的基础上，结合概率论等提出的一种不确定性推理方法。1976年在专家系统MYCIN中首先应用，它是不确定推理方法中应用最早、且简单有效的方法之一。具有不确定性知识具有不确定性知识(规则规则)如何表示如何表示?不确定性的证据如何表示不确定性的证据如何表示?如何进行推理计算，即如何将证据的不确定性和知识的不确如何进行推理计算，即如何将证据的不确定性和知识的不确定性传递到结论定性传递到结论?第81页，本讲稿共98页可信度概念可信度概念智能信息处理与仪器研究室可信度是人们在实际生活中根据自己的经验或观察对某一事件或现象为可信度是人们在实际生活中根据自己的经验或观察对某一事件或现象为真的真的相信程度相信程度：例如，孙晓强昨天没来上课，他的理由是因为肚子疼，：例如，孙晓强昨天没来上课，他的理由是因为肚子疼，就此理由而言，只有以下两种可能：一种是孙晓强真的肚子疼了，即就此理由而言，只有以下两种可能：一种是孙晓强真的肚子疼了，即理由为真；另一种是孙晓强根本没有肚子疼，只是找个借口不来上课，理由为真；另一种是孙晓强根本没有肚子疼，只是找个借口不来上课，即理由为假。可信度也可以称做即理由为假。可信度也可以称做确定性因子确定性因子，在以产生式作为知识表，在以产生式作为知识表示的专家系统示的专家系统MYClNMYClN中，用以度量知识和证据的不确定性。显然，可中，用以度量知识和证据的不确定性。显然，可信度具有较大的主观性和经验性，其准确性是难以把握的。但是，对信度具有较大的主观性和经验性，其准确性是难以把握的。但是，对某一具体领域而言由于该领域专家具有丰富的专业知识及实践经验，某一具体领域而言由于该领域专家具有丰富的专业知识及实践经验，要给出该领域知识的可信度还是完全有可能的。另外，人工智能所面要给出该领域知识的可信度还是完全有可能的。另外，人工智能所面临的问题，较难用精确的数学模型进行描述，并且先验概率及条件概临的问题，较难用精确的数学模型进行描述，并且先验概率及条件概率的确定也比较困难，因此用可信度来表示知识及证据的不确定性仍率的确定也比较困难，因此用可信度来表示知识及证据的不确定性仍不失为一种可行的方法。不失为一种可行的方法。第82页，本讲稿共98页知识不确定性的表示知识不确定性的表示智能信息处理与仪器研究室 在基于可信度的不确定性推理模型中,知识是以产生式规则的形式表示的，知识的不确定性则是以可信度CF(H，E)表示的。其一般形式为 IF E THEN H (CF(H，E)其中：E E是知识的前提条件，或称为证据。它既可以是一个简单条件，也可以是用AND及OR把多个简单条件连接起来所构成的复合条件。例如，有 E=E1 AND E2 AND(E3 0R E4)H H是结论，它可以是一个单一的结论，也可以是多个结论。CF(H,E)CF(H,E)是该条知识的可信度,称为可信度因子(Certainty Factor)或规则强度.第83页，本讲稿共98页证据不确定性的表示证据不确定性的表示智能信息处理与仪器研究室 单个证据的不确定性获取方法 如果支持结论的证据只有一条，则证据可信度值的确定分两种情况。第一种情况是，证据为初始证据，其可信度的值一般由提供证据的用户直接指定，指定的方法也是用可信度因子对证据不确定性进行表示，例如 CF(E)0.8,表示证据E的可信度为0.8。第二种情况就是用先前推出的结论作为当前推理的证据，对于这种情况的证据，其可信度的值在推出该结论时通过不确定性传递算法计算得到。证据E的可信度CF(E)也是在-1,1上取值。第84页，本讲稿共98页证据不确定性的表示证据不确定性的表示智能信息处理与仪器研究室 组合证据的不确定性的获取方法 如果支持结论的证据有多个，那么这多个证据间的关系有可能是合取的关系，也可能是析取关系。这多个证据构成一个组合证据。当证据是多个单一证据的合取时，即 E=E1E2E3En 若El，E2，E3，En各证据的可信度分别为CF(E1)，CF(E2),CF(En)，则 CF(E)minCF(E1)，CF(E2),.CF(En)当证据是多个单一证据的析取时，即 E=E1E2E3En CF(E)minCF(E1)，CF(E2),.CF(En)第85页，本讲稿共98页不确定性的推理计算不确定性的推理计算智能信息处理与仪器研究室 不确定性的推理计算是从不确定的初始证据出发，通过运用相关的不确定性知识，最终推不确定性的推理计算是从不确定的初始证据出发，通过运用相关的不确定性知识，最终推出结沦并求出结论的可信度值。出结沦并求出结论的可信度值。只有单条知识支持结论时，结论可信度的计算方法只有单条知识支持结论时，结论可信度的计算方法 如果支持结论的知识只有一条，且已知证据的可信度CF(E)和规则(知识)IF E THEN H的可信度CF(H,E),则结论H的可信度计算公式如下：CF(H)CF(H，E)x Max0，CF(E)第86页，本讲稿共98页不确定性的推理计算不确定性的推理计算智能信息处理与仪器研究室多条知识支持同一结论时，结论不确定性的合成计算方法多条知识支持同一结论时，结论不确定性的合成计算方法 若由多条不同知识推出了相同的结论，但可信度不同，则可用合成算法求出结论的综合可信度。由于对多条知识的综合可通过两两的合成实现，所以下面只考虑两条知识的情况。设有如下知识：IF E1 THEN H (CF(H，E1)IF E2 THEN H (CF(H，E2)则结论H的综合可信度可分如下两步算出：(a)分别计算每条知识的结论可信度CF(H)：CF1(H)=CF(HE1)x Max0,CF(E1)CF2(H)=CF(H，E2)x Max0,CF(E2)b)用下式求出E1与E2对H的综合影响所形成的可信度CF1,2(H)：第87页，本讲稿共98页不确定性的推理计算不确定性的推理计算智能信息处理与仪器研究室这也是著名的专家系统这也是著名的专家系统MYCINMYCIN中所使用的结论不确定性计算公式。中所使用的结论不确定性计算公式。第88页，本讲稿共98页不确定性的推理计算不确定性的推理计算智能信息处理与仪器研究室在已知结论原始可信度的情况下，结论可信度的更新计算方法在已知结论原始可信度的情况下，结论可信度的更新计算方法 在某些情况下，如果已知证据E对结论H有影响，且知识IFE THEN H的可信度为CF(H,E)，同时结论H原来的可信度为CF(H)，那么如何求在证据E下结论H可信度的更新值CF(H/E)呢?即已知规则IF E THEN H(CF(H，E)及CF(H)，求CF(H/E)。这时分三种情况进行讨论:第89页，本讲稿共98页不确定性的推理计算不确定性的推理计算智能信息处理与仪器研究室第90页，本讲稿共98页不确定性的推理计算不确定性的推理计算智能信息处理与仪器研究室第91页，本讲稿共98页主观主观Bayes方法方法智能信息处理与仪器研究室 主观Bayes方法又称主观概率论，是内R0.Duda等人于1976年提出的一种不确定推理模型，它是对概率论中基本Bayes公式的改进，是一种基于概率逻辑的方法。该方法在地矿勘探专家系统PROSPECTOR中得到了成功的应用。由于主观Bayes方法是对概率论中基本Bayes公式的改进，所以在介绍主观Bayes不确定推理模型之前，先回顾一下概率论中的基本Bayes公式。第92页，本讲稿共98页Bayes公式公式智能信息处理与仪器研究室第93页，本讲稿共98页Bayes公式公式智能信息处理与仪器研究室第94页，本讲稿共98页Bayes公式公式智能信息处理与仪器研究室第95页，本讲稿共98页Bayes公式公式智能信息处理与仪器研究室第96页，本讲稿共98页智能信息处理与仪器研究室第97页，本讲稿共98页智能信息处理与仪器研究室证据理论证据理论证据理论又称D-S理论，是由A.P.Dempster首先提出，井由GShafer进一步发展起来的一种处理不确定性的理论。该理论满足比概率论弱的公理能够区分“不确定”与“不知道”的差异，并能处理由“不知道”引起的不确定性，具有较大的灵活性，因而受到人们的重视。由于涉及到较多数学基础知识，建议同学们课后找相关参考书自学。第98页，本讲稿共98页