分类： AI

在自然语言处理领域，分词是一个至关重要的步骤。最近，一篇名为《随机分词浅探：从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算法在实际应用中将具备更高的可靠性和效率，为自然语言处理领域的分词任务提供了更优的解决方案。

近年来，Transformer架构在自然语言处理领域取得了显著的成果，而Attention机制则是其核心所在。然而，随着研究的深入，传统的标准Attention机制暴露出了一些计算复杂度和资源需求上的问题，这促使研究者们开始探索更高效的线性Attention。然而，线性Attention在实际效果上却一直不如标准Attention。本文将从“集中注意力”的角度，探讨线性Attention的局限性，并尝试给出一个合理的解释。

Attention机制的稀疏性

什么是稀疏性？

在《从熵不变性看Attention的Scale操作》一文中，我们用信息熵来度量Attention的“集中注意力”程度。熵越低，Attention越有可能集中在某个token上。然而，信息熵只能用于归一化且非负的Attention矩阵，这限制了其适用范围。因此，我们引入了另一种稀疏性度量指标：S(x) = E[|x|] / sqrt(E[x^2])。这个指标与信息熵类似，S(x)越小，表示对应的随机矢量越稀疏，即越有可能“一家独大”。

标准Attention的稀疏性

对于标准Attention机制，f = exp，我们可以推导出其稀疏性：

S(a) = exp(-1/2 * σ^2 * ||q||^2)

当σ或||q||趋向无穷大时，S(a)趋向于0，这意味着标准Attention可以任意稀疏地“集中注意力”。

GAU的稀疏性

对于Gated Attention Unit (GAU)机制，f = relu2，其稀疏性较为复杂，但通过计算可以发现，只有当偏置项β小于0时，稀疏性才有机会趋于0。这表明，GAU在某些条件下也能实现较高的稀疏性。

线性Attention的局限性

极简线性Attention

对于最简单的线性Attention，即不加任何激活函数f = identical，其稀疏性为：

S(a) = sqrt(2/π * γ * exp(-β^2/(2γ^2)) + β * erf(β/(2√γ)) / (β^2 + γ^2))

从图像可以看出，极简线性Attention的稀疏性存在一个较高的下限，这意味着它难以“集中注意力”到关键位置上。

一般线性Attention

线性Attention的一般形式为a_j ∝ g(q) ⋅ h(k_j)，其稀疏性为：

S(a) = 1 / sqrt(1 + (σ~ * μ~ * ||q~||_2 / ||q~||_1)^2)

这表明，要想线性Attention变得稀疏，可以通过降低k~串行的信噪比或增大q的模长。然而，非负型线性Attention通常只能表示绝对位置的重要性，难以表达相对位置的重要性。

线性衰减Attention

对于带有显式递归的线性RNN模型，其稀疏性为：

S(a) = 1 - λ^n / n(1 - λ) * sqrt(1 + λ / (1 + λ^n))

当λ < 1时，随着n趋向无穷大，S(a)趋向0。这意味着这种模型可以实现较高的稀疏性，但其注意力仅能表达固定不变的注意力衰减，难以自适应地关注到长距离的上下文。

结论

本文通过Attention矩阵的稀疏程度，考察了不同Attention机制的潜力，得出以下结论：

1. 标准Attention可以实现任意稀疏的注意力矩阵。
2. 线性Attention难以实现高稀疏性，尤其是在表示相对位置的重要性时。
3. 带有显式衰减的线性Attention可以实现稀疏性，但其注意力固定，难以自适应。

这些发现或许能够解释线性Attention在实际效果上略逊一筹的原因。线性Attention在“集中注意力”方面存在固有的局限性，这使得它在处理复杂上下文时表现不如标准Attention。未来的研究或许需要在如何提高线性Attention的稀疏性和灵活性上继续努力，以期实现更高效且性能优越的Transformer模型。

参考文献

1. 《Transformer升级之路：3、从Performer到线性Attention》
2. 《为什么现在的LLM都是Decoder-only的架构？》
3. 《从熵不变性看Attention的Scale操作》
4. 《FLASH：可能是近来最有意思的高效Transformer设计》
5. 《相对位置编码Transformer的一个理论缺陷与对策》
6. 《如何度量数据的稀疏程度？》
7. 《线性Attention的探索：Attention必须有个Softmax吗？》
8. 《Google新作试图“复活”RNN：RNN能否再次辉煌？》

通过上述分析，我们不仅理解了不同Attention机制的稀疏性差异，还揭示了线性Attention在实际应用中的局限性。希望本文的讨论能够为未来的研究提供一些新的思路和方向。