Download 14-07

CJ Oates, JQ Smith, S Mukherjee and J Cussens

Exact Estimation of Multiple Directed Acyclic Graphss

Abstract: Probability models based on directed acyclic graphs (DAGs) are widely used to make inferences and predictions concerning interplay in multivariate systems. In many applications, data are collected from related but non-identical units whose DAGs may differ but are likely to share many features. Statistical estimation for multiple related DAGs appears extremely challenging since all graphs must be simultaneously acyclic. Recent work by Oyen and Lane (2013) avoids this problem by making the strong assumption that all units share a common ordering of the variables and that this ordering is known to the statistician. In this paper we propose a novel Bayesian formulation for multiple DAGs

and, requiring no assumptions on any ordering of the variables, we prove that the maximum a posteriori estimate is characterised as the solution to an integer linear program (ILP). Consequently estimation may be achieved using highly optimised techniques for ILP instances, including constraint propagation and cutting plane algorithms. Our framework permits a complex dependency structure on the collection of units, including group and subgroup structure. This dependency structure can itself be efficiently learned from data and a special case of our methodology provides a novel analogue of k-means clustering for DAGs. Results on simulated data and fMRI data obtained from multiple subjects are presented.