Inductive Logic Programming

This part of the course describes Inductive Logic Programming (ILP) and its application to NLP.

Date: 26 October 2005

Assignment

(I adapted these from exercises given by Dimitar Kazakov on his Symbolic Learning of Natural Language module. Thanks to Dimitar.)

1. Grab these sentences, and this incomplete background knowledge file. Add the necessary
   • modes,
   • declarations,
   • settings (Tip: watch out for low default settings for i and clauselength.)
   • and background predicate definitions
   so that Aleph induces a single-clause theory which covers all positive examples. (There are no negative examples, and you don't need any).
2. Grab this data on past tense formation of English verbs. You are not expected to be able to get Aleph to induce an optimal theory, but you should be able to get a few reasonable rules. (Aleph is not the optimal choice for this sort of problem.) Here's a tip that might help you: examples are saved internally in Aleph using the predicate example/3 so that to get hold of positive example number, say, 23, you call example(23,pos,X). You somehow need to push Aleph into realising that past/2 is a function mapping the 1st argument to the second. Adding lots of negative examples to this effect is a rather yucky solution.

Project suggestions

Biomedical information extraction

Have a go at the Genic Interaction Extraction Challenge task. This requires you to induce rules to extract protein/gene interactions. The good news is that the training data is annotated and in a logical format, just right for ILP! This task was associated with the recent Learning Language in Logic (LLL05) workshop. You can see how other people have got on by reading the proceedings.

Grammar induction

The grammar induction software you used in Lab Session 2 could be developed in many ways. Developments such as this could involve a number of projects.

1. The search strategy is currently rather exhaustive, something more heuristic is probably needed to scale it up.
2. It will probably be beneficial to add a probabilistic element.
3. The constraints on potential grammar rules could be altered.
4. It would be good to do more work on inducing lexical entries for unknown words.
5. Develop an interactive version so that rule candidates for a particular sentence can be presented for an expert to accept/reject/tweak.
6. Use WSJ bracketings to constrain hypotheses.

CoNNL shared tasks

Of course, there are any number of natural language learning tasks where it might be interesting to apply ILP (most usually `vanilla' ILP such as encountered in Lab Session 1). For example, why not have a look at the CoNLL Shared Tasks. (Go to the bottom of the page).

Resources

• The Aleph algorithm and manual
• Yap Prolog
• Brief manual for Pulman/Cussens grammar induction software

Literature

• Logic, Programming and Prolog (2ed) by Ulf Nilsson and Jan Małuszyński. Previously published by John Wiley & Sons Ltd.
• Sašo Džeroski, James Cussens, and Suresh Manandhar. An introduction to inductive logic programming and learning language in logic. In James Cussens and Sašo Džeroski, editors, Learning Language in Logic, volume 1925 of LNAI. Springer, 2000. This chapter introduces Inductive Logic Programming (ILP) and Learning Language in Logic (LLL). No previous knowledge of logic programming, ILP or LLL is assumed. Elementary topics are covered and more advanced topics are discussed. For example, in the ILP section we discuss subsumption, inverse resolution, least general generalisation, relative least general generalisation, inverse entailment, saturation, refinement and abduction. We conclude with an overview of this volume and pointers to future work
• Stephen Pulman and James Cussens. Grammar learning using Inductive Logic Programming. Oxford University Working Papers in Linguistics, Philology and Phonetics, 6:31-45, May 2001 This paper gives a brief introduction to a particular machine learning method known as inductive logic programming. It is argued that this method, unlike many current statistically based machine learning methods, implies a view of grammar learning that bears close affinity to the views linguists have of the logical problem of language acquisition. Two experiments in grammar learning using this technique are described, using a unification grammar formalism, and positive-only data.
• Learning Semantic Lexicons from a Part-of-Speech and Semantically Tagged Corpus Using Inductive Logic Programming. Vincent Claveau, Pascale Sébillot, Cécile Fabre, Pierrette Bouillon; Journal of Machine Learning Research 4(Aug):493-525, 2003. [abs][pdf][ps.gz][ps]

Back to course page

Last modified: Mon Oct 24 09:03:34 BST 2005