讨论 2021-07-01
=
###### tags: `tutorials` `Fudan` `2021`

## 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