Estimation of sparse binary pairwise Markov networks using pseudo-likelihoods. (English) Zbl 1245.62121

Summary: 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 approximation procedure based on the pseudo-likelihood of J. Besag [Proc. 21 Nat. Conf. Artificial Intell. (AAAI-06), 24, 179–195 (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 iteration moves it closer to the exact solution. Our results show that this procedure is faster than the competing exact method proposed byS.-I. Lee et al. [Advances Neural Inform. Process. Syst. (2006)]. However, we also find that the approximate pseudo-likelihood as well as the approaches of M.J. Wainwright et al. [ibid., Vancouver (2006)], when implemented using the coordinate descent procedure of J. Friedman et al. [Tech. Rep., Stanford Univ. (2008)] are much faster than the exact methods, and only slightly less accurate.


62M99 Inference from stochastic processes
60J99 Markov processes
68T99 Artificial intelligence
05C90 Applications of graph theory
65C20 Probabilistic models, generic numerical methods in probability and statistics
62J12 Generalized linear models (logistic models)


Full Text: Link