错误界模型

版本空间把“仍可能是真目标”的候选保留下来。Halving 并不要求每轮知道哪个候选正确；它只选择能让两种标签分支尽量平衡的预测，使每次错误都购买一次至少减半的信息进展。正因为真目标始终留在集合中，这种缩减不可能无限发生。

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

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

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

当预测来自有限专家集合且每轮能观察专家是否出错时，Weighted Majority 算法公理库Weighted Majority 算法Weighted Majority · 加权多数算法在二元在线预测中，对犯错专家乘法降权并按剩余权重多数表决。按错误乘性衰减权重，把学习器累计错误控制在最佳固定专家错误数与 $\log N$ 复杂度项之和。它实现的是专家式错误界；一般假设类仍需给出如何产生专家、如何更新版本空间或如何利用几何结构。

Halving 算法公理库Halving 算法Halving algorithm · 折半算法在有限可实现假设类中按版本空间多数预测，每次错误至少淘汰一半候选。把有限类的版本空间缩减变成 ${\log }_2|\mathcal{H}|$ 错误界，Perceptron公理库Perceptron 算法Perceptron · 感知机算法对误分类样本沿标签方向更新线性权重的基础在线分类算法。则用几何 margin 在无限线性类中得到有限错误保证；Littlestone 维公理库Littlestone 维Littlestone dimension · online mistake dimension以自适应实例树的路径打散刻画可实现在线学习的最优确定性错误数。进一步刻画一般可实现在线类的最优最坏错误数。

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