精选 4 篇来自 WSDM 2019、NeurIPS 2018、WWW 2018 和 COLING 2018 的知识图谱相关工作,带你快速了解知识图谱领域最新研究进展。
本期内容选编自微信公众号「开放知识图谱」。
WSDM 2019
■ 论文解读 | 叶群,浙江大学计算机学院,研究方向为知识图谱、NLP
论文动机
基于 spring-electrical 的模型在网络可视化中取得了非常成功的应用,一个优秀的网络可视化算法意味着越相似的节点在空间中欧式距离越相近。 本文将 spring-electrical 模型应用在了链接预测问题上,前提是假设节点之间的欧氏距离和节点之间存在 link 的概率成正相关。 性能评估上,模型与 baseline 的对比显示了其性能的优越,尤其是在 node embedding 维度很低的时候。
问题描述
知识图谱由于种种原因,其中很多节点之间存在缺失的边。链接预测算法指的是,给定网络节点和网络结构等信息,去预测尚未存在边的节点之间存在链接的概率。
实验中,给定网络 G=
评估指标采用 AUC 值:
Baseline
介绍三种常用的 baseline。
1. Local similarity indices
分析节点周围的局部结构,作为节点之间存在链接的概率(以下式子中 δ 表示节点的相邻一跳节点)。
Common neighbours: 以两节点公共邻居的个数来衡量存在链接的概率。
Adamic-Adar index: common neighbours 的一种加权的改进。
Preferential Attachment index: 以节点现有的度来衡量节点之间存在链接的概率(非常 naïve 的 assumption)。
2. Matrix factorization
矩阵分解的方式将网络的邻接矩阵作为输入,分解成两个低秩的矩阵。低秩矩阵的行或列可以作为节点的 latent feature,将两节点的 latent feature 做点积,即可得到两节点之间存在链接的概率。
Truncate SVD
Non-negative matrix factorization(NMF)
3. Neural embedding
一些工作尝试用神经网络来学习 graph embedding,比如经典的 DeepWalk 和 node2vec 算法,都是受 word2vec 的启发。基本思想是将图中的节点当做单词,在图中随机游走得到一系列节点当作一个句子,然后利用 word2vec 的目标函数来做训练。训练完成后,将节点的 embedding 做点积,即得到节点之间存在链接的概率。
模型
Spring-electrical 中的 spring 指的是弹簧,electrical 指的是电荷,其基本思想是将一张图当做一个机械系统,将图中的节点比作电荷,将边比作弹簧。所有的电荷均为同性电荷,相互之间存在斥力;弹簧力表现为引力。
基于这样的假设,当这个力学系统达到平衡之后,不存在边相连的节点将会由于斥力,在空间距离上分布较远。
对库伦定律进行修改,引入超参 p,电荷之间的斥力公式为:
对虎克定律进行修改,弹簧的引力公式为:
通过利用力是能量的负梯度这个性质,可以将一个力学系统转换成能量系统,力的平衡对应系统能量的最小值。所以,目标函数为求解系统能量的极小值,即:
上式的求解存在两个问题:1)计算复杂度过大;2)容易收敛到局部极小值。 本文采用了一种叫做 ScalableForce Directed Placement(SFDP)的优化方法进行求解,较好地解决了这两个问题。
Case Study
在实际的数据集上进行评估之前,本文先在由球体的三角剖分得到的图上进行了 case study。链接预测的结果如下图所示,可以看到 SFDP 方法取得了很好的效果,同时注意到 SFDP 方法在向量维度极小的情况(d=2,3)下,依旧取得非常好的效果。
除此之外,实验将 d=3 的向量进行了可视化(如下图),比较了不同模型可视化的差异。可以看到,SFDP 方法很好的保留了球体的原始形状,SVD 向量分布在 3 条坐标轴上,node2vec 则是一个锥形。
造成这种差异的原因是,SFDP 采用了欧式距离作为损失函数,而 SVD 和 node2vec 则是基于点积。基于欧式距离的损失函数会使不相似的节点在空间上尽可能远,而点积则会使不相似节点尽可能垂直。
实验
实验在以下几个公开数据集上做了评估:PowerGrid: 美国的电力供应网络;Euroroad: 欧洲道路交通网络;Airport: 美国航空机场网络;Facebook: Facebook社交网络;Reactome: 蛋白质的相互作用网络;Ca-HepTh:arXiv上的作者合作关系网络。
实验结果如下图所示,SFDP 在多数数据集上的表现都达到最优,同时在向量维度 d=2,3 时就可以得到非常好的实验效果。
下表是得到最佳结果时 embedding 维度的比较,SFDP 方法在 d=2,3 维度时的结果就可以媲美其他模型 100 维甚至 500 维的效果,embedding 效率极高。
下表给出了 SFDP 模型与 localsimilarity indices 方法的效果比较:
另外实验还在二分网络和有向图数据集上进行评估,并对 SFDP 做了相应的修改。
总结
本文将网络可视化中的 spring-electrical 模型应用在了链接预测问题上,在数据集评估上取得了十分优越的结果,尤其是在低维空间展现了非常好的效果。Embedding 维度效率的提升可以解决向量嵌入在现实应用中的一些问题,如向量维度过高时最近邻搜索的计算复杂度过高。后续工作可以聚焦在如何为 latent feature model 选择更优的距离度量以及向量维度效率更深入的分析。
WWW 2018
■ 论文 解读 | 仲亮靓,东南大学硕士研究生,研究方向为基于知识图谱的推荐系统
动机
新闻文本的语言非常凝练,其中包含了很多实体和常识知识。但目前的新闻个性化推荐方法都没有利用这些外部知识,也没有使用新闻之间潜在的知识层面的联系。这就导致推荐的结果总是局限于简单额匹配,不能合理地扩展。
为了解决以上的问题,文章中提出了 基于内容的结合知识图谱来做新闻推荐(点击率预测)的方法 DKN(Deep Knowledge-aware Network) 。
贡献
文章的贡献有:
1. 新提出的 DKN 模型是基于内容的深度学习推荐模型,适合像新闻这样的具有高度时效性的推荐;
2. 设计了 KCNN(Knowledge-aware CNN)模块来联合学习新闻的语义层和知识层的表示;
3. 用 Attention 模块对用户历史点击过的新闻对于当前候选推荐新闻的影响程度进行建模。
方法
文中提出的模型图如图 1 所示。 输入:一个用户点击过的新闻的标题、一条候选推荐新闻的标题;输出:用户点击这条候选新闻的概率。
▲ 图1. DKN算法模型框架
步骤:
1. 将新闻标题中的词和知识图谱中实体做实体链接;
2. 为每个实体搜索它在知识图谱中的相邻实体(以此来获得更加丰富、具有区分力的信息);
3. KCNN(融合新闻的词表示和新闻表示,得到一个新闻的 Knowledge-aware 的向量表示)。
-
多通道(multi-channel):把 word embedding、entityembedding、上下文实体 embedding 作为 CNN 的三个通道;
-
词语-实体对齐(word-entity-aligned): 将标题中的词向量和实体向量一一对应,如果词向量在知识图谱中没有与之对应的实体,就用 0 向量来填充。
因为词向量和实体向量来自两个不同的向量空间且训练出来的相连的维度也不一样,所以通过一个线性 或非线性 的方法将实体向量映射到词向量空间中。最终得到新闻的如下形式的矩阵表示:
其中,w_i 表示标题中第 i 个词的词向量,e_i 表示与第 i 个词对应的实体的向量,\bar{e_i} 表示第 i 词对应的实体在知识普图中的上下文信息(所有与它相邻的实体的向量的均值)。将得到的多通道堆叠矩阵放入 CNN 中,最终得到新闻的 embedding 结果。
Attention-based用户兴趣抽取
用户对于自己点击过的每个新闻话题的兴趣并不是完全一样的,所以用户点击过的每个新闻对于用户是否点击候选推荐新闻的影响力也是不一样的,因此这里需要加入 Attention 机制。
输入:两条新闻标题(用户点击过的一条新闻和候选新闻)的 KCNN embedding 结果;输出:该条历史新闻对于候选新闻点击率的影响权重。
将两个 embedding 结果做全连接,然后使用一个 DNN(公式中用 H 表示)作为 Attention 网络,最后再用 softmax 函数来规格化影响权重,具体公式如下:
把这些历史新闻的向量和对应的权重,做加权平均,作为用户的 embedding 结果。
最后再将用户的 embedding 结果、候选推荐新闻的 embedded 结果做全连接,放到一个 DNN(公式中用 G 表示)中,得到最终的用户点击该条候选新闻的概率。
实验
数据来源:Bing News 的系统日志。
数据特征:实验中给出了新闻数据中新闻标题所含的词语数量平均值、新闻标题中包含的实体数量平均值、添加上下文实体后得到的实体数量平均值等,表明了加入知识图谱中的相邻实体确实能够丰富新闻的特征,具体如下表所示。
实验对比:
1. 文中把当前引入深度学习的协同过滤算法(DFM)和基于内容(KPCNN、DSSM、DeepWide、DeepFM、YouTubeNet)的个性化推荐算法都做了对比,实验表明 DKN 算法的推荐效果最好;
2. 对于 DKN 算法中,也做了使用不同知识表示学习算法、是否加入 Attention 机制、是否将 entity embedding 结果转换到 word embedding 结果的向量空间中、以及三种输入信息(Word embedding)、Entity embedding、上下文 embedding)组合都做了对比实验,实验表明使用三种输入信息、TransD 方法、非线性映射方法并加入 Attention 机制的效果最好。
总结
论文中所提出的模型主要部分还是使用了 CNN 和 Attention 这两个的组合,主要创新点还是在于首次将知识图谱引入到新闻推荐算法中,也就是利用知识图谱来提取更多的新闻特征应用推荐算法中。
COLING 2018
■ 论文 解读 | 谭亦鸣,东南大学博士生,研究方向为跨语言知识图谱问答
问题背景与动机
多关系问答(multi-relationquestion answering)是知识问答的一个重要任务,“多关系”指的是问题中包含多个关系和实体信息,为了回答这类问题,需要对知识库中多个事实三元组进行分析和推理。
现有的方法主要可以分为两类:基于语义分析和基于 embedding。 基于语义分析的方法主要依赖于人工特征与标注,但是泛化能力较弱。基于 embedding 的方法一般利用弱监督机制训练得到 end-to-end 问答模型,但是现有的方法主要依赖于相似度计算而在推理方面有所欠缺。
在这篇文章中, 作者提出可解释推理网络(Interpretable Reason Network,IRN)模型用于解决多关系问答。 通过多跳推理的形式完成多关系问题的问答过程。
贡献
本文亮点主要包括:
1. 提出面向多关系问答的 IRN 模型,并在性能上取得了 state-of-art;
2. 相对于现有推理网络,这篇文章提出的方法更具可解释性,多跳推理的过程可以清晰的反映答案生成的过程。
模型
IRN 的整体框架如图所示,其中包含三个子模型:Input Module,ReasoningModule,Answer Module,分别用于问句的 embedding,三元组推理以及答案的生成。
以问题 ‘How old is Obama’s daughter?’ 为例,问题的解析、推理和回答过程包含三跳(3 hops),每个 hop 包含的过程相同,描述如下:
1. Input Module :输入问题( 仅初始) ,得到问题的 embedding 形式 q;
2. Reasoning Module :输入 q ,以及对问题 NER 得到的实体信息 e 1 ,找到对应的关系 r 1 ;
3. Input Module :将已识别关系信息 r 1 从 q 中去除,得到更新的 q’ ,用于下一步推理;
4. Answer Module :根据已得到的 e 1 和 r 1 从知识库中找到对应的答案信息;
5. Reasoning Module :将已分析实体信息 e 1 与关系信息 r 1 融合,并用于下一步推理。
其中,获取关系 r 的计算过程如以下公式所示:
实验
本文实验所使用的数据基于 WorldCup2014,数据集的统计信息由表 1 所示。
实验结果
对比模型说明:
1. Embed (Bordes et al., 2014b):利用 embedding 空间将问题和答案进行匹配的方法;
2. Subgraph (Bordes et al., 2014a):在 Embed 基础上利用实体子图加强答案实体的表达;
3. Seq2Seq (Sutskever et al., 2014):使用基于 LSTM 的 encoder-decoder 实现的语义解析模型;
4. MemN2N (Sukhbaatar et al., 2015):使用记忆网络构建的 end2end 模型,其中记忆单元包含了相关的三元组信息;
5. KVMemN2N (Miller et al., 2016):在 MemN2N 的基础上,将记忆单元划分为键-值两个部分,键为头实体及关系,值为尾实体;
6. IRN-weak (This paper)
可解释性分析:
表 3 反映了 IRN 在多跳过程中识别关系和实体的精准度,r1/e1 -> rn/en -> a。
NeurIPS 2018
■ 论文 解读 | 吴杨,浙江大学计算机学院,研究方向为知识图谱、NLP
动机
在视觉问题回答中,较为复杂的问题经常需要多步骤的推理才能够回答,比如说 “What isplaced next to the bus on the right of the picture?” 这样的问题,我们需要先根据 (bus, on theright of, picture) 这组关系找到 bus on the right 这个复合物体,然后继续去寻找 next to [buson the right] 这个物体最终来解决这个问题。
而 本文则提出了一个 VQA 的推理链(Chain of Reasoning, CoR) ,能够充分利用图片和问句的信息对复杂问题中的关系和复合物体的寻找,并取得了非常好的效果。
本文的主要贡献在于:
-
提出了 VQA 推理链方法,能够动态的产生新的关系和复合物体以对问题进行推理;
-
在 4 种主要的数据集上都产生了 state-of-the-art 的效果;
-
对 CoR 的中间过程产生的复合物体进行了可视化。
方法
概述
VQA 的一种通用解法是将图片和问题映射到同一个向量空间后使用 element-wise 乘法或者 MLP 等等转化成分类问题。
本文的过程也是这样。图片经过 RCNN 转化为 m 个初始物体的向量表示之后,我们将这些物体两两组合起来,就可以获得 m*m 个关系的向量表示,然后利用问题的 embedding 从这 m*m 个关系向量中,产生出新一轮的 m 个复合物体,这样一直循环下去最终得到问题的答案表示的那个复合物体。
也就是说,本文和常规的想办法将问题解构成简单问题的思路不同,反而是将已有的可能是答案的物体进行组合,再用问题去挑选和进一步组合这些物体。
Data Embedding部分
将问题通过 GRU 转化成为维度的向量。将图片通过 RCNN 转化为 维度的向量,其中 V 中保存着 m 个初始物体的向量表示。
CoR 部分
第一步:产生 Attention 和本轮输出
将图片转成的向量 V 作为第一轮 CoR 的复合物体(橘黄色部分),将其向量映射到 Ds 维度,将问题向量映射到 Dp 维度,然后分别采用 2 个变换矩阵将他们映射到同一维度 Df,并使用 element-wise 乘法乘起来产生 m 维 Df 的向量(紫红色部分),上述过程重复 K 次,(Mutan 方法)对得到的紫红色向量加到一起,经过 MLP 最终产生 m 维的 attention(黑白灰 3 维部分)。
总的来说,本步骤的目的是计算问题对复合物体的 Attention。并准备产生 m*m 个关系 embedding。最后,用这个 Attention 对复合物体进行操作就可以产生本轮的输出了。其中各部分的公式表示如下:
其中,Pt,St 表示初步把问题和复合物体转化到的 embedding。Ft 表示将他们映射到同一维度并进行 element-wise 产生紫红色节点的部分。At 表示获得的 Attention,Ot 表示本轮的输出。
第二步:产生 m*m 个关系的 embedding
这一步中,我们首先将问题转化成为两个向量(黑白灰很长的向量),然后分别用该向量对 m 个复合物体进行 element-wise 相乘,并将第一个作为关系向量的 m*1 维行向量,第二个作为 1*m 维列向量,将这两个向量对应项相加合并成为 m*m 维向量作为关系向量(金黄色的部分)。涉及的公式如下:
其中 Gl 为第一个问题向量,Gr 为第二个问题向量,Rij 为最终的 m*m 维关系向量。
第三步:产生新的 m 个复合物体 embedding
利用第一步得到的 Attention,对产生的 m*m 维关系向量进行操作得到新的 m 个复合物体(这里论文原本打算直接保留 m*m 个向量送到下一轮,但是这样会导致复杂度成指数级上升)涉及到的公式为:
决策部分
对于 CoR 部分产生的 T 个输出向量 Ot,我们将之连接起来成为新的长向量,再将之和问题映射到同一维度,进行 Element-wise 乘法,最后经过矩阵变换+softmax 成为最终每个类别的概率。涉及的公式如下:
这里的 O* 表示长向量,H 表示 Element-Wise 得到的向量,a 表示最终的概率向量。
训练部分
训练的时候,主要是确定训练集的概率向量。如果对于一个 Q 对应一个 A 的训练集,显然我们取 A 那一维度的值为 1,其它都取 0 即可。但 VQA 数据集的答案是由多个人标记的。标记的结果可能不同。因此需要平均一下:
对于最终的 loss 我们用 K-L 散度计算:
实验
1. 在各数据集上取得的成果:
从上表中可以看出,在几乎所有的数据集上,模型都有提升,有些问题类型的提升不是很明显,但在 Color 和 Num 这两类问题的提升较大,有将近 6 个百分点。
2. 可视化
这一部分中,本文对 CoR 过程中产生的复合物体进行了可视化,可视化的方法是遍历 1105904×36 个方框,并对方框中图片的内容计算其与复合物体的相似度。其中红色方框和蓝色方框分别是 Attention 中权重最大的两个复合物体。
其中前三个问题都得到了很好的回答,而且复合物体寻找也是正确的,最后一个判断错误的原因可能是因为该问题太复杂,而 CoR 的跳数在本文中取了 3 跳。可能无法解决该问题。
总结
本文提出了 VQA 系统中利用推理链 CoR 解决多跳推理问题的方法,通过将图片中的物体进行多步的组合形成复杂的物体,并利用问题对这些物体进行选择和重新组合,最终取得答案需要的那些物体从而解决问题的方法。
点击以下标题查看更多相关文章:
# 投 稿 通 道 #
让你的论文被更多人看到
如何才能让更多的优质内容以更短路径到达读者群体,缩短读者寻找优质内容的成本呢? 答案就是:你不认识的人。
总有一些你不认识的人,知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁,促使不同背景、不同方向的学者和学术灵感相互碰撞,迸发出更多的可能性。
PaperWeekly 鼓励高校实验室或个人,在我们的平台上分享各类优质内容,可以是 最新论文解读 ,也可以是 学习心得 或 技术干货 。我们的目的只有一个,让知识真正流动起来。
:memo: 来稿标准:
• 稿件确系个人 原创作品 ,来稿需注明作者个人信息(姓名+学校/工作单位+学历/职位+研究方向)
• 如果文章并非首发,请在投稿时提醒并附上所有已发布链接
• PaperWeekly 默认每篇文章都是首发,均会添加“原创”标志
:mailbox_with_mail: 投稿邮箱:
• 投稿邮箱: hr@paperweekly.site
• 所有文章配图,请单独在附件中发送
• 请留下即时联系方式(微信或手机),以便我们在编辑发布时和作者沟通
:mag:
现在,在 「知乎」 也能找到我们了
进入知乎首页搜索 「PaperWeekly」
点击 「关注」 订阅我们的专栏吧
关于PaperWeekly
PaperWeekly 是一个推荐、解读、讨论、报道人工智能前沿论文成果的学术平台。如果你研究或从事 AI 领域,欢迎在公众号后台点击 「交流群」 ,小助手将把你带入 PaperWeekly 的交流群里。
▽ 点击 | 阅读原文 | 获取最新论文推荐
以上所述就是小编给大家介绍的《近期知识图谱顶会论文推荐,另附超详笔记解读》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 一朝爆发?解读知识图谱和图数据库的 2018
- 一个关于ollie的论文解读,论文目的在于知识图谱三元组提取
- 知识图谱发展的难点&构建行业知识图谱的重要性
- YOCSEF「知识图谱」专题探索班成功举办,五大高校、三大企业共话知识图谱理论与未来
- 新瓶装旧酒:为什么需要知识图谱?什么是知识图谱?——KG的前世今生
- 知识图谱:知识图谱赋能企业数字化转型 | AI 研习社职播间第 3 期
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
计算机动画的算法基础
鲍虎军 金小刚 彭群生 / 浙江大学出版社 / 2000-12 / 60.00元
《计算机应用技术前沿丛书:计算机动画的算法基础》主要内容简介:20世纪是一个科技、经济空前发展的时代,从世纪初相对论、量子理论的创立到今天以信息产业为龙头的高科技产业成为经济发展的第一支柱,人类社会发生了根本性的变革。而在这场以科学技术为社会发展直接动因的变革中,意义最深远、影响最广泛的就是计算机及其相关技术的发展和应用。在过去的50年里,计算机已从最初的协助人类进行精密和复杂运算的单一功能的运算......一起来看看 《计算机动画的算法基础》 这本书的介绍吧!