人智导（十七）：基于知识的方法

人智导（十七）：基于知识的方法

基于知识的智能体

• 智能体感知(perceiving)环境后决定在环境中如何行动
• 决策(decision making)：基于知识(knowledge)
• 知识表示与自动推理：表示语言(inference-capable representation)
• 智能体（知识系统）：知识库(KB) + 推理引擎(IE)

基于知识的智能体设计

• 知识库：世界中的事实和规则的集合（集合中的每一个元素我们称之为句子）
• 需要一种语言来构造句子（知识表示语言knowledge representation)
• 构造一个基于知识的智能体(KB-Agent)：
  • 需要有一种方式能增加新句子到知识库中
  • 需要有一种方式能实现问题(query)的解答（基于知识）

基于知识的智能体程序框架

Function KB-Agent(precept) returns an action
	static: KB
	        t
	TELL(KB, MAKE-PERCEPT-SENTENCE(percept, t))
	action <--- ASK(KB, MAKE-ACTION-QUERY(t))
	TELL(KB, MAKE-ACTION-SENTENCE(action, t))
	t <--- t+1
	return action
1
2
3
4
5
6
7
8

智能体与其知识库进行问与答的过程：

• 智能体告诉(tell)知识库，感知到了什么；然后询问(ask)知识库，应当如何行动
• 知识库根据它的知识给出回答(answer)
• 推理(inference)的细节：隐含于过程TELL与ASK中
• 表示(representation)的细节：隐含于两个MAKE函数中

基知识的智能体构建

基于知识的智能体构建，通过TELL告诉其需要知道的：

• 通过句子描述（表示知识），并且逐句地添加到知识库KB中（背景知识background knowledge）
• 构建的过程应尽可能简单，以句子的形式易于表示知识

推理示例：“魔怪世界”

魔怪世界：展示了推理的动机

情境的描述

• 感知(percepts)：stench, breeze, glitter, bump, cream 例如元组[stench, breeze, glitter, no bump, no scream]
• 动作(actions)：go forward, turn right, turn left, grab, shoot, limb
• 目标(goals)：没有被魔怪吃掉或没有落入陷阱，并获取到金子返回初始位置
• 环境(environment)：
  • 完全可观测？no
  • 动作的效果确定？yes
  • 环境是静态的？yes，魔怪和陷阱位置不变
  • 离散性的？yes

游戏中的推理

初始状态：在格子[1, 1], no stench, no breeze
推理出结论“陷阱在[3, 1]”：组合了在不同时间，不同地点获得的知识

知识表示语言

智能体具备知识

• 需要一种合适的表示知识语言
  • 知识(knowledge)能被显式地表示出来(represented explicitly)
  • 表示的语言可提供进行自动推理的机制(inference mechanism)
• 知识表示与自动推理：构建知识系统的关键

表示语言

• 自然语言(nature language)（中文、英文等等）
  • 极强的表达能力
  • 情境上下文依赖的(context-dependent)
  • 更多的是通讯的属性，而非仅仅表示
  • 多义性
• 程序设计语言（如C，Java等等）
  • 精确表示，例如$world[2,2]\leftarrow Pit$语义精确：[2,2]有陷阱
  • 不适于不精确和不完整的表示，例如：某些格子里有陷阱，[3,1]或[2,2]可能有陷阱
  • 表达能力不足
• 知识表示语言
  • 句子与事实间通过语言的语义(semantics)进行对应解释
  • 推理：能通过已知的句子推导出它们蕴含(entail)的新句子

知识表示语言的属性

• 结合自然语言和程序语言的优势
  • 强的表达性和简洁
  • 无二义性且情境上下文独立(independent of context)
• 句子组合型
  • 简单句可组合成复合句
  • 复合句的语义是其组成部分（简单句）语义的组合
• 句子之间的蕴含关系：取决于其在语义层面对应的事实间的关联
• 具有推理能力的表示
  • 推断出句子（集合）与句子之间的蕴含关系
  • 推理程序应当能回答任何问题$\alpha$，只要这个问题被知识库KB（句子集合）所蕴含

逻辑：通用知识表示语言

逻辑包括两个部分：

1. 语言，用以描述客观世界中的事实
   • 句法(syntax)：如何构造句子
   • 语义(sementics)：句子与具体事实间的系统性约束
2. 验证的理论(proof theory)
   • 通过给定的句子集（前提）推断出该句子集所蕴含的句子（结论）

机器推理

• 永真性(Validity)和不可满足性(Usatisfiability)
  • 永真性：在世界中所有可能的解释下都是真的，例如：格子[1,1]中有陷阱或没有陷阱
  • 不可满足性：在世界中所有可能的解释下都是假的
• 永真性与不可满足性：实现计算机推理的关键
• 机器推理的局限：机器不能理解句子本身所表达的含义
  魔怪世界中，如果问“探宝者进入格子[2,2]是否OK？”([2,2] is OK?)
  机器仅能做到的：
  判断句子"[2,2] is OK"是否被知识库(KB)所蕴含，亦即，句子"if KB is true then [2,2] is OK"是否是永真的
  逻辑推理：基于永真性的形式化推理
• 一个句子是永真的(valid)，当且仅当在所有解释情况下句子都是真(true)，例如$A\vee \neg A$
• 基于永真性的推理：KB蕴含$\alpha$当且仅当句子$KB\Rightarrow \alpha$是永真的
• 一个句子是不可满足的，当且仅当没有任何情况使得句子是真(true)，例如$A\wedge \neg A$ KB蕴含$\alpha$当且仅当句子$KB\wedge \neg \alpha$是不可满足的

机器自动推理的本质意义

• 句子的复杂性方面是没有限制的
  知识库可组合成一个句子，即构成复合句"if KB then P"
• 机器推理的特点：
  • 机器在完全不知句子的含义及其解释的情况下，可以推断出永真的结论
  • 而人是知道具体含义和解释的，所以机器推理出的结论对人而言是有意义的
• 自动推理的本质：通过纯机械的方式来验证句子的永真性
  [2, 2] is OK? 问题解答为 if KB then "[2, 2] is OK"的永真判断

智能体的逻辑推理

命题逻辑

基本概念

Propositions（命题）

• 在客观世界中成立或者不成立
• 每个命题有两种状态：真(true)或者假(false)

语法

原子(Atom)：常量：真(True)，假(False)；命题符号：P,Q,… （简单句）
联结符(Logical connectives)：组成复合句
$\wedge$（合取），$\vee$（析取），$\Rightarrow$（蕴含），$\iff$（等价），$\neg$（非）
文字(Literal)：是一个正原子或者是一个负原子
合式公式(wff)：（复合）句子

• 原子本身
• 用联结符组合wff

语义

• 解释(Interpretation)：原子和命题间的关联
  例如，P：野兽先辈具有屑鉴二相性
  P的值：真(true)
  明确一个解释，原子即有一个值true或false
• 真值表(Truth table)
  给定所有原子的解释，计算出wff的值
  真值表例：n个命题$2^n$

• 永真性(validty)：在所有可能的解释下句子wff都为真

• 模型(Model)：句子(wff)若在某一解释下为真，这个解释被称作是该句子(wff)的一个模型
• 逻辑蕴含(Entailment):
  $\Delta$：一系列句子的集合(wffs)（知识库）；一个句子$\alpha$被$\Delta$逻辑所蕴含，如果$\Delta$的模型也是$\alpha$的模型。$\alpha$称为$\Delta$的逻辑结论 $$\Delta \models \alpha$$

推理规则(Inference Rules)

假言推理(Modus Ponens)：$$\frac{\alpha \to \beta ,\alpha }{\beta }$$
析取引入(Or-Introduction)：$$\frac{{\alpha }_i}{{\alpha }_1\vee {\alpha }_2\vee \cdots \vee {\alpha }_n}$$
合取消除(And-Elimination)：$${\frac{{\alpha }_1\wedge {\alpha }_2\wedge \cdots \wedge {\alpha }_n}{{\alpha }_i}}_{i=1,\dots ,n}$$
非消除(Double-Negation Elimination)：$$\frac{\neg \neg \alpha }{\alpha }$$
合取引入(And-Introduction)：$$\frac{{\alpha }_1,{\alpha }_2,\dots ,{\alpha }_n}{{\alpha }_1\wedge {\alpha }_2\wedge \cdots \wedge {\alpha }_n}$$
归结(Resolution)：$$\frac{\alpha \vee \beta ,\neg \beta }{\alpha }$$ $$\frac{\alpha \vee \beta ,\neg \beta \vee \gamma }{\alpha \vee \gamma }$$

演绎/证明(decuction/proof)

$\Delta$：一系列句子的集合(wffs)
$\Re$：一系列的推理规则
一个句子(wff)$\alpha$是句子集合$\Delta$的一个演绎（或验证），当且仅当$\alpha$能够通过$\Re$从$\Delta$推导出（$\alpha$称为$\Delta$的一个定理）。即KaTeX parse error: Expected '}', got 'EOF' at end of input: …ash _{\Re\alpha
推理程序：构建这样一个证明，发现一个合适的推理规则应用的步骤序列

推理的合理性和完备性

• $\mathfrak{R}$推理过程的合理性soundness:
  若$\Delta {⊢}_{\Re }\alpha$，则$\Delta \models \alpha$
• $\mathfrak{R}$推理过程的完备性completeness：
  若$\Delta \models \alpha$，则$\Delta {⊢}_{\Re }\alpha$

具备逻辑推理能力的智能体

• 知识库(KB)
  描述感知（事实）的句子：
  $\neg S1.1$ $\neg B1.1$
  $\neg S2.1$ $B2.1$
  $S1.2$ $\neg B1.2$
  描述环境背景知识（规则）的句子
  $R1:\neg S1.1\to \neg W1.1\wedge \neg W1.2\wedge \neg W2.1$
  $R2:\neg S2.1\to \neg W1.1\wedge \neg W2.1\wedge \neg W2.2\wedge \neg W3.1$
  $R3:\neg S1.2\to \neg W1.1\wedge \neg W1.2\wedge \neg W2.2\wedge \neg W1.3$
  $R4:S1.2\to W1.3\vee W1.2\vee W2.2\vee W1.1$
• 知识库中给定了这些句子，智能体如何判断出W1.3（魔怪在格子[1, 3]中）
  • 构建真值表，判断句子$KB\to W1.3$永真
    共有12个命题，真值表有$2^{12}=4096$行
  • 逻辑推理

总结

• 基于知识的方法：智能体决策需要知识
• 基于知识的智能体包括两个组成部分：知识库和推理引擎
• 知识的表示需要特定语言，知识以句子的形式显式表示并存储于知识库中
• 智能体基于知识库中的知识（句子），推导出逻辑结论（新句子），以此决定如何行动
• 机器推理的本质是永真性的验证
• 命题逻辑：简单的表示语言，但已足够于展现推理的能力