Inductive Logic Programming

Inductive Logic Programming

Inductive Logic Programming (ILP) combines logic programming with machine learning. It uses logic both to derive conclusions from rules (deduction) and to infer rules from examples (induction). Its central aim is to learn logic-programming clauses that explain observed examples while making use of existing background knowledge.

Core Setup and Objective

An ILP task includes:

• Positive and negative examples, expressed in a logic-programming language.
• A domain theory or background knowledge, expressed in the same formalism.
• A hypothesis language, which specifies the kinds of clauses the learner is allowed to construct.

The learner searches for a hypothesis that covers the positive examples and does not cover the negative examples, taking the background theory into account. Because examples, background knowledge, and hypotheses share a representation, ILP can handle structured data and relationships among multiple entities.

Generalization, Specialization, and Search

ILP treats learning as a search through a space of possible hypotheses:

• Specialization moves from more general hypotheses toward more specific ones. This supports a top-down search, typically starting from a very general hypothesis. The lecture identifies θ-subsumption as a common way of organizing this relation.
• Generalization moves from specific hypotheses toward more general ones. This supports a bottom-up search, typically starting from facts or examples. Inverse resolution is given as a standard generalization operation.

Under the stated conditions, the hypothesis space can be organized as a lattice, with least upper bounds and greatest lower bounds for pairs of clauses. The lecturer presents induction as an attempt to reverse deduction where possible.

Generic ILP Algorithm

A general procedure described in the lecture is:

1. Choose a search direction.
   • For top-down search, initialize with a very general hypothesis.
   • For bottom-up search, initialize from the examples or facts.
2. Choose search operations.
   • Use specialization—often θ-subsumption—for top-down search.
   • Use generalization—often inverse resolution—for bottom-up search.
3. Select a current hypothesis from the set of candidates.
4. Expand it by applying the chosen inference operations to generate new hypotheses.
5. Evaluate and prune candidates.
   • If a hypothesis is too specific because it fails to cover positive examples, further specializations of it are not useful.
   • If it is too general because it covers negative examples, further generalizations are not useful.
   • Redundant or irrelevant candidates may also be removed.
6. Repeat until a stopping condition is met. The search method—such as depth-first, breadth-first, or best-first—depends partly on how candidates are selected and pruned.

When a Hypothesis Is Considered Correct

The lecture gives four criteria for a correct hypothesis:

• Sufficiency: It covers all available positive examples.
• Necessity: Removing it would leave some positive examples uncovered by the remaining hypotheses.
• Consistency: It does not contradict the domain theory.
• Strong consistency: It does not cover negative examples.

Finding a hypothesis that meets these conditions can serve as a termination condition.

Examples and Applications

• A bottom-up example starts with facts such as an individual being male and being a parent, then generalizes toward a rule expressing that a father is male and a parent.
• A bird example illustrates the hypothesis space using birds such as penguins, sparrows, and eagles, plus background facts about properties such as laying eggs, flying, and having talons. It shows how top-down and bottom-up methods traverse the hypothesis space in opposite directions.

The lecture names FOIL, Progol, Golem, and Marvin as ILP systems. It notes that systems use different search strategies, including hill climbing and best-first search, though the subtitles do not clearly establish every system-to-strategy pairing.

ILP is especially suited to domains with complex structures and relationships. The lecture highlights natural-language processing and bioinformatics as important application areas. Some ILP systems can also invent new predicates and add them to the theory.

Speakers and Sources Featured

• Speaker: One lecturer, whose name is not given in the subtitles.
• Source: NPTEL-NOC IITM, Machine Learning, Week 5, Lecture 3.