Graphical modeling in dynamical systems: Structure learning and computational complexity

Publikation: Bog/antologi/afhandling/rapportPh.d.-afhandling

  • Søren Wengel Mogensen
The thesis studies graphical modeling of local independence in stochastic processes. By applying a separation criterion to graphs, we obtain a graphical representation of a local independence structure which describes how the system evolves over time. We describe a class of graphs which facilitates graphical modeling of partially observed stochastic processes driven by correlated error processes.

Within this graphical framework, we prove some Markov properties for specific classes of stochastic processes which provides a link between a graph and the local independence structure of a stochastic process. Graphs that encode the same independence structure are said to be Markov equivalent. Characterizations of Markov equivalence are interesting as they allow us to understand which graphical structures are indistinguishable in terms of the separation models that they encode. We prove several results relating to Markov equivalence in different classes of graphs. We also consider various computational problems and show that many of the naturally occuring problems are hard in these classes of graphs.

We consider structure learning in the case of partially observed stochastic processes, i.e., the task of recovering a graphical representation from an observational distribution. Exact structure learning based on tests of local independence is also hard and we suggest an approximation algorithm which is computationally feasible.
OriginalsprogEngelsk
ForlagDepartment of Mathematical Sciences, Faculty of Science, University of Copenhagen
StatusUdgivet - 2020

ID: 248025969