  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.
