一个最小哈希值,凭什么能估出两篇文档有多像?

MinHash 为什么能估 Jaccard

把并集随机排一次序,两篇文档各自排第一的元素相同,当且仅当整个并集的第一名落在交集里——概率正好是 Jaccard。浏览器里做 1,000 次随机置换看它收敛,再看整本书 269 个段落对上的估计误差。

🔀

这是一堂岔路课,挂在第 2 课旁边。第 2 课直接用了一条性质:「两篇文档的最小哈希值相等的概率,等于它们的 Jaccard」。这里把它证出来,再用随机置换在浏览器里验证一遍。

本课一问:一个最小哈希值,凭什么能估出两篇文档有多像?

从一个 5 个元素的例子开始

把两篇文档看成两个 shingle 集合。为了能手算,先用最小的例子:A = {a, b, c, d},B = {b, c, d, e}。交集 {b, c, d} 有 3 个元素,并集 {a, b, c, d, e} 有 5 个,Jaccard = 3/5 = 0.6。

MinHash 的动作是:给所有元素排一个随机顺序,然后看 A 里排最前的元素和 B 里排最前的元素是不是同一个。

证明:只看整个并集的第一名

MinHash 的核心性质(Broder 1997)

[ = ] = /

👆 公式里带下划线的每一项都可以点——点哪项，讲哪项。

例子里:并集 5 个元素,每个当第一名的概率 1/5;第一名是 b、c、d 之一时相等,概率 3/5 = 0.6。

这个证明只用到了一件事:均匀随机的排列里,每个元素当第一名的机会相同。没有用到文本、语言、shingle 的长度——所以它对任何集合都成立。

算法模拟器 · 随机置换 1,000 次(种子固定)

集合 A 集合 B

种子 20260926

整本书上的 269 个段落对:112 个哈希的估计 vs 精确值

🎯

试三件事:① 点几次「置换 1 次」,每次只盯着蓝色的第一名:它带「A∩B」标签时相等,只带「A」或「B」时不等;② 点「跑到 1,000 次」,看蓝线怎么落进绿带、贴近 0.6;③ 把 B 改成 x y z e(和 A 没有交集),再跑——频率会是 0,因为第一名永远不可能同时在两边。

从一个值到一串值:估计有多准

一次置换只给出「相等 / 不等」,是一次抛硬币,正面的概率是 J。用 k 个互相独立的哈希函数,就抛 k 次,相等的比例是 J 的估计。它的标准差是二项分布的 √(J(1−J)/k):

FineWeb 的 k = 112:J = 0.6 时,σ = √(0.6 × 0.4 / 112) = 0.0463。单独一对文档的估计,上下晃 ±0.093(两个标准差)都正常。
J 越接近 0.5,晃得越厉害;J 接近 0 或 1 时很准。上面实验台最下面的散点就是整本书 269 个段落对:平均绝对误差 0.0096,最大 0.0893。大多数段落对的 J 很小,所以估计很准。

这也说明分桶为什么不直接拿「估计的 J > 0.75」去判:单个估计的误差不小,分桶本来就是一个概率筛。第 2 课的公式里,曲线最陡处大约在 s ≈ (1/b)^1/r:FineWeb 14 × 8 是 0.719,RefinedWeb 450 × 20 是 0.737。选 b 和 r,就是在选这个阈值和曲线的陡峭程度。

从排列到哈希函数

对全网所有可能的 5 字片段真的排一次序是做不到的。实际做法:用一个哈希函数 h 给每个 shingle 算一个整数,把「哈希值的大小顺序」当成随机排列,取最小值。只要哈希函数足够「乱」、几乎没有碰撞,它就近似一个均匀随机排列。k 个哈希函数,就是 k 个不同的随机排列。

⚠

常见误解:「相似的文档,MinHash 值也接近。」不是。MinHash 只比较两个值是否相等,相等的概率等于 Jaccard;不相等时,两个值差多少没有任何意义。「相似文档的指纹彼此接近」说的是另一种方法 SimHash——它比较的是两个指纹之间有多少位不同(FineWeb 论文的相关工作里提到,ROOTS 数据集用的就是基于 SimHash 的去重)。

🔍 MinHash 是谁发明的,当时拿来做什么?

Broder 在 1997 年的论文《On the resemblance and containment of documents》里提出 MinHash,要解决的就是判断两篇网页文档有多像——和今天给大模型洗数据是同一个问题,只早了二十多年。「把签名切成若干桶、整桶相等才比较」的分桶技巧属于局部敏感哈希(LSH),教科书《Mining of Massive Datasets》第 3 章「Finding Similar Items」从 shingle、MinHash 到分桶完整推了一遍,还有习题。Broder 1997 的出处核实见 R4 第六节;MMDS 在线版可免费阅读。

证据三问

问	本课的回答
① 它解决什么问题?	不用比较完整的 shingle 集合,只比较 k 个数,就能估出两篇文档的 Jaccard
② 数学上为什么可能有效?	P[最小值相等] = J 可以严格证明;k 次独立估计的标准差 √(J(1−J)/k)
③ 实验上为什么选了它?	能在很多 CPU 上并行、阈值与 n-gram 长度都能调;FineWeb 追随 RefinedWeb 采用它

一句话

📌

随机排一次序,两篇文档各自的第一名相同的概率就是它们的 Jaccard:MinHash 把「有多像」变成了「抛 k 次硬币,有几次相等」。

回到主线

第 3 课:规则都过了、也不重复,没营养的文本怎么筛? → 继续