Viterbi Sampling算法的改进与完善 2024-05-29 作者 C3P00 在自然语言处理领域，分词是一个至关重要的步骤。最近，一篇名为《随机分词浅探：从Viterbi Decoding到Viterbi Sampling》的文章中，作者提出了一种名为“Viterbi Sampling”的随机分词算法。本文将详细讨论该算法的改进，并从数学上证明其效果可以与Subword Regularization等价。 问题分析 在知乎的评论中，用户 @鹤舞 指出，当前的采样算法可能会在多次二选一的过程中“稀释”了部分方案的出现概率，导致原本分数最高的切分并不是以最高概率出现。 例如，假设有三种切分方案，每种方案的得分都一样，理应每种方案的出现概率都是1/3。然而，Viterbi Sampling算法将多选一的过程拆分成多步的二选一，从而导致概率分布发生偏移。 示例分析 以单词“watching”为例，有三种切分方案：watch ing, wat ching, 和 w atching。按照Viterbi Sampling的操作，先在前两种方案中选择，概率均为1/2；然后再与第三种方案比较，概率依然为1/2。最终，前两种方案的出现概率为1/4，而第三种方案的出现概率变为了1/2。 解决办法 为了解决上述问题，可以采用“水塘采样（Reservoir sampling）”的算法。具体来说，每次进行二选一后，同时缓存累积概率，并在后续的二选一过程中使用累积概率进行比较。 具体实现 假设前两种切分方案的概率均为1/3，选择其中一种后，总的累积概率为2/3。接下来，新方案被选中的概率为1/3，而不是1/2。这保证了每种方案的出现概率均保持为1/3。 在实际计算时，为避免指数爆炸问题，可以缓存对数形式的概率，并利用logsumexp函数避免溢出。 Zlogi = logsumexp(Zlogi-1, αsi) 相应的实现已经内置在bytepiece>=0.5.0中。 完美采样的证明 为了证明改进后的Viterbi Sampling算法是“完美采样”，我们需要回顾Viterbi Decoding的基本原理。Viterbi Decoding通过动态规划找出最优的分词方案，其子串也必须是对应子字节串的最优切分方案。 数学推导 通过动态规划，可以计算出每个位置的最优切分方案及其得分。而在Viterbi Sampling中，我们需要对所有切分方案进行采样，其采样概率应与得分成正比。 Z(c1, c2, ..., cl) = ∑ Z(c1, ..., ck) * e^(α * s(ck+1, ..., cl)) 通过逐步计算累积权重Z. 可以实现对所有切分方案的完美采样。✅ 递归式转换 在实际计算中，使用对数形式的累积权重Zlog，并通过logsumexp函数进行累积计算。 Zlog(c1, c2, ..., cl) = logsumexp(Zlog(c1, ..., ck) + α * s(ck+1, ..., cl)) 这样可以避免直接计算指数导致的溢出问题。 文章小结 本文通过详细分析和数学推导，完善了之前提出的Viterbi Sampling算法。改进后的算法不仅解决了概率“稀释”问题，而且在效果上与Subword Regularization等价，同时在使用效率上更具优势。 通过这些改进，Viterbi Sampling算法在实际应用中将具备更高的可靠性和效率，为自然语言处理领域的分词任务提供了更优的解决方案。
在自然语言处理领域，分词是一个至关重要的步骤。最近，一篇名为《随机分词浅探：从Viterbi Decoding到Viterbi Sampling》的文章中，作者提出了一种名为“Viterbi Sampling”的随机分词算法。本文将详细讨论该算法的改进，并从数学上证明其效果可以与Subword Regularization等价。
问题分析
在知乎的评论中，用户 @鹤舞 指出，当前的采样算法可能会在多次二选一的过程中“稀释”了部分方案的出现概率，导致原本分数最高的切分并不是以最高概率出现。
例如，假设有三种切分方案，每种方案的得分都一样，理应每种方案的出现概率都是1/3。然而，Viterbi Sampling算法将多选一的过程拆分成多步的二选一，从而导致概率分布发生偏移。
示例分析
以单词“watching”为例，有三种切分方案：watch ing, wat ching, 和 w atching。按照Viterbi Sampling的操作，先在前两种方案中选择，概率均为1/2；然后再与第三种方案比较，概率依然为1/2。最终，前两种方案的出现概率为1/4，而第三种方案的出现概率变为了1/2。
解决办法
为了解决上述问题，可以采用“水塘采样（Reservoir sampling）”的算法。具体来说，每次进行二选一后，同时缓存累积概率，并在后续的二选一过程中使用累积概率进行比较。
具体实现
假设前两种切分方案的概率均为1/3，选择其中一种后，总的累积概率为2/3。接下来，新方案被选中的概率为1/3，而不是1/2。这保证了每种方案的出现概率均保持为1/3。
在实际计算时，为避免指数爆炸问题，可以缓存对数形式的概率，并利用logsumexp函数避免溢出。
相应的实现已经内置在bytepiece>=0.5.0中。
完美采样的证明
为了证明改进后的Viterbi Sampling算法是“完美采样”，我们需要回顾Viterbi Decoding的基本原理。Viterbi Decoding通过动态规划找出最优的分词方案，其子串也必须是对应子字节串的最优切分方案。
数学推导
通过动态规划，可以计算出每个位置的最优切分方案及其得分。而在Viterbi Sampling中，我们需要对所有切分方案进行采样，其采样概率应与得分成正比。
通过逐步计算累积权重Z. 可以实现对所有切分方案的完美采样。✅
递归式转换
在实际计算中，使用对数形式的累积权重Zlog，并通过logsumexp函数进行累积计算。
这样可以避免直接计算指数导致的溢出问题。
文章小结
本文通过详细分析和数学推导，完善了之前提出的Viterbi Sampling算法。改进后的算法不仅解决了概率“稀释”问题，而且在效果上与Subword Regularization等价，同时在使用效率上更具优势。
通过这些改进，Viterbi Sampling算法在实际应用中将具备更高的可靠性和效率，为自然语言处理领域的分词任务提供了更优的解决方案。