强化学习与序列生成

介绍

序列生成有广泛的应用，如机器翻译、序列标注（实体识别等）、文本摘要、问答等等。从机器学习的角度来说，序列生成就是给定一些上下文（context）$x$，然后生成序列 $y$（即 $y_1y_2…y_T$）。针对序列生成任务，使用监督学习时，不管是用CNN、RNN还是Transformer来建模型，最终优化的目标大多是最小化negative log-likelihood，目标函数公式如下：

$$L_{nll} = -\sum_{t=1}^T \log p(y_t|y_1,...,y_{t-1}, x) \tag{1}\label{eq1}$$

当模型训练完后，一般用如下greedy search的方式生成序列 $\hat{y}=[\hat{y}_1,…\hat{y}_T]$，即选每一个时间步骤上选择概率最大的输出，其中$\hat{y}_t$表示第 $t$ 步生成的输出：

$$\hat{y}_{t} = \underset{y_t}{\operatorname{argmax}}p(\hat{y}_t|\hat{y}_1,...\hat{y}_{t-1}, x)$$

对文本生成（如摘要、翻译）任务来说，评估函数一般是ROUGE, BLEU。监督学习很难直接对这类不可微分的评估函数进行学习。这就使得训练和测试的时候产生了偏差。于是强化学习（Reinforcement Learning）的优势就体现出来。强化学习不需要反馈（reward）或者损失是可微分的，因而可以使用任何评估函数用来进行优化学习。

强化学习框架

就我所知，Ranzatoet al.(2016)的文章¹首先使用强化学习框架来训练序列生成，并参考Williams,1992²和Zaremba & Sutskever, 2015³文中的policy gradient方法REINFORCE算法来训练。强化学习框架⁴的基本要素有agent，state，action，reward，policy。在序列生成任务中，Ranzato将这些要素按如下方式对应：

• agent: 序列生成模型（RNN等）
• action: 在每一个时间步骤选择下一个输出（词或标注等）
• policy: agent的参数$\theta$
• state: 模型内部状态（如RNN的hidden units）
• reward: 可是任何评估函数分值，如ROUGE等，可在每个action后获得反馈，也可在序列生成完后再反馈

目标函数

训练的目标就是找到参数以最大化反馈（reward）$r( y )$。loss定义为负的反馈期望（negative expected reward）：

$$L_{rl} = - \sum_{y}p(y|x,\theta)r(y) = -\mathbb{E}_{y \sim p(y|x,\theta)}r(y) \tag{2}\label{eq2}$$

公式含义为：给定上下文 $x$ ，对所有可能生成的序列 $y$ 的反馈计算概率加权和。最大化期望和，也就是更新参数，使得反馈越大的序列，生成出来的概率越大。然而生成的序列 $y$ 的可能组合太多，完全计算所有可能的序列，然后再计算梯度下降更新几乎不可能。在实际中采用近似处理，即根据模型得到的概率函数 $p(y|x,\theta)$ 采样（Sampling） 一个序列 $y^s$ (即 $y_1^s,…,y_T^s$)。具体就是对每一个time step $t$，根据概率 $p(y_t|y_1,…,y_{t-1},x,\theta)$ 随机选择一个输出 $y_t^s$ 。

$$L_{rl} \approx -r(y^s)\sum_{t=1}^T \log p(y_t^s|y_1^s,...,y_{t-1}^s, x, \theta) \tag{3}\label{eq3}$$

对比公式$\eqref{eq1}$和公式$\eqref{eq3}$，这里有两点区别：

1. 通过强化学习把不可微分的评估函数分值变成了权重，然后类似监督学习一样进行梯度更新
2. 一般监督学习训练时都是使用真实（groud truth）的序列 $y$，而强化学习用的采样的序列$y^s$。

策略梯度和REINFORCE算法

为了计算公式$\eqref{eq2}$的梯度，采用REINFORCE算法²,⁴。带有不可微分的反馈函数的期望梯度，可以按如下方式计算，即对策略的梯度（策略为参数$\theta$）：

$$\nabla_\theta L_{rl} = -\mathbb{E}_{y \sim p(y|x,\theta)}[r(y) \nabla_\theta \log p(y|x,\theta)]$$

像上面提到的一样，对每一个训练样本，根据概率 $p(y_t|y_1,…,y_{t-1}, x, \theta)$用 Monte-Carlo采样一条序列$y^s = (y_1^s, … ,y_T^s)$。通过采样得到 $y^s$ 后，梯度公式就变为：

$$\nabla_\theta L_{rl} \approx r(y^s) \nabla_\theta \log p(y^s|x,\theta)$$

对比公式$\eqref{eq3}$ $L_{rl}$ 和公式$\eqref{eq1}$ $ L_{nll} $ ，可发现公式$\eqref{eq3}$ $L_{rl}$ 相当于在梯度更新时添加了 $r(y^s)$ 权重，若序列分值越大梯度便越大，反之则梯度减弱。在实际训练的时候，因为随机采样的搜索空间太大，直接进行强化学习会导致不稳定和很难收敛。所以通常先用$L_{nll}$进行预训练，然后再使用用 $L_{rl}$ 训练。

REINFORCE with a Baseline

Ranzato文章¹指出REINFORCE算法会先建立一个baseline $\bar{r}_{t}$。引入baseline后目标函数为（非原文中的公式，此处根据理解改写）：

$$L_{rl} = - \sum_{t=1}^T （r(y^s) - \bar{r}_{t}) \log p(y_t^s|y_1^s,...,y_{t-1}^s, x, \theta) \tag{4} \label{eq4}$$

$\bar{r}_t$含义为：如果$r(y^s) > \bar{r}_t$，鼓励选择当前的输出$y_t^s$，梯度方向为增大$y_t^s$的概率，反之则减少其概率。文中 $\bar{r}_t$ 用RNN的隐藏变量$\mathbf{h}_t$作为输入，使用线性回归模型，$\bar{r}_t = w \cdot \mathbf{h}_t + b $，用最小化损失函数$||\bar{r}_t - r(y^s)||^2$进行训练。

Ranzato文章¹采用了一种混合策略，先使用$L_{nll}$训练$N^{nll}$轮。然后混合训练$N^{nll+rl}$轮，混合训练时前$(T - \Delta)$个time step用$L_{nll}$，后面$\Delta$个time step用$L_{rl}$学习。接着继续混合训练$N^{nll+rl}$轮，这次time step分别为$(T-2\Delta)$和$2\Delta$。如此往复直到最终完全使用强化学习训练。

Self-critical Policy Gradient

与Ranzato et al.(2016)¹不同是，Renie et al.(2016)⁵ 首先介绍了用常数$b$作为baseline，表明它不影响梯度的期望，但是可以减少梯度估计时的方差。然后Renie et al.使用了self-critical policy sequence training (SCST)算法。算法在训练的每一循环产生两个输出序列：

1. $y^s$: 与上面相同，在每一个解码的步骤上根据 $p(y_t^s|y_1^s,…,y_{t-1}^s)$ 进行采样，随机选择 $y_t^s$
2. $\hat{y}$: 在每一个解码的步骤上选择 $p(y_t^s|y_1^s,…,y_{t-1}^s)$ 最大概率，即gready search选择 $\hat{y}_t$

得到两个序列后，强化学习的目标函数如下：

$$L_{rl} = -(r(y^s) - r(\hat{y})) \sum_{t=1}^T \log p(y_t^s|y_1^s,...,y_{t-1}^s, x) \tag{5} \label{eq5}$$

公式$\eqref{eq5}$和公式$\eqref{eq3}$对比多了一个基于gready search生成的序列$\hat{y}$的反馈。作为矫正，也就是将$y^s$和$\hat{y}$进行对比，所以叫self-critical。梯度下降更新$L_{rl}$ 的含义相当于，若$r(y^s) \gt r(\hat{y})$，采样的结果比gready search结果好，增大采样到的 $y^s$ 的概率，相反则减小其概率。而 $| r(y^s) - r(\hat{y}))|$ 值就是一个弹性的学习率权重。

Paulus et al. (2018)⁶将$L_{rl}$和$L_{nll}$合在一起，来训练生成式摘要抽取:

$$L_{mixed} = \gamma L_{nll} + (1-\gamma)L_{rl}$$

从最终的目标函数来看，强化学习起到作用基本是给目标函数添加了基于ROUGE或BLEU评估函数带来的权值。有意思的是，只用 $L_{rl}$ 训练的结果在ROUGE评分上会比使用混合的高，但是人工评估，混合目标函数训练出的结果可读性和相关性会更好。这一点在下面的抽取式摘要中得到了类似的印证。

其他

coherence reward

Wu & Hu, 2018⁷文章使用强化学习从文章中抽取句子作为摘要。强化学习的架构基本相同，只是action变成二选一，即通过{0, 1}判断是否抽取当前句子作为摘要。除此之外，文中在使用ROUGE作为最终的反馈，还在每一个time step上引入了一个新的反馈coherence。最终训练时使用的目标函数为（非原文中的公式，而是基于理解和文中的算法步骤改写）：

$$L_{rl} = - \sum_{t=1}^T (r(y^s) + \lambda \sum_{i=t}^T{\tilde{r}_i}) \log p(y_t^s|y_1^s,...,y_{t-1}^s, x) \tag{6} \label{eq6}$$

公式中的 $\tilde{r}$ 为在每一个action后立刻得到coherence反馈。文中单独训练了一个网络来判断两句话的coherence分值。若当前句子被选取为摘要，则跟上一句选取为摘要的句子计算词、coherence分值，反之分值为0。

持续更新中…..

References

¹. Marc’Aurelio Ranzato, Sumit Chopra, Michael Auli, and Wojciech Zaremba. Sequence level training with recurrent neural networks. In _ICLR_ 2016. ↩

². Ronald J. Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. In _Machine Learning_, 8:229-256, 1992 ↩

³. Wojciech Zaremba and Ilya Sutskever. Reinforcement Learning Neural Turing Machines - Revised. In _arXiv preprint arXiv:1505.00521_, 2015 ↩

⁴. Richard S. Sutton and Andrew G. Barto. Reinforcement learning: An introduction. _MIT Press_, 1988 ↩

⁵. Steven J Renie, Etienne Marcheret, Youssef Mroueh, Jarret Ross, and Vaibhava Goel. Self-critical sequence training for image captioning. In _CVPR_ 2017 ↩

⁶. Romain Paulus, Caiming Xiong, and Richard Socher. A deep reinforced model for abstractive summarization. In _ICLR_ 2018. ↩

⁷. Yuxiang Wu and Baotian Hu. Learning to Extract Coherent Summary via Deep Reinforcement Learning. _AAAI_, 2018 ↩

⁸. Asli Celikyilmaz, Antoine Bosselut, Xiaodong He, and Yejin Choi. Deep communicating agents for abstractive summarization. In _Proc. of NAACL_, 2018 ↩

⁹. Yaser Keneshloo, Tian Shi, Naren Ramakrishnan and Chandan K. Reddy. Deep Reinforcement Learning For Sequence to Sequence Models, In _arXiv preprint arXiv:1805.09461_, 2018 ↩

Appendix

Ranzato et al.(2016)¹文中提到了$\frac{\partial L}{\partial o_t} = softmax(o_t) - \mathbb{1}(y_t)$，其中$o_t = [o_{t1},…,o_{tT}]$ 是每一步softemax的输入，$L$为目标函数。下面对这个梯度公式做出了推导：

$$\begin{align} L & = -\sum_{t=1}^T \log p(y_t|y_1,...,y_{t-1}, x) \\ & = -\sum_{t=1}^T \log(softmax(o_t) \mathbb{1}(y_t)) \\ \end{align}$$

$\mathbb{1}(i)$是一个指示器(indicator)，只有第$i$元素为1，其余为0。$L$对$o_t$的梯度$\frac{\partial L}{\partial o_t}$推导如下

1. $o_{ti}=y_t$时，对$o_{ti}$的偏导为：

$$\begin{align} \frac{\partial L}{\partial o_{ti}} & = -\frac{\partial \log(\frac{e^{o_{ti}}}{\sum_{j=1}^T e^{o_{tj}}})}{\partial o_{ti}} \\ & = -\frac{\partial ( o_{ti} - \log({\sum_{j=1}^T e^{o_{tj}}}))}{\partial o_{ti}} \\ & = - 1 + \frac{1}{\sum_{j=1}^T e^{o_{tj}}}e^{o_{ti}} \end{align}$$

1. $o_{tj} \neq y_t$时，对$o_{ti}$的偏导为：

$$\begin{align} \frac{\partial L}{\partial o_{tj}} & = -\frac{\partial \log(\frac{e^{o_{ti}}}{\sum_{k=1}^T e^{o_{tk}}})}{\partial o_{tj}} \\ & = -\frac{\partial ( o_{ti} - \log({\sum_{k=1}^T e^{o_{tk}}}))}{\partial o_{tj}} \\ & = \frac{1}{\sum_{k=1}^T e^{o_{tj}}}e^{o_{tj}} \end{align}$$

所以最终：

$$\frac{\partial L}{\partial o_t} = softmax(o_t) - \mathbb{1}(y_t)$$