口假设空间孔的复杂度是影响学习任务难度的重要因素之 怡PAC可学习( properly pac learnable) 假设空间包含了学习算法C所有可能输出的假设,在PAC学习中假设空 间与概念类完全相同,即升=C ●直观地看,这意味着学习算法的能力与学习任务“恰好匹配”,即所有候选假 设都来自概念类。 ●然而在现实应用中我们对概念类C通常一无所知,设计一个假设空间与概念类 恰好相同的学习算法通常是不切实际的。 口研究的重点:当假设空间与概念类不同的情形,即升≠C时
假设空间 的复杂度是影响学习任务难度的重要因素之一 ⚫ 恰PAC可学习(properly PAC learnable) 假设空间 包含了学习算法 所有可能输出的假设, 在PAC学习中假设空 间与概念类完全相同, 即 . ⚫ 直观地看, 这意味着学习算法的能力与学习任务“恰好匹配”, 即所有候选假 设都来自概念类。 ⚫ 然而在现实应用中我们对概念类 通常一无所知, 设计一个假设空间与概念类 恰好相同的学习算法通常是不切实际的。 研究的重点：当假设空间与概念类不同的情形，即 时
有限假设空间 口可分情况 目标概念C属于假设空间升,即C∈用 给定包含m个样例的训练集D,如何找出满足误差参数的假设呢 种简单的学习策略 由于存在于假设空间升中,因此任何在训练集冂上出现标记错误的假设肯定不 是目标概念C. 保留与刀一致的假设,剔除与刀不一致的假设 ●若训练集冂足够大,则可不断借助D中的样例剔除不一致的假设,直到升中仅剩 下一个假设为止,这个假设就是目标概念C
有限假设空间 可分情况 目标概念 属于假设空间 ,即 . 给定包含m个样例的训练集D，如何找出满足误差参数的假设呢？ 一种简单的学习策略 ⚫ 由于 存在于假设空间 中, 因此任何在训练集 上出现标记错误的假设肯定不 是目标概念 . ⚫ 保留与 一致的假设, 剔除与 不一致的假设. ⚫ 若训练集 足够大, 则可不断借助 中的样例剔除不一致的假设, 直到 中仅剩 下一个假设为止, 这个假设就是目标概念
有限假设空间 ●通常情形下,由于训练集规模有限,假设空间中可能存在不止一个与刀 致的“等效”假设,对这些假等效假设,无法根据刀来对它们的有优劣 做进一步区分 到底需要多少样例才能学得目标概念c的有效近似呢? ●训练集D的规模使得学习箅法C以概率1-δ找到目标假设的∈近似,则 m2-InH+In) ●可分情况下的有限假设空间升都是PAC可学习的,输出假设h的泛化误差随样例 数目的增多而收敛到0,收敛速率为O()
有限假设空间 ⚫ 通常情形下, 由于训练集规模有限, 假设空间 中可能存在不止一个与 一致的“等效”假设, 对这些假等效假设, 无法根据 来对它们的有优劣 做进一步区分. 到底需要多少样例才能学得目标概念c的有效近似呢？ ⚫ 训练集 的规模使得学习算法 以概率 找到目标假设的 近似, 则： ⚫ 可分情况下的有限假设空间 都是PAC可学习的, 输出假设 的泛化误差随样例 数目的增多而收敛到 , 收敛速率为
有限假设空间 口不可分情况 对于较困难的学习问题,目标概念C不属于假设空间,即假定对 于任何h∈礼,E(h)≠0,升中的任何一个假设都会在训练集上出 现或多或少的错误 定理121 若为有限假设空间0<6<1,则对任意h∈,有 PE(b)-E(b)|≤ In H+In(2/8 2m >1-6
有限假设空间 不可分情况 对于较困难的学习问题, 目标概念 不属于假设空间 , 即假定对 于任何 , 中的任何一个假设都会在训练集上出 现或多或少的错误. 定理12.1 若 为有限假设空间 ,则对任意 , 有