Extreme multiclass classification criteria

Anna Choromanska, Ish Kumar Jain

Research output: Contribution to journalArticlepeer-review


We analyze the theoretical properties of the recently proposed objective function for efficient online construction and training of multiclass classification trees in the settings where the label space is very large. We show the important properties of this objective and provide a complete proof that maximizing it simultaneously encourages balanced trees and improves the purity of the class distributions at subsequent levels in the tree. We further explore its connection to the three well-known entropy-based decision tree criteria, i.e., Shannon entropy, Gini-entropy and its modified variant, for which efficient optimization strategies are largely unknown in the extreme multiclass setting. We show theoretically that this objective can be viewed as a surrogate function for all of these entropy criteria and that maximizing it indirectly optimizes them as well. We derive boosting guarantees and obtain a closed-form expression for the number of iterations needed to reduce the considered entropy criteria below an arbitrary threshold. The obtained theorem relies on a weak hypothesis assumption that directly depends on the considered objective function. Finally, we prove that optimizing the objective directly reduces the multi-class classification error of the decision tree.

Original languageEnglish (US)
Article number16
Issue number1
StatePublished - Mar 2019


  • Boosting
  • Decision trees
  • Multiclass classification

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Extreme multiclass classification criteria'. Together they form a unique fingerprint.

Cite this