Developments of Knowledge Reasoning Based on Deep Reinforcement Learning

doi:10.3778/j.issn.1002-8331.2108-0052

Abstract

Abstract: Knowledge reasoning is an important method for the completion of knowledge graphs and has played an important role in many application fields such as vertical search and intelligent question answering. With the continuous in-depth research on the application of knowledge reasoning, the interpretability of knowledge reasoning has received extensive attention. The knowledge reasoning method based on deep reinforcement learning has better interpretability and stronger reasoning ability, which can make full use of the information of entities and relationships in the knowledge graph to make the reasoning effect better. The relevant concepts of knowledge graph and the basic research situation are introduced. The basic concepts of knowledge reasoning and the research progress in recent years are illuminated. Focusing on the closed domain reasoning and open domain reasoning, in-depth analysis and comparison of the current knowledge reasoning methods based on deep reinforcement learning are conducted. This paper also summarizes the data sets and evaluation methods involved. Finally, the future research directions are prospected.

Key words: knowledge graph, knowledge reasoning, deep reinforcement learning, link prediction, fact prediction

摘要： 知识推理是知识图谱补全的重要方法，已在垂直搜索、智能问答等多个应用领域发挥重要作用。随着知识推理应用研究的不断深入，知识推理的可解释性受到了广泛关注。基于深度强化学习的知识推理方法具备更好的可解释性和更强的推理能力，能够更加充分地利用知识图谱中实体、关系等信息，使得推理效果更好。简要介绍知识图谱及其研究的基本情况，阐述知识推理的基本概念和近年来的研究进展，着重从封闭域推理和开放域推理两个角度，对当下基于深度强化学习知识推理方法进行了深入分析和对比，同时对所涉及到的数据集和评价指标进行了总结，并对未来研究方向进行了展望。

关键词: 知识图谱, 知识推理, 深度强化学习, 链接预测, 事实预测

SONG Haonan, ZHAO Gang, SUN Ruoying. Developments of Knowledge Reasoning Based on Deep Reinforcement Learning[J]. Computer Engineering and Applications, 2022, 58(1): 12-25.

宋浩楠, 赵刚, 孙若莹. 基于深度强化学习的知识推理研究进展综述[J]. 计算机工程与应用, 2022, 58(1): 12-25.

References

[1] BERNERS L T，HENDLER J，LASSILA O.The semantic web[J].Scientific American，2001，284（5）：34-43.
[2] SHADBOLT N，BERNERS L T，HALL W.The semantic web revisited[J].IEEE Intelligent Systems，2006，21（3）：96-101.
[3] SINGHAL A.Introducing the knowledge graph：Things，not strings[EB/OL].（2012）[2021-07-01].https：//blog.csdn.net/eli00001/article/details/64905724.
[4] BOLLACKER K，EVANS C，PARITOSH P，et al.Freebase：A collaboratively created graph database for structuring human knowledge[C]//Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data，2008：1247-1250.
[5] AUER S，BIZER C，KOBILAROV G，et al.DBpedia：A nucleus for a web of open data[M]//The semantic Web.Berlin Heidelberg：Springer，2007：722-735.
[6] CARLSON A，BETTERIDGE J，KISIEL B，et al.Toward an architecture for never-ending language learning[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence，2010：1306-1313.
[7] Sohu encyclopedia[EB/OL].（2015）[2021-07-01].http：//baike.sogou.com/h66616234.htm.
[8] Baidu encyclopedia[EB/OL].（2015）[2021-07-01].http：//baike.baidu.com/view/10972128.htm.
[9] WEST R，GABRILOVICH E，MURPHY K，et al.Knowledge base completion via search-based question answering[C]//Proceedings of the 23rd International Conference on World Wide Web，2014：515-526.
[10] 刘峤，李杨，段宏，等.知识图谱构建技术综述[J].计算机研究与发展，2016，53（3）：582-600.
LIU Q，LI Y，DUAN H，et al.Knowledge graph construction techniques[J].Journal of Computer Research and Development，2016，53（3）：582-600.
[11] JI S X，PAN S R，CAMBRIA E，et al.A survey on knowledge graphs：Representation，acquisition and applications[J].arXiv：2002.00388，2020.
[12] 刘知远，孙茂松，林衍凯，等.知识表示学习研究进展[J].计算机研究与发展，2016，53（2）：247-261.
LIU Z Y，SUN M S，LIN Y K，et al.Knowledge representation learning：A review[J].Journal of Computer Reseach and Development，2016，53（2）：247-261.
[13] WANG Q，MAO Z，WANG B，et al.Knowledge graph embedding：A survey of approaches and applications[J].IEEE Transactions on Knowledge and Data Engineering，2017，29（12）：2724-2743.
[14] 官赛萍，靳小龙，贾岩涛，等.面向知识图谱的知识推理研究进展[J].软件学报，2018，29（10）：2966-2994.
GUAN S P，JIN X L，JIA Y T，et al.Knowledge reasoning over knowledge graph：A survey[J].Journal of Software，2018，29（10）：2966-2994.
[15] 张仲伟，曹雷，陈希亮，等.基于神经网络的知识推理研究综述[J].计算机工程与应用，2019，55（12）：8-19.
ZHANG Z W，CAO L，CHEN X L，et al.Survey of knowledge reasoning based on neural network[J].Computer Engineering and Applications，2019，55（12）：8-19.
[16] LI W，QI G，JI Q.Hybrid reasoning in knowledge graphs：Combing symbolic reasoning and statistical reasoning[J].Semantic Web，2020，11（1）：53-62.
[17] 王永庆.人工智能原理与方法[M].西安：西安交通大学出版社，1998.
WANG Y Q.Principles and methods of artificial intelligence[M].Xi’an：Xi’an Jiaotong University Press，1998.
[18] KOMPRIDIS N.So we need something else for reason to mean[J].International Journal of Philosophical Studies，2000，8（3）：271-295.
[19] TARI L.Knowledge inference[M].New York：Springer-Verlag，2013：1074-1078.
[20] 吴运兵，杨帆，赖国华，等.知识图谱学习和推理研究进展[J].小型微型计算机系统，2016，37（9）：2007-2013.
WU Y B，YANG F，LAI G H，et.al.Research progress of knowledge graph learning and reasoning[J].Journal of Chinese Computer Systems，2016，37（9）：2007-2013.
[21] 徐增林，盛泳潘，贺丽荣，等.知识图谱技术综述[J].电子科技大学学报，2016，45（4）：589-606.
XU Z L，SHENG Y P，HE L R，et al.Review on knowledge graph techniques[J].Journal of University of Electronic Science and Technology of China，2016，45（4）：589-606.
[22] 漆桂林，高桓，吴天星.知识图谱研究进展[J].情报工程，2017，3（1）：4-25.
QI G L，GAO H，WU T X.The research advances of knowledge graph[J].Technology Intelligence Engineering，2017，3（1）：4-25.
[23] WANG W Y，MAZAITIS K，COHEN W W.Programming with personalized pagerank：A locally groundable first-order probabilistic logic[C]//Proceedings of the 22nd ACM International Conference on Information & Knowledge Management，2013：2129-2138.
[24] WANG W Y，MAZAITIS K，LAO N，et al.Efficient inference and learning in a large knowledge base[J].Machine Learning，2015，100（1）：101-126.
[25] COHEN W W.Tensorlog：A differentiable deductive database[J].arXiv：1605.06523，2016.
[26] JANG S M，CHOI J Y，YI MY，et al.Semi-automatic quality assessment of linked data without requiring ontology[C]//Proceedings of the International Semantic Web Conference（ISWC） NLPDBpedia，2015.
[27] CHEN Y，GOLDBERG S，WANG D Z，et al.Ontological pathfinding[C]//Proceedings of the 2016 International Conference on Management of Data，2016：835-846.
[28] LEE T W，LEWICKI M S，GIROLAMI M，et al.Blind source separation of more sources than mixtures using overcomplete representations[J].IEEE Signal Processing Letters，1999，6（4）：87-90.
[29] DICKINSON I.Implementation experience with the dig 1.1 specification[EB/OL].（2004）[2021-07-01].http：//www.hpl.hp.com/semweb/publications.html.
[30] 龚资.基于OWL描述的本体推理研究[D].长春：吉林大学，2007.
GONG Z.Research on ontology reasoning based on OWL[D].Changchun：Jilin University，2007.
[31] LU S Y，HSU K H，KUO L J.A semantic service match approach based on wordnet and SWRL rules[C]//Proceedings of 2013 IEEE 10th International Conference on e-Business Engineering，2013：419-422.
[32] BORDES A，USUNINER N，GARCIA D A，et al.Translating embeddings for modeling multi-relational data[C]//Advances in Neural Information Processing Systems，2013：2787-2795.
[33] WANG Z，ZHANG J，FENG J，et al.Knowledge graph embedding by translating on hyperplanes[C]//Proceedings of the 28th Conference on Artificial Intelligence，2014：1112-1119.
[34] LIN Y，LIU Z，SUN M，et al.Learning entity and relation embeddings for knowledge graph completion[C]//Proceedings of the 29th Conference on Artificial Intelligence，2015：2181-2187.
[35] JI G，HE S，XU L，et al.Knowledge graph embedding via dynamic mapping matrix[C]//Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing，2015：687-696.
[36] EBISU T，ICHISE R.Toruse：Knowledge graph embedding on a lie group[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence，2018：1819-1826.
[37] SUN Z，DENG Z H，NIE J Y，et al.Rotate：Knowledge graph embedding by relational rotation in complex space[C]//Proceedings of the 7th International Conference on Learning Representations，2019：1-18.
[38] ZHANG S，TAY Y，YAO L，et al.Quaternion knowledge graph embeddings[C]//Proceedings of the 33rd Conference on Neural Information Processing Systems，2019：2731-2741.
[39] LIN Y，LIU Z，LUAN H，et al.Modeling relation paths for representation learning of knowledge bases[C]//Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing，2015：705-714.
[40] 陈海旭，周强，刘学军.一种结合路径信息和嵌入模型的知识推理方法[J].小型微型计算机系统，2020，41（6）：1147-1151.
CHEN H X，ZHOU Q，LIU X J.Knowledge graph reasoning combining path information and embedding model[J].Journal of Chinese Computer Systems，2020，41（6）：1147-1151.
[41] JIA Y，WANG Y，JIN X，et al.Path-specific knowledge graph embedding[J].Knowledge-Based Systems，2018，151：37-44.
[42] BING W Y，HONG Z D，WEN L X，et al.Knowledge graph reasoning based on paths of tensor factorization[J].Pattern Recognition and Artificial Intelligence，2017，30（5）：473-480.
[43] LAO N，COHEN W W.Relational retrieval using a combination of path-constrained random walks[J].Machine Learning，2010，81（1）：53-67.
[44] LAO N，MITCHELL T，COHEN W W.Random walk inference and learning in a large scale knowledge base[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing，Association for Computational Linguistics，2011：529-539.
[45] GARDNER M，MITCHELL T.Efficient and expressive knowledge base completion using subgraph feature extraction[C]//Proceedings of the Conference on Empirical Methods in Natural Language Processing，2015：1488-1498.
[46] GARDNER M，TALUKDAR P，KRISHNAMURTHY J，et al.Incorporating vector space similarity in random walk inference over knowledge bases[C]//Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing，2014：397-406.
[47] DAS R，NEELAKANTAN A，BELANGER D，et al.Chains of reasoning over entities，relations，and text using recurrent neural networks[C]//Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics，2017：132-141.
[48] CHEN W，XIONG W，YAN X，et al.Variational knowledge graph reasoning[J].arXiv：1803.06581，2018.
[49] TOUTANOVA K，CHEN D，PANTEL P，et al.Representing text for joint embedding of text and knowledge bases[C]//Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing，2015：1499-1509.
[50] XIE R，LIU Z，JIA J，et al.Representation learning of knowledge graphs with entity descriptions[C]//Proceedings of the 30th AAAI Conference on Artificial Intelligence，2016：2659-2665.
[51] SCHLICHTKRULL M，KIPF T N，BLOEM P，et al.Modeling relational data with graph convolutional networks[C]//Proceedings of the European Semantic Web Conference，2018：593-607.
[52] YANG B，YIH W，HE X，et al.Embedding entities and relations for learning and inference in knowledge bases[J].arXiv：1412.6575，2014.
[53] GRAVES A，WAYNE G，REYNOLDS M，et al.Hybrid computing using a neural network with dynamic external memory[J].Nature，2016，538：471-476.
[54] SHEN Y，HUANG P S，CHANG M W，et al.Modeling large-scale structured relationships with shared memory for knowledge base completion[C]//Proceedings of the 2nd Workshop on Representation Learning for NLP，2017：57-68.
[55] XIONG W，HOANG T，WANG W Y.Deeppath：A reinforcement learning method for knowledge graph reasoning[J].arXiv：1707.06690，2017.
[56] WILLIAMS R J.Simple statistical gradient-following algorithms for connectionist reinforcement learning[J].Machine Learning，1992，8（3）：229-256.
[57] DAS R，DHULIAWALA S，ZAHEER M，et al.Go for a walk and arrive at the answer：Reasoning over paths in knowledge bases using reinforcement learning[J].arXiv：1711.05851，2017.
[58] HOCHREITER S，SCHMIDHUBER J.Long short-term memory[J].Neural Computation，1997，9（8）：1735-1780.
[59] LIN X V，SOCHER R，XIONG C.Multi-hop knowledge graph reasoning with reward shaping[J].arXiv：1808. 10568，2018.
[60] DETTMERS T，MINERVINI P，STENETORRP P，et al.Convolutional 2D knowledge graph embeddings[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence，2018：1811-1818.
[61] HO J，ERMON S.Generative adversarial imitation lear-ning[C]//Advances in Neural Information Processing Systems，2016：4565-4573.
[62] LI R，CHENG X.DIVINE：A generative adversarial imitation learning framework for knowledge graph reasoning[C]//Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing，2019：2642-2651.
[63] WANG H，LI S，PAN R，et al.Incorporating graph attention mechanism into knowledge graph reasoning based on deep reinforcement learning[C]//Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing，2019：2623-2631.
[64] FU C，CHEN T，QU M，et al.Collaborative policy learning for open knowledge graph reasoning[C]//Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing，2019：2672-2681.
[65] TOUTANOVA K，CHEN D，PANTEL P，et al.Representing text for joint embedding of text and knowledge bases[C]//Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing，2015：1499-1509.
[66] TROUILLON T，WELBL J，RIEDEL S，et al.Complex embeddings for simple link prediction[C]//Proceedings of the International Conference on Machine Learning，2016：2071-2080.
[67] YANG B，YIH W，HE X，et al.Embedding entities and relations for learning and inference in knowledge bases[J].arXiv：1412.6575，2014.
[68] ROCKTASCHEL T，RIEDEL S.End-to-end differentiable proving[J].arXiv：1705.11040，2017.
[69] YANG F，YANG Z，COHEN W W.Differentiable learning of logical rules for knowledge base completion[J].arXiv：1702.08367，2017.
[70] KOK S，DOMINGOS P.Statistical predicate invention[C]//Proceedings of the 24th International Conference on Machine Learning，2007：433-440.
[71] XU C，BAI Y，BIAN J，et al.RC-NET：A general framework for incorporating knowledge into word representations[C]//Proceedings of the 23rd ACM International Conference on Information and Knowledge Management，2014：1219-1228.
[72] HAN X，LIU Z，SUN M.Neural knowledge acquisition via mutual attention between knowledge graph and text[C]//Proceedings of the 32nd AAAI Conference on Artificial Intelligence，2018：4832-4839.