Short Text Understanding: A Database Approach

Presentation on theme: "Short Text Understanding: A Database Approach"— Presentation transcript:

1 Short Text Understanding: A Database Approach
周晓方1,2 华雯1,3 1The University of Queensland, Australia 2苏州大学 3中国人民大学

2 内容提要 研究背景 研究动机 研究问题描述 研究所面临的挑战 解决方案 内容特征评分 社会特征评分 时态特征评分 总结

3 短文本

4 Michael Jordan (basketball)
短文本理解应用举例：语义检索 Air Jordan jordan bulls Michael Jordan (basketball) 检索结果

5 短文本理解应用举例：查询推荐 “hotel in la”？ “restaurant in la”？

6 短文本理解应用举例：实体浏览 https://en.wikipedia.org/wiki/Shaquille_O%27Neal

7 文本理解的层次 概念／实体 命名实体 主题 词法、语法结构 理解语义信息 我们的研究方向 预定义的几个类别 主题建模，主题表示为单词上的分布
传统的NLP技术 理解字面信息

8 文本理解工作的研究方向 文本理解：找到文本中提及的概念／实体 句子 段落 文档 文档集 ？ 短文本 句子 我们的研究方向

9 短文本理解的难点 信息量有限 包含大量的缩略词、拼写错误、语法错误 歧义性 - 短文本理解的重点 Harry Potter

10 短文本理解的难点 信息量有限 包含大量的缩略词、拼写错误、语法错误 歧义性 - 短文本理解的重点包括概念／实体消歧 Jordan

11 短文本理解的难点 信息量有限 包含大量的缩略词、拼写错误、语法错误 歧义性 - 短文本理解的重点包括概念／实体消歧 数据量规模庞大
2013年，Twitter平均每天收到5亿微博 2012年，Google平均每天收到30亿查询

12 解决方案 给定名词词组，选取候选概念/实体 消歧：为每个候选概念/实体计算合理的评分 从现有知识库中获得 Harry Potter
Harry Potter (book) 从现有知识库中获得 Harry Potter (movie) Harry Potter (character) Jordan Jordan (country) Air Jordan Michael Jordan (basketball) Michael Jordan (ml expert)

13 Probase知识库 名词词组和概念间的IsA关系 优势 巨大的概念覆盖率 概率信息可用于计算概念的初始评分
Pr(concept|term)：看见某一词组时想到某一概念的概率

14 Wikipedia知识库 实体页面、重定向页面、消歧页面、超链接 → 名词 词组与实体间的映射关系 优势 实体页面可用于实现实体浏览
实体页面包含对实体的具体描述，可计算实体的初始评分 实体的流行度 上下文相似度 名词词组在文本中的上下文与描述实体的Wikipedia页面间的相似度 … 现有知识库可以提供初始评分，但不能消歧，需要新的知识

15 新的评分指标 短文本内容 内容特征 用户兴趣 社会特征 热门事件的影响 时态特征

16 新的评分指标 短文本内容 内容特征 用户兴趣 社会特征 热门事件的影响 时态特征

17 现有基于内容的评分方式的不足 上下文相似度[1] 话题一致性[2][3][4]
名词词组在文本中的上下文与描述实体的Wikipedia页面的 相似度 话题一致性[2][3][4] 一个文本中出现的名词词组是语义相似或相关的 对一个文本中的所有名词词组进行联合概念/实体消歧 短文本中不适合 [1] R. Mihalcea and A. Csomai. Wikify!: Linking documents to encyclopedic knowledge. In CIKM 2007. [2] S. Kulkarni, A. Singh, G. Ramakrishnan, and S. Chakrabarti. Collective annotation of wikipedia entities in web text. In KDD 2009. [3] Y. Song, H. Wang, Z. Wang, H. Li, and W. Chen. Short text conceptualization using a probabilistic knowledgebase. In IJCAI 2011. [4] D. Kim, H. Wang, and A. Oh: Context-dependent conceptualization. In IJCAI 2013.

18 基于上下文语义相关度的评分方式* 任意词组间的语义相关性 难点： 准确计算词组间语义相关度 效率问题：词组间语义相关关系的庞大规模
watch movie read book age character watch harry potter read harry potter age harry potter * W. Hua, Z. Wang, H. Wang, K. Zheng, X. Zhou. Short Text Understanding Through Lexical-Semantic Analysis. In ICDE 2015 (Best Paper Award)

19 离线获取语义相关性 什么是词组间的语义相关？ 无法一一枚举词组间的关系 → 统一表示为共现关系
IsProductOf：“ipad”和“apple” IsCompetitorOf：“google”和“bing” IsAttributeOf：“population”和“china” IsAdjectiveOf：“pink”和“shoe” IsVerbOf：“watch”和“harry potter” … 无法一一枚举词组间的关系 → 统一表示为共现关系 词组在同一文本中共同出现，则语义相关

20 构建共现网 单个词组以不同类型出现时会和 不同的上下文相关 → 共现网应 构建在类型词组间 共现频率越高，相关性越高 距离越近，相关性越高
watch buy product price ipad omega brand harry potter watch[v] buy[v] product[c] price[att] ipad[inst] omega[inst] watch[inst] brand[c] watch[c] harry potter[inst] 常用词几乎与所有词共现 → 对于表示语义相关性 毫无意义，需要减小其在 共现网中的权重

21 Outlook.com is a free personal email from microsoft
构建共现网 自动分析16.8亿Web页面中的每个句子，得到类型词组集 根据共现的句子个数、在句子中的距离加权 使用类似于tf-idf的加权 Outlook.com is a free personal from microsoft {outlook[instance], free[adjective], personal[adjective], [concept], microsoft[instance]} 共现频率越高，相关性越大 距离越远，相关性越小 减小常用词的边权

22 压缩共现网 为什么需要压缩共现网？ 如何压缩共现网? 能帮助消岐的是词组与概念间的语义相关性
“watch harry potter” → “watch movie” 类型词组的数量很多：16M名词词组和2.7M概念 增加存储开销 降低在共现网上进行操作的效率 如何压缩共现网? 根据IsA关系将名词词组映射为其概念 使用K-Mediods算法对相似的概念进行聚类 边权从原始共现网中聚集得到

23 hotel california[inst] april in paris[inst]
watch[v] buy[v] age[att] lyrics[att] harry potter[inst] hotel california[inst] april in paris[inst] product[c] price[att] ipad[inst] omega[inst] watch[inst] brand[c] company[c] apple[inst] google[inst] read[v] song[c] 原始共现网 watch[c] watch[v] read[v] movie book character age[att] song lyrics[att] price[att] product brand buy[v] company 压缩后共现网

24 概念消歧 概念消歧是短文本理解的一个重点 加权投票算法 对原始的概念向量进行过滤或者重新加权和排序 最终得分是自我投票与上下文投票的乘积
watch harry potter read harry potter movie book 初始评分 从上下文中获得的语义支持

25 概念消歧举例 watch harry potter movie book character novel concept cluster
watch[verb] harry potter filtering movie film tv show sport co-occur

26 概念消歧举例 ipad apple fruit company food product concept cluster filtering
device concept cluster ipad[instance] apple device product brand company co-occur

27 新的评分指标 短文本内容 内容特征 用户兴趣 社会特征 热门事件的影响 时态特征

28 基于用户兴趣的评分方式 用户兴趣的作用 现有的基于用户兴趣的评分方式*的不足 对篮球感兴趣的用户：“Michael Jordan”
对用户发布的所有微博中的名词词组进行联合实体链接 部分用户缺乏信息且效率低 * W. Shen, J. Wang, P. Luo, and M. Wang. Linking named entities in tweets with knowledge base via user interest modeling. In KDD 2013.

29 Michael Jordan (basketball) Michael Jordan (ml expert)
基于社会交互的用户兴趣挖掘* 利用用户间的订阅关系来计算用户兴趣度 用户对实体的兴趣度=用户对订阅经常提及该实体的用户 社区的兴趣度 难点 小世界理论：4.12步之内可达 → 可达不等于感兴趣 用户订阅网很大 → 在线计算可达性效率低 与实体相关联的用户社区很大 → 一一计算目标用户与社区 中每个用户的可达性效率低 Michael Jordan (basketball) Michael Jordan (ml expert) * W. Hua, K. Zheng, X. Zhou. Microblog Entity Linking with Social Temporal Context. In SIGMOD 2015

30 加权可达性 小世界理论：4.12步之内可达 → 可达不等于感兴趣 加权可达性
启发式规则1：在订阅网中，u到v的距离越近，则u可能订阅v的 概率越大 启发式规则2：u所订阅的用户中参与u到v的最短路径的用户越 多，则u订阅v的概率越大 → 考虑用户在订阅网中的连通强度 最短路径距离 参与最短路径的朋友圈用户比例

31 加权可达性索引 用户订阅网很大 → 在线计算可达性效率低 扩展传递闭包索引算法 扩展两跳标记索引算法 关键技术点
预计算加权可达性并存储在加权可达性矩阵中 存储开销大，查询效率高 扩展两跳标记索引算法 每个节点v关联一个入标记集和出标记集 减小存储开销，同时保证线性的查询效率 关键技术点 设计增量算法减小索引构建的计算开销

32 增量算法计算扩展传递闭包索引 增量计算参与最短路径的朋友圈用户

33 增量算法计算扩展两跳标记索引 增量计算参与最短路径的朋友圈用户

34 用户社区影响力估算 与实体相关联的用户社区很大 → 一一计算目标用户 与社区中每个用户的可达性效率低
找到社区 𝑈 𝑒 中最有影响力的用户集合 发表了关于实体𝑒的大量短文本 在候选实体 𝐸 𝑚 间具有区分度 只在目标用户和有影响力的用户间进行加权可达性计算 基于tf-idf的方式 用户对社区的短文本贡献率 用户在候选实体间的区分度 基于信息熵的方式 用户短文本在候选实体上是否为有偏分布

35 新的评分指标 短文本内容 内容特征 用户兴趣 社会特征 热门事件的影响 时态特征

36 用户兴趣的动态变化 实体流行度：实体长期的被感兴趣程度 实体热门度：用户兴趣随最近热门事件的变化
NBA赛季：“Michael Jordan”→ Michael Jordan (basketball) ICML召开：“Michael Jordan”→ Michael Jordan (ML expert)

37 实体热门度挖掘* 实体热门度 难点 实体的最近流行度，即最近有大量短文本提及该实体 采用滑动窗口模型，时间窗口为𝜏
热门度可以在相关实体间相互传播 NBA热门度提高 → Michael Jordan (basketball)热门度提高 ICML热门度提高 → Michael Jordan (ML expert)热门度提高 流行度高的实体与很多其他实体相关，大规模的热门度传 播非常耗时 * W. Hua, K. Zheng, X. Zhou. Microblog Entity Linking with Social Temporal Context. In SIGMOD 2015

38 实体热门度传播 根据启发式规则构建实体热门度传播网 同一个名词词组的候选实体间不应该相互传播热门度 实体越相关，传播热门度的比率越大
只有高度相关的实体间才能相互增强热门度，减少时间开 销 类似于PageRank的实体热门度传播算法

39 实验设置 实验数据集 评估指标 Bing：随机采样1500条查询 Twitter: 5M用户发布的29.3M微博
用其中一部分微博作为历史数据来预计算与实体相关联的用户社 区，用另一部分微博来进行测试 评估指标 只有包含的所有名词词组都被正确标注，该短文本才算被 正确标注 term accuracy= # correctly labeled terms # detected terms text accuracy= # correctly labeled texts # texts

40 准确性 基于内容特征 Song[1]：基于名词词组间的语义相似性 Kim[2]：基于名词词组间的语义相关性
Our Approach：基于任意词组间的语义相关性 Song Kim Our Approach term-level 0.694 0.701 0.943 text-level 0.525 0.526 0.890 [1] Y. Song, H. Wang, Z. Wang, H. Li, and W. Chen. Short text conceptualization using a probabilistic knowledgebase. In IJCAI 2011. [2] D. Kim, H. Wang, and A. Oh: Context-dependent conceptualization. In IJCAI 2013.

41 准确性 基于社会特征 基于时态特征 Shen*：基于历史微博推断用户兴趣 Our Approach：基于用户订阅关系推断用户兴趣 Shen
term-level 0.671 0.719 text-level 0.593 0.628 Popularity Recency term-level 0.678 0.686 text-level 0.591 0.600 * W. Shen, J. Wang, P. Luo, and M. Wang. Linking named entities in tweets with knowledge base via user interest modeling. In KDD 2013.

42 效率 短文本长度变化 只有3条查询包含多余11个单词 大部分查询包含5个以内的单词

43 总结 理解短文本= 得到短文本中提及的概念/实体，可以支 持各种Web应用 创新点及贡献 下一步工作 查询推荐、实例浏览、语义检索…
使用新的知识（评分方式）帮助进行短文本理解 词组间的语义相关性、用户兴趣度、实体热门度 → 短文本理解的 准确性可达89%，比传统的基于内容的方法提高36.5% 设计有效的索引结构、增量算法、近似算法、启发式规则来 提高短文本理解的效率 在几十毫秒甚至几毫秒内理解大部分短文本 下一步工作 多特征结合消歧，知识库更新以及用户内容和关系动态维护

44

45 模型的准确性 增加了准确性5%-8% 参数𝛼、𝛽和𝛾分别表示用户兴趣度、实体热门度、实 体流行度在评分函数中的比重
在线实体链接算法On-the-fly[1] 联合实体链接算法Collective[2] 参数𝛼、𝛽和𝛾分别表示用户兴趣度、实体热门度、实 体流行度在评分函数中的比重 [1] P. Ferragina and U. Scaiella. Tagme: On-the-fly annotation of short text fragments (by Wikipedia entities). In CIKM 2010. [2] W. Shen, J. Wang, P. Luo, and M. Wang. Linking named entities in tweets with knowledge base via user interest modeling. In KDD 2013.

46 模型的效率 能在0.5毫秒内完成一条微博的实体链接 在线实体链接算法On-the-fly[1] 联合实体链接算法Collective[2]
[1] P. Ferragina and U. Scaiella. Tagme: On-the-fly annotation of short text fragments (by Wikipedia entities). In CIKM 2010. [2] W. Shen, J. Wang, P. Luo, and M. Wang. Linking named entities in tweets with knowledge base via user interest modeling. In KDD 2013.