《人工智能》之《知识表示方法》
知识是一个抽象的术语，用于尝试描述人对某种特定对象的理解。
知识的定义
知识的一般概念：知识是人们在改造客观世界的实践中积累起来的认识和经验。
知识的代表性定义：
- 知识是经过裁剪、塑造、解释、选择和转换的信息（Feigenbaum）；
- 知识由特定领域的描述、关系和过程组成（Bernstein）；
- 知识=事实+信念+启发式（Heyes Roth）。
知识、信息、数据的关系：
知识的类型
按知识的性质：概念、命题、公理、定理、规则和方法。
按知识的作用域：
- 常识性知识：通用通识的知识，人们普遍知道的、适用于所有领域的知识；
- 领域性知识：面向某个具体专业领域的知识。
按知识的作用效果：
- 事实性知识：用于描述事物的概念、定义、属性等，或用于描述问题的状态、环境、条件等的知识；
- 过程性知识：用于问题求解过程的操作、演算和行为的知识，或指出如何使用那些与问题有关的事实性知识的知识；
- 控制性知识：(元知识或超知识)。是关于如何使用过程性知识的知识。例如：推理策略、搜索策略、不确定性的传播策略。
按知识的确定性：
- 确定性知识：可说明其真值为真或为假的知识；
- 不确定性知识：包括不精确、模糊、不完备知识。
1.不精确：知识本身有真假，但由于认识水平限制却不能肯定其真假；
表示：用可信度、概率等描述
2.模糊：知识本身的边界就是不清楚的。例如：大，小等；
表示：用可能性、隶属度来描述
3.不完备：解决问题时不具备解决该问题的全部知识。例如：医生看病。
知识表示
- 对知识的一种描述；
- 一种计算机可以接受的用于描述知识的数据结构；
- 表示方法不唯一；
- 是人工智能的核心。
知识表示的要求
- 表示能力：能否正确、有效地表示问题。包括：
表达范围的广泛性
领域知识表示的高效性
对非确定性知识表示的支持程度 - 可利用性：可利用这些知识进行有效推理。包括：
对推理的适应性：推理是根据已知事实利用知识导出结果的过程
对高效算法的支持程度：知识表示要有较高的处理效率 - 可实现性：要便于计算机直接对其进行处理
- 可组织性：可以按某种方式把知识组织成某种知识结构
- 可维护性：便于对知识的增、删、改等操作
- 自然性： 符合人们的日常习惯
知识表示存在的问题
- 人是如何表示知识，存储知识的仍然是个迷；
- 目前用计算机来进行知识处理面临三大难题：
1. “Clear-Cut”问题：主要处理可形式化的边界清晰问题；
2. 知识获取瓶颈：很难把现实中的知识转化为计算机可理解的知识；
3. 知识窄台阶：多为专家系统知识，缺乏常识性知识。
如何让机器理解下面的故事？
主人让小马托着两袋盐巴过河，他不小心把一部分浸到了河里。于是盐巴融化在河里一部分，盐袋子也变轻了。小马很开心，得意洋洋地回家了。
第二次，主人又给小马托起棉花过河。小马想起来上次，故意把棉花都浸到了河里。结果，小马沉得要死，死扛着回家了。
如何让机器理解如此场景？
我们不是音频分析的手段来实现对贝多芬音乐的欣赏，也不是用视频分析的手段来实现对梵高油画的欣赏”（杨雄里院士）。
这其中蕴含深刻的整合过程，因此必然涉及大量的背景知识和感知经验。
人的概念系统
- 人的概念系统是非任务特定性的，具有很强的通用性。正是这种不局限于特定目标的特性，使人可以处理各种各样问题（通用人工智能的目标）；
- Nisson认为“人工智能最重要的部分就是发现一个适用的概念化知识结构。”（建立一套基于统一认知理论的计算模型，即基于单一结构上多个程序的认知模型）。
1 状态空间法（State Space Representation）
许多问题的求解方法是试探搜索方法。这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符为基础来表示和求解问题的。
状态(state)：表示问题解法中每一步问题状况的数据结构；
算符(operator)：把问题从一种状态变换为另一种状态的手段（或操作）。
1.1 问题状态描述
定义：
- 状态(State)：描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合,即(n+1)维向量。
- 算符(Operate)：使问题从一种状态变化为另一种状态的手段，也称操作符。
- 状态空间(State Space)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、操作符集合F以及目标状态集合G，即三元状态（S，F，G）。
要完成某个问题的状态描述，必须：
- 该状态描述方式，特别是初始状态描述；
- 操作符集合及其对状态描述的作用；
- 目标状态描述的特性。
1.2 状态图示法
有关图的知识：《软件技术基础》之《图》
图的显示说明：对于显式说明，各节点及其具有代价的弧线由一张表明确给出。此表可能列出该图中的每一节点、它的后继节点以及连接弧线的代价(相关知识：D是邻接矩阵, 如何求i,j的最短距离？)
图的隐示说明：已知起始节点｛si｝和后继节点算符 Γ。 后继节点算符能作用于任一节点以产生该节点的
- 全部后继节点
- 各连接弧线的代价(例如：棋局）
寻找一种状态到另一种状态的算符序列等价于寻找图上的最短路径问题。
表示方法的多样性： 如3数码难题中
- 规则1：移动数码（3X4条规则）
- 规则2：移动空格（4条规则）
应该选择小而简单的状态空间。
1.3 示例：修道士(Missionaries)和野人(Cannibals)问题
问题描述
设在河的一岸有三个野人、三个修道士和一条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：
- 修道士和野人都会划船，每次船上至多可载两个人；
- 在河的任一岸，如野人数超过修道士数，修道士会被野人吃掉。
如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。
状态表示
用一个三元组来表示状态：S=(m, c, b)
| 集合 | 说明 |
|---|---|
| m | 左岸的修道士人数 (missionary ） |
| c | 左岸的野人数 (cannibal) |
| b | 左岸的船数 （bank) |
右岸的状态可由下式确定：
| 状态 | 式 |
|---|---|
| 右岸修道士数 | m’=3-m |
| 右岸野人数 | c’=3-c |
| 右岸船数 | b’=1-b |
该表示方式下，m，c都可取0、1、2、3，b可取0和1，共有4×4×2=32种状态，如下所示：
操作集
状态空间
给出状态和操作的描述之后，该问题的状态空间是：
状态空间图
2 问题归约法（Problem Reduction Representation）
问题归约法是另一种基于状态空间的问题描述与求解方法。已知问题的描述， 通过一系列变换把此问题最终变为一个本原问题集合；这些本原问题的解可以直接得到，从而解决了初始问题。
2.1 问题归约描述
问题归约法由3部分组成：
- 一个初始问题描述；
- 一套把问题变换为子问题的操作符；
- 一套本原问题描述。
问题归约法的实质：
从目标（要解决的问题）出发逆向推理，建立子问题以及子问题的子问题，直至最后把初始问题规约为一个平凡的本原问题集合。
归约方式
- 分解
- 等价变换
2.2 示例：梵塔难题（Tower of Hanoi Puzzle）
问题描述
有3个柱子(1，2，3)和3个不同尺寸的圆盘(A，B，C)。在每个圆盘的中心有个孔，所以圆盘可以堆叠在柱子上。最初，全部3个圆盘都堆在柱子1上：最大的圆盘C在底部，最小的圆盘A在顶部。要求把所有圆盘都移到柱子3上，每次只许移动一个，而且只能先搬动柱子顶部的圆盘，还不许把尺寸较大的圆盘堆放在尺寸较小的圆盘上。
归约过程
- 移动圆盘A和B至柱子2的双圆盘难题；
- 移动圆盘C至柱子3的单圆盘难题；
- 移动圆盘A和B至柱子3的双圆盘难题。
由上可以看出简化了难题每一个都比原始难题容易，所以问题都会变成易解的本原问题。
归约描述
问题归约方法是应用算符来把问题描述变换为子问题描述。
可以用状态空间表示的三元组合(S、F、G)来规定与描述问题；
对于梵塔问题，子问题[(111)→(122)]，[(122)→(322)]以及[(322)→(333)]规定了最后解答路径将要通过的脚踏石状态(122)和(322)。
问题归约方法可以应用状态、算符和目标这些表示法来描述问题，这并不意味着问题归约法和状态空间法是一样的。
梵塔问题归约图
2.3 与或图表示
与图、或图、与或图
我们用一个似图结构来表示把问题归约为后继问题的替换集合，这一似图结构叫做问题归约图，也叫与或图。