CHILLIN

System:CHILLIN
Version:1.0 Alpha
Pointers: http://www.cs.utexas.edu/users/ml/chillin.html
Code:Quintus Prolog
References:Zelle and Mooney 1996

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

  1. 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.
  2. 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.


back to index