Exact Bayesian Structure Discovery in Bayesian Networks 论文

摘要

Learning a Bayesian network structure from data is a well-motivated but computationally hard task. We present an algorithm that computes the exact posterior probability of a subnetwork, e.g., a directed edge; a modified version of the algorithm finds one of the most probable network structures. This algorithm runs in time $O(n 2^n + n^{k+1} C(m))$, where $n$ is the number of network variables, $k$ is a constant maximum in-degree, and $C(m)$ is the cost of computing a single local marginal conditional likelihood for $m$ data instances. This is the first algorithm with less than super-exponential complexity with respect to $n$. Exact computation allows us to tackle complex cases where existing Monte Carlo methods and local search procedures potentially fail. We show that also in domains with a large number of variables, exact computation is feasible, given suitable a priori restrictions on the structures; combining exact and inexact methods is also possible. We demonstrate the applicability of the presented algorithm on four synthetic data sets with 17, 22, 37, and 100 variables.