Learning to be Smooth: An End-to-End Differentiable Particle Smoother

Authors: ali  younis
erik b sudderth
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-06 21:37:25

Abstract: 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.

Main paper: 
 introduction: 
 Global localization of the state of a moving vehicle using a city-scale map is challenging due to the large area, as well as the inherent ambiguity in urban landscapes, where many street intersections and buildings appear similar. Recent work on global localization [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] has typically localized each time point independently during training, sometimes followed by temporal post-processing, often with demanding requirements like near-exact external estimation of relative vehicle poses [11] .For a broader range of state estimation problems in fields like vision and robotics, a number of methods for end-to-end particle filter (PF) training have been proposed [8, [12] [13] [14] [15] [16] . Learnable PFs are suitable for global localization because they can represent multi-modal posterior densities, propagate uncertainty over time, and learn models of real vehicle dynamics and complex sensors directly from data. However, most learnable PF methods have only been applied to simulated environments [12] [13] [14] , with only a few preliminary applications to real-world data [8, 15] .Particle filters [17] [18] [19] [20] [21] only use past observations to estimate the current state. For offline inference from complete time series, more powerful particle smoothing (PS) algorithms [22] [23] [24] [25] [26] [27] may in principle perform better by integrating past and future data. But to our knowledge, recent advances in end-to-end differentiable training of PFs have not been generalized to the more complex PS scenario, requiring error-prone human engineering of PS dynamics and observation models. Classical work on generative parameter estimation via PS [28] is limited to parametric models with few parameters. In contrast, we develop differentiable PS that scale to complex models defined by deep neural networks.After introducing differentiable particle filters (Sec. 2) and classical particle smoothers (Sec. 3), we develop our differentiable, discriminative Mixture Density Particle Smoother (MDPS, see Fig. 1 ) in Sec. 4 . Thorough experiments in Sec. 5 then highlight the advantages of our MDPS over differential PFs on a synthetic bearings-only tracking task, and also show substantial advantages over search-based and retrieval-based baselines for challenging real-world, city-scale global localization problems. Birds-Eye-View (BEV) feature map by extracting features before applying a geometric projection [11] . Map features are extracted via a feed-forward encoder, and un-normalized particle weights are computed as an inner product between BEV features and features of a local map extracted from the global map at the particle location. 
differentiable particle filters: 
 Particle filters iteratively estimate the posterior distribution p(x t |y 1:t , a 1:t ) over the state x t at discrete time t given a sequence of observations y t and, optionally, actions a t . PFs use a collection of N samples, or particles, x (:) t = {x t-1 , a t ), conditioned on actions a t if available. Of note, only simulation of the dynamics model is required; explicit density evaluation is unnecessary. Using reparameterization [29] [30] [31] , the dynamics model can be defined as a feed-forward neural network f (•) that transforms random (Gaussian) noise to produce new particles:EQUATIONt ∼ N (0, I).Measurement Updates and Discriminative Training. Proposed particles are importance-weighted by the likelihood function, wt ∝ p(y t |x(i) t )w (i)t-1 , to incorporate the latest observation y t into the posterior. The updated weights are then normalized such that N i=1 w (i) t = 1. However, for complex observations like images or LiDAR, learning accurate generative models p(y t |x t ) is extremely challenging. Recent work [8, [12] [13] [14] [15] has instead learned discriminative PFs parameterized by differentiable (typically, deep neural network) measurement models:EQUATIONHere, l(x t ; y t ) scores particles to minimize a loss, such as negative-log-likelihood or squared-error, in the prediction of true target states x t that are observed during training.The stochastic nature of PF dynamics causes some particles to drift towards states with low posterior probability. These low-weight particles do not usefully track the true system state, wasting computational resources and reducing the expressiveness of the overall approximate posterior.Particle resampling offers a remedy by drawing a new uniformly weighted particle set x(:) t from x (:) t , with each particle duplicated (or not) proportional to its current weight w (i) t . The simplest multinomial resampling strategy [23, 32, 33] chooses particles independently with replacement:EQUATIONt , . . . , w (N ) t).(3)To maintain an unbiased posterior, resampled particles have weight ŵ(i) t = 1 N . Multinomial resampling may be implemented [32] by drawing a continuous Unif(0, 1) variable for each particle, and transforming these draws by the inverse cumulative distribution function (CDF) of particle weights.Stratified resampling [23, 32, 33] reduces the variance of conventional multinomial resampling, by first partitioning the interval (0, 1] into N sub-intervals (0, 1 N ] ∪ ... ∪ (1 -1 N , 1]. One uniform variable is then sampled within each sub-interval, before transforming these draws by the inverse CDF of particle weights. Our differentiable PS incorporate stratified resampling to reduce variance with negligible computational overhead, making training more robustly avoid local optima (see Fig. 2 ).While other methods like residual resampling [34, 32, 35] have been proposed in the PF literature, this partially-deterministic approach is less robust than stratified resampling in our experiments (see Fig. 2 ), and also much slower because residual resampling cannot be parallelized across particles.For our mixture density PS, particles are resampled from a continuous Gaussian mixture, in which all components share a common standard deviation β. This resampling can equivalently be expressed asx(i) t = µ (i) t + βη (i) t , where η (i) t ∼ N (0, I) and µ (i)t is generated via discrete sampling of the mixture component means. We incorporate stratified resampling in this step to boost performance.For discriminative PFs to effectively learn to propagate state estimates over time, gradients are needed for all steps of the PF. While differentiable dynamics and measurement models are easily constructed via standard neural-network architectures, discrete particle resampling is not differentiable.Truncated-Gradient Particle Filters (TG-PF) [15] , the first so-called "differentiable" particle filter, actually treated the resampling step as non-differentiable and simply truncated gradients to zero at resampling, preventing back-propagation through time (BPTT) [36] . Due to this weakness, dynamics models were assumed known rather than learned, and measurement models were learned from biased gradients that fail to propagate information over time, reducing accuracy [14] .Soft Resampling Particle Filters (SR-PF) [13] utilize a differentiable resampling procedure that sets particle resampling weights to be a mixture of the true weights and a discrete uniform distribution:EQUATIONt , . . . , vEQUATIONGradients are then propagated via the resampled particle weights defined as:EQUATIONThis simple approach resamples low-weight particles more frequently, degrading performance. The gradients of Eq. ( 5) also have substantial bias, because they incorrectly assume model perturbations only influence the particle weights in (5) , and not the discrete particle resampling in (4).Relaxations of Discrete Resampling. While discrete particle resampling could potentially be replaced by continuous particle interpolation with samples from a Gumbel-Softmax or Concrete distribution [37, 38] , no work has successfully applied such relaxations to PFs, and experiments in Younis and Sudderth [14] show very poor performance for this baseline. Alternatively, entropyregularized optimal transport particle filters (OT-PF) [12] replace discrete resampling with an entropy-regularized optimal transport problem, that minimizes a Wasserstein metric to determine a probabilistic mapping between the weighted pre-resampling particles and uniformly weighted post-resampling particle. OT-PF performance is sensitive to a non-learned entropy regularization hyperparameter, and the biased gradients induced by this regularization may substantially reduce performance [14] . Furthermore, "fast" Sinkhorn algorithms [39] for entropy-regularized OT still scale quadratically with the number of particles, and in practice are orders of magnitude slower than competing resampling strategies. This makes OT-PF training prohibitively slow on the challenging city-scale localization tasks considered in this paper, so we do not compare to it. runs for Bearings-Only tracking (Sec. 5.1). We boost the robustness of the top-performing MDPF [14] , which previously used multinomial resampling, by incorporating variance-reduced stratified resampling; residual resampling is both slower and less effective. Stratified resampling provides larger advantages for the lesssophisticated TG-PF [15] and SR-PF [13] gradient estimators, but these baselines remain inferior to MDPF. Our MDPS substantially improves on all PFs by incorporating both past and future observations when computing posteriors. Classic FFBS particle smoothers [24, 25] have poor performance, even when provided the true likelihoods (rather than a learned approximation), showing the effectiveness of our end-to-end learning of particle proposals and weights. Forward PFs are initialized with noisy samples of the true state, while MDPF-Backward (the backwards-time PF component of MDPS) is initialized by sampling uniformly from the state space.Mixture Density Particle Filters (MDPF) [14] are a differentiable variant of regularized PFs [40, 41] . MDPF estimates a continuous kernel state density [42] by convolving particles with a continuous, and differentiable, kernel function K (such as a Gaussian) with bandwidth hyperparameter β:EQUATIONParticles are then resampledEQUATIONt , β) from this continuous mixture instead of via discrete resampling. Unbiased and low-variance Importance Weighted Sample Gradient (IWSG) [14] estimates may then be constructed by viewing the particle proposal q(z) = m(z | ϕ 0 ) to be fixed to the mixture model parameters ϕ 0 = {x (:) t , w (:) t , β} at the current training iteration. Gradients then account for parameter perturbations not by perturbing particle locations as in standard reparameterization [29] [30] [31] , but by perturbing particle importance weights away from uniform:EQUATION)With this approach, the bandwidth parameter β may also be tuned for end-to-end prediction of state distributions, avoiding the need for classic bandwidth-selection heuristics [42] [43] [44] . An "adaptive" variant of MDPF [14] incorporates two bandwidths, one for particle resampling (to propagate information over time) and a second for estimation of state posteriors (to compute the loss). Our MDPS also incorporates separate bandwidths for resampling and state estimation, as detailed below.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We discuss the limitations of our method in the main paper text. Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.• While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
from filtering to smoothing: 
 Particle smoothers extend PFs to estimate the state posteriors p(x t |y 1:T ) given a full T -step sequence of observations. (To simplify equations, we do not explicitly condition on actions a 1:T in the following two sections.) Particle smoothers continue to approximate posteriors via a collection of particles ← → x(1:N ) twith associated weights ← → w(1:N ) t, where we use bi-directional overhead arrows to denote smoothed posteriors. Classical particle smoothing algorithms, which are non-differentiable and typically assume human-engineered dynamics and likelihoods, fall into two broad categories.Forward-Filtering, Backward Smoothing (FFBS) algorithms [24, 25] A natural algorithm emerges from Eq. ( 8), where a conventional PF first approximates p(x t |y 1:t ) for all times via particles -→ x(1:N ) t with weights -→ w(1:N ) t. A backward smoother then recursively reweights the "forward" particles to account for future data, but does not change particle locations:EQUATIONBecause FFBS sets ← → x(i) t = - → x (i)t , it is only effective when filtered state posteriors p(x t |y 1:t ) substantially overlap with smoothed posteriors p(x t |y 1:T ) [25] ; performance deteriorates when future data is highly informative. FFBS also requires explicit evaluation, not just simulation, of the state transition dynamics p(x t+1 |x t ), which is not tractable for dynamics parameterized as in Eq. (1) .Two Filter Smoothing (TFS) algorithms [22, 24, 25] This yields a particle re-weighting approach where backward filter particles ←x(1:N ) t are re-weighted using the forward filter particle set, to produce the final smoothed particle weights ← → wEQUATIONConventional TFS set ← → x(1:N ) t = ← - x (1:N ) t, which similar to FFBS, makes performance heavily dependant on significant overlap in support between p(x t |y t+1:T ) and p(x t |y 1:T ). Like FFBS, TFS also restrictively requires evaluation (not just simulation) of the state transition dynamics.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA] Justification: We dont have any theoretical results but instead conduct experiments on existing datasets.Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
mixture density particle smoothers: 
 Our novel Mixture Density Particle Smoother (MDPS, Fig. 1 ) can be seen as a differentiable TFS, where the forward and backward filters of Eq. ( 13) are defined as MDPFs (Sec. 2.3). Using discriminative differentiable particle filters (MDPFs) within the TFS frameworks, and replacing Eq. ( 14) with an importance-weighted integration of forward and backward particles, enables an effective and end-to-end differentiable particle smoother. We begin by rewriting Eq. (13) Figure 3 : Position and error recall using the MGL [11] dataset. Recall is computed with the top posterior mode as well as with the best of the top-3 posterior modes, extracted via non-maximal suppression. As expected, Retrieval [3] methods do poorly due to their lack of discrimination power between neighboring map patches.Dense search [11] does better by using fine map details during localization, but it requires a ground truth hint ("Cheating" with GT, which artificially improves performance) to work well at city-scale environments. Retrieval (PF) [8] uses unlearned state dynamics, which proves useful, but still suffers from the poor discriminative ability of retrieval. In contrast, MDPF [14] uses end-to-end learned dynamics and measurement models, allowing for good performance but suffering from only using past information when estimating posterior densities. Our MDPS is able to learn similar strong dynamics and measurement models as MDPF, and also incorporates future as well as past information to achieve a more accurate posterior density and thus higher recall.where the forward and backward filters no longer condition on the current observation. This allows for functionally identical MDPFs to be used for both directions, simplifying implementation. MDPFs parameterize state posteriors as continuous kernel density mixtures:EQUATION)Unlike discrete probability measures, these continuous mixture distributions can be combined via direct multiplication to give a smoothed posterior mixture containing N 2 components, one for each pair of forward and backward particles. For this product integration of forward and backward filters, the normalizing constants for all pairs of kernels must be explicitly computed to correctly account for the degree to which hypotheses represented by forward and backward particles are consistent. These normalization constants are tractable for some simple kernels including Gaussians [46] , but more complex for the other cases such as von Mises kernels of orientation angles [47, 48] .Direct mixture multiplication eliminates the need to evaluate the dynamics model, as in classic TFS, but introduces significant overhead due to the quadratic scaling of the number of mixture components.To address this issue, our MDPS uses importance sampling where the smoothed posterior is defined by M ≪ N 2 particles drawn from a mixture of the filter posteriors:EQUATIONBy construction, this proposal will include regions of the state space that lie within the support of either p(x t |y 1:t-1 ) or p(x t |y t+1:T ), improving robustness. Our experiments set M = 2N , drawing N particles from each of the filtered and smoothed posteriors. Given true dynamics and likelihood models, importance sampling may correct for the fact that smoothed particles are drawn from a mixture rather than a product of filtered densities, as well as incorporate the local observation:EQUATIONTo more easily train a discriminative PS, rather than estimating each term in Eq. ( 19) separately, we directly parameterize their product via a feed-forward neural network l(•):EQUATIONThe posterior weight network l(•) scores particles based on agreement with y t , as well as consistency with the forward and backward filters, and implicitly accounts for the auxiliary distribution γ t (•). To allow state prediction and compute the training loss, the smoothed posterior is approximated as:EQUATIONwhere ← → β is a learned, dimension-specific bandwidth parameter. Training Loss and Gradient Computation. We discriminatively train our MDPS by minimizing the negative log-likelihood of the true state sequence:EQUATIONDuring training, the IWSG estimator of Eq. ( 7) provides unbiased estimates of the gradients of the forward and backward resampling steps. We may similarly estimate gradients of the mixture resampling (18) that produces smoothed particles, enabling the first end-to-end differentiable PS:EQUATION)Training Details. Because the smoother weights of Eq. ( 20) cannot be effectively learned when filter parameters are random, we train MDPS via a three-stage procedure. In stage 1, the forward and backward PFs are trained separately (sharing only parameters for the encoders, see Fig. 1 ) to individually predict the state. In stage 2, the PFs are frozen and the particle smoother measurement model l(•) of Eq. ( 20) is trained. In stage 3, all models are unfrozen and trained jointly to minimize the loss in the MDPS output state posterior predictions of the true states. The forward MDPF, backward MDPF, and MDPS posterior each have separate kernel bandwidths (- → β , ← - β , ← → β )that are jointly learned with the dynamics and measurement models. We randomly resample a stochastic subset of the training sequences for each step, and adapt learning rates via the Adam [49] optimizer. Computational Requirements. At training time, to allow unbiased gradient propagation, MDPS computes importance weights for each particle during resampling. For N particles and T time-steps, this requires O(T N 2 ) operations. At inference time, importance weighting is not needed as the particle weights can simply be set as uniform, and resampling only requires O(T N ) operations. All phases of our MDPS scale linearly with N at test time, in contrast with other differentiable relaxations such as OT-PF [12] , which requires O(T N 2 ) operations for both training and inference.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We disclose all important information for reproducing our results in the main text (secs. 4 and 5) and the appendix (supplement).• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. (c) If the contribution is a new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
experiments: 
 We evaluate our MDPS on a synthetic bearings-only tracking task [14] , as well as on real-world city-scale global localization. For all tasks, we estimate the MDPF/MDPS posterior distributions of a 3D (translation and angle) state x t = (x, y, θ), using Gaussian kernels for the position dimensions, and von Mises kernels for the angular dimensions of the state posterior mixtures. To allow comparison to prior discriminative PFs, we use the same bearings-only tracking task as [14] , where the 3D state of a variable-velocity synthetic vehicle is tracked via noisy bearings from a fixedposition radar. 85% of observations are the true bearing plus von Mises noise, while 15% are uniform outliers. Train and evaluation sequences have length T = 50. Unlike Younis and Sudderth [14] , we find truncated BPTT [50] is not necessary if bandwidths are initialized appropriately. Filtering particles are initialized as the true state with added Gaussian noise, while MDPF-Backward (and the MDPS backwards filter) are initialized with uniformly sampled particles to mimic datasets where often only the starting state is known. More details can be found in the Appendix.We compare our MDPS methods to several existing differentiable particle filter baselines, but no differentiable particle smoother baseline exists. Instead, we implement the classic FFBS [24, 25] algorithm (Sec. 3), which assumes known dynamics and measurement models. Since FFBS is not differentiable, we learn the dynamics model using the dataset true state pairs {x t-1 , x t } outside of the FFBS algorithm. In order to simulate from and evaluate the state transition dynamics, as needed by the FFBS, we parameterize the dynamics model to output a mean and use a fixed bandwidth parameter (tuned on validation data) to propose new particles. We also use the true observation likelihood as the measurement model, instead of a learned approximation; this boosts FFBS performance.Results. In Fig. 2 we show statistics of performance over 11 training and evaluation runs for each method. We compare to TG-PF [15] , SR-PF [13] , the classical FFBS [24, 25] , and MDPF [14] . Interestingly, MDPF outperforms SR-PF and TG-PF even when the initial particle set is drawn uniformly from the state space as in MDPF-Backward.By incorporating more temporal data, MDPS substantially outperforms MDPF. Even when unfairly provided the true observation likelihood, FFBS performs poorly since particles are simply re-weighted (not moved) by the backward smoother. This inflexibility, and lack of end-to-end learning, makes FFBS less robust to inaccuracies in the forward particle filter.We are the first to compare resampling variants in the context of modern discriminative PFs. Stratified resampling substantially improves TG-PF and SR-PF performance, but only modestly improves the worst-performing MDPF runs. This may be because even with basic multinomial resampling, the lower-variance MDPF gradients dramatically outperform all TG-PF and SR-PF variants. Residual resampling performs worse than stratified resampling, and is also much slower since it cannot be easily parallelized on GPUs, so we do not consider it for other datasets.Our global localization task is adopted from Sarlin et al. [11] , where we wish to estimate the 3D state (position and heading) of a subject (person/bike/vehicle) as it moves through real-world city-scale environments. Observations are gravity-aligned first-person images, actions are noisy odometry, and a 2D planimetric map is provided to help localize globally. We use the Mapillary Geo-Localization [11] and KITTI [51] datasets to compare our MDPS method to MDPF [14] as well as other methods specifically designed for the global localization task, which are not sequential Monte Carlo methods.Our global localization task is distinct from local localization systems, which aim to track subject positions relative to their starting position, instead of in relation to the global map origin. Visual SLAM systems [21] almost exclusively solve the local localization task, using the starting position as the origin of their estimated map. If a map is provided, then just the localization part of Visual SLAM can be run, but detailed visual or 3D maps of the environment are needed. These have prohibitive memory requirements at city-scales, and need constant updating as the visual appearance of the environment changes (e.g., with the weather/seasons) [11] . Hybrid place recognition with localization also requires detailed visual or 3D maps [52] . In our experiments, we instead seek to use planimetric maps for global localization, which are compact and robust to environment changes. It is not obvious how to apply SLAM/Hybrid place recognition systems to this type of map.Retrieval methods [1] [2] [3] [4] [5] [6] [7] rely on latent vector similarity where map patches and the observation are encoded into a common latent state space before doing a vector similarity search. These methods are trained using a contrastive loss [2, 53] that forces the observation encoding to be similar to its corresponding map patch encoding, while being dissimilar to other patch and observation encodings. Accuracy depends on map patch extraction density and patch similarity; if similar patches are mapped to near-identical encodings, performance suffers. Zhou et al. [8] extend this framework using a nondifferentiable PF, where a retrieval-based measurement model is trained outside the PF framework, and non-learned dynamics are fixed to actions with added Gaussian noise.Refinement methods [9, 10] refine an initial position estimate via expensive optimization, by maximizing the alignment of features extracted from the observation and map. Due to the extreme non-linearity of this objective, refinement methods require an accurate initial estimate to converge to the correct solution, if at all. This prevents their use for city-scale global localization.Dense Search [11] extracts birds-eye-view (BEV) features from the observed images via geometric projection (see Fig. 1 ), before applying a dense search to align BEV features with extracted map features. Heuristic alignment probabilities may be produced by tracking alignment values during search, and applying a softmax operator. Higher discretization density boosts accuracy, but requires significantly more memory and compute. Temporal information can be used by warping probability volumes onto the current time-step, but this requires near-exact relative poses which Sarlin et al. [11] determine via an expensive, black-box Visual-Inertial SLAM system [21] .In the Mapillary Geo-Localization (MGL) [11] dataset, images sequences are captured from handheld or vehicle-mounted cameras as a subject (person/bike/car) roams around various European and U.S. cities. Observations are set as 90 • Field-of-View images in various viewing directions, with actions being noisy odometry. A planimetric map of the environment is also provided via the OpenStreetMap platform [54] at 0.5 meter/pixel resolution. We generate custom training, validation, and test splits to create longer sequences with T = 100 steps. For particle-based methods, we use stratified resampling and set the initial particle sets to be the true state with added noise. More details are in the Appendix.Implementation Details. For MDPF and our MDPS, we set the dynamics model to a multi-layer perceptron (MLP) network. The measurement model incorporates BEV features [11] and map features as illustrated in Fig. 1 . The smoother measurement model incorporates additional inputs via an extra MLP. Memory constraints prevent Dense Search in city-scale environments, so we consider two methods to limit the search space. A sliding window limits the search space to a 256m × 256m area that is recursively re-centered around the best position estimate at t -1, propagated to t using a t . We can also limit the search space to a 256m × 256m area containing the true state, though this artificially increases performance. We similarly limit the search space for Retrieval, which performs poorly in large environments; Zhou et al. [8] even limit the vector search to known road networks.Results. We compare our MDPS to MDPF [14] , Dense Search [11] , Retrieval [3] implemented as detailed by [11] , and Retrieval (PF) [8] , reporting the position and rotation recall in Fig. 3 . Due to ambiguity in large city environments (e.g., intersections can look very similar), estimated state posteriors can be multi-modal (see Fig. 4 ), and thus simply reporting accuracy using the highest probability mode does not fully characterize performance. We thus also extract the top-three modes using non-maximal suppression (see Appendix), and report accuracy of the best mode. Interestingly, MDPF and MDPS give dramatic improvements over baselines engineered specifically for this task, highlighting the usefulness of end-to-end training. MDPS outperforms MDPF by using the full sequence of data to reduce mode variance, and discard incorrect modes as illustrated in Fig. 4 .Informative dynamics models boost performance, as demonstrated by the MDPS and MDPF results in Fig. 3 . We visualize the learned dynamics of the MDPS forward filter in Fig. 5 . Good dynamics models keep particles densely concentrated in high-probability regions, while also including diversity to account for sometimes-noisy actions. This enables learning of more discriminative measurement models, since training encourages the weights model to disambiguate nearby particles. Longitudinal localization performance is poor for all methods due to lack of visual features. MDPF [14] offers dramatic improvements for lateral error over Retrieval [3] , Retrieval (PF) [8] and Dense Search [11] baselines, even when these baselines are constrained to operate around the ground truth state ("Cheating" with GT). For longitudinal recall, methods using "Cheating" with GT have good performance because they are artificially constrained to be near the true state, and thus have significantly less position ambiguity along the roadway. MDPS offers further improvements over MDPF as it maintains a more diverse set of posterior modes, instead of prematurely collapsing to incorrect modes.Computational Requirements. While MDPS is more accurate than other methods, it is also more efficient than dense search. Because dense search must try many options to find the best alignment of the BEV and extracted map features, it has complexity O(KW 2 H 2 ) for K search rotations, and search locations defined on a grid of width W and height H. (For notational simplicity, we assume the BEV features and the map features have the same width and height.) This complexity can be reduced to O(KW H log(W H)) by using the Fast Fourier Transform. In contrast, MDPS has complexity O(N W H), where N ≪ K log(W H), as it only compares the BEV and map features at the particle locations. This allows MDPS to better scale to large-scale environments.We also evaluate our MDPS method for the global localization task using the KITTI [51] dataset, where observations are forward-facing camera images from a moving vehicle. We augment this datatset with noisy odometry computed from the ground truth states and use the default Train, Test1, and Test2 splits for training, validation, and evaluation respectively. Like MGL, a planimetric map of the environment is provided via the OpenStreetMap platform [54] at 0.5 meter/pixel resolution. Due to the small size of the KITTI dataset, we pre-train all methods using MGL before refining on KITTI, using the same network architectures as was used for the MGL dataset. See Appendix for details.Results. Due to the forward-facing camera, the observation images lack visual features for useful localizing along the roadway, therefore we decouple the position error into lateral and longitudinal errors when reporting recalls in Fig. 6 . Understandably, all methods have larger longitudinal error than lateral error. Interestingly, MDPF and MDPS offer similar Top 3 mode performance for small lateral errors (under 2 meters) while significantly outperforming all other methods. When the lateral error is greater than 2 meters, MDPS sees a performance gain as it maintains a more diverse set of posterior modes, whereas MDPF prematurely collapses the posterior density to incorrect modes.Like all particle-based methods, our MDPS suffers from the curse of dimensionality [55] where particle sparsity increases as the dimension of the state space increases, reducing expressiveness of state posteriors. More effective use of particles via smarter dynamics and measurement models, as enabled by end-to-end MDPS training, can reduce but not eliminate these challenges.Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material?Answer: [Yes]Justification: Code will be released on GitHub if the paper is accepted after some code cleanup.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
discussion: 
 We have developed a fully-differentiable, two-filter particle smoother (MDPS) that robustly learns more accurate models than classic particle smoothers, whose components are often determined via heuristics. MDPS successfully incorporates temporal information from the past as well as the future to produce more accurate state posteriors than state-of-the-art differentiable particle filters. When applied to city-scale global localization from real imagery, our learned MDPS dramatically improves on search and retrieval-based baselines that were specifically engineered for the localization task.In this section we give additional experiment results for the global localization task on the MGL [11] and KITTI [51] datasets.A.1 MGL Dataset Additional Results show the current true state and state history (black arrow and black line), the estimated posterior density of the current state (red cloud, with darker being higher probability) and the the top 3 extracted modes (blue arrows) for each method. By using the full sequence of observations and actions when computing state posteriors, MDPS is able to estimate a more accurate and tighter posterior than the forward or backward MDPFs. Mixture Density Particle Filtering:Given observations y 1:T and actions a 1:T with N being the number of particles 1. Initialize particle set {x(:) 1 , w (:)1 , β} using initial known state or via some other method. Normalize weights such that N i=1 w (i) 1 = 1 2. For t = 2, ..., T and i = 1, ..., N (a) Resample particle from mixture distributionx (i) t ∼ m(x (:) t-1 , w (:) t-1 , β), w (i) t = 1 N(b) Apply noisy system dynamics to particle:EQUATIONt ; y t ) 3. Output: {x igure 14: Recall of position and angle for MDPS using the MGL dataset [11] with varying numbers of particles at inference time. Here we specify the number of particles N used for the forward and backward filters of MDPS. The final MDPS posterior density is defined by 2N particles as described in sec. 4. Interestingly, performance plateaus quickly as we increase the number of particles implying MDPS's ability to use particles smartly and efficiently, allowing for fewer particles to be used, lowering the computation and memory requirements neeeded for effective models.q(x) = 1 2 m(x; - → x (:) 1:T , - → w (:) 1:T , - → β ) + 1 2 m(x; ← - x (:) 1:T , ← - w (:) 1:T , ← - β ) (b) Sample particles: ← → x (i) t ∼ q(x) (c) Compute weights ← → w (i) t = l ← → x (i) t ; y t , m( ← → x (i) t ; - → x (:) 1:T , - → w (:) 1:T , - → β ), m( ← → x (i) t ; ← - x (:) 1:T , ← - w (:) 1:T , ← - β ) q( ← → x (i) t ) 4. Output: { ← → x (:) 1:T , ← → w (:) 1:T , ← → β }A key hyper-parameter for particle filters and smoothers is the number of particles to use at inference time. Using more particles increases performance as shown in fig. 14 but performance can quickly plateau. As seen in fig. 4 , effective models tend to concentrate particles densely in likely regions of the state space. By using more particles, the particle density of these likely regions is increased but with diminishing returns. Each additional particle within the dense regions will vary only slightly from its neighbors, minimally adding to the particle set diversity. Further using more particles increases computation and memory requirements making smarter models which are more particle efficient, such as our MDPS, attractive for real world deploymentThe Bearings Only Tracking Task adopted from Younis and Sudderth [14] aims to track the state of a vehicle as it navigates a simple environment. No actions are provided for this task and the observations are given as noisy bearings to a radar station:y t ∼ α • Uniform(-π, π) + (1 -α) • VonMises(ψ(x t ), κ), where ψ(x t ) is the true bearing with α = 0.15 and κ = 50. The velocity of the vehicle varies over time, changing randomly when selecting a target new way point with 1m/s or 2m/s being equally likely. During training, ground truth states are provided every 4 time-steps however dense true states are given at evaluation time. All sequences are of length T = 50 and we use 5000, 1000 and 5000 sequences for training, validation and evaluation respectively.For all methods we use 50 particle during training and evaluation. For forward-in-time running PF methods, we initialize the particle set as the true state with small Gaussian noise (σ = 0.01) on the x-y components of the state. For the angle components of the initial particles we add Von Mises noise (with concentration κ = 100) to the true state. For backward-in-time running PF methods we set the initial particle set as random samples drawn uniformly from the state space.Learning rates are varied throughout the training stages ranging from 0.001 to 0.000001 though we find that all methods are robust to learning rate selection when using the Adam [49] optimizer, with sensible learning rate effecting convergence speed but not performance.For SR-PF [13] we set λ = 0.1.All methods (baselines and ours) for the Bearings Only Tracking Task use the same dynamics and measurement model architectures which are described below.Dynamics Models. We parameterize the dynamics model as a residual neural network as shown in figs. 15 Measurement Models. Figure 17 shows the feed-forward neural network architecture for the measurement models used for the Bearings Only Tracking Task.MDPS Forward Backward Combination. For the Bearings Only Tracking Task, the MDPS smoothed measurement model is very similar to the measurement model using for MDPF but with additional inputs. The MDPS smoothed measurement model network architecture is shown in fig. 18 . Fully Connected (8)Fully Connected (8) Fully Connected (8)Input: Observations In this section we give more information about the experiments conducted with the Mapillary Geo-Location Dataset (MGL) [11] and KITTI [51] datasets.For all particle filter methods (including ones internal to MDPS) we use 250 particle during training and evaluation and initialize the filters using 1000 particles. For PF and smoother methods, we initialize the particle set as the true state with Gaussian noise (σ = 50 meters) on the x-y components of the state. For the angle components of the initial particles we add Von Mises noise to the true state.Initial learning rates are varied throughout the training stages ranging from 0.01 to 0.000001 though we find that all methods are robust to learning rate selection when using the Adam [49] optimizer, with sensible learning rates effecting convergence speed. For comparison methods, we use the learning rates as specified by the method authors or select them via a brief hyper-parameter search if they are not stated.In the MGL dataset, observations are images captured by various types of handheld or vehicle mounted cameras. Some cameras capture 360 • images which require additional processing before being used as observations. These 360 • images are cropped to a 90 • Field-of-View in random viewing directions, with the same viewing direction being used for the whole observation sequence. All images are then gravity aligned to produce the observation sequence. A planimetric map of the environment is also provided via the OpenStreetMap platform [54] at 0.5 meter/pixel resolution, and all observation images are publicly available under a CC-BY-SA license via the Mapillary platform. All KITTI data is published under the CC-BY-NC-SA licence.Unfortunately the creators of the MGL dataset trained their methods on single observations from the dataset and did not use sequences during training [11] . As such, observations from sequences are scattered amongst the training and testing splits, preventing effecting training of methods that require longer uninterrupted sequence data such as MDPF and MDPS. We therefore create custom train, validation and evaluation splits of the MGL dataset in order to accommodate longer sequences for training and evaluation.Due to data integrity and corruption issues we exclude all sequences from the "Vilnius" portion of the dataset.Dynamics Models. The network architecture of the dynamics model used for the MGL and KITTI is shown in fig. 19 and is similar to that used in the Bearings Only Tracking task, using the same angle to vector particle transformation. Note for this dynamics model we do not mask out any component of the state. Measurement Models. The measurement model used for MDPF and MDPS uses the Birds-Eye-View (BEV) feature encoder and the map encoder from the official Dense Search implementation released by Sarlin et al. [11] . As shown in fig. 1 , a Birds-Eye-View (BEV) feature map is estimated from the observation using a geometric projection [11] where columns of the observation image are considered polar rays with features binned into course depth planes projected away from the camera focal plane. This gives a top-down representation of the local area in polar coordinates (bearing and course distance of an image feature from the camera center). The polar representation of the scene is then sampled into top-down Cartesian coordinates to yield the final BEV feature map. We refer the reader to Sarlin et al. [11] and the appendix for more details. To compute particle weights, we compute the alignment, via a dot-product, between the BEV feature map and a local region from the neural map, cropped and rotated at the current particles location. For l(•) from eqn. 20 we use fully-connected layers to produce the final smoothed particle weights from the BEV-map dot-product alignment and the forward and backward filter posterior densities. The map feature encoder is a U-Net based architecture with a VGG-19 [56] backbone and the BEV feature encoder is based on a multi-head U-Net with a ResNet-101 [57] backbone as well as a differentiable but un-learned geometric projection. We refer the reader to Sarlin et al. [11] for more details about the encoders. To derive the un-normalized particle log-weights, the BEV encoding is compared, via dot-product, to a local map patch extracted at a specific particle to compute an alignment value. This is akin to the dense search described in Sarlin et al. [11] but at only a single location determined by the particle.MDPS Forward Backward Combination. The MDPS smoother measurement model differs from the measurement models of MDPF as it requires additional inputs as described in eqn 20. We implement this model as a 4-layered, 64-wide fully-connected feed-forward neural network with PReLU [58] activation's shown in fig. 20 . Importantly all computed un-normalized weights are bound to be within [0.0001, 1] using a Sigmoid function with an offset. Input into this network is the BEV-map feature alignment computed in the same way as the MDPF measurement model as well as the posterior probability values from the forward and backward filters for the current smoothed particle. As stated in sec. 4, effective training of MDPS requires training in stages. Importantly due to VRAM constraints, we are unable to train large map and observation encoders on long sequences. Therefore we train on short sequences before freezing the encoders, training the rest of the models on longer sequences.Training procedure for MDPS on the MGL dataset:1. Train forward and backward MDPFs individually via independent loss functions, sharing map and observation encoders, on short sequences from the dataset. Here we hold the output posterior bandwidths fixed to prevent converging to poor local optima where the bandwidth is widened while the dynamics and measurement models are not informative. 2. Freeze all MDPF models, unfreeze the MDPF output posterior bandwidths and train on long sequences. 3. Freeze all MDPF models (including bandwidths) and train the MDPS measurement model and output posterior bandwidth on long sequences. 4. Unfreeze all models except the map and BEV encoders and train MDPS on long sequences.Due to the small size of the KITTI dataset along with pre-training using the MGL dataset, a special constrained training procedure is required to prevent immediate over-fitting to the training split.Instead of jointly refining all components simultaneously, we fine-tuning the forward and backward MDPFs before freezing those models and fine-tuning the MDPS smoothed measurement model:1. Train the forward and backward MDPFs individually via independent loss functions, sharing map and observation encoders, on short sequences from the dataset. We hold the output posterior bandwidths fixed.2. Freeze BEV and map encoders, training the forward and backward MDPFs individually via independent loss functions on long sequences.3. Freeze all MDPF models, unfreeze the MDPF output posterior bandwidths and train on long sequences.4. Freeze all MDPF models (including bandwidths) and train the MDPS smoothed measurement model and output posterior bandwidth on long sequences.5. Freeze all models except for the MDPS output posterior bandwidth and train on long sequences.Retrieval. The Retrieval [3] baseline as described by Samano et al. [3] encodes individual patches from the environment global map into the a latent space. This is inefficient if the map patches are densely sampled and is prohibitive to run for large environments. Instead a dense feature map can be predicted from the global map in one forward CNN pass to generate dense map encoding for map patches roughly sized according to the CNN receptive field [11] . We adopt this dense encoding approach for Retrieval, implementing the Retrieval method as specified by Sarlin et al. [11] .Dense Search. For Dense Search we use the official implementation released by Sarlin et al. [11] which differs from the text description present in the official paper. In the paper description a location prior is computed from the provided map which estimates regions of the state space that are likely to be occupied (e.g. the prior says that rivers and inside buildings are unlikely to be occupied by a car). The prior is then multiplied with the observation likelihood (probability volume computed via dense search) to produce the final state posterior. In the official implementation this prior is disabled making the state posterior simply the observation likelihood. Further we use VGG-19 [56] as our map encoder backbone.Retrieval (PF). Zhou et al. [8] embeds standard Retrieval methods within a non-differentiable particle filter where the dynamics are set as Gaussian Noise:EQUATIONIn our experiments we set γ as 2.5m for the x-y state position components and 15 • for the angular state components, chosen via a brief hyper-parameter search. The measurement model is defined asEQUATIONwhered (i)t is the alignment of the observation latent encoding with the map patch encoding at the current particles location x (i) t ,computed via the Retrieval method. After a brief hyper-parameter search we set σ = 2 in our experiments.Applying baselines to city-scale environments. Due to memory constraints, dense search over the whole map is not possible (approx. 809 GB is needed for T = 100 length sequence at 0.5m per pixel resolution). We therefore offer 2 methods for applying this dense search at city scales. Ground Truth (GT) Cheat Method: using the ground truth state, we extract a small region from the map in which we do dense search. This greatly reduces the search space, saving memory but also greatly (and artificially) improves performance. Sliding Window Method: At t = 1 a small region extracted around the true state is densely searched. At subsequent time-steps, the best alignment from the dense search of the previous time-step is propagated using a t and used as the center of a new small region which is then searched. Retrieval methods tend to fail when applied to large environments with Zhou et al. [8] even limiting the search to patches on known road networks. To address this, we limit the search space of Retrieval like in Dense Search using the GT Cheat and Sliding Window techniques, considering map patches within small regions.Due to multi-modality of the posterior estimate, simply extracting the top mode to evaluate errors is not a good gauge of performance. Instead we to extract the top-3 modes from the posterior density for evaluation. This can be easily achieved via a non-maximal suppression scheme where modes are extracted before particles around those modes are deleted. Specifically after extracting the top mode, the distance of all particle to that top mode is calculated. Particle within some threshold of the top mode are deleted from the particle set and the weights of all remaining particles are re-normalized to admit a valid probability density after deletion. The next top mode is then extracted and the deletion process repeated until a total of 3 modes are extracted. In our implementation, we delete particles that are within 5m and 30 • of the top mode.For methods that admit a discrete probability volume (such as Dense Search and Retrieval), we suppress the values of all probability cells within 5m and 30 • of the top mode during the deletion step. Extracting the top mode can be simply achieved by finding the maximum value within the discrete probability volume.We give an approximation for compute resources needed to run our experiments in tables 1, 2 and 3. Since our experiments are bottle-necked by GPU resources and require only minimal CPU and memory needs, we report the GPU needs and GPU runtime for each experiment. In addition to the compute resources stated in this section, we used additional resources over the course of our project when developing our methods, though the amount of resources used is difficult to quantify and thus we do not report here.For evaluation, all methods can comfortably run in under 2 hours for the full evaluation split of MGL (using a NVIDIA A6000 GPU) and in under 1 hour for Bearings Only (using a NVIDIA RTX 3090 GPU) and KITTI (using a NVIDIA A6000 GPU). Justification: Yes the abstract and introduction state the claims we are making in the main paper text. We backup these claims with experimental results in sec. 5. Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Important details needed to understand the results are given in the main paper (sec. 5) with additional detail given in the appendix (supplement) for more curious readers.Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] .Justification: Our work primarily focuses on state estimation systems for robotics. As such there is little risk for abuse of our methods without substantial innovation by a bad actor and thus the broader negative impacts of our work is very limited.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] .Justification: Our work focuses on general state prediction models that can be applied to a range of tasks though we only use synthetic or real world robotics datasets limiting the ability of our models to be misused.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix:  


Decision: This paper presents a novel end-to-end differentiable particle smoother called Mixture Density Particle Smoother (MDPS) for state estimation problems in robotics and computer vision. The key contributions are:

1. Extending recent advances in differentiable particle filters to the more complex particle smoothing scenario.
2. Developing a gradient propagation framework across long time sequences for training particle smoothers.
3. Integrating forward and backward particle streams with stratified resampling and importance weighting.
4. Demonstrating improvements over state-of-the-art particle filters and search-based baselines on real-world, city-scale global vehicle localization tasks, albeit under the assumption that the localization is over a planimetric global map.

The reviewers were split in their assessments, with two recommending acceptance and two recommending rejection. The positive reviews highlighted the novelty of the approach, the strong experimental results and specifically the performance gains over rfiltering-only approaches, and the potential impact on real-world applications. The negative reviews raised concerns about the clarity of the mathematical presentation and the technique/claims, and questions about the practical applicability given the computational demands.

The authors' rebuttals addressed many of these concerns, providing additional details on the mathematical foundations, clarifying the novelty of their approach, and explaining the experimental setup. They also acknowledged limitations and areas for future work. While there were specific concerns regarding insufficient baseline comparisons, the authors state their approach operates under significantly more challenging conditions (e.g. estimation over a much larger parameter counts). There has been a concern regarding the definition of stratified resampling, which despite author responses, does not seem to have been fully resolved. 

Despite the split opinions, I recommend accepting this paper with the condition that the authors address the clarity and rigor concerns in a revised version. The reasons for this recommendation are:

1. This is the first work to successfully develop an end-to-end differentiable particle smoother, which is a non trivial contribution to the field, whereas differentiable particle filters do exist.
2. The method demonstrates substantial improvements over baselines on tasks that are moderately challenging. 
3. The approach has the potential to address important problems in robotics and computer vision with potential real-world applications. 
4. The authors have actively participated in the discussion to help alleviate reviewer concerns, and have shown willingness to address reviewer concerns and improve the paper.

To address the remaining concerns, the authors should:
1. Improve the clarity and rigor of the mathematical presentation, particularly around gradient estimations, and the definition of stratified resampling in the context of the this paper. 
2. Add more detailed comparisons to classical particle smoothing methods, even if only in synthetic scenarios.
3. Provide a more in-depth discussion of the computational requirements and potential limitations in high-dimensional settings, while also highlighting the fact that inference is more efficient. 
4. Consider adding pseudocode for the algorithm to improve reproducibility.

In conclusion, while there are areas for improvement, the novel contributions and strong empirical results make this paper a valuable addition to the NeurIPS proceedings. The authors should use the revision period to address the noted concerns and strengthen the paper further.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: None.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: **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: questions: Can you explain how the proposed method achieves differentiable stratified resampling?
limitations: limitations: I appreciate the authors' candour that the proposed method will suffer from a curse of dimension.
paper_summary: paper_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.
strength_weakness: strength_weakness: [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: 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?
limitations: 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.

Comments: title: Re: Unbiased gradients of stratified resampling
Re: Proof of unbiasedness
Unbiased gradients of stratified resampling
Proof of unbiasedness
Response to Authors
comment: 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.
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.
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.
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.
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.
> 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).
> 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.
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?
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.