【机器学习chp8】统计学习理论

前言

本文遗留问题：无

前言

一、结构风险最小化

1、最小化风险决策

2、分类与回归中的最小化风险决策

3、统计学习的基本目标

4、无免费午餐定理

5、Hoeffding不等式

（1）背景及定义

（2）Hoeffding不等式的意义与特点

6、Hoeffding不等式的应用——训练误差与测试误差的偏差分析

（1）训练误差与测试误差的偏差分析

（2）泛化能力评估

（3）概率估计

（4）总结

7、有限个模型的机器学习中的训练误差与测试误差的偏差分析

（1）背景与问题

（2）Hoeffding 不等式的应用

（3）模型选择问题

（4）错误概率的推导

（5）结论

（6）两个关键问题需要解决

（7）关键问题一

（8）关键问题二

8、无限个模型的机器学习的训练误差与测试误差的偏差分析

（1）假设空间复杂度对偏差的影响

（2）VC 维度的引入

（3）无限模型的泛化上界分析

（4）无限模型的泛化能力分析

9、模型复杂度

（1）模型复杂度与 “训练误差与测试误差偏差” 的关系

（2）模型复杂度与 “训练误差与测试误差偏差” 的关系公式推导

10、样本复杂度

（1）定义

（2）公式分析

（3）实例分析

11、结构风险最小化

12、模型评价

（1）奥卡姆剃刀原则（Occam's Razor）

（2）最小描述长度原则（MDL Principle）

（3）示例分析

（4）机器学习实践中的模型评价

13、例子：多项式拟合sin函数

二、误差的偏差-方差分解

1、训练数据与目标函数

2、偏差与方差的概念

3、正则化与模型复杂度的影响

4、实验观察

5、偏差-方差权衡的实际意义

三、学习曲线

1、学习曲线

2、学习曲线的分析和意义

3、从学习曲线判断过拟合、欠拟合（欠拟合和过拟合的外在表现）

（1）欠拟合图示

（2）过拟合图示

（3）好的模型图示

（4）模型复杂度与训练误差、验证误差的关系

（5）欠拟合与过拟合的解决方法

四、⭐⭐全文总结⭐⭐

附录

1、经验风险与结构风险

2、期望风险

（1）期望风险定义

（2）期望风险、经验风险、结构风险的关系

3、条件风险

4、有限个模型的机器学习和无限个模型的机器学习

（1）假设空间的规模

（2）泛化能力的来源

（3）表达能力的限制

（4）泛化风险的控制方法

（5）总结

有限与无限模型学习的本质区别

5、假设空间是什么

（1）什么是假设空间

（2）形式化的定义

（3）假设空间的来源

（4）假设空间的作用

（5）假设空间的选择

（6）举例说明

6、关键问题二的详细分析

（1）Hoeffding 不等式的前提条件

（2）f* 的选择改变了性质

（3）使用 Hoeffding 不等式的替代方法

7、模型复杂度与容忍度概念辨析

（1）模型复杂度

（2）容忍度（测试误差与训练误差之间的偏差上界）

（3）二者的联系

一、结构风险最小化

1、最小化风险决策

核心内容：

引入损失函数 $L(\hat{y}, y)$ 表示预测值 $\hat{y}$ 与真实值 $y$ 之间的差异。
期望风险 $R_{\text{exp}}(\hat{y}(x)) = \int L(\hat{y}(x), y) p(x, y) dx dy$ ，是整体损失的期望值。
条件风险 $R(\hat{y}(x) | x) = \int L(\hat{y}(x), y)p(y|x)dy$ ：是给定样本 $x$ 时的损失。
最优决策选择使对每个样本条件风险最小的决策规则： $\hat{y}(x)$ 。

最小风险决策是最小期望风险决策，期望风险是所有条件风险的加权平均，要让最小期望风险最小，就得使对每个样本条件风险最小，因为这里对每个样本条件风险最小的决策是同一个规则。

2、分类与回归中的最小化风险决策

分类任务

0-1损失函数： $L(\hat{y}, y) = 0 \text{ (if } \hat{y} = y\text{), } 1 \text{ (otherwise)}$
条件风险 $R(\hat{y}(x)|x) = 1 - P(Y=c|x)$ ，最小化条件风险等价于选择 最大后验概率分类器： $\hat{y}(x) = \text{argmax}_c P(Y = c|x)$

这其实就是本专栏《机器学习chp2》中的最小错误率决策。

回归任务

平方损失函数： $L(\hat{y}, y) = (\hat{y} - y)^2$ 。
条件风险公式化后，最优预测值为条件期望： $\hat{y}(x) = \mathbb{E}[y|x]$ 。

3、统计学习的基本目标

机器学习三部分：模型、策略、算法。

统计学习的目标：

寻找映射函数 $f(x)$ （模型），使得其期望风险（损失函数：策略） $R(f) = \mathbb{E}[L(f(x), y)]$ 最小。
统计学习本质是一个期望风险最小化（算法）问题。

问题引入：

在实际中无法获取联合分布 $p(x, y)$ ，只能通过训练样本近似期望风险，即只能经验风险来近似期望风险。由此带来的过拟合问题是算法需要关注的最关键的点。

4、无免费午餐定理

定理内容：

假设所有可能的目标函数在问题空间上是均匀分布的，在这种情况下，任意两种算法在所有问题上的平均性能是相同的。
换句话说，没有一个算法可以在所有情况下都表现得最好。
如果考虑到所有潜在的问题，任何一种算法的优点在某些问题上会被另一种算法的优点抵消。总体而言，所有算法的表现是“平均一致”的。
如果要比较两种算法的表现，需要在特定问题的背景下进行分析。
NFL 定理成立的前提是目标函数在问题空间上是均匀分布的。然而，在实际问题中，这一条件往往不满足。具体而言：
- 真实世界的任务分布通常不是均匀的。
- 某些算法可能在真实世界中的某些特定问题上表现优异。

启示：

NFL 定理告诉我们，算法性能的优劣依赖于问题的分布特性。
在实际中，问题的分布通常不是均匀的，充分利用问题的先验知识，选择与问题特性匹配的模型和算法，是提高性能的关键。

“在目标函数均匀分布的假设下” 是 No Free Lunch (NFL) 定理 的核心前提条件之一，它的意思是：在所有可能的问题中，目标函数（或数据分布）是均匀分布的，即每一个目标函数出现的概率是相等的。

目标函数的含义

在机器学习或优化问题中，目标函数是我们希望优化或学习的函数。例如：
- 在分类问题中，目标函数可能是类别标签 $y$ 与输入 $x$ 的映射 $f(x)$ 。
- 在优化问题中，目标函数可能是我们希望最小化的损失函数或能量函数。

5、Hoeffding不等式

（1）背景及定义

Hoeffding不等式是概率论中的一个重要工具，属于集中不等式的范畴，用于量化独立随机变量的和（或均值）与其期望值之间偏离的概率。它的核心作用是为大数法则和统计学习理论提供概率界限。

数学形式：

$P\left(\left|\frac{1}{N} \sum_{i=1}^N Z_i - \mathbb{E}[Z_i]\right| \geq \epsilon\right) \leq 2\exp\left(-\frac{2N\epsilon^2}{(b-a)^2}\right)$

其中：

记 $\bar{Z} = \frac{1}{N}\sum_{i=1}^N Z_i$ ，表示样本均值。
$\exp(-\frac{2N\epsilon^2}{(b-a)^2})$ ：随着样本数量 $N$ 增大，概率界会以指数速度减小。
$Z_1, Z_2, \dots, Z_N$ ：独立随机变量，每个变量的取值范围为 $[a, b]$ ；
$\mathbb{E}[Z_i]$ ：随机变量 $Z_i$ 的期望；
$\epsilon > 0$ ：指定的偏差范围；
$N$ ：样本数量。

（2）Hoeffding不等式的意义与特点

i、概率收敛的速度

Hoeffding不等式表明，随着样本数量 $N$ 的增加，样本均值 $\bar{Z}$ 与期望值 $\mathbb{E}[\bar{Z}]$ 的偏差超过 $\epsilon$ 的概率以指数形式减小。

ii、与样本范围相关

偏差概率界限与变量的取值范围 $[a, b]$ 密切相关。如果范围更小（即 $(b-a)$ 更小），概率界限会更严格。

iii、分布无关性

Hoeffding不等式不依赖于随机变量的分布形式，只要求随机变量独立且取值有界。这使得它具有很强的适用性。

6、Hoeffding不等式的应用——训练误差与测试误差的偏差分析

（1）训练误差与测试误差的偏差分析

在机器学习中，Hoeffding不等式可以用来量化训练误差与测试误差之间的偏差：

$P\left(|E_{\text{train}} - E_{\text{test}}| \geq \epsilon\right) \leq 2 \exp\left(-2N\epsilon^2\right)$

其中：

$E_{\text{train}}$ 是训练集上的误差；
$E_{\text{test}}$ 是测试集上的误差；
$N$ 是样本数量。

结论是：当样本数量 $N$ 足够大时，训练误差和测试误差非常接近。

（2）泛化能力评估

Hoeffding不等式可以为机器学习模型的泛化性能提供理论界限：

如果模型在训练集上的表现非常好，且训练样本足够多，则模型在测试集上的表现也会很好。

（3）概率估计

在概率估计问题中，Hoeffding不等式可以用来分析样本估计值与真实概率之间的差距。例如，使用样本均值估计总体概率时，可以通过 Hoeffding 不等式提供误差界限。

（4）总结

Hoeffding不等式是统计学习理论中的重要工具，它以独立随机变量的均值为中心，提供了一个概率偏差的严格界限。其特点是分布无关性和指数形式的概率衰减，是分析机器学习中泛化误差、训练误差与测试误差差异的强有力工具。然而，在具体应用中，可以结合实际场景使用更精细的界限（如 Bernstein 不等式）以获得更紧的结果。

7、有限个模型的机器学习中的训练误差与测试误差的偏差分析

（1）背景与问题

假设模型集合是有限的（包含有限个模型），记为 $\{f_1, f_2, \dots, f_M\}$ ，其中 $M$ 是模型数量。
希望通过训练数据找到一个最优模型 $f^*$ ，使得训练误差 $E_{\text{train}}(f^*)$ 能很好地近似测试误差 $E_{\text{test}}$ 。

（2）Hoeffding 不等式的应用

利用 Hoeffding 不等式，可以为任意一个具体模型 $f$ 给出训练误差和测试误差之间的偏差概率界限：

$P(|E_{\text{train}}(f) - E_{\text{test}}(f)| \geq \epsilon) \leq e^{-2N\epsilon^2}$

这里 $N$ 是样本数量， $\epsilon$ 是训练误差与测试误差的允许偏差。

（3）模型选择问题

当模型集合有限时，从所有模型中选择训练误差最小的模型 $f^*$ 。但需要保证选出的模型在测试集上也有良好表现。

（4）错误概率的推导

选择 $f^*$ 后，训练误差与测试误差的偏差概率为：

$P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leq$ $P($ 坏 $f_1$ 或坏 $f_2$ 或坏 $f_M$ $)$

根据联合概率的不等式：

$P($ 坏 $f^*)$ $\leq$ $P($ 坏 $f_{1})$ $+$ $P($ 坏 $f_{2})$ $+\cdots +$ $P($ 坏 $f_{M})$

每个模型的“坏”概率上界为 $e^{-2N\epsilon^2}$ ，因此：

$P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leq M \cdot e^{-2N\epsilon^2}$

（5）结论

当模型数量 $M$ 是有限的，样本数量 $N$ 足够大时，上述概率界限可以非常小，从而保证测试误差接近训练误差。
这说明：有限假设空间的机器学习是可行的。

（6）两个关键问题需要解决

（7）关键问题一

公式 $P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leqslant$ $P($ 坏 $f_1$ 或坏 $f_2$ 或坏 $f_M$ $)$ $\leq$ $P($ 坏 $f_{1})$ $+$ $P($ 坏 $f_{2})$ $+\cdots +$ $P($ 坏 $f_{M})$ 为什么成立？（其中 $P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) =$ $P($ 坏 $f^*)$ ）

公式前一半成立的原因是：（这里说的模型的好坏其实指的是过拟合的程度，过拟合程度高就相对坏，过拟合程度低就相对好）

$f^*$ 包含在假设空间 $\{f_1, f_2, \ldots, f_M\}$ 中， $f^*$ 是假设空间 $\{f_1, f_2, \ldots, f_M\}$ 中训练误差最小的模型。所以假设空间中至少有一个是坏的的概率一定是大于其中的一个 $f^*$ 是坏的的概率。也就是说， $f^*$ 是坏的，因为 $f^*$ 属于假设空间 $\{f_1, f_2, \ldots, f_M\}$ ，所以假设空间 $\{f_1, f_2, \ldots, f_M\}$ 中至少有一个是坏的，但假设空间 $\{f_1, f_2, \ldots, f_M\}$ 中有一个是坏的， $f^*$ 却不一定是坏的（其实这里 $f^*$ 大概率就是假设空间中坏的那一个，因为 $f^*$ 训练误差最小，它是最可能过拟合的），所以说 $f^*$ 是坏的的概率一定小于假设空间 $\{f_1, f_2, \ldots, f_M\}$ 中有一个是坏的的概率，即公式的前一半成立。

公式后一半成立的原因是：

联合事件的概率上界可以用所有单独事件概率的和表示： $P(A$ 或 $B)$ $\leq P(A) + P(B)$

（8）关键问题二

这个问题是否理解是本章是否理解的关键！！！

既然 f* 是候选集中的一个，为什么不能直接对 f* 使用 Hoeffding 不等式来确定其训练误差和测试误差之间的差距概率的上界呢？

这是一个非常深刻的问题，涉及Hoeffding 不等式的适用范围以及模型选择对概率分布的影响。虽然 $f^*$ 是候选集中的一个，但直接对 $f^*$ 使用 Hoeffding 不等式并不能准确反映其训练误差和测试误差之间的差距上界。原因在于模型选择过程改变了 $f^*$ 的性质，使得 Hoeffding 不等式不再适用于单独的 $f^*$ 。这个选择过程是从整个假设空间中选择的训练误差最小的一个，其实 $f^*$ 也极可能是样本空间中最坏的或者说比较坏的，挑选出 $f^*$ 后，可以对其他假设模型使用 Hoeffding 不等式，再根据关键问题一中的结论，即可推导出有限假设空间时的训练误差和测试误差的偏差分析。

所以说无法通过Hoeffding 不等式来确定 $f^*$ 训练误差与测试误差之间的差距概率的上界，那要怎么办呢？

为了弥补直接对 $f^*$ 使用 Hoeffding 不等式的问题，统计学习理论提出了改进的方法，将模型选择过程引入不等式的分析中。通过将假设空间的复杂度（如候选模型数量 M 或 VC 维度）引入到不等式中，我们可以得出更合理的上界。总的来说就是，模型选择过程破坏了概率独立性假设，需要通过假设空间复杂度和联合事件概率来修正 Hoeffding 不等式的适用范围。详细分析见附录6

此处转到附录6

8、无限个模型的机器学习的训练误差与测试误差的偏差分析

无限假设空间的介绍见附录4

通过上面对有限个模型机器学习的训练误差与测试误差的偏差分析中的关键问题二进行详细的剖析，在无限多个模型中选择最优的模型，这个选择过程极大地扩大了训练误差与测试误差的偏差。

想要估计 $f^*$ 的训练误差与测试误差的偏差，直接使用 Hoeffding 不等式显然不可行，由于假设空间无限大，所以通过联合事件概率将模型数量 $M$ 引入到不等式中也不可行。所以要让假设空间的复杂度（如VC维）引入到不等式中。详细分析如下：

（1）假设空间复杂度对偏差的影响

对于有限假设空间（模型个数为 $M$ ），最优模型的坏概率 $P($ 坏 $f^*)$ 上界为：

$P($ 坏 $f^*)$ $\leq M \cdot e^{-2N\epsilon^2}$

含义：
- $N$ ：样本数；
- $\epsilon$ ：训练误差与测试误差之间的偏差。

当假设空间为无限时， $M \to \infty$ ，这个上界趋向无穷大，不能有效描述偏差。

（2）VC 维度的引入

为解决无限假设空间问题，引入VC（Vapnik-Chervonenkis）维度，它衡量假设空间的复杂度，定义为假设空间可以打散的最大样本点数。

VC 维度的作用：
- 即使假设空间是无限的，但其复杂度可以通过 $d_{VC}$ 量化。
- 打散的点数越多，模型越复杂，训练误差与测试误差偏差越大。

（3）无限模型的泛化上界分析

在 VC 维度的基础上，训练误差与测试误差之间的偏差满足以下 VC 不等式：

$P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leq 4 \cdot \sum_{i=0}^{d_{VC}} \binom{2N}{i} \cdot e^{-\frac{1}{8}N\epsilon^2}$

i、上界的简化

当样本数 $N$ 足够大时，二项式项可以简化为最高项，得到：

$P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leq 4 \cdot (2N)^{d_{VC}} \cdot e^{-\frac{1}{8}N\epsilon^2}$

ii、含义分析

偏差的上界依赖于假设空间的复杂度（通过 $d_{VC}$ 表示）和样本数 $N$ 。
当假设空间复杂度 $d_{VC}$ 增加时，偏差上界变大，泛化能力变弱。
增加样本数 $N$ 可以有效减小偏差，但如果 $d_{VC}$ 过大，需要的样本量可能变得不可接受。

（4）无限模型的泛化能力分析

i、泛化误差的公式

最终的泛化误差由两部分组成：

$E_{\text{test}}(f^*) \leq E_{\text{train}}(f^*) + \Omega(d_{VC}, N, \delta)$

其中， $\Omega(d_{VC}, N, \delta)$ 称为模型复杂度项（这是模型复杂度项，并不是模型复杂度， $d_{VC}$ 才代表模型复杂度），定义为：

$\Omega(d_{VC}, N, \delta) = \sqrt{\frac{8}{N} \ln \left(\frac{4(2N)^{d_{VC}+ 1} }{\delta}\right)}$

ii、模型复杂度的影响

假设空间复杂度 $d_{VC}$ 越大，复杂度项 $\Omega$ 增加，泛化误差变大。
当训练样本数 $N$ 增加时，复杂度项 $\Omega$ 减小，但 $d_{VC}$ 过大可能需要极大的 $N$ 才能弥补。

iii、最优模型复杂度

综合考虑，存在一个最优的 $d_{VC}$ （假设空间的复杂度）使得测试误差最小：

$d_{VC}$ 过低，模型欠拟合；
$d_{VC}$ 过高，模型过拟合。

无限模型中，训练误差和测试误差的偏差必须通过复杂度控制项 $\Omega(d_{VC}, N, \delta)$ 来补偿。无限模型的训练误差与测试误差偏差主要取决于假设空间复杂度与样本数之间的平衡。

9、模型复杂度

模型复杂度与容忍度概念辨析见附录7

（1）模型复杂度与 “训练误差与测试误差偏差” 的关系

关键公式：

$E_{\text{train}}(f^*) - \Omega(d_{\text{vc}}, N, \delta) \leq E_{\text{test}}(f^*) \leq E_{\text{train}}(f^*) + \Omega(d_{\text{vc}}, N, \delta)$

其中， $\Omega(d_{VC}, N, \delta)$ 称为模型复杂度项（测试误差和训练误差之间的偏差上界 $\epsilon$ ，即容忍度），定义为：

$\Omega(d_{VC}, N, \delta) = \sqrt{\frac{8}{N} \ln \left(\frac{4(2N)^{d_{VC}+ 1} }{\delta}\right)}$

前边一般好像没什么用，训练误差本来就是小于测试误差的，再减去一个模型复杂度，就更小了，这个公式主要是后面一半。

（2）模型复杂度与 “训练误差与测试误差偏差” 的关系公式推导

10、样本复杂度

（1）定义

知道了容忍度 $\varepsilon$ ，则样本估计的公式为：

$N = \frac{8}{\varepsilon^2} \ln\left( \frac{4 (2N)^{d_{\text{vc}} + 1}}{\delta} \right)$

核心含义：这两个公式建立了模型复杂度（ $d_{\text{vc}}$ ）、训练样本数（ $N$ ）和误差容忍度（ $\varepsilon$ ）之间的关系。

（2）公式分析

误差上界（ $\varepsilon$ ）： $\varepsilon$ 表示测试误差和训练误差之间的最大允许偏差：
- 当样本量 $N$ 增加时，误差上界 $\varepsilon$ 减小，测试误差更接近训练误差。
- 当模型复杂度（VC 维度） $d_{\text{vc}}$ 增加时，误差上界 $\varepsilon$ 增大，表示更复杂的模型需要更多样本。
样本数需求（ $N$ ）：当我们设定误差容忍度 $\varepsilon$ 和置信水平 $1-\delta$ 后，可以通过公式2计算所需的样本量 $N$ ：
- 如果要求更高的置信度（更低的 $\delta$ ），需要更多样本。
- 如果希望误差更小（更低的 $\varepsilon$ ），也需要更多样本。

（3）实例分析

假设要求：

$\varepsilon = 0.1, \delta = 0.1, d_{\text{vc}} = 3$

通过代入公式，计算得到 $N \approx 30,000$ 。

如果 VC 维度提升为 $d_{\text{vc}} = 4$ ，则需要的样本数增加到 $N \approx 40,000$ 。

因此理论上来讲， $N\approx 10000d_{vc}$ 。但从实践上来讲 $N\approx 10d_{vc}$ 。

11、结构风险最小化

我们希望期望风险最小化

$R_{\text{exp}}(f) = \int L(f(x), y) p(x, y) dx dy$

期望风险是模型 $f(x)$ 在所有可能数据上的损失的数学期望。但在实际中，我们无法直接计算 $R_{\text{exp}}(f)$ ，因为数据的真实分布 $p(x, y)$ 是未知的。

机器学习中，只给定了训练样本，只能计算经验风险：

$R_{\text{emp}}(f) = \frac{1}{N} \sum_{i=1}^N L(f(x_i), y_i)$

经验风险是基于有限训练数据的平均损失。

经验风险最小化会产生过拟合 $\rightarrow$ 结构风险最小化：

$R_{\text{str}}(f) = R_{\text{emp}}(f) + \lambda R(f)$

结构风险在经验风险的基础上增加了正则化项 $\lambda R(f)$ ，其中：

$R(f)$ ：模型复杂度度量（例如模型的 VC 维度）。
$\lambda$ ：正则化系数，控制经验风险与模型复杂度之间的权衡。

泛化偏差公式：

$E_{\text{test}}(f^*) \leq E_{\text{train}}(f^*) + \Omega(d_{\text{vc}}, N, \delta)$

揭示了测试误差取决于训练误差和模型复杂度（以及样本量）的关系。

结构风险最小化（SRM）是期望在模型复杂度和训练误差之间找到一个最佳平衡，使模型具备更好的泛化能力。

12、模型评价

（1）奥卡姆剃刀原则（Occam's Razor）

核心思想: 简单的模型比复杂的模型更可取，前提是它们在解释数据上的表现差异不大。
- “如无必要，勿增实体”是奥卡姆剃刀原则的核心思想。
- 在机器学习中，选择假设时，优先考虑假设空间较小且解释力足够的模型。
为何重要:
- 复杂模型更容易出现过拟合，导致对未见数据表现较差。
- 简单模型往往有更好的泛化性能。
实例说明:
- 对同一数据，A模型较简单，B模型较复杂。尽管两者都很好地拟合了训练数据，但奥卡姆剃刀会偏向更简单的A模型。

（2）最小描述长度原则（MDL Principle）

核心思想: 模型的复杂度不仅体现在模型本身，还包括使用模型解释数据所需的描述长度。
- 描述长度公式： $K(f, D) = K(f) + K(D \, \text{using} \, f)$
- $K(f)$ : 模型的复杂度。
- $K(D \, \text{using} \, f)$ : 使用模型 $f$ 解释数据的长度。
理论意义:
- 数据量越大，模型复杂度的影响越小。
- 更倾向于简单模型，因为它能更好地平衡解释数据的能力与自身复杂度。
应用场景:
- 如果两个模型对数据的拟合程度相同，则选择描述长度最小的模型。

补充：

解释 $K(D \, \text{using} \, f)$ ：模型 $f$ 对数据 $D$ 的规律捕捉得不够好，则 $K(D \, \text{using} \, f)$ 的值会较大， $K(D \, \text{using} \, f)$ 越小，说明模型对数据的描述能力越强。

简单例子

假设有一组数据点 $D$ ，要用模型 $f$ 进行拟合：

模型 A（简单模型）：
- 例如线性回归模型，只需要几个参数（如斜率和截距）。
- $K(f)$ 小，因为模型复杂度低。
- 如果数据是线性分布，则 $K(D \, \text{using} \, f)$ 也很小。
模型 B（复杂模型）：
- 例如高次多项式模型，需要更多的参数来定义模型。
- $K(f)$ 大，因为模型复杂度高。
- 如果数据点是简单线性分布，复杂模型可能过拟合，导致 $K(D \, \text{using} \, f)$ 增加。

最终选择使 $K(f, D) = K(f) + K(D \, \text{using} \, f)$ 最小的模型。

（3）示例分析

训练数据下的A、B模型

初始数据点: A和B都能很好拟合训练数据，判断谁更优？

由训练数据可知：

模型A比模型B简单，即 $K_A(f)<K_B(f)$ ，

模型A和模型B都适用于数据点。即 $K_A(D \, \text{using} \, f)=K_B(D \, \text{using} \, f)$

所以 $K_A(f,D)<K_B(f,D)$ ，模型A更优。

增加测试数据1后的A、B模型

增加数据点后: A比B更能很好拟合训练数据，判断谁更优？

由训练数据可知：

模型A比模型B简单，即 $K_A(f)<K_B(f)$ ，

模型A和模型B都适用于数据点。即 $K_A(D \, \text{using} \, f)< K_B(D \, \text{using} \, f)$

所以 $K_A(f,D)<K_B(f,D)$ ，模型A更优。

增加测试数据2后的A、B模型

增加数据点后: B比A更能很好拟合训练数据，判断谁更优？

由训练数据可知：

模型A比模型B简单，即 $K_A(f)<K_B(f)$ ，

模型A和模型B都适用于数据点。即 $K_A(D \, \text{using} \, f) > K_B(D \, \text{using} \, f)$

衡量模型复杂度和模型对数据的适应程度对模型拟合性能的影响，在此显然后者对问题影响更大，所以 $K_A(f,D)> K_B(f,D)$ ，模型B更优。

（4）机器学习实践中的模型评价

理论与实践的差异:

理论上，训练误差可以反映模型好坏，但在实践中，测试误差才是评估模型是否真实有效的唯一标准。

数据划分:

训练集: 用于训练模型。
验证集: 用于选择模型，估计测试误差。
- 验证误差提供对模型泛化能力的无偏估计。
测试集: 用于评估模型性能，计算真实误差。

要点:

训练、验证、测试集相互独立，不重叠。
测试集代表模型未来可能遇到的数据，需谨慎使用，避免信息泄露。

13、例子：多项式拟合sin函数

（1）训练数据和模型函数

输入数据在[0,1]区间均匀采样10个点，输出为sin(2πx)加上高斯噪声。
模型使用的是多项式函数
$f(x, \mathbf{w}) = w_0 + w_1 x + w_2 x^2 + w_3 x^3 + \cdots + w_M x^M$ ，复杂度由多项式阶数M决定。

（2）欠拟合与过拟合

M=0 或 1 时，模型复杂度低，无法捕捉数据的规律，出现欠拟合。
M=9 时，多项式完全拟合训练数据，导致对噪声的过拟合，测试误差显著增加。

（3）训练误差和测试误差的曲线

随着模型复杂度增加，训练误差持续降低，但测试误差先减小后增加，这对应着模型从欠拟合到最佳拟合，再到过拟合的过程。

（4）数据量与模型复杂度的关系

数据量较小时，高复杂度模型容易过拟合。
数据量增加后，更复杂的模型也能获得较低的测试误差，因为更多的数据支持了复杂模型的泛化能力。

（5）正则化的作用

不同阶多项式拟合的系数

可见，随着 M 的增加，系数的绝对值增加当 M = 9时，对目标变量中的噪声也进行了很好地微调。

引入L2正则化（如 $\lambda \sum w_j^2$ ），通过惩罚过大的模型参数控制模型复杂度。

实验表明，适当的正则化可以显著降低测试误差，提高模型的泛化能力。

二、误差的偏差-方差分解

1、训练数据与目标函数

训练数据：

输入 $x$ 在区间 [0, 1] 上均匀采样 25 个点。
输出 $y = \sin(2\pi x) + \varepsilon$ ，其中噪声 $\varepsilon \sim \mathcal{N}(0, 0.3^2)$ 。

目标：

使用多项式拟合训练数据，模型假设空间为 M=25 阶的多项式。
使用结构风险最小化目标函数：

$J(f, \lambda) = \frac{1}{N} \sum_{i=1}^N (f(x_i) - y_i)^2 + \lambda \sum_{j=1}^M w_j^2$

其中，正则项通过超参数 $\lambda$ 控制模型复杂度。

改变 $\lambda$ 观察实验结果， $\lambda$ 在 $[10^{-6},10^{1}]$ 之间的log空间均匀采样40个点。

2、偏差与方差的概念

偏差（Bias）：

偏差衡量模型预测的期望与真实值之间的距离。
数学形式： $\text{Bias}^2 = (\mathbb{E}[\hat{y}_D] - y)^2$ 。
偏差体现了模型表达能力的不足，偏差大通常意味着欠拟合。

方差（Variance）：

方差反映了模型预测结果的波动性，即对训练数据变化的敏感度。
数学形式： $\text{Var} = \mathbb{E}[(\hat{y}_D - \mathbb{E}[\hat{y}_D])^2]$ 。
方差大通常意味着模型过拟合训练数据。

噪声：

噪声为不可避免的随机误差，记为 $\text{Noise} = \varepsilon^2$ 。

误差的偏差-方差分解： 总误差可以分解为三部分：

$\mathbb{E}[(\hat{y}_D - y)^2] = \text{Var}[\hat{y}_D] + \text{Bias}^2 + \text{Noise}$

推导：

$\mathbb{E}[(\hat{y}_D - y)^2] = \mathbb{E}[(\hat{y}_D - (y^* + \varepsilon))^2] ]$

$= \mathbb{E}[(\hat{y}_D - y^*)^2] + \mathbb{E}[\varepsilon^2] ]$

$= \mathbb{E}[(\hat{y}_D - \bar{y} + \bar{y} - y^*)^2] + \text{Var}[\varepsilon] ]$

$= \mathbb{E}[(\hat{y}_D - \bar{y})^2] + \mathbb{E}[(\bar{y} - y^*)^2] - 2\mathbb{E}[(\hat{y}_D - \bar{y})(\bar{y} - y^*)] + \text{Var}[\varepsilon]$

$= \text{Var}[\hat{y}_D] + (\bar{y} - y^*)^2 - 2(\bar{y} - y^*)\mathbb{E}[\hat{y}_D - \bar{y}] + \text{Var}[\varepsilon]$

$= \text{Var}[\hat{y}_D] + (\bar{y} - y^*)^2 - 2(\bar{y} - y^*)(\mathbb{E}[\hat{y}_D] - \bar{y} )+ \text{Var}[\varepsilon]$

$= \text{Var}[\hat{y}_D] + (\bar{y} - y^*)^2 + \text{Var}[\varepsilon]$

$= \text{Var}[\hat{y}_D] + \text{Bias}^2 + \text{Noise}$

3、正则化与模型复杂度的影响

正则化参数 $\lambda$ 控制模型复杂性：

较大的 $\lambda$ ：增加正则化，模型趋于简单，偏差增加，方差减小。
较小的 $\lambda$ ：减少正则化，模型趋于复杂，偏差减小，方差增加。

偏差-方差权衡：

简单模型：高偏差、低方差（欠拟合）。
复杂模型：低偏差、高方差（过拟合）。
最优模型：在偏差和方差之间取得平衡，提供最优的泛化能力。

4、实验观察

偏差-方差关系：

在实验中通过多次采样训练集，对不同复杂度模型进行拟合，观察训练误差和测试误差。
当 $\lambda$ 较小时，训练误差较低但测试误差较高，表明过拟合。
当 $\lambda$ 较大时，测试误差和训练误差都较高，表明欠拟合。
最优点对应于偏差与方差达到最佳权衡的 $\lambda$ 值。

图形分析：

在不同正则参数 $\lambda$ 下绘制偏差、方差和总误差。可以看到偏差和方差呈现相反的趋势，总误差曲线有一个最小点。

5、偏差-方差权衡的实际意义

深刻理解模型复杂度：

高复杂度的模型可能具有较低的偏差但方差较高，表现为过拟合。
简单的模型可能具有较高的偏差但方差较低，表现为欠拟合。

实际限制：

偏差和方差无法直接计算，因为它们依赖于数据分布的真实情况。
偏差-方差分解仅对数据集的均值有效，而实际中我们通常只有单个观察数据集。

三、学习曲线

1、学习曲线

定义与目标

学习曲线通过展示训练集大小对模型在训练集和验证集上的性能影响，帮助我们判断模型的拟合状态（欠拟合或过拟合）及诊断模型的偏差和方差问题。

表现形式

横轴：训练集样本数量。
纵轴：模型性能指标（如精度、误差等）。
训练曲线显示训练集上的性能，验证曲线显示验证集上的性能。

2、学习曲线的分析和意义

训练误差与验证误差趋势：

随着训练集增大，训练误差通常会升高，而验证误差会降低。
当数据量足够大时，两者趋于平稳。

偏差和方差的可视化：

验证误差和训练误差之间的差异（验证误差 - 训练误差）可以反映模型的方差。
验证误差和目标误差（最优性能之间的差距）可以反映模型的偏差。

如下图所示，随机森林方差大、线性模型方差小；随机森林偏差小、线性模型偏差大。说明随机森林更能拟合训练集数据，随机森林的模型复杂度更大，但随机森林更容易过拟合。

不同模型区域稳定的样本集合大小不同：

简单模型通常需要更少的数据来达到稳定状态，而复杂模型需要更多数据。

3、从学习曲线判断过拟合、欠拟合（欠拟合和过拟合的外在表现）

（1）欠拟合图示

验证集和训练集的误差值都很大，偏差大，此时为欠拟合。（高偏差）

（2）过拟合图示

训练集误差非常小，但验证集误差远大于训练集误差，此时为过拟合。（高方差）

（3）好的模型图示

（4）模型复杂度与训练误差、验证误差的关系

训练误差随着模型复杂度增加一直减小。

验证误差随着模型复杂度的变化先减小（欠拟合程度减轻）；当模型复杂度超过一定值后，验证误差随模型复杂度增加而增大，此时模型进入过拟合状态。

（5）欠拟合与过拟合的解决方法

欠拟合（高偏差）：

表现：训练误差和验证误差均较高，验证集和训练集的性能相差不大。
改进方向：
- 增加模型复杂度（更灵活的假设空间）。
- 增加模型的迭代次数（训练更充分）。
- 引入更多特征。

过拟合（高方差）：

表现：训练误差极低，但验证误差明显高于训练误差。
改进方向：
- 降低模型复杂度。
- 使用正则化（如L1/L2正则化、Dropout）。
- 增加训练数据。

四、⭐⭐全文总结⭐⭐

本文第一部分介绍结构风险最小化，也就是期望风险最小化，但期望风险公式中的 $p(x,y)$ 是基于全集的，是不知道的，无法计算。只能通过训练样本近似期望风险，即只能经验风险来近似期望风险。数据集毕竟不是全集，由此带来的过拟合问题是算法需要关注的最关键的点。

文中通过Hoeffding不等式量化了训练误差与测试误差之间的偏差（1.6），但这种量化只适用于有限的假设空间，对于无限假设空间，不能使用Hoeffding不等式。要将假设空间的复杂度（如VC维）引入到不等式中，从而得到无限假设空间下的训练误差与测试误差之间的偏差。文中还介绍了（1.9）通过模型复杂度 $d_{VC}$ ，样本数量（N），置信度（ $1-\delta$ ）来表示测试误差与训练误差的关系。同样还建立了（1.10）模型复杂度（ $d_{\text{vc}}$ ）、训练样本数（ $N$ ）和误差容忍度（ $\varepsilon$ ）之间的关系，从而估计使用某种模型达到某种误差容忍度所需的最小样本数。（1.12）中介绍了最小描述长度原则（MDL），说明模型选择要根据模型复杂度和模型对数据的适应程度两个因素来决定。

第二部分介绍了误差的偏差方差分解，影响偏差的主要因素是模型的种类以及是否欠拟合，不同的模型完全稳定时偏差不同，欠拟合的程度越高，偏差越大；影响方差的主要因素是模型的过拟合程度，过拟合程度越大，方差越大。

第三部分介绍了学习曲线，学习曲线的核心是训练集数量对模型性能（训练集误差，测试集误差）的影响。介绍了方差偏差在学习曲线中的体现，介绍了欠拟合过拟合在学校曲线中的体现。最后还介绍了解决欠拟合过拟合的方法。

附录

1、经验风险与结构风险

经验风险

经验风险是模型在训练数据集上的平均损失，反映了模型对已知数据的拟合能力。

数学形式为： $R_{\text{emp}}(f) = \frac{1}{N} \sum_{i=1}^N L(f(x_i), y_i)$

$f(x)$ ：模型预测函数。
$L(f(x), y)$ ：损失函数，衡量模型预测值与真实值的差距（如平方损失、0-1损失）。
$(x_i, y_i)$ ：训练集中的样本对。
$N$ ：训练样本数量。

通过优化模型参数，使经验风险最小化。这一过程称为经验风险最小化，经验风险的最小化并不保证模型泛化性能良好。只考虑训练集上的损失，容易导致过拟合。过拟合的模型虽然能极好地拟合训练数据，但在测试数据上的表现可能较差。

结构风险

结构风险在经验风险的基础上，加入了对模型复杂度的惩罚项，用于平衡模型的拟合能力和复杂度，目的是防止过拟合。

数学形式为： $R_{\text{struct}}(f) = R_{\text{emp}}(f) + \lambda \cdot \Omega(f)$

$R_{\text{emp}}(f)$ ：经验风险。
$\Omega(f)$ ：模型复杂度度量（正则化项），如模型的参数个数、参数的范数、VC维等。
$\lambda$ ：正则化系数，控制经验风险与模型复杂度之间的权衡。

结构风险综合了模型对训练数据的拟合能力（经验风险）和模型复杂性。通过优化结构风险，选择既能拟合训练数据又不太复杂的模型。通过引入复杂度惩罚，结构风险最小化有效避免了过拟合问题。更加注重模型的泛化能力。

2、期望风险

（1）期望风险定义

期望风险是模型在真实数据分布（总体数据）上的平均损失。

$R_{\text{exp}}(f) = \mathbb{E}_{(x, y) \sim p(x, y)}[L(f(x), y)] = \int L(f(x), y) p(x, y) dx dy$

$L(f(x), y)$ ：损失函数，用来衡量预测值 $f(x)$ 和真实标签 $y$ 的差异。
$p(x, y)$ ：数据分布。

$R_{\text{exp}}(f)$ 是衡量模型性能的“黄金标准”，直接反映模型在数据分布上的表现。数据分布 $p(x, y)$ 通常是未知的，因此 $R_{\text{exp}}(f)$ 无法直接求解。当每个样本都是独立的时候， $p(x, y)=\frac{1}{N}$ ，N为总体样本数量，期望风险的公式变为：

$R_{\text{exp}}(f) = \mathbb{E}_{(x, y) \sim p(x, y)}[L(f(x), y)] =\frac{1}{N} \sum_{i=1}^N L(f(x_i), y_i)$

优化目标：理想情况下，我们希望找到一个模型 $f^*$ ，使得期望风险最小化：

$f^* = \arg\min_{f} R_{\text{exp}}(f)$

（2）期望风险、经验风险、结构风险的关系

经验风险 $R_{\text{emp}}(f)$ 是期望风险的近似值，在训练样本量足够大时，可以逼近期望风险。

期望风险是机器学习的理论目标，但由于数据分布未知，无法直接优化。

经验风险是对期望风险的近似，基于有限训练数据进行优化，但容易过拟合。

结构风险通过在经验风险上加入正则化，限制模型复杂度，从而提高泛化能力。在实际问题中，结构风险最小化是最常用的策略。

3、条件风险

条件风险是指在给定某一个具体输入 $x$ 时，模型预测值和真实值之间的期望损失。它是期望风险的一个局部化描述，专注于特定输入 $x$ 的情况下，模型预测的表现。

条件风险的数学定义为：

$R(f(x) | x) = \mathbb{E}[L(f(x), y) | x] = \int L(f(x), y) p(y | x) \, dy$

其中：

$f(x)$ ：模型对输入 $x$ 的预测；
$L(f(x), y)$ ：损失函数，衡量预测值 $f(x)$ 与真实值 $y$ 的差距；
$p(y | x)$ ：在给定输入 $x$ 时，输出 $y$ 的条件概率分布。

局部化分析：条件风险描述了在输入 $x$ 处，模型预测表现的平均损失。

优化目标：在给定 $x$ 的情况下，找到使条件风险最小的预测值 $f(x)$ ，这就是统计学习中的最优决策。

与期望风险的关系：期望风险是对所有输入 $x$ 的条件风险的加权平均：

$R(f) = \mathbb{E}_x[R(f(x)|x)] = \int R(f(x)|x) p(x) dx$

4、有限个模型的机器学习和无限个模型的机器学习

有限个模型和无限个模型的机器学习的本质区别可以归结为以下几个方面：

（1）假设空间的规模

本质：模型集合（假设空间）的规模影响了学习的表达能力和复杂度控制方式。

有限模型的机器学习：
- 假设空间包含有限个候选模型，可以枚举这些模型。
- 优点：假设空间小，计算开销低，过拟合风险较低。
- 缺点：表达能力受限，可能无法很好地拟合复杂的模式。
无限模型的机器学习：
- 假设空间包含无穷多个模型，通常由连续参数（如实数参数的模型）定义。
- 优点：假设空间大，表达能力强，可以拟合复杂的模式。
- 缺点：容易过拟合，训练难度高，需要额外的正则化或约束控制。

（2）泛化能力的来源

本质：有限模型与无限模型在泛化能力上的保障方式不同。

有限模型的泛化：
- 泛化能力主要依赖于假设空间的“有限性”，即较小的模型数量限制了模型复杂度，从而降低了过拟合的可能性。
- 理论分析简单。例如，Hoeffding 不等式可以用于分析训练误差与测试误差之间的偏差。
无限模型的泛化：
- 泛化能力来自于正则化或模型选择等手段，而不是假设空间的有限性。
- 需要更复杂的理论分析工具（如 VC 维、Rademacher 复杂度）来量化模型复杂度和泛化误差。
- 例如，在深度学习中，通过 Dropout、L2 正则化、早停等技术控制模型复杂度，从而提升泛化能力。

（3）表达能力的限制

本质：假设空间的规模决定了模型的表达能力（能否拟合复杂的数据分布）。

有限模型的表达能力：
- 假设空间受限，可能无法很好地表示复杂的模式。
- 适合简单问题或小数据集。例如：
  - 使用简单规则分类“猫”和“狗”（耳朵特征、尾巴特征）。
  - 低维线性回归。
无限模型的表达能力：
- 假设空间大，能够拟合任意复杂的分布，但需要适当约束避免过拟合。
- 适合复杂问题和大数据集。例如：
  - 深度神经网络可以学习图像、语音中的复杂模式。
  - 支持向量机（核函数）在无限维特征空间中分类。

（4）泛化风险的控制方法

本质：两种模型在泛化风险（训练误差与测试误差的偏差）的控制方式不同。

有限模型：

泛化风险由假设空间的大小控制。
对于个模型，根据 Hoeffding 不等式，可以得出坏模型（训练误差与测试误差偏差大的模型）出现的概率界限： (坏模型)
- 假设空间的大小 $M$ 增大会增加坏模型的概率。
- 样本数量 $N$ 增大可以有效降低偏差概率。

无限模型：
- 泛化风险通过正则化或模型复杂度约束控制。
- 需要通过限制模型的 VC 维或使用 Rademacher 复杂度等理论，分析模型复杂度与样本数量的关系，从而确保泛化能力。
- 样本数量不足时，假设空间的无限性可能导致严重的过拟合。

（5）总结

有限与无限模型学习的本质区别

特性	有限模型学习	无限模型学习
假设空间	有限个假设（模型数量 M 是有限值）	无限个假设（如参数化模型）
错误概率分析	利用 Hoeffding 不等式，训练误差与测试误差的偏差概率可以被有效估计	简单联合概率界限失效，需要引入更高级工具
泛化能力	样本数足够大时，训练误差与测试误差接近	需要正则化、约束等手段控制模型复杂性，保证泛化能力
模型表达能力	受限于假设空间大小	无限假设空间具有更强的表达能力
理论分析工具	Hoeffding 不等式	需要引入 VC 维、Rademacher 复杂度等

5、假设空间是什么

（1）什么是假设空间

假设空间（Hypothesis Space） 是机器学习模型从数据中寻找最优解的候选解集合，也就是所有可能的模型或函数的集合。
假设空间定义了模型可以表示的所有可能的输入-输出关系。

（2）形式化的定义

假设空间通常记为 $\mathcal{H}$ ，其中每个假设 $h \in \mathcal{H}$ 是一个函数，用于映射输入 $x$ 到输出 $y$ ： $h: \mathcal{X} \to \mathcal{Y}$

$\mathcal{X}$ ：输入空间（所有可能的输入值）。
$\mathcal{Y}$ ：输出空间（所有可能的输出值）。
$\mathcal{H}$ ：所有可能的假设函数集合。

（3）假设空间的来源

假设空间由以下因素决定：

模型的类型

不同类型的模型有不同的假设空间：
- 线性回归：假设空间是所有线性函数集合。
- 决策树：假设空间是所有可能的树结构（分裂规则）。
- 支持向量机：假设空间是所有可能的超平面集合。

模型的参数

假设空间的大小与模型参数的自由度相关：
- 有限假设空间：参数的取值是离散或有限的（例如，决策树的最大深度有限）。
- 无限假设空间：参数是连续的，假设空间的大小趋于无穷（例如，线性回归中的权重为实数）。

约束条件

对假设空间施加约束会缩小它的大小。例如：
- 正则化（如 L2 范数）限制了模型参数的大小，减少了假设空间的自由度。
- 在神经网络中，限制网络层数和节点数等超参数会减少假设空间的规模。

（4）假设空间的作用

学习的目标：

机器学习的目标是在假设空间 $\mathcal{H}$ 中找到一个“最优假设” $h^*$ ，使得它在训练数据上表现良好，并且能够泛化到测试数据。训练模型的过程就是优化参数的过程，其实就是在假设空间中寻找最优假设。

如果假设空间太小，可能无法找到足够好的假设（欠拟合）。
如果假设空间太大，可能找到的假设只适用于训练数据，而不适用于测试数据（过拟合）。

泛化能力的关键：

假设空间的大小和复杂度会直接影响模型的泛化能力：

小假设空间：容易欠拟合，因为假设空间可能无法包含真实的目标函数。
大假设空间：容易过拟合，因为假设空间可能过于灵活，拟合训练数据中的噪声。

（5）假设空间的选择

选择假设空间的原则：

任务复杂度：选择能够表示任务目标函数的假设空间。

简单任务：选择较小的假设空间（例如线性模型）。
复杂任务：选择较大的假设空间（例如深度神经网络）。

数据量：假设空间的大小应与数据量匹配。

数据少：选择较小的假设空间以避免过拟合。
数据多：可以选择较大的假设空间。

正则化：通过正则化控制假设空间的有效规模，防止过拟合。

（6）举例说明

线性模型的假设空间

假设输入是二维向量 $x = (x_1, x_2)$ ，输出是实数 $y \in \mathbb{R}$ 。
使用线性回归模型：
- 假设空间 $\mathcal{H}$ ：所有可能的线性函数集合。
- $\mathcal{H}$ 的大小由权重 $w_1, w_2$ 和偏置 $b$ 的取值范围决定。如果 $w_1, w_2, b$ 是连续值，则假设空间是无限的。

决策树的假设空间

假设输入是二分类问题的特征 $x \in \{0, 1\}^3$ 。
决策树模型：
- 如果深度限制为 2，则假设空间包括所有深度为 2 的决策树。
- 假设空间的大小是有限的，因为有限的特征和深度限制了可能的树结构数量。

神经网络的假设空间

假设使用一个 3 层的神经网络，每层有 10 个神经元。
假设空间是所有可能的网络权重组合生成的函数集合：
- 如果权重是连续值，则假设空间是无限的。
- 如果权重的值被量化为离散值（例如，整数），则假设空间是有限的。

6、关键问题二的详细分析

该问题为：为什么假设空间中的训练误差最小的假设 $f^{*}$ 不能通过 Hoeffding 不等式来确定其训练误差和测试误差之间的差距概率的上界呢？

（1）Hoeffding 不等式的前提条件

Hoeffding 不等式用于描述独立随机变量的和的偏差，其前提是：

假设我们有固定的 $f$ （即函数 $f$ 是预先确定的，而不是通过数据选择的）。
训练误差 $E_{\text{train}}(f)$ 和测试误差 $E_{\text{test}}(f)$ 是随机变量，且其差距依赖于数据分布。

公式为：

$P(|E_{\text{train}}(f) - E_{\text{test}}(f)| \geq \epsilon) \leq 2 e^{-2N\epsilon^2}$

其中 $N$ 是样本数量。

但这依赖于 $f^*$ 是固定的。而 $f^*$ 并不是固定的，它是从候选模型集中选择出来的，且选择过程依赖于训练数据。

（2）f* 的选择改变了性质

当我们在候选集 $\{f_1, f_2, \ldots, f_M\}$ 中选择了 $f^*$ ，这个选择过程本身会增加 $f^*$ 偏离 Hoeffding 不等式条件的风险。原因如下：

i、 $f^*$ 是训练数据的函数

$f^*$ 是通过最小化训练误差 $E_{\text{train}}$ 选出来的，即： $f^* = \arg\min_{f \in \{f_1, f_2, \ldots, f_M\}} E_{\text{train}}(f)$
因此， $f^*$ 的选择依赖于训练数据。这意味着：
- $f^*$ 并不是一个固定的函数；
- 它的训练误差 $E_{\text{train}}(f^*)$ 是训练数据的结果，而不是独立于训练数据的量。

ii、Hoeffding 不等式的前提被破坏

Hoeffding 不等式假设 $E_{\text{train}}(f)$ 和 $E_{\text{test}}(f)$ 的关系只由随机采样引入的差异决定。
但在选择 $f^*$ 的过程中，我们已经特意挑选了训练误差最小的模型，这种挑选过程破坏了 Hoeffding 不等式的独立性假设。

iii、“挑选的最优”可能放大偏差

从 $M$ 个候选模型中挑选 $f^*$ ，会自然放大 $E_{\text{train}}(f^*)$ 和 $E_{\text{test}}(f^*)$ 之间的偏差，因为 $f^*$ 更可能是过拟合的结果（即，它在训练集上表现得极好，但在测试集上表现较差）。
因此，直接对 $f^*$ 使用 Hoeffding 不等式会低估这种偏差。

（3）使用 Hoeffding 不等式的替代方法

为了弥补直接对 $f^*$ 使用 Hoeffding 不等式的问题，统计学习理论提出了改进的方法，将模型选择过程引入不等式的分析中。关键思想是：

i、处理联合事件

不再只看 $P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon)$ ，而是分析整个候选集的联合事件： $P(\exists f \in \{f_1, f_2, \ldots, f_M\}, |E_{\text{train}}(f) - E_{\text{test}}(f)| \geq \epsilon)$
使用 Hoeffding 不等式估计每个模型的训练误差和测试误差差距的上界，然后通过联合概率性质（如联合概率的上界为单个事件概率之和）来处理整个假设空间。

ii、引入假设空间复杂度（如 VC 维度）

假设空间的复杂度越大（候选模型数量 $M$ 越多或模型越复杂），训练误差和测试误差之间的差距可能越大。
因此，我们需要引入额外的复杂度惩罚项来控制这种偏差。这就是结构风险最小化（Structural Risk Minimization, SRM）中的核心思想。

iii、Hoeffding 不等式的修正版本（本文“有限个模型的机器学习中的训练误差与测试误差的偏差分析”就是将候选模型数量 $M$ 引入到不等式中）

通过将假设空间的复杂度（如候选模型数量 $M$ 或 VC 维度）引入到不等式中，我们可以得出更合理的上界。例如：

$P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leq M \cdot e^{-2N\epsilon^2}$

或者：

$P(|E_{\text{train}}(f^*) - E_{\text{test}}(f^*)| \geq \epsilon) \leq 4 \cdot (2N)^{d_{VC}} \cdot e^{-N\epsilon^2}$

这反映了假设空间复杂度对泛化误差的影响。

7、模型复杂度与容忍度概念辨析

（1）模型复杂度

定义：模型复杂度通常用 VC 维度 $d_{\text{vc}}$  来表示。它是衡量一个假设空间（模型族）能适配数据复杂程度的指标。

影响：

模型复杂度越高，表示模型可以表达的函数形式越多，拟合能力更强。
如果模型太复杂而数据量不足，容易导致过拟合，即在训练数据上表现很好，但在测试数据上表现较差。
模型复杂度通过 VC 不等式影响测试误差的理论上界。

在公式中体现：在测试误差和训练误差偏差公式中，模型复杂度以 $d_{\text{vc}}$ 的形式出现：

$\Omega(d_{\text{vc}}, N, \delta) = \sqrt{\frac{8}{N} \ln\left( \frac{4(2N)^{d_{\text{vc}} + 1}}{\delta} \right)}$

其中 $\Omega(d_{\text{vc}}, N, \delta)$ 是“偏差上界”的一部分，它与 $d_{\text{vc}}$ 成正相关。

（2）容忍度（测试误差与训练误差之间的偏差上界）

定义：容忍度（测试误差和训练误差之间的偏差上界）表示模型的泛化误差范围。它是一个数值，描述了测试误差和训练误差的最大可能偏差。

公式：通过理论推导，容忍度 $\varepsilon$ 的公式为：

$\varepsilon = \sqrt{\frac{8}{N} \ln\left( \frac{4(2N)^{d_{\text{vc}} + 1}}{\delta} \right)}$

其中：

$\varepsilon$ ：容忍度。
$N$ ：训练样本数量。
$d_{\text{vc}}$ ：模型复杂度。
$\delta$ ：置信参数。

影响：

容忍度描述了在一定概率（ $1-\delta$ ）下，训练误差和测试误差之间偏差不会超过的值。
容忍度越小，表示测试误差更接近训练误差，泛化性能更好。

（3）二者的联系

关联性：容忍度 $\varepsilon$ 是由模型复杂度 $d_{\text{vc}}$ 、样本量 $N$ 、置信参数 $\delta$ 决定的：

$\varepsilon = \Omega(d_{\text{vc}}, N, \delta)$

当模型复杂度 $d_{\text{vc}}$ 增大时，容忍度 $\varepsilon$ 也会增大。这是因为更复杂的模型容易过拟合，测试误差和训练误差的偏差更大。
当样本量 $N$ 增加时，容忍度 $\varepsilon$ 减小，训练误差更能代表测试误差。
当置信参数 $\delta$ 减小时，容忍度 $\varepsilon$ 也会增大，因为需要更高的置信水平。