Inductive Logic Programming
ILP theory describes the inductive inference of logic programs from instances and background knowledge
ILP contributes to the practice of logic programming by providing tools that assist logic programmers to develop and verify programs
Model Theory of ILP
The background theory is a set of definite clauses
The negative evidence is derived implicitly, by making the closed world assumption (realized by the minimal Herbrand model)
The hypotheses are sets of general clauses expressible using the same alphabet as the background theory
A Generic ILP Algorithm
Combining Delete with Prune it is easy to obtain advanced search
Some frequently employed criteria require that a solution be found, or that it is unlikely that an adequate hypothesis can be obtained from the current queue
Proof Theory of ILP
θ -subsumes is the simplest model of deduction for ILP which regards clauses as sets of (positive and negative) literals
A clause c 1 θ -subsumes a clause c 2 if and only if there exists a substitution θ such that c 1 θ ⊆ c 2
c 1 is called a generalisation of c 2 (and c 2 a specialisation of c 1 ) under θ subsumption
θ -subsumes The θ subsumption inductive inference rule is:
Basic algorithm for CProgol:
Select an example to be generalized.
Build most-specific-clause. Construct the most specific clause that entails the example selected, and is within language restrictions provided. This is usually a definite clause with many literals, and is called the "bottom clause."
Find a clause more general than the bottom clause. This is done by searching for some subset of the literals in the bottom clause that has the "best" score.
Remove redundant examples. The clause with the best score is added to the current theory, and all examples made redundant are removed. Return to Step 1 unless all examples are covered.
Michalski’s train problem
Assume ten railway trains: five are travelling east and five are travelling west; each train comprises a locomotive pulling wagons; whether a particular train is travelling towards the east or towards the west is determined by some properties of that train
The learning task: determine what governs which kinds of trains are Eastbound and which kinds are Westbound
Michalski’s train problem can be viewed as a classification task: the aim is to generate a classifier (theory) which can classify unseen trains as either Eastbound or Westbound
The following knowledge about each car can be extracted: which train it is part of, its shape, how many wheels it has, whether it is open (i.e. has no roof) or closed, whether it is long or short, the shape of the things the car is loaded with. In addition, for each pair of connected wagons, knowledge of which one is in front of the other can be extracted.
Generate the hypotheses