IPMCMC

[emilemathieu]

Hi all !

Do you have any plan of implementing Particle Gibbs with Ancestor Sampling and Interacting Particle Markov Chain Monte Carlo ? These are very useful PMCMC algorithms, which are implemented in Anglican.

Best, Emile

[emilemathieu]

PGAS is really useful to tackle degeneracy path issues. Particle Gibbs with Ancestor Sampling for Probabilistic Programs explains how to implement it in a PPL. I'll look deeper at it to see how it could be implementable in Turing.

If you have any remark/advice don't hesitate since it seems non trivial to implement.

[yebai]

I'd recommend to implement this for a limited case first, since it's hard to apply ancestor resampling to models with varying number of dimensions. You can take a look at #250 first, where PG is limited to one vector-valued variable.

[emilemathieu]

I'll have a look at https://github.com/yebai/Turing.jl/issues/250.

Implementing IPMCMC seems easier. Have you already used parallelisation in Turing ? IPMCMC requires running several SMC and CSMC in parallel.

[yebai]

Implementing IPMCMC seems easier. Have you already used parallelisation in Turing ? IPMCMC requires running several SMC and CSMC in parallel.

I've tried to use threaded tasks (ie coroutines) on Julia 0.5, there were some bugs (see https://github.com/yebai/Turing.jl/issues/65) on the Julia side. We are waiting the threads library to become more stable.

[yebai]

Ps. actually, it's possible to implement IPMCMC with standard coroutines, as they already support non-preemptive multitasking.

[emilemathieu]

Could you give me a reference or more details to understand how to use coroutines for IPMCMC ?

[yebai]

Could you give me a reference or more details to understand how to use coroutines for IPMCMC ?

It's worth having a look at / playing with the following examples first. They demonstrate how tasks are copied in Turing, and how it's used to represent execution traces (particles).

• https://github.com/yebai/Turing.jl/blob/master/test/taskcopy.jl/clonetask.jl
• https://github.com/yebai/Turing.jl/blob/master/test/trace.jl/trace.jl

I'll do my best to help if you run into any questions / difficulties.

[jwvdm]

Hi Emile,

It might be worth pointing out that the implementation for PGAS that we present in the paper actually differs from the approach that we implement in the current release of Anglican:

• In the paper, we construct a symbolic expression for conditional densities during evaluation, which is sometimes referred to as a concolic execution.

• In the current Anglican implementation, the execution model is based on a continuation passing style transformation. In this execution model, we perform the ancestor resampling step by re-running a program conditioned on a random database in a manner similar to "lightweight" Metropolis-Hastings implementations.

A limitation of the second strategy is that it increases the computational cost of the algorithm from linear to quadratic in the number of generations. That said, on balance this "lightweight" implementation for PGAS is probably the one I'd advise looking at first for Turing.

I'm happy to advise on implementation considerations for PGAS. Incidentally, I also co-wrote the IPMCMC implementation for Anglican, so I can answer questions about that as well.

[emilemathieu]

Thanks Jan-Willem for these precious insights !

I'll look into that next week and I'll definitely come back to you for specific questions.

Best, Emile

[emilemathieu]

Hi all !

I'm implementing IPMCMC in a sequential (non-parallelised) way, such that it could then be parallelised once someone know how to do that in Julia. It's almost done !

@yebai: Could you please explain what's use_replay in resample!(particles, spl.alg.resampler, ref_particle; use_replay=false) and the difference between TraceR and TraceC. I don't really get this things.

Best, Emile

[emilemathieu]

The PR for the IPMCMC sampler can be found here https://github.com/yebai/Turing.jl/pull/351

[yebai]

@jwvdm Seems you're the only expert on the IPMCMC algorithm here, could you help us review this PR, please?

[emilemathieu]

@yebai, have you seen my question on use_replay and TraceR ?

[yebai]

Could you please explain what's use_replay in resample!(particles, spl.alg.resampler, ref_particle; use_replay=false) and the difference between TraceR and TraceC. I don't really get this things.

Sure - there are two ways for copying/forking particles in Turing. The first one is based on replaying random variables, while the second one is based on coroutine copying. The first method for particle copying requires storing all random variables generated during execution of a Turing program. For these purposes, we implemented two related data structures: TraceR and TraceC. Basically, TraceR corresponds to TraceReplay, and stores all random variables; while TraceC does not store all random variables.

Regarding use_replay, it tells the resample! function to use replay to copy particles instead of using coroutine copying.

BTW: I've put this answer on the wiki.

[jwvdm]

@yebai @emilemathieu: I can take a look. It might be a week or so until I get to it, so feel free to ping me again if you don't hear back.

[emilemathieu]

I'll add some comments, and factorise a bit things.

[emilemathieu]

There are some errors in my IPMCMC code, I'll notice you when these are fixed (+ comments).