Can decision stumps have more than 2 leaves? I understand decision stump: a shallow 1-level decision tree is often used as base-leaner in ensemble methods such as AdaBoost. What is not immediately clear to me is using such ensemble methods in multi-class classification task.
Can a decision stump have more than 2 leaves? Or each decision stump picks only 2-classes of the multi-class and fits model on?
I want to understand how decision stump works in a multiclass classification task. Which of this illustrations (my drawing) describe how it works (3-class problem for instance)?


@Ben Reiniger has a more complete answer with lots of useful details about random forests; definitely read that first.
I, on the other hand, want to elaborate on one single point: each decision in a tree-based model splits examples according to a single feature.
Consider the following example: we have n continuous features Xi and a categorical response with three levels y1, y2, y3. At each split the model chooses feature Xi and comes up with a decision rule such as:

If Xi < some number x, then the example belongs to the left child of the root. If Xi $\geq$ x, then it belongs to the right child.

What would a three-way split look like?

If Xi < some number x1, go left; if Xi is between x1 and x2, go in the middle; if Xi $\geq$ x2 then go right.

You suggest that since the target has three levels, three-way splits might be more appropriate. However:

*

*Three-way splits are more complex to estimate: we need to find two cutoff values x1 and x2 instead of just one x by optimizing a metric such as impurity.

*One three-way split is equivalent to two consecutive two-way splits so a tree-based model with binary decisions is just as flexible.

*There is no guarantee that any given feature Xi separates all three classes from each other. (Maybe both y1 and y2 instances tend to have low Xi and only y3 instances tend to have high Xi).

