CHILLIN is an ILP algorithm
combining elements of top-down and bottom-up induction methods.
CHILLIN's input consists of sets of ground facts representing
positive and negative examples, and a set of background predicates
defined by definite clauses. Examples may contain functors.
Basically, CHILLIN tries to construct a small, simple theory
covering the positive, but not the negative examples by repeatedly
compacting its current version of the program. Compactness is
measured as the syntactic size of the theory.
The algorithm starts with a most specific theory, namely the set of
all positive examples. Then it generalises the current theory, aiming
to find a generalisation which allows to remove a maximum number of
clauses from the theory while all positive examples remain provable.
Similar to GOLEM's approach, the generalisation algorithm finds
a random sampling of pairs of clauses in the current program. These
pairs are generalised by constructing their
least-general-generalisations under theta-subsumption. If a
generalisation covers negative examples, it is specialised by adding
antecedents using a FOIL-like algorithm. If the specialisation
with background predicates is not sufficient for preventing negative
examples from being covered, CHILLIN tries to invent new
predicates for further specialisation of the clause. At each step,
CHILLIN considers a number of possible generalisations and
implements the one that best compresses the theory.
CHILLIN is able to learn recursive predicates. It avoids
generating theories leading to endless recursion by imposing syntactic
restrictions on recursive predicates. However, CHILLIN may learn
recursive predicates covering negative examples.
CHILLIN is the inductive component of the parser-acquisition system
CHILL
which generates natural language parsers by
training over
corpora of parsed text. Within CHILL, CHILLIN induces search
control rules within a logic program that implements a shift-reduce parser.
References
J.M. Zelle and R.J. Mooney.
Learning to parse database queries using inductive logic programming.
In Proceedings of the 14th National Conference on Artificial
Intelligence, pages 1050-1055. AAAI Press/MIT Press, 1996.
J.M. Zelle, R.J. Mooney, and J.B. Konvisser.
Combining top-down and bottom-up techniques in inductive logic
programming.
In W.W. Cohen and H. Hirsh, editors, Proceedings of the 11th
International Conference on Machine Learning, pages 343-351. Morgan
Kaufmann, 1994.