Discrete Chebyshev Classifiers

Elad Eban, Elad Mezuman, Amir Globerson
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1233-1241, 2014.

Abstract

In large scale learning problems it is often easy to collect simple statistics of the data, but hard or impractical to store all the original data. A key question in this setting is how to construct classifiers based on such partial information. One traditional approach to the problem has been to use maximum entropy arguments to induce a complete distribution on variables from statistics. However, this approach essentially makes conditional independence assumptions about the distribution, and furthermore does not optimize prediction loss. Here we present a framework for discriminative learning given a set of statistics. Specifically, we address the case where all variables are discrete and we have access to various marginals. Our approach minimizes the worst case hinge loss in this case, which upper bounds the generalization error. We show that for certain sets of statistics the problem is tractable, and in the general case can be approximated using MAP LP relaxations. Empirical results show that the method is competitive with other approaches that use the same input.

Cite this Paper

BibTeX
@InProceedings{pmlr-v32-eban14, title = {Discrete Chebyshev Classifiers}, author = {Eban, Elad and Mezuman, Elad and Globerson, Amir}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1233--1241}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/eban14.pdf}, url = {https://proceedings.mlr.press/v32/eban14.html}, abstract = {In large scale learning problems it is often easy to collect simple statistics of the data, but hard or impractical to store all the original data. A key question in this setting is how to construct classifiers based on such partial information. One traditional approach to the problem has been to use maximum entropy arguments to induce a complete distribution on variables from statistics. However, this approach essentially makes conditional independence assumptions about the distribution, and furthermore does not optimize prediction loss. Here we present a framework for discriminative learning given a set of statistics. Specifically, we address the case where all variables are discrete and we have access to various marginals. Our approach minimizes the worst case hinge loss in this case, which upper bounds the generalization error. We show that for certain sets of statistics the problem is tractable, and in the general case can be approximated using MAP LP relaxations. Empirical results show that the method is competitive with other approaches that use the same input.} }
Endnote
%0 Conference Paper %T Discrete Chebyshev Classifiers %A Elad Eban %A Elad Mezuman %A Amir Globerson %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-eban14 %I PMLR %P 1233--1241 %U https://proceedings.mlr.press/v32/eban14.html %V 32 %N 2 %X In large scale learning problems it is often easy to collect simple statistics of the data, but hard or impractical to store all the original data. A key question in this setting is how to construct classifiers based on such partial information. One traditional approach to the problem has been to use maximum entropy arguments to induce a complete distribution on variables from statistics. However, this approach essentially makes conditional independence assumptions about the distribution, and furthermore does not optimize prediction loss. Here we present a framework for discriminative learning given a set of statistics. Specifically, we address the case where all variables are discrete and we have access to various marginals. Our approach minimizes the worst case hinge loss in this case, which upper bounds the generalization error. We show that for certain sets of statistics the problem is tractable, and in the general case can be approximated using MAP LP relaxations. Empirical results show that the method is competitive with other approaches that use the same input.
RIS
TY - CPAPER TI - Discrete Chebyshev Classifiers AU - Elad Eban AU - Elad Mezuman AU - Amir Globerson BT - Proceedings of the 31st International Conference on Machine Learning DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-eban14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1233 EP - 1241 L1 - http://proceedings.mlr.press/v32/eban14.pdf UR - https://proceedings.mlr.press/v32/eban14.html AB - In large scale learning problems it is often easy to collect simple statistics of the data, but hard or impractical to store all the original data. A key question in this setting is how to construct classifiers based on such partial information. One traditional approach to the problem has been to use maximum entropy arguments to induce a complete distribution on variables from statistics. However, this approach essentially makes conditional independence assumptions about the distribution, and furthermore does not optimize prediction loss. Here we present a framework for discriminative learning given a set of statistics. Specifically, we address the case where all variables are discrete and we have access to various marginals. Our approach minimizes the worst case hinge loss in this case, which upper bounds the generalization error. We show that for certain sets of statistics the problem is tractable, and in the general case can be approximated using MAP LP relaxations. Empirical results show that the method is competitive with other approaches that use the same input. ER -
APA
Eban, E., Mezuman, E. & Globerson, A.. (2014). Discrete Chebyshev Classifiers. Proceedings of the 31st International Conference on Machine Learning, in Proceedings of Machine Learning Research 32(2):1233-1241 Available from https://proceedings.mlr.press/v32/eban14.html.

Related Material