ACTA Scientiarum Naturalium Universitatis Pekinensis
A Hybrid Optimization Framework Fusing Word- and Sentence-level Information for Extractive Summarization
LIN Xinyi1,2, YAN Rui1,†, ZHAO Dongyan1
1. Institute of Computer Science and Technology, Peking University, Beijing 100080; 2. School of Electronic Engineering and Computer Science, Peking University, Beijing 100871; † Corresponding author, E-mail: ruiyan@pku.edu.cn
Abstract In order to fuse word-level and sentence-level information from different semantic spaces, the authors propose a hybrid optimization framework to optimize word-level information while simultaneously incorporate sentence-level information as constraints. The optimization is conducted by iterative unit substitutions. The performance on DUC benchmark datasets demonstrates the effectiveness of proposed framework in terms of ROUGE evaluation. Key words extractive summarization; word-level information; sentence-level information; hybrid optimization framework
多文档摘要生成工作是自然语言处理领域的核心任务之一, 十几年来吸引了众多的研究者投入该任务中, 其目标是利用计算机, 自动为一组文档生成一段限定字数的精简、浓缩的摘要, 辅助读者快速领悟文档集合的要点, 捕捉重要信息。
完成这个任务的一个很自然的想法, 是将文档拆解成一组语义单元, 然后根据预设的标准, 从中抽取单元集合的子集进行重组, 形成摘要。组成文档最常用的语义单元是句子和单词, 所以摘要工作通常也是基于这两个粒度。目前, 大多数研究主要关注句子层级, 例如质心法(centroid-based method)
(MEAD[1]和 NEATS[2])、基于图排序法(graph-based method) (Pagerank[3–4], HITS[5] 和 Clustercmrw[6])和子模方法 (submodular functions)[7]。基于单词级别的方法主要是整数线性规划法(integer linear programming process)[8]。Gillick等[8]将单词视为赋有不同权重的语义单元, 将摘要工作抽象为一个整数线性规划问题, 在长度限制内, 抽取句子集合形成摘要, 使之包含的单词总权重最大。然而, 研究者很少将句子级别和单词级别的信息进行融合, 主要是因为单词和句子来自于不同的语义空间, 在大部
[9]分情况下, 这两个空间非线性相关。Xie 等 在融
合句子和单词信息时, 对句子和单词的分数分别进行归一化, 然后将两个分数进行线性叠加。尽管这个方法效果欠佳, 但不失为融合词句信息的一个简单直接的解决思路。本文提出一个混合词层级和句层级信息的迭代优化摘要框架。之所以要融合词层级和句层级的信息, 是因为词层级和句层级从不同角度满足了摘要的需求, 并且功能存在互补。句子拥有完整的语法结构, 其中大部分字词的作用是连接, 使之形成语法上可读的句子, 而与语义内容无关。相比之下,单词粒度小, 表达的含义更凝练、精准, 以单词为粒度能够更加充分地利用有限的摘要长度, 包含更多的重要文档信息。虽然单词体积小, 以它为粒度能够提高摘要的有效信息率, 但摘要还需考虑其可读性、连续性和逻辑完整性。简单地将一个个单词实体拼接起来, 无法形成可读的文段。句子的优势在于, 它是更完整的语义单元, 包含必需的语法结构、语义连接以及实体间的逻辑关系, 保证了可读性, 并且保留了一定的连续性、时间的顺序性以及逻辑的完整性。因此, 更优的策略应该是结合两个层级的优势, 在抽取重要句子的同时, 使之包含尽可能多的重要单词。相比于直接将句子和单词的权重进行线性组合的简单方法, 我们考虑到两个语义空间的数学关系不明确, 为避免直接刻画句子层级和单词层级信息的关系, 使用类似双任务的主任务和副任务框架来实现句子层级和单词层级信息的融合。本文将任务抽象为带依赖关系的背包问题, 用迭代框架对该优化问题进行求解。一方面, 由于重要程度不同, 每个单词有不同的权重得分。任务的主要目标是在长度限制内, 迭代更新选择的句子集合, 使之包含单词的总得分最高。另一方面, 句子作为更高层次的语义单元, 也有其句子层级的得分, 其特征包括句子的重要性、句子组合的多样性和信息覆盖率等,将这些特征的得分作为迭代替换句子单元时的约束条件。该框架在寻求单词层级信息的最优解的同时, 保证了句子层级信息的不断优化, 最终得到一个句子层级得分尽可能高的单词层级上的近似最优解。具体而言, 我们通过最大化单词级别的分数获得一个初始摘要, 这个初始摘要虽然是单词层级上的近似最优解, 但它在句子层级上的分数可能较低,所以在满足长度限制的约束下, 迭代地进行句子集合的替换, 使之满足句子层级评分的约束条件, 并 且保证该替换得到的摘要在单词级别上表现出与最优解相差不超过一个阈值, 最终获得一个单词级别和句子级别表现双高的平衡点。实验结果表明, 该框架在标准数据集DUC上使用 ROUGE[10]进行评测, 获得明显的效果提升。
1融合词句层级信息的迭代优化框架1.1词层级优化
如果将单词视为原子单元, 句子则是由多个单词构成的有序元组。首先将任务刻画为单词层级上得分最大化的一个最优问题的求解, 最终目标是选取句子集合构成摘要, 使得摘要中的单词总分最高。我们虽然以句子为单元进行抽取, 但只保证了摘要的可读性, 优化目标还是在于使得单词得分最大化, 即句子层面信息依旧未考虑进来。
为了获取单词的得分, 我们选用最经典的单词评分策略 tf-isf 方法, 为每个单词进行打分[11]。tf 表示单词在句子中的词频; isf表示逆向句子频率, 是出现该单词的句子占所有句子的比例的倒数再取对数值。给定一个多次出现的单词w (实验中, 筛去
i出现次数小于 5 的单词, 以省去不必要的处理), 将其对应所有句子的 tf-isf 分数进行求和, 并取平均值作为该单词的得分, 记做 (wi)。
通常, 基于单词的摘要有一个基本的假设, 即单词间是相互独立的, 所以我们可以简单地将单词的得分直接相加, 用来评价一个摘要在单词级别上的质量。
其中, S 是摘要, O(S)是该摘要在单词级别上的得分。为了避免冗余, 摘要中重复出现的单词不进行重复计分。我们的目标是抽取包含尽可能多重要单词的句子, 使得O(S)最大化。我们通过贪心法获得argmax O(S)的近似解, 将其作为迭代优化框架的初始摘要。
1.2 句层级优化
通过贪心法求得的近似解只在单词层级上获得近似最优, 却没有考虑句子层级的信息。句子的特征对于形成一篇逻辑关系完整合理、信息覆盖率高、冗余度低的摘要十分关键[7]。为了加强摘要在句子层级上的表现, 需要为摘要设定句子层级上优化的方向。
首先, 我们考虑句子层级上最突出的几个特征,