如何应对Seq2Seq中的根本停不下来问题？
原文链接 | 2020-06-16 | 苏剑林
在Seq2Seq的解码过程中，我们是逐个token地递归生成的，直到出现****标记为止，这就是所谓的“自回归”生成模型。然而，研究过Seq2Seq的读者应该都能发现，这种自回归的解码偶尔会出现“根本停不下来”的现象，主要是某个片段反复出现，比如“今天天气不错不错不错不错不错…”、“你觉得我说得对不对不对不对不对不对…”等等，但就是死活不出现****标记。ICML 2020的文章《Consistency of a Recurrent Language Model With Respect to Incomplete Decoding》比较系统地讨论了这个现象，并提出了一些对策，本文来简单介绍一下论文的主要内容。
解码算法#
对于自回归模型来说，我们建立的是如下的条件语言模型
\[\begin{equation}p(y_t|y_{\lt t}, x)\label{eq:p}\end{equation}\]
那么解码算法就是在已知上述模型时，给定\(x\)来输出对应的\(y=(y_1,y_2,\dots,y_T)\)来。解码算法大致可以分为两类：确定性解码算法和随机性解码算法，原论文分别针对这两类解码讨论来讨论了“根本停不下来”问题，所以我们需要来了解一下这两类解码算法。
确定解码#
确定性解码算法就是当输入文本固定之后，解码出来的输出文本也是固定的，这类算法包含贪心搜索（Greedy Search）和束搜索（Beam Search），事实上贪心搜索是束搜索的一个特例，所以只需要讨论束搜索。
束搜索我们需要固定一个“束”的大小（Beam Size）\(k\)，然后从左往右逐个token地解码，每步只保留总得分最高的\(k\)个序列。比如\(k=2\)，token空间为\(V=\{a,b,c,d\}\)，那么解码流程示例如下：
第一步，算\(p(y_1|y_0,x)\)（\(y_0\)是固定的起始标记
），然后保留最大的两个，比如\(\{a,b\}\)，并记录它们的得分（概率对数）；第二步，算\(p(y_2|y_0,a,x)\)和\(p(y_2|y_0,b,x)\)，这时候候选序列一共有\(k\times |V|=8\)个，保留总得分（也就是当前token分数加上\(a\),\(b\)本身的分数）最大的两个，比如\(\{(a,c),(b,d)\}\)，并记录各自的总得分；第三步，算\(p(y_3|y_0,a,c,x)\)和\(p(y_3|y_0,b,d,x)\)，这时候候选序列一共有\(k\times |V|=8\)个，保留总得分（也就是当前token分数加上\((a,c)\),\((b,d)\)本身的分数）最大的两个，比如\(\{(a,c,d),(a,c,c)\}\)，并记录各自的总得分；…依此类推，每个序列直到出现****就停止，最后从这\(k\)个已经完成终止的序列中选最优的那个输出。一般有两种选择，一是输出总得分最大的，二是输出平均得分最大的（处以各自token数），有时候还会根据实际需求加入长度惩罚等。
随机解码#
随机性解码算法，顾名思义，就是哪怕输入文本固定了，解码出来的输出文本也不是固定的，比如从训练语言模型进行随机采样就是这这种算法（参考《现在可以用Keras玩中文GPT2了》）。对于Seq2Seq来说，我们很多时候希望得到确定性的结果，所以多数场景下我们都是用Beam Search。但是Beam Searc的生成结果可能会出现过于单一的现象（即类似“好的”、“不知道”、“谢谢”这类比较“安全”的回复），或者有时候我们希望增加输出的多样性（比如我们之前开源的做相似句生成的SimBERT模型），这时候就需要随机性解码算法，它包含三种情况：原生随机解码、top-k随机解码、Nucleus随机解码。
原生随机解码很简单，就是每步按概率随机采样一个token，比如第一步算\(p(y_1|y_0,x)\)，然后按概率随机采样一个token，比如\(c\)；然后第二步算\(p(y_2|y_0,c,x)\)，接着按概率随机采样一个token，比如\(a\)；那么第三步就算\(p(y_3|y_0,c,a,x)\)，再按概率随机采样；…；依此类推，直到采样到****停止。
top-k随机解码出自文章《Hierarchical Neural Story Generation》，其实就是在原生随机解码基础上加了个截断：每一步只保留概率最高的\(k\)个token，然后重新归一化后再采样，这样做是希望在“得分高”和“多样性”方面做一个折中。显然，当\(k=1\)时，其实就等价于贪心搜索。
Nucleus随机解码则来自文章《The Curious Case of Neural Text Degeneration》，跟top-k随机解码类似，也是对采样空间做了个截断，截断方式是：固定\(p\in(0, 1)\)，然后只保留概率最高的、概率和刚好超过\(p\)的若干个token，所以它也叫top-p采样。
除了top-k和top-p这两种截断方式外，还有一些自适应的截断方式，比如论文《Sparse Sequence-to-Sequence Models》将最后预测分布的softmax函数换成了稀疏版本的softmax，它能自动让大部分不可能的token概率变为0，而不需要认为地选择\(k\)或\(p\)。
适可而止#
从Seq2Seq的模型设计和上面介绍的解码算法来看，并没有任何的理论保证解码过程一定能停下来，也就是说并没有东西保证一定会出现****标记，这只能靠模型自己学出来，而当模型学得不够好时，就会出现“根本停不下来”的现象了。而原论文则针对不同的解码算法做了相应的分析，提出了对应的策略，让解码过程能够“适可而止”。
有界的隐向量#
建模概率\(\eqref{eq:p}\)的经典方式就是
\[\begin{equation}p(y_t|y_{\lt t}, x)=softmax(Wh_t+b),\quad h_t=f(y_{\lt t}, x)\end{equation}\]
也就是说，先算一个隐向量\(h_t\)，然后接一个全连接，然后softmax激活。在这种形式下，原论文说
如果对于任意的\(t\)，\(\Vert h_t\Vert\)是有上界的，那么原生随机解码就能够“适可而止”。
看上去很强很实用的一个结论是不是？让\(\Vert h_t\Vert\)是有上界是一个很简单的事情，比如加个Layer Norm就可以了，那是不是说加个Layer Norm就可以解决所有的问题呢？并不是。上述结论理论上是对的，推理过程是：因为\(\Vert h_t\Vert\)是有上界的，所以对于任意的\(t\)、任意的token，\(p(y_t|y_{\lt t}, x)\)是有正的下界的（因为\(Wh_t\)不会无穷大，所以\(e^{Wh_t}\)也不会无穷大，归一化后也不会无限接近于0），那也就意味着存在一个正数\(\epsilon > 0\)，总有\(p(\text{}|y_{\lt t}, x)\geq \epsilon\)，因为概率是一个正数，因此只要你采样足够多步，总有机会采样到****的，所以不会永远停不下来。
这推理过程是不是有点让人啼笑皆非？没错，是能停，但是要采样足够多步，感觉就像是“只要你买足够多张彩票就一定能中头奖”一样，并没什么确切的实际价值。采样足够多步之后，该循环的、该重复的token可能都已经重复多次了，就算能停下来，得到的输出可能也没有意义了，或许还不如直接按长度截断。
主动添加#
注意上述结论还只是对原生随机解码成立，对于top-k随机解码和Nucleus随机解码不一定成立，因为经过截断后****就不一定出现在采样空间中了，当然，我们可以手动把****添加进采样空间，所以就有了如下的结论：
如果对于任意的\(t\)，\(\Vert h_t\Vert\)是有上界的，并且我们把****也加入到采样空间中，那么top-k随机解码和Nucleus随机解码就能够“适可而止”。
只不过，这有点像是废话…
自截断设计#
注意，上面的两个结论都只能用于随机解码，对于确定性解码来说，因为没有了随机性，所以我们没法保证一定能碰到****。为此，原论文提出了一个自截断的设计：想办法让\(p(\text{}|y_{\lt t}, x)\)有正的下界，而且这个下界随着\(t\)的增大而增大，最终逐渐趋于1。
这种自截断的设计也不复杂，就是定义\(p(\text{}|y_{\lt t}, x) = 1 - \alpha(h_t)\)，其中
\[\begin{equation}\begin{aligned} \alpha(h_0)=&\,\sigma\left(w_{\text{}}^{\top} h_0 + b_{\text{}}\right) \\ \alpha(h_t)=&\,\sigma\left(w_{\text{}}^{\top} h_t + b_{\text{}}\right)\left[1 - p(\text{}|y_{\lt {t-1}}, x)\right] \end{aligned}\end{equation}\]
这里的\(\sigma(\cdot)\)负责将\(\mathbb{R}\)映射到\([0, 1-\epsilon]\)，比如可以用\(\sigma(\cdot)=(1-\epsilon)\text{sigmoid}(\cdot)\)。设计好\(p(\text{}|y_{\lt t}, x)\)后，剩下的token概率还是按照原来的softmax方式计算，然后乘以\(\alpha(h_t)\)即可。
现在我们有
\[\begin{equation}\begin{aligned} p(\text{}|y_{\lt t}, x)=&\,1 - \sigma\left(w_{\text{}}^{\top} h_t + b_{\text{}}\right)\left[1 - p(\text{}|y_{\lt {t-1}}, x)\right]\\ =&\,1 - \prod_{i=0}^t\sigma\left(w_{\text{}}^{\top} h_i + b_{\text{}}\right)\\ \geq&\, 1 - (1 - \epsilon)^{t+1} \end{aligned}\end{equation}\]
显然只要\(t > -\ln 2/\ln (1-\epsilon)\)，\(p(\text{}|y_{\lt t}, x) > 0.5\)，也就是说，对于贪心搜索来说必然在\(-\ln 2/\ln (1-\epsilon)\)步内停止，而对随着\(p(\text{}|y_{\lt t}, x)\)越来越接近1，显然Beam Search也能在有限步停止。
个人评价#
原论文的主要内容大体上就是这样了，总的来说，它确实给我们提供了对解码算法的一些新认识，以及提供了一些缓解“根本停不下来”问题的有效策略。但是，作为一篇ICML论文来说，我觉得原论文的视角并不高，总体显得有些显浅。
原论文的大部分篇幅，是在用数学化的语言来重新表述已有的内容，比如什么是解码算法、什么是top-k随机解码、什么是Beam Search、什么是“根本停不下来”等等，原论文都给下了个数学定义，这不能说没有意义，但对论文本身要探讨的问题并没有什么价值，而除去这部分东西，原论文就没多少内容了。其次，原论文的结论太弱，关于随机解码的应对策略前面已经点评过了，结论是对的，但基本没实用价值；而对于确定性解码的自截断设计，其实很生硬，有种粗暴截断的感觉，完全没有优雅感。
最关键的问题是，对于“根本停不下来”这个问题，论文通篇都是在回答“是什么”、“怎么办”这两个问题，没有探讨“为什么”，没有提供任何关于理解“根本停不下来”本质的有用信息，从而并没有得到更贴近本质的应对策略，这是笔者觉得相当难以接受的。
文章小结#
本文介绍了Seq2Seq的解码算法，讨论了解码过程中可能出现的“根本停不下来”的现象，并介绍了ICML 2020的一篇论文中提供的应对策略。