Learning Trees and Rules with Set-Valued Features

William W. CohenAAAI 1996

Introduction

Traditional machine learning algorithms typically rely on fixed-length feature vectors, where each instance is described by a predetermined set of numerical or categorical attributes. While effective for many structured data tasks, this representation falters when faced with high-dimensional, sparse data like text or complex relational structures. In text categorization, for instance, representing a document as a vector often requires a feature for every possible word in a language, leading to massive, mostly empty data structures. Similarly, in relational learning, "propositionalizing" data to fit vector formats often results in a combinatorial explosion of features that cripples training speed.

This paper proposes an elegant solution: Set-Valued Features. By allowing features to be sets of strings rather than single values, algorithms can represent complex data compactly and efficiently without sacrificing the expressive power of more complex logic-based systems.

Methods: Extending Symbolic Learning

The core innovation presented by William W. Cohen is the adaptation of standard symbolic learners—specifically decision trees (ID3) and rule learners (RIPPER)—to handle these set-valued attributes. Instead of simple equality tests, the author introduces "primitive tests" based on set membership:

  • Element-of test ($s \in u_i$): Checks if a specific string s is present in the set-valued feature $u_i$.
  • Not-element-of test ($s \notin u_i$): Checks if string s is absent from the set.

To implement this, the author introduces the MaxGainTest function. Rather than requiring a pre-defined vocabulary, the algorithm dynamically scans the training data to identify unique strings within a set-valued feature. It then evaluates which string $s$ provides the maximum information gain (or entropy reduction) when used as a membership test. This approach is theoretically grounded in Blum’s "infinite attribute model," ensuring that the models generalize well even when the space of potential features is effectively infinite.

Key Results in Relational and Text Learning

The effectiveness of set-valued features was evaluated across several benchmarks, including relational problems like student loan prediction and large-scale text categorization using AP Newswire and Reuters datasets.

One of the most striking results was the performance leap in relational learning. Traditional Inductive Logic Programming (ILP) systems often struggle with the computational overhead of searching through complex relational hypotheses. By treating relational links as set-valued features, the RIPPER algorithm achieved massive speedups.

Comparison of RIPPER and Grendel2 performance on relational learning tasks.

As shown in the table above, on the "4-local" bias test with 500 examples, RIPPER completed training in just 9.1 seconds, whereas the first-order learner Grendel2 required 376 seconds—a nearly 40x speedup—while achieving the exact same 0.0% error rate.

In text categorization, RIPPER with set-valued features also proved superior to standard baselines. On the AP headlines dataset, it outperformed the Rocchio algorithm (a common IR baseline) in the majority of categories, demonstrating that rule-based learners can be both efficient and highly accurate on large-scale text tasks.

Key Insights: The Power of Totality

A common practice in text processing is "feature selection"—pruning the vocabulary to keep models manageable. However, Cohen’s research suggests that with the efficiency of set-valued features, such pruning is not only unnecessary but potentially detrimental.

Performance of RIPPER variants across different vocabulary sizes.

The experimental data indicates that performance is maximized when the algorithm is allowed to consider "all words" present in the training set. As the vocabulary is restricted to smaller subsets of words, metrics like the F-score and recall begin to decline significantly. Because set-valued features provide a sparse representation, the system can scale to hundreds of thousands of documents and tens of thousands of unique words without the quadratic memory growth associated with traditional feature vectors.

Conclusion and Future Directions

The use of set-valued features bridges the gap between simple attribute-value learning and complex relational logic. It allows for a "sparse-first" approach to data representation that is both memory-efficient and computationally fast. While the current work focuses on sets of strings, the framework is extensible. Future research could explore sets of more complex objects or the integration of weighted sets (e.g., TF-IDF scores). Ultimately, this approach simplifies data preparation for non-experts, as it removes the need for complex logic programming or aggressive feature engineering.

Summary updated

BibTeX
@inproceedings{cohen1996learning,
  author = {William W. Cohen},
  title = {{Learning Trees and Rules with Set-Valued Features}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1996},
}
Figure