对样本的简短解释
分类器可能仅因为假设类足够灵活而拟合样本。另一种可能是:它能从样本的一小部分重构出来。如果是这样,大部分观测值并非指定该分类器所必需,可以用来检验由保留观测值确定的假设。这个想法即使在整个假设类无限时,也能导出泛化界。
保留哪些观测值是在看到数据后决定的,因此不能自动把它们视为随机训练集、把其余部分视为独立测试集。证明必须考虑所有可能保留的指标和所有可能的附加消息。对数据依赖的压缩,这种计数是主要的数学代价。
精确的压缩模型
设 是带标签样本 上的分布,从 独立同分布地抽取 。对分类器 ,记 。假设重构规则产生的所有分类器均可测,且下文使用的选择、损失和风险事件可测。
定义 4.1.1
(带附加信息的压缩方案)
确定性的压缩过程选择至多含 个位置的子集 ,以及恰好 个附加信息比特。固定的确定性重构规则只接收按指标递增排列的所选带标签样本及这 个比特,返回分类器 ;它不接收其余观测值。附加字符串可以依赖整个样本,所以证明要计入全部 种可能。如果不需要附加信息,取 。
假设对于 ,最终重构出的分类器以概率一与全部 个样本一致。例如,在可实现的采样模型中,为该模型构造的压缩方案可以保证这一点。定理并不声称每个分布或假设类都存在这样的方案。样本值允许重复:选择针对位置,二项式计数针对位置而不是不同的数值。
压缩界
定理 4.1.2
(有限附加信息下的一致压缩)
设 和 为整数。在上述模型中,对每个 ,以至少 的概率,重构分类器满足
对数均为自然对数。此界可能大于一,此时结论仍正确,但不提供有效信息。
概念视角组合
这个界在计算描述的数目
一个描述是一个配对:至多 个位置的集合,加上一个 位比特串。这样的描述共有 个,所以界可写成 。取 、,得 ,;若 ,界为 。
证明
(计算每个可能的保留集合与附加字符串)
对 ,固定一个大小为 的位置集合 和一个特定的 比特附加字符串。对这些位置的样本取条件后,重构规则得到一个固定分类器 ;其余 个样本仍是来自 的独立抽样。如果 ,则所有剩余样本都与 一致的条件概率至多为
此界一致适用于保留样本的各种取值。大小为 的指标集合有 种,附加字符串有 种。对所有 、指标集合和字符串使用并集界,故“存在某个此类重构,其真实误差大于 且与所有未保留样本一致”的概率至多为
实际压缩器可以用整个样本选择指标和附加比特;其输出仍在上述计数之中。全样本一致性保证它与未保留样本一致。将最后的表达式设为 ,在所得阈值小于一时得到结论;若阈值至少为一,则风险至多为一,结论立即成立。
证明透视
为什么可以计算依赖数据的选择
独立性假设只用在一处:对一个固定的下标集合和附加字符串,给定所选值后,其余 个样本仍是来自 的独立抽样,由此得到因子 。实际选择不必独立于这些其余样本。关键的一步,是先对所有可能的选择与字符串使用并集界,再问压缩器实际选了哪一种。一致性假设使论证完结:无论实际产生哪个重构,它都属于被计数的、与全部未保留样本一致的那些之一。出现的是 而不是 ,因为保留的样本可以免费拟合,所以只需考虑最坏情形 。若省去这一计数,就会把依赖数据的留出集误当作事先固定的集合。
例题 4.1.3
(代入压缩界)
、、、 时,指标集合数为 。界为
这是充分的高概率界,不是某次运行的精确风险。指标集合之和是证明中的代价:重构规则实际接收的是保留样本和比特,而不是所有可能集合的单独描述。样本小时同一公式说明不了多少。取 、、、,指标集合数为 ,界为 ,大于一:结论仍正确,但无法由它得出风险的任何信息。
保留两个样本的阈值方案
命题 4.1.4
(阈值类可压缩为两个样本和两个比特)
设分类器为实数上的 以及两个常值分类器,并假设 可由此类实现:其中某个 满足 。则几乎必然地,样本具有 、 的压缩方案,其重构与全部 个样本一致。因此 时上面的定理适用。
证明
(最大负点与最小正点)
每个有限样本都几乎必然与 一致。若两类标签都出现,选最大的观测负样本点 和最小的观测正样本点 ;若同一个极值出现在多个位置,选择最小下标。与 一致蕴含 :若 ,每个负点都小于 ,每个正点都大于或等于 。取 重构 。每个观测负点至多为 ,每个观测正点至少为 ,故重构结果一致。
若标签全为零,则不保留点,重构常零分类器;若标签全为一,则重构常一分类器。两个固定附加比特足以区分这些情形和混合情形。这里并不声称它是最省的编码。虽然阈值有无限多个,定理仍适用于压缩后的重构。若同时出现两种标签却次序颠倒,样本便不与此类一致,因此不能悄悄删去一致性假设。
例题 4.1.5
(由六个带标签点重构阈值)
取样本 、、、、、,位置为 至 。最大负点是位置 1 的 。最小正点是 ,出现在位置 3 和 6;规则取最小下标,即位置 3。保留的一对是 和 ,附加字符串记录两种标签都出现。重构为 。三个负点 、、 都小于 ,三个正点 、、 都大于它,所以 一致。重复的值说明为什么计数针对位置:两个 是不同的位置,只保留其中一个。
例题 4.1.6
(只有一种标签的边界情形)
设全部 个标签都是零,点为 。方案不保留任何样本,即 ,附加字符串说明出现的是全零情形。重构为常零分类器,与四个样本都一致。当 、、 时,界为 ,没有意义,因为 太小。计数仍然覆盖这种情形:实际压缩器选了 ,它属于被计数的 。
反例模式
空描述不能暗中使用样本信息
令 上的分布为均匀分布,所有真实标签为零。考虑这样一个规则:看过样本后,在每个观测过的点输出零,在每个未观测过的点输出一。它的经验误差为零,但至少有 个定义域点未被观察,故真实误差至少为 。若称其描述为“保留零个样本、零个比特”,就无效:重构需要完整的观测点列表。信息被隐藏在计数之外时,不能应用 的压缩界。
定理能说明什么,不能说明什么
定理控制一致重构假设的总体误差。它不要求目标属于有限类,也不计数所有可能分类器的基数。但它要求样本独立、重构规则固定、保留规模和附加信息有界,以及样本一致性。压缩过程可能在统计上有意义,但寻找或重构它在计算上不可行;运行时间必须另行分析。
对于有噪声或不可实现的数据,全一致的重构可能不存在。不能直接删去一致性假设并保留相同证明:未保留观测值不再全部与重构假设一致。允许训练误差的界使用不同的尾概率估计,并必须计入如何选择这些错误。
常见错误
(忘记附加比特使计数相乘)
假设分析阈值方案时当作不需要附加信息。对 、、,得到 ,比正确的 小。附加字符串在三种情形(混合、全零、全一)中作选择,并集界必须对全部 个字符串求和,这里贡献 。重构规则在保留样本之外读取的任何内容,都要计入 。
常见错误
(把保留样本当作普通训练集)
写成“用 个保留点训练,用其余 个测试”,容易让人想到普通的训练与测试划分。保留点是看过全部 个样本后才选的,所以其余 个对实际选出的子集并不是独立测试集。独立性只在固定下标集合的条件下成立,这正是证明要为每一个可能的集合付出代价的原因。
练习与解答
快速检查
(若 、,允许保留零个或一个样本,有多少种指标子集?如果还允许 个附加比特,并集界中的计数如何改变?)
分别数大小为 0 和 1 的子集,再数附加字符串。
解答 · 答案
共有 个子集。三个比特允许 个附加字符串,因此并集计数乘以八。
快速检查
(一个含两种标签且一致的阈值样本,其最大负点为 、最小正点为 。给出一个重构阈值,并解释为何没有样本点被误分类。)
用中点规则。
解答 · 答案
取 。由最大负点和最小正点的定义,所有负点不大于 ,所有正点不小于 ,故 正确标记全部样本。
快速检查
(某过程声称 、,但重构读取了整个样本。定理证明的哪一步失效?)
想一想:保留样本和比特固定后,什么被固定了。
解答 · 答案
给定零个保留样本后,分类器仍由其余全部观测值计算,因而并未固定且不独立。于是不能应用固定假设下的概率 。
快速检查
(对固定 和置信水平 ,解释为什么当 时所示界趋于零。不要求精确渐近常数。)
用 的幂界住指标集合之和。
解答 · 答案
当 时,指标集合之和至多为 ,故其对数至多按 的对数增长,而分母 线性增长。比值趋于零。