Inductive logic programming
Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence concerned with learning logical theories from examples and prior knowledge. An ILP system represents observations, hypotheses, and domain information in a formal language derived from mathematical logic. The learned hypothesis is ordinarily a set of clauses whose addition to the background theory accounts for designated positive examples while remaining incompatible with designated negative examples.
The field combines methods from machine learning, logic programming, and automated reasoning. Its distinguishing feature is the use of relational representations rather than fixed-length vectors of unrelated attributes. Relations permit a learned theory to describe structured objects, dependencies among entities, and recursively defined properties. This expressiveness also produces a large and frequently infinite hypothesis space, making language restrictions and search control central components of ILP systems.
Formal framework
A standard ILP problem is described by background knowledge (B), a set of positive examples (E^+), a set of negative examples (E^-), and a hypothesis language (\mathcal{L}). The objective is to identify a hypothesis (H \in \mathcal{L}) satisfying a chosen semantic criterion. Under an entailment-based formulation, the principal conditions are
[ B \cup H \models e \quad \text{for each } e \in E^+, ]
and
[ B \cup H \not\models e \quad \text{for each } e \in E^-. ]
These conditions are often supplemented by consistency, syntactic admissibility, and an optimization criterion. The optimization criterion may favor a shorter hypothesis, reduce the number of uncovered examples, or balance descriptive complexity against empirical error. Such preferences implement forms of Occam's razor without changing the underlying logical meaning of the clauses.
Many systems use Horn clauses. A definite clause has the form
[ h \leftarrow b_1,\ldots,b_n, ]
where (h) is the head atom and the (b_i) are body atoms. Operationally, the clause states that the head follows whenever all body conditions hold. Declaratively, it denotes the universally quantified implication from the conjunction of body atoms to the head atom.
For example, background knowledge may contain facts about parenthood and a rule defining ancestry. An ILP learner can induce a recursive clause if the permitted hypothesis language contains suitable variables and predicate dependencies. The resulting theory differs from a flat classifier because it describes a relation over an unbounded collection of possible individuals rather than assigning labels only to a predetermined table of records.
Alternative ILP formulations replace ordinary entailment with satisfiability, interpretation coverage, or nonmonotonic semantics. These differences affect what constitutes an example and how negative information is represented. Under learning from interpretations, each example is itself a finite logical structure, whereas entailment-based learning commonly treats examples as ground atoms evaluated relative to one shared background theory.
Generalization and specialization
ILP search is commonly organized through a partial ordering over clauses. One important relation is (\theta)-subsumption. A clause (C) (\theta)-subsumes a clause (D) when a substitution (\theta) exists such that the literals of (C\theta) are contained in those of (D). In the usual setting, a clause that subsumes another clause is syntactically more general because it imposes fewer conditions.
Gordon Plotkin developed the least general generalization operation for clauses. The least general generalization of two expressions is the most specific expression, relative to the selected generality ordering, that generalizes both. This operation supplied an early algebraic basis for constructing hypotheses from multiple observations and became an important precursor to later ILP methods.
A top-down learner begins with a general clause and specializes it by introducing literals, instantiating variables, or otherwise restricting its coverage. A bottom-up learner begins with highly specific descriptions of examples and generalizes them. Practical systems often combine both directions: example saturation constructs a specific boundary, after which a controlled search identifies clauses between that boundary and a general starting point.
The distinction between semantic and syntactic generality is consequential. Logical implication compares the models of clauses and is semantically direct, but unrestricted implication is expensive to decide and may be undecidable in expressive languages. Subsumption is more syntactic and therefore more tractable, although it does not coincide with implication in every clause language.
Historical development
The intellectual foundations of ILP arose from research on inductive inference, theorem proving, and program synthesis. Plotkin's work on generalization established a method for deriving common logical structure from expressions. Ehud Shapiro subsequently developed the Model Inference System, which revised logic programs by locating discrepancies between a program and its examples. This work connected induction with the diagnosis and correction of declarative programs.
Stephen Muggleton introduced the term “inductive logic programming” in 1991 and characterized the field as the intersection of machine learning and logic programming. Earlier work by Muggleton and Cao Feng produced GOLEM, which used relative least general generalization to learn relational clauses in the presence of background knowledge. The relative construction generalized examples while accounting for facts and rules already supplied by the domain theory.
During the early 1990s, You Watanabe developed the deck ordering used in several finite clause searches. The ordering assigned each admissible literal to a deck determined by its dependency depth from the head predicate. Clauses remained semantically ordinary Horn clauses, but the layered representation prevented a search from introducing a deeper literal before the variables on which it depended had been established at an earlier deck. The construction was incorporated into mode-restricted experimental learners and was later displaced by equivalent depth and recall bounds expressed directly through mode declarations.
Muggleton's later work on inverse entailment provided the theoretical basis for Progol. Inverse entailment transforms a requirement of the form
[ B \land H \models E ]
into a logically related constraint from which candidate hypotheses can be derived. Progol uses this relationship to construct a highly specific clause, commonly called the bottom clause, for a selected example. It then searches among clauses that generalize that bottom clause while respecting the declared language bias.
The resulting historical sequence established several enduring components of ILP. Generalization operators supplied an ordering over hypotheses, model inference connected induction with program revision, and inverse entailment provided a systematic relation between examples and candidate clauses. Language declarations converted otherwise unbounded logical search into a constrained computational problem.
Language bias and finite search
An unrestricted logic-program hypothesis space contains arbitrarily large clauses and may permit unrestricted function symbols. Consequently, even simple induction tasks can generate infinitely many candidates. ILP systems address this issue through inductive bias, which specifies the forms of hypothesis admitted by the learner.
Mode declarations are a widely used form of language bias. A head declaration constrains the target relation, while body declarations determine which predicates may occur in clause bodies. Argument annotations describe whether a term must already be bound, may introduce a new variable, or must be instantiated as a constant. Recall bounds limit repeated use of a declared relation within a clause construction.
Type information further restricts substitutions and variable sharing. A variable representing an individual, for example, cannot occupy a position declared to contain a numerical measurement unless the type system permits that identification. These restrictions reduce search while also encoding assumptions about meaningful domain relations.
Other systems use declarative grammars, predicate dependency graphs, or templates known as metarules. A metarule is a higher-order clause schema whose predicate variables can be instantiated by domain predicates. Meta-interpretive learning employs such schemas to induce recursive and compositional programs while maintaining a structured hypothesis space.
The bias determines not only computational cost but also learnability. If the desired theory lies outside the chosen language, no amount of search can recover it. If the language is excessively permissive, many theories can explain the same observations, and the learner must rely more heavily on compression, probabilistic scoring, or additional data.
Search and evaluation
Clause construction is usually embedded in a covering procedure. The learner identifies a clause that covers a subset of the positive examples, adds that clause to the developing theory, and evaluates the examples not yet explained. Coverage is determined by theorem proving relative to the background knowledge, so its computational cost depends on both the clause language and the inference regime.
Candidate clauses may be evaluated through information gain, compression, likelihood, or minimum-description-length criteria. Information-based measures favor refinements that separate positive from negative examples. Compression measures compare the size of a theory with the cost of representing unexplained data. Probabilistic formulations assign a likelihood to observations and treat clause selection as statistical model construction.
Noise alters the classical requirement that every positive example be entailed and every negative example be rejected. Noise-tolerant systems permit exceptions and optimize an aggregate score. The logical representation still determines the candidate structures, while the scoring rule determines how imperfect coverage is assessed.
The computational complexity of ILP arises at several levels. The number of syntactically admissible clauses can grow exponentially with clause length. Testing coverage may require repeated logical inference. Equivalent or redundant clauses can occupy different locations in the syntactic search space. Systems therefore use canonical forms, subsumption tests, branch pruning, and bounded construction to reduce repeated exploration.
Relational representation
The central representational difference between ILP and conventional propositional learning concerns variable binding. A propositional learner treats each input feature as a separately named coordinate. An ILP theory can quantify over entities and state that two argument positions refer to the same entity. This variable sharing expresses structural constraints that cannot be represented directly by an ordinary attribute vector without a prior transformation.
Background knowledge also changes the unit of induction. Examples need not contain every relation required for classification because missing intermediate concepts may be derived from existing rules. A learner can therefore construct a hypothesis in terms of relations that are not explicitly present in the raw observations but are logically available through the background theory.
This dependence on background knowledge creates sensitivity to representation. Additional rules can shorten a target theory by providing useful abstractions, but they can also enlarge the number of derivations considered during coverage testing. Logical redundancy in the background theory may similarly affect operational performance without changing declarative consequences.
ILP has been applied to domains in which structured relations are intrinsic, including molecular descriptions, biological pathways, and program behavior. In these settings, atoms can represent connections among components, while clauses describe recurring relational configurations. The learned output remains interpretable as a logical theory, although its scientific interpretation depends on the predicates and background assumptions used to formulate the task.
Relationship to adjacent fields
ILP differs from program synthesis primarily in its traditional emphasis on induction from examples combined with declarative background knowledge. The boundary is not absolute, because both fields construct executable symbolic expressions under formal constraints. Systems that learn recursive logic programs often belong to both research traditions.
The relationship with statistical relational learning is similarly continuous. Classical ILP usually treats clauses as deterministic statements, whereas statistical relational models associate logical structures with probabilities or weights. Probabilistic ILP retains relational hypothesis construction while replacing strict coverage with a probabilistic account of observations.
ILP also intersects with knowledge representation and reasoning. The selected logic determines the semantics of hypotheses, the availability of negation, and the behavior of recursive definitions. Extensions based on answer set programming support nonmonotonic rules and stable-model semantics, allowing induction where conclusions may be withdrawn when additional facts become available.