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 -