这节课是数据专题的第二讲，很有老派大数据味道的一节课。
上节课讲了"有什么数据集"，这节课则关注这些处理步骤的细节，会讲很多经典的大数据处理算法，还有一些挺有意思的数学，看看质量过滤和去重到底是怎么工作的。
一、过滤算法三大流派
所有过滤算法解决的都是同一个问题：我手里有一点点我想要的高质量数据T，还有一大堆乱七八糟的原始数据R（比如Common Crawl），我怎么从R里找出和T差不多的东西？
这个问题有两个硬性要求，缺一不可：
- 必须能泛化：我已经有T了，再找一模一样的没有意义，我要的是和T相似但不同的新数据
- 必须快：R可能是整个互联网的数据，如果你用一个70B的Llama去给每个网页打分，那打分的成本比训练模型本身还高，不如直接用这些算力去训练
我们将介绍三种实现这个高层抽象组件的方法。
1. 老当益壮的n-gram模型
第一个方法简单到你可能不敢相信：用一个n-gram语言模型。
就是那个在Transformer出现之前统治了NLP几十年的东西。我们用Kneser-Ney平滑训练一个n-gram模型，然后用它给每个文档打分，保留困惑度最低的那些。
n-gram模型的核心思想特别朴素：一个句子出现的概率，等于每个词在前面n-1个词之后出现的概率的乘积。比如三元模型里，"the cat in"的概率就是"in"出现在"the cat"后面的次数，除以"the cat"总共出现的次数。
但这个方法有个致命问题：稀疏性。当n变大的时候，绝大多数可能的n-gram在语料库里一次都没出现过，哪怕它们是完全合理的句子。所以我们需要Kneser-Ney平滑，简单来说就是：如果我没见过"the cat in"，那我就退一步看"cat in"的概率；如果也没见过，就再退一步看"in"本身的概率。即如果我没有足够的数据支持这个计数，我可以使用更低阶的 n 元语法，然后尝试对其进行插值或回退。
在工业界人们倾向于使用一个名为 KenLM 的特定实现。这是一个专门为速度优化的n-gram库，最早是为机器翻译写的，现在成了数据过滤的标配。
n-gram模型的问题是它根本不懂语义，只看相邻的词有没有一起出现过。比如"the the"在英语里虽然不常见，但比"asdf asdf"常见多了，所以它会觉得重复的"the"是高质量数据。
但没关系，我们不需要一个完美的过滤器，我们只需要一个能把最垃圾的东西过滤掉的过滤器。CCNet就是这么做的：他们把Common Crawl里的所有段落按困惑度排序，只保留前1/3。就是这么简单粗暴的方法，成了第一个Llama数据集的基础。
2. fastText：Facebook的又一个神器
第二个方法是fastText，也是Facebook做的。2016年的时候，所有人都在搞复杂的神经网络分类器，结果Facebook的人跳出来说：你们搞的那些花里胡哨的东西，还不如一个线性分类器好用，而且速度快100倍。
传统的词袋分类器有个问题：参数太多了。如果你的词汇量是8000，要分64类，那你就需要一个8000×64的矩阵，也就是50多万个参数。这还只是一元语法，如果用二元语法，参数数量会爆炸。
fastText的解决方法是先降维再分类，也就是先拿到词 Embedding，再用 Embedding 做分类。
- 先把每个词映射到一个很小的隐藏维度（比如16维）
- 把一个句子里所有词的向量取平均
- 再用一个线性层从16维映射到类别数
这样参数数量就从V×K变成了H×(V+K)，一下子少了两个数量级。其中V是词汇量，K是类别数，H是隐藏维度。
然后为了解决n-gram数量爆炸的问题，他们用了一个技巧：哈希trick。不管有多少个二元语法，我都把它们哈希到固定数量的桶里（比如1000万个）。就算有碰撞也没关系，训练的时候模型自己会处理。
对于质量过滤来说，我们只需要分两类：好文档和坏文档。所以fastText就退化成了一个最简单的线性分类器。
当然，你也可以用BERT甚至Llama来做分类器，效果肯定更好。但如果你要过滤100倍的数据，最后只保留1%，那你的分类器的计算成本必须是训练模型的1%以下。
3. DSIR：更有原则的重要性采样
第三个方法叫DSIR，是2023年提出来的，全称是Data Selection via Importance Resampling（基于重要性重采样的语言模型数据选择）。
这个方法的思路和前两个都不一样：前两个是在判断"这个文档是不是好的"，而DSIR是在问"这个文档和我的目标数据分布有多像"。
首先，快速回顾一下重要性重采样。这在很多领域都有应用，比如粒子滤波和蒙特卡洛方法。假设我想从目标分布p里采样，但我只能从建议分布q里采样。那我可以：
- 先从q里采样一堆样本
- 给每个样本一个权重：w = p(x)/q(x)
- 按照权重重新采样，这样得到的样本就近似服从p分布了
放到数据选择的场景里：
- p就是我们的目标高质量数据的分布
- q就是原始数据的分布
但这里有个问题：我们的目标数据通常很少，根本不足以训练一个好的分布模型。所以DSIR还是用了老办法：哈希n-gram。我们不用训练复杂的模型，就统计一下哈希后的n-gram的频率，用这个来估计分布。
结果怎么样呢？在GLUE基准上，DSIR比fastText有小幅提升。更重要的是，它是一个更有原则的方法，能更好地保持数据的多样性，不会像分类器那样只挑最像目标数据的东西。
所有过滤方法的本质
讲完这三个方法，你会发现它们其实都是同一个框架的不同实现：
- 你有目标数据T和原始数据R
- 你训练一个模型，得到一个评分函数score(x)
- 你根据这个评分从R里挑东西
- KenLM：score(x)是x在T的n-gram模型下的概率，挑概率高的
- fastText：score(x)是x来自T而不是R的概率，挑概率高的
- DSIR：score(x)是p_T(x)/p_R(x)，按照这个概率重采样
二、过滤技术的三个应用
同样的过滤流水线，换个训练数据，就能解决完全不同的问题。
1. 语言识别：我只要英语
第一个应用是语言识别：我只想保留英语的文档，其他语言的都扔掉。
你可能会问：现在的大模型不都是多语言的吗？为什么还要过滤？
有两个原因：
- 数据问题：很多小语言的高质量数据非常难获取和处理
- 计算问题：在计算有限的情况下，如果你把30%的token分给其他语言，那你的英语性能肯定会下降。最典型的例子就是BLOOM，它只在30%的英语数据上训练，结果英语能力比同时期的纯英语模型差很多。
当然，如果你有足够多的算力，多语言模型是很好的，语言之间还有正向迁移。现在所有的前沿模型都是多语言的，能处理100多种语言。
工业界用fastText来做语言识别，他们有一个现成的语言识别模型，支持176种语言，是在维基百科、翻译网站和东南欧新闻上训练的。
Dolma数据集的做法特别简单：运行这个fastText模型，只要英语概率大于0.5就保留。
Percy 现场演示了这个模型，但是结果不太靠谱。这个所有人都在用的模型，其实有很多问题。它对短句、代码、混合语言的处理都很差。还有一个很严重的问题：它可能会把英语的方言（比如非裔美国人英语）识别为非英语，这会引入偏见。
一个精彩的案例：OpenWebMath
三年前有一篇论文叫OpenWebMath，他们想从Common Crawl里筛选出数学文本。他们的方法是把数学当成一种"语言"来处理：
- 先用规则过滤，比如包含LaTeX命令的页面
- 在一个叫ProofPile的数学证明数据集上训练KenLM，保留困惑度低于15000的页面
- 训练一个fastText分类器来预测一个页面是不是数学写作
最有意思的是他们的阈值设置：如果一个页面已经被规则识别为数学，那分类器的阈值只要0.17就可以；如果没有被规则识别，那阈值就要0.8。
结果怎么样？他们生成了147亿个token的数学语料库。用这个语料库训练的1.4B模型，比用20倍通用数据训练的模型数学能力还要强。这就是数据过滤的威力。
2. 质量过滤：什么是"好"数据
质量过滤是最模糊的一个话题，因为没有人能准确定义什么是"好"数据。
有意思的是，早期的很多数据集（比如C4、Gopher、RefinedWeb）都明确说他们没有用基于模型的质量过滤。但最近的论文基本上都投降了：没办法，基于模型的过滤就是效果好太多。
我们来看几个经典的做法：
- GPT-3：他们把非Common Crawl的数据（维基百科、书籍、WebText）作为正样本，Common Crawl作为负样本，训练了一个线性分类器。然后他们不是简单地保留高分文档，而是按照帕累托分布随机保留，这样能保留更多多样性。
- LLaMA：他们用维基百科引用的页面作为正样本。注意，不是维基百科本身，而是维基百科里链接到的那些页面。他们认为能被维基百科引用的页面，质量应该不会太差。
- phi-1：这是我最喜欢的一个例子，完全改变了大家对数据的看法。他们的目标是用教科书级别的高质量数据训练一个很小的模型（1.3B）。他们的做法是：
- 拿GitHub上的Python代码数据集The Stack
- 抽10万个文件，用GPT-4给每个文件打分，评估它对一个想学编程的学生的教育价值
- 用这10万个标注好的样本训练一个随机森林分类器
- 用这个分类器去筛选整个The Stack数据集
结果太惊人了：用原来的数据集训练，96000步之后HumanEval只有12.19%；用过滤后的数据集训练，36000步之后就达到了17.68%。训练步数减少了62%，效果还更好。
学生提问：为什么我们可以用GPT-4来标注数据，而不是直接用GPT-4来过滤所有数据？
回答：因为贵啊。GPT-4标注10万个文件可能只要几千美元，但如果用它去标注几亿个文件，那就要几百万美元了。而我们用GPT-4标注10万个样本，然后蒸馏出一个几毫秒就能跑一个文件的分类器，这才是可扩展的方法。
这也是未来的一个大趋势：以前我们是找人类来标注高质量数据，现在我们可以用大模型来生成我们想要的任何类型的高质量数据，然后蒸馏出快速的分类器。
3. 毒性过滤：去掉不好的东西
最后一个应用是毒性过滤，就是去掉那些仇恨言论、色情内容之类的不好的东西。
例如 Dolma 是在 Jigsaw Toxic Comments 数据集上(这个数据集是维基百科的讨论页评论，由人类标注了有毒、严重有毒、淫秽、威胁、侮辱、身份仇恨这几个标签)训练了两个 FastText 分类器，一个基本上对应仇恨，另一个对应 NSFW（不适合工作场合）。
三、去重
过滤是这个东西我永远不想要，而去重是这个东西还不错，但有一个就够了，不需要其他的。
互联网有多重复
互联网天生就充满了重复。有两种重复：
- 精确重复：比如古腾堡计划的书籍被镜像到了几千个不同的网站上，Common Crawl不知道它们是一样的，会全部存下来。
- 近似重复：比如MIT许可证，在GitHub上出现了几百万次，可能有的地方少了一个逗号，有的地方改了一个名字。还有那些模板生成的内容，比如电商网站的产品描述，只是把国家名字从加拿大换成了美国。
有一个很极端的例子：在C4数据集里，有一句话重复出现了61036次。这句话是：
"通过结合奇妙的创意、有趣的安排，并紧跟该领域的当前趋势，让你更有灵感，赋予艺术气息。如果您能在婚礼中应用其中的部分或全部设计，我们将不胜荣幸。相信我，精彩的创意如果能应用于现实，一定会让周围的人惊叹不已！"
这是亚马逊上一个卖涂鸦面具的产品的描述。我们不知道为什么它会出现在6万多个不同的页面上，但它就是在那里。
没有人想让模型在这句话上训练61000个epoch。这纯粹是浪费算力，而且会导致模型记住这些内容，带来版权和隐私问题。
去重的设计空间
在做去重之前，你要先回答三个问题：
- 什么是一个"项目"：是一个句子？一个段落？还是整个文档？
- 什么是"重复"：是完全一样？还是99%一样？还是50%一样？
- 重复了怎么办：是全部删掉？还是保留一个？
去重最大的挑战是：它本质上是一个成对比较的问题。如果你有1亿个文档，直接两两比较就是1e16次操作，这是不可能完成的。所以我们需要线性时间的算法。
所有去重算法的基础都是：哈希函数。
精确去重
精确去重最简单：计算每个项目的哈希值，然后保留每个哈希值的一个副本。
1 | hash_items = itertools.groupby(sorted(items, key=mmh3.hash), key=mmh3.hash) |
这个方法简单、快速、精确。C4数据集就是这么做的：他们把文档切成3个句子的跨度，然后做精确去重。
如果你有特别多的数据，连存储所有哈希值的内存都没有，那你可以用布隆过滤器。
布隆过滤器是一个特别巧妙的数据结构，它用一个位数组和多个哈希函数来表示一个集合。它的特点是：
- 如果它说一个东西不在集合里，那它肯定不在
- 如果它说一个东西在集合里，那它可能在，也可能不在（假阳性）
你可以通过调整位数组的大小和哈希函数的数量，把假阳性率降到任意低。比如Dolma数据集就把假阳性率设到了1e-15，几乎不可能出错。
近似去重：MinHash + LSH
精确去重只能处理完全一样的内容，但我们还需要处理近似重复。
首先我们需要一个衡量两个文档相似度的指标：杰卡德相似度。两个集合A和B的杰卡德相似度等于它们的交集大小除以并集大小。如果两个文档有99%的词是一样的，那它们的杰卡德相似度就是0.99。
但直接计算所有文档对的杰卡德相似度还是O(n²)的。所以我们需要一个魔法：MinHash。
MinHash是一个哈希函数，它有一个神奇的性质：两个集合的MinHash值相等的概率，正好等于它们的杰卡德相似度。
这怎么可能？其实道理很简单。想象一下，我们把所有可能的词随机打乱顺序。对于集合A来说，MinHash(A)就是这个打乱后的列表里第一个出现在A中的词。
如果两个集合A和B的交集是3个词，并集是5个词，那么第一个出现的词在交集中的概率就是3/5，也就是0.6。这正好就是它们的杰卡德相似度。
太妙了，对不对？但这还不够。因为单个MinHash的碰撞概率等于杰卡德相似度，随机性太强了。我们想要的是：如果相似度大于0.99，就几乎一定碰撞；如果小于0.99，就几乎不碰撞。
这时候就需要**局部敏感哈希（LSH）**了。
LSH的想法是：我们用很多个MinHash函数，然后把它们分成b个"带"，每个带有r个函数。两个文档只要有任意一个带的所有r个哈希值都相同，我们就认为它们是重复的。
这个"与或"结构会产生一个非常锐利的阈值效应。通过调整b和r，你可以精确控制你想要的阈值。比如用b=20，r=450，你就可以得到一个大约0.99的阈值。也就是说，两个文档只要有超过99%的内容是一样的，就几乎一定会被检测为重复；如果低于99%，就几乎不会被检测到。
学生提问：现在合成数据越来越多，很多内容是释义出来的，不是简单的复制粘贴。这些方法检测不出来怎么办？
讲师回答：你说的对。这些基于n-gram的方法对释义完全无能为力。现在有一些新的研究，用语义嵌入来做去重，这样就能检测出语义上相似的内容。但这样做成本高很多，而且你要非常小心，不要把本来就应该多样化的内容也过滤掉了。
另一个学生提问：有没有什么情况我们其实想要重复数据？
讲师回答：当然有。如果一个文档质量特别高，那你其实想要在它上面多训练几个epoch。很多论文在中期训练的时候，都会对高质量数据进行多轮训练。
我觉得最优的做法可能不是完全去重，而是根据一个文档出现的次数来调整它的采样权重。比如取出现次数的平方根或者对数，这样重要的文档会出现更多次，但不会出现61000次这么夸张。
课程总结
这节课提到了很多算法工具：
- 过滤：KenLM、fastText、DSIR
- 应用：语言识别、质量过滤、毒性过滤
- 去重：哈希、布隆过滤器、MinHash、LSH
但这些都只是工具而已。知道这些算法怎么工作只是第一步，真正重要的是花时间和数据打交道。要去看你过滤掉了什么，留下了什么，然后训练一个小模型看看效果，再回来调整你的阈值和参数。这个过程没有捷径，只能靠经验。