Laurent Decreusefond

Ian Flint

Moment formulae for general point processes

Keywords: Point processes, Moments, Stochastic integral, Measure transformation, Malliavin calculus. 1

The goal of this paper is to generalize most of the moment formulae obtained in [Pri11]. More precisely, we consider a general point process µ, and show that the relevant quantities to our problem are the so-called Papangelou intensities. Then, we show some general formulae to recover the moment of order n of the stochastic integral of a random process. We will use these extended results to study a random transformation of the point process.

Introduction

Point processes constitute a general framework used to model a wide variety of phenomena. The underlying theory is well understood, and the relevant literature is abundant (see [START_REF] Daley | An introduction to the theory of point processes[END_REF] and [START_REF] Kallenberg | Random measures[END_REF] for example). However, we have a much deeper understanding of the Poisson point process, which is one of the reasons for its use in a lot of practical cases. In particular, one has a chaos-expansion of Poisson functionals, concentration inequalities, moment formulae, etc. ([Pri11,[START_REF] Privault | Stochastic analysis in discrete and continuous settings with normal martingales[END_REF]) On the other hand, one lacks most of these tools for more general point processes. Our goal is to obtain moment formulae for very general point processes that are only required to have a Papangelou intensity. Intuitively, the Papangerlou intensity c is such that c(x, ξ) λ(dx) is the conditional probability of finding a particle in the vicinity of x, given the configuration ξ (here λ is the reference measure). Historically, the first type of processes satisfying this condition is the Gibbs process. For a Gibbs process, c(x, ξ) = e H(x∪ξ)-H (ξ) , where H is a global energy function, chosen in a suitable class of functions. The interested reader can find further information regarding Gibbs processes in [START_REF] Ruelle | Statistical mechanics: Rigorous results[END_REF][START_REF]Superstable interactions in classical statistical mechanics[END_REF] as well as in [START_REF] Nguyen | Integral and differential characterizations of the Gibbs process[END_REF]. More recently, determinantal processes have been found to have Papangelou intensities under certain conditions (see [START_REF] Georgii | Conditional intensity and Gibbsianness of determinantal point processes[END_REF] as well as [START_REF] Yoo | Gibbsianness of fermion random point fields[END_REF]).

As we have stated previously, our aim is to obtain moment formulae for quite general point processes. Hence, we will follow the path of [Pri12], in which some moment formulae were obtained for the Poisson point process (PPP). In particular, the main result of [Pri12] is the following formula, obtained in the case of the PPP:

E[ u x (ξ) ξ(dx) n ] = {P1,...,P k }∈Tn E E k u |P1| x1 . . . u |P k | x k (ξ ∪ x 1 ∪ • • • ∪ x k ) λ(dx 1 ) . . . λ(dx k ) ,
where T n is the set of all partitions of {1, . . . , n}, |P i | is the cardinality of P i , i = 1, . . . , k, and u : E × X → R is a nonnegative measurable process. The proofs in [Pri12] are mostly based on the use of previous results related to Malliavin calculus (in particular the formula that gives E[δ(u) n ]). In this paper, we generalize all the formulae in [Pri12] to the case of a point processes which has Papangelou intensities (which obviously includes the case of the PPP). Our proofs are mainly based on the Georgii-Nguyen-Zessin formula, and as a consequence, we also obtain analogues of the formula that gives E[δ(u) n ]. In all cases, the difference between the PPP and a general point process is a randomization of the underlying measure λ obtained by multiplying it by c(•, ξ).

Our results also allow us to study random transformations of point processes. In the case of a general point process µ, let us introduce a random transformation τ , such that each particle x of the configuration ξ is moved to τ (x, ξ). Then, we obtain an explicit characterization of τ µ if we only assume that τ is invertible and exvisible (the term will be defined precisely in section 5). An application is to show that the non-random transformation of a dererminantal measure yields another determinantal measure.

The remainder of the article is organized as follows. In section 2, we introduce the basic tools that are used to study point processes. In section 3, we give the main result of the paper, as well as most interesting consequences. In part 4, we show analogue formulae for E[δ(u) n ], where δ is the divergence, which will be rigorously defined in the case of a general point process. To conclude, section 5 will deal with the study of a random transformation of the measure µ.

Notations and general results

2.1. Point processes. Let E be a Polish space, O(E) the family of all non-empty open subsets of E and B denotes the corresponding Borel σ-algebra. λ is a Radon measure on (E, B). Let X be the space of locally finite subsets in E, also called the configuration space:

X = {ξ ⊂ E : |Λ ∩ ξ| < ∞ for any compact Λ ⊂ E}.
In fact, X consists of all positive integer-valued Radon measures such that for all x ∈ E, ξ(x) ≤ 1. Hence, it is naturally topologized by the vague topology, which is the weakest topology such that for all continuous and compactly supported functions f on E, the mapping

ξ → f, ξ := x∈ξ f (x)
is continuous. We denote by F the corresponding σ-algebra. We will call elements of X configurations and identify a locally finite configuration ξ with the atomic Radon measure x∈ξ ε x , where we have written ε x for the Dirac measure at x ∈ E. For a given ξ = x∈ξ ε x , we will usually view ξ as a set, and write ξ ∪ x 0 = ξ ∪ {x 0 } for the addition of a particle at x 0 and ξ \ x 0 = ξ \ {x 0 } for the removal of a particle at x 0 . Moreover, for a measurable nonnegative u : E × X → R, we will often use the notation u x (ξ) ξ(dx) := x∈ξ u x (ξ).

Next, let X 0 = {ξ ∈ X : |ξ| < ∞} the space of all finite configurations on E. X 0 is naturally equipped with the trace σ-algebra

F 0 = F | X0 .
A random point process is defined as a probability measure on (X , F ). A random point process µ is characterized by its Laplace transform, which is defined for any measurable non-negative function f on E as

L(f ) = X e -x∈ξ f (x) µ(dξ).
Now, let us introduce a number of measures useful in the study of point processes. Our notations are inspired by that of [START_REF] Georgii | Conditional intensity and Gibbsianness of determinantal point processes[END_REF], where the reader can also find a brief summary of many properties of Papangelou intensities.

Definition 1. We define the λ-sample measure L on (X 0 , F 0 ) by the identity

f (α) L(dα) = n≥0 1 n! E n f ({x 1 , . . . , x n }) λ(dx 1 ) . . . λ(dx n ),
for any measurable nonnegative function f on X 0 .

Point processes are often characterized via their correlation function, defined as below.

Definition 2 (Correlation function). A point process µ is said to have a correlation function ρ : X 0 → R if ρ is measurable and

X α⊂ξ, α∈X0 f (α) µ(dξ) = X0 f (α) ρ(α) L(dα),
for all measurable nonnegative functions f on X 0 . For ξ = {x 1 , . . . , x n }, we will sometimes write ρ(ξ) = ρ n (x 1 , . . . , x n ) and call ρ n the n-th correlation function, where here ρ n is a symmetrical function on E n .

It can be noted that correlation functions can also be defined by the following property, both characterizations being equivalent in the case of simple point processes.

Proposition 2.1. A point process µ is said to have correlation functions (ρ n ) n∈N if for any A 1 , . . . , A n disjoint bounded Borel subsets of E,

E[ n i=1 ξ(A i )] = A1ו••×An ρ n (x 1 , . . . , x n ) λ(dx 1 ) . . . λ(dx n ).
Recall that ρ 1 is the mean density of particles with respect to λ, and

ρ n (x 1 , . . . , x n ) λ(dx 1 ) . . . λ(dx n )
is the probability of finding a particle in the vicinity of each x i , i = 1, . . . , n.

Let us now define the so-called Campbell measures:

Definition 3 (Campbell measures). The reduced Campbell measure of a point process µ is the measure C µ on the product space (E × X , B ⊗ F ) defined by

C µ (A × B) = x∈ξ 1 A (x)1 B (ξ \ x) µ(dξ),
where A ∈ B and B ∈ F . We define similarly the reduced compound Campbell measure of a point process µ is the measure Ĉµ on the product space (X 0 ×X , F 0 ⊗F ) defined by

Ĉµ (A × B) = α⊂ξ, α∈X0 1 A (α)1 B (ξ \ α) µ(dξ),
where A ∈ F 0 and B ∈ F .

The results in this paper can be obtained under the assumption C µ ≪ µ, but we will work under a slightly stronger condition in order to find more compact results. We will thus assume throughout this paper that the following condition is fulfilled:

Hypothesis 1 (Condition (Σ λ )). The point process µ is assumed to satisfy condi- tion (Σ λ ), i.e. C µ ≪ λ ⊗ µ.
Henceforth, any Radon-Nikodym density c of C µ relative to λ ⊗ µ is called a version of the Papangelou intensity of µ.

The preceding assumption also implies that Ĉµ ≪ L⊗µ and we will thus similarly denote any Radon-Nikodym density of Ĉµ relative to L ⊗ µ by ĉ. One then has for any ξ ∈ X , ĉ(∅, ξ) = 1, as well as for all x ∈ E, ĉ(x, ξ) = c(x, ξ). Moreover, the following commutation relationship is also verified:

(1) ∀ξ, η, ν ∈ X , ĉ(ν, η ∪ ξ) ĉ(η, ξ) = ĉ(ν ∪ η, ξ).
Hypothesis 1, along with the definition of the reduced Campbell measure, allows us to write the following important identity, known as the Georgii-Nguyen-Zessin identity:

(2)

X x∈ξ u(x, ξ \ x) µ(dξ) = X E u(x, ξ) c(x, ξ) λ(dx)µ(dξ),
for all measurable nonnegative functions u : E × X → R. We also have a similar identity for all measurable nonnegative functions u : X 0 × X → R:

(3)

X α⊂ξ, α∈X0 u(α, ξ \ α) µ(dξ) = X E u(α, ξ) ĉ(α, ξ) λ(dx)µ(dξ),
Combining relation (2) and the definition of the correlation functions, we find

E[c(x, ξ)] = ρ 1 (x),
for almost every x ∈ E. We also find more generally, using (3), that

(4) E[ĉ(α, ξ)] = ρ(α),
for almost every α ∈ X 0 .

Let us continue by giving some examples of point processes satisfying assumption 1.

Example (Poisson process). Let us start by considering the well-known Poisson

process with intensity z with respect to λ, noted π zdλ , defined for example via its Laplace transform as follows:

L π zdλ (f ) = e -(1-e -f (x) ) z(x)λ(dx) .
In that case, (Σ λ ) is verified and we have c(x, ξ) = z(x), for any x ∈ E and ξ ∈ X , and the Georgii-Nguyen-Zessin identity reads

X x∈ξ u x (ξ \ x) π zdλ (dξ) = X E u x (ξ) z(x) λ(dx)π zdλ (dξ),
which is a well known result in the Poisson case (known as the Campbell-Mecke identity). Recall that the Poisson measure has a correlation function defined by

ρ π zdλ (ξ) = x∈ξ z(x), ξ ∈ X .
One can notice that ρ 1 (x) = z(x), x ∈ E, which is also equal to c(x, ξ). Indeed, recall that c(x, ξ) λ(dx) is interpreted as the probability of finding a particle in the differential region dx, conditionally on ξ. For the Poisson process, the conditioning by ξ does not add any information and thus the probability is also equal to ρ 1 (x) λ(dx).

Moment formulae

Let us start by proving a simple combinatorial lemma. F P 1 , . . . , P l-1 , P l ∪ {n + 1}, P l+1 , . . . , P k .

Proof. Let us consider the functions (Ξ k ) 1≤k≤n+1 defined as follows.

Ξ k : T k n+1 -→ T k n ∪ T k-1 n , {P 1 , . . . , P k } -→ {P 1 , . . . , P l-1 , P l \ {n + 1}, P l+1 , . . . , P k },
where 1 ≤ l ≤ k is such that {n + 1} ∈ P l . Moreover, let us define the function Ξ as

Ξ : T n+1 -→ T n , P -→ Ξ |P| (P),
where T n is the set of all partitions of {1, . . . , n}. Then, Ξ is surjective from T n+1 into T n and moreover, for P = {P 1 , . . . , P |P| } ∈ T n , we have that

Ξ -1 (P) = P ∪ {n + 1} ∪ |P| l=1 P 1 , . . . , P l ∪ {n + 1}, . . . , P |P| .
Then, using the preceding observations, we obtain

n+1 k=1 P∈T k n+1 F (P) = P∈Tn+1 F (P) = P∈Tn P={P1,...,P |P| } F (P ∪ {n + 1}) + |P| l=1 F ( P 1 , . . . , P l ∪ {n + 1}, . . . , P |P| ),
which is the desired result once we sum on the different lengths possible for elements of T n .

We can now give the first important result of this paper, which will yield many cases of particular interest.

Theorem 3.1. For any n ∈ N, any measurable nonnegative functions u k : E ×X → R, k = 1, . . . , n, and any bounded function F on X , we have

E[F n k=1 u k (y, ξ) ξ(dy)] = n k=1 P∈T k n E E k F (ξ ∪ x)u P (x, ξ ∪ x)ĉ(x, ξ) λ k (dx) ,
where T k n is the set of all partitions of {1, . . . , n} into k subsets. Here, for P = {P 1 , . . . , P k } ∈ T k n , we have used the compact notation x = (x 1 , . . . , x k ), as well as λ k (dx) = λ(dx 1 ) . . . λ(dx k ) and

u P (x, ξ) = k l=1 i∈P l u i (x l , ξ).
Proof. We will prove this result by induction on n. Let u : E × X → R be a measurable nonnegative function. First note that by the Georgii-Nguyen-Zessin identity (2), we have

E[F (ξ) u(y, ξ) ξ(dy)] = E[ F (ξ ∪ x)u(x, ξ ∪ x) c(x, ξ) λ(dx)].
Now, for n ∈ N * , let u 1 , . . . , u n+1 be nonnegative measurable functions on E × X . We have by induction:

E[F n+1 k=1 u k (y, ξ) ξ(dy)] = E[F (ξ) n k=1 u k (z, ξ) u n+1 (y, ξ) ξ(dy) 1/n ξ(dz)] = n k=1 P∈T k n E E k F (ξ ∪ x)u P (x, ξ ∪ x)ĉ(x, ξ) u n+1 (z, ξ ∪ x){ξ ∪ x}(dz)λ k (dx) .
Here, the last part can be rewritten

u n+1 (z, ξ ∪ x){ξ ∪ x}(dz) = u n+1 (z, ξ ∪ x) ξ(dz) + k l=1 u n+1 (x l , ξ ∪ x).
Hence, after regrouping the terms, we find

E[F n+1 k=1 u k (y, ξ) ξ(dy)] = n k=1 P∈T k n k l=1 E E k F (ξ ∪ x)u P (x, ξ ∪ x)u n+1 (x l , ξ ∪ x) ĉ(x, ξ) λ k (dx) + n k=1 P∈T k n E E k F (ξ ∪ x)u P (x, ξ ∪ x) u n+1 (z, ξ ∪ x) ξ(dz) ĉ(x, ξ) λ k (dx) .
Then, by Fubini's theorem, and the Georgii-Nguyen-Zessin formula (2), the second sum is equal to

E E k F (ξ ∪ x)u P (x, ξ ∪ x) u n+1 (z, ξ ∪ x) ξ(dz) ĉ(x, ξ) λ k (dx) = E E k+1 F (ξ ∪ x ∪ z)u P (x, ξ ∪ x ∪ z)u n+1 (z, ξ ∪ x ∪ z)ĉ(x, ξ ∪ z)c(z, ξ)λ k (dx)λ(dz) = E E k+1 F (ξ ∪ x ∪ z)u P (x, ξ ∪ x ∪ z)u n+1 (z, ξ ∪ x ∪ z) ĉ(x ∪ z, ξ) λ k (dx)λ(dz) = E E k+1 F (ξ ∪ x)u P∪{n+1} (x, ξ ∪ x) ĉ(x, ξ) λ k+1 (dx) ,
since by (1), we know that ĉ({x 1 , . . . , x k }, ξ ∪ y) c(y, ξ) = ĉ({x 1 , . . . , x k , y}, ξ). To summarize, we have found

E[F n+1 k=1 u k (y, ξ) ξ(dy)] = n k=1 P∈T k n k l=1 E E k F (ξ ∪ x)u P (x, ξ ∪ x)u n+1 (x l , ξ ∪ x) ĉ(x, ξ) λ k (dx) + E E k+1 F (ξ ∪ x)u P∪{n+1} (x, ξ ∪ x) ĉ(x, ξ) λ k+1 (dx) ,
and we obtain the desired result by applying lemma 3.1.

The previous quite general property includes many interesting cases. In particular, if all u k , k = 1, . . . , n are equal, one generalizes the results in [Pri11] and obtains the moments of u x (ξ) ξ(dx) : Corollary 3.1. For any n ∈ N, any measurable nonnegative function u : E × X → R; and any bounded function F on X , we have

E[F u(y, ξ) ξ(dy) n ] = n k=1 {P1,...,P k }∈T k n E E k F (ξ ∪ x 1 ∪ • • • ∪ x k ) k l=1 u |P l | (x l , ξ ∪ x 1 ∪ • • • ∪ x k )ĉ({x 1 , . . . , x k }, ξ) λ(dx 1 ) . . . λ(dx k ) ,
where

|P i | is the cardinality of P i , i = 1, . . . , k.
This result includes the case where u x (ξ) = v(x) is a deterministic function:

Corollary 3.2. For any n ∈ N, and any measurable nonnegative function v on E, we have

E[F v(y) ξ(dy) n ] = n k=1 {P1,...,P k }∈T k n E k v(x 1 ) |P1| . . . v(x k ) |P k | E[F (ξ ∪ x 1 ∪ • • • ∪ x k )ĉ({x 1 , . . . , x k }, ξ)] λ(dx 1 ) . . . λ(dx k ).
The previous corollary yields

Cov F, ( v(x) ξ(dx)) n = n k=1 {P1,...,P k }∈T k n E k v(x 1 ) |P1| . . . v(x k ) |P k | E[(F (ξ ∪ x 1 ∪ • • • ∪ x k ) -F (ξ))ĉ({x 1 , . . . , x k }, ξ)] λ(dx 1 ) . . . λ(dx k ).
The case of F = 1 is also of particular interest:

Corollary 3.3. For any n ∈ N, any measurable nonnegative non-random functions

v k : E → R, k = 1, . . . , n, we have E[ n k=1 v k (y) ξ(dy)] = n k=1 {P1,...,P k }∈T k n E k i∈P1 v i (x 1 ) • • • i∈P k v i (x k ) ρ({x 1 , . . . , x k }) λ(dx 1 ) . . . λ(dx k ).
Note that we recover here a classical formula, which reads for n = 1, 2, 3:

E[ v(x) ξ(dx)] = E v(x)ρ 1 (x) λ(dx), E[ v(x) ξ(dx) 2 ] = E v(x) 2 ρ 1 (x) λ(dx) + E 2 v(x)v(y)ρ({x, y}) λ(dx)λ(dy), E[ v(x) ξ(dx) 3 ] = E v(x) 3 ρ 1 (x) λ(dx) + 3 E 2 v(x) 2 v(y)ρ({x, y}) λ(dx)λ(dy) + E 3 v(x)v(y)v(z)ρ({x, y, z}) λ(dx)λ(dy)λ(dz).
The previous corollary is interesting in itself because it is in fact an equivalent characterization of the existence of correlation functions. More precisely, we have the following result:

Proposition 3.1. Let (ρ k ) k∈N be a family of symmetrical, measurable functions, and ρ k : E k → R for k ∈ N. Assume moreover that the measure µ is simple, in the sense that P(ξ(x) ≤ 1) for all x ∈ E. Then, the measure µ possesses correlation functions (ρ k ) k∈N (with respect to λ) if and only if, for any n ∈ N, and any measurable nonnegative functions v k : E → R, k = 1, . . . , n, we have

E[ n k=1 v k (x) ξ(dx)] = n k=1 {P1,...,P k }∈T k n E k i∈P1 v i (x 1 ) • • • i∈P k v i (x k ) ρ k (x 1 , . . . , x k ) λ(dx 1 ) . . . λ(dx k ).
Proof. Assume that we have

X α⊂ξ, α∈X0 f (α) µ(dξ) = X0 f (α) ρ(α) L(dα),
where f is any measurable nonnegative function on X 0 . Then, for k ∈ N,

X α⊂ξ, |α|=k f (α) µ(dξ) = 1 k! E k f ({x 1 , . . . , x k }) ρ k (x 1 , . . . , x k ) λ(dx 1 ) . . . λ(dx k ).
Now, we can write for n ∈ N and ξ ∈ X , x1,...,xn∈ξ

v 1 (x 1 ) . . . v n (x n ) = n! n k=1 {P1,...,P k }∈T k n α⊂ξ, |α|=k α={x1,...,x k } i∈P1 v i (x 1 ) . . . i∈P k v i (x k ),
where the n! appears since when we write {x 1 , . . . , x k } ⊂ ξ, we only choose ordered subsets of ξ. Then, we find the desired result by taking the expectation of the previous equality. Indeed, we have by definition

E α⊂ξ, |α|=k α={x1,...,x k } i∈P1 v i (x 1 ) • • • i∈P k v i (x k ) = 1 n! E E k i∈P1 v i (x 1 ) • • • i∈P k v i (x k )ĉ({x 1 , . . . , x k }, ξ) λ(dx 1 ) . . . λ(dx k ). ,
and we conclude by using (4). On the other hand, assume that there exists some symmetrical measurable functions (ρ k ) k∈N , such that for any n ∈ N, and any measurable nonnegative functions

v k : E → R, k = 1, . . . , n, we have E[ n k=1 v k (y) ξ(dy)] = n k=1 {P1,...,P k }∈T k n E k i∈P1 v i (x 1 ) . . . i∈P k v i (x k ) ρ k (x 1 , . . . , x k ) λ(dx 1 ) . . . λ(dx k ). Let A 1 , . . . , A n be n disjoint Borel subsets of E. Take v k = 1 A k , k = 1, . . . , n.
Then, the different terms of the right-hand side sum are all equal to 0, except for the subdivision consisting of only singletons. Hence,

E[ n k=1 ξ(A k )] = A1ו••×An ρ k (x 1 , . . . , x n ) λ(dx 1 ) . . . λ(dx n ),
which means that µ has correlation functions (ρ k ) k∈N since µ is a simple point process.

Extended moment formulae for the divergence

The aim of this section is to obtain analogue formulae involving the divergence of a general operator. Let us now start by defining a new random measure ν by the formula

f (y, ξ) ν(dy) = f (y, ξ) ξ(dy) -f (y, ξ)c(y, ξ) λ(dy), for f on E × X such that E[ E |f (y, ξ)|c(y, ξ) λ(dy)] < ∞.
In order to ensure the rest of the results in this section, we will need to make another assumption on µ which will be assumed to hold henceforth.

Hypothesis 2. We assume that the moments of the point process µ are all finite, i.e. that for all ϕ bounded, compactly supported function, and for all n ∈ N,

E[ ϕ(x) ξ(dx) n ] < ∞.
By corollary 3.3 the previous condition can be rewritten as

∀n ∈ N, Λ n ρ n (x 1 , . . . , x n ) λ(dx 1 , . . . , dx n ) < ∞,
for all compacts Λ of E. Then, we prove the following:

Proposition 4.1. We assume that hypothesis 2 is verified. Then, for any n ∈ N, any bounded process u : E × X → R with compact support on E, and any bounded function F on X , we have

E[F u(y, ξ) ν(dy) n ] = n i=0 (-1) i n i n k=1 {P1,...,P k }∈T k n-i E E k ĉ(x, ξ)F (ξ ∪ x) k l=1 u(x l , ξ ∪ x) |P l | u(z, ξ ∪ x)c(z, ξ ∪ x) λ(dz) i λ k (dx) .
Proof. This is a direct consequence of the binomial formula

E[F u(y, ξ) ν(dy) n ] = n i=0 (-1) i n i E F u(y, ξ) ξ(dy) n-i u(y, ξ)c(y, ξ) λ(dy) i ,
and thus we obtain the desired result by applying proposition 3.1.

Recall that the associated formula for π 1 (the Poisson process of intensity λ), as obtained in [Pri11], is

E π 1 [F u(y, ξ) ν(dy) n ] = n i=0 (-1) i n i n k=1 {P1,...,P k }∈T k n-i E π 1 E i+k F (ξ∪{x 1 ∪• • •∪x k }) k l=1 u |P l | (x l , ξ ∪ x 1 ∪ • • • ∪ x k ) i+k l=k+1 u(x l , ξ ∪ x 1 ∪ • • • ∪ x k ) λ(dx 1 ) . . . λ(dx i+k ) .
Here, by comparison, the general formula can be written as

E[F u(y, ξ) ν(dy) n ] = n i=0 (-1) i n i n k=1 {P1,...,P k }∈T k n-i E E i+k G k ({x 1 , . . . , x i+k }, ξ)F (ξ ∪ {x 1 ∪ • • • ∪ x k }) k l=1 u |P l | (x l , ξ ∪ x 1 ∪ • • • ∪ x k ) i+k l=k+1 u(x l , ξ ∪ x 1 ∪ • • • ∪ x k ) λ(dx 1 ) . . . λ(dx i+k ) .
where

G k ({x 1 , . . . , x i+k }, ξ) = ĉ({x 1 , . . . , x k }, ξ)c(x i+1 , ξ ∪ x 1 ∪ • • • ∪ x k ) . . . c(x i+k , ξ ∪ x 1 ∪ • • • ∪ x k ) = k l=1 c(x l , ξ ∪ x 1 ∪ • • • ∪ x l ) i+k l=i+1 c(x l , ξ ∪ x 1 ∪ • • • ∪ x k ).
Let us now introduce the so-called divergence operator δ.

Definition 4 (Divergence operator). For any measurable u :

E × X → R such that E[ |u(y, ξ)| c(y, ξ) λ(dy)] < ∞, we define δ(u) as δ(u) = u(y, ξ \ y) ν(dy) = u(y, ξ \ y) ξ(dy) -u(y, ξ) c(y, ξ) λ(dy).
We can notice that the divergence of a bounded process u is correctly defined since for such a process,

E[ |u(y, ξ)| c(y, ξ) λ(dy)] ≤ C E[ c(y, ξ) λ(dy)] = 1.
The next proposition gives a moment formula for this newly introduced operator. Proposition 4.2. For any n ∈ N, any bounded process u : E × X → R, with compact support on E, and any bounded function F on X , we have

E[F δ(u) n ] = n i=0 (-1) i n i n k=1 {P1,...,P k }∈T k n-i E E i+k G k ({x 1 , . . . , x i+k }, ξ)F (ξ ∪ {x 1 , . . . , x k }) i+k l=k+1 u(x l , ξ∪{x 1 , . . . , x k }) k l=1 u |P l | (x l , ξ∪{x 1 , . . . , xl , . . . , x k })λ(dx 1 ) . . . λ(dx i+k ) ,
where, G k is the function defined in the previous paragraph. The notation {x 1 , . . . , xl , . . . , x k } stands for {x 1 , . . . , x l-1 , x l+1 , . . . , x k }.

Proof. Recall that by definition,

E[F δ(u) n ] = E[F v(y, ξ) ν(dy) n ],
where v(y, ξ) = u(y, ξ \ y), for (y, ξ) ∈ E × X . Therefore, we can apply proposition 4.1, and we obtain the desired result.

The previous definition of the operator δ is justified by the duality formula with respect to the difference gradient, defined below.

Definition 5 (Difference operator). For F : X → R, we define DF , the difference operator applied to F , as follows:

DF : E × X -→ R (x, ξ) -→ D x F (ξ) = F (ξ ∪ x) -F (ξ \ x).
Then, the previous definition of δ satisfies the following corollary of proposition 4.2.

Corollary 4.1 (Duality relation).

For any bounded function F on X , and a process u : (x, ξ) → u(x, ξ) in Dom(δ), we have

E[F δ(u)] = E[ E D z F (ξ)u(z, ξ)c(z, ξ) λ(dz)].
Here, we say that a process u : (x, ξ) → u(x, ξ) belongs to Dom(δ) whenever there exists a constant c such that for any F ∈ L 2 (µ),

X E D z F (ξ)u(z, ξ) C µ (dz, dξ) ≤ c F L 2 (µ) .
Recall that in the Poisson case, C µ = λ ⊗ µ and we recover the classical duality relationship.

One also finds an extended Skorohod isometry in the case of a more general point process (see [START_REF]An introduction to the theory of point processes[END_REF]):

Corollary 4.2. E[δ(u) 2 ] = E[ u(y, ξ) 2 c(y, ξ) λ(dy)] + E[ u(y, ξ ∪ z) u(z, ξ ∪ y) -2u(z, ξ) ĉ({y, z}, ξ) λ(dy)λ(dz)] + E[ u(y, ξ)c(y, ξ) λ(dy) 2 ].
5. Random transformation of the point process 5.1. Exvisibility. The goal of this section is to give an application of the previous moment formulae. As was explained in the introduction, we wish to study a random transformation of the point process measure µ. The main condition that enables us to study the random transformation in depth is that of exvisibility (to our knowledge, this notion was first introduced in [START_REF]An introduction to the theory of point processes[END_REF]). We will start by recalling the definition of exvisibility as well as most of the main properties.

Definition 6 (Exvisibility). Define the exvisible σ-algebra Z to be the σ-algebra generated by sets of the form B × U , B ∈ B, U ∈ F B c . A stochastic process is said to be exvisible if it is measurable with respect to Z on E × X .

In particular, let us introduce what we will call simple exvisible processes:

Definition 7 (Simple exvisible process). We call simple exvisible process a stochastic process of the form

u(x, ξ) = N i=1 1 Ai (x)F i (ξ),
where N ∈ N, A 1 , . . . , A N ∈ B and the F i are F A c i -measurable for i = 1, . . . , N . This notion is important because of the following proposition: Proposition 5.1. A stochastic process is exvisible if and only if it is the limit of simple exvisible processes, i.e. there exists a sequence (A n k ) of subdivisions of E, and

F A c i -measurable (F n k ) such that ∀x ∈ E, ∀ξ ∈ X , u(x, ξ) = lim n k 1 A n k (x)F n k (ξ (A n k ) c ).
Let us also recall the following property of exvisible processes.

Proposition 5.2. For u an exvisible process, we have

∀x ∈ E, ∀ξ ∈ X , D x u(x, ξ) = 0. Proof. Assume that u is of the type u(x, ξ) = 1 A (x)F (ξ A c
), where A ∈ B and F is a measurable function on X . We can write

D x u(x, ξ) = 1 A (x) F ((ξ ∪ x) A c ) -F (ξ A c ) = 0, since (ξ ∪ x) A c = ξ A c , when x ∈ A.
The result then follows from the monotone class theorem.

The following proposition will also be of particular interest:

Proposition 5.3. Let u : E × X → R be an exvisible process. Then, it holds that

D x1 u(x 2 , ξ) . . . D x k-1 u(x k , ξ)D x k u(x 1 , ξ) = 0,
for k ≥ 2, (x 1 , . . . , x k ) ∈ E and ξ ∈ X . More generally, we can easily prove that for k ≥ 2,

k l=1 u(x l , ξ ∪ x 1 ∪ • • • ∪ x k ) n l = k l=1 u(x l , ξ) n l ,
for all (x 1 , . . . , x k ) ∈ E, ξ ∈ X , and (n 1 , . . . , n k ) ∈ N k .

Proof. We will start by proving the first part. Let us consider an exvisible process u, as well as k ≥ 2, (x 1 , . . . , x k ) ∈ E and ξ ∈ X . Then,

k l=1 D x l u(x l+1 , ξ) = I,J⊂{1,...,k}, I∩J=∅ i∈I u(x i+1 , ξ ∪ x i ) j∈J (-u(x j+1 , ξ)),
where we have used the convention

x k+1 = x 1 . Now, if we assume that u is of the form u(x, ξ) = 1 A (x)F (ξ A c ), we have k l=1 D x l u(x l+1 , ξ) = I,J⊂{1,...,k}, I∩J=∅ 1 A k (x 1 , . . . , x k ) i∈I F ((ξ ∪ x i ) A c ) j∈J (-F (ξ A c )) = I,J⊂{1,...,k}, I∩J=∅ 1 A k (x 1 , . . . , x k ) i∈I F (ξ A c ) j∈J (-F (ξ A c )) = 0.
Hence, the same holds for any exvisible u by the monotone class theorem. The generalization follows by the same arguments.

Exvisibility is in fact similar to adaptedness for processes on the real line. We can even reformulate the Skorohod isometry (corollary 4.2) in order to draw the parallel between point processes and processes on the real line :

E[δ(u) 2 ] = E[ u(y, ξ) 2 c(y, ξ) λ(dy)] + E[ D z u(y, ξ)D y u(z, ξ)ĉ({x, y}, ξ) λ(dy)λ(dz)] -E[ u(z, ξ)u(y, ξ)c(z, ξ)D z c(y, ξ) λ(dy)λ(dz)].
This particular way of writing the formula is useful since when u is exvisible, D z u(y, ξ)D y u(z, ξ) = 0 for a.e. x, y ∈ E and ξ ∈ X , and therefore the second term is zero. Moreover, one would have the expected Skorohod isometry E[δ(u) 2 ] = E[ u(y, ξ) 2 c(y, ξ) λ(dy)] if and only if c(y, ξ) = c(y, ξ ∪ z) for a.e. (y, z) ∈ E 2 and a.e. ξ ∈ X , i.e. if c does not depend on the configuration ξ.

Hence, µ would therefore necessarily be a PPP in this case (see [START_REF] Mecke | Stationäre zufällige Masse auf lokalkompakten Abelschen Gruppen[END_REF]).

5.2. Random transformations. Now, let us consider a random shifting τ : E × X → E. For ξ ∈ X , consider the image measure of ξ by τ , which we will call the random transformation τ * (ξ), defined as

τ * (ξ) = x∈ξ δ τ (x,ξ) ,
and thus τ * shifts each point of the configuration in the direction τ . We will say that τ * is exvisible if τ is. Now, we wish to study the effect of the the transformation on the underlying measure µ under sufficiently strong conditions on τ . The following hypotheses will be considered:

(H1): The random transformation τ * is exvisible, in the sense defined previously in this section. (H2): For a.e. ξ ∈ X , τ (•, ξ) is invertible, and we will note its inverse τ -1 (x, ξ), x ∈ E, ξ ∈ X . We will also denote by τ -1 * (ξ) the image measure of ξ by τ -1 . Theorem 5.1. Let τ : E × X → E be a random shifting as defined previously, and satisfying (H1) and (H2). Let us assume that τ maps λ to σ, i.e. τ (•, ξ)λ = σ, ξ ∈ X , where σ is a fixed measure on (E, B). Then, τ * µ has correlation functions

(5) ρ τ (x 1 , . . . , x k ) = E ĉ({τ -1 (x 1 , ξ), . . . , τ -1 (x k , ξ)}, ξ) , x 1 , . . . , x k ∈ E,
with respect to σ.

Proof. Our aim for the proof is to use proposition 3.1 (characterization of correlation functions). By proposition 3.1, we have for any n ∈ N, any measurable nonnegative (non-random) functions v k : E → R, k = 1, . . . , n, we have

E τ * µ [ n k=1 v k (y) ξ(dy)] = n k=1 {P1,...,P k }∈T k n E µ E k ĉ({x 1 , . . . , x k }, ξ) k l=1 i∈P l v i (τ (x l , ξ ∪ x 1 ∪ • • • ∪ x k )) λ(dx 1 ) . . . λ(dx k ) = n k=1 {P1,...,P k }∈T k n E µ E k ĉ({x 1 , . . . , x k }, ξ) k l=1 i∈P l v i (τ (x l , ξ)) λ(dx 1 ) . . . λ(dx k ) = n k=1 {P1,...,P k }∈T k n E µ E k ĉ({τ -1 (x 1 , ξ), . . . , τ -1 (x k , ξ)}, ξ) k l=1 i∈P l v i (x l ) σ(dx 1 ) . . . σ(dx k ) ,
where the second equality follows from (H1) and proposition 4.1. By proposition 3.1, we conclude that τ * µ has correlation functions (with respect to σ), which are given by ρ τ (x 1 , . . . , x k ) = E ĉ({τ -1 (x 1 , ξ), . . . , τ -1 (x k , ξ)}, ξ) , x 1 , . . . , x k ∈ E, since the previous functions are obviously symmetrical (by symmetry of ĉ(•, ξ) as a function on E n ), and since an invertible transformation of a simple point process µ yields another simple process (allowing us to apply proposition 3.1).

This theorem directly generalizes all known results. Indeed, consider the following corollary:

Corollary 5.1. Let µ = π dλ be the Poisson measure with intensity λ. Let τ : E × X → E be a random transformation satisfying (H1) and (H2). Let us assume that τ maps λ to σ, i.e. τ (•, ξ)λ = σ, ξ ∈ X . Then, τ maps π dλ to π dσ .

Proof. The corollary follows directly from the theorem, since π dλ has a Papangelou intensity of 1. Therefore, τ * π dλ has intensity σ and its correlation functions, given by (5), are also equal to 1.

We also recover some previously known results of quasi-invariance in the case of the determinantal random measure. Let us start by introducing determinantal point processes, and recalling some well-known facts. The interested reader can find further results concerning determinantal processes in [START_REF] Hough | Determinantal processes and independence[END_REF][START_REF] Shirai | Random point fields associated with certain Fredholm determinants. II. Fermion shifts and their ergodic and Gibbs properties[END_REF]. We define a Hilbert-Schmidt operator K from L 2 (E, λ) to L 2 (E, λ) satisfying the following conditions:

(i): K is a bounded symmetric integral operator on L 2 (E, λ), and we also write K(•, •) for its kernel. (ii): The spectrum of K is included in [0, 1[ (Here, we exclude 1 in order to ensure the existence of Papangelou intensities). (iii): K is of locally trace class.

Under these conditions, we define (µ K , λ) to be the (unique) measure with intensity λ and correlation functions ρ(x 1 , . . . , x n ) = det K(x i , x j ) 1≤i,j≤n (existence and uniqueness of point processes with given correlation functions are discussed in [Len75a, Len75b], see as well [START_REF] Soshnikov | Determinantal random point fields[END_REF] for the case of determinantal processes). We further define the operator J, called the global interaction operator, as J := K(I -K) -1 . Since we assumed that ||K|| < 1, J is properly defined as a bounded operator. We will also define J [Λ] := K Λ (I -K Λ ) -1 , where we will be wary of the fact that J [Λ] is not the restriction of J to Λ, but rather J applied to the operator K Λ . In order to ensure the existence of the Papangelou intensities, let us introduce the following condition on the operator J:

(H3):

• J has a continuous integral kernel.

• J has finite range R < ∞.

• µ does not percolate.

Here, (H3) was the condition introduced in [GY05] to ensure the existence of Papangelou intensities for the point process once we are not limited to the compact Λ. More precisely, it was shown that under (H3), the determinantal process with global interaction operator J satisfies condition (Σ λ ), i.e. it admits Papangelou intensities c K . These intensities are well defined for the measure µ K,Λ (restriction of µ to Λ) as c K,Λ (x, ξ) = det J [Λ] (ξ∪x)

det J [Λ] (ξ) , x ∈ E, ξ ∈ X . Here, the notation J [Λ] (ξ) stands for J [Λ] (x i , x j ) 1≤i,j≤n where ξ = {x 1 , . . . , x n } ∈ X . However, the main result of [START_REF] Georgii | Conditional intensity and Gibbsianness of determinantal point processes[END_REF] is that (µ K , λ) also satisfies condition (Σ λ ) under condition (H3), and c K is explicitly given by the formula:

c K (x, ξ) = det J(ξ W ∪ x) det J(ξ W ) 1 diam W (x,ξ)<∞ ,
where W (x, ξ) is the union of the clusters of B R (x ∪ ξ) hitting x and ξ W := ξ W (x,ξ) . With these preliminaries in mind, we can apply our previous results.

Corollary 5.2. Let µ K be the determinantal measure with intensity λ and kernel K. Assume that the associated operator J satisfies (H3). Let τ : E × X → E be a transformation satisfying (H1) and (H2). Let us assume that τ maps λ to σ, i.e. τ (•, ξ)λ = σ, ξ ∈ X . Then, τ * µ K has correlation functions given by (6) ρ τ (x 1 , . . . , x k ) = E det J(ξ W ∪ {τ -1 (x 1 , ξ), . . . , τ -1 (x k , ξ)}) det J(ξ W ) , x 1 , . . . , x k ∈ E, and where W is the union of the clusters of B R ({τ -1 (x 1 , ξ), . . . , τ -1 (x k , ξ)} ∪ ξ) hitting {τ -1 (x 1 , ξ), . . . , τ -1 (x k , ξ)}. Moreover, if we further assume that τ is a non-random, invertible transformation, and define

T : L 2 (σ) -→ L 2 (λ), f -→ f • τ.
Then, τ maps (µ K , λ) to (µ Kτ , σ), where K τ = T -1 KT .

Proof. The first part of the corollary is a direct consequence of theorem 5.1. If we further assume that τ is non-random, then by (4), we have ρ τ (x 1 , . . . , x k ) = ρ(τ -1 (x 1 ), . . . , τ -1 (x n )) = det K(τ -1 (x i ), τ -1 (x j )) 1≤i,j≤n .

Its then remains to notice that the kernel K τ = T -1 KT is again an integral operator with kernel K τ (x, y) = K(τ -1 (x), τ -1 (y)), x, y ∈ E.

Remark. If we do not assume that τ is non-random, then there is no reason for ρ τ to be given by the determinant of a Hilbert-Schmidt operator K ′ . Therefore, τ * µ K is not necessarily determinantal in the general case of a random shift τ .

We can note that the last part of the corollary is another formulation of the quasiinvariance results obtained in [START_REF] Camilier | Quasi-invariance and integration by parts for determinantal and permanental processes[END_REF]. The study in the aforementioned paper was limited to determinantal processes on a compact Λ. On such a compact, (H3) is obviously satisfied and we therefore have the existence of Papangelou intensities.

Lemma 3. 1 .

 1 Let F be a function from the power set P(N) to R. Then for n ∈ N * , ...,P k }∈T k n F P ∪ {n + 1} + n k=1 P={P1,...,P k }∈T k n k l=1


Chongsheng Zhang
email: chongsheng.zhang@yahoo.com

Florent Masseglia
email: florent.masseglia@inria.fr

Xiangliang Zhang
email: xiangliang.zhang@kaust.edu.sa

Discovering Highly Informative Feature Set Over High Dimensions

For many textual collections, the number of features is often overly large. These features can be very redundant, it is therefore desirable to have a small, succinct, yet highly informative collection of features that describes the key characteristics of a dataset. Information theory is one such tool for us to obtain this feature collection. With this paper, we mainly contribute to the improvement of efficiency for the process of selecting the most informative feature set over high-dimensional unlabeled data. We propose a heuristic theory for informative feature set selection from high dimensional data. Moreover, we design data structures that enable us to compute the entropies of the candidate feature sets efficiently. We also develop a simple pruning strategy that eliminates the hopeless candidates at each forward selection step. We test our method through experiments on real-world data sets, showing that our proposal is very efficient.

I. INTRODUCTION

Feature selection is the task of selecting interesting or important features, and removing irrelevant or redundant ones. It has been widely used in many application fields, such as discriminative gene selection [START_REF] Jaeger | Improved gene selection for classification of microarrays[END_REF] and text categorization [START_REF] Yang | A comparative study on feature selection in text categorization[END_REF]. Before selecting the features, an interestingness measure should be defined to assess the significance of the features or featuresets (i.e. feature sets). For instance, if the interestingness is measured by a given utility function, we select feature sets with the best (highest or lowest) utility scores. Given the measurement for the feature sets, one can design efficient algorithms to search for the best feature sets, where wrapper and filter [START_REF] Liu | Computational Methods of Feature Selection (Chapman & Hall/Crc Data Mining and Knowledge Discovery Series)[END_REF] are the commonly used methods.

Besides the interestingness measures, feature selection is closely related to the characteristics of the data itself. Feature selection techniques for labeled data are rather different from those for unlabeled data [START_REF] Guyon | An introduction to variable and feature selection[END_REF]. For unlabeled data, we do not have class as references and feature selection always depends on the applications and tasks. For example, when choosing the top-k most important keywords from large documents, the tf -idf method [START_REF] Salton | Introduction to Modern Information Retrieval[END_REF] can be used to measure the weight of each keyword; when finding a feature set that contains the most information, one can resort to information theory based feature selection methods [START_REF] Heikinheimo | Finding low-entropy sets and trees from binary data[END_REF], [START_REF] Knobbe | Maximally informative k-itemsets and their efficient discovery[END_REF]. Example 1 addresses the problem of feature selection for document retrieval.

Example 1: We would like to retrieve documents from table I, in which the columns of {O 1 , ..., O 10 } are 10 documents,

O9 O10 A 1 1 1 1 1 0 0 0 0 0 B 0 1 0 0 1 1 0 1 0 1 C 1 0 0 1 0 1 1 0 1 0 D 1 0 1 1 1 1 1 1 1 1 E 1 1 1 1 1 1 1 1 1 1
and the attributes of {A, B, C, D, E} are some features (key words) in the documents, where the value "1" means that the feature is contained in the document, and "0" not. It is easy to find that (D, E) is a frequent featureset, because features D and E occur together in nearly every document. However, it provides little help for document retrieval. By contrast, (A, B, C) is an infrequent featureset, as its member features rarely or never appear together in the data. And it is troublesome to summarize the value patterns of featureset (A, B, C). Providing it with the values < 1, 0, 0 > we could find the corresponding document O 3 ; similarly, given the values < 0, 1, 1 > we will have the according document O 6 . Although (A, B, C) is infrequent, it contains lots of useful information which is hard to summarize. We call it an informative feature set.

From the above example, we can see that it is useful to discover informative feature sets. Indeed, information theory provides strong support to measure the informativeness of the feature sets. But for unlabeled data, it requires computing the joint probability not just for the case when all the features have appeared together, but also for all the other cases when some features have appeared in the transactions but others have not. This is an exhaustive work. To tackle this problem, the authors in [START_REF] Knobbe | Maximally informative k-itemsets and their efficient discovery[END_REF] proposed an effective and efficient method for selecting the informative feature sets over low-dimensions. However, this algorithm does not scale well for high-dimensions.

In this paper, we investigate the problem of efficient discovery of most informative feature set over unlabeled highdimensional data. This is a very challenging task. First, there are d! k!×(d-k)! candidate feature sets having k features, k is a user-specified parameter denoting the size of the feature set that s/he expects, and d is the data dimension. Because of the high dimensions, the number of candidates increases greatly w.r.t. d. Second, due to the characteristics of informative feature sets, we have to compute for each candidate feature set, the probability for every existing case of feature composition in all the transactions, and there are up to 2 k possible cases of feature combinations. If the number of transactions is n, we need as many as n * 2 k computations for each candidate feature set. Overall, we need n * 2 k * d! k!×(d-k)! calculations for all the candidates. This is very computation-demanding.

To solve the above problem, we propose a heuristic theory. Exploiting the fact that usually only a few features are correlated in most textual collections, our heuristic theory i) divides the features into independent and dependent sets and ii) reduces the candidate features for informative feature sets to a rather small subset. Upon this theory, we introduce a forward selection algorithm that discovers the most informative feature set based on the selected features. Moreover, we design a data structure that speeds up the computation of the entropies of the candidate featuresets. We also introduce a pruning strategy that helps filter out the unpromising candidate featuresets. Based on all our proposal, we build a framework IIS (Feature Independence based Informative featureset Selection). Experiments on real-world datasets show that our method can save 90% computation time comparing with the algorithm from the literature.

The remaining of this paper is organized as follows. In section II, we discuss the related work about feature selection. After giving the related definitions in section III, we introduce the theory for feature set mining and give our algorithm and two optimization techniques, as well as the concrete IIS framework in section IV. We evaluate our work in section V. Finally, we conclude and give perspectives in section VI.

II. RELATED WORK

Feature selection is a very important tool for many data mining applications. In [START_REF] Liu | Computational Methods of Feature Selection (Chapman & Hall/Crc Data Mining and Knowledge Discovery Series)[END_REF] we find a systematic review of the foundations, techniques and applications of existing feature selection methods. This paper focuses on selecting the most informative feature set over high-dimensional unlabeled data. We therefore discuss the related work referring the keywords of informative feature set, high-dimensional data and unlabeled data.

Informative feature set selection on unlabeled data has been studied in recent years. Knobbe et al. in [4] proposed a heuristic algorithm to extract informative featureset of size k with the highest entropy. Such featuresets are called miki. The proposed ForwardSelection algorithm performs multiple scans over the dataset. Within each scan, miki's size gradually increases, by adding a new feature f to the miki at current iteration. They showed the advantage of ForwardSelection over the brute force algorithms that evaluate the entropies of all the possible subsets of size k. Afterwards, method for low entropy feature set discovery was also investigated. In [START_REF] Heikinheimo | Finding low-entropy sets and trees from binary data[END_REF], Heikinheimo et. al. proposed two algorithms designed to extract the sets of both low entropy and high entropy featuresets from static datasets. In [START_REF] Zhang | Discovering highly informative feature sets from data streams[END_REF], we extended miki to work on streaming data with transient features and proposed to reduce its candidates by removing similar sets according to mutual information criteria. But these methods become inefficient in high-dimensions, because we will have huge candidate feature sets to check in high-dimensions, and for each candidate we have to calculate the counts and compute the probability for all appeared feature combinations, including the ones where some features appeared but others did not. Our work aims to speed up the searching and computation for most informative feature set.

There are many approaches in feature selection for highdimensional data. But most of them are towards labelled data. Yu and Liu [START_REF] Yu | Feature selection for high-dimensional data: A fast correlation-based filter solution[END_REF] use the class concept as the reference and identify all predominant features which are most capable to predict class concept. The proposed method is based on discovering pair uncertainty correlation with the class concept and other features. They only considered the pair correlationship, but the cases that several features jointly decide the class concept have not been considered. Our work is about informative feature set selection over unlabeled and high dimensional data, and the task is to find the feature set with highest joint uncertainty, whereas the features can be dependent or independent of others. FastANOVA [START_REF] Zhang | Fastanova: an efficient algorithm for genome-wide association study[END_REF] was designed for joint association discovery, but strong association (or correlation) within a feature set does not imply a high information (i.e. joint entropy) contained in the feature set. In fact, even though the features in the set are weakly associated, their joint entropy can be very high.

III. DEFINITIONS

Preliminary Definitions. We refer to book [START_REF] Thomas | Elements of Information Theory[END_REF] for the preliminary definitions of entropy, joint entropy of a feature set, mutual information and relevance coefficient. Let H(X) denote the entropy of feature X, and H(I) represent the joint entropy of featureset I. The mutual information between two discrete variables can be computed by Formular 1. The Relevance Coefficient (RO) between two features is measured by Formula 2. Features A and B are independent if RO(A, B) = 0; A and B are mutually redundant if RO(A, B) = 1.

M I(AB) = H(A) + H(B) -H(AB)

(1)

RO(A, B) = M I(A, B) M IN {H(A), H(B)} (2)
To relax the conditions of feature independence and redundancy, we introduce the following definition and equation to measure the relationship between two features, using a lower bound threshold ξ and a upper bound threshold δ.

Definition 1: The relationship between two features depends on their RO value.

A and B are

     independent, if RO(A, B) < ξ; redundant, if RO(A, B) > δ; relevant, otherwise (3)
Now let us define the highly/most informative feature set. Definition 2: Given a size k, the Highly/Most Informative Featureset (HI) is the featureset that has the largest entropy value among all the candidates having size k, as given by formula 4.

H(HI) = M AX{H(IS k ), IS k ∈ SS k } (4)
where

IS = {I 1 , I 2 , ..., I n } is the set of all n possible features, IS k = {I m1 , I m2 , ..., I m k } is a featureset of size k (k < n), SS k = {IS k } is the set of all possible featuresets of size k.
Problem Definition. In this paper, we aim at discovering the most informative featureset over high-dimensional unlabeled dataset. Given such high dimensions, our approach should reduce the search space and be as effective as possible.

IV. INFORMATIVE FEATURESET SELECTION OVER HIGH DIMENSIONS

In this section, we first introduce a heuristic theory that forms the foundation of our framework. Then we present the MIFS forward feature selection algorithm. We next introduce two techniques to speed up the searching and computation for highly informative featureset. Finally, we introduce the IIS framework.

A. The Heuristic Feature Reduction Theory

Before illustrating the theory, we first give some basic ideas and concepts. k is a user input parameter, denoting the size of the expected informative feature set. In our theory, we perform the following steps:

1) Sort the features by entropy; 2) Evaluate independence between features, and categorize them into dependent and independent sets; 3) Fetch the top-k features from the independent sets and put them into BRFSet (Brief Reference Feature Set); 4) Get all the features which rank higher than the last feature in BRFSet, and insert them into MiniSet (Minimum candidate feature Set). 5) Considering some features in MiniSet could have correlated features, we maintain MaxSet to include both MiniSet and all the features which are correlated with features in it;

Finally, our theory limits the search space of informative feature sets to MaxSet, so we can perform informative feature set selection methods on MaxSet. We explain the reasons for choosing MaxSet in the following.

We first refer to the following theorem in [START_REF] Thomas | Elements of Information Theory[END_REF].

Theorem 1: If and only if variables X 1 ,X 2 , ..., X n-1 ,X n are mutually independent, then

H(X 1 , X 2 , ..., X n-1 , X n ) = n i=1 H(X i ) (5)
If the condition in theorem 1 is satisfied, it will be simple to compute the joint entropy. Otherwise, we claim the following inference.

Lemma 1: andX m , 1 ≤ m ≤ n, is independent of any of the features in S, but the features in S are not necessarily mutually independent. Then

If S = {X 1 ,X 2 , ..X m-1 ,X m+1 ... X n-1 ,X n },
H(X 1 , X 2 , ..X m-1 , X m , X m+1 ....X n-1 , X n ) = H(X m ) + H(X 1 , X 2 , ..X m-1 , X m+1 ...X n-1 , X n ) (6)
Proof: The reason is that X m is not independent of S. Let us take a small example of three variables A, B and C. In table II, the left part is the data, and the right part is the joint probability of these three features.

Judging from the joint probability of (A,B) and (A,C), we can see that A and B, A and C are independent respectively. However, this is not the case for (A,B,C). Actually,

P (A = 0, B = 1, C = 0) = 1/4, whereas P (A = 0) = 1/2, P (B = 1, C = 0) = 1/4 Thus, P (A = 0, B = 1, C = 0) = P (A = 0) × P (B = 1, C = 0). So A is not independent of (B,C).
Bases on Theorem 1 and Lemma 1, we infer the importance of independence among features as expressed in Lemma 2.

Lemma 2: We can not use Theorem 1 unless all the features in the given set are mutually independent. Otherwise, it is unreliable because of Lemma 1.

In practice, in many real-world high-dimensional datasets, only a few features are correlated, most of them are independent. Therefore, we can safely rely on Theorem 1 to compute the joint entropy for a feature set comprising mutually independent features. When the feature sets include part of the dependent features, theorem 1 can not be used directly. However, it can still be used to estimate the bounds for the joint entropies of the feature sets, such that some unpromising candidates can be filtered out first. Next, for the remaining candidate sets, we still need to compute the exact joint entropy values. Therefore, we introduce Lemma 3 in IIS.

Lemma 3: Let f s be a subset of size k from MaxSet. f s can never become the most informative featureset, if its maximum entropy is lower than BRFSet.

Proof: Suppose we have two candidates, fs and BRFSet. Because the features in BRFSet are top-K mutually independent features, the joint entropy of BRFSet will be the sum entropy of the individual features according to theorem 1. As f s's entropy is lower than that of BRFSet, we will choose BRFSet as the most informative featureset.

Given the above lemmas and discussions, we finally provide the following Heuristic Feature Reduction Theory: the most informative feature set is more likely to be a subset from MaxSet. This heuristic theory can be illustrated in three folds. In the first place, the most informative feature set from the independent set is BRFSet. BRFSet is the last and reference candidate we have. We can see from lemma 3 that if the upper bound of a featureset's entropy is smaller than the entropy of BRFSet, it can be safely discarded. Next, features in {M axSet -BRF Set} already contain all the top-ranked dependent features and their correlated ones, from which we can select a subset of most informative featuresets. Finally, now that each feature in BRFSet is independent of any other feature in MaxSet, it is more likely that the one from BRFSet, instead of the remaining independent features, will contribute more to the joint entropy of a featureset. In subsection IV-E, we will build the IIS framework based on this theory.

A B C 0 1 0 1 0 0 0 0 1 1 1 1 A (B,C) (0,0) (0,1) (1,0) (1,

B. MIFS: Mining Highly Informative Featureset

With the above heuristic feature reduction theory, we can greatly reduce the number of features for highly informative featureset discovery. Even so, we may still have a very large number of candidates. Let d denote the number of features, n is the number of transactions and k is the size of features set, the number of candidate sets having size k is:

nc = d! k! × (d -k)! (7)
For instance, if d = 40, k = 20, then nc = 1.3785 × 10 11 . Therefore we can not afford to enumerate all the candidates of size k, instead, we have to resort to the heuristic algorithms for the consideration of efficiency. Our proposed feature selection algorithm is named MIFS. Initially, the top two features are the pair features with the largest joint entropy. We insert them into a set mifs. Then iteratively, we first check the first feature f in {M axSet -M IF S}. If f and features in mifs are mutually independent, then we simply add f to mifs; otherwise, based on the current mifs and f , we generate all the possible candidates having size i. At the end of this round, for all the candidates, we scan the data to compute their exact entropy values and find a feature subset Maxsubset (of size i) with the largest entropy value. In the next iteration i + 1, we vacuum the candidate features in the iteration i. i gradually increases from 2 to k, and after k-2 iterations, we will have the final highly informative feature set mifs of size k.

C. Selecting Only the Promising Featuresets

In this part we present a strategy which can help us filter out the unpromising featuresets at each iteration in the above MIFS algorithm, based on Lemma 3. We compare the bounds of each candidate feature set with the bounds the reference. Initially, the reference set is the top-i features in BRFSet, i is the current iteration number in algorithm MIFS. Let lb and ub denote the lower and upper bounds. There are 6 cases we need to consider. Bounds comparison is simple so we skip the comparison details. The final strategy is: candidates whose entropy upper bounds are lower than lb will be discarded without consideration; all existing candidates will be removed when there is a featureset whose entropy lower bound is larger than ub, and this featureset will be considered as the new reference; in the rest cases we update lb or ub correspondingly.

D. MFI Data Structure: Pattern Mapping and Feature Indexing for feature selection

The complexity of the MIFS algorithm is |k| * |m| * |n|, where k is the size of the feature set, |m| is the total number of features in MaxSet, |n| is the size of the data. We find that we have to scan the data several times, which is costly. In order to reduce the cost, we make a data structure MFI to help us efficiently find the related records. We maintain two kinds of data structures in MFI:

(i) A pattern map/table which summarizes all the appeared feature sets and their counts, if two users share the same feature sets, then the count for the pattern in the map is 2;

(ii) Feature indices which keep all the ids of the patterns containing this feature. Note that, as we give an order of the patterns by their first occurrence time, the pattern ids in each feature index are monotone increasing. This monotonic feature facilitates the search and merge of ids from different indices. Example 2: Data management in MFI. In Figure 1 (1) we have the transactions in the data, and the data structure for storing and identifying the complete patterns is given in Figure 1 (2). Figure 1 (3) is the indices for different features of A, B, C and D. Each time we read a transaction, we check whether the feature set of the object already exists in the pattern map.

If yes, we increase the count for the pattern by 1. Otherwise, we first insert the feature set in the pattern map with pid as the identifier, then add the new pid to the end of related indices. For instance, for the red color transaction T 12 , because the pattern (A, C) does not exist in the pattern map, we insert the pattern. Next we insert the according pattern id in indices for features A and C. When we are incrementally searching for the most informative feature set, at each step, we need to compute the entropy of all the new feature subsets which are generated by adding one feature to the current most informative feature subset. There we need MFI to quickly find the relevant records.

Example 3: Efficient Computations of Entropy in MFI. Let (A, B) be the most informative feature subset in the current round. In the following round, we will have to compute the entropy of (A, B, C) and the combination of (A, B) with either of the remaining features. Owing to our index, when computing the entropy of featureset (A, B, C), we do not have to navigate all the records, instead, all we need to check are patterns kept in index A, B, or C. Thus the computation cost on the entropy will be greatly cut.

According to Formula 7, the search space rapidly increases with the number of features. Thus, the larger the data and the number of features, the more useful MFI is.

E. The IIS Framework

We build the IIS framework that implements our informative feature sets discovery theory proposed in sub-session IV-A, generates featureset candidates from MaxSet using MIFS described in sub-session IV-B, then removes unpromising candidates using techniques in subsection IV-C. When computing the exact entropies of the remaining techniques, it utilizes techniques in sub-session IV-D. MIFS stops when the length of the selected feature set is k.

V. EXPERIMENTS Data Set. We use two kinds of real-world datasets in the experiments: Web logs kept by the server at our research institute, and data from a Telecom that maintains the portal visits made by the clients using their mobile devices. The information of the datasets are depicted in Table III in which the first 3 datasets belongs to the Web log dataset and the rest are part of Telecom dataset . There the field of users denotes the number of unique users appeared in the dataset, but one user could request different pages at separate transactions, so we summarize the transactions by users. Parameter Setting. There are two thresholds for relevance and redundancy, and one user-specified parameter: k, which is the size/length of the feature set. Regarding the thresholds, ξ is set to 0.01, and the value for δ is 0.99. We tested different parameters, and these two values are empirical ones.

We use MIKI from [START_REF] Knobbe | Maximally informative k-itemsets and their efficient discovery[END_REF] as the reference for evaluating the informative feature set mining problem. For efficiency, we use CPU time as the criteria. For evaluating the quality of the algorithms, we use the selected feature sets and their entropy values as the standards. We first look at the selected features, if they are the same, then both algorithms are considered having the same effectiveness. Otherwise, we will check the according entropies, and the one with higher entropy is deemed superior. Results of WWW datasets. (A), (B) and (C) in table IV show the experimental results on dataset1, dataset2 and dataset3. In table IV (A), the "selected features" field denotes the selected informative feature sets, given different k values (because the names of the features are long URL addresses, we only unique ids to represent them). The terms such as "+17" mean that the new selected features (e.g. k = 6) are composed of feature 17 and the previous result (e.g. k = 5). We have the following observations from the results.

(I)No matter how the value of k varies, the selected features and their respective entropy of IIS is always the same as MIKI. This observation verified our heuristic theory. For example, when k is 10, the feature sets discovered by MIKI and IIS are the same, and so it does with the according entropy values.

(II)No matter how the value of k varies, IIS is always much more efficient than MIKI. We can see that for WWW datasets, IIS saves up to 90% of the time cost by MIKI. As an example, when k is 15, MIKI takes 898 seconds to get the result, but IIS only uses 90 seconds.

(III) For the same dataset, when k increases, it takes much more time to have the final results. MIKI suffers a lot when k increases, but the case is much more better for IIS.

The above observations still hold for dataset2 and dataset3. We also observe that when k is the same, the more features a dataset has, the longer time it takes. Because the more features we have, the more candidates need to be evaluated. But since IIS limits the candidate features to a small subset, it suffers less than MIKI. For instance, for the results when k is 30 on dataset2 and dataset3, the computation time for MIKI increased by 38.2%, but IIS only increased 28.2%. Results of Telecom datasets. We also tested IIS on Telecom datasets, which have much more features than WWW datasets. (D), (E), and (F) in table IV show the results of both algorithms on dataset4, dataset5 and dataset6. Similar to the results of WWW datasets, the selected features and entropy are always the same for both algorithms, but IIS uses less time. For example, when k = 5, MIKI uses 3641 seconds on testdata5, but our approach only uses 52 seconds, which is 1.4% of that for MIKI. It is clear that when the number of features is very large, IIS is much more efficient.

VI. CONCLUSIONS AND FUTURE WORK

In this paper, we proposed a heuristic theory to reduce the dimension for informative feature set discovery from high dimensions. We also introduced structures and a strategy to accelerate the computation of exact entropy of the candidates and prune hopeless featuresets. In the future work we will investigate how to adapt our method to high-dimensional streaming data.

Fig. 1 .

 1 Fig. 1. Indexing the High-dimensional Data

TABLE II THE

 II JOINT DISTRIBUTION (LEFT) AND PROBABILITY (RIGHT) OF A, B AND C

TABLE IV RESULTS

 IV OF WWW (A,B,C) AND Telecom (D,E,F) DATASETS

							(A) DATASET1
			K			MIKI				IIS
				time(s) selected features	entropy time(s) selected features	entropy
			5	141	2 4 11 18 20	0.4866	12	2 4 11 18 20	0.4866
			6	192	+17		0.5588	16	+17		0.5588
			7	247	+25		0.6284	21	+25		0.6284
			8	307	+13		0.6954	27	+13		0.6954
			9	377	+51		0.7582	33	+51		0.7582
			10	448	+24		0.8164	41	+24		0.8164
			15	898	+1 15 21 31 37	1.0560	90	+1 15 21 31 37	1.0560
			20	1502	+27 29 30 44 64 1.2303	164	+27 29 30 44 64 1.2303
			25	2255	+7 8 23 41 54	1.3576	266	+7 8 23 41 54	1.3576
			30	3094	+10 19 39 42 50 1.4510	398	+10 19 39 42 50 1.4510
	(B) DATASET2						(C) DATASET3
	K		MIKI			IIS		K		MIKI	IIS
		time(s) entropy value	Time	entropy value		time(s) entropy value Time	entropy value
	5	301	0.44826	23	0.44826		5	410	0.450336	37	0.450336
	6	408	0.516571	34	0.516571		6	556	0.516729	51	0.516729
	7	524	0.580686	46	0.580686		7	719	0.582751	67	0.582751
	8	655	0.640754	60	0.640754		8	894	0.642691	84	0.642691
	9	803	0.699638	75	0.699638		9	1096	0.701557	105	0.701557
	10 957	0.753519	92	0.753519		10	1313	0.754748	128	0.754748
	15 1934	0.9719		209	0.9719		15	2648	0.972163	276	0.972163
	20 3271	1.13181	380	1.13181		20	4486	1.13377	497	1.13377
	25 4888	1.24471	615	1.24471		25	6748	1.2476	792	1.2476
	30 6800	1.3296		912	1.3296		30	9403	1.33378	1169	1.33378
							(D) DATASET4
			K			MIKI				IIS
				time(s) selected features	entropy time(s) selected features	entropy
			5	1560	14 17 24 28 60	0.8596	31	14 17 24 28 60	0.8596
			6	2108	+21		0.9284	42	+21		0.9284
			7	2716	+15		0.9943	55	+15		0.9943
			8	3367	+37		1.0446	69	+37		1.0446
			9	4110	+40		1.0849	85	+40		1.0849
			10	5187	+20		1.1245	102	+20		1.1245
			15	7649	+19 27 36 56 72 1.2890	180	+19 27 36 56 72 1.2890
	(E) DATASET5						(F) DATASET6
	K		MIKI			IIS		K		MIKI	IIS
		time(s) entropy value	Time	entropy value		time(s) entropy value Time	entropy value
	5	3641	0.956659	52	0.956659		5	4327	0.753494	54	0.753494
	6	4939	1.01765	71	1.01765		6	5859	0.814299	74	0.814299
	10 9333	1.19006	173	1.19006		10 10949	0.981289	177	0.981289

This work has been conducted and funded when the first two authors were members of the AxIS team at INRIA Sophia Antipolis.