Learning equivalence classes of Bayesian network structures

TLDR

Approaches to learning Bayesian networks typically combine a scoring function with a heuristic search, and many scoring functions return a score for the entire equivalence class, making it appropriate to search over equivalence classes rather than individual structures. The authors propose a search space whose states correspond to equivalence classes of Bayesian network structures. This space enables any heuristic search algorithm to be applied directly to equivalence classes. Greedy search performance in the proposed equivalence-class space is comparable to that in a search space of individual structures.

Abstract

Approaches to learning Bayesian networks from data typically combine a scoring function with a heuristic search procedure. Given a Bayesian network structure, many of the scoring functions derived in the literature return a score for the entire equivalence class to which the structure belongs. When using such a scoring function, it is appropriate for the heuristic search algorithm to search over equivalence classes of Bayesian networks as opposed to individual structures. We present the general formulation of a search space for which the states of the search correspond to equivalence classes of structures. Using this space, any one of a number of heuristic search algorithms can easily be applied. We compare greedy search performance in the proposed search space to greedy search performance in a search space for which the states correspond to individual Bayesian network structures.