使用样本内误差估计的一个难点是需要确定拟合中用到的参数个数（或复杂度）$d$。虽然在第 7.6 节介绍的有效参数个数适用于一些非线性模型，但并不能满足所有的应用场景。万普尼克-泽范兰杰斯（Vapnik–Chervonenkis）理论提供了一个复杂度的一般性的度量定义，以及对应的乐观值边界。以下为这个理论的简单综述。
假设有一类函数 $\{f(x,\alpha)\}$，由参数向量 $\alpha$ 索引，定义域为 $x\in\mathbb{R}^p$。现假设 $f$ 为一个指示函数，即取值为 0 或 1。若 $\alpha=(\alpha_0,\alpha_1)$ 而且 $f$ 为线性指示函数 $I(\alpha_0+\alpha_1^Tx>0)$，则似乎可以合理地认为 $f$ 类函数参数个数为 $p+1$。但对函数 $f(x,\alpha)=I(\sin\alpha\cdot x)$，$\alpha\in\mathbb{R}$，$x\in\mathbb{R}$，应如何处理？图 7.5 中是函数 $\sin(50\cdot x)$ 的曲线。这是一个很抖动弯曲的函数曲线，频率 $\alpha$ 越高这个曲线的抖动越快速，但它只有一个参数。尽管如此，似乎并不能就推论出它比 $p=1$ 维度的线性指示函数 $I(\alpha_0+\alpha_1^Tx)$ 复杂度更低。
![**图 7.5**：实线曲线为函数 $\sin(50x)$，$x\in[0,1]$。绿色（实心）和蓝色（空心）的方点演示了只要选定了足够高的合适频率 $\alpha$，对应的指示函数 $I(\sin(\alpha x)>0)$ 可将任意多的点区分开。](https://public.guansong.wang/eslii/ch07/eslii_fig_07_05.png)
万普尼克-泽范兰杰斯（VC）维度是一种通过评估其抖动程度来度量一类函数的复杂度的方法。
函数类 $\{f(x,\alpha)\}$ 的VC 维度定义为：可被 $\{f(x,\alpha)\}$ 中的函数（在某种配置下）区分开的点的最大个数。
如果无论如何给每个点分配二分类的标签，函数类中存在一个函数可以完全将两种类型分离开，则称这些点被这一类函数区分开。
图 7.6 说明了平面上的线性指示函数的 VC 维度是 3 而不是 4，因为四个点不一定可以被一条直线区分开。一般地，$p$ 维上的线性指示函数的 VC 维度是 $p+1$，这与自由参数的个数相同。另一方面，如图 7.5 所示，可证明 $\sin(\alpha x)$ 族函数有无穷个 VC 维度。只要选择合适的 $\alpha$，任意一个点集合都可被这类函数区分开（练习 7.8）。
上面只讨论了指示函数的 VC 维度，但这个定义可以推广到实数函数中。一类实数函数 $\{g(x,\alpha)\}$ 的 VC 维度是指示函数类 $\{I(g(x,\alpha)-\beta>0\}$ 的 VC 维度，其中 $\beta$ 取值在 $g$ 的值域中。
VC 维度可用来构建（样本外）预测误差的估计，同时也得到很多结论。利用 VC 维度的概念，可证明在一类函数的训练误差中关于乐观值的一些结论。例如，在使用 VC 维度为 $h$ 的一类函数 $\{f(x,\alpha)\}$ 拟合 N 个训练样本时，下面的结论成立的（对训练集的）概率不小于 $1-\eta$：
$$\begin{align} \text{Err}_\mathcal{T} & \leq \overline{\text{err}} + \frac{\epsilon}{2} \left( 1 + \sqrt{1 + \frac{4\cdot\overline{\text{err}}}{\epsilon}}\right) \tag{二分类} \\ \text{Err}_\mathcal{T} & \leq \frac{\overline{\text{err}}}{(1 - c \sqrt{\epsilon})_+} \tag{回归} \\ \text{where } & \epsilon = a_1 \frac{h[\log(a_2N/h)+1] - \log(\eta/4)}{N} \\ \text{and } & 0 < a_1 \leq 4, 0 < a_2 \leq 2 \end{align}$$ $$\tag{7.46}$$这些边界对所有函数成员 $f(x,\alpha)$ 同时成立，其来自于 Cherkassky and Mulier 2007, p 116-118。他们推荐 $c=1$。他们对回归问题推荐 $a_1=a_2=1$，对分类问题没有给出建议，但 $a_1=4$ 和 $a_2=2$ 对应了最差的情况。他们也给出了回归问题中的另一个实用的边界：
$$\text{Err}_\mathcal{T} \leq \overline{\text{err}} \left( 1 - \sqrt{\rho - \rho\log\rho + \frac{\log N}{2N}} \right)^{-1}_+ \tag{7.47}$$其中 $\rho=p/N$，并且没有待调整的常数。从边界中可见乐观值随 $h$ 升高而随 $N$ 降低，这于从表达式 7.24 中的 AIC 修正项 $d/N$ 中推出的性质一致。然而边界 7.46 中的结论更强：它们给出的是对所有函数 $f(x,\alpha)$ 的概率上成立的上界，而不是每个固定函数 $f(x,\alpha)$ 的乐观值期望，使我们可以从函数类的级别进行选择。
万普尼克提出的 结构风险最小化（structural risk minimization，SRM） 方法适用于一系列 VC 维度递增 $h_1<h_2 \dots$ 的嵌套模型，然后选择其中上界最小的模型。
注意类似于 7.46 中的上界通常是松弛的，但这并不影响它们成为模型选择中的可用的准则，因为重要的是测试误差互相之间的相对大小而不是绝对大小。这个方法的缺点是难以计算一类函数的 VC 维度。通常只能获得 VC 维度一个粗略的上界，而这可能并不合乎需求。第 12.2 节中的支持向量分类器，是一个运用结构风险最小化的成功案例。
7.9.1 示例（续）
![**图 7.7**：箱形图，展示了图 7.3 中四个场景中相对误差 $100 \times[\text{Err}\_\mathcal{T}(\hat{\alpha})-\min_\alpha\text{Err}\_\mathcal{T}(\alpha)]/[\max_\alpha\text{Err}\_\mathcal{T}(\alpha)-\min_\alpha\text{Err}\_\mathcal{T}(\alpha)]$ 的分布。这是使用选定模型想对于最优模型的误差。每个箱形图中有 100 个大小为 80 的训练集，计算误差的测试集大小为10,000。](https://public.guansong.wang/eslii/ch07/eslii_fig_07_07.png)
图 7.7 展示了对图 7.3 的例子使用 AIC、BIC 和 SRM 选择模型大小的结果。在 “KNN” 标签的模型中，$\alpha$ 表示邻域大小，在 “REG” 标签的模型中，$\alpha$ 表示变量子集大小。通过每个模型选择方法（例如 AIC），估计出最优模型 $\hat{\alpha}$ 并在测试集计算出真实的预测误差 $\text{Err}_\mathcal{T}(\hat{\alpha})$。在同样的训练集上计算出最优和最差模型选择的预测误差：$\min_\alpha\text{Err}_\mathcal{T}(\alpha)$ 和 $\max_\alpha\text{Err}_\mathcal{T}(\alpha)$ 和箱形图展示了下面这个数值的分布：
$$100 \times \frac {\text{Err}_\mathcal{T}(\hat{\alpha}) - \min_\alpha \text{Err}_\mathcal{T}(\alpha)} {\max_\alpha \text{Err}_\mathcal{T}(\alpha) - \min_\alpha \text{Err}_\mathcal{T}(\alpha)}$$其代表了使用所选模型想对于最优模型的误差。线性回归中模型复杂度为特征的个数；如第 7.5 所提到，由于没有将最优子集搜寻的操作考虑进来，这会低估自由度 $\text{df}$。线性分类器的 VC 维度也是特征个数。我们用 $N/k$ 作为 k-最近邻的 VC 维度。在加性误差的回归模型中，这个数值可证明是确切的有效自由度（练习 7.6）；但并不确定它等于 VC 维度。我们用 $a_1=a_2=1$ 作为 7.46 中的常数；SRM 的结果会根据常数改变，上述的值给出了最有利的结果。我们也用另一种实用边界 7.47 进行了 SRM 模型选择，得到近乎完全相同的结果。我们用 $\hat{\sigma}^2_\varepsilon = [N/(N-d)]\cdot\text{err}(\alpha)$ 作为约束最小模型（对 k 最近邻此模型为 $k=5$，因为 $k=1$ 产生零训练误差）的误分类误差。AIC 准则似乎在四个场景中都表现良好，尽管 0-1 损失的使用缺乏理论支撑。BIC 也同样表现良好，然而 SRM 的表现有好有坏。
本节练习
练习 7.6
证明一个加性误差项模型中，k 最近邻回归拟合的有效自由度为 $N/k$。
练习 7.8
Show that the set of functions $\{I(\sin(\alpha x)>0)\}$ can shatter the following points on the line: $$z^1=10^{-1},\dots,z^\ell=10^{-\ell}\tag{7.66}$$ for any $\ell$. Hence the VC dimension of the class $\{I(\sin(\alpha x)>0)\}$ is infinite.