前言
Unigram算法通常用于SentencePiece中，这是AlBERT、T5、mBART、Big Bird和XLNet等模型使用的分词算法。
💡 本节深入介绍了Unigram算法，甚至展示了一个完整的实现。如果您只想了解分词算法的一般概述，可以跳到结尾部分。
src link: https://huggingface.co/learn/nlp-course/chapter6/7
Operating System: Ubuntu 22.04.4 LTS
参考文档
训练算法
与BPE和WordPiece相比，Unigram的工作方向相反：它从一个大的词汇表开始，从中移除标记，直到达到所需的词汇表大小。构建这个基础词汇表有几种选择：例如，我们可以取预分词单词中最常见的子串，或者在对初始语料库应用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”) \times P(u") \times P(g”) = \frac{5}{210} \times \frac{36}{210} \times \frac{20}{210} = 0.000389$$
相比之下，标记化[“pu”, “g”]的概率为：
$$P([pu", g”]) = P(pu") \times P(g”) = \frac{5}{210} \times \frac{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算法。本质上，我们可以构建一个图来检测给定词的可能分段，方法是如果从字符a到字符b的子词在词汇表中，就说从字符a到字符b有一条边，并且给这条边分配子词的概率。
为了找到图中具有最佳分数的路径，Viterbi算法确定了单词中每个位置的最佳分数分段，该分段在该位置结束。由于我们从开始到结束，因此可以通过遍历所有以当前位置结束的子词，然后使用从此子词开始位置的标记化最佳分数来找到最佳分数。然后，我们只需展开到达终点的路径。
让我们使用我们的词汇表和单词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”]。
现在轮到您了！确定单词huggun”的标记化及其分数。
回到训练
现在我们已经了解了标记化是如何工作的，我们可以更深入地探讨训练期间使用的损失。在任何给定阶段，此损失都是通过使用当前词汇表和Unigram模型（如前所述，由语料库中每个标记的频率确定）对语料库中的每个单词进行标记化来计算的。
语料库中的每个单词都有一个分数，损失是这些分数的负对数似然性——也就是说，语料库中所有单词的-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现在我们需要计算删除每个标记如何影响损失。这相当繁琐，所以在这里我们只对两个标记进行计算，等到有代码帮助我们时再进行整个过程。在这个（非常）特定的案例中，我们有两个所有单词的等价标记化：如前所述，例如，pug”可以标记化为[“p”, “ug”]，并且具有相同的分数。因此，从词汇表中删除pu”标记将产生完全相同的损失。
另一方面，删除hug”会使损失变得更糟，因为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”可能会从词汇表中删除，但不是hug”。
实现Unigram
现在让我们用代码实现我们到目前为止看到的所有内容。与BPE和WordPiece一样，这不是Unigram算法的高效实现（恰恰相反），但它应该能帮助您更好地理解它。
我们将使用与之前相同的语料库作为示例：
corpus = [
"This is the Hugging Face Course.",
"This chapter is about tokenization.",
"This section shows several tokenizer algorithms.",
"Hopefully, you will be able to understand how they are trained and generate tokens.",
]这次，我们将使用xlnet-base-cased作为我们的模型：
from transformers import AutoTokenizer
tokenizer = AutoTokenizer.from_pretrained("xlnet-base-cased")与BPE和WordPiece一样，我们从计算语料库中每个单词的出现次数开始：
from collections import defaultdict
word_freqs = defaultdict(int)
for text in corpus:
words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
new_words = [word for word, offset in words_with_offsets]
for word in new_words:
word_freqs[word] += 1
word_freqs然后，我们需要将词汇表初始化为比我们最终想要的词汇量大一些的东西。我们必须包括所有基本字符（否则我们将无法标记化每个单词），但对于较大的子字符串，我们只保留最常见的子字符串，因此我们按频率对它们进行排序：
char_freqs = defaultdict(int)
subwords_freqs = defaultdict(int)
for word, freq in word_freqs.items():
for i in range(len(word)):
char_freqs[word[i]] += freq
# Loop through the subwords of length at least 2
for j in range(i + 2, len(word) + 1):
subwords_freqs[word[i:j]] += freq
# Sort subwords by frequency
sorted_subwords = sorted(subwords_freqs.items(), key=lambda x: x[1], reverse=True)
sorted_subwords[:10][('▁t', 7), ('is', 5), ('er', 5), ('▁a', 5), ('▁to', 4), ('to', 4), ('en', 4), ('▁T', 3), ('▁Th', 3), ('▁Thi', 3)]我们将字符与最佳子词组合，以获得大小为300的初始词汇表：
token_freqs = list(char_freqs.items()) + sorted_subwords[: 300 - len(char_freqs)]
token_freqs = {token: freq for token, freq in token_freqs}💡 SentencePiece使用一种更高效的算法，称为增强后缀数组（ESA）来创建初始词汇表。
接下来，我们计算所有频率的总和，将频率转换为概率。对于我们的模型，我们将存储概率的对数，因为与乘以小数相比，相加对数在数值上更稳定，这将简化模型损失的计算：
from math import log
total_sum = sum([freq for token, freq in token_freqs.items()])
model = {token: -log(freq / total_sum) for token, freq in token_freqs.items()}现在主要的函数是使用Viterbi算法标记化单词的函数。正如我们之前所看到的，该算法计算单词的每个子字符串的最佳分段，我们将将其存储在一个名为best_segmentations的变量中。我们将为单词中的每个位置（从0到其总长度）存储一个字典，其中包含两个键：最佳分段中最后一个标记的起始位置的索引，以及最佳分段的分数。一旦列表完全填充，我们将能够使用最后一个标记的起始位置的索引来检索完整的分段。
填充列表只需两个循环：主循环遍历每个起始位置，第二个循环尝试从该起始位置开始的所有子字符串。如果子字符串在词汇表中，我们就有了直到该结束位置的单词的一个新的分段，我们将它与best_segmentations中的内容进行比较。
一旦主循环完成，我们就从最后开始，从一个起始位置跳到下一个，一边前进一边记录遇到的tokens，直到我们到达单词的开头。
def encode_word(word, model):
best_segmentations = [{"start": 0, "score": 1}] + [
{"start": None, "score": None} for _ in range(len(word))
]
for start_idx in range(len(word)):
# This should be properly filled by the previous steps of the loop
best_score_at_start = best_segmentations[start_idx]["score"]
for end_idx in range(start_idx + 1, len(word) + 1):
token = word[start_idx:end_idx]
if token in model and best_score_at_start is not None:
score = model[token] + best_score_at_start
# If we have found a better segmentation ending at end_idx, we update
if (
best_segmentations[end_idx]["score"] is None
or best_segmentations[end_idx]["score"] > score
):
best_segmentations[end_idx] = {"start": start_idx, "score": score}
segmentation = best_segmentations[-1]
if segmentation["score"] is None:
# We did not find a tokenization of the word -> unknown
return ["<unk>"], None
score = segmentation["score"]
start = segmentation["start"]
end = len(word)
tokens = []
while start != 0:
tokens.insert(0, word[start:end])
next_start = best_segmentations[start]["start"]
end = start
start = next_start
tokens.insert(0, word[start:end])
return tokens, score我们可以在一些单词上尝试我们的初始模型。
print(encode_word("Hopefully", model))
print(encode_word("This", model))(['H', 'o', 'p', 'e', 'f', 'u', 'll', 'y'], 41.5157494601402)
(['This'], 6.288267030694535)现在，计算模型在语料库上的损失变得很容易了！
def compute_loss(model):
loss = 0
for word, freq in word_freqs.items():
_, word_loss = encode_word(word, model)
loss += freq * word_loss
return loss我们可以检查它在我们拥有的模型上是否有效。
compute_loss(model)413.10377642940875计算每个标记的分数并不难；我们只需要计算通过删除每个标记得到的模型的损失。
import copy
def compute_scores(model):
scores = {}
model_loss = compute_loss(model)
for token, score in model.items():
# We always keep tokens of length 1
if len(token) == 1:
continue
model_without_token = copy.deepcopy(model)
_ = model_without_token.pop(token)
scores[token] = compute_loss(model_without_token) - model_loss
return scores我们可以尝试在一个给定的标记上这样做：
scores = compute_scores(model)
print(scores["ll"])
print(scores["his"])由于 “ll” 在 “Hopefully” 的分词中使用，并且移除它可能会让我们两次使用标记 “l”，我们预计这将有一个正的损失。”his” 只在单词 “This” 内部使用，它被分词为自身，所以我们预计它的损失为零。以下是结果：
6.376412403623874
0.0💡 这种方法效率非常低，因此 SentencePiece 使用了模型中没有标记 X 的损失的近似值：它不是从零开始，而是只使用剩余词汇中的分词替换标记 X。这样，所有分数都可以在一次计算中同时与模型损失一起计算出来。
在所有这些准备就绪后，我们需要做的最后一件事是将模型使用的特殊标记添加到词汇表中，然后循环，直到我们从词汇表中剪掉足够的标记以达到我们期望的大小：
percent_to_remove = 0.1
while len(model) > 100:
scores = compute_scores(model)
sorted_scores = sorted(scores.items(), key=lambda x: x[1])
# Remove percent_to_remove tokens with the lowest scores.
for i in range(int(len(model) * percent_to_remove)):
_ = token_freqs.pop(sorted_scores[i][0])
total_sum = sum([freq for token, freq in token_freqs.items()])
model = {token: -log(freq / total_sum) for token, freq in token_freqs.items()}然后，要分词一些文本，我们只需要应用预分词，然后使用我们的 encode_word() 函数：
def tokenize(text, model):
words_with_offsets = tokenizer.backend_tokenizer.pre_tokenizer.pre_tokenize_str(text)
pre_tokenized_text = [word for word, offset in words_with_offsets]
encoded_words = [encode_word(word, model)[0] for word in pre_tokenized_text]
return sum(encoded_words, [])
tokenize("This is the Hugging Face course.", model)['▁This', '▁is', '▁the', '▁Hugging', '▁Face', '▁', 'c', 'ou', 'r', 's', 'e', '.']这就是 Unigram 的全部内容！希望现在您已经感觉自己像是一个分词器方面的专家了。在下一节中，我们将深入探讨 🤗 Tokenizers 库的构建块，并向您展示如何使用它们来构建自己的分词器。
结语
第三百一十五篇博文写完，开心！！！！
今天，也是充满希望的一天。
