Inference with Aggregate Data: An Optimal Transport Approach
This addresses inference problems for large populations in fields like control and estimation, offering a scalable solution with proven convergence, though it is incremental as it builds on existing belief propagation and optimal transport methods.
The paper tackles inference over probabilistic graphical models with aggregate data by proposing Sinkhorn belief propagation (SBP), an efficient algorithm with polynomial complexity and global convergence, unlike prior methods that are computationally prohibitive or lack convergence guarantees. It demonstrates performance on applications like inferring population flow from aggregate observations.
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.