Algoritmi za uvjetno uzorkovanje u skrivenim Markovljevim modelima

master's thesis

• Author: Erik Banek
• Mentor: Miljenko Huzak (mentor)
• Committee member: Miljenko Huzak (predsjednik povjerenstva)
• Committee member: Snježana Lubura Strunjak (član povjerenstva)
• Committee member: Vanja Wagner (član povjerenstva)
• Committee member: Bojan Basrak (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2020-04-28, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

U ovome radu prezentiramo problem izglađivanja na općenitim skrivenim Markovljevim modelima. Problem izglađivanja i srodni problemi sa sekvencijalnom strukturom distribucija su se rješavali Kalmanovim i proširenim Kalmanovi filtrom koji imaju snažne pretpostavke o normalnosti ili linearizaciji modela. Sekvencijalni Monte Carlo algoritmi su nastali iz potrebe da se takvi problemi riješe na općenitijoj klasi modela, i uz slabije pretpostavke. Prezentiramo i motiviramo nastanak algoritma sekvencijalnog uzorkovanja po važnosti s reuzorkovanjem koji služi kao prototip svih sekvencijalnih Monte Carlo metoda. Prvo poglavlje motivira proučavanje skrivenih Markovljevih modela s primjerima i pokazuje kako oni pokrivaju vrlo široku klasu modela. Dajemo teoretsku podlogu Markovljevim lancima na općenitom prostoru stanja i formalno definiramo skrivene Markovljeve procese te problem izglađivanja. Zatim u drugom poglavlju obrađujemo algoritam uzorkovanja po važnosti i njegova proširenja, sve s ciljem kasnije primjene na problemima sa sekvencijalnom strukturom poput izglađivanja. Obrađujemo samo-normalizirajuću varijantu i dodatak reuzorkovanja. Poopćujemo definiciju asimptotske normalnosti na dvostruke nizove i uvodimo alate koji služe za asimptotsku analizu uvjetno nezavisnih dvostrukih nizova, sve s ciljem dokazivanja da korak reuzorkovanja čuva asimptotsku normalnost. Kao proširenje tehnike uzorkovanja po važnosti na skrivene Markovljeve modele, u trećem poglavlju opisujemo sekvencijalno uzorkovanje po važnosti i dajemo nekoliko načina na koje možemo implementirati instrumentalnu distribuciju u tom algoritmu. Pokazujemo prisutnost problema degeneracije u algoritmu te da ga dodavanje reuzorkovanja uspješno rješava. Na kraju, dajemo dovoljne uvjete i dokazujemo asimptotsku normalnost sekvencijalnog algoritma sa reuzorkovanjem, pritom se oslanjajući na dokaz čuvanja normalnosti koraka reuzorkovanja.

Abstract (english)

In this thesis we present the problem of smoothing on general state space hidden Markov models. Smoothing and other related problems with sequential structure have been solved by using the Kalman filter and the extended Kalman filter, which have strong assumptions on normality and linearity of models. Sequential Monte Carlo methods were developed with the goal of not needing such strong model assumptions. We present and motivate the development of an algorithm called sequential importance sampling with resampling, which serves as a prototype for all sequential Monte Carlo methods. The first chapter motivates exploration of hidden Markov models with examples, and tries to argue that it is a very versatile class of models. We also give a theoretical background on general state space Markov chains and formally define hidden Markov processes and the smoothing problem. Then in the second chapter, we present importance sampling and some of its extensions, with the goal of applying it on problems with a sequential structure, as in the case of smoothing in hidden Markov models. The extensions we present are self-normalizing importance sampling and importance sampling with resampling. For proving asymptotic normality of estimators that those algorithms give, we show generalizations of asymptotic normality for triangular arrays and tools which we use for the analysis of conditionally independent triangular arrays. In the third chapter we present sequential importance sampling and describe several possible ways of implementing instrumental kernels. That algorithm is a generalization of importance sampling which can be used for smoothing in hidden Markov models. We describe how weight degeneracy occurs in sequential importance sampling and present reasons why resampling is a necessary addition to sequential importance sampling. At the end, we present a proof of asymptotic normality of sequential sampling with resampling.

• Keywords: Markovljevi modeli; Kalmanovi filter; Monte Carlo metoda
• Keywords (english): Markov models; Kalman filter; Monte Carlo method
• Language: croatian
• URN:NBN: urn:nbn:hr:217:979892
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2020-07-22 10:06:33