Knowledge graphs (KG) are multi-relational, graphstructured databases which store facts about the real world. Thereby, entities correspond to vertices and binary relations to edge types that specify how the entities are related to each other. KGs are useful resources for various artificial intelligence (AI) tasks in different fields such as named entity disambiguation in NLP (Han and Zhao 2010) or visual relation detection in computer vision (Baier, Ma, and Tresp 2017). Examples of large sized KGs include Freebase (Bollacker et al. 2008), YAGO (Suchanek, Kasneci, and Weikum 2007), and WordNet (Miller 1995). In particular, the Google Knowledge Graph (Singhal 2012) is a well-known example of a commercial KG with more than 18 billion facts, used by the search engine to enhance results. One major issue, however, is that most real-world KGs are incomplete (i.e., true facts are missing) or contain false facts. Machine learning algorithms designed to solve this problem try to infer missing triples or detect false facts based on observed connectivity patterns.
Most machine learning approaches for reasoning on KGs embed both entities and predicates into low dimensional vector spaces. Then a score for the plausibility of a triple can be computed based on these embeddings. Common to most of these methods is their black-box nature because what contributed to this score is hidden from the user. This lack of transparency constitutes a potential limitation when it comes to deploying KGs in real world settings. Explainability as a development focus for new machine learning models has gained attention in the last few years (see (Ribeiro, Singh, and Guestrin 2016), (Mahendran and Vedaldi 2015), or (Montavon et al. 2017)) as the success of machine learning and AI continues, while the ability to understand and interpret the increasingly complex and powerful methods staggers behind. Laws that require explainable algorithms and models have been considered and implemented (Goodman and Flaxman 2017). Additionally, in contrast to one-way black-box con-figurations, comprehensible machine learning methods allow to build systems where both machines and users interact and influence each other.
In this work we describe a novel method for triple clas-sification based on reinforcement learning. Inspired by the concept outlined in (Irving, Christiano, and Amodei 2018) to increase AI safety via debates, we model the task of triple classification as a debate between two agents each presenting arguments for the thesis (the triple is true) and the antithesis (the triple is false), respectively. Based on these arguments, a binary classifier, referred to as the judge, decides whether the fact is true or false. In that sense the two agents act as feature extractors that present evidence for and against the validity of the fact. In contrast to most methods based on representation learning, the arguments can be displayed to the user such that he can audit the classification of the judge and potentially overrule the decision. Further, our method can be used to create tools for knowledge graph curation or question answering where the users can interact with the system by inputting additional arguments or make a decision based on the agents’ arguments. Moreover, mining evidence for both the thesis and the antithesis can be considered as adversarial feature generation, making the classifier more robust towards contradictory evidence or corrupted data. To the best of our knowledge, our method constitutes the first model based on
Figure 1: The agents debate whether Michael Jordan is a professional basketball player. While agent 1 extracts arguments from the KG promoting that the fact is true (green), agent 2 argues that it is false (red). Based on the arguments the judge decides that Michael Jordan is a professional basketball player.
debate dynamics for triple classification in KGs.
In this section we provide a brief introduction to KGs in a formal setting and review the most relevant related work. Let E denote the set of entities and consider the set of binary relations R. A knowledge graph is a collection of facts stored as triples of the form (s, p, o) – subject, predicate, and object. To indicate whether a triple is true or false, we consider the binary characteristic function . For all we assume (i.e., a KG is a collection of true facts). However, in case a triple is not contained in KG, it does not imply that the corresponding fact is false but rather unknown (open world assumption). Triple classification (or fact-checking) is concerned with predicting the truth value
Representation learning is an effective and popular technique underlying many KG reasoning methods. The basic idea is to project both entities and relations into a low dimensional vector space. Then the likelihood of triples is modelled in terms of a functional on the embedding spaces. Popular methods based on representation learning include the translational embedding method TransE (Bordes et al. 2013), factorization approaches such ComplEx (Trouillon et al. 2016), or deep neural network methods including ConvE (Dettmers et al. 2018). While these methods efficiently encode the local neighborhood of entities, they cannot reason through more complex inference paths in KGs. Therefore, path-based reasoning methods have been studied. For instance, the PathRanking Algorithm (PRA) proposed in (Lao, Mitchell, and Cohen 2011) uses a combination of weighted random walks through the graph for inference. (Xiong, Hoang, and Wang 2017) proposed the reinforcement learning based path searching approach called DeepPath, where an agents picks relational paths between entity pairs. Recently, and more related to our work, (Das et al. 2018) proposed the multi-hop reasoning method MINERVA. The basic idea is to display the query subject and predicate to the agent and let the agent perform a policy guided walk to the correct object entity. The paths that MINERVA produces also lead to some degree of explainability. However, we find that only actively mining arguments for the thesis and the antithesis, thus exposing the user to both sides of a debate, allows to make a well-informed decision.
Our method is inspired on the concept outlined in (Irving, Christiano, and Amodei 2018) where the authors propose the use of debate dynamics for the AI alignment task. Their concept is based on training agents to play a zero sum debate game where they raise arguments which are evaluated by a judge. More concretely, given a question or a proposed action, two or multiple agents take turns making short statements until a human can decide which of the agents gave the more convincing information. While a major part of their work consists of theoretical considerations, they also conduct an initial experiment on MNIST with an automated judge: First, an image is shown to two agents and each of them selects a digit. Then, the two agents sequentially select pixels of the image with the goal to convince a sparse classifier that the pixels stem from an image that displays the digits to which they are committed. Thereby, the classifier cannot observe the complete image but only the pixels revealed by the agents. The authors state that their eventual goal is to produce natural language debates, where humans judge dialogues between the agents. In that regard, our method can be seen as a first step in that direction since paths in a knowledge graph correspond to factual statements that can be easily translated to natural language.
We formulate the task of fact prediction in terms of a debate between two opposing agents. Thereby, a query triple corresponds to the statement around which the debate is centered. The agents mine paths on the KG that serve as evidence for the thesis or the antithesis. More concretely, they traverse the graph sequentially and select the next hop based on a policy that takes previous transitions and the query triple into account. The transitions are added to the current path extending the argument. All paths are processed by a binary classifier called the judge that tries to distinguish between true and false triples. An exemplary debate is shown in Figure 1. The main steps of a debate can be summarized as follows:
1. A query triple around which the debate is centered is pre-
Figure 2: Sketch of the architecture of our method: The two agents extract arguments from the KG. Along with the query relation and the query object, these arguments are processed by the judge who classifies whether the query is true or false.
sented to both agents
2. The two agents take turns extracting paths from the KG that serve as arguments for the thesis and the antithesis.
3. The judge processes the arguments along with the query triple and estimates the truth value of the query triple.
While the parameters of the judge are fitted in a supervised fashion, both agents are trained to navigate through the graph using reinforcement learning. More concretely, their environments are modelled via the fixed horizon, deterministic Markov decision processes outlined below.
States The fully observable state space S for each agent is given by . Intuitively, we want the state to encode the query triple and the location of exploration (i.e., the current location) of agent at time t. Thus, a state is represented by
Actions The set of possible actions for agent i from a state is denoted by . It consists of all outgoing edges from the entity and the corresponding target entities. More formally,
Moreover, we denote with the action that agent i performed at time t. We include self-loops for each node such that the agent can stay at the current node.
Environments The environments evolve deterministically by updating the state according to the agents’ actions (i.e., by changing the agents’ locations). The query fact remains the same. Formally, the transition function of agent i at time t is given by
and A
Policies We denote the history of agent i up to time t with the tuple for and . The agents encode their histories via recurrent neural networks. The output is mapped to a distribution over all admissible actions (i.e., transitions). This induces agent spe-cific policies , where and denotes the set of all trainable parame- ters. Then, the next action of agent i is sampled according to Categorical
Debate Dynamics In a first step, the query triple q with truth value is presented to both agents. Agent 1 argues that the fact is true, while agent 2 argues that it is false. Similar to most formal debates, we consider a fixed number of rounds . In every round n = 1, 2, . . . , N the agents start graph traversals with fixed length the subject entity of the query . More concretely, agent 1 starts generating a sequence consisting of entities and relations followed by a mandatory end of argument action. Then agent 2 proceeds by producing a similar sequence starting from ending with the stop action. After N rounds the debate terminates and concatenating all paths leads to the overall sequence of arguments . The judge processes and predicts the truth value of the triple. This induces a binary classifier . The parameters of the judge are trained in a supervised fashion to approximate the underlying truth value of the triple . An overview of the architecture of our method is depicted in Figure 2.
Since agent 1 argues that the thesis is true, the rewards after every round are given by the classification score . Similarly, the rewards of agent 2 are given
by . Intuitively, this means that the agents receive high rewards whenever they extract an argument that is considered by judge as strong evidence for their position. To find the best set of parameters the agents maximize the expected cumulative rewards where standard methods such as REINFORCE (Williams 1992) can be employed.
Table 1: Two examples of debates generated by our method: While agent 1 argues that the query triple is true and agent 2 argues that it is false. The underscore indicates inverse relations.
In this section we present the results of a preliminary experiment and discuss applications and directions of future works. We implemented our method as outlined in Section 3 where the policies of the agents consists of LSTM cells with a dense neural network stacked on top. The judge processes each argument individually by a feed forward neural network, sums the output for each argument up and processes the resulting sum by a linear, binary classifier. Both agents and the judge have separate lookup tables that contain embeddings for the relations and entities. We run this first experiment on the benchmark dataset FB15k-237 (Toutanova et al. 2015) which contains around 15,000 different entities mainly focused around culture, sports, and politics. Following (Socher et al. 2013) we select the following relations for training and testing purposes: ’gender’, ’profession’, ’nationality’, ’ethnicity’, and ’religion’. Thereby we found that 82.4% of the query triples in the balanced test set (i.e., equally many true and false facts) were classified correctly by the judge. While these results are promising for a first experiment, we leave the majority of the empirical work including experimenting with different architectures to future research.
By manually examining the quality of the extracted paths we found mostly reasonable arguments (e.g. when arguing that a person has a certain nationality, the agents frequently bring up that the fact the person is born in a city in this country). However, there were also some arguments that do not make intuitive sense. We conjecture that this is partially due to the fact that the embeddings of entities encode their neighborhoods. While the judge has access to this information through the training process, it remains hidden to the user. For example, when arguing for the fact that Nelson Mandela was an actor (see Table 1) the argument of agent 1 requires the user to know that both Naomi Campbell as well as Leonardo DiCaprio are actors (which is encoded in FB15k-237). Then this argument serves as evidence that Nelson Mandela was also an actor since people tend to have friends that share their profession (social homophily). However, without this context information it is not intuitively clear why this is a reasonable argument. To asses whether the arguments are informative for users in an objective setting we plan to conduct a survey where respondents take the role of the judge making a classification decision based on the agents’ arguments.
Many KGs, including DBpedia, Freebase, and Wikidata, are (among other techniques) semiautomatically built and maintained with the assistance of manual efforts to ensure that the knowledge keeps expanding and is kept up-to-date and accurate (Ge et al. 2016). While manually validating triples is laborious, most machine learning methods for this task are based on a numerical confidence score which is hard to interpret. Our method can be employed for interactive KG curation and fact checking. More concretely, if there are doubts concerning the truthfulness of a triple, the user can examine the arguments to make an informed decision or input arguments that the agents might have missed. Suppose, for example, the triple (BarackObama, nationality, USA) is classified as false and the user observes that one agent brought up the argument that Barack Obama was born in Kenya – a fact most likely mined from an unreliable source from the web. The user can then enter the correct fact that Obama is born in Hawaii which results in the correct classification. On a related note, (Nickel et al. 2015) raise the point that when applying statistical methods to incomplete KGs the results are likely to be affected by biases in the data generating process and should be interpreted accordingly. Otherwise, blindly following recommendations from KG reasoning methods can even strengthen these biases. While the judge in our method also exploits skews in the underlying data, the arguments of the agents can help to identify these biases and potentially exclude problematic arguments from the classification decision. Moreover, our method can be integrated into QA systems. Instead of simply providing an answer to a question, the system could then also display evidence for and against this answer allowing the user to trace back the decision. This added transparency can potentially increasing user acceptance.
We have described a novel approach for triple classification in KGs based on a debate game between two opposing reinforcement learning agents that argue whether a fact is true or false. The two agents search the KG for arguments that shift the judge, a binary classifier, towards their position. Since the judge bases its decision on the extracted arguments, the user can examine the arguments and trace back the classification decision. This also allows for building tools where the user interacts with the system leading to higher acceptance of KG reasoning tools. While the first experiments that we conduct in the scope of this work are promising, significant further research, including experiments with different architectures for the agents and the judge, is required. Another directions for future work is a systematic, qualitative analysis of the arguments.
Baier, S.; Ma, Y.; and Tresp, V. 2017. Improving visual relationship detection using semantic modeling of scene descriptions. In International Semantic Web Conference, 53–68. Springer.
Bollacker, K.; Evans, C.; Paritosh, P.; Sturge, T.; and Taylor, J. 2008. Freebase: a collaboratively created graph database for structuring human knowledge. In Proceedings of the 2008 ACM SIGMOD international conference on Management of data, 1247–1250. AcM.
Bordes, A.; Usunier, N.; Garcia-Duran, A.; Weston, J.; and Yakhnenko, O. 2013. Translating embeddings for modeling multi-relational data. In Advances in neural information processing systems, 2787–2795.
Das, R.; Dhuliawala, S.; Zaheer, M.; Vilnis, L.; Durugkar, I.; Krishnamurthy, A.; Smola, A.; and McCallum, A. 2018. Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning. In ICLR.
Dettmers, T.; Minervini, P.; Stenetorp, P.; and Riedel, S. 2018. Convolutional 2d knowledge graph embeddings. In Thirty-Second AAAI Conference on Artificial Intelligence.
Ge, T.; Wang, Y.; de Melo, G.; Li, H.; and Chen, B. 2016. Visualizing and curating knowledge graphs over time and space. Proceedings of ACL-2016 System Demonstrations 25–30.
Goodman, B., and Flaxman, S. 2017. European union regulations on algorithmic decision-making and a “right to explanation”. AI Magazine 38(3):50–57.
Han, X., and Zhao, J. 2010. Structural semantic relatedness: a knowledge-based method to named entity disambiguation. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, 50–59. Association for Computational Linguistics.
Irving, G.; Christiano, P.; and Amodei, D. 2018. Ai safety via debate. arXiv preprint arXiv:1805.00899.
Lao, N.; Mitchell, T.; and Cohen, W. W. 2011. Random walk inference and learning in a large scale knowledge base. In Proceedings of the Conference on Empirical Methods in Natural Language Processing, 529–539. Association for Computational Linguistics.
Mahendran, A., and Vedaldi, A. 2015. Understanding deep image representations by inverting them. In Proceedings of the IEEE conference on computer vision and pattern recognition, 5188–5196.
Miller, G. A. 1995. Wordnet: a lexical database for english. Communications of the ACM 38(11):39–41.
Montavon, G.; Lapuschkin, S.; Binder, A.; Samek, W.; and Müller, K.-R. 2017. Explaining nonlinear classification decisions with deep taylor decomposition. Pattern Recognition 65:211–222.
Nickel, M.; Murphy, K.; Tresp, V.; and Gabrilovich, E. 2015. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE 104(1):11–33.
Ribeiro, M. T.; Singh, S.; and Guestrin, C. 2016. Why should i trust you?: Explaining the predictions of any classifier.
In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, 1135– 1144. ACM.
Singhal, A. 2012. Introducing the knowledge graph: things, not strings. [Online; accessed 28-March-2019].
Socher, R.; Chen, D.; Manning, C. D.; and Ng, A. 2013. Reasoning with neural tensor networks for knowledge base completion. In Advances in neural information processing systems, 926–934.
Suchanek, F. M.; Kasneci, G.; and Weikum, G. 2007. Yago: a core of semantic knowledge. In Proceedings of the 16th international conference on World Wide Web, 697–706. ACM.
Toutanova, K.; Chen, D.; Pantel, P.; Poon, H.; Choudhury, P.; and Gamon, M. 2015. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, 1499–1509.
Trouillon, T.; Welbl, J.; Riedel, S.; Gaussier, E.; and Bouchard, G. 2016. Complex embeddings for simple link prediction. In International Conference on Machine Learning (ICML), volume 48, 2071–2080.
Williams, R. J. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning 8(3-4):229–256.
Xiong, W.; Hoang, T.; and Wang, W. Y. 2017. Deeppath: A reinforcement learning method for knowledge graph reasoning. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing (EMNLP 2017). Copenhagen, Denmark: ACL.