wordpress 文字插件下载,seo工具助力集群式网站升级,建筑室内设计软件,阿里巴巴国际站买家版目录 12.1基础知识
12.2 PAC学习
12.3有限假设空间
12.3.1可分情形
12.3.2不可分情形
12.4VC维
12.5 Rademacher复杂度 12.1基础知识 计算学习理论研究的是关于通过计算来进行学习的理论#xff0c;即关于机器学习的理论基础#xff0c;其目的…目录 12.1基础知识
12.2 PAC学习
12.3有限假设空间
12.3.1可分情形
12.3.2不可分情形
12.4VC维
12.5 Rademacher复杂度 12.1基础知识 计算学习理论研究的是关于通过计算来进行学习的理论即关于机器学习的理论基础其目的是分析学习任务的困难本质为学习算法提供理论保证并根据分析结果指导算法设计。 给定样例集 {(X1 , Y2) , (X2Y2 )... (Xm , Ym)} ,。 令h为X到Y 的一个映射其泛化误差为 h在D上的经验误差为 后面部分将研究经验误差与泛化误差之间的逼近程度会用到几个常用不等式: 1.Jensen 不等式:对任意凸函数 f(x 有 2.HoefIding 不等式 : 若 为m个独立随机变量且满足 则对任意 有: 3.McDiarmid 不等式 : 若 为m个独立随机变量且对任意1im函数f 满足 12.2 PAC学习 计算学习理论中最基本的是概率近似正确 ( 简称 PAC) 学习理论 。 PAC 辨识 :对 所有 和分布D,若存在学习算法其输出假设 满足: 则称学习算法 能从假设空间中 PAC 辨识概念类 C. PAC 可学习 : 令m表示从分布D中独立同分布采样得到的样例数目对所有分布D 若存在学习算法和多项式函数poly,使得对任何mpoly. PAC 学习算法: 若学习算法使概念类 C为PAC 可学习的且 的运行时间也多项式函数 poly 则称概念类 C 是高效 PAC 可学习 的称为概念类C的 PAC 学习算法. 样本复杂度 : 满足 PAC 学习算法所需的 m poly 中最小的m称为学习算法 的样本复杂度. 12.3有限假设空间 12.3.1可分情形 可分情形意味着目标概念c属于假设空间H即 。对 PAC 学习来说只要训练集D 的规模能使学习算法以概率 找到目标假设的近似即可. 我们先估计泛化误差大于 但在训练集上仍表现完美的假设出现的概率. 假定 h的泛化误差大于 对分布 D上随机来样而得的任何样例 (x y)有 由于D包含 m个从 D 独立同分布采样而得的样例因此,h与D 表现一 致的概率为 12.3.2不可分情形 引理若训练集D包含m个从分布D上独立同分布采样而得的样例则对任意 有 推论 若训练集D 包含 m个从分布 D上独立同分布来样而得的样例 则对任意 以至少 的概率成立: 定理 若H为有限假设空间 则对任意 有 12.4VC维 现实学习任务所面临的通常是无限假设空间欲对此种情形的可学习性进行研究需度量假设空间的复杂度.最常见的办法是考虑假设空间的 VC维。1. 增长函数 增长函数也称为VC维增长函数描述了在给定假设空间下能够被假设空间所“分割”或“覆盖”的训练样本的最大数量。具体来说它衡量的是假设空间中能够对样本集进行不同标签分配的能力。增长函数的定义如下对于一个假设空间 H )和一个样本集 S 大小为 m 增长函数 ( ) 表示假设空间 H 能够对样本集 S 进行的不同标签分配的最大数量。 2. 打分 打分是一个与增长函数紧密相关的概念。它描述了一个假设空间能否对某个样本集进行所有可能的标签分配。具体来说一个假设空间 (H )能打分一个样本集 S 大小为 m如果 H 中的假设可以对 S 中的每一种可能的标签分配进行匹配。 3. 打散 打散或称为分裂是一个与打分相关的概念描述了假设空间能否在所有可能的标签分配下对样本集进行准确的分类。具体来说假设空间 H 能打散一个样本集S 大小为 m 如果H能对 S 中的每一种标签分配进行正确的分类。换句话说如果假设空间 H 能生成所有可能的标签分配。 4. VC维 VC维是衡量一个假设空间复杂度的指标它反映了假设空间能够打散的最大样本集的大小。具体来说VC维是一个假设空间 H 可以打散的最大样本集的大小。即如果假设空间 H 能打散大小为 d 的样本集但不能打散大小为 d1 的样本集那么 H 的VC维就是 d。 增长函数 衡量假设空间对样本集进行的标签分配的能力。打分 描述假设空间是否能够覆盖所有可能的标签分配。打散 具体指假设空间对样本集进行所有可能标签分配的能力。VC维 是衡量假设空间复杂度的关键指标反映了最大打散能力。 12.5 Rademacher复杂度 Rademacher 复杂度 是另一种刻画假设空间复 杂度的途径与 vc 维不同的是它在一定程度上考虑了数据分布. 给定训练集 {(X1 , Y2), (X2Y2)... (Xm , Ym)} 假设h 的经验误差为: 经验误差最小的假设是: 是Rademacher 随机变量. 函数空间 F 关于 Z 的经验 Rademacher 复杂度: 函数空间 F 关于Z 上分布D的 Rademacher 复杂度
