Graphical Model

Graphical model (GM) has been one of powerful paradigms for succinct representations of joint probability distributions in various scientific fields including information theory, statistical physics and artificial intelligence. GM represents a joint distribution of some random variables by a graph structured model where each vertex corresponds to a random variable and each edge captures the conditional dependence between random variables. We have worked on solving inference and learning problems arising in GMs and related applications.

Optimality of BP

Belief Propagation (BP) is the most popular deterministic algorithm for solving intractable computational inference in GM. BP has shown remarkable performances in practice, but its theoretical understanding is not fully established yet. We found several examples where BP can guarantee provably the desired optimality: independent set, matching, shortest path, traveling salesman, cycle packing, vertex/edge cover, network flow and crowd-sourcing.

Efficient Learning for Crowdsourced Regression

Jungseul Ok, Sewoong Oh, Jinwoo Shin, Yunhun Jang and Yung Yi
submitted

Optimality of Belief Propagation for Crowdsourced Classification

Jungseul Ok, Sewoong Oh, Jinwoo Shin and Yung Yi
ICML 2016

Minimum Weight Perfect Matching via Blossom Belief Propagation

Sungsoo Ahn, Sejun Park, Michael Chertkov and Jinwoo Shin
NIPS 2015

Max-Product Belief Propagation for Linear Programming: Applications to Combinatorial Optimization

Sejun Park and Jinwoo Shin
UAI 2015

A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles

Jinwoo Shin, Andrew E. Gelfand and Michael Chertkov
NIPS 2013

Counting Independent Sets using the Bethe Approximation

Venkat Chandrasekaran, Misha Chertkov, David Gamarnik, Devavrat Shah and Jinwoo Shin
SIAM Journal on Discrete Mathematics, vol. 25, no. 2, pp. 1012-1034, 2011

(edited by Jinwoo Shin, Mar 2017)

Fast Mixing MCMC

Markov Chain Monte Carlo (MCMC) is the most popular randomized algorithm for solving intractable computational inference in GM. In contrast to BP, MCMC is an exact probabilistic method which, however, often suffers from (exponentially) slow mixing. We found several examples/regimes of fast (polynomial-time) mixing MCMCs.

Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models

Sejun Park, Yunhun Jang, Andreas Galanis, Jinwoo Shin, Daniel Stefankovic and Eric Vigoda
AISTATS 2017

Synthesis of MCMC and Belief Propagation (code)

Sungsoo Ahn, Michael Chertkov, and Jinwoo Shin
NIPS 2016

Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets

Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, and Eric Vigoda
FOCS 2011

Distributed Averaging via Lifted Markov Chains

Kyomin Jung, Devavrat Shah, and Jinwoo Shin
IEEE Transactions on Information Theory, vol. 56, no. 1, pp. 634-647, 2010

Dynamics in Congestion Games

Devavrat Shah and Jinwoo Shin
SIGMETRICS 2010

(edited by Jinwoo Shin, Mar 2017)

Advanced Alternatives to BP and MCMC

We have also worked on developing advanced alternatives to BP and MCMC algorithms, for improved inferecne on GM. First, BP is an iterative algorithm, which often diverges. However, there exists always a fixed point of the BP iteration. We developed a message-passing algorithm computes a BP fixed point in a polynomial number of operations for general binary graphical models of n variables where the maximum degree in the underlying graph is O(log n). Our algorithm can be used as an alternative to BP fixing its convergence issue and is the first fully polynomial-time approximation scheme for the BP fixed-point computation in such a large class of graphical models, while the approximate fixed-point computation is known to be (PPAD-)hard in general.

The Complexity of Approximating a Bethe Equilibrium

Jinwoo Shin
IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3959-3969, 2014 (preliminary version appeared in AISTATS 2012)

Second, we propose novel frameworks synthesizing complementary benefits of BP and MCMC. They can be also naturally combined with other popular MCMC techniques, annealed/sequential/adaptive importance sampling, boosting the performance.

Gauge Optimization via ADMM for Approximate Inference

Sungsoo Ahn, Michael Chertkov, and Jinwoo Shin
submitted

Synthesis of MCMC and Belief Propagation (code)

Sungsoo Ahn, Michael Chertkov, and Jinwoo Shin
NIPS 2016

(edited by Jinwoo Shin, Mar 2017)

Learning Parameters of GM

Learning parameters of GM involves computationally intractible inferences tasks, where BP and MCMC can be used for approximate inference. Furthermore, that of latent GM is inherently much harder than that of no-latent ones since the latent variables make the corresponding log-likelihood non-concave. Nevertheless, Expectation-Maximization (EM) schemes are popularly used in practice, but they are typically stuck in bad local optima. We have worked on relaxing the issues of learning GMs rigorously.

Sequential Local Learning for Latent Graphical Models

Sejun Park, Eunho Yang and Jinwoo Shin
submitted

Adiabatic Persistent Contrastive Divergence Learning

Hyeryung Jang, Hyungwon Choi, Yung Yi and Jinwoo Shin
ISIT 2017

Rapid Mixing Swendsen-Wang Sampler for Stochastic Partitioned Attractive Models

Sejun Park, Yunhun Jang, Andreas Galanis, Jinwoo Shin, Daniel Stefankovic and Eric Vigoda
AISTATS 2017

(edited by Jinwoo Shin, Mar 2017)