VC 维统计可能的标签模式,但本身并不告诉我们如何找到分类器。坐标轴平行盒子提供一个易于实现的算法和初等的分布无关证明。关键思想是几何的:如果学习器漏掉了大量正样本概率,那么目标盒的某个大量边界区域必定没有被样本命中。
模型与学习器
固定整数 。未知目标盒为 ,所有端点有限且 。从 上任意分布 独立抽取 个样本 ,标签无噪声:。不假设分布有密度,也不排除原子。盒 的总体错误率为
定义 1.3.1
(最紧外包盒)
若至少观察到一个正样本,就输出包含所有正样本的最小闭坐标轴平行盒子:
若没有正样本,则输出空集。
因此假设类包含空集。在实数比较模型中,该规则使用 次坐标比较及 个端点存储;位复杂度取决于输入编码。
引理 1.3.2
(没有假阳性与一致性)
在无噪声模型下,对每份样本都有 。因此 包含每个观察到的正样本,并且不含任何观察到的负样本,即与样本一致。
证明
(最小值与最大值留在目标之内)
每个正样本都在 中。每个坐标上的最小值和最大值都在对应目标区间内,所以 ; 为空时也成立。因此所有观察到的正样本都在 中,所有观察到的负样本在 外,也必在 外。
学习器可能产生假阴性,但没有假阳性。与样本一致的盒未必等于目标盒。
含原子时的边界带
定理 1.3.3
(盒的分布无关样本界)
设 。若
则 。保证适用于每个分布 和上述每个目标盒;对数为自然对数。
证明
(边界带与并集界)
令 ,。若 ,由于学习器没有假阳性,每份样本都满足 。否则 。对每个坐标 ,选择阈值 ,使
即使有原子,这些阈值也存在。例如,令 为满足 的 的下确界;因为 、目标坐标有界,且 使定义集合非空,所以下确界有限。右连续性给出第一个不等式;对每个 有 ,令 并用从下连续性得第二个。对 使用同样论证得到上阈值。阈值不必分割原子,各不等式也不必取等。
将 个事件 与 称为边界带。若样本命中每条带,则至少有一个正样本,故 非空。每个坐标都存在不大于 的正样本和不小于 的正样本。因此,被 漏掉的目标正点必对某个 满足 或 。由 (3) 和并集界,其概率至多为 ;由于 ,这就是全部分类风险。即使 ,这个论证仍成立。
每条带的概率至少为 ,所以 次独立抽样漏掉某条固定带的概率至多为 。对 条带使用并集界,得到
各带可以重叠,漏掉它们的事件也不必独立。独立性用于控制多次抽样漏掉一条固定带的概率。
证明透视
为什么同时使用非严格与严格不等式?
非严格边界带有足够概率被抽中,即使阈值处有原子也如此。一旦样本命中该带,这一侧只有严格越过阈值的点可能被漏掉;这些严格尾部的概率至多为 。我们不需要将原子切成指定概率质量。
例子与两个误区
例题 1.3.4
(一份误导性样本)
在二维空间中,令 均匀分布于 四点,目标为 。假设 且观察到的两个正样本是 和 。输出为退化盒 ,它符合样本,却漏掉另外两点,风险为 。这样的样本具有正概率;PAC 保证控制误导性样本发生的频率,并不声称它不可能发生。
例题 1.3.5
(三维的一次运行及其样本量)
令 ,观察到正样本 、、。逐坐标取最小值和最大值,得 。对 、,不等式 (2) 要求 ,所以 即可。如果样本中没有任何正样本,输出就是空集,其风险等于 。在 (2) 成立时,除非 (此时风险本来就小于 ),这种情况发生的概率至多为 。
例题 1.3.6
(稀少的正样本:低于阈值的情形)
令 、、,所以 ,并设只有 的质量落在 内。由于 ,证明在第一步就结束:无论样本如何,即使输出为空集,也有 ,因为学习器没有假阳性。这种情况不需要任何样本量条件。
常见错误
(期望学习器重建边界)
该学习器不能从任意 中精确识别目标。若 集中于原点,则所有包含原点的目标盒产生相同带标签数据;它们的边界可以不同,而只要在原点一致,任何盒的风险都为零。PAC 错误依赖分布,并不是几何边界重建。
常见错误
(以为每条带的概率恰好等于 )
若分布有密度,可以选取阈值使带的概率恰好为 。有原子时一般做不到:阈值处的单个原子可以带有大于 的质量。这就是 (3) 对带使用非严格不等式、对尾部使用严格不等式,而不要求等号的原因。
证明同时使用了无噪声标签,下面的例子具体说明样本界对标签噪声并不稳健。
反例模式
标签噪声破坏没有假阳性的不变量
取 、, 在 处质量为 ,在 处质量为 。设在 处的每个样本以概率 独立地被误标为正,而 处的标签正确。取 ,不等式 (2) 要求 ,故取 。每次抽样得到 处的噪声正样本的概率为 ,所以样本以概率 含有这样的点。此时 包含 ,而 在 之外,相对真实目标的风险至少为 。所声称的失败概率 被大幅超出。证明所依赖的正是不变量 ;任意标签噪声需要不同的分析。
练习与解答
快速检查
(若 中的正样本为 和 ,返回什么盒?)
逐坐标取最小值和最大值。
解答 · 答案
第一个坐标为 ,第二个坐标为 ,所以盒为 。
快速检查
(取 、、,给出 (2) 的充分整数样本数。)
计算 ,其中 。
解答 · 答案
,所以 即可。
快速检查
(在本模型下,为什么负训练样本不可能落入返回的盒?)
比较返回的盒与目标盒。
解答 · 答案
返回的盒包含于 ,而每个负点在 外。
快速检查
(在 (3) 中存在原子时,为什么下边界带的非严格不等式不能与严格尾部不等式互换?)
想象一个恰好位于阈值处的原子。
解答 · 答案
阈值处可能有正质量:包含该原子可能是使边界带质量至少为 所必需的,而排除该原子才能使尾部质量至多为 。例如,若阈值 处原子质量为 且下方没有正质量,则非严格带质量为 ,严格尾部质量为零。不必取原子的任意一部分。