| 1. |
- Andersson Naesseth, Christian, et al.
(författare)
-
Capacity estimation of two-dimensional channels using Sequential Monte Carlo
- 2014
-
Ingår i: 2014 IEEE Information Theory Workshop. ; , s. 431-435
-
Konferensbidrag (refereegranskat)abstract
- We derive a new Sequential-Monte-Carlo-based algorithm to estimate the capacity of two-dimensional channel models. The focus is on computing the noiseless capacity of the 2-D (1, ∞) run-length limited constrained channel, but the underlying idea is generally applicable. The proposed algorithm is profiled against a state-of-the-art method, yielding more than an order of magnitude improvement in estimation accuracy for a given computation time.
|
|
| 2. |
- Andersson Naesseth, Christian, et al.
(författare)
-
High-Dimensional Filtering Using Nested Sequential Monte Carlo
- 2019
-
Ingår i: IEEE Transactions on Signal Processing. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 1053-587X .- 1941-0476. ; 67:16, s. 4177-4188
-
Tidskriftsartikel (refereegranskat)abstract
- Sequential Monte Carlo (SMC) methods comprise one of the most successful approaches to approximate Bayesian filtering. However, SMC without a good proposal distribution can perform poorly, in particular in high dimensions. We propose nested sequential Monte Carlo, a methodology that generalizes the SMC framework by requiring only approximate, properly weighted, samples from the SMC proposal distribution, while still resulting in a correctSMCalgorithm. This way, we can compute an "exact approximation" of, e. g., the locally optimal proposal, and extend the class of models forwhichwe can perform efficient inference using SMC. We showimproved accuracy over other state-of-the-art methods on several spatio-temporal state-space models.
|
|
| 3. |
- Andersson Naesseth, Christian, 1986-
(författare)
-
Machine learning using approximate inference : Variational and sequential Monte Carlo methods
- 2018
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Automatic decision making and pattern recognition under uncertainty are difficult tasks that are ubiquitous in our everyday life. The systems we design, and technology we develop, requires us to coherently represent and work with uncertainty in data. Probabilistic models and probabilistic inference gives us a powerful framework for solving this problem. Using this framework, while enticing, results in difficult-to-compute integrals and probabilities when conditioning on the observed data. This means we have a need for approximate inference, methods that solves the problem approximately using a systematic approach. In this thesis we develop new methods for efficient approximate inference in probabilistic models.There are generally two approaches to approximate inference, variational methods and Monte Carlo methods. In Monte Carlo methods we use a large number of random samples to approximate the integral of interest. With variational methods, on the other hand, we turn the integration problem into that of an optimization problem. We develop algorithms of both types and bridge the gap between them.First, we present a self-contained tutorial to the popular sequential Monte Carlo (SMC) class of methods. Next, we propose new algorithms and applications based on SMC for approximate inference in probabilistic graphical models. We derive nested sequential Monte Carlo, a new algorithm particularly well suited for inference in a large class of high-dimensional probabilistic models. Then, inspired by similar ideas we derive interacting particle Markov chain Monte Carlo to make use of parallelization to speed up approximate inference for universal probabilistic programming languages. After that, we show how we can make use of the rejection sampling process when generating gamma distributed random variables to speed up variational inference. Finally, we bridge the gap between SMC and variational methods by developing variational sequential Monte Carlo, a new flexible family of variational approximations.
|
|
| 4. |
- Andersson Naesseth, Christian, et al.
(författare)
-
Nested Sequential Monte Carlo Methods
- 2015
-
Ingår i: Proceedings of The 32nd International Conference on Machine Learning. - : Journal of Machine Learning Research (Online). - 9781510810587 ; , s. 1292-1301
-
Konferensbidrag (refereegranskat)abstract
- We propose nested sequential Monte Carlo (NSMC), a methodology to sample from sequences of probability distributions, even where the random variables are high-dimensional. NSMC generalises the SMC framework by requiring only approximate, properly weighted, samples from the SMC proposal distribution, while still resulting in a correct SMC algorithm. Furthermore, NSMC can in itself be used to produce such properly weighted samples. Consequently, one NSMC sampler can be used to construct an efficient high-dimensional proposal distribution for another NSMC sampler, and this nesting of the algorithm can be done to an arbitrary degree. This allows us to consider complex and high-dimensional models using SMC. We show results that motivate the efficacy of our approach on several filtering problems with dimensions in the order of 100 to 1 000.
|
|
| 5. |
- Andersson Naesseth, Christian, 1986-, et al.
(författare)
-
Reparameterization Gradients through Acceptance-Rejection Sampling Algorithms
- 2017
-
Ingår i: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. - : PMLR.
-
Konferensbidrag (refereegranskat)abstract
- Variational inference using the reparameterization trick has enabled large-scale approximate Bayesian inference in complex probabilistic models, leveraging stochastic optimization to sidestep intractable expectations. The reparameterization trick is applicable when we can simulate a random variable by applying a differentiable deterministic function on an auxiliary random variable whose distribution is fixed. For many distributions of interest (such as the gamma or Dirichlet), simulation of random variables relies on acceptance-rejection sampling. The discontinuity introduced by the accept-reject step means that standard reparameterization tricks are not applicable. We propose a new method that lets us leverage reparameterization gradients even when variables are outputs of a acceptance-rejection sampling algorithm. Our approach enables reparameterization on a larger class of variational distributions. In several studies of real and synthetic data, we show that the variance of the estimator of the gradient is significantly lower than other state-of-the-art methods. This leads to faster convergence of stochastic gradient variational inference.
|
|
| 6. |
- Andersson Naesseth, Christian, et al.
(författare)
-
Sequential Monte Carlo for Graphical Models
- 2014
-
Ingår i: Advances in Neural Information Processing Systems. ; , s. 1862-1870
-
Konferensbidrag (refereegranskat)abstract
- We propose a new framework for how to use sequential Monte Carlo (SMC) algorithms for inference in probabilistic graphical models (PGM). Via a sequential decomposition of the PGM we find a sequence of auxiliary distributions defined on a monotonically increasing sequence of probability spaces. By targeting these auxiliary distributions using SMC we are able to approximate the full joint distribution defined by the PGM. One of the key merits of the SMC sampler is that it provides an unbiased estimate of the partition function of the model. We also show how it can be used within a particle Markov chain Monte Carlo framework in order to construct high-dimensional block-sampling algorithms for general PGMs.
|
|
| 7. |
- Andersson Naesseth, Christian, 1986-, et al.
(författare)
-
Variational Sequential Monte Carlo
- 2018
-
Ingår i: Proceedings of International Conference on Artificial Intelligence and Statistics, 9-11 April 2018, Playa Blanca, Lanzarote, Canary Islands. - : PMLR. ; , s. 968-977
-
Konferensbidrag (refereegranskat)abstract
- Many recent advances in large scale probabilistic inference rely on variational methods. The success of variational approaches depends on (i) formulating a flexible parametric family of distributions, and (ii) optimizing the parameters to find the member of this family that most closely approximates the exact posterior. In this paper we present a new approximating family of distributions, the variational sequential Monte Carlo (VSMC) family, and show how to optimize it in variational inference. VSMC melds variational inference (VI) and sequential Monte Carlo (SMC), providing practitioners with flexible, accurate, and powerful Bayesian inference. The VSMC family is a variational family that can approximate the posterior arbitrarily well, while still allowing for efficient optimization of its parameters. We demonstrate its utility on state space models, stochastic volatility models for financial data, and deep Markov models of brain neural circuits.
|
|
| 8. |
- Lindsten, Fredrik, 1984-, et al.
(författare)
-
Divide-and-Conquer With Sequential Monte Carlo
- 2017
-
Ingår i: Journal of Computational And Graphical Statistics. - : AMER STATISTICAL ASSOC. - 1061-8600 .- 1537-2715. ; 26:2, s. 445-458
-
Tidskriftsartikel (refereegranskat)abstract
- We propose a novel class of Sequential Monte Carlo (SMC) algorithms, appropriate for inference in probabilistic graphical models. This class of algorithms adopts a divide-and-conquer approach based upon an auxiliary tree-structured decomposition of the model of interest, turning the overall inferential task into a collection of recursively solved subproblems. The proposed method is applicable to a broad class of probabilistic graphical models, including models with loops. Unlike a standard SMC sampler, the proposed divide-and-conquer SMC employs multiple independent populations of weighted particles, which are resampled, merged, and propagated as the method progresses. We illustrate empirically that this approach can outperform standard methods in terms of the accuracy of the posterior expectation and marginal likelihood approximations. Divide-and-conquer SMC also opens up novel parallel implementation options and the possibility of concentrating the computational effort on the most challenging subproblems. We demonstrate its performance on a Markov random field and on a hierarchical logistic regression problem. Supplementary materials including proofs and additional numerical results are available online.
|
|
| 9. |
- Naesseth, Christian Andersson, et al.
(författare)
-
Markovian Score Climbing: Variational Inference with KL(p||q)
- 2020
-
Ingår i: Advances in Neural Information Processing Systems 33 (NeurIPS 2020). ; , s. 15499-15510
-
Konferensbidrag (refereegranskat)abstract
- Modern variational inference (VI) uses stochastic gradients to avoid intractable expectations, enabling large-scale probabilistic inference in complex models. VI posits a family of approximating distributions q and then finds the member of that family that is closest to the exact posterior p. Traditionally, VI algorithms minimize the “exclusive Kullback-Leibler (KL)” KL(q||p), often for computational convenience. Recent research, however, has also focused on the “inclusive KL” KL(p||q), which has good statistical properties that makes it more appropriate for certain inference problems. This paper develops a simple algorithm for reliably minimizing the inclusive KL using stochastic gradients with vanishing bias. This method, which we call Markovian score climbing (MSC), converges to a local optimum of the inclusive KL. It does not suffer from the systematic errors inherent in existing methods, such as Reweighted Wake-Sleep and Neural Adaptive Sequential Monte Carlo, which lead to bias in their final estimates. We illustrate convergence on a toy model and demonstrate the utility of MSC on Bayesian probit regression for classification as well as a stochastic volatility model for financial data.
|
|
| 10. |
- Rainforth, Tom, et al.
(författare)
-
Interacting Particle Markov Chain Monte Carlo
- 2016
-
Ingår i: Proceedings of the 33rd International Conference on Machine Learning (ICML). ; , s. 2616-2625
-
Konferensbidrag (refereegranskat)abstract
- We introduce interacting particle Markov chain Monte Carlo (iPMCMC), a PMCMC method based on an interacting pool of standard and conditional sequential Monte Carlo samplers. Like related methods, iPMCMC is a Markov chain Monte Carlo sampler on an extended space. We present empirical results that show significant improvements in mixing rates relative to both non-interacting PMCMC samplers and a single PMCMC sampler with an equivalent memory and computational budget. An additional advantage of the iPMCMC method is that it is suitable for distributed and multi-core architectures.
|
|
