Unigram

#deepLearning/unigram

Unigram tokenization 算法

Unigram 算法常用于 SentencePiece 中，该切分算法被 AlBERT，T5，mBART，Big Bird 和 XLNet 等模型广泛采用。

Unigram 是基于概率的删除策略，从一个大词汇库开始，然后逐步删除词汇，直到达到目标词汇库大小。

对于词汇表中的每个符号，算法计算如果删除该符号，整体损失会增加多少，如果增加得很少，说明这个词对整体来说并不重要可以删掉，然后寻找删除后损失增加最少的符号。

这个过程非常消耗计算资源，因此删除与最低损失增长相关的百分之/p （p 是一个可以控制的超参数，通常是 10 或 20）的符号。然后重复此过程，直到词汇库达到所需大小。

语料库

("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"]

所有可能出现子词的频率

("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)

例如， "ug" 出现在 "hug" ， "pug" 和 "hugs" 中，所以它在我们的语料库中的频率是 20。所以，所有频率之和为 210，子词 "ug" 出现的概率是 20/210。

现在对一个给定的单词进行分词，要查看所有可能的分词组合，并根据 Unigram 模型计算出每种可能的概率。 由于所有的分词都被视为独立的，因此这个单词分词的概率就是每个子词概率的乘积。例如，将 "pug" 分词为 ["p", "u", "g"] 的概率为：

\[ P([\text{“p”}, \text{“u”}, \text{“g”}]) = P(\text{“p”}) \times P(\text{“u”}) \times P(\text{“g”}) = \frac{5}{210} \times \frac{36}{210} \times \frac{20}{210} = 0.000389 \] 将 “pug” 分词为 ["pu", "g"] 的概率为：

\[ P([\text{“pu”}, \text{“g”}]) = P(\text{“pu”}) \times P(\text{“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"]。

计算损失值

语料库中的每个词都有一个分数，损失（loss）值是这些分数的负对数似然 —— 即所有词的语料库中所有词的 -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)

损失值（loss）为

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

“pug”可以被分词为 ["pu", "g"] ，也可以被分词为 ["p", "ug"] ，获得的分数是相同的。因此，去除词汇表中的 "pu" 损失值还会是一样的。

但是，去除 "hug" 之后，损失会变得更糟，因为 "hug" 和 "hugs" 的 tokenization 会变成

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

这些变化将导致损失增加

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

因此， "pu" tokens 可能会从词汇表中移除，但 "hug" 则不会。

实现 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")

计算语料库中每个单词的出现次数

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
        # 循环遍历长度至少为2的子字
        for j in range(i + 2, len(word) + 1):
            subwords_freqs[word[i:j]] += freq

# 按频率对子词排序
sorted_subwords = sorted(subwords_freqs.items(), key=lambda x: x[1], reverse=True)
sorted_subwords[:10]

# outputs:
[('▁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}

计算所有频率的总和，将频率转化为概率

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 里的内容进行比较。

当主循环结束后，我们就从词的最后一个位置开始，然后一步步往前跳，跳过的每一步，我们都会记录下来，直到我们回到词的开头。

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)):
        # best_score_at_start应该由循环的前面的步骤计算和填充
        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
                # 如果我们发现以 end_idx 结尾的更好分段,我们会更新
                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:
        # 我们没有找到单词的 tokens  -> 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))

# outputs:
(['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)

# outputs:
413.10377642940875

计算分数

import copy

def compute_scores(model):
    scores = {}
    model_loss = compute_loss(model)
    for token, score in model.items():
        # 我们将保留长度为 1 的 tokens
        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"])

# outputs:
6.376412403623874
0.0

这种方式效率非常低，所以 SentencePiece 使用了一种估算方法来计算如果没有 X token，模型的损失会是多少：它不是重新开始，而是只是用剩下的词表里 X token 的分词方式来替代它。这样，所有的得分都能在和模型损失一起的同时计算出来。

将模型使用的特殊 tokens 添加到词汇表中，然后循环直到从词汇表中剪除足够多的 tokens 以达到期望的规模

percent_to_remove = 0.1
while len(model) > 100:
    scores = compute_scores(model)
    sorted_scores = sorted(scores.items(), key=lambda x: x[1])
    # 删除分数最低的percent_to_remov tokens 。
    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()}

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)

# outputs:
['▁This', '▁is', '▁the', '▁Hugging', '▁Face', '▁', 'c', 'ou', 'r', 's', 'e', '.']