Change search
Link to record
Permanent link

Direct link
BETA
Publications (5 of 5) Show all publications
Olsson, J. & Westerborn, J. (2017). Efficient particle-based online smoothing in general hidden Markov models: The PaRIS algorithm. Bernoulli, 23(3), 1951-1996
Open this publication in new window or tab >>Efficient particle-based online smoothing in general hidden Markov models: The PaRIS algorithm
2017 (English)In: Bernoulli, ISSN 1350-7265, E-ISSN 1573-9759, Vol. 23, no 3, p. 1951-1996Article in journal (Refereed) Published
Abstract [en]

This paper presents a novel algorithm, the particle-based, rapid incremental smoother (PaRIS), for efficient online approximation of smoothed expectations of additive state functionals in general hidden Markov models. The algorithm, which has a linear computational complexity under weak assumptions and very limited memory requirements, is furnished with a number of convergence results, including a central limit theorem. An interesting feature of PaRIS, which samples on-the-fly from the retrospective dynamics induced by the particle filter, is that it requires two or more backward draws per particle in order to cope with degeneracy of the sampled trajectories and to stay numerically stable in the long run with an asymptotic variance that grows only linearly with time.

Place, publisher, year, edition, pages
INT STATISTICAL INST, 2017
Keywords
central limit theorem, general hidden Markov models, Hoeffding-type inequality, online estimation, particle filter, particle path degeneracy, sequential Monte Carlo, smoothing
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-206226 (URN)10.3150/16-BEJ801 (DOI)000398013100017 ()2-s2.0-85016201786 (Scopus ID)
Note

QC 20170517

Available from: 2017-05-17 Created: 2017-05-17 Last updated: 2017-10-06Bibliographically approved
Westerborn, J. (2015). On particle-based online smoothing and parameter inference in general hidden Markov models. (Licentiate dissertation). Stockholm: KTH Royal Institute of Technology
Open this publication in new window or tab >>On particle-based online smoothing and parameter inference in general hidden Markov models
2015 (English)Licentiate thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of two papers studying online inference in general hidden Markov models using sequential Monte Carlo methods.

The first paper present an novel algorithm, the particle-based, rapid incremental smoother (PaRIS), aimed at efficiently perform online approximation of smoothed expectations of additive state functionals in general hidden Markov models. The algorithm has, under weak assumptions, linear computational complexity and very limited memory requirements. The algorithm is also furnished with a number of convergence results, including a central limit theorem.

The second paper focuses on the problem of online estimation of parameters in a general hidden Markov model. The algorithm is based on a forward implementation of the classical expectation-maximization algorithm. The algorithm uses the PaRIS algorithm to achieve an efficient algorithm.

Abstract [sv]

Denna avhandling består av två artiklar som behandlar inferens i dolda Markovkedjor med generellt tillståndsrum via sekventiella Monte Carlo-metoder.

Den första artikeln presenterar en ny algoritm, PaRIS, med målet att effektivt beräkna partikelbaserade online-skattningar av utjämnade väntevärden av additiva tillståndsfunktionaler. Algoritmen har, under svaga villkor, en beräkningkomplexitet som växer endast linjärt med antalet partiklar samt h\ögst begränsade minneskrav. Dessutom härleds ett antal konvergensresultat för denna algoritm, såsom en central gränsvärdessats.

Den andra artikeln fokuserar på online-estimering av modellparametrar i en generella dolda Markovkedjor. Den presenterade algoritmen kan ses som en kombination av PaRIS och en nyligen föreslagen online-implementation av den klassiska EM-algoritmen.

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2015. p. viii, 15
Series
TRITA-MAT-A ; 2015:06
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-166629 (URN)978-91-7595-554-4 (ISBN)
Presentation
2015-06-05, Rum 3721, Institutionen för matematik, Lindstedtsvägen 25, KTH, Stockholm, 14:00 (English)
Opponent
Supervisors
Note

QC 20150521

Available from: 2015-05-21 Created: 2015-05-12 Last updated: 2015-05-21Bibliographically approved
Westerborn, J. & Olsson, J. (2014). EFFICIENT PARTICLE-BASED ONLINE SMOOTHING IN GENERAL HIDDEN MARKOV MODELS. Paper presented at IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), MAY 04-09, 2014, Florence, ITALY. Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing
Open this publication in new window or tab >>EFFICIENT PARTICLE-BASED ONLINE SMOOTHING IN GENERAL HIDDEN MARKOV MODELS
2014 (English)In: Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing, ISSN 1520-6149Article in journal (Refereed) Published
Abstract [en]

This paper deals with the problem of estimating expectations of sums of additive functionals under the joint smoothing distribution in general hidden Markov models. Computing such expectations is a key ingredient in any kind of expectation-maximization-based parameter inference in models of this sort. The paper presents a computationally efficient algorithm for online estimation of these expectations in a forward manner. The proposed algorithm has a linear computational complexity in the number of particles and does not require old particles and weights to be stored during the computations. The algorithm avoids completely the well-known particle path degeneracy problem of the standard forward smoother. This makes it highly applicable within the framework of online expectation-maximization methods. The simulations show that the proposed algorithm provides the same precision as existing algorithms at a considerably lower computational cost.

Keywords
Hidden Markov models, particle filters, smoothing methods, Monte Carlo methods, state estimation
National Category
Fluid Mechanics and Acoustics
Identifiers
urn:nbn:se:kth:diva-158346 (URN)10.1109/ICASSP.2014.6855159 (DOI)000343655308009 ()2-s2.0-84905270424 (Scopus ID)
Conference
IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), MAY 04-09, 2014, Florence, ITALY
Note

QC 20150121

Available from: 2015-01-21 Created: 2015-01-07 Last updated: 2017-12-05Bibliographically approved
Olsson, J. & Westerborn, J.An efficient particle-based online EM algorithm for general state-space models.
Open this publication in new window or tab >>An efficient particle-based online EM algorithm for general state-space models
(English)Manuscript (preprint) (Other academic)
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-166628 (URN)
Note

QS 2015

Available from: 2015-05-12 Created: 2015-05-12 Last updated: 2015-05-21Bibliographically approved
Olsson, J. & Westerborn, J.Efficient particle-based online smoothing in general hidden Markov models: the PaRIS algorithm.
Open this publication in new window or tab >>Efficient particle-based online smoothing in general hidden Markov models: the PaRIS algorithm
(English)Manuscript (preprint) (Other academic)
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-166617 (URN)
Note

QS 2015

Available from: 2015-05-12 Created: 2015-05-12 Last updated: 2015-05-21Bibliographically approved
Organisations
Identifiers
ORCID iD: ORCID iD iconorcid.org/0000-0001-9565-7686

Search in DiVA

Show all publications