Poster
Large-Margin Convex Polytope Machine
Alex Kantchelian · Michael C Tschantz · Ling Huang · Peter Bartlett · Anthony D Joseph · J. D. Tygar

Wed Dec 10th 07:00 -- 11:59 PM @ Level 2, room 210D #None

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.

Author Information

Alex Kantchelian (UC Berkeley)
Michael C Tschantz (UC Berkeley)
Ling Huang (Intel)
Peter Bartlett (UC Berkeley)
Anthony D Joseph (University of California, Berkeley)
J. D. Tygar

More from the Same Authors