Complexity of inference in graphical models

Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha
Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, PMLR R6:70-78, 2008.

Abstract

It is well-known that inference in graphical models is hard in the worst case, but 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 et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR6-chandrasekaran08a, title = {Complexity of inference in graphical models}, author = {Chandrasekaran, Venkat and Srebro, Nathan and Harsha, Prahladh}, booktitle = {Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence}, pages = {70--78}, year = {2008}, editor = {McAllester, David A. and Myllymäki, Petri}, volume = {R6}, series = {Proceedings of Machine Learning Research}, month = {09--12 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r6/main/assets/chandrasekaran08a/chandrasekaran08a.pdf}, url = {https://proceedings.mlr.press/r6/chandrasekaran08a.html}, abstract = {It is well-known that inference in graphical models is hard in the worst case, but 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 et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth.}, note = {Reissued by PMLR on 09 October 2024.} }
Endnote
%0 Conference Paper %T Complexity of inference in graphical models %A Venkat Chandrasekaran %A Nathan Srebro %A Prahladh Harsha %B Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2008 %E David A. McAllester %E Petri Myllymäki %F pmlr-vR6-chandrasekaran08a %I PMLR %P 70--78 %U https://proceedings.mlr.press/r6/chandrasekaran08a.html %V R6 %X It is well-known that inference in graphical models is hard in the worst case, but 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 et al. (1994), we show that low treewidth is indeed the only structural restriction that can ensure tractability. Thus, even for the "best case" graph structure, there is no inference algorithm with complexity polynomial in the treewidth. %Z Reissued by PMLR on 09 October 2024.
APA
Chandrasekaran, V., Srebro, N. & Harsha, P.. (2008). Complexity of inference in graphical models. Proceedings of the 24th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R6:70-78 Available from https://proceedings.mlr.press/r6/chandrasekaran08a.html. Reissued by PMLR on 09 October 2024.

Related Material