知识图谱 概念与技术 第12章：基于知识图谱的搜索与推荐

《知识图谱:概念与技术》pleyangdeqing2018/8/30基于知识图谱的搜索与推荐2•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐2018/8/30基于知识图谱的搜索与推荐3•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐基于知识图谱的搜索容？基于知识图谱的搜索thing/entity相关实体、概念有关的属性基于知识图谱的搜索thing/entity相关实体、概念有关的属性relatedthings潜在关系2018/8/30基于知识图谱的搜索与推荐7发现匹配结果匹配结果排序相关结果推荐•目标实体、属性的查找•关联计算•排序学习•目标实体的属性展示•相关实体、概•展现目标实体发现匹配结果匹配结果排序相关结果推荐•目标实体、属性的查找•关联计算•排序学习•目标实体的属性展示•相关实体、概•展现目标实体与相关实体间•……Web流程确确定搜索目标•分词•规则解析•实体识别•实体链接•……2018/8/30基于知识图谱的搜索与推荐8•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐2018/8/30基于知识图谱的搜索与推荐9搜索意图理解短文本，因此搜索意图的理解最主要•将指代实体的文本mention链接到知识库中特定实体的过程•实体解析/命名实体识别entityresolution/nameentityrecognition•共指消解co-referenceresolution•词义消岐wordsensedisambiguation•……2018/8/30基于知识图谱的搜索与推荐10马短文本实体链接马•同一个实体在广泛的文本中可能有多个mention(指代词)•SenatorObamas•同一个指代词可能指代多个不同实体•算法目标•利用实体指代词m与候选实体e的上下文等相关特征计算两者的匹配度分数pe,m，按分数进行排序，并选择分数最大的实体ebest作为m的链接结果，即ebest=aTgmaxpe,me•局部模型•为短文本中的每个指代词及其链接的实体单独计算pe,m，每个链接实体都是独立产生•全局模型•考虑文本中多个指代词所链接的实体间联系，对上下文内所有歧义的实体指代一同消歧•令T={m1,e1,m2,e2…}为一个全局实体链接方案，则目标函数为：NTbest=aTgmaxTOT=aTgmaxT⃞pmi,ei+⃞wei,eji=1tj∈T2018/8/30基于知识图谱的搜索与推荐12短文本实体链接{SteveJobs,SteveWozniak,SteveBallmer,...}2018/8/30基于知识图谱的搜索与推荐13短文本实体链接•文本相似度•计算候选实体上下文文本(如百科页面)与指代词上下文的相似度•候选实体上下文：实体的百科页面(或摘要文字)、实体锚文本•指代词上下文：指代词所在的段落/文档、紧挨指代词前后的n个词量、概念(主题)向量2018/8/30基于知识图谱的搜索与推荐14短文本实体链接•实体间的相似度•计算候选实体e1与上下文中的实体e2的相似度分数，通常利用两个实体的邻居集合U1和U2进行比较|U1∪U2|||U1∪U2|•Jaccarde1,e2=U1/|W|∗|U2|/|w|•PMIe1,e2=UU1/|W|∗|U2|/|w|logmax|U1|,|U2|−loglogmax|U1|,|U2|−logU1∩U2log|w|−logmin|U1|,|U2|•AdamicAdare1,e2=σn∈U1∩U2log2018/8/30基于知识图谱的搜索与推荐15短文本实体链接•训练数据缺乏•难以训练出符合应用环境的监督模型•上下文中的其他实体少•局部模型起主导作用•上下文中的词语少•通常只提供了模糊的主题信息•“红楼梦是谁写的”•“写”->“文学作品”->红楼梦(四大名著之一)2018/8/30基于知识图谱的搜索与推荐16短文本实体链接•因为短文本上下文的信息量少，利用主题是比较流行的做法•潜在的主题(LDA)•难以捕捉到实体的细粒度特征•难以解释•手工构造的主题•难以扩展•可以捕捉实体细粒度特征•大量的信息(实体的文章和属性)•大覆盖度(甚至囊括新实体或者长尾实体)2018/8/30基于知识图谱的搜索与推荐17短文本实体链接•首先实体与指代词之间的主题/概念相似度simcm,e=cosvcm,vcevce是实体的概念向量，vcm是指代词上下文的概念向量，计算如下：vcm=vcm=⃞D(w,m)w∈CT(m)CT(m)是上下文词集合•词的概念向量vcw的每一维如下计算Tw,c=⃞e∈E2018/8/30基于知识图谱的搜索与推荐18短文本实体链接•再计算实体与指代词之间的文本相似度simtm,e=maxwCeCTm,wdeKP(e)cosvwwc,vwwdKP(e)是关键词组集合，从实体相关文档与属性中抽取•另外再考虑与上下文无关的特征相似度•实体流行度•实体名与指代词的相似度•综合几类相似度分数得到实体与指代词间的最终相似度pe,m2018/8/30基于知识图谱的搜索与推荐19短文本实体链接NT=argx⃞pe,mi+wT′•其中实体凝聚度(实体间的相关度)为wT=⃞coℎei,ejei∈T,ej∈T此•NP难的全局算法复杂度可以接受•不需要近似算法2018/8/30基于知识图谱的搜索与推荐201,1,,•结合实体相似度和相关度coℎe1,e2=y·simee1,e2+1−y·rele1,e2•simee1,e2相似度：可考虑NGD距离•rele1,e2相关度首先计算rel′e1,e2=⃞r∈R(e1,e2)2Ter+HreR(e1,e2)是e1,e2之间的关系集合，Te1,r={e′|e1,r,e′∈KG}，H(r,e2)={e′|e′,r,e2∈KG}•像“配偶”和“父母”这样对应少的关系会有大权值•像“国家”和“出生地”这样对应多的关系会有小权值•由于逆关系通常对应的是同一个关系，因此两个方向取最大值得到rele1,e2=max(rel′e1,e2,rel′e2,e1)2018/8/30基于知识图谱的搜索与推荐21•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐2018/8/30基于知识图谱的搜索与推荐22容•展现实体的属性信息•发现(推荐)更多相关实体•KG中的邻居实体(包括直接邻居和高阶邻居)•对目标实体进行概念化的说明/解释•展现目标实体与相关实体间的关系•……相关实体发现/推荐相关实体相关实体相关实体发现/推荐]•对于给定的一个实体es，并针对目标实体e所属的类型T及其与给定实体的相关实体发现/推荐•实体共现相关度•实体类型过滤•利用百科实体页面中的分类信息•上下文建模的共现文档集合中，则是实体e与es的共现语言模型，t越多地出现在的共现文档集合中，则2018/8/30基于知识图谱的搜索与推荐26•问题定义[3]•给定由一组实体代表的查询q，产生一个(组)概念能完美解释给定实体间的潜在联系•q中包括搜索实体与推荐的相关实体，因此产生的概念是发现相关实体的基础找到的概念既要有代表性又要能很好地在找到的概念既要有代表性又要能很好地在最优的粒度层级上解释所推荐的相关实体利用Probase发现概念与实体间的关系•寻找的概念ci应满足下述目标PecPeciPciq6(ci)argmaxrelq,ee∈E−qiargminKLPCq,PCq,ee∈E−qn P(ci|q)=6(ci)Pciqlog(P(ci P(ci|q)•计算P(ci|q)1.NaïveBayesModelP(q|ci)P(ci)Pciq=P(q)∝⃞P(P(q|ci)P(ci)ej∈q∝P(ci)⃞入P(ej|ci)⃞(1−入)P(ej)ej∈q,nej,ci>0ej∈q,nej,ci=0Pciq=1−⃞(1−P(ci|ej))ej∈q距离q中实体更近的概念更值得考虑距离q中实体更近的概念更值得考虑il•计算6(ci)•计算6(ci)•Penalizepopularconcepts•6ci=2.Hierarchy-basedApproach(Averagefirstpassagetime)q•argCaxσc∈Cσqi∈qℎ(qi|c)qℎqic=0,ifqi=c•⃞ℎqic=1+σc′∈c(c′)Pc′ℎqic=0,ifqi=c2018/8/30基于知识图谱的搜索与推荐31•发现实体间的潜在关联具有重要应用价值•KG为实体间的关系提供了数据支撑•挑战：两个实体间的关联路径可能有多条2018/8/30基于知识图谱的搜索与推荐32eDSM]产eDSM]产•问题转化为对实体间的各条路径进行排序，主要考虑三个要素[4]•Specificity：流行的实体得分要低(类似IDF基本思想)score1p=σe∈pspece,spep=log(1+1/docCount(e))•Connectivity:路径中一条边e1,e2的权重与e1和e2的相似度成正比score2p=σ(e1,e2)∈psime1,e2,sime1,e2=cos(e1,e2)•Cohesiveness:要考虑紧挨着的两条边(三个实体)之间的凝聚度score3p=⃞sime1+e2,e3(e1,e2,e3)∈pscorep=score1p×score2p×score3p2018/8/30基于知识图谱的搜索与推荐33•展现实体关系图谱•基于实体间发现的重要关系，可将目标实体与所有挖掘出的相关实体一同展现到一个关系图谱中，为搜索用户提供更加丰富的信息2018/8/30基于知识图谱的搜索与推荐34参考文献[1]L.Chen,J.Liang,C.XieandYanghuaXiao.“ShortTextEntityLinkingwithFine-grainedTopics”.CIKM(2018).[2]Bron,Marc,K.Balog,andM.D.Rijke.“Rankingrelatedentities:componentsand2010:1079-1088.[3]Y.Zhang,YanghuaXiaoetal.“EntitySuggestionwithConceptualExpanation”.IJCAI(2017).hSBhatiaandVMisraConnectingtheDotsExplainingRelationshipsBetweenUnconnectedEntitiesinaKnowledgeGraph.”(2016).[5]N.AggarwalandP.Buitelaar.Wikipedia-baseddistributionalsemanticsforentityrelatedness.InAAAIFallSymposiumSeries,2014.2018/8/30基于知识图谱的搜索与推荐35•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐图书(亚马逊)新闻(今日头条)音乐(网易云音乐)基于知识图谱的推荐图书(亚马逊)新闻(今日头条)音乐(网易云音乐)电影(豆瓣)餐馆(大众点评)2018/8/30基于知识图谱的搜索与推荐37基于知识图谱的推荐IRieI•基于协同过滤:p(i|u,behavior(u))•基于记忆•基于模型•基于内容:p(i|u,content(u,i))•混合方法•基于知识:p(i|u,knowledge)2018/8/30基于知识图谱的搜索与推荐38基于知识图谱的推荐2018/8/30基于知识图谱的搜索与推荐39基于知识图谱的推荐•基于协同过滤•冷启动•数据稀疏•可扩展性•……•基于内容•特征描述•结果同质性•……基于知识图谱的推荐口提高精准度(precision)口知识图谱为物品引入了更多的语义关系口知识图谱可以深层次地发现用户兴趣喜欢盗梦空间基口知识图谱提供了不同的关系连接种类口有利于推荐结果的发散，避免推荐结果越来越局限于单一类型科导演敦刻尔克导演敦刻尔克基于知识图谱的推荐ity口知识图谱可以连接用户的兴趣历史和推荐结果喜欢盗梦空间2018/8/30基于知识图谱的搜索与推荐43•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐2018/8/30基于知识图谱的搜索与推荐44基于知识的传统推荐•通过用户的输入限定物品属性值形成规则集合，形成候选物品的范围餐馆的菜系、手机的价位等性选择页面基于知识的传统推荐•先通过某种算法产生一组候选物品给用户选择，似性计算找出其他与参照物品高度相似的候选代交互，直至最终产生用户最想要的物品索与推荐[1]2018/8/30基于知识图谱的搜索与推荐46基于知识的传统推荐同于KG的知识•用户的标签、社交网络、商品的目录等信息，只要是有助于发现用户个vs知识图谱知识2018/8/30基于知识图谱的搜索与推荐47基于知识的传统推荐•物品知识的获取•系统需要人工构建知识，对长尾实体的覆盖有限•用户知识的获取差2018/8/30基于知识图谱的搜索与推荐48•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐2018/8/30基于知识图谱的搜索与推荐49基于知识图谱的物品画像argmaxp(i|u,knowledge(i))i∈I]•为每种属性生成一个表示向量，每一维对应该属性的某个值的权重•例如，电影的演员属性可以表示成一个向量，第一维的值可以是第1号演员对该电影•两部电影在某种属性上的相似度可以计算为该属性的两个向量的距离•两部电影的相似度则是所有属性相似度的综合，例如加权和或加权平均2018/8/30基于知识图谱的搜索与推荐50电影I和j在属]l基于知识图谱的物品画像tionNetwork•将物品和其每种属性值对应的实体都表示成异构信息网络的一类结点，它•例如，每部电影和其每个演员都由一条表示“参演”的边相连•因为不同物品间会共享某些属性对应的实体，所以会有一条经过该共享实path•例如，成龙主演的不同电影之间都通过一条“电影-演员(成龙)-电影”的元路径相连基于知识图谱的物品画像•基于异构信息网络[3]异构信息网络图[3]包含多种类型结点和多种类型边的图称之为异构信息网络SSpv是电影v在属性p上 simp2×|Spv simp|Sp(v)|+|Sp(v′)|一般基于Skip-gram一般基于Skip-gram模型•基于随机游走的graphembedding模型•在异构信息网络图中应用基于随机游点的向量表示(即画像)•DeepWalk•Node2Vec•Metapath2Vec[4]•HIN2Vec基于知识图谱的物品画像•基于KGembedding模型dding•TransE•TransD•TransH•TransR基于知识图谱的物品画像•基于KGembedding模型•应用实例DeepKnowledge-awareNetwork(DKN)[5]口实体间的语义关系难以被传统方法(话题模型、词向量方法)发掘基于知识图谱的物品画像•基于KGembedding模型•应用实例DeepKnowledge-awareNetwork(DKN)口实体连接(entitylinking)口知识图谱构建(knowledgegraphconstruction)口知识图谱特征学习(knowledgegraphembedding)口得到实体特征(entityembedding)基于知识图谱的物品画像•基于KGembedding模型•应用实例DeepKnowledge-awareNetwork(DKN)特征 (contextualentityembeddings)对实验证明TranD效果最好示基于知识图谱的物品画像•基于KGembedding模型•应用实例DeepKnowledge-awareNetwork(DKN)荐模型KGembedding基于知识图谱的物品画像•基于深度学习的知识融合模型•应用实例CollaborativeKnowledgebaseEmbedding(CKE)[6]•通过不同的embedding/编码器模型将物品综合成•基于用户-物品交互记录生成用户表示向量•用户向量和物品向量都灌入神经网络，依否值得推荐给用户(物品匹配用户)基于知识图谱的物品画像•基于深度学习的知识融合模型•应用实例CollaborativeKnowledgebaseEmbedding(CKE)物品的不同类型知识用不同的模型表示2018/8/30基于知识图谱的搜索与推荐61•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐2018/8/30基于知识图谱的搜索与推荐62基于知识图谱的用户画像argmaxp(i|u,knowledge(u))i∈I•标签是用户画像的最常见手段•一般来说，描述用户的标签越多、越具体，对用户个性化推荐的帮助越大？2018/8/30基于知识图谱的搜索与推荐63基于知识图谱的用户画像•示例C9高校学生智能但是我们知道他俩存在相似性(潜在关联)基于知识图谱的用户画像•基于概念标签的用户画像[7]•过程描述•利用知识图谱的分类数据(如is_a关系)找出输入标签实体所属的概念，例如“复旦•新找出的概念或实体作为扩展标签的候选集•应用经典的机器学习算法，如MDL(最小描述长度)从扩展标签候选集中精选出满足目标的标签，且概念所属的分类层级又不至于太抽象基于知识图谱的用户画像•MDL算法•假设X是输入的一组标签(对应了知识图谱中的实体)，c是要寻找的概念，则c对X的编码长度为P(c)是概念c的先验概率，P(xi|c)是c能代表xi的分数，分别计算如下：n(c,e)是在知识图谱中能发现的某个实体e属于概念c(即两者构成isA关系)的数量，P(xi|c)则度量了对于一个概念c我们能想到属于它的一个实体e的程度基于知识图谱的用户画像•输出：国家or亚洲国家or东亚国家？基于知识图谱的用户画像画像[8]•算法过程•利用门控循环神经网络(GRU)生成用户的序列偏好向量htu作为用户u在t时刻的基•记忆网络的读取基于知识图谱的用户画像•基于深度学习模型的用户画像•算法过程•记忆网络的更新：每当记录到用户一条新交互记录(获取用户新看的一部电影)eai时，就对vau进行更新2018/8/30基于知识图谱的搜索与推荐69•搜索意图理解•实体探索•基于传统知识的推荐•基于知识图谱的物品画像•基于知识图谱的用户画像•基于知识图谱的跨领域推荐基于知识图谱的跨领域推荐•缓解冷启动问题•提高推荐精准度•增加推荐多样性•数据海量性•数据异构性•数据稀疏性•数据相依性•数据低质性基于知识图谱的跨领域推荐•跨领域推荐的几种场景•用户/物品完全重叠•能比较容易地将两个领域合并成一•用户/物品部分重叠•重叠的用户/物品成为新兴共享和•用户/物品完全不重叠•需要挖掘领域间隐含的共同用户/[10]基于知识图谱的跨领域推荐•主流的跨领域推荐算法•基于协同过滤•基于语义关系•基于深度学习•实现跨领域推荐的关键假设•用户的兴趣偏好或项目特征在领域之间存在一致性或相关性基于知识图谱的跨领域推荐•跨领域的实体关联[9]•利用知识图谱发现不同类实体间的关联路径，并计算相关度基于迭代的权重传播(类似PageRank)可算出头尾实体结点的Mahler的关联图谱[9]基于知识图谱的跨领域推荐•跨领域的特征语义关联[10,11]•针对用户和物品完全不重叠的特殊跨领域场景domainB?recommend基于知识图谱的跨领域推荐•跨领域的特征语义关联•首先构建一个多部图G(multi-partitegraph)[10]•基于Manifold算法找出领域1的用户与领域2的物品之间的潜在关联基于知识图谱的跨领域推荐•跨领域的特征语义关联•挑战在于如何找出两个领域特征(标签)之间的语义关联？即构建X0矩阵微概念向量间的距离可作为两个标签的语义距离，而和概念向量之间的距离(如NGD概念向量间的距离可作为两个标签的语义距离，而和概念向量之间的距离(如NGD[