讨论 2019-11-18
=

## 序列解码

机器翻译乃至文本生成中的必不可少的一个环节就是解码，同时由于大部分文本生成采用序列方式生成，所以最常用的解码方式也是序列解码。本次内容从马尔可夫模型和维特比解码出发，再到循环神经网，beam search等流行结构和算法。

## 生成为什么叫解码，难在何处？
生成的目标是按照我们的要求，产生一段文本，而解码则是找寻一组离散的变量取值来满足模型要求。假如我们把模型规定为翻译规则，那么翻译问题就可以转变为寻找最符合翻译规则的一段文本。解码本质上是一个优化问题，而优化离散变量或是复杂函数都是十分困难的。但显然现实应用场景并不允许我们进行十分复杂的解码过程（耗时过长，对算力要求高等），所以在设计模型时通常要考虑解码的难易程度。

### 文本空间
在解码文本类内容时，我们通常要面对极大的文本空间，试想字符的排列是十分庞大的。因此，文本解码问题基本是不可能采用枚举类的方法的，必须依赖独立性假设，或进行拆解。

### 语言的复杂性
语言包含了繁多且复杂的规律，有时一两个字的区别就对语义产生了极大的影响，换言之语言规律对应的函数极其复杂，难以优化。

## 马尔可夫条件
马尔可夫条件是一个非常强的假设，其假定序列中的第t次决策只和t-1的状态相关，与t-2到更之前的状态都无关。这种性质也叫作无后效性，即所作出的决定只影响下一步而不在影响后续决策。

$P(x_t|x_{<t}) = P(x_t|x_{t-1})$

- 不合符条件可以创造条件，类似状态压缩动态规划的做法，对于有后效性的状态，可以把多个状态合并成一个状态，直到没有后效性为止，但这种压缩会使状态空间变得很大，最终退化。
- 可以把原问题拆分，保证局部最优就是全局最优，不管是估计参数还是解码都十分简单，迅速。

## 维特比解码
对于任意有向无环图（DAG），我们可以利用动态规划的思想，对任意点的转移方程即是前驱节点的代价加上从该节点转移过来之和的最优者。


## 隐马尔可夫模型
隐马尔可夫模型引入了隐变量的概念，隐变量之间满足马尔可夫条件，再有隐变量决定观测变量。
$P(y_t|y_{<t},x_{<t}) = P(y_t|x_t) P(x_t|x_{t-1})$
我们可以看出，这和RNN的公式有些类似
$P(y_t|y_{<t},h_{<t}) = P(y_t|h_t) P(h_t|h_{t-1},y_{t-1})$
## RNN
RNN虽然与隐马尔可夫模型有相似之处，但本质不同，RNN并不遵守马尔可夫条件，所以表达能力的上限更强。同时RNN的状态转移也选择在连续空间中进行决定转换，而非概率采样的形式。看似RNN中$h_t$是由$h_{t-1}$计算得来，但同时也会接受$x_t$的信息，所以并不是只和之前状态相关。更好理解的形式是Attention，它明确打破了马尔可夫条件，因为可以对之前整个序列进行访问，显然每个决定都有后效性。

## Transformer
正如上面对Attention的描述，Transformer显式地打破了马尔可夫条件，并且比RNN更高效。在RNN中，对$h_{<t}$的表示能力取决于隐层维度，换言之，越复杂，越需要历史信息参与的模型也要求更大的隐层维度。但Transformer并不受这一点影响。

## beam search
脱离了马尔可夫条件之后，虽然能建模更加复杂的规律，但也引入了后效性，导致无法用维特比算法解码（也用不起，词表过大，意味着状态数太多）。beam search是对贪心算法的拓展，每次保留Top-K种方案。虽然是贪心算法，但beam search实际效果很好，并且保留的方案数也不需要很多，这要是序列的每个决策实际上只集中在少数几个选择上。（其余大部分选项趋于0）

Beam search的变种很多，有局部打分，全局打分，保持活性等众多不同修改。但遗憾的是这些改进的超参数通常只适用于某一个数据集。

## decoding penalty
其中lp为length penalty，cp为coverage penalty，$p_{i,j}$为Attention score。可以看到，在生成时我们鼓励长句子和高覆盖。
其中超参设置可参见https://arxiv.org/pdf/1609.08144.pdf

$$ep(X,Y) = \gamma \frac{|X|}{|Y|}$$
另外还有对EOS的控制，希望翻译得到的句子长度和原句符合一定的比例关系。