Tractable Induction and Classification in First Order Logic Via Stochastic Matching

TL;DR

This paper introduces STILL, a novel approach to learning in First-Order Logic (FOL) that tackles the inherent exponential complexity of matching. By employing a "stochastic matching" heuristic, STILL enables polynomial-time induction and classification of FOL hypotheses without size restrictions, offering a practical solution for complex relational domains.

What Problem Does This Paper Address?

Learning in First-Order Logic (FOL) is powerful for domains with complex relationships between objects (like molecules or natural language). However, a major hurdle is the "matching" step: determining how parts of a hypothesis relate to parts of an example. This process can be computationally explosive, growing exponentially with the size of hypotheses. Existing solutions often restrict hypothesis size or employ complex search strategies, limiting their applicability. This paper aims to overcome this intractability by allowing for polynomial-time learning and classification of FOL hypotheses of any size, without requiring prior domain knowledge.

Methods

The core innovation is stochastic matching. Instead of exhaustively checking all possible ways a hypothesis can match an example, STILL samples a subset of these matches. This sampling is controlled by the user, allowing them to balance computational cost with the quality of the learned hypotheses.

STILL builds upon the Disjunctive Version Space (DiVS) framework. DiVS addresses limitations of traditional Version Spaces by handling noisy data and disjunctive concepts. It represents hypotheses as a conjunction of disjunctions, making them more manageable.

The stochastic matching is integrated into both the induction (learning) and classification (prediction) phases:

  • Stochastic Induction: When learning, instead of considering all possible instantiations of literals in a clause against an example, STILL samples a user-defined number of these instantiations. This approximates the full set of matches, making hypothesis construction tractable.
  • Stochastic Classification: Similarly, when classifying a new instance, instead of checking all possible matches against learned hypotheses, STILL samples a subset. This allows for polynomial-time classification even with potentially large hypotheses.

The paper also explores two sampling mechanisms: a basic one and an "advanced" one that uses some naive domain knowledge to map similar atoms.

Datasets

The primary dataset used for experimental validation is the mutagenesis dataset. This dataset describes molecules and their mutagenic activity. The paper notes that this dataset can be represented in both FOL and attribute-value formats.

Key Insights and Ideas

  • Stochasticity as a Resource Management Tool: The paper frames stochastic matching not as a bias in the traditional sense (like language or search bias), but as a way to manage computational resources. The more resources (samples) you allocate, the better the approximation and potentially the more accurate the learning.
  • Tractability Without Size Restrictions: The most significant insight is achieving polynomial-time learning and classification in FOL without imposing a priori limits on hypothesis size. This is a major step towards applying ILP to truly complex, relational problems.
  • The "Advanced" SM Surprise: Unexpectedly, the "advanced" sampling mechanism, which tried to map similar atoms, performed worse than the basic random sampling. This suggests that rougher, more numerous discriminant differences (from basic SM) might be more effective for classification than a few acute ones (from advanced SM).
  • Competitive Accuracy with Massive Speedup: STILL achieves competitive predictive accuracy compared to other ILP learners, but with a speedup of two to three orders of magnitude.

Key Results

  • STILL achieved competitive predictive accuracy on the mutagenesis dataset, comparable to other ILP systems.
  • The computational cost of STILL was significantly lower, taking less than two minutes for a dataset that took other systems thousands of seconds (e.g., PROGOL and FOIL).
  • Experiments showed that the predictive accuracy of STILL degrades gracefully as the number of samples decreases.
  • The "advanced" sampling mechanism did not improve performance over the basic stochastic sampling.

Limitations and Future Work

  • Approximation: The core limitation is that stochastic matching provides an approximation. While the accuracy improves with more samples, it's not guaranteed to be exact.
  • Readability: The paper acknowledges that the price for tractability is a potential decrease in the readability of the learned hypotheses, which are expressed as disjunctions of clauses.
  • Formal Guarantees (PAC Model): A key future research direction is to provide formal guarantees for STILL within a PAC (Probably Approximately Correct) learning framework. This would involve understanding how the number of samples relates to the probability of correctness.
  • More Sophisticated Sampling: The authors suggest exploring more sophisticated sampling mechanisms beyond the basic and "advanced" ones presented.

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{1997tractable,
  title = {{Tractable Induction and Classification in First Order Logic Via Stochastic Matching}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure