主页
个人中心
公开课
偶是大橘子哇
预计阅读时间：7分钟57秒

掌握Bias-Variance平衡：VC 维与泛化界的实证研究

模型复杂度与数据规模如何影响机器学习中的泛化性能，及如何评估与实践

0
0

本文原作者：Kuriko Iwai，喜欢原作者的文章可以访问博客，点击这里


引言

偏差-方差权衡是监督式机器学习中的核心挑战。


Vapnik–Chervonenkis（VC）维度提供了一种理论规则，用于估计模型在未见数据上的表现能力，这对于高效应对这一挑战至关重要。

在本文中，我将通过实证方式评估 VC 维度、VC 界以及不同模型泛化能力之间的关系，并在合成数据集上测量它们的泛化误差。


打散（Shattering）的机制：VC 维度的定义


Vapnik–Chervonenkis（VC）维度是机器学习中的一个基础概念，它通过理论方式量化模型在任意标注方式下能够被完全正确分类的数据点数量，从而衡量统计分类模型的容量。


下图通过一个二维平面上的线性分类器对三个数据点进行“打散”来说明这一概念：二维平面上线性分类器打散三个点，以说明 VC 维度的容量。

image.png

图 A：二维平面上线性分类器的 VC 维度


“模型打散了一组三个点”，意味着无论标签如何分配（例如图 A 中显示的红色或蓝色标签），模型都可以以零误差对其进行完美分类。

因此，我们可以得出结论：该分类器的 VC 维度为 3。


模型复杂度与偏差-方差权衡

VC 维度通过定义泛化界，提供了一个形式化的模型容量度量，用以预测模型在未见数据上的表现能力：

  • 低 VC 维度：简单模型（例如线性分类器）具有较低的泛化界。它们捕捉复杂数据结构的能力有限。
  • 高 VC 维度：复杂模型（例如深度神经网络）具有较高的 VC 维度。它们能够学习高度复杂的模式，但也更容易记住数据中的噪声。


模型性能的衡量：误差分解

在监督学习中，关键在于评估模型是否真正学到了数据背后的规律，还是仅仅记住了训练数据集。

下图展示了模型评估过程以及三种示例结果：


误差分解图：通过 Bayes 误差、训练误差与验证误差之间的差距来定义偏差与方差。
image.png

图 B：训练、验证与测试阶段的误差分解（由 Kuriko IWAI 创建）


首先，原始数据被划分为三个集合：

  • 训练集：用于学习模式
  • 验证集：用于调节超参数并模拟真实世界表现
  • 测试集：作为最终的未见数据基准

然后，研究者分析不同误差率之间的差距：

  • 可避免偏差（或偏差）：训练误差与 Bayes 误差（理论上的最小误差率，即人类误差率）之间的差距。高偏差意味着模型过于简单，无法理解数据。
  • 方差：训练误差与验证误差之间的差距。该差距估计泛化误差。高方差意味着模型未能有效地将所学知识迁移到新数据上。

欠拟合与过拟合

偏差与方差之间的关系定义了机器学习中最常见的两种问题。

▫ 1. 欠拟合（高偏差，低方差）

当模型过于简单，无法表示数据的潜在结构时，就会发生欠拟合。

  • 情形：模型未能捕捉数据中的“信号”。
  • 可能原因：模型复杂度不足；缺乏高质量特征。
  • 结果：高偏差，低方差；训练误差和验证误差都很高。

在图 B 中，一个简单模型产生了高达 14 个点的偏差和 1 个点的低方差，因为该模型对训练集来说过于简单，几乎没有从中学习到任何东西。


过拟合（低偏差，高方差）

当复杂模型过度学习训练数据（包括其中的噪声和随机波动）时，就会发生过拟合。

  • 情形：模型记住了具体的训练样本，而不是学习可泛化的规则。
  • 可能原因：相对于数据量而言模型过于复杂；训练迭代次数过多。
  • 结果：低偏差，高方差。

在图 B 中，一个复杂模型实现了接近 0 的低偏差，但产生了 15 个点的高方差，因为该模型对训练集来说过于复杂，几乎完全记住了数据。


然而，这种对训练集的记忆无法迁移到验证集，因为训练集中包含独特的噪声和偶然样本，这些在其他数据集中不会重复出现。

因此，模型最终在验证集上产生了很高的误差，未能成功泛化其学习（记忆）。


理想模型与偏差-方差权衡

理想模型能够在低偏差与低方差之间取得平衡，有效捕捉训练数据中的潜在模式，同时保持对未见数据的迁移能力。


在实践中，当人们试图通过增加模型复杂度来降低偏差时，偏差-方差权衡便出现了：模型变得更加灵活，同时也开始捕捉噪声，从而增加方差。

随着模型架构变得越来越复杂，过拟合通常比欠拟合更具挑战性。


VC 维度如何定义泛化界

VC 维度用于评估 VC 界（VC bound），即模型真实误差的一个概率上界。

它回答的问题是：

在最坏情况下，这个模型在真实世界中可能遇到的最大误差是多少？

从数学上看，VC 界表示样本内误差（in-sample error）与样本外误差（out-of-sample error）之间的差距，使得：

其中：

  • (E_{out})：样本外误差（也称总误差或泛化误差）
  • (E_{in})：样本内误差（平均训练误差）
  • (N)：训练集中的样本总数
  • (d_{VC})：模型的 VC 维度
  • ：置信参数（例如 (δ = 0.05) 表示以 95% 的置信度保证该界成立）

在渐近符号（Big-O）中，忽略常数后，式 (1.1) 可写为：


样本内误差（In-Sample Error）

样本内误差衡量的是模型在其实际训练数据上的平均损失（误差）。

其中：

  • (N)：训练集样本总数
  • (L(y, h(x)))：损失函数（例如均方误差或 0/1 损失）

如图 B 所示，当发生欠拟合时，样本内误差可能很高；当过拟合或达到理想状态时，样本内误差可能较低。


样本外误差（Out-of-Sample Error）

样本外误差（也称总误差或泛化误差）表示模型在未见数据上的期望总误差。

在理论上，该误差可以分解为三个基本组成部分：

注意：式 (3.1) 的分解特定适用于平方误差损失。

其中：

  • Bayes error 是问题本身固有的噪声。例如 [ y = f(x) + \epsilon ] 其中 (y) 是观测标签（带噪声的真实值），(f(x)) 是模型试图学习的真实理想函数。
  • Bias²（偏差平方） 表示 Bayes error 与训练误差之间的差距。
  • Variance（方差） 表示训练误差与模型在未见数据上的真实误差之间的差距。

当样本 ((x,y)) 来自真实底层分布 (P) 时，(E_{out}) 表示为：

其中：

  • (h(x))：模型生成的假设（预测函数）
  • ({E}[L])：在分布 (P) 下对所有可能样本的期望损失
  • (L(y, h(x)))：损失函数

然而，在实践中，计算真实的 (E_{out}) 几乎是不可能的，因为现实世界中的底层分布 (P) 极其复杂且充满噪声。

因此，该界假设训练误差可以作为真实误差的可靠近似，因为数据是 i.i.d.（独立同分布）的。


于是，我们通常用测试集来近似误差。测试集在训练过程中未被使用，并假设真实误差 (E_{out}) 与估计误差 (\hat{E}_{out}) 之间的差距可以忽略。

这一过程表示为：

其中 (N_{test}) 表示测试集中的样本总数。


机器学习模型的 VC 维度

VC 维度衡量的是模型能够“打散”（shatter）的最大样本集合大小。简单来说：


步骤 1： 找到最大的整数 (n)，使得至少存在一种由 (n) 个点构成的排列方式可以被模型打散。

步骤 2： 证明不存在任何由 (n+1) 个点构成的集合能够被该模型打散。


VC 维度的公式因模型不同而不同。


线性分类器（Perceptrons）

对于一个位于 (n) 维空间中的线性分隔器（其中 (n) 为特征数量）：


如图 A 所示，在二维空间（(n=2)）中，一条直线可以打散三个点；在三维空间中，一个平面可以打散四个点。前提是模型具有 (n+1) 个参数（(n) 个权重加一个偏置项）。


多项式分类器

一个次数为 (d) 的多项式曲面在 (n) 维空间中分离数据：

该式表示在 (n) 个变量中，一个次数为 (d) 的一般多项式所包含的项数。

例如，在二维空间中的二次多项式，其 VC 维度为：


最近邻（1-NN）

1-NN 模型可以通过简单地记忆样本位置来打散任意数量的点，因此其 VC 维度为无穷大：

式 (4.3) 正确预测了：如果不施加额外约束，1-NN 极易发生过拟合。


支持向量机（SVM）

对于 SVM，VC 维度并不严格由维度数量决定，而是由间隔 (\gamma) 以及包含数据的球体半径 (R) 决定：

式 (4.4) 解释了为什么 SVM 在高维空间中仍然具有良好的泛化能力；其复杂度取决于找到的间隔大小，而不仅仅是特征数量。


为什么 VC 界很重要

式 (1.1) 表明，VC 界利用 VC 维度 (d_{VC}) 来计算样本内误差与样本外误差之间的最大可能差距。

该公式从数学上证明了机器学习中的一个基本权衡：

  • 复杂模型容易过拟合，因为增加 (d_{VC}) 会增大 VC 界，从而扩大训练误差与真实误差（理论上可用验证误差表示）之间的差距。
  • 更多数据会使训练误差成为更可靠的总误差估计，因为当 (N) 增加时，VC 界会收缩，使得 (E_{in}) 更接近 (E_{out})。

为了最小化 (E_{out})，关键在于平衡模型复杂度：既要足够复杂以降低 (E_{in})，又要足够简单以保持 VC 界较小。


开发者说明

VC 维度是一种传统理论。

在实践中，我很少直接使用它来选择或调节模型。一方面，它并不适用于大多数现代模型；另一方面，计算精确的 VC 维度在模型复杂时具有很大的数学难度。


此外，VC 界代表的是最坏情况下的“松弛”上界，而这种极端情况在现实中往往并不会出现。


因此，在实践中，我通常会对多个模型进行基准测试，并几乎总是使用正则化和早停（early stopping）来防止过拟合。

VC 维度本质上是一种用于量化模型复杂度的理论工具。


实证测试：Python 中的结构风险最小化（SRM）

我将演示如何利用结构风险最小化（SRM）来寻找最优的多项式次数。

SRM: Structural Risk Minimization


◼ 数据集

首先，我构造一个合成数据集，其中真实关系为：

并加入较大的噪声以模拟现实世界的不完美：

import numpy as np

np.random.seed(42)

N = 100
X = np.sort(np.random.rand(N, 1), axis=0)
def true_func(x): return np.sin(2 * np.pi * x)
y = true_func(X).ravel() + np.random.normal(0, 0.3, N)  # 加入噪声

随后，我创建一个更干净的测试数据集，用于后续模拟真实的 (E_{out})：

X_test = np.linspace(0, 1, 500).reshape(-1, 1)
y_test = true_func(X_test).ravel() + np.random.normal(0, 0.3, 500)


Pipeline（Scaling + Complexity）

在循环中，我使用 sklearn.pipeline.Pipeline 为每个多项式次数 (d) 执行三项操作：

  1. PolynomialFeatures(degree=d) 增加模型容量（VC 维度），将单个特征 (x) 转换为 ()（对应式 (4.2)）。
  2. StandardScaler() 将所有特征缩放为均值 0、方差 1。
  3. LinearRegression() 在缩放后的特征上拟合线性回归系数。

计算 VC 界与 SRM 逻辑

根据公式，我计算 (e_{in})、(e_{out})、(d_{VC}) 和 SRM。

结构风险最小化（SRM）用于比较两种选择最优多项式次数的方法：

  • 经验选择：选取 (e_{out}) 最小的 (d)，即基于测试集实际表现。
  • 理论选择（SRM）：选取 (e_{in} + vc_bound) 最小的 (d)，完全不查看测试数据。

实践中通常采用经验选择；理论选择仅用于演示。


import numpy as np
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import PolynomialFeatures, StandardScaler
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error

results = []
for d in degrees:
    # pipeline
    model = Pipeline([
        ("poly", PolynomialFeatures(degree=d)),
        ("scaler", StandardScaler()), 
        ("linear", LinearRegression())
    ])
    model.fit(X, y)

    # compute E_{in}, E_{out}, vc bound, srm
    e_in = mean_squared_error(y, model.predict(X))
    e_out = mean_squared_error(y_test, model.predict(X_test))
    vc_bound = compute_vc_bound(d_vc=d + 1, N=N)
    srm_score = e_in + vc_bound 

    # store the results
    results.append({
        'd': d,
        'e_in': e_in,
        'e_out': e_out,
        'srm': srm_score
    })

# find optimal d
opt_d_empirical = degrees[np.argmin([r['e_out'] for r in results])]
opt_d_theoretical = degrees[np.argmin([r['srm'] for r in results])]


结果

模拟结果表明：当模型复杂度（多项式次数）从 1 增加到 14 时，VC 界逐渐增大，代表模型灵活性的惩罚增加。

这导致样本内误差 (E_{in})（红色实线）与样本外误差 (E_{out})（黑色实线）之间的差距扩大。

在该案例中：

  • 理论最优次数为 (d = 7)（黑色虚线），由 SRM 得出；
  • 经验最优次数为 (d = 5)（红色虚线）。

这表明实际数据更适合较简单的五次模型，尽管理论建议使用更复杂的七次模型。

当 (d > 5) 时，模型开始拟合噪声，造成计算资源浪费并降低性能。


image.png

图 C：样本内与样本外误差随多项式次数变化的对比图（由 Kuriko IWAI 创建）


预测性分析

▫ 当样本数量 (N) 增加时：

  • VC 界缩小：更多数据对模型形成更强约束。
  • 差距收敛：(E_{in}) 与 (E_{out}) 趋于一致。
  • 最优复杂度提高：最优次数可能从 5 上升至 10。
  • 理论与实践更一致。


▫ 当模型复杂度 (d) 增加时：

  • (E_{in}) 下降：模型逐渐记忆训练数据。
  • 方差激增：模型对噪声变得敏感。
  • 泛化间隙扩大：(E_{out}) 上升，出现过拟合风险。


总结

VC 维度是机器学习中的重要理论支柱，用于量化模型容量。

VC 界为我们提供了一种“安全估计”，即模型在未见真实数据上性能可能下降的松弛上界。

多项式模型实验实证验证了若干学习理论核心原则：

  • 偏差-方差权衡：提高多项式次数降低 (E_{in})，但扩大泛化间隙。
  • 复杂度与数据规模的关系：高 VC 维模型在样本较少时容易将噪声视为信号。
  • 理论与实践的模型选择差异：由于 VC 界较为松弛，理论选择的模型往往略微复杂于经验最优模型。

在所有预测模型中，实现低偏差与低方差的平衡仍是首要目标，以确保今天学到的模式在未来数据中依然有效。

评论
Copyright Created by DataER | 沪ICP备2024052789号-5 | 沪公网安备31010402336337号