Many real-world applications involve multivariate, geo-tagged time series data: at each location, multiple sensors record corresponding measurements. For example, air quality monitoring system records PM2.5, CO, etc. The resulting time-series data often has missing values due to device outages or communication errors. In order to impute the missing values, state-of-the-art methods are built on Recurrent Neural Networks (RNN), which process each time stamp sequentially, prohibiting the direct modeling of the relationship between distant time stamps. Recently, the self-attention mechanism has been proposed for sequence modeling tasks such as machine translation, significantly outperforming RNN because the relationship between each two time stamps can be modeled explicitly. In this paper, we are the first to adapt the self-attention mechanism for multivariate, geo-tagged time series data. In order to jointly capture the self-attention across different dimensions (i.e. time, location and sensor measurements) while keep the size of attention maps reasonable, we propose a novel approach called Cross-Dimensional Self-Attention (CDSA) to process each dimension sequentially, yet in an order-independent manner. On three real-world datasets, including one our newly collected NYC-traffic dataset, extensive experiments demonstrate the superiority of our approach compared to state-of-the-art methods for both imputation and forecasting tasks. 
 Various monitoring applications, such as those for air quality (Zheng et al. (2015) ), health-care (Silva et al. (2012) ) and traffic (Jagadish et al. (2014) ), widely use networked observation stations to record multivariate, geo-tagged time series data. For example, air quality monitoring systems employ a collection of observation stations at different locations; at each location, multiple sensors concurrently record different measurements such as PM2.5 and CO over time. Such time series are important for advanced investigation and also are useful for future forecasting. However, due to unexpected sensor damages or communication errors, missing data is unavoidable. It is very challenging to impute the missing data because of the diversity of the missing patterns: sometimes almost random while sometimes following various characteristics. Traditional data imputation methods usually suffer from imposing strong statistical assumptions. For example, Scharf & Demeure (1991) and Friedman et al. (2001) fit a smooth curve on observations in either time series (Ansley & Kohn (1984) ; Shumway & Stoffer (1982) ) or spatial distribution (Friedman et al. (2001); Stein (2012) ). Deep learning methods (Li et al. (2018) ; Che et al. (2018); Cao et al. (2018) ; Luo et al. (2018a) ) have been proposed to capture temporal relationship based on RNN (Cho et al. (2014b) ; Hochreiter & Schmidhuber (1997) ; Cho et al. (2014a) ). However, due to the constraint of sequential computation over time, the training of RNN cannot be parallelized and thus is usually time-consuming. Moreover, the relationship between each two distant time stamps cannot be directly modeled. Recently, the self-attention mechanism as shown in Fig. 1(b) has been proposed by the seminal work of Transformer (Vaswani et al. (2017) ) to get rid of the limitation of sequential processing, accelerating the training time substantially and improving the performance significantly on seq-to-seq tasks in Natural Language Processing (NLP) because the relevance between each two time stamps is captured explicitly. In this paper, we are the first to adapt the self-attention mechanism to impute missing data in multivariate time series, which cover multiple geo-locations and contain multiple measurements as Figure 1: (a) Illustration of the multivariate, geo-tagged time series imputation task: the input data has three dimensions (i.e. time, location, measurement) with some missing values (indicated by the orange dot); the output is of same shape as the input while the missing values have been imputed (indicated by the red dot). (b) Self-attention mechanism: the Attention Map is first computed using every pair of Query vector and Key vector and then guides the updating of Value vectors via weighted sum to take into account contextual information. (c) Traditional Self-Attention mechanism updates Value vector along the temporal dimension only vs. Cross-Dimensional Self-Attention mechanism updates Value vector according to data across all dimensions. shown in Fig. 1(a) . In order to impute a missing value in such unique multi-dimensional data, it is very useful to look into available data in different dimensions (i.e. time, location and measurement), as shown in Fig. 1(c) , to capture the intra-correlation individually. To this end, we investigate several choices of modeling self-attention across different dimensions. In particular, we propose a novel Cross-Dimensional Self-Attention (CDSA) mechanism to capture the attention crossing all dimension jointly yet in a decomposed manner. In summary, we make the following contributions: (i) We are the first to apply the self-attention mechanism to the multivariate, geo-tagged time series data imputation task, replacing the conventional RNN-based models to speed up training and directly model the relationship between each two data values in the input data. (ii) For such unique time series data of multiple dimensions (i.e. time, location, measurement), we comprehensively study several choices of modeling self-attention crossing different dimensions. Our proposed CDSA mechanism models self-attention crossing all dimensions jointly yet in a dimension-wise decomposed way, preventing the size of attention maps from being too large to be tractable. We show that CDSA is independent with the order of processing each dimension. (iii) We extensively evaluate on two standard benchmarks and our newly collected traffic dataset. Experimental results show that our model outperforms the state-of-the-art models for both data imputation and forecasting tasks. We visualize the learned attention weights which validate the capability of CDSA to capture important cross-dimensional relationships. The effects of different training losses: For the forecasting task in METR-LA, we compare the performance by setting different training loss in Table 5 and we can see the performance with RMSE as loss metric achieves the best performance. Ablation study of different cross-dimensional self-attention manners: We compare the performance for different solutions in CDSA mechanism on the three datasets listed above. 1) The way of attention modeling determines the computational complexity. As shown in Table 1 , since the Independent calculates dimension-specific Value vectors in parallel, the number of variables and FLOPs are larger than those of the Decomposed. As the Joint and the Shared both share the variables for each dimension, the number of variables is small and basically equals with each other. As the Joint builds a huge attention map, its FLOPs is much larger than others. Since the Decomposed draws attention maps like the Independent but shares Value like the Joint, it reduces the computational complexity significantly. 2) As shown in Table 6 -8, we evaluate these methods on three datasets and the Decomposed always achieves the best performance thanks to the better learning ability compared to the Joint and Shared. More discussions can be found in Supp. Study of using the imputed time series for forecasting. On NYC-Traffic of missing rate 50%, we impute missing values in historical data (using statistical methods and our CDSA respectively) and Attention Map Visualization: Fig. 4 shows an PM10 imputation example in location fangshan at t 2 . Since the pattern of PM2.5 around t 2 is similar to that at t 1 , the attention in orange box is high. As we can see that PM2.5 and PM10 are strongly correlated , in order to impute PM10 at t 2 , our model utilizes PM10 at t 1 (green arrow) and PM2.5 at t 1 (blue arrow), which crosses dimensions. More visualization examples can be found in Supp. In this paper, we have proposed a cross-dimensional self-attention mechanism to impute the missing values in multivariate, geo-tagged time series data. We have proposed and investigated three methods to model the cross-dimensional self-attention. Experiments show that our proposed model achieves superior results to the state-of-the-art methods on both imputation and forecasting tasks. Given the encouraging results, in the future we plan to extend our CDSA mechanism from multivariate, geo-tagged time series to the input that has higher dimension and involves multiple data modalities. A MODEL ARCHITECTURE
A novel self-attention mechanism for multivariate, geo-tagged time series imputation. This paper proposes the problem of applying the transformer network to spatiotemporal data in a compuationally efficient way, and investigates ways of implementing 3D attention. This paper empirically studies the effectiveness of transformer models for time series data imputation across dimensions of the input.