PAC可学性与假设空间$\mathcal{H}$复杂度密切相关。假设空间$\mathcal{H}$越复杂，寻找到目标概念的难度越大。对于有限假设空间，可以用其中包含假设的数据来刻画假设空间的复杂度。 然而对于大多数学习问题来说， 学习算法考虑的假设空间并非是有限的，因而无法使用假设的数量来刻画假设空间复杂度。 有以下两种方法可以刻画无限假设空间的复杂度:

• 与数据分布$\mathcal{D}$无关的VC维及其扩展 Natatajan维
• 与数据分布$\mathcal{D}$相关的Rademacher维

VC维

一般的学习任务中通常都是无限假设空间，例如$R^d$空间中所有的线性超平面。为了对这些无限假设空间进行研究，通常考虑其VC维。在介绍VC维之前，需要先知道的概念有：增长函数（growth function）、对分（dichotomy）、打散（shattering）和断点（break point）

令$\mathcal{H}$表示假设空间，其中每一个假设是$\mathcal{X}$到Y={−1,+1}\mathcal{Y}=\{-1, +1\}Y={−1,+1}的映射，对于数据集D={x1,...,xm}D=\{x_1,...,x_m\}D={x1​,...,xm​}, $\mathcal{H}$在数据集$D$上的限制是从$D$到 {−1+1}m\{-1+1\}^m{−1+1}m的一族映射：
H∣D={h(x1),...,h(xm)∣h∈H}\mathcal{H}_{|D} = \{h(x_1),...,h(x_m) | h \in \mathcal{H}\}H∣D​={h(x1​),...,h(xm​)∣h∈H}

增长函数： 增长函数表示假设空间H对m个示例所能赋予标记的最大可能结果数。可以表示为：
∏H(m)=maxx1,...,xm∣{h(x1),...,h(xm)∣h∈H}}∣\prod_{\mathcal{H}}(m) = \underset{x_1,...,x_m}{max}|\{ h(x_1),...,h(x_m) | h \in \mathcal{H}\}\}|H∏​(m)=x1​,...,xm​max​∣{h(x1​),...,h(xm​)∣h∈H}}∣
对于大小为$m$的数据集，有：

$$\prod _{\mathcal{H}}(m)=\underset{|D|=m}{\max }|{\mathcal{H}}_{|D}|$$

$\mathcal{H}$对样本所能赋予的标记可能结果输越大，$\mathcal{H}$的表示能力越强。增长函数在一定程度上描述了假设空间$\mathcal{H}$的适应能力，反映了假设空间的复杂度。尽管$\mathcal{H}$可能包包含无穷个假设空间，但${\mathcal{H}}_{|D}$是有限的，即$\mathcal{H}$对所有样本赋予标记可能的结果是有限的，例如对于二分类问题，对$m$个样本最多有$2^m$个可能的结果

对分: 对于二分类问题来说，$\mathcal{H}$的假设对$D$中$m$个示例赋予标记的每种可能结果称为对D的一种对分（dichotomy）。对分也是增长函数的一种上限。

打散：假设空间$\mathcal{H}$能实现样本集$\mathcal{D}$的所有对分, 即${\mathcal{H}}_{|D}=2^m$， 称样本集$D$能被假设空间$\mathcal{H}打散$, 此时 ${\prod }_{\mathcal{H}}(m)=2^m$

有些情况下，$\mathcal{H}$的增长函数不可以达到$2^m$，例如在二维平面上的线性划分中，下面几种情况不可以线性可分

Break Point：随着m的增大，一定会出现一个m使假设空间无法shatter。这种不满足 的情况说明增长函数从这个点开始变缓了，是一个重大突破，所以我们把第一个不满足shatter的m值称为break point

VC Dimension: 假设空间$\mathcal{H}$的VC维是能够被$\mathcal{H}$打散的最大样本集的大小, 即

VC(H)=max{m:∏H(m)=2m}VC(\mathcal{H}) = max \{ m: \prod_{\mathcal{H}}(m) = 2^m \}VC(H)=max{m:H∏​(m)=2m}

${\prod }_{\mathcal{H}}(m)$为假设空间在数据集大小为$m$时的增长函数。 还有一种定义，理解起来更为方便：

对于一个假设空间$\mathcal{H}$，如果存在m个数据样本能够被假设空间H中的函数按所有可能的 种形式分开 ，则称假设空间$\mathcal{H}$能够把m个数据样本打散（shatter）。假设空间H的VC维就是能打散的最大数据样本数目m。若对任意数目的数据样本都有函数能将它们shatter，则假设空间$\mathcal{H}$的VC维为无穷大

要证明一个假设空间的$\mathcal{H}$的VC维为$d$， 需要证明亮点:

• 存在大小为$d$的样本集$D$能被$\mathcal{H}$打散
• 任意大小为$d+1$的样本集$D^{\prime }$都不能被$\mathcal{H}$打散

我们用个例子来更深刻的理解VC维. 令$\mathcal{H}$表示所有定义在$R$上阈值函数的集合。仍然考虑二分类问题，一点典型的阈值函数为:
$$h(x)=\{\begin{array}{r}+1，x>=c\\ -1，x<c\end{array}$$
通过调整不同的参数$c$可以得到不同的假设。易知存在大小为1的样本集能被$\mathcal{H}$打散。但是任意大小为2的样本集都不能被$\mathcal{H}$打散。于是VC($\mathcal{H}$) = 1。 譬如任意两个样本$x1=0,x2=3$. 可以通过调整参数$c$来得到分类结果.
$$\{\begin{array}{r}c=-1可以得到h(x1)=+1,h(x_2)=+1\\ c=1可以得到h(x1)=-1,h(x_2)=+1\\ c=4可以得到h(x1)=-1,h(x_2)=-1\end{array}$$
但是永远无法得到$h(x1)=+1,h(x_2)=-1$。

如果假设空间$\mathcal{H}$为有限集合，那么对于任意数据集$D$， 有$|H_{|D}\le |H|$。 当$|H|<2^{|D|}$时，$\mathcal{H}$无法打散$D$，因此可得$VC(\mathcal{H})<=log2|\mathcal{H}|$, 事实上，有限假设空间的$VC(\mathcal{H})$通常远小于 $log2|\mathcal{H}|$

需要指出的是, VC维是针对二分类问题定义的。对于多分类问题，可以用Natarajan维来刻画假设空间复杂度。在多分类问题中，假设空间$\mathcal{H}$中的假设是$\mathcal{X}$到Y={0,1,...,K−1}\mathcal{Y}=\{0,1,...,K-1\}Y={0,1,...,K−1}的映射，其中$K$为类别常数。同样的我们可以定义增长函数和打散。这里不再赘述。

Rademacher Complexity (拉德马赫尔复杂度）

Rademacher complexity是另一种刻画假设空间复杂度的工具，与VC维不同的是，它在一定程度上考虑了数据的分布。Rademacher complexity通过测量一个函数族拟合随机噪声的能力来反映该函数族的丰富度(The Rademacher complexity captures the richness of a family of functions by measuring the degree to which a hypothesis set can fit random noise)

给定数据集 D={(x1,y1),...,(xm,ym)}D = \{(x_1, y_1), ..., (x_m, y_m) \}D={(x1​,y1​),...,(xm​,ym​)}, $h\in \mathcal{H}$的经验误差为 (针对二分类问题):

$$\hat{E}(h)=\frac{1}{m}I(h(x_i)\ne y_i)=\frac{1}{2}-\frac{1}{2m}\sum _{i=1}^m{y}_{i}h(x_i)$$

若能预测对所有样本，则$\frac{1}{m}{\sum }_{i=1}^m{y}_{i}h(x_i)$取得最大值1。然而现实任务中的标记样本可能会受噪音的影响，标记可能存在偏差。在这种情况下，选择假设空间$\mathcal{H}$中表现最好的假设可能不如选择$\mathcal{H}$事先已经考虑了随机噪声的假设。
考虑随机变量${\sigma }_i$, 以0.5的概率取+1，0.5的概率取-1， 又被称为Rademacher变量，对$\sigma \text{σ}\sigma =({\sigma }_1,{\sigma }_2,...,{\sigma }_m)$求期望可以得到:

$$E_{\sigma }[\underset{h\in \mathcal{H}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}h(x_i)]$$

上式和增长函数有着相似的作用，体现了假设空间在数据集$D$的表示能力，取值范围为[0, 1], 值越接近1，假设空间的表示能力越强.当取值为1时， 存在$h\in \mathcal{H}$使得$h(x_i)={\sigma }_i$, 即${\prod }_{\mathcal{H}}=2^m$, 即$\mathcal{H}$能打散$D$.

考虑实值函数空间$\mathcal{F}$, 令Z={z1,...,zm}Z=\{z_1,...,z_m\}Z={z1​,...,zm​}， 其中$z_i\in \mathcal{Z}$。函数空间$\mathcal{F}$关于$\mathcal{Z}$的 emprical Rademecher complexity:

$${\hat{\mathcal{R}}}_z(\mathcal{F})=E_{\sigma }[\underset{f\in \mathcal{F}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}f(z_i)]$$

$Z$是一个给定集合。Emprical Rademacher complexity复杂度衡量的函数空间$\mathcal{F}$与随机噪声在$Z$上的相关性。相比于给定的$Z$，我们更关心$Z$服从分布$\mathcal{D}$时函数空间的复杂度。对分布$\mathcal{D}$独立同分布采样得到大小为$m$的集合，求期望得到Rademacher complexity

$${\mathcal{R}}_z(\mathcal{F})=E_{Z\subset \mathcal{Z}:|Z|=m}[{\hat{\mathcal{R}}}_z(\mathcal{F})]$$

如果将${\sigma }_i$改为其他的分布，可以得到其他复杂度的定义，例如Gaussian Complexity。函数空间$\mathcal{F}$关于$\mathcal{Z}$的 emprical Gaussian complexity:

$${\hat{\mathcal{O}}}_z(\mathcal{F})=E_g[\underset{f\in \mathcal{F}}{\sup }\frac{1}{m}\sum _{i=1}^m{g}_{i}f(z_i)]$$

其中$g_i$服从$N(0,1)$标准正态分布。 同样的，可以对经验Guassian complexity求期望得到Gaussian复杂度。

$${\mathcal{O}}_z(\mathcal{F})=E_{Z\subset \mathcal{Z}:|Z|=m}[{\hat{\mathcal{O}}}_z(\mathcal{F})]$$

Rademacher复杂度和VC维用到的增长函数有一定关系