Tensor Variable Elimination for Plated Factor Graphs

Fritz Obermeyer, Eli Bingham, Martin Jankowiak, Neeraj Pradhan, Justin Chiu, Alexander Rush, Noah Goodman
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:4871-4880, 2019.

Abstract

A wide class of machine learning algorithms can be reduced to variable elimination on factor graphs. While factor graphs provide a unifying notation for these algorithms, they do not provide a compact way to express repeated structure when compared to plate diagrams for directed graphical models. To exploit efficient tensor algebra in graphs with plates of variables, we generalize undirected factor graphs to plated factor graphs and variable elimination to a tensor variable elimination algorithm that operates directly on plated factor graphs. Moreover, we generalize complexity bounds based on treewidth and characterize the class of plated factor graphs for which inference is tractable. As an application, we integrate tensor variable elimination into the Pyro probabilistic programming language to enable exact inference in discrete latent variable models with repeated structure. We validate our methods with experiments on both directed and undirected graphical models, including applications to polyphonic music modeling, animal movement modeling, and latent sentiment analysis.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-obermeyer19a, title = {Tensor Variable Elimination for Plated Factor Graphs}, author = {Obermeyer, Fritz and Bingham, Eli and Jankowiak, Martin and Pradhan, Neeraj and Chiu, Justin and Rush, Alexander and Goodman, Noah}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {4871--4880}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/obermeyer19a/obermeyer19a.pdf}, url = {https://proceedings.mlr.press/v97/obermeyer19a.html}, abstract = {A wide class of machine learning algorithms can be reduced to variable elimination on factor graphs. While factor graphs provide a unifying notation for these algorithms, they do not provide a compact way to express repeated structure when compared to plate diagrams for directed graphical models. To exploit efficient tensor algebra in graphs with plates of variables, we generalize undirected factor graphs to plated factor graphs and variable elimination to a tensor variable elimination algorithm that operates directly on plated factor graphs. Moreover, we generalize complexity bounds based on treewidth and characterize the class of plated factor graphs for which inference is tractable. As an application, we integrate tensor variable elimination into the Pyro probabilistic programming language to enable exact inference in discrete latent variable models with repeated structure. We validate our methods with experiments on both directed and undirected graphical models, including applications to polyphonic music modeling, animal movement modeling, and latent sentiment analysis.} }
Endnote
%0 Conference Paper %T Tensor Variable Elimination for Plated Factor Graphs %A Fritz Obermeyer %A Eli Bingham %A Martin Jankowiak %A Neeraj Pradhan %A Justin Chiu %A Alexander Rush %A Noah Goodman %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-obermeyer19a %I PMLR %P 4871--4880 %U https://proceedings.mlr.press/v97/obermeyer19a.html %V 97 %X A wide class of machine learning algorithms can be reduced to variable elimination on factor graphs. While factor graphs provide a unifying notation for these algorithms, they do not provide a compact way to express repeated structure when compared to plate diagrams for directed graphical models. To exploit efficient tensor algebra in graphs with plates of variables, we generalize undirected factor graphs to plated factor graphs and variable elimination to a tensor variable elimination algorithm that operates directly on plated factor graphs. Moreover, we generalize complexity bounds based on treewidth and characterize the class of plated factor graphs for which inference is tractable. As an application, we integrate tensor variable elimination into the Pyro probabilistic programming language to enable exact inference in discrete latent variable models with repeated structure. We validate our methods with experiments on both directed and undirected graphical models, including applications to polyphonic music modeling, animal movement modeling, and latent sentiment analysis.
APA
Obermeyer, F., Bingham, E., Jankowiak, M., Pradhan, N., Chiu, J., Rush, A. & Goodman, N.. (2019). Tensor Variable Elimination for Plated Factor Graphs. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:4871-4880 Available from https://proceedings.mlr.press/v97/obermeyer19a.html.

Related Material