Timezone: »
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.
Author Information
Sejun Park (KAIST)
Eunho Yang (KAIST,AITRICS)
Se-Young Yun (KAIST)
Jinwoo Shin (KAIST, AITRICS)
Related Events (a corresponding poster, oral, or spotlight)
-
2019 Poster: Spectral Approximate Inference »
Fri Jun 14th 01:30 -- 04:00 AM Room Pacific Ballroom
More from the Same Authors
-
2020 Poster: Cost-Effective Interactive Attention Learning with Neural Attention Processes »
Jay Heo · Junhyeon Park · Hyewon Jeong · Kwang Joon Kim · Juho Lee · Eunho Yang · Sung Ju Hwang -
2020 Poster: Self-supervised Label Augmentation via Input Transformations »
Hankook Lee · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Context-aware Dynamics Model for Generalization in Model-Based Reinforcement Learning »
Kimin Lee · Younggyo Seo · Seunghyun Lee · Honglak Lee · Jinwoo Shin -
2020 Poster: Polynomial Tensor Sketch for Element-wise Function of Low-Rank Matrix »
Insu Han · Haim Avron · Jinwoo Shin -
2020 Poster: Learning What to Defer for Maximum Independent Sets »
Sungsoo Ahn · Younggyo Seo · Jinwoo Shin -
2020 Poster: Adversarial Neural Pruning with Latent Vulnerability Suppression »
Divyam Madaan · Jinwoo Shin · Sung Ju Hwang -
2019 Poster: Robust Inference via Generative Classifiers for Handling Noisy Labels »
Kimin Lee · Sukmin Yun · Kibok Lee · Honglak Lee · Bo Li · Jinwoo Shin -
2019 Poster: Learning What and Where to Transfer »
Yunhun Jang · Hankook Lee · Sung Ju Hwang · Jinwoo Shin -
2019 Oral: Robust Inference via Generative Classifiers for Handling Noisy Labels »
Kimin Lee · Sukmin Yun · Kibok Lee · Honglak Lee · Bo Li · Jinwoo Shin -
2019 Oral: Learning What and Where to Transfer »
Yunhun Jang · Hankook Lee · Sung Ju Hwang · Jinwoo Shin -
2019 Poster: Training CNNs with Selective Allocation of Channels »
Jongheon Jeong · Jinwoo Shin -
2019 Poster: Trimming the $\ell_1$ Regularizer: Statistical Analysis, Optimization, and Applications to Deep Learning »
Jihun Yun · Peng Zheng · Eunho Yang · Aurelie Lozano · Aleksandr Aravkin -
2019 Oral: Training CNNs with Selective Allocation of Channels »
Jongheon Jeong · Jinwoo Shin -
2019 Oral: Trimming the $\ell_1$ Regularizer: Statistical Analysis, Optimization, and Applications to Deep Learning »
Jihun Yun · Peng Zheng · Eunho Yang · Aurelie Lozano · Aleksandr Aravkin -
2018 Poster: Deep Asymmetric Multi-task Feature Learning »
Hae Beom Lee · Eunho Yang · Sung Ju Hwang -
2018 Poster: Bucket Renormalization for Approximate Inference »
Sungsoo Ahn · Michael Chertkov · Adrian Weller · Jinwoo Shin -
2018 Oral: Deep Asymmetric Multi-task Feature Learning »
Hae Beom Lee · Eunho Yang · Sung Ju Hwang -
2018 Oral: Bucket Renormalization for Approximate Inference »
Sungsoo Ahn · Michael Chertkov · Adrian Weller · Jinwoo Shin -
2017 Poster: Faster Greedy MAP Inference for Determinantal Point Processes »
Insu Han · Prabhanjan Kambadur · Kyoungsoo Park · Jinwoo Shin -
2017 Poster: Sparse + Group-Sparse Dirty Models: Statistical Guarantees without Unreasonable Conditions and a Case for Non-Convexity »
Eunho Yang · Aurelie Lozano -
2017 Poster: Confident Multiple Choice Learning »
Kimin Lee · Changho Hwang · KyoungSoo Park · Jinwoo Shin -
2017 Talk: Confident Multiple Choice Learning »
Kimin Lee · Changho Hwang · KyoungSoo Park · Jinwoo Shin -
2017 Talk: Sparse + Group-Sparse Dirty Models: Statistical Guarantees without Unreasonable Conditions and a Case for Non-Convexity »
Eunho Yang · Aurelie Lozano -
2017 Talk: Faster Greedy MAP Inference for Determinantal Point Processes »
Insu Han · Prabhanjan Kambadur · Kyoungsoo Park · Jinwoo Shin -
2017 Poster: Ordinal Graphical Models: A Tale of Two Approaches »
ARUN SAI SUGGALA · Eunho Yang · Pradeep Ravikumar -
2017 Talk: Ordinal Graphical Models: A Tale of Two Approaches »
ARUN SAI SUGGALA · Eunho Yang · Pradeep Ravikumar