The ACL Learning Framework

The learning framework of ACL differs from ILP because both the background knowledge and the learned theory
are abductive theories.
An abductive theory T in Abductive Logic Programming is a triple < P, A, I >, where P is a definite logic program, A is a set of predicates called abducible predicates (or simply abducibles), and I is a set of range-restricted clauses called integrity constraints.
As a knowledge representation framework, when we represent a problem in ALP via an abductive theory T, we generally assume that the abducible predicates in A carry all the incompleteness of the program P in modelling the external problem domain in the sense that if we (could) complete the abducible predicates in P then P would completely describe the problem domain. An abductive theory can support abductive (or hypothetical) reasoning for several purposes such as diagnosis, planning or default reasoning. The central notion used for this is that of an abductive explanation for an observation or a given goal. When an observation O can be abductively explained in a theory T with explanation Delta we write T|=AO. with Delta. We can now define the learning problem when the language of the background and target theories is the one of ALP.
 

Abductive Concept Learning

Given: Find:

A set of rules P'  belonging to H and a set of constraints I' belonging to Ysuch that the new abductive theory T'=< P union P', A, I union I'> satisfies the following conditions

where E+ stands for the conjunction of all positive examples.

In effect, we have replaced the deductive entailment in the ILP problem with abductive entailment to define the ACL learning problem.
 

Example 1

Suppose we want to learn the concept father. Let the background theory be T=< P, A, empty_set> where:
P={parent(john,mary).
    male(john).
    parent(david,steve).
    parent(katy,ellen).
    female(katy).}
A={male/1,female/1}
Let the training examples be:
E+={father(john,mary),father(david,steve)}.
E-={father(katy,ellen),father(john,steve),father(steve,john),father(steve,katy)}
In this case, a possible hypotheses learned by ACL would consist of
P'={father(X,Y) :- parent(X,Y),male(X)}
I'={:- male(X),female(X)}
This hypothesis satisfies the definition of ACL because
  1.  T'|=Afather(john,mary),father(david,steve) with D={male(david)}
  2.  T' does not abductively entail father(katy,ellen) as the only possible explanation for this goal, namely {male(katy)} is made inconsistent by the learned integrity constraints I'
  3.  T' does not abductively entail father(john,steve), father(steve,john) and father(steve,katy) because they have no possible abductive explanations.
Hence, despite the fact that the background theory is incomplete (in its abducible predicates), ACL can find an appropriate solution to the learning problem by suitably extending the background theory with abducible assumptions. Note that the learned theory without the integrity constraint would not satisfy the definition of ACL, because there would exist an abductive explanation for the negative example father(katy,ellen), namely {male(katy). This explanation is prohibited in the complete theory by the learned constraint together with the fact female(kathy).

The full ACL problem can be split into two subproblems: (1) learning the rules together with appropriate strong explanations and (2) learning integrity constraints. The solutions of the two subproblems can be combined to obtain a solution for the original problem.

The first subproblem, called ACL1, has the following definition.

ACL1

Given: Find:

A set of rules P' belonging to H such that the new abductive theory TACL1=< P union P', A, I> satisfies the following conditions

where not_E- stands for the conjunction of the complement of every negative example.
 

Example 2

In the case of example 1 above, a solution to the ACL1 problem would consist of
P'={father(X,Y) :- parent(X,Y),male(X)}
Delta+={male(david)}
Delta-={not_female(katy)}

The ACL1 problem is solved by the system ACL1. The input file for the learning problem of example 1 is father.bg.  From this input file, the ACL1 system finds the above solution, as can be seen from the father.rules file.

Indeed, the information generated by ACL1 through the abductive explanations for negative examples can be used to provide a solution of the full ACL problem through a second learning phase. From the output of ACL1, i.e., its set of rules and the sets of assumptions and for covering positive examples and uncovering negative ones, a solution to ACL can be found by learning constraints that are consistent with Delta+and inconsistent with the complement of every abducible in Delta- .

The definition of the second subproblem, called ACL2, can be given as follows.

ACL2

Given Find

A set of constraints I' Î Ysuch that the new abductive theory satisfies the following condition

where not_l is the complement of l with respect to default negation.

The ACL2 problem is solved by means of the ICL system. The input for ICL is generated by the ACL1 system, for the case of example 1 the input files for ICL are again father.bg, containing the background knowledge, and father.kb, containing the interpretations, that is generated by the ACL1 system.
The theory, obtained by combining the solutions of the two subproblems, gives a solution to the full ACL problem.

Example 2

In the case of example 1 and 2 above, the input to the second learning phase, performed by ICL, would consist of The solution of the ACL2 problem is
I'={:- male(X),female(X)}
Indeed the above solution is found by ICL from the above interpretations, as can be seen from the file father.theory.

Back to the main ACL page.

Back to the LIA Home Page
Go to the DEIS Home Page Go to the Alma Mater Home Page