K-hyperplane Hinge-Minimax Classifier
Margarita Osadchy, Tamir Hazan, Daniel Keren · 2015
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 as-sign the hinge-loss to upper bound the misclas-sification error of the positive examples and use the minimax risk to upper bound the misclassifi-cation error with respect to the worst case distri-bution 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 classifica-tion and show that they are dimensionally inde-pendent and decay as 1/ m form samples. We propose an efficient algorithm for training an in-tersection of finite number of hyperplanes and demonstrate its effectiveness on real data, includ-ing letter and scene recognition. 1.