PD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification

Ian En-Hsu Yen, Xiangru Huang, Pradeep Ravikumar, Kai Zhong, Inderjit Dhillon
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:3069-3077, 2016.

Abstract

We consider Multiclass and Multilabel classification with extremely large number of classes, of which only few are labeled to each instance. In such setting, standard methods that have training, prediction cost linear to the number of classes become intractable. State-of-the-art methods thus aim to reduce the complexity by exploiting correlation between labels under assumption that the similarity between labels can be captured by structures such as low-rank matrix or balanced tree. However, as the diversity of labels increases in the feature space, structural assumption can be easily violated, which leads to degrade in the testing performance. In this work, we show that a margin-maximizing loss with l1 penalty, in case of Extreme Classification, yields extremely sparse solution both in primal and in dual without sacrificing the expressive power of predictor. We thus propose a Fully-Corrective Block-Coordinate Frank-Wolfe (FC-BCFW) algorithm that exploits both primal and dual sparsity to achieve a complexity sublinear to the number of primal and dual variables. A bi-stochastic search method is proposed to further improve the efficiency. In our experiments on both Multiclass and Multilabel problems, the proposed method achieves significant higher accuracy than existing approaches of Extreme Classification with very competitive training and prediction time.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-yenb16, title = {PD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification}, author = {Yen, Ian En-Hsu and Huang, Xiangru and Ravikumar, Pradeep and Zhong, Kai and Dhillon, Inderjit}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {3069--3077}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/yenb16.pdf}, url = {https://proceedings.mlr.press/v48/yenb16.html}, abstract = {We consider Multiclass and Multilabel classification with extremely large number of classes, of which only few are labeled to each instance. In such setting, standard methods that have training, prediction cost linear to the number of classes become intractable. State-of-the-art methods thus aim to reduce the complexity by exploiting correlation between labels under assumption that the similarity between labels can be captured by structures such as low-rank matrix or balanced tree. However, as the diversity of labels increases in the feature space, structural assumption can be easily violated, which leads to degrade in the testing performance. In this work, we show that a margin-maximizing loss with l1 penalty, in case of Extreme Classification, yields extremely sparse solution both in primal and in dual without sacrificing the expressive power of predictor. We thus propose a Fully-Corrective Block-Coordinate Frank-Wolfe (FC-BCFW) algorithm that exploits both primal and dual sparsity to achieve a complexity sublinear to the number of primal and dual variables. A bi-stochastic search method is proposed to further improve the efficiency. In our experiments on both Multiclass and Multilabel problems, the proposed method achieves significant higher accuracy than existing approaches of Extreme Classification with very competitive training and prediction time.} }
Endnote
%0 Conference Paper %T PD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification %A Ian En-Hsu Yen %A Xiangru Huang %A Pradeep Ravikumar %A Kai Zhong %A Inderjit Dhillon %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-yenb16 %I PMLR %P 3069--3077 %U https://proceedings.mlr.press/v48/yenb16.html %V 48 %X We consider Multiclass and Multilabel classification with extremely large number of classes, of which only few are labeled to each instance. In such setting, standard methods that have training, prediction cost linear to the number of classes become intractable. State-of-the-art methods thus aim to reduce the complexity by exploiting correlation between labels under assumption that the similarity between labels can be captured by structures such as low-rank matrix or balanced tree. However, as the diversity of labels increases in the feature space, structural assumption can be easily violated, which leads to degrade in the testing performance. In this work, we show that a margin-maximizing loss with l1 penalty, in case of Extreme Classification, yields extremely sparse solution both in primal and in dual without sacrificing the expressive power of predictor. We thus propose a Fully-Corrective Block-Coordinate Frank-Wolfe (FC-BCFW) algorithm that exploits both primal and dual sparsity to achieve a complexity sublinear to the number of primal and dual variables. A bi-stochastic search method is proposed to further improve the efficiency. In our experiments on both Multiclass and Multilabel problems, the proposed method achieves significant higher accuracy than existing approaches of Extreme Classification with very competitive training and prediction time.
RIS
TY - CPAPER TI - PD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification AU - Ian En-Hsu Yen AU - Xiangru Huang AU - Pradeep Ravikumar AU - Kai Zhong AU - Inderjit Dhillon BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-yenb16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 3069 EP - 3077 L1 - http://proceedings.mlr.press/v48/yenb16.pdf UR - https://proceedings.mlr.press/v48/yenb16.html AB - We consider Multiclass and Multilabel classification with extremely large number of classes, of which only few are labeled to each instance. In such setting, standard methods that have training, prediction cost linear to the number of classes become intractable. State-of-the-art methods thus aim to reduce the complexity by exploiting correlation between labels under assumption that the similarity between labels can be captured by structures such as low-rank matrix or balanced tree. However, as the diversity of labels increases in the feature space, structural assumption can be easily violated, which leads to degrade in the testing performance. In this work, we show that a margin-maximizing loss with l1 penalty, in case of Extreme Classification, yields extremely sparse solution both in primal and in dual without sacrificing the expressive power of predictor. We thus propose a Fully-Corrective Block-Coordinate Frank-Wolfe (FC-BCFW) algorithm that exploits both primal and dual sparsity to achieve a complexity sublinear to the number of primal and dual variables. A bi-stochastic search method is proposed to further improve the efficiency. In our experiments on both Multiclass and Multilabel problems, the proposed method achieves significant higher accuracy than existing approaches of Extreme Classification with very competitive training and prediction time. ER -
APA
Yen, I.E., Huang, X., Ravikumar, P., Zhong, K. & Dhillon, I.. (2016). PD-Sparse : A Primal and Dual Sparse Approach to Extreme Multiclass and Multilabel Classification. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:3069-3077 Available from https://proceedings.mlr.press/v48/yenb16.html.

Related Material