Littlestone 维

树打散定义 ​

一棵深度 $d$ 的完全二叉实例树在每个内部节点标一个 $x\in \mathcal{X}$，两条出边标 $0$ 与 $1$；较深节点的实例可依赖此前经过的标签。若对每条根到叶标签路径 $(y_1,\dots ,y_d)$，都有某个 $h\in \mathcal{H}$ 在该路径遇到的实例上依次输出这些标签，就称树被 $\mathcal{H}$ 在线打散。最大深度是 $\mathrm{Ldim}(\mathcal{H})$。

概念图像 ​

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

与错误界的等价 ​

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

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

例子与边界 ​

有限类满足 $\mathrm{Ldim}(\mathcal{H})\le {\log }_2|\mathcal{H}|$，因为深度 $d$ 的树有 $2^d$ 条路径，每个确定性假设在树中至多实现一条路径。有限 VC 维并不保证有限 Littlestone 维；两者对应 IID 批协议与最坏序列协议。agnostic 在线学习还需 sequential Rademacher complexity 等工具，本页不把它们折叠进定义。

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

$$h_k(x)=\mathbf{1}\{x\ge k\},k\in \{1,\dots ,n+1\}.$$

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

$$\mathrm{Ldim}(\mathcal{H})=\lfloor {\log }_2(n+1)\rfloor$$

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

上述等价只针对可实现序列和确定性最坏错误数。若标签含噪，版本空间未必保留真假设；若要求随机化 learner 的期望 regret，或允许比较器也犯错，就要进入 agnostic 在线协议。计算边界也独立存在：Standard Optimal Algorithm 需要比较两个子版本空间的 Littlestone 维，信息论上最优并不保证这些维数能在多项式时间求出。

参考资料

• Nick Littlestone, Learning Quickly When Irrelevant Attributes Abound, Machine Learning, 1988.
• Noga Alon et al., Adversarial Laws of Large Numbers and Optimal Regret in Online Classification, STOC/JACM, 2021.