Decision stump explained

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

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^{[2] [3]} or a stump with the two leaves, one of which corresponds to some chosen category, and the other leaf to all the other categories.^[4] For binary features these two schemes are identical. A missing value may be treated as a yet another category.

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^[5] used as components (called "weak learners" or "base learners") in machine learning ensemble techniques such as bagging and boosting. For example, a Viola–Jones face detection algorithm employs AdaBoost with decision stumps as weak learners.^[6]

The term "decision stump" was coined in a 1992 ICML paper by Wayne Iba and Pat Langley.^{[7] [8]}

See also

• Decision list

Notes and References

1. Robert C. . Holte . Very simple classification rules perform well on most commonly used datasets . Machine Learning . 11 . 1 . 63–90 . 1993 . 10.1023/A:1022631118932 . 6596 .
2. Book: Loper . Edward L. . Bird . Steven . Klein . Ewan . Natural language processing with Python . . Sebastopol, CA . 2009 . 978-0-596-51649-9 . 2010-06-10 . https://web.archive.org/web/20100618205152/http://nltk.googlecode.com/svn/trunk/doc/book/ch06.html . 2010-06-18 . dead .
3. This classifier is implemented in Weka under the name OneR (for "1-rule").
4. This is what has been implemented in Weka's DecisionStump classifier.
5. Book: Reyzin . Lev . Schapire . Robert E. . 2006 . http://www.cs.princeton.edu/~schapire/papers/boost_complexity.pdf . How Boosting the Margin Can Also Boost Classifier Complexity . ICML′06: Proceedings of the 23rd international conference on Machine Learning . 753–760 . 10.1145/1143844.1143939 . 978-1-59593-383-6. 2483269 .
6. Viola . Paul . Jones . Michael J. . 2004 . Robust Real-Time Face Detection . International Journal of Computer Vision . 57 . 2 . 137–154 . 10.1023/B:VISI.0000013087.49260.fb. 2796017 .
7. Book: Iba . Wayne . Langley . Pat . 1992 . http://lyonesse.stanford.edu/~langley/papers/stump.ml92.pdf . Induction of One-Level Decision Trees . ML92: Proceedings of the Ninth International Conference on Machine Learning, Aberdeen, Scotland, 1–3 July 1992 . Morgan Kaufmann . 233–240 . 10.1016/B978-1-55860-247-2.50035-8 . 978-1-55860-247-2.
8. Book: Oliver . Jonathan J. . David Hand (statistician) . Hand . David . 1994 . Averaging Over Decision Stumps . Machine Learning: ECML-94, European Conference on Machine Learning, Catania, Italy, April 6–8, 1994, Proceedings . Lecture Notes in Computer Science . 784 . Springer . 231–241 . 3-540-57868-4 . 10.1007/3-540-57868-4_61 . These simple rules are in effect severely pruned decision trees and have been termed decision stumps .