Boosting with Multi-Way Branching in Decision Trees

Yishay Mansour, David A. McAllesterNeurIPS 1999 · OpenReview

Introduction

In machine learning, "boosting" refers to the ability of an algorithm to achieve arbitrarily high accuracy by combining many "weak" rules of thumb. Historically, researchers proved that standard top-down decision tree algorithms (like CART or C4.5) perform boosting, but their mathematical proofs were limited to binary trees—trees where every node splits into exactly two paths.

This paper bridges the gap between the theory and practice of decision tree learning. In the real world, decision trees often use multi-way branching (e.g., splitting a "Color" attribute into Red, Blue, and Green). There is a natural trade-off: a multi-way split provides more information but "spends" more of the tree's size budget. Before this work, there was no rigorous theoretical justification for how much improvement a multi-way split should provide to be considered efficient. The authors extend boosting guarantees to multi-way branching trees, proving that greedy top-down construction remains an effective boosting strategy as long as the improvement from a split scales with the logarithm of the number of branches it creates.

Methods: The Multi-Branch Growth Procedure

The authors introduce a new multi-branch tree growth procedure, redefining what makes a branching function "acceptable" during the greedy construction of a tree.

  • The Index Function: Similar to previous work, they use an index function (such as Entropy or the Gini Index) to measure the "impurity" of a node.
  • The Logarithmic Trade-off: The authors propose that if a split creates $k$ branches, the reduction in impurity doesn't need to be linear (proportional to $k$). Instead, they prove that the return only needs to be proportional to the logarithm of the number of branches ($\ln k$).
  • VW-Trees: To prove their main theorem, they develop a novel mathematical abstraction called a Visited Weighted Tree (VW-tree). This allows them to track "visitation counts" and "weights" for each node, ensuring that the greedy algorithm always makes enough progress to satisfy the boosting requirements.

(Note: As a purely theoretical paper, it does not use empirical datasets for training or evaluation, relying instead on mathematical proofs that apply to any dataset satisfying the "weak learning hypothesis.")

Key Insights and Theoretical Results

The paper frames tree construction as a game where the learner has a "budget" of total leaves. A four-way split is "twice as expensive" as a two-way split because it adds more leaves in a single step.

Naively, one might think a 10-way split should be five times better than a 2-way split. However, this paper shows that such an expectation is overkill. Because of the way decision trees partition space, a logarithmic return ($\ln k$) is sufficient to maintain the same boosting efficiency as binary trees. This reinforces the idea that "greedy" algorithms—which make the best local choice at each step without looking ahead—are theoretically sound for boosting, even when the choices involve complex multi-way splits.

The Main Result (Theorem 4.1): The authors prove that if a tree $T$ is grown using their $\gamma$-boosting multi-branch procedure, the training error $\epsilon(T)$ is bounded by: $$ \epsilon(T) \le |T|^{-\gamma} $$ where $|T|$ is the number of leaves and $\gamma$ is a constant representing the strength of the weak learner. This confirms that the boosting property of decision trees is robust; it isn't a fluke of binary branching but a fundamental characteristic of top-down partitioning, provided the branching "cost" is handled correctly.

Limitations and Future Work

  • Focus on Training Error: The paper primarily addresses how quickly the algorithm reduces error on the training set. While it mentions that smaller trees generalize better (via VC dimension arguments), it doesn't deeply explore the trade-off between multi-way branching and overfitting on unseen data.
  • Heuristic Alignment: While the paper provides a theoretical curve ($g(k) \approx \ln k$), it doesn't compare this directly to the specific heuristics used in C4.5 (like Gain Ratio). A natural next step would be to see if practical algorithms could be improved by strictly adhering to the logarithmic trade-off discovered here.
  • Computational Complexity: The proof assumes the existence of an "acceptable" split at each step, but finding that split in a massive feature space remains a computational challenge in practice.

Summary updated

Abstract

It is known that decision tree learning can be viewed as a form of boosting. However, existing boosting theorems for decision tree learning allow only binary-branching trees and the generalization to multi-branching trees is not immediate. Practical decision tree al(cid:173) gorithms, such as CART and C4.5, implement a trade-off between the number of branches and the improvement in tree quality as measured by an index function. Here we give a boosting justifica(cid:173) tion for a particular quantitative trade-off curve. Our main theorem states, in essence, that if we require an improvement proportional to the log of the number of branches then top-down greedy con(cid:173) struction of decision trees remains an effective boosting algorithm.
BibTeX
@inproceedings{mansour1999boosting,
  author = {Yishay Mansour and David A. McAllester},
  title = {{Boosting with Multi-Way Branching in Decision Trees}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {1999},
  url = {https://openreview.net/forum?id=rJEi1DWObH},
}

Loading related content...

Figure