Seq2Seq重复解码问题追根溯源

[155****7220]

本篇文章的顺序会有些奇怪，一般来说应该先分析为什么会出现解码中停不下来或者是重复解码的问题，然后提出解决这个问题的办法，但由于分析为什么这个过程涉及到的数学公式繁多，过程也很复杂，考虑到不是那么多同学对这个部分感兴趣，可能大部分同学只是重点关注如何解决问题，所以本文的顺序是先提出如何解决问题，然后再阐述为什么

注：本文提到的"根本停不下来"和"重复解码"问题实际上本质是一样的

如何应对Seq2Seq中"根本停不下来"的问题？

在Seq2Seq的解码过程中，token是逐个递归生成的，直到出现<eos>标记为止，这就是所谓的"自回归"生成模型。然而，研究过Seq2Seq的读者应该都能发现，这种自回归的解码偶尔会出现"根本停不下来"的现象，主要是某个片段反复出现，例如"今天天气不错不错不错不错…"、"你觉得我说的对不对对不对对不对…"等等，但就是死活不出现<eos>标记。ICML2020的文章《Consistency of a Recurrent Language Model With Respect to Incomplete Decoding》比较系统地讨论了这个现象，并提出了一些对策，本文来简单介绍一下论文的主要内容

解码算法

对于自回归模型来说，我们建立的是如下的条件语言模型
$$
p(y_t\mid y_{<t}, x) \tag{1}
$$
那么解码算法就是在已知上述模型时，给定$x$来输出对应的$y=(y_1,y_2,\dots ,y_T)$。解码算法大致可以分为两类：确定性解码算法和随机性解码算法，原论文分别针对这两类解码讨论了"根本停不下来"问题，所以我们首先需要来了解一下这两类解码算法

确定解码

确定性解码算法就是当输入文本固定后，解码出来的输出文本也是固定的，这类算法包含贪心搜索（Greedy Search）和束搜索（Beam Search），事实上贪心搜索是束搜索的一个特例，所以只需要讨论束搜索

对于束搜索来说，我们首先要确定一个超参数$k$表示"束"的大小，然后从左往右逐个token地解码，每步只保留总得分最高的$k$个序列。例如$k=2$，token空间为$V=a,b,c,d$，那么解码流程示例如下：

第一步，算$p(y_1\mid y_0,x)$（$y_0$是固定的起始标记<bos>），然后保留最大的$k=2$个，例如$a,b$，并记录它们的得分（概率对数）

第二步，算$p(y_2\mid y_0,a,x)$和$p(y_2\mid y_0,b,x)$，这时候候选序列一共有$k\times |V|=8$个，保留总得分（也就是当前token分数加上$a,b$本身的分数）最大的两个，比如$(a,c),(b,d)$，并记录各自的总得分

…

依此类推，每个序列直到出现<eos>就停止，最后从这个$k$个已经解码完成的序列中选最优的那个输出。一般有两种选择，一是输出总得分最大的，而是输出平均得分最大的（除以各自token数），有时候还会根据实际需求加入长度惩罚等

随机解码

随机性解码算法，顾名思义，就是哪怕输入文本固定了，解码出来的输出文本也不是固定的。实际上根据业务场景的不同，确定性和随机性解码都有其应用，但是在学术界，我们很多时候希望得到确定性的结果，所以多数场景下我们都是用Beam Search。但是Beam Search的生成结果可能会出现过于单一的现象（即类似"好的"、“不知道”、"谢谢"这类比较"保守"的回复），或者有时候我们希望增加输出的多样性，这时候就需要随机性解码算法，它包含三种情况：原生随机解码、top-k随机解码、Nucleus随机解码

原生随机解码很简单，就是每步按概率随机采样一个token，比如第一步算$p(y_1\mid y_0,x)$，然后按概率随机采样一个token，假设是$c$；然后第二步算$p(y_2\mid y_0,c,x)$，接着按概率随机采样一个token，假设是$a$；那么第三步就算$p(y_3\mid y_0,c,a,x)$，再按概率采样；依此类推，直到采样到<eos>为止。这个方法真是跟它的名字一样不靠谱

top-k随机解码出自文章《Hierarchical Neural Story Generation》，其实就是在原生随机解码基础上加了个截断：每一步只保留概率最高的$k$个token，重新归一化后再采样，这样做是希望在"得分高"和"多样性"两个方面做一个折中。显然，当$k=1$时，其实就等价于贪心搜索。top-k解码公式如下：
$$
p’(y_t\mid y_{<t}) = \begin{cases}p(y_t\mid y_{<t})/p’,\quad \text{if}\ y_t\in V^{(k)}\0,\quad \text{otherwise}\end{cases}
$$
其中
$$
\begin{aligned}
p’ &= \sum\limits_{y_t\in V^{(k)}} p(y_t\mid y_{<t})\
\max\limits_{V^{k}\subset V}p’&=\sum\limits_{y_t\in V^{(k)}}p(y_t\mid y_{<t})
\end{aligned}
$$

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的模型设计和上面介绍的解码算法来看，并没有任何的理论保证解码过程一定能停下来，也就是说并不能保证一定会出现<eos>标记，这只能靠模型自己学出来，而当模型学得不够好时，就会出现"根本停不下来"的现象了。而原论文则针对不同的解码算法做了相应的分析，提出了对应的策略，让解码过程能够"适可而止"

有界的隐向量

建模概率(1)的经典方式就是
$$
\begin{aligned}p(y_t|y_{\lt t}, x)&=softmax(Wh_t+b)\h_t&=f(y_{\lt t}, x)\end{aligned}\tag{2}
$$
也就是说，先算一个隐向量$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\mid y_{<t}, x)$是有正的下界的（因为$W{h}_t$不会无穷大，所以$e^{W{h}_t}$也不会无穷大，归一化后也不会无限接近于0），那也就意味着存在一个正数$\epsilon>0$，总有$p(\text{<eos>}|y_{\lt t}, x)\geq \epsilon$，因为概率是一个正数，因此只要你采样足够多步，总有机会采样到<eos>的，所以永远不会停不下来

这推理过程有点离谱，没错，是能停，但是要采样足够多步，感觉就像是"只要你买足够多张彩票就一定能中头奖"一样，没什么确切的实际价值。采样足够多步之后，该循环的、该重复的token可能都已经重复多次了，就算能停下来，得到的输出可能也没有意义了，或许还不如直接按长度截断

实际上我觉得也不能怪这篇论文的作者，实际上本身原生随机解码就有点离谱，在这么随机的方法上硬生生想一个解决办法也是不太靠谱的

主动添加<eos>

注意上述结论还只是对原生随机解码成立，对于top-k随机解码和Nucleus随机解码不一定成立，因为经过截断后<eos>就不一定出现在采样空间中了，当然，我们可以手动把<eos>添加进采样空间，所以就有了如下结论：

如果对于任意的$t$，$\Vert h_t|$是有上界的，并且我们把<eos>强行添加到采样空间中，那么top-k随机解码和Nucleus随机解码就能够"适可而止"

这种方法，实际上就是人为提高了<eos>的采样概率，但实际上提升应该不会太大，因为即便<eos>被添加进了采样空间，但如果它的采样概率不够大的话，肯定还是取不到它，那就一点儿用都没有了

自截断设计

注意，上面两个结论都只能用于随机解码，对于确定性解码来说，因为没有了随机性，所以我们没法保证一定能碰到<eos>。为此，原论文提出了一个自截断的设计：想办法让$p(\text{<eos>}\mid y_{<t}, x)$有正的下界，而且这个下界随着$t$的增大而增大，最终逐渐趋于1

这种自截断的设计也不复杂，就是定义$p(\text{<eos>}\mid y_{<t}, x)=1-\alpha(h_t)$，其中
$$
\begin{equation}\begin{aligned}
\alpha(h_0)=&,\gamma\left(w_{\text{<eos>}}^{\top} h_0 + b_{\text{<eos>}}\right)
\
\alpha(h_t)=&,\gamma\left(w_{\text{<eos>}}^{\top} h_t + b_{\text{<eos>}}\right)\left[1 - p(\text{<eos>}|y_{\lt {t-1}}, x)\right] \
=&,\gamma\left(w_{\text{<eos>}}^{\top} h_t + b_{\text{<eos>}}\right)\alpha(h_{t-1})\
=&, \gamma\left(w_{\text{<eos>}}^{\top} h_t + b_{\text{<eos>}}\right)\gamma\left(w_{\text{<eos>}}^{\top} h_{t-1} + b_{\text{<eos>}}\right)\alpha(h_{t-2})\
…&\
=& , \prod_{i=0}^{t}\gamma\left(w_{\text{<eos>}}^{\top} h_i + b_{\text{<eos>}}\right)
\end{aligned}\tag{3}\end{equation}
$$
这里的$\gamma (\cdot )$负责将$\mathbb{R}$映射到$[0,1-ϵ]$，例如可以用$\gamma (\cdot )=(1-ϵ)\sigma (\cdot )$。设计好$p(\text{<eos>}\mid y_{<t},x)$后，剩下的token概率还是按照原来的softmax方式计算，然后乘以$\alpha (h_t)$即可

现在我们有
$$
\begin{equation}\begin{aligned}
p(\text{<eos>}|y_{\lt t}, x)=&,1 - \gamma\left(w_{\text{<eos>}}^{\top} h_t + b_{\text{<eos>}}\right)\left[1 - p(\text{<eos>}|y_{\lt {t-1}}, x)\right]\
=&,1 - \prod_{i=0}^t\gamma\left(w_{\text{<eos>}}^{\top} h_i + b_{\text{<eos>}}\right)\
\geq&, 1 - (1 - \epsilon)^{t+1} \

&, 1 - (1 - \epsilon)^{t}
\end{aligned}\tag{4}\end{equation}
$$
显然只要$t>-\frac{\ln2}{\ln(1-\epsilon)},p(\text{<eos>}\mid y_{<t},x)>0.5$，而随着$p(\text{<eos>}\mid y_{<t},x)$越来越接近1，显然Beam Search也能在有限步内停止

$$
\begin{aligned}
&\because\ p(\text{<eos>}\mid y_{<t},x)>1-(1-\epsilon)^{t}=0.5\
&\therefore\ (1-\epsilon)^{t}= \frac{1}{2}
\end{aligned}
$$
两边同取以$(1-ϵ)$为底的对数，则有
$$
t = -\log_{1-\epsilon} 2
$$
由换底公式${\log }_{a}b=\frac{{\log }_{c}b}{{\log }_{c}a}$得
$$
t = -\frac{\ln2}{\ln(1-\epsilon)}
$$
由于$0<1-\epsilon<1$，所以很明显当$t>-\frac{\ln2}{\ln(1-\epsilon)}$时，$p(\text{<eos>}\mid y_{<t},x)>0.5$，并且随着$t$的增大，$p(\text{<eos>}\mid y_{<t},x)$也逐渐增大