人工智能幻灯片3

《人工智能幻灯片3》由会员分享，可在线阅读，更多相关《人工智能幻灯片3（60页珍藏版）》请在金锄头文库上搜索。

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

2、国逻辑学家刘易斯（C.I.Lewis）建立了模态命题逻辑；波兰的J.卢卡西维茨和美国的E.L.波斯特分别于1920和1921年建立了多值逻辑。,非经典逻辑，一般泛指与经典命题逻辑和经典谓词逻辑不同的那些逻辑。 非经典逻辑系统所使用形式语言与经典逻辑的语言基本相同，它们的差别在于经典逻辑系统中的某些定理，在这类逻辑中不再成立（即不再是定理）。 非经典逻辑大体上可以划分为两类：一类是与经典逻辑平行的逻辑，如直觉主义逻辑、多值逻辑和模糊逻辑。另一类是对经典逻辑进行扩充的逻辑，如模态逻辑、时态逻辑与动态逻辑。,3.1 经典推理和非经典推理,模态逻辑（Modal Logic）是逻辑学中最引人注目的一种非

3、经典逻辑，也是大部分非经典逻辑的基础。它不仅是程序语义描述的有力工具、时态逻辑和动态逻辑的理论基础，而且在知识的形式表示方面表现出极大的优越性。 模态逻辑主要是研究“必然”、“可能”、“不可能”和“偶然”等所谓“模态”概念的逻辑学说。,3.1.1 模态逻辑,3.1.1 模态逻辑,模态逻辑和经典二值逻辑一样，也分为命题逻辑与谓词逻辑两个层次：即模态命题逻辑和模态谓词逻辑两层次。 模态逻辑研究主要有三个方面的内容： 语法的研究 逻辑语义的研究 代数语义学的研究,前面所讨论的经典逻辑、模态逻辑等属于二值逻辑，即每一个命题皆取真假二值之一为值，每一命题或者真或者假。 如果更一般地来考查一个命题；使其不

4、限于只取“真”、“假”二值，而是可以取三值、四值、任意有限个值，乃至可数无穷多个值，那么，这种多值命题间的逻辑关系的研究就称之为多值逻辑。,3.1.2 多值逻辑,三值逻辑是最简单的多值逻辑，也是最重要的逻辑系统，以三值逻辑系统为背景可以更深入地了解多值逻辑系统的理论与应用。 克利恩（Kleene）三值逻辑系统K3 卢卡西维茨（Luckasiewicz）三值逻辑系统L3 波兹瓦（Bochvar）三值逻辑系统B,3.1.2 多值逻辑,人工智能研究的发展，迫使人们研究人的常识性推理的形式化问题。常识具有不确定性，一个常识可能具有众多的例外，一个常识可能是尚无理论根据或缺乏充分验证的经验，并且常识对环

5、境往往有极强的依存性。,3.1.3 非单调逻辑,例如“鸟是会飞的”。但有许多例外，如鸵鸟、死鸟就不会飞。由于常识的这种不确定，决定了常识推理的所谓非单调性，即依据常识进行通常的逻辑推理，但保留对常识的不确定性及环境的变迁造成的推理失误的修正权。,3.1.3 非单调逻辑,建立在谓词逻辑基础上的经典逻辑是单调的。在单调逻辑系统中，新的命题可以加入系统，新的定理可被证明，并且这种加入和证明决不会导致前面已知命题或已证明命题的无效。 单调逻辑不能完整地反应人类的思维过程和推理方式。,3.1.3 非单调逻辑,人类认识世界的过程是个否定之否定的辩证发展过程。由于人们对客观世界的认识不仅是不确定的，而且往往

6、是不完全的，新知识的出现往往在一定程度上否定、完善、或补充了旧的知识。所以人类的思维及推理行为本质上是非单调的。例如根据某些前提推出的某一结论，但当人们又获得另外一些事实后，却又取消这一结论。显然，结论并不随着条件的增加而增加，这种推理称为非单调的，相应的逻辑系统称为非单调逻辑系统。,3.1.3 非单调逻辑,3.1 经典推理与非经典推理,3.2 非单调推理,明斯基（Minsky）于1975年提出，并以“鸟会飞”为例加以说明。 非单调推理具有下列特征： 推理系统的定理集合不随推理过程的进行而单调增大； 新推理出的定理很可能会修正以至否定原有的一些定理，使得原来能够解释的一些现象变得不能解释。,3

7、.2 非单调推理,代表性研究工作： 赖特（Reiter）的缺省推理 穆尔（Moore）的自认识逻辑 麦卡锡（McCarthy）的界限推理 多伊尔（Doyle）的真值维护系统,3.2.1 缺省推理,定义：如果X不能在某个给定的时间内被证明，那么得结论Y。 在没有证据能够证明某命题不成立时，就承认该命题成立 。即尽管不具备该命题的全部知识，也能够进行合理的推理并给出正确的结论。 其核心是在默认或假设某些命题成立的前提下进行推理，也称为默认推理。,3.2.1 缺省推理,缺省推理规则的表达式为： 缺省规则的先决条件 缺省规则的默认条件 缺省规则的结论 M：模态算子，表示“假定是相容的”，即其否定不可证

8、明。,3.2.1 缺省推理,上式表示：如果先决条件 成立，而且默认条件 相容，即没有证据证明不成立 ，则可推出结论 成立。 缺省规则可用来表示推理知识，特别是对于像“大多数P是Q”、“大多数P具有性质Q”等类知识。如“一般来说，鸟会飞”可表示为：,20,3.2.1 缺省推理,缺省规则虽然可以表示模糊量词“几乎”、“大多数”等，但它却不涉及模糊逻辑。 缺省推理是非单调的，如果前面缺省的命题一旦加入系统，就必须消除用缺省推理产生的命题。,3.2.1 缺省推理,缺省规则的分类 规范缺省规则：由先决条件 成立一般可推出结论 成立 。 半规范缺省规则：除 外，由先决条件 的成立一般可推出结论 成立 。,

9、3.2.1 缺省推理,不规范缺省规则：凡是不属于前两类的缺省规则。 另一分类 封闭式：在缺省规则中不含自由变元 重言式：先决条件为空 演绎规则：如果默认条件为空，则退化为演绎规则,3.2.2 限定推理,麦卡锡在20世纪70年代末提出的，在经典逻辑的框架内研究适合于表示非单调性的特殊推理形式。 核心思想“Occam剃刀”原理 如果一个句子叙述一个命题，那么它叙述的仅仅是这个命题，一点也不能扩展。 麦卡锡提出的“Occam剃刀”原理叫做极小模型,3.2.2 限定推理,存在问题 麦卡锡等是用极小模型概念来描述谓词限定及领域限定的，而极小模型并不总是存在的； 限定谓词的选择，限定理论没有批出应当对哪一

10、个谓词进行限定，而对谓词的不同限定往往会取得不同的结果。,3.2.3真值维持系统,维持推理的一致性 实现非单调推理系统的核心技术之一。 把一个非单调推理系统的信念集（常识集）分为两个部分，即 。其中 为基本信念集；A为假设集，可视为对 的尝试性扩充。鉴于推理系统视 为永真，因而推理中产生的不一致仅由引入不适当的假设引起。 真值维持系统（TMS）是服务于维持推理一致性的有效技术。,3.2.3真值维持系统,真值维持系统（TMS）最早由多伊尔（Doyle）于1979年建立 。 TMS是一个已经实现了的非单调推理系统，用以协助其它推理程序维持系统的正确性。它的作用不是产生新的推理，而是在其他程序所产生

11、的命题之间保持相容性。一旦发现某个命题不相容，它就调出自己的推理机制，面向从属关系的回溯，并通过修改最小的信念集来消除不相容。,3.2.3真值维持系统,TMS的作用原理 TMS中每个知识单元都是一个信念，每个信念都有其正面或反面的证据。在推理过程中论据发生了变化，信念也随之发生变化。,推理机,真值维持系统,知识库,论据变化,获取信息,修改信息,3.3 时序推理,由艾伦（Allen）提出的一种表示时间知识和进行时间区间推理的方法，能够处理事件之间的时序关系。 时序推理不是建立在逻辑基础上的，消除了一阶逻辑的局限性，具有较大的实用价值。,3.4 不确定性推理,一种建立在非经典逻辑基础上的基于不确定

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

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

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

15、性 和规则的强度 ，其中H表示假设，试求H的不确定性 。即,3.4.2 不确定性的算法,并行规则算法：根据独立的证据 和 ，分别求得假设 H的不确定性为 和 。求出证据 和 的组合导致结论H的不确定性 ，即,3.4.2 不确定性的算法,组合证据的不确定性算法 证据合取的不确定性算法：根据2个证据 和 的确定性值 ，求出证据 和 合取的不确定性。即： 证据析取的不确定性算法：根据2个证据 和 的确定性值 ，求出证据 和 析取的不确定性。即：,3.4.2 不确定性的算法,组合证据不确定性计算中常用算法 最大最小法 概率方法 有界方法,3.5 概率推理,概率推理 设有如下产生式规则 则证据或前提条件

16、E不确定性的概率为P（E），概率推理的目的就是求出在证据E下结论H发生的概率 。,3.5 概率推理,采用贝叶斯方法进行推理 已知前提E的概率 和H的先验概率 ，并已知H成立时E出现的条件概率 ，则：,3.5 概率推理,若一个证据E支持多个假设 则贝叶斯公式为 若有多个证据和多个结论，则有,3.5 概率推理,例：设 为三个结论，E是支持这些结论的证据，已知： 则 说明随着证据E的出现， 成立的可能性略有增加，而 成立的可能性却略有降低。,3.5 概率推理,在原来证据 的基础上，增加另一个证据 ，已知： 则,由于E1和E2的出现，使得H2、H1的可能性增大，H3的可能性下降。,实际应用中，不容易获知“结论 的先验概率 及证据E的条件概率 杜达、哈特等人在贝叶斯公式的基础上，于19