Bayesian Abductive Logic Programs: A Probabilistic Logic for Abductive Reasoning
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2840-2840.
https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-492
© 2011 International Joint Conferences on Artificial Intelligence
Abstract
In this proposal, we introduce Bayesian Abductive Logic Programs (BALP), a probabilistic logic that adapts Bayesian Logic Programs (BLPs) for abductive reasoning. Like BLPs, BALPs also combine first-order logic and Bayes nets. However, unlike BLPs, which use deduction to construct Bayes nets, BALPs employ logical abduction. As a result, BALPs are more suited for problems like plan/activity recognition that require abductive reasoning. In order to demonstrate the efficacy of BALPs, we apply it to two abductive reasoning tasks — plan recognition and natural language understanding.
- [Getoor and Taskar, 2007] L. Getoor and B. Taskar, editors. Intro- duction to Statistical Relational Learning. MITP, Cambridge, MA, 2007.
- [Gogate and Dechter, 2007] Vibhav Gogate and Rina Dechter. Samplesearch: A scheme that searches for consistent samples. In AISTATS-07, 2007.
- [Kakas et al., 1993] Andonakis C. Kakas, Robert A. Kowalski, and Francesca Toni. Abductive logic programming. Journal of Logic and Computation, 2(6):719-770, 1993.
- [Kate and Mooney, 2009] R. J. Kate and R. J. Mooney. Probabilis- tic abduction using Markov logic networks. In IJCAI-09 Work- shop on Plan, Activity, and Intent Recognition, Pasadena, CA, July 2009.
- [Kersting and De Raedt, 2001] Kristian Kersting and Luc De Raedt. Towards combining inductive logic programming with Bayesian networks. In ILP-01, pages 118-131, Strasbourg, France, September 2001.
- [Kersting and Raedt, 2008] Kristian Kersting and Luc De Raedt. Basic principles of learning Bayesian logic programs. In Proba- bilistic Inductive Logic Programming, pages 189-221, 2008.
- [Levesque, 1989] Hector J. Levesque. A knowledge-level account of abduction. In IJCAI-89, pages 1061-1067, Detroit, MI, Aug 1989. IJCAI
- [Pearl, 1988] Judea Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. MKP, CA, 1988.
- [Peirce, 1958] Charles Sanders Peirce. Collected Papers of Charles Sanders Peirce. MITP, Cambridge, Mass., 1958.
- [Pople, 1973] Harry E. Pople. On the mechanization of abductive logic. In IJCAI-73, pages 147-152, 1973. IJCAI
- [Richardson and Domingos, 2006] Matthew Richardson and Pedro Domingos. Markov logic networks. Machine Learning, 62:107- 136, 2006.
- [Stickel, 1988] M. E. Stickel. A Prolog-like inference system for computing minimum-cost abductive explanations in natural- language interpretation. Technical Report Tech. Note 451, SRI International, CA, Sep 1988.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Abduction, also called abductive reasoning is defined as the process of finding the best explanation for a set of observations [Peirce, 1958]. It is widely used in tasks such as activity recognition, plan recognition, and diagnosis, that require inferring cause from effect. For example, in plan recognition, given a set of actions performed by an intelligent agent, abductive reasoning is used to identify the high level plan or goal of the agent. Similarly, in medical diagnosis, given a set of symptoms observed in a patient, abductive reasoning is used to diagnose the disease that caused the symptoms. Several other tasks like natural language understanding, image interpretation, etc. could be solved using abductive reasoning. Abductive reasoning is hypothetical in nature, i.e one could only hypothesize the cause for the observed effects. Further, there could be several possible explanations for the same set of observations. As a result, it is considered to be a weak kind of inference [Kakas et al., 1993].
Most previous approaches to abductive reasoning have been based on first-order logic and determine a small set of assumptions sufficient to deduce the observations [Pople, 1973; Levesque, 1989; Kakas et al., 1993]. While these logicbased approaches handle structured representations, they are unable to handle uncertainty in the observations or background knowledge and are incapable of estimating the likelihood of alternative explanations. Another popular approach to abduction involves using Bayes nets to compute the posterior probability of alternative explanations given the observations [Pearl, 1988]. A major limitation of this approach is that it cannot handle structured representations involving relations amongst multiple entities since Bayes nets are essentially propositional in nature.
Recently, a number of formalisms that integrate first-order logic and probabilistic graphical models have been developed in the area of statistical relational learning (SRL) [Getoor and Taskar, 2007]. Of these formalisms, Markov Logic Networks (MLNs) [Richardson and Domingos, 2006], which combine first-order logic and undirected graphical models (Markov nets) have been used for abductive plan recognition by Kate and Mooney [2009]. Since MLNs employ deduction for logical inference, they adapt MLNs for abduction by adding reverse implications for every rule in the knowledge base. However, the addition of these rules increases the size and complexity of the MLN, resulting in a computationally expensive model. Like MLNs, most SRL formalisms use deduction for logical inference, and hence cannot be used effectively for abductive reasoning. As a result, my research is focussed on the development of a SRL formalism that can perform abductive reasoning efficiently.
2 Proposal
In this proposal, we propose Bayesian Abductive Logic Programs (BALP), a new formalism that adapts Bayesian Logic Programs (BLPs) [Kersting and De Raedt, 2001] for abductive reasoning. Like most SRL formalisms, BLPs also use deduction for logical inference, and hence cannot be used effectively for abductive reasoning. As a result, we enhance BLPs to support abductive reasoning by employing logical abduction instead of deduction. Like BLPs, BALPs combine first-order logic and directed graphical models (Bayes nets). Like all SRL formalisms, BALPs also integrate the strengths of both first-order logic and probabilistic graphical models, thus overcoming the limitations of the approaches mentioned above. The contributions of my Ph.D thesis are as follows:
- We develop the BALP framework for abductive reasoning. We first present the necessary enhancements to BLPs in order to support logical abduction. We then learn the parameters of the BALP framework using the
- Expectation Maximization (EM) algorithm adapted for BLPs by Kersting and De Raedt [2008].
- We apply BALPs to the task of plan recognition. We present an experimental evaluation comparing BALPs with existing approaches for abduction on different planrecognition datasets.
- We then extend BALPs to the task of natural language understanding. In this context, we apply BALPs to perform deeper inference to improve the performance of a question answering system. We enhance BALPs to be able to perform both abductive as well as deductive inference for natural language understanding.
3 CompletedWork
My progress till date includes development of the BALP framework for abductive reasoning and experimental evaluation of the developed framework on the task of plan recognition.
3.1 Bayesian Abductive Logic Programs
Bayesian Abductive Logic Programs (BALP) enhance BLPs with logical abduction. In an abductive task like plan recognition, the known facts are insufficient to support the derivation of deductive proof trees for the requisite queries. By using abduction, missing literals can be assumed in order to complete the proof trees needed to determine the structure of the ground network. We derive a set of most-specific abductive proof trees for the given observations using the method originally proposed by Stickel [1988]. The resulting abductive proof trees are then used to build the structure of the ground Bayes net using the standard approach for BLPs. We then learn the parameters of the BALP framework using the EM algorithm adapted for BLPs by Kersting and De Raedt [2008]. For probabilistic inference, we use off-the shelf approaches [Pearl, 1988; Gogate and Dechter, 2007] developed for Bayesian networks.
3.2 BALPs for Plan Recognition
The task of plan recognition involves identifying the high level plan of an agent based on its actions. We applied BALPs to the task of plan recognition and compared its performance with existing approaches for plan recognition. In the experimental evaluation performed on three plan-recognition datasets, we compared BALPs to planrecognition approaches that belonged to different categories (first-order logic, statistical learning, SRL). We found that BALPs consistently outperformed all these approaches, thus proving that they are effective for plan recognition.
4 FutureWork
Going forward, we would like to extend BALPs for the task of natural language understanding. In this context, we apply BALPs to perform deeper inference to improve the performance of a question answering system. An information extraction (IE) system is capable of extracting only those facts that are explicitly stated in the text. However, for some queries, the question answering system is required to perform deeper inference based on the facts that are stated explicitly in the text. We would like to apply BALPs to perform this kind of deeper inference. However, we notice that this inference does not always have to be abductive in nature. In some cases, a combination of both abductive and deductive inference is required to answer certain queries. Therefore, we would like to enhance BALPs to be able to perform both abductive and deductive inference for natural language understanding.
Learning a model for any SRL formalism involves two tasks - learning the structure (first-order clauses), and learning the parameters. For the task of plan-recognition, the structure of the model can be developed manually either based on inputs from an expert or based on the planning domain developed for the planner. However, it is not trivial to manually develop the set of first-order clauses for a natural language understanding system due to the vastness of the domain. For future work, we focus on the problem of learning the structure of the model for the task of natural language understanding.
@inproceedings{ijcai2011p492,
title = {Bayesian Abductive Logic Programs: A Probabilistic Logic for Abductive Reasoning},
author = {Raghavan, Sindhu V.},
booktitle = {Proceedings of the Twenty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-11}},
publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
editor = {Toby Walsh},
pages = {2840--2840},
year = {2011},
month = {7},
doi = {10.5591/978-1-57735-516-8/IJCAI11-492},
url = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-492},
}
TY - CPAPER TI - Bayesian Abductive Logic Programs: A Probabilistic Logic for Abductive Reasoning AU - Raghavan, Sindhu V. T2 - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11 PB - AAAI Press/International Joint Conferences on Artificial Intelligence PY - 2011 SP - 2840 EP - 2840 DO - 10.5591/978-1-57735-516-8/IJCAI11-492 UR - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-492 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: