Jorma Rissanen

STOCHASTIC CHAINS WITH MEMORY OF VARIABLE LENGTH A. GALVES AND E. L ÖCHERBACH

Stochastic chains with memory of variable length constitute an interesting family of stochastic chains of infinite order on a finite alphabet. The idea is that for each past, only a finite suffix of the past, called context, is enough to predict the next symbol.

These models were first introduced in the information theory literature by Rissanen (1983) as a universal tool to perform data compression. Recently, they have been used to model up scientific data in areas as different as biology, linguistics and music. This paper presents a personal introductory guide to this class of models focusing on the algorithm Context and its rate of convergence.

Introduction

Chains with memory of variable length appear in Rissanen's 1983 paper called A universal data compression system. His idea was to model a string of symbols as a realization of a stochastic chain where the length of the memory needed to predict the next symbol is not fixed, but is a deterministic function of the string of the past symbols.

Considering a memory of variable length is a practical way to overcome the well known difficulty of the exponentially growing number of parameters which are needed to describe a Markov chain when its order increases. However if one wants to fit accurately complex data using a Markov chain of fixed order, one has to use a very high order. And this means that to estimate the parameters of the model we need huge samples, which makes this approach unsuitable for many practical issues. It turns out that in many important scientific data, the length of the relevant portion of the past is not fixed, on the contrary it depends on the past. For instance, in molecular biology, the translation of a gene into a protein is initiated by a fixed specific sequence of nucleotide bases called start codon. In other words, the start codon designs the end of the relevant portion of the past to be considered in the translation.

The same phenomenon appears in other scientific domains. For instance in linguistics, both in phonology and in syntax, there is the notion of domains in which the grammar operates to define admissible strings of forthcoming symbols. In other terms, the boundary of the linguistic domain defines the relevant part of the past for the processing of the next linguistic units. Rissanen's ingenious idea was to construct a stochastic model that generalizes this notion of relevant domain to any kind of symbolic strings.

To be more precise, [START_REF] Rissanen | A universal data compression system[END_REF] called context the relevant part of the past. The stochastic model is defined by the set of all contexts and an associated family of transition probabilities.

Models with memory of variable length are not only less expensive than the classical fixed order Markov chains, but also much more clever since they take into account the structural dependencies present in the data. This is precisely what the set of contexts expresses.

Rissanen has introduced models having memory of variable length as a universal system of data compression. His goal was to compress in real time a string of symbols generated by an unknown source. To do this, we have to estimate at each step the length of the context of the string observed until that time step, as well as the associated transition probabilities.

If we knew the contexts, then the estimation of the associated transition probabilities could be done using a classical procedure such as maximum likelihood estimation. Therefore, the main point is to put hands on the context length. In his seminal 1983 paper, But also from the point of view of probability theory, this class of models is interesting.

In effect, if the length of the contexts is not bounded, then chains with memory of variable length are chains of infinite order. Existence, uniqueness, phase-transitions, perfect simulation are deep mathematical questions that should be addressed to in this new and challenging class of models.

Last but not least, models of variable length revealed to be very performing tools in applied statistics, by achieving in an efficient way classification tasks in proteomics, genomics, linguistics, classification of musical styles, and much more.

In what follows we present a personal introductory guide to this class of models with no attempt to give a complete survey of the subject. We will mainly focus on the algorithm Context and present some recent results obtained by our research team.

Probabilistic context trees

In what follows A will represent a finite alphabet of size |A|. Given two integers m ≤ n, we will denote by x n m the sequence (x m , . . . , x n ) of symbols in A. Let A * + be the set of all finite sequences, that is

A * + = ∞ k=1 A {-k,...,-1} .
We shall write A = A {...,-n,...,-2,-1} , and denote by x -1 -∞ any element of A. Our main object of interest is what we shall call context length function.

Definition 2.1. A context length function l is a function l : A * + → {1, 2, . . .} ∪ {∞} satisfying the following two properties. (i) For any k ≥ 1, for any x -1 -k ∈ A * + , we have l(x -1 -k ) ∈ {1, . . . , k} ∪ {+∞}. (ii) For any x -1 -∞ ∈ A, if l(x -1 -k ) = k for some k ≥ 1, then l(x -1 -i ) = ∞, for any i < k l(x -1 -i ) = k, for any i > k.
Intuitively, given a sequence x -1 -∞ , the function l tells us, at which position in the past we can stop since we have reached the end of the context. The first condition is a kind of adaptivity condition. It tells us that we can decide whether the end of the context has already been reached at step k just by inspecting the past sequence up to that step. If l equals +∞, we have to look further back in the past. The second condition is a consistency condition. It tells us that once we have reached the bound of the context, we do not have to look further back in the past, and that the context of a longer sequence x -1 -i , i > k, is also the context of x -1 -k . In other terms, once the identification of the context is made at a given step k, this decision will not be changed by any further data present in the past before k.

By abuse of notation, we shall also call l the natural extension of the context length function to A, given by

l(x -1 -∞ ) = inf {k ≥ 1 : l(x -1 -k ) < +∞},
with the convention that inf ∅ = +∞.

Definition 2.2. For any x -1 -∞ ∈ A, we shall call x -1 -l(x -1 -∞ ) the context associated to l of the infinite sequence x -1 -∞ .

Definition 2.3. Let l be a given context length function. A stationary stochastic chain (X n ) n∈Z taking values in A is a chain having memory of variable length, if for any infinite past x -1 -∞ ∈ A and any symbol a ∈ A, we have

P X 0 = a | X -1 -∞ = x -1 -∞ = P X 0 = a | X -1 -l(x -1 -∞ ) = x -1 -l(x -1 -∞ )
.

(2.4)

We shall use the short hand notation

p(a|x -1 -k ) = P X 0 = a | X -1 -k = x -1 -k . (2.5)
We are mainly interested in those values of p(a|x

-1 -k ) where k = l(x -1 -∞ ).
Observe that the set {ℓ(X -1 -∞ ) = k} is measurable with respect to the σ-algebra generated by X -1 -k . Thus we have Proposition 2.6. Let (X n ) be a stationary chain as in definition 2.3, having context

length function l. Put F k = σ{X -k , . . . , X -1 }, k ≥ 1. Then l(X -1 -∞ ) is a (F k ) k -stopping time.
Given a context length function l, we define an associated countable subset τ ⊂ A * + by

τ = τ l = {x -1 -k : k = l(x -1 -k ), k ≥ 1}.
To simplify notation, we will denote by x and y generic elements of τ.

Definition 2.7. Given a finite sequence

x -1 -k , we shall call suffix of x -1 -k each string x -1 -j with j ≤ k. If j < k we call x -1 -j proper suffix of x -1 -k . Now let S ⊂ A * + .
We say that S satisfies the suffix property if for no x -1 -k ∈ S, there exists a proper suffix x -1 -j ∈ S of x -1 -k .

The following proposition follows immediately from property (ii) of definition 2.1.

Proposition 2.8. Given a context length function l, the associated set τ l satisfies the suffix property.

As a consequence, τ can be identified with the set of leaves of a rooted tree with a countable set of finite labeled branches.

Definition 2.9. We call probabilistic context tree on A the ordered pair (τ, p), where

p = {p(.|x), x ∈ τ }
is the family of transition probabilities of (2.5). We say that the probabilistic context tree (τ, p) is unbounded if the function l is unbounded.

Definition 2.10. Let (X n ) n∈Z be a stationary chain and let (τ, p) be a probabilistic context tree. We shall say that (X n ) n∈Z is compatible with (τ, p), if (2.5) holds for all

x ∈ τ.

In order to illustrate these mathematical concepts, let us consider the following example.

Example 2.11. Consider a two-symbol alphabet A = {0, 1} and the following context length function

l(x -1 -∞ ) = inf {k : x -k = 1}.
Then the associated tree τ is given by

τ = {10 k , k ≥ 0},
where 10 k represents the sequence (x -k-1 , x -k , . . . , x -1 ) such that x -i = 0 for all

1 ≤ i ≤ k and x -k-1 = 1.
The associated transition probabilities are defined by

P (X 0 = 1|X -1 = . . . = X -k = 0, X -k-1 = 1) = q k , k ≥ 0, with 0 ≤ q k ≤ 1.
Clearly, the stochastic chain associated to this context length function l is a chain of infinite order. This raises the mathematical question of existence of such a process. It is straightforward to see that the following proposition holds true.

Proposition 2.12. Suppose that

X 0 = 1. Put T 1 = inf{k ≥ 1 : X k = 1}. A necessary and sufficient condition for T 1 < +∞ almost surely is k≥0 q k = +∞. (2.13)
This means that if (2.13) is satisfied, then -provided the chain starts from 1 -almost surely there will be appearance of an infinite number of the symbol 1. This implies that there exists a non-trivial stationary chain associated to this probabilistic context tree.

Observe that the process X n is actually a renewal process with the renewal times defined as follows.

T 0 = sup{n < 0 : X n = 1}, and for k ≥ 1,

T k = inf{n > T k-1 : X n = 1} and T -k := sup{n < T -(k-1) : X n = 1}.
This example shows clearly that the tree of contexts defines a partition of all possible pasts with the exception of the single string composed of all symbols identical to 0. The condition (2.13) shows that it is possible to construct the chain taking values in the set of all sequences having an infinite number of symbols 1 both to the left and to the right of the origin.

However, we could also include this exceptional string to the set of possible contexts by defining an extra parameter q ∞ . This is the choice of [START_REF] Csiszár | Context tree estimation for not necessarily finite memory processes, via BIC and MDL[END_REF]. If q ∞ is strictly positive, then condition (2.13) implies that after a finite time, there will appearance of the symbol 1, even if we start with an infinity of symbols 0. In other terms, this exceptional string does not have to be considered if we are interested in the stationary regime of the chain.

In case that q ∞ = 0 and (2.13) holds, we have the phenomenon of phase transition.

One of the phases is composed of only one string having only the symbol 0.

The renewal process is an interesting example of a chain having memory of unbounded variable length. In the case where the probabilistic context tree is bounded, the corresponding chain is in fact a Markov chain whose order is equal to the maximal context length. However, the tree of contexts provides interesting additional information concerning the dependencies in the data and the structure of the chain. This raises the issue how to estimate the context tree out of the data. This was originally solved in Rissanen's 1983 paper using the algorithm Context.

At this point it is important to discuss the following minimality issue. Among all possible context trees fitting the data, we want of course to identify the smallest one. This is the tree corresponding to the smallest context length function. More precisely, if l and

l ′ are context length functions, we shall say that l ≤ l ′ if l(x -1 -∞ ) ≤ l ′ (x -1 -∞ ) for any string x -1 -∞ ∈ A. From now on we shall call context of a string x -1
-∞ the context associated to the minimal context length function. Estimating this minimal context is precisely the goal of the algorithm Context.

The algorithm Context

We now present the algorithm Context introduced by [START_REF] Rissanen | A universal data compression system[END_REF]. The goal of the algorithm is to estimate adaptively the context of the next symbol X n given the past symbols X n-1 0 . The way the algorithm Context works can be summarized as follows.

Given a sample produced by a chain with variable memory, we start with a maximal tree of candidate contexts for the sample. The branches of this first tree are then pruned starting from the leaves towards the root until we obtain a minimal tree of contexts well adapted to the sample. We associate to each context an estimated probability transition defined as the proportion of time the context appears in the sample followed by each one of the symbols in the alphabet. We stop pruning once the gain function exceeds a given threshold.

Let X 0 , X 1 , . . . , X n-1 be a sample from the finite probabilistic tree (τ, p). For any finite string x -1 -j with j ≤ n, we denote N n (x -1 -j ) the number of occurrences of the string in the sample

N n (x -1 -j ) = n-j t=0 1 X t+j-1 t = x -1 -j . (3.1)
Rissanen first constructs a maximal candidate context X n-1 n-M (n) where M (n) is a random length defined as follows

M (n) = min i = 0, 1, . . . , ⌊C 1 log n⌋ : N n (X n-1 n-i ) > C 2 n √ log n . (3.2)
Here C 1 and C 2 are arbitrary positive constants. In the case the set is empty we take

M (n) = 0.
Rissanen then shortens this maximal candidate context by successively pruning the branches according to a sequence of tests based on the likelihood ratio statistics. This is formally done as follows.

If b∈A N n (x -1 -k b) > 0, define the estimator of the transition probability p by

pn (a|x -1 -k ) = N n (x -1 -k a) b∈A N n (x -1 -k b) (3.3)
where x -1 -j a denotes the string (x -j , . . . , , x -1 , a), obtained by concatenating x -1 -j and the symbol a.

If b∈A N n (x -1 -k b) = 0, define pn (a|x -1 -k ) = 1/|A|. For i ≥ 1 we define Λ n (x -1 -i ) = 2 y∈A a∈A N n (yx -1 -i a) log pn (a|x -1 -i y) pn (a|x -1 -i ) , (3.4)
where yx -1 -i denotes the string (y, x -i , . . . , x -1 ), and where

pn (a|x -1 -i y) = N n (yx -1 -i a) b∈A N n (yx -1 -i b)
.

Notice that Λ n (x -1 -i ) is the log-likelihood ratio statistic for testing the consistency of the sample with a probabilistic suffix tree (τ, p) against the alternative that it is consistent with (τ ′ , p ′ ) where τ and τ ′ differ only by one set of sibling nodes branching from x -1 -i .

Λ n (x -1 -i ) plays the role of a gain function telling us whether it is worth or not taking a next step further back in the past.

Rissanen then defines the length of the estimated current context ln as ln (X n-1

0 ) = 1 + max i = 1, . . . , M (n) -1 : Λ n (X n-1 n-i ) > C 2 log n , (3.5)
where C 2 is any positive constant.

Then, the result in [START_REF] Rissanen | A universal data compression system[END_REF] is the following.

Theorem 3.6. Given a realization X 0 , . . . , X n-1 of a probabilistic suffix tree (τ, p) with finite height, then

P ln (X n-1 0 ) = ℓ(X n-1 0 ) -→ 0 (3.7)
as n → ∞.

Rissanen proves this result in a very short and elegant way. His starting point is the following upper bound.

P ln (X n-1 0 ) = ℓ(X n-1 0 ) ≤ P ln (X n-1 0 ) = ℓ(X n-1 0 )|N n X n-1 n-ℓ(X n-1 0 ) > C 2 n √ log n P N n X n-1 n-ℓ(X n-1 0 ) > C 2 n √ log n +P w∈τ N n (w) ≤ C 2 n √ log n . (3.8)
Then he provides the following explicit upper bound for the conditional probability in the right-hand side of (3.8)

P ln (X n-1 0 ) = ℓ(X n-1 0 ) | N n X n-1 n-ℓ(X n-1 0 ) > C 2 n √ log n ≤ C 1 log n e -C ′ 2 √ log n , (3.9)
where C 1 , C 2 and C ′ 2 are positive constants independent of the maximum of the context length function.

With respect to the second term he only observes that, by ergodicity, for each x -1 -k ∈ τ we have

P N n x -1 -k ≤ C 2 n √ log n -→ 0 (3.10)
as n → ∞. Since τ is finite the convergence in (3.10) implies the desired result.

The unbounded case

In his original paper, Rissanen was only interested in the case of bounded context trees.

However, from the mathematical point of view, it is interesting to consider also the case of unbounded probabilistic context trees corresponding to chains of infinite order. It can be argued that also from an applied point of view the unbounded case must be considered as noisy observation of Markov chains generically have infinite order memory.

The unbounded case raises immediately the preliminary question of existence and uniqueness of the corresponding chain. This issue can be addressed by adapting to probabilistic context trees the conditions for existence and uniqueness that have already been (1) Weakly non-nullness, that is

a∈A inf x∈τ p(a | x) > 0 ; (4.2)
(2) Continuity, that is

β(k) = max a∈A sup{|p(a | x) -p(a | y)|, y ∈ τ, x ∈ τ with x k = y} → 0 (4.3)
as k → ∞. We also define

β(0) = max a∈A sup{|p(a | x) -p(a | y)|, y ∈ τ, x ∈ τ with x -1 = y -1 }.
The sequence {β(k)} k ∈ N is called the continuity rate.

For a probabilistic suffix tree of type A with summable continuity rate, the maximal coupling argument used in [START_REF] Fernández | Markov approximations of chains of infinite order, Fifth Brazilian School in Probability (Ubatuba[END_REF] implies the uniqueness of the law of the chain consistent with it.

We now present a slightly different version of the algorithm Context using the same gain function Λ n but in which the length of the maximum context candidate is now deterministic and nor more random. More precisely, we define the length of the biggest candidate context now as

k(n) = C 1 log n (4.4)
with a suitable positive constant C 1 .

The intuitive reason behind the choice of the upper bound length C 1 log n is the impossibility of estimating the probability of sequences of length much longer than log n based on a sample of length n. Recent versions of this fact can be found in Marton and[START_REF] Marton | Correction: "Entropy and the consistent estimation of joint distributions[END_REF] and [START_REF] Csiszár | Large-scale typicality of Markov sample paths and consistency of MDL order estimators. Special issue on Shannon theory: perspective, trends, and applications[END_REF]. Now, the definition of ln is similar to the one in the original algorithm of Rissanen, that is ln (X n-1

0 ) = 1 + max i = 1, . . . , k(n) -1 : Λ n (X n-1 n-i ) > C 2 log n , (4.5)
where C 2 is any positive constant.

The reason for taking the length of the maximum context candidate deterministic and no more random is to be able to use the classical results on the convergence of the law of Λ n (x -1 -i ) to a chi-square distribution. However, we are not in a Markov setup since the probabilistic context tree is unbounded, and the chi-square approximation only works for Markov chains of fixed finite order.

To overcome this difficulty, we use the canonical Markov approximation of chains of infinite order presented in Fernández and Galves (2002) that we recall now by adapting the definitions and theorem to the framework of probabilistic context trees. The goal is to approximate a chain compatible with an unbounded probabilistic context tree by a sequence of chains compatible with bounded probabilistic context trees. Definition 4.6. For all k ≥ 1, the canonical Markov approximation of order k of a chain (X n ) n∈Z is the chain with memory of variable length bounded by k compatible with the probabilistic context tree (τ [k] , p [k] ) where

τ [k] = {x ∈ τ ; l(x) ≤ k} ∪ {x -1 -k ; x ∈ τ, l(x) ≥ k} (4.7)
for all a ∈ A, x ∈ τ, and where

p [k] (a | x -1 -j ) := P (X 0 = a | X -1 -j = x -1 -j ) (4.8)
for all x -1 -j ∈ τ [k] .

Observe that for contexts x ∈ τ which length does not exceed k, we have p [k] (a | x) = p(a | x). However, for sequences x -1 -k which are internal nodes of τ , there is no easy explicit formula expressing p

[k] (•|x -1 -k ) in terms of the family {p(•|y), y ∈ τ }.
The main result of Fernández and Galves (2002) that will be used in the proof of the consistency of the algorithm Context can be stated as follows.

Theorem 4.9. Let (X n ) n∈Z be a chain compatible with a type A probabilistic context tree (τ, p) with summable continuity rate, and let (X

[k]
n ) n∈Z be its canonical Markov approximation of order k. Then there exists a coupling between (X n ) n∈Z and (X Theorem 4.11. Let X 0 , X 2 , . . . , X n-1 be a sample from a type A unbounded probabilistic suffix tree (τ, p) with continuity rate β(j) ≤ f (j) exp{-j}, with f (j) → 0 as j → ∞.

[k] n ) n∈Z and a constant C > 0 such that P X 0 = X [k] 0 ≤ Cβ(k) .
Then, for any choice of positive constants C 1 and C 2 in (4.4) and (4.5), there exist positive constants C and D such that

P ln (X n-1 0 ) = ℓ(X n-1 0 ) ≤ C 1 log n(n -C 2 + D/n) + Cf (C 1 log n) .
The proof can be sketched very easily. Take k = k(n) = C 1 log(n) and construct a coupled version of the processes (X t ) t∈Z and (X

[k(n)] t
) t∈Z . First of all notice that for k = k(n), P ln (X 0 , . . . , X n-1 ) = ℓ(X 0 , . . . , X n-1 ) ≤ P ln (X

[k] 0 , . . . X [k] n-1 ) = ℓ(X [k] 0 , . . . X [k] n-1 ) + P n i=1 {X i = X [k] i } . (4.12)
Using the inequality (4.10) of [START_REF] Fernández | Markov approximations of chains of infinite order, Fifth Brazilian School in Probability (Ubatuba[END_REF], the second term in (4.12) can be bounded above as

P n i=1 {X i = X [k] i } ≤ n C β(k(n)).
The first term in (4.12) can be treated using the classical chi-square approximation for the log-likelihood ratio test for Markov chains of fixed order k.

More precisely, we know that for fixed x -1 -i , under the null hypothesis, the statistics Λ n (x -1 -i ), given by (3.4), has asymptotically chi-square distribution with |A| -1 degrees of freedom (see, for example, van der Vaart (1998)). We recall that, for each x -1 -i the null hypothesis (H i 0 ) is that the true context is x -1 -i . Since we are going to perform a sequence of k(n) sequential tests where k(n) → ∞ as n diverges, we need to control the error in the chi-square approximation. For this, we use a well-known asymptotic expansion for the distribution of Λ n (x -1 -i ) due to [START_REF] Hayakawa | The likelihood ratio criterion and the asymptotic expansion of its distribution[END_REF] which implies that

P Λ n (x -1 -i ) ≤ t | H i 0 = P χ 2 ≤ t + D/n , (4.13)
where D is a positive constant and χ 2 is random variable with distribution chi-square with |A| -1 degrees of freedom.

Therefore, it is immediate that

P Λ n (x -1 -i ) > C 2 log n ≤ e -C 2 log n + D/n .
By the way we defined ln in (4.5), in order to find ln (X n-1

0

) we have to perform at most k(n) tests. We want to give an upper bound for the overall probability of type I error in a sequence of k(n) sequential tests. An upper bound is given by the Bonferroni inequality, which in our case can be written as

P ∪ k(n) i=2 {Λ n (x -1 -i ) > C 2 log n} | H i 0 ≤ k(n) i=2 P (Λ n (x -1 -i ) > C 2 log n | H i 0 ).
This last term is bounded above by C 1 log n(n -C 2 + D/n). This concludes the proof.

Theorem 4.11 not only proves the consistency of the algorithm Context, but it also gives an upper bound for the rate of convergence. The estimation of the rate of convergence is crucial because it gives a bound on the minimum size of a sample required to guarantee, with a given probability, that the estimated tree is the good one. This is the issue we address to in the next section.

Rate of convergence of the algorithm Context

Note that Rissanen's original theorem 3.6 as well as theorem 4.11 only show that all the contexts identified are true contexts with high probability. In other words, the estimated tree is a subtree of the true tree with high probability. In the case of bounded probabilistic context trees this missing point was handled with in [START_REF] Weinberger | A universal finite memory source[END_REF]. This paper not only proves that the set of all contexts is reached, but also gives a bound for the rate of convergence.

More precisely, let us define the empirical tree τn = X j-1 j-lj (X j-1 0 )

: j = n/2, . . . , n .

(5.1)

Actually, this is a slightly simplified version of the empirical tree defined in [START_REF] Weinberger | A universal finite memory source[END_REF]. In particular, we are neglecting all the computational aspects considered there. But from the mathematical point of view, this definition perfectly does the job.

Their convergence result is the following.

Theorem 5.2. Let (τ, p) be a bounded probabilistic context tree and let X 0 , . . . , X n be compatible with (τ, p). Then we have n≥1

P (τ n = τ ) log n < +∞.
In the unbounded case, this issue was treated without estimation of the rate of convergence in [START_REF] Ferrari | Estimation of general stationary processes by variable length Markov chains[END_REF] and including estimation of the rate of convergence in Galves and Leonardi (2008).

This last paper considers another slightly modified version of the algorithm Context using a different gain function, which has been introduced in Galves et al. (2007). More precisely, let us define for any finite string x -1 -k ∈ A * + the gain function

∆ n (x -1 -k ) = max a∈A |p n (a|x -1 -k ) -pn (a|x -1 -(k-1) )|.
This gain function is well adapted to use exponential inequalities for the empirical transition probabilities in the pruning procedure rather than the chi-square approximation of the log-likelihood ratio as in theorems 3.6 and 4.11.

The theorem is stated in the following framework. Consider a a stationary chain (X n ) n∈Z compatible with an unbounded probabilistic context tree (τ, p). For this chain, we define the sequence (α n ) n∈N by

α 0 = a∈A inf x∈τ p(a|x), α n = inf x -1 -n a∈A inf y∈τ :l (y)≥n,y n =x -1 -n p(a|y).
We assume that the probabilistic context tree (τ, p) satisfies the condition (4.2) of weakly non-nullness, that is α 0 > 0. We assume also the following summability condition

α = n≥0 (1 -α n ) < +∞. (5.3)
Given a sequence x j 1 = (x 1 , . . . , x j ) ∈ A j we denote by p(x j 1 ) = P(X j 1 = x j 1 ).

Then for an integer m ≥ 1, we define

D m = min x -1 -k ∈τ :k≤m max a∈A { |p(a|x -1 -k ) -p(a|x -1 -(k-1) )| }, (5.4)
and

ǫ m = min{ p(x -1 -k ) : k ≤ m and p(x -1 -k ) > 0 }. (5.5)
Intuitively, D m tells us how distinctive is the difference between transition probabilities associated to the exact contexts and those associated to a string shorter one step in the past. We do not want to impose restrictions on the transition probabilities elsewhere then at the end of the branches of the context tree. This has to do with the pruning procedure which goes from the leaves to the root of the tree.

In the unbounded case, a natural way to state the convergence results is to consider truncated trees. The definition is the following. Given an integer K we will denote by τ | K the tree τ truncated to level K, that is

τ | K = {x -1 -k ∈ τ : k ≤ K} ∪ {x -1 -K such that x -1 k ∈ τ for some k ≥ K}.
Actually, this is exactly the same tree which was called τ [K] in (4.7). The notation τ | K is more suitable for what follows.

The associated empirical tree of height k is defined in the following way.

Definition 5.6. Given δ > 0 and k < n, the empirical tree is defined as

τ δ,k n = {x -1 -r , 1 ≤ r ≤ k : ∆ n (x -1 -r ) > δ ∧ ∆ n (y -(r+1) -(r+j) x -1 -r ) ≤ δ, ∀ y -(r+1) -j , 1 ≤ j ≤ k -r}.
In case r = k, the string y

-(r+1) -(r+j) is empty.
Note that in this definition, the parameter δ expresses the coarseness of the pruning criterion and k is the maximal length of the estimated contexts. Now, Galves and Leonardi (2008) obtain the following result on the rate of convergence for the truncated context tree.

Theorem 5.7. Let (τ, p) be a probabilistic context tree satisfying (4.2) and (5.3). Let X 0 , . . . , X n be a stationary stochastic chain compatible with (τ, p). Then for any integer

K, any k satisfying k > max x∈τ | K min {ℓ(y) : y ∈ τ, x K = y}, (5.8)
for any δ < D k and for each

n > 2(|A| + 1) min(δ, D k -δ)ǫ k + k (5.9)
we have that

P (τ δ,k n | K = τ | K ) ≤ 4 e 1 e |A| k+2 exp -(n-k) [min( δ 2 , D k -δ 2 ) -|A|+1 (n-k)ǫ k ] 2 ǫ 2 k C 4|A| 2 (k + 1)
,

where

C = α 0 8e(α + α 0 )
.

In this theorem, the empirical trees have to be of height k ≥ K for the following reason.

Truncating τ at level K implies that contexts longer than K are cut before reaching their end, and associated transition probabilities might not differ when comparing them at length K and K -1. That's why we consider the bigger empirical tree of height k satisfying condition (5.8). This guaranties that for each element x of the truncated empirical tree there is at least one real context y which has x as its suffix.

As a consequence of theorem 5.7, Galves and Leonardi (2008) obtain the following strong consistency result.

Corollary 5.10. Let (τ, p) be a probabilistic context tree satisfying the conditions of theorem 5.7. Then

τ δ,k n | K = τ | K , (5.11)
eventually almost surely, as n → ∞.

The main ingredient of the proof of theorem 5.7 is an exponential upper bound for the deviations of the empirical transition probabilities. More precisely, Galves and Leonardi (2008) prove the following result.

Theorem 5.12. For any finite sequence x -1 -k with p(x -1 -k ) > 0, any symbol a ∈ A, any t > 0 and any n > |A|+1 tp(x -1 -k ) + k the following inequality holds.

P |p n (a|x -1 -k ) -p(a|x -1 -k )| > t ≤ 2|A| e 1 e exp -(n-k) [t -|A|+1 (n-k)p(x -1 -k ) ] 2 p(x -1 -k ) 2 C 4|A| 2 (k + 1) , (5.13)
where Theorem 5.15. Let (X n ) n∈Z be a stationary stochastic chain compatible with the probabilistic context tree (τ, p) of theorem 5.7. Then, there exist a sequence {ρ l } l∈N such that for any i ≥ 1, any k > i, any j ≥ 1 and any finite sequence x j 1 , the following inequality holds

C = α 0 8e(α + α 0 ) . ( 5
sup x i 1 ∈A i |P (X k+j-1 k = x j 1 | X i 1 = y i 1 ) -p(x j 1 )| ≤ j ρ k-i-1 .
(5.16)

Moreover, the sequence {ρ l } l∈N is summable and

l∈N ρ l ≤ 1 + 2α α 0 .
Theorem 5.7 generalizes to the unbounded case previous results in [START_REF] Galves | Exponential inequalities for VLMC empirical trees[END_REF] for the case of bounded context trees. Note that the definition of the context tree estimator depends on the parameter δ, the same appearing in the constants of the exponential bound. To assure the consistency of the estimator we have to choose a δ sufficiently small, depending on the true probabilities of the process. The same thing happens to the parameter k. Therefore, this estimator is not universal, meaning that for fixed δ and k it fails to be consistent for all variable memory processes for which conditions (5.8) and

(5.9) are not satisfied. We could try to overcome this difficulty by letting δ = δ(n) → 0 and k = k(n) → +∞ as n increases. But doing this, we loose the exponential character of the upper bound. This could be considered as an illustration of the result in Finesso et al.

(1996) who proved that in the simpler case of estimating the order of a Markov chain, it is not possible to have a universal estimator with exponential bounds for the probability of overestimation.

Some final comments and bibliographic remarks

Chains with memory of variable length were introduced in the information theory literature by [START_REF] Rissanen | A universal data compression system[END_REF] (2007). They proved that in the case of a binary alphabet and when taking δ within a suitable interval, it is possible to recover the context tree in the bounded case out from a noisy sample where each symbol can be flipped with small probability independently of the others.

The case of unbounded probabilistic context trees as far as we know was first considered by [START_REF] Ferrari | Estimation of general stationary processes by variable length Markov chains[END_REF] who also proved a weak consistency result for the algorithm Context in this more general setting. The unbounded case was also considered by [START_REF] Csiszár | Context tree estimation for not necessarily finite memory processes, via BIC and MDL[END_REF] who introduced a different approach for the estimation of the probabilistic context tree using the Bayesian Information Criterion (BIC) as well as the Minimum Description Length Principle (MDL). We refer the reader to this last paper for a nice description of other approaches and results in this field, including the context tree maximizing algorithm by [START_REF] Willems | The Context-Tree weighting method: Basic properties[END_REF]. We also refer the reader to Garivier This presentation did not intend to be exhaustive and the bibliography in many cases only gives a few hints about possible starting points to the literature. However, we think we have presented the state of the art concerning the rate of convergence of context tree estimators.

In the introduction we said that Rissanen's ingenious idea was to construct a stochastic model that generalizes the notion of relevant domain (in biology or linguistics) to any kind of symbolic strings. Actually, God only knows what Jorma had in mind when he invented this class of models. The French poet Paul Eluard wrote a book called Les frères voyants.

This was the name given in the middle-age to people guiding blind persons. So maybe

Rissanen acted as a frère voyant using his intuition to push mathematics and statistics into a challenging new direction.

Date:

  January 7, 2008. This work is part of PRONEX/FAPESP's project Stochastic behavior, critical phenomena and rhythmic pattern identification in natural languages (grant number 03/09930-9), CNPq's project Stochastic modeling of speech (grant number 475177/2004-5) and CNRS-FAPESP project Probabilistic phonology of rhythm. AG is partially supported by a CNPq fellowship (grant 308656/2005-9).

  Rissanen solved this problem by introducing the algorithm Context. This algorithm estimates in a consistent way both the length of the context as well as the associated transition probability. The class of models with memory of variable length raises interesting questions from the point of view of statistics. Examples are the rate of convergence and the fluctuations of the algorithm Context and other estimators of the model. Another challenging question would be how to produce a robust version of the algorithm Context.

  proved for infinite order chains. This is precisely what is done in the paper by Duarte et al. (2006) who adapt the type A condition presented in Fernández and Galves (2002) in the following way. To simplify the presentation, let us introduce some extra notation. Recall that x and y denote generic elements of τ. Given x = x -1 -i and y = y -1 -j , we shall write x k = y if and only if k ≤ min{i, j} and x -1 = y -1 , . . . , x -k = y -k . Definition 4.1. A probabilistic suffix tree (τ, p) on A is of type A if its transition probabilities p satisfy the following conditions.

(4. 10 )

 10 Using this result and the classical chi-square approximation for Markov chains, Duarte et al. (2006) proved the consistency of their version of the algorithm Context in the unbounded case and also provided an upper bound for the rate of convergence. Their result is the following.

. 14 )

 14 The proof of this theorem is inspired by recent exponential upper bounds obtained by Dedecker and Doukhan (2003), Dedecker and Prieur (2005) and Maume-Deschamps (2006). It is based on the following loss-of-memory inequality of Comets et al. (2002).

(

  2006a, b) for recent and elegant results on the BIC and the Context Tree Weighting Method (CTW). Garivier (2006c) is a very good presentation of models having memory of variable length, BIC, MDL, CTW and related issues in the framework of information theory. With exception of Weinberger et al. (1995), the issue of the rate of convergence of the algorithm estimating the probabilistic context tree was not addressed in the literature until recently. Weinberger et al. (1995) proved in the bounded case that the probability that the estimated tree differs from the finite context tree is summable as a function of the sample size. Assuming weaker hypotheses than Ferrari and Wyner (2003), Duarte et al. (2006) proved in the unbounded case that the probability of error decreases as the inverse of the sample size. Leonardi (2007) obtained an upper bound for the rate of convergence of penalized likelihood context tree estimators. It showed that the estimated context tree truncated at any fixed height approximates the real truncated tree at a rate that decreases faster than the inverse of an exponential function of the penalizing term. The proof mixes the approaches of Galves et al. (2008) and Csiszár and Talata (2006). Several interesting papers have recently addressed the question of classification of proteins and DNA sequences using models with memory of variable length, which in bioinformatics are often called prediction suffix trees (PST). Many of these papers have been written from a bio-informatics point of view focusing on the development of new tools rather than being concerned with mathematically rigorous proofs. The interested reader can find a starting point to this literature for instance in the papers by Bejerano et al. (2001), Bejerano and Yona (2001), Eskin et al. (2000), Leonardi (2006) and Miele et al. (2005). The same type of analysis has been used successfully to classification tasks in other domains like musicology (Lartillot et al. 2003), linguistics ( Selding et al. 2001), etc.

  as a universal system for data compression. Originally called by Rissanen tree machine, tree source, context models, etc., this class of models recently became popular in the statistics literature under the name of Variable Length Markov Chains (VLMC), coined by[START_REF] Bühlmann | Variable length Markov chains[END_REF]. In all the variants the decision to prune a branch is taken by considering a gain Context in the case where the contexts have a bounded length. Bühlmann and Wyner (1999) proved the weak consistency of the algorithm also in the finite case without assuming a prior known bound on the maximal length of the memory but using a bound allowed to grow with the size of the sample. A different gain function was introduced in Galves et al. (2008), considering differences between successive empirical transition probabilities and comparing them with a given threshold δ. An interesting consequence of the use of this different gain function was obtained by Collet et al.

	function.
	Rissanen (1983), Bühlmann and Wyner (1999) and Duarte et al. (2006) all defined the
	gain function in terms of the log likelihood ratio function. Rissanen (1983) proved the
	weak consistency of the algorithm
	Rissanen (1983) not only introduced the notion of variable memory models but he

also introduced the algorithm Context to estimate the probabilistic context tree. From Rissanen (1983) to Galves et al. (2008), passing by Ron et al. (1996) and Bühlmann and Wyner (1999), several variants of the algorithm Context have been presented in the literature.


Philippe Calcagno
email: p.calcagno@brgm.fr

Chamaret Aurélie

Nicolas Chauvin

Sunsearé Gabalda

Santiago Gabillard

Antonio Guillen

David Michéa

Fabien Pasquier

Joachim Pouderoux

Vincent Bouchot

Aurélie Chamaret

Sunseare Gabalda

David Michea

Thermo2Pro: A tool for deep geothermal exploration in basin context

Keywords: Deep geothermal exploration, information system, Web tool, sedimentary basin, dissemination

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

Abstract:

It is well known that a better understanding of the geology and petrophysical properties is necessary to develop deep geothermal projects. However, this knowledge must be shared within the professional community to be efficient. Thermo2Pro is essentially a Web tool designed to fill the gap between the information derived from R&D projects and the authorities of the geothermal sector who need to use it.

Thermo2Pro is a joint project lead by ADEME and BRGMthe French Environment and Energy Management Agency, and the French Geological Survey -. It is dedicated to professionals dealing with the deep geothermal exploration in basin context. A user committee, gathering contracting authorities, local authorities, and design offices, has been involved in the development of the project since its very beginning. Thermo2Pro has two main objectives: to give relevant material to prepare a pre-feasibility study, and to promote geothermal development by facilitating access to the information.

The main vector for Thermo2Pro is a Web application where the user accesses the information by simulating vertical or horizontal sections and boreholes. Requests are defined via an interactive cartographic interface running WPS Web services (Web Processing Service, OGC -Open Geospatial Consortium). Data are kept in 3D grids allowing a management of the information in a standard way; staying independent from the tools that have generated this information. The 3D grids are stored in a VTK format (Visualization Tool Kit).

The functionalities of Thermo2Pro will be demonstrated through data related to the Trias aquifer of the Paris basin. This reservoir could be a complement to the Dogger that has been exploited since the 80's in the area. The available information for the Trias will be mainly a model of geometry, an estimation of porosity, and a model of temperatures. Those parameters have been acquired and inferred in the scope of the CLASTIQ-2 R&D project (ADEME and BRGM).


Laurent Najman
email: l.najman@esiee.fr

Thierry Géraud
email: thierry.geraud@lrde.epita.fr

Discrete set-valued continuity and interpolation

.

Introduction

This paper is the first in a series dedicated to the notion of the tree of shapes, which has been introduced [START_REF] Monasse | Fast computation of a contrast-invariant image representation[END_REF][START_REF] Caselles | Geometric description of topographic maps[END_REF] as a way to filter an image u : X ⊂ R n → R (n ≥ 2) in a self-dual way, meaning intuitively that processing either u or -u would give the same result. In its continuous definition, this tree is made by the connected components of upper level sets {x; u(x) ≥ λ} λ∈R and lower level sets {x; u(x) < λ} λ∈R . This definition, by itself, is not really self-dual, as the tree of shapes of u is not the same as the tree of shapes of -u.

The goal of this paper is to propose a purely discrete framework in which a true self-dual definition of the tree of shapes can be given, together with a proof of the existence and uniqueness of such a tree for a given class of functions. We then provide several ways to interpret any image as belonging to this class of functions, one of them being self-dual. In the next paper of this series [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nd images[END_REF], we provide a quasi-linear algorithm relying on this theoretical framework, that allows the computation of the tree of shapes of an image, whatever its dimension.

In order to achieve our goal, we extend the notion of set-valued uppersemicontinuity [START_REF] Aubin | Set-valued analysis[END_REF] to the discrete case (T0-Alexandroff topology), and from which we build the notions of simple map and plain map that share the main properties of a classical continuous function. To obtain the tree of shapes, we also need to adapt the notion of well-composed map to our framework.

First approaches to discrete continuity date back to Rosenfeld [START_REF] Rosenfeld | continuous" functions on digital pictures[END_REF], followed by Boxer [START_REF] Boxer | Digitally continuous functions[END_REF]. Many authors have recognized that the set-valued setting is important to the discrete case [START_REF] Kovalevsky | A new concept for digital geometry[END_REF][START_REF] Tsaur | continuous" multifunctions in discrete spaces with applications to fixed point theory[END_REF][START_REF] Escribano | Digitally continuous multivalued functions, morphological operations and thinning algorithms[END_REF]. None has proposed what we develop in this paper, although it may appear very natural for a researcher familiar with set-valued analysis.

2 Set-valued continuity on discrete spaces

Topology reminder

A topological space is a set X composed of elements, or points, of arbitrary nature in which certain subsets A ⊆ X, called closed sets of the topological space X, have been defined so as to satisfy the following conditions, called the axioms of a topological space:

1. The intersection of any number and the union of any finite number of closed sets is a closed set. 2. The whole set X and the empty set ∅ are closed.

The sets complementary to the closed sets of X are called the open sets of the topological space X.

The intersection of all closed sets containing a set M ⊂ X is called the closure of M in the topological space X and is denoted by cl X (M ). Every open set containing a set M is called a neighborhood of the set M . A set M ⊂ X is said to be degenerate if it contains just one point.

Definition 1 A topological space X is said to be a T 0 -space if every two distinct degenerate subsets of X have distinct closures in X. A T 0 -space is called a discrete space if the union of an arbitrary number of closed sets of the space is closed.

Finite T 0 -spaces are the most important cases of the so called discrete spaces [START_REF] Alexandroff | Diskrete Räume[END_REF][START_REF] Alexandroff | Combinatorial topology[END_REF][START_REF] Arenas | Alexandroff spaces[END_REF]. Another important example is the Khalimsky grid of dimension n, which is define as follows:

H 1 0 = {{x}; x ∈ Z} (1) H 1 1 = {{x, x + 1}; x ∈ Z} (2) H 1 = H 1 0 ∪ H 1 1 (3) H n = {h 1 × . . . × h n , ∀i ∈ [1, n], h i ∈ H 1 } (4)
In the Khalimsky grid, the elements of H 1 0 are closed sets, and the elements of H 1 1 are open sets. Although our definitions and results are valid in any discrete space, we will illustrate them on (a subset of) the Khalimsky grid.

If X is a discrete space, the intersection of all open sets containing a set M ⊂ X is an open set, called the star of M in the topological space X. The star of M in X is denoted by st X (M ). If M = {x} is degenerate, by abuse of notation, we write st X (x) = st X ({x}).

Definition 2 A set is said to be connected if it is not the union of two disjoint nonempty closed sets.

For discrete spaces, this definition is equivalent to the one provided by the connectivity by paths. Two points x and y of X of a discrete space X are neighbors if either y ∈ st X (x) or x ∈ st X (y). A path in X from x to y is a sequence x 0 = x, x 1 , . . . , x n = y such that x i+1 is a neighbor of x i . One can prove that a set is connected if for any two points of this set, there exists a path between them. A connected component of X is a connected subset of X that is maximal for the connectivy property. We can also mention that any discrete space is locally connected, in the sense that any point x ∈ X has a smallest open connected neighborhood in X, namely st X (x). The following lemma is useful in the sequel.

Definition 3 Let M and N be two subspaces of X. M and N are separated if each is disjoint from the closure of the other, that is, if

(M ∩ cl X (N )) ∪ (N ∩ cl X (M )) = ∅. Lemma 4
If two open sets of a discrete space are disjoint, then they are separated.

Set-valued maps

In the sequel, X and Y denotes two discrete spaces. The main references for set valued analysis is [START_REF] Aubin | Set-valued analysis[END_REF]. An application F is called a set-valued map from X to Y if for any x ∈ X, F associates to x the set F (x) ⊂ Y , called the image of F at x. In this case, the domain of F is the set Dom(F ) = {x : F (x) = ∅}.

A set-valued map F : X Y is called upper semicontinuous at x ∈ Dom(F ) (usc at x) if and only if for all y ∈ st X (x), F (y) ⊆ st Y (F (x)). F is said to be upper semicontinuous if and only if it is upper semicontinuous at every point

x ∈ Dom(F ). X Y x (a) X Y x (b)
Fig. 1. (a) A discrete set-valued map F that is usc at x, drawn on a subset of the Khalimsky grid H2 Note that F is also an interval-valued map, and x is both a minimum and a maximum of F . (b) A discrete set-valued map that is lsc at x.

One can remark that upper semicontinuity is the natural adaptation to setvalued map of the definition of a continuous function. An example of a usc set-value map is given in Fig. 1(a).

A useful property of a continuous function is that the inverse image of a closed (open) set is a closed (open) set. To adapt this property to set valued maps, we need to define the inverse. Let M be a subset of Y , F : X Y be a set-valued map. We denote F ⊕ (M ) = {x ∈ X; F (x) ∩ M = ∅} , and

F (M ) = {x ∈ X; F (x) ⊆ M }. The subset F ⊕ (M ) is called the inverse image of M by F and F (M ) is called the core of M by F . Proposition 5 A set-valued map F : X Y is usc if and only if the core of any open set is open: F is usc if and only if F st Y = st X F If furthermore F is with nonempty values (or if Dom(F ) is closed) F is usc if and only if the inverse image of any closed subset is closed: F is usc if and only if F ⊕ cl Y = cl X F ⊕ .
Intuitively, a function is continuous if, roughly speaking, it can be drawn as a single unbroken curve with no "holes" nor "jumps". In other words, a continuous function transforms a connected set into a connected set. For a set M ⊆ X, we write

F (M ) = ∪ x∈M F (x). Proposition 6 Let F be a usc set-valued map such that, for all x ∈ X, F (x) is a closed (resp. open) connected set. Then, for any connected set M , F (M ) is a closed (resp. open) connected set. X Y Fig. 2. A quasi-simple map.
We say that a usc set-valued map F is a closed (resp. open) quasi-simple map if for all x ∈ X, F (x) is a closed (resp. open) connected set, and if furthermore, for any {x} = st X (x) ∈ X, F (x) is degenerate. A quasi-simple map F is simple if it is the smallest of all quasi-simple maps with the same data on open points, i.e, a quasi-simple map F 1 is simple if for any quasi-simple map

F 2 such that for any {x} = st X (x) ∈ X, F 1 (x) = F 2 (x), then, for all x ∈ X, F 1 (x) ⊆ F 2 (x).
Fig. 2 is an example of a quasi-simple map, while Fig. 3 is a simple map. The class of simple maps is interesting because it corresponds to our intuition (i.e. a single ubroken curve with no "holes" nor "jump") of continuous functions (at least when a simple map is interval-valued, see section 3).

In particular if f is a function defined for all {x} = st X (x) ∈ X with f (x) ∈ Y and f (x) closed (resp. open), there exists a (unique) closed (resp. open) simple map such that for all {x} = st X (x) ∈ X, F (x) = {f (x)}.

Remark 1. V. Kovalevsky [START_REF] Kovalevsky | A new concept for digital geometry[END_REF] defines the "continuous" functions as the ones that are called lower semicontuinous in our framework. More precisely, V. Kovalevsky uses prop. 8 below as the definition of a continuous function.

Definition 7 A set-valued map F : X Y is called lower semicontinuous (lsc) at x ∈ Dom(F ) if for any open subset M ⊂ Y such that M ∩ F (x) = ∅, then for all y ∈ st X (x), F (y) ∩ M = ∅.
Fig. 1(b) gives an example of an lsc set-valued map. This definition is the adaptation to the (discrete) set-valued setting of the celebrated characterization of continuous function (a function f is continuous at x if and only if it maps any sequence converging to x to sequences converging to f (x).) However, as no convergence can be defined in a discrete space, we have to use a topological definition. We have the following characterization of lsc maps.

Proposition 8 A set-valued map F : X Y is lsc if and only if the inverse image of any open set is open: F is lsc if and only if F ⊕ st Y = st X F ⊕ If furthermore F is with nonempty values (or if Dom(F ) is closed) F is lsc if and only if the core of any closed subset is closed: F is lsc if and only if F cl Y = cl X F .
However, it is not possible to obtain simple lsc set-valued maps with interesting properties for our goal, and V. Kovalevsky then studies connectivity-preserving set-valued maps, that would be called Darboux maps in a more classical setting. In our framework (as in the classical one), some connectivity-preserving maps exist that are not usc, although prop. 6 shows that there exists usc maps preserving connectivity.

Interval-valued maps

Recall that a set X is said to be unicoherent if X is connected and for any two closed connected sets M and N of X such that X = M ∪ N , then M ∩ N is connected. In the sequel, X 0 denotes a finite discrete topological space, and X ⊂ X 0 denotes an unicoherent subset of X 0 .

An interval is a connected subset of H 1 . Remark that H 1 is a totally ordered set, in the sense where H 1 is in bijection with 1 2 Z: we identify the open sets of H 1 with the elements of 1 2 Z \ Z and the closed sets of H 1 with the elements of Z. We thus have . . . < {0} < {0, 1} < {1} < . . ., and operations such as λ + 1 2 (where λ ∈ H 1 ), max or min on any subset of H 1 are well-defined. We say that a set-valued map F is an interval-valued map if the images of F are intervals. We say that an interval-valued map is bounded if there exists λ and µ in H 1 such that λ ≤ min{ν ∈ F (X)} and µ ≥ max{ν ∈ F (X)}. It is easy to check that interval-valued maps verify important classical theorems, such as for example, the intermediate value theorem (which is a simple consequence of Pr. 6 and of the connectedness of an interval).

As illustrated on Fig. 3, a simple closed-valued interval-valued map from H 1 to H 1 is what one would intuitively draw when dealing with a classical continuous function. Thus we will use the following definition.

Definition 9 A closed-valued, interval-valued simple map F from X to H 1 , with dom(F ) = X is called a plain map on X.

1 -1 -2 {1,2} 2 {0,1} 0 0 1 -1 {-1,0} {-2,-1} {0,1} {-1,0} Fig. 3. A plain map F from H 1 to H 1 .
Remark that, as X is finite, a plain map is bounded. We have the following property.

Proposition 10 If F is a plain map on X, then F is an open-valued usc map and F ⊕ is a closed-valued usc map.

Level sets and extrema

We need to adapt to the set-valued case the notions of upper and lower level sets. In the sequel, F denotes an interval-valued map from X to

H 1 . Let λ ∈ Z, we write [F λ] = F (] -∞, λ[) = { x ∈ X | ∀µ ∈ F (x), µ < λ }. The set [F λ]
is called the (strict) lower level set (of F , at level λ). Similarly, the (strict) upper level set (of F , at level λ) is the set [F λ] = F (]λ, +∞[). Thanks to prop. 10, the upper and lower level sets of a plain map are open.

The connected components of a set M ⊆ X will be denoted by CC(M ). If x ∈ M , the connected component of M that contains x will be denoted by CC(M, x), and by extension, we write

CC(M, x) = ∅ if x ∈ M . If ∅ = C ⊆ M and C is connected, the connected component of M containing C, denoted by CC(M, C) is CC(M, x) with x ∈ C. Definition 11 (Extrema) A connected component of [F λ] is a minimum of F if it does not contain any other connected component of [F µ] for any µ < λ. A connected component of [F λ] is a maximum of F if it does not contain any other connected component of [F µ] for any µ > λ.
An extremum of F is either a maximum or a minimum of F .

We say that a set M is flat for F if for all x ∈ M , F (x) = F (M ). Remark that F (M ) is not always a degenerate set and that an extremum of a set-valued map is not always flat: for example, the point x in Fig. 1(a) is both a minimum and a maximum, and although this extremum is flat, it is not degenerate. It is easy to draw an example where a minimum of a set valued map contains several maxima, and hence is not flat.

Lemma 12

The extrema of a plain map F are flat open sets. Furthermore, for any extrema M of F , F (M ) is degenerate.

Proposition 13 Let F be a plain map on X that is not constant. Then the extrema of F are separated.

In the same way as the strict level sets, we can define the (large) lower and upper level sets

[F λ] = X \ [F λ] = F ⊕ (] -∞, λ]) = { x ∈ X | ∃µ ∈ F (x); µ ≤ λ } and [F λ] = X \ [F λ].
≡ λ] = [F λ] ∩ [F λ] = { x ∈ X | λ ∈ F (x) } and [F ≡ λ] = X \ [F ≡ λ] = { x ∈ X | λ ∈ F (x) } = [F λ] ∪ [F λ]. The following relations are natural. We indeed have [F λ] = [F λ] ∪ [F ≡ λ], [F λ] = [F λ] ∪ [F ≡ λ] and [F ≡ λ] = [F λ] ∪ [F λ]
. Similarly, we have for any

λ 1 and λ 2 in H 1 , λ 1 < λ 2 ⇒ [F λ 1 ] ⊆ [F λ 2 ] and λ 1 < λ 2 ⇒ [F λ 2 ] ⊆ [F λ 1 ]. But if we have λ 1 < λ 2 ⇒ [F λ 1 ] ∩ [F λ 2 ] = ∅, the following relation is uncommon. λ 1 < λ 2 ⇒ [F λ 1 ] ∩ [F λ 2 ] = ∅ (5)
Indeed, for instance, for x such as

F (x) = [1, 2], we have both x ∈ [F 1] and x ∈ [F 2]
. Note that we may also have:

[F λ + 1 2 ] [F λ] (6)
Indeed, with the same example, if

F (x) = [1, 2], x ∈ [F 1], but x ∈ [F 3 2
]. But, by the very definition of a plain map, if F is plain, for any λ ∈ H 1 , we always have the following property.

Proposition 14 A set-valued map F is a plain map if and only if, for any λ ∈ H 1 ,

[F λ] = cl X ([F λ + 1 2 ]) and [F λ] = cl X ([F λ - 1 2 ]) (7)
We can reconstruct F from its lower and upper level sets, with the following process: set

f min (x) = min{λ ∈ Z; x ∈ [F λ]} and f max (x) = max{λ ∈ Z; x ∈ [F λ]}. Then F (x) = [f min (x), f max (x)].
The process is simpler if F is plain: then for any degenerate open set x ∈ X, we have

F (x) = {min{λ ∈ Z; x ∈ [F (λ + 1)]}} = {max{λ ∈ Z; x ∈ [F (λ -1)]}}.
The other images of a simple/plain map F can be deduced from these ones.

Definition 15 Let T ⊆ 2 X . We say that T is a tree (of subsets of X) if (i) X ∈ T , and (ii), if M, N ∈ T , then either M ∩ N = ∅, M ⊆ N , N ⊆ M . In the last two cases, we say that M and N are nested.

For a plain map F , let us denote

U (F ) = {M ; M ∈ CC([F λ]), λ ∈ H 1 }, U ⊕ (F ) = {M ; M ∈ CC([F λ]), λ ∈ H 1 }, L (F ) = {M ; M ∈ CC([F λ]), λ ∈ H 1 } and L ⊕ (F ) = {M ; M ∈ CC([F λ]), λ ∈ H 1 }.
We remark that any two elements of one of these four sets are either disjoint or nested, hence they are trees. The set U (F ) (resp. L (F )) is the tree of open connected components of the lower (resp. upper) level sets of F , while U ⊕ (F ) (resp. L ⊕ (F )) is the tree of closed connected components of the lower (resp. upper) level sets of F . In the literature, similar trees have been called min-or max-trees, or component trees.

Shapes of Interval-Valued Maps

Topology is not so important when we consider independently the min or the max tree. It becomes fundamental when considering both trees at the same time, which is at the basis of the so-called tree of shapes.

Definition 16 Let M ⊆ X. We call cavities of M in X the components of X \ M . Let p ∞ ∈ X a reference point. We call saturation of M with respect to p ∞ the set sat(M, p ∞ ) = X \ CC(X \ M, p ∞ ).
For any λ ∈ H 1 , we call quasi-shape of x the set:

S λ (F, x) = sat(CC([F ≡ λ], x), p ∞ ) (8)
We thus have two different types possible for a given shape:

either S λ (F, x) = sat(CC([F λ], x), p ∞ ) (9) or S λ (F, x) = sat(CC([F λ], x), p ∞ ). (10)
But all the shapes being open, the type of a shape can not be known from the shape itself (contrary to the case of the continuous framework [START_REF] Caselles | Geometric description of topographic maps[END_REF]). Consider the family of sets:

S(F, x) = { S λ (F, x) } λ \ ∅. (11)
and denote by S(F ) the set formed by all the S(F, x) for all x ∈ X.

The notion of surface used in this paper is the one of n-surface.

Definition 17 (n-surface, [START_REF] Bertrand | A model for digital topology[END_REF][START_REF] Evako | Dimension on discrete spaces[END_REF]) A discrete space Y is a 0-surface if Y is made of exactly two points x and y such that x ∈ st Y (y) and y

∈ st Y (x). A discrete space Y is a n-surface (n > 0) if Y is connected and if, for any x ∈ Y , cl Y (x) ∪ st Y (x) \ {x} is a (n -1)-surface.
The notion of well-composed connected set has been introduced in [START_REF] Latecki | Well-composed sets[END_REF][START_REF] Latecki | 3d well-composed pictures[END_REF]. Several extensions have been proposed in the literature [START_REF] Marchadier | Thinning grayscale well-composed images[END_REF][START_REF] Gonzalez-Diaz | Well-composed cell complexes[END_REF][START_REF] Wang | Digital connectivity and extended well-composed sets for gray images[END_REF]. In this paper, we extend it to maps by considering at the same time upper and lower level sets.

Definition 18 (Well-composed set and map)

A connected set M is well- composed if ∂M = cl X (M ) ∩ cl X (X \ M ) is a n-surface. A set N is well- composed if any connected component of ∂N is a n-surface. A plain map F is well-composed if for any λ ∈ H 1 , both [F λ] and [F λ] are well-composed.
Remark 2. Note that a well-composed set is a regular open set [START_REF] Ronse | Regular open or closed sets[END_REF].

Lemma 19 If a plain map F is well-composed, then for any λ ∈ H 1 , and for any connected component

C ∈ CC([F λ]) (resp. C ∈ CC([F λ])), there exists a connected component CC ∈ CC([F λ + 1 2 ]) (resp. CC ∈ CC([F λ -1 2 ])) such that C = cl X (CC).
Lemma 20 If a plain map F is well-composed, then for any λ ∈ H 1 , and for any connected component

M ∈ CC([F λ]) (resp. M ∈ CC([F λ])), we have sat(cl X (M )) = cl X (sat(M )).
Theorem 21 If F is a well-composed plain map, then any two quasi-shapes are either disjoint or nested. Hence S(F ) is a tree.

The proof of Th. 21 is essentially the same as the one of Th. 2.6 in [START_REF] Caselles | Geometric description of topographic maps[END_REF], adapted for the set-valued case of a plain map, and with a different ending that uses Lemma 20 and Lemma. 19. Due to space constraint, this proof will be provided in an extended version of this paper.

Definition 22

We call shape of x the smallest non-empty quasi-shape of x defined by: S(F, x) = S∈S(F,x)

S ( 12
)
We denote by S(F ) the set formed by all the shapes of x for all x ∈ X

The intersection in ( 12) is open as an intersection of open sets in a discrete space; moreover it is non-empty, as S(F, x) is one of the quasi-shapes of x by proposition 21.

Corollary 23

The set S(F ) is a tree (called the tree of shapes).

Interpolation

In order to apply the framework, we need a way to interpret any function defined on a grid as a well-composed plain map. Unfortunately, directly interpreting a set of data as a plain map (as in Fig. 4.a) does not lead to a well-composed plain map. We do not want to modify the original data, as it is done in [START_REF] Siqueira | Topological repairing of 3D digital images[END_REF].

Closer to what we propose in this paper are the magnification process of [START_REF] Nakamura | Magnification in digital topology[END_REF], and even closer is [START_REF] Stelldinger | Topological equivalence between a 3d object and the reconstruction of its digital image[END_REF], where new points are introduced thanks to subdivision of the space, the value on the points being derived from a majority rule. However, none of the previous approaches is equivalent to the simple interpolation we propose an operator over a multiset of integers that is increasing with respect to any element of the multiset, that is, ∀z = {z 1 , . . . , z k } ∈ M(Z), ∀i ∈ [1, k], we have: z i ≤ z i ⇒ op({z 1 , . . . , z i-1 , z i , z i+1 , . . . , z k }) ≤ op(z).

Some well-known eligible operators are the minimum, the maximum, and the median (with med({a, b}) = (a + b)/2). From any operator op we can derive an "interpolation" of a function f : Z n → Z into a plain map F : H n H 1 :

I op : (Z n → Z) -→ (H n H 1 ) f -→ I op (f )
where I op (f ) is recursively defined by:

∀h ∈ H n , I op (f )(h) =    2f ( h1 2 , . . . , hn 2 ) if h ∈ 2H n 1 op({I(f )(h ); h ∈ st X (cl X (h)) ∩ 2H n 1 }) if h ∈ I n 1 span({I(f )(h ); h ∈ st X (h) ∩ H n 1 }) otherwise.
Furthermore, the elements of C n 1 shall not lead to extrema in I op (f ). Proposition 24 Any plain map obtained thanks to the max-or the min-interpolation is well-composed.

The max-and min-interpolation reproduces the Rosenfeld 4-and 8-topology. The tree of shapes obtained with this interpolation is the one computed by all previous existing algorithms [START_REF] Caselles | Geometric description of topographic maps[END_REF]. However, the max-or the min-interpolation do not lead to a self-dual filtering. This is illustrated in Conjecture 26 With the suitable space subdivision, the median interpolation leads to a self-dual map whatever the dimension of the space.

Remark 27 Fig. 4.d shows that the mean operator is not suited for our type of interpolation.

Conclusion

In this paper, we have shown how to obtain a well-composed plain map from any set of data defined on a grid, and we provide a median-interpolation operator inducing a true self-dual tree. In another paper [START_REF] Géraud | A quasi-linear algorithm to compute the tree of shapes of nd images[END_REF], we provide a quasi-linear algorithm for computing the tree of shapes from a n-dimensional well-composed plain map. A dedicated algorithm (less memory consuming) will also be provided for the 2D case.

  Original data seen as a plain map. (b) Minimum interpolation.

  Fig 4.b. Proposition 25 The median interpolation of a function defined on Z 2 leads to a self-dual plain map. This proposition is illustrated on Fig. 4.c.

Acknowledgements. This work received funding from the Agence Nationale de la Recherche, contract ANR-2010-BLAN-0205-03 and through "Programme d'Investissements d'Avenir" (LabEx BEZOUT n • ANR-10-LABX-58).

 [START_REF] Caselles | Geometric description of topographic maps[END_REF]are in red, whereas contours of connected components of [F 5] are in green and blue. One can remark that (a) and (d) are not well-composed and that the saturation of the components of (a) and of (d) do not satisfy Lemma 19 and 20, contrary to the components of (b) and (c). In particular, the saturation of the red component in (a) or (d) does not include the blue component.

hereafter. More precisely, we map a function defined on Z n to a function defined on the Khalimsky grid H n using an adequate space subdivision.

Let us denote by H n 1 the set of the elements of H n that are open sets:

and the subset of

Let us denote by M(Z) the set of multisets having Z as the underlying set of elements; for instance we have {1, 1, 2} ∈ M(Z). Let op : M(Z) → 1