用矛盾图判断分类器的复杂度，一眼看穿能否过拟合。
Contradiction Graphs Determine VC Dimension
- 构建标签序列的矛盾图，通过邻接关系反映分类冲突。
- 单个矛盾图即可判断VC维是否≥m，全序列可精确确定VC维。
- 适合研究模型泛化能力的理论工作者，尤其关注过拟合问题。
我们研究二值概念类相关的矛盾图。对于一个类 $H \subseteq \{0,1\}^X$，其阶数为 $m$ 的矛盾图 $G_m(H)$ 的顶点是长度为 $m$ 且被 $H$ 实现的带标签序列，当两个序列在某个共同域点上赋予相反标签时，它们之间存在边。我们的主要结果是，单个图 $G_m(H)$ 即可决定阈值谓词 $\mathrm{VCdim}(H)\ge m$。因此，整个序列 $(G_m(H))_{m \ge 1}$ 可以确定精确的VC维，特别是能区分有限与无限的VC维，回答了Alon等（2024）提出的问题。
原文摘要 · Abstract (English)
We study the contradiction graphs associated with binary concept classes. For a class $H \subseteq \{0,1\}^X$, the order-$m$ contradiction graph $G_m(H)$ has as vertices the $H$-realizable labeled sequences of length $m$, with two vertices adjacent when the two sequences assign opposite labels to some common domain point. Our main result is that the single graph $G_m(H)$ determines the threshold predicate $\mathrm{VCdim}(H)\ge m$. Consequently, the full sequence $(G_m(H))_{m \ge 1}$ determines the exact VC dimension and, in particular, detects finite versus infinite VC dimension, answering a question posed by Alon et al. (2024).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。