关键词抽取、社会标签推荐 及其在社会计算中的应用

Presentation on theme: "关键词抽取、社会标签推荐 及其在社会计算中的应用"— Presentation transcript:

1 关键词抽取、社会标签推荐 及其在社会计算中的应用
刘知远

2 目录 关键词抽取和社会标签推荐简介 关键词抽取方法 关键词抽取的应用 展望

3 问题描述 关键词自动抽取 Automatic Keyphrase Extraction 定义：自动从文档中抽取关键词作为文档摘要 特点：
多个词或短语 一般来自文档内容

4 关键词抽取的典型应用场景 新闻、学术论文 社会化标注

5 关键词标注方式 关键词标注 关键词抽取 关键词分配 社会化标注

6 关键词标注方法 关键词抽取 有监督 二分类 多分类 无监督 词频 图方法

7 有监督方法 转化为二分类问题 转化为多分类多标签问题 判断某个候选关键词是否为关键词 Frank 1999采用朴素贝叶斯分类器
Turney 2000采用C4.5决策树分类器 转化为多分类多标签问题 传统文本分类方法 受限词表作为候选关键词集合（分类标签） 人工标注训练数据 费时费力 不适用于网络时代

8 无监督方法 词频 图方法 基于TFIDF及其变形对候选关键词进行排序 Rada 2004: PageRank  TextRank
Huang 2006: 复杂网络统计性质 Litvak and Last 2007: HITS

9 词频方法 TFIDF 𝑤 = 𝑡𝑓 𝑤 ∙ 𝑙𝑜𝑔 2 𝐷 { 𝑑𝑓 𝑤 }
Term-frequency inverse document-frequency (TFIDF) TF: the importance of the term within the document IDF: the informativeness of the term in the document set TFIDF 𝑤 = 𝑡𝑓 𝑤 ∙ 𝑙𝑜𝑔 2 𝐷 { 𝑑𝑓 𝑤 }

10 TextRank R(w): w的PageRank值 O(w): w的出度 e( 𝑤 𝑗 , 𝑤 𝑖 ): 𝑤 𝑗 → 𝑤 𝑖 边上的权重
构建词网 PageRank 选取排序最高的词为关键词 R(w): w的PageRank值 O(w): w的出度 e( 𝑤 𝑗 , 𝑤 𝑖 ): 𝑤 𝑗 → 𝑤 𝑖 边上的权重 V: 节点集合 𝜆: 平滑因子

11 文献综述-无监督方法小结 TFIDF: 仅考虑词自身频度 TextRank: 考虑文档内词间语义关系

12 研究问题 关键词应当具备以下特点 如何在关键词抽取中考虑对文档主题的覆盖性问题 如何解决文档与关键词间的词汇差异问题 相关性，可读性，覆盖性
关键词与文档主题保持一致性 如何在关键词抽取中考虑对文档主题的覆盖性问题 一个文档往往有多个主题 现有方法没有提供机制对主题进行较好覆盖 如何解决文档与关键词间的词汇差异问题 许多关键词在文档中频度较低、甚至没有出现 “machine transliteration” vs “machine translation” “iPad” vs “Apple”

13 例子 史蒂夫·乔布斯先后领导和推出了Macintosh、iMac、 iPod、iPhone等风靡全球亿万人的电子产品，深刻地 改变了现代通讯、娱乐乃至生活的方式。2011年10 月5日他因病逝世，享年56岁。乔布斯是改变世界的 天才，他凭敏锐的触觉和过人的智慧，勇于变革， 不断创新，引领全球资讯科技和电子产品的潮流， 把电脑和电子产品变得简约化、平民化，让曾经是 昂贵稀罕的电子产品变为现代人生活的一部分。 关键词:乔布斯、苹果、电子产品

14 研究思路 对文档主题结构进行建模，并用于提高关键词抽取的覆盖性 利用无标注文档集中的文档与关键词的主题一致性，弥合文档与 关键词的词汇差异
利用文档内部信息构造文档主题 利用文档外部信息构造文档主题 结合文档内部、外部信息 利用无标注文档集中的文档与关键词的主题一致性，弥合文档与 关键词的词汇差异

15 内容提要 通过文档词聚类构建主题进行关键词抽取 利用隐含主题构建主题进行关键词抽取 综合利用隐含主题和文档结构进行关键词抽取
利用机器翻译弥合词汇差异进行关键词抽取 社会计算中的典型应用

16 通过文档词聚类构建主题 进行关键词抽取

17 研究动机与方法 动机：利用文档内部信息对文档主题进行建模 方法 在文档中选取候选关键词 计算候选关键词之间的语义相似度 对文档中的词进行聚类
在每个聚类中选取聚类中心（exemplar）扩展出关键词

18 算法细节 候选关键词相似度度量 聚类方法选取 基于同现关系的相似度 基于维基百科的相似度
Cosine，Euclid，PMI，NGD 聚类方法选取 层次聚类（hierarchical clustering） 谱聚类（spectral clustering） 消息传递聚类（Affinity Propagation）

19 实验结果 数据集合：论文摘要 参数影响

20 实验结果 与其他算法的比较 举例

21 小结 提出了利用聚类对文档内部主题结构建模的关键词抽取算法 对比了不同的相似度度量算法、聚类算法 较好地实现推荐关键词的覆盖性 存在问题
不同聚类个数的设定会极大影响关键词抽取效果 稳定性较差,与多个因素有关:词汇相似度计算、聚类方法、聚类个数等

22 通过隐含主题模型构建主题 进行关键词抽取

23 隐含主题模型 对文档主题进行建模的无监督学习模型 常见隐含主题模型 由用户指定隐含主题个数 根据大规模文档集合中学习 每个主题是在词上的分布
每个词和文档都可以表示为主题上的分布 常见隐含主题模型 Latent Semantic Analysis （LSA/LSI） Probabilistic LSA （pLSA） Latent Dirichlet allocation （LDA）

24 隐含主题模型示例

25 利用隐含主题模型进行关键词抽取 文档的主题分布：𝑃(𝑧|𝑑) 词的主题分布：𝑃(𝑧|𝑤) 通过多种方式度量其语义关系 存在问题
Cosine similarity KL-divergence 𝑃 𝑤 𝑑 = 𝑧 𝑃 𝑤 𝑧 𝑃(𝑧|𝑑) 存在问题 LDA运算复杂度较高，在大规模数据集合上运行速度较慢 解决方案：并行化，或者在线学习

26 LDA学习算法 其他位置上的词w的主题分布 该文档其他位置上词的主题分布 Gibbs Sampling

27 隐含主题模型的并行研究 LDA的已有并行算法 主要问题 Approximate Distributed LDA （AD-LDA）
Asynchronous LDA（AS-LDA） 主要问题 内存瓶颈：要求主题模型（𝑊×𝐾）保存于每台机器内存 通信瓶颈：要求每次迭代机器间都要交互整个主题模型

28 PLDA+算法 机器分为两种功能： 一部分机器用于维护训练文档 一部分机器用于维护主题模型

29 PLDA+算法

30 实验效果-维基百科（20万词汇）

31 在线学习-Online LDA 基本思想 特点 Related Works 整个数据集合上的大循环每个文档上的小循环
每次只在一个很小的集合上学习并更新模型 不再返回去看旧的数据 特点 快速 有利于Web随时间变化较快的数据 Related Works Online Learning for Latent Dirichlet Allocation Deterministic Single-Pass Algorithm for LDA Sparse stochastic inference for latent Dirichlet allocation

32 综合利用隐含主题模型和文档结构进行关键词抽取

33 研究思路 前述工作 综合考虑文档主题和内部结构进行关键词抽取 LDA：利用隐含主题模型发现文档主题 TextRank：利用文档内部结构信息
Topical-PageRank（TPR）

34 研究方法

35 研究方法 𝑅 𝑧 ( 𝑤 𝑖 )=𝜆 𝑗: 𝑤 𝑗 → 𝑤 𝑖 𝑒( 𝑤 𝑗 , 𝑤 𝑖 𝑂( 𝑤 𝑗 𝑅 𝑧 ( 𝑤 𝑗 )+(1−𝜆) 𝑝 𝑧 𝑤 𝑖 𝑝 𝑧 𝑤 𝑖 =𝑃(𝑤|𝑧) , probability of word 𝑤 given topic 𝑧. 𝑝 𝑧 𝑤 𝑖 =𝑃(𝑧|𝑤) , probability of word 𝑧 given topic 𝑤. 𝑝 𝑧 𝑤 𝑖 =𝑃(𝑤|𝑧)×𝑃(𝑧|𝑤) , product of hub and authority.

36 研究方法 候选关键词: 名词性词组 (adjective)*(noun)+ 文档主题分布: 𝑃(𝑧|𝑑) for each topic 𝑧

37 (a) Topic on “Terrorism”
示例 (a) Topic on “Terrorism” (b) Topic on “Israel” (c) Topic on “U.S.” (d) TPR Result

38 实验 实验数据 评价指标 新闻数据: 308 篇，来自DUC2001 论文摘要: 2,000 篇，来自(Hulth, 2003)
precision, recall, F-measure 𝑝= 𝐶 𝑐𝑜𝑟𝑟𝑒𝑐𝑡 𝐶 𝑒𝑥𝑡𝑟𝑎𝑐𝑡 , 𝑟= 𝐶 𝑐𝑜𝑟𝑟𝑒𝑐𝑡 𝐶 𝑠𝑡𝑎𝑛𝑑𝑎𝑟𝑑 , 𝑓= 2𝑝𝑟 𝑝+𝑟 binary preference measure (Bpref) 𝐵𝑝𝑟𝑒𝑓= 1 𝑅 𝑟∈𝑅 1− 𝑛 ranked higher than 𝑟 𝑀 mean reciprocal rank (MRR) 𝑀𝑅𝑅= 1 𝐷 𝑑∈𝐷 1 𝑟𝑎𝑛𝑘 𝑑

39 与其他方法比较 在新闻数据上，𝑀 从1 到 20变化 在论文摘要数据上，𝑀 从1 到 10变 化

40 小结 LDA通过文档主题进行关键词抽取，因此取得较TFIDF、TextRank 较优的结果
TPR综合了TextRank和LDA的优点，在两个数据集合上都表现出了 它的优势 由于TPR可以按照主题推荐关键词，因此可以用于文档可视化， 也可以用来进行查询导向（query focused）的关键词抽取

41 利用机器翻译模型进行关键词抽取

42 研究问题 文档和关键词都是对同一事物的描述 词汇差异的表现 问题 主题一致，词汇差异 很多关键词在文档中出现次数不高
有的关键词在文档中根本没有出现（尤其是短文本） 问题 TFIDF、TextRank及其扩展、LDA等方法均没有很好解决词汇差异问题

43 相关工作 TextRank的扩展ExpandRank LDA 在构建词网时，同时考虑文档的近邻文档
从“文档层次（document level）”利用外部信息 容易引入噪音 LDA 通过主题分布的相似度来对候选关键词排序 从“主题层次（topic level）”利用外部信息 由于主题一般是粗粒度的 倾向于推荐普通词 容易发生主题漂移

44 研究思路 事物 文档 关键词 翻译 在“词汇层次（word level）”利用外部信息 文档和关键词是对同一事物的描述
关键词抽取问题翻译问题 事物 文档 关键词 翻译

45 研究方法 构建翻译对（translation pairs）
学习两种语言间词汇的翻译概率（translation probabilities） 𝑃( 𝑤 𝑘 | 𝑤 𝑑 ) 利用SMT中的词对齐（word alignment）算法 给一个新的文档𝑑 计算每个候选关键词𝑝的似然概率 𝑃 𝑝 𝑑 = 𝑖∈𝑝 𝑗∈𝑑 𝑃 𝑤 𝑖 | 𝑤 𝑗 𝑃( 𝑤 𝑗 |𝑑) 按照候选关键词的值进行排序

46 研究方法-构建翻译对集合 将文档标题或摘要看作近似用关键词语言写成 问题 大部分文档有标题或摘要信息 将标题/摘要与文档正文形成翻译对
摘要、文档往往较长 直接使用词对齐算法效率较低、效果较差 没有标题/摘要的时候怎么办

47 研究方法-构建翻译对集合 给定标题和文档，提出两种构建翻译对的办法 采样法（sampling）：将较长的文档进行抽样，直到与标题长度一致
基于词在文档中的重要性（TFIDF）进行采样 分割法（split）：将较长文档划分为句子，用每句话与标题构成一个 翻译对 只有句子与标题之间相似度大于某个阈值𝛿才放入训练集

48 研究方法-构建翻译对集合 当没有标题或摘要，从文档正文中选择重要的句子来与正文构成 翻译对 选择文档第一句话 选择与文档最相关的一句话

49 实验设置 句子对齐算法采用IBM Model-1的工具GIZA++ 在13,702篇中文新闻上进行试验

50 实验结果

51 实验结果-抽取重要句子构建翻译对

52 实验结果-关键词生成 （Keyword Generation）
在测试时，只能够根据新闻标题产生关键词

53 实验结果-关键词生成举例 文档题目：“以军方称伊朗能造核弹 可能据此对伊朗动武” 方法 推荐关键词 标准答案 核武器,以色列,伊朗 SMT
伊朗,动武,以军,以色列,军事,核武器 TFIDF 伊朗,动武,核弹,以军,据此 TextRank 伊朗,可能,据此,核弹,动武 LDA 伊朗,美国,谈判,以色列, 制裁 ExpandRank 伊朗,以色列, 黎巴嫩,美国,以军

54 小结 机器翻译技术可以有效解决词汇差异问题 标题/摘要与文档能够构建高质量的翻译对 推荐更符合文档主题的关键词 甚至能够胜任关键词生成任务
对于新闻文档而言，正文第一句也可以用来构建高质量翻译对

55 利用隐含主题模型+机器翻译模型 进行关键词抽取

56 研究思路 + =

57 例子 Topic-52 Topic-92 Top Words Keyphrases 1 设计 程序 计算机 2 创意 开发 编程 3 设计师
design 应用 软件工程 4 杂志 手工 对象 C++ 5 时尚 平面设计 技术 程序设计 6 游戏 programming 7 作品 系统 软件开发 8 色彩 产品设计 函数 Linux 9 视觉 工业设计 软件 计算机科学 10 广告 方法 Alan

58 例子——“图形” Topic-52 Topic-92 设计 0.482 游戏编程 0.201 色彩搭配学 0.089 程序设计语言
0.107 字体设计 0.084 Web2.0 0.094 产品设计 0.077 C 0.078 设计景观 0.05 Linux 艺术设计 0.039 图形学 0.049

59 标签推荐样例——源氏物语 Top WTM TTM TWTM 1 源氏物语 小说 2 名著 日本 外国文学 3 4 历史 5 紫式部 爱情 6
政治 社会学 7 文化 文学 8 政治学 9 Eason 俄罗斯 10 政治哲学 女性

60 方法比较

61 关键词抽取与社会标签推荐 在社会计算中的应用

62 微博关键词 以新浪微博为平台 利用关键词抽取技术获取用户发表微 博的关键词 应用前景 发现和建模用户兴趣 为用户之间链接赋予更丰富信息
推荐用户感兴趣的产品、信息和好友等 具有广阔的商业前景

63 微博关键词 应用情况 部署新浪、人人、豆瓣、腾讯和网易五大平台
2011年上线至今，注册用户量超过320万人；典型用户包括马化腾、李 开复、林俊杰等名人

64 微博关键词社会影响

65 分析政治文件 与新华社联合分析2013年“两会”报告 联合撰写深度报道十余篇 获得国内几十家重要媒体的上百次转载
《清华学子研发“词云图”　解码全国两会“关键词”》、 《词云图 里看李克强总理的履职关切》、《“发展”十年居榜首　重点十载皆不 同——“词云”解读<政府工作报告>》等 获得国内几十家重要媒体的上百次转载 包括人民网、新浪、网易、搜狐、腾讯、凤凰网、新京报、羊城晚报等 成为多家报纸的当期封面

66 年度关键词

67 揽悦推荐

68 考虑社会网络结构的用户标签推荐 微博用户属性和兴趣可以通过标签来表示，微博只有一部分用户 标注标签
提出同时考虑用户产生内容和用户社会网络关系的标签推荐模型 将标签作为“显式”的主题，通过概率的方式建立用户内容与标 签之间的语义关系 同时将用户的社会关系网络作为一种正则化因子考虑进来

69 基于专家发现的微博辟谣 微博是谣言泛滥的温床，网络谣言已经严重危害公共利益、影响 社会稳定
如何快速高效识别谣言是重要的研究问题，需要大量知识储备， 无法做到全自动 提出一种有效结合机器智能和群体智能进行谣言识别的框架：通 过对微博用户和可疑谣言的分析，寻找最有可能判定该谣言的专 家

70 总结 关键词抽取需要考虑主题覆盖度和词汇差异问题 关键词抽取、社会标签推荐在社会计算中的应用 通过文档内词聚类构建文档主题
通过隐含主题模型构建文档主题 综合考虑隐含主题和文档结构 基于机器翻译模型 基于隐含主题+机器翻译模型 关键词抽取、社会标签推荐在社会计算中的应用 “微博关键词”应用 揽悦社会推荐系统 用户标签推荐系统 基于专家发现的微博辟谣框架

71 展望 关键词抽取的深层次问题 关键词抽取社会计算中的（文档）摘要任务 如何抽取短语/多词表达/新词
隐含主题、社会标签、关键词的层次结构关系 时序因素的考虑 关键词抽取社会计算中的（文档）摘要任务

72 参考文献 Chen Liang, Zhiyuan Liu, Maosong Sun. Expert Finding for Microblog Misinformation Identification. COLING 2012. Zhiyuan Liu, Chen Liang, Maosong Sun. Topical Word Trigger Model for Keyphrase Extraction. COLING 2012. Zhiyuan Liu, Cunchao Tu, Maosong Sun. Tag Dispatch Model with Social Network Regularization for Microblog User Tag Suggestion. COLING 2012. Han Li, Zhiyuan Liu, Maosong Sun. Random Walks on Context-Aware Relation Graphs for Ranking Social Tags. COLING 2012. Zhiyuan Liu, Xinxiong Chen, Maosong Sun. Mining the interests of Chinese microbloggers via keyword extraction. FCS 2012. Zhiyuan Liu, Xinxiong Chen, Maosong Sun. A Simple Word Trigger Method for Social Tag Suggestion. EMNLP 2011. Zhiyuan Liu, Xinxiong Chen, Yabin Zheng, Maosong Sun. Automatic Keyphrase Extraction by Bridging Vocabulary Gap. CoNLL 2011. Zhiyuan Liu, Wenyi Huang, Yabin Zheng, Maosong Sun. Automatic Keyphrase Extraction via Topic Decomposition. EMNLP, 2010. Zhiyuan Liu, Yuzhou Zhang, Edward Y. Chang, Maosong Sun. PLDA+: Parallel Latent Dirichlet Allocation with Data Placement and Pipeline Processing. ACM TIST, 2010. Zhiyuan Liu, Peng Li, Yabin Zheng, Maosong Sun. Clustering to Find Exemplar Terms for Keyphrase Extraction. EMNLP, 2009.

73 谢谢各位！ 欢迎提出宝贵意见和建议! 刘知远