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 efectiveness of our method in the problem of probabilistic identification of neurons in the worm C.elegans Let P ∈ R n×n be a binary matrix representing a permutation of n elements (i.e. each row and column of P contains a unique 1). We consider the distribution over P defined as where A, B F is the Frobenius matrix inner product, log L is a parameter matrix and Z L is the normalizing constant. Here we address the problem of marginal inference, i.e. computing the matrix of expectations ρ := E(P). This problem is known to be intractable since it requires access to Z L , also known as the permanent of L, and whose computation is known to be a #P-hard problem Valiant (1979) To overcome this difficulty we introduce Sinkhorn variational marginal inference, which can be computed efficiently and is straightforward to implement. Specifically, we approximate ρ as S(L), the Sinkhorn operator applied to L (Sinkhorn, 1964) . S(L) is defined as the (infinite) successive row and column normalization of L (Adams and Zemel, 2011; , a limit that is known to result in a doubly stochastic matrix (Altschuler et al., 2017) . In section 2 we argue the Sinkhorn approximation is sensible, and in section 3 we describe the problem of probabilistic inference of neural identity in C.elegans and demonstrate the Sinkhorn approximation produces the best results. We have introduced the Sinkhorn approximation for marginal inference, and our it is a sensible alternative to sampling, and it may provide faster, simpler and more accurate approximate marginals than the Bethe approximation, despite typically leading to worse permanent approximations. We leave for future work a thorough analysis of the relation between quality of permanent approximation and corresponding marginals. Also, it can be verified that S(L) = diag(x)Ldiag(y ), where diag(x), diag(y ) are some positive vectors x, y turned into diagonal matrices (Peyré et al., 2019) . Then, Additionally, we obtain the (log) Sinkhorn approximation of the permanent of L, perm S (L), by evaluating S(L) in the problem it solves, (2.3). By simple algebra and using the fact that S(L) is a doubly stochastic matrix we see that By combining the last three displays we obtain from which the result follows.
New methodology for variational marginal inference of permutations based on Sinkhorn algorithm, applied to probabilistic identification of neurons
{"src": "scitldr-AIC_train", "paper_id": "HkxPtJh4YB"}