Putting MRFs on a Tensor Train

Journal of Machine Learning Research. 2014.

Ветров Д. П., Осокин А. А., Родоманов А. О., Novikov A.

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.  

Ключевые слова: probabilistic graphical models, tensor decomposition