Linear separation and approximation by minimizing the sum of concave functions of distances

4OR-Q J Oper Res (2014) 12:77–85 DOI 10.1007/s10288-013-0245-0 RESEARCH PAPER Linear separation and approximation by minimizing the sum of concave functions of distances Frank Plastria ·Emilio Carrizosa Received: 13 May 2013 / Published online: 20 September 2013 © Springer-Verlag Berlin Heidelberg 2013 Abstract One recently proposed criterion to separate two data sets in Classification is to use a hyperplane that minimizes the sum of distances to it from all the misclassified data points, where misclassification means lying on the wrong side of the hyperplane, or rather in the wrong halfspace. In this paper we study an extension of this problem: we seek the hyperplane minimizing the sum of concave nondecreasing functions of the distances of misclassified points to it. It is shown that an optimal hyperplane exists containing at least daffinely independent points. This extends the result known for the minimization of the sum of distances, and enables to use combinatorial localsearch heuristics for this problem. As a corollary, the same result is obtained for the approximation problem in which a hyperplane minimizing the sum of concave nondecreasing functions of the distances from a set of data points is sought. Keywords Linear separation ·Linear approximation ·Distance minimization Mathematics Subject Classification 90B85 ·62-07 ·68U05 1 Nonlinear distance functions Two nonempty finite data sets A,Bin Rdare said to be linearly separable if there exist u∈Rd,u= 0 and β∈R,such that the hyperplane, The research of the authors was partially supported by the projects FWOAL453 and VUB-GOA62 (Belgium) and MTM2009-14039 and FQM-329 (Junta de Andalucía, Spain). F. Plastria (B) MOSI, Vrije Universiteit Brussel, Pleinlaan 2, 1050 Brussels, Belgium e-mail: [email protected] E. Carrizosa Fac. de Matemáticas, Universidad de Sevilla, Tarfia s/n, 41012 Sevilla, Spain e-mail: [email protected] 123 78 F. Plastria, E. Carrizosa H(u,β)def ={x∈Rdu;x=β}, satisfies u;a≥β∀a∈A u;b≤β∀b∈B(1) In this paper we consider the case where the sets A,Bare not linearly separable, and thus a hyperplane H(u,β)satisfying some relaxation of (1) is sought. A first strategy, proposed by Mangasarian (1994), amounts to finding a hyperplane maximizing the number of constraints in (1) that are satisfied, max |A∗|+|B∗| s.t. u;a≥β∀a∈A∗ u;b≤β∀b∈B∗ A∗⊂A,B∗⊂B u= 0,β∈R (2) A different strategy, proposed in Mangasarian (1999) and later analyzed in Carrizosa and Plastria (2008), Karam et al. (2007), is based on the minimization of distances to correct classification, as described below. See also Plastria and Carrizosa (2012)fora minmax approach. Given u∈Rd,u= 0 and β∈R,let H(u,β) ≥and H(u,β) ≤denote the two closed halfspaces with common boundary H(u,β), H(u,β) ≥def =x∈Rd:u;x≥β H(u,β) ≤def =x∈Rd:u;x≤β According to (1) any point a∈A(resp. b∈B) is misclassified when a∈ H(u,β) ≥ (resp. b∈ H(u,β) ≤). Given a norm γin Rd,let dγbe the distance in Rdinduced by γ, and consider the problem of finding the hyperplane minimizing the sum of distances of the points to their respective halfspace of correct classification, min  a∈A dγ(a,H≥(u,β))+ b∈B dγ(b,H≤(u,β)) s.t. u= 0,β∈R (3) Observe that dγ(a,H≥(u,β)) =(−u;a+β)+ γ◦(u)(4) dγ(b,H≤(u,β)) =(u;b−β)+ γ◦(u),(5) Carrizosa and Plastria (2008), where (t)+=max{t,0},and γ◦is the norm dual to γ. 123 Linear separation by minimizing concave functions of distances 79 In this paper we address an extension of models (2) and (3). A different way of combining (2)–(3) can be found in Chen and Mangasarian (1996). Here, instead of summing the misclassification distances as in (3), we take the sum of misclassification costs, where cost is a function of distance with certain properties. More precisely, consider the set of functions F, Fdef ={f:R+−→ R+fis concave,with f(0)=0}.(6) Any f∈Fsatisfies f(s)≥0 for all s≥0,and when applied to distances yields a cost (which is zero for zero distances). On the other hand, concavity implies a diminishing effect of larger distances, which is a necessary condition for robustness. See Carrizosa and Rodríguez-Chía (1997) for further motivation for this model of cost functions. The definition implies that any f∈Fis nondecreasing in R+,Plastria (2009). For each a∈A,(resp. b∈B,)let fa(resp. fb)beafunctioninF,and consider the problem min  a∈A fa(d(a,H≥(u, β))) + b∈B fb(d(b,H≤(u, β))) s.t. u= 0,β∈R, which, by (4)–(5), can be written as min F(u,β)def = a∈A fa(−u;a+β)+ γ◦(u)+ b∈B fb(u;b−β)+ γ◦(u) s.t. u= 0,β∈R. (7) A possible choice for functions fin (7)is f(t)=tp(0 <p≤1). In particular, for p=1, one obtains (3), whereas values of p,0<p<1 have been advocated, in a related context, by Stam (1997); the step function f(t)=1,if t>0 0,if t=0(8) which counts the number of misclassified points, yields (2); other functions of possible interest such as f(t)=min{t/C,1}or f(t)=1−e−tC (C>0) remain, as far as we know, unexplored. The purpose of this note is to show that, under these concavity conditions, there always exists an optimal solution (u,β)to (7) such that H(u,β)contains sufficiently many data points. It follows that complete enumeration can be used as a polynomial resolution technique. 2 The localization property Before we show the localization property, the following technical lemmas are needed. 123 80 F. Plastria, E. Carrizosa Lemma 1 Let K be a convex set in Rd+1.Then, the set R++ ·K defined as R++ ·Kdef ={z∈Rd+1:z=ty for somet >0,y∈K} is convex. This is in fact simply the (pointed) conical hull of K(i.e. without the origin in case 0/∈K) Lemma 2 Let νbe a norm in Rd+1.Let S be a pointed cone in Rd+1such that ν(x)>0∀x∈S.Let v1,...,v k∈Rd+1be such that vi;x≥0for all x ∈S,and let f1,..., frbe concave nondecreasing functions in R+.Then, the function ϕ, ϕ(x)= r  i=1 fivi;x ν(x) is quasiconcave on S. Proof First observe that ϕis well defined in Ssince ν(x)>0∀x∈S. Define, for α≥0,the set Lαas the upper level set of ϕ, namely: Lα={x∈S:ϕ(x)≥α} It suffices to show that, for any α, the set Lαis convex. Convexity of Lαwill be shown by showing that Lα=R++ ·y∈S: r  i=1 fi(vi;y)≥α∩{y:ν(y)≤1}.(9) By the concavity of the functions fi,the functions fi(vi;y)are concave, so their sum is also concave and its upper level sets are convex. Hence, by Lemma 1the righthandside set is convex, and then the result follows. Let us show (9). We have by definition of Lαthat Lα= ε>0x∈S: r  i=1 fivi;x ν(x)≥α, ν(x)=ε(10) = ε>0x∈S: r  i=1 fivi;x ε≥α, ν(x)=ε(11) = ε>0x∈S: r  i=1 fivi;x ε≥α, ν(x)≤ε,(12) where the last equality follows from the following: it is evident that the set in (11)is included in the one in (12); any xin this latter set satisfies x∈S, and there exists 123 Linear separation by minimizing concave functions of distances 81 some ε>0 such that ν(x)≤ε, and r  i=1 fivi;x ε≥α By assumption all vi;x≥0, so vi;x ν(x)≥vi;x εand, since all fiare nondecreasing, r  i=1 fivi;x ν(x)≥α. This shows that xbelongs to the set in (11) for the choice ε=ν(x). Hence, Lα= ε>0x∈S:x=εy, r  i=1 fi(vi;y)≥α, ν(y)≤1 = ε>0x∈Rd+1:x=εy,y∈S, r  i=1 fi(vi;y)≥α, ν(y)≤1, which is exactly statement (9), and thus the result follows. Theorem 3 Problem (7)has an optimal solution (u,β)such that (u,β)contains at least d affinely independent points of A ∪B. Proof The proof goes parallel to the ones given in Carrizosa and Plastria (2008), Plastria and Carrizosa (2001) for related problems, now using Lemma 2as supporting result. Take an arbitrary solution (u0,β 0), u0= 0,and we will find a solution (u,β)with H(u,β) containing at least daffinely independent points of A∪Band F(u,β) ≤ F(u0,β 0). Define the sets A≥ (u0,β0)={a∈A:u0;a−β0≥0} A≤ (u0,β0)={a∈A:u0;a−β0≤0} B≥ (u0,β0)={b∈B:u0;b−β0≥0} B≤ (u0,β0)={b∈B:u0;b−β0≤0}. By construction, since the sets A,Bare assumed not to be linearly separable, one has that If A≥ (u0,β0)=∅, then B≥ (u0,β0)=∅ If A≤ (u0,β0)=∅, then B≤ (u0,β0)=∅.(13) 123 82 F. Plastria, E. Carrizosa Moreover, let C(u0,β 0)be the polyhedron in Rd+1defined by the inequalities and equality u;a−β≥0∀a∈A≥ (u0,β0) u;a−β≤0∀a∈A≤ (u0,β0) u;b−β≥0∀b∈B≥ (u0,β0) u;b−β≤0∀b∈B≤ (u0,β0)  a∈A≥ (u0,β0) (u;a−β)− a∈A≤ (u0,β0) (u;a−β) + b∈B≥ (u0,β0) (u;b−β)− b∈B≤ (u0,β0) (u;b−β)=δ0, (14) where δ0is the constant δ0 def = a∈A≥ (u0,β0) (u0;a−β0)− a∈A≤ (u0,β0) (u0;a−β0) + b∈B≥ (u0,β0) (u0;b−β0)− b∈B≤ (u0,β0) (u0;b−β0). By construction, δ0≥0.Moreover, δ0>0,since, otherwise, H(u0,β 0)would contain A∪B,contradicting the assumption that A,Bare not linearly separable. On the other hand, C(u0,β 0)=∅,since (u0,β 0)∈C(u0,β 0). Moreover, the polyhedron C(u0,β 0)is bounded. Indeed, otherwise, it would contain a direction (u,β)= (0,0), which should satisfy u;a−β≥0∀a∈A≥ (u0,β0) u;a−β≤0∀a∈A≤ (u0,β0) u;b−β≥0∀b∈B≥ (u0,β0) u;b−β≤0∀b∈B≤ (u0,β0)  a∈A≥ (u0,β0) (u;a−β)− a∈A≤ (u0,β0) (u;a−β) + b∈B≥ (u0,β0) (u;b−β)− b∈B≤ (u0,β0) (u;b−β)=0, (15) implying all inequalities above are equalities, and then A∪Bwould be contained in a hyperplane, which contradicts our non separability hypothesis. One also has that no (0,β) ∈C(u0,β 0). Indeed, (0,0)∈ C(u0,β 0)because δ0>0,and thus (0,0)does not satisfy the last condition defining C(u0,β 0). Suppose further that, on the contrary, some β= 0 exists such that (0,β)∈C(u0,β 0). If it were β>0,(0,β)could not satisfy the first and third block of constraints in (14), implying A≥(u0,β 0)=B≥(u0,β 0)=∅,whereas for β<0,the second and fourth block of 123 Linear separation by minimizing concave functions of distances 83 inequalities should be void, yielding A≤(u0,β 0)=B≤(u0,β 0)=∅.Both cases are in contradiction with (13), thus we conclude that no βexists with (0,β)∈C(u0,β 0). Let νbe the convex positively homogeneous function in Rd+1defined as ν(u,β)=γ◦(u). We just showed in other words that ν(u,β)>0 for all (u,β)∈C(u0,β 0). Now, consider Problem (7) restricted to the nonempty bounded polyhedron C(u0,β 0). One has that for all (u,β)∈C(u0,β 0) F(u,β) = a∈A≤ (u0,β0) faβ−a;u γ◦(u)+ b∈B≥ (u0,β0) fbb;u−β γ◦(u) = a∈A≤ (u0,β0) faβ−a;u ν(u,β) + b∈B≥ (u0,β0) fbb;u−β ν(u,β) (16) By Lemma 2,Fis quasiconcave on the bounded polyhedron C(u0,β 0), thus there exists some extreme point (u∗,β∗)of C(u0,β 0)such that F(u∗,β∗)≤F(u,β) ∀(u,β)∈C(u0,β 0), and, in particular, F(u∗,β∗)≤F(u0,β 0). Since (u∗,β∗)is a vertex of C(u0,β 0), there must exist a subset of d+1 linearly independent constraints from (14) satisfied with equality at (u∗,β∗). In other words H(u∗,β∗)must contain a subset of affinely independent points from A∪Bwith cardinality at least d. As a consequence of Theorem 3, finding an optimal solution to Problem (7) can be reduced to inspecting a finite set of candidate solutions, since any daffinely independent points univoquely define a hyperplane. This is illustrated in Fig. 1. Setting in (7)fas f(t)=tpfor p=0.1,0.2,...,1,we obtain, by complete enumeration of candidate lines, the depicted optimal separating lines. Each line is optimal for the respective p-values 0.1–0.2, 0.3, 0.4–0.7 and 0.8–1. It may be observed in the example that, the lower the value of p, the lower the number of missclassified points, viz., respectively 10,10,11 and 12, as was to be expected since fconverges to the step function (8)forp↓0. Such a complete enumeration strategy is only feasible for low-dimensional problems. For more general settings, the localization property may be advantageously used in local-search heuristic approaches, as was already done in Plastria and De Bruyne (2010) for the case of linear distance functions. 123 84 F. Plastria, E. Carrizosa Fig. 1 Optimal separating lines for different values of p 3 Application to approximation Theorem 3can also be applied to an approximation problem, in which a set Xis given, and a hyperplane H(u,β)is sought minimizing the sum of concave functions fxof the distances from the data points xto H(u,β), min  x∈X fx(d(x,H(u, β))) s.t. u= 0,β∈R, (17) which can also be written as min  x∈X fx(−u;x+β)+ γ◦(u)+ x∈X fx(u;x−β)+ γ◦(u) s.t. u= 0,β∈R. (18) Indeed, taking A=B=Xin Theorem 3one immediately obtains Corollary 4 Problem (17)has an optimal solution (u,β)such that (u,β)contains at least d affinely independent points of X. 123 Linear separation by minimizing concave functions of distances 85 References Carrizosa E, Plastria F (2008) Optimal expected distance separating halfspace. Math Oper Res 33:662–677 Carrizosa E, Rodríguez-Chía A (1997) Weber problems with alternative transportation systems. Eur J Oper Res 97:87–93 Chen C, Mangasarian OL (1996) Hybrid misclassification minimization. Adv Comput Math 5:127–136 Karam A, Caporossi G, Hansen P (2007) Arbitrary-norm hyperplane separation by variable neighbourhood search. IMA J Manag Math 18:173–189 Mangasarian OL (1994) Misclassification minimization. J Glob Optim 5:309–323 Mangasarian OL (1999) Arbitrary-norm separating plane. Oper Res Lett 24:15–23 Plastria F (2009) Asymmetric distances, semidirected networks and majority in Fermat–Weber problems. Ann Oper Res 167:121–155 Plastria F, Carrizosa E (2001) Gauge-distances and median hyperplanes. J Optim Theory Appl 110:173–182 Plastria F, Carrizosa E (2012) Minmax-distance approximation and separation problems: geometrical properties. Math Program 123:153–177 Plastria FS, De Bruyne S, Carrizosa E (2010) Alternating local search based VNS for linear classification. Ann Oper Res 174:121–134 Stam A (1997) Nontraditional approaches to statistical classification: some perspectives on Lp-norm methods. Ann Oper Res 74:1–36 123