人工智能课件3.ppt

1、人工智能及其应用 第三章第三章 高级知识推理高级知识推理 目录 经典推理和非经典推理经典推理和非经典推理 非单调推理非单调推理 A A* *算法算法 消解原理消解原理 规则演绎系统规则演绎系统 产生式系统产生式系统 系统组织技术系统组织技术前言 客观事物存在随机性随机性、模糊性模糊性、不完全性不完全性和不不精确性精确性，若采用精确推理方法，必然无法反映事物的真实性。 在不完全和不确定的情况下需要运用不确定知识进行推理，即不确定性推理不确定性推理。 求解过程中得到的有关问题的结论如不随知识的增加而单调增加，则需采用非单调推理非单调推理。3.1 经典推理和非经典推理 经典逻辑：传统的命题逻辑、谓词

2、逻辑 非经典逻辑：突破经典逻辑范畴的其他逻辑经典逻辑自古以来早就有之，而现代非经典逻辑的研究则始于1910年。最早提出和创立的非经典逻辑系统，是美国逻辑学家刘易斯（C.I.Lewis）建立了模态命题逻辑；波兰的J.卢卡西维茨和美国的E.L.波斯特分别于1920和1921年建立了多值逻辑。 非经典逻辑，一般泛指与经典命题逻辑和经典谓词逻辑不同的那些逻辑。 非经典逻辑系统所使用形式语言与经典逻辑的语言基本相同，它们的差别在于经典逻辑系统中的某些定理，在这类逻辑中不再成立（即不再是定理）。 非经典逻辑大体上可以划分为两类：一类是与经与经典逻辑平行的逻辑典逻辑平行的逻辑，如直觉主义逻辑、多值逻辑和模糊

3、逻辑。另一类是对经典逻辑进行扩充对经典逻辑进行扩充的逻辑的逻辑，如模态逻辑、时态逻辑与动态逻辑。 3.1 经典推理和非经典推理 模态逻辑（Modal Logic）是逻辑学中最引人注目的一种非经典逻辑，也是大部分非经典逻辑的基础。它不仅是程序语义描述的有力工具、时态逻辑和动态逻辑的理论基础，而且在知识的形式表示方面表现出极大的优越性。 模态逻辑主要是研究“必然”、“可能”、“不可能”和“偶然”等所谓“模态”概念的逻辑学说。 3.1.1 模态逻辑3.1.1 模态逻辑 模态逻辑和经典二值逻辑一样，也分为命题逻辑与谓词逻辑两个层次：即模态命题逻辑模态命题逻辑和模模态谓词逻辑态谓词逻辑两层次。 模态逻辑

4、研究主要有三个方面的内容： 语法的研究 逻辑语义的研究 代数语义学的研究 前面所讨论的经典逻辑、模态逻辑等属于二值逻辑，即每一个命题皆取真假二值之一为值，每一命题或者真或者假。 如果更一般地来考查一个命题；使其不限于只取“真”、“假”二值，而是可以取三值、四值、任意有限个值，乃至可数无穷多个值，那么，这种多值命题间的逻辑关系的研究就称之为多值逻辑多值逻辑。 3.1.2 多值逻辑 三值逻辑是最简单的多值逻辑，也是最重要的逻辑系统，以三值逻辑系统为背景可以更深入地了解多值逻辑系统的理论与应用。 克利恩（Kleene）三值逻辑系统K3 卢卡西维茨（Luckasiewicz）三值逻辑系统L3 波兹瓦（

5、Bochvar）三值逻辑系统B 3.1.2 多值逻辑 人工智能研究的发展，迫使人们研究人的常识性推理的形式化问题。常识具有不确定性，一个常识可能具有众多的例外，一个常识可能是尚无理论根据或缺乏充分验证的经验，并且常识对环境往往有极强的依存性。3.1.3 非单调逻辑 例如“鸟是会飞的”。但有许多例外，如鸵鸟、死鸟就不会飞。由于常识的这种不确定，决定了常识推理的所谓非单调性，即依据常识进行通常的逻辑推理，但保留对常识的不确定性及环境的变迁造成的推理失误的修正权。 3.1.3 非单调逻辑 建立在谓词逻辑基础上的经典逻辑是单调的。在单调逻辑系统中，新的命题可以加入系统，新的定理可被证明，并且这种加入和

6、证明决不会导致前面已知命题或已证明命题的无效。 单调逻辑不能完整地反应人类的思维过程和推理方式。3.1.3 非单调逻辑 人类认识世界的过程是个否定之否定的辩证发展过程。由于人们对客观世界的认识不仅是不确定的，而且往往是不完全的，新知识的出现往往在一定程度上否定、完善、或补充了旧的知识。所以人类的思维及推理行为本质上是非单调的。例如根据某些前提推出的某一结论，但当人们又获得另外一些事实后，却又取消这一结论。显然，结论并不随着条件的增加结论并不随着条件的增加而增加，这种推理称为非单调的，相应的逻辑而增加，这种推理称为非单调的，相应的逻辑系统称为非单调逻辑系统系统称为非单调逻辑系统。3.1.3 非单

7、调逻辑3.1 经典推理与非经典推理经典逻辑经典逻辑非经典逻辑非经典逻辑推理方法演绎逻辑推理归纳逻辑推理辖域取值二值逻辑（T or F）多值逻辑运算法则经典逻辑中的运算法则在非经典逻辑中不适用，如狄摩根定理等。逻辑算符只能进行是非判断，答案是唯一的，即“真”或“假”附加算符（模态算符）来处理“什么可能真”、“什么允许假”等问题是否单调单调的，即已知事实均为充分可信的，不会随着新事实的出现而使原有事实为假。非单调的，当人们对客观情况的认识有了深化时，一些旧的认识可能被修正以至否定。3.2 非单调推理 明斯基（Minsky）于1975年提出，并以“鸟会飞”为例加以说明。 非单调推理具有下列特征： 推

8、理系统的定理集合不随推理过程的进行而单调增大； 新推理出的定理很可能会修正以至否定原有的一些定理，使得原来能够解释的一些现象变得不能解释。3.2 非单调推理 代表性研究工作： 赖特（Reiter）的缺省推理 穆尔（Moore）的自认识逻辑 麦卡锡（McCarthy）的界限推理 多伊尔（Doyle）的真值维护系统3.2.1 缺省推理 定义：如果X不能在某个给定的时间内被证明，那么得结论Y。 在没有证据能够证明某命题不成立时，就承认该命题成立 。即尽管不具备该命题的全部知识，也能够进行合理的推理并给出正确的结论。 其核心是在默认或假设某些命题成立的前提下进行推理，也称为默认推理默认推理。3.2.1

9、 缺省推理 缺省推理规则的表达式为： 缺省规则的先决条件 缺省规则的默认条件 缺省规则的结论 M：模态算子，表示“假定是相容的”，即其否定不可证明。1( ):( ),( )( )nA xMB xMB xC x( )A x( )B x( )C x3.2.1 缺省推理 上式表示：如果先决条件 成立，而且默认条件 相容，即没有证据证明不成立 ，则可推出结论 成立。 缺省规则可用来表示推理知识，特别是对于像“大多数P是Q”、“大多数P具有性质Q”等类知识。如“一般来说，鸟会飞”可表示为：( )A x( )B x( )C x( ):( )( )Bird xMFly xFly x3.2.1 缺省推理 缺省

10、规则虽然可以表示模糊量词“几乎”、“大多数”等，但它却不涉及模糊逻辑。 缺省推理是非单调的，如果前面缺省的命题一旦加入系统，就必须消除用缺省推理产生的命题。203.2.1 缺省推理 缺省规则的分类 规范缺省规则：由先决条件 成立一般可推出结论 成立 。 半规范缺省规则：除 外，由先决条件 的成立一般可推出结论 成立 。( )A x( )B x( )D x( )A x( )C x( ):( )( )A xB xB x( ):( ( )( )( )A xM C xD xC x 3.2.1 缺省推理 不规范缺省规则：凡是不属于前两类的缺省规则。 另一分类 封闭式：在缺省规则中不含自由变元 重言式：先

11、决条件为空 演绎规则：如果默认条件为空，则退化为演绎规则3.2.2 限定推理 麦卡锡在20世纪70年代末提出的，在经典逻辑的框架内研究适合于表示非单调性的特殊推理形式。 核心思想“Occam剃刀”原理 如果一个句子叙述一个命题，那么它叙述的仅仅是这个命题，一点也不能扩展。 麦卡锡提出的“Occam剃刀”原理叫做极小极小模型模型3.2.2 限定推理 存在问题 麦卡锡等是用极小模型概念来描述谓词限定及领域限定的，而极小模型并不总是存在的； 限定谓词的选择，限定理论没有批出应当对哪一个谓词进行限定，而对谓词的不同限定往往会取得不同的结果。3.2.3真值维持系统 维持推理的一致性 实现非单调推理系统的

12、核心技术之一。 把一个非单调推理系统的信念集（常识集）分为两个部分，即 。其中 为基本信念集；A为假设集，可视为对 的尝试性扩充。鉴于推理系统视 为永真，因而推理中产生的不一致仅由引入不适当的假设引起。 真值维持系统（TMS）是服务于维持推理一致性的有效技术。SA 3.2.3真值维持系统 真值维持系统（TMS）最早由多伊尔（Doyle）于1979年建立 。 TMS是一个已经实现了的非单调推理系统，用以协助其它推理程序维持系统的正确性。它的作用不是产生新的推理，而是在其他程序所产生的命题之间保持相容性。一旦发现某个命题不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消

13、除不相容。3.2.3真值维持系统 TMS的作用原理 TMS中每个知识单元都是一个信念，每个信念都有其正面或反面的证据。在推理过程中论据发生了变化，信念也随之发生变化。推理机推理机真值维持系统真值维持系统知识库知识库论据变化获取信息修改信息3.3 时序推理 由艾伦（Allen）提出的一种表示时间知识和进行时间区间推理的方法，能够处理事件之间的时序关系。 时序推理不是建立在逻辑基础上的，消除了一阶逻辑的局限性，具有较大的实用价值。3.4 不确定性推理 一种建立在非经典逻辑基础上的基于不确定性知识的推理。 目的：根据用户提供的初始证据，通过运用不确定性知识，最终推理出不确定性的结论，并推算出结论为确

14、定性的程度。3.4.1 不确定性的表示与度量 不确定性的表示 知识不确定性的表示：需要考虑2个直接相关的因素： 能根据领域问题特征把其不确定性比较准确地描述出来，满足问题求解的需要； 便于推理过程中推算不确定性。 在专家系统中，用“知识的表态强度知识的表态强度”表示相应知识的不确定性程度，它可以是知识在应用中成功的概率，也可以是知识的可信度，一般由领域专家给出。3.4.1 不确定性的表示与度量 证据不确定性的表示 观察事物产生的不确定性导致证据的不确定性。 有2种来源的证据： 用户在求解问题时提供的初始证据 在推理中用前面推出的结论作为当前推理的证据。 证据强度：表示相应证据的不确定性程度。对

15、于初始证据，其值由用户给出；对于推理中产生的证据，由推理的不确定传递算法计算得到。3.4.1 不确定性的表示与度量 结论不确定性的表示 由于使用知识和证据具有不确定性，导致结论也具有不确定性。 也称为规则的不确定性，表示当规则的条件完全满足时，产生某种结论的不确定性程度。3.4.1 不确定性的表示与度量 不确定性的度量 明确取值范围，如-1，1或0，1。 确定量度方法和范围时，须注意： 量度要能充分表达相应知识和证据不确定性的程度。 量度范围的指定应便于领域专家和用户对不确定性的估计。 量度要便于对不确定性的传递进行计算。 量度的确定应当是直观的，并有相应的理论依据。3.4.2 不确定性的算法

16、 不确定性的匹配算法 推理是一个不断运用知识的过程，为了找到所需的知识，需要在这一过程中用知识的前提条件与已知证据进行匹配，只有匹配成功的知识才能可能被应用。 在不确定性推理中，存在“如何才算匹配成功”这一问题。目前常用的解决方法是：设计一个用来计算匹配双方相似程度的算法，再指定一个相似的限度，用来衡量匹配双方相似的程度是否落在指定的限度内。这个限度称为阈值。3.4.2 不确定性的算法 不确定性的更新算法：解决“知识不确定性的动态积累和传递”，算法如下： 已知规则前提已知规则前提：已知证据E的不确定性 和规则的强度 ，其中H表示假设，试求H的不确定性 。即( )C E(,)f H E()C H

17、1()(),(,)C Hg C Ef H E3.4.2 不确定性的算法 并行规则算法并行规则算法：根据独立的证据 和 ，分别求得假设 H的不确定性为 和 。求出证据 和 的组合导致结论H的不确定性 ，即1E212()(),()C HgCHCH2E1()C H2()C H1E2E3.4.2 不确定性的算法 组合证据的不确定性算法 证据合取的不确定性算法证据合取的不确定性算法：根据2个证据 和 的确定性值 ，求出证据 和 合取的不确定性。即： 证据析取的不确定性算法证据析取的不确定性算法：根据2个证据 和 的确定性值 ，求出证据 和 析取的不确定性。即：1E2E1E2E1E2E1E2E12312(

18、)(),()C E AND EgC EC E12412()(),()C E OR EgC EC E3.4.2 不确定性的算法 组合证据不确定性计算中常用算法 最大最小法 概率方法 有界方法12121212()min(),()()max(),()C E AND EC EC EC E OR EC EC E1212121212()()()()()()()()C E AND EC E C EC E OR EC EC EC E C E12121212()max0,()()1()min1,()()C E AND EC EC EC E OR EC EC E3.5 概率推理 概率推理 设有如下产生式规则 则证

19、据或前提条件E不确定性的概率为P（E），概率推理的目的就是求出在证据E下结论H发生的概率 。IFETHENH()P H E3.5 概率推理 采用贝叶斯方法进行推理 已知前提E的概率 和H的先验概率 ，并已知H成立时E出现的条件概率 ，则：()P E()P H()P E H()()()()P E H P HP H EP E3.5 概率推理 若一个证据E支持多个假设则贝叶斯公式为 若有多个证据和多个结论，则有(1,2,)iIFETHENHin12,nHHH1()()()(1,2,)()()iiinjjjP E HP HP HEinP HP E H111()()()()()()()imiiimnjm

20、jjjP E HP EHP HP HEEP E HP EHP H3.5 概率推理 例：设 为三个结论，E是支持这些结论的证据，已知： 则 说明随着证据E的出现， 成立的可能性略有增加，而 成立的可能性却略有降低。123,HHH123123()0.3,()0.4,()0.5()0.5,()0.3,()0.4P HP HP HP E HP E HP E H123()0.32,()0.26,()0.46P HEP HEP HE1H23,HH3.5 概率推理 在原来证据 的基础上，增加另一个证据 ，已知： 则123112233212233()0.3,()0.4,()0.5()0.5,()0.6,()0

21、.3()0.7,()0.9,()0.1P HP HP HP E HP EHP EHP EHP EHP EH112212312()0.313()0.643()0.045P HE EP HE EP HE E由于由于E1和和E2的出的出现，使得现，使得H2、H1的可能性增大，的可能性增大，H3的可能性下降。的可能性下降。1E2E 实际应用中，不容易获知“结论 的先验概率 及证据E的条件概率 杜达、哈特等人在贝叶斯公式的基础上，于1976年提出主观贝叶斯方法，建立了不精确推理模型，并把它成功应用于PROSPECTOR专家系统（地矿勘察）。3.6 主观贝叶斯方法iH()iP H()iP HE 主观贝叶斯

22、方法的不精确推理过程就是根据前提E的概率 ，利用规划的充分性因子LS和必要性因子LN，把结论H的先验概率 更换为后验概率 的过程。3.6 主观贝叶斯方法()P E()iP HE()P H 知识表示方法 表示知识的静态强度 LS为上式成立的充分性因子，衡量证据E对结论H的支持程度3.6.1 知识不确定性的表示(,)IFETHENLS LNH(,)LS LN()()P E HLSP EH LN为上式成立的必要性因子。衡量证据E对结论H的支持程度 LS、LN的取值范围为 ，其具体数值由领域专家决定 。3.6.1 知识不确定性的表示()1()()1()PE HP E HLNPEHP EH0,) 定义概

23、率函数 上式表示X的几率的几率等于X出现的概率与X不出现的概率之比。3.6.1 知识不确定性的表示()()()1()()P XP XO XP XPX0,()0(),()1P XO XP X 则有 修改后的贝叶斯公式为修改后的贝叶斯公式为：3.6.1 知识不确定性的表示()()()()P E HO H EO HP EH()()()()O H ELS O HO HELN O H证据证据E为真为真证据证据E为假为假 知识的动态强度：对于初始证据E，用户根据观察S给出的 。 由于难以给出 ，在具体应用中引入可信度 ，表示对所提供证据可以相信的程序。3.6.2 证据不确定性的表示()P E S()C E

24、 S()P E S 当采用初始证据进行推理时，通过提问用户得到 ，通过CP公式可求出 3.6.2 证据不确定性的表示()1() ( )() () 1()051( ) ()( )()()05P H SP HEP HP HEC E SC E SP HP H EP HC E SC E S()C E S()P H S 当采用推理过程中得到的中间结论作为证据进行推理时，通过EH公式可求得3.6.2 证据不确定性的表示()( )()()() 0()( )( )()( )( ) ()( )( )() 11( )P H SP HP HEP HEP E SP E SP EP EP H EP HP HP E SP

25、 EP EP E SP E()P H S 如果有n条知识都支持同一结论H，而且每条知识的前提条件分别是n个相互独立的证据 E1，E2，En，而这些证据又分别与观察S1，S2，Sn相对应，这时，首先对每条知识分别求出H的后验几率 ，然后按下述公式求出所有观察下H的后验几率。3.6.2 证据不确定性的表示()iO H S1212()()()(,)( )( )( )( )nnO H SO H SO H SO H S SSO HO HO HO H P99例例3.4 主观贝叶斯法的优点 计算公式是在概率论的基础上推导而来，具有比较坚实的理论基础。 规则的充分性因子（LS）和必要性因子（LN）比较全面地反

26、映了证据和结论间的因果关系，使推出的结论具有比较准确的确定性。 该方法实现了不确定性的逐级传递，是一种比较实用而又灵活的不确定性推理方法3.6.3 优缺点 主观贝叶斯法的缺点 要求领域专家给出规则的同时，给出H的先验概率 ，实现起来比较困难。 贝叶斯公式成立的前提是证据E之间相互独立，使该方法的应用受到一定限制。3.6.3 优缺点()P H 肖特里菲（Shortliffe）等人在确定性理论基础上结合概率论等理论提出的一种不精确推理模型。 可信度：根据经验对一个事物或现象为真的可信度：根据经验对一个事物或现象为真的相信程度。相信程度。 该方法计算简单，具有一个合理而有效的推理模式，因此在专家系统

27、（MYCIN）等领域获得较广泛的应用。3.7 可信度方法 由德普斯特（Dempster）提出，并由沙沸（Shafer）进一步发展起来，简称D-S理论。 1981年，巴纳特（Barnett）把该理论引入专家系统中，同年，卡威（Garvey）等人用它实现了不确定性推理。 D-S理论只需满足比概率论更弱的公理系统，而且能处理由“不知道”引起的不确定性。3.8 证据理论 D-S理论主要优点： 只需满足比概率论更弱的公理系统，而且能处理由“不知道”引起的不确定性。 领域专家可从不同的语义层次上表达他们的知识，而不必限制在由单元素所表示的最明确的层次上。3.8 证据理论 D-S理论主要缺点： 要求D中元素满足互斥条件，对于实际系统难以实现。 需要给出的概率分配数太多，计算比较复杂。3.8 证据理论