Bernd Gärtner
ABSTRACT
Following recent work of Clarkson, we translate the coreset framework to the problems of finding the point closest to the origin inside a polytope, finding the shortest distance between two polytopes, Perceptrons, and soft- as well as hard-margin Support Vector Machines (SVM). We prove asymptotically matching upper and lower bounds on the size of coresets, stating that µ-coresets of size (1+o(1)) E*/µ do always exist as µ-0, and that this is best possible. The crucial quantity E* is what we call the excentricity of a polytope, or a pair of polytopes. Additionally, we prove linear convergence speed of Gilbert's algorithm, one of the earliest known approximation algorithms for polytope distance, and generalize both the algorithm and the proof to the two polytope case. Interestingly, our coreset bounds also imply that we can for the first time prove matching upper and lower bounds for the sparsity of Perceptron and SVM solutions.
- P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Approximating extent measures of points. Journal of the ACM, 51(4):606--635, 2004. Google Scholar
Digital Library
- P. K. Agarwal, S. Har-Peled, and K. R. Varadarajan. Geometric approximation via coresets. Math. Sci. Res. Inst. Publ., 52:1--30, 2005.Google Scholar
- S. Ahipasaoglu, P. Sun, and M. Todd. Linear convergence of a modified Frank-Wolfe algorithm for computing minimum-volume enclosing ellipsoids. Optimization Methods and Software, 23(1):5--19, 2008. Google ScholarDigital Library
- M. Badoiu and K. L. Clarkson. Smaller core-sets for balls. SODA '03: Proceedings of the fourteenth annual ACM-SIAM Symposium on Discrete Algorithms, 2003. Google ScholarDigital Library
- M. Badoiu and K. L. Clarkson. Optimal core-sets for balls. Computational Geometry: Theory and Applications, 40(1):14--22, 2007. Google ScholarDigital Library
- M. Badoiu, S. Har-Peled, and P. Indyk. Approximate clustering via core-sets. STOC '02: Proceedings of the thiry-fourth annual ACM Symposium on Theory of Computing, 2002. Google ScholarDigital Library
- K. Bennett and E. Bredensteiner. Duality and geometry in SVM classifiers. ICML '00: Proceedings of the 17nd International Conference on Machine Learning, 2000. Google ScholarDigital Library
- C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 2(2):121--167, 1998. Google ScholarDigital Library
- K. L. Clarkson. Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. SODA '08: Proceedings of the nineteenth annual ACM-SIAM Symposium on Discrete Algorithms, 2008. Google ScholarDigital Library
- D. J. Crisp and C. J. C. Burges. A geometric interpretation of u-SVM classifiers. NIPS '00: Advances in Neural Information Processing Systems 12, 2000.Google Scholar
- M. Frank and P. Wolfe. An algorithm for quadratic programming. Naval Res. Logist. Quart., 3:95--110, 1956.Google ScholarCross Ref
- E. Gilbert, D. Johnson, and S. Keerthi. A fast procedure for computing the distance between complex objects in three-dimensional space. Robotics and Automation, IEEE Journal of, 4(2):193--203, 1988.Google Scholar
- E. G. Gilbert. An iterative procedure for computing the minimum of a quadratic form on a convex set. SIAM Journal on Control, 4(1):61--80, 1966.Google ScholarCross Ref
- T. Graepel, R. Herbrich, and R. C. Williamson. From margin to sparsity. NIPS '00: Advances in Neural Information Processing Systems 12, 2000.Google Scholar
- S. Har-Peled, D. Roth, and D. Zimak. Maximum margin coresets for active and noise tolerant learning. IJCAI, 2007. Google ScholarDigital Library
- S. Keerthi, S. Shevade, C. Bhattacharyya, and K. Murthy. A fast iterative nearest point algorithm for support vector machine classifier design. Neural Networks, IEEE Transactions on, 11(1):124--136, 2000. Google ScholarDigital Library
- J. Lopez, A. Barbero, and J. Dorronsoro. On the equivalence of the SMO and MDM algorithms for SVM training. Machine Learning and Knowledge Discovery in Databases, 288--300, 2008.Google Scholar
- M. E. Mavroforakis, M. Sdralis, and S. Theodoridis. A novel SVM geometric algorithm based on reduced convex hulls. ICPR '06: 18th International Conference on Pattern Recognition, 2:564--568, 2006. Google ScholarDigital Library
- M. E. Mavroforakis and S. Theodoridis. A geometric approach to support vector machine (SVM) classification. Neural Networks, IEEE Transactions on, 17(3):671--682, 2006. Google ScholarDigital Library
- B. Mitchell, V. Dem'yanov, and V. Malozemov. Finding the point of a polyhedron closest to the origin. SIAM Journal on Control, 1974.Google ScholarCross Ref
- A. B. Novikoff. On convergence proofs for perceptrons. Proceedings of the Symposium on the Mathematical Theory of Automata, 12:615--622, 1963.Google Scholar
- R. Panigrahy. Minimum enclosing polytope in high dimensions. CoRR, cs.CG/0407020, 2004.Google Scholar
- J. C. Platt. Fast training of support vector machines using sequential minimal optimization. Advances in kernel methods: support vector learning, pages 185--208, 1999. MIT Press Cambridge, MA, USA. Google ScholarDigital Library
- D. Roobaert. DirectSVM: A fast and simple support vector machine perceptron. Neural Networks for Signal Processing X. Proceedings of the 2000 IEEE Signal Processing Society Workshop, 1(1):356 -- 365, 2000.Google ScholarCross Ref
- F. Rosenblatt. The Perceptron: A probabilistic model for information storage and organization in the brain. Psychological Review, 65(6):386--408, 1958.Google ScholarCross Ref
- S. Shalev-Shwartz and Y. Singer. A new perspective on an old perceptron algorithm. Learning Theory, Lecture Notes in Computer Science, 264--278, 2005. Google ScholarDigital Library
- M. Todd and E. Yildirim. On Khachiyan's algorithm for the computation of minimum-volume enclosing ellipsoids. Discrete Applied Mathematics, 155(13):1731--1744, 2007. Google ScholarDigital Library
- I. W. Tsang, A. Kocsor, and J. T. Kwok. Simpler Core Vector Machines with enclosing balls. ICML '07: Proceedings of the 24th International Conference on Machine Learning, 2007. Google ScholarDigital Library
- I. W. Tsang, J. T. Kwok, and J. Zurada. Generalized Core Vector Machines. Neural Networks, IEEE Transactions on, 17(5):1126--1140, 2006. Google ScholarDigital Library
- I. W. Tsang, J. T. Kwok, and P.-M. Cheung. Core Vector Machines: Fast SVM training on very large data sets. Journal of Machine Learning Research, 6:363--392, 2005. Google ScholarDigital Library
- S. V. N. Vishwanathan, A. J. Smola, and M. N. Murty. SimpleSVM. ICML '03: Proceedings of the 20th International Conference on Machine Learning, pages 760--767, 2003.Google Scholar
- G. M. Ziegler. Lectures on polytopes. Graduate Texts in Mathematics, 152, 1995. Springer Verlag.Google Scholar
Index Terms
- Coresets for polytope distance
Recommendations
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
The problem of maximizing a concave function f(x) in the unit simplex Δ can be solved approximately by a simple greedy algorithm. For given k, the algorithm can find a point x(k) on a k-dimensional face of Δ, such that f(x(k) ≥ f(x*) − O(1/k). Here f(x*)...
On coresets for support vector machines
Highlights- A coreset construction algorithm for boosting support vector machines.
- Lower ...
AbstractWe present an efficient coreset construction algorithm for large-scale Support Vector Machine (SVM) training in Big Data and streaming applications. A coreset is a small, representative subset of the original data points such that a ...
Radius, diameter, incenter, circumcenter, width and minimum enclosing cylinder for some polyhedral distance functions
AbstractIn this paper we present efficient algorithms to compute the radius, diameter, incenter, circumcenter, width and k dimensional enclosing cylinder for convex polyhedral and convex polyhedral offset distance functions in plane and in ℜ d ...
Comments