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
On particle-based online smoothing and parameter inference in general state-space models
KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematical Statistics.ORCID iD: 0000-0001-9565-7686
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: urn:nbn:se:kth:diva-215292ISBN: 978-91-7729-562-4 (print)OAI: oai:DiVA.org:kth-215292DiVA, id: diva2:1147566
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
List of papers
1. 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
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
2. Particle-based adaptive-lag online marginal smoothing in general state-space models
Open this publication in new window or tab >>Particle-based adaptive-lag online marginal smoothing in general state-space models
(English)Manuscript (preprint) (Other academic)
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-215290 (URN)
Note

QC 20171009

Available from: 2017-10-06 Created: 2017-10-06 Last updated: 2017-10-09Bibliographically approved
3. Particle-based, online estimation of tangent filters with application to parameter estimation in nonlinear state-space models
Open this publication in new window or tab >>Particle-based, online estimation of tangent filters with application to parameter estimation in nonlinear state-space models
(English)Manuscript (preprint) (Other academic)
National Category
Probability Theory and Statistics
Identifiers
urn:nbn:se:kth:diva-215291 (URN)
Note

QC 20171009

Available from: 2017-10-06 Created: 2017-10-06 Last updated: 2017-10-09Bibliographically approved
4. 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
2015 (English)In: IFAC-PapersOnLine, ISSN 2405-8963, Vol. 48, no 28, p. 963-968Article in journal (Refereed) Published
Abstract [en]

Estimating the parameters of general state-space models is a topic of importance for many scientific and engineering disciplines. In this paper we present an online parameter estimation algorithm obtained by casting our recently proposed particle-based, rapid incremental smoother (PaRIS) into the framework of online expectation-maximization (EM) for state-space models proposed by Cappé (2011). Previous such particle-based implementations of online EM suffer typically from either the well-known degeneracy of the genealogical particle paths or a quadratic complexity in the number of particles. However, by using the computationally efficient and numerically stable PaRIS algorithm for estimating smoothed expectations of timeaveraged sufficient statistics of the model we obtain a fast algorithm with very limited memory requirements and a computational complexity that grows only linearly with the number of particles. The efficiency of the algorithm is illustrated in a simulation study.

Keywords
EM algorithm, parameter estimation, particle filters, recursive estimation, state space models
National Category
Mathematics
Identifiers
urn:nbn:se:kth:diva-195392 (URN)10.1016/j.ifacol.2015.12.255 (DOI)2-s2.0-84988598857 (Scopus ID)
Note

QC 20161122

Available from: 2016-11-22 Created: 2016-11-03 Last updated: 2017-10-06Bibliographically approved

Open Access in DiVA

Kappa(1074 kB)112 downloads
File information
File name FULLTEXT01.pdfFile size 1074 kBChecksum SHA-512
29261071bc91f9cb98822bd549f3f9ff64bfd6ef0459ecbf03d72b9f994d74a26317e285f4a04f736ec1729ade0727a5505d07932652627e03777bd3133ae4a7
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Westerborn, Johan
By organisation
Mathematical Statistics
Probability Theory and Statistics

Search outside of DiVA

GoogleGoogle Scholar
Total: 112 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 203 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