Characterizing inverse time dependency in multi-class learning

Danqi Chen; Weizhu Chen; Qiang Yang

doi:10.1109/ICDM.2011.32

Characterizing inverse time dependency in multi-class learning

Danqi Chen, Weizhu Chen, Qiang Yang

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011
Pages	1020-1025
Number of pages	6
DOIs	https://doi.org/10.1109/ICDM.2011.32
State	Published - 2011
Externally published	Yes
Event	11th IEEE International Conference on Data Mining, ICDM 2011 - Vancouver, BC, Canada Duration: Dec 11 2011 → Dec 14 2011

Publication series

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

Conference

Conference	11th IEEE International Conference on Data Mining, ICDM 2011
Country	Canada
City	Vancouver, BC
Period	12/11/11 → 12/14/11

All Science Journal Classification (ASJC) codes

Engineering(all)

Keywords

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

Access to Document

10.1109/ICDM.2011.32

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

Cite this

@inproceedings{3e5223fd0ffb49fcb09f6980ae1d3b29,

title = "Characterizing inverse time dependency in multi-class learning",

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.",

keywords = "Inverse dependency, Large-scale classification, Multi-class learning, Supervised learning",

author = "Danqi Chen and Weizhu Chen and Qiang Yang",

year = "2011",

doi = "10.1109/ICDM.2011.32",

language = "English (US)",

isbn = "9780769544083",

series = "Proceedings - IEEE International Conference on Data Mining, ICDM",

pages = "1020--1025",

booktitle = "Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011",

note = "11th IEEE International Conference on Data Mining, ICDM 2011 ; Conference date: 11-12-2011 Through 14-12-2011",

}

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., 6137308, Proceedings - IEEE International Conference on Data Mining, ICDM, pp. 1020-1025, 11th IEEE International Conference on Data Mining, ICDM 2011, Vancouver, BC, Canada, 12/11/11. https://doi.org/10.1109/ICDM.2011.32

TY - GEN

T1 - Characterizing inverse time dependency in multi-class learning

AU - Chen, Danqi

AU - Chen, Weizhu

AU - Yang, Qiang

PY - 2011

Y1 - 2011

N2 - 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.

AB - 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.

KW - Inverse dependency

KW - Large-scale classification

KW - Multi-class learning

KW - Supervised learning

UR - http://www.scopus.com/inward/record.url?scp=84863156480&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84863156480&partnerID=8YFLogxK

U2 - 10.1109/ICDM.2011.32

DO - 10.1109/ICDM.2011.32

M3 - Conference contribution

AN - SCOPUS:84863156480

SN - 9780769544083

T3 - Proceedings - IEEE International Conference on Data Mining, ICDM

SP - 1020

EP - 1025

BT - Proceedings - 11th IEEE International Conference on Data Mining, ICDM 2011

T2 - 11th IEEE International Conference on Data Mining, ICDM 2011

Y2 - 11 December 2011 through 14 December 2011

ER -