Inferning with High Girth Graphical Models
Uri Heinemann, Amir Globerson · 2014
Unsupervised learning of graphical models is an important task in many domains. Although maximum likelihood learning is computation-ally hard, there do exist consistent learning algo-rithms (e.g., psuedo-likelihood and its variants). However, inference in the learned models is still hard, and thus they are not directly usable. In other words, given a probabilistic query they are not guaranteed to provide an answer that is close to the true one. In the current paper, we provide a learning al-gorithm that is guaranteed to provide approxi-mately correct probabilistic inference. We fo-cus on a particular class of models, namely high girth graphs in the correlation decay regime. It is well known that approximate inference (e.g, us-ing loopy BP) in such models yields marginals that are close to the true ones. Motivated by this, we propose an algorithm that always returns models of this type, and hence in the models it returns inference is approximately correct. We derive finite sample results guaranteeing that be-yond a certain sample size, the resulting mod-els will answer probabilistic queries with a high level of accuracy. Results on synthetic data show that the models we learn indeed outperform those obtained by other algorithms, which do not return high girth graphs.