|
|
Finding Optimal Bayesian Network Structures with Constraints Learned from Data
Xiannian Fan, Brandon Malone, Changhe Yuan
Abstract:
Several recent algorithms for learning Bayesian
network structures first calculate potentially op-
timal parent sets (POPS) for all variables and
then use various optimization techniques to find
a set of POPS, one for each variable, that con-
stitutes an optimal network structure. This pa-
per makes the observation that there is useful
information implicit in the POPS. Specifically,
the POPS of a variable constrain its parent can-
didates. Moreover, the parent candidates of all
variables together give a directed cyclic graph,
which often decomposes into a set of strongly
connected components (SCCs). Each SCC cor-
responds to a smaller subproblem which can be
solved independently of the others. Our results
show that solving the constrained subproblems
significantly improves the efficiency and scala-
bility of heuristic search-based structure learning
algorithms. Further, we show that by consider-
ing only the top p POPS of each variable, we
quickly find provably very high quality networks
for large datasets.
Keywords:
Pages: 200-209
PS Link:
PDF Link: /papers/14/p200-fan.pdf
BibTex:
@INPROCEEDINGS{Fan14,
AUTHOR = "Xiannian Fan
and Brandon Malone and Changhe Yuan",
TITLE = "Finding Optimal Bayesian Network Structures with Constraints Learned from Data",
BOOKTITLE = "Proceedings of the Thirtieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-14)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2014",
PAGES = "200--209"
}
|
|