We have developed a new local search algorithm, within the score+search approach for learning Bayesian network structures from databases. The main feature of our algorithm is that it does not search in the space of DAGs, but uses a new form of representation, restricted PDAGs, that allows us to search efficiently in a space similar to the space of equivalence classes of DAGs. For the common situation in which a decomposable scoring function is used, the set of operators that define the neighborhood structure of our search space can be scored locally (as it happens in the space of DAGs), i.e. we can evaluate any neighboring restricted PDAG by computing at most two local scores. In this way, we maintain the computational efficiency that the space of DAGs offers and, at the same time, we explore a more reduced search space, with a smoother landscape, which avoids some early decisions on edge directions. These characteristics may help to direct the search process towards better network structures.
The experimental results show that our search method based on restricted PDAGs can efficiently and accurately recover complex Bayesian network structures from data, and can compete with several state of the art Bayesian network learning algorithms, although it does not significantly improve them. Our experiments in Section 6, as well as those conducted by [17], seem to point out that search algorithms based on PDAGs can obtain slightly better results, with respect to both effectiveness and efficiency, than search methods based on DAGs, especially for highly structured models (i.e., models that can be (almost) perfectly represented by a DAG). We believe that PDAGs can also be useful in domains which are complex (contain many variables and complicated dependence patterns) and sparse (represent many independence relationships).
For future research, we are planning to integrate the techniques developed in this paper within more powerful search methods, such as the ones considered by [7],[23] or [30]. Additionally, in the light of the results obtained by our method in combination with Tabu Search, it may be interesting to incorporate another operator, which could either be a classical arc reversal or some kind of specific operator to destroy h-h patterns. We also intend to work on the adaptation and application of our algorithm to real problems in the field of classification.
Acknowledgments
This work has been supported by the Spanish Ministerio de Ciencia y Tecnología (MCYT) and the Junta de Comunidades de Castilla-La Mancha under Projects TIC2001-2973-CO5-01 and PBC-02-002, respectively. We are grateful to our colleague José M. Puerta for his invaluable help with the implementation of several algorithms. We are also grateful to the three anonymous reviewers for useful comments and suggestions.