小C的第一宇宙
1 确定性知识系统
wangc
Nov 2, 2017
阅读本文需要 23 分钟(按字数)

按照符号主义的观点，知识是一切智能行为的基础，要使机器具有智能，就必须使它拥有并可以使用知识。但在现有条件下，人们日常使用的、用自然语言描述的知识，计算机还不能直接识别，因此要使计算机拥有知识，首先必须用一定方法将知识表示出来。至于知识的使用，实际上是一个知识推理过程。根据知识的确定化程度，知识表示和推理方法可分为确定性和不确定性两大类。本章主要讨论前一类，后一类将在后面章节讨论。

什么是知识系统

知识系统是一种拥有知识并且可以使用知识进行推理的智能系统。知识系统的构建涉及两大基本技术，一是知识表示，二是知识推理。

知识表示

知识的概念可以从两个方面来讨论，一是知识的定义，二是知识的类型。一种普遍的观点认为，知识是人们在改造客观世界的实践中积累起来的认识和经验。 按知识的确定性分知识可分为确定性知识和不确定性知识。确定性知识是可以给出其真值为“真”或“假”的知识。这些知识是可以精确表示的知识。不确定性知识是指具有“不确定”特性的知识，这种不确定特性包括不完备性、不精确性和模糊性。

关于知识…

知识推理

人工智能的推理研究，就是要基于人类的思维机理，去实现机器的自动推理。除推理的思维机理外，它包括两个基本问题，一是推理的方法，二是推理的控制策略。常见的推理方法有，演绎推理，归纳推理等。推理过程不仅依赖于所用的推理方法，也依赖于推理的控制策略。推理的控制策略是指如何使用领域知识使推理过程尽快达到目标的策略。

关于推理…

确定性知识系统

表示方法

谓词逻辑表示法

简介

谓词逻辑不仅可以用来表示事物的状态、属性、概念等事实性知识，也可以用来表示事物的因果关系，即规则。对事实性知识，通常是用否定、析取或合取符号连接起来的谓词公式表示。对事物间的因果关系，通常用蕴涵式表示，例 如，对“如果x，则 y ’可表示为“x—>y’。 当用谓词逻辑表示知识时，首先需要根据所表示的知识定义谓词，然后再用连接词或量词把这些谓词连接起来，形成一个谓词公式。 例 2.1 用谓词逻辑表示知识“所有教师都有自己的学生”。 解： 首先定义谓词:

  • TEACHERU(x):表示x是教师。
  • STUDENT(y):表示y是学生。
  • TEACHESU，表示x是y的老师。 此时，该知识可用谓词表示为 (∀x)(∃y)(TEACHER(x)—>TEACHESU(x,y)ΛSTUDENT(y)) 该谓词公式可读为:对所有x，如果x是一个教师，那么一定存在一个个体y，x是y的老师，且y是一个学生。

    实例

    例2.4设在一房间里，c处有一个机器人，a和b处各有一张桌子，分别称为a桌和 b桌上，a桌上有一盒子，如图2.1所示。要求机器人从c处出发把盒子从a桌上拿 到b桌上，然后再回到c处。请用谓词逻辑来描述机器人的行动过程。 image

    1. 定义谓词：
    • TABLE(x)：x是桌子。
    • EMPTY(y)：y手中是空的。
    • AT(y,z)：y在z处。
    • HOLDS(y,w)：y拿着w。
    • ON(w,x)：w在x桌面上。 其中，X的个体域是{a,b};y的个体域是{robot}，z的个体域是{a,b,c}，w的个体域是{box}。
      1. 初末状态 问题的初始状态
    • AT(robot,c)
    • EMPTY(robot)
    • ON(box,a)
    • TABLE(a)
    • TABLE(b) 问题的目标状态
    • AT(robot,c)
    • EMPTY(robot)
    • ON (box,b)
    • TABLE(a)
    • TABLE(b)
      1. 基本操作
    • GOTO(x,y):从x处走到处。
    • PICKUP(x):在x处拿起盒子。
    • SETDOWN(x):在x处放下盒子。
      1. 问题解决 image

        特性

        逻辑知识表示的主要特点是建立在一阶逻辑的基础上，并利用逻辑运算方法研究推理的规律，即条件与结论之间的蕴涵关系。逻辑表示法的主要优点如下。

      2. 自然。一阶谓词逻辑是一种接近于自然语言的形式语言系统，谓词逻辑表示法接近于人们对问题的直观理解，易于被人们接受。
      3. 明确。逻辑表示法对如何由简单陈述句构造复杂陈述句的方法有明确规定，如联结词、量词的用法与含义等。对于用逻辑表示法表示的知识，人们都可以按照一种标准的方法去解释它，因此用这种方法表示的知识明确、易于理解。
      4. 精确。谓词逻辑是一种二值逻辑，其谓词公式的真值只有“真”与“假”，因此可用来表示精确知识，并可保证经演绎推理所得结论的精确性。
      5. 灵活。逻辑表示法把知识和处理知识的程序有效地分开。在使用这种方法表示知识时，无须考虑程序中处理知识的细节。
      6. 模块化。在逻辑表示法中，各条知识都是相对独立的，它们之间不直接发生联系。因此添加、删除、修改知识的工作比较容易进行。 逻辑表示法也存在一些不足，其主要缺点如下。
      7. 知识表示能力差。逻辑表示法只能表示确定性知识，而不能表示非确定性知识，如不精确 、模糊性知识。实际上，人类的大部分知识都不同程度地具有某种不确定性，这就使得它表示知识的范围和能力受到了一定的限制。另外，逻辑表示法还难以表示过程性知识和启发性知识。
      8. 知识库管理困难。逻辑表示法缺乏知识的组织原则，利用这种表示法所形成的知识库管理比较困难。
      9. 存在组合爆炸。由于逻辑表示法难以表示启发性知识，因此在推理过程中只能盲目地使用推理规则。这样，当系统知识量较大时，容易发生组合爆炸。
      10. 系统效率低。逻辑表示法的推理过程是根据形式逻辑进行的。它把推理演算与知识含义截然分开，拋弃了表达内容中所含有的语义信息，往往使推理过程冗长，降低了系统效率。

产生式表示方法

简介

产生式(production)这 一 术 语 是 1943年 由美国数学家波斯特（ E.Post)首次提出并使用的。到1972年，纽厄尔和西蒙在研究人类的认知模型中开发了基于规则的产生式系统。目前，产生式表示法已成为人工智能中应用最多的一种知识表示模式，尤其是在专家系统方面，许多成功的专家系统都是采用产生式表示方法。

  • 事实的表示 事实可看成是断言一个语言变量的值或断言多个语言变量之间关系的陈述句。其中，语言变量的值或语言变量之间的关系可以是数字，也可以是一个词等。例如，陈述句“雪是白的”，其中“雪”是语言变量，“白的”是语言变量的值。再如，陈述句“王峰热爱祖国”，其中，“王峰”和“祖国”是两个语言变量，“热爱”是语言变量之间的关系。在产生式表示法中，事实通常是用三元组或四元组来表示的。

对确定性知识，一个事实可用一个三元组(对象，属性，值)或(关系，对象1，对象2）来表示。其中，对象就是语言变量。这种表示方式，在机器内部可用一个表来实现。

  • 规则的表示 规则描述的是事物间的因果关系，其含义是“如果……，则……”。婉则的产生式表示形式常称为产生式规则，简称产生式，或称规则。一个规则由前件和后件两部分组成，其基本形式为：
  • IF <前件> THEN <后件>
  • 或 <前件> — <后件> 其 中 ，前件是该规则可否使用的先决条件，它由单个事实或多个事实的逻辑组合构成;后件是一组结论或操作，它指出当“前件”满足时，应该推出的“结论”或应该执行的“动作”。 严格地讲，用巴克斯范式给出的规则的形式化描述如下：
  • <规则> :: <前提> — <结论>
  • <前提> ::= <简单条件> | <复合条件>
  • <结论> ::= <事实> | <动作>
  • <复合条件> ::= <简单条件> And <简单条件> [(And < 简单条件>…)]|<简单条件> Or <简单条件> [(Or<简单条件>… )]
  • <动作> ::= < 动作名> | [(<变元>，… )] #### 简例 上面给出的是产生式表示的一般方法，下面以“动物识别系统”中的产生式规则为例，给出两个具体的产生式知识表示方法。 在经典的“动物识别系统”中，有以下两条产生式规则：
  • r3:IF动物有羽毛THEN动物是鸟
  • r15:IF动物是鸟AND动物善飞THEN动物是信天翁 其中，r3和r15分别是相应产生式在“动物识别系统”中的编号，我们称为规则序号。 对r2，其前提条件是“动物有羽毛”，结论是“动物是鸟”，其含义是“如果动物有羽毛，则动物是鸟”。对r15，其前提条件是“动物是鸟AND动物善飞”，其前提条件是由子条件“动物是鸟”和另一个子条件“动物善飞”通过析取构成的一个组合条件。该产生式的含义是“如果动物有羽毛，并且动物善飞，则该动物是信天翁”。

    特性

    产生式表示法的主要优点如下：

    1. 自然性。产生式表示法用“如果……，则……”的形式表示知识，这种表示形式与人类的判断性知识基本一致，既直观、自然，又便于进行推理。

  1. 模块性。每条产生式规则都是一个独立的知识单元，它描述了前提与结论之间的一种静态关系，其正确性可以独立地得到保证;各产生式规则之间不存在相互调用关系，这就大大增加了规则的模块性。

  2. 有效性。产生式表示除用来表示确定性知识外，稍做变形就可用来表示不确定性知识。

产生式表示法的主要缺点如下：

  1. 效率较低。在产生式表示中，各规则之间的联系必须以综合数据库为媒介，并且，其求解过程是一种反复进行的“匹配一冲突消解一执行”过程，即先用规则前提与综合数据库中的已知事实进行匹配,再从规则库中选择可用规则，当有多条规则可用时，还需要按一定策略进行“冲突消解”，然后才能执行选中的规则。这样的执行方式将导致执行的效率较低。

  2. 不便于表示结构性知识。由于产生式表示中的知识具有一致格式，且规则之间不能相互调用，因此那种具有结构关系或层次关系的知识，用产生式很难将其以自然的方式来表示。

语义网络表示法

语义网络是一种用实体及其语义关系来表达知识的有向图。其中，节点代表实体，表示各种事物、概念、情况、属性、状态、事件、动作等;弧代表语义关系，表示它所连接的两个实体之间的语义联系。在语义网络中，每一个节点和弧都必须带有标志，这些标志用来说明它所代表的实体或语义。

在语义网络表示中，一个最基本的语义单元称为语义基元，一个语义基元所对应的那部分网络结构称为基本网元。一个语义基元可用如下三元组：(节点1，弧，节点2) 来描述，其结构可用一个基本网元来表示。例如，若用A，B分别表示三元组中的节点1和节点2,用表示A与B之间的语义联系，则它所对应的基本网元的结构下图。 image

详细…

框架表示法

简介

框架理论认为，人们对现实世界中各种事物的认识都是以一种类似于框架的结构存储在记忆中的。当遇到一个新事物时，就从记忆中找出一个合适的框架，并根据新的情况对其细节加以修改、补充，从而形成对这个新事物的认识。例 如 ，当一个人走进一家从未去过的饭店前，会根据以往的经验，想象到在饭店里将看到菜单、餐桌、服务员等。至于菜单的样式、餐桌的颜色、服务员的服饰等细节，都需要在进人饭店之后通过观察来得到。但是这样的一种知识结构却是事先可以预见到的。

实例

例2.14 一个直接描述硕士生有关情况的框架

Frame <MASTER>
    Name：Unit（Last-name，First-name）
    Sex：Area（male，female）
              Default： male
    Age：Unit（Years）
    Major：Unit（Major）
    Field：Unit（Field）
    Advisor：Unit（Last-name，First-name）
    Project ：Area（National，Provincial，Other）
                     Default：National
    Paper：Area（SCI，EI，Core，General）
                  Default：Core 
    Address：< S-Address>
    Telephone：Home  Unit（Number）
                         Mobile  Unit（Number）

推理方法

产生式推理

通常人们把利用产生式知识表示方法所进行的推理称为产生式推理，把由此所产生的系统称为产生式系统。按照推理的控制方向，产生式推理可分为正向、逆向和混合三种方式。

基本结构

  • 综合数据库
    1. 存放推理过程的各种当前信息。如：问题的初始状态，输入的事实，中间结论及最终结论。
    2. 作为推理过程选择可用规则的依据。推理过程中规则是否可用是通过该规则的前提与DB中的已知事实的匹配来确定的。可匹配的规则称为可用规则。利用可用规则进行推理，将会得到一个结论。该结论若不是目标，将作为新的事实放入DB，成为以后推理的已知事实。
  • 规则库（知识库）
    1. 作用：用于存放推理所需要的所有规则，是整个产生式系统的知识集是产生式系统能够进行推理的根本。
    2. 要求：知识的完整性、一致性、准确性、灵活性和可组织性
  • 控制系统
    1. 控制系统的主要作用：亦称推理机，用于控制整个产生式系统的运行，决定问题求解过程的推理线路。
    2. 控制系统的主要任务：
      • 选择匹配：按一定策略从规则库种选择规则与综合数据库中的已知事实进行匹配。
      • 冲突消解：对匹配成功的规则，按照某种策略从中选出一条规则执行。
      • 执行操作：对所执行的规则，若其后件为一个或多个结论，则把这些结论加入综合数据库；若其后件为一个或多个操作时，执行这些操作。
      • 终止推理：检查综合数据库中是否包含有目标，若有，则停止推理
      • 路径解释：在问题求解过程中，记住应用过的规则序列，以便最终能够给出问题的解的路径。

正向推理

从已知事实出发、正向使用规则，也称为数据驱动推理或前向链推理。

  • 算法流程图 image
  • 实例 设有以下两条规则
  • r3：IF 动物有羽毛 THEN 动物是鸟
  • r15：IF 动物是鸟 AND 动物善飞 THEN 动物是信天翁 其中，r3和r15是上述两条规则在动物识别系统中的规则编号。假设已知有以下事实：动物有羽毛，动物善飞。求满足以上事实的动物是何种动物。

解：由于已知事实“动物有羽毛”，即r3的前提条件满足，因此r3可用，承认的r3结论，即推出新的事实“动物是鸟”。此时，r15的两个前提条件均满足，即r15的前提条件满足，因此r15可用，承认的r15结论，即推出新的事实“动物是信天翁”。

逆向推理

从某个假设目标出发，逆向使用规则，亦称为目标驱动推理或逆向链推理。

  • 算法流程图 image
  • 实例（同正向推理的例子） 解：开始推理前，综合数据库和假设库均为空。开始推理后，现将初始证据“动物有羽毛”和“动物善飞”放入综合数据库；将动物是“信天翁”放入初始假设集。开始推理时，从假设集取出“动物是信天翁”，综合数据库中没有包含该假设，然后检查该假设能否被某个规则所导出？发现它可以被r15导出，r15可用。使用r15，将“动物是鸟”和“动物善飞”放入假设集。从假设集取出一个假设“动物是鸟”，该假设仍不是综合数据库中的已知事实，但发现它可以由r3导出，说明r3可用。使用r3，将其前提条件“动物有羽毛”放入假设集。此时，假设集中的所有假设已全部被综合数据库中的事实所满足，推理完成。

混合推理

正向推理比较直观，但其推理无明确的目标，求解问题时可能会执行许多与解无关的操作，导致推理效率较低。

逆向推理过程的目标明确，但是当用户对解的情况认识不清，选择假设目标不好时，会影响系统效率。

因此人们提出了混合（双向）推理方法混合（双向）推理是一种把正向和逆向结合起来使用的推理方法。有以下三种方式：

  • 可以采用先正向后逆向
  • 也可以采用先逆向后正向
  • 还可以采用随机选择正向和逆向的推理方法。

自然演绎推理

简介

从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。自然演绎推理最基本的推理规则是三段论推理，它包括： 假言推理，拒取式，假言三段论

实例

设已知如下事实：A,B,A→C,B∧C→D,D→Q。求证：Q为真。 证明：因为

  • A, A→C⇒ C 假言推理
  • B,C⇒ B∧C 引入合取词
  • B∧C，B∧C→D ⇒ D 假言推理
  • D, D→Q ⇒ Q假言推理 因此，Q为真

归纳演绎推理

简介

归结演绎推理是一种基于鲁宾逊归结原理的机器推理技术。鲁宾逊归结原理是在海伯伦理论基础上提出的一种逻辑“反证法”。定理证明的实质就是要对前提P和结论Q，证明P→Q永真。要证明P→Q永真，可以采用反证法的思想，把关于永真性的证明转化为关于不可满足性的证明。即：要证明P→Q永真，只要能够证明P∧﹁Q是不可满足即可(原因是：﹁ (P→Q) ⇔ ﹁(﹁ P∨Q) ⇔ P∧﹁ Q 。

实例

已知：“张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。”问：“现在李在哪个教室上课？”

解：

  • 首先定义谓词：
    • C(x, y) x和y是同班同学；
    • At(x, u) x在u教室上课。
  • 把已知前提用谓词公式表示如下：
    • C(zhang, li)
    • (∀x) (∀y) (∀u) (C(x, y)∧At(x, u)→At(y,u))
    • At(zhang, 302)
  • 把目标的否定用谓词公式表示如下：
    • ﹁(∃v)At(li, v)
  • 把上述公式化为子句集：
    • C(zhang, li)
    • ﹁C(x, y)∨﹁At(x, u)∨At(y, u)
    • At(zhang, 302)
  • 把目标的否定化成子句式，并用重言式
    • ﹁At(li,v) ∨At(li,v) 代替之。
  • 把此重言式加入前提子句集中，得到一个新的子句集，对这个新的子句集，应用归结原理求出其证明树。其求解过程如下图所示。 image
  • 该证明树的根子句就是所求的答案，即“李明在302教室”。

相关连接