Detailansicht

Optimization of advanced Markov chain Monte Carlo methods with applications to biological systems

Richard Paul

Art der Arbeit

Masterarbeit

Universität

Universität Wien

Fakultät

Fakultät für Physik

Studiumsbezeichnung bzw. Universitätlehrgang (ULG)

Masterstudium Computational Science

Betreuer*in

Christoph Dellago

Volltext herunterladen
Volltext in Browser öffnen

DOI

10.25365/thesis.72044

URN

urn:nbn:at:at-ubw:1-13597.15144.728096-4

Link zu u:search

(Print-Exemplar eventuell in Bibliothek verfügbar)

Abstracts

Abstract

(Deutsch)

Ziel der Bayesschen Inferenz is es, aus gegebenen Daten unbekannte Modellparameter mit Hilfe der Bayesschen Statistik abzuleiten. Die Qualität der einzelnen Parameterschätzungen ist in der A-Posteriori-Verteilung abgebildet, aus der in der Praxis mit Hilfe von Markov-Ketten-Monte-Carlo-Algorithmen Stichproben gezogen werden. Die Berechnung der A-Posteriori-Dichte kann rechenintensiv sein, insbesondere wenn sie kostspielige Vorwärtssimulationen des zugrunde liegenden Modells erfordert. Effizientes Sampling ist daher entscheidend, um solche Parameterschätzprobleme praktisch lösbar zu machen. Eine besondere Klasse von Problemen, die bei der Bayes'schen 13C-Stoffflussanalyse auftritt, ist die Bestimmung von Reaktionsraten in metabolischen Reaktionsnetzwerken aus Isotopenmarkierungsdaten. Neben komplex geformter A-Posteriori-Verteilungen, weisen diese Probleme linear begeschränkte Parameterräume auf, die zusätzliche Sorgfalt beim Sampling erfordern. Neben der Entwicklung immer ausgefeilterer Sampling-Algorithmen, stellt die Hyperparameteroptimierung bestehender Algorithmen einen weiteren Ansatzpunkt zur Steigerung der statistischen Effizienz dar, der bisher aus praktischer Sicht noch wenig Beachtung gefunden hat. Theoretische Ergebnisse existieren für bestimmte Samplingalgorithmen, die nahelegen, dass das Erreichen bestimmter Akzeptanzraten des Metropolis-Hastings-Algorithmus die Effizienz optimiert. In dieser Arbeit betrachten wir die erwartete quadrierte Sprungweite als ein alternatives und allgemeineres Ziel zur Optimierung der Effizienz von Markov-Ketten-Monte-Carlo-Algorithmen. Wir präsentieren einen auf Thompson-Sampling basierenden Tuning-Algorithmus zur Optimierung der Schrittweite, einem bestimmten Hyperparameter, den zahlreiche Sampling-Algorithmen aufweisen. Mithilfe kleiner Stichproben wird dabei entweder die Akzeptanzrate oder die erwartete quadratische Sprungweite geschätzt und optimiert. Der Algorithmus wird an einer Reihe von angewandten Problemen aus der Bayesschen \Ciso-Stoffwechselanalyse getestet, die so konzipiert sind, dass sie typische Problemmerkmale aus realen Anwendungsfällen aufweisen, wie z.B. Multimodalitäten und Nicht-Identifizierbarkeiten. Die Ergebnisse des Thompson-Sampling-Tuners werden mit den Ergebnissen eines umfangreichen und systematischen Experiments verglichen, bei dem die optimalen Schrittgrößen im Brute-Force-Verfahren berechnet wurden. Wir stellen fest, dass der vorgestellte Thompson-Sampling-Tuner gut geeignet ist, um nahezu optimale Schrittgrößen für die getesteten Probleme unter Verwendung der erwarteten quadratischen Sprungdistanz zu ermitteln. Der Algorithmus ist außerdem zuverlässig in der Lage, Schrittgrößen zu identifizieren, die gewünschte Akzeptanzraten erreichen. Weiters bestätigen die Ergebnisse der umfangreichen Studie, dass Hyperparameteroptimierung gemäß der Akzeptanzrate nicht allgemein anwendbar ist. Stattdessen legen die Ergebnisse nahe, dass Hyperparameteroptimierung gemäß der erwarteten quadratischen Sprungdistanz zuverlässiger ist, um angemessene Hyperparameter zu ermitteln. Insbesondere, erreicht die Hyperparameteroptimierung gemäß der erwarteten quadratischen Sprungdistanz eine 300\% Verbesserung der statistischen Effizienz. Zu guter letzt stellen wir die quelloffene, hochleistungsfähige Python-Bibliothek hopsy vor, die im Rahmen dieser Arbeit implementiert wurde, um Polytop-Sampling für Anwender zu erleichtern. Alle Ergebnisse dieser Arbeit wurden mit hopsy erzielt und der Quellcode ist online verfügbar [1]. Insbesondere ist auch der hier entwickelte Thompson-Sampling-Tuner in hopsy verfügbar. [1] https://github.com/ripaul/mscthesis

Abstract

(Englisch)

Bayesian inference aims at inferring unknown model parameters from given data by the means of Bayesian statistics. The quality of particular parameter estimates is encoded in the posterior distribution, which in practice has to be sampled using Markov chain Monte Carlo algorithms. The computation of the posterior density may be computationally expensive, especially when it requires costly forward simulations of the underlying model. Efficient sampling is thus crucial to make such parameter estimation problems practically feasible. A particular class of problems which arise in Bayesian \Ciso metabolic flux analysis is the determination of reaction rates in metabolic reaction networks from isotope labeling data. Apart from complexly shaped posterior distributions, these problems exhibit linearly constrained parameter spaces, which require additional care during sampling. Apart from the development of ever more sophisticated sampling algorithms, the hyperparametrization of existing algorithms admits another lever for increasing the statistical efficiency of sampling, which has not yet gained much attention from a practical perspective. For particular sampling algorithms, theoretical results exist which suggest that achieving particular target acceptance rates optimizes the efficiency. Throughout this thesis, we consider the expected squared jump distance as an alternative and more general target for optimizing the efficiency of Markov chain Monte Carlo sampling. We devise a Thompson sampling based tuning algorithm for optimizing the step size, a particular hyperparameter numerous sampling algorithms exhibit, using short, preliminary samples from which acceptance rate or expected squared jump distance are estimated. The algorithm is tested on a number of problems from Bayesian \Ciso metabolic flux analysis, which are designed to exhibit typical problem features found in real world applications, such as multimodalities and non-identifiabilities.The results of the Thompson sampling tuner are compared against the results of an extensive and systematical experiment, where optimal step sizes are computed in a brute-force manner. We find that the presented Thompson sampling tuner is well capable of identifying close to optimal step sizes for the tested problems using the expected squared jump distance. The algorithm is further also capable of reliably identifying step sizes achieving desired acceptance rates. Further, the results of the extensive study confirm that acceptance rate tuning is not generally applicable and instead suggests that tuning \wrt the expected squared jump distance is more reliable for identifying reasonable hyperparameters. In particular, our results suggest that tuning \wrt the expected squared jump distance can improve statistical efficiency by up to 300\%. Finally, we present the open-source, high-performance Python library which was implemented alongside this thesis to facilitate polytope sampling for practitioners. All results of this thesis were achieved using and the source code is made available online [1]. In particular, also the Thompson sampling tuner is accessible in hopsy. [1] https://github.com/ripaul/mscthesis

Autor*innen

Richard Paul

Haupttitel (Englisch)

Optimization of advanced Markov chain Monte Carlo methods with applications to biological systems

Paralleltitel (Deutsch)

Optimierung fortgeschrittener Markov-Ketten-Monte-Carlo-Methoden mit Anwendungen auf Biologischen Systemen

Publikationsjahr

2022

Umfangsangabe

x, 110 Seiten : Illustrationen

Sprache

Englisch

Beurteiler*in

Christoph Dellago

Klassifikationen

31 Mathematik > 31.70 Wahrscheinlichkeitsrechnung ,

31 Mathematik > 31.76 Numerische Mathematik ,

31 Mathematik > 31.80 Angewandte Mathematik ,

35 Chemie > 35.73 Biochemische Reaktionen ,

42 Biologie > 42.10 Theoretische Biologie ,

42 Biologie > 42.11 Biomathematik, Biokybernetik ,

42 Biologie > 42.15 Zellbiologie ,

54 Informatik > 54.59 Programmierung: Sonstiges ,

54 Informatik > 54.76 Computersimulation ,

54 Informatik > 54.79 Computermethodik: Sonstiges

AC Nummer

AC16598184

Utheses ID

63903

Studienkennzahl

UA | 066 | 910 | |

Detailansicht

Abstracts

Schlagwörter