A4 · Data（Common Crawl → 可用的预训练数据）
年份 2026（Spring 2026）—— 往年（2025 / 2024）题面不同，见「作业说明」
分值 未记录 ✗（官方主页没有公布各项作业的比重 ✓ 不推断 ✗）
发布 / 截止 5 月 6 日发布 / 5 月 20 日截止（L16）（官方日程标注 tentative / 暂定 ✓）
算力 训练对比环节需 GPU（过滤/去重本身是 CPU 与磁盘密集 ✓）
配哪几讲 候选（机器按术语匹配，供参考）：第13讲 §六、真实数据集演进史（2018 → 2024）；第13讲 §三、数据从哪来：互联网没你想的那么简单；第14讲 §3. 去重：从精确重复到近似重复；第14讲 §导览
代码仓库 https://github.com/stanford-cs336/assignment4-data
官方题面 PDF（本地原件在 _local/A4/）

官方原文：Convert raw Common Crawl dumps into usable pretraining data. Perform filtering and deduplication to improve model performance.

做什么

题面来自官方材料（本地原件在 _local/，官方链接见「材料」）。 编号是原件的编号（notebook 是 cell 序号、PDF 是页码），方便跟官方题面对号。 本项目不提供答案（D53）。

第 1 页

CS336 Assignment 4 (data)：为语言建模过滤数据

版本 26.0.1

CS336 Staff

2026 年春季

1 作业概览

在本作业中，你将获得一些关于过滤 Web crawls 以创建 language modeling 数据的实践经验。

你将实现什么。

  1. 将 Common Crawl HTML 转换为文本。
  2. 用多种方法过滤提取出的文本（例如有害内容、个人可识别信息等）。
  3. 对训练数据去重（deduplicate）。

你将运行什么。

  1. 在不同数据集上训练 language models，以更好地理解特定处理决策对性能的影响。

代码长什么样。

所有作业代码以及这份 writeup 都可在 GitHub 上获取：github.com/stanford-cs336/assignment4-data

请 git clone 该仓库。如果有任何更新，我们会通知你，你可以 git pull 获取最新版本。

  1. cs336_basics/*：此文件夹包含用于训练我们在 assignment 1 中构建的模型的代码。该模型经过了少量优化，将 assignment 1 中一些手写的组件替换为 PyTorch 原生对应实现（例如，使用 PyTorch 内置的 cross-entropy kernel）。我们还包含了一个支持多 GPU distributed data parallel 训练的训练脚本。你将使用这个脚本来在你过滤后的数据上训练模型。
  2. cs336_data/*：这是你编写 assignment 4 代码的地方。我们创建了一个名为 cs336_data 的模块，其中包含 starter code 和该作业的占位符。
  3. tests/*.py：包含你必须通过的所有测试。这些测试会调用定义在 tests/adapters.py 中的 hooks。你需要实现 adapters，把你的代码连接到测试。编写更多测试和/或修改测试代码可能有助于调试你的代码，但你的实现应当通过原始提供的测试套件。
  4. README.md：此文件包含有关预期目录结构的更多细节，以及一些关于设置环境的基本说明。

如何提交。

你将向 Gradescope 提交以下文件：

第 2 页

2 过滤 Common Crawl

虽然 large language models 主要是在互联网数据上训练的，但大多数研究者并不会为了给自己的模型获取训练数据而构建 Web crawler。相反，他们使用公开可用的 crawls。最流行的公开 Web crawl 来自 Common Crawl，这是一个非营利组织，提供免费的网页语料库，提供“超过 2500 亿个页面，时间跨度 17 年”[注 1]。

然而，正如我们将看到的，把 Common Crawl（CC）的 dump 转换成可用于 language model 训练的数据需要大量工作。例如，网页的原始数据是 HTML，而我们想从中提取文本。此外，许多页面可能质量很低、是精确重复或几乎重复、含有有害内容，或包含敏感信息，而我们可能想把这些页面过滤掉，或从数据集中移除其内容中不想要的部分。在本作业中，我们将搭建一个流水线，执行其中若干步骤，把原始互联网数据转换成可用于 language models 的训练集。

2.1 查看数据

在实现任何东西之前，先查看原始数据并对其有个感觉总是有用的。CC 数据以三种格式提供：

对于下面的问题，我们将查看一个 WARC 文件及其对应的 WET 文件。这些文件属于 2026 年的一次 Common Crawl crawl，下载方式如下：

# Download a sample WARC file.
$ wget https://data.commoncrawl.org/crawl-data/CC-MAIN-2026-12/segments/1741613651012.6/warc/CC-MAIN-20260310152245-20260310182245-00000.warc.gz
# Download its corresponding WET file.
$ wget https://data.commoncrawl.org/crawl-data/CC-MAIN-2026-12/segments/1741613651012.6/wet/CC-MAIN-20260310152245-20260310182245-00000.warc.wet.gz

这些文件位于：

WARNING: 这些文件包含完全未过滤的互联网页面，其中可能包含大量潜在有害内容。如果你看到一篇你不想读的文档，尽可以继续滚动并跳到另一篇。

[注 1] https://commoncrawl.org/

第 3 页

Problem (look_at_cc)：查看 Common Crawl（4 分）

(a) 使用上面路径提供的 WARC 文件副本。我们来看这个文件中的第一个页面。这是一个 gzip 压缩文件，你可以用以下命令浏览其内容：

$ zcat /shared-data/CC/example.warc.gz | less

less 让你用键盘方向键、Page Up、Page Down 浏览文件。要退出，按“q”。

查看第一个网页。它的 URL 是什么？它现在还能访问吗？通过查看原始 HTML，你能判断这个页面似乎是在讲什么吗？

Deliverable: 用 2–3 句话回答。

(b) 现在来看对应的 WET 文件：

$ zcat /shared-data/CC/example.warc.wet.gz | less

注意，WET 文件包含 HTTP headers（例如 Content-Length），它们不属于提取出的文本内容。如果你查看第一个示例，你会看到其中包含从你刚才看到的原始 HTML 中提取出的文本。

注意，提取出的文本中有很多让人联想到 HTML 结构，而不是页面真正的主内容。你看到的文本中，有没有哪些部分你认为本应被提取器过滤掉？思考一下这些文本作为训练数据的质量：用看起来像这样的文本训练模型，可能会出什么问题？反过来，模型可能从这个页面中提取出哪些有用信息？

Deliverable: 用 3–4 句话回答。

(c) 什么算作一个好的训练示例，高度依赖上下文。描述一个应用领域，在这个领域中，把这个示例保留在训练数据里可能有用；再描述一个可能没用的领域。

Deliverable: 用 1–2 句话回答。

(d) 我们再看一些例子，以更好地了解 Common Crawl 里有什么。查看另外 25 条 WET records。对于每条 record，非常简要地评论文档的语言（如果你能识别的话）、域名、它是什么类型的页面等。在你看到一个你认为“高质量”的网页之前，需要看多少个示例？

Deliverable: 对 25 个文档做简要标注，包括文档语言、域名、页面类型，以及关于文档的其他杂项备注。还需要给出：在你看到一个高质量示例之前，经过了多少个示例。

2.2 HTML 到文本的转换

正如你查看上面的 WARC 和 WET 文件时可能已经意识到的，从 HTML 中提取文本很有挑战性。通常，任何提取过程都会寻找 HTML 中的可见内容（例如 <p> 标签，这些标签本应包含文本块）。但这仍然可能提取出比我们在 Web 浏览器中打开页面时所认为的主内容多得多的东西。例如，打开 StackOverflow 时，主内容在问题和回答中，但从技术上说，菜单选项、指向其他 StackExchange 中无关页面的链接、页脚、注册或登录链接——这些都是可见文本，而要把它们与页面的主内容可靠地区分开来是很困难的。

第 4 页

许多工具都实现了文本抽取流程。在本作业中，我们将使用 Resiliparse[注 2] 库来执行文本抽取。Resiliparse 还会帮助解决一个更基础的问题：检测包含原始内容的字节的文本编码。尽管 Web 上的大多数页面都采用 UTF-8 编码（根据 Wikipedia，占 98.2%），我们的文本抽取流程也应能稳健处理其他编码。

注意：

我们建议使用 FastWARC 库来遍历每个 WARC 文件中的记录。具体来说，以下类可能会有帮助：

python from fastwarc.warc import ArchiveIterator, WarcRecordType

问题 (extract_text)：HTML 转文本（3 分）

(a) 编写一个函数，从包含原始 HTML 的字节串中抽取文本。使用 resiliparse.extract.html2text.extract_plain_text 执行抽取。该函数需要一个字符串，因此你需要先将字节串解码为 Unicode 字符串。注意，输入字节串可能不是以 UTF-8 编码的，因此你的函数应能在 UTF-8 失败时检测编码。Resiliparse 还提供 resiliparse.parse.encoding.detect_encoding()，它可能会有用。

交付物： 一个函数，它接收包含 HTML 的字节串并返回包含抽取文本的字符串。实现适配器 [run_extract_text_from_html_bytes]，并确保它通过 uv run pytest -k test_extract_text_from_html_bytes。

(b) 在单个 WARC 文件上运行你的文本抽取函数。将其输出与对应 WET 文件中抽取的文本进行比较。你注意到哪些差异和/或相似之处？哪种抽取看起来更好？

交付物： 用 2-3 句话回答，比较并对比你自己的函数抽取的文本与 WET 文件中抽取的文本。

2.3 语言识别

Web 上包含用数千种语言编写的页面。但是，要在大多数计算预算下训练一个能够大规模有效利用如此多样数据的多语言模型是很有挑战性的。因此，许多源自 Common Crawl 的语言建模训练集只包含有限语言集合的数据。

用于此目的的一个有用库是 fastText（https://fasttext.cc），它提供高效的文本分类器。该库既提供在你自己的数据上训练分类器的基础设施，也提供一组预训练模型，包括用于语言识别的模型。你可以从 https://fasttext.cc/docs/en/language-identification.html 下载 fastText 语言识别模型 lid.176.bin；它也可在 /shared-data/classifiers/lid.176.bin 获取。

通常，语言过滤器使用分类器给出的分数来决定是否保留给定页面。使用 fastText 语言识别分类器实现一个语言识别过滤器，它应给出一个非负分数，表示其对该预测的置信程度。

[注 2] https://resiliparse.chatnoir.eu/en/stable/index.html

第 5 页

问题 (language_identification)：语言识别（6 分）

(a) 编写一个函数，它接收一个 Unicode 字符串，并识别该字符串中出现的主要语言。你的函数应返回一个二元组，包含语言标识符以及一个 0 到 1 之间的分数，表示其对该预测的置信程度。

交付物： 一个执行语言识别的函数，给出其最可能的语言预测和分数。实现适配器 [run_identify_language]，并确保它通过 uv run pytest -k test_identify_language 中的两个测试。注意，这些测试假定英语（“en”）和中文（“zh”）使用特定的字符串标识符，因此如有必要，你的测试适配器应执行任何适用的重新映射。

(b) 语言模型在推理时的行为在很大程度上取决于其训练数据。因此，数据过滤流程中的问题可能会导致下游问题。你认为语言识别过程中的问题可能引发哪些问题？在风险更高的场景中（例如部署面向用户的产品时），你会如何缓解这些问题？

交付物： 用 2-5 句话回答。

(c) 在从 WARC 文件抽取的文本上运行你的语言识别系统（通过你之前实现的文本抽取函数）。手动识别 20 个随机样本中的语言，并将你的标签与分类器预测进行比较。报告任何分类器错误。文档中有多大比例是英语？根据你的观察，在过滤中使用什么样的分类器置信度阈值比较合适？

交付物： 用 2-5 句话回答。

2.4 个人可识别信息

Web 上包含大量可用于联系或识别个人的信息，例如电子邮件地址、电话号码或 IP 地址。我们可能不希望面向用户的语言模型输出关于真实人物的此类信息，而一个常见步骤是在训练数据集中遮蔽这些信息。

你现在将实现三个过程，分别用于遮蔽 (a) 电子邮件地址、(b) 电话号码和 (c) IP 地址。

问题 (mask_pii)：个人可识别信息（3 分）

(a) 编写一个函数来遮蔽电子邮件。你的函数将接收一个字符串作为输入，并将所有电子邮件地址实例替换为字符串 |||EMAIL_ADDRESS|||。要检测电子邮件地址，你可以查找能够可靠完成此事的正则表达式。

交付物： 一个函数，它将给定字符串中的所有电子邮件地址替换为字符串 |||EMAIL_ADDRESS|||，返回一个二元组，包含新字符串和被遮蔽的实例数量。实现适配器 [run_mask_emails]，并确保它通过 uv run pytest -k test_mask_emails 中的所有测试。

(b) 编写一个函数来遮蔽电话号码。你的函数将接收一个字符串作为输入，并将所有电话号码实例替换为字符串 |||PHONE_NUMBER|||。可靠地做到这一点可能极具挑战性，因为电话号码可能会以极其

（原文在此页中断）

第 6 页

电话号码的格式多种多样，但你至少应尝试覆盖美国最常用的电话号码格式，并且对细微的句法偏差保持稳健。

Deliverable: 一个函数，将给定字符串中的电话号码替换为字符串 "|||PHONE_NUMBER|||"，并返回一个 pair（二元组），包含新字符串以及被掩码的实例数量。实现 adapter [run_mask_phone_numbers]，并确保它通过：

uv run pytest -k test_mask_phones

(c) 编写一个函数来掩码 IP 地址。对于本题，只需关注 IPv4 地址（由点分隔的 4 个不超过 255 的数字）即可。你的函数将接收一个字符串作为输入，并将所有 IP 地址实例替换为字符串 "|||IP_ADDRESS|||"。

Deliverable: 一个函数，将给定字符串中的 IPv4 地址替换为字符串 "|||IP_ADDRESS|||"，并返回一个 pair（二元组），包含新字符串以及被掩码的实例数量。实现 adapter [run_mask_ips]，并确保它通过：

uv run pytest -k test_mask_ips

(d) 你认为当这些过滤器被朴素地应用到训练集上时，语言模型下游可能会出现哪些问题？你可以如何缓解这些问题？

Deliverable: 用 2–5 句话回答。

(e) 在你从 WARC 文件中抽取出的文本上运行你的 PII 掩码函数（通过你之前实现的文本抽取函数）。查看 20 个发生了替换的随机样例；给出一些假阳性与假阴性的例子。

Deliverable: 用 2–5 句话回答。

2.5 有害内容

未经过滤的 Web 抓取转储包含大量我们不希望语言模型在推理时重复的文本。其中一些训练样本甚至可能出人意料地来自通常无害的网站，例如 Wikipedia —— 例如，若干页面上用户留下的评论可能相当有毒。尽管基本上不可能为“什么是有害内容”划定一条清晰界线，许多数据过滤流水线仍然会对主要包含有害内容的页面做一些过滤。

识别此类内容有很多方法，包括统计禁词表中的词，或基于人工标注者给出的标签构建简单分类器。在本部分作业中，我们将重点关注识别两大类有害内容：“Not safe for work”（NSFW）（包括色情、脏话或其他可能令人不适的内容），以及有毒言论（“粗鲁、不尊重或不合理的语言，很可能使某人退出讨论”[注 3]）。我们将使用 Dolma 项目 [1] 提供的 fasttext 预训练模型，判断输入的一段文本是否属于这两类中的任意一类。这些分类器是在 Jigsaw Toxic Comments 数据集上训练的，该数据集包含按多种标签分类的 Wikipedia 评论。[注 4]

NSFW 分类器可在以下地址下载：dolma-artifacts.org/.../jigsaw_fasttext_bigrams_nsfw_final.bin。

仇恨言论分类器可在以下地址获取：dolma-artifacts.org/.../jigsaw_fasttext_bigrams_hatespeech_final.bin。

我们也将这两个分类器放到了共享数据目录中：

[注 3] https://current.withgoogle.com/the-current/toxicity/ [注 4] https://paperswithcode.com/dataset/toxic-comment-classification-challenge

第 7 页

使用这些模型实现一个函数：它接收一个包含页面内容的 Unicode 字符串，并返回一个标签（例如 “toxic”、“non-toxic”）以及一个置信度分数。

Problem (harmful_content)：有害内容（6 分）

(a) 编写一个函数来检测 NSFW 内容。

Deliverable: 一个函数，将给定字符串标记为是否包含 NSFW 内容，并返回一个 pair（二元组），同时包含标签与置信度分数。实现 adapter [run_classify_nsfw]，并确保它通过：

uv run pytest -k test_classify_nsfw

注意，这个测试只是一个 sanity check，取自 Jigsaw 数据集，但绝不表示你的分类器是准确的；你应当自行验证。

(b) 编写一个函数来检测有毒言论。

Deliverable: 一个函数，将给定字符串标记为是否属于有毒言论，并返回一个 pair（二元组），同时包含标签与置信度分数。实现 adapter [run_classify_toxic_speech]，并确保它通过：

uv run pytest -k test_classify_toxic_speech

同样，这个测试也只是一个 sanity check，同样取自 Jigsaw。

(c) 你认为当这些过滤器被用于创建训练集时，语言模型下游可能会出现哪些问题？你可以如何缓解这些问题？

Deliverable: 用 2–5 句话回答。

(d) 在你从 WARC 文件中抽取出的文本上运行你的有害内容过滤器（通过你之前实现的文本抽取函数）。查看 20 个随机样例，并将分类器预测结果与你自己的判断进行比较。报告任何分类器错误。有害文档占多大比例？根据你的观察，在过滤时应使用什么样的分类器置信度阈值比较合适？

Deliverable: 用 2–5 句话回答。

2.6 质量规则

即使按语言过滤页面并移除有害内容之后，剩余页面中仍有相当大一部分对语言模型训练而言质量较低。同样，尽管“质量”并不容易定义，浏览 Common Crawl 的样例有助于识别低质量内容的例子，例如：

Gopher 论文 [2] 描述了一组简单的质量过滤器，用于从网页抓取数据中移除类似的简单低质量文本案例。这些过滤器由易于理解的简单启发式规则组成，通常可以覆盖许多明显不合适的样例。Gopher quality filters（Gopher 质量过滤器）包括

第 8 页

若干基于文档长度、单词长度、符号与单词之比，以及是否出现某些英文 stop words 的准则。在这份作业中，你要实现 Gopher 论文 [2] 中所描述过滤器的一个子集。具体来说，你应当删除满足以下条件的文档：

关于 Gopher 论文所用全部质量过滤器的完整描述，请参阅该论文的 Appendix A。

Problem (gopher_quality_filters): Gopher quality filters (3 points)

(a)

实现（至少）上面所描述的这部分 Gopher quality filters。至于把文本切分成单词（tokenize），你可能会觉得 NLTK 包有用（具体来说是 nltk.word_tokenize），不过并不要求你一定用它。

Deliverable: 一个函数，它唯一的参数是一个字符串，返回布尔值，表示该文本是否通过 Gopher quality filters。实现 adapter [run_gopher_quality_filter]。然后，确保你的过滤器能通过 uv run pytest -k test_gopher 中的测试。

(b)

在你从 WARC 文件中抽取出的文本上（用你之前实现的文本抽取函数）运行你基于规则的质量过滤器。随机查看 20 个样例，把过滤器的判定结果与你自己的判断进行比较。对质量过滤器与你的判断不一致的情况加以评论。

Deliverable: 一段 2–5 句的回复。

2.7 Quality Classifier

现在让我们超越 Gopher 规则所刻画的那些简单句法质量准则。语言模型训练并不是第一个出现“需要按质量对内容排序”这一需求的场景。特别是，文本质量同样是 information retrieval 中的一个基本挑战。搜索引擎所利用的经典信号之一是 Web 上的链接结构：高质量页面倾向于链接到其他高质量页面 [3]。OpenAI 在构建 WebText（GPT-2 [4] 训练所用的数据集）时使用了类似的洞见：他们收集那些被 Reddit 评论以不低于某个 “karma” 阈值链接的页面。Reddit 的一个替代方案是把 Wikipedia 当作高质量链接的来源，因为从 Wikipedia 页面链接出去的外部资源往往是可信的页面 [5]。

虽然使用受控来源通常能得到高质量内容，但按今天的标准，由此得到的数据集最终还是偏小（OpenWebText 有 40GB 文本，而 The Pile 比它大 20 倍以上）。一种做法是：把这些参考页面当作正例，把 Common Crawl 中的（随机）页面当作负例，训练一个 fastText classifier。这个 classifier 给出一个质量分，你可以用它从整个 Common Crawl 中过滤掉页面。设定质量阈值就是在 precision 与 recall 之间做权衡。

在这部分作业中，你将构建一个 quality classifier。为方便起见，我们已经从最近的一份 Wikipedia dump 中抽取了参考页面的 URL，放在共享数据目录 /shared-data/wiki/enwiki-20260501-extracted_urls.txt.gz 下。该文件包含截至 2026 年 5 月的英文 Wikipedia 页面上出现的外部链接，但我们期望你自己对

第 9 页

这些 URL 做子采样，以获得用于训练分类器的“高质量”文本正例。注意这些正例中仍可能含有不理想的内容，因此使用你已经构建好的其他 primitive（例如 language identification、过滤规则等）来进一步提升它们的质量可能会很有用。给定一个 URL 文件，你可以用 wget 以 WARC 格式抓取其内容：

wget --timeout=5 \
    -i subsampled_positive_urls.txt \
    --warc-file=subsampled_positive_urls.warc \
    -O /dev/null

Problem (quality_classifier): Quality classifier (15 points)

(a)

训练一个 quality classifier，让它给定文本时返回一个数值型的质量分。

Deliverable: 一个 quality classifier，供下一个子问题使用。

(b)

写一个函数，把一个页面标记为高质量或低质量，并给出对该标签的置信度分数。

Deliverable: 一个函数，它唯一的参数是字符串，返回一个 pair：标签（是否高质量）与置信度分数。实现 adapter [run_classify_quality]。作为 sanity check，确保它能正确分类我们提供的两个样例，运行 uv run pytest -k test_classify_quality。

3 Deduplication

Web 上存在大量重复内容。有些页面彼此完全重复——想想归档页面，或者标准工具生成的默认页面，比如流行 Web 服务器返回的 404 页面。但大多数重复发生在更细的粒度上。例如，考虑 Stack Overflow 上的所有问题页面。虽然每个页面都有独特的内容（例如问题、评论、答案本身），但所有页面也都含有大量冗余，比如页眉、菜单选项和页脚，这些在所有此类页面渲染时都会以完全相同的形式重复出现。在本节的第一部分，我们先处理这种完全重复，之后再看看如何处理近似重复。

3.1 Exact line deduplication

对完全重复进行去重的一个简单做法是：只保留文档中那些在整个 corpus 里唯一的行。事实证明，这足以消除很大一部分冗余，例如我们上面提到的页眉和菜单选项。在较简单的情况下，当我们删除掉在别处完全重复出现的行之后，往往就只剩下每个页面独有的主体内容（比如 StackOverflow 上的问题和答案）。

要做到这一点，我们可以先对 corpus 做一遍扫描，统计每一行出现的次数。然后第二遍，我们重写每个文档，只保留其中唯一的行。

朴素地说，保存这些计数器所需的数据结构可能要占用与存储 corpus 中所有唯一行一样多的空间。一个简单的内存效率技巧是改用行的 hash 作为 key，让 key 具有固定大小（而不是取决于行的长度）。现在你就来实现这个简单的去重方法。

第 10 页

Problem (exact_deduplication)：精确行去重（3 分）

编写一个函数，接收输入文件路径列表，并对它们执行精确行去重。它应首先统计语料中每一行的频次，使用 hash 来减少内存占用，然后重写每个文件，只保留其独有的行。

Deliverable： 一个执行精确行去重的函数。你的函数应接收两个参数：(a) 输入文件路径列表；(b) 输出目录。它应将每个输入文件重写到输出目录中，文件名相同，但通过移除在输入文件集合中出现不止一次的行来对内容去重。例如，如果输入路径是 a/1.txt 和 a/2.txt，输出目录是 b/，你的函数应写出文件 b/1.txt 和 b/2.txt。实现 adapter [run_exact_line_deduplication]，并确保它能通过以下命令：

uv run pytest -k test_exact_line_deduplication

3.2 MinHash + LSH 文档去重

Exact deduplication 对于移除跨多个网页逐字重复的内容很有用，但不能处理文档内容略有差异的情况。例如，考虑软件许可证文档——许可证文档通常由模板生成，模板需要填入年份和软件作者姓名。因此，一个 MIT 许可项目的许可证文件与另一个 MIT 许可项目的许可证文件内容大体相同，但它们并非 exact duplicates。为了移除这类重复的、大体模板化的内容，我们需要 fuzzy deduplication。为了高效地进行文档级 fuzzy deduplication，我们将使用 minhash 与 locality sensitive hashing（LSH）[注 5]。

为了执行 fuzzy deduplication，我们将使用文档之间一种特定的 similarity 概念：每个文档的 n-gram 之间的 Jaccard similarity。集合 $S$ 和 $T$ 之间的 Jaccard similarity 定义为 $\frac{|S\cap T|}{|S\cup T|}$。为了朴素地执行 fuzzy deduplication，我们可以把每个文档表示为一个 n-gram 集合，并计算所有文档对之间的 Jaccard similarity；如果某一对超过特定的 Jaccard similarity 阈值，就将其标记为 duplicates。然而，这种方法对于大型文档集合（例如 Common Crawl）并不实用。此外，朴素地存储一个 n-gram 集合会比存储一个文档占用多得多的内存。

MinHashing

为了解决内存问题，我们把文档的 n-gram 集合表示替换为 signature。具体来说，我们希望构造这样的 signature：如果比较两个文档的 signature，就能得到这两个文档各自 n-gram 集合之间 Jaccard similarity 的近似值。Minhash signature 满足这些性质。为了计算文档 n-gram 集合 $S=\{s_1,\ldots,s_n\}$ 的 minhash signature，我们需要 $k$ 个不同的 hash 函数 $h_1,\ldots,h_k$ [注 6]。每个 hash 函数把一个 n-gram 映射到一个整数。给定 hash 函数 $h_i$，文档 n-gram 集合 $S$ 的 minhash 为

$$\text{minhash}(h_i,S)=\min(h_i(s_1),h_i(s_2),\ldots,h_i(s_n)).$$

文档 n-gram 集合 $S$ 的 signature 是 $\mathbb{R}^k$ 中的一个向量，其中第 $i$ 个元素包含 $S$ 在随机 hash 函数 $h_i$ 下的 minhash，即

$$[\text{minhash}(h_1,S),\text{minhash}(h_2,S),\ldots,\text{minhash}(h_k,S)].$$

事实证明，对于两个文档的 n-gram 集合 $S_1$ 和 $S_2$，集合之间的 Jaccard similarity 可由 minhash 值相同的列所占比例来近似（证明见 [6] 第 3 章 3.3.3 节）。例如，给定文档 signature $[1,2,3,2]$ 和 $[5,2,3,4]$，Jaccard

[注 5] 关于 LSH 和 minhashing 更深入的讨论，请参见 J. Leskovec、A. Rajaraman 和 J. D. Ullman [6] 的第 3 章。该章可在线获取：infolab.stanford.edu/~ullman/mmds/ch3n.pdf。

[注 6] 这 $k$ 个不同的 hash 函数可以来自同一族，但使用不同 seed。例如，MurmurHash3 是一个 hash 函数族，使用特定 seed 就实例化该族中的一个特定 hash 函数。

第 11 页

n-gram 集合之间的 similarity 近似为 $2/4$，因为这些 signature 的第二列和第三列具有相同的 minhash 值。

局部敏感哈希（Locality-sensitive hashing, LSH）

尽管 minhashing 为我们提供了一种内存高效的文档表示，并保留任意文档对之间的期望 similarity，但我们仍然需要比较所有文档对，以找出 similarity 最大的那些。LSH 提供了一种方法，可以高效地把可能具有高 similarity 的文档分到 bucket 中。为了把 LSH 应用于我们的文档 signature（现在是 $\mathbb{R}^k$ 中的一个向量），我们将把 signature 分成 $b$ 个 band，每个 band 含 $r$ 个 minhash，且 $k=br$。例如，如果我们有 100 个元素的文档 signature（由 100 个随机 hash 函数生成），可以把它分成 2 个 band、每个 50 个 minhash，或 4 个 band、每个 25 个 minhash，或 50 个 band、每个 2 个 minhash，等等。如果两个文档在某个特定 band 上具有相同的 hash 值，它们会被聚到同一个 bucket 中，并被视为 candidate duplicates。因此，在 signature 数量固定时，增加 band 数量会提高 recall 并降低 precision。

下面给出一个具体例子。假设文档 $D_1$ 的 minhash signature 为 $[1,2,3,4,5,6]$，文档 $D_2$ 的 minhash signature 为 $[1,2,3,5,1,2]$。如果我们使用 3 个 band、每个 band 含 2 个 minhash，那么 $D_1$ 的第一个 band 是 $[1,2]$，第二个 band 是 $[3,4]$，第三个 band 是 $[5,6]$。类似地，$D_2$ 的第一个 band 是 $[1,2]$，第二个 band 是 $[3,5]$，第三个 band 是 $[1,2]$。由于第一个 band 中的 hash 匹配（两个文档都是 $[1,2]$），$D_1$ 和 $D_2$ 会在第一个 band 下被聚到一起。它们不会在任何其他 band 下被聚到一起，因为那些 hash 不匹配。然而请注意，由于这两个文档至少在一个 band 下被聚到一起，无论其他 band 是否匹配，它们都会被视为 candidate duplicates。

一旦识别出 candidate duplicates，我们可以用多种方式处理它们。例如，我们可以计算所有 candidate duplicates 之间的 Jaccard similarity，并把超过设定阈值的对标记为 duplicates。

最后，我们跨 bucket 聚簇重复文档。例如，假设文档 A 和 B 在一个 bucket 中匹配，并且它们的真实 Jaccard similarity 高于我们的阈值；文档 B 和 C 在另一个 bucket 中匹配，并且它们的真实 Jaccard similarity 也高于我们的阈值。那么，我们会把文档 A、B 和 C 视为一个 cluster。我们对每个 cluster 中的文档随机移除除一个以外的所有文档。

Problem (minhash_deduplication)：MinHash + LSH 文档去重（8 分）

编写一个函数，接收输入文件路径列表，并使用 minhash 和 LSH 执行 fuzzy document deduplication。具体来说，你的函数应计算所提供路径列表中每个文档的 minhash signature，使用给定 band 数量的 LSH 识别 candidate duplicates，然后计算 candidate duplicates 之间的真实 n-gram Jaccard similarity，并移除超过给定阈值的那些。为了提高 recall（遵循 [7]），在计算 minhash signature 和/或比较 Jaccard similarity 之前，对文本进行 normalize：转小写、去除标点、归一化空白字符、去除重音符号，并应用 NFD unicode normalization。

Deliverable： 一个执行 fuzzy document deduplication 的函数。你的函数至少应接收以下参数：

你可以

第 12 页

假设用于计算 minhash signature 的 hash 个数能被用于 LSH 的 band 数整除。

你的函数应把每个输入文件改写（rewrite）到输出目录下、保持同名，但只写入那些 (a) 不是候选重复项，和/或 (b) 在聚簇 bucket 中被随机选中保留的文档。例如，如果输入路径是 a/1.txt 和 a/2.txt，输出目录是 b/，那么你的函数应写出文件 b/1.txt 和 b/2.txt。实现 adapter run_minhash_deduplication，并确保它能通过 uv run pytest -k test_minhash_deduplication。

4 为语言建模过滤数据

现在我们已经实现了各种用于过滤 web crawl 数据的 primitive，接下来把它们用起来，生成一些语言建模训练数据。

在这部分作业中，你的目标是过滤一批 CC WET 文件，产出语言建模训练数据。你的起点是已经做过英语过滤的 WET 文件：我们保留了按照 fastText lid.176.bin 语言识别模型判断英语概率至少为 70% 的文档。这些经过英语过滤的 WET 文件放在 /shared-data/english-wet-data，供你作为起点使用。

具体来说，你的目标是过滤 CC dump 来构造语言建模数据，使得训练出来的 Transformer 语言模型在 Paloma benchmark [8] 的 C4 100 domains 子集上 validation perplexity 最小。你不应修改模型架构或训练流程，因为目标是构造最好的数据。该数据集包含 C4 语言建模数据集 [9] 中 100 个最常见 domain 的样本。我们已把这份数据的一份副本放在 /shared-data/tokenized_paloma_c4_100_domains_validation.bin（用 GPT-2 tokenizer 分词过）——你可以翻看这些数据，了解它长什么样。可以用下面的方式加载：

import numpy as np
data = np.fromfile(
    "/shared-data/tokenized_paloma_c4_100_domains_validation.bin",
    dtype=np.uint16
)
from transformers import AutoTokenizer
tokenizer = AutoTokenizer.from_pretrained("gpt2")
print(tokenizer.decode(data[0:2000]))

给定你过滤后的数据集，你将在这份数据上训练一个 GPT-2 small 规模的模型，并在 C4 100 上评估其 perplexity。

我们提醒：你可以利用 Paloma validation 数据来构造过滤器或分类器，以处理 CC WET 文件，但不得把任何 validation 数据原样复制进你的训练数据。语言模型不应看到 validation set 中的任何数据。

即便是这批 WET 文件，数据量也相当可观。为了高效处理这些数据，我们建议尽可能使用 multi-processing。特别是，你可能会觉得 Python 的 concurrent.futures 或 multiprocessing API 有用。下面我们给出一个用 concurrent.futures 把函数并行到多个进程的最小示例：

第 13 页

import concurrent.futures
import os
from tqdm import tqdm

def process_single_wet_file(input_path: str, output_path: str):
    # TODO: read input path, process the input, and write the output to output_path
    return output_path

# Set up the executor
num_cpus = len(os.sched_getaffinity(0))
executor = concurrent.futures.ProcessPoolExecutor(max_workers=num_cpus)
wet_filepaths = ["a.warc.wet.gz", "b.warc.wet.gz", "c.warc.wet.gz"]
output_directory_path = "/path/to/output_directory/"
futures = []
for wet_filepath in wet_filepaths:
    # For each warc.wet.gz filepath, submit a job to the executor and get a future back
    wet_filename = str(pathlib.Path(wet_filepath).name)
    future = executor.submit(
        process_single_wet_file,
        wet_filepath,
        os.path.join(output_directory_path, wet_filename)
    )
    # Store the futures
    futures.append(future)

# Iterate over the completed futures as they finish, using a progress bar
# to keep track of progress.
for future in tqdm(
        concurrent.futures.as_completed(futures),
        total=len(wet_filepaths),
):
    output_file = future.result()
    print(f"Output file written: {output_file}")

处理大段文本时，请使用本地的并行方式，例如 concurrent.futures 或 multiprocessing。要在 modal 上跨 worker 并行，请对输入调用 .map(...)。

我们还建议使用 FastWARC 库来遍历每个 WET 文件中的 record，使用 tldextract 库从 URL 中抽取 domain 以便过滤。特别是，下面这些类可能会有所帮助：

from fastwarc.warc import ArchiveIterator, WarcRecordType
from tldextract import TLDExtract

Problem (filter_data)：为语言建模过滤数据（6 分）

(a) 写一个脚本，从一批 Common Crawl WET 文件（位于 /shared-data/english-wet-data）中过滤出语言建模数据。你可以自由使用本作业前面各部分已经实现的各种 primitive，也可以自由探索其他过滤器和数据生成方法（例如基于 n-gram 语言模型 perplexity 的过滤）。你的目标是产出这样的数据：在它上面训练后，能使 Paloma benchmark 的 C4 100 domains 子集上的 perplexity 最小。

第 14 页

再次提醒：你可以利用 Paloma validation 数据来构造过滤器或分类器，以处理 CC WET 文件，但不得把任何 validation 数据原样复制进你的训练数据。

你的脚本应报告每个你用到的 filter 保留了多少个 example，以便你了解各个 filter 对最终输出数据的贡献有多大。

Deliverable: 一个（或一系列）脚本，并行过滤所提供的 CC WET 文件以产出语言建模数据。一份书面 breakdown，说明在被丢弃的 example 中，各个 filter 步骤分别去掉了多大比例。

(b) 过滤所提供的 WET 文件（原始为 2,500 个 raw WET 文件）需要多长时间？过滤整个 Common Crawl dump 需要多长时间？

Deliverable: 数据过滤 pipeline 的运行时间。

现在我们已经产出了一些语言建模数据，接下来看看它，以便更好地理解其内容。

Problem (inspect_filtered_data)：检查过滤后的数据（4 分）

(a) 从你过滤后的数据集中随机取五个 example。评价它们的质量，以及它们是否适合用于语言建模，尤其考虑到我们的目标是在 C4 100 domains benchmark 上最小化 perplexity。

Deliverable: 来自最终过滤数据的五个随机 example。只展示数据中相关的摘录也可以，因为文档可能很长。对每个 example，用 1–2 句话描述该 example，以及它是否值得用于语言建模。

(b) 取五个被你的过滤脚本删除和/或修改过的 CC WET。是你的过滤流程的哪一部分删除或修改了这些文档？你认为对它们的删除和/或修改是否合理？

Deliverable: 来自原始 WET 的五个随机被丢弃 example。只展示数据中相关的摘录也可以，因为文档可能很长。对每个 example，用 1–2 句话描述该 example，以及它的删除是否合理。

(c) 如果你上面的分析促使你进一步修改数据 pipeline，可以在训练模型之前进行这些修改。报告你试验过的任何数据改动和/或数据迭代。

Deliverable: 对你试验过的数据改动和/或迭代的描述。

在把语言模型训练在我们的数据上之前，我们需要先对它做 tokenize。使用 transformers 提供的 GPT-2 tokenizer，把你过滤后的数据编码成整数 ID 序列，用于训练语言模型。别忘了在每个文档之后加上 GPT-2 的 end-of-sequence token <|endoftext|>。下面是一些 starter code：

import multiprocessing
import numpy as np
from tqdm import tqdm

第 15 页

from transformers import AutoTokenizer
input_path = "path/to/your/filtered/data"
output_path = "path/to/your/tokenized/data"
tokenizer = AutoTokenizer.from_pretrained("gpt2")
def tokenize_line_and_add_eos(line):
    return tokenizer.encode(line) + [tokenizer.eos_token_id]
with open(input_path) as f:
    lines = f.readlines()
pool = multiprocessing.Pool(multiprocessing.cpu_count())
chunksize = 100
results = []
for result in tqdm(
    pool.imap(tokenize_line_and_add_eos, lines, chunksize=chunksize),
    total=len(lines),
    desc="Tokenizing lines"
):
    results.append(result)
pool.close()
pool.join()
# Flatten the list of ids and convert to numpy array
all_ids = [token_id for sublist in results for token_id in sublist]
print(f"Tokenized and encoded {input_path} into {len(all_ids)} tokens")
ids_array = np.array(all_ids, dtype=np.uint16)
ids_array.tofile(output_path)

Problem (tokenize_data)：对数据做 tokenize（2 分）

写一个脚本，对你过滤后的数据做 tokenize 并序列化。请确保按上面的示例代码，用 ids_array.tofile(output_path) 完成序列化，其中 ids_array 是一个由整数 ID 构成的 np.uint16 numpy 数组。这样才能与提供的 training script 保持兼容。

你过滤后的 dataset 中共有多少个 token？

Deliverable: 一个用来 tokenize 并序列化你过滤后数据的脚本，以及你产出的 dataset 中的 token 数量。

现在我们的 dataset 已经 tokenize 好了，可以在上面训练模型了。我们将在生成的数据上训练一个 GPT-2 small 规模的模型，大约 430M 参数，并在训练过程中定期在 C4 100 domains dataset 上测量验证性能。这次训练使用 8 张 B200 GPU、data parallelism、每张设备 batch size 128、共 16,384 个 optimization steps。在 context length 为 512 的情况下，这相当于训练期间采样了约 $2^{33} = 8.6\text{B}$ 个 training tokens。用这套配置，我们的训练跑完大约用了 2:00 小时。

[注 7] https://github.com/stanford-cs336/assignment4-data/blob/master/scripts/train.py

第 16 页

用 scripts/train.py 处的 train.py 脚本启动训练。[注 7] 你可以在 cs336_basics/train_config.py 中查看将要使用的超参数。用 --train-bin 传入你 tokenize 后的训练数据路径：

uv run modal run scripts/train.py --train-bin /root/data/your_data.bin

再强调一次，本作业的目标是优化数据以最小化 validation loss，而不是通过修改模型和/或优化流程来把 loss 压低，所以不要改动训练流程或训练脚本。

然后，你可以用下面的命令从保存的模型中采样：

uv run modal run scripts/generate_with_gpt2_tok.py --model-path /root/data/output/your_data

Problem (train_model)：训练模型（8 分）

在你 tokenize 后的 dataset 上训练一个语言模型（GPT-2 small 规模，约 430M 参数）。定期测量在 C4 100 domains 上的 validation loss。你的模型达到的最好 validation loss 是多少？

Deliverable: 记录到的最好 validation loss、对应的 learning curve，以及对你所做工作的说明。

Bibliography

[1] L. Soldaini et al., “Dolma: An Open Corpus of Three Trillion Tokens for Language Model Pretraining Research,” arXiv preprint arXiv:2402.00159, 2024.

[2] J. W. Rae et al., “Scaling language models: Methods, analysis & insights from training gopher,” arXiv preprint arXiv:2112.11446, 2021.

[3] L. Page, S. Brin, R. Motwani, and T. Winograd, “The pagerank citation ranking: Bring order to the web,” in Proc. of the 7th International World Wide Web Conf, 1998.

[4] A. Radford et al., “Language models are unsupervised multitask learners,” OpenAI blog, vol. 1, no. 8, p. 9, 2019.

[5] H. Touvron et al., “LLaMA: Open and Efficient Foundation Language Models.” 2023.

[6] J. Leskovec, A. Rajaraman, and J. D. Ullman, Mining of Massive Datasets, 2nd ed. USA: Cambridge University Press, 2014.

[7] G. Penedo et al., “The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data, and Web Data Only.” 2023.

[8] I. Magnusson et al., “Paloma: A Benchmark for Evaluating Language Model Fit.” 2023.

[9] C. Raffel et al., “Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer,” Journal of Machine Learning Research, vol. 21, no. 140, pp. 1–67, 2020, [Online]. Available: http://jmlr.org/papers/v21/20-074.html

材料

数据 / 仓库（只给链接，不下载 ✗）

按 D50：数据集与 starter code 只给链接 ✓（starter code 用 git clone 拿 ✓，数据集太大 ✗ 而且年年变 ✓）。这些链接故意不放在「材料」小节 ✓ —— 放了就会被 --fetch 下载 ✗。

自查