有限类定理可以保证一致假设具有泛化能力,却未必解决如何计算出这样一个假设。单调合取式让我们同时看到这两个部分:简单算法能找到一致规则,而独立样本论证能控制其总体误差。结果与分布无关,但依赖无噪声的可实现性。
模型与删除规则
定义 1.2.1
(单调合取式、目标与风险)
设 、,对 定义单调合取式
空合取式是恒为 1 的常数。未知目标是某个固定的 ; 独立同分布于 上任意固定分布 ,标签无噪声:。候选规则 的风险为 。
学习器从 开始。对每个标签为 1 的样本,它删除所有满足 的坐标 。更新时忽略负样本,最后输出 。计算至多检查 个坐标值,除样本本身外使用 工作存储空间。若没有正样本,它输出所有 个变量的合取式。
例题 1.2.2
(用正样本删除坐标)
当 时,取目标 。正样本 和 分别删除坐标 4 和 2,剩下 。删除步骤不需要负样本 ;所得合取式将它标为零。另一个样本即使也一致,仍可能留下额外坐标。
例题 1.2.3
(没有正样本:所有变量的合取式)
设 ,目标为 。假设样本只含负样本 和 。没有坐标被删除,所以 ,输出为 。两个负样本在各自的坐标中都有零,输出把它们标为 0,因此是一致的。它的风险是 的概率,即目标的正点中除 以外的部分。若 的大部分质量落在那里,风险就很大。这并不矛盾:这样的样本正是“样本量太小、没有见到正样本”的罕见事件,而下面的定理说明 足够大时这种事件的概率很小。
例题 1.2.4
(代入样本量的界)
取 、、。则 ,,所以
定理保证的最小整数是 。这个类有 个成员, 却只有几百:界对 是线性的,因为类只通过 进入。把 减半为 会使要求加倍,,即 ;把 平方为 只增加约 个样本。
输出为何一致
引理 1.2.5
(删除式学习器的不变量)
在无噪声的可实现模型中,删除式学习器维持的集合 在每一步都满足 。因此输出 与全部 个样本一致,并且对每个 , 蕴含 。
证明
(目标坐标从不被删除)
每个真正的正样本对所有 都满足 。因此目标坐标绝不会被删除,在每一步都有 。结束时,每个观察到的正样本在每个保留坐标上都是 1,所以被 标为 1。每个观察到的负样本至少有一个目标坐标为零;由于所有目标坐标都保留下来, 将它标为 0。因此即使没有正样本,输出也与全部 个样本一致。
此外, 蕴含 。学习器可能因为保留多余变量而出现假负错误,但在上述假设下不会出现假正错误。这种单侧错误是该算法的不变量,不是任意一致学习器的性质。
证明透视
保留额外变量会缩小正区域
唯一不显然的一步,是把删除规则读成关于下标的陈述:只有当某个标签为 1 的样本在某坐标上为零时,该坐标才被删除。证明用到两个假设。标签无噪声,使每个标签为 1 的样本都是目标的真正正样本,于是所有目标坐标在其上都等于 1,没有一个会被删除。可实现性使每个负样本违反目标,所以它在某个目标坐标上为零。
两个包含关系方向相反。对下标集合有 ;对正区域有 ,因为给合取式增加变量会使它更难满足。前者给出负样本上的一致性,后者给出没有假正错误。混淆这两个方向会颠倒对假正和假负错误的结论。
论证得以完结,是因为每个保留的坐标都从未在正样本上见到为 0,而目标坐标绝不会被删除。若有一个正标签被破坏,第一步就失效,“预测与识别目标”一节末尾会说明。
分布无关的样本保证
定理 1.2.6
(具体的可实现情形 PAC 保证)
固定 和 。如果
则对样本取概率,输出满足 的概率至少为 。对数均为自然对数。该界对每个 和类中的每个目标合取式成立。
证明
(对所有合取式作并集界)
包括空合取式在内,共有 个合取式。固定一个满足 的候选 。对每个独立带标签样本,它与目标一致的概率至多为 ,因此与全部 个样本一致的概率至多为 。对这个固定有限类使用并集界,存在任何这样的一致坏候选的概率至多为 。在其补事件上,每个一致候选的风险都小于 。删除式学习器的输出一致,所以满足该界。
该界对所有分布一致成立,并非以某个有利样本为条件。证明中使用了有限类,但算法无需枚举全部 个候选。保证针对预测误差,而非精确恢复目标变量集合。
揭示遗漏证据的另一种证明。 对每个坐标,记 。在抽样之前固定任意坐标 。若 ,每个独立样本至少以 的概率提供删除它的证据。该坐标在全部 个样本后存活的概率至多为 。如果没有这样的坐标存活,一个假负结果必然满足 且某个保留坐标等于 0,所以并集界给出风险严格小于 。因此失败概率至多为 。这个替代界可能比有限类界更宽松,但明确体现了稀有正样本的作用。作并集界的事件不必独立;独立性用在 个样本之间。
预测与识别目标
反例模式
相关变量妨碍精确识别
取 ,分布只支撑在 和 上。目标 和 在这个支撑集上给出相同标签,尽管它们在 和 上不同。无论获得多少来自该分布的独立同分布带标签数据,都无法区分所选目标。两个规则在 下都可以有零风险。分布无关的 PAC 准确性并不保证识别目标表示,也不保证在分布支撑集外的点上正确。
常见错误
(在负样本上删除坐标)
很容易想到同样用负样本修剪,即删除负样本取 0 的每个坐标。上面的例子已经说明这是错的:目标为 时,负样本 只在坐标 3 上为 0,而坐标 3 正是目标坐标,这条规则会删掉目标需要的变量。负样本只说明某个目标坐标为 0,却没有说明是哪一个。只有正样本能提供删除的证据。
常见错误
(把类的大小当成运行时间或样本量)
证明数了全部 个合取式,但学习器从不枚举它们,样本量只通过 依赖于这个类。运行时间是 ,样本量对 是线性的。类的大小出现在分析中,不出现在算法中。
稀有证据也可能延迟学习,却不违反定理。令目标为空合取式, 的概率为 , 的概率为 。若 次抽样全是 ,其概率为 ,则没有坐标被删除,输出的风险为 。一次 抽样是正样本,会删除每个坐标,得到恒为一的目标。高概率界使误导性样本足够稀有,而不是宣称它们不可能发生。
任意标签噪声会破坏上述证明。当 、目标为 时,输入 0 处一个被破坏成正标签的样本会删除真实变量,此后输出恒为 1,并可能产生假正错误。有噪声的模型需要另外的假设和分析。
练习与解答
快速检查
(当 时,处理正样本 和 。输出是什么?它把 标为何值?)
删除每个正样本取 0 的坐标。
解答 · 答案
第一个正样本删除坐标 3,第二个删除坐标 2。输出为 ,把 标为 0。
快速检查
(当 、、 时,给出定理所要求的充分整数样本量。)
用自然对数代入,再向上取整。
解答 · 答案
取 。
快速检查
(若未观察到正样本,在无噪声可实现模型中输出为何仍然一致?)
看负样本对目标坐标有何要求。
解答 · 答案
每个负样本在某个目标坐标上为零,而所有目标坐标都保留在输出中,所以输出把每个负样本标为 0。
快速检查
(在 下风险为零是否意味着所选下标集合等于 ?说明理由。)
对照上面的双变量例子。
解答 · 答案
不意味着。相关坐标可以使不同合取式在 的整个支撑集上相同,如上面的双变量例子。