第十二章:计算学习理论
第十二章：计算学习理论
纲要 口概述 ●关注的问题 些概念及记号 口可学习性 ●什么是“学习” ●什么是“可学习的” ●假设空间复杂性对可学习性的影响 有限假设空间 ●无限假设空间:基于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) 对于任意两个映射 , 通过“不合”度量它们的差 别
什么是“学习” 口概念( concept) 概念是从样本空间λ到标记空间υ的映射,它决定示例m的真实标记J ●目标概念 如果对任何样例,y)均有c(m)=y成立,则称C为目标概念 ●概念类( concept class 所有我们希望学得的目标概念所构成的集合称为"概念类,用符号C表示
什么是“学习” 概念(concept) 概念是从样本空间 到标记空间 的映射, 它决定示例 的真实标记 . ⚫ 目标概念 如果对任何样例 均有 成立, 则称 为目标概念. ⚫ 概念类(concept class) 所有我们希望学得的目标概念所构成的集合称为”概念类”, 用符号 表示
什么是“学习” 口假设空间( hypothesis space) 给定学习算法C,它所考虑的所有可能概念的集合,用符号升表示 ●由于学习算法事先并不知道概念类的真实存在,因此H和C通常是不同的, 学习算法会把自认为可能的目标概念集中起来构成孔 ●对于h∈升,由于并不能确定它是否真的是目标概念,因此称为“假设” 显然,h也是从样本空间到标记空间y的映射 ●学习过程可以视为C在冲中进行的搜索过程
什么是“学习” 假设空间(hypothesis space) 给定学习算法 , 它所考虑的所有可能概念的集合, 用符号 表示. ⚫ 由于学习算法事先并不知道概念类的真实存在, 因此 和 通常是不同的, 学习算法会把自认为可能的目标概念集中起来构成 . ⚫ 对于 ,由于并不能确定它是否真的是目标概念, 因此称为“假设”. 显然, 也是从样本空间 到标记空间 的映射. ⚫ 学习过程可以视为 在 中进行的搜索过程
什么是“学习” 口可分的与不可分的 ●可分的( separable) 若目标概念C∈,即H中存在假设能将所有的示例完全正确分开(按照与 真实标记一致的方式),则称该问题对学习算法C是“可分的”( separable),也 称“一致的”( consistent) ●不可分的( separable) 若目标概念C,则升中不存在任何假设能将所有的示例完全正确分开, 则称该问题对学习算法C是“不可分的”(non- separable),也称“不一致的” (non-consistent)
什么是“学习” 可分的与不可分的 ⚫ 可分的(separable) 若目标概念 , 即 中存在假设能将所有的示例完全正确分开(按照与 真实标记一致的方式), 则称该问题对学习算法 是“可分的”(separable), 也 称“一致的”（consistent). ⚫ 不可分的(separable) 若目标概念 ,则 中不存在任何假设能将所有的示例完全正确分开， 则称该问题对学习算法 是“不可分的”(non-separable), 也称“不一致的” （non-consistent)
口对于给定训练集D,我们希望基于学习算法C学得的模型所对应 的假设九尽可能接近目标概念C 为什么不是希望精确地学到目标概念c呢? 机器学习过程受到很多因素的制约 获得的训练集刀往往仅包含有限数量的样例,因此通常会存在一些在上“等效” 的假设,学习算法无法区别这些假设; ●从分布D采样得到D的过程有一定的偶然性,即便对同样大小的不同训练集,学 得结果也可能有所不同
对于给定训练集 , 我们希望基于学习算法 学得的模型所对应 的假设 尽可能接近目标概念 . 为什么不是希望精确地学到目标概念c呢？ 机器学习过程受到很多因素的制约 ⚫ 获得的训练集 往往仅包含有限数量的样例, 因此通常会存在一些在 上“等效” 的假设, 学习算法无法区别这些假设; ⚫ 从分布 采样得到 的过程有一定的偶然性, 即便对同样大小的不同训练集, 学 得结果也可能有所不同
什么是“可学习的” 口概率近似正确( Probably approximately correct,PAC) 我们希望以比较大的把握学得比较好的模型,即以较大概率学得误差 满足预设上限的模型 令δ表示置信度,上述要求形式化为 定义PAC辨识( PAC Identify) 对0<,6<1,所有c∈C和分布D,若存在学习算法C,其输出假 设h∈H满足 P(E(hb)≤)≥1-6, 则称学习算法C能从假设空间中PAC辨识概念类? 这样的学习算法C能以较大概率(至少1—)学得目标概念c的近似(误差最多为)
什么是“可学习的” 概率近似正确(Probably Approximately Correct, PAC) 我们希望以比较大的把握学得比较好的模型, 即以较大概率学得误差 满足预设上限的模型. 令 表示置信度，上述要求形式化为： 定义 PAC辨识(PAC Identify) 对 ,所有 和分布 ,若存在学习算法 , 其输出假 设 满足 则称学习算法 能从假设空间 中PAC辨识概念类 . 这样的学习算法 能以较大概率(至少 )学得目标概念 的近似(误差最多为 )