
Spectral Approximate Inference
Given a graphical model (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 lowtemperature 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 twofold: (a) we first propose a fully polynomialtime approximation scheme (FPTAS) for approximating the partition function of GM associating with a lowrank coupling matrix; (b) for general highrank GMs, we design a spectral meanfield scheme utilizing (a) as a subroutine, where it approximates a highrank GM into a product of rank1 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, as demonstrated in our experiments.
05/14/2019 ∙ by Sejun Park, et al. ∙ 3 ∙ shareread it

Rapid Mixing SwendsenWang Sampler for Stochastic Partitioned Attractive Models
The Gibbs sampler is a particularly popular Markov chain used for learning and inference problems in Graphical Models (GMs). These tasks are computationally intractable in general, and the Gibbs sampler often suffers from slow mixing. In this paper, we study the SwendsenWang dynamics which is a more sophisticated Markov chain designed to overcome bottlenecks that impede the Gibbs sampler. We prove O( n) mixing time for attractive binary pairwise GMs (i.e., ferromagnetic Ising models) on stochastic partitioned graphs having n vertices, under some mild conditions, including low temperature regions where the Gibbs sampler provably mixes exponentially slow. Our experiments also confirm that the SwendsenWang sampler significantly outperforms the Gibbs sampler when they are used for learning parameters of attractive GMs.
04/06/2017 ∙ by Sejun Park, et al. ∙ 0 ∙ shareread it

Sequential Local Learning for Latent Graphical Models
Learning parameters of latent graphical models (GM) is inherently much harder than that of nolatent ones since the latent variables make the corresponding loglikelihood nonconcave. Nevertheless, expectationmaximization schemes are popularly used in practice, but they are typically stuck in local optima. In the recent years, the method of moments have provided a refreshing angle for resolving the nonconvex issue, but it is applicable to a quite limited class of latent GMs. In this paper, we aim for enhancing its power via enlarging such a class of latent GMs. To this end, we introduce two novel concepts, coined marginalization and conditioning, which can reduce the problem of learning a larger GM to that of a smaller one. More importantly, they lead to a sequential learning framework that repeatedly increases the learning portion of given latent GM, and thus covers a significantly broader and more complicated class of loopy latent GMs which include convolutional and random regular models.
03/12/2017 ∙ by Sejun Park, et al. ∙ 0 ∙ shareread it

MaxProduct Belief Propagation for Linear Programming: Applications to Combinatorial Optimization
The maxproduct belief propagation (BP) is a popular messagepassing heuristic for approximating a maximumaposteriori (MAP) assignment in a joint distribution represented by a graphical model (GM). In the past years, it has been shown that BP can solve a few classes of linear programming (LP) formulations to combinatorial optimization problems including maximum weight matching, shortest path and network flow, i.e., BP can be used as a messagepassing solver for certain combinatorial optimizations. However, those LPs and corresponding BP analysis are very sensitive to underlying problem setups, and it has been not clear what extent these results can be generalized to. In this paper, we obtain a generic criteria that BP converges to the optimal solution of given LP, and show that it is satisfied in LP formulations associated to many classical combinatorial optimization problems including maximum weight perfect matching, shortest path, traveling salesman, cycle packing, vertex/edge cover and network flow.
12/16/2014 ∙ by Sejun Park, et al. ∙ 0 ∙ shareread it

Minimum Weight Perfect Matching via Blossom Belief Propagation
Maxproduct Belief Propagation (BP) is a popular messagepassing algorithm for computing a MaximumAPosteriori (MAP) assignment over a distribution represented by a Graphical Model (GM). It has been shown that BP can solve a number of combinatorial optimization problems including minimum weight matching, shortest path, network flow and vertex cover under the following common assumption: the respective Linear Programming (LP) relaxation is tight, i.e., no integrality gap is present. However, when LP shows an integrality gap, no model has been known which can be solved systematically via sequential applications of BP. In this paper, we develop the first such algorithm, coined BlossomBP, for solving the minimum weight matching problem over arbitrary graphs. Each step of the sequential algorithm requires applying BP over a modified graph constructed by contractions and expansions of blossoms, i.e., odd sets of vertices. Our scheme guarantees termination in O(n^2) of BP runs, where n is the number of vertices in the original graph. In essence, the BlossomBP offers a distributed version of the celebrated Edmonds' Blossom algorithm by jumping at once over many substeps with a single BP. Moreover, our result provides an interpretation of the Edmonds' algorithm as a sequence of LPs.
09/23/2015 ∙ by Sungsoo Ahn, et al. ∙ 0 ∙ shareread it
Sejun Park
is this you? claim profile