VC维

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2020年3月23日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。 此條目可能包含原创研究。 (2020年3月23日) 请协助補充参考资料、添加相关内联标签和删除原创研究内容以改善这篇条目。详细情况请参见讨论页。 此條目没有列出任何参考或来源。 (2020年3月23日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。 此條目可参照英語維基百科相應條目来扩充。 (2020年3月23日) 若您熟悉来源语言和主题，请协助参考外语维基百科扩充条目。请勿直接提交机械翻译，也不要翻译不可靠、低品质内容。依版权协议，译文需在编辑摘要注明来源，或于讨论页顶部标记{{Translated page}}标签。

瓦普尼克-契尔沃年基斯维（Vapnik-Chervonenkis Dimension），简称VC维，由弗拉基米尔·瓦普尼克与阿列克谢·契尔沃年基斯提出。在VC理论中，VC维是对一个可学习分类函数空间的能力（复杂度，表示能力等）的衡量。它定义为算法能“打散”的点集的势的最大值。 直观地，一个分类模型的能力与其复杂程度相关。例如，考虑一个高次多项式的分类模型：若函数值大于0则分类为正，反之则分类为负。高次多项式能够“摆动”的范围很大，所以能够很好地拟合给定的点集。当然因此，这样的模型也很可能会在其他符合原点集趋势的点集上分类错误。我们说这一多项式是高能力的。如果考虑一个简单的线性分类模型，就不一定能够很好地拟合给定的点集。

给定一集合族${\displaystyle H}$与一集合${\displaystyle C}$，定义其交为如下的集合族：

${\displaystyle H\cap C:=\{h\cap C\vert h\in H\}}$

称${\displaystyle H}$能打散${\displaystyle C}$，当且仅当${\displaystyle H\cap C}$包含${\displaystyle C}$的所有子集，即

${\displaystyle \vert H\cap C\vert =2^{\vert C\vert }}$

${\displaystyle H}$的VC维定义为能被${\displaystyle H}$打散的势最大的集合的势。

对一个参数记为${\displaystyle \theta }$的分类模型${\displaystyle f}$，称模型${\displaystyle f}$能够打散一点集${\displaystyle X=\{x_{1},x_{2},\cdots ,x_{n}\}}$，当且仅当对任意标签集${\displaystyle Y\in \{-1,+1\}^{n}}$都存在参数${\displaystyle \theta ^{*}}$使得${\displaystyle f_{\theta ^{*}}}$在${\displaystyle (X,Y)}$上分类完全正确。

模型${\displaystyle f}$的VC维定义为能被${\displaystyle f}$打散的势最大的点集的势，或等价地，满足存在${\displaystyle X}$，${\displaystyle \vert X\vert =D}$使得${\displaystyle f}$能打散${\displaystyle X}$的最大的${\displaystyle D}$。

• 紹爾-謝拉赫引理