Bertrand Gauthier
email: bertrand.gauthier@esat.kuleuven.be

Johan A K Suykens
email: johan.suykens@esat.kuleuven.be

energy, discrepancy Svm Rkhs

RKHS, energy, discrepancy and SVM

Keywords: supervised learning, classification, SVM, RHKS, energy, discrepancy, energy-SVM, discrepancy-SVM, model-oriented supervised subsample selection

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

Reproducing kernel Hilbert spaces (RKHSs, see for instance [START_REF] Wahba | Spline Models for Observational Data[END_REF][START_REF] Berlinet | Reproducing Kernel Hilbert Spaces in Probability and Statistics[END_REF]) are strongly related with support vector machines (SVMs, see for instance [START_REF] Vapnik | Statistical Learning Theory[END_REF][START_REF] Suykens | Least Squares Support Vector Machines[END_REF][START_REF] Rasmussen | Gaussian Processes for Machine Learning[END_REF][START_REF] Steinwart | Support Vector Machines[END_REF]), and in particular with the so-called 2 -norm (or 2 -regularised) SVMs. To be more precise, consider a set (x i , y i ) N i=1 of labeled data-points (two-class problem), with for all i ∈ {1, • • • , N }, x i ∈ X and y i ∈ {+1, -1}, where X is a general set (binary classification). Let H be a separable RKHS of real-valued functions on X , with reproducing kernel K(•, •). The RKHS formulation of a hard-margin SVM consists in solving the problem, for f ∈ H and b ∈ R,

minimise f,b 1 2 f 2 H subject to y k f (x k ) + b 1, for all k ∈ {1, • • • , N }, (1.1)
and soft-margin extensions are achieved by adding a slack-variable penalisation term to the cost (loss function). For the sake of simplicity, in this work, we only consider 1 and 2 -loss SVMs (L1-SVM and L2-SVM, see Remarks B.1 and B.2). Notice that one may eventually consider that b (the b-term, or offset) is known (for the sake of simplicity, we shall in this case assume that b = 0). We recall that problem (1.1) may have no solution.

When dealing with RKHS of measurable functions, one can naturally define the notion of energy and discrepancy relative to a given RKHS (Section 3), as considered in [START_REF] Damelin | A walk through energy, discrepancy, numerical integration and group invariant measures on measurable subsets of Euclidean space[END_REF] (the notion of discrepancy appears, with different meanings, in many other areas of mathematics and statistics, see for instance [START_REF] Niederreiter | Random Number Generation and Quasi-Monte Carlo Methods[END_REF][START_REF] Daubechies | An iterative thresholding algorithm for linear inverse problems with a sparsity constraint[END_REF]). Notice that in our framework, the measurability condition induces no restriction at all as far as one deals with finite data sets: the energy and discrepancy-SVM models are in this case defined for any reproducing kernel.

We investigate the connections that exist between SVM dual solutions and minimal energy or discrepancy configurations on data-points. We in particular show that 2 -norm SVM models have a natural interpretation in the framework of energy minimisation on simplex of probability measures supported by the data. We introduce the notion of energy-SVM (or E-SVM, in short) and show that this class of models consists in an equivalent formulation for classical RKHS-based SVMs. The RKHS formulation of a hard-margin energy-SVM is given by so that the SVM classifier and the energy-SVM classifier are equal. We refer to γ * as the optimal threshold ; in particular, for energy-SVMs, γ * is the energy of the underlying minimal energy configuration (and γ * = h * 2 H 0). The equivalence between the SVM and energy-SVM frameworks in the 1 or 2 -loss cases is tackled in Section 5. Notice that the energy-SVM setting can be viewed as a supervised version of the one-class SVM formulation proposed in [START_REF] Schölkopf | Estimating the support of a high-dimensional distribution[END_REF] and is strongly related with the framework of ν-SVMs introduced in [START_REF] Schölkopf | New support vector algorithms[END_REF].

minimise h,γ,b 1 2 h 2 H -γ subject to y k h(x k ) + b γ, for all k ∈ {1, • • • , N }, (1.2
By replacing the energy minimisation by a discrepancy minimisation, one can introduce the notion of discrepancy-SVMs (or D-SVMs, in short), see Section 6. A hard-margin discrepancy-SVM has the following primal RKHS formulation:

minimise h,γ,b 1 2 h 2 H + (h|f θ ) H -γ subject to y k h(x k ) + b γ, for all k ∈ {1, • • • , N }, (1.3)
where the distortion function f θ ∈ H is defined as f θ (x) = N k=1 y k θ k K(x, x k ), with x ∈ X and θ = (θ 1 , • • • , θ N ) T ∈ R N . The vector θ ∈ R N represents the signed-measure supported by the data that defines the discrepancy minimisation problem (Section 6.1). The optimal threshold of a D-SVM is given by γ * = h * 2 H + (h * |f θ ) H . When γ * > 0 (admissible distortion, see Section 6.2), the discrepancy-SVM classifier is classically defined as sign h * (x) + b * , x ∈ X . Notice that contrary to E-SVMs, for D-SVMs with general distortion, γ * can be negative. Soft-margin discrepancy-SVMs with 1 and 2 -loss are also introduced. For θ = 0, the discrepancy-SVM is the energy-SVM, so that E-SVMs appear as particular D-SVMs; but D-SVMs can also be obtained by linear penalisation of the E-SVM dual formulation, as detailed in Section 6.3.

We refer to data-points associated with non-zero components of a dual D-SVM solution as dualsupport-vectors (d-SVs), and we call representer-support-vectors (r-SVs) the data-points appearing in the kernel representation of the D-SVM decision function induced by (1.3) (see Definition 6.1). For E-SVMs, d-SVs and r-SVs are equivalent, but this no longer holds for D-SVMs, due to the presence of the distortion term f θ . The d-SVs of a D-SVM are the support-points of the underlying minimal discrepancy configuration.

Our numerical experiments point out that depending on the type of distortion considered, D-SVM models inherit some interesting poperties. Admissible distortion terms may for instance be used to integrate specific prior information in SVM decision functions, in order to enhance the SVM prediction efficiency or to reduce the computational cost of the SVM classifier. We also illustrate that low-discrepancy configurations, and in particular d-SVs of D-SVMs (independently of the admissibility of the distortion), appear as an interesting tool for supervised model-oriented subsample selection, allowing in particular to achieve SVMs with high sparsity.

As an interesting feature, the energy and discrepancy-SVM dual formulation consists in a simplex restricted quadratic programming (QP) since it amounts to search for a minimal energy or discrepancy configuration on a simplex of probability measures supported by the data (plus additional constraints for models with b-term or 1 -loss). General E-SVM and D-SVM dual problems can be efficiently solved thanks to, for instance, the 2-component exchange strategy described in Appendix C (this strategy can be viewed as an hybrid between the SMO and the vertex-exchange strategies see for instance [START_REF] Keerthi | Convergence of a generalized SMO algorithm for SVM classifier design[END_REF][START_REF] Hush | QP algorithms with guaranteed accuracy and run time for support vector machines[END_REF] and [START_REF] Pronzato | Design of Experiments in Nonlinear Models[END_REF]Chap. 9]). Note that in the framework of sparse updatetype solvers for QPs, closed-analytical expressions of all the quantities required at any iteration of the algorithm are available and extremely cheap to evaluate (e.g., optimal step-length, gradient update). Furthermore, such strategies usually enjoy complexity bounds independent of the problem size, so that the overall computational complexity of the solver growth linearly with the size of the data set (in practice, the main limiting factor lies in the sparsity of the dual solution, and not in the size of the data set itself), making the framework of energy and discrepancy-SVMs a good candidate to scale up to very large data sets.

The paper is organised as followed: Section 2 is devoted to some additional recalls about RKHSs and SVMs, and Section 3 focuses on the notions of energy and discrepancy relative to a given RKHS. In Section 4, we study the connection between dual SVM formulation and energy minimisation, and we introduce the notion of energy-SVM; 1 -loss and 2 -loss energy-SVMs (L1-E-SVM and L2-E-SVM) are described in Section 5. Discrepancy-SVMs are studied in Section 6. Some numerical experiments are carried-out in Section 7, and Section 8 concludes.

RKHS, SVM and notations

Let {φ j |j ∈ I} be an orthonormal basis of the RKHS H (with I a general at most countable index set). For f ∈ H, f = j∈I w j φ j , with w j ∈ R (and w j = (f |φ j ) H ), we use the matrix notation f = w T φ = φ T w, so that in particular f 2 H = w T w. To be more precise, the column vector w ∈ R I stands for the coefficient of f in the orthonormal basis {φ j |j ∈ I} of H, and w T is a row vector. Also, for x ∈ X , we use the notation f (x) = w T φ(x) = φ T (x)w. The application x → φ(x) ∈ R I , x ∈ X , is referred to as a feature map associated with the kernel K(•, •).

In this framework, (1.1) can be written under the parametric form minimise w,b where the notation α 0 stands for α i 0, for all i ∈ {1, • • • , N }.

P(w) = 1 2 w T w subject to y k w T φ(x k ) + b 1, for all k ∈ {1, • • • , N }, ( 2
When they exist, we denote by w * and b * the solution of the primal (2.1), and by α * the solution of the dual (2.2), we recall that w * = Φ T Yα * , and

y k b * = 1 -[Ωα * ] k for all k ∈ {1, • • • , N } such that α * k > 0, where [Ωα] k is the k-th component of the vector Ωα. We have φ T (x k )w * + b * 1, for all k ∈ {1, • • • , N }, with equality for all k such that α * k > 0. In addition of the kernel K(•, •), in view of (2.2), the SVM model naturally involves a kernel Ω(•, •) on Z × Z , with Z = X × {+1, -1}. The labeled kernel Ω(•, •) is given by, for z = (x, y) and z = (x , y ) ∈ Z , Ω(z, z ) = K(x, x )I(y, y ), with I(y, y ) = yy = +1 if y = y , -1 if y = y .
By definition, the kernel I(•, •) is symmetric and positive on the label-space {+1, -1}. The kernel Ω(•, •) is therefore symmetric and positive (positivity follows from the Schur product theorem), and the N × N labeled kernel matrix Ω associated with the SVM data set {z k = (x k , y k )} N k=1 has i, j entry Ω(z i , z j ).

Weighted 1 -loss and generalised

RKHS, energy and discrepancy

Let X be a measurable set and consider a symmetric and positive kernel K : X × X → R. We assume that the kernel K(•, •) is measurable; that is more precisely that K(•, •) is measurable on X × X endowed with the product σ-algebra, and that the diagonal of K(•, •) is a measurable function on X . We denote by H the RKHS associated with the kernel K(•, •) and we assume that any h ∈ H is a measurable function from X onto R. We also assume that H is separable.

Let M be the set of all signed measures on X . We introduce the linear space M(K) ⊂ M, defined as

M(K) = ν ∈ M X K(x, x)d|ν|(x) < +∞ ,
where |ν| stands for the total variation measure for the signed measure ν (see, e.g., [START_REF] Dudley | Real analysis and probability[END_REF]).

From the reproducing property of the kernel K(•, •) and the Cauchy-Schwarz inequality, we have, for all h ∈ H and ν ∈ M(K),

X h(x)dν(x) X |h(x)|d|ν|(x) h H X K(x, x)d|ν|(x).
The linear functional I ν on H, defined as

I ν [h] = X h(x)dν(x),
∀x ∈ X , f ν (x) = X K(x, t)dν(t). (3.1)
For all ν ∈ M(K), we introduce (see [START_REF] Damelin | A walk through energy, discrepancy, numerical integration and group invariant measures on measurable subsets of Euclidean space[END_REF])

E K (ν) def = f ν 2 H = X ×X K(x, t)dν(x)dν(t), (3.2)
and by definition, E K (ν) 0. We refer to E K (ν) as the energy of the measure ν with respect to the kernel K(•, •). If µ is another measure in M(K), we also define

ν, µ K def = f ν f µ H = X ×X K(x, t)dν(x)dµ(t). (3.3)
By construction, •, • K is a symmetric and positive bilinear form on M(K). We have in particular

E K (ν) = f ν 2 H = ν, ν K def = ν 2 K .
Finally, the squared discrepancy between ν and µ is defined as

D 2 K (ν, µ) def = ν -µ 2 K = E K (ν -µ) = E K (ν) + E K (µ) -2 ν, µ K . (3.4)
Remark 3.1. The interest of the notion of discrepancy in the context of quadrature approximation of functions in RKHS is tackled in [START_REF] Damelin | A walk through energy, discrepancy, numerical integration and group invariant measures on measurable subsets of Euclidean space[END_REF]. References to the notion of energy relative to RKHS in the context of potential theory can for instance be found in [START_REF] Schwartz | Sous-espaces hilbertiens d'espaces vectoriels topologiques et noyaux associés[END_REF]Sec. 11].

Energy and SVM

We now illustrate the close relation that exists between energy and the SVM dual formulation for two-class learning problems. Notice that we can choose either to encode the label-information by using signed measures and the initial kernel K(•, •), or by using the labeled kernel Ω(•, •) and positive measures. In what follows, we consider this second option, but remark that the two approaches are equivalent and complementary.

Energy minimisation

Let z i = (x i , y i ) N i=1 be a set of labeled data-points, x i ∈ X and y i ∈ {+1, -1}, and let ν be a discrete signed measure supported by the data-points, that is ν =

N i=1 υ i δ z i , with υ = (υ 1 , • • • , υ N ) T ∈ R N ,
and where δ z i stands for the Dirac measure centered at z i = (x i , y i ). The energy of the measure ν with respect to the kernel Ω(•, •) is given by (using matrix-notation)

E(υ) def = E Ω (ν) = υ T Ωυ.
We denote by P the simplex of all probability measures supported by the data. Minimising E Ω (•) on the simplex P (see Remark 4.2), while potentially adding the constraint y T υ = 0 accounting for the presence of an unknown b-term, leads to the quadratic problem (the scalar 1/2 is added for correspondance with the SVM formulation):

minimise υ 1 2 E(υ) = 1
2 υ T Ωυ, subject to υ 0 and 1 T υ = 1 (and y T υ = 0).

(4.1)

It is important to remark that the minimisation problem (4.1) always admits a solution since it consists in minimising a convex function on a convex compact subset of R N .

Problems (4.1) and (2.2) are very close in their mathematical formulation; the following Theorem 4.1 shows that these two problems are in fact strongly related. A proof is given in Appendix A.

Theorem 4.1. Let υ * be a solution of (4.1); the problem (2.2) admits a solution α * = 0 if and only if E(υ * ) = (υ * ) T Ωυ * > 0. In this case, we have

α * = υ * E(υ * ) and υ * = α * 1 T α * and 1 T α * = E(α * ).
More generally, notice that Theorem 4.1 holds if we replace, in (2.2), (4.1) and Theorem 4.1, the vector 1 by any vector r = (r 1 , • • • , r N ) T ∈ R N such that r i > 0 (what we denote by r > 0); see also Remark 4.2.

Energy-SVM model

The following "proposition-definition" describes the energy-SVM model, which consists in a SVM admitting the energy minimisation (4.1) as Lagrange dual formulation. Proposition 4.1 (energy-SVM). We call parametric primal form of a energy-SVM model the problem (see (1.2) for the RKHS primal formulation)

minimise ω,γ,b P (ω, γ) = 1 2 ω T ω -γ subject to Y[Φω + b1] γ1 (4.2) with ω ∈ R I , ξ ∈ R N , γ ∈ R
* = γ * -[Ωυ * ] k , for all k ∈ {1, • • • , N } such that υ * k > 0. The energy-SVM decision function φ T ω * + b * verifies y k (φ T (x k )ω * + b * )
γ * , for all k ∈ {1, • • • , N }, with equality for all k such that υ * k > 0. If γ * > 0, we have sign φ T (x k )ω * + b * = y k for all k, defining a hard-margin classifier.

The energy-SVM primal formulation (1.2)-(4.2) differs from the SVM primal formulation (1.1)-(2.1) by the presence of term γ which represents the condition 1 T υ = 1 through Lagrange duality, i.e., the restriction of the energy minimisation problem to the simplex of probability measure supported by the data (see Remark 4.2).

Following Section 2, the parametric formulation (4.2) can be derived from the RKHS formulation (1.2) by considering h = ω T φ, and reciprocally. Notice that in view of Section 3 and using more particularly the notation introduced in (3.1), we have

∀x ∈ X , h * (x) + b * = φ T (x)ω * + b * = N k=1 y k υ * k K(x, x k ) + b * = X K(x, t)dν * s (t) + b * = f ν * s (x) + b * , (4.4)
where ν * s = N k=1 y k υ * k δ x k is the optimal signed-measure on X , supported by the data (so, ν * s is a signed-measure on X and ν * is a measure on Z ). with τ ∈ R N , b and γ ∈ R, and where Ω † is a pseudoinverse of Ω. We in particular have Ωυ + by -γ1 = τ 0 (remark that y = Y1). The energy-SVM primal problem (4.2) can be derived from (4.5) thanks to the change of variables ω = Φ T YΩ † (τ + γ1by). Notice that when the matrix Φ T Φ is invertible, the Moore-Penrose pseudoinverse of Ω is given by

Ω † = YΦ(Φ T Φ) -2 Φ T Y.
Remark 4.2 (weighted-threshold). In the energy-minimisation problem (4.1), we have chosen to deal with measures ν (supported by the data) such that υ 0 and 1 T υ = 1. However, we could as well consider the more general condition υ 0 and r T υ = 1, where r = (r 1 , • • • , r N ) T ∈ R N , r > 0, is given (so, in (4.1), r = 1). The underlying primal energy-SVM problem then reads

minimise ω,γ,b P (ω, γ) = 1 2 ω T ω -γ subject to Y[Φω + b1] γr.
The weighted-threshold r allows to enforce data-points dependent constraints on the decision function. The choice r = 1 can in a sense be viewed as a non-informative choice. Similar remarks hold for all the SVM models discussed in this paper, in the sense that all the SVMs discussed in this article can be defined for a general weighted-threshold r.

L1 and L2 energy-SVM

To continue the analogy between SVM and energy-SVM, we now describe soft-margin extensions of the energy-SVM model through the use of 1 or 2 -type slack variables penalisation in the primal formulation, which corresponds to the framework of L1-SVM and L2-SVM. For the sake of generality, we consider a weighted 1 -loss penalisation in the L1-SVM case, and a generalised 2 -loss penalisation for L2-SVMs.

Kernel matrix regularisation and L2-E-SVM

Section 4 indicates that non-separable SVM problems are associated with zero-valued minimal energy states. This observation therefore suggests a natural way to deal with non-separability in the framework of energy-SVM models, by simply adding a symmetric positive definite matrix to the kernel matrix Ω. Indeed, let Σ be a positive definite symmetric matrix, for all υ ∈ R N , υ = 0, we then have υ T (Ω + Σ)υ > 0.

Proposition 5.1 (L2-energy-SVM). We call (parametric) primal form of a L2-energy-SVM model the problem minimise ω,γ,b,ξ

P (ω, γ, ξ) = 1 2 ω T ω -γ + 1 2 ξ T Σ -1 ξ subject to Y[Φω + b1] γ1 -ξ.
(5.1)

with ω ∈ R I , ξ ∈ R N , γ ∈ R and b ∈ R (b = b * = 0 in the no-b-term case)
, and where Σ ∈ R N ×N is a fixed symmetric positive definite matrix. The dual form of the L2-energy-SVM model is given by minimise

υ D(υ) = 1 2 υ T (Ω + Σ)υ subject to υ 0 and 1 T υ = 1 (and y T α = 0), (5.2)
with υ ∈ R N . If υ * is a solution of (5.
2), then the primal solution is

ω * = Φ T Yυ * and ξ * = Συ * and γ * = (υ * ) T (Ω + Σ)υ * > 0,
and,

y k b * = γ * -[(Ω + Σ)υ * ] k , for any k ∈ {1, • • • , N } such that υ * k > 0. The L2-energy-SVM decision function φ T ω * + b * verifies y k (φ T (x k )ω * + b * ) γ * -ξ * k , for all k ∈ {1, • • • , N }, with equality for all k such that υ * k > 0. The L2-energy (soft-margin) classifier is given by sign φ T (x)ω * + b * , x ∈ X .
The L2-SVM model equivalent to the L2-energy-SVM given in Proposition 5.1 is described in Remark B.2 (these two SVMs lead to exactly the same classifier).

Remark 5.1. The Lagrange dual problem associated with (5.2) is given by

minimise τ ,γ 1 2 (τ + γ1 -by) T (Ω + Σ) -1 (τ + γ1 -by) -γ, subject to τ 0, (5.3)
with τ ∈ R N and b ∈ R and γ ∈ R. We in particular have (Ω + Σ)υ + by -γ1 = τ 0. The L2-energy-SVM primal problem (5.1) can be derived from (5.3) thanks to the following change of variables:

ω C -1 ξ = Φ T Y C T (Ω + Σ) -1 (τ + γ1 -by),
where Σ = CC T is the Cholesky decomposition of Σ.

L1-energy-SVM

Following the classical SVM framework, one can also define, in the context of energy-SVM, a softmargin classifier thanks to a 1 -type slack variables penalisation.

Proposition 5.2 (L1-energy-SVM). We call (parametric) primal form of a L1-energy-SVM model the problem minimise ω,γ,b,ξ

P (ω, γ, ξ) = 1 2 ω T ω -γ + c T ξ subject to Y[Φω + b1] γ1 -ξ and ξ 0, (5.4
)

with ω ∈ R I , ξ ∈ R N , γ ∈ R and b ∈ R (b = b * = 0 in the no-bias case), and where c = (c 1 , • • • , c N ) T ∈ R N is a fixed given vector such that c > 0 and 1 T c 1.
The dual form of the L1-energy-SVM model is given by

minimise υ D(υ) = 1 2 υ T Ωυ subject to 0 υ c and 1 T υ = 1 (and y T υ = 0), (5.5)
with υ ∈ R N . If υ * is a solution of (5.5), then the primal solution is

ω * = Φ T Yυ * , and γ * -y k b * = [Ωυ * ] k , for all k ∈ {1, • • • , N } such that 0 < υ * k < c k ; so that in particular, for k + and k -∈ {1, • • • , N }, such that 0 < υ *
k± < c k± , and y k + = +1 and y k -= -1, we have

γ * = ([Ωυ * ] k -+ [Ωυ * ] k + )/2 and b * = ([Ωυ * ] k --[Ωυ * ] k + )/2.
In addition, (υ * ) T ξ * = c T ξ * , and

ξ * k = 0 for all k such that υ * k < c k . For k such that υ * k = c k , the non-trivial components of the vector ξ * are given by -ξ * k = [Ωυ * ] k -γ * + y k b * , and in particular γ * = (υ * ) T Ωυ * + (υ * ) T ξ * . The L1-energy-SVM decision function φ T ω * +b * verifies y k (φ T (x k )ω * +b * ) γ * -ξ * k , for all k ∈ {1, • • • , N }, with equality for k such that υ * k > 0. The (soft-margin) classifier sign φ T (x)ω * + b * , x ∈ X , is well-defined if and only γ * > 0.
The underlying L1-SVM model is described in Remark B.1.

Remark 5.2. The dual problem associated with (5.5) is given by

minimise τ ,γ 1 2 (τ -ξ + γ1 -by) T Ω † (τ -ξ + γ1 -by) -γ + c T ξ, subject to τ 0 and ξ 0, (5.6
) and where Ω † is a pseudoinverse of Ω. We in particular have Ωυ + by -γ1 + ξ = τ 0. The L1-energy-SVM primal problem (5.4) can be derived from (5.3) thanks to the change of variables ω = Φ T YΩ † (τξ + γ1by).

with τ ∈ R N , ξ ∈ R N , b ∈ R and γ ∈ R,

Discrepancy and SVM

In view of Section 3, energy minimisation problems can be viewed as particular discrepancy minimisation problems (i.e., µ = 0 for energy minimisation). Following Section 4, it therefore appears natural to define SVM models whose dual formulation consists in discrepancy minimisation problem.

Discrepancy-SVM

Let θ = (θ 1 , • • • , θ N ) T ∈ R N
and consider the signed measure µ = N i=1 θ i δ z i supported by the data points, with z i = (x i , y i ) ∈ X × {+1, -1}. Using matrix notation, the squared discrepancy between ν and µ, relative to Ω(•, •), is given by

D 2 Ω (ν, µ) = (υ -θ) T Ω(υ -θ) = υ T Ωυ + θ T Ωθ -2θ T Ωυ.
Proposition 6.1 (discrepancy-SVM). We call parametric primal form of a discrepancy-SVM model with distortion θ the problem (see (1.3) for the primal RKHS formulation)

minimise ω,γ,b P (ω, γ) = 1 2 ω T ω + ω T Φ T Yθ -γ subject to Y[Φω + b1] γ1, (6.1
)

with ω ∈ R I , γ ∈ R and b ∈ R (b = b * = 0 in the no-b-term case)
, and where θ ∈ R N is given. The dual form of the discrepancy-SVM model is given by

minimise υ D(υ) = 1 2 (υ -θ) T Ω(υ -θ) subject to υ 0 and 1 T υ = 1 (and y T υ = 0), (6.2)
with υ ∈ R N . If υ * is a solution of (6.2), then the primal solution is

ω * = Φ T Y(υ * -θ) and γ * = (υ * ) T Ω(υ * -θ),
and,

y k b * = γ * -[Ω(υ * -θ)] k , for any k ∈ {1, • • • , N } such that υ * k > 0. The D-SVM decision function φ T ω * +b * verifies y k (φ T (x k )ω * +b * ) γ * , for all k ∈ {1, • • • , N }, with equality for all k such that υ * k > 0. In particular, if γ * > 0, we have sign φ T (x k )ω * + b * = y k , for all k ∈ {1, • • • , N }, defining a hard-margin classifier.
Since the term θ T Ωθ is constant (i.e., the measure µ is fixed), one may replace the primal-dual cost functions P and D in (6.1)-(6.2) by

P (ω, γ) = 1 2 (ω + Φ T Yθ) T (ω + Φ T Yθ) -γ and D(υ) = 1 2 υ T Ωυ -θ T Ωυ (6.3)
respectively (the constraints remaining unchanged); obviously, the D-SVM solutions are not affected by this change. We shall in particular consider this altenative formulation (6.3) in Sections 6.4 since it allows to simplify the formulation of L2-D-SVMs (see also Section 6.3).

In comparison with (1.3), the RKHS primal formulation for the D-SVM defines through (6.3) is given by minimise

h,γ,b 1 2 h + f θ 2 H -γ subject to y k h(x k ) + b γ, for all k ∈ {1, • • • , N }. (6.4)
Using the change of variable h = h + f θ , problem (6.4) can be rewritten as

minimise h,γ,b 1 2 h 2 H -γ subject to y k h(x k ) + b -f θ (x k ) γ, for all k ∈ {1, • • • , N }, (6.5)
so that the distortion then appears in the constraints of the D-SVM primal formulation (instead of appearing in the cost). Notice that we have y k f θ (x k ) = [Ωθ] k , and that following (4.4), we can introduce the measure µ s on X , defined as µ s = N k=1 y k θ k δ x k , so that f θ = f µs ∈ H. The D-SVM decision function can be written as, for x ∈ X ,

h * (x) + b * = N k=1 y k [υ * θ -θ] k K(x, x k ) + b * , (6.6)
and following (6.5),

h * (x) + b * = h * (x) + b * -f θ (x) = N k=1 y k [υ * θ ] k K(x, x k ) + b * -f θ (x)
, where, as a remainder, h * and h * are solution of (1.3)-(6.4) and (6.5) respectively, and h * = h * + f θ . Using RKHS notation, the optimal threshold γ * reads:

γ * = h * 2 H + (h * |f θ ) H = h * 2 H -( h * |f θ ) H .
Remark 6.1. The dual problem associated with (6.2) is given by

minimise τ ,γ 1
2 (τ + Ωθ + γ1 -by) T Ω † (τ + Ωθ + γ1 -by) -γ -1 2 θ T Ωθ, subject to τ 0, (6.7)
with τ ∈ R N , γ ∈ R, and where Ω † is a pseudoinverse of Ω. We in particular have Ω(υθ) + by -γ1 = τ 0. The discrepancy-SVM primal problem (6.1) can be derived from (6.7) thanks to the change of variables ω + Φ T Yθ = Φ T YΩ † (τ + Ωθ + γ1by).

Some properties of discrepancy-SVMs

In view of (6.6), we remark that the notion of support-vectors for a D-SVM differs from the classical interpretation of support-vectors in E-SVMs. Definition 6.1. We call dual-support-vector (d-SV) of a discrepancy-SVM any data-point x k such that [υ * ] k > 0, and we call representer-support-vector (r-SV) any data-point such that [υ *θ] k = 0.

Dual-SVs correspond to strictly positive components of the D-SVM dual solution υ * , and representer-SVs consist in data-points that appear, through the kernel K(•, •), in the dual representation (6.6) of the D-SVM decision function. For E-SVMs (i.e., θ = 0), d-SVs and r-SVs coincide, but this is no longer the case for general D-SVMs (i.e., θ = 0). The d-SVs of a D-SVM are support-points of the underlying minimal discrepancy configuration. Notice in particular that if θ satisfies the constraints appearing in (6.2), then υ * = θ and γ * = 0 (such cases have therefore no practical interest). The choice of the distortion θ offers a way to act on the distribution of the d-SVs. Depending on the considered distortion, the d-SVs distribution may inherit of some interesting properties, as illustrated in Section 7 and further discuss in Section 8.

In the RKHS primal formulation of D-SVMs, depending on the considered (equivalent) formulation (1.3)-(6.4) or (6.5), the distortion f θ appears in the cost or in the constraints respectively. In view of formulation (1.3)-(6.4) (i.e., f θ in the cost), we remark that the term (h * |-f θ ) H has to be as large as possible, enforcing the D-SVM decision function h * to contain f -θ = -f θ . This interpretation is even more clear in view of formulation (6.5) (i.e., f θ in the constraints) since the distortion term f -θ is here explicitly included in the D-SVMs decision function. The D-SVM therefore define a decision function that incorporates the distortion term f -θ ; this may for instance be used to integrate certain kind of priors in SVM decision functions (see Sections 7 and 8 for illustration and discussion).

In view of formulation (6.5), the role played by the distortion should not be confused with the weighted-threshold described in Remark 4.2. These two effects are distinct and complementary, and one may consider D-SVMs that combine both distortion θ and general weighted-threshold r.

These observations of course raise questions relative to the choice of suitable distortions. In particular, the D-SVM decision function (6.6) defines a hard-margin classifier (i.e., sign(h * (x k ) + b * ) = y k for all k) if and only if γ * > 0 (we recall that for a D-SVM with general distortion θ, γ * can be negative). We denote by υ * θ the dual solutions of the D-SVM with distortion θ, and by γ * θ the associated optimal threshold (the subscript explicitly indicates de considered distortion); in particular υ * 0 is the E-SVM dual solution (i.e., θ = 0), with minimal energy γ * 0 . We can therefore naturally define the subset O + = θ γ * θ > 0 of all admissible distortions, i.e., distortions leading to a strictly positive optimal threshold. Lemma 6.1 in particular shows that when γ * 0 is strictly positive, then it always exists θ = 0 such that γ * θ > 0.

Lemma 6.1. Consider the D-SVM model of Proposition 6.1, and let

C = max k K(x k , x k ).
If γ * 0 > 0 (i.e., the underlying E-SVM defined a classifier), then for any η ∈ R N , we have

γ * λη > 0 for all λ ∈ R such that |λ| < √ CE(η) 1/2 /γ * e .
So, if E(η) > 0, then there always exists λ = 0 such that γ * λη > 0 (i.e., λη ∈ O + ). Assume that η is such that the function f η classifies the data (i.e., y k f η (x k ) > 0 for all k), then for all λ 0, we have γ * λη > 0.

When a distortions of the form θ = λη is considered, with η ∈ R N and λ ∈ R, we shall refer to η as the distortion direction.

Linear penalisation of the energy

Let d = (d 1 , • • • , d N ) T ∈ R N and consider the problem minimise υ D(υ) = 1 2 υ T Ωυ -d T υ subject to υ 0 and 1 T υ = 1 (and y T υ = 0), (6.8)
with υ ∈ R N (this problem always admits a solution). We immediately remark that a D-SVM with distortion θ correspond to the case d = Ωθ (i.e., d belongs to the range of Ω). Following (6.3) and (6.5), we introduce:

minimise ω,γ,b P (ω, γ) = 1 2 ω T ω -γ subject to Y[Φω + b1] -d γ1, (6.9)
with

ω ∈ R I , γ ∈ R and b ∈ R (b = b * = 0 in the no-b-term case).
Lemma 6.2. Problem (6.8) is the dual of problem (6.9), if υ * is a solution of (6.8), then

ω * = Φ T Yυ * and γ * = (υ * ) T Ωυ * -d T υ * ,
and

y k b * = γ * -[Ωυ * -d] k , for any k ∈ {1, • • • , N } such that υ * k > 0.
Notice that following Section 5 (and Section 6.4), one can also define 1 or 2 -loss extensions of the primal-dual problems (6.9)- (6.8).

When d = Ωθ, with θ ∈ R N , the inequality constraints in (6.9) can be rewritten as

Y Φ ω -Φ T Yθ + b1] γ1,
which corresponds to the parametric form of the constraints in (6.5), with h = φ T ω. Section 6.3 therefore suggests that it may be possible to extend the framework of D-SVM by considering general linear penalisation of the energy. However, notice that when Ω is full rank, the range of Ω is the whole space R N , so that considering d = Ωθ does not induce any restriction. In addition, for general penalisation d, defining a decision function of the form (6.6) from the primal-dual formulation (6.9)-(6.8) requires special treatment since the out-of-sample extension of the model is this case not canonically defined.

L1 and L2-discrepancy-SVM

P (ω, γ, ξ) = 1 2 (ω + Φ T Yθ) T (ω + Φ T Yθ) -γ + c T ξ subject to Y[Φω + b1] γ1 -ξ and ξ 0, (6.10
) with υ ∈ R N . If υ * is a solution of (6.11), then the primal solution is

with ω ∈ R I , ξ ∈ R N , γ ∈ R
ω * = Φ T Y(υ * -θ),
and, we have

γ * -y k b * = [Ω(υ * -θ)] k , for any k ∈ {1, • • • , N } such that 0 < υ * k < c k , so that in particular, for k + and k -∈ {1, • • • , N }, such that 0 < υ *
k± < c k± , and y k + = +1 and y k -= -1,

γ * = ([Ω(υ * -θ)] k -+ [Ω(υ * -θ)] k + )/2 and b * = ([Ω(υ * -θ)] k --[Ω(υ * -θ)] k + )/2.
In addition, (υ * ) T ξ * = c T ξ * , and ξ * k = 0 for all k such that υ * k < c k . For k such that υ * k = c k , the non-trivial components of the vector ξ * are given by -ξ

* k = [Ω(υ * -θ)] k -γ * + y k b * , and in particular γ * = (υ * ) T Ω(υ * -θ) + (υ * ) T ξ * . The L1-discrepancy-SVM decision function φ T ω * + b * verifies y k (φ T (x k )ω * + b * ) γ * -ξ * k , for all k ∈ {1, • • • , N }, with equality for all k such that υ * k > 0.
The (soft-margin) classifier sign φ T (x)ω * + b * , x ∈ X , is well-defined if and only γ * > 0. Proposition 6.3 (L2-discrepancy-SVM). We call (parametric) primal form of a L2-discrepancy-SVM model the problem minimise ω,γ,b,ξ

P (ω, γ, ξ) = 1 2 (ω + Φ T Yθ) T (ω + Φ T Yθ) -γ + 1 2 ξ T Σ -1 ξ subject to Y[Φω + b1] γ1 -ξ, (6.12
) with υ ∈ R N . If υ * is a solution of (6.13), then the primal solution is

with ω ∈ R I , ξ ∈ R N , γ ∈ R
ω * = Φ T Y(υ * -θ) and γ * = (υ * ) T (Ω + Σ)υ * -θ T Ωυ * , and ξ * = Συ * ,
and,

y k b * = γ * -[(Ω + Σ)υ * -Ωθ] k , for any k ∈ {1, • • • , N } such that υ * k > 0. The L2-discrepancy-SVM decision function x → φ T ω * +b * verifies y k (φ T (x k )ω * +b * ) γ * -ξ * k , for all k ∈ {1, • • • , N }, with equality for all k such that υ * k > 0.
The (soft-margin) classifier sign φ T (x)ω * + b * , x ∈ X , is well-defined if and only γ * > 0.

Numerical experiments

This section aims at illustrating some properties of discrepancy-SVM models. All the D-SVMs are solved in the dual thanks to the 2-component exchange strategy described in Appendix C (in particular, the considered D-SVM dual formulations corresponds to the ones discused in this appendix). Notice that depending on the data set size and the computational power at disposal, the labeled kernel matrix may be too large to fit in the computer RAM; in this case, we simply compute and treat on the fly the required entries of the matrix. The accuracy of the optimisation is indicated thanks to a bounding of the type D( υ) -D(υ * )

, where υ is the approximate dual solution and is the duality gap. With a slight abuse of vocabulary, we refer to (and denote) the approximate solution υ as the true dual solution υ * . For numerical efficiency, the FW solver is always initialised by considering a as sparse as possible vector υ (i.e., the initial υ has only one non-null component in the no-b-term case, and two for models with b-term). For illustration purpose, the dual problems are here solved with a relatively high accuracy; however reaching such high accuracy is in practice generally not necessary since the computations then become more and more demanding and have, after a certain treshold, a very small impact on the quality of the SVM predictions. For simplicity, we only consider hard-margin and 2 -loss D-SVMs.

Double-spiral

We consider an isotropic Gaussian kernel K(x, y) = exp(-xy 2 / 2 ), with x and y ∈ [-1, 1] 2 , where • stands for the Euclidian norm of R 2 , and > 0 is the bandwidth parameter. The data consist of a 40 × 40 square grids on [-1, 1] 2 , the N grid = 1 600 grids point being classified in two classes according to a double-spiral shape, as illustrated in Figure 3. The SVM models are trained with N = 900 data-points selected randomly among the grid points, and the model is tested on the N test = N grid -N = 700 remaining points (we use the same training and test subsamples for all the experiments). The considered D-SVMs are "hard-margin" (i.e., model of Proposition (6.1)) and without b-term. The main objective of this example is to illustrate how the dual-SVs distribution vary as function of the considered distortion θ.

In order to evaluate the influence of the bandwidth parameter , Figure 1 shows the minimal energy γ * = E(υ * ), the number n υ * of strictly positive components of υ * and the number of misclassified test-points for various values of ; for illustration purpose, we also represent the values of 1 T Ω1/N 2 . As expected, for small , the model has no generalisation ability, and in particular, all points are support-vectors. The minimal energy γ * reaches its maximun for ≈ 0.065, and we can observe that for < 0.065, the bandwidth appears to be clearly underestimated. The results for large bandwidth, i.e., 0.3 are relatively interesting in terms of prediction and sparsity of the dual solution; but this behaviour is mainly induced by the fact that the considered model is of hardmargin type (in particular, the solutions are more and more costly to evaluated as increases). To be as representative as possible and for illustration purpose, we mainly use = 0.15 in the following experiments.

Figures 3 and4 show the dual solution (i.e., optimal measure) υ * for a hard-margin D-SVM with distortion θ = λη, with η = 1/N , for various values of λ and for = 0.15. Notice that considering η = 1/N may be viewed as a non-formative choice for the distortion direction η. The computational cost of the underlying optimisations (i.e, number of FW iterations required to reach the precision = 1e-15) is indicated Table 1; as well as the obtained cost function values. As expected, the computational cost of the dual solution decreases with the number of d-SVs (i.e., for a fixed kernel matrix, the more the dual solution is sparse, the faster it can be computed).

The optimal threshold γ * is strictly positive for -26 < λ < 1 approximately (see Figure 5). Notice that λ = 1 plays here a particular role because η = 1/N verifies the constraint appearing in the dual formulation of the considered D-SVM model, so that, we have in this case υ * = η and γ * = 0. Remark also that for = 0.15, the distortion function f η is relatively closed of a classifier since we have sign(f η (x k ) = y k ) for only 35 of the 900 training points, as illustrated in Figure 2. We can observe different behaviours depending on the value of λ (we recall the considered distortion is θ = λ1/N ). For λ 0, the dual solution υ * becomes more and more sparse (i.e., the number n υ * of d-SVs decreases) as λ decreases (notice however that since all the components of the distortion θ are non-null, all data-points are r-SVs), and the optimal treshold remains positive for λ > -26 approximatively. This observation is in accordance with what can be expected in view of Section 6.2 since the distortion function f λη = -λf -η is almost a classifier. For λ < 26, the D-SVM decision function is no more able to overcomes the wrong predictions made by f λη and the optimal threshold γ * becomes negative. Notice that the d-SVs follow a typical support-vectors type distribution, in the sense that they mainly lie at the frontier between the two classes.

For 0 λ 1, the optimal threshold γ * is always strictly positive. The D-SVM classifier have to counteract the distortion f η (that, roughly speaking, plays here "against the classification"), so that the number of d-SVs increases with λ. We observe that υ * tends to η = 1/N as λ tends to 1 (and in particular υ * = η/N for λ = 1, since η is an admissible solution for the D-SVM dual problem).

For λ > 1, the optimal threshold is always negative and the D-SVM classifier is therefore never defined (the model is no not able to produce a classifying decision function that incorporates f -λη ). The number of d-SVs decrease when λ increases. Remarkably, the distribution of the d-SVs for this range of distortions appears to be very different from usual support-vectors type distributions: the d-SVs do not mainly lie at the frontier of the two classes (as it is generally the case for SVMs), but have what can be called a "prototype-vectors like" type of distribution. In the primal D-SVM setting, this effect can be interpreted as follow: the classifier is no more able to evercome the effect of the distortion f θ , but still try to generate the more efficient as possible correction (while remaining in the constraints). The distribution of the d-SVs for this kind of distortions suggests that minimal discrepancy configuration may offer an interesting tool to design model-oriented supervised subsample selection strategies for SVM models.

Figure 5 and Table 2 present the set of all admissible distortions of the form θ = λ1/N (i.e., the set of all λ ∈ R such that γ (λ1/N ) > 0), for three different values of the bandwidth paramater, precisely = 0.1, 0.15 and 0.3. For information purpose, the number n υ * of d-SVs of underlying A Gaussian kernel with = 0.15 is used and optimisations are stopped for =1e-15 (see also Table 1). The number n υ * of dual-SVs, the optimal threshold γ * and, when γ * > 0, the number off misclassified test-points are indicated.

D(υ * ) -1.3e-1 2.15e-3 4.16e-4 -7.3e-4 -1.69e-2 -4.52e-2 -1.41e-1
D-SVMs and of the number of misclassified test-points (when γ * > 0), as function of λ, are also indicated. As increases, the distortion function f η less and less discriminates the two classes (more precisely, as function of , we have sign(f η (x k )) = y k for 885, 865 and 689 data-points respectively, for 900 points in total). As a consequence, in view of Section 6.2, the length of the interval of admissible λ decreases as increases.

Table 2: Number n υ * of dual-SVs and number of misclassified test-points for the D-SVM models with θ = λ1/N , with λ = 0 and for an as small as possible λ such that γ * > 0 (demoted by λ min ). The values of are the ones considered in Figure 5, and =1e-15. To further illustrate the potential interest of minimal discrepancy configurations for subsample selection, Figure 6 shows the predictions obtained by two E-SVM trained on the d-SVs of a D-SVM model with distortions θ = 21/N and θ = 10υ * 0 respectively. Notice that f υ * 0 is a classifier since it consists in the E-SVM decision function for the E-SVM trained on the 900-point training set (υ * 0 is the dual solution, see Figure 3, and the considered E-SVM has no b-term). The efficiency of the obtained classifiers is relatively good. Especially, the SVM obtained from the subsample induced by the distortion θ = 21/N leads, on the full square grid, to a double spiral which is very close to the initial one. The main interest of the resulting SVMs lies in the prototype-vector type distribution of their SVs, which may potentially, depending of the data set considered, offers an interesting alternative to achieve SVMs with high sparsity, as illustrated in Section 7.2.

≈ λ min n υ * (λ min ) n υ * (λ = 0) miscl. (λ min ) miscl. (λ = 0) = 0.

UCI Data Sets

We now illustrate some potential interests of the D-SVMs framework on two UCI data sets, see [START_REF] Lichman | UCI machine learning repository[END_REF], namely:

- Both data sets are preliminary standardised: each of their d attributes is centered and reduced (the empirical mean and variance are brought back to zero and one respectively). In each cases, an For both E-SVMs, the number of SVs, the number of misclassified test-points and the number of misclassified points among the full data set (1 600 points) are also indicated. A Gaussian kernel with = 0.15 is considered, and =1e-15.

isotropic Gaussian kernel is considered (same expression as in Section 7.1). We consider L2-D-SVMs ( 2 -loss) with Σ = sId N , where Id N is the N × N identity matrix and s ∈ R, s 0 (soft-margin parameter).

The data sets are classically splited in training and test subsamples. For the sake of simplicity, the results for only one representative training/test splitting are presented.

MAGIC Gamma Telescope data set

We randomly select N = 13 000 data-points for the SVMs training and keep the remaining N test = 19 020 -N = 6 020 for test. The considered training set consists of 8 450 points in the +1-class and 4 550 in the -1-class. For comparison purpose and to investigate the range of parameters to consider, a L2-E-SVM is first considered; the results are summarised in Table 3. The obtained classifiers have relatively high efficiencies on the test subsample, but require large numbers of SVs. The following experiment aims at illustrating that D-SVMs may potentially be used to incorporate certain kinds of prior knowledges into SVM decision functions.

We consider a random subsample of N 1 = 6 500 points inside of the N = 13 000 full training subset. We then compute a L2-E-SVM on the reduced N 1 -point subsample, leading to a dual solution υ * red ∈ R N 1 . The dual solution υ * red is next extended into a vector υ seq ∈ R N by simply fixing to zero each component of υ seq which does not correspond to a point in the reduced subsample. More precisely, if

I red = {i 1 , • • • , i N 1 } ⊂ {1, • • • , N } is
the index-set of the points belonging to the reduced subsample, then [υ seq ] k = 0 for all k ∈ I red , and [υ seq ] k = [υ * red ] l for all k = i l ∈ I red . We finally compute, on the full training set, L2-D-SVMs with distortion direction η = υ seq (we more precisely consider distortions θ = λη, with λ 0 since we want f υseq to be part of the finial SVM decision function). The final L2-D-SVM contains a b-term, and for illustration purpose, we consider two different distortion directions: one is induced by a L2-E-SVM with b-term, and the other one by a L2-E-SVM without b-term.

For the sake of simplicity, we fix the bandwidth and soft-margin parameters and s to 1.5 and 2 respectively (for this particular experiment, the results for s = 2 are slightly better than the one for s = 1, contrary to what we have observed in Table 3). Our results are listed in Table 4. The initial L2-E-SVMs, (with and without b-term) trained on the N 1 -point subset have a relatively high efficiency on the test subsample and therefore appear as interesting priors for the computation of a model on the full training set. We first observe that the final L2-D-SVM does not seems to be very influenced by the presence or absence of a b-term in the initial L2-E-SVM. In accordance with our previous observations (Section 7.1), the number of d-SVs decreases with λ; as a consequence the L2-D-SVM dual solutions are less and less costly to evaluate as λ decreases (in our experiment, the number of FW iterations is fixed, and we therefore observe a decrease of the optimisation error bound ). The predictions obtained for 0 < λ 2 are very good since they outperform the predictions obtained by directly training, with similar parameters and s, the model on the full subsample (see Table 3). Table 4: Results obtained for a L2-E-SVM with or without b-term, computed on the reduced N 1point training set (Gamma Ray data set) for = 1.5 and s = 2; the number of FW iterations is fixed to 3N 1 (A). Next, for various values of λ, results for a L2-D-SVM with b-term and distortion θ = λυ seq computed on the full training set, with = 1.5 and s = 2. The number of FW iterations is fixed to 3N . For (B), the initial L2-E-SVM (i.e., trained on the N 1 -point reduced subsample) contains a b-term, and is without b-term for (C). Model-oriented supervised subsample selection. This second experiment aims at illustrating that low discrepancy configurations, and in particular d-SVs of D-SVMs with appropriate distortion, may be used to design subsample selection strategies in order to achieve high sparsity in SVMs. We apply the following simple protocol: a L2-D-SVM (without b-term) with distortion θ = λ1/N (λ > 1) is first computed on the full training subset, and the obtained d-SVs are next used as subsample for the computation of a L2-E-SVM. For the D-SVM-based subsample extraction, we consider a bandwidth relatively small in view of Table 3, and a relatively large bandwith for the predicting E-SVM. The results obtained for various sets of parameters are presented in Table 5.

D(υ

               -0.1 2
(C)                -0.1 2
As expected in view of Section 7.1, the number of d-SVs for the extracting L2-D-SVM decreases as λ increases; also, the number of d-SVs increases with the soft-margin parameter s. The obtained SVMs are significantly sparser than the models presented in Tables 3 and4, while keeping relatively high efficiencies on the test subsample. Interestingly, we in particular observe that the final predicting E-SVM apparently does not require soft-margin. The examples also suggest that is possible to modulate the size of the extracted subsample and the level of sparsity of the predicting SVM thanks to the adjustment of the parameters associated with the extracting and predicting SVMs.

For the extracting L2-D-SVM with parameters ( , s, λ) = (1.5, 1, 1.5), the model has 11 155 d-SVs, so that in this case, only 1 845 training points are not kept in the low-discrepancy subsample. For the L2-E-SVM computed on the full training set with the same parameter values (i.e., = 1.5 and s = 1, see Table 3), we observe that ξ * k > γ * for 1 308 points (i.e., the soft-margin slack variables are active, see Proposition 5.1), and remarkably, all these points are excluded by the D-SVM-based subsample selection. Roughly speaking, the discrepancy-based subsample selection automatically excludes most of the points that are source of problems for classification, allowing the classifier to become significantly sparser. For comparison purpose, we first compute a L2-E-SVM (with b-term) on the full training set; the results are summarised in Table 6. The results obtain for the D-SVM-based subsample selection, presented in Table 7, are in accordance with Section 7.2.1: it appears possible to modulate the size of the extracted subsample and the level of sparsity of the predicting SVM through the extracting and predicting SVMs parameters, and the obtained classifiers are significantly sparser than the original ones while keeping relatively high efficiencies on the test subsample.

Concluding discussion

We propose an alternative formulation for classical 2 -regularised SVMs in which the dual problem consists in a energy minimisation problem, introducing the so called energy-SVM classification models. By replacing the energy minimisation by a general discrepancy minimisation problem, one can define the class of discrepancy-SVM models, appearing as a simple natural extension of the energy-SVM framework.

The dual formulation of energy and discrepancy-SVMs consists in a simplex restricted QP. In this context, at each gradient decent iteration, it is in particular possible to find the optimal 2component exchange direction in O(N ) complexity, so that the dual formulation of the energy and discrepancy-SVMs can this way be solved efficiently, see Appendix C.

Our numerical experiments point out two potential methodological applications of discrepancy-SVMs. First, the distortion term of discrepancy-SVMs may be used to incorporate specific prior information in SVM classifiers: when a distortion with a priori good classification ability is available, the D-SVM classifier has only to focus on the correction to be applied to the initial distortion term, and this dichotomy may be used to enhance the SVM prediction efficiency, or to reduce the computational cost of SVM classifiers. Second, for appropriate distortions, considering lowdiscrepancy configurations of data-points, and in particular d-SVs of D-SVMs (which have the interest of being obtained by convex optimisation) appears as an interesting supervised modeloriented subsample selection strategy in order to compute SVMs with high sparsity while reducing the impact of possible outliers. Notice that more generally, our study suggests that energy and discrepancy-based criterion may be used to compare the interest (in terms of classification) of various subsamples of a given data set, as discussed in Remark A.1. Further works are however needed in oder to propose fully operational learning strategies based on the notion of discrepancy-SVMs.

For θ = λη, we obtain γ * λη E(υ * 0 ) - √ C|λ|E(η) 1/2 , with λ ∈ R and η = (η 1 , • • • , η N ) T ∈ R N . Now, assume that η is such that the function f η classifies the data. Since y k f η (x k ) = [Ωη] k , there exists κ > 0 such that Ωη κ1 (one may consider κ = min k [Ωη] k ). For λ < 0, we have γ * λη = E(υ * λη ) -λη T Ωυ * λη -λκ > 0.
Finally, since f η ∈ H classifies the data, from Theorem 4.1, γ 0 = E(υ * 0 ) > 0.

Remark A.1. Consider a subset {(x i k , y i k )} n k=1 of n points among the full N -point data set, with index-set

I sub = {i 1 , • • • , i n } ⊂ {1, • • • , N }.
Such a subsample can be associated with the probability measure ν = 1 n n k=1 y i k δ x i k , where each point receives the same (non-informative) weight 1/n. For a given subsample size n, the energy and discrepancy criterion may therefore be used to compare the potential interest, in terms of classification, of different data subsamples: the subsets with the lowest energy or discrepancy being, in view of our study, potentially the more interesting. Notice that considering the discrepancy criterion requires the specification of the underlying distortion measure µ, and in such a framework, considering the uniform probability on the full data set appears as an interesting and relatively reasonable choice. It may also be possible to consider combinatorial optimisation strategies allowing for the extraction of subsamples with low energy or discrepancy (fixed-size supervised model-oriented subsample selection). -the j-th component can give weight only if it has weight to give, i.e., if υ j > 0, -in the 1 -loss case, the i-th component can receive weight only if υ i < c i -for models with b-term, because of the constraint y T υ = 0, a 2-component exchange must be class-restricted (i.e., only vertices belonging to a same class can exchange weight).

B Weighted L1-SVM, generalised L2-SVM

P(w, ζ) = 1 2 w T w + 1 2 ζ T Σ -1 ζ, subject to Y[Φw + b1] 1 -ζ, (B.3) with w ∈ R I , ζ = (ζ 1 , • • • , ζ N ) T ∈ R N ,
We denote by A υ the set of all admissible 2-exchange directions at υ, that is A υ = κ = e ie j υ i < c i and υ j > 0 (and y i = y j for models with b-term) .

The optimal 2-exchange descent direction at υ is obtained by considering

κ * = e i * -e j * = argmin κ∈Aυ κ T ∇D(υ),
and ρ * = min(ρ, υ j * , c i *υ i * ), where ρ is given by (C.2) (obviously, for δ = κ * ). The following two paragraphs indicate how to easily defined the optimal 2-exchange directions for any feasible υ by introducing the so called sets of receiving and giving components at υ. Notice that the determination of κ * is achieved in O(N ) complexity. Models without b-term: We denote by I υ,G the index-set corresponding to components of υ that can potentially give weight, that is I υ,G = {k|υ k > 0}. We also introduce I υ,R = {k|υ k < c k }, which stands for the index-set defined by the components of υ that can potentially receive weight (in the hard-margin or 2 -loss cases, I υ,R = {1, • • • , N }). In particular, we have

A υ = e i -e j (i, j) ∈ I υ,R × I υ,G .
The optimal 2-exchange direction κ * = e i *e j * is obtained by considering

i * = argmin i∈I υ,R [∇D(υ)] i and j * = argmax j∈I υ,G [∇D(υ)] j .
We refer to the sets I υ,R and I υ,G as the set of receiving and giving components at υ (the same naming is used for models with b-term). Models with b-term: We denote by I + υ,R and I - υ,R the index-sets corresponding to components of υ that can receive weight and belong to the +1 or -1 class respectively, that is I + υ,R = {k|y k = +1 and υ k < c k } and I - υ,R = {k|y k = -1 and υ k < c k }.

We also define the sets I + υ,G and I - υ,G which correspond to components of υ that can potentially give weight and belong to the +1 or -1, that is I + υ,G = {k|y k = +1 and υ k > 0} and I - υ,G = {k|y k = -1 and υ k > 0}.

The set A υ of admissible 2-exchange directions is given by

A υ = A + υ ∪ A - υ = e i -e j (i, j) ∈ (I + υ,R × I + υ,G ) ∪ (I - υ,R × I - υ,G ) .
We can this way obtain the optimal 2-exchange direction for both classes: [∇D(υ)] j .

Finally, the optimal 2-exchange direction κ * is obtained by considering the minimum between (κ * + ) T ∇D(υ) and (κ * -) T ∇D(υ). Algorithm 1 gives an overview of the 2-component exchange strategy for solving the dual formulation of general D-SVMs with constant treshold. Compute the 2-exchange direction κ * ∈ A υ k and step size ρ * optimal for υ k ;

4:

υ k+1 ← υ k + ρ * κ * ; k ← k + 1; 5:
Update ∇D(υ k ) and A υ k ;

6:

Check stopping criterion; 7: end while 8: return υ k ;

A classical stopping criterion consists in pursuing the optimisation while -(κ * ) T ∇D(υ k ) > τ for a given treshold τ > 0 (the convergence of this strategy is discussed below); more simply, the optimisation can be stopped after a certain number of iterations.

C.2 Hard-margin and 2 -loss

In the hard-margin and 2 -loss cases, the feasibility conditions read 0 υ and 1 T υ = 1 (and y T υ = 0 for models with b-term). The 2-component exchange strategy is in this case strongly related with the so-called vertex-exchange strategy (see for instance [START_REF] Pronzato | Design of Experiments in Nonlinear Models[END_REF]Chap. 9]). Models without b-term: The extreme points of the polytope defined by the constraints in (C.1) are all the vectors e i , 1 i N , so that the 2-component exchange strategy is exactly the vertex-exchange strategy.

The receiving-component is a Frank-Wolfe (FW) toward-vertex (such a vertex is not necessarily unique), and the giving-component is a FW away-vertex. The convergence of the 2-component exchange algorithm can this way be easily verified from [START_REF] Guélat | Some comments on Wolfe's "away step[END_REF]Theorem 1] by simply remarking that since υ 0 and 1 T υ = 1, by definition of j * , we have υ T ∇D(υ) e T j * ∇D(υ), so that +e j * -) T ∇D(υ) and (e i * -e j * + ) T ∇D(υ), that is e i *e j * is the optimal 2-exchange direction. Inequality (C.5) corresponds to the FW toward descent direction; inequality (C.6) is related to the vertex-exchange optimal descent direction (involving the update of 4 components of υ); and inequality (C.7) is associated with the optimal 2-exchange direction.

One vertex-exchange iteration consists in considering at the same time the optimal 2-exchange direction for both classes and to apply the same step size in each class (as a trade of, notice that it may be possible to consider simultaneously the optimal 2-exchange direction for both classes and to search for the underlying two optimal step sizes).

In practice, we observe that in terms of number of iterations, the vertex-exchange strategy converges faster than the 2-component exchange strategy; however, gradient update for the vertexexchange involved 4 components of υ; and only two for the 2-component exchange. The 2-component exchange strategy seems to be slightly more interesting in terms of computational time (in particular for problems where the kernel matrix can not be stored).

  ) with h ∈ H, b ∈ R and γ ∈ R. Solution h * , b * and γ * for the problem (1.2) always exists and Theorem 4.1 shows that the SVM problem (1.1) admits a solution (denoted by f * and b * ) if and only if γ * > 0. In this case f * = h * /γ * and b * = b * /γ * ; in particular, since γ * > 0, we have ∀x ∈ X , sign f * (x) + b * = sign h * (x) + b * ,

. 1 )

 1 with w ∈ R I and b ∈ R (b = b * = 0 in the no-b-term case). For the sake of readability, we introduce some few additional notations: we define y = (y 1 , • • • , y N ) T ∈ R N ; we denote by Φ ∈ R N ×I the matrix with i, j entry φ j (x i ) (feature matrix), and by Y = diag(y) the N × N diagonal matrix with i-th diagonal entry y i . The inequality constraints in (2.1) then read Y[Φw + b1] 1, with 1 = (1, • • • , 1) T ∈ R N , and we can introduce the labeled kernel-matrix Ω = YΦΦ T Y.The Lagrange dual of problem (2.1), written for convenience as a minimisation problem, is given by, for α ∈ R N , minimise α D(α) = 1 2 α T Ωα -1 T α, subject to α 0 (and y T α = 0, for model with unknown b-term),(2.2)

  and b ∈ R (b = b * = 0 in the no-b-term case). The dual form of the energy-SVM model is given by minimise υ D(υ) = 1 2 υ T Ωυ subject to υ 0 and 1 T υ = 1 (and y T α = 0), (4.3) with υ ∈ R N . If υ * is a solution of (4.3), then the primal solution is ω * = Φ T Yυ * and γ * = (υ * ) T Ωυ * , and, y k b

Remark 4 . 1 .,γ 1 2

 411 The Lagrange dual problem associated with (4.1) (i.e., the dual of the E-SVM dual formulation) is given by minimise τ (τ + γ1by) T Ω † (τ + γ1by)γ, subject to τ 0, (4.5)

Proposition 6 . 2 (

 62 L1-discrepancy-SVM). We call (parametric) primal form of a L1-discrepancy-SVM model the problem minimise ω,γ,b,ξ

  and b ∈ R (b = b * = 0 in the no-b-term case), and where θ ∈ R N and c= (c 1 , • • • , c N ) T ∈ R N , such that c0 and 1 T c 1, are given. The dual form of the L1-discrepancy-SVM model is given by minimise υ D(υ) = 1 2 υ T Ωυθ T Ωυ subject to 0 υ c and 1 T υ = 1 (and y T υ = 0),(6.11)

  and b ∈ R (b = b * = 0 in the no-b-term case), and where θ ∈ R N and the symmetric positive definite matrix Σ ∈ R N ×N are given. The dual form of the L2-discrepancy-SVM model is given by minimise υ D(υ) = 12 υ T (Ω + Σ)υθ T Ωυ subject to υ 0 and 1 T υ = 1 (and y T υ = 0),(6.13)

Figure 1 :

 1 Figure 1: Values of γ * = E(υ * ), n υ * and number of misclassified test-points for 57 different values of the bandwidth parameter between 0.01 and 0.4. For each value of , a E-SVM model without b-term (and with Gaussian kernel) is considered and optimisations are stopped for =1e-14. For illustration purpose, we also represent the values of 1 T Ω1/N 2 .

  f η for = 0.3 (η = 1/N )

Figure 2 :

 2 Figure 2: Distortion function f η on [-1, 1] 2 , with η = 1/N , for = 0.15 (left) and = 0.3 (right). For = 0.15, sign(f η ) misclassified 35 of the 900 training data-points, and 211 for = 0.3.

2 -- 4 -

 24 n υ * = 58 γ * = 0.003504 misclass: 21 optimal measure υ * for λ =n υ * = 13 γ * = -0.056472 optimal measure υ * for λ = -50 n υ * = 347 γ * = 0.000188 misclass: 36 optimal measure υ * for λ = 0.n υ * = 237 γ * = -0.007338 optimal measure υ * for λ = 2

Figure 3 :

 3 Figure 3: Graphical representation of the measure υ * for the D-SVM (without b-term) with θ = λ1/N (η = 1/N ), for λ = -50, -2, 0 0.4 and 2.A Gaussian kernel with = 0.15 is used and optimisations are stopped for =1e-15 (see also Table1). The number n υ * of dual-SVs, the optimal threshold γ * and, when γ * > 0, the number off misclassified test-points are indicated.

4 -

 4 n υ * = 145 γ * = -0.031187 optimal measure υ * for λ = n υ * = 74 γ * = -0.114887 optimal measure υ * for λ = 10

Figure 4 :

 4 Figure 4: Same as Figure 3, for λ = 4 (left) and λ = 10 (right).

λ

  Number of misclassified test-points

Figure 5 :

 5 Figure 5: For the double-spiral example, evolution of γ * , n υ * and of the number of misclassified test-points (when γ * > 0) as function λ (D-SVM with θ = λ1/N ) for three different values of the bandwidth parameter ( =1e-7 and Gaussian kernel).

  the MAGIC Gamma Telescope data set, which consists of 19 020 data-points in R d , with d = 10, labeled in two classes, with 12 332 points in the +1-class and 6 688 in the -1-class, -the MiniBooNE particle identification data set, consisting of 129 596 data-points in R d with d = 50, labeled in two classes, with 36 488 points in the +1-class and 93 108 in the -1-class (the initial data set actually contains 130 064 points, but we remove the 468 points whose all 50 components are equal to -999).

Figure 6 :

 6 Figure 6: Dual-SVs for a D-SVM trained on the double-spiral 900 points training-set, for distortion θ = 21/N (top-left) and θ = 10υ * 0 (bottom-left, we recall υ * 0 that is the E-SVM dual solution), prediction, on the whole square grid, for a E-SVM trained on the d-SVs of the D-SVM with θ = 21/N (top-right) and θ = 10υ * 0 (bottom-right).For both E-SVMs, the number of SVs, the number of misclassified test-points and the number of misclassified points among the full data set (1 600 points) are also indicated. A Gaussian kernel with = 0.15 is considered, and =1e-15.

Remark B. 1

 1 (weighted L1-SVM). In order to describe the L1-SVM model associated with the L1energy-SVM defined in Proposition 5.2, we consider the weighted L1-SVM model with (parametric) primal formulation given by minimise w,b,ζP(w, ζ) = 1 2 w T w + čT ζ, subject to Y[Φw + b1] 1ζ and ζ 0, (B.1) with w ∈ R I , ζ = (ζ 1 , • • • , ζ N ) T ∈ R N and b ∈ R (b = b * = 0 in the no-b-term case), and whereč ∈ R N , č > 0 is given. The associated dual problem is minimise α D(α) = 1 2 α T (Ω + Σ)α -1 T α, subject to 0 α č (and y T α = 0 in presence of a b-term), (B.2) with α ∈ R N . If the subset defined by the constraints in (B.2) is non-empty, then the two problems (B.1) and (B.2) always admit solutions and we have w * = Φ T Yα * , and y k b * = 1 -[Ωυ * ] k , for any k ∈ {1, • • • , N } such that 0 < α * k < čk . If c = čγ * with γ * > 0, then the L1-energy-SVM model of Proposition 5.2 and the L1-SVM model defined by the primal-dual problems (B.1)-(B.2) are fully equivalent (in the sense that they lead to exactly the same classifier), and in particular υ * = γ * α * , ω * = γ * w * , ξ * = γ * ζ * and b * = γ * b * . Remark B.2 (generalised L2-SVM). The classifier defined in Proposition 5.1 corresponds to a generalised L2-SVM classifier (the underlying decision functions being identical, up to a rescaling by γ * > 0). The primal form of the associate L2-SVM model is given by minimise w,b,ζ

  and b ∈ R (b = b * = 0 in the no-b-term case). The dual formulation is minimise α D(α) = 1 2 α T (Ω + Σ)α -1 T α, subject to α 0 (and y T α = 0 in presence of a b-term), (B.4) with α ∈ R N . The following relation exists between the solutions of (B.3)-(B.4) and the ones of Proposition 5.1: υ * = γ * α * , ω * = γ * w * , ξ * = γ * ζ * and b * = γ * b * .

  υ)] j ,and the optimal 2-component exchange-direction in the +1-class is therefore κ * + = e i * +e j * + . In the same way, for the -1-class, we define κ * -= e i * -e j * -

Algorithm 1 2 -

 2 component exchange solver for general D-SVMs with constant treshold Require: Feasible vector υ 0 (initialisation), A, d, c (and y for models with b-term); 1: k ← 0; compute ∇D(υ k ) and the sets A υ k of admissible 2-exchange directions at υ k ; 2: while stopping criterion is ok do 3:

Lemma C. 1 .

 1 If υ is feasible for (C.1) and verify κ T ∇D(υ) 0 for all κ ∈ A υ , then υ = υ * .Proof. From the first order optimality condition for υ * , we have (υυ * ) T ∇D(υ) 0 for any feasible υ, and in particular, such a vector υυ * can always be written under the formυυ * = κ∈A υ * β κ κ,with only positive coefficients β κ .

D

  (υ) -D(υ * ) -(e i *υ) T ∇D(υ) (C.3)-(e i *e j * ) T ∇D(υ).(C.4) Inequality (C.3) is related to the FW toward descent direction, while inequality (C.4) is related to the vertex-exchange descent direction; both can be used to evaluate distance to optimality (the FW bound being tighter). Models with b-term: The extreme points of the feasible set for υ consist in all the vectors of the form1 2 (e i + e j ), with y i = +1 and y j = -1. If the data set contains N + points in the +1-class and N -points in -1-class (with N + + N -= N ), there is N + N -extreme points. Any vertexexchange iteration therefore involves 4 components of υ. However, in the constant threshold case (i.e., r = 1), it is still possible to define an optimisation strategy based on 2-component exchanges.The convergence of the 2-exchange strategy can be verified from [6, Theorem 1]; we indeed havemin (i + ,i -)∈I + υ,R ×I - υ,R (e i + + e i -) T ∇D(υ) = min i + ∈I + υ,R e T i + ∇D(υ) + min i -∈I - υ,R e T i -∇D(υ),and in the same waymax (j + ,j -)∈I + υ,G ×I - υ,G (e j + + e j -) T ∇D(υ) = max j + ∈I + υ,G e T j + ∇D(υ) + max j -∈I - υ,G e T j -∇D(υ).We therefore haveD(υ) -D(υ * ) -(e i * + + e i * -)/2υ T ∇D(υ) (C.5) -(e i * + + e i * -)/2 -(e j * + + e j * -)/2 T ∇D(υ) (C.6) = -(e i * +e j * + )/2 + (e i * -e j * -)/2 T ∇D(υ) -(e i *e j * ) T ∇D(υ), (C.7) where i * ∈ I + υ,R ∩ I - υ,R and j * ∈ I + υ,G ∩ I - υ,G are obtained by considering the minimun between (e i *

  is therefore continuous. So, from the Riesz representation theorem, there exists f ν ∈ H such that I ν [h] = (h|f ν ) H , where (•|•) H stands for the inner product of H. The following integral representation holds:

Table 1 :

 1 For the D-SVMs presented in Figures 3 4, value of the cost function at the optimum and number of FW for the computation of υ * λη with accuracy =1e-15, the optimisations being initialised at υ = (1, 0, 0, • • • ) T (i.e., ν = δ x 1 ).

	λ	-50	-2	0	0.4	2	4	10
	iterations	192	5 377	41 056	750 736	348 621	63 580	22 438

Table 3 :

 3 For a L2-E-SVM with or without b-term computed on the Gamma Ray training set, from left to right, considered bandwidth and soft-margin parameters, values of the dual cost at the optimum, error bound at the optimum, number of d-SVs and efficiency of the classifier on the test subsample. The number of FW iterations is fixed to 3N .

		s	D(υ * )	d-SVs	efficiency on test (%) global +1-class -1-class
		1 1 1.18e-4 6.43e-9 10 245 86.81	92.43	76.61
		1.5 1 1.09e-4 1.24e-8	9 878	87.66	94.23	75.72
	b-term	2.5 1 9.98e-5 9.26e-9	9 504	87.62	95.34	73.63
		5 1 8.95e-5 4.05e-10 9 658	86.96	95.54	71.38
		1.5 2 2.00e-4 9.54e-10 10 409 87.28	94.02	75.02
		1 1 1.10e-4 9.88e-9 10 327 87.14	94.18	74.37
		1.5 1 1.04e-4 3.49e-8 10 009 87.67	94.72	74.88
	no b-term	2.5 1 9.85e-5 7.00e-8	9 644	87.59	95.29	73.62
		5 1 8.93e-5 5.45e-8	9 679	86.98	95.54	71.42
		1.5 2 1.91e-4 3.06e-9 10 507 87.48	94.74	74.28
	Sequential learning.

Table 5 :

 5 For various sets of parameters (Gamma Ray data set), L2-D-SVM-based subsample extraction followed by L2-E-SVM prediction. The number of FW iterations for the D-SVM-based extraction is fixed to 2N , and to 2n ex for the predicting E-SVM (or = 1e-11, if this accuracy is reached before 2n ex iterations), where n ex is the size of the extracted subsample.

	L2-D-SVM (extraction)			L2-E-SVM (prediction)
	s λ	d-SVs	b-term		s	d-SVs	efficiency on test (%) global +1-class -1-class
			no	2.85	0	590 87.23	95.60	72.03
	1.5 1 1.5	11 155	yes no	2.85 2.85 0.05 1 111 87.19 0 458 87.21	95.56 95.54	72.08 72.03
			yes	2.85 0.05 1 042 87.24	95.57	72.12
			no	2.85	0	523	86.74	95.44	70.95
	1.5 0 1.5	5 450	yes no	2.85 2.85 0.05 0	483 688	86.69 86.84	95.41 95.89	70.86 70.44
			yes	2.85 0.05	646	86.84	95.93	70.35
			no	2.85	0	133	85.03	96.96	63.37
	1.5 1 2	6 923	yes no	2.85 2.85 0.05 0	130 193	85.07 84.98	96.86 96.91	63.66 63.33
			yes	2.85 0.05	188	85.18	96.93	63.84
	7.2.2 MiniBooNE particle identification data set
	We consider a N = 100 000 randomly selected training set and keep the remaining N test = 29 596
	points for test (the considered training set consists of 28 196 points in the +1-class and 71 804 in
	the -1-class).

Table 6 :

 6 For a L2-E-SVM with b-term computed on the MiniBooNE training set, from left to right, considered bandwidth and soft-margin parameters, values of the dual cost at the optimum, error bound at the optimum, number of d-SVs, number of ξ * k > γ * (active soft-margin) and efficiency of the classifier on the test subsample. The number of FW iterations is fixed to N .

	s	D(υ * )	d-SVs soft	efficiency on test (%) global +1-class -1-class
	5 0.4 1.74e-5 1.34e-7 29 303 2 363 94.81	91.68	96.03
	6 0.4 1.54e-5 1.49e-7 28 850 3 164 94.89	92.15	95.96

Table 7 :

 7 For various parameter settings (MiniBooNE data set), L2-D-SVM-based subsample extraction followed by L2-E-SVM prediction. The number of FW iterations for the D-SVM-based extraction is fixed to N , and to n ex for the predicting E-SVMs (or = 1e-11, if this accuracy is reached before n ex iterations), where n ex is the size of the extracted subsample.

	L2-D-SVM (extraction)			L2-E-SVM (prediction)
	s	λ	d-SVs	b-term		s	d-SVs	efficiency on test (%) global +1-class -1-class
				no	8 0.05	263	91.56	84.17	94.38
	5 0.1 1.5	32 893	yes no	8 0.05 11 0	255 115 91.51 91.47	83.94 84.41	94.40 94.27
				yes	11	0	112	91.48	84.27	94.28
				yes	11 0.05	575	92.91	87.99	94.83
	5 0 1.3	46 110	yes	11	0	370	92.97	88.24	94.81
				no	8	0	781	93.02	88.25	94.87
				yes	8	0	389	93.37	89.98	94.67
	3 0 1.5	61 995	no	8	0	396	93.39	90.14	94.65
				yes	8 0.05	593	93.35	89.81	94.73
				yes	8	0	1 084 94.06	91.00	95.25
	3 0.1 1.3	82 678	yes	7	0	1 333 94.13	91.11	95.30
				yes	7 0.05 1 911 94.05	90.86	95.29

Acknowledgements

The research leading to these results has received funding from the European Research Council under the European Union's Seventh Framework Programme (FP7/2007-2013) / ERC AdG A-DATADRIVE-B (290923). This paper reflects only the authors' views, the Union is not liable for any use that may be made of the contained information -Research Council KUL: GOA/10/09 MaNet, CoE PFV/10/002 (OPTEC), BIL12/11T, PhD/Postdoc grants -Flemish Government: FWO: PhD/Postdoc grants, projects: G.0377.12 (Structured systems), G.088114N (Tensor based data similarity); IWT: PhD/Postdoc grants, projects: SBO POM (100031); iMinds Medical Information Technologies SBO 2014 -Belgian Federal Science Policy Office: IUAP P7/19 (DYSCO, Dynamical systems, control and optimization, 2012-2017).

A Proofs and remarks

Proof of Theorem 4.1. By convexity, υ * is solution of (4.1) if and only if for all υ ∈ R N such that υ 0 and 1 T υ = 1 (and y T υ = 0), we have (first order optimality condition) (υυ * ) T Ωυ * 0.

(A.1)

If (υ * ) T Ωυ * = E(υ * ) > 0, since 1 T υ = 1, then (A.1) leads to

We introduce α = υ * /E(υ * ). The optimality condition (A.2) is then equivalent to assuming that for all α ∈ R N such that α 0 (and y T α = 0), we have

since in particular 1 T α > 0 for all α 0 such that α = 0. By definition, α verifies

So, by subtracting (A.4) to both sides of inequality (A.3), we obtain

which is exactly the optimality condition for the problem (2.2), and therefore α * = α. We now assume that α * = 0 is a solution of (2.2). The optimality condition (A.5) holds in particular for all α such that 1 T α = 1 T α * > 0, that is α = (1 T α * )υ, with υ 0 and 1 T υ = 1 (and y T υ = 0). Introducing υ = α * 1 T α * , inequality (A.5) leads to C Component-exchange solver for general D-SVMs

The dual formulation of a D-SVM with constant treshold r = 1 can be written under the general form, for υ where we recall that

The matrix A is symmetric and positive and we have A = Ω + Σ in the 2 -loss case, and A = Ω for the hard-margin and 1 -loss case. The vector c = (c 1 , • • • , c N ) T ∈ R N is related to the 1 -loss case (and c must be such that the set of feasible υ is non-empty); in the hard-margin or 2 -loss cases, one may simply assume that c k 1 for all k ∈ {1, • • • , N } (so that the underlying constraints will never be active since we hace υ 0 and 1 T υ = 1). Finally, d = Ωθ ∈ R N is related to the distortion term. The gradient of D at υ is ∇D(υ) = Aυd; ∇D is therefore Lipschitz-continous, and when A is invertible, D is strongly convex. We denote by υ * a solution for (C.1).

For any feasible υ and any descent direction δ (i.e., such that δ T ∇D(υ) < 0; by definition, such descent direction always exists when υ = υ * ), the analytical expression of the optimal step-size can be easily obtained (line-search); we indeed have

which is a convex degree-2 polynomial in ρ, reaching its minimum at (unconstrained step-size)

in particular, if δ T Aδ = 0 (this can for instance occur in the hardmargin or 1 -loss case), then ρ = +∞. Combining this result with the feasibility conditions in (C.1) leads to the step size ρ * = max{ρ 0|ρ ρ and υ + ρδ is feasible}.

Since the problem (C.1) is simplex-restricted, that is υ 0 and 1 T υ = 1, increasing (or decreasing) one component of υ necessarily requires to decrease (or increase) some other components of υ in exactly the same proportion, and we may therefore try to take advantage of this property inherent to the dual formulation of D-SVMs. We also want to point out that for large scale problems (and more particularly in the context of "kernelised" solver, where the QP matrix A is not stored), it is of interest to use as sparse as possible descent direction δ since the computation of the optimal step-size and of the gradient update ∇D(υ + ρδ) = ∇D(υ) + Aδ is numerically cheap.

C.1 The 2-component exchange strategy

We denote by e i the i-th element of the canonical basis of R N , that is [e i ] i = 1, all the other component being equal to zero. Considering υ + ρ(e ie j ) amounts to transfer a mass ρ from the j-th to the i-th component of υ; in other words, υ i receives (receiving-component) mass from υ j (giving-component). We shall refer to vectors of the form κ = e ie j as 2-component exchange directions (or 2-exchange directions, for short).

For any feasible υ, admissibility conditions for 2-exchange directions are very simple:

C.3

-loss

In the 1 -loss case, the structure of the polytope defined by the constraint in (C.1) strongly depends on c and the extreme points can not be as easily characterised as in the hard-margin or 2 -loss cases. The 2-exchange strategy is in this case strongly related with the SMO algorithm since optimal 2-exchange directions can be interpreted as maximal violating pairs. The convergence of the 2-exchange strategy can be obtained by following the proof proposed in [8, Theorem 1] (one may also refer to [START_REF] Fan | Working set selection using second order information for training support vector machines[END_REF][START_REF] Hush | QP algorithms with guaranteed accuracy and run time for support vector machines[END_REF]).

C.4 Remark on the weighted threshold case

υ subject to 0 υ Rc and 1 T υ = 1 (and y T R -1 υ = 0 for models with b-term).

(C.9)

For model without b-term, the 2-component exchange can this way be directly applied to problem (C.9); but this does not hold for models with b-term (it is in this case not possible to rely only on 2-exchanges).

In the hard-margin and 2 -loss cases, for models with b-term, the extreme points of the polytope defined by the constraints in (C.9) are of the form (r i e i + r j e j )/(r i + r j ), with y i = +1 and y j = -1. The vertex-exchange strategy therefore define a functional 4-component update strategy, which can be used to define a 4-component exchange strategy allowing to takle 1 -loss case.