Journal
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH
Volume 48, Issue -, Pages 23-65Publisher
AI ACCESS FOUNDATION
DOI: 10.1613/jair.4039
Keywords
-
Categories
Funding
- NSF [IIS-0953723, EPS-0903787, IIS-1219114]
- Academy of Finland (Finnish Centre of Excellence in Computational Inference Research COIN) [251170]
Ask authors/readers for more resources
In this paper, learning a Bayesian network structure that optimizes a scoring function for a given dataset is viewed as a shortest path problem in an implicit state-space search graph. This perspective highlights the importance of two research issues: the development of search strategies for solving the shortest path problem, and the design of heuristic functions for guiding the search. This paper introduces several techniques for addressing the issues. One is an A* search algorithm that learns an optimal Bayesian network structure by only searching the most promising part of the solution space. The others are mainly two heuristic functions. The first heuristic function represents a simple relaxation of the acyclicity constraint of a Bayesian network. Although admissible and consistent, the heuristic may introduce too much relaxation and result in a loose bound. The second heuristic function reduces the amount of relaxation by avoiding directed cycles within some groups of variables. Empirical results show that these methods constitute a promising approach to learning optimal Bayesian network structures.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available