K-hyperplane Hinge-Minimax Classifier

Margarita Osadchy, Tamir Hazan, Daniel Keren
Proceedings of the 32nd International Conference on Machine Learning, PMLR 37:1558-1566, 2015.

Abstract

We explore a novel approach to upper bound the misclassification error for problems with data comprising a small number of positive samples and a large number of negative samples. We assign the hinge-loss to upper bound the misclassification error of the positive examples and use the minimax risk to upper bound the misclassification error with respect to the worst case distribution that generates the negative examples. This approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, in contrast to kernel SVM which produces a very large number of support vectors in such settings. We derive empirical risk bounds for linear and non-linear classification and show that they are dimensionally independent and decay as 1/\sqrtm for m samples. We propose an efficient algorithm for training an intersection of finite number of hyperplane and demonstrate its effectiveness on real data, including letter and scene recognition.

Cite this Paper

BibTeX
@InProceedings{pmlr-v37-osadchy15, title = {K-hyperplane Hinge-Minimax Classifier}, author = {Osadchy, Margarita and Hazan, Tamir and Keren, Daniel}, booktitle = {Proceedings of the 32nd International Conference on Machine Learning}, pages = {1558--1566}, 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/osadchy15.pdf}, url = {https://proceedings.mlr.press/v37/osadchy15.html}, abstract = {We explore a novel approach to upper bound the misclassification error for problems with data comprising a small number of positive samples and a large number of negative samples. We assign the hinge-loss to upper bound the misclassification error of the positive examples and use the minimax risk to upper bound the misclassification error with respect to the worst case distribution that generates the negative examples. This approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, in contrast to kernel SVM which produces a very large number of support vectors in such settings. We derive empirical risk bounds for linear and non-linear classification and show that they are dimensionally independent and decay as 1/\sqrtm for m samples. We propose an efficient algorithm for training an intersection of finite number of hyperplane and demonstrate its effectiveness on real data, including letter and scene recognition.} }
Endnote
%0 Conference Paper %T K-hyperplane Hinge-Minimax Classifier %A Margarita Osadchy %A Tamir Hazan %A Daniel Keren %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-osadchy15 %I PMLR %P 1558--1566 %U https://proceedings.mlr.press/v37/osadchy15.html %V 37 %X We explore a novel approach to upper bound the misclassification error for problems with data comprising a small number of positive samples and a large number of negative samples. We assign the hinge-loss to upper bound the misclassification error of the positive examples and use the minimax risk to upper bound the misclassification error with respect to the worst case distribution that generates the negative examples. This approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, in contrast to kernel SVM which produces a very large number of support vectors in such settings. We derive empirical risk bounds for linear and non-linear classification and show that they are dimensionally independent and decay as 1/\sqrtm for m samples. We propose an efficient algorithm for training an intersection of finite number of hyperplane and demonstrate its effectiveness on real data, including letter and scene recognition.
RIS
TY - CPAPER TI - K-hyperplane Hinge-Minimax Classifier AU - Margarita Osadchy AU - Tamir Hazan AU - Daniel Keren BT - Proceedings of the 32nd International Conference on Machine Learning DA - 2015/06/01 ED - Francis Bach ED - David Blei ID - pmlr-v37-osadchy15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 37 SP - 1558 EP - 1566 L1 - http://proceedings.mlr.press/v37/osadchy15.pdf UR - https://proceedings.mlr.press/v37/osadchy15.html AB - We explore a novel approach to upper bound the misclassification error for problems with data comprising a small number of positive samples and a large number of negative samples. We assign the hinge-loss to upper bound the misclassification error of the positive examples and use the minimax risk to upper bound the misclassification error with respect to the worst case distribution that generates the negative examples. This approach is computationally appealing since the majority of training examples (belonging to the negative class) are represented by the statistics of their distribution, in contrast to kernel SVM which produces a very large number of support vectors in such settings. We derive empirical risk bounds for linear and non-linear classification and show that they are dimensionally independent and decay as 1/\sqrtm for m samples. We propose an efficient algorithm for training an intersection of finite number of hyperplane and demonstrate its effectiveness on real data, including letter and scene recognition. ER -
APA
Osadchy, M., Hazan, T. & Keren, D.. (2015). K-hyperplane Hinge-Minimax Classifier. Proceedings of the 32nd International Conference on Machine Learning, in Proceedings of Machine Learning Research 37:1558-1566 Available from https://proceedings.mlr.press/v37/osadchy15.html.

Related Material