【搜出来的文本】⋅(一)从文本生成到搜索采样
By 苏剑林 | 2021-01-07 | 60038位读者 |最近,笔者入了一个新坑:基于离散优化的思想做一些文本生成任务。简单来说,就是把我们要生成文本的目标量化地写下来,构建一个分布,然后搜索这个分布的最大值点或者从这个分布中进行采样,这个过程通常不需要标签数据的训练。由于语言是离散的,因此梯度下降之类的连续函数优化方法不可用,并且由于这个分布通常没有容易采样的形式,直接采样也不可行,因此需要一些特别设计的采样算法,比如拒绝采样(Rejection Sampling)、MCMC(Markov Chain Monte Carlo)、MH采样(Metropolis-Hastings Sampling)、吉布斯采样(Gibbs Sampling),等等。
有些读者可能会觉得有些眼熟,似乎回到了让人头大的学习LDA(Latent Dirichlet Allocation)的那些年?没错,上述采样算法其实也是理解LDA模型的必备基础。本文我们就来回顾这些形形色色的采样算法,它们将会出现在后面要介绍的丰富的文本生成应用中。
明确目标 #
很多时候,我们需要根据一些特定的信息$\boldsymbol{c}$来生成目标文本$\boldsymbol{x}$,用数学的话说就是条件语言模型$p(\boldsymbol{x}|\boldsymbol{c})$,不过我们无法得到足够多的语料对$(\boldsymbol{x},\boldsymbol{c})$去直接监督训练一个条件语言模型,而是只能训练一个无条件的语言模型$p(\boldsymbol{x})$,但我们又可以人为地设计一个指标来定量描述$\boldsymbol{x}$和$\boldsymbol{c}$之间的联系。那么在这种情况下,如何根据无条件的语言模型$p(\boldsymbol{x})$和$\boldsymbol{x},\boldsymbol{c}$之间的联系来做有条件的文本生成,便成为了我们的研究对象。我们可以称之为“受限文本生成(Constrained Text Generation)”
举例来说,用关键词造句,那么$\boldsymbol{c}$就是关键词的集合,我们可以定义示性函数:
\begin{equation}\chi(\boldsymbol{x}, \boldsymbol{c})=\left\{\begin{aligned}&1,\,\,\text{如果}\boldsymbol{x}\text{包含关键词集}\boldsymbol{c} \\
&0,\,\,\text{如果}\boldsymbol{x}\text{不包含关键词集}\boldsymbol{c}\end{aligned}\right.
\end{equation}
继而定义
\begin{equation}\rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\chi(\boldsymbol{x}, \boldsymbol{c})\end{equation}
$p(\boldsymbol{x})$保证了生成句子的流畅性,$\chi(\boldsymbol{x}, \boldsymbol{c})$保证了生成句子包含所要求的关键词,那么问题就可以变成最大化操作$\mathop{\text{argmax}}\limits_{\boldsymbol{x}} \rho(\boldsymbol{x}, \boldsymbol{c})$或采样操作$\boldsymbol{x}\sim \rho(\boldsymbol{x}, \boldsymbol{c})$。当然,这里的$\rho(\boldsymbol{x}, \boldsymbol{c})$还不是概率分布,要完成归一化后才是真正的概率分布:
\begin{equation}\frac{\rho(\boldsymbol{x}, \boldsymbol{c})}{\sum\limits_{\boldsymbol{x}}\rho(\boldsymbol{x}, \boldsymbol{c})} = \frac{p(\boldsymbol{x})\chi(\boldsymbol{x}, \boldsymbol{c})}{\sum\limits_{\boldsymbol{x}}p(\boldsymbol{x})\chi(\boldsymbol{x}, \boldsymbol{c})}\end{equation}
但分母通常是难以显式计算出来的。那也就是说,我们对待采样分布也只了解到它正比于某个函数$\rho(\boldsymbol{x}, \boldsymbol{c})$,而不知道精确的分布表达式。
类似的例子并不少,比如说文本摘要。什么是文本摘要呢?其实就是用更少的文字$\boldsymbol{x}$尽可能表达出跟原文$\boldsymbol{c}$一样的意思,这时候我们可以定义:
\begin{equation}\rho(\boldsymbol{x}, \boldsymbol{c}) = p(\boldsymbol{x})\cdot \text{sim}(\boldsymbol{x}, \boldsymbol{c})\cdot \chi(\boldsymbol{x}, \boldsymbol{c})\end{equation}
这里的$\text{sim}(\boldsymbol{x}, \boldsymbol{c})$是某个文本相似度函数,而$\chi(\boldsymbol{x}, \boldsymbol{c})$是长度的示性函数,即$\boldsymbol{x}$的长度在某个范围(可能依赖于$\boldsymbol{c}$)内,它就为1,否则为0。此时我们同样得到了一个未归一化的概率分布$\rho(\boldsymbol{x}, \boldsymbol{c})$,需要最大化它或者从它里边采样。很明显,这个目标就意味着我们要得到一段跟原文语义尽可能相似的、长度满足一定约束的文字,这不就是摘要的存在意义吗?所以,这套思路的核心出发点就在于:我们要把自己要生成的目标定量地捋清楚,然后再去执行下一步操作。
困难分析 #
所以,抛开前面的背景不说,现在我们面临的问题就是有一个分布$p(\boldsymbol{x})$,我们只知道$p(\boldsymbol{x})\propto \rho(\boldsymbol{x})$,即
\begin{equation}p(\boldsymbol{x}) = \frac{\rho(\boldsymbol{x})}{\sum\limits_{\boldsymbol{x}} \rho(\boldsymbol{x})}\end{equation}
中的分母我们无法显式计算出来。在本系列文章中,$\boldsymbol{x}$代表文本,即一个离散元素的序列,但后面的推论同样也适用于$\boldsymbol{x}$是连续型向量的场景。现在我们要搜索最大位置$\mathop{\text{argmax}}\limits_{\boldsymbol{x}} p(\boldsymbol{x})$或进行采样$\boldsymbol{x}\sim p(\boldsymbol{x})$,后面我们将会看到,搜索最大值其实也可以看成是采样的特例,因此我们主要关心采样方式。
前面说了,之所以需要设计一些特别的算法来完成采样,是因为直接从$p(\boldsymbol{x})$中采样是困难的,而我们需要理解采样的困难所在,才能真正理解后面所设计的采样算法的关键之处。困难在哪?如果$\boldsymbol{x}$的候选值空间不大,哪怕有100万个候选值,我们都可以把每个$p(\boldsymbol{x})$都算出来,然后按照普通的类别采样来进行。然而,一般$\boldsymbol{x}$的候选值空间远远不止100万,假如$\boldsymbol{x}$有10个分量,每个分量有1万个选择(对应于词表大小),那么总的排列就有$10^{40}$种了,不可能事先算好每一种排列的概率然后依概率采样。
那怎么办呢?所谓“不积硅步,无以至千里”,那就只能一步步来了,也就是说,我没法直接实现$10^{40}$选1,那我做10次“$10^4$选1”可以吗?这就对应着所谓的“自回归生成”:
\begin{equation}p(\boldsymbol{x})=p(x_1) p(x_2|x_1) p(x_3|x_1, x_2) \cdots p(x_n|x_1,\cdots,x_{n-1}) = \prod_{t=1}^n p(x_t|\boldsymbol{x}_{< t})\end{equation}
这样我们就可以先从$p(x_1)$采样一个$x_1$,然后从$p(x_2|x_1)$中采样一个$x_2$,依此递归了。但是,自回归生成只是对应于无条件的语言模型或者是有监督训练的Seq2Seq模型,而如果希望像前面举的例子那样,往无条件语言模型的生成过程中加点约束,那么对应出来的模型就不再是自回归的了,也就无法按照这样的递归采样了。
所以,我们就不得不需要后面介绍的各种采样算法了,它也是“一步步来”的思想,但所使用的分布形式更加广泛一些。
重要采样 #
在《从采样看优化:可导优化与不可导优化的统一视角》、《如何划分一个跟测试集更接近的验证集?》等文章里,我们介绍过“重要性采样”的概念,即如果我们想估计期望$\mathbb{E}_{\boldsymbol{x}\sim p(\boldsymbol{x})}[f(\boldsymbol{x})]$,但是$p(\boldsymbol{x})$又不是易于采样的分布,那么我们可以找一个跟$p(\boldsymbol{x})$相近的、易于采样的分布$q(\boldsymbol{x})$,然后根据下述变换
\begin{equation}
\mathbb{E}_{\boldsymbol{x}\sim p(\boldsymbol{x})}[f(\boldsymbol{x})] = \sum_{\boldsymbol{x}} p(\boldsymbol{x}) f(\boldsymbol{x}) = \sum_{\boldsymbol{x}} q(\boldsymbol{x})\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x}) = \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x})\right]
\end{equation}
转化为从$q(\boldsymbol{x})$采样来算$\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x})$的期望了,也就是用$\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}$对每个样本进行加权,所以它被称为“重要性采样(Importance Sampling)”。如果只知道$p(\boldsymbol{x})\propto \rho(\boldsymbol{x})$,那么重要性采样也是可以进行的,这是因为
\begin{equation}1 = \sum_{\boldsymbol{x}} p(\boldsymbol{x}) = \sum_{\boldsymbol{x}} q(\boldsymbol{x})\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})} = \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}\right]\end{equation}
所以
\begin{equation}
\mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}f(\boldsymbol{x})\right] = \mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}\left[\frac{p(\boldsymbol{x}) / q(\boldsymbol{x})}{\mathbb{E}_{\boldsymbol{x}\sim q(\boldsymbol{x})}[p(\boldsymbol{x}) / q(\boldsymbol{x})]}f(\boldsymbol{x})\right]
\end{equation}
这样一来,我们发现上式只依赖于$p(\boldsymbol{x})$的相对值,不依赖于它的绝对值,所以把$p(\boldsymbol{x})$换成跟它成正比的$\rho(\boldsymbol{x})$也是可以的,最终简化成:
\begin{equation}
\mathbb{E}_{\boldsymbol{x}\sim p(\boldsymbol{x})}[f(\boldsymbol{x})] \approx \frac{\sum\limits_{i=1}^N \rho(\boldsymbol{x}_i) / q(\boldsymbol{x}_i) \cdot f(\boldsymbol{x}_i)}{\sum\limits_{i=1}^N
\rho(\boldsymbol{x}_i) / q(\boldsymbol{x}_i)},\quad \boldsymbol{x}_1,\cdots,\boldsymbol{x}_N\sim q(\boldsymbol{x})\end{equation}
拒绝采样 #
上一节的重要性采样实现了将复杂分布期望转化为简单分布期望,但这还不是我们的真正目的,我们要实现的是把样本从分布$p(\boldsymbol{x})$中采样出来,而不是估算它的某个期望。思想依然跟重要性采样一样,引入易于采样的分布$q(\boldsymbol{x})$,然后从中随机地筛掉某些样本,使得剩下的样本服从分布$p(\boldsymbol{x})$。
具体来说,假设有函数$\alpha(\boldsymbol{x})\in [0, 1]$,我们按照如下流程进行采样,即“拒绝采样(Rejection Sampling)”:
拒绝采样 从$q(\boldsymbol{x})$采样一个样本$\boldsymbol{x}$,从$U[0,1]$中采样一个随机数$\varepsilon$,若$\varepsilon \leq \alpha(\boldsymbol{x})$则接受该样本,否则拒绝并重新按照此流程采样。
那么,此时采样出来的$\boldsymbol{x}$真正的概率分布是什么呢?其实也不难,由于样本$\boldsymbol{x}$被保留下来的概率是$\alpha(\boldsymbol{x})$,因此它的相对概率就是$q(\boldsymbol{x})\alpha(\boldsymbol{x})$,我们只需要将它重新归一化
\begin{equation}\frac{q(\boldsymbol{x})\alpha(\boldsymbol{x})}{\sum\limits_{\boldsymbol{x}} q(\boldsymbol{x})\alpha(\boldsymbol{x})}\end{equation}
就得到拒绝采样对应的真正的概率分布了,从这个形式也可以看出,将接受率乘以一个0到1之间的数,理论上拒绝采样对应的分布是不变的。
这个过程启示我们,拒绝采样可以让我们实现从正比于$q(\boldsymbol{x})\alpha(\boldsymbol{x})$的分布中采样,那么根据$p(\boldsymbol{x})=q(\boldsymbol{x})\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}$,我们可以让$\alpha(\boldsymbol{x})=\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}$作为接受概率,来进行从$q(\boldsymbol{x})$出发的拒绝采样,结果就相当于从$p(\boldsymbol{x})$采样了。当然,还没那么简单,根据概率的归一化性质,除非$q(\boldsymbol{x})$恒等于$p(\boldsymbol{x})$,否则$\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}$不可能一直都在$[0, 1]$内。但这不要紧,只要$\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}$有上界,那么我们就可以选择一个足够大的常数$M$,使得$\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})\cdot M}\in [0, 1]$,此时以$\alpha(\boldsymbol{x})=\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})\cdot M}$为接受概率即可,刚才我们说了,乘以一个常数不会影响拒绝采样对应的分布。换句话说,也就是这个过程同样不依赖于完全精确的$p(\boldsymbol{x})$,可以将$p(\boldsymbol{x})$换成跟它成正比的$\rho(\boldsymbol{x})$。
关于接受率$\alpha(\boldsymbol{x})$,尽管理论上只要求它$\alpha(\boldsymbol{x})\in[0, 1]$就行了,但实际上还是以$\max\limits_{\boldsymbol{x}}\alpha(\boldsymbol{x}) = 1$为好,这是因为过小的接受率会导致拒绝太多(几乎来一个拒绝一个),采样效率太低,生成一个合理的样本的成本过大了。类似地,尽管理论上对$q(\boldsymbol{x})$的要求只是易于采样并且$\frac{p(\boldsymbol{x})}{q(\boldsymbol{x})}$有上界,但实际上$q(\boldsymbol{x})$与$p(\boldsymbol{x})$仍然是越相近越好,否则依然可能造成接受率过低而导致采样成本大到难以接受。所以,尽管拒绝采样看上去提供了一种几乎能从任意分布$p(\boldsymbol{x})$中进行采样的方案,但实际应用时近似分布$q(\boldsymbol{x})$的设计依然是一个不小的难题。
本文小结 #
从本文开始,我们开了个新坑,试图从离散优化的角度来完成某些文本生成任务(受限文本生成)。它通过确定一个定量的评估目标,然后通过最大化这个目标或者从中采样就可以得到我们想要的输出,而不需要标签数据监督训练新模型。在这个过程中,所要用到的工具是一些主要是采样算法,本文先介绍了其中很基本的重要性采样和拒绝采样,后面将会继续完善该系列文章,敬请大家期待。
转载到请包括本文地址:https://www.spaces.ac.cn/archives/8062
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Jan. 07, 2021). 《【搜出来的文本】⋅(一)从文本生成到搜索采样 》[Blog post]. Retrieved from https://www.spaces.ac.cn/archives/8062
@online{kexuefm-8062,
title={【搜出来的文本】⋅(一)从文本生成到搜索采样},
author={苏剑林},
year={2021},
month={Jan},
url={\url{https://www.spaces.ac.cn/archives/8062}},
}
January 7th, 2021
苏神 你好 请问这种基于离散优化的方法比基于梯度下降的方法的优势在哪里呢?
你问这个问题,说明你可能还没理解“明确目标”这一节说的内容。这两者说的不是一回事,不是相互替代品,所以不存在什么优势的说法。
一般的文本生成,是把它建模为一个映射关系$y=f_{\theta}(x)$,需要用标签数据进行训练,用梯度下降优化$\theta$,训练完成之后,输入一个$x$,就能得到对应的$y$。这里的文本生成,是直接写出一个目标$\rho(x, y)$,这个目标是人为设计的,不需要标签数据训练的(但可能需要无标签数据训练),然后我们让$y = \mathop{\arg\max}_y \rho(x, y)$(或者采样),这个$\mathop{\arg\max}$操作需要离散优化(因为$y$是离散的)。
梯度下降的对象是模型参数,离散优化的对象就是我们的想要的输出。
两者的区别是:前者其实你可以不知道你要干什么,但是你有很多标签数据,我用标签数据去训练模型,这个过程哪怕完全不了解任务背景的人也可以去做,反正都是套模型去训练,管它$x,y$分别代表什么含义呢;后者需要你了解你这个任务的目的,然后去量化这个目标,然后直接去找出这个目的的最优解,而不需要监督数据。
比如摘要任务,对于前者来说,你需要给我一堆$(\text{原文},\text{摘要})$的数据对,然后我去训练一个Seq2Seq模型;对于后者来说,我不需要数据对,因为我知道摘要就是“用更短的话描述出跟原文最相似的内容”,你看有个“更短”、“最相似”,“更”、“最”说明这是可以量化的,量化之后我就可以去找它的最优解了,找出它的最优解就是我们想要的输出。
我的理解是梯度下降优化是在优化模型的参数。而这里的离散优化是在求解$argmax$, 这个过程中其实并不涉及参数训练(不包含梯度回传)。苏神有没有可能把这种离散优化(采样过程)应用神经网络训练(梯度下降)中呢?有些时候我们也想在模型中使用$argmax$,但苦于$argmax$ 不可导,无法直接使用。需要专门设计模块解决这个问题,比如您博客中的VQ-VAE,或者Gumbel Softmax等。我很好奇,这种离散的采样的过程怎么与神经网络训练相结合呢?
1、梯度下降也可以理解为在求解$\mathop{\arg\max}$,所以是不是求解$\mathop{\arg\max}$不是区别;
2、采样的过程不用训练,采样的目标需要用到的东西可以训练,比如第三篇需要一个MLM模型,后面的例子一般需要一个单向语言模型,这些都可以事先训练好。
January 8th, 2021
苏神你好啊,这个方向耳目一新,膜拜一下。
$p(x)$确保了流畅度,相当于一个语言模型?
$\chi(x, y)$确保的是一个目标约束。
对于这句“往无条件语言模型的生成过程中加点约束,那么对应出来的模型就不再是自回归的了,也就无法按照这样的递归采样了”不是很理解,为什么加了约束就不能递归采样了?
像很多可控生成,比如PPLM等也是在后处理的时候改变$p(x)$分布,这种跟$\chi(x, y)$的约束有什么不一样的地方么?
PPLM新增的限制是自回归的,所以合起来也是自回归的。但是一般的$\chi(x,y),\text{sim}(x,y)$都不一定是自回归的,所以合起来就不是自回归的了。
其实最关键的问题是,自回归必须从单方向生成(从左往右),可控性会差很多。后面我们将会看到,用离散优化的思路,将会突破这个单方向生成的限制,相当于允许对结果不断修改润色,从而有更大的灵活性。
噢,很cool,期待。
January 9th, 2021
大佬,nlp领域有类似于写同义句之类的方向吗,就是输入一个句子或者文本,输出一个不完全一样(一两个单词不一样,或者完全不一样)的但是语义一样的句子或文本,用无监督的方法
SimBERT是这样的一个模型,之前有文章介绍过,不过SimBERT算是监督训练的。无监督的相似、同义并不好定义。
楼上应该是想找一个文本泛化工具吧?如果是,可以了解下nlpcda,链接是https://github.com/425776024/nlpcda。其中,第九种方案【使用simbert做生成式相似句生成】或许可以帮到你,根本原理是苏神去年提供的方案:https://spaces.ac.cn/archives/7427。
January 11th, 2021
10s快速浏览了一下,我们之前做过CGMH,可能有点类似。https://arxiv.org/abs/1811.10996,后续也有大量其他人的类似工作。
感谢作者大佬捧场,这个系列会慢慢展开,后面也会介绍到贵作CGMH,最后则补充一些我们自己的工作~
January 25th, 2021
苏神, 拒绝采样那里是不是应该$\alpha (x) > \epsilon$
为什么呢?
苏神, 我是这样想的:
从q中采样x的概率是$q(x)$, 然后从U[0, 1]中采样$\epsilon$的概率密度是1, $\epsilon$要掉到$[0, \alpha(x)]$里面接受该样本x, 积分的概率才是$\alpha(x)$, 否则是$1-\alpha(x)$了.
不知道是不是哪里想的有问题问题
噢噢,是我想反了,抱歉抱歉。我一开始老想到拒绝率去了,全部都改过来了。
感谢苏神的博客, 每次看都让我对NLP模型的理解更深了一层
February 4th, 2021
关于拒绝采样 目的是把样本从分布p(x)中采样出来 引入q(x)是一个自己选的好算的且已知的分布,到这里都没问题 ; 如果α是接受率 , 我们需要M * q(x)逼近p(x) (这样接受率高) , 但是我们对p(x)是不知道他的信息的 ,又如何去选择合适的M呢
在拒绝采样的场景中,我们至少需要知道跟它成正比的$\rho(x)$的表达式,以及需要知道$q(x)$的精确表达式,在这个前提下,找一个$M$使得$\frac{\rho(\boldsymbol{x})}{q(\boldsymbol{x})\cdot M}$恒不大于1,理论上是可以做到的。
是的理论上可以做到,我的意思是:就像选择一个合适的接受率α是比较困难的(过小的接受率会导致拒绝太多) 和这个道理一样 选择合适的M也是困难的,即仍然会导致接受率 p(x)/q(x) * M 难以选到一个合适的;也就是仍然可能导致新的接受率过大或者过小
所以这种变通之法的本质是把一个难解决的问题转化成了另一个难解决的问题;不知道我的这个理解是否正确,谢谢苏神指点
我似乎看不懂你关注的点。理论上$M$的最优解是$\max\limits_x \frac{\rho(\boldsymbol{x})}{q(\boldsymbol{x})}$,你是说这个最大值的求解会有困难吗?理论上高维空间中的全局最大值确实是很困难的,但至少它已经是一个完全定量化的目标了。而且未必要求出它的最大值,只需要求一个差不多可用的上界就够了。
总的来说,高维空间中进行拒绝采样是很困难的,但困难的来源并不是因为$M$难求,哪怕我们求出了$M=\max\limits_x \frac{\rho(\boldsymbol{x})}{q(\boldsymbol{x})}$,那也只是在某些点上接受率为1,其他很多点上接受率可能还是很低,这才是它困难的问题所在。
是的我就是这个意思 , 谢谢苏神指点~
另外我认为 "理论上M的最优解是maxρ(x)/q(x)" 好像不是很合适?
因为M的目的不是越大越好,而是"越合适越好"; 这也正好契合了苏神后面说的"哪怕我们求出了M=maxρ(x)/q(x),那也只是在某些点上接受率为1,其他很多点上接受率可能还是很低"
总之非常感谢苏神的分享,受益匪浅
$M$肯定不是越大越好啊,但至少要大于等于$\max\limits_x \frac{\rho(\boldsymbol{x})}{q(\boldsymbol{x})}$啊,只有这样$\alpha(x)$才能不超过1。
明白了 感谢苏神指点~