Abductive Concept Learning (ACL)

System: Abductive Concept Learning (ACL)
Code: SICStus Prolog 2.1 #8 source code, Solaris platform (because of ICL)
References: Kakas and Riguzzi 1997
Other comments: needs the system ICL

ACL learns abductive theories. An abductive theory is a triple $T=\langle P, A, I \rangle$ where $P$ is a logic program, $A$ is a set of predicates about which assumptions can be made, called abducibles, and $I$ is a set of integrity constraints in the form of denials. The notion of entailment is replaced by that of abductive entailment: a goal $G$ is abductively entailed from $T$ (we write $T\models_{A}G$) if there exists a set of ground facts $\Delta$ ( abductive explanation) such that $P \cup \Delta \models G$ ($\Delta$ explains $G$) and $P \cup \Delta \models I$ ($\Delta$ is consistent with the integrity constraints).

The input of ACL consists of an abductive theory $T$ as background knowledge and two sets of ground atoms as positive and negative examples. ACL finds an abductive theory $T'=\langle P', A, I' \rangle$ with $P' \supset P$ and $I' \supseteq I$ such that $T' \models_{A} E^{+}$ and $\forall e^{-} \in E^{-}$, $T' \not \models_{A} e^{-}$ where $E^+$ stands for the conjunction of all positive examples.

Learning abductive theories allows to learn from incomplete knowledge, since abducible predicates can be used in order to represent incomplete knowledge.

The algorithm learns first all the rules and then all the constraints. Rule learning is performed by a top-down ILP algorithm where coverage testing is performed using an abductive proof procedure. The algorithm adopts a beam search strategy and a special heuristic function that gives different weights to examples covered with or without abduction. The output of the rule learning phase is a set of rules and a set of explanations: one explanation (possibly empty) for each positive example and all possible explanations (of which none is empty) for each negative examples. The requirement that no explanation for negative examples is empty is needed in order to be able to exclude all of them in the second phase by learning constraints.

Constraints are learned using ICL. The input to ICL consists of the abductive explanations for positive examples as positive interpretations and the abductive explanations for negative examples as negative interpretations. Rules previously learned together with those from the background knowledge constitute the background knowledge of ICL.

References

  1. A.C. Kakas and F. Riguzzi, 'Learning with Abduction' in the Seventh International Workshop on Inductive Logic Programming (ILP97), Lecture Notes in Artificial Intelligence, Volume 1297, Springer Verlag, 1997, pp. 181-189.