PDF《高级人工智能》

归纳学习 Inductive Learning 史忠植 中国科学院计算技术研究所 高级人工智能

第七章 2015/4/15 史忠植 高级人工智能

2 内容提要 7.

1 归纳学习的逻辑基础 7.2 偏置变换 7.3 变型空间方法 7.4 AQ归纳学习算法 7.5 产生与测试方法 7.6 决策树学习 7.7 可学习的计算理论 2015/4/15 史忠植 高级人工智能

3 概述给定关于某个概念的一系列已知的正例和反例, 其任务是从中归纳出一个一般的概念描述.归纳学 习能够获得新的概念,创立新的规则,发现新的理 论. 泛化(generalization)用来扩展一假设的语义信息, 以使其能够包含更多的正例,应用于更多的情况. 特化(specialization)是泛化的相反的操作,用于 限制概念描述的应用范围. 2015/4/15 史忠植 高级人工智能

4 归纳学习的一般模式 给定: ① 观察语句集(事实)F:这是有关某类对象中个别 具体对象的知识或某一对象的部分特征的知识. ② 假定的初始归纳断言(可空):是关于目标的泛化项或泛化描 述. ③ 背景知识:背景知识定义了在观察语句和所产生的候选归纳 断言上的假定和限制,以及任何有关问题领域知识.有关问题领 域知识包括特化所找归纳断言的期望性质的择优标准. 寻找: 归纳断言H(hypothesis), H 重言或弱蕴涵观察语句并满足背景 知识. 2015/4/15 史忠植 高级人工智能

5 基本符号表 ~ 非 &

合取(逻辑乘) ? 析取(逻辑加) ? 蕴涵 ? 逻辑等价 ? 项重写 ? 异或 F事实集 H 假设 |>

特化 |<

泛化 2015/4/15 史忠植 高级人工智能

6 基本符号表 |= 重新形式化 ?vi存在量词约束变项vi ?Ivi 数值存在量词约束变项vi ?vi 全称量词约束变项vi Di 概念描述 Ki 判断一个概念的名字的谓词 ::>

将概念描述与概念名连接的蕴涵 ei 一个事件(对一种情况的描述) Ei 仅对概念ki的事件为真的谓词 Xi 属性 LEF 评价函数 DOM(P) 描述符P的定义域 2015/4/15 史忠植 高级人工智能

7 概念获取 概念获取的一类特殊情况,它的观察语句集F是一个 蕴涵的集合, 其形式如下: F: {eik ::>

Ki} i ? I 其中,eik(Ki的训练事件)是概念Ki的第k个例子的符 号描述.概念的谓词Ki, I是Ki的下标集合. eik ::>

Ki的含义是 凡符合描述eik的事件均可被 断言为概念Ki的例子. 2015/4/15 史忠植 高级人工智能

8 概念获取 学习程序要寻求的归纳断言H可以用概念识别规则集来 刻画, 形式如下: H:{Di ::>

Ki} i ? I 其中Di是概念Ki的描述,即表达式Di是事件的逻辑推论, 该事件可被断言为概念Ki的一个例子. 2015/4/15 史忠植 高级人工智能

9 完整性条件 ? i ? I (Ei ? Di) 2015/4/15 史忠植 高级人工智能

10 一致性条件 ? i,j ? I (Di ? ~ Ej), 若i?j2015/4/15 史忠植 高级人工智能

11 描述符类型 (1) 名称性描述符.这种描述符的定义域由独立的 符号或名字组成,即值集中值之间没有结构关系. 例如水果、人名等. (2) 线性描述符.该类描述符值集中的元素是一个 全序集.例如,资金、温度、重量、产量等都是线 性描述符.表示序数、区间、比率和绝对标度的变 量都是线性描述符的特例.将一个集合映射成一个 完全有序集的函数也是线性描述符. 2015/4/15 史忠植 高级人工智能

12 描述符类型 (3) 结构描述符.其值集是一个树形的图结构, 反映值之间的生成层次. 在这样的结构中,父节点表示比子节点更一般的 概念.例如,在 地名 的值集中, 中国 是节 点 北京 、 上海 、 江苏 、 广东 等的 父节点. 结构描述符的定义域是通过问题背景知识说明 的一组推理规则来定义的.结构描述符也能进一步 细分为有序和无序的结构描述符.描述符的类型对 确定应用描述符的操作是很重要的. 2015/4/15 史忠植 高级人工智能