Unigram Tokenization

Unigram 算法通常用于 SentencePiece，这是 AlBERT、T5、mBART、Big Bird 和 XLNet 等模型使用的分词算法。

它从一个较大的词汇表开始，然后逐步删除其中的 token，直到达到所需的词汇大小。构建词汇表有几种选择：例如，我们可以从预分词的单词中提取最常见的子字符串，或者在初始语料库上应用 BPE，设置一个较大的词汇表大小。

在每个训练步骤中，Unigram 算法根据当前词汇表计算语料库的损失。然后，对于词汇表中的每个符号，算法计算如果删除该符号，整体损失将增加多少，并寻找增加损失最少的符号。这些符号对整体损失的影响较小，因此在某种意义上它们“需求较低”，是最适合被删除的候选符号。

这个操作非常耗费资源，因此我们并不是仅仅删除与最低损失增加相关联的单个符号，而是删除与最低损失增加相关联的 p（p 是一个可以控制的超参数，通常为 10 或 20）百分比的符号。这个过程会重复进行，直到词汇表达到所需的大小。

请注意，我们永远不会删除基本字符，以确保任何单词都可以被分词。

现在，这仍然有些模糊：算法的主要部分是计算语料库的损失，并观察在删除某些标记后它是如何变化的，但我们尚未解释如何做到这一点。这一步骤依赖于 Unigram 模型的分词算法，因此我们将在接下来详细介绍这一部分。

假设我们有如下语料库：

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

对于这个例子，我们将所有子串作为初始词汇表：

["h", "u", "g", "hu", "ug", "p", "pu", "n", "un", "b", "bu", "s", "hug", "gs", "ugs"]

Unigram 模型是一种语言模型，认为每个标记与之前的标记是独立的。从某种意义上说，它是最简单的语言模型，因为给定之前上下文的标记 X 的概率仅仅是标记 X 的概率。因此，如果我们使用 Unigram 语言模型来生成文本，我们总是会预测最常见的标记。

给定标记的概率是其在原始语料库中的频率（出现的次数），除以词汇表中所有标记频率的总和（以确保概率之和为 1）。例如，“ug” 出现在 “hug”、“pug” 和 “hugs” 中，因此在我们的语料库中它的频率为 20。

以下是词汇中所有可能子词的频率：

("h", 15) ("u", 36) ("g", 20) ("hu", 15) ("ug", 20) ("p", 17) ("pu", 17) ("n", 16)
("un", 16) ("b", 4) ("bu", 4) ("s", 5) ("hug", 15) ("gs", 5) ("ugs", 5)

因此，所有频率的总和为 210，子词 “ug” 的概率为 20/210。

现在，要对给定的单词进行分词，我们查看所有可能的标记分割方式，并根据 Unigram 模型计算每种方式的概率。由于所有标记被视为独立的，因此这个概率仅仅是每个标记概率的乘积。例如，单词 “pug” 的分词 [“p”, “u”, “g”] 的概率为：

P([‘‘p“,‘‘u“,‘‘g“])=P(‘‘p“)×P(‘‘u“)×P(‘‘g“)=5/210​×36/210​×20/210​=0.000389

相对而言，分词 [“pu”, “g”] 的概率为：

P([‘‘pu“,‘‘g“])=P(‘‘pu“)×P(‘‘g“)=5/210​×20/210​=0.0022676

因此，这种分词的概率更高。一般来说，标记数量最少的分词将具有最高的概率（因为每个标记都要进行一次 210 的除法），这直观上符合我们的目标：将一个单词拆分为尽可能少的标记。

因此，使用 Unigram 模型对单词的分词就是具有最高概率的分词。在 “pug” 的例子中，以下是我们为每种可能的分割获得的概率：

["p", "u", "g"] : 0.000389
["p", "ug"] : 0.0022676
["pu", "g"] : 0.0022676

因此，“pug” 将被分词为 [“p”, “ug”] 或 [“pu”, “g”]，具体取决于首先遇到的哪种分割（请注意，在更大的语料库中，这种相等情况是很少见的）。

在这种情况下，找出所有可能的分词并计算它们的概率是比较容易的，但一般来说，这会稍微困难一些。有一个经典算法用于此，称为维特比算法（Viterbi algorithm）。本质上，我们可以构建一个图来检测给定单词的可能分词，方法是如果从字符 a 到字符 b 的子词在词汇表中，则在字符 a 和字符 b 之间建立一个分支，并将该分支的概率赋给子词的概率。

为了在这个图中找到最佳得分的路径，维特比算法会确定在单词的每个位置，结束于该位置的得分最高的分词。由于我们是从开头到结尾，因此可以通过循环遍历所有以当前的位置结束的子词，并使用从该子词开始位置的最佳分词得分来找到这个最佳得分。然后，我们只需回溯到达末尾时所采取的路径。

让我们看看一个使用我们词汇表和单词 “unhug” 的示例。对于每个位置，结束于该位置的最佳得分子词如下：

Character 0 (u): "u" (score 0.171429)
Character 1 (n): "un" (score 0.076191)
Character 2 (h): "un" "h" (score 0.005442)
Character 3 (u): "un" "hu" (score 0.005442)
Character 4 (g): "un" "hug" (score 0.005442)

因此，“unhug” 将被分词为 [“un”, “hug”]。

现在我们已经了解了分词的工作原理，可以更深入地探讨训练过程中使用的损失函数。在任意阶段，这个损失是通过使用当前词汇表和基于语料库中每个 token 频率确定的 Unigram 模型，对语料库中的每个词进行分词来计算的（如前所述）。

语料库中的每个词都有一个得分，而损失是这些得分的负对数似然值，即语料库中所有词的 −log⁡(P(word))-\log(P(\text{word}))−log(P(word)) 的总和。

让我们回到之前的例子，使用以下语料库：

("hug", 10), ("pug", 5), ("pun", 12), ("bun", 4), ("hugs", 5)

每个词的分词及其对应的得分为：

"hug": ["hug"] (score 0.071428)
"pug": ["pu", "g"] (score 0.007710)
"pun": ["pu", "n"] (score 0.006168)
"bun": ["bu", "n"] (score 0.001451)
"hugs": ["hug", "s"] (score 0.001701)

因此，损失为：

10 * (-log(0.071428)) + 5 * (-log(0.007710)) + 12 * (-log(0.006168)) + 4 * (-log(0.001451)) + 5 * (-log(0.001701)) = 169.8

现在我们需要计算删除每个 token 如何影响损失值。这个过程相当繁琐，所以我们这里只计算两个 token 的情况，完整的过程留待我们有代码辅助时再进行。在这个（非常）特殊的例子中，我们对所有词有两种等效的分词方式：正如我们之前看到的，例如 “pug” 可以分为 [“p”, “ug”]，得分相同。因此，从词汇表中删除 “pu” token 不会改变损失值。

另一方面，删除 “hug” token 会使损失变得更大，因为 “hug” 和 “hugs” 的分词将变成：

"hug": ["hu", "g"] (score 0.006802)
"hugs": ["hu", "gs"] (score 0.001701)

这些变化将导致损失增加：

- 10 * (-log(0.071428)) + 10 * (-log(0.006802)) = 23.5

因此，”pu” 这个 token 可能会从词汇表中被移除，而 “hug” 不会被移除。

来源：https://huggingface.co/learn/nlp-course/en/chapter6/7?fw=pt