For challenging state estimation problems arising in domains like vision and robotics, particle-based representations attractively enable temporal reasoning about multiple posterior modes. Particle smoothers offer the potential for more accurate offline data analysis by propagating information both forward and backward in time, but have classically required human-engineered dynamics and observation models. Extending recent advances in discriminative training of particle filters, we develop a framework for low-variance propagation of gradients across long time sequences when training particle smoothers. Our"two-filter'' smoother integrates particle streams that are propagated forward and backward in time, while incorporating stratification and importance weights in the resampling step to provide low-variance gradient estimates for neural network dynamics and observation models. The resulting mixture density particle smoother is substantially more accurate than state-of-the-art particle filters, as well as search-based baselines, for city-scale global vehicle localization from real-world videos and maps.
Paper
Similar papers
Peer review
Summary
This paper proposes an end-to-end differentiable particle smoother and presents its application to global localization of a subject moving through real-world city-scale environments. Although there exists prior work in differentiable particle *filtering*, such as Mixture Density Particle Filters (MDPF), *smoothing* yields a more accurate estimate for offline data processing as it incorporates all the observations taken along the full trajectory. This paper revisits the classic formulation of Two Filter Smoothing (TFS) and leverages its principle to fuse two MDPFs, one running forward in time and one backward, into the novel Mixture Density Particle Smoother (MDPS). MDPS achieves higher log-likelihood and better tracking accuracy compared to MDPF and other prior work.
Strengths
* To my knowledge, this paper proposes the first framework for end-to-end differentiable particle smoothing. Smoothing is a powerful tool for offline state estimation and expected to achieve better accuracy than filtering. The proposed MDPS is a valuable framework for offline state estimation that does not require hand-designed state transition or observation models. * The technical approach is a sound combination of MDPF and TFS. Although I have some remaining questions about the underlying math (which is discussed below), the authors seem to have successfully designed their differentiable smoothing framework by leveraging the principled TFS formulation. * Empirical results show a clear advantage of the smoothing framework compared to its filtering counterpart as well as other prior work based on non-probabilistic schemes (e.g. refinement).
Weaknesses
[EDIT] All major concerns have been resolved after the rebuttal. * Some of the math presented in Section 3 for TFS seems to be incorrect. Specifically, I do not think equation (14) holds; it seems to be missing $p(y_t \mid x_t)$ from its numerator. Similarly, the resulting equation (15) for the particle weights does make sense either; multiplying a weight by a weighted sum of estimated states would not result in a weight. It would instead result in a new state. Please check (14) and (15) again and correct any errors. Also, please clarify how (14) and (15) relate to the practical implementation of MDPS presented in Section 4. In its current form of the paper, (14) and (15) seem unnecessary for MDPS because we instead have the correct equation (16) to begin with. * Many figures should be updated for better readability when printed on paper. Figures 1, 4, 7 - 11 have map patches and RGB observations that are too small. I suggest that the authors increase the font size as well and make each component in the figures bigger. The same goes for Figures 3 and 6, where the legends are too small to associate different curves with different methods. More details on MDPF would be appreciated at the end of Section 2 for self-completeness of the information. Specifically, I did not fully follow what the “adaptive” variant means and why two bandwidths was necessary. * More details on MDPF would be appreciated at the end of Section 2 for clarity. Specifically, I did not fully follow what the “adaptive” variant means and why two bandwidths were necessary.
Questions
[EDIT] All major concerns have been resolved after the rebuttal. * For MDPS, did you ever try initializing the estimates from some random states rather than the noised version of the true states? I wonder whether smoothing can actually correct erroneous initial estimates. If true, that is another advantage compared to MDPF, since we cannot hope for filtering to fix errors in initial estimates at all. * MDPS requires more GPU runtime to train than MDPF by design, as presented in Tables 1, 2, and 3. Would MDPF still perform worse than MDPS even when you let MDPF train longer to match the GPU runtime of MDPS? In other words, would the loss and the accuracy of MDPF not improve further with additional training epochs?
Rating
7
Confidence
4
Soundness
3
Presentation
2
Contribution
3
Limitations
* As a fundamental limitation of the proposed approach, training requires three separate stages and thus takes more GPU runtime. I would appreciate it if the authors could comment on the tradeoff between better performance and more demand for compute when compared to MDPF.
Summary
My understanding is that this work seeks to learn a state-space model by differentiating through a regularised version of the sequential Monte Carlo (SMC) approximation of the the (generalised) two-filter smoother.
Strengths
I am not very familiar with the applications used as numerical examples but they seem to be reasonably close to real-world scenarios.
Weaknesses
**Lack of clarity & rigour** I do not believe that the presentation of this work is adequate for NeurIPS. The manuscript is much too informal and therefore very difficult to follow and verify. It reads like a mid-1990s engineering conference paper. For example, * The work should really include some pseudo-code. Without this, it is very hard to even understand what the proposed algorithm exactly is. It is not even entirely clear to me whether the proposed method seeks to learn only the measurement model or also the system equation. The short paragraph on "Training details" at the end of Section 4 is also highly insufficient. * Throughout Section 3 and 4, the same symbols seem to be used for model densities and their (e.g. Monte Carlo or other) approximations * Lines 70/71 claim: "Our differentiable PS incorporate stratified resampling to reduce variance with negligible computational overhead, making training more robustly avoid local optima". I don't find evidence for this and it is not clear to me how the authors would achieve differentiable stratified resampling. * Some notation is not or insufficiently clearly defined, e.g. $\hat{w}^{(i)}$ and its gradient in Equation 7. * Line 108 mentions "unbiased" gradient estimates but I cannot see how this would be true for any of the proposed methodology. **Missing baselines** There are well-known SMC based, recursive parameter-estimation methods against which the method should really be compared, e.g.: Kantas, N., Doucet, A., Singh, S. S., Maciejowski, J., & Chopin, N. (2015). On particle methods for parameter estimation in state-space models. **Insufficient motivation** It is not clear to me what the motivation for the proposed approach is, except that no one has previously tried to differentiate through the two-filter smoothing approximation.
Questions
Can you explain how the proposed method achieves differentiable stratified resampling?
Rating
3
Confidence
3
Soundness
1
Presentation
1
Contribution
1
Limitations
I appreciate the authors' candour that the proposed method will suffer from a curse of dimension.
Proof of unbiasedness
> Line 108 mentions how unbiased gradient estimates may be produced via the Importance Weighted Sample Gradients (IWSG) estimator proposed in [14]. IWSG computes gradients based on importance sampling [21]. Briefly, importance sampling itself produces unbiased weighted samples from some distribution of interest, and therefore differentiating through importance sampling yields unbiased gradients as well. Experiments in [14] show that this approach has dramatically reduced variance compared to reparameterization-based gradient estimators. Thank you. I have now read [14]. It seems to me that the IWSG from [14] approximates the particle approximation of each filter by a kernel density estimate which is indeed differentiable. However, due to the introduction of this extra layer of (kernel-density) approximation, I don't see how the IWSG method from [14] would give unbiased gradients of the **original** particle filter. It might give unbiased gradients of some (likely biased) approximation. But **having unbiased gradients for an approximation of a particle filter is not the same as having unbiased gradients for the particle filter itself.** Unfortunately, like the present manuscript, [14] is written in a highly informal manner and does not seem to provide any proof of the claimed unbiasedness. I would be willing to raise my score if the authors could actually provide a proof of the claim that the proposed method from [14] gives unbiased gradients for the **original** particle filter. In my view, providing rigorous proofs of such claims is a must for a NeurIPS publication.
Unbiased gradients of stratified resampling
> Stratified resampling [31,32] is a method of drawing i.i.d. samples from some target distribution while reducing the variance associated with those samples. These samples can be thought of as uniformly weighted samples from the target distribution (i.e. where all the weights are equal). To compute gradients for these samples we use Importance Weighted Sample Gradients (IWSG) [14] which can be applied to any sampling method that produces i.i.d. samples. IWSG propagates gradients via adjusting the weights of the drawn samples (which are initially uniform), yielding a differentiable stratified resampling technique that has the lower sampling variance properties of stratified resampling and the unbiased gradients of IWSG. To raise my score, I would want to see an actual proof that the claim "IWSG gives unbiased estimates of (stratified) resampling" is true. As discussed in my previous comment, what the present method at most gives is an unbiased estimate of a gradient of some (very likely biased) **approximation** of the particle filter (for any arbitrary resampling scheme).
Re: Unbiased gradients of stratified resampling
We emphasize that the “true” particle filter that we are trying to approximate, which will be run at test-time, is a “regularized” particle filter that uses KDEs to approximate marginals. Please see our other comment (Re: Proof of unbiasedness) for more details on this point. For the KDE resampling step, some number of particles will be drawn from each of the KDE mixture components, before continuous sampling from that component’s kernel (a Gaussian or von Mises density in our experiments). While stratified resampling allocates particles to mixture components via a distinct algorithm, the expected number of particles allocated per component is identical to classic multinomial resampling. See [31, Sec. 2.3] for a proof of this. Then by the linearity of the expectation operator, gradients of this stratified resampling step may be computed via the same importance-sampling estimator we use for multinomial resampling. We appreciate the question, and agree this point did not have adequate detail in our submitted manuscript. We will add additional detail (adapting the proof in [31] to our setup/notation) in future revisions.
Thank you. I still don't exactly understand what the authors mean by "stratified" resampling in their context. But it is not what is normally called "stratified resampling" in the literature. I continue to think that this paper needs to be greatly improved in terms of rigour, clarity and presentation before it is publishable. I would recommend that the authors take a look at the presentation of particle filters in publications in high-ranking computational statistics journals over the past decade for examples on how to achieve this.
Re: Proof of unbiasedness
We did not emphasize this due to space constraints, but the theoretical foundations of KDE-based particle filters (which are standardly called “regularized” particle filters in the literature) are quite strong. The cited paper by Musso et al. [40] gives an overview, and detailed results are developed by Le Gland and Oudjane (Annals of Applied Prob. 2004). For conventional discrete-resampling particle filters, theoretical results show weak convergence to the optimal filter posterior as the number of particles becomes large. Regularized particle filters have similar guarantees, but by directly approximating the posterior density, one can also obtain strong convergence (in variational distance or other Lp norms) to the optimal posterior. Moreover, while standard particle filters require strong “mixing” assumptions on the dynamics to avoid degeneracy, regularized filters behave better (in both theory and practice) for low-noise dynamics due to the diversity provided by their continuous resampling step. By “original” particle filter, we assume you mean the basic “bootstrap” particle-filter that does discrete resampling with replacement. Computing gradients for such particle filters is not a goal of our paper, because they are inferior (in both theory and practice) to regularized (KDE-based) particle filters. At test time, our mixture density particle filters/smoothers employ KDE regularization, and thus this regularization must also be accounted for when computing gradients during training. As detailed in [14, Sec. 4], the IWSG method does give an unbiased estimate of gradients for the regularized, KDE resampling step. The mathematical proof is simple because we build on classic importance sampling principles, but it is nevertheless novel (in this context) and empirically effective. In the classic particle filtering literature, regularized particle filters were already motivated by having greater test-time stability/robustness, as well as superior theoretical guarantees. One interesting conclusion of our work is that in addition to having these advantages, the smoothness of regularized particle filters also has the advantage of making accurate gradient estimation easier. Experimentally, differentiable particle filters based on discrete-resampling perform dramatically worse than our approach (see the TG-PF and SR-PF baselines in Figure 2 of this submission, and the wider experimental comparison in [14, Figure 5]). **Reference:** Le Gland, F., & Oudjane, N. (2004). Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters. The Annals of Applied Probability, 14(1), 144-187.
Summary
The author's propose the first differentiable particle smoother, building on the MDPF of Younis and Sudderth which replaces the multinomial resampling step with a sampling from a KDE mixture. Their smoother is a two filter smoother where both the forwards and backwards filters are MDPFs. Instead of using the forwards filter to re-weight the particles from the backwards filter, as is conventional, particles are drawn directly from the mixture of the forwards and backwards posteriors. The author's test their smoother, first a toy bearings only tracking example. Then the a more complicated visual localisation task as well and the KITTI dataset. The smoother out performs the state-of-the-art filtering and search-based methods tested.
Strengths
1. A differentiable particle smoother is the obvious next step to differentiable filtering, especially given much previous work trains their filters in an offline, batched way on with access to ground truth latent state in training. I.e. on smoothing problems. This is the first paper to successfully construct a differentiable smoother capable of learning the complete model. 2. The experiment results are very strong and give good credibility to the algorithm. The used scenario is considerably more complex than those often used to test algorithms in a similar class. 3. Using the direct product of the mixtures simplifies the calculations greatly. 4. The paper is well organised and easy to follow.
Weaknesses
1. This method and it's predecessor the MDPF appear to enjoy less theoretical support than other differentiable particle algorithms such as \'{S}cibior and Wood's stop gradient resampling or Thornton, Corenflos et al.'s OT resampler. For example neither the gradient estimates nor state estimates appear to be consistent, or at least there is no proof they are. 2. Unlike the MDPF, this smoother requires the pointwise evaluation of the posterior density. This differs from the usual two filter smoother, I am unconvinced that the KDE approximation is accurate enough for this purpose. Some more analysis could be used to justify this approach. 3. This method has potential impact outside of just visual localisation, instead of several visual localisation experiments an example of a different problem could have boosted the apparent impact. 4. The text on the figures is far too small.
Questions
None.
Rating
7
Confidence
4
Soundness
3
Presentation
3
Contribution
4
Limitations
It is mentioned in the limitations that the curse of dimensionality may be lifted somewhat with smarter proposal. There is no evidence that this algorithm nor the MDPF is adept at learning a non-bootstrap proposal.
Summary
The paper proposes a learnable differentiable particle smoother system that extends an existing differentiable particle filter to a smoother. The method utilizes two independent particle filters for the two smoothing directions with importance sampling to address computation scaling issues.
Strengths
- Proposed smoothing approach outperforms filtering setting - Combination of sensible components into the proposed filtering setup
Weaknesses
While the proposed method appears to work and improves over the baseline particle filter variant it is unclear how well it performs in contrast to other smoothers which would pose a fair comparison. Additionally, the particular task of large scale global localization is something that robotics has been investigating for a long time and as such one would expect to see comparisons to the typical way this is solved, such as full visual SLAM or hybrid place recognition with localization. As the KITTI dataset is used it is also disappointing that no comparison to the benchmark results of the dataset are presented. Overall it is unclear how well the proposed method works when compared to known approaches deployed in practice. The power of a learnable filter/smoother is that it can learn models where it is hard or impossible to define them manually. However, the chosen application has very well defined and workable models making the motivation less convincing. As such it would be highly interesting to see the method be evaluated on scenarios where no models exist or even exist and are compared with. In line with that it would also be interesting to know how feasible it is to run the proposed method on higher dimensional data. The method requires a significant amount of time to train and run which makes it questionable whether it is even practical for real applications. Another issue arises from this is that different methods were provided with different amount of training time. While it is valid to see how well methods work when given the same parameters (particles) it is also important to assess how good other methods would perform if they had access to the same amount of training time which for the MDPF vs MPDS is still twice as much. The paper mentions that given true dynamics and likelihood models the sampling will compensate for the mismatch between samples and density mixture. Is that statement meant to indicate that these ground truth models are required, or that in an ideal case this would technically happen? If the first meaning is intended, where do these models come from? If the second meaning is intended, how close does the proposed method get to this and is there a way to assess that? It appears that the absolute error of the proposed method and all others is exceedingly large with being many meters off to achieve any reasonable amount of recall. This is where reproducing numbers from the KITTI benchmark is crucial to get an idea of the hardness of the problem. Figure 5 is hard to interpret, especially since there are now comparisons to other methods provided. While one can see that the prediction somewhat maps to parts of the future state it is very noisy and unclear how good it actually is. Given the massive training times of the method, it would be important to provide insights into the scalability both in terms of number of particles and dimensionality of the estimation problem. Another question that arises in that regard is how the proposed method compares to methods based around Stein variational inference [1] which is capable of handling high-dimensional problems very efficiently. Overall, while the proposed method performs better than other filtering methods it is unclear how practical the method is given the required compute time and limitation in the dimensionality of problems. This is further exarberated by the fact that there is no comparison to typical solutions of the chosen problem setups and a lack of particle smoother baselines. [1] Liu, Qiang, and Dilin Wang. "Stein variational gradient descent: A general purpose bayesian inference algorithm." *Advances in neural information processing systems* 29 (2016).
Questions
- With regards to the sampling, in the paper M is selected to be equal between the two filter directions. What's the impact of selecting M and it's distribution onto the two distributions? - In the description of baseline methods it is mentioned that refinement methods require an "accurate initial estimate". How good does this have to be in practice and/or in the specific experiments shown in the paper?
Rating
3
Confidence
4
Soundness
2
Presentation
3
Contribution
2
Limitations
The limitation section is very basic and really is about the limitation of the family of methods in general rather than the proposed method. Expanding on that and providing information about the proposed method would be expected.
Response to Authors
I greatly appreciate the authors for taking the time and effort to prepare the rebuttal. The initial response by the authors have largely addressed my concerns, and I will increase my score accordingly. Below please find my response. * > We agree that the details on MDPF in Sec. 2 are brief, and that expanding this section could be beneficial. In short, the adaptive MDPF as described in [14] is simply a particle filter that decouples the distribution used for resampling and the distribution used as the posterior estimate. The rationale is that the distribution used for resampling particles may not necessarily be appropriate for estimating the state posterior, since the latter may concentrate probability mass more tightly when observations are informative. Adaptive MDPF decouples the resampling and posterior bandwidths and learns each separately, allowing the resampling and posterior distributions to be separately tuned for each application. Thank you for clarifying. Please include this piece of information into the paper if the space permits. * > With regard to MDPS initialization, in the Mapillary and Kitti experiments we initialize MDPS with particles within approximately 150 meters of the true state with the localization area only being 614x614 meters (i.e. particles are drawn randomly from about ~19% of the localization area). This initialization results in erroneous initial estimates for MDPF but interestingly we find that MDPS is able to correct these erroneous initial estimates by using information from the backward filter. Given this, we believe that MDPS could correct initial states when initialized with totally random particles. This seems to be a reasonable performance improvement to expect, over any filtering-based approaches. I highly recommend the authors to highlight this point in the paper so the fundamental advantage of smoothing is made even clearer.
Thank you for your response. Reading the other reviews, I agree that the full pseudo-code should appear, even if just in an appendix. A couple of questions: I am personally not very familiar with the theory of KDE-based (or regularised) particle filters, does consistency hold in the particle filtering case of recursive approximation? If such results exist they could be mentioned in the text. I missed the details on the adaptive MDPF on first reading. How does this strategy differ from the well known auxiliary particle filter [Pitt and Shepard 1999], that also uses a different distribution for weighting and resampling, other than that the distributions are both learned rather than analytically optimised?
Thank you for taking the time to respond to our rebuttal. We will add pseudo-code to the appendix in later revisions of this paper. To answer your questions: **I am personally not very familiar with the theory of KDE-based (or regularised) particle filters, does consistency hold in the particle filtering case of recursive approximation?** We did not emphasize this due to space constraints, but the theoretical foundations of KDE-based particle filters (which are standardly called “regularized” particle filters in the literature) are quite strong. The cited paper by Musso et al. [40] gives an overview, and detailed results are developed by Le Gland and Oudjane (Annals of Applied Prob. 2004). For conventional discrete-resampling particle filters, theoretical results show weak convergence to the optimal filter posterior as the number of particles becomes large. Regularized particle filters have similar guarantees, but by directly approximating the posterior density, one can also obtain strong convergence (in variational distance or other Lp norms) to the optimal posterior. Moreover, while standard particle filters require strong “mixing” assumptions on the dynamics to avoid degeneracy, regularized filters behave better (in both theory and practice) for low-noise dynamics due to the diversity provided by their continuous resampling step. In this context, one can think of the KDE smoothing as adding a small amount of regularization/bias to the density estimate in order to reduce variance. For classic regularized particle filters, this bias is decayed to zero as the number of particles increases by reducing the kernel bandwidth (theorems characterize the optimal convergence rate). For our mixture density particle filters/smoothers, the bandwidth is implicitly tuned to the given application and particle budget via the training process. **I missed the details on the adaptive MDPF on first reading. How does this strategy differ from the well known auxiliary particle filter [Pitt and Shepard 1999], that also uses a different distribution for weighting and resampling, other than that the distributions are both learned rather than analytically optimised?** Great question. The classic auxiliary particle filter is a generative model that tries to look “one step ahead” in the discrete resampling step, by approximating the likelihood of the next observation. However to do this, it needs to be able to quickly compute a mean/mode of the dynamics, which is easy for many classic models (e.g., if dynamics are a fixed non-linear function plus Gaussian noise) but not for our scenario (where dynamics are parameterized by a learned neural network and may be complex, see Fig. 5). In contrast, our tuning of the KDE resampling bandwidth is not determined by a one-step lookahead of the next observation, but instead by the behavior of the particle filter over many future time steps (as quantified by backpropagation of loss gradients). Interestingly, it is not clear how to do this tuning based on theoretical results for standard particle filters, so we are unaware of direct analogs of our approach in the classic particle filter literature. In some sense, our adaptive proposals and the auxiliary PF are complementary to each other, and in future research it would be interesting to explore variants of the auxiliary PF idea that accommodate the more complex dynamical models we consider. **Reference:** Le Gland, F., & Oudjane, N. (2004). Stability and uniform approximation of nonlinear filters using the Hilbert metric and application to particle filters. The Annals of Applied Probability, 14(1), 144-187.
Thank you for the clarifications. While I understand the points I am currently not fully convinced by them. I can see that the proposed method works and could be useful, yet I do not truly see how the application used to showcase it is a good one. At this stage I will not change my score but will keep an open mind during the reviewer discussion.
Decision
Accept (poster)