PaperlayerView exact revision on arXiv

Source-linked AI summary

The return of AdaBoost.MH: multi-class Hamming trees

Balázs Kégl

arXiv:1312.6086v1cs.LG

TL;DR

AdaBoost.MH lacked an effective tree-based multiclass learner that avoided reducing the problem to K one-against-all classifications. The paper introduces factorized Hamming trees, and reports performance on par with SVMs and AOSOLogitBoost and significantly better than other known AdaBoost.MH implementations.

  • Problem

    AdaBoost.MH's simple one-against-all base learners work well with stumps, but boosting stumps is often suboptimal and training K one-against-all trees had not produced state-of-the-art results.

    Source: §1 · p. 1

  • Method

    The paper trains Hamming trees by factorizing vector-valued classifiers into an input-independent vote vector and a label-independent scalar classifier, using the scalar classifier to partition inputs at inner nodes.

    Source: §1 · p. 1

  • Results

    Hamming-tree AdaBoost.MH performs on par with SVMs and AOSOLogitBoost, and significantly better than other known AdaBoost.MH implementations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Hamming trees show that AdaBoost.MH can be one of the best off-the-shelf multiclass classifiers without reducing the problem to K one-against-all classifications.

    Source: §5 · p. 8

    The formal setup begins with balanced single-label multiclass data, with n/K examples per class.

    Source: §2.1 · p. 3

Abstract

from arXiv · show

Within the framework of AdaBoost.MH, we propose to train vector-valued decision trees to optimize the multi-class edge without reducing the multi-class problem to $K$ binary one-against-all classifications. The key element of the method is a vector-valued decision stump, factorized into an input-independent vector of length $K$ and label-independent scalar classifier. At inner tree nodes, the label-dependent vector is discarded and the binary classifier can be used for partitioning the input space into two regions. The algorithm retains the conceptual elegance, power, and computational efficiency of binary AdaBoost. In experiments it is on par with support vector machines and with the best existing multi-class boosting algorithm AOSOLogitBoost, and it is significantly better than other known implementations of AdaBoost.MH.

1. Introduction

The paper introduces Hamming trees for AdaBoost.MH, optimizing the multiclass edge without reducing the problem to K one-against-all classifiers. In experiments, this approach performs on par with SVMs and AOSOLogitBoost and significantly better than other known AdaBoost.MH implementations.

1. Introduction

  • Earlier AdaBoost.MH implementations used K loosely connected one-against-all classifiers; boosting stumps is often suboptimal, while using K decision trees had not produced state-of-the-art results.Earlier multiclass extensions AdaBoost.M1 and AdaBoost.M2 also required strong base-learner performance and had limited practical success.Source: §1 · p. 1
  • Hamming trees optimize the multiclass edge without reducing the problem to K one-against-all classifications, factorizing a vector-valued classifier into an input-independent vote vector and a label-independent scalar classifier.At inner nodes, the vote vector is discarded and the scalar binary classifier partitions the input space.Source: §1 · p. 1
  • Hamming-tree AdaBoost.MH performs on par with SVMs and AOSOLogitBoost, and significantly better than other known AdaBoost.MH implementations.The comparison is reported for experiments using an open-source package for reproducibility.Source: §1 · p. 2

2. ADABOOST.MH

The section sets up AdaBoost.MH as minimizing a weighted multiclass margin objective to control Hamming loss, then develops factorized base classifiers for efficient multiclass tree learning. Its framework covers single-label, multilabel, and multitask settings.

2.1. The multi-class setup: single-label and multi-label/multi-task

  • Label vectors encode a correct class as +1 and other classes as −1, while the representation also extends to multilabel and multitask learning.Weighted Hamming loss can weight label errors uniformly in multilabel or multitask settings or asymmetrically for single-label classification.Source: §2.1 · p. 2

2.2. ADABOOST.MH

  • AdaBoost.MH builds its final discriminant as a sum of vector-valued base classifiers while minimizing a weighted multiclass exponential margin-based error that upper-bounds Hamming loss.The algorithm seeks a discriminant with small weighted Hamming loss.Source: §2.2 · p. 3

2.3. Base learning for ADABOOST.MH

  • The base-learning objective can use any vector-valued multiclass learner, but conventional single-label trees may need to grow large to meet the weak-learning condition and can yield suboptimal results.When the condition Z(t) ≤ 1 − δ holds, the one-error is upper-bounded by the product of round objectives and becomes zero in O(log n) iterations.Source: §2.3 · p. 3

2.4. Casting the votes

  • Each factorized base classifier combines a positive coefficient, an input-independent length-K vote vector, and a label-independent scalar classifier; the scalar classifier partitions inputs while votes assign class-specific directions.The vote vector can vote for or against each class, and the coefficient decreases as the weighted error increases.Source: §2.3 · p. 3, §2.4 · p. 4
  • Factorization preserves the weak-learning condition: if a classifier combination has negative edge, complementing either its scalar classifier or vote vector yields positive edge.Source: §2.4 · p. 4
  • For decision stumps, exhaustive search over the binary cut and vote vector takes Θ(nK) time, enabling efficient Hamming-tree construction without globally maximizing the edge over both components.The optimal vote vector and coefficient can be set efficiently once the scalar classifier is given.Source: §2.4 · pp. 4–5

3. Hamming trees

Hamming trees factorize multiclass classifiers into a vote vector and a binary cut, using the cut to partition inputs while retaining the full classifier at leaves. A greedy edge-based procedure grows the tree, and additive local edges ensure positive tree edge when the local edges are positive.

3. Hamming trees

  • Single-label decision trees may need to grow large to satisfy the weak-learning condition, yet their boosted results are suboptimal for AdaBoost.MH.The passage identifies this as a limitation of the commonly used tree implementation for AdaBoost.MH.Source: §3 · p. 5
  • Factorizing each multiclass classifier into a vote vector and binary classifier lets inner nodes partition inputs using only the binary classifier while leaves retain the full classifier.The method can use any multiclass base classifier of this factorized form for tree cuts.Source: §3 · p. 5
  • Additivity of the gain over data subsets means positive local edges yield a positive tree edge, allowing any weak binary classifier to define inner cuts.Local leaf edges add up to the edge of the full tree.Source: §3 · pp. 5–6
  • The greedy procedure repeatedly splits the leaf with the greatest edge improvement, partitions its data, and trains base classifiers on the resulting leaves.A priority queue ranks candidate leaves by edge improvement.Source: §3 · pp. 5–6
  • With decision-stump base learners, tree construction takes O(nKdN) time, or O(nKd log N) when the tree is balanced.The procedure does not explicitly control tree shape.Source: §3 · p. 6

4. Experiments

Experiments evaluate Hamming trees on small and mid-sized benchmarks, image-recognition tasks, and data challenges. On the mid-sized benchmarks, Hamming trees and AOSOLogitBoost are reported as the strongest methods, while Hamming trees outperform other AdaBoost.MH implementations.

Reproducibility

  • The experiments use open-source multiboost software, and the authors planned to release configuration files, data splits, and hyperparameter-validation scripts.The software version was 1.2.Source: §4 · p. 6

Experimental data

  • The experiments cover five mid-sized and nine small UCI data sets, with the small-set comparison to Gaussian-kernel SVMs following a prior study’s setup.The mid-sized sets were selected to overlap with recent multiclass boosting studies.Source: §4 · p. 6

Hyperparameter selection

  • For small data sets, the authors use 10×10 cross-validation to tune hyperparameters and estimate generalization error, including a smoothed test error for selecting stopping time.For mid-sized data sets, they report 1×5 cross-validation; selected hyperparameters are then used to rerun AdaBoost.MH on joined training and validation data.Source: §4 · pp. 6–7

Small benchmarks

  • On small data sets, AdaBoost.MH is on par with SVMs and wins on six of nine sets, though large error bars make trends difficult to establish.The error bars reflect the small size and noisiness of these data sets.Source: Table 2 · p. 6, §4 · p. 7

Comparison protocol

  • Comparisons with several alternative boosting methods are constrained by prior papers’ incomplete hyperparameter tuning, so the authors use different comparison choices to limit bias.For some methods they report post-validated best errors; for others they use a hyperparameter choice recommended by prior work.Source: §4 · p. 8

Mid-sized benchmarks

  • Hamming trees and AOSOLogitBoost are the best algorithms on five mid-sized data sets, with Hamming trees winning all five but remaining within one standard deviation.Hamming trees are also reported as significantly better than other AdaBoost.MH implementations.Source: Table 1 · p. 7, §4 · p. 8

Image recognition

  • On MNIST, Hamming trees of stumps over pixels achieve 1.25% test error, while trees over Haar filters achieve 0.85%.The pixel-stump trees use eight inner nodes and about 50,000 iterations; the Haar-filter trees use four inner nodes and 10,000 iterations.Source: §4 · p. 8

Data challenges

  • In data challenges, Hamming trees place 17th on Kaggle emotions, achieve top-ten performance on Yahoo! Learning-to-Rank, and win the INTERSPEECH Emotion sub-challenge.The paper reports a 57% test error on Kaggle emotions and a runner-up finish in the INTERSPEECH Social Signals sub-challenge.Source: §4 · p. 8

5. Conclusion

The conclusion presents Hamming trees as a way to optimize AdaBoost.MH’s multiclass edge without reducing the task to K one-against-all classifiers. It also identifies stronger binary cuts and standard multi-label and sequence-to-sequence benchmarks as future directions.

Conclusion

  • Hamming trees optimize the multiclass edge prescribed by AdaBoost.MH without reducing the problem to K binary one-against-all classifications.The paper concludes that, without this restriction, AdaBoost.MH is one of the best off-the-shelf multiclass classifiers and retains binary AdaBoost’s conceptual elegance, power, and computational efficiency.Source: §5 · p. 8

Future directions

  • The general setup permits any binary classifier, and the authors identify stronger classifiers such as SVMs and standard multi-label and sequence-to-sequence benchmarks as future work.Decision stumps at tree nodes and leaves are described as a natural choice because of learning efficiency.Source: §5 · p. 8

A. Showing (9)

The passage links intermediate derivation steps to earlier definitions and refers to a fact used in the final step.

A. Showing (9)

  • The derivation of (16) uses the definition of h in (6), and (17) follows from the definitions of μℓ− and μℓ+ in (7) and (8).The passage also says the final step (18) uses a stated fact, without identifying that fact here.Source: A. Showing (9) · p. 10

B. Multi-class decision stumps

The section describes efficient decision-stump optimization for multiclass learning. It searches thresholds within features by edge and selects across features by energy.

B. Multi-class decision stumps

  • A decision stump is a one-decision, two-leaf tree whose decision uses a selected feature and threshold.Within each feature, the search maximizes edge; across features, the selection minimizes energy.Source: B. Multi-class decision stumps · p. 10
  • With feature values preordered, a decision stump maximizing edge can be found in Θ(ndK) time.The sorting can be done once for all features outside the boosting loop.Source: B. Multi-class decision stumps · p. 10, Figure 3 · p. 11
  • As a threshold moves across sorted values, each classwise edge changes by ±w_i,ℓ, and the optimal-vote total edge is the sum of absolute classwise edges.This update is the main computational trick in BESTSTUMP.Source: B. Multi-class decision stumps · p. 10
  • BESTSTUMP tests thresholds halfway between distinct sorted feature values and returns the threshold and vote vector maximizing the edge.STUMPBASE then sets the coefficient and selects across features by minimizing energy.Source: B. Multi-class decision stumps · p. 10, Figure 3 · p. 11

C. Cutting the data set

A scalar binary classifier partitions the data matrices X, Y, and W by the sign of its classification. The accompanying edge update changes γℓ according to the label condition.

C. Cutting the data set

  • A scalar binary classifier partitions X, Y, and W according to the sign of ϕ(xi).This is the basic operation for adding a tree node.Source: C. Cutting the data set · p. 11, Figure 5 · p. 12
  • When yi,ℓ=1, γℓ decreases by 2wi,ℓ; when yi=−1, γℓ increases by 2wi,ℓ.Figure 4 describes this update in line 5 of BESTSTUMP.Source: Figure 4 · p. 12
Loading 1312.6086v1…