机器学习.ppt

2概念学习 ConceptLearning 2 1概念学习基础2 2寻找极大特殊假设算法2 3候选消去算法2 4候选消去算法的讨论2 5归纳偏置Problem 2 1概念学习基础 2 1 1从例子开始2 1 2基本概念2 1 3假设空间和归纳学习 2 1 1从例子开始 例子需要学习的概念 Aldo水上运动的日子 Sport Day 训练样例 2 1 1从例子开始 Sport Day概念学习任务已知1 实例集X 可能的日子 每个日子由下列属性描述 天气 晴朗 多云 下雨 气温 暖 冷 湿度 正常 高 风力 强 弱 水温 暖 凉 天气预报 相同 变化 2 假设集H 假设描述由六元组组成 分别对应6个属性 是6个属性的值约束的合取式 值约束有三种形式 1 确定的值 2 变量 3 拒取 2 1 1从例子开始 3 目标概念c Sport Day X Yes No 4 训练样例集 见前表 求解H中的一个假设h 使得对于X中的任意x 有h x c x 2 1 2基本概念 定义1概念学习将某个布尔函数的输入和输出作为训练样例 从中推导出该布尔函数 定义2概念设X为对象的集合 概念C定义为X的子集 即C X C中每个元素称为概念C的实例 定义3目标函数cc X T F 即若c x T 则x C 定义4训练样例集D由序偶 d x c x 组成的集合 其中d x 为实例x的描述 x X 有时直接用x表示实例描述 正例集D x c x T 反例集D x c x F 2 1 2基本概念 概念描述CD某种表示法语言的合法语句 常用的表示法为特征向量 如 在Aldo水上锻炼的日子问题中 用属性元组 天气 气温 湿度 风力 水温 天气预报 刻画问题 概念及实例 该6元组允许的值构成一个特征空间 语法合法的元组是一个概念描述 如 暖 强 暖 相同 它覆盖特征空间的一个区域 只含一个点的描述为实例描述 如 晴朗 暖 正常 强 暖 相同 注意 实例描述是概念描述的特例 属性A实例x在属性A上的取值记为A x X VA集合D中其属性A的值为v的元素记为Dv 即Dv x x D A x v VA为属性A的值集 2 1 3假设空间和归纳学习 定义5假设空间HH是由概念描述组成的集合 它确定了目标函数的范围 需要学习的假设h H是目标函数c的一个定义 假设空间包含 1 假设 即概念描述 2 实例描述 例子 Aldo进行水上运动的日子 天气 气温 湿度 风力 水温 天气预报 实例空间的元素 3 2 2 2 2 2 96假设空间的元素 5 4 4 4 4 4 5120 语法不同 语义不同的假设个数 1 4 3 3 3 3 3 973 2 1 3假设空间和归纳学习 归纳学习的基本假设概念学习是一类特殊的归纳学习 归纳学习从训练样例集学习一个概念描述h 目标函数c的定义 而已知的仅仅是c在训练样例上的值 这只能保证假设与训练样例拟合 因此 需要一个基本假设 任一假设如果在足够大的训练样例集中很好逼近目标函数 则它在其他实例中也能很好逼近目标函数 2 1 3假设空间和归纳学习 定义6一般性关系 设hi和hj为定义在X上的两个布尔函数 概念描述 hi比hj更一般或等价 hi hj 当且仅当 x X hj x 1 hi x 1 这是假设空间的一种偏序关系 从一般到特殊 其逆关系为 特殊性关系 从集合的观点看 2 1 3假设空间和归纳学习 例有下列两个概念描述h1 晴朗 强 h2 晴朗 则 h2 h1 或h1 h2偏序关系的作用 1 为假设空间提供了一种层次结构 2 对任意概念学习问题提供了一种学习制导机制 2 1 3假设空间和归纳学习 归纳推理规则归纳学习需要归纳推理规则 一般化规则1 确定值2 确定值 变量 3 当属性值为数值时 a b a b 4 爬一般性树 概念的层次结构 特殊化规则与一般化规则对偶 方向相反 2 1 3假设空间和归纳学习 归纳学习与搜索归纳学习可以用搜索问题来描述如下 状态 概念描述 或假设 操作 归纳推理规则搜索 从某个初始假设出发 在假设空间寻找能够与所有训练样例拟合的假设 评估函数 与训练样例集合拟合的程度 2 2寻找极大特殊假设算法 寻找极大特殊假设 FIND S算法1 将h初始化为H中最特殊的假设2 对于每个正例x 对正例循环1 对h的每个属性约束ai 对属性约束循环IFx满足aiTHEN不做任何处理ELSE将h的ai替换为x满足的另一个更一般约束3 输出假设h 2 2寻找极大特殊假设算法 算法的运行 Sport Day 晴朗 暖 正常 强 暖 相同 晴朗 暖 强 暖 相同 晴朗 暖 强 2 2寻找极大特殊假设算法 算法分析1 只使用一般化规则 搜索沿着一条偏序链向前 即 设hi为算法的第i次循环中得到的假设 则h1 h2 hn2 在做一般化推理时 采取保守策略 即一般化程度尽可能小 3 当假设空间的概念描述为属性的合取式时 算法总能发现覆盖训练样例的最特殊的假设 4 既使训练样例正确 目标概念包含在H中 得到的假设也可能覆盖反例 2 2寻找极大特殊假设算法 算法的弱点1 收敛性算法是否收敛到目标概念 需要多少样例才能收敛 2 噪音敏感 3 多个极大特殊的假设的情况下 如何处理 2 3候选消去算法 2 3 1版本空间2 3 2候选消去算法2 3 3算法运行 2 3 1版本空间 定义7一致性设h是假设 D是训练样例集合 h与D是一致的 当且仅当对于D中的每个样例 x c x 都有h x c x 即Consistent h D x c x D h x c x x满足h是指h x 1 注意一致性与满足性的区别 定义8版本空间 VersionSpace 设假设空间H 训练样例集合D 关于H和D的版本空间是H中与D一致的假设构成的集合 记为VSH D 即VSH D h H Consistent h D 2 3 1版本空间 版本空间的表示1 列表将假设空间的所有假设形成一个表 List Then Eliminate算法1 VS H中所有假设的列表2 对每个训练样例 x c x 从VS中移去所有h x c x 的假设h3 输出VS中的所有假设 2 3 1版本空间 2 G S表示定义极大一般集合G 极大边界 设H为假设空间 D为训练样例集 关于H和D的一般边界G为H中与D一致的极大一般成员构成的集合 G g H Consistent g D g H g g Consistent g D 定义极大特殊集合S 极小边界 设H为假设空间 D为训练样例集 关于H和D的特殊边界S为H中与D一致的极大特殊成员构成的集合 S s H Consistent s D s H s s Consistent s D 2 3 1版本空间 定理2 1版本空间表示定理设X为任意实例集合 H为X上定义的布尔假设集合 令c X 0 1 为任一目标函数 D为任一训练样例集合 x c x 对所有X H c和D 以及良定义的S和G VSH D h H s S g G g h s 因此 版本空间VSH D可用两个边界集合S和G来表示 注 良定义指任意偏序链都有上界和下界 2 3 2候选消去算法 1 将G初始化为H中的极大一般集合 S初始化为H中的极大特殊集合 2 对于每个训练样例d 做1 若d是正例从G中删除所有与d不一致的假设 对S中每个与d不一致的假设s 从S中删除s S必须与当前见到的样例一致把s的所有满足下列条件的极小泛化式h加入S 对s一般化h与d一致 且存在G的成员比h更一般 从S中移去所有这样的假设 它比S中另一个假设更一般 满足S的定义2 若d是反例 从S中删除所有与d不一致的假设 对G中每个与d不一致的假设g 从G中删除g G必须与当前见到的样例一致把g的所有满足下列条件的极小特殊式h加入G 对g一般化h与d一致 且存在S的成员比h更特殊 从G中移去所有这样的假设 它比G中另一个假设更特殊 满足G的定义 2 3 2候选消去算法 图示算法思路 极大边界G 覆盖目前输入的所有正例遇反例 特殊化 极小边界S 排除目前输入的所有反例遇正例 泛化 收缩 2 3 2候选消去算法 算法说明用一般化规则产生s的极小泛化式用特殊化规则产生g的极小特殊式s的极小泛化式h满足下列条件h s 且 h h h s g的极小特殊式h满足下列条件g h 且 h g h h 2 3 3算法运行 训练样例s 晴朗 w 暖 n 正常 c 冷 st 强 c 凉 h 高 sm 相同 ch 变化 r 雨 cld 多云 2 3 3算法运行 初始S0 G0 第二次循环 训练样例 d1 s w n st w sm SportDay Yesd2 s w h st w sm SportDay yes 2 3 3算法运行 第三次循环注意 n 不包含在G3中 因为它与d2不一致 判断标准 不存在S中的成员比它更特殊 训练样例 d3 r c h st w ch SportDay No 2 3 3算法运行 第四次循环 训练样例 d4 s w h st c ch SportDay Yes 2 3 3算法运行 最终版本空间 2 4候选消去算法的讨论 2 4 1算法的收敛性2 4 2生成训练样例2 4 3不完全目标概念的应用 2 4 1算法的收敛性 收敛性的含义当给定足够多的 合适分布的训练样例时 算法确定的版本空间G S将包含一个概念描述 该概念描述是所需要的目标函数 合适分布的训练样例指 训练样例D与所有实例X的分布形态一致 如在SportDay例子中 如果所有正例都是在湿度值上不同 S集合将不会发生变化 判断训练样例的分布 对于属性元组的表示 可以根据训练样例在每个属性的取值情况判断 2 4 1算法的收敛性 算法收敛的条件1 无噪音即所有训练样例的目标函数值c x 无错误 如果D中包含错误的样例 算法有可能错误地删除版本空间的目标概念 因为它会删除G或S中与样例不一致的假设 这种情况下 给定足够多的训练样例 G S会收缩到一个空的版本空间 2 4 1算法的收敛性 算法收敛的条件2 假设空间H包含目标概念的描述如果训练样例正确 但算法不收敛 原因可能有 1 表示法的选择本身有问题2 表示法的描述能力有限在SportDay的例子中 限定假设只能是属性约束的合取式 这将不能描述需要析取式的目标概念 2 4 2生成训练样例 生成训练样例的语境学习器控制实验进程 自动生成实验 然后由外部教师对其进行分类 给出实验的目标函数值 从而形成训练样例 用于进一步的学习 生成训练样例的原则和策略1 生成的实例既被G S中的某些假设满足 又被另一些假设否定 理想情况 1 2满足 1 2否定 算法在每次迭代时把候选假设减半 2 微差异反例 生成与正例只有一个差异的实例 期望教师将其分类为反例 2 4 3不完全目标概念的应用 问题由于训练样例不够多 学习算法最后得到的G S集合包含多个假设 这种情况下 怎样使用学到的假设 即如何用它们对新实例进行分类 其可信度如何 处理方法1 当G S中的所有假设将实例x分类为正例 那么x为正例的可信度高 判断 x是否满足S中的每个假设 2 当G S中的所有假设将实例x分类为反例 那么x为反例的可信度高 判断 x是否不满足G中的每个假设 3 如果实例x满足的假设数目与不满足的假设数目相同 x最适合用作进一步学习的训练样例 4 如果实例x满足的假设数目多于不满足的假设数目 投票选举的结果将是x为正例 并附加一个可信度比例 2 5归纳偏执 2 5 1有偏假设空间2 5 2无偏学习器2 5 3归纳偏执 2 5 1有偏假设空间 SportDay的有偏假设空间对假设的描述从语法形式上有限制 如 只包含属性约束的合取式 这种限制的问题用例子说明 覆盖d1和d2的最特殊假设为 w n st c ch 但是它仍然太一般 而包含样例d3 原因是我们不允许哪怕最简单的析取式 这是学习的一种偏向 表示法偏执 2 5 2无偏学习器 无偏假设空间表达实例集合的所有子集的假设空间 在SportDay例子中 实例空间X的大小为96 可定义的概念为296个 而合取假设空间只能表示973个假设 因而它是一个偏执很大的假设空间 无偏假设空间 允许假设的析取式 合取式和否定式 例如概念 天气 晴朗或天气 多云 可表示为 s cld 2 5 2无偏学习器 无偏学习器的困境用SportDay例子说明在无偏假设空间进行学习的困难 设训练样例包含三个正例 x1 x2 x3 两个反例 x4 x5 则版本空间的S和G边界分别为 保守学习算法 S x1 x2 x3 G x4 x5 虽然 这种表示法表达概念的能力很强 但是除了S总是包含所有正例的析取式 G总是包含所有反例的析取式取非外 学习器无法进行其他的泛化和特殊化操作 2 5 2无偏学习器 归纳推理的基本属性如果不对目标概念的形式做预先假定 学习器从根本上无法对未见实例进行分类 偏执 Bias 概念描述的形式 感兴趣的属性 以及可使用的符号学习器采取保守的学习策略 泛化时 在覆盖新正例的前提下 泛化程度最小 狭化时 在排除新反例的情况下 特殊化程度最小 2 5 3归纳偏执 定义9归纳偏执 InductionBias 设X为实例集合 L为概念学习算法 令c为X上定义的任意概念 Dc x c x 为c的任意训练样例集 L xi Dc 表示经过数据Dc的训练后 L赋予实例xi的分类 L的归纳偏执是最小断言集合B 它使任意目标概念c和相应的训练样例Dc满足 xi X B Dc xi L xi Dc 其中 表示证明关系 2 5 3归纳偏执 为什么引入归纳偏执L学习器的归纳推理过程可以描述如下 Dc xi L xi Dc y z 表示z从y归纳得出 一般情况下 L xi Dc 的正确性无法证明 即 分类L xi Dc 无法从训练数据和新实例xi中演绎出来 问题是 应该在Dc xi上附加什么样的前提 才能演绎出L xi Dc 2 5 3归纳偏执 候选消去算法的归纳偏执目标概念c包含在给定的假设空间H中 由B c H Dc和xi演绎出L xi Dc 的证明 设B c H Dc x c x 无噪音 实例xi 则Consistent c Dc 为真 根据VSH Dc的定义 可演绎出c VSH Dc 另一方面 定义L xi Dc 为版本空间中所有假设的一致投票