Exploiting Within-Clique Factorizations in Junction-Tree Algorithms

Julian McAuley, Tiberio Caetano
Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, PMLR 9:525-532, 2010.

Abstract

We show that the expected computational complexity of the Junction-Tree Algorithm for maximum a posteriori inference in graphical models can be improved. Our results apply whenever the potentials over maximal cliques of the triangulated graph are factored over subcliques. This is common in many real applications, as we illustrate with several examples. The new algorithms are easily implemented, and experiments show substantial speed-ups over the classical Junction-Tree Algorithm. This enlarges the class of models for which exact inference is efficient.

Cite this Paper

BibTeX
@InProceedings{pmlr-v9-mcauley10a, title = {Exploiting Within-Clique Factorizations in Junction-Tree Algorithms}, author = {McAuley, Julian and Caetano, Tiberio}, booktitle = {Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics}, pages = {525--532}, year = {2010}, editor = {Teh, Yee Whye and Titterington, Mike}, volume = {9}, series = {Proceedings of Machine Learning Research}, address = {Chia Laguna Resort, Sardinia, Italy}, month = {13--15 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v9/mcauley10a/mcauley10a.pdf}, url = {https://proceedings.mlr.press/v9/mcauley10a.html}, abstract = {We show that the expected computational complexity of the Junction-Tree Algorithm for maximum a posteriori inference in graphical models can be improved. Our results apply whenever the potentials over maximal cliques of the triangulated graph are factored over subcliques. This is common in many real applications, as we illustrate with several examples. The new algorithms are easily implemented, and experiments show substantial speed-ups over the classical Junction-Tree Algorithm. This enlarges the class of models for which exact inference is efficient.} }
Endnote
%0 Conference Paper %T Exploiting Within-Clique Factorizations in Junction-Tree Algorithms %A Julian McAuley %A Tiberio Caetano %B Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2010 %E Yee Whye Teh %E Mike Titterington %F pmlr-v9-mcauley10a %I PMLR %P 525--532 %U https://proceedings.mlr.press/v9/mcauley10a.html %V 9 %X We show that the expected computational complexity of the Junction-Tree Algorithm for maximum a posteriori inference in graphical models can be improved. Our results apply whenever the potentials over maximal cliques of the triangulated graph are factored over subcliques. This is common in many real applications, as we illustrate with several examples. The new algorithms are easily implemented, and experiments show substantial speed-ups over the classical Junction-Tree Algorithm. This enlarges the class of models for which exact inference is efficient.
RIS
TY - CPAPER TI - Exploiting Within-Clique Factorizations in Junction-Tree Algorithms AU - Julian McAuley AU - Tiberio Caetano BT - Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics DA - 2010/03/31 ED - Yee Whye Teh ED - Mike Titterington ID - pmlr-v9-mcauley10a PB - PMLR DP - Proceedings of Machine Learning Research VL - 9 SP - 525 EP - 532 L1 - http://proceedings.mlr.press/v9/mcauley10a/mcauley10a.pdf UR - https://proceedings.mlr.press/v9/mcauley10a.html AB - We show that the expected computational complexity of the Junction-Tree Algorithm for maximum a posteriori inference in graphical models can be improved. Our results apply whenever the potentials over maximal cliques of the triangulated graph are factored over subcliques. This is common in many real applications, as we illustrate with several examples. The new algorithms are easily implemented, and experiments show substantial speed-ups over the classical Junction-Tree Algorithm. This enlarges the class of models for which exact inference is efficient. ER -
APA
McAuley, J. & Caetano, T.. (2010). Exploiting Within-Clique Factorizations in Junction-Tree Algorithms. Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 9:525-532 Available from https://proceedings.mlr.press/v9/mcauley10a.html.

Related Material