错误界模型

版本空间把“仍可能是真目标”的候选保留下来。Halving 并不要求每轮知道哪个候选正确；它预测候选中票数较多的标签；分支有多平衡由输入决定，算法不能自行改变。若预测错误，被删除的恰是占多数的一支，因此每次错误都带来至少减半的信息进展。正因为真目标始终留在集合中，这种缩减不可能无限发生。

这个证明还显示无限类不能直接用基数对数。无限类是否有有限最坏错误界由 Littlestone 维控制；VC 维只刻画 IID 批学习，二者可能不同。

量词要求同一个算法对每个 $T$、每条可实现的长度 $T$ 序列都满足同一上界，不能看完序列再另选算法。实轴阈值 $h_a(x)=\mathbf{1}\{x\ge a\}$ 提供一个反例：对手维护包含可能阈值的开区间，每轮选其中点，并给出与学习器预测相反的标签。根据标签保留左半或右半区间，任意有限轮后仍存在一致阈值，却可让确定性学习器轮轮出错。这个 VC 维为 $1$ 的类没有有限的确定性最坏错误界，具体说明了批学习与在线学习的区别。

若序列含噪，不存在零错误比较器，绝对错误界通常不再有限；应改用相对最好假设的 regret 或 agnostic mistake bound。预测后才揭示标签也是本质条件，不能把事后重放当在线保证。

以四个候选假设开始，第一次按多数预测却犯错后，至少两个候选与新标签矛盾，版本空间至多剩两个；第二次犯错后至多剩一个。只要序列可实现，真目标从不会被删掉，因此算法最多犯 ${\log }_{2}4=2$ 次。这一保证与轮数无关，却依赖每次能准确维护全部一致候选。

当预测来自有限专家集合且每轮能观察专家是否出错时，Weighted Majority 算法理路Weighted Majority 算法Weighted Majority · 加权多数算法在二元在线预测中，对犯错专家乘法降权并按剩余权重多数表决。按错误乘性衰减权重，把学习器累计错误控制在最佳固定专家错误数与 $\log N$ 复杂度项之和。当有限假设类的每个 $h$ 各作为一个固定专家、序列又由其中某个专家完全实现时，最佳专家错误数为零，便得到只依赖专家数的绝对错误界；一般有损专家序列则只有相对错误界。一般假设类仍需给出如何产生专家、如何更新版本空间或如何利用几何结构。

Halving 算法理路Halving 算法Halving algorithm · 折半算法在有限可实现假设类中按版本空间多数预测，每次错误至少淘汰一半候选。把有限类的版本空间缩减变成 ${\log }_2|\mathcal{H}|$ 错误界，Perceptron理路Perceptron 算法Perceptron · 感知机算法对误分类或零间隔样本沿标签方向更新线性权重的基础在线分类算法。则在 $\Vert x_t\Vert \le R$ 且存在单位分隔方向、正间隔 $\gamma$ 的线性序列上给出至多 $(R/\gamma {)}^2$ 次更新，实际预测错误数不超过更新数；使用它的 $\{-1,+1\}$ 标签时，先把本页标签改记为 $2y_t-1$。Littlestone 维理路Littlestone 维Littlestone dimension · online mistake dimension以自适应实例树的路径打散刻画可实现在线学习的最优确定性错误数。进一步刻画一般可实现在线类的最优最坏错误数。

错误界与 PAC 样本界可以使用同一个类，却量化不同序列。PAC 对 IID 抽样给概率保证；mistake bound 要对对手挑选的任意可实现次序成立。有限 VC 维也不自动给有限在线错误界，不能在两种协议之间只替换复杂度符号。