Variable Elimination in the Fourier Domain
This work provides a new foundational approach for approximate inference in machine learning, potentially impacting a broad range of applications.
The paper tackles the problem of representing high-dimensional probability distributions compactly by introducing a Fourier domain representation for probabilistic graphical models, and demonstrates significant improvements in the variable elimination algorithm compared to traditional methods.
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.