Decision stump

An example of a decision stump that discriminates between two of three classes of Iris flower data set: Iris versicolor and Iris virginica. This particular stump achieves 94% accuracy on Iris dataset for these two classes.

A decision stump is a machine learning model consisting of a one-level decision tree.^[1] That is, it is a decision tree with one internal node (the root) which is immediately connected to the terminal nodes. A decision stump makes a prediction based on the value of just a single input feature. Sometimes they are also called 1-rules.^[2]

Depending on the type of the input feature, several variations are possible. For nominal features, one may build a stump which contains a leaf for each possible feature value^[3][4] or a stump with the two leaves, one of which corresponds to some chosen category, and the other leaf to all the other categories.^[5] For binary features these two schemes are identical. A missing value may be treated as a yet another category.^[5]

For continuous features, usually, some threshold feature value is selected, and the stump contains two leaves — for values below and above the threshold. However, rarely, multiple thresholds may be chosen and the stump therefore contains three or more leaves.

Decision stumps are often^[6] used as components (called "weak learners" or "base learners") in machine learning ensemble techniques such as bagging and boosting. For example, a state-of-the-art Viola–Jones face detection algorithm employs AdaBoost with decision stumps as weak learners.^[7]

The term "decision stump" has been coined in a 1992 ICML paper by Wayne Iba and Pat Langley.^[1][8]

References

1. ^ ^{a b} Wayne Iba and Pat Langley. (1992). Induction of One-Level Decision Trees. Proceedings of the Ninth International Conference on Machine Learning.
2. ^ Robert C. Holte (1993). "Very Simple Classification Rules Perform Well on Most Commonly Used Datasets". http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.2711&rep=rep1&type=pdf. 
3. ^ Loper, Edward L.; Bird, Steven; Klein, Ewan (2009). Natural language processing with Python. Sebastopol, CA: O'Reilly. ISBN 0-596-51649-5. http://nltk.googlecode.com/svn/trunk/doc/book/ch06.html. 
4. ^ This classifier is implemented in Weka under the name OneR (for "1-rule").
5. ^ ^{a b} This is what has been implemented in Weka's DecisionStump classifier.
6. ^ Lev Reyzin and Robert E. Schapire. (2006). How Boosting the Margin Can Also Boost Classifier Complexity. ICML 2006. Page 7.
7. ^ Paul Viola and Michael J. Jones. (2004). Robust Real-Time Face Detection. International Journal of Computer Vision, 2004.
8. ^ Jonathan Oliver and David Hand. (1994). Averaging Over Decision Stumps. ECML 1994. doi:10.1007/3-540-57868-4_61
   Quote: "These simple rules are in effect severely pruned decision trees and have been termed decision stumps [cites Iba and Langley]".