Evaluating Anytime Algorithms for Learning Optimal Bayesian Networks
  Exact algorithms for learning Bayesian networks guarantee to find provably
optimal networks. However, they may fail in difficult learning tasks due to
limited time or memory. In this research we adapt several anytime heuristic
search-based algorithms to learn Bayesian networks. These algorithms find
high-quality solutions quickly, and continually improve the incumbent solution
or prove its optimality before resources are exhausted. Empirical results show
that the anytime window A* algorithm usually finds higher-quality, often
optimal, networks more quickly than other approaches. The results also show
that, surprisingly, while generating networks with few parents per variable are
structurally simpler, they are harder to learn than complex generating networks
with more parents per variable.
