ｗｅｅｔｓ　ａｓ　ｓｅｎｔｅｎｃｅｓ，ａｎｄ　ａｄｏｐｔ　ｔｒａｄｉｔｉｏｎａｌ　ｓｕｍｍａｒｉｚａｔｉｏｎ　ｍｅｔｈｏｄｓ，ｓｕｃｈ　ａｓＳｕｍＢａｓｉｃ，Ｃｅｎｔｒｏｉｄ，ＬｅｘＲａｎｋ　ｔｏ　ｖａｌｉｄａｔｅ　ｔｈｅ　ｒｅｌｅｖａｎｔ　ｐｅｒｆｏｒｍａｎｃｅ　ｏｎ　ｍｉｃｒｏｂｌｏｇｇｉｎｇ　ｐｏｓｔｓ．Ｈｏｗｅｖｅｒ，ｉｔ　ｉｓ　ｎｏｔ　ｃｌｅａｒ　ｗｈｅｔｈｅｒ　ａｄｄｉｎｇ　ｔｈｅ　ｃｏｍｐｌｅｘｉｔｙ　ｏｆ　ｍｅｔｈｏｄｓ　ｗｉｌｌ　ｉｍｐｒｏｖｅ　ｔｈｅ　ｓｙｓｔｅｍｐｅｒｆｏｒｍａｎｃｅ．Ｓｏｍｅ　ｏｔｈｅｒ　ｒｅｓｅａｒｃｈｅｓ　ｅｘｐｌｏｒｅ　ｔｏ　ｕｔｉｌｉｚｅ　ｓｔａｔｉｃ　ｓｏｃｉａｌ　ｆｅａｔｕｒｅｓ　ｅｘｃｅｐｔ　ｆｏｒ　ｔｅｘｔｕａｌｃｏｎｔｅｎｔ，ｓｕｃｈ　ａｓ　ｎｕｍｂｅｒ　ｏｆ　ｒｅｐｌｉｅｓ，ｎｕｍｂｅｒ　ｏｆ　ｒｅｔｗｅｅｔｓ，ｎｕｍｂｅｒ　ｏｆ　ｌｉｋｅｓ，ａｕｔｈｏｒ　ｐｏｐｕｌａｒｉｔｙ　ａｎｄｔｅｍｐｏｒａｌ　ｓｉｇｎａｌｓ．Ｔｈｅｓｅ　ｍｅｔｈｏｄｓ　ｒａｒｅｌｙ　ｃｏｎｓｉｄｅｒ　ｔｈｅ　ｄａｔａ　ｓｐａｒｓｉｔｙ，ｔｈｅ　ｓｔｒｏｎｇ　ｓｏｃｉａｌ　ｒｅｄｕｎｄａｎｃｙａｎｄ　ｔｈｅ　ｐｏｔｅｎｔｉａｌ　ｓｏｃｉａｌ　ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　ｔｗｅｅｔｓ　ｅｘｐｌｉｃｉｔｌｙ，ｉｇｎｏｒｉｎｇ　ｔｈｅ　ｆａｃｔ　ｔｈａｔ　ｉｎｆｏｒｍａｔｉｏｎ　ｃａｎｓｐｒｅａｄ　ａｌｏｎｇ　ｔｈｅ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ．Ｉｎｓｐｉｒｅｄ　ｂｙ　ｃｏｍｐｒｅｓｓｉｖｅ　ｓｅｎｓｉｎｇ　ａｎｄ　ｓｏｃｉａｌ　ｔｈｅｏｒｉｅｓ，ｗｅ　ｐｒｏｐｏｓｅａ　ｎｏｖｅｌ　ａｐｐｒｏａｃｈ　ｆｏｒ　Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎ　ｂａｓｅｄ　ｏｎ　Ｓｏｃｉａｌ　Ｎｅｔｗｏｒｋ　ａｎｄ　Ｓｐａｒｓｅ　Ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ（ＳＮＳＲ）ｆｏｒ　ｉｎｔｅｇｒａｔｉｎｇ　ｓｏｃｉａｌ　ｍｅｄｉａ　ｃｏｎｔｅｎｔ　ａｎｄ　ｓｔｒｕｃｔｕｒｅ　ｉｎｆｏｒｍａｔｉｏｎ．Ｔｈｅ　ｓｏｃｉａｌ　ａｎａｌｙｓｉｓｉｎｄｉｃａｔｅｓ　ｔｈａｔ　ｔｈｅ　ｍｅｍｂｅｒｓ　ｉｎ　ａ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ｏｆｔｅｎ　ｅｘｈｉｂｉｔ　ｃｏｒｒｅｌａｔｅｄ　ｂｅｈａｖｉｏｒｓ，ｓｅｎｔｉｍｅｎｔ　ａｎｄｔｏｐｉｃ　ｃａｎ　ｂｅ　ｄｉｆｆｕｓｅｄ　ｔｈｒｏｕｇｈ　ｎｅｔｗｏｒｋ．Ｃｏｎｓｉｓｔｅｎｃｙ　ｍｅａｎｓ　ｔｈａｔ　ｓｏｃｉａｌ　ｂｅｈａｖｉｏｒｓ　ｃｏｎｄｕｃｔｅｄ　ｂｙ　ｔｈｅｓａｍｅ　ｐｅｒｓｏｎ　ｋｅｅｐ　ｃｏｎｓｉｓｔｅｎｔ　ｉｎ　ａ　ｓｈｏｒｔ　ｐｅｒｉｏｄ　ｏｆ　ｔｉｍｅ．Ｃｏｎｔａｇｉｏｎ　ｍｅａｎｓ　ｔｈａｔ　ｆｒｉｅｎｄｓ　ｃａｎ　ｉｎｆｌｕｅｎｃｅｅａｃｈ　ｏｔｈｅｒ．Ｗｅ　ｅｘｐｌｏｒｅ　ｗｈｅｔｈｅｒ　ｓｏｃｉａｌ　ｒｅｌａｔｉｏｎｓ（ｅｘｐｒｅｓｓｉｏｎ　ｃｏｎｓｉｓｔｅｎｃｙ　ａｎｄ　ｅｘｐｒｅｓｓｉｏｎ　ｃｏｎｔａｇｉｏｎ）ｃａｎ　ｈｅｌｐ　Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎ　ｕｎｄｅｒ　ａ　ｇｉｖｅｎ　ｔｏｐｉｃ，ｍｏｄｅｌｉｎｇ　ｒｅｌａｔｉｏｎｓ　ｂｅｔｗｅｅｎ　ｔｗｅｅｔｓ　ｄｅｓｃｒｉｂｅｄａｓ　ｔｈｅ　ｓｏｃｉａｌ　ｒｅｇｕｌａｒｉｚａｔｉｏｎ　ａｎｄ　ｉｎｔｅｇｒａｔｉｎｇ　ｉｔ　ｉｎｔｏ　ｔｈｅ　ｇｒｏｕｐ　ｓｐａｒｓｅ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｒａｍｅｗｏｒｋ．Ｉｔｃｏｎｄｕｃｔｓ　ａ　ｓｐａｒｓｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　ｐｒｏｃｅｓｓ　ｂｙ　ｓｅｌｅｃｔｉｎｇ　ｔｗｅｅｔｓ　ｔｈａｔ　ｃａｎ　ｂｅｓｔ　ｒｅｃｏｎｓｔｒｕｃｔ　ｔｈｅ　ｏｒｉｇｉｎａｌｔｗｅｅｔｓ，ｗｉｔｈ　ｃｏｎｓｉｄｅｒｉｎｇ　ｃｏｖｅｒａｇｅ　ａｎｄ　ｓｐａｒｓｉｔｙ．Ｗｅ　ｓｉｍｕｌｔａｎｅｏｕｓｌｙ　ｄｅｓｉｇｎ　ｔｈｅ　ｄｉｖｅｒｓｉｔｙ　ｒｅｇｕｌａｒｉｚａｔｉｏｎｔｏ　ｒｅｍｏｖｅ　ｔｈｅ　ｓｔｒｏｎｇ　ｒｅｄｕｎｄａｎｃｙ　ｂｒｏｕｇｈｔ　ｂｙ　ｓｏｃｉａｌ　ｉｎｆｏｒｍａｔｉｏｎ　ｐｒｏｐａｇａｔｉｏｎ．Ｉｎ　ｐａｒｔｉｃｕｌａｒ，ｗｅｐｒｅｓｅｎｔ　ａ　ｍａｔｈｅｍａｔｉｃａｌ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒｍｕｌａｔｉｏｎ　ａｎｄ　ｄｅｖｅｌｏｐ　ａｎ　ｅｆｆｉｃｉｅｎｔ　Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍ　ｗｉｔｈ　Ｎｅｓｔｅｒｏｖ’ｓ　ａｃｃｅｌｅｒａｔｅｄ　ｇｒａｄｉｅｎｔ　ｄｅｓｃｅｎｔ．Ｍｅａｎｗｈｉｌｅ，ｄｕｅ　ｔｏ　ｔｈｅ　ｌａｃｋ　ｏｆ　ｐｕｂｌｉｃｃｏｒｐｕｓ，ｗｅ　ｃｏｎｓｔｒｕｃｔ　ｔｈｅ　ｇｏｌｄ　ｓｔａｎｄａｒｄ　ｔｗｅｅｔ　ｓｕｍｍａｒｙ　ｄａｔａｓｅｔｓ　ｆｏｒ　１２ｄｉｆｆｅｒｅｎｔ　ｔｏｐｉｃｓ　ｂｙ　ａｓｋｉｎｇ２４ｖｏｌｕｎｔｅｅｒｓ　ｔｏ　ｍａｎｕａｌｌｙ　ｓｅｌｅｃｔ　ｔｈｅ　ｍｏｓｔ　ｉｎｆｏｒｍａｔｉｖｅ　ｔｗｅｅｔｓ，ａｌｌ　ｉｎ　４８ｅｘｐｅｒｔ　ｓｕｍｍａｒｉｅｓ．Ｅｘｐｅｒｉ－ｍｅｎｔａｌ　ｒｅｓｕｌｔｓ　ｏｎ　ｔｈｉｓ　ｄａｔａｓｅｔｓ　ｓｈｏｗ　ｔｈｅ　ｅｆｆｅｃｔｉｖｅｎｅｓｓ　ｏｆ　ｏｕｒ　ａｐｐｒｏａｃｈ　ｆｏｒ　ｈａｎｄｌｉｎｇ　ｔｈｅ　ｌａｒｇｅ　ｓｃａｌｅｓｈｏｒｔ　ａｎｄ　ｎｏｉｓｙ　ｍｅｓｓａｇｅｓ　ｉｎ　ｓｏｃｉａｌ　ｍｅｄｉａ．Ｉｔ　ｓｕｇｇｅｓｔｓ　ｔｈａｔ　ｉｎｔｅｇｒａｔｉｎｇ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ｉｎｆｏｒｍａｔｉｏｎｉｎｔｏ　ｔｈｅ　ｐｒｏｐｏｓｅｄ　ｓｐａｒｓｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ　ｆｒａｍｅｗｏｒｋ　ｈｅｌｐｓ　ｉｍｐｒｏｖｅ　Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎ．Ｍｉｎｉｎｇｔｈｅ　ｇｒｏｕｐ　ｓｐａｒｓｉｔｙ　ｐａｔｔｅｒｎｓ　ｏｆ　ｓａｌｉｅｎｔ　ｔｗｅｅｔｓ　ａｎｄ　ｄｅｓｉｇｎｉｎｇ　ｔｈｅ　ｄｉｖｅｒｓｉｔｙ　ｒｅｇｕｌａｒｉｚａｔｉｏｎ　ｉｎ　ｔｅｒｍｓ　ｏｆｒｅｄｕｎｄａｎｃｙ　ｂｒｏｕｇｈｔ　ｂｙ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ　ａｒｅ　ａｌｓｏ　ｅｆｆｅｃｔｉｖｅ．Ｋｅｙｗｏｒｄｓ　 Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎ；ｓｐａｒｓｅ　ｒｅｃｏｎｓｔｒｕｃｔｉｏｎ；ｎｅｔｗｏｒｋ　ｔｏｐｏｌｏｇｙ；ｓｏｃｉａｌ　ｔｈｅｏｒｉｅｓ；Ｎｅｓｔｅｒｏｖ’ｓ　ａｃｃｅｌｅｒａｔｅｄ　ｇｒａｄｉｅｎｔ　ｄｅｓｃｅｎｔ　ａｌｇｏｒｉｔｈｍ１　引　言社会媒体的繁荣改变和影响了人们获取和发布信息的方式．本文研究面向特定话题的推特摘要，旨在从事件相关的社会媒体短文本中提炼简洁、核心的推文集，以捕捉有效信息，可用于竞争情报分析、电子商务等；同时，也可协助政府监管危机事件，从而降低灾难损失、给出有益的反馈，并把控舆情方向．尽管传统的文本摘要技术发展了很多年，但是新兴的社会媒体平台产生了大规模嘈杂且不规范的碎片化短文本，为社会媒体摘要研究带来了诸多挑战，然而也带来了新的机遇．现有的推特摘要方法通常将推文看作句子，对其进行重要性打分并筛选推文集．包括：（１）利用传统的文本摘要方法［１］，即仅考虑文本信息，这些方法包括ＳｕｍＢａｓｉｃ［２］、Ｃｅｎｔｒｏｉｄ［３］、ＬｅｘＲａｎｋ［４］和 ＴｅｘｔＲａｎｋ［５］等；（２）利用社交媒体平台的静态特 性［６－７］，包括推文转发数、回复数、点赞数、用户权威特性（粉丝数、关注数等）、时间特性、地理特性等；但这些方法忽略了社会媒体短文本是网络互联的；（３）利用社交媒体平台的动态特性［８－９］，即社会网络结构信息，包括转发关系、回复（Ｒｅｐｌｙ）关系、关注（Ｆｏｌｌｏｗ）关系等．但该类研究主要是从用户层次考虑网络结构，一般认为高权威度用户所发的推文同样具有很高的重要性．然而，通过用户之间的社会网络连接可以推测，推文之间也存在潜在的６期 贺瑞芳等：基于社会媒体内容和网络拓扑的特定话题推特摘要研究１１５７计算推文相似度使得推文之间互相关联的传统方法，该方法仅仅利用了纯文本信息．通过社会网络结构构建推文层面的相互关联网络结构可能包含更多的语义线索．因此，本文需要探索一种建模推文层面网络信息互联的新方法，以进行推特摘要．社会学理论揭示了互联信息的这种相互影响的现象．人们在短时间内更倾向于保持一致的情感、爱好，这种现象称之为一致性．除此之外，人们通过一系列交互和反馈行为在彼此之间建立了联系，这层联系对彼此产生的影响是微妙的，可以对一个人的爱好、说话方式或者表达内容产生重大的影响．人们渐渐会和好友在某个话题上保持相似的观点，甚至以相似的语调和用词来表达这些观点，这种现象称之为传染性．受到这两种社会学理论的启发，本文将进一步探索如何利用这两种理论做推特摘要．近年来，基于数据重构的摘要方法被提出［１０－１２］，并且在传统评测任务 ＤＵＣ／ＴＡＣ 上表现出色，但其并不能直接迁移到社会媒体情景中．也正是由于之前提到的社会学理论可与基于数据重构的方法无缝结合，本文从压缩感知、稀疏重构角度出发，将推文看作一种信号，提出了整合社交网络结构信息统一的推特摘要优化框架．其综合考虑了一个好的推特摘要应该具备的几个特性：（１）覆盖性（Ｃｏｖｅｒａｇｅ），即一个好的摘要应该尽可能包含整个语料谈论话题的各个方面；（２）稀疏性（Ｓｐａｒｓｉｔｙ），即假设信号是稀疏可压缩的，摘要只是原推特语料的一部分．假设每个句子可以由所有其他句子通过非负线性组合来表示，那么不是所有句子在表示该句子的过程中都占有很大比重．摘要句子即是这样一组句子基，通过这组句子基张成的子空间，可以表示整个语料的其它句子，从而以尽 可能小 的误差重构原始语料；（３）多样性（Ｄｉｖｅｒｓｉｔｙ），即保证摘要句子之间的冗余度尽可能小．主要贡献如下：① 从统计学角度验证了两种社会学理论的存在，即表达一致性和表达传染性；形式化地定义了整合社会网络结构的推特摘要框架．② 建模了推文层面的网络结构信息，并作为社会项正则整合到基于稀疏重构的优化框架中．③ 引入组稀疏正则可以从语料层面选择重要的推文，引入多样性正则可以缓解由于社交网络的引入而带来的更加严峻的冗余度问题．④ 构建了推特摘要语料，包括１２ 个特定话题数据集以及每个数据集对应的四个专家摘要．本文第２节综合分析和讨论相关工作；第３节给出问题阐述和数据分析，并进行社会学理论的验证；第４节详细论述本文提出的基于稀疏重构和社会网络结构的社会媒体推特摘要方法；第５节给出基于 Ｎｅｓｔｅｒｏｖ加速梯度下降的摘要优化算法；第６节介绍真实数据集上推特摘要的标准语料 制作方案，并在此基础上验证本文方法的有效性；第７节进行总结和展望．２　相关工作社会媒体平台的产生、成长经历近１０年时间．它的繁荣催生了以推特摘要为代表的社会媒体摘要研究，其部分地传承了传统文本摘要方法．现有的自动摘要方式一般 可分为 两 大类：抽取式 和 理解式．（１）抽取式摘要从原始语料中抽取一部分句子形成摘要，可以保证摘要句子的可读性，但是摘要句子之间以及摘要句子内部会产生冗余信息；（２）理解式摘要通常采用句子压缩、融合、改写等自然语言处理技术实现，在技术难度上比较大．故当前文本摘要研究大多数还是基于抽取式的研究路线．同时，由于推特文本的碎片化、不规范性以及大量噪声，使得理解式摘要方法中的语法分析、句法分析等底层技术难以发挥作用．因此，本文采取抽取式摘要路线，相关工作的调研也围绕此展开．２．１　传统文本摘要产生文本摘要的过程通常可以描述为：句子重要性打分、句子筛选、摘要句子排序这三个过程．如何对句子进行重要性打分是摘要研究的重点．已有的方法包括：（１）基于特征的方法，例如 Ｃｅｎｔｒｏｉｄ和ＳｕｍＢａｓｉｃ［２－３］，这些方法考虑了词频和句子位置信息来计算句子的权重；（２）基于图的方法采用了类似ＰａｇｅＲａｎｋ的算法，例如 ＬｅｘＲａｎｋ和 ＴｅｘｔＲａｎｋ［４－５］，以句子或词作为节点，句子或词之间的相似度作为构建图中边权重的依据，利用随机游走的思想最终得到句子或词的重要性．然而，该类方法面临去冗余的问题．一些研究者开始利用（３）基于聚类的思想来保持摘要的多样性［１３－１８］．其主要采用主题建模、聚类算法以及矩阵分解的思想来产生覆盖性更高的摘要．最近，（４）基于数据重构的摘要方法的出现［１０－１２］，为解决摘要研究中存在的经典问题，即覆盖性、重要性及多样性，带来了新的可能性．然而由于社交媒体中大规模的文本具有简短、嘈杂及其附带的社会特性，使得这些传统方法不能很好地发挥作用．１１６７ 计　　算　　机　　学　　报 ２０１９年展使得人们不断探索传统摘要方法在 类 似 推 特 平 台 上 的 应 用．这 些 方 法 包 括（１）Ｈｙｂｒｉｄ　ＴＦ－ＩＤＦ［１］，其针对推特短文本语料对经典的 ＴＦ－ＩＤＦ 模 型 进 行 变 种，在 计 算 ＩＤＦ（ＩｎｖｅｒｓｅＤｏｃｕｍｅｎｔ　Ｆｒｅｑｕｅｎｃｙ）的时候是把每个帖子看成一个文档，在计算 ＴＦ（Ｔｅｒｍ　Ｆｒｅｑｕｅｎｃｙ）的时候是把所有帖子看成一个大文档；（２）短语强化算法［１９－２０］，其通过不断选择使用频率最高的短语，最终生成摘要句子．这些方法仅考虑了文本信息．然而，社交媒体平台还包含除文本信息之外的大量丰富信息，比如推文转发数、回复数、用户粉丝数、关注数、时间、地理信息，以及社交网络结构等信息；（３）基于社会网络静 态 信 息 和 用 户 层 面 网 络 结 构 的 推 特 摘 要，Ｄｕａｎ等人［９］考查了推文内容质量、用户发文数、粉丝数、粉丝数与关注数的比率等信息，以及通过关注（Ｆｏｌｌｏｗ）关系构建的用户网络结构；Ｌｉｕ等人［７］考查了推文转发数、用户粉丝数以及推文可读性三方面的特性．以上两个工作均采用基于 ＰａｇｅＲａｎｋ 的扩展模型．Ａｌｓａｅｄｉ等人［２１］提出了用于事件摘要的三个方法，考查了时间和转发数两个特性．Ｃｈａｎｇ等人［６，８］把推特摘要研 究看成有监督的分类任务，即判断每条推文可否被选择为一个摘要句子．并通过充分挖掘社交媒体中存在的一些特性，包括推文转发数、回复数、点赞数、内容相关度、用户粉丝数、关注数、权威度、时间间隔等，作为分类器的输入特征，从而选择摘要推文．以上方法主要利用了社会网络的静态信息或者用户层面的网络结构，并没有考虑到推文层面的网络结构，而诸如情感、话题、内容等推特信息是可以沿着潜在的网络结构进行传播，本文通过研究这种传播现象，以期获得更多潜在的语义线索进行推特摘要研究．２．３　结合社会网络结构的探索社会学理论以及社会网络分析为我们做推特摘要研究提供了新思路，即如何结合拓扑结构和文本内容做推特摘要．社会网络传播，或者说社交影响力在多个领域都有研究．比如，（１）情感分析［２２］认为人们在短时间内对某个话题或事物保持情感一致性，具有朋友关系的两个人在情感上更容易互相影响，并称之为情绪传染性；（２）话题识别［２３］认为人们在短时间内对专注的话题会保持一致的偏好，除此之外，具有朋友关系的两个人更有可能对同一话题感兴趣，并称之为社会传染性；（３）话题具体的影响力分析［２４］识别特定话题下具有影响力的用户，并对用户关注（Ｆｏｌｌｏｗ）关系中的这种现象进行建模：一部分用户关注其他人是由于对共同话题感兴趣，故粉丝所发内容是会受到关注者所发内容的影响；而一部分用户关注其他用户只是由于热度（粉丝数等），他们所发内容很少受到关注者所发内容的影响．通过将这种现象建模到主题模型中，既可以识别特定话题下具有影响力的用户，同时也可以提升话题检测的性能；以及（４）网络推断和话题模型的联合建模［２５］等．根据这些研究可知，情感和话题是可以沿着网络传播的．本文将深入探索作为情感和话题的载体———表达内容是否可以沿着网络进行传播，以及如何影响推特摘要．３　问题陈述与数据分析本文面向特定话题进行推特摘要研究，即输入与某个话题相关的推特文本集，输出若干条重要推文形成摘要并可描述该话题的主要内容．本节首先给出一些符号定义，并正式描述本文推特摘要的整个流程；其次由于缺乏推特摘要的公开语料，本节将介绍语料建设中的数据准备环节，其中专家摘要的制作过程放在实验部分；同时，重新定义两种社会学理论（表达一致性、表达传染性），并在我们的数据集上验证其存在性．３．１　问题陈述本文约定加粗的大写字符表示矩阵（例如 Ｍ），加粗的小写字符表示向量（例如 ｍ），小写字符表示标量（例如 ｍ）．Ｍｉ＊和 Ｍ＊ｊ分别表示矩阵 Ｍ 的第ｉ行和第ｊ列．Ｍｉｊ表示矩阵 Ｍ 在第ｉ 行第ｊ 列的值．ＭＦ表示矩阵的 Ｆｒｏｂｅｎｉｕｓ范数，Ｍ２，１表示矩阵的２，１范数．特别地，ＭＦ＝∑ｍｉ∑ｎｊＭ２ｉ槡ｊ，Ｍ ２，１＝∑ｍｉＭｉ＊ ２＝∑ｍｉ∑ｎｊＭ２ｉ槡ｊ．给定特 定 话 题 的 推 特 语 料，该 语 料 可 表 示 为ＴＦ－ＩＴＦ（Ｔｅｒｍ　Ｆｒｅｑｕｅｎｃｙ　Ｉｎｖｅｒｓｅ　Ｔｗｅｅｔ　Ｆｒｅｑｕｅｎｃｙ）矩阵，即Ｓ＝［ｔ１，ｔ２，…，ｔｎ］∈!ｍ×ｎ，其中 ｍ 表示词汇表大小，ｎ 表示推文数量．Ｓ 矩阵的每一列ｔｉ为单个推文的向量表示．Ｕ∈ !ｄ×ｎ表示用户－推 文矩阵，其中，ｄ 为用户数，Ｕｉｊ＝１表示第ｊ条推文是由第ｉ个用户发布．本文根据 Ｆｏｌｌｏｗ 关系构建用户 －用户矩阵Ｆ∈!ｄ×ｄ，其中Ｆｉｊ＝１表示第ｉ个与第ｊ 个用户是有联系的．依据上面给定的符号，本文的推特摘要任务可６期 贺瑞芳等：基于社会媒体内容和网络拓扑的特定话题推特摘要研究１１７７在线出版日期：２０１８－１０－１５．本课题得到国家自然科学基金面上项目（６１４７２２７７）和天津市自然科学基金一般项目（１８ＪＣＹＢＪＣ１５５００）资 助．贺 瑞 芳 （通 信 作 者），博 士，副 教 授，主 要 研 究 方 向 为 自 然 语 言 处 理、社 会 媒 体 挖 掘 及 机 器 学 习．Ｅ－ｍａｉｌ：ｒｆｈｅ＠ｔｊｕ．ｅｄｕ．ｃｎ．段兴义，硕士，主要研究方向为自然语言处理、多文本自动摘要．张雪菲，硕士，主要研究方向为自然语言处理、社会计算．赵文丽，硕士研究生，主要研究方向为自然语言处理．基于社会媒体内容和网络拓扑的特定话题推特摘要研究贺瑞芳　段兴义　张雪菲　赵文丽（天津大学智能与计算学部　天津　３００３５０）（天津市认知计算与应用重点实验室　天津　３００３５０）摘　要　推特摘要旨在从话题相关的社会媒体短文本中提炼概要的推文集，以获取有效信息，可用于舆情监控、竞争情报分析及电子商务等．然而社会媒体的海量、嘈杂及不规范性使得仅依赖纯文本的传统摘要方法难以直接迁移到社交媒体情景中；而现有的推特摘要方法很少考虑数据稀疏性和社会网络传播带来的强冗余性，鲜有通过挖掘推文之间潜在的社会网络结构关系进行文摘内容选择，忽略了信息可以沿着社交网络进行传播．受压缩感知及社会学理论的启发，该文提出基于社会网络和稀疏重构的推特摘要方法（ＳＮＳＲ）以更好地融合社会媒体内容和结构信息．首先，挖掘推文中隐含的摘要模式，将其建模为组稀疏正则项，以捕捉代表性的推特摘要组合；其次，建模社会网络中表达一致性与表达传染性为社会化正则项，以探索推文之间的潜在网络结构关系在推特摘要中的作用；再次，建模社会媒体信息传播带来的强冗余性为多样性正则项，进而将这些约束整合到稀疏重构的推特摘要框架中；最后，提出基于 Ｎｅｓｔｅｒｏｖ加速梯度下降的推特摘要算法，以解决推特摘要优化框架中的覆盖性、稀疏性以及多样性等问题．同时，由于推特摘要标准语料的缺乏，作者建设了１２个话题的评测数据集．相关的实验结果证明了文中提出方法的有效性．关键词　推特摘要；稀疏重构；网络拓扑；社会学理论；Ｎｅｓｔｅｒｏｖ加速梯度下降算法中图法分类号 ＴＰ１８　　　ＤＯＩ号 １０．１１８９７／ＳＰ．Ｊ．１０１６．２０１９．０１１７４Ｔｏｐｉｃ　Ｏｒｉｅｎｔｅｄ　Ｔｗｉｔｔｅｒ　Ｓｕｍｍａｒｉｚａｔｉｏｎ　Ｂａｓｅｄ　ｏｎ　Ｓｏｃｉａｌ　Ｍｅｄｉａ　Ｃｏｎｔｅｎｔ　ａｎｄＮｅｔｗｏｒｋ　ＴｏｐｏｌｏｇｙＨＥ　Ｒｕｉ－Ｆａｎｇ　ＤＵＡＮ　Ｘｉｎｇ－Ｙｉ　ＺＨＡＮＧ　Ｘｕｅ－Ｆｅｉ　ＺＨＡＯ　Ｗｅｎ－Ｌｉ（Ｃｏｌｌｅｇｅ　ｏｆ　Ｉｎｔｅｌｌｉｇｅｎｃｅ　ａｎｄ　Ｃｏｍｐｕｔｉｎｇ，Ｔｉａｎｊｉｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｔｉａｎｊｉｎ　３００３５０）（Ｔｉａｎｊｉｎ　Ｋｅｙ　Ｌａｂｏｒａｔｏｒｙ　ｏｆ　Ｃｏｇｎｉｔｉｖｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ａｐｐｌｉｃａｔｉｏｎ，Ｔｉａｎｊｉｎ　３００３５０）Ａｂｓｔｒａｃｔ　 Ｓｏｃｉａｌ　ｍｅｄｉａ　ｐｌａｔｆｏｒｍｓ，ｓｕｃｈ　ａｓ　Ｔｗｉｔｔｅｒ，ｐｒｏｖｉｄｅ　ｕｓ　ａ　ｖｅｒｙ　ｃｏｎｖｅｎｉｅｎｔ　ｗａｙ　ｔｏ　ａｃｃｅｓｓｉｎｆｏｒｍａｔｉｏｎ，ｔｈｒｏｕｇｈ　ｗｈｉｃｈ　ａｍｏｕｎｔｓ　ｏｆ　ｕｓｅｒｓ　ｃａｎ　ｆｒｅｅｌｙ　ｐｒｏｄｕｃｅ　ｃｏｎｔｅｎｔ（ｃａｌｌｅｄ　ｔｗｅｅｔｓ）ｏｎ　ｔｈｅｉｒｉｎｔｅｒｅｓｔｅｄ　ｔｏｐｉｃｓ．Ｔｈｅｒｅｆｏｒｅ，ｉｔ　ｂｅｃｏｍｅｓ　ｏｎｅ　ｏｆ　ｔｈｅ　ｍｏｓｔ　ｐｏｐｕｌａｒ　ｓｏｃｉａｌ　ｎｅｔｗｏｒｋ．Ｆａｓｔ　ｉｎｃｒｅａｓｉｎｇｐｏｓｔｓ　ｍａｋｅ　ｐｅｏｐｌｅ　ｌｏｓｔ　ｉｎ　ｔｈｅ　ｏｃｅａｎ　ｏｆ　ｆｒａｇｍｅｎｔｅｄ　ｔｅｘｔｓ．Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎ　ａｉｍｓ　ｔｏ　ｅｘｔｒａｃｔｔｈｅ　ｃｏｒｅ　ａｎｄ　ｃｏｎｃｉｓｅ　ｔｗｅｅｔ　ｓｕｍｍａｒｙ　ｆｒｏｍ　ｔｏｐｉｃ　ｒｅｌｅｖａｎｔ　ｓｈｏｒｔ　ｔｅｘｔｓ　ｉｎ　ｓｏｃｉａｌ　ｍｅｄｉａ　ｓｏ　ａｓ　ｔｏ　ｑｕｉｃｋｌｙａｃｑｕｉｒｅ　ｅｓｓｅｎｔｉａｌ　ｉｎｆｏｒｍａｔｉｏｎ．Ｉｔ　ｃａｎ　ｂｅ　ｕｓｅｄ　ｉｎ　ｏｐｉｎｉｏｎ　ｍｏｎｉｔｏｒｉｎｇ，ｃｏｍｐｅｔｉｔｉｖｅ　ｉｎｔｅｌｌｉｇｅｎｃｅ　ａｎａｌｙｓｉｓａｎｄ　ｅｌｅｃｔｒｏｎｉｃ　ｃｏｍｍｅｒｃｅ，ｅｓｐｅｃｉａｌｌｙ　ｉｎ　ｓｏｍｅ　ｅｍｅｒｇｅｎｃｉｅｓ，ｗｈｉｃｈ　ｈｅｌｐｓ　ｔｏ　ａｉｄ　ａｇｅｎｃｉｅｓ　ｍｏｎｉｔｏｒｃｒｉｓｉｓ　ｐｒｏｇｒｅｓｓ　ｓｏ　ａｓ　ｔｏ　ａｓｓｉｓｔ　ｒｅｃｏｖｅｒｙ　ａｎｄ　ｐｒｏｖｉｄｅ　ｄｉｓａｓｔｅｒ　ｒｅｌｉｅｆ．Ｙｅｔ　ｔｒａｄｉｔｉｏｎａｌ　ｓｕｍｍａｒｉｚａｔｉｏｎｍｅｔｈｏｄｓ　ｏｎｌｙ　ｃｏｎｓｉｄｅｒ　ｔｅｘｔ　ｉｎｆｏｒｍａｔｉｏｎ，ｗｈｉｃｈ　ｉｓ　ｉｎｓｕｆｆｉｃｉｅｎｔ　ｉｎ　ｓｏｃｉａｌ　ｍｅｄｉａ　ｓｉｔｕａｔｉｏｎ　ｗｉｔｈ　ｔｈｅｌａｒｇｅ　ｓｃａｌｅ，ｎｏｉｓｙ　ａｎｄ　ｉｎｆｏｒｍａｌ　ｍｅｓｓａｇｅｓ．Ｐｒｅｖｉｏｕｓ　ｅｘｉｓｔｉｎｇ　Ｔｗｉｔｔｅｒ　ｓｕｍｍａｒｉｚａｔｉｏｎ　ａｐｐｒｏａｃｈｅｓ话题的推特语料Ｃ，可以获得文本内容矩阵Ｓ、用户 －推文矩阵Ｕ 以及用户－用户矩阵Ｆ，我们的目标是通过优化模型得到重构系数矩阵 Ｗ，并 根 据 Ｗ 按 一 定 压 缩 比 自 动 生 成 摘 要Ｓｕｍｍａｒｙ≈ＳＷ．３．２　数据描述使用公开的推特语料作为原始数据集，其最初由伊利诺伊大学①的一个研究团队所收集．由于集中在 ５，６，７ 三 个 月 的 数 据 最 多 （数 据 收 集 方 式 所致），我们统计每个月的 Ｈａｓｈｔａｇ频数，选择那些频数较大且对应于某个具体事件（一方面可以查看包含该 Ｈａｓｈｔａｇ的推文内容是否描述某个事件，一方面可以在浏览器上通过检索时间及 Ｈａｓｈｔａｇ，确认是否发生了某个事件）的 Ｈａｓｈｔａｇ作为话题标签，利用这些话题标签收集话题数据集．除此之外，每个话题不止一个话题标签，比如“＃ｏｓａｍａ”和“＃ｏｓａｍａｂｉｎ－ｌａｄｅｎ”描述的是一个话题．有些推文内容虽然不包含标签信息，但是包含类似“ｏｓａｍａ”这样的关键词，因此，我们主要根据推文内容是否包含 Ｈａｓｈｔａｇ或者除掉“＃”号后得到的关键词来收集话题．结合时间信息（每条推文都包含发布时间这一信息）以及上述处理过程，可以得到某个话题的推文数量随时间的变化，通过观察这种时序变化趋势，大致把话题分为热点话题（如图１）和突发话题（如图２）两种．同时考虑到社会学理论中一致性和传染性的短时间效应．进一步做如下处理：若该话题是热点话题，则收集该话题发生前后共五天时间内的推特数据作为该热点话题的数据集（图１）；若该话题是突发话题，则收集该话题发生后五天时间内的推特数据 作为该突发话题的数据集（图２）．最后筛选得到１２个话题，这些话题涉及政治、科技、体育、自然灾害、恐怖袭击和娱乐八卦等领域．得到特定话题的数据集后，需进一步做数据清洗，把满足以下条件之一图 １　哈利波特上映图 ２　挪威恐怖袭击的推文过滤掉，最终得到１２个话题的统计信息参见表１：（１）重复多次的推文（只保留一次）．（２）除 Ｈａｓｈｔａｇ、关键词、＠、ＵＲＬ 以及停用词外，单词数少于３的推文（对于特定话题，几乎所有的推文都包含一致的 Ｈａｓｈｔａｇ或关键词．除掉以上这些信息后几乎没有其他内容的推文，我们认为其增量信息比较少）．（３）对应 用 户 在数 据 集 中 属于 孤立 点 的 推文（保证网络结构的稠密性）．表 １　数据集统计信息统计信息 时间 推文数 用户数用户最大度用户最小度用户最大推文数用户最小推文数用户平均推文数Ｐ－ｖａｌｕｅ（一致性）Ｐ－ｖａｌｕｅ（传染性）Ｏｓａｍａ　 ０５０１　 ４６８０　 １３０９　 ６９　 １　 ４２　 ２　 ３．６５　 ４．７８Ｅ－１２５　 １．８２Ｅ－３３Ｊｏｐｉｎ　 ０５２２　 ２８９６　 １０８２　 ６８　 １　 ９３　 １　 ２．６８　 ２．１０Ｅ－９８　 ６．６０Ｅ－０９Ｍａｖｓ　 ０６１２　 ３８５９　 １７８０　 ７６　 １　 ９２　 １　 ２．１８　 ９．０１Ｅ－２１１　 ８．０９Ｅ－０８Ｗｅｉｎｅｒｇａｔｅ　 ０６１６　 １２７８　 ８８５　 ５２　 １　 １１　 １　 １．４５　 ４．６２Ｅ－１９　 ５．１７Ｅ－１０Ｂｅｔａｗａｒｄｓ　 ０６２６　 ７８７　 ２００　 １６　 １　 ５７　 １　 ３．９４　 ２．１０Ｅ－２７　 ３．６２Ｅ－０５Ｃａｓｅｙ－Ａｎｔｈｏｎｙ　 ０７０５　 ６２４１　 １３１８　 ７４　 １　 １８０　 ２　 ４．７４　 ５．６６Ｅ－９７　 １．５９Ｅ－２７Ａｓｏｂａｍａ　 ０７０６　 ４８８８　 ２００９　 １４２　 １　 ６３　 １　 ２．４３　 ５．３２Ｅ－９９　 ９．８１Ｅ－０６Ａｔｌａｎｔｉｓ　 ０７０８　 ２５１５　 ７１２　 ４７　 １　 ２１　 ２　 ３．５３　 １．０１Ｅ－７２　 １．４４Ｅ－１４Ｈａｒｒｙｐｏｔｔｅｒ　 ０７１５　 ２７６０　 ８６５　 ３７　 １　 ２６　 ２　 ３．１９　 ３．４１Ｅ－８９　 ２．２４Ｅ－１０ＷＷＣ　 ０７１７　 ３６４２　 ２１０３　 ２１９　 １　 ２５　 １　 １．７３　 ３．０８Ｅ－５４　 １．０５Ｅ－０８Ｏｓｌｏ　 ０７２２　 ４５７１　 １０２６　 ７７　 １　 ５６　 ２　 ４．４６　 ２．６２Ｅ－１３１　 ４．９８Ｅ－１９ＳＤＣＣ　 ０７２２　 ５８１７　 ４４２　 ８１　 ２　 １６１　 ２　 １３．１６　 ３．２１Ｅ－１４３　 １．３１Ｅ－１１３．３　社会学理论验证分析社会学理论，尤其是一致性［２６］和传染性［２７－２８］，１１８７ 计　　算　　机　　学　　报 ２０１９年① ｈｔｔｐｓ：／／ｗｉｋｉ．ｅｎｇｒ．ｉｌｌｉｎｏｉｓ．ｅｄｕ／ｄｉｓｐｌａｙ／ｆｏｒｗａｒｄ／Ｄａｔａｓｅｔ－ＵＤＩ－ＴｗｉｔｔｅｒＣｒａｗｌ－Ａｕｇ２０１２任务中被证明是有用的．社会学理论指出社会网络中成员之间通常会展现出相关的行为，情感和话题都会随着网络进行传播．一致性一般认为，同一个人在短时间内表现出的社会行为具有一致性；传染性一般认为，具有朋友关系的两个人可以对彼此产生影响．本节我们主要考查对于每个话题集，社会学理论是否 存在，并且给出验证方法．首先对于我们的任务，重 新定义了一致性和传染性：（１）表达一致性．同一用户所发的两个推文在内容上是否比随机选择的两个推文更相似？（２）表达传染性．具有朋友关系的两个用户所发的推文在内容上是否比随机 选择的两个推文更相似？为了验证这两个问题，我们给出计算两个推文距离的公式Ａｉｊ＝ ｔｉ－ｔｊ　 ２，其中ｔｉ，ｔｊ分别为第ｉ，ｊ条推文的向量表示．两个推文越相似，Ａｉｊ越接近０．对于第一 个 问 题，我 们 构 建 两 个 维 度 一 致 的 向 量ｃｏｎｓｃ和ｃｏｎｓｒ．第一个向量的每一维是通过计算同一用户所发两条推文的距离得到，第二个向量的每一维是通过计算两条随机选择推文的距离得到．然后对这两个向量做双样本 Ｔ 检 验，并 设 置 空 假 设为，两个向量并无很大差异，即 Ｈ０：ｃｏｎｓｃ＝ｃｏｎｓｒ；备择假设为，同一用户所发的两条推文在距离上比随机选择的两条推文更小，即 Ｈ１：ｃｏｎｓｃ＜ｃｏｎｓｒ．类似地，为了验证第二个问题，我们构建了两个维度一致的向量ｃｏｎｔｃ和ｃｏｎｔｒ．第一个向量的每一维是通过计算具有朋友关系的用户所发两条推文的距离得 到，第 二 个 向 量 的 每 一 维 是 通 过 计 算 随机选择的两条推文的距离得到．我们同样在这两个向量上做双样本 Ｔ 检验．设置空假设为 Ｈ０：ｃｏｎｔｃ＝ｃｏｎｔｒ，即两个朋友关系的用户所发推文的距离与随机选择两条推文的距离并无很大差异．备择假设为Ｈ１：ｃｏｎｔｃ＜ｃｏｎｔｒ，表示两个朋友关系的用户所发的推文在距离上比随机选择的两条推文更小．对于所有的话题集，一致性空假设和传染性空假设都以置信度α＝０．０１（两种社会学理论在所有数据集中均以超过 ９９％ 的概率存在）的水平 被 排斥，其中 Ｐ－ｖａｌｕｅｓ在表 １ 的最后两列呈现．该验证分析说明，两种社会学理论在数据集中是真实存在的，这为在推特摘要优化建模中融入社会媒体信息传播的一致性和传染性奠定了基础．４　ＳＮＳＲ总体框架４．１　推特摘要的组稀疏模式挖掘压缩感知理论认为，自然信号一般是稀疏且可压缩的．稀疏重构的思想与稀疏编码（Ｓｐａｒｓｅ　Ｃｏｄｉｎｇ）类似，来源于压缩感知理论．即原始信号可由一组基向量来表示，通过约束最小化重构误差，找到最具有代表性的基向量，其张开的子空间可以很好地表示原始信号的空间．这种思想被广泛应用于信号处理、图像或视频压缩等领域，比如针对图像压缩，一方面通过观察基像素点即可了解原始图像的大致内容；另一方面通过保存基像素点和重构矩阵，即可最大地还原原始图像，使得对于超大规模图像的保存，可以大大节省空间消耗．推特摘要任务的目标与稀疏重构的思想不谋而合．从推文集中抽取简洁、核心的代表信息形成摘要，通过阅读摘要即可了解原始数据集的概要内容，也相当于是对原始文本集的一种压缩处理．特别地，对于抽取式推特摘要方法，可以把原始推文（句子）集看作信号，那么推特摘要的任务就是从原信号中寻找能最好地重构其的样本子空间，即一组推文基向量，使得这组推特摘要句子可以最大化地重构原始推特文本集．对于给定的推特语料 Ｃ，其可以表示为文本矩阵Ｓ∈!ｍ×ｎ．对于第ｉ个推文ｔｉ∈Ｓ，可以通过其他推文的线性组合形式化表示为ｔｉ＝∑ｎｊ＝１ｃ（ｊ）Ｗｊｉｔｊ （１）为了更好地解释文摘句选择的物理含义，式（１）中ｃ（ｊ）＝０表示第ｊ个推文ｔｊ不是摘要推文，ｃ（ｊ）＝１表示第ｊ个推文ｔｊ最终被选为摘要推文．对于抽取式摘要，假设我们最终需要抽取ｋ条推文形成摘要，则有∑ｎｊ＝１ｃ（ｊ）＝ｋ．Ｗｊｉ表示推文ｔｊ在重构推文ｔｉ时的权重，其值越大表示在重构推文ｔｉ时所占的比重越大．由于每一个推文向量ｔｉ是通过计算 ＴＦ－ＩＴＦ 得到的，每一个维度均为非负值，故需要对 Ｗｊｉ增加非负约束．除此之外，我们需要增加额外的约束 Ｗｉｉ＝０来避免句子自身重构自身的现象，否则会导致其重构系数接近于０，Ｗｉｉ接近于１，以至于失去稀疏重构原本的意义．因此，基于稀疏重构的推特摘要方法的目标函数可以表示为６期 贺瑞芳等：基于社会媒体内容和网络拓扑的特定话题推特摘要研究１１９７ｉ－∑ｎｊ＝１ｃ（ｊ）Ｗｊｉｔｊ２２满足ｃ∈｛０，１｝ｎ，∑ｎｊ＝１ｃ（ｊ）＝ｋ （２）ｉ∈｛１，２，…，ｎ｝Ｗｉｉ＝０ｉ，ｊ∈｛１，２，…，ｎ｝Ｗｊｉ０式（２）可以进一步用矩阵形式来表示：ｍｉｎ１２Ｓ－ＳＤ（ｃ）Ｗ２Ｆ满足ｃ∈｛０，１｝ｎ，∑ｎｊ＝１ｃ（ｊ）＝ｋ （３）ｄｉａｇ（Ｗ）＝０，Ｗ ０式（３）中Ｓ 表示文本矩阵，Ｄ（ｃ）是一个对角矩阵，第ｉ行对角 元 素 的 值 对 应 于ｃ（ｉ）的 取 值，Ｗ ＝［Ｗ＊１，Ｗ＊２，…，Ｗ＊ｎ］∈!ｎ×ｎ是 一个重构系数矩阵，每一列Ｗ＊ｊ＝［Ｗ１ｊ，Ｗ２ｊ，…，Ｗｎｊ］是重构推文ｔｊ的系数向量．Ｗ ０ 保证矩阵元 素非负，再加上约 束ｄｉａｇ（Ｗ）＝０，即可保证对角线的每一个元素为０，即Ｗｉｉ＝０．由于ｃ向量的约束，使得目标函数式（３）的优化是一 个 混 合 线 性 规 划 问 题，求 解 非 常 困 难．鉴 于Ｄ（ｃ）的对角线只有有限多个１，而多数取值为０，使Ｄ（ｃ）Ｗ 所得矩阵中会有很多整行为 ０的情况．令Ｗ＝Ｄ（ｃ）Ｗ，并通过对Ｗ 添加２，１范数约束，即组稀疏正则项，可以确保 Ｗ 的行稀疏性，从而近似模拟Ｄ（ｃ）Ｗ 的行选择过程．由于Ｗｉ＊＝［Ｗｉ１，Ｗｉ２，…，Ｗｉｎ］中的每一维表示第ｉ条推文 重构其他 推 文 时 的 权重，当第ｉ行元素全部为０时，表示该推文在重构整个语料中的重要性比较低，也就很大概率不会被选择为摘要推文，所以对Ｗ 的行选择可以认为是对推文的选择．实际上，若是去掉 Ｄ（ｃ）的相关表达，直接加组稀疏约束建模效果是等价的，对运算过程没有影响．式（３）可以重新改写为ｍｉｎＷ１２Ｓ－ＳＷ　２Ｆ＋λ Ｗ ２，１ （４）满足ｄｉａｇ（Ｗ）＝０，Ｗ ０式（４）中λ为组稀疏正则项参数，Ｗ ２，１＝∑ｎｉ＝１Ｗｉ＊ ２，Ｗｉ＊ ２＝∑ｎｊ＝１Ｗ２ｉ槡ｊ．由此通过组稀疏学习的约束可以实现挖掘推文集中的摘要推文组的潜在模式，使得摘要推文从全局角度保证了一定的非冗余性．４．２　建模推文层次的网络结构为了减少重构误差，并且在重构过程中做出纠正，我们使用社会学理论建模推文层次的网络结构信息，并作为社会正则项整合到稀疏重构的优化框架中．源于 Ｇｒａｐｈ　Ｌａｓｓｏ［２９］思想的启发，也就是说，对于两条相关连的推文，由于其本来距离就很接近，需要让它们在重构过程中依旧保持相似．为了利用社交网络结构做推特摘要，我们使用之前提到的社会学理论来构建推文层次的 网络结构．具体地，需要把给定的用户 －推文矩阵Ｕ 和用户－用户矩阵Ｆ 转换为推文－推文矩阵：（１）通过表达一致性理论构建的推文 －推文关联矩阵定义为Ｔｃｏｎｓ＝ＵＴＵ，其中Ｔｃｏｎｓ＝１表示两条推文是同一用户所发；（２）通过表达传染性理论构造的推文 －推文关联矩阵被定义为Ｔｃｏｎｔ＝ＵＴＦＵ，其中Ｔｃｏｎｔ＝１表示两条推文是具有朋友关系的用户所发．然后，我们通过线性组合这两种矩阵，最终得到推文 －推文关联矩阵为Ｔ＝Ｔｃｏｎｓ＋ｂＴｃｏｎｔ，其中ｂ是这两种矩阵的平衡参数．理论上，ｂ值越大，说明传染性的影响越大，两个具有朋友关系的用户所发的推特越接近，在公式上表现为尽可能拉近推特的距离，避免重构误差（亦即本来距离较近的两条推特，在重构后距离拉大，加上该约束可以拉近距离，纠正重构偏差）．ｂ值越小，说明传染性的影响越小，具有朋友关系的用户所发推特越容易避免被强制拉近．至于ｂ取大取小，取决于数据集本身的网络特性（传染性），是一个可调节的参数．实验时我们简单取ｂ＝１，当然也可以对ｂ的不同取值作分析．Ｔｉｊ＝１表示两条推文是有关联的，否则没有关联．我们定义Ｓ 的重构矩阵为Ｓ＾＝ＳＷ，那么 ＧｒａｐｈＬａｓｓｏ惩罚项，即社会正则项可以表示为Ωｇｒａｐｈ＝１２∑ｎｉ＝１∑ｎｊ＝１Ｔｉｊ Ｓ＾＊ｉ－Ｓ＾＊ｊ２２＝∑ｍｉ＝１Ｓ＾ｉ＊Ｄ－Ｔ　Ｓ＾Ｔｉ＊＝ｔｒ（ＳＷＬＷＴＳＴ） （５）其中，ｔｒ（·）表示矩阵的迹，Ｌ＝Ｄ－Ｔ 是拉普拉斯矩阵，Ｄ∈!ｎ×ｎ是对角矩阵，而且 Ｄｉｉ＝∑ｎｊ＝１Ｔｉｊ，每一个对角元素表示推文节点在图中的度．通过整合式（５）到式（４），可以得到：ｍｉｎＷ１２Ｓ－ＳＷ　２Ｆ＋α２ｔｒ（ＳＷＬＷＴＳＴ）＋λ Ｗ２，１（６）满足 ｄｉａｇ（Ｗ）＝０，Ｗ ０其中，α 是社会正则项参数，式（６）产生了将社会媒１１０８ 计　　算　　机　　学　　报 ２０１９年相融合的基于稀疏重构的推特摘要框架．４．３　社会网络传播带来的强冗余信息建模去冗余 一 直 是 摘 要 研 究 的 重 点．社 会 研 究 表明［２８］，社会网络中的互惠关系以及某些三元结构大大增加了社会传染性，这将导致在某个特定的网络结构中，会带来更多的冗余以及缺乏新颖性的信息．因此，相较于传统摘要研究，推特摘要面临更严峻的去冗余问题．目前存在一些考虑多样性来选择摘要的研究．最 具 代 表 性 的 方 法 称 为 最 大 边 缘 相 关 性（Ｍａｘｉｍａｌ　Ｍａｒｇｉｎａｌ　Ｒｅｌｅｖａｎｃｅ，ＭＭＲ）．该方法一般是在推文排序后使用，通过综合考虑相关度与冗余度进行句子选择，其作为额外的步骤来实施，而不是模型的一部分．基于话题的方法可以发现语料中的子话题，同时在某种程度上解决了多样性问题．但是这类方法存在一些关键挑战：评估推文在每个子话题的重要性，评估每个子话题在整个语料的重要性，子话题之间的去冗余（比如，由于划分粒度较小，使得两个子话题很类似）．基于稀疏重构的摘要方法倾向于从语料层面选择重要的句子，但是没有明显的倾向会包含语料的各个方面．这类工作已有的针对多样性的研究包括：Ｌｉｕ等人［１１］引入一个相关性项来控制多样性，但是他们的模型求解过程比较复杂；Ｙａｏ等人［１２］引入了一个不相似度矩阵，大大地降低了计算复杂度．然而他们计算该不相似度矩阵的方法并不适用于推特语料，一方面是由于推特语料的嘈杂、不规范；一方面他们使用句子长度或者词汇库大小来计算每个单词的编码损失，这种计算方法使得不相似度矩阵中的每个元素都很大，导致Ｗ 的每个元素都接近于０，不容易区分句子的重要性．受到该不 相 似 度 矩 阵 的 启 发，本 文 提 出 相 对简单但 却 很 有 效 的 余弦相似度矩阵对社会媒体传播引发的强冗余信息建模．对于 每 个 元 素 ｉｊ∈［０，１］表示推文ｔｉ和推文ｔｊ的余弦相似度．在稀疏重构的过程中，我们添加约束ｄｉａｇ（Ｗ）＝０来避免自身重构自身的现象，基于这种认识，我们有理由避免推文被那些与其极为相似的推文重构．例如下面这个例子：（１）Ｔｗｅｅｔ１：ｔｈｅ　ｍｏｏｄ　ｗａｓ　ｓｏｌｅｍｎ　ａｔ　ｔｈｅ　ｇａｒｄｅｎ　ｏｆｒｅｆｌｅｃｔｉｏｎ　ｉｎ　ｌｏｗｅｒ　ｍａｋｅｆｉｅｌｄ　ｆｏｌｌｏｗｉｎｇ　ｔｈｅ　ｄｅａｔｈ　ｏｆ　ｏｓａｍａ　ｂｉｎｌａｄｅｎ．ｖｉｄｅｏ：ｈｔｔｐ：／／ｆｂ．ｍｅ／ｔｏｆ３ｐｑｏｋ（２）Ｔｗｅｅｔ２：ｔｈｅ　ｍｏｏｄ　ｗａｓ　ｓｏｌｅｍｎ　ａｔ　ｔｈｅ　ｇａｒｄｅｎ　ｏｆｒｅｆｌｅｃｔｉｏｎ　ｉｎ　ｌｏｗｅｒ　ｍａｋｅｆｉｅｌｄ　ｆｏｌｌｏｗｉｎｇ　ｏｓａｍａ　ｂｉｎ　ｌａｄｅｎ’ｓｄｅａｔｈ．ｖｉｄｅｏ：ｈｔｔｐ：／／ｂｉｔ．ｌｙ／ｌ９ｔｖｄｗ显然这 两 条 推 文 很 相 似，这 会 导 致 重 构 系 数Ｗ１２和Ｗ２１都接近于１，从而导致提高了这两条推文在整个语料的重要性的问题．通过初步的实验，我们观察到，倘若不加多样性约束，在生成的最终摘要中会存在很多这种相似推文．为了更好地避免这种“相似”的重构现象，我们重新计算为ｉｊ＝１， 若ｉｊθ０，烅烄烆否则（７）式（７）中θ是用来区分相似推文对和常规推文对的阈值．由此进一步建模推特摘要的多样性，并提出多样性正则项的表达形式：ｔｒ（ＴＷ）＝∑ｎｉ＝１∑ｎｊ＝１ｉｊＷｉｊ．并整合到式（６）中得到最终的目标函数为ｍｉｎＷ１２Ｓ－ＳＷ　２Ｆ＋α２ｔｒ（ＳＷＬＷＴＳＴ）＋　　γｔｒ（ＴＷ）＋λ Ｗ２，１（８）满足ｄｉａｇ（Ｗ）＝０，Ｗ ０其中，γ 是 多样性正 则项参数．通 过 优化目标函 数式（８），可以得到重构的系数矩阵 Ｗ．每条推文的重要性分数可以通过下式得到：Ｓｃｏｒｅ（ｔｉ）＝ Ｗｉ＊ ２（９）依据重要性分数对推文进行排序，最后筛选前几条推文形成最终摘要．５　优化的推特摘要算法５．１　算　法由于 Ｗ２，１不可导，所以目标函数式（８）是非平滑的．受到 前 人 工 作［２２，３０－３１］的 启 发，本 文 提 出 基 于Ｎｅｓｔｅｒｏｖ加速梯度下降的摘要优化算法．针对该非平滑优化问题的解决方法，目标函数可以被等价的表示为　ｍｉｎＷｆ（Ｗ）＝１２Ｓ－ＳＷ　２Ｆ＋α２ｔｒ（ＳＷＬＷＴＳＴ）＋　　γｔｒ（ＴＷ） （１０）满足Ｚ＝｛Ｗ｜Ｗ ０，ｄｉａｇ（Ｗ）＝０，Ｗ２，１ｚ｝式（１０）中ｚ是２，１球的半径，并且λ和ｚ 具有一对一的映射关系．由于任意范式都定义了一个凸集，故Ｚ 是一个封闭的凸集．由此，我们的问题转换为定义域为封闭凸集、目标函数为凸函数的凸优化问题．接下来，我们阐述本文基于 Ｎｅｓｔｅｒｏｖ加速投影６期 贺瑞芳等：基于社会媒体内容和网络拓扑的特定话题推特摘要研究１１１８梯度下降的优化算法，可以用来解决式（１０）中带约束的凸优化问题．首选不考虑式（１０）中带约束Ｗ∈Ｚ 的优化问题：ｍｉｎＷｆ（Ｗ）．我们知道，通过梯度下降，Ｗｔ＋１可以通过式（１１）更新：Ｗｔ＋１＝Ｗｔ－１ｌｒｆ′（Ｗｔ） （１１）其中，ｌｒ表示学习率，ｌｒ的值根据 Ａｒｍｉｊｏ－Ｇｏｌｄｓｔｅｉｎ［３２］规则通过线搜索（Ｌｉｎｅ　Ｓｅａｒｃｈ）方法得到．ｆ′（Ｗ）表示目标函数ｆ（Ｗ）对Ｗ 的求导：ｆ′（Ｗ）＝ＳＴＳＷ－ＳＴＳ＋γ＋αＳＴＳＷＬ （１２）优化问题中的平滑部分可以等价地改写为线性函数ｆ（Ｗ）在Ｗｔ处的近端正则，表示为Ｗｔ＋１＝ａｒｇ　ｍｉｎＷＧｌｒ，Ｗｔ（Ｗ），其中，Ｇｌｒ，Ｗｔ（Ｗ）＝ｆ（Ｗｔ）＋〈ｆ′（Ｗｔ），Ｗ－Ｗｔ〉＋ｌｒ２Ｗ－Ｗｔ２Ｆ（１３）考虑到我们优化问题的等价形式以及约束项Ｚ，我们可以通过以下迭代公式得到最终解：Ｗｔ＋１＝ａｒｇ　ｍｉｎＷ ∈ＺＧｌｒ，Ｗｔ（Ｗ） （１４）通过忽视式（１３）中独立于Ｗ 的项，式（１４）可以归约为Ｗｔ＋１＝ｍｉｎＷ∈Ｚ１２Ｗ－Ｕｔ２Ｆ（１５）其中，Ｕｔ＝Ｗｔ－１／ｌｒｆ′（Ｗ），则 Ｗ 表示Ｕ 在凸集Ｚ上的欧几里得投影（Ｅｕｃｌｉｄｅａｎ　ｐｒｏｊｅｃｔｉｏｎ）：式（１５）可以分解为ｎ个子问题：ｗｊｔ＋１＝ｍｉｎｗｊ∈ｚｊ１２ｗｊ－ｕｊｔ２２（１６）其中，ｕｊｔ，ｗｊ，ｗｊｔ分别表示矩阵Ｕｔ，Ｗ，Ｗｔ的第ｊ行．给定λ，通过欧几里得投影得到的解的形式为ｗｊｔ＝１－λｌｒ　ｕｊ（ ）ｔｕｊｔ， 若 ｕｊｔλｌｒ０，烅烄烆否则（１７）上述方法的收敛速度为 Ｏ（１／ｋ），而 Ｎｅｓｔｅｒｏｖ方法加速了该优化过程，使收敛速度达到 Ｏ（１／ｋ２），其中ｋ表示迭代次数．Ｎｅｓｔｅｒｏｖ方法基于两个序列｛Ｗｔ｝和｛Ｖｔ｝，其中｛Ｗｔ｝是近似解序列，｛Ｖｔ｝是搜索点序列．｛Ｖｔ｝是｛Ｗｔ｝和｛Ｗｔ－１｝的结合：Ｖｔ＝Ｗｔ＋!（Ｗｔ－Ｗｔ－１），其中，! 是结合系数．Ｕｔ可以由｛Ｖｔ｝通过类似“梯度”更新的方法计算得到，所以Ｕｔ可以重新计算为Ｕｔ＝Ｖｔ－１ｌｒｆ′（Ｗ）．详细的算法过程见算法１．算法１．　基于 ＮＡＧ 的模型优化算法．输入：Ｓ，Ｕ，Ｆ，，Ｗ０，α，γ，λ，θ，ε输出：Ｗ１．初始化μ０＝０，μ１＝１，Ｗ１＝Ｗ０，ｌｒ＝０．１２．Ｔ＝ＵＴＦＵ＋ＵＴＵ，Ｌ＝Ｄ－Ｔ，＝θ３．ＦＯＲｉｔｅｒ＝０，１，２，…，ＤＯ４．　Ｖ＝Ｗ１＋（μ０－１）（Ｗ１－Ｗ０）／μ１５．　ｆ′（Ｗ）＝ＳＴＳＷ１－ＳＴＳ＋γ＋αＳＴＳＷ１Ｌ６．　ＬＯＯＰ７．　　Ｕ＝Ｖ－１／ｌｒｆ′（Ｗ）８．　　ＦＯＲ　ｅａｃｈ　ｒｏｗＵｉ＊ ｏｆ　Ｕ　ＤＯ９．　　　Ｗｉ＊＝Ｓλ／ｌｒ（Ｕｉ＊）／／使用式（１７）解决１０．　　ＥＮＤＦＯＲ１１．　　Ｗ＝Ｗ－ｄｉａｇ（Ｗ），Ｗ＝ｍａｘ（Ｗ，０）１２．　　ＩＦ　ｆ（Ｗ）Ｇｌｒ，Ｖ（Ｗ）ＴＨＥＮ１３．　　　ｂｒｅａｋ１４．　　ＥＮＤＩＦ１５．　　ｌｒ＝２×ｌｒ１６．　ＥＮＤＬＯＯＰ１７．　Ｓｅｔ　ｆｕｎＶａｌ（ｉｔｅｒ）＝ｆ（Ｗ）＋λ Ｗ２，１１８．　ＩＦ｜ｆｕｎＶａｌ（ｉｔｅｒ）－ｆｕｎＶａｌ（ｉｔｅｒ－１）｜εＴＨＥＮ１９．　　ｂｒｅａｋ２０．　ＥＮＤＩＦ２１．　Ｗ０＝Ｗ１２２．　Ｗ１＝Ｗ２３．　μ０＝μ１２４．　μ１＝（１＋ １＋４槡μ２１）／２２５．ＥＮＤＦＯＲ算法中第３到第２５行描述了用 Ｎｅｓｔｅｒｏｖ方法解决 优 化 问 题 式 （８），第 ６ 到 第 １６ 行 描 述 了 用Ａｒｍｉｊｏ－Ｇｏｌｄｓｔｅｉｎ规则通过线搜索得到学习率ｌｒ，第２４行μ１的值依据［３３］所提到的方法得到，这里，μ０和μ１均为 Ｎｅｓｔｅｒｏｖ梯度下降法中计算步长的辅助变量．通过该算法可以解决我们模型的优化问题，并通过式（９）计算每条推文的重要性以形成摘要．５．２　收敛性及时间复杂度分析收敛性：对于 Ｎｅｓｔｅｒｏｖ加速梯度下降算法，通过在搜 索 点Ｖｔ执 行 梯 度 下 降 而 不 是 在 近 似 点 Ｗｔ执行梯度下降，收敛率可以达到Ｏ　１／ｋ（ ）２，其中ｋ为迭代次数，同 时 可 以 得 到 算 法 的 理 论 迭 代 次 数 为Ｏ（１／槡ε），其中ε表示收敛阈值．该结论可以通过如１１２８ 计　　算　　机　　学　　报 ２０１９年