Pierre Holat

Marc Plantevit

Chedy Raïssi

Nadi Tomeh

Thierry Charnois

Bruno Crémilleux

Sequence Classification Based on Delta-Free Sequential Pattern

Keywords: sequence mining, free patterns, text classification, feature selection, early classification

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

I. INTRODUCTION

Sequence classification is an important component of many real-world applications where information is structured into sequences [START_REF] Xing | A brief survey on sequence classification[END_REF]. In biology, for instance, classifying DNA or protein sequences into various categories may help understanding their structure and function [START_REF] Deshpande | Evaluation of techniques for classifying biological sequences[END_REF], while in medicine, classifying times series of heart rates may help identifying pathological cases [START_REF] Wei | Semi-supervised time series classification[END_REF]. Similarily, classifying textual documents into different topic categories is essential in many natural language processing (NLP) and information retrieval (IR) applications [START_REF] Aggarwal | A survey of text classification algorithms[END_REF], [START_REF] Sebastiani | Machine learning in automated text categorization[END_REF]. However, sequence classification is a challenging task for several reasons, which we address in this paper.

First, the task of feature selection [START_REF] Liu | Computational Methods of Feature Selection (Chapman & Hall/Crc Data Mining and Knowledge Discovery Series[END_REF], which is an important step in many classification approaches that operate on a feature-based representation of the data, is not trivial. A simple approach would be to consider each item of the sequence as a feature. However, the sequential nature of the sequence and the dependencies between individual items cannot easily modeled. While more complete information can be captured by considering all possible sub-sequences instead of individual items, the exponential growth of the number of such subsequences is computationally prohibitive and results in sparsity issues. A simple middle-ground solution is to consider short segments of consecutive items, called n-grams as features [START_REF] Chuzhanova | Feature selection for genetic sequence classification[END_REF], [START_REF] Leslie | The spectrum kernel: A string kernel for svm protein classification[END_REF], however, the complete feature space is still not entirely explored.

Second, the classification accuracy may not be the only criterion we wish to optimize. In their key paper [START_REF] Xing | Mining sequence classifiers for early prediction[END_REF], Xing et al., discuss the notion of early prediction for sequence classifiers. The authors note that: "a reasonably accurate prediction using an as short as possible prefix [..] of a sequence is highly valuable". This is an important condition for critical applications that need to supervise and classify sequences as early as possible. For instance, in diagnosing a disease from a sequence of records in medical tests, or in network intrusion or failure detection systems, it is obviously better to detect and classify a sequence of to be abnormal at the onset of the disease or the beginning of the network attack or failure.

These issues can be addressed by exploiting sequential pattern mining techniques which can efficiently explore the complete feature space. Sequential pattern mining is one of the most studied and challenging tasks in data mining. Since its introduction by Agrawal and Srikant in [START_REF] Agrawal | Mining sequential patterns[END_REF], many researchers developed approaches to mine sequences in different and various fields such as bioinformatics, customer marketing, web log analysis and network telecommunications. While the extraction of sequential patterns can be seen as an end in itself, it has been shown useful as a first step to build global classification models [START_REF]Parallel Universes and Local Patterns[END_REF]- [START_REF] Zaki | VOGUE: A variable order hidden markov model with duration based on frequent sequence mining[END_REF]. The idea behind this process is that the extracted sequential patterns are easily manipulated, understood and used as features or rules by classification methods and models [START_REF] Lesh | Mining features for sequence classification[END_REF]- [START_REF] Tseng | Effective temporal data classification by integrating sequential pattern mining and probabilistic induction[END_REF]. However, it is generally known that pattern mining typically yields an exponential number of patterns. Hence, many researchers focused on selecting a small subset of patterns with the same expressiveness power without jeopardizing the classification accuracy. Two of the most-used concise representations, the free and closed patterns, find their origin in Galois lattice theory and Formal Concept Analysis. A set of patterns is said to form an equivalence class if they are mapped to the same set of objects (or transactions) of a data set, and hence have the same support. The maximal element of an equivalence class is usually referred to as the closed pattern of the equivalence class. On the contrary, a free pattern (or generator) is a minimal element of the equivalence class. The authors in [START_REF] Li | Minimum description length principle: Generators are preferable to closed patterns[END_REF] studied and compared the efficiency of generators and closed patterns and concluded that "generators are preferable in inductive inference and classification when using the Minimum Description Length principle". In the case of sequential patterns (as opposed to itemset patterns), no previous work tries to compare the different concise representations because the methods are not easy to transpose. However, depending on the support parameter, the number of free patterns may still be prohibitively large.

In this paper we solve this problem by introducing a new algorithm for the extraction of free patterns. We show the usefulness of these patterns in addressing the two issues of sequence classification mentioned above, namely: feature selection and earliness optimization. The contribution of this paper is thus three-fold.

First, in Section II we shed new light on the problem of concise representations for sequences by analyzing the usage of δ-free sequences, with δ being a parameter that allows to group equivalence classes with similar support values, and hence provide finer control on the number of extracted patterns. This is the first study to extend the notion of freeness to sequences. We introduce and discuss properties showing that δfree sequences are indeed an efficient condensed representation of sequences and introduce a new algorithm to compute them. Second, in Section III, we describe a pipeline approach to textual document classification that uses δ-free patterns as features, and show that it outperforms other feature selection baseline methods while using smaller number of features. Third, in Section IV, we show that δ-free patterns are efficient to build a sequence classifier that optimizes both accuracy and earliness. This classifier is based on special rules called δstrong sequence rules. We present a novel technique to select the best δ-strong rules from δ-free patterns.

II. MINING δ-FREE SEQUENTIAL PATTERNS

In this section we present a novel algorithm to extract δ-free patterns from a database of sequences. We start by formalizing the problem and providing the necessary definitions in Sections II-A and II-B. We then describe the algorithm in Section II-C and analyze its performance Section II-D.

A. Definitions and problem description

Let I = {i 1 , i 2 . . . i m } be the finite set of items. An itemset is a non-empty set of items. A sequence S over I is an ordered list it 1 , . . . , it k , with it j an itemset over I, j = 1 . . . k. A k-sequence is a sequence of k items (i.e., of length k), |S| denotes the length of sequence S and S[0, l] denotes the l-sequence identified as a prefix of sequence S. T(I) will denote the (infinite) set of all possible sequences over I and L denotes the set of labels, or classes. A labeled sequence database D over I is a finite set of triples (SID, T, C), called transactions, with SID ∈ {1, 2, . . .} an identifier, T ∈ T(I) a sequence over I and C ∈ L is the class label associated to the sequence T . Let s = e 1 , e 2 , . . . , e n be a sequence. We denote by s (i) = e 1 , . . . , e i-1 , e i+1 , . . . , e n , the sequence s in which the i th elements is deleted. '•' denotes the itemsetappend operation between 2 sequences and '-•' denotes the item-append operation between 2 sequences. For instance, Given a user-defined minimal frequency threshold σ, the problem of sequential pattern mining is the extraction of all the sequences S in D such that f req D S ≥ σ. The set of all frequent sequences for a threshold σ in a database D is denoted FSeqs(D, σ) 1 , For the sake of simplicity, we limit our examples and discussions to sequences of items, but all our propositions and theorems hold for the general case of sequences of itemsets.

Definition 2.1 (Inclusion

): A sequence S = is 1 is 2 . . . is n is a subsequence of another sequence S = is 1 is 2 . . . is m , denoted S S, if there exist i 1 < i 2 < . . . i j . . . < i n such that is 1 ⊆ is i1 , is 2 ⊆ is i2 . . . is n ⊆ is in .
FSeqs(D, σ) = {S | f req D S ≥ σ} TABLE I. THE SEQUENCE DATABASE USED AS THE RUNNING EXAMPLE. S1 (a)(b)(c)(d)(a)(b)(c) + S2 (a)(b)(c)(b)(c)(d)(a)(b)(c)(d) + S3 (a)(b)(b)(c)(d)(b)(c)(c)(d)(b)(c)(d) + S4 (b)(a)(c)(b)(c)(b)(b)(c)(d) + S5 (a)(c)(d)(c)(b)(c)(a) - S6 (a)(c)(d)(a)(b)(c)(a)(b)(c) - S7 (a)(c)(c)(a)(c)(b)(b)(a)(e)(d) - S8 (a)(c)(d)(b)(c)(b)(a)(b)(c) -

B. δ-free sequential patterns

The notion of minimal patterns according to a constraint has already been explored for more than a decade in the itemset framework. In this context, the free patterns (also called minimal generators) are the minimal patterns according to the frequency measure. In order to accept some few exceptions, this notion is generalized with the δ-free patterns introduced and studied in [START_REF] Boulicaut | Free-sets: A condensed representation of boolean data for the approximation of frequency queries[END_REF]. To the best of our knowledge, this notion of δ-freeness was never introduced or defined in the context of sequences. In the following, we extend this notion to sequences.

Definition 2.5 (δ-free sequential patterns): Given a sequence database D, a sequence s is δ-free if:

∀s ≺ s, Support(s , D) > Support(s, D) + δ
The δ-free sequential patterns are especially interesting in real-world domains where few exceptions often appear and data sets often contain missing, incorrect or uncertain values. By using δ-free sequential patterns, one takes a more pragmatic approach to the extraction of sequential patterns towards the final goal of classification. Furthermore, this new type of pattern is also appealing from an implementation point of view as it helps maintaining very fast runtimes. Note also that a δfree sequential pattern is a sequence that cannot be represented as a rule accepting less than δ errors.

Given the sequence database D ex (Table I), Figure 1 represents all 1-free sequential patterns (in bold) having a support greater or equal to 3. For instance, (b)(d)(b) 3 is a 1-free sequence whereas sequence (b) 8 is not 1-free since it has the same support as 8 . The next subsection presents an algorithm that efficiently mines δ-free frequent sequences.

C. DEFFED : a new extraction algorithm

To understand the underlying complexity gap between itemsets and sequences representations, one can notice that the set of frequent free patterns is a concise representation of the frequent itemsets that can be efficiently obtained thanks to an anti-monotonicity property. However, this is not true anymore for sequences. The next property highlights this fundamental difference and the complex algorithmic challenges that result.

Property 2.6: Anti-monotonicity property does not hold for δ-free sequences.

A simple illustration from our running example suffices to show that sequence (a) is not 1-free whereas sequence (a)(a) is 1-free. As a consequence, it is impossible to use counting inference for sequences with δ-free patterns. Note that this property meets the pessimistic results of [START_REF] Raïssi | Mining conjunctive sequential patterns[END_REF]. Sequence generators [START_REF] Gao | Efficient mining of frequent sequence generators[END_REF], [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF] are a particular case of δ-free sequence (i.e., δ = 0). In [START_REF] Gao | Efficient mining of frequent sequence generators[END_REF], [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF], the authors introduced a monotonous property for a subset of non-generator sequences. We extend this property to δ-free sequences. This generalization is based on the notion of δ-equivalence of projected databases. This definition can be exploited to produce a monotone property of some non δ-free sequences: Property 2.8: Let s and s be two sequences. If s ≺ s and D |s ≡ δ D |s , then no sequence with prefix s can be δ-free.

Proof: (By contradiction) Let s and s be two sequences such that s ≺ s, Support(s , D) -Support(s, D) ≤ δ and D |s ≡ δ D |s . Assume that there exists a sequence s p = s • s c that is δ-free. Since D |s ≡ δ D |s , there exists a sequence s = s • s.c such that Support(s , D) -Support(s p , D) ≤ δ. This leads to a contradiction to the assumption that s p is δ-free. Property 2.8 is very interesting as it avoids the exploration of unpromising sequences. Furthermore, the verification of δequivalence of projected databases can be restricted only to subsequence of length n -1 as stated in Property 2.9: Property 2.9 (Backward pruning): Let s p = e 1 , e 2 , . . . , e n be a prefix sequence. If there exists an integer i (1

≤ i < n -1) such that D |sp ≡ δ D |s (i) p
, then the exploration of the sequence s p can be stopped since there is no other δ-free sequential patterns in S with prefix s p that can be discovered. Property 2.9 enables the efficient pruning of unpromising sequences and can be trivially included in any algorithm mining free sequential patterns.

Property 2.10: Let s p = e 1 , e 2 , . . . , e n be a prefix sequence. If s p is δ-free then s p cannot be pruned (unpromising). Proof: If s p is δ-free then there exists no integer i such that Support(s p , D) + δ < Support(s p (i) , D). Hence, there exists no integer i such that s p ≡ δ s p (i) and the pruning of s p cannot be applied.

While these properties enable the full exploitation of the monotonous property of some non δ-free sequences, one can also take benefit of the combination of two constraints: the δ-freeness and the frequency. In the case where sequences are within the neighborhood of the positive border of the frequent sequences, the combination of the two constraints can be used as stated in the following property.

Property 2.11: Let σ be the minimum support threshold. Let s p be a sequence such that σ ≤ Support(s p , D) ≤ σ + δ, then the exploration of the sequence s p can be stopped.

Proof: It is easy to prove that sequences with prefix s p cannot be both frequent and δ-free.

Both Properties 2.9, 2.10 and 2.11 are used as pruning techniques in Algorithm of Figure 2 called DEFFED (DElta Free Frequent sEquence Discovery). In the same spirit as Bide algorithm for closed sequential patterns [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF], DEFFED mines frequent δ-free sequences without candidate maintenance. It adopts a bi-directional checking to prune the search space deeply. DEFFED only stores a set of frequent sequences that are δ-free. This is a huge advantage compared to the generateand-prune algorithms that would not otherwise handle the impressive number of non δ-free frequent sequences. In addition, it is important to note that δ-free sequences do not provide a condensed representation of frequent sequential patterns. They have to be combined with other patterns (maximal frequent sequential patterns) to exclude some infrequent patterns.

To discover the complete set of frequent δ-free sequential patterns in sequence database D (i.e., all the frequent δ-free sequence with prefix ), algorithm DEFFED must be launched as follows: DeFFeD(σ, δ, , D, { |D| }). Indeed, |D| is, by definition, the smallest δ-free sequential pattern. Algorithm DEFFED first scans the sequence database to find the frequent 1-sequences (Line 1). Then, it treats each frequent 1-sequence (Line 4) as a prefix and check if the prefix sequence is δ-free (Line 9). Finally, if the prefix sequence is worth being explored (tests in Lines 15 and 21), the algorithm is recursively called on the prefix sequence. if ¬is f ree then 15:

if integer i -D |s p ≡ δ D |s p (i) then 16:
unpromising ← ; end if 25: end for (b) How does DEFFED compare to state-of-the-art algorithms BIDE [START_REF] Wang | Bide: Efficient mining of frequent closed sequences[END_REF] and PrefixSpan [START_REF] Pei | Prefixspan: Mining sequential patterns efficiently by prefix-projected pattern growth[END_REF]?

All the experiments were performed on a cluster and DEFFED , BIDE and PrefixSpan were implemented in Java. Nodes are equipped with 8 processors at 2.53GHz and 16Go of RAM under Debian operating Figure 3 shows the impact of δ with respect to the minimal support threshold σ on the memory usage. As previously discussed with higher δ, the number of extracted sequential patterns tends to get very low. The consumption of memory follows this behavior in 3(c). But not with the generated data sets because the δ parameter is not high enough (in comparison to the number of sequences) to impact the number of extracted patterns. This space management via the δ parameter can be very useful in systems where memory is a core issue (i.e. embedded systems, sensors), again in these cases, a high parameter δ can help pushing the extraction process to very low supports.

One remaining issue is the comparison of DEFFED with well-known and efficient approaches (i.e., BIDE for closed frequent sequence and PrefixSpan for frequent sequences). From a theoretical point of view, nothing can be stated about the cardinality of the set of frequent delta-free sequences in comparison to the set of frequent closed sequences (the 0-free sequences are the minimal sequences in a support equivalence class, while closed sequences are the maximal ones). However, in Figure 4, one can notice the efficiency of the DEFFED in terms of runtime and in Figure 4(a), with a small error value δ = 5 or δ = 10, the number of extracted patterns is drastically lower than closed sequences. Notice that the P remierLeague data set is very dense which explains the very high runtime values. For instance, for σ = 0.75, BIDE takes more than 250 million milliseconds (69 hours) to complete the extraction process.

III. DEFFED FOR FEATURE SELECTION

In this section we investigate the utility of δ-free patterns as features in a supervised text classification task. We describe our classification approach in Section III-A and discuss our experiments in Section III-B.

A. A supervised classification approach

We follow [START_REF] Nigam | Using maximum entropy for text classification[END_REF] and employ a maximum entropy (MaxEnt) framework to model the probability of a category label c given a sequence s according to Equation 1.

P (c|s) = 1 Z(s, θ) exp{ |θ| k=1 θ k,c g k (s)} (1)
The partition function Z acts as a normalizer; each g k is a binary feature function which returns 1 if the feature k ∈ K is present in the sequence s and 0 otherwise; and the parameter θ We run the extraction algorithm on each subset D c independently, and construct the set of δ-free patterns which we call K c . We aggregate all such sets to construct the set of features to be used by the classifier K = ∪ c {K c }. The ability to produce an accurate estimation of the model parameters θ depends heavily on their number and the sparsity of the data, which is directly related to the number of patterns produced by DeF F eD. We compare the δ-free based approach to building K with several selection approaches, including using individual items (bag of word) or contiguous short segments (n-grams) as features. The classification performance is evaluated using the well-known F-measure.

B. Experiments

We report an experimental evaluation of our approach by doing text classification using a real data set proposed by the French Laboratory LIMSI during the DEFT'2008 evaluation campaign 1 . The corpus statistics are given in Table III. Each document is modeled as a sequence and the set of possible categories for each document is C = {sport, economy, television, art}. The sources of those documents are articles from the French newspapers "Le Monde" and the online free encyclopedia "Wikipedia". We use the Wapiti2 [START_REF] Lavergne | Practical very large scale CRFs[END_REF] implementation of the MaxEnt classifier in its default settings. Table IV presents the results of our text classification experiments. With the baseline approaches to feature selection, the best performance we were able to achieve is using all contiguous patterns, without gaps between the individual items in the source sequence and with a maximum size of 7, as features. The baseline approach did not scale up to include patterns with gaps due to memory limitations. We also compared our method with the VOGUE method [START_REF] Zaki | VOGUE: A variable order hidden markov model with duration based on frequent sequence mining[END_REF]. VOGUE is a variable order and gapped Hidden Markov Model (HMM) with duration. It uses sequence mining to extract frequent patterns in the data. It then uses the mined patterns to build a variable order HMM with explicit duration on the gap states for sequence modeling and classification. The implementation (available on the author's website3 ) uses the python extension module Psyco4 to speed up the computation, which is unmaintained and only available for 32bit systems. Therefore it is limited to 4Go of RAM, hence the really bad F-measure on a large data set like DEFT. The baseline experiments also include some basic features selection: frequents patterns extraction with an absolute minimal support σ = 5. We can see that this features selection reduces the number of features but at the cost of some accuracy. However the use of a delta threshold of δ = 10% (relative to the number of documents) results in comparable performances to the best baseline approach in terms of Fmeasure, while reducing dramatically the number of features. We can see on Figure 5 that with higher values of the minimum support σ the classification is really inefficient, as expected when using only patterns that are "too" frequent. But we can also see that the threshold δ enhances the classification. The experiments were done with different minimal support values: 0.01%, 0.025%, 0.05%, 0.1%, 0.2%, 0.4%, 0.8%, 1.6%, 3.2%, 6.4%, 12.8% and 25.6% and δ values of 0%, 0.025%, 0.05%, 0.1%, 0.2%, 0.4%, 0.8%, 1.6%, 3.2%, 6.4%, 12.8%, 25.6% and 51,2% w.r.t to the number of documents of the corpus. Figure 6 highlights the effect of of low thresholds on the F-measure. The noticeable drop of the F-measure at δ = 0, σ = 0.01% and 0.025% is because the extraction returns too many patterns to be handled as features by the classifier. However with δ > 0, DEFFED is able to produce a low number of features to be processed by the classifier even with a low minimal support of σ = 0.01%. Figure 7 is a more complete view of the effects of δ on the F-measure (δ from 0 to 1 with 0.02 steps, σ = 0.005%). With a δ = 1 (100%), the only δ-free sequence is the empty pattern . There are no features to process, hence the F -measure = 0. of sequential patterns with σ = 0.01% and δ = 0 failed because of the large number of patterns to explore. However, when δ > 0, we are able to extract the δ-free patterns even with a minimum support as low as σ = 0.01%, whereas it is not possible in the absence of the δ parameter (i.e., δ = 0). We can see in Figure 9, which represent the running time of our algorithm on the DEFT data set, that the δ-freeness also play a major role in the efficiency of the extraction process. The experiments described in this section provide an empirical evidence on the usefulness of DEFFED as a feature selection method which results in a much smaller number of features without sacrificing the classification performance.

IV. DEFFED FOR EARLY PREDICTION

In this section we introduce the δ-strong sequential rules and our early-prediction sequence classifier. We show that the δ-free sequences are very efficient to build early prediction sequence classifiers that rely on high accuracy of the prediction coupled with minimal costs. We discuss our experiments in Section IV-B.

A. Sequential classification rules based on δ-free sequential patterns

A sequential classification rule r is an implication of the form r : s → c in which the premise of the rule is a sequence from T(I) and the conclusion c is a class label from L. Such a rule can be evaluated with the usual support-based measures which are based on the support of the sequence s in the partition of the data set which contains class label c (denoted Support(s, D c )). The confidence of a sequential rule is Confidence(r, D) = Support(s,Dc) Support(s,D) .

Sequence database D can then be partitioned into n subsets D i where D i contains all data sequences related to class label c i ∈ L. A sequential δ-strong rule is an implication of the form r : s → c i if, given a minimum support threshold σ and an integer δ, the following conditions hold: Support(s, D) ≥ σ and Support(s, D) -Support(s, D i ) ≤ δ A δ-strong rule accepts at most δ errors, that is, its confidence is lower-bounded:

1 -δ σ ≤ Confidence(s → c i , D) ≤ 1.
Given the property of minimality of the δ-free patterns that we present in section II-B, if we use a δ-free pattern as a premise of a δ-strong rule we are ensuring that there does not exist s ≺ s such that s is the premise of a δ strong rule. By considering the property of minimal body, the number of sequential rules is highly reduced. To understand that, observe that for a given δ-strong sequential rule s → c i , the following inequalities hold,

Support(s, D) ≥ σ ; Support(s, D\D i ) ≤ δ ; Support(s, D i ) ≥ σ -δ .
In particular,

σ -δ ≤ Support(s, D) ≤ |D i | + δ
Minimal δ-strong sequential classification rules also satisfy interesting properties on rule conflicts. Indeed, several rule conflicts properties proved in [START_REF] Crémilleux | Simplest rules characterizing classes generated by delta-free sets[END_REF] also hold for sequential patterns. When inequality δ < σ 2 is respected, it is obvious that it will be impossible to find a specialization of a premise leading to a different conclusion, i.e., a different class label.

For the selection of the best δ-strong rules, we have to use a set of rules avoiding classification conflicts. Thanks to the properties of the δ-free sequential patterns, if δ < σ 2 , we cannot have two δ-strong sequential classification rules r 1 : s → c and r 2 : s → c such that s s and c = c .

Early prediction oriented sequence classifiers have to process itemsets from a sequence in a consecutive and progressive way. Obviously, these classifiers rely, for the prediction, exclusively on the prefix of a sequence. Each sequence itemset i, processed by a classifier is associated with a cost value c(i). The total cost of prediction for a sequence S, denoted c(S), is the sum of the costs of each item in the minimal prefix sequence to achieve the classification task.

According to early prediction purpose, we assume that new sequences arrive item by item. The goal of the early prediction is to associate a class label to the new sequence as soon as possible. At each update of the new unclassified sequence, the classifier tries to match the sequence to the premises of the rules. The best way to directly focus on the new incoming item of the sequence is to store the δ-strong rules of the classifier in a suffix tree structure. The suffix tree stores all the rules of the classifier. The leaves of the tree contain class labels and support information. The use of a suffix tree to store δ-strong rules enables to directly concentrate on promising rules. Notice that suffix tree structure was successfully applied by [START_REF] Sun | Mining for outliers in sequential databases[END_REF] to approximate sequence probabilities and discover outliers in sequence databases.

B. Experiments

We report qualitative results of our early-based sequence classifier over real-world data sets. The different data sets used for the experiments and their parameters are summarized in table V. The SEN SOR and P ION EER data sets are downloaded from the UCI Machine Learning Repository. The data were collected through sensors as robots navigate through a room [START_REF] Frank | UCI machine learning repository[END_REF]. The data sets used in this experiment are discretized to meet the classical sequential patterns needs. In this set of experiments, we analyze the effectiveness of the classification in terms of accuracy and earlyness cost. The data sets ROBOT and P ION EER are first mined for δ-free sequential patterns, then the early-prediction sequence classifier is built upon carefully selected δ-strong rules as discussed previously. Table VI presents the different extraction results and the classification results. For the ROBOT data set, the optimal results are obtained with a minimal support of 0.05 and δ = 20. The average prediction costs in this precise case is 8.7043 meaning that the classifier needs in average to read 9 items before predicting the sequence's class. Notice that in average in this data set a sequence contains 24 items, so our classifier needs a little bit more than the third of the sequence to be able to fire its prediction. Table VII presents the confusion matrix built from the evaluation of this data set with σ = 0.05 and δ = 20 and 2 classes. The important thing is to notice that the third column contains all sequences that did not get classified by any rule. This may be caused by: (i) a high support threshold that is not low enough to find sequential patterns that will cover more data sequences or (ii) restrictive rule selection (via a black listing scheme) that favor some non-optimal covering leading to accuracy losses. The last experiment is presented in order to illustrate the weak point of our approach. Because the data set P ION EER contains a few but long data sequences, the minimal support that can be used to extract sequential patterns is indeed very high : 0.55. Here the δ value is attaining a critical case of almost σ 2 which generates rules of confidence 50% with a high rate of conflicts. This explains the very poor accuracy of 0.20625. Furthermore, any lower value of δ is not enough to generate an interesting set of δ-strong rules.

V. RELATED WORK

Since the key paper of Mannila and Toivonen [START_REF] Mannila | Multiple uses of frequent sets and condensed representations (extended abstract)[END_REF], subsequent research has focused on building concise representations for frequent patterns. That is, lossless subsets of frequent patterns with the same expressiveness power. However, most of the work (and results) focused on frequent itemset patterns (i.e., sets of items), mainly because of the deeper relations and understanding already developed in various mathematical fields like set theory, combinatorics, and Galois connections in order theory. Indeed, researchers introduced closed sets [START_REF] Pasquier | Discovering frequent closed itemsets for association rules[END_REF], free sets [START_REF] Boulicaut | Free-sets: A condensed representation of boolean data for the approximation of frequency queries[END_REF], and non-derivable itemsets [START_REF] Calders | Mining all non-derivable frequent itemsets[END_REF]. However, finding concise representations for structured data is a more challenging exercise as pointed out by the authors of [START_REF] Raïssi | Mining conjunctive sequential patterns[END_REF]. Closed patterns were successfully extended to sequence in [START_REF] Wang | Frequent closed sequence mining without candidate maintenance[END_REF], [START_REF] Yan | Clospan: Mining closed sequential patterns in large databases[END_REF], [START_REF] Fradkin | Margin-closed frequent sequential pattern mining[END_REF]. Recently, generator sequences were proposed in [START_REF] Gao | Efficient mining of frequent sequence generators[END_REF], [START_REF] Lo | Mining and ranking generators of sequential patterns[END_REF], [START_REF] Baralis | Compact representations of sequential classification rules[END_REF]. Subsequently, a general framework for minimal pattern mining was introduced by Soulet et al. in [START_REF] Soulet | Efficiently depth-first minimal pattern mining[END_REF], but this was limited to chains (i.e., sequences without gaps). Our first proposition in this paper (the DEFFED algorithm) is a generalization of sequence generators that are a particular case of δ-free sequences (δ = 0). Moreover, DEFFED is able to discover δ-free frequent sequences of itemsets whereas work about sequence generators are limited to sequence of items.

The classification of sequence data has been extensively studied [START_REF] Lesh | Mining features for sequence classification[END_REF]- [START_REF] She | Frequent-subsequence-based prediction of outer membrane proteins[END_REF], [START_REF] Grosskreutz | A relevance criterion for sequential patterns[END_REF]. Most previous work has combined sequence feature selection and common classification methods. For instance, the authors of [START_REF] Park | Prediction of protein subcellular locations by support vector machines using compositions of amino acids and amino acid pairs[END_REF], [START_REF] She | Frequent-subsequence-based prediction of outer membrane proteins[END_REF] study the prediction of outer membrane proteins from protein sequences by combining several feature selection methods and support vector machines (SVMs) [START_REF] Joachims | Text categorization with suport vector machines: Learning with many relevant features[END_REF]. Other methods are based on Hidden Markov Models (HMM) which are stochastic generalizations of finitestate automata have been proposed for sequence classification [START_REF] Durbin | Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids[END_REF], [START_REF] Rabiner | A tutorial on hidden markov models and selected applications in speech recognition[END_REF]. In a paper by Zaki et al. [START_REF] Zaki | VOGUE: A variable order hidden markov model with duration based on frequent sequence mining[END_REF], the authors proposed the VOGUE method, which addresses the main limitations of HMMs. VOGUE is a two steps method: it first, mines sequential patterns and then builds HMMs based on the extracted features. Some criteria for feature selection are proposed in [START_REF] Lesh | Mining features for sequence classification[END_REF], [START_REF] Grosskreutz | A relevance criterion for sequential patterns[END_REF]. The authors of [START_REF] Lesh | Mining features for sequence classification[END_REF] use the confidence measure to quantify the features. Our work can lead to a generalization of this previous work by allowing the use of any frequencybased measure. In a similar way, Grosskreutz et al. [START_REF] Grosskreutz | A relevance criterion for sequential patterns[END_REF] showed the utility of minimum patterns for classification, but their approach is restricted to items for binary classifications. Other methods of classification rely on string kernels to extend methods such as SVMs [START_REF] Joachims | Text categorization with suport vector machines: Learning with many relevant features[END_REF] to be able to handle sequence data [START_REF] Watkins | Dynamic alignment kernels[END_REF], [START_REF] Leslie | The spectrum kernel: A string kernel for svm protein classification[END_REF]. However these approaches focus more on strings than general sequences, as in our work.

VI. CONCLUSION

We have studied in this paper a new type of patterns in sequential data, the δ-free sequential patterns. These patterns are the shortest sequences of equivalence classes on the support w.r.t the δ threshold. We described the anti-monotonicity property which does not hold in sequential data and we presented novel pruning properties based on the projected databases of the sequences. A correct and complete algorithm to mine these δ-free sequential patterns is tested and we show that the number of extracted patterns is greatly reduced compared to a frequent or closed patterns extraction approach. The δ-free sequential patterns are also extracted more efficiently in term of time and memory consumption.

We have then showed how δ-free patterns can be employed to address two problems related to sequence classification, namely feature selection in a statistical approach and early prediction in a symbolic approach. First, using the DEFFED algorithm for feature selection allows to explore the entire feature space and to retain only promising patterns. This method results in smaller and more interpretable classification while at the same time it contains richer information than simpler feature selection methods. Second, we have shown that δ-free patterns can be used to identify δ-strong symbolic classification rules with minimal prefix, which turn out to be highly efficient for early prediction by maximizing the earliness constraint.

In future work, we will investigate the use of δ-free sequential patterns in natural language processing problems in order to incorporate more information into the classification process, such as part-of-speech tags.

  (a)(b) • (b)(a) = (a)(b)(b)(a) and (a)(b) -• (c)(a) = (a)(b, c)(a) .

Definition 2 . 2 (

 22 Support): The support of a sequence S in a transaction database D, denoted Support(S, D), is defined as: Support(S, D) = |{(SID, T ) ∈ D|S T }|. The frequency of S in D, denoted f req D S , is f req D S = Support(S,D) |D| .

Example 2 . 3 (

 23 Running Example): In this paper, we use the sequence database D ex in Table I containing 8 data sequences with I = {a, b, c, d, e} and L = {+, -} as the running example. Sequence (a)(b)(a) is included in S 1 = (a), (b), (c), (d), (a), (b), (c) . Sequence S 1 is thus said to support (a)(b)(a) . Notice, however, that S 5 does not support (b)(d) as (b)(d) S 5 . In addition S 4 [0, 3] = (b)(a)(c) is the prefix of sequence S 4 of length 3.

Definition 2 . 4 (

 24 Projected database[START_REF] Pei | Mining sequential patterns by pattern-growth: The prefixspan approach[END_REF]): Let s p be a sequential pattern in sequence database D. The s p -projected database, denoted as D |sp , is the collection of suffixes of sequences in D having the prefix s p .Note that the prefix of a sequential pattern s p within a data sequence S is equal to the subsequence of S starting at the beginning of S and ending strictly after the first minimal occurrence of s p in S[START_REF] Mannila | Discovery of frequent episodes in event sequences[END_REF]. In the running example, D ex| (a)(b)(a) = { (b)(c) , (b)(c)(d) , , , , (b)(c) , (e)(d) , (b)(c) }.

Fig. 1 .

 1 Fig. 1. The enumeration tree of the Frequent 1-Free sequential patterns on D (σ = 3)

Definition 2 .

 2 7 (δ-equivalence of projected databases): Let s and s be two sequences, Their respective projected database D |s and D |s are said δ-equivalent (denoted by D |s ≡ δ D |s ) if they have at most δ different suffixes.

  Data : σ, δ, prefix sequence s p and its projected database D |sp , F F S Result : F F S∪ The set of frequent δ-free sequences with prefix s p 1: LF I ← frequent 1-sequences(D |sp , σ); 2: is f ree ← ⊥; 3: unpromising ← ⊥; 4: for all item e ∈ LF I do 5: s p = s p • e ; 6: D |s p ← pseudo projected database(D |sp , s p ); 7: if Support(s p , D) + δ < Support(s p , D) then 8: //potentially δ-free 9: if integer i and Support(s p (i) , D) -δ > Support(s p , D) then 10: F DS ← F DS ∪ {s p }; 11: is f ree ← ;

  if it is possible to find frequent δ-free sequences (property 2.11 )*/ 21: if Support(s p , D) > σ + δ then 22:Call DEFFED (σ, δ, s p , D |s p , F F S);

Fig. 2 .

 2 Fig. 2. Algorithm DeFFeD (DElta Free Frequent sEquence Discovery)

Fig. 4 .

 4 Fig. 4. Comparison between BIDE, PrefixSpan and DEFFED .

  k,c ∈ θ associates a weight to each feature in a given category. The classification task amounts to searching for the most probable category ĉ ∈ C according to the rule ĉ = arg max c∈C P (c|s). The parameters θ of the MaxEnt model are learned during training on a corpus of n labeled sequences D = {(s i , c i )} n i=1 . The DEFFED algorithm intervene in this approach when computing the set of features K used by the classifier. During training, we divide the training corpus by categories into distinct subsets such that D = ∪ c {D c }.

Fig. 5 .

 5 Fig. 5. Effects of the δ-freeness and minimal support (σ) parameters on the F-measure

Fig. 7 .

 7 Fig. 7. Detailed effect of δ-freeness (0 to 100%) on classification F-measure with a minimal support of 0.05%

Fig. 8 .

 8 Fig. 8. Effect of δ-freeness and minimal support (σ) on the number of extracted patterns

Fig. 9 .

 9 Fig. 9. Effect of δ-freeness and minimal support (σ) on extraction time

TABLE II .

 II DIFFERENT DATA SETS USED FOR THE EXPERIMENTS.

	Data Set	Items	Avg. size	Avg. size	# of data
			of itemsets	of sequences	sequences
	S50TR2SL10IT10K	10000	2	10	50000
	S100TR2SL10IT10K	10000	2	10	100000
	PremierLeague	240	2	38	280

TABLE III .

 III DETAILS OF THE DEFT DATA SET.

	Data Set	# of documents	# of words	# of distincts words
	Training set	15,223	3,375,888	161,622
	Test set	10,596	2,306,471	128,377

TABLE IV .

 IV TEXT CLASSIFICATION RESULTS. δ AND THE MINIMUM SUPPORT σ ARE THE PARAMETERS OF THE EXTRACTION ALGORITHM.

		Model	σ	δ	F-measure	# of model parameters	Model size
		bag of word	0	-	0.863	646.488	21Mb
	Baselines	frequent word 4-gram (no gap) frequent 4-gram (no gap)	5 0 5	---	0.865 0.870 0.865	210.820 33.967.272 477.188	7Mb 1306Mb 21Mb
		7-gram (no gap)	0	-	0.853	73.060.660	3036Mb
		frequent 7-gram (no gap)	5	-	0,865	483.464	16Mb
		VOGUE (gap max. of 5)	0.05%	-	0,23	-	1902Mo
	DEFFED	0-free 10%-free	0.05% 0.05%	0 10%	0,823 0.870	104.240 26.764	4Mb 0.8Mb

TABLE V .

 V DIFFERENT DATA SETS USED FOR THE EXPERIMENTS.

	Data Set	Items	Avg. size	Avg. size	# of data sequences
		Items	of itemsets	of sequences
	ROBOT	102	1	20	5456
	PIONEER	350	1	72	159

TABLE VII .

 VII CONFUSION MATRIX FOR DATA SET ROBOT WITH σ = 0.05 AND δ = 20.

		Predicted A	Predicted B	Unknown
	Class A	1745	150	310
	Class B	161	1936	0

TABLE VI .

 VI DIFFERENT CLASSIFICATION RESULTS WITH VARYING δ, σ PARAMETERS.

	Data Set	σ	δ	# frequent δ-free	# δ-strong rules	# classifier rules	Early pred. cost	Avg. pred. cost per sequence	Accuracy
	ROBOT	0.2	1	13	3	3	28496	6.6238	0.4867
	ROBOT	0.1	40	100	19	19	36146	8.4021	0.6052
	ROBOT	0.05	20	695	320	292	37446	8.7043	0.8556
	P ION EER	0.55	170	189	5	3	2327	14.54375	0.20625

In the case that σ is an integer, f req D S is defined w.r.t. Support(S, D). In the rest of the paper, σ is an integer if it is not specified.

http://deft.limsi.fr/2008

http://wapiti.limsi.fr/

http://www.cs.rpi.edu/ ∼ zaki/www-new/pmwiki.php/Software/Software

http://psyco.sourceforge.net/

ACKNOWLEDGMENTS

This work is supported by the French National Research Agency (ANR) as part of the project Hybride ANR-11-BS02-002 and the "Investissements d'Avenir" program (reference: ANR-10-LABX-0083).


Ronen Eldan

Joseph Lehec

Bounding the norm of a log-concave vector via thin-shell estimates

Chaining techniques show that if X is an isotropic log-concave random vector in R n and Γ is a standard Gaussian vector then

for any norm • , where C is a universal constant. Using a completely different argument we establish a similar inequality relying on the thinshell constant σn = sup Var(|X|); X isotropic and log-concave on R n .

In particular, we show that if the thin-shell conjecture σn = O(1) holds, then n 1/4 can be replaced by log(n) in the inequality. As a consequence, we obtain certain bounds for the mean-width, the dual mean-width and the isotropic constant of an isotropic convex body. In particular, we give an alternative proof of the fact that a positive answer to the thin-shell conjecture implies a positive answer to the slicing problem, up to a logarithmic factor.

Introduction

Given a stochastic process (X t ) t∈T , the question of obtaining bounds for the quantity E sup t∈T X t is a fundamental question in probability theory dating back to Kolmogorov, and the theory behind this type of question has applications in a variety of fields.

The case that (X t ) t∈T is a Gaussian process is perhaps the most important one. It has been studied intensively over the past 50 years, and numerous bounds on the supremum in terms of the geometry of the set T have been attained by Dudley, Fernique, Talagrand and many others.

The case of interest in this paper is a certain generalization of the Gaussian process. We consider the supremum of the process (X t = X, t ) t∈T where X is a log-concave random vector in R n and T ⊂ R n is a compact set. Throughout the article x, y denotes the inner product of x, y ∈ R n and |x| =

x, x the Euclidean norm of x. Our aim is to obtain an upper bound on this supremum in terms of the supremum of a corresponding Gaussian process Y t = Γ, t where Γ is a gaussian random vector having the same covariance structure as X.

Before we formulate the results, we begin with some notation. A probability density ρ : R n → [0, ∞) is called log-concave if it takes the form ρ = exp(-H) for a convex function H : R n → R ∪ {+∞}. A probability measure is logconcave if it has a log-concave density and a random vector taking values in R n is said to be log-concave if its law is log-concave. Two canonical examples of log-concave measures are the uniform probability measure on a convex body and the Gaussian measure. It is a well-known fact that any log-concave probability density decays exponentially at infinity, and thus has moments of all orders. A log-concave random vector X is said to be isotropic if its expectation and covariance matrix satisfy

E(X) = 0, cov(X) = id.
Let σ n be the so-called thin-shell constant:

σ n = sup X Var(|X|) (1)
where the supremum runs over all isotropic, log-concave random vectors X in R n . It is trivial that σ n ≤ √ n and it was proven initially by Klartag [K2] that in fact

σ n = o( √ n).
Shortly afterwards, Fleury-Guédon-Paouris [FGP] gave an alternative proof of this fact. Several improvements on the bound have been established since then, and the current best estimate is σ n = O(n 1/3 ) due to Guédon-Milman [Gu-M].

The thin-shell conjecture, which asserts that the sequence (σ n ) n≥1 is bounded, is still open. Another related constant is:

τ 2 n = sup X sup θ∈S n-1 n i,j=1 E X i X j X, θ 2 , (2)
where the supremum runs over all isotropic log-concave random vectors X in R n . Although it is not known whether τ n = O(σ n ), we have the following estimate, proven in [E]

τ 2 n = O n k=1 σ 2 k k . (3)
The estimate σ n = O(n 1/3 ) thus gives τ n = O(n 1/3 ), whereas the thin-shell conjecture yields

τ n = O( √ log n).
We denote by Γ the standard Gaussian vector in R n (with identity covariance matrix). We are now ready to formulate our main theorem.

Theorem 1. Let X be an isotropic log-concave random vector in R n and let • be a norm. Then there is a universal constant C such that

E X ≤ C log n τ n E Γ . (4)
Remark. It is well known that, as far as E X is concerned, there is no loss of generality assuming additionally that the support of X is contained in a ball of radius C 0 √ n for some sufficiently large constant C 0 (see for instance Lemma 8 below). Then it is easily seen that X satisfies the following ψ 2 estimate

P | X, θ | ≥ t) ≤ Ce -ct 2 / √ n , ∀t ≥ 0, ∀θ ∈ S n-1 ,
where C, c are universal constants. Combining this with chaining methods developed by Dudley-Fernique-Talagrand (more precisely, using Theorem 1.2.6. and Theorem 2.1.1. of [T]), one gets the inequality

E X ≤ C ′ n 1/4 E Γ ,
we refer to [Bou] for more details. This means that using the current best-known bound for the thin-shell constant: σ n = O(n 1/3 ), the above theorem does not give us anything new. On the other hand, under the thin-shell hypothesis we obtain using (3)

E X ≤ C log n E Γ .
As an application of Theorem 1, we derive several bounds related to the mean width and dual mean width of isotropic convex bodies and to the socalled hyperplane conjecture. We begin with a few definitions. A convex body K ⊂ R n is a compact convex set whose interior contains the origin. For x ∈ R n , we define

x K = inf{λ; x ∈ λK} to be the gauge associated to K (it is a norm if K is symmetric about 0). The polar body of K is denoted by

K • = {y ∈ R n ; x, y ≤ 1, ∀x ∈ K}.
Next we define

M (K) = S n-1 x K σ(dx), M * (K) = S n-1 x K • σ(dx),
where σ is the Haar measure on the sphere, normalized to be a probability measure. These two parameters play an important rôle in the asymptotic theory of convex bodies.

The convex body K is said to be isotropic if a random vector uniform on K is isotropic. When K is isotropic, the isotropic constant of K is then defined to be

L K = |K| -1/n ,
where |K| denotes the Lebesgue measure of K. More generally, the isotropic constant of an isotropic log-concave random vector is L X = f (0) 1/n where f is the density of X. The slicing or hyperplane conjecture asserts that L K ≤ C for some universal constant C. The current best estimate is L K ≤ Cn 1/4 due to Klartag [K1]. We are ready to formulate our corollary:

Corollary 2. Let K be an isotropic convex body. Then one has,

(i) M * (K) ≥ c √ n/( √ log n τ n ), (ii) L K ≤ Cτ n (log n) 3/2 ,
where c, C > 0 are universal constants.

Remark. Part (ii) of the corollary is nothing new. Indeed, in [EK], it is shown that L K ≤ Cσ n for a universal constant C > 0. Our proof uses different methods and could therefore shed some more light on this relation, which is the reason why we provide it.

Using similar methods, we attain an alternative proof of the following correlation inequality proven initially by Hargé in [H].

Proposition 3 (Hargé). Let X be a random vector on R n . Assume that E(X) = 0 and that X is more log-concave than Γ, i.e. the density of X has the form

x → exp -V (x) - 1 2 |x| 2
for some convex function V : R n → (-∞, +∞]. Then for every convex function ϕ : R n → R we have Eϕ(X) ≤ Eϕ(Γ).

The structure of the paper is as follows: in section 2 we recall some properties of a stochastic process constructed in [E], which will serve as one of the central ingredients in the proof of Theorem 1, as well as establish some new facts about this process. In section 3 we prove the main theorem and Proposition 3. Finally, in section 4 we prove Corollary 2.

In this note, the letters c, c, c ′ , C, C, C ′ , C ′′ will denote positive universal constants, whose value is not necessarily the same in different appearances. Further notation used throughout the text: id will denote the identity n×n matrix. The Euclidean unit sphere is denoted by S n-1 = {x ∈ R n ; |x| = 1}. The operator norm and the trace of a matrix A are denoted by A op and Tr(A), respectively. For two probability measures µ, ν on R n , we let T 2 (µ, ν) be their transportation cost for the Euclidean distance squared:

T 2 (µ, ν) = inf ξ R n ×R n |x -y| 2 ξ(dx, dy)
where the infimum is taken over all measures ξ on R 2n whose marginals onto the first and last n coordinates are the measures µ and ν respectively. Finally, given a continuous martingale (X t ) t≥0 , we denote by [X] t its quadratic variation. If X is R n -valued, then [X] t is a non-negative matrix whose i, j coefficient is the quadratic covariation of the i-th and j-th coordinates of X at time t.

Acknowlegements. The authors wish to thank Bo'az Klartag for a fruitful discussion and Bernard Maurey for allowing them to use an unpublished result of his.

The stochastic construction

We make use of the construction described in [E]. There it is shown that, given a probability measure µ having compact support and whose density with respect to the Lebesgue measure is f , and given a standard Brownian motion (W t ) t≥0 on R n ; there exists an adapted random process (µ t ) t≥0 taking values in the space of absolutely continuous probability measures such that µ 0 = µ and such that the density f t of µ t satisfies

df t (x) = f t (x) A -1/2 t (x -a t ), dW t , ∀t ≥ 0, (5)
for every x ∈ R n , where

a t = R n x µ t (dx), A t = R n (x -a t ) ⊗ (x -a t ) µ t (dx)
are the barycenter and the covariance matrix of µ t , respectively. Let us give now the main properties of this process. Some of these properties have already been established in [E], in this case we will only give the general idea of the proof. We refer the reader to [E, Section 2,3] for complete proofs. Firstly, for every test function φ the process

R n φ dµ t t≥0 is a martingale. In particular E R n φ dµ t = R n φ dµ, ∀t ≥ 0. ( 6
)
The Itô differentials of a t and A t read

da t = A 1/2 t dW t ( 7
)
dA t = -A t dt + R n (x -a t ) ⊗ (x -a t ) A -1/2 t (x -a t ), dW t µ t (dx). ( 8
)
Recall that µ is assumed to have compact support, and observe that the support of µ t is included in that of µ, almost surely. This shows that the processes (a t ) and (A t ) as well as the process involved in the local martingale part of equation ( 8) are uniformly bounded. In particular the local martingales of the last two equations are actually genuine martingales. Thus we get from ( 8)

d dt ETr(A t ) = -ETr(A t ).
Integrating this differential equation we obtain

ETr(A t ) = e -t Tr(A 0 ), t ≥ 0. ( 9
)
Combining this with (7) we obtain

E|a t | 2 = |a 0 | 2 + t 0 ETr(A s ) ds = |a 0 | 2 + (1 -e -t )Tr(A 0 ).
The process (a t ) t≥0 is thus a martingale bounded in L 2 . By Doob's theorem, it converges almost surely and in L 2 to some random vector a ∞ .

Proposition 4. The random vector a ∞ has law µ.

Proof. Let φ, ψ be functions on R n satisfying

φ(x) + ψ(y) ≤ |x -y| 2 , x, y ∈ R n . ( 10
) Then φ(a t ) + R n ψ(y) µ t (dy) ≤ R n |a t -y| 2 dy = Tr(A t ).
Taking expectation and using ( 6) and ( 9) we obtain

R n φ dν t + R n ψ dµ ≤ Tr(A 0 )e -t ,
where ν t is the law of a t . This holds for every pair of functions satisfying the constraint (10). By the Monge-Kantorovich duality (see for instance [START_REF] Villani | Optimal transport. Old and new, Grundlehren der Mathematischen Wissenschaften[END_REF]Theorem 5.10]) we obtain

T 2 (ν t , µ) ≤ e -t Tr(A 0 )
where T 2 is the transport cost associated to the Euclidean distance squared, defined in the introduction. Thus ν t → µ in the T 2 sense, which implies that a t → µ in law, hence the result.

Let us move on to properties of the operator norm of A t . We shall use the following lemma which follows for instance from a theorem of Brascamp-Lieb [START_REF] Brascamp | On extensions of the Brunn-Minkowski and Prékopa Leindler theorems, including inequalities for log concave functions, and with an application to the diffusion equation[END_REF]Theorem 4.1.]. We provide an elementary proof using the Prékopa-Leindler inequality.

Lemma 5. Let X be a random vector on R n whose density ρ has the form

ρ(x) = exp - 1 2 Bx, x -V (x)
where B is a positive definite matrix, and V : R n → (-∞ + ∞] is a convex function. Then one has, cov(X) ≤ B -1 .

In other words, if a random vector X is more log-concave than a Gaussian vector Y , then cov(X) ≤ cov(Y ).

Proof. There is no loss of generality assuming that B = id (replace X by B 1/2 X otherwise). Let Λ : x → log E(e x,X ).

Since log-concave vectors have exponential moment Λ is C ∞ in a neighborhood of 0 and it is easily seen that

∇ 2 Λ(0) = cov(X). ( 11
)
Fix a ∈ R n and define

f : x → a, x - 1 2 |x| 2 -V (x), g : y → -a, y - 1 2 |y| 2 -V (y), h : z → - 1 2 |z| 2 -V (z).
Using the inequality

1 2 a, x -y - 1 4 |x| 2 - 1 4 |y| 2 ≤ 1 2 |a| 2 - 1 8 |x + y| 2 ,
and the convexity of V we obtain

1 2 f (x) + 1 2 g(y) ≤ 1 2 |a| 2 + h x + y 2 , ∀x, y ∈ R n .
Hence by Prékopa-Leindler z) dz.

R n e f (x) dx 1/2 R n e g(y) dy 1/2 ≤ e |a| 2 /2 R n e h(
This can be rewritten as

1 2 Λ(a) + 1 2 Λ(-a) -Λ(0) ≤ 1 2 |a| 2 .
Letting a tend to 0 we obtain ∇ 2 Λ(0)a, a ≤ |a| 2 which, together with (11), yields the result.

Recalling ( 5) and applying Itô's formula to log(f t ) yields

d log(f t )(x) = A -1/2 t (x -a t ), dW t - 1 2 A -1 t (x -a t ), x -a t dt
This shows that the density of the measure µ t satisfies

f t (x) = f (x) exp c t + b t , x - 1 2 B t x, x (12)
where c t , b t are some random processes, and

B t = t 0 A -1 s ds. ( 13
)
Lemma 6. If the initial measure µ is more-log-concave than the standard Gaussian measure, then almost surely

A t op ≤ e -t , ∀t ≥ 0.
Proof. Since µ is more log-concave than the Gaussian, equation ( 12) shows that the density f t of µ t satisfies

f t (x) = exp - 1 2 |x| 2 - 1 2 B t x, x -V t (x)
for some convex function V t . the previous lemma, the covariance matrix A t of µ t satisfies

A t ≤ (B t + id) -1 ≤ 1 λ t + 1 id,
where λ t is the lowest eigenvalue of B t . Therefore

A t op ≤ 1 λ t + 1 .
On the other hand, the equality (13) yields

λ t ≥ t 0 A s -1 op ds, showing that t 0 A s -1 op ds + 1 ≤ A t -1 op .
Integrating this differential inequality yields the result.

The following proposition will be crucial for the proof of our main theorem. Its proof is more involved than the proof of previous estimate, and we refer to [E, Section 3].

Proposition 7. If the initial measure µ is log-concave then

E A t op ≤ C 0 A 0 op τ 2 n log(n) e -t , ∀t ≥ 0, where C 0 is a universal constant.

Proof of the main theorem

We start with an elementary lemma.

Lemma 8. Let X be a log-concave random vector in R n and let • be a norm. Then for any event F

E X ; F ≤ C 1 P(F ) E X ,
where C 1 is a universal constant. In particular, if P(F ) ≤ (2C 1 ) -2 , one has

E X ≤ 2E X ; F c , (14)
where F c is the complement of F .

Proof. This is an easy consequence of Borell's lemma, which states as follows.

There exist universal constants C, c > 0 such that,

P X > tE X ≤ Ce -ct .
By Fubini's theorem and the Cauchy-Schwarz inequality

E X ; F = ∞ 0 P X > t, F dt ≤ ∞ 0 P X > t dt × P(F ).
Plugging in Borell's inequality yields the result, with constant C 1 = 2C/c.

The next ingredient we will need is the following proposition, which we learnt from B.Maurey. The authors are not aware of any published similar result. Proposition 9. Let (M t ) t≥0 be a continuous martingale taking values in R n . Assume that M 0 = 0 and that the quadratic variation of M satisfies ∀t > 0, [M ] t ≤ id, almost surely. Then (M t ) t≥0 converges almost surely, and the limit satisfies the following inequality. Letting Γ be a standard Gaussian vector, we have for every convex function ϕ :

R n → R ∪ {+∞} Eϕ(M ∞ ) ≤ Eϕ(Γ).
Proof. The hypothesis implies that M is bounded in L 2 , hence convergent by Doob's theorem. Let X be a standard Gaussian vector on R n independent of (M t ) t≥0 . We claim that

Y = M ∞ + (id -[M ] ∞ ) 1/2 X
is also a standard Gaussian vector. Indeed, for a fixed x ∈ R n one has

E e i x,Y | (M t ) t≥0 = exp i x, M ∞ + 1 2 [M ] ∞ x, x - 1 2 |x| 2 = exp iL ∞ + 1 2 [L] ∞ - 1 2 |x| 2 ,
where L is the real martingale defined by L t = M t , x . Itô's formula shows that

D t = exp iL t + 1 2 [L] t
is a local martingale. On the other hand the hypothesis yields

|D t | = exp 1 2 [M ] t x, x ≤ exp 1 2 |x| 2
almost surely. This shows that (D t ) t≥0 is a bounded martingale; in particular

E(D ∞ ) = E(D 0 ) = 1, since M 0 = 0. Therefore E e i x,Y = e -|x| 2 /2 ,
proving the claim. Similarly (just replace X by -X)

Z = M ∞ -(id -[M ] ∞ ) 1/2 X
is also standard Gaussian vector. Now, given a convex function φ, we have

Eϕ(M ∞ ) = Eϕ Y + Z 2 ≤ 1 2 E (ϕ(Y ) + ϕ(Z)) = Eϕ(Y ),
which is the result.

We are now ready to prove the main theorem.

Proof of Theorem 1. Let us prove that given a norm • and a log-concave vector X satisfying E(X) = 0 we have

E X ≤ Cτ n (log n) 1/2 cov(X) 1/2 op E Γ , (15)
for some universal constant C. If X is assumed to be isotropic, then cov(X) = id and we end up with the desired inequality (4). Our first step is to reduce the proof to the case that X has a compact support. Assume that (15) holds for such vectors, and for r > 0, let Y r be a random vector distributed according to the conditional law of X given the event {|X| ≤ r}.

Then Y r is a compactly supported log-concave vector, and by our assumption,

E Y r -E(Y r ) ≤ Cτ n (log n) 1/2 cov(Y r ) 1/2 op E Γ . (16)
Besides, it is easily seen by dominated convergence that

lim r→+∞ E Y r -EY r = E X , lim r→+∞ cov(Y r ) = cov(X).
So letting r tend to +∞ in ( 16) yields ( 15). Therefore, we may continue the proof under the assumption that X is compactly supported.

We use the stochastic process (µ t ) t≥0 defined in the beginning of the previous section, with the starting law µ being the law of X. Let T be the following stopping time:

T = inf t ≥ 0, t 0 A s ds > C 2 τ 2 n log n A 0 op ,
where C is a positive constant to be fixed later and with the usual convention that inf(∅) = +∞. Define the stopped process a T by (a T ) t = a min(t,T ) .

By the optional stopping theorem, this process is also a martingale and by definition of T its quadratic variation satisfies

[a T ] t ≤ C 2 τ 2 n log n A 0 op , ∀t ≥ 0. Also (a T ) 0 = a 0 = E(X) = 0. Applying Proposition 9 we get E a T = E (a T ) ∞ ≤ Cτ n (log n) 1/2 A 0 1/2 op E Γ . ( 17
)
On the other hand, using Proposition 7 and Markov inequality we get

P(T < +∞) = P ∞ 0 A s op ds > C 2 τ 2 n log n A 0 op ≤ C 0 C 2 .
So P(T < +∞) can be rendered arbitrarily small by choosing C large enough.

By Proposition 4 we have a ∞ = X in law; in particular a ∞ is log-concave. If P(T < +∞) is small enough, we get using Lemma 8

E X = E a ∞ ≤ 2E a ∞ ; T = ∞ = 2E a T ; T = ∞ ≤ 2E a T .
Combining this with (17) and recalling that A 0 = cov(X) we obtain the result (15).

The proof of Proposition 3 follows the same lines. The main difference is that Proposition 6 is used in lieu of Proposition 7.

Proof of Proposition 3. Let Y r b a random vector distributed according to the conditional law of X given |X| ≤ r. Then Y r is also more log-concave than Γ and Eϕ(Y r ) → Eϕ(X) as r → +∞. So again we can assume that X is compactly supported, and consider the process (µ t ) t≥0 starting from the law of X. By Lemma 6, the process (a t ) t≥0 is a martingale whose quadratic variation satisfies Remark. This proof is essentially due to Maurey; although his (unpublished) argument relied on a different stochastic construction.

Application to Mean Width and to the Isotropic Constant

In this section, we prove Corollary 2. Let Γ be a standard Gaussian vector in R n and let Θ be a point uniformly distributed in S n-1 . Integration in polar coordinates shows that for any norm

• ,

E Γ = c n E Θ ,
where

c n = E|Γ| = √ n + O(1),
since Γ has the thin-shell property. Theorem 1 can thus be restated as follows. If Y is an isotropic log-concave random vector and K is a convex body containing 0 in its interior then

E Y K ≤ C n log n τ n M (K). ( 18
)
Now let K be an isotropic convex body and let X be a random vector uniform on K. Since X ∈ K almost surely, we have

X K • ≥ |X| 2 , hence E X K • ≥ E|X| 2 = n.
Applying (18) to K • and to X thus gives

M * (K) ≥ c √ n √ log n τ n ,
which is (i).

In [Bou], Bourgain combined the inequality

E X ≤ Cn 1/4 E Γ (19)
with a theorem of Pisier to get the estimate

L K ≤ Cn 1/4 log n.
Part (ii) of the corollary is obtained along the same lines, replacing (19) by our main theorem. We sketch the argument for completeness.

Recall that K is assumed to be isotropic and that X is uniform on K. Let T be a positive linear map of determinant 1. Then by the arithmetic-geometric inequality E X (T K) • ≥ E X, T X = Tr(T ) ≥ n.

Applying (18) to the random vector X and the convex body (T K) • we get

M * (T K) ≥ c √ n √ log n τ n . (20)

[a] t = t 0 A

 0 s ds ≤ id, ∀t ≥ 0, almost surely. Since again a 0 = E(X) = 0, Proposition 9 yields the result.