Learning Equivalence Classes of Bayesian Networks Structures
This work addresses a methodological improvement for researchers in probabilistic graphical models, but it appears incremental as it adapts existing search algorithms to a refined search space without claiming broad breakthroughs.
The paper tackles the problem of learning Bayesian networks from data by proposing a search space where states correspond to equivalence classes of structures, rather than individual structures, to better align with scoring functions that evaluate entire classes. The result shows a comparison where greedy search in this new space is evaluated against traditional methods, though no concrete performance numbers are provided in the 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.