Abstract:
Although partially observable stochastic processes are ubiquitous in many fields of science,
little work has been devoted to discovering and analysing the means by which several such
processes may interact to influence each other. In this thesis we extend probabilistic structure
learning between random variables to the context of temporal models which represent
partially observable stochastic processes. Learning an influence structure and distribution
between processes can be useful for density estimation and knowledge discovery.
A common approach to structure learning, in observable data, is score-based structure
learning, where we search for the most suitable structure by using a scoring metric to value
structural configurations relative to the data. Most popular structure scores are variations on
the likelihood score which calculates the probability of the data given a potential structure.
In observable data, the decomposability of the likelihood score, which is the ability to
represent the score as a sum of family scores, allows for efficient learning procedures and
significant computational saving. However, in incomplete data (either by latent variables or
missing samples), the likelihood score is not decomposable and we have to perform
inference to evaluate it. This forces us to use non-linear optimisation techniques to optimise
the likelihood function. Furthermore, local changes to the network can affect other parts of
the network, which makes learning with incomplete data all the more difficult.
We define two general types of influence scenarios: direct influence and delayed influence
which can be used to define influence around richly structured spaces; consisting of
multiple processes that are interrelated in various ways. We will see that although it is
possible to capture both types of influence in a single complex model by using a setting of
the parameters, complex representations run into fragmentation issues. This is handled by
extending the language of dynamic Bayesian networks to allow us to construct single
compact models that capture the properties of a system’s dynamics, and produce influence
distributions dynamically.
The novelty and intuition of our approach is to learn the optimal influence structure in
layers. We firstly learn a set of independent temporal models, and thereafter, optimise a
structure score over possible structural configurations between these temporal models. Since
the search for the optimal structure is done using complete data we can take advantage of
efficient learning procedures from the structure learning literature. We provide the
following contributions: we (a) introduce the notion of influence between temporal models;
(b) extend traditional structure scores for random variables to structure scores for temporal
models; (c) provide a complete algorithm to recover the influence structure between
temporal models; (d) provide a notion of structural assembles to relate temporal models for
types of influence; and finally, (e) provide empirical evidence for the effectiveness of our
method with respect to generative ground-truth distributions.
The presented results emphasise the trade-off between likelihood of an influence structure to
the ground-truth and the computational complexity to express it. Depending on the
availability of samples we might choose different learning methods to express influence
relations between processes. On one hand, when given too few samples, we may choose to
learn a sparse structure using tree-based structure learning or even using no influence
structure at all. On the other hand, when given an abundant number of samples, we can use
penalty-based procedures that achieve rich meaningful representations using local search
techniques.
Once we consider high-level representations of dynamic influence between temporal models,
we open the door to very rich and expressive representations which emphasise the
importance of knowledge discovery and density estimation in the temporal setting.
Description:
A Ph.D. thesis submitted to the Faculty of Science, University of the Witwatersrand,
in fulfillment of the requirements for the degree of Doctor of Philosophy in Computer
Science
May 2018