机器学习入门介绍

Artificial Intelligence Principles and Applications 第 7 章 机 器 学 习 (Machine Learning) 桑 克 （ R. Shank)： “ 一 台 计 算 机 若 不 会 学 习 ， 就 不 能 说 它 具有 智 能 。 ” 2 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 机 器 学 习 的 基 本 概 念 3 7.1 机 器 学 习 的 基 本 概 念7.1.1 学 习7.1.2 机 器 学 习7.1.3 机 器 学 习 系 统7.1.4 机 器 学 习 的 发 展7.1.5 机 器 学 习 的 分 类 4 7.1.1 学 习（ 1） 学 习 是 系 统 改 进 其 性 能 的 过 程 ： 西 蒙 ， 1980。（ 2） 学 习 是 获 取 知 识 的 过 程 。（ 3） 学 习 是 技 能 的 获 取 。（ 4） 学 习 是 事 物 规 律 的 发 现 过 程 。 学 习 ： 一 个 有 特 定 目 的 的 知 识 获 取 过 程 。 内 在 行 为 ： 获 取 知 识 、 积 累 经 验 、 发 现 规 律 。 外 部 表 现 ： 改 进 性 能 、 适 应 环 境 、 实 现 系 统 的 自 我 完 善 。 “学 习 是 系 统 中 的任 何 改 进 ， 这 种 改进 使 得 系 统 在 重 复同 样 的 工 作 或 进 行类 似 的 工 作 时 ， 能完 成 得 更 好 。 ”例 如 “ 小 孩 学 走 路 ” 、“ 学 弹 钢 琴 ” 等 。学 习 ： 从 感 性 知 识 到 理 性 知 识 的 认 识 过 程 ， 从 表 层 知识 到 深 层 知 识 的 转 换 过 程 。 5 7.1 机 器 学 习 的 基 本 概 念7.1.1 学 习7.1.2 机 器 学 习7.1.3 机 器 学 习 系 统7.1.4 机 器 学 习 的 发 展7.1.5 机 器 学 习 的 分 类 6 机 器 学 习 (Machine Learning)： 计 算 机 能 模 拟 人 的学 习 行 为 ， 自 动 地 通 过 学 习 获 取 知 识 和 技 能 ， 不 断改 善 性 能 ， 实 现 自 我 完 善 。 7.1.2 机 器 学 习1） 学 习 机 理 : 对 学 习 机 制 的 研 究 ， 即 人 类 获 取 知 识 、 技 能 和抽 象 概 念 的 天 赋 能 力 。 2） 学 习 方 法 ： 在 生 物 学 习 机 理 进 行 简 化 的 基 础 上 ， 用 计 算 的方 法 进 行 再 现 。3） 学 习 系 统 ： 根 据 特 定 任 务 的 要 求 ， 建 立 相 应 的 学 习 系 统 。 7 7.1 机 器 学 习 的 基 本 概 念7.1.1 学 习7.1.2 机 器 学 习7.1.3 机 器 学 习 系 统7.1.4 机 器 学 习 的 发 展7.1.5 机 器 学 习 的 分 类 8 1. 机 器 学 习 系 统 的 定 义 学 习 系 统 ： 能 够 在 一 定 程 度 上 实 现 机 器 学 习 的 系 统 。 萨 利 斯 (Saris)的 定 义 （ 1973年 ） ： 能 够 从 某 个 过 程 或 环境 的 未 知 特 征 中 学 到 有 关 信 息 ， 并 且 能 把 学 到 的 信 息 用于 未 来 的 估 计 、 分 类 、 决 策 或 控 制 ， 以 便 改 进 系 统 的 性能 。 施 密 斯 等 的 定 义 （ 1977年 ） ： 在 与 环 境 相 互 作 用 时 ， 能利 用 过 去 与 环 境 作 用 时 得 到 的 信 息 ， 并 提 高 其 性 能 。7.1 机 器 学 习 的 基 本 概 念 7. .3 机 器 学 习 系 统 9 2. 机 器 学 习 系 统 的 条 件 和 能 力 （ 1） 具 有 适 当 的 学 习 环 境（ 2） 具 有 一 定 的 学 习 能 力 （ 3） 能 应 用 学 到 的 知 识 求 解 问 题 （ 4） 能 提 高 系 统 的 性 能 7.1.3 机 器 学 习 系 统 10 3. 机 器 学 习 系 统 的 基 本 模 型7.1.3 机 器 学 习 系 统 执 行 与 评 价环 境 学 习 知 识 库学 习 系 统 的 基 本 结 构 11 7.1 机 器 学 习 的 基 本 概 念7.1.1 学 习7.1.2 机 器 学 习7.1.3 机 器 学 习 系 统7.1.4 机 器 学 习 的 发 展7.1.5 机 器 学 习 的 分 类 12 7.1.4 机 器 学 习 的 发 展1. 神 经 元 模 型 的 研 究 （ 20世 纪 50年 代 中 期 ） 主 要 研 究 工 作 ： 应 用 决 策 理 论 的 方 法 研 制 可 适 应 环 境 的 通 用学 习 系 统 （ general purpose learning system） 。 1957年 ， 罗 森 勃 拉 特 （ F. Rosenblatt） 提 出 感 知 器 模 型 。 塞 缪 尔 （ Samuel） 的 跳 棋 程 序 ： 分 析 了 约 175000副 不 同 棋 局后 ， 归 纳 出 了 棋 类 书 上 推 荐 的 走 法 ， 准 确 率 达 到 48 。 1969 年 ， 明 斯 基 和 佩 珀 特 （ Papert ） 发 表 了 论 著 Perceptron ， 对 神 经 元 模 型 的 研 究 作 出 了 悲 观 的 论 断 。 13 7.1.4 机 器 学 习 的 发 展2. 符 号 学 习 的 研 究 （ 20世 纪 70年 代 中 期 ）符 号 概 念 获 取 的 学 习 方 法 （ 1970年 ） ： 模 拟 人 类 的 概念 学 习 过 程 ， 通 过 分 析 一 些 概 念 的 正 例 和 反 例 构 造 出这 些 概 念 的 符 号 表 示 。莫 斯 托 夫 （ D. J. Mostow） 的 指 导 式 学 习 。温 斯 顿 （ Winston） 和 卡 鲍 尼 尔 （ J. G. Carbonell） 的类 比 学 习 。米 切 尔 （ T. M. Mitchell） 等 人 的 解 释 学 习 。 14 7.1.4 机 器 学 习 的 发 展3. 连 接 学 习 的 研 究 （ 20世 纪 80年 代 ） 连 接 学 习 ： 一 种 以 非 线 性 大 规 模 并 行 处 理 为 主 流 的 神经 网 络 研 究 。 1980年 ， 在 卡 内 基 梅 隆 大 学 召 开 了 第 一 届 机 器 学 习国 际 研 讨 会 。 1986年 ， 创 刊 了 第 一 本 机 器 学 习 杂 志 Machine Learning 。 15 7.1 机 器 学 习 的 基 本 概 念7.1.1 学 习7.1.2 机 器 学 习7.1.3 机 器 学 习 系 统7.1.4 机 器 学 习 的 发 展7.1.5 机 器 学 习 的 分 类 16 7.1.5 机 器 学 习 的 分 类 1. 按 学 习 方 法 分 类 （ 温 斯 顿 ， 1977 ） ： 机 械 式 学 习 、 指 导 式 学 习 、 示 例 学 习 、 类 比 学 习 、 解 释 学 习 等 。2. 按 学 习 能 力 分 类 ： 监 督 学 习 （ 有 教 师 学 习 ） 17 7.1.5 机 器 学 习 的 分 类 2. 按 学 习 能 力 分 类 ： 再 励 学 习 （ 强 化 学 习 或 增 强 学 习 ） 18 7.1.5 机 器 学 习 的 分 类 2. 按 学 习 能 力 分 类 ： 非 监 督 学 习 （ 无 教 师 学 习 ）3. 按 推 理 方 式 分 类 ： n 基 于 演 绎 的 学 习 （ 解 释 学 习 ） 。n 基 于 归 纳 的 学 习 （ 示 例 学 习 、 发 现 学 习 等 ） 。4. 按 综 合 属 性 分 类 ：n 归 纳 学 习 、 分 析 学 习 、 连 接 学 习 、 遗 传 式 学 习 等 。 19 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 20 7.2 机 械 式 学 习 机 械 式 学 习 （ rote learning） 又 称 记 忆 学 习 ， 或 死记 式 学 习 ： 通 过 直 接 记 忆 或 者 存 储 外 部 环 境 所 提 供的 信 息 达 到 学 习 的 目 的 ， 并 在 以 后 通 过 对 知 识 库 的检 索 得 到 相 应 的 知 识 直 接 用 来 求 解 问 题 。 机 械 式 学 习 实 质 是 用 存 储 空 间 来 换 取 处 理 时 间 。 21 7.2 机 械 式 学 习 l在 给 定 搜 索 深 度 下 用 估 价 函数 对 格 局 进 行 评 分 ， 通 过 倒推 计 算 求 出 上 层 节 点 的 倒 推值 ， 决 定 当 前 的 最 佳 走 步 。l 下 次 遇 到 相 同 情 况 ， 直 接 利用 倒 推 值 决 定 最 佳 走 步 ， 不需 重 新 计 算 。塞 缪 尔 的 跳 棋 程 序 CHECKERS 以 A 为 结 点 的 博 弈 树QA6 A博 弈 搜 索 树2 B 6 C2 4 8 6 91 2 3 4 3 8 6 5 6 4 9 6 22 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 23 7.3 指 导 式 学 习 指 导 式 学 习 （ learning by being told） 又 称 嘱 咐 式学 习 或 教 授 式 学 习 ： 由 外 部 环 境 向 系 统 提 供 一 般 性的 指 示 或 建 议 ， 系 统 把 它 们 具 体 地 转 化 为 细 节 知 识并 送 入 知 识 库 中 。 在 学 习 过 程 中 要 反 复 对 形 成 的 知识 进 行 评 价 ， 使 其 不 断 完 善 。 指 导 式 学 习 的 学 习 过 程 ： 征 询 指 导 者 的 指 示 或 建议 、 把 征 询 意 见 转 换 为 可 执 行 的 内 部 形 式 、 加 入 知识 库 、 评 价 。 24 7.3 指 导 式 学 习 简 单 征 询 ： 指 导 者 给 出 一 般 性 的 意 见 ， 系 统 将 其 具 体 化 。 复 杂 征 询 ： 系 统 不 仅 要 求 指 导 者 给 出 一 般 性 的 建 议 ， 而且 还 要 具 体 地 鉴 别 知 识 库 中 可 能 存 在 的 问 题 ， 并 给 出 修 改意 见 。 被 动 征 询 ： 系 统 只 是 被 动 地 等 待 指 导 者 提 供 意 见 。 主 动 征 询 ： 系 统 不 只 是 被 动 地 接 受 指 示 ， 而 且 还 能 主 动地 提 出 询 问 ， 把 指 导 者 的 注 意 力 集 中 在 特 定 的 问 题 上 。 1. 征 询 指 导 者 的 指 示 或 建 议 25 7.3 指 导 式 学 习 学 习 系 统 应 具 有 把 用 约 定 形 式 表 示 的 征 询 意 见 转 化 为 计 算 机内 部 可 执 行 形 式 的 能 力 ， 并 且 能 在 转 化 过 程 中 进 行 语 法 检 查 及适 当 的 语 义 分 析 。 2. 把 征 询 意 见 转 换 为 可 执 行 的 内 部 形 式 在 加 入 过 程 中 要 对 知 识 进 行 一 致 性 检 查 ， 以 防 止 出 现 矛 盾 、冗 余 、 环 路 等 问 题 。 3. 加 入 知 识 库 评 价 方 法 ： 对 新 知 识 进 行 经 验 测 试 ， 即 执 行 一 些 标 准 例 子 ， 然 后 检 查 执 行 情 况 是 否 与 已 知 情 况 一 致 。 4. 评 价 26 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 27 7.4 归 纳 学 习7.4.1 归 纳 推 理7.4.2 示 例 学 习7.4.3 观 察 与 发 现 学 习 28 7.4.1 归 纳 推 理归 纳 推 理 ： 应 用 归 纳 方 法 所 进 行 的 推 理 ， 即 从 足 够多 的 事 例 中 归 纳 出 一 般 性 的 知 识 。它 是 一 种 从 个 别 到 一 般 、 从 部 分 到 整 体 的 推 理 。归 纳 推 理 的 重 要 特 征 ： 归 纳 出 的 结 论 不 能 绝 对 保 证它 的 正 确 性 ， 只 能 以 某 种 程 度 相 信 它 为 真 。 例 如 ， 由 “ 麻 雀 会 飞 ” 、 “ 鸽 子 会 飞 ” 、 “ 燕 子 会飞 ” 归 纳 出 “ 有 翅 膀 的 动 物 会 飞 ” 、 “ 长 羽 毛 的 动 物 会 飞 ” 等 结论 。 29 从 个 别 事 例 归 纳 出 一 般 性 知 识 的 方 法 ： 设 ： 某 类 事 物 A中 的 具 体 事 物 。 已 知 都 有 属 性 P， 并 且 没 有 发 现 反 例 。 当 n 足 够 大 时 ， 可 得 出 ： “ A中 所 有 事 物 都 有 属 性 P” 。 7.4.1 归 纳 推 理n21 aaa ， 1. 枚 举 归 纳 n21 aaa ， 30 例 如 ， 设 有 如 下 已 知 事 例 ： 张 三 是 足 球 运 动 员 ， 他 的 体 格 健 壮 。 李 四 是 足 球 运 动 员 ， 他 的 体 格 健 壮 。 刘 六 是 足 球 运 动 员 ， 他 的 体 格 健 壮 。 事 例 足 够 多 时 ， 可 归 纳 出 一 般 性 知 识 ： 凡 是 足 球 运 动 员 ， 他 的 体 格 一 定 健 壮 。7.4.1 归 纳 推 理1. 枚 举 归 纳 (0.9) 31 已 知 两 个 事 物 a与 b有 n个 属 性 相 似 或 相 同 ， 即 ：a具 有 属 性 P1， b也 具 有 属 性 P1。 a具 有 属 性 P2， b也 具 有 属 性 P2。 a具 有 属 性 Pn， b也 具 有 属 性 Pn。 且 a具 有 属 性 Pn+1 ， 则 当 n足 够 大 时 ， 可 归 纳 出 b也 具 有 属 性 P n+1。 7.4.1 归 纳 推 理2. 联 想 归 纳 32 设 ： 且 则 当 A与 B中 有 新 元 素 出 现 时 （ 设 A 中 的 a及 B中 的 b ） ，若 已 知 a 有 属 性 ， 就 可 得 出 b 有 属 性 ， 即 7.4.1 归 纳 推 理 3. 类 比 归 纳 1 2, , ,A a a , 21 bbB 1,2,.i iP a Q b i bQaP 33 一 般 模 式 ：（ 1） 若 H 为 真 时 ， 则 H E必 为 真 或 以 置 信 度 cf1成 立 。（ 2） 观 察 到 E 成 立 或 以 置 信 度 cf2成 立 。（ 3） 则 H 以 某 种 置 信 度 ( cf ) 成 立 。7.4.1 归 纳 推 理4. 逆 推 理 归 纳 ： 由 结 论 成 立 推 出 前 提 以 某 种 置 信 度 成 立 。 用 公 式 表 示 ： EH 1cfE 2cfH cf 34 则 H的 置 信 度 ：7.4.1 归 纳 推 理4. 逆 推 理 归 纳 （ 续 ） EP HPcfEP HPHEPEHPfc 11 21 cffccf EH的 置 信 度 cf1 = P(H/E)HE的 置 信 度 cf1= P(E/H)EH 1cfE 2cfH cf HE 1cfE 2cfH cf 35 7.4.1 归 纳 推 理5. 消 除 归 纳 消 除 归 纳 ： 通 过 不 断 否 定 原 先 的 假 设 来 得 出 结 论 。 已 知 ： 结 论 ： 1 21 1 1 i ni in i A A A AAAAA A 36 7.4.1 归 纳 推 理演 绎 推 理 归 纳 推 理 一 般 个 别 个 别 一 般 必 然 性 推 理 或 然 性 推 理 （ “ 主 观 不 充分 置 信 ” 的 推 理 ） 结 论 不 会 超 出 前 提 所 断定 的 范 围 ； 不 能 获 取 新 知 识 。 结 论 适 用 于 更 大 的 范 围 ； 可 获 取 新 知 识 。 演 绎 推 理 与 归 纳 推 理 的 区 别 37 7.4 归 纳 学 习7.4.1 归 纳 推 理7.4.2 示 例 学 习7.4.3 观 察 与 发 现 学 习 38 7.4.2 示 例 学 习 示 例 学 习 （ learning from examples， 实 例 学 习 或 从 例 子中 学 习 ） ： 通 过 从 环 境 中 取 得 若 干 与 某 概 念 有 关 的 例 子 ，经 归 纳 得 出 一 般 性 概 念 的 一 种 学 习 方 法 。 示 例 学 习 中 ， 外 部 环 境 （ 教 师 ） 提 供 一 组 例 子 （ 正 例 和反 例 ） ， 然 后 从 这 些 特 殊 知 识 中 归 纳 出 适 用 于 更 大 范 围 的一 般 性 知 识 ， 它 将 覆 盖 所 有 的 正 例 并 排 除 所 有 反 例 。 39 7.4.2 示 例 学 习1. 示 例 学 习 的 学 习 模 型 示 例 空 间 验 证搜 索 解 释 形 成 知 识 知 识 库 图 7.7 示 例 学 习 的 学 习 模 型 40 7.4.2 示 例 学 习 2. 形 成 知 识 的 方 法（ 1） 变 量 代 换 常 量 例 如 ， 假 设 有 两 个 关 于 扑 克 牌 “ 同 花 ” 概 念 的 示 例 。示 例 1：示 例 2： 1 2 3 41 2 3 4, , ,c c c cc c c c 花 色 （ ， 梅 花 ） 花 色 （ ， 梅 花 ） 花 色 （ ， 梅 花 ） 花 色 （ ， 梅 花 ）同 花 （ ）1 2 3 41 2 3 4, , ,c x c x c x c xc c c c 花 色 （ ， ） 花 色 （ ， ） 花 色 （ ， ） 花 色 （ ， ）同 花 （ ） 可 得 到 一 条 一 般 性 的 知 识 ：规 则 1： 1 2 3 41 2 3 4, , ,c c c cc c c c 花 色 （ ， 红 桃 ） 花 色 （ ， 红 桃 ） 花 色 （ ， 红 桃 ） 花 色 （ ， 红 桃 ）同 花 （ ） 41 7.4.2 示 例 学 习 2. 形 成 知 识 的 方 法（ 2） 舍 弃 条 件 例 如 示 例 ： 1 2 3 41 2 3 4, , ,c x c x c x c xc c c c 花 色 （ ， ） 花 色 （ ， ） 花 色 （ ， ） 花 色 （ ， ）同 花 （ ） 可 得 到 一 条 一 般 性 的 知 识 ：规 则 1： 花 色 ( c1,黑 桃 ) 点 数 （ c1, 7） 花 色 ( c2,黑 桃 ) 点 数 （ c2, 3） 花 色 ( c3,黑 桃 ) 点 数 （ c3, 10） 花 色 ( c4,黑 桃 ) 点 数 （ c4, 5） 同 花 ( c1, c2, c3, c4) 42 7.4.2 示 例 学 习 2. 形 成 知 识 的 方 法（ 3） 增 加 操 作 前 件 析 取 法 例 如 关 于 “ 脸 牌 ” 示 例 ： 1 11 11 1c J cc Q cc K c示 例 1： 点 数 （ ， ） 脸 （ ）示 例 2： 点 数 （ ， ） 脸 （ ）示 例 3： 点 数 （ ， ） 脸 （ ） 1 2 3 1c J c Q c K c 规 则 2： 点 数 （ ， ） 点 数 （ ， ） 点 数 （ ， ） 脸 （ ）得 到 知 识 ： 43 7.4.2 示 例 学 习 2. 形 成 知 识 的 方 法（ 3） 增 加 操 作 内 部 析 取 法 ： 在 示 例 的 表 示 中 使 用 集 合 与 集 合 间 的 成 员关 系 来 形 成 知 识 。 例 如 示 例 ： 1 11 11 1 c J cc Q cc K c 示 例 1： 点 数 （ ） 脸 （ ）示 例 2： 点 数 （ ） 脸 （ ）示 例 3： 点 数 （ ） 脸 （ ）1 1 c J Q K c 点 数 （ ） ， ， 脸 （ ）得 到 知 识 ： 44 7.4.2 示 例 学 习 2. 形 成 知 识 的 方 法（ 4） 合 取 变 析 取 例 如 ： “ 男 同 学 与 女 同 学 可 以 组 成 一 个 班 ” 。 归 纳 ： “ 男 同 学 或 女 同 学 可 以 组 成 一 个 班 ” 。 （ 5） 归 结 归 纳 例 如 ： 得 到 ： 1 1P E HP E H 1 2E E H l 示 例 1： 某 天 下 雨 ， 且 自 行 车 在 路 上 出 了 毛病 需 修 理 ， 所 以 他 上 班 迟 到 。l 示 例 2： 某 天 没 下 雨 ， 但 交 通 阻 塞 ， 所 以 他上 班 迟 到 。l 得 到 ： 如 果 自 行 车 在 路 上 出 了 毛 病 需 修 理 ，或 者 交 通 阻 塞 ， 则 他 有 可 能 上 班 迟 到 。 45 7.4.2 示 例 学 习 2. 形 成 知 识 的 方 法（ 6） 曲 线 拟 合 设 在 示 例 空 间 提 供 了 一 批 如 下 形 式 的 示 例 ： (x, y, z) 示 例 1： (1, 0, 10) 示 例 2： (2, 1, 18) 示 例 3： (-1, -2, -6)应 用 曲 线 拟 合 法 （ 例 如 最 小 二 乘 法 ） 得 到 ： z=2x+6 y+8 46 7.4 归 纳 学 习7.4.1 归 纳 推 理7.4.2 示 例 学 习7.4.3 观 察 与 发 现 学 习 47 7.4.3 观 察 与 发 现 学 习观 察 与 发 现 学 习 （ learning from observing and discovery） : 观 察 学 习 ： 用 于 对 事 例 进 行 概 念 聚 类 ， 形 成 概念 描 述 。 发 现 学 习 ： 用 于 发 现 规 律 ， 产 生 定 律 或 规 则 。 48 7.4.3 观 察 与 发 现 学 习1. 概 念 聚 类 (1980年 ,米 卡 尔 斯 基 （ R. S. Michalski) 基 本 思 想 : 把 事 例 按 一 定 的 方 式 和 准 则 进 行 分 组 ， 如 划分 为 不 同 的 类 ， 不 同 的 层 次 等 ， 使 不 同 的 组 代 表 不 同 的 概念 ， 并 且 对 每 一 个 组 进 行 特 征 概 括 ， 得 到 一 个 概 念 的 语 义符 号 描 述 。 49 7.4.3 观 察 与 发 现 学 习 1. 概 念 聚 类 例 如 事 例 ： 喜 鹊 、 麻 雀 、 布 谷 鸟 、 乌 鸦 、 鸡 、 鸭 、 鹅 ， 分 为 两 类 ： 鸟 = 喜 鹊 ， 麻 雀 ， 布 谷 鸟 ， 乌 鸦 ， 家 禽 = 鸡 、 鸭 、 鹅 ， 得 知 ： “ 鸟 有 羽 毛 、 有 翅 膀 、 会 飞 、 会 叫 、 野 生 ” 。 “ 家 禽 有 羽 毛 、 有 翅 膀 、 会 飞 、 会 叫 、 家 养 ” 。 50 7.4.3 观 察 与 发 现 学 习 2. 发 现 学 习 发 现 学 习 : 从 系 统 的 初 始 知 识 、 观 察 事 例 或 经 验 数 据 中归 纳 出 规 律 或 规 则 。 无 教 师 指 导 的 归 纳 学 习 经 验 发 现 : 从 经 验 数 据 中 发 现 规 律 和 定 律 。 知 识 发 现 : 指 从 已 观 察 的 事 例 中 发 现 新 的 知 识 。 51 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 52 7.5 类 比 学 习7.5.1 类 比 推 理7.5.2 属 性 类 比 学 习7.5.3 转 换 类 比 学 习 类 比 学 习 (learning by analogy)：通 过 对 相 似 事 物 进 行 比 较 所 进 行 的一 种 学 习 。 53 7.5.1 类 比 推 理 类 比 推 理 ： 由 新 情 况 与 记 忆 中 的 已 知 情 况 在 某 些方 面 相 似 ， 从 而 推 出 它 们 在 其 他 相 关 方 面 也 相 似 。 源 域 S： 已 经 认 识 的 域 ， 包 括 过 去 曾 经 解 决 过 且 与当 前 问 题 类 似 的 问 题 以 及 相 关 知 识 ；目 标 域 T： 当 前 尚 未 完 全 认 识 的 域 ， 是 遇 到 的 新 问题 。 类 比 推 理 的 目 的 ： 从 源 域 S中 选 出 与 当 前 问 题 最 近似 的 问 题 及 其 求 解 方 法 来 求 解 当 前 的 问 题 ， 或 者 建立 起 目 标 域 T中 已 有 命 题 间 的 联 系 ， 形 成 新 知 识 。 54 7.5.1 类 比 推 理 类 比 推 理 的 推 理 过 程 ： 1） 回 忆 与 联 想 ： 在 S中 找 出 与 当 前 情 况 相 似 的 情 况 ， 并 按相 似 度 从 高 到 低 进 行 排 序 。 2） 选 择 ： 选 出 与 当 前 情 况 最 相 似 的 情 况 及 其 有 关 知 识 。 3） 建 立 对 应 关 系 ： 在 S与 T的 相 似 情 况 之 间 建 立 相 应 的 映射 。 4） 转 换 ： 把 S中 的 有 关 知 识 引 到 T中 ， 建 立 起 求 解 当 前 问 题 的 方 法 或 者 学 习 到 关 于 T的 新 知 识 。 设 S1与 T1分 别 表 示 S与 T 中 的 某 一 情 况 ， 且 S1与 T1相 似 ，再 假 设 S2与 S1相 关 ， 则 由 类 比 推 理 可 推 出 T 中 的 T2 ， 且 T2与 S2相 似 。 55 7.5 类 比 学 习7.5.1 类 比 推 理7.5.2 属 性 类 比 学 习7.5.3 转 换 类 比 学 习 56 7.5.2 属 性 类 比 学 习 属 性 类 比 学 习 : 根 据 两 个 相 似 事 物 的 属 性 实 现 类 比学 习 的 。 属 性 类 比 学 习 系 统 （ 1979年 ， 温 斯 顿 ） ： 源 域 和 目 标 域 都 是 用 框 架 表 示 的 ， 分 别 称 为 源 框 架和 目 标 框 架 。 框 架 的 槽 用 于 表 示 事 物 的 属 性 。 学 习 过 程 : 把 源 框 架 中 的 某 些 槽 值 传 递 到 目 标 框 架的 相 应 槽 中 去 。 57 7.5.2 属 性 类 比 学 习候 选 槽 ： 其 槽 值 有 可 能 要 传 递 给 目 标 框 架 的 那 些 槽 。选 择 的 方 法 ：（ 1） 选 择 具 有 极 端 槽 值 的 槽 ， 例 如 “ 很 大 ” 、 “ 很小 ” （ 2） 选 择 已 经 被 确 认 为 “ 重 要 槽 ” 的 槽（ 3） 选 择 与 源 框 架 相 似 的 框 架 中 不 具 有 的 槽（ 4） 选 择 相 似 框 架 中 不 具 有 这 种 槽 值 的 槽（ 5） 选 择 源 框 架 中 的 所 有 槽 1. 从 源 框 架 中 选 择 若 干 槽 作 为 候 选 槽 58 7.5.2 属 性 类 比 学 习筛 选 规 则 ：（ 1） 选 择 在 目 标 框 架 中 还 未 填 值 的 槽 。 （ 2） 选 择 在 目 标 框 架 中 为 典 型 事 例 的 槽 。 （ 3） 选 择 与 目 标 框 架 有 紧 密 关 系 的 槽 ， 或 者 与 目 标 框 架 的 槽 类 似 的 槽 。 2. 根 据 目 标 框 架 对 候 选 槽 进 行 筛 选 59 7.5 类 比 学 习7.5.1 类 比 推 理7.5.2 属 性 类 比 学 习7.5.3 转 换 类 比 学 习 60 7.5.3 转 换 类 比 学 习 在 状 态 空 间 表 示 法 的 知 识 表 示 中 ， “ 状 态 ” ： 描 述问 题 在 不 同 时 刻 的 状 况 ； “ 算 符 ” ： 描 述 改 变 状 态 的 操作 。 当 问 题 由 初 始 状 态 变 换 到 目 标 状 态 时 ， 所 用 算 符 的 序列 就 构 成 了 问 题 的 一 个 解 。 如 何 使 问 题 由 初 始 状 态 变 换 到 目 标 状 态 呢 ？ “ 手 段 目 标 分 析 ” 法 （ means-end analysis，MEA） ， 又 称 为 “ 中 间 结 局 分 析 ” 法 ： 纽 厄 尔 等 人 在通 用 问 题 求 解 程 序 GPS（ general problem solver） 中 提出 的 一 种 问 题 求 解 模 型 。 61 7.5.3 转 换 类 比 学 习 “手 段 目 标 分 析 ” 法 （ MEA） 求 解 问 题 的 基 本 过 程 ：（ 1） 把 问 题 的 当 前 状 态 与 目 标 状 态 进 行 比 较 ， 找 出 差 异 。（ 2） 根 据 差 异 找 出 一 个 可 减 小 差 异 的 算 符 。（ 3） 如 果 该 算 符 可 作 用 于 当 前 状 态 ， 则 用 该 算 符 把 当 前 状 态改 变 为 另 一 个 更 接 近 于 目 标 状 态 的 状 态 ； 如 果 不 能 ， 则 保 留 当前 状 态 ， 并 生 成 一 个 子 问 题 ， 再 对 此 子 问 题 应 用 MEA。（ 4） 当 子 问 题 被 求 解 后 ， 恢 复 保 留 的 状 态 ， 继 续 处 理 原 问 题 。 62 7.5.3 转 换 类 比 学 习 回 忆 过 程 ： 找 出 新 、 旧 问 题 间 的 差 别 ， 包 括 ：（ 1） 初 始 状 态 的 差 别 。（ 2） 目 标 状 态 的 差 别 。（ 3） 路 径 约 束 的 差 别 。（ 4） 求 解 方 法 可 应 用 度 的 差 别 。 转 换 过 程 ： 把 旧 问 题 的 求 解 方 法 经 适 当 变 换 使 之 成 为 求 解 新问 题 的 方 法 ， 变 换 中 用 MEA来 减 小 目 标 状 态 与 初 始 状 态 之 间 的差 异 ， 使 初 始 状 态 逐 步 过 渡 到 目 标 状 态 ， 即 求 出 问 题 的 解 。 转 换 类 比 学 习 ： 由 外 部 环 境 获 得 与 类 比 有 关 的 信 息 ， 学 习 系统 找 出 与 新 问 题 相 似 的 旧 问 题 的 有 关 知 识 ， 把 这 些 知 识 进 行 转换 使 之 适 用 于 新 问 题 ， 从 而 获 得 新 的 知 识 。 63 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 64 7.6 解 释 学 习 解 释 学 习 （ explanation-based learning） ： 由 美 国Illinois大 学 的 Dejong于 1983年 提 出 ， 属 于 分 析 学 习 ，本 质 为 演 绎 学 习 方 法 。 它 是 通 过 运 用 相 关 的 领 域 知 识 ， 对 当 前 提 供 的 单个 实 例 的 问 题 求 解 进 行 分 析 ， 从 而 构 造 解 释 并 产 生 相应 知 识 的 。 解 释 学 习 系 统 ：米 切 尔 （ Mitchell） 等 人 研 制 的 LEX和 LEAP系 统 ，明 顿 （ S. Minton） 等 人 研 制 的 PRODIGY系 统 等 。 65 7.6 解 释 学 习7.6.1 解 释 学 习 的 概 念7.6.2 解 释 学 习 的 学 习 过 程7.6.3 领 域 知 识 的 完 善 性 66 7.6.1 解 释 学 习 的 概 念 解 释 学 习 ： 通 过 运 用 相 关 的 领 域 知 识 及 一 个 训 练 实 例 来对 某 一 目 标 概 念 进 行 学 习 ， 并 最 终 生 成 这 个 目 标 概 念 的一 般 性 描 述 。 解 释 学 习 的 一 般 性 描 述 （ 米 切 尔 （ Mitchell） 等 ，1986） ： 给 定 ： 领 域 知 识 DT（ 用 于 证 明 训 练 实 例 为 什 么 可 作 为 目 标 概 念的 实 例 ） 目 标 概 念 TC（ 要 学 习 的 概 念 ） 训 练 实 例 TE 操 作 性 准 则 OC （ 指 导 系 统 对 描 述 目 标 的 概 念 进 行 取 舍 ） 找 出 ： 满 足 OC的 关 于 TC的 充 分 条 件 。 67 7.6.1 解 释 学 习 的 概 念 解 释 学 习 与 示 例 学 习 的 主 要 区 别 ：（ 1） 示 例 学 习 ： 输 入 一 组 实 例 。 解 释 学 习 ： 输 入 一 个 实 例 。（ 2） 示 例 学 习 ： 归 纳 学 习 ， 不 要 求 提 供 领 域 知 识 。 解 释 学 习 ： 演 绎 学 习 ， 要 求 提 供 完 善 的 领 域 知 识 。（ 3） 示 例 学 习 ： 概 念 的 获 取 ， 即 知 识 增 加 的 一 面 。 解 释 学 习 ： 技 能 提 高 的 一 面 。 68 7.6.2 解 释 学 习 的 学 习 过 程 证 明 过 程 ： 通 过 运 用 领 域 知 识 进 行 演 绎 实 现 的 ， 证 明的 结 果 是 得 到 一 个 解 释 结 构 。 1. 构 造 解 释 解 释 学 习 的 学 习 过 程 ： 首 先 运 用 领 域 知 识 找 出 训 练 实例 为 什 么 是 目 标 概 念 的 证 明 ， 即 解 释 ， 然 后 按 操 作 性 准则 对 解 释 进 行 推 广 ， 从 而 得 出 关 于 目 标 概 念 的 学 习 描 述 。 例 如 ， 学 习 目 标 ： “ 一 个 物 体 x可 以 安 全 地 放 置 在 另 一 个 物 体y的 上 面 ” （ 堆 叠 问 题 ） 。 目 标 概 念 ： 物 体 （ x, y)， Safe-to-stack(x, y) 69 7.6.2 解 释 学 习 的 学 习 过 程 训 练 实 例 （ 描 述 物 体 Obj1和 Obj2的 事 实 ） ：领 域 知 识 （ 安 全 放 置 准 则 和 计 算 准 则 ） ： ),( 21 ObjObjStackToSafe 1 2 1 21 21 1( , ), ( , ),( , ), ( , ),( ,1) ( ,0.1).On Obj Obj Lighter Obj ObjIsa Obj book AI Isa Obj table bookVolume Obj Density Obj ),()( yxStackToSafeyFragile ),(),( yxStackToSafeyxLighter ),(),(),(),( wpWeightwdvdpDensityvpVolume )15,(),( pWeightbooktablepIsa ),(),(),(),( 21212211 ppLighterwwSmallerwpWeightwpWeight 例 如 ， 学 习 目 标 ： “ 一 个 物 体 x可 以 安 全 地 放 置 在 另 一 个 物 体y的 上 面 ” （ 堆 叠 问 题 ） 。 目 标 概 念 ： 物 体 （ x, y)， Safe-to-stack(x, y) 70 7.6.2 解 释 学 习 的 学 习 过 程 1 21 212 1 1 ( , ),( , ),( , ),( , ),( ,1),( ,0.1).On Obj ObjLighter Obj ObjIsa Obj book AIIsa Obj table bookVolume ObjDensity Obj 1. 构 造 解 释 ),( 21 ObjObjStackToSafe ),( 21 ObjObjLighter)1.0,( 1ObjWeight )15,( 2ObjWeight )15,1.0(Smaller),( 2 booktableObjIsa )1,( 1ObjVolume )1.0,( 1ObjDensity )1.0,1.0,1(*Safe -To-Stack ( Obj 1, Obj2) 的 解 释 结 构),(),( yxStackToSafeyxLighter ),(),(),(),( wpWeightwdvdpDensityvpVolume )15,(),( pWeightbooktablepIsa ),(),(),(),( 21212211 ppLighterwwSmallerwpWeightwpWeight ),()( yxStackToSafeyFragile 71 7.6.2 解 释 学 习 的 学 习 过 程 任 务 ： 对 上 一 步 得 到 的 解 释 结 构 进 行 一 般 化 处 理 ， 从而 得 到 关 于 目 标 概 念 的 一 般 性 知 识 。 处 理 的 方 法 : 把 常 量 变 换 为 变 量 ， 并 把 某 些 不 重 要 的信 息 去 掉 ， 只 保 留 那 些 对 以 后 求 解 问 题 所 必 须 的 关 键 性信 息 。 2. 获 取 一 般 性 的 知 识 72 7.6.2 解 释 学 习 的 学 习 过 程 2. 获 取 一 般 性 的 知 识 ),( 21 OOStackToSafe ),( 21 OOLighter),( 11 wOWeight )15,( 2OWeight )15,( 1wSmaller),( 2 booktableOIsa ),( 11 vOVolume ),( 11 dODensity ),(* 111 wdvSafe -To -Stack ( O 1 , O2 ) 一 般 化 解 释 结 构 73 7.6.3 领 域 知 识 的 完 善 性 两 种 极 端 情 况 ：（ 1） 构 造 不 出 解 释 原 因 ： 系 统 中 缺 少 某 些 相 关 的 领 域 知 识 ， 或 者 领 域 知 识中 包 含 了 矛 盾 等 错 误 。 （ 2） 构 造 出 了 多 种 解 释 原 因 ： 领 域 知 识 不 健 全 ， 已 有 的 知 识 不 足 以 把 不 同 的 解释 区 分 开 来 。 74 第 7章 机 器 学 习7.1 机 器 学 习 的 基 本 概 念7.2 机 械 式 学 习7.3 指 导 式 学 习7.4 归 纳 学 习7.5 类 比 学 习7.6 基 于 解 释 的 学 习7.7 学 习 方 法 的 比 较 与 展 望 75 7.7 机 器 学 习 方 法 的 比 较 与 展 望7.7.1 各 种 机 器 学 习 方 法 的 比 较7.7.2 机 器 学 习 的 展 望 76 7.7.1 各 种 机 器 学 习 方 法 的 比 较 以 推 理 能 力 排 列 机 械 式 学 习 ， 指 导 式 学 习 ， 解 释 学 习 ， 类 比 学 习 ， 示 例 学 习 ， 观 察 与 发 现 学 习 。 适 用 领 域 连 接 学 习 ： 模 拟 人 类 较 低 级 的 神 经 活 动 。 符 号 学 习 ： 模 拟 人 类 的 高 级 思 维 活 动 。 对 领 域 理 论 的 要 求 示 例 学 习 、 观 察 与 发 现 学 习 ： 领 域 理 论 要 求 较 少 。 解 释 学 习 ： 要 求 提 供 完 善 的 领 域 知 识 。 77 7.7.1 各 种 机 器 学 习 方 法 的 比 较 知 识 获 取 角 度 ： 示 例 学 习 、 观 察 与 发 现 学 习 ： 通 过 学 习 可 以 产 生 新 概 念 描 述 ， 可 用 于 专 家 系 统 的 知 识 获 取 。 解 释 学 习 : 学 习 目 标 主 要 是 改 善 系 统 的 效 率 ， 而 不 扩 充 概 念 描 述 的 范 围 。 指 导 式 学 习 : 通 过 与 指 导 者 （ 如 领 域 专 家 ） 的 交 互 学 习 新 知 识 ， 同 时 又 可 帮 助 指 导 追 踪 推 理 过 程 ， 发 现 其 中 的 错 误 ， 找 出 产 生 错 误 的 原 因 ， 然 后 由 指 导 者 进 行 修 正 。 78 7.7 机 器 学 习 方 法 的 比 较 与 展 望7.7.1 各 种 机 器 学 习 方 法 的 比 较7.7.2 机 器 学 习 的 展 望 79 7.7.2 机 器 学 习 的 展 望（ 1） 人 类 学 习 机 制 的 研 究 。（ 2） 发 展 和 完 善 现 有 的 学 习 方 法 ， 并 开 展 新 的 学 习 方 法 的 研 究 。（ 3） 建 立 实 用 的 学 习 系 统 ， 特 别 是 多 种 学 习 方 法 协 同 工 作 的 集 成 化 系 统 的 研 究 。（ 4） 机 器 学 习 的 结 构 模 型 、 计 算 理 论 、 算 法 和 混 合 学 习 的 有 关 理 论 及 应 用 的 研 究 。 80THE END Artificial Intelligence Principles and Applications