# Learning Factor Graphs in Polynomial Time and Sample Complexity

Pieter Abbeel, Daphne Koller, Andrew Y. Ng.

Year: 2006, Volume: 7, Issue: 64, Pages: 1743−1788

#### Abstract

We study the computational and sample complexity of parameter and
structure learning in graphical models. Our main result shows that
the class of factor graphs with bounded degree can be learned in
polynomial time and from a polynomial number of training examples,
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. Importantly,
unlike standard maximum likelihood estimation algorithms, 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. In
addition to our main result, we show that the sample complexity of
parameter learning in graphical models has an *O*(1) dependence
on the number of variables in the model when using the KL-divergence
normalized by the number of variables as the performance criterion.