Learn how to do inference in a higher order probabilistic programming language in a way that is very near to being compatible with tight-bounds model-learning via gradient-based evidence lower-bounding. In particular you are going to learn how to do sequential Monte-Carlo-based inference in the probabilistic programming context. You should note in doing this homework the increased efficiency of inference in the HMM model in particular, the model in which partial “reward” is accumulated.
In order to successfully complete this task you will also have to face the wonders of the CPS transformation. Conveniently for you, you do not have to code the CPS transformation. In the provided support code you will note that Daphne is invoked with the argument desugar-hoppl-cps which not only desugars the HOPPL as before but also transforms the desugared HOPPL code into CPS-form (following the recipe in the book).
The upshot of all this is that, provided you have taken care to ensure an immutable environment as required in the previous homework, you can exploit the CPS-form of the passed-in program. Again, here, the support code has been restructured to do most of this for you. What do you get from CPS? You get explicit control over the “rest of the computation” (via the continuation function), you get the ability to branch the environment easily (via pure datastructures), and you get to avoid stack blow-up by trampolining (by exploiting CPS). What this means is that you can implement SMC. And the version of SMC that you have implemented is dramatically more expressive than say, normal SMC researchers are familiar with, because the “state transition” arises from evaluating program expressions. This means that arbitrarily complex, program-specified link functions are naturally supported. Oh if only Arnaud and friends would understand this!
And this all means that you are now well prepared to take the next and final step towards building a world-class general purpose probabilistic programming system. By coupling the evaluator you will have at the end of this assignment (whether run in IS or SMC mode) with differentiable proposal and model learning you are there.
In this homework you are to implement an interpreter based on Sequential Monte Carlo. See [1, Chap. 6]. Sequential Monte Carlo requires forking the interpreter environment which requires implementing your environment using immutable datastructures (see pyrsistent) as you did in the previous homework. This is also provided for you in the support code.
Note that in SMC you should use the addresses to ensure that whatever breakpoints you choose to resample at you are observe-ing the same RV (i.e. the same address). This check is provided for you in the support code.
You might want to, before embarking on the SMC task, write an importance sampling inference engine first. This is not provided but hinted at in the support code.
The support code is extensive in this case and your task is more about understanding SMC than understanding how to implement an interpreter of CPS-ed programs. You should concentrate on understanding what sample and observe must do, and how to manipulate the interpreter state so as to arrive at a population of particles and and marginal probability estimate.
Submit a .pdf file to gradescope.ca showing your answers for each section. Please use wandb reporting and logging as in all previous homeworks.
Convergence of posterior expectations against particle count (for particle counts from 1 to 100000 in powers of ten increments) will be assessed for the 3 short HOPPL programs from HW 5.
Provide histogram plots of the distributions obtained for each return value of each program for each particle count.
Additionally, for each particle count and each program, report the marginal probability/evidence estimate returned by SMC.
In this case a huge amount of very helpful Python scaffolding is provided, highlighting in particular a trampolining interpreter that utilizes the continuation passing-style guarantee to avoid stack blow-up.