Logarithmic Time One-Against-Some

Hal Daumé III, Nikos Karampatziakis, John Langford, Paul Mineiro
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:923-932, 2017.

Abstract

We create a new online reduction of multiclass classification to binary classification for which training and prediction time scale logarithmically with the number of classes. We show that several simple techniques give rise to an algorithm which is superior to previous logarithmic time classification approaches while competing with one-against-all in space. The core construction is based on using a tree to select a small subset of labels with high recall, which are then scored using a one-against-some structure with high precision.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-daume17a, title = {Logarithmic Time One-Against-Some}, author = {Daum{\'e}, III, Hal and Nikos Karampatziakis and John Langford and Paul Mineiro}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {923--932}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/daume17a/daume17a.pdf}, url = {https://proceedings.mlr.press/v70/daume17a.html}, abstract = {We create a new online reduction of multiclass classification to binary classification for which training and prediction time scale logarithmically with the number of classes. We show that several simple techniques give rise to an algorithm which is superior to previous logarithmic time classification approaches while competing with one-against-all in space. The core construction is based on using a tree to select a small subset of labels with high recall, which are then scored using a one-against-some structure with high precision.} }
Endnote
%0 Conference Paper %T Logarithmic Time One-Against-Some %A Hal Daumé, III %A Nikos Karampatziakis %A John Langford %A Paul Mineiro %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-daume17a %I PMLR %P 923--932 %U https://proceedings.mlr.press/v70/daume17a.html %V 70 %X We create a new online reduction of multiclass classification to binary classification for which training and prediction time scale logarithmically with the number of classes. We show that several simple techniques give rise to an algorithm which is superior to previous logarithmic time classification approaches while competing with one-against-all in space. The core construction is based on using a tree to select a small subset of labels with high recall, which are then scored using a one-against-some structure with high precision.
APA
Daumé, III, H., Karampatziakis, N., Langford, J. & Mineiro, P.. (2017). Logarithmic Time One-Against-Some. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:923-932 Available from https://proceedings.mlr.press/v70/daume17a.html.

Related Material