Content deleted Content added
reduce verbosity per Wikipedia:Manual_of_Style/Words_to_watch#Editorializing and MOS:NOTE |
change paradigms template to navbox (see Template talk:Programming paradigms#too long) |
||
| (28 intermediate revisions by 17 users not shown) | |||
Line 1:
{{Short description|Logic programming using abductive reasoning}}
{{No footnotes|date=February 2015
'''Abductive logic programming''' ('''ALP''') is a high-level [[knowledge representation|knowledge-representation]] framework that can be used to solve problems declaratively, based on [[abductive reasoning]]. It extends normal [[logic programming]] by allowing some predicates to be incompletely defined, declared as abducible predicates. Problem solving is effected by deriving hypotheses on these abducible predicates (abductive hypotheses) as solutions of problems to be solved. These problems can be either observations that need to be explained (as in classical abduction) or goals to be achieved (as in normal [[logic programming]]). It can be used to solve problems in diagnosis, [[planning]], natural language and [[machine learning]]. It has also been used to interpret [[negation as failure]] as a form of abductive reasoning.
==Syntax==
Line 7 ⟶ 8:
* P is a logic program of exactly the same form as in logic programming
* A is a set of predicate names, called the abducible predicates
* IC is a set of [[first-order logic|first-order classical formulae]].
Normally, the logic program P does not contain any clauses whose head (or conclusion) refers to an abducible predicate. (This restriction can be made without loss of generality.) Also in practice, many times, the [[integrity constraints]] in IC are often restricted to the form of denials, i.e. clauses of the form:
Line 61 ⟶ 62:
; Domain knowledge (P)
: <
feed(lactose) :- make(permease), make(galactosidase).
make(Enzyme) :- code(Gene, Enzyme), express(Gene).
Line 69 ⟶ 70:
code(lac(z), galactosidase).
temperature(low) :- amount(glucose, low).
</syntaxhighlight>
; Integrity constraints (IC)
: <
false :- amount(S, V1), amount(S, V2), V1 ≠ V2.
</syntaxhighlight>
; Abducibles (A)
: <
abducible_predicate(amount).
</syntaxhighlight>
The problem goal is <math>G=\text{feed(lactose)}</math>. This can arise either as an observation to be explained or as a state of affairs to be achieved by finding a plan. This goal has two abductive explanations:
Line 86 ⟶ 87:
\end{cases}</math>
The decision which of the two to adopt could depend on
Once an explanation has been chosen, then this becomes part of the theory, which can be used to draw new conclusions. The explanation and more generally these new conclusions form the solution of the problem.
==Default reasoning in ALP==
As shown in the Theorist system,<ref>{{cite report | url=https://www.cs.ubc.ca/~poole/papers/Theorist-CS-86-06.pdf |first1=David |last1=Poole |first2=Randy |last2=Goebel |first3=Romas |last3=Aleliunas | title=Theorist: A Logical Reasoning System for Defaults and Diagnosis | institution=Univ. Waterloo | type=Research Report | number=CS-86-06 | date=Feb 1986 }}</ref><ref>{{cite book | url= |first1=David |last1=Poole |first2=Randy |last2=Goebel |first3=Romas |last3=Aleliunas | contribution=Theorist: A Logical Reasoning System for Defaults and Diagnosis | pages=331–352 | doi=10.1007/978-1-4612-4792-0 | isbn=978-1-4612-9158-9 | editor1=Nick J. Cercone | editor2= Gordon McCalla | title= The Knowledge Frontier – Essays in the Representation of Knowledge | ___location=New York, NY | publisher=Springer | series=Symbolic Computation | volume= | edition=1st | year=1987 |s2cid=38209923 }}</ref> abduction can also be used for [[default reasoning]].
Moreover, abduction in ALP can simulate [[negation as failure]] in normal logic programming.
Consider the classic example of reasoning by default that a bird can fly if it cannot be shown that the bird is abnormal. Here is a variant of the example using negation as failure:
<syntaxhighlight lang="prolog">
canfly(X) :- bird(X), not(abnormal_flying_bird(X)).
abnormal_flying_bird(X):- wounded(X).
bird(john).
bird(mary).
wounded(john).
</syntaxhighlight>
Here is the same example using an abducible predicate <syntaxhighlight inline lang="prolog">normal_flying_bird(_)</syntaxhighlight> with an integrity constraint in ALP:
<syntaxhighlight lang="prolog">
canfly(X) :- bird(X), normal_flying_bird(X).
false :- normal_flying_bird(X), wounded(X).
bird(john).
bird(mary).
wounded(john).
</syntaxhighlight>
The abducible predicate <syntaxhighlight inline lang="prolog">normal_flying_bird(_),</syntaxhighlight> is the contrary of the predicate <syntaxhighlight inline lang="prolog">abnormal_flying_bird(_)</syntaxhighlight>.
Using abduction in ALP it is possible to conclude <syntaxhighlight inline lang="prolog">canfly(mary)</syntaxhighlight> under the assumption <syntaxhighlight inline lang="prolog">normal_flying_bird(mary)</syntaxhighlight>. The conclusion can be derived from the assumption because it cannot be shown that the integrity constraint is violated, which is because it cannot be shown that <syntaxhighlight inline lang="prolog">wounded(mary).</syntaxhighlight> In contrast, it is not possible to conclude <syntaxhighlight inline lang="prolog">canfly(john),</syntaxhighlight> because the assumption <syntaxhighlight inline lang="prolog">normal_flying_bird(john)</syntaxhighlight> together with the fact <syntaxhighlight inline lang="prolog">wounded(john)</syntaxhighlight> violates the integrity constraint. This manner of reasoning in ALP simulates reasoning with negation as failure.<ref>Eshghi, K. and Kowalski, R.A., 1989, June. Abduction Compared with Negation by Failure. In ICLP (Vol. 89, pp. 234-255).</ref>
Conversely, it is possible to simulate abduction in ALP using negation as failure with the [[stable model semantics]].<ref>Kakas, A.C., Kowalski, R.A. and [[Francesca Toni |Toni, F.]], 1992. Abductive logic programming. Journal of logic and computation, 2(6), pp.719-770.</ref> This can be done by adding, for every abducible predicate <syntaxhighlight inline lang="prolog">p,</syntaxhighlight> an additional contrary predicate <syntaxhighlight inline lang="prolog">negp,</syntaxhighlight> and a pair of clauses:
<syntaxhighlight lang="prolog">
p :- not(negp).
negp :- not(p).
</syntaxhighlight>
This pair of clauses has two stable models, one in which <syntaxhighlight inline lang="prolog">p,</syntaxhighlight> is true, and the other in which <syntaxhighlight inline lang="prolog">negp,</syntaxhighlight> is true. This technique for simulating abduction is commonly used in [[answer set programming]] to solve problems using a ''generate and test'' methodology.
==Formal semantics==
Line 100 ⟶ 139:
This definition leaves open the choice of the underlying semantics of logic programming through which we give the exact meaning of the entailment relation <math>\models</math> and the notion of consistency of the (extended) logic programs. Any of the different semantics of logic programming such as the completion, stable or well-founded semantics can (and have been used in practice) to give different notions of abductive explanations and thus different forms of ALP frameworks.
The above definition takes a particular view on the formalization of the role of the integrity constraints <math>\mathit{IC}</math> as restrictions on the possible abductive solutions. It requires that these are entailed by the logic program extended with an abductive solution, thus meaning that in any model of the extended logic program (which one can think of as an ensuing world given <math>\Delta</math>) the requirements of the integrity constraints are met. In some cases this may be unnecessarily strong and the weaker requirement of consistency, namely that <math>P \cup \mathit{IC} \cup \Delta</math> is consistent, can be sufficient, meaning that there exists at least one model (possible ensuing world) of the extended program where the integrity constraints hold. In practice, in many cases, these two ways of formalizing the role of the integrity constraints coincide as the logic program and its extensions always have a unique model. Many of the ALP systems use the entailment view of the integrity constraints as this can be easily implemented without the need for any extra specialized procedures for the satisfaction of the integrity constraints since this view treats the constraints in the same way as the problem goal.
In many practical cases, the third condition in this formal definition of an abductive explanation in ALP is either trivially satisfied or it is contained in the second condition via the use of specific integrity constraints that capture consistency.
==Implementation and systems==
Most of the implementations of ALP extend the SLD resolution-based computational model of logic programming. ALP can also be implemented by means of its link with [[Answer Set Programming]] (ASP), where the ASP systems can be employed. Examples of systems of the former approach are ACLP, A-system, CIFF, SCIFF, ABDUAL and ProLogICA.
== See also ==
* [[Inductive logic programming]]
== Notes ==
Line 118 ⟶ 153:
== References ==
{{refbegin}}
* {{cite book |first1=D. |last1=Poole |first2=R. |last2=Goebel |first3=R. |last3=Aleliunas |chapter=Theorist: a logical reasoning system for defaults and diagnosis |editor1-first=Nick |editor1-last=Cercone |editor2-first=Gordon |editor2-last=McCalla |title=The Knowledge Frontier: Essays in the Representation of Knowledge |
* {{cite book |first1=A.C. |last1=Kakas |first2=P. |last2=Mancarella |chapter=Generalised Stable Models: A Semantics for Abduction |editor-first=L.C. |editor-last=Aiello |title=ECAI 90: proceedings of the 9th European Conference on Artificial Intelligence |publisher=Pitman
* {{cite journal |first1=L. |last1=Console |first2=D.T. |last2=Dupre |first3=P. |last3=Torasso |title=On the Relationship between Abduction and Deduction |journal=[[Journal of Logic and Computation]] |volume=1 |issue=5 |pages=661–690 |year=1991 |doi=10.1093/logcom/1.5.661
* {{cite journal |first1=A.C. |last1=Kakas |first2=R.A. |last2=Kowalski |author2link = Robert Kowalski|first3=F. |last3=Toni|author3-link= Francesca Toni |title=Abductive Logic Programming |journal=Journal of Logic and Computation |volume=2 |issue=6 |pages=719–770 |year=1993 |doi=10.1093/logcom/2.6.719
* {{cite journal |first1=Marc |last1=Denecker |first2=Danny |last2=De Schreye |title=SLDNFA: An Abductive Procedure for Abductive Logic Programs |journal=
* {{cite journal |first1=M. |last1=Denecker |first2=A.C. |last2=Kakas |title=Special issue: abductive logic programming |journal=
* {{cite book |first1=M. |last1=Denecker |first2=A.C. |last2=Kakas |chapter=Abduction in Logic Programming |editor1-first=A.C. |editor1-last=Kakas |editor2-first=F. |editor2-last=Sadri |title=Computational Logic: Logic Programming and Beyond: Essays in Honour of Robert A. Kowalski |
* {{cite journal |first=D. |last=Poole |title=Probabilistic Horn abduction and Bayesian networks |journal=[[Artificial Intelligence (journal)|Artificial Intelligence]]|volume=64 |issue=1 |pages=81–129 |year=1993 |doi=10.1016/0004-3702(93)90061-F |url=https://www.cs.ubc.ca/~poole/papers/pha-bn.pdf }}
* {{cite journal|first1=F. |last1=Esposito |first2=S. |last2=Ferilli |first3=T.M.A. |last3=Basile |first4=N. |last4=Di Mauro |title=Inference of abduction theories for handling incompleteness in first-order learning |journal=
{{refend}}
Line 134 ⟶ 169:
* [http://lia.deis.unibo.it/sciff/ SCIFF]
* [http://dtai.cs.kuleuven.be/krr/Asystem/asystem.html Asystem]
{{Programming paradigms navbox}}
[[Category:Logic programming]]
| |||