上界说明样本足够时某个算法能够成功。下界提出另一问题:样本更少时,是否存在任何算法能一致地成功?下面的困难不在于计算缓慢,而在于缺少信息:从未观察到的标签仍可能取任一值。
打散集合上的困难族
设二元分类器类 打散互异的点 ,其中 。这就是说,这些点的每一种二元标记都由 中至少一个成员实现。设 为这些点上的均匀分布。学习器获得 个来自 的独立带标签样本,其标签由未知的固定目标 给出;学习器输出可测二元分类器。学习器可以随机化,也不必输出 的成员;其内部随机位独立于目标和样本。
记 。对随机化学习器,风险的概率或期望同时涉及样本和学习器的随机位。
定理 2.3.1
(未见点下界)
对每个这样的学习器,都存在某个固定目标 ,使得
特别地,若 ,存在某个固定目标满足 。
证明
(对打散集合上所有标记求平均)
暂时独立均匀地从 选取 个目标标签,且这些标签独立于样本输入和学习器的随机位。这个随机目标仅用于求平均:打散性质保证每一种标记都由原类中的一个目标实现。对样本点、其观察到的标签和学习器随机位取条件。对于每个未出现在样本中的点,它的目标标签仍是独立于所有这些信息的公平二元随机变量。无论学习器在该点预测什么,其条件错误概率都是 。
一个特定点未被抽到的概率为 。对所有点的条件错误求和并取平均,得到上述期望。由于这是对有限多个可实现目标标记求平均,至少有一个固定目标达到该值;在由此得到的学习问题中,这个目标在实际抽样前选定。
若 ,Bernoulli 不等式给出 ,因此该目标的期望风险至少为 。由于 ,
整理得到所述概率下界。
证明透视
每个假设在求平均论证中的作用
这个证明只有一步不显然:把未知目标换成随机目标,对学习器能看到的一切取条件,然后发现每个未见标签仍是公平硬币。用到三个假设,各在一处。
打散性质只在由随机标记回到原类时使用。它保证全部 种标记都可实现,因此平均是对 的真正成员取的。若改取 ,看过一个带标签样本后所有标签都已知,没有任何隐藏信息,平均误差为 。
的均匀性以及标签与样本输入的独立性用在取条件这一步。独立性使未见点的标签在给定学习器全部所见信息后仍是公平二元值,所以在该点任何预测的错误概率都不低于 。均匀性使每个点的权重为 ,且以相同概率 被漏掉;若 非均匀,同样的计算给出 。
论证之所以闭合,是因为有限多个数的平均不超过其最大值,所以某个固定标记的期望风险至少等于平均。选出的标记依赖于学习器和 ,但不依赖样本:随机目标在学习问题本身中从不存在。Bernoulli 不等式一步以及由期望转到概率一步属于常规计算,只用到 。
即使允许输出类外分类器和不受限计算,这也说明固定精度与置信度下所需样本数量必须随 至少线性增长。它并未说每个目标都困难,也未说学习器必然失败;它本身也没有证明对任意精度和置信度参数的完整依赖关系。
例。 若 、,则某个固定目标的期望风险下界为 。这里是有放回地抽取四次:重复抽到同一点不会揭示新标签,定理已经计入这种可能性。
置信度可能要求观察稀有样本
现在取两个被打散的点 ,固定 。令 、。选取两个可实现目标,它们在 处都标记为零,在 处的标记相反。令 为训练输入中没有 的事件,则 。
在 上,两个目标下带标签样本和学习器独立随机位的联合分布相同,且 在两个目标下的概率相同。对于每个可能的输出,其在 的二元预测至少与两个目标之一不一致。在该目标下,风险至少为 。对两个目标和学习器随机性求平均,得出某个固定目标满足
因此,若要保证两个目标下的失败概率均至多为 ,其中 ,必要条件是
第二个不等式利用 ()及 。所有对数均为自然对数。这是该困难族的必要条件,而不是一般 PAC 学习的充分样本量。每个学习问题中的目标和分布都是固定的,不能在看到样本后改变。
反例模式
训练误差为零不能证明泛化
错误命题:若分类器在训练样本上误差为零,则其真实误差很小。取 , 为 上全部 种标记的类, 为均匀分布,目标为 (依 的次序)。设样本为 。分类器 与两个观察到的标签都一致,故训练误差为 。但 在 、 处与 不同,所以 。而 本身同样与此样本一致,且 :样本无法区分 与 。这两次抽样的输入都落在 的概率为 ,而下界保证不论学习器如何,某个目标的期望风险至少为 。要修正这个命题,必须有控制整个类的陈述:当 相对于 的容量足够大时,一致分类器才保证风险小;而依本定理,若 打散 个点, 至少须为 的量级。
下界说明了什么,又没有说明什么
两种构造作用不同。第一种统计打散集合上可以隐藏多少独立标签选择。第二种使一个有信息的点变得稀有,从而解释对所要求失败概率的对数依赖。两者都没有使用运行时间假设。某个算法在简单分布或特定目标上表现很好,并不违反最坏情况的下界。
论证假设样本独立且预测为二元值。如果允许学习器主动查询所选点的标签,或者进一步限制数据分布和目标,这个证明并不会自动适用于改变后的学习模型。选出的困难目标可以依赖学习器,但样本仍是在目标固定后才抽取。
练习与解答
快速检查
(当 、 时,计算保证对某个目标成立的期望风险下界。)
解答 · 答案
。
快速检查
(当 、 时,计算两个目标中某一个的稀有事件失败概率下界。)
解答 · 答案
。
快速检查
(为什么学习器的内部随机化不能消除未见点论证?)
解答 · 答案
连同观察到的样本一起对学习器随机位取条件;每个未见标签仍是独立的公平二元随机变量。
快速检查
(第一个定理是否说每个目标的期望风险都至少为所示下界?解释原因。)
解答 · 答案
不是。求平均只证明对该学习器及样本量至少存在一个固定困难目标;其他目标可能很容易。