计算学习理论.pdfVIP

王 郭 魏 翔 宇 p 概述 l 关注的问题 l 一些概念及记号 p 可学习性 l 什么是 “学习” l 什么是 “可学习的” l 假设空间复杂性对可学习性的影响 l 有限假设空间 l 无限假设空间：基于VC维的分析 l 无限假设空间：基于Rademacher复杂度的分析 p 稳定性 p 怎样刻画 “ ”这个过程 ？ p 什么样的问题是 “ ” ？ p 什么样的问题是 “ ” ？ p 对于给定的学习算法，能否在理论上预测其性能 ？ p 理论结果如何指导现实问题的算法设计 ？ p样例集 ：独立同分布样本, 仅考虑二分类问题 p 为从 到 的一个映射 l 泛化误差 ：分类器的期望误差 l 经验误差 ：分类器在给定样例集上的平均误差 由于 是 的独立同分布采样, 因此 的经验误差的期望等于其泛化误差。 在上下文明确时, 将 和 分别简记为 和 . p 误差参数 为 的上限, 即 表示预先设定的学得模型所应满足的误差要求 p 一致性 若 在数据集 上的经验误差为0, 则称 与 一致, 否则不一致。 p 不合(disagreement) 对于任意两个映射 , 通过 “不合”度量它们的差 别 p 概念(concept) 概