AI 导论2:推理

正文索引 [隐藏]

1. 概述

数据与信息:数据是信息的载体和表示;信息是数据的语义

知识:有关信息关联在一起形成的信息结构

知识的特性:相对正确性、不确定性、可标识性、可利用性

知识的分类

  • 按作用范围:常识、领域性知识
  • 按作用分:事实性知识(陈述)、规则(描述因果)
  • 按确定性分:确定性知识(可分真假),不确定性知识
  • 按表现形式分:逻辑性知识(逻辑推理),形象性知识(描述事物形象)

命题逻辑表示法:无法反应客观事物的结构及逻辑特征

谓词逻辑表示法:谓词名 + 个体

  • 谓词名:刻画个体性质、状态、关系
  • 个体:独立存在的事物或者概念

产生式表示法

  • 表示事实

    image-20191209164459334

  • 表示规则

    image-20191209164531860

  • 与谓词逻辑蕴含式的区别:产生式可以表示不精确的知识

    image-20191209164707873

  • 产生式系统:规则库 + 综合数据库 + 控制系统

    • 规则库:描述相应领域知识的产生式集合

    • 综合数据库:存放已知的事实和推导出的事实

    image-20191209165350521

    • 控制机制

    • 匹配:匹配规则的条件部分

    • 冲突消解:当多于一条的规则匹配成功时,选择其中一条规则加以执行

    • 存放:将匹配规则的结论部分放入综合数据库(直接添加到数据库中,或者替换其中的某些内容)

    • 执行:执行相应操作

    • 验证:计算结论的不确定性

    • 终止:决定系统何时终止运行

    • 分类

    • 按推理方向分:正向(数据驱动)、后向(目标驱动)、双向

    • 按确定性分:确定性、不确定性

    • 特点

    • 优点:自然、模块化、有效、清晰

    • 缺点:低效、不能表达具有结构性的知识

2. 确定性推理

有一说一的步步为营式推理

目标

  • 根据已知条件,证明一个蕴含式
  • 直接蕴含推理得到答案

方法

  1. 描述已知、待求为逻辑表达式
  2. 逻辑表达式 -> 子句集
  3. 子句集合一化简
  4. 归结得到答案

I. 子句集的获取

文字:原子谓词公式和其否定形式(说白了就是不带逻辑符号)

例如:P(x),¬P(x,f(x)), Q(x,g(x))

子句:任何文字的析取式(用或逻辑连接文字)

例如:P(x)∨Q(x), ¬P(x,f(x))∨Q(x,g(x))

空子句:不包含任何文字的子句

子句集

image-20191209171555289

  • 意义:对于任意论域中的任何一个解释, S 中的子句不能同时取得真值 T 时,S 就是不可满足的,这样就证明了谓词公式 F 是不可满足的

子句集获取举例

image-20191209172228356

  1. 消去“→”和“↔”

    image-20191209172500080

  2. “¬” 前移

    image-20191209172513656

  3. 重命名变元,不同量词约束的变元不同名

    image-20191209172527953

  4. 消去存在量词

    image-20191209172538320

    • 每消掉一个存在量词,需要用一个有关所有全称量词的函数替换过去
    • 存在量词不在全称量词的辖域内:新的个体常量替换受该量词约束的变元
    • 存在量词位于一个或者多个全称量词的辖域内:要用Skolem函数f(x1, x2,…, xn)替换受该存在量词约束的变元
    • 存在量词 (∃y) 及 (∃z) 都位于 (∀x) 的辖域内, 所以需要用Skolem函数替换,设替换 y 和 z 的 Skolem 函数分别是 f(x) 和 g(x)
  5. 全程量词左移

    image-20191209172647328image-20191209172702500

  6. 化为 Skolem 标准形

    image-20191209172647328image-20191209172702500

    • Skolem 标准形:image-20191209173036291
  7. 消全称量词,变元更名,不同子句中变元不同名

    image-20191209173050745

  8. 消合取量词

    image-20191209173101989

海伯伦理论

为了判断子句集的不可满足性,需要对所有可能论域上的所有解释进行判定,只有当子句集对任何非空个体域上的任何一个解释都是不满足的,才可断定该子句集是不可满足的。

海伯伦构造了一个特殊的论域,并证明只要对这个特殊域上的一切解释进行判定,就可知道子句集是否不可满足

II. 子句集的化简

本部分的目标是合并相似子句,精简子句集

i. 变量代换

image-20191209191843362

  • t:常量、变量、函数
  • x:变元
  • 用 t 替换 x (用特殊替换一般
  • t、x 不能相同
  • x 不能出现在另一个 t 中 例: {g(y)/x, f(x)/y} 不是代换

ii. 代换复合

image-20191209192445915

tλ:对 t 用 λ 进行代换

举例:

image-20191209192531135

iv. 公式集的合一

image-20191209193244293

合一不唯一,就是不停代换

举例:

image-20191209193323962

v. 最一般的合一

image-20191209193416939

求取方法

image-20191209193441555

III. 鲁滨逊归结原理(重要)

归结证伪

思路:检查子句集 S 中是否包含空子句
空子句永远无法满足,所以 S 中有空子句就肯定不可满足

  • 若存在,S 不可满足
  • 不包含:在子句集中选择合适子句归结
    • 归结出空子句,S不可满足
    • 无法归结出空子句,S 可满足

i. 归结

找矛盾,证明不可能

image-20191209194822379

例1

代换归结

image-20191209195506363

例2

合一归结

image-20191209195630691

例3

若子句含有可合一的文字,则先进行合一再归结

image-20191209195719589

ii. 归结反演证蕴含

image-20191209195940141

iii. 归结优化

一般归结过程

image-20191209200237902

删除策略

删除某些无用子句缩小归结范围

  • 纯文字删除法

    • 纯文字:某文字 L 在子句集 S 中不存在互补的文字 ¬L
    • 删除:包含纯文字的子句(因为永远删不空)
  • 重言式删除法

    • 重言式:某子句同时包含互补的文字
    • 删除:包含重言式的子句(因为该子句永真)
  • 包孕删除法:就是删除可被替代的子句

    image-20191209200346441

限制策略

限制参加归结的子句,减小归结盲目性

  • 支持集策略:每次归结的亲本子句中至少有一个是由目标公式的否定所得到的子句,或者是它的后裔,该策略完备

    image-20191209200517159

  • 线性输入策略:参加归结的两个子句中至少有一个是初始子句集中的子句,该策略效率高但是不完备

    img

  • 祖先过滤策略

    • C1, C2, 满足任意一个条件:
    • \1. C1和C2中至少有一个是初始子句集中的 子句
    • \2. C1和C2中一个是另外一个的祖先子句
    • 评价:完备
  • 单文字子句策略

    • 如果一个子句只包含一个文字,则称它为单文字子句
    • 参加归结的两个子句中必须至少有一个 是单文字子句。
    • 评价
    • 用单文字子句策略归结时,归结式比亲本子句 含有较少的文字,这有利于朝着空子句的方向 前进,因此它有较高的归结效率
    • 这种归结策略是不完备的。当初始子句集中不包含 单文字子句时,归结就无法进行。

IV. 实际应用

求解步骤

  1. 已知前提用谓词公式表示出来,化为子句集 S
  2. 待求解的问题也用谓词公式表示出来,然后把它否定,并与谓词Answer构成析取式。 Answer 是一个为了求解问题而专设的谓词。把上述析取式化为子句集,并且把该子句集并入到子句集S中,得到子句集S’
  3. 对S’ 归结。
  4. 若得到归结式Answer,则可获得答案

经典例题

image-20191209201045282
image-20191209201222567

3. 不确定性推理

发生某件事的前提下,推理发生另一间事的概率

  • 静态强度:数值,知识 H 的不确定性程度,P(H|E),CF(H, E)

  • 动态强度:T(E),证据 E 的不确定性程度,P(E|S),CF(E)

  • 匹配度:推理过程中证据知识的前提相似程度

  • 不确定性匹配算法:确定匹配度的算法

  • 组合证据不确定性 T

    • 最大最小法

    img

    • 概率法

    img

    • 有界法

    img

I. 基本概率方法

模型:IF E THEN H

  • E:证据,evidence
  • H:结论,hypothesis
  • P(H | E):E 出现时 H 的确定性程度

逆概率公式

image-20191209212800510

II. 主观 Bayes 方法

模型:IF E THEN (LS, LN) H(P(H))

  • P(H):H 的先验概率,专家给出

  • LS:充分性度量,[0, +∞),E => H 程度,专家给出

    img

  • LN:必要性度量,[0, +∞),E <= H 程度,专家给出

    img

  • LS, LN 又称知识的静态强度

    • LS>1: 证据 E 是对 H 有利的证据
    • LS<1: 证据 E 是对 H 不利的证据
    • LN>1: 证据 ¬E 是对 H 有利的证据
    • LN<1: 证据 ¬E 是对 H 不利的证据
    • 不能出现 LS>1 且 LN>1 的取值
    • 不能出现 LS<1 且 LN<1 的取值

E 的不确定性 P(E|S)

证据 E 不是可以直接观测的情况,使用观测值 S 来估计 E,这个估计有一个准确率,为 P(E|S),为知识的动态强度

如果 E 由多个证据合成:,则:

image-20191209222621218

H 的不确定性 P(H|S)

首先介绍一下几率函数,是表示概率的另外一种方法

image-20191209215833011

然后进行分类讨论:

  • P(E|S) = 1,证据完全没毛病:

    image-20191214223952314

  • P(E|S) = 0,证据压根就是个错哒,所以直接使用 E 的否定:

    image-20191214224031470

  • P(E|S) = P(E),S 和 E 就没关系,进而 S 和 H 也就没关系:

    image-20191214224140525

  • 其他情况,使用分段线性插值(其实就是分段函数,两点式求函数)的方法可求得,称为 EH 公式:

    image-20191209222504925

ps:上述 EH 公式用也可使用几率函数表示

如果有多个证据支持结论,则可用下公式复合:

image-20191209223212083

III. 可信度方法

可信度:根据经验对一个事物和现象为真的相信程度称为可信度,在可信度方法中,由专家给出规则或知识的可信度,从而可避免对先验概率、或条件概率的要求, C(E|S) 替代 P(E|S),简化了模型

image-20191209223805682
image-20191209223955438

模型:IF E THEN H (CF(H, E))

  • CF(H,E):知识的可信度,取值 [-1, 1]
    • = 1, 对应 P(H|E) = 1
    • = -1,对应 P(H|E) = 0
    • = 0,对应 P(H|E) = P(H)

E 的不确定性 CF(E)

知识的动态强度,取值 [-1, 1]

  • CF(E) > 0: E 以某种可信度为真
  • CF(E) < 0: E 以某种可信度为假

如果 E 由多个证据合成:

image-20191210082955790

H 的不确定性 CF(H)

image-20191210083214273

如果有多条知识支持结论,则需要合成一下:

image-20191210083427633
image-20191210083453662

IV. 带阈值限度的可信度方法

模型:IF E THEN H (CF(H,E), λ)

  • C(H,E):知识可信度,取值 [0,1]
  • λ:阈值,取值 [0,1],只有当 CF(E) ≥ λ 时,该知识被应用

H 的不确定性 C(H)

CF(E) ≥ λ 时,

image-20191210083214273

如果有多条知识支持结论,则可采用以下几种办法合成:

  • 极大值法 img
  • 加权求和法 img
  • 有限和法 img
  • 递推法 img

V. 加权可信度方法

模型:IF E1(w1) AND E2(w2) AND ... AND En(wn) THEN H (CF(H,E), λ)

  • wn:第 n 个证据的权值,取值范围 [0,1]

E 的不确定性 C(E)

image-20191210091902827

H 的不确定性 CF(H)

CF(E) ≥ λ 时,

image-20191210083214273

VI. 前件带不确定性的可信度方法

模型

IF E1(cf1, w1) AND ... AND En(cfn, wn) THEN H (CF(H,E), λ)

E1(cf'1), ... , En (cf'n)

  • cfn:第 n 个 E 的要求可信度,取值 [0,1]
  • cf'n:第 n 个 E 的可信度,取值 [0,1],知识的动态强度

H 的不确定性 C(H)

image-20191210094329134

image-20191210094645436

4. 模糊推理

借鉴一段比较接近的知识,推理出欲求结论

I. 模糊集

隶属函数image-20191210095710748,将论域 U 中任意元素映射到 [0,1] 上的函数

模糊集image-20191210095837806,隶属函数的集合,多用image-20191210100757012

隶属度image-20191210095918365 称为 u 对 A 的隶属度

表示方法

image-20191210100519973

举个具体的例子:

image-20191210100452343

运算

  • 包含:若image-20191210100943414 ,则 image-20191210101024778
  • 交:image-20191210101050357
  • 并:image-20191210101102587
  • 补:image-20191210101117793

匹配度

指两个模糊集的相似程度,为 1 - d(A, B),其中 d(A, B) 为语义距离,由多种计算方法:

  • 海明距离

    img

  • 欧几里得距离

    img

  • 明可夫斯基距离

    img

  • 切比雪夫距离

    img

II. 多元模糊关系

n 元模糊关系 R:论域 U1× ... × Un 上的模糊集,通过 A1, ..., An 的笛卡尔乘积得到:

image-20191210104719650

ps: 所谓 image-20191210104139651 , 其实就是针对每个 u 选最小的隶属度

现在将维数降至二维,看看一个二元模糊关系长什么样子:

image-20191210102953658

模糊关系的合成

设 R1 与 R2 分别是 U × V 与 V × W 上的两个模糊关系,则 R1 与 R2 的合成就是将合成一个论域为 U × W 的新模糊关系 R1 ◦ R2 ,隶属函数为:

image-20191210103605437

运算法则其实和矩阵非常像:

例 1

image-20191210103639264

例 2

image-20191210104929824

III. 简单模糊推理

模糊命题:x is A

  • x:谈论对象
  • A:模糊概念,可用模糊集表示
  • 举例:Bob is young

推理模型:IF x is A THEN y is B

观察到的总不会和 A 一模一样,所以记为 A‘,只要 A’ 和 A 的匹配度达到一定值,就能代表 A,当然,使用 A' 推导出的也只能是一个和 B 近似的 B‘

  1. 求 A 、B 间的模糊关系 R
  2. R 与证据的合成求出模糊结论
    • 假言推理:x is A => y is B,使用 B' = A' ◦ R
    • 拒绝式推理:y is B => x is A,使用 A' = R ◦ B'

模糊关系的构造方法

  • 扎德法

    • 极大极小规则:image-20191210111633388
    • 算数规则:image-20191210111657325
  • Mamdani 法:image-20191210113210803

  • Mizumoto 法:image-20191210113320133

例1(使用扎德法)

image-20191210111754714

  1. 算 R:

    image-20191210112116032

  2. 假言推理

    image-20191210112730142

  • 若将题目证据改为:image-20191210112901583,就需要使用拒绝式推理:

    image-20191210113047544

构造方法的评测

准确性评测

首先定义几个形容词:very, more or less, not, not very, not more or less:

  • image-20191210141203509
  • image-20191210141227003
  • image-20191210141327894
  • image-20191210141348873
  • image-20191210141405258

然后,判定一个模糊关系的构造方法针对某一情况靠不靠谱,需要从以下八个原则进行逐一诊断:

  • 原则 1:x is A => y is B
  • 原则 2:x is very A => y is very B / y is B
  • 原则 3:x is more or less A => y is more or less B / y is B
  • 原则 4:x is not A => y is unknown / y is not B
  • 原则 5:y is not B => x is not A
  • 原则 6:y is not very B => x is not very A
  • 原则 7:y is not more or less B => x is not more or less A
  • 原则 8:y is B => x is unknown / x is A

举个例子,用以下实例评测各方法准确性:

image-20191210142029601

  1. 先算用各种乱七八糟的方法算下 R

    image-20191210142414672

  2. 再算下那些 not、very 啥的

    image-20191210142601385

  3. 对照原则,得出评价表,复合原则越多,证明该方法效果在当前情况效果越好

    image-20191210143242750

模糊三段论评测

image-20191210143805653

经过计算,发现不是所有模糊关系构造法构造出的模糊关系都具有传递性的:

image-20191210143922334

IV. 知识前件为复合条件的模糊推理

image-20191210144153306

扎德法

  • A = A1 ∩ ... ∩ An
  • A' = A1' ∩ ... ∩ An'

image-20191210151158633

祖卡莫托法

  • 算出 R(Ai, B),i = 1,2,...,n
  • 算出 Bi'
  • B' = B1' ∩ ... ∩ Bn'

V. 多重模糊推理

image-20191210152407775

为了简化模型,讨论最简单的形式:IF x is A THEN y is B ELSE y is C,其中 A, A' ∈ F(U); B, C, D ∈ F(V)

目标:x is A' => y is D

思路:还是通过各种方法构造 R,然后推得 D,看 D 和 B、C 哪个匹配度高

VI. 带有可信度因子的模糊推理

带上可信度因子主要是增加了结论的可信度评价标准

单一证据

image-20191210152038190

组合证据

image-20191210152056009