赵康智(清华大学,微软亚洲研究院实习生)、王希廷、谢幸作者社会计算组原创

SIGIR 2020 | 知识图谱上推荐推理的模仿学习框架

编者按:尽管知识图谱推理的发展前景广阔,但在收敛性和可解释性上仍存在一定的问题。微软亚洲研究院的研究员利用一个基于元启发式方法的示例路径抽取方法来以较低的标记代价提取示例路径集合,进而提出了一个对抗的 Actor-Critic 模型来进行示例路径指导下的路径搜索。实验结果表明,这一方法在推荐准确性和可解释性方面均优于最新的基线方法。

知识图谱推荐推理

知识图谱如今被广泛用于提高推荐算法的准确性方面。同时,知识图谱上用户-物品的多跳连接关系也赋予了系统进行推荐推理(Recommendation Reasoning)的能力,让图谱上的路径可以用来表示推荐某个物品的具体原因。例如,在向用户 Bob 推荐“Acalme Sneaker”这双鞋时,推荐的原因可以从如下连接关系中推理得到:

这条路径说明推荐“Acalme Sneaker”给 Bob,是因为 Bob 曾经购买过同品牌(Nike)的鞋 Revolution 5 Running Shoe。

与基于自然语言的解释相比,这种知识图谱推理很少得出关于物品的错误论断,例如错误地描述物品的品牌或生产商。这是因为路径上的边都是知识图谱中已经确为事实的知识。另外,知识图谱推理能够忠实地反映出推荐模型的工作机理,这样就增加了用户的信任度和满意度。

知识图谱推理尽管有很好的发展前景,但是仍然存在着巨大的研究挑战。传统的推荐方法侧重于根据用户的偏好,为给定的候选物品集合进行打分,而知识图谱推理还需要在复杂的知识图谱中识别可行的候选路径(路径查找)。现有研究主要的重心在前者,常常使用缺乏有效监督的蛮力算法来进行路径查找,导致了算法在收敛性和可解释性方面的问题。

收敛性:现有的方法缺少有效地指导和监督路径查找的机制。例如,现有的穷举搜索的方法可以枚举知识图谱上所有可能的候选路径,但这在大规模的知识图谱上是不可行的。REINFORCE 通过路径采样得到稀疏的奖励信号,来逐渐地改进策略。由于奖励信号的稀疏性和知识图谱巨大的动作空间,使得这种反复试验的方法收敛性较差。

可解释性:现有的方法仅优化推荐准确度这一个目标,无法保证生成的路径有较高的解释性。连接同一用户-物品组合可能有多条路径导致相同的推荐准确性,而某些路径作为推荐原因时的说服力并不强。为了实现良好的可解释性,将用户真正感兴趣的实体和关系类型纳入路径当中十分重要。同时,除了在路径中纳入上述的实体和关系类型,路径本身的类型对可解释性也很重要。例如,考虑以下两种路径类型:

“看过商品 A 的用户也看过”这种类型的路径在说服力上就弱于“买过商品 A 的用户也买过”的路径类型。

为了解决上面的问题,本文尝试通过引入不完善的示例路径(Imperfect Demonstration Paths)来解决这些问题。文中介绍了如何使用极少标注快速得到示例路径,还设计了一个基于模仿学习知识图谱推理框架,从而使示例路径这样的弱监督信号可以和增强学习中的稀疏奖励信号自然结合。在这个框架的基础上,我们提出了对抗的 Actor-Critic(Adversarial Actor-Critic,ADAC)模型来进行示例路径指导下的路径搜索。实验表明,该方法比现有的方法收敛得更快,同时能够获得更好的推荐准确性和可解释性。

示例路径抽取

为了得到对知识图谱推理有用的不完善的示例路径,我们提出了一个基于元启发式方法的抽取方法。元启发式方法是“可被用来定义启发式方法的概念”,常被用来解决组合优化问题。通过指定示例路径需要的属性,来定义元启发方法。这些属性被进一步用来定义示例路径抽取的启发式规则。具体来说,考虑以下三种属性:

P1:可得性。示例路径通过较低的标记代价得到。

P2:可解释性。示例路径比随机采样得到的路径更有解释性。

P3:准确性。示例路径指向准确的推荐结果。例如,该路径能够连接用户和他/她交互过的物品。

只要满足上述三个属性,抽取的示例路径就被认为是有效的,即使它们是稀疏而且有噪声的(不完善)。基于这些属性,我们定义了三种抽取示例路径的启发式规则。

最短路径。研究表明,精炼的解释降低了用户的认知负担,同时被认为是更具解释性的。因此用户-物品组合之间更短的路径比随机采样的连接更具解释力(P2)。为了保证准确性(P3),我们仅考虑连接用户 u 和他交互过的物品 v_u 的路径作为示例路径。具体而言,给定(u, v_u),首先从知识图谱上去除 u 和 v_u 之间观察到的交互。这样就得到了一个新的知识图谱。随后将 G 视为无权重的图,并使用 Dijkstra 算法来自动生成 u 和 v_u 之间的最短路径(P1)。将生成的最短路径作为示例路径。之后对所有用户和其交互过的物品重复这个过程,来得到一组示例路径。

元路径。元路径(Meta-Path)是实体类型和关系构成的序列。在知识图谱推理中,元路径自然对应着元级别的解释策略。通过提供元路径,就可以得到理想的解释策略。我们的框架是通过极少量(1~3条)人工定义的元路径来提高模型性能(P1)。只要这些元路径被认为比随机采样的元路径更具解释力,他们就应当是有效的(P2)。与现有的基于元路径的方法相比,由于不需要上述预定义的元路径是完备的或是最优的,所以这一方法可以显著地减少人工标注的成本。之所以能够使用这些并不完善的元路径作为输入,是因为我们利用了元路径来指导路径搜索,而非限制搜索空间。为了基于这些预定义的元路径生成示例路径,我们在知识图谱上进行了有限制的随机游走,将每个用户 u 作为随机游走的起点,然后仅采样那些元路径属于预定义集合的路径。在所有采样得到的路径中,只保留那些通向用户交互过物品的路径,并将其作为示例路径(P3)。

兴趣路径。一个更具解释力的推理路径应当在实体级别符合用户的兴趣,比如路径中包含用户感兴趣的实体。在一些数据集中,得到实体级别的用户兴趣相对比较容易。例如,在包含用户评论的数据集中,可以通过查找实体是否出现在用户的评论中,来自动判断路径上的实体是否符合用户的兴趣(P1)。在这种情况下,使用随机游走得到一组路径,并查看每条路径中的实体是否多数符合用户兴趣,并仅保留那些符合用户兴趣的路径(P2),同时,去除那些没有将用户与其交互过的物品连接起来的路径,以保证准确性(P3),并将剩余路径作为示例路径。

推荐推理的模仿学习框架

我们提出了一种能够同时利用含有用户交互关系的知识图谱和提取的示例路径的方法。模型要解决的主要问题,是如何在一个统一的框架内,对不完善的示例路径、观察到的交互关系和知识图谱上的隐含事实进行高效地建模。为了实现这一目标,我们设计了对抗 Actor-Critic(ADversarial Actor-Critic,ADAC)模型,综合应用了基于 Actor-Critic 的强化学习和对抗模仿学习

图1:对抗 Actor-Critic 模型进行示例路径指导下的路径搜索如图1所示的模型框架。其中,知识图谱是马尔科夫决策过程环境(MDP  environment)的一部分。Actor 用来学习路径搜索策略,它与 MDP 环境进行交互,从而得到知识图谱上的搜索状态(State)和可能的行为(Action)。通过环境给出的奖励(reward)反馈 𝑅_𝑒,𝑡,Actor 判断现在的策略是否是用户感兴趣的。为了进一步集成示例路径,我们设计了一个对抗模仿学习模块(蓝色部分),包含有两个鉴别器(Discriminator)。鉴别器用来区分专家路径和 Actor 生成的路径,而 Actor 通过模仿专家示例路径,来“混淆”鉴别器,使它更难作出区分。当动作路径与专家示例路径在元路径级别(Meta-path Level)相似和路径级别(Path Level)相似时,模仿学习模块就会分别给 Actor 以更高的元路径奖励 𝑅_𝑚,𝑡 及路径奖励 𝑅_𝑝,𝑡。这样就得到了三种类型的奖励,𝑅_𝑒,𝑡、𝑅_𝑚,𝑡 和 𝑅_𝑝,𝑡。它们进一步由 Critic 建模,来精确地预测每个动作的价值。通过奖励梯度的无偏估计,学得的价值信息就用来训练 Actor。

Actor 网络构建。Actor 学习一个路径搜索策略,它计算的是在状态和可能的动作空间的条件下,动作的条件概率分布。我们使用全连接层和 Softmax 函数来建模 Actor 网络。

对抗模仿学习。对抗模仿学习模块包含两个部分:路径鉴别器和元路径鉴别器。路径鉴别器 𝐷_𝑝 判断在每个时间 𝑡 时,Actor 是否能够生成一个与示例路径相似的路径段,元路径鉴别器 𝐷_𝑚 通过比较元路径,来判断 Actor 所采用的总体解释策略是否与示例路径的策略相似。路径鉴别器与元路径鉴别器的损失函数和得到的奖励有相似的形式:

Critic 网络构建。Critic 的目标是高效地建模来自强化学习(即 MDP 环境)和模仿学习(即鉴别器)的奖励信息。给定状态, Critic 网络计算每个动作 𝑎_𝑡 的价值为 Q_ϕ (s_t,a_t),并利用时间差分方法来学习 Critic 网络。首先根据贝尔曼方程计算学习目标:

其中 𝑅_𝑡 是混合奖励,它一方面激励路径搜索策略,使之搜索到与示例路径更相似的路径,另一方面让策略得到更高的推荐准确性。之后,Critic 通过最小化如下 TD 误差(TD Error)来更新参数

给定 𝑄_𝜙(𝑠_𝑡,𝑎_𝑡),Actor 再通过最小化以下损失函数来学习参数

性能评测

我们在亚马逊三种不同的物品类别上验证了提出的模型:Beauty(美妆产品)、Clothing Shoes and Jewelry(服饰鞋帽)和 Cell Phones and Accessories(手机及配件)。这里为了公平只用了最短路径得到示例(没有额外人工标注)。实验结果表明,与基线方法相比,Actor-Critic 方法在推荐准确性方面取得了更好的结果。

表1:推荐准确性比较为了评估推理路径的可解释性,我们使用真实的评论文本设计了两个评价指标。设计可解释性评价指标的基本思想是,用户发表的真实评论文本揭示了用户-物品之间产生交互的原因。因此,如果一个推理路径包含很多真实评论中提到的词语,那它应当有很好的可解释性。具体而言,对每个推荐正例,过滤掉评论中出现频率大于5000或者 TF-IDF 得分小于0.1的词语,将剩下的词语作为真实词语。然后将路径中的实体集合起来,并按照它们的频率进行排序,将实体类型是 Word、Brand 或者 Category 的实体,提取其字符串作为抽取的解释词语。我们通过比较推理路径抽取的解释词语和真实词语的相似程度来评价可解释性。同时,也基于匹配词语使用精确率(Precision)和召回率(Recall)来评价可解释性。
表2:可解释性比较比较 ADAC 在 Beauty 和 Clothing 数据集上的收敛性可以看到,ADAC 通过有效利用示例路径在路径级别和元路径级别的信息实现了高效地收敛
图2:收敛性比较我们还对比了使用不同种类的示例路径对模型准确性和可解释性的影响。图3展示了使用不同示例路径得到的推理路径,可以看到利用我们的模仿学习框架,模型不仅能够找到与示例路径相同类型的推理路径,还能泛化到其它种类的路径上来。
图3:使用不同示例路径生成的推理路径总结

本文设计了一种基于模仿学习知识图谱推理框架,来为用户进行可解释推荐,它解决了知识图谱推理时遇到的收敛性和可解释性问题。首先利用一个基于元启发式方法的示例路径抽取方法来以较低的标记代价提取示例路径集合。然后提出了一个对抗的 Actor-Critic 模型,进行示例路径指导下的路径搜索。实验结果表明,这一方法在推荐准确性和可解释性方面均优于最新的基线方法。

了解更多技术细节,请点击阅读原文查看论文

Leveraging Demonstrations for Reinforcement Recommendation Reasoning over Knowledge Graphs

本文作者:赵康智(清华大学微软亚洲研究院实习生)、王希廷、谢幸

微软研究院AI头条
微软研究院AI头条

专注科研19年,盛产黑科技

理论模仿学习知识图谱SIGIR 2020
相关数据
微软亚洲研究院机构

微软亚洲研究院于1998年在北京成立,是微软公司在亚太地区设立的基础及应用研究机构,也是微软在美国本土以外规模最大的一个研究院。微软亚洲研究院从事自然用户界面、智能多媒体、大数据与知识挖掘、人工智能、云和边缘计算、计算机科学基础等领域的研究,致力于推动计算机科学前沿发展,着眼下一代革命性技术的创新,助力微软实现长远发展战略。通过与微软产品部门紧密合作,微软亚洲研究院将众多创新技术转移到了微软的核心产品中,如Office、Windows、Azure、Bing、Visual Studio、Xbox Kinect以及小冰、Cortana和Microsoft Translator等人工智能产品。

https://www.msra.cn/
清华大学机构

清华大学(Tsinghua University),简称“清华”,由中华人民共和国教育部直属,中央直管副部级建制,位列“211工程”、“985工程”、“世界一流大学和一流学科”,入选“基础学科拔尖学生培养试验计划”、“高等学校创新能力提升计划”、“高等学校学科创新引智计划”,为九校联盟、中国大学校长联谊会、东亚研究型大学协会、亚洲大学联盟、环太平洋大学联盟、清华—剑桥—MIT低碳大学联盟成员,被誉为“红色工程师的摇篮”。 清华大学的前身清华学堂始建于1911年,因水木清华而得名,是清政府设立的留美预备学校,其建校的资金源于1908年美国退还的部分庚子赔款。1912年更名为清华学校。1928年更名为国立清华大学。1937年抗日战争全面爆发后南迁长沙,与北京大学、南开大学组建国立长沙临时大学,1938年迁至昆明改名为国立西南联合大学。1946年迁回清华园。1949年中华人民共和国成立,清华大学进入了新的发展阶段。1952年全国高等学校院系调整后成为多科性工业大学。1978年以来逐步恢复和发展为综合性的研究型大学。

相关技术
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

损失函数技术

在数学优化,统计学,计量经济学,决策理论,机器学习和计算神经科学等领域,损失函数或成本函数是将一或多个变量的一个事件或值映射为可以直观地表示某种与之相关“成本”的实数的函数。

知识图谱技术

知识图谱本质上是语义网络,是一种基于图的数据结构,由节点(Point)和边(Edge)组成。在知识图谱里,每个节点表示现实世界中存在的“实体”,每条边为实体与实体之间的“关系”。知识图谱是关系的最有效的表示方式。通俗地讲,知识图谱就是把所有不同种类的信息(Heterogeneous Information)连接在一起而得到的一个关系网络。知识图谱提供了从“关系”的角度去分析问题的能力。 知识图谱这个概念最早由Google提出,主要是用来优化现有的搜索引擎。不同于基于关键词搜索的传统搜索引擎,知识图谱可用来更好地查询复杂的关联信息,从语义层面理解用户意图,改进搜索质量。比如在Google的搜索框里输入Bill Gates的时候,搜索结果页面的右侧还会出现Bill Gates相关的信息比如出生年月,家庭情况等等。

贝尔曼方程技术

“贝尔曼方程(Bellman Equation)”也被称作“动态规划方程(Dynamic Programming Equation)”,由理查·贝尔曼(Richard Bellman)发现。贝尔曼方程是动态规划(Dynamic Programming)这种数学最佳化方法能够达到最佳化的必要条件。此方程将“决策问题在特定时间点的值”以“来自初始选择的报酬 及 由初始选择衍生的决策问题的值”的形式表示。藉这个方式将动态最佳化问题变成较简单的子问题,而这些子问题遵守由贝尔曼所提出的“最佳化原理”。

条件概率分布技术

条件概率分布(Conditional Probability Distribution,或者条件分布,Conditional Distribution )是现代概率论中的概念。 已知两个相关的随机变量X 和Y,随机变量Y 在条件{X =x}下的条件概率分布是指当已知X 的取值为某个特定值x之时,Y 的概率分布。

模仿学习技术

模仿学习(Imitation Learning)背后的原理是是通过隐含地给学习器关于这个世界的先验信息,就能执行、学习人类行为。在模仿学习任务中,智能体(agent)为了学习到策略从而尽可能像人类专家那样执行一种行为,它会寻找一种最佳的方式来使用由该专家示范的训练集(输入-输出对)。

强化学习技术

强化学习是一种试错方法,其目标是让软件智能体在特定环境中能够采取回报最大化的行为。强化学习在马尔可夫决策过程环境中主要使用的技术是动态规划(Dynamic Programming)。流行的强化学习方法包括自适应动态规划(ADP)、时间差分(TD)学习、状态-动作-回报-状态-动作(SARSA)算法、Q 学习、深度强化学习(DQN);其应用包括下棋类游戏、机器人控制和工作调度等。

推荐文章
暂无评论
暂无评论~