多类学习与 Natarajan 维

问题从哪里改变 ​

二分类中，每个样本点只有两种标签，因而“能否实现该点集上的所有二元标记”自然导向 VC 维。多类分类把标签集改为 $Y$，其中 $|Y|=k\ge 3$。此时一个函数族即使不能在每个点上实现全部 $k$ 个标签，也可能在大量点上稳定地作出两两不同的选择；直接照搬二元打散定义会把这种真实的表达能力漏掉。

设 $H\subseteq Y^X$。Natarajan 维抓住的不是“每点任意选一个标签”，而是先为每个点指定一对互异候选，再问 $H$ 能否独立实现每一组二选一。这正好保留 VC 打散的二元组合骨架，同时允许不同样本点使用不同的标签对。

Natarajan 打散 ​

有限集合 $S=\{x_1,\dots ,x_m\}\subseteq X$ 被 $H$ Natarajan 打散，若存在两个函数

$$f_0,f_1:S\to Y,f_0(x)\ne f_1(x)(x\in S),$$

使得对每个二进制向量 $b\in \{0,1{\}}^m$，都有某个 $h_b\in H$ 满足

$$h_b(x_i)=f_{b_i}(x_i),i=1,\dots ,m.$$

Natarajan 维 $d_N(H)$ 是可被如此打散的最大集合大小；若任意有限大小都能打散，则记为无穷。标签对可以随 $x_i$ 改变，但在枚举 $2^m$ 种选择之前必须固定，不能为每个 $b$ 临时换一对标签。

当 $|Y|=2$ 时，每点唯一的互异标签对就是两个二元标签，Natarajan 维退化为VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。。这说明它是真正的多类推广，而不是参数数量或 one-vs-rest 分类器个数的别名。

与 graph dimension 的区别 ​

另一种常见尺度是 graph dimension。集合 $S$ 被 graph-shattered，若存在基准标记 $f:S\to Y$，使得对每个子集 $T\subseteq S$，某个 $h\in H$ 在 $T$ 上等于 $f$，在 $S\setminus T$ 上处处不等于 $f$。它只要求“偏离基准”，没有固定偏离后采用哪个标签，因此一般比 Natarajan 打散更宽松：

$$d_N(H)\le d_G(H).$$

对有限标签集，两者至多相差与 $\log k$ 有关的因子。样本复杂度定理有时以 $d_N$ 给下界、以 $d_G$ 给上界；若不说明使用的是哪一种维度，公式看似只差对数，实际证明对象已经改变。

一个可见的打散例子 ​

考虑有序输入 $X=\mathbb{R}$、标签 $Y=\{A,B,C\}$，假设类由“两段常值规则”组成：选择阈值 $t$ 及左右两个不同标签，令 $x<t$ 输出左标签、$x\ge t$ 输出右标签。两个有序点 $x_1<x_2$ 可被 Natarajan 打散：在两点都固定候选对 $A/B$，把阈值放在样本区间外可实现 $AA,BB$，放在两点之间并交换左右标签可实现 $AB,BA$。但任取三个点及每点的两个互异候选，总能从首、尾候选中各选一个不同于所选中点标签的值，形成相邻位置都改变标签的模式；两段常值规则至多改变一次，无法实现它。因此这个类的 Natarajan 维恰为 $2$。标签多并不自动带来高维，函数族允许标签怎样随输入变化才是关键。

相反，若 $X$ 含 $d$ 个指定点，而 $H$ 包含这些点上所有取值于 $\{A,B\}$ 的函数，那么即使全局标签集还有许多其他类别，也已有 $d_N(H)\ge d$。额外标签只有在假设类确实能使用它们形成新的限制模式时才影响复杂度。

学习保证 ​

对有限标签集、0–1 损失和 IID 样本，有限 Natarajan 维是分布无关多类可学性的核心组合条件。典型不可知 PAC 上界具有

$$m=O\left(\frac{d_N(H)\log k+\log \left(1/\delta \right)}{{\epsilon }^2}\right)$$

的形状；不同定理会改用 graph dimension，或在 $d_N$ 与 $k$ 的对数项上给出更精细常数。可实现情形通常把主要的 $1/{\epsilon }^2$ 改善为 $1/\epsilon$，但仍必须交代学习器是否 proper，以及输出类是否扩大。

这里的 $\log k$ 不是把 $k$ 个 one-vs-rest 问题作并集界后必然得到的答案。one-vs-rest 会改变可表示的决策规则、冲突消解方式和统计依赖；它是一种算法构造，不是多类维数的定义。

边界 ​

若标签集无限，单靠 Natarajan 维可能不足以给出想要的统一结论，还需控制标签增长或改用适合具体输出结构的复杂度。层次标签、集合值输出和排序也不是把 $k$ 换成更大的数即可处理，它们各自有不同的损失与打散概念。

本页讨论的是函数类的统计表达能力。训练多类模型的计算复杂度、标签噪声和类别不平衡不会由 $d_N(H)$ 自动解决；它们必须回到统计与计算复杂度公理库学习的统计复杂度与计算复杂度Statistical-computational complexity of learning分开衡量数据量、求解代价和输出表示，避免把统计可学误读为计算可解。及具体损失模型中分析。

参考资料

• Balas K. Natarajan, “On Learning Sets and Functions,” Machine Learning, 1989.
• Amit Daniely, Nati Linial, and Shai Shalev-Shwartz, “Multiclass Learnability and the ERM Principle,” COLT, 2011.
• Shai Ben-David et al., “A Theory of Learning from Different Domains,” related multiclass dimension preliminaries.