大数据算法 课程总结笔记 I（期末部分）

这是我在 2026 年春季于中科大学习丁虎老师的《大数据算法》课程时整理的期末考试复习笔记。非常喜欢的好课。只是可惜讲义编写得比较潦草。这里的笔记尽可能指出讲义中各种概念的几何意义与机器学习意义，并尝试找出各种定义、定理的动机。

6 VC 维

VC 维及其几何概念

VC 维和核心集（coreset）是描述模型表达能力的数学工具。

直观来看，VC 维描述的是一个分类器在任意的正负类指定下，能够区分（称为“打散”）的最大数据点数目。如：

• 在二维平面上，二维直线可以打散（不共线的）3 个点，但不能打散（任何分布下的）4 个点，因此二维直线的 VC 维为 3；
• X 是二维平面 ， 是二维平面里的一个圆，那么
• X 是三维平面 ， 是三维平面里的一个球，那么
• X 是二维平面 ， 是二维平面里的一个多边形，那么

严格的数学的定义见讲义。以下是这些几何概念和机器学习中概念的对应，提供一些直观的理解。

范围空间由基集和范围族共同确定。

VC 维的定义是“存在”性的，如果存在大小为 的点集能被打散，则 . 反过来，如果对于任意大小为 的点集都不能被打散，则 .

VC 维并不是越高越好。能完全打散样本集的模型容易产生过拟合，VC 维适当（较低）的模型能够有更强的泛化潜力。当 VC 维低于样本集大小时，泛化误差界开始起作用，训练集上的表现具有了代表性，这由 VC 不等式保证。

定理 6.1：如果有一个 Range Space ，它的 VC 维 ，那么定义两个集合：

令 ，，则这两个 Range Space 的 VC 维在 和 之间，即：

这个定理描述了多个模型用并、交操作组合出来的新模型表达能力的上下界，提供了一个模型组合的“安全边界”。

对于给定的范围空间 ，数据集合 ，误差参数 . 可在空间上定义一些“网状”结构：

• ：对于 ，若 中任意大小足够的范围 均一定包含 中的点，则称 是 关于 的一个 。

  • 要求采样范围“不能漏掉”显著的区域。

• ：对于 ，如果对于任意范围 ，，即采样集合 计算出来的密度与真实密度的误差都不超过 ，则称 是 的一个 。

  • 要求采样范围“能正确估计”显著的区域。

显然 的定义是更强的条件。

定理 6.2 & 6.3： ， 是 的均匀采样子集。

• 是 的概率 的条件为
• 是 的概率 的条件为

可以观察到这些概率和 无关。

实际意义：经验观察可以推广到实际真理。无论多大的数据，学习一个能良好分类这些数据的模型只需要一个（良好采样的）小样本，这个小样本的大小仅和模型的复杂程度与对误差的容忍度有关，而与数据集的大小无关。

假如说有一个巨大的包含正负样本的数据集，数据集的数据维度为 ，在该数据集上存在一个良好的分类超平面能很好的分开正样本和负样本，那么我们根据这两个定理，可以得出，当我们的SVM分类器的训练数据集的大小大概为 时，我们可以保证，对任何一个新来的数据点，分类出错的概率小于 。

VC 维与 PAC Learning

可高效 PAC 学习的实际意义是：高概率的采样条件下（失败概率 ），对任意分布的训练&测试集，算法可学习到误差足够小（小于 ）的模型，且算法时间复杂度是 的多项式级别。（能大概率学到足够好的模型的多项式算法）

定理6.4（奥卡姆剃刀）：如果一个算法能够高效地找到一个一致的假设（consistent hypothesis），那么对于任何有限概念类 ，只要提供至少 个样本，该算法就能实现 PAC 学习。其中样本数 满足：

• 一致的假设是指能精确区分训练数据集上所有正负样本的假设，于是这样的假设训练误差为0.

实际意义：“若无必要，勿增实体”，假设越小，泛化能力越强。对于两个能通过训练数据集的分类的模型，选择更简单的那个（即 VC 维更小的那个），能得到更好的泛化能力。

7 核心集

定义：对于数据集 上特定的问题 ，对于解空间 中任意解，满足以下误差约束的带权数据集 （足够具有代表性的数据集）

带权是核心集必要的属性，这里的权重类似于将一个数据点复制多份来代表它在原始数据集中的重要程度。

核心集的使用通常遵循”构建 -> 求解 -> 映射”的三步范式：

• 数据缩减（构建核心集）： 给定一个包含数亿条记录的海量数据集 ，使用一种快速算法（通常是线性的，甚至是亚线性的时间复杂度）从中提取出一个极小的核心集 。核心集中的每个数据点通常会被赋予一个权重（Weight），用来代表它”代表”了原始数据集中的多少个点。
• 在核心集上运行算法（求解）： 将原来计算复杂度极高（例如 或 ）的机器学习或数据挖掘算法应用到核心集 上。因为 的规模远小于 （例如 有 10 亿个点， 只有 1 万个点），计算时间被成千上万倍地缩短。
• 结果映射（应用结果）： 将在核心集 上训练出的模型或得到的参数，直接作为原始数据集 的近似最优解。

对每个问题通常都有特定的核心集构建方式，包括分治、几何划分/聚类、贪心、重要性采样等。有一些直观的例子：

• 点云最小包围球问题的核心集是临近边界的点（凸性）；
• k-means 聚类问题的核心集是靠近数据密集区的点；k-means++ 可以作为一个核心集初始化算法，其思想也是很多核心集构建算法的基础。

讲义及作业、考试中有介绍一些核心集的构建方法。(TODO)

深度学习中核心集的主要应用有：

• 持续学习：在历史样本中选择核心集作为记忆。

  • Yoon 等人提出的准则：小批量相似性、样本多样性、Coreset 亲和性。

• 池式主动学习：模型主动以 coreset 原则选取重要样本。
• 生成模型：优化数据子集选取、自适应动态选择数据点等。(Small-GAN)

• LLM：CoLM 技术。传统 coreset 方法用于语言数据存在 (1) 小数据源样本容易被忽略; (2) Adam 优化器的梯度缩放影响未被考虑; (3) 语言模型维度极高、距离度量容易退化。

  • CoLM 提出的三步策略：小数据源样本保留、梯度归一化、梯度维度压缩。

8 最优传输

问题形式：有两个离散归一化分布向量 ，成本矩阵（“距离”），目标是找到一个传输计划（“耦合”）矩阵 满足 （记这类矩阵集合为 ），最小化总运输成本 .

即：找到一个从分布 到分布 的最优传输计划 ，使得运输成本（由成本矩阵 定义）最小。

熵正则化：TODO

应用：

• 生成式模型：Flow Matching, Diffusion Model.
• 领域自适应：在源领域上训练一个模型，利用最优传输将源领域的分布映射到目标领域，从而实现模型在目标领域的迁移。怎么感觉和我们在做的需求有点像，有空认真研究一下。
• Wasserstein 鲁棒分布优化：TODO

9 分布式算法

10 Beyond worst case analysis

11 SGD 随机梯度下降

随机梯度下降系列算法目前研究的方向可以分为这四大类：

1. Variance Reduction 技术：尽可能缩减随机采样梯度的方差；SAG, SVRG, SAGA 等。
2. 动量法：解决梯度方向来回震荡的问题；Nesterov 加速等。
3. 自适应算法：对不同参数自适应调整学习率；AdaGrad, RMSProp（均方根传播）。
4. 二阶优化方法：基本上没什么人用，只在学术界出现；Hessian 矩阵求逆太慢了（计算量大）；近似又会引入误差，抵消了二阶微分引入的修正；claim 的优势是不受鞍点影响，但实际上动量法、自适应法也能解决。

目前影响力最广泛的算法是结合 2 和 3 的思想提出的 Adam 优化器 (2015)。2024 年 Keller Jordan 在博客中提出了 MUON 算法，

回顾一下问题背景。我们先形式化一下机器学习想解决的问题：

其中有误差情形 . 误差分为三部分

其中 是模型的近似误差（函数空间 自身的缺陷）， 是泛化误差（模型对训练集 外数据分布估计的误差，也取决于函数空间的 VC 维）， 是训练误差（训练方法造成的误差）。SGD 主要关注的是训练误差的优化。

由于随着函数空间变得复杂时，函数空间会变大从而近似误差会增加，但是 VC 维也会增加，使得泛化误差增大，因此近似误差和泛化误差之间（在 VC 维理论上）存在 trade-off。但是这一 trade-off 在当前的深度学习理论中并不清晰，存在许多实际应用中的反例。

例子有线性回归、逻辑回归、神经网络等。

为了保证梯度下降符合预期，人们提出了各种正则化策略，如 Ridge Regression（L2 正则化，=Weight Decay，解决多重共线性问题），Lasso 正则化（L1 正则化）。这些正则化策略能惩罚大的系数，让模型不仅尽可能拟合数据，还要尽量简单（“奥卡姆剃刀”），以减少过拟合风险。可以用偏差-方差分解理论解释（将一部分方差转化为偏差），也可以用贝叶斯先验（认为系数不应过大）解释。

一般的梯度下降方法形式为：，终止条件为 （注意该终止条件在一些鞍点上也被满足，这是非预期的情形）。其收敛依赖于 Lipschitz 假设和强凸性。