## Exact Bayesian Structure Discovery in Bayesian Networks

** Mikko Koivisto, Kismat Sood**; 5(May):549--573, 2004.

### Abstract

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.