Abductive Logic Programming Task
An Abductive Logic Programming (ALP) Task is a Logic-based Abduction Reasoning Task that extends Logic Programming with Abductive Reasoning.
- Context:
- It can be solved by a Abductive Logic Programming System by implementing a Abductive Logic Programming Algorithm.
- …
- Example(s):
- Counter-Example(s):
- See: Non-Monotonic Reasoning, Most Economical Explanation, Explanation-based Learning, Explanation-Based Learning, Inductive Logic Programming, Set Cover Problem, Occam's Razor, Prior Probability, Proof Theory, Sequent Calculus, Analytic Tableaux, Modal Logic, Abductive Logic Programming.
References
2019
- (Wikipedia, 2019) ⇒ https://en.wikipedia.org/wiki/Abductive_reasoning#Logic-based_abduction Retrieved:2019-9-1.
- In logic, explanation is accomplished through the use of a logical theory [math]\displaystyle{ T }[/math] representing a domain and a set of observations [math]\displaystyle{ O }[/math] . Abduction is the process of deriving a set of explanations of [math]\displaystyle{ O }[/math] according to [math]\displaystyle{ T }[/math] and picking out one of those explanations. For [math]\displaystyle{ E }[/math] to be an explanation of [math]\displaystyle{ O }[/math] according to [math]\displaystyle{ T }[/math] , it should satisfy two conditions:
- [math]\displaystyle{ O }[/math] follows from [math]\displaystyle{ E }[/math] and [math]\displaystyle{ T }[/math] ;
- [math]\displaystyle{ E }[/math] is consistent with [math]\displaystyle{ T }[/math] .
- In formal logic, [math]\displaystyle{ O }[/math] and [math]\displaystyle{ E }[/math] are assumed to be sets of literals. The two conditions for [math]\displaystyle{ E }[/math] being an explanation of [math]\displaystyle{ O }[/math] according to theory [math]\displaystyle{ T }[/math] are formalized as: : [math]\displaystyle{ T \cup E \models O; }[/math] : [math]\displaystyle{ T \cup E }[/math] is consistent.
Among the possible explanations [math]\displaystyle{ E }[/math] satisfying these two conditions, some other condition of minimality is usually imposed to avoid irrelevant facts (not contributing to the entailment of [math]\displaystyle{ O }[/math] ) being included in the explanations. Abduction is then the process that picks out some member of [math]\displaystyle{ E }[/math] . Criteria for picking out a member representing "the best" explanation include the simplicity, the prior probability, or the explanatory power of the explanation.
A proof-theoretical abduction method for first order classical logic based on the sequent calculus and a dual one, based on semantic tableaux (analytic tableaux) have been proposed (Cialdea Mayer & Pirri 1993). The methods are sound and complete and work for full first order logic, without requiring any preliminary reduction of formulae into normal forms. These methods have also been extended to modal logic.
Abductive logic programming is a computational framework that extends normal logic programming with abduction. It separates the theory [math]\displaystyle{ T }[/math] into two components, one of which is a normal logic program, used to generate [math]\displaystyle{ E }[/math] by means of backward reasoning, the other of which is a set of integrity constraints, used to filter the set of candidate explanations.
- In logic, explanation is accomplished through the use of a logical theory [math]\displaystyle{ T }[/math] representing a domain and a set of observations [math]\displaystyle{ O }[/math] . Abduction is the process of deriving a set of explanations of [math]\displaystyle{ O }[/math] according to [math]\displaystyle{ T }[/math] and picking out one of those explanations. For [math]\displaystyle{ E }[/math] to be an explanation of [math]\displaystyle{ O }[/math] according to [math]\displaystyle{ T }[/math] , it should satisfy two conditions:
2017
- (Kakas, 2017) ⇒ Antonis C. Kakas. (2017). “Abduction”. In: (Sammut & Webb, 2017) DOI:10.1007/978-1-4899-7687-1_1
- QUOTE: Abduction as studied in the area of Artificial Intelligence and the perspective of learning is mainly defined in a logic-based approach. Other approaches to abduction include set covering (See, e.g., Reggia 1983) or case-based explanation, (e.g., Leake 1995). The following explanation uses a logic-based approach.
Given a set of sentences [math]\displaystyle{ T }[/math] (a theory or model), and a sentence [math]\displaystyle{ O }[/math] (observation), the abductive task is the problem of finding a set of sentences [math]\displaystyle{ H }[/math] (abductive explanation for [math]\displaystyle{ O }[/math]) such that:
::: 1. [math]\displaystyle{ T \cup H \models O }[/math];
- QUOTE: Abduction as studied in the area of Artificial Intelligence and the perspective of learning is mainly defined in a logic-based approach. Other approaches to abduction include set covering (See, e.g., Reggia 1983) or case-based explanation, (e.g., Leake 1995). The following explanation uses a logic-based approach.
- 2. [math]\displaystyle{ T \cup H }[/math] is consistent,
- where [math]\displaystyle{ \models }[/math] denotes the deductive entailment relation of the formal logic used in the representation of our theory and consistency refers also to the corresponding notion in this logic. The particular choice of this underlying formal framework of logic is in general a matter that depends on the problem or phenomena that we are trying to model. In many cases, this is based on first order predicate calculus, as, for example, in the approach of theory completion in Muggleton and Bryant (2000). But other logics can be used, e.g., the nonmonotonic logics of default logic or logic programming with negation as failure when the modeling of our problem requires this level of expressivity.
2010
- (Corapi et al., 2010) ⇒ Domenico Corapi, Alessandra Russo, and Emil C. Lupu. (2010). “Inductive Logic Programming As Abductive Search.” In: Proceedings of Technical Communications of the International Conference on Logic Programming, 2010. doi:10.4230/LIPIcs.ICLP.2010.54
- QUOTE: ALP and ILP are extensions of logic programming. They both search for a hypothesis that is able to account for some given evidence. ALP constructs hypotheses in the form of ground facts. ILP systems generate rules that are able to discriminate between positive and negative examples that represent the training data. In general, ILP is regarded as a machine learning technique and used when a certain knowledge base must be enriched with rules that are also able to classify new examples (...)
Definition 1.1. An ALP task is defined as [math]\displaystyle{ \langle g, T, A, I \rangle }[/math] where [math]\displaystyle{ T }[/math] is a normal logic program, [math]\displaystyle{ A }[/math] is a set of abducible facts, [math]\displaystyle{ I }[/math] is a set of integrity constraints and [math]\displaystyle{ g }[/math] is a ground goal. [math]\displaystyle{ \Delta \in ALP \langle g, T, A, I \rangle }[/math] is an abductive solution for the ALP task [math]\displaystyle{ \langle g, T, A, I\rangle }[/math], if [math]\displaystyle{ \Delta \subseteq A, T \cup \Delta }[/math] is consistent, [math]\displaystyle{ T \cup \Delta \models g }[/math] and [math]\displaystyle{ T \cup \Delta \models I }[/math]. [math]\displaystyle{ ALP \langle g, T, A, I \rangle }[/math] denotes the set of all abductive solutions for the given ALP task.
- QUOTE: ALP and ILP are extensions of logic programming. They both search for a hypothesis that is able to account for some given evidence. ALP constructs hypotheses in the form of ground facts. ILP systems generate rules that are able to discriminate between positive and negative examples that represent the training data. In general, ILP is regarded as a machine learning technique and used when a certain knowledge base must be enriched with rules that are also able to classify new examples (...)
2009
- (Ray, 2009) ⇒ Oliver Ray. (2009). “Nonmonotonic Abductive Inductive Learning.” In: Applied Logic Journal, 7(3). doi:10.1016/j.jal.2008.10.007
- QUOTE: ALP seeks to find the conditions under which a query [math]\displaystyle{ G }[/math] (goal) can be made to succeed from a program [math]\displaystyle{ T }[/math] (theory) composed of facts, rules and constraints. The ALP task is usually defined as computing a set of ground atoms [math]\displaystyle{ \Delta }[/math], called an explanation, together with a ground substitution [math]\displaystyle{ \theta }[/math], called an answer substitution, such that [math]\displaystyle{ T \cup \Delta \models G \theta }[/math]. The atoms in [math]\displaystyle{ \Delta }[/math] are usually restricted to a set [math]\displaystyle{ A }[/math] of predicates called abducibles, which identify concepts for which only partial information is available in the theory (e.g., potential faults in a diagnosis task or possible actions in a planning domain). Any pair [math]\displaystyle{ (\Delta, \theta) }[/math] which satisfies these properties is called an abductive solution of G w.r.t. [math]\displaystyle{ T }[/math] and [math]\displaystyle{ A }[/math].
Hereafter, [math]\displaystyle{ \phi (T,G,A) }[/math] will denote the set of all abductive solutions of G w.r.t. [math]\displaystyle{ T }[/math] and [math]\displaystyle{ A }[/math]. Systems for computing such abductive solutions can be classed into two complementary approaches: top-down ALP methods that extend resolution inference with the ability to assume literals [21], and bottom-up methods based on model construction techniques like Answer Set Programming (ASP) [26]. To ensure termination of these procedures, it is assumed some appropriate bound is placed on computational resources (e.g., maximum resolution depth in an ALP system or total execution time in an ASP system).
- QUOTE: ALP seeks to find the conditions under which a query [math]\displaystyle{ G }[/math] (goal) can be made to succeed from a program [math]\displaystyle{ T }[/math] (theory) composed of facts, rules and constraints. The ALP task is usually defined as computing a set of ground atoms [math]\displaystyle{ \Delta }[/math], called an explanation, together with a ground substitution [math]\displaystyle{ \theta }[/math], called an answer substitution, such that [math]\displaystyle{ T \cup \Delta \models G \theta }[/math]. The atoms in [math]\displaystyle{ \Delta }[/math] are usually restricted to a set [math]\displaystyle{ A }[/math] of predicates called abducibles, which identify concepts for which only partial information is available in the theory (e.g., potential faults in a diagnosis task or possible actions in a planning domain). Any pair [math]\displaystyle{ (\Delta, \theta) }[/math] which satisfies these properties is called an abductive solution of G w.r.t. [math]\displaystyle{ T }[/math] and [math]\displaystyle{ A }[/math].