在线分类器逐个观察样本,并在收到标签之前预测。批量预测器则需要在训练后面对新样本。当样本独立地来自同一固定分布时,每次在线预测面对的样本,相对于过去而言都是新抽取的。这使我们可以把在线表现转化为总体风险陈述。具体输出和概率的来源都很重要:对已保存预测器的平均风险作保证,并不自动保证其中每一个预测器的风险。
在线序列与批量混合规则
设 Z1,…,ZT 独立同分布于 P,其中 T≥1。在看到 Zt 之前,确定性在线规则只根据 Z1,…,Zt−1 选择可测预测器 ht;所有平局规则预先固定。将预测器表示在可测空间中,令联合可测损失 ℓ(h,z) 取值于 [0,1],定义
L(h)=EZ∼Pℓ(h,Z),mt=ℓ(ht,Zt),L=T1t=1∑TL(ht).
假设预测器的选择及其风险可测。已保存预测器构成随机批量规则,定义如下。
由 h1,…,hT 构成的混合规则按以下方式回答每次未来预测:独立于训练样本从 P 抽取一个新测试样本,并独立于训练和测试样本从 {1,…,T} 中均匀重新选取 J,再使用 hJ。给定训练样本后,包括随机选择 J 在内的期望测试损失为
EJ,Zℓ(hJ,Z)=T1t=1∑TL(ht)=L.
这是 Gibbs 混合规则,不一定是单个确定性分类器。以下除 log2 外,对数均为自然对数。
一般有界损失的置信界
对任意 0<δ<1,以关于 Z1,…,ZT 的至少 1−δ 的概率,
L≤T1t=1∑Tmt+2Tlog(1/δ).这里不需要可实现性假设。概率针对训练样本;随机下标已在 L 内取平均。
令 Ft=σ(Z1,…,Zt),并令 F0 为平凡信息。由于 ht 是 Ft−1-可测的,而 Zt 独立于 Ft−1 且服从 P,由联合可测性和 Fubini 定理得到的条件期望固定变量引理给出
E[mt∣Ft−1]=L(ht).令 Dt=L(ht)−mt。给定历史后它的均值为零,且处于长度为一的区间。对条件分布应用 Hoeffding 引理,对 s>0 得到 E[esDt∣Ft−1]≤es2/8。反复取条件期望得到
Eexp(st=1∑TDt)≤eTs2/8.Markov 不等式给出 Pr(t∑Dt≥Tε)≤exp(−sTε+Ts2/8)。选 s=4ε 得到 e−2Tε2;令其等于 δ。所得事件蕴含所给的界。
证明透视
相对于预测器是新样本
论证并不把 ht 当作独立于整个训练集的对象:后续样本可能影响后续预测器。我们只使用 Zt 抽取时 ht 已由过去确定这一事实。如果预测器可以在预测前查看 Zt,条件期望恒等式就可能失效。
对错误次数更快的界
对二元分类使用零一损失,令 M=t∑mt。下一个论证利用给定历史后的错误指标服从 Bernoulli 分布。当 M 很小时,它可能更紧。
对任意预先固定的 b>0 和 0<δ<1,以关于训练样本的至少 1−δ 的概率,
L≤T(1−e−b)bM+log(1/δ).参数 b 在看到样本前选择;根据数据选取它需要额外的同时控制。该界针对混合规则的风险,在独立同分布假设下适用于任何可测的确定性在线规则。
给定 Ft−1,令 pt=L(ht),It=mt∈{0,1}。独立性给出 E[It∣Ft−1]=pt。令 a=1−e−b,则
E[eapt−bIt∣Ft−1]=eapt(1−apt)≤1,其中用到 1−u≤e−u。反复取条件期望得 Eexp(at∑pt−bM)≤1。由 Markov 不等式,
Pr(at∑pt−bM≥log(1/δ))≤δ.在其补事件上整理即得结论。
若有限类 H 有 N 个成员,且存在一个固定的 h∗∈H 满足 P(h∗(X)=Y)=0,则固定目标在一个概率为一的事件上正确标记全部 T 个样本,因此不会被淘汰。采用固定平局规则的可测折半算法在该事件上至多犯 k=⌊log2N⌋ 次错误。取 b=log2,以至少 1−δ 的概率有
L≤T2(klog2+log(1/δ)).
这里用固定目标和独立同分布可实现性,保证在线错误界几乎必然成立。T 较小时右边可能超过 1;风险始终不超过 1,因此可把界截断为 1。
当 N=8、T=300、δ=0.05 时,k=⌊log28⌋=3。快速率界为 2(3log2+log20)/300=2(2.0794+2.9957)/300≈0.0338;一般有界损失界至多为 3/300+log20/600=0.01+0.0707≈0.0807。二者分别在其置信事件上约束同一个条件混合风险;二者都没有说每个单独保存的分类器具有该风险。
取 T=100、δ=0.05、M=0。取 b=log2,快速率界为 2log20/100≈0.0599,而一般界为 0+log20/200≈0.1224。当 M=0 时,快速率界仍按 1/T 衰减,而一般界的衰减不可能快于 1/T;这正是额外的 Bernoulli 结构发挥作用的情形。
取 N=8、k=3、T=10、δ=0.05。快速率的表达式为 2(2.0794+2.9957)/10≈1.015,超过 1;风险始终不超过 1,所以界被截断为 1,没有提供任何信息。至多三次错误时的一般界仍给出 0.3+log20/20≈0.3+0.387=0.687。两个界并无一致的优劣:T 大而 M 小时快速率较好,T 非常小时平方根界可能较好。
快速率界是对在抽样之前固定的 b 证明的。取使右边对观察到的 M 最小的 b,并不在该定理涵盖之内,因为指数矩论证只对每个固定的 b 分别控制 Eexp(at∑pt−bM)。依赖数据的选取需要同时控制,例如对有限的取值网格用并集界,并把 δ 分给网格中的各个值。
指标 mt 是不同预测器 ht 的损失,每个都只在它尚未见过的那一个样本上度量。它们的和 M 不是任何单个分类器的训练误差,上述界也不适用于看完最后一个样本后再选取的预测器 hT+1;它们适用的是已保存预测器 h1,…,hT 的平均风险 L。
如果只抽取一次下标会怎样?
反例模式
平均值可以掩盖差的已保存预测器
假设分布的标签始终为 0,在线规则先保存一个始终预测 1 的分类器,然后保存九个始终预测 0 的分类器。这十个风险为 1,0,…,0,所以 L=0.1。如果均匀抽取一次下标 J,然后将它固定为部署的分类器,则它的总体风险以概率 0.1 为 1,否则为 0。单凭 L 的界,不能保证所选单个 hJ 的风险必然不超过 0.1。
每次预测都重新独立抽取下标实现的是混合损失。只抽一次则得到随机分类器;给定样本后对 J 取期望,其风险仍等于同一平均值,但实际选中分类器的风险可能变化。例如,对任一给定训练样本,Markov 不等式给出 PrJ(L(hJ)>L/η)≤η,其中 0<η<1。与概率至少 1−δ 的样本事件结合,总失败概率至多为 δ+η。另行验证或选择也是一种方法。
练习与解答
快速检查
(一个在线二元学习器在 T=200 个独立同分布轮次中几乎必然至多犯两次错。取 b=log2,给出 δ=0.1 时混合风险的快速率界。)
代入 M≤2、b=log2 及 1−e−b=1/2。
解答 · 答案
以至少 0.9 的概率,L≤2(2log2+log10)/200=2(1.3863+2.3026)/200≈0.0369。
快速检查
(若所有保存的分类器总体风险都为 0.2,混合风险是多少?任取其中一个分类器的风险是多少?)
解答 · 答案
二者都是 0.2:混合风险是 T 个相等数值的平均,而每个单独分类器的风险按假设都是 0.2。只有保存的风险互不相同时,这两个概念才会有差别。
快速检查
(如果允许 ht 在预测前读取当前标签,为什么一般证明会失效?)
解答 · 答案
此时给定过去后,当前样本与选中的预测器不再独立,因而 E[mt∣Ft−1]=L(ht) 未必成立,Dt 的条件均值也未必为零。
快速检查
(在十个分类器的反例中,PrJ(L(hJ)>0.1) 是多少?)
数一数风险大于 0.1 的已保存分类器有几个。
解答 · 答案
为 1/10:恰好一个已保存分类器的风险为 1>0.1,其余九个风险为 0。虽然 L 恰为 0.1,这个事件的概率仍是 0.1。