Support vector machines and Radon's theorem

DOI10.3934/FODS.2022017MaRDI QIDQ6154223zbMATH OpenOpenAlexFDO

Authors Henry Adams, Elin Farnell, Brittany Story

Publication date 14 February 2024

Published in Foundations of Data Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.00617

zbMATH Keywords

convex geometrylinear classificationRadon's theoremsupport vector machines

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Topological data analysis (62R40)

Abstract: A support vector machine (SVM) is an algorithm that finds a hyperplane which optimally separates labeled data points in $mathbb{R}^n$ into positive and negative classes. The data points on the margin of this separating hyperplane are called support vectors. We connect the possible configurations of support vectors to Radon's theorem, which provides guarantees for when a set of points can be divided into two classes (positive and negative) whose convex hulls intersect. If the convex hulls of the positive and negative support vectors are projected onto a separating hyperplane, then the projections intersect if and only if the hyperplane is optimal. Further, with a particular type of general position, we show that (a) the projected convex hulls of the support vectors intersect in exactly one point, (b) the support vectors are stable under perturbation, (c) there are at most $n+1$ support vectors, and (d) every number of support vectors from 2 up to $n+1$ is possible. Finally, we perform computer simulations studying the expected number of support vectors, and their configurations, for randomly generated data. We observe that as the distance between classes of points increases for this type of randomly generated data, configurations with fewer support vectors become more likely.

Recommendations

• Combinatorial properties of support vectors of separating hyperplanes
• On the optimal separating hyperplane for arbitrary sets: a generalization of the SVM formulation and a convex hull approach
• scientific article; zbMATH DE number 1453043
• scientific article; zbMATH DE number 1974047
• Support vector machines and distance minimization

Cites work

• A dice probability problem
• A Generalization of Radon's Theorem
• An integral‐geometric meaning for lower order area functions of convex bodies
• An introduction to support vector machines and other kernel-based learning methods.
• APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS
• scientific article; zbMATH DE number 1970438 (Why is no real title available?)
• scientific article; zbMATH DE number 1749054 (Why is no real title available?)
• Hyperplane separability and convexity of probabilistic point sets
• Kernel methods in machine learning
• Kinematic measures for sets of support figures
• On a common generalization of Borsuk's and Radon's theorem
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Stochastic and Integral Geometry
• Stochastic Tverberg theorems with applications in multiclass logistic regression, separability, and centerpoints of data
• Support vector machines: theory and applications.
• The Geometry of Radon's Theorem
• Tverberg’s theorem is 50 years old: A survey
• VC-based confidence and credibility for support vector machines

Cited in

(1)

• Tverberg's theorem and multi-class support vector machines

This page was built for publication: Support vector machines and Radon's theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6154223)