大语言模型之十 SentencePiece

import re
from collections import Counter, defaultdict


def build_vocab(corpus: str) -> dict:
    """Step 1. Build vocab from text corpus"""

    # Separate each char in word by space and add mark end of token
    tokens = [" ".join(word) + " " for word in corpus.split()]
    
    # Count frequency of tokens in corpus
    vocab = Counter(tokens)  

    return vocab


def get_stats(vocab: dict) -> dict:
    """Step 2. Get counts of pairs of consecutive symbols"""

    pairs = defaultdict(int)
    for word, frequency in vocab.items():
        symbols = word.split()

        # Counting up occurrences of pairs
        for i in range(len(symbols) - 1):
            pairs[symbols[i], symbols[i + 1]] += frequency

    return pairs


def merge_vocab(pair: tuple, v_in: dict) -> dict:
    """Step 3. Merge all occurrences of the most frequent pair"""
    
    v_out = {}
    bigram = re.escape(' '.join(pair))
    p = re.compile(r'(?

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15
• 16
• 17
• 18
• 19
• 20
• 21
• 22
• 23
• 24
• 25
• 26
• 27
• 28
• 29
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58

BPE在字符和单词级别的混合表示之间实现了完美的平衡，使其能够管理大型语料库。这种行为还允许使用适当的子单词标记对词汇表中的任何稀有单词进行编码，而不引入任何“未知”标记。这尤其适用于德语等外语，因为德语中存在许多复合词，很难学习到丰富的词汇。有了这种标记化算法，每个单词现在都可以克服被遗忘的恐惧（athazagoraobia）。

WordPiece

Google的Bert模型在分词的时候使用的是WordPiece算法。与BPE算法类似，WordPiece算法也是每次从词表中选出两个子词合并成新的子词。与BPE的最大区别在于，如何选择两个子词进行合并：BPE选择频数最高的相邻子词合并，而WordPiece选择能够提升语言模型概率最大的相邻子词加入词表。

WordPiece选取子词的方法如下，假设句子$S=(t_1,t_2,\cdots ,t_n)$由n个子词组成，$t_i$表示子词，且假设各个子词之间是独立存在的，则句子$S$的语言模型似然值等价于所有子词概率的乘积：
$$\log P(s)=\sum _{i=1}^N\log P(t_i)$$
设把相邻位置的x和y两个子词进行合并，合并后产生的子词记为z，此时句子$S$似然值的变化可表示为：
$$\log P(t_z)-（logP(t_x)+logP(t_y)）=\log (\frac{P(t_z)}{P(t_x)P(t_y)})$$
似然值的变化就是两个子词之间的互信息。简而言之，WordPiece每次选择合并的两个子词，他们具有最大的互信息值，也就是两子词在语言模型上具有较强的关联性，它们经常在语料中以相邻方式同时出现。

Unigram Language Model (ULM)

与WordPiece一样，Unigram Language Model(ULM)同样使用语言模型来挑选子词。不同之处在于，BPE和WordPiece算法的词表大小都是从小到大变化，属于增量法。而Unigram Language Model则是减量法,即先初始化一个大词表，根据评估准则不断丢弃词表，直到满足限定条件。ULM算法考虑了句子的不同分词可能，因而能够输出带概率的多个子词分段。
对于句子S，$X=(x_1,x_2,\cdots ,x_m)$为句子的一个分词结果，由m个子词组成。所以，当前分词下句子S的似然值可以表示为：
$$P(X)=\prod _{i=1}^{m}P(x_i)$$
对于句子S，挑选似然值最大的作为分词结果，则可以表示为：
$$x^{\ast }=\arg \underset{x\in U(x)}{\max }P(X)$$

这里$U(x)$包含了句子的所有分词结果。在实际应用中，词表大小有上万个，直接罗列所有可能的分词组合不具有操作性。针对这个问题，可通过维特比算法得到$x^{\ast }$来解决。
每个字词的概率$P(x_i)$用最大期望的方法计算，假设当前词表V，则M步最大化对象是如下似然函数：
$$L=\sum _{s=1}^{|D|}\log (P(X^{(s)}))=\sum _{s=1}^{|D|}\log (\sum _{x\in U(X^{(s)})}P(x))$$
其中，|D|是语料库中语料数量。上述公式的一个直观理解是，将语料库中所有句子的所有分词组合形成的概率相加。
初始时，词表V并不存在，因而，ULM算法采用不断迭代的方法来构造词表以及求解分词概率：
1.初始时，建立一个足够大的词表，一般，可用语料中的所有字符加上常见的字符串初始化词表，也可以通过BPE初始化；
2.针对当前词表，用EM算法求解买个subword在语料上的概率；
3.对于每个字词，计算当该字词从词表中移除时，总的loss降低了多少，记为该字词的loss。
4.将字词按照loss大小进行排序，丢弃一定比例loss最小的字词（比如20%），保留下来的字词生成新的词表。这里需要注意的是，单字符不能被丢弃，这是为了避免OOV情况，
5.重复步骤2到4，直到词表大小减少到设定范围。

Sentence Piece

SentencePiece实现了直接从句子训练得到subword的方法(e.g., byte-pair-encoding (BPE) [Sennrich et al.]) and unigram language model [Kudo.])，它是谷歌推出的子词开源工具包，其中集成了BPE、ULM子词算法。除此之外，SentencePiece还能支持字符和词级别的分词。更进一步，为了能够处理多语言问题，sentencePiece将句子视为Unicode编码序列，从而子词算法不用依赖于语言的表示。

Llama使用Sentence Piece Byte-Pair编码（BPE）词元分析器，该词元分析器专为Llama模型设计，不应与OpenAI模型使用的标记器(x)混淆。
使用sentence piece编码中文的例子见Sentencepiece_python_module_example.ipynb

SentencePiece包括下图蓝色的Normaliser，Encoder，Decoder以及Trainer四个部分。

1.Normaliser并不是指对tokenizer之后的数字进行均值和方差归一化，在NLP中，归一化是指标准化文本中的单词，使它们遵循合适的格式。Sentence Piece采用的归一化方法是将单词/字母更改为等效的NFKC Unicode（例如以U+0026开头）。当然也可以用不同unicode方法。对于那些感兴趣的人，可以在这里找到规范化器的C++[https://github.com/google/sentencepiece/blob/master/src/normalizer.cc]实现。
2. trainer使用算法根据subword建立词汇表。SentencePiece支持BPE和unigram两种语言模型。
3.Encoder和Decoder分别是前处理和后处理。
图中的过程可以用SentencePiece 论文如下公式：

Decode(Encode(Normalized(text))) = Normalized(text)
1

这被称为无损tokenization.