Asymptotiques pou l’estimation

The approximation of fixed-interval smoothing distributions is a key is- sue in inference for general state-space hidden Markov models (HMM). This contribution establishes non-asymptotic bounds for the Forward Filtering Backward Smoothing (FFBS) and the Forward Filtering Backward Simula- tion (FFBSi) estimators of fixed-interval smoothing functionals. We show that the rate of convergence of the L-mean errors of both methods de- pends on the number of observations T and the number of particles N only through the ratio T /N for additive functionals. In the case of the FFBS, this improves recent results providing bounds depending on T /. These smoothed additive functionals appear naturally for maximum likelihood parameter inference in hidden Markov models. The computation of the gradient of the log-likelihood function (Fisher score) or of the intermediate quantity of the Expectation Maximization algorithm in- volves the estimation of such smoothed functionals, see [Capp´finite state-spaces, these smoothed additive functionals cannot be computed explicitly. In this paper, we consider Sequential Monte Carlo algorithm henceforth referred to as particle methods, to approximate these quantities. These methods combine sequential importance sampling and sampling importance resampling steps to produce a set of random particles with associated importance weights to approximate the fixed-interval smoothing distributions.The most straightforward implementation is based on the so-called path- space method. The complexity of this algorithm per time-step grows only linearly with the number N of particles, see [Del Moral, 2004]. However, a well-known shortcoming of this algorithm is known in the literature as the path degeneracy; see [Doucet et al., 2011] for a discussion.

 Framework

Several solutions have been proposed to solve this degeneracy prob- lem. In this paper, we consider the Forward Filtering Backward Smoothing algorithm (FFBS) and the Forward Filtering Backward Simulation algo- rithm (FFBSi) introduced in [Doucet et al., 2000] and further developed in [Godsill et al., 2004]. Both algorithms proceed in two passes. In the forward pass, a set of particles and weights is stored. In the Backward pass of the FFBS the weights are modified but the particles are kept fixed. The FFBSi draws independently different particle trajectories among all possible paths. Since they use a backward step, these algorithms are mainly adapted for batch estimation problems. However, as shown in [Del Moral et al., 2010a], when applied to additive functionals, the FFBS algorithm can be imple- mented forward in time, but its complexity grows quadratically with the number of particles. As shown in [Douc et al., 2011a], it is possible to im- plement the FFBSi with a complexity growing only linearly with the number of particles.-norm of the deviation between the smoothed ad-ditive functional and its particle approximation has been studied recently in [Del Moral et al., 2010a, Del Moral et al., 2010b]. In the unpublished paper by [Del Moral et al., 2010b], it is shown that the FFBS estimator variance of any smoothed additive functional is upper bounded by terms.

This paper is organized as follows. Section 7.2 introduces further defi- nitions and notations and the FFBS and FFBSi algorithms. In Section 7.3, upper bounds for the L-mean error and exponential deviation inequalities of these two algorithms are presented. In Section 7.4, some Monte Carlo experiments are presented to support our theoretical claims. The proofs are presented in Sections 7.5 and 7.6.Let X and Y be two general state-spaces endowed with countably gen- erated σ-fields X and Y. Let M be a Markov transition kernel defined on). Furthermore, the smoothing of such functions can be com- puted forward in time as shown in [Del Moral et al., 2010a]. This forward algorithm is exactly the one presented in [Doucet et al., 2011] as an alter- native to the use of the path-space method. Therefore, the results outlined in Section 7.3 hold for this method and confirm the conjecture mentioned in [Doucet et al., 2011].-mean error bounds and exponential deviation inequalities of the FFBS and FFBSi algorithms are established for additive functionals of the form (7.6). Our results are established under the following assumptions.Assumptions A9 and A10 give bounds for the model and assumption A11 for quantities related to the algorithm. A9(i), referred to as the strong mixing condition, is crucial to derive time-uniform exponential deviation inequalities and a time-uniform bound of the variance of the marginal smoothing distri- bution (see [Del Moral et Guionnet, 2001] and [Douc et al., 2011a]). For all function h from a space E to R, osc(h) is defined.