错误界模型

协议与保证 ​

每轮先见 $x_t$，学习器提交 ${\hat{y}}_t$，随后才见真标签 $y_t$。序列对类 $\mathcal{H}$ 可实现，若存在一个固定 $h^{\ast }\in \mathcal{H}$ 对所有轮满足 $h^{\ast }(x_t)=y_t$。算法的 mistake bound $M(\mathcal{H})$ 要对任意长度、任意次序的可实现序列保证

$$\sum _t\mathbf{1}\{{\hat{y}}_t\ne y_t\}\le M(\mathcal{H}).$$

有限类的 Halving 算法维护与历史一致的版本空间，每次按版本空间多数预测。每次犯错至少淘汰一半候选，所以错误数至多 $\lfloor {\log }_2|\mathcal{H}|\rfloor$。这个证明不需要例子顺序随机，环境甚至可根据历史挑下一个 $x_t$。

版本空间在第 $t$ 轮前是

$$V_t=\{h\in \mathcal{H}:\mathrm{\forall }s<t,h(x_s)=y_s\}.$$

可实现性保证 $h^{\ast }\in V_t$，所以它永不为空。多数预测犯错时，与预测相同的至少一半候选被新标签排除，故 $|V_{t+1}|\le |V_t|/2$；连续犯 $M$ 次错后仍有 $1\le |V_{T+1}|\le |\mathcal{H}|/2^M$，整理即得界。

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

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

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

错误界与 PAC 样本界使用同一个类却量化不同序列。PAC 对 IID 抽样的概率保证；mistake bound 要对对手挑选的任意可实现次序成立。有限 VC 维也不自动给有限在线错误界，在线对应的组合尺度是 Littlestone 维。

参考资料

• Nick Littlestone, “Learning Quickly When Irrelevant Attributes Abound,” 1988.
• Littlestone, Warmuth, 1994.