MaxSketch: Robust Distinct Counting in Streams via Random Projections¶

会议: NeurIPS 2026
arXiv: 2605.15571
OpenReview: https://openreview.net/forum?id=1MB9KxyzHe
领域: 信息检索/RAG
关键词: 数据流算法, 基数估计, 随机投影, 极值统计, 表征学习

一句话总结¶

针对高维流式数据中同类实体呈现近似而非严格相等的鲁棒去重计数难题，本文提出基于高斯随机投影的极值草图 MaxSketch，证明了在聚类几何结构下仅需 $\tilde{O}(\log n/\varepsilon^2)$ 内存即可实现 $(1+\varepsilon)$ 乘性逼近，突破了一般度量空间的 $\Omega(\sqrt{n})$ 下界。

研究背景与动机¶

在数据流中估计去重元素数目（基数估计或 $F_0$ 估计）是大规模数据分析和数据库系统的经典核心课题。以 Flajolet-Martin、LogLog 和 HyperLogLog 为代表的传统算法依靠确定性哈希函数和极值统计量，能够在仅占用对数级内存的单遍扫描中提供高精度的乘性近似保证。然而，经典算法的正确性完全建立在「相同实体每次出现都拥有完全一致的离散键值」这一刚性假设之上。

在现代高维感知与表征学习场景中，这一假设被根本性打破。以监控视频中的行人重识别或图像流检索为例，同一目标在不同时刻因光照、视角、遮挡和姿态的变化，像素级甚至深层特征表征之间存在显著扰动。若直接对连续嵌入使用局部敏感哈希（LSH）并串联经典 HyperLogLog，LSH 的距离相关碰撞概率会导致碰撞偏倚与重复频次交织；而若维护显式聚类中心，内存消耗将随着类别数线性暴涨，丧失流式算法的亚线性内存优势。近期理论工作探索了一般度量空间中的鲁棒去重计数，但证明了在最坏情况下不可避免需要 $\Omega(\sqrt{n})$ 的内存下界。

这一瓶颈促使研究者重新审视现代深度网络特征的内在规律：深度表征在终端训练阶段广泛呈现「神经坍缩（Neural Collapse）」现象，即同类样本向同向致密聚拢，而异类中心之间近似正交或弱相关。面对一般度量空间难以逾越的内存下界，本文的核心切入点在于利用深度表征的聚类内积几何，将流式观测映射为对类别基数严格单调的极值统计量。核心 idea：利用最大值聚合天然丢弃重复观测的机制，基于固定的高斯随机投影构建极值草图 MaxSketch，在同类致密对齐与异类弱相关的几何假设下，将流式序列压缩为单调反映去重数目的标量统计量，以 $\tilde{O}(\log n/\varepsilon^2)$ 内存打破度量空间的平方根瓶颈。

方法详解¶

整体框架¶

MaxSketch 的核心流程分为观测流输入、高斯随机投影与极值维护、全局标量统计量汇聚以及单调读出估计四个阶段。输入数据为单位球面上的高维向量流 $\tilde{X} = \langle \tilde{x}_1, \dots, \tilde{x}_n \rangle \subset \mathbb{S}^{d-1}$，每个观测均围绕某个潜在目标中心受到噪声扰动。算法预先固定一组独立同分布的标准高斯随机向量 $w_1, \dots, w_m \sim \mathcal{N}(0, I_d)$，当数据流依次到达时，在线更新每组投影方向上的当前最大标量投影值，无需缓存历史样本。

当数据流扫描完毕后，草图仅保留 $m$ 个最大投影标量 $M_j(\tilde{X}) = \max_{1 \le i \le n} \langle w_j, \tilde{x}_i \rangle$。随后，算法计算这 $m$ 个最大值的均值 $S(\tilde{X}) = \frac{1}{m} \sum_{j=1}^m M_j(\tilde{X})$。理论分析证明，由于独立中心在高斯随机投影下的极大值期望随中心数量严格递增，且类内扰动被严格控制在可容忍范围内，统计量 $S(\tilde{X})$ 与真实去重目标数 $k^\star$ 之间具备强单调性。最后，通过预计算的无数据几何网格阈值检索，或借助少量弱监督计数样本拟合的一维保序读出函数，即可在常数时间内解码出目标去重数量的乘性估计。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入数据流<br/>n 个单位向量"] --> B["高斯投影与在线极值维护<br/>更新 m 个标量最大值"]
    B --> C["均值聚合统计量<br/>计算标量 S(X)"]
    C --> D["单调读出解码<br/>几何阈值或保序回归"]
    D --> E["输出去重计数估计"]

关键设计¶

1. 几何聚类模型：规范类内对齐与类间弱相关的内积结构

针对任意度量空间中最坏情况输入导致 $\Omega(\sqrt{n})$ 内存下界的困境，该设计将输入序列形式化为 $(\eta, \rho)$-可聚类序列。设定 $k^\star$ 个未知的隐空间单位中心向量 $x^{(1)}, \dots, x^{(k^\star)} \in \mathbb{S}^{d-1}$，要求任意观测 $\tilde{x}_i$ 与其所属中心满足类内内积对齐 $\langle \tilde{x}_i, x^{(r(i))} \rangle \ge 1 - \eta/2$（即扰动向量范数 $\| \tilde{x}_i - x^{(r(i))} \|^2 \le \eta$），同时任意相异中心之间满足类间弱相关 $|\langle x^{(r)}, x^{(s)} \rangle| \le \rho$。这一设计直接契合深度学习自监督学习与分类表征中的神经坍缩特性，摒弃了一般度量空间的对抗性构造，为极值统计提供了具备分析可行性的解析支撑。

2. 极值高斯草图：利用最大值算子天然消除重复频次偏倚

针对传统和/均值聚合容易将出现频率误判为实体基数的缺陷，MaxSketch 采用最大值聚合机制： $$M_j(\tilde{X}) = \max_{1 \le i \le n} \langle w_j, \tilde{x}_i \rangle, \quad S(\tilde{X}) = \frac{1}{m} \sum_{j=1}^m M_j(\tilde{X})$$ 一旦某目标类别的某次观测在投影方向 $w_j$ 上产生了较大投影值，该目标在后续流中无论重复出现多少次，均不会对极大值产生显著推高效应；相反，新目标的出现会引入潜在的更优投影极值，推动整体最大值分布向右平移。借助 Sudakov-Fernique 极值不等式与高斯浓度理论，证明了即使中心之间存在弱相关 $\rho \le c_\rho \varepsilon / \ln n$、类内扰动满足 $\eta \le c_\eta \varepsilon^2 / (\ln n)^2$，投影极大值依然紧密围绕独立高斯极值，并在 $k$ 与 $(1+\varepsilon)k$ 之间保持 $\Omega(\varepsilon / \sqrt{\ln k})$ 的期望可分间隔。

3. 对数级几何阈值检索与保序读出：将高维计数规约为一维单调函数拟合

在获得统计量 $S(\tilde{X})$ 后，算法避免了复杂的非线性解码。在理论分析中，作者设计了比率为 $(1+\varepsilon)$ 的几何网格序列 $t_r = \lceil (1+\varepsilon)^r \rceil$ 与对应的预置判定阈值 $\theta_r$： $$\theta_r := \frac{1}{2} \left( U(t_r) + L(t_{r+1}) \right)$$ 其中 $U(t)$ 与 $L(t)$ 分别为基于 $t$ 个独立标准高斯极大值理论均值构造的上下界容忍区间。根据高斯 1-Lipschitz 函数浓度性质，仅需 $m \ge C \cdot \frac{\ln n \cdot \ln(\ln n / (\varepsilon \delta))}{\varepsilon^2}$ 个高斯投影，即可在全网格上通过并集界保证以至少 $1-\delta$ 的概率命中区间 $[k^\star, (1+\varepsilon)k^\star]$。在实际分布部署中，这一机制进一步体现为：将输入特征与去重计数的依赖完全凝练在标量 $S(\tilde{X})$ 上，使端到端弱监督学习退化为一维保序回归（Isotonic Regression），具备样本复杂度低与泛化稳定的优良特性。

实验关键数据¶

主实验¶

论文在 MNIST、CIFAR-10 以及由 LFW、CelebA 和 CMU Multi-PIE 合并构建的大规模人脸数据流（共 10,206 个独立身份，测试序列长度 $n=20,000$）上进行了详尽评测。在人脸流实验中，提取冻结的 DeepFace VGG-Face 4096 维特征，真实去重人数 $k \in [100, 5100]$，对比了度量空间代表性流式基线 Zhang (2025)。在 CIFAR-10 序列上比较了不同编码器训练机制下的计数表现。

数据集 / 评测任务	评估指标 / 容差	MaxSketch (本文)	对比基线 / 机制	性能差距与表现分析
真实人脸流 ($n=20000, k \le 5100$)	$\pm 50$ 计数准确率	$\ge 60.0\%$	Zhang (2025) ($\alpha=0.40$)	Zhang 基线在 51 个 $k$ 测试点中有 43 个无法达到 $\pm 150$ 准确率
真实人脸流 ($n=20000, k \le 5100$)	$\pm 100$ 计数准确率	$\approx 98.0\%$	Zhang (2025) ($\alpha=0.40$)	本文统计嵌入平滑吸收类内分布重叠，保持近乎全段可用
真实人脸流 ($n=20000, k \le 5100$)	$\pm 150$ 计数准确率	$\approx 100.0\%$	Zhang (2025) ($\alpha=0.40$)	本文在大范围 $k$ 下无系统性偏倚，极值统计量稳定单调
CIFAR-10 ($n_{\text{test}}=10$)	精确准确率 ($\pm 1$ 准确率)	0.70 (0.99)	E2E (纯端到端计数监督)	冻结预训练特征明显优于弱监督从头训练 0.55 (0.85)
CIFAR-10 ($n_{\text{test}}=20$)	精确准确率 ($\pm 1$ 准确率)	0.69 (0.98)	E2E (纯端到端计数监督)	冻结预训练特征表现稳定，E2E 准确率为 0.62 (0.83)
CIFAR-10 ($n_{\text{test}}=50$)	精确准确率 ($\pm 1$ 准确率)	0.70 (0.97)	E2E (纯端到端计数监督)	预训练微调可提升至 0.78 (0.99)，E2E 仅 0.63 (0.92)

消融实验¶

在 MNIST 图像流上，作者深入研究了当训练序列长度较短（$n_{\text{train}} \in \{10, 20, 50\}$）时，模型直接外推到未见过的极长序列（$n_{\text{test}} \in \{150, 250, 500\}$）的泛化能力。由于 1-NN 分类准确率在所有配置下均为 1.00，表明表征空间未退化，长序列下的误差主要来自回归读出头的标定偏置。

训练序列长度 $n_{\text{train}}$	测试 $n_{\text{test}}=150$ (精确 / $\pm 1$)	测试 $n_{\text{test}}=250$ (精确 / $\pm 1$)	测试 $n_{\text{test}}=500$ (精确 / $\pm 1$)	泛化特性说明
$n_{\text{train}} = 10$	0.37 (0.97)	0.25 (0.90)	0.06 (0.78)	短序列训练在外推 50 倍长度时长尾略有低估，但 $\pm 1$ 仍保持高位
$n_{\text{train}} = 20$	0.70 (0.99)	0.58 (0.98)	0.37 (0.96)	随训练长度适度增加，外推精度显著提升，排序信号完整保持
$n_{\text{train}} = 50$	0.99 (1.00)	0.98 (1.00)	0.96 (1.00)	覆盖充分的计数值后，即使序列长度外推 10 倍，精确率仍超过 96%

关键发现¶

聚类几何决定计数成败：在 MNIST 等类内变异极小的数据上，所有聚合算子（MaxSketch、DeepSets、LSTM）均达到接近 100% 的准确率；而在复杂场景中，基于最大值的极值统计抗频次扰动优势明显。
统计嵌入的平滑鲁棒性：Zhang (2025) 的度量空间去重算法极度依赖近重复阈值 $\alpha$，在真实人脸特征类内/类间距离交叠时彻底失效；而 MaxSketch 将输入映射为统计期望，轻微的几何违背仅引起连续平移，保序读出头能自然吸收偏差。
端到端弱监督的表征瓶颈：在 CIFAR-10 上，仅凭序列总计数进行端到端监督很难诱导理想的聚类结构，准确率落后于带监督预训练特征，证明了良好的初始表征几何是高效流式去重的先决条件。

亮点与洞察¶

提出极值草图消减频次干扰：巧妙利用高斯随机投影的最大值运算，在不保留任何历史向量的前提下天然免疫高频重复项的干扰，从信息论结构上解除了去重与频次的耦合。
打破度量空间平方根下界：证明了利用表征学习中常见的类内紧致与类间低内积结构，去重计数的空间复杂度可从 $\tilde{\Omega}(\sqrt{n})$ 下降至多项式对数级 $\tilde{O}(\log n / \varepsilon^2)$，搭建了流式算法与现代深度表征几何的理论桥梁。
统计嵌入将高维流缩聚为一维单调函数：固定的随机投影将复杂的高维流式多集合统计规约为单个单调标量，使得下游弱监督学习转变为极易优化的保序回归。

局限与展望¶

强依赖预训练几何的类间正交性：当输入特征空间语义严重重叠或类内变异过大（破坏 $(\eta, \rho)$-可聚类假设）时，极值统计量的期望差会被压缩，导致分辨精度下降。
理论下界尚未明确闭环：论文证明了在聚类几何下 $\tilde{O}(\log n / \varepsilon^2)$ 的充分性，但该几何假设下的信息论最优下界仍待理论界彻底厘清。
仅提供粗粒度基数而无实体检索能力：MaxSketch 是纯粹的统计量草图，只能估计唯一实体数量，无法向用户返还去重后的具体代表性样本或聚类分配。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 巧妙将高斯极值理论引入连续嵌入流去重，从理论上突破了一般度量空间的平方根内存瓶颈。
实验充分度: ⭐⭐⭐⭐ 包含 MNIST、CIFAR-10 及大规模人脸流对比，消融与泛化分析完备，若补充更多自然图像/文本流实验将更丰富。
写作质量: ⭐⭐⭐⭐⭐ 理论推导清晰完备，从引理、定理到算法还原环环相扣，实验设计针对性极强。
价值: ⭐⭐⭐⭐⭐ 沟通了经典数据流算法与现代深度表征学习，对大规模视频监控、网络流量去重等流式系统具有重要理论和工程启发。

数据集 / 评测任务	评估指标 / 容差	MaxSketch (本文)	对比基线 / 机制	性能差距与表现分析
真实人脸流 (\(n=20000, k \le 5100\))	\(\pm 50\) 计数准确率	\(\ge 60.0\%\)	Zhang (2025) (\(\alpha=0.40\))	Zhang 基线在 51 个 \(k\) 测试点中有 43 个无法达到 \(\pm 150\) 准确率
真实人脸流 (\(n=20000, k \le 5100\))	\(\pm 100\) 计数准确率	\(\approx 98.0\%\)	Zhang (2025) (\(\alpha=0.40\))	本文统计嵌入平滑吸收类内分布重叠，保持近乎全段可用
真实人脸流 (\(n=20000, k \le 5100\))	\(\pm 150\) 计数准确率	\(\approx 100.0\%\)	Zhang (2025) (\(\alpha=0.40\))	本文在大范围 \(k\) 下无系统性偏倚，极值统计量稳定单调
CIFAR-10 (\(n_{\text{test}}=10\))	精确准确率 (\(\pm 1\) 准确率)	0.70 (0.99)	E2E (纯端到端计数监督)	冻结预训练特征明显优于弱监督从头训练 0.55 (0.85)
CIFAR-10 (\(n_{\text{test}}=20\))	精确准确率 (\(\pm 1\) 准确率)	0.69 (0.98)	E2E (纯端到端计数监督)	冻结预训练特征表现稳定，E2E 准确率为 0.62 (0.83)
CIFAR-10 (\(n_{\text{test}}=50\))	精确准确率 (\(\pm 1\) 准确率)	0.70 (0.97)	E2E (纯端到端计数监督)	预训练微调可提升至 0.78 (0.99)，E2E 仅 0.63 (0.92)

训练序列长度 \(n_{\text{train}}\)	测试 \(n_{\text{test}}=150\) (精确 / \(\pm 1\))	测试 \(n_{\text{test}}=250\) (精确 / \(\pm 1\))	测试 \(n_{\text{test}}=500\) (精确 / \(\pm 1\))	泛化特性说明
\(n_{\text{train}} = 10\)	0.37 (0.97)	0.25 (0.90)	0.06 (0.78)	短序列训练在外推 50 倍长度时长尾略有低估，但 \(\pm 1\) 仍保持高位
\(n_{\text{train}} = 20\)	0.70 (0.99)	0.58 (0.98)	0.37 (0.96)	随训练长度适度增加，外推精度显著提升，排序信号完整保持
\(n_{\text{train}} = 50\)	0.99 (1.00)	0.98 (1.00)	0.96 (1.00)	覆盖充分的计数值后，即使序列长度外推 10 倍，精确率仍超过 96%