Abductive Logic Programming Task

An Abductive Logic Programming Task is a logic-based abductive reasoning task that extends logic programming with abductive reasoning to find logical explanations for observed facts while maintaining logical consistency.

AKA: ALP Task, Logical Abduction Task, Explanation Finding Logic Task.
Context:
- It can typically be formalized as a tuple <⟨g, T, A, I⟩> where abductive logic programming ground goal g represents the observation to be explained, abductive logic programming theory T is a normal logic program, abductive logic programming abducible set A contains potential explanation atoms, and abductive logic programming integrity constraint set I ensures explanation consistency.
- It can typically generate abductive logic programming solution consisting of ground atom set Δ (the explanation) and ground substitution θ (the answer substitution) such that solution consistency requirements and goal derivation requirements are satisfied.
- It can typically require that T ∪ Δ is logically consistent and that T ∪ Δ ⊨ g, where Δ ⊆ A and ⊨ represents logical entailment.
- It can typically support knowledge completion through missing information identification and hypothetical fact generation.
- It can typically enable diagnostic reasoning by identifying potential causes for observed symptoms.
- ...
- It can often be solved through abductive logic programming system using either top-down abductive resolution or bottom-up model construction approaches.
- It can often employ minimality criterion to select explanations with the fewest assumptions, following Occam's razor principle.
- It can often require bounded computational resources such as maximum resolution depth or execution time limit to ensure algorithm termination.
- It can often complement inductive logic programming task where the former generates ground facts while the latter produces general rules.
- It can often be applied in logic-based artificial intelligence systems for explanation generation and automated reasoning.
- ...
- It can range from being a Simple Abductive Logic Programming Task to being a Complex Abductive Logic Programming Task, depending on its abductive logic programming theory complexity.
- It can range from being a Pure Abductive Logic Programming Task to being a Hybrid Abductive-Inductive Logic Programming Task, depending on its abductive logic programming learning integration.
- It can range from being a Domain-Specific Abductive Logic Programming Task to being a General-Purpose Abductive Logic Programming Task, depending on its abductive logic programming application scope.
- It can range from being a Propositional Abductive Logic Programming Task to being a First-Order Abductive Logic Programming Task, depending on its abductive logic programming logical expressivity.
- ...
- It can integrate with answer set programming for abductive logic programming solution computation.
- It can connect to constraint logic programming for abductive logic programming integrity constraint enforcement.
- It can support machine learning system for abductive logic programming knowledge acquisition.
- It can combine with inductive logic programming for abductive logic programming theory refinement.
- ...
Examples:
Counter-Examples:
- Abductive Concept Learning Task, which focuses on concept classification rather than explanation generation through logical theory extension.
- Backward Chaining Task, which performs logical deduction from existing knowledge without generating new abducible hypothesises.
- Extraction-Case Abduction Task, which relies on case-based reasoning rather than logic programming formalism for explanation derivation.
- Set Covering Abduction Task, which employs set theory instead of logical entailment to find minimal covering explanations.
- Bayesian Inference Task, which uses probability theory rather than symbolic logic for explanation generation and hypothesis evaluation.
See: Logic-based Abductive Reasoning Task, Non-Monotonic Reasoning Task, Most Economical Explanation Selection, Explanation-based Learning Task, Inductive Logic Programming Task, Set Cover Problem Task, Occam's Razor Application, Prior Probability Calculation, Proof Theory Application, Sequent Calculus System, Analytic Tableaux Method, Modal Logic System, Integrity Constraint Enforcement.

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.

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];

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.

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).