TY - BOOK

T1 - Graphical modeling in dynamical systems

T2 - Structure learning and computational complexity

AU - Mogensen, Søren Wengel

PY - 2020

Y1 - 2020

N2 - 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.

AB - 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.

UR - https://soeg.kb.dk/permalink/45KBDK_KGL/1pioq0f/alma99123788927805763

M3 - Ph.D. thesis

BT - Graphical modeling in dynamical systems

PB - Department of Mathematical Sciences, Faculty of Science, University of Copenhagen

ER -