just a quick post to announce that particles now implements several of the smoothing algorithms introduced in our recent paper with Dang on the complexity of smoothing algorithms. Here is a plot that compares their running time for a given number of particles:
All these algorithms are based on FFBS (forward filtering backward smoothing). The first two are not new. O(N^2) FFBS is the classical FFBS algorithm, which as complexity O(N^2).
FFBS-reject uses (pure) rejection to choose the ancestors in the backward step. In our paper, we explain that the running time of FFBS-reject is random, and may have an infinite variance. Notice how big are the corresponding boxes, and the large number of outliers.
To alleviate this issue, we introduced two new FFBS algorithms; FFBS-hybrid tries to use rejection, but stops after N failed attempts (and then switch to the more extensive, exact method). FFBS-MCMC simply uses a (single) MCMC step.
Clearly, these two variants runs faster, but FFBS-MCMC wins the cake. This has to do with the inherent difficulty in implementing (efficiently) rejection sampling in Python. I will blog about that point later on (hopefully soon). Also, the running time of FFBS-MCMC is deterministic and is O(N).
That’s it. If you want to know more about these algorithms (and other smoothing algorithms), have a look at the paper. The script that generated the plot above is also available in particles (in folder papers/complexity_smoothing). This experiment was performed on the same model as the example as in the chapter on smoothing in the book, essentially. I should add that, in this experiment, the Monte Carlo variance of the output is essentially the same for the four algorithms (so comparing them only in terms of CPU time is fair).