Google 研究员详解:采样碰撞概率的 LSH 最优性定理
moultano · x · 2026-09-06
Google 研究员 moultano 在讨论中引用自己 2018 年的论文《Maximally Consistent Sampling and the Jaccard Index of Probability Distributions》(arXiv:1809.04052,发表于 ICDMW 2018),说明其最优性结论:当你要以一种方式从某个分布采样、并最大化与另一个未知分布碰撞的概率时,该文给出的算法在很强的意义下是最优的。
论文核心贡献:
- 提出计算概率分布 MinHash 的简单高效算法,稀疏与稠密数据的运行时间均与当时最优方法持平
- 该算法的碰撞概率构成一种新的正向量相似度度量,可视为 Jaccard 指数在概率分布上的自然推广
- 证明了这种基于采样的碰撞概率在任何 LSH(locality sensitive hash)中都是最优的相似度度量
原文是针对「最优性定理是什么」的追问给出的回答。
「研究」频道最新
- LLM 持续学习方法 iSDFT 开源:500+ 实验平衡可塑性与稳定性 — hbouammar · 2026-09-23
- 多项式 Freiman-Ruzsa 定理留下算法难题：如何高效找到子空间 — gautamcgoel · 2026-09-23
- 研究员论证:堆并行 agent 是弱路径,RSI 需要更强 agent — gleech · 2026-09-23
- Courtade–Kumar 猜想获证明:信息论经典问题给出多比特扩展 — abeirami · 2026-09-23
- TimePre 论文登 TMLR:可逆归一化稳住概率时序预测的多假设学习 — _vztu · 2026-09-23
- Agent评测缺的不是榜单 而是可复现的轨迹与日志 — seanwbren · 2026-09-23