# Inference with Aggregate Data: An Optimal Transport Approach

arXiv: https://arxiv.org/abs/2003.13933 · HTML: https://mlsanity.com/paper/2003.13933/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2020.

## Built on by (most cited first, 6 of 6)

- [DiffCollage: Parallel Generation of Large Content with Diffusion Models](https://mlsanity.com/paper/2303.17076/) (2023)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Estimating Latent Population Flows from Aggregated Data via Inversing Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2212.14527/) (2022)
- [Fast block-coordinate Frank-Wolfe algorithm for semi-relaxed optimal transport](https://mlsanity.com/paper/2103.05857/) (2021)
- [Non-approximate Inference for Collective Graphical Models on Path Graphs via Discrete Difference of Convex Algorithm](https://mlsanity.com/paper/2102.09191/) (2021)
- [Inference of collective Gaussian hidden Markov models](https://mlsanity.com/paper/2107.11662/) (2021)

## Abstract (arXiv)

We consider inference (filtering) problems over probabilistic graphical models with aggregate data generated by a large population of individuals. We propose a new efficient belief propagation type algorithm over tree-structured graphs with polynomial computational complexity as well as a global convergence guarantee. This is in contrast to previous methods that either exhibit prohibitive complexity as the population grows or do not guarantee convergence. Our method is based on optimal transport, or more specifically, multi-marginal optimal transport theory. In particular, we consider an inference problem with aggregate observations, that can be seen as a structured multi-marginal optimal transport problem where the cost function decomposes according to the underlying graph. Consequently, the celebrated Sinkhorn/iterative scaling algorithm for multi-marginal optimal transport can be leveraged together with the standard belief propagation algorithm to establish an efficient inference scheme which we call Sinkhorn belief propagation (SBP). We further specialize the SBP algorithm to cases associated with hidden Markov models due to their significance in control and estimation. We demonstrate the performance of our algorithm on applications such as inferring population flow from aggregate observations. We also show that in the special case where the observations are generated by a single individual, our algorithm naturally reduces to the standard belief propagation algorithm.