Tverberg's theorem and multi-class support vector machines

Pablo Soberón

doi:10.3934/fods.2024039

Article Contents

2025, Volume 7, Issue 2: 568-580. Doi: 10.3934/fods.2024039

This issue Previous Article Persistent homology with k-nearest-neighbor filtrations reveals topological convergence of PageRank Next Article Affine invariant ensemble transform methods to improve predictive uncertainty in neural networks

Tverberg's theorem and multi-class support vector machines

Pablo Soberón^{1, 2, ,}

1.
The Graduate Center, City University of New York, USA
2.
Baruch College, City University of New York, USA

^*Corresponding author: Pablo Soberón
^*Corresponding author: Pablo Soberón

Received: April 2024

Early access: September 9, 2024

Published online: September 9, 2024

The author is supported by NSF CAREER award no. 2237324, NSF award no. 2054419 and a PSC-CUNY Trad B award.

Abstract / Introduction Full Text(HTML) Figure(3) / Table(2) Related Papers Cited by

Abstract

We show how, using linear-algebraic tools developed to prove Tverberg's theorem in combinatorial geometry, we can design new models of multi-class support vector machines (SVMs). These supervised learning protocols require fewer conditions to classify sets of points, and can be computed using existing binary SVM algorithms in higher-dimensional spaces, including soft-margin SVM algorithms. We describe how the theoretical guarantees of standard support vector machines transfer to these new classes of multi-class support vector machines. We give a new simple proof of a geometric characterization of support vectors for largest margin SVMs by Veelaert.

Keywords:

Mathematics Subject Classification: Primary: 52A35, 52C35; Secondary: 62R07, 62R40.

Citation:

Full Text(HTML)

Figure 1. (1) An example of an SVM, we emphasize the support hyperplanes parallel to the generated hyperplane for each class. (2) An example of an multi-class SVM under the proposed model. Notice that it is not possible to separate any two classes of points with a hyperplane. (3) The half-spaces in part (2) can be used to classify space using convex regions. The model can distinguish regions where it is ambiguous

Download: Full-size image PowerPoint slide

Figure 2. An example of a largest-margin SVM with two sets. If we project the support vectors onto the separating hyperplane, the convex hulls of the projections of different sides intersect

Download: Full-size image PowerPoint slide

Figure 3. This figure shows the process to find (TSVM) for two sets of points. First we embed the sets in $ U_1 $, then we reflect $ A_2 $ across the origin to obtain their representatives in $ U_2 $. We take the convex hull of $ Y_1 $ and $ Y_2 $ and intersect it with $ R $, which in the figure gives us a hexagon. We take the closest point $ p $ to the origin in $ {\rm{conv}}(Y)\cap R $ and construct a hyperplane parallel to the facet containing $ p $ of $ {\rm{conv}}(Y) $ through the origin. This hyperplane intersects $ U_1 $ in the largest-margin SVM for the original sets

Download: Full-size image PowerPoint slide

Table 1. Any linear SVM algorithm can be applied to the computation of our multi-class SVM, including soft-margin SVMs. If we denote $ \tau(a, b;d) $ the complexity of computing an SVM with $ a+b $ data points in $ \mathbb{R}^d $ (one class with $ a $ points and one with $ b $ points), then the computational complexity in terms of $ n $ of our results can be described as listed above. We assume our original set of points has $ k $ classes with $ n/k $ points each. We include the complexity of a naive approach to (AvA) and (1vA) for comparison. The randomized algorithm for (TSVM) also has constant factors that depend on the product $ dk $ but not $ n $. Statistical guarantees would be the same as those running a linear SVM with the parameters above. (Simple TSVM) and deterministic (TSVM) are equivalent to running a single SVM, while randomized (TSVM) is equivalent to running $ O(n) $ binary SVMs

(AvA)	$ \binom{k}{2} \tau (n/k, n/k; d)$
(1vA)	$ k \cdot \tau (n/k, n-(n/k);d)$
(Simple TSVM)	$ \tau(1, n-1;(d+1)(k-1))$
(TSVM)	$ O\Big(n \cdot \tau \Big(1, (d+1)(k-1)+1; (d+1)(k-1)+1\Big)\Big)$ (randomized) $ \tau((n/k)^k, 1; d(k-1)+1)$ (deterministic)

| Show Table

DownLoad: CSV

Algorithm 1 Computing TSVM

1: procedure TSVM(Family $ Y $, Tuple $ Y' $)
2:  Order $ Y $ randomly as $ p_1, \ldots, p_{|Y|} $ where the first $ |Y'| $ elements are $ Y' $. The tuple $ Y' $ must have $ (k-1)(d+1) $ points, and are the candidates for the support vectors of the TSVM.
3:  Find the TSVM for $ Y' $, denoted $ H $. This is a half-space in $ \mathbb{R}^{(d+1)(k-1)} $ that does not contain the origin.
4  for each $ p_t \in Y $ do
5:    Check $ p_t \in H $.
6:    if $ p_t \not \in H $ then
7:      Find the TSVM $ H' $ for $ Y' \cup \{p_t\} $.
8:      Let $ Y'' $ be the $ (d+1)(k-1) $-tuple whose TSVM is $ H' $.
9:      $ H $ = TSVM($ \{ p_1, \ldots, p_t \}, Y'') $
10:  return $ H $

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	H. Adams, E. Farnell and B. Story, Support vector machines and Radon's theorem, Found. Data Sci., 4 (2022), 467-494. doi: 10.3934/fods.2022017.
[2]	N. Amenta, J. De Loera and P. Soberón, Helly's theorem: New variations and applications, Algebraic and Geometric Methods in Discrete Mathematics, Contemp. Math., Amer. Math. Soc., Providence, RI, 685 (2017), 55-95. doi: 10.1090/conm/685/13718.
[3]	P. V. M. Blagojević and G. M. Ziegler, Beyond the Borsuk–Ulam theorem: The topological tverberg story, A Journey Through Discrete Mathematics, 34 (2017), 273-341. doi: 10.1007/978-3-319-44479-6_11.
[4]	B. E. Boser, I. M. Guyon and V. N. Vapnik, A training algorithm for optimal margin classifiers, Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory, (1992), 144-152. doi: 10.1145/130385.130401.
[5]	I. Bárány, P. V. M. Blagojević and G. M. Ziegler, Tverberg's theorem at 50: Extensions and counterexamples, Notices of the American Mathematical Society, 63 (2016), 732-739. doi: 10.1090/noti1415.
[6]	I. Bárány and S. Onn, Colourful linear programming, Integer Programming and Combinatorial Optimization, Springer Berlin Heidelberg, 1084 (1996), 1-15. doi: 10.1007/3-540-61310-2_1.
[7]	I. Bárány and P. Soberón, Tverberg's theorem is 50 years old: A survey, Bulletin of the American Mathematical Society, 55 (2018), 459-492. doi: 10.1090/bull/1634.
[8]	K. Crammer and Y. Singer, On the algorithmic implementation of multiclass kernel-based vector machines, Journal of Machine Learning Research, (2001), 265-292.
[9]	J. A. De Loera and T. Hogan, Stochastic tverberg theorems with applications in multiclass logistic regression, separability, and centerpoints of data, SIAM Journal on Mathematics of Data Science, 2 (2020), 1151-1166. doi: 10.1137/19M1277102.
[10]	K.-B. Duan and S. S. Keerthi, Which is the best multiclass svm method? an empirical study, International Workshop on Multiple Classifier Systems, (2005), 278-285. doi: 10.1007/11494683_28.
[11]	V. Franc and V. Hlaváč, Multi-class support vector machine, Object Recognition Supported by User Interaction for Service Robots, 2 (2002), 236-239. doi: 10.1109/ICPR.2002.1048282.
[12]	B. Gärtner, J. Matoušek, L. Rüst and P. Škovroň, Violator spaces: Structure and algorithms, Discrete Applied Mathematics, 156 (2008), 2124-2141. doi: 10.1016/j.dam.2007.08.048.
[13]	S. Har-Peled and M. Jones, Journey to the center of the point set, ACM Transactions on Algorithms (TALG), 17 (2020), 1-21. doi: 10.1145/3431285.
[14]	M. A. Hearst, S. T. Dumais, E. Osuna, J. Platt and B. Scholkopf, Support vector machines, IEEE Intelligent Systems and Their Applications, 13 (1998), 18-28. doi: 10.1109/5254.708428.
[15]	C.-W. Hsu and C.-J. Lin, A comparison of methods for multiclass support vector machines, IEEE transactions on Neural Networks, 13 (2002), 415-425. doi: 10.1109/72.991427.
[16]	J. Radon, Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten, Mathematische Annalen, 83 (1921), 113-115. doi: 10.1007/BF01464231.
[17]	S. Sarkar and P. Soberón, Tolerance for colorful Tverberg partitions, European J. Combin., 103 (2022), 103527, 13 pp. doi: 10.1016/j.ejc.2022.103527.
[18]	K. S. Sarkaria, Tverberg's theorem via number fields, Israel Journal of Mathematics, 79 (1992), 317-320. doi: 10.1007/BF02808223.
[19]	M. Sharir and E. Welzl, A combinatorial bound for linear programming and related problems, Annual Symposium on Theoretical Aspects of Computer Science, 577 (1992), 567-579. doi: 10.1007/3-540-55210-3_213.
[20]	P. Soberón, Equal coefficients and tolerance in coloured tverberg partitions, Combinatorica, 35 (2015), 235-252. doi: 10.1007/s00493-014-2969-7.
[21]	I. Steinwart and A. Christmann, Support Vector Machines, Springer Science & Business Media, 2008.
[22]	H. Tverberg, A generalization of Radon's theorem, J. London Math. Soc., 41 (1966), 123-128. doi: 10.1112/jlms/s1-41.1.123.
[23]	P. Veelaert, Combinatorial properties of support vectors of separating hyperplanes, Annals of Mathematics and Artificial Intelligence, 75 (2015), 89-115. doi: 10.1007/s10472-014-9430-x.