PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust LogitBoost and Adaptive Base Class (ABC) LogitBoost

Ping Li

arXiv:1203.3491v1cs.LGstat.ML

TL;DR

The paper addresses numerical stability and base-class selection in multiclass logitboost. It introduces robust logitboost with an explicit tree-split criterion and combines it with abc-boost to create abc-logitboost, which outperforms the corresponding baseline algorithms in the reported experiments, with some deep-learning comparisons showing room for improvement.

  • Problem

    Logitboost’s tree-split construction was viewed as potentially numerically unstable, while adaptive base-class boosting had previously been implemented with mart rather than logitboost.

  • Method

    The paper derives an explicit tree-split criterion for robust logitboost and combines robust logitboost with abc-boost to develop abc-logitboost for multiclass classification.

  • Results

    Abc-logitboost outperforms abc-mart and logitboost, while robust logitboost outperforms mart, except on Poker25kT1 and Poker25kT2.

  • Takeaways & Limitations

    The reported experiments support abc-logitboost as the strongest of the compared boosting algorithms, while deep learning achieves better performance on certain datasets.

  • Takeaways & Limitations

    The M-Noise1–M-Noise6 test sets are very small, limiting statistical-significance evaluation on those datasets.

Abstract

from arXiv · show

Logitboost is an influential boosting algorithm for classification. In this paper, we develop robust logitboost to provide an explicit formulation of tree-split criterion for building weak learners (regression trees) for logitboost. This formulation leads to a numerically stable implementation of logitboost. We then propose abc-logitboost for multi-class classification, by combining robust logitboost with the prior work of abc-boost. Previously, abc-boost was implemented as abc-mart using the mart algorithm. Our extensive experiments on multi-class classification compare four algorithms: mart, abcmart, (robust) logitboost, and abc-logitboost, and demonstrate the superiority of abc-logitboost. Comparisons with other learning methods including SVM and deep learning are also available through prior publications.

1 Introduction

The paper revisits logitboost for multiclass classification, where regression trees serve as weak learners in an additive model. It addresses numerical stability and adaptive base-class selection, culminating in abc-logitboost.

  • Logitboost: Logitboost and mart generalize classical logistic regression through additive models whose terms are typically regression-tree weak learners.The model parameters are learned by maximum likelihood, equivalently by minimizing negative log-likelihood.
  • Base-class choice: The usual sum-to-zero constraint reduces multiclass boosting to K −1 modeled classes by designating one class as the base class.Earlier logitboost work conditioned on a base class and reported derivatives independent of that choice.
  • Logitboost: Logitboost builds its model stagewise using first- and second-order loss derivatives and fits a separate regression function for each class.With tree weak learners, the diagonal approximation is presented as practically necessary.
  • Adaptive Base Class Boost: Adaptive base-class boosting searches for the best base class at each iteration to minimize training loss; its mart implementation is abc-mart.This paper combines abc-boost with robust logitboost to develop abc-logitboost.
  • Robust Logitboost: The paper responds to concerns about logitboost’s numerical stability by introducing an explicit tree-construction formulation called robust logitboost.The formulation is intended to make the tree-split criterion explicit for the standard tree-based implementation.

2 Robust Logitboost

Robust logitboost specifies a second-order tree-split criterion and uses it in a tree-based boosting algorithm. The criterion is argued to be numerically stable and is contrasted with mart’s split construction.

  • Tree-Split Criterion Using 2nd-order Information: Robust logitboost selects a split index that maximizes the reduction in weighted squared error for ordered feature values.The procedure operates on weights and response values associated with the sorted feature order.
  • Tree-Split Criterion Using 2nd-order Information: The robust criterion groups p_i,k(1 − p_i,k) terms, reducing the likelihood of numerical problems when probabilities approach extreme values.When these terms tend to zero throughout a region, the model is fitted perfectly and the corresponding numerator approaches zero at a square rate.
  • Robust Logitboost: Algorithm 2 constructs J-terminal-node regression trees using residuals r_i,k − p_i,k and the robust tree-split criterion.Terminal-node values are computed after the trees are constructed.
  • Friedman’s Mart Algorithm: Mart uses a different split criterion based on first-order responses, while its terminal-node update matches logitboost’s weighted-average equation.The paper states that mart can be obtained by replacing robust logitboost’s split criterion with mart’s criterion.
  • Friedman’s Mart Algorithm: The paper argues that robust logitboost’s split criterion is numerically more stable than the corresponding mart update formula.The mart update formula has nevertheless been used successfully in practice for 10 years.

3 Adaptive Base Class (ABC) Logitboost

ABC-logitboost combines adaptive base-class selection with robust logitboost to build a multi-class algorithm. The analysis shows that the full Hessian is base-class invariant, but diagonal approximation makes base-class choice matter for tree construction.

  • Adaptive Base Class Logitboost: ABC-logitboost combines abc-boost with robust logitboost, using adaptive base-class selection and a tree-split procedure for multi-class classification.The algorithm searches over candidate base classes at each boosting iteration and uses derivatives associated with the selected class.
  • Adaptive Base Class Logitboost: ABC-logitboost differs from abc-mart only in its tree-split procedure, while retaining the exhaustive base-class search strategy.The paper describes abc-mart as abc-boost combined with mart and abc-logitboost as abc-boost combined with robust logitboost.
  • Adaptive Base Class Logitboost: For each candidate base class, the algorithm fits J-terminal-node regression trees for the remaining classes using weighted residuals.The weights are p_i,b(1−p_i,b)+p_i,k(1−p_i,k)+2p_i,bp_i,k.
  • Why Does the Choice of Base Class Matter?: The full Hessian is non-zero and independent of the base-class choice, so base-class selection would not matter if the full Hessian were used.This result is stated for the K=3 example with k=0 as the base class.
  • Why Does the Choice of Base Class Matter?: Base-class choice matters in practice because diagonal approximation is required to construct trees at each boosting iteration.The diagonal approximation is presented as a consequence of using trees as the base learner.

4 Experiments on Multi-class Classification

The experiments use varied multi-class datasets, including large, noisy, and small-training-set variants. Their stated goal is to compare mart, abc-mart, robust logitboost, and abc-logitboost across reasonable parameter settings.

  • Datasets: The study evaluates algorithms on Covertype, Poker, Mnist variants, and Letter partitions with different training and testing constructions.The datasets include large-sample settings, noise and transformation variants, and small-training-set partitions.
  • Datasets: Letter4k and Letter2k use small training sets to demonstrate algorithm performance under limited training data.Letter4k uses 4,000 training samples and Letter2k uses 2,000, with the remaining data used for testing.
  • Experimental Goals: The experiments aim to show that abc-logitboost outperforms robust logitboost, abc-mart outperforms mart, and robust logitboost often outperforms mart.The stated comparisons also include abc-logitboost often outperforming abc-mart.
  • Experimental Goals: The reported improvements are intended to hold across almost all reasonable parameter settings rather than only selected parameter combinations.The main parameter is J, the number of terminal tree nodes; test errors are often insensitive to shrinkage when ν≤0.1.

4.3 Detailed Experiment Results on Mnist10k, M-Image, Letter4k, and Letter2k

Experiments on Mnist10k, M-Image, Letter4k, and Letter2k evaluate four boosting algorithms across tree sizes and shrinkage values. The results consistently favor abc-logitboost over the other compared methods.

  • Experimental setup: The experiments vary J across 13 tree sizes and ν across four shrinkage values, training up to 10000 iterations before reporting final test mis-classification errors.The evaluated tree sizes are J ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20, 24, 30, 40, 50}, and ν ∈ {0.04, 0.06, 0.08, 0.1}.
  • Datasets and comparisons: Tables 2–5 report test mis-classification errors for mart, abc-mart, logitboost, and abc-logitboost on Mnist10k, M-Image, Letter4k, and Letter2k.Each table separates mart versus abc-mart and logitboost versus abc-logitboost comparisons.
  • Mnist10k results: On Mnist10k, abc-logitboost consistently improves over robust logitboost and abc-mart, while robust logitboost improves over mart and abc-mart improves over mart.The reported comparisons are consistent across the tested parameter settings.
  • Parameter sensitivity: The reported Mnist10k performances are not very sensitive to the tested parameters, especially given its 60000 test samples.Appendix B provides P-values for every combination of J and ν.
  • Iteration-wise behavior: Figure 1 tracks test mis-classification errors across all boosting iterations for ν = 0.04, 0.06, and 0.1 with selected J values.The authors identify these full-iteration curves as their most reliable comparison, although they cannot present all such plots.

4.4 Experiment Results on Poker25kT1, Poker25kT2

Poker25kT1 and Poker25kT2 use two test-set halves with a shared training set to support reliable comparisons. Their results are close across the two splits, while mart and logitboost show some sensitivity to tree size.

  • Dataset construction: Poker25kT1 and Poker25kT2 split the original 1000000-sample test set into two equal parts while sharing the same training set.Each dataset uses one half for testing, and the other dataset’s test set serves as validation when parameter sensitivity matters.
  • Experimental setup: Tables 6 and 7 report test mis-classification errors for J ∈ {4, 6, 8, 10, 12, 14, 16, 18, 20}, ν ∈ {0.04, 0.06, 0.08, 0.1}, and M = 10000.The machine-accuracy stopping condition is not reached for these experiments.
  • Cross-split comparison: Corresponding entries across Poker25kT1 and Poker25kT2 are very close, supporting reliable results from the four boosting algorithms on this dataset.Unlike Mnist10k, test errors—especially for mart and logitboost—are slightly sensitive to J.
  • Parameter selection: For the broader summary, the authors report test errors at J = 20 and ν = 0.1 for datasets whose errors are not too parameter-sensitive, while noting that more tuning may improve results.Poker25kT1 and Poker25kT2 are excluded from this fixed-parameter reporting rule.
  • Algorithm comparisons: Across the reported results, abc-logitboost and abc-mart outperform logitboost and mart respectively, while abc-logitboost also outperforms abc-mart outside the Poker25k datasets.The corresponding comparison for logitboost versus mart is likewise reported outside Poker25kT1 and Poker25kT2.

4.6 Comparisons with SVM and Deep Learning

The paper compares its boosting algorithms with SVM and deep learning across modified MNIST datasets and finds that deep learning performs especially well on some datasets, while boosting outperforms SVM on Poker.

  • All four boosting algorithms achieve test error rates below 10% on Poker25kT1 and Poker25kT2, compared with about 40% for SVM.The SVM comparison comes from private communication.
  • The six correlated-noise datasets M-Noise1 through M-Noise6 are compared using SVM, deep learning, and four boosting algorithms.The datasets vary by degree of correlation from high to low.
  • The modified-MNIST comparison covers M-Basic, M-Rotate, M-Image, M-Rand, and M-RotImg.
  • Deep learning achieves excellent test results on datasets including M-Rand and M-Noise6.These comparisons use results from prior publications.

4.7 Test Errors versus Boosting Iterations

The paper evaluates test errors over boosting iterations on small and large datasets, emphasizing trajectory plots and reporting relative improvements of adaptive-base methods over their counterparts.

  • Test-error plots are considered more reliable than a single number for comparing boosting algorithms.
  • Test errors are plotted for Mnist10k, M-Rand, M-Image, Letter15k, Letter4k, and Letter2k through up to 10000 iterations.Training stops earlier when the training loss approaches machine accuracy.
  • For Covertype and Poker, test mis-classification errors are plotted over 5000 iterations because the machine accuracy is not reached.
  • Relative test-error improvements are reported for abc-logitboost over robust logitboost and abc-mart over mart.The comparison is made as a function of boosting iterations.

5 Conclusion

The paper introduces robust logitboost and abc-logitboost and evaluates them against other learning methods. Its experiments report strong boosting performance while noting that deep learning remains better on certain datasets.

  • Robust logitboost explicitly formulates the tree-split criterion for implementing logitboost, while abc-logitboost combines robust logitboost with abc-boost for multiclass classification.
  • Extensive experiments demonstrate the performance of abc-logitboost.
  • Comparisons with SVM and deep learning use results from prior publications.
  • Deep learning achieves performance that current boosting algorithms cannot match on certain datasets, leaving room for future improvement.

A Experiments on Binary Classification

The appendix compares robust logitboost with mart on binary-classification datasets, using fixed tree size and shrinkage settings in the reported experiments.

  • Four datasets are used to compare robust logitboost with mart for binary classification.
  • The binary-classification datasets include Forest521k, Forest100k, Mnist2Class, and IJCNN1.Mnist2Class converts MNIST into a binary problem by grouping digits 0–4 and 5–9.
  • The experiments use tree size J = 20 and shrinkage ν = 0.1.

B P-values for the Experiments on Mnist10k and M-Image

This section reports p-values for the Mnist10k and M-Image experiments, evaluating whether improvements remain significant across parameter combinations. It also provides additional experimental detail for M-Image.

  • P-values are computed for all parameter combinations to assess whether improvements are significant beyond one particular setting.The section refers readers to Sec. 4.5 for the definitions of P1, P2, P3, and P4.
  • Mnist10k: Table 12 reports the p-values for the Mnist10k experiments.
  • M-Image: The authors provide additional experimental details for M-Image because researchers asked about the boosting algorithms’ performance on that dataset.
  • M-Image: Table 13 reports the p-values for the M-Image experiments.
Loading 1203.3491v1…