Year: 2018

Abstract:
In order to integrate uncertainty estimates into deep time-series modelling, Kalman Filters (KFs) (Kalman et al., 1960) have been integrated with deep learning models. Yet, such approaches typically rely on approximate inference techniques such as variational inference which makes learning more complex and often less scalable due to approximation errors. We propose a new deep approach to Kalman filtering which can be learned directly in an end-to-end manner using backpropagation without additional approximations. Our approach uses a highdimensional factorized latent state representation for which the Kalman updates simplify to scalar operations and thus avoids hard to backpropagate, computationally heavy and potentially unstable matrix inversions. Moreover, we use locally linear dynamic models to efficiently propagate the latent state to the next time step. While our locally linear modelling and factorization assumptions are in general not true for the original low-dimensional state space of the system, the network finds a high-dimensional latent space where these assumptions hold to perform efficient inference. This state representation is learned jointly with the transition and noise models. The resulting network architecture, which we call Recurrent Kalman Network (RKN), can be used for any time-series data, similar to a LSTM (Hochreiter and Schmidhuber, 1997) but uses an explicit representation of uncertainty. As shown by our experiments, the RKN obtains much more accurate uncertainty estimates than an LSTM or Gated Recurrent Units (GRUs) (Cho et al., 2014) while also showing a slightly improved prediction performance and outperforms various recent generative models on an image imputation task.

heading: 1 INTRODUCTION
text: State-estimation in unstructured environments is a very challenging task as observations or measurements of the environment are often high-dimensional and only provide partial information about the state. Images are a good example: Even for low resolution, the number of pixels can quickly exceed tens or hundreds of thousands and it is impossible to obtain any information about the dynamics, such as velocities, from a single image. Additionally, the observations may be noisy or may not contain useful information for the task at hand. Such noise can for example be introduced by poor illumination or motion blur and occlusions can prevent us from observing some or all relevant aspects of the scene. In addition to state estimation, it is also often desirable to predict future states or observations, for example, in order to assess the consequences of future actions. To this end, an initial estimate of the current state is necessary which again has to be inferred from observations. In such environments we typically also have to deal with a high uncertainties in the state estimates. Being able to model this uncertainty is crucial in many decision making scenarios, e.g., if we need to decide to perform an action now or wait until more information about the scene is available.
Deep learning models have been very successful for time-series modelling in unstructured environments. Classical models such as LSTMs (Hochreiter and Schmidhuber, 1997) or GRUs (Cho et al., 2014) perform well but fail to capture the uncertainty of the state estimate. Recent probabilistic deep learning approaches have used the Kalman filter (KF) as a tool to integrate uncertainty estimates into deep time-series modelling (Haarnoja et al., 2016; Watter et al., 2015; Archer et al., 2015; Fraccaro et al., 2017; Krishnan et al., 2017). These approaches use the KF to perform inference in
a low-dimensional (latent) state space that is typically defined by a deep encoder. However, using KF in such a state space comes with two main limitations. In order to be usable for non-linear dynamics, we have to introduce approximations such as the extended KF (Haarnoja et al., 2016) and variational inference methods (Krishnan et al., 2017; Fraccaro et al., 2017). Moreover, the KF equations require computationally expensive matrix inversions that are hard to scale to high dimensional latent spaces for more complex systems and computationally demanding to fully backpropagate in an end-to-end manner. Most of these methods are implemented as (variational) auto-encoders and are therefore also limited to predicting future observations or imputing missing observations and can not be directly be applied to state estimation.
We introduce the Recurrent Kalman Network, an end-to-end learning approach for Kalman filtering and prediction. While Kalman filtering in the original state space requires approximations due to the non-linear models as well as matrix inversions that are hard to back-propagate and computationally expensive, the RKN uses a learned high-dimensional latent state representation that allows for efficient inference using locally linear transition models and a factorized belief state representation which avoids expensive and numerically problematic matrix inversions. Conceptually, this idea is related to kernel methods which use high-dimensional feature spaces to approximate nonlinear functions with linear models (Gebhardt et al., 2017). However, in difference to kernel feature spaces, our feature space is given by a deep encoder and learned in an end-to-end manner.
The RKN can be used for any time-series data set for which LSTMs and GRUs are currently the state of the art. In contrast to those, the RKN uses an explicit representation of uncertainty which governs the gating between keeping the current information in memory or updating it with the current observation. While the RKN shows a slightly improved performance in terms of state estimation errors, both LSTMs and GRUs struggle with estimating the uncertainty of the prediction while the RKN can provide accurate uncertainty estimates. In relation to existing KF-based approaches, our approach can be used for state estimation as well as for generative tasks such as image imputation. We also show that we outperform state of the art methods on a complex image imputation task.

heading: 1.1 RELATED WORK
text: Using encoders for time-series modelling of high-dimensional data such as images is a common approach. Such encoders can also be easily integrated in well known deep time-series models such as LSTMs (Hochreiter and Schmidhuber, 1997) or GRUs (Cho et al., 2014). These models are very effective but do not provide good uncertainty estimates as shown in our experiments. Pixel to Torques (P2T) (Wahlström et al., 2015) employs an autoencoder to obtain low dimensional latent representations from images together with a transition model. They subsequently use the models to perform control in the latent space. Embed to Control (E2C) (Watter et al., 2015) can be seen as an extension of the previous approach with the difference that a variational autoencoder (Kingma and Welling, 2013) is used. However, both of these approaches are not recurrent and rely on observations which allow inferring the whole state from a single observation. They can therefore not deal with noisy or missing data.
Another family of approaches interprets encoder-decoder models as latent variable models that can be optimized efficiently by variational inference. They derive a corresponding lower bound and optimize it using the stochastic gradient variational Bayes approach (Kingma and Welling, 2013). Black Box Variational Inference (BB-VI) (Archer et al., 2015) proposes a structured Gaussian variational approximation of the posterior, which simplifies the inference step at the cost of maintaining a tri-diagonal covariance matrix of the full state. To circumvent this issue, Structured Inference Networks (SIN) (Krishnan et al., 2017) employ a flexible recurrent neural network to approximate the dynamic state update. Deep Variational Bayes Filters (DVBF) (Karl et al., 2016) integrate general Bayes filters into deep feature spaces while the Kalman Variational Autoencoder (KVAE) (Fraccaro et al., 2017) employs the classical Kalman Filter and allows not only filtering but also smoothing.
Variational Sequential Monte Carlo (VSMC) (Naesseth et al., 2017) uses particle filters instead, however they are only learning the proposal function and are not working in learned latent spaces. Yet, these models can not be directly used for state estimation as they are formulated as generative models of the observations without the notion of the real state of the system. Moreover, the use of variational inference introduces an additional approximation that might affect the performance of the algorithms. The approaches given in (Archer et al., 2015; Fraccaro et al., 2017; Haarnoja et al.,
2016) directly use the Kalman update equations in the latent state, which limits these approaches to rather low dimensional latent states due to the expensive matrix inversions.
The BackpropKF (Haarnoja et al., 2016) applies a CNN to estimate the observable parts of the true state given the observation. Similar to our approach, this CNN additionally outputs a covariance matrix indicating the models certainty about the estimate and allows the subsequent use of an (extended) Kalman filter with known transition model. In contrast, we let our model chose the feature space that is used for the inference such that locally linear models can be learned and the KF computations can be simplified due to our factorization assumptions.
A summary of all the approaches, listing also their basic properties, can be seen in Table 1. We compare the approaches whether they are scaleable to high dimensional latent states, whether they can be
used for state estimation, whether they can provide uncertainty estimates, whether they can handle noise or missing data and whether the objective can be optimized directly or via a lower bound. All probabilistic generative models rely on variational inference which optimizes a lower bound, which potentially affects the performance of the algorithms. The P2T and E2C approaches rely on the Markov assumption and therefore can not deal with noise (or need very large window sizes). Traditional recurrent models (LSTMs, GRUs) can be trained directly by backpropagation through time and therefore typically yield very good performance but are lacking uncertainty estimates (which, however, can be artificially added as in our experiments). Our RKN approach combines the advantages of all methods above as it can be learned by direct optimization without the use of a lower bound and it provides a principled way of representing uncertainty inside the neural network.

heading: 2 FACTORIZED INFERENCE IN DEEP FEATURE SPACES
text: Lifting the original input space to a high-dimensional feature space where linear operations are feasible is a common approach in machine learning, e.g., in kernel regression and SVMs. The Recurrent Kalman Network (RKN) transfers this idea to state estimation and filtering, i.e., we learn a high dimensional deep feature space that allows for efficient inference using the Kalman update equations even for complex systems with high dimensional observations. To achieve this, we assume that the belief state representation can be factorized into independent Gaussian distributions as described in the following sections.

heading: 2.1 LATENT OBSERVATION AND STATE SPACES
text: The RKN encoder learns a mapping to a high-dimensional latent observation space W = Rm. The encoder also outputs a vector of uncertainty estimates σobst , one for each entry of the latent observation wt. Hence, the encoder can be represented by (wt,σobst ) = enc(ot). The latent state space Z = Rn of the RKN is related to the observation space W by the linear latent observation model H = [ Im 0m×(n−m) ] , i.e., w = Hz with w ∈ W and z ∈ Z . Im denotes the m ×m identity matrix and 0m×(n−m) denotes a m× (n−m) matrix filled with zeros. The idea behind this choice is to split the latent state vector zt into two parts, a vector pt for holding information that can directly be extracted from the observations and a vector mt to store information inferred over time, e.g., velocities. We refer to the former as the observation or upper part and the latter as the memory or lower part of the latent state. For an ordinary dynamical system and images as observations the former may correspond to positions while the latter corresponds to velocities.
Clearly, this choice only makes sense for m ≤ n and in this work we assume n = 2m, i.e., for each observation unit pi, we also represent a memory unit mi that stores its velocity information.
For each sequence, we initialize z+0 with an all zeros vector and Σ + 0 with 10 · I. In practice, it is beneficial to normalize wt since the statistics of noisy and noise free images differ considerably.

heading: 2.2 THE TRANSITION MODEL
text: To obtain a locally linear transition model we learnK constant transition matrices A(k) and combine them using state dependent coefficients α(k)(zt), i.e., At = ∑K k=0 α (k)(zt)A (k). A small neural network with softmax output is used to learn α(k). Similar approaches are used in (Fraccaro et al., 2017; Karl et al., 2016).
Using a dense transition matrix in high-dimensional latent spaces is not feasible as it contains too many parameters and causes numerical instabilities and overfitting, as preliminary experiments showed. Therefore, we design each A(k) to consist of four band matrices A(k) = [B
(k) 11 ,B (k) 12 ; B (k) 21 ,B (k) 22 ] with bandwidth b. This choice reduces the number of parameters while
not affecting performance since the network is free to choose the state representation.
We assume the covariance of the transition noise to be diagonal and denote the vector containing the diagonal values by σtrans. The noise is learned and independent of the state. Moreover, it is crucial to correctly initialize the transition matrix. Initially, the transition model should focus on copying the encoder output so that the encoder can learn how to extract good features if observations are available and useful. On the other hand it is crucial that A does not yield an instable system. We choose B(k)11 = B (k) 22 = I and B (k) 12 = −B (k) 21 = 0.2 · I.

heading: 2.3 FACTORIZED COVARIANCE REPRESENTATION
text: Since the RKN learns high-dimensional representations, we can not work with the full state covariance matrices Σ+t and Σ − t . We can also not fully factorize the state covariances by diagonal matrices as this neglects the correlation between the memory and the observation parts. As the memory part is excluded from the observation model H, the Kalman update step would not change the memory nodes nor their uncertainty if we would only use a diagonal covariance matrix Σ+t . Hence, for each observation node pi, we compute the covariance with its corresponding memory node mi. All the other covariances are neglected. This might be a crude approximation for many systems, however, as our network is free to choose its own state representation it can find a representation where such a factorization works well in practice. Thus, we use matrices of the form Σt = [Σut ,Σ s t; Σ s t,Σ l t], where each of Σut ,Σ s t,Σ l t ∈ Rm×m is a diagonal matrix. Again, we denote the vectors containing the diagonal values by σut ,σ l t and σ s t.

heading: 2.4 FACTORIZED INFERENCE IN THE LATENT SPACE
text: Inference in the latent state space can now be implemented, similar to a standard KF, using a prediction and an observation update. Prediction Update. Equivalently to the classical Kalman Filter, the current prior ( z−t ,Σ − t ) is
obtained from the last posterior ( z+t−1,Σ + t−1 ) by
z−t = Atz + t−1 and Σ − t = AtΣ + t−1A T t + I · σtrans. (1)
However, the special structure of the covariances enables us to significantly simplify the equation for the covariance. While being straight forward, the full derivations are rather lengthy, thus, we refer to the supplementary material where the equations are given in Eqs. 7,8 and 9.
Observation Update. Next, the prior is updated using the latent observation (wt,σobst ). Similar to the state, we split the Kalman gain matrix Qt into an upper Q u t and a lower part Q l t. Both Q u t
and Qlt are squared matrices. Due to the simple latent observation model H = [ Im 0m×(n−m) ] and the factorized covariances all off-diagonal entries of Qut and Q l t are zero and we can work with vectors representing the diagonals, i.e., qut and q l t. Those are obtained by
qut = σ u,− t ( σu,−t + σ obs t ) and qlt = σ s,− t ( σu,−t + σ obs t ) , (2)
where denotes an elementwise vector division. With this the update equation for the mean simplifies to
z+t = z − t + [ qut qlt ] [ wt − zu,−t wt − zu,−t ] (3)
where denotes the elementwise vector product. The update equations for the individual covariance parts are given by
σu,+t = (1m − qut ) σ u,− t , σ s,+ t = (1m − qut ) σ s,− t and σ l,+ t = σ l,− t − qlt σ s,− t , (4)
where 1m denotes the m dimensional vector consisting of ones. Again, we refer to the supplementary material for a more detailed derivations.
Besides avoiding the matrix inversion in the Kalman gain computation, the factorization of the covariance matrices reduces the total amount of numbers to store per matrix from n2 to 3m. Additionally, working with σs makes it trivial to ensure that the symmetry and positive definiteness of the state covariance are not affected by numerical issue.

heading: 2.5 LOSS AND TRAINING
text: We consider two different potential output distributions, Gaussian distributions for estimating low dimensional observations and Bernoulli distributions for predicting high dimensional observations/images. Both distributions are computed by decoders that use the current latent state estimate zt as well its uncertainty estimates σ u,+ t ,σ s,+ t ,σ l,+ t .
Inferring states. Let s1:T be the ground truth sequence with dimension Ds, the Gaussian loglikelihood for a single sequence is then computed as
L ( s(1:T ) ) = 1
T T∑ t=1 logN ( st ∣∣∣∣decµ(z+t ), decΣ(σu,+t ,σs,+t ,σl,+t )) , (5) where decµ(·) and decΣ(·) denote the parts of the decoder that are responsible for decoding the latent mean and latent variance respectively.
Inferring images. Let o1:T be images with Do pixels. The Bernoulli log-likelihood for a single sequence is then given by
L ( o(1:T ) ) = 1
T T∑ t=1 Do∑ i=0 o (i) t log ( deco,i ( z+t )) + ( 1− o(i)t ) log ( 1− deco,i ( z+t )) , (6)
where o(i)t is the ith pixel of the tth image. The pixels are in this case represented by grayscale values in the range of [0; 1]. The ith dimension of the decoder is denoted by deco,i ( z+t ) , where we use a sigmoid transfer function as output units for the decoder.
Gradients are computed using (truncated) backpropagation through time (BPTT) (Werbos, 1990) and clipped. We optimize the objective using the Adam (Kingma and Ba, 2014) stochastic gradient descent optimizer with default parameters.

heading: 2.6 THE RECURRENT KALMAN NETWORK
text: The prediction and observation updates results in a new type of recurrent neural network, that we call Recurrent Kalman Network, which allows working in high dimensional state spaces while keeping numerical stability, computational efficiency and (relatively) low memory consumption. Similar to the input gate in LSTMs (Hochreiter and Schmidhuber, 1997) and GRUs (Cho et al., 2014) the Kalman gain can be seen as a gate controlling how much the current observation influences the state. However, this gating explicitly depends on the uncertainty estimates of the latent state and observation and is computed in a principled manner. Using sparse transition models allows working in higher dimensional spaces with considerably less parameters than LSTMs or GRUs. For a fixed bandwidth b and number of basis matrices k, the number of parameters of the RKN scales linear in the state size while it scales quadratically for LSTMs and GRUs. Moreover, the RKN provides a principled method to deal with absent inputs by just omitting the update step and setting the posterior to the prior.

heading: 3 EVALUATION AND EXPERIMENTS
text: A full listing of hyperparameters and data set specifications can be found in the supplementary material1. We compare to LSTM and GRU baselines for which we replaced the RKN transition layer with generic LSTM and GRU layers. Those were given the encoder output as inputs and have an internal state size of 2n. The internal state was split into two equally large parts, the first part was used to compute the mean and the second to compute the variance. We additionally executed most of the following experiments using the root mean squared error to illustrate that our approach is also competitive in prediction accuracy. The RMSE results can be found in the appendix.

heading: 3.1 PENDULUM
text: We evaluated the RKN on a simple simulated pendulum with images of size 24 × 24 pixels as observations. Gaussian transition noise with standard deviation of σ = 0.1 was added to the angular velocity after each step. In the first experiment, we evaluated filtering in the presence of high observation noise. We compare against LSTMs and GRUs as these are the only methods that can also perform state estimation. The amount of noise varies between no noise at all and the whole image consisting of pure noise. Furthermore, the noise is correlated over time, i.e., the model may observe pure noise for several consecutive time steps. Details about the noise sampling process can be found in the appendix. We represent the joint angle θt as a two dimensional vector st = θt = (sin(θt), cos(θt))
T to avoid discontinuities. We compared different instances of our model to evaluate the effects of assuming sparse transition models and factorized state covariances. The results are given in Table 2. The results show that our assumptions do not affect the performance, while we need to learn less parameters and can use much more efficient computations using the factorized representation. Note that for the more complex experiments with a higher dimensional latent state space, we were not able to experiment with full covariance matrices due to lack of memory and massive computation times. Moreover, the RKN outperforms LSTM and GRU in all settings.
In a second experiment we evaluated the image prediction performance and compare against existing variational inference approaches. We randomly removed half of the images from the sequences and tasked the models with imputing those missing frames, i.e., we train the models to predict images instead of the position. We compared our approach to the Kalman Variational Autoencoder
1A link to source code will be added here in the final version.
(KVAE) (Fraccaro et al., 2017), Embed to Control (E2C) (Watter et al., 2015) and Structured Inference Networks (SIN) (Krishnan et al., 2017). The results can be found in Table 3. Again, our RKN outperforms all other models. This is surprising as the variational inference models use much more complex inference methods and in some cases even more information such as in the KVAE smoothing case. Sample sequences can be found in the supplementary material. All hyperparameters are the same as for the previous experiment.

heading: 3.2 MULTIPLE PENDULUMS
text: Dealing with uncertainty in a principled manner becomes even more important if the observation noise affects different parts of the observation in different ways. In such a scenario the model has to infer which parts are currently observable and which parts are not. To obtain a simple experiment with that property, we repeated the pendulum experiments with three colored pendulums in one image. The image was split into four equally sized square parts and the noise was generated individually for each part such that some pendulums may be occluded while others are visible. Exemplary images are shown in the supplementary material. A comparison to LSTM and GRU baselines can be found in Figure 2 and an exemplary trajectory in Figure 3. The RKN again clearly outperforms the competing methods. We also computed the quality of the uncertainty prediction by showing the histograms of the normalized prediction errors. While this histogram has clearly a Gaussian shape for the RKN, it looks like a less regular distribution for the LSTMs.

heading: 3.3 QUAD LINK
text: We repeated the filtering experiment on a system with much more complicated dynamics, a quad link pendulum on images of size 48× 48 pixels. Since the individual links of the quad link may occlude each other different amounts of noise are induced for each link. Two versions of this experiment were evaluated. One without additional noise and one were we added noise generated by the same process used in the pendulum experiments. You can find the results in Table 4.
Furthermore, we repeated the imputation experiment with the quad link. We compared only to the informed KVAE, since it was the only model producing competitive results for the pendulum. Our approach achieved −44.470 ± 0.208 (informed) and −44.584 ± 0.236 (uninformed). The KVAE
σ(j),+
for each entry j of s for all time steps in all
test sequences. This normalized error should follow a Gaussian distribution with unit variance if the prediction is correct. We compare the resulting error histograms with the a unit variance Gaussian. The left histogram shows the RKN, the right one the LSTM. The RKN perfectly fits the normal distribution while the LSTM’s normalized error distribution has several modes. Again we designed the smaller LSTM and GRU to have roughly the same amount of parameters as the RKN.
achieved −52.608± 0.602 for smoothing and −59.0218± 0.580 for filtering . Sample images can be found in the appendix.

heading: 3.4 KITTI DATASET FOR VISUAL ODOMETRY
text: We evaluated the RKN on the KITTI Data set for visual odometry (Geiger et al., 2012). Following (Zhao et al., 2018) we constructed an encoder consisting of FlowNet2 (Ilg et al., 2017), four convolutional and two branches of fully connected layers.
Following the standard KITTI evaluation procedure achieve an transnational error of 4.24% and a rotational error of 0.0404rad /100m . Those result are competitive to other recent results on the KITTI dataset using only monocular images (Zhao et al., 2018; Wang et al., 2018) and demonstrate the applicability of our approach to real world applications.

heading: 4 CONCLUSION
text: In this paper, we introduced the Recurrent Kalman Network that jointly learns high-dimensional representations of the system in a latent space with locally linear transition models and factorized covariances. The update equations in the high-dimensional space are based on the update equations of the classical Kalman filter, however due to the factorization assumptions they simplify to scalar operations that can be performed much faster and with greater numerical stability. Our model outperforms generic LSTMs and GRUs on various state estimation tasks while providing reasonable uncertainty estimates. Additionally, it outperformed several generative models on an image imputation task. Training is straight forward and can be done in an end-to-end fashion.
In future work we want to exploit the principled notion of a variance provided by our approach in scenarios where such a notion is beneficial, e.g. reinforcement learning. Similar to (Fraccaro et al., 2017) we could expand our approach to not just filter but smooth over trajectories in offline postprocessing scenarios which could potentially increase the estimation performance significantly.

heading: A SIMPLIFIED KALMAN FILTER FORMULAS
text: As stated above the simple latent observation model H = [ Im 0m×(n−m) ] , as well as the assumed factorization of the covariance matrices allow us to simplify the Kalman Filter equations.
A.1 NOTATION
In the following derivations we neglect the time indices t and t + 1 for brevity. For any matrix M, M̂ denotes a diagonal matrix with the same diagonal as M, m denotes a vector containing those diagonal elements andM (ij) denotes the entry at row i and column j. Similarly, v(i) denotes the i-th entry of a vector v. The point wise product between two vectors of same length (Hadamat Product) will be denoted by and the point wise division by .
A.2 PREDICTION STEP
Mean: z− = Az+
Covariance: Σ− = AΣ+AT + Σ̂ trans
The computation of the mean can not be further simplified, however, depending on the state size and bandwidth, sparse matrix multiplications may be exploited. For the covariance, let T = AΣ+. Then,
T = AΣ+ = [ B11 B12 B21 B22 ][ Σ̂ u,+ Σ̂ s,+
Σ̂ s,+ Σ̂ l,+
]
=
[ B11Σ̂ u,+ + B12Σ̂ s,+ B11Σ̂ s,+ + B12Σ̂ l,+
B21Σ̂ u,+ + B22Σ̂ s,+ B21Σ̂ s,+ + B22Σ̂ l,+ ] and
Σ− = TAT + Σ̂ trans
=
[ B11Σ̂ u,+ + B12Σ̂ s,+ B11Σ̂ s,+ + B12Σ̂ l,+
B21Σ̂ u,+ + B22Σ̂ s,+ B21Σ̂ s,+ + B22Σ̂ l,+
] [ BT11 B T 21
BT12 B T 22
] + Σ̂ trans
=
[ Σ̂ u,− Σ̂ s,−
Σ̂ s,− Σ̂ l,−
] ,
with Σu,− = ( B11Σ̂ u,+ + B12Σ̂ s,+ ) BT11 + ( B11Σ̂ s,+ + B12Σ̂ l,+ ) BT12 + Σ̂ u,trans
= B11Σ̂ u,+ BT11 + B12Σ̂ s,+ BT11 + B11Σ̂ s,+ BT12 + B12Σ̂ l,+ BT12 + Σ̂ u,trans Σl,− = ( B21Σ̂ u,+ + B22Σ̂ s,+ ) BT21 + ( B21Σ̂ s,+ + B22Σ̂ l,+ ) BT22 + Σ̂ l,trans
= B21Σ̂ u,+ BT21 + B22Σ̂ s,+ BT21 + B21Σ̂ s,+ BT22 + B22Σ̂ l,+ BT22 + Σ̂ l,trans Σs,− = ( B21Σ̂ u,+ + B22Σ̂ s,+ ) BT11 + ( B21Σ̂ s,+ + B22Σ̂ l,+ ) BT12
= B21Σ̂ u,+ BT11 + B22Σ̂ s,+ BT11 + B21Σ̂ s,+ BT12 + B22Σ̂ l,+ BT12
Since we are only interested in the diagonal parts of Σu,−,Σl,− and Σs,− i.e. Σ̂ u,− , Σ̂ l,− and Σ̂ s,−
, we can further simplify these equations by realizing two properties of the terms above. First, for any matrix M,N and a diagonal matrix Σ̂ it holds that(
MΣ̂NT )(ii) = n∑ k=1 A(ik)B(ik)σ(k) = ( NΣ̂MT ) ii .
Hence, we can simplify the equations for the upper and lower part to
Σu,− = B11Σ̂ u,+ BT11 + 2 ·B12Σ̂ s,+ BT11 + B12Σ̂ l,+ BT12 + Σ̂ u,trans ,
Σl,− = B21Σ̂ u,+ BT21 + 2 ·B22Σ̂ s,+ BT21 + B22Σ̂ l,+ BT22 + Σ̂ l,trans .
Second, since we are only interested in the diagonal of the result it is sufficient to compute only the diagonals of the individual parts of the sums which are almost all of the same structure i.e. S = MΣ̂ + NT . Let T = MΣ̂ + , then each element of T can be computed as
T (ij) = n∑ k=1 M (ik)Σ̂(kj) = M (ij)σ(j).
Consequently, the elements of S = TAT can be computed as
S(ij) = n∑ k=1 T (ik)A(kj) = n∑ k=1 M (ik)σkN (jk).
Ultimately, we are not interested in S but only in Ŝ
Ŝ(ii) = n∑ k=1 M (ik)N (ik)σ(k).
Using this we obtain can obtain the entries of σu,−,σl,− and σs,− by
σu,−,(i) = m∑ k=1 ( B (ik) 11 )2 σu,+,(i) + 2 m∑ k=1 B (ik) 11 B (ik) 12 σ s,+,(i) + m∑ k=1 ( B (ik) 12 )2 σl,+,(i) + σu,trans,(i)
(7)
σl,−,(i) = m∑ k=1 ( B (ik) 21 ) σu,+,(i) + 2 m∑ k=1 B (ik) 22 B (ik) 21 σ s,+,(i) + m∑ k=1 ( B (ik) 22 )2 σl,+,(i) + σl,trans,(i)
(8)
σs,−,(i) = m∑ k=1 B (ik) 21 B (ik) 11 σ u,+,(i) + m∑ k=1 B (ik) 22 B (ik) 11 σ s,+,(i)... (9)
... + m∑ k=1 B (ik) 21 B (ik) 12 σ s,+,(i) + m∑ k=1 B (ik) 22 B (ik) 12 σ l,+,(i),
which can be implemented efficiently using elementwise matrix multiplication and sum reduction.
A.3 UPDATE STEP
Kalman Gain Q = Σ−HT ( HΣ−HT + Σobs )−1 Mean z+ = z− + Q ( w −Hz−
) Covariance Σ+ = (I−QH) Σ−
First, note that
Σ−HT =
[ Σ̂ u,−
Σ̂ s,−
] and HΣ−HT + Σ̂ obs = Σ̂ u,− + Σ̂ obs
and thus the computation of the Kalman Gain only involves diagonal matrices. Hence the Kalman
Gain matrix also consists of two diagonal matrices, i.e., Q =
[ Q̂ u
Q̂ l
] whose diagonals can be
computed by
qu = σu,− ( σu,− + σobs ) and ql = σs,− ( σu,− + σobs ) . (10)
Using this result, the mean update can be simplified to
z+ = z− + [ qu ql ] [ w − zu,− w − zu,− ] . (11)
For the covariance we get:[ Σ̂ u,+ Σ̂ s,+
Σ̂ s,+ Σ̂ l,+
] = (In −QH) Σ− = [ Im − Q̂ u 0m×m
−Q̂ l
Im
][ Σ̂ u,− Σ̂ s,−
Σ̂ s,− Σ̂ l,−
]
=
[ ( Im − Q̂ u ) Σ̂ u,− ( Im − Q̂ u ) Σ̂ s,−
−Q̂ l Σ̂ u,− + Σ̂ s,− −Q̂ l Σ̂ s,− + Σ̂ l,−
] .
Hence the diagonals of the individual parts can be computed as
σu,+ = (1m − qu) σu,− (12) σs,+ = (1m − qu) σs,− (13) σl,+ = σl,− − ql σs,−. (14)

heading: B ROOT MEAN SQUARE ERROR RESULTS
text: To evaluate the actual prediction performance of our approach we repeated some experiments using the RMSE as loss function. Other than that and removing the variance output of the decoder no changes were made to the model, hyperparameters and learning procedure. The results can be found in Table 5.
C VISUALIZATION OF IMPUTATION RESULTS
Exemplary results of the data imputation experiments conducted for the Pendulum and Quad Link experiment can be found in Figure 4

heading: D NETWORK ARCHITECTURES AND HYPER PARAMETERS
text: For all experiments Adam (Kingma and Ba, 2014) with default parameters (α = 10−3, β1 = 0.9, β2 = 0.999 and ε = 10−8) was used as an optimizer. The gradients were computed using (truncated) Backpropagation Trough Time (BpTT) (Werbos, 1990). Further in all (transposed) convolutional layers layer normalization (LN) (Ba et al., 2016) was employed to normalize the filter responses. ”Same” padding was used. The elu activation function (Clevert et al., 2015) plus a constant 1 is denoted by (elu + 1) was used to ensure that the variance outputs are positive.
D.1 PENDULUM AND MULTIPLE PENDULUM EXPERIMENTS
Observations Pendulum: Grayscale images of size 24×24 pixels. Multiple Pendulum: RGB images of size 24× 24 pixels. See Figure 5 for examples. Dataset: 1000 Train and 500 Test sequences of length 150. For the filtering experiments noise according to section E was added , for imputation 50% of the images were removed randomly. Encoder: 2 convolution + 1 fully connected + linear output & (elu + 1) output:
• Convolution 1: 12, 5× 5 filter, ReLU, 2× 2 max pool with 2× 2 stride • Convolution 2: 12, 3× 3 filter with 2× 2 stride, ReLU, 2× 2 max pool with 2× 2 stride • Pendulum: Fully Connected 1: 30, ReLU • Multiple Pendulum: Fully Connected 1: 90, ReLU
Transition Model Pendulum: 15 dimensional latent observation, 30 dimensional latent state. Multiple Pendulum: 45 dimensional latent observation, 90 dimensonal latent state. Both: bandwidth: 3, number of basis: 15
• α(zt): No hidden layers - softmax output
Decoder (for s+t ): 1 fully connected + linear output:
• Fully Connected 1: 10, ReLU
Decoder (for o+t ): 1 fully connected + 2 transposed convolution + transposed convolution output:
• Fully Connected 1: 144 ReLU • Transposed Convolution 1: 16, 5× 5 filter with 4× 4 stride, ReLU • Transposed Convolution 2: 12, 3× 3 filter with 2× 2 stride, ReLU • Transposed Convolution Out: Pendulum: 1 Multiple Pendulum: 3, 3 × 3 filter with 1 × 1
stride, Sigmoid
Decoder (for σ+t or σ + t ): 1 fully connected + (elu + 1):
• Fully Connected 1: 10, ReLU
D.2 QUAD LINK
Observations: Grayscale images of size 48x48 pixels. Dataset: 4000 Train and 1000 Test sequences of length 150. For the filtering with additional noise experiments noise according to section D was added, for imputation 50% of the images were removed randomly. Encoder: 2 convolution + 1 fully connected + linear output & (elu + 1) output:
• Convolution 1: 12, 5× 5 filter with 2× 2 stride, ReLU, 2× 2 max pool with 2× 2 stride • Convolution 2: 12, 3× 3 filter with 2× 2 stride, ReLU, 2× 2 max pool with 2× 2 stride • Fully Connected 1: 200 ReLU
Transition Model 100 dimensional latent observation, 200 dimensional latent state, bandwidth: 3, number of basis: 15
• α(zt): No hidden layers - softmax output
Decoder (for s+t ): 1 fully connected + linear output:
• Fully Connected 1: 10, ReLU
Decoder (for o+t ): 1 fully connected + 2 transposed convolution + transposed convolution output:
• Fully Connected 1: 144 ReLU • Transposed Convolution 1: 16, 5× 5 filter with 4× 4 stride, ReLU • Transposed Convolution 2: 12, 3× 3 filter with 4× 4 stride, ReLU • Transposed Convolution Out: 1, 1× 1 stride, Sigmoid
Decoder (for σ+t or σ + t ): 1 fully connected + (elu + 1):
• Fully Connected 1: 10, ReLU
D.3 KITTI
Observation and Data Set: Images from the KITTI (Geiger et al., 2012) dataset for visual odometry. Sequences 00, 01, 02, 08, 09 used for training. Sequences 03, 04, 05, 06, 07, 10 for testing. Encooder: FlowNet2 + 4 Convolutional + 2 Branches of dense Layers. See (Zhao et al., 2018) Transition Model: 100 dimensional latent observations, 200 dimensional latent state, bandwidth: 5, number of basis: 20
• α(zt): No hidden layers - softmax output
Decoder (for s+t ): 2 fully connected + linear output:
• Fully Connected 1: 128, ReLU • Fully Connected 1: 128, ReLU
Decoder (for σ+t or σ + t ): 2 fully connected + (elu + 1):
• Fully Connected 1: 128, ReLU • Fully Connected 1: 128, ReLU

heading: E OBSERVATION NOISE GENERATION PROCESS
text: Let U(x, y) denote the uniform distribution from x to y.To generate the noise for the pendulum task for each sequence a sequence of factors ft of same length was generated. To correlate the factors they were sampled as f0 ∼ U(0, 1) and ft+1 = min(max(0, ft + rt), 1) with rt ∼ U(−0.2, 0.2). Afterwards, for each sequence two thresholds t1 ∼ U(0.0, 0.25) and t2 ∼ U(0.75, 1) were sampled.
All ft < t1 were set to 0, all ft > t2 to 1 and the rest was linearly mapped to the interval [0, 1]. Finally, for each image it an image consisting of pure uniformly distributed noise inoiset was sampled and the observation computed as ot = ft · it + (1− ft) · inoiset .

Review summaries:
This paper proposes a method for inferring the latent state and making predictions based on a sequence of observations. The idea is to map the observation to a latent space where the relation to the latent state is linear, and the dynamics of the latent state are locally linear. Therefore, in this latent space a Kalman filter can be applied to infer the current state and predict the next state, including uncertainty estimates. Finally, the predicted latent state is mapped to a prediction for the observation or some other variable of interest.