MAP Estimation for Graphical Models by Likelihood Maximization
Computing a {\em maximum a posteriori} (MAP) assignment in graphical models is a crucial inference problem for many practical applications. Several provably convergent approaches have been successfully developed using linear programming (LP) relaxation of the MAP problem. We present an alternative approach, which transforms the MAP problem into that of inference in a finite mixture of simple Bayes nets. We then derive the Expectation Maximization (EM) algorithm for this mixture that also monotonically increases a lower bound on the MAP assignment until convergence. The update equations for the EM algorithm are remarkably simple, both conceptually and computationally, and can be implemented using a graph-based message passing paradigm similar to max-product computation. We experiment on the real-world protein design dataset and show that EM's convergence rate is significantly higher than the previous LP relaxation based approach MPLP. EM achieves a solution quality within $95$\% of optimal for most instances and is often an order-of-magnitude faster than MPLP.
Code (0)
등록된 구현이 없습니다.
Tasks
Protein DesignSimilar Papers 제목 키워드 기반
High dimensional Sparse Gaussian Graphical Mixture Model
This paper considers the problem of networks reconstruction from heterogeneous data using a Gaussian Graphical Mixture Model (GGMM). It is well known that parameter estimation in this context is challenging due to large …
modelparameter estimationVariable SelectionVocal Bursts Intensity PredictionLearning Arbitrary Sum-Product Network Leaves with Expectation-Maximization
Sum-Product Networks with complex probability distribution at the leaves have been shown to be powerful tractable-inference probabilistic models. However, while learning the internal parameters has been amply studied, le…
Density EstimationLARGE: A Locally Adaptive Regularization Approach for Estimating Gaussian Graphical Models
The graphical Lasso (GLASSO) is a widely used algorithm for learning high-dimensional undirected Gaussian graphical models (GGM). Given i.i.d. observations from a multivariate normal distribution, GLASSO estimates the pr…
Momentum-Space Renormalization Group Transformation in Bayesian Image Modeling by Gaussian Graphical Model
A new Bayesian modeling method is proposed by combining the maximization of the marginal likelihood with a momentum-space renormalization group transformation for Gaussian graphical models. Moreover, we present a scheme …
Maximum likelihood thresholds of Gaussian graphical models and graphical lasso
Associated to each graph G is a Gaussian graphical model. Such models are often used in high-dimensional settings, i.e. where there are relatively few data points compared to the number of variables. The maximum likeliho…