基于遗传算法的非监督摘要提取*

王 涛，范晓波，胥小波

（1.四川省科学技术信息研究所，四川 成都 610000；2.中国电子科技网络信息安全有限公司，四川 成都 610000）

0 引言

自动生成文本摘要是自然语言处理（Natural Language Processing）领域中一项比较复杂但意义重大的工作。所谓生成文本摘要就是指利用计算机自动地从原始文献中提取重要句子组成文章摘要的过程。随着Web 2.0 的迅猛发展，各种用户原创内容爆炸式增长，使得有价值信息的获取愈发困难。自动生成文本摘要从海量文本中抽取出最重要的语句，可以有效帮助用户花很少的代价获取文档的主要信息。

大体而言，自动摘要可分为基于抽取的自动摘要和基于抽象的自动摘要。基于抽取的自动摘要是指选择输入文档的相关句子并将它们连接起来形成摘要。而基于抽象的方法是指采用新的句子来生成保持原文意思的摘要。基于抽象的自动摘要受制于自然语言处理技术的瓶颈，实现相对困难，因此目前主要的研究和应用集中在基于抽取的自动摘要[1]。根据摘要提取的技术途径不同，抽取的自动摘要可分为基于特征的方法[2-3]、基于图的方法[4-5]和基于神经网络的方法[6-9]。基于特征的方法即评估每个句子的特征，然后评价它的重要性，并输出重要性靠前的句子；基于图的方法（如TextRank[5]）从文档中构建图形，其中图的节点为文档中的句子，而边为句子之间的相似度，然后通过考虑节点之间的关系选取图中重要的节点（句子）。受益于深度学习在自然语言处理领域的广泛运用，近年来提出一些基于深度学习的摘要提取方法，如seq2seq网络[8]、pointer-generator 网络[9]等。然而，基于深度学习的方法需要大量有监督的训练数据，在实际运用中依赖人工构建的训练样本。

子集选择算法是无监督自动文档摘要的有效方法，首先将摘要抽取建模成子集选择问题，即将原文看成一个由句子构成的集合，而摘要为从集合中精心挑选的子集。特别地，选择的摘要子集应使得某个效益函数最大化。然而，子集选择是非确定性多项式（Nondeterministic Polynomial，NP）完全的[10]。当前文献普遍采用贪婪式算法求解。

不同于当前文献的一般方法，本文提出一种基于遗传算法（Genetic Algorithm，GA）的非监督摘要抽取方法。遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，发现在求解摘要提取问题中有独特的优势。该方法将每条候选摘要编码成0-1 序列。除了能搜索到效益函数的最优解之外，传统的遗传算法在变异过程中随机选择某个基因进行突变。考虑到句子位置影响句子的重要性，如出现在段首、段中和段末的句子重要性不同，在遗传算法变异选择过程中，将以更高的概率选择上述特定位置的句子。

1 无监督摘要抽取模型

本节将说明如何使用子集选择模型来定义自动文档摘要。为了便于描述，本文将一篇特定文档定义为句子的有序集合。不失一般性，假设原文共有n条句子，记si表示第i条句子，摘要提取可以视为从集合S={s1,…,sn}中提取子集T⊂S来作为原文的摘要。给定某个效益函数，子集T的选取应该使得效益函数最大化。令fs表示定义在集合S上的效益函数，则摘要抽取模型可表示为求解如下优化表达式：

式中，优化条件|T|≤k表示最多从原文中抽取k条句子作为摘要。

怎么选取效益函数呢？一种直观的理解是给定|T|≤k约束下，子集中蕴含的“信息”应越多越好。通常来说，一段话包含的信息量要多于其段落中某些句子组成的子集的信息量。令T1、T2均为T的子集且T1⊂T2，则应有fs(T1)＜fs(T2)，即集合的效益函数值应大于其子集的效益函数值。

当前文献中已经给出了几种效益函数定义形式。

1.1 成对（Pairwise）效益函数

第一个子集评分函数是由Lin 和Bilme[11]提出的。基于成对句子相似度模型，成对效益函数使用等式（2）对摘要T进行评分：

式中，σ(i,j)≥0 表示句子i和j之间的相似性度量（如句子TFIDF 的余弦相似性）。式（2）中，等式右边的第一项是衡量摘要T中的句子与S中的其他句子的相似程度；第二项为T内部的各个句子之间的相似程度。λ≥0 是一个标量参数，用来权衡第一项和第二项。最大化上述效益函数可以使得T中的句子与S中的其他句子相似度较高，而其内部相似度较低，即增加所选摘要与其他句子的相似性，同时最小化摘要中蕴含的重复信息，从而实现有效的信息抽取。

1.2 覆盖效益函数

覆盖效益函数基于词覆盖[12]的概念。该概念首先被提出用于多文档检索，随后被引入用来衡量自动文档摘要的质量。在词覆盖的定义中，文档中的每个词v都具备一个权重ω(v)用来表示该词在文档中的重要程度。给定一个摘要T，如果T中某条句子含有词v，则称摘要T覆盖词v，而摘要的得分就是其覆盖的所有词的权重之和：

式中，U(T)表示T中所有词的并集。最大化该效益函数属于著名的最大覆盖问题，即选择摘要使得其能最大化覆盖原文档中所有重要的词。在简单情况下，类似成对效益函数，式（3）中的权重函数ω(v)可以为词语的TFIDF 值。

值得注意的是，不管是哪一种效益函数，其本质都是以尽可能少的文本涵盖文档信息，区别仅是信息的描述角度不同。本文提出的遗传算法抽取文本摘要方法可适用于以上任何一种效益函数。

2 基于改进遗传算法的摘要抽取

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。将每个可行解编码成染色体，染色体被表示为一组定义个体的参数（特征）。为了选择最佳的个体，使用了一个适应度函数。适应度函数的结果是表示解的质量的适应度值。适应度值越高，解决方案的质量越高。根据质量选择最佳个体，以产生所谓的交配池，其中质量较高的个体在交配池中被选择的概率较高。

遗传算法的一般流程是模拟自然进化过程进行循环迭代，直至收敛或满足最大迭代次数。每一次循环包括：评估每条染色体所对应个体的适应度；遵照“适应度越高，选择概率越大”的原则，从种群中选择两个个体作为父方和母方（精英保留策略）；抽取父母双方的染色体进行交叉，产生子代；对子代的染色体进行变异。为了将遗传算法应用于文本摘要，本文从如下几个方面进行阐述。

（1）候选解编码。在基于遗传算法进行摘要抽取时，由于其本质是从集合S={s1,…,sn}中提取子集T⊂S作为原文的摘要，因此将每一个可行解编码成n维的0/1 向量，其中1 代表选中对应位置的句子作为摘要，而0 表示未选中。

（2）适应度函数。适应度函数表达一个候选解的好坏，其中好的解应该以较大的概率在下一次迭代中保存。特别地，最好的精英解应保证能进入下一代；相反，较差的解会以较大的概率淘汰。由于摘要提取的目的是使fs(T)最大化，因此可以简单地将目标函数fs(T)设为适应度函数。

（3）交叉算子。交叉算子根据交叉率将种群中的两个个体（即父方和母方）随机地交换某些基因并产生新的基因组合，期望将有益基因组合在一起。由于将个体编码成n维的0/1 向量，通常分别从父方的位字符串和母方对应的位字符串进行随机交换。在摘要提取中，摘要长度远小于原文，即在个体编码中1 的个数远远小于0 的个数。为了加快算法的收敛速度，本文只在父母双方基因的“差异处”进行随机交换。这里的差异处指的是父母在该位置的编码不一样，对于父母双方a、b，其差异处为集合{i,ai,xor bi=1}，其中xor表示异或操作。

（4）变异。对于任意一个个体，采用随机0/1突变的方式模拟个体变异。

以上是采用一般流程的遗传算法进行非监督摘要提取。然而，在算法迭代产生新种群的过程中，候选个体从父母双方随机选择基因，且变异位置随机，忽略了中文写作习惯的影响，如起始句、点题句等句子的重要性比其他句子高，本文称之为重点句子。研究表明，在人工摘要中，选取段首句作为摘要的比例高达85%，而选取段尾句作为摘要的比例接近7%[13]。针对该问题，本文对上述通用的遗传算法进行改进，以更适用于非监督摘要提取。充分考虑句子位置、点题句等情况对节点权重的影响，将适应度函数修改为fs(T)+βgs(T)。其中，gs(T)衡量段首句和段尾句的重要性，一种最简单的方式是令段首和段尾为1，其他为0；β用来控制gs(T)在适应度函数中的权重。同时，为了加快遗传算法的收敛速度，在交叉操作中以更高的概率选择父母双方中处于重点句位置的句子。

综上所述，本文提出的基于改进遗传算法的摘要抽取算法流程如下：

1.输入原始文档；

2.采用编码方案进行编码并初始化种群；

3.采用适应度函数fs(T)+βgs(T)评估种群中个体适应度；

4.采用精英保留策略的选择方式进行个体选择；

5.对于选择的个体采用交叉、变异方案进行交叉、变异操作；

6.重复步骤3～步骤5，直到满足最大迭代次数；

7.输出最后一次迭代的最佳个体，而个体中状态为1 对应的句子集合即文档的摘要。

3 实验结果与分析

采用公开的中文短文本摘要数据集（https://www.jianshu.com/p/f98deb85e0ff）验证自动摘要算法的性能。该数据集来源于新浪微博主流媒体发布的微博，共679 898 条数据，每条数据均包含源博文和参考摘要。为了采用算法进行摘要提取，首先进行数据预处理。具体步骤为：

（1）去除实验噪声，即去除对提取摘要无明显影响的图片、表格、特殊符号等计算机语言不易识别的形式；

（2）文档分割，将文档分割为句子形成句子集合，再对这些句子进行分词、去除停用词，得到由词项构成的句子集合；

（3）向量化，本文的摘要提取框架可适用于不同的效益函数fs，不失一般性，考虑式（2）所示的成对效益函数。

实验首先分析了遗传算法的收敛速度。算法的收敛速度会影响其在实际使用中的摘要抽取速度。图1 显示了遗传算法在测试集中目标函数随迭代次数的变化趋势。由图1 可见，一般在迭代20 次后，算法就可达到收敛状态。

图1 目标函数随迭代次数变化趋势

如前所述，本文在一般的遗传算法的基础上对中文语言的特点进行一些改进。由于起始句、点题句等句子的重要性比其他句子高，在种群迭代过程中需充分考虑段首句和段尾句对节点权重的影响。表1 展示了改进前和改进后的遗传算法摘要抽取的一个示例，显然该示例中改进后抽取的摘要更接近参考摘要。

表1 改进前和改进后的遗传算法摘要抽取示例

最后，对本文算法和其他摘要抽取算法进行实验对比。摘要质量的评价方法采用自动摘要领域广泛使用的Rouge（Recall-Oriented Understudy for Gisting Evaluation）指标[14]。Rouge 指标是一种基于召回率（Recall）和n元词（n-gram）的自动化评价方法。它的基本思想是将系统生成的自动摘要与标准摘要对比，通过统计二者之间重叠的基本单元（n元语法、词序列和词对）的数目来评价摘要的质量。Rouge-n指标（n=1、2、3、4，分别代表基于1 元词到4 元词的模型）又分为召回率、准确率和f度量，分别定义如下：

式中，Countmatch(n-gram)表示算法生成摘要和参考摘要中同时出现n-gram的个数；Count(n-gram)则表示参考摘要中出现的n-gram个数。为了简单起见，本文采用Rouge-1 指标，即Rouge 中的1 元词模型。

将本文提出的算法和文献[15]中摘要抽取方法进行比较。文献[15]采用贪婪算法的方式求解效益函数的极值问题。贪婪算法在每一次迭代中，选择使得效益函数增长最大的句子作为摘要。

贪婪式算法抽取摘要的主要流程如下：

1.输入原始文档和摘要句子长度k；

2.设S为候选摘要并初始化为空集；

3.计算当前摘要的fs(T)；

4.从原始文档中选择句子i使得fs∪i(T)-fs(T)最大化；

5.重复步骤3 和步骤4 共k次；

6.输出选择的句子作为原始文档的摘要。

实验结果如表2 所示，展示了不同的摘要抽取算法在测试集上对应指标的平均值。可见，改进后的遗传算法的召回率、准确率和f度量均优于贪婪算法。原因在于贪婪算法只是近似求解算法，不能保证能求到极值，而采用精英保留策略的遗传算法在理论上已经证明能收敛到目标函数的最大值。同时，对比一般的遗传算法和改进的遗传算法，改进遗传算法充分考虑了中文摘要中的重点句，因而具备较高的抽取精度。

表2 不同的摘要抽取算法的性能

4 结语

本文提出了一种新的基于遗传算法的非监督摘要提取算法，将每条候选摘要中的句子编码成0-1 序列。考虑到句子位置影响句子重要性，如段首、段中和段末的句子在表达意思上重要性不同，算法在目标函数中加上正则项，使得遗传算法在变异选择过程中将以更高的概率选择上述特定位置的句子。实验结果表明，相对于贪婪式非监督摘要提取算法，本文提出的方法具有较好的摘要提取性能。