Luc Lehéricy
email: luc.lehericy@math.u-psud.fr

State-by-state Minimax Adaptive Estimation for Nonparametric Hidden Markov Models

Keywords: hidden Markov model, model selection, nonparametric density estimation, oracle inequality, adaptive minimax estimation, spectral method, least squares method

In this paper, we introduce a new estimator for the emission densities of a nonparametric hidden Markov model. It is adaptive and minimax with respect to each state's regularityas opposed to globally minimax estimators, which adapt to the worst regularity among the emission densities. Our method is based on Goldenshluger and Lepski's methodology. It is computationally efficient and only requires a family of preliminary estimators, without any restriction on the type of estimators considered. We present two such estimators that allow to reach minimax rates up to a logarithmic term: a spectral estimator and a least squares estimator. We show how to calibrate it in practice and assess its performance on simulations and on real data.

Introduction

Finite state space hidden Markov models, or HMMs in short, are powerful tools for studying discrete time series and have been used in a variety of applications such as economics, signal processing and image analysis, genomics, ecology, speech recognition and ecology among others. The core idea is that the behaviour of the observations depends on a hidden variable that evolves like a Markov chain.

Formally, a hidden Markov model is a process (X j , Y j ) j≥1 in which (X j ) j is a Markov chain on X , the Y i 's are independent conditionally on (X j ) j and the conditional distribution of Y i given (X j ) j depends only on X i . The parameters of the HMM are the parameters of the Markov chain, that is its initial distribution and transition matrix, and the parameters of the observations, that is the emission distributions (ν * k ) k∈X where ν * k is the distribution of Y j conditionally to X j = k. Only the observations (Y j ) j are available.

In this article, we focus on estimating the emission distributions in a nonparametric setting. More specifically, assume that the emission distributions have a density with respect to some known dominating measure µ, and write f * k their densities-which we call the emission densities. The goal of this paper is to estimate all f * k 's with their minimax rate of convergence when the emission densities are not restricted to belong to a set of densities described by finitely many parameters.

Nonparametric state-by-state adaptivity

Theoretical results in the nonparametric setting have only been developed recently. De [START_REF] De Castro | Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models[END_REF] and Bonhomme et al. (2016b) introduce spectral methods, and the latter is proved to be minimax but not adaptive-which means one needs to know the regularity of the densities beforehand to reach the minimax rate of convergence. De [START_REF] De Castro | Minimax adaptive estimation of nonparametric hidden Markov models[END_REF] introduce a least squares estimator which is shown to be minimax adaptive up to a logarithmic term. However, all these papers have a common drawback: they study the emission densities as a whole and can not handle them separately. This comes from their error criterion, which is the supremum of the errors on all densities: what they actually prove is that max k∈X fk -f * k 2 converges with minimax rate when ( fk ) k are their density estimators. In general, the regularity of each emission density could be different, leading to different rates of convergence. This means that having just one emission density that is very hard to estimate is enough to deteriorate the rate of convergence of all emission densities.

In this paper, we construct an estimator that is adaptive and estimates each emission density with its own minimax rate of convergence. We call this property state-by-state adaptivity. Our method does so by handling each emission density individually in a way that is theoretically justified-reaching minimax and adaptive rates of convergence with respect to the regularity of the emission densities-and computationally efficient thanks to its low computational and sample complexity.

Our approach for estimating the densities nonparametrically is model selection. The core idea is to approximate the target density using a family of parametric models that is dense within the nonparametric class of densities. For a square integrable density f * , we consider its projection f * M on a finite-dimensional space P M (the parametric model), where M is a model index. This projection introduces an error, the bias, which is the distance f * -f * M 2 between the target quantity and the model. The larger the model, the smaller the bias. On the other hand, larger models will make the estimation harder, resulting in a larger variance fM -f * M 2 2 . The key step of model selection is to select a model with a small total error-or alternatively, a good bias-variance tradeoff.

In many situations, it is possible to reach the minimax rate of convergence with a good bias-variance tradeoff. Previous estimators of the emission densities of a HMM perform such a tradeoff based on an error that takes the transition matrix and all emission densities into account. Such an error leads to a rate of convergence that corresponds to the slowest minimax rate amongst the different parameters. In contrast, our method performs a biasvariance tradeoff for each emission density using an error term that depends only on the density in question, which makes it possible to reach the minimax rates for each density.

Plug-in procedure

The method we propose is based on the method developed in the seminal papers of Goldenshluger andLepski (2011, 2014) for density estimation, extended by [START_REF] Goldenshluger | General selection rule from a family of linear estimators[END_REF] to the white noise and regression models. It takes a family of estimators as input and chooses the estimator that performs a good bias-variance tradeoff separately for each hidden state. We recommend the article of [START_REF] Lacour | Estimator selection: a new method with applications to kernel density estimation[END_REF] for an insightful presentation of this method in the case of conditional density estimation.

Our method and assumptions are detailed in Section 2. Let us give a quick overview of the method. Assume the densities belong to a Hilbert space H. Given a family of subsets of finite-dimensional subspaces of H (the models) indexed by M and estimators f (M ) k of the emission densities for each hidden state k and each model M , one computes a substitute for the bias of the estimators by

A k (M ) = sup M f (M ) k - f (M ∧M ) k 2 -σ(M ) .
for some penalty σ. Then, for each state k, one selects the estimator Mk from the model M minimizing the quantity A k (M ) + 2σ(M ). The penalty σ can also be interpreted as a variance bound, so that this penalization procedure can be seen as performing a biasvariance tradeoff. The novelty of this method is that it selects a different Mk , that is a different model, for each hidden state: this is where the state-by-state adaptivity comes from. Also note that contrary to [START_REF] Goldenshluger | General selection rule from a family of linear estimators[END_REF], we do not make any assumption on how the estimators are computed, provided a variance bound holds.

The main theoretical result is an oracle inequality on the selected estimators f ( Mk ) k , see Theorem 2. As a consequence, we are able to get a rate of convergence that is different for each state. These rates of convergence will even be adaptive minimax up to a logarithmic factor when the method is applied to our two families of estimators: spectral estimators and least squares estimators. To the best of our knowledge, this is the first state-by-state adaptive algorithm for hidden Markov models.

Note that finding the right penalty term σ is essential in order to obtain minimax rates of convergence. This requires a fine theoretical control of the variance of the auxiliary estimators, in the form of assumption [H( )] (see Section 2.1). To the best of our knowledge, there is no suitable result in the literature. This is the second theoretical contribution of this paper: we control two families of estimators in a way that makes it possible to reach adaptive minimax rate with our state-by-state selection method, up to a logarithmic term.

On the practical side, we run this method and several variants on data simulated from a HMM with three hidden states and one irregular density, as illustrated in Section 4. The simulations confirm that it converges with a different rate for each emission density, and that the irregular density does not alter the rate of convergence of the other ones, which is exactly what we wanted to achieve.

Better still, the added computation time is negligible compared to the computation time of the estimators: even for the spectral estimators of Section 3.2 (which can be computed much faster than the least squares estimators and the maximum likelihood estimators using EM), computing the estimators on 200 models for 50,000 observations (the lower bound of our sample sizes) of a 3-states HMM requires a few minutes, compared to a couple of seconds for the state-by-state selection step. The difference becomes even larger for more observations, since the complexity of the state-by-state selection step is independent of the sample size: for instance, computing the spectral estimators on 300 models for 2,200,000 observations requires a bit less than two hours, and a bit more than ten hours for 10,000,000 observations, compared to less than ten seconds for the selection step in both cases. We refer to Section 4.6 for a more detailled discussion about the algorithmic complexity of the algorithms.

Families of estimators

We use two methods to construct families of estimators and apply the selection algorithm. The motivation and key result of this part of the paper is to control the variances of the estimators by the right penalty σ. This part is crucial if one wants to get adaptive minimax rates, and has not been adressed in previous papers. For both methods, we develop new theoretical results that allow to obtain a penalty σ that leads to adaptive minimax rates of convergence up to a logarithmic term. We present the algorithms and theoretical guarantees in Section 3.

The first method is a spectral method and is detailed in Section 3.2. Several spectral algorithms were developed, see for instance [START_REF] Anandkumar | A method of moments for mixture models and hidden Markov models[END_REF] and [START_REF] Hsu | A spectral algorithm for learning hidden Markov models[END_REF] in the parametric setting, and Bonhomme et al. (2016b) and[START_REF] De Castro | Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models[END_REF] in a nonparametric framework. The main advantages of spectral methods are their computational efficiency and the fact that they do not resort to optimization procedure such as the EM and more generally nonconvex optimization algorithm, thus avoiding the well-documented issue of getting stuck into local sub-optimal minima.

Our spectral algorithm is based on the one studied in De [START_REF] De Castro | Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models[END_REF]. However, their estimator cannot reach the minimax rate of convergence: the variance bound σ(M ) deduced from their results is proportional to M 3 , while reaching the minimax rate requires σ(M ) to be proportional to M . To solve this issue, we introduce a modified version of their algorithm and show that it has the right variance bound, so that it is able to reach the adaptive minimax rate after our state-by-state selection procedure, up to a logarithmic term. Our algorithm also has an improved complexity: it is at most quasi-linear in the number of observations and in the model dimension, instead of cubic in the model dimension for the original algorithm.

The second method is a least squares method and is detailed in Section 3.3. Nonparametric least squares methods were first introduced by De Castro et al. (2016) to estimate the emission densities and extended by Lehéricy (to appear) to estimate all parameters at once. They rely on estimating the density of three consecutive observations of the HMM using a least squares criterion. Since the model is identifiable from the distribution of three consecutive observations when the emission distributions are linearly independent, it is possible to recover the parameters from this density. In practice, these methods are more accurate than the spectral methods and are more stable when the models are close to not satisfying the identifiability condition, see for instance De [START_REF] De Castro | Minimax adaptive estimation of nonparametric hidden Markov models[END_REF] for the accuracy and Lehéricy (to appear) for the stability. However, since they rely on the minimization of a nonconvex criterion, the computation times of the corresponding algorithms are often longer than the ones from spectral methods.

A key step in proving theoretical guarantees for least squares methods is to relate the error on the density of three consecutive observations to the error on the HMM parameters in order to obtain an oracle inequality on the parameters from the oracle inequality on the density of three observations. More precisely, the difficult part is to lower bound the error on the density by the error on the parameters. Let us write g and g the densities of the first three observations of a HMM with parameters θ and θ respectively (these parameters actually correspond to the transition matrix and the emission densities of the HMM). Then one would like to get g -

g 2 ≥ C(θ) d(θ, θ )
where d is the natural L 2 distance on the parameters and C(θ) is a positive constant which does not depend on θ . Such inequalities are then used to lower bound the variance of the estimator of the density of three observations g * by the variance of the parameter estimators: let g be the projection of g * and g be the estimator of g * on the current approximation space (with index M ). Denote θ * M and θM the corresponding parameters and assume that the error g -g 2 is bounded by some constant σ (M ), then the result will be that

d( θM , θ * M ) ≤ σ (M ) C(θ * M )
.

Such a result is crucial to control the variance of the estimators by a penalty term σ, which is the result we need for the state-by-state selection method. In the case where only the emission densities vary, De Castro et al. ( 2016) proved that such an inequality always holds for HMMs with 2 hidden states using brute-force computations, but it is still unknown whether it is always true for larger number of states. When the number of states is larger than 2, they show that this inequality holds under a generic assumption. Lehéricy (to appear) extended this result to the case where all parameters may vary. However, the constants deduced from both articles are not explicit, and their regularity (when seen as a function of θ) is unknown, which makes it impossible to use in our setting: one needs the constants C(θ * M ) to be lower bounded by the same positive constant, which requires some sort of regularity on the function θ -→ C(θ) in the neighborhood of the true parameters.

To solve this problem, we develop a finer control of the behaviour of the difference g -g 2 , which is summarized in Theorem 10. We show that it is possible to assume C to be lower semicontinuous and positive without any additional assumption. In addition, we give an explicit formula for the constant when θ and θ are close, which gives an explicit bound for the asymptotical rate of convergence. This result allows us to control the variance of the least squares estimators by a penalty σ which ensures that the state-by-state method reaches the adaptive minimax rate up to a logarithmic term.

Numerical validation and application to real data sets

Section 4 shows how to apply the state-by-state selection method in practice and shows its performance on simulated data and a comparison with a method based on cross validation that does note estimate state by state.

Note that the theoretical results give a penalty term σ known only up to a multiplicative constant which is unknown in practice. This problem, the penalty calibration issue, is usual in model selection methods. It can be solved using algorithms such as the dimension jump heuristics, see for instance [START_REF] Birgé | Minimal penalties for gaussian model selection[END_REF], who introduce this heuristics and prove that it leads to an optimal penalization in the special case of Gaussian model selection framework. This method has been shown to behave well in practice in a variety of domains, see for instance [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF]. We describe the method and show how to use this heuristics to calibrate the penalties in Section 4.2.

We propose and compare several variants of our algorithm. Section 4.2 shows some variants in the calibration of the penalties and Section 4.3 shows other ways to select the final estimator. We discuss the result of the simulations and the convergence of the selected estimators in Section 4.4.

In Section 4.5, we compare our method with a non state-by-state adaptive method based on cross validation. Finally, we discuss the complexities of the auxiliary estimation methods and of our selection procedures in Section 4.6.

In Section 5, we apply our algorithm to two sets of GPS tracks. The first data set contains trajectories of artisanal fishers from Madagascar, recorded using a regular sampling with 30 seconds time steps. The second data set contains GPS positions of Peruvian seabird, recorded with 1 second time steps. We convert these tracks into the average velocity during each time step and apply our method using spectral estimators as input. The observed behaviour confirms the ability of our method to adapt to the different regularities by selecting different dimensions for each emission density.

Section 6 contains a conclusion and perspectives for this work. Finally, Appendix A contains the details of our spectral algorithm and Appendix B is dedicated to the proofs.

Notations

We will use the following notations throughout the paper.

• [K] = {1, . . . , K} is the set of integers between 1 and K.

• S(K) is the set of permutations of [K].

• • F is the Frobenius norm. We implicitely extend the definition of the Frobenius norm to tensors with more than 2 dimensions.

• Span(A) is the linear space spanned by the family A.

• σ 1 (A) ≥ • • • ≥ σ p∧n (A) are the singular values of the matrix A ∈ R n×p .

• L 2 (Y, µ) is the set of real square integrable measurable functions on Y with respect to the measure µ.

• For f = (f 1 , . . . , f K ) ∈ L 2 (Y, µ) K , G(f ) is the Gram matrix of f , defined by G(f ) i,j = f i , f j for all i, j ∈ [K].

The state-by-state selection procedure

In this section, we introduce the framework and our state-by-state selection method. In Section 2.1, we introduce the notations and assumptions. In Section 2.2, we present our selection method and prove that it satisfies an oracle inequality.

Framework and assumptions

Let (X j ) j≥1 be a Markov chain with finite state space X of size K. Let Q * be its transition matrix and π * be its initial distribution. Let (Y j ) j≥1 be random variables on a measured space (Y, µ) with µ σ-finite such that conditionally on (X j ) j≥1 the Y j 's are independent with a distribution depending only on X j . Let ν * k be the distribution of Y j conditionally to {X j = k}. Assume that ν * k has density f * k with respect to µ. We call (ν * k ) k∈X the emission distributions and f * = (f * k ) k∈X the emission densities. Then (X j , Y j ) j≥1 is a hidden Markov model with parameters (π * , Q * , f * ). The hidden chain (X j ) j≥1 is assumed to be unobserved, so that the estimators are based only on the observations (Y j ) j≥1 .

Let (P M ) M ∈N be a nested family of finite-dimensional subspaces such that their union is dense in L 2 (Y, µ). The spaces (P M ) M ∈N are our models; in the following we abusively call M the model instead of P M . For each index M ∈ N, we write f * ,(M ) = (f * ,(M ) k

) k∈X the projection of f * on (P M ) K . It is the best approximation of the true densities within the model M .

In order to estimate the emission densities, we do not need to use every models. Typically there is no point in taking models with more dimensions than the sample size, since they will likely be overfitting. Let M n ⊂ N be the set of indices which will be used for the estimation from n observations. For each M ∈ M n , we assume we are given an estimator

f (M ) n = ( f (M ) n,k ) k∈X ∈ (P M ) K .
We will need to assume that for all models, the variance-that is the distance between f (M ) n and f * ,(M ) -is small with high probability. In the following, we drop the dependency in n and simply write M and f (M ) .

The following result is what one usually obtains in model selection. It bounds the distance between the estimators f (M ) and the projections f * ,(M ) by some penalty function σ. Thus, σ/2 can be seen as a bound of the variance term.

[H( )] With probability 1 -, ∀M ∈ M, inf τ n,M ∈S(K) max k∈X f (M ) k -f * ,(M ) τ n,M (k) 2 ≤ σ(M, , n) 2
where the upper bound σ : (M, , n

) ∈ M × [0, 1] × N * -→ σ(M, , n) ∈ R + is nondecreasing in M .
We show in Sections 3.2 and 3.3 how to obtain such a result for a spectral method and for a least squares method (using an algorithm from Lehéricy (to appear)). In the following, we omit the parameters and n in the notations and only write σ(M ).

What is important for the selection step is that the permutation τ n,M does not depend on the model M : one needs all estimators ( f (M )

k

) M ∈M to correspond to the same emission density, namely f * τn(k) when τ n,M = τ n is the same for all models M . This can be done in the following way: let M 0 ∈ M and let

τ (M ) ∈ arg min τ ∈S(K) max k∈X f (M ) τ (k) - f (M 0 ) k 2
for all M ∈ M. Then, consider the estimators obtained by swapping the hidden states by these permutations. In other words, for all k ∈ X , consider

f (M ) k,new = f (M ) τ (M ) (k) .
Now, assume that the error on the estimators is small enough. More precisely, write

B M,M 0 = max k∈X f * ,(M ) k -f * ,(M 0 ) k 2
the distance between the projections of f * on the models M and M 0 and assume that 2 [σ(M )/2 + σ(M 0 )/2 + B M,M 0 ] (that is twice the upper bound of the distance between two estimated emission densities corresponding to the same hidden states in models M and

M 0 ) is smaller than m(f * , M 0 ) := min k =k f * ,(M 0 ) k -f * ,(M 0 ) k 2
, which is the smallest distance between two different densities of the vector f * ,(M 0 ) .

Then [H( )] ensures that with probability as least 1 -, for all k, there exists a single component of f (M ) that is closer than σ(M )/2 + σ(M 0 )/2 of f * ,(M 0 ) k

, and this component will be f (M ) τ (M ) (k) by definition. This is summarized in the following lemma.

Lemma 1 Assume [H( )] holds. Then with probability 1 -, there exists a permutation τ n ∈ S(K) such that for all k ∈ X and for all M ∈ M such that

σ(M ) + σ(M 0 ) + 2B M,M 0 < m(f * , M 0 ), one has max k∈X f (M ) k,new -f * ,(M ) τn(k) 2 ≤ σ(M ) 2 . ( 1
)
Proof Proof in Section B.1

Thus, this property holds asymptotically as soon as inf M tends to infinity and sup M ∈M σ(M ) tends to zero.

Estimator and oracle inequality

Let us now introduce our selection procedure. This method and the following theorem are based on the approach of [START_REF] Goldenshluger | Bandwidth selection in kernel density estimation: oracle inequalities and adaptive minimax optimality[END_REF], but do not require any assumption on the structure of the estimators, provided a variance bound such as Equation (1) holds.

For each k ∈ X and M ∈ M, let

A k (M ) = sup M ∈M f (M ) k - f (M ∧M ) k 2 -σ(M ) .
A k (M ) serves as a replacement for the bias of the estimator f (M ) k , as can be seen in Equation (2). This comes from the fact that for large M , the quantity

f (M ) k - f (M ) k 2 is upper bounded by the variances f (M ) k -f * ,(M ) k 2 and f (M ) k -f * ,(M ) k 2 (which are bounded by σ(M )/2) plus the bias f * ,(M ) k -f * k 2 .
Thus, only the bias term remains after substracting the variance bound σ(M ).

Then, for all k ∈ X , select a model through the bias-variance tradeoff Mk ∈ arg min

M ∈M {A k (M ) + 2σ(M )} and finally take fk = f ( Mk ) k .
The following theorem shows an oracle inequality on this estimator.

Theorem 2 Let ≥ 0 and assume equation ( 1) holds for all k ∈ X with probability 1 -.

Then with probability 1 -,

∀k ∈ X , fk -f * τn(k) 2 ≤ 4 inf M ∈M f * ,(M ) τn(k) -f * τn(k) 2 + σ(M, ) .
Proof We restrict ourselves to the event of probability at least 1 -where equation ( 1) holds for all k ∈ X . The first step consists in decomposing the total error: for all M ∈ M and k ∈ X ,

f ( Mk ) k -f * τn(k) 2 ≤ f ( Mk ) k - f ( Mk ∧M ) k 2 + f ( Mk ∧M ) k - f (M ) k 2 + f (M ) k -f * ,(M ) τn(k) 2 + f * ,(M ) τn(k) -f * τn(k) 2
.

From now on, we will omit the subscripts k and τ n (k). Using equation ( 1) and the definition of A(M ) and M , one gets

f ( M ) -f * 2 ≤(A(M ) + σ( M )) + (A( M ) + σ(M )) + σ(M ) + f * ,(M ) -f * 2 ≤2A(M ) + 4σ(M ) + f * ,(M ) -f * 2 .
Then, notice that A(M ) can be bounded by

A(M ) ≤ sup M f (M ) -f * ,(M ) 2 + f (M ∧M ) -f * ,(M ∧M ) 2 -σ(M ) + sup M f * ,(M ) -f * ,(M ∧M ) 2 . Since σ is nondecreasing, σ(M ∧ M ) ≤ σ(M )
, so that the first term is upper bounded by zero thanks to equation ( 1). The second term can be controlled since the orthogonal projection is a contraction. This leads to

A(M ) ≤ f * -f * ,(M ) 2 , (2)
which is enough to conclude.

Remark 3 The oracle inequality also holds when taking

A k (M ) = sup M ≥M f (M ) k - f (M ) k 2 -σ(M ) + .
Remark 4 Note that the selected Mk implicitely depends on the probability of error through the penalty σ.

In the asymptotic setting, we take as a function of n, so that Mk is a function of n only. This will be used to get rid of when proving that the estimators reach the minimax rates of convergence.

Plug-in estimators and theoretical guarantees

In this section, we introduce two methods to construct families of estimators of the emission densities. We show that they satisfy assumption [H( )] for a given variance bound σ.

In Section 3.1, we introduce the assumptions we will need for both methods. Section 3.2 is dedicated to the spectral estimator and Section 3.3 to the least squares estimator.

Framework and assumptions

Recall that we approximate L 2 (Y, µ) by a nested family of finite-dimensional subspaces (P M ) M ∈M such that their union is dense in L 2 (Y, µ) and write f * ,(M ) k the orthogonal projection of f * k on P M for all k ∈ X and M ∈ M. We assume that M ⊂ N and that the space P M has dimension M . A typical way to construct such spaces is to take P M spanned by the first M vectors of an orthonormal basis.

Both methods will construct an estimator of the emission densities for each model of this family. These estimators will then be plugged in the state-by-state selection method of Section 2.2, which will select one model for each state of the HMM.

We will need the following assumptions.

[HX] (X j ) j≥1 is a stationary ergodic Markov chain with parameters (π * , Q * );

[Hid] Q * is invertible and the family f * is linearly independent.

The ergodicity assumption in [HX] is standard in order to obtain convergence results. In this case, the initial distribution is forgotten exponentially fast, so that the HMM will essentially behave like a stationary process after a short period of time. For the sake of simplicity, we assume the Markov chain to be stationary.

[Hid] appears in identifiability results, see for instance [START_REF] Gassiat | Finite state space non parametric hidden Markov models are in general identifiable[END_REF] and Theorem 8. It is sufficient to ensure identifiability of the HMM from the law of three consecutive observations. Note that it is in general not possible to recover the law of a HMM from two observations (see for instance Appendix G of Anandkumar et al. ( 2012)), so that three is actually the minimum to obtain general identifiability.

The spectral method

Algorithm 1 is a variant of the spectral algorithm introduced in De Castro et al. (2017). Unlike the original one, it is able to reach the minimax rate of convergence thanks to two improvements. The first one consists in decomposing the joint density on different models, hence the use of two dimensions m and M . The second one consists in trying several randomized joint diagonalizations instead of just one, and selecting the best one, hence the parameter r. These additional parameters do not actually add much to the complexity of the algorithm: in theory, the choice m, r ≈ log(n) is fine (see Corollary 6), and in practice, any large enough constant works, see Section 4 for more details.

For all M ∈ M, let (ϕ M 1 , . . . , ϕ M M ) be an orthonormal basis of P M . Let

η 3 (m, M ) 2 := sup y,y ∈Y 3 m a,c=1 M b=1 (ϕ m a (y 1 )ϕ M b (y 2 )ϕ m c (y 3 ) -ϕ m a (y 1 )ϕ M b (y 2 )ϕ m c (y 3 )) 2 .
The following theorem follows the proof of Theorem 3.1 of De Castro et al. ( 2017), with modifications that allow to control the error of the spectral estimators in expectation and are essential to obtain the right rates of convergence in Corollary 6.

Theorem 5 Assume [HX] and [Hid] hold. Then there exists a constant M 0 depending on f * and constants C σ and n 1 depending on f * and Q * such that for all ∈ (0, 1), for all Algorithm 1: Spectral estimation of the emission densities of a HMM (short version)

Data: A sequence of observations (Y 1 , . . . , Y n+2 ), two dimensions m ≤ M , an orthonormal basis (ϕ 1 , . . . , ϕ M ) and number of retries r.

Result: Spectral estimators ( f (M,r) k ) k∈X .
[

Step 1] Consider the following empirical estimators: for any a, c ∈ [m] and b ∈ [M ],

• Mm,M,m (a, b, c)

:= 1 n n s=1 ϕ a (Y s )ϕ b (Y s+1 )ϕ c (Y s+2 ) • Pm,m (a, c) := 1 n n s=1 ϕ a (Y s )ϕ c (Y s+2 ).
∈ [M ], B(b) ≈ RDiag[ Ô(b, •)]R -1 for some matrix R (see details in Algorithm 3, in Appendix A). [Step 5] Define the emission densities estimators f (M,r) := ( f (M,r) k ) k∈X by: for all k ∈ X , f (M,r) k := M b=1 Ô(b, k)ϕ b . m, M ∈ M such that M ≥ m ≥ M 0 and for all n ≥ n 1 η 2 3 (m, M )(-log ) 2 , with probability greater than 1 -6 , inf τ ∈S(K) max k∈X f (M, t ) k -f * ,(M ) τ (k) 2 2 ≤ C σ η 2 3 (m, M ) (-log ) 2 n Proof Proof in Section B.2.
Note that the constants n 1 and C σ depend on Q * and f * . This dependency will not affect the rates of convergence of the estimators (with respect to the sample size n), but it can change the constants of the bounds and the minimum sample size needed to reach the asymptotic regime.

Let us now apply the state-by-state selection method to these estimators. The following corollary shows that it is possible to reach the minimax rate of convergence up to a logarithmic term separately for each state under standard assumptions. Note that we need to bound the resulting estimators by some power of n, but this assumption is not very restrictive since α can be arbitrarily large.

Corollary 6 Assume [HX] and [Hid] hold. Also assume that η 2 3 (m, M ) ≤ C η m 2 M for a constant C η > 0 and that for all k ∈ X , there exists

s k such that f * ,(M ) k -f * k 2 = O(M -s k ).
Then there exists a constant C σ depending on f * and Q * such that the following holds.

Let α > 0 and C ≥ 2(1 + 2α) C η C σ . Let f sbs be the estimators selected from the family ( f (M, (1+2α) log(n) ) ) M ≤Mmax(n) with M max (n) = n/ log(n) 5 , m M = log(n) and σ(M ) = C M log(n) 4
n for all M . Then there exists a sequence of random permutations

(τ n ) n≥1 such that ∀k ∈ X , E (-n α ) ∨ ( f sbs τn(k) ∧ n α ) -f * k 2 2 = O   n log(n) 4 -2s k 2s k +1   .
The novelty of this result is that each emission density is estimated with its own rate of convergence: the rate -s k 2s k +1 is different for each emission density, even though the original spectral estimators did not handle them separately. This is due to our state-by-state selection method.

Moreover, it is able to reach the minimax rate for each density in an adaptive way. For instance, in the case of a β-Hölder density on Y = [0, 1] D (equipped with a trigonometric basis), one can easily check the control of η 3 , and the control f * ,(M ) k

-f * k 2 = O(M -β/D
) follows from standard approximation results, see for instance [START_REF] Ronald | Constructive approximation[END_REF]. Thus, our estimators converge with the rate (n/ log(n) 4 ) -2β/(2β+D) to this density: this is the minimax rate up to a logarithmic factor.

Remark 7 By aligning the estimators like in Section 2.1, one can replace the sequence of permutations in Corollary 6 by a single permutation, in other words there exists a random permutation τ which does not depend on n such that

∀k ∈ X , E (-n α ) ∨ ( f sbs τ (k) ∧ n α ) -f * k 2 2 = O   n log(n) 4 -2s k 2s k +1   .
This means that the sequence ( f sbs k ) n≥1 is an adaptive rate-minimax estimator of f * k -or more precisely of one of the emission densities (f * k ) k ∈X , but since the distribution of the HMM is invariant under relabelling of the hidden states, one can assume the limit to be f * k without loss of generality-up to a logarithmic term.

At this point, it is important to note that the choice of the constant C ≥ 2(1+2α) C η C σ depends on the hidden parameters of the HMM and as such is unknown. This penalty calibration problem is very common in the model selection framework and can be solved in practice using methods such as the slope heuristics or the dimension jump method which have been proved to be theoretically valid in several cases, see for instance [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF] and references therein. We use the dimension jump method and explain its principle and implementation in Section 4.2. Proof Using Theorem 5, one gets that for all n and for all

M ∈ M such that n ≥ n 1 η 2 3 (m M , M )(1 + 2α) 2 log(n) 2 , with probability 1 -6n -1-2α , inf τ ∈S(K) max k∈X f (M, t ) k -f * ,(M ) τ (k) 2 2 ≤C σ η 2 3 (m M , M ) (1 + 2α) 2 log(n) 2 n ≤(1 + α) 2 C σ C η M log(n) 4 n ≤ σ(M ) 2 4 where σ(M ) = C M log(n) 4 n with C such that C 2 ≥ 4(1 + 2α) 2 C σ C η . The condition on M becomes n ≥ n 1 log(n) 4 M (1 + 2α) 2
and is asymptotically true for all M ≤ M max (n) as soon as

M max (n) = o(n/ log(n) 4 ).
Thus, [H(6n -( 1+2α) )] is true for the family ( f (M, (1+2α) log(n) ) ) M ≤Mmax(n) . Note that the assumption M max (n) = o(n/ log(n) 4 ) also implies that there exists M 1 such that for n large enough, Lemma 1 holds for all M ≥ M 1 , so that Theorem 2 implies that for n large enough, there exists a permutation τ n such that with probability 1 -6n -(1+2α) , for all k ∈ X ,

f sbs τn(k) -f * k 2 ≤ 4 inf M 1 ≤M ≤Mmax { f * ,(M ) k -f * k 2 + σ(M )} = O inf M 1 ≤M ≤Mmax M -s k + M log(n) 4 n = O n log(n) 4 -s k /(1+2s k )
,

where the tradeoff is reached for M = ( n log(n) 4 ) 1/(1+2s k ) , which is in [M 1 , M max (n)] for n large enough.
Finally, write A the event of probability smaller than 6n -(1+2α) where [H(6n -( 1+α) )] doesn't hold, then for n large enough and for all k ∈ X ,

E (-n α ) ∨ ( f sbs τn(k) ∧ n α ) -f * k 2 2 ≤ E 1 A f sbs τn(k) -f * k 2 2 + E 1 A c (n 2α + f * k 2 2 ) = O n log(n) 4 -2s k /(1+2s k ) + O n 2α + f * k 2 2 n 1+2α = O n log(n) 4 -2s k /(1+2s k )
.

The penalized least squares method

Let F be a subset of L 2 (Y, µ). We will need the following assumption on F in order to control the deviations of the estimators:

[HF] f * ∈ F K * , F is closed under projection on P M for all M ∈ M and ∀f ∈ F, f ∞ ≤ C F ,∞ f 2 ≤ C F ,2
with C F ,∞ and C F ,2 larger than 1.

A simple way to construct such a set F when µ is a finite measure is to take the sets (P M ) M spanned by the first M vectors of an orthonormal basis (ϕ i ) i≥0 whose first vector ϕ 0 is proportional to 1. Then any set F of densities such that

f dµ = 1, i f, ϕ i 2 ≤ C F ,2 and i | f, ϕ i | ϕ i ∞ ≤ C F ,∞ for given constants C F ,2 and C F ,∞ and for all f ∈ F satisfies [HF]. When Q ∈ R K×K , π ∈ R K and f ∈ (L 2 (Y, µ)) K , let g π,Q,f (y 1 , y 2 , y 3 ) = K k 1 ,k 2 ,k 3 =1 π(k 1 )Q(k 1 , k 2 )Q(k 2 , k 3 )f k 1 (y 1 )f k 2 (y 2 )f k 3 (y 3 ).
When π is a probability distribution, Q a transition matrix and f a K-uple of probability densities, then g π,Q,f is the density of the first three observations of a HMM with parameters (π, Q, f ). The motivation behind estimating g π,Q,f is that it allows to recover the true parameters under the identifiability assumption [Hid], as shown in the following theorem.

Let Q be the set of transition matrices on X and ∆ the set of probability distributions on X . For a permutation τ ∈ S(K), write P τ its matrix (that is the matrix defined by P τ (i, j) = 1 {j=τ (i)} ). Finally, define the distance on the HMM parameters

d perm ((π 1 , Q 1 , f 1 ), (π 2 , Q 2 , f 2 )) 2 = inf τ ∈S(K) π 1 -P τ π 2 2 2 + Q 1 -P τ Q 2 P τ 2 F + k∈X f 1,k -f 2,τ (k) 2 2 .
This distance is invariant under permutation of the hidden states. This corresponds to the fact that a HMM is only identifiable up to relabelling of its hidden states.

Theorem 8 (Identifiability) Let (π * , Q * , f * ) ∈ ∆ × Q × (L 2 (Y, µ)) K such that π * x > 0 for all x ∈ X and [Hid] holds. Then for all (π, Q, f ) ∈ ∆ × Q × (L 2 (Y, µ)) K , (g π,Q,f = g π * ,Q * ,f * ) ⇒ d perm ((π, Q, f ), (π * , Q * , f * )) = 0.
Proof The spectral algorithm of De Castro et al. ( 2017) applied on the finite dimensional space spanned by the components of f and f * allows to recover all the parameters even when the emission densities are not probability densities and when the Markov chain is not stationary.

Define the empirical contrast

γ n (t) = t 2 2 - 2 n n j=1 t(Z j )
where

Z j := (Y j , Y j+1 , Y j+2
) and (Y j ) 1≤j≤n+2 are the observations. It is a biased estimator of the L 2 loss: for all t ∈ (L 2 (Y, µ)) 3 ,

E[γ n (t)] = t -g * 2 2 -g * 2
Algorithm 2: Least squares estimation of the emission densities of a HMM Data: A sequence of observations (Y 1 , . . . , Y n+2 ), a dimension M and an orthonormal basis Φ = (ϕ 1 , . . . , ϕ M ). Result: Least squares estimators π(M) , Q(M) and ( f (M ) k

) k∈X .

[

Step 1] Compute the tensor MM defined by MM (a, b, c)

:= 1 n n s=1 ϕ a (Y s )ϕ b (Y s+1 )ϕ c (Y s+2 ) for all a, b, c ∈ [M ]. [Step 2] Find a minimizer (π (M ) , Q(M) , Ô) of (π, Q, O) -→ M (π,Q,O) -MM 2 F where • π ∈ R K is a probability distribution on X , i.e. k∈X π k = 1; • Q ∈ R K×K is a transition matrix on X , i.e. k ∈X Q(k, k ) = 1 for all k ∈ X ; • O is a M × K matrix such that for all k ∈ X , M b=1 O(b, k)ϕ b ∈ F; • M (π,Q,O) ∈ R M ×M ×M is defined by M (π,Q,O) (•, b, •) = ODiag[π]QDiag[O(b, •)]QO for all b ∈ [M ]. [Step 3] Consider the emission densities estimators f (M ) := ( f (M ) k ) k∈X defined by for all k ∈ X , f (M ) k := M b=1 Ô(b, k)ϕ b .
where g * = g π * ,Q * ,f * . Since the bias does not depend on the function t, one can hope that the minimizers of γ n are close to minimizers of t -g * 2 . We will show that this is indeed the case.

The least squares estimators of all HMM parameters are defined for each model

P M by (π (M ) , Q(M) , f (M ) ) ∈ arg min π∈∆, Q∈Q, f ∈(P M ∩F ) K γ n (g π,Q,f ).
The procedure is summarized in Algorithm 2. Note that with the notations of the algorithm,

γ n (g π,Q,O Φ ) = M (π,Q,O) -MM 2 F -MM 2 F .
Then, the proof of the oracle inequality of Lehéricy (to appear) allows to get the following result.

Theorem 9 Assume [HF], [HX] and [Hid] hold.

Then there exists constants C and n 0 depending on C F ,2 , C F ,∞ and Q * such that for all n ≥ n 0 , for all t > 0, with probability greater than 1 -e -t , one has for all M ∈ M such that M ≤ n:

ĝπ (M ) , Q(M) , f (M ) -g π * ,Q * ,f * ,(M ) 2 2 ≤ C t n + M log(n) n .
In order to deduce a control of the error on the parameters-and in particular on the emission densities-from the previous result, we will need to assume that the quadratic form derived from the second-order expansion of (π,

Q, f ) ∈ ∆ × Q × F K -→ g π,Q,f -g * 2 2 around (π * , Q * , f * ) is nondegenerate.
It is still unknown whether this nondegeneracy property is true for all parameters (π * , Q * , f * ) such that [Hid] and [HX] hold. De [START_REF] De Castro | Minimax adaptive estimation of nonparametric hidden Markov models[END_REF] prove it for K = 2 hidden states when only the emission densities are allowed to vary by using brute-force computations. To do so, they introduce an (explicit) polynomial in the coefficients of π * , Q * and of the Gram matrix of f * and prove that its value is nonzero if and only if the quadratic form is nondegenerate for the corresponding parameters. The difficult part of the proof is to show that this polynomial is always nonzero.

For the expression of this polynomial-which we will write H-in our setting, we refer to Section B.3. Note that Lehéricy (to appear) proves that this polynomial H is non identically zero: it is shown that there exists parameters (π, Q, f ) satisfying [HX] and [Hid] such that H(π, Q, f ) = 0, which means that the following assumption is generically satisfied:

[Hdet] H(π * , Q * , f * ) = 0.
The following result allows to lower bound the L 2 error on the density of three consecutive observations by the error on the parameters of the HMM using this condition. It is an improvement of Theorem 6 of De Castro et al. ( 2016) and Theorem 9 of Lehéricy (to appear). The main difference is that the constant c * (π * , Q * , f * , F) does not depend on the f around which the parameters are taken. This is crucial to obtain Corollary 11, from which we will deduce [H0]. Note that we do not need f to be in a compact neighborhood of f * . Another improvement is that the constant in the minoration only depends on the true parameters and on the set F.

Theorem 10

1. Assume that [HF] holds and that for all f ∈ F, f dµ = 1.

Then there exist a lower semicontinuous function

(π * , Q * , f * ) -→ c * (π * , Q * , f * , F)
that is positive when [Hid] and [Hdet] hold and a neighborhood V of f * in F K depending only on π * , Q * , f * and F such that for all f ∈ V and for all π ∈ ∆,

Q ∈ Q and h ∈ F K , g π,Q,h -g π * ,Q * ,f 2 2 ≥ c * (π * , Q * , f * , F)d perm ((π, Q, h), (π * , Q * , f )) 2 .
2. There exists a continuous function

: (π * , Q * , f * ) → (π * , Q * , f * ) that is positive when [Hid] and [Hdet] hold and such that for all π ∈ ∆, Q ∈ Q and h ∈ (L 2 (Y, µ)) K a K-uple of probability densities such that d perm ((π, Q, h), (π * , Q * , f * )) ≤ (π * , Q * , f * ), one has g π,Q,h -g π * ,Q * ,f * 2 2 ≥ c 0 (π * , Q * , f * )d perm ((π, Q, h), (π * , Q * , f * )) 2 .
where

c 0 (π * , Q * , f * ) = (inf k∈X π * (k)) σ K (Q * ) 4 σ K (G(f * )) 2 4 ∧ H(π * , Q * , f * ) 2(1 ∧ K G(f * ) ∞ )(3K 3 (1 ∨ G(f * ) 4 ∞ )) K 2 -K/2 .
Proof Proof in Section B.4.

Corollary 11 Assume [HX], [HF],

[Hid] and [Hdet] hold. Also assume that for all f ∈ F, f dµ = 1.

Then there exists a constant n 0 depending on C F ,2 , C F ,∞ and Q * and constants M 0 and C depending on F, Q * and f * such that for all n ≥ n 0 and t > 0, with probability greater than 1 -e -t , one has for all M ∈ M such that M 0 ≤ M ≤ n:

inf τ ∈S(K) max k∈X f (M ) k -f * ,(M ) τ (k) 2 2 ≤ C M log(n) n + t n .
Remark 12 Using the second point of Theorem 10, one can alternatively take n 0 and M 0 depending on F, Q * and f * , and C depending on C F ,2 , C F ,∞ , Q * and f * only. For instance, one can take C = C/c 0 (π * , Q * , f * ) with the notations of Theorems 9 and 10.

In particular, this means that the asymptotic variance bound of the least squares estimators (and therefore the rate of convergence of the estimators selected by our state-by-state selection method) does not depend on the set F, but only on the HMM parameters and on the bounds C F ,2 and C F ,∞ on the square and supremum norms of the emission densities. Note that this universality result is essentially an asymptotic one since it requires n 0 to depend on F in a non-explicit way.

Proof Let V be the neighborhood given by Theorem 10, then there exists M 0 such that for all M ≥ M 0 , f * ,(M ) ∈ V. Then Theorem 9 and Theorem 10 applied to π = π(M) , Q = Q(M) , h = f (M ) and f = f * ,(M ) for all M allow to conclude.

We may now state the following result which shows that the state-by-state selection method applied to these estimators reaches the minimax rate of convergence (up to a logarithmic factor) in an adaptive manner under generic assumptions. Its proof is the same as the one of Corollary 6.

Corollary 13 Assume [HX], [HF],

[Hid] and [Hdet] hold. Also assume that for all f ∈ F, f dµ = 1 and that for all k, there exists

s k such that f * ,(M ) k -f * k 2 = O(M -s k ).
Then there exists a constant C σ depending on C F ,2 , C F ,∞ , Q * and f * such that the following holds.

Let C ≥ C σ and let f sbs be the estimators selected from the family ( f (M ) ) M ≤n with

σ(M ) = C M log(n)
n for all M , aligned like in Remark 7. Then there exists a random permutation τ which does not depend on n such that

∀k ∈ X , E f sbs τ (k) -f * k 2 = O   n log(n) -s k 2s k +1   .

Numerical experiments

This section is dedicated to the discussion of the practical implementation of our method. We run the spectral estimators on simulated data for different number of observations and study the rate of convergence of the selected estimators for several variants of our method. Finally, we discuss the algorithmic complexity of the different estimators and selection methods.

In Section 4.1, we introduce the parameters with which we generate the observations. In Section 4.2, we discuss how to calibrate the constant of the penalty in practice. In Section 4.3, we introduce two other ways to select the final estimators, the POS and MAX variants. Section 4.4 contains the results of the simulations for each variant and calibration method. In Section 4.5, we present a cross validation procedure and compare its results with the one obtained using our method. Finally, we discuss the algorithmic complexity of the different algorithms and estimators in Section 4.6.

Setting and parameters

We take Y = [0, 1] equipped with the Lebesgue measure. We choose the approximation spaces spanned by a trigonometric basis:

P M := Span(ϕ 1 , . . . , ϕ M ) with      ϕ 1 (x) = 1 ϕ 2m (x) = √ 2 cos(2πmx) ϕ 2m+1 (x) = √ 2 sin(2πmx)
for all x ∈ [0, 1] and m ∈ N * . We will consider a hidden Markov model with K = 3 hidden states and the following parameters:

• Transition matrix

Q * =  
0.7 0.1 0.2 0.08 0.8 0.12 0.15 0.15 0.7   ;

• Emission densities (see Figure 1)

-Uniform distribution on [0; 1];

-Symmetrized Beta distribution, that is a mixture with the same weight of 2 3 X and 1 -1 3 X with X, X i.i.d. following a Beta distribution with parameters (3, 1.6); -Beta distribution with parameters (3, 7).

We generate n observations and run the spectral algorithm in order to obtain estimators for the models P M with M_min ≤ M ≤ M_max, m = 20 and r = 2 log(n) + 2 log(M ) , where M_min = 3 and M_max = 300. Finally, we use the state-by-state selection method to choose the final estimator for each emission density. The main reason for using spectral estimators instead of maximum likelihood estimation or least squares estimation is its computational speed: it is much faster for large n than the least squares algorithm or the EM algorithm, which makes studying asymptotic behaviours possible.

We made 300 simulations, 20 per value of n, with n taking values in {5 × 10 4 , 7 × 10 4 , 1 × 10 5 , 1.5 × 10 5 , 2.2 × 10 5 , 3.5 × 10 5 , 5 × 10 5 , 7 × 10 5 , 1 × 10 6 , 1.5 × 10 6 , 2.2 × 10 6 , 3.5 × 10 6 , 5 × 10 6 , 7 × 10 6 , 1 × 10 7 }.

Penalty calibration

It is important to note that when considering spectral and least squares methods, the penalty σ in the state-by-state selection procedure depends on the hidden parameters of the HMM and as such is unknown in practice. This penalty calibration problem is well known and several procedures exist that allow to solve it, for instance the slope heuristics and the dimension jump method (see for instance [START_REF] Baudry | Slope heuristics: overview and implementation[END_REF] and references therein). In the following, we will use the dimension jump method to calibrate the penalty in the state-by-state selection procedure. Consider a penalty shape pen shape and define Mk (ρ) the model selected for the hidden state k by the state-by-state selection estimator using the penalty ρ pen shape :

Mk (ρ) ∈ arg min M ∈M {A k (M ) + 2ρ pen shape (M )}.
where

A k (M ) = sup M ∈M f (M ) k - f (M ∧M ) k 2 -ρ pen shape (M ) .
The dimension jump method relies on the heuristics that there exists a constant C such that C pen shape is a minimal penalty. This means that for all ρ < C, the selected models Mk (ρ) will be very large, while for ρ > C, the models will remain small. This translates into a sharp jump located around a value ρ jump,k = C in the plot of ρ -→ Mk (ρ). The final step consists in taking twice this value to calibrate the constant of the penalty, thus selecting the model M (2ρ jump,k ). In practice, we take ρ jump,k as the position of the largest jump of the function ρ -→ Mk (ρ).

Figure 2 shows the resulting dimension jumps for n = 220, 000 observations. Each curve corresponds to one of the Mk (ρ) and has a clear dimension jump, which confirms the relevance of the heuristics. Several methods may be used to calibrate the constant of the penalty:

eachjump. Calibrate the constant independently for each state. This method has the advantage of being easy to calibrate since there is usually a single sharp jump in each state's complexity. However, our theoretical results do not suggest that the penalty constant is different for each state;

jumpmax. Calibrate the constant for all states together using only the latest jump. This consists in taking the maximum of the ρ jump,k to select the final models. Since the penalty is known up to a multiplicative constant and taking a constant larger than needed does not affect the rates of convergence-contrary to smaller constants-this is the "safe" option;

jumpmean. Calibrate the constant for all states together using the mean of the positions of the different jumps.

We try and compare these calibration methods in Section 4.4.

Alternative selection procedures

Variant POS.

As mentionned in Section 2.2, it is also possible to select the estimators using the criterion

A k (M ) = sup M ≥M f (M ) k - f (M ) k 2 -σ(M ) + followed by Mk ∈ arg min M ∈M {A k (M ) + 2σ(M )}.
This positivity condition was in the original Goldenshluger-Lepski method. The theoretical guarantees remain the same as the previous method and both behave almost identically in practice, as shown in Section 4.4.

Variant MAX.

In the context of kernel density estimation, [START_REF] Lacour | Estimator selection: a new method with applications to kernel density estimation[END_REF] show that the Goldenshluger-Lepski method still works when the biais estimate A k (M ) of the model M is replaced by the distance between the estimator of the model M and the estimator with the smallest bandwidth (the analog of the largest model in our setting). They also prove an oracle inequality for this method after adding a corrective term to the penalty.

The following variant is based on the same idea. It consists in selecting the model Mk ∈ arg min for each k ∈ X and takes fk

M ∈M { f (Mmax) k - f (M ) k 2 + σ(M )}
= f ( Mk ) k ,
where σ is the same penalty as the one in the usual state-by-state selection method. An advantage of this algorithm is its lower complexity, since it requires O(M max ) computations of L 2 norms instead of O(M 2 max ). We do not study this method theoretically in our setting. However, the simulations (and in particular Figure 4) show that it behaves similarly to the standard state-by-state selection method in the asymptotic regime and even has a smaller error for small number of observations. In addition, the dimension jumps are much sharper for this method than for the usual state-by-state selection method (see Figure 2), which makes the calibration heuristics easier to use.

Results

Figure 3 shows the evolution of the error fk -f * k 2 for each state k with respect to the number of observations n, for all penalty calibration methods and all variants of the model selection procedure. Figure 4 compares the evolution of the median error for the different calibration methods and for the different selection variants, and Figure 5 compares two estimators with the oracle estimators.

When the number of observations n is large enough, the logarithm of the error decreases linearly with respect to log(n). This corresponds to the asymptotic convergence regime: the error is expected to decrease as a power of the number of observations n when n tends to infinity. The corresponding slopes are listed in Table 1.

For each state, the confidence intervals of the rates of all estimators-including the oracle estimators-have a common intersection (except for the symmetrized Beta distribution in the jumpmax MAX variant, whose estimators seem to converge faster than the others). This tends to confirm that the calibration and selection variants are asymptotically equivalent. This phenomenon is also visible in Figures 3 and4: in the asymptotic regime, the errors decrease in a similar way for all methods.

Furthermore, the rates of convergence are clearly distinct. The uniform distribution is estimated with a rate of convergence of approximately n -1/2 , which is also the best possible rate (it corresponds to a parametric estimation rate). In comparison, the rate of convergence for the symmetrized Beta distribution is much slower (around n -0.36 ). This shows that the algorithm effectively adapts to the regularity of each state and that one irregular emission density does not deteriorate the rates of convergence of the other densities.

Note that the above rates are in accordance with the minimax rates as far as the Hölder regularity is concerned. The minimax Hölder rate for the symmetrized Beta (which is 0.6-Hölder) is n -3/11 , or approximately n -0.27 , which means our estimator converges faster than the minimax rate would suggest. The minimax Hölder rate for the Beta distribution (which is 3-Hölder) is n -3/7 , or approximately n -0.43 , which is around the observed value.

Comparison with cross validation

In this section, we use a cross validation procedure based on our spectral estimators to check whether our method actually improves estimation accuracy.oe When estimating a density by taking an estimator within some class (the model), two sources of error appear: the bias, that is the (deterministic) distance between the true Each color corresponds to one emission density. In Subfigures (a)-(c), the full lines correspond to the basic selection method, the dashed ones to the POS method and the dotted ones to the MAX method. In Subfigures (d)-(f), the full lines correspond to the eachjump method, the dashed ones to the jumpmax method and the dotted ones to the jumpmean method.

density and the model, and the variance, that is the (random) error of the estimation within the model. Small models will have a large bias but a small variance, while large models will have a small bias and a large variance. The core issue of model selection is to select a model that minimizes the total error, that is large enough to accurately describe the true densities and small enough to prevent overfitting: in other words, perform a bias-variance tradeoff.

Cross validation seeks to achieve such a tradeoff by computing an estimate of the total error. This is done by splitting the sample into two sets, the training sample being used for the calibration of the estimator and the validation sample for measuring the error. Figure 5: Comparison of the errors for the eachjump MAX method (full lines), for the eachjump method (dashed lines) and for the oracle estimators (dotted lines).

For each k, the oracle estimator is defined as

f (M oracle k ) k where M oracle k minimizes M -→ f (M ) k -f * k 2 .
The oracle corresponds to the best estimator one could possibly select among the preliminary estimator if the true densities were known.

Taking the mean of these errors for different splits between training and validation samples provides an estimator of the total error. This method has become popular for its simplicity of use. We refer to the survey of [START_REF] Sylvain Arlot | A survey of cross-validation procedures for model selection[END_REF] for an overview on this method and its guarantees.

Risk

We use the least squares criterion of Algorithm 2 to quantify the error of the estimators. Since the guarantees on spectral estimators rely on the L 2 norm, a least squares criterion is more natural than the likelihood. In addition, the spectral estimators might take negative values depending on the orthonormal basis, which is not a problem as far as L 2 error is concerned but can be an issue for the likelihood.

Let us first recall this criterion. Given an orthonormal basis (ϕ i ) i∈N of L 2 (Y, µ), define the coordinate tensor of the empirical distribution of the triplet (Y 1 , Y 2 , Y 3 ) on this basis by

M(a, b, c) := 1 n n s=1 ϕ a (Y s )ϕ b (Y s+1 )ϕ c (Y s+2 ) for all a, b, c ∈ N.
Given a transition matrix Q of size K, a stationary distribution π of Q and a vector of

densities f = (f 1 , . . . , f K ), define the coordinate matrix O of f by O(b, k) = ϕ b , f k . Let M (π,Q,f ) be the coordinate tensor of the distribution of (Y 1 , Y 2 , Y 3 ) under the parameters (π, Q, f ), that is M (π,Q,f ) (•, b, •) = ODiag[π]QDiag[O(b, •)]QO
for all b ∈ N. criterion for the estimated parameters using the segment I j as observed sample. Finally, for each M , we average this error on all segments I j , which gives the least squares cross validation error E VC (M ).

This cross validation criterion is used to select one model MVC ∈ arg min M E VC (M ), from which we construct the final estimators of the emission densities fk = f ( MVC ) k for all k. Note that the selected model is the same for all emission densities.

Results

Figure 6 compares the selected model dimensions for each n using our state-by-state selection method and using the cross validation method. When the number of observations n becomes larger than 10 6 , the cross validation tends to always pick the largest model, which means that it does not prevent overfitting as well as our method.

The L 2 errors on the emission densities are shown in Figure 7. It appears that the cross validation has a lower error for small n (n ≤ 350, 000) than our method. However, for larger values of n, the errors becomes larger than the ones of our method (see Figure 5) by up to one order of magnitude, and only start decreasing once the selected model is set to the maximum dimension.

Finally, the estimated rates of convergence are shown in Table 1. Our state-by-state method outperforms the cross validation method for all emission densities. The cross validation estimators only reach the minimax rate of convergence for the less regular density: the symmetrized Beta, and even then they converge slower than the state-by-state estimator. All other emission densities are estimated slower than their minimax rate.

Algorithmic complexity

In the following, we treat K as a constant as far as the algorithmic complexity is concerned.

The different complexities are summarized in Table 2.

Spectral algorithm (see Section 3.2)

We consider the algorithmic complexity of estimating the emission densities for all models M such that M min ≤ M ≤ M max with n observations and auxiliary parameters r and m depending on n and M (upper bounded by m max and r max ).

Step 1 can be computed for all models with O(nM max m 2 max ) operations. It is the only step whose complexity depends on n. Steps 2 and 3 require O(m 3 M ) operations for each model and Steps 4 to 7 require O(M r) operations for each model, for a total of O(nM max m 2 max + M 2 max m 3 max + M 2 max r max ) operations. In practice, one takes m ∝ log(n), r ∝ log(n) + log(M ) and M max ≤ n, so that the total complexity of the spectral algorithm is O(n log(n) 2 M max ).

In comparison, the complexity of the spectral algorithm of De Castro et al. ( 2017) is O(nM 3 max ) because of Step 1. This becomes much larger than our complexity when M max grows as a power of n (which is necessary in order to reach minimax rates).

Least squares algorithm (see Section 3.3)

We consider the algorithmic complexity of estimating the emission densities for all models M such that M min ≤ M ≤ M max with n observations.

Step 1 is similar to the one of the spectral algorithm, but with O(nM 3 max ) operations. The complexity of Step 2 is more difficult to evaluate. Since the criterion is nonconvex, finding the minimizer requires to run an approximate minimization algorithm whose complexity C n will depend on the desired precision-which will in turn depend on the number of observations n-and on the initial points. As discussed in Lehéricy (to appear), this is usually the longest step when computing least squares estimators. Thus, the total complexity of the least squares algorithm is O(nM 3 max + C n ). Note that despite the worse sample complexity, the least squares algorithm is tractable and can greatly improve the estimation for small sample size. As shown in Section 4.4, the spectral algorithm is unstable for small samples, which makes the state-by-state selection procedure return abnormal results. This can be explained by the matrix inversions of the spectral method, which sometimes lead to nearly singular matrices when the noise is too large. On the other hand, the least squares method does not involve any matrix inversion, and often gives better results than the spectral estimators, as shown in De Castro et al. ( 2016), thus making it a relevant choice for small to medium data sets.

Selection method and POS variant (see Sections 2.2 and 4.3)

We consider the algorithmic complexity of selecting estimators from a family ( f (M ) ) M min ≤M ≤Mmax of estimators. The selection algorithms can be decomposed in two parts.

• Compute the distances f (M ) k - f (M )
k 2 for all M , M and k. This has complexity O(M 3 max ): it requires to compute the L 2 distance of at most M 2 max couples of functions in a Hilbert space of dimension M max .

• Compute ρk defined as the abscissa of the largest jump of the function ρ -→ Mk (ρ) for all k, where Mk is defined as in Section 4.2. Note that computing Mk (ρ) requires O(M 2 max ) operations. An approximate value of ρk can be computed in O(log(ρ k )M 2 max ) operations, which is usually O(M 2 max ).

Once the ρk are known, it is possible to calibrate the penalty in constant time for the three calibrations methods (eachjump, jumpmax and jumpmean) and to select the final models in O(M 2 max ) operations. Thus, the total complexity of the selection algorithm and of its POS variant is O(M 3 max ).

Selection method, MAX variant (see Section 4.3)

In the MAX variant, the first step of the standard selection procedure is replaced by computing the distances

f (Mmax) k - f (M )
k 2 for all M . This has complexity O(M 2 max ). The complexity of the other steps remains unchanged.

Thus, the total complexity of the MAX variant of the selection algorithm is O(M 2 max ).

Algorithm Complexity

Preliminary estimators

Spectral method O(n log(n) 2 M max ) Spectral method (De Castro et al. ( 2017
)) O(nM 3 max ) Least squares method O(nM 3 max + C n ) Selection step Standard and POS variant O(M 3 max ) MAX variant O(M 2 max )
Table 2: Complexities of the different algorithms. n is the number of observations, M max is the largest model dimension considered.

Application to real data

In this section, we present the results of our method on two sets of trajectories. Trajectories are a typical example of dependent data that shows several behaviours depending on the activity of the entity being tracked, which makes hidden Markov models a popular modelling choice. For instance, the movement of a fisher is not the same depending on whether he's travelling to the next fishing zone or actually fishing.

The first data set follows artisanal fishers in Madagascar. The second one contains seabird movements. Studying the movements of fishers and seabirds has many applications, for instance understanding the fishing habits of the tracked entity, controlling the fishing pressure on local ecosystems and monitoring the dynamics of coastal ecosystems, see for instance [START_REF] Boyd | Movement models provide insights into variation in the foraging effort of central place foragers[END_REF]; [START_REF] Vermard | Identifying fishing trip behaviour and estimating fishing effort from VMS data using Bayesian hidden Markov models[END_REF] and references therein.

Artisanal fishery

We use GPS tracks of artisanal fishers with a regular sampling period of 30 seconds. These tracks were produced by Faustinato Behivoke (Institut Halieutiques et des Sciences Marines, Université de Toliara, Madagascar) and Marc Léopold (IRD), who recorded artisanal fishers from Ankilibe, in Madagascar. Their fishing method is a seine netting.

From this data, we compute the velocity of the fisher during each time step. In order to estimate densities on [0, 1], we divide this velocity by an upper bound of the maximum observed velocity. We consider the observation space Y = [0, 1] endowed with the dominating measure δ 0 + Leb, where δ 0 is the dirac measure in zero and Leb is the Lebesgue measure on [0, 1]. As a proof of concept, we use the orthonormal basis consisting of the trigonometric basis on [0, 1] and the indicator function of {0}, that is the family (ϕ m ) m∈N defined on [0,1] by

if x = 0, ϕ 0 (x) = 1 ϕ m (x) = 0 for all m ∈ N * if x = 0,            ϕ 0 (x) = 0 ϕ 1 (x) = 1 ϕ 2m (x) = √ 2 cos(2πmx) for all m ∈ N * ϕ 2m+1 (x) = √ 2 sin(2πmx) for all m ∈ N *
The number of hidden states is chosen using the spectral thresholding method of Lehéricy (to appear). This methods consists is based on the fact that the rank of the spectral tensor E Nm,m (with the notations of Algorithm 3 in Appendix A) is the number of hidden states. This is visible in the spectrum of Nm,m by an elbow, as shown in Figure 8. Based on these spectra, we use two hidden states.

The results using M_max = 1000 are shown in Figures 9 and10. We took the normalizing velocity large enough that all observed normalized velocities belong to [0, 0.8], hence the plot betweeen 0 and 0.8 for the densities.

In both cases, the selected model complexities differ greatly depending on the state. This comes from the fact that in both cases, one of the density is spiked, thus requiring more vectors of the orthonormal basis to be approximated. This illustrates that our method is able to estimate the smoother densities with fewer vectors of the basis, thus preventing overfitting.

As a side note, we needed considerably less observations than in the simulations: around 10,000, compared to 500,000 in the simulations. This can be explained by the fact that each state is very stable, with an estimated probability of leaving the states below 0.02-compared to 0.3 in the simulations. This is encouraging, as hidden states in real data are expected to be rather stable, especially when the sampling frequency is high, as long as the conditional independance of the observations can be assumed to hold.

Seabird foraging

In this Section, we consider the seabird data from [START_REF] Bertrand | Generalized Pareto for pattern-oriented random walk modelling of organisms' movements[END_REF] and we focus on the tracks named cormorant d in this paper.

We apply the same transformation as in the previous section to obtain normalized velocities in [0, 0.8] (after removal of anomalous velocities exceeding 150 m/s) and run the spectral algorithm with the trigonometric basis on [0, 1] plus the indicator of {0}. The spectral thresholding gives a number of hidden states equal to two; we set it to three to account for more complex behaviours of the seabirds. The results are shown in Figure 11.

Note that the use of the trigonometric basis allows the estimated densities to take negative values. This is not a problem as far as minimax rates of convergence (in L 2 norm) are concerned, however this can become an issue if one wants to use these densities in a forward-backward algorithm in order to get an estimator of the hidden states. One way to circumvent this problem is to use simplex projection to compute an approximation of the projection of these estimated density on the simplex of all probability densities. Note that since this is an L 2 projection on a convex set which contains the true densities, the projected densities have an even smaller error, thus keeping the minimax rate of convergence of the original estimators. The resulting densities are shown in Figure 12 The number of observations in this setting is even smaller than for the fishery's data set: our algorithm was able to recover three emission densities from less than 3,000 observations, despite the states being less stable than in the fishery data set: the diagonal terms of the estimated transition matrix using the EM algorithm are (0.83, 0.93, 0.98). In addition, the result of our method is consistent with other estimation methods, as shown in Figure 12: estimating the parameters with the EM algorithm using piecewise constant densities leads to a very similar result.

Conclusion and perspectives

We propose a state-by-state selection method to infer the emission densities of a HMM. Using a family of estimators, our method selects one estimator for each hidden state in a way that is adaptive with respect to this state's regularity. This method does not depend on the type of preliminary estimator, as long as a suitable variance bound is available. As such, it may be seen as a plug-in that takes a family of estimators and the corresponding variance bound and outputs the selected estimator. Note that its complexity does not depend on the number of observations used to compute the estimators, which makes it applicable to arbitrarily large data sets.

To apply this method, we present two families of estimators: a least squares estimator and a spectral estimator. For both, we prove a bound on their variance and show that this bound allows to recover the minimax rate of convergence separately on each hidden state, up to a logarithmic factor. The variance bounds are similar to a BIC penalty, with an additional logarithmic factor for the spectral estimators.

We carry out a numerical study of the method and some variants on simulated data. We use the spectral estimators, which are both fast and don't suffer from initialization issues, unlike the least squares and maximum likelihood estimators. The simulations show that our selection method is very fast compared to the computation of the estimators and that indeed, the final estimators reach the minimax rate of convergence on each state.

Then, we compare our method with a cross validation estimator based on a least square risk. This estimator only reaches the minimax rate corresponding to the worst regularity among the emission densities and fails to select models with small dimensions. It is still noteworthy that the cross validation returns relevant results for small sample sizes, whereas our method requires the sample size to be large enough to work properly. An interesting problem would be to investigate whether cross validation or other methods can be combined with our state-by-state selection method to give an algorithm that is both fast, stable for small sample sizes and optimal in the asymptotic setting.

Finally, we apply our algorithm to real trajectory data sets. On this data, our method proves that it is able to match the regularity of the underlying emission densities. In addition, it is able to produce sensible results with far fewer observations than in our simulation study.

Our state-by-state selection method can be easily applied to multiview mixture models (also named mixture models with repeated measurement, see for instance Bonhomme et al. (2016a) and [START_REF] Gassiat | Efficient semiparametric estimation and model selection for multidimensional mixtures[END_REF]). Let us first describe the model. A multiview mixture model consists of two random variables, a hidden state U and an observation vector Y := (Y i ) i∈ [m] such that conditionally to U , the components Y i of Y are independent with a distribution depending only on U and i. Let us assume that U takes its values in a finite set X of size K and that the Y i have some density f * u,i conditionally to U = u with respect to a dominating measure. A question of interest is to estimate the densities f * u,i from a sequence of observed (Y n ) n≥1 .

Our state-by-state selection method can be applied directly to such a model as long as estimators with a proper variance bound are available (see assumption [H( )] in Section 2.1). Indeed, we never use the dependency structure of the model. Regarding the development of preliminary estimators, multiview mixture models appear closely related to hidden Markov models: [START_REF] Anandkumar | A method of moments for mixture models and hidden Markov models[END_REF] and Bonhomme et al. (2016b) develop spectral methods that work for both multiview mixtures and HMMs at the same time using the same theoretical arguments. Thus, it seems clear that variance bounds such as the ones we developed can also be written for multiview mixture models.

Let M ∈ M. Let us show that f (M )

τ -1 n,M (k ) - f (M 0 ) τ -1 n,M 0 (k) 2 > f (M ) τ -1 n,M (k) - f (M 0 ) τ -1 n,M 0 (k) 2 for all k, k ∈ X such that k = k. If this holds, then the definition of τ (M ) implies that τ (M ) = τ -1 n,M • τ n,M 0 . Thus, one has max k∈X f (M ) k,new -f * ,(M ) τ n,M 0 (k) 2 ≤ σ(M ) 2 , which is exactly Equation (1) with τ n = τ n,M 0 .
Applying the triangular inequality leads to

f (M ) τ -1 n,M (k) - f (M 0 ) τ -1 n,M 0 (k) 2 ≤ f (M ) τ -1 n,M (k) -f * ,(M ) k 2 + f * ,(M ) k -f * ,(M 0 ) k 2 + f * ,(M 0 ) k - f (M 0 ) τ -1 n,M 0 (k) 2 ≤ σ(M ) 2 + B M,M 0 + σ(M 0 ) 2 and f (M ) τ -1 n,M (k ) - f (M 0 ) τ -1 n,M 0 (k) 2 ≥ f * ,(M 0 ) k -f * ,(M 0 ) k 2 - f (M ) τ -1 n,M (k ) -f * ,(M ) k 2 -f * ,(M ) k -f * ,(M 0 ) k 2 -f * ,(M 0 ) k - f (M 0 ) τ -1 n,M 0 (k) 2 ≥m(f * , M 0 ) - σ(M ) 2 -B M,M 0 - σ(M 0 ) 2 .
Thus, the result holds as soon as m

(f * , M 0 )-σ(M ) 2 -B M,M 0 -σ(M 0 ) 2 > σ(M ) 2 +B M,M 0 + σ(M 0 )
2 , which is the condition of Lemma 1.

B.2 Proof of Theorem 5

The structure of the proof is the same as the one of Theorem 3.1 of De [START_REF] De Castro | Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models[END_REF].

The first difference lies in the fact that we consider different models for each component of the tensors Nm,M and Mm,M,m in Step 1. As a consequence, we use the left and right singular vectors of Nm,M instead of just the right singular vectors of Pm,m . A careful reading shows that their proof can be adapted straightforwardly to this situation.

The second difference consists in generating several independant random unitary matrices in Step 4 and keeping the one that separates the eigenvalues of all Ĉi (k) best. This allows to replace Lemma F.6 of De Castro et al. ( 2017) by the following one, based on the independence of the unitary matrices:

Lemma 14 For all x > 0 and r ∈ N * ,

P ∀k, k 1 = k 2 , | Λi 0 (k, k 1 ) -Λi 0 (k, k 2 )| ≥ 2e -x/r (1 -2 N m,M ) 1/2 √ eK 5/2 (K -1) γ(O M ) ≥ 1 -e -x and P Λi 0 ∞ ≥ 1 + √ 2 x + log(K 2 r) √ K O M 2,∞ ≤ e -x ,
The notations N m,M (or

P M in the original proof ), γ(O M ) et O M 2,∞ are introduced in De Castro et al. (2017).
Using this lemma, their proof leads to our result by taking r = x = t.

The proof is the same for q and A.

The next lemma will be used to link the norms of A and Af .

Lemma 16 For all Ā ∈ R K×K and f

* ∈ (L 2 (Y, µ)) K , σ K (G(f * )) Ā 2 F ≤ k∈X ( Āf * ) k 2 2 ≤ K G(f * ) ∞ Ā 2 F
Proof For the first inequality, we use that for all k ∈ X ,

( Āf * ) k 2 2 = Ā(k, •)G(f * ) Ā(k, •) ≥σ K (G(f * )) Ā(k, •) 2 2
and the inequality follows by summing over k.

For the second inequality,

k∈X ( Āf * ) k 2 2 = k∈[K] ( Āf * ) k (x) 2 µ(dx) = k∈[K]   j∈[K] Ā(k, j)f * j (x)   2 µ(dx) ≤ k∈[K] K j∈[K] Ā(k, j) 2 (f * j ) 2 (x)µ(dx) ≤K   k,j∈[K] Ā(k, j) 2   sup j∈X (f * j ) 2 (x)µ(dx) =K Ā 2 F G(f * ) ∞ .
Finally, we will use the following result of Lehéricy (to appear) (Section B.2) in order to upper bound the spectrum of the matrix M .

Lemma 17 For all π 1 , π

2 ∈ ∆, for all Q 1 , Q 2 ∈ Q and for all f 1 , f 2 ∈ (L 2 (Y, µ)) K , g π 1 ,Q 1 ,f 1 -g π 2 ,Q 2 ,f 2 2 ≤ 3K( G(f 1 ) 3 ∞ ∨ G(f 2 ) 3 ∞ )d perm ((π 1 , Q 1 , f 1 ), (π 2 , Q 2 , f 2 ))
Together, these results imply that for all (p, q, A),

g π * +p,Q * +q,f * + Āf * -g π * ,Q * ,f * 2 2 ≤3K( G(f * + Āf * ) 3 ∞ ∨ G(f * ) 3 ∞ )( p 2 2 + q 2 F + k∈X ( Āf ) k 2 F ) ≤3K G(f * ) 3 ∞ (1 + K 2 A 2 F ) 3 (K p 2 2 + K q 2 F + K 2 G(f * ) ∞ A 2 F ) so that σ 1 (M ) ≤ √ 3K 3 (1 ∨ G(f ) 2 ∞ ). Since H = (K-1)(2K+1) i=1 σ i (M ), one has σ (K-1)(2K+1) (M ) ≥ H (3K 3 (1 ∨ G(f ) 4 ∞ )) K 2 -K/2 . Now, assume that [Hid] holds, so that σ K (G(f * )) > 0, then g π * +p,Q * +q,f * + Āf * -g π * ,Q * ,f * 2 2 ≥ σ (K-1)(2K+1) (M )( p 2 2 + q 2 F + A 2 F ) + o( p 2 2 + q 2 F + A 2 F ) ≥ σ (K-1)(2K+1) (M ) 1 ∧ K G(f * ) ∞ p 2 2 + q 2 F + k∈X ( Āf * ) k 2 F + o 1 1 ∧ σ K (G(f * )) p 2 2 + q 2 F + k∈X ( Āf * ) k 2 F
and finally

g π * +p,Q * +q,f * + Āf * -g π * ,Q * ,f * 2 2 ≥ c 2 (π * , Q * , f * ) p 2 2 + q 2 F + k∈X ( Āf * ) k 2 F + o p 2 2 + q 2 F + k∈X ( Āf * ) k 2 F (4) where c 2 (π * , Q * , f * ) = H (1 ∧ K G(f * ) ∞ )(3K 3 (1 ∨ G(f * ) 4 ∞ )) K 2 -K/2
is positive as soon as [Hid] and [Hdet] hold.

B.4 Proof of Theorem 10

Let

N f (p, q, h) = g π * +p,Q * +q,f +h -g π * ,Q * ,f 2 2 and (p, q, h) 2 f = d perm ((π * + p, Q * + q, f + h), (π * , Q * , f )) 2 .
We want to show that there exists a constant c * > 0 such that there exists a neighborhood V of f * such that if one writes

c f := inf p∈(∆-∆), q∈(Q-Q), h∈(F -F ) K N f (p, q, h) (p, q, h) 2 f then inf f ∈V c f ≥ c * .
The proof follows the structure of the proof of Theorem 6 of De [START_REF] De Castro | Minimax adaptive estimation of nonparametric hidden Markov models[END_REF]. It consists of three steps: the first one controls the component of h that is orthogonal to f . This makes it possible to restrict h to the finite-dimensional space spanned by f in the two other parts. The second step controls the case when h is small, so that the behaviour of N f is given by its quadratic form, and the last step controls the case where h is far from zero. bounded by (inf k (π * k + p k )σ K (Q * + q)) 2 σ K (G(f + u)) and σ K (Q * + q) 2 σ K (G(f + u)). Therefore, their Hadamard product is positive, and one has (((Π Q ) G(f + u)Π Q ) i,j (Q G(f + u)Q ) i,j ) i,j = (DU) (DU) with U an orthogonal matrix and D a diagonal matrix with positive diagonal coefficients. Moreover, the Schur product theorem implies that σ K (D) 2 ≥ (inf k (π * k + p k )) 2 σ K (Q * + q) 4 σ K (G(f + u)) 2 . Then M f (p, q, u, a) ≥

k (π * k + p k )) 2 σ K (Q * + q) 4 σ K (G(f + u)) 2 a 2 2 .
Finally, let c 1 (π * + p, Q * + q, f + u) = (inf k (π * k + p k )) 2 σ K (Q * + q) 4 σ K (G(f + u)) 2 . The application (p, π * , q, Q * , u, f ) → c 1 (π * + p, Q * + q, f + u) is continuous and nonnegative, it is positive when [Hid] holds for the parameters (π * + p, Q * + q, f + u), and one has M f (p, q, u, a) ≥ c 1 (π * + p, Q * + q, f + u) a 2 2 .

We will now control the term N f (p, q, u). Two cases appear: when (π * + p, Q * + q, f + u) is close to (π * , Q * , f * ) in some sense and when it is not. The first case will be solved using the nondegeneracy of the quadratic form ensured by [Hdet]. The second case will be solved using the identifiability of the HMM. B.4.2 In the neighborhood of f * .

The Taylor expansion of (p, q, u) ∈ (∆ -∆) × (Q -Q) × ((F -F) ∩ Span(f )) K → N f (p, q, u) around (0, 0, 0) leads to a nonnegative quadratic form and no linear part. [Hdet], [Hid] and equation (4) ensure that this form is positive for f = f * . Let c 2 (Q * , π * , f ) be as defined in Section B.3.2, then f → c 2 (Q * , π * , f ) is continuous and it is positive in the neighborhood of f * . Moreover, there exists a positive constant η depending on G(f ) ∞ such that for all (p, q, u) such that (p, q, u) f ≤ 1, one has N f (p, q, u) ≥ c 2 (Q * , π * , f ) (p, q, u) 2 f -η (p, q, u) 3 f .

For instance, η = 4000K 6 G(f ) 3 ∞ works: the terms of order 2 or more in the Taylor expansion of N f are the scalar product of sums of terms of the form i,j,k∈X π * (i)Q * (i, j)Q * (j, k)f i ⊗ f j ⊗ f k where zero to three of the f may be replaced by u, zero to two of the Q * by q and π * may be replaced by p and at least one of them is replaced. There are 63 possibilities, which leads to a sum of (63K 3 ) 2 terms, each of which can be bounded by G(f ) 3 ∞ (max{p(i), q(i, j), u i 2 | i, j ∈ X }) r where r is the number of replaced terms. By taking the right permutation of states, the max can be bounded by (p, q, u) f , hence the result.

Then, using (p, q, h) 2 f = (p, q, u) 2 f + a 2 2 leads to N f (p, q, h) (p, q, h) 2 f ≥c 1 (Q * + q, π * + p, f + u) a 2 2 (p, q, u)

2 f + a 2 2 + c 2 (Q * , π * , f ) (p, q, u) 2 f (p, q, u) 2 f + a 2 2 -η (p, q, u) 2 f ( (p, q, u) 2 f + a 2 2 ) 1/2 ≥c 1 (Q * + q, π * + p, f + u) a 2 2 (p, q, u) 2 f + a 2 2 + c 2 (Q * , π * , f ) (p, q, u) 2 f (p, q, u) 2 f + a 2 2 -η (p, q, u) 2 f
Let c 0 = min(c 1 /2, c 2 )/2, then c 0 is continuous and there exists a continuous function (π * , Q * , f ) → (π * , Q * , f ) which is positive as soon as [Hid] and [Hdet] hold for (π * , Q * , f ) and such that

(p, q, u) f ≤ (π * , Q * , f ) ⇒ N f (p, q, h) (p, q, h) 2 f ≥ c 0 (Q * , π * , f ).
Thus, there exists positive constants 0 and c near depending on Q * , π * and f * such that Lemma 18 The application

∀(p, q, h, f ) ∈ (∆ -∆) × (Q -Q) × (F -F) K × F K
(p, q, u, f ) ∈ (∆ -∆) × (Q -Q) × (F -F) K × F K -→ N f (p, q, u)
restricted to the set of (p, q, u, f ) such that u ∈ Span(f ) K is uniformly continuous for the norm • tot defined by

(p, q, u, f ) 2 tot := p 2 2 + q 2 F + k∈X u k 2 2 + f k 2 2 .
Thus, by compactness of (∆ -∆) × (Q -Q) × ((F -F) ∩ Span(f )) K , the application c far : f -→ inf (p,q,u)∈(∆-∆)×(Q-Q)×((F -F )∩Span(f )) K s.t. (p,q,u) f > 0 N f (p, q, u) is continuous. Let us now prove that c far (f * ) > 0. Let (p n , q n , u n ) n ∈ ((∆ -∆) × (Q -Q) × ((F -F) ∩ Span(f * )) K ) N be a sequence such that (p n , q n , u n ) f * > 0 for all n and c far (f * ) = lim n N f * (p n , q n , u n ).

By compactness, this sequences converges towards a limit (p, q, u) up to taking a subsequence. Necessarily (p, q, u) f * ≥ 0 . Since [Hid] holds, Theorem 8 shows that N f * (p, q, u) > 0, which implies c far (f * ) > 0 by continuity of N f * . Note that c far (f * ) may depend on F in addition to the parameters π * , Q * and f * . Thus, by continuity, there exists 1 > 0 such that for all f ∈ F K such that k∈X f kf * k 2 2 ≤ 2 1 , c far (f ) ≥ c far (f * )/2. Finally, [HF] implies that there exists a constant C depending only on C F ,2 such that (p, q, u) 2 f ≤ (p, q, h) 2 f ≤ C for all (p, q, h) ∈ (∆ -∆) × (Q -Q) × (F -F) K . Therefore, ∀(p, q, h, f

) ∈ (∆ -∆) × (Q -Q) × (F -F) K × F K s.t. (p, q, u) f ≥ 0 and k∈X f k -f * k 2 2 ≤ 2 1 , N f (p, q, h) (p, q, h) 2 f ≥ N f (p, q, u) C ≥ c far (f * ) 2C .
The theorem follows by taking c * (π * , Q * , f * , F) = min c far (f * ) 2C , c near and the neighborhood containing all f ∈ F K such that k∈X f k -f * k 2 2 ≤ min( 0 , 1 ) 2 . Moreover, (π, Q, f ) -→ c * (π, Q, f , F) is lower bounded by this value in a neighborhood of (π * , Q * , f * ), so that it can be assumed to be lower semicontinuous.

Note that the dependency of c * on F appears during this last step and is made non explicit because of the compactness assumption.

B.4.4 Proof of Lemma 18

N f (p, q, u)-N f (p , q , u ) = g π * +p,Q * +q,f +u -g π * ,Q * ,f 2 2 -g π * +p ,Q * +q ,f +u -g π * ,Q * ,f 2 2 ≤2 g π * +p,Q * +q,f +u -g π * +p ,Q * +q ,f +u 2 2 + 2 g π * ,Q * ,f -g π * ,Q * ,f 2 2 + 2 g π * +p ,Q * +q ,f +u -g π * ,Q * ,f , g π * +p,Q * +q,f +u -g π * +p ,Q * +q ,f +u + 2 g π * +p ,Q * +q ,f +u -g π * ,Q * ,f , g π * ,Q * ,f -g π * ,Q * ,f

Then, using the fact that g π,Q,f -

g π ,Q ,f 2 ≤ √ 3KC 3 F ,2 (π -π , Q -Q , f -f , 0) tot (see Lemma 17), that g π,Q,f
2 ≤ C 3 F ,2 (see for instance Lemma 29 of Lehéricy (to appear)) and the Cauchy-Schwarz inequality, N f (p, q, u) -N f (p , q , u ) ≤6KC 6 F ,2 (p -p , q -q , f + ufu , 0) 2 tot + 6KC 6 F ,2 (0, 0, 0, ff ) 2 tot + 4

√ 3KC 6 F ,2 (p -p , q -q , f + u -f -u , 0) tot + 4 √ 3KC 6 F ,2 (0, 0, 0, f -f ) 2 tot ≤24KC 6
F ,2 (p -p , q -q , uu , ff ) 2 tot + (p -p , q -q , uu , ff ) tot ,

[

  Step 2] Let Ûm be the m × K matrix of orthonormal left singular vectors of Pm,m corresponding to its top K singular values. Ûm can be seen as a projection. Denote by P and M (•, b, •) the projected tensors, defined by P = Û m Pm,m Ûm and likewise for M . [Step 3] Form the matrices B(b) := (P ) -1 M for all b ∈ [M ]. [Step 4] Construct a matrix Ô by taking the best approximate simultaneous diagonalization of all B(b) among r attempts: for all b

Figure 1 :

 1 Figure 1: Emission densities. In all following figures, the uniform distribution corresponds to the green lines, the Beta distribution to the red lines and the symmetrized Beta distribution to the blue lines.

Figure 2 :

 2 Figure2: Selected complexities with respect to the penalty constant ρ for the same simulation of n = 500, 000 observations. The colored dashed lines correspond to the single-state complexities M k (ρ).

Figure 3 :Figure 4 :

 34 Figure 3: Logarithm of the L 2 error on each emission densities depending on the logarithm of the number of observations for each of the selection and calibration methods. Each color corresponds to one emission density. The full lines are the medians of the 20 observations and the dashed ones are the 25 and 75 percentiles.

Figure 6 :

 6 Figure 6: Selected model dimensions for each n using our state-by-state selection method (left) and 10-fold cross validation (right). The full lines are the median model dimensions and the dashed lines are the 25 and 75 percentiles.

Figure 7 :

 7 Figure 7: Error of the cross validation estimators for each n using 10-fold cross validation.The full lines are the median errors for each density and the dashed lines are the 25 and 75 percentiles.

Figure 8 :

 8 Figure 8: First 15 eigenvalues of the spectrum of the empirical tensor N50,50 (see Algorithm 3 in Appendix A). Left: fisher 1, right: fisher 2.

Figure 9 :

 9 Figure 9: Selected complexities and estimated densities on artisanal fishery data (fisher 1, n = 17, 300). Green = state 1, blue = state 2. The dirac component is shown as a dot at y = 0. The selected dimensions are (14, 41).

Figure 10 :

 10 Figure 10: Selected complexities and estimated densities on artisanal fishery data (fisher 2, n = 11, 600). Green = state 1, blue = state 2. The dirac component is shown as a dot at y = 0. The selected dimensions are (68, 18).

Figure 11 :

 11 Figure 11: Selected complexities and estimated densities for Cormorant d's trajectory (n = 2, 891). Green = state 1, blue = state 2, red = state 3. The selected dimensions are (80, 110, 15).

Figure 12 :

 12 Figure 12: Projection of the estimated densities of Figure 11 for Cormorant d on the set of probability densities (left) and comparison with an estimation with histogram densities on a regular partition of size 300 using the EM algorithm (right).

  from f * .

Acknowledgments

I am grateful to Elisabeth Gassiat and Claire Lacour for their precious advice. I thank Augustin Touron for providing me with a R implementation of the spectral algorithm. I would also like to thank Marie-Pierre Etienne and of course Faustinato Behivoke (Institut Halieutiques et des Sciences Marines, Université de Toliara, Madagascar), Marc Léopold (IRD) and Sophie Bertrand (IRD) for letting me work on their data sets.

Appendix A. Spectral algorithm, full version

) ∼ log(n) for the estimators fk computed with n ≥ 700, 000 observations (n ≥ 1, 000, 000 for the cross validation estimators from Section 4.5). The smaller the exponent, the faster the estimators converge. The line "hidden states known" is obtained by density estimation when the hidden states are observed.

The empirical least squares criterion is M (π,Q,f ) -M 2 F . It corresponds to the L 2 error between the empirical distribution of three consecutive observations and the theoretical distribution under the parameters (π, Q, f ).

Implementation

We use 10-fold cross validation, that is we split the sequence into 10 segments of same size I 1 , . . . , I 10 . In order to avoid interferences between samples, we prune the ends of each segment, so that the observations in each segment can be considered independent. In practice, we take a gap of 30 observations between two segments.

We ran 150 simulations, 10 per value of n, with the same parameters as in Section 4.1. Each simulation is as follows.

For each segment I j , we run the spectral algorithm on all models P M for M_min ≤ M ≤ M_max using only the observations from the other segments. The transition matrix is estimated using an additional step of the spectral method which is adapted from Steps 8 and 9 of Algorithm 1 of De [START_REF] De Castro | Consistent estimation of the filtering and marginal smoothing distributions in nonparametric hidden Markov models[END_REF]. Then, we compute the least squares ) k∈X , Q and π.

[

Step 1] Consider the following empirical estimators: for any a, c ∈ [m] and b ∈ [M ],

• Lm (a

[

Step 2] Let Ûm be the m × K matrix of orthonormal left singular vectors and VM be the M × K matrix of orthonormal right singular vectors of Nm,M corresponding to its top K singular values.

[

Step 5] Compute Ri a (K × K) unit Euclidean norm columns matrix that diagonalizes the matrix Ĉi (1): R-1 i Ĉi (1) Ri = Diag( Λi (1, 1), . . . , Λi (1, K)). ) k∈X defined by for all k ∈ X , f (M,r)

[

Step 8] Let Ôm be the m × K matrix containing the first m rows of Ô. Set π = Π ∆ ( Û m Ôm ) -1 Û m Lm where Π ∆ is the L 2 projection onto the probability simplex.

[Step 9] Let Q be the transition matrix defined by

where Π TM is the projection onto the set of transition matrices. This projection is obtained by projecting each line of the matrix onto the probability simplex.

Appendix B. Proofs

B.1 Proof of Lemma 1

Let τ n,M be the permutation that minimizes τ -→ max

.

[H( )] means

that with probability 1 -, one has max

B.3 Definition of the polynomial H

B.3.1 Definition

We parametrize the application

in the following way. For p ∈ R K-1 , q ∈ R K×(K-1) and A ∈ R K×(K-1) , define the extensions

p corresponds to π -π * , q to Q -Q * and A to the components of ff * on f * (which is a basis as soon as [Hid] holds). The condition on the last component of p and of each line of q and Ā follows from the fact that p corresponds to the difference of two probability vectors, q corresponds to the difference of two transition matrices and Ā correspond to the difference of two vectors of probability densities on a basis of probability densities. Then, consider the quadratic form derived from the Taylor expansion of

Let M be the matrix associated to this quadratic form. We define H as the determinant of M . Direct computations show that H is a polynomial in the coefficients of π * , Q * and G(f * ).

B.3.2 Link between H and the quadratic form from Equation (3)

The goal of this section is to show how H can be used to lower bound the quadratic form from Equation (3) by a positive constant times the distance between (π, Q, f ) and (π * , Q * , f * ). We will not need the assumptions [Hid], [HF] or [Hdet] unless specified otherwise. Let us start by the relation between the norms of (p, q, A) and (p, q, Ā).

Lemma 15 For all (p, q, A)

B.4.1 The orthogonal part.

Let u be the orthogonal projection of h on Span(f ). Then

where

Let us write Π the matrix whose diagonal terms are the elements of π * + p and Q the matrix Q * + q, then M f can be written as

By the Schur product theorem, these terms are nonnegative since they correspond to Hadamard products of three Gram matrices which are nonnegative. Thus, one can lower bound M f (p, q, u, a) by the second term of the sum, which leads to M f (p, q, u, a)

Assume [Hid] holds for the parameters (π * +p, Q * +q, f +u), then the matrices (Π Q ) G(f + u)Π Q and Q G(f + u)Q are positive symmetric with respective lowest eigenvalue lower