话题检测与跟踪技术的发展与研究.

话题检测与跟踪技术的发展与研究

骆卫华刘群

{luoweihua, liuqun}@ict.ac.cn

中国科学院计算技术研究所

摘要:本文介绍了话题检测与跟踪技术的由来和发展历程,并展望其应用前景,同时比较系统地介绍了现有的话题检测与跟踪系统主要采用的方法,并对其效果进行了比较。

关键词:话题检测与跟踪,向量空间模型,语言模型

Development and Analysis of Technology of Topic Detection and Tracking

Luo Weihua, Liu Qun

{luoweihua, liuqun}@ict.ac.cn

Institute of Computing Technology, Chinese Academy of Sciences

Abstract: The paper introduces the origin and history of the development of technology of topic detection and tracking, and makes remarks on its prospect. It also describes systemically the methods adopted by the current systems of topic

detection and tracking, and makes comparison among their performance.

Keywords: Topic Detection and Tracking, Vector Space Model, Language Model

1 应用背景

随着信息传播手段的进步,尤其是互联网这一新媒体的出现,我们已经摆脱了信息贫乏的桎梏,进入一个信息极度丰富的社会。在目前信息爆炸的情况下,信息的来源已不再是问题,而如何快捷准确的获取感兴趣的信息才是人们关注的主要问题。目前的各种信息检索、过滤、提取技术都是围绕这个目的展开的。由于网络信息数量太大,与一个话题相关的信息往往孤立地分散在很多不同的地方并且出现在不同的时间,仅仅通过这些孤立的信息,人们对某些事件难以做到全面的把握。一般的检索工具都是基于关键词的,返回的信息冗余度过高,很多不相关的信息仅仅是因为含有指定的关键词就被作为结果返回了,因此人们迫切地希望拥有一种工具,能够自动把相关话题的信息汇总供人查阅。话题检测与跟踪(Topic Detection and Tracking,以下简称TDT技术就是在这种情况下应运而生的。通过话题发现与跟踪,人们可以将这些分散的信息有效地汇集并组织起来,从而帮助用户发现事件的各种因素之间的相互关系,从整体上了解一个事件的全部细节以及与该事件与其它事件之间的关系。目前此方面的研究已经引起了人们的普遍兴趣。

TDT技术可以用来监控各种语言信息源,在新话题出现时发出警告,在信息安全、金融证券、行业调研等领域都有广阔的应用前景。此外,它还可以用来跟踪某个话题的来龙去

脉,进行历史性质的研究。

2发展历程

话题检测与跟踪是一项旨在依据事件对语言文本信息流进行组织、利用的研究,也是为应对信息过载问题而提出的一项应用研究。

TDT的概念最早产生于1996年,当时美国国防高级研究计划署(DARPA根据自己的需求,提出要开发一种新技术,能在没有人工干预的情况下自动判断新闻数据流的主题。1997年,研究者开始对这项技术进行初步研究,并做了一些基础工作(包括建立了一个针对TDT 研究的预研语料库。当时的研究内容包括寻找内在主题一致的片断,即给出一段连续的数据流(文本或语音,让系统判断两个事件之间的分界,而且能自动判断新事件的出现以及旧事件的再现。从1998年开始,在DARPA支持下,美国国家标准技术研究所(NIST每年都要举办话题检测与跟踪国际会议,并进行相应的系统评测。2002秋季召开了TDT的第五次会议(即TDT 2002。这个系列评测会议作为DARPA支持的TIDES(Translingual Information Detection, Extraction and Summarization,跨语言信息检测、抽取和总结项目下的两个系列会议(另一个是文本检索会议TREC之一,越来越受到人们的重视。参加该评测的机构包括著名的大学、公司和研究所,如IBM Watson研究中心、BBN公司、卡耐基-梅隆大学、马萨诸塞大学、宾州大学、马里兰大学、龙系统公司等。国内这方面的研究开展得要晚一些,1999年国立大学参加了TDT话题检测任务的评测,中文大学参加了TDT 2000的某些子任务的评测。最近北京大学和中科院计算所的研究人员也开始进行这方面的跟踪和研究。

TDT会议采用的语料是由会议组织者提供并由语言数据联盟(Linguistic Data Consortium,以下简称LDC对外发布的TDT系列语料,目前已公开的训练和测试语料包括TDT预研语料(TDT Pilot Corpus、TDT2和TDT3,这些语料都人工标注了若干话题作为标准答案。TDT2和TDT3收录的报道总量多达11万6千篇,从而很大程度上避免数据稀疏问题的影响,同时也能很好地验证算法的有效性。总的来看,TDT系列评测会议呈现两大趋势:一是努力提高信息来源的广泛性,不仅包括互联网上的文本数据,还包括来自广播、电视的语音数据;二是强调多语言的特性。从1999年开始,TDT会议引入了对汉语话题的评测,2002年又计划增加阿拉伯语的测试集。

可以看到,话题检测与跟踪和信息抽取研究一样,其建立与发展是以评测驱动的方式进行的。这种评测研究的方法具有以下一些特点:明确的形式化的研究任务、公开的训练与测试数据、公开的评测比较。它将研究置于公共的研究平台上,使得研究之间的比较更加客观,从而让研究者认清各种技术的优劣,起到正确引导研究发展方向的目的。

3 研究内容与现状

与一般的信息检索或者信息过滤不同,TDT所关心的话题不是一个大的领域(如美国的对华或者某一类事件(如恐怖活动,而是一个很具体的“事件(Event”,如美国911事件、江访美等等。为了区别于语言学上的概念,TDT评测会议对“话题”进行了定义:所谓话题(Topic,就是一个核心事件或活动以及与之直接相关的事件或活动。而一个事件(Event通常由某些原因、条件引起,发生在特定时间、地点,涉及某些对象(人或物,并可能伴随某些必然结果。通常情况下,可以简单地认为话题就是若干对某事件相

关报道的集合1。“话题检测与跟踪”则定义为“在新闻专线(Newswire 和广播新闻等来源的数据流中自动发现主题并把主题相关的内容联系在一起的技术”。例如,“俄克拉荷马城爆炸案”这个主题包括1995年美国联邦大楼被炸、悼念仪式、州和美国联邦的一系列调查、对Timothy McVeigh 的指控等等。这个定义和其它与话题有关的研究不同,那些研究主要处理信息分类问题,比如任何与爆炸有关的事件。处理分类问题需要专门的分类体系,注解起来效率低而且主观色彩浓厚。TDT 与其它研究不同之处还在于它强调新事件的发现,希望找出不在人们意料之中的或没有人知道如何去查询的事件。

TDT 是一项综合的技术,需要比较多的自然语言处理理论和技术作为支撑,因此这些测评对其进行了细化。根据不同的应用需求,TDT 评测会议把话题检测和跟踪分成五个子任务。

表一 TDT 的技术任务

TDT 会议对参评的TDT 系统定下的目标是“实现一个功能强大、用途广泛的全自动算法用以判断自然语言数据的主题结构,同时要做到与来源、媒介、领域和语言无关”。目前的成果表明切分定界的性能已经和人工相差无几,话题跟踪技术也已基本实用,但话题检测技术还有待改进。尤其值得一提的是,单一语言的测试性能并不随语种的变化而发生很大变化,对汉语话题的跟踪和检测性能与英语十分接近。

为了对不同的系统进行量化比较,TDT 会议制订了一套评测规范。每一个参评系统的性能是由误报率和漏报率加权求和的结果进行衡量,称为检测错误开销C Det ,其计算公式是:

target non FA FA target Miss Miss Det P P C P P C C -⋅⋅+⋅⋅= C Miss 和C FA 分别是漏查和误报的开销;P Miss 和P FA 分别是漏查和误报的条件概率;P target 是目标话题的先验概率,P non-target =1-P target 。C Miss 、C FA 和P target 都是预设值,作为调节漏报率和误报率在评测结果中所占比重的系数。检测开销通常被归一化为0和1之间的一个值: arg arg (min{,}Det Det Norm Miss t et FA non t et C C C P C P -=⋅⋅

一般直接用(C Det Norm 作为评价系统性能的分数。

1 显然,对这种相关性必须做一个界定,不能任由集合无限扩大。为此,TDT 会议组织者在构造TDT 语料时,对挑选出来的每个话题都定义了相关性判定规则。

2 在TDT 的评测中,“报道”定义为“论述某个话题的新闻片断,它包括两个以上

表述该事件的说明语句”。

4 主要实现方法

构造一个实用化的TDT系统是进行TDT研究的主要目的之一,也是检验现有方法优劣的基础。从参评的数量来看,话题发现和话题跟踪两个子任务最受关注。因此我们介绍的实现方法也以这两个任务为主。总体而言,要实现话题发现与跟踪功能,需要解决以下主要问题:

(1话题/报道的模型化

(2话题-报道相似度的计算

(3聚类策略

(4分类策略(阈值选择策略

整个系统的流程大致是(以话题跟踪为例:

图1 话题跟踪系统流程

针对以上问题,我们将逐一介绍一些已经被广泛采用并得到实际评测验证的方法。

4.1 话题/报道模型

要判断某个报道是否和话题相关,首先就需要解决话题和报道如何表示便于计算和比较的问题,也就是话题/报道用什么模型来表示。目前常用的模型主要有语言模型(Language Model,LM和向量空间模型(Vector Space Model,VSM。

(1语言模型

语言模型是一种概率模型。假设报道中出现的词δn各不相关,则某则报道S和话题C 相关的概率:

P(C|S =

(| ((|

(

((

n

n n

P C P C P S C

P C

P S P

δ

δ

⋅

≈∏

其中p(C是任何一则新报道和话题C相关的先验概率,p(δn|C是表示词δn在某话题C中的生成概率。p(δn|C可以表示成一个两态的混合模型,如图2所示:

图2 p(δn |C的两态模型

其中一个状态是词在该话题中所有报道的分布,另一个状态是词在整个语料中的分布。这样就构成了一个词的生成模型。计算此模型中的两个状态采用的是最大似然估计(ML ,即该话题的所有报道中δn 出现的次数除以该话题所有报道包含的总词数。因为话题语言模型很稀疏,这里必须解决未见词的0概率问题,通常采用线性插值法把背景语言模型加入进去: p ’(δn |C = α·p(δn |C+(1-α ·p(δn

一般英语状态分布和话题状态分布采用期望最大化(EM 算法估算,EM 算法能够对与话题相关的词汇赋予较高概率。

(2向量空间模型

向量空间模型是目前最简便高效的文本表示模型之一。其基本思想是:给定一自然语言文档D =D (t 1,w 1;t 2,w 2;…;t N ,w N ,其中t i 是从文档D 中选出的特征项,w i 是项的权重,1≤i ≤N 。为了简化分析,通常不考虑t k 在文档中的先后顺序并要求t k 互异(即没有重复。这时可以把t 1,t 2,…,t N 看成一个N 维的坐标系,而w 1,w 2,…,w N 为相应的坐标值,因而D (w 1,w 2,…,w N 被看成是N 维空间中的一个向量,而两个文档D 1和D 2之间的(内容相关程度常常用它们之间的相似度Sim (D 1,D 2来度量。当文档被表示为文档空间的向量,我们就可以借助于向量之间的某种距离来表示文档间的相似度。在实际的参评系统中,基本上都以词作为文本特征项。特征(词加权采用的是IR 系统中常用的tf*idf 加权策略。tf 是词在文档中的出现次数,表示词对于描述文档的重要程度,idf 是包含词的文档数的倒数,用于削弱那些在语料中频繁出现的词的重要程度,因为它们没有什么区分能力。

某些系统把词分成命名实体和内容词两类,视其对文档表达的重要度的不同赋予不同的权重。

(3中心向量模型

中心向量模型实际是向量空间模型的一种变形。每个话题用一个中心向量表示,所谓中心向量就是在此类中所有报道的向量表示的平均值。输入的报道和每个话题的中心向量相比较,选择最相似的那个话题。如果报道和话题的相似度超过一个阈值θmatch ,则认为该报道“过旧”,如果相似度超过第二个阈值θcertain ,则把新报道加入到该话题中并调整类的中心向量。如果相似度不超过θmatch ,则认为该报道为新,并创建一个新的话题,以此报道作为其中心向量。

无论选择哪种模型,一般都需要进行初始化,即消去禁用词,对于英语而言,还需要做词根还原的工作。

4.2 相似度计算

对所有的话题C 1、C 2、……C n ,要判断某一则报道S 属于哪一个话题,就需要计算报

P(S|C

道和各个话题之间的相似程度，最后把最高相似度和阈值进行比较，对于语言模型而言，就 是寻找 k 满足： k = arg max P(Ci | S i 由前面的语言模型，上式其实就等于 k = arg max ∏ i m P (δ m | Ci P (δ m P (δ m | C P (δ m 在实际应用中，常取 log 值，因此，相似度计算公式就表示为 D(S, C = log ∏ m 通常用语言模型算出的话题与话题之间的相似度不可比较， 因为单个语言模型都有各自 不同的概率特征，比如，有的话题所用的词很特殊，像“霍根班德在 200 米自由泳中击败索 普” ，而有的话题用词就很普通，像“克林顿总统访问中国” 。这样测试文档和不同话题之间 算出的分数差异很大，不能用单一的阈值进行比较，此时必须进行归一化。一种简单方法是 用分数除以文档长度。但考虑到用上面的 D(S,C算出的值基本上是一组的随机离散变 量值，如果值足够多的话，由中心极限理论，其分布近似为高斯分布，假设τ为原来的概率， µ为所有报道对某话题概率的平均值，σ是这些概率的标准方差，则新的分值可以归一化为： τ’ = (τ-µ/σ 向量空间模型和中心向量模型通常采用 cosine 公式来计算报道－话题的相似度，即求 两者的内积，则相似度计算公式可表示为 D(S,C = ∑q d ( ∑ q ( ∑ d i i 2 i 2 i 其中 qi、di 分别是报道和话题中的特征项的权值。cosine 相似度在比较两个长文档时比较有

效， 此时如果两个文档的向量维数不进行任何压缩， 系统性能最佳； 当其中一个维数降低时， 性能就会下降。因为本身已进行了长度归一化，所以 cosine 相似度不依赖于特定的特征加 权方法。 近来有些系统开始尝试用 OKAPI 公式来计算报道-话题相似度，其形式是： Ok(d1,d2;cl = ∑ w∈d 1 ∩ d 2 i 1 2 twtw (idf ( w + 2λ nw,d nw + ncl 所得结果表示文档和文档之间的距离，其中 d1,d2 是两个文档，cl 是 d1,d2 中较早出现的那 t 对其进行归一化处理使得 个文档所属的话题。w 是词 w 在文档 i 中调整后的词频， i ∑ i w w t =1 于 d 的长度，idf(w是词 w 的倒文档频率， nw 是包含词 w 的文档数目， ncl 是话题 cl 中文档的数目， nw,cl 是话题 cl 中包含词 w 的文档的数目，λ是控制词的权值中和话题相关 的那部分“动态权值”的可调参数。 文档和话题之间的分数是一个平均值： Ok(d,cl = |cl|-1 ∑ Ok (d , d d ∈cl f f ; cl

在做跟踪训练时， 把所有的训练报道分成一个或多个话题， 然后对每一则测试报道计算它跟 某个话题之间的分数。根据分数做两个阈值判断。如果分数超过高阈值Θm，则把该报道并 。如果分数超过了低阈值Θd，则表示此报道与话 入话题（因而通过 ncl 影响了将来的分数） 题相关，但不把它并入聚类。 4.3 聚类分类策略 判断某个新报道是属于已有话题还是一个新话题， 往往是同时进行的。 通常的做法是把 新报道和已有话题进行比较， 如果相似度高于某个阈值， 则把新报道归入相似度最高的话题 中，如果对所有话题的相似度都低于阈值，则创建一个新话题。但在具体实现中，还牵涉到 选用哪些聚类、分类和根据反馈进行参数调整的策略。 最简单的方法称为增量聚类算法，它顺序处理报道，一次处理一则，对每一则报道它执 行两个步骤： 1． 选择：选出和报道最相似的聚类 2． 比较阈值： 把报道和阈值相比较， 决定是把报道分到聚类里还是创建一个新的聚类。 这种算法非常直观，便于实现，但它的缺点也很明显： 对一则报道只能做一次决策，因此 早期根据很少的信息所做的错误判断累计到后面可能相当可观； 随着报道

的不断处理，计 算开销会越来越大。对语料库处理的后期，系统可能需要把每则报道和几千个聚类相比较。 针对这些缺点稍加改进，就形成了增量 k-means 方法，它在当前报道窗口中进行迭代操 作，每一次迭代都要做适当的改变。具体步骤是： 1. 使用增量聚类算法处理当前可调整窗口中的全部报道。 2. 把可调整窗口中的每一则报道和旧的聚类进行比较， 判断每则报道是要合并到聚类 中去还是用作新聚类的种子。 3. 根据计算结果立刻更新所有的聚类。 4. 重复步骤（2）－（3） ，直到所有的聚类不再变化 5. 查看下一批报道，转向（1） 。 KNN 算法是一种常用的文本分类算法，它应用在话题跟踪上也有比较好的效果，其基 本思想是把新报道和所有的报道逐一比较，计算其相似度，然后选择最相近的 k 个“邻居” （报道） ，在这 k 个邻居中，如果某个话题包含的报道数最多，则把新报道也归入该话题， 并对话题模型重新训练。 对于参数调整，各个系统也采用不同的策略。有些系统只根据正例（和话题相关）对话 题模型进行调整，而有些系统则兼顾正例和反例。对以向量空间表示的话题而言，Rocchio 方法是一种较为有效的参数调整方法，其形式为： ω 'jc = αω jc + β ' ∑ i∈C xij nC −γ ∑ i∉C xij n − nC 其中 ω jc 是调整之后的权值，ω jc 是原来的权值，i 表示已处理的报道，C 表示某个话题， xij 是 i 中的特征项，n 是已处理报道的总数， nC 是正例的总数。 除此之外， 有些研究机构也在尝试新的算法， 比如支持向量机 （Support Vector Machine） 、 最大熵（Maximum Entropy） 、文档扩展等，但都还需要在评测中实际验证其效果。

4.4 性能比较 CMU 对各种分类器在 TDT 上的应用做了一个比较，结果如表二、表三所示： 系统（在 TDT1 上调整参数） kNN.avg1(k=5 Rocchio(γ=-2, n=200 LM(α=0.025 BORG(综合以方法 系统（在 TDT3 上调整参数） kNN.avg1(k=2000 Rocchio(γ=-.25, n=200 LM(α=0.25 BORG(综合以上方法 AA .0033 .0022 .0035 .0021 表二 AA .0023 .0026 .0040 .0023 δ 0% 12% 43% AB .0030 .0033 .0040 .0027 δ 13%

21% 33% δ 34% 3% 40% AB .0063 .0060 .0045 .0028 δ 57% 55% 38% - 表三 其中，括号内是各个方法设定的参数。表一中的 AA 表示在 TDT1 上训练并测试，AB 表示 在 TDT1 上训练，在 TDT3 上测试。表二中的 AA 表示在 TDT3 上训练并测试，AB 表示在 TDT3 上训练，在 TDT1 上测试。δ是 BORG 方法相对于其它方法分数提高的百分比。测试 分数是归一化之后的 CDet，显然，这个值越低越好。 综上来看，TDT 系统采用的方法在各个子任务中已经取得了很大进展，尤其是话题跟 踪，已经取得了相当好的分数，但也有以下主要问题： （1） 所用到的主要技术与文本分类聚类、信息检索、信息过滤、信息抽取等比较相 似，可以直接用在相关的评测中； （2） 针对 TDT 特定需求的方法基本上没有进展； （3） 对话题本身的特征关注不够，比如可以考虑引入规则是否有效，这个想法基于 以下事实，即：如果两则报道讨论的是在同一个地点发生的关于同一个人的事， 那么这两则报道讨论的可能就是同一件事； （4） 评测中最好系统的成绩虽然比以前有了很大提高， 但和全面实用还有一段距离。 5 结束语 目前来看，TDT 的研究呈现以下特点： （1） 大多数已公开系统采用的方法主要还是传统的文本分类、信息过滤和检索的方 法，专门针对话题发现与跟踪自身特点的算法还未形成； （2） 要取得整体上比较满意的效果并不太困难，但对某个用户感兴趣的特定话题， 现有系统都无法保证取得满意的效果，比如对于用户当前最为关注的“伊拉克 战争” ，系统不能保证取得高于平均值的准确率； （3） 综合使用多种相对成熟的方法，从长期来看在实际应用中可能效果最佳，同时 这也是将来的一个研究发展方向。 总而言之，TDT 是自然语言处理领域中的一个新兴的研究课题。通过评测驱动的方式， TDT 的研究已经取得了相当大的进展。但当前的研究主要还是基于传统的统计方法，这些 方法在文本分类、信息检索、信息过滤等领域得到广泛的应用。将来的发展应主要关注话题

本身的特性，并考虑多种方法的综合运用。TDT 的发展和实际应用息息相关，它能够

弥补 信息检索的一些不足，在国家信息安全、企业市场调查、个人信息定制等方面都存在着实际 需求。随着现有系统性能的不断提高，TDT 在各个领域必将得到越来越广泛地应用。 参考文献 [1]S.A. Lowe, “The Beta-Binomial Mixture Model forWord Frequencies

in

Documents

with

Applications

to

Information

Retrieval,”Proceedings of Eurospeech ’99,Budapest, September 1999. [2]S.A. Lowe, “The Beta-Binomial Mixture Model and Its Application to TDT Tracking and Detection,” Proceedings of the DARPA Broadcast News Workshop, February 1999. [3]W. Lam and H. Meng and K. Hui. “Multilingual Topic Detection Using a Parallel Corpus”. In Proceedings of the DARPA TDT 2000 Workshop, November 2000. [4]Jin, H., R. Schwartz, S. Sista and F. Walls, “Topic Tracking for Radio, TV Broadcast and Newswire,” Proceedings of the DARPA Broadcast News Workshop, Herndon, Va, 1999. [5]Schwartz, R., Imai, T., Nguyen, L., and Makhoul, J., “A maximum Likelihood Model for Topic Calssification of Broadcast News,” in Proc. Eurospeech, Rhodes, Greece, September,1997. [6]Walls, F., Jin, H., Sista, S., and Schwartz, R., “Topic Detection in Broadcast News,” in Proceedings of the DARPA Broadcast News Workshop, Herndon, Va, 1999. [7]J.P. Yamron, I. Carp, L. Gillick, S.A. Lowe, and P. van Mulbregt,“Topic Tracking in a News Stream”, Proceedings of the DARPA Broadcast News Workshop, February 1999.