📊 statistics

MaxSketch: Robust Distinct Counting in Streams via Random Projections

本文介绍了 MaxSketch，这是一种基于随机投影的算法，它利用学习表示中的几何结构，在噪声高维数据流中实现鲁棒的 distinct 计数估计，达到近最优的对数级内存复杂度，从而克服了经典草图方法及先前最坏情况界存在的局限性。

原作者： Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

发布于 2026-05-18

📖 1 分钟阅读☕ 轻松阅读

原作者： Nikos Tsikouras, Constantine Caramanis, Christos Tzamos

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

想象你站在一处繁忙的十字路口，手持相机，试图统计有多少独特的人经过。

在计算机科学的旧时代，如果每个人都佩戴着统一的 ID 徽章，计数就很简单。如果“爱丽丝”经过，她的徽章上写着“爱丽丝”。如果她再次经过，徽章上依然写着“爱丽丝”。计算机只需检查是否曾见过完全相同的徽章即可。经典计数工具正是如此运作：它们依赖精确匹配。

但在现实世界中，人们并不佩戴 ID 徽章。他们穿着不同的衣服，站在不同的光线下，摆出不同的姿势。如果爱丽丝穿着红色外套经过，后来又穿着蓝色夹克经过，一台简单的计算机可能会想：“那是个新面孔！”从而将她计数两次。这就是嘈杂、高维数据的问题：同一物体每次出现时看起来都不同。

旧方法与新问题

以往尝试解决此问题的方法是将外观相似的事物归为一组（聚类）。但这就像试图通过保存你见过的每个人的照片来计数。如果你看到了 10,000 人，就需要记住 10,000 张照片。这会占用过多内存，尤其是当你正在实时处理海量数据流时。

另一种方法试图说：“如果两张照片足够接近，它们就是同一个人。”但在数学上，这被证明极其困难。在最坏的情况下，为了获得准确的计数，你需要巨大的内存（与总人数的平方根成正比）。这就像为了统计体育场内的人群，而需要一座城市大小的图书馆。

解决方案：MaxSketch

本文作者介绍了一种名为MaxSketch的新方法。他们意识到，现代人工智能（特别是深度学习）已经非常擅长组织数据。当你训练 AI 识别面部或物体时，它自然会学习将“爱丽丝”归入一个紧密的簇，将“鲍勃”归入另一个遥远的簇。即使爱丽丝换了外套，她的“数字指纹”仍会保持在原始位置附近。

MaxSketch利用这种自然聚类来计数，而无需记住每一张照片。

类比：“风洞”

想象你有一个巨大的风洞，里面有许多风扇从不同的随机方向吹风。

设置：你有一串人（数据点）穿过风洞。
测试：对于每个风扇方向，你问：“在这个风向中，谁站得最远？”
神奇之处：如果有 100 张爱丽丝的照片穿过，对于某个特定的风扇方向，她只会成为“最远”的那个人一次。其余 99 次，她虽然还在，但不会改变答案，因为她已经是最大值了。风洞有效地忽略了重复，只关心独特群体的存在。
计数：通过平均成千上万个随机风向的结果，计算机可以估算数据流中有多少个不同的“簇”（独特的人）。

为何有效

论文证明，如果数据是“表现良好”的（意味着 AI 成功地将相似事物归为一组，并将不同事物分隔开），这种方法就极其高效。

内存：MaxSketch 不需要一座城市大小的图书馆，只需要一本小笔记本（对数级内存）。这就像通过拍摄几快照风向的快照来计数人群，而不是给每个人拍照。
准确性：它可以以极高的精度（误差极小）估算独特人数。
鲁棒性：即使穿红大衣的“爱丽丝”与穿蓝夹克的“爱丽丝”看起来略有不同，只要它们仍被识别为处于 AI 记忆中的同一个大致“邻域”内，该方法依然有效。

他们的测试内容

研究人员在以下数据上测试了该方法：

MNIST（手写数字）：这里的“簇”非常清晰（数字"3"总是看起来像"3"）。在此情况下，MaxSketch 表现完美，即使计数序列远长于其训练序列。
CIFAR-10（小型彩色图像）：这里的情况更为混乱。它仍然工作良好，尤其是当 AI 已经训练过识别这些物体时。
真实人脸数据：使用来自现实世界的真实人像照片。尽管数据并不完美，MaxSketch 仍能很好地估算出数千张照片流中有多少独特的人，其表现优于专为嘈杂数据设计的以往方法。

核心结论

MaxSketch是一个巧妙的技巧，它将一个困难的计数问题转化为一个简单的“寻找最大值”问题。通过利用现代 AI 自然将相似事物归为一组这一事实，它可以用极少的内存统计海量嘈杂数据流中的独特项目。它架起了传统计数算法与现代 AI 之间的桥梁，表明如果你的数据组织得当，你无需记住一切就能知道有多少独特的事物存在。

技术摘要：MaxSketch：通过随机投影实现流数据中的鲁棒性不同计数

问题陈述

当元素的重复出现由相同键（例如，精确的字符串匹配）表示时，估计数据流中不同元素数量的经典问题已得到充分理解。HyperLogLog 等算法通过依赖一致的哈希值，以对数级内存实现了这一目标。然而，在现代数据模态（例如，计算机视觉、自然语言）中，观测值是高维且充满噪声的。同一底层对象的不同实例（例如，同一个人的不同图像）仅近似相似，而非完全相同。

在这种“鲁棒性不同计数”模式下，经典草图（sketches）失效，因为它们无法区分新对象与现有对象的噪声变体。在一般度量空间中的近期研究已确立，鲁棒性计数的最坏情况内存下界为 $\tilde{\Omega}(\sqrt{n})$ ，这比精确设置下可实现的 $\tilde{O}(\log n)$ 要差指数级。本文解决的核心问题是：现代学习表示中特有的几何结构——即同一对象的观测值形成紧密簇，而不同对象对应于分离良好的方向——能否突破这一 $\sqrt{n}$ 障碍。

方法论：MaxSketch

作者引入了MaxSketch，这是一种简单的、基于最大值的流式草图，旨在利用学习嵌入的几何结构。

核心机制

MaxSketch 不通过求和或平均投影（这些操作随频率缩放，并将不同性与多重性混淆），而是通过最大值操作聚合观测值。

随机投影：给定单位向量流 $X = \langle \tilde{x}_1, \dots, \tilde{x}_n \rangle \subset S^{d-1}$ ，算法固定 $m$ 个独立的随机高斯向量 $w_1, \dots, w_m \sim \mathcal{N}(0, I_d)$ 。
最大聚合：对于每个投影 $w_j$ ，计算其与流中任意观测值的最大内积：
$M_j(X) = \max_{1 \le i \le n} \langle w_j, \tilde{x}_i \rangle$
统计量：最终草图是这些最大值的平均值：
$S(X) = \frac{1}{m} \sum_{j=1}^m M_j(X)$

理论基础

该方法基于流是 $(\eta, \rho)$ -可聚类的假设。这意味着：

簇内对齐：同一对象的观测值在方向上接近潜在中心（由 $\eta$ 控制）。
簇间分离：不同对象的潜在中心具有较低的内积（由 $\rho$ 控制）。

在此假设下，一组向量的最大投影表现得像独立高斯变量的最大值。该最大值的期望随不同潜在方向（簇）的数量单调增长。通过分析高斯过程的极值统计（利用 Slepian 不等式和 Lipschitz 函数的集中性），作者证明了 $k$ 个簇与 $(1+\epsilon)k$ 个簇之间的期望最大值之差足以以高概率区分它们。

主要贡献

MaxSketch 算法：一种置换不变且兼容流处理的草图，直接在连续嵌入上操作。其构造方式天然地丢弃了多重性，因为同一对象的额外重复一旦达到该簇的“峰值”，就不会增加最大投影值。
改进的内存保证：本文证明，在自然的可聚类性假设下，MaxSketch 使用 $\tilde{O}(\log n / \epsilon^2)$ 内存即可实现对不同计数的 $(1+\epsilon)$ 倍乘近似。这相对于没有此类结构的一般度量空间已知的 $\tilde{\Omega}(\sqrt{n})$ 下界有了显著改进。
学习归约：作者表明，一旦随机投影固定，草图对输入的依赖就坍缩为单个标量统计量 $S(X)$ ，该统计量对真实计数是单调的。因此，学习预测计数简化为拟合一维单调函数（读出层），这具有样本效率且条件良好。
固定草图的存在性：虽然理论保证最初假设每个流使用新的随机投影，但本文证明，对于可聚类流分布，单个固定的投影集以高概率就足够了。

实验结果

作者在三个方面验证了 MaxSketch：

MNIST：在类内变异性较低的场景中，MaxSketch（仅通过计数监督进行端到端训练）实现了近乎完美的准确率，并外推到远长于训练期间所见序列长度的序列。这证实了理论预测：当嵌入聚类良好时，聚合机制具有鲁棒性。
CIFAR-10：在类内变异性较高的场景中，仅通过计数监督进行端到端训练的准确率低于使用预训练特征的情况。然而，模型仍然捕捉到了计数的正确排序，这表明难点在于学习可聚类的几何结构，而非计数机制本身。
真实世界人脸流：使用固定预训练嵌入（DeepFace）处理合并的人脸数据集（LFW、CelebA、Multi-PIE），将 MaxSketch 与 Zhang 提出的用于一般度量空间鲁棒性不同计数的算法进行了比较。MaxSketch 表现出卓越的鲁棒性，在广泛的不同计数范围内（高达 5,100）保持了高准确率（例如， $\ge 60\%$ 的误差在 $\pm 50$ 以内），而基线算法由于距离分布的重叠违反了其严格的几何假设而严重失效。

意义与主张

本文声称弥合了经典流算法与现代表示学习之间的鸿沟。其主要意义在于证明学习表示中常见的几何结构从根本上降低了不同计数的复杂性。

作者认为，鲁棒性计数的 $\sqrt{n}$ 下界是缺乏结构的最坏情况度量空间的产物。在现代深度学习的领域，其中“神经坍缩”诱导了紧密的类内簇和分离良好的类间方向，该问题变得可用多项式对数级内存解决。MaxSketch 提供了一个理论有据、分析可行的解决方案，利用这种结构，为在嘈杂的高维数据流中进行高效的不同计数提供了一条途径，而无需显式的聚类或身份监督。