Abductive logic programming: Difference between revisions

Revision as of 15:17, 22 November 2023

Latest revision as of 22:59, 1 February 2024

(7 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 91:

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==

===Example 4===

The following example shows how abduction can be to simulate [[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>

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 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), normalnot(abnormal_flying_bird(X)).

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

bird(john).

bird(mary).

Line 101 ⟶ 106:

</syntaxhighlight>

Here is the same example using an abducible predicate <syntaxhighlight inline lang="prolog">normal_flying_bird(_)</syntaxhighlight> with an integrity constraint in ALP:

Here the predicate <syntaxhighlight inline lang="prolog">normal()</syntaxhighlight> is abducible, and the abducible condition <syntaxhighlight inline lang="prolog">normal(X)</syntaxhighlight> corresponds to the negative literal <syntaxhighlight inline lang="prolog">not(abnormal(X))</syntaxhighlight> in normal logic programming. The constraint <syntaxhighlight inline lang="prolog">false :- normal(X), wounded(X)</syntaxhighlight> ensures that the abducible condition is not assumed when the condition <syntaxhighlight inline lang="prolog">wounded(X)</syntaxhighlight> also holds. This is like ensuring that <syntaxhighlight inline lang="prolog">not(abnormal(X))</syntaxhighlight> succeeds when <syntaxhighlight inline lang="prolog">wounded(X)</syntaxhighlight> fails.

The goal of explaining the observation <syntaxhighlight inline lang="prolog">canfly(mary)</syntaxhighlight> has the solution <syntaxhighlight inline lang="prolog">normal(mary)</syntaxhighlight>. The same solution justifies the answer <syntaxhighlight inline lang="prolog">X = mary</syntaxhighlight> for the goal:

<syntaxhighlight lang="prolog">

canfly(X) :- bird(X), normal_flying_bird(X).

-? canfly(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 135 ⟶ 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 148 ⟶ 169:

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

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

{{Programming paradigms navbox}}

[[Category:Logic programming]]