Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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
Efficient particle-based online smoothing in general hidden Markov models: The PaRIS algorithm
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematical Statistics.ORCID iD: 0000-0003-0772-846X
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematical Statistics.ORCID iD: 0000-0001-9565-7686
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. Vol. 23, no 3, p. 1951-1996
Keywords [en]
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: urn:nbn:se:kth:diva-206226DOI: 10.3150/16-BEJ801ISI: 000398013100017Scopus ID: 2-s2.0-85016201786OAI: oai:DiVA.org:kth-206226DiVA, id: diva2:1096197
Note

QC 20170517

Available from: 2017-05-17 Created: 2017-05-17 Last updated: 2017-10-06Bibliographically approved
In thesis
1. On particle-based online smoothing and parameter inference in general state-space models
Open this publication in new window or tab >>On particle-based online smoothing and parameter inference in general state-space models
2017 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis consists of 4 papers, presented in Paper A-D, on particle- based online smoothing and parameter inference in general state-space hidden Markov models.

In Paper A a novel algorithm, the particle-based, rapid incremental smoother (PaRIS), aimed at efficiently performing online approxima- tion of smoothed expectations of additive state functionals in general hidden Markov models, is presented. The algorithm has, under weak assumptions, linear computational complexity and very limited mem- ory requirements. The algorithm is also furnished with a number of convergence results, including a central limit theorem.

In Paper B the problem of marginal smoothing in general hidden Markov models is tackled. A novel, PaRIS-based algorithm is presented where the marginal smoothing distributions are approximated using a lagged estimator where the lag is set adaptively.

In Paper C an estimator of the tangent filter is constructed, yield- ing in turn an estimator of the score function. The resulting algorithm is furnished with theoretical results, including a central limit theorem with a uniformly bounded variance. The resulting estimator is applied to online parameter estimation via recursive maximum liklihood.

Paper D focuses on the problem of online estimation of parameters in general hidden Markov models. The algorithm is based on a for- ward implementation of the classical expectation-maximization algo- rithm. The algorithm uses the PaRIS algorithm to achieve an efficient algorithm. 

Abstract [sv]

Denna avhandling består av fyra artiklar, presenterade i Paper A-D, som behandlar partikelbaserad online-glättning och parameter- skattning i generella dolda Markovkedjor.

I papper A presenteras en ny algoritm, PaRIS, med målet att effek- tivt beräkna partikelbaserade online-skattningar av glättade väntevär- den av additiva tillståndsfunktionaler. Algoritmen har, under svaga villkor, en beräkningskomplexitet som växer endast linjärt med antalet partiklar samt högst begränsade minneskrav. Dessutom härleds ett an- tal konvergensresultat för denna algoritm, såsom en central gränsvärdes- sats. Algoritmen testas i en simuleringsstudie.

I papper B studeras problemet att skatta marginalglättningsfördel- ningen i dolda Markovkedjor. Detta åstadkoms genom att exekvera PaRIS-algoritmen i marginalläge. Genom ett argument om mixning i Markovkedjor motiveras att avbryta uppdateringen efter en av ett stoppkriterium bestämd fördröjning vilket ger en adaptiv fördröjnings- glättare.

I papper C studeras problemet att beräkna derivator av filterfördel- ningen. Dessa används för att beräkna gradienten av log-likelihood funktionen. Algoritmen, som innehåller en uppdateringsmekanism lik- nande den i PaRIS, förses med ett antal konvergensresultat, såsom en central gränsvärdessats med en varians som är likformigt begränsad. Den resulterande algoritmen används för att konstruera en rekursiv parameterskattningsalgoritm.

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

Place, publisher, year, edition, pages
Stockholm: KTH Royal Institute of Technology, 2017. p. 27
Series
TRITA-MAT-A ; 2017:04
National Category
Probability Theory and Statistics
Research subject
Applied and Computational Mathematics
Identifiers
urn:nbn:se:kth:diva-215292 (URN)978-91-7729-562-4 (ISBN)
Public defence
2017-11-03, F3, Lindstedtsvägen 26, Stockholm, 09:00 (English)
Opponent
Supervisors
Note

QC 20171009

Available from: 2017-10-09 Created: 2017-10-06 Last updated: 2017-10-09Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Olsson, JimmyWesterborn, Johan

Search in DiVA

By author/editor
Olsson, JimmyWesterborn, Johan
By organisation
Mathematical Statistics
In the same journal
Bernoulli
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • harvard1
  • 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