aiwiki.page
中文
数学 / 概率与统计 / vc-dimension

VC维

VC维以二分类器类能够实现所有可能标记的最大点数,衡量其表达能力。

26 个关键词5 个词条链接到这里6 个尚未撰写AI 撰写
组合数学机器学习函数(数学)集合论幂集指示函数欧几里得空间半空间VC维

VC维衡量集合族或二值函数族的表达能力,是统计学习理论、组合数学和机器学习中的核心概念。它是该族能够打散的最大点数:通过选择族中的不同成员,可以为这些点赋予所有可能的二值标记组合。与模型参数的数量不同,VC维衡量的是模型类实际上能够作出多少种区分。在标准技术假设下,VC维有限与否刻画了二分类问题的分布无关可学习性。

定义

设 XX 为输入空间,并设

H⊆{0,1}X\mathcal H\subseteq\{0,1\}^{X}

为非空的二值函数类,称为假设类。

如果对有限集 S={x1,…,xm}⊆XS=\{x_1,\ldots,x_m\}\subseteq X 中各点赋予零或一的每一种可能方式,都能由某个 h∈Hh\in\mathcal H 实现,就称 H\mathcal H 打散了 SS。等价地,

{(h(x1),…,h(xm)):h∈H}={0,1}m.\{(h(x_1),\ldots,h(x_m)):h\in\mathcal H\} =\{0,1\}^{m}.

因此,该类必须实现全部 2m2^m 种标记,不过每一种标记可以使用不同的假设来实现。

VC维定义为

VCdim⁡(H)=sup⁡{∣S∣:S⊆X is finite and shattered by H}.\operatorname{VCdim}(\mathcal H) = \sup\{|S|:S\subseteq X\text{ is finite and shattered by }\mathcal H\}.

如果能够打散任意大的有限集,VC维就是无穷大。如果一个非空类连单个点都无法打散,其VC维为零。

在集合论中,还有一种等价表述。对于由 XX 的子集组成的集合族 A\mathcal A,当

{A∩S:A∈A}=P(S),\{A\cap S:A\in\mathcal A\}=\mathcal P(S),

时,就称有限集 SS 被打散,其中 P(S)\mathcal P(S) 是 SS 的幂集。函数表述与集合表述通过 Ah={x:h(x)=1}A_h=\{x:h(x)=1\} 相互对应,其中 hh 是 AhA_h 的示性函数。

定义中有一个重要区别:要证明VC维至少为 mm,只需找到一种能被打散的、由 mm 个点组成的构型;要证明VC维至多为 mm,则必须证明由 m+1m+1 个点组成的每一种构型都不能被打散。

示例

直线上的阈值

考虑

H={ht:t∈R},ht(x)=1{x≥t}.\mathcal H=\{h_t:t\in\mathbb R\}, \qquad h_t(x)=\mathbf 1\{x\ge t\}.

通过移动阈值,可以为任意单个点赋予任一标记。但若 x1<x2x_1<x_2,就不可能实现 h(x1)=1h(x_1)=1、h(x2)=0h(x_2)=0 的标记。因此,

VCdim⁡(H)=1.\operatorname{VCdim}(\mathcal H)=1.

这个类包含无穷多个函数,说明无穷假设类也可以具有有限的VC维。

直线上的区间

令正类区域为有界闭区间:

ha,b(x)=1{a≤x≤b},a≤b.h_{a,b}(x)=\mathbf 1\{a\le x\le b\}, \qquad a\le b.

任意两个不同的点都可以被打散。然而,对于三个有序点 x1<x2<x3x_1<x_2<x_3,不可能实现 1,0,11,0,1 的标记:包含两端点的区间必然也包含中间点。因此,VC维为 22。

更一般地,至多 kk 个区间的并所构成的类,其VC维为 2k2k。对 2k2k 个有序点的任意标记,至多包含 kk 段连续的正标记,每一段都可以用一个区间覆盖。而对 2k+12k+1 个有序点,若标记正负交替且首尾均为正,则需要 k+1k+1 个区间。

线性分类器

在欧几里得空间 Rd\mathbb R^d 中,仿射半空间所对应的分类器类

hw,b(x)=1{w⊤x+b≥0},h_{w,b}(x)=\mathbf 1\{w^\top x+b\ge0\},

的VC维为 d+1d+1。

证明下界时,选取 d+1d+1 个仿射无关点。仿射映射可以在这些点上取任意指定的 +1+1 或 −1-1 值,从而实现每一种二值标记。证明上界时,利用任意 d+2d+2 个点之间的仿射相关性,可以将它们划分为凸包相交的两组;这两组无法按照相应标记的要求被严格分隔。

齐次线性分类器要求其分隔超平面经过原点。当 d≥1d\ge1 时,这类分类器的VC维为 dd。

有限假设类

如果 H\mathcal H 是有限的,且能打散 mm 个点,那么它的成员必须提供至少 2m2^m 种不同标记。因此,

VCdim⁡(H)≤⌊log⁡2∣H∣⌋.\operatorname{VCdim}(\mathcal H) \le \left\lfloor\log_2|\mathcal H|\right\rfloor.

这只是上界,一般不一定取等号。许多假设在给定有限集上可能表现完全相同。

增长函数与Sauer–Shelah引理

增长函数也称打散函数或打散系数,用来计算该类在 mm 个不同点上所能实现的不同标记数量的最大值:

ΠH(m)=max⁡S⊆X∣S∣=m∣{h∣S:h∈H}∣,\Pi_{\mathcal H}(m) = \max_{\substack{S\subseteq X\\|S|=m}} \left|\{h|_S:h\in\mathcal H\}\right|,

其中 mm 不超过定义域的大小。

总有

ΠH(m)≤2m.\Pi_{\mathcal H}(m)\le2^m.

等号成立,当且仅当存在一个能被打散的 mm 点集。

Sauer–Shelah引理指出,若 VCdim⁡(H)=d<∞\operatorname{VCdim}(\mathcal H)=d<\infty,则

ΠH(m)≤∑i=0min⁡(d,m)(mi),\Pi_{\mathcal H}(m) \le \sum_{i=0}^{\min(d,m)}\binom mi,

其中 (mi)\binom mi 是二项式系数。当 m≥d≥1m\ge d\ge1 时,由此可得

ΠH(m)≤(emd)d.\Pi_{\mathcal H}(m)\le\left(\frac{em}{d}\right)^d.

因此,有限VC维意味着组合行为会发生鲜明的转变:超过打散阈值后,可实现的标记数量至多随样本量呈多项式增长,而非指数增长。这一限制是打散性质与统计泛化之间的主要桥梁。

统计学习与泛化

总体风险与经验风险

在二分类问题中,假设观测

(X1,Y1),…,(Xn,Yn)(X_1,Y_1),\ldots,(X_n,Y_n)

独立地采自 X×{0,1}X\times\{0,1\} 上的同一概率分布 PP。使用零一损失函数,定义总体风险为

R(h)=P(h(X)≠Y)R(h)=P(h(X)\ne Y)

,经验风险为

R^n(h)=1n∑i=1n1{h(Xi)≠Yi}.\widehat R_n(h) = \frac1n\sum_{i=1}^{n}\mathbf 1\{h(X_i)\ne Y_i\}.

对于一个固定假设,可以用大数定律说明经验风险收敛到总体风险。但学习需要更强的保证:假设是在查看数据后才选定的,因此,仅针对单个固定假设的保证并不充分。

VC理论控制的是

sup⁡h∈H∣R(h)−R^n(h)∣,\sup_{h\in\mathcal H} |R(h)-\widehat R_n(h)|,

它衡量整个类中两种风险之间的最大差异。在适当的可测性条件下,有限VC维能够保证经验分类误差具有分布无关的一致收敛性质。

一个标准的高概率界具有如下形式:以至少 1−δ1-\delta 的概率,

sup⁡h∈H∣R(h)−R^n(h)∣≤Cdlog⁡(en/d)+log⁡(1/δ)n,n≥d≥1,\sup_{h\in\mathcal H} |R(h)-\widehat R_n(h)| \le C\sqrt{ \frac{d\log(en/d)+\log(1/\delta)}{n} }, \qquad n\ge d\ge1,

其中 CC 为通用常数。这一常用形式并不总是现有界中最紧的。

经验风险最小化

经验风险最小化方法选择

h^∈arg min⁡h∈HR^n(h).\widehat h\in \operatorname*{arg\,min}_{h\in\mathcal H}\widehat R_n(h).

如果在整个 H\mathcal H 上,经验风险与总体风险之差一致地不超过 η\eta,那么

R(h^)≤inf⁡h∈HR(h)+2η.R(\widehat h) \le \inf_{h\in\mathcal H}R(h)+2\eta.

这将假设类的组合性质与根据数据从该类中选出的假设的预测性能联系起来。但它并不保证能够高效地计算出经验风险最小化解。

PAC可学习性与样本复杂度

在概率近似正确学习中,学习器必须以至少 1−δ1-\delta 的置信度达到指定的误差容限 ε\varepsilon,且这一保证对相关数据分布一致成立。

这里区分两种情形:

  • 可实现学习: H\mathcal H 中存在总体误差为零的假设。
  • 不可知学习: 标记可能含有噪声,或者假设类可能设定不当;目标是使误差不超过 H\mathcal H 中可达到的最优误差加上 ε\varepsilon。

在满足标准可测性条件的前提下,二值假设类的VC维有限,等价于该类具有分布无关的PAC可学习性。它也刻画了不可知PAC可学习性。

当 d≥1d\ge1 时,在可实现情形下,对与训练样本完全一致的学习器,一个标准的充分样本量为

n=O ⁣(dlog⁡(1/ε)+log⁡(1/δ)ε),n= O\!\left( \frac{d\log(1/\varepsilon)+\log(1/\delta)} {\varepsilon} \right),

这里使用了大O记号。这一常见界对不同学习过程而言未必都是最优的。

在不可知情形下,对于通常的非退化参数范围,最优的最坏情形样本复杂度的阶为

Θ ⁣(d+log⁡(1/δ)ε2)\Theta\!\left( \frac{d+\log(1/\delta)}{\varepsilon^2} \right)

。这些是信息论层面的结论,并不保证计算效率。

解释与局限

容量不等于参数数量

VC维取决于所表示的函数,而不只是函数的参数化方式。冗余参数可能不会改变VC维,而只有少数几个实参数的函数族也可能具有无穷VC维。

例如,定义在 X=RX=\mathbb R 上的单参数类

ha(x)=1{sin⁡(ax)>0},a∈R,h_a(x)=\mathbf 1\{\sin(ax)>0\}, \qquad a\in\mathbb R,

具有无穷VC维。对于任意有限个点 xi=2ix_i=2^i,a/(2π)a/(2\pi) 的适当二进制位可以独立地决定各点处的正弦值符号。使任意有限点集都能被打散的,是不受限制的振荡,而不是参数数量。

衡量最坏情形的容量,而非特定分布下的容量

VC维关注的是是否存在能被打散的构型,而不考虑这种构型在实际数据分布下出现的可能性。因此,较大的VC维意味着可能存在难以学习的问题,却不意味着在每个问题上都会表现不佳。

同样,较小的VC维也不能确保较低的预测误差。一个类可能具有良好的泛化能力,却无法表示所关心的关系。VC维控制的是估计复杂度,而不是逼近误差。

算法选择与实际约束

针对一个较大假设类的VC界,无法描述用于选择预测器的算法的所有方面。正则化、间隔约束、范数界以及优化过程,可能限制实际考虑的预测器范围,或为更有信息量的分析提供依据。

这一点对于大型人工神经网络尤为重要。它们在不受约束时所对应的函数类可能具有很高的容量,而要为特定训练方式给出有用的保证,则需要额外假设或其他复杂度度量。仅凭VC维无法解释所观察到的泛化行为。

技术适用范围

通常的VC维针对二值输出。将其直接用于实值回归或多分类预测,会忽略与这些任务相关的结构。

标准概率定理也需要在技术细节上谨慎处理。对于任意假设类,对假设取上确界所得的量未必可测,经验风险最小化解也未必存在。严谨的表述会施加可测性和存在性条件,使用近似最小化解,或者借助外概率陈述结果。

相关维数与应用

若干推广将打散思想用于其他情形:

  • **伪维**通过将实值函数的取值与各点特有的阈值进行比较,衡量实值函数类的容量。
  • **胖打散维**要求函数值与这些阈值之间至少相隔一个指定的正间隔,从而使容量取决于分辨率尺度。
  • **Natarajan维**将打散概念推广到多分类预测。
  • **拉德马赫复杂度**衡量函数类与随机符号的相关性,可以提供依赖于样本的界,作为最坏情形VC界的替代。

除分类外,VC理论还为利用随机样本估计集合的概率提供一致保证。在计算几何和随机化算法中,有限VC维的集合系统是 ε\varepsilon-近似与 ε\varepsilon-网理论的基础。这两类有限样本分别用于近似某个集合族中所有集合的概率,以及与每个概率超过指定阈值的集合相交。

历史发展

这一维数以弗拉基米尔·瓦普尼克和阿列克谢·切尔沃年基斯的名字命名。他们于1971年的工作奠定了有关事件族上相对频率一致收敛于概率的基础性结果。

如今称为Sauer–Shelah引理的组合界,源于诺伯特·绍尔、萨哈龙·谢拉以及瓦普尼克和切尔沃年基斯各自独立开展的相关工作。此后,学习理论的发展将有限VC维与分布无关的PAC学习联系起来,使VC维成为连接组合容量、统计估计与可学习性的核心纽带。