当前位置：首页 > news >正文

【LLM开发】Unigram算法

news 来源：原创 2025/5/23 6:37:56

Unigram算法

参考：Unigram算法解释
参考书籍：How Can We Make Language Models Better at Handling the Diversity and Variability of Natural Languages
Unigram 算法是一种基于概率的子词分词方法，与BPE算法、WordPiece算法不同，其核心思想是通过逐步删减初始大词汇表优化分词结果。

核心原理

算法基于Unigram 单语言模型，假设每个子词的出现是独立的。句子的概率是由子词序列的乘积决定的。假设每个子词独立出现，因此词汇（子词序列）可以表示为各个subword出现概率的乘积：
$\prod_{i=1}^{L} p(x_{i})$
其中， $x = (x_{1}, x_{2}, ..., x_{L})$ 是subword序列， $p(x_{i})$ 是subword $x_{i}$ 出现的概率。

最优分割

假设，我们已经构建好一个Unigram词汇表。现在输入一个句子 $X$ ，则最优的subword 分割 $x^{*}$ 通过最大化上述概率得到。
$x^{*} = \arg \max _{x \in S(X)} P(x)$
$S (x)$ 表示输入句子 $X$ 后，算法给出的所有可能的subword 分割候选方案。

Unigram算法在这一层面，可以对照最大正相匹配、最大逆向匹配等算法来学习，它并不应该完全对照wordPiece算法或BPE算法进行学习，因为wordPiece算法和BPE等算法更注重如何构建词汇表。

构建词汇表

Unigram算法需要基于一个词汇表（或许我们可以考虑使用BPE算法或者WordPiece算法构建的词汇表，给Unigram算法使用？）。

构建词汇表的流程为：

1.初始化词汇表：从训练语料库中生成一个初始的词汇表，包括所有的字符和一些常见的subword（也可以是所有的subword）。
例如，对于句子hello world!，可以初始化一个包含所有字符和所有subword的词汇表：

['h', 'e', 'l', 'o', 'w', 'r', 'd', '!', 'he', 'el', 'll', 'lo', 'o ', ' w', 'wo', 'or', 'rl', 'ld', 'd!', 'hel', 'ell', 'llo', 'lo ', 'o w', ' wo', 'wor', 'orl', 'rld', 'ld!', 'hell', 'ello', 'word', 'orld', 'rld!' ...]

包含所有子词字符串数量很多，不过在训练构建词表之前，原始的语料库会进行标准化和预分词。简单地说，标准化会将语料库的编码统一；预分词：对于英文而言，会将语料库先按照空格和特殊字符切分，得到带有空格（也可以不带）的一系列单词；然后再依据这些单词构建初始词汇表。

初始词汇表可以有两种方式构建：一种是数据驱动的方法，如BPE算法或Apriori算法生成一个较大的候选子词集合。穷举法穷举所有可能的子词组合（长度 $\le$ 4 的字符序列），穷举法计算成本高。
*穷举法为什么建议要subword长度 $\le$ 4？* 我认为有两个主要原因，以hopefully为例，限制长度，可以减少穷举成本，（如果不限制长度h、ho、hop、hope、hopef、hopefu、hopeful、hopefull、hopefully…会产生45种组合，限制长度后，会产生30种）；其次，对于数据量较小的数据库，hopefully的出现频率可能和ly的频率一致；这样在后面迭代优化词表的时候会直接选择hopefully 的组合方式，这样进一步降低了ly的对于似然函数的贡献，而导致ly被删除。
那么，必定有人问，为什么词汇表尽量不选择hopefully而是选择ly，这是因为ly在真实世界下的分布具有更广泛的分布，是许多副词的组成部分；而hopefully只能表示自身，而不再具有表示其他词的功能。
下图的例子更加直观：经过迭代在hu和hug概率差不多的时候，hug会保留在词汇表中，而hu会被删除。（一切的根源在于语料库中hu和hug的概率是否差不多，因此，语料库尽可能满足真实世界分布）

词汇表的构建目标是不断从当前词汇表移除一些subword，直到词汇表大小 $∣ V ∣ = M$ ， $M$ 表示词汇表预计大小。

2.迭代优化词表
优化subwrod概率：使用的是EM算法优化subword的概率分布，使得边际似然最大化。
如上所述，给定一个subward序列或word $x$ ， $(x_{1}, x_{2}, ..., x_{L}), \forall x_{i} \in V$ ，可以得出：
$\prod_{i=1}^{L} p(x_{i})$

上述公式有一个潜在的假设，及每个子词 $x_{i}$ 的出现都是彼此独立的。

则可以对整个语料库建模其对数似然函数：
$\mathcal{L} = \sum_{x \in C} log(p(x))$

目标是最大化这个 $\mathcal{L}$ ，

Unigram Tokenization算法根据以下两个步骤迭代计算（EM算法 Estimation-Maximization）：

估计步骤：我们计算整个语料库上的对数似然值 $\mathcal{L}$ 。
最大化似然步骤：我们移除 $V$ 中 $\eta$ % 的子词。移除的这些子词后，词汇表能够最大化 $\mathcal {L}$ 。

为了实现估计步骤，我们首先要对语料库中的单词 $x$ ，计算subword tokenization $x_{1}, x_{2}, ..., x_{L}$ 最大化 Unigram 概率。（实现思路可以看HuggingFace Unigram；或者是以下）

语料库中的句子可以被分解为单词、句子、字符；例如This is the Hugging Face Course.
那么 $x$ 可以是句子，This is the Hugging Face Course.；
$x$ 可以是单词，x="This"、x="is"…，
$x$ 可以是字符，x="T"、x="h"、x="i"、…；
但是，对于字符进行建模丧失了词汇的语义，并且Token数量会显著增大->这是因为没有有效压缩信息；
通常来说， $x$ 表示词汇；

Hugging Face对这个进行了一定的更改，可能计算速度更快。
Hugging Face的Unigram算法计算语料库种词汇对当前词汇表的 $l oss$ ，然后计算删除当前词汇中那些出现概率低的词汇对词汇表 $l oss$ 的影响，

估计步骤：使用当前子词概率，通过通过 Viterbi 算法为语料库中的每个词找到最优分词路径；
最大化似然步骤：根据所有分词路径统计子词出现的频率，更新每个词的概率；
$p(x_{i}) = \frac {subword x_{i}出现的概率}{所有子词出现的总次数}$
这一过程不断迭代，直至概率收敛；
当 $∣ V ∣ = M$ 时，停止迭代。
Unigram tokenization 相比BPE分词的关键优势在于，它为给定的分词方式关联了一个概率 $p (x)$ -> $\prod_{i=1}^{L} p(x_{i})$ 。

最大化 $\mathcal{L} = \sum_{x \in C} log(p(x))$ ；实际上是最大化每一个单词的概率 $p (x)$ ，单词的概率是由构成它的subword描述的 $p(x) = p(x_{1})p(x_{2})...p(x_{L})$ ，以词汇hug为例，构成它的子词可以是{"h", "u", "g"} {"hu", "g"} {"h", "ug"}, {"hug"}，因此：
$\begin{align} \mathcal{L} &= \arg\max \sum_{x \in C} log(p(x)) \\ \mathcal{L} &= \sum_{x \in C} \arg\max log(p(x)) \\ \mathcal{L} &= \sum_{x \in C} log(\arg\max p(x)) \\ \end{align}$

所以在编程计算的时候，目标可以是 $\mathcal{L} = \sum_{x \in C} \arg\max log(p(x))$ 或 $\mathcal{L} = \sum_{x \in C} log(\arg\max p(x))$ 。并且 $p(x)=p(x_1)p(x_{2})...p_{L} \rightarrow \log p(x)= \log p(x_{1}) + \log p_{2} + ... +\log p_{L}$ ；求取 $\max log(p(x)) = \max \sum_{i=1}^{L} \log p(x_{i})$ ；求这个可以用动态规划法求解。

Unigram算法

核心原理

最优分割

构建词汇表

相关文章：