Timezone: »
Markov Chain Monte Carlo (MCMC) and Belief Propagation (BP) are the most popular algorithms for computational inference in Graphical Models (GM). In principle, MCMC is an exact probabilistic method which, however, often suffers from exponentially slow mixing. In contrast, BP is a deterministic method, which is typically fast, empirically very successful, however in general lacking control of accuracy over loopy graphs. In this paper, we introduce MCMC algorithms correcting the approximation error of BP, i.e., we provide a way to compensate for BP errors via a consecutive BP-aware MCMC. Our framework is based on the Loop Calculus (LC) approach which allows to express the BP error as a sum of weighted generalized loops. Although the full series is computationally intractable, it is known that a truncated series, summing up all 2-regular loops, is computable in polynomial-time for planar pair-wise binary GMs and it also provides a highly accurate approximation empirically. Motivated by this, we, first, propose a polynomial-time approximation MCMC scheme for the truncated series of general (non-planar) pair-wise binary models. Our main idea here is to use the Worm algorithm, known to provide fast mixing in other (related) problems, and then design an appropriate rejection scheme to sample 2-regular loops. Furthermore, we also design an efficient rejection-free MCMC scheme for approximating the full series. The main novelty underlying our design is in utilizing the concept of cycle basis, which provides an efficient decomposition of the generalized loops. In essence, the proposed MCMC schemes run on transformed GM built upon the non-trivial BP solution, and our experiments show that this synthesis of BP and MCMC outperforms both direct MCMC and bare BP schemes.
Author Information
Sungsoo Ahn (KAIST)
Michael Chertkov (Los Alamos National Laboratory)
Jinwoo Shin (KAIST)
More from the Same Authors
-
2021 : SURF: Semi-supervised Reward Learning with Data Augmentation for Feedback-efficient Preference-based Reinforcement Learning »
Jongjin Park · Younggyo Seo · Jinwoo Shin · Honglak Lee · Pieter Abbeel · Kimin Lee -
2022 : STUNT: Few-shot Tabular Learning with Self-generated Tasks from Unlabeled Tables »
Jaehyun Nam · Jihoon Tack · Kyungmin Lee · Hankook Lee · Jinwoo Shin -
2022 : Dynamics-Augmented Decision Transformer for Offline Dynamics Generalization »
Changyeon Kim · Junsu Kim · Younggyo Seo · Kimin Lee · Honglak Lee · Jinwoo Shin -
2022 : Unsupervised Meta-learning via Few-shot Pseudo-supervised Contrastive Learning »
Huiwon Jang · Hankook Lee · Jinwoo Shin -
2023 Poster: Multi-scale Diffusion Denoised Smoothing »
Jongheon Jeong · Jinwoo Shin -
2023 Poster: Slimmed Asymmetrical Contrastive Learning and Cross Distillation for Lightweight Model Training »
Jian Meng · Li Yang · Kyungmin Lee · Jinwoo Shin · Deliang Fan · Jae-sun Seo -
2023 Poster: Modality-Agnostic Self-Supervised Learning with Meta-Learned Masked Auto-Encoder »
Huiwon Jang · Jihoon Tack · Daewon Choi · Jongheon Jeong · Jinwoo Shin -
2023 Poster: Learning Large-scale Neural Fields via Context Pruned Meta-Learning »
Jihoon Tack · Subin Kim · Sihyun Yu · Jaeho Lee · Jinwoo Shin · Jonathan Richard Schwarz -
2023 Poster: S-CLIP: Semi-supervised Vision-Language Pre-training using Few Specialist Captions »
Sangwoo Mo · Minkyu Kim · Kyungmin Lee · Jinwoo Shin -
2023 Poster: Guide Your Agent with Adaptive Multimodal Rewards »
Changyeon Kim · Younggyo Seo · Hao Liu · Lisa Lee · Jinwoo Shin · Honglak Lee · Kimin Lee -
2023 Poster: Accelerating Reinforcement Learning with Value-Conditional State Entropy Exploration »
Dongyoung Kim · Jinwoo Shin · Pieter Abbeel · Younggyo Seo -
2023 Poster: Collaborative Score Distillation for Consistent Visual Synthesis »
Subin Kim · Kyungmin Lee · June Suk Choi · Jongheon Jeong · Kihyuk Sohn · Jinwoo Shin -
2022 Poster: NOTE: Robust Continual Test-time Adaptation Against Temporal Correlation »
Taesik Gong · Jongheon Jeong · Taewon Kim · Yewon Kim · Jinwoo Shin · Sung-Ju Lee -
2022 Poster: RényiCL: Contrastive Representation Learning with Skew Rényi Divergence »
Kyungmin Lee · Jinwoo Shin -
2022 Poster: Meta-Learning with Self-Improving Momentum Target »
Jihoon Tack · Jongjin Park · Hankook Lee · Jaeho Lee · Jinwoo Shin -
2022 Poster: Scalable Neural Video Representations with Learnable Positional Features »
Subin Kim · Sihyun Yu · Jaeho Lee · Jinwoo Shin -
2021 Poster: Improving Transferability of Representations via Augmentation-Aware Self-Supervision »
Hankook Lee · Kibok Lee · Kimin Lee · Honglak Lee · Jinwoo Shin -
2021 Poster: Landmark-Guided Subgoal Generation in Hierarchical Reinforcement Learning »
Junsu Kim · Younggyo Seo · Jinwoo Shin -
2021 Poster: RoMA: Robust Model Adaptation for Offline Model-based Optimization »
Sihyun Yu · Sungsoo Ahn · Le Song · Jinwoo Shin -
2021 Poster: Scaling Neural Tangent Kernels via Sketching and Random Features »
Amir Zandieh · Insu Han · Haim Avron · Neta Shoham · Chaewon Kim · Jinwoo Shin -
2021 Poster: Meta-Learning Sparse Implicit Neural Representations »
Jaeho Lee · Jihoon Tack · Namhoon Lee · Jinwoo Shin -
2021 Poster: Object-Aware Regularization for Addressing Causal Confusion in Imitation Learning »
Jongjin Park · Younggyo Seo · Chang Liu · Li Zhao · Tao Qin · Jinwoo Shin · Tie-Yan Liu -
2021 Poster: Object-aware Contrastive Learning for Debiased Scene Representation »
Sangwoo Mo · Hyunwoo Kang · Kihyuk Sohn · Chun-Liang Li · Jinwoo Shin -
2021 Poster: SmoothMix: Training Confidence-calibrated Smoothed Classifiers for Certified Robustness »
Jongheon Jeong · Sejun Park · Minkyu Kim · Heung-Chang Lee · Do-Guk Kim · Jinwoo Shin -
2020 Poster: Distribution Aligning Refinery of Pseudo-label for Imbalanced Semi-supervised Learning »
Jaehyung Kim · Youngbum Hur · Sejun Park · Eunho Yang · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Time-Reversal Symmetric ODE Network »
In Huh · Eunho Yang · Sung Ju Hwang · Jinwoo Shin -
2020 Poster: Learning from Failure: De-biasing Classifier from Biased Classifier »
Junhyun Nam · Hyuntak Cha · Sungsoo Ahn · Jaeho Lee · Jinwoo Shin -
2020 Poster: CSI: Novelty Detection via Contrastive Learning on Distributionally Shifted Instances »
Jihoon Tack · Sangwoo Mo · Jongheon Jeong · Jinwoo Shin -
2020 Poster: Guiding Deep Molecular Optimization with Genetic Exploration »
Sungsoo Ahn · Junsu Kim · Hankook Lee · Jinwoo Shin -
2020 Poster: Consistency Regularization for Certified Robustness of Smoothed Classifiers »
Jongheon Jeong · Jinwoo Shin -
2020 Poster: Trajectory-wise Multiple Choice Learning for Dynamics Generalization in Reinforcement Learning »
Younggyo Seo · Kimin Lee · Ignasi Clavera Gilaberte · Thanard Kurutach · Jinwoo Shin · Pieter Abbeel -
2020 Poster: Learning Bounds for Risk-sensitive Learning »
Jaeho Lee · Sejun Park · Jinwoo Shin -
2020 Poster: Few-shot Visual Reasoning with Meta-Analogical Contrastive Learning »
Youngsung Kim · Jinwoo Shin · Eunho Yang · Sung Ju Hwang -
2019 Poster: Mining GOLD Samples for Conditional GANs »
Sangwoo Mo · Chiheon Kim · Sungwoong Kim · Minsu Cho · Jinwoo Shin -
2018 : Lunch & Posters »
Haytham Fayek · German Parisi · Brian Xu · Pramod Kaushik Mudrakarta · Sophie Cerf · Sarah Wassermann · Davit Soselia · Rahaf Aljundi · Mohamed Elhoseiny · Frantzeska Lavda · Kevin J Liang · Arslan Chaudhry · Sanmit Narvekar · Vincenzo Lomonaco · Wesley Chung · Michael Chang · Ying Zhao · Zsolt Kira · Pouya Bashivan · Banafsheh Rafiee · Oleksiy Ostapenko · Andrew Jones · Christos Kaplanis · Sinan Kalkan · Dan Teng · Xu He · Vincent Liu · Somjit Nath · Sungsoo Ahn · Ting Chen · Shenyang Huang · Yash Chandak · Nathan Sprague · Martin Schrimpf · Tony Kendall · Jonathan Richard Schwarz · Michael Li · Yunshu Du · Yen-Chang Hsu · Samira Abnar · Bo Wang -
2018 Poster: A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks »
Kimin Lee · Kibok Lee · Honglak Lee · Jinwoo Shin -
2018 Poster: Stochastic Chebyshev Gradient Descent for Spectral Optimization »
Insu Han · Haim Avron · Jinwoo Shin -
2018 Spotlight: A Simple Unified Framework for Detecting Out-of-Distribution Samples and Adversarial Attacks »
Kimin Lee · Kibok Lee · Honglak Lee · Jinwoo Shin -
2018 Spotlight: Stochastic Chebyshev Gradient Descent for Spectral Optimization »
Insu Han · Haim Avron · Jinwoo Shin -
2018 Poster: Learning to Specialize with Knowledge Distillation for Visual Question Answering »
Jonghwan Mun · Kimin Lee · Jinwoo Shin · Bohyung Han -
2017 Poster: Gauging Variational Inference »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Poster: Synthesis of MCMC and Belief Propagation »
Sungsoo Ahn · Michael Chertkov · Jinwoo Shin -
2016 Poster: Interaction Screening: Efficient and Sample-Optimal Learning of Ising Models »
Marc Vuffray · Sidhant Misra · Andrey Lokhov · Michael Chertkov -
2015 Poster: Minimum Weight Perfect Matching via Blossom Belief Propagation »
Sungsoo Ahn · Sejun Park · Michael Chertkov · Jinwoo Shin -
2015 Spotlight: Minimum Weight Perfect Matching via Blossom Belief Propagation »
Sungsoo Ahn · Sejun Park · Michael Chertkov · Jinwoo Shin -
2013 Poster: A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles »
Jinwoo Shin · Andrew E Gelfand · Misha Chertkov