ACL (UCY)

System Abductive Concept Learning (ACL)
Version 1 and 2
Code SICStus Prolog 3 #5 source code
References [1]
Pointers http://www-lia.deis.unibo.it/Software/ACL/
Other comments version 1 needs the system ICL

Description

Abductive Concept Learning (ACL) is a learning framework that extends the one of Inductive Logic Programming by considering both the background and the target theories as abductive theories and by adopting an abductive notion of entailment as the coverage relation. In this extended framework, it is possible to learn with incomplete background information about the training examples by exploiting the hypothetical reasoning of abduction.

Abductive theories are represented as triples , where P is a logic program, A is a set of abducible predicates, or predicates about which assumptions can be made, and I is a set of integrity constraints. The notion of entailment is replaced by that of abductive entailment: a goal G is abductively entailed from T (we write ) if there exists a set of ground facts (abductive explanation) such that ( explains G) and ( is consistent with the integrity constraints).

The ACL system learns abductive theories in two phases:

The first phase is performed by a subsystem of ACL called ACL1, while the second phase is performed by adopting the system ICL that is able to learn from positive and negative interpretations.

ACL1 is a top-down algorithm using beam-search 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 first learning phase can be performed on its own and is sufficient for many learning problem where no new constraints need to be learned. This is for example the case of many learning problems from incomplete information.

Two different versions of ACL1 are available. The first allows the full ACL problem to be solved by producing the necessary data for the second phase. The second version is an optimization of the first version for the case where no second phase must be performed. Version 1 should be used when the aim is to learn full abductive theories, containing new integrity constraints. Version 2 should be used when there is no need to learn new integrity constraints and the aim is simply to learn from an incomplete background knowledge.

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. The input background knowledge together with the rules learned constitute the background knowledge of ICL.

Motivations

Abductive theories are a powerful means of knowledge representation and reasoning. Therefore, learning them is an interesting task. They can be used to represent domains where the information is incomplete, therefore ACL can be used for learning in presence of incomplete knowledge. In this case, abduction completes the available background knowledge by generating explanations that allow the coverage of examples.

State of development

The Prolog implementation of the two versions of ACL1, together with the relative user manuals, is available. The code and manuals can be downloaded from http://www-lia.deis.unibo.it/Software/ACL/.

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.


back to index