Searching for Bayesian Network Structures in the Space of Restricted
  Acyclic Partially Directed Graphs
  Although many algorithms have been designed to construct Bayesian network
structures using different approaches and principles, they all employ only two
methods: those based on independence criteria, and those based on a scoring
function and a search procedure (although some methods combine the two). Within
the score+search paradigm, the dominant approach uses local search methods in
the space of directed acyclic graphs (DAGs), where the usual choices for
defining the elementary modifications (local changes) that can be applied are
arc addition, arc deletion, and arc reversal. In this paper, we propose a new
local search method that uses a different search space, and which takes account
of the concept of equivalence between network structures: restricted acyclic
partially directed graphs (RPDAGs). In this way, the number of different
configurations of the search space is reduced, thus improving efficiency.
Moreover, although the final result must necessarily be a local optimum given
the nature of the search method, the topology of the new search space, which
avoids making early decisions about the directions of the arcs, may help to
find better local optima than those obtained by searching in the DAG space.
Detailed results of the evaluation of the proposed search method on several
test problems, including the well-known Alarm Monitoring System, are also
presented.
