Julie Bu Daher
email: julie.bu-daher@loria.fr

Armelle Brun
email: armelle.brun@loria.fr

Handling Item Similarity in Behavioral Patterns through General Pattern Mining

Modeling human behavior on the Web is often performed by sequential pattern mining (SPM). However, the similarity between data elements often results in the decrease of the number of patterns mined. This work proposes to handle this similarity by managing multiple data sources representing different views of the data. We introduce G SPM, a behavioral pattern mining algorithm that takes advantage of multi-source data to handle the problem of data similarity. It adopts a selective mining strategy to limit the complexity and forms general patterns to limit the decrease of the patterns.

Experimental results confirm that G SPM succeeds in handling the problem of item similarity. In addition, G SPM outperforms traditional approaches in terms of runtime and redundancy of the resulting set of patterns.

I. INTRODUCTION

Nowadays, a significant amount of data is available over the Web. By analyzing these data, we can discover knowledge, extract links between data elements, predict future data, etc. For example, from the customers' traces of activities on an ecommerce website, it is possible to identify frequent purchase behaviors. Obtaining such behavior-related information is the focus of Web usage mining [START_REF] Raphaeli | Analyzing online consumer behavior in mobile and pc devices: A novel web usage mining approach[END_REF] that has attracted attention during the last two decades [START_REF] Aldekhail | Application and significance of web usage mining in the 21st century: a literature review[END_REF]. Sequential pattern mining, is a key task in data mining. It aims at identifying frequent patterns in data, under the form of sequences of items or itemsets that occur frequently in the data. In Web usage mining, such patterns are behavioral patterns.

Some data characteristics could lead to the loss of possibly interesting patterns and thus could limit the number of frequent patterns mined. This is particularly the case of the similarity that could exist between certain data items. This similarity results in the occurrence of several patterns representing the same behavior. The behavior could be frequent; however, as its frequency is distributed among several patterns, this could result in the infrequency of these patterns and thus their loss. Let us consider an example of two sequential patterns, p 1 and p 2 , representing customers' purchase patterns mined from the log file of an e-commerce website. p 1 = i 47 , i 25 , i 1 , i 19 and p 2 = i 47 , i 25 , i 2 , i 19 , with supports of 7 and 8 respectively where i v is an item id. If the minimum support to consider a pattern as frequent is set to 10, p 1 and p 2 are not frequent. However, we can see that p 1 and p 2 only differ by items i 1 and i 2 , both at position 3. Supposing that i 1 and i 2 are stainless steel scissors of 8.3 inches, where i 1 is a green one and i 2 is a purple one, it is clear that these patterns represent the same general purchase behavior. We can thus consider that both patterns are similar, and they are infrequent due to the similarity between i 1 and i 2 . The actual purchase pattern is p = i 47 , i 25 ,"stainless steel scissors 8.3 inches", i 19 . p encompasses p 1 and p 2 , and p is frequent as its support is equal to at least the sum of the supports of p 1 and p 2 . We call p a general pattern, and p 1 and p 2 are original patterns. We define a general pattern as a frequent pattern that encompasses a set of similar but infrequent original patterns. Mining general patterns allows to limit the decrease in the number of frequent patterns. However, a general pattern is less precise than an original one. For this reason, frequent patterns will directly be part of the final output, while only infrequent patterns are considered for forming general ones.

Obviously, general patterns cannot be mined from a log file as the descriptions of the items are not part of such data. However, data on the Web can be collected from multiple sources, where each source can represent data from a specific viewpoint. Putting these data together results in a heterogeneous and multi-source dataset and we consider that it can be used to handle the problem of item similarity. An example of a 3-source dataset in relation with the previous example is as follows. A first data source contains the traces of the activities of the customers on the website. A second data source contains descriptive data of customers collected from their customer accounts on the website: age, gender, preferences, etc. A third data source contains descriptive data of products that can be purchased: brand, size, expiry date, etc. Each source thus provides data related to a specific perspective about the retail website: purchase activity, customers or items.

The traditional pattern mining literature either integrates data sources together or mines sources separately. The first approach allows mining general patterns but is highly complex and mined redundant patterns, while the second approach cannot form general patterns. In this work, we propose an in-between approach that mines data sources selectively. Referring to the previous example, the source containing customers' behavior is denoted the main source and is used to mine original patterns. The other sources provide data about customers or products and are denoted additional sources and can be used to form general patterns.

We thus propose G SPM, a General Sequential Pattern Mining algorithm, that manages multiple sources to cope with the problem of item similarity. It is designed to 1) limit the complexity of the mining process by relying on a selective mining, 2) mine general patterns, while controlling the level of generality of the mined patterns. This paper is organized as follows. Section 2 reviews the literature in the domain. Section 3 introduces G SPM. Section 4 is dedicated to the experimental evaluations of G SPM. Section 5 concludes this work and draws future perspectives.

II. RELATED WORK

A. Sequential Pattern Mining

Pattern mining consists of discovering interesting, useful, and unexpected patterns in large databases [START_REF] Han | Data mining: concepts and techniques[END_REF]. Pattern mining has attracted much attention and a particular emphasis has been given to sequential pattern mining that considers the ordering of elements in a sequential database [START_REF] Fournier-Viger | A survey of sequential pattern mining[END_REF]. A sequential database is made up of a set of sequences where a sequence is an ordered list of itemsets.

The interestingness of a pattern is usually defined as its frequency (support), i.e. the number of sequences in which it appears. The patterns with a support greater than a predefined minimum support min sup are considered as frequent patterns. The sequential pattern mining (SPM) domain is very active where many algorithms have been proposed. They mainly differ in the way they cross the search space: depthfirst or breadth-first search, and in the representation of the database: horizontal, vertical or projected. PrefixSpan [START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefixprojected pattern growth[END_REF], and SPAM [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF] are popular SPM algorithms. These algorithms are designed to mine a sequential database formed by a unique database. However, data is not always that simple.

B. Multi-* Data Mining

Not only voluminous amounts of data are created and collected on a daily basis on the Web, but they also can be provided by various data sources. Each data source can represent a specific data dimension or data table. The literature uses several terms to refer to such databases We propose to refer to such data as multi- * data.

1) Multi-source data: Multi-source data represent data collected from several data sources. Each source provides one or more kinds of data with similar or different structures; The data provided by different sources can have homogeneous or heterogeneous structures.

2) Multi-dimensional data: In multi-dimensional data, each data element is made up of several fields, where one field represents a feature, an attribute, or a dimension [START_REF] Aggarwal | Data mining: the textbook[END_REF]. One dimension is often either a data sequence or a set of descriptive attributes. The most popular work proposes two mining strategies [START_REF] Pinto | Multidimensional sequential pattern mining[END_REF]. They differ in the priority given to the dimensions in the mining process: sequential or descriptive dimension mined first, as well as in the way they are then attached to each other.

3) Multi-relational data: The term multi-relational data is used in the relational database domain for data provided by multiple database tables (relations) and linked through some of their attributes [START_REF] Džeroski | Multi-relational data mining: an introduction[END_REF]. The algorithms mainly either combine tables and perform a global process or use id-list propagation to mine itemsets from different tables without combining them. The first approach is complex and generates a huge number of patterns, while the second approach does not support data of heterogeneous kinds nor it supports mining sequential data.

C. Typology of Relations Among Data Sources

To the best of our knowledge, no specific focus has been made on the nature of the relations between tables or data sources and on their impact on the mining process and the mined patterns. There is an exception in the domain of context-based sequential pattern mining, where [START_REF] Ziembiński | Algorithms for context based sequential pattern mining[END_REF] introduces two types of contexts: the sequence context that provides contextual data to a whole data sequence, and the element context that provides contextual data to each element in the sequence. We choose to exploit these two types of context for determining two kinds of relations between data sources in multi-source data. Figure 1 presents both types of relations for the dataset from the introduction. One data source is sequential and represents customer behavior (main source). It is related to two additional sources, which represent customer and item description, with different types of relations. 1) The Complementary Relation: A complementary relation connects an element of a sequence of the main source with an element of an additional source which is close to the element context from [START_REF] Ziembiński | Algorithms for context based sequential pattern mining[END_REF]. As displayed in Figure 1, the elements in both sources represent an item id where it is a primary key in the descriptive source of items and foreign key in the sequential source. We refer to this relation as a complementary relation as it complements elements of the sequence. This additional source is thus called a complementary source. Notice that if both sources are integrated, it will result in a traditional sequential database, made up of sequences of itemsets (in this case item ids with the description of items).

2) The Contextual Relation: A contextual relation connects the id of a sequence of the main source with the same id in the additional source which is close to the sequence context from [START_REF] Ziembiński | Algorithms for context based sequential pattern mining[END_REF]. In Figure 1, the element of the additional source is the customer id. If sources are integrated, it results in a multi-dimensional source containing descriptive and sequential dimensions. We refer to this relation as a contextual relation as the additional source can be considered as providing contextual information to the sequence. This additional source is thus called a contextual source.

D. Item Similarity Mining

In the data mining literature, pattern mining in the context of similar items is a problem that has received little interest. We found two frames in which this problem has been considered: text mining and multi-database mining. In text mining, [START_REF] Simanovsky | Mining text patterns for synonyms extraction[END_REF] aims to extract synonym terms from a text collection. The proposed approach relies on the identification of common synonym patterns, i.e. word sequences used to connect a phrase and its synonym. In multi-database mining, [START_REF] Zhang | Mining globally interesting patterns from multiple databases using kernel estimation[END_REF] proposes to identify synonym customers, where the same customer is represented by different ids in different databases, by comparing the elements that describe them in each database. However, to the best of our knowledge, the specific problem of mining similarities in pattern mining has not been addressed.

III. G SPM: A GENERAL SEQUENTIAL PATTERN MINING ALGORITHM THAT HANDLES ITEM SIMILARITY

The similarity between items in the data leads to a decrease in the support of some patterns and thus to a limited number of mined patterns. In order to handle this problem, G SPM is designed to mine general sequential patterns by relying on the item-related complementary data source.

Before presenting G SPM, we first introduce definitions and notations that will be used in the algorithm, and we detail the traditional naive approach.

A. Definitions and Notation

Let M SDB be the multi-source database made up of two sources connected with a complementary relation. S is the sequential source, referred to as the main source. Let I = {i 1 , i 2 , . . . , i n } be a set of distinct items, concretely item ids. S is made up of a set of sequences S = {S 1 , . . . , S t }, with S i = s i1 , . . . s iti , with s ij ∈ I.

C is the complementary source. C describes a set of items (I(C)). Each item i, i ∈ I(C), is associated with a set of attributes values, att(i) = {a 1 , . . . , a d } and one of these attributes represents the item id.

1) Original Frequent Pattern: In Web usage mining, a frequent sequential pattern p is an ordered list of items, denoted by p = e 1 , e 2 , . . . , e n where e k ∈ I with 1 ≤ k ≤ n. Given a minimum support threshold min sup, a sequential pattern p is frequent in S if sup(p) ≥ min sup. sup(p) is the support of p and represents the number of sequences in S where p occurs. In this work, such a frequent pattern is referred to as an original frequent pattern.

2) Promising Pattern: Let min sup prom be a support threshold, where min sup prom < min sup. The original pattern p is a promising pattern if min sup prom ≤ sup(p) < min sup i.e. p is not frequent but is almost frequent.

3) Similar Items: Let i j and i k be two distinct items. The similarity between these items (sim(i j , i k )) is evaluated as the ratio of common attributes values between both items (att(i j ) and att(i k )). i j and i k are considered as similar if sim(i j , i k ) ≥ min simitem where min simitem is a threshold representing the minimum ratio of common attributes values between two items.

4) Similar Patterns: Let p 1 and p 2 be two distinct patterns. p 1 and p 2 are similar if 1) they have the same length, 2) they are made up of the same sequence of items except at one position, 3) the items at this position are similar. Given p 1 = e 11 , e 12 , . . . , e 1l and p 2 = e 21 , e 22 , . . . , e 2l , p 1 and p 2 are similar if ∃i, sim(e 1i , e 2i ) ≥ min simitem ∧ ∀j ∈ [1..l] ∧ j = i, e 1j = e 2j .

5) General Pattern: A pattern is a general pattern if at least one of its elements is a description of an item (a set of attributes values). p = e 1 , e 2 , . . . , e l is a general pattern if ∃j, k, e j ⊆ att(i k ).

B. The Naive Approach

A study of the literature has highlighted that the traditional approach, that we refer to as the naive approach, first forms a unique dataset by integrating sources and then performs pattern mining on the integrated dataset (SC). The dataset consists of the item ids and their descriptive attributes. As SC is made up of sequences of itemsets, it can be mined by traditional SPM algorithms (see Section II). Although these algorithms are not specifically designed to tackle the item similarity problem, the data contained in SC make these algorithms naturally able to mine general patterns. Referring to the example in the introduction, a pattern mined from SC can be: p = {i 47 , eraser, pink, large}, {i 25 , pencils, woodcased, pre-sharpened},{stainless, steel scissors, 8.3 inches}, {i 19 , post-it, 3"x3", super-sticky} . We can see that the first, second and fourth elements of p contain redundant information as they contain both the item ids as well as the descriptive attributes. In line with our goal, having only the item id is sufficient as it is frequent. However, such an approach is interesting when considering the third element that is only made of attributes as the item id is not frequent; therefore, a "generalization" has been automatically made. A post-processing step can be made for the three other elements to discard the attributes when the item id is part of an element of a pattern. The resulting pattern will thus be: p = i 47 , i 25 , "stainless steel scissors 8.3 inches", i 19 , which corresponds to the general pattern. We conclude that this approach allows mining the patterns of interest. However, the resulting set of patterns is huge and redundant; and the mining process is highly complex, not only due to the mining of a complex dataset, but also due to the post-processing.

C. The G SPM Algorithm

To overcome the limits of the naive approach, we propose G SPM, a General Sequential Pattern Mining algorithm, that adopts a "mine and select" approach. G SPM relies on a double assumption. First, due to the similarity between items, some behaviors may occur under the form of several patterns. The support of this behavior is thus distributed over several patterns with lower supports that could be infrequent. Second, the id of an item is more precise than its attributes as an item id represents a unique item, while a set of attributes may represent several items. Thus, a pattern containing item ids is more precise than a one containing sets of attributes.

G SPM is designed to mine frequent original patterns as well as frequent general patterns that encompass similar infrequent patterns. It is presented in Algorithm 1 and proceeds as follows. G SPM starts the mining process by one source, namely the main source, and it first mines original patterns from this source: frequent patterns (F f , with a support ≥ min sup) and promising patterns (F p , with min sup prom ≤ support(F p ) < min sup) (line 2). Any traditional SPM algorithm can be used for this step. Each frequent original pattern is part of the final output set of the algorithm. A complexity gain is thus obtained on these patterns, in comparison to the naive approach of the literature. For each promising pattern, G SPM checks if its relatively low support is due to the similarity between items. So, for each pair of promising patterns (lines 3 and 4), G SPM checks if these patterns are pseudo-similar (line 5), i.e. they have the same length and differ at only one position. If yes (line 6), G SPM attempts to generalize them and form a general pattern (line 7) by mining the complementary source (C) that contains descriptive attributes of the items. The generalization identifies if the items that differ in both patterns are similar (line 26). Different items are considered similar if they share a minimum number of common attributes (min simitem). If items are similar, the general pattern is formed by replacing the items with their set of common attributes (line 30). The support of this general pattern G is equal to the sum of the supports of the two promising patterns. If G is frequent, it is added to F g , the set of general patterns, by using add general pattern (line 8). If G is already part of F g , add general pattern simply updates the support of G. The algorithm returns both sets of original frequent patterns and general frequent patterns.

IV. EXPERIMENTS

In this section, we discuss the experimental evaluations of G SPM. The experiments are run on a 64-bit Intel Core 2.60GHz CPU laptop, 7.7 GB RAM and Ubuntu 16.04 LTS operating system.

A. Data

The dataset used is a subset of the music corpus from [START_REF] Huillier | Modéliser la diversité au cours du temps pour comprendre le contexte de l'utilisateur dans les systèmes de recommandation[END_REF] and proposed by the Deezer company 1 . It consists of two data sources. The first source provides behavioral data representing users' consultations of soundtracks on Deezer website. It consists of sequences of soundtrack ids. This source is considered as the main source. The second source contains descriptive data about the soundtracks consisting of six descriptive attributes for each soundtrack. It is considered as the complementary source. P g ← general(C, p i , p j , pos, min sup, com a) nb dif f ← 0 //number of differences 16: The characteristics of the main source are displayed in Table I. The six descriptive attributes from the complementary source are the following. Duration represents the soundtrack duration in seconds. Artist ranking represents the ranking of the soundtrack's artist on Deezer (from 0 to 1,000,000). Acousticness is the soundtrack's acoustic level, energy is the soundtrack's activity level, danceability represents how much the soundtrack is suitable for dancing and speechiness represents the importance of the soundtrack's lyrics. These last four attributes take the form of a number ranging in the interval [0, 1].

for (k = 1 ; k ≤ length(p i ) ; k + +) do 17: if (p i [k]! = p j [k]) then 18: nb dif f ← nb dif f +
The mining of original patterns in G SPM, as well as in the naive approach are performed by SPAM algorithm [START_REF] Ayres | Sequential pattern mining using a bitmap representation[END_REF], with its implemented version in SPMF library [START_REF] Fournier-Viger | The spmf open-source data mining library version 2[END_REF]. SPAM is proved in the literature to be efficient and faster than other algorithms on datasets with long sequences.

In line with the literature, the minimum support threshold used (min sup) is determined according to the characteristics of the dataset: number of sequences, number of transactions and average length of the sequences. We set the value of min sup to 40 which represents 1.8% of the total number of sequences.

B. The Naive Approach

The previously discussed naive approach is considered as the baseline and is compared to G SPM. Recall that this approach integrates both data sources in one dataset made up of sequences of itemsets. Each itemset contains an item id and its set of descriptive attributes. The length of the sequences is noticeably increased compared to that of the sequences of the main source. Consequently, it leads to an increase in the complexity of the mining process especially as the number of descriptive attributes is significant. When running SPAM with min sup = 40 on this dataset, the number of frequent patterns is too huge to be stored (more than 15GB), the runtime of the mining process takes 3 days and the number of generated frequent patterns is greater than 1 billion. When running SPAM algorithm on a sample of this dataset made up of 3 attributes, the number of frequent patterns reaches 55 million patterns, with a runtime of 1.5 hours. These results confirm the complexity of this approach and thus its inadequacy on such a dataset. The set of patterns is also huge and redundant. Not only many patterns contain both the item id and the item descriptions, but also many patterns are subsets of others. For example, both patterns p = i 20 , i 98 , {kettle, steel, 1 liter} and p = i 20 , i 98 , {kettle, steel} can be mined, and p ⊂ p . Therefore, we consider that p is redundant with p as it provides no additional information, and it is more general. Therefore, an additional complexity due to the post-processing is required to obtain non-redundant patterns.

C. The G SPM Algorithm 1) Mining Promising Patterns: G SPM starts by mining original patterns: frequent and promising ones, from the main data source, with a traditional SPM algorithm. min sup prom and min sup are used as the minimum support thresholds.

Recall that min sup is set to 40. With SPAM, the number of mined frequent patterns is 1, 280 and the runtime is 0.368 seconds. As for the value of min sup prom, it impacts the number of promising patterns and the runtime. In this concern, we experimentally evaluate the impact of min sup prom on G SPM. Recall that the promising patterns are those that are considered for generalization. We choose to represent min sup prom as a percentage of min sup and to vary min sup prom from 90% to 75% of min sup. II confirms that the value of min sup prom greatly impacts the number of promising patterns, in line with the literature stating that the number of frequent patterns increases exponentially with the decrease of the minimum support. For the highest value of min sup prom (90% of min sup), the number of promising patterns is almost equivalent to that of frequent patterns (90% of frequent patterns). For each decrease by 5% of min sup prom, the number of promising patterns increases within a range of 70% to 85%. For example, when min sup prom is equal to 80% of min sup, the number of promising patterns is almost 3 times larger than that of frequent patterns. The runtime of the algorithm also increases as min sup prom decreases, but with a smaller degree than the number of promising patterns. For the highest value of min sup prom, the increase in the runtime is only 31%, whereas the number of promising patterns is almost equal to that of frequent patterns. When min sup prom equals 80% of min sup, the runtime increases by only 72% (the number of promising patterns is increased by 293%).

2) Forming General Patterns: The number of general patterns formed by G SPM and the runtime of the algorithm are of interest in this section. They are both presented in table III. In these experiments, we set min simitem, defined in III-A3, to 0.8.

When min sup prom is set to 90% of min sup, the number of general patterns (340) represents about 30% of the number of promising patterns. Let us study in details the way this set is obtained. First, we focus on the number of promising patterns that have at least one pseudo-similar pattern in the set of promising patterns, (named # pseudo-similar patterns in row 3 of table III for the sake of simplicity). 94.5% of the promising patterns have pseudo-similar patterns, which is quite high. The effective pruning occurs with the similarity between items: only 44.8% of the promising patterns have at least one similar pattern (named similar patterns in row 4). Notice that there is no pruning due to the support of the general pattern (line 31, Algorithm 1) as min sup prom > 50%, so if two patterns are similar, the resulting general pattern is frequent.

Let us now focus on the impact of min sup prom on these values. As expected, the number of general patterns increases with the decrease of min sup prom; it is even more than doubled for each decrease of 5% of min sup prom. With min sup prom = 75%, it is 3,930, three times larger than that of original frequent patterns. In addition, the number of general patterns represents from 30% to 61% of the promising patterns as min sup prom decreases. When focusing on the number of pseudo-similar patterns, it slightly increases. The main difference occurs here again in the identification of similar patterns. The increase in the ratio can be explained by the fact that the initial set of promising patterns is larger for lower values of min sup prom, so the chances of having a similar pattern among the promising ones are higher. When min sup prom = 85%, the number of general patterns is close to the number of original frequent patterns. In this case, the total number of frequent patterns is almost doubled (2,153 patterns). Let us now consider the runtime of G SPM according to min sup prom. As expected, it is longer than the runtime of mining the main source only (see Table II). More importantly, it is significantly lower that of the naive approach (see section IV-B). This confirms that one of the goals of G SPM is achieved: reducing the complexity of the mining process. When considering the impact of min sup prom on the runtime, we can see that it increases linearly with the number of promising patterns. Although the generalization step is complex , the increase in the runtime of the algorithm remains limited. The total number of frequent original patterns and frequent general patterns is: 1,620 for min sup prom = 90% and 5,210 for min sup prom = 75%. Notice that this number can be significantly increased by decreasing the value of min sup prom.

From the previous experiments, we can consider that the most adequate value of min sup prom for this dataset is min sup prom = 85% of min sup as it results in a significant but limited number of frequent general patterns relative to the frequent patterns generated by SPM process (about 70% of additional patterns), and it has a limited runtime (around 4 minutes). At last, we can see that the set of patterns mined by G SPM is much smaller than that mined by the naive approach as it is not redundant. This confirms that the second goal of G SPM is achieved: limiting the number of mined patterns.

V. CONCLUSION AND FUTURE WORK

This paper aimed at handling the problem of item similarity in behavioral pattern mining. We proposed G SPM, an algorithm that takes advantage of multi-source data to generate frequent general patterns by adopting a strategy of selective mining of sources. This strategy limits the complexity of the mining process and the redundancy among the mined patterns. The conducted experiments confirm that this strategy significantly decreases the runtime compared to the naive approach and that general patterns are actually formed.

Initial choices have been made, and they will be questioned in future works. For example, the similarity between two patterns can only be performed on patterns of the same length, and two candidate patterns can only differ by one item. Obviously, we can identify more candidates by adopting more advanced similarity measures and by considering more item differences between patterns, especially for long ones.

Fig. 1 .

 1 Fig. 1. A 3-source database with contextual and complementary relations

6 :

 6 1 https://www.deezer.com/ Algorithm 1 G SPM(M SDB, min sup, min sup prom, com a)1: F g ← ∅ 2: F f , F p ← SP M (S,min sup, min sup prom) 3: for (i = 1 ; i ≤ |F p | ; i + +) do 4: for (j = i + 1 ; j ≤ |F p | ; j + +) do 5: pos ← are pseudo sim patt(p i , p j ) if pos = -1 then 7:

8 :

 8 F g ← add general pattern(F g , P g ) Function are pseudo sim patt(p i , p j ) 13: pos ← -1 14: if (length(p i ) = length(p j )) then

	9:	end if
	10:	end for
	11: end for
	12: return F f , F g
	15:

  [START_REF] Aggarwal | Data mining: the textbook[END_REF]

	19:	pos ← k
	20:	end if
	21:	end for
	22:	if nb dif f > 1 then
	23:	pos ← -1
	24:	end if
	25: end if
	26: return pos
		Function general(C,p i ,p j ,pos,min sup,min simitem)
	27: G ← ∅
	28: r ← sim(att(p i [pos]), att(p j [pos]))
	29: if (r ≥ min simitem) then
	30:	s ← set comm att(att(p i [pos]), att(p j [pos]))
	31:	G ← p i
	32:	Replace(G, pos, s)
	33:	if (sup(p i ) + sup(p j ) ≥ min sup) then
	34:	return G
	35:	else
	36:	return ∅
	37:	end if
	38: end if
		# Sequences	2,220
		# Avg. sequence length 49
		# Consultations	108,596
		# Artists	8,959
		# Soundtracks	34,080
		Period	5th-8th Dec. 2016
		TABLE I
		CHARACTERISTICS OF THE MAIN SOURCE

Table II

 II

	min sup prom	90%	85%	80%	75%
	(relative to min sup)	(36)	(34)	(32)	(30)
	# promising patterns	1,135	2,129	3,745	6,399
	(% relative to freq. patt.)	(90%)	(166%)	(293%)	(500%)
	additional runtime (s)	0.115	0.231	0.266	0.322
	(% add. runtime)	(+31%)	+(63%) (+72%) (+87%)
		TABLE II

IMPACT

  OF min sup prom ON THE PROMISING PATTERNS AND RUNTIME displays the number of promising patterns and the runtime of G SPM over different values of min sup prom. Recall that the number of frequent patterns remains fixed. Table

TABLE III IMPACT

 III OF min sup prom ON THE NUMBER OF GENERAL PATTERNS AND RUNTIME

ACKNOWLEDGMENT

This work has been funded by the PIA2 e-FRAN METAL Project (2016-2021).


Xavier Gendre
email: gendre@unice.fr

Simultaneous estimation of the mean and the variance in heteroscedastic Gaussian regression

Keywords: AMS 2000 subject classifications: 62G08 Gaussian regression, heteroscedasticity, model selection, Kullback risk, convergence rate

Let Y be a Gaussian vector of R n of mean s and diagonal covariance matrix Γ. Our aim is to estimate both s and the entries σ i = Γ i,i , for i = 1, . . . , n, on the basis of the observation of two independent copies of Y . Our approach is free of any prior assumption on s but requires that we know some upper bound γ on the ratio max i σ i / min i σ i . For example, the choice γ = 1 corresponds to the homoscedastic case where the components of Y are assumed to have common (unknown) variance. In the opposite, the choice γ > 1 corresponds to the heteroscedastic case where the variances of the components of Y are allowed to vary within some range. Our estimation strategy is based on model selection. We consider a family {Sm ×Σm, m ∈ M} of parameter sets where Sm and Σm are linear spaces. To each m ∈ M, we associate a pair of estimators (ŝm, σm) of (s, σ) with values in Sm × Σm. Then we design a model selection procedure in view of selecting some m among M in such way that the Kullback risk of (ŝ m, σ m) is as close as possible to the minimum of the Kullback risks among the family of estimators {(ŝm, σm), m ∈ M}. Then we derive uniform rates of convergence for the estimator (ŝ m, σ m) over Hölderian balls. Finally, we carry out a simulation study in order to illustrate the performances of our estimators in practice.

Introduction

Let us consider the statistical framework given by the law of a Gaussian vector Y with mean s = (s 1 , . . . , s n ) ′ ∈ R n and diagonal covariance matrix

Γ σ =       σ 1 0 • • • 0 0 . . . . . . . . . . . . . . . . . . 0 0 • • • 0 σ n      
where σ = (σ 1 , . . . , σ n ) ′ ∈ (0, ∞) n . The vectors s and σ are both assumed to be unknown. Hereafter, for any t = (t 1 , . . . , t n ) ′ ∈ R n and τ = (τ 1 , . . . , τ n ) ′ ∈ 1 imsart-ejs ver. 2007/12/10 file: meavar.hyper28178.tex date: July 16, 2008 X. Gendre/Simultaneous estimation of the mean and the variance 2 (0, ∞) n , we denote by P t,τ the law of a Gaussian vector with mean t and covariance matrix Γ τ and by K(P s,σ , P t,τ ) the Kullback-Leibler divergence between P s,σ and P t,τ , K(P s,σ , P t,τ ) = 1 2

n i=1 (s i -t i ) 2 τ i + φ τ i σ i ,
where φ(u) = log u + 1/u -1, for u > 0. Note that, if the σ i 's are known and constant, the Kullback-Leibler divergence becomes the squared L 2 -norm and, in expectation, corresponds to the quadratic risk.

Let us suppose that we observe two independent copies of Y , namely Y [1] = (Y [START_REF] Akaike | Statistical predictor identification[END_REF] 1 , . . . , Y [START_REF] Akaike | Statistical predictor identification[END_REF] n ) ′ and Y [2] = (Y [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF] 1 , . . . , Y [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF] n ) ′ . Their coordinates can be expanded as Y

[j] i

= s i + √ σ i ε [j]
i , i = 1, . . . , n and j = 1, 2 , (

where ε [1] = (ε

[1] 1 , . . . , ε [1]
n ) ′ and ε [2] = (ε

[2]
1 , . . . , ε [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF] n ) ′ are two independent standard Gaussian vectors. The aim of this paper is to estimate the pair (s, σ) by model selection on the basis of the observation of Y [1] and Y [2] .

For this, we introduce a collection F = {S m × Σ m , m ∈ M} of products of linear subspaces of R n indexed by a finite or countable set M. In the sequel, these products will be called models and, for any m ∈ M, we will denote by D m the dimension of S m × Σ m . To each m ∈ M, we can associate a pair of independent estimators (ŝ m , σm ) = (ŝ m (Y [1] ), σm (Y [2] )) with values in S m × Σ m that we precise later. The Kullback risk of (ŝ m , σm ) is given by E[K(P s,σ , P ŝm,σm )] and is of order of the sum of two terms, inf (t,τ )∈Sm×Σm K(P s,σ , P t,τ ) + D m .

(1.

2)

The first one, called the bias term, represents the capacity of S m × Σ m to approximate the true value of (s, σ). The second, called the variance term, is proportional to the dimension of the model and corresponds to the amount of noise that we have to control. To warrant a small risk, these two terms have to be small simultaneously. Indeed, using the Kullback risk as a quality criterion, a good model is one minimizing (1.2) among F . Clearly, the choice of a such model depends on the pair of the unknown parameters (s, σ) and make good models unavailable to us. So, we have to construct a procedure to select an index m = m(Y [1] , Y [2] ) ∈ M depending on the data only, such that E[K(P s,σ , P ŝ m ,σ m )] is close to the minimal risk

R(s, σ, F ) = inf m∈M E[K(P s,σ , P ŝm,σm )] .
The art of model selection is precisely to provide procedure solely based on the observations in that way. The classical way consists in minimizing an empirical penalized criterion stochastically close to the risk. Considering the likelihood function with respect to Y [1] ,

∀t ∈ R n , τ ∈ (0, ∞) n , L(t, τ ) = 1 2 n i=1 Y [1] i -t i 2 τ i + log τ i ,
we choose m as the minimizer over M of the penalized likelihood criterion

Crit(m) = L(ŝ m , σm ) + pen(m) (1.3)
where pen is a penalty function mapping M into R + = [0, ∞). In this work, we give a form for the penalty in such way to obtain a pair of estimators (ŝ m, σ m) with a Kullback risk close to R(s, σ, F ).

Our approach is free of any prior assumption on s but requires that we know some upper bound γ 1 on the ratio σ * /σ * γ where σ * (resp. σ * ) is the maximum (resp. minimum) of the σ i 's. The knowledge of γ allows us to deal equivalently with two different cases. First, "γ = 1" corresponds to the homoscedastic case where the components of Y [1] and Y [2] are independent with a common variance (i.e. σ i ≡ σ) which can be unknown. On the other side, "γ > 1" means that the σ i 's can be distinct and are allowed to vary within some range. This uncommonness of the variances of the observations is known as the heteroscedastic case. Heteroscedasticity arises in many practical situations in which the assumption that the variances of the data are equal is debatable.

The research field of the model selection has known an important development in the last decades and it is beyond the scope of this paper to make an exhaustive historical review of the domain. The interested reader could find a good introduction to model selection in the first chapters of [START_REF] Mcquarrie | Regression and times series model selection[END_REF]. The first heuristics in the domain are due to Mallows [START_REF] Mallows | Some comments on c p[END_REF] for the estimation of the mean in homoscedastic Gaussian regression with known variance. In more general Gaussian framework with common known variance, Barron et al. [START_REF] Barron | Risk bounds for model selection via penalization[END_REF], Birgé and Massart ([9] and [START_REF] Birgé | A generalized c p criterion for gaussian model selection[END_REF]) have designed an adaptive model selection procedure to estimate the mean for quadratic risk. They provide non-asymptotic upper bound for the risk of the selected estimator. For bound of order of the minimal risk among the model collection, this kind of result is called oracle inequalities. Baraud [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] has generalized their results to homoscedastic statistical models with non-Gaussian noise admitting moment of order bigger than 2 and a known variance. All these results remain true for common unknown variance if some upper bound on it is supposed to be known. Of course, the bigger is this bound, the worst are the results. Assuming that γ is known does not imply the knowledge of a such upper bound.

In the homoscedastic Gaussian framework with unknown variance, Akaike has proposed penalties for estimating the mean for quadratic risk (see [START_REF] Akaike | Statistical predictor identification[END_REF], [START_REF] Akaike | Information theory and an extension of the maximum likelihood principle[END_REF] and [START_REF] Akaike | A new look at the statistical model identification[END_REF]). Replacing the variance by a particular estimator in his penalty term, Baraud [START_REF] Baraud | Model selection for regression on a fixed design[END_REF] has obtained oracle inequalities for more general noise than Gaussian and polynomial model collection. Recently, Baraud, Giraud and Huet [START_REF] Baraud | Gaussian model selection with an unknown variance[END_REF] have constructed penalties able to take into account the complexity of the model collection for estimating the mean with quadratic risk in Gaussian homoscedastic model with unknown variance. They have also proved results for the estimation of the mean and the variance factor with Kullback risk. This problem is close to ours and corresponds to the case "γ = 1". A motivation for the present work was to extend their results to the heteroscedastic case "γ > 1" in order to get oracle inequalities by minimization of penalized criterion as (1.3). Assuming that the model collection is not too large, we obtain inequalities with the same flavor up to a logarithmic factor

E[K(P s,σ , P ŝ m ,σ m )] (1.4) C inf m∈M inf (t,τ )∈Sm×Σm K (P s,σ , P t,τ ) + D m log 1+ǫ D m + R
where C and R are positive constants depending in particular on γ and ǫ is a positive parameter.

A non-asymptotic model selection approach for estimation problem in heteroscedastic Gaussian model was studied in few papers only. In the chapter 6 of [START_REF] Arlot | Rééchantillonnage et sélection de modèles[END_REF], Arlot estimates the mean in heteroscedastic regression framework but for bounded data. For polynomial model collection, he uses resampling penalties to get oracle inequalities for quadratic risk. Closer to our problem, Comte and Rozenholc [START_REF] Comte | Adaptive estimation of mean and volatility functions in (auto-)regressive models[END_REF] have estimated the pair (s, σ). Their estimation procedure is different from ours and it makes the theoretical results difficultly comparable between us. For instance, they proceed in two steps (one for the mean and one for the variance) and they give risk bounds separately for each parameter in L 2 -norm while we estimate directly the pair (s, σ) for Kullback risk.

As described in [START_REF] Birgé | From model selection to adaptive estimation[END_REF], one of the main advantages of inequalities such as (1.4) is that they allow us to derive uniform convergence rates for the risk of the selected estimator over many classes of smoothness. Considering a collection of histogram models, we provide convergence rates over Hölderian balls. Indeed, for α 1 , α 2 ∈ (0, 1], if s is α 1 -Hölderian and σ is α 2 -Hölderian, we prove that the risk of (ŝ m, σ m) converges with a rate of order of

n log 1+ǫ n -2α/(2α+1)
where α = min{α 1 , α 2 } is the worst regularity. To compare this rate, we can think of the homoscedastic case with only one observation of Y . Indeed, in this case, the optimal rate of convergence in the minimax sense is n -2α/(2α+1) and, up to a logarithmic loss, our rate is comparable to this one. To our knowledge, our results in non-asymptotic estimation of the mean and the variance in heteroscedastic Gaussian model are new.

The paper is organized as follows. The main results are presented in section 2. In section 3, we carry out a simulation study in order to illustrate the performances of our estimators in practice. The last sections are devoted to the proofs and to some technical results.

Main results

In a first time, we introduce the model collection, the estimators and the procedure. Next, we present the main results whose proofs can be found in the section 4. In the sequel, we consider the framework (1.1) and, for the sake of simplicity, we suppose that there exists an integer k n 0 such that n = 2 kn .

Model collection and estimators

In order to estimate the mean and the variance, we consider linear subspaces of R n constructed as follows. Let M be a countable or finite set. To each m ∈ M, we associate a regular partition p m of {1, . . . , 2 kn } given by the

|p m | = 2 km consecutive blocks (i -1)2 kn-km + 1, . . . , i2 kn-km , i = 1, . . . , |p m | .
For any I ∈ p m and any x ∈ R n , let us denote by x| I the vector of R n/|pm| with coordinates (x i ) i∈I . Then, to each m ∈ M, we also associate a linear subspace E m of R n/|pm| with dimension 1 d m 2 kn-km . This set of pairs (p m , E m ) allows us to construct a model collection. Hereafter, we identify each m ∈ M to its corresponding pair (p m , E m ).

For

any m = (p m , E m ) ∈ M, we introduce the subspace S m ⊂ R n of the E m -piecewise vectors, S m = {x ∈ R n such that ∀I ∈ p m , x| I ∈ E m } , and the subspace Σ m ⊂ R n of the piecewise constant vectors, Σ m =    I∈pm g I 1l I , ∀I ∈ p m , g I ∈ R    . The dimension of S m × Σ m is denoted by D m = |p m |(d m + 1
). To estimate the pair (s, σ), we only deal with models S m × Σ m constructed in a such way. More precisely, we consider a collection of products of linear subspaces

F = {S m × Σ m , m ∈ M} (2.1)
where M is a set of pairs (p m , E m ) as above. In the paper, we will often make the following hypothesis on the model collection:

(H θ ) There exists θ > 1 such that ∀m ∈ M, n θ θ -1 (4γ 2 + 1)D m .
This hypothesis avoids handling models with dimension too great in front of the number of observations. Let m ∈ M, we denote by π m the orthogonal projection on S m . We estimate (s, σ) by the pair of independent estimators (ŝ m , σm ) ∈ S m × Σ m given by ŝm = π m Y [1] and σm = I∈pm σm,I 1l I where ∀I ∈ p m , σm,I = 1

|I| i∈I Y [2] i -π m Y [2] i 2 .
Thus, we get a collection of estimators {(ŝ m , σm ), m ∈ M}.

Risk upper bound

We first study the risk on a single model to understand its order. Take an arbitrary m ∈ M. We define

(s m , σ m ) ∈ S m × Σ m by s m = π m s and σ m = I∈pm σ m,I 1l I where ∀I ∈ p m , σ m,I = 1 |I| i∈I (s i -s m,i ) 2 + σ i .
Easy computations proves that the pair (s m , σ m ) reaches the minimum of the Kullback-Leibler divergence on

S m × Σ m , inf (t,τ )∈Sm×Σm K(P s,σ , P t,τ ) = K(P s,σ , P sm,σm ) = 1 2 I∈pm i∈I log σ m,I σ i .
The next proposition permits us to compare this quantity with the Kullback risk of (ŝ m , σm ).

Proposition 1. Let m ∈ M, if the hypothesis (H θ ) is fulfilled, then K(P s,σ , P sm,σm ) ∨ D m 4γ E [K (P s,σ , P ŝm,σm )] K(P s,σ , P sm,σm ) + 4γ 2 θ 3 D m .
As announced in (1.2), this result shows that the Kullback risk of the pair (ŝ m , σm ) is of order of the sum of a bias term K(P s,σ , P sm,σm ) and a variance term which is proportional to D m . Thus, minimizing the Kullback risk E [K (P s,σ , P ŝm,σm )] among m ∈ M corresponds to finding a model that realizes a compromise between these two terms.

Let pen be a non negative function on M, we choose m ∈ M as some minimizer of the penalized criterion m = argmin m∈M {L (ŝ m , σm ) + pen(m)} .

(2.2)

In the sequel, we denote by (s, σ) = (ŝ m, σ m) the selected pair of estimators. It satisfies the following result:

Theorem 2. Under the hypothesis (H θ ), suppose there exist A, B > 0 such that, for any

(k, d) ∈ N 2 , M k,d = Card m ∈ M such that |p m | = 2 k and d m = d A(1 + d) B . (2.3)
Moreover, assume that there exist δ, ǫ > 0 such that

D m 5δγn log 1+ǫ n , ∀m ∈ M . (2.4) If we take ∀m ∈ M, pen(m) = γθ + log 1+ǫ D m D m (2.5) then E [K (P s,σ , P s,σ )] C inf m∈M K (P s,σ , P sm,σm ) + D m log 1+ǫ D m + R (2.6)
where R = R(γ, θ, A, B, ǫ, δ) is a positive constant and C can be taken equal to

C = 2 1 + (4γθ 2 + 1)γθ log 1+ǫ 2 .
The inequality (2.6) is close to an oracle inequality up to a logarithmic factor. Thus, considering the penalty (2.5) whose order is slightly bigger than the dimension of the model, the risk of the estimator provided by the criterion (1.3) is comparable the minimal one among the model collection F .

Convergence rate

One of the main advantages of an inequality as (2.6) is that it gives uniform convergence rates with respect to many well known classes of smoothness. To illustrate this, we consider the particular case of the regression on a fixed design. For example, in the framework (1.1), we suppose that

∀1 i n, s i = s r (i/n) and σ i = σ r (i/n),
where s r and σ r are two unknown functions that map [0, 1] to R.

In this section, we handle the normalized Kullback-Leibler divergence

K n (P s,σ , P t,τ ) = 1 n K (P s,σ , P t,τ ) ,
and, for any α ∈ (0, 1) and any L > 0, we denote by H α (L) the space of the α-Hölderian functions with constant L on [0, 1],

H α (L) = {f : [0, 1] → R : ∀x, y ∈ [0, 1], |f (x) -f (y)| L|x -y| α } .
Moreover, we consider a model collection F P C as described in the section 2.1 such that, for any m ∈ M, E m is the space of dyadic piecewise constant functions on d m blocks. More precisely, let m = (p m , E m ) ∈ M and consider the regular dyadic partition p ′ m with |p m |d m blocks that is finer than p m . We define S m as the space of the piecewise constant functions on p ′ m ,

S m =    f = I∈p ′ m f I 1l I such that ∀I ∈ p ′ m , f I ∈ R    ,
and Σ m as the space of the piecewise constant functions on p m ,

Σ m =    g = I∈pm g I 1l I such that ∀I ∈ p m , g I ∈ R    .
Then, the model collection that we consider is

F P C = {S m × Σ m , m ∈ M} .
Note that this collection satisfies (2.3) with A = 1 and B = 0. The following result gives a uniform convergence rate for (s, σ) over Hölderian balls.

Proposition 3. Let α 1 , α 2 ∈ (0, 1], L 1 , L 2 >
E [K n (P s,σ , P s,σ )] C n log 1+ǫ n -2α/(2α+1) (2.7)
where α = min{α 1 , α 2 } and C is a constant which depends on α 1 , α 2 , L 1 , L 2 , θ, γ, σ * and ǫ.

The exponent α corresponds to the worst regularity between s and σ. As we are estimating simultaneously the two functions, it is not paradoxical to obtain a rate of convergence that depends on the function that is the hardest to estimate. In order to compare the rate given by (2.7), we can think to the homoscedastic case with only one observation of Y . In this framework, it is known that, if s is in H α (L), the optimal rate of convergence in minimax sense is n -2α/(2α+1) for the estimation of s in quadratic risk. Moreover, in the heteroscedastic case with one observation of Y , Wang et al. [START_REF] Wang | Effect of mean on variance function estimation in nonparametric regression[END_REF] have proved that the order of the minimax rate of convergence for the estimation of the variance function is max n -4α1 , n -2α2/(2α2+1) once s ∈ H α1 (L 1 ) and σ ∈ H α2 (L 2 ). Thus, up to a logarithmic factor, the rate of convergence given by the previous property can be compared to these optimal rates.

Simulation study

To illustrate our results, we consider the following pairs of functions (s r , σ r ) defined on [0, 1] and, for each one, we precise the true value of γ:

• M1 (γ = 2) s r (x) =        4 if 0 x < 1/4 0 if 1/4 x < 1/2 2 if 1/2 x < 3/4 1 if 3/4 x 1 and σ r (x) = 2 if 0 x < 1/2 1 if 1/2 x 1 ,
• M2 (γ = 1)

s r (x) = 1 + sin(2πx + π/3) and σ r (x) = 1 , • M3 (γ = 7/3) s r (x) = 3x/2 and σ r (x) = 1/2 + 2 sin(4π(x ∧ 1/2) 2 )/3 , • M4 (γ = 2) s r (x) = 1 + sin(4π(x ∧ 1/2)) and σ r (x) = (3 + sin(2πx))/2 .
In all this section, we consider the model collection F P C and we take k n = 10. Let us first present how our procedure performs on the examples with the true value of γ for each simulation, ǫ = 10 -2 in the assumption (2.4) and the penalty (2.5). The estimators are drawn in plain line and the true functions in dotted line. In the case of M1, we can note that the procedure choose the "good" model in the sense that if the pair (s r , σ r ) belongs to a model of F P C , this one is generally chosen by our procedure. Repeating the simulation 25 000 times with the framework of M1 gives us that, with probability higher than 99.9%, the probability for making this "good" choice is about 0.9985 (±3 × 10 -5 ). Even if the mean does not belong to one of the S m 's, the procedure recover the homoscedastic nature of the observations in the case M2. By doing 25 000 simulations with the framework induced by M2, the probability to choose an homoscedastic model is around 0.99996 (±1 × 10 -5 ) with a confidence of 99.9%. For more general framework as M3 and M4, the estimators perform visually well and detect the changements in the behaviour of the mean and the variance functions.

The parameter γ is supposed to be known and is present in the definition of the penalty. So, we naturally can ask what is its importance in the procedure.

In particular, what happens if we do not have the good value? The following table present some estimations of the ratio

E [K (P s,σ , P s,σ )] / inf m∈M E [K (P s,σ , P ŝm,σm )]
for several values of γ. These estimated values have been obtained with 500 repetitions for each one. The main part of the computation time is devoted to the estimation of the oracle's risk. 1: Ratio between the Kullback risk of (s, σ) and the one of the oracle.

As expected, the best estimations are obtained for the good value of γ. But it is interesting to observe that the ratio does not suffer to much from small errors on the knowledge of γ. For example, in the homoscedastic case M2, even if we have supposed that γ = 3, the ratio stays reasonably small.

Proofs

For any I ⊂ {1, . . . , n} and any x, y ∈ R n , we introduce the notations

x, y I = i∈I x i y i and x 2 I = i∈I x 2 i .
Let m ∈ M, we will use several times in the proofs the fact that, for any

I ∈ p m , |I|σ m,I σ * χ 2 (|I| -d m -1) (4.1)
where χ 2 (|I| -d m -1) is a χ 2 random variable with |I| -d m -1 degrees of freedom.

Proof of the proposition 1

Let us expand the Kullback risk of (ŝ m , σm ),

E [K(P s,σ , P ŝm,σm )] = 1 2 I∈pm i∈I E (s i -ŝm,i ) 2 σm,I + φ σm,I σ i = E [K(P s,σ , P sm,σm )] + 1 2 I∈pm |I|E φ σm,I σ m,I .
To upper bound the expectation, note that

∀I ∈ p m , E[σ m,I ] = σ m,I - 1 |I| i∈pm σ i π m,i,i = σ m,I (1 -ρ I )
where

ρ I = 1 |I|σ m,I i∈pm σ i π m,i,i ∈ (0, 1) .
We apply the lemmas 10 and 11 to each block I ∈ p m and, by concavity of the logarithm, we get

E φ σm,I σ m,I log E σm,I σ m,I + E σ m,I σm,I -1 log(1 -ρ I ) + 1 1 -ρ I 1 + 8γ 2 (|I| -d m -2γ 2 ) (|I| -d m -4γ 2 ) 2 -1 -ρ I + 1 1 -ρ I 1 + 8γ 2 (|I| -d m -2γ 2 ) (|I| -d m -4γ 2 ) 2 -1 1 1 -ρ I ρ 2 I + 8γ 2 (|I| -d m -2γ 2 ) (|I| -d m -4γ 2 ) 2 .
Using (H θ ) and the fact that ρ I γd m /|I|, we obtain

1 2 I∈pm |I|E φ σm,I σ m,I 1 2 I∈pm |I| 1 -ρ I ρ 2 I + 8γ 2 (|I| -d m -2γ 2 ) (|I| -d m -4γ 2 ) 2 1 2 I∈pm γ 2 d 2 m |I| -γd m + 8γ 2 |I| 2 θ (|I| -γd m )(|I| -d m -4γ 2 ) |p m | γ(θ -1) 2 d m + 4γ 2 θ 3 4γ 2 θ 3 D m .
For the lower bound, the positivity of φ in (4.2) and the independence between ŝm and σm give us

E [K(P s,σ , P ŝm,σm )] 1 2 I∈pm E s -ŝm 2 I σm,I 1 2 I∈pm E s -ŝm 2 I E [σ m,I ] 1 2 I∈pm |I| s -s m 2 I + σ * d m s -s m 2 I + (|I| -d m )σ * .
It

Proof of theorem 2

We prove the following more general result: then

(1 -α)E [K (P s,σ , P s,σ )] inf m∈M {E [K (P s,σ , P ŝm,σm )] + pen(m)} + R 1 (M) + R 2 (M)
where R 1 (M) and R 2 (M) are defined by

R 1 (M) = Cθ 2 γ m∈M |p m |d m 2Cθ 2 γ |p m |d m log(1 + d m ) x m ⌊2 log(1+dm)⌋ and R 2 (M) = 2(α + γθ) + 1 α m∈M |p m | exp - n 2θ|p m | log 1 + α|p m |x m γn(α + 2) .
In these expressions, ⌊•⌋ is the integral part and C is a positive constant that could be taken equal to 12 √ 2e/( √ e -1).

Before proving this result, let us see how it implies the theorem 2. The choice (2.5) for the penalty function corresponds to x m = D m log 1+ǫ D m in (4.2). Applying the previous theorem with α = 1/2 leads us to

E [K (P s,σ , P s,σ )] 2 inf m∈M {E [K (P s,σ , P ŝm,σm )] + pen(m)} + 2Cθ 2 γR 1 + 8(γθ + 1)R 2 with R 1 = m∈M |p m |d m 2Cθ 2 γ |p m |d m log(1 + d m ) x m ⌊2 log(1+dm)⌋
and

R 2 = m∈M |p m | exp - n 2θ|p m | log 1 + |p m |x m 5γn .
Using the upper bound on the risk of the proposition 1, we easily obtain the coefficient of the infimum in (2.6). Thus, it remains to prove that the the two quantities R 1 and R 2 can be upper bounded independently of n. For this, we denote by B ′ = B + 2 log(2Cθ 2 γ) + 1 and we compute

R 1 = m∈M |p m |d m 2Cθ 2 γ |p m |d m log(1 + d m ) |p m |(1 + d m ) log 1+ǫ (|p m |(1 + d m )) ⌊2 log(1+dm)⌋ k 0 d 1 M k,d 2 k/2 d 2Cθ 2 γ2 -k/2 log(1 + d) (k log 2 + log(1 + d)) 1+ǫ ⌊2 log(1+d)⌋ A k 0 d 1 (1 + d) B ′ 2 k/2 2 -k/2 log(1 + d) (k log 2 + log(1 + d)) 1+ǫ ⌊2 log(1+d)⌋ A(R ′ 1 + R ′′ 1 )
. We have split the sum in two terms, the first one is for d = 1,

R ′ 1 = k 0 2 B ′ log 2 (k log 2 + log 2) 1+ǫ = 2 B ′ log ǫ 2 k 0 1 (k + 1) 1+ǫ < ∞ .

The other part R ′′

1 is for d 2 and is equal to

k 0 d 2 (1 + d) B ′ 2 -k(⌊2 log(1+d)⌋-1)/2 log(1 + d) (k log 2 + log(1 + d)) 1+ǫ ⌊2 log(1+d)⌋ . Noting that 1 < log(1 + d) ⌊2 log(1 + d)⌋, we have R ′′ 1 k 0 2 -k/2 d 2 (1 + d) B ′ exp (-ǫ⌊2 log(1 + d)⌋ log log(1 + d)) √ 2 √ 2 -1 d 2 (1 + d) B ′ -ǫ log log(1+d) < ∞ .
We now handle R 2 and (2. For any positive t, 1 + t 1+ǫ (1 + t) 1+ǫ , then we finally obtain

R 2 = m∈M |p m | exp - n 2θ|p m | log 1 + |p m |x m 5γn m∈M |p m | exp - x m 10θγ(δ + 1)|p m | k 0 d 1 M k,d 2 k exp - (1 + d) log 1+ǫ 2 k (1 + d) 10θγ(δ + 1) AR ′ 2 R ′′ 2
where we have set

R ′ 2 = k 0 exp k log 2 - (k log 2) 1+ǫ 5θγ(δ + 1) < ∞ and R ′′ 2 = d 1 exp B log(1 + d) - (1 + d) log 1+ǫ (1 + d) 10θγ(δ + 1) < ∞ .
We now have to prove theorem 4. For an arbitrary m ∈ M, we begin the proof by expanding the Kullback-Leibler divergence of (s, σ),

K(P s,σ , P s,σ ) = 1 2 n i=1 (s i -si ) 2 σi + φ σi σ i = K(P s,σ , P ŝm,σm ) + [L(ŝ m , σm ) -K(P s,σ , P ŝm,σm )] +[L(ŝ m , σm ) -L(s, σ)] + [K(P s,σ , P s,σ ) -L(s, σ)] .
The difference between the divergence and the likelihood can be expressed as

K(P s,σ , P ŝm,σm ) -L(ŝ m , σm ) = 1 2 I∈pm i∈I σ i σm,I -1 1 -ε [1] i 2 - 2(s i -ŝm,i ) √ σ i ε [1] i σm,I - 1 2 n i=1 ε [1] i 2 + log σ i .
By the definition (2.2) of m, for any α ∈ (0, 1), we can write

(1 -α)K(P s,σ , P s,σ ) (4.3) K(P s,σ , P ŝm,σm ) + pen(m) + G(m) +W 1 ( m) + W 2 ( m) + Z( m) -pen( m)
where, for any m ∈ M,

W 1 (m) = I∈pm 1 σm,I π m Γ 1/2 σ ε [1] 2 I , W 2 (m) = I∈pm 1 σm,I s m -s, Γ 1/2 σ ε [1] I - α 2 s m -s 2 I , Z(m) = 1 2 I∈pm i∈I σ i σm,I -1 1 -ε [1] i 2 -αφ σm,I σ i and G(m) = I∈pm 1 σm,I s -ŝm , Γ 1/2 σ ε [1] I - 1 2 i∈I σ i σm,I -1 1 -ε [1] i 2 .
We subdivide the proof of theorem 4 in several lemmas.

Lemma 5. For any m ∈ M, we have

E[G(m)] 0 .
Proof. Let us compute this expectation to obtain the inequality. By independence between ε [1] and ε [2] , we get [2] 0.

E G(m) ε [2] = I∈pm - 1 σm,I E π m Γ 1/2 σ ε [1] , Γ 1/2 σ ε [1] I = - I∈pm 1 σm,I E π m Γ 1/2 σ ε [1] 2 I . It leads to E[G(m)] = E E G(m) ε
In order to control Z(m), we split it in two terms that we study separately,

Z(m) = Z + (m) + Z -(m)
where

Z + (m) = 1 2 I∈pm i∈I σ i σm,I -1 + 1 -ε [1] i 2 -αφ σm,I σ i 1l σm,I σi and Z -(m) = 1 2 I∈pm i∈I σ i σm,I -1 + ε [1] i 2 -1 -αφ σm,I σ i 1l σm,I >σi .
Lemma 6. Let m ∈ M and x be a positive number. Under the hypothesis (H θ ), we get

E (Z + (m) -x) + γθ|p m | α exp - n -(d m + 3)|p m | 2|p m | log 1 + 2α|p m |x γn .
Proof. We begin by setting, for all 1 i n,

T i (m) = (σ i /σ m,i -1) + n j=1 (σ j /σ m,j -1) 2 + 1/2
and we denote by

S(m) = n i=1 T i (m) 1 -ε [1] i 2 .
We lower bound the function φ by the remark

∀a ∈ (0, 1), ∀u ∈ [a, 1], 1 u -1 2 2 a φ(u) .
Thus, we obtain

n i=1 σ i σm,i -1 2 + 2 max i n σ i σm,i n j=1 φ σm,j σ j 1l σm,j σj = 2M (m)
and we use this inequality to get

Z + (m) = 1 2 n i=1 σ i σm,i -1 2 + 1/2 S(m) - α 2 n i=1 φ σm,i σ i 1l σm,i σi M (m) 2 S(m) + - α 2 n i=1 φ σm,i σ i 1l σm,i σi 1 4α max i n σ i σm,i S(m) 2 + .
To control S(m), we use the inequality (4.2) in [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF], conditionally to ε [2] . Let u > 0,

P max i n σ i σm,i S(m) 2 + u = E P S(m) u/ max i n σ i σm,i ε [2] E exp - u 4 min i n σm,i σ i .
By the remark (4.1), we can upper bound it by

P max i n σ i σm,i S(m) 2 + u E exp - u 4γ min I∈pm X I imsart-
E Z + (m) - γ 2α t + ∞ 0 E exp - αu γ + t 2 min I∈pm X I du ∞ 0 E max I∈pm exp - αu γ + t 2 X I du .
Using (H θ ), we roughly upper bound the maximum by the sum and we get

E Z + (m) - γ 2α t + I∈pm γ|I| α(|I| -d m -3) 1 + t |I| -(|I|-dm-3)/2 γθ|p m | α exp - n -(d m + 3)|p m | 2|p m | log 1 + t|p m | n .
Take t = 2αx/γ to conclude.

Lemma 7. Let m ∈ M and x be a positive number, then

E (Z -(m) -(2α + 1)x) + 2α + 1 α e -αx .
Proof. Note that for all u > 1, we have

2φ(u) 1 u -1 2 .
Let t > 0, we handle Z -(m) conditionally to ε [2] and, using the previous lower bound on φ, we obtain

P Z -(m) 2α + 1 2α t ε [2] P 1 2 n i=1 σ i σm,i -1 - ε [1] i 2 -1 2α + 1 2α t + α 4 n i=1 σ i σm,i -1 2 - ε [2] P   1 2 n i=1 σ i σm,i -1 - ε [1] i 2 -1 t + t 2 n i=1 σ i σm,i -1 2 - ε [2]   . Let us note that max i n σ i σm,i -1 - 1 ,
thus, we can apply the inequality (4.1) from [START_REF] Laurent | Adaptive estimation of a quadratic functional by model selection[END_REF] to get

P Z -(m) 2α + 1 2α t exp(-t/2) .
This inequality leads us to

E Z -(m) - 2α + 1 α t + +∞ (2α+1)t/α P(Z -(m) u)du 2α + 1 α e -t .
Take t = αx to get the announced result.

It remains to control W 1 (m) and W 2 (m). For the first one, we now prove a Rosenthal-type inequality.

Lemma 8. Consider any m ∈ M. Under the hypothesis (H θ ), for any x > 0, we have

E[(W 1 (m) -γθD m -x) + ] Cθ 2 γ |p m |d m 2Cθ 2 γ |p m |d m log(1 + d m ) x ⌊2 log(1+dm)⌋
where ⌊•⌋ is the integral part and C is a positive constant that could be taken equal to

C = 12 √ 2e √ e -1 ≈ 43.131 .
Proof. Using the lemma 10 and the remark (4.1), we dominate W 1 (m), Take x > 0 and an integer q > 1, then

W 1 (m) W ′ 1 (m) = γ I∈pm |I|d m |I| -d m -1 F I = γnd m n -|p m |(1 + d m ) I∈pm
E (W ′ 1 (m) -E[W ′ 1 (m)] -x) + E (W ′ 1 (m) -E[W ′ 1 (m)]) q + (q -1)x q-1 . (4.4) We set V = W ′ 1 (m) -E[W ′ 1 (m)].
It is the sum of the independent centered random variables

X I = γnd m n -|p m |(1 + d m ) (F I -E[F I ]), I ∈ p m .
To dominate E V q + , we use the theorem 9 in [START_REF] Boucheron | Moment inequalities for functions of independent random variables[END_REF]. Let us compute

I∈pm E[X 2 I ] = 2γ 2 n 2 d m (n -3|p m |)|p m | (n -|p m |(d m + 3)) 2 (n -|p m |(d m + 5)) 2γ 2 θ 3 |p m |d m
and so,

E V q + 1/q 12κγ 2 θ 3 |p m |d m q + qκ √ 2E max I∈pm |X I | q 1/q
where κ = √ e 2( √ e -1) .

We consider

q = 1 + ⌊2 log(1 + d m )⌋ where ⌊•⌋ is the integral part. Such choice of q implies 2|p m |q < n -|p m |(1 + d m )
and we roughly upper bound the maximum by the sum

E max I∈pm |X I | q (γθd m ) q E max I∈pm |F I -E[F I ]| q (γθd m ) q 2 q-1 (E[F m ] q + |p m |E[F q m ]) 2γθ 2 d m q 2 + |p m | 2 (2γθd m ) (1 + 2(q -1)/d m ) 1 -2|p m |q/(n -|p m |(1 + d m )) q 6γθ 2 d m q |p m | .
Thus, it gives

E V q + 1/q γθ 2 12κ|p m |d m q + 6κ √ 2|p m | 1/q d m q 6κ √ 2γθ 2 |p m |d m q + |p m | 1/q d m q 12κ √ 2γθ 2 |p m |d m (1 + ⌊2 log(1 + d m )⌋) .
Injecting this inequality in (4.4) leads to

E (W ′ 1 (m) -E[W ′ 1 (m)] -x) + Cγθ 2 |p m |d m Cγθ 2 |p m |d m (1 + 2 log(1 + d m )) 2x ⌊2 log(1+dm)⌋ . Lemma 9.
Consider any m ∈ M and let x be a positive number. Under the hypothesis (H θ ), we have

E (W 2 (m) -x) + γθ|p m | α exp - n -(d m + 3)|p m | 2|p m | log 1 + 2α|p m |x γn .
Proof. Let us define

A(m) = I∈pm s -s m 2 I σm,I .
We apply the Gaussian inequality to W 2 (m) conditionally to ε [2] ,

∀t > 0, P     W 2 (m) + α 2 A(m) 2t I∈pm Γ 1/2 σ (s -s m ) 2 I σ2 m,I ε [2]     e -t .
It leads to

P W 2 (m) + α 2 A(m) 2tA(m) max i n σ i σm,i ε [2] e -t
and thus, by the remark (4.1),

P W 2 (m) γt α max I∈pm X -1 I ε [2] P W 2 (m) t α max i n σ i σm,i ε [2] e -t
where the X I 's are i.i.d. random variables of law χ 2 (|I| -d m -1) /|I|. Finally, we integrate following ε [2] and we get

P(W 2 (m) t) E max I∈pm exp - αt γ X I .
We finish as we did for Z + (m),

E W 2 (m) - γ 2α t + +∞ 0 E max I∈pm exp - αu γ + t 2 X I du γθ α I∈pm 1 + t |I| -(|I|-dm-3)/2 γθ|p m | α exp - n -(d m + 3)|p m | 2|p m | log 1 + t|p m | n .
In order to end the proof of theorem 4, we need to put together the results of the previous lemmas. Because γ 1, for any x > 0, we can write

e -αx exp - n 2|p m | log 1 + 2α|p m |x γn .
We now come back to (4.3) and we apply the preceding results to each model. Let m ∈ M, we take x = x m 2(2 + α) and, recalling (4.2), we get the following inequalities

(1 -α)E[K(P s,σ , P s,σ )] E[K(P s,σ , P ŝm,σm )] + pen(m) + E W 1 ( m) -γθD m - x m 2(2 + α) + +E W 2 ( m) - x m 2(2 + α) + + E Z + ( m) - x m 2(2 + α) + +E Z -( m) -(1 + 2α) x m 2(2 + α) + E[K(m)] + pen(m) + R 1 (M) + R 2 (M) (4.5)
where R 1 (M) and R 2 (M) are the sums defined in the theorem 4. As the choice of m is arbitrary, we can take the infimum among m ∈ M in the right part of (4.5).

Proof of the proposition 3

For the collection F P C , we have A = 1 and B = 0 in (

) + D m log 1+ǫ D m + R n C inf m∈M s -s m 2 2 2nσ * + σ -σm 2 2 2nσ 2 * + D m log 1+ǫ D m + R n because, for any x > 0, φ(x) (x -1/x) 2 . Assuming (s r , σ r ) ∈ H α1 (L 1 ) × H α2 (L 2 )
, we know (see [START_REF] Devore | Constructive approximation[END_REF]) that

s -s m 2 2 nL 2 1 (|p m |d m ) -2α1 and σ -σm 2 2 nL 2 2 |p m | -2α2 . Thus, we obtain E [K n (P s,σ , P s,σ )] C inf m∈M L 2 1 2σ * (|p m |d m ) -2α1 + L 2 2 2σ 2 * |p m | -2α2 + log 1+ǫ n n D m + R n .
If α 1 < α 2 , we can take

|p m |d m = L 2 1 n 2σ * log 1+ǫ n 1/(1+2α1) and |p m | = L 2 2 n 2σ 2 * log 1+ǫ n 1/(1+2α1)
.

For α 1 α 2 , this choice is not allowed because it would imply d m = 0. So, in this case, we take

d m = 1 and |p m | = (L 2 1 σ * + L 2 2 )n 2σ 2 * log 1+ǫ n 1/(1+2α2)
.

In the two situation, we obtain the announced result.

Technical results

This section is devoted to some useful technical results. Some notations previously introduced can have a different meaning here.

Lemma 10. Let Σ be a positive symmetric n × n-matrix and σ 1 , . . . , σ n > 0 be its eigenvalues. Let P be an orthogonal projection of rank D 1. If we denote M = P ΣP , then M is a non-negative symmetric matrix of rank D and, if τ 1 , . . . , τ D are its positive eigenvalues, we have Proof. We denote by Σ 1/2 the symmetric square root of Σ. By a classical result, M has the same rank, equal to D, than P Σ 1/2 . On a first side, we have max On the other side, we can write min

1 i D τ i = min V ⊂R n dim(V )=n-D+1 max x∈V x =0 M x, x x 2 = min V ⊂R n dim(V )=n-D+1 max x∈V x =0 Σ 1/2 P x 2 x 2 min V ⊂R n dim(V )=n-D+1 max x∈V ∩im(P ) x =0 Σ 1/2 x 2 x 2 min V ′ ⊂R n dim(V ′ ) 1 max x∈V ′ x =0 Σ 1/2 x 2
x 2 = min The function ϕ(u) is equal to 1 at u = 0 and tends to 0 as u goes to 1. Moreover, we easily compute its derivative

b i ε i ) 2 , then E 1 Z 1 E[Z] 1 + 8θ 2 b (n -2θ 2 b ) (n -
ϕ ′ (u) = 2ϕ(u) 1 -u 1 - nu 4θ 2 b (1 -(1 -1/θ b )u) 2 2ϕ(u) 1 -u 1 - nu 4θ 2 b 2 (1 -u) 3 1 - nu 4θ 2 b .
(5.1)

By integration by parts, we obtain

E 1 Z 1 2b * K 1 +

Fig 1 :Fig 2 :Fig 3 :Fig 4 :

 1234 Fig 1: Estimation on the mean (left) and the variance (right) in the case M1.

  γ

Theorem 4 .

 4 Let α ∈ (0, 1) and consider a collection of positive weights {x m } m∈M . If the hypothesis (H θ ) is fulfilled and if ∀m ∈ M, pen(m) γθD m + x m , (4.2)

4 ) implies log 1 + |p m |x m 5γn |p m |x m 5 (

 415 δ|p m | + 1)γn x m 5(δ + 1)γn .

  F I where the F I 's are i.i.d. Fisher random variables of parameters (d m , n/|p m |d m -1). Let us note that γ 2 D m γ|p m |d m E[W ′ 1 (m)] γθ|p m |d m γθD m .

Lemma 11 .

 11 Let ε be a standard Gaussian vector in R n , a = (a 1 , . . . , a n ) ′ ∈ R n and b 1 , . . . , b n > 0. We denote by b * (resp. b * ) the maximum (resp. minimum) of the b i 's and θ b b * /b * . If n > 4θ 2 b and Z = n i=1 (a i + √

4θ 2 b ) 2 .

 2 Proof. Note that E[Z] = n i=1 (a 2 i + b i ). For all x > 0, we define r(x) = log(1 + x)-x/(1+x), r is non-negative and increasing. Consider λ > 0, we upper bound the Laplace transform of Z, ψ(λ) = E[e -λZ ] * ) . Denoting by K = E[Z]/(2b * ), we get the following inequalities: e -Kt dt imsart-ejs ver. 2007/12/10 file: meavar.hyper28178.tex date: July 16, 2008 X. Gendre/Simultaneous estimation of the mean and the variance 25 where t = 2λb * /(1 + 2λb * ) and, for all u ∈ [0, 1),

1 0ϕ

 1 ′ (t)e -Kt dt and, because 4θ 2 b < n and (5.1), we get

Table

	1	1.5	2	2.5	3
	M1 1.81 1.56 1.20 1.47 1.49
	M2 1.34 1.38 1.46 1.73 1.86
	M3 2.21 1.99 1.63 1.61 1.87
	M4 1.27 1.33 1.16 1.32 1.67

  is obvious that the hypothesis (H θ ) ensures d m |I|/2. Thus, we get σ * d m (|I| -d m )σ * and

	E [K(P s,σ , P ŝm,σm )]	1 2 I∈pm	|I|σ * d m (|I| -d m )σ *	|p m |d m 2γ	D m 4γ	.

To conclude, we know that (ŝ m , σm ) ∈ S m × Σ m and, by definition of (s m , σ m ), it implies E [K(P s,σ , P ŝm,σm )] E [K(P s,σ , P sm,σm )] .

  ejs ver. 2007/12/10 file: meavar.hyper28178.tex date: July 16, 2008 X. Gendre/Simultaneous estimation of the mean and the variance where the X I 's are i.i.d. random variables of law χ 2 (|I| -d m -1) /|I|. Let t > 0, the first expectation is dominated by

imsart-ejs ver. 2007/12/10 file: meavar.hyper28178.tex date:July 16, 2008