Learning First-Order Logical Rules from Relational Data

92 concepts79 papers1 proposal

Most traditional machine learning algorithms expect data to arrive in a single, flat table where each row represents an independent instance and each column represents a fixed attribute. This tabular format belongs to the realm of propositional logic. However, real-world domains—such as molecular biology, social networks, computer protocols, and natural language syntax—are inherently relational and structured. Forcing these complex structures into a standard classifier requires a process called "flattening," which introduces severe limitations.

The Problem with Flattening Data

When you flatten a relational database or a graph into a single table, you destroy the native structural relationships between entities. As Hendrik Blockeel et al. point out in their work on environmental modeling, preserving data in its native relational format is essential for capturing complex dependencies that are otherwise lost during preprocessing [Simultaneous Prediction of Mulriple Chemical Parameters of River Water Quality with TILDE].

Flattening also creates practical engineering hurdles:

  • Data Sparseness: In natural language processing, representing context using flat attribute-value vectors leads to massive, sparse feature spaces. Lucia Specia demonstrates that modeling linguistic dependencies directly through relational logic avoids this sparseness by focusing on explicit structural relationships rather than fixed-length feature lists [A Hybrid Relational Approach for WSD - First Results].
  • Information Loss: In tasks like coreference resolution, entities can have a variable number of mentions. Xiaofeng Yang et al. observe that flattening these variable-length clusters into fixed-length vectors causes significant information loss, whereas a relational structure naturally accommodates arbitrary numbers of connections [An Entity-Mention Model for Coreference Resolution with Inductive Logic Programming].

The Solution: Algorithmic Lifting

To bypass these limitations, Inductive Logic Programming (ILP) and relational learning "lift" machine learning algorithms from propositional representations to first-order logic. As explained by Jonathan Baxter et al., logical lifting extends learning frameworks to operate over complex representations like first-order logic or Horn expressions, allowing models to reason within structured domains while maintaining formal theoretical foundations [Guest Editors' Introduction].

Propositional Logic (Flat)      --->   First-Order Logic (Lifted)
[Color=Red, Shape=Round]               ∃X,Y: color(X, red) ∧ connected(X, Y)

This paradigm does not require inventing entirely new learning theories from scratch. Instead, it focuses on relational algorithm upgrading. Manfred Jaeger et al. describe this as generalizing classical propositional algorithms to a relational level, enabling the reuse of established search and optimization techniques directly on structured data [Preface].

As Ivan Bratko et al. note, by replacing attribute-value representations with relational predicates, standard models like decision trees can be adapted to reason about objects and their interconnections [ILP turns 20 - Biography and future challenges]. This makes relational learning a powerful, expressive generalization of classical machine learning [Relational Learning and Inductive Logic Programming Made Easy Abstract of Tutorial].

How Upgraded Algorithms Work

To understand why lifting works, consider how a familiar model—the decision tree—is upgraded into a First-Order Logical Decision Tree.

In a standard decision tree, a node splits data based on a simple attribute check (e.g., Age > 30). In a first-order logical decision tree, developed by Hendrik Blockeel et al., the splitting criteria are replaced by first-order logic queries [Scaling Up Inductive Logic Programming by Learning from Interpretations]. A split node might query the data structure like this:

$$\exists Y : \text{parent}(X, Y) \land \text{profession}(Y, \text{accountant})$$

This allows the tree to branch based on complex relationships across multiple relational tables without ever flattening the data.

The learning process typically involves searching a hypothesis space of logical clauses to find rules that explain the data. For instance, Alexey Loginov et al. demonstrate how inductive learning algorithms can treat specific structural configurations as positive examples and others as negative examples, automatically searching for a logical formula that separates them [Abstraction Refinement via Inductive Learning].

This search can induce general rules, such as Horn clauses grounded in Herbrand semantics. Ole-Christoffer Granmo et al. show that learning these conditional dependencies directly creates sound, human-interpretable knowledge bases that are highly compact and robust to noise [A relational tsetlin machine with applications to natural language understanding].

Leveraging Background Knowledge and Interpretability

A major advantage of learning in first-order logic is the ability to seamlessly integrate prior domain knowledge into the learning process. Traditional models must learn patterns entirely from raw data vectors, but ILP systems can ingest "background knowledge" in the form of pre-defined logic predicates.

For example, the authors of [Learning Minesweeper with Multinational Learning] demonstrate that leveraging background knowledge predicates allows an inductive logic system to efficiently learn complex, multi-step game strategies.

Because the output of these systems consists of formal logic statements (such as if-then rules), the resulting models are inherently transparent and interpretable:

Key Foundational Work

Integrating Multiple Knowledge Representations and Learning Capabilities in an Expert System: The ADVISE System (1983) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_inductive_logic_programming_568800b8,
  title = {inductive logic programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inductive-logic-programming/rdr_568800b83e604d70a43bb2179ea82470},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_inductive_logic_programming_568800b8_v1,
  title = {inductive logic programming},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/inductive-logic-programming/rdr_568800b83e604d70a43bb2179ea82470/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake