Inductive Logic Programming (ILP) | LGG, Inverse Resolution & Predicate Invention Tutorial

ILP Overview and Goals

Inductive Logic Programming (ILP) is the advanced form of first-order rule learning. Its goal is to comprehensively learn first-order rules (Horn clauses) and support predicate invention—automatically discovering new predicates that capture implicit relationships in the data.

Key Capabilities

• Complete rule learning: Learns full first-order Horn clauses
• Predicate invention: Discovers new predicates not in background knowledge
• Background knowledge integration: Incorporates existing domain knowledge
• Complex relationship modeling: Handles multi-entity relationships

Minimum General Generalization (LGG)

LGG generalizes two specific rules into the most general rule that covers both, making minimal changes to preserve essential information.

Core Idea

Given two specific rules $r_1$ and $r_2$ , find the most general rule $r_{\text{LGG}}$ such that:

• $r_{\text{LGG}}$ covers all examples covered by $r_1$ and $r_2$
• $r_{\text{LGG}}$ is the most general (least specific) such rule
• Changes from $r_1$ and $r_2$ are minimal

LGG Algorithm Steps

1. Find common predicates: Identify predicates that appear in both rules (with same predicate name)
2. For each common predicate:
- • Recursively examine arguments (terms in parentheses)
- • If arguments are identical, keep them as-is
- • If arguments differ, replace with a new variable
3. Remove non-common predicates: Delete predicates that appear in only one rule
4. Result: The LGG rule contains only common predicates with generalized arguments

LGG Example

Rule 1:

better(1,10) ← root_more_curled(1,10) ∧ sound_more_deep(1,10)

Rule 2:

better(1,15) ← root_more_curled(1,15) ∧ navel_more_concave(1,15)

LGG Result:

better(1,Y) ← root_more_curled(1,Y)

Common predicate: $\text{root\_more\_curled}$ . Different arguments: $10$ and $15$ → replaced with variable $Y$ . Non-common predicates removed.

Inverse Resolution

Resolution is a deductive inference rule (from general to specific). Inverse resolution is the reverse—an inductive inference rule (from specific to general) that can invent new predicates to simplify rule structures.

Unification Concepts

Substitution

A substitution $\theta = \{t_1/v_1, t_2/v_2, \ldots\}$ replaces variables $v_i$ with terms $t_i$ .

Example: $\theta = \{1/X, 2/Y\}$ replaces $X$ with $1$ and $Y$ with $2$ .

Unification

Unification finds a substitution that makes two expressions equal. $A = \text{color\_deeper}(1, X)$ and $B = \text{color\_deeper}(Y, 2)$ unify with $\theta = \{2/X, 1/Y\}$ .

Most General Unifier (MGU)

The MGU is the most general substitution that unifies two expressions. All other unifiers can be derived from the MGU.

Four Complete Inverse Resolution Operations

These operations enable predicate invention and rule generalization:

1. Absorption

\frac{p \leftarrow A \land B; \quad q \leftarrow A}{p \leftarrow q \land B; \quad q \leftarrow A}

Introduces new predicate $q$ to factor out common subexpression $A$ .

2. Identification

\frac{p \leftarrow A \land B; \quad p \leftarrow A \land q}{q \leftarrow B; \quad p \leftarrow A \land q}

Discovers that $q$ is equivalent to $B$ .

3. Intra-Construction

\frac{p \leftarrow A \land B; \quad p \leftarrow A \land C}{q \leftarrow B; \quad p \leftarrow A \land q; \quad q \leftarrow C}

Invents predicate $q$ to represent common pattern in $B$ and $C$ .

4. Inter-Construction

\frac{p \leftarrow A \land B; \quad q \leftarrow A \land C}{p \leftarrow r \land B; \quad r \leftarrow A; \quad q \leftarrow r \land C}

Invents predicate $r$ to factor out common subexpression $A$ .

Predicate Invention: Core Advantage

The most powerful feature of ILP is predicate invention—automatically discovering new predicates that capture implicit patterns in the data, making rules more concise and generalizable.

Example: Predicate Invention

Given rules:

\text{better}(X, Y) \leftarrow \text{color\_deeper}(X, Y) \land \text{root\_more\_curled}(X, Y)

\text{better}(X, Y) \leftarrow \text{color\_deeper}(X, Y) \land \text{navel\_more\_concave}(X, Y)

ILP can invent new predicate $\text{superior}(X, Y)$ :

\text{superior}(X, Y) \leftarrow \text{root\_more\_curled}(X, Y)

\text{superior}(X, Y) \leftarrow \text{navel\_more\_concave}(X, Y)

\text{better}(X, Y) \leftarrow \text{color\_deeper}(X, Y) \land \text{superior}(X, Y)

The invented predicate $\text{superior}$ captures the common pattern, making the rule set more concise and interpretable.

Bioinformatics Application Example

Apply ILP to discover protein-protein interaction patterns. Learn rules predicting when two proteins interact based on their properties and relationships.

Protein Interaction Rules

Background Knowledge:

• $\text{located\_in}(P, C)$ : Protein P is located in cellular component C
• $\text{has\_function}(P, F)$ : Protein P has function F
• $\text{similar\_sequence}(P1, P2)$ : Proteins P1 and P2 have similar sequences
• $\text{interacts}(P1, P2)$ : Proteins P1 and P2 interact (target predicate)

Learned Rule:

\text{interacts}(P1, P2) \leftarrow \text{located\_in}(P1, C) \land \text{located\_in}(P2, C) \land \text{has\_function}(P1, F) \land \text{has\_function}(P2, F)

Rule states: "If two proteins are in the same cellular component AND have the same function, then they interact."

With Predicate Invention:

ILP invents predicate $\text{co\_localized}(P1, P2)$ :

\text{co\_localized}(P1, P2) \leftarrow \text{located\_in}(P1, C) \land \text{located\_in}(P2, C)

\text{interacts}(P1, P2) \leftarrow \text{co\_localized}(P1, P2) \land \text{has\_function}(P1, F) \land \text{has\_function}(P2, F)

The invented predicate $\text{co\_localized}$ captures the co-location pattern, making the rule more concise and reusable.

ILP Advantage:

ILP discovers meaningful biological patterns and invents predicates that represent biological concepts (co-localization), enabling knowledge discovery that goes beyond simple pattern matching.

Advantages and Limitations

Advantages

• Predicate invention: Discovers implicit relationships
• Knowledge discovery: Reveals hidden patterns in data
• Concise rules: Invented predicates simplify rule structures
• Background knowledge: Integrates domain expertise
• Comprehensive learning: Learns complete Horn clauses

Limitations

• High complexity: Computationally expensive
• Data quality sensitive: Requires clean, consistent data
• Difficult to engineer: Hard to implement and tune
• Limited scalability: May not scale to very large datasets
• Requires expertise: Needs domain knowledge for predicates