分析学习PPT课件.pptx

《分析学习PPT课件.pptx》由会员分享，可在线阅读，更多相关《分析学习PPT课件.pptx（60页珍藏版）》请在金锄头文库上搜索。

1、 第十一章分析学习 2020 4 8 1 前言 神经网络和决策树这样的学习方法需要一定数目的训练样例才能达到一定级别的泛化精度 分析学习使用先验知识和演绎推理来扩大训练样例提供的信息 因此它不受同样的界限制约 本章讨论一种称为基于解释的学习 EBL 的分析学习方法 基于解释的学习中 先验知识用于分析观察到的学习样例是怎样满足目标概念的 然后这个解释用于区分训练样例中哪些是相关的特征 哪些是不相关的 这样 样例就可基于逻辑推理进行泛化 而不是基于统计推理 2020 4 8 2 简介 归纳和分析学习问题 PROLOG EBG算法 PROLOG EBG运行举例 1 2 3 4 目录 对基于解释的学习

2、的说明 5 搜索控制知识的基于解释的学习 6 小结 7 2020 4 8 3 简介 前面章节讨论的各种归纳法 决策树 神经网络 归纳逻辑编程 遗传算法 在实践中的一个关键限制是 在可用数据不足时性能较差 正如第7章分析 给定数目的训练样例 学习的精度存在基本的上下界 是否能开发出这样的学习方法 它们训练精度上的基本限制不受可用训练数据的数量所制约 2020 4 8 4 简介 基于解释的学习就是这样的一种学习方法 1 能接受显式的先验知识 与训练数据一同作为输入 2 使用先验知识来分析或解释每个训练样例 以推理出样例的哪些特征与目标函数相关 哪些不相关 3 减小了待搜索假设空间的复杂度 减小了样

3、本复杂度 提高了学习器的泛化精度 注意 基于解释的学习与前一章所示的归纳逻辑系统 如CIGOL 使用先验背景知识来指导学习不同 因为后者使用背景知识推理出的特征扩大了输入实例的描述 增加了待搜索假设空间的复杂度 2020 4 8 5 例子 下国际象棋的学习任务 我们期望程序学习识别棋局位置的重要类别 比如有一目标概念 黑棋将在两步内失去王后的棋盘状态 下图显示了此目标概念的一个正例 白马同时攻击黑王和黑后 黑棋必须移动其王 从而白棋就会吃掉黑后 2020 4 8 6 例子 下国际象棋的学习任务 当然 归纳逻辑方法也能用于学习此目标概念 但是我们需要提供成千上万的类似上图的训练样例 才能期望归纳

4、学习到的假设被正确地泛化 这里 我们要研究一下人类的学习方法 人类只需要少数的训练样例就能学习到这样的目标概念 人类是怎样从少数训练样例中成功地泛化的呢 答案在于人类非常依赖合法移动棋子的先验知识来解释或分析训练样例 如上图的训练样例 多数人会给出这样的解释 因为白马同时攻击黑王和黑后 黑子必须摆脱被将军的局面 所以让白子吃掉黑后 该解释的重要性在于 它提供了所需要的信息以从训练样例的细节中合理泛化到正确的一般假设 此解释中提到的样例特征 如白马 黑王 黑后的位置 是与目标概念有关的 应该被包含在一般的假设中 2020 4 8 7 例子 下国际象棋的学习任务 在下棋的例子中 学习器需要的先验知

5、识是下棋的合法规则 即马以及其他子的合法移动 对弈者必须交替移子以及要赢棋必须抓住对方的王 对弈理论上 只要给定这样的先验知识 就有可能对任意棋盘状态计算出最优的走法 然而 实践中这样的计算极为复杂 人类也很难做到 因此 在下棋以及诸如调度和规划等的搜索密集问题的人类学习中 包含了一个很长的发现先验知识的过程 2020 4 8 8 基于解释学习的基本原理 基于解释学习利用先验知识分析一个或少数几个实例 说明观察到的学习实例是怎样满足目标概念的 然后基于逻辑推理对样例进行泛化 产生适合以后求解类似问题的控制规则和知识 解释学习分为两步 1 通过分析一个求解实例来产生解释结构 2 对结构进行泛化

6、获取一般的控制规则 2020 4 8 9 内容安排 1 给出一个特定的基于解释的学习算法 称为Prolog EBG 2 考查Prolog EBG的一般特性以及与前面讨论的归纳算法之间的关系 3 描述了应用基于解释的学习以提高大状态空间搜索的性能 本章假定生成解释所基于的先验知识是完全正确的 下一章讨论更一般的情况 即先验知识只是近似正确 注意 2020 4 8 10 归纳和分析学习问题 分析和归纳学习问题的重要区别是它们设想的学习问题形式不同 1 在归纳学习中 学习器被赋予一个假设空间H和训练数据D 它从H中选择一个输出假设 并且希望这个假设与D一致 2 在分析学习中 学习器的输入除了假设空间

7、H和训练数据D 还有一个领域理论B 由可用于解释训练样例的背景知识组成 学习器中H中选择一个输出假设 并希望这个假设既与D一致 也与B一致 2020 4 8 11 归纳和分析学习问题 分析学习举例 学习的目标概念 黑棋将在两步内失去王后的状态实例 xi描述一特定棋盘状态 当黑棋两步内失去王后 f xi 值为真 否则为假假设空间 用Horn子句集表示 其中谓词表示棋子的位置领域理论 形式化的下棋规则 注意 在分析学习中 引入一致性约束 当领域理论B不涵蕴h的否定时 则称h与B一致 一致性约束减少了当数据不能单独在H中决定h时 学习器面临的歧义性 领域理论由一组Horn子句描述 它使系统原则上可以

8、加入任何学习到的假设至后续的领域理论中 2020 4 8 12 例子 SafeToStack x y 已知实例空间X 每个实例描述一对物理对象 它们由谓词Color Volume Owner Material Type Density描述 它们之间的关系用谓词On描述 假设空间H 每个假设是一组Horn子句规则 每个Horn子句的头部为一个包含目标谓词SafeToStack的文字 每个Horn子句为文字的合取 这些文字基于描述实例的谓词以及谓词LessThan Equal GreaterThan和函数plus minus和time 如下例SafeToStack x y Volume x vx

9、Volume y vy LessThan vx vy 目标概念 谓词SafeToStack x y 表示两个物理对象 一个可被安全地叠放在另一个上 2020 4 8 13 例子 SafeToStack x y 训练样例 下面显示了一个典型的正例SafeToStack Obj1 Obj2 On Obj1 Obj2 Owner Obj1 Fred Type Obj1 Box Owner Obj2 Louise Type Obj2 Endtable Density Obj1 0 3 Color Obj1 Red Material Obj1 Cardboard Color Obj2 Blue Mate

10、rial Obj2 Wood Volume Obj1 2 领域理论B SafeToStack x y Fragile y SafeToStack x y Lighter x y Lighter x y Weight x wx Weight y wy LessThan wx wy Weight x w Volume x v Density x d Equal w times v d Weight x 5 Type x Endtable Fragile x Material x Glass 求解 H中一个与训练样例和领域理论一致的假设 2020 4 8 14 例子 SafeToStack x y

11、SafeToStack x y Lighter x y Lighter x y Weight x wx Weight y wy LessThan wx wy Weight x w Volume x v Density x d Equal w times v d Weight x 5 Type x Endtable 2020 4 8 15 用完美的领域理论学习 Prolog EBG 本章考虑的基于解释的学习是在领域理论完美的情况下 即领域理论正确且完整 当领域理论中每个断言都是客观的真实描述时 该领域理论被称为是正确的 当领域理论覆盖了实例空间中所有正例时 该领域理论被称为是完整的 注意 每个满

12、足目标概念的实例都可由领域理论证明其满足性 但在这里完整性的定义不要求领域理论可证明反例不满足目标概念 根据Prolog惯例 不能证明的断言认定则为假 因此完整性定义包含全部正例和反例 2020 4 8 16 用完美的领域理论学习 Prolog EBG 1 在某些情况下 有可能提供完美领域理论 比如下棋问题 棋子的合法走子提供了完美的领域理论 进一步讲 有了这样的完美的领域理论 也很难写出最优下棋策略 在这种情况下 我们更希望学习器得到完美的领域理论后 能够形成对目标概念有帮助的描述 如 可能丢后的棋局状态 方法是对特殊训练样例进行考查和泛化 2 在许多情况下 不能够假定有完美的领域理论 但我

13、们可以使用基于不完美领域理论的近似合理的解释 它以完美理论为基础 学习器的完美领域理论的假定是否合理 如果学习器有了完美的领域理论 还有必要再去学习吗 2020 4 8 17 Prolog EBG算法 Prolog EBG是一种基于解释的学习方法 是一种序列覆盖算法 它的过程是 1 学习单个Horn子句规则 移去此规则覆盖的正例 2 在剩余正例上重复这个过程 直到覆盖所有正例为止 对于任意的正例集合 Prolog EBG输出的假设包含一组对应于领域理论的目标概念的逻辑充分条件 2020 4 8 18 基于解释的Prolog EBG算法 Prolog EBG TargetConcept Trai

14、ningExample DomainTheory LearnedRules Pos TrainingExamples中的正例 对Pos中没有被LearnedRules覆盖的每个正例 做以下操作 1 解释 Explanation 以DomainTheory表示的解释 说明正例满足TargetConcept 2 分析 SuffcientConditions 按照Explanation能够充分满足TargetConcept的正例的最一般特征集合 3 改进 LearnedRules LearnedRules NewHornClause 其中NewHornClause的形式是 TargetConcept

15、 SufficientConditions 返回LearnedRules 2020 4 8 19 Prolog EBG的运行举例 Prolog EBG对每个还没有被某个Horn子句覆盖的正例 通过下列步骤生成一新Horn子句 1 解释新的正例 2 分析该解释以确定一合适的泛化 3 通过加入一新的Horn子句以覆盖该正例以及其他相似实例来改进当前假设 2020 4 8 20 解释训练样例 按照领域理论建立解释 说明该正例如何满足目标概念 当领域理论正确且完整时 此解释构成了训练样例满足目标概念的证明 一般情况下 可能有多种解释 这些解释中任意一个或所有的都可被使用 每个解释可对训练样例形成不同的

16、泛化 所有解释都将被给定的领域理论论证 在Prolog EBG中 解释的生成使用了如Prolog中的反向链式搜索 找到第一个有效证明时终止 如下图对前面SafeToStack Obj1 Obj2 的正例进行了解释 此解释说明因为Obj1比Obj2更轻 Lighter 所以Obj1可以安全的堆叠 SafeToStack 在Obj2上 更进一步 知道Obj1更轻是因为它的重量 Weight 可由它的密度 Density 和体积 Volume 推得 并且Obj2的重量 Weight 可由茶几 Endtable 的默认重量值得到 2020 4 8 21 解释训练样例 2020 4 8 22 分析解释 从上图可以看出 解释中包含了Obj1的Density 但没有它的Owner特征 因此 SafeToStack x y 的假设应包含Density x 0 3 而不包含Owner x Fred 通过收集解释的叶节点中提及的特征 可形成一个由领域理论论证的一般规则 SafeToStack x y Volume x 2 Density x 0 3 Type y Endtable 形成的规则构成了此训练样