🤖 machine learning

A Practical Theory of Generalization in Selectivity Learning

原作者： Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Peizhi Wu, Haoshu Xu, Ryan Marcus, Zachary G. Ives

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位厨师，试图根据发出的邀请预测会有多少人参加晚宴。在数据库领域，这被称为选择性估计：即猜测有多少行数据会匹配特定的搜索查询。

几十年来，数据库系统一直使用简单的规则（例如“假设数据均匀分布”）来进行这些猜测。但当数据杂乱无章或问题棘手时，这些规则往往会失效。最近，科学家们开始利用**机器学习（AI）来学习这些模式。这些 AI 模型对于它们之前见过的问题非常擅长猜测，但当被问及与训练数据略有不同的问题时，它们往往会彻底失败。这被称为分布外（OOD）**问题。

本文《选择性学习泛化的实用理论》试图弥合数学理论（声称 AI 应该有效）与现实（AI 在面对新的、奇怪的问题时往往表现不佳）之间的差距。

以下是用简单术语进行的分解：

1. 问题：“概率”陷阱

我们过去拥有的最佳数学理论（称为 PAC 学习）依赖一条严格的规则：AI 的预测必须表现得像一张完美的概率地图。

比喻：想象一张地图，其中的墨水代表找到数据的可能性。旧理论规定：“墨水必须始终为正，且整张地图上的墨水总量必须恰好等于 1。”
现实：最强大的 AI 模型（如深度学习）并不遵循这些严格规则。它们可能会在某些区域预测“负墨水”或“超过 100% 的墨水”，因为它们只是在努力最小化误差。由于它们打破了“完美地图”的规则，旧数学理论认为：“我们无法证明这些模型在新数据上会有效。”
结果：我们拥有了强大的工具，但没有数学保证它们不会在数据变化时失效。

2. 突破：“有符号地图”理论

作者们意识到，我们不需要一张“完美的概率地图”。我们只需要一张**“有符号地图”**。

比喻：想象一张地图，其中的墨水可以是正（蓝色）或负（红色）。只要数学上能够平衡，这张地图就依然有效。
发现：他们证明，即使 AI 模型使用这些“有符号”（正负）预测，它仍然是可学习的。
重大胜利：他们证明，如果 AI 在训练数据上学习良好，那么只要新数据不是完全陌生的（例如，它仍在模型已知的大致范围内），它也将在新的、未见过的数据（OOD）上表现不错。这是一个巨大的飞跃，因为它涵盖了旧理论无法解释的强大深度学习模型。

3. 解决方案：两种新策略

利用这种新的“有符号地图”理论，作者构建了两种实用工具，帮助现有的 AI 模型更好地猜测新数据。

策略 A：NeuroCDF（"CDF"方法）

他们不再要求 AI 直接猜测答案（例如，“有多少行？”），而是要求 AI 猜测累积分布函数（CDF）。

比喻：与其问“房间里现在有多少人？”（如果房间在变化，这很难回答），不如问 AI“到某个特定点为止，房间里有多少人？”
工作原理：AI 学习数据分布的形状（即 CDF）。为了获得特定查询的答案，系统只需对这些 CDF 点进行加减（就像通过知道角落来计算矩形的面积）。
优势：因为这种方法在数学上强制 AI 表现得像一张“有符号地图”，所以它被保证在新数据上具有鲁棒性。
局限：训练起来有点棘手，因为它有时会给出负数，这对于行数计数来说没有意义。

策略 B：SeConCDF（“自一致性”训练器）

这是一种更实用、“即插即用”的解决方案。它接受任何现有的 AI 模型，并为其提供特殊的训练程序。

比喻：想象一个学生参加考试。通常，他们只是死记硬背答案。使用 SeConCDF，老师还会要求学生根据底层规则（即 CDF）解释为什么答案是那个样子。
工作原理：AI 被训练同时做两件事：
1. 直接预测答案（通常的方式）。
2. 预测底层 CDF，并检查这些 CDF 是否与答案一致。
优势：这种“自我检查”迫使 AI 学习数据的底层结构，而不仅仅是死记硬背答案。它使模型对新问题具有更强的鲁棒性，而无需改变模型架构或降低其速度。

4. 结果：它有效吗？

作者在真实的数据库数据集（如电影数据库和人口普查数据）上测试了这些想法。

准确性：当他们向模型提出与训练数据略有不同的问题时（例如，询问不同的年份或不同的数值范围），使用SeConCDF训练的模型比标准模型犯的错误要少得多。
速度：由于猜测更准确，数据库系统不会浪费时间去处理错误数量的数据。查询运行得更快。
对比：新方法击败了旧的“完美概率”模型（理论上安全但实际表现弱），并显著改进了强大的深度学习模型（实际表现强但理论风险高）。

总结

该论文指出：“我们发现了一条新的数学规则，证明强大的 AI 模型可以信赖地处理新数据，即使它们不遵循旧的严格规则。随后，我们构建了一种训练方法（SeConCDF），利用这一规则使数据库 AI 模型在面对意外问题时变得更加聪明和可靠。”

技术摘要：选择性学习中的泛化实用理论

1. 问题陈述

本文探讨了实用查询驱动的选择性学习模型与最先进（SOTA）学习理论之间的理论鸿沟。尽管查询驱动模型（如 MSCN 等深度学习回归器）已展现出优于传统直方图的实证性能，但现有的理论框架——特别是可能近似正确（PAC）学习框架——无法解释其有效性。

prior 理论存在两个主要局限性：

假设性限制：SOTA 理论 [26] 假设选择性预测器是由概率测度诱导的（需满足非负性和归一化约束）。然而，高性能的实用模型（如基于回归的深度学习模型和 LEO）往往违反这些约束（例如产生负值或非单调输出），且并非由概率测度诱导。因此，现有的可学习性结果不适用于这些实用模型。
分布内局限性：PAC 框架仅在训练和测试工作负载来自同一分布时刻画泛化能力。它无法量化**分布外（OOD）**泛化误差，而这在现实世界的数据库场景中至关重要，因为查询工作负载经常发生偏移（例如查询中心或粒度的变化）。

本文旨在通过以下方式弥合这些差距：(1) 放宽对概率测度的理论依赖，纳入带符号测度；(2) 在温和假设下建立 OOD 泛化误差界。

2. 方法论与理论框架

2.1 理论基础

作者引入了一个基于带符号测度的新理论框架。

带符号测度：与概率测度不同，带符号测度满足可列可加性，但放宽了非负性（C2）和归一化（C3）的约束。这使得该理论能够涵盖可能输出负值或总和不为 1 的基于回归的模型。
分布内可学习性（定理 4.1）：作者证明了由带符号测度诱导的选择性预测器类（特别是那些关于勒贝格测度绝对连续的类）是 PAC 可学习的。他们确立了该类类的 fat-shattering 维度是有限的，其界限为 $\tilde{O}(C \cdot (1/\gamma)^{\lambda+1})$ ，其中 $C$ 是测度全变差的界限， $\lambda$ 是范围空间的 VC 维度。这意味着在训练数据充足的情况下，训练误差与真实误差保持接近。

2.2 分布外（OOD）泛化

超越 PAC 框架，本文建立了定理 4.2，提供了 OOD 泛化误差界。

假设：该定理依赖于三个温和假设：
1. 有界性：学习到的选择性函数是有界的。
2. 支撑集包含：测试分布的支撑集包含在训练分布的支撑集内（即测试工作负载不会查询训练期间未见过的区域）。
3. 多样性：训练范围覆盖了多样化的区域集合，确保误差不仅仅在特定的“简单”范围上最小化。
结果：在这些假设下，如果预测器 $\hat{S}$ 的分布内误差有界为 $\epsilon$ ，则其在不同分布 $P$ 上的 OOD 误差有界为 $O(\sqrt{\epsilon})$ 。该结果适用于任何由带符号测度诱导的预测器。

2.3 提出的策略

利用这些理论见解，作者提出了两种改进现有模型的策略：

策略 1：NeuroCDF（建模 CDF）

概念：NeuroCDF 不直接建模查询的选择性，而是使用神经网络建模底层的累积分布函数（CDF）。范围查询的选择性随后通过包含 - 排除原理，作为查询顶点处 CDF 值的线性组合来计算。
理论保证：由于 NeuroCDF 显式建模 CDF，其预测被证明是由带符号测度诱导的。因此，它继承了定理 4.2 的 OOD 泛化保证。
局限性：NeuroCDF 在处理相对误差指标（如 Qerror）时存在困难，因为 CDF 的线性组合可能产生负估计值，这对于 Qerror 是无效的。

策略 2：SeConCDF（CDF 自一致性正则化）

概念：为了结合直接选择性建模的灵活性（支持 Qerror）与 CDF 建模的 OOD 鲁棒性，作者提出了SeConCDF。
机制：SeConCDF 使用复合损失函数训练标准的查询驱动模型（如 MSCN 或 LW-NN）：
1. 原始预测损失：直接选择性预测的标准损失（如 Qerror 或 RMSE）。
2. CDF 预测损失：强制模型预测与观测数据一致的 CDF 值的辅助损失。
3. 一致性损失：一个正则化项，强制直接选择性预测与从模型学习到的 CDF 推导出的选择性之间的一致性。
目标：这种“软约束”鼓励模型表现得如同由带符号测度诱导，从而在不牺牲优化 Qerror 的能力或不改变模型架构的情况下，改善 OOD 泛化能力。

3. 实验结果

作者通过将 SeConCDF 集成到两个最先进的深度学习模型（LW-NN和MSCN）中来评估其性能。实验在单表（Census）和多表数据集（IMDb-small, DSB, CEB）上进行，涉及包含查询中心移动和查询粒度偏移的合成 OOD 工作负载。

OOD 泛化准确性：
- 标准深度学习模型（MSCN, LW-NN）在 OOD 查询上表现出显著的性能下降（例如，中位数 Qerror 从个位数跃升至四位数）。
- SeConCDF显著缓解了这种下降。例如，在具有粒度偏移的 IMDb-small 数据集上，SeConCDF 将 MSCN 的中位数 Qerror 从约 103 降低至约 2.1，同时保持了强大的分布内性能。
- NeuroCDF 也显示出 improved OOD 鲁棒性，但受限于其与 Qerror 的不兼容性。
查询延迟：
- 改进的选择性估计准确性直接转化为更好的查询执行计划。
- 在 OOD 场景中，使用 SeConCDF 训练的模型实现的查询延迟与 PostgreSQL 相当，并显著优于标准 MSCN（后者常因基数估计不佳而导致次优计划）。
与 SOTA 理论模型的比较：基于先前 SOTA 理论（由概率测度诱导，如 PtsHist, QuadHist）的模型比原始深度学习模型表现出更好的 OOD 稳定性，但在分布内准确性和整体 OOD 性能方面，通常不如 SeConCDF 增强的深度学习模型。

4. 主要贡献

理论扩展：本文证明了由带符号测度诱导的选择性预测器是可学习的，将 PAC 学习的范围从概率测度扩展到包含实用的基于回归的模型。
OOD 泛化界：它在温和假设下建立了选择性学习的首个非平凡 OOD 泛化误差界，表明误差随分布内误差的平方根缩放（ $O(\sqrt{\epsilon})$ ）。
实用框架：
- NeuroCDF：一种建模 CDF 以保障带符号测度诱导的新范式。
- SeConCDF：一种通用的训练方法，通过 CDF 自一致性正则化增强现有模型的 OOD 泛化能力，兼容 Qerror 等标准损失函数。
实证验证：证明了这些理论见解在现实世界数据库场景中，能切实提升 OOD 工作负载的预测准确性和查询延迟。

5. 意义与主张

本文声称其主要贡献在于弥合选择性学习中理论与实践之间的鸿沟。通过放宽对概率测度的限制性假设，作者提供了一个理论基础，解释了实用深度学习模型为何及何时能够泛化。

其意义在于能够形式化保证并实际提升学习到的基数估计器对工作负载偏移的鲁棒性。作者强调，其目标不仅仅是在特定基准测试中超越现有的 SOTA 模型，而是验证其理论框架能否被操作化，从而使现有模型在查询分布不可避免地发生偏移的动态现实环境中更加可靠。他们得出结论，他们的方法提供了一条原则性的路径，以增强学习到的数据库组件的可靠性。