欢迎访问一起赢论文辅导网
本站动态
联系我们

手机:15327302358
邮箱:peter.lyz@163.com

Q Q:
910330594  
微信paperwinner
工作时间:9:00-24:00

博士论文
当前位置:首页 > 博士论文
基于社会媒体内容和网络拓扑的特定话题推特摘要研究
来源:一起赢论文网     日期:2020-03-07     浏览数:227     【 字体:

 weets as sentences,and adopt traditional summarization methods,such asSumBasic,Centroid,LexRank to validate the relevant performance on microblogging posts.However,it is not clear whether adding the complexity of methods will improve the systemperformance.Some other researches explore to utilize static social features except for textualcontent,such as number of replies,number of retweets,number of likes,author popularity andtemporal signals.These methods rarely consider the data sparsity,the strong social redundancyand the potential social relations between tweets explicitly,ignoring the fact that information canspread along the social network.Inspired by compressive sensing and social theories,we proposea novel approach for Twitter summarization based on Social Network and Sparse Reconstruction(SNSR)for integrating social media content and structure information.The social analysisindicates that the members in a social network often exhibit correlated behaviors,sentiment andtopic can be diffused through network.Consistency means that social behaviors conducted by thesame person keep consistent in a short period of time.Contagion means that friends can influenceeach other.We explore whether social relations(expression consistency and expression contagion)can help Twitter summarization under a given topic,modeling relations between tweets describedas the social regularization and integrating it into the group sparse optimization framework.Itconducts a sparse reconstruction process by selecting tweets that can best reconstruct the originaltweets,with considering coverage and sparsity.We simultaneously design the diversity regularizationto remove the strong redundancy brought by social information propagation.In particular,wepresent a mathematical optimization formulation and develop an efficient Twitter summarizationalgorithm with Nesterov’s accelerated gradient descent.Meanwhile,due to the lack of publiccorpus,we construct the gold standard tweet summary datasets for 12different topics by asking24volunteers to manually select the most informative tweets,all in 48expert summaries.Experi-mental results on this datasets show the effectiveness of our approach for handling the large scaleshort and noisy messages in social media.It suggests that integrating social network informationinto the proposed sparse reconstruction framework helps improve Twitter summarization.Miningthe group sparsity patterns of salient tweets and designing the diversity regularization in terms ofredundancy brought by social network are also effective.Keywords  Twitter summarization;sparse reconstruction;network topology;social theories;Nesterov’s accelerated gradient descent algorithm1 引 言社会媒体的繁荣改变和影响了人们获取和发布信息的方式.本文研究面向特定话题的推特摘要,旨在从事件相关的社会媒体短文本中提炼简洁、核心的推文集,以捕捉有效信息,可用于竞争情报分析、电子商务等;同时,也可协助政府监管危机事件,从而降低灾难损失、给出有益的反馈,并把控舆情方向.尽管传统的文本摘要技术发展了很多年,但是新兴的社会媒体平台产生了大规模嘈杂且不规范的碎片化短文本,为社会媒体摘要研究带来了诸多挑战,然而也带来了新的机遇.现有的推特摘要方法通常将推文看作句子,对其进行重要性打分并筛选推文集.包括:(1)利用传统的文本摘要方法[1],即仅考虑文本信息,这些方法包括SumBasic[2]、Centroid[3]、LexRank[4]和 TextRank[5]等;(2)利用社交媒体平台的静态特 性[6-7],包括推文转发数、回复数、点赞数、用户权威特性(粉丝数、关注数等)、时间特性、地理特性等;但这些方法忽略了社会媒体短文本是网络互联的;(3)利用社交媒体平台的动态特性[8-9],即社会网络结构信息,包括转发关系、回复(Reply)关系、关注(Follow)关系等.但该类研究主要是从用户层次考虑网络结构,一般认为高权威度用户所发的推文同样具有很高的重要性.然而,通过用户之间的社会网络连接可以推测,推文之间也存在潜在的6期 贺瑞芳等:基于社会媒体内容和网络拓扑的特定话题推特摘要研究1157计算推文相似度使得推文之间互相关联的传统方法,该方法仅仅利用了纯文本信息.通过社会网络结构构建推文层面的相互关联网络结构可能包含更多的语义线索.因此,本文需要探索一种建模推文层面网络信息互联的新方法,以进行推特摘要.社会学理论揭示了互联信息的这种相互影响的现象.人们在短时间内更倾向于保持一致的情感、爱好,这种现象称之为一致性.除此之外,人们通过一系列交互和反馈行为在彼此之间建立了联系,这层联系对彼此产生的影响是微妙的,可以对一个人的爱好、说话方式或者表达内容产生重大的影响.人们渐渐会和好友在某个话题上保持相似的观点,甚至以相似的语调和用词来表达这些观点,这种现象称之为传染性.受到这两种社会学理论的启发,本文将进一步探索如何利用这两种理论做推特摘要.近年来,基于数据重构的摘要方法被提出[10-12],并且在传统评测任务 DUC/TAC 上表现出色,但其并不能直接迁移到社会媒体情景中.也正是由于之前提到的社会学理论可与基于数据重构的方法无缝结合,本文从压缩感知、稀疏重构角度出发,将推文看作一种信号,提出了整合社交网络结构信息统一的推特摘要优化框架.其综合考虑了一个好的推特摘要应该具备的几个特性:(1)覆盖性(Coverage),即一个好的摘要应该尽可能包含整个语料谈论话题的各个方面;(2)稀疏性(Sparsity),即假设信号是稀疏可压缩的,摘要只是原推特语料的一部分.假设每个句子可以由所有其他句子通过非负线性组合来表示,那么不是所有句子在表示该句子的过程中都占有很大比重.摘要句子即是这样一组句子基,通过这组句子基张成的子空间,可以表示整个语料的其它句子,从而以尽 可能小 的误差重构原始语料;(3)多样性(Diversity),即保证摘要句子之间的冗余度尽可能小.主要贡献如下:① 从统计学角度验证了两种社会学理论的存在,即表达一致性和表达传染性;形式化地定义了整合社会网络结构的推特摘要框架.② 建模了推文层面的网络结构信息,并作为社会项正则整合到基于稀疏重构的优化框架中.③ 引入组稀疏正则可以从语料层面选择重要的推文,引入多样性正则可以缓解由于社交网络的引入而带来的更加严峻的冗余度问题.④ 构建了推特摘要语料,包括12 个特定话题数据集以及每个数据集对应的四个专家摘要.本文第2节综合分析和讨论相关工作;第3节给出问题阐述和数据分析,并进行社会学理论的验证;第4节详细论述本文提出的基于稀疏重构和社会网络结构的社会媒体推特摘要方法;第5节给出基于 Nesterov加速梯度下降的摘要优化算法;第6节介绍真实数据集上推特摘要的标准语料 制作方案,并在此基础上验证本文方法的有效性;第7节进行总结和展望.2 相关工作社会媒体平台的产生、成长经历近10年时间.它的繁荣催生了以推特摘要为代表的社会媒体摘要研究,其部分地传承了传统文本摘要方法.现有的自动摘要方式一般 可分为 两 大类:抽取式 和 理解式.(1)抽取式摘要从原始语料中抽取一部分句子形成摘要,可以保证摘要句子的可读性,但是摘要句子之间以及摘要句子内部会产生冗余信息;(2)理解式摘要通常采用句子压缩、融合、改写等自然语言处理技术实现,在技术难度上比较大.故当前文本摘要研究大多数还是基于抽取式的研究路线.同时,由于推特文本的碎片化、不规范性以及大量噪声,使得理解式摘要方法中的语法分析、句法分析等底层技术难以发挥作用.因此,本文采取抽取式摘要路线,相关工作的调研也围绕此展开.2.1 传统文本摘要产生文本摘要的过程通常可以描述为:句子重要性打分、句子筛选、摘要句子排序这三个过程.如何对句子进行重要性打分是摘要研究的重点.已有的方法包括:(1)基于特征的方法,例如 Centroid和SumBasic[2-3],这些方法考虑了词频和句子位置信息来计算句子的权重;(2)基于图的方法采用了类似PageRank的算法,例如 LexRank和 TextRank[4-5],以句子或词作为节点,句子或词之间的相似度作为构建图中边权重的依据,利用随机游走的思想最终得到句子或词的重要性.然而,该类方法面临去冗余的问题.一些研究者开始利用(3)基于聚类的思想来保持摘要的多样性[13-18].其主要采用主题建模、聚类算法以及矩阵分解的思想来产生覆盖性更高的摘要.最近,(4)基于数据重构的摘要方法的出现[10-12],为解决摘要研究中存在的经典问题,即覆盖性、重要性及多样性,带来了新的可能性.然而由于社交媒体中大规模的文本具有简短、嘈杂及其附带的社会特性,使得这些传统方法不能很好地发挥作用.1167 计  算  机  学  报 2019年展使得人们不断探索传统摘要方法在 类 似 推 特 平 台 上 的 应 用.这 些 方 法 包 括(1)Hybrid TF-IDF[1],其针对推特短文本语料对经典的 TF-IDF 模 型 进 行 变 种,在 计 算 IDF(InverseDocument Frequency)的时候是把每个帖子看成一个文档,在计算 TF(Term Frequency)的时候是把所有帖子看成一个大文档;(2)短语强化算法[19-20],其通过不断选择使用频率最高的短语,最终生成摘要句子.这些方法仅考虑了文本信息.然而,社交媒体平台还包含除文本信息之外的大量丰富信息,比如推文转发数、回复数、用户粉丝数、关注数、时间、地理信息,以及社交网络结构等信息;(3)基于社会网络静 态 信 息 和 用 户 层 面 网 络 结 构 的 推 特 摘 要,Duan等人[9]考查了推文内容质量、用户发文数、粉丝数、粉丝数与关注数的比率等信息,以及通过关注(Follow)关系构建的用户网络结构;Liu等人[7]考查了推文转发数、用户粉丝数以及推文可读性三方面的特性.以上两个工作均采用基于 PageRank 的扩展模型.Alsaedi等人[21]提出了用于事件摘要的三个方法,考查了时间和转发数两个特性.Chang等人[6,8]把推特摘要研 究看成有监督的分类任务,即判断每条推文可否被选择为一个摘要句子.并通过充分挖掘社交媒体中存在的一些特性,包括推文转发数、回复数、点赞数、内容相关度、用户粉丝数、关注数、权威度、时间间隔等,作为分类器的输入特征,从而选择摘要推文.以上方法主要利用了社会网络的静态信息或者用户层面的网络结构,并没有考虑到推文层面的网络结构,而诸如情感、话题、内容等推特信息是可以沿着潜在的网络结构进行传播,本文通过研究这种传播现象,以期获得更多潜在的语义线索进行推特摘要研究.2.3 结合社会网络结构的探索社会学理论以及社会网络分析为我们做推特摘要研究提供了新思路,即如何结合拓扑结构和文本内容做推特摘要.社会网络传播,或者说社交影响力在多个领域都有研究.比如,(1)情感分析[22]认为人们在短时间内对某个话题或事物保持情感一致性,具有朋友关系的两个人在情感上更容易互相影响,并称之为情绪传染性;(2)话题识别[23]认为人们在短时间内对专注的话题会保持一致的偏好,除此之外,具有朋友关系的两个人更有可能对同一话题感兴趣,并称之为社会传染性;(3)话题具体的影响力分析[24]识别特定话题下具有影响力的用户,并对用户关注(Follow)关系中的这种现象进行建模:一部分用户关注其他人是由于对共同话题感兴趣,故粉丝所发内容是会受到关注者所发内容的影响;而一部分用户关注其他用户只是由于热度(粉丝数等),他们所发内容很少受到关注者所发内容的影响.通过将这种现象建模到主题模型中,既可以识别特定话题下具有影响力的用户,同时也可以提升话题检测的性能;以及(4)网络推断和话题模型的联合建模[25]等.根据这些研究可知,情感和话题是可以沿着网络传播的.本文将深入探索作为情感和话题的载体———表达内容是否可以沿着网络进行传播,以及如何影响推特摘要.3 问题陈述与数据分析本文面向特定话题进行推特摘要研究,即输入与某个话题相关的推特文本集,输出若干条重要推文形成摘要并可描述该话题的主要内容.本节首先给出一些符号定义,并正式描述本文推特摘要的整个流程;其次由于缺乏推特摘要的公开语料,本节将介绍语料建设中的数据准备环节,其中专家摘要的制作过程放在实验部分;同时,重新定义两种社会学理论(表达一致性、表达传染性),并在我们的数据集上验证其存在性.3.1 问题陈述本文约定加粗的大写字符表示矩阵(例如 M),加粗的小写字符表示向量(例如 m),小写字符表示标量(例如 m).Mi*和 M*j分别表示矩阵 M 的第i行和第j列.Mij表示矩阵 M 在第i 行第j 列的值.MF表示矩阵的 Frobenius范数,M2,1表示矩阵的2,1范数.特别地,MF=∑mi∑njM2i槡j,M 2,1=∑miMi* 2=∑mi∑njM2i槡j.给定特 定 话 题 的 推 特 语 料,该 语 料 可 表 示 为TF-ITF(Term Frequency Inverse Tweet Frequency)矩阵,即S=[t1,t2,…,tn]∈!m×n,其中 m 表示词汇表大小,n 表示推文数量.S 矩阵的每一列ti为单个推文的向量表示.U∈ !d×n表示用户-推 文矩阵,其中,d 为用户数,Uij=1表示第j条推文是由第i个用户发布.本文根据 Follow 关系构建用户 -用户矩阵F∈!d×d,其中Fij=1表示第i个与第j 个用户是有联系的.依据上面给定的符号,本文的推特摘要任务可6期 贺瑞芳等:基于社会媒体内容和网络拓扑的特定话题推特摘要研究1177在线出版日期:2018-10-15.本课题得到国家自然科学基金面上项目(61472277)和天津市自然科学基金一般项目(18JCYBJC15500)资 助.贺 瑞 芳 (通 信 作 者),博 士,副 教 授,主 要 研 究 方 向 为 自 然 语 言 处 理、社 会 媒 体 挖 掘 及 机 器 学 习.E-mail:rfhe@tju.edu.cn.段兴义,硕士,主要研究方向为自然语言处理、多文本自动摘要.张雪菲,硕士,主要研究方向为自然语言处理、社会计算.赵文丽,硕士研究生,主要研究方向为自然语言处理.基于社会媒体内容和网络拓扑的特定话题推特摘要研究贺瑞芳 段兴义 张雪菲 赵文丽(天津大学智能与计算学部 天津 300350)(天津市认知计算与应用重点实验室 天津 300350)摘 要 推特摘要旨在从话题相关的社会媒体短文本中提炼概要的推文集,以获取有效信息,可用于舆情监控、竞争情报分析及电子商务等.然而社会媒体的海量、嘈杂及不规范性使得仅依赖纯文本的传统摘要方法难以直接迁移到社交媒体情景中;而现有的推特摘要方法很少考虑数据稀疏性和社会网络传播带来的强冗余性,鲜有通过挖掘推文之间潜在的社会网络结构关系进行文摘内容选择,忽略了信息可以沿着社交网络进行传播.受压缩感知及社会学理论的启发,该文提出基于社会网络和稀疏重构的推特摘要方法(SNSR)以更好地融合社会媒体内容和结构信息.首先,挖掘推文中隐含的摘要模式,将其建模为组稀疏正则项,以捕捉代表性的推特摘要组合;其次,建模社会网络中表达一致性与表达传染性为社会化正则项,以探索推文之间的潜在网络结构关系在推特摘要中的作用;再次,建模社会媒体信息传播带来的强冗余性为多样性正则项,进而将这些约束整合到稀疏重构的推特摘要框架中;最后,提出基于 Nesterov加速梯度下降的推特摘要算法,以解决推特摘要优化框架中的覆盖性、稀疏性以及多样性等问题.同时,由于推特摘要标准语料的缺乏,作者建设了12个话题的评测数据集.相关的实验结果证明了文中提出方法的有效性.关键词 推特摘要;稀疏重构;网络拓扑;社会学理论;Nesterov加速梯度下降算法中图法分类号 TP18   DOI号 10.11897/SP.J.1016.2019.01174Topic Oriented Twitter Summarization Based on Social Media Content andNetwork TopologyHE Rui-Fang DUAN Xing-Yi ZHANG Xue-Fei ZHAO Wen-Li(College of Intelligence and Computing,Tianjin University,Tianjin 300350)(Tianjin Key Laboratory of Cognitive Computing and Application,Tianjin 300350)Abstract  Social media platforms,such as Twitter,provide us a very convenient way to accessinformation,through which amounts of users can freely produce content(called tweets)on theirinterested topics.Therefore,it becomes one of the most popular social network.Fast increasingposts make people lost in the ocean of fragmented texts.Twitter summarization aims to extractthe core and concise tweet summary from topic relevant short texts in social media so as to quicklyacquire essential information.It can be used in opinion monitoring,competitive intelligence analysisand electronic commerce,especially in some emergencies,which helps to aid agencies monitorcrisis progress so as to assist recovery and provide disaster relief.Yet traditional summarizationmethods only consider text information,which is insufficient in social media situation with thelarge scale,noisy and informal messages.Previous existing Twitter summarization approaches话题的推特语料C,可以获得文本内容矩阵S、用户 -推文矩阵U 以及用户-用户矩阵F,我们的目标是通过优化模型得到重构系数矩阵 W,并 根 据 W 按 一 定 压 缩 比 自 动 生 成 摘 要Summary≈SW.3.2 数据描述使用公开的推特语料作为原始数据集,其最初由伊利诺伊大学①的一个研究团队所收集.由于集中在 5,6,7 三 个 月 的 数 据 最 多 (数 据 收 集 方 式 所致),我们统计每个月的 Hashtag频数,选择那些频数较大且对应于某个具体事件(一方面可以查看包含该 Hashtag的推文内容是否描述某个事件,一方面可以在浏览器上通过检索时间及 Hashtag,确认是否发生了某个事件)的 Hashtag作为话题标签,利用这些话题标签收集话题数据集.除此之外,每个话题不止一个话题标签,比如“#osama”和“#osamabin-laden”描述的是一个话题.有些推文内容虽然不包含标签信息,但是包含类似“osama”这样的关键词,因此,我们主要根据推文内容是否包含 Hashtag或者除掉“#”号后得到的关键词来收集话题.结合时间信息(每条推文都包含发布时间这一信息)以及上述处理过程,可以得到某个话题的推文数量随时间的变化,通过观察这种时序变化趋势,大致把话题分为热点话题(如图1)和突发话题(如图2)两种.同时考虑到社会学理论中一致性和传染性的短时间效应.进一步做如下处理:若该话题是热点话题,则收集该话题发生前后共五天时间内的推特数据作为该热点话题的数据集(图1);若该话题是突发话题,则收集该话题发生后五天时间内的推特数据 作为该突发话题的数据集(图2).最后筛选得到12个话题,这些话题涉及政治、科技、体育、自然灾害、恐怖袭击和娱乐八卦等领域.得到特定话题的数据集后,需进一步做数据清洗,把满足以下条件之一图 1 哈利波特上映图 2 挪威恐怖袭击的推文过滤掉,最终得到12个话题的统计信息参见表1:(1)重复多次的推文(只保留一次).(2)除 Hashtag、关键词、@、URL 以及停用词外,单词数少于3的推文(对于特定话题,几乎所有的推文都包含一致的 Hashtag或关键词.除掉以上这些信息后几乎没有其他内容的推文,我们认为其增量信息比较少).(3)对应 用 户 在数 据 集 中 属于 孤立 点 的 推文(保证网络结构的稠密性).表 1 数据集统计信息统计信息 时间 推文数 用户数用户最大度用户最小度用户最大推文数用户最小推文数用户平均推文数P-value(一致性)P-value(传染性)Osama  0501  4680  1309  69  1  42  2  3.65  4.78E-125  1.82E-33Jopin  0522  2896  1082  68  1  93  1  2.68  2.10E-98  6.60E-09Mavs  0612  3859  1780  76  1  92  1  2.18  9.01E-211  8.09E-08Weinergate  0616  1278  885  52  1  11  1  1.45  4.62E-19  5.17E-10Betawards  0626  787  200  16  1  57  1  3.94  2.10E-27  3.62E-05Casey-Anthony  0705  6241  1318  74  1  180  2  4.74  5.66E-97  1.59E-27Asobama  0706  4888  2009  142  1  63  1  2.43  5.32E-99  9.81E-06Atlantis  0708  2515  712  47  1  21  2  3.53  1.01E-72  1.44E-14Harrypotter  0715  2760  865  37  1  26  2  3.19  3.41E-89  2.24E-10WWC  0717  3642  2103  219  1  25  1  1.73  3.08E-54  1.05E-08Oslo  0722  4571  1026  77  1  56  2  4.46  2.62E-131  4.98E-19SDCC  0722  5817  442  81  2  161  2  13.16  3.21E-143  1.31E-113.3 社会学理论验证分析社会学理论,尤其是一致性[26]和传染性[27-28],1187 计  算  机  学  报 2019年① https://wiki.engr.illinois.edu/display/forward/Dataset-UDI-TwitterCrawl-Aug2012任务中被证明是有用的.社会学理论指出社会网络中成员之间通常会展现出相关的行为,情感和话题都会随着网络进行传播.一致性一般认为,同一个人在短时间内表现出的社会行为具有一致性;传染性一般认为,具有朋友关系的两个人可以对彼此产生影响.本节我们主要考查对于每个话题集,社会学理论是否 存在,并且给出验证方法.首先对于我们的任务,重 新定义了一致性和传染性:(1)表达一致性.同一用户所发的两个推文在内容上是否比随机选择的两个推文更相似?(2)表达传染性.具有朋友关系的两个用户所发的推文在内容上是否比随机 选择的两个推文更相似?为了验证这两个问题,我们给出计算两个推文距离的公式Aij= ti-tj  2,其中ti,tj分别为第i,j条推文的向量表示.两个推文越相似,Aij越接近0.对于第一 个 问 题,我 们 构 建 两 个 维 度 一 致 的 向 量consc和consr.第一个向量的每一维是通过计算同一用户所发两条推文的距离得到,第二个向量的每一维是通过计算两条随机选择推文的距离得到.然后对这两个向量做双样本 T 检 验,并 设 置 空 假 设为,两个向量并无很大差异,即 H0:consc=consr;备择假设为,同一用户所发的两条推文在距离上比随机选择的两条推文更小,即 H1:consc<consr.类似地,为了验证第二个问题,我们构建了两个维度一致的向量contc和contr.第一个向量的每一维是通过计算具有朋友关系的用户所发两条推文的距离得 到,第 二 个 向 量 的 每 一 维 是 通 过 计 算 随机选择的两条推文的距离得到.我们同样在这两个向量上做双样本 T 检验.设置空假设为 H0:contc=contr,即两个朋友关系的用户所发推文的距离与随机选择两条推文的距离并无很大差异.备择假设为H1:contc<contr,表示两个朋友关系的用户所发的推文在距离上比随机选择的两条推文更小.对于所有的话题集,一致性空假设和传染性空假设都以置信度α=0.01(两种社会学理论在所有数据集中均以超过 99% 的概率存在)的水平 被 排斥,其中 P-values在表 1 的最后两列呈现.该验证分析说明,两种社会学理论在数据集中是真实存在的,这为在推特摘要优化建模中融入社会媒体信息传播的一致性和传染性奠定了基础.4 SNSR总体框架4.1 推特摘要的组稀疏模式挖掘压缩感知理论认为,自然信号一般是稀疏且可压缩的.稀疏重构的思想与稀疏编码(Sparse Coding)类似,来源于压缩感知理论.即原始信号可由一组基向量来表示,通过约束最小化重构误差,找到最具有代表性的基向量,其张开的子空间可以很好地表示原始信号的空间.这种思想被广泛应用于信号处理、图像或视频压缩等领域,比如针对图像压缩,一方面通过观察基像素点即可了解原始图像的大致内容;另一方面通过保存基像素点和重构矩阵,即可最大地还原原始图像,使得对于超大规模图像的保存,可以大大节省空间消耗.推特摘要任务的目标与稀疏重构的思想不谋而合.从推文集中抽取简洁、核心的代表信息形成摘要,通过阅读摘要即可了解原始数据集的概要内容,也相当于是对原始文本集的一种压缩处理.特别地,对于抽取式推特摘要方法,可以把原始推文(句子)集看作信号,那么推特摘要的任务就是从原信号中寻找能最好地重构其的样本子空间,即一组推文基向量,使得这组推特摘要句子可以最大化地重构原始推特文本集.对于给定的推特语料 C,其可以表示为文本矩阵S∈!m×n.对于第i个推文ti∈S,可以通过其他推文的线性组合形式化表示为ti=∑nj=1c(j)Wjitj (1)为了更好地解释文摘句选择的物理含义,式(1)中c(j)=0表示第j个推文tj不是摘要推文,c(j)=1表示第j个推文tj最终被选为摘要推文.对于抽取式摘要,假设我们最终需要抽取k条推文形成摘要,则有∑nj=1c(j)=k.Wji表示推文tj在重构推文ti时的权重,其值越大表示在重构推文ti时所占的比重越大.由于每一个推文向量ti是通过计算 TF-ITF 得到的,每一个维度均为非负值,故需要对 Wji增加非负约束.除此之外,我们需要增加额外的约束 Wii=0来避免句子自身重构自身的现象,否则会导致其重构系数接近于0,Wii接近于1,以至于失去稀疏重构原本的意义.因此,基于稀疏重构的推特摘要方法的目标函数可以表示为6期 贺瑞芳等:基于社会媒体内容和网络拓扑的特定话题推特摘要研究1197i-∑nj=1c(j)Wjitj22满足c∈{0,1}n,∑nj=1c(j)=k (2)i∈{1,2,…,n}Wii=0i,j∈{1,2,…,n}Wji0式(2)可以进一步用矩阵形式来表示:min12S-SD(c)W2F满足c∈{0,1}n,∑nj=1c(j)=k (3)diag(W)=0,W 0式(3)中S 表示文本矩阵,D(c)是一个对角矩阵,第i行对角 元 素 的 值 对 应 于c(i)的 取 值,W =[W*1,W*2,…,W*n]∈!n×n是 一个重构系数矩阵,每一列W*j=[W1j,W2j,…,Wnj]是重构推文tj的系数向量.W 0 保证矩阵元 素非负,再加上约 束diag(W)=0,即可保证对角线的每一个元素为0,即Wii=0.由于c向量的约束,使得目标函数式(3)的优化是一 个 混 合 线 性 规 划 问 题,求 解 非 常 困 难.鉴 于D(c)的对角线只有有限多个1,而多数取值为0,使D(c)W 所得矩阵中会有很多整行为 0的情况.令W=D(c)W,并通过对W 添加2,1范数约束,即组稀疏正则项,可以确保 W 的行稀疏性,从而近似模拟D(c)W 的行选择过程.由于Wi*=[Wi1,Wi2,…,Win]中的每一维表示第i条推文 重构其他 推 文 时 的 权重,当第i行元素全部为0时,表示该推文在重构整个语料中的重要性比较低,也就很大概率不会被选择为摘要推文,所以对W 的行选择可以认为是对推文的选择.实际上,若是去掉 D(c)的相关表达,直接加组稀疏约束建模效果是等价的,对运算过程没有影响.式(3)可以重新改写为minW12S-SW 2F+λ W 2,1 (4)满足diag(W)=0,W 0式(4)中λ为组稀疏正则项参数,W 2,1=∑ni=1Wi* 2,Wi* 2=∑nj=1W2i槡j.由此通过组稀疏学习的约束可以实现挖掘推文集中的摘要推文组的潜在模式,使得摘要推文从全局角度保证了一定的非冗余性.4.2 建模推文层次的网络结构为了减少重构误差,并且在重构过程中做出纠正,我们使用社会学理论建模推文层次的网络结构信息,并作为社会正则项整合到稀疏重构的优化框架中.源于 Graph Lasso[29]思想的启发,也就是说,对于两条相关连的推文,由于其本来距离就很接近,需要让它们在重构过程中依旧保持相似.为了利用社交网络结构做推特摘要,我们使用之前提到的社会学理论来构建推文层次的 网络结构.具体地,需要把给定的用户 -推文矩阵U 和用户-用户矩阵F 转换为推文-推文矩阵:(1)通过表达一致性理论构建的推文 -推文关联矩阵定义为Tcons=UTU,其中Tcons=1表示两条推文是同一用户所发;(2)通过表达传染性理论构造的推文 -推文关联矩阵被定义为Tcont=UTFU,其中Tcont=1表示两条推文是具有朋友关系的用户所发.然后,我们通过线性组合这两种矩阵,最终得到推文 -推文关联矩阵为T=Tcons+bTcont,其中b是这两种矩阵的平衡参数.理论上,b值越大,说明传染性的影响越大,两个具有朋友关系的用户所发的推特越接近,在公式上表现为尽可能拉近推特的距离,避免重构误差(亦即本来距离较近的两条推特,在重构后距离拉大,加上该约束可以拉近距离,纠正重构偏差).b值越小,说明传染性的影响越小,具有朋友关系的用户所发推特越容易避免被强制拉近.至于b取大取小,取决于数据集本身的网络特性(传染性),是一个可调节的参数.实验时我们简单取b=1,当然也可以对b的不同取值作分析.Tij=1表示两条推文是有关联的,否则没有关联.我们定义S 的重构矩阵为S^=SW,那么 GraphLasso惩罚项,即社会正则项可以表示为Ωgraph=12∑ni=1∑nj=1Tij S^*i-S^*j22=∑mi=1S^i*D-T S^Ti*=tr(SWLWTST) (5)其中,tr(·)表示矩阵的迹,L=D-T 是拉普拉斯矩阵,D∈!n×n是对角矩阵,而且 Dii=∑nj=1Tij,每一个对角元素表示推文节点在图中的度.通过整合式(5)到式(4),可以得到:minW12S-SW 2F+α2tr(SWLWTST)+λ W2,1(6)满足 diag(W)=0,W 0其中,α 是社会正则项参数,式(6)产生了将社会媒1108 计  算  机  学  报 2019年相融合的基于稀疏重构的推特摘要框架.4.3 社会网络传播带来的强冗余信息建模去冗余 一 直 是 摘 要 研 究 的 重 点.社 会 研 究 表明[28],社会网络中的互惠关系以及某些三元结构大大增加了社会传染性,这将导致在某个特定的网络结构中,会带来更多的冗余以及缺乏新颖性的信息.因此,相较于传统摘要研究,推特摘要面临更严峻的去冗余问题.目前存在一些考虑多样性来选择摘要的研究.最 具 代 表 性 的 方 法 称 为 最 大 边 缘 相 关 性(Maximal Marginal Relevance,MMR).该方法一般是在推文排序后使用,通过综合考虑相关度与冗余度进行句子选择,其作为额外的步骤来实施,而不是模型的一部分.基于话题的方法可以发现语料中的子话题,同时在某种程度上解决了多样性问题.但是这类方法存在一些关键挑战:评估推文在每个子话题的重要性,评估每个子话题在整个语料的重要性,子话题之间的去冗余(比如,由于划分粒度较小,使得两个子话题很类似).基于稀疏重构的摘要方法倾向于从语料层面选择重要的句子,但是没有明显的倾向会包含语料的各个方面.这类工作已有的针对多样性的研究包括:Liu等人[11]引入一个相关性项来控制多样性,但是他们的模型求解过程比较复杂;Yao等人[12]引入了一个不相似度矩阵,大大地降低了计算复杂度.然而他们计算该不相似度矩阵的方法并不适用于推特语料,一方面是由于推特语料的嘈杂、不规范;一方面他们使用句子长度或者词汇库大小来计算每个单词的编码损失,这种计算方法使得不相似度矩阵中的每个元素都很大,导致W 的每个元素都接近于0,不容易区分句子的重要性.受到该不 相 似 度 矩 阵 的 启 发,本 文 提 出 相 对简单但 却 很 有 效 的 余弦相似度矩阵对社会媒体传播引发的强冗余信息建模.对于 每 个 元 素 ij∈[0,1]表示推文ti和推文tj的余弦相似度.在稀疏重构的过程中,我们添加约束diag(W)=0来避免自身重构自身的现象,基于这种认识,我们有理由避免推文被那些与其极为相似的推文重构.例如下面这个例子:(1)Tweet1:the mood was solemn at the garden ofreflection in lower makefield following the death of osama binladen.video:http://fb.me/tof3pqok(2)Tweet2:the mood was solemn at the garden ofreflection in lower makefield following osama bin laden’sdeath.video:http://bit.ly/l9tvdw显然这 两 条 推 文 很 相 似,这 会 导 致 重 构 系 数W12和W21都接近于1,从而导致提高了这两条推文在整个语料的重要性的问题.通过初步的实验,我们观察到,倘若不加多样性约束,在生成的最终摘要中会存在很多这种相似推文.为了更好地避免这种“相似”的重构现象,我们重新计算为ij=1, 若ijθ0,烅烄烆否则(7)式(7)中θ是用来区分相似推文对和常规推文对的阈值.由此进一步建模推特摘要的多样性,并提出多样性正则项的表达形式:tr(TW)=∑ni=1∑nj=1ijWij.并整合到式(6)中得到最终的目标函数为minW12S-SW 2F+α2tr(SWLWTST)+  γtr(TW)+λ W2,1(8)满足diag(W)=0,W 0其中,γ 是 多样性正 则项参数.通 过 优化目标函 数式(8),可以得到重构的系数矩阵 W.每条推文的重要性分数可以通过下式得到:Score(ti)= Wi* 2(9)依据重要性分数对推文进行排序,最后筛选前几条推文形成最终摘要.5 优化的推特摘要算法5.1 算 法由于 W2,1不可导,所以目标函数式(8)是非平滑的.受到 前 人 工 作[22,30-31]的 启 发,本 文 提 出 基 于Nesterov加速梯度下降的摘要优化算法.针对该非平滑优化问题的解决方法,目标函数可以被等价的表示为 minWf(W)=12S-SW 2F+α2tr(SWLWTST)+  γtr(TW) (10)满足Z={W|W 0,diag(W)=0,W2,1z}式(10)中z是2,1球的半径,并且λ和z 具有一对一的映射关系.由于任意范式都定义了一个凸集,故Z 是一个封闭的凸集.由此,我们的问题转换为定义域为封闭凸集、目标函数为凸函数的凸优化问题.接下来,我们阐述本文基于 Nesterov加速投影6期 贺瑞芳等:基于社会媒体内容和网络拓扑的特定话题推特摘要研究1118梯度下降的优化算法,可以用来解决式(10)中带约束的凸优化问题.首选不考虑式(10)中带约束W∈Z 的优化问题:minWf(W).我们知道,通过梯度下降,Wt+1可以通过式(11)更新:Wt+1=Wt-1lrf′(Wt) (11)其中,lr表示学习率,lr的值根据 Armijo-Goldstein[32]规则通过线搜索(Line Search)方法得到.f′(W)表示目标函数f(W)对W 的求导:f′(W)=STSW-STS+γ+αSTSWL (12)优化问题中的平滑部分可以等价地改写为线性函数f(W)在Wt处的近端正则,表示为Wt+1=arg minWGlr,Wt(W),其中,Glr,Wt(W)=f(Wt)+〈f′(Wt),W-Wt〉+lr2W-Wt2F(13)考虑到我们优化问题的等价形式以及约束项Z,我们可以通过以下迭代公式得到最终解:Wt+1=arg minW ∈ZGlr,Wt(W) (14)通过忽视式(13)中独立于W 的项,式(14)可以归约为Wt+1=minW∈Z12W-Ut2F(15)其中,Ut=Wt-1/lrf′(W),则 W 表示U 在凸集Z上的欧几里得投影(Euclidean projection):式(15)可以分解为n个子问题:wjt+1=minwj∈zj12wj-ujt22(16)其中,ujt,wj,wjt分别表示矩阵Ut,W,Wt的第j行.给定λ,通过欧几里得投影得到的解的形式为wjt=1-λlr uj( )tujt, 若 ujtλlr0,烅烄烆否则(17)上述方法的收敛速度为 O(1/k),而 Nesterov方法加速了该优化过程,使收敛速度达到 O(1/k2),其中k表示迭代次数.Nesterov方法基于两个序列{Wt}和{Vt},其中{Wt}是近似解序列,{Vt}是搜索点序列.{Vt}是{Wt}和{Wt-1}的结合:Vt=Wt+!(Wt-Wt-1),其中,! 是结合系数.Ut可以由{Vt}通过类似“梯度”更新的方法计算得到,所以Ut可以重新计算为Ut=Vt-1lrf′(W).详细的算法过程见算法1.算法1. 基于 NAG 的模型优化算法.输入:S,U,F,,W0,α,γ,λ,θ,ε输出:W1.初始化μ0=0,μ1=1,W1=W0,lr=0.12.T=UTFU+UTU,L=D-T,=θ3.FORiter=0,1,2,…,DO4. V=W1+(μ0-1)(W1-W0)/μ15. f′(W)=STSW1-STS+γ+αSTSW1L6. LOOP7.  U=V-1/lrf′(W)8.  FOR each rowUi* of U DO9.   Wi*=Sλ/lr(Ui*)//使用式(17)解决10.  ENDFOR11.  W=W-diag(W),W=max(W,0)12.  IF f(W)Glr,V(W)THEN13.   break14.  ENDIF15.  lr=2×lr16. ENDLOOP17. Set funVal(iter)=f(W)+λ W2,118. IF|funVal(iter)-funVal(iter-1)|εTHEN19.  break20. ENDIF21. W0=W122. W1=W23. μ0=μ124. μ1=(1+ 1+4槡μ21)/225.ENDFOR算法中第3到第25行描述了用 Nesterov方法解决 优 化 问 题 式 (8),第 6 到 第 16 行 描 述 了 用Armijo-Goldstein规则通过线搜索得到学习率lr,第24行μ1的值依据[33]所提到的方法得到,这里,μ0和μ1均为 Nesterov梯度下降法中计算步长的辅助变量.通过该算法可以解决我们模型的优化问题,并通过式(9)计算每条推文的重要性以形成摘要.5.2 收敛性及时间复杂度分析收敛性:对于 Nesterov加速梯度下降算法,通过在搜 索 点Vt执 行 梯 度 下 降 而 不 是 在 近 似 点 Wt执行梯度下降,收敛率可以达到O 1/k( )2,其中k为迭代次数,同 时 可 以 得 到 算 法 的 理 论 迭 代 次 数 为O(1/槡ε),其中ε表示收敛阈值.该结论可以通过如1128 计  算  机  学  报 2019年

[返回]
上一篇:基于双重注意力机制的异步优势行动者评论家算法
下一篇:基于必然属性分析的粒描述