大规模文档去重技术 MinHash

对以上文档哈希矩阵中的每一列取最小值 —— 即 “MinHash” 中的 “Min” 的题中之义，我们就能得到该文档最终的 MinHash 值:

从技术上讲，虽然我们通常取最小值，但这并不代表我们一定要取每列的最小值。其他顺序统计量也是可以的，例如最大值、第 k 个最小值或第 k 个最大值 Datasketch 的实现修改而得的。

def embed_func(
    content: str,
    idx: int,
 *,
    num_perm: int,
    ngram_size: int,
    hashranges: List[Tuple[int, int]],
    permutations: np.ndarray,
) -> Dict[str, Any]:
    a, b = permutations
    masks: np.ndarray = np.full(shape=num_perm, dtype=np.uint64, fill_value=MAX_HASH)
    tokens: Set[str] = {" ".join(t) for t in ngrams(NON_ALPHA.split(content), ngram_size)}
    hashvalues: np.ndarray = np.array([sha1_hash(token.encode("utf-8")) for token in tokens], dtype=np.uint64)
    permuted_hashvalues = np.bitwise_and(
        ((hashvalues * np.tile(a, (len(hashvalues), 1)).T).T + b) % MERSENNE_PRIME, MAX_HASH
    )
    hashvalues = np.vstack([permuted_hashvalues, masks]).min(axis=0)
    Hs = [bytes(hashvalues[start:end].byteswap().data) for start, end in hashranges]
    return {"__signatures__": Hs, "__id__": idx}

熟悉 Datasketch 的读者可能会问，为什么我们要费心费力剥离 Datasketch 库提供的所有高级功能？其主要原因并不是因为我们要减少依赖项，而是因为我们想要尽可能地榨取 CPU 的算力。而将多个步骤融合到一个函数中，是更好利用计算资源的手段之一。

由于每个文档的计算互相独立，因此我们可以充分利用 datasets 库的 map 函数来实现并行化:

embedded = ds.map(
	function=embed_func,
	fn_kwargs={
		"num_perm": args.num_perm,
		"hashranges": HASH_RANGES,
		"ngram_size": args.ngram,
		"permutations": PERMUTATIONS,
	},
	input_columns=[args.column],
	remove_columns=ds.column_names,
	num_proc=os.cpu_count(),
	with_indices=True,
	desc="Fingerprinting...",
)

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

局部敏感哈希 (LSH)

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

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

遍历 doc_ids 列的每一行，将其中的文档两两配对就生成了候选对。上表中，我们能生成一个候选对: (0, 1) 。

候选对生成后 ……

很多数据去重的论文或教程讲完上一节就结束了，但在实际项目中我们还涉及如何处理这些候选对的问题。通常，候选对生成后，我们有两个选择:

1. 由于 MinHash 只是一个近似，所以仍需计算两个文档的 N- 元组集合的交并比来算得准确的 Jaccard 相似性。此时，因为 LSH 已经帮我们过滤了不少，所以最终参与计算的候选对的量会大大减少。在 BigCode 项目中，我们起初就采用了这种做法，效果相当不错。
2. 我们还可以直接认可 LSH 选出来的相似对。这里面可能会有个问题: Jaccard 相似性不具传递性，也就是说 $A$ 相似于 $B$ 且 $B$ 相似于 $C$，并不意味着 $A$ 相似于 $C$。所以这里可能会有不少假阳性。通过在 The Stack 数据集上的实验，我们发现，直接认可 LSH 选出来的相似对在很大程度上能提高下游模型的性能，同时还节省了处理时间和训练时间。因此目前我们正慢慢开始转向这种方法。但是，这个经验并不是放之四海而皆准的，如果你准备在自己的数据集上仿效我们的做法，我们建议你在此之前好好检查你的数据集及其特点，然后作出数据驱动的决策。

最后，我们可以用生成的相似文本对构建一个图，在这个图中，重复的文档会被聚至同一个社区或同一个连通子图中。不幸的是， datasets 在这方面帮不上什么忙，因为现在我们需要类似 groupby 的功能，以根据 条带 ID 及 文档在该条带上的取值 对文档进行聚类。下面列出了我们尝试过的一些方案:

方案 1: 老办法，迭代数据集以创建图，然后用一个图处理库对其做社区检测或者连通分量检测。

我们测试下来，该方案的扩展性不怎么好，其原因是多方面的: 首先，整个数据集迭代起来很慢，而且内存消耗很大; 其次，诸如 graphtool 或 networkx 的市面上流行的图处理库创建图的开销较大。

方案 2: 使用流行的 Python 框架 (如 dask ) 及其高效的 groupby 操作。

但迭代慢和创建图慢的问题仍然存在。

方案 3: 迭代数据集并使用并查集 (union find data structure) 对文档进行聚类。

这个方案引入了一个很小的迭代开销，对中等数据集的有不错的效果不错，但在大数据集上还是慢。

for table in tqdm(HASH_TABLES, dynamic_ncols=True, desc="Clustering..."):
	for cluster in table.values():
		if len(cluster) <= 1:
			continue
		idx = min(cluster)
		for x in cluster:
			uf.union(x, idx)

方案 4: 对大数据集，使用 Spark。

我们已经知道到 LSH 的有些步骤是可以并行化的，我们可以用 Spark 来实现它们。Spark 的好处是，它开箱即支持分布式 groupBy ，而且也能很轻松地实现像 Datasketch，而 Datasketch 的 MinHash 实现与 Spark 的原生实现完全不同。我们希望之前的经验和教训能帮助到后面的工作，而不是另起炉灶，进入另一个消融实验的轮回，因此我们选择在 Spark 中自己实现 Datasketch 的 MinHash 算法。

edges = (
	records.flatMap(
		lambda x: generate_hash_values(
			content=x[1],
			idx=x[0],
			num_perm=args.num_perm,
			ngram_size=args.ngram_size,
			hashranges=HASH_RANGES,
			permutations=PERMUTATIONS,
		)
	)
	.groupBy(lambda x:(x[0], x[1]))
	.flatMap(lambda x: generate_edges([i[2] for i in x[1]]))
	.distinct()
	.cache()
)

以下是基于 @geiping_2022 提到基于子字符串的数据去重并没有提高他们模型的下游性能。在使用前，可能还需要对现存数据集进行彻底检查，例如，@gao_2020 声明他们只确保 Pile 本身及其子集都已去重，但不保证其与任何下游基准数据集没有重复，要不要对 Pile 与下游基准数据集进行去重取决于使用者自己。

在数据泄露和基准污染方面，还有很多需要探索的地方。由于 HumanEval 也是 GitHub Python 存储库之一，我们不得不重新训练了我们的代码模型。早期的工作还发现，最流行的编码基准之一的 MBPP@rae_2021 分享了一些关于如何检测和删除它们的有趣的启发式方法。

致谢

题图中的表情符 (Hugging Face、圣诞老人、文档、巫师以及魔杖) 来自于 Noto Emoji (Apache 2.0)。我也庄严保证，这篇博文是我一个字一个字敲出来的，没有使用任何文本生成 API。

非常感谢 Huu Nguyen(@Huu) 和 Hugo Laurençon(@HugoLaurencon) 在 BigScience 项目中的合作，以及 BigCode 项目中每个人一路上的帮助！如果你发现任何错误，请随时联系我: mouchenghao at gmail dot com。

更多资源

• Datasketch (MIT)
• simhash-py 及 simhash-cpp (MIT)
• Deduplicating Training Data Makes Language Models Better (Apache 2.0)
• Gaoya (MIT)
• BigScience (Apache 2.0)
• BigCode (Apache 2.0)

参考文献

• [1] : Nikhil Kandpal, Eric Wallace, Colin Raffel, Deduplicating Training Data Mitigates Privacy Risks in Language Models, 2022
• [2] : Gowthami Somepalli, et al., Diffusion Art or Digital Forgery? Investigating Data Replication in Diffusion Models, 2022
• [3] : Katherine Lee, Daphne Ippolito, et al., Deduplicating Training Data Makes Language Models Better, 2022
• [4] : Loubna Ben Allal, Raymond Li, et al., SantaCoder: Don’t reach for the stars!, 2023
• [5] : Leo Gao, Stella Biderman, et al., The Pile: An 800GB Dataset of Diverse Text for Language Modeling, 2020
• [6] : Asier Gutiérrez-Fandiño, Jordi Armengol-Estapé, et al., MarIA: Spanish Language Models, 2022
• [7] : Jack W. Rae, Sebastian Borgeaud, et al., Scaling Language Models: Methods, Analysis & Insights from Training Gopher, 2021
• [8] : Xi Victoria Lin, Todor Mihaylov, et al., Few-shot Learning with Multilingual Language Models, 2021
• [9] : Hugo Laurençon, Lucile Saulnier, et al., The BigScience ROOTS Corpus: A 1.6TB Composite Multilingual Dataset, 2022
• [10] : Daniel Fried, Armen Aghajanyan, et al., InCoder: A Generative Model for Code Infilling and Synthesis, 2022
• [11] : Erik Nijkamp, Bo Pang, et al., CodeGen: An Open Large Language Model for Code with Multi-Turn Program Synthesis, 2023
• [12] : Yujia Li, David Choi, et al., Competition-Level Code Generation with AlphaCode, 2022
• [13] : Frank F. Xu, Uri Alon, et al., A Systematic Evaluation of Large Language Models of Code, 2022
• [14] : Aakanksha Chowdhery, Sharan Narang, et al., PaLM: Scaling Language Modeling with Pathways, 2022
• [15] : Lewis Tunstall, Leandro von Werra, Thomas Wolf, Natural Language Processing with Transformers, Revised Edition, 2022
• [16] : Denis Kocetkov, Raymond Li, et al., The Stack: 3 TB of permissively licensed source code, 2022
• [17] : Rocky | Project Hail Mary Wiki | Fandom
• [18] : Raimondas Kiveris, Silvio Lattanzi, et al., Connected Components in MapReduce and Beyond, 2014
• [19] : Jacob Austin, Augustus Odena, et al., Program Synthesis with Large Language Models, 2021
• [20]: Amro Abbas, Kushal Tirumala, et al., SemDeDup: Data-efficient learning at web-scale through semantic deduplication, 2023
• [21]: Edith Cohen, MinHash Sketches : A Brief Survey, 2016

英文原文: huggingface.co/blog/dedup

原文作者: Chenghao Mou

译者: Matrix Yao (姚伟峰)，英特尔深度学习工程师，工作方向为 transformer-family 模型在各模态数据上的应用及大规模模型的训练推理。

审校/排版: zhongdongy (阿东)