Putting MRFs on a Tensor Train


Alexander Novikov, Anton Rodomanov, Anton Osokin, Dmitry Vetrov ;
Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):811-819, 2014.


In the paper we present a new framework for dealing with probabilistic graphical models. Our approach relies on the recently proposed Tensor Train format (TT-format) of a tensor that while being compact allows for efficient application of linear algebra operations. We present a way to convert the energy of a Markov random field to the TT-format and show how one can exploit the properties of the TT-format to attack the tasks of the partition function estimation and the MAP-inference. We provide theoretical guarantees on the accuracy of the proposed algorithm for estimating the partition function and compare our methods against several state-of-the-art algorithms.

Related Material