Large-margin Convex Polytope Machine
Title | Large-margin Convex Polytope Machine |
Publication Type | Conference Paper |
Year of Publication | 2014 |
Authors | Kantchelian, A., Tschantz M. Carl, Huang L., Bartlett P. L., Joseph A. D., & Tygar J.D.. |
Published in | Proceedings of the 27th International Conference on Neural Information Processing Systems |
Page(s) | 3248–3256 |
Publisher | MIT Press |
Place Published | Cambridge, MA, USA |
Abstract | We present the Convex Polytope Machine (CPM), a novel non-linear learning algorithm for large-scale binary classification tasks. The CPM finds a large margin convex polytope separator which encloses one class. We develop a stochastic gradient descent based algorithm that is amenable to massive datasets, and augment it with a heuristic procedure to avoid sub-optimal local minima. Our experimental evaluations of the CPM on large-scale datasets from distinct domains (MNIST handwritten digit recognition, text topic, and web security) demonstrate that the CPM trains models faster, sometimes several orders of magnitude, than state-of-the-art similar approaches and kernel-SVM methods while achieving comparable or better classification performance. Our empirical results suggest that, unlike prior similar approaches, we do not need to control the number of sub-classifiers (sides of the polytope) to avoid overfitting. |
URL | http://www.icsi.berkeley.edu/pubs/networking/largemarginconvex2014.pdf |
ICSI Research Group | Networking and Security |