🤖 AI

Learning Filters with Certainty

本文提出利用计数布隆过滤器中的计数器值来估计成员指示的确定性，从而增强结合了这些数据结构与机器学习模型的混合架构。

原作者： Yuval Banoun, Daniel Sadoc Menasche, Ori Rottenstreich

发布于 2026-06-23

📖 1 分钟阅读☕ 轻松阅读

原作者： Yuval Banoun, Daniel Sadoc Menasche, Ori Rottenstreich

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

想象一下你正在一个大型活动中负责一个非常繁忙的安全检查站。你有一份 VIP 名单（即“集合”）的人员获准进入。你的目标是快速决定走近门口的人是否在名单上。

旧方法：“也许”清单

传统上，保安使用一种名为 布隆过滤器 (Bloom Filter) 的工具。把它想象成一份巨大的、超快速的清单。

工作原理： 当一位 VIP 到达时，保安会在清单上的几个位置做标记。稍后，如果有人问：“这个人是 VIP 吗？”保安会检查同样的那些位置。如果这些位置都被标记了，保安就会说：“是的，他们很可能是 VIP。”
问题所在： 因为这份清单很小且由所有人共享，有时随机的人会被误标（比如两个人在碰撞时意外地盖到了同一个位置）。这被称为 假阳性 (False Positive)。保安会对并非真正 VIP 的人说“是”。
安全规则： 为了保险起见，如果位置被标记了，保安绝不会说“不”。他们只有在位置为空白时才会说“不”。这意味着他们永远不会错过真正的 VIP（没有假阴性），但可能会放进一些冒充者。

新想法：“置信度计”

本文作者引入了一个更智能的版本，称为 计数布隆过滤器 (Counting Bloom Filter, CBF)。与其仅仅在某个位置做一个简单的“X”标记，不如想象一下保安在每个位置都使用了一个 计数器（就像一个数字计数器）。

工作原理： 每当一位真正的 VIP 通过时，他们对应的位置数值就会增加（1, 2, 3...）。
神奇之处： 如果一个随机的冒充者试图混入，他们可能会意外触碰到一个数值为“1”的位置。但如果他们触碰到的是一个数值为“12”的位置，那这很可能不是巧合。
深刻见解： 本文认为这些数字不仅仅是为了计数；它们是一个 置信度计 (Confidence Meter)。高数值意味着：“我非常确定这个人属于这里。”低数值意味着：“我不确定；这可能只是个巧合。”

加入“智能助手”（机器学习）

论文还讨论了如何使用 机器学习 (ML) 模型，这就像一位训练有素的安全专家，可以通过观察一个人的脸部或身份证件来判断其是否为 VIP。

专家的难题： 即便是最好的专家也会犯错。有时他们也会感到犹豫不决。
解决方案： 论文提出了四种不同的方式，将专家与 置信度计 结合起来，以做出更好的决策。

以下是论文描述的四种“组队策略”：

1. “专家优先”组 (模型 1)

工作原理： 专家首先观察那个人。如果专家非常有信心（“没错，他绝对是 VIP！”），则直接放行。
备份方案： 如果专家不确定（“嗯，也许吧？”），则将此人交给置信度计。置信度计会检查数值。如果数值足够高，它会说“是”；如果数值较低，它会说“不”。
优点： 通过让专家处理显而易见的情况来节省时间。

2. “守门员优先”组 (模型 2)

工作原理： 一个简单、快速的“守门员”（标准的清单）首先检查那个人。如果守门员说“不”，则此人被拒之门外。如果守门员说“也许”，则将其交给专家。
转折点： 专家不仅仅给出一个最终的“是/否”结论。相反，专家会给出一个“置信度分数”给置信度计。置信度计利用这个分数来决定它应该有多严格。
优点： 守门员过滤掉了明显的伪造者，因此专家和置信度计只需处理棘手的案例。

3. “快速通道”组 (模型 3)

工作原理： 这类似于模型 2，但有一个快捷方式。守门员先检查。如果守门员说“也许”，则由专家查看。
快捷方式： 如果专家非常有信心，则直接放行，无需再麻烦置信度计。
备份方案： 如果专家不确定，置信度计会介入并承担繁重的工作。
优点： 对于专家确定的情况，它的速度最快；但对于不确定的情况，它依然非常安全。

4. “全能一体”组 (模型 4)

工作原理： 这是集成度最高的一个团队。同一个置信度计在开始和结束时都会被使用。
流程： 首先，置信度计检查数值是否为零。如果其中任何一个位置为零，该人就被拒之门外。如果不是，数值将被交给专家。
神奇之处： 专家会同时观察那个人和这些数值来进行决策。如果专家仍然不确定，置信度计会最后一次利用这些数值进行最终判定。
优点： 它两次使用了同一个工具，节省了空间，并且让专家能直接从数值中学习。

核心总结

本文的核心观点是：不确定性本身就是有用的信息。

在过去，安全工具只能给出二元答案：“是”或“否”。本文展示了通过使用 计数布隆过滤器，我们可以获得一个“也许”的答案，这个答案能告诉我们“我们有多确定”。通过将这种“确定性信号”与智能计算机模型相结合，我们可以构建出比以往更快、占用内存更少、且错误更少的系统。

本文并不声称解决了医疗诊断或预测股市的问题；它专门关注如何使这些数字化的“清单”在处理数据缓存、检测网络问题或过滤计算机系统中的信息等任务时变得更加聪明。

技术摘要：具备确定性的学习型过滤器

问题陈述
布隆过滤器（Bloom Filters, BFs）广泛应用于网络系统和机器学习（ML）流水线中，用于集合表示和成员查询。然而，标准的布隆过滤器仅提供二元指示（成员/非成员），并且由于哈希冲突，本质上存在假阳性问题。为了避免假阴性，布隆过滤器无法支持删除操作，这限制了其在动态集合中的应用。虽然计数布隆过滤器（Counting Bloom Filters, CBFs）通过使用计数器而非位来解决了删除限制，但它们通常仅被视为二元结构，即只要所有计数器非零，即返回正向指示。

作者认为，CBF 中与哈希冲突相关的确定性包含着有价值的信息。具体而言，计数器的值可以被用于估计正向成员指示的“确定性”（后验概率）。本文探讨了当将 CBF 与学习型成员模型（ML）结合时，如何利用这种“确定性信号”实现从二元决策向概率推理的跨越。

方法论与架构
本文基于先前研究 [12] 的观察，即 CBF 计数器允许估计后验成员概率 $P(x \in S | V(x))$ ，其中 $V(x)$ 是计数器向量。作者提出了四种不同的架构，将学习模型与布隆过滤器及 CBF 集成，利用不同的策略来结合学习得分 $f(x)$ 、CBF 计数器向量 $V(x)$ 以及可选的预过滤。

模型 1：学习型计数布隆过滤器 (Learned Counting Bloom Filter)
- 结构： 一个学习型预言机（Oracle）充当前端分类器。如果模型足够自信（ $f(x) \ge \tau$ ），则立即输出正向决策。如果得分较低，则将查询传递给 CBF。
- 机制： CBF 不仅仅作为二元备份，而是作为后验估计器。它使用总体先验（ $p_0 = P(x \in S)$ ）来计算后验概率。如果后验概率超过阈值 $\eta$ ，则判定为正向；否则为负向。
- 权衡： 这是最简单的“即插即用”替代方案，但缺乏前端预过滤器，可能导致较高的假阳性率（FPR）。
模型 2：非对称三明治架构 (Asymmetric Sandwich)
- 结构： 标准布隆过滤器（ $B_1$ ）位于学习模型之前。只有当 $B_1$ 指示存在成员时，才会查询学习模型。
- 机制： 学习模型的得分 $f(x)$ 不直接用于二元决策，而是作为 CBF 后验计算的先验（ $p_1 = f(x)$ ）。最终决策基于使用该学习先验的 CBF 后验。
- 权衡： 前端的 BF 通过过滤掉明显的非成员来降低 FPR。学习先验与结构化计数证据的结合，比单一来源产生的后验信息更丰富。
模型 3：带有早期决策的非对称三明治架构 (Asymmetric Sandwich with Early Decision)
- 结构： 与模型 2 类似，具有前端 BF 和学习模型，但增加了早期退出路径。
- 机制： 如果前端 BF 通过了查询且学习模型高度自信（ $f(x) \ge \tau$ ），系统立即输出正向决策，跳过 CBF。如果置信度较低（ $f(x) < \tau$ ），则将查询传递至 CBF，由学习得分作为后验测试的先验。
- 权衡： 该架构为高置信度情况降低了延迟和计算成本，同时保留了 CBF 的确定性感知推理能力。
模型 4：对称 MAP 三明治架构 (Symmetric MAP Sandwich)
- 结构： 单个 CBF 既作为初始筛选设备，也作为最终决策模块。
- 机制： CBF 首先检查是否所有计数器均非零。如果是，则将计数器向量 $V(x)$ 和元素 $x$ 传递给显式使用这两类特征的学习模型（MAP 预言机）。模型的输出 $f(x, V(x))$ 具有两个用途：(1) 若高于阈值 $\tau$ ，作为直接决策；(2) 若低于阈值，作为最终 CBF 后验测试的 MAP 式先验（ $p_2$ ）。
- 权衡： 这提供了学习与过滤之间最紧密的集成，允许模型从确定性信号中学习。它复用了一个 CBF，与使用多个滤波器的模型相比减少了内存占用，但也造成了阶段间的统计依赖。

核心贡献

确定性感知数据结构： 本文将 CBF 从简单的支持删除的结构重新定义为能够输出置信度得分而非二元答案的“确定性感知”数据结构。
四种新颖架构： 作者提出了四种特定的架构（模型 1–4），利用 CBF 的计数器值来量化成员查询中的不确定性。
理论分析： 本文对每种架构的假阳性率（FPR）进行了形式化分析，推导出的公式考虑了学习预言机的错误率、过滤器的假阳性以及后验决策阈值之间的相互作用。
权衡特征化： 本文讨论了各架构在 FPR、推理成本、内存占用以及利用确定性决策收益方面的权衡。

结果与意义
本文并未针对特定数据集展示新的实证实验结果，而是依赖于理论推导和对先前模拟工作（如 [12]）的引用，以证明计数器的效用。

理论发现： 分析表明，计数器乘积显著影响后验成员概率。对于先验概率较低的元素，即使计数器乘积的小幅增加也会导致估计的成员确定性大幅提升。
意义： 作者声称，引入 CBF 计数器的内存开销不应仅被视为支持删除的成本，而应被视为一种“信息丰富的信号”。通过利用这一信号，机器学习模型可以以标准布隆过滤器无法实现的方式对不确定性进行推理。
实际影响： 本文指出，这些架构允许系统设计者在假阳性、假阴性和内存使用量之间选择运行点。它强调了一个实际挑战：虽然 CBF 可以通过插入/删除进行在线更新，但学习模型通常需要定期重新训练，这暗示了一种混合更新策略。

结论
本文得出结论，计数布隆过滤器提供了一种通用的紧凑集合表示机制，通过与学习模型结合，可以提供细致的、基于概率的成员决策。所提出的架构提供了一个将这些确定性信号集成到机器学习流水线中的框架，平衡了准确性、延迟和内存效率之间的权衡。未来的研究方向包括组件间的最优内存分配、自适应决策阈值，以及探索其他能够暴露内部确定性信号的概率数据结构。