第 14 讲：数据 II — 转换、过滤、去重、混合与合成数据

目录 · ← l13 · l15 →

第 14 讲：数据 II — 转换、过滤、去重、混合与合成数据

日期：5 月 13 日（周三，Spring 2026） | 讲师：Percy Liang | 材料：lecture_14.py

概览

这是数据工程算法核心的一讲。覆盖流水线四个阶段——转换（transformation）（HTML/PDF → 文本）、过滤（filtering）（语言识别、质量、毒性，基于分类器）、去重（deduplication）（精确去重与哈希、MinHash、LSH）、数据混合（data mixing）（如何给各来源加权、epoch 陷阱、UniMax 上限、回归式混合、模拟 epoch）——最后讲后训练 / 合成数据（OpenThoughts、SWE-smith、SWE-Zero 等）。

核心概念与定义

• 转换：原始数据不是文本，而是 HTML、PDF 或目录。HTML→文本：去掉 boilerplate（导航、广告）、抽正文、把表格/图片线性化（有损）。工具：trafilatura、resiliparse、jusText、lynx。质量很重要（DCLM）。FinePDFs：对 PDF 重新抓取 + OCR（RolmOCR/Docling）+ 清洗。
• 过滤——算法积木：给定目标数据 T 与原始数据 R，找出与 T 相似的子集 T′ ⊂ R。两步框架：(1) 基于 R 与 T 估计一个模型 → 得到打分函数；(2) 按分数保留样本。类型：T 的生成式模型（KenLM：score(x) = p_T(x)）或分类器（fastText：score(x) = p(T|x)）；按阈值（随机地）保留。
  • 必备性质：能从目标数据泛化（T′ ≠ T），并且极快（R 巨大）。
  • 应用：语言识别（fastText lid.176，176 种语言；Dolma 保留 p(en) ≥ 0.5）、质量过滤、毒性过滤（Jigsaw Toxic Comments，6 个标签）。
  • 基于模型 vs 基于规则：C4/Gopher/RefinedWeb/FineWeb/Dolma 刻意不用模型过滤；GPT-3/LLaMA/DCLM 用——”正成为常态”。
  • 案例：OpenMathText（规则 + KenLM 困惑度 < 15000 + fastText 数学分类器 → 147 亿 token，效果超过 20 倍数据量的模型）；GPT-3（词特征线性分类器 + Pareto-9 随机保留）；LLaMA/RedPajama（正样本 = 被 Wikipedia 引用 的页面）；phi-1（用 GPT-4 给 The Stack 的 Python 子集打”教育价值”标签 → 用 codegen 模型嵌入训练随机森林 → HumanEval 12.19% → 17.68%，且步数只有 1/3）；Dolma 的毒性过滤（Jigsaw 分类器）。
  • 过滤的规模依赖：并不存在唯一最优阈值——训练越久越需要更多（更低质量）数据；训练越短越需要更少（更高质量）数据。
• 去重（deduplication）：精确重复（镜像站、fork）与近似重复（服务条款页面、模板化文本——某商品描述在 C4 中重复了 61036 次）。为什么去重：训练更高效（token 更少）并避免记忆（版权/隐私）。
  • 设计空间：(1) 以什么为”条目”（句子/段落/文档）；(2) 如何匹配（精确匹配、存在公共子条目、公共子条目比例）；(3) 采取什么动作（全删 / 只留一个）。
  • 关键挑战：比较条目与条目需要线性时间算法才能扩展到海量数据。
• 哈希（hashing）：把条目映射为小的哈希值。密码学哈希（SHA-256）：抗碰撞、慢。非密码学哈希（MurmurHash、DJB2、CityHash）：快，用于哈希表。去重用 MurmurHash。
• 精确去重：按哈希分组、每组留一个（MapReduce 风格，天然可并行）。C4：条目 = 3 句片段、精确匹配、只留一个——但从文档中间删除片段会破坏连贯性。
• Jaccard 相似度：J(A,B) = |A∩B| / |A∪B|；近似重复定义为 Jaccard ≥ 阈值。
• MinHash：一种哈希方案，满足 Pr[h(A) = h(B)] = Jaccard(A,B)——这里你希望碰撞概率与相似度挂钩（与普通哈希相反！）。minhash(S, seed) = min(mmh3.hash(x, seed) for x in S)；用多个种子时，最小哈希相等的比例即为 Jaccard 的估计。
  • 为什么成立：随机哈希诱导出对元素的随机排列；集合的最小元素在其元素之间均匀分布，故 A 与 B 共享最小值当且仅当 A∪B 的全局最小元素属于 A∩B——概率为 |A∩B|/|A∪B|。
• 局部敏感哈希（LSH）：把碰撞概率”锐化”成阈值判定。用 n = b·r 个哈希函数分成 b 个 band、每 band r 个：A 与 B 碰撞当且仅当某个 band 内全部 r 个哈希都相等。碰撞概率 P = 1 − (1 − s^r)^b——关于相似度 s 的 S 形曲线；相变点位于 s* = (1/b)^(1/r)。增大 r 会锐化曲线并把阈值右移（更难匹配）；增大 b 则左移（更容易）。真实配置（Lee 等 2021）：n=9000、b=20、r=450 → 阈值 ≈ (1/20)^(1/450) ≈ 0.993。在阈值处 P(碰撞) ≈ 1 − 1/e。
• 数据混合：各来源的分布 p(s) 该怎么定？基线：凭感觉（手工）、均匀采样、按 token 数比例采样。两个直觉冲突：要给高质量来源加权，但每个来源都是有限的——在小的高质量来源上过度 epoch 会导致过拟合（例：10B token 的来源在 p=0.5、训练 1T token 时 = 50 个 epoch！）。
  • UniMax：均匀采样 + 对每个来源的 epoch 数设硬上限 C：p(s)·train_tokens ≤ C——用于多语模型的语言平衡。
  • 回归式混合（RegMix）：定义混合分布的分布（如 Dirichlet），训练小模型，回归”混合 → 损失”（线性/GBT），再优化；两个希望：(1) 回归在最优点附近准确，(2) 最优混合能迁移到大尺度。
  • 模拟 epoch（simulated epoching）：按相同比例对所有来源降采样，让小规模跑出与大规模相同的 epoch 结构——于是小规模拟合出的最优混合能迁移。
• 后训练 / 合成数据配方：(1) 定义环境；(2) 定义任务/提示；(3) 用强教师模型收集回答。例子：OpenThoughts（用 QwQ-32B 造 120 万条；每提示采样 16 条有帮助；更强的模型不一定是更好的教师——QwQ-32B 优于 DeepSeek-R1；答案过滤没帮助；小而精的来源优于大而杂的来源）；SWE-smith（用 LM 往仓库注入 bug 来生成任务；128 个仓库产出 5 万个任务）；SWE-Zero（30 万条不依赖仓库特定执行的 agent 轨迹——强模型内部具备代码语义的”世界模型”；15 万个 GitHub PR；从 Qwen3-Coder-480B 蒸馏）；SWE-rebench（2.1 万个可交互的 Python SWE 任务）；SWE-ZERO-12M-trajectories（用 1.7B 的小 agent 把规模推到 1200 万条轨迹）。

代码示例：基于哈希的精确去重

代码（Python）：

import itertools, mmh3

items = ["Hello!", "hello", "hello there", "hello", "hi", "bye"]

# 按哈希分组、每组留一个（MapReduce 风格，可并行）
hash_items = itertools.groupby(sorted(items, key=mmh3.hash), key=mmh3.hash)
deduped_items = [next(group) for h, group in hash_items]
# -> "hello" 只出现一次；"Hello!" 与之不同（字节不同）

代码做了什么： 按 MurmurHash 值排序、把相同哈希分到一组、每组取第一个——线性时间的精确去重。

实现深挖：

• 为什么用 MurmurHash：快速的非密码学哈希——这里碰撞可以接受（我们要去重而非加密）；在 TB 级数据上用密码学哈希会慢得不必要。
• 为什么”排序后 groupby”：与哈希分桶等价，但写成 MapReduce 友好的形式——该模式可在分片数据上跨 worker 并行（作业 4 正是用 concurrent.futures 处理 WET 文件）。
• 为什么 “Hello!” ≠ “hello”：哈希作用于字节——大小写与标点差异会让近乎相同的文本得到不同哈希；这是精确去重无法解决的局限（所以需要 MinHash）。

与作业的联系：作业 4 的去重任务以段落/文档的精确哈希为基线，再用 MinHash 做近重复去除——这个片段就是起点，只是要扩展到在规模化语料上对分词后的文档操作。

代码示例：MinHash 与 LSH（作业 4 的核心）

代码（Python）：

import mmh3

def jaccard(A, B):
    return len(A & B) / len(A | B)

def minhash(S: set[str], seed: int) -> int:
    """MinHash：Pr[minhash(A) == minhash(B)] = Jaccard(A, B)。"""
    return min(mmh3.hash(x, seed) for x in S)

def get_prob_collision(sim, b, r):
    prob_match = sim ** r                     # 一个 band 内 r 个哈希全部相同
    return 1 - (1 - prob_match) ** b          # 某个 band 匹配

# 验证估计量：
A = {"1", "2", "3", "4"}; B = {"1", "2", "3", "5"}
true_j = jaccard(A, B)
n = 100
matches = [minhash(A, seed) == minhash(B, seed) for seed in range(n)]
assert abs(sum(matches)/n - true_j) < 0.01   # 估计值 ≈ 真实 Jaccard

# LSH：b 个 band、每 band r 个哈希；碰撞概率是一条陡峭的 S 形曲线
p80 = get_prob_collision(sim=0.8, b=10, r=10)   # 接近 1
p20 = get_prob_collision(sim=0.2, b=10, r=10)   # 接近 0
threshold = (1 / b) ** (1 / r)                  # 相变点位置

代码做了什么： 实现 MinHash（对集合在某个种子下的最小哈希），用实验验证 Jaccard 估计量，并计算 LSH 的 band 碰撞概率——展示把”相似度”变成”近似阈值判定”的 S 形曲线。

实现深挖：

• 为什么取最小：对随机哈希来说，A∪B 中每个元素成为最小值的概率相同；A 的最小值等于 B 的最小值，当且仅当全局最小元素落在 A∩B 中 → 概率 = |A∩B|/|A∪B| = Jaccard。
• 为什么用 band（b·r）：单个哈希的碰撞概率就是 Jaccard 本身——太”软”。band 内的”与”（r 个都相同：s^r）加上跨 band 的”或”（b 个中任一：1−(1−s^r)^b）把它锐化成以 (1/b)^(1/r) 为中心的阶跃。
• 为什么参数重要：n=9000、b=20、r=450（真实配置）瞄准相似度 ≥ ~0.993 的近重复——你要找的是几乎完全相同的文档，而非大致相关的文档。调 (b, r) 就是权衡假阳性与假阴性。
• 为什么这是作业 4 的瓶颈：在数百 GB 上做去重需要线性、近似、可并行的匹配——MinHash + LSH 正是如此（避免 O(n²) 的两两比较）。

与作业的联系：作业 4：在过滤后的语料上实现 MinHash 去重（条目 = 文档/段落，用 shingle token 的 Jaccard 匹配，每个近重复簇保留一个），并测量去重对困惑度的影响。讲义的 get_prob_collision 与阈值数学就是你在报告中论证 (b, r) 取值的依据。

代码示例：数据混合与 epoch 陷阱

代码（Python）：

def num_epochs(source_tokens: float, weight: float, train_tokens: float) -> float:
    return (weight * train_tokens) / source_tokens

# 陷阱：小规模高质量来源被反复读取
sources = {"low": 10e12, "high": 10e9}        # 10T vs 10B token
p = {"low": 0.5, "high": 0.5}                  # 天真的 50/50 混合
train = 1e12                                   # 训练 1T token
epochs = {s: num_epochs(sources[s], p[s], train) for s in sources}
# epochs["high"] == 50  -> 稀缺来源被过 50 遍：过拟合！

# UniMax：给每个来源的 epoch 数设硬上限
C = 2
p = {s: min(p[s], C * sources[s] / train) for s in sources}   # 之后需重新归一化

# 模拟 epoch：按相同比例对所有来源降采样
ratio = 10e9 / 1e12                            # 小规模运行 / 大规模运行
downsampled = {s: sources[s] * ratio for s in sources}   # 小规模的"等价"数据量

代码做了什么： 计算天真混合下每个来源的 epoch 数（暴露 50 个 epoch 的过拟合陷阱），应用 UniMax 式 epoch 上限，并展示模拟 epoch 的比例降采样。

实现深挖：

• 为什么 epoch 数重要：一个来源被看 50 遍就会被记住；在小规模上最优的混合（偏向稀缺高质量数据）在大规模上不是最优——这是会破坏”混合迁移”的规模依赖效应。
• 为什么模拟 epoch 能修复迁移：把所有来源都降采样到小规模运行的 token 预算，让小规模实验看到与大规模运行相同的 epoch 结构；此时拟合出的最优点才能迁移（第 9 讲”让小规模看起来像大规模”的主题）。
• 为什么上限是务实解法（UniMax）：给每个来源的 epoch 数设硬上限即可避免病态的过度重复，无需重新拟合——这是多语混合的标准技巧。

与作业的联系：作业 4 的最后一步是在 token 预算下混合各来源（排行榜：在给定 token 数下最小化困惑度）：epoch 陷阱与 UniMax 上限正是”每个来源该保留多少过滤后数据”的核心考量。作业 3 的扩展律推理用的是同一套”从小到大迁移”的逻辑。

关键要点

1. 数据流水线：转换（HTML→文本）→ 过滤（语言/质量/毒性的分类器）→ 去重（精确 + MinHash/LSH）→ 混合（权重、上限、模拟 epoch）。
2. 过滤 = “在原始数据中找出与目标相似的部分”：用生成式模型（KenLM）或分类器（fastText）打分；按阈值或随机保留；必须能泛化且极快。
3. 规模化去重需要线性时间的近似匹配：MurmurHash 做精确去重；MinHash（Pr[碰撞] = Jaccard）+ LSH band（阈值在 (1/b)^(1/r) 的 S 形曲线）做近重复。
4. 混合存在规模依赖：天真权重会过度 epoch 稀缺来源（50 epoch 陷阱）；用 UniMax 上限或模拟 epoch 让小规模最优点可迁移。
5. 后训练数据越来越合成化：教师模型 + 环境 + 过滤（OpenThoughts、SWE-Zero）——而更小但更高质量的来源常常优于更大更杂的来源。

常见陷阱

• O(n²) 去重：两两比较全部文档不可行；必须基于哈希（精确或 MinHash）。
• LSH 参数选错：(b, r) 决定阈值——b 太小/r 太大会漏掉近重复；相变点在 (1/b)^(1/r)，要按目标相似度来选。
• 把哈希碰撞当真值：MurmurHash 会有碰撞；精确去重是”高精度”但非完美；MinHash 是对 Jaccard 的有方差估计——哈希个数（n）要足够。
• 过度 epoch 稀缺来源：天真的按比例或按质量加权会记住小来源；要设上限或做模拟 epoch。
• 跨规模用固定过滤阈值：最优阈值随训练预算变化（训练越久越应保留更多数据）。
• 去重破坏文档连贯性：C4 式删除文档中间片段会产出不连贯文本——要检查去重单位对下游质量的影响。
• 分类器正负样本有偏：你的质量过滤器会继承所选目标数据的偏差（例如 RefinedWeb 作负样本）。

复习题

1. 问： 为什么 MinHash 的碰撞概率等于 Jaccard 相似度？
   • 答： 随机哈希置换让 A∪B 中每个元素成为最小值的概率相同。A 与 B 的最小值相同，当且仅当全局最小元素落在 A∩B 中——概率为 |A∩B|/|A∪B| = Jaccard。
2. 问： LSH 如何把”碰撞概率 = 相似度”变为硬阈值？
   • 答： 用 b 个 band、每 band r 个哈希，只要某个 band 内 r 个最小哈希全部相等就判为碰撞：P = 1−(1−s^r)^b。这是关于相似度 s 的 S 形曲线，陡峭的过渡位于 s* = (1/b)^(1/r)——高于 s* 的近重复几乎必然碰撞，远低于 s* 的几乎不碰撞。
3. 问： 为什么在小规模上最优的混合在大规模上会失败？怎么修？
   • 答： 随着训练 token 增多，稀缺的高质量来源会被过度 epoch（例子里是 50 个 epoch）——小规模最优点给了它们过高权重。修法：UniMax 对每来源 epoch 数设硬上限，或模拟 epoch（按比例降采样所有来源）让小规模复现大规模的 epoch 结构。