Sinkhorn Permutation Variational Marginal Inference


Gonzalo Mena, Erdem Varol, Amin Nejatbakhsh, Eviatar Yemini, Liam Paninski ;
Proceedings of The 2nd Symposium on Advances in Approximate Bayesian Inference, PMLR 118:1-9, 2020.


We address the problem of marginal inference for an exponential family defined over the set of permutation matrices. This problem is known to quickly become intractable as the size of the permutation increases, since its involves the computation of the permanent of a matrix, a #P-hard problem. We introduce Sinkhorn variational marginal inference as a scalable alternative, a method whose validity is ultimately justified by the so-called Sinkhorn approximation of the permanent. We demonstrate the effectiveness of our method in the problem of probabilistic identification of neurons in the worm C.elegans.

Related Material