Learning Trees and Rules with Set-Valued Features

In most learning systems examples are represented as fixed-length “ feature vectors”, the components of which are either real numbers or nominal values. W e propose an extension of the featurevector representation that allows the value of a feature to be a set of strings; for instance, to represent a small white and black dog with the nominal features size and species and the setvalued feature color, one might use a feature vector with size=small, species=canis-f amiliaris and color={ white, black}. Since we make no assumptions about the number of possible set elements, this extension of the traditional feature-vector representation is closely connected to Blum’ s “ infinite attribute” rep resentation. We argue that many decision tree and rule learning algorithms can be easily extended to setvalued features. We also show by example that many real-world learning problems can be efficiently and naturally represented with set-valued features; in particular, text categorization problems and problems that arise in propositionalizing first-order representations lend themselves to set-valued features.

Authors

• William W. Cohen Google AI

Keywords

No keywords are indexed for this paper.