《知识图谱: 概念与技术》第12 讲基于知识图谱的搜索与推荐•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐搜索的进化•Web搜索用户到底想搜什么内容？除了返回姚明的信息还能提供其他内容么？•Web搜索的进化•Web 搜索的进化keyword/stringthing/entity related things相关实体、概念潜在关系有关的属性确定搜索目标发现匹配结果匹配结果排序相关结果推荐搜索意图理解：•分词•规则解析•实体识别•实体链接•……•目标实体的属性展示•相关实体、概念的推荐•展现目标实体与相关实体间的关系•……•排序学习•目标实体、属性的查找•关联计算知识图谱•Web搜索的工作流程内容提纲•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐搜索意图理解•因为搜索/查询语句一般都是短文本，因此搜索意图的理解最主要的挑战是短文本的实体链接•实体链接的基本任务•将指代实体的文本mention链接到知识库中特定实体的过程•实体链接的相关问题与挑战•实体解析/命名实体识别entity resolution/name entity recognition•共指消解co-reference resolution•词义消岐word sense disambiguation•……短文本实体链接•实体链接为什么是一个挑战？•同一个实体在广泛的文本中可能有多个mention（指代词）•Barack Obama•Barack H. Obama都是指美国前任总统奥巴马•President Obama•Senator Obama•President of the United States•同一个指代词可能指代多个不同实体•Michael Jordan 到底是指篮球巨星还是机器学习大牛？•“苹果”是指能吃的水果还是时尚的公司/手机？•算法目标•利用实体指代词m 与候选实体e 的上下文等相关特征计算两者的匹配度分数φe,m ，按分数进行排序，并选择分数最大的实体e best 作为m 的链接结果，即e best =argmax e φe,m •局部模型•为短文本中的每个指代词及其链接的实体单独计算φe,m ，每个链接实体都是独立产生•全局模型•考虑文本中多个指代词所链接的实体间联系，对上下文内所有歧义的实体指代一同消歧•令Γ={m 1,e 1,m 2,e 2…}为一个全局实体链接方案，则目标函数为：Γbest =argmax ΓO Γ=argmax Γi=1N φm i ,e i +t j ∈Γψe i ,e jψe i ,e j 是实体e i ,e j 之间的相关度分数不光考虑实体和指代词之间的相关度，还考虑•上下文特征•示例：...when did Steve leave apple...{Steve Jobs,Steve Wozniak,Steve Ballmer,...}句中提的到底是哪个Steve？•上下文特征•文本相似度•计算候选实体上下文文本（如百科页面）与指代词上下文的相似度•候选实体上下文：实体的百科页面（或摘要文字）、实体锚文本•指代词上下文：指代词所在的段落/文档、紧挨指代词前后的n个词•相似度模型：词袋向量、概念（主题）向量•上下文特征•实体间的相似度•计算候选实体e1与上下文中的实体e2的相似度分数，通常利用两个实体的邻居集合U1和U2进行比较•相似度/相关度计算指标：•Jaccard e1,e2=|U1∩U2||U1∪U2|•PMI e1,e2=U1∩U2/|W|U1/|W|∗|U2|/|W|•NGD e1,e2=1−log max|U1|,|U2|−log U1∩U2log|W|−log min|U1|,|U2|•AdamicAdar e1,e2=σn∈U1∩U2log1degree n•短文本实体链接的挑战•训练数据缺乏•难以训练出符合应用环境的监督模型•上下文中的其他实体少•局部模型起主导作用•上下文中的词语少•通常只提供了模糊的主题信息•“红楼梦是谁写的”•“写”->“文学作品”->红楼梦（四大名著之一）•主题的作用•因为短文本上下文的信息量少，利用主题是比较流行的做法•现有主题方法的不足•潜在的主题（LDA）•难以捕捉到实体的细粒度特征•难以解释•手工构造的主题•难以扩展•利用实体的概念作为主题•可以捕捉实体细粒度特征•大量的信息(实体的文章和属性)•大覆盖度(甚至囊括新实体或者长尾实体)•计算主题凝聚度[1]•首先实体与指代词之间的主题/概念相似度sim c m,e=cos v c m,v c ev c e是实体的概念向量，v c m是指代词上下文的概念向量，计算如下：v c m=w∈CT(m)v c w D(w,m)CT(m)是上下文词集合•词的概念向量v c w的每一维如下计算r w,c=e∈E n w,e·r(e,c)σr(e,c′)•再计算实体与指代词之间的文本相似度cos v w w c,v w w d sim t m,e=max wc∈CT m,w d∈KP(e)KP(e)是关键词组集合，从实体相关文档与属性中抽取•另外再考虑与上下文无关的特征相似度•实体流行度•实体名与指代词的相似度•综合几类相似度分数得到实体与指代词间的最终相似度φe,m•全局目标函数Γ=arg maxΓ′i=1Nφe,m i+ψΓ′•其中实体凝聚度（实体间的相关度）为ψΓ=e i∈Γ,e j∈Γcoℎe i,e j •短文本上下文中的实体少，因此•NP难的全局算法复杂度可以接受•不需要近似算法•计算实体凝聚度•结合实体相似度和相关度coℎe1,e2=γ·sim e e1,e2+1−γ·rel e1,e2•sim e e1,e2相似度：可考虑NGD距离•rel e1,e2相关度首先计算rel′e1,e2=r∈R(e1,e2)2T e1,r+|H(r,e2)|R(e1,e2)是e1,e2之间的关系集合，T e1,r={e′|e1,r,e′∈KG}，H(r,e2)={e′|e′,r,e2∈KG}•像“配偶” 和“父母”这样对应少的关系会有大权值•像“国家” 和“出生地”这样对应多的关系会有小权值•由于逆关系通常对应的是同一个关系，因此两个方向取最大值得到rel e1,e2=max(rel′e1,e2,rel′e2,e1)内容提纲•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐实体探索•探索目标实体本身以外更多的内容•展现实体的属性信息•发现（推荐）更多相关实体•KG中的邻居实体（包括直接邻居和高阶邻居）•对目标实体进行概念化的说明/解释•展现目标实体与相关实体间的关系•……•More than oneentity•问题定义[2]•对于给定的一个实体e s，并针对目标实体e所属的类型T及其与给定实体的关系描述R，为目标实体计算如下的概率，最后按照此概率对所有相关的目标实体进行排序并输出•实体共现相关度•实体类型过滤•利用百科实体页面中的分类信息•利用命名实体识别工具•上下文建模t 是关系描述R 中的一个词，是实体e 与e s 的共现语言模型，t 越多地出现在e 与e s 的共现文档集合中，则越大前述的计算两个实体相似度的方法都可适用•问题定义[3]•给定由一组实体代表的查询q ，产生一个（组）概念能完美解释给定实体间的潜在联系•q 中包括搜索实体与推荐的相关实体，因此产生的概念是发现相关实体的基础BRICEmerging economy Growing Market Chinese internet giantChinese companyCountryCompany应该推荐什么相关实体？•算法描述•寻找的概念c i应满足下述目标1. Probabilistic Relevance Modelargmax e∈E−q rel q,e=iP e c i P c i qδ(c i)2. Relative Entropy Modelargmin e∈E−q KL P C q,P C q,e=i=1nδ(c i)P c i q log(P(c i|q)P(c i|q,e))利用Probase发现概念与实体间的关系找到的概念既要有代表性又要能很好地在最优的粒度层级上解释所推荐的相关实体•计算P(c i |q)1. Naïve Bayes ModelP c i q =P(q|c i )P(c i )P(q)∝ෑe j ∈qP(e j |c i )P(c i )∝P(c i )ෑe j ∈q,n e j ,c i >0λP(e j |c i )ෑe j ∈q,n e j ,c i =0(1−λ)P(e j )2. Noisy-or ModelP c i q =1−ෑe j ∈q(1−P(c i |e j ))•计算δ(c i)•用于度量目标概念的粒度，好的概念既不能太一般化也不能太具体化Concept Number of EntitiesCountry2648Developing country149Growing market18 Entity-based ApproachChina India BrazilDevelopingCountryCountryHierarchy-based Approach 距离q中实体更近的概念更值得考虑•计算δ(c i)1. Entity-based Approach•Penalize popular concepts•δc i=1P(c i)2. Hierarchy-based Approach（Average first passage time）•argmaxC q k σc∈C q kσqi∈qℎ(q i|c)•൝ℎq i c=0,if q i=c ℎq i c=1+σc′∈c(c′)P c′q iℎ(c′|c)if q i≠c•发现实体间的潜在关联具有重要应用价值•KG为实体间的关系提供了数据支撑•挑战：两个实体间的关联路径可能有多条哪种关系才是最该展现的？ISIS头目与一位伊朗少将之间的关联路径[4]•问题转化为对实体间的各条路径进行排序，主要考虑三个要素[4]•Specificity：流行的实体得分要低（类似IDF基本思想）score1p=σe∈p spec e,spe p=log(1+1/docCount(e))•Connectivity:路径中一条边e1,e2的权重与e1和e2的相似度成正比score2p=σ(e1,e2)∈p sim e1,e2,sim e1,e2=cos(e1,e2)•Cohesiveness:要考虑紧挨着的两条边（三个实体）之间的凝聚度score3p=(e1,e2,e3)∈psim e1+e2,e3•最终，score p=score1p×score2p×score3pe1是DSM模型[5]产生的实体向量，也可以用前述的方法计算两个实体的相似度•展现实体关系图谱•基于实体间发现的重要关系，可将目标实体与所有挖掘出的相关实体一同展现到一个关系图谱中，为搜索用户提供更加丰富的信息参考文献[1]L.Chen,J.Liang,C.Xie and Yanghua Xiao.“Short Text Entity Linking with Fine-grained Topics”.CIKM(2018).[2]Bron, Marc, K. Balog, and M. D. Rijke. “Ranking related entities: components and analyses.”ACM International Conference on Information and Knowledge Management ACM, 2010:1079-1088.[3]Y.Zhang, Yanghua Xiao et al. “Entity Suggestion with Conceptual Expanation”.IJCAI(2017).[4]Aggarwal, Nitish, S. Bhatia, and V. Misra. “Connecting the Dots: Explaining Relationships Between Unconnected Entities in a Knowledge Graph.” (2016).[5]N. Aggarwal and P. Buitelaar. Wikipedia-based distributional semantics for entity relatedness. In AAAI Fall Symposium Series, 2014.内容提纲•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐电影（豆瓣）图书（亚马逊）推荐系统应用挂广泛•推荐算法的目标p(i|u)或者f:U×I Rargmaxi∈I•推荐算法分类•基于协同过滤:p(i|u,behavior(u))•基于记忆•基于模型•基于内容:p(i|u,content(u,i))•混合方法•基于知识:p(i|u,knowledge)•推荐算法的基本框架精准的用户/物品画像是关键•传统推荐算法的挑战•基于协同过滤•冷启动•数据稀疏•可扩展性•……•基于内容•特征描述•同义/多义词•结果同质性•……❑提高精准度（precision ）❑知识图谱为物品引入了更多的语义关系❑知识图谱可以深层次地发现用户兴趣推荐系统中引入知识图谱的优势：喜欢盗梦空间小李子泰坦尼克号主演主演可能喜欢❑增加多样性（diversity）❑知识图谱提供了不同的关系连接种类❑有利于推荐结果的发散，避免推荐结果越来越局限于单一类型推荐系统中引入知识图谱的优势：喜欢盗梦空间小李子泰坦尼克号主演主演科幻黑客帝国克里斯托弗·若兰敦刻尔克题材题材导演导演推荐系统中引入知识图谱的优势：❑可解释性（interpretability）❑知识图谱可以连接用户的兴趣历史和推荐结果❑提高用户对推荐结果的满意度和接受度，增强用户对推荐系统的信任喜欢盗梦空间你可能也喜欢：泰坦尼克号，因为它们有相同的主演；黑客帝国，因为它们有相同的题材；敦刻尔克，因为它们有相同的导演；……内容提纲•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐•基于约束的知识化推荐•什么是约束知识？•通过用户的输入限定物品属性值形成规则集合，形成候选物品的范围约束——关于用户的知识•例如：电影的演员、歌曲的演唱者、餐馆的菜系、手机的价位等类似基于输入条件的查询大众点评餐馆查询/推荐的属性选择页面•基于个案的知识化推荐•什么是个案知识？•先通过某种算法产生一组候选物品给用户选择，将用户的选择作为参照物，再通过物品间的相似性计算找出其他与参照物品高度相似的候选物品，再让用户进一步选择，多次与用户的迭代交互，直至最终产生用户最想要的物品类似问答式的搜索•传统的推荐系统对知识的理解不同于KG的知识•用户的标签、社交网络、商品的目录等信息，只要是有助于发现用户个性偏好和物品特征的数据都曾被看作是知识传统用户/物品知识vs知识图谱知识•传统知识化推荐的挑战•物品知识的获取•系统需要人工构建知识，对长尾实体的覆盖有限•用户知识的获取•系统需要用户输入信息，甚至要反复交互，体验感差知识图谱的出现为解决这些问题带来契机！内容提纲•基于知识图谱的搜索•搜索意图理解•实体探索•基于知识图谱的推荐•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐•基本算法目标p(i|u,knowledge(i))argmaxi∈I•基于向量空间模型[2]•为每种属性生成一个表示向量，每一维对应该属性的某个值的权重•例如，电影的演员属性可以表示成一个向量，第一维的值可以是第1号演员对该电影的TF-IDF权重值TF-IDF值如何计算？•两部电影在某种属性上的相似度可以计算为该属性的两个向量的距离•两部电影的相似度则是所有属性相似度的综合，例如加权和或加权平均每种属性的权重如何考虑？•基于向量空间模型[2]用户u对电影m i的喜好评分按照以下公式计算：属性p的权重电影I和j在属性p上的相似度。
