Today I [barely made it on a delayed train from Leaminton Spa to Oxford as I] chaired my invited session at SPA 2015 on advanced MCMC methodology. The three speakers, Randal Douc, Mike Pitt and Matti Vihola, all gave talks related to the pseudomarginal technique. For instance, Randal gave examples of guaranteed variance improvements by adding randomisation steps in the generation of the rv’s behind the unbiased estimation of the likelihood function. Mike Pitt presented the paper I discussed a little while ago about evaluating the computing performances of pseudomarginal approximations, with a fairly compelling perspective [I may have missed from the paper] on approximating the distribution on the approximation to the loglikelihood as a normal. Which led me to ponder at the ultimate version where the loglikelihood itself would get directly simulated in an MCMC algorithm bypassing the preliminary simulation of the parameters. Sounds a bit too fantasylike to be of any use… Matti Vihola also presented recent results with Christophe Andrieu on comparing pseudomarginal approximations, based on convex ordering properties. They included a domination result on ABCMCM algorithms, as noted in a recent post. Which made me musing about the overall importance of unbiasedness in the global picture, where all we need are converging approximations, in fine.
Archive for particle filters
SPA 2015 Oxford [my day #2]
Posted in pictures, Statistics, Travel, University life with tags British Rail, Keble College, Leamington Spa, Oxford, particle filters, pseudomarginal MCMC, SPA 2015, systematic resampling, unbiased estimation, University of Oxford on July 17, 2015 by xi'anStochastic volatility filtering with intractable likelihoods
Posted in Books, Statistics, University life with tags ABC, alphastable processes, auxiliary particle filter, EPABC, particle filters, SMC, stochastic volatility on May 23, 2014 by xi'an“The contribution of our work is twofold: first, we extend the SVM literature, by proposing a new method for obtaining the filtered volatility estimates. Second, we build upon the current ABC literature by introducing the ABC auxiliary particle filter, which can be easily applied not only to SVM, but to any hidden Markov model.”
Another ABC arXival: Emilian Vankov and Katherine B. Ensor posted a paper with the above title. They consider a stochastic volatility model with an αstable distribution on the observables (or returns). Which makes the likelihood unavailable, even were the hidden Markov sequence known… Now, I find very surprising that the authors do not mention the highly relevant paper of Peters, Sisson and Fan, Likelihoodfree Bayesian inference for αstable models, published in CSDA, in 2012, where an ABC algorithm is specifically designed for handling αstable likelihoods. (Commented on that earlier post.) Similarly, the use of a particle filter coupled to ABC seems to be advanced as a novelty when many researchers have implemented such filters, including Pierre Del Moral, Arnaud Doucet, Ajay Jasra, Sumeet Singh and others, in similar or more general settings. Furthermore, Simon Barthelmé and Nicolas Chopin analysed this very model by EPABC and ABC. I thus find it a wee bit hard to pinpoint the degree of innovation contained in this new ABC paper…
MCqMC 2014 [day #1]
Posted in pictures, Running, Statistics, Travel, University life with tags Belgium, Bernoulli factory, Leuven, MCMC, MCQMC2014, Monte Carlo Statistical Methods, multilevel Monte Carlo, particle filters, SDEs, unbiasedness on April 9, 2014 by xi'anAs I have been kindly invited to give a talk at MCqMC 2014, here am I. in Leuven, Belgium, for this conference I have never attended before. (I was also invited for MCqMC 2012 in Sydney The talk topics and the attendees’ “sociology” are quite similar to those of the IMACS meeting in Annecy last summer. Namely, rather little on MCMC, particle filters, and other tools familiar in Bayesian computational statistics, but a lot on diffusions and stochastic differential equations and of course quasiMonte Carlo methods. I thus find myself at a boundary of the conference range and a wee bit lost by some talks, which even titles make little sense to me.
For instance, I have trouble to connect with multilevel Monte Carlo within my own referential. My understanding of the method is one of a control variate version of tempering, namely of using a sequence of approximations to the true target and using rougher approximations as control variates for the finer approximations. But I cannot find on the Web a statistical application of the method outside of diffusions and SDEs, i.e. outside of continuous time processes… Maybe using a particle filter from one approximation to the next, down in terms of roughness, could help.
“Several years ago, Giles (2008) introduced an intriguing multilevel idea to deal with such biased settings that can dramatically improve the rate of convergence and can even, in some settings, achieve the canonical “square root” convergence rate associated with unbiased Monte Carlo.” Rhee and Glynn, 2012
Those were my thoughts before lunchtime. today (namely April 7, 2014). And then, after lunch, Peter Glynn gave his plenary talk that just answered those questions of mine’s!!! Essentially, he showed that formula Pierre Jacob also used in his Bernoulli factory paper to transform a convergingbiasedintoanunbiased estimator, based on a telescopic series representation and a random truncation… This approach is described in a paper with Changhan Rhee, arXived a few years ago. The talk also covered more recent work (presumably related with Changhan Rhee’s thesis) extending the above to Markov chains. As explained to me later by Pierre Jacob [of Statisfaction fame!], a regular chain does not converge fast enough to compensate for the explosive behaviour of the correction factor, which is why Rhee and Glynn used instead a backward chain, linking to the exact or perfect samplers of the 1990’s (which origin can be related to a 1992 paper of Asmussen, Glynn and Thorisson). This was certainly the most riveting talk I attended in the past years in that it brought a direct answer to a question I was starting to investigate. And more. I was also wondering how connected it was with our “exact” representation of the stationary distribution (in an Annals of Probability paper with Jim Hobert). Since we use a stopping rule based on renewal and a geometric waiting time, a somewhat empirical version of the inverse probability found in Peter’s talk. This talk also led me to reconsider a recent discussion we had in my CREST office with Andrew about using square root(ed) importance weights, since one of Peter’s slides exhibited those square roots as optimal. Paradoxically, Peter started the talk by downplaying it, stating there was a single idea therein and a single important slide, making it a perfect afterlunch talk: I wish I had actually had thrice more time to examine each slide! (In the afternoon session, Éric Moulines also gave a thoughtprovoking talk on particle islands and double bootstrap, a research project I will comment in more detail the day it gets arXived.)
Nonlinear Time Series just appeared
Posted in Books, R, Statistics, University life with tags book review, CHANCE, EM algorithm, Eric Moulines, Markov chains, MCMC, Monte Carlo Statistical Methods, nonlinear time series, particle filters, pMCMC, R, Randal Douc, sequential Monte Carlo, simulation, statistical inference, time series on February 26, 2014 by xi'anMy friends Randal Douc and Éric Moulines just published this new time series book with David Stoffer. (David also wrote Time Series Analysis and its Applications with Robert Shumway a year ago.) The books reflects well on the research of Randal and Éric over the past decade, namely convergence results on Markov chains for validating both inference in nonlinear time series and algorithms applied to those objects. The later includes MCMC, pMCMC, sequential Monte Carlo, particle filters, and the EM algorithm. While I am too close to the authors to write a balanced review for CHANCE (the book is under review by another researcher, before you ask!), I think this is an important book that reflects the state of the art in the rigorous study of those models. Obviously, the mathematical rigour advocated by the authors makes Nonlinear Time Series a rather advanced book (despite the authors’ reassuring statement that “nothing excessively deep is used”) more adequate for PhD students and researchers than starting graduates (and definitely not advised for selfstudy), but the availability of the R code (on the highly personal page of David Stoffer) comes to balance the mathematical bent of the book in the first and third parts. A great reference book!
particle efficient importance sampling
Posted in Statistics with tags efficient importance sampling, hidden Markov models, importance sampling, particle filters, sequential Monte Carlo, state space model, stochastic volatility on October 15, 2013 by xi'anMarcel Scharth and Robert Kohn just arXived a new article entitled “particle efficient importance sampling“. What is—the efficiency—about?! The spectacular diminution in variance—(the authors mention a factor of 6,000 when compared with regular particle filters!—in a stochastic volatility simulation study.
If I got the details right, the improvement stems from a paper by Richard and Zhang (Journal of Econometrics, 2007). In a statespace/hidden Markov model setting, (nonsequential) importance sampling tries to approximate the smoothing distribution one term at a time, ie p(x_{t}x_{t1},y_{1:n}), but Richard and Zhang (2007) modify the target by looking at
p(y_{t}x_{t})p(x_{t}x_{t1})χ_{(}x_{t1},y_{1:n}),
where the last term χ_{(}x_{t1},y_{1:n}) is the normalising constant of the proposal kernel for the previous (in t1) target, k(x_{t1}x_{t2},y_{1:n}). This kernel is actually parameterised as k(x_{t1}x_{t2},a_{t}(y_{1:n)}) and the EIS algorithm optimises those parameters, one term at a time. The current paper expands Richard and Zhang (2007) by using particles to approximate the likelihood contribution and reduce the variance once the “optimal” EIS solution is obtained. (They also reproduce Richard’s and Zhang’s tricks of relying on the same common random numbers.
This approach sounds like a “miracle” to me, in the sense(s) that (a) the “normalising constant” is far from being uniquely defined (and just as far from being constant in the parameter a_{t}) and (b) it is unrelated with the target distribution (except for the optimisation step). In the extreme case when the normalising constant is also constant… in a_{t}, this step clearly is useless. (This also opens the potential for an optimisation in the choice of χ_{(}x_{t1},y_{1:n})…)
The simulation study starts from a univariate stochastic volatility model relying on two hidden correlated AR(1) models. (There may be a typo in the definition in Section 4.1, i.e. a Φ_{i} missing.) In those simulations, EIS brings a significant variance reduction when compared with standard particle filters and particle EIS further improves upon EIS by a factor of 2 to 20 (in the variance). I could not spot in the paper which choice had been made for χ()… which is annoying as I gathered from my reading that it must have a strong impact on the efficiency attached to the name of the method!
Special Issue of ACM TOMACS on Monte Carlo Methods in Statistics
Posted in Books, R, Statistics, University life with tags ACM Transactions on Modeling and Computer Simulation, Berlin, EM algorithm, importance sampling, integer valued functions, MCMC, Monte Carlos Statistical Methods, optimisation, parallelisation, particle filters, rare events, simulation, WSC 2012 on December 10, 2012 by xi'anAs posted here a long, long while ago, following a suggestion from the editor (and North America Cycling Champion!) Pierre Lécuyer (Université de Montréal), Arnaud Doucet (University of Oxford) and myself acted as guest editors for a special issue of ACM TOMACS on Monte Carlo Methods in Statistics. (Coincidentally, I am attending a board meeting for TOMACS tonight in Berlin!) The issue is now ready for publication (next February unless I am confused!) and made of the following papers:
* Massive parallelization of serial inference algorithms for a complex generalized linear model MARC A. SUCHARD, IVAN ZORYCH, PATRICK RYAN, DAVID MADIGAN 

*Convergence of a Particlebased Approximation of the Block Online Expectation Maximization Algorithm SYLVAIN LE CORFF and GERSENDE FORT 

* Efficient MCMC for Binomial Logit Models AGNES FUSSL, SYLVIA FRÜHWIRTHSCHNATTER, RUDOLF FRÜHWIRTH 

* Adaptive EquiEnergy Sampler: Convergence and Illustration AMANDINE SCHRECK and GERSENDE FORT and ERIC MOULINES 

* Particle algorithms for optimization on binary spaces CHRISTIAN SCHÄFER 

* Posterior expectation of regularly paved random histograms RAAZESH SAINUDIIN, GLORIA TENG, JENNIFER HARLOW, and DOMINIC LEE 

* Small variance estimators for rare event probabilities MICHEL BRONIATOWSKI and VIRGILE CARON 

* SelfAvoiding Random Dynamics on Integer Complex Systems FIRAS HAMZE, ZIYU WANG, and NANDO DE FREITAS 

* Bayesian learning of noisy Markov decision processes SUMEETPAL S. SINGH, NICOLAS CHOPIN, and NICK WHITELEY 
Here is the draft of the editorial that will appear at the beginning of this special issue. (All faults are mine, of course!) Continue reading