Neural Architecture Search

分词算法有BPE(Byte Pair Encoding,BPE )、BBPE（Byte-level BPE）、WordPiece、ULM【Unigram Language Model】等。

Byte Pair Encoding (BPE)

BPE最早是一种数据压缩算法，由Sennrich等人于2015年引入到NLP领域并很快得到推广。该算法简单有效，因而目前它是最流行的方法。GPT-2和RoBERTa使用的Subword算法都是BPE。

BPE获得Subword的步骤如下：

准备足够大的训练语料，并确定期望的Subword词表大小；
将单词拆分为成最小单元。比如英文中26个字母加上各种符号，这些作为初始词表；
在语料上统计单词内相邻单元对的频数，选取频数最高的单元对合并成新的Subword单元；
重复第3步直到达到第1步设定的Subword词表大小或下一个最高频数为1.

Byte-level BPE

Unicode： Unicode 是一种字符集，旨在涵盖地球上几乎所有的书写系统和字符。它为每个字符分配了一个唯一的代码点（code point）用于标识字符。Unicode 不关注字符在计算机内部的具体表示方式，而只是提供了一种字符到代码点的映射。Unicode 的出现解决了字符集的碎片化问题，使得不同的语言和字符能够在一个共同的标准下共存。然而，Unicode 并没有规定如何在计算机内存中存储和传输这些字符。

UTF-8： UTF-8（Unicode Transformation Format-8）是一种变长的字符编码方案，它将 Unicode 中的代码点转换为字节序列。UTF-8 的一个重要特点是它是向后兼容 ASCII 的，这意味着标准的 ASCII 字符在 UTF-8 中使用相同的字节表示，从而确保现有的 ASCII 文本可以无缝地与 UTF-8 共存。在 UTF-8 编码中，字符的表示长度可以是1到4个字节，不同范围的 Unicode 代码点使用不同长度的字节序列表示，这样可以高效地表示整个 Unicode 字符集。UTF-8 的编码规则是：

单字节字符（ASCII 范围内的字符）使用一个字节表示，保持与 ASCII 编码的兼容性。
带有更高代码点的字符使用多个字节表示。UTF-8 使用特定的字节序列来指示一个字符所需的字节数，以及字符的实际数据。

例如，英文字母 “A” 的 Unicode 代码点是U+0041，在 UTF-8 中表示为 0x41（与 ASCII 编码相同）；而中文汉字 “你” 的 Unicode 代码点是U+4F60，在 UTF-8 中表示为0xE4 0xBD 0xA0三个字节的序列。

所以简单的来说：

Unicode 是字符集，为每个字符分配唯一的代码点。
UTF-8 是一种基于 Unicode 的字符编码方式，用于在计算机中存储和传输字符。

Byte(字节)：计算机存储和数据处理时，字节是最小的单位。一个字节包含8个(Bit)二进制位，每个位可以是0或1，每位的不同排列和组合可以表示不同的数据，所以一个字节能表示的范围是256个。

BBPE核心思想将BPE的从字符级别扩展到子节（Byte）级别。BPE的一个问题是如果遇到了unicode编码，基本字符集可能会很大。BBPE就是以一个字节为一种“字符”，不管实际字符集用了几个字节来表示一个字符。这样的话，基础字符集的大小就锁定在了256（2^8）。采用BBPE的好处是可以跨语言共用词表，显著压缩词表的大小。而坏处就是，对于类似中文这样的语言，一段文字的序列长度会显著增长。因此，BBPE based模型可能比BPE based模型表现的更好。然而，BBPE sequence比起BPE来说略长，这也导致了更长的训练/推理时间。BBPE其实与BPE在实现上并无大的不同，只不过基础词表使用256的字节集。

Byte-level BPE(BBPE)和Byte-Pair Encoding (BPE)区别就是BPE是最小词汇是字符级别，而BBPE是字节级别的，通过UTF-8的编码方式这一个字节的256的范围，理论上可以表示这个世界上的所有字符。

所以实现的步骤和BPE就是实现的粒度不一样，其他的都是一样的。

初始词表：构建初始词表，包含一个字节的所有表示(256)。
构建频率统计：统计所有子词单元对（两个连续的子词）在文本中的出现频率。
合并频率最高的子词对：选择出现频率最高的子词对，将它们合并成一个新的子词单元，并更新词汇表。
重复合并步骤：不断重复步骤 2 和步骤 3，直到达到预定的词汇表大小、合并次数，或者直到不再有有意义的合并（即，进一步合并不会显著提高词汇表的效益）。
分词：使用最终得到的词汇表对文本进行分词。

大模型中，以Byte-level BPE(BBPE)这种方式进行分词是不会出现OOV

WordPiece

WordPiece算法与 BPE（Byte-Pair Encoding）都是子词分词算法，但它们在合并策略上存在关键区别。WordPiece的主要目标是通过最大化训练数据的似然（likelihood），即在每次迭代中，选择能最大化训练数据似然增益的子词对（subword pair）进行合并。

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

看到这里，你可能不清楚WordPiece是如何选取子词的。这里，通过形式化方法，能够清楚地理解WordPiece在合并这一步是如何作出选择的。假设句子S=(t1,t2,…,tn)由n个子词组成，ti表示子词，且假设各个子词之间是独立存在的，则句子S的语言模型似然值等价于所有子词概率的乘积：

假设把相邻位置的x和y两个子词进行合并，合并后产生的子词记为z，此时句子S似然值的变化可表示为：

从上面的公式，很容易发现，似然值的变化就是两个子词之间的互信息。简而言之，WordPiece每次选择合并的两个子词，他们具有最大的互信息值，也就是两子词在语言模型上具有较强的关联性，它们经常在语料中以相邻方式同时出现。

算法流程如下：

准备足够大的训练语料
确定期望的subword词表大小
将单词拆分成字符序列
基于第3步数据训练语言模型
从所有可能的subword单元中选择加入语言模型后能最大程度地增加训练数据概率的单元作为新的单元
重复第5步直到达到第2步设定的subword词表大小或概率增量低于某一阈值

Unigram Language Model (ULM)

与WordPiece一样，Unigram Language Model(ULM)同样使用语言模型来挑选子词。不同之处在于，BPE和WordPiece算法的词表大小都是从小到大变化，属于增量法。而Unigram Language Model则是减量法,即先初始化一个大词表，根据评估准则不断丢弃词表，直到满足限定条件。ULM算法考虑了句子的不同分词可能，因而能够输出带概率的多个子词分段。

我们接下来看看ULM是如何操作的。

对于句子S，x→=(x1,x2,…,xm)为句子的一个分词结果，由m个子词组成。所以，当前分词下句子S的似然值可以表示为：

对于句子S，挑选似然值最大的作为分词结果，则可以表示为

这里U(x)包含了句子的所有分词结果。在实际应用中，词表大小有上万个，直接罗列所有可能的分词组合不具有操作性。针对这个问题，可通过维特比算法得到x∗来解决。

那怎么求解每个子词的概率P(xi)呢？ULM通过EM算法来估计。假设当前词表V, 则M步最大化的对象是如下似然函数：

其中，|D|是语料库中语料数量。上述公式的一个直观理解是，将语料库中所有句子的所有分词组合形成的概率相加。

但是，初始时，词表V并不存在。因而，ULM算法采用不断迭代的方法来构造词表以及求解分词概率：

初始时，建立一个足够大的词表。一般，可用语料中的所有字符加上常见的子字符串初始化词表，也可以通过BPE算法初始化。
针对当前词表，用EM算法求解每个子词在语料上的概率。
对于每个子词，计算当该子词被从词表中移除时，总的loss降低了多少，记为该子词的loss。
将子词按照loss大小进行排序，丢弃一定比例loss最小的子词(比如20%)，保留下来的子词生成新的词表。这里需要注意的是，单字符不能被丢弃，这是为了避免OOV情况。
重复步骤2到4，直到词表大小减少到设定范围。

可以看出，ULM会保留那些以较高频率出现在很多句子的分词结果中的子词，因为这些子词如果被丢弃，其损失会很大。