Seq2Seq重复解码问题追根溯源

ゞ浴缸里的玫瑰 2022-09-02 04:15 174阅读 0赞

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

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

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

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

#### 解码算法 ####

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

#### 确定解码 ####

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

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

> 第一步，算 p ( y 1 ∣ y 0 , x ) p(y\_1\\mid y\_0, x) p(y1∣y0,x)（ y 0 y\_0 y0是固定的起始标记<bos>），然后保留最大的 k = 2 k=2 k=2个，例如 \{ a , b \} \\\{a,b\\\} \{ a,b\}，并记录它们的得分（概率对数）
> 
> 第二步，算 p ( y 2 ∣ y 0 , a , x ) p(y\_2\\mid y\_0,a,x) p(y2∣y0,a,x)和 p ( y 2 ∣ y 0 , b , x ) p(y\_2\\mid y\_0,b,x) p(y2∣y0,b,x)，这时候候选序列一共有 k × ∣ V ∣ = 8 k\\times |V|=8 k×∣V∣=8个，保留总得分（也就是当前token分数加上 a , b a,b a,b本身的分数）最大的两个，比如 \{ ( a , c ) , ( b , d ) \} \\\{(a,c),(b,d)\\\} \{ (a,c),(b,d)\}，并记录各自的总得分
> 
> …
> 
> 依此类推，每个序列直到出现<eos>就停止，最后从这个 k k k个已经解码完成的序列中选最优的那个输出。一般有两种选择，一是输出总得分最大的，而是输出平均得分最大的（除以各自token数），有时候还会根据实际需求加入长度惩罚等

#### 随机解码 ####

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

**原生随机解码**很简单，就是每步按概率随机采样一个token，比如第一步算 p ( y 1 ∣ y 0 , x ) p(y\_1\\mid y\_0, x) p(y1∣y0,x)，然后按概率随机采样一个token，假设是 c c c；然后第二步算 p ( y 2 ∣ y 0 , c , x ) p(y\_2\\mid y\_0,c,x) p(y2∣y0,c,x)，接着按概率随机采样一个token，假设是 a a a；那么第三步就算 p ( y 3 ∣ y 0 , c , a , x ) p(y\_3\\mid y\_0, c, a, x) p(y3∣y0,c,a,x)，再按概率采样；依此类推，直到采样到<eos>为止。这个方法真是跟它的名字一样不靠谱

**top-k随机解码**出自文章[《Hierarchical Neural Story Generation》][Hierarchical Neural Story Generation]，其实就是在原生随机解码基础上加了个截断：每一步只保留概率最高的 k k k个token，重新归一化后再采样，这样做是希望在"得分高"和"多样性"两个方面做一个折中。显然，当 k = 1 k=1 k=1时，其实就等价于贪心搜索。top-k解码公式如下：  
 p ′ ( y t ∣ y < t ) = \{ p ( y t ∣ y < t ) / p ′ , if y t ∈ V ( k ) 0 , otherwise 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\} p′(yt∣y<t)=\{ p(yt∣y<t)/p′,ifyt∈V(k)0,otherwise  
其中  
 p ′ = ∑ y t ∈ V ( k ) p ( y t ∣ y < t ) max ⁡ V k ⊂ V p ′ = ∑ y t ∈ V ( k ) p ( y t ∣ y < t ) \\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\} p′Vk⊂Vmaxp′=yt∈V(k)∑p(yt∣y<t)=yt∈V(k)∑p(yt∣y<t)

**Nucleus随机解码**则来自文章[《The Curious Case of Neural Text Degeneration》][The Curious Case of Neural Text Degeneration]，跟top-k随机解码类似，也是对采样空间做了个截断，截断方式是：固定 p ∈ ( 0 , 1 ) p\\in (0,1) p∈(0,1)，然后只保留概率最高的、概率和刚好超过 p p p的若干个token，所以它也叫top-p采样

除了top-k和top-p这两种截断方式外，还有一些自适应的截断方式，比如论文[《Sparse Sequence-to-Sequence Models》][Sparse Sequence-to-Sequence Models]将最后预测分布的softmax函数换成了稀疏版本的softmax，它能自动让大部分不可能的token概率变为0，从而不需要人为的选择 k k k或 p p p

### 适可而止 ###

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

#### 有界的隐向量 ####

建模概率(1)的经典方式就是  
 p ( y t ∣ y < t , x ) = s o f t m a x ( W h t + b ) h t = f ( y < t , x ) (2) \\begin\{aligned\}p(y\_t|y\_\{\\lt t\}, x)&=softmax(Wh\_t+b)\\\\h\_t&=f(y\_\{\\lt t\}, x)\\end\{aligned\}\\tag\{2\} p(yt∣y<t,x)ht=softmax(Wht\+b)=f(y<t,x)(2)  
也就是说，先算一个隐向量 h t h\_t ht，然后接一个全连接，最后跟一个softmax激活。在这种形式下，原论文说

> 如果对于任意的 t t t， ∥ h t ∥ \\Vert h\_t\\Vert ∥ht∥是有上界的，那么原生随机解码就能够"适可而止"

看上去好像是一个很厉害的结论，让 ∥ h t ∥ \\Vert h\_t\\Vert ∥ht∥有上界是一个很简单的事情，比如加个Layer Norm就可以了，那是不是说加个Layer Norm就可以解决所有的问题呢？并不是。上述结论理论上是对的，推理过程是：因为 ∥ h t ∥ \\Vert h\_t\\Vert ∥ht∥是有上界的，所以对于任意的 t t t、任意的token， p ( y t ∣ y < t , x ) p(y\_t\\mid y\_\{<t\}, x) p(yt∣y<t,x)是有正的下界的（因为 W h t Wh\_t Wht不会无穷大，所以 e W h t e^\{Wh\_t\} eWht也不会无穷大，归一化后也不会无限接近于0），那也就意味着存在一个正数 ϵ > 0 \\epsilon>0 ϵ>0，总有 p ( <eos> ∣ y < t , x ) ≥ ϵ p(\\text\{<eos>\}|y\_\{\\lt t\}, x)\\geq \\epsilon p(<eos>∣y<t,x)≥ϵ，因为概率是一个正数，因此只要你采样足够多步，总有机会采样到<eos>的，所以永远不会停不下来

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

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

#### 主动添加<eos> ####

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

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

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

#### 自截断设计 ####

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

这种自截断的设计也不复杂，就是定义 p ( <eos> ∣ y < t , x ) = 1 − α ( h t ) p(\\text\{<eos>\}\\mid y\_\{<t\}, x)=1-\\alpha(h\_t) p(<eos>∣y<t,x)=1−α(ht)，其中

α ( h 0 ) =   γ ( w <eos> ⊤ h 0 + b <eos> ) α ( h t ) =   γ ( w <eos> ⊤ h t + b <eos> ) \[ 1 − p ( <eos> ∣ y < t − 1 , x ) \] =   γ ( w <eos> ⊤ h t + b <eos> ) α ( h t − 1 ) =   γ ( w <eos> ⊤ h t + b <eos> ) γ ( w <eos> ⊤ h t − 1 + b <eos> ) α ( h t − 2 ) . . . =   ∏ i = 0 t γ ( w <eos> ⊤ h i + b <eos> ) (3) \\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\} α(h0)=α(ht)===...=γ(w<eos>⊤h0\+b<eos>)γ(w<eos>⊤ht\+b<eos>)\[1−p(<eos>∣y<t−1,x)\]γ(w<eos>⊤ht\+b<eos>)α(ht−1)γ(w<eos>⊤ht\+b<eos>)γ(w<eos>⊤ht−1\+b<eos>)α(ht−2)i=0∏tγ(w<eos>⊤hi\+b<eos>)(3)

这里的 γ ( ⋅ ) \\gamma(\\cdot) γ(⋅)负责将 R \\mathbb\{R\} R映射到 \[ 0 , 1 − ϵ \] \[0, 1-\\epsilon\] \[0,1−ϵ\]，例如可以用 γ ( ⋅ ) = ( 1 − ϵ ) σ ( ⋅ ) \\gamma(\\cdot)=(1-\\epsilon)\\sigma(\\cdot) γ(⋅)=(1−ϵ)σ(⋅)。设计好 p ( <eos> ∣ y < t , x ) p(\\text\{<eos>\}\\mid y\_\{<t\},x) p(<eos>∣y<t,x)后，剩下的token概率还是按照原来的softmax方式计算，然后乘以 α ( h t ) \\alpha(h\_t) α(ht)即可

现在我们有

p ( <eos> ∣ y < t , x ) =   1 − γ ( w <eos> ⊤ h t + b <eos> ) \[ 1 − p ( <eos> ∣ y < t − 1 , x ) \] =   1 − ∏ i = 0 t γ ( w <eos> ⊤ h i + b <eos> ) ≥   1 − ( 1 − ϵ ) t + 1   >   1 − ( 1 − ϵ ) t (4) \\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\} p(<eos>∣y<t,x)==≥>1−γ(w<eos>⊤ht\+b<eos>)\[1−p(<eos>∣y<t−1,x)\]1−i=0∏tγ(w<eos>⊤hi\+b<eos>)1−(1−ϵ)t\+11−(1−ϵ)t(4)

显然只要 t > − ln ⁡ 2 ln ⁡ ( 1 − ϵ ) , p ( <eos> ∣ y < t , x ) > 0.5 t>-\\frac\{\\ln2\}\{\\ln(1-\\epsilon)\},p(\\text\{<eos>\}\\mid y\_\{<t\},x)>0.5 t>−ln(1−ϵ)ln2,p(<eos>∣y<t,x)>0.5，而随着 p ( <eos> ∣ y < t , x ) p(\\text\{<eos>\}\\mid y\_\{<t\},x) p(<eos>∣y<t,x)越来越接近1，显然Beam Search也能在有限步内停止

>  ∵ p ( <eos> ∣ y < t , x ) > 1 − ( 1 − ϵ ) t = 0.5 ∴ ( 1 − ϵ ) t = 1 2 \\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\} ∵p(<eos>∣y<t,x)>1−(1−ϵ)t=0.5∴(1−ϵ)t=21  
> 两边同取以 ( 1 − ϵ ) (1-\\epsilon) (1−ϵ)为底的对数，则有  
>  t = − log ⁡ 1 − ϵ 2 t = -\\log\_\{1-\\epsilon\} 2 t=−log1−ϵ2  
> 由换底公式 log ⁡ a b = log ⁡ c b log ⁡ c a \\log\_a b = \\frac\{\\log\_c b\}\{\\log\_c a\} logab=logcalogcb得  
>  t = − ln ⁡ 2 ln ⁡ ( 1 − ϵ ) t = -\\frac\{\\ln2\}\{\\ln(1-\\epsilon)\} t=−ln(1−ϵ)ln2  
> 由于 0 < 1 − ϵ < 1 0<1-\\epsilon<1 0<1−ϵ<1，所以很明显当 t > − ln ⁡ 2 ln ⁡ ( 1 − ϵ ) t>-\\frac\{\\ln2\}\{\\ln(1-\\epsilon)\} t>−ln(1−ϵ)ln2时， p ( <eos> ∣ y < t , x ) > 0.5 p(\\text\{<eos>\}\\mid y\_\{<t\},x)>0.5 p(<eos>∣y<t,x)>0.5，并且随着 t t t的增大， p ( <eos> ∣ y < t , x ) p(\\text\{<eos>\}\\mid y\_\{<t\},x) p(<eos>∣y<t,x)也逐渐增大

### Seq2Seq重复解码问题现象的理论分析尝试 ###

上述论文仅仅只是阐述了应对Seq2Seq停不下来问题的策略，并没有从提供原理上的理解。近日，AAAI 2021上有一篇名为[《A Theoretical Analysis of the Repetition Problem in Text Generation》][A Theoretical Analysis of the Repetition Problem in Text Generation]的论文，里边从理论上分析了Seq2Seq重复解码现象。从本质上来看，重复解码和解码不停止是同理的，所以这篇新论文算是填补了前面那篇论文的空白

#### 基本思路 ####

所谓重复解码，指的是解码结果出现重复片段，比如解码结果为"A B C D B C D B C D E F"，那么"B C D"就是重复片段了，因此这个解码结果就出现了重复解码现象。简单起见，如果解码过程中子序列 s = \[ w 1 , w 2 , ⋯   , w n \] s=\[w\_1,w\_2,\\cdots,w\_n\] s=\[w1,w2,⋯,wn\]后面接着的子序列是 t = \[ w 1 , w 2 , ⋯   , w n , w 1 \] t=\[w\_1,w\_2,\\cdots ,w\_n, w\_1\] t=\[w1,w2,⋯,wn,w1\]，我们就称 \[ w 1 , w 2 , ⋯   , w n \] \[w\_1, w\_2, \\cdots ,w\_n\] \[w1,w2,⋯,wn\]为一个\*\*“重复子序列”\*\*，而我们现在要做的事情，就是要分析解码过程中出现重复子序列的概率

可能有读者疑问，为什么 t t t的最后要多加一个 w 1 w\_1 w1？从后面的过程中我们就会明白，这个其实只是为了分析上的方便，并没有什么必然性。为了得到这样的一个指标，我们接下来先从简单的二元解码出发，得到一些有代表性的结果，然后看它能否推广到一般的自回归解码器中去

#### 二元解码 ####

一般的自回归模型形式为：  
 p ( y ∣ x ) = ∏ t = 1 l p ( y t ∣ y < t , x ) (5) p(\\boldsymbol\{y\}|\\boldsymbol\{x\}) = \\prod\_\{t=1\}^l p(y\_t|\\boldsymbol\{y\}\_\{< t\}, \\boldsymbol\{x\})\\tag\{5\} p(y∣x)=t=1∏lp(yt∣y<t,x)(5)  
也就是说，位置 t t t的解码不仅依赖于输入 x x x，还依赖 t t t之前已经获得的所有解码结果。简单起见，我们先考虑一种简单的情况，假设每一步解码只依赖于前一时刻的结果，即：  
 p ( y ∣ x ) = ∏ t = 1 l p ( y t ∣ y t − 1 , x ) (6) p(\\boldsymbol\{y\}|\\boldsymbol\{x\}) = \\prod\_\{t=1\}^l p(y\_t|y\_\{t-1\}, \\boldsymbol\{x\})\\tag\{6\} p(y∣x)=t=1∏lp(yt∣yt−1,x)(6)  
这样一来，对于固定的 x x x，解码器实际上就只是一个 n × n n\\times n n×n的转移矩阵 P = ( P i , j ) \\boldsymbol\{P\}=(P\_\{i,j\}) P=(Pi,j)，其中 P i , j P\_\{i,j\} Pi,j表示从 i i i后面接 j j j的概率， n n n代表词表大小。这样的解码器叫做**二元语法模型、2-gram模型、马尔可夫模型**等等。我们还需要一个终止标记<eos>，遇到<eos>就停止解码，所以实际上转移矩阵是 ( n + 1 ) × ( n + 1 ) (n+1)\\times (n+1) (n\+1)×(n\+1)才对，但是我们考虑重复解码都是在终止之前，所以只需要考虑除去<eos>的 n × n n\\times n n×n部分就行了

我们要计算的是重复子序列出现的概率，假设 \[ i , j , k \] \[i,j,k\] \[i,j,k\]是一个三元重复子序列，那么它的出现概率就是序列 \[ i , j , k , i , j , k , i \] \[i,j,k,i,j,k,i\] \[i,j,k,i,j,k,i\]出现的概率：  
 P i , j P j , k P k , i P i , j P j , k P k , i = P i , j 2 P j , k 2 P k , i 2 (7) P\_\{i,j\}P\_\{j,k\}P\_\{k,i\}P\_\{i,j\}P\_\{j,k\}P\_\{k,i\}=P\_\{i,j\}^2P\_\{j,k\}^2P\_\{k,i\}^2 \\tag\{7\} Pi,jPj,kPk,iPi,jPj,kPk,i=Pi,j2Pj,k2Pk,i2(7)  
因此所有的三元重复子序列的概率为  
 ∑ i , j , k P i , j 2 P j , k 2 P k , i 2 = Tr   ( P ⊗ P ) 3 (8) \\sum\_\{i,j,k\} P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2 = \\text\{Tr\}\\,(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^3\\tag\{8\} i,j,k∑Pi,j2Pj,k2Pk,i2=Tr(P⊗P)3(8)  
这里的 ⊗ \\otimes ⊗表示逐位元素对应相乘，而 Tr \\text\{Tr\} Tr则是矩阵的迹，即对角线元素之和。最后，我们将所有长度的重复子序列概率都加起来：  
 R = ∑ k = 1 ∞ Tr   ( P ⊗ P ) k = Tr   ( ∑ k = 1 ∞ ( P ⊗ P ) k ) (9) R = \\sum\_\{k=1\}^\{\\infty\}\\text\{Tr\}\\,(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^k = \\text\{Tr\}\\,\\left(\\sum\_\{k=1\}^\{\\infty\}(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^k\\right)\\tag\{9\} R=k=1∑∞Tr(P⊗P)k=Tr(k=1∑∞(P⊗P)k)(9)

> 两个矩阵对应位置相乘 ⊗ \\otimes ⊗的目的是为了使得每个位置上的值变为原来的平方，因此就实现了式子(7)的目的
> 
>  ( P ⊗ P ) k (\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^k (P⊗P)k中的 k k k实际上表示 k k k元重复子序列，那为什么对这个 k k k次方的矩阵求迹就是结果了呢？下图以 k = 2 k=2 k=2为例（其中蓝色矩阵中的每一项都是平方项，只不过我并没有显式的标出平方，大家心里有数就行）
> 
> ![a7f3fcbd3af4d8b20ef3a0c43cac2c70.png_shadow][]
> 
> 对角线上的每一个元素代表了固定 i i i而遍历 j j j的结果，那么把所有的对角线都加起来（迹），实际上就是做了一个 ∑ i \\sum\\limits\_\{i\} i∑的操作

这就是二元解码器出现重复解码的概率。当然目前它还只是一个理论公式，不过它是我们重要的出发点。我们将分别推导它的上下界，以获得更有启发性的结果

#### 一个下界 ####

直接看式(9)可能看不出点儿啥，我们可以先推导它一个更加直观的下界。还是以三元重复子序列为例，利用均值不等式我们可以得到：  
 ∑ i , j , k P i , j 2 P j , k 2 P k , i 2 = n 3 × ∑ i , j , k P i , j 2 P j , k 2 P k , i 2 n 3 ≥ n 3 × ( ∑ i , j , k P i , j P j , k P k , i n 3 ) 2 = ( Tr   P 3 ) 2 n 3 (10) \\sum\_\{i,j,k\} P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2 = n^3\\times\\frac\{\\sum\_\{i,j,k\} P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2\}\{n^3\}\\geq n^3\\times\\left(\\frac\{\\sum\_\{i,j,k\} P\_\{i,j\} P\_\{j,k\} P\_\{k,i\}\}\{n^3\}\\right)^2 = \\frac\{(\\text\{Tr\}\\, \\boldsymbol\{P\}^3)^2\}\{n^3\} \\tag\{10\} i,j,k∑Pi,j2Pj,k2Pk,i2=n3×n3∑i,j,kPi,j2Pj,k2Pk,i2≥n3×(n3∑i,j,kPi,jPj,kPk,i)2=n3(TrP3)2(10)

> 上述不等式主要是由平方平均数大于等于算数平均数得到的，我们将 P i , j P j , k P k , i , n 3 P\_\{i,j\}P\_\{j,k\}P\_\{k,i\},n^3 Pi,jPj,kPk,i,n3分别记作 x , m x,m x,m，则根据均值不等式有  
>  ∑ x 2 m ≥ ∑ x m \\sqrt\{\\frac\{\\sum x^2\}\{m\}\}\\ge \\frac\{\\sum x\}\{m\} m∑x2≥m∑x  
> 两边同时平方得  
>  ∑ x 2 m ≥ ( ∑ x m ) 2 \{\\frac\{\\sum x^2\}\{m\}\}\\ge \\left(\\frac\{\\sum x\}\{m\}\\right)^2 m∑x2≥(m∑x)2

事实上，我们还可以做的更精细一些。假设 P \\boldsymbol\{P\} P矩阵有一些元素为0，那么 P i , j 2 P j , k 2 P k , i 2 P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2 Pi,j2Pj,k2Pk,i2中的非零元素的个数就不是 n 3 n^3 n3，我们假设非零元素个数为 N 3 ( P ) < n 3 N\_3(\\boldsymbol\{P\})<n^3 N3(P)<n3，那么我们再利用均值不等式的时候，可以只对非零元素进行，结果是将上述的 n 3 n^3 n3换为 N 3 ( P ) N\_3(\\boldsymbol\{P\}) N3(P)：  
 ∑ i , j , k P i , j 2 P j , k 2 P k , i 2 ≥ ( Tr   P 3 ) 2 N 3 ( P ) (11) \\sum\_\{i,j,k\} P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2 \\geq \\frac\{(\\text\{Tr\}\\, \\boldsymbol\{P\}^3)^2\}\{N\_3(\\boldsymbol\{P\})\} \\tag\{11\} i,j,k∑Pi,j2Pj,k2Pk,i2≥N3(P)(TrP3)2(11)  
 N 3 ( P ) N\_3(\\boldsymbol\{P\}) N3(P)的直接计算比较困难，没有一般的通项公式，但我们可以做个简单的估算：设 P \\boldsymbol\{P\} P的非零元素的比例为 ζ \\zeta ζ，也就是非零元素个数为 ζ n 2 \\zeta n^2 ζn2，那么我们可以认为 P i , j 2 P j , k 2 P k , i 2 P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2 Pi,j2Pj,k2Pk,i2的非零元素比例近似为 ζ 3 \\zeta^3 ζ3

> 单个 P i , j P\_\{i,j\} Pi,j非零的概率是 ζ \\zeta ζ，所以三项同时非零的概率就是 ζ 3 \\zeta^3 ζ3

由于总的排列数为 n 3 n^3 n3，所以我们可以认为 N 3 ( P ) ∼ ζ 3 n 3 N\_3(\\boldsymbol\{P\})\\sim \\zeta^3n^3 N3(P)∼ζ3n3，或者一般地 N k ( P ) ∼ ζ k n k N\_k(\\boldsymbol\{P\})\\sim \\zeta^k n^k Nk(P)∼ζknk。注意可以举例说明这个估计既不能保证是上界，也不能保证是下界，所以将 N 3 ( P ) N\_3(\\boldsymbol\{P\}) N3(P)替换为 ζ 3 n 3 \\zeta^3 n^3 ζ3n3后，我们无法保证上述不等号的成立。不过，如果我们愿意相信 ζ 3 n 3 \\zeta^3n^3 ζ3n3是一个足够好的近似，我们依然可以（怀着忐忑而又坚定的信念）写下  
 ∑ i , j , k P i , j 2 P j , k 2 P k , i 2 ≥ ( Tr   P 3 ) 2 ζ 3 n 3 (12) \\sum\_\{i,j,k\} P\_\{i,j\}^2 P\_\{j,k\}^2 P\_\{k,i\}^2 \\geq \\frac\{(\\text\{Tr\}\\, \\boldsymbol\{P\}^3)^2\}\{\\zeta^3 n^3\} \\tag\{12\} i,j,k∑Pi,j2Pj,k2Pk,i2≥ζ3n3(TrP3)2(12)  
以及  
 R = ∑ k = 1 ∞ Tr   ( P ⊗ P ) k ≥ ∑ k = 1 ∞ ( Tr   P k ) 2 ζ k n k (13) R = \\sum\_\{k=1\}^\{\\infty\}\\text\{Tr\}\\,(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^k \\geq \\sum\_\{k=1\}^\{\\infty\} \\frac\{(\\text\{Tr\}\\, \\boldsymbol\{P\}^k)^2\}\{\\zeta^k n^k\}\\tag\{13\} R=k=1∑∞Tr(P⊗P)k≥k=1∑∞ζknk(TrPk)2(13)  
或者我们干脆不关心不等号，直接将右边的结果视为 R R R的一个估计

#### 初步结论 ####

此时可能有些读者会疑惑：我们一般所用的模型的概率分布都是Softmax出来的，Softmax的结果都不等于0，所以 ζ \\zeta ζ应该恒等于1，因此引入 ζ \\zeta ζ似乎并没有什么价值？

并非如此。的确，Softmax出来的概率分布不会有严格等于0的情况，但是我们的解码算法，通常却会将它们强制置零！文本生成常用的解码算法主要包括随机采样和确定性解码两种，其中随机采样分为直接随机采样、Top-k随机采样、Top-p随机采样，而确定性解码则包括Greedy Search、Beam Search两种，在这五种不同的解码算法中，除了最不常用的直接随机外，其余四种都是强行保留若干个最优结果来作为候选值，这样就相当于**直接截断了转移矩阵**，大大降低了非零概率 ζ \\zeta ζ

比如最极端的Greedy Search，容易推出它最小的非零概率为 ζ = 1 n \\zeta=\\frac\{1\}\{n\} ζ=n1，由前面式(13)的推导知， ζ \\zeta ζ是在分母中，所以 ζ \\zeta ζ的缩小意味着重复率 R R R的增加，这就告诉我们Greedy Search的重复解码风险是相当高的。尽管目前的结论仅仅是在二元解码模型的假设下得出的，但Greedy Search重复解码确实是我们经常观察到的现象，所以这结论于解释确实已经有代表性了

#### 一个上界 ####

有了下界，怎么可以没有上界呢？**下界能帮助我们结识一些现象，而上界则可以给我们提供改进思路**

为了推导上界，我们利用到如下两个结论：

1.  矩阵的迹等于它所有特征值之和
2.  如果 λ 1 ( A ) ≥ λ 2 ( A ) ≥ ⋯ ≥ λ n ( A ) \\lambda\_1(\\boldsymbol\{A\})\\geq\\lambda\_2(\\boldsymbol\{A\})\\geq\\cdots\\geq\\lambda\_n(\\boldsymbol\{A\}) λ1(A)≥λ2(A)≥⋯≥λn(A)是矩阵 A \\boldsymbol\{A\} A的所有特征值，那么 λ 1 k ( A ) ≥ λ 2 k ( A ) ≥ ⋯ ≥ λ n k ( A ) \\lambda\_1^k(\\boldsymbol\{A\})\\geq\\lambda\_2^k(\\boldsymbol\{A\})\\geq\\cdots\\geq\\lambda\_n^k(\\boldsymbol\{A\}) λ1k(A)≥λ2k(A)≥⋯≥λnk(A)是矩阵 A k \\boldsymbol\{A\}^k Ak的所有特征值

所以，我们可以推导：  
 R =   ∑ k = 1 ∞ Tr   ( P ⊗ P ) k = ∑ k = 1 ∞ ∑ i = 1 n λ i ( ( P ⊗ P ) k ) =   ∑ k = 1 ∞ ∑ i = 1 n λ i k ( P ⊗ P ) = ∑ i = 1 n ∑ k = 1 ∞ λ i k ( P ⊗ P ) =   ∑ i = 1 n λ i ( P ⊗ P ) 1 − λ i ( P ⊗ P ) (14) \\begin\{aligned\} R =&\\, \\sum\_\{k=1\}^\{\\infty\}\\text\{Tr\}\\,(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^k = \\sum\_\{k=1\}^\{\\infty\}\\sum\_\{i=1\}^n\\lambda\_i\\left((\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})^k\\right)\\\\ =&\\, \\sum\_\{k=1\}^\{\\infty\}\\sum\_\{i=1\}^n\\lambda\_i^k\\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right) = \\sum\_\{i=1\}^n \\sum\_\{k=1\}^\{\\infty\}\\lambda\_i^k\\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right) \\\\ =&\\, \\sum\_\{i=1\}^n \\frac\{\\lambda\_i \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\}\{1 - \\lambda\_i \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\} \\end\{aligned\}\\tag\{14\} R===k=1∑∞Tr(P⊗P)k=k=1∑∞i=1∑nλi((P⊗P)k)k=1∑∞i=1∑nλik(P⊗P)=i=1∑nk=1∑∞λik(P⊗P)i=1∑n1−λi(P⊗P)λi(P⊗P)(14)  
上述过程用到了级数 ∑ k = 1 ∞ x k = x 1 − x \\sum\\limits\_\{k=1\}^\{\\infty\}x^k=\\frac\{x\}\{1-x\} k=1∑∞xk=1−xx，该级数只有在 ∣ x ∣ < 1 |x|<1 ∣x∣<1才收敛，而很巧的是，我们可以证明 P ⊗ P \\boldsymbol\{P\}\\otimes \\boldsymbol\{P\} P⊗P的特征根绝对值必然不大于1，且通常都小于1：由于 P \\boldsymbol\{P\} P是转移矩阵，因此它的每一行之和都为1，因此 P ⊗ P \\boldsymbol\{P\}\\otimes \\boldsymbol\{P\} P⊗P的每一行之和都小于等于1，设 λ , x \\lambda,\\boldsymbol\{x\} λ,x是它的特征值和特征向量，那么 ( P ⊗ P ) x = λ x (\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\})\\boldsymbol\{x\}=\\lambda \\boldsymbol\{x\} (P⊗P)x=λx，不失一般性，设 x \\boldsymbol\{x\} x的绝对值最大的元素为 x 1 x\_1 x1， P ⊗ P \\boldsymbol\{P\}\\otimes \\boldsymbol\{P\} P⊗P的第一个行向量为 q 1 ⊤ \\boldsymbol\{q\}\_1^\{\\top\} q1⊤，那么我们有 ∣ λ ∣ ∣ x 1 ∣ = ∣ q 1 ⊤ x ∣ ≤ ∣ x 1 ∣ |\\lambda| |x\_1| = |\\boldsymbol\{q\}\_1^\{\\top\}\\boldsymbol\{x\}| \\leq |x\_1| ∣λ∣∣x1∣=∣q1⊤x∣≤∣x1∣，从而 ∣ λ ∣ ≤ 1 |\\lambda|\\leq 1 ∣λ∣≤1，并且等号成立的条件还是比较苛刻的，所以通常来说都是 ∣ λ ∣ < 1 |\\lambda|<1 ∣λ∣<1

> 注意这里 x 1 x\_1 x1不是随便取的一个别名，而是向量 x \\boldsymbol\{x\} x中的第一个值，也就是说，我设 x \\boldsymbol\{x\} x绝对值最大的元素就是第一个数，因此 ∣ λ ∣ ∣ x 1 ∣ = ∣ q 1 ⊤ x ∣ |\\lambda||x\_1|=|\\boldsymbol\{q\}\_1^\{\\top\}\\boldsymbol\{x\}| ∣λ∣∣x1∣=∣q1⊤x∣是肯定成立的

注意函数 x 1 − x \\frac\{x\}\{1-x\} 1−xx在 \[ − 1 , 1 ) \[-1,1) \[−1,1)区间是单调递增的，所以式(14)中占主导的是第一项 λ 1 ( P ⊗ P ) 1 − λ 1 ( P ⊗ P ) \\frac\{\\lambda\_1 \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\}\{1 - \\lambda\_1 \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\} 1−λ1(P⊗P)λ1(P⊗P)，如果非要给整体弄一个上界的话，那么可以是 n λ 1 ( P ⊗ P ) 1 − λ 1 ( P ⊗ P ) \\frac\{n\\lambda\_1 \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\}\{1 - \\lambda\_1 \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\} 1−λ1(P⊗P)nλ1(P⊗P)

> 这里可能有读者认为占主导地位的是 λ n ( P ⊗ P ) 1 − λ n ( P ⊗ P ) \\frac\{\\lambda\_n \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\}\{1 - \\lambda\_n \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\} 1−λn(P⊗P)λn(P⊗P)，但实际上并不是，因为我们在前面假设了 λ 1 ≥ ⋯ ≥ λ n \\lambda\_1 \\ge \\cdots \\ge \\lambda\_n λ1≥⋯≥λn，而 1 − λ λ \\frac\{1-\\lambda\}\{\\lambda\} λ1−λ在区间 \[ − 1 , 1 ) \[-1,1) \[−1,1)内又是单调递增的，随意很明显 λ 1 ( P ⊗ P ) 1 − λ 1 ( P ⊗ P ) \\frac\{\\lambda\_1 \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\}\{1 - \\lambda\_1 \\left(\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}\\right)\} 1−λ1(P⊗P)λ1(P⊗P)是最大的

#### 再次结论 ####

由此可见，如果想要降低重复率 R R R，那么我们要想办法降低矩阵 P ⊗ P \\boldsymbol\{P\}\\otimes \\boldsymbol\{P\} P⊗P的最大特征值。 P ⊗ P \\boldsymbol\{P\}\\otimes \\boldsymbol\{P\} P⊗P是一个非负矩阵，根绝非负矩阵的\*\*“Frobenius介值定理”**，我们有：  
 min ⁡ i ∑ j P i , j 2 ≤ λ 1 ( P ⊗ P ) ≤ max ⁡ i ∑ j P i , j 2 (15) \\min\_i \\sum\_j P\_\{i,j\}^2 \\leq \\lambda\_1 (\\boldsymbol\{P\}\\otimes\\boldsymbol\{P\}) \\leq \\max\_i \\sum\_j P\_\{i,j\}^2\\tag\{15\} iminj∑Pi,j2≤λ1(P⊗P)≤imaxj∑Pi,j2(15)  
关于Frobenius介值定理，基本上在任何一本矩阵分析书上都有介绍，它说的是**"非负矩阵的最大特征值在它每一行的和的最小值与最大值之间"\*\*。现在我们知道，为了降低 P ⊗ P \\boldsymbol\{P\}\\otimes \\boldsymbol\{P\} P⊗P的最大特征值，我们需要想办法降低它的每一行之和，即 ∑ j P i , j 2 \\sum\\limits\_\{j\}P\_\{i,j\}^2 j∑Pi,j2，并且由于均值不等式  
 ∑ j P i , j 2 ≥ n ( ∑ j P i , j n ) 2 = 1 n (16) \\sum\_j P\_\{i,j\}^2\\geq n\\left(\\frac\{\\sum\_j P\_\{i,j\}\}\{n\}\\right)^2 = \\frac\{1\}\{n\}\\tag\{16\} j∑Pi,j2≥n(n∑jPi,j)2=n1(16)  
知它的最小值为 1 n \\frac\{1\}\{n\} n1，在 P i , 1 = P i , 2 = ⋯ = P i , n P\_\{i,1\}=P\_\{i,2\}=\\cdots=P\_\{i,n\} Pi,1=Pi,2=⋯=Pi,n时取到，因此最终我们得出结论：**要降低最大特征值，就要使矩阵 P \\boldsymbol\{P\} P每一行尽可能均匀，换言之，要降低 P \\boldsymbol\{P\} P每一行的方差**

怎么降低方差呢？很简单，不能出现过高的概率值即可，比如某一行接近one hot的形式，那么平方之后依然接近one hot的形式，那么求和就接近1，远远大于理论最小值 1 n \\frac\{1\}\{n\} n1。什么情况下会出现过高的概率值呢？也不难理解，就是某个字词后面可以接的字词很少，甚至只有1个候选值的时候，比如"忐"几乎只能接"忑"，那么 P i = 忐 , j = 忑 P\_\{i=\\text\{忐\},j=\\text\{忑\}\} Pi=忐,j=忑就相当高，“矩"后面大概接"阵”、"形"比较多，所以"矩"那一行的方差也不小。那么怎么才能不出现这种过高的概率值呢？很简单，将高概率值的合并起来，当做一个新词来看待就行了，比如"忐忑"合并为一个词，那么"忐"那一行就不存在了，也就无所谓方差大了。同理，“矩形”、"矩阵"也应该合并为一个词比较好

所以，说白了这就告诉我们，**对于文本生成任务来说，以词为单位比以字为单位更加靠谱**（更不容易出现重复解码）。适当地合并一些相关程度比较高的词作为新词加入到词表中，降低转移矩阵的方差，有助于降低重复解码的风险，原论文还给这个操作起了个很高端的名字，叫做Rebalanced Encoding Algorithm，事实上就是这个意思

#### 一般解码 ####

前面我们都是以二元解码模型为例进行的研究，那这个证明过程容易推广到一般的自回归模型中吗？很遗憾，并不容易。对于一般的自回归模型来说，它相当于每一步的 P \\boldsymbol\{P\} P都是不一样的，因此只要模型性能足够好，其实基本上不会出现重复解码，事实上经过充分预训练的生成式模型，确实很少出现重复解码。但是，对于一般的自回归解码，偶尔也还是能观察到重复解码现象，这又该怎么解释呢？

我们或许可以反过来想，\*\*一般的自回归模型出现重复解码现象，是因为它此时退化为了二元解码模型？\*\*对于难度比较高的输入，模型可能无法精细捕捉好每一步的转移概率，从而只能将转移矩阵退化为二元解码，这是有可能的

那么原论文对于这一块又是怎么处理的呢？其实也差不多。原论文假设一般的自回归模型的转移矩阵，只是在二元解码的转移矩阵 P \\boldsymbol\{P\} P的基础上加了个特定时刻的扰动 P ~ = P + Q t \\boldsymbol\{\\tilde\{P\}\}=\\boldsymbol\{P\}+\\boldsymbol\{Q\_t\} P~=P\+Qt，然后指出在 Q t \\boldsymbol\{Q\_t\} Qt足够小的时候， P ~ \\boldsymbol\{\\tilde\{P\}\} P~与二元解码矩阵 P \\boldsymbol\{P\} P的差距也足够小（有点像废话），因此二元解码的结果也能代表一般自回归模型了。所以，对于一般的自回归模型来说，我们确实很无力了，只能用这种想法跟它沾点儿边了～

### References ###

*  [如何应对Seq2Seq中的“根本停不下来”问题？][Seq2Seq]
 *  [Seq2Seq重复解码现象的理论分析尝试][Seq2Seq 1]

[Consistency of a Recurrent Language Model With Respect to Incomplete Decoding]: https://arxiv.org/abs/2002.02492
[Hierarchical Neural Story Generation]: https://arxiv.org/abs/1805.04833
[The Curious Case of Neural Text Degeneration]: https://arxiv.org/abs/1904.09751
[Sparse Sequence-to-Sequence Models]: https://arxiv.org/abs/1905.05702
[A Theoretical Analysis of the Repetition Problem in Text Generation]: https://arxiv.org/abs/2012.14660
[a7f3fcbd3af4d8b20ef3a0c43cac2c70.png_shadow]: /images/20220829/70edca175a9b4095827d8e70aacb9460.png
[Seq2Seq]: https://kexue.fm/archives/7500
[Seq2Seq 1]: https://kexue.fm/archives/8128