本文是《LLM 时代的经典机器学习：只讲它在哪里重现》系列的第 5 篇（共六篇）。上一篇：无监督——K-Means、PCA 与 embedding 聚类；下一篇：评估——从混淆矩阵到 judge 的一致性。

预训练语料里有大量重复：同一篇文章的几十个转载、改了几个词的模板页、复制粘贴的代码。重复的数据让模型记忆而不是学习，去重是数据工程里收益最确定的一步。精确去重（对整段文本取 hash）只能抓完全一样的副本；近似去重要处理”大部分一样”的文本，标准做法是 MinHash + LSH。它是无监督学习里”相似度估计”的一个漂亮应用——三个经典元素（集合相似度、随机化估计、用概率分桶换掉两两比较）没有一个是深度学习，但在 15T token 上做去重，没有它寸步难行。这一篇把它的概率算清楚。

全篇的核心问题是：

两段文本”相似”到什么程度算重复？MinHash 的阈值怎么定？为什么不用两两比较？

一、总览

1. 三步

文本 → n-gram 集合           Jaccard J = |A ∩ B| / |A ∪ B|                    "相似"的定义
集合 → k 个 MinHash 签名      P(签名相等) = J → 相等比例是 J 的无偏估计        用 k 个数代替整个集合
签名 → 分 b 组每组 r 个       任一组全等即候选：P = 1 − (1 − s^r)^b            用概率分桶换掉 O(n²)

2. 本文的章节安排

配套脚本：05_minhash_lsh.py（纯 NumPy）。

二、Jaccard

1. 把文本变成集合

先把一段文本切成 n-gram 集合：连续 \(n\) 个词（或字符）为一项，去重。”the quick brown fox” 的词级 2-gram 集合是 {the quick, quick brown, brown fox}。\(n\) 取 5 左右：太小（1-gram = 词袋）任何两段用词相近的文本都”相似”，太大一点改动就让所有 n-gram 都变。

2. 交并比

两个集合 \(A, B\) 的 Jaccard 相似度：

——共有的 n-gram 占全部 n-gram 的比例，取值 \([0, 1]\)，完全相同为 1，没有共同项为 0。一段 100 个词的文本改掉 5 个词，词级 5-gram 大约有 25 个受影响，\(J \approx (100 - 25) / (100 + 25) = 0.6\)。

为什么不用编辑距离？编辑距离是 \(O(\lvert A \rvert \cdot \lvert B \rvert)\) 的动态规划，且不能像集合那样被压缩成几个数——下一章的 MinHash 只对集合相似度成立。

三、MinHash

1. 问题

直接算 Jaccard 要存整个集合、两两求交——\(n\) 段文本要算 \(n^2 / 2\) 次集合运算。MinHash 用 \(k\) 个整数代替整个集合，且两个签名的比较能估计 Jaccard。

2. 一行证明

取一个随机 hash 函数 \(h\)（把每个 n-gram 映成一个大整数，相当于给全体 n-gram 一个随机排列），定义集合的 MinHash 为 \(\min_{a \in A} h(a)\)——集合里 hash 值最小的那个元素。

两个集合的 MinHash 相等的概率恰好等于 Jaccard：

证明：\(\min h(A) = \min h(B)\) 当且仅当 \(A \cup B\) 里 hash 值最小的那个元素同时属于 \(A\) 和 \(B\)（即属于 \(A \cap B\)）。\(h\) 是随机的，\(A \cup B\) 里每个元素成为”最小”的概率相同，所以这个概率是 \(\lvert A \cap B \rvert / \lvert A \cup B \rvert\)。一行。

3. \(k\) 个签名

用 \(k\) 个独立的 hash 函数得到 \(k\) 个签名；两个集合签名相等的比例就是 \(J\) 的估计——\(k\) 次伯努利试验、成功概率 \(J\)（L0 第四篇），估计的标准差是 \(\sqrt{J(1 - J) / k}\)（L0 第八篇的标准误）。

改动词数   真实 Jaccard   k=16 估计   k=128 估计   k=1024 估计
     0        1.000       1.000       1.000        1.000
     2        0.790       0.812       0.820        0.791
     5        0.637       0.688       0.609        0.646
    10        0.337       0.438       0.414        0.334
    20        0.023       0.000       0.000        0.027
估计的标准差 ≈ √(J(1−J)/k)：k=128 时约 ±0.04

\(k = 16\) 抖动大（0.337 估成 0.438），\(k = 128\) 到 ±0.04，\(k = 1024\) 到 ±0.015。用 128 个整数（512 字节）代替一个几百个 n-gram 的集合，还能以 ±0.04 的精度比较相似度——这是 MinHash 的全部价值。实际系统用 128 到 256 个。

实现上不需要 \(k\) 个不同的 hash 函数：一个 hash 函数 \(h_0\) 加 \(k\) 组随机的 \((a_i, b_i)\)，\(h_i(x) = (a_i h_0(x) + b_i) \bmod p\)（\(p\) 是一个大素数），脚本就是这么做的。

四、LSH

1. 还是 \(O(n^2)\)

有了签名，比较两段文本从”求集合交并”变成”比 128 个整数”，快了，但仍然要两两比较——\(10^9\) 段文本是 \(5 \times 10^{17}\) 对，不可能。

2. 分组分桶

局部敏感哈希（LSH）的想法：把 \(k\) 个签名分成 \(b\) 组（band），每组 \(r\) 个（\(k = b \times r\)）；每组的 \(r\) 个签名拼在一起再 hash 成一个桶号；任何一组落进同一个桶的两段文本成为候选对，只对候选对精确算 Jaccard。

签名 [128 个整数] ──分成 b=16 组、每组 r=8 个──►  组 1 → 桶 A₁   组 2 → 桶 A₂  …  组 16 → 桶 A₁₆
另一段文本                                        组 1 → 桶 B₁   组 2 → 桶 B₂  …
                                                  任一 Aᵢ = Bᵢ → 候选对

3. S 曲线

两段 Jaccard 为 \(s\) 的文本：一组的 \(r\) 个签名全相等的概率是 \(s^r\)；某一组不全等是 \(1 - s^r\)；\(b\) 组全都不全等是 \((1 - s^r)^b\)；所以成为候选的概率是

这是一条 S 形曲线：\(s\) 小时接近 0，\(s\) 大时接近 1，中间陡峭地过渡。

    s     b=14,r=8     b=8,r=16     b=28,r=4     b=20,r=5
 0.30       0.0009       0.0000       0.2037       0.0475
 0.50       0.0533       0.0001       0.8359       0.4701
 0.60       0.2111       0.0023       0.9795       0.8019
 0.70       0.5645       0.0263       0.9995       0.9748
 0.75       0.7716       0.0774       1.0000       0.9956
 0.80       0.9235       0.2042       1.0000       0.9996
 0.90       0.9996       0.8059       1.0000       1.0000
 0.95       1.0000       0.9903       1.0000       1.0000

b=14, r= 8: 曲线在 s ≈ 0.685 处过 50%
b= 8, r=16: 曲线在 s ≈ 0.856 处过 50%
b=28, r= 4: 曲线在 s ≈ 0.395 处过 50%

曲线过 50% 的位置 \(s_{50} = (1 - 0.5^{1/b})^{1/r}\) 就是这套参数的阈值。FineWeb 用 \(b = 14, r = 8\)（112 个 hash）：\(s = 0.5\) 时候选概率 5%，0.7 时 56%，0.8 时 92%，0.9 时 99.96%，曲线在 0.685 过 50%——这就是”Jaccard 大于约 0.7 视为重复”的来源，它不是拍脑袋定的，是这组 \((b, r)\) 的 S 曲线中点。

调整的方向：\(r\) 大更陡更严（\(b = 8, r = 16\) 阈值到 0.856，只抓几乎相同的），\(b\) 大更宽松（\(b = 28, r = 4\) 阈值到 0.395，改一半词也算候选）。\(b \times r\) 固定时二者此消彼长；想两头都好就加总签名数 \(k\)。

五、在 2000 段文本上跑一遍

脚本造了 1700 段随机文本、再从中复制 300 段各改掉 1–6 个词做近重复，用 \(b = 14, r = 8\) 去重：

两两比较要算 1,999,000 对 Jaccard；LSH 只产生 267 个候选对（0.01%），再对候选精确算
300 组真实近重复的 Jaccard 分布: 最小 0.64 / 中位 0.81 / 最大 0.96
Jaccard ≥ 0.7 的真实对 254 个，其中 LSH 找到 226；候选里 Jaccard ≥ 0.7 的共 236（多出来的是碰巧相似的随机对）
漏掉的都是 Jaccard 低于阈值的：改了 5–6 个词的对 J≈0.6，按 S 曲线只有约 21% 概率成候选

三件事：

• 两两比较 200 万对 → 267 个候选，工作量降到万分之一。\(n\) 越大收益越大：\(10^9\) 段文本两两比较不可能，LSH 的候选数与真实重复对数同阶。
• Jaccard ≥ 0.7 的 254 对里找到 226（89%）。漏掉的 28 对 Jaccard 在 0.7 附近——S 曲线在那里只有 56%，本来就是一半一半。想抓全就把阈值往下调（增 \(b\)）或增 \(k\)。
• 候选里有 10 对是碰巧相似的随机对（236 − 226）——精确算 Jaccard 那一步会过滤掉不够相似的；LSH 只负责”不漏太多”，”不错杀”由后面的精确比较负责。

改了 5–6 个词的对 Jaccard 约 0.6，只有 21% 的概率成候选。这不是 bug，是阈值的定义：你说了 0.7 以下不算重复。

六、工程上的几件事

• 词级还是字符级 n-gram：英文用词级 5-gram（FineWeb）；中文没有天然分词，用字符级 5–10 gram 或先分词。
• 精确去重先做：对整段文本（或归一化后的文本）取一个 hash，完全相同的先去掉——便宜、没有误差，能去掉一大半。MinHash 处理剩下的近重复。
• 文档内 vs 跨文档：跨文档去重是本篇的内容；文档内的重复（同一页面重复的导航栏、页脚）用行级 / 段级的精确 hash 处理。
• 去重多少合适：去重太狠会把”合理的重复”（高质量的教科书内容被大量引用）也去掉。实践里常按 Jaccard 阈值去重后再对高质量来源做”上采样”补回来——去重是为了控制重复的分布，不是消灭一切重复。L4 预训练系列第三篇讲这些取舍。
• 规模：15T token 的去重在几百台机器上跑几天；签名的生成是 embarrassingly parallel，分桶是一次 shuffle。datatrove、text-dedup 一类库把这套流程封装好了，但参数 \((k, b, r)\) 要自己按本篇的 S 曲线定。

七、自测

1. 两段 100 个词的文本有 90 个词级 5-gram 相同、各自有 10 个不同，Jaccard 是多少？
2. 为什么 MinHash 相等的概率恰好是 Jaccard？用一句话说出证明的关键。
3. \(k = 64\) 个签名估计 \(J = 0.5\)，标准差多少？想到 ±0.02 要多少个签名？
4. \(b = 16, r = 8\)（128 个 hash）的阈值大约在哪？比 \(b = 14, r = 8\) 更严还是更松？
5. 一个团队说”我们用 MinHash 去掉了所有 Jaccard > 0.8 的重复”。按 \(b = 14, r = 8\) 的曲线，\(J = 0.8\) 的对有多少概率被漏掉？

答案要点：（1）\(90 / (90 + 10 + 10) = 0.82\)。（2）\(A \cup B\) 里 hash 最小的元素在 \(A \cap B\) 里的概率 = 交的大小 / 并的大小，因为随机 hash 下每个元素成为最小的概率相同。（3）\(\sqrt{0.25 / 64} = 0.0625\)；\(0.25 / 0.02^2 = 625\) 个。（4）\((1 - 0.5^{1/16})^{1/8} \approx 0.67\)；更松一点（\(b\) 大）。（5）\(1 - 0.9235 = 7.7\%\)——”所有”是不准确的，LSH 是概率算法。

八、本文小结

• Jaccard \(= \lvert A \cap B \rvert / \lvert A \cup B \rvert\)，在 n-gram 集合上定义”相似”；改 5% 的词大约 0.6。
• MinHash：随机 hash 取最小值，两个集合最小值相等的概率恰好等于 Jaccard（一行证明：并集里最小的元素落在交集里的概率）；\(k\) 个签名相等的比例是无偏估计，标准差 \(\sqrt{J(1-J)/k}\)，\(k = 128\) 时 ±0.04——用 512 字节代替整个集合。
• LSH：\(k\) 个签名分 \(b\) 组每组 \(r\) 个，任一组全等即候选；\(P = 1 - (1 - s^r)^b\) 是 S 曲线，过 50% 的位置 \((1 - 0.5^{1/b})^{1/r}\) 就是阈值。FineWeb 的 \(b = 14, r = 8\) 阈值 0.685——“Jaccard > 0.7 算重复”是这条曲线的中点；\(r\) 大更严、\(b\) 大更松。
• 2000 段文本：200 万对 → 267 个候选（万分之一）；阈值以上的对找到 89%，漏掉的都在阈值附近；LSH 负责不漏，精确比较负责不错杀。
• 工程：精确去重先做；词级 / 字符级 n-gram 按语言定；去重是控制重复的分布而不是消灭重复；参数 \((k, b, r)\) 按 S 曲线定。

下一篇是本系列最后一篇：评估——混淆矩阵、阈值的权衡、AUC、类别不平衡、校准、交叉验证、配对检验、多重比较，以及每一个在 LLM 评测里的陷阱。

• 上一篇
  LLM 时代的经典机器学习（04）：无监督——K-Means、PCA 与 embedding 聚类
• 下一篇
  LLM 时代的经典机器学习（06）：评估——从混淆矩阵到 judge 的一致性