Structural Regression Trees

AAAI 1996

TL;DR

This paper introduces Structural Regression Trees (SRT), a novel algorithm that bridges the gap between symbolic logic and statistical regression for predicting numerical values. SRT learns interpretable decision trees that incorporate relational background knowledge, offering a powerful new tool for domains where traditional methods fall short.

What Problem Does This Paper Address?

Many real-world machine learning tasks involve predicting a numerical value based on complex, relational data and background knowledge. Inductive Logic Programming (ILP) is well-suited for learning from relational data, but most ILP systems struggle with predicting numerical values or handling "non-determinate" background knowledge (where a predicate can have multiple valid interpretations). This limitation hinders their application in fields like quantitative structure-activity relationships (QSAR) and other scientific domains. Existing statistical methods, while capable of numerical prediction, often lack interpretability and struggle to integrate domain-specific relational knowledge.

Methods

SRT integrates the statistical method of regression trees (like CART) into the ILP framework. It constructs a decision tree where each node contains a literal or a conjunction of literals. The algorithm recursively builds the tree by selecting the best literal or conjunction at each node to partition the training data, aiming to minimize the sum of squared errors. A key innovation is its ability to handle non-determinate background knowledge by allowing the user to specify which literals can extend a clause, offering a controlled way to incorporate complex relationships.

SRT also introduces an optional "outlier detection by analogy" mechanism. This feature leverages relational background knowledge to identify test instances that are dissimilar to the training instances covered by the firing clause. If an instance is deemed an outlier, SRT can predict a value based on a more similar cluster of training instances, enhancing robustness.

The algorithm generates a series of trees of increasing complexity and selects the best one using the Minimum Description Length (MDL) principle, which balances model simplicity and accuracy to avoid overfitting.

Datasets

The paper evaluates SRT on five real-world domains:

  • Quantitative Structure-Activity Relationships (QSAR):
    • Inhibition of Escherichia coli dihydrofolate reductase (DHFR) by pyrimidines.
  • Inhibition of DHFR by triazines.
  • Finite Element Mesh Design: A domain with non-determinate background knowledge.
  • Mutagenicity Prediction: Predicting the mutagenic activity of chemicals (harmful to DNA).
  • Biodegradability Prediction: Predicting the half-rate of aerobic aqueous biodegradation in hours.

Key Insights and Ideas

  • Bridging Symbolic and Statistical Learning: SRT successfully merges the interpretability of symbolic logic (ILP) with the numerical prediction capabilities of statistical regression trees. This is crucial for domains requiring both understanding and precise numerical output.
  • Handling Non-Determinate Knowledge: The explicit mechanism for handling non-determinate literals is a significant advancement, opening up ILP to a wider range of complex real-world problems where predicates have multiple interpretations.
  • Outlier Detection via Analogy: The ability to detect and handle outliers using relational similarity is a clever way to improve robustness without sacrificing the core tree-based learning. It adds an instance-based reasoning component to the symbolic learner.
  • MDL for Model Selection: Using MDL for tree selection provides a principled way to prune the search space and select the most appropriate model, preventing overfitting and ensuring generalization.

Key Results

  • Competitive Performance: SRT demonstrated competitive performance across several real-world domains, often matching or exceeding existing methods in terms of Spearman rank correlation coefficients and other accuracy measures.
  • QSAR Domains: SRT performed particularly well in the pyrimidine and triazine QSAR domains, outperforming other methods and identifying previously unrecognized outliers.
  • Non-Determinate Domains: SRT showed promise in domains with non-determinate background knowledge (mesh design, biodegradability), where many other ILP systems cannot be applied.
  • Interpretability: A key qualitative result is that SRT produces comprehensible and explicit rules for predicting numbers, a significant advantage over purely statistical models.

Limitations and Future Work

  • User Specification of Literals: While SRT handles non-determinate literals, the user must specify which literals can be used to extend clauses. The authors suggest that a more generic solution for this would simplify the method's application.
  • Linear Regression in Leaves: The paper notes that assigning constant values to leaves limits accuracy. A future direction is to assign linear regression models to leaves for potentially more accurate predictions.
  • Tree Reuse: Currently, SRT regenerates trees from scratch in each iteration. The authors plan to extend the algorithm to reuse parts of trees from previous iterations to improve efficiency.
  • Comparison with Pruning Methods: The authors intend to compare their MDL-based tree selection with more traditional pruning methods like those used in CART.
  • Search Strategy Comparison: A deeper comparison between SRT's divide-and-conquer approach and FORS's covering approach for relational regression is suggested.

Summary updated

BibTeX
@inproceedings{1996structural,
  title = {{Structural Regression Trees}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure