一、EM 算法训练 Unigram LM语料的对数似然函数给定一个语料库C{s1,s2,...,sM}其中每个句子s是一个字符序列。对于每个句子s我们用T(s)表示它的所有可能分词方式的集合。在 Unigram 假设下句子s的概率是它所有可能分词方式的概率之和整个语料库的对数似然函数就是所有句子对数概率的和我们的训练目标是其中K是目标词汇表大小V是当前词表。为什么需要 EM 算法这个优化问题有两个难点隐变量存在我们不知道每个句子的正确分词方式T组合优化问题词汇表V是离散的无法直接用梯度下降求解E 步前向 - 后向算法计算期望出现次数实际实现中我们使用前向 - 后向算法Forward-Backward Algorithm可以在O(nL)的时间复杂度内计算出所有 token 的期望出现次数。前向算法Forward Algorithm定义前向变量α(i)为句子前i个字符的所有可能分词方式的概率和。初始化α(0)1空字符串的概率为 1递推公式其中L是词汇表中最长 token 的长度s[i−l:i]表示从位置i−l到i的子串。后向算法Backward Algorithm定义后向变量β(i)为句子从第i个字符到末尾的所有可能分词方式的概率和。初始化β(n)1空字符串的概率为 1递推公式期望出现次数的计算公式有了前向和后向变量我们可以直接计算 token t在句子s中出现在位置i的概率P(t 出现在位置 i∣s)α(n)α(i)⋅P(t)⋅β(i∣t∣)其中∣t∣是 tokent的长度α(n)就是整个句子的概率P(s)。然后token t在句子s中的期望出现次数就是所有位置概率的和最后token t在整个语料中的期望出现次数就是所有句子期望次数的和M 步更新 token 概率M 步的目标是在给定期望出现次数E(t)的情况下找到一组新的概率P(t)使得语料的对数似然最大。构造拉格朗日函数来求解这个带约束的优化问题对P(t)求偏导并令其等于 0所以最终的更新公式就是token 损失计算的推导 EM 迭代收敛后我们需要计算每个 token 的损失以决定删除哪些 token。损失的精确计算公式tokent的损失定义为删除 tokent后语料对数似然的下降量。其中 Lwith t包含 tokent时的语料对数似然Lwithout t删除 tokent后的语料对数似然直接计算这个损失需要对每个 token 都重新运行一次前向算法时间复杂度是O(∣V∣⋅nL)这在词汇表很大时是不可接受的。SentencePiece 中的高效近似计算这个近似基于以下观察删除一个 tokent对语料对数似然的影响主要来自于那些包含t的分词方式。近似损失的计算公式或者更简单的近似SentencePiece 实际使用的这个近似的直观理解是token t的损失等于它在语料中的期望出现次数乘以它的负对数概率。出现次数多的 token损失大概率低的 token负对数概率大损失大SentencePiece 中 EM 算法的实现细节只迭代 1-2 次 EMEM 算法收敛非常快在 Unigram LM 分词问题中EM 算法通常在 1-2 次迭代后就已经收敛到了一个很好的局部最优解后续迭代收益递减第 3 次及以后的迭代对对数似然的提升非常小通常小于 0.1%但会显著增加训练时间平滑项的具体形式为了防止过拟合和概率为 0 的情况SentencePiece 在 M 步会添加一个小的加性平滑项其中ϵ通常设置为10−5。这个平滑项确保了即使一个 token 的期望出现次数为 0它也不会被分配 0 概率。初始词汇表构建的详细过程1.统计语料中所有字符的出现频率2.按照频率从高到低排序字符3.选择前C个字符使得它们的总出现频率达到character_coverage通常是 0.99954.对于剩下的字符不加入初始词汇表而是使用 byte_fallback 处理5.然后统计所有 1-6 gram 的出现频率6.过滤掉出现频率低于阈值的 n-gram通常是 27.将所有单个字符和保留的 n-gram 合并得到初始词汇表二. Viterbi 算法Viterbi 算法解决的是给定一个句子s和词汇表V找到概率最大的分词方式T∗。如前所述我们将其转化为最短路径问题节点0,1,...,nn是句子长度 边i→j当且仅当s[i:j]∈V 边权重w(i,j)−logP(s[i:j])目标找到从0到n的最短路径Viterbi 的动态规划公式:阶段算法处理方式目的训练阶段前向-后向算法把所有切法都加起来估计每个 token 的期望出现次数使用阶段Viterbi 算法只找概率最大的一种切法输出最终分词结果边界条件处理Viterbi 算法的正确性完全依赖于边界条件的严谨处理任何疏漏都会导致分词错误或程序崩溃。以下是三个必须正确处理的边界情况无法到达的位置问题描述在状态转移过程中某些位置i可能没有任何分词方式能够到达此时dp[i]会保持初始值∞。处理方式在遍历每个位置i时首先检查dp[i]是否为∞。如果是直接跳过该位置不进行任何状态转移。无法分词的异常情况问题描述在回溯阶段如果发现prev[current] -1说明从位置current无法回溯到起点。这通常发生在词汇表中缺少某个字符或者句子包含无法识别的符号时。处理方式采用 回退到单个字符 的策略。当遇到无法回溯的位置时强制将当前字符作为一个单独的 token然后继续回溯。byte_fallback 机制的集成问题描述当开启byte_fallbackTrue时词汇表中包含 256 个 UTF-8 字节 token。对于不在词汇表中的字符需要将其拆分为对应的字节 token 进行处理。处理方式在 Viterbi 算法中增加一个特殊分支。如果一个子串不在词汇表中检查它是否是一个单个字符。如果是将其拆分为 UTF-8 字节然后使用字节 token 的概率进行计算。Viterbi 算法的性能优化技巧Viterbi 算法的时间复杂度为O(nL)其中n是句子长度L是最长 token 长度。在处理长文本或大词汇表时可以通过以下技巧进一步提升性能前缀树Trie加速查找问题使用哈希表判断子串是否在词汇表中每次查找都需要创建一个字符串对象开销较大。优化将词汇表存储在一个前缀树中。在状态转移时从当前位置i开始沿着前缀树的边逐个字符匹配直到无法继续为止。效果可以将查找时间从O(L)降低到O(1)平均情况并且避免了创建大量临时字符串。提前终止剪枝问题在状态转移过程中某些位置i的dp[i]值已经非常大即使加上最小可能的 token 成本也无法超过当前已经找到的最优路径。优化预先计算词汇表中所有 token 的最小负对数概率min_cost。在处理位置i时如果dp[i] min_cost dp[n]则可以提前终止对该位置的处理。dp[n] 当前已经找到的完整分词路径的总代价。词表里所有 token 中最小的 token 代价。效果在处理长句子时可以显著减少需要处理的位置数量。并行化处理问题Viterbi 算法的状态转移是顺序执行的无法直接并行化。优化虽然状态转移本身是顺序的但可以将长文本分割成多个独立的句子然后并行处理每个句子。此外在处理单个句子时对于每个位置i可以并行检查所有可能的 token 长度l。效果在多核 CPU 上可以获得接近线性的加速比。三、常见误区1. 为什么 Unigram LM 的 token 概率和为 1但同一句子的所有分词方式概率和不为 1这是理解 Unigram LM 最关键的一个误区。Unigram LM 是一个生成式语言模型它的概率归一化是针对所有可能的 token 序列而不是针对同一个句子的不同分词方式。它假设文本是通过以下随机过程生成的从词汇表中随机选择一个 token概率为P(t)重复步骤 1直到生成一个终止符或达到最大长度在这个生成过程中所有可能的 token 序列包括不同长度的句子的概率之和为 1同一个句子的不同分词方式只是所有可能序列中的一个子集它们的概率之和自然不为 1这就是为什么我们在计算句子概率时需要对所有可能的分词方式求和P(s)T∈T(s)∑P(T)2. 为什么训练过程中永远不删除单个字符 token这是 Unigram LM 分词器的一个基本设计原则目的是保证分词器的完备性。如果我们删除了某个单个字符 token那么任何包含这个字符的句子都无法被正确分词即使这个字符非常生僻我们也必须保留它或者使用 byte_fallback 机制来处理它在 SentencePiece 的实现中单个字符 token 会被标记为 不可删除在计算损失和删除 token 时会被自动跳过
