Abductive logic programming: Difference between revisions

Revision as of 20:35, 23 November 2023

Latest revision as of 22:59, 1 February 2024

(6 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Logic programming using abductive reasoning}}

{{No footnotes|date=February 2015}}{{Programming paradigms}}

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

Line 93:

==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&ndash;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 &ndash; 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 iscannot consistent tobe assumeshown that the bird canis flyabnormal. The example can be formulated naturally as an abductive logic program. Here is a variant of the example using negation as failure:

<syntaxhighlight lang="prolog">

canfly(X) :- bird(X), normal_flying_birdnot(abnormal_flying_bird(X)).

false :- normal_flying_birdabnormal_flying_bird(X),:- wounded(X).

bird(john).

bird(mary).

Line 105 ⟶ 106:

</syntaxhighlight>

InHere is the generalsame case,example abductionusing in ALP can be simulated by adding, for everyan abducible predicate <syntaxhighlight inline lang="prolog">p,normal_flying_bird(_)</syntaxhighlight> awith pairan ofintegrity clausesconstraint in ALP:

Here the predicate <syntaxhighlight inline lang="prolog">normal_flying_bird(_)</syntaxhighlight> is abducible. 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 assumption and conclusion are acceptable 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.

The example can be reformulated in normal logic programming without abduction, by using [[negation as failure]] with a non-abducible predicate <syntaxhighlight inline lang="prolog">abnormal_flying_bird(_),</syntaxhighlight> which is the contrary of the abducible predicate <syntaxhighlight inline lang="prolog">normal_flying_bird(_)</syntaxhighlight>:

<syntaxhighlight lang="prolog">

canfly(X) :- bird(X), not(abnormal_flying_birdnormal_flying_bird(X)).

abnormal_flying_birdfalse :- normal_flying_bird(X):-, wounded(X).

bird(john).

bird(mary).

Line 117 ⟶ 116:

</syntaxhighlight>

The example can be reformulated in normal logic programming without abduction, by using [[negation as failure]] with a non-abducible predicate <syntaxhighlight inline lang="prolog">abnormal_flying_birdnormal_flying_bird(_),</syntaxhighlight> which is the contrary of the abducible predicate <syntaxhighlight inline lang="prolog">normal_flying_birdabnormal_flying_bird(_)</syntaxhighlight>:.

In general, reasoning by means of abduction in ALP simulates reasoning by negation as failure in normal logic programming.<ref>Eshghi, K. and Kowalski, R.A., 1989, June. Abduction Compared with Negation by Failure. In ICLP (Vol. 89, pp. 234-255).</ref> Conversely, negation as failure with the [[stable model semantics]] can simulate abduction in ALP.

HereUsing theabduction predicatein <syntaxhighlightALP inline lang="prolog">normal_flying_bird(_)</syntaxhighlight> is abducible. Itit 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 andbecause conclusionit arecannot acceptablebe 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>

In the general case, abduction in ALP can be simulated by adding, for every abducible predicate <syntaxhighlight inline lang="prolog">p,</syntaxhighlight> a pair of clauses:

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

abpnegp :- not(p).

</syntaxhighlight>

whereThis <syntaxhighlightpair inlineof lang="prolog">abp</syntaxhighlight>clauses ishas atwo predicatestable representingmodels, theone contraryin ofwhich <syntaxhighlight inline lang="prolog">p,</syntaxhighlight> is true, and neitherthe <syntaxhighlightother inline lang="prolog">abp</syntaxhighlight>in norwhich <syntaxhighlight inline lang="prolog">pnegp,</syntaxhighlight> are abducible.<ref>Kakas,is Atrue.C., Kowalski,This R.A.technique andfor Toni,simulating F.,abduction 1992. Abductive logicis commonly used in [[answer set programming.]] Journalto ofsolve logicproblems using a ''generate and computation,test'' 2(6), ppmethodology.719-770.</ref>

==Formal semantics==

Line 155 ⟶ 156:

* {{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 |year=1990 |isbn=978-0273088226 |pages=385–391 }}

* {{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 |citeseerx=10.1.1.31.9982 }}

* {{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 |citeseerx=10.1.1.37.3655 }}

* {{cite journal |first1=Marc |last1=Denecker |first2=Danny |last2=De Schreye |title=SLDNFA: An Abductive Procedure for Abductive Logic Programs |journal=[[Journal of Logic Programming]] |volume=34 |issue=2 |pages=111–167 |date=February 1998 |doi=10.1016/S0743-1066(97)00074-5 |citeseerx = 10.1.1.21.6503 }}

* {{cite journal |first1=M. |last1=Denecker |first2=A.C. |last2=Kakas |title=Special issue: abductive logic programming |journal=Journal of Logic Programming |volume=44 |issue=1–3 |pages=1–4 |date=July 2000 |doi=10.1016/S0743-1066(99)00078-3 |doi-access=free }}

Line 168 ⟶ 169:

* [http://lia.deis.unibo.it/sciff/ SCIFF]

* [http://dtai.cs.kuleuven.be/krr/Asystem/asystem.html Asystem]

{{Programming paradigms navbox}}

[[Category:Logic programming]]