Sequential Monte Carlo: Towards Degeneracy-Free Methods

Imperfectly observed evolving systems arise throughout the human world. Weather forecasting, modelling stock prices, transcribing music or interpreting human speech automatically are just a few of the situations in which imperfect observations of a system which evolves in time are all that is available whilst the underlying system is the thing in which we are interested: Given satellite observations and sparse localised measurements, we'd like to accurately characterise the weather now and predict future weather; given measurements of pitch at discrete times we'd like a computer to be able to produce a meaningful description of what was being said at the time.Surprisingly, it's possible to model a great number of these problems using a common framework, known as a state space model (or hidden Markov model). Inferring the likely value of the unobserved process based upon a sequence of observations, as those observations become available is in principle reasonably straightforward but it requires the evaluation of integrals which cannot be solved by analytical mathematics and which are too complex to deal with accurately via simple numerical methods. Simulation-based techniques have been developed to address these problems and are now the most powerful collection of tools for estimating the current state of the unobserved process given all of the observations received so far. Much effort has been dedicated in recent years to designing algorithms to efficiently describe the likely path of the unobserved process from the beginning of the observation sequence up to the current time in a similar way. This problem is much harder as each observation we receive tells us a little more about the likely history of the process and continually updating this ever-longer list of locations in an efficient way is far from simple.The methods proposed here will attempt to extend simulation-based statistical techniques in a new direction which is particularly well suited to characterisation of the whole path of the unobserved process and not just its terminal value. Two different strategies based around the same premise - that sometimes several smaller simulations can in a particular sense outperform a single larger simulation for the same computational cost - will be investigated. The techniques developed will be investigated both theoretically and empirically.In addition to developing and analysing new computational techniques, the project will provide software libraries which simplify the use of these methods in real problems (hopefully to the extent that scientists who are expert in particular application domains will be able to apply the techniques directly to their own problems).The research could be considered successful if:1/ It leads to new methods for performing inference in state space models.2/ These methods can be implemented with less application-specific tuning that existing methods require or these methods provide more efficient use of computational resources.3/ These methods are sufficiently powerful to allow the use of more complex models than are currently practical.4/ The methods are adopted by practitioners in at least some of the many areas in which these techniques might be usefully employed.The long term benefits could include more realistic assessment of risk in financial systems, more reliable tracking and prediction of meteorological phenomena and improved technological products wherever there is a need to dynamically incorporate knowledge arising from measurements as they become available. There will be particular advantages in settings in which the full path of the imperfectly observed underlying process is of interest but there is scope for improvement even when this is not the case.

Potential beneficiaries of the proposed research are numerous and diverse. Imperfectly observed systems which evolve over time are ubiquitous: problems as diverse as quantifying risk in financial markets to weather forecasting require solutions of a very similar form. This project aims to extend the state of the art in statistical inference for these problems. Direct beneficiaries of the project may be divided into a number of groups: (1) Specialists of Monte Carlo Methods and Interacting Particle Systems. (2) Researchers in related disciplines. (3) Developers of products and systems which perform inference in imperfectly-observed time series. The first group will benefit primarily from increased knowledge about the performance of interacting and non-interacting ensembles of SMC methods as well as theoretical characterisation of certain local properties of SMC algorithms. The second from the availability of novel, widely applicable algorithms which should require less application-specific tuning than existing methods as well as delivering improved performance (and expanding the range of models which can be employed) especially when working directly with unobserved trajectories. The final group will benefit in the same way and especially from the availability of software to allow easy and computationally efficient implementation of the proposed algorithms. SMC techniques are already employed in many areas: econometrics, online trading strategies and risk management; signal processing, communications and control engineering; genetics and other areas of biology; particle physics; robotics, navigation and tracking; computer graphics and many others. Any significant developments, properly disseminated, in this area should attract interest: it is important to capitalise upon this interest by making potential benefits clear to possible users and ensuring that implementation is as easy as is possible. The longer term benefits of the project are closely linked to the RCUK Digital Economy programme. By providing core methodology, the project aims to facilitate systems in areas ranging from the medical (real-time diagnostics in which it is necessary to combine data from several sources as it becomes available, for example) to the explictly economic (non-elective trading systems depend fundamentally upon accurate, online quantification of risk). It is hoped that the algorithms developed in the project will find widespread application throughout these areas with a two principal benefits: allowing the use of more realistic models with concomitant improved estimation and more realistic quantification of risk and allowing easy implementation by non-specialists. If the project is successful, then indirect benefits will be experienced in the medium to long term by much larger groups, including the general public. Improved estimating, inference and prediction in broad classes of time-series model will have far-reaching consequences. As well as providing opportunities for parameter estimation, estimation of the path of the latent process is important for understanding of the evolution of stochastic systems and especially for the accurate quantification of risk: a critical problem in many areas. The algorithms proposed here are, of course, just one step towards improving inference in these systems. However, the approach detailed here is qualitatively different to anything which has been considered previously and they seek to directly address the degeneracy problem which afflicts essentially all simulation-based approaches to inference in these problems. Other techniques which ameliorate the problem or perform limited inference without resolving it have been developed in recent years but typically come at the cost of either super-linear computational cost or analaytic approximations which are difficult to accurately characterise.