Orderingbased Search: A Simple and Effective Algorithm for Learning Bayesian Networks (2005)by M. Teyssier and D. Koller
Abstract:
One of the basic tasks for Bayesian networks (BNs) is that of learning a network structure from data. The BNlearning problem is NP hard, so the standard solution is heuristic search. Many approaches have been proposed for this task, but only a very small number outperform the baseline of greedy hillclimbing with tabu lists; moreover, many of the proposed algorithms are quite complex and hard to implement. In this paper, we propose a very simple and easytoimplement method for addressing this task. Our approach is based on the wellknown fact that the best network (of bounded indegree) consistent with a given node ordering can be found very efficiently. We therefore propose a search not over the space of structures, but over the space of orderings, selecting for each ordering the best network consistent with it. This search space is much smaller, makes more global search steps, has a lower branching factor, and avoids costly acyclicity checks. We present results for this algorithm on both synthetic and real data sets, evaluating both the score of the network found and in the running time. We show that orderingbased search outperforms the standard baseline, and is competitive with recent algorithms that are much harder to implement.
Download Information
M. Teyssier and D. Koller (2005). "Orderingbased Search: A Simple and Effective Algorithm for Learning Bayesian Networks." Proceedings of the Twentyfirst Conference on Uncertainty in AI (UAI) (pp. 584590).


Bibtex citation
@inproceedings{Teyssier+Koller:UAI05,
title = {Orderingbased Search: A Simple and Effective Algorithm for Learning Bayesian Networks},
author = {M. Teyssier and D. Koller},
booktitle = {Proceedings of the Twentyfirst Conference on Uncertainty in AI (UAI)},
address = {Edinburgh, Scottland, UK},
month = {July},
year = 2005,
pages = {584590},
}
full list
