Estimation of Sparse Binary Pairwise Markov Networks using Pseudo-likelihoods

By Holger Hofling, Robert Tibshirani. 2009

199 citations recorded by the source corpus.

We consider the problems of estimating the parameters as well as the structure of binary-valued Markov networks. For maximizing the penalized log-likelihood, we implement an approximate procedure based on the pseudo-likelihood of Besag (1975) and generalize it to a fast exact algorithm. The exact algorithm starts with the pseudo-likelihood solution and then adjusts the pseudo-likelihood criterion so that each additional iterations moves it closer to the exact solution. Our results show that this procedure is faster than the competing exact method proposed by Lee, Ganapathi, and Koller (2006a). However, we also find that the approximate pseudo-likelihood as well as the approaches of Wainwright et al. (2006), when implemented using the coordinate descent procedure of Friedman, Hastie, and Tibshirani (2008b), are much faster than the exact methods, and only slightly less accurate.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Learning generative models for protein fold families (2011, background): “More recently several authors [36, 21, 18, 25] have considered convex approximations to the complexity metric and tractable (convex) approximations to the goodness of fit metric.”
Structure Learning in Graphical Modeling (2016, methodology): “H¨oﬂing & Tibshirani (2009) explore this pseudo-likelihood method for Ising models but ﬁnd rather little diﬀerence with neighborhood selection.”
On stochastic proximal gradient algorithms (2014, background): “…algorithms that this strategy breaks down when the instrumental distribution π∗ is not well fitted to the target πθ, a situation which typically implies large fluctuation of the importance weights {w(θn, Xn+1,j)}mn+1j=1 ; this occurs all the more as the dimension of the integration space increases.”
On Perturbed Proximal Gradient Algorithms (2014, methodology): “One notable exception that tackles the log - likelihood function is Höfling and Tibshirani ( 2009 ) , using an active set strategy ( to preserve sparsity ) , and the junction tree algorithm for computing the partial derivatives of the log - partition function .”
Bayesian model choice and information criteria in sparse generalized linear models (2011, methodology): “The resulting graph estimate Ĝρ has an edge between nodes j and k based on the values of β̂ρjk and β̂ ρ kj , using either an and or an or rule; compare also Höfling and Tibshirani (2009).”
Global Quantitative Modeling of Chromatin Factor Interactions (2014, methodology): “To speed up computation for structure learning, we replaced likelihood with pseudo-likelihood approximation [18,40,41].”
Convex Structure Learning in Log-Linear Models: Beyond Pairwise Potentials (2010, methodology): “To address this problem, one can use pseudo-likelihood (Wainwright et al., 2006; Höfling and Tibshirani, 2009) or other approximate methods (Lee et al., 2006; Banerjee et al., 2008).”