第 22b 章 分类误差评估：交叉验证与 VC 界

本章与第 22a 章共同对应 Wasserman 原书第 22 章，重点是原书 22.8 节《Assessing Error Rates and Choosing a Good Classifier》及相关习题。第 22a 章的实验已经显示：不限深度的树训练误差为 0，测试误差却比线性模型还差。训练误差会系统地低估真实误差，而且模型越灵活、被比较的模型越多，低估越严重。这正是量化研究中"回测过拟合"的数学本质。本章给出两类工具：一是交叉验证，用没参与训练的数据估计误差；二是概率不等式（Hoeffding、VC 不等式），给出对整族分类器同时成立的误差界，从而量化"挑选"本身带来的乐观偏差。最后讨论时间序列中交叉验证的正确用法。

学习目标

1. 理解训练误差为什么低估真实误差，能画出"训练误差单调下降、验证误差 U 形"的典型图像并解释它。
2. 会用留出验证和 K 折交叉验证估计错误率、选择模型复杂度。
3. 会用 Hoeffding 不等式与并集界推导有限分类器族的一致收敛界，并据此解释"从 \(m\) 个策略中挑最好的"的乐观偏差。
4. 理解粉碎系数、VC 维的定义，会计算简单集合类的 VC 维，知道 VC 界的意义和局限。
5. 理解分类问题中偏差–方差权衡与回归的不同（Friedman 分解）。
6. 能识别时间序列数据中随机 K 折造成的信息泄露，会使用前推验证与剔除重叠样本。

读前导读

这一章在解决什么问题

结论：本章回答"回测里看到的胜率，有多少是真本事、有多少是挑出来的运气"，并给出定量的修正方法。

你在 CFA 的回测与数据挖掘偏差（data-snooping bias）部分见过这个问题的定性描述：试了足够多的策略，总有一个看起来很好。本章把它变成数学：如果你从 \(m\) 个策略里挑出样本内最好的那个，它的真实胜率与样本内胜率之间的差距，最多会有多大？答案只随 \(\log m\) 增长，这就是 Hoeffding 不等式加并集界。对线性分类器、树这类有无穷多个参数取值的"策略族"，用 VC 维代替 \(m\) 来度量"挑选空间有多大"。

实务上更常用的是交叉验证：把数据切开，在没参与训练的部分上打分。但金融时间序列有自相关和标签重叠，随机切分会让模型"偷看"到测试期的信息，导致严重高估。本章最后专门讲怎么正确地在时间序列上做验证，这在量化研究中可能比本章任何定理都更直接有用。

需要先想起来的数学

1. 二项分布与样本比例的置信区间。 正确次数 \(\sim\text{Binomial}(n,p)\)，比例 \(\hat p\) 的标准误 \(\sqrt{p(1-p)/n}\)。例：500 天、胜率 52%，标准误约 \(\sqrt{0.25/500}\approx0.022\)，52% 离 50% 还不到一个标准误。

2. 指数与对数的反解。 从 \(2me^{-2n\epsilon^2}=\alpha\) 解出 \(\epsilon\)：两边取自然对数 \(\log(2m)-2n\epsilon^2=\log\alpha\)，于是 \(\epsilon^2=\frac{1}{2n}\log\frac{2m}{\alpha}\)。参见 第 00 册第 04 章 级数与收敛 中指数对数部分。

3. 概率不等式与并集界。 并集界：\(\mathbb P(A_1\cup\cdots\cup A_m)\le\sum_j\mathbb P(A_j)\)，即"至少一件坏事发生"的概率不超过各件坏事概率之和（重叠部分被重复计算，所以是上界）。Hoeffding 不等式给出样本均值偏离真值的概率上界，比切比雪夫不等式紧得多。参见 第 00 册第 07 章 概率中的分析工具。

4. 记号 \(\sup\) 与 \(\max\)。 \(\sup\)（上确界）可以先当作"最大值"理解；区别只在于无穷多个对象时最大值可能取不到，但上确界总存在。例：\(\{0.9,0.99,0.999,\dots\}\) 没有最大值，上确界是 1。参见 第 00 册第 01 章 函数极限与连续。

5. 标准正态分布函数 \(\Phi\)。 \(\Phi(z)=\mathbb P(Z\le z)\)，\(1-\Phi(z)\) 是右尾概率。例：\(1-\Phi(1)\approx0.16\)，\(1-\Phi(-1)\approx0.84\)。

怎么读这一章

核心必读：22b.1、22b.2（交叉验证与"使用纪律"）、22b.3（有限族界，最贴近"挑策略"问题）、22b.7（时间序列交叉验证）、22b.8 实战。22b.4 的 VC 理论第一次只需理解"粉碎"的定义、例 22.22–22.23 和"VC 维是容量度量"这一结论，VC 不等式的常数可以略过。22b.5 Friedman 分解与 22b.6 维数灾难几何直观可在第二遍阅读。建议顺序：22b.1 → 22b.2 → 22b.7 → 22b.8 实验 (1)(2) → 22b.3 → 实验 (3) → 22b.4 → 22b.5–22b.6。

22b.1 训练误差的乐观偏差

训练误差 \(\hat L_n(h)\) 在固定 \(h\) 时是 \(L(h)\) 的无偏估计。但实际中 \(\hat h\) 是用同一份数据挑出来的——在所有候选中，它恰好让训练误差最小。被挑中的那个，往往是"在这份数据上运气好"的那个，所以 \(\hat L_n(\hat h)\) 向下有偏。

白话解释：用期望的语言说，对每个固定的 \(h\)，\(\mathbb E\hat L_n(h)=L(h)\)；但"先取最小值再求期望"不等于"先求期望再取最小值"：\(\mathbb E\big[\min_h\hat L_n(h)\big]\le\min_h\mathbb E\hat L_n(h)\)。最小值这个操作会主动挑出向下偏离的那个。

金融直觉：这就是基金业的"冠军诅咒"。1000 只基金都没有选股能力，去年排名第一的那只业绩依然会很亮眼；拿它的去年业绩估计明年业绩，必然高估。22b.8 实验 (3) 用数字演示了这一点：1 万个纯随机策略中最好的那个，样本内方向准确率平均达 58.6%。

例 22.14（CORIS）。 依次拟合含 1、2、…、9 个协变量的 logistic 模型，再逐个加入平方项，得到 18 个复杂度递增的分类器。训练误差单调下降（继续加项可以降到零）；10 折交叉验证估计的误差先降后升。这与第 20 章的偏差–方差权衡是同一件事：复杂度低时偏差主导，复杂度高时方差主导。

22b.2 交叉验证

22b.2.1 留出验证

最简单的做法：把数据随机分成训练集 \(\mathcal T\) 与验证集 \(\mathcal V\)（常留约 10%–30% 做验证）。只用 \(\mathcal T\) 构造 \(\hat h\)，然后在 \(\mathcal V\) 上计算

22b.2.2 K 折交叉验证

1. 把数据随机分成大小近似相等的 \(K\) 块（常取 \(K=5\) 或 \(10\)）；
2. 对 \(k=1,\dots,K\)：删去第 \(k\) 块，用其余数据训练得 \(\hat h_{(k)}\)，在第 \(k\) 块上计算错误率 \(\hat L_{(k)}\)；
3. \(\hat L(h)=\frac1K\sum_{k=1}^K\hat L_{(k)}\)。（22.33）

每个观测恰好被验证一次，所有数据都参与了训练和验证。

补充：\(K\) 的选择。 每次训练只用 \((K-1)/K\) 的数据，所以 CV 估计的是"样本量略小时"的误差，略偏悲观；\(K\) 越大这一偏差越小，但各折训练集高度重叠，估计的方差和计算量都增加。\(K=5\) 或 \(10\) 是常用的折中。留一法（\(K=n\)）在第 20 章的平滑问题中有捷径公式，在分类中一般没有。

例 22.15（CORIS 分类树）。 10 折 CV 误差在 6 个叶时最小，选出的树规则简单且可解释（见第 22a 章）。

重要的使用纪律。 用 CV 选出复杂度（例如叶子数）后，CV 误差的最小值本身又是一个"挑出来的最小值"，同样偏乐观。需要无偏的最终误差估计时，应在一开始就留出一份从不参与任何选择的测试集，或使用嵌套交叉验证（外层估计误差、内层选参数）。

22b.3 概率不等式：有限分类器族

交叉验证给出点估计；概率不等式则给出对整族分类器同时成立的置信区间，从而量化"挑选"的代价。设 \(\mathcal H\) 是一族分类器，**经验风险最小化（ERM）**选出

工具：Hoeffding 不等式（第 01 章）。\(X_i\sim\text{Bernoulli}(p)\) IID 时

定理 22.16（一致收敛）。 若 \(\mathcal H\) 有限，含 \(m\) 个分类器，则

定理 22.17。 令

这个结论的关键在于"无论怎样选出"。对单个固定的分类器，区间半宽是 \(\sqrt{\log(2/\alpha)/(2n)}\)；要对从 \(m\) 个中挑出的那个负责，半宽要放大到 \(\sqrt{\log(2m/\alpha)/(2n)}\)。\(\mathcal H\) 越大，区间越宽——候选越多，越可能挑中一个靠运气胜出的，宽区间正是对此的补偿。 好消息是代价只随 \(\log m\) 增长。

推导拆解：定理 22.17 的 \(\epsilon\) 是这样定出来的：要求定理 22.16 右边 \(2me^{-2n\epsilon^2}\) 恰好等于 \(\alpha\)，取对数解出 \(\epsilon\)（见读前导读第 2 条）。

证明里的关键是第一个不等号：\(\hat h\) 是 \(\mathcal H\) 中的某一个，所以"\(\hat h\) 偏离超过 \(\epsilon\)"这个事件包含在"族中至少有一个偏离超过 \(\epsilon\)"这个事件里，前者概率不会更大。由于后者对所有成员同时控制，不管你用什么方法（甚至偷看数据）选出 \(\hat h\)，界都成立。

数值感受（\(n=500\)，\(\alpha=0.05\)）：\(m=1\) 时半宽 0.061；\(m=10000\) 时 0.114。候选数扩大 1 万倍，半宽不到翻倍。但反过来看，即便只测了一个策略，500 天的数据也只能把胜率确定到 ±6% 左右。

22b.4 VC 理论：无限分类器族

线性分类器有无穷多个，\(\log m=\infty\)，定理 22.17 失效。Vapnik 与 Chervonenkis 的想法是：在 \(n\) 个数据点上，无穷多个分类器能产生的不同标注方式其实是有限的。

22b.4.1 粉碎系数与 VC 不等式

设 \(\mathcal A\) 是一族集合。对有限点集 \(F=\{x_1,\dots,x_n\}\)，令

白话解释：把"集合 \(A\)"理解为一条交易规则"在 \(A\) 里就做多"。在 \(n\) 个历史日子上，一条规则的全部行为就是"哪些天做多"，即 \(F\) 的一个子集。规则有无穷多条，但它们在这 \(n\) 天上产生的不同"做多日组合"最多 \(2^n\) 种；真正影响过拟合程度的是实际能产生多少种，这就是 \(N_{\mathcal A}(F)\)。

小例子：规则族为"信号值 ≤ 阈值 \(a\) 时做多"（半直线）。三天的信号值为 1、2、3，阈值从左到右移动，只能产生 \(\varnothing\)、\(\{1\}\)、\(\{1,2\}\)、\(\{1,2,3\}\) 四种组合，而不是 \(2^3=8\) 种。所以这族规则虽然有无穷多个阈值，"有效个数"只有 \(n+1\) 个，挑选它的代价很小。

"粉碎"就是"任何做多日组合都能实现"——容量大到可以拟合任何标签，这正是过拟合的危险信号。

定理 22.18（Vapnik–Chervonenkis 1971）。 对任意分布 \(\mathbb P\)、任意 \(n\) 和 \(\epsilon>0\)，

对分类器族 \(\mathcal H\)，令 \(\mathcal A=\{\{x:h(x)=1\}:h\in\mathcal H\}\)，定义 \(s(\mathcal H,n)=s(\mathcal A,n)\)。

定理 22.19。

它与定理 22.17 结构完全相同，只是把"分类器个数 \(m\)"换成了"在 \(n\) 个点上能产生的不同标注数 \(s(\mathcal H,n)\)"。只有当 \(s(\mathcal H,n)\) 增长得不太快（多项式而非指数）时，\(\epsilon_n\to0\)，这个界才有用。

22b.4.2 VC 维

定义 22.20。 \(\mathcal A\) 的 VC 维 \(VC(\mathcal A)\) 是 \(\mathcal A\) 能粉碎的最大点集的大小，即使 \(s(\mathcal A,k)=2^k\) 的最大 \(k\)；若对所有 \(n\) 都有 \(s(\mathcal A,n)=2^n\)，则 \(VC(\mathcal A)=\infty\)。

定理 22.21（Sauer 引理的推论）。 若 \(VC(\mathcal A)=v<\infty\)，则 \(s(\mathcal A,n)\le n^v+1\)。

这是一个"相变"：粉碎系数要么在所有 \(n\) 上等于 \(2^n\)（指数增长，界无用），要么一旦超过 VC 维就只能多项式增长。VC 维有限，\(\log s(\mathcal H,n)\approx v\log n\)，于是 \(\epsilon_n\approx\sqrt{32v\log n/n}\to0\)。VC 维是分类器族"容量"的度量。

推导拆解：为什么多项式增长就够、指数增长就不行？把 \(s\) 代入 \(\epsilon_n^2=\frac{32}{n}\log\frac{8s}{\alpha}\)。

若 \(s=2^n\)：\(\log s=n\log2\)，\(\epsilon_n^2\approx32\log2\approx22\)，不随 \(n\) 减小，界没用。直观上，族能拟合任意标签，数据再多也无法排除"纯靠拟合噪声"。

若 \(s\le n^v+1\)：\(\log s\approx v\log n\)，\(\epsilon_n^2\approx\frac{32v\log n}{n}\)。分子是对数增长，分母是线性增长，比值趋于 0（例如 \(n=10^6\) 时 \(\log n/n\approx1.4\times10^{-5}\)）。

实务上的读法：要让误差界维持不变，样本量大致要与 \(v\)（乘一个对数因子）成比例增加。

例题。 计算 VC 维要做两件事：找一个大小为 \(v\) 的点集能被粉碎，再证明任何 \(v+1\) 个点都不能被粉碎。

• 例 22.22：半直线 \(\{(-\infty,a]\}\)。任何单点能被粉碎（\(a\) 取在点的左边或右边）。两点 \(x<y\) 时，挑不出只含 \(y\) 的子集（包含 \(y\) 的半直线必然包含 \(x\)）。\(VC=1\)。
• 例 22.23：实轴上的闭区间。两点能被粉碎；三点 \(x<y<z\) 时挑不出 \(\{x,z\}\)（包含 \(x,z\) 的区间必然包含 \(y\)）。\(VC=2\)。
• 例 22.24：平面上的线性半空间。任意不共线的三点能被粉碎；四点时，若构成凸四边形，对角的两点无法被单独挑出；若一点在另三点的凸包内，该点无法被单独排除。\(VC=3\)。一般地，\(\mathbb R^d\) 中半空间的 VC 维是 \(d+1\)。
• 例 22.25：平面上边平行于坐标轴的矩形。菱形排列的 4 点能被粉碎；任意 5 点中，取最左、最右、最上、最下的点（至多 4 个），包含它们的最小矩形必然包含剩下的点，所以去掉那个点的子集无法挑出。\(VC=4\)。

定理 22.26。 \(d\) 维线性分类器的 VC 维是 \(d+1\)，所以真实错误率的 \(1-\alpha\) 置信区间为 \(\hat L_n(\hat h)\pm\epsilon_n\)，

VC 界的实际意义与局限。 VC 界对任何分布都成立，代价是常数极其保守。下一节的计算会显示，5 维线性分类器、3000 个样本时 \(\epsilon_n\approx0.75\)——比 0–1 区间的一半还宽，毫无实用价值。它的价值在于定性结论：(1) 只要 VC 维有限，ERM 就能一致地逼近族内最优；(2) 误差界随 \(\sqrt{v\log n/n}\) 变化，所需样本量与模型容量成正比；(3) 不同族的比较应看容量而不是参数个数（例如 \(\sin(\omega x)\) 只有一个参数但 VC 维无穷）。实践中误差估计还是要靠交叉验证。

22b.5 分类中的偏差–方差：与回归不同

原书习题 13（Friedman 1997）揭示了分类与回归的一个重要差别。固定 \(x\)，设估计的回归函数近似正态 \(\hat r(x)\approx N(\bar r(x),\sigma^2(x))\)，\(\hat h(x)=I(\hat r(x)>\frac12)\)。由第 22a 章定理 22.5 的证明，

推导拆解：第一个等式就是第 22a 章证明中"错分概率之差 \(=(2r-1)(h^*-h)\)"在随机的 \(\hat h\) 上取期望：\(\hat h\ne h^*\) 时多付 \(|2r-1|\)，否则不多付。第二步：设 \(r(x)>\frac12\)，\(h^*=1\)，于是 \(\hat h\ne h^*\) 等价于 \(\hat r<\frac12\)；\(\hat r\) 近似 \(N(\bar r,\sigma^2)\)，标准化得 \(\mathbb P\big(Z<\frac{1/2-\bar r}{\sigma}\big)=1-\Phi\big(\frac{\bar r-1/2}{\sigma}\big)\)（用了 \(\Phi(-z)=1-\Phi(z)\)）。

数值例子：设真实 \(r(x)=0.6\)。 模型 A：\(\bar r=0.55\)（低估了 0.05，但方向对），\(\sigma=0.05\)。\(\Phi\) 的自变量 \(=1\)，误判概率 \(1-\Phi(1)\approx0.16\)；把 \(\sigma\) 降到 0.01，自变量 \(=5\)，误判概率几乎为 0。降方差有益。 模型 B：\(\bar r=0.45\)（偏差把方向弄反），\(\sigma=0.05\)。自变量 \(=-1\)，误判概率 \(1-\Phi(-1)\approx0.84\)；把 \(\sigma\) 降到 0.01，误判概率接近 1。降方差反而更糟。

解读：分类中偏差的作用是非线性的，只有符号重要。

• 若偏差不改变 \(\bar r\) 落在 1/2 的哪一侧（\(\Phi\) 的自变量为正），偏差再大也无妨，减小方差 \(\sigma\) 就能降低错误率；
• 若偏差把 \(\bar r\) 推到了错误的一侧（自变量为负），减小方差反而提高错误率——估计越"自信"，错得越稳定。

所以分类对偏差的容忍度高于回归：一个概率估计得很不准（偏差大）但方向正确的模型，可以是很好的分类器。这也解释了为什么朴素 Bayes 这类概率严重失真的方法分类效果不差，以及为什么 bagging（降方差）在分类中特别有效。对交易而言，它提醒我们区分两个目标：预测方向（分类）和预测幅度或概率（回归、概率校准）。仓位大小依赖于后者，只做好前者是不够的。

22b.6 维数灾难的几何直观

原书习题 10（Hastie et al. 2001）：\(X\) 在 \([-\frac12,\frac12]^d\) 上均匀分布，\(n\) 个样本，\(R\) 是原点到最近样本点的距离。对 \(r\le\frac12\)，半径 \(r\) 的球在立方体内，\(\mathbb P(R>r)=(1-v_d(r))^n\)，\(v_d(r)=r^d\frac{\pi^{d/2}}{\Gamma(d/2+1)}\)。令其为 1/2，得 \(R\) 的中位数

推导拆解：\(\mathbb P(R>r)=(1-v_d(r))^n\) 的含义是"\(n\) 个点全都落在半径 \(r\) 的球外"：每个点落在球内的概率等于球的体积 \(v_d(r)\)（立方体体积为 1，均匀分布下概率 = 体积），各点独立，所以概率相乘。\(v_d(r)\) 是 \(d\) 维球体积公式，\(\Gamma\) 是阶乘的推广（\(\Gamma(k+1)=k!\)），\(d=2\) 时退化为 \(\pi r^2\)，\(d=3\) 时为 \(\frac43\pi r^3\)。令 \((1-v_d(R))^n=\frac12\) 解出 \(R\) 就是中位数。

关键在于高维球的体积极小：半径 \(\frac12\) 的球在 \(d=10\) 时只占单位立方体体积的约 0.25%，大部分体积都在"角落"里，所以中心附近几乎没有样本。

22b.7 时间序列中的交叉验证（本教材补充）

原书的交叉验证假设数据 IID。金融数据违反这一假设的方式有两种，都会让随机 K 折严重高估预测能力。

1. 特征的持续性。 估值、长期动量、波动率等特征高度自相关，相邻两天的特征几乎相同。随机分折时，测试样本的"邻居"几乎必然在训练集中。
2. 标签重叠。 用"未来 \(H\) 天收益的方向"作标签时，相邻样本的标签共享 \(H-1\) 天的收益，几乎相同。

两者叠加：灵活的模型只要"记住"训练集中时间相邻的样本，就能在测试集上猜对，哪怕特征对未来毫无预测力。正确的做法：

• 前推验证（walk-forward）：只用测试期之前的数据训练，模拟真实的信息结构；
• 剔除（purging）：从训练集中删去标签区间与测试期重叠的样本（训练集末尾的 \(H\) 天）；
• 禁区（embargo）：在测试期之后再空出一段，防止测试期信息通过序列相关渗入随后的训练样本（在"组合 K 折"等非前推的方案中需要）。

这些做法系统地见于 López de Prado（2018）《Advances in Financial Machine Learning》。

22b.8 量化实战

场景。 三个实验。(1) 用不同大小的分类树重现例 22.14 的图像：训练误差、10 折 CV 误差、真实测试误差。(2) 构造一个标签完全不可预测的数据集——日收益是纯噪声，特征是高度持续的 AR(1) 过程，标签是未来 20 日收益的方向——比较随机 5 折 CV 与前推验证。(3) \(m\) 个纯随机的"择时策略"在 500 个交易日上比较方向准确率，看最优者的样本内表现，以及 Hoeffding + 并集界与 VC 界给出的修正量。

import numpy as np, warnings
warnings.filterwarnings("ignore")
from sklearn.tree import DecisionTreeClassifier
from sklearn.ensemble import RandomForestClassifier
from sklearn.model_selection import KFold, cross_val_score

rng = np.random.default_rng(222)
# ---------- (1) 复杂度与误差：训练误差单调降，CV 误差 U 形 ----------
def make(n):
    X = rng.standard_normal((n, 5))
    logit = 0.6 * X[:, 0] - 0.5 * (X[:, 1] ** 2 - 1) + 0.4 * X[:, 0] * X[:, 1]
    return X, rng.binomial(1, 1 / (1 + np.exp(-logit)))
X, y = make(2000); Xte, yte = make(100000)
print("叶子数  训练误差  10折CV误差  测试误差")
for leaves in [2, 4, 8, 16, 32, 64, 128, 256, 512]:
    m = DecisionTreeClassifier(max_leaf_nodes=leaves, random_state=0)
    cv = 1 - cross_val_score(m, X, y, cv=KFold(10, shuffle=True, random_state=0)).mean()
    m.fit(X, y)
    print("%5d %9.3f %10.3f %9.3f" % (leaves, 1 - m.score(X, y), cv, 1 - m.score(Xte, yte)))

# ---------- (2) 时间序列：随机 K 折的信息泄露 ----------
T, H = 3000, 20
ret = 0.01 * rng.standard_normal(T + H)                       # 日收益：纯噪声，不可预测
feat = np.zeros((T, 3))
for k, phi in enumerate([0.98, 0.95, 0.9]):                   # 高度持续的特征（如估值、长期均线偏离）
    e = rng.standard_normal(T)
    for t in range(1, T):
        feat[t, k] = phi * feat[t - 1, k] + e[t]
fwd = np.array([ret[t + 1:t + 1 + H].sum() for t in range(T)])  # 未来 20 日收益（标签相互重叠）
lab = (fwd > 0).astype(int)
rf = RandomForestClassifier(n_estimators=200, min_samples_leaf=5, random_state=0, n_jobs=-1)
acc_random = cross_val_score(rf, feat, lab, cv=KFold(5, shuffle=True, random_state=0)).mean()
acc_block, acc_purged = [], []
folds = np.array_split(np.arange(T), 5)
for k in range(1, 5):                                          # 前推：只用过去训练
    te = folds[k]
    tr_all = np.arange(te[0])
    tr_pur = np.arange(max(te[0] - H, 0))                      # 剔除与测试期标签重叠的最后 H 天
    acc_block.append(rf.fit(feat[tr_all], lab[tr_all]).score(feat[te], lab[te]))
    acc_purged.append(rf.fit(feat[tr_pur], lab[tr_pur]).score(feat[te], lab[te]))
print("标签不可预测（真实准确率 50%%）时：随机5折 CV 准确率 = %.3f" % acc_random)
print("                         前推验证 = %.3f   前推+剔除重叠 = %.3f" % (np.mean(acc_block), np.mean(acc_purged)))

# ---------- (3) 有限类的一致收敛界：从 m 个“策略”中挑最好的 ----------
n, alpha = 500, 0.05
for m in [1, 10, 100, 1000, 10000]:
    best = []
    for _ in range(200):
        acc = rng.binomial(n, 0.5, size=m) / n                 # m 个纯随机策略的样本内方向准确率
        best.append(acc.max())
    eps = np.sqrt(np.log(2 * m / alpha) / (2 * n))
    print("m=%5d  最优策略样本内准确率均值=%.3f   Hoeffding+并集界 ε=%.3f" % (m, np.mean(best), eps))
# VC 界：d 维线性分类器
for d, nn in [(5, 3000), (5, 100000), (50, 100000)]:
    eps = np.sqrt(32 / nn * np.log(8 * (nn ** (d + 1) + 1) / alpha))
    print("VC 界: d=%2d, n=%6d -> ε=%.3f" % (d, nn, eps))

关键输出：

叶子数  训练误差  10折CV误差  测试误差
    2     0.393      0.408     0.415
    4     0.353      0.377     0.378
    8     0.331      0.365     0.357
   16     0.312      0.369     0.366
   32     0.280      0.376     0.381
   64     0.236      0.379     0.375
  128     0.174      0.394     0.398
  256     0.084      0.403     0.409
  512     0.000      0.415     0.427
标签不可预测（真实准确率 50%）时：随机5折 CV 准确率 = 0.584
                         前推验证 = 0.491   前推+剔除重叠 = 0.495
m=    1  最优策略样本内准确率均值=0.500   Hoeffding+并集界 ε=0.061
m=   10  最优策略样本内准确率均值=0.535   Hoeffding+并集界 ε=0.077
m=  100  最优策略样本内准确率均值=0.555   Hoeffding+并集界 ε=0.091
m= 1000  最优策略样本内准确率均值=0.572   Hoeffding+并集界 ε=0.103
m=10000  最优策略样本内准确率均值=0.586   Hoeffding+并集界 ε=0.114
VC 界: d= 5, n=  3000 -> ε=0.753
VC 界: d= 5, n=100000 -> ε=0.154
VC 界: d=50, n=100000 -> ε=0.435

解读。

1. 例 22.14 的图像。 训练误差从 0.393 单调降到 0；CV 误差在 8 个叶子处最低（0.365），之后回升；真实测试误差与 CV 误差走势一致，最低点也在 8 个叶子。CV 正确地选出了复杂度。
2. 随机 K 折的泄露非常严重。 标签由纯噪声决定，任何方法的真实准确率都是 50%。随机 5 折 CV 却报告 58.4%——在日频方向预测中，这已经是"非常强"的信号。前推验证给出 49.1%，剔除重叠后 49.5%，都与真实情况相符。若在回测报告中看到用随机 K 折得到的准确率，应该首先怀疑这一点。
3. 挑选的代价。 1 万个毫无预测力的策略，最好的那个在 500 天上平均有 58.6% 的方向准确率。Hoeffding + 并集界给出的半宽 \(\epsilon=0.114\) 足以覆盖这一乐观偏差（\(0.586-0.5=0.086<0.114\)），而且只随 \(\sqrt{\log m}\) 增长。这正是第 10b 章多重检验在分类语言中的表述：报告最优策略的表现时，必须同时报告一共试了多少个。
4. VC 界过于保守。 5 维线性分类器、3000 个样本时 \(\epsilon=0.75\)，没有任何实用意义；10 万样本时也有 0.15。50 维时更差。VC 界的价值在于说明"容量与样本量之比"决定泛化能力，而不是给出可用的数字。

本章小结

用同一份数据选出的分类器，其训练误差会低估真实误差，模型越灵活、候选越多，低估越严重。交叉验证用未参与训练的数据估计误差，K 折 CV 是标准做法；CV 的最小值本身也偏乐观，最终评估需要独立的测试集或嵌套 CV。概率不等式给出对整族分类器同时成立的误差界：有限族用 Hoeffding 加并集界，半宽 \(\sqrt{\log(2m/\alpha)/(2n)}\) 随候选数的对数增长；无限族用粉碎系数和 VC 维代替候选数，VC 维有限时粉碎系数多项式增长、ERM 一致。VC 界常数过于保守，主要提供定性理解。分类中的偏差只在改变决策方向时才有害，因此分类比回归更能容忍偏差，降方差的方法更有效。时间序列中随机 K 折会因特征持续性和标签重叠而泄露信息，必须使用前推验证和剔除。

练习

基础

1. 证明定理 22.16 与 22.17。若 \(n=250\)（一年交易日），\(\alpha=0.05\)，要使半宽 \(\epsilon\le0.05\)，最多能比较多少个策略？（提示：\(\log(2m/0.05)\le2\cdot250\cdot0.0025=1.25\)，\(m\le0.087\)，即连一个都不够；说明一年数据不足以在 5% 精度上确认方向准确率。）
2. 证明例 22.22、22.23 中的 VC 维结论。
3. 原书习题 4：求平面上圆盘族 \(\{(x,y):(x-a)^2+(y-b)^2\le c^2\}\) 的 VC 维。（答案：3。三个不共线点可被粉碎；四点时，若构成凸四边形，两对对角点不能同时被分别挑出——两圆之差的几何论证；若一点在另三点凸包内，则无法排除该点。）
4. 解释为什么 \(\sin(\omega x)\) 型分类器族 \(\{x:\sin(\omega x)>0\}\) 只有一个参数，VC 维却是无穷。这对"用参数个数衡量模型复杂度"有什么启示？
5. 留出验证集大小为 \(m=500\)，测得错误率 0.46。给出真实错误率的 95% 置信区间，并判断能否在 5% 水平上声称分类器优于瞎猜。（提示：\(0.46\pm1.96\sqrt{0.46\cdot0.54/500}=0.46\pm0.044\)，上界 0.504，不能。）

进阶

6. 原书习题 13：推导 22b.5 节的 Friedman 公式，并构造一个数值例子说明"减小方差反而提高错误率"。
7. 原书习题 10：推导最近邻距离中位数公式，并编程验证 \(n=100,1000,10000\) 时中位数超过 1/2 的维数分别为 9、12、14。
8. 原书习题 6：用 VC 理论给 iris 数据（或任一 4 维、150 样本的数据集）上的 LDA 分类器构造真实错误率的置信区间。结果有用吗？与 10 折 CV 比较。
9. 在 22b.8 节实验 (2) 中把标签期限 \(H\) 从 20 改为 1，随机 5 折的乐观偏差如何变化？把特征持续性 \(\phi\) 改为 0.5 呢？分别解释"特征持续性"与"标签重叠"各自的贡献。
10. 设计一个嵌套交叉验证：外层 5 折前推估计误差，内层在训练期内用前推验证选择树的叶子数。与"在全样本上用 CV 选叶子数、再报告该 CV 误差"的做法比较，后者偏乐观多少？

原书推荐习题：第 22 章习题 4、6、10、13。

原书对照