Littlestone 维

VC 维让对手先摆好一组点，再问能否实现所有静态标注；Littlestone 维允许对手看见过去标签后选择下一个点。对象因此不是普通点集，而是把所有可能历史同时编码的决策树。节点实例依路径变化，正是在线自适应性的来源。

与错误界的等价 ​

若存在深度 $d$ 的打散树，对手每轮把当前节点实例交给学习器，并沿与学习器预测相反的边给出真标签。无论学习器怎样预测，它连续 $d$ 轮犯错，且打散性质保证整条路径仍由某个 $h$ 实现。因此任何确定性 learner 的最坏错误数至少为 $d$。

当 $\mathrm{Ldim}(\mathcal{H})<\mathrm{\infty }$ 时，反方向可用 Standard Optimal Algorithm：在收到 $x$ 后，比较版本空间两个标签子类的 Littlestone 维，预测维数较大的那一侧。若预测错误，保留下来的另一侧维数必严格下降，否则把两棵同深打散子树接到根 $x$ 会构造更深树。于是错误数至多 $\mathrm{Ldim}(\mathcal{H})$。两边合并说明可实现在线最优确定性 mistake bound 恰等于该维数。

有限类满足 $\mathrm{Ldim}(\mathcal{H})\le {\log }_2|\mathcal{H}|$，因为深度 $d$ 的树有 $2^d$ 条路径，每个确定性假设在树中至多实现一条路径。

一个能看见树自适应性的例子是有限有序域 $\{1,\dots ,n\}$（$n\ge 1$） 上的阈值类

对手在根节点询问中位点；标签 $0$ 把可行阈值留在中位点右侧，标签 $1$ 则留在左侧。此后在剩余区间继续询问中位点，正好形成二分搜索树。因此

（非满二叉树时按可嵌入的最大完全深度理解），同时这族非退化阈值的 VC 维只有 $1$。在稠密无限序域上，二分过程可延续任意有限深度，Littlestone 维因而为无穷；这给出“有限 VC 不推出有限在线维”的具体见证。

计算边界也独立存在：Standard Optimal Algorithm 需要比较两个子版本空间的 Littlestone 维，信息论上最优并不保证这些维数能在多项式时间求出。

有限类的 ${\log }_2|\mathcal{H}|$ Halving 界由 Littlestone 维统一推广；Standard Optimal Algorithm 则达到该维数给出的信息论最优错误数。

上述错误数等价针对可实现序列和确定性学习器。若标签含噪，版本空间未必保留真假设；在非预见对手下允许随机预测、以期望 regret 评价的不可知在线二分类中，有限 Littlestone 维仍刻画能否取得统一次线性上界。这个结论需另行处理有损比较器与随机化，可用序贯复杂度等工具分析，不能直接照搬版本空间缩减证明。