Convex structure learning for Bayesian networks: polynomial feature selection and approximate ordering
- Yuhong Guo
- Dale Schuurmans, AICML
We present a new approach to learning the structure and parameters of a Bayesian network based on regularized estimation in an exponential family representation. Here we show that, given a fixed variable order, the optimal structure and parameters can be learned efficiently, even without restricting the size of the parent variable sets. We then consider the problem of optimizing the variable order for a given set of features. This is still a computationally hard problem, but we present a convex relaxation that yields an optimal “soft” ordering in polynomial time. One novel aspect of the approach is that we do not perform a discrete search over DAG structures, nor over variable orders, but instead solve a continuous convex relaxation that can then be rounded to obtain a valid network structure. We conduct an experimental comparison against standard structure search procedures over standard objectives, which cope with local minima, and evaluate the advantages of using convex relaxations that reduce the effects of local minima.
Citation
Y. Guo, D. Schuurmans. "Convex structure learning for Bayesian networks: polynomial feature selection and approximate ordering". Conference on Uncertainty in Artificial Intelligence (UAI), January 2006.| Keywords: | machine learning |
| Category: | In Conference |
BibTeX
@incollection{Guo+Schuurmans:UAI06,
author = {Yuhong Guo and Dale Schuurmans},
title = {Convex structure learning for Bayesian networks: polynomial feature
selection and approximate ordering},
booktitle = {Conference on Uncertainty in Artificial Intelligence (UAI)},
year = 2006,
}Last Updated: April 24, 2007Submitted by William Thorne
