A Caltech Library Service

Complexity of Inference in Graphical Models

Chandrasekaran, Venkat and Srebro, Nathan and Harsha, Prahladh (2010) Complexity of Inference in Graphical Models. .

PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Graphical models provide a convenient representation for a broad class of probability distributions. Due to their powerful and sophisticated modeling capabilities, such models have found numerous applications in machine learning and other areas. In this paper we consider the complexity of commonly encountered tasks involving graphical models such as the computation of the mode of a posterior probability distribution (i.e., MAP estimation), and the computation of marginal probabilities or the partition function. It is well-known that such inference problems are hard in the worst case, but are tractable for models with bounded treewidth. We ask whether treewidth is the only structural criterion of the underlying graph that enables tractable inference. In other words, is there some class of structures with unbounded treewidth in which inference is tractable? Subject to a combinatorial hypothesis due to Robertson, Seymour, and Thomas (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. More precisely we show that for every growing family of graphs indexed by tree-width, there exists a choice of potential functions such that the corresponding inference problem is intractable. Thus even for the "best case" graph structures of high treewidth, there is no polynomial-time inference algorithm. Our analysis employs various concepts from complexity theory and graph theory, with graph minors playing a prominent role.

Item Type:Report or Paper (Technical Report)
Related URLs:
URLURL TypeDescription ItemConference Paper
Additional Information:Portions of this work were done while the first and third authors were at the Toyota Technological Institute in Chicago. A preliminary version of this paper appeared in Proc. 24th Conference on Uncertainty in Artificial Intelligence (UAI), 2008 (Chandrasekaran et al., 2008). We would like to thank Lance Fortnow and Jaikumar Radhakrishnan for helpful discussions and referring us to the result of Tamassia and Tollis (1989).
Subject Keywords:Graphical models; Markov random fields; treewidth; graph minor; complexity; inference
Record Number:CaltechAUTHORS:20121011-133225017
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34854
Deposited By: Tony Diaz
Deposited On:11 Oct 2012 20:59
Last Modified:03 Oct 2019 04:22

Repository Staff Only: item control page