机器学习希望最小化模型的期望（泛化）误差$L$，即模型在整个数据分布上的平均误差。然而我们只能在训练集上最小化经验误差$\hat{L}$，我们期望通过最小化经验误差来最小化泛化误差。但是训练数据和数据真实分布之间是有差异的，又根据奥卡姆剃刀原理，在训练误差相同的情况下，模型复杂度越小，泛化性能越好，因此一些理论提出使用经验误差和模型复杂度来定义模型期望误差的上界。通常表示为以下形式：

$\displaystyle L \leq \hat{L}+\mathcal{O}\left(\sqrt{\frac{Complexity}{n}}\right)$

$\displaystyle \mathop{E}\limits_{x,y\sim \mathfrak{B}}L(g(x),y) \leq \sum\limits_{i=1}^n L(g(x_i),y_i)+\mathcal{O}\left(\sqrt{\frac{G_{Complex}}{n}}\right)$

　　其中$n$表示训练数据量，$g$表示拟合完后的模型，$G$表示$g$的假设类（优化空间），$g\in G$，$G_{Complex}$表示假设类的复杂度。这些不等式的主要区别在于对模型复杂度的量化，即不等式右边第二项。

VC维

　　VC维表示模型一定可以完美拟合的最大数据量，一定程度上度量了模型的表示能力。比如对于二维线性模型$f(x) =\sigma( w_1x_1+w_2x_2+b)$，其VC维为3。可以很容易判断在二维空间中任意的三个点都是线性可分的，从而$f(x)$可以完美划分拟合。而对于4个点，出现异或的情况时，二维线性模型就不能划分了。

　　对于VC维为$h$的模型（假设类、优化空间），期望误差上界为

$\displaystyle L \leq \hat{L}+\sqrt{\frac{h(\log(2N/h)+1)-\log(\eta/4)}{N}}$

　　其中右侧称为风险边界，其中$\eta$为置信度，取值$(0,1]$。不等式成立的概率为$1-\eta$。

　　参考：

　　https://blog.csdn.net/qq_43391414/article/details/111692672

　　https://zhuanlan.zhihu.com/p/94480190

Rademacher复杂度

　　Rademacher复杂度是一种衡量模型复杂度的度量，特别是在处理大样本限定的统计学习中。对于一个数据集，Rademacher复杂度被定义为随机分配标签后，模型能够拟合这些随机标签的能力。直观上看，如果一个模型可以很好地拟合随机的噪声，那么它可能过于复杂，有过拟合的风险。相较于VC维，Rademacher复杂度与数据相关，因此最终得到的bound更紧，对于调节模型复杂度具有更强的指导意义。

　　对于一个给定的假设类（例如某个待优化的线性模型，或所有的深度为2的决策树），和给定的数据集大小$n$，我们可以计算假设类的Rademacher复杂度。为了计算Rademacher复杂度，我们随机分配标签给数据集，然后找到在这个随机标签数据集上误差最小的假设，计算这个假设在这个随机标签数据集上的正确率。重复这一过程多次，平均得到的所有正确率。则这个平均正确率就是假设类的Rademacher复杂度。

　　比如对于包含$n$个训练样本的二分类任务，假设类为$G$，其Rademacher复杂度$\mathfrak{R}_n(G)$表示为：

$\displaystyle\mathfrak{R}_n(G)=\mathop{E}\limits_\sigma\left[\sup_{g\in G}\frac{1}{n}\sum_{i=1}^n \sigma_ig(x_i)\right]$

　　其中随机数据集标签$\sigma$服从在$\{-1,+1\}^n$上的均匀分布。

　　则期望误差上界为：

$\displaystyle L\leq\hat{L}+2\mathfrak{R}_n(G)+\sqrt{\frac{\log\frac{1}{\delta}}{2n}}$

$\displaystyle L\leq\hat{L}+2\mathfrak{R}_n(G)+3\sqrt{\frac{\log\frac{2}{\delta}}{2n}}$

　　以上两个不等式同时在$1-\delta$的概率下成立。

　　参考：

　　ChatGPT 4.0

　　https://www.zhihu.com/question/264208923

　　https://zhuanlan.zhihu.com/p/337298338