权衡熵和相关度的自动摘要技术研究

罗文娟,马慧芳,何 清,史忠植

(1.中国科学院计算技术研究所,北京100190;2.中国科学院 研究生院,北京100190;3.西北师范大学数学与信息科学学院,甘肃兰州730070)

1 引言

自动摘要技术作为一种典型的文本抽取技术,是自然语言处理、信息检索、文本挖掘等文档信息处理技术的有益补充[1]。自动摘要技术兴起于20世纪60年代[2],主要目的在于帮助用户花很少的代价去获取文档的主要信息[3]。根据产生摘要目的的不同,自动摘要技术分为基于查询的摘要技术和通用摘要技术[4]。

其中,基于查询的摘要技术强调根据查询条件生成摘要,而通用摘要技术更侧重于掌握文章大意,获得文章的概要描述。另一方面,根据是否生成新的语句,自动摘要技术分为基于抽取的摘要技术和基于概括的摘要技术。基于抽取的摘要技术直接从文章中抽取完整的语句作为摘要,而基于概括的摘要技术在理解文章的基础上重新组织语句生成摘要[5]。

特别地,对于基于抽取的自动摘要技术,主要有三类不同的抽取方法：(1)自然语言理解方法(Natural Language Processing Approach);(2)知识工程方法(Knowledge Engineering Approach);(3)机器学习方法(Machine Learning Approach)。自然语言理解方法主要采用自然语言处理技术对文章理解、归纳后进行信息抽取;知识工程方法依靠人工编写抽取模式,使系统能处理特定知识领域的信息抽取问题。机器学习方法利用机器学习技术通过训练文本来进行摘要预测[1]。在本文中,我们主要采用机器学习方法从文档中抽取句子进而生成通用摘要。

一般而言,用于文档摘要技术的机器学习方法分为有监督和无监督两大类[6]。典型的无监督自动摘要技术如潜在语义分析(Latent Semantic Analysis)[7]、非负矩阵分解(Non-negative Matrix Factorizatoin)[8]通过对文档词频矩阵的分解得到文档更简练的表达方式进而抽取摘要。此外,无监督自动摘要技术还包括基于图的排序算法,如 HITS[9]、PageRank[10]以及Manifold-Ranking[11]等。此类算法从图的角度理解文档,采用点表示文档中的句子,采用边描述句子之间的相似度,最后运用特定的排序算法对句子进行排序进而抽取摘要[10]。

有监督自动摘要技术采取特征向量表示句子,把摘要抽取问题看作分类或回归问题,通过有监督的机器学习方法学习文档,生成摘要预测模型[12]。因此,如何从句子中抽取有利于摘要生成的启发式特征,成为有监督自动摘要技术发展的一个难题。

我们认为,高质量的文档摘要应该满足以下两点要求：(1)紧凑——文档摘要应该是原始文档的无冗余信息抽取;(2)高覆盖率——尽可能多地覆盖原始文档涉及的主题,这保证生成的文档摘尽量少的丢失信息。特别地,我们认为紧凑是句子之间相关关系的一种度量,而覆盖率是句子自身信息含量的一种度量。我们的目的在于生成最大限度覆盖文档所有主题的简约摘要。不难发现,为扩大摘要的覆盖率,增加摘要信息含量的同时可能带来信息的冗余,而为了获得简约摘要又有可能以降低覆盖率为代价。故而,高质量的摘要是紧凑性和覆盖率的完美权衡。

在本文中,我们定义了熵用以度量句子自身的覆盖率,定义了相关度用以度量句子之间的相关关系。具体地,我们定义了绝对熵、平均熵、TFISF(Term Frequency-Inverse Sentence Frequency)熵、平均TFISF熵和相对熵以度量文档的覆盖率;前向、后向和对称相关度以度量文档的紧凑性。我们采用线性回归和 ELM(Extreme Learning Machine)回归对上述特征及特征组合的效果进行了系统的实验,单文档摘要和多文档摘要的实验结果表明权衡熵和相关度能有效地提高摘要的质量。

本文的结构如下：第2节给出各种特征抽取的定义和计算公式;第3节给出问题的形式化定义和基于回归的有监督摘要技术的相关算法;第4节给出实验结果用以验证特征抽取的有效性;第5节对整篇文章进行了总结。

2 特征抽取

有监督的自动摘要技术通过把语句表示成特征向量,运用机器学习方法选择句子作为文档摘要。在本文中,除了熵和相关度以外,我们还采用到的其他典型的句子特征[7]包括：句子位置、句子长度、句子的似然值、句子主题词个数、句子中低频词的个数、句子中两项关键词个数以及句子和其他句子共有的词数。

2.1 熵

为度量句子本身的信息含量,我们引入信息论中的熵用以度量句子的覆盖率。特别地,根据句子词频向量矩阵的不同表示,我们定义了以下五种熵。

2.1.1 绝对熵

由于词频向量中非零词频多为1,故而较长的句子对应较大的绝对熵。该特征会倾向于选择较长的句子作为摘要。

2.1.2 平均熵

为了减少绝对熵对长句的倾向,我们提出平均熵,它是对绝对熵的平均,它的计算公式如下：

由上式可知,平均熵加入了对句子长度的惩罚,会倾向于选择较短的句子作为摘要。

假设句子xi长度为n,句中单词词频均为1,代入绝对熵的计算公式,可得E(xi)=log(n);代入平均熵的计算公式,可得E(xi)=log(n)/n。不难看出,当 n＞e时,平均熵为句子长度的减函数,故而相较于绝对熵,平均熵引入对句子长度的惩罚,使得抽取的特征转为倾向于选择短句。

2.1.3 TFISF熵

TFISF熵的计算公式与绝对熵的计算公式相似,它们的区别在于绝对熵采用文档词频矩阵,而TFISF熵采用TFISF矩阵。给定文档的TFISF词频矩阵表示B,对于B中一个行向量Bi代表第i个句子,f1j表示单词j在句子i中的句子逆句子频数,fij的计算公式如下：

其中,nij代表单词j在句i中出现的次数,|S|代表文档中的句子总数,代表所有包含单词j的句子总数。

相对于绝对熵,TFISF熵对句子的词频考虑更加合理,对高频词的惩罚一定程度上考虑了句子中单词的新颖性。

2.1.4 平均TFISF熵

由TFISF熵的计算公式可以看出,相比于绝对熵,它对每一个高频的词给出一个对数惩罚项。与平均熵的想法类似,我们对TFISF熵加入一个对句子长度的惩罚项,进而得到平均TSISF熵的计算公式：

其中,pij的定义和TFISF熵中的pij一致,可以看出,这个特征在一定程度上考虑了句子中单词的新颖性,并且倾向于选择短句。

2.1.5 相对熵

我们认为句子的信息量只与它含有的不同单词个数有关,重复单词不增加句子的信息量。单词的信息量仅与它在文档中出现的概率相关。按照信息论的相关内容,单词出现的概率越小,它的信息量越高。

相对熵的计算公式与绝对熵的计算公式相似,它们的区别在于绝对熵的计算基于文档词频矩阵,而相对熵的计算则基于文档的相对词频矩阵。给定文档的相对词频表示C,对于C中的一个行向量Ci=[fi1,fi2,fi3,…,fin],Ci代表第i个句子,f1j表示单词j在句子i中的相对词频,fij的计算公式如下：

其中,nij代表单词j在句子i中出现的次数,从上述相对词频的计算公式中,我们可以看到句子的词频表示不再统计单词在句子中出现的次数,仅依赖于单词在整篇文档中的相对词频。因此,相对词频从文档全局角度对单词的信息量进行统计。相对熵的计算公式如下：

在相对熵这样一种度量框架下,一个包含大量高频词的句子会比一个包含大量低频词的句子具有更小的相对熵。注意到过量选择含有大量高频词的句子可能会导致信息冗余,而采用相对熵则有利于选择文档中比较新颖的句子。

相对熵的计算仅从句子中的单词在全文中出现的概率出发,在这种度量下,句子的长短不再直接影响到相对熵,故而,本文没有引入对平均相对熵的讨论。

2.2 相关度

为度量句子之间的紧凑关系,我们提出相关度这一概念。我们利用句子之间的相似度来统计句子的相关度,计算公式如下：

其中,x代表文档,xi和xj分别代表第i和第j个句子。R(xi)代表xi的相关度,S(xi,xj)代表xi和xj之间的相似度。特别地,根据句子之间相似度的不同计算公式,我们定义了以下三种相关度。

2.2.1 前向相关度

前向相关度是指相似度的计算基于前向图的相关度,其中,前向相似度的计算如下：

其中,Overlap(xi,xj)代表xi和xj之间共有的单词个数,length(xj)指的是xj的长度。

2.2.2 后向相关度

后向相关度是指相似度基于后向图的相关度,其中,后向相似度的计算如下：

其中,Overlap(xi,xj)和length(xi)与前向相关度中的定义一致。

2.2.3 对称相关度

对称相关度是指相似度基于对称图的相关度,其中,后向相似度的计算如下：其中,Overlap(xi,xj)和length(xi)与前向相关度中的定义一致。

从以上相关度的计算公式中,我们可以看出各种相关度的计算基于句子之间相似度,因而该特征度量的是句子之间的相关关系。

3 基于回归的自动摘要技术

在本文中,我们采用基于回归的模型对训练数据进行学习,生成的模型将用于目标摘要预测,我们选择预测得分高的句子作为最终摘要。下面先给出问题的形式化定义。

3.1 问题定义

在回归模型框架下,对每一个句子 xi,都有一个对应的yi表示xi是否属于摘要。特别地,在本文中,假定句子抽取的特征共m维,对于文档中的句子 xi形式化表示为：2,…,n},其中 xij表示句i的特征j,yi表示的是句子i的 ROUGE-2-P得分,关于ROUGE得分,我们会在实验部分给出说明。通过回归模型,我们构造以下的判别函数：

目标是使解得的φT具有最小预测误差。我们按照以下公式选择句子作为摘要：

3.2 线性回归模型

对于线性回归模型[13],假定：

使用最小二乘误差估计β,可得：

极小化最小二乘误差,对上式中的β求导,可得：

根据产生的β*,按照下式选择摘要：

3.2 ELM回归模型

ELM回归模型[14]和线性回归模型的区别在于β的求解方法不同。对于有M个隐层神经元的单隐层前馈网络(SLFNs),ELM优化目标可表示为：

其中

在上式当中,函数g(◦)的目标是尽量逼近训练数据,使得训练误差为0。在ELM 模型下,问题可以形式化为：

Hβ =Y,其中

上式的求解用到了Moore-Penrose的广义逆矩阵[14],β的一种解为：

其中,H+就是矩阵H的Moore-Penrose广义逆矩阵。最后,我们按照式(16)选择摘要。

3.3 基于回归的自动摘要算法

我们给出基于回归的自动摘要算法,假定训练文档集共有n条语句,测试文档集共有m条语句,算法流程如下：

算法1：基于回归的自动摘要算法

输入：训练文档集 X=[x1,…,xn;y1,…,yn],其中 xi是句子i的特征向量表示,yi是xi的 ROUGE得分;测试文档集 T=[t1,…,tm];摘要句数 K。

输出：文档集T的摘要集S。

步骤1：把X作为输入,对于线性回归模型,采用式(15)解得 β*,对于 ELM 回归模型,采用式(19)解得β*;

步骤2：O=β*◦T,得到文档集 T的回归得分O;

步骤3：对于 T中每篇文档,根据(16)式选择得分最高的K条句子作为摘要S。

为了权衡覆盖率和紧凑性,我们采用了不同的特征及特征组合进行了系统的实验,用以验证权衡熵和相关度对于摘要质量的影响。

4 实验

我们把特征抽取用于单文档和多文档摘要,采用的标准数据是公测数据DUC2001和DUC 2005,其中DUC2001用于测试单文档摘要,DUC2005用于测试多文档摘要。

4.1 实验设计

为了验证抽取特征的有效性,我们对所有抽取的特征都进行了实验,并且采用了线性回归和ELM回归,与没有加入抽取特征的实验结果进行对比,对抽取特征的有效性进行了验证。

同时,为了验证验证算法的有效性,对于同样的数据集,我们也实现了一些经典算法如LSA,HITS和RANDOM[12]等,分别用于单文档和多文档摘要,用于验证算法的有效性。

4.1.1 数据预处理

我们首先把文档分解成句子集合,进而进行特征抽取,并且采用了Porter Stemming[16]工具对单词进行了处理。其中,单文档摘要数据集包含147个文件合计6721条语句,多文档摘要数据集包含50个主题,1593个文件,合计48109条语句。

4.1.2 度量标准

我们采用ROUGE[15]工具包对摘要质量进行评测。在ROUGE评测标准里,有以下几项评测度量：1.ROUGE-N-R,它是以长度为N的单词串为计算单元的摘要的召回率：

2.ROUGE-N-R,它是以长度为N的单词串为计算单元的摘要的准确率：

3.ROUGE-N-F,它是 ROUGE-N-R 和 ROUGEN-R的F度量：

在上述度量公式中,N是gramn中的单词串长度,s代表摘要中的句子,y*代表用本文的方法生成的摘要,y代表文档的标准摘要。Countmatch(gramn)代表y和y*共有的长度为N的词组数,Count(gramn)代表的是相应的摘要中的长度为N的单词串总数。

4.2 实验结果

4.2.1 单文档摘要实验结果

单一特征抽取的实验结果详见表1。抽取特征组合的实验结果详见表2。本文方法与其他摘要算法的比较详见表3。

表1的结果表明对于线性回归和ELM回归,熵和相关度的加入使得各项 ROUGE得分有所变化。从表2中,我们可以看出熵和相关度的组合基本上提高了两种回归方法的ROUGE-1-R得分。这表明,权衡熵和相关度使得生成的摘要在紧凑性和覆盖率之间取得了更好的平衡。对于同一种回归方法,不同的熵和相关度组合导致不同的覆盖率和紧凑性的权衡进而影响摘要质量。此外,对于同一种特征组合,线性回归和ELM回归生成摘要质量的不同表明不同的回归方法在覆盖率和紧凑性之间的权衡也不相同。特别地,对于同一种熵,后向相关度的表现优于其他相关度,这一结果和Rada M.[9]的实验结果一致,即：在文档的图表示中,后向图表示最为有效。上述实验结果表明权衡熵和相关度能有效地提高摘要质量。

表1 线性回归和ELM回归特征抽取各项ROUGE得分——单文档摘要

表2 线性回归和ELM回归特征组合ROUGE-1-R得分——单文档摘要

表3 线性回归和ELM回归与其他算法结果比较——单文档摘要

表3给出了线性回归和ELM回归在DUC01数据集上的结果与其他典型摘要算法的结果对比,结果表明本文算法有效地提高了摘要质量。其中,Indstr-SVM[12]算法是到本文算法提出为止对于DUC01数据集表现最好的算法。相较于此算法,可以看出,权衡熵和相关度能更有效地提高摘要质量。

图1给出了各种特征组合的ROUGE-1-R得分,从图中我们可以看出,加入相关度和熵的特征组合后,ROUGE-1-R得分基本优于仅采用基本特征的ROUGE-1-R得分,这证明了权衡熵和相关度的有效性,进一步验证了高质量的摘要是覆盖率和紧凑性的完美平衡。

图1 线性回归和ELM回归特征组合ROUGE-1-R得分——单文档摘要

4.2.2 多文档摘要实验结果

单文档摘要的实验结果表明,有效地权衡熵和相关度能提高生成摘要的质量,为进一步验证这一观点,我们采用DUC2005的多文档摘要数据进行实验。相较于DUC2001的有标注摘要,DUC2005的数据缺乏对句子的标注信息,为此我们采用DUC2001的数据作为训练数据,DUC2005作为测试数据,具体实验结果详见表4。本文算法与其他经典摘要算法的比较详见表5。

表4 线性回归和ELM回归特征组合ROUGE-2-R得分——多文档摘要

表5 线性回归和ELM回归与其他算法结果比较——多文档摘要

从表4中我们可以看出,对于线性回归和ELM回归,相对于仅采用基本特征的情况,抽取的特征组合基本使得 ROUGE得分有所提高。与单文档摘要一致,对于同一种熵,后向相关度的表现也优于其他相关度。而对于同一种相关度,不同的熵对应的特征组合产生的摘要质量不尽相同。这进一步说明了不同的特征组合是对覆盖率和紧凑性的不同权衡。另外,不同的回归方法对应的最佳特征组合并不相同,证明了对熵和相关度的不同权衡会对摘要质量产生的影响不同。上述实验结果进一步验证了有效的采用特征组合对摘要的紧凑性和覆盖率进行权衡能够提高摘要质量,高质量的摘要是紧凑性和高覆盖率的最佳权衡。

表5给出了对于多文档摘要,本文提出线性回归和ELM回归与其他经典摘要算法生成摘要质量的对比结果。多文档摘要实验结果证明了权衡熵和相关度能更有效地提高摘要质量。

5 结语

本文提出了高质量摘要的两个要求——紧凑和高覆盖率,针对这两个要求,本文从文档特征抽取的角度出发,采用基于回归的有监督摘要技术,对单文档摘要和多文档摘要进行实验,研究了不同的特征组合对于摘要质量的影响。实验结果表明不同的特征组合影响的是覆盖率和紧凑性之间的权衡,进而影响生成摘要的质量。同时,与其他经典摘要算法的比较结果也证明了有效的权衡熵和相关度能够提高生成摘要的质量。

[2]仇晶.基于机器学习的文本信息抽取技术的研究[D].北京：北京理工大学博士学位论文,2009.

[3]H.P.L..The automatic creation of literature abstracts[J].IBM Journal of Research and Development,1958.

[4]Dou S.,Jian-Tao S.,Hua L.,Qiang Y.,et al.Document summmarization using conditional random fields[C]//Proceedings of International Joint Conference On Artificial Intelligence,pp.2862-2867,2007.

[5]John M.C.,Dianne P.O..Text summarization via hidden markov models[C]//Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Developmentin Information Retrieval,2001.

[6]Shafiq R.J..Automatic Annotation Techniques for Supervised and Semi-supervised Query-focused Summarization[C]//Proceedings of ACL09,2009.

[7]Karen S.J..Automatic summarizing：The state of the art[J].Information processingand M anagement,2007,43：1449-1481.

[8]Yihong G.,X.Liu.Generic text summarization using relevance measure and latent semantic analysis[C]//Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval,2001.

[8]Ju-Hong L.,Sun P.,Chan-Min A.,Daeho K..Automatic generic document summarization based on nonnegative matrix factorization[J].Information Processing and Management,45：22-34,2009.

[9]Rada M..Language independent extractive summarization[C]//Proceedings of the 20th national conference on Artificial Intelligence,Vol.4,pp.1688-1689,2005.

[10]Dou S.,QiangY.,Zheng C..Noise reduction through summariation for web-page classification[J].Information Processing and Management,42：1735-1747,2007.

[11]Xiaojun W.Jianwu Y.Jianguo X..Manifol-d-Ranking Based Topic-Focused M ulti-Document Summarization[C]//Proceedings ofIJCAI07, pp.2903-2908,2007.

[12]Liangda L.,Ke Z.,Gui-Rong X.,Hongyuan Z.,et al.Enhancing diversity,coverage and balance for summarization through structure learning[C]//Proceedings ofWWW '09,Vol.4825,pp.71-80,2009.

[13]Douglas C.M.,Elizabeth A.P.,Geoffery G V..Introduction to linear regression analysis[M].Wiley,2nd edition,1992.

[14]Guang-Bin H.,Qin-Yu Z.,Chee-Kheong S..Extreme learning machine：A new learning scheme of feedforward neural networks[C]//Proceedings of International Joint Conference on Neural Networks,vol.2,pp.985-990,2004.

[15]Chin Y.L.,Eduard H..Automatic evaluation of summaries using n-gram co-occurrence statistics[C]//Proceedings of HLT-NAACL2003,pp.71-78,2003.

[16]Martin F.P..An algorithm for suffix stripping[J].Program,1980,14(3)：130-137.