Logic Programming

Inductive Logic Programming

Inductive logic programming (ILP) is a logical approach to machine learning. From a database of facts and expected results, which are divided into positive and negative examples, an ILP system tries to derive a logic program that proves all the positive and none of the negative examples. More formally, ILP systems develop predicate descriptions from examples and background knowledge. The examples, background knowledge and final descriptions are all described as logic programs.

One search strategy for ILP systems is to invert rules of deduction (resolution) and therefore induce hypotheses which may solve the learning problem. The theory of ILP is based on proof theory and model theory for the first order predicate calculus. Inductive hypothesis formation is characterised by techniques including inverse resolution, relative least general generalisations, inverse implication and inverse entailment.

ILP systems have been applied to a number of problem domains. Many applications benefit from the relational descriptions generated by the ILP systems. Their ability to accommodate background knowledge is also fundamental. ILP is particularly useful in bio-informatics and natural language processing.

Here are some of the implementations of ILP:

  • The Duce system uses six inductive inference rules, of which, four are concerned with definite clause propositional logic.
  • CIGOL inverts resolution of clauses in first order predicate logic.
  • Golem is based on the construction of relative least general generalisations.
  • Progol implements the theoretical framework of inverting entailment.