Projected Transfer Operators: Discretization of Markov processes in high-dimensional state spaces

Abstract

For 15 years, so called Markov State Models (MSM) have been used successfully to simplify large complex systems, which are described by Markov processes. The goal of Markov State Modeling is the approximation of a Markov process by a Markov chain on a small finite state space. Until 2005, Markov State Models have been always constructed via full partitions of state space, i.e. sets that cover the whole state space. That is, one calculated the transition probabilities for the approximating Markov chain from the transition probabilities of the original Markov process between partitioning sets. We also called this class of methods classical or Standard MSM. Then, the idea of rather using fuzzy affiliation functions instead of a deterministic clustering into sets was introduced. Two years ago, an approach was proposed that avoided full partitions of state space and constructed a fuzzy MSM variant by defining small disjoint sets in the most dominant metastable regions. Recently, we introduced another method, which is based on these so called core sets. In this thesis, we developed a mathematical framework that is applicable to all of these former MSM techniques. We used a general, functional analytic approach and understood Markov State Models as best approximations of the original transfer operator in terms of discretization. For core set based MSM this led to a new construction via conditional stopping times instead of transition probabilities. From this point of view we could also prove several statements about the approximation quality of the models, which are also valid for classical MSM and other methods that refer to projected operators. For example, we connected the reproduction of the dominant timescales of the system by the Markov State Model to projection errors of the associated eigenvectors. From error estimates for these projection errors, we further understood how to choose the discretization, i.e. the core sets, in order to ensure a good approximation quality. Moreover, we used these results to construct an algorithm for the estimation of the MSM from a realization of the original Markov process. One should emphasize that the estimation of an appropriate discretization itself is also part of this method. Finally, for finite state spaces we could connect the core set based MSM variant to so called fuzzy cluster problems. That is, we used the construction of the Markov State Model to develop a novel fuzzy clustering approach and we demonstrated its properties by application to a sample network. We think that this ending is very appealing because it shows the broad impact of the developed mathematical framework. We started with MSM, i.e. discretizations for Markov processes on continuous state spaces, and using the results from this analysis we ended with a proposal for the fuzzy clustering of networks.

Seit 15 Jahren werden so genannte Markov State Modelle (MSM) erfolgreich eingesetzt um komplexe Systeme zu vereinfachen, die von Markovprozessen beschrieben werden. Das Ziel eines MSM ist die Approximation eines solchen Markovprozesses durch eine Markovkette auf möglichst kleinem Zustandsraum. Dabei werden die Übergangswahrscheinlichkeiten der Markovkette aus Übergangswahrscheinlichkeiten des ursprünglichen Prozesses zwischen Teilmengen des Zustandsraums berechnet. Bis 2005 wurden hierbei immer vollständige Zerlegungen betrachtet, d.h. die Teilmengen überdeckten den kompletten Zustandsraum. Solche Modelle nannten wir daher auch klassische oder Standard MSM. Es kam die Idee auf, die Punkte des Zustandsraumes nicht deterministisch in Mengen aufzuteilen, sondern so genannte weiche/fuzzy Zuordnungen zu verwenden. Vor ungefähr zwei Jahren wurde dann vorgeschlagen, ebenfalls vollständige Zerlegungen zu vermeiden und eine fuzzy MSM Variante durch vereinzelte, disjunkte Mengen in den Regionen der höchsten Metastabilität zu konstruieren. Auf diesen so genannten Core Sets beruht auch der bisher letzte, von uns vorgestellte Ansatz. In dieser Arbeit ist nun ein mathematischer Rahmen entstanden, der alle bisherigen MSM Methoden einschließt. Dazu wählten wir einen funktionalanalytischen Zugang und verstanden Markov State Modelle als Bestapproximationen des ursprünglichen Transferoperators durch Diskretisierung. In Bezug auf Core Set basierte MSM entstand daraus eine neuartige Konstruktion durch bedingte Stoppzeiten anstelle von einfachen Übergangswahrscheinlichkeiten. Wir erarbeiteten aus diesem Blickwinkel mehrere Resultate über die Approximationsgüte der Methode, welche sogar für die klassischen MSM und andere Verfahren gültig sind, die sich auf Projektionen von Operatoren zurückführen lassen. Wir konnten unter anderem zeigen, dass die dominanten Zeitskalen des Markovprozesses durch das MSM korrekt wiedergegeben werden, falls die Projektionsfehler der dazugehörigen Eigenvektoren klein genug sind. Fehlerabschätzungen für diese Projektionsfehler ließen sogar die Einsicht zu, wie ein solches Core Set basiertes Markov State Modell zu konstruieren ist. Wir konnten dies nutzen, um einen Algorithmus zur Schätzung des Modells aus einer Simulation des ursprünglichen Prozesses anzugeben. Besonders hervorzuheben ist, dass die Methode auch die Schätzung der Core Sets, also der Diskretisierung selbst, beinhaltet. Für endliche Zustandsräume konnten wir die Ideen zur Konstruktion der MSM nutzen um einen neuartigen Ansatz zur Clusteranalyse herzuleiten. Die Methode wurde dann an einem Netzwerkbeispiel verdeutlicht. Wir finden, dass dies ein harmonisches Ende ist, da es die weitreichenden Einsatzmöglichkeiten des entwickelten mathematischen Hintergrundes aufzeigt. Wir begannen mit einer Analyse von MSM, d.h. Diskretisierungen von Markovprozessen auf kontinuierlichen Zustandsräumen, und nutzen die Resultate um die Arbeit mit einem Vorschlag zu fuzzy Clusterverfahren abzuschließen.