Monte Carlo Filtering Objectives

1 Introduction

Learning a generative model with latent variables for time series is of interest in many applications. However, exact inference and marginalization are often intractable for flexible generative models, making it challenging to learn. There are a few popular approaches to circumvent these difficulties: implicit methods that learn generative models by comparing generated samples to data distributions like Generative Adversarial Networks (GANs) [Goodfellow et al., 2014]; and explicit methods that define surrogate objectives of the intractable marginal log-likelihood like Variational Autoencoder (VAEs) [Kingma and Welling, 2014], or tractable marginals by invertible transformations like Normalizing Flows (NFs) [Rezende and Mohamed, 2015]. Explicit methods are often preferable when latent/encoded information is of importance, e.g. filtering and smoothing problems for some subsequent tasks. In this work, we mainly focus on the second approach and propose a family of surrogate filtering objectives to learn generative models and adaptive importance proposal models for time series.

∗Contact Author

Researchers have introduced various surrogate objectives using variational approximations of intractable posterior for time series, known as evidence lower bounds (ELBOs), such as STONE [Bayer and Osendorfer, 2014], VRNN [Chung et al., 2015], SRNN [Fraccaro et al., 2016], DKF [Krishnan et al., 2017], KVAE [Fraccaro et al., 2017]. However, they typically suffer from a general issue caused by the limited flexibility of the variational approximations, thus restricting the learning of generative models. To alleviate this constraint, IWAE [Burda et al., 2016] proposes a tighter objective by averaging importance weights of multiple samples drawn from a variational approximation. Monte Carlo objectives (MCOs) [Mnih and Rezende, 2016] generalizes the IWAE objective and ELBOs for non-sequential data. AESMC [Le et al., 2018], FIVO [Maddison et al., 2017], and VSMC [Naesseth et al., 2018] extend this idea for sequential data using the estimators by Sequential Monte Carlo (SMC) and propose closely related surrogates objectives for learning.

Inspired by MCOs and the sequential variants, we propose Monte Carlo filtering objectives (MCFOs), a new family of surrogate objectives for generative models of time series, that

• broadens previously limited choices of estimators for time series other than SMC,
• possesses unique properties such as monotonic convergence and asymptotic bias, revealing the factors that determine a tighter objective: the number of samples and importance proposals,
• reduces high variance in gradient estimates of proposal models common in state-of-the-art algorithms, without introducing bias, which allows for faster convergence and sample efficient proposal models.

The paper is organized as follows: we first review the definition of MCOs and discuss common limitations of existing filtering variants. In Section 3, we derive MCFOs, explain their relations to other objectives and important properties. We demonstrate two instances of MCFOs with SMC and Particle Independence Metropolis-Hasting (PIMH) to learn models on 1) Linear Gaussian State Space Models (LGSSMs), 2) nonlinear, non-Gaussian, high dimensional SSMs of video sequences, 3) non-Markovian music sequences 1 .

1 See [Chen et al., 2021] for a complete version of this manuscript including appendices.

2 Background

2.1 Monte Carlo Objectives

For a generative model with observation x and latent state z, a Monte Carlo objective (MCO) [Mnih and Rezende, 2016] is defined as an estimate of the marginal log-likelihood log p(x) by samples drawn from a proposal distribution q:

where R is any unbiased estimator of p(x) that E[R] = p(x). It is also a lower bound of log p(x) as can be shown using Jensen's inequality. When an estimator takes a single sample from q and R = p(x, z)/q(z), the MCO can be identified as ELBO in variational inference [Mnih and Rezende, 2016]. When an estimator averages importance weights from K samples, RK = K-1 ∑Ki=1 p(zi , x)/q(zi ), it yields an importance weighted ELBO (IW-ELBO) [Burda et al., 2016; Domke and Sheldon, 2018]. This bound is proven to be tighter with increasing K and asymptotically converges to log p(x), as K → ∞.

2.2 Sequential Monte Carlo

For a sequential observation x1:T with latent trajectory z1:T , the generative process can be factorized as p(z1:T , x1:T ) = p(z1)p(x1|z1) ∏Tt=2 p(zt|z1:t-1, x1:t-1)p(xt|z1:t, x1:t-1). Inferring latent trajectory, p(z1:T |x1:T ), is of importance for marginalization and to learn generative models, however, usually intractable. Sequential Monte Carlo (SMC) approximates a target distribution, specifically p(z1:T |x1:T ), using a set of weighted sample trajectories { ˜wiT , ˆzi1:T }i=1:K. It combines Sequential Importance Sampling (SIS) with resampling, consisting of four main steps:

Sample K particles ˆzit from proposal q(zt|¯zi1:t-1 , x1:t) with previously resampled trajectories ¯zi1:t-1 ;

Resample from { ˜wi t , ˆzi1:t } to obtain equally-weighted particles ¯zi1:t = ˆzAit-1 1:t , with ancestral indices Ait-1 .

This iteration continues until time T. Besides being an approximate inference, SMC also gives an unbiased estimate of the marginal likelihood p(x1:T ) by the importance weights:

The variance of this estimate, accessed by the so-called Effective Sample Size (ESS) for sample efficiency, is largely dependent on the proposal distributions q. We refer to [Doucet and Johansen, 2009] for a more in-depth discussion.

2.3 Variational Filtering Objectives

To learn a generative model for time series data, various ELBO-like surrogate objectives have been proposed using different factorizations of generative models and approximations q(z1:T |x1:T ). IW-ELBO can be extended to sequences by changing from Importance Sampling (IS) to SIS estimator RK = K-1 ∑Ki=1 p(zi1:T , x1:T )/q(zi1:T ). However, such an estimator suffers from exponential growth of variance with the length of sequences.To improve this, AESMC, FIVO and VSMC propose three closely related MCOs, exploiting the SMC estimators (2):

It is found that the learning of generative models via the objective suffers high variance in gradient estimation, since importance weight wi t does not allow for smooth gradient computation. We show that simply ignoring some high variance term in the gradient estimate as the suggested solution in previous methods, introduces an extra bias and leads to nonoptimality of proposal and generative parameters at convergence. To tackle these problems and extend variational filtering objectives, we propose MCFOs, and discuss their important properties in the following sections.

3 Monte Carlo Filtering Objectives

Instead of constructing variational lower bound from (2), we leverage the decomposition of joint marginal log-likelihood:

Nonetheless, log p(xt|x1:t-1) is usually intractable, which makes learning a generative model by maximizing (4) only possible in some limited cases. Instead, we define LKt , an MCO for each log p(xt|x1:t-1) with K samples:

specifically LK1 for log p(x1),

where q(zt|z1:t-1, x1:t) and q(z1|x1) are the proposal distributions, RK t and RK 1 are the unbiased estimators of p(xt|x1:t-1) and p(x1) with K samples; see [Chen et al., 2021, Appendix B.1] for derivations. Summing up the series of MCOs , a Monte Carlo filtering objective (MCFO), LMCFO:

is defined as the lower bound of log p(x1:T ). To avoid notation clutter, we leave out arguments when the context permits.

Considering the filtering problem for which future observations have no impact on the current posterior, replacing p(z1:K 1:t-1 |x1:t-1) in QKt with K sample approximations ˆ p(z1:K 1:t-1 |x1:t-1) = ∑Ki=1 ˜wi t-1 δ(zi1:t-1 - ˆzi1:t-1 ) retrieves the definition of ELBOSMC in (3). The objective can be considered as an estimate of MCFOs by SMC and is consistent to MCFOs with the asymptotic bias of O(1/K); see [Chen et al., 2021, Appendix B.2] for details. MCFOs can freely choose other estimator alternatives such as PIMH [Andrieu et al., 2010] and unbiasedMCMCwith couplings [Jacob et al., 2017] to further improve sampling efficiency of SMC.

3.1 Properties of MCFOs

Except for the general properties inherited fromMCOs such as bound and consistency, the convergence of MCFOs is monotonic like IW-ELBO, but unique to earlier filtering objectives. Additionally, the asymptotic bias of MCFOs can be shown to relate to the total variances of estimators.

Proposition 1. (Properties of MCFOs). Let LKMCFO be an MCFO of log p(x1:T ) by a series of unbiased estimators Rt of p(xt|x1:t-1) using K samples. Then,

1. (Bound) log p(x1:T ) ≥ LKMCFO .
2. (Monotonic convergence) LK+1 MCFO ≥ LKMCFO ≥ . . . ≥ L1MCFO .
3. (Consistency) If p(z1, x1)/q(z1|x1) and p(z1:t, x1:t)/(p(z1:t-1, x1:t-1)q(zt|z1:t-1, x1:t)) for all t ∈ [2, T] are bounded, then LKMCFO → log p(x1:T ) as K → ∞.
4. (Asymptotic Bias) For a large K, the bias of bound is related to the variance of estimator Rt, V[Rt],

Proof. See [Chen et al., 2021, Appendix B.3].

Although increasing the number of samples K leads to a tighter MCFO, a large K is infeasible in terms of computational and memory. It has also been shown that larger K may deteriorate to learn proposals [Rainforth et al., 2018]. An appropriate K is a critical hyperparameters that affects learning both generative and proposal models. On the other hand, asymptotic bias suggests another way for a tighter bound, i.e. using less variant estimators Rt, which has been overlooked in recent literature. It explains why the bounds defined by SMC are tighter than IW-ELBO by SIS. Thus, the proposal model that permits less variant Rt, either designed or learned, is another key instrument.

3.2 Optimal Importance Proposals

Considering proposals q as an argument of MCFOs, we can derive the optimal proposals when they maximize the bound.

Proposition 2. (Optimal importance proposals q∗ for an MCFO). The bound is maximized and exact to log p(x1:T ) when the importance proposals are

Proof. See [Chen et al., 2021, Appendix B.4].

The optimal importance proposals always propagate samples from the previous filtering posterior p(z1:t-1|x1:t-1) to the new target p(z1:t|x1:t), thus leads MCFOs to be exact. For SSMs that assume Markovian latent variables and conditional independent observations, the optimal importance proposals are further simplified to p(zt|zt-1, xt) [Doucet et al., 2000, Proposition 2]. For common intractable problems, though the filtering posteriors and optimal proposals are not accessible, we can learn a parametric adaptive importance proposal model jointly with generative models by optimizing MCFOs.

3.3 Learning Generative and Proposal Models

To illustrate the learning of a flexible importance proposal and/or a generative model, we explicitly parameterize generative model pθ and proposal model qφ by θ and φ respectively, and optimize them by gradient-based algorithms.

Earlier methods suffer from high variance in gradient estimate due to the second term in (6) in Table 1. This is mainly caused by 1) large magnitudes of log ˆ p(x1:T ), especially at the beginning of training; and 2) high variance in the gradient for non-smooth categorical distribution of discrete ancestral indices Ait-1 in SMC. FIVO and VSMC propose to ignore the high variance term to stabilize and accelerate convergence. However, it comes at the cost of an induced bias that cannot be eliminated by increasing the number of samplesand deteriorates the convergence to optimum [Roeder et al., 2017].

MCFOs can circumvent the issue for ▽φLKMCFO by reparameterization trick [Kingma and Welling, 2014] without an extra bias. Assuming the proposal distribution qφ is reparameterizable, ▽φLKt is estimated less variantly by:

where {ˆzi1:t }i=1:K are K sample trajectories, e.g. from SMC, and can be specified with ancestral indices Ait-1 when resampling applies, fθ,φ(·) is the logarithm average function log 1K ∑Ki=1 ( ·· ), and ϵi is a sample from a base distribution p(ϵ). The same trick cannot directly apply to ▽θLKt , because of the existence of θ in the expectation. Instead, we use the score function of p(xt|x1:t-1) to estimate ▽θLKt :

where ˜wi t are the normalized importance weights of ˆzi1:t ; see [Chen et al., 2021, Appendix B.5, B.6] for detailed derivation of (7) and (8). Essentially, the score function estimate is equivalent as dropping the high variance term in (6) for ▽θ.

NASMC [Gu et al., 2015] is closely related to MCFOs with SMC implementation in terms of ▽θ, and RWS [Bornschein and Bengio, 2015] is a special case of NASMC that replaces SMC by SIS. These two methods, however, construct a different surrogate objectives for optimizing φ. While NASMC and RWS minimize the approximated inclusive KL-divergence, KL( ˆ pθ(z1:t|x1:t)||qφ(z1:t|x1:t)), MCFOs minimize the disclusive KL-divergence, KL(QKt (z1:K 1:t |x1:t)||pθ(z1:K 1:t |x1:t)), on the extended latent space as the dual problem of maximizing surrogate objectives. When the family of proposals is adequately flexible to include simple true posteriors, both NASMC and MCFOs converge to the same optimum. To fit a potentially complex multi-modal posterior, the simple proposal learned by NASMC and RWS tends to have undesired low density everywhere in order to cover all modalities, thus impairs the sample efficiency of estimators and restricts the learning of generative models. For MCFOs, QKt (z1:K 1:t |x1:t) is naturally a mixture of simple proposal distributions qφ with importance weights ˜wi t-1 , which remains flexible to fit multimodal posteriors, while sustaining sample efficiency.

Furthermore, when the latent and observation variables are assumed to be finite-order Markovian, both gradients of MCFOs can be updated incrementally which makes them well suited for arbitrarily long sequences and data streams.

4 Experiments

We seek to evaluate our method in experiments by answering: 1) what is the side-effect of ignoring the high variance term as proposed in earlier methods; 2) do the gradient estimates of MCFOs reduce the variance without the cost of additional bias; 3) how does the number of samples affect the learning of generative models and how sample efficient are the learned proposal models? We evaluate two instances of MCFOs, MCFO-SMC and MCFO-PIMH, using SMC and PIMH respectively to learn generative and proposal models on LGSSM, non-Gaussian, nonlinear, high dimensional SSMs of video sequences, and non-Markovian polyphonic music sequences 2 . We restrict the form of posteriors to qφ(zt|zt-1, xt) for SSM cases to encode history into low dimensional representations, while using VRNN to accommodate long temporal dependencies for non-Markovian data. To be noted, all models are amortized over all time instances.

4.1 Gradient Estimation

Following [Rainforth et al., 2018; Le et al., 2018], we carry out experiments to examine gradient estimators on a tractable LGSSM, defined by θ1 and θ2, and importance proposal qφ(zt|zt-1, xt), parameterized by φ:

The gradient estimates are computed by backwards automatic differentiationon the objectives defined by IWAE, AESMC and MCFO-SMC w.r.t. θ and φ using sequences generated by the LGSSM. AESMC is implemented ignoring the high variance term in (6) as suggested. Figure 1 shows 1000 gradient samples by all three methods under different numbers of samples, K, when both θ and φ are at optima.

For ▽φ, the induced bias of AESMC is distinct and does not disappear with increasing K, which makes parameters unable to converge to the exact optimum. Although increasing K decreases the variance for all methods, it is specially detrimental to AESMC for which gradient estimates are barely close to true gradients [Rainforth et al., 2018], but beneficial to IWAE and MCFO. For ▽θ, MCFO and AESMC have similar estimates close to the analytical gradients, while IWAE estimates are substantially deviated due to the high variance of SIS estimators. Training by MCFOs is expected to have a similar performance but with less computations, compared to the alternating strategy to optimize IWAE objective for φ and AESMC for θ [Le et al., 2018]. See [Chen et al., 2021, Appendix D.1] for gradient estimates at other locations.

4.2 Learning and Inference on LGSSMs

To examine the learning of generative and proposal parameters, we generate 5000 trajectories by LGSSM in (9) with θ1 = 0.9, θ2 = 1.2, of which 4000 are for training and rest for testing. Figure 2 illustrates 5 benchmarking methods including bootstrap filtering [S¨arkk¨a, 2013], IWAE, AESMC, NASMC and MCFO-SMC, using the same initialization and optimizer; see [Chen et al., 2021, Appendix D.2] for experiment setups. Note that bootstrap uses prior as proposal, thus no proposal parameter needs to learn. To evaluate the performance of learned proposal models for sample efficiency and tightness of lower bound, we report the variance of estimators by ESS = (∑i ( ˜wi t )2 )-1 , and average over test sequences.

2 The implementation of our algorithms and experiments are available at https://github.com/ssajj1212/MCFO.

MCFO-SMC and NASMC learn more sample efficient proposal models than bootstrap, AESMC and IWAE, and converge to the exact analytic optimum. Although AESMC does not differ significantly in terms of NLLs from MCFO and NASMC, the bias in gradient estimates shown previously, causes it slow to converge and cannot converge to the exact optimum. MCFO learns both generative and proposal models faster than AESMC. For this simple case, NASMC converges faster than MCFOs, since fitting a Gaussian proposal with NASMC to the uni-modal Gaussian posterior of LGSSM is easier than fitting a mixture of Gaussian proposals with MCFO. However, NASMC may fail to learn multimodal posteriors for general intractable problems, as shown in the next section. Furthermore, increasing the number of samples and replacing SMC by PIMH with different number of sweeps only slightly improve the learning by MCFOs, see more results in [Chen et al., 2021, Appendix D.2].

4.3 Video Sequences

To assess MCFOs in more general cases, we simulate 1000 video sequences of a single pendulum system in gym, out of which 500 are used for testing. Each sequence contains 20 32 × 32 pixel grayscale images representing factorized Bernoulli distributions of high-dimensional observations; see examples in Figure 3. The transition and proposal distributions, pθ(zt|zt-1) and qφ(zt|xt, zt-1), are parameteric Gaussian MLPs, while observation models, pθ(xt|zt), are parameteric Bernoulli MLPs. The latent dimension is set to 3, and optimizers and model definitions are the same for all methods; see [Chen et al., 2021, Appendix E].

Figure 3 shows the commonly used one-step prediction errors in observations and ESSs on the test set, evaluated by SMC with 1000 particles on the models trained by AESMC, MCFO-SMC and MCFO-PIMH with K = 10, 20, 50, 100. Additionally, Table 2 reports both metrics averaged over the last 1000 iterations of trainings. Note that NASMC fails to converge in this task regardless of K. Compared to AESMC, both MCFO-SMC and MCFO-PIMH, show quicker convergences, lower prediction errors and higher ESSs that indicate more sample efficient proposal models, especially at smaller K. Furthermore, MCFOs implicitly regularize to learn simpler generative models, see [Chen et al., 2021, Appendix E]. Although MCFO-PIMH converges faster than MCFO-SMC and AESMC because of better Monte Carlo approximations, the improvement at convergence is marginally small considering that it requires more computations for each sweep in PIMH. Increasing K does improve generative model learning, but slightly impairs the sample efficiency of proposal models. No statistically significant gain is observed to increase K over 200. Therefore, the sweet spot of K needs to balance the performance of generation and inference.

4.4 Polyphonic Music

To demonstrate the performance of MCFOs for nonMarkovian high dimensional data with complex temporal dependencies, we train VRNN models with MCFO-SMC and MCFO-PIMH on four polyphonic music datasets [Boulanger et al., 2012]. We preprocess all musical notes to 88dimensional binary sequences and configure generative and proposal models as [Maddison et al., 2017]; see [Chen et al., 2021, Appendix F] for experiment details. Table 3 reports the estimated NLLs using 500 samples, as with the other benchmarked methods, on the models trained by MCFO-SMC and MCFO-PIMH with 10, 20 samples. As can be seen for all four datasets, MCFO-SMC and MCFO-PIMH are either superior or comparable to the other state-of-the-art algorithms.

5 Conclusion

We introduce Monte Carlo filtering objectives (MCFOs), a new family of variational filtering objectives to learn generative and importance proposal models for time series. MCFOs extend the choices of estimators to use and accommodate some theoretical properties for tighter objectives. We show empirically that MCFOs and the proposed gradient estimators facilitate to learn parametric generative and proposal models more stably and efficiently, compared to state-of-the-art methods in various tasks. In future works, we would like to explore the equivalence of MCFOs for smoothing problems and explore tractable MCFOs by flow-based methods.

Acknowledgements

This work is supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP).