Convex Calibrated Surrogates for Hierarchical Classification

Harish Ramaswamy, Ambuj Tewari, Shivani Agarwal
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1852-1860, 2015.

Abstract

Hierarchical classification problems are multiclass supervised learning problems with a pre-defined hierarchy over the set of class labels. In this work, we study the consistency of hierarchical classification algorithms with respect to a natural loss, namely the tree distance metric on the hierarchy tree of class labels, via the usage of calibrated surrogates. We first show that the Bayes optimal classifier for this loss classifies an instance according to the deepest node in the hierarchy such that the total conditional probability of the subtree rooted at the node is greater than \frac12. We exploit this insight to develop new consistent algorithm for hierarchical classification, that makes use of an algorithm known to be consistent for the “multiclass classification with reject option (MCRO)” problem as a sub-routine. Our experiments on a number of benchmark datasets show that the resulting algorithm, which we term OvA-Cascade, gives improved performance over other state-of-the-art hierarchical classification algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-ramaswamy15, title = {Convex Calibrated Surrogates for Hierarchical Classification}, author = {Ramaswamy, Harish and Tewari, Ambuj and Agarwal, Shivani}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1852--1860}, year = {2015}, editor = {Bach, Francis and Blei, David}, volume = {37}, series = {Proceedings of Machine Learning Research}, address = {Lille, France}, month = {07--09 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v37/ramaswamy15.pdf}, url = {https://proceedings.mlr.press/v37/ramaswamy15.html}, abstract = {Hierarchical classification problems are multiclass supervised learning problems with a pre-defined hierarchy over the set of class labels. In this work, we study the consistency of hierarchical classification algorithms with respect to a natural loss, namely the tree distance metric on the hierarchy tree of class labels, via the usage of calibrated surrogates. We first show that the Bayes optimal classifier for this loss classifies an instance according to the deepest node in the hierarchy such that the total conditional probability of the subtree rooted at the node is greater than \frac12. We exploit this insight to develop new consistent algorithm for hierarchical classification, that makes use of an algorithm known to be consistent for the “multiclass classification with reject option (MCRO)” problem as a sub-routine. Our experiments on a number of benchmark datasets show that the resulting algorithm, which we term OvA-Cascade, gives improved performance over other state-of-the-art hierarchical classification algorithms.} }
Endnote
%0 Conference Paper %T Convex Calibrated Surrogates for Hierarchical Classification %A Harish Ramaswamy %A Ambuj Tewari %A Shivani Agarwal %B Proceedings of the 32nd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2015 %E Francis Bach %E David Blei %F pmlr-v37-ramaswamy15 %I PMLR %P 1852--1860 %U https://proceedings.mlr.press/v37/ramaswamy15.html %V 37 %X Hierarchical classification problems are multiclass supervised learning problems with a pre-defined hierarchy over the set of class labels. In this work, we study the consistency of hierarchical classification algorithms with respect to a natural loss, namely the tree distance metric on the hierarchy tree of class labels, via the usage of calibrated surrogates. We first show that the Bayes optimal classifier for this loss classifies an instance according to the deepest node in the hierarchy such that the total conditional probability of the subtree rooted at the node is greater than \frac12. We exploit this insight to develop new consistent algorithm for hierarchical classification, that makes use of an algorithm known to be consistent for the “multiclass classification with reject option (MCRO)” problem as a sub-routine. Our experiments on a number of benchmark datasets show that the resulting algorithm, which we term OvA-Cascade, gives improved performance over other state-of-the-art hierarchical classification algorithms.
RIS
TY - CPAPER TI - Convex Calibrated Surrogates for Hierarchical Classification AU - Harish Ramaswamy AU - Ambuj Tewari AU - Shivani Agarwal BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-ramaswamy15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1852 EP - 1860 L1 - http://proceedings.mlr.press/v37/ramaswamy15.pdf UR - https://proceedings.mlr.press/v37/ramaswamy15.html AB - Hierarchical classification problems are multiclass supervised learning problems with a pre-defined hierarchy over the set of class labels. In this work, we study the consistency of hierarchical classification algorithms with respect to a natural loss, namely the tree distance metric on the hierarchy tree of class labels, via the usage of calibrated surrogates. We first show that the Bayes optimal classifier for this loss classifies an instance according to the deepest node in the hierarchy such that the total conditional probability of the subtree rooted at the node is greater than \frac12. We exploit this insight to develop new consistent algorithm for hierarchical classification, that makes use of an algorithm known to be consistent for the “multiclass classification with reject option (MCRO)” problem as a sub-routine. Our experiments on a number of benchmark datasets show that the resulting algorithm, which we term OvA-Cascade, gives improved performance over other state-of-the-art hierarchical classification algorithms. ER -
APA
Ramaswamy, H., Tewari, A. & Agarwal, S.. (2015). Convex Calibrated Surrogates for Hierarchical Classification. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1852-1860 Available from https://proceedings.mlr.press/v37/ramaswamy15.html.

Related Material