dc.contributor.author
Dittmer, Evelyn
dc.date.accessioned
2018-06-08T00:08:56Z
dc.date.available
2009-03-04T09:40:55.992Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/11530
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-15728
dc.description
1 Introduction 1 2 Markov Processes 7 2.1 Markov Jump Processes . . . . . . .
. . . . . . . . . . . . . . 7 2.1.1 The Generator Matrix . . . . . . . . . . .
. . . . . . . 8 2.1.2 The Imbedding Problem . . . . . . . . . . . . . . . . .
9 2.1.3 Necessary Conditions for the Existence of a Generator 11 2.1.4
Uniqueness of the Generator . . . . . . . . . . . . . . 14 2.1.5 Imbedding of
Perturbed Generator Matrices . . . . . . 15 2.2 The Ornstein-Uhlenbeck Process
. . . . . . . . . . . . . . . . 17 3 Hidden Markov Models 22 3.1 The EM
Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 24 3.1.1 The Baum-
Welch Algorithm . . . . . . . . . . . . . . . 27 3.1.2 Metastability Analysis
with HMMs . . . . . . . . . . . 29 4 Parameter Estimation for Ornstein-
Uhlenbeck Processes 31 4.1 Propagation of the Probability Density . . . . . .
. . . . . . . 31 4.1.1 Further Simplification . . . . . . . . . . . . . . . .
. . 34 4.2 Optimal Parameters via the Maximum Likelihood Principle . 34 4.3
Multi-Dimensional Parameter Estimation without Euler Discretization . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . 36 5 HMMSDE 40 5.1 Model
Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 5.2 Concept .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 5.2.1 Likelihood
Function . . . . . . . . . . . . . . . . . . . 42 5.3 Partial Observability .
. . . . . . . . . . . . . . . . . . . . . . 43 5.3.1 Expectation Step . . . .
. . . . . . . . . . . . . . . . . 43 5.3.2 Maximization Step . . . . . . . . .
. . . . . . . . . . . 44 5.4 Enhancements and Application . . . . . . . . . .
. . . . . . . 44 5.5 Illustrative Example: Three-Hole Potential . . . . . . .
. . . 46 6 Parameter Estimation for Markov Jump Processes 53 6.1 Discrete
Likelihood . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Continuous
Likelihood . . . . . . . . . . . . . . . . . . . . . . 54 6.3 Finding an
Optimal Generator under Partial (Discrete) Observation . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . 56 6.3.1 The Expectation Step . . . . . .
. . . . . . . . . . . . 59 6.3.2 The Maximization Step . . . . . . . . . . . .
. . . . . 63 6.4 Comparison and Discussion of the Maximum Likelihood Estimator
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 6.4.1 Resolvent
Method . . . . . . . . . . . . . . . . . . . . 64 i 6.4.2 Quadratic
Optimization Method . . . . . . . . . . . . 65 6.4.3 Pros and Cons . . . . . .
. . . . . . . . . . . . . . . . 66 6.4.4 Perturbation Theory . . . . . . . . .
. . . . . . . . . . 68 6.5 Numerical Examples . . . . . . . . . . . . . . . .
. . . . . . . 69 6.5.1 Generator Estimation under Perturbation . . . . . . .
69 6.5.2 A Metastable Generator . . . . . . . . . . . . . . . . . 71 7 HMM
with Generator Estimation 74 7.1 Hidden Markov Jump Process . . . . . . . . .
. . . . . . . . . 74 7.1.1 Concept . . . . . . . . . . . . . . . . . . . . . .
. . . . 75 7.1.2 Parameter Estimation . . . . . . . . . . . . . . . . . . 78
7.1.3 Numerical Examples . . . . . . . . . . . . . . . . . . . 80 7.2 Markov
Jump Output Process . . . . . . . . . . . . . . . . . . 89 7.2.1 Model Design
. . . . . . . . . . . . . . . . . . . . . . . 90 7.2.2 Likelihood . . . . . .
. . . . . . . . . . . . . . . . . . . 90 7.2.3 Partial Observability . . . . .
. . . . . . . . . . . . . . 91 7.2.4 Example: Recovering an HMM-MJP from a
Realization with Varying Time Lag . . . . . . . . . . . . . . . 92 7.2.5
Example: A Metastable Generator Revisited . . . . . 99 7.2.6 Example: A
Discrete Generator for an Smoluchowski Process . . . . . . . . . . . . . . . .
. . . . . . . . . . 104 7.3 Alternative Approaches to HMM Variants . . . . . .
. . . . . 109 8 Summary 111 9 Zusammenfassung 112
dc.description.abstract
In this thesis a set of procedures for the analysis of time series was
developed. The models introduced here are based on the concept of Hidden
Markov models. A hidden Markov model (HMM) consists of two stochastic
processes. However, only one of these is observable. The HMM variants
presented herein have been developed with regard to a prospective application
to biomolecular time series. Therefore, the investigated time series are
realizations of processes that can be characterized as follows: They jump
between metastable states. The correlation times are small with respect to the
exit times from a metastable state. On a time scale, chosen in such a way that
the process is Markovian, these jumps occur instantaneously. That is:
Transitions between metastable states in equilibrium take place in one or very
few time steps. By means of the presented methods in particular, the question
how metastable states can be distinguished by kinetic patterns is addressed.
The local dynamics are modeled either by a space-discrete Markov jump process
or by a continuous diffusion process. Both concepts are discussed by means of
several examples. Particularly we focussed on the issue of generator
estimation. The combination of the generator estimation with the concept of
the hidden Markov model is new. It allows for analyzing time-continuous
processes with standard HMM techniques. Especially the time-continuity of the
model makes the analysis of time series with varying time lags possible.
Furthermore, a model with Markov jump output process has the advantage that
the process is determined by the generator matrix only. Hence no additional
assumption about the distribution of the data is required. Beyond this in the
examples we observed that even if the box-discretization is rather coarse-
grained, the local dynamics still can be expressed satisfactorily by an HMM-
MJP. In the scope of this thesis HMM-MJP was applied to small systems,
generated by Smoluchowski dynamics, by a discrete generator or by an HMM
itself. However, the algorithms are applicable to the high-dimensional case.
How HMM-MJP performs in the application to larger systems - such as the
simulation of biomolecules - has to be clarified in further investigations.
Difficulties arising with larger systems are on the one hand computational
costs and on the other hand cumulations of small entries in the generator
matrix. Too many small entries close to zero can lead to numerical
instabilities. One approach to handle these problems is the restriction of the
state space as described in the examples 7.2.5 and 7.2.6.
de
dc.description.abstract
In dieser Arbeit wurde ein Verfahrenskatalog zur Zeitreihenanalyse
metastabiler Systeme entwickelt. Die hier eingeführten Modelle basieren auf
dem Konzept der Hidden Markov Modelle. Ein Hidden Markov Modell (HMM) besteht
aus zwei stochastischen Prozessen, von denen nur einer beobachtbar ist. Die
HMM-Varianten in dieser Arbeit wurden im Hinblick auf die spätere Anwendung
auf Biomolekuelzeitreihen entwickelt. Deshalb sind die zu analysierenden
Zeitreihen Realisierungen von Prozessen, die sich wie folgt charakterisieren
lassen: Sie springen zwischen metastabilen Zustaenden. Die Korrelationsszeiten
sind im Vergleich zu den Austrittszeiten aus einem metastabilen Zustand klein.
Auf einer Zeitskala, die so gewaehlt ist, dass der Prozess Markovsch ist,
passieren diese Spruenge "ploetzlich". Das heißt: Uebergänge zwischen
metastabilen Zuständen im Gleichgewicht passieren in einem oder in sehr
wenigen Zeitschritten. Mit den vorgestellten Verfahren laesst sich
insbesondere die Frage, wie metastabile Zustaende anhand kinetischer Muster zu
unsterscheiden sind, behandeln. Die lokale Dynamik wird entweder duch einen
raeumlich diskreten Markovschen Sprungprozess oder aber durch einen
kontinuierlichen Diffusionsprozess modelliert. Diese beiden Konzepte wurden
anhand von Beispielen diskutiert. Insbesondere die Frage der
Generatorschaetzung wurde in dieser Arbeit eingehend behandelt. Die
Kombination der Generatorschaetzung mit dem Konzept des Hidden Markov Modells
ist neu. Sie ermoeglicht die Analyse zeit-kontinuierlicher Prozesse mit
bewährten HMM-Techniken. Die Darstellung durch zeit-kontinuierliche Modelle
erlaubt insbesondere die Analyse von Zeitreihen mit unterschiedlicher
Zeitschrittweite. Desweiteren hat ein HMM mit beobachtbarem Markovschen
Sprungprozess den Vorteil, dass der Prozess allein durch die Generatormatrix
bestimmt wird und keine zusaetzliche Annahme ueber die Verteilung der Daten
notwendig ist. Darueber hinaus hat sich in den Bespielen gezeigt, dass sich
selbst bei groben Boxdiskretisierungen die lokale Dynamik durch ein HMM-MJP
noch gut beschreiben laesst. Im Rahmen dieser Arbeit wurde das HMM-MJP auf
kleine Systeme angewandt, die von einer Smoluchowski Dynamik, einem diskreten
Generator oder einem HMM generiert wurden. Die Algorithmen sind jedoch auf den
hochdimensionalen Fall uebertragbar. Wie sich das HMM-MJP in der Anwendung auf
groeßere Systeme - etwa der Simulation von Biomoleküulen - bewaehrt, ist noch
in weiterfuehrenden Arbeiten zu untersuchen. Die Schwierigkeiten, die groeßere
Systeme mit sich bringen, sind zum einen der Rechenaufwand und zum anderen die
Häufung sehr kleiner Einträge in der Generatormatix, die zu numerischer
Instabilitaet fuehren koennen. Ein Ansatz, diese Probleme zu bewaeltigen, ist
die Einschränkung des Zustandsraumes, wie in den Beispielen 7.2.5 und 7.2.6
beschrieben.
de
dc.format.extent
II, 119 S.
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject
Hidden Markov Models (HMM)
dc.subject
Generator Estimation
dc.subject
Kinetic Processes
dc.subject
Imbedding Problem
dc.subject
Diffusion Processes
dc.subject
Makov Jump Processes
dc.subject.ddc
500 Naturwissenschaften und Mathematik::510 Mathematik
dc.title
Hidden Markov Models with time-continuous output behavior
dc.contributor.contact
dittmer@mi.fu-berlin.de
dc.contributor.firstReferee
Prof. Christof Schütte
dc.contributor.furtherReferee
Dr. Wilhelm Huisinga
dc.date.accepted
2009-02-11
dc.identifier.urn
urn:nbn:de:kobv:188-fudissthesis000000008760-2
dc.title.translated
Hidden Markov Modelle mit zeit-kontinuierlichem Ausgabeverhalten
de
refubium.affiliation
Mathematik und Informatik
de
refubium.mycore.fudocsId
FUDISS_thesis_000000008760
refubium.mycore.derivateId
FUDISS_derivate_000000005254
dcterms.accessRights.dnb
free
dcterms.accessRights.openaire
open access