Tractable Induction and Classification in First Order Logic Via Stochastic Matching

Michèle Sebag, Céline Rouveirol

Abstract: Learning in first-order logic (FOL) languages suffers from a specific difficulty: both induction and classification are potentially exponential in the size of hypotheses. This difficulty is usually dealt with by limiting the size of hypotheses, via either syntactic restrictions or search strategies. This paper is concerned with polynomial induction and use of FOL hypotheses with no size restrictions. This is done via stochastic matching: instead of exhaustively exploring the set of matchings between any example and any short candidate hypothesis, one stochastically explores the set of matchings between any example and any candidate hypothesis. The user sets the number of matching samples to consider and thereby controls the cost of induction and classification. Experiments on a real-world problem pertaining to organic chemistry fully demonstrate the potentialities of the approach regarding both predictive accuracy and computational cost.

The Bottleneck of First-Order Logic

In machine learning, First-Order Logic (FOL) is a powerful tool for describing complex, relational data, such as the molecular structure of chemicals where multiple atoms and bonds interact. Learning these rules, a field known as Inductive Logic Programming (ILP), has historically been hampered by a massive computational bottleneck: the "matching" step.

If a learning algorithm proposes a rule with several variables and tests it against a complex example (e.g., a molecule with 40 atoms), the number of possible ways to map the rule to the example scales exponentially. Traditional ILP systems like FOIL or PROGOL manage this by strictly limiting the length and complexity of the hypotheses they can learn. This paper introduces STILL (Stochastic Inductive Learning), an algorithm designed to learn unrestricted, complex FOL rules in polynomial time.

Methodology: STILL and Stochastic Matching

To bypass the exponential matching problem, STILL relies on two primary innovations:

  1. Disjunctive Version Space (DiVS): Unlike traditional Version Spaces that struggle with noise or disjunctive concepts, DiVS represents hypotheses as a conjunction of disjunctions. This allows it to build a space of all consistent hypotheses that cover at least one training example while discriminating against counter-examples.
  2. Stochastic Matching: This is the core novelty. Rather than exhaustively checking every possible mapping between an example and a counter-example to find discriminative features, STILL randomly samples a user-defined number of mappings ($K$).

By sampling, the algorithm's complexity becomes linear with respect to the number of samples rather than exponential with respect to hypothesis size. For classification, STILL employs a $k$-nearest neighbor approach, where a new instance is classified based on a majority vote of training examples whose hypotheses cover it, again verified via stochastic sampling.

Experimental Evaluation

The algorithm was evaluated on the Mutagenesis dataset, a standard benchmark in relational learning. The goal is to predict the mutagenic activity of nitroaromatic molecules. The dataset provides highly relational FOL descriptions including atoms, bonds, and chemical structures.

Key Results and Comparative Performance

STILL achieved state-of-the-art predictive accuracy while offering significant computational speedups. Using basic random sampling, the algorithm reached 93.3% accuracy, outperforming prominent baselines such as PROGOL (88%), FOIL (86%), and standard neural networks (89%).

Comparison of predictive accuracy across standard machine learning and ILP algorithms.

Beyond accuracy, the efficiency gains were staggering. While traditional systems like PROGOL can take between 11 to 32 hours to process this dataset, STILL completed the task in under two minutes—as low as 27 seconds in specific configurations. Furthermore, the experiments demonstrated "graceful degradation": as the number of stochastic samples is reduced to save compute time, accuracy decreases smoothly rather than failing catastrophically.

Performance of Advanced (a) and Basic (b) Stochastic Matching (SM) across different parameter settings.

Insights and Future Work

One of the most surprising findings was the "Smart Sampling Paradox." The authors tested an "Advanced" sampling mechanism that used chemical domain knowledge to match similar atoms. However, this did not significantly outperform "Basic" random sampling. Random sampling forced the algorithm to explore a wider, more diverse array of structural differences, whereas the heuristic approach focused too narrowly on minor differences, missing broader discriminative features.

While STILL offers a powerful way to handle unrestricted complexity, it does face a trade-off in interpretability. Because it produces a massive, redundant list of constraints, it lacks the clean "if-then" readability of traditional decision trees. Future work will focus on developing a formal PAC (Probably Approximately Correct) learning model to mathematically define the relationship between the number of random samples and the statistical probability of finding a correct hypothesis.

Summary updated

Abstract

Learning in first-order logic (FOL) languages suffers from a specific difficulty: both induction and classification are potentially exponential in the size of hypotheses. This difficulty is usually dealt with by limiting the size of hypotheses, via either syntactic restrictions or search strategies. This paper is concerned with polynomial induction and use of FOL hypotheses with no size restrictions. This is done via stochastic matching: instead of exhaustively exploring the set of matchings between any example and any short candidate hypothesis, one stochastically explores the set of matchings between any example and any candidate hypothesis. The user sets the number of matching samples to consider and thereby controls the cost of induction and classification. One advantage of this heuristic is to allow for resource-bounded learning, without any a priori knowledge about the problem domain. Experiments on a real-world problem pertaining to organic chemistry fully demonstrate the potentialities of the approach regarding both predictive accuracy and computational cost.
BibTeX
@inproceedings{sebag1997tractable,
  author = {Michèle Sebag and Céline Rouveirol},
  title = {{Tractable Induction and Classification in First Order Logic Via Stochastic Matching}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure