Spanning Tree Approximations for Conditional Random Fields


Patrick Pletscher, Cheng Soon Ong, Joachim Buhmann ;
Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:408-415, 2009.


In this work we show that one can train Conditional Random Fields of intractable graphs effectively and efficiently by considering a mixture of random spanning trees of the underlying graphical model. Furthermore, we show how a maximum-likelihood estimator of such a training objective can subsequently be used for prediction on the full graph. We present experimental results which improve on the state-of-the-art. Additionally, the training objective is less sensitive to the regularization than pseudo-likelihood based training approaches. We perform the experimental validation on two classes of data sets where structure is important: image denoising and multilabel classification.

Related Material