多类学习与 Natarajan 维

形式陈述

多类问题的变化

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

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

Natarajan 打散

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

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

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

h_b(x_i)=f_{b_i}(x_i),\qquad i=1,\ldots,m.

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

当 $|Y|=2$ 时，每点唯一的互异标签对就是两个二元标签，Natarajan 维退化为VC 维。这说明它是真正的多类推广，而不是参数数量或 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$ 给上界；若不说明使用的是哪一种维度，公式看似只差对数，实际证明对象已经改变。

直觉

多类打散不要求每个点都能任取全部 $k$ 个标签。它先在每个点固定一对可区分标签，再检查这些二选一是否能独立组合；这样既保留了 VC 打散的 Boolean 骨架，又允许不同位置使用不同标签对。

Graph dimension 只区分“等于基准”与“不等于基准”，把所有偏离标签合并成一类，因此通常更宽松。两种维度之间的对数差并非记号误差，而是偏离基准后是否还要固定具体标签所造成的信息差。

例子与边界

一个可见的打散例子

考虑有序输入 $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(1/\delta)}{\varepsilon^2}\right)

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

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

边界

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

本页讨论的是函数类的统计表达能力。训练多类模型的计算复杂度、标签噪声和类别不平衡不会由 $d_N(H)$ 自动解决；它们必须回到统计与计算复杂度及具体损失模型中分析。

推论与应用

当 $k=2$ 时，Natarajan 维退化为 VC 维；对有限 $k$ ，它把多类函数族的组合能力压缩成一个可进入样本复杂度的维数。可实现与不可知情形仍分别对应 $1/\varepsilon$ 与 $1/\varepsilon^2$ 的基本统计尺度，不能只保留维数项。

应用到结构化输出时，先确认“每点标签对”是否仍符合输出语义。排序、集合值标签和层次类别的损失并不只判断标签是否相等，通常需要新的打散概念；把输出空间大小代入 $\log k$ 不会自动给出正确保证。

参考资料

Balas K. Natarajan, “On Learning Sets and Functions,” Machine Learning 4, 1989.
Amit Daniely, Nati Linial, and Shai Shalev-Shwartz, “Multiclass Learnability and the ERM Principle,” COLT, 2011.
Shai Ben-David, Nicolò Cesa-Bianchi, David Haussler, and Philip M. Long, “Characterizations of Learnability for Classes of $\{0,\ldots,n\}$ -Valued Functions,” Journal of Computer and System Sciences 50(1), 1995.

形式陈述 ​

多类问题的变化 ​

Natarajan 打散 ​

与 graph dimension 的区别 ​

一个可见的打散例子 ​

学习保证 ​

边界 ​