Characterizing inverse time dependency in multi-class learning

Danqi Chen, Weizhu Chen, Qiang Yang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

The training time of most learning algorithms increases as the size of training data increases. Yet, recent advances in linear binary SVM and LR challenge this commonsense by proposing an inverse dependency property, where the training time decreases as the size of training data increases. In this paper, we study the inverse dependency property of multi-class classification problem. We describe a general framework for multi-class classification problem with a single objective to achieve inverse dependency and extend it to three popular multi-class algorithms. We present theoretical results demonstrating its convergence and inverse dependency guarantee. We conduct experiments to empirically verify the inverse dependency of all the three algorithms on large-scale datasets as well as to ensure the accuracy.

Original languageEnglish (US)
Title of host publicationProceedings - 11th IEEE International Conference on Data Mining, ICDM 2011
Pages1020-1025
Number of pages6
DOIs
StatePublished - 2011
Externally publishedYes
Event11th IEEE International Conference on Data Mining, ICDM 2011 - Vancouver, BC, Canada
Duration: Dec 11 2011Dec 14 2011

Publication series

NameProceedings - IEEE International Conference on Data Mining, ICDM
ISSN (Print)1550-4786

Conference

Conference11th IEEE International Conference on Data Mining, ICDM 2011
CountryCanada
CityVancouver, BC
Period12/11/1112/14/11

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Keywords

  • Inverse dependency
  • Large-scale classification
  • Multi-class learning
  • Supervised learning

Fingerprint Dive into the research topics of 'Characterizing inverse time dependency in multi-class learning'. Together they form a unique fingerprint.

  • Cite this

    Chen, D., Chen, W., & Yang, Q. (2011). Characterizing inverse time dependency in multi-class learning. In Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011 (pp. 1020-1025). [6137308] (Proceedings - IEEE International Conference on Data Mining, ICDM). https://doi.org/10.1109/ICDM.2011.32