Minimizing the error of linear separators on linearly inseparable data

Minimizing the error of linear separators on linearly inseparable data Boris Aronov a, Delia Garijo b, Yurai Núñez-Rodríguez c, David Rappaport d, Carlos Seara e,∗, Jorge Urrutia f a Department of Computer Science and Engineering, Polytechnic Institute of NYU, USA b Dept. de Matemática Aplicada I, Universidad de Sevilla, Spain c Lakes Environmental Software, 60 Bathurst Dr. Unit 6, Waterloo, ON, N2V2A9, Canada d School of Computing, Queen’s University, Kingston, Canada e Dept. de Matemàtica Aplicada II, Universitat Politècnica de Catalunya, Spain f Instituto de Matemáticas, Universidad Nacional Autónoma de México, Mexico Keywords: Linearly inseparable Classifiers Error minimizers abstract Given linearly inseparable sets Rof red points and Bof blue points, we consider several measures of how far they are from being separable. Intuitively, given a potential separator (‘‘classifier’’), we measure its quality (‘‘error’’) according to how much work it would take to move the misclassified points across the classifier to yield separated sets. We consider several measures of work and provide algorithms to find linear classifiers that minimize the error under these different measures. 1. Introduction Current massive data collection methods have provided researchers with a wealth of data, together with the challenge of making sense of it. Partitioning or clustering data as a method of data analysis is an important tool in providing meaning to large amounts of data. Performing this type of analysis is multifaceted, and can range from applications in geography and land use, pattern recognition, medical health studies, economics, detecting similarity between genres of music, and data mining to assist in targeted marketing strategies, to name but a few. Partitioning data using separators or classifiers to perform cluster analysis on training sets is a standard technique, for example it is used in pattern recognition applications [22]. Thus the problem of determining if two disjoint point sets are separable has been widely studied in the literature. See for instance Megiddo [35] for the seminal fixed dimension linear programming method for linear separability. Elizondo [24] surveys a variety of techniques and discusses the application of linear separability to machine learning. O’Rourke et al. [36] and Boissonnat et al. [7] consider algorithms for circular separability, and Hurtado et al. [30] and Arkin et al. [3] examine a variety of separability criteria. In some applications the training data may contain some points that have been misclassified resulting in the situation where no natural1partition scheme classifies the data. In this case classification is attempted where some amount of error is tolerated. Within that context, Aronov and Har-Peled [4] studied the following problem: given a bicolored point set, find a ball that contains the maximum number of red points without containing any blue points. Cortés et al. [18] address the ∗Corresponding author. E-mail addresses: [email protected] (B. Aronov), [email protected] (D. Garijo), [email protected] (Y. Núñez-Rodríguez), [email protected] (D. Rappaport), [email protected] (C. Seara), [email protected] (J. Urrutia). 1Here by a natural partition we mean a partition given by a simple classifier like disk, square, or a halfplane. problem of finding two boxes SRand SBsuch that the number of red and blue points in SRand SBrespectively is maximized, while ignoring the points in SR∩SB. Mathematical programming techniques have been used in the operations research community to solve similar problems [5,19,31,40]. In this paper we present algorithms that minimize the error when using a linear separator. Given two linearly inseparable point sets we attempt to find a hyperplane which splits the union of the sets into disjoint subsets in such a way that some error functions are minimized. We call such hyperplanes optimal classifiers. The notion of optimality is left intentionally informal as the precise properties that should be optimized are application dependent. We will examine several different criteria for choosing an optimal classifier. We will proceed on the assumption that the dimension dof the problem is a small constant and be mostly concerned about the asymptotic dependence of the speed of our algorithms on the size nof the point sets. Let Rbe a set of rred points and Ba set of bblue points in Rd. Let n:= r+bbe the total number of points and assume that the point sets are disjoint and in general position, that is, no d+1 of the points lie in the same hyperplane in Rd. We say that Rand Bare (linearly) separable if there exists a (linear) separator, which is an oriented hyperplane so that the red points lie to its left and the blue points lie to its right. (Formally, each side of the hyperplane is a closed halfspace delimited by it, so points on the hyperplane are considered to lie on both sides simultaneously.) If there is no separator for Rand B, then we say that the sets are inseparable. Let P= {p1, . . . , pn} := R∪B. Let hbe a hyperplane x1a1+ ··· + xdad=a0, and let h−be the halfplane containing the points (x1,...,xd)such that x1a1+ ··· + xdad≤a0, and h+be the halfspace that contains the points satisfying x1a1+ ··· + xdad≥a0. We will say that h−lies to the left of h, while h+lies to the right of h. If hwere a separator of P, we would have R⊂h−and B⊂h+. As it is not, it misclassifies the red points R(h):= Rrh−and the blue points B(h):= Brh+. We use Ξ=Ξ(h):= R(h)∪B(h)to denote the set of points misclassified by h. We use s(h)to represent the quality of has a classifier; it depends on hand Ξ=Ξ(h). Our goal is to find a hyperplane that minimizes the cost under one of the following four measures, where d(·,·)denotes the Euclidean distance between points in Rdand d(p,X)denotes the Euclidean distance from a point pto a set X: MinMax: Maximum Euclidean distance from hto a point in Ξ, i.e., s∞(h):= max p∈Ξ(h) d(p,h)=max{max p∈Rd(p,h−), max p∈Bd(p,h+)}. MinSum: Sum of the Euclidean distances from hto points in Ξ, i.e., s1(h):=  p∈Ξ(h) d(p,h)= p∈R d(p,h−)+ p∈B d(p,h+). MinSum2: Sum of squares of the Euclidean distances from hto points in Ξ, i.e., s2(h):=  p∈Ξ(h) d2(p,h)= p∈R d2(p,h−)+ p∈B d2(p,h+). MinMis: Just the cardinality of Ξ, i.e., the number of misclassified points, s0(h)= |Rrh−|+|Brh+|. We are interested in finding an optimal classifier, which we define to be a halfspace hOpt minimizing the quantity s(h); it is not always unique. Notice that since d(p,h±)is a continuous function of h, so are s∞(h), s1(h), and s2(h). We will use a standard duality transform. It maps a point p∈Rdto a non-vertical hyperplane p∗⊂Rd, and vice versa, that is, it maps a non-vertical hyperplane hto the point h∗such with (h∗)∗=hand (p∗)∗=p; moreover pis above hif and only if h∗is above p∗. Outline of the paper. We present algorithms to find optimal classifiers using the four measures described above. In Section 2we present solutions for the one-dimensional problem, as this will provide some illuminating intuition for proceeding to problems of higher dimension. We devote Section 3to describing some crucial observations that relate the separability problems in one dimension to those in higher dimensions. In Sections 4–7 we study each of the measures in arbitrary dimension. The algorithms are based on existing techniques from the computational geometry literature. We show that finding an optimal classifier using the MinMax measure is equivalent to determining the penetration depth between two convex polyhedra, and can therefore be solved using existing methods. For optimizing classifiers using the MinSum,MinSum2, and MinMis measures we use duality and levels in arrangements to systematically enumerate candidate solutions. The computational complexities of the algorithms are summarized in the following Table 1. 2. One dimension We first consider the one-dimensional case of our set of problems. The input sets Rand Blie on the real line. Then a classifier is a point h. We will assume that h+is the half-line [h,+∞)and h−is the half-line (−∞,h]; the reverse case is handled by a symmetric argument. For simplicity, we will omit the symmetric cases in the statement of our lemmas. We seek the point (or points) hOpt minimizing s(h). Notice that d(p,h+)is convex as a function of h, as is its square ((p−h)2for h≥p, and 0 for h<p); the same holds for d(p,h−). Since the first three error measures are defined as the maximum, sum, and the sum of squares of these functions Table 1 Summary of the time complexities. Dimension MinMax MinSum MinSum2MinMis d=1Θ(n)Θ(n)Θ(n)Θ(nlog n) d=2Θ(nlog n)O(n4/3log1+ϵn)O(n2)O(n2) O(n4/3)* d=3O(n2)O(n5/2log6n)*O(n3)O(n3) d>4O(n⌈d/2⌉)O(nd)O(nd)O(nd) *Randomized expected time. over all p∈P, in each case s(h)is a convex function of h. Therefore it attains its minimum at a unique closed interval. In fact, only s1may attain its minimum on a non-zero-length interval. 2.1. MinMax Recall that s∞(h)is the pointwise maximum of piecewise-linear convex functions and thus piecewise-linear and convex. It is easily checked that it is nowhere constant, since Rand Bare inseparable, and hence has a unique minimum. Observation 1. The optimal MinMax classifier hOpt is the mean of the leftmost blue point and the rightmost red point and can be computed in Θ(n)time. Indeed, by definition, the cost s∞(h)is realized by the misclassified points furthest from hand thus can be reduced by a small change of hin the appropriate direction, unless it is midway between extreme misclassified points, as claimed. 2.2. MinSum Recall that s(h):= s1(h)is a sum of npiecewise-linear convex functions and thus piecewise-linear and convex. Therefore it achieves its minimum at a unique point or a closed interval, where it is constant. Specifically, between consecutive points of P,s(h)=p∈R(h)d(p,h−)+p∈B(h)d(p,h+)=p∈R(h)(p−h)+p∈B(h)(h−p)is a linear function with slope −|R(h)|+|B(h)|. It has breakpoints at points of P. Therefore, we have Theorem 2. In one dimension, optimal MinSum is achieved at any point with the property that the number of red and blue misclassified points is equal. More precisely, hOpt lies in the closed interval between the rth and (r+1)st point of P, counting from the left, or between the bth and (b+1)st point, counting from the right. This interval can be computed in optimal linear time.2 Proof. The first statement follows from previous discussion, while the second can be deduced by counting the number of points to the left of hOpt, when it does not coincide with a point of P: since the number of red points to the right of hOpt is equal to the number of blue points to the left of it, the total number of points to its left is precisely r, as claimed. Since the minimum must be achieved on a closed interval, this must be the interval delimited by the rth and (r+1)st points from the left; such an interval always exists, as −|R(h)|+|B(h)|starts at −r, ends at band shrinks by exactly one every time h crosses a point of P. Since the total number of points is n=r+b, the claim follows. The desired interval can be computed by using a linear-time select algorithm [6].  2.3. MinSum2 Uniqueness of the optimum follows from our previous observations. Indeed, d2(p,h+)and d2(p,h−)are both convex, continuous, everywhere differentiable functions; each is composed of a quadratic and strictly convex portion and an identically zero portion. The sum of nsuch functions is convex. Moreover, its minimum can be attained along a non-zerolength interval only if all the constituent functions are zero within it, which is not possible for inseparable point sets. To find the unique minimum, consider a candidate separator h. Then MinSum2error is given by s2(h)= p∈R d2(p,h−)+ p∈B d2(p,h+)= p∈R(h) d2(p,h)+ p∈B(h) d2(p,h) = p∈Ξ(h) (p−h)2=h2·|Ξ(h)|−2h· p∈Ξ(h) p+ p∈Ξ(h) p2, which is a piecewise quadratic function. Put Σ(h):= p∈Ξ(h)p. By previous discussion, s2(h)is strictly convex and differentiable everywhere, hence its minimum value must occur in that interval between consecutive points of Pwhere 2A result similar to Theorem 2 is proved by Simon [42] but in the context of the support vector machines and the algorithmic learning theory. hOpt := Σ(h)/|Ξ(h)|occurs within the interval; this value has a geometric interpretation: hOpt is the arithmetic mean (i.e., the centroid) of the misclassified points. Thus it remains to explain how to find this unique minimum. An O(nlog n)algorithm is clear: after sorting P, we compute |Ξ(−∞)|and Σ(−∞), and then incrementally update them, maintaining Σ(h)and Ξ(h), and evaluating Σ(h)/|Ξ(h)|for every interval between consecutive points of P, until we find the unique interval containing the local (and, therefore, global) minimum. In fact, the optimum can be identified in linear time by a prune-and-search procedure; refer to algorithm 1, where Σrepresents the sum of the coordinates of the points we know will be misclassified in the optimal solutions and Nrepresents the number of such points. Its correctness follows from the convexity of s2(h)and the above discussion. Its running time is linear, as it obeys a recurrence of the form T(n)≤cn +T(n/2). Thus we have shown Theorem 3. The one-dimensional MinSum2problem has a unique solution which can be found in optimal linear time. Input: Inseparable sets Rof red points and Bof blue points on a line, with a total of npoints. Output: The value hOpt at which the MinSum2error measure s2(h)is minimized. Initialization: Σ←0; N←0; repeat Determine pand q, the points that straddle the median rank in P; ΣB←the sum of the coordinates of the blue points to the left of pin P; ΣR←the sum of the coordinates of the red points to the right of qin P; NB←the number of blue points to the left of pin P; NR←the number of red points to the right of qin P; h←ΣB+ΣR+Σ NB+NR+N; switch hdo case p<h<q return h; end case h<p P←subset of Pto the left of h; Σ←Σ+ΣR; N←N+NR; end case h>q P←subset of Pto the right of h; Σ←Σ+ΣB; N←N+NB; end end until ; Algorithm 1:AverageOfMisclassified. 2.4. MinMis Consider inseparable point sets Rand B. A different way to achieve separability is by removing misclassified points. The MinMis problem for R∪Bis equivalent to computing an optimal classifier for Band Rthat minimizes the number of misclassified points (see [25] for the problem in two dimensions). In order to compute a classifier hOpt yielding the minimum number of misclassified points, i.e., the classifier hOpt that minimizes s:= s0(h)= |Ξ(h)|, we sort the points in O(nlog n)time, obtaining a linear number of intervals delimited by consecutive points. Any point in an interval gives the same value of s. Scanning the points left to right, while maintaining the number of misclassified points of either color, one can determine the value of sin each interval, and therefore the minimum value, in linear time. We thus obtain an overall O(nlog n)time algorithm for computing the optimal classifier (either a point or an interval). Next we see that this algorithm is optimal. Consider the following ε-distance problem for points on a line [3]: The ε-distance problem. Given a set of npoints x1,...,xnon a line and a real value ε > 0, decide whether |xi−xj|> ε, for all i,j∈ {1,...,n},i= j. The ε-distance problem has an Ω(nlog n)-time lower bound in the algebraic computation tree model [3]. Now we reduce the ε-distance problem to our MinMis problem as follows. We are given x1,...,xnand ε > 0. For each xiwe add ri=xi−ε/2 to Rand bi=xi+ε/2 to B. In addition, we create 10n red points to the left of all points considered so far and 10nblue points to the right of all of them. This can be easily done in linear time. This ensures that the left side of the classifier is considered red and the right is blue, for the optimal classifier. Refer to Fig. 1. Fig. 1. Lower bound construction. Fig. 2. Projecting an optimal solution. Now, if |xi−xj|> ε, for all i,j∈ {1,...,n},i= j, then the red and blue points coming from points xialternate along the line: red, followed by blue, followed by red, etc. Thus for a separator hlying between these points, the number of misclassified points oscillates between nand n−1. In particular, it is easy to check that the number of misclassified points is at least n−1 for any position of hand the minimum is n−1. On the other hand, if there exist iand j= i, such that |xi−xj| ≤ ε, then there is at least one point common to the intervals [ri,bi]and [rj,bj], for i= j. Such a point misclassifies no more than n−2 points. Thus we have proved Theorem 4. The one-dimensional MinMis problem can be solved in O(nlog n)time and this is the best possible in the algebraic computation tree model. 3. From one to higher dimensions Before proceeding with the higher-dimensional versions of our problem, we make the following simple but crucial observation which follows from the fact that signed Euclidean distances to a hyperplane are preserved under an orthogonal projection to a line orthogonal to the hyperplane (refer to Fig. 2): Observation 5. Let hOpt be an optimal classifier for inseparable sets R,B⊂Rd,d>1, for any of our error measures. Let ℓbe the line perpendicular to hOpt and passing through the origin, and let R⊥,B⊥, and h⊥ Opt be the respective orthogonal projections of R,B, and hOpt to ℓ. Then h⊥ Opt is an optimal classifier for the one-dimensional problem R⊥,B⊥for the same error measure. We find the following general approach to obtain an optimal classifier useful for several different error measures. Given a non-vertical candidate classifier hyperplane h, we aim to place red points to the left of it and blue points to the right of it (vertical classifiers can often be handled by an extension of the following discussion, or directly, as a problem of finding an optimal classifier in one lower dimension). Classifiers with red points to the right of them and blue points to the left are handled by a symmetric argument. Given a set P=B∪Rof points, and a candidate classifier h, the exact analytical form of the error measure s(h)depends on the set Ξ(h)of misclassified points, which in turn is determined by the way in which hpartitions P; in fact, for all measures but s∞the analytical form is completely determined by this bipartition. We now consider the situation in the dual: let A:= A(P∗)be the arrangement of the planes dual to points of P[23]. The various bipartitions of Pby hcorrespond precisely to the various cells of Athat may contain the point h∗dual to h. As we will see in following sections, the analytical form of s(h)for MinSum and MinSum2is not only completely determined by the cell Ccontaining h∗, but can also (1) be updated from cell to neighboring cell in constant time and (2) be used to compute arg minh∗∈Cs(C)in constant time, under certain assumptions on our model of computation; see below for details. An analogous statement holds for MinMis, with ‘‘cells’’ replaced by ‘‘faces of any dimension’’, as this error measure is not continuous. This implies Theorem 6. Let R and B be inseparable points sets in Rd,d>1. An optimal classifier according to MinSum,MinSum2, or MinMis error measure can be computed in O(nd)time. We devote the next section to MinMax, which requires separate treatment. We further discuss the remaining measures and related existing work in Sections 5–7. abcd Fig. 3. Antipodal pairs from CH(B)and CH(R)are shown in four representative configurations. 4. Higher dimensions: MinMax Recall that we have assumed that Rand Bare inseparable, so that the convex hulls CH(R)and CH(B)properly intersect. Combining Observations 1 and 5, we notice that an optimal classifier hin any fixed direction, for the MinMax measure, occurs half-way between the left supporting hyperplane of Band the right supporting hyperplane of Rparallel to h. The error s(h)is precisely half the distance between these hyperplanes. Hence minimizing s(h)is equivalent to minimizing this distance, over all orientations of h. It is not difficult to see that the smallest such distance, over all possible orientations of h, is precisely the minimum distance by which one needs to translate CH(R)to separate it from CH(B). This quantity has been studied in the past, under the names intersection depth and penetration depth [2,8,15,21,32,33]. In the light of the previous discussion, the two-dimensional version of the problem can be solved in linear time by the rotating-calipers method [44], once the convex hulls of Rand Bhave been computed. (Recall that the convex hull of a set of n points in two dimensions can be computed optimally in O(nlog n)time, using O(n)space [23].) See Fig. 3 for an illustration. Thus we have Theorem 7. The two-dimensional MinMax problem can be solved in O(nlog n)time, using O(n)space. This cannot be improved in the algebraic computation tree model. To show that the algorithm is worst-case optimal, we use a reduction from the Max–Gap problem for points on the first quadrant of the unit circle which is known to have an Ω(nlog n)lower bound in the algebraic computation tree model [3]. An instance of Max–Gap for points on the first quadrant of the unit circle is a set of points Z, together with the question: What is the maximum Euclidean distance between consecutive points? The reduction is as follows. Let a set Zof npoints on the open first quadrant of the unit circle be an instance of Max–Gap. Put R1:= Z= {r1,...,rn}, where riare numbered in their x-order (which is not given). Reflect R1through the origin to obtain a set B1= {b1,...,bn}of blue points in the third quadrant, as illustrated in Fig. 4. Construct three additional red points r′ iand symmetrically located blue points b′ i; refer to Fig. 4. We draw vertical and horizontal lines at distance 2 from the origin. The point r′ 2lies at the bottom left corner of the resulting 4 ×4 square; r′ 1is chosen on the left edge of the square so that r1r′ 1is tangent to the circle. The remaining additional points are constructed analogously. Put R:= R1∪{r′ 1,r′ 2,r′ 3} and B:= B1∪{b′ 1,b′ 2,b′ 3}. Now consider the resulting MinMax optimization problem for Rand B. Observe that the smallest distance between parallel support lines of CH(R)and of CH(B)occurs when the lines pass through points that give the Max–Gap of Z, as indicated in the figure. Thus the solution of the MinMax problem would yield a line hfrom which one can, in linear time, identify Max–Gap in Z, completing the proof. In three dimensions, the MinMax problem (also known as penetration depth) can be solved by examining all pairs of potential contacts made by two supporting planes with opposite orientations, one for CH(R)and one for CH(B). (Recall that the convex hull of a set of npoints in three dimensions can be computed optimally in O(nlog n)time.) The problem with this approach is that the number mof such pairs of contacts is quadratic in the worst case, as in the width problem [29]. Any algorithm that evaluates all such pairs of contacts will run in worst-case time Ω(n2). By using the techniques developed by Houle and Toussaint [29] we can obtain an optimal approximate MinMax separator in O(m+nlog n)time, but this is not the best possible. There exists extensive literature on width computation and penetration depth, as mentioned above. In particular, in [2] it was shown how to compute the penetration depth in expected time O(n3/2+δ), for any δ > 0. (In fact, the expected running time of the algorithm is actually O(m1/2+δn1/2+n1+δ), so it will run significantly faster when m≪n2.) As for the width problem, for d≥4, an O(n⌈d/2⌉)time algorithm can be achieved by realizing the solution space as a convex polytope in Rd+1, applying an optimal halfspace intersection algorithm, triangulating the resulting set, and explicitly optimizing s∞(h)function over each simplex separately [10,16]. (Recall that the convex hull of a set of npoints, or the intersection of nhalfspaces, in any fixed dimension d≥4 can be computed optimally in O(n⌈d/2⌉)time [14].) Fig. 4. The construction of the sets Rand Bfrom Zis shown illustrating the lower bound argument. 5. Higher dimensions: MinSum As outlined at the end of Section 3, one can find the optimal classifier for the MinSum measure by effectively examining all candidate classifiers h, or equivalently, enumerating all possible placements of the point h∗dual to hin the arrangement A. In this section we explain the details of this process and simplify it a great deal by proving the following theorem, which implies that only the vertices of the dual arrangement Aneed to be examined. Theorem 8. Let R and B be inseparable points sets in Rd,d>1. Then there is an optimal classifier hOpt of R and B that contains d affinely independent points of R ∪B. Equivalently, h∗ Opt lies at a vertex of A. The vertex must belong to a cell of the r-level of A. Proof. We will make a slight notational adjustment, just for the duration of this section. We will be discussing ways in which a hyperplane hpartitions a point set P. This is unambiguous as long as hdoes not pass through any of the points. In the dual, as long as h∗stays off the hyperplanes of P∗, there is a clear notion of which hyperplanes lie below it and which lie above. Starting with a point h∗in an open cell cof A, consider the set Ξ(c)=Ξ(h)of misclassified points. Now fix this set Ξ(c)and let h∗vary over the closed cell ¯ c: in the following discussion we treat just the points of Ξ(c)as misclassified, and none other. This varies from our original definition in that some points contained in hwill now be considered misclassified. This does not affect our measure of error, as the contribution of a point on hto s(h)is zero, whether or not it is considered misclassified. The effect of this adjustment in the dual is as follows: for a generic point h∗∈c, we determine which hyperplanes of P∗ lie above and which below, and then extend this convention to points h∗lying on the boundary of c. Recall that translating a candidate classifier hparallel to itself corresponds to moving h∗along a line parallel to the xd-axis. Applying Theorem 2 and Observation 5 to the best classifier in this family of hyperplanes, we conclude that there must be precisely rhyperplanes above h∗and precisely bhyperplanes below it, i.e., h∗must lie in a (closed) cell on the r-level of A. (A full-dimensional cell lies on the r-level of A, or is an r-level cell, when precisely rhyperplanes pass below it.) Additionally, putting ρ=ρ(h):= |R(h)|and β=β(h):= |B(h)|, we must have ρ=βfor an optimal classifier. We observe that s(h)= p∈R(h) d(p,h)+ p∈B(h) d(p,h)=ρd(h,C(R(h))) +βd(h,C(B(h))) =ρ(d(h,C(R(h))) +d(h,C(B(h)))), where we have used C(·)to denote the centroid of a set. Fix a closed r-level cell ¯ c. Since (with our adjusted convention) ρis a constant over ¯ c, to minimize s(h)over ¯ c, it is sufficient to minimize the expression H(h):= d(h,C(R(h))) +d(h,C(B(h))) over ¯ c. We now argue that this latter expression can attain its minimum only at a vertex of ¯ c. In short, the function we are minimizing is the sum of the distances to centroids of the red and the blue misclassified points, which by definition lie on the opposite sides of h. If there were no restrictions on positioning the hyperplane h, the function would achieve its minimum value of zero when hpassed through the two centroids. Minimizing H(h), while constraining h∗to lie in ¯ c, is equivalent to restricting our attention to those hyperplanes hthat separate CH(R(h)) and CH(B(h)). We argue that among all such hyperplanes h, none can minimize s(h)without passing through d(affinely independent) points of P. Indeed, H(h)= |s|sin α, where αis the angle between hand the segment s:= C(R(h))C(B(h)) and |s|is the length of s;H(h)cannot achieve its minimum of zero, since the endpoints of slie on opposite sides of hand having slie within hwould imply that Rand Bare separable, contradicting our assumptions. We first argue that hmust be a separating tangent of CH(R(h)) and CH(B(h)). If hstrictly separates the two sets, it can be rotated (say, around s∩h) to decrease αand thus h. Hence hmust touch at least one of the sets. If hmisses the other set, it can be shifted parallel to itself without affecting H(h)to strictly separate the two sets, yielding a contradiction, as above. Thus his a tangent to the two sets and passes through at least two of their vertices. As long as the affine dimension of h∩Pis less than d−1, we can rotate haround h∩P. It is easy to check that at least one ‘‘direction’’ of this rotation reduces αand thus H(h). (For specificity, pick any d−2-flat πcontaining h∩Pand rotate haround it: there is a one-dimensional family of hyperplanes containing π, so this rotation is well-defined. By assumption, if rotated by a sufficiently small amount in either direction, hcontinues to be an inner tangent of CH(R(h)) and CH(B(h)). In at least one direction, however, the angle αdecreases. Hence the original hcould not minimize H(h), as claimed.) Therefore, as long as hcontains fewer than dpoints of P, there is at least one direction in which it can be infinitesimally rotated around the points h∩P, while maintaining tangency to CH(R(h)) and CH(B(h)) and reducing α. Thus any such choice of a hyperplane cannot be a minimum, for a given bipartition. In other words, the affine hull of hOpt ∩P, for an optimal classifier hOpt, must have dimension d−1, or h∗ Opt must be a vertex of A, as claimed.  5.1. MinSum for d =2 Let hbe a candidate classifier line for Rand Baccording to the MinSum criterion, with h+(h−)denoting the closed halfplane to the right (left) of h. Let h:ax +y+e=0. Denote by px,pythe coordinates of a point p. The contribution of p∈R(h)to s(h):= s1(h)is apx+py+e √a2+1, while the contribution of p∈B(h)is given by a similar expression, with a negative sign. Summing the contributions of all points and using the fact that |B(h)|=|R(h)|(see proof of Theorem 8), we obtain s(h)=s(a)=A1a+A2 √a2+1, where A1=A1(h):= p∈R(h)px−p∈B(h)pxand A2=A2(h):= p∈R(h)py−p∈B(h)py;A1and A2depend only on the bipartition of Pby hand not on the precise placement of h; the function, for a fixed Ξ, depends only on a, the slope of h. As noted above, the optimum must be achieved at a vertex of an r-level cell in A(see Fig. 5). Tight bounds on the maximum complexity (i.e., number of edges and vertices) of the r-level cells in an arrangement of nlines are not known—determining the order of magnitude of this quantity as a function of nis a long-standing open problem in discrete geometry. For r=Θ(n) it is known to be neΩ(√log n)[43] and O(n4/3)[20]. There is extensive literature for constructing levels in line arrangements. The best known deterministic algorithm is due to Chan [9] and runs in O(n4/3log1+εn)time and O(n)space. Chan [9,13] presented a randomized algorithm that guarantees O(n4/3)expected time for constructing the r-level in an arrangement of nlines in the plane; the bounds improve somewhat if r≪n. Once the r-level cells have been computed, the remaining computations can be carried out in time proportional to the size of the level. Hence we have a deterministic O(n4/3log1+εn)time algorithm and a randomized O(n4/3)expected running time algorithm for finding the set of all optimal classifiers minimizing the MinSum error measure in the plane. Theorem 9. The two-dimensional MinSum problem can be solved deterministically in time O(n4/3log1+εn)for an arbitrarily small constant ε > 0or in O(n4/3)expected time. 5.2. MinSum for d ≥3 The foregoing discussion extends to three and higher dimensions. We illustrate the calculations in three dimensions. Let h:ax +ey +z+f=0 be a plane with normal vector (a,e,1). Let p=(px,py,pz)∈P, then d(p,h)is given by d(p,h)= ±apx+epy+pz+f √a2+e2+1, with the sign chosen according to whether p∈h+or p∈h−. Since, by Theorem 2 and Observation 5,|B(h)| = |R(h)|, we have s(h)=aA1+eA2+A3 √a2+e2+1, where A1=A1(h):= p∈R(h)px−p∈B(h)px,A2=A2(h):= p∈R(h)py−p∈B(h)py, and A3=A3(h):= p∈R(h)pz− p∈B(h)pz. These values are constants for a fixed bipartition, i.e., for h∗in a fixed cell of A. Hence, these quantities and the exact analytic expressions for s(h)can be maintained in constant time, when moving from a level-rcell to an adjacent level-rcell. The total complexity of the cells on the r-level is the number of their vertices, edges, and faces. Under general position assumptions, it is proportional to the number of vertices of the cells involved. The number of vertices of the r-level is at Fig. 5. A set of 8 points in the plane (left). The level-4 cells in the dual arrangement of the 8 lines (right). most O(nr3/2)[41]; the exact maximum complexity of the r-level is a long-standing open problem in discrete geometry. Chan [12] gives an O(nlog n+nr3/2log6r)expected time algorithm for constructing the r-level in an arrangement of n planes. As before, given the set of r-level cells, we traverse these cells in a, say, depth-first-search order of the graph of their adjacencies, going from cell to neighboring cell c, updating the quantities A1(c), A2(c)and A3(c)in constant time and obtaining the exact closed-form equation for the function s(c)for the current cell. By Theorem 8, evaluating s(h)on all vertices of r-level cells is sufficient to locate the optimal classifier(s). Each such evaluation is done in constant time, apart from some initialization cost, so the running time is dominated by the complexity of computing the r-level. Theorem 10. The three-dimensional MinSum problem can be solved in O(n5/2log6n)expected time. In higher dimensions, the same approach still applies. Namely the optimum is achieved by hdual to a vertex of an r-level cell of A. Thus it is sufficient to evaluate the function at these vertices. This can be done in constant time per vertex, after some linear-time set-up. The bottleneck again is computing the said vertices. Again, determining the order of magnitude of the maximum number of such vertices is a long-standing open problem in discrete geometry. It is asymptotically the same as the complexity of the r-level. For dimension d≥4, the best known upper bound for the size of the r-level is only slightly better than the On⌊d/2⌋r⌈d/2⌉[16]. More specifically, it is O(nd−αd) for a very small constant αd=1/(4d−3)d. As Agarwal et al. [1] observed, the bound can be made sensitive to r, namely O(n⌊d/2⌋r⌈d/2⌉−αd). Matoušek et al. [34] give an O(n4−2/45)upper bound for d=4. For an arbitrary fixed dimension d, the r-level in an arrangement of nhyperplanes in Rdcan be constructed deterministically (see Chan [13]) in time On⌊d/2⌋r⌈d/2⌉log n log rO(1). To summarize, we have proven Theorem 11. The d-dimensional MinSum problem can be solved deterministically in time On⌊d/2⌋r⌈d/2⌉log n log rO(1)=O(nd). 6. Higher dimensions: MinSum2 We proceed to implement the plan outlined at the end of Section 3for MinSum2. Namely, we consider the dual arrangement Aand evaluate s2(h)for h∗ranging over all cells cof A. This corresponds to fixing the sets R(h)=R(c)and B(h)=B(c)and therefore the expression for s2(h)in terms of the coordinates of h∗. The function is a quadratic expression whose minimum can be computed in constant time, in constant dimension; this assumes the ability to compute roots of a system of O(d)equations in dunknowns, which is not an uncommon assumption in computational geometry; in d=2 the minima can be computed explicitly in radicals. We fill in some of the details below. 6.1. MinSum2for d =2 Let hOpt:ax +y+e=0 be the optimal classifier line according to the MinSum2criterion. The squared distance between a point pand the line his given by d2(p,h)=(apx+py+e)2 a2+1.