Variable Elimination in the Fourier Domain

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.

以紧凑形式表示复杂高维概率分布的能力是图模型领域的关键见解之一。分解表示在机器学习中无处不在，并带来了主要的计算优势。我们探索一种基于离散傅里叶表示的不同类型的紧凑表示，对基于条件独立性的经典方法进行补充。我们表明，一大类概率图模型具有紧凑的傅里叶表示。这一理论结果开辟了一种全新的近似概率分布的方法。我们通过将其应用于变量消除算法来展示这种方法的重要性。与传统的桶表示和其他近似推理算法相比，我们获得了显著的改进。