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

Höfling, Holger; Tibshirani, Robert

J. Mach. Learn. Res. 10, 883-906 (2009).

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.

MSC:

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)

Keywords:

logistic regression; \(L_1\) penalty; model selection; binary variables

Software:

glmnet