Variable Elimination in the Fourier Domain

Yexiang Xue, Stefano Ermon, Ronan Le Bras,  Carla, Bart Selman
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:285-294, 2016.

Abstract

The ability to represent complex high dimensional probability distributions in a compact form is one of the key insights in the field of graphical models. Factored representations are ubiquitous in machine learning and lead to major computational advantages. We explore a different type of compact representation based on discrete Fourier representations, complementing the classical approach based on conditional independencies. We show that a large class of probabilistic graphical models have a compact Fourier representation. This theoretical result opens up an entirely new way of approximating a probability distribution. We demonstrate the significance of this approach by applying it to the variable elimination algorithm. Compared with the traditional bucket representation and other approximate inference algorithms, we obtain significant improvements.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-xue16, title = {Variable Elimination in the Fourier Domain}, author = {Xue, Yexiang and Ermon, Stefano and Bras, Ronan Le and Carla, and Selman, Bart}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {285--294}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/xue16.pdf}, url = {https://proceedings.mlr.press/v48/xue16.html}, abstract = {The ability to represent complex high dimensional probability distributions in a compact form is one of the key insights in the field of graphical models. Factored representations are ubiquitous in machine learning and lead to major computational advantages. We explore a different type of compact representation based on discrete Fourier representations, complementing the classical approach based on conditional independencies. We show that a large class of probabilistic graphical models have a compact Fourier representation. This theoretical result opens up an entirely new way of approximating a probability distribution. We demonstrate the significance of this approach by applying it to the variable elimination algorithm. Compared with the traditional bucket representation and other approximate inference algorithms, we obtain significant improvements.} }
Endnote
%0 Conference Paper %T Variable Elimination in the Fourier Domain %A Yexiang Xue %A Stefano Ermon %A Ronan Le Bras %A Carla %A Bart Selman %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-xue16 %I PMLR %P 285--294 %U https://proceedings.mlr.press/v48/xue16.html %V 48 %X The ability to represent complex high dimensional probability distributions in a compact form is one of the key insights in the field of graphical models. Factored representations are ubiquitous in machine learning and lead to major computational advantages. We explore a different type of compact representation based on discrete Fourier representations, complementing the classical approach based on conditional independencies. We show that a large class of probabilistic graphical models have a compact Fourier representation. This theoretical result opens up an entirely new way of approximating a probability distribution. We demonstrate the significance of this approach by applying it to the variable elimination algorithm. Compared with the traditional bucket representation and other approximate inference algorithms, we obtain significant improvements.
RIS
TY - CPAPER TI - Variable Elimination in the Fourier Domain AU - Yexiang Xue AU - Stefano Ermon AU - Ronan Le Bras AU - Carla AU - Bart Selman BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-xue16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 285 EP - 294 L1 - http://proceedings.mlr.press/v48/xue16.pdf UR - https://proceedings.mlr.press/v48/xue16.html AB - The ability to represent complex high dimensional probability distributions in a compact form is one of the key insights in the field of graphical models. Factored representations are ubiquitous in machine learning and lead to major computational advantages. We explore a different type of compact representation based on discrete Fourier representations, complementing the classical approach based on conditional independencies. We show that a large class of probabilistic graphical models have a compact Fourier representation. This theoretical result opens up an entirely new way of approximating a probability distribution. We demonstrate the significance of this approach by applying it to the variable elimination algorithm. Compared with the traditional bucket representation and other approximate inference algorithms, we obtain significant improvements. ER -
APA
Xue, Y., Ermon, S., Bras, R.L., Carla, & Selman, B.. (2016). Variable Elimination in the Fourier Domain. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:285-294 Available from https://proceedings.mlr.press/v48/xue16.html.

Related Material