Siméon Valère

Bitseki Penda

Gorgui Gackou
email: gorgui.gackou@uca.fr

S Val Ère

MODERATE DEVIATION PRINCIPLES FOR BIFURCATING MARKOV CHAINS: CASE OF FUNCTIONS DEPENDENT OF ONE VARIABLE

Keywords: Bifurcating Markov chains, moderate deviation principles, deviation inequalities, binary trees Mathematics Subject Classification (2020): 60F10, 60J80

research documents, whether they are published or not. The documents may come

Introduction

First, we give a general definition of a moderate deviation principles. Let (Z n ) n≥0 be a sequence of random variables with values in S endowed with its Borel σ-field B(S) and let (s n ) n≥0 be a positive sequence that converges to +∞. We assume that Z n /s n converges in probability to 0 and that Z n / √ s n converges in distribution to a centered Gaussian law. Let I : S → R + be a lower semicontinuous function, that is for all c > 0 the sub-level set {x ∈ S, I(x) ≤ c} is a closed set. Such a function I is called rate function and it is called good rate function if all its sub-level sets are compact sets. Let (b n ) n≥0 be a positive sequence such that b n → +∞ and b n / √ s n → 0 as n goes to +∞.

Definition 1.1 (Moderate deviation principle, MDP).

We say that Z n /(b n √ s n ) satisfies a moderate deviation principle in S with speed b 2 n and the rate function I if, for any A ∈ B(S),

-inf x∈A • I(x) ≤ lim inf n→∞ 1 b 2 n log P Z n b n √ s n ∈ A ≤ lim sup n→∞ 1 b 2 n log P Z n b n √ s n ∈ A ≤ -inf x∈ Ā I(x),
where A • and Ā denote respectively the interior and the closure of A.

Bifurcating Markov chains (BMC, for short) are a class of stochastic processes indexed by regular binary tree. They are appropriate for example in the modeling of cell lineage data when each cell in one generation gives birth to two offspring in the next one. Recently, they have received a great deal of attention because of the experiments of biologists on aging of Escherichia Coli (E. Coli , for short). E. Coli is a rod-shaped bacterium which reproduces by dividing in two, thus producing two daughters: one of type 0 which has the old pole of the mother and the other of type 1 which has the new pole of the mother. The genealogy of the cells may be entirely described by a binary tree. To the best of our knowledge, the term bifurcating Markov chains appears for the first time in the works of Basawa and Zhou [START_REF] Basawa | Non-Gaussian bifurcating models and quasi-likelihood estimation[END_REF]. Thereafter, it was Guyon in [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF] who had introduced and properly studied the theory of BMC. The first example of BMC, named bifurcating autoregressive process (BAR, for short), were introduced by Cowan and Staudte [START_REF] Cowan | The bifurcating autoregression model in cell lineage studies[END_REF] in order to study the mechanisms of cell division in Escherichia Coli. Since this work of Cowan and Staudte, the BAR process has been widely studied in the literature and several extensions have been made. In particular, Guyon, in [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF], have used an extension of BAR process to get statistical evidence of aging in E.Coli.

In this paper, we are interested in moderate deviation principles( MDP, for short ) for additive functionals of bifurcating Markov chains. The MDP can be seen as an intermediate behavior between the central limit theorem and large deviation. Usually, the MDP exhibits a simpler rate function inherited from the approximated Gaussian process, and holds for a larger class of dependent random variables than the large deviation principle. Unlike the results given in [START_REF] Bitseki Penda | Deviation inequalities, moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF], we treat here the case of functions which depends on one variable only. For this type of additive functionals, the martingale decomposition done in [START_REF] Bitseki Penda | Deviation inequalities, moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF] is no longer valid. Indeed, as explained for e.g. in [START_REF] Delmas | Detection of cellular aging in a Galton-Watson process[END_REF] Remark 1.7, the error term on the last generation is not negligible. Note that recently, Bitseki and Delmas [START_REF] Bitseki Penda | Central limit theorem for bifurcating markov chains[END_REF] have studied central limit theorem for additive functionals of bifurcating Markov chain. They have studied the case where the functions depend only on the trait of a single individual for BMC. Bitseki and Delmas [START_REF] Bitseki Penda | Central limit theorem for bifurcating markov chains[END_REF] observes three regimes (sub-critical, critical, supercritical), which correspond to a competition between the reproducing rate (a mother has two daughters) and the ergodicity rate for the evolution of the trait along a lineage taken uniformly at random. This phenomenon already appears in the works of Athreya [START_REF] Athreya | Limit theorems for multitype continuous time Markov branching processes[END_REF]. Here we investigate the moderate deviation principles for MBC depending only on one variable for the two cases: subcritical and critical regimes. The super-critical regime, which require another way of centering will be done in a future work.

The rest of the paper is organized as follows. In Section 2, we present the model of bifurcating Markov chains. In Section 3, we give some notations and the main assumptions for our results. In Section 4, we set our main results: the sub-critical case in Section 4.1 and the critical case in Section 4.2. Section 5 is dedicated to the proof of the main result in sub-critical case and Section 6 is dedicated to the proof of the main result in Critical case. In Section 7, we illustrate numerically our results. Finally, in Section 8, we give some useful results.

The model of bifurcating Markov chain

2.1. The regular binary tree associated to BMC models. We denote by N (resp. N * ) the space of (resp. positive) natural integers. We set

T 0 = G 0 = {∅}, G k = {0, 1} k and T k = 0≤r≤k G r for k ∈ N * , and T = r∈N G r .
The set G k corresponds to the k-th generation, T k to the tree up to the k-th generation, and T the complete binary tree. One can see that the genealogy of the cells is entirely described by T (each vertex of the tree designates an individual). For i ∈ T, we denote by |i| the generation of i (|i| = k if and only if i ∈ G k ) and iA = {ij; j ∈ A} for A ⊂ T, where ij is the concatenation of the two sequences i, j ∈ T, with the convention that ∅i = i∅ = i.

2.2.

The probability kernels associated to BMC models. Let (S, S ) be a measurable space. For any q ∈ N * , we denote by B(S q ) (resp. B b (S q ), resp. C b (S q )) the space of (resp. bounded, resp. bounded continuous ) R-valued measurable functions defined on S q . For all q ∈ N * , we set S ⊗q = S ⊗ . . . ⊗ S . Let P be a probability kernel on (S, S ⊗2 ), that is: P(•, A) is measurable for all A ∈ S ⊗2 , and P(x, •) is a probability measure on (S 2 , S ⊗2 ) for all x ∈ S. For any g ∈ B b (S 3 ) and h ∈ B b (S 2 ), we set for x ∈ S:

(1) (Pg)(x) = S 2
g(x, y, z) P(x, dy, dz) and (Ph)(x) = S 2 h(y, z) P(x, dy, dz).

We define (Pg) (resp. (Ph)), or simply P g for g ∈ B(S 3 )(resp. Ph for h ∈ B(S 2 )), as soon as the corresponding integral (1) is well defined, and we have that Pg and Ph belong to B(S). we denote by P 0 , P 1 and Q respectively the first and the second marginal of P, and the mean of P 0 and P 1 , that is, for all x ∈ S and B ∈ S P 0 (x, B) = P(x, B × S), P 1 (x, B) = P(x, S × B) and Q = (P 0 + P 1 ) 2 .

Now let us give a precise definition of bifurcating Markov chain.

Definition 2.1 (Bifurcating Markov Chains, see [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF][START_REF] Bitseki Penda | Central limit theorem for bifurcating markov chains[END_REF]).

We say a stochastic process indexed by T, X = (X i , i ∈ T), is a bifurcating Markov chain (BMC) on a measurable space (S, S ) with initial probability distribution ν on (S, S ) and probability kernel P on S × S ⊗2 if:

-(Initial distribution.) The random variable X ∅ is distributed as ν.

-(Branching Markov property.) For any sequence (g i , i ∈ T) of functions belonging to B b (S 3 ) and for all k ≥ 0, we have

E i∈G k g i (X i , X i0 , X i1 )|σ(X j ; j ∈ T k ) = i∈G k Pg i (X i ).
Following [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF], we introduce an auxiliary Markov chain Y = (Y n , n ∈ N) on (S, S ) with Y 0 = X 1 and transition probability Q. The chain (Y n , n ∈ N) corresponds to a random lineage taken in the population. We shall write E x when X ∅ = x (i.e. the initial distribution ν is the Dirac mass at x ∈ S).

Notations and assumptions

For f ∈ B b (S), we set f ∞ = sup{|f (x)|, x ∈ S}. We will work with the following ergodic property.

Assumption 3.1. There exists a probability measure µ on (S, S ), a positive real number M and α ∈ (0, 1) such that for all f ∈ B b (S):

(2)

|Q n f -µ, f | ≤ M α n f ∞ for all n ∈ N.
We consider the stronger ergodic property based on a second spectral gap.

Assumption 3.2. There exists a probability measure µ on (S, S ), a positive real number M , α ∈ (0, 1), a finite non-empty set J of indices, distinct complex eigenvalues {α j , j ∈ J} of the operator Q with |α j | = α, non-zero complex projectors {R j , j ∈ J} defined on CB b (S), the Cvector space spanned by B b (S), such that R j • R j = R j • R j = 0 for all j = j (so that j∈J R j is also a projector defined on CB b (S)) and a positive sequence (β n , n ∈ N) converging to 0, such that for all f ∈ B b (S), with θ j = α j /α:

(3) Q n (f ) -µ, f -α n j∈J θ n j R j (f ) ≤ M β n α n f ∞ for all n ∈ N.
Without loss of generality, we shall assume that the sequence (β n , n ∈ N) in Assumption 3.2 is non-increasing and bounded from above by 1. This assumption will be used when α = 1/ √ 2. For f ∈ B b (S), f and f will denote the functions defined by:

(4) f = f -f, µ and f = f -α n j∈J θ n j R j (f ).
Let f = (f , ∈ N) be a sequence of elements of B b (S). We will assume in the sequel that

(5) sup ∈N { f ∞ } = c ∞ < +∞,
in such a way that ( 2) and ( 3) are uniformly satisfied by the sequence f. We set for n ∈ N and i ∈ T n :

(6) N n,i (f) = n-|i| =0 N n,i (f ) = |G n | -1/2 n-|i| =0 M iG n-|i|-( f ). We deduce that i∈G k N n,i (f) = |G n | -1/2 n-k =0 M G n-( f ) which gives for k = 0 that N n,∅ (f) = |G n | -1/2 n =0 M G n-( f ).
To study the asymptotics of N n,∅ (f), it is convenient to write for n ≥ k ≥ 1:

(7) N n,∅ (f) = |G n | -1/2 k-1 r=0 M Gr ( fn-r ) + i∈G k N n,i (f).
Asymptotic normality for N n,∅ (f) have been studied in [START_REF] Bitseki Penda | Central limit theorem for bifurcating markov chains[END_REF]. Our aim in this paper is to complete this result by studying moderate deviation principles for N n,∅ (f). More precisely, given a sequence (b n , n ∈ N) such that:

lim n→∞ b n = ∞ and lim n→∞ b n |G n | = 0, our aim is to prove that b -1 n N n,∅ (
f) satisfies a moderate deviation principle with speed b 2 n and rate function I defined by ( 8)

I(x) = sup λ∈R {λx -1 2 λ 2 Σ(f) -1 } = 1 2 Σ(f) -1 x 2 if Σ(f) = 0 +∞ if Σ(f) = 0,
where

Σ(f) = Σ sub (f) = Σ sub 1 (f) + 2Σ sub 2 (f) if 2α 2 < 1 Σ crit (f) = Σ crit 1 (f) + 2Σ crit 2 (f) if 2α 2 = 1, with Σ sub 1 (f) = ≥0 2 -µ, f 2 + ≥0, k≥0 2 k-µ, P (Q k f )⊗ 2 , (9) Σ sub 2 (f) = 0≤ <k 2 -µ, fk Q k-f + 0≤ <k r≥0 2 r-µ, P Q r fk ⊗ sym Q k-+r f , (10)
Σ crit 1 (f) = k≥0 2 -k µ, Pf * k,k = k≥0 2 -k j∈J µ, P(R j (f k ) ⊗ sym R j (f k )) , (11)
Σ crit 2 (f) = 0≤ <k 2 -(k+ )/2 µ, Pf * k, , (12)
and where for k, ∈ N:

(13) f * k, = j∈J θ -k j R j (f k ) ⊗ sym R j (f ).
More precisely, our aim is to prove that

-inf x∈A • I(x) ≤ lim inf n→∞ 1 b 2 n log P b -1 n N n,∅ (f) ∈ A ≤ lim sup n→∞ 1 b 2 n log P b -1 n N n,∅ (f) ∈ A ≤ -inf x∈ Ā I(x),
where A • and Ā denote respectively the interior and the closure of A. In particular, the latter asymptotic result implies that

lim n→∞ 1 b 2 n log P b -1 n N n,∅ (f) > δ = -I(δ) ∀δ > 0.
We note that 2α 2 < 1 corresponds to the sub-critical regime and 2α 2 = 1 to the critical regime.

The super-critical regime, that is the case where 2α 2 > 1, is not treated in this paper. Indeed, for this case, another way to centered the functions is necessary to get moderate deviation principles. This will be done in a future work.

Remark 3.3. Let f ∈ B b (S). If the sequence f = (f , ∈ N) is defined by: f 0 = f and f = 0 for all ≥ 1, then we have N n,∅ (f) = |G n | -1/2 M Gn ( f ) and Σ(f) = Σ G (f ), where Σ G (f ) = Σ sub G (f ) = µ, f 2 + k≥0 2 k µ, P Q k f ⊗ 2 if 2α 2 < 1 Σ crit G (f ) = j∈J µ, P(R j (f ) ⊗ sym R j (f )) if 2α 2 = 1, If the sequence f = (f , ∈ N) is defined by: f = f for all ∈ N, then we have N n,∅ (f) = |G n | -1/2 M Tn ( f ) = √ 2 -2 -n |T n | -1/2 M Tn ( f ) and Σ(f) = Σ T (f ), where Σ T (f ) = Σ sub T (f ) = Σ sub G (f ) + 2Σ sub T,2 (f ) if 2α 2 < 1 Σ crit T (f ) = Σ crit G (f ) + 2Σ crit T,2 (f ) if 2α 2 = 1, with Σ sub T,2 (f ) = k≥1 µ, f Q k f + k≥1 r≥0 2 r µ, P Q r f ⊗ sym Q r+k f , Σ crit T,2 (f ) = j∈J 1 √ 2 θ j -1 µ, P(R j (f ) ⊗ sym R j (f )) .

The main results

4.1. The sub-critical cases: 2α 2 < 1.

In the sub-critical case, we consider a sequence (b n , n ∈ N) such that:

lim n→∞ b n = ∞ and lim n→∞ b n |G n | = 0.
Then, we have the following result.

α ∈ (0, 1/ √ 2). Let f ∈ B b (S). Then b -1 n |G n | -1/2 M Gn ( f ) and b -1 n |T n | -1/2
α = 1/ √ 2. Let f ∈ B b (S). Then b -1 n (n|G n |) -1/2 M Gn ( f ) and b -1 n (n|T n |) -1/2 M Tn ( f )
p n < n 2 .
When there is no ambiguity, we write p for p n .

Let i, j ∈ T. We write i j if j ∈ iT. We denote by i ∧ j the most recent common ancestor of i and j, which is defined as the only u ∈ T such that if v ∈ T and v i, v j then v u. We also define the lexicographic order i ≤ j if either i j or v0 i and v1 j for v = i ∧ j. Let X = (X i , i ∈ T) be a BM C with kernel P and initial measure ν. For i ∈ T, we define the σ-field:

F i = {X u ; u ∈ T such that u ≤ i}.
By construction, the σ-fields (F i ; i ∈ T) are nested as F i ⊂ F j for i ≤ j.

We define for n ∈ N, i ∈ G n-pn and f ∈ F N the martingale increments:

(16) ∆ n,i (f) = N n,i (f) -E [N n,i (f)| F i ] and ∆ n (f) = i∈Gn-p n ∆ n,i (f).
Thanks to (6), we have:

i∈Gn-p n N n,i (f) = |G n | -1/2 pn =0 M G n-( f ) = |G n | -1/2 n k=n-pn M G k ( fn-k ).
Using the branching Markov property, and (6), we get for i ∈ G n-pn :

E [N n,i (f)| F i ] = E [N n,i (f)| X i ] = |G n | -1/2 pn =0 E Xi M G pn-( f ) .
We deduce from [START_REF] Cowan | The bifurcating autoregression model in cell lineage studies[END_REF] with k = np n that:

(17) N n,∅ (f) = ∆ n (f) + R 0 (n) + R 1 (n), with R 0 (n) = |G n | -1/2 n-pn-1 k=0 M G k ( fn-k ) and R 1 (n) = i∈Gn-p n E [N n,i (f)| F i ] .
Our goals will be achieved if we prove the following: Note that (18) and (19) mean that R 0 (n) and R 1 (n) are negligible in the sense of moderate deviations in such a way that from (52), N n,∅ (f) and ∆ n (f) satisfy the same moderate deviation principle (see Dembo and Zeitouni [START_REF] Dembo | Large Deviations Techniques and Applications[END_REF], chap. 4).

∀δ > 0, lim n→∞ 1 b 2 n log P(|b -1 n R 0 (n)| > δ) = -∞; (18) ∀δ > 0, lim n→∞ 1 b 2 n log P(|b -1 n R 1 (n)| > δ) = -∞; (19) b -1 n ∆ n (f)

Proof of (18).

Using the Chernoff inequality, we have, for all λ > 0, ( 21)

P(b -1 n R 0 (n) > δ) ≤ exp(-λb n |G n | 1/2 ) E exp λ n-p-1 k=0 M G k ( fn-k ) .
For all ∈ {0, . . . , np -1}, we set

I = E exp λ n-p--2 k=0 M G k ( fn-k ) exp λM G n-p--1 r=0 g p,r, ,
where g p,r, = 2 r Q r fp+ +1-r , with the convention that an empty sum is zero. For all ∈ {0, . . . , np -2}, we have the following decomposition:

(22) I = E exp λ n-p--2 k=0 M G k ( fn-k ) exp λM G n-p--2 r=0 2 Q(g p,r, ) J ,
where

J = E   exp   λ i∈G n-p--2 r=0 (g p,r, (X i0 ) + g p,r, (X i1 ) -2Q(g p,r, )(X i ))   H n-p--2   .
Using branching Markov property, we get

J = i∈G n-p--2 E Xi exp λ r=0 (g p,r, (X i0 ) + g p,r, (X i1 ) -2Q(g p,r, )(X i )) .
Using ( 2) and ( 5), we get

r=0 (g p,r, (X i0 ) + g p,r, (X i1 ) -2Q(g p,r, )(X i )) ≤ 2M c ∞ r=0 (2 α) r .
Using Lemma 8.2 and the latter inequality, we get, for all i ∈ G n-p--2 ,

E Xi exp λ r=0 (g p,r, (X i0 ) + g p,r, (X i1 ) -2Q(g p,r, )(X i )) ≤ exp 2λ 2 M 2 c 2 ∞ (1 + α) 2 a 2 ,
with a = r=0 (2α) r . The latter inequality implies that 22) and ( 23), it follows that (24)

(23) J ≤ exp 2λ 2 M 2 c 2 ∞ (1 + α) 2 a 2 |G n-p--2 | . From (
I ≤ exp 2λ 2 M 2 c 2 ∞ (1 + α) 2 a 2 |G n-p--2 | I +1 .
Using the recurrence (24) for all ∈ {0, . . . , np -2} for the first inequality, (3) and ( 5) for the second inequality, we are led to

E exp λ n-p-1 k=0 M G k ( fn-k ) = I 0 ≤ exp 2λ 2 M 2 c 2 ∞ (1 + α) 2 n-p-2 =0 a 2 |G n-p--2 | I n-p-1 ≤ exp 2λ 2 M 2 c 2 ∞ (1 + α) 2 n-p-2 =0 a 2 |G n-p--2 | + λ c ∞ M n-p-1 r=0 (2α) r+1 .
We have 21) that for all λ > 0, there exists a positive constant c α such that (25)

n-p-2 =0 a 2 |G n-p--2 | ≤            6 |G n-p-1 | if 2α ≤ 1 2α 2 (2α-1) 2 (1-2α 2 ) |G n-p-1 | if 1 < 2α < √ 2 1 (2α-1) 2 (n -p -1)|G n-p-1 | if 2α 2 = 1 1 (2α-1) 2 (2α 2 -1) (2α) 2(n-p-1) if 2α 2 > 1 It follows from (
P(b -1 n R 0 (n) > δ) ≤ exp -λb n |G n | 1/2 + c α λ 2 |G n-p | + c α λ(1 + (2α) n-p ) . Taking λ = 2 -1 c -1 α δ b n |G p | |G n | -1/2 in (25)
, we get, for some positive constant c α,δ ,

P b -1 n R 0 (n) > δ ≤ exp - c α,δ b 2 n |G p | δ 2 4c α .
Doing the same thing for the sequence -f instead of f, we conclude that

P b -1 n R 0 (n) > δ ≤ 2 exp - c α,δ b 2 n |G p | δ 2 4c α .
In the latter inequality, taking the log, dividing by b 2 n and letting n goes to infinity, we get the result.

Remark 5.1. Let f ∈ B b (S). Since we will use frequently this type of inequality, we give here a general procedure to upper-bound the probability P(||G n-p | -1 M Gn-p ( f )| > δ). From Chernoff inequality, we have, for all λ > 0, (26)

P |G n-p | -1 M Gn-p ( f ) > δ ≤ exp (-λδ|G n-p |) E exp λM Gn-p ( f ) .
For all m ∈ {0, . . . , n -p}, we set

I m = E exp 2 m λM Gn-p-m (Q m f ) .
Using the branching Markov property, we have

I m = E exp 2 m+1 λM Gn-p-m-1 (Q m+1 f ) J m ,
where

J m = i∈Gn-p-m-1 E Xi exp 2 m λ Q m f (X i0 ) + Q m f (X i1 ) -2Q m+1 f (X i ) .
Using (2) and Lemma 8.2, we have the following upper-bound:

J m ≤ exp λ 2 f 2 ∞ M 2 (1 + α) 2 (2α 2 ) m |G n-p | .
This implies that (27)

I m ≤ exp λ 2 f 2 ∞ M 2 (1 + α) 2 (2α 2 ) m |G n-p | I m+1 .
Using the recurrence relation ( 27) and ( 2) (to upper-bound I n-p ), we are led to (28) 26) and using (28), we are led to

I 0 ≤ exp λ 2 f 2 ∞ M 2 (1 + α) 2 a α,n |G n-p | + λ f ∞ M (2α) n-p , where a α,n = n-p-1 m=0 (2α 2 ) m . We set a α = lim n→∞ a α,n , which is finite since 2α 2 < 1. Taking λ = δ/(2 f 2 ∞ M 2 (1 + α) 2 a α ) in (
P |G n-p | -1 M Gn-p ( f ) > δ ≤ exp - δ 2 |G n-p | 4 f 2 ∞ M 2 (1 + α) 2 a α 1 - 2 f ∞ M α n-p δ .
Finally, since we can do the same thing for -f instead of f , we conclude that

(29) P |G n-p | -1 M Gn-p ( f ) > δ ≤ 2 exp - δ 2 |G n-p | 4 f 2 ∞ M 2 (1 + α) 2 a α 1 - 2 f ∞ M α n-p δ .

proof of (19).

We set g p = p =0 2 p-Q p-f in such a way that using the definition of R 1 (n), we have 2) and ( 5), we have

P b -1 n |R 1 (n)| > δ = P |G n-p | -1 M Gn-p (g p ) > δb n |G n | -1/2 |G p | . Using (
g p ∞ ≤ c ∞ M (p + 1) if 2α ≤ 1 c α c ∞ M if 1 < 2α < √ 2.
Applying (29) to g p and δb n |G n | -1/2 |G p |, we get, for n going to infinity and for some positive constant C α,δ ,

P b -1 n |R 1 (n)| > δ ≤ 2 exp -C α,δ δ 2 b 2 n |G p |p -2 if 2α ≤ 1 2 exp -C α,δ δ 2 b 2 n (2α 2 ) -p if 1 < 2α < √ 2.
Finally, (19) follows by taking the log, dividing by b 2 n and letting n goes to infinity in the latter inequality.

Proof of (20): Moderate deviations principle for b -1

n ∆ n (f). First we study the bracket of ∆ n (f):

V (n) = i∈Gn-p n E ∆ n,i (f) 2 |F i .
Using ( 6) and ( 16), we write:

(30) V (n) = |G n | -1 i∈Gn-p n E Xi   pn =0 M G pn -( f ) 2   -R 2 (n) = V 1 (n) + 2V 2 (n) -R 2 (n), with: V 1 (n) = |G n | -1 i∈Gn-p n pn =0 E Xi M G pn-( f ) 2 , V 2 (n) = |G n | -1 i∈Gn-p n 0≤ <k≤pn E Xi M G pn -( f )M G pn -k ( fk ) , R 2 (n) = i∈Gn-p n E [N n,i (f)|X i ] 2 .
Lemma 5.2. Under the Assumptions of Theorem 4.1, we have

(31) lim sup n→∞ 1 b 2 n log P (R 2 (n) > δ) = -∞.
Proof. Using the branching Markov property, we have

(32) R 2 (n) = |G n | -1 i∈Gn-p g p (X i ), with g p = p =0 2 p-Q p-f 2 .
Using ( 2) and ( 5), we get

g p ∞ ≤ c 2 ∞ M 2 p =0 (2α) p- 2 ≤ c 2 ∞ M 2 (p + 1) 2 if 2α ≤ 1 c 2 ∞ M 2 c α (2α) 2p if 1 < 2α < √ 2.
This implies that R 2 (n) is upper-bounded by a deterministic sequence which converge to 0. As a consequence, we conclude that (31) holds.

n log P V 1 (n) -Σ sub 1 (f) > δ = -∞,
where

Σ sub 1 (f) = ≥0 2 -µ, f 2 + ≥0, k≥0 2 k-µ, P (Q k f )⊗ 2 := H 3 (f) + H 4 (f)
Proof. Using (65), we get:

(33) V 1 (n) = V 3 (n) + V 4 (n), with V 3 (n) = |G n | -1 i∈Gn-p p =0 2 p-Q p-( f 2 )(X i ), V 4 (n) = |G n | -1 i∈Gn-p p-1 =0 p--1 k=0 2 p-+k Q p-1-( +k) P Q k f ⊗ 2 (X i ).
The proof is divided into two parts.

Part I. First we prove that (34) lim sup

n→∞ 1 b 2 n log P (|V 3 (n) -H 3 (f)| > δ) = -∞. Since H 3 (f) = p =0 2 -µ, f 2 + >p 2 -µ, f 2 and lim n→∞ >p 2 -µ, f 2 = 0,
then to get (34), it suffices to prove that lim sup

n→∞ 1 b 2 n log P |V 3 (n) -H [n] 3 (f)| > δ = -∞, where H [n] 3 (f) = p =0 2 -µ, f 2 .
We set

g p = p =0 2 -Q p-f 2 -µ, f 2 and then V 3 (n) -H [n] 3 (f) = |G n-p | -1 M Gn-p (g p ).
Using ( 2) and ( 5), we have, for some positive constant c α ,

g p ∞ ≤ 4c 2 ∞ c α M 2 -p if 2α < 1 4c 2 ∞ M (p + 1)α p if 2α > 1.
Using (29), we get, for n going to infinity and for some positive constant C α,δ :

P V 3 (n) -H [n] 3 (f) > δ ≤ 2 exp -δ 2 C α,δ |G n+p | if 2α ≤ 1 2 exp -δ 2 C α,δ p -2 |G n |(2α 2 ) -p if 1 < 2α < √ 2.
Finally, (34) follows from the latter inequality by taking the log and dividing by b 2 n .

Part II. Next, we prove that

(35) lim sup n→∞ 1 b 2 n log P (|V 4 (n) -H 4 (f)| > 2δ) = -∞. Note that V 4 (n) -H 4 (f) = |G n-p | -1 M Gn-p (H 4,n (f) -H 4 (f)), where (36)
H 4,n (f) = ≥0,k≥0 h (n) ,k 1 { +k<p} and H 4 (f) = ≥0,k≥0 h ,k , with h (n) ,k = 2 k-Q p-1-( +k) P Q k f ⊗ 2 and h ,k = µ, P (Q k f )⊗ 2 .
Using ( 2) and ( 5), we have

(37) |h ,k | + |h (n) ,k | ≤ 2C 2 ∞ M 2 (2α 2 ) k 2 -. Let r 0 large enough such that (38) 2c 2 ∞ M 2 ∨k>r0 (2α 2 ) k 2 -≤ δ.
For n going to infinity, we have

|M Gn-p (H 4,n (f) -H 4 (f))| ≤ |M Gn- p ( ∨k≤r0 (h (n)
,k -h ,k ))| + M Gn-p ( ∨k>r0 (|h ,k | + |h (n) ,k |)) ≤ |M Gn- p ( ∨k≤r0 (h (n)
,k -h ,k ))| + 2 c 2 ∞ M 2 |G n-p | ∨k>r0 (2α 2 ) k 2 -, (39)
where we used (37) for the second inequality. From (39), we get

(40) |V 4 (n) -H 4 (f)| ≤ |G n-p | -1 |M Gn-p (g p )| + 2 c 2 ∞ M 2 ∨k>r0 (2α 2 ) k 2 -,
where

g p = ∨k≤r0 (h (n)
,kh ,k ). From (38) and (40), to get (35), it suffices to prove that

(41) lim sup n→∞ 1 b 2 n log P |G n-p | -1 M Gn-p (g p ) > δ .
Using (2) and ( 5) twice, we have, for some positive constant c α ,

g p ∞ ≤ c 3 ∞ M 3 c α γ(r 0 )α p-1 where γ(r 0 ) = r 0 (2α) r0 if 2α ≤ 1 (2α) r0 if 1 < 2α < √ 2.
Using (29) with g p instead of f , we get, for some positive constant C α,δ ,

P |G n-p | -1 M Gn-p (g p ) > δ ≤ exp -δ 2 C α,δ |G n-p |α -2p .
Taking the log, dividing by b 2 n and letting n goes to infinity in the latter inequality, we get (41) and then (35).

n log P V 2 (n) -Σ sub 2 (f) > δ = -∞,
where

Σ sub 2 (f) = 0≤ <k 2 -µ, fk Q k-f + 0≤ <k r≥0 2 r-µ, P Q r fk ⊗ sym Q k-+r f := H 5 (f) + H 6 (f)
Proof. Using (66), we get:

(42) V 2 (n) = V 5 (n) + V 6 (n), with V 5 (n) = |G n | -1 i∈Gn-p 0≤ <k≤p 2 p-Q p-k fk Q k-f (X i ), V 6 (n) = |G n | -1 i∈Gn-p 0≤ <k<p p-k-1 r=0 2 p-+r Q p-1-(r+k) P Q r fk ⊗ sym Q k-+r f (X i ).
Part I. First, we prove that

(43) lim sup n→∞ 1 b 2 n log P (|V 6 (n) -H 6 (f)| > 2δ) = -∞.
We have

V 6 (n) -H 6 (f) = |G n-p | -1 M Gn-p (H 6,n (f) -H 6 (f))
, where

H 6,n (f) = 0≤ <k r≥0 h (n) k, ,r 1 {r+k<p} and H 6 (f) = 0≤ <k r≥0 h k, , r , with h (n)
k, ,r = 2 r-Q p-1-(r+k) P Q r fk ⊗ sym Q k-+r f and h k, ,r = 2 r-µ, P Q r fk ⊗ sym Q k-+r f .
Using (2) and ( 5), we have

(44) |h ,k,r | + |h (n) ,k,r | ≤ 2 c 2 ∞ M 2 2 r-α k-+2r . Let r 0 large enough such that (45) 2 c 2 ∞ M 2 0≤ <k r≥0 k∨r>r0 2 r-α k-+2r < δ.
We set g p = 0≤ <k, r≥0, k∨r≤r0 (h

(n) k, ,r -h k, ,r
). Using (44), we have, for n going to infinity in such a way that p > r 0 , (46)

|V 6 (n) -H 6 (f)| ≤ |G n-p | M Gn-p (g p ) + 2 c 2 ∞ M 2 0≤ <k r≥0 k∨r>r0 2 r-α k-+2r .
From (45) and (46), to get (43), it suffices to prove that (47) lim sup

n→∞ 1 b 2 n log P |G n-p | -1 M Gn-p (g p ) > δ = -∞.
Using (2) and ( 5) twice, we have, for some positive constant c α ,

g p ∞ ≤ 2 c α c 3 ∞ M 3 γ(r 0 ) α p , where γ(r 0 ) = (2α) -r0 if 2α < 1 r 2 0 if 2α ≥ 1.
Using (29) with g p instead of f , we get, for some positive constant C α,δ ,

P |G n-p | -1 M Gn-p (g p ) > δ ≤ exp -δ 2 C α,δ |G n-p |α -2p .
Taking the log, dividing by b 2 n and letting n goes to infinity in the latter inequality, we get (47) and then (43).

Part II. Next, with the finite constant H 5 (f) defined by:

H 5 (f) = 0≤ <k 2 -µ, fk Q k-f , we prove that (48) lim sup n→∞ 1 b 2 n log P (|V 5 (n) -H 5 (f)| > 2δ) = -∞.
We set

H 5,n (f) = 0≤ <k h (n) k, 1 {k≤p} , and
H [n] 5 (f) = 0≤ <k h k, 1 {k≤p} , with h (n) k, = 2 -Q p-k fk Q k-f 1 {k≤p} and h ,k = µ, fk Q k-f .
We have the following decomposition:

V 5 (n) -H 5 (f) = |G n-p | -1 M Gn-p H 5,n (f) -H [n] 5 (f) + H [n] 5 (f) -H 5 (f) .
Using (2) and ( 5), we have

|h (n) k, | + |h k, | ≤ 2c 2 ∞ M α k-2 -,
which implies that lim n→∞ |H 5 (f) -H

log P |G n-p | -1 M Gn-p H 5,n (f) -H [n] 5 (f) > δ = -∞.
Setting g p = H 5,n (f) -H

[n] 5 (f), we have, using (2) and (5):

g p ∞ ≤ c α 2 -p if 2α < 1 c α pα p if 1 ≤ 2α < √ 2,
for some positive constant c α . Finally, (49), and then (48), follows by applying (29) to g p instead of f and by taking the log, dividing by b 2 n and by letting n goes to infinity.

As a direct consequence of (30) and Lemmas 5.2, 5.3 and 5.4, we have the following result. Proof. Since p < n/2, we have for all i ∈ G n-p ,

|∆ n,i (f)| ≤ 2c ∞ 2 -n 2 +p ≤ C,
where C is a positive constant. This implies that ∆ n (f) is a martingale with bounded differences. Using the result of Dembo [START_REF] Dembo | Moderate deviations for martingales with bounded jumps[END_REF] (see also Djellout [11] and Puhalski [START_REF] Puhalskii | Large deviations of semimartingales: a maxingale problem approach i. limits as solutions to a maxingale problem[END_REF]), we get the result from Lemma 5.5. (51)

|Q n ( f )| ≤ M α n c ∞ and |Q n ( f )| ≤ M β n α n c ∞
It follows from (51) that there exists a finite constant c J depending only on {α j , j ∈ J} such that for all ∈ N, n ∈ N,

j 0 ∈ J |f | ≤ M c ∞ , | f | ≤ M c ∞ , | µ, f | ≤ M c ∞ , | j∈J θ n j R j (f )| ≤ 2M c ∞ and |R j0 (f )| ≤ c J M c ∞ .
We recall that:

(52) N n,∅ (f) = ∆ n (f) + R 0 (n) + R 1 (n), with R 0 (n) = |G n | -1/2 n-pn-1 k=0 M G k ( fn-k ) and R 1 (n) = i∈Gn-p n E [N n,i (f)| F i ] .
Let (b n ) n∈N be a sequence elements of N such that :

b n → ∞ and b n n|G n | -→ n→∞ 0
Our goals will be achieved if we prove the following:

∀δ > 0, lim n→∞ 1 b 2 n log P(|b -1 n n -1/2 R 0 (n)| > δ) = -∞; (53) ∀δ > 0, lim n→∞ 1 b 2 n log P(|b -1 n n -1/2 R 1 (n)| > δ) = -∞; (54) b -1 n n -1/2 ∆ n (f)
log P |n -1 V 3 (n)| > δ = -∞. Indeed we have n -1 V 3 (n) = |G n-p | -1 n -1 M Gn-p (g p ), where g p = p =0 2 -Q p-( f 2 ). Since the sequence f = (f , ∈ N) satisfies (5), we have g p ∞ ≤ 4c 2 ∞ . This implies that |n -1 V 3 (n)| ≤ 4c 2 ∞ n -1 . So n -1 V 3 (n)
is upper-bounded by a deterministic sequence which goes to 0. Then applying the remark 8.1 to n -1 V 3 (n), we get the result.

Part II. Next, we prove that lim sup

n→∞ 1 b 2 n log P |n -1 V 4 (n) -Σ crit 1 (f)| > δ = -∞.
Recall H 4,n (f) and f k, defined respectively in (36) and ( 13). For k, , r ∈ N, we consider the following C-valued functions defined on S 2 :

(57)

f k, ,r = j∈J θ r j R j (f k ) ⊗ sym j∈J θ r+k- j R j (f ) .
Recall that 2α 2 = 1. We set H4,n =

≥0, k≥0 h(n) ,k 1 { +k<p} with h(n) ,k = 2 k-α 2k Q p-1-( +k) (Pf , ,k ) = 2 -Q p-1-( +k) (Pf , ,k ) .
For f ∈ B b (S), recall f defined in (4). Then we have h

(n) ,k - h(n) k, = h n,1 ,k + h n,2 ,k + h n,3 ,k , where h n,1 ,k = 2 k-Q p-1-( +k) P(Q k fk ⊗ sym Q k fk ), h n,2 ,k = 2 k-Q p-1-( +k) P(Q k fk ⊗ sym Q k ( j∈J R j (f k ))), h n,3 ,k = 2 k-Q p-1-( +k) P(Q k ( j∈J R j (f k )) ⊗ sym Q k ( j∈J R j (f k ))).
This implies that

n -1 |G n-p | -1 M Gn-p (H 4,n (f) -H4,n (f)) = n -1 |G n-p | -1 u∈Gn-p 3 i=1 ≥0;k≥0 h n,i ,k (X u )1 { +k<p} .
Using Assumption 3. We set H where we have used the definition of ∆ n,i (f), the inequality ( r k=0 a k ) 4 ≤ (r + 1) 3 r k=0 a 4 k and the branching Markov property. Using (2) and ( 5), we can apply Theorem 2.1 given in [START_REF] Bitseki Penda | Deviation inequalities, moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF] From ( 14) and (50), we have

(63) lim n→∞ n 3 2 -n+p ((n|G n |) -1 b 2 n ) = 0.
Finally, the result of the Lemma follows using (62), (63) and Remark 8.1.

For Chen-Ledoux type condition, we have the following result. From the latter equality and using the convention log(0) = -∞, we get the result of the Lemma.

We can now state the following result.

Lemma 6.8. Under the assumptions of Theorem 4.3, we have that n -1/2 b -1 n ∆ n (f) satisfies a moderate deviation principle with speed b 2 n and rate function I defined in [START_REF] Delmas | Detection of cellular aging in a Galton-Watson process[END_REF]. Proof. Applying Theorem 1 in [START_REF] Djellout | Moderate deviations for martingale differences and applications to o-mixing sequences[END_REF] (a simplified version is given in Proposition 8.4) to the martingale differences n -1/2 ∆ n,i (f), the proof follows from Lemmas 6.5, 6.6 and 6.7. 6.5. Completion of the proof of Theorem 4.3. Finally, using (52), (53), (54) and Lemma 6.8, we deduce Theorem 4.3.

Numerical studies

For our numerical illustrations, we consider a BMC (X u , u ∈ T) living in [0, 1], with transition with B(α, β) the normalizing constant of a standard Beta distribution with shape parameters α and β. For simplicity, we choose X ∅ such that L(X ∅ ) = Beta(2, 2), where Beta(2, 2) is the standard Beta distribution with shape parameters (2, 2). Now, one can prove that this process is stationary, it has an explicit invariant density: the standard Beta distribution with shape parameters (2, 2). One can also prove that E [X u0 |X u ] = E [X u1 |X u ] = X u /5 + 2/5, (for more details, we refer e.g. to [START_REF] Pitt | Constructing first order stationary autoregressive models via latent processes[END_REF]). Now, it is not hard to verify that this process satisfies our required assumptions. In particular, using for example Theorem 2.1 in [START_REF] Hairer | Yet another look at harris' ergodic theorem for markov chains[END_REF], one can prove that Assumption 3.1 is satisfied with α = 1/5. We are thus in the sub-critical case. First, we will illustrate Theorem 4.1 (and more

P = Q ⊗ Q given by Q(x,

Theorem 4 . 1 .

 41 Let X be a BMC with kernel P and initial distribution ν such that Assumption 3.1 is in force with α ∈ (0, 1/ √ 2). Let f = (f , ∈ N) be a sequence of elements of B b (S) satisfying (5) and Assumption 3.1 uniformly. Then b -1 n N n,∅ (f) satisfies a moderate deviation principle with speed b 2 n and rate function I defined in (8). As a direct consequence of Remark 3.3 and Theorem 4.1, we have the following result.

Corollary 4 . 2 .

 42 Let X be a BMC with kernel P and initial distribution ν such that Assumption 3.1 is in force with

4. 2 . 2 .

 22 The critical cases: 2α 2 = 1. In this critical case, we consider a sequence (b n , n ∈ N) such that:[START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF] limn→∞ b n = ∞ and lim n→∞ b n n|G n | = 0.Then, we have the following result. Theorem 4.3. Let X be a BMC with kernel P and initial distribution ν such that Assumption 3.2 is in force with α = 1/ √ Let f = (f , ∈ N) be a sequence of elements of B b (S) satisfying (5) and Assumption 3.2 uniformly. Then b -1 n n -1 2 N n,∅ (f) satisfies a moderate deviation principle with speed b 2 n and rate function I defined in (8). As a direct consequence of Remark 3.3 and Theorem 4.3, we have the following result. Corollary 4.4. Let X be a BMC with kernel P and initial distribution ν such that Assumption 3.2 is in force with

5 .

 5 satisfy a moderate deviation principle with speed b 2 n and rate function I defined in[START_REF] Delmas | Detection of cellular aging in a Galton-Watson process[END_REF], with Σ(f) replaced respectively by Σ G (f ) and Σ T (f ). Proof of Theorem 4.15.1. A quick overview of our strategy.Let (p n , n ∈ N) be a non-decreasing sequence of elements of N * such that:[START_REF] Pitt | Constructing first order stationary autoregressive models via latent processes[END_REF]

  satisfies a MDP on S with speed b 2 n and rate function I. (20)

Lemma 5 . 3 .

 53 Under the Assumptions of Theorem 4.1, we have

Lemma 5 . 4 .

 54 Under the Assumptions of Theorem 4.1, we have

  )| = 0. As a result, to get (48), it suffices to prove that

Lemma 5 . 5 .sup n→∞ 1 b 2 n

 552 Under the Assumptions of Theorem 4.1, we havelim log P |V (n) -Σ sub (f)| > δ = -∞We can now state the following result. Lemma 5.6. Under Assumptions of Theorem 4.1, we have that b -1 n ∆ n (f) satisfies a moderate deviation principle with speed b 2 n and rate function I defined in (8).

5. 5 . 6 .

 56 Completion of the proof of Theorem 4.1. Finally, using the decomposition (52) and the results of sections 5.2, 5.3 and 5.4, we deduce Theorem 4.1. Proof of Theorem 4.3 6.1. A quick overview of our strategy. Let (p n , n ∈ N) be a non-decreasing sequence of elements of N * such that, for all λ > 0: (50) p n < n, lim n→∞ p n /n = 1 and lim n→∞ np nλ log(n) = +∞. When there is no ambiguity, we write p for p n . Let us consider the sequence f = (f , ∈ N) of elements of B b (S) which satisfies the Assumption (3.2) (and then Assumption 3.1) uniformly, namely:

  satisfies a MDP on S with speed b 2 n and rate function I. (55)Proof. Recall the decomposition of V 1 (n) given in (33) and the definition of Σ crit 1 (f) given in 11. The proof is divided into two parts.

2 , ( 5 )

 25 and the fact that the sequence (β k , k ∈ N) is decreasing, we can upper bound each function |h n,i ,k |, i ∈ {1, 2, 3}, by C2 -β k . This implies that (58) n -1 |G n-p | -1 M Gn-p (H 4,n (f) -H4,n (f)) ≤ Cn -1

h

  ,k 1 {k+ <p} with h ,k = 2 -µ, P(f , ,k ) .

with 2α 2 2 n

 22 = 1 to get E Xi [M G p-( f ) 4 ] ≤ Cp 2 2 2(p-) . The latter inequality and (61) imply that(62) b n|G n | i∈Gn-p n -2 E ∆ n,i (f) 4 |F i ≤ Cn 3 2 -n+p ((n|G n |) -1 b 2 n ).

Lemma 6 . 7 .b 2 n

 672 Under the assumptions of Theorem 4.3, we have lim sup n→∞ 1 log P |G n | sup i∈Gn-pP Fi |∆ n,i (f)| > b n n|G n | = -∞.Proof.Using (5), we have, for n large enough and for all i∈ G n-p , |∆ n,i (f)| ≤ C2 -n 2 +p < b n n|G n |. This implies that P Fi |∆ n,i (f)| > b n n|G n | = 0 ∀i ∈ G n-p .

proof of (53).

We follow the same lines of the proof of (18) with 2α 2 = 1. First, using Chernoff inequality, we have

Next, taking λ = bnδ(n|Gn|) 1/2 2cα(n-p)|Gn-p| and doing the same thing for -f instead of f, we get

Finally, taking the log, dividing by b 2 n and letting n goes to infinity, we get the result.

Remark 6.1. We have the following version of Remark 5.1 when 2α 2 = 1:

(56)

6.3. proof of (54). With g p = p =0 2 p-Q p-f , and using the definition of R 1 (n), we have for all δ > 0

So according to (51) , we have:

By applying (56) to g p and b n δn 1/2 |G p ||G n | -1/2 and using the fact that 2α 2 = 1, we have:

.

So taking the log and dividing by b 2 n , and letting n goes to infinity, we get the result.

6.4. Proof of (55): Moderate deviations principle for b -1 n n -1/2 ∆ n (f). First we study the bracket of n -1 2 ∆ n (f) given by n -1 V (n), where V (n) is defined in (30). We have the following result: Lemma 6.2. Under the assumptions of Theorem 4.3, we have

Proof. Recall the definition of R 2 (n) and g p given in (32). So according to (51) and using 2α 2 = 1, we have

Therefore, R 2 (n) is upper-bounded by a deterministic sequence which goes to 0. According to Remark 8.1, we get the result.

Using Assumption 3.2 and (5), we get

Finally, from [START_REF] Bitseki Penda | Central limit theorem for bifurcating markov chains[END_REF], we have

From (58), ( 59) and ( 60), we conclude that |n -1 V 4 (n)-Σ crit 1 (f)| is upper-bounded by a deterministic sequence which goes to 0. Therefore applying the remark 8.1 to n -1 V 4 (n) -Σ crit 1 (f), we get the result. Lemma 6.4. Under the assumptions of Theorem 4.3, we have

Proof. Recall the decomposition given in (42). Then following the lines of the proof of Lemma 6.3, we prove that lim sup

and the result follows.

As a direct consequence of (30) and Lemmas 6.2, 6.3 and 6.4, we have the following result.

Lemma 6.5. Under the assumptions of Theorem 4.3, we have

Next, contrary to the sub-critical case, we need to check the exponential Lindeberg condition and Chen-Ledoux type condition, that is conditions (C2) and (C3) given in Proposition 8.4. Indeed, in the critical case, the martingale n -1 2 ∆ n (f) does not have bounded differences in such a way that Lemma 6.5 is not longer sufficient to get the moderate deviations principle of n -1 2 ∆ n (f). In order to check exponential Lindeberg condition, we have the following exponential Lyapunov condition which implies the exponential Lindeberg condition. Lemma 6.6. Under the assumptions of Theorem 4.3, we have

Proof. For all i ∈ G n-p , we have

precisely Corollary 4.4) with the sequence f = (f, 0, 0, . . .) and the function f (x) = x. In this case, we have the following exact results:

Next, we will illustrate that the range of speed considered in the critical case does not work in this example. For that purpose, we simulate B = 50000 samples (X (s) = (X

u , u ∈ G 12 ), s ∈ {1, . . . , B}) of the bifurcating Markov chain at the n-th generation, with n = 12. For each sample

). This allows us to get empirical values of the rate function. Next in the same graph, we plot the true rate function and the empirical rate function. As we can see in Figure 1, the empirical rate function fit well exact rate function, except in the last figure where the empirical rate function is near to 0 since the speed considered is not valid for the subcritical case, but only for the critical. We also stress that the differences observed between empirical and exact rate functions can be explained from the fact that the sample size is not large enough.

Appendix

The following Remark is used in the proofs of Lemmas 6.3, 6.4 and 6.2.

Remark 8.1. We assume that (S, d) is a metric space. Let (Z n ) n∈N be a sequence of random variables valued in S, Z a random variable valued in S and v n a rate. So if d(Z n , Z) is upper-bounded by a deterministic sequence which converges to 0, then, for all sequence (v n , n ∈ N) converging to ∞, Z n converges v n -superexponentially fast in probability to Z, that is for all δ > 0, lim sup

The following result is known as Azuma-Bennett-Hoeffding inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF][START_REF] Bennett | Probability inequalities for the sum of independent random variables[END_REF][START_REF] Hoeffding | Probability inequalities for sums of bounded random variables[END_REF].

Lemma 8.2. Let X be a real-valued and centered random variable such that a ≤ X ≤ b a.s., with a < b. Then for all λ > 0, we have

We have the following many-to-one formulas. Ideas of the proofs can be found in [START_REF] Guyon | Limit theorems for bifurcating Markov chains. Application to the detection of cellular aging[END_REF] and [START_REF] Bitseki Penda | Deviation inequalities, moderate deviations and some limit theorems for bifurcating Markov chains with application[END_REF].

Assuming that all the quantities below are well defined, we have:

). In the first three figures, one can see that empirical rate function fit well the exact rate function. The differences can be explained from the fact that the sample size is not large enough to generate enough large deviation events. In the last figure, one can see that the empirical rate function is reduced to 0. This is due to the fact that the speed considered here is valid only in the critical case, not in the subcritical case.

We recall here a simplified version of Theorem 1 in [START_REF] Djellout | Moderate deviations for martingale differences and applications to o-mixing sequences[END_REF]. We consider the real martingale (M n , n ∈ N) with respect to the filtration (H n , n ∈ N) and we denote ( M n , n ∈ N) its bracket. Remark 8.5. For all n ≥ 1, we set m n = M n -M n-1 . Note that, in Proposition 8.4, if the sequence (m n ) n≥1 is uniformly bounded, we recover a simplified version of the result of Dembo [START_REF] Dembo | Moderate deviations for martingales with bounded jumps[END_REF] and if the sequence (m n ) n≥1 is bounded by a deterministic sequence, we recover a simplified version of the result of Puhalskii [START_REF] Puhalskii | Large deviations of semimartingales: a maxingale problem approach i. limits as solutions to a maxingale problem[END_REF].


Clément Christophe
email: clement.christophe@edf.fr

Julien Velcin
email: julien.velcin@univ-lyon2.fr

Jairo Cugliari
email: jairo.cugliari@univ-lyon2.fr

Philippe Suignard
email: philippe.suignard@edf.fr

Manel Boumghar
email: manel.boumghar@edf.fr

Change detection in textual classification with unexpected dynamics

Keywords: Change Detection, Text Streams, Forecasting

come

Introduction

Nowadays, companies all over the world receive a considerable amount of feedback from clients. A major part of these feedback is done by email and companies that receive large quantities of emails have implemented classification algorithms based on pre-defined classification schemes. These schemes are implemented by domain experts who know which type of feedback clients will send to the company. In other words, they expect some topics of discussion to be more present in the data, because they have a profound understanding of the field and of the market. However, these classification schemes may have to evolve in the future. Observing changes in a classification scheme for streaming data is a crucial task for companies to solve. An unexpected change in the volume of documents covered by one category or another can be a sign of a new emerging problem. Therefore it could mean that the classification scheme should be updated. On one hand, some categories may have a temporal pattern: they occur more frequently at the beginning of the year, month, or week, or during specific seasons. On the other hand, it is essential for companies to be able to detect as soon as possible if the frequency of a category is evolving unexpectedly over time.

While analyzing textual data streams, it is common to model the information in order to detect events, outliers or new topics [START_REF] Pimentel | A review of novelty detection[END_REF]. For example, methods like [START_REF] Allan | Detections, bounds, and timelines: Umass and tdt-3[END_REF][START_REF] Long | Towards effective event detection, tracking and summarization on microblog data[END_REF][START_REF] Metzler | Structured event retrieval over microblog archives[END_REF][START_REF] Huang | Topic detection from large scale of microblog stream with high utility pattern clustering[END_REF][START_REF] Peng | Emerging topic detection from microblog streams based on emerging pattern mining[END_REF] are designed to raise an alert as soon as a different document is detected but the core contribution resides in the mathematical definition of this difference. This is why these methods are well suited for different tasks like event, outlier, first-story detection.

Authors of Online-Latent Dirichlet Allocation (OLDA) [START_REF] Lau | On-line trend analysis with topic models:\# twitter trends detection topic model online[END_REF] developed an unsupervised topic model that can be used to raise an alert as soon as the meaning of a latent topic is changed by the publication of documents. Finally, TopicSketch [START_REF] Xie | Topicsketch: Real-time bursty topic detection from twitter[END_REF] is designed to raise an alert if the frequency of single words or their co-occurrences evolve in an unexpected manner. Even if these methods monitor different entities of the textual content, we notice that the transformation from text to time series is one of their main method in common. In this work, we compare our model to two baselines. The first is [START_REF] Allan | Detections, bounds, and timelines: Umass and tdt-3[END_REF] which has, according to their conclusion, hit the limit of simple Information Retrieval approaches. Partly because they are using only one feature (TF-IDF) to represent the textual content in a bag-of-words setting. The second is [START_REF] Xie | Topicsketch: Real-time bursty topic detection from twitter[END_REF] which is a state of the art method for the task of event detection using only textual content. These methods are built to detect sudden and short burst in the data and not long-term change.

The field of novelty detection in textual data is a rather recent field with an illposed problematic. While it has been studied in several manners and contexts [START_REF] Markou | Novelty detection: a review-part 1: statistical approaches[END_REF][START_REF] Tsai | Multilingual novelty detection[END_REF][START_REF] Christophe | How to detect novelty in textual data streams? A comparative study of existing methods[END_REF], there is no existence of a general framework or evaluation methods. When looking at a textual data stream, we can consider different types of novelty: a neologism, a new topic, a change in the distribution of the data, etc. We separate the field of novelty detection into two distinct tasks:

-Volume Novelty: it is observed in known entities of the textual contents as words or topics. It resides in the temporal aspect of these entities. For example: the frequency of a word or of a known category can vary in unusual ways. -Structure Novelty: it is observed when an underlying change in the distribution of the data is detected, or when it concerns unknown or abstract entities of the textual content. For example, with the appearance of a new word or of a new topic. Also, some complex changes can be observed: topics can merge together, the underlying distribution of a topic can be so modified that there is a change in the meaning.

While the two tasks are different in nature, they are often intimately linked: the change in the frequency of a certain word can be a sign of the appearance of a new topic and vice-versa. However, by considering these tasks distinctively, we can develop a framework to resolve them. In this work, we will focus on the resolution of the first type of novelty: Volume novelty. This type of novelty is easier to analyze in a quantitative point of view and is very present in our industrial use-case. We will work with two textual datasets: the New York Times Annotated Corpus (NYTAC) and the Électricité de France (EDF) dataset for industrial use. These datasets contain news articles written by the New York Times and anonymized emails sent by clients to EDF. Each document is classified into a particular category of a classification scheme: manually for the New York Times and automatically for EDF. Volume of documents classified into each category at each time-step can vary over time so we will analyze this dynamic and detect unexpected changes.

In this work, we challenge a classification scheme already used by EDF. We do not want to detect abnormal values as outliers or anomalies but we expect to find an aggregation of these odd values that gives us information about the change of a category. This task is often solved in other fields of application: in industrial processes [START_REF] El-Shal | A fuzzy expert system for fault detection in statistical process control of industrial processes[END_REF], healthcare [START_REF] Noyez | Control charts, Cusum techniques and funnel plots. A review of methods for monitoring performance in healthcare[END_REF], product quality [START_REF] Macgregor | Statistical process control of multivariate processes[END_REF], power monitoring [START_REF] Lazzaretti | Novelty detection and multi-class classification in power distribution voltage waveforms[END_REF] or cybersecurity [START_REF] Tartakovsky | Efficient computer network anomaly detection by changepoint detection methods[END_REF]. A popular choice among these methods is the use of sequential analysis algorithm like the Cumulative Sum Control Chart (CUSUM) [START_REF] Page | Continuous inspection schemes[END_REF] to raise an alert when the signal differs from previous (labelled as "normal") behavior. These methods use time series monitoring to raise alerts when changes occur. They are not well-suited for textual data and they do not necessarily use forecasting algorithms. We aim to solve our problem in two parts, first by forecasting the evolution of the monitored signal and then by analyzing the forecasting error. Our main objectives are as follows:

1. to learn the underlying dynamics of categories inside a classification scheme. 2. to raise an alert when a learned dynamic seems to change. 3. to be as quick as possible to detect the change. 4. to limit the number of false alarms in term of extreme value: we do not want to raise alarms for one-time changes.

In this paper, we present an algorithm able to raise alerts as soon as a non-predicted change in the volume of documents labelled into one category is detected. We assume that the documents are automatically labelled into pre-defined categories by a classification scheme. In Section 2, we start by detailing how we use exogenous variables to forecast a signal and how we apply the CUSUM algorithm to raise alerts. In Section 3, we present our dataset and the different textual features used for grounding the forecasting mechanism. Finally, in Section 4 we present our evaluation methodology and the different results we obtained.

Methods

In this work, our main hypothesis is that novelty appears when we are not able to correctly forecast the future. With that idea in mind, we transform our textual content into time series signals and we use a known forecasting algorithm in order to learn the dynamics and predict the evolution of our classification scheme.

Univariate forecasting method

Since the novelty that we want to detect corresponds to an unexpected change in the volume of a signal, we use forecasting methods to predict what should be the normal behavior of our signal [y 1 , y 2 , ..., y t , ..., y N ]. In simple words, we assume that the normal expected behavior at time t can be expressed as :

y t+1 = h(y 0,...,t ) + t
where t is a zero correlation white noise process.

We predict only the next value of our signal y t+1 using the past values y 0,...,t . In this section, we present two forecasting algorithms: the first one is based on K-Nearest Neighbors [START_REF] Martinez | Time Series Forecasting with KNN in R: the tsfknn Package[END_REF], and the second one is based on ARIMA.

-K-Nearest Neighbors: traditionally used in classification and regression, we can use the KNN algorithm for prediction. Let l be a positive integer representing a maximum lag, then we use the l previous values y t,...,t-l to predict the next value y t+1 . Applying a rolling mechanism, we are able to train a model with some features [y t,...,t-l ] and targets y t+1 . -ARIMA: AutoRegressive Integrated Moving Average is one of the most popular linear models in time series forecasting. It is based on the assumption that it is possible to forecast a signal using only its past values. It is a linear regression model that uses its own lags as predictors.

2.2 Forecasting using exogenous variables.

We use a forecasting model3 based on constructed features derived from our initial textual data. Let [y 1 , y 2 , ..., y t , ..., y N ] be a time series where y t is the value of the time series at time t (e.g., hours, days or months) and [x 1f , x 2f , ..., x tf , x N f ] be a multivariate time series where x tf is the value of feature f at time t. Our model should be in the form:

y t+1 = h(x t,1 , x t,2 , ..., x t,F ) + t
where F is the number of features used and t is an error term. The function h maps an entry x t ∈ R F to y ∈ R + .

We use a Random Forest [START_REF] Breiman | Random forests[END_REF] to estimate the function h. Although this algorithm is often used for classification, it is also well suited for prediction and time series forecasting [START_REF] Kumar | Forecasting stock index movement: A comparison of support vector machines and random forest[END_REF]. Compared to more recent methods based on neural networks, Random Forest has the advantage to give us information about feature importance. It estimates this importance by measuring how much the prediction error increases when data for that feature is permuted while others are left unchanged.

The time period δt is constant: it can be hours, days or months. The random forest model is trained on a subset of the data with t ∈ {1, ..., t c } with t c being a constant marking the end of the training window. Once the model is trained, we can use it to forecast ŷt+1 for t ∈ {t c+1 , ..., t N }. To this end, we use a rolling mechanism where at each point, we obtain a 1 time-step ahead prediction. The model is evaluated by looking at the error between the prediction and the actual value: e t+1 = y t+1 -ŷt+1 . We make the assumption that a large error of prediction is a sign of change. In consequence, we monitor the evolution of e t to detect out-of-control behavior.

Cumulative Sum Control Chart

Very popular in statistical processes control, the Cumulative Sum Control Chart (CUSUM) is a sequential analysis method conceived to detect changes on processes. For this, a statistic based on cumulative sums s t is computed and tracked [START_REF] Kenett | Modern Industrial Statistics: with applications in R, MINITAB and JMP[END_REF]. Deviations from a target value are successively added to get consistent departures of the CUSUM statistic when the process deviates from the target.

A test statistic g t sums up its input s t with the idea to raise an alarm when the sum exceeds a threshold h. In order to prevent positive drifts caused by noise in the data, a drift term ν is subtracted at each time-slice. To prevent negative drift, g t is reset to 0 each time it falls lower than a threshold a. Mathematically,

g t = max(g t-1 + s t -ν, 0) or max(g t-1 -s t -ν, 0), an alarm is raised if g t > h
In our case, we track the prediction error which should stay in a process of controlled variations since we assume it should be close to white noise. For this, let θt =

1 t-t0
e k be the cumulative statistic over the period started just after the last observed alarm t 0 . Then, at time t we observe the change on the statistic given by s t = e t -θt-1 .

CUSUM method depends on two parameters that control the sensitivity to change in the process: threshold h and drift ν. For most applications using CUSUM, values of these parameters can be fixed manually after a thorough analysis of the monitored process. In our case, since we are monitoring several signals at the same time, we compute automatically the values of these parameters. We update our CUSUM parameters based on the maximum values of each of our monitored signal (taken during the training phase): it presents the advantage that raised alerts are not dependent on the different magnitudes of the signals.

h = 1
2 max(y 1,...,tc ), This threshold value represent the sensitivity to the error of our prediction model. Since we want to limit the number of false alarms and the detection of very small bursts, we fixed this value while experimenting. With the same idea in mind, the drift parameter ν was set to 2.

3 Data and feature importance

Data

We test our method on two datasets: one public dataset (New York Times Annotated Corpus) and one dataset constituted of anonymized client emails for industrial use for EDF (Electricité de France). Their characteristics are summarized in Table 1.

The New York Times Annotated Corpus (NYTAC)4 is a public corpus of written articles published by the New York Times between 1987 and 2007. It contains more than 1.8 millions articles that were manually annotated into categories (e.g., Terrorism, Motion Pictures, Politics, Economy). For this work, we focus on the articles published between 1995 and 2005. In order to illustrate our approach, we selected some specific categories to monitor, for example: Terrorism, Basketball, United States International Relations, Motion Pictures, Elections and Colleges and Universities. Figure 1 illustrates the temporal dynamics of these categories in our dataset in terms of number of documents labelled under a category by month. We also selected some categories with noisy and constant behavior in order to properly evaluate our approach. Our dataset contains 13 categories. Electricité de France (EDF) is the main french electricity producer. With more than 35 millions clients, EDF receives hundreds of thousands emails per month. In order to best process this data, the business entity have implemented classification methods based on classification schemes constructed by business experts. However, they noticed that the volume of emails associated with each category may vary unusually over time. From a business point of view, it is essential to have a system able to raise alerts when the volume of documents in a category is evolving unusually. The EDF emails corpus is a private and anonymized (in accord with GDPR regulations) corpus of email, in french, sent by clients to EDF between October 2018 and October 2019. EDF classification scheme is organized between 12 main categories but only 8 are exploited in this work because some are unusable: due to very low volume, empty email or containing spam.

Exogenous variables

We now describe three families of features used in our prediction model:

Frequency of words: we count the occurrences of certain words each day. Since we work with pre-defined categories, we are able to select automatically a certain number of words closely related to one category. For each category, we select a certain number of words to monitor. In addition to the raw frequency of the words, we consider the lag of the frequency ∆ p f w t = f w t -f w t-p . We chose to work with p = 7 or p = 365 to represent the weekly and yearly seasonality. In the EDF dataset, since we only have one year of data, we work only with a weekly lag of p = 7. These values of lags are illustrated on Figure 3, we see that the Basketball category presents 10 periods over 3650 data points (yearly seasonality) and Motion Pictures category present 7 periods over 49 data points (weekly seasonality). Frequency of topics: Latent Dirichlet Allocation (LDA) [START_REF] Blei | Latent dirichlet allocation[END_REF] is a topic modeling algorithms that seeks to discover topic structures hidden in a textual dataset. Using probabilistic generative model, it describes each document as a mixture of topics θ d and each topic as a distribution over the vocabulary φ z . In this work, we train a LDA model on our train dataset D train = D 0 , D 1 , ...D tc with 30 and 20 topics respectively for the NYTAC and EDF dataset with |D t | being the number of document published at time t. We form signals corresponding to the number of times a given topic occurs each day. For each document arriving in our corpus in a streaming manner, we infer its mixture of topic by observing the words that compose it. We have a time series:

[k 1,i , ..., k t,i , ..., k T,i ] and k t,i = 1 |Dt| |Dt| j=1 p(z i |d j,t )
With z i being ith topic and d j a document in D t . We also represent this time series with lags values at p = 7 and p = 365.

Table 2 shows the 5 most probable words associated with some topics built with LDA and Figure 4 shows the frequency of these topics over the entire corpus of the New York Times. We observe that information is carried by the words associated with each topic but also by its temporal aspect. For example, we notice a change of behavior over time in topic 17, as well as a cyclic pattern in topics 7 and 21 that can give us information about the temporal dynamics of our data. We will see in Section 4 that these unsupervised topics behaviors are useful to predict the evolution of our classification scheme.

Frequency of co-occurrence of topics: for each topic pair z i,j we count the number of times they occur in the same documents at time t. A topic z i is considered as present in a document if p(z i |d) > 0.1. This threshold is chosen to maximize the impact of these features on forecasting.

Feature selection

In Section 3.2, we saw that we select a certain number of features to include in our forecasting model. Indeed, since it is computationally expensive to monitor the frequency of the entire vocabulary, we choose to automatically select a few unique words that describe effectively the category we are monitoring.

In order to select which words to monitor for each category in the NYT, we solve a classification problem with a Naive Bayes classifier on the training part of our data (from 0 to t c ). We represent each word in a term frequency-inverse document frequency (TF-IDF) space. TF-IDF for a term t of a document d in our document set is computed as follows:

tf idf (t, d) = tf (t, d) * idf (t) idf (t) = log[ n df (t) ] + 1
where n is the total number of documents in the document set, tf (d, t) the frequency of term t in document d and df (t) is the document frequency of t; the document frequency is the number of documents in the document set that contain the term t. While this classifier obtains 87% of accuracy on the New York Times, we are more interested at observing the most discriminative features for each class. Some of these are provided as examples in Table 4.We chose to solve our classification problem with a Naive Bayes classifier on a TF-IDF matrix because it is simple, fast to compute and has good performance over our two datasets and is also easier to generalize to other datasets and other languages.

Categories presented in the EDF dataset are more specific. While it would be possible to apply the same technique to select words to monitor, we preferred to use the internal expertise of the company to determine the important features. We asked some business experts to manually select some words to monitor for each category.

Experiments and results

In this Section, we measure the contribution of the exogenous variables to the forecasting algorithm. We show how the different features contribute to the forecast and explain them. We present the results obtained by our model CDPred (for Change Detection with Prediction) in terms of consistence of alerts: we want a model able to raise alerts at the right time. We explore the timeline of alerts raised and link them with real events on the New York Times dataset. We compare the sensitivity to change and the amount of change needed to raise an alert between CDPred and some baselines. Finally we present the alerts raised in an industrial context and how it can be useful to EDF.

Contribution of the exogenous variables

In this Section, we present the forecasting performance of the models presented in Section 2. Our main hypothesis is that some observable variables in the textual content of our data are useful to accurately forecast the evolution of a signal (i.e. the volume of documents classified into a category). We compare the Root Mean Square Error (RMSE) of our different forecasting models:

RM SE = N i=1 (ŷi-yi) 2 N
with ŷi being the predicted value of the time series at time i, y i the true value, and N the length of the time series.

Since we have one model per category, we compute the mean of all our RMSE for the whole dataset. RMSE could hide different behavior between signals of each categories as they have different magnitudes. We observed that the difference in RMSE between models is overall proportional.

Results are presented in Table 5. We observe an overall better prediction using a Random Forest Model using exogenous variables. It is important to note that the best combination of parameters have been used for each forecasting model. For example, the random forest model used for forecasting has a hyperparameter n corresponding to the number of trees in the forest. Here n = 500 has been chosen using a k-fold cross validation (k = 10). Since the Random Forest is the best model for prediction, we will present the results (in terms of alerts raised) using this model.

Feature importance

First of all, as we use a Random Forest model for prediction, we can observe the feature importance for the forecasting of each category. Table 6 shows some features importance for 5 categories of the New York Times. The words associated with the topic shown in this Table are presented in Table 2. Table 7 shows the features importance for 4 categories of the EDF dataset.

For most of the monitored categories, frequencies of certain words are more important for the forecast. For the New York Times, the 6 most useful features about the Terrorism category are words frequencies and nearly all are about the words "Bombing" and "Federal". Indeed, the raw frequency brings information and the use of lags is also useful for the forecasting. These lags carry information about the change in periodicity of the time series and seem to be helpful in case of sudden peak in the data. We will discuss this hypothesis later. In the EDF dataset, we observe that the Digital category is best described with the help of 4 words frequencies.

In some categories, for example Motion Pictures, Art and, most importantly US Itl. Relations, information is contained in the LDA topic signals. Indeed, its main feature is the signal corresponding to the evolution of Topic 17. In Table 2, Topic 17 is about US President and its top words are about the United States and the American President Clinton. It is a good description for a US Itl. Relations category in the New York Times.

Also, we observe that for categories Basketball and Relation, the co-occurrence signal of 2 topics brings some information for the forecasting algorithm. For Basketball, Topic 7 and 12 are, respectively about College Sports and Justice. While the first is rather close to basketball in term of words used, we could argue that the second brings information because of the word "Court" having a meaning in both basketball and justice context and because of several justice cases around the NBA (National Basketball Association) in the early 2000s. 6. Top features used for each category forecast on the New York Times. " 365" and " 7" indicate, respectively, the use of the lag p = 365 and p = 7."Cooc" indicates the Frequency of co-occurrence of some topics

Baselines

In order to evaluate our model CDPred, we compare it to two baseline from the literature. Our first baseline is adapted from Allan et al., 2000 (TF-IDF) where a method to detect and track new topics is presented. This method is based on the popular term frequency-inverse document frequency (TF-IDF) statistic and is built to raise alerts on 7. Top features used for each category forecast on the EDF dataset. "Cooc" indicates the Frequency of co-occurrence of some topics particular terms when their TF-IDF statistics cross a manually-determined threshold. The second algorithm is Xie et al., 2016 (TopicSketch). It is an algorithm based on the monitoring of physical measurements (speed, acceleration) of textual entities (words and n-grams). It is built to raise alert when these statistics have crossed a threshold.

In order to compare to CDPred that raises alerts not on specific words but rather on a signal, we selected alerts raised on words that are clearly linked with our categories. We selected 100 words per category with the method presented in Section 3.3. Selected words seem to discriminate as much qualitatively (Table 4) as quantitatively (Table 6)

In Xie et al., 2016 (TopicSketch) and Allan et al., 2000 (TF-IDF), threshold values are set manually. We ran experiments with different values of threshold and we present the optimal results in terms of number of alerts raised. It means that we are minimizing the ratio between number of interesting and false alerts. These are presented in Figure 6.

We clearly see that for Allan et al., 2000 (TF-IDF), alerts are raised randomly compared to the observed signal. We notice a great number of alerts around the peak in US Itl. Relations but other than that, we can conclude that this method is not effective to resolve our task. Xie et al., 2016 (TopicSketch) seems to raise false alarms in categories such as Theater and Art. Alerts raised in Basketball and US Itl. Relations make sense compared with the dynamic of the signal. In Basketball, Xie et al., 2016 (TopicSketch) has a tendency to raise alerts at each peak of the season. In US Itl. Relations, we notice that it raises alerts at each small peak in the volume of documents classified under this category. While it seems to be a good solution to detect sudden bursts in the data, it is not a good method to detect long-term changes in the dynamic. In other words, it has no memory of the usual dynamic of the monitored signal.

4.4 Alerts raised on the New York Times.

In Figure 7, we can see the alerts raised by our model in 6 categories annotated in the New York Times: Terrorism, US International Relations, Basketball and Politics and Government, Elections, Colleges and Universities. These categories are studied here because they are the ones that present an interesting temporal aspect. Terrorism, US International Relations and Elections categories are linked with major events that conducted in massive changes in the editorial slant of the New York Times and obviously For bursts 2 and 4, we see that our alerts raised by CDPred are well localized around these events. For US International Relations, compared to alert raised by our baselines in Figure 6, we see that our alerts are much more consistent with real world events. For burst 3, even if the peak is much lower than burst 4, it has considerably changed the proportion of articles tagged under the US International Relations category for a duration of 2 month. We see that our system has correctly detected this burst very early.

For burst 1, it has provoked only a one-day surge in the number of article tagged under the Terrorism category, we could reasonably argue that it is a false alarm, as it do not correspond to more long term change in the classification. However, it also corresponds to a very abnormal peak in the volume of document under this category. For burst 5, we see that, even if elections correspond to a cyclic signal, the peak around November 2002 is abnormal in terms of volume and start earlier than usual.

Categories about Basketball and Politics and Government are also interesting to monitor. The Basketball signal is cyclic, as it follow the NBA and NCAA season in the United States. We see, in Figure 6, that our TopicSketch baseline has a tendency to raise an alert every time a peak in present in the signal, even if this peak happen every year. On the other hand, we see that our model CDPred did not raise any alert for this category. We can conclude that it has correctly learned the correct dynamic of the category. The Politics and Government category seem to be fairly constant but also very noisy over time. By looking at the signal, we could hardly argue that a change has occurred in the dynamic of the category. However, CDPred has raised an alert at the following date: 2nd January 2002. This date corresponds to the day of the inauguration of the new mayor of New York City Michael Bloomberg.

In Figure 8, we present other categories annotated in the New York Times: Art, Theater, Automobiles and Dancing. These categories all have a fairly constant but noisy signal: no changes in the dynamics are observed in these categories. We see that, compared to alerts raised by our baselines presented in Figure 6, our model CDPred did not raise a lot of alerts. Only 4, that can be considered as false alarm, have been raised by CDPred on these 4 categories.

In Table 8 we can observe the difference between the date of the events detected by CDPred in 7 and the date of the first alert raised by CDPred compared to our baselines. We have ∆ method = t change -t alert . We notice that, for very big bursts, like the WTC terrorist attacks and the start of Iraq War, the three model are able to raise alerts fairly quickly. However, our model CDPred detect the unexpected change in the volume faster than the others. We saw that the entry of NATO in the Kosovo War had an long term impact on the dynamic of the US International Relations category and we observe in this table that CDPred was faster that TopicSketch to detect the change and that the baseline TF-IDF never detected it. Finally, we see in Figure 8 that some categories do not seem to present any change in their dynamics, they are fairly constant so they should not present any alerts raised during our monitoring. We present in Table 9, the number of alerts raised in these cate-Fig. 7. Alerts raised by CDPred (dotted blue) on 6 categories of the NYTAC gories by our model CDPred and the other baselines. These alerts are considered false alerts as they do not correspond to real major events that have been identified or to any changes of dynamics. We see that our model is less likely that tfidf [START_REF] Allan | Detections, bounds, and timelines: Umass and tdt-3[END_REF]TopicSketch Xie et al., 2016 to raise false alerts on these constant categories.

In this Section, we observed the results of our model CDPred on different tasks. While it is difficult to evaluate quantitatively this type of model, we saw that our approach is efficient to detect bursts that have a long-term impact on a signal. We saw that CDPred is less prone to raise alerts on one-time burst, and to raise false alarm when the dynamic of the signal is not changing. Also, CDPred seems to be faster than the

Industrial application

We mentioned in Section 1 that the main motivation behind this work was to be able to raise early alerts when changes in the dynamics of a classification scheme are detected. The CDPred model has been studied in an industrial context and we will present in this Section the main results on the EDF dataset, presented earlier.

In Figure 9, we observe the alerts raised for 4 categories: Relation with EDF, Accessibility, Digital and Solidarity. -For Accessibility, we see that the change of dynamic that has begun around 2019-06 is clearly detected by our model and that a lot of alerts are raised after that because the new dynamic still do not correspond to the normal dynamic observed during training time.

-For Solidarity, we observe a peak occurring for about two months (between 2019-04 and 2019-06) that is also clearly detected by our model. It is interesting to note that this peak is detected even if the normal volume of documents classified under this category is very low: about one or two documents per day. -For Relation with EDF, the unusual volume seems to appear at the beginning of our observation (even during training time). We see that the end of this burst is detected at the beginning of 2019-01. -Finally, for Digital, three alerts are raised, one in 2019-06 that does not seem to correspond to any change in the dynamic and two other that are occurring at a sudden peak in the volume of document. These alerts may be considered as false alarms. However, we can see that the change of dynamic seems to appear at the very end of our observation and it is legitimate to wonder whether, with a few more observations, we could have detected this change.

Compared to the New York Times, the EDF dataset has less one-time burst and some categories contains real changes of dynamics during our period of observation. We saw that CDPred is able to detect this changes and, since it is a private corpus, we are not able to discuss the reason behind these changes.

Conclusion and future work

In this work, we presented an algorithm capable of raising alerts of unexpected change in a stream of textual documents. To this end, we cast our textual content in the form of a temporal signal and we observed the changes in the volume of a category. We based our method on the hypothesis that an unexpected change in a signal is tied to a greater forecasting error. Instead of using traditional endogenous forecasting method directly on the signal, we used exogenous variables observed in the textual content of our dataset. Using classical textual analysis and topic modeling techniques to build these features, we showed that we obtain a better forecasting model without adding much more complexity. The goal of this work was not to obtain a perfect forecasting model but rather having a model with information about the underlying signal it tries to predict. Random-Forest algorithm for prediction has been chosen due to its great explicability in relation with the textual features.

Then we combined this forecasting model with a sequential analysis method, traditionally used in the monitoring of industrial process. By applying the CUSUM algorithm on our prediction error, we are able to evaluate its stability and to raise alerts as soon as it is considered unusual. We demonstrated that our model is good at noticing large bursts and also better than the well-established methods chosen as baselines for small bursts. By being based on a forecasting algorithm, our model present the advantage of not being sensitive to cyclicity. Indeed, we showed that, compared to the baselines, it does not raise any alerts when the signal is cyclic. Finally, CDPred is less sensitive to noise in the sense that it raises less false alarms on one-day events and on constant categories.

In terms of textual features, it may be interesting to study other types of information, such as the number of verbs, nouns and adjectives since it should differ from one category to another. Another interesting feature to represent our textual entities could lie in the use of embeddings models such as Word2Vec [START_REF] Mikolov | Distributed representations of words and phrases and their compositionality[END_REF]. For our forecasting model, we chose a simple Random Forest because we kept in mind that one of the main extension of this work could be on the explicability of the alerts. We can analyze the importance of each feature to identify the words or documents responsible for an alert. Also, a good extension to the model would reside in the possibility to validate an alert in order to avoid large group of alerts concerning the same event (e.g. categories Terrorism, US Itl. Relations and Accessibility. Finally, since we observed the change in the dynamic of a textual data stream and we developed an explainable model concerning this change, we suppose that it would be possible to learn to detect the weak signals appearing before the change.

Fig. 1 .

 1 Fig. 1. Evolution of the number of articles published under different categories per day in the NYTAC.

Fig. 2 .

 2 Fig. 2. Evolution of the number of emails sent under different categories per day in the EDF corpus.

Fig. 3 .

 3 Fig. 3. Auto-correlation for 2 categories of the NYTAC. We see an yearly (left) and weekly (right) seasonality.

Fig. 4 .

 4 Fig. 4. Evolution of the frequency of some topics over time on the New York Times dataset.

Fig. 5 .

 5 Fig. 5. Evolution of the frequency of some topics over time on the EDF dataset.

Fig. 6 .

 6 Fig. 6. Alerts raised by our baselines TF-IDF (Allan et al., 2000) ( dotted green) and TopicSketch (Xie et al., 2016) (orange) on 4 categories of the NYTAC

Fig. 8 .

 8 Fig. 8. Alerts raised by CDPred (dotted blue) on 4 categories of the NYTAC

Fig. 9 .

 9 Fig. 9. Alerts raised by CDPred (dotted blue) on 4 categories of the EDF Dataset

Table 1 .

 1 Summary of datasets used for this work

	dataset docs language # of used cat. # of used docs	time range	time range for train (tc)
	NYTAC 1.8M English	13	400k	1995-2005	1995-1998
	EDF 100k French	8	80k	Oct.2018-Oct.2019 Oct.2018-Jan.2019

Table 2 .

 2 Top words associated with some topics on the NYT dataset.

	Basketball Justice College Sports Cinema	Art US President
	Game	Case	Tournament	Film	Work	State
	Point	Court	College	Movie	Show	United
	Team	Lawyer Connecticut	Director	Art	American
	Knicks	Judge	State	Hollywood Artist	Clinton
	Second	Trial	National	Star	Image	President
	Topic 21 Topic 12	Topic 7	Topic 29 Topic 6 Topic 17
	Access	Consumption Monitoring Communication Invoices Contract change
	Fil		Equipe		Pièce	Compte	Contrat
	Consommation		e.quilibre	Jointe	Suite	Demande
	Acces		Consommation	Trouver	Facture	Service
	Jour		Electricité	Téléphone	Service	Résiliation
	Actualité		Distribuer	Ci-joint	Réclamation	Offres
	Topic 8		Topic 11	Topic 7	Topic 5	Topic 15

Table 3 .

 3 Top words associated with some topics on the EDF dataset.

Table 4 .

 4 Most discriminative words for some categories of the New York Times

	Terrorism	Art	Motion Pictures Basketball US Itl. Relations
	attack	art	film	game	clinton
	terrorist museum	movie	knicks	united
	state	painting	actor	team	state
	official	artist	director	point	president
	federal	work	hollywood	player	american
	american gallery	directed	basketball	official
	people	show	story	season	nato
	united exhibition	character	net	palestinian
	bombing sculpture	theater	coach	administration
	terrorism	new	festival	play	china

Table 5 .

 5 RMSE of different prediction algorithms. KNN-Prediction and ARIMA are univariate and Random-Forest is using exogenous variables described in Section 3.

	Algorithm	Mean RMSE on NYTAC Mean RMSE on EDF
	KNN-Prediction	4.15 ± 1.22	13.08 ± 1.88
	ARIMA	3.97 ± 1.08	10.41 ± 1.52
	Random-Forest	2.41 ± 0.82	7.87 ± 1.36

Table 8 .

 8 Absolute value of the ∆ (in days) between the actual day of the change and the day of the alert.Sketch corresponds to[START_REF] Xie | Topicsketch: Real-time bursty topic detection from twitter[END_REF] and tfidf corresponds to[START_REF] Allan | Detections, bounds, and timelines: Umass and tdt-3[END_REF]

	Category	Event	t change ∆ tf idf ∆ Sketch ∆ CDP red
	Terrorism	Security tightening 1998-08-21 33	19	0
	Terrorism	WTC terrorist attacks 2001-09-11 3	1	1
	US Itl. Relations	Kosovo War	1999-03-23 251	13	10
	US Itl. Relations	Iraq War	2003-03-20 12	5	0
	Elections	Mid Terms Elections 2002-08-30 14	11	7

Table 9 .

 9 Categories N Sketch N tf idf N CDP red Number of false alerts N raised by each model for different constant categories. Sketch corresponds to[START_REF] Xie | Topicsketch: Real-time bursty topic detection from twitter[END_REF] tfidf corresponds to Allan et al., 2000.

	Art	10	32	0
	Murders	6	10	0
	Theater	11	24	1
	Travel	4	18	1
	Dancing	2	8	1
	Automobiles	5	10	2

Reproducibility code is available at https://github.com/clechristophe/ CPDPred

https://catalog.ldc.upenn.edu/LDC2008T19