minhash-大模型输入前的去重

参考

https://zhuanlan.zhihu.com/p/866163175
https://juejin.cn/post/7028173427802374152

问题场景

在大批量的输入给到大模型的时候，耗费的token过多。用hash去重后，还有很多是只有个别文字有变化，其他完全一致的情况。这种时候就需要用“相似”来去重。

MinHash 示例讲解

假如我们 一个语料库，里面有3篇文档，分别如下：

doc_id	内容
0	Deduplication is so much fun!
1	Deduplication is so much fun and easy!
2	I wish spider dog is a thing.

✂️步骤1: 切分n-gram

在本例中，我们使用以单词为基本单元的 3-gram (即每 3 个连续单词组成一个元组)，且不考虑标点符号。

doc_id	3-元组
0	{“Deduplication is so”, “is so much”, “so much fun”}
1	{‘so much fun’, ‘fun and easy’, ‘Deduplication is so’, ‘is so much’}
2	{‘dog is a’, ‘is a thing’, ‘wish spider dog’, ‘spider dog is’, ‘I wish spider’}

步骤2: 生成 n-gram 的 MinHash

使用 MinHash 方法时，每个 N-gram 需要生成多个哈希值，有如下两种策略可选

1. 使用不同的哈希函数进行多次哈希。
2. 使用一个哈希函数进行哈希后再进行多次重排。（这种方法的好处是，只需要计算一次初始哈希值，然后通过一些简单的数学操作就可以得到多个哈希值，节省了计算多个独立哈希函数的开销。）

本例中，我们选择第二种方法，重排生成 5 个哈希值。

N-元组	哈希值
Deduplication is so	[403996643, 2764117407, 3550129378, 3548765886, 2353686061]
is so much	[3594692244, 3595617149, 1564558780, 2888962350, 432993166]
so much fun	[1556191985, 840529008, 1008110251, 3095214118, 3194813501]

Q ：此处为何需要生成多个哈希值？
A ：使用 MinHash 方法时，每个 N-元组生成多个哈希值的主要原因是为了更准确地估计集合之间的相似性，尤其是 Jaccard 相似度。具体来说：

1. 模拟多个哈希函数：通过生成多个哈希值，可以模拟使用多个不同的哈希函数。这有助于捕捉集合中元素的多样性，减少单一哈希函数可能带来的偏差。
2. 提高准确性：生成多个哈希值可以提高 MinHash 签名的准确性。更多的哈希值意味着更细粒度的估计，从而更接近真实的 Jaccard 相似度。
3. 减少随机性影响：单个哈希值可能会因为碰巧的原因导致相似性估计不准确。多个哈希值通过平均化这些随机因素，提供更稳定和可靠的估计。
4. 提高鲁棒性：在实际应用中，数据可能会有噪声或不一致性。多个哈希值可以增加方法的鲁棒性，使其在面对不完美数据时仍能提供合理的相似性估计。

通过这些方式，MinHash 能够在大规模数据处理中有效地比较集合的相似性。
【补充】个人认为就是为了使后续整个篇章的特征表示维度更高，使其从概率上更容易准确的估计相似性。

关于第二种方法的具体例子讲解：

1. 初始哈希计算：

   • 使用一个哈希函数 h 对 N-gram 进行初始哈希计算，得到一个初始哈希值 h(x)。

2. 生成多个哈希值：

   • 通过数学变换生成多个哈希值。例如，可以使用线性变换的方法。

   • 设定 k 对变换参数 (a_i, b_i)，其中 i 从 1 到 k。这些参数可以是随机选择的常数。

   • 计算多个哈希值 h_i(x) 的公式为：
     $$h_i(x)=(a_i\cdot h(x)+b_i)\mathrm{mod}c$$

   • 其中，c 是一个大的质数，用于减少哈希碰撞。

示例

假设我们有一个 N-gram “abc”，并且我们选择的哈希函数 h 计算结果为 h(“abc”) = 123456。我们想生成 3 个哈希值：

• 选择变换参数：(a_1, b_1) = (2, 3), (a_2, b_2) = (5, 7), (a_3, b_3) = (11, 13)
• 选择质数 c = 10007

计算哈希值：

1. $h_1("abc")=(2\cdot 123456+3)\mathrm{mod}10007=246915\mathrm{mod}10007=8412$

2. $h_2("abc")=(5\cdot 123456+7)\mathrm{mod}10007=617287\mathrm{mod}10007=1233$

3. $h_3("abc")=(11\cdot 123456+13)\mathrm{mod}10007=1358016\mathrm{mod}10007=5678$

通过这种方法，我们只需一次计算初始哈希值，然后通过简单的线性变换生成多个哈希值，节省了计算多个独立哈希函数的开销。

步骤3: 由n-gram的MinHash生成doc的MinHash

doc_id	MinHash
0	[403996643, 840529008, 1008110251, 2888962350, 432993166]
1	[403996643, 840529008, 1008110251, 1998729813, 432993166]
2	[166417565, 213933364, 1129612544, 1419614622, 1370935710]

对以上文档哈希矩阵中的每一列取最小值 —— 即 “MinHash” 中的 “Min” 的题中之义，我们就能得到该文档最终的 MinHash 值。
【注意】其他顺序统计量也是可以的，例如最大值、第 k 个最小值或第 k 个最大值。

minhash计算完毕之后，每个文档都被映射成了一个整数数组。为了弄清楚哪些文档彼此相似，我们需要根据这些指纹对它们进行聚类。轮到 局部敏感哈希 (Locality Sensitive Hashing，LSH) 闪亮登场了。

步骤4:局部敏感哈希 (LSH)

LSH 将指纹数组按行分成若干个条带 (band)，每个条带的行数相同，如果遇到最后一个条带行数不足，我们就直接忽略它。以条带数 2 为例，每个条带有 2 行，具体组织如下:

doc_id	MinHash	条带
0	[403996643, 840529008, 1008110251, 2888962350, 432993166]	{0: [403996643, 840529008], 1: [1008110251, 2888962350]}
1	[403996643, 840529008, 1008110251, 1998729813, 432993166]	{0: [403996643, 840529008], 1: [1008110251, 1998729813]}
2	[166417565, 213933364, 1129612544, 1419614622, 1370935710]	{0: [166417565, 213933364], 1: [1129612544, 1419614622]}

Q ：此处为何要划分为条带？
A ：在局部敏感哈希（LSH）中，将 MinHash 签名划分为条带（band）的目的是为了在计算效率和相似性检测之间找到一个平衡。具体原因包括：

1. 提高效率：通过划分条带，可以减少需要比较的文档对数。只有在至少一个条带中哈希值相同的文档才会被进一步考虑为可能的相似对。这样可以显著减少计算量。
2. 控制相似性阈值：条带和行数的选择决定了相似性的敏感度。更多的条带和较少的行数意味着更高的敏感性（更容易找到相似的文档），而较少的条带和更多的行数意味着更严格的相似性要求。
3. 减少误报和漏报：通过调整条带的数量和每个条带的行数，可以平衡误报（false positives）和漏报（false negatives）。这允许系统在保持较低的误报率的同时，仍能有效地检测到相似的文档。
4. 灵活性：分成多个条带后，可以灵活地调整参数以适应不同的应用需求。不同的条带配置可以适应不同的相似性阈值要求。

通过这种方式，LSH 能够在大规模数据集中高效地识别潜在的相似文档对。

步骤5: 分桶

若两个文档在某条带上 MinHash 值相同，这两个文档就会被聚到同一个桶中备选。

条带 ID	条带值	doc_ids
0	[403996643, 840529008]	0, 1
1	[1008110251, 2888962350]	0
1	[1008110251, 1998729813]	1
0	[166417565, 213933364]	2
1	[1129612544, 1419614622]	2

步骤6: 桶内相似度计算

由于 MinHash 只是一个近似，所以仍需计算两个文档的 N-元组集合的交并比来算得准确的 Jaccard 相似性。此时，因为 LSH 已经帮我们过滤了不少，所以最终参与计算的候选对的量会大大减少。

总结：

基于 MinHash 进行文本去重的流程应为：

1. 读取待去重的文本条目（假设共有 N 条文本）；
2. 针对每条文本条目（假设文本拆分后词的数量为 M）：
   2.1 使用 N 元词袋模型转化文本条目（转换后会得到 M-1 个 ngram 组）；
   2.2 针对转换后的 ngram 表示（假设为词袋大小为 p），使用 MinHash 将文本条目转换为固定长度的向量表示（假设向量大小为 k，则完成这一步需要 p!*(M-1) 次循环）；
   2.3 将文档向量表示按固定尺寸拆分为 LSH 带（假设带宽为 l，则一个文档包含 k//l 个 LSH 带）；
3. 针对所有的文档，如果两个文档中包含相同的 LSH 带，则将其放置到同一个 LSH 桶中（最多会生成 N*(N-1)*(k/l) 个桶，此时每个桶中只包含一个元素；最少会生成一个桶，此时桶中包含 N 个元素）；
4. 针对所有包含复数个文本条目的桶，计算桶中文本条目间的 ngram 组的 Jaccard 相似度，如果相似度大于阈值则标记为重复项目（当上一步只生成一个桶时是最坏情况，需要 N*(N-1) 次循环)；
5. 使用上一步得到的重复条目标记即可获取去重后的结构。

根据上面的流程可知，该算法的时间复杂度为：O(N+p!(M-1)+N(N-1)*(k/l)+N(N-1))，只要文本条目中不包含长度大于 N^2 的条目，即可认为该方法的时间复杂度为 O(N^2)。

后记

理论上，直接算Jaccard相似度的结果最准。但海量文本直接求Jaccard相似度复杂度太高，两个文档需要逐个词比较，为降低复杂度，我们使用两个文档的最小哈希值相等的概率来等价于两个文档的Jaccard相似度，并可以证明两者是相等的。具体证明参考：
https://zoe.red/2024/508.html

代码实现：
https://ezirmusitua.site/blog/dedupe-text-with-min-hash#minhash-%E7%9A%84%E4%BB%A3%E7%A0%81%E5%AE%9E%E7%8E%B0