Optimal Particle-based Approximation of Discrete Distributions (OPAD)
Particle-based methods include a variety of techniques, such as Markov Chain Monte Carlo (MCMC) and Sequential Monte Carlo (SMC), for approximating a probabilistic target distribution with a set of weighted particles. In this paper, we prove that for any set of particles, there is a unique weighting mechanism that minimizes the Kullback-Leibler (KL) divergence of the (particle-based) approximation from the target distribution, when that distribution is discrete -- any other weighting mechanism (e.g. MCMC weighting that is based on particles' repetitions in the Markov chain) is sub-optimal with respect to this divergence measure. Our proof does not require any restrictions either on the target distribution, or the process by which the particles are generated, other than the discreteness of the target. We show that the optimal weights can be determined based on values that any existing particle-based method already computes; As such, with minimal modifications and no extra computational costs, the performance of any particle-based method can be improved. Our empirical evaluations are carried out on important applications of discrete distributions including Bayesian Variable Selection and Bayesian Structure Learning. The results illustrate that our proposed reweighting of the particles improves any particle-based approximation to the target distribution consistently and often substantially.
Code (0)
등록된 구현이 없습니다.
Tasks
Variable SelectionMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Wasserstein variational gradient descent: From semi-discrete optimal transport to ensemble variational inference
Particle-based variational inference offers a flexible way of approximating complex posterior distributions with a set of particles. In this paper we introduce a new particle-based variational inference method based on t…
Variational InferenceOn the Convergence of Min-Max Langevin Dynamics and Algorithm
We study zero-sum games in the space of probability distributions over the Euclidean space $\mathbb{R}^d$ with entropy regularization, in the setting when the interaction function between the players is smooth and strong…
Particle-based Variational Inference for Continuous Systems
Since the development of loopy belief propagation, there has been considerable work on advancing the state of the art for approximate inference over distributions defined on discrete random variables. Improvements includ…
Variational InferenceApproximating Posterior Predictive Distributions by Averaging Output From Many Particle Filters
This paper introduces the {\it particle swarm filter} (not to be confused with particle swarm optimization): a recursive and embarrassingly parallel algorithm that targets an approximation to the sequence of posterior pr…
Bayesian posterior approximation via greedy particle optimization
In Bayesian inference, the posterior distributions are difficult to obtain analytically for complex models such as neural networks. Variational inference usually uses a parametric distribution for approximation, from whi…
Bayesian InferenceVariational Inference