Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Particle filters and Markov chains for learning of dynamical systems
Linköping University, Department of Electrical Engineering, Automatic Control. Linköping University, The Institute of Technology.
2013 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

Sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC) methods provide computational tools for systematic inference and learning in complex dynamical systems, such as nonlinear and non-Gaussian state-space models. This thesis builds upon several methodological advances within these classes of Monte Carlo methods.Particular emphasis is placed on the combination of SMC and MCMC in so called particle MCMC algorithms. These algorithms rely on SMC for generating samples from the often highly autocorrelated state-trajectory. A specific particle MCMC algorithm, referred to as particle Gibbs with ancestor sampling (PGAS), is suggested. By making use of backward sampling ideas, albeit implemented in a forward-only fashion, PGAS enjoys good mixing even when using seemingly few particles in the underlying SMC sampler. This results in a computationally competitive particle MCMC algorithm. As illustrated in this thesis, PGAS is a useful tool for both Bayesian and frequentistic parameter inference as well as for state smoothing. The PGAS sampler is successfully applied to the classical problem of Wiener system identification, and it is also used for inference in the challenging class of non-Markovian latent variable models.Many nonlinear models encountered in practice contain some tractable substructure. As a second problem considered in this thesis, we develop Monte Carlo methods capable of exploiting such substructures to obtain more accurate estimators than what is provided otherwise. For the filtering problem, this can be done by using the well known Rao-Blackwellized particle filter (RBPF). The RBPF is analysed in terms of asymptotic variance, resulting in an expression for the performance gain offered by Rao-Blackwellization. Furthermore, a Rao-Blackwellized particle smoother is derived, capable of addressing the smoothing problem in so called mixed linear/nonlinear state-space models. The idea of Rao-Blackwellization is also used to develop an online algorithm for Bayesian parameter inference in nonlinear state-space models with affine parameter dependencies.

Place, publisher, year, edition, pages
Linköping University Electronic Press, 2013. , 42 p.
Series
Linköping Studies in Science and Technology. Dissertations, ISSN 0345-7524 ; 1530
Keyword [en]
Bayesian learning, System identification, Sequential Monte Carlo, Markov chain Monte Carlo, Particle MCMC, Particle filters, Particle smoothers
National Category
Control Engineering Probability Theory and Statistics
Identifiers
URN: urn:nbn:se:liu:diva-97692DOI: 10.3384/diss.diva-97692ISBN: 978-91-7519-559-9 (print)OAI: oai:DiVA.org:liu-97692DiVA: diva2:654644
Public defence
2013-10-25, Visionen, Hus B, Campus Valla, Linköpings universitet, Linköping, 10:15 (English)
Opponent
Supervisors
Projects
CNDMCADICS
Funder
Swedish Research Council
Available from: 2013-10-08 Created: 2013-09-19 Last updated: 2013-10-08Bibliographically approved
List of papers
1. Backward simulation methods for Monte Carlo statistical inference
Open this publication in new window or tab >>Backward simulation methods for Monte Carlo statistical inference
2013 (English)In: Foundations and Trends in Machine Learning, ISSN 1935-8237, Vol. 6, no 1, 1-143 p.Article in journal (Refereed) Published
Abstract [en]

Monte Carlo methods, in particular those based on Markov chains and on interacting particle systems, are by now tools that are routinely used in machine learning. These methods have had a profound impact on statistical inference in a wide range of application areas where probabilistic models are used. Moreover, there are many algorithms in machine learning which are based on the idea of processing the data sequentially, first in the forward direction and then in the backward direction. In this tutorial we will review a branch of Monte Carlo methods based on the forward-backward idea, referred to as backward simulators. These methods are useful for learning and inference in probabilistic models containing latent stochastic processes. The theory and practice of backward simulation algorithms have undergone a significant development in recent years and the algorithms keep finding new applications. The foundation for these methods is sequential Monte Carlo (SMC). SMC-based backward simulators are capable of addressing smoothing problems in sequential latent variable models, such as general, nonlinear/non-Gaussian state-space models (SSMs). However, we will also clearly show that the underlying backward simulation idea is by no means restricted to SSMs. Furthermore, backward simulation plays an important role in recent developments of Markov chain Monte Carlo (MCMC) methods. Particle MCMC is a systematic way of using SMC within MCMC. In this framework, backward simulation gives us a way to significantly improve the performance of the samplers. We review and discuss several related backward-simulation-based methods for state inference as well as learning of static parameters, both using a frequentistic and a Bayesian approach.

Keyword
Bayesian learning, Markov chain Monte Carlo, Nonlinear signal processing, Particle smoothing, Sequential Monte Carlo
National Category
Control Engineering Probability Theory and Statistics
Identifiers
urn:nbn:se:liu:diva-98294 (URN)10.1561/2200000045 (DOI)
Projects
CNDMCADICS
Funder
Swedish Research Council
Available from: 2013-10-07 Created: 2013-10-07 Last updated: 2013-10-08
2. Ancestor Sampling for Particle Gibbs
Open this publication in new window or tab >>Ancestor Sampling for Particle Gibbs
2012 (English)In: Proceedings of the 26th Conference on Neural Information Processing Systems, 2012Conference paper, Published paper (Refereed)
Abstract [en]

We present a novel method in the family of particle MCMC methods that we refer to as particle Gibbs with ancestor sampling (PG-AS). Similarly to the existing PG with backward simulation (PG-BS) procedure, we use backward sampling to (considerably) improve the mixing of the PG kernel. Instead of using separate forward and backward sweeps as in PG-BS, however, we achieve the same effect in a single forward sweep. We apply the PG-AS framework to the challenging class of non-Markovian state-space models. We develop a truncation strategy of these models that is applicable in principle to any backward-simulation-based method, but which is particularly well suited to the PG-AS framework. In particular, as we show in a simulation study, PG-AS can yield an order-of-magnitude improved accuracy relative to PG-BS due to its robustness to the truncation error. Several application examples are discussed, including Rao-Blackwellized particle smoothing and inference in degenerate state-space models.

Keyword
Particle Gibbs, Sampling
National Category
Probability Theory and Statistics Control Engineering
Identifiers
urn:nbn:se:liu:diva-88610 (URN)9781627480031 (ISBN)
Conference
26th Conference on Neural Information Processing Systems, Lake Tahoe, NV, USA, 3-6 December, 2012
Projects
CADICSCNDM
Funder
Swedish Research Council
Available from: 2013-02-13 Created: 2013-02-13 Last updated: 2013-10-08
3. Bayesian semiparametric Wiener system identification
Open this publication in new window or tab >>Bayesian semiparametric Wiener system identification
2013 (English)In: Automatica, ISSN 0005-1098, E-ISSN 1873-2836, Vol. 49, no 7, 2053-2063 p.Article in journal (Refereed) Published
Abstract [en]

We present a novel method for Wiener system identification. The method relies on a semiparametric, i.e. a mixed parametric/nonparametric, model of a Wiener system. We use a state-space model for the linear dynamical system and a nonparametric Gaussian process model for the static nonlinearity. We avoid making strong assumptions, such as monotonicity, on the nonlinear mapping. Stochastic disturbances, entering both as measurement noise and as process noise, are handled in a systematic manner. The nonparametric nature of the Gaussian process allows us to handle a wide range of nonlinearities without making problem-specific parameterizations. We also consider sparsity-promoting priors, based on generalized hyperbolic distributions, to automatically infer the order of the underlying dynamical system. We derive an inference algorithm based on an efficient particle Markov chain Monte Carlo method, referred to as particle Gibbs with ancestor sampling. The method is profiled on two challenging identification problems with good results. Blind Wiener system identification is handled as a special case.

Place, publisher, year, edition, pages
Elsevier, 2013
Keyword
System identification, Wiener, Block-oriented models, Gaussian process, Semiparametric, Particle filter, Ancestor sampling, Particle Markov chain Monte Carlo
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-95954 (URN)10.1016/j.automatica.2013.03.021 (DOI)000321233900011 ()
Note

Funding Agencies|project Calibrating Nonlinear Dynamical Models|621-2010-5876|Swedish Research Council||CADICS||Linnaeus Center||

Available from: 2013-08-19 Created: 2013-08-12 Last updated: 2017-12-06
4. An Efficient Stochastic Approximation EM Algorithm using Conditional Particle Filters
Open this publication in new window or tab >>An Efficient Stochastic Approximation EM Algorithm using Conditional Particle Filters
2013 (English)In: Proceedings of the 38th International Conference on Acoustics, Speech, and Signal Processing, IEEE conference proceedings, 2013, 6274-6278 p.Conference paper, Published paper (Refereed)
Abstract [en]

I present a novel method for maximum likelihood parameter estimation in nonlinear/non-Gaussian state-space models. It is an expectation maximization (EM) like method, which uses sequential Monte Carlo (SMC) for the intermediate state inference problem. Contrary to existing SMC-based EM algorithms, however, it makes efficient use of the simulated particles through the use of particle Markov chain Monte Carlo (PMCMC) theory. More precisely, the proposed method combines the efficient conditional particle filter with ancestor sampling (CPF-AS) with the stochastic approximation EM (SAEM) algorithm. This results in a procedure which does not rely on asymptotics in the number of particles for convergence, meaning that the method is very computationally competitive. Indeed, the method is evaluated in a simulation study, using a small number of particles with promising results.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2013
Keyword
Maximum likelihood, Stochastic approximation, Conditional particle filter
National Category
Control Engineering Signal Processing
Identifiers
urn:nbn:se:liu:diva-93459 (URN)10.1109/ICASSP.2013.6638872 (DOI)000329611506087 ()
Conference
38th International Conference on Acoustics, Speech, and Signal Processing, Vancouver, Canada, 26-31 May, 2013
Projects
CNDMCADICS
Funder
Swedish Research Council, 621-2010-5876
Available from: 2013-06-03 Created: 2013-06-03 Last updated: 2014-02-20
5. Rao-Blackwellized Particle Smoothers for Mixed Linear/Nonlinear State-Space Models
Open this publication in new window or tab >>Rao-Blackwellized Particle Smoothers for Mixed Linear/Nonlinear State-Space Models
2013 (English)In: Proceedings of the 38th International Conference on Acoustics, Speech, and Signal Processing, IEEE conference proceedings, 2013, 6288-6292 p.Conference paper, Published paper (Refereed)
Abstract [en]

We consider the smoothing problem for a class of conditionally linear Gaussian state-space (CLGSS) models, referred to as mixed linear/nonlinear models. In contrast to the better studied hierarchical CLGSS models, these allow for an intricate cross dependence between the linear and the nonlinear parts of the state vector. We derive a Rao-Blackwellized particle smoother (RBPS) for this model class by exploiting its tractable substructure. The smoother is of the forward filtering/backward simulation type. A key feature of the proposed method is that, unlike existing RBPS for this model class, the linear part of the state vector is marginalized out in both the forward direction and in the backward direction.

Place, publisher, year, edition, pages
IEEE conference proceedings, 2013
Keyword
Rao-Blackwellization, Particle smoothing, Backward simulation, Sequential Monte Carlo
National Category
Signal Processing Control Engineering
Identifiers
urn:nbn:se:liu:diva-93460 (URN)10.1109/ICASSP.2013.6638875 (DOI)000329611506090 ()
Conference
38th International Conference on Acoustics, Speech, and Signal Processing, Vancouver, Canada, 26-31 May, 2013
Projects
CNDMCADICS
Funder
Swedish Research Council, 621-2010-5876
Available from: 2013-06-03 Created: 2013-06-03 Last updated: 2014-02-20Bibliographically approved
6. A non-degenerate Rao-Blackwellised particle filter for estimating static parameters in dynamical models
Open this publication in new window or tab >>A non-degenerate Rao-Blackwellised particle filter for estimating static parameters in dynamical models
2012 (English)In: Proceedings of the 16th IFAC Symposium on System Identification, 2012Conference paper, Oral presentation only (Refereed)
Abstract [en]

The particle filter (PF) has emerged as a powerful tool for solving nonlinear and/or non-Gaussian filtering problems. When some of the states enter the model linearly, this can be exploited by using particles only for the "nonlinear" states and employing conditional Kalman filters for the "linear" states; this leads to the Rao-Blackwellised particle filter (RBPF). However, it is well known that the PF fails when the state of the model contains some static parameter. This is true also for the RBPF, even if the static states are marginalised analytically by a Kalman filter. The reason is that the posterior density of the static states is computed conditioned on the nonlinear particle trajectories, which are bound to degenerate over time. To circumvent this problem, we propose a method for targeting the posterior parameter density, conditioned on just the current nonlinear state. This results in an RBPF-like method, capable of recursive identification of nonlinear dynamical models with affine parameter dependencies.

Keyword
Particle Filtering/Monte Carlo Methods; Nonlinear System Identification; Recursive Identification
National Category
Electrical Engineering, Electronic Engineering, Information Engineering
Identifiers
urn:nbn:se:liu:diva-81271 (URN)10.3182/20120711-3-BE-2027.00184 (DOI)
Conference
16th IFAC Symposium on System Identification, Brussels, Belgium, July 11-13, 2012.
Projects
CADICSCNDM
Funder
Swedish Research Council
Available from: 2012-09-10 Created: 2012-09-10 Last updated: 2013-10-08
7. An Explicit Variance Reduction Expression for the Rao-Blackwellised Particle Filter
Open this publication in new window or tab >>An Explicit Variance Reduction Expression for the Rao-Blackwellised Particle Filter
2011 (English)In: Proceedings of the 18th IFAC World Congress, 2011, 11979-11984 p.Conference paper, Published paper (Refereed)
Abstract [en]

Particle filters (PFs) have shown to be very potent tools for state estimation in nonlinear and/or non-Gaussian state-space models. For certain models, containing a conditionally tractable substructure (typically conditionally linear Gaussian or with finite support), it is possible to exploit this structure in order to obtain more accurate estimates. This has become known as Rao-Blackwellised particle filtering (RBPF). However, since the RBPF is typically more computationally demanding than the standard PF per particle, it is not always beneficial to resort to Rao-Blackwellisation. For the same computational effort, a standard PF with an increased number of particles, which would also increase the accuracy, could be used instead. In this paper, we have analysed the asymptotic variance of the RBPF and provide an explicit expression for the obtained variance reduction. This expression could be used to make an efficient discrimination of when to apply Rao-Blackwellisation, and when not to.

Keyword
Particle filtering, Monte-Carlo methods, Rao-Blackwellised particle filter, Marginalised particle filter, Rao-Blackwellisation, Variance reduction
National Category
Control Engineering
Identifiers
urn:nbn:se:liu:diva-81259 (URN)10.3182/20110828-6-IT-1002.02920 (DOI)978-3-902661-93-7 (ISBN)
Conference
18th IFAC World Congress, Milano, Italy 28 August-2 September, 2011
Projects
CADICSCNDM
Funder
Swedish Research Council
Available from: 2012-09-10 Created: 2012-09-10 Last updated: 2013-10-08

Open Access in DiVA

Particle filters and Markov chains for learning of dynamical systems(666 kB)1800 downloads
File information
File name FULLTEXT01.pdfFile size 666 kBChecksum SHA-512
e07a1de4a9ca1475cc8210fe788daa4156b48561dc0f0754fe4a9c1fd9683f5de09253c66e5a802947c0a0fde4c781e1518eff83a5af7e32d6c3bd270d138983
Type fulltextMimetype application/pdf
omslag(140 kB)36 downloads
File information
File name COVER01.pdfFile size 140 kBChecksum SHA-512
130c6ec90cf6f07bddbf62a69963452eefd08dd296e8561fd668b8fac950ec6fbb507124848368106e9925a65284cf7041aa5541c42361a1e296d378adbc5215
Type coverMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Lindsten, Fredrik
By organisation
Automatic ControlThe Institute of Technology
Control EngineeringProbability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 1800 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 1576 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf