PaperlayerView exact revision on arXiv

Source-linked AI summary

DART: Dropouts meet Multiple Additive Regression Trees

K. V. Rashmi, Ran Gilad-Bachrach

arXiv:1505.01866v1cs.LGstat.ML

TL;DR

MART’s later boosted trees can over-specialize, limiting their contribution across instances and leaving predictions sensitive to early trees. The paper proposes DART, which applies dropout by muting complete trees within MART. Across ranking, regression, and classification, DART outperforms MART and addresses over-specialization to a considerable extent.

  • Problem

    MART suffers over-specialization: later trees affect few instances, which can harm unseen-data performance and increase sensitivity to early trees.

  • Method

    DART applies dropout by muting complete trees within MART, rather than muting only features or connections.

  • Results

    DART outperforms MART and random forest across ranking, regression, and classification tasks with significant margins.

  • Takeaways & Limitations

    DART’s more even tree contributions address over-specialization while preserving continued learning to compensate for ensemble deficiencies.

  • Takeaways & Limitations

    Shrinkage reduces over-specialization only partly; as the ensemble grows, the problem reappears.

Abstract

from arXiv · show

Multiple Additive Regression Trees (MART), an ensemble model of boosted regression trees, is known to deliver high prediction accuracy for diverse tasks, and it is widely used in practice. However, it suffers an issue which we call over-specialization, wherein trees added at later iterations tend to impact the prediction of only a few instances, and make negligible contribution towards the remaining instances. This negatively affects the performance of the model on unseen data, and also makes the model over-sensitive to the contributions of the few, initially added tress. We show that the commonly used tool to address this issue, that of shrinkage, alleviates the problem only to a certain extent and the fundamental issue of over-specialization still remains. In this work, we explore a different approach to address the problem that of employing dropouts, a tool that has been recently proposed in the context of learning deep neural networks. We propose a novel way of employing dropouts in MART, resulting in the DART algorithm. We evaluate DART on ranking, regression and classification tasks, using large scale, publicly available datasets, and show that DART outperforms MART in each of the tasks, with a significant margin. We also show that DART overcomes the issue of over-specialization to a considerable extent.

1 Introduction

MART can over-specialize because later trees affect only a few instances, while shrinkage only partly alleviates this pattern. DART applies dropout by muting complete trees and is evaluated against established ensemble methods across three tasks.

  • Over-specialization: Later MART trees can affect only a few instances, increasing unseen-data risk and making predictions sensitive to early trees.The added capacity may not significantly improve training error.
  • Limits of shrinkage: Shrinkage reduces early-tree impact, but over-specialization reappears as the ensemble grows.The passage identifies shrinkage as the common approach and describes the remaining problem as fundamental.
  • DART approach: DART mutes complete trees rather than features, applying dropouts within MART to address over-specialization.The paper distinguishes this from dropout approaches that mute neural connections or input features.
  • Evaluation: DART is evaluated on ranking, regression, and classification using large-scale, publicly available datasets, with comparisons to MART and random forest.The paper reports significant-margin improvements in each task.
  • Reported outcome: DART produces more balanced tree contributions and outperforms MART in each evaluated task with significant margins.The introduction attributes improved performance partly to addressing over-specialization.

2 Overcoming the Over-specialization in MART

MART concentrates contribution in early trees, while shrinkage slows but does not eliminate this imbalance. DART slows specialization and maintains more even later-tree contributions while continuing to compensate for ensemble deficiencies.

  • MART behavior: MART’s first tree makes a significant contribution, while later trees contribute negligibly for most data points.This pattern is measured using the absolute expected tree contribution over training data.
  • MART behavior: MART’s later trees can make negligible contributions to the overall prediction for most data points, visible as large yellow leaves.The yellow leaves indicate trees abstaining on many instances.
  • MART behavior: Adding a constant to every label changes only the first tree substantially, so it learns the bias while later trees learn deviations.This makes the ensemble sensitive to decisions made by the first tree.
  • Shrinkage: The 100th tree’s contribution is about 15 orders of magnitude smaller than the first without shrinkage, versus 4 orders with shrinkage.Shrinkage makes contribution differences more gradual, but they remain notable.
  • DART: DART trees specialize more slowly, and later trees retain higher expected contributions than in MART or MART with shrinkage.The passage links this pattern to reduced sensitivity to individual trees.
  • DART: DART continues learning trees that compensate for existing deficiencies while balancing diversity against over-specialization.The passage contrasts this controlled behavior with random forest and identifies MART and random forest as extreme DART cases.

3 Description of the DART Algorithm

DART extends MART’s gradient-boosting procedure by fitting trees on gradients computed from a random subset of the ensemble, then normalizing the new and dropped trees before updating the model. It supports regression, classification, and ranking through task-specific losses, while using dropout selection to reduce over-specialization.

  • MART foundation: MART fits each new regression tree to the inverse derivative of a task-specific loss and adds it to the ensemble.The loss can be chosen for regression, classification, or ranking.
  • Task-specific losses: The loss function determines MART’s task applicability: squared loss supports regression, logistic loss supports classification, and LambdaMart defines the ranking gradient.For ranking, the gradient uses pairwise NDCG loss among points associated with the same query.
  • DART algorithm: DART computes the next tree’s gradient using only a randomly selected subset of the existing ensemble.The dropped-tree subset creates a modified model for learning the next regression tree.
  • DART algorithm: DART normalizes the new tree by 1/k, then scales the new and dropped trees by k/(k+1) before adding the update.Here, k is the number of trees dropped when constructing the modified model.
  • Regularization: DART’s dropout size controls regularization, spanning MART when no trees are dropped and random-forest behavior when all trees are dropped.The paper describes these endpoints as aggressive MART and conservative random-forest modes.
  • DART algorithm: DART can use Binomial-plus-one dropout, independently dropping existing trees with probability pdrop while ensuring at least one tree is dropped per iteration.When pdrop is very small, the procedure effectively drops one tree per round, denoted pdrop = ε.

4 Evaluation

DART is evaluated against MART and random forest on ranking, regression, and classification tasks using large-scale public datasets. Across these evaluations, DART generally achieves stronger results, with especially clear gains in ranking and regression.

  • Evaluation setup: DART is evaluated on ranking, regression, and classification tasks using large-scale, publicly available datasets.The evaluation compares DART with MART using different shrinkage factors and with random forest whenever applicable.
  • 4.1 Ranking: ∼0.4 NDCG points: DART gains this amount over MART on the ranking task.DART also gains 0.2 points at position 1 and 0.38 points at position 2.
  • 4.2 Regression: For every ensemble size, the best DART regression model outperforms the best MART and random forest models.This remains true even when DART is restricted to dropping only a single tree per iteration.
  • 4.2 Regression: DART and MART achieve their lowest regression losses with trees comprising only 50 leaves, whereas random forest requires larger trees to achieve low losses.With tree sizes limited to 50 and 100 leaves, the best random forest losses are 44.48 and 36.29, respectively.
  • 4.3 Classification: On face detection, DART and MART both achieve their highest accuracy with 250-tree ensembles, while DART’s accuracy advantage is statistically significant.The models disagree on 1106 test predictions; MART gets 481 correct and DART gets 625 correct, with recall rates of 0.665 and 0.672, respectively.
  • Overall comparison: Random forest does not compare well against MART or DART in the reported experiments, showing that the optimal dropout point between these extremes is not trivial.The paper treats MART and random forest as two extremes of the DART algorithm.

5 Conclusions

The paper introduces DART to address MART’s over-specialization by muting complete trees during training. DART produces more even tree contributions and considerable accuracy gains across ranking, regression, and classification.

  • 5 Conclusions: DART applies dropouts to complete trees in MART, rather than muting features, to address over-specialization.The approach is adapted from dropout methods used in neural networks.
  • 5 Conclusions: DART’s ensemble trees contribute more evenly toward the final prediction than those in MART.The paper presents this pattern in Figure 1.
  • 5 Conclusions: DART achieves considerable accuracy gains on ranking, regression, and classification tasks.The evaluation uses large-scale, publicly available datasets.
  • 5 Conclusions: Future work includes applying dropout to AdaBoost and tuning dropped-set selection and normalization techniques.The authors also identify further directions for understanding and refining dropout-based ensemble methods.

Acknoledgments

The research was conducted while the first author was an intern in Microsoft Research’s machine learning department.

  • Acknoledgments: The research was conducted during the first author’s internship in Microsoft Research’s machine learning department.
Loading 1505.01866v1…