Large-margin Convex Polytope Machine

TitleLarge-margin Convex Polytope Machine
Publication TypeConference Paper
Year of Publication2014
AuthorsKantchelian, A., Tschantz M. Carl, Huang L., Bartlett P. L., Joseph A. D., & Tygar J.D..
Published inProceedings of the 27th International Conference on Neural Information Processing Systems
PublisherMIT Press
Place PublishedCambridge, MA, USA

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.

ICSI Research Group

Networking and Security