分词

语言模型 $p$ 是建立在词元（token）序列的上的一个概率分布输出，其中每个词元来自某个词汇表$V$，如下的形式。

[the, mouse, ate, the, cheese]

Tips: 词元(token)一般在NLP（自然语言处理）中来说，通常指的是一个文本序列中的最小单元，可以是单词、标点符号、数字、符号或其他类型的语言元素。通常，对于NLP任务，文本序列会被分解为一系列的tokens，以便进行分析、理解或处理。在英文中一个"token"可以是一个单词，也可以是一个标点符号。在中文中，通常以字或词作为token（这其中就包含一些字符串分词的差异性，将在后续内容中讲到）。

然而，自然语言并不是以词元序列的形式出现，而是以字符串的形式存在（具体来说，是Unicode字符的序列），比如上面的序列的自然语言为“the mouse ate the cheese”。

分词器将任意字符串转换为词元序列： 'the mouse ate the cheese.' $\Rightarrow [the,mouse,ate,the,cheese,.]$

Tips: 熟悉计算机的可能清晰字符串和序列的差异性，这里只做一个简要的说明。 字符串：所有字母、符号和空格都是这这个字符串的一部分。 词元序列：由多个字符串组成（相当于把一个字符串分割为了多了子字符串，每个子字符串是一个词元）

基于空格的分词

可视化的词编码： https://observablehq.com/@simonw/gpt-tokenizer

分词，其实从字面很好理解，就是把词分开，从而方便对于词进行单独的编码，对于英文字母来说，由于其天然的主要由单词+空格+标点符号组成，最简单的解决方案是使用text.split(' ')方式进行分词，这种分词方式对于英文这种按照空格，且每个分词后的单词有语义关系的文本是简单而直接的分词方式。然而，对于一些语言，如中文，句子中的单词之间没有空格，例如下文的形式。

$$\mathrm{今}\mathrm{天}\mathrm{去}\mathrm{了}\mathrm{商}\mathrm{店}。\text{"我今天去了商店。"}$$

还有一些语言，比如德语，存在着长的复合词（例如Abwasserbehandlungsanlange）。即使在英语中，也有连字符词（例如father-in-law）和缩略词（例如don't），它们需要被正确拆分。例如，Penn Treebank将don't拆分为do和n't，这是一个在语言上基于信息的选择，但不太明显。因此，仅仅通过空格来划分单词会带来很多问题。

那么，什么样的分词才是好的呢？目前从直觉和工程实践的角度来说：

• 首先我们不希望有太多的词元（极端情况：字符或字节），否则序列会变得难以建模。
• 其次我们也不希望词元过少，否则单词之间就无法共享参数（例如，mother-in-law和father-in-law应该完全不同吗？），这对于形态丰富的语言尤其是个问题（例如，阿拉伯语、土耳其语等）。
• 每个词元应该是一个在语言或统计上有意义的单位。

Byte pair encoding

将字节对编码（BPE (opens new window)）算法应用于数据压缩领域，用于生成其中一个最常用的分词器。BPE分词器需要通过模型训练数据进行学习，获得需要分词文本的一些频率特征。

学习分词器的过程，直觉上，我们先将每个字符作为自己的词元，并组合那些经常共同出现的词元。整个过程可以表示为：

• Input(输入)：训练语料库（字符序列）。 算法步骤
• Step1. 初始化词汇表 $V$ 为字符的集合。
• while(当我们仍然希望V继续增长时)： Step2. 找到$V$ 共同出现次数最多的元素对 $x,x^{\prime }$ 。
• Step1. 用一个新的符号 $x{x}^{\prime }$ 替换所有 $x,x^{\prime }$ 的出现。
• Step4. 将$x{x}^{\prime }$ 添加到V中。

这里举一个例子：

输入语料： Input:

I = [['the car','the cat','the rat']]

我们可以发现这个输入语料是三个字符串。

Step1. 首先我们要先构建初始化的词汇表$V$,所以我们将所有的字符串按照字符进行切分，得到如下的形式：

[['t', 'h', 'e', '$\space$', 'c', 'a', 'r'],
['t', 'h', 'e', '$\space$', 'c', 'a', 't'],
['t', 'h', 'e', '$\space$', 'r', 'a', 't']]

对于着三个切分后的集合我们求其并集，从而得到了初始的词汇表$V$=['t','h','e',' ','c','a','r','t']。

在此基础上我们假设期望继续扩充$V$,我们开始执行 Step2-4.

执行 Step2.找到$V$ 共同出现次数最多的元素对 $x,x^{\prime }$: 我们找到$V$ 共同出现次数最多的元素对 $x,x^{\prime }$，我们发现't'和'h'按照'th'形式一起出现了三次，'h'和'e'按照'he'形式一起出现了三次，我们可以随机选择其中一组，假设我们选择了'th'。

执行 Step1. 用一个新的符号 $x{x}^{\prime }$ 替换所有 $x,x^{\prime }$ 的出现： 将之前的序列更新如下：(th 出现了 1次)

[[th, e, $\sqcup$, c, a, r], 
[th, e, $\sqcup$, c, a, t],
[th, e, $\sqcup$, r, a, t]] 

执行 Step4. 将$x{x}^{\prime }$ 添加到V中： 从而得到了一次更新后的词汇表$V$=['t','h','e',' ','c','a','r','t','th']。

接下来如此往复：

1. [the, $\bigsqcup ,c,a,r]$, [the, $\bigsqcup ,c,a,t],[$ the, $\bigsqcup ,r,a,t]$ (the 出现了 1次)

2. [the, $\bigsqcup ,ca,r]$, [the, $\bigsqcup ,ca,t],[$ the, $\bigsqcup ,ra,t]$ (ca 出现了 2次)

Unicode的问题

Unicode（统一码）是当前主流的一种编码方式。其中这种编码方式对BPE分词产生了一个问题（尤其是在多语言环境中），Unicode字符非常多（共144,697个字符）。在训练数据中我们不可能见到所有的字符。 为了进一步减少数据的稀疏性，我们可以对字节而不是Unicode字符运行BPE算法（Wang等人，2019年 (opens new window)）。 以中文为例：

$$\text{ 今天}\Rightarrow \text{[x62, x11, 4e, ca]}$$

BPE算法在这里的作用是为了进一步减少数据的稀疏性。通过对字节级别进行分词，可以在多语言环境中更好地处理Unicode字符的多样性，并减少数据中出现的低频词汇，提高模型的泛化能力。通过使用字节编码，可以将不同语言中的词汇统一表示为字节序列，从而更好地处理多语言数据。

Unigram model (SentencePiece)

与仅仅根据频率进行拆分不同，一个更“有原则”的方法是定义一个目标函数来捕捉一个好的分词的特征，这种基于目标函数的分词模型可以适应更好分词场景，Unigram model就是基于这种动机提出的。我们现在描述一下unigram模型（Kudo，2018年 (opens new window)）。

这是SentencePiece工具（Kudo＆Richardson，2018年 (opens new window)）所支持的一种分词方法，与BPE一起使用。 它被用来训练T5和Gopher模型。给定一个序列 $x_{1:L}$ ，一个分词器 $T$ 是 $p\left(x_{1:L}\right)=\prod _{(i,j)\in T}p\left(x_{i:j}\right)$ 的一个集合。这边给出一个实例：

• 训练数据（字符串）： $𝖺𝖻𝖺𝖻𝖼$
• 分词结果 $T=(1,2),(1,4),(5,5)$ （其中 $V=\{𝖺𝖻,𝖼\}$ ）
• 似然值： $p(x_{1:L})=2/1\cdot 2/1\cdot 1/1=4/27$

在这个例子中，训练数据是字符串" $𝖺𝖻𝖺𝖻𝖼$ "。分词结果 $T=(1,2),(1,4),(5,5)$ 表示将字符串拆分成三个子序列： $，，(𝖺,𝖻)，(𝖺,𝖻)，(𝖼)$ 。词汇表 $V=\{𝖺𝖻,𝖼\}$ 表示了训练数据中出现的所有词汇。

似然值 $p(x_{1:L})$ 是根据 unigram 模型计算得出的概率，表示训练数据的似然度。在这个例子中，概率的计算为 $2/1\cdot 2/1\cdot 1/1=4/27$ 。这个值代表了根据 unigram 模型，将训练数据分词为所给的分词结果 $T $ 概率。

unigram 模型通过统计每个词汇在训练数据中的出现次数来估计其概率。在这个例子中， $𝖺𝖻$ 在训练数据中出现了两次， $𝖼$ 出现了一次。因此，根据 unigram 模型的估计， $p(𝖺𝖻)=2/1$ ， $p(𝖼)=1/1$ 。通过将各个词汇的概率相乘，我们可以得到整个训练数据的似然值为 $4/27$ 。

似然值的计算是 unigram 模型中重要的一部分，它用于评估分词结果的质量。较高的似然值表示训练数据与分词结果之间的匹配程度较高，这意味着该分词结果较为准确或合理。

算法流程

• 从一个“相当大”的种子词汇表 $V$ 开始。
• 重复以下步骤：
  • 给定 $V$ ，使用EM算法优化 $p(x)$ 和 $T$ 。
  • 计算每个词汇 $x\in V$ 的 $loss(x)$ ，衡量如果将 $x$ 从 $V$ 中移除，似然值会减少多少。
  • 按照 $loss$ 进行排序，并保留 $V$ 中排名靠前的80%的词汇。

这个过程旨在优化词汇表，剔除对似然值贡献较小的词汇，以减少数据的稀疏性，并提高模型的效果。通过迭代优化和剪枝，词汇表会逐渐演化，保留那些对于似然值有较大贡献的词汇，提升模型的性能。