William Charky Kengne
email: william-charky.kengne@malix.univ-paris1.fr

Testing for parameter constancy in general causal time series models

Keywords: Semi-parametric test, Change of parameters, Causal processes, Quasi-maximum likelihood estimator, Weak convergence

come

Testing for parameter constancy in general causal time series models

Introduction

Many statistical data can be represented by models which may change over time, for instance hydraulic flow, climate data. Before any inference on these data, it is crucial to test whether a change has not occurred in the model.

Since Page [START_REF] Page | A test for a change in a parameter occurring at an unknown point[END_REF] in 1955, real advances have been done about tests for change detection. Horvath [START_REF] Horváth | Change in autoregressive processes[END_REF] proposed a test for detecting a change in the parameter of autoregressive processes based on weighted supremum and L p -functionals of the residual sums. The CUSUM statistic which was introduced by Brown et al. [START_REF] Brown | Techniques for testing the constancy of regression relationships over time[END_REF] in 1975, was modified by Inclan and Tiao [START_REF] Inclan | Use of cumulative sums of squares for retrospective detection of changes of variance[END_REF] for testing change in variance of independent random variables.

Their test has asymptotically correct size but the asymptotic power is unknown. Numerous works devoted to the CUSUM-type procedure, for instance Kim et al. [START_REF] Kim | On the CUSUM test for parameter changes in GARCH(1, 1) models[END_REF] for testing change in parameters of GARCH(1,1), Kokoszka and Leipus [START_REF] Kokoszka | Leipus Testing for parameter changes in ARCH models[END_REF] in the specific case of ARCH(∞) or Aue et al. [START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF] for testing breaks in covariance. Kulperger and Yu [START_REF] Kulperger | High moment partial sum processes of residuals in GARCH models and their applications[END_REF] studied the high moment partial sum process based on residuals and applied it to residual CUSUM test in GARCH model. Horváth et al. [START_REF] Horváth | Ratio tests for change point detection[END_REF] suggested to compute the ratio of the CUSUM functionals instead of the differences for testing change in the mean of a time series. Berkes et al. [START_REF] Berkes | Testing for parameter constancy in GARCH(p; q) models[END_REF] used a test based on approximate likelihood scores for testing parameter constancy in GARCH(p,q) models. These procedures are mostly developed in a parametric framework and their asymptotic powers are unknown. The present work is a new contribution to the challenging problem of test for change detection.

In this paper, we consider a general class M T (M, f ) of causal (non-anticipative) time series. Let M, f : IR I N → IR be measurable functions, (ξ t ) t∈Z be a sequence of centered independent and identically distributed (iid) random variables called the innovations and satisfying var(ξ 0 ) = σ 2 and Θ a compact subset of IR d . Let T ⊂ Z, and for any θ ∈ Θ, define Class M T (M θ , f θ ): The process X = (X t ) t∈Z belongs to M T (M θ , f θ ) if it satisfies the relation:

X t+1 = M θ ( (X t-i ) i∈I N ) ξ t + f θ ( (X t-i ) i∈I N ) for all t ∈ T . ( 1
)
The existence and properties of this general class of affine processes were studied in Bardet and Wintenberger [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF]. Numerous classical time series are included in M Z (M, f ): for instance AR(∞), ARCH(∞), TARCH(∞), ARMA-GARCH or bilinear processes. Now, assume that a trajectory (X 1 , • • • , X n ) of X = (X t ) t∈Z is observed and consider the following hypothesis:

H 0 : there exists θ 0 ∈ Θ such that (X 1 , • • • , X n ) belongs to the class M {1,••• ,n} (M θ0 , f θ0 ) ;

H 1 : there exist K ≥ 2, θ 1 , • • • , θ K ∈ Θ such that (X 1 , • • • , X n ) belongs to K ∩ j=1 M T n j (M θj , f θj ) where T n j = {t j-1 + 1, t j-1 + 2, • • • , t j } with 0 = t 0 < t 1 < • • • < t K-1 < t K = n .
Thus, it is easy to see that under H 1 the property of stationary is lost after the first change. This is not the case in many existing works (for instance Kouamo et al. [START_REF] Kouamo | Testing for homogeneity of variance in the wavelet domain[END_REF] ) where the stationarity or the K-th order stationarity after the change is an essential assumption.

In this paper we study a new test for change detection (see Bardet et al. [3] for the procedure of the estimation of the instants of change). We consider a semi-parametric test statistic based on the QLME which is a modification of the statistic introduced by Lee et al. [START_REF] Lee | The Cusum Test for Parameter Change in Time Series Models[END_REF]

. For k, k ′ ∈ {2, • • • , n -1} (with k ≤ k ′ ) let θ n (X k , • • • , X k ′ ) be the QLME of the parameter computed on {k, • • • , k ′ }. The basic idea of our procedure is that : under H 0 , θ n (X 1 , • • • , X k ) and θ n (X k+1 , • • • , X n ) are close to θ n (X 1 , • • • , X n ) and the distances ∥ θ n (X 1 , • • • , X k ) -θ n (X 1 , • • • , X n )∥ and ∥ θ n (X k+1 , • • • , X n ) -θ n (X 1 , • • • , X n )∥ are not too large. Therefore,
we show that the test statistic is finite under the null hypothesis and diverges to infinity under the alternative of one change. Simulation results compared to some other procedures show that our procedure is more powerful. In Section 2 we present assumptions, some examples and construct the test statistic. In Section 3 we give some asymptotic results. The empirical studies of AR(1), ARCH(1) and GARCH [START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF][START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF] are detailed in Section 4 and the proofs of the main results are presented in Section 5.

Assumptions and test statistics 2.1 Assumptions on the class of models M

Z (f θ , M θ )
Let θ ∈ IR d and M θ and f θ be numerical functions such that for all

(x i ) i∈I N ∈ IR I N , M θ ( (x i ) i∈I N ) ̸ = 0 and f θ ( (x i ) i∈I N )
∈ IR. We will use the following norms:

1. ∥ • ∥ applied to a vector denotes the Euclidean norm of the vector;

2. for any compact set Θ ⊆ IR d and for any g : Θ -→ IR d ′ , ∥g∥ Θ = sup θ∈Θ (∥g(θ)∥).

Let Ψ θ = f θ , M θ and i = 0, 1, 2, then for any compact set Θ ⊆ IR d , define

Assumption A i (Ψ θ , Θ): Assume that ∥∂ i Ψ θ (0)/∂θ i ∥ Θ < ∞
and there exists a sequence of non-negative real number (α

(k) i (Ψ θ , Θ)) i≥1 such that ∞ ∑ k=1 α (i) k (Ψ θ , Θ) < ∞ satisfying ∂ i Ψ θ (x) ∂θ i - ∂ i Ψ θ (y) ∂θ i Θ ≤ ∞ ∑ k=1 α (i) k (Ψ θ , Θ)|x k -y k | for all x, y ∈ IR I N .
In the sequel we refer to the particular case called "ARCH-type process" if f θ = 0 and if the following assumption holds with h θ := M 2 θ :

Assumption A i (h θ , Θ): Assume that ∥∂ i h θ (0)/∂θ i ∥ Θ < ∞
and there exists a sequence of non-negative real number (α

(k) i (h θ , Θ)) i≥1 such as ∞ ∑ k=1 α (i) k (h θ , Θ) < ∞ satisfying ∂ i h θ (x) ∂θ i - ∂ i h θ (y) ∂θ i Θ ≤ ∞ ∑ k=1 α (i) k (h θ , Θ)|x 2 k -y 2 k | for all x, y ∈ IR I N .
Then define the set:

Θ(r) := {θ ∈ Θ, A 0 (f θ , {θ}) and A 0 (M θ , {θ}) hold with ∑ k≥1 α (0) k (f θ , θ) + (E |ξ 0 | r ) 1/r ∑ k≥1 α (0) k (M θ , θ) < 1} ∪ {θ ∈ Θ, f θ = 0 and A 0 (h θ , {θ}) hold with (E |ξ 0 | r ) 2/r ∑ k≥1 α (0) k (h θ , θ) < 1}.
The Lipschitz-type hypothesis A i (Ψ θ , Θ) are classical when studying the existence of solutions of the general model. If θ ∈ Θ(r) the existence of a unique causal, stationary and ergodic solution

X = (X t ) t∈Z ∈ M Z (f θ , M θ )
is assured (see [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF]). The subset Θ(r) is defined as a reunion to consider accurately general causal models and ARCH-type models simultaneously.

The following assumptions are needed to study QLME property. Assumption D(Θ): ∃h > 0 such that inf

θ∈Θ (|h θ (x)|) ≥ h for all x ∈ IR I N . Assumption Id(Θ): For all θ, θ ′ ∈ Θ 2 , ( f θ (X 0 , X -1 , • • • ) = f θ ′ (X 0 , X -1 , • • • ) and h θ (X 0 , X -1 , • • • ) = h θ ′ (X 0 , X -1 , • • • ) a.s. ) ⇒ θ = θ ′ .
Assumption Var(Θ): For all θ ∈ Θ, one of the families

( ∂f θ ∂θ i (X 0 , X -1 , • • • ) ) 1≤i≤d or ( ∂h θ ∂θ i (X 0 , X -1 , • • • ) ) 1≤i≤d is a.s. linearly independent.
As in [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF], we will make the convention that if A i (M θ , Θ) holds then α

(i) ℓ (h θ , Θ) = 0 and if A i (h θ , Θ) holds then α (i) ℓ (M θ , Θ) = 0. Denote : Assumption K(f θ , M θ , Θ) : for i= 0, 1, 2, A i (f θ , Θ) and A i (M θ , Θ) (or A i (h θ , Θ)) hold and there exists l > 2 such that α (i) j (f θ , Θ) + α (i) j (M θ , Θ) + α (i) j (h θ , Θ) = O(j -l ), for i= 0, 1.
Throughout the sequel, we will assume that the functions θ → M θ and θ → f θ are twice continuously differentiable on Θ.

Examples

1. AR(∞) models.

Consider the AR(∞) process defined by :

X t = ∑ k≥1 ϕ k (θ * 0 )X t-k + ξ t , t ∈ Z with θ * 0 ∈ Θ, where Θ is a compact subset of IR d such that ∑ k≥1 ∥ϕ k (θ)∥ Θ < 1. The process belongs to the class M Z (M θ * 0 , f θ * 0 ) where f θ (x 1 , • • • ) = ∑ k≥1 ϕ k (θ)
x k and M θ ≡ 1 for all θ ∈ Θ. Then Assumptions D(Θ) and A 0 (f θ , Θ) hold with h = 1 and α

(0) k (f θ , Θ) = ∥ϕ k (θ)∥ Θ . If there exists ℓ > 2 and ϕ k twice differentiable such as ∥ϕ k (θ)∥ Θ = ∥ϕ ′ k (θ)∥ Θ = ∥ϕ ′′ k (θ)∥ Θ = O(k -ℓ
), then Assumptions K(f θ , M θ , Θ) holds. Moreover, if ξ 0 is a nondegenerate random variable, Id(Θ) and Var(Θ) hold. For any r ≥ 1 such

that E |ξ 0 | r < ∞, Θ(r) = Θ.
2. GARCH(p,q) models.

Consider the GARCH(p,q) process defined by :

X t = σ t ξ t , σ 2 t = α * 0 + q ∑ k=1 α * k X 2 t-k + p ∑ k=1 β * k σ 2 t-k , t ∈ Z with E (ξ 2 0 ) = 1 and θ * 0 := (α * 0 , • • • , α * q , β * 1 , • • • , β * p ) ∈ Θ where Θ is a compact subset of ]0, ∞[×[0, ∞[ p+q such that ∑ q k=1 α k + ∑ p k=1 β k < 1 for all θ ∈ Θ.
Then there exists (see Bollerslev [START_REF] Bollerslev | Generalized autoregressive conditional heteroskedasticity[END_REF] or Nelson and Cao [START_REF] Nelson | Inequality Constraints in the Univariate GARCH Model[END_REF]) a nonnegative sequence (

ψ k (θ * 0 )) k≥0 such that σ 2 t = ψ 0 (θ * 0 ) + ∑ k≥1 ψ k (θ * 0 )X 2 t-k with ψ 0 (θ * 0 ) = α * 0 /(1 - ∑ p k=1 β * k ). This process belongs to a class M Z (M θ * 0 , f θ * 0 ) where M θ (x 1 , • • • ) = √ ψ 0 (θ) + ∑ k≥1 ψ k (θ)x k and f θ ≡ 0 ∀θ ∈ Θ. Assumptions D(Θ) holds with h = inf θ∈Θ (α 0 ). If there exists 0 < ρ 0 < 1 such that for any θ ∈ Θ, ∑ q k=1 α k + ∑ p k=1 β k ≤ ρ 0 then the sequences (∥ψ k (θ)∥ Θ ) k≥1 , (∥ψ ′ k (θ)∥ Θ )
Θ(r) = { θ ∈ Θ ; (E |ξ 0 | r ) 2/r q ∑ k=1 α k + p ∑ k=1 β k < 1 } .

Test statistics

Assume that a trajectory (X

1 , • • • , X n ) is observed. It is clear that if (X 1 , • • • , X n ) ∈ M {1,••• ,n} (M θ , f θ ), then
for T ⊂ {1, • • • , n}, the conditional quasi-(log)likelihood computed on T is given by :

L n (T, θ) := - 1 2 and h t θ = ( M t θ ) 2 . For T ⊂ {1, • • • , n}, define the estimator θ n (T ) := argmax θ∈Θ ( L n (T, θ)). Moreover, for 1 ≤ k ≤ n, denote T k = {1, • • • , k} and T k = {k + 1, • • • , n}. Now, define G n (T ) := 1 Card(T ) ∑ t∈T ( ∂ q t ( θ n (T )) ∂θ )( ∂ q t ( θ n (T )) ∂θ ) ′ and F n (T ) := - 2 Card(T ) ( ∂ 2 L n (T, θ n (T )) ∂θ∂θ ′ ) . For k = 1, • • • , n -1, denote : Σ n,k := k n F n (T k ) G n (T k ) -1 F n (T k )1 det( Gn(T k ))̸ =0 + n -k n F n (T k ) G n (T k ) -1 F n (T k )1 det( Gn(T k ))̸ =0 . Let (v n ) n∈I N be a sequence satisfying v n → ∞ and v n /n → 0 (as n → ∞). Denote Π n = [v n , n -v n ] ∩ IN and
define the statistics:

Q (1) n := max k∈Πn Q (1) n,k
where

Q (1) n,k := k 2 n ( θ n (T k ) -θ n (T n ) ) ′ Σ n,k ( θ n (T k ) -θ n (T n ) ) ; Q (2) n := max k∈Πn Q (2) n,k
where

Q (2) n,k := (n -k) 2 n ( θ n (T k ) -θ n (T n ) ) ′ Σ n,k ( θ n (T k ) -θ n (T n ) ) ; Q n := max ( Q (1) n , Q (2) n
) which is the test statistic.

Remark 2.1 Note that, the choice of (v n ) is crucial in practice. We evaluated the procedure with

v n = [log n], [(log n) 2 ], [(log n) 3 ] and recommend to use v n = [(log n) 2 ] for linear model and v n = [(log n) 5/2 ] for GARCH-type model.
Lee and Song [START_REF] Lee | Test for parameter change in ARMA models with GARCH innovations[END_REF] constructed a test for detecting changes in parameters of ARMA-GARCH models. Their test statistic uses a matrix Σ n which depends on the estimator θ n (T n ). Under the null hypothesis (the parameter

θ 0 does not change), Σ n is a consistent estimator of F G -1 F where G = E [(∂q 0 (θ 0 )/∂θ)(∂q 0 (θ 0 )/∂θ) ′ ] and F = E [∂ 2 q 0 (θ 0 )/∂θ∂θ ′ ].
Under the alternative, the model depends on several parameters and θ n (T n ) may not be a consistent estimator of one of them. Therefore, the convergence of the matrix Σ n is not assured. Thus, the asymptotic behavior of the test statistic may be very difficult to study. To solve this problem, we introduce the family of matrices { Σ n,k , k ∈ Π n }. It is easy to see that under the null hypothesis, any sequence ( Σ n,kn ) n>1,kn∈Πn is consistent. We show (see proof of Theorem 3.2) that under the local alternative where there is one change in the model, there exists a sequence ( Σ n,k * n ) n>1,k * n ∈Πn which converges.

3 Asymptotic results

Asymptotic under the null hypothesis

Theorem 3.1 Assume D(Θ), Id(Θ), Var and K(f θ , M θ , Θ). Under the null hypothesis H 0 , if θ 0 ∈ • Θ(4), then for j = 1, 2, Q (j) n D -→ n→∞ sup 0≤τ ≤1 ∥W d (τ )∥ 2
where W d is a d-dimensional Brownian bridge.

For any α ∈ (0, 1), let C α denote the (1 -α/2)-quantile of the distribution of sup

0≤τ ≤1 ∥W d (τ )∥ 2 .
Then, the following corollary is a direct application of Theorem 3.1. n,k are all below the red line which represents the limit of the critical region. Figure 1 c-) andd

Corollary 3.1 Under assumptions of Theorem 3.1 :

∀α ∈ (0, 1) lim sup n→∞ P ( Q n > C α ) ≤ α.
-) show that Q (1) n,k and Q (2)
n,k are larger and increase around the point where the change occurs.

As it can be observed on the Figure 1 and Figure 2 , the statistics Q

(1)

n and Q (1)
n are not clearly equal. Figure 2 shows the typical example for ARCH [START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF] with one change where

Q (1) n < C α and Q (2)
n > C α . In general, we don't know if under the alternative hypothesis each of statistics

Q (1) n and Q (2)
n take large values. But, under the local alternative of one change, the maximum of these two statistics diverges to infinity (see Theorem 3.2). This is the reason why we define the critical region as {max( Q

(1) n , Q (2) n ) > C α }.

The asymptotic under a local alternative

In this subsection, we consider a local alternative that there is one change in the model. More precisely, define

H (loc) 1 : there exist τ * ∈ (0, 1) and θ * 1 , θ * 2 ∈ Θ with θ * 1 ̸ = θ * 2 such that X 1 , • • • X [nτ * ] ∈ M T [nτ * ] (M θ * 1 , f θ * 1 ) and X [nτ * ]+1 , • • • , X n ∈ M T [nτ * ] (M θ * 2 , f θ * 2 ).

Theorem 3.2 Assume D(Θ), Id(Θ), Var and K(f

θ , M θ , Θ). Under H (loc) 1 , if θ * 1 , θ * 2 ∈ • Θ(4), then Q n a.s.
-→ n→∞ ∞.

Remark 3.2 1-) Theorem 3.2 shows that the test with the local alternative H (loc) 1

is consistent in power. 2-) This procedure can also be used to test multiple changes using ICSS type algorithm developed by Inclán and Tiao [START_REF] Inclan | Use of cumulative sums of squares for retrospective detection of changes of variance[END_REF].

a-) Q n,k (1

Some simulations results

In this section, we evaluate the performance of the procedure through empirical study. We compare our results with those obtained by Kouamo et al. [START_REF] Kouamo | Testing for homogeneity of variance in the wavelet domain[END_REF], Lee and Na [START_REF] Lee | Test for parameter change in stochastic processes based on conditional least-squares estimator[END_REF] and the results obtained from the residual CUSUM test by using the statistics defined by Kulperger and Yu [START_REF] Kulperger | High moment partial sum processes of residuals in GARCH models and their applications[END_REF]. For a sample size n, Q n is computed with v n = [(ln n) 2 ] for AR model and v n = [(ln n) 5/2 ] for GARCH model and is compared to the critical value of the test. In the following models, (ξ t ) t∈Z are iid standard Gaussian random variables.

Test for parameter change in AR(p) models

Let us consider a AR(p) process :

X t = p ∑ k=1 ϕ * k X t-k + ξ t with p ∈ IN * .
The true parameter of the model is de-

noted by θ * 0 = (ϕ * 1 , • • • , ϕ * p ) ∈ Θ where Θ = {θ = (ϕ 1 , • • • , ϕ p ) ∈ IR p / p ∑ i=1 |ϕ i | < 1}. Since M θ ≡ 1, Θ(r) = Θ for any r ≥ 1. Assume (X 1 , • • • , X n ) is observed, we have for any θ ∈ Θ, q t (θ) = ( X t - p ∑ k=1 ϕ k X t-k ) 2 , ∂ q t (θ) ∂θ = -2 ( X t - p ∑ k=1 ϕ k X t-k ) • (X t-1 , X t-2 , • • • , X t-p ) and for 1 ≤ i, j ≤ n ∂ 2 q t (θ) ∂ϕ i ∂ϕ j = 2X t-i X t-j .
We consider a AR(1) process with one parameter. At level α = 0.05, the critical value is C α ≃ 2.20. For n = 1024, 2048, 4096 ; we generate a sample (X 1 , • • • , X n ) in the following situations : (i) there is no change and the parameter of the model is θ 0 = 0.9 and (ii) there is one change and the parameter θ 0 = 0.9 changes to θ 1 = 0.

Test for parameter change in GARCH(1,1) models

Consider the GARCH(1,1) model defined by:

∀t ∈ Z, X t = σ t ξ t with σ 2 t = α * 0 + α * 1 X 2 t-1 + β * 1 σ 2 t-1 with θ * 0 = (α * 0 , α * 1 , β * 1 ) ∈ Θ ⊂]0, ∞[×[0, ∞[ 2 and satisfying α * 1 + β * 1 < 1. The ARCH(∞) representation is σ 2 t = α * 0 /(1 -β * 1 ) + α * 1 ∑ k≥1 (β * 1 ) k-1 X 2 t-k . For any θ ∈ Θ and t = 2, • • • , n , we have h t θ = α 0 /(1 -β 1 ) + α 1 X 2 t-1 + α 1 t ∑ k=2 β k-1 1 X 2 t-k and q t (θ) = X 2 t / h t θ + log( h t θ ).
Therefore, it follows that ∂ q t (θ) ∂θ = 1

h t θ ( 1 - X 2 t h t θ )( ∂ h t θ ∂α 0 , ∂ h t θ ∂α 1 , ∂ h t θ ∂β 1 ) with ∂ h t θ /∂α 1 = X 2 t-1 + t ∑ k=2 β k-1 1 X 2 t-k ∂ h t θ /∂α 0 = 1/(1 -β 1 ), and ∂ h t θ /∂β 1 = α 0 /(1 -β 1 ) 2 + α 1 X 2 t-2 + α 1 t ∑ k=3 (k -1)β k-2 1 X 2 t-k . Let θ = (α 0 , α 1 , β 1 ) = (θ 1 , θ 2 , θ 3 ) ∈ Θ, for 1 ≤ i, j ≤ 3, we have ∂ 2 q t (θ) ∂θ i ∂θ j = 1 ( h t θ ) 2 ( 2X 2 t h t θ -1 ) ∂ h t θ ∂θ i ∂ h t θ ∂θ j + 1 h t θ ( 1 - X 2 t h t θ ) ∂ 2 h t θ ∂θ i ∂θ j with ∂ 2 h t θ /∂α 2 0 = 0, ∂ 2 h t θ /∂α 0 ∂α 1 = 0, ∂ 2 h t θ /∂α 2 1 = 0, ∂ 2 h t θ /∂α 1 ∂β 1 = X 2 t-2 + t ∑ k=3 (k -1)β k-2 1 X 2 t-k , ∂ 2 h t θ /∂α 0 ∂β 1 = 1/(1 -β 1 ) 2 and ∂ h t θ /∂β 2 1 = 2α 0 /(1 -β 1 ) 3 + 2α 1 X 2 t-3 + α 1 t ∑ k=4 (k -1)(k -2)β k-3 1 X 2 t-k .
1. Case of ARCH(1). Assume β 1 = 0 and θ = (α 0 , α 1 ). At level α = 0.05, the critical value is C α ≃ 3.02.

For n = 500, 800, 1000 ; we generate a sample (X 1 , • • • , X n ) in the following situations : (i) there is no change, the parameter of the model is θ 0 = (1, 0.3) and (ii) there is one change, the parameter θ 0 = (1, 0.3) changes to two different values of θ 1 = (0.5, 0.3) and θ 1 = (0. (2) statistic defined by Kulperger and Yu [START_REF] Kulperger | High moment partial sum processes of residuals in GARCH models and their applications[END_REF].

Table 2 and Table 3 show that the empirical level of the test decreases and the empirical power increases as n increases. For ARCH model, we can see that the empirical level is less than 0.05 when n = 800. It is not very surprising because the asymptotic size of the test is less than α = 0.05. This is not the case for GARCH model. It is explained by the fact that the application of the procedure to GARCH model requires ARCH(∞) representation. Thus, the information contained in all the past of the process is not used because it is not observed. In Table 2, figures in brackets are the results obtained by Lee and Na [START_REF] Lee | Test for parameter change in stochastic processes based on conditional least-squares estimator[END_REF] using the CUSUM test based on conditional least-squares estimator. In Table 3, figures in brackets are the results of the residual CUSUM test that we obtained by using CU SU M (2) statistic studied by Kulperger and Yu [START_REF] Kulperger | High moment partial sum processes of residuals in GARCH models and their applications[END_REF]. Once again, our test statistic Q n provides best results.

Proofs of the main results

Let (ψ n ) n and (r n ) n be sequences of random variables. Throughout this section, we use the notation ψ n = o P (r n ) to mean : for all ε > 0, P (|ψ n | ≥ ε|r n |) → 0 as n → ∞. Write ψ n = O P (r n ) to mean : for all ε > 0, there exists C > 0 such that P (|ψ n | ≥ C|r n |) ≤ ε for n large enough.

Some preliminary results

First, let us prove useful technical lemmas.

Under the null hypothesis H

0 the observations (X 1 , • • • , X n ) belong in the class M {1,••• ,n} (M θ0 , f θ0 ), de- fine the matrix G := E [ ∂q 0 (θ 0 ) ∂θ ∂q 0 (θ 0 ) ∂θ ′]
( where ′ denotes the transpose) and

F := E [ ∂ 2 q 0 (θ 0 ) ∂θ∂θ ′ ] .
Under assumption Var, F is a non-singular matrix (see [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF]). Proof. It is clear that G is symmetric. Moreover, for 1 ≤ i ≤ d, we have :

∂q 0 (θ 0 ) ∂θ i = -2 ξ 0 √ h 0 θ0 ∂f 0 θ0 ∂θ i - ξ 2 0 h 0 θ0 ∂h 0 θ0 ∂θ i + 1 h 0 θ0 ∂h 0 θ0 ∂θ i . Thus, using independence of ξ 0 and X -1 , X -2 , • • • we obtain : E [ ∂q 0 (θ 0 ) ∂θ ′ ∂q 0 (θ 0 ) ∂θ ] = 4E [ 1 h 0 θ0 ∂f 0 θ0 ∂θ ′ ∂f 0 θ0 ∂θ ] + E ( (ξ 2 0 -1) 2 ) E [ 1 (h 0 θ0 ) 2 ∂h 0 θ0 ∂θ ′ ∂h 0 θ0 ∂θ ] . ( 2
)
Since E ξ 2 0 = 1, it is easy to see that E

( (ξ 2 0 -1) 2 ) > 0.
Under Var, one of the two matrix of the right-hand side of relation ( 2) is positive definite and the other is semi-positive definite. Thus, G is positive definite.

Now, recall that

F := E [ ∂ 2 q 0 (θ 0 ) ∂θ∂θ ′ ] . Let T ⊂ {1, • • • , n}. For any θ ∈ Θ and i = 1, • • • , d, by Taylor expansion of ∂L n (T, θ 0 )/∂θ i , there exist θ n,i ∈ [θ 0 , θ] such that: ∂L n (T, θ) ∂θ i = ∂L n (T, θ 0 ) ∂θ i + ∂ 2 L n (T, θ n,i ) ∂θ∂θ i (θ -θ 0 ) (3)
where

[a, b] = {λa + (1 -λ)b ; λ ∈ [0, 1]}. Denote F n (T, θ) = -2 ( 1 card(T ) ∂ 2 L n (T, θ n,i ) ∂θ∂θ i ) 1≤i≤d . Then, (3) implies, Card(T )F n (T, θ)(θ -θ 0 ) = -2 ( ∂L n (T, θ) ∂θ - ∂L n (T, θ 0 ) ∂θ ) . (4)
Similarly, for any θ ∈ Θ we can find a matrix F n (T, θ) such that

Card(T ) F n (T, θ)(θ -θ 0 ) = -2 ( ∂ L n (T, θ) ∂θ - ∂ L n (T, θ 0 ) ∂θ ) . (5)
With θ = θ n (T ) in ( 5) and using the fact that

∂ L n (T, θ n (T ))/∂θ = 0 (because θ n (T ) is a local extremum of L n (T, •)), it comes Card(T ) F n (T, θ n (T ))( θ n (T ) -θ 0 ) = 2 ∂ L n (T, θ 0 ) ∂θ . ( 6
) Remark 5.1 If Card(T ) -→ n→∞ ∞ and θ = θ(n) -→ n→∞ θ 0 , then F n (T, θ) a.s. -→ n→∞ F and F n (T, θ) a.s.
-→ n→∞ F (see [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF] and [START_REF] Bardet | Detecting multiple change-points in general causal time series using penalized quasi-likelihood[END_REF]). In particular, if

Card(T ) -→ n→∞ ∞ , then F n (T, θ n (T )) a.s. -→ n→∞ F and F n (T, θ n (T )) a.s.
-→ n→∞ F.

Lemma 5.2 Under assumptions of Theorem 3.1

1 √ n max k∈Πn k ( F n (T k , θ n (T k )) -F ) ( θ n (T k ) -θ 0 ) = o P (1).

Proof.

For k ∈ Π n , we know that √ k( θ n (T k )) -θ 0 ) converges in distribution to the Gaussian law as n -→ ∞ (see Theorem 2 of [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF]). Therefore, max

k∈Πn √ k( θ n (T k ) -θ 0 ) = O P (1). Remark 5.1 implies that max k∈Πn F n (T k , θ n (T k )) -F = o(1) a.s. Thus 1 √ n max k∈Πn k ( F n (T k , θ n (T k )) -F ) ( θ n (T k ) -θ 0 ) ≤ max k∈Πn F n (T k , θ n (T k )) -F × max k∈Πn √ k( θ n (T k ) -θ 0 ) = o(1)O P (1) a.s. = o P (1).
Under assumptions of Theorem 3.1, the matrix

G is invertible. Denote Σ = F G -1 F Q (1) n := max k∈Πn Q (1) n,k
where

Q (1) n,k := k 2 n ( θ n (T k ) -θ n (T n ) ) ′ Σ ( θ n (T k ) -θ n (T n ) ) and
Q (2) n := max k∈Πn Q (2) n,k
where

Q (2) n,k := (n -k) 2 n ( θ n (T k ) -θ n (T n ) ) ′ Σ ( θ n (T k ) -θ n (T n ) ) . Lemma 5.3 Under assumptions of Theorem 3.1 max k∈Πn Q (j) n,k -Q (j) n,k = o P (1) for j = 1, 2.
Proof. The proof is provided for j = 1, proceed similarly for j = 2. For any k ∈ Π n , we have

Q (1) n,k -Q (1) n,k ≤ k 2 n ∥ θ n (T k ) -θ n (T n )∥ 2 ∥ Σ n,k -Σ∥ ≤ 2 k 2 n ( ∥ θ n (T k ) -θ 0 ∥ 2 + ∥ θ n (T n ) -θ 0 ∥ 2 ) ∥ Σ n,k -Σ∥ ≤ 2 ( ∥ √ k( θ n (T k ) -θ 0 )∥ 2 + ∥ √ n( θ n (T n ) -θ 0 )∥ 2 ) ∥ Σ n,k -Σ∥. ( 7
) Since k ∈ Π n , k, n-k -→ ∞ as n -→ ∞. Therefore, √ k( θ n (T k )-θ 0 ) = O P (1) as n -→ ∞, √ n( θ n (T n )-θ 0 ) = O P (1), F n (T k ) a.s. -→ n→∞ F , F n (T k ) a.s. -→ n→∞ F , G n (T k ) a.s. -→ n→∞ G and G n (T k ) a.s. -→ n→∞ G which is invertible. Thus, for n large enough, G n (T k ) and G n (T k ) are invertible. It follows that as n -→ ∞, ∥ Σ n,k -Σ∥ = k n F n (T k ) G n (T k ) -1 F n (T k ) + n -k n F n (T k ) G n (T k ) -1 F n (T k ) -F G -1 F = k n ( k n F n (T k ) G n (T k ) -1 F n (T k ) -F G -1 F ) + n -k n ( F n (T k ) G n (T k ) -1 F n (T k ) -F G -1 F ) ≤ ∥ F n (T k ) G n (T k ) -1 F n (T k ) -F G -1 F ∥ + ∥ F n (T k ) G n (T k ) -1 F n (T k ) -F G -1 F ∥ = o(1) a.s.
Therefore, [START_REF] Billingsley | Convergence of Probability Measures[END_REF]

implies max k∈Πn Q (1) n,k -Q (1)
n,k = o P (1).

Lemma 5.4 Under assumptions of Theorem 3.1

-2 √ n ∂L n (T [nτ ] , θ 0 ) ∂θ D -→ W G (τ ) in D([0, 1], IR d )
where W G is a d-dimensional Gaussian process with zero mean and covariance matrix min(τ, s)G.

Proof. Recall that -2 ∂L n (T [nτ ] , θ 0 ) ∂θ = [nτ ] ∑ t=1 ∂q t (θ 0 ) ∂θ . Denote F t = σ(X t-1 , • • • ).
Since X is stationary and ergodic, it is the same for the process ( ∂q t (θ 0 ) ∂θ ) t∈Z . Moreover, ( ∂q t (θ 0 ) ∂θ , F t ) is a square integrable martingale difference process (see [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF]) with covariance matrix G. Then, the result follow by using Theorem 23.1 Billingsley (1968) (see [START_REF] Billingsley | Convergence of Probability Measures[END_REF] page 206). Lemma 5.5 Under assumptions of Theorem 3.1

-2 √ n G -1/2 ( ∂L n (T [nτ ] , θ 0 ) ∂θ - [nτ ] n ∂L n (T n , θ 0 ) ∂θ ) D -→ W d (τ ) in D([0, 1], IR d )
where W d is a d-dimensional Brownian bridge.

Proof. By Lemma 5.4, it comes

-2 √ n ( ∂L n (T [nτ ] , θ 0 ) ∂θ - [nτ ] n ∂L n (T n , θ 0 ) ∂θ ) D -→ W G (τ ) -τ W G (1) in D([0, 1], IR d ).
Since the covariance matrix of the process {W G (τ ) -τ W G (1), 0 ≤ τ ≤ 1} is (min(τ, s) -τ s)G, the covariance matrix of the process {G -1/2 (W G (τ )-τ W G (1)), 0 ≤ τ ≤ 1} is (min(τ, s)-τ s)I d (where I d is the d-dimensional identity matrix). Therefore, the process is equal (in distribution) to d-dimensional Brownian bridge and the result follows.

Lemma 5.6 Under assumptions of Theorem 3.1

-2 √ n G -1/2 ∂ L n (T [nτ ] , θ n (T n )) ∂θ D -→ W d (τ ) in D([0, 1], IR d ).
Proof. From [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF], we have 1

√ n ∂L n (T n , •) ∂θ - ∂ L n (T n , •) ∂θ Θ = o P (1). This implies, 1 √ n max k∈Πn ∂L n (T k , •) ∂θ - ∂ L n (T k , •) ∂θ Θ = o P (1). (8)
Let k ∈ Π n . Applying (4) with T = T k and θ = θ n (T n ), we have

kF n (T k , θ n (T n ))( θ n (T n ) -θ 0 ) = -2 ( ∂L n (T k , θ n (T n )) ∂θ - ∂L n (T k , θ 0 ) ∂θ ) .
By plugging it in (8), we have

1 √ n max k∈Πn ∂ L n (T k , θ n (T n )) ∂θ - ∂L n (T k , θ 0 ) ∂θ + 1 2 kF n (T k , θ n (T n ))( θ n (T n ) -θ 0 ) = o P (1). (9)
But, by Remark 5.1, it comes that

1 √ n max k∈Πn k ( F n (T k , θ n (T n )) -F n (T n , θ n (T n )) ) ( θ n (T n ) -θ 0 ) ≤ 1 √ n max k∈Πn k ( F n (T k , θ n (T n )) -F n (T n , θ n (T n )) ) × ∥ √ n( θ n (T n ) -θ 0 )∥ = o(1)O P (1) a.s.
= o P (1).

Thus, (9) becomes

1 √ n max k∈Πn ∂ L n (T k , θ n (T n )) ∂θ - ∂L n (T k , θ 0 ) ∂θ + 1 2 kF n (T n , θ n (T n ))( θ n (T n ) -θ 0 ) = o P (1). (10)
Applying ( 4) with T = T n , θ = θ n (T n ), and using (1/ √ n)(∂L n (T n , θ n (T n ))/∂θ) = o P (1) (see [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF]), it follows

F n (T n , θ n (T n ))( θ n (T n ) -θ 0 ) = 2 n ∂L n (T n , θ 0 ) ∂θ + o P ( 1 √ n ). (11)
Therefore, [START_REF] Francq | Maximum likelihood estimation of pure garch and arma-garch processes[END_REF] becomes

1 √ n max k∈Πn ∂ L n (T k , θ n (T n )) ∂θ - ∂L n (T k , θ 0 ) ∂θ + k n ∂L n (T n , θ 0 ) ∂θ = o P (1). ( 12
)
Now, let 0 < τ < 1, for large value of n, we have [τ n] ∈ Π n ; write

-2 √ n G -1/2 ∂ L n (T [nτ ] , θ n (T n )) ∂θ = -2 √ n G -1/2 [ ∂ L n (T [nτ ] , θ n (T n )) ∂θ - ( ∂L n (T [nτ ] , θ 0 ) ∂θ - [nτ ] n ∂L n (T n , θ 0 ) ∂θ ) + ( ∂L n (T [nτ ] , θ 0 ) ∂θ - [nτ ] n ∂L n (T n , θ 0 ) ∂θ ) ]
and the result follows by using ( 12) and Lemma 5.5.

Proof of Theorem 3.1 and Theorem 3.2

Proof of Theorem 3.1 .

We give the proof for j = 1, proceed similarly for j = 2. By Lemma 5.

∂L n (T k , θ 0 ) ∂θ - 1 2 kF ( θ n (T k ) -θ 0 ) = 1 √ n max k∈Πn ∂ L n (T k , θ 0 ) ∂θ - 1 2 kF ( θ n (T k ) -θ 0 ) + o P (1) = 1 √ n max k∈Πn 1 2 k F n (T k , θ n (T k ))( θ n (T n ) -θ 0 ) - 1 2 kF ( θ n (T k ) -θ 0 ) + o P (1) = 1 √ n max k∈Πn 1 2 k ( F n (T k , θ n (T k )) -F ) ( θ n (T n ) -θ 0 ) + o P (1) = o P (1). (13)
Using ( 12) and 13, we have

1 √ n max k∈Πn ∂L n (T k , θ n (T n )) ∂θ - 1 2 kF ( θ n (T k ) -θ n (T n )) = 1 √ n max k∈Πn ∂L n (T k , θ 0 ) ∂θ - k n ∂L n (T n , θ 0 ) ∂θ - 1 2 kF ( θ n (T k ) -θ n (T n )) + o P (1) = 1 √ n max k∈Πn 1 2 kF ( θ n (T k ) -θ 0 ) - k n ∂L n (T n , θ 0 ) ∂θ - 1 2 kF ( θ n (T k ) -θ n (T n )) + o P (1) = 1 √ n max k∈Πn 1 2 kF ( θ n (T n ) -θ 0 ) - k n ∂L n (T n , θ 0 ) ∂θ + o P (1) ≤ √ n 1 2 F ( θ n (T n ) -θ 0 ) - 1 n ∂L n (T n , θ 0 ) ∂θ + o P (1). ( 14
) Note that √ n(F -F n (T n , θ n (T n ))) ( θ n (T n ) -θ 0 ) ≤ F -F n (T n , θ n (T n )) √ n( θ n (T n ) -θ 0 )
= o(1)O P (1) a.s.

= o P [START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF].

By plugging it in [START_REF] Kierfer | K-sample analogues of the Kolmogorov-Smirnov and Cramér-v.Mises tests[END_REF] and applying (4) with T = T n and θ = θ n (T n ), we have

1 √ n max k∈Πn ∂L n (T k , θ n (T n )) ∂θ - 1 2 kF ( θ n (T k ) -θ n (T n )) ≤ √ n 1 2 F n (T n , θ n (T n ))( θ n (T n ) -θ 0 ) - 1 n ∂L n (T n , θ 0 ) ∂θ + o P (1). (15)
Therefore, using ( 11), ( 15) implies

1 √ n max k∈Πn ∂L n (T k , θ n (T n )) ∂θ - 1 2 kF ( θ n (T k ) -θ n (T n )) = o P (1). (16)
Now, let 0 < τ < 1, for large value of n, we have

[τ n] ∈ Π n ; write -2 √ n G -1/2 ∂ L n (T [nτ ] , θ n (T n )) ∂θ = - [nτ ] √ n G -1/2 F ( θ n (T [nτ ] ) -θ n (T n )) -2G -1/2 1 √ n [ ∂ L n (T [nτ ] , θ n (T n )) ∂θ - 1 2 [nτ ]F ( θ n (T [nτ ] ) -θ n (T n ))
] .

Therefore, using ( 16) we have

- [nτ ] √ n G -1/2 F ( θ n (T [nτ ] ) -θ n (T n )) = -2 √ n G -1/2 ∂ L n (T [nτ ] , θ n (T n )) ∂θ + o P (1)
and the result follows by using Lemma 5.6.

Proof of Theorem 3.2 .

Let τ * ∈ (0, 1) the true value of break. Denote k * = [nτ * ]. For n large enough , k * ∈ Π n . Therefore, we have

for j = 1, 2, Q (j) n = max k∈Πn Q (j) n,k ≥ Q (j)
n,k * . Thus, it follows that

Q n = max( Q (1) n , Q (2) n ) ≥ max( Q (1) n,k * , Q (2) n,k * ). ( 17
) Since θ * 1 , θ * 2 ∈ • Θ(4), it comes from [2] that the model M Z (M θ * 1 , f θ * 1 ) and M Z (M θ * 2 , f θ * 2 )
have a 4-order stationary solution which we denote (X t,j ) t∈Z for j = 1, 2.

For j = 1, 2 denote for any t ∈ Z, q t,j (θ) := (X t,j -f t,j θ ) 2 /(h t,j θ ) + log(h t,j θ ) with f t,j θ := f θ (X t-1,j , X t-2,j , . . .), h t,j θ := (M t,j θ ) 2 where M t,j θ := M θ (X t-1,j , X t-2,j , . . .). Also denote for j = 1, 2 F (j) = E [ ∂ 2 q 0,j (θ * j ) ∂θ∂θ ′ ] and G (j) = E [( ∂q 0,j (θ * j ) ∂θ )( ∂q 0,j (θ * j ) ∂θ

) ′ ]
.

For j = 1, 2, Lemma 5.1 implies that the matrix G (j) is symmetric positive definite and Corollary 5.1 of [START_REF] Bardet | Detecting multiple change-points in general causal time series using penalized quasi-likelihood[END_REF] implies G n (T k * ) a.s.

-→ n→∞ G (1) and G n (T k * ) a.s.

-→ n→∞ G (2) . Lemma 4 of [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF] implies F n (T k * ) a.s.

-→ n→∞ F (1) and

F n (T k * ) a.s.
-→ n→∞ F (2) . Therefore, it follows that

Σ n,k * := k * n F n (T k * ) G n (T k * ) -1 F n (T k * )1 det( Gn(T k * ))̸ =0 + n -k * n F n (T k * ) G n (T k * ) -1 F n (T k * )1 det( Gn(T k * ))̸ =0
a.s.

-→ n→∞ τ * F (1) (G (1) ) -1 F (1) + (1 -τ * )F (2) (G (2) ) -1 F (2) . [START_REF] Kulperger | High moment partial sum processes of residuals in GARCH models and their applications[END_REF] Denote Σ = τ * F (1) (G (1) ) -1 F (1) + (1 -τ * )F (2) (G (2) ) -1 F (2) . It is easy to see that Σ is a symmetric positive . It is easy to see that δ (j) > 0 for j = 1, 2.

Using [START_REF] Kulperger | High moment partial sum processes of residuals in GARCH models and their applications[END_REF], we have

δ (j) n a.s.
-→ n→∞ δ (j) for j = 1, 2. (

From [START_REF] Bardet | Asymptotic normality of the quasi-maximum likelihood estimator for multidimensional causal processes[END_REF] and [START_REF] Bardet | Detecting multiple change-points in general causal time series using penalized quasi-likelihood[END_REF] n . Therefore, (1) n ≃ n(τ * ) 2 δ (1) n .

Q (1) n,k * := (k * ) 2 n ( θ n (T k * ) -θ n (T n )) ′ Σ n,k * ( θ n (T k * ) -θ n (T n )) ≥ (k * ) 2 n δ
• else θ n (T n ) ∈ B c o (θ * 2 , ρ 2 ) and (

θ n (T k * ) -θ n (T n )) ′ Σ n,k * ( θ n (T k * ) -θ n (T n )) ≥ δ (2)
n . Therefore,

Q (2) n,k * = (n -k * ) 2 n ( θ n (T k * ) -θ n (T n )) ′ Σ n,k * ( θ n (T k * ) -θ n (T n ) ≥ (n -k * ) 2 n δ (2) n ≃ n(1 -τ * ) 2 δ (2) n .
In all cases, we have

Q n ≥ max( Q (1) n,k * , Q (2) n,k * ) ≥ min ( n(τ * ) 2 δ (1) n , n(1 -τ * ) 2 δ (2) n
) .

Thus the result follows by using [START_REF] Lee | The Cusum Test for Parameter Change in Time Series Models[END_REF].

Remark 3 . 1

 31 Quantile values of the distribution of sup 0≤τ ≤1∥W d (τ )∥ 2 are known (see for instance Kieffer[START_REF] Kierfer | K-sample analogues of the Kolmogorov-Smirnov and Cramér-v.Mises tests[END_REF] for d ∈ {1, • • • , 5} or Lee et al.[START_REF] Lee | The Cusum Test for Parameter Change in Time Series Models[END_REF] for d ∈ {1, • • • , 10}). Theorem 3.1 and Corollary 3.1 imply that a large value of Q n means there is a change in the model. At a nominal level α, the critical region of the test is ( Q n > C α ).

Figure 1

 1 Figure 1 is an illustration of the test procedure for AR(1) process. At a level α = 0.05, for d = 1, C α ≃ 2.20.

Figure 1 a

 1 Figure 1 a-) and b-) show that, the values of Q (1) n,k and Q (2)

Figure 1 :Figure 2 :

 12 Figure 1 : Typical realization of the statistics Q (1) n,k and Q (2) n,k for 1000 sample of AR(1) with v n = [log n]. a-) and b-) are the case of AR(1) where parameter ϕ 1 = 0.3 remains constant. c-) and d-) are the case of AR(1) with parameter ϕ 1 = 0.3 changing to 0.5 at k * = 400.

Lemma 5 . 1

 51 Assume the functions θ → M θ and θ → f θ are 2-times continuously differentiable on Θ. Under the null hypothesis D(Θ) and Var, G is a symmetric, positive definite matrix.

  definite matrix. For all ρ > 0 and θ ∈ Θ, denote B o (θ, ρ) (rep. B c (θ, ρ) ) the open (resp. closed) ball centered at θ of radius ρ in Θ. i.e.B o (θ, ρ) = {x ∈ Θ ; ∥θ -x∥ < ρ} and B c (θ, ρ) = {x ∈ Θ ; ∥θ -x∥ ≤ ρ}. For A ⊂ Θ, we denote A c = {x ∈ Θ ; x / ∈ A}. Since θ * 1 ̸ = θ * 2 and θ * 1 , θ * 2 ∈ • Θ(4) ⊂ • Θ, then there exist ρ 1 > 0 and ρ 2 > 0 such as B o (θ * 1 , ρ 1 ) ∩ B o (θ * 2 , ρ 2 ) = ∅. For all n ∈ IN , denote δ (j) n = inf x∈Bc(θ * j ,ρj /2); y∈B c o (θ * j ,ρj ) ( (x -y) ′ Σ n,k * (x -y) ) for j = 1, 2. Also denote δ (j) = inf x∈Bc(θ * j ,ρj /2); y∈B c o (θ * j ,ρj ) ( (x -y) ′ Σ(x -y) )

Table 1 :

 1 [START_REF] Berkes | GARCH processes: structure and estimation[END_REF] at n/2. The following table indicates the proportion of the number of rejections of the null hypothesis out of 100 repetitions. Empirical levels and powers at nominal level 0.05 of the test for parameter change in AR(1) model. The empirical levels are computed when θ 0 = 0.9 ; the empirical powers are computed when θ 0 changes to θ 1 = 0.5 at n/2. Figures in brackets are the results obtained by Kouamo et al.[START_REF] Kouamo | Testing for homogeneity of variance in the wavelet domain[END_REF] at the scale J=4 with KSM and CVM statistic in wavelet domain.

		n = 1024	n = 2048	n = 4096
	Empirical levels	0.080 (0.134 ; 0.092) 0.070 (0.100 ; 0.062) 0.050 (0.082 ; 0.040)
	Empirical powers when θ 1 = 0.5 0.980 (0.590 ; 0.530) 0.990 (0.720 ; 0.680) 0.990 (0.810 ; 0.790)

Table 1

 1 shows that the empirical level of the test decreases as n increases and equals to 0.05 when n = 4096. These levels are close to those obtained byKouamo et al. with CVM (Cramér-Von Mises) test statistic. The results obtained with our test statistic Q n are clearly more accurate.

Table 2 :

 2 Empirical levels and powers at nominal level 0.05 of the test for parameter change in ARCH(1) model. The empirical levels are computed when θ 0 = (1, 0.3) ; the empirical powers are computed when θ 0 changes to θ 1 at n/2. Figures in brackets are the results obtained by Lee and Na [20].2. Case of GARCH[START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF][START_REF] Aue | Break detection in the covariance structure of multivariate time series models[END_REF]. Now θ = (α 0 , α 1 , β 1 ). At level α = 0.05, the critical value is C α ≃ 3.47. For n = 500, 1000, 1500 ; we generate a sample (X 1 , • • • , X n ) in the following situations : (i) there is no change, the parameter of the model is θ The following table indicates the proportion of the number of rejections of the null hypothesis out of 500 repetitions.

		n = 500	n = 800	n = 1000
	Empirical levels	0.068 (0.088) 0.048 (0.080) 0.036 (0.074)
	Empirical powers when θ 1 = (0.5, 0.3) 0.948 (0.922) 0.972 (0.987) 0.998 (0.995)
	Empirical powers when θ 1 = (0.5, 0.6) 0.876 (0.498) 0.976 (0.589) 0.984 (0.606)
		n = 500	n = 1000	n = 1500
	Empirical levels	0.100 (0.030) 0.078 (0.032) 0.052 (0.042)
	Empirical powers when θ 1 = (0.7, 0.4, 0.1) 0.498 (0.334) 0.752 (0.658) 0.934 (0.848)
	Empirical powers when θ 1 = (1, 0.4, 0.3)	0.654 (0.404) 0.968 (0.772) 0.976 (0.922)

5, 0.6)

at n/2. The following table indicates the proportion of the number of rejections of the null hypothesis out of 500 repetitions. 0 = (1, 0.4, 0.1) and (ii) there is one change, the parameter θ 0 = (1, 0.4, 0.1) changes two different values of θ 1 = (0.7, 0.4, 0.1) and θ 1 = (1, 0.4, 0.3) at n/2.

Table 3 :

 3 Empirical

levels and powers at nominal level 0.05 of test the for parameter change in GARCH(1,1) model. The empirical levels are computed when θ 0 = (1, 0.4, 0.1) ; the empirical powers are computed when θ 0 changes to θ 1 at n/2. Figures in brackets are the results of the residual CUSUM test using CU SU M

  , we have θ n (T k

* ) a.s. -→ n→∞ θ * 1 and θ n (T k * ) a.s. -→ n→∞ θ * 2 . Therefore, for n large enough, θ n

(T k * ) ∈ B o (θ * 1 , ρ 1 /2) and θ n (T k * ) ∈ B o (θ * 2 , ρ 2 /2

). Thus, two situations may occur

• if θ n (T n ) ∈ B o (θ * 2 , ρ 2 ) i.e. θ n (T n ) ∈ B c o (θ * 1 , ρ 1 ) then ( θ n (T k * ) -θ n (T n )) ′ Σ n,k * ( θ n (T k * ) -θ n (T n )) ≥ δ (1)

Acknowledgements

The author thanks Jean-Marc Bardet and Olivier Wintenberger for many discussions which helped to improve this work.


Fabien Carmagnac
email: fabien.carmagnac@a2ia.com

Pierre Héroux

Éric Trupin

Distance Based Strategy for Supervised Document Image Classification

This paper deals with supervised document image classification. An original distance based strategy allows automatic feature selection. The computation of a distance between an image to be classified and a class representative (point of view) allows to estimate a membership function for all classes. The choice of the best point of view performs the feature selection. This idea is used by an algorithm which iteratively filters the list of candidate classes. The training phase is performed by computing the distances between every class. Each iteration of the classification algorithm computes the distance d between the image to be classified and the chosen representative. The classes whose distance with this point of view differs from d are deleted in the list of candidate classes. This strategy is implemented as a module of A2IA FieldReader to identify the class of the processed document. Experimental results are presented and compared with results given by a knn classifier.

Introduction

Since a few years, handwritten recognition systems have improved (automatic zip code, form field or cheque amount reader) leading to commercial applications. The good reading rates of such systems allow to process less constrained documents (eg. order forms, invoices). To validate the reading results on such semi-structured documents, it is necessary to associate a reading model to each document class. This reading model contains information about the fields of the document: position, nature (letters, digits, consistency rules, meaning).

Some systems process only a unique kind of document. Others receive an heterogeneous stream of documents. In that case the system has to identify the document class (and therefore the corresponding reading model) of a given document, which means a document class identification module precedes the reading module. In many systems, the classes to discriminate are known before the classification module conception [START_REF] Héroux | Classification methods study for automatic form class identification[END_REF] [START_REF] Clavier | Stratégies de tri : un système de tri des formulaires[END_REF]. During the desing it is possible to determine the most discriminating features by studying the images representing the classes. On the other hand, systems are now conceived without knowing the number or the nature of the document classes. Then the classification module has to automatically determine the best features set for the given set of document classes during a learning step.

This paper presents a document classification module, which automatically performs feature selection on any set of document classes. This module is designed to be added to an existing system that reads handwritten fields on documents from a unique class. This system needs to know the reading model. By associating a reading model to each document class, the document classification module allows the system to process an heterogeneous stream of documents.

The system is intended to be sold to final users such as government services or banks, which are not specialists in document analysis nor classification specialists. Therefore the module determines reflexively the most discriminating set of features given a specific problem. If the available features set is not able to efficiently separate the images of a particular project, new features can be easily inserted inside the module.

Our strategy simultaneously performs the feature selection for a given problem and the document classification. It is based on the computation of distance between documents. In section 2, we remind the context in which the classification module is inserted and we expose the constraints attached to a commercial use. Section 3 introduces the main definitions. It details the notion of document class, presents the structure of the features used to extract feature sets, and finally introduces the concept of distance between document images according to to a feature and its metric. Section 4 details the principles of the classification process which is presented in section 5 and 6. Section 5 presents the different steps of the supervised learning phase. Section 6 describes the processes applied to document image to determine its class. Finally, experimental results are presented in section 7. These are compared with results given by a knn classifier.

Context and Constraints

We remind that the module presented in this article is added to an existing system that reads handwritten fields of forms from a unique class. The purpose of the module is to identify the class of the document so that the system can process documents from multiple classes. Once the document class is determined, the document is processed as done before by using the associated reading model. This reading model includes rules (location, nature, syntax, meaning, consistency) which allow to improve the automatic reading.

The use of the classification module as a part of a commercial product implies to respect some constraints. It must be able to discriminate the class of a document among a hundred classes, and the processing time has to be lower than a limit fixed by the final user (1 or 2 seconds per document with a 1GHz PC). This implies that the processing time is a sub linear function of the classes number.

The time needed to classify a document among 100 classes must not be 10 times greater than the time needed to classify a document among 10 classes. On the other hand, final users are not specialists in document analysis. They do not know how to determine the best parameters for the classification. The classification module must be able to automatically adapt its parameters to be as robust as possible on any document set, by evaluating its discrimination performance.

Definitions

This section defines the most important terms used in the description of the classification module principle. More accurately, the concepts of document classes, feature, and distance between documents are introduced and detailed.

As mentioned above, we define a document image class as a set of document images on which the same reading model is applied. In our case, the reading model is defined by the final user. A document class is then defined because of the subsequent processing. Two documents are in the same class if the fields to be read are at the same location even if the images look structurally very different. On the other hand, two documents which images are very similar can be in two different classes if, for example, two fields have their location inverted. For a given problem, two documents from the same class can be in two different classes in an other problem, if their reading model becomes different.

Notation 1 Document image and document images set The document image classes set is called ClassSet. The document images set is called ImageSet. The set of images belonging to class

C is called ImageSet C .
The features used can be numerical, syntactical and/or structural. It is possible to associate different metrics to each feature. Each metric allows to compute a distance between two document images.

Definition 1. Feature and Metric

The feature space associated to the feature

F is called Space F . A metric associ- ated to F is called M F . F : ImageSet → Space F M F : Space F × Space F → [0, 1]
The features set is called F eatureSet. The metric set is called M etricSet.

The metric associated to each feature can be computed with Euclidean, Hamming, Max, Min [START_REF] Ribert | Structuration évolutive de données : Application à la construction de classifieurs distribués[END_REF], edition distance, graph distance.

Definition 2. Distance between document images

The distance between document images I 1 and I 2 according the feature F is defined by :

D F : ImageSet × ImageSet → [0, 1] D F (I 1 , I 2 ) = M F (F (I 1 ), F (I 2 ))
A distance computed between two documents from the same class is called an intra-class distance. Otherwise, it is called an inter-class distance. For each metric M F and for each class C, an image is chosen as representative. This choice is detailed in section 5.

Notation 2

The image which represents the class C according to M F is called

I * M F ,C .
The distance between an image I and a class C according to M F is defined as the distance between I and I * M F ,C . Definition 3.

D (M F ,C) : ImageSet → [0, 1] D (M F ,C) (I) = D (M F ,C) I * M F ,C , I = M F (F (I * M F ,C ), F (I))

Notation 3 intra-class and inter-class distances

The set of inter-class distances between

I * M F ,C and images from C ′ is called DX M F ,C (C ′ ). The set of intra-class distances DX M F ,C (C) is called DI M F ,C .

Classification principle

In classical approaches, a document image is represented by a point in a feature space. Then, classes correspond to clusters. The classification process consists in finding frontiers between these clusters. Our approach differs from commonly used classifiers. The feature space is projected in a one dimensional distance space. A point in this space represents the distance according a metric between a point of the feature space and a point of view. The representative I * M F ,C defines a point of view. Thanks to the metric M F , it is possible to compute the distances between I * M F ,C and each other class. Let Ĩ be the image to classify and C be the class of Ĩ. The computation of D (M F ,C) ( Ĩ) gives the position of Ĩ with respect to C. If we know the relative position of every class C ′ and even if only one distance is computed, we can estimate the value of the membership function for each class. Indeed, if the distance between C and C ′ differs from the distance between C and Ĩ, the probability that Ĩ is a member of C ′ is low.

More formally, for each class C ′ , the set of inter-class distances

DX M F ,C (C ′ ) between I * M F ,C the representative of C according M F and images from the C ′ is computed. D (M F ,C) (I) is the distance between the representative of C et Ĩ.
Then, Ĩ might be a member of every class C ′′ where

D (M F ,C) (I) is close to DX M F ,C (C ′′ ).
This is the main idea of our approach. In classical methods, Ĩ is considered as a member of the nearest class in the feature space. Our approach computes the distance d between Ĩ and a point of view. Ĩ is then considered as a member of a class whose distance to the point of view is close to d.

The classification module has Card(M etricSet) × Card(ClassSet) couples (M F , C). Each of these can be a point of view. Then the training step of our module consists in computing the distances between the document images from the different classes.

The classification of an unknown document consists in selecting a sequence of couples (M F , C) and exploiting the different classification hypothesis to identify the real class.

Learning

The learning phase is performed for each feature F and each corresponding metric M F . First, a document image from ImageSet C is chosen for each couple (M F , C) to represent the C class according M F . This is performed by computing the intra-class distances D M F (I, J) , ∀(I, J) ∈ ImageSet C × ImageSet C . We deduce I * M F ,C from the intra-class distances. Different choice might be implemented. The representative can be the gravity center, the image which minimize the greatest intra-class-distance or the image which minimizes the standard deviation of the intra-class distances. This choice may be the subject of future study. Our choice is the image which minimizes the standard deviation.

The second step of the learning phase consists in giving to each class the knowledge of the distance which separates it from other classes according to each metric. To do so, we could evaluate the distances between every document image from a C class and every document image from C ′ classes. But to reduce the training time, only the distances between the class representative of C and every document image from the other classes are computed. Theses distances allow to build the sets DX M F ,C (C ′ ) and DI M F ,C of inter and intra-class distances (cf. notation 3).

Each class has now the knowledge of the distance between its representative and every image from the other classes according every M F .

Then, a membership function can be defined from the computed learning data. Indeed, according to each feature, each class has the knowledge of the distance with the other classes.

So if a document image is represented by a point in the feature space, and if the projection of this point in the distance space is located in the interval

[min(DX M F ,C (C ′ )), max(DX M F ,C (C ′ ))],
then the image might be a member of the class C ′ . On the other hand, the more the point is far of this interval, the lower is the value of the membership function.

Classification

Classification is performed by iteratively filtering the list of candidate classes.

First, for each iteration, a (M F , C) couple is selected. The module selects the couple for which the ranges of the DX F,C (C ′ ) are the most different for every C ′ in the candidate classes. The most informative couple is the one which maximizes the distances between intervals and which minimizes their intersection. These intervals in the distance space correspond to hyper-rings in the feature space (see Fig. 1(a), 1(b) and 1(c)). In other words, the couple (M F , C) which gives the best point of view, if it is the one with the lowest intersection between hyperrings. Then, an image represented by a point in the distance space, will belong to a low number of intervals.

Figures 1(a), 1(b) and 1(c) presents a problem with 3 classes and 1 feature space. It illustrates the discriminating power of different points of view. Indeed, if the selected point of view is the center of the class A, there is an intersection between the ring including the class B and the ring including the class C. This means that the corresponding intervals in the distance space overlap. The interval overlap is lower if the selected point of view is the center of class B. There is no more overlap if the center of class C is chosen. Then each point of the feature space belongs to one ring at most. This choice can be made in different feature spaces and with different metrics. The distance D (M F ,C) ( Ĩ) between Ĩ and the selected point of view I * M F ,C is then computed with the metric of the selected feature F . This distance computation corresponds to draw a circle in Space F centered on the representative image of the selected class C. All classes which intersect the circle are kept in the candidate class list because the membership function is equal to 1. Classes whose membership function value is lower than a threshold are removed from the list. This process is repeated until one class or less remains in the candidate list. The selection of the best point of view correspond to choose the feature space and the metric with the best discriminating power for the candidate classes. The iterative process corresponds to determine a path in a dynamically built decision tree [START_REF] Vannoorenberghe | Handling uncertain labels in multiclass problems using belief decision trees[END_REF]. If no class remains, Ĩ is rejected.

The choice of the best point of view does not take into account the eliminated classes. However, their representative are still potential points of view.

Experimental Results

The classification module contains 6 features (graphical [START_REF] Clavier | Stratégies de tri : un système de tri des formulaires[END_REF] [5] and structural [1] [6]). For the presented test, the representative of each couple (M F , C) is chosen as the image which minimizes the intra-class distance standard-deviation.

The tests have been performed on different bases containing images representing differents classes of cheque-deposits, forms and air flight coupons. Experimental results are given in Table 1.

As mentionned in section 2, the classes are defined by the position and the nature of the handwritten fields to be read. The preprocessing (eg. binarization) is an other source of variability. On the other hand, users only provide few images for learning (5 to 10 images per class). Fig. 7 shows examples of images from two different bases. The results presented in table 1 have be compared with the ones given by a knn classifier. In a first experiment, tests have been performed with a classifier for each of the 6 features. Several values of k have been tested (1, 3, 5 and 10) but it seems that it has a low influence on the results. The results also showed that some features are well suited for a problem and have a low discriminating power on an other. Indeed, the best configuration gave a classification rate of 96% on a problem, but the same feature gave classification rate lower than 60% on an other base.

In a second experiment, all the features have been grouped in a single feature vector. The results were lower than 40% for every base, the discriminating power of well suited features being disturbed by others. A feature selection should have been performed for each base. This comparison validate the dynamic feature selection of our approach. Moreover, the knn classifier needs to compute the distance with every point of the training set whereas our approach only compute a distance per iteration.

Conclusion

This article presents an original classification strategy which is applied to document image classification. This strategy is implanted as a module of a complete solution which aims at automatically reading handwritten fields on document images from multiple classes. The strategy presents some advantages. First, the classification process is a sub-linear function of the number of classes. We do not have to compute the distance with every class representative. This allow to use it in an industrial context. Moreover, the module is easily configurable. By setting the number or the proportion of candidate classes to eliminate, a maximum number of iteration can be set. Lastly, the module architecture allows to add features very easily. In our system, a feature is only defined by its features space and its distance computation. Indeed, it is only required to write a function that places an image in the applied feature space and a distance function returning a real in [0, 1]. So for a particular difficult project with specific constraints, we can easily add features dedicated to the discrimination of the not easily separable classes.

At each iteration of the classification process, the best feature vector with the best point of view is dynamically determined.

The main advantage to work in distance spaces, is that it allows to use a large variety of feature. The processed feature vectors can be very different. There is no restriction concerning its size and nature. Numeric, syntactic and structural features can be mixed in the feature set and even in the same feature vector if a distance can be computed between two vectors.

The learning phase can be incremental. If a new class is added, the previous computed distance are kept, only the distances with the new documents have to be evaluated. New features can be added in the same way.

It seems that this strategy can be applied to a large scope of classification problems with supervised learning.

The strategy presented in this paper is a very preliminary work. The first results seem to be promising, but they could be improved by further works on many aspects (choice of the class representative, dynamic determination of the best feature vector for the best point of view).

Another future work would be to improve the used feature set. For example, the better feature vector could be determined to limit the computation complexity. The feature vectors could be combined to build new ones, for example by using genetic algorithms. We can imagine that the built feature vector would use features exploiting different zones of the document image. The genetic algorithms would then select the features associated to the most discriminating zones.

Fig. 1 .

 1 Fig. 1. Choice of the point of view

  Candidates ← ClassSet while Card(Candidates) > 1 choose best couple(F,C) compute d= D (F,C) (I) remove far classes in Candidates according to DX F,C endWhile if Card(Candidates) > 0 then C=Candidates[0] else reject I

Fig. 2 .

 2 Fig. 2. Exemple of images

Table 1 .

 1 Results

		#Images #Classes #Iterations	Good	Reject Confusion
					classification rate	rate
					rate
	A	25125	2	1	100%	0%	0%
	B	123	8	2 to 4	96%	4%	0%
	C	65689	6	2 to 3	92%	4%	4%
	D	8770	6	2 to 3	95%	4%	1%
	C+D 10000	12	2 to 4	89%	1%	9%