Se-Jun Park (KAIST EE), Eun-Ho Yang (KAIST CS), Se-Young Yun (KAIST IE), Jin-Woo Shin (KAIST EE) accepted at 36th International Conference on Machine Learning (ICML 2019)

Title: Spectral Approximate Inference

Authors: SejJun Park, Eun-hHo Yang, Se-Young Yun, Jin-wWoo Shin

 Graphical models (GMs) have been successfully applied to various applications of machine learning. Given a GM, computing its partition function is the most essential inference task, but it is computationally intractable in general. To address the issue, iterative approximation algorithms exploring certain local structure/consistency of GM have been investigated as popular choices in practice. However, due to their local/iterative nature, they often output poor approximations or even do not converge, e.g., in low-temperature regimes (hard instances of large parameters). To overcome the limitation, we propose a novel approach utilizing the global spectral feature of GM. Our contribution is two-fold: (a) we first propose a fully polynomial-time approximation scheme (FPTAS) for approximating the partition function of GM associating with a low-rank coupling matrix; (b) for general high-rank GMs, we design a spectral mean-field scheme utilizing (a) as a subroutine, where it approximates a high-rank GM into a product of rank-1 GMs for an efficient approximation of the partition function. The proposed algorithm is more robust in its running time and accuracy than prior methods, i.e., neither suffers from the convergence issue nor depends on hard local structures. Our experiments demonstrate that it indeed outperforms baselines, in particular, significantly in the low-temperature regimes.

Figure1. An illustration of the spectral approximate inference for the partition function approximation
Show List