Inference with Aggregate Data: An Optimal Transport Approach

• URL: http://arxiv.org/abs/2003.13933v2
• Date: Sat, 3 Oct 2020 00:35:30 GMT
• Title: Inference with Aggregate Data: An Optimal Transport Approach
• Authors: Rahul Singh, Isabel Haasler, Qinsheng Zhang, Johan Karlsson, Yongxin Chen
• Abstract summary: 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 algorithm over tree-structured graphs with computational complexity as well as a global convergence guarantee.
• Score: 16.274397329511196
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Learning Unnormalized Statistical Models via Compositional Optimization [73.30514599338407]
  Noise-contrastive estimation(NCE) has been proposed by formulating the objective as the logistic loss of the real data and the artificial noise. In this paper, we study it a direct approach for optimizing the negative log-likelihood of unnormalized models.
  arXiv  Detail & Related papers  (2023-06-13T01:18:16Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  Efficient computation of the optimal transport distance between two distributions serves as an algorithm that empowers various applications. This paper develops a scalable first-order optimization-based method that computes optimal transport to within $varepsilon$ additive accuracy.
  arXiv  Detail & Related papers  (2023-01-30T15:46:39Z)
• EM's Convergence in Gaussian Latent Tree Models [22.987933817370305]
  We show that the unique non-trivial point of the population log-likelihood is its global maximum. We establish that the expectation-maximization algorithm is guaranteed to converge to it in the single latent variable case.
  arXiv  Detail & Related papers  (2022-11-21T23:12:58Z)
• Convergence of batch Greenkhorn for Regularized Multimarginal Optimal Transport [6.123324869194195]
  We provide a complete converge analysis based on the properties of the iterative Bregman projections (IBP) method with greedy control. When specialized to above mentioned algorithms, our results give new insights and/or improve existing ones.
  arXiv  Detail & Related papers  (2021-12-01T21:31:26Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Sparse PCA via $l_{2,p}$-Norm Regularization for Unsupervised Feature Selection [138.97647716793333]
  We propose a simple and efficient unsupervised feature selection method, by combining reconstruction error with $l_2,p$-norm regularization. We present an efficient optimization algorithm to solve the proposed unsupervised model, and analyse the convergence and computational complexity of the algorithm theoretically.
  arXiv  Detail & Related papers  (2020-12-29T04:08:38Z)
• Incremental inference of collective graphical models [16.274397329511196]
  In particular, we address the problem of estimating the aggregate marginals of a Markov chain from noisy aggregate observations. We propose a sliding window Sinkhorn belief propagation (SW-SBP) algorithm that utilizes a sliding window filter of the most recent noisy aggregate observations.
  arXiv  Detail & Related papers  (2020-06-26T15:04:31Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  junction tree algorithm is the most general solution for exact MAP inference with run-time guarantees. We propose a new graph transformation technique via node cloning which ensures a run-time for solving our target problem independently of the form of a corresponding clique tree.
  arXiv  Detail & Related papers  (2019-12-27T13:30:29Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.