On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems

Harish G. Ramaswamy, Balaji Srinivasan Babu, Shivani Agarwal, Robert C. Williamson
Proceedings of The 27th Conference on Learning Theory, PMLR 35:885-902, 2014.

Abstract

A popular approach to solving multiclass learning problems is to reduce them to a set of binary classification problems through some output code matrix: the widely used one-vs-all and all-pairs methods, and the error-correcting output code methods of Dietterich and Bakiri (1995), can all be viewed as special cases of this approach. In this paper, we consider the question of statistical consistency of such methods. We focus on settings where the binary problems are solved by minimizing a binary surrogate loss, and derive general conditions on the binary surrogate loss under which the one-vs-all and all-pairs code matrices yield consistent algorithms with respect to the multiclass 0-1 loss. We then consider general multiclass learning problems defined by a general multiclass loss, and derive conditions on the output code matrix and binary surrogates under which the resulting algorithm is consistent with respect to the target multiclass loss. We also consider \emphprobabilistic code matrices, where one reduces a multiclass problem to a set of \emphclass probability labeled binary problems, and show that these can yield benefits in the sense of requiring a smaller number of binary problems to achieve overall consistency. Our analysis makes interesting connections with the theory of proper composite losses (Buja et al., 2005; Reid and Williamson, 2010); these play a role in constructing the right ‘decoding’ for converting the predictions on the binary problems to the final multiclass prediction. To our knowledge, this is the first work that comprehensively studies consistency properties of output code based methods for multiclass learning.

Cite this Paper

BibTeX
@InProceedings{pmlr-v35-ramaswamy14, title = {On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems}, author = {Ramaswamy, Harish G. and Srinivasan Babu, Balaji and Agarwal, Shivani and Williamson, Robert C.}, booktitle = {Proceedings of The 27th Conference on Learning Theory}, pages = {885--902}, year = {2014}, editor = {Balcan, Maria Florina and Feldman, Vitaly and Szepesvári, Csaba}, volume = {35}, series = {Proceedings of Machine Learning Research}, address = {Barcelona, Spain}, month = {13--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v35/ramaswamy14.pdf}, url = {https://proceedings.mlr.press/v35/ramaswamy14.html}, abstract = {A popular approach to solving multiclass learning problems is to reduce them to a set of binary classification problems through some output code matrix: the widely used one-vs-all and all-pairs methods, and the error-correcting output code methods of Dietterich and Bakiri (1995), can all be viewed as special cases of this approach. In this paper, we consider the question of statistical consistency of such methods. We focus on settings where the binary problems are solved by minimizing a binary surrogate loss, and derive general conditions on the binary surrogate loss under which the one-vs-all and all-pairs code matrices yield consistent algorithms with respect to the multiclass 0-1 loss. We then consider general multiclass learning problems defined by a general multiclass loss, and derive conditions on the output code matrix and binary surrogates under which the resulting algorithm is consistent with respect to the target multiclass loss. We also consider \emphprobabilistic code matrices, where one reduces a multiclass problem to a set of \emphclass probability labeled binary problems, and show that these can yield benefits in the sense of requiring a smaller number of binary problems to achieve overall consistency. Our analysis makes interesting connections with the theory of proper composite losses (Buja et al., 2005; Reid and Williamson, 2010); these play a role in constructing the right ‘decoding’ for converting the predictions on the binary problems to the final multiclass prediction. To our knowledge, this is the first work that comprehensively studies consistency properties of output code based methods for multiclass learning.} }
Endnote
%0 Conference Paper %T On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems %A Harish G. Ramaswamy %A Balaji Srinivasan Babu %A Shivani Agarwal %A Robert C. Williamson %B Proceedings of The 27th Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2014 %E Maria Florina Balcan %E Vitaly Feldman %E Csaba Szepesvári %F pmlr-v35-ramaswamy14 %I PMLR %P 885--902 %U https://proceedings.mlr.press/v35/ramaswamy14.html %V 35 %X A popular approach to solving multiclass learning problems is to reduce them to a set of binary classification problems through some output code matrix: the widely used one-vs-all and all-pairs methods, and the error-correcting output code methods of Dietterich and Bakiri (1995), can all be viewed as special cases of this approach. In this paper, we consider the question of statistical consistency of such methods. We focus on settings where the binary problems are solved by minimizing a binary surrogate loss, and derive general conditions on the binary surrogate loss under which the one-vs-all and all-pairs code matrices yield consistent algorithms with respect to the multiclass 0-1 loss. We then consider general multiclass learning problems defined by a general multiclass loss, and derive conditions on the output code matrix and binary surrogates under which the resulting algorithm is consistent with respect to the target multiclass loss. We also consider \emphprobabilistic code matrices, where one reduces a multiclass problem to a set of \emphclass probability labeled binary problems, and show that these can yield benefits in the sense of requiring a smaller number of binary problems to achieve overall consistency. Our analysis makes interesting connections with the theory of proper composite losses (Buja et al., 2005; Reid and Williamson, 2010); these play a role in constructing the right ‘decoding’ for converting the predictions on the binary problems to the final multiclass prediction. To our knowledge, this is the first work that comprehensively studies consistency properties of output code based methods for multiclass learning.
RIS
TY - CPAPER TI - On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems AU - Harish G. Ramaswamy AU - Balaji Srinivasan Babu AU - Shivani Agarwal AU - Robert C. Williamson BT - Proceedings of The 27th Conference on Learning Theory DA - 2014/05/29 ED - Maria Florina Balcan ED - Vitaly Feldman ED - Csaba Szepesvári ID - pmlr-v35-ramaswamy14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 35 SP - 885 EP - 902 L1 - http://proceedings.mlr.press/v35/ramaswamy14.pdf UR - https://proceedings.mlr.press/v35/ramaswamy14.html AB - A popular approach to solving multiclass learning problems is to reduce them to a set of binary classification problems through some output code matrix: the widely used one-vs-all and all-pairs methods, and the error-correcting output code methods of Dietterich and Bakiri (1995), can all be viewed as special cases of this approach. In this paper, we consider the question of statistical consistency of such methods. We focus on settings where the binary problems are solved by minimizing a binary surrogate loss, and derive general conditions on the binary surrogate loss under which the one-vs-all and all-pairs code matrices yield consistent algorithms with respect to the multiclass 0-1 loss. We then consider general multiclass learning problems defined by a general multiclass loss, and derive conditions on the output code matrix and binary surrogates under which the resulting algorithm is consistent with respect to the target multiclass loss. We also consider \emphprobabilistic code matrices, where one reduces a multiclass problem to a set of \emphclass probability labeled binary problems, and show that these can yield benefits in the sense of requiring a smaller number of binary problems to achieve overall consistency. Our analysis makes interesting connections with the theory of proper composite losses (Buja et al., 2005; Reid and Williamson, 2010); these play a role in constructing the right ‘decoding’ for converting the predictions on the binary problems to the final multiclass prediction. To our knowledge, this is the first work that comprehensively studies consistency properties of output code based methods for multiclass learning. ER -
APA
Ramaswamy, H.G., Srinivasan Babu, B., Agarwal, S. & Williamson, R.C.. (2014). On the Consistency of Output Code Based Learning Algorithms for Multiclass Learning Problems. Proceedings of The 27th Conference on Learning Theory, in Proceedings of Machine Learning Research 35:885-902 Available from https://proceedings.mlr.press/v35/ramaswamy14.html.

Related Material