Source-linked AI summary
NAOMI: Non-Autoregressive Multiresolution Sequence Imputation
Yukai Liu, Rose Yu, Stephan Zheng, Eric Zhan, Yisong Yue
TL;DR
Long-range sequence imputation is difficult because missing data and autoregressive error compounding limit existing methods. NAOMI uses non-autoregressive multiresolution modeling, recursive coarse-to-fine decoding, and adversarial training, and reports a 60% accuracy improvement across benchmark sequence datasets.
Problem
Existing imputation methods rely on restrictive missingness assumptions or autoregressive decoding that is susceptible to compounding error in long-range sequences.
Method
NAOMI models conditional distributions from history and predicted future, recursively imputing values from coarse to fine resolutions with a non-autoregressive divide-and-conquer strategy.
Results
NAOMI achieves 60% improvement in accuracy across benchmark datasets including traffic time series, billiards, and basketball trajectories.
Takeaways & Limitations
NAOMI can impute long-range spatiotemporal sequences with arbitrary missing patterns using multiresolution modeling and adversarial training.
Abstract
from arXiv · showhide
Missing value imputation is a fundamental problem in spatiotemporal modeling, from motion tracking to the dynamics of physical systems. Deep autoregressive models suffer from error propagation which becomes catastrophic for imputing long-range sequences. In this paper, we take a non-autoregressive approach and propose a novel deep generative model: Non-AutOregressive Multiresolution Imputation (NAOMI) to impute long-range sequences given arbitrary missing patterns. NAOMI exploits the multiresolution structure of spatiotemporal data and decodes recursively from coarse to fine-grained resolutions using a divide-and-conquer strategy. We further enhance our model with adversarial training. When evaluated extensively on benchmark datasets from systems of both deterministic and stochastic dynamics. NAOMI demonstrates significant improvement in imputation accuracy (reducing average prediction error by 60% compared to autoregressive counterparts) and generalization for long range sequences.
1 Introduction
Missing data can destabilize sequence learning, while existing statistical and autoregressive approaches struggle with flexible missing patterns and long-range sequences. NAOMI addresses these challenges with non-autoregressive, multiresolution recursive imputation and adversarial training.
- Motivation: Missing observations can introduce bias into training data and destabilize downstream sequence-learning tasks.The paper highlights motion tracking as one real-world setting where occlusion, crossing trajectories, and camera instability create missing data.
- Motivation: Statistical methods rely on strong missingness assumptions and perform poorly when missing proportions or sequence lengths are high.The cited limitations include weak generalization to unseen data and dependence on assumptions such as missing at random.
- Motivation: Autoregressive imputation is vulnerable to compounding errors, causing existing methods to struggle with long-range sequence dynamics.These models condition on previous time steps and impute sequentially, which can make errors catastrophic over long ranges.
- Approach: NAOMI models conditional distributions using both history and predicted future, exploiting multiresolution structure through recursive divide-and-conquer imputation.The method fills missing values from coarse to fine-grained resolutions rather than conditioning only on previous values.
- Contributions: The model combines non-autoregressive decoding with adversarial training and achieves 60% improvement in accuracy across benchmark sequence datasets.Experiments cover traffic time series, billiards, and basketball trajectories, with arbitrary missing patterns.
2 Related Work
Prior work includes statistical and deep generative imputation, non-autoregressive sequence modeling, adversarial training, and multiresolution generation. NAOMI combines these directions for recursive non-autoregressive sequence imputation.
- Missing Value Imputation: Statistical imputation methods impose strong missing-pattern assumptions, while latent-variable approaches are restricted to certain parametric models.Examples include averaging, regression, MICE, nearest neighbours, and EM-based latent-variable models.
- Non-Autoregressive Modeling: Non-autoregressive models have shown competitive advantages in scalable sequence decoding for natural language processing and speech.Prior examples include parallel feed-forward speech synthesis and latent-fertility or deterministic translation models.
- Generative Adversarial Training: Sequence adversarial methods use imitation or reinforcement learning to address sequential dependencies that whole-sequence discriminators may overlook.The related work notes that whole-sequence discrimination can suffer from mode collapse.
- Multiresolution Generation: Existing multiresolution generative models primarily capture spatial structure or assume additive resolutions, unlike NAOMI's recursive spatiotemporal generation.NAOMI is distinguished from image-oriented multiresolution models and hierarchical sequence models.
3 Non-Autoregressive Multiresolution Sequence Imputation
NAOMI replaces sequential autoregressive imputation with a non-autoregressive, multiresolution decoder that uses forward and backward context to fill missing sequence values recursively. It combines this architecture with differentiable adversarial training and maintains O(T) total runtime.
- Motivation: Autoregressive imputation compounds errors over long sequences, especially when it cannot use known future observations to constrain missing values.This motivates NAOMI's non-autoregressive design.
- Architecture: NAOMI uses a forward-backward encoder to map incomplete observations and masking information into forward and backward hidden representations.The hidden states encode history and future context for decoding.
- Architecture: The multiresolution decoder imputes recursively from coarse to fine resolutions by selecting known pivots, filling near their midpoint, and reusing the new value at finer resolutions.For a length-five sequence, it predicts x3 from x1 and x5, then imputes x2 and x4.
- Efficient decoding: NAOMI updates hidden states after each imputation and reuses earlier computations, updating forward states once and backward states at most twice.This update strategy supports recursive decoding without recomputing all hidden states.
- Efficiency: NAOMI has O(T) total runtime and O(T) memory usage, while its runtime scales logarithmically with sequence length through the decoder resolution parameter.The decoder parameter R is selected so 2^R is close to the common missing-interval size.
- Learning objective: Training uses a general loss for deterministic dynamics and a discriminator-based adversarial objective for stochastic dynamics, with a fully differentiable generator enabled by reparameterization.The adversarial formulation follows generative adversarial imitation learning while avoiding direct sampling during optimization.
4 Experiments
Experiments evaluate NAOMI on traffic, billiards, and basketball sequence imputation under diverse missing-value patterns. Across these settings, NAOMI generally outperforms autoregressive and single-resolution baselines while preserving multiresolution or realistic dynamics.
- Experimental setup: Experiments cover traffic time series, billiards trajectories, and basketball player movements, with comparisons against interpolation, nearest-neighbor, and autoregressive GAN baselines.The traffic dataset contains multivariate sequences with 963 sensor dimensions and 122 to 140 missing values per sequence.
- Traffic time series: 23% lower L2 loss than autoregressive baselines is achieved by NAOMI on traffic time series imputation.KNN also performs reasonably because repeated daily traffic patterns make similar training sequences useful for imputation.
- Traffic time series: NAOMI captures multiscale traffic fluctuations, whereas SingleRes learns mainly smoothed or averaged behavior and frequently deviates from ground truth.The visualization compares predictions from NAOMI and SingleRes against observed steps and ground-truth curves.
- Robustness and basketball movement: NAOMI remains better than SingleRes across all billiards metrics as missing proportions increase, although both models degrade drastically with larger gaps.For basketball, NAOMI outperforms baselines in almost all domain-specific metrics and produces trajectories with realistic velocities and speeds.
- Robustness and basketball movement: In basketball imputation, performance and variance generally degrade with more missing values, but performance can improve beyond a certain missing proportion.This reflects a trade-off between information from observations and constraints imposed on generative model outputs; fewer observations can permit more flexible distributions.
- Forward prediction: NAOMI also supports forward prediction and learns reflection dynamics better than other baselines in billiards, producing straighter lines than autoregressive models.Forward prediction is treated as imputation with only a leading observed sequence and no known future observations.
5 Conclusion
NAOMI imputes missing values in long-range spatiotemporal sequences by recursively decoding from coarse to fine resolutions with a non-autoregressive model. The paper also identifies incomplete training sequences and the trade-off between partial observations and external constraints as directions for future work.
- NAOMI is a deep generative model for imputing missing data in long-range spatiotemporal sequences.
- NAOMI recursively predicts missing values from coarse to fine-grained resolutions using multiresolution modeling and adversarial training.
- Future work will investigate inferring the underlying distribution when complete training sequences are unavailable.
- The trade-off between partial observations and external constraints remains another direction for deep generative imputation models.