St Jorge Guevara

Ephane Canu
email: scanu@insa-rouen.fr

R Hirata
email: hirata@ime.usp.br

Éphane Canu

Stéphane Canu

Support Measure Data Description

Keywords: Kernel on distributions, One-class classification, support vector data description, embedding of probability measures, mean map, group anomaly detection

come

INTRODUCTION

D ATA description (DD) or One-Class Classification is the task of building models to depict the common characteristics of objects in some data set, with the aim of performing machine learning tasks such as anomaly and novelty detection, clustering and classification [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]- [START_REF] Chandola | Anomaly detection: A survey[END_REF] . The main idea of DD methods is to assume an underlying distribution generating the points in the dataset. Consequently, most of them extract from training data some distribution information, for instance, an empirical probability density function, a density level set or information about the density support set.

Usually, DD methods work on datasets given by sets of the form: {x i } N i=1 , x i ∈ R D , where N is the number of observations in the dataset. However, there is a growing interest in machine learning methods for datasets whose individual observations are clusters, groups or, sets of points in R D [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF]- [START_REF] Muandet | Learning from distributions via support measure machines[END_REF]. Such datasets are sets of the form:

T = {s i } N i=1 , (1)
where N is the number of observations and the observation s i is the set {x

(i) 1 , x (i) 2 , . . . , x (i)
Li } with cardinality L i , and each element of s i is a point in R D . Practical examples of observations taking the form of s i are: a set of image features in an image dataset [START_REF] Lowe | Distinctive image features from scale-invariant keypoints[END_REF], a set of spatio-temporal features [START_REF] Laptev | On space-time interest points[END_REF], a set of replicates values for a measurement process [START_REF] Wernisch | Analysis of wholegenome microarray replicates using mixed models[END_REF], a set of points describing point wise uncertainty [START_REF] Shivaswamy | Second order cone programming approaches for handling missing and uncertain data[END_REF]- [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF], a set describing subjective judgments [START_REF] Viertl | Statistical Methods for Fuzzy Data[END_REF], a set describing the invariance of some particular object [START_REF] Graepel | Invariant pattern recognition by semidefinite programming machines[END_REF].

Data description of datasets given by ( 1) is of crucial importance for possible practical applications as we illustrate taking as example the group anomaly detection task [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF], [START_REF] Xiong | Hierarchical probabilistic models for group anomaly detection[END_REF]. The aim of group anomaly detection is to detect anomalous sets of points from datasets taking the form of (1), i.e., to detect unusual observations s i from [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]. Each anomalous set of points, or group anomaly, could be given by [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF]: 1) point-based anomalies, that is, the aggregation of anomalous points, i.e., all the elements in s i are anomalous, or 2) distribution-based anomalies, that is, the anomalous aggregation of non-anomalous points, i.e., all the elements in s i are non-anomalous but the aggregation itself is unusual or anomalous.

In classical anomaly detection 1 , a point is anomalous if it differs from the majority of points in the dataset, for example, a point far away from the empirical mean, or from the support of the generating distribution of points in the dataset. However in group anomaly detection, a group or set of points is considered anomalous, if the local distribution of those points is not similar to the local distributions of the non-anomalous groups of points. Consequently, the information provided by each local distribution of points is crucial for a right description of datasets given by [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]. Figure 1 shows how taking a statistic from s i , and describing such representative values with conventional DD methods, is not enough to guarantee group anomaly detection, because reducing the information provided by s i to a single value will turn conventional anomaly detection methods, highly depended of such a procedure. Moreover, by doing so, useful information could be discarded.

Minimum Volume Sets (MV-sets) for describing

Fig. 1: Left part: four observations: s 1 , s 10 , s 23 , s 77 , from a dataset given by [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF], containing one hundred observations. Observations s 3 , s 10 are two non-anomalous groups of points. Observations s 23 , s 77 are two anomalous groups of points. The plotting axes suggest an overlapping between points from anomalous and nonanomalous groups. Right: red and green points are the group means of anomalous and non-anomalous groups of all the observations in the dataset, respectively. The overlapping between the group means of the anomalous and non-anomalous groups will turn classical DD methods not suitable to perform group anomaly detection in this dataset.

datasets. MV-sets are widely used to find a description of datasets of the form {x i } N i=1 , x i ∈ R D [1]- [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF]. A volume set is a set of points belonging to some region in R D . A MV-set is then computed following some optimization criteria, over all the possible volume sets. Instead of consider such a general case, DD methods consider only the class of sets formed by sets of points belonging to some specific geometric form, as for example, classes of sets given by ellipsoids and convex sets [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF], half-spaces in a Reproducing Kernel Hilbert Spaces (RKHS) [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF], [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF] or enclosing balls in a RKHS [START_REF] Tax | Support vector data description[END_REF]. This work aims to find a description of datasets given by [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]. To do that, we assume that points in s i are generated from a unknown local generating distribution P i . Doing that, the description of (1) can be posed as estimating a MV-set for {P i } N i=1 . Formally, we assume that the points in each observation:

x (i) 1 , x (i) 2 , . . . , x (i)
Li ∈ s i , are i.i.d 2 realizations of a random variable X distributed according to some unknown local probability measure P i defined on the measurable space (R D , B(R D )), with B(R D ) denoting the Borel σ-algebra of R D . A generalization of the definition of MV-set [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]- [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF] to the case of probability measures is given by the next definition. Definition 1.1 (MV-set for probability measures). Let (P, A, E) be a probability space, where P is the space of all probability measures P on (R D , B(R D )), A is some suitable σ-algebra of P, and E is a probability measure 2. Independently and identically distributed. on (P, A). The MV-set is the set 3 4 :

G * α = inf G {ρ(G)|E(G) ≥ α, G ∈ A}, (2)
where ρ is a reference measure on A, and α ∈ [0, 1].

The MV-set G * α , describes a fraction α of the mass concentration of E 5 .

That is, given α ∈ [0, 1] and a reference measure ρ, a MV-set for a set of probability measures is found as follows: 1) measuring each possible set of probability measures G ∈ A, by E(G), 2) keeping all the sets of probability measures G ∈ A satisfying E(G) ≥ α and, 3) selecting the set G * α ∈ A, such that ρ(G * α ) is the infimum ρ(G) over are all the sets G ∈ A satisfying E(G) ≥ α. Finding a MV-set of a set of probability measures with the above procedure is very general, instead, we limit our attention to the class of sets A formed by sets of probability measures satisfying that the realizations of the random variables following such probability measures are inside of a hypersphere or ball.

Enclosing balls in Reproducing Kernel Hilbert Spaces. Considering {P i } N i=1 as an i.i.d sample distributed according to E, such that each P i is unknown, we use an implicit feature mapping given by a realvalued positive definite kernel defined on P × P. We consider then the class A in (2) implicitly defined by such a kernel, as the set of enclosing balls of the implicit representer functions of {P i } N i=1 in a RKHS. Consequently, the MV-set given by ( 2) is given by the minimum enclosing ball (MEB) of such functions in the RKHS.

The representer functions of {P i } N i=1 in a RKHS are given by performing the embedding of {P i } N i=1 into a RKHS [START_REF] Smola | A hilbert space embedding for distributions[END_REF], [START_REF] Guilbart | Produits scalaires sur l'espace des mesures[END_REF]- [START_REF] Berlinet | Reproducing kernel Hilbert spaces in probability and statistics[END_REF]. Such embedding provides a way to compute inner products in P using a kernel defined on P × P, without computing the density of such local distributions as an intermediate step. Moreover, a good approximation for the kernel is assured by an empirically estimation of it using (1) [START_REF] Smola | A hilbert space embedding for distributions[END_REF]. Consequently, in the same way of kernel methods, the description of {P i } N i=1 will be a function depending only on some training examples, P i , which in analogy to support vectors in kernel methods are called as support measures. Consequently, we call the DD method presented in this work as Support Measure Data Description or SMDD.

We present three SMDD models through the paper. In Section 2 is presented the first one as an optimization problem with chance constraints [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF], [START_REF] Wallace | Applications of stochastic programming[END_REF] in the space of probability measures, which is further extended to a RKHS in Section 3. The second and third models are direct extensions of the SVDD model [START_REF] Tax | Support vector data description[END_REF] to the case of 3. A is for instance the Borel σ-algebra with respect to the topology of weak convergence [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF], [START_REF] Ferguson | Prior distributions on spaces of probability measures[END_REF].

4. Assuming that all Borel probability measures P ∈ P have compact domain.

5. As density level sets [START_REF] Steinwart | A classification framework for anomaly detection[END_REF] are MV-sets (the converse is not true [START_REF] Garcia | Level sets and minimum volume sets of probability density functions[END_REF], [START_REF] Scott | Learning minimum volume sets[END_REF]), then alternatively (2) can be stated as estimating the p-level set of E: Cp = {P ∈ P|E(P) ≥ p}, p ∈ [0, 1],, where the set Cp defines a MV-set satisfying that G * 1 correspond to the p-zero level set of E, that is, the density support estimation set of E.

datasets given by {P i } N i=1 . The third SMDD model is almost the same as the second model with the only difference that it considers a scaling of data and translation invariant kernels. Both SMMD models are presented in Section 3. The relationship among all the SMDD models is presented in Section 4. We show through a set of experiments in Section 5, the behavior of such models in the group anomaly detection task using artificial and real world datasets. Finally, some conclusions are given in Section 6.

Notation. We consider a random vector defined on the probability space (Ω, F, P) as a Borel measurable map: X : Ω → R D , satisfying X(ω) = ω, ∀ω ∈ Ω, i.e, X is a identity map. Also, we always consider Ω = R D and F = B(R D ), implying that for B ∈ B(R D ) the probability measure induced by X given by P X (B) = P{ω : X(ω) ∈ B} equals to the probability measure P(B), i.e., P X = P. We always abbreviate P{ω : a < X(ω) ≤ b} by P(a < X ≤ b).

SUPPORT MEASURE DATA DESCRIPTION IN THE SPACE OF PROBABILITY MEASURES

In this section we estimate a empirical MV-set for {P i } N i=1 , as a MEB for the realizations of random variables distributed according {P i } N i=1 . We name such approach as SMDD model in the space of probability measures, which is presented as an optimization problem with chance constraints [START_REF] Shapiro | Lectures on stochastic programming: modeling and theory[END_REF], [START_REF] Wallace | Applications of stochastic programming[END_REF]. Further, using Markov's inequality [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF], we transform such an optimization problem into another one with deterministic constraints. We also present its dual formulation as well. All the results in the present section are further kernelized and consequently extended to a RKHS in Section 3.

Given an i.i.d sample {P i } N i=1 , a first definition for an empirical version of the set G in (2) is given by Ĝ

(R, c) = {P i ∈ P | X i -c 2 ≤ R 2 }, (3)
where (R, c) ∈ R × R D are named as the enclosing balls for {P i } N i=1 , and X i ∼ P i 6 . The empirical MV-set Ĝ * α is then found by estimating the MEB (optimal R and c values, following some optimization criteria) using the sample {P i } N i=1 . In this case, the optimal radius will be proportional to the value α in (2). However, (3) is very conservative definition, because P i will be in [START_REF] Scott | Learning minimum volume sets[END_REF], only if all the possible realizations of X i ∼ P i are inside the enclosing ball (R, c).

A more flexible formulation is given by allowing some realizations of X i ∼ P i not be part of the set Ĝ, this can be done by setting some arbitrary threshold values:

K = {κ i } N i=1 , κ i ∈ [0, 1]
to control the probability for which the realizations of X i ∼ P i are inside of the ball (R, c). That is, given the set K = {κ i } N i=1 , κ i ∈ [0, 1], a more flexible formulation for an empirical version of G in (2) is given by: Ĝ

(K, R, c) = {P i ∈ P | P i ( X i -c 2 ≤ R 2 ) ≥ 1 -κ i }. (4)
6. Notation ∼ means distributed according to.

As each probability measure P i is in Ĝ(K, R, c) depending on its associated value κ i , it is possible to see that if all κ i = 0, then (4) reduces to (3), and if for some i, κ i = 1, then P i is always in Ĝ(K). Probability measures not considered (or considered) to be part of Ĝ(K) are those for which the corresponding distribution function

P i ( X i -c 2 ≤ R 2 ) is less (or greater) than κ i .
Finding the empirical MV-set given by ( 4) means to define an optimization problem with chance constraints. That is, given {P i } N i=1 , and {κ i } N i=1 , κ i ∈ [0, 1], the optimization problem is given by

min c∈R D ,R∈R R 2 subject to P i ( X i -c 2 ≤ R 2 ) ≥ 1 -κ i ,
for all i = 1, . . . , N , where R and c are the radius and the center of the enclosing ball, respectively and, the random vector X i ∼ P i is the uncertainty parameter for the chance-constrained model.

In the same way of kernel methods, we introduce the slack variables: ξ = (ξ 1 , ξ 2 , . . . , ξ N ) ∈ R N to allow some probability measures from {P i } N i=1 not be part of the estimated MEB, then we have the following chanceconstrained program:

Problem 2.1. min c∈R D ,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to P i ( X i -c 2 ≤ R 2 + ξ i ) ≥ 1 -κ i , ξ i ≥ 0.
for all i = 1, . . . , N , where λ > 0 is a regularization parameter.

As the κ i -values are thresholds, an intuitive interpretation for the chance constraints of Problem 2.1 is that the probability that the random vector X i ∼ P i takes its values outside the ball ( R 2 + ξ i , c) is bounded by κ i . Equivalently, the left side of each probabilistic constraint of Problem 2.1 is the distribution function of the random variable 7

Z i = X i -c 2 on the argument R 2 + ξ i , that is, F Zi (R 2 + ξ i ) = P i ( X i -c 2 ≤ R 2 + ξ i ), then, Problem 2.
1 can be posed as:

min c∈R D ,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to F Zi (R 2 + ξ i ) ≥ 1 -κ i , i = 1, . . . , N ξ i ≥ 0, i = 1, . . . , N.
In this formulation, the 1 -κ i values are lower bounds for the distribution function F Zi . Then, all P i , such that ξ i = 0 and F Zi (R) = 1 -κ i , are support measures (in analogy with support vectors), all P i , such that ξ i > 0 and F Zi (R+ξ i ) = 1-κ i , are errors allowed in the training set and, all P i , such that ξ i = 0 and F Zi (R) > 1 -κ i , are non critical points because they are in the MV-set.

7. A distribution function of a random variable X is a function F X from R to [0, 1] given by F X (x) = P({ω : X(ω) ≤ x}) ≡ P(X ≤ x)
It is worth to note that Problem 2.1 is is equivalent to SVDD [START_REF] Tax | Support vector data description[END_REF] when the probability measures are the probability Dirac measures, i.e., P i = δ xi , where δ xi (X i ) = 1 iff X i = x i and zero otherwise [START_REF] Berlinet | Reproducing kernel Hilbert spaces in probability and statistics[END_REF]. Then there is certainty with probability one that the only possible realization of X i ∼ δ xi is x i , this allow us to eliminate the probabilistic constraints and to formulate the problem as the usual SVDD, that is, in this case finding the solution in the input space equals to finding the solution in the space of all probability Dirac measures.

Formulation by Markov's Inequality

Chance constraints of Problem 2.1 control the probability of constraint violation, allowing flexibility in the model. However, each constraint requires we deal with every possible realization of X ∼ P i . Then, it is necessary to transform this problem into another one with deterministic constraints, this can be achieved, by using the Markov's inequality [START_REF] Boucheron | Concentration inequalities: A nonasymptotic theory of independence[END_REF], which for a nonnegative random variable X ∼ P and for some t > 0, bounds P(X ≥ t) by E P [X]/t.

Each chance constraint of Problem 2.1 can be written in equivalent form as

P i ( X i -c 2 ≥ R 2 + ξ i ) ≤ κ i .
Assuming that each probability measure P i has mean µ i ∈ R D and covariance Σ i ∈ R D×D , and noting that X i -c 2 ≥ 0 and (R 2 + ξ i ) ≥ 0 are satisfied, Markov's inequality bounds each chance constraint as:

P i ( X i -c 2 ≥ R 2 + ξ i ) ≤ E Pi [ X i -c 2 ] R 2 + ξ i , i = 1, 2 . . . , N,
where E Pi denotes the expectation for a random variable distributed according P i .

Lemma 2.1. 8 Let P be a probability measure with mean µ and covariance matrix Σ, then for

X ∼ P E P [ X -c 2 ] = tr(Σ) + µ -c 2 .
Applying Lemma 2.1 and Markov's inequality to the chance constraints of Problem 2.1 yields:

P i ( X i -c 2 ≥ R 2 + ξ i ) ≤ tr(Σ i ) + µ i -c 2 R 2 + ξ i , ∀i = 1, 2 . . . , N .
As κ i is the upper bound for the chance constraint i, it is necessary to ensure that

tr(Σ i ) + µ i -c 2 R 2 + ξ i ≤ κ i . (5)
Using [START_REF] Tax | Support vector data description[END_REF] and given {µ i ,

Σ i } N i=1 ⊂ R D × R D×D es- timated from {P i } N i=1 and {κ i } N i=1 , κ i ∈ (0, 1], the deterministic form of Problem 2.1 is the following: Problem 2.2. min c∈R D ,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to µ i -c 2 ≤ (R 2 + ξ i )κ i -tr(Σ i ), ξ i ≥ 0,
8. The proof is found in the supplemental material.

for all i = 1, . . . , N . Problem 2.2 is named as SMDD with joint constraints if κ i = κ for all i ∈ 1, 2, . . . , N .

Lemma 2.2. If there is no information about Σ i , and κ i = 1, ∀i then, SMDD (Problem 2.2) is equivalent to a SVDD [START_REF] Tax | Support vector data description[END_REF] with µ i instead of x i .

Proof: By hypothesis, tr(Σ i ) = 0, replacing κ i = 1, ∀i in Problem 2.2 we get the SVDD [START_REF] Tax | Support vector data description[END_REF] with µ i instead of x i .

Dual Formulation

Denote by α and β the Lagrange multiplier vectors with nonnegative components α i and β i , i = 1, 2, . . . , N , respectively. The Lagrangian for Problem 2.2 is:

L(R, c, ξ, α, β) =R 2 + λ N i=1 ξ i - N i=1 α i {(R 2 + ξ i )κ i -µ i -c 2 } -tr(Σ i )} - N i=1 βξ i (6)
The stationarity and complementarity Karush-Kuhn-Tucker (KKT) conditions for this problem are respectively:

∂ R L = 0 : N i=1 α i κ i c L = 0 : -2 N i=1 α i µ i + 2 N i=1 α i c ∂ ξi L = 0 : λ -α i κ i -β i = 1 = 0 = 0    (7)
α i {(R 2 + ξ i )κ i -µ i -c 2 -tr(Σ i )} β i ξ i = 0 = 0 (8)
Replacing, the KKT's condition in [START_REF] Chandola | Anomaly detection: A survey[END_REF], we obtain the dual problem, i.e., given {µ i ,

Σ i } N i=1 ⊂ R D × R D×D estimated from {P i } N i=1 and {κ i } N i=1 , κ i ∈ [0, 1]
, the dual form of Problem 2.2 is given by Problem 2.3.

max α∈R N N i=1 α i µ i , µ i - N i,j=1 α i α j µ i , µ j N i=1 α i + N i=1 α i tr(Σ i ) subject to 0 ≤ α i κ i ≤ λ, i = 1, . . . , N N i=1 α i κ i = 1.

Representer Theorem and Analysis of KKT's

From stationary conditions [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF], the Representer Theorem [START_REF] Schlkopf | A generalized representer theorem[END_REF] for c is:

c = i α i µ i i α i , i ∈ {i ∈ I | 0 < α i κ i ≤ λ}, (9)
where I = {1, 2, . . . , N }.

Analyzing the complementarity conditions (8) we identify the following cases for all i ∈ I. See Table [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF] for a summary.

• α i = 0, β i > 0 =⇒ ξ i = 0, that yields µ i -c 2 + tr(Σ i ) ≤ R 2 κ i . All the realizations x of X i ∼ P i . satisfying x -c 2 = ( µ i -c 2 + tr(Σ i ))/κ i , κ i = 0 for i ∈ {i ∈ I | α i = 0}
will be inside the ball (R, c) no matters the value for κ i . Consequently, all P i , i ∈ {i ∈ I | α i = 0} are considered to be described by the ball.

• α i > 0, β i = 0 =⇒ ξ i > 0, that yields µ i -c 2 + tr(Σ i ) = (R 2 +ξ i )κ i . All the realizations x of X i ∼ P i satisfying x -c 2 = ( µ i -c 2 + tr(Σ i ))/κ i , κ i = 0 for i ∈ {i ∈ I | α i κ i = λ} will be outside the ball (R, c) with probability κ i . Consequently, all P i , i ∈ {i ∈ I | α i κ i = λ} are considered to be errors allowed in the training set {P i } N i=1 . • α i > 0, β i > 0 =⇒ ξ i = 0 and 0 < α i κ i < λ.
From this and ( 8) we can retrieve the radius

R 2 = µ i -c 2 + tr(Σ i ) κ i , ( 10
)
where i ∈ {i ∈ I | 0 < α i κ i < λ}. Notice that all the realizations x of X i ∼ P i satisfying x -c 2 = ( µ i -c 2 + tr(Σ i ))/κ i , κ i = 0 for i ∈ {i ∈ I | 0 < α i κ i < λ} will be on the surface of the ball (R, c).
Consequently, all P i , i ∈ {i ∈ I | 0 < α i κ i < λ} are considered described by the ball (R, c) and are called support measures.

α i = 0 β i > 0 ξ i = 0 µ i -c 2 + tr(Σ i ) ≤ R 2 κ i i ∈ {i ∈ I|α i = 0} α i > 0 β i = 0 ξ i > 0 µ i -c 2 + tr(Σ i ) = (R 2 + ξ i )κ i i ∈ {i ∈ I|α i κ i = λ} β i > 0 ξ i = 0 µ i -c 2 + tr(Σ i ) = R 2 κ i i ∈ {i ∈ I|0 < α i κ i < λ}

TABLE 1: Summarizing table for the analysis of KKT's condition

The radius value given by [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF] can also be obtained alternatively using information from a Lagrange multipliers of the Lagrangian of Problem 2.3, as we point out in the following result. Teorema 2.3. 9 Let η be the Lagrange multiplier of the constraint

N i=1 α i κ i = 1 of the Lagrangian of Problem 2.3, then R = √ η.
Optimization models with chance constraints in kernel methods were previously studied for the case of input uncertainty. Zhang et al [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF], model input uncertainties with a bounded uncertainty model for data with additive noise. In [START_REF] Shivaswamy | Second order cone programming approaches for handling missing and uncertain data[END_REF], [START_REF] Ben-Tal | Chance constrained uncertain classification via robust optimization[END_REF] is assumed some a priori distribution for model uncertainties resulting in an optimization 9. The proof is found in the supplemental material. model formulated as a Second Order Cone Program [START_REF] Lobo | Applications of second-order cone programming[END_REF]. In [START_REF] Yang | Exploiting uncertain data in support vector classification[END_REF] is considered a Taylor approximation in the RKHS to deal with input uncertainties. The main disadvantage of all those models is the kernelization step and the a priori assumptions for P i .

SUPPORT MEASURE DATA DESCRIPTION IN REPRODUCING KERNEL HILBERT SPACES

In this section we present three formulations of SMDD in a RKHS. Those formulations are MEB's in the RKHS, which correspond to nonlinear descriptions of the training set {P i } N i=1 . The first SMDD model in a RKHS, described in Section 3.2, is the kernelization of the SMDD model presented in the last section. The second and third SMDD models in a RKHS, described in Sections 3.3 and 3.4, respectively, are direct extensions of the SVDD [START_REF] Tax | Support vector data description[END_REF] to the case of training sets of probability measures. with the only difference that the third model uses only invariant translation kernels and a scaling of data. We start our discussion showing the main facts of the Hilbert space embeddings of probability measures.

Notation. Letter H denotes a RKHS of functions f : R D → R, with positive definite kernel k : R D × R D → R, and norm . H . Also, notation k(X i , .), means the mapping t → k(X i , t), with fixed value X i ∼ P i . Inner products in H are denoted by ., . H and . H denotes the norm in the RKHS.

Hilbert Space Embedding of Probability Measures

Hilbert space embedding of probability measures [START_REF] Smola | A hilbert space embedding for distributions[END_REF], [START_REF] Guilbart | Produits scalaires sur l'espace des mesures[END_REF]- [START_REF] Berlinet | Reproducing kernel Hilbert spaces in probability and statistics[END_REF], gives a way to represent probability measures P i as functions in a RKHS. Such functions are commonly named as representer functions, mean functions or mean maps. We present them in the following definition. Definition 3.1 (Mean map). Let P be a probability measure and X ∼ P. The mean map in H is the function:

µ P : R D → R t → µ P (t) = E P [k(X, t)], (11)
where

E P [k(X, t)] = x∈R D k(x, t)dP(x).
Thus, µ P is the representer function in H for P. A sufficient condition guaranteeing the existence of µ P in H is given by assuring that µ P (X) = E P [k(X, X)] < ∞, and k(., .) being a measurable function [START_REF] Smola | A hilbert space embedding for distributions[END_REF], [START_REF] Gretton | A kernel two-sample test[END_REF], [START_REF] Sriperumbudur | Hilbert space embeddings and metrics on probability measures[END_REF]. As a consequence, the reproducing property f, µ

P = f, E P [k(X, .)] = E P [f (X)] holds for all f ∈ H.
The embedding of probability measures P ∈ P to mean maps µ P ∈ H, is given in the following definition. Definition 3.2. The embedding of probability measures P ∈ P in H is given by the mapping

µ : P → H P → µ P = E P [k(X, .)] ( 12
)
where

E P [k(X, .)] = x∈R D k(x, .)dP(x).
Choosing characteristic kernels [START_REF] Sriperumbudur | Hilbert space embeddings and metrics on probability measures[END_REF]- [START_REF] Sriperumbudur | Injective hilbert space embeddings of probability measures[END_REF] for k(., .), the embedding µ is injective, that is,

µ P , f = µ Q , f for all f ∈ H implies P = Q, or equivalently, a positive definite kernel is characteristic if d(P, Q) = µ P -µ Q H = 0 ⇔ P = Q,
where d is a metric on P. Some examples of characteristic kernels are the Gaussian, Laplacian, inverse multiquadratics, B 2n+1 -splines kernels, etc [START_REF] Sriperumbudur | Hilbert space embeddings and metrics on probability measures[END_REF]. Furthermore, an empirical estimator of µ P from the sample {x i } M i=1 drawn i.i.d. from P assure a good approximation for µ P , i.e., the term µ P -µ emp , where µ emp is a empirical estimator of µ P , is bounded [START_REF] Smola | A hilbert space embedding for distributions[END_REF].

Kernel on probability measures

The mapping

P × P → R (P, Q) → P, Q P = µ P , µ Q H , (13)
defines an inner product on P, where from Fubini's theorem [START_REF] Ash | Probability and measure theory[END_REF] follows that µ P , µ

Q H = x∈R D x ∈R D k(x, x )dP(x)dQ(x )
, consequently, the real-valued kernel on P × P, defined by

k(P, Q) = P, Q P = µ P , µ Q H = x∈R D x ∈R D k(x, x )dP(x)dQ(x ) (14)
is positive definite [START_REF] Berlinet | Reproducing kernel Hilbert spaces in probability and statistics[END_REF]. Note that, k(P, Q)

= E P [E Q [k(X, X )]
], X ∼ P and X ∼ Q, by virtue of the reproducing property.

Hilbert space embedding of signed measures was introduced in [START_REF] Guilbart | Produits scalaires sur l'espace des mesures[END_REF] and later by [START_REF] Suquet | Distances euclidiennes sur les mesures signees et applications a des theoremes de berry-esseen[END_REF], [START_REF] Berlinet | Reproducing kernel Hilbert spaces in probability and statistics[END_REF], and by [START_REF] Smola | A hilbert space embedding for distributions[END_REF] when the measures are probability measures. Some applications in machine learning include, dimensionality reduction [START_REF] Fukumizu | Dimensionality reduction for supervised learning with reproducing kernel hilbert spaces[END_REF], measuring independence of random variables [START_REF] Gretton | Kernel methods for measuring independence[END_REF], two-sample test [START_REF] Gretton | A kernel two-sample test[END_REF], embeddings of Hidden Markov Models into RKHS [START_REF] Song | Hilbert space embeddings of hidden markov models[END_REF], Bayes rule [START_REF] Fukumizu | Kernel bayes' rule[END_REF], support vector machines [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF], [START_REF] Muandet | Learning from distributions via support measure machines[END_REF] among others [START_REF] Sriperumbudur | Hilbert space embeddings and metrics on probability measures[END_REF], [START_REF] Sriperumbudur | Injective hilbert space embeddings of probability measures[END_REF], [START_REF] Zhang | Domain adaptation under target and conditional shift[END_REF]. The kernel on probability measures can be estimated using (1) without requiring fitting some probabilistic models to the observations. Another related kernels on distributions which assume probabilistic models for observations are the Fisher kernel [START_REF] Jaakkola | Exploiting generative models in discriminative classifiers[END_REF], the kernel based on the symmetrized Kullback-Leibler (KL) divergence on distributions [START_REF] Moreno | A kullback-leibler divergence based kernel for svm classification in multimedia applications[END_REF], the Bhattacharyya kernel [START_REF] Kondor | A kernel between sets of vectors[END_REF], and the probability product kernel [START_REF] Jebara | Bhattacharyya and expected likelihood kernels[END_REF].

SMDD model in a RKHS as Chance Constrained Problem

Applying the theory of Hilbert space embeddings of probability measures, in this section we generalize the SMDD presented in Section 2 to the case of RKHS. For example, Markov's inequality and lemmas of Section 2 are extended to the case of mean functions and covariance operators in RKHS.

Using a positive definite real-valued kernel k, defined on R D × R D , the set Ĝ from ( 4) is given by: Ĝ

(K) = {P i ∈ P | P i ( k(X i , .) -c(.) 2 H ≤ R 2 ) ≥ 1 -κ i },
where k(X, .) ∈ H, X ∼ P, and the center and radius of the ball are c ∈ H, and R ∈ R, respectively. Enclosing balls (R, c(.)), are defined in the RKHS, which in the input space correspond to nonlinear descriptions of {P} N i=1 . The MEB is then formulated as follows: given

{P i } N i=1 and {κ i } N i=1 , κ i ∈ [0, 1]
, SMDD in the RKHS as chance-constrained program is the following:

min c∈H,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to P i ( k(X i , .) -c(.) 2 H ≤ R 2 + ξ i ) ≥ 1 -κ i , ξ i ≥ 0, for all i = 1, . . . , N .
Solving the above chance constrained program requires that constrains must satisfy all possible realizations of X i ∼ P i , which is hard to compute. Instead, it is possible to transform it into a deterministic one by embedding the probability measures into a RKHS and using Markov's inequality. Using the same argument of Section 2.1, Markov's inequality also holds in the RKHS:

P i ( k(X i , .) -c(.) 2 H ≥ R 2 + ξ i ) ≤ E P [ k(X i , .) -c(.) 2 H ] R 2 + ξ i ,
for all i = 1, 2, . . . , N .

Trace of the Covariance Operator

The term E P [ k(X i , .)-c(.) 2 H can be computed using the trace of the covariance operator in H and mean maps µ P . The covariance operator in H with kernel k is the mapping Σ H : H → H, such that for all f, g ∈ H it satisfies:

f, Σ H g H = E P [f (X)g(X)] -E P [f (X)]E P [g(X)],
because reproducing property 10 . The covariance operator is then the possible infinite dimensional matrix:

Σ H = E P [k(X, .)k(X, .) ] -E P [k(X, .)]E P [k(X, .)] . (15)
From this, the trace of Σ H can be obtained as: 11 tr(Σ H ) =

t∈R D E P [k(X, t)k(X, t) ] -E P [k(X, t)]E P [k(X, t)] dt = E P [ k(X, .)k(X, .) H ] -E P [k(X, .)], E P [k(X, .)] H = E P [k(X, X)] -µ P , µ P H ,
where the last line is due to the reproducing property and Definition 3.1. Then, using [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF], yields

tr(Σ H ) = E P [k(X, X)] -k(P, P), (16)
10. Σ H is a bounded operator on a separable infinite dimensional Hilbert space and can be represented by an infinite matrix [START_REF] Debnath | Hilbert Spaces with Applications[END_REF].

11. Note that as µ P (X) < ∞, follows that tr(Σ H ) < ∞.

that is, the trace of a possible infinite dimensional matrix can be computed in terms of kernels evaluations. In the same way of Section 2.1, Lemma 2.1 becomes:

Lemma 3.1. 12 E P [ k(X, .) -c(.) 2 H ] = tr(Σ H ) + µ P -c(.) 2 H .

Deterministic Form in the RKHS

From Lemma (3.1), Markov's inequality and a similar analysis of Section 2.1, given the mean functions {µ Pi } N i=1 of {P i } N i=1 and {κ i } N i=1 , κ i ∈ (0, 1], the deterministic form of SMDD in the RKHS is the following:

Problem 3.1. min c∈H,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to µ Pi -c(.) 2 H ≤ (R 2 + ξ i )κ i -tr(Σ H i ), ξ i ≥ 0,
for all i = 1, . . . , N , where tr(Σ H i ) is given by ( 16).

Dual Formulation of Problem 3.1

Denoting by α and β the Lagrange multipliers vectors with nonnegative components α i and β i , i = 1, 2, . . . , N , respectively, the Lagrangian of Problem 3.1 is

L(R, c(.), ξ, α,β) = R 2 + λ N i=1 ξ i - N i=1 α i {(R 2 + ξ i )κ i -µ Pi -c(.) 2 H } -tr(Σ H i )} - N i=1 βξ i (17)
The stationarity and complementarity KKT conditions for this problem are:

∂ R L = 0 : N i=1 α i κ i c(.) L = 0 : -2 N i=1 α i µ Pi + 2 N i=1 α i c(.) ∂ ξi L = 0 : λ -α i κ i -β i = 1 = 0 = 0    (18)
α i {(R 2 + ξ i )κ i -µ Pi -c(.) 2 H -tr(Σ H i )} β i ξ i = 0 = 0 (19)
Replacing ( 18) into [START_REF] Yang | Exploiting uncertain data in support vector classification[END_REF], the dual problem is obtained as follows: given the mean functions

{µ Pi } N i=1 of {P i } N i=1 and {κ i } N i=1 , κ i ∈ [0, 1], the dual form of Problem 3.1 is given by Problem 3.2. max α∈R N N i=1 α i µ Pi , µ Pi H - N i,j=1 α i α j µ Pi , µ Pj H N i=1 α i + N i=1 α i tr(Σ H i ) subject to 0 ≤ α i κ i ≤ λ, i = 1, . . . , N N i=1 α i κ i = 1.
12. The proof is found in the supplemental material.

By virtue of [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF], k(P i , P i ) = µ Pi , µ Pi H , then the dual objective function of Problem 3.2 becomes:

N i=1 α i k(P i , P i ) - N i,j=1 α i α j k(P i , P j ) N i=1 α i + N i=1 α i tr(Σ H i )

Representer Theorem and Analysis of KKT's

From KKT's conditions, the Representer Theorem in the RKHS is:

c(.) = i α i µ Pi i α i = i α i E Pi [k(X, .)] i α i , (20)
for all i ∈ {i ∈ I | 0 < α i κ i ≤ λ}, where I = {1, 2, . . . , N } Analyzing stationary [START_REF] Smola | A hilbert space embedding for distributions[END_REF] and complementary (19) conditions we have the same information provided by Table 1

but with µ Pi ∈ H instead of µ i ∈ R D , c ∈ H instead c ∈ R D and Σ H i instead of Σ i .
From this we have

• all P i , i ∈ {i ∈ I | α i = 0} are described by (R, c), because µ Pi are inside (R, c) • all P i , i ∈ {i ∈ I | α i κ i =
λ} are considered to be the errors allowed in the training set. • all P i , i ∈ {i ∈ I | 0 < α i κ i < λ} are the support measures, from this the radius is computed as

R 2 = µ Pi -c(.) 2 + tr(Σ H i ) κ i , (21)
for all i ∈ {i ∈ I | 0 < α i κ i < λ}. Alternatively, R can be computed by Theorem (2.3) as R = √ η, where η is the Lagrange multiplier of the constraint N i α i κ i of the Lagrangian of Problem 3.2. It is worth to note that using the linear kernel: k(x, x ) = x, x in ( 14), Problem 3.2 is equivalent to Problem 2.3, because, k(P i ,

P j ) = E Pi [E Pj [ X, X ]] = µ i , µ j .

Role of κ-values

As it was point out in Section 2, particular values for κ in the constraint i will increment or decrement the radius covering the realizations of X ∼ P i . We illustrate this behavior in Figure 2, which shows a dataset of ten Gaussian distributions, and six MEB's for them, given by solving Problem 3.2, with six different settings for the κ values. We used the RBF kernel k(x, x ) = exp(-γ xx 2 ) and γ = 1 to implement [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF].

Left to right of top part of Figure 2 shows three MVsets in the input space which are three MEB's in RKHS, given by solving three SMDD (Problem 3.2) with κ i = 0.8, κ i = 0.9 and κ i = 1.0 for all the constraints i of the three models, respectively.

Left to right of bottom part of Figure 2 shows another three MV-set. All the three SMDD models have κ i = 1 in their constraints, excepting κ 1 = κ 2 = 0.8 for the first, κ 1 = κ 2 = 0.9 for the second, and κ 1 = κ 2 = 1.0 for the third SMDD. Depending on particular κ values, the corresponding probability measures P 1 and P 2 , belongs to the MV-set in some degree. Fig. 2: Six MEB's describing a dataset of Gaussian distributions, showing the effect of choosing particular κ values for their constraints. Top part: all the three models share the same κ-value, which is incremented from left to right. Bottom part: all the three models have κ = 1 for all their constraints, except its constraints i = 1 and i = 2, which are incremented from left to right. Decreasing a κ-value for some specific constraint, tend to cover the respectively P i

SMDD in a RKHS as a direct extension of SVDD

Differently of the SMDD model of the last section that uses mean maps and covariance operators, the SMDD model presented in this section only uses mean maps. This model is a direct extension of the SVDD to deal with probability measures. Using the mean maps µ Pi , an empirical version of G from (4) is given by:

Ĝ(R, c) = {P i ∈ P | µ Pi -c(.) 2 H ≤ R 2 }, (22)
then, the empirical MV-set Ĝ * α is computed by a MEB for the mean maps {µ Pi } N i=1 . This can be formulated as follows: given the mean functions {µ Pi } N i=1 of {P i } N i=1 , the SMDD model is the following:

min c(.)∈H,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to µ Pi -c(.) 2 H ≤ R 2 + ξ i , i = 1, . . . , N ξ i ≥ 0, i = 1, . . . , N.
The Lagrangian for the above problem is:

L(R, c(.), ξ, α, β) =R 2 + λ N i=1 ξ i - N i=1 α i {(R 2 + ξ i ) -µ Pi -c(.) 2 } - N i=1 βξ i (23)
The optimality (KKT) conditions for this problem are:

∂ R L = 0 : N i=1 α i c(.) L = 0 : -2 N i=1 α i µ Pi + 2 N i=1 α i c(.) ∂ ξi L = 0 : λ -α i -β i = 1 = 0 = 0    ( 24
)
α i {(R 2 + ξ i ) -µ Pi -c(.) 2 } β i ξ i = 0 = 0 (25)

Dual Formulation

Given the mean functions {µ Pi } N i=1 of {P i } N i=1 , the dual form of the previously Problem is given by replacing, ( 24) into (23) as follows:

Problem 3.3. max α∈R N N i=1 α i k(P i , P i ) - N i,j=1 α i α j k(P i , P j ) subject to 0 ≤ α i ≤ λ, i = 1, . . . , N N i=1 α i = 1
where it was used [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF] to replace µ Pi , µ Pj by the kernel k(P i , P j ). From [START_REF] Ferguson | Prior distributions on spaces of probability measures[END_REF] follows that the Representer Theorem is:

c(.) = i α i µ Pi , i ∈ {i ∈ I | 0 < α i ≤ λ}.
Analyzing [START_REF] Steinwart | A classification framework for anomaly detection[END_REF] follows that all P i , i ∈ {i ∈ I | α i = 0} are probability measures described by (R, c), because µ Pi are inside the ball (R, c).

All P i , i ∈ {i ∈ I | α i = λ} are errors. All P i , i ∈ {i ∈ I | 0 < α i < λ} are support measures.
If the linear kernel: k(x, x ) = x, x is used in ( 14), Problem 3.3 is equivalent to the dual problem of SVDD [START_REF] Tax | Support vector data description[END_REF], because, k(P i , P j ) = E Pi [E Pj [ X, X ]] will be µ i , µ j .

SMDD Model in a RKHS using Mean Maps with Norm One and Invariant Translation Kernels

Translation invariant kernels or stationary kernels [START_REF] Genton | Classes of kernels for machine learning: A statistics perspective[END_REF], are kernels of the form k I (x, x) = k (x -x ), that is, such kernels only depend on the difference x -x , and not of the observations x, x themselves. The kernel k is positive definite only if it can be written as R D cos(ω (x-x ))dF (ω), where F is a positive measure.

Implicit feature maps of translation invariant kernels, are functions k I (x, .) in a RKHS lying on a surface of a hypersphere, that is, have constant norm. To see that, note that translation invariant kernels satisfy:

k I (x, x) = k I (x, .), k I (x, .) H = , ∀x ∈ R D
where is a constant value, then immediately follows that k I (x, .) H = | |, that is, functions k I (x, .) lie on a surface of a sphere of radius | |.

However, mean maps given as µ P = E P [k I (X, .)], does not have constant norm, because

µ P H = E P [k I (X., )] H ≤ E P [ k I (X., ) H ] = | |,
by convexity of . H and Jensen's inequality.

A possible solution to prevent small values for the radius, is to scale mean maps µ P to have norm one, to lie on the surface of some hypersphere. The following theorem is due to Muandet et al [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF]. Teorema 3.2 (Spherical Normalization [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF]). If kernel k(., .) is characteristic and the examples are linearly independent in the RKHS H, then the spherical normalization:

µ P , µ Q H = µ P , µ Q H µ P , µ P H µ Q , µ Q H , (26)
preserves the injectivity of the mapping µ : P → H.

Or in another words, Theorem 3.2 says that all the information is preserved after performing spherical normalization on the data.

Consequently, an empirical version for the set Ĝ from (4) is given by:

Ĝ(R, c) = {P i ∈ P | µ Pi -c(.) 2 H ≤ R 2 , µ P 2 H = 1} then, the empirical MV-set Ĝ * α is the MEB of the mean maps {µ Pi } N i=1 satisfying µ P 2 H = 1, such the kernel used in E Pi [k I (X, .)] = µ Pi is translation invariant.
The optimization problem for this model is almost the same as given in Problem 3.3:

max α∈R N N i=1 α i k(P i , P i ) - N i,j=1 α i α j k(P i , P j ) subject to 0 ≤ α i ≤ λ, i = 1, . . . , N N i=1 α i = 1,
but with kernel:

k(P i , P j ) = k(P i , P j ) k(P i , P i ) k(P j , P j ) , (27)
which is due to Theorem 3.2. Note that k is given by ( 14) but with kernel k I . As N i=1 α i k(P i , P i ) is constant, formerly problem can be written as Problem 3.4.

max α∈R N - N i,j=1 α i α j k(P i , P j ) subject to 0 ≤ α i ≤ λ, i = 1, . . . , N N i=1 α i = 1,
This formulation looks like the dual formulation of One-class Support Vector Machine [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF], but is not directly equivalent. We discuss this point in the next section.

RELATIONSHIP AMONG SMDD MODELS

In this section we point out the relationship among SMDD models, also we discuss the equivalence between SMDD models and One-Class Support Measure machine (OCSMM) [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF], [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF]. Thorough this Section, we denote the SMDD presented in Section 3.2 as M1 (Problems 3.1 and 3.2), the SMDD of Section 3.3 as M2 (Problem 3.3), and the SMDD of Section 3.4 as M3 (Problem 3.4).

We start showing how M1 can be formulated if we restrict it only to the case of joint constraints and same covariance matrix. Thus, we use this formulation to compare it with M1 and M2. Teorema 4.1. 13 The Primal form of M1 (Problem 3.1) with joint constraints sharing the same covariance matrix, i.e, κ i = κ and Σ H i = Σ H for all i = 1, 2 . . . , N and λ > 0, can be written as Problem 4.1.

min c(.)∈H,ρ ∈R,ξ ∈R N c(.) 2 H 2 -ρ + λ N i=1 ξ i subject to µ Pi , c(.) H ≥ ρ -ξ i , i = 1, . . . , N ξ i ≥ - µ Pi 2 H 2 , i = 1, . . . , N.
where

ξ i = 1 2 κξ i - µ Pi 2 H 2 (28)
Notice that Problem 4.1 is a less flexible formulation of M1 (Problem 3.1), because it considers the same local covariance and the same κ values for all points. It is easy to verify that, for optimal c ∈ H and ρ values from Problem 4.1. 14 , we retrieve the radius as:

R = (tr(Σ) + c 2 -2ρ ))/κ, (29)
or equivalently, solving Problem 3.1 for κ i = κ and Σ i = Σ for all i = 1, 2 . . . , N , we can retrieve ρ of Problem 4.1 as follows:

ρ = - 1 2 (R 2 κ -tr(Σ) -c 2 ).
Teorema 4.2. 15 Using the kernel between probability measures given by ( 14), the dual of Problem 4.1 is given by: Problem 4.2. From this, we can solve Problem 4.2 and apply Lemma 4.3 to retrieve ρ, the center via the Representer Theorem given by ( 24) as c = i α i µ Pi , i ∈ {i|0 < α i ≤ λ}, and the radius R from (29).

max α∈R N 1 2 N i=1 α i k(P i , P i ) - 1 2 N i,j=1 α i α j k(P i , P j ) subject to 0 ≤ α i ≤ λ, i = 1, . . . , N N i=1 α i = 1.
13. The proof is found in the supplemental material. 14. See proof of Theorem 4.1 in the supplemental material as an example 15. The proof is found in the supplemental material.

Equivalence among SMDD models

M1 vs M2

Problem 4.2 is the dual of M1 with joint constraints sharing the same covariance matrix. Under this setting M1 is almost the same as M2 but with a difference of a scaling factor of 0.5 in the dual objective function.

M1 vs M3

After spherical normalization on data, the dual objective function of Problem 4.2, becomes -0.5 N i,j=1 α i α j k(P i , P j ), because the other term in the objetive function is constant where k is the kernel given by [START_REF] Suquet | Distances euclidiennes sur les mesures signees et applications a des theoremes de berry-esseen[END_REF]. Therefor, M1 with joint constraints sharing the same covariance matrix and spherical normalization on data is equivalent to model M3, with a difference of a scaling factor of 0.5 in the dual objective function, as well.

Connection with One-Class Support Vector Machines

It is widely known that SVDD [START_REF] Tax | Support vector data description[END_REF] and One-Class Support Vector Machines (OCSVM) [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF] are equivalent if translation invariant kernels are used [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF], [START_REF] Tax | Support vector data description[END_REF]. Although, Problem 4.1 is pretty similar to OCSVM with probability measures [START_REF] Sch Ölkopf | Estimating the support of a high-dimensional distribution[END_REF], [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF], SMDD is not directly equivalently with one-class support vector machines, because even if an invariant translation kernel is used, norms of mean maps are not constant. However, if is performed spherical normalization on data there is the following equivalence: Corollary 4.4. M2, M3 and OCSMM [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF] Consequently, it is possible to deduce that M1 under the setting given by Problem 4.2 is equivalent to OC-SMM, with a difference of a scaling factor of 0.5 in the dual objective function.

EXPERIMENTS

In this section, following the works [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF], [START_REF] Xiong | Hierarchical probabilistic models for group anomaly detection[END_REF], [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF], we tested the SMDD models in the challenging task of group anomaly detection for the case of Point-based anomaly detection in 5.1 and, for the case of Distributionbased anomaly detection in Section5.2. Finally, in Section 5.3, we use real data from the Sloan Digital Sky Survey (SDSS) project, to detect anomalous groups of galaxies. We employed the same notation as the ones given in Section 4 to denote the SMDD models, i.e., M1 is the SMDD given by Problem 3.2, M2 by Problem 3.3, and M3 by Problem 3.4. Also, for comparison purposes, M4 will be the OCSMM [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF], and M5 will be the SVDD [START_REF] Tax | Support vector data description[END_REF]. We used M5 as the baseline for our experiments. This is shown in Table 2.

Kernel and covariance estimation. The kernel between probability measures given by ( 14) was estimated via the empirical estimator:

k(P i , P j ) ≈ 1 L i L j Li l=1 Lj l =1 k(x (i) l , x (j) l ), (30)
on the training set given by [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]. Also, the trace of the covariance operator in the RKHS given by ( 16) was estimated by:

tr(Σ H i ) ≈ 1 L i -1 Li l=1 k(x (i) l , x (i) l ) - 1 L i (L i -1) Li l=1 Li l=1 k(x (i) l , x (i) l ). ( 31
)
where R D × R D is a positive definite kernel. We used CVX, a package for specifying and solving convex programs [START_REF] Grant | CVX: Matlab software for disciplined convex programming, version 2.1[END_REF], [START_REF]Graph implementations for nonsmooth convex programs[END_REF] to solve M1. To solve M2, M3, M4 and M5 we used the SVM and Kernel Methods Matlab Toolbox (SVM-KM) [START_REF] Canu | Svm and kernel methods matlab toolbox[END_REF]. 16 Thorough the experiments, for each observation s i from (1) we used the terms: group, cluster or set of points, interchangeably, i.e., we say training sets given by (1) have N groups, clusters or set of points. As M5 was not originally designed to deal with probability measures it was trained using only the empirical group means.

Point-Based Group Anomaly Detection over a Gaussian Mixture Distribution data set

The goal of group anomaly detection is to find groups of points with unexpected behavior from datasets given by [START_REF] Polonik | Minimum volume sets and generalized quantile processes[END_REF]. Differently from usual anomaly detection, points of anomalous groups can be highly mixed with points of non-anomalous groups turning group anomaly detection a challenge problem.

In Point-Based Group Anomaly detection [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF], anomalous groups are given by aggregating individually anomalous points. For this experiment, we generated 50 nonanomalous groups of points and 20 anomalous groups [START_REF] Graepel | Invariant pattern recognition by semidefinite programming machines[END_REF]. The Matlab code and datasets for experiments can be found at http://www.vision.ime.usp.br/ ∼ jorjasso/SMDD.html of points as we will detail in the next paragraph. The number of points by group for all non-anomalous and anomalous groups was randomly chosen from a Poisson distribution: n i ∼ Poisson(100).

Points of non-anomalous groups were randomly sampled from a Multimodal Gaussian Mixture Distribution or GMD [START_REF] Xiong | Hierarchical probabilistic models for group anomaly detection[END_REF], [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF], with two different group type distributions: π = (0.48, 0.52). That is, the first 48% of non-anomalous groups of points were generated from a two dimensional GMD with three components, mixture weights: (0.33, 0.64, 0.03), means: (-1.7, -1), (1.7, -1), (0, 2), and 0.2 * I 2 as the sharing covariance matrix, where I 2 denote the 2 × 2 identity matrix. The other 52% of non-anomalous groups were generated from another GMD with the same parameters but with mixture weights: (0.33, 0.03, 0.64). The green box in Figure 3 shows three non-anomalous groups for π = 0.48 and the yellow box shows two non-anomalous groups for π = 0.52.

Three different types of anomalous groups have been generated. the first type was given by 10 groups of points randomly generated from the normal distribution: N ((-0.4, 1), I 2 ). The magenta box in Figure 3 shows five anomalous groups of this type. The second type was given by 5 group of points sampled from a GMD with four components, weights: (0.1, 0.08, 0.07, 0.75), means: (-1.7, -1), (1.7, -1), (0, 2), (0.6, -1), and 0.2 * I 2 as the sharing covariance matrix. The blue box in Figure 3 shows five anomalous groups of this type. The third type of group anomalies was given by 5 group of points sampled from a GMD with four components, weights: (0.14, 0.1, 0.28, 0.48), means: (-1.7, -1), (1.7, -1), (0, 2), (-0.5, 1), and 0.2 * I 2 as the sharing covariance matrix. The red box in Figure 3 shows five anomalous groups of this type. Fig. 3: Group anomaly detection dataset. Green and yellow boxes contains non-anomalous groups of points. Red, blue, and magenta boxes contains anomalous groups of points.

To get reliable statistics, we performed 200 runs, over a training set given by the 50 non-anomalous groups. The test set was given by the 20 anomalous groups, plus an extra of 10 non-anomalous groups generated with the same procedure as the training set, totalizing a test set of 30 groups. The performance metrics were: the area under the ROC curve (AUC), and the accuracy (ACC).

As usually, in one-class classification, training data and test data has no labels, turning impossible to have a validation set for model selection. Also, as the problem of describing a dataset is not trivial, because it may exists many models describing well such dataset, we follows the same methodology used in literature, that is, we choose arbitrarily a value for the regularization parameter λ of the SMDD model and, the kernel parameters are computed using some heuristic on the available data, avoiding to use the training or the test set for perform model selection.

It was considered a regularization parameter λ = 1, and a kernel between probability measures [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF] implemented by a RBF kernel with bandwidth parameter γ computed as the inverse of the 0.1 quantile of the Euclidean distance between all possible pair of points in the dataset. i.e.,

γ = 1/s( x (i) k -x (j) l 2 ), ( 32
)
where s is the 0.1 quantile, i, j are the groups indices, and k, l are the points indices. Figures 4a,4b, 4c show the results in boxplots for this experiment. The boxplots shows the AUC, the ACC for non-anomalous groups, and the ACC for anomalous groups respectively. The red mark in each boxplot is the median and the edges of each boxplot are the 25th and 75th percentiles, the height of each boxplot is the inter quartile range. This experiment shows that all the SMDD models: M1, M2, and M3 detect such anomalies very well. The AUC value close to one of those models indicate that the SMDD models detect group anomalies with few false positives and false negatives. On the other hand, M5 (SVDD) can not detect such group anomalies using only the group means as the training set.

To see why group anomaly detection is a hard problem, the plot of the means of all the non-anomalous and anomalous groups is shown in Figure 4d. The green points are the means of non-anomalous groups. Red, blue, and magenta points are the means of anomalous groups of points corresponding to the red, blue, and magenta boxes in Figure 3. Because the non-anomalous group means overlap the anomalous group means, methods as One-class support vector machines and SVDD will not perform well, because such methods consider anomalies the points far away from the mean of the description of the data.

Distribution-Based Group Anomaly Detection over a Gaussian Mixture Distribution data set

Distribution-Based Group Anomalies [START_REF] Xiong | Group anomaly detection using flexible genre models[END_REF] are anomalous groups of points that individually are non-anomalous but together form anomalous groups. For this experiment, it was generated 50 non-anomalous groups of points to form the training set and 15 anomalous groups of points plus 15 non-anomalous points to form the test Marks on the x-axis of each boxplot are the DD models and y-axis is the performace measure. Figure 4d plots the means of non-anomalous groups vs. the means of anomalous groups. Red, magenta and blue points are the group means of anomalous groups. Green points are the means of non-anomalous groups set, as we will explain in the next paragraph. Also, the number of points per group was given as the previous experiment, that is:

n i ∼ Poisson(100).
Points in each non-anomalous group, were sampled from a two dimensional unimodal GMD with three components, mixture weights: p = {0.33, 0.33, 0.33}, means: (-1.7, 1), (1.7, -1), (0, 2), and sharing the same covari-ance matrix: 0.2 * I 2 .

Anomalous groups were generated from the same GMD of non-anomalous groups, but with two of their covariance matrices rotated 45 degrees, that is, individually the points are relatively normal but together as a group are anomalous.

As the last experiment, it was used the AUC and ACC metrics for performance measure, a regularization parameter λ = 1, and a kernel between probability measures [START_REF] Zhang | Support vector classification with input data uncertainty[END_REF] implemented by a RBF kernel with bandwidth parameter γ computed as the inverse of the median of the Euclidean distance between all possible pair of points in the dataset.

Figure 5d shows the group means. Green points are the non-anomalous groups means and red points are the anomalous groups means. As in the last experiment, to find such group anomalies is hard because the overlapping between the group means of the non-anomalous and anomalous groups.

Figures 5a,5b,5c show in boxplots the AUC, the ACC for non-anomalous groups, and the ACC for anomalous groups respectively. Also, for this type of group anomalies all the SMDD models performs very well. As it was expected, performance of M5 is the worst because the overlapping of group means.

Finally, for the same training set, we considered another distribution-based group anomalies, ten group anomalies were generated from a GMD with the same parameters of the training set, but with weights: p = {0.85, 0.08, 0.07} and another ten group anomalies with weights: p = {0.04, 0.48, 0.48}. Figure 5h shows the means of the anomalous (red) and non-anomalous groups (green). For this particular setting, it is possible to see that classical methods such as SVDD and one-class support vector machine will perform well based only on the means information. Figures 5e,5f, 5g show the AUC, the ACC for non-anomalous groups, and the ACC for anomalous groups respectively. Models M2 and M3 perform as M5 (SVDD). Performance of M1 is affected because it uses first and second moment information for a problem that is easily solved using only information of the group means. However, because the dimensionality of the data, it is very hard to to know beforehand such information.

Group Anomaly Detection in Astronomical Data

In this section, we tested the SMDD models with real data: The Sloan Digital Sky Survey 17 (SDSS) project. This dataset contains massive spectroscopy surveys of the universe, the Milky Way galaxy, and extrasolar planetary systems. The idea of the experiment is to use the dataset to detect anomalous clusters of galaxies. a problem, using the same dataset, had been previously studied in [START_REF] Xiong | Hierarchical probabilistic models for group anomaly detection[END_REF]- [START_REF] Muandet | One-class support measure machines for group anomaly detection[END_REF] as a group anomaly detection problem. The dataset contains about 7 × 10 5 galaxies, where each galaxy is represented by a 4000-dimensional feature vector representing spectral information. Features vectors were processed as follows [START_REF] Xiong | Nonparametric divergence estimation with applications to machine learning on distributions[END_REF]: each vector was down-sampled to get a 500-dimensional feature vector to represent a galaxy. Clusters of galaxies were obtained analyzing the spatial neighborhood of galaxies, see [START_REF] Xiong | Nonparametric divergence estimation with applications to machine learning on distributions[END_REF] for details. This procedure returns 505 clusters of galaxies of a total of 7530 galaxies. Thus, each cluster of galaxies is a group of about 10 -15 galaxies. Finally, PCA was applied to the feature vectors of galaxies, to get a four-dimensional dataset, preserving about 85% of the variance of the data.

To perform group anomaly detection, a training set was formed by randomly choosing 455 group of galaxies among the original 505 groups. Also, it was generated five test datasets, each of them containing the remaining 50 non-anomalous groups from the original 505 groups plus 50 anomalous groups.

In the first test dataset, each anomalous group was constructed by randomly selecting about n i ∼ Poisson(15) galaxies from the 7530 galaxies, i.e, galaxies from the 505 non-anomalous groups. Note that, because galaxies were randomly chosen, the aggregation itself of such galaxies are anomalous.

Anomalous groups for the second, third, fourth and fifth test sets were generated as follows: First, the covariance of the 7530 observations (galaxies) was empirically estimated. After that, were selected randomly three sets of galaxies from the 7530 galaxies, each one containing about n i ∼ Poisson (15) galaxies. Were computed the empirical means of the three sets. With the three empirical mean values and the empirical covariance matrix, a GMD with three components and weights: p = {0.33, 0.33, 0.33} was constructed.

Anomalous groups of points for the second test data set were generated from the above GMD, with about n i ∼ Poisson (15) points per group. Anomalous groups 17. http://www.sdss3.org/ of points for the third, fourth and fifth test set were generated as the second test set, but using the covariance matrices 5 * Σ, 10 * Σ, and 100 * Σ, respectively.

We plotted in Figures 6d, 6h, 6l, 6p,and 6t the group means of the PCA features. Green points are the nonanomalous group means and red points are the anomalous group means. Each figure shows four plots: upperleft: the plot of the first vs second dimension, upperright: the plot of the second vs third dimension, bottomleft: the plot of the third vs four dimension, bottom-right: the plot of the four vs first dimension. Note that, because the overlapping of group means of non-anomalous groups and anomalous groups, group anomalies for this experiment are hard to detect.

For all the SMDD models, the kernel between probability measures was implemented via the RBF kernel. To get reliable statistics, it was performed 200 runs for each test set to get the AUC, the ACC of non-anomalous and the ACC of anomalous groups. Figures 6a,6b, and 6c show the AUC, the ACC for non-anomalous groups, and the ACC for the anomalous groups in the first test set. The kernel parameter was computed by [START_REF] Schlkopf | A generalized representer theorem[END_REF] but with s being the median. It was considered a regularization parameter allowing about 30% of the non-anomalous groups to be the errors allowed in the training set. Models M2 and M3 performs a little worst detecting group anomalies than M5 for this choice of parameters. However, the AUC metric for M5 shows that performance for this model is not better than chance. On the another hand M1 and M4 perform better than the baseline and both in similar way detecting group anomalies. Note that the ACC for the non-anomalous groups is about 70% because the choice of the regularization parameter. Plot of the group means in Figure 6d shows the hardness of the problem.

Figures 6e,6f, and 6g show the AUC, the ACC for non-anomalous groups, and the ACC for the anomalous ones in the second test set. The RBF kernel parameter was computed by [START_REF] Schlkopf | A generalized representer theorem[END_REF]. It was considered a regularization parameter allowing about 20% of the non-anomalous groups to be the errors allowed in the training set. The AUC metric shows that M5 performs worst than the other models, and spherical normalization on data increases the performance as it can be seen by the AUC value of M3. On the other hand, the accuracy of normal groups is about 80% because the choice of λ. The plot of the group means is shown in Figure 6h.

Figures 6i,6j, and 6k show the AUC, the ACC for non-anomalous groups, and the ACC for the anomalous groups in the third test set. The RBF kernel parameter was computed by [START_REF] Schlkopf | A generalized representer theorem[END_REF] and the regularization parameter was set to λ = 1. The ACC for anomalous groups shows that M2 performs worst detecting the group anomalies, however, such a metric is only based on a threshold of 0 for the output of the models (models outputs greater than zero are anomalies, otherwise are considered non-anomalies). The AUC metric shows that for several choices of thresholds all the models performs pretty well as it is shown in Figure 6i. Again the models with worst performance are M5 and M2, and spherical normalization has a positive effect, increasing the AUC value to one of M3. Performance metrics for the fourth test set has similar characteristics than the third set as it can be seen in Figures 6m, 6n, and6o, where the AUC, the ACC for non-anomalous groups, and the ACC for the anomalous groups are shown. The RBF kernel parameter and the regularization parameter were the same as the above ex-periment. Again, spherical normalization has a positive effect in the AUC metric.

As the group means becomes more spread because characteristics of the fifth test set, AUC metric shows that all the models performs pretty well, nevertheless, M5 is the model with worst performance. Figures 6q, 6r, and6s show the AUC, the ACC for non-anomalous groups, and the ACC for the anomalous groups. The regularization paramter was λ = 1 and the RBF kernel parameter was chosen as [START_REF] Schlkopf | A generalized representer theorem[END_REF] but with s being the 0.9 quantile.

CONCLUSION

In this work, we presented a data description method called SMDD for datasets, where each observation is a set of points in R D . To do that, we considered each observation as a probability measure, thus, the SMDD method finds the MEB of the representer functions of a set of probability measures in a RKHS. The main advantages of our approach is that it does not required an estimation of probabilistic models for each observations, that is, it does not assumed any particular form for the probability density functions of each P i . Instead, everything is done by the embedding of probability measures into RKHS, using a real-valued positive definite kernel on probability measures.

Through the paper, we formulated three SMDD models. The first one uses information of the trace of the covariance operator in a RKHS and mean maps. This model is formulated as a chance constrained program which is further transformed into a deterministic one by means of Markov's inequality. The second SMDD model is a direct extension of the SVDD method to the case of probability measures. This model also uses the mean map embedding of probability measures technique. The third SMDD model is almost the same as the second one, but it considers an scaling of data and translation invariant kernels. The reason behind this, is that mean maps under translation invariant kernels do not have a constant norm in the RKHS. We compared the relationship of the three models, showing the cases when the SMDD models are equivalents, as well.

The presented SMDD models were tested in the challenging group anomaly detection task. We showed empirically that they perform pretty well for such a task, showing that the SMDD method is an alternative methodology to deal with group anomaly detection. SMDD gives a way to perform group anomalous detection by describing a region in the RKHS, given by a MEB of the mean maps of the probability measures used for represent the non-anomalous groups of points. Therefore, mean maps not belonging to the MEB are considered anomalies. As possible practical task to be addressed by SMDD models include novelty detection, clustering and classification, for datasets of probability measures.

INTRODUCTION

In this notes, we provide further details of the paper Support measure data description. We start in Section 2 using an example of a dataset whose observations are Gaussian distribution to understand the formulation of SMDD in the space of probability measures. This section could be read along Section 2 of the paper. In Section 3, we give a list of al the SMDD models in the RKHS presented in the Section 3 of the paper. Section 4 presents a formulation when it is used joint constraints for a SMDD model with chance constraints. In Section 5, we use the linear kernel in two SMDD models and, compare them with the SVDD method. Finally, all the proofs of the paper are presented in Section 6.

Table 1 shows the notation used in this note.

INTERPRETATION OF SMDD IN THE SPACE OF PROBABILITY MEASURES

The following chance-constrained program is the SMDD in the space of probability measures:

Problem 2.1.

min c∈R D ,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to P i ( X i -c 2 ≤ R 2 + ξ i ) ≥ 1 -κ i , ξ i ≥ 0.
for all i = 1, . . . , N , where R and c are the radius and the center of the hypersphere respectively, λ > 0 is a regularization parameter, and the random vector X i ∼ P i is the uncertainty parameter for the chance-constrained model.

i = N (µ i , Σ i ), µ i ∈ R 2
, and Σ i ∈ R 2×2 . The empirical minimum volume set of E given by a enclosing ball is the red circle. As P i is normal, then Z i ∼ χ 2 (Chi-square distribution) with one degree of freedom. The particular cases are: probability measures P 1 and P 4 are the support measures in P. P 5 is the allowed error associated to the slack variable ξ 5 . Probability measures P 2 and P 3 are not critical measures. Figure 1b shows the cumulative Chi-square distribution F Zi , we observe that decreasing κ i has the effect to increase the radius R to cover a particular P i , then κ i values are directly related to the probability mass α in Equation 2 of the paper. Figure 1c shows five different kappa values for P 4 , the values are: {1, 00.8, 0.6, 0.4, 0.2}, we can see that as κ i tends to zero, the radius tends to cover P 4 . The lower bounds 1-κ i for F Zi allow to have a more (if κ i goes to one) or a less conservative (if κ i goes to zero) model to describe a set of probability measures.

Problem 2.1 is futher simplified using Markov's inequality:

tr(Σ i ) + µ i -c 2 R 2 + ξ i ≤ κ i , (1)
min c∈R D ,R∈R,ξ∈R N R 2 + λ N i=1 ξ i subject to µ i -c 2 ≤ (R 2 + ξ i )κ i -tr(Σ i ), ξ i ≥ 0, whose dual is Problem 2.3. max α∈R N N i=1 α i µ i , µ i - N i,j=1 α i α j µ i , µ j N i=1 α i + N i=1 α i tr(Σ i ) subject to 0 ≤ α i κ i ≤ λ, i = 1, . . . , N N i=1 α i κ i = 1
Geometric intepretation of Problem 2.2 Assuming ξ i = 0, 1, 2, . . . , N , for each constraint, we have from (1):

R √ κ i ≥ µ i -c 2 + tr(Σ i ) = µ i -c + tr(Σ i ) -γ i , γ i ∈ R +

LIST OF SMDD MODELS IN A RKHS

We summarize the SMDD models in a RKHS presented in the paper. where

∂ αi L = ( N j=1 α j )2 µ i , N j=1 α j µ j ( N j=1 α j ) 2 - N i=1 N j=1 α i α j µ i , µ j ( N j=1 α j ) 2 -µ i 2 -tr(Σ i ) -ηκ i -ν(κ i -c) = 0 (4)
but for complementarity condition of (2.3) follows that ν i = 0 implies α i > 0, then

∂ αi L = 2 µ i , c -c 2 -µ i 2 -tr(Σ i ) -ηκ i = 0.
Analyzing the KKT's condition of Problem 2.3, we have that α i > 0, β i > 0 =⇒ ξ i = 0 and 0 < α i κ i < λ. From this and KKT's complementarity conditions we can retrieve the radius

R 2 = µ i -c 2 + tr(Σ i ) κ i , (5)
where i ∈ {i ∈ I | 0 < α i κ i < λ}. Thus, follows that η = R 2 , then R = √ η. 2 )

- N i=1 α i { µ Pi , c(.) H -ρ + ξ i - µ Pi 2 H 2 } - N i=1 β i ξ (6)
The optimality (KKT) conditions for this problem are:

∂ ρ L = 0 : N i=1 α i c(.) L = 0 : c(.) - N i=1 α i µ Pi ∂ ξ i L = 0 : λ -α i -β i = 1 0 0    (7)
α i { µ Pi , c(.) H -ρ + ξ i -

µ P i 2 H 2 } β i ξ i = 0 0 (8)
Replacing, ( 7) into (6) yields 1 2 N i=1 (α i -λ) k(P i , P i ) -

Lemma 4 . 3 .

 43 Let η be the Lagrange multiplier of constraint N i=1 α i = 1 of Lagrangian of Problem 4.2, then ρ = η.

Fig. 5 :

 5 Fig. 5: Experimental results and plot of the group means for the two Distribution-based anomaly detection experiments. Each row of figures represent one experiment. Boxplots show the ACC and AUC statistics. Marks on the x-axis of each boxplot are the DD models and y-axis is the performace measure.

Fig. 4 :

 4 Fig. 4: Experimental results and a plot of the group means for the Point-based group anomaly detection experiment. Boxplots show the ACC and AUC statistics. Marks on the x-axis of each boxplot are the DD models and y-axis is the performace measure. Figure 4d plots the means of non-anomalous groups vs. the means of anomalous groups. Red, magenta and blue points are the group means of anomalous groups. Green points are the means of non-anomalous groups

  Means of groups. (m) AUC. (n) ACC Normal. (o) ACC Anomalous. (p) Means of groups. (q) AUC. (r) ACC Normal. (s) ACC Anomalous. (t) Means of groups.

Fig. 6 :

 6 Fig. 6: Experimental results and plots of the means of non-anomalous groups vs. the means of anomalous group for the group anomaly detection task over a SDSS III dataset. Each row of figures represent one experiment.

  (a) Red circle: empirical minimum volume set for {Pi} 5 i=1 given by a minimum enclosing ball in the space of probability measures.

  The cumulative Chi-square distribution (blue curve) shows that decreasing κi has the effect to increase the radius R to cover some Pi. Decreasing κ4 increases the radius R to cover the observation P4.

Fig. 1 to

 1 Fig. 1

  where the last equation comes from the fact that for alla, b ∈ R + ∪ {0}, √ a 2 + b 2 = (a + b) 2 -2ab ≤ a + b, then follows: ∃γ ∈ R + such √ a 2 + b 2 = a+b-γ and replacing a = µ-c and b = tr(Σ) we have the equality.

Figure ( 2 )

 2 shows this interpretation.

Fig. 2 :α

 2 Fig. 2: Geometric interpretation of the deterministic constraints.

  (a) A MV-set given by a minimum enclosing ball from M1 with linear kernel for a kernel on probability measures, joint constraints and λ = 1, for a dataset of Gaussian distributions. Small red circles are the support measures. The means are not on the surface of the ball, because M1 considers the trace of the covariance. (b) A minimum enclosing ball from M2 with linear kernel for a kernel on probability measures and λ = 1, for a dataset of Gaussian distributions. Small red circles are the support measures. Model M2 with this setting is equivalent to a SVDD (M5), trained using only the group means. M2 differs from M1 inthe length of the radius. (c) Dash-dot black circles: Minimum enclosing balls for the group means of a dataset of Gaussian distributions, for several choices of λ in M5 with linear kernel. Red circle: a minimum enclosing ball from M1 with λ = 1 with linear kernel for a kernel on probability measures and λ = 1, for a dataset of Gaussian distributions.

2 = 2 = 2 6. 2 3 The

 22223 Fig. 3

2 Nα

 2 α i α j k(P i , P j ), but -λ i=1 k(P i , P i ) is constant, then, the dual form of the above Problem is given by: i α j k(P i , P j )subject to 0 ≤ α i ≤ λ, i = 1, . . . , N N i=1 α i = 1,

TABLE 2 :

 2 Models used in experiments

TABLE 1 :

 1 Symbols used in the paper.

training set {P i } 5 i=1 , where P

6.3 Proof of Lema 3.1

  E P [ k(X, .) -c(.) 2 ] = E P [ k(X, .), k(X, .) H ] -2 µ P , c(.) H + c(.) 2 H = tr(Σ H ) + µ P 2 H -2 µ P , .c(.) H + c(.) 2 H = tr(Σ H ) + µ P -c(.) 2Changing variables in Problem 3.1 by-ρ = 1 2 (R 2 κtr(Σ H ) -c(.) 2 H ), implies R 2 = (tr(Σ H ) + c(.) 2for all i = 1, . . . , N . Settingξ i = 1 2 (κξ i -µ Pi Pi , c(.) H ≥ ρ -ξ i , i = 1, . . . , N Pi , c(.) H ≥ ρ -ξ i , i = 1, . . . , N Pi , c(.) H ≥ ρ -ξ i + µ Pi

										then, Problem 4.1 could be written as:
										min c(.)∈H,ρ ∈R,ξ ∈R N	c(.) 2 H 2	-ρ + λ	N i=1	(ξ i -	µ Pi 2	2 H	)
										subject to	µ 2 H 2	,
										ξ i ≥ 0,
										H	for all i = 1, . . . , N .
										The Lagrangian for the previously Problem is:
	6.4 Proof of Theorem 4.1	H -	L(c(.), ρ, ξ, α, -β) =	c(.) 2 H 2	-ρ + λ	i=1 N	(ξ i -	µ Pi	2 H
	2ρ))/k, Problem 3.1 becomes:
	min c(.)∈H,R∈R,ξ∈R N		tr(Σ H ) + c(.) 2 H -2ρ k	+ λ	N i=1	ξ i
	subject to				µ Pi , c(.) H ≥ ρ -	1 2	(κξ i -µ Pi	2 H ),
						ξ i ≥ 0,
	ξ i =	2ξ i + µ P i k	2 H		2 H ) implies 2 the objective and multiplying by k
	function gives:
	min c(.)∈H,R∈R,ξ∈R N	1 2	(tr(Σ H ) + c(.) 2 H -2ρ)
						+	k 2	λ	N i=1	2ξ i + µ Pi k	2 H
	subject to µ this is simplified to
	min c(.)∈H,R∈R,ξ∈R N	1 2	(tr(Σ H ) + c(.) 2 H -2ρ)+
						λ	N i=1	ξ i +	1 2	λ	N i=1	µ Pi	2 H
	subject to				µ ξ i ≥ -	µ Pi 2	2 H	, i = 1, . . . , N.
	dropping the constant terms, we arrive at
	min c(.)∈H,R∈R,ξ∈R N		c(.) 2 H 2	-ρ + λ	N i=1	ξ i
	subject to				µ ξ i ≥ -	µ Pi 2	2 H	, i = 1, . . . , N.
	6.5 Proof ot Theorem 4.2
	From (3), if:
		ξ =	1 2	κξ =⇒ ξ = ξ +	µ Pi 2	2 H	,

Pi , c(.) H ≥ ρ -ξ i , i = 1, . . . , N 2ξ i + µ Pi 2 H k ≥ 0, i = 1, . . . , N.

ACKNOWLEDGMENTS

This work was partly done while the first author was visiting the Institute National of Science Appliqués, Rouen-France. The authors would like to thank to FAPESP grant # 2011/50761-2, CNPq, CAPES, NAP eScience -PRP -USP.

M2: SMDD in a RKHS as a direct extension of SVDD

Primal

Dual

Problem 3.3.

α i α j k(P i , P j )

M3: SMDD Model in a RKHS using Mean Maps with Norm One and Invariant Translation Kernels

Problem 3.4.

but with kernel: k(P i , P j ) = k(P i , P j ) k(P i , P i ) k(P j , P j ) ,

M1 WITH JOINT CONSTRAINTS

Primal

Problem 4.1.

where

Dual

Problem 4.2.

α i α j k(P i , P j )

SMDD MODELS WITH LINEAR KERNEL

We examined here the behaviour of M1, M2 and M5 when the linear kernel is used. As we point out in the end of Section 2 of the paper, if the linear kernel is used, M2 is equivalent to a SVDD (M5) trained on the group means, because under that setting, the RKHS will be the same as the input space, consequently mean functions µ P ∈ H will be µ ∈ R D .

The training set was given by 10 groups of points, artificially generated from ten two-dimensional Gaussian distributions. To do that, we set arbitrarily the mean and covariance matrix for each two-dimensional distribution. Elements of the training set are plotted in 3a, 3b and 3c, as several ellipsoids, which are the contours of the probability density function of the local Gaussian distribution, such inner and outer ellipses cover about the 35% and 85% of the probability mass of each local Gaussian distribution, respectively.

Setting the regularization parameter to λ = 1 for M1 and M5, Figure 3a shows a minimum enclosing ball found by M1. The radius does not cross the means of the support measures (small red circles). because M1 to use mean maps, also uses the trace of the covariance operator. Figure 3b shows a minimum enclosing ball found by M2. This model uses only information given by mean maps, consequently, the radius cross the means of the support measures. Therefore, the radius found by M1 is greater than the radius found by M2. The only case, where both radius are equal is where the space of probability Dirac measures are considered, that is, no information about the covariance of P i , as we pointed out in Section 2 of the paper.

Figure 3c shows how by varying the regularization parameter in a SVDD solution is not equal to the solution provided by M1. Dashdot black circles denote several minimum enclosing balls found by M5 (SVDD), each of them obtained by varying the regularization parameter λ to allow {0%, 10%, 20%, 30%, 40 . . . , 90%} of the training data to be errors. This was done by set λ proportionally to 1/(N * q), where N is the number of examples in the training set and q is the percentage of training examples to be considered errors. Red circle in Figure 3c denote the minimum enclosing ball found by M1 with λ = 1 and all κ-values set to one. The minimum enclosing ball obtained from M1 is bigger than the one obtained from M5 in the case of 0% errors allowed, because M1 considers the information given by the trace of local covariances in the training set. We pointed out in the paper that M1 is equivalent to M5 only if all the κ values are ones, and there is no information of local covariance matrices.