Notes/机器学习/深度学习模型/05-大语言模型/1-分词-Tokenization/1-Tokenization.md

title, draft, tags

title	draft	tags
Tokenization：子词切分的数学体系	false	Tokenization BPE SentencePiece WordPiece NLP 大语言模型

Tokenization：子词切分的数学体系

---

一、问题引入：为什么需要子词切分

1.1 词级切分的问题

词级（Word-level）切分将文本分割为单词集合：

• 词表大小受语料库词汇量限制
• 未登录词（OOV）无法处理
• 多语言场景下词表膨胀

数学表示：

设词表为 $V$，单词 $w \in V$。对句子 $s = w_1 w_2 \ldots w_T$，词级切分要求 $w_i \in V, \forall i$。

当遇到新词 w_{i} \notin V 时，系统必须返回 UNK（unknown） token，这丢失了所有语义信息。

1.2 字符级切分的问题

字符级（Character-level）切分将文本分割为字符集合：

• 彻底解决 OOV 问题
• 序列长度大幅增加（英文增加约 4-8倍，中文增加更多）
• 字符的语义信息远低于词

序列长度对比（以英文为例）：

切分方式	平均序列长度倍数
词级	1×（基准）
子词级	1.3-1.7×
字符级	4-8×

1.3 子词切分的核心思想

**子词切分（Subword Tokenization）**是两种极端之间的平衡：

将罕见词拆分成更小的子词片段，同时保留高频词的完整性。

关键观察：

• 词的内部结构是有意义的（如 "unexpected" = "un" + "expect" + "ed"）
• 语言的词形态变化有规律（如 "running" = "run" + "n" + "ing"）
• 子词片段可以跨词共享（如 "un" 出现在 "unexpected", "unfair", "undo"）

目标：

1. 将开放词表问题变成有限词表问题
2. 保持合理的序列长度
3. 保留子词的语义可解释性

---

二、BPE（Byte Pair Encoding）

2.1 算法起源与核心思想

BPE 最初是 Gage（1994）提出的一种数据压缩算法，用于压缩稀有字节序列。后被 Sennrich et al.（2016）引入 NLP 作为子词切分算法。

关键区分（两类工业主流BPE）：

1. Sennrich 字符级 BPE：机器翻译使用，拆分英文单词字符
2. GPT 字节级 BPE：大模型标配，直接操作 UTF-8 字节，无语言字符依赖，彻底杜绝 OOV

核心思想：

在语料库中迭代地合并最高频的相邻字节对（byte pairs），最终构建一个包含所有子词单元的固定词表。

2.2 算法的数学形式化

定义（字符序列）：

设语料库为 $C$，其中每个样本是字符序列 $c_1 c_2 \ldots c_n$。

定义（BPE 合并操作）：

给定字符序列，定义所有相邻对（pair）为：

\mathcal{P}(c_1 \ldots c_n) = \{ (c_i, c_{i+1}) : 1 \leq i < n \}

定义（合并频率）：

对于每个 pair $p = (a, b)$，定义其在语料库中的出现频率：

\text{freq}(p) = \sum_{s \in C} \text{count}_s(p) \tag{2.1}

其中 \text{count}_s(p) 是 pair p 在序列 s 中出现的次数。

2.3 BPE 算法步骤

Algorithm: BPE Tokenization

输入：语料库 $C$，目标词表大小 $|V|$（不含 UNK 和句子开始/结束等特殊 token）

预处理：

1. 将每个词拆分为字符序列
2. 统计所有字符级别的 pair 频率
3. 现代大模型规范：使用前缀空格符 Ġ 替代老式 </w> 词尾标记，便于解码保真

迭代：

while |V| < target_size:
    1. 找到语料库中频率最高的 pair (a, b)
    　freq_max = argmax_{(a,b)} freq(a,b)
    2. 将语料库中所有 (a, b) 合并为新符号 "ab"
    　- 更新所有包含 (a, b) 的序列
    　- 更新 pair 频率表
    3. 将 "ab" 加入词表 V

输出：词表 $V$（包含字符、合并后的子词、以及特殊 token）

2.4 BPE 的编码与解码

编码（Tokenization）：

给定词 $w = c_1 c_2 \ldots c_n$，编码过程：

1. 初始化：w = [c_1, c_2, \ldots, c_n]
2. 如果词不在词表中，重复以下直到所有片段都在词表中：
   • 从右向左找到最长的、在词表中的子词（工业界标准 BPE 编码方向）
   • 如果找不到，替换为 UNK
3. 返回子词序列

贪心最长匹配编码（实际使用）：

def encode(word):
    if word not in word_set:
        return [UNK]

    tokens = []
    pos = 0
    while pos < len(word):
        # 尝试最长匹配
        end = len(word)
        found = False
        while end > pos:
            substr = word[pos:end]
            if substr in vocab:
                tokens.append(substr)
                pos = end
                found = True
                break
            end -= 1

        if not found:
            tokens.append(UNK)
            break

    return tokens

解码（Detokenization）：

给定子词序列 $t_1, t_2, \ldots, t_k$：

1. 去掉所有 标记
2. 直接拼接相邻子词
3. 返回拼接结果

注意：解码需要正确处理空格。例如：

• 子词序列 ["Ġthe", "Ġcat"] 解码为 " the cat"
• Ġ 表示空格

2.5 BPE 的数学性质

性质（词表大小控制）：

BPE 的词表大小 |V| 可以通过合并次数近似控制：

|V| \approx |V_{\text{base}}| + N_{\text{merge}} \tag{2.2}

其中 |V_{\text{base}}| 是基础字符数（通常 256-500），N_{\text{merge}} 是执行的合并次数。注意：由于合并操作可能产生子词覆盖、冗余淘汰，实际词表大小并非严格线性相加，该等式仅为近似关系。

性质（OOV 处理）：

对于未登录词 $w$，编码过程保证：

1. 如果 w 可以完全分解为词表中的子词，则编码成功
2. 否则，包含 UNK token

性质（子词共享）：

设两个词 w_1 和 w_2 共享一个子词单元 $s$，则在编码表示中：

I(w_1) \cap I(w_2) \neq \emptyset \tag{2.3}

其中 I(w) 是词 w 编码后的子词索引序列。

2.6 BPE 的变种与改进

Faster BPE（基于 Trie 树）：

使用 Trie 树存储词表，可以 O(1) 查找子词：

• 节点表示字符
• 边表示子词片段
• 时间复杂度从 O(n \cdot m) 降到 O(n)

BPE-Dropout：

在编码时随机跳过合并操作：

• 训练时使用 dropout：每次以概率 p 跳过某个合并
• 推理时不使用 dropout
• 完整作用：1. 增强分词鲁棒性 2. 生成多粒度子词序列 3. 大幅提升低资源语种泛化能力

---

三、SentencePiece

3.1 设计动机

BPE 的问题：

1. 需要预处理：BPE 假设文本已经被"空格分隔"，但很多语言（如中文、日文）不使用空格分词
2. 语言依赖：分词器需要针对每种语言单独开发
3. 歧义问题：空格分词在某些语言中本身就有歧义（如德语复合词）

SentencePiece 的核心思想：

将整个句子视为一个字符序列，不依赖任何预处理的分词，直接在原始文本上运行 BPE。

核心规则：▁（U+2581）仅作为子词开头前缀，不会出现在子词中部，是解码保真的关键。

3.2 算法描述

Algorithm: SentencePiece Training

输入：

• 原始语料库（未分词的文本）
• 目标词表大小 |V|
• 字符归一化配置（Unicode NFC/NFD）

预处理：

1. 字符归一化：将 Unicode 文本标准化（如将 é 转为 e + accent 的组合）
2. 空格替换：将空格替换为特殊字符 ▁（U+2581）
3. 直接构建字符序列

训练：与标准 BPE 完全相同

解码：

1. 将 ▁ 替换为空格
2. 拼接子词
3. 逆标准化

3.3 与标准 BPE 的关键区别

维度	标准 BPE	SentencePiece
输入	预分词文本（空格分隔）	原始句子（无需分词）
空格处理	丢失（被空格分词）	保留（替换为 ▁）
语言依赖	需要语言特定分词器	语言无关
解码保真度	空格可能丢失	完全恢复原始文本

3.4 归一化与逆标准化

Unicode 归一化：

SentencePiece 使用 Unicode 归一化确保一致的字符表示。工业界统一使用 NFKC：

形式	示例	说明
NFC	é（单一字符）	组合形式
NFD	e + combining accent	分解形式
NFKC	é（单一字符）	业界标配，规范化兼容区字符（如全角转半角）
NFKD	e + combining accent	分解兼容区字符

逆标准化：

训练时记录归一化映射，解码时逆应用以恢复原始表示。

3.5 子词平滑与置信度

定义（子词置信度）：

对于编码后的子词序列 $s_1, s_2, \ldots, s_k$，定义子词置信度：

\text{conf}(s_i) = \frac{\text{freq}(s_i)}{\sum_{j=1}^k \text{freq}(s_j)} \tag{3.1}

这衡量了子词在训练语料中的统计显著性。

应用：

在某些实现中，低置信度的子词可以被进一步拆分或标记为 UNK。

---

四、WordPiece

4.1 算法起源与与 BPE 的区别

WordPiece 由 Schuster 和 Nakajima（2012）提出，最早用于 Google 的日语/韩语语音搜索系统，后被 BERT 采用。

与 BPE 的关键区别：

维度	BPE	WordPiece
选择合并的依据	最高频率的 pair	最大似然的 pair
合并判据	\text{freq}(a,b)	\text{score}(a,b) = \log P(a,b) - \log P(a) - \log P(b)
编码策略	Longest-match-first	同样使用 Longest-match-first
语言学偏好	无	可能倾向于有语言学意义的切分

4.2 WordPiece 的数学推导

核心思想：

BPE 基于频率，WordPiece 基于子词序列的似然。

设语料库为 $C$，词 w 可以被切分为子词序列 $s_1, s_2, \ldots, s_k$。

定义（词的似然）：

P(w) = \prod_{i=1}^k P(s_i) \tag{4.1}

其中 P(s) 是子词 s 在语料库中的（归一化）频率。

定义（合并得分）：

对于候选 pair $(a, b)$，定义合并得分：

\text{score}(a,b) = \log P(ab) - \log P(a) - \log P(b) \tag{4.2}

推导：

考虑将 a 和 b 合并为 $ab$。合并后的似然变化为：

\Delta = \log P(ab) - (\log P(a) + \log P(b)) \tag{4.3}

当 \Delta > 0 时，合并能提高整体似然。WordPiece 选择使 \Delta 最大的 pair 进行合并。

等价的频率解释：

部分实现使用频率近似替代对数似然比：

\text{score}(a,b) \approx \log \frac{\text{freq}(ab)}{\text{freq}(a) \cdot \text{freq}(b)}

这是对互信息的简化近似。注意：原版 WordPiece 核心是基于对数似然的得分公式（式 4.2），频率等价形式仅为工程实现近似，并非官方标准形式。

4.3 WordPiece 算法步骤

Algorithm: WordPiece Training

输入：语料库 $C$，目标词表大小 |V|

预处理：

1. 将每个词初始化为字符序列
2. 统计所有子词（包括字符）的频率

迭代：

while |V| < target_size:
    1. 对于每个候选 pair (a,b)，计算 score(a,b)
    　- 使用动态规划避免重复计算
    2. 找到 score 最高的 pair
    3. 合并该 pair，加入词表
    4. 更新频率表

4.4 编码算法

Algorithm: WordPiece Encoding

输入：词 $w$，词表 V

初始化：

S = [c_1, c_2, \ldots, c_n]

其中 c_i 是字符，末尾不加特殊标记（与 BPE 不同）

贪心切分：

while S is not empty:
    1. 从 S 的起始位置开始
    2. 尝试找到最长的、在词表中的前缀
    　- 如果找到长度 L 的子词，加入结果，消耗 L 个字符
    　- 如果没找到，输出 [UNK]
    3. 重复直到 S 为空

与 BPE 的细微区别：

WordPiece 的编码更严格地依赖词表。在 BERT 实现中：

1. 使用 [UNK] token 表示单个未知字符
2. 如果整个词都无法编码，也使用 [UNK]

4.5 BERT 中的 WordPiece 实现

BERT 使用的 WordPiece 标志性规则：词内子词添加 ## 前缀

例如 running → run ##ning

这使得 BERT 能够区分：

• run 是独立词
• ##ning 是词内子词（接在前面的词后面）

特殊 Token：

Token	含义
[PAD]	填充
[UNK]	未知词
[CLS]	分类任务特殊位
[SEP]	句子分隔
[MASK]	掩码

词表结构：

BERT 的词表包含：

• 约 30,522 个 WordPiece token
• 覆盖英文的 BPE 风格子词
• 包含常见标点和符号

4.6 线性时间实现

问题：朴素的 WordPiece 编码在最坏情况下是 O(n^2) 的。

解决方案（最大前缀匹配）：

使用 Trie 树（或者 BERT 使用的改进版）实现 O(n) 编码：

1. 构建 Trie 树，节点是字符，边是子词
2. 从根节点开始，贪心地寻找最长匹配
3. 每一步查找是 $O(1)$，总复杂度 O(n)

字典树实现的关键操作：

def encode(self, text):
    tokens = []
    pos = 0
    while pos < len(text):
        # 在 Trie 中找最大匹配
        node = self.root
        longest = 0
        for i in range(pos, len(text)):
            if text[i] not in node.children:
                break
            node = node.children[text[i]]
            if node.is_word_end:
                longest = i - pos + 1
        if longest > 0:
            tokens.append(text[pos:pos+longest])
            pos += longest
        else:
            tokens.append([UNK])
            pos += 1
    return tokens

---

五、三种 Tokenizer 的对比与实践

5.1 数学对比

维度	BPE	SentencePiece	WordPiece
合并依据	频率 \max \text{freq}(a,b)	频率（同 BPE）	似然 \max \text{score}(a,b)
核心公式	\text{freq}(ab)	\text{freq}(ab)	\log P(ab) - \log P(a) - \log P(b)
输入格式	预分词文本	原始文本	预分词文本
语言依赖	需要分词器	语言无关	需要分词器

5.2 词表大小对性能的影响

词表大小 |V| 与 OOV 率的关系：

设语料库中词的频率分布为 $P(w)$，词表大小为 $|V|$。定义截断分布：

P_V(w) = \begin{cases} P(w) & \text{if } w \in V \\ \sum_{w' \notin V} P(w') & \text{if } w = \text{UNK} \end{cases} \tag{5.1}

OOV 率：

\text{OOVRate} = \sum_{w \notin V} P(w) \tag{5.2}

词表大小与覆盖率的实验规律：

对于大规模英文语料：

• $|V| = 10,000$：覆盖率约 85-90%
• $|V| = 30,000$：覆盖率约 95-98%
• $|V| = 50,000$：覆盖率约 98-99%

中文场景注意：上述英文数据不能套用于中文。中文以单字为基础单元，需要更大词表（通常 50K-100K+），序列长度变化规律与英文完全不同。

5.3 子词切分的质量指标

定义（子词信息熵）：

对于子词序列 $s_1, \ldots, s_k$，定义其信息熵：

H(s) = -\sum_{i=1}^k P(s_i) \log P(s_i) \tag{5.3}

其中 P(s_i) 是子词 s_i 在词表中的（归一化）频率。

定义（子词完整性）：

对于词 $w$，定义子词完整性：

\text{Integrity}(w) = \frac{\text{len}(I(w))}{\text{len}(w)} \tag{5.4}

其中 \text{len}(I(w)) 是切分后所有子词的总长度（字符数），\text{len}(w) 是原词长度。比值越大代表切分越零碎（与原文相反）。

澄清：子词信息熵 H(s) = -\sum P(s_i)\log P(s_i) 仅用于衡量词表整体分布均衡性，不能直接用于评判单条文本分词质量。

5.4 训练中的常见问题

问题 1：词表大小选择

• 过大：过拟合到训练语料，泛化能力差
• 过小：OOV 率高，子词序列过长

解决方案：

1. 从 10K 开始，逐步增大到 50K，观察 OOV 率和序列长度
2. 选择使 f(|V|) = \alpha \cdot \text{OOVRate} + \beta \cdot \text{AvgSeqLen} 最小的 |V|

问题 2：特殊字符处理

解决方案：

1. 统一 Unicode 归一化（NFKC）
2. 处理控制字符和格式字符
3. 对于中文字符，通常按单个字符处理

问题 3：训练语料偏置

如果训练语料中某类词出现频率过高，词表会偏向这些词。

解决方案：

1. 下采样高频词
2. 使用分层采样

---

六、数学公式速查

6.1 BPE 核心公式

Pair 频率：

\text{freq}(a,b) = \sum_{s \in C} \text{count}_s(a,b) \tag{6.1}

词表大小：

|V| \approx |V_{\text{base}}| + N_{\text{merge}} \tag{6.2}

（近似关系，非严格等式）

6.2 WordPiece 核心公式

合并得分：

\text{score}(a,b) = \log P(ab) - \log P(a) - \log P(b) \tag{6.3}

6.3 性能指标

OOV 率：

\text{OOVRate} = \sum_{w \notin V} P(w) \tag{6.5}

子词信息熵：

H(s) = -\sum_{s_i} P(s_i) \log P(s_i) \tag{6.6}

---

七、总结

三种 Tokenizer 的定位：

Tokenizer	适用场景	核心优势
BPE	英文为主的西方语言	简单高效，易于实现
SentencePiece	多语言、无分词语言的场景	语言无关，端到端训练
WordPiece	BERT 等需要高质量表示的任务	语言学意义的切分倾向

核心洞察：

子词切分是连接"字符级无 OOV"和"词级语义丰富"的最优解。BPE/WordPiece 通过统计语料库中的 n-gram 频率，在数据驱动和人工设计之间找到了平衡点。SentencePiece 通过端到端的训练方式，使得子词切分不再依赖语言特定的预处理，为多语言模型提供了统一的基础设施。

工程实践要点：

1. 词表大小需要根据具体任务调整，中文通常需要更大的词表
2. SentencePiece 是当前多语言模型的事实标准
3. 编码时使用 Trie 树可以显著加速

---

延伸阅读：

1. Gage, "A New Algorithm for Data Compression" (1994) — BPE 原始论文
2. Sennrich et al., "Neural Machine Translation of Rare Words with Subword Units" (2016) — BPE 引入 NLP
3. Schuster and Nakajima, "Japanese and Korean Voice Search" (2012) — WordPiece 原始论文
4. Kudo, "Subword Regularization: Breaking Text into Subwords for Neural MT" (2018) — SentencePiece
5. Provilkov et al., "BPE-Dropout: Simple and Effective Subword Regularization" (2020)