Rademacher 复杂性

Rademacher 复杂性是对假设空间H能够适应随机噪音能力的度量，衡量一个假设空间能够在多大程度上拟合随机标签的能力，反映了假设空间的复杂度，越复杂的空间，拟合噪声的能力就越强，误差上界越大

Define

Rademacher 变量：

• 独立同分布，取值为 +1或-1，概率为1/2

假设我们有一个假设空间 $\mathcal{H}$ 和一个数据集 $S=\{x_1,x_2,...,x_m\}$，Rademacher 复杂性定义如下：

$${\mathcal{R}}_S(\mathcal{H})={\mathbb{E}}_{\sigma }\left[\underset{h\in \mathcal{H}}{\sup }\frac{1}{m}\sum _{i=1}^m{\sigma }_{i}h(x_i)\right]$$

这里：

• ${\sigma }_i$ 是 Rademacher 变量，用来为每个样本随机分配一个 +1 或 -1 标签。
• $h(x_i)$是假设 $h$ 在样本 $x_i$上的预测结果。
• 这个表达式衡量的是假设空间$\mathcal{H}$在拟合随机标签 $\sigma$上的能力。取上界表示假设空间中表现最好的那个假设 $h$，即对随机标签拟合最好

Rademacher 复杂性提供了一个数据集上的度量，用来评估假设空间在给定数据上的适应性。它与模型的容量和复杂性密切相关。

泛化误差上界

基于 Rademacher 复杂性，我们可以得到模型的 泛化误差上界。具体地，假设我们有一个训练数据集$S=\{x_1,x_2,...,x_m\}$，并且我们希望用假设 $h\in \mathcal{H}$ 来估计其泛化误差 $L(h)$ ，定义如下：

• 真实误差（泛化误差）：$L(h)={\mathbb{E}}_{(x,y)\sim D}[\ell (h(x),y)]$，表示假设 $h$ 在分布 $D$ 上的期望损失。
• 经验误差（训练误差）： ${\hat{L}}_S(h)=\frac{1}{m}{\sum }_{i=1}^m\ell (h(x_i),y_i)$ ，表示假设 $h$ 在训练集上的平均损失。

Rademacher 复杂性将这两个误差联系起来，给出泛化误差的上界。通常的形式如下：

$$L(h)\le {\hat{L}}_S(h)+2{\mathcal{R}}_S(\mathcal{H})+\mathcal{O}\left(\frac{1}{\sqrt{m}}\right)$$

其中：

• $L(h)$ 是模型 $h$ 的泛化误差。
• ${\hat{L}}_S(h)$ 是模型 $h$ 的经验误差。
• ${\mathcal{R}}_S(\mathcal{H})$ 是假设空间$\mathcal{H}$ 的 Rademacher 复杂性。
• $\mathcal{O}(1/\sqrt{m})$是一个与样本量 $m$ 有关的修正项，表示误差收敛速度。

该公式表明：

1. 模型的 泛化误差 $L(h)$ 由 经验误差 ${\hat{L}}_S(h)$和 Rademacher 复杂性控制。
2. Rademacher 复杂性越小，模型的泛化误差越接近训练误差。因此，具有较小 Rademacher 复杂性的假设空间能够更好地泛化。
3. 当样本量$m$足够大时，误差上界会收敛到实际的泛化误差。

解释

1. 经验误差 是模型在训练集上的误差，它反映了模型对训练数据的拟合程度。
2. Rademacher 复杂性 则反映了模型假设空间的容量和拟合随机噪声的能力。复杂性越大，意味着模型越有可能过拟合，从而导致泛化误差增大。
3. 泛化误差上界 是训练误差和 Rademacher 复杂性之和。当假设空间的复杂性增大时，模型虽然在训练集上表现更好，但泛化能力会受到限制，容易过拟合。

应用与意义

• Rademacher 复杂性可以帮助我们选择合适的模型：选择一个具有较小 Rademacher 复杂性的模型可以避免过拟合，提升泛化能力。
• 在实际问题中，计算 Rademacher 复杂性有助于理解模型的复杂度、容量以及如何有效地在数据上进行拟合。
• 对于深度学习等复杂模型，尽管理论上很难精确计算 Rademacher 复杂性，但它依然提供了一个衡量模型过拟合风险的工具。