Title: CROSS-DIMENSIONAL SELF-ATTENTION FOR MULTI-VARIATE, GEO-TAGGED TIME SERIES IMPUTATION

Abstract: 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 NYCtraffic dataset, extensive experiments demonstrate the superiority of our approach compared to state-of-the-art methods for both imputation and forecasting tasks.

1. INTRODUCTION:

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. 2012)) to model spatial-temporal relationship. Luo et al. (2018a) built GRUI by incorporating RNN into a Generative Adversarial Network (GAN). Nevertheless, the spatiotemporal and measurements correlation are mixed and indistinguishable. so that the mediate back propagation from loss of available observation can contribute to the missing value updating. Nevertheless, these RNN-based models fundamentally suffer from the constraint of sequential processing, which leads to long training time and prohibits the direct modeling of the relationship between two distant data values.

2. RELATED WORK:

Self-attention. Recently, Vaswani et al. (2017) introduced the Transformer framework which relies on self-attention, learning the association between each two words in a sentence. Then self-attention has been widely applied in seq-to-seq tasks such as machine translation, image generation (Yang et al. (2016) ; Zhang et al. (2018a) ) and graph-structured data (Veličković et al. (2017) ). In this paper, we are the first to apply self-attention for multi-dimensional data imputation and specifically we investigate several choices of modeling self-attention crossing different data dimensions.

3. APPROACH:

In Sec. 3.1, we first review the conventional self-attention mechanism in NLP. In Sec. 3.2, we propose three methods for computing attention map cross different dimension. In Sec. 3.3 and 3.4, we present details of using CDSA for missing data imputation.

3.1. CONVENTIONAL SELF-ATTENTION:

As shown in Fig. 1 (b), for language translation task in NLP, given an input sentence, each word x i is mapped into a Query vector q i of d-dim, a Key vector k i of d-dim, and a Value vector v i of v-dim. The attention from word x j to word x i is effectively the scaled dot-product of q i and k j after Softmax, which is defined as A(i, j) = exp(S(i, j)) T j=1 exp(S(q, j))

-1 where Then, v i is updated to v i as a weighted sum of all the Value vectors, defined as v i = T j=1 A(i, j)v j , after which each v i is mapped to the layer output x i of the same size as x i . In order to adapt the self-attention from NLP to our multivariate, geo-tagged time series data, a straightforward way is to view all data in a time stamp as one word embedding and model the self-attention over time.

3.2. CROSS-DIMENSIONAL SELF-ATTENTION:

In order to model Cross-Dimensional Self-Attention (CDSA), in this section we propose three solutions: (1) model attention within each dimension independently and perform late fusion; (2) model attention crossing all dimension jointly; (3) model attention crossing all dimension in a joint yet decomposed manner. We assume the input X ∈ R T ×L×M has three dimensions corresponding time, location, measurement. X can be reshaped into 2-D matrices (i.e. X T ∈ R T ×LM , X L ∈ R L×M T , X M ∈ R M ×T L ) or an 1-D vector (i.e. X ∈ R T LM ×1 ). Similarly, this subscript may be applied on the Query, Key and Value, e.g.,

Q ∈ R T ×L×M ×d , Q L ∈ R L×M T d and Q ∈ R T LM ×d .

3.2.1. INDEPENDENT:

As shown in Fig. 2 (a), the input X is reshaped into three input matrices X T , X L and X M . Three streams of self-attention layers are built to process each input matrix in parallel. Such as the first layer in stream on X L , each vector X L (l, :) of M T -dim is viewed as a word vector in NLP. Following the steps in Sec. 3.1, X L (l, :) is mapped to Q L (l, :) and K L (l, :) of d L -dim, as well as V L (l, :) of v L -dim. The output of every stream's last layer are fused through element-wise addition, X = α T X T + α L X L + α M X M , where the weights α T , α L and α M are trainable parameters. Besides, the hyper-parameters for each stream such as the number of layers, are set separately.

3.2.2. JOINT:

As shown in Fig. 2 (b), the three-dimensional input X is reshaped as to X. Each unit X(p) is mapped to Q(p, :) and K(p, :) of d-dim as well as V (p, :) of v-dim, where p = p(t, l, m) denotes the index mapping from the 3-D cube to the vector form. In this way, an attention map of dimension T LM × T LM is built to directly model the cross-dimensional interconnection.

3.2.3. DECOMPOSED:

The Independent manner sets multiple attention sub-layers in each stream to model the dimensionspecific attention but fail in modeling cross-dimensional dependency. In contrast, the Joint manner learns the cross-dimensional relationship between units directly but results in huge computation workload. To capture both the dimension-specific and cross-dimensional attention in a distinguishable way, we propose a novel Decomposed manner.

As shown in Fig. 2(c ), the input X is reshaped as input matrices X T , X L , X M and X. Each unit X(p) is mapped to vector V (p, :) of v-dim as in the Joint while X T , X L and X M are used for building attention map A T , A L ,A M individually as in the Independent. The attention maps are applied on Value vector in order as,

V = AV = A M V S,2 = A M A L V S,1 = A M A L A T V .

(1)

The attention map with is reshaped from the original attention map and consistent with the calculation in (1), e.g., A T ∈ R T LM ×T LM is reshaped from A T ∈ R T ×T . More specifically,

EQUATION

where ⊗ denotes tensor product and I is the Identity matrix where the subscript indicates the size, e.g., I T ∈ R T ×T . Although the three reshaped attention maps are applied with a certain order, according to (2), we show that each unit in A is effectively calculated as

EQUATION

where p 0 = p(t 0 , l 0 , m 0 ), p 1 = p(t 1 , l 1 , m 1 ). Following the associativity of tensor product, we demonstrate

EQUATION

) where σ = σ(T,L,M) denotes the arbitrary arrangement of sequence (T,L,M), e.g., σ =(L,T,M) and σ(T) = L. Effectively, the arrangement σ is the order of attention maps to update V . As (3)-(4) shows that the weight in A is decomposed as the product of weights in three dimension-specific attention maps, the output and gradient back propagation are order-independent. Furthermore, we show in Supp. B that the cross-dimensional attention map has the following property:

T LM p1=1 A(p 0 , p 1 ) = T t1=1 L l1=1 M m1=1

A T (t 0 , t 1 )A L (l 0 , l 1 )A M (m 0 , m 1 ) = 1.

(5) In summary, the Independent builds attention stream for each dimension while the Joint directly model the attention map among all the units. Our proposed CDSA is based on the Decomposed, which forms a cross-dimensional attention map, out of three dimension-specific maps. As an alternative of the Decomposed, the Shared maps unit X(p) to Q(p, :) and K(p, :) of d-dim and calculates all three dimension-specific attention map, e.g.,

A L = Softmax(Q L K L / √ M T d).

As shown in Table 1 , by using Tensorflow profile and fixing the hyper-parameters with detailed explanations in Supp., the Decomposed significantly decreases the FLoating point OPerations (FLOPs) compared to the Joint and requires less variables than the Independent. Detailed comparisons are reported in Sec. 4.3. 2015)) vehicle detection model to detect the number of vehicles (#vehicle) in each snapshot. To aggregate such raw data into time series, for every non-overlapping 5-minute window, we averaged #vehicle from each snapshot to obtain the average #vehicle as the only measurement. Finally, we obtained 186 time series and the gap between two consecutive time stamps is 5 minutes.

The natural missing rate of the whole dataset is 8.43%. In order to simulate experiments for imputation, we further remove some entries and hold them as ground truth for evaluation. The imputation task is to estimate values of these removed entries. To mimic the natural data missing pattern, we model our manual removal as a Burst Loss, which means at certain location the data is continuously missed for a certain period. More details about vehicle detection and burst loss are be found in Supp. To simulate various data missing extents, we vary the final missing rate after removal from 20% to 90%.

For each missing rate, we randomly select 432 consecutive time slots to train our model and evaluate the average RMSE of 5 trials. The dataset will be released publicly. KDD-2018 (Cup (2018) ) is an Air Quality and Meteorology dataset recorded hourly. As indicated in Luo et al. (2018a) , 11 locations and 12 measurements are selected. The natural missing rate is 6.83%. In order to simulate experiments for imputation, we follow Luo et al. (2018a) to split the data to every 48 hours, randomly hold values of some available entries and vary the missing rate from 20% to 90%. Mean Squared Error (MSE) is used for evaluation.

METR-LA (Jagadish et al. ( 2014)). We follow Li et al. (2018) to use this dataset for traffic speed forecasting. This dataset contains traffic speed at 207 locations recorded every 5 minutes for 4 months. Following Li et al. (2018) , 80% of data at the beginning of these 4 months is used for training and the remaining 20% is for testing. In order to simulate the forecasting scenario, within either training or testing set, every time series of consecutive 2 hours are enumerated. For each time series, data in the first hour is treated as input and data in the second hour is to be predicted. We respectively evaluate the forecasting results at 15-th, 30-th, 60-th minutes in the second 1 hour and also evalaute the average evaluation results within the total 1 hour. We use RMSE, Mean Absolute Error (MAE) and Mean Absolute Percentage Error (MAPE) as evaluation metrics. 3 shows that our method again achieves significant improvements on cross-dimensional data imputation task. Detailed overview of baselines can be found in Supp.

4.2. COMPARISONS WITH STATE-OF-THE-ART:

Forecasting (METR-LA). Table 4 shows that for the forecasting task, our CDSA method outperforms previous methods in most cases. In particular, our method demonstrates clear improvement at long-term forecasting such as 60 min. This again confirms that our CDSA cthe effectiveness of directly modeling the relationship between every two data values (could from different dimensions and of far distance). But RNN-based methods and methods that sequentially conduct spatial conv and temporal conv fail to model the distant spatio-temporal relationship explicitly. 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. 

5. CONCLUSION:

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.1 NORMALIZATION LAYER Under the NLP scenario, each word is embedded as a vector and normalized individually. However, in the Cross-Dimensional scenario, the normalization applied on each individual unit will always lead to a zero-output. As shown in Fig. 5 , different measurements may exhibit different correlation, i.e., PM2.5 and PM 10 are significantly positively correlated (ρ PM2.5, PM 10 = 0.8278) while NO 2 and O 3 are negatively correlated (ρ NO2,O3 = -0.5117). As discussed in Fig. 4 (b) in the paper, different measurement may be used as reference for imputation of other measurements. As such, the normalization cross multiple measurements is unreasonable and we choose to apply normalization for each measurement in parallel which presumes that the time series inside the spatial network is essentially drawn from a standard normal distribution. We subsequently add the trainable scalar and bias to scale the normalized value and the scalars (biases) for different measurements are trained individually. 

A.2 UNIT-WISE FEED-FORWARD NETWORK:

Making use of the approximation property of multi-linear layer Hornik et al. (1989) , a fully connected feed-forward network (FFN) is applied to each unit separately and identically. This FFN consists of three fully connected layer while RuLU is set as the activation function.

FFN(x) = max(max(0, xW 1 + b 1 )W 2 + b 2 )W 3 + b 3 (6)

During experiment, since the FFN is applied on each unit individually, we found the improvement by simply increasing the size of weight and bias of each layer is not obvious while increasing the depth of FFN will lead to obvious improvement.

A.3 IMPUTATION MASK:

For the self-attention sub-layer in imputation task NYC and KDD-2018, we modify the attention map with mask in (7) to prevent unit of available observation from contributing to the estimation of itself.

S(i, j) = -∞ i = j q i k j / √ d otherwise (7)

where q i and k j are d-dim vectors. This masking, combined with fact that there is no offset between input and output, ensures that the estimation of unit X(p(t, l, m)) depends on all the units except for itself, including both available and complemented units. In this way, the gradient back-propagation can be used to update the missed value effectively. The Table 9 shows the performance improvement of imputation mask applied in our model and demonstrate that mask prevents the estimation of itself and improve the inference ability of the model. Joint As shown in Fig. 6 , when we build the attention among different units in the Joint, two different kernels will be used to map each input unit X(p) = X (t, l, m) to an 1-D Query vector and an 1-D Key vector individually. As attention map is a scaled dot-product between Query and Key (Fig. 6 Left) after Softmax, each value of attention map in Joint is essentially the scaled numerical multiplication between each two units of input (Fig. 6 Right) after Softmax. As such, the multiple parameters inside that kernels only perform as a single scalar and the learning ability/relationship representation in Joint is limited.

Decomposed According to Sec. 3.2.3, to calculate the dimension-specific attention map, e.g., the attention map of Time A T , the input X will be reshaped into matrix X T . Thus, the units corresponding to the same timestamp, reshaped into one vector X T (t, :), will be mapped into dimension-specific Query vector Q T (t, :) and Key vector K T (t, :). As more parameters will be introduced into such vector-vector mapping, each dimensional-specific map can learn the intra-correlation and the crossdimensional attention map can model the relationship among each input units effectively.

Shared Same with the Decomposed, the Shared will calculate the dimension-specific attention maps individually. Like Joint, the Shared will map each unit X(p) into vector. To calculate the dimensionspecific attention map (e.g., A T ), the "vector-vector mapping" is essentially the summation of the units corresponding to the same timestamp while the multiple parameters introduced in the mapping still perform as a single scalar. As a result, the learning ability of the intra-correlation is limited so that the cross-dimensional attention map cannot model the relationship among input units effectively. where the subscript labels the attention between two units, i.e., t 12 = Softmax(q 1 k 2 / √ d) where q 1 and k 2 are d-dim vectors. Besides, the empty entry indicates 0.

As described in (2) in the paper, the original attention maps A T , A L and A M are reshaped to A T , A L and A M . By setting T = L = M = 2 as an example, we draw the attention maps before and after reshape in Fig. 7 . Making use of the matrix structure, we have

EQUATION

where

T t1=1 A T (t 0 , t 1 ) = 1, L l1=1 A L (l 0 , l 1 ) = 1 and M m1=1 A M (m 0 , m 1 ) = 1.

Besides, the reshape operation for attention map on different dimension is only determined by the index mapping function, p = p(t, l, m) = LM t + M l + m, from the 3-dimensional cube to the vector form.

C CDSA FRAMEWORK FOR DATA FORECASTING:

Different from time series imputation task, the time series forecasting task use the current observation to estimate the time series in the future. To begin with, We first introduce the framework for time series forecasting and we compare the performance for two different types of input.

C.1 PREDICTION FRAMEWORK:

As shown in Fig. 8 , we apply our CDSA mechanism in Transformer framework and use the same Feed Forward structure as in Sec. 3.3 in the paper. Notably, we set N = 9 for both encoder and decoder and no CDSA module is used to derive a complement input for prediction task where the missing value is replaced with global mean. The architecture detail is shown in Fig. 9 The decoder in NLP task originally sets the shifted output as input. Take the German-to-English translation scenario as an example where the embedded word vectors of German are set as the Encoder input, the model will first send a [GO] vector into the decoder and generate the first word vector of the translated English sequence, then the predicted vector will be sent into the decoder to predict the next word vector and the decoder will complete the sentence translation by repeating this operation until the end.

Mapping directly from this model setting in NLP task to our series forecasting scenario, we can also use the shifted ground truth as the decoder input, i.e., to forecast the speed of the next T time stamps given the speed of the first T time stamps, the data of T ≤ t ≤ 2T -1 are sent into the decoder. Consequently, the Casual Mask in Vaswani et al. (2017) need to be modified to make sure that the leftward information flow is prevented.

For data forecasting by CDSA in the Decomposed, the masking on Attention Map on Time is simply masking out (setting to -∞) the values in the input of Softmax which corresponds to the leftward information flow. Same with Vaswani et al. (2017) , the masking is only adopted in the Multi-head CDSA layer labeled as (Mask TLM) in Fig. 9 . However, as shown in Fig. 10 , to calculate the Attention Map of Location and Measurement for data forecasting at 2T -1, all illegal units of input corresponding to t ≥ 2T -1 have to be masked out (setting as 0). Then, the Masked Input are mapped to Query, Key and Value to build the Attention Map and calculate the Updated Value. sampling makes this framework suffer from an exhausted training time, since we need to send the predicted output back to decoder (Run) and repeat this Run for T times. During testing, we can use the output corresponding to its own Run (Step) as the predicted result, as well as the output of the last run (Final). As shown in the first 2 columns in Table 10 , the performance of outputs in the last run (Final) is better than that of Step mode, which means the leftward information flow still exists to break the auto-regressive property in data forecasting even though the mask is adopted on the input data. For fair comparison, the models for testing are trained in one GPU and the training time are all less than 50 hours.

Typically, missing value still exists in the original dataset. During experiment, we use the global mean to replace the missing value (Mean). We also compare the prediction performance between the input with Mean Filling and Complemented Input of Sec. 3.3. and the results in Table 10 shows the Complemented Input does not lead to performance improvement but increase the training workload. Consequently, we make encoder and decoder share the same input to reduce the memory usage and training time while our model achieves better performance for long-term prediction. et al. (2018a) select 11 common locations between the two datasets and the measurements of paired locations are concatenated. The location pairs are described in Table 11 . Since the unit of some measurements are label-based, e.g., the measurement weather denotes the types of weather including sunny, rainy and etc, these label are replaced with value such as 1, 2, ..., 9. As the range of different measurements varies, Luo et al. (2018a) first apply Z-score normalization for each measurement and the MSE is calculated based on normalized data while the metrics calculation for other dataset are based on the original data. Burst loss simulation: As shown in Fig. 11 , we term the loss area marked as blue as the Burst loss area where for a certain camera, the data is continuously missed for a δ time slots. After statistics and analysis, we found the the length of time slots 2 ≤ δ ≤ 134. Then, for those time slots of burst loss, we calculate the mean µ = 6.350773 and standard deviation δ = 9.809643. With the mean and standard deviation, We model the generation of burst loss as Gaussian process. As shown in Fig. 12 (b) and Fig. 13 , the arrow/unit with deeper color indicates a higher weight and the index of location can be found in Table 11 . According to the map in Fig. 13 , in most cases, neighbouring locations often share higher attention weight, e.g., the estimation at location 1 is mainly relied on the available data from location 2, location 3 and location 4. However, the estimation of location 11 is not relied on its neighbor (location 6), instead, it is mainly relied on the location 8. We think this relation is induced since both location 11 and location 8 are the center of express way while they are away from the urban area. Thus, the air condition from those two location my highly correlated. Besides the sample in Fig. 4 where the missing value can be estimated from the cross-dimensional available data, Fig. 14 visualizes another example and further shows that when predicting missing value A, our model pays strong attention to available values C and D while also some attention to another missing value B. Following the model hyper-parameter setting in Tabls. 1, we further compare the average running time for one segment during testing. As the way of attention modeling determines the computational efficiency, computation method with higher FLOPs also leads to longer running time. As shown in Table . 12, the running time of Joint is much higher than the rest 3 methods. Since the computation schemes of Shared is similar with the Decomposed, while the number of trainable variables of Shared is much less that of Decomposed, the average processing time of Shared is a bit smaller than the running time of the Decomposed. As described in the main paper, we use the 23-day data of NYC-Traffic for further forecasting. We split the data into two segments, one segment contained the data of the first 20 days and the other contained the data of the rest 3 days. We used the imputed data from the first segment to forecast the value of the second segment. To provide comprehensive comparison, according to different missing ratio (i.e., 30%, 50% 70%), we remove the value of some units in the first segment according to burst loss and then feed the segment with missing value into the data statistical imputation model (i.e., Mean filling, Kriging expo, Kriging linear) and deep learning methods (MTSI, DCRNN, BRITS, CDSA(ours)). Then, we feed the imputed data in to prediction model (ARIMA, Random Forest Friedman et al. (2001) ) and evaluate the forecasting performance in terms of RMSE. According to the Fig. 15 , we can find our proposed model always outperforms than other method.

E.3 RUNNING TIME COMPARISON:



F EXPERIMENT SETTING F.1 BASELINES:

We compare our method with both deep learning based methods and statistical methods while all statistical methods are adopted for each measurement individually.

• Mean Filling: Replace the missing data with global mean. The dataset in METR-LA also has missing data while the missing rate is 91%. Thus, the segment sample whose all units are zero, i.e., all-zero sample, exists. During training, the all-zero sample (in training set) essentially has no contribution for the model training. During testing and validation, the evaluation metric will of such samples will not be counted.

Data Pre-processing We apply Z-score normalization on each measurement as ( 9) respectively and fill the missing value with 0.

EQUATION

Optimizer We use the Adam optimizer Kingma & Ba (2014) while the initial learning rate in each epoch is set as lr(e) = r 0 × α ceil(max(0,e-d)/i) .

(10)

F.3 KDD-2015:

For KDD-2018 , Luo et al. (2018a) adopts content loss in a GAN-based model to train the random noise and then estimate the missing value, i.e., for one data segment, according to the specified missing rate, some available data will be held to evaluate the imputation performance, while the remaining available data will be set as groundtruth to calculate the content loss. Our experiment on NYC-Traffic follows the same experiment setup as KDD-2018 while the noise is replaced with the remaining available data and the model parameter is trained according to the content loss. Thus, there is no division of training, validation or testing since the training loss is not calculated from the held available data.

To comprehensively develop our experiment, we also adopting our method on KDD-2015 and follow the experiment setup in Yi et al. (2016) ; Cao et al. (2018) while the available data will be trained to predict the held data directly.

KDD-2015 (Zheng et al. (2015) ). This dataset focuses on air quality and meteorology. It contains data recorded hourly, ending up with totally 8,759 time stamps. PM2.5 measurement is recorded at 36 locations and Temperature and Humidity are recorded at 16 locations in Beijing from 05/01/2014 to 04/30/2015, with natural missing rate 13.3%, 21.1% and 28.9% respectively. We treat those two subsets as two separate tasks and evaluate our method on each task separately. Following Yi et al. (2016) , data in 3 rd , 6 th , 9 th and 12 th months are for testing and the remaining months are for training. We randomly select 36 consecutive time slots to train our model and evaluate Mean Absolute Error (MAE) as well as Mean Relative Error (MRE).

In order to simulate experiments for imputation, besides the natural missing data, for PM2.5 we follow the strategy used in (Yi et al. (2016) ; Cao et al. (2018) ; Zhou & Huang (2018) ) to further manually remove entries and hold the corresponding value as ground truth. The imputation task is to predict values of these manually removed entries. For Temperature and Humidity, we follow Zhou & Huang (2018) to randomly hold 20% of available data.

KDD-2015. Table 14 shows that for PM2.5, our method outperforms the traditional methods significantly and achieves comparable MAE as IIN (Zhou & Huang (2018) ) while better MRE than IIN (Zhou & Huang (2018) ). For Temperature and Humidity, our method consistently outperforms state-of-the-art methods. Since the Decomposed draws attention maps as the Independent but shares Value as the Joint, it reduces the computational complexity significantly. As shown in Table 15 , we also evaluate these methods on KDD-2015 datasets and the Decomposed achieves the best performance.

:

https://nyctmc.org/

https://github.com/bsmurphy/PyKrige

Figures and Tables:

Figure 2: Three choices of implementing our Cross-Dimensional Self-Attention mechanism

Figure 3: The framework employing CDSA for data imputation and forecasting.

Figure 4: Visualization of the cross-dimensional self-attention on KDD-2018. (a) Part of Time-Measurement attention map. (b) Two time series of PM2.5 and PM10. The value at purple dot is missing and our model predicts its value based on other values. The arrow in (b) represents attention whose score is highlighted with bounding box in (a) of the same color.

Figure 5: Different correlation between different measurements. The time slots when both of the chosen measurements are available are selected and the value of the first 300 selected time slots are plotted. Upper: PM2.5 & PM10 are significantly positively correlated and Lower: NO 2 & O 3 are negatively correlated.

Figure 6: The effective attention map calculation in Joint and Shared.

Figure 7: Reshape Attention Map: The original attention map in (a) is reshaped into (b-d) respectively. The variable (t, l, m) denotes the attention map units for Time, Location and Measurementwhere the subscript labels the attention between two units, i.e., t 12 = Softmax(q 1 k 2 /

Figure8: The framework of using Crossing-Dimensional Self-Attention (CDSA) for data forecasting.

Figure 10: Casual Mask Design for Attention Map on LocationBesides, the decoder generates predictions given previous ground truth observations during training while the ground truth observations are replaced by predictions generated by the model itself during testing. As, the discrepancy between the input distributions of training and testing can cause degraded performance, We adopt the integrated samplingBengio et al. (2015) as inLi et al. (2018) to mitigate this impact while this method is very time-consuming for the Transformer framework. During testing,

Figure 11: Loss condition of NYC dataset: The horizontal axis represents time line while the vertical axis represents sensors. Each unit indicates whether the data is missed in a 5-min window. The white area indicates available observation. The blue area indicates the Burst Loss. The red area indicates the time slots when the data of all the sensors are missed. The green area denotes as Abnormal for a certain location the data is continuously missed for a very long period.

Figure 12: Attention map example of the last CDSA layer

Figure 14: Visualization of prediction of missing point A, our model not only attends to available points (e.g. C, D) but also attends to missing points (e.g. B).

Figure 15: RMSE comparison for Downstream Forecasting on NYC-Traffic

Auto RegressiveAkaike (1969);Orfanidis (1988);Haddadi et al. (1998): Aggregate both forward and backward auto regressive on each time series data by weighted average and replace the missed value, implemented in MATLAB. • Kriging: Fit linear (Exponential) function between data variance and geodesic distance and replace the missing value w.r.t. the geo-location. Applied on each time slot and implemented in PyKrige 2 . • Multi-Imputation by Chained Equation (MICE) Buuren & Groothuis-Oudshoorn (2010): Replace missing data by creating multiple imputations with chained equations. • k-nearest neighbor (KNN) Speed (2003); Hastie et al. (1999); Troyanskaya et al. (2001): Use normalized Euclidean distance to find similar samples and impute the missing values with weighted average of its neighbors. • Matrix Factorization (MF) Yu et al. (2016): Factorizes the incomplete matrix into two low-rank matrices and fill the missing values by l 1 sparsity and l 2 penalty. • MTSI Luo et al. (2018a): Treat each measurement at different location as variables identically, align the time series of all the variables into one matrix and impute the missed data through RNN-based GAN. • ST-MVL Yi et al. (2016): Replace the missed value by using geo-location information • BRITS Cao et al. (2018): Treat the missing data as variable of the bidirectional RNN and impute by getting the delayed gradients for missing values in both forward and backward directions. • IIN Zhou & Huang (2018): Connect three bi-directional RNN in turn while the output of each RNN are adopted in loss calculation. • FC-LSTM Sutskever et al. (2014): Apply fully connected LSTM hidden units in Encoder-Decoder RNN structure to model the temporal dependency and forecast the traffic speed. • DCRNN Li et al. (2018): Model traffic speed as signals diffused over bidirectional graph and modify the gated recurrent unit in encoder-decoder RNN structure to capture the spatiotemporal dependency. • DST-GCNN Wang et al. (2018): Build a two-stream framework for model the condition stream and flow evolution while the model use the predicted condition to forecast the flow. • GaAN Zhang et al. (2018b): Use attention mechanism for each location and then graph aggregator to assemble the neighbor nodes and impute the missing value. F.2 IMPLEMENTATION DETAILS

Computational complexity of several methods to implement CDSAWe normalize each measurement of the input by subtracting the mean and dividing by standard deviation across training data. Then the entries with missed value are set 0. We use the Adam optimizer (Kingma & Ba (2014)) to minimize the Root Mean Square Error (RMSE) between the prediction and ground truth. The model is trained on a single NVIDIA GTX 1080 Ti GPU. More details (e.g., network hyper-parameters, learning rate and batch size) can be found in Supp.

Table content: <table><tr><td>Methods</td><td colspan="4">Independent Joint Shared Decomposed</td></tr><tr><td>FLOPs(×10 9 )</td><td>0.39</td><td>3.22</td><td>0.21</td><td>0.24</td></tr><tr><td>Number of Variables (×10 5 )</td><td>18.15</td><td>0.44</td><td>0.44</td><td>16.09</td></tr><tr><td>3.3 FRAMEWORK</td><td/><td/><td/><td/></tr><tr><td colspan="5">Imputation: As shown in Fig. 3(a), we apply our CDSA mechanism in a Transformer Encoder, a</td></tr><tr><td colspan="5">stack of N = 8 identical layers with residual connection (He et al. (2016)) and normalization (Lei Ba</td></tr><tr><td colspan="5">et al. (2016)) as employed by Vaswani et al. (2017). To reconstruct the missing (along with other)</td></tr><tr><td colspan="5">values of the input, we apply a fully connected Feed Forward network on the final Value tensor, which</td></tr><tr><td colspan="2">is trained jointly with the rest of the model.</td><td/><td/><td/></tr><tr><td colspan="5">Forecasting: As shown in Fig. 3(b), we apply our CDSA mechanism in Transformer framework</td></tr><tr><td colspan="5">where we set N = 9 for both encoder and decoder. Similar to imputation, we use a fully connected</td></tr><tr><td colspan="2">feed forward network to generate the predicted values.</td><td/><td/><td/></tr><tr><td>3.4 IMPLEMENTATION DETAILS</td><td/><td/><td/><td/></tr><tr><td>4 EXPERIMENTS</td><td/><td/><td/><td/></tr></table>

RMSE on dataset NYC-Traffic for comparisons with SOTA

Table content: <table><tr><td>Model \ Missing Rate</td><td>20%</td><td>30%</td><td>40%</td><td>50%</td><td>60%</td><td>70%</td><td>80%</td><td>90%</td></tr><tr><td>Auto Regressive</td><td colspan="8">2.354 2.357 2.359 2.362 2.364 2.652 2.796 3.272</td></tr><tr><td>Kriging expo</td><td colspan="8">2.142 2.145 2.157 2.152 2.155 2.165 2.182 2.231</td></tr><tr><td>Kriging linear</td><td colspan="8">2.036 2.008 2.031 2.038 2.056 2.074 2.111 2.194</td></tr><tr><td colspan="9">MTSI Luo et al. (2018a) 1.595 1.597 1.603 1.605 1.608 1.641 1.672 1.834</td></tr><tr><td colspan="9">BRITS Cao et al. (2018) 1.337 1.339 1.341 1.355 1.376 1.395 1.408 1.477</td></tr><tr><td colspan="9">DCRNN Li et al. (2018) 1.397 1.399 1.401 1.419 1.432 1.443 1.459 1.601</td></tr><tr><td>CDSA (ours)</td><td colspan="8">1.203 1.208 1.211 1.214 1.215 1.217 1.234 1.377</td></tr><tr><td colspan="7">Table 3: MSE on dataset KDD-2018 for comparisons with SOTA</td><td/><td/></tr><tr><td>Model \ Missing Rate</td><td>20%</td><td>30%</td><td>40%</td><td>50%</td><td>60%</td><td>70%</td><td>80%</td><td>90%</td></tr><tr><td>Mean Filling</td><td colspan="8">0.916 0.907 0.914 0.923 0.973 0.935 0.937 1.002</td></tr><tr><td>KNN Filling</td><td colspan="8">0.892 0.803 0.776 0.798 0.856 0.852 0.873 1.243</td></tr><tr><td>MF Filling</td><td colspan="8">0.850 0.785 0.787 0.772 0.834 0.805 0.860 1.196</td></tr><tr><td colspan="9">MTSI Luo et al. (2018a) 0.844 0.780 0.753 0.743 0.803 0.780 0.837 1.018</td></tr><tr><td colspan="9">BRITS Cao et al. (2018) 0.455 0.421 0.372 0.409 0.440 0.482 0.648 0.725</td></tr><tr><td colspan="9">DCRNN Li et al. (2018) 0.579 0.565 0.449 0.506 0.589 0.622 0.720 0.861</td></tr><tr><td>CDSA (ours)</td><td/><td/><td/><td/><td/><td/><td/><td/></tr></table>

MAE/RMSE/MAPE on dataset METR-LA for comparisons with SOTA

Table content: <table><tr><td>Model</td><td colspan="6">15min MAE RMSE MAPE MAE RMSE MAPE 30min</td></tr><tr><td colspan="2">FC-LSTM Sutskever et al. (2014) 3.44</td><td>6.3</td><td>9.6%</td><td>3.77</td><td>7.23</td><td>10.9%</td></tr><tr><td>MTSI Luo et al. (2018a)</td><td>3.75</td><td>7.31</td><td colspan="2">10.52% 3.89</td><td>7.73</td><td>11.04%</td></tr><tr><td>BRITS Cao et al. (2018)</td><td>2.86</td><td>5.46</td><td>7.49%</td><td>3.37</td><td>6.78</td><td>9.13%</td></tr><tr><td>DCRNN Li et al. (2018)</td><td>2.77</td><td>5.38</td><td>7.3%</td><td>3.15</td><td>6.45</td><td>8.8%</td></tr><tr><td>DST-GCNN Wang et al. (2018)</td><td>2.68</td><td>5.35</td><td>7.2%</td><td>3.01</td><td>6.23</td><td>8.52%</td></tr><tr><td>GaAN Zhang et al. (2018b)</td><td>2.71</td><td>5.24</td><td>6.99%</td><td>3.12</td><td>6.36</td><td>8.56%</td></tr><tr><td>CDSA(ours)</td><td>3.01</td><td>5.08</td><td>7.82%</td><td>3.14</td><td>5.38</td><td>8.30%</td></tr><tr><td>Model</td><td colspan="6">60min MAE RMSE MAPE MAE RMSE MAPE Mean</td></tr><tr><td colspan="2">FC-LSTM Sutskever et al. (2014) 4.37</td><td>6.89</td><td>13.2%</td><td>3.86</td><td>7.41</td><td>11.2%</td></tr><tr><td>MTSI Luo et al. (2018a)</td><td>4.22</td><td>8.39</td><td colspan="2">12.15% 4.01</td><td>7.59</td><td>10.85%</td></tr><tr><td>BRITS Cao et al. (2018)</td><td>3.65</td><td>7.66</td><td colspan="2">10.55% 3.32</td><td>6.96</td><td>9.47%</td></tr><tr><td>DCRNN Li et al. (2018)</td><td>3.60</td><td>7.59</td><td colspan="2">10.50% 3.28</td><td>6.80</td><td>8.87%</td></tr><tr><td>DST-GCNN Wang et al. (2018)</td><td>3.41</td><td>7.47</td><td>10.25%</td><td>-</td><td>-</td><td>-</td></tr><tr><td>GaAN Zhang et al. (2018b)</td><td>3.6</td><td>7.6</td><td>10.5%</td><td>3.16</td><td>6.41</td><td>8.72%</td></tr><tr><td>CDSA(ours)</td><td>3.40</td><td>6.27</td><td>9.76%</td><td>3.16</td><td>5.48</td><td>8.50%</td></tr><tr><td>4.3 DISCUSSIONS</td><td/><td/><td/><td/><td/><td/></tr></table>

Comparisons of different losses in CDSA on METR-LA 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 Table1, 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 the imputed historical data into traffic prediction model ARIMA. We compare performances in terms of RMSE: Mean Filling 1.953, Kriging expo 1.681, Kriging linear 1.733, MTSI 1.675, DCRNN 1.666, BRITS 1.579, CDSA 1.536. This indicate that when using the imputed time series for forecasting, our CDSA can achieve significant gains in the downstream forecasting task as well compared to traditional imputation methods. More details can be found in Supp. E.3.

Table content: <table><tr><td>Time</td><td>30min</td><td>Ave</td><td colspan="3">30min Ave 30min</td><td>Ave</td><td>30min</td><td>Ave</td></tr><tr><td>Metric \ Loss</td><td colspan="2">RMSE</td><td colspan="2">MSE</td><td colspan="2">MAE</td><td colspan="2">(RMSE+MAE)/2</td></tr><tr><td>MAE</td><td>3.14</td><td>3.16</td><td>3.43</td><td>3.41</td><td>3.28</td><td>3.33</td><td>3.21</td><td>3.25</td></tr><tr><td>RMSE</td><td>5.38</td><td>5.48</td><td>6.20</td><td>6.11</td><td>5.67</td><td>5.83</td><td>5.55</td><td>5.70</td></tr><tr><td>MAPE</td><td colspan="8">8.30% 8.50% 9.32% 9.19 8.70% 9.00% 8.53% 8.80%</td></tr><tr><td colspan="7">Ablation study of different cross-dimensional self-attention manners:</td><td/><td/></tr></table>

Comparisons of different manners to implement CDSA on dataset NYC-Traffic.

Table content: <table><tr><td colspan="2">Model \ Missing Rate 20%</td><td>30%</td><td>40%</td><td>50%</td><td>60%</td><td>70%</td><td>80%</td><td>90%</td></tr><tr><td>CDSA(Independent)</td><td colspan="8">1.327 1.327 1.331 1.355 1.362 1.379 1.393 1.425</td></tr><tr><td>CDSA(Joint)</td><td/><td colspan="6">Not Applicable due to memory usage limitation</td></tr><tr><td>CDSA(Shared)</td><td colspan="8">1.637 1.645 1.651 1.657 1.684 1.729 1.733 1.935</td></tr><tr><td colspan="9">CDSA(Decomposed) 1.204 1.208 1.211 1.214 1.215 1.217 1.235 1.377</td></tr></table>

Comparisons of different manners to implement CDSA on dataset KDD-2018. .799 0.672 0.692 0.784 0.793 0.791 0.832 CDSA(Decomposed) 0.373 0.393 0.287 0.291 0.387 0.495 0.521 0.631

Table content: <table><tr><td colspan="2">Model \ Missing Rate 20%</td><td>30%</td><td>40%</td><td>50%</td><td>60%</td><td>70%</td><td>80%</td><td>90%</td></tr><tr><td>CDSA(Independent)</td><td colspan="8">0.482 0.523 0.351 0.366 0.484 0.573 .608 0.721</td></tr><tr><td>CDSA(Joint)</td><td colspan="8">0.451 0.497 0.317 0.336 0.404 0.520 0.558 0.677</td></tr><tr><td>CDSA(Shared)</td><td colspan="2">0.783 0</td><td/><td/><td/><td/><td/></tr></table>

Comparisons of different manners to implement CDSA on dataset METR-LA.

Table content: <table><tr><td>Model \ Dataset</td><td colspan="6">60 min MAE RMSE MAPE MAE RMSE MAPE Mean</td></tr><tr><td>CDSA(Independent)</td><td>3.54</td><td>7.02</td><td colspan="2">10.29% 3.25</td><td>6.29</td><td>8.81%</td></tr><tr><td>CDSA(Joint)</td><td>3.63</td><td>7.62</td><td colspan="2">10.54% 3.30</td><td>6.83</td><td>9.43%</td></tr><tr><td>CDSA(Shared)</td><td>3.92</td><td>7.93</td><td colspan="2">11.17% 3.53</td><td>7.33</td><td>10.26%</td></tr><tr><td colspan="2">CDSA(Decomposed) 3.40</td><td>6.27</td><td>9.76%</td><td>3.16</td><td>5.48</td><td>8.50%</td></tr></table>

Performance Improvement for Imputation Mask

Table content: <table><tr><td colspan="2">Model \ Missing Rate</td><td>20%</td><td>30%</td><td>40%</td><td>50%</td><td>60%</td><td>70%</td><td>80%</td><td>90%</td></tr><tr><td>KDD-2018</td><td colspan="9">Masked 0.373 0.393 0.287 0.291 0.387 0.495 0.521 0.631 No Mask 0.886 0.839 0.838 0.849 0.917 0.903 0.947 1.195</td></tr><tr><td>NYC</td><td colspan="2">Masked No Mask 1.69 1.04</td><td>1.10 1.70</td><td>1.32 1.72</td><td>1.18 1.77</td><td>1.18 1.80</td><td>1.28 1.84</td><td>1.29 1.91</td><td>1.75 2.04</td></tr><tr><td colspan="4">A.4 ATTENTION MAP CALCULATION</td><td/><td/><td/><td/><td/></tr></table>

Comparisons of Prediction Performance on dataset METR-LA

Table content: <table><tr><td>Time</td><td>Metric</td><td colspan="2">Shifted Output Shifted Output (Mean Final) (Mean Step)</td><td>Encoder Input (Complemented)</td><td>Encoder Input (Mean)</td></tr><tr><td/><td>MAE</td><td>3.05</td><td>3.09</td><td>3.15</td><td>3.01</td></tr><tr><td>15 min</td><td>RMSE</td><td>5.46</td><td>5.50</td><td>5.31</td><td>5.08</td></tr><tr><td/><td>MAPE</td><td>8.31%</td><td>8.47%</td><td>8.18%</td><td>7.82%</td></tr><tr><td/><td>MAE</td><td>3.49</td><td>3.54</td><td>3.47</td><td>3.14</td></tr><tr><td>30 min</td><td>RMSE</td><td>6.62</td><td>6.66</td><td>5.96</td><td>5.38</td></tr><tr><td/><td>MAPE</td><td>9.56%</td><td>9.88%</td><td>9.19%</td><td>8.30%</td></tr><tr><td/><td>MAE</td><td>4.21</td><td>4.26</td><td>4.17</td><td>3.40</td></tr><tr><td>60 min</td><td>RMSE</td><td>8.14</td><td>8.19</td><td>7.67</td><td>6.27</td></tr><tr><td/><td>MAPE</td><td>11.44%</td><td>11.79%</td><td>11.94%</td><td>9.76%</td></tr><tr><td/><td>MAE</td><td>3.51</td><td>3.56</td><td>3.54</td><td>3.16</td></tr><tr><td>Mean</td><td>RMSE</td><td>6.56</td><td>6.61</td><td>6.14</td><td>5.48</td></tr><tr><td/><td>MAPE</td><td>9.56%</td><td>9.84%</td><td>9.53%</td><td>8.50%</td></tr></table>

Selection of Common Locations between Air Quality and Meteorology The original KDD 2018 dataset consists of an Air Quality data of 35 locations and an Meteorology dataset of 18 locations. each dataset contains 6 different measurements. During experiment, Luo

Table content: <table><tr><td>D DATASET DESCRIPTION</td><td/><td/></tr><tr><td colspan="3">D.1 DATA AGGREGATION ON KDD 2018 DATASET</td></tr><tr><td/><td>Air Quality</td><td>Meteorology</td></tr><tr><td colspan="2">1 fengtaihuayuan</td><td>fengtai meo</td></tr><tr><td>2</td><td>fangshan</td><td>fangshan meo</td></tr><tr><td>3</td><td>daxing</td><td>daxing meo</td></tr><tr><td>4</td><td>tongzhou</td><td>tongzhou meo</td></tr><tr><td>5</td><td>shunyi</td><td>shunyi meo</td></tr><tr><td>6</td><td>pingchang</td><td>pingchang meo</td></tr><tr><td>7</td><td>mentougou</td><td>mentougou meo</td></tr><tr><td>8</td><td>pinggu</td><td>pinggu meo</td></tr><tr><td>9</td><td>huairou</td><td>huairou meo</td></tr><tr><td>10</td><td>miyun</td><td>miyun meo</td></tr><tr><td>11</td><td>yanqin</td><td>yanqing meo</td></tr></table>

Computational complexity of several methods to implement CDSA

Table content: <table><tr><td>Methods</td><td colspan="4">Independent Joint Shared Decomposed</td></tr><tr><td>Average running time / sample (ms)</td><td>218</td><td>859</td><td>159</td><td>161</td></tr></table>



Table content: <table><tr><td/><td/><td/><td colspan="2">: Statistics of Dataset</td><td/><td/></tr><tr><td>Dataset</td><td>Task</td><td># location</td><td># meas.</td><td>duration</td><td>Start</td><td>End</td></tr><tr><td>KDD-2018</td><td>Imputation</td><td>36</td><td>12</td><td>364 days</td><td>1/1/2017</td><td>12/30/2017</td></tr><tr><td colspan="2">NYC Traffic Imputation</td><td>186</td><td>1</td><td>23 days</td><td>12/03/2015</td><td>12/26/2015</td></tr><tr><td colspan="2">METR-LA Forecasting</td><td>207</td><td>1</td><td>122 days</td><td>3/1/2012</td><td>6/30/2012</td></tr><tr><td>Dataset</td><td>#Training</td><td colspan="5">#Testing #Validation unit duration seg. length Loss function</td></tr><tr><td>KDD-2018</td><td>182</td><td>-</td><td>182</td><td>2 hours</td><td>48 hours</td><td>RMSE</td></tr><tr><td>NYC Traffic</td><td>173</td><td>-</td><td>173</td><td>5 minutes</td><td>36 hours</td><td>RMSE</td></tr><tr><td>METR-LA</td><td>23991</td><td>3404</td><td>6831</td><td>5 minutes</td><td>1 hour</td><td>RMSE</td></tr></table>

MAE/MRE on dataset KDD-2015 for comparisons with SOTA

Table content: <table><tr><td>Model \ Dataset</td><td>PM2.5 MAE MRE</td><td colspan="2">TEMP MAE MRE</td><td colspan="2">HUM MAE MRE</td></tr><tr><td>Mean</td><td colspan="5">55.51 77.97% 9.21 97.56% 20.34 57.85%</td></tr><tr><td>KNN</td><td colspan="5">29.79 41.85% 1.26 19.83% 7.28 16.22%</td></tr><tr><td>MICE</td><td colspan="5">27.42 38.52% 1.23 18.29% 6.97 15.87%</td></tr><tr><td>ST-MVL Yi et al. (2016)</td><td colspan="2">12.12 17.40% 0.68</td><td>4.59%</td><td>3.37</td><td>5.91%</td></tr><tr><td>MTSI Luo et al. (2018a)</td><td colspan="2">13.34 18.01% 0.71</td><td>4.67%</td><td>3.51</td><td>6.21%</td></tr><tr><td>BRITS Cao et al. (2018)</td><td colspan="2">11.56 16.65% 0.63</td><td>4.16%</td><td>3.31</td><td>5.68%</td></tr><tr><td>DCRNN Li et al. (2018)</td><td colspan="2">12.33 17.82% 0.69</td><td>4.59%</td><td>2.95</td><td>5.12%</td></tr><tr><td colspan="3">IIN Zhou &amp; Huang (2018) 10.63 15.31% 0.63</td><td>4.22%</td><td>2.90</td><td>5.09%</td></tr><tr><td>CDSA (ours)</td><td colspan="2">10.67 14.89% 0.61</td><td>4.15%</td><td>2.81</td><td>4.92%</td></tr></table>

Comparisons of different manners to implement CDSA on dataset KDD-2015.

Table content: <table><tr><td>Model \ Dataset</td><td>PM2.5 MAE MRE</td><td colspan="4">TEMP MAE MRE MAE MRE HUM</td></tr><tr><td colspan="3">CDSA(Independent) 11.54 16.01% 0.68</td><td>4.40%</td><td>3.19</td><td>5.42%</td></tr><tr><td>CDSA(Joint)</td><td colspan="2">11.20 15.52% 0.65</td><td>4.27%</td><td>3.05</td><td>5.37%</td></tr><tr><td>CDSA(Shared)</td><td colspan="2">13.85 19.26% 0.75</td><td>5.18%</td><td>3.56</td><td>6.47%</td></tr><tr><td colspan="6">CDSA(Decomposed) 10.67 14.89% 0.61 4.15% 2.81 4.92%</td></tr></table>

Peer review (iclr2020):
This paper proposes a Transformer-based model with cross-dimensional self-attention for multivariate time series imputation and forecasting. The authors consider time series with observations collected at different locations (L), for different measurements (M), and at different timestamps (T). The authors describe 4 different self-attention mechanisms based on how the three dimensions, and it turns out the proposed Decomposed approach achieves the best performance and has moderate model complexity among the four. Experiments on several traffic and air quality datasets show the superiority of the proposed model. Overall the problem and the proposed model are well motivated. Handling time series data with missing values is quite important, and the authors design the novel cross-dimensional attention mechanism which is reasonable and performs well. Especially, the authors compare several recent RNN-based models. The proposed method outperforms these strong baselines in imputation and long-term forecasting tasks. However, I do have a few questions and concerns. It would be quite helpful to see the training time and model size comparisons with baselines, which is to validate the claim in the introduction that `replacing the conventional RNN-based models to speed up training`. The proposed model treats all three dimensions equally, with direct attention of every two variables, and is independent with the order. Though effective and mathematically clean, I am not sure the temporal/spatial smoothness and dependencies in time series are properly modeled in this way -- as time series is not the same as embedded sequences in NLP. This may explain why the performance on short-term forecasting is relatively unsatisfying. It seems that the proposed model is designed for missing completely at random (implied by the statement `... due to unexpected sensor damages or communication errors` from the introduction, and the experimental settings on adding missing values). Many missing variables in time series may be missing at random or even not at random. About the experiments: Two datasets of the three mentioned in the main paper have M=1, which degrade the proposed model from 3-dimensional to 2-dimensional. Why forecasting experiment is conducted on METR-LA, while using the imputation for forecasting is conducted on a different dataset and without comparing other forecasting baselines? What are the metrics used in Tables 6, 7, 9? Several metrics are used (RMSE, MSE, MAPE, MAE, MRE) while results on different datasets are shown in different but not all metrics. Is there any reason to cherry-pick metrics for different experiments? In Table 4, the proposed method*s results in RMSE is consistently better than shown in MAE compared with other baselines. Any explanations would be useful. The overall idea is relatively easy to follow, while some detailed descriptions should be added or clarified. When taking health-care data as an example of geo-tagged time series, could you explain or provide references? Figure 2 only demonstrates 3 attention mechanisms, and the Shared should also be included. S(i,j) is used in Section 3.1 without explicit formal definition. Please clarify the sentence about sigma below Equation (4). Please refer to the section number explicitly in Supp if used. (E.g., on Pages 5 and 7.) On which dataset and what settings are the results in Table 1 computed? The numbers are helpful, but it would be better if the results are computed based on the hyperparameters (e.g., T, L, M, d_V, etc). Minor typos: Page 3, Paragraph of RNN-based data imputation methods: `...indistinguishable. so that...` Page 3, Section 3.1, `..where Then, ...` Page 14, A* is used to denote the reshaped tensor, while 	ilde is used in the main paper. Page 16, `During testing,`