Bottom-Up Symbolic Rule Induction

23 concepts22 papers1 proposal

Traditional machine learning often searches a massive space of possible models or rules from the top down, pruning away hypotheses that contradict the data. However, this approach can be computationally prohibitive and highly sensitive to noise.

An alternative paradigm turns this process on its head: bottom-up inductive generalization. Instead of starting with a broad hypothesis space, we start directly with the observed data points—specific ground facts—and systematically abstract them into general rules.

As Ling demonstrated in Inductive Learning from Good Examples, providing a small set of highly descriptive examples can transform computationally hard learning problems into efficient, polynomial-time tasks. By building logic programs directly from instances rather than pruning a predefined hypothesis space, bottom-up learning becomes inherently more robust against over-generalization noise.

The Abstraction Pipeline: From Ground Facts to Rule Schemata

How do we move from a concrete observation to an abstract rule? The process relies on a sequence of symbolic transformation operators that systematically strip away specific details while preserving relational structures.

First, individual instances or observations are converted into their most specific descriptive formulas, often called "bottom clauses." For example, in Inductive Logic Programming (ILP), Specia et al. in Learning Expressive Models for Word Sense Disambiguation show how constructing highly specific bottom clauses for individual training examples serves as the foundation for inducing human-readable relational rules.

Once these bottom clauses are established, the system applies abstraction operators to broaden their scope. The most fundamental operator is variable substitution: replacing concrete constants with variables. As de Souza Mota et al. explored in Inductive Learning in Shared Neural Multi-Spaces, transforming specific ground instances into universal logical rules via variable replacement allows an agent to derive broad symbolic patterns from a remarkably small set of observations.

Beyond simple variable substitution, more advanced structural transformations like folding and subsumption are used to compress and generalize rules. In the context of learning Assumption-Based Argumentation (ABA) frameworks, De Angelis et al. in ABA Learning via ASP and Learning Brave Assumption-Based Argumentation Frameworks via ASP demonstrate how adding specific ground facts to cover positive examples and subsequently applying folding operators shifts the model from memorizing training data to discovering underlying logical principles. Similarly, Toni et al. in Learning Assumption-based Argumentation Frameworks show that replacing specific constants with higher-level concepts from background knowledge ensures logical consistency across a wider range of unseen scenarios.

Inverting Deduction: Inverse Unification and Resolution

To understand why bottom-up induction works, it helps to look at it as the exact inverse of standard logical deduction. In deduction, we apply a general rule to a specific fact to derive a conclusion:

$$\text{Fact} \land (\text{Fact} \rightarrow \text{Conclusion}) \implies \text{Conclusion}$$

In bottom-up induction, we work backward: given the conclusion and our background knowledge, we infer the rule. This mechanism is formalized through techniques like inverse resolution and inverse unification.

As outlined by Bratko et al. in ILP turns 20 - Biography and future challenges, inverse resolution reverses deductive inference steps to find the most specific generalizations that explain a set of observations. When dealing with dynamic or relational data, inverse unification acts as the primary generalization engine.

Work by Tenorio et al. in Learning about Actions and Events in Shared NeMuS and Schramm et al. in Category-based Inductive Learning in Shared NeMuS demonstrates how inverse unification analyzes specific instances and works backward to identify a common logical structure. By reversing the unification process, the system synthesizes general predicates that encompass positive examples while systematically excluding negative ones.

Bounding Generalization via the Least General Generalization

If the goal is to generalize, why not make the rules as broad as possible? The danger of unconstrained generalization is that it quickly leads to over-generalization, where the induced rules become trivial, noisy, or incorrect. To prevent this, bottom-up induction seeks the Least General Generalization (LGG)—the lowest common denominator or closest common ancestor that covers the examples.

   [Over-Generalized Rule] (Too broad: "Any object can be stacked on any object")
             ^
             |
   [Least General Generalization (LGG)] (Just right: "Flat objects can be stacked on flat objects")
        /          \
  [Instance A]   [Instance B] (Specific video examples of stacking blocks)

In Specific-to-General Learning for Temporal Events with Application to Learning Event Definitions from Video, Fern et al. show how finding the LGG enables the acquisition of complex relational concepts (like "stacking" objects) from positive data alone, without requiring negative examples.

This principle is highly versatile across domains. For instance, Yang et al. in Learning Symbolic Rules for Reasoning in Quasi-Natural Language apply LGG to natural language sentences, finding the lowest common ancestor between two specific sentence examples to automatically synthesize general logical templates without manual engineering. Furthermore, Sakama et al. in Brave induction: a logical framework for learning from incomplete information combine inverse entailment with Least Generalization under Subsumption to derive concise, meaningful hypotheses even when the underlying information is incomplete.

Data Efficiency and Explainability in Practice

Because bottom-up rule induction anchors its search space in actual observations, it possesses two massive advantages over deep learning: extreme data efficiency and native explainability.

Instead of requiring thousands of statistical examples, agents can learn from a single successful instance. As highlighted by Cazenave in Jacques Pitrat, l'Intelligence Artificielle et les Jeux, explanation-based generalization allows an agent to use the underlying rules of a system to reason about a successful outcome and transform a single sequence of actions into reusable first-order logic rules. This parsimonious approach is highly practical for real-world robotics; Baumann et al. in Intuitive teaching of medical device operation to clinical assistance robots demonstrate how encoding observed state changes from a few human demonstrations into symbolic logic rules allows clinical robots to generalize functional behaviors safely.

Finally, because the output of bottom-up induction consists of explicit logical constraints (such as Horn clauses), the resulting models are fully transparent. Kotonya in Explainable Automated Fact-Checking: A Survey notes that mining logical triples and Horn rules from knowledge graphs provides structured, human-readable justifications for automated verdicts. Similarly, Shirai et al. in Rule-Based Link Prediction over Event-Related Causal Knowledge in Wikidata show that bottom-up Horn rule induction successfully extracts interpretable symbolic patterns from large knowledge graphs, ensuring that the path from specific data points to abstract predictions remains entirely auditable.

Key Foundational Work

Inductive Learning from Good Examples (1991) — contributed 3 concept elements to this direction.
Automatic Generation of Object Class Descriptions Using Symbolic Learning Techniques (1991) — contributed 1 concept elements to this direction.
Learning Temporal, Relational, Force-Dynamic Event Definitions from Video (2002) — 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_symbolic_rule_induction_befc8bc0,
  title = {symbolic rule induction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-rule-induction/rdr_befc8bc0ff534d84b2660227be12f40d},
  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_symbolic_rule_induction_befc8bc0_v1,
  title = {symbolic rule induction},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/symbolic-rule-induction/rdr_befc8bc0ff534d84b2660227be12f40d/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