讨论 2023-04-27
=
###### tags: `tutorials` `Fudan` `2023`
# 文本生成解码 (二)

本次分享主要会讨论两个话题，一是beam search，即如何同时搜索多条路径以获得更好的结果。二是利用自动机进行解码限制。

## Beam Search
序列生成中总归要涉及到解码算法，这次先介绍最常用的Beam Search，之后如有机会再介绍其他更复杂的解码算法。

### 条件独立
解码各步骤条件独立，解码得到的结果与解码顺序无关，这也是非自回归模型的目标，即可以并行解码。如图所示，各位置独立选择即可。


### 1-Markov
一阶马尔可夫条件，即每个元素只依赖前面一个元素的取值，此时可以采用动态规划，局部最优即是全局最优，每步贪心的选取最优值即可。


### Beam Search
高阶马尔可夫条件，每个元素依赖之前的多个元素，此时局部最优不在是全局最优，只能求近似解。如图是Beam=2的情况，保留得分最高的两个序列。下图中蓝色表示第一名，红色表示第二名，可以看到最终的最高分是中间的第二名引出的，换言之是在贪心解码中被淘汰的路径。


### 转移限制
实际上元素和元素之间不是可以随意转换的，比如EOS之后不能再有其他元素，比如某些元素后只能跟某些元素等。在Beam Search过程中需要关注这些问题，通常对EOS有如下处理，对每个Beam设置标签，代表已经EOS还是没有，如果一个Beam出现EOS，提出整个列表，同时选取得分顺位在总Beam数+1且不是EOS的序列加入，保证总Beam数不变。为此需要将Beam按两倍展开，对其中一半的序列交易限制，让其不可选择EOS。


### cache重排序
自回归生成的解码过程通常都要使用cache功能，也就是已经解码的序列所对应的特征有些是不需要重复计算的。如果不考虑Beam Search，那么我们只要维护Batch个cache即可，每步往里面添加一个元素即可，但Beam Search会改变前缀数量和顺位，如之前例子中给出的，一个Beam可能会派生成出两个新的Beam，也可能一个Beam中分数都很低，无派生，这都会导致其序列前缀改变，同时对应的cache也不一样。为此，就需要每一步根据Beam的派生关系（由上一步的某一个Beam衍生出这一步的某一个Beam），需要继承其来源的cache。而这一过程通常称之为cache重排序。

关于如何Batch，有需要可以参考我自己写的Beam Search
https://github.com/QipengGuo/GraphWriter-DGL/blob/reproduce/graphwriter.py#L98-L180

## 自动机解码

### Trie树
前缀树是一种很常用的字符串处理结构，其本质是一个简化的自动机，我们从根节点出发，然后根据下一个字符是什么进行分支，可以看出，每个节点向下前进的路线是有限的，换言之，当我们生成了一些文字之后，后续内容必须要在一个固定范围里选择，而不是整个词表。这也是自动机限制的核心思想，每个状态只能在一个词表的子集中进行选择。

### Sub-token 自动机
Trie原本是为字符设计，但我可以简单的把它拓展成以subword为单位的，比如括号表达式，我们可以通过一个自动机保证其输出合法性。

当然，这里有一个有趣的问题是，为什么模型自己学不会这些简单的模式，括号表达式都有可能犯错？

我的个人理解是抽象能力不足导致的，括号表达式在我们看来很简单，但比如在一个左括号之后，模型已经生成了1000个token的内容，这个时候，它是否有能力把把已生成的部分抽象成两个token，左括号和文字内容？如果不能，那么他考虑是一个有1001个token的序列该如何向下进行生成的问题，自然很难。并且这种抽象是临时的，如果我们要继续生成文字内容，这1000个token就需要细致的来看，所以模型需要在抽象和细节之间恰当的切换，这种能力并不是很容易获得的。某种意义上，这比现在的instruction tuning还要难，因为模型需要自己下命令，调整自己的思维方式。

### Soft 自动机限制

很多时候，自动机的规则并不是那么容易设计的。但我们可以用一个折中的办法，通过上一个词来约束生成过程。
$$P(w_t|w_{<t})+P(w_t|w_{t-1})$$