|
|
|
|
PAC-learning bounded tree-width Graphical Models
Mukund Narasimhan, Jeff Bilmes
Abstract:
We show that the class of strongly connected graphical models with treewidth at most k can be properly eficiently PAC-learnt with respect to the Kullback-Leibler Divergence. Previous approaches to this problem, such as those of Chow ([1]), and Ho gen ([7]) have shown that this class is PAClearnable by reducing it to a combinatorial optimization problem. However, for k > 1, this problem is NPcomplete ([15]), and so unless P=NP, these approaches will take exponential amounts of time. Our approach differs significantly from these, in that it first attempts to find approximate conditional independencies by solving (polynomially many) submodular optimization problems, and then using a dynamic programming formulation to combine the approximate conditional independence information to derive a graphical model with underlying graph of the tree-width speci ed. This gives us an eficient (polynomial time in the number of random variables) PAC-learning algorithm which requires only polynomial number of samples of the true distribution, and only polynomial running time.
Keywords: null
Pages: 410-417
PS Link:
PDF Link: /papers/04/p410-narasimhan.pdf
BibTex:
@INPROCEEDINGS{Narasimhan04,
AUTHOR = "Mukund Narasimhan
and Jeff Bilmes",
TITLE = "PAC-learning bounded tree-width Graphical Models",
BOOKTITLE = "Proceedings of the Proceedings of the Twentieth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-04)",
PUBLISHER = "AUAI Press",
ADDRESS = "Arlington, Virginia",
YEAR = "2004",
PAGES = "410-417"
}
|
|
