Learning Definite and Normal Logic Programs by Induction on Failure
Author(s)
Kimber, Timothy
Type
Thesis
Abstract
This thesis presents two novel inductive logic programming (ILP) approaches, based on
the notion of a connected theory. A connected theory contains clauses that depend on
one another, either directly or via clauses in the background knowledge. Generalisation
of such a theory is proved to be a sound and complete method for learning definite ILP
hypotheses. The Induction on Failure (IOF) proof procedure, based on the connected
theory generalisation method, adds secondary examples into the hypothesis, and generates
auxiliary clauses to explain them. These concepts, novel to IOF, address the issues of
incompleteness present in previous definite ILP methods.
The concept of the connected theory is also applied to the non-monotonic, normal program
setting. Thus, the method of generalisation of a normal connected theory is presented.
Fundamental to this is the assertion that a partial non-monotonic hypothesis must include
both positive and negative information, which the general hypothesis should preserve. This
has resulted in, as far as the author is aware, the most complete semantic characterisation
available of non-monotonic ILP using a bridge formula. It is proved that generalisation of
such a formula to a set of completed definitions is a sound method of generating normal
program hypotheses. In the course of establishing a completeness result for this latter
approach, the semantics of the supported consequences of a normal program are defined,
and the support tree method is presented and shown to be a sound and complete proof
procedure for supported consequences. Using these results, it is shown that, for function-free
programs, any correct hypothesis for which the examples are supported consequences
of the learned program can be derived via a normal connected theory.
the notion of a connected theory. A connected theory contains clauses that depend on
one another, either directly or via clauses in the background knowledge. Generalisation
of such a theory is proved to be a sound and complete method for learning definite ILP
hypotheses. The Induction on Failure (IOF) proof procedure, based on the connected
theory generalisation method, adds secondary examples into the hypothesis, and generates
auxiliary clauses to explain them. These concepts, novel to IOF, address the issues of
incompleteness present in previous definite ILP methods.
The concept of the connected theory is also applied to the non-monotonic, normal program
setting. Thus, the method of generalisation of a normal connected theory is presented.
Fundamental to this is the assertion that a partial non-monotonic hypothesis must include
both positive and negative information, which the general hypothesis should preserve. This
has resulted in, as far as the author is aware, the most complete semantic characterisation
available of non-monotonic ILP using a bridge formula. It is proved that generalisation of
such a formula to a set of completed definitions is a sound method of generating normal
program hypotheses. In the course of establishing a completeness result for this latter
approach, the semantics of the supported consequences of a normal program are defined,
and the support tree method is presented and shown to be a sound and complete proof
procedure for supported consequences. Using these results, it is shown that, for function-free
programs, any correct hypothesis for which the examples are supported consequences
of the learned program can be derived via a normal connected theory.
Date Issued
2011-10
Date Awarded
2012-08
Copyright Statement
Attribution NoDerivatives 4.0 International Licence (CC BY-ND)
Advisor
Broda, Krysia
Russo, Alessandro
Sponsor
Imperial College London
Publisher Department
Computing
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)