第十二章:计算学习理论
第十二章：计算学习理论
纲要 口概述 ●关注的问题 些概念及记号 口可学习性 ●什么是“学习” ●什么是“可学习的” ●假设空间复杂性对可学习性的影响 有限假设空间 ●无限假设空间:基于VC维的分析 无限假设空间:基于 Rademacher复杂度的分析 口稳定性
纲要 概述 ⚫ 关注的问题 ⚫ 一些概念及记号 可学习性 ⚫ 什么是“学习” ⚫ 什么是“可学习的” ⚫ 假设空间复杂性对可学习性的影响 ⚫ 有限假设空间 ⚫ 无限假设空间：基于VC维的分析 ⚫ 无限假设空间：基于Rademacher复杂度的分析 稳定性
关注的问题 口怎样刻画“学习”这个过程? 口什么样的问题是“可学习的”? 口什么样的问题是“易学习的”? 口对于给定的学习算法,能否在理论上预测其性能? 口理论结果如何指导现实问题的算法设计?
关注的问题 怎样刻画“学习”这个过程？ 什么样的问题是“可学习的”？ 什么样的问题是“易学习的”？ 对于给定的学习算法，能否在理论上预测其性能？ 理论结果如何指导现实问题的算法设计？
些概念及记号 口样例集:独立同分布样本,仅考虑二分类问题 D={(c1,y1),(a2,y2),…,(xrm,ym)},x;∈,v∈y={-1,+1} 口h为从礼到y的一个映射 泛化误差:分类器的期望误差 E(h;D)=P~D(h(m)≠y) ●经验误差:分类器在给定样例集上的平均误差 E(h; D) ∑(a)≠ m 由于D是D的独立同分布采样,因此h的经验误差的期望等于其泛化误差。 在上下文明确时将E(h;D)和E(h;D)分别简记为E(h)和E(hb
一些概念及记号 样例集：独立同分布样本, 仅考虑二分类问题 为从 到 的一个映射 ⚫ 泛化误差：分类器的期望误差 ⚫ 经验误差：分类器在给定样例集上的平均误差 由于 是 的独立同分布采样, 因此 的经验误差的期望等于其泛化误差。 在上下文明确时, 将 和 分别简记为 和
些概念及记号 口误差参数 ∈为E(h的上限,即E(h)≤e →表示预先设定的学得模型所应满足的误差要求 口一致性 若h在数据集D上的经验误差为0,则称h与D一致,否则不一致。 日不合( disagreement) 对于任意两个映射h1,h2∈→y,通过“不合”度量它们的差 d(hr, h2=PinD(h1(a) h2(a)
一些概念及记号 误差参数 为 的上限, 即 表示预先设定的学得模型所应满足的误差要求 一致性 若 在数据集 上的经验误差为0, 则称 与 一致, 否则不一致。 不合(disagreement) 对于任意两个映射 , 通过“不合”度量它们的差 别