人工智能基础

# 人工智能主要学派

# 符号主义

又称为逻辑主义、心理学派或计算机学派是基于物理符号系统的人工智能学派（谓词逻辑）

# 连接主义

又称为仿生学派或生理学派，是基于神经网络与学习算法的人工智能学（神经网络）

# 行为主义

又称为进化主义或控制论学派，是基于控制论和 “动作 - 感知” 控制系统的人工智能学派（强化学习）

# 知识表示

# 概述

# 知识的概念

• 知识：经过加工的信息，是对信息的提炼和概括，它是高度概括的信息。
• 信息：是数据所表达的客观事实，数据是信息的载体，信息是用来消除不确定性从而使数据得以解读。
• 数据：数据是可以被记录和识别的一组有意义的符号，以适合于人工或自然方式进行通信、解释或处理。

# 知识的特征

• 相对正确性：任何知识都是在一定条件和环境下产生的，在特定的条件和环境下才是正确的。（经典物理）
• 存在不确定性的知识：随机性引起的、模糊性引起的、经验引起的、不完全性引起的。
• 可表示性与可利用性：知识可以用适当的形式表示出来，如语言、文字、图形、神经网络等。

# 知识的分类

• 以知识的作用范围来划分：知识可以分为常识性知识和领域性知识。
  • 常识性知识是通用性知识，是人们普遍了解的知识，具有较广泛的应用范围。
  • 领域性知识是面向某个具体领域的知识，是专业性知识，只有相应专业领域的人员才能掌握并用来求解领域内的有关问题。
• 按知识的确定性划分：知识可分为确定知识和不确定知识。
• 按照人类的思维及认识方法来分：可分为逻辑性知识和形象性知识
  • 逻辑性知识是反映人类逻辑思维过程的知识，这种知识一般都具有因果关系及难以精确描述的特点。
  • 形象思维知识是人类思维的另一种方式，是通过形象思维所获得的知识。
• 按知识的作用及表示来划分：可分为事实性知识、规则性知识、控制性知识和元知识
  • 事实性知识是指有关领域内的概念、事实、事物的属性、状态及其关系的描述，包括事物的分类、属性、事物间关系、科学事实、客观事实等。
  • 规则性知识是指有关问题中与事物的行动、动作相联系的因果关系知识，这种知识是动态的、变化的。
  • 控制性知识是用控制策略表示问题的知识，包含有关部门各种处理过程、策略和结构的知识，常用来协调整个问题求解的过程。
  • 元知识是指有关知识的知识，是知识库中的高层知识，包括怎样使用规则、解释规则、校验规则、解释程序结构等知识。

# 知识的表示

就是研究用机器表示知识的一般方法，可以看作是将知识符号化（即编码成某种数据结构）并输入到计算机的过程和方法；

# 知识表示的分类

• 陈述性知识表示
  • 含义：以数据的形式表示知识。这类表示法将知识表示与知识的运用（推理）分开处理，在表示知识时，并不涉及如何运用知识的问题， 是一种静态的描述方法。
  • 优缺点：优点是灵活简洁。其缺点是推理过程不透明，不易理解。
• 过程性知识表示
  含义：知识表示的形式是一个 “过程” 。它将知识的表示与运用（推理）相结合，知识就寓于程序之中，是一种动态的描述方法。
  优缺点：优点是推理过程直接、清晰。其缺点是不够严格，知识间有交互重叠，灵活性差，知识的增、删极不方便。

# 谓词逻辑表示法

命题逻辑和谓词逻辑是最先应用于人工智能的两种逻辑，谓词逻辑是在命题逻辑基础上发展起来的，命题逻辑可以看作是谓词逻辑的一种特殊形式。

# 命题

命题是具有真假意义的陈述句，通常用大写的英文字母表示

• 原子命题：不能分解成更简单的命题。
• 复合命题：由连接词、标点符号和原子命题等复合构成的命题
• 命题逻辑：研究命题和命题之间关系的符号逻辑系统。
• 命题常量（命题常元）：一个命题标识符表示确定的命题。
• 命题变元（命题变量） ：命题标识符只表示任意命题的位置标志。

# 命题的语法

• 命题常元：$True(T)$ 和$False(F)$；
• 命题符号：$P$、$Q$、$R$、$T$ 等；
• 联结词： $\neg$（非）、$\wedge$（合取）、$\vee$（析取）、$\rightarrow$（蕴含）、$\leftrightarrow$（等价）；
• 括号：$( )$。

# 命题的特点

• 命题逻辑把原子命题作为最基本的单元，不再往下分析。比如说命题 P“π 是无理数” 和命题 Q “无理数是实数” 这两个命题，在命题逻辑的范畴内是找不到什么联系的。
• 命题这种表示法有较大的局限性，它无法把它所描述的客观事物的结构及逻辑特征反映出来，也不能把不同事物的共同特征描述出来

# 谓词

谓词逻辑是命题逻辑的扩充与发展，它将一个原子命题分解成谓词与个体两部分。谓词描述个体的属性，以及个体之间的关系。谓词对应于语言中的谓语，或谓语 + 宾语，个体常项常用单词或 a，b，c 等小写字母表记，个体变项常用 x，y，z 等小写字母表记。
个体变元的取值范围称为个体域。个体域可以是有限的，也可以是无限的。个体词描述逻辑中的重要名词，作为对象（对象是个体词描述的东西）。
谓词逻辑：根据对象和对象上的谓词（即对象的属性和对象之间的关系），通过使用连接词和量词来表示世界的符号逻辑系统。

# 谓词公式

# 谓词公式的几个重要概念

• 函数符号与谓词符号：若函数符号$f$ 中包含的个体数目为$n$，则称$f$ 为$n$ 元函数符号。若谓词符号$P$ 中包含的个体数目为$n$，则称$P$ 为$n$ 元谓词符号。
• 谓词的阶：如果谓词 P 中的所有个体都是个体常量、变元、或函数，则该谓词为一阶谓词。如果谓词 P 中某个个体本身又是一个一阶谓词，则称 P 为二阶谓词。
• 谓词的项
  1. 单独一个个体是项 (包括常量和变量)。
  2. 若$f$ 是$n$ 元函数符号，而$t_1,t_2,…,t_n$ 是项，则$f(t_1, t_2,…,t_n)$ 是项。
  3. 任何项仅由规则（1）（2）所生成。

# 谓词公式的语法

• 谓词公式来表示知识：标点符号、括号、逻辑联结词、常量符号集、变量符号集、n 元函数符号集、n 元谓词符号集、量词
• 谓词演算：合法表达式 (原子公式、合式公式)，表达式的演算化简方法，标准式（合取的前束范式或析取的前束范式）

# 谓词公式的语法元素

• 常量符号。
• 变量符号。
• 函数符号。
• 谓词符号。
• 联结词。
• 在个体变量及其作用域下：引入量词： $\forall$（全称量词）、$\exists$（存在量词）。后面跟着变量，称为量词的指导变元。
• 公式（原子公式与合式公式）若$P$ 为$n$ 元谓词符号，$t_1,t_2,…,t_n$ 都是项，则称$P(t_1, t_2, …, t_n)$ 为原子公式，简称原子。
• 一阶谓词逻辑的（合式）公式（可简称公式）可递归定义如下
  1. 原子公式是公式 (也称为原子公式)。
  2. 若 P、Q 是公式，则 ($﹁P$)、($P∧Q$)、($P∨Q$)、($P→Q$)、($P↔Q$) 也是公式。
  3. 若 P 是公式，x 是任一个体变元，则 $(∀x)P$、$(∃x)P$ 也是公式。
  4. 任何公式都由有限次应用（1）（2）（3）来产生。

# 谓词公式的解释

一阶谓词逻辑公式的解释：设 D 为谓词公式 P 的非空个体域，若对 P 中的个体、函数、谓词按如下规定赋值：
（1）为每个个体指派 D 中的一个元素。
（2）为每个 n 元函数指派一个从 Dⁿ 到 D 的映射。
（3）为每个 n 元谓词指派一个从 Dⁿ 到 {T,F} 的映射。
则称这些指派为公式 P 在 D 上的一个解释

# 谓词逻辑知识表示

• 谓词逻辑表示的适应范围：适合于表示事物的状态、属性、概念等事实性知识，也可以用来表示事物间具有确定因果关系的规则性知识。
• 对事实性知识：可以使用谓词公式中的析取符号与合取符号连接起来的谓词公式来表示
• 对规则性知识：通常使用由蕴涵符号连接起来的谓词公式来表示
• 谓词公式表示知识的步骤
  1. 定义谓词及个体，确定每个谓词及个体的确切含义
  2. 根据所要表达的事物或概念，为每个谓词中的变元赋以特定的值
  3. 根据所要表达的知识的语义，用适当的连接符将各个谓词连接起来形成谓词公式

# 谓词逻辑表示的特点

• 优点：严密性、自然性、通用性、知识易于表达、易于实现
• 缺点：效率低、灵活性差、组合爆炸

# 产生式表示法

# 产生式表示法的基本方法

# 产生式规则

通常用于表示事物间的因果关系

• 基本形式
  • if P then Q 或 $P \rightarrow Q$
  • P 表示规则的条件
  • Q 表示规则激活时应该执行的动作

# 规则分类

• 前提 - 结论型
• 条件 - 动作型

# 规则的表示

产生式系统中每条规则是一个 “前提→结论” 或 “条件→结论” 的产生式，简单形式为：

• IF〈前提〉THEN〈结论〉
• IF〈条件〉THEN〈动作〉

# 规则知识的表示

• 确定性规则知识可用简单形式表示
• 不确定性规则知识：$P \rightarrow Q (可信度)$ 或 IF P THEN Q (可信度)

# 事实知识的表示

• 确定性事实知识一般使用三元组表示：(对象，属性，值) 或 (关系，对象 1，对象 2)
• 不确定性事实知识使用四元组表示：(对象，属性，值，不确定度量值) 或 (关系，对象 1，对象 2，不确定度量值)

# 产生式系统的基本结构

# 规则库

用于描述相应领域内知识的产生式集合，是某领域知识 (规则) 的存储器，其中的规则是以产生式形式表示的。规则库中包含着将问题从初始状态转换成目标状态 (或解状态) 的那些变换规则。

规则库是专家系统的核心，也是一般产生式系统赖以进行问题求解的基础。其中知识的完整性和一致性、知识表达的准确性和灵活性以及知识组织的合理性，都将对产生式系统的性能和运行效率产生直接的影响。

# 综合数据库

用于存放输入的事实、从外部数据库输入的事实以及中间结果（事实）和最后结果的工作区。

当规则库中的某条产生式的前提可与综合数据库中的某些已知事实匹配时，该产生式就被激活，并把用它推出的结论放入综合数据库中，作为后面推理的已知事实。综合数据库的内容是在不断变化的，是动态的

# 推理机

用来控制和协调规则库与综合数据库的运行，包含了控制策略和推理方式。

# 控制策略

作用就是确定选用什么规则或如何应用规则。通常从选择规则到执行操作分 3 步完成：匹配、冲突解决和操作。

# 匹配

将当前综合数据库中的事实与规则中的条件进行比较，如果相匹配，则这一规则称为匹配规则。

通过冲突解决策略选中的在操作部分执行的规则称为启用规则

# 冲突解决

• 专一性排序
• 规则排序
• 规模排序
• 就近排序

# 操作

执行规则的操作部分。经过操作以后，当前的综合数据库将被修改，其他的规则有可能将成为启用规则。

# 产生式系统的推理方式

# 正向推理

正向推理是从已知事实出发，通过规则库求得结论。正向推理方式也被称为数据驱动方式或自底向上的方式。

推理过程：

1. 规则库中的规则与综合数据库中的事实进行匹配，得到匹配的规则集合；
2. 使用冲突解决算法，从匹配规则集合中选择一条规则作为启用规则；
3. 执行启用规则的操作部分，将该启用规则的操作结果送入综合数据库或对综合数据库进行必要的修改。

重复这个过程直至达到目标。

# 反向推理

反向推理是从目标（作为假设）出发，反向使用规则，求得已知事实。这种推理方式也被称为目标驱动方式或自顶向下的方式。

其推理过程是：

1. 规则库中的规则后件与目标事实进行匹配，得到匹配的规则集合；
2. 使用冲突解决算法，从匹配规则集合中选择一条规则作为启用规则；
3. 将启用规则的前件作为子目标。

重复这个过程直至各子目标均为已知事实，则反向推理的过程就算成功结束。

# 双向推理

双向推理是一种既自顶向下又自底向上的推理。推理从两个方向同时进行，直至某个中间界面上两方向结果相符便成功结束。

双向推理较正向或反向推理所形成的推理网络来得小，从而推理效率更高。

# 产生式系统的分类

• 按产生式所表示的知识是否具有确定性
  • 确定性产生式系统
  • 不确定性产生式系统
• 按推理机的推理方式
  • 正向推理
  • 反向推理
  • 双向推理
• 按规则库及综合数据库的性质与结构特征
  • 可交换的产生式系统：规则的使用次序对问题的最终求解是无关紧要的
  • 可分解的产生式系统：把一个规模较大且较复杂的问题分解为若干个规模较小且较简单的子问题，然后对每个子问题分别进行求解
  • 可恢复的产生式系统：在问题求解过程中既可以对综合数据库添加新内容、又可删除或修改老内容的产生式系统

# 产生式系统的特点

# 产生式表示法的优点

• 清晰性
• 模块性
• 自然性

# 产生式表示法的缺点

• 难以扩展
• 规则选择效率低

# 框架表示

框架理论的基本观点是 “人脑已存储有大量的典型情景，当人面临新的情景时，就从记忆中选择（粗匹配）一个称作框架的基本知识结构，这个框架是以前记忆的一个知识空框，而其具体内容依新的情景而改变，对这空框的细节加工修改和补充，形成对新情景的认识又记忆于人脑中，以丰富人的知识。

• 强调事物内部的结构化描述；
• 较好地反映人观察事物的思维方式；
• 应用于机器人识别领域。

# 框架结构

框架由描述事物的各个方面的槽组成，每个槽可有若干个侧面。

• 一个槽用于描述所讨论对象的某一方面的属性，
• 一个侧面用于描述相应属性的一个方面。
• 槽和侧面所具有的值分别称为槽值和侧面值。槽值可以是逻辑的、数字的，可以是程序、条件、默认值或是一个子框架。

一个框架通常由框架名、槽名、侧面和值这四部分组成

<框架名>

  槽名1：侧面名11 值11

        侧面名12 值12

  槽名2：侧面名21 值21

        侧面名22 值22

  约束： 约束条件1

        约束条件2

# 系统预定义槽名

• ISA：表示框架的类别
• AKO：表示框架的上位类
• Instance：表示框架的实例，指出下层框架
• Part-of：表示框架的部分

# 框架网络

多个互联的框架连接起来组成的框架系统称为框架网络。

它包含两方面的含义：

• 网络中的节点是框架，利用节点之间的关系可由某些框架推论出另一些框架；
• 网络中的节点既可代表框架，也可代表框架中的槽，每条弧的一头联着某个框架的一个槽，另一头联着另一个框架。

# 框架表示法的推理方法

# 匹配

由框架所构成的知识库，当利用它进行推理时，其过程往往是根据已知的信息，通过与知识库中预先存储的框架进行匹配，找出一个或几个与该信息所提供的情况最适合的预选框架，形成初步假设。然后在在该假设框架引导下，收集进一步的信息。按某种评价原则，对预选的框架进行评价，以决定最后接受或放弃预选的框架。

# 默认推理（填槽过程中）

在框架网络中，各框架之间通过 ISA 链（槽）构成半序的继承关系。在填槽过程中，如果没有特别的说明，子框架的槽值将继承父框架相应的槽值，称为默认推理。

# 框架表示法的特点

# 继承性

是框架的一个很重要的性质，下层框架可以从上层框架继承某些属性或值，也可以进行补充和修改。这样一些相同的信息可以不必重复存储，减少冗余信息节省了存储空间

# 结构化

框架表示法是一种结构化的知识表示方法。不但把知识的内部结构表示出来还可以把知识之间的联系也表示出来，是一种表达能很强的知识表示方法。

# 自然性

在人类思维和理解活动中分析和解释遇到的情况时，就从记忆中选择一个类似事物的框架，通过对其细节进行修改或补充，形成对新事物的认识，这与人们的认识活动是一致的。

# 推理灵活多变

框架表示法没有固定的推理机制，它可以根据待求解问题的特点采取灵活地采取多种推理方法。

# 缺点

框架表示法的主要不足之处在于它不善于表达过程性知识。因此它经常与产生式表示法结合起来使用，以取得互补效果。

# 语义网络

# 语义网络的概念

语义网络是一种通过概念及其语义联系（或语义关系）来表示知识的有向图，其节点和弧带有标注。

• 其中有向图的各节点用来表示各种事物、概念、情况、属性、状态、事件和动作等对象，
• 节点上的标注用来区分各节点所表示的不同对象，每个各节点可以带有多个属性，以表征其所代表的对象的特性
• 节点还可以是一个语义子网络；
• 弧是有方向的、有标注的，方向表示节点间的主次关系且方向不能随意调换。标注用来表示各种语义联系

# 语义网络的基本结构

语义网络一般由一些最基本的语义单元组成。这些最基本的语义单元被称为语义基元（基本语义联系），可用三元组表示：(节点 1，弧，节点 2)。

# 语义网络的基本语义联系

# 类属关系

• AKO (A-Kind-of): 表示一个事物是另一个事物的一种类型。
• AMO (A-Member-of): 表示一个事物是另一个事物的成员。
• ISA (Is-a): 表示一个事物是另一个事物的实例。

# 包含关系

• Part-of: 表示一个事物是另一个事物的一部分。
• Member-of: 表示一个事物是另一个事物的成员。

# 属性关系

• Have: 表示一个事物具有某种属性。
• Can: 表示一个事物具有某种能力。

# 时序关系

• Before: 表示一个事物发生在另一个事物之前。
• After: 表示一个事物发生在另一个事物之后。

# 位置关系

• Located-on: 表示一个事物位于另一个事物之上。
• Located-at: 表示一个事物位于另一个事物的某个位置。
• Located-under: 表示一个事物位于另一个事物之下。
• Located-inside: 表示一个事物位于另一个事物之内。
• Located-outside: 表示一个事物位于另一个事物之外。

# 相邻关系

• Similar-to: 表示一个事物与另一个事物相似。
• Near-to: 表示一个事物与另一个事物接近。

# 因果关系

• If-then: 表示如果一个事物发生，则另一个事物也会发生。

# 组成关系

• Composed-of: 表示一个事物由另一个事物组成。

# 语义网络表示知识的方法

# 事实性知识的表示

通常把有关一个事物或一组相关事物的知识用一个语义网络来表示

# 情况、动作和事件的表示

增加了情况节点、动作节点和事件节点，允许用一个节点来表示情况、动作和事件。

# 情况的表示

在用语义网络表达那些由不及物动词表示的语句或没有间接宾语的及物动词表示的语句时（祈使句、动作只关联单一个体），如果该语句的动作表示了一些其它情况，如动作作用的时间等，则需要增加一个情况节点用于指出各种不同的情况。

# 动作的表示

有些表示知识的语句既有发出动作的主体，又有接受动作的客体。在用语义网络表示这样的知识时，可以增加一个动作节点用于指出动作的主体和客体。

# 事件的表示

如果要表示的知识可以看成是发生的一个事件，那么可以增加一个事件节点来描述这条知识

# 连词和量词的表示（逻辑关系的表示）

# 合取与析取的表示

当用语义网络来表示知识时，为了能表示知识中体现出来的 “合取与析取” 的语义联系，可通过增加合取节点与析取节点来表示。只是在使用时要注意其语义，不应出现不合理的组合情况。

# 存在量词与全称量词的表示

• 对存在量词可以直接用 “AKO”、“ISA” 等语义关系来表示。
• 对全称量词可以采用语义网络分区技术来表示，也称为分块语义网络，该技术的基本思想是：把一个复杂的命题划分成若干个子命题，每一个子命题用一个简单的语义网络来表示，称为一个子空间，多个子空间构成一个大空间。每个子空间看作是大空间中的一个节点，称为超节点。空间可以逐层嵌套，子空间之间用弧相互连接。

# 否定的表示

• 基本语义关系的否定的表示，可通过在有向弧上直接标注该基本语义关系的否定的方法来解决
• 一般语义关系的否定的表示，通常需要引进 “非” 节点来表示。

# 语义网络表示知识的步骤

1. 确定问题中所有对象和各个对象的属性。
2. 确定所讨论对象间的关系。
3. 根据语义网络中所涉及的关系，对语义网络中的节点及弧进行整理，包括增加节点、弧和归并节点等。
4. 将各对象作为语义网络的一个节点，而各对象间的关系作为网络中各节点的弧，连接形成语义网络。

# 语义网络的推理过程

# 继承推理

继承是指把对事物的描述从抽象结点传递到具体结点。通过继承可以得到所需结点的一些属性值，它通常是沿着 ISA、AKO、AMO 等继承弧进行的。继承的一般过程为：

1. 建立结点表，存放待求结点和所有以 ISA、AKO、AMO 等继承弧与此结点相连的那些结点。
2. 检查表中的第一个是否有继承弧。如果有，就从该弧所指的所有结点放入结点表的末尾，记录这些结点的所有属性，并从结点表中删除第一个结点。如果没有，仅从结点表中删除第一个结点。
3. 重复检查表中的第一个是否有继承弧，直到结点表为空。记录下来的属性就是待求结点的所有属性。

# 匹配推理

语义网络问题的求解一般是通过匹配来实现的。所谓匹配就是在知识库的语义网络中寻找与待求问题相符的语义网络模式。其主要过程为：

1. 根据问题的要求构造网络片断，该网络片断中有些结点或弧为空，标记待求解的问题（询问处）。
2. 根据该语义网络片断在知识库中寻找相应的信息。
3. 当待求解的语义网络片断和知识库中的语义网络片断相匹配时，则与询问处（也就是待求解的地方）相匹配的事实就是问题的解。

# 语义网络的特点

• 结构性：语义网络把事物的属性以及事物间的各种语义联系显式地表现出来，是一种结构化的知识表示法。在这种方法中，下层结点可以继承、新增和修改上层结点的属性，从而实现信息共享。
• 联想性：着重强调事物间的语义联系，体现了人类思维的联想过程。
• 自索引性：语义网络表示把各结点之间的联系以明确、简洁的方式表示出来，通过与某一结点连接的弧很容易找出相关信息，而不必查找整个知识库。可以有效地避免搜索时的组合爆炸问题。
• 自然性：是一种直观的知识表示方法，符合人们表达事物间关系的习惯，而且把自然语言转换成语义网络也较为容易。
• 非严格性：语义网络没有公认的形势表示体系，它没有给其节点和弧赋予确切的含义。在推理过程中有时不能区分物体的 “类” 和 “实例” 的特点。因此，通过语义网络实现的推理不能保证其推理结果的正确性。
• 另外，语义网络表示法的推理规则不十分明了。其表达范围也受到一定限制，一旦当语义网络中结点个数比较多时，网络结构复杂，推理就难以进行。

# 确定性推理

# 推理的基本概念

# 推理的定义

• 推理的概念：是指按照某种策略从已知事实出发去推出结论的过程。
• 推理所用的事实：
  • 初始证据：推理前用户提供的
  • 中间结论：推理过程中所得到的
• 推理过程：由推理机来完成，所谓推理机就是智能系统中用来实现推理的那些程序。
• 推理的两个基本问题
  • 推理的方法：解决前提和结论的逻辑关系，不确定性传递
  • 推理的控制策略：解决推理方向，冲突消解策略

# 推理方法及其分类

# 按推理的逻辑基础分类

# 演绎推理

演绎推理是从已知的一般性知识出发，去推出蕴含在这些已知知识中的适合于某种个别情况的结论。是一种由一般到个别的推理方法，其核心是三段论。

# 归纳推理

是一种由个别到一般的推理方法。归纳推理的类型

• 按照所选事例的广泛性可分为完全归纳推理和不完全归纳推理

  • 完全归纳推理：是指在进行归纳时需要考察相应事物的全部对象，并根据这些对象是否都具有某种属性，推出该类事物是否具有此属性。如，计算机质量检验。
  • 不完全归纳推理：是指在进行归纳时只考察了相应事物的部分对象，就得出了关于该事物的结论。

• 按照推理所使用的方法可分为枚举、类比、统计和差异归纳推理等

  • 枚举归纳推理：是指在进行归纳时，如果已知某类事物的有限可数个具体事物都具有某种属性，则可推出该类事物都具有此种属性。
  • 类比归纳推理：是指在两个或两类事物有许多属性都相同或相似的基础上，推出它们在其他属性上也相同或相似的一种归纳推理。

# 默认推理

默认推理又被称为缺省推理，它是在知识不完全的情况下假设某些条件已经具备 所进行的推理。

由于这种推理允许某些默认条件是成立的，这就摆脱了需要知道全部有关事实才能进行推理的束缚，使得推理在知识不完全的情况下也能进行。

在默认推理中，如果到某一时刻发现原先所做的默认不正确，则要撤销所做的默认以及由此默认推出的所有结论，重新按新情况进行推理。

# 演绎推理与归纳推理的区别

演绎推理是在已知领域内的一般性知识的前提下，通过演绎求解一个具体问题或者证明一个结论的正确性。它所得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭露出来，因此它不能增殖新知识。

归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。

# 单调推理与非单调推理

• 单调推理：在推理过程中随着推理的向前及新知识的加入，推出的结论是呈单调增加的趋势，并且越来越接近最终目标，在推理过程中不出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又回到前面的某一步
• 非单调推理：在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定它，使得推理退回到前面的某一步，重新开始。

# 确定性推理与不确定性推理

• 确定性推理（精确推理）：如果在推理中所用的知识都是精确的，即可以把知识表示成必然的因果关系，然后进行逻辑推理，推理的结论或者为真，或者为假，这种推理就称为确定性推理。
• 不确定性推理（不精确推理）：在人类知识中，有相当一部分属于人们的主观判断，是不精确的和含糊的。由这些知识归纳出来的推理规则往往是不确定的。基于这种不确定的推理规则进行推理，形成的结论也是不确定的，这种推理称为不确定性推理。

# 启发式推理与非启发式推理

• 启发式推理：如果在推理过程中，运用了与问题有关的启发性知识，即解决问题的策略、技巧及经验，以加快推理过程，提高搜索效率，这种推理过程就被称为启发式推理。
• 非启发式推理：如果在推理过程中，不运用启发性知识，只按照一般的控制逻辑进行推理，这种推理过程就被称为非启发式推理。

# 推理的控制策略

# 推理方向

• 正向推理：是从初始状态出发，使用规则，到达目标状态。又称为数据驱动推理、前向链推理、模式制导推理及前件推理。
• 逆向推理：是以某个假设目标为出发点的一种推理，又称为目标驱动推理、逆向链推理、目标制导推理及后件推理。
• 混合推理：已知的事实不充分的情况下，通过正向推理先把其运用条件不能完全匹配的知识都找出来，并把这些知识可导出的结论作为假设，然后分别对这些假设进行逆向推理。
  • 先正向再逆向，通过正向推理，即从已知事实演绎出部分结果，然后再用逆向推理证实该目标或提高其可信度。
  • 先逆向再正向，先假设一个目标进行逆向推理，然后再利用逆向推理中得到的信息进行正向推理，以推出更多的结论。
• 双向推理：双向推理是指正向推理与逆向推理同时进行，且在推理过程中的某一步骤上 “碰头” 的一种推理。正向推理所得的中间结论恰好是逆向推理此时要求的证据

# 求解策略

决定推理是只求一个解还是求所有解以及最优解等

# 限制策略

对推理的深度、宽度、时间、空间等进行限制

# 冲突消解策略

• 在推理过程中，匹配会出现三种情况：

  • 已知事实不能与知识库中的任何知识匹配成功
  • 已知事实恰好只与知识库中的一个知识匹配成功
  • 已知事实可与知识库中的多个知识匹配成功；或者有多个（组）已知事实都可与知识库中某一知识匹配成功；或者有多个（组）已知事实可与知识库中的多个知识匹配成功

• 按就近原则排序：该策略把最近被使用过的规则赋予较高的优先级。

• 按已知事实的新鲜性排序：一般我们认为新鲜事实是对旧知识的更新和改进，比老知识更有效，即后生成的事实比先生成的事实具有较大的优先性。

• 按匹配度排序：在不确定推理时，匹配度不仅可确定两个知识模式是否可匹配，还可用于冲突消解。根据匹配程度来决定哪一个产生式规则优先被应用。

• 按领域问题特点排序：该方法按照求解问题领域的特点将知识排成固定的次序。

• 按上下文限制排序：该策略将知识按照所描述的上下文分成若干组，在推理过程中根据当前数据库中的已知事实与上下文的匹配情况，确定选择某组中的某条知识。

• 按条件个数排序：多条规则生成的结论相同的情况下，由于条件个数较少的规则匹配所花费的时间较少而且容易实现，所以将条件少的规则赋予较高的优先级，优先被启用。

• 按规则的次序排序：该策略是以知识库中预先存入规则的排列顺序作为知识排序的依据，排在前面的规则具有较高的优先级。

# 推理的逻辑基础

# 谓词与个体

在谓词逻辑中，可以将原子命题分解为谓词与个体两部分。

• 个体：是指可以独立存在的物体，可以是抽象的或具体的。
• 谓词：则用于刻画个体的性质、状态或个体间的关系。
  • 一元谓词：一个谓词，可以与一个个体相关联，它刻画了个体的性质。
  • 多元谓词：一个谓词，可以与多个个体相关联，它刻画了个体间的关系。
  • 谓词的一般形式可表示为：$P(x_1,x_2, …,x_n)$ 其中 P 是谓词，而$x_1,x_2, …,x_n$ 是个体。

# 谓词逻辑的永真性和可满足性

# 谓词公式的解释

设 D 是谓词公式 P 的非空个体域，若对 P 中的个体常量、函数和谓词按如下规定赋值：

1. 为每个个体常量指派$D$ 中的一个元素；
2. 为每个 n 元函数指派一个从$D_n$ 到$D$ 的一个映射，其中$D_n=\{(x_1, x_2, …, x_n)| x_1, x_2, …, x_n∈D\}$
3. 为每个 n 元谓词指派一个从$D_n$ 到$\{F，T\}$ 的映射。

则称这些指派为 P 在 D 上的一个解释。

# 谓词公式的永真性

如果谓词公式 P 对非空个体域 D 上的任一解释都取得真值 T，则称 P 在 D 上是永真的；如果 P 在任何非空个体域上均是永真的，则称 P 永真。

可见，要判定一谓词公式为永真，必须对每个非空个体域上的每个解释逐一进行判断。当解释的个数为有限时，尽管工作量大，公式的永真性毕竟还可以判定，但当解释个数为无限时，其永真性就很难判定了

如果谓词公式 P 对非空个体域 D 上的任一解释都取假值 F，则称 P 在 D 上是永假的；如果 P 在任何非空个体域上均是永假的，则称 P 永假。谓词公式的永假性又称不可满足性或不相容。

# 谓词公式的可满足性

对于谓词公式 P，如果至少存在 D 上的一个解释，使公式 P 在此解释下的真值为 T，则称公式 P 在 D 上是可满足的。

• 谓词公式的可满足性也称为相容性。
• 谓词公式 P 的永假与不可满足是等价的。
• 归结推理就是采用一种逻辑上的反证法，将永真性转换为不可满足性的证明。

# 谓词公式的等价性与永真蕴含

设 P 与 Q 是 D 上的两个谓词公式，D 是它们共同的个体域。若对 D 上的任意解释，P 与 Q 的取值都相同，则称公式 P 与 Q 在域 D 上是等价的。如果 D 是任意非空个体域，则称 P 与 Q 是等价的。记作：$P⇔Q$。

# 置换与合一

# 置换

置换可简单的理解为是在一个谓词公式中用置换项去替换变量。

置换是形如$\{t_1/x_1,t_2/x_2,…,t_n/x_n\}$ 的有限集合。其中，$t_1,t_2,…,t_n$ 是项；$x_1,x_2,…,x_n$ 是互不相同的变元；$t_i/x_i$ 表示用$t_i$ 替换$x_i$。并且要求$t_i$ 与$x_i$ 不能相同，$x_i$ 不能循环地出现在另一个$t_j$ 中。

不含任何元素的置换称为空置换，以$ε$ 表示。

谓词公式 F 的特例：设 F 为谓词公式，σ 为一个置换，则称 Fσ 为谓词公式的特例，或 F 的例。

# 置换的乘法

设

$$θ = \{t_1/x_1,t_2/x_2,…,t_n/x_n\}\\ λ = \{ u_1/y_1, u_2/y_2, … , u_m/y_m \}$$

是两个置换。则 θ 与 λ 的合成也是一个置换，记作$θ\circ λ$，也称置换乘法。它是从集合$\{ t_1λ/x_1, t_2λ/x_2, … , t_nλ/x_n, u_1/y_1, u_2/y_2, … , u_m/y_m \}$ 中删去以下两种元素

1. 当$t_iλ=x_i$ 时，删去$t_iλ/x_i (i=1, 2 ,…, n)$；
2. 当$y_j∈\{ x_1, x_2 ,…, x_n \}$ 时，删去$u_j/y_j (j=1, 2 ,…, m)$

最后剩下的元素所构成的集合。

# 置换的性质

(1) 空置换$\varepsilon$ 是左么元和右么元，即对任意的置换$\theta$，$\varepsilon \circ \theta=\theta \circ \varepsilon = \theta$
(2) 对任意表达式 E，恒有$E(\theta \circ \lambda)＝(E\theta)\lambda$。
(3) 若对任意表达式 E 恒有$E\theta＝E\lambda$，则$\theta＝\lambda$。
(4) 对任意置换$\theta$，$\lambda$，$\mu$, 恒有$(\theta\circ\lambda) \circ \mu=\theta\circ(\lambda\circ\mu)$ 即置换的合成满足结合律。
(5) 设 A 和 B 为表达式集合，则$(A\cup B)\theta=A\theta\cup B\theta$
注意：置换的合成不满足交换律。

# 合一

合一可理解为是寻找项对变量的置换，使两个谓词公式一致。可定义为：

合一的概念：设有公式集$F=\{F_1, F_2,…,F_n\}$，若存在一个置换$θ$，可使$F_1θ=F_2θ=…=F_nθ$，则称$θ$ 是$F$ 的一个合一。称$F_1,F_2,…,F_n$ 是可合一的。

一般来说，一个公式集的合一不是唯一的

# 最一般合一

设$σ$ 是公式集$F$ 的一个合一，如果对$F$ 的任一个合一$θ$ 都存在一个置换$λ$，使得$θ=σ \circ λ$，则称$σ$ 是一个最一般合一 (MGU)。

一个公式集的最一般合一是唯一的。

# 差异集

表达式的非空集合 W 的差异集 (difference set) 是按下述方法得出的子表达式的集合：

1. 在 W 的所有表达式中找出对应符号不全相同的第一个符号 (自左算起)。
2. 在 W 的每个表达式中，提取出占有该符号位置的子表达式。这些子表达式的集合便是 W 的差异集 D。

# 自然演绎推理

从一组已知为真的事实出发，直接运用经典逻辑中的推理规则推出结论的过程称为自然演绎推理。

自然演绎推理最基本的推理规则是三段论推理，它包括：

• 假言推理$P, P→Q ⇒ Q$
• 拒取式$﹁ Q, P→Q ⇒ ﹁P$
• 假言三段论$P→Q, Q→R ⇒ P→R$

# 避免产生两类错误

肯定后件 (Q) 的错误：当$P→Q$ 为真时，希望通过肯定后件 Q 推出前件 P 为真，这是不允许的.
否定前件 (P) 的错误：当$P→Q$ 为真时，希望通过否定前件 P 推出后件 Q 为假，这也是不允许的.

# 自然演绎推理的优缺点

• 优点：定理证明过程自然，容易理解，而且它拥有丰富的推理规则，推理过程灵活，便于在它的推理规则中嵌入领域启发式知识。
• 缺点：容易产生组合爆炸，推理过程中得到的中间结论一般呈指数形式递增。

# 归结演绎推理

# 子句型

# 子句与子句集

• 原子谓词公式及其否定统称为文字
• 任何文字的析取式称为子句
• 不含任何文字的子句称为空子句
  • 由于空子句不含有任何文字，也就不能被任何解释所满足，因此空子句是永假的，不可满足的
  • 空子句一般被记为$\varnothing$ 或 NIL
• 由子句或空子句所构成的集合称为子句集
• 子句的合取称为合取范式
• 合取范式表示为子句集，子句间隐含合取关系

# 公式的标准化

合取范式 -> 前束范式 ->Skolem 标准型

• 量词前束范式：$(Q_1x_1)(Q_2x_2)…(Q_nx_n)M$，其中$Q_i$ 是量词，$x_i$ 是约束变量，M 是不含量词的母式

一阶逻辑公式所对应的 Skolem 标准型基于如下思想来构造:

1. 当一阶逻辑的一个公式被变换为前束范式后，其中的前束是一个存在量词或全称量词的序列，母式中不再含有量词。
2. 因为母式不含量词，所以可以变换为合取范式。
3. 通过使用 Skolem 函数，可以在前束中将存在量词消去，而不影响公式的永假性。

# 子句集的化简

1. 消去连接词$\rightarrow$ 和$\leftrightarrow$，（$P\rightarrow Q \Leftrightarrow \neg P \vee Q$；$P\leftrightarrow Q \Leftrightarrow (P\land Q)\vee (\neg P \land \neg Q)$）
2. 减少否定符号的辖域：将每个否定符号$﹁$移到紧靠谓词的位置，使得每个否定符号最多只作用于一个谓词上$\neg(∀x)P(x) ⇔ (∃x) \neg P(x)$；$\neg(∃x)P(x) ⇔ (∀x) \neg P(x)$
3. 对变元标准化：在一个量词的辖域内，把谓词公式中受该量词约束的变元全部用另外一个没有出现过的任意变元代替，使不同量词约束的变元有不同的名字
4. 化为前束范式：把所有量词都移到公式的左边，并且在移动时不能改变其相对顺序。
5. 消去存在量词：若存在量词不出现在全称量词的辖域内（即它的左边没有全称量词），只要用一个新的个体常量替换受该存在量词约束的变元，就可消去该存在量词；若存在量词位于一个或多个全称量词的辖域内，例如$(∀x_1)…(∀x_n) (∃y)P(x_1，x_2 ,…, x_n ,y)$ 则需要用 Skolem 函数$f(x_1，x_2 ,…, x_n)$ 替换受该存在量词约束的变元 y，然后再消去该存在量词。
6. 化为 Skolem 标准型
7. 省掉全称量词
8. 根据合取词拆分公式：在母式中消去所有合取词，把母式用子句集的形式表示出来。其中，子句集中的每一个元素都是一个子句。
9. 更换变量名称：对子句集中的某些变量重新命名，使任意两个子句中不出现相同的变量名。

# 子句集的应用

• 化简后的标准子句集是不唯一的
• 设有谓词公式 F，其标准子句集为 S，则 F 为不可满足的充要条件是 S 为不可满足的。

# 鲁滨逊归结原理

鲁滨逊归结原理基本思想：首先把欲证明问题的结论否定，并加入子句集，得到一个扩充的子句集 S'。然后设法检验子句集 S' 是否含有空子句，若含有空子句，则表明 S' 是不可满足的；若不含有空子句，则继续使用归结法，在子句集中选择合适的子句进行归结，直至导出空子句或不能继续归结为止。

鲁滨逊归结原理包括：命题逻辑归结原理；谓词逻辑归结原理

# 归结式的定义及性质

• 若 P 是原子谓词公式，则称$P$ 与$﹁P$ 为互补文字。
• 设$C_1$ 和$C_2$ 是子句集中的任意两个子句，如果$C_1$ 中的文字$L_1$ 与$C_2$ 中的文字$L_2$ 互补，那么可从$C_1$ 和$C_2$ 中分别消去$L_1$ 和$L_2$，并将$C_1$ 和$C_2$ 中余下的部分按析取关系构成一个新的子句$C_{12}$，则称这一过程为归结，称$C_{12}$ 为$C_1$ 和$C_2$ 的归结式，称$C_1$ 和$C_2$ 为$C_{12}$ 的亲本子句。
• 归结式$C_{12}$ 是亲本子句$C_1$ 和$C_2$ 的逻辑结论
  • 设$C_1$ 和$C_2$ 是子句集$S$ 中的两个子句， $C_{12}$ 是$C_1$ 和$C_2$ 的的归结式，若用$C_{12}$ 代替$C_1$ 和$C_2$ 后得到新的子句集$S_1$，则由$S_1$ 的不可满足性可以推出原子句集$S$ 的不可满足性
  • 设$C_1$ 和$C_2$ 是子句集$S$ 中的两个子句， $C_{12}$ 是$C_1$ 和$C_2$ 的的归结式，若把$C_{12}$ 加入$S$ 中得到新的子句集$S_2$，则$S_2$ 与$S$ 的不可满足性是等价的。
• 子句集 S 是不可满足的，当且仅当存在一个从 S 到空子句的归结过程

# 命题逻辑的归结

• 命题逻辑的归结原理：假设 F 为已知前提，G 为欲证明的结论，归结原理把证明 G 为 F 的逻辑结论转化为证明$F∧﹁G$ 为不可满足。而在不可满足的意义上，公式$F∧﹁G$ 与其子句集是等价的，即把公式集上的不可满足转化为子句集上的不可满足。

在命题逻辑中，已知 F，证明 G 为真的归结反演过程如下：

1. 否定目标公式 G，得$﹁G$;
2. 把$﹁G$ 并入到公式集 F 中，得到$\{F，﹁G\}$；
3. 把$\{F，﹁G\}$ 化为子句集 S。
4. 应用归结原理对子句集 S 中的子句进行归结，并把每次得到的归结式并入 S 中。如此反复进行，若出现空子句，则停止归结，此时就证明了 G 为真。

# 谓词逻辑的归结

需要先用一个最一般合一（MGU） 对变元进行代换，然后才能进行归结。

• 设$C_1$ 和$C_2$ 是两个没有公共变元的子句，$L_1$ 和$L_2$ 分别是$C_1$ 和$C_2$ 中的文字（除变元外是潜在的互补文字）。如果$L_1$ 和$L_2$ 不考虑互补性时存在最一般合一$σ$，则称$C_{12}=(\{C_1σ\}-\{ L_1σ\})∪(\{ C_2σ\}-\{ L_2σ\})$ 为$C_1$ 和$C_2$ 的二元归结式，而$L_1$ 和$L_2$ 为归结式上的文字

谓词逻辑中的二元归结式（应用因子的概念）
若$C_{1}$ 和$C_{2}$ 是无公共变元的子句，则

1. $C_{1}$ 和$C_{2}$ 的二元归结式；
2. $C_{1}$ 和$C_{2}$ 的因子$C_{2}\sigma_{2}$ 的二元归结式；
3. $C_{1}$ 的因子$C_{1}\sigma_{1}$ 和$C_{2}$ 的二元归结式；
4. $C_{1}$ 的因子$C_{1}\sigma_{1}$ 和$C_{2}$ 的因子$C_{2}\sigma_{2}$ 的二元归结式。

这四种二元归结式都是子句$C_{1}$ 和$C_{2}$ 的二元归结式，记为$C_{12}$。

谓词逻辑的归结反演过程与命题逻辑的归结反演过程相比，其步骤基本相同，但每步的处理对象不同。例如，在化简子句集时，谓词逻辑需要把由谓词构成的公式集化为子句集；在按归结原理进行归结时，谓词逻辑的归结原理需要考虑两个亲本子句的最一般合一。

# 归结演绎推理的归结策略

• 宽度优先搜索
• 支持集策略：每一次参加归结的两个亲本子句中，至少应该有一个是由目标公式的否定所得到的子句或它们的后裔
• 删除策略
  • 纯文字删除法
  • 重言式删除法
  • 包孕式删除法
• 单文字子句策略
• 线性输入策略
• 祖先过滤策略

# 搜索

# 状态空间搜索

# 问题的状态空间表示

状态空间记为 SP，可表示为二元组：SP=(S,O)

• S：问题求解（即搜索）过程中所有可能到达的合法状态构成的集合；
• O：操作算子的集合，操作算子的执行会导致问题状态的变迁；
• 状态：用于记载问题求解（即搜索）过程中某一时刻问题现状的快照；
  • 抽象为矢量形式 $Q=[q_0,q_1,…,q_n]^T$
  • 每个元素$q_i$ 称为状态分量
  • 给定每个状态分量$q_k$ 值就得到一个具体的状态
    用状态空间搜索来求解问题的系统均定义一个状态空间，并通过适当的搜索算法在状态空间中搜索解答路径。
    问题的状态空间是一个表示该问题的全部可能状态及其变迁的有向图。

# 盲目搜索

# 宽度优先搜索

# 深度优先搜索

# 有界深度搜索

1. 把初始节点 S0 放入 OPEN 表中，置 S0 的深度 d (S0)=0。
2. 如果 OPEN 表为空，则问题无解，失败并退出。
3. 把 OPEN 表中的第一个节点取出放入 CLOSE 表。按顺序编号 n。
4. 考察节点 n 是否为目标节点。若是，则求得了问题的解，成功并退出。
5. 如果节点 n 的深度 d (n)=dm，则转第 (2) 步。
6. 如果节点 n 不可扩展，则转第 (2) 步。
7. 扩展节点 n。将其子节点放入 OPEN 表的首部，并为其配置指向父节点的指针。然后转第 (2) 步。

# 迭代加深搜索

• 它是一种回避选择最优深度限制问题的策略，它是试图尝试所有可能的深度限制：
  • 首先深度为 0，
  • 然后深度为 1，
  • 然后为 2，等等。
• 如果初始深度为 0，则该算法只生成根节点，并检测它。
• 如果根节点不是目标，则深度加 1，通过典型的深度优先算法，生成深度为 1 的树。

# 启发式搜索

# 评估函数

• 评估函数 f (x) 定义为从初始节点 S0 出发，约束地经过节点 x 到达目标节点 Sg 的所有路径中最小路径代价的估计值。评估函数的一般形式为：f (x)=g (x)+h (x)
  • g (x)：从初始节点 S0 到节点 x 的实际代价；
  • h (x)：从 x 到目标节点 Sg 的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h (x) 称为启发式函数。

# 启发式搜索 A 算法

A 算法的设计与一般图搜索相同，划分为二个阶段：

• 初始化：建立只包含初始状态节点 s 的搜索图 G:={s}，OPEN:={s}，CLOSE:={}
• 搜索循环
  • MOVE-FIRST (OPEN)- 取出 OPEN 表首的节点 n
  • 扩展出 n 的子节点，插入搜索图 G 和 OPEN 表
  • 适当的标记和修改指针（子节点 -> 父节点）
  • 排序 OPEN 表（评价函数 f (n) 的值排序）

通过循环地执行该算法，搜索图会因不断有新节点加入而逐步长大，直到搜索到目标节点。

# A * 算法

A * 算法定义：

• 在 A 算法中，规定 h (n)≤h*(n);
• 经如此限制以后的 A 算法就是 A * 算法。

# 迭代加深 A * 算法

迭代加深搜索算法，它以深度优先的方式在有限制的深度内搜索目标节点。
该算法在每个深度上检查目标节点是否出现，如果出现则停止，否则深度加 1 继续搜索。
而 A * 算法是选择具有最小评估函数值的节点扩展。
迭代加深 A * 搜索算法 IDA * 是上述两种算法的结合。

# 问题规约

# 问题规约的描述

问题归约的状态空间可表示为三元组表示: $(S_0,O,P)$
其中：

• $S_0$ 是初始问题，即要求解的问题；
• P 是本原问题集，其中的每一个问题是不用证明的，自然成立的，如公理、已知事实等，或已证明过的问题；
• O 是操作算子集，它是一组变换规则，通过一个操作算子把一个问题化成若干个子问题

# 问题规约的实质

从目标 (要解决的问题) 出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题归约为一个平凡的本原问题集合。

# 与或图表示

应用问题归约策略得到的状态空间图，也称为 “与或图”

• 逻辑 “与” 关系 —— 用圆弧将几条节点间关联弧连接在一起
  • 表示问题分解为子问题；
  • 子问题的状态联合起来构成问题状态。
  • 子问题全部解决才会导致问题的解决；
• 逻辑 “或” 关系：
  • 问题可以有多种分解方式；
  • 问题（子问题）可能激活多个状态变迁操作；
  • 只要一种分解方式或状态变迁操作能导致最终的解答成功即可；
  • 导致多个可能的解答
• K 连接弧：对应于某个给定集合的各节点，用一个连接它们的圆弧来标记。这种弧叫 K 连接弧，表示对问题 A 由某个操作算子作用后产生 K 个子问题。
• 弧连接的子节点叫与节点。
• K=1 的连接弧连接的子节点叫做或节点。

# 与或图搜索的基本概念

• 根节点 —— 无父节点的节点，用于指示问题初始状态（和一般图一样）
• 叶节点 —— 无子节点的节点
• 终节点 —— 能用于联合表示目标状态的节点（本原问题）
  • 终节点必定是叶节点，反之不然；
  • 目标状态 —— 终结点的集合。
• 解图的定义
  • 解图纯粹是一种 “与” 图
  • 解图中，节点或节点组间不存在 “或” 关系；
  • 所有叶节点都是终节点
• 解图的生成
  • 自根节点开始选 K - 连接；
  • 从该 K - 连接指向的每个子节点出发，再选一 K - 连接；
  • 如此反复进行，直到所有 K - 连接都指向终节点为止.
• 解图代价 —— 以 C (n) 指示节点 n 到终节点集合解图的代价，并令 K - 连接的代价就为 K， 则
  • 若 n 是终节点，则 C (n)=0；
  • 若 n 有一 K - 连接指向子节点 n₁，n₂，…，n_k，且这些子节点每个都有到终节点集合的解图，则 C (n) = K + C (n₁) + C(n₂) + … + C(n_k)
• 能解节点
  • 终节点是能解节点；
  • 若节点 n 存在一个 K - 连接指向子节点 n₁n₂，…，n_k，且这些子节点都是能解节点，则 n 是能解节点；
• 不能解节点
  • 非终节点的叶节点是不能解节点；
  • 若节点 n 的每一个 K - 连接都至少指向一个不能解节点，则 n 是不能解节点。

# 与或图的启发式搜索

• 评价函数：f (n)=h (n)，其中 h (n) 是对 n 到终节点集合解图中最小解图代价的估计；

• 与或图中存在 “或” 关系，会有多个候选的局部解图，选择局部解图中可能代价最小的用于下一步搜索。

• （局部）解图代价 ——f (n0)

  • n₀—— 初始状态节点
  • 由于解图是以递归方式生成的，所以解图的代价也是以递归地计算出 f (n₀)。
  • 若父节点 n 的 K - 连接指向的子节点：n₁,n₂,…,n_k，则 f (n) = K + h (n₁) + h(n₂) + … + h(n_k)，代替 h (n)

# AO * 算法

符号说明：

• G - 搜索图；
• G’- 被选中的待扩展局部解图；
• LGS - 候选的待扩展局部解图集；
• n₀ - 根节点，即初始状态节点；
• n - 被选中的待扩展节点；
• f_i(n₀)- 第 i 个待扩展局部解图的可能代价。

算法划分二个阶段：

• 初始化
  • 建立只包含初始状态节点 n0 的搜索图 G:={n₀}；
  • 待扩展局部解图集 LGS:={}；
• 搜索循环
  • 选择和扩展 LGS 中的局部解图；
  • 精化新局部解图代价的估计；
  • 传递节点的能解性。

算法实现过程

1. G=n₀, LGS 为空集；
2. 若 n₀ 是终节点，则标记 n₀ 是能解节点，否则计算 f (n₀)=h(n₀)，并把 G 作为 0 号候选局部解图加进 LGS；
3. 若 n₀ 标记为能解节点，则算法成功返回；
4. 选择 LGS 中 f_i(n₀) 最小的待扩展解图 G’；
5. 随机选择 G’中一个非终节点的叶节点作为 n；
6. 扩展 n，建立 K - 连接，子节点 n_i 并加入 G；计算子节点 n_i 的 f (n_i)=h(n_i)
7. 若 n 存在 j 个 K - 连接，LGS 中删除 G’，将 j 个新的局部解图加入 LGS;
8. 精化新局部解图代价的估计 f (n)=h (n)，用公式 f (n) = K + h (n₁) + h(n₂) + … + h(n_k) 取代原先的 f (n); 递归地作用到初始节点 n₀；
9. 传递新局部解图中节点的能解性，标记作为终节点的子节点为能解节点；递归地传递节点的能解性到初始节点 n₀。

# 博弈

# 极大极小过程

极大极小过程是考虑双方对弈若干步之后，从可能的走法中选一步相对好的走法来走，即在有限的搜索深度范围内进行求解。
需要定义一个静态估价函数 f, 以便对棋局的态势做出评估。
这个函数可以根据棋局的态势特征进行定义。假定对弈双方分别为 MAX 和 MIN，规定：

• 有利于 MAX 方的态势：f (p) 取正值
• 有利于 MIN 方的态势：f (p) 取负值
• 态势均衡的时候：f (p) 取零

其中 p 代表棋局。

1. 当轮到 MIN 走步的节点时（取与时），MAX 应考虑最坏的情况（即 f (p) 取极小值）。
2. 当轮到 MAX 走步的节点时（取或时），MAX 应考虑最好的情况（即 f (p) 取极大值）。
3. 评价往回倒推时，相应于两位棋手的对抗策略，交替使用（1）和（2）两种方法传递倒推值。

# α-β 过程

α-β 过程就是把生成后继和倒推值估计结合起来，及时剪掉一些无用分支，以此来提高算法的效率。具体的剪枝方法如下：

1. 对于一个与节点 MIN，若能估计出其倒推值的上确界 β，并且这个 β 值不大于 MIN 父节点（一定是或节点）的估计倒推值的下确界 α，即 α≥β，则不必再扩展该 MIN 节点的其余子节点了，因为这些节点的估值对 MIN
2. 对于一个或节点 MAX，若能估计出其倒推值的下确界 α，并且这个 α 值不小于 MAX 的父节点（一定是与节点）的估计倒推值的上确界 β，即 α≥β，则不必再扩展该 MAX 节点的其余子节点了，因为这些节点的估值对 MAX 父节点的倒推值已无任何影响了。这一过程称为 β 剪枝。

# 不确定性推理

# 概率推理

# 全概率公式

设有事件$A_1,A_2,…, A_n$ 满足:

1. $A_i$ 与$A_j$ 互斥，即$A_i∩A_j=∅$，$i≠j$；
2. $P(A_i)>0$，$i=1,2,…,n$；
3. 样本空间$D$ 是各个事件的并集，即$D=A_1∪A_2∪…∪A_n$。

则对任意事件 B，有：$P(B)=P(B|A_1)P(A_1)+P(B|A_2)P(A_2)+…+P(B|A_n)P(A_n)=\sum\limits_{i=1}^{n}P(B|A_i)P(A_i)$

# 贝叶斯公式

设有事件$A_1,A_2,…, A_n$ 满足:

1. $A_i$ 与$A_j$ 互斥，即$A_i∩A_j=∅$，$i≠j$；
2. $P(A_i)>0$，$i=1,2,…,n$；
3. 样本空间$D$ 是各个事件的并集，即$D=A_1∪A_2∪…∪A_n$。

则对任意事件 B，有：$P(A_i|B)=\frac{P(B|A_i)P(A_i)}{\sum\limits_{j=1}^{n}P(B|A_j)P(A_j)}$

其中

• $P(A_i)$ 是事件$A_i$ 的先验概率；
• $P(B|A_i)$ 是在事件$A_i$ 发生条件下事件$B$ 的条件概率（逆概率）；
• $P(A_i|B)$ 是在事件$B$ 发生条件下事件$A_i$ 的条件概率，称为后验概率。

# 经典概率方法

设有如下产生规则：If E Then H，其中 E 为前提条件，H 为结论，具有随机性，那么条件概率 P (H|E) 就表示在 E 发生时，H 的概率，可以用它作为证据 E 出现时结论 H 的不确定性程度。
同样对于复合条件$E=E_1∧E_2∧…∧E_n$ 也可以用条件概率$P(H|E_1…E_n)$ 作为证据$E_1,…,E_n$ 出现时，结论 H 的不确定性程度。

# 贝叶斯方法

# 单个证据

对于产生式规则 If E Then H_i，用条件概率$P(H_i|E)$ 作为证据 E 出现时，结论$H_i$ 的确定性程度。根据 Bayes 公式，可以得到$P(H_i|E)=\frac{P(H_i)P(E|H_i)}{\sum\limits_{j=1}^{n}P(H_j)P(E|H_j)}$

# 多个证据

对于有多个证据$E_1, E_2,\dots, E_m$ 和多个结论$H_1, H_2,\dots, H_n$，并且每个证据都以一定程度支持结论的情况，可以得到$P(H_i|E_1,E_2,\dots,E_m)=\frac{P(H_i)P(E_1,E_2,\dots,E_m|H_i)}{\sum\limits_{j=1}^{n}P(H_j)P(E_1,E_2,\dots,E_m|H_j)}=\frac{P(H_i)P(E_1|H_i)P(E_2|H_i)…P(E_m|H_i)}{\sum\limits_{j=1}^{n}P(H_j)P(E_1|H_j)P(E_2|H_j)…P(E_m|H_j)}$

# 主观贝叶斯方法

# 规则不确定性

在主观 Bayes 方法中，规则的不确定性知识可表示为：IF E THEN (LS,LN) H，其中 (LS,LN) 用来表示该知识的强度。LS（充分性度量）和 LN（必要性度量）表示形式分别如下：

• 充分性度量$LS=\frac{P(E|H)}{P(E|\neg H)}$，表示 E 对 H 的支持强度，取值范围为$[0, +∞)$，一般由专家给出。
• 必要性度量$LN=\frac{P(\neg E|H)}{P(\neg E|\neg H)}=\frac{1-P(E|H)}{1-P(E|\neg H)}$，表示$﹁E$ 对 H 的支持强度，即 E 对 H 为真的必要性程度，取值范围为$[0, +∞)$，也由专家凭经验给出。
• 几率函数$O(x)=\frac{P(x)}{1-P(x)}$
• 几率似然性形式$O(H|E)=LS\times O(H)$，LS 称为充分似然性，因为如果 LS=+∞，则证据 E 对于推出 H 为真实逻辑充分的。
• 必然性似然性形式$O(H|\neg E)=LN\times O(H)$，LN 称为必要似然性，因为如果 LN=+∞，则证据$﹁E$ 对于推出 H 为真实逻辑必要的。

# LS 的性质

当 LS>1 时，$O(H|E)>O(H)$，说明 E 支持 H；LS 越大，O (H|E) 比 O (H) 大得越多，即 LS 越大，E 对 H 的支持越充分。

• 当 LS→∞时，$O(H|E)→∞$，表示由于 E 的存在，将导致 H 为真。
• 当 LS=1 时，$O(H|E)=O(H)$，说明 E 对 H 没有影响；
• 当 LS<1 时，$O(H|E)<O(H)$，说明 E 不支持 H；
• 当 LS=0 时，$O(H|E)=0$，说明 E 的存在使 H 为假。

由上述分析可以看出，LS 反映的是 E 的出现对 H 为真的影响程度。因此称 LS 为知识的充分性度量

# LN 的性质

当 LN>1 时，$O(H|\neg E)>O(H)$，说明$\neg E$ 支持 H，即由于 E 的不出现，增大了 H 为真的概率。并且 LN 越大，$O(H| \neg E)$ 就越大，即$\neg E$ 对 H 为真的支持就越强。

• 当 LN→∞时，即$O(H|\neg E)→∞$，表示由于$\neg E$ 的存在，将导致 H 为真。
• 当 LN=1 时，$O(H|\neg E)=O(H)$，说明$\neg E$ 对 H 没有影响；
• 当 LN<1 时，$O(H|\neg E)<O(H)$，说明$\neg E$ 不支持 H；
• 当 LN=0 时，$O(H|\neg E)=0$，说明$\neg E$ 的存在将导致 H 为假。

由上述分析可以看出，LN 反映的是 E 不存在时对 H 为真的影响。因此称 LN 为知识的必要性度量。

# LS 和 LN 的关系

由于 E 和$\neg E$ 是互斥的，因此只有下面三种情况存在

• 当 LS>1 且 LN<1，即 E 支持 H，$\neg E$ 不支持 H；
• 当 LS<1 且 LN>1，即 E 不支持 H，$\neg E$ 支持 H；
• 当 LS=LN=1，即 E 和$\neg E$ 对 H 没有影响。

# 组合证据的不确定性计算

• 当组合证据是多个单一证据的合取时，即$E=E_1∧E_2∧…∧E_m$，如果已知在当前观察 S 下，每个单一证据$E_i$ 有概率$P(E_i|S)$，则组合证据 E 的概率为$P(E|S)=min\{P(E_1|S),P(E_2|S),…,P(E_m|S)\}$
• 当组合证据是多个单一证据的析取时，即$E=E_1∨E_2∨…∨E_m$，如果已知在当前观察 S 下，每个单一证据$E_i$ 有概率$P(E_i|S)$，则组合证据 E 的概率为$P(E|S)=max\{P(E_1|S),P(E_2|S),…,P(E_m|S)\}$
• 对于非运算，即，则$P(\neg E|S)=1-P(E|S)$

# 不确定性的传递

# 证据肯定为真

当证据 E 肯定为真，即全证据一定出现时，此时$P(E)=P(E|S)=1$。将 H 的先验几率更新为后验几率的公式为:$O(H|E)=LS×O(H)$，如果是把 H 的先验概率更新为其后验概率，则根据几率和概率的对应关系有:$P(H|E)=\frac{LS×P(H)}{1+(LS-1)×P(H)}$

# 证据肯定为假

当证据 E 肯定为假，即证据一定不出现时，$P(E)=P(E|S)=0$，$P(\neg E)=1$。将 H 的先验几率更新为后验几率的公式为:$O(H|\neg E)=LN×O(H)$，如果是把 H 的先验概率更新为其后验概率，则根据几率和概率的对应关系有:$P(H|\neg E)=\frac{LN×P(H)}{1+(LN-1)×P(H)}$

# 证据不确定

当证据既非为真又非为假时，不能再用上面的方法计算 H 的后验。这时因为 H 依赖于证据 E，而 E 基于部分证据 S，则 P (E|S) 是 E 依赖于 S 的似然性。这时可以使用下面的公式来计算 P (H|S) 的值：$P(H|S)=P(H|E)×P(E|S)+P(H|\neg E)×P(\neg E|S)$

$$P(H|S)=\begin{cases} P(H|\neg E)+\frac{P(H)-P(H|\neg E)}{P(E)}P(E|S) & \text{if } 0\leq P(E|S) < P(E)\\ P(H)+\frac{P(H|E)-P(H)}{1-P(E)}(P(E|S)-P(E)) & \text{if } P(E) \leq P(E|S) \leq 1 \end{cases}$$

# 结论不确定性的合成

假设有 n 条知识都支持同一结论 H，且这些知识的前提条件分别是 n 个相互独立的证据 E₁，E₂…，E_n，而每个证据所对应的观察又分别是 S₁，S₂，…，S_n。在这些观察下，求 H 的后验概率的方法：

1. 首先对每条知识分别求出 H 的后验几率是$O(H|S_i)$;
2. 利用这些后验几率并按下述公式求出所有观察下 H 的后验几率:$O(H|S_1S_2…S_n)=\frac{O(H|S_1)}{O(H)}\times\frac{O(H|S_2)}{O(H)}\times…\times\frac{O(H|S_n)}{O(H)}\times O(H)$

# 主观贝叶斯方法的优点

1. 该方法基于概率理论，具有坚实的理论基础，是目前不确定推理中最成熟的方法之一；
2. 计算量适中。

# 主观贝叶斯方法的缺点

1. 要求有大量的概率数据来构造知识库，并且难于对这些数据进行解释；
2. 在原始证据具有相互独立性，并能提供精确且一致的主观概率数据的情况下，该方法可以令人满意地处理不确定推理。但在实际当中，这些概率值很难保证一致性。

# 可信度方法

# 可信度的定义

在 C-F 模型中，可信度最初定义为信任与不信任的差，即 CF 定义为：$CF=\frac{MB-MD}{1-min\{MB,MD\}}$

• MB (Measure Belief,MB) 称为信任增长度，它表示因为与前提条件 E 匹配的证据出现，使结论 H 为真的信任的增长程度。

• MD (Measure Disbelief, MD) 称为不信任增长度，它表示因为与前提条件 E 匹配的证据出现，对结论 H 的不信任的增长程度。

• MB 定义为：$MB(H,E)=\begin{cases} 1 & \text{if } P(H)=1\\ \frac{max\{P(H|E),P(H)\}-P(H)}{1-P(H)} & \text{else} \end{cases}$

• MD 定义为：$MD(H,E)=\begin{cases} 1 & \text{if } P(H)=0\\ \frac{max\{P(H|\neg E),P(H)\}-P(H)}{P(H)} & \text{else} \end{cases}$

• $CF(H,E)$ 的计算公式为：$CF(H,E)=\begin{cases} MB(H,E)-0=\frac{P(H|E)-P(H)}{1-P(H)} & \text{if } P(H|E) > P(H)\\ 0 & \text{if } P(H|E) = P(H)\\ 0-MD(H,E)=-\frac{P(H)-P(H|E)}{P(H)} & \text{if } P(H|E) < P(H) \end{cases}$

# 可信度的计算

# 组合证据不确定性的计算

• 当组合证据是多个单一证据的合取时，即 E = E₁ AND E₂ AND … AND E_m，如果已知 CF (E_i) 是证据 E_i 的可信度，则组合证据 E 的可信度为：$CF(E)=min\{CF(E_1),CF(E_2),…,CF(E_m)\}$
• 当组合证据是多个单一证据的析取时，即 E = E₁ OR E₂ OR … OR E_m，如果已知 CF (E_i) 是证据 E_i 的可信度，则组合证据 E 的可信度为：$CF(E)=max\{CF(E_1),CF(E_2),…,CF(E_m)\}$
• 对于非运算，即$CF(\neg E)=\neg CF(E)$

# 不确定性的推理算法

# 证据肯定为真时

$CF(H)=CF(H,E)$

# 证据不是肯定存在时

$CF(H)=CF(H,E)×max\{0,CF(E)\}$

# 证据是多个条件组合的情况

$CF(H)=\begin{cases} CF_1(H) + CF_2(H) - CF_1(H)×CF_2(H) & \text{if } CF_1(H) \geq 0 \text{ and } CF_2(H) \geq 0\\ CF_1(H) + CF_2(H) + CF_1(H)×CF_2(H) & \text{if } CF_1(H) < 0 \text{ and } CF_2(H) < 0\\ \frac{CF_1(H)+CF_2(H)}{1-min\{|CF_1(H)|,|CF_2(H)|\}} & \text{if } CF_1(H)\times CF_2(H) < 0\\ \end{cases}$

# 证据理论

# 证据理论的形式化

# 概率分配函数

设 Ω 为变量 x 的所有可能取值的有限集合 (亦称样本空间)，且 Ω 中的每个元素都相互独立，则由 Ω 的所有子集构成的集合称为幂集，记为 2^Ω 。

当 Ω 中的元素个数为 N 时，则其幂集的元素个数为 2^N，且其中的每一个元素 A 都对应于一个关于 x 的命题，称该命题为 “x 的值在 A 中”。

设函数$m:2^Ω→[0,1]$，满足：$m(\varnothing )=0$，$\sum\limits_{A\subseteq \Omega}m(A)=1$，则称 m 为 Ω 上的概率分配函数，其中 m (A) 称为 A 的基本概率，m (A) 表示依据当前的环境对假设集 A 的信任程度。

# 信任函数

信任函数（belief function）$Bel:2^Ω→[0,1]$ 定义为：$Bel(A)=\sum\limits_{B \subseteq A}m(B)$，其中$Bel(A)$ 表示对 A 的信任程度，其值为 A 的所有子集的概率之和，表示对 A 的总的信任度

# 似然函数

似然函数（plausibility function）$Pl:2^Ω→[0,1]$ 定义为：$Pl(A)=1-Bel(\neg A)$，其中$\neg A$ 表示 A 的补集，即$\neg A=Ω-A$，似然函数又称为不可驳斥函数或上限函数。由于$Bel(A)$ 表示对 A 为真的信任度，$Bel(\neg A)$ 表示对$\neg A$ 的信任度，即 A 为假的信任度，因此，Pl (A) 表示对 A 为非假的信任度。

# 概率分配函数的正交和

设$m_1$ 和$m_2$ 是 Ω 上的两个概率分配函数，其正交和$m=m_1⊕m_2$ 满足：$m(\varnothing)=0$，$m(A)=K^{-1}\sum\limits_{B\cap C=A}m_1(B)m_2(C)$，其中$K=1-\sum\limits_{B\cap C=\varnothing}m_1(B)m_2(C)=\sum\limits_{B\cap C\neq \varnothing}m_1(B)m_2(C)$

# 证据理论推理模型

# 一个特殊的概率分配函数

设$\Omega=\{s_1,s_2,…,s_n\}$，m 为定义在 2^Ω 上的概率分配函数，且 m 满足：

1. $m(\{s_i\}) \geq 0$，对任意$s_i \in \Omega$；
2. $\sum\limits_{i=1}^{n}m(\{s_i\})\leq 1$；
3. $m(\Omega)=1-\sum\limits_{i=1}^{n}m(\{s_i\})$。
4. 对任意$A \subseteq \Omega$，且$|A|>1$ 或$|A|=0$，有$m(A)=0$。

则有：

• 信任函数
  • $Bel(A)=\sum\limits_{s_i \in A}m(\{s_i\})$
  • $Bel(\Omega)=\sum\limits_{B\subseteq \Omega}m(B)=\sum\limits_{i=1}^{n}m(\{s_i\})+m(\Omega)=1$
• 似然函数
  • $Pl(A)=1-Bel(\neg A)=m(\Omega)+Bel(A)$
  • $Pl(\Omega)=1-Bel(\varnothing)=1-0=1$
  • $Pl(A)-Bel(A)=Pl(B)-Bel(B)=m(\Omega)$

# 类概率函数

利用信任函数 Bel (A) 和似然函数 Pl (A)，可以定义 A 的类概率函数，并把它作为 A 的不确定性度量。$f(A)=Bel(A)+\frac{|A|}{|\Omega|}(Pl(A)-Bel(A))$，其中$|A|$ 表示 A 中元素的个数，$|\Omega|$ 表示 Ω 中元素的个数，$f(A)$ 表示 A 的类概率函数，也可以用来度量证据 A 的不确定性。

f (A) 有如下性质：

1. $f(\varnothing)=0$，$f(\Omega)=1$；
2. $0 \leq f(A) \leq 1$；
3. $Bel(A) \leq f(A) \leq Pl(A)$；
4. $f(\neg A)=1-f(A)$；

# 不确定性的推理

对于不确定性规则：If E Then H, CF，定义：$m(\{a_i\})=f(E)\cdot c_i$，或表示为：$m(\{a_1\},\{a_2\},…,\{a_n\})=f(E)\cdot c_1, f(E)\cdot c_2,…,f(E)\cdot c_n$，规定$m(\Omega)=1-\sum\limits_{i=1}^{n}m(\{a_i\})$，而对于$\Omega$ 的其他子集 H，规定$m(H)=0$。
当$H$ 为$\Omega$ 的真子集时，有：$Bel(H)=\sum\limits_{B\subseteq H}m(B)=\sum\limits_{i=1}^{n}m(\{a_i\})$。

# 组合证据的不确定性计算

当规则的前提（证据）E 是多个命题的合取或析取时，$f(E_1∧E_2∧…∧E_m)=min\{f(E_1),f(E_2),…,f(E_m)\}$，$f(E_1∨E_2∨…∨E_m)=max\{f(E_1),f(E_2),…,f(E_m)\}$。

当有多条规则支持同一结论时，设 H={a₁,a₂,…, a_n}，则:
If E₁ Then H，CF₁ (CF₁={c₁₁,c₁₂,…,c_1n})
If E₂ Then H，CF₂ (CF₂={c₂₁,c₂₂,…,c_2n})
………
If E_m Then H，CF_m (CF_m={c_m1,c_m2,…,c_mn})
如果这些规则相互独立地支持结论 H，则可以先计算 m_i({a₁},{a₂},…,{a_n}) = ( f(E_i)·c_i1, f(E_i)·c_i2,…, f(E_i)·c_im) (i=l,2,…,m)
然后根据前面介绍的求正交和的方法，对这些 m_i 求正交和，以组合所有规则对结论 H 的支持。一旦累加的正交和 m (H) 计算出来，就可以计算 Bel (H)、Pl (H)、f (H)。

# 机器学习

# 学习系统

# 学习系统的基本要求

通常一个学习系统应该满足如下的基本要求：

1. 具有适当的学习环境：学习系统中环境并非指通常的物理条件，而是指学习系统进行学习时所必需的信息来源。
2. 具有一定的学习能力：学习系统应通过与环境反复多次相互作用，逐步学 到有关知识，并且要使系统在学习过程中通过实践验证、评价所学知识的正确性
3. 能用所学的知识解决问题：学习系统能把学到的信息用于对未来的估计、分类、决策和控制。
4. 能提高系统的性能：提高系统的性能是学习系统最终目标。通过学习， 系统随之增长知识，提高解决问题的能力，使之能完成原来不能完成的任务，或者比原来做得更好

# 学习系统的基本模型

学习系统至少应有：环境、知识库、学习环节和执行环节四个基本部分。一种典型的机器学习系统（迪特里奇（Dietterich）学习模型）如图

# ID3 算法

1. $E(S)=-P^+\log_2P^+-P^-\log_2P^-$，其中$P^+$ 和$P^-$ 分别是正例和负例的概率。
2. $E(S,A)=\sum\limits_{i=1}^{n}\frac{|S_i|}{|S|}E(S_i)$，其中$S_i$ 是 S 中属性 A 的第 i 个取值所对应的样本子集。
3. $G(S,A)=E(S)-E(S,A)$，其中 G (S,A) 是信息增益，表示属性 A 对样本集 S 的信息增益，每次选择信息增益最大的属性作为划分属性。