My home page
Biography
Research
Publications
My group
Courses
Professional activities
FAQ
Personal
Papers

Daphne Koller Publications

Learning Factor Graphs in Polynomial Time & Sample Complexity (2005)

by P. Abbeel, D. Koller, and A.Y. Ng
[newer version, 2006]

Abstract: We study computational and sample complexity of parameter and structure learning in graphical models. Our main result shows that the class of factor graphs with bounded factor size and bounded connectivity can be learned in polynomial time and polynomial number of samples, assuming that the data is generated by a network in this class. This result covers both parameter estimation for a known network structure and structure learning. It implies as a corollary that we can learn factor graphs for both Bayesian networks and Markov networks of bounded degree, in polynomial time and sample complexity. Unlike maximum likelihood estimation, our method does not require inference in the underlying network, and so applies to networks where inference is intractable. We also show that the error of our learned model degrades gracefully when the generating distribution is not a member of the target class of networks.

Download Information

P. Abbeel, D. Koller, and A.Y. Ng (2005). "Learning Factor Graphs in Polynomial Time & Sample Complexity." Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI) (pp. 1-9). pdf ps.gz

Bibtex citation

@inproceedings{Abbeel+al:UAI05,
  title = {Learning Factor Graphs in Polynomial Time \& Sample Complexity},
  author = {P. Abbeel and D. Koller and A.Y. Ng},
  booktitle = {Proceedings of the Twenty-first Conference on Uncertainty in AI (UAI)},  
  address = {Edinburgh, Scottland, UK},
  month = {July},
  year = 2005,
  pages = {1--9},
}

full list
Click to go to robotics Click to go to theory Click to go to CS Stanford Click to go to Stanford's Webpage
home | biography | research | papers | my group
courses | professional activities | FAQ | personal