Tverberg's theorem and multi-class support vector machines
Pablo Soberón



    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.


Tidal reconstruction of neutron star mergers from their late inspiral
    [
    
=====================================================================





§ INTRODUCTION


Support vector machines (SVMs) are a supervised learning model for data classification with a wide range of applications Boser1992, hearst1998support, steinwart2008support.  The underlying geometric problem is, given two finite sets A, B of points in ^d, to find a hyperplane separating A and B.  A key example are largest margin SVMs, in which the separating hyperplane maximizes the minimum distance to each set.  We assume that A ∩ B = ∅ for such a hyperplane to exist.  If A ∩ B ≠∅, minimizing the number of misclassified points by a hyperplane is NP-hard, but one can use adaptations such as soft-margin SVM.

A variation of this model, multi-class support vector machines, arises when we want to classify more than two sets of points.  If we want to classify k classes A_1, …, A_k, the most common approaches are one-versus-all (1vA) and all-versus-all (AvA) models, both of which break the classification problem into many binary support vector machines.  In the first, we have to solve for k support vector machines, each separating a single class from the union of the other k-1,  In the second, we solve for k2 support vector machines separating each pair of classes.  Some optimization methods aggregate several SVMs into a single optimization problem in a higher-dimensional space, which can then be adjusted to be easier to solve Franc.2002, crammer2001algorithmic.  Multiple other models for multi-class SVMs have been proposed duan2005best, hsu2002comparison.

Many combinatorial properties of SVMs are related to classic results in discrete geometry, such as Radon's theorem Veelaert.2015, Adams2022.  Radon's theorem states that given d+2 points in ^d, there exists a partition of them into two sets whose convex hulls intersect Radon:1921vh.  A well-known generalization of Radon's theorem is Tverberg's theorem, in which we seek to split a set of points into several subsets whose convex hulls intersect.  Tverberg proved that given (k-1)(d+1)+1 points in ^d, there exists a partition of them into k sets whose convex hulls intersect Tverberg:1966tb.  The case k=2 is Radon's theorem.  There is active research around Tverberg's theorem, as it has led to important developments in discrete geometry and topological combinatorics Barany:2016vx, Blagojevic:2017bl, Barany:2018fy.

A far-reaching tool to prove variations of Tverberg's theorem is a linear-algebraic technique devised by Sarkaria <cit.> and simplified by Bárány and Onn <cit.>.  In addition to leading to one of the simplest known proofs of Tverberg's theorem, this technique is highly malleable and can be used to prove a multitude of variations of Tverberg's theorem.

The goal of this manuscript is to show a link between Tverberg's theorem and multi-class SVMs via the linear algebra techniques mentioned above.  The existence of a connection between multi-class SVMs and Tverberg's theorem was conjectured by Adams et al. Adams2022, when they linked Radon's theorem to binary SVMs.  To have a multi-class SVM that does not missclassify any points, the (1vA) model requires each class to be separable from the union of the other k-1, and the (AvA) model requires any two classes to be separable.  We propose a new type of multi-class SVM which uses a weaker condition.   Applying our model for k=2 leads to classic SVMs.  Of course, since we do not ask any two A_i, A_j to be separable, potential miss-classifications are unavoidable.  We only require ⋂_i=1^k (A_i) = ∅.  The output will be a family of k closed half-spaces H_1, …, H_k such that 

    
  * For each i=1,…, k we have have A_i ⊂ H_i and
    
  * the half-spaces satisfy ⋂_i=1^k H_i = ∅.




We describe how the half-spaces can be used to split ^d into k convex regions, each corresponding to an A_i.  The model can also be used to distinguish the regions of ambiguity.  The subdivision of ^d is most natural when k ≤ d+1.

We describe in <ref> the complexity of computing these multi-class SVM.  We compare directly with the complexity of computing a single SVM, to highlight the influence of the dimension.







Tverberg's theorem is a challenging algorithmic problem har2020journey.  One key difference between the problem addressed in this manuscript and the problem of finding Tverbreg partitions is that when training SVMs the labels are assigned before-hand.  Tverberg's theorem has also been applied to multi-class logistic regression de2020stochastic.  

Since the constructions are based on Sarkaria's linear-algebraic technique, we can deduce several combinatorial properties of these multi-class SVMs.  The model (simple TSVM) is invariant under orthogonal transformations, but not under translations.  The model (TSVM) is invariant under any isometry of ^d.  To prove these properties, a closer look at Sarkaria's method is needed, so the arguments presented here may be useful in the classic context of variations of Tverberg's theorem.

We also discuss the existence and properties of support vectors.  It is known that for any two separable sets A, B ⊂^d, there exist A' ⊂ A, B' ⊂ B such that |A' ∪ B'| ≤ d+1 and such that the largest-margin SVM induced by A, B is the same as the largest-margin SVM induced by A', B'.  For (TSVM) and (simple TSVM) a similar property holds.  For any k-tuples of sets A_1, …, A_k, there is a (k-1)(d+1)-subset of A_1 ∪…∪ A_k that induces the same (TSVM).  The same holds for (simple TSVM).  In either case we call this (k-1)(d+1)-subset the support vectors of the multi-class SVM.

The manuscript is organized as follows.  First, we present in <ref> a new proof of a characterization of critical points in largest-margin SVMs.  In <ref> we describe the linear-algebraic tools needed for our constructions.  In <ref> we describe the models (TSVM) and (simple TSVM), and their main properties.  In <ref> we discuss the induced partitions of ^d and finally in <ref> we study how the model behaves when we apply orthogonal transformations to the sets of points.









§ PROJECTION OF SUPPORT VECTORS.


Given two finite sets of points A, B in ^d that are linearly separable, let H be a separating hyperplane at maximal distance from A and B.  We denote by ε this distance, so

    ε = (H,  A) =  (H,  B)


We say that a point in a ∈ A is a support vector if (a, H) = ε, and similarly for points in B.  We assign labels to the points so that the points of A assigned positive and the points of B are assigned negative.

One interesting property about the projections of the support vectors is that the convex hulls of the projections onto the separating hyperplane of each side intersect, as in <ref>.  This was proven independently by Veelaert and by Adams, Carr, and Farnell Veelaert.2015, Adams2022.  One of the proofs involves the Karush–Kuhn–Tucker theorem and the other Householder transformations.  We present an elementary proof.


Given a separable set of points in ^d with two labels, the convex hulls of the projections of the negative and positive support vectors onto the induced largest margin SVM intersect.






Let L be the set of labeled points.  Let H be the separating hyperplane at maximum distance from the labeled sets, and let S_+, S_- be the positive and negative support vectors, respectively.  Let ε > 0 be the distance of the support vectors to H.
This means that 

    (x,H)      = ε    
    (x,H)     > ε    .


Let P_+ be the orthogonal projection of S_+ onto H, and P_- be the orthogonal projections of S_- onto H.  We assume that P_+ ∩ P_- = ∅ and look for a contradiction.

Since P_+ ∩ P_- = ∅, there exists a co-dimension one affine subspace H' of H that separates P_+ and P_-.  Notice that H' is a co-dimension two affine subspace of ^d.

Let us project all the points into the two-dimensional subspace (H')^⊥.  We denote this projection by π.  In (H')^⊥, π(H) is a line ℓ and π(H') is a point p.  Let ℓ_2 be the orthogonal line to ℓ through p.

The lines ℓ and ℓ_2 split (H')^⊥ into four quadrants.  Since P_+ ∩ P_- = ∅, the points of π(S_+) and those of π(S_-) are separated by ℓ_2.  They are also separated by ℓ by construction, so π(S_+) and π(S_-) are in opposite quadrants.

This means that we can rotate ℓ slightly around p so that its distance to each point in π(S_+) and π(S_-) increases.  If the angle of rotation is small enough, the distance of π^-1(ℓ) to the rest of the points in L remains strictly larger than ε.  This contradicts H being the largest-margin SVM. 




§ LINEAR-ALGEBRAIC TOOLS


In this section, we introduce Sarkaria's construction to tackle Tverberg-type problems.  Suppose we are given k sets A_1, …, A_k in ^d.  We introduce v_1, …, v_k, which are the vertices of a regular simplex in ^k-1 centered at the origin.  We further assume that each v_i is a unit vector.  A crucial property of this k-tuple is that its linear dependences are precisely the linear combinations in which all coefficients are equal.   For each i we associate v_i to A_i.  Given x ∈ A_i we first append a coordinate 1 to make it into a vector in ^d+1, x̅ = [ x; 1 ].  Then, we take the tensor product with its corresponding v_i, defining  S(x) = x̅⊗ v_i = x̅ v_i^T ∈^(d+1)(k-1).


In this manuscript we treat ^(d+1)(k-1) as the set of (d+1)(k-1)× 1 vectors and as the set of (d+1)×(k-1) matrices interchangeably.

Finally, for i=1,…, k, we define the set

    Y_i = {S(x) : x ∈ A_i,  i=1,…, k}⊂^(d+1)(k-1)


The main difference with our approach and the one by  Bárány and Onn is that for each point in A_1 ∪… A_k we already know to which class it belongs, so it yields a unique point in the higher-dimensional space.  When one wants to prove Tverberg's theorem, we have to assign classes to unlabeled sets of points, so each point in ^d is represented by a k-tuple in ^(d+1)(k-1).

The main reason why this transformation can be used to study Tverberg-type problems and why we can use it in the context of multi-class SVMs is the following lemma.


Let k, d be positive integers.  Let A_1, …, A_k be finite sets of points in ^d such that ⋂_i=1^k  (A_i) = ∅.  Then, for Y_1, …, Y_k defined as above, 0 ∉( ⋃_i=1^k Y_i).



Let A = ⋃_i=1^k A_i and Y = ⋃_i=1^k Y_i.  We prove the contrapositive.  Assume that the origin in ^(d+1)(k-1) is in the convex hull of Y.  We want to show that the convex hulls of the sets A_i intersect.  Then, for each x ∈ A there exists a non-negative coefficient α(x) such that ∑_x ∈ Aα(x) = 1 and

    0 = ∑_x ∈ Aα(x) S(x)     = ∑_x ∈ A_1α(x) S(x) + … +  ∑_x ∈ A_kα(x) S(x) 
        = ∑_x ∈ A_1α(x) (x̅⊗ v_1) + … +  ∑_x ∈ A_Kα(x) (x̅⊗ v_k)    
        = ( ∑_x ∈ A_1α(x) x̅) ⊗ v_1 + … +  ( ∑_x ∈ A_kα(x) x̅) ⊗ v_k.


If we look at the linear dependences of v_1, …, v_k in ^k-1, we can see that β_1 v_1 + … + β_k v_k = 0 if an only if β_1 = … = β_k.  This carries through the tensor product and we have ∑_x ∈ A_1α(x) x̅ = … = ∑_x ∈ A_kα(x) x̅.

This is an equality in ^d+1.  If we look at the last coordinate, we have
∑_x ∈ A_1α(x) = … = ∑_x ∈ A_kα(x).
Since the total sum of the coefficients was one, each of the sums above must be 1/k.  If we look at the first d coordinates and multiply each equation by k, we have

    ∑_x ∈ A_1 (kα(x))x = … = ∑_x ∈ A_k (kα(x))x.

and each of the terms above is a convex combination.  This means that the convex hulls of the A_i have non-empty intersection, ⋂_i=1^k  (A_i) ≠∅.


Therefore, the origin in ^(d+1)(k-1) can be separated from Y by a hyperplane.  We can find this hyperplane with any existing algorithm for SVMs, which is the central point of this manuscript.  If we have a hyperplane separating a set from the origin in ^(d+1)(k-1), we want to obtain a set of half-spaces as described in the introduction.

In other words, we need to be able to map hyperplanes in ^(d+1)(k-1) into k-tuples of hyperplanes in ^d explicitly.  This has been done recently Sarkar:2020uk.  We describe the process below.

Let Π: ^d+1→^d be the function that erases the last coordinate.  For each y ∈^(d+1)(k-1) let us think of y as a (d+1) × (k-1) matrix.  For i ∈ [k] we define the function

    f_i : ^(d+1)(k-1)   →^d 
    
        y    ↦Π (y v_i)

where yv_i is considered as a product of matrices.


If x ∈ A_i, then f_i(S(x))=x.



A simple computation shows that

    f_i(S(x)) = f_i(x̅ v_i^T) = Π (x̅ v_i^T v_i) = Π (x̅) = x.

The third equality follows since v_i is a unit vector.


For each i ∈ [k], consider the d-dimensional affine subspace U_i = {x̅⊗ v_i : x ∈^d}⊂^(d+1)(k-1).  Given a half-space H in ^(d+1)(k-1), consider the k half-spaces in ^d
defined by H_i = f_i (U_i ∩ H) for i∈ [k].


Let H be a closed half-space in ^(k-1)(d+1). If 0 ∉H then ⋂_i=1^k H_i = ∅.



As before, let's consider ^(d+1)(k-1) as the set of (d+1) × (k-1) matrices.  Each closed half-space H can be defined using a linear functional and a constant.  Using the Frobenius product, we can express H using a (k-1)× (d+1) matrix M and a constant λ such that

    H = {S ∈^(k-1)(d+1) : tr(S M) ≥λ}.

Since the origin is not contained in H, we can assume that λ > 0.  Suppose on the contrary that there exists an x ∈^d so that x ∈⋂_i=1^k f_i (U_i ∩ H) and we look for a contradiction.  In other words, for i=1,…, k we have x̅⊗ v_i ∈ H, so
tr (x̅v_i^T M) ≥λ > 0.

If we write each of the k inequalities as i varies and add them, we have

    0< k λ≤∑_i=1^k tr (x̅v_i^T M) = tr(x̅(∑_i=1^k v_i^T) M) = 0.

The last equality follows as ∑_i=1^k v_i = 0.  This is the contradiction we wanted.


Now we have all the ingredients to define a multi-class SVM.  Another important subspace for our computations is the following d(k-1)-dimensional space

    R = { y ∈^(d+1)(k-1): }.


This subspace has been used previously to prove some variations of Tverberg's theorem with some coloring conditions added to the set soberon2015equal.  Some particular translates of R will also be useful.  For i=1,…, k we define R_i = { S ∈^(k-1)(d+1): }.

Notice that U_i ⊂ R_i for each i=1,…, k.


Let z_1, z_2, …, z_k ∈^(d+1)(k-1) such that z_i ∈ U_i for each i=1,…, k.  The only point in R ∩{z_1,…, z_k} is the barycenter of the set {z_1, …, z_k}.



Consider each z_i as a (d+1)× (k-1) matrix.  Suppose that λ_1z_1 + … + λ_k z_k is a convex combination in R.  If we look at the last row of this linear combination we have λ_1 v_1 + … + λ_k v_k = 0.  This means that λ_1 = … = λ_k, as we wanted.




§ CONSTRUCTION AND BASIC PROPERTIES OF MULTI-CLASS SVM


We are now ready to formalize the multiclass SVMs described in the introduction.  Given k sets A_1, …, A_k in ^d whose convex hulls do not all overlap, we seek a family of k half-spaces H_1,…, H_k such that A_i ⊂ H_i for each i=1,…, k and so that the half-space H_1, …, H_k do not all intersect.  For the following definition we need the subspaces U_i = {x̅⊗ v_i : x ∈^d} and their associated functions f_i defined above.


Let A_1, …, A_k be finite families of points in ^d whose convex hulls do not intersect.  We define the multi-class support vector machine (Simple TSVM) as a family of k closed half-spaces H_1, …, H_k obtained as follows.  First, for each x ∈ A_i construct the point S(x) = x̅ v_i^T ∈^(d+1)(k-1).  Let Y be the collection of all points obtained this way.  Find H the closed half-space in ^(d+1)(k-1) that contains Y and whose distance from the origin is maximal.  For i=1,…, k the half-space H_i is defined as H_i = f_i(U_i ∩ H).


The computation of (simple TSVM) consists of finding the distance from Y to the origin.  We can also think of this as finding the largest-margin SVM in ^(d+1)(k-1) that separates the origin from Y, and then doubling the distance to the origin.  The discussion in the previous section shows that this multi-class support vector machine satisfies the desired properties.  For a soft-margin version, it suffices to compute in ^(d+1)(k-1) an SVM with one class equal to Y and the other equal to {0}.  If we denote by τ(a,b;d) the complexity of an algorithm to compute an SVM with data points in ^d and two classes of size a and b, then the complexity of computing (simple TSVM) is τ(n,1;(d+1)(k-1)), where n is the number |A_1|+ … +|A_k| of data points.  Any other performance metrics we have for an SVM transfer to (simple TSVM) if we do the change of parameter as outlined above.

For the second type of multi-class SVM, we consider the following alternative definition.  Recall that in the space of (d+1)×(k-1) matrices we denoted by R the subspace where the last row is equal to zero.


Let A_1, …, A_k be finite families of points in ^d whose convex hulls do not intersect.  We define the multi-class support vector machine (TSVM) as a family of k closed half-spaces H_1, …, H_k obtained as follows.  First, for each x ∈ A_i construct the point S(x) = x̅ v_i^T ∈^(d+1)(k-1).  Let Y be the collection of all points obtained this way and consider P = R ∩(Y).  Compute p the closest point of P to the origin, and H the closed half-space in ^(d+1)(k-1) that contains Y, whose boundary hyperplane contains p, and whose distance from the origin is maximal.  The half-spaces H_i are defined as H_i = f_i(U_i ∩ H).


Even though this definition is more involved it has two big advantages.  First, it is stable under translations of the sets of points.  Second, in the case k=2 it is precisely a largest-margin SVM.  We prove these properties in the next section.  Just like SVM have critical points, any (TSVM) is fixed by a small set of points.


Let A_1, …, A_k be k finite sets in ^d such that ⋂_i=1^k A_i = ∅.  We can find subsets A_1' ⊂ A_1, …, A_k'⊂ A_k such that A_1', …, A'_k induces the same (simple TSVM) as A_1, …, A_k and such that |A_1'|+…+|A_k'|≤ (d+1)(k-1)



We follow the construction in <ref>. Since 0 ∉(Y) the closest point to the origin in (Y) must be in a face of the polytope (Y).  This face K can have dimension at most (d+1)(k-1)-1.  By Carathéodory's theorem, we can choose a set of at most (d+1)(k-1) point in Y ∩ K whose convex hull contains p.  The subsets of A_1,…, A_k that induced this subset in Y ∩ K satisfy the condition we wanted.



Let A_1, …, A_k be k finite sets in ^d such that ⋂_i=1^k A_i = ∅.  We can find subsets A_1' ⊂ A_1, …, A_k'⊂ A_k such that A_1', …, A'_k induces the same (TSVM) as A_1, …, A_k and such that |A_1'|+…+|A_k'|≤ (d+1)(k-1)



The proof is similar to the previous theorem.  If we look for the minimal face of Y sustaining p, it has dimension at most (k-1)(d+1)-1, so the same application of Carathéodory's theorem yields the result.  The only additional detail to check is that R ∩(Y) ≠∅.  This holds because for every choice x_1 ∈ A_1, …, x_k ∈ A_k, the baryceneter of the point S(x_1),…, S(x_k) is in (Y) ∩ R. 


We denote the subsets obtained by Theorem <ref> and Theorem <ref> as the support vectors of a (simple TSVM) or (TSVM), respectively.

As mentioned above, to compute (Simple TSVM) we need to compute an SVM in a (k-1)(d+1)-dimensional space with |A_1|+… + |A_k|+1 points.  A direct approach to compute (TSVM) would be to first find the vertices of (Y)∩ R and solve the induced SVM.  We know R is a linear subspace of co-dimension k-1, so the vertices of (Y) ∩ R should be the intersection of the (k-1)-skeleton of (Y) with R.  Due to Lemma <ref>, this is a subset of the barycenters of k-tuples with one element in each Y_i.  Therefore, we can compute these barycenters and then compute an SVM in R.  This leads us to solve an SVM in a (k-1)d-dimensional space with |A_1|·…· |A_k|+1 points.

Theorem <ref> shows that computing a TSVM can be treated as a linear programming type problem, as in the framework of Sharir and Welzl Sharir:1992ih.  This is a randomized approach to problems which are combinatorially similar to linear programming problems, so that they can be solved in expected linear time in the input, which is a signficant reduction over brute-force approaches.  This means that for fixed k, d we can compute (TSVM) with a randomized algorithm in expected time linear in |A_1|+… +|A_k|. We describe the process in Algorithm <ref>, before translating back to ^d.

The key idea to compute this is to order the points randomly.  At any point, we have computed (TSVM) for the first t-1 points and we keept track of the support vector of this TSVM.  When including the t-th point, if we don't need to adjust the current halfspace H generated by (TSVM), we keep goint.  Otherwise, we adjust our guess for the support vectors and run the algorithm again for the first t points.  The computations of Sharir and Welzl bound the expected number of times we need to rerun this procedure, and end up with an expected running time linear on the input.  For deeper explanations, we recommend references on linear-programming type algorithms and violator spaces Gartner:2008bp, Amenta:2017ed.




The model (TSVM) generalizes largest-margin SVMs when k=2.  This is the main motivation to use the subspace R in the computation.  Let us prove that this is indeed the case.


For k=2, the multiclass SVM (TSVM) gives the two support hyperplanes of the largest-margin SVM of A_1 and A_2.



Notice that k=2 is the only case when U_i = R_i for all values of i.  Additionally, each U_i is a translate of R.  In this case we also have v_1 = 1, v_2 = -1 in ^1.  Therefore R_1 = {x̅∈^d+1: x ∈^d} and R_2 = {-x̅∈^d+1: x ∈^d}.  Let p be the closest point of (Y)∩ R to the origin, and H be the affine hyperplane in ^d+1 through p from <ref>.  Let H' be the hyperplane through the origin of ^d+1, parallel to H, and let H” = H ∩ U_1.  
Notice that p is the distance between H and H'.  Since a translate of p lies in U_1, H”+p contains the support vectors in of A_1 in U_1.  The same holds for (H'∩ U_2)+p for the support vectors in A_2, so H”-p contains the support vectors of A_2 in U_1.  This means that the (TSVM) induced by A_1, A_2 is an SVM at common distance p from each side.

Similarly, given a separating hyperplane H̃ for A_1, A_2 at distance ε from each set, we can embed ^d in U_1 and then reflect the embedding of A_2 with respect to the origin in ^d+1 so that it lies in U_2.  If we extend H̃ through the origin in ^d+1, we have a hyperplane through the origin at distance ε from the convex hull of the embedding of A_1 in U_1 and A_2 in U_2.  The largest margin SVM must therefore coincide with the one induced by (TSVM).


An illustration of the ideas behind this proof is shown in <ref>.





§ SUBDIVISION OF AMBIENT SPACE AND POTENTIAL CLASSIFICATION ERRORS


In each of <ref> and <ref> we use a half-space H in ^(d+1)(k-1) that does not contain the origin to generate the corresponding half-space H_1, …, H_k in ^d.

In each case, we can introduce a half-space H' that is a translate of H and whose boundary contains the origin.  Notice that the half-spaces H'_i = f_i(U_i ∩ H') for i=1,… k have non-empty intersection but their interiors have an empty intersection.  This is a direct consequence of <ref> because H' contains the origin and the interior of H' does not.

As an illustration, for k=2 the two half-space H'_1, H'_2 from (TSVM) share their boundary, which is precisely the largest-margin SVM for A_1, A_2.

Let T= ⋂_i=1^k H'_k and Δ = ^d∖( ⋃_i=1^k H_i^∘), where X^∘ denotes the interior of X for any X ⊂^d.  Now for i=1,…, k we define the convex sets
M_i = {p + tq: p ∈ T,  t ≥ 0,  q ∈Δ∩ H_i}.


  
  
 
 




Intuitively, Δ is the polytopal region not contained in the union of the H_i.  The set T is an affine subspace inside Δ.  If k ≤ d+1, we the set Δ is constructed by making a simplex in the orthogonal complement of T and extending it in the directions of T.  The set M_i is formed by taking all possible rays that start at T and go in the direction of a point of H_i in the boundary of Δ.  The case when Δ is a simplex is perhaps the most illustrative one, since in this case T is a point and we simply take the cones from T towards each of the facets of Δ.  This case looks like <ref> (3).

As mentioned before, the condition needed to generate (TSVM) or (simple TSVM) is that the convex hulls of the sets A_i do not all overlap.  If the convex hulls of fewer of these sets overalp, any model that subdivides ^d into convex pieces is bound to miss-label some data.  We minimize the misslabelings with our constructions.  
 


§ EQUIVARIANCE


In this section we describe how the multi-class SVMs we introduced interact with transformations of the set of points.  It is clear that if we apply the same affine transformation to the sets of points A_1, …, A_r and the half-spaces H_1, …, H_r the containments are preserved, but we are interested to see if the algorithms to obtain H_1, …, H_r behave as expected with these transformations.


Let M be an orthogonal linear transformation of ^d.  Let H_1, …, H_r be the (simple TSVM) induced by A_1, …, A_r.  Then (M H_1, …, MH_r) is the (simple TSVM) induced by MA_1, …, MA_r.



First notice that M can be extended to ^d+1 by acting on the first d coordinates and leaving the last coordinate fixed.  This is also an orthogonal transformation.  We denote this transformation by M_2, so Mx = M_2x̅.  Finally, we denote by M_3 the transformation on ^(d+1)(k-1) that multiplies every column of a (d+1)×(k-1) matrix by M_2, so y ↦ M_2y as a product of matrices.

This last transformation is also orthogonal.  To see this, we first show that it preserves the dot product between vectors in U_i and U_j for any (possibly equal) i and j.  We use a known factorization for the dot product of tensor products, as shown below.


    ⟨x̅⊗ v_i, y̅⊗ v_j⟩    = ⟨x̅, y̅⟩⟨ v_i, v_j ⟩ = ⟨ M_2 x̅, M_2 y̅⟩⟨ v_i, v_j ⟩ = 
        = ⟨ (M_2 x̅) ⊗ v_i, (M_2 y̅) ⊗ v_j⟩ = ⟨ M_3 (x̅⊗ v_i) , M_3 (y̅⊗ v_j) ⟩


Consider the union of an affine basis for each of U_1, …, U_k-1.  This set of (d+1)(k-1) vectors forms a basis of ^(d+1)(k-1), and M_3 preserves the dot product between any two of these vectors.  Therefore M_3 preserves the dot product in ^(d+1)(k-1) and is therefore orthogonal.




Let M be an orthogonal linear transformation of ^d and H_1, …, H_k be the (TSVM) induced by A_1, …, A_k.  Then (M H_1, …, MH_k) is the (TSVM) induced by MA_1, …, MA_k.



We follow the ideas used in the proof of <ref>.  We notice that M_3 fixes R.  Therefore, the restriction of M_3 to R is an orthogonal transformation.  This means that for any half-space H in ^(d+1)(k-1), we have (M_3H) ∩ R = M_3(H∩ R).  Again, if H is the half-space in ^(d+1)(k-1) that induces our (TSVM), we have that M_3H is the half-space for the new set of points. 

Now, if we consider the (TSVM) induced by A_1, …, A_k, we have to find the half-space H in ^(d+1)(k-1) farthest from the origin that contains Y.  Clearly, M_3H is the farthest half-space from the origin that contains M_3Y.  For i=1,…, k, we also have f_i(U_i ∩ (M_3 H)) = M f_i(U_i ∩ H).



Let q be a vector in ^d.  Let X be the set of support vectors of the (TSVM) induced by A_1, …, A_k.  Then X+q is the set of support vectors of the (TSVM) induced by A_1+q, …, A_k+q.



To find the (TSVM) incuded by A_1, …, A_k we need to compute (Y) ∩ R.  Notice that this set is invariant under translations of A = ⋃_i=1^k A_i.  This is because for any points x_1, …, x_k the barycenter of {x̅_1 ⊗ v_1, …, x̅_k ⊗ v_k} is the same as the barycenter of {(x_1+q)⊗ v_1, …, (x_k+q)⊗ v_k}.  Since (Y) ∩ R does not change, the set of support vectors remains the same.




§ ACKNOWLEDGMENTS

The author thanks Henry Adams for helpful comments.





Amenta:2017edinproceedings
      author=Amenta, N.,
      author=De Loera, J.,
      author=Soberón, P.,
       title=Helly's theorem: New variations and applications,
        date=2017,
   booktitle=Algebraic and geometric methods in discrete mathematics,
      editor=Harrington, Heather,
      editor=Omar, Mohamed,
      editor=Wright, Matthew,
   publisher=American Mathematical Society,
       pages=5596,


Adams2022article
      author=Adams, Henry,
      author=Farnell, Elin,
      author=Story, Brittany,
       title=Support vector machines and Radon's theorem,
        date=2022,
        ISSN=2639-8001,
     journal=Found. Data Sci.,
      volume=4,
      number=4,
       pages=467494,
         url=https://doi.org/10.3934/fods.2022017,


Barany:2016vxarticle
      author=Bárány, Imre,
      author=Blagojević, Pavle V. M.,
      author=Ziegler, Günter M.,
       title=Tverberg's Theorem at 50: Extensions and Counterexamples,
        date=2016,
     journal=Notices of the American Mathematical Society,
      volume=63,
       pages=732 739,


Boser1992inproceedings
      author=Boser, Bernhard E.,
      author=Guyon, Isabelle M.,
      author=Vapnik, Vladimir N.,
       title=A training algorithm for optimal margin classifiers,
        date=1992,
   booktitle=Proceedings of the 5th annual acm workshop on computational
  learning theory,
       pages=144152,


Barany:1996bzincollection
      author=Bárány, Imre,
      author=Onn, Shmuel,
       title=Colourful linear programming,
    language=English,
        date=1996,
      series=Integer Programming and Combinatorial Optimization,
      volume=1084,
   publisher=Springer Berlin Heidelberg,
       pages=1 15,


Barany:2018fyarticle
      author=Bárány, Imre,
      author=Soberón, Pablo,
       title=Tverberg's theorem is 50 years old: A survey,
        date=2018,
     journal=Bulletin of the American Mathematical Society,
      volume=55,
      number=4,
       pages=459 492,


Blagojevic:2017blincollection
      author=Blagojević, Pavle V. M.,
      author=Ziegler, Günter M.,
       title=Beyond the Borsuk–Ulam Theorem: The Topological Tverberg
  Story,
        date=2017,
      series=A Journey Through Discrete Mathematics,
      volume=34,
   publisher=Springer, Cham,
       pages=273 341,


crammer2001algorithmicarticle
      author=Crammer, Koby,
      author=Singer, Yoram,
       title=On the algorithmic implementation of multiclass kernel-based
  vector machines,
        date=2001,
     journal=Journal of machine learning research,
      volume=2,
      number=Dec,
       pages=265292,


duan2005bestinproceedings
      author=Duan, Kai-Bo,
      author=Keerthi, S Sathiya,
       title=Which is the best multiclass svm method? an empirical study,
organization=Springer,
        date=2005,
   booktitle=International workshop on multiple classifier systems,
       pages=278285,


de2020stochasticarticle
      author=De Loera, Jesus A,
      author=Hogan, Thomas,
       title=Stochastic tverberg theorems with applications in multiclass
  logistic regression, separability, and centerpoints of data,
        date=2020,
     journal=SIAM Journal on Mathematics of Data Science,
      volume=2,
      number=4,
       pages=11511166,


Franc.2002article
      author=Franc, Voitčch,
      author=Hlaváč, Václav,
       title=Multi-class Support Vector Machine,
        date=2002,
     journal=Object recognition supported by user interaction for service
  robots,
      volume=2,
       pages=236239,


Gartner:2008bparticle
      author=Gärtner, Bernd,
      author=Matoušek, Jiří,
      author=Rüst, Leo,
      author=Škovroň, Petr,
       title=Violator spaces: Structure and algorithms,
        date=2008,
     journal=Discrete Applied Mathematics,
      volume=156,
      number=11,
       pages=21242141,


hearst1998supportarticle
      author=Hearst, Marti A.,
      author=Dumais, Susan T,
      author=Osuna, Edgar,
      author=Platt, John,
      author=Scholkopf, Bernhard,
       title=Support vector machines,
        date=1998,
     journal=IEEE Intelligent Systems and their applications,
      volume=13,
      number=4,
       pages=1828,


hsu2002comparisonarticle
      author=Hsu, Chih-Wei,
      author=Lin, Chih-Jen,
       title=A comparison of methods for multiclass support vector machines,
        date=2002,
     journal=IEEE transactions on Neural Networks,
      volume=13,
      number=2,
       pages=415425,


har2020journeyarticle
      author=Har-Peled, Sariel,
      author=Jones, Mitchell,
       title=Journey to the center of the point set,
        date=2020,
     journal=ACM Transactions on Algorithms (TALG),
      volume=17,
      number=1,
       pages=121,


Radon:1921vharticle
      author=Radon, Johann,
       title=Mengen konvexer Körper, die einen gemeinsamen Punkt
  enthalten,
        date=1921,
     journal=Mathematische Annalen,
      volume=83,
      number=1,
       pages=113 115,


Sarkaria:1992vtarticle
      author=Sarkaria, Karanbir S.,
       title=Tverberg’s theorem via number fields,
        date=1992,
     journal=Israel journal of mathematics,
      volume=79,
      number=2,
       pages=317 320,


steinwart2008supportbook
      author=Steinwart, Ingo,
      author=Christmann, Andreas,
       title=Support vector machines,
   publisher=Springer Science & Business Media,
        date=2008,


soberon2015equalarticle
      author=Soberón, Pablo,
       title=Equal coefficients and tolerance in coloured tverberg
  partitions,
        date=2015,
     journal=Combinatorica,
      volume=35,
      number=2,
       pages=235252,


Sarkar:2020ukarticle
      author=Sarkar, Sherry,
      author=Soberón, Pablo,
       title=Tolerance for colorful Tverberg partitions,
        date=2022,
     journal=European J. Combin.,
      volume=103,
       pages=Paper No. 103527,


Sharir:1992ihinproceedings
      author=Sharir, Micha,
      author=Welzl, Emo,
       title=A combinatorial bound for linear programming and related
  problems,
        date=1992,
      series=Annual Symposium on Theoretical Aspects of Computer Science,
      volume=577,
       pages=567 579,


Tverberg:1966tbarticle
      author=Tverberg, Helge,
       title=A generalization of Radon’s theorem,
        date=1966,
     journal=J. London Math. Soc,
      volume=41,
      number=1,
       pages=123 128,


Veelaert.2015article
      author=Veelaert, Peter,
       title=Combinatorial properties of support vectors of separating
  hyperplanes,
        date=2015,
        ISSN=1012-2443,
     journal=Annals of Mathematics and Artificial Intelligence,
      volume=75,
      number=1-2,
       pages=89115,





