{'fraction_non_alphanumeric': 0.03787701660042086, 'fraction_numerical': 0.01205785096362604, 'mean_word_length': 4.131984916009599, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 4, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 13, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sorting out typicality with the inverse moment matrix SOS polynomial

We study a surprising phenomenon related to the representation of a cloud of data points using polynomials. We start with the previously unnoticed empirical observation that, given a collection (a cloud) of data points, the sublevel sets of a certain distinguished polynomial capture the shape of the cloud very accurately. This distinguished polynomial is a sum-of-squares (SOS) derived in a simple manner from the inverse of the empirical moment matrix. In fact, this SOS polynomial is directly related to orthogonal polynomials and the Christoffel function. This allows to generalize and interpret extremality properties of orthogonal polynomials and to provide a mathematical rationale for the observed phenomenon. Among diverse potential applications, we illustrate the relevance of our results on a network intrusion detection task for which we obtain performances similar to existing dedicated methods reported in the literature.


Introduction
Capturing and summarizing the global shape of a cloud of points is at the heart of many data processing applications such as novelty detection, outlier detection as well as related unsupervised learning tasks such as clustering and density estimation. One of the main difficulties is to account for potentially complicated shapes in multidimensional spaces, or equivalently to account for non standard dependence relations between variables. Such relations become critical in applications, for example in fraud detection where a fraudulent action may be the dishonest combination of several actions, each of them being reasonable when considered on their own. Accounting for complicated shapes is also related to computational geometry and nonlinear algebra applications, for example integral computation [9] and reconstruction of sets from moments data [4,5,10]. Some of these problems have connections and potential applications in machine learning. The work presented in this paper brings together ideas from both disciplines, leading to a method which allows to encode in a simple manner the global shape and spatial concentration of points within a cloud.
We start with a surprising (and apparently unnoticed) empirical observation. Given a collection of points, one may build up a distinguished sum-of-squares (SOS) polynomial whose coefficients (or Gram matrix) is the inverse of the empirical moment matrix (see Section 3). Its degree depends on how many moments are considered, a choice left to the user. Remarkably its sublevel sets capture much of the global shape of the cloud as illustrated in Figure 3. This phenomenon is not incidental as illustrated in many additional examples in Appendix A. To the best of our knowledge, this observation has remained unnoticed and the purpose of this paper is to report this empirical finding to the machine learning community and provide first elements toward a mathematical understanding as well as potential machine learning applications. The proposed method is based on the computation of the coefficients of a very specific polynomial which depends solely on the empirical moments associated with the data points. From a practical perspective, this can be done via a single pass through the data, or even in an online fashion via a sequence of efficient Woodbury updates. Furthermore the computational cost of evaluating the polynomial does not depend on the number of data points which is a crucial difference with existing nonparametric methods such as nearest neighbors or kernel based methods [1]. On the other hand, this computation requires the inversion of a matrix whose size depends on the dimension of the problem (see Section 3). Therefore, the proposed framework is suited for moderate dimensions and potentially very large number of observations.
In Section 4 we first describe an affine invariance result which suggests that the distinguished SOS polynomial captures very intrinsic properties of clouds of points. In a second step, we provide a mathematical interpretation that supports our empirical findings based on connections with orthogonal polynomials [3]. We propose a generalization of a well known extremality result for orthogonal univariate polynomials on the real line (or the complex plane) [13, Theorem 3.1.2]. As a consequence, the distinguished SOS polynomial of interest in this paper is understood as the unique optimal solution of a convex optimization problem: minimizing an average value over a structured set of positive polynomials. In addition, we revisit [13,Theorem 3.5.6] about the Christoffel function. The mathematics behind provide a simple and intuitive explanation for the phenomenon that we empirically observed.
Finally, in Section 5 we perform numerical experiments on KDD cup network intrusion dataset [11]. Evaluation of the distinguished SOS polynomial provides a score that we use as a measure of outlyingness to detect network intrusions (assuming that they correspond to outlier observations). We refer the reader to [1] for a discussion of available methods for this task. For the sake of a fair comparison we have reproduced the experiments performed in [14] for the same dataset. We report results similar to (and sometimes better than) those described in [14] which suggests that the method is comparable to other dedicated approaches for network intrusion detection, including robust estimation and Mahalanobis distance [6,8], mixture models [12] and recurrent neural networks [14].
2 Multivariate polynomials and moments

Notations
We fix the ambient dimension to be p throughout the text. For example, we will manipulate vectors in R p as well as p-variate polynomials with real coefficients. We denote by X a set of p variables X 1 , . . . , X p which we will use in mathematical expressions defining polynomials. We identify monomials from the canonical basis of p-variate polynomials with their exponents in N p : we associate We use the expressions < gl and ≤ gl to denote the graded lexicographic order, a well ordering over p-variate monomials. This amounts to, first, use the canonical order on the degree and, second, break ties in monomials with the same degree using the lexicographic order with X 1 = a, X 2 = b . . . For example, the monomials in two variables X 1 , X 2 , of degree less or equal to 3 listed in this order are given by denotes the set of p-variate polynomials: linear combinations of monomials with real coefficients. The degree of a polynomial is the highest of the degrees of its monomials with nonzero coefficients 1 . We use the same notation, deg(·), to denote the degree of a polynomial or of an element of N p . For d ∈ N, R d [X] denotes the set of p-variate polynomials of degree less or equal to d. We set s(d) = p+d d , the number of monomials of degree less or equal to d. We will denote by v d (X) the vector of monomials of degree less or equal to d sorted by ≤ gl . We let v d (X) : With this notation, we can write a polynomial P ∈ R d [X] as follows P (X) = p, v d (X) for some real vector of denotes the evaluation of P with the assignments X 1 = x 1 , X 2 = x 2 , . . . X p = x p . Given a Borel probability measure µ and α ∈ N p , y α (µ) denotes the moment α of µ: y α (µ) = R p x α dµ(x). Throughout the paper, we will only consider measures of which all moments are finite.

Moment matrix
Given a Borel probability measure µ on R p , the moment matrix of µ, M d (µ), is a matrix indexed by monomials of degree at most d ordered by ≤ gl . For α, β ∈ N p d , the corresponding entry in M d (µ) is defined by M d (µ) α,β := y α+β (µ), the moment α + β of µ. When p = 2, letting y α = y α (µ) for α ∈ N 2 4 , we have 1 y 10 y 01 y 20 y 11 y 02 X 1 y 10 y 20 y 11 y 30 y 21 y 12 X 2 y 01 y 11 y 02 y 21 y 12 y 03 X 2 1 y 20 y 30 y 21 y 40 y 31 y 22 X 1 X 2 y 11 y 21 y 12 y 31 y 22 y 13 X 2 2 y 02 y 12 y 03 y 22 y 13 y 04 . M d (µ) is positive semidefinite for all d ∈ N. Indeed, for any p ∈ R s(d) , let P ∈ R d [X] be the polynomial with vector of coefficients p, we have where the integral is understood elementwise.

Sum of squares (SOS)
We denote by , the set of polynomials (resp. polynomials of degree at most d) which can be written as a sum of squares of polynomials. Let P ∈ R 2m [X] for some m ∈ N, then P belongs to Σ 2m [X] if there exists a finite J ⊂ N and a family of polynomials P j ∈ R m [X], j ∈ J, such that P = j∈J P 2 j . It is obvious that sum of squares polynomials are always nonnegative. A further interesting property is that this class of polynomials is connected with positive semidefiniteness. Indeed, P belongs to Σ 2m [X] if and only if As a consequence, every positive semidefinite matrix Q ∈ R s(m)×s(m) defines a polynomial in Σ 2m [X] by using the representation in (1).

Empirical observations on the inverse moment matrix SOS polynomial
The inverse moment-matrix SOS polynomial is associated to a measure µ which satisfies the following.
Assumption 1 µ is a Borel probability measure on R p with all its moments finite and M d (µ) is positive definite for a given d ∈ N.
Definition 1 Let µ, d satisfy Assumption 1. We call the SOS polynomial Q µ,d ∈ Σ 2d [X] defined by the application: the inverse moment-matrix SOS polynomial of degree 2d associated to µ.
Actually, connection to orthogonal polynomials will show that the inverse function x → Q µ,d (x) −1 is called the Christoffel function in the literature [13,3] (see also Section 4).
In the remainder of this section, we focus on the situation when µ corresponds to an empirical measure over n points in R p which are fixed. So let x 1 , . . . , x n ∈ R p be a fixed set of points and let µ := 1 n n i=1 δ xi where δ x corresponds to the Dirac measure at x. In such a case the polynomial Q µ,d in (2) is determined only by the empirical moments up to degree 2d of our collection of points. Note that we also require that M d (µ) 0. In other words, the points x 1 , . . . , x n do not belong to an algebraic set defined by a polynomial of degree less or equal to d. We first describe empirical properties of inverse moment matrix SOS polynomial in this context of empirical measures. A mathematical intuition and further properties behind these observations are developped in Section 4.

Sublevel sets
The starting point of our investigations is the following phenomenon which to the best of our knowledge has remained unnoticed in the literature. For the sake of clarity and simplicity we provide an illustration in the plane. Consider the following experiment in R 2 for a fixed d ∈ N: represent on the same graphic, the cloud of points {x i } i=1...n and the sublevel sets of SOS polynomial Q µ,d in R 2 (equivalently, the superlevel sets of the Christoffel function). This is illustrated in the left panel of Figure 3. The collection of points consists of 500 simulations of two different Gaussians and the value of d is 4. The striking feature of this plot is that the level sets capture the global shape of the cloud of points quite accurately. In particular, the level set {x : Q µ,d (x) ≤ p+d d } captures most of the points. We could reproduce very similar observations on different shapes with various number of points in R 2 and degree d (see Appendix A).

Measuring outlyingness
An additional remark in a similar line is that Q µ,d tends to take higher values on points which are isolated from other points. Indeed in the left panel of Figure 3, the value of the polynomial tends to be smaller on the boundary of the cloud. This extends to situations where the collection of points correspond to shape with a high density of points with a few additional outliers. We reproduce a similar experiment on the right panel of Figure 3. In this example, 1000 points are sampled close to a ring shape and 40 additional points are sampled uniformly on a larger square. We do not represent the sublevel sets of Q µ,d here. Instead, the color and shape of the points are taken proportionally to the value of Q µ,d , with d = 8.
First, the results confirm the observation of the previous paragraph, points that fall close to the ring shape tend to be smaller and points on the boundary of the ring shape are larger. Second, there is a clear increase in the size of the points that are relatively far away from the ring shape. This highlight the fact that Q µ,d tends to take higher value in less populated areas of the space.

Relation to maximum likelihood estimation
If we fix d = 1, we recover the maximum likelihood estimation for the Gaussian, up to a constant additive factor. To see this, set µ = 1 n n i=1 x i and S = 1 n n i=1 x i x T i . With this notation, we have the following block representation of the moment matrix, where V = S − µµ T is the empirical covariance matrix and the expression for the inverse is given by Schur complement. In this case, we have Q µ, We recognize the quadratic form that appears in the density function of the multivariate Gaussian with parameters estimated by maximum likelihood. This suggests a connection between the inverse SOS moment polynomial and maximum likelihood estimation. Unfortunately, this connection is difficult to generalize for higher values of d and we do not pursue the idea of interpreting the empirical observations of this section through the prism of maximum likelihood estimation and leave it for further research. Instead, we propose an alternative view in Section 4.

Computational aspects
Recall Estimating the coefficients of Q µ,d has a computational cost that depends only linearly in the number of points n. The cost of evaluating Q µ,d is constant with respect to the number of points n. This is an important contrast with kernel based or distance based methods (such as nearest neighbors and one class SVM) for density estimation or outlier detection since they usually require at least O(n 2 ) operations for the evaluation of the model [1]. Moreover, this is well suited for online settings where inverse moment matrix computation can be done using Woodbury updates.
The dependence in the dimension p is of the order of p d for a fixed d. Similarly, the dependence in d is of the order of d p for a fixed dimension p and the joint dependence is exponential. This suggests that the computation and evaluation of Q µ,d will mostly make sense for moderate dimensions and degree d.

Invariances and interpretation through orthogonal polynomials
The purpose of this section is to provide a mathematical rationale that explains the empirical observations made in Section 3. All the proofs are postponed to Appendix B. We fix a Borel probability measure µ on R p which satisfies Assumption 1. Note that M d (µ) is always positive definite if µ is not supported on the zero set of a polynomial of degree at most d. Under Assumption 1, M d (µ) induces an inner product on R s(d) and by extension on R d [X] (see Section 2). This inner product is denoted by ·, · µ and satisfies for any polynomials P, Q ∈ R d [X] with coefficients p, q ∈ R s(d) , We will also use the canonical inner product over . We will omit the subscripts for this canonical inner product and use ·, · for both products.

Affine invariance
It is worth noticing that the mapping x → Q µ,d (x) does not depend on the particular choice of v d (X) as a basis of R d [X], any other basis would lead to the same mapping. This leads to the result that Q µ,d captures affine invariant properties of µ.
Lemma 1 Let µ satisfy Assumption 1 and A ∈ R p×p , b ∈ R p define an invertible affine mapping on R p , A : x → Ax+b. Then, the push foward measure, defined byμ(S) = µ(A −1 (S)) for all Borel sets S ⊂ R p , satisfies Assumption 1 (with the same d as µ) and for all Lemma 1 is probably better understood when µ = 1/n n i=1 δ xi as in Section 3. In this case, we haveμ = 1/n n i=1 δ Axi+b and Lemma 1 asserts that the level sets of Qμ ,d are simply the images of those of Q µ,d under the affine transformation x → Ax + b. This is illustrated in Appendix D.

Connection with orthogonal polynomials
We define a classical [13,3] family of orthonormal polynomials, It follows from (3) that P α , P β µ = 0 if α = β. Existence and uniqueness of such a family is guaranteed by the Gram-Schmidt orthonormalization process following the ≤ gl order on the monomials, and by the positivity of the moment matrix, see for instance [3, Theorem 3.1.11].
Let D d (µ) be the lower triangular matrix which rows are the coefficients of the polynomials P α defined in (3) ordered by ≤ gl . It can be shown that This has the following consequence.

A variational formulation for the inverse moment matrix SOS polynomial
In this section, we show that the family of polynomials {P α } α∈N p d defined in (3) is the unique solution (up to a multiplicative constant) of a convex optimization problem over polynomials. This fact combined with Lemma 2 provides a mathematical rationale for the empirical observations outlined in Section 3. Consider the following optimization problem.
We first comment on problem (4). Let P = α∈N p d Q 2 α be the SOS polynomial appearing in the objective function of (4). The constraints of problem (4) restrict P to be in a certain set S d ⊂ Σ d [X]. With this notation, problem (4) is reformulated as min P ∈S d P dµ. Therefore problem (4) balances two antagonist targets, on one hand the minimization of the average value of the SOS polynomial P with respect to µ, on the other hand the avoidance of the trivial polynomial, enforced by the constraint that P ∈ S d . The constraints on P are simple and natural, they ensure that P is a sum of squares of polynomials {Q α } α∈N p d , where the leading term of Q α (according to the ordering ≤ gl ) is q αα x α with q αα > 0 (and hence does not vanish). Inversely, using Cholesky factorization, for any SOS polynomial Q of degree 2d which coefficient matrix (see equation (1)) is positive definite, there exists a > 0 such that aQ ∈ S d . This suggests that S d is a quite general class of nonvanishing SOS polynomials. The following result, which gives a relation between Q µ,d and solutions of (4), uses a generalization of [13, Theorem 3.1.2] to several orthogonal polynomials of several variables.
, is (part of) the unique optimal solution of (4).
Theorem 1 states that up to the scaling factor λ, the distinguished SOS polynomial Q µ,d is the unique optimal solution of problem (4). A detailed proof is provided in the Appendix B and we only sketch the main ideas here. First, it is remarkable that for each fixed α ∈ N p d (and again up to a scaling factor) the polynomial P α is the unique optimal solution of the problem: , Q(x) = x α + β< gl α q β x β . This fact is well-known in the univariate case [13, Theorem 3.1.2] and does not seem to have been exploited in the literature, at least for purposes similar to ours. So intuitively, P 2 α should be as close to 0 as possible on the support of µ. Problem (4) has similar properties and the constraint on the vector of weights θ enforces that, at an optimal solution, the contribution (Q * α ) 2 dµ to the overall sum in the criterion is the same for all α. Using Lemma 2 yields (up to a multiplicative constant) the polynomial Q µ,d . Other constraints on θ would yield different weighted sum of the squares P 2 α . This will be a subject of further investigations. To sum up, Theorem 1 provides a rationale for our observations. Indeed when solving (4), intuitively, Q µ,d should be as close to 0 as possible on average while remaining in a large class of nonvanishing SOS polynomials.

Christoffel function and outlier detection
The following result from [3, Theorem 3.5.6] draws a direct connection between Q µ,d and the Chritoffel function (the right hand side of (5)).

Theorem 2 ([3])
Let Assumption 1 hold and letx ∈ R p be fixed, arbitrary. Then Theorem 2 provides a mathematical rationale for the use of Q µ,d for outlier or novelty detection purposes. Indeed, from Lemma 2 and equation (3), we have Q µ,d ≥ 1 on R p . Furthermore, the solution of the minimization problem in (5) satisfies P (x) 2 = 1 and µ x ∈ R p : P (x) 2 ≤ 1 ≥ 1 − Q µ,d (x) −1 (by Markov's inequality). Hence, for high values of Q µ,d (x), the sublevel set x ∈ R p : P (x) 2 ≤ 1 contains most of the mass of µ while P (x) 2 = 1. Again the result of Theorem 2 does not seem to have been interpreted for purposes similar to ours.

Experiments on network intrusion datasets
In addition to having its own mathematical interest, Theorem 1 can be exploited for various purposes. For instance, the sub-level sets of Q µ,d , and in particular {x ∈ R p : Q µ,d (x) ≤ p+d d }, can be used to encode a cloud of points in a simple and compact form. However in this section we focus on another potential application in anomaly detection.
Empirical findings described in Section 3 suggest that the polynomial Q µ,d can be used to detect outliers in a collection of real vectors by taking µ to be the corresponding empirical measure. This is backed up by the results presented in Section 4. In this section we illustrate these properties on a real world example. We choose the KDD cup 99 network intrusion dataset (available at [11]) which consists of network connection data with labels describing whether they correspond to normal traffic or network intrusions. We follow [15] and [14] and construct five datasets consisting of labeled vectors in R 3 , the label indicating normal traffic or network attack. The content of these datasets is summarized in the following The details on how these datasets are constructed are available in [15,14] and are reproduced in Appendix C. The main idea is to give to each datapoint an outlyingness score solely based on its position in R 3 and then compare outliers predicted by the score with the label indicating network intrusion. The underlying assumption is that network intrusion corresponds to infrequent abnormal behaviors and could thus be considered as outliers.
We reproduce the exact same experiment that was described in [14, Section 5.4] using the value of the inverse moment matrix SOS polynomial from Definition 1 as an outlyingness score (with d = 3). The authors of [14] have compared different types of methods for outlier detection in the same experimental setting: methods based on robust estimation and Mahalanobis distance [6,8], mixture model based methods [12] and recurrent neural network based methods. These results are gathered in [14, Figure 7]. In the left panel of Figure 2 we represent the same performance measure for our approach. We first compute the value of the inverse moment SOS polynomial for each datapoint and use it as an outlyingness score. We then display the proportion of correctly identified outliers, with score above a given threshold, as a function of the proportion of examples with score above the threshold (for different values of the threshold). The main comments are as follows.
• The inverse moment matrix SOS polynomial does detect network intrusions with varying performances on the five datasets.
• Except for the "ftp-data dataset", the global shape of these curves are very similar to results reported in [14,Figure 7] indicating that the proposed approach is comparable to other dedicated methods for intrusion detection in these four datasets.
In a second experiment, we investigate the effect of changing the value of d in Q µ,d on the performances in terms of outlier detection. We focus on the "others" dataset because it is the most heterogeneous in term of data and outliers. We adopt a slightly different measure of performance and use precision recall curves (see for example [2]) to measure performances in identifying network intrusions (the higher the curve, the better). We call the area under such curves the AUPR. The right panel of Figure 2 represents these results. First, the case d = 1, which corresponds to vanilla Mahalanobis distance as outlined in Section 3.3, gives poor performances. Second, the global performances rapidly increase with d and then decrease and stabilize.
This suggests that d can be used as a tuning parameter which controls the "complexity" of Q µ,d . Indeed, 2d is the degree of the polynomial Q µ,d and it is expected that more complex models will potentially identify more diverse classes of examples of points as outliers. In our case, this means identifying regular traffic as outliers while it actually does not correspond to intrusions.

Conclusion and future work
We presented empirical findings with a mathematical intuition regarding the sublevel sets of the inverse moment matrix SOS polynomial. This opens many potential subjects of investigations.
• Similarities with maximum likelihood.
• Statistics in the context of empirical processes.
• Relation between a density and its inverse moment matrix SOS polynomial. Assymptotics when the degree increases.
• Connections with computational geometry and non Gaussian integrals.
• Computationally tractable extensions in higher dimensions.

B Proofs
We use the same notation as in the main text. We recall that Assumption 1.
Assumption 1 µ is a Borel probability measure on R p with all its moments finite and M d (µ) is positive definite for a given d ∈ N.
Lemma 2 and Theorem 2 are taken from the literature and we provide a proof for completeness.

B.1 Proof of Lemma 1
First we show that the mapping x → Q µ,d (x) does not depend on the choice of a specific basis of R d [X]. Then we will deduce the affine invariance property.
, there exists an invertible matrix C ∈ R s(d)×s(d) such that w d (X) = Cv d (X). We reproduce the computation of Definition 1 with this new basis. We write N d (µ) the moment matrix computed with the polynomial basis w d . We have which concludes the proof.
Lemma 1 Let µ satisfy Assumption 1 and A ∈ R p×p , b ∈ R p define an invertible affine mapping on R p , A : x → Ax+b. Then, the push foward measure, defined byμ(S) = µ(A −1 (S)) for all Borel sets S ⊂ R p , satisfies Assumption 1 (with the same d as µ) and for all x ∈ R p , Q µ,d (x) = Qμ ,d (Ax + b).
Proof : Let us first compute M d (μ). For the push forward measureμ, it holds that for any µ integrable function f : By considering polynomial f , we have thatμ has all its moments finite and satisfies Assumption 1 with the same d as µ. Furthermore, we have We can deduce the following identity for all x ∈ R p , It remains to notice that mappings defined by w d (x) = v d (Ax + b) for all x ∈ R p form a basis of the polynomials of degree up to d on R p (by invertibility of the affine mapping). Combining (7) and (8), we see that x → v d (Ax + b) simply corresponds to the use of a different basis of R d [X]. The result follows by applying Lemma 3 and the proof is complete.
Lemma 2 Let µ satisfy Assumption 1, then Q µ,d = Proof : Let D d (µ) be the lower triangular matrix which rows are the coefficients of the polynomials P α defined in (3) ordered by ≤ gl . From properties in (3), D d (µ) is lower triangular with positive coefficients on its diagonal and therefore invertible.
. Plugging this in definition 1 and using equation (1) leads to the desired identity. The average value result follows because we manipulate an orthonormal basis of s(d) polymials, each of which has a square average value (with respect to µ) equal to 1.

B.3 Proof of Theorem 1
We recall the the optimization problem.
Proof : General remarks. Observe that (4) is a convex optimization problem as we have The proof is based on KKT optimality conditions for Problem (4). We first prove that any optimal solution should be of the form Q * α = √ λP α , α ∈ N p d , for some λ > 0. Then we show that there exists a solution of the KKT system which has this form and finally that this solution is unique. The conclusion of Theorem 1 will then follow from Lemma 1. We begin with some notations that we will use throughout the proof.
Notation. Let {e α } α∈N p d denote the canonical basis of R s(d) indexed by α ∈ N p d according to ≤ gl order. The orthonormal polynomials {P α } α∈N p d (with respect to µ) are uniquely defined. For each α ∈ N p d , we write p α = (p αβ ) β∈N p d ∈ R s(d) the coefficients of the polynomial P α . By construction of P α , for every α, β ∈ N p d , α < gl β, p αβ = 0 and p αα > 0.
for all β ∈ N p d , α < gl β. We use the following assignment for the primal and dual variables.
Proof : Fix an arbitrary P ∈ R d [X] andx ∈ R p . Assume that P (x) = 1. Letting for all α ∈ N p d , a α = P, P α µ , by orthonormality, we have The assumption that P (x) = 1 can be used in conjonction with Cauchy-Schwartz inequality to obtain where the last equality comes from the definition of ·, · µ and Lemma 2. There is equality in equation 20 if and only if a α = P α (x)/Q µ,d (x) which always leads to P (x) = 1. This shows that the infimum is attained and concludes the proof.

C Details about the preparation of the datasets
We reproduce the exact same manipulations as in the references. We downloaded the kddcup.data from the following repository https://archive.ics.uci.edu/ml/machine-learning-databases/kddcup99-mld/ This file contains 4898431 instances of network connections described by 42 features including the type of connection (attack or normal). We filter the records by keeping only those for which the variable logged in is positive. We kept the labels (type of connection) together with the four most important features: service, duration, src_bytes, dst_bytes. We applied to the three last variables (numerical) the function log(· + 0.1)/10. We build four datasets with the four most frequent instances of service and group all the remaining records in the dataset others to get our five datasets.

D Illustration of affine invariance
The following Figure illustrate the affine invariance property described in Lemma 1.  4). The cloud in the middle is rotation of the original one and the cloud on the right is the same after centering and scaling. We observe that the level sets follow the same transformations.