Abstract
Missing data in time series is a pervasive challenge across domains like IoT, computer vision, and healthcare. Traditional approaches relying on Recurrent Neural Networks (RNNs) or Neural Ordinary Differential Equations (NODEs) often suffer from error compounding due to their sequential nature. We present NRTSI (Non-Recurrent Time Series Imputation), a novel framework that treats time series as unordered sets of (time, value) tuples. By employing a hierarchical Transformer-based architecture, NRTSI avoids sequential dependencies, handles irregularly sampled data naturally, and achieves state-of-the-art performance across diverse benchmarks.
Introduction
Real-world time series data frequently contain gaps due to sensor malfunctions or intermittent observations. Imputing these missing values is critical for downstream analysis. Conventional models typically process data sequentially, where the imputation of a point $x_t$ depends on previously imputed values. This leads to "error compounding," where small initial errors propagate and amplify over time. Furthermore, standard recurrent models struggle with irregular sampling intervals. While NODEs address timing irregularities, they remain fundamentally recurrent and computationally intensive.
NRTSI shifts this paradigm by viewing a time series not as a sequence, but as a permutation-equivariant set $S = \{(t_i, x_i)\}$. This perspective allows the model to leverage global context from both the past and future simultaneously, effectively eliminating the sequential error trap.
Methodology
The core of NRTSI is a non-recurrent architecture built upon the Transformer encoder. By utilizing multi-head self-attention, the model captures complex interactions between observed and missing data points without being constrained by temporal order.
Hierarchical Imputation Strategy
NRTSI employs a "divide and conquer" approach. It first imputes points located in the largest missing gaps (coarse resolution). These newly imputed points then serve as "anchors" to guide the imputation of finer details in subsequent stages. This hierarchical process ensures structural consistency across long horizons.
Time Encoding and Parallelism
To maintain temporal awareness within a set-based framework, NRTSI uses sinusoidal time encodings. The authors provide mathematical proof that absolute time encodings allow the model to represent relative temporal distances through linear transformations. A significant advantage of this non-recurrent design is parallelism: NRTSI can impute multiple missing points at the same hierarchy level concurrently, leading to faster inference compared to sequential models.
Experiments and Results
NRTSI was evaluated on a wide range of datasets, including Billiards Ball Trajectories, PEMS-SF Traffic data, MuJoCo physics simulations, and stochastic Football Player Trajectories.
Quantitative Performance
NRTSI consistently outperformed established baselines such as NAOMI, Latent-ODE, and BRITS. On the Billiards dataset, it achieved a 64% reduction in L2 loss compared to NAOMI. In the PEMS-SF Traffic benchmark, NRTSI demonstrated superior accuracy, significantly reducing L2 loss compared to both recurrent and non-recurrent competitors.
Robustness and Speed
The model proved highly robust in "partially observed" scenarios, outperforming competitors across various missingness rates (10% to 80%). Despite its larger parameter count (84M), NRTSI's parallel nature makes it faster during inference than sequential models like NAOMI.
Key Insights
- Sets > Sequences: Treating time series as sets allows the attention mechanism to look globally without being constrained by a specific direction.
- Anchor Points: Starting imputation with the largest gaps provides critical structural information for the rest of the series.
- Regularization Nuances: Standard Transformer tricks like Layer Normalization and Dropout were found to hurt imputation performance and were removed for NRTSI.
Conclusion
NRTSI represents a significant advancement in time series imputation by moving away from recurrent dependencies. While the $O(L^2)$ complexity of self-attention remains a challenge for very long sequences, the hierarchical approach and parallel execution offer a scalable and highly accurate solution for irregularly sampled data. Future work will explore more efficient attention mechanisms and relative positional embeddings to further enhance performance.
Summary updated