Support Vector Machines in the Hilbert Geometry

There are a number of applications of the Hilbert geometry in science and engineering. An example involves discrete probability distributions. A discrete probability distribution $\mathrm{\Pi }=\{p_1,\mathrm{\dots },p_n\}$ can be modeled as a point in the probability simplex, $\{x\in {ℝ}^n:x_i\ge 0,{\sum }_i{x}_i=1\}$. Clearly, this body is equivalent to a simplex in ${ℝ}^{n-1}$, and hence the $(n-1)$-dimensional simplicial Hilbert distance provides a natural distance measure between two probability distributions. Nielsen and Sun have demonstrated the benefits of using the Hilbert metric over other standard distance functions for probability distributions [25]. They considered clustering tasks in the probability simplex and the correlation elliptope. They observed that the Hilbert metric performed competitively when compared to other distance models in the probability simplex, such as the Fischer-Hotelling-Rao metric distance and the Kullback-Liebler divergence. They also showed that the Hilbert metric on the probability simplex satisfies the important property of being information monotone [25].

Beyond machine learning, the Hilbert metric has found recent uses in the context of convex approximation [2]. This is due to its close relationship with Macbeath regions [35, 1], which, up to scaling factors, are equivalent to Hilbert balls. This has been used to analyze the flag approximability of convex bodies [36] and the construction of efficient convex coverings [3]. Various results from classical computational geometry have been recreated in the Hilbert metric, including algorithms for Voronoi diagrams [18, 18, 6] and Delaunay triangulations [17].

The remainder of the paper is organized as follows. In Section 2, we present preliminary definitions and facts about the Hilbert geometry and SVMs. In Section 3, we present the proof that the Hilbert SVM problem is of LP-type of combinatorial dimension three. In Section 4, we present algorithms for computing the primitives of violation testing and computing the objective function. Finally, in Section 5, we present concluding remarks.

In this section, we will introduce the Funk, reverse-Funk, and Hilbert geometries over $\mathrm{\Omega }$. For any two points $p,q\in \mathrm{int}(\mathrm{\Omega })$, if $p=q$ all the distances are defined to be zero. Otherwise, let $p^{\prime }$ and $q^{\prime }$ denote the endpoints of the chord $\overline{pq}$ ordered as $⟨p^{\prime },p,q,q^{\prime }⟩$ (see Figure 2(a)). These distances are defined in terms of the ratios of distances between pairs of these points.

Intuitively, $d_{\mathrm{\Omega }}^F(p,q)$ is a measure of how far $q$ is from $p$ relative to the boundary that lies beyond $q$, and $d_{\mathrm{\Omega }}^{rF}(p,q)$ is just the reverse of this. The Hilbert distance $d_{\mathrm{\Omega }}^H(p,q)$ symmetrizes these by taking their arithmetic mean.

These distance functions are all nonnegative and satisfy the triangle inequality [27]. The Hilbert distance defines a metric over $\mathrm{int}(\mathrm{\Omega })$. The Funk and reverse Funk are asymmetric, and so they each define a weak metric over $\mathrm{int}(\mathrm{\Omega })$. Observe that as either point approaches the boundary of $\mathrm{\Omega }$, the Hilbert distance approaches $\mathrm{\infty }$. (This is true for one of the two points in Funk and reverse-Funk.) The Funk and reverse-Funk distances are invariant under invertible affine transformations. The Hilbert distance has the additional property that it is invariant under invertible projective transformations.

Letting $d_{\mathrm{\Omega }}^{\ast }$ denote any of the above and given a point $p\in \mathrm{\Omega }$ and scalar $r\ge 0$, the associated metric balls are defined in the standard way.

In particular, letting ${\lambda }^F(r)=1-e^{-r}$ and ${\lambda }^{rF}(r)=e^r-1$, it is easy to verify that the Funk and reverse-Funk balls are

Thus, the Funk ball is a scaling of $\mathrm{\Omega }$ by a factor of ${\lambda }^F(r)$ about $p$ [26] (see Figure 2(b)), and the reverse-Funk ball is the intersection of $\mathrm{\Omega }$ with a scaling of $-\mathrm{\Omega }$ by a factor of ${\lambda }^{rF}(r)$ about $p$ (see Figure 2(c)). Unlike the Funk ball, this scaling may generally extend outside $\mathrm{\Omega }$.

The Hilbert ball about a point is a bit more complicated to describe. Let us first consider the planar case. Given a point $p\in \mathrm{int}(\mathrm{\Omega })$, define a spoke to be the chord $\overline{pv}$, for some vertex $v$ of $\mathrm{\Omega }$, and define a half-spoke to be either of the subsegments of the spoke whose endpoint is $p$. The $m$ vertices of $\mathrm{\Omega }$ define $m$ spokes, which induce $2m$ half-spokes joining $p$ to the boundary of $\mathrm{\Omega }$ (see Figure 2(d)). Nielsen and Shao showed that $B_{\mathrm{\Omega }}^H(p,r)$ is a convex polygon whose vertices are the $2m$ points lying on these half-spokes at Hilbert distance $r$ from $p$. Furthermore, the edges of the ball satisfy the following concurrency condition [24].

This lemma generalizes to ${ℝ}^d$, where $e$, $e^{\prime }$ and $e^{\prime \prime }$ are facets, but the planar version suffices for our results. Since all distances will be defined with respect to $\mathrm{\Omega }$ henceforth, we will frequently omit explicit references to $\mathrm{\Omega }$ when discussing distances and metric balls.

The concept of spokes can be easily generalized to the case where $\mathrm{\Omega }$ is a convex polytope in ${ℝ}^d$, and $p\in \mathrm{int}(\mathrm{\Omega })$. In particular, for $0\le k\le \lfloor (d-1)/2\rfloor$, consider two faces $f$ and $f^{\prime }$ of $\mathrm{\Omega }$ of respective dimensions $k$ and $d-k-1$ such that $p$ lies in the convex hull of $f\cup f^{\prime }$. It follows from straightforward conditions on dimensionality (see, e.g., [14]) that, assuming general position, for any two such faces, there is at most one line passing through $p$ that intersects both faces. Define a spoke of $p$ to be the chord of $\mathrm{\Omega }$ contained in any such line, and again a half-spoke is the portion of the chord lying on one side of $p$. (The planar case arises when $d=2$ and $k=0$.)

In this section, we present a number of technical results regarding the geometry and construction of Hilbert and Funk balls for lines and hyperplanes. Due to space limitations, some details are omitted and appear in the full version of the paper.

Let us consider how to compute the reverse-Funk ball of radius $r$ for a hyperplane $h$ that intersects a polytope $\mathrm{\Omega }$. (Later, we will consider how this applies to the planar case, where $h$ is a line.) Consider any point $q$ that lies on the boundary of $B^{rF}(h,r)$ (see Figure 4(a)). This means that the closest point of $q$ on $h$ lies at Funk distance $r$. Letting $p$ denote this point, we have $d^F(q,p)=r$. Consider the supporting hyperplane $h^{\prime }$ of $\mathrm{\Omega }$ that is parallel to $h$ and on the opposite side from $q$. Let $q^{\prime }$ be a vertex of $\mathrm{\Omega }$ on $h^{\prime }$ (see Figure 4(b)). By convexity, the segment $\overline{q^{\prime }q}$ intersects $h$ at some point $p$ within $\mathrm{\Omega }$. Define ${\mathrm{cp}}^F(q,h)$ to be this point. By Eq. (4) (noting that $q$ here plays the role of $p$ in the equation), we have $\Vert p-q\Vert /\Vert q^{\prime }-q\Vert ={\lambda }^F(r)$. It follows that the set of points $q$ that lie on the boundary of $B^{rF}(h,r)$ define a hyperplane $h^{\prime \prime }$ that is parallel to $h$, where the relative distances between these hyperplanes is determined by ${\lambda }^F(r)$. By applying the same logic to the points on the opposite side of $h$, it follows that $B^{rF}(h,r)$ is the intersection of $\mathrm{\Omega }$ with a slab bounded by two hyperplanes that are parallel to $h$.

The times to compute ${\mathrm{cp}}^F(q,h)$ and $d^F(q,h)$ are dominated by the time needed to compute the supporting hyperplanes of $\mathrm{\Omega }$ that are parallel to $h$. If $\mathrm{\Omega }$ is an $m$-sided convex polygon in ${ℝ}^2$, this can be done in $O(\log m)$ time through binary search. If $\mathrm{\Omega }$ is a convex polytope in ${ℝ}^d$ with $m_0$ vertices, this can be done in $O(m_0)$ time.

Next, we consider the Hilbert ball of radius $r\ge 0$ about a line $\mathrm{\ell }$ that intersects the interior of $\mathrm{\Omega }$, $B^H(\mathrm{\ell },r)$. The procedure for constructing such a ball was given by Gezalyan and Mount [18, Lemma 6], but we sketch it here for the sake of completeness.

First, extend each of the edges of $\mathrm{\Omega }$ until the extension intersects $\mathrm{\ell }$. For each such point $s$, consider the triangle defined by the convex hull of the edge $e$ that was extended to form $s$ and the vertex $v$ where the supporting line for $\mathrm{\Omega }$ passing through $s$ hits the opposite side of $\mathrm{\Omega }$ (see Figure 5(a)). These triangles subdivide $\mathrm{\Omega }$. Each such triangle has two chords that cross $\mathrm{\ell }$. On each such chord, create two points at Hilbert distance $r$ from the crossing point with $\mathrm{\ell }$. These points are in convex position, and by the projective properties of the Hilbert distance, the line segments connecting them through each triangle are part of the Hilbert ball. Together, these points constitute the vertices of the convex hull of the Hilbert ball of the line (see Figure 5(b)).

Given a point $q\in \mathrm{\Omega }$, we can compute its closest point on $\mathrm{\ell }\cap \mathrm{\Omega }$ as follows. Determine the triangle of the above construction that contains $q$ (see Figure 5(c)). Consider the chord passing through $q$ and the appropriate vertex $v$ of the triangle. Let ${\mathrm{cp}}^H(q,\mathrm{\ell })$ denote the intersection point of this chord with $\mathrm{\ell }$. The chord that joins $q$ and ${\mathrm{cp}}^H(q,\mathrm{\ell })$ is called the closest-point spoke for $q$ with respect to $\mathrm{\ell }$.

Before discussing SVMs in the Hilbert setting, it is illustrative to explore the differences with the Euclidean case. Given two point sets $A,B\in {ℝ}^d$ (see Figure 6(a)) which are assumed to be linearly separable, the objective is to compute a separating hyperplane $h$ that maximizes the margin, defined to be the minimum distance of either point set to $h$ (see Figure 6(b)). The points achieving the margin are called the support vectors. Local minimality considerations imply that, assuming general position, the number of support vectors does not exceed $d+1$ [7].

Define a slab to be the region bounded between two parallel hyperplanes, the Euclidean SVM problem can be interpreted as the problem of computing the slab of maximum orthogonal width that separates $A$ and $B$. The SVM hyperplane lies midway between the slab’s bounding hyperplanes. The margin $r$ is just half the slab’s width (see Figure 6(b)). An alternative and equivalent interpretation is to consider the maximum radius $r$ such that by placing balls of radius $r$ about the points of $A$ and $B$, the resulting sets of balls are linearly separable (see Figure 6(c)). By replacing Euclidean balls with metric balls, this observation can be readily generalized to any normed space.

In ${ℝ}^d$, we refer to the hyperplane $h$ that achieves the maximum Hilbert margin as the Hilbert SVM hyperplane for $A$ and $B$, and we define the Funk SVM hyperplane analogously for the Funk distance. The following lemma provides a characterization of this hyperplane.

In this section, we show that our Hilbert and Funk SVM problems possess properties similar to that of low-dimensional linear programming, which leads to an efficient algorithmic solution. In particular, we show that these problems have a property called LP-type [30]. This type of problem requires a finite set $S$ as input and an objective function $f$ to be maximized, which induces a total ordering over subsets of $S$. Generally, an LP-type problem is defined as follows.

A basis of an LP-type problem is a set $S^{\prime }\subseteq S$ with the property that every proper subset of $S^{\prime }$ has a larger objective-function value than $S^{\prime }$ itself. The combinatorial dimension of an LP-type problem is defined to be the maximum cardinality of a basis.

A natural choice for $S$ would be $A\cup B$ and a basis would consist of $d+1$ points of this set. While this suffices for the simpler Funk distance and the Hilbert distance in the plane, we will need more information for the multidimensional Hilbert SVM problem. In particular, we will use pairs consisting of a point of $A\cup B$ and a half-spoke for this point. As seen in Lemma 7, these entities locally define the SVM hyperplane. Given $A$, $B$, and $\mathrm{\Omega }$, define $V=V_{\mathrm{\Omega }}(A,B)$ to be the set of pairs $(p,s)$, where $p\in A\cup B$, and $s$ is any half-spoke emanating from $p$. Such a pair is called a point-spoke. In the multidimensional setting, the role of the set $S$ in the definition of LP-type will be played by $V$.

We define the objective function for the multidimensional Hilbert SVM problem as follows. Recall that $\mathrm{Sep}(A,B)$ denotes the set of $(d-1)$-dimensional hyperplanes that separate $A$ and $B$. Given a hyperplane $h\in \mathrm{Sep}(A,B)$ and a point-spoke $v=(p,s)$, define $d_{\mathrm{\Omega }}^H(v,h)$ to be the Hilbert distance from $p$ to $h$ measured along the half-spoke $s$. If $s$ does not intersect $h$, define the distance to be $\mathrm{\infty }$. In the planar case, given any set $S^{\prime }\subset A\cup B$, we define $f(S^{\prime })$ to be

In the multidimensional case, given any $h\in \mathrm{Sep}(A,B)$ and $V^{\prime }\subset V$, define

Given $p\in \mathrm{int}(\mathrm{\Omega })$, define $\sigma (p)$ to be the set of half-spokes of $p\in \mathrm{int}(\mathrm{\Omega })$. By convexity of Hilbert balls, for any $p\in A\cup B$ the half-spoke $s\in \sigma (p)$ that defines the distance $d_{\mathrm{\Omega }}^H(p,h)$ to any hyperplane $h$ is the one that minimizes the value of $d_{\mathrm{\Omega }}^H((p,s),h)$. Thus, the objective function for our LP-type problem is the following.

Our next result shows that Hilbert SVM satisfies these conditions.

We will first discuss the objective function for the Funk SVM, since it is the easier of the two. In the planar case, Lemma 7 implies that a basis consists of three points, say $\{a,b,c\}$. From the lemma, we know that two points must come from one set and one from the other, so there is no loss in generality in assuming that $a,c\in A$ and $b\in B$. Let $\mathrm{\ell }$ be the SVM line we seek. Consider the supporting line of $\mathrm{\Omega }$ that lies on the opposite side of $\mathrm{\ell }$ as $a$ and $c$. Let $v$ denote the vertex of $\mathrm{\Omega }$ incident to this supporting line. By Lemma 5(ii), ${\mathrm{cp}}^F(a,\mathrm{\ell })$ and ${\mathrm{cp}}^F(c,\mathrm{\ell })$ lie on the segments $\overline{av}$ and $\overline{cv}$, respectively (see Figure 9(a)). Since $d^F(a,\mathrm{\ell })=d^F(c,\mathrm{\ell })$, it follows that $\mathrm{\ell }$ is parallel to $\overline{ac}$.

Given the two points $a$ and $c$, we can compute the vertex $v$ in $O(\log m)$ time by binary search on the boundary of $\mathrm{\Omega }$. We can compute the parallel supporting line on the opposite side of $\mathrm{\Omega }$ in $O(\log n)$ time, which is used to compute $b$’s Funk distance. From these two lines, it is straightforward to compute the location of the parallel line $\mathrm{\ell }$ that equalizes the Funk distances among all three points.

By combining this with the observations from Section 4, we can compute both the violation test and the objective function for the planar Funk SVM in time $O(\log m)$. Given that the ground set $A\cup B$ has $n$ points, the overall running time is $O(n\log m)$, and Theorem 2(i) follows.

Next, let us consider the $d$-dimensional case, for any fixed $d\ge 3$. A basis consists of $d+1$ points ${\{p_i\}}_{i=0}^d\subseteq A\cup B$. By Lemma 5(i), the points $p_i$ lie on two sides of a slab that is parallel to the desired SVM hyperplane. Let $h$ denote this hyperplane. To compute $h$, observe that it can be represented as $\{x\in {ℝ}^d:⟨x,w⟩=1\}$, for some nonzero vector $w\in {ℝ}^d$. Thus, there exist reals $\alpha$ and $\beta$ such that the points $p_i$ above the slab satisfy $⟨p_i,w⟩-\alpha =0$ and the points below the slab satisfy $⟨p_i,w⟩-\beta =0$. This yields a system of $d+1$ homogeneous linear equations in the $d+2$ variables $\{\alpha ,\beta ,w_1,\mathrm{\dots },w_d\}$. We can solve these equations to determine $w$ up to a nonzero scale factor.

This fixes the orientation of $h$, but not its exact location. To compute its location, we first determine the two supporting hyperplanes of $\mathrm{\Omega }$ parallel to $h$. This can be done in $O(m_0)$ time, where $m_0$ denotes the number of vertices of $\mathrm{\Omega }$. Given these hyperplanes, we take any basis point of $A$ and any basis point of $B$, and through a straightforward calculation, in $O(1)$ time we can determine the parallel hyperplane $h$ that equalizes the Funk distance to each.

In summary, assuming that the dimension $d$ is fixed, both the violation test and the objective function can be computed in $O(m_0)$ time. Given that the ground set $A\cup B$ has $O(n)$ points, the overall running time is $O(n{m}_0)$. This establishes Theorem 2(ii).

Next, let us consider how to compute the objective function for the $d$-dimensional case, for any fixed $d\ge 3$. A basis consists of $d+1$ point-spoke pairs ${\{p_i,s_i\}}_{i=0}^d$. We claim that we can compute $h$ in $O(m)$ time. To see this, observe that $h$ can be represented as $\{x\in {ℝ}^d:⟨x,w⟩=1\}$ for some nonzero vector $w\in {ℝ}^d$. For a given point-spoke pair $(p_i,s_i)$, in $O(m)$ time we can compute the points $x_i$ and $y_i$, where the extension of the half-spoke intersects $\partial \mathrm{\Omega }$. Let us assume this is oriented so that $y_i-x_i$ is in the direction of $s_i$ (see Figure 9(b)). For a given distance $r$, let $q_i=q_i(r)$ denote the point along this spoke that is at Hilbert distance $r$ from $p$. To simplify the calculation, let $\widehat{r}=\exp (2r)$, and let us assume that the chord $\overline{x_i{y}_i}$ is affinely mapped to the interval $[0,1]$ on the real line, which maps $p_i$ and $q_i$ to points in this interval (which we will continue to refer to as $p_i$ and $q_i$). By Eq. (3), for $0\le i\le d$

Together with the constraints $\widehat{r}\ge 1$ (from the fact that $r\ge 0$) and ${\{0\le q_i\le 1\}}_{i=0}^d$ (from the requirement that the $q_i$’s lie in the interval $[0,1]$), this yields a system of $d+1$ algebraic equations of degree $2$ in the $d+1$ unknowns $\{\widehat{r},w_1,\mathrm{\dots },w_d\}$. (Note that the $p_i$ values are fixed.) Since $d$ is a fixed constant, we can solve this system in $O(1)$ time. If this system has a feasible solution, then the objective function value is $r=\frac{1}{2}\ln \widehat{r}$, and the values of the $q_i$’s determine the hyperplane by specifying the points where the separating hyperplane crosses each of the half-spokes.

The time to compute the objective function is dominated by the $O(m)$ time needed to compute the endpoints of each of the half-spoke extensions. By Lemma 4, each point gives rise to $O(m^2)$ half-spokes, which implies that the ground set $V$ is of size $O(n{m}^2)$. Thus, the overall running time is $O(n{m}^3)$, and this establishes Theorem 1(ii).

Finally, let us consider computing the objective function for the planar Hilbert SVM. From Lemma 7, a basis consists of three support vectors, which must include at least one point from each of $A$ and $B$. As before, if we are presented with a subset that does not meet these conditions, we report a value of $+\mathrm{\infty }$ for the objective function. We will focus on the more interesting case of computing the Hilbert SVM objective function for a basis consisting of three points $\{a,b,c\}$. There is no loss in generality in assuming that $a,c\in A$ and $b\in B$. As observed earlier, the value of the objective function is the maximum $r$ such that the balls $B(a,r)$ and $B(c,r)$ are linearly separable from $B(b,r)$. The resulting separating line $\mathrm{\ell }$ is equidistant to all three points (see Figure 8(a)). Note that there need not be a separating line that is equidistant to three points (see Figure 8(c)). In this section, we will present an $O({\log }^{2}m)$ time algorithm that either finds the desired equidistant separating line, or reports that no such line exists. Note that if the line does not exist, the value of the objective function reduces to a two-point case, either $\{a,b\}$ or $\{b,c\}$, whichever achieves the smaller separation distance.