什么是“可学习的” 定义PAC可学习( PAC Learnable) 令m表示从分布D中独立同分布采样得到的样例数目,0<∈,0<1, 对所有分布D,若存在学习算法C和多项式函数oly(,…,,),使得对于任 何m≥poly(1∈,1/6,size(m),size(c),C能从假设空间H中PAC辨识 概念类C则称概念类C对假设空间孔而言是PAC可学习的,有时也简称概 念类C是PAC可学习的
什么是“可学习的” 定义 PAC可学习(PAC Learnable) 令 表示从分布 中独立同分布采样得到的样例数目, , 对所有分布 ,若存在学习算法 和多项式函数 , 使得对于任 何 , 能从假设空间 中PAC辨识 概念类 , 则称概念类 对假设空间 而言是PAC可学习的，有时也简称概 念类 是PAC可学习的
什么是“可学习的” PAC可学习性描述的是概念类C的性质,若考虑到对应学习算法C的时间复 杂度,则有: 定义PAC学习算法( PAC Learning Algorithm) 若学习算法C使概念类C为PAC可学习的,且C的运行时间也是多项式 函数poly(1/e,1/6,.ie(m),size(C),则称概念类C是高效PAC可学习 ( efficiently PAc learnable)的,称C为概念类C的PAC学习算法
什么是“可学习的” PAC可学习性描述的是概念类 的性质，若考虑到对应学习算法 的时间复 杂度，则有： 定义 PAC学习算法(PAC Learning Algorithm) 若学习算法 使概念类 为PAC可学习的, 且 的运行时间也是多项式 函数 , 则称概念类 是高效PAC可学习 (efficiently PAC learnable)的, 称 为概念类 的PAC学习算法
什么是“可学习的” 假定学习算法C处理每个样本的时间为常数,则C的时间复杂度等价于其样 本复杂度.于是,我们对算法时间复杂度的分析可变为对样本复杂度的分析 定义样本复杂度( Sample Complexity) 满足PAC学习算法C所需的m≥poly(1/e,1/6,size(c),size(c) 中最小的m,称为学习算法C的样本复杂度
什么是“可学习的” 假定学习算法 处理每个样本的时间为常数, 则 的时间复杂度等价于其样 本复杂度. 于是, 我们对算法时间复杂度的分析可变为对样本复杂度的分析. 定义 样本复杂度(Sample Complexity) 满足PAC学习算法 所需的 使概念类 为 中最小的 , 称为学习算法 的样本复杂度
什么是“可学习的” 口PAC学习的意义 ●给出了一—个抽象地刻画机器学习能力的框架,基于这个框架可以对很 多重要问题进行理论探讨。 ●研究某任务在什么样的条件下可学得较好的模型? ●某算法在什么样的条件下可进行有效的学习? 需要多少训练样例才能获得较好的模型? ●把对复杂算法的时间复杂度的分析转为对样本复杂度的分析
什么是“可学习的” PAC学习的意义： ⚫ 给出了一个抽象地刻画机器学习能力的框架, 基于这个框架可以对很 多重要问题进行理论探讨。 ⚫ 研究某任务在什么样的条件下可学得较好的模型？ ⚫ 某算法在什么样的条件下可进行有效的学习？ ⚫ 需要多少训练样例才能获得较好的模型？ ⚫ 把对复杂算法的时间复杂度的分析转为对样本复杂度的分析
口假设空间孔的复杂度是影响可学习性的重要因素之 一般而言,孔越大,其包含任意目标概念的可能性越大,但从中找到某 个具体概念的难度也越大 ●|HL有限时,我们称升为“有限假设空间”,否则称为“无限假设空间
假设空间 的复杂度是影响可学习性的重要因素之一 ⚫ 一般而言, 越大, 其包含任意目标概念的可能性越大, 但从中找到某 个具体概念的难度也越大. ⚫ 有限时, 我们称 为“有限假设空间”, 否则称为“无限假设空间