TU Darmstadt / ULB / TUprints

Scalable Inference in Graph-coupled Continuous-time Markov Chains

Linzner, Dominik (2021)
Scalable Inference in Graph-coupled Continuous-time Markov Chains.
Technische Universität
doi: 10.12921/tuprints-00017403
Ph.D. Thesis, Primary publication, Publisher's Version

[img]
Preview
Text
2020-29-12_Linzner_Dominik.pdf
Copyright Information: CC BY-SA 4.0 International - Creative Commons, Attribution ShareAlike.

Download (6MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Scalable Inference in Graph-coupled Continuous-time Markov Chains
Language: English
Referees: Köppl, Prof. Dr. Heinz ; Opper, Prof. Dr. Manfred
Date: 2021
Place of Publication: Darmstadt
Collation: xviii, 101 Seiten
Date of oral examination: 11 December 2020
DOI: 10.12921/tuprints-00017403
Abstract:

In this dissertation novel techniques for inference and learning of and decision-making in probabilistic graphical models over combinatorial state-spaces in continuous-time are developed. Such models are prevalent in the natural sciences and engineering. They can be used to describe various types of multi-agent dynamics on networks, with applications ranging from gene-regulatory networks in molecular biology to social networks in the social sciences to power-grids in engineering. All these examples exist in continuous-time. The first part of this thesis focuses on inference and learning from incomplete data, recorded at irregular positions in time - which represents the status-quo when dealing with data from molecular biology. Inference based on such data is intractable, with the most prominent reason being the exponentially growing state-space in the number of agents. A common approach to alleviate the state-space explosion are variational approximations. Variational approximations allow for exact computation of approximate inference solutions. This contrasts sampling, which computes approximate solutions of exact inference. Variational approximations exist in various forms for static- or a discrete-time graphical models. We provide a principled way of generating variational approximations for inference in continuous-time probabilistic graphical models of various degrees of accuracy. Similarly, learning probabilistic graphical models is non-tractable, as the number of graph-structures scales super-exponentially in the number of agents. This becomes especially hopeless in the aforementioned incomplete data-scenario, where for each of the possible graphs the intractable inference has to be performed. We relax the combinatorial problem of structure search to a gradient-based approach using optimization over mixtures of possible structures. By combination with the aforementioned variational inference, a scalable method for structure learning from incomplete time-series data is developed. The second part of this thesis focuses on decision-making in continuous-time multi-agent networks. First we take the perspective of an external policymaker. The goal is to perform optimal sequential interventional experiments to learn network structure and parameters requiring only a minimal amount of resources. For this, we adopt techniques from optimal experimental design and causal inference. Making optimal decisions under uncertainty requires accounting for all possible outcomes. This is intractable to do exactly in multi-agent systems. We develop a novel variational criterion that allows for making decisions in high-dimensional settings. We show how interventions from Pearls do-calculus can be translated from static to continuous-time models. The result is surprising - the outcome of an intervention in a continuous-time cyclic interaction graph is the same as in a static acyclic Bayesian network. Then, we take the perspective of individual agents and make optimal local state-dependent decisions in the form of actions to achieve a common goal. In this planning scenario, each agent has to account for all possible state-action trajectories of all other agents. Here, we leverage the variational perturbation theory developed in the first part of the thesis by making use of the duality between planning and inference. We show how the (discounted) planning via inference framework translates into continuous-time.

Alternative Abstract:
Alternative AbstractLanguage

In dieser Dissertation werden neue Techniken für Inferenz und Lernen von und Entscheidungsfindung in probabilistischen graphischen Modellen über kombinatorische Zustandsräume in kontinuierlicher Zeit entwickelt. Solche Modelle sind in den Natur- und Ingenieurwissenschaften weitverbreitet. Sie können zur Beschreibung verschiedener Arten von Multi-Agenten-Dynamiken in Netzwerken verwendet werden, wobei die Anwendungen von genregulatorischen Netzwerken in der Molekularbiologie über soziale Netzwerke in den Sozialwissenschaften bis hin zu Stromnetzen in den Ingenieurwissenschaften reichen. Alle diese Beispiele existieren in kontinuierlicher Zeit. Der erste Teil dieser Arbeit befasst sich mit der Inferenz und dem Lernen auf Basis unvollständiger Daten, die an unregelmäßigen Positionen in der Zeit aufgenommen wurden - was den Status-quo in der Molekularbiologie darstellt. Auf solchen Daten basierende Inferenz ist nicht skalierbar, wobei der prominenteste Grund dafür der exponentiell wachsende Zustandsraum in der Zahl der Agenten ist. Ein üblicher Ansatz zur Milderung der Zustandsraumexplosion sind Variationsnäherungen. Variationsnäherungen ermöglichen die exakte Berechnung von approximativen Inferenzlösungen. Dies steht im Gegensatz zur Stichprobenmethode, die approximative Berechnungen für exakte Inferenzen ermöglicht. Solche Variationsapproximationen existieren in verschiedenen Formen in statischen oder zeitdiskreten probabilistischen graphischen Modell. Wir hingegen bieten eine prinzipielle Methode zur Erzeugung von Variationsnäherungen für die Inferenz in zeitkontinuierlichen probabilistischen graphischen Modellen mit verschiedenen Genauigkeitsgraden. In ähnlicher Weise ist das Erlernen der Strukturen probabilistischer graphischer Modelle nicht skalierbar, da die Anzahl der Strukturen mit der Anzahl der Agenten super-exponentiell skaliert. Besonders aussichtslos wird dies im oben erwähnten Szenario mit unvollständigen Daten, in welchem für jeden der möglichen Strukturen die nicht skalierbare Inferenz durchgeführt werden muss. Wir relaxieren das kombinatorische Problem der Struktursuche auf einen gradientenbasierten Ansatz, bei dem die Optimierung über Mischungen möglicher Strukturen erfolgt. Durch Kombination mit der oben erwähnten Variationsinfererenz wird eine skalierbare Methode zum Strukturlernen aus unvollständigen Zeitreihendaten entwickelt. Der zweite Teil dieser Arbeit konzentriert sich auf die Entscheidungsfindung in zeitkontinuierlichen Multiagentennetzwerken. Zunächst nehmen wir die Perspektive eines externen Planers ein. Das Ziel besteht darin, eine optimale Sequenz von Interventionsexperimenten durchzuführen, um die Netzwerkstruktur und -parameter unter möglichst geringen Ressourcen zu erlernen. Dazu übernehmen wir Techniken aus der optimalen Versuchsplanung und kausaler Inferenz. Um optimale Entscheidungen unter Unsicherheit treffen zu können, müssen alle möglichen Ereignisse unter Einbezug ihrer Eintrittswahrscheinlichkeit berücksichtigt werden, was wiederum in Multi-Agenten-Systemen nicht exakt zu bewerkstelligen ist. Wir entwickeln ein neuartiges Variationskriterium, das es ermöglicht, Entscheidungen in hochdimensionalen Problemen zu treffen. Wir zeigen, wie Interventionen aus Pearls do-calculus von statischen auf zeitkontinuierliche Modelle übertragen werden. Das Ergebnis ist überraschend - der Effekt einer Intervention in einem zeitkontinuierlichen zyklischen Interaktionsgraphen ist derselbe wie in einem statischen azyklischen Bayes'schen Netzwerk. Im folgenden nehmen wir die Perspektive der einzelnen Agenten ein und treffen optimale lokale, zustandsabhängige Entscheidungen in Form von Aktionen, um ein gemeinsames Ziel zu erreichen. In diesem Planungsszenario muss jeder Agent alle möglichen Zustands-Aktions-Trajektorien aller anderen Agenten berücksichtigen. Hier nutzen wir die im ersten Teil der Arbeit entwickelte Variationsstörungstheorie, indem wir uns die Dualität zwischen Planung und Inferenz zunutze machen. Wir zeigen, wie die (diskontierte) Planung über einen Inferenzansatz in kontinuierlicher Zeit übertragen werden.

German
Status: Publisher's Version
URN: urn:nbn:de:tuda-tuprints-174031
Classification DDC: 000 Generalities, computers, information > 004 Computer science
500 Science and mathematics > 510 Mathematics
600 Technology, medicine, applied sciences > 620 Engineering and machine engineering
Divisions: 18 Department of Electrical Engineering and Information Technology > Institute for Telecommunications > Bioinspired Communication Systems
Date Deposited: 13 Jan 2021 14:50
Last Modified: 10 May 2022 09:38
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/17403
PPN: 474802477
Export:
Actions (login required)
View Item View Item