A Gradient-Based Boosting Algorithm for Regression Problems

Richard S. Zemel, Toniann PitassiNeurIPS 2000 · OpenReview

Summary

This paper introduces a novel gradient-based boosting algorithm specifically designed for regression problems. By utilizing a multiplicative objective function that re-weights training examples rather than just fitting residuals, the authors provide a method that reduces training error and exhibits superior resistance to overfitting compared to traditional regression boosting techniques.

What Problem Does This Paper Address?

Boosting algorithms like AdaBoost revolutionized machine learning by combining "weak learners" (simple models) into a single "strong learner." However, these were originally built for binary classification, where an answer is strictly either right or wrong.

Regression—predicting continuous values—is trickier. In regression, a prediction isn't just "wrong"; it can be "a little wrong" or "very wrong." Most early attempts to adapt boosting to regression relied on "residual fitting," where each subsequent model tries to predict the remaining error of the previous ensemble. While effective, this approach often deviates from the core probabilistic properties of classification boosting and is highly susceptible to overfitting. Zemel and Pitassi set out to create a regression boosting framework that retains the elegant "distribution-shifting" property of AdaBoost.

Methods

The authors derive their algorithm from a novel, multiplicative objective function ($J_T$). Unlike standard Gradient Boosting Machines (which typically minimize a loss by changing the target values for the next learner), this method keeps the targets fixed and instead re-weights the training distribution.

Key technical components include:

  • Multiplicative Objective: The cost function is structured such that the objective for each new hypothesis is formed by simply re-weighting the existing training distribution based on previous errors.
  • Exponentiated Squared Error: The weights are updated using the exponentiated squared error of the current ensemble.
  • The $\tau$ Threshold: They introduce a problem-dependent parameter, $\tau$, which acts as a threshold to demarcate "correct" from "incorrect" responses, allowing them to prove a convergence bound on training error similar to the original AdaBoost proof.
  • Line Search: Instead of an analytical solution for the combination coefficients ($c_t$), the algorithm uses a simple line search to find the optimal weight for each new hypothesis.

Datasets

The algorithm was evaluated on two primary benchmarks:

  1. F1 (Friedman’s Nonlinear Problem): A synthetic dataset with 10 independent input variables, where only five have actual predictive value. This tests the model's ability to ignore noise and capture complex nonlinear relationships.
  2. Boston Housing Dataset: A classic real-world benchmark consisting of 506 examples with 12 continuous variables used to predict housing prices.

In both cases, the "weak learners" used were neural networks with varying numbers of hidden nodes.

Key Insights and Ideas

  • Average Error vs. Error of the Average: The authors use a probabilistic framework to show that their objective function attempts to minimize the average error of the individual models (incorporating both bias and variance). In contrast, residual-fitting methods minimize the error of the average model (focusing primarily on bias).
  • The Complexity Sweet Spot: A fascinating insight in the paper is the discovery that the choice of boosting algorithm should depend on the complexity of the weak learner. If your weak learners are extremely simple (e.g., 1-2 hidden nodes), residual fitting performs better. However, as the weak learners become more complex, this new gradient-based method becomes superior because it is less prone to overfitting.
  • Inherent Regularization: Because the algorithm forces new hypotheses to resemble existing ones if they cannot significantly improve the estimate, it has a built-in bias-variance tradeoff that prevents the ensemble from "chasing noise" in the way residual fitting often does.

Key Results

  • Convergence: The authors provide a formal proof that their method reduces training error at each stage, provided the weak learner meets a minimum accuracy threshold.
  • Generalization: In empirical tests on the F1 and Boston Housing data, the proposed algorithm showed better generalization than residual-fitting approaches as the number of boosting stages increased.
Performance comparison across boosting stages
  • Overfitting Resistance: While residual-fitting algorithms often showed a sharp decrease in training error followed by a rise in test error (classic overfitting), the authors' method exhibited much more stable performance across boosting rounds. The figure above illustrates how the proposed algorithm ("OurAlg") stabilizes effectively compared to residual fitting and mixture-of-experts approaches.

Limitations and Future Work

  • The $\tau$ Parameter: The algorithm requires a manually chosen threshold $\tau$. While the results were consistent across different values in their tests, this adds a layer of hyperparameter tuning that is problem-dependent.
  • Simple Learner Performance: The method does not perform as well as residual fitting when the base learners are very weak (low capacity).
  • Future Directions: The authors suggest extending the model to include input-dependent coefficients. This would allow the ensemble to assign different "confidence" levels to specific learners based on which part of the input space they are predicting, effectively moving toward a "mixture-of-experts" architecture.

Summary updated

Abstract

In adaptive boosting, several weak learners trained sequentially are combined to boost the overall algorithm performance. Re(cid:173) cently adaptive boosting methods for classification problems have been derived as gradient descent algorithms. This formulation jus(cid:173) tifies key elements and parameters in the methods, all chosen to optimize a single common objective function. We propose an anal(cid:173) ogous formulation for adaptive boosting of regression problems, utilizing a novel objective function that leads to a simple boosting algorithm. We prove that this method reduces training error, and compare its performance to other regression methods. The aim of boosting algorithms is to "boost" the small advantage that a hypothesis produced by a weak learner can achieve over random guessing, by using the weak learning procedure several times on a sequence of carefully constructed distribu(cid:173) tions. Boosting methods, notably AdaBoost (Freund & Schapire, 1997), are sim(cid:173) ple yet powerful algorithms that are easy to implement and yield excellent results in practice. Two crucial elements of boosting algorithms are the way in which a new distribution is constructed for the learning procedure to produce the next hy(cid:173) pothesis in the sequence, and the way in which hypotheses are combined to pro(cid:173) duce a highly accurate output. Both of these involve a set of parameters, whose values appeared to be determined in an ad hoc maImer. Recently boosting algo(cid:173) rithms have been derived as gradient descent algorithms (Breiman, 1997; Schapire & Singer, 1998; Friedman et al., 1999; Mason et al., 1999). These formulations justify the parameter values as all serving to optimize a single common objective function. These optimization formulations of boosting originally developed for classification problems have recently been applied to regression problems. However, key prop(cid:173) erties of these regression boosting methods deviate significantly from the classifica(cid:173) tion boosting approach. We propose a new boosting algorithm for regression prob(cid:173) lems, also derived from a central objective function, which retains these properties. In this paper, we describe the original boosting algorithm and summarize boosting methods for regression. We present our method and provide a simple proof that elucidates conditions under which convergence on training error can be guaran(cid:173) teed. We propose a probabilistic framework that clarifies the relationship between various optimization-based boosting methods. Finally, we summarize empirical comparisons between our method and others on some standard problems. 1 A Brief Summary of Boosting Methods Adaptive boosting methods are simple modular algorithms that operate as follows. Let 9 : X -t Y be the function to be learned, where the label set Y is finite, typ(cid:173) ically binary-valued. The algorithm uses a learning procedure, which has access to n training examples, {(Xl, Y1), ... , (xn, Yn)}, drawn randomly from X x Yac(cid:173) cording to distribution D; it outputs a hypothesis I : X -t Y, whose error is the expected value of a loss function on I(x) , g(x), where X is chosen according to D. Given f, cl > 0 and access to random examples, a strong learning procedure outputs with probability 1 - cl a hypothesis with error at most f, with running time polyno(cid:173) mial in 1/ f, 1/ cl and the number of examples. A weak learning procedure satisfies the same conditions, but where f need only be better than random guessing. Schapire (1990) showed that any weak learning procedure, denoted WeakLeam, can be efficiently transformed ("boosted") into a strong learning procedure. The AdaBoost algorithm achieves this by calling WeakLeam multiple times, in a se(cid:173) quence of T stages, each time presenting it with a different distribution over a fixed training set and finally combining all of the hypotheses. The algorithm maintains a weight w: for each training example i at stage i, and a distribution D t is computed by normalizing these weights. The algorithm loops through these steps: At stagei, the distribution D t is given to WeakLeam, which generates a hy(cid:173) pothesis It- The error rate ft of It w.r.t. D t is: ft = 2::i f,(x');t'y ' wU 2::7=1 w~ w: * (ft/ (l - The new training distribution is obtained from the new weights: W;+l
BibTeX
@inproceedings{zemel2000gradient,
  author = {Richard S. Zemel and Toniann Pitassi},
  title = {{A Gradient-Based Boosting Algorithm for Regression Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2000},
  url = {https://openreview.net/forum?id=ByWT08Zdbr},
}
Figure