A Dual-Stage Attention-Based Recurrent Neural Network for Time Series Prediction

1 Introduction

Time series prediction algorithms have been widely applied in many areas, e.g., financial market prediction [Wu et al., 2013], weather forecasting [Chakraborty et al., 2012], and complex dynamical system analysis [Liu and Hauskrecht, 2015]. Although the well-known autoregressive moving average (ARMA) model [Whittle, 1951] and its variants [Asteriou and Hall, 2011; Brockwell and Davis, 2009] have shown their effectiveness for various real world applications, they cannot model nonlinear relationships and do not differentiate among the exogenous (driving) input terms. To address this issue, various nonlinear autoregressive exogenous (NARX) models [Lin et al., 1996; Gao and Er, 2005;

∗Most of this work was performed while the first author was an intern at NEC Labs America.

Diaconescu, 2008; Yan et al., 2013] have been developed. Typically, given the previous values of the target series, i.e. (y1, y2, · · · , yt-1) with yt-1 ∈ R, as well as the current and past values of n driving (exogenous) series, i.e., (x1, x2, · · · , xt) with xt ∈ Rn , the NARX model aims to learn a nonlinear mapping to the current value of target series yt, i.e., ˆ yt = F(y1, y2, · · · , yt-1, x1, x2, · · · , xt), where F(·) is the mapping function to learn.

Despite the fact that a substantial effort has been made for time series prediction via kernel methods [Chen et al., 2008], ensemble methods [Bouchachia and Bouchachia, 2008], and Gaussian processes [Frigola and Rasmussen, 2014], the drawback is that most of these approaches employ a predefined nonlinear form and may not be able to capture the true underlying nonlinear relationship appropriately. Recurrent neural networks (RNNs) [Rumelhart et al., 1986; Werbos, 1990; Elman, 1991], a type of deep neural network specially designed for sequence modeling, have received a great amount of attention due to their flexibility in capturing nonlinear relationships. In particular, RNNs have shown their success in NARX time series forecasting in recent years [Gao and Er, 2005; Diaconescu, 2008]. Traditional RNNs, however, suffer from the problem of vanishing gradients [Bengio et al., 1994] and thus have difficulty capturing long-term dependencies. Recently, long short-term memory units (LSTM) [Hochreiter and Schmidhuber, 1997] and the gated recurrent unit (GRU) [Cho et al., 2014b] have overcome this limitation and achieved great success in various applications, e.g., neural machine translation [Bahdanau et al., 2014], speech recognition [Graves et al., 2013], and image processing [Karpathy and Li, 2015]. Therefore, it is natural to consider state-of-theart RNN methods, e.g., encoder-decoder networks [Cho et al., 2014b; Sutskever et al., 2014] and attention based encoderdecoder networks [Bahdanau et al., 2014], for time series prediction.

Based upon LSTM or GRU units, encoder-decoder networks [Kalchbrenner and Blunsom, 2013; Cho et al., 2014a; Cho et al., 2014b; Sutskever et al., 2014] have become popular due to their success in machine translation. The key idea is to encode the source sentence as a fixed-length vector and use the decoder to generate a translation. One problem with encoder-decoder networks is that their performance will deteriorate rapidly as the length of input sequence increases [Cho et al., 2014a]. In time series analysis, this could be a con-

(a) Input Attention Mechanism

(b) Temporal Attention Mechanism

Figure 1: Graphical illustration of the dual-stage attention-based recurrent neural network. (a) The input attention mechanism computes the attention weights αk t for multiple driving series {x1 , x2 , · · · , xn } conditioned on the previous hidden state ht-1 in the encoder and then feeds the newly computed ˜xt = (α1 t x1t , α2 tx2t , · · · , αn t xnt )⊤ into the encoder LSTM unit. (b) The temporal attention system computes the attention weights βt t based on the previous decoder hidden state dt-1 and represents the input information as a weighted sum of the encoder hidden states across all the time steps. The generated context vector ct is then used as an input to the decoder LSTM unit. The output ˆ yT of the last decoder LSTM unit is the predicted result.

cern since we usually expect to make predictions based upon a relatively long segment of the target series as well as driving series. To resolve this issue, the attention-based encoderdecoder network [Bahdanau et al., 2014] employs an attention mechanism to select parts of hidden states across all the time steps. Recently, a hierarchical attention network [Yang et al., 2016], which uses two layers of attention mechanism to select relevant encoder hidden states across all the time steps, was also developed. Although attention-based encoderdecoder networks and hierarchical attention networks have shown their efficacy for machine translation, image captioning [Xu et al., 2015], and document classification, they may not be suitable for time series prediction. This is because when multiple driving (exogenous) series are available, the network cannot explicitly select relevant driving series to make predictions. In addition, they have mainly been used for classification, rather than time series prediction.

To address these aforementioned issues, and inspired by some theories of human attention [H¨ubner et al., 2010] that posit that human behavior is well-modeled by a two-stage attention mechanism, we propose a novel dual-stage attentionbased recurrent neural network (DA-RNN) to perform time series prediction. In the first stage, we develop a new attention mechanism to adaptively extract the relevant driving series at each time step by referring to the previous encoder hidden state. In the second stage, a temporal attention mechanism is used to select relevant encoder hidden states across all time steps. These two attention models are well integrated within an LSTM-based recurrent neural network (RNN) and can be jointly trained using standard back propagation. In this way, the DA-RNN can adaptively select the most relevant input features as well as capture the long-term temporal dependencies of a time series appropriately. To justify the effectiveness of the DA-RNN, we compare it with state-ofthe-art approaches using the SML 2010 dataset and the NASDAQ 100 Stock dataset with a large number of driving series. Extensive experiments not only demonstrate the effectiveness of the proposed approach, but also show that the DA-RNN is easy to interpret, and robust to noisy inputs.

2 Dual-Stage Attention-Based RNN

In this section, we first introduce the notation we use in this work and the problem we aim to study. Then, we present the motivation and details of the DA-RNN for time series prediction.

2.1 Notation and Problem Statement

Given n driving series, i.e., X = (x1 , x2 , · · · , xn )⊤ = (x1, x2, · · · , xT ) ∈ Rn×T , where T is the length of window size, we use xk = (xk1 , xk2 , ·, xkT )⊤ ∈ RT to represent a driving series of length T and employ xt = (x1t , x2t , · · · , xnt )⊤ ∈ Rn to denote a vector of n exogenous (driving) input series at time t.

Typically, given the previous values of the target series, i.e. (y1, y2, · · · , yT-1) with yt ∈ R, as well as the current and past values of n driving (exogenous) series, i.e., (x1, x2, · · · , xT ) with xt ∈ Rn , the NARX model aims to learn a nonlinear mapping to the current value of the target series yT :

where F (·) is a nonlinear mapping function we aim to learn.

2.2 Model

Some theories of human attention [H¨ubner et al., 2010] argue that behavioral results are best modeled by a two-stage attention mechanism. The first stage selects the elementary stimulus features while the second stage uses categorical information to decode the stimulus. Inspired by these theories, we propose a novel dual-stage attention-based recurrent neural network (DA-RNN) for time series prediction. In the encoder, we introduce a novel input attention mechanism that can adaptively select the relevant driving series. In the decoder, a temporal attention mechanism is used to automatically select relevant encoder hidden states across all time steps. For the objective, a square loss is used. With these two attention mechanisms, the DA-RNN can adaptively select the most relevant input features and capture the long-term temporal dependencies of a time series. A graphical illustration of the proposed model is shown in Figure 1.

Encoder with input attention

The encoder is essentially an RNN that encodes the input sequences into a feature representation in machine translation [Cho et al., 2014b; Sutskever et al., 2014]. For time series prediction, given the input sequence X = (x1, x2, · · · , xT ) with xt ∈ Rn , where n is the number of driving (exogenous) series, the encoder can be applied to learn a mapping from xt to ht (at time step t) with

where ht ∈ Rm is the hidden state of the encoder at time t, m is the size of the hidden state, and f1 is a non-linear activation function that could be an LSTM [Hochreiter and Schmidhuber, 1997] or gated recurrent unit (GRU) [Cho et al., 2014b]. In this paper, we use an LSTM unit as f1 to capture long-term dependencies. Each LSTM unit has a memory cell with the state st at time t. Access to the memory cell will be controlled by three sigmoid gates: forget gate ft, input gate it and output gate ot. The update of an LSTM unit can be summarized as follows:

where [ht-1; xt] ∈ Rm+n is a concatenation of the previous hidden state ht-1 and the current input xt. Wf , Wi, Wo, Ws ∈ Rm×(m+n) , and bf , bi, bo, bs ∈ Rm are parameters to learn. σ and ⊙ are a logistic sigmoid function and an elementwise multiplication, respectively. The key reason for using an LSTM unit is that the cell state sums activities over time, which can overcome the problem of vanishing gradients and better capture long-term dependencies of time series.

Inspired by the theory that the human attention system can select elementary stimulus features in the early stages of processing [H¨ubner et al., 2010], we propose an input attentionbased encoder that can adaptively select the relevant driving series, which is of practical meaning in time series prediction.

Given the k-th input driving series xk = (xk1 , xk2 , ·, xkT )⊤ ∈ RT , we can construct an input attention mechanism via a deterministic attention model, i.e., a multilayer perceptron, by referring to the previous hidden state ht-1 and the cell state st-1 in the encoder LSTM unit with:

and

where ve ∈ RT , We ∈ RT×2m and Ue ∈ RT×T are parameters to learn.We omit the bias terms in Eqn. (8) to be succinct. αk t is the attention weight measuring the importance of the k-th input feature (driving series) at time t. A softmax function is applied to ekt to ensure all the attention weights sum to 1. The input attention mechanism is a feed forward network that can be jointly trained with other components of the RNN. With these attention weights, we can adaptively extract the driving series with

Then the hidden state at time t can be updated as:

where f1 is an LSTM unit that can be computed according to Eqn. (3) - (7) with xt replaced by the newly computed ˜xt. With the proposed input attention mechanism, the encoder can selectively focus on certain driving series rather than treating all the input driving series equally.

Decoder with temporal attention

To predict the output ˆ yT , we use another LSTM-based recurrent neural network to decode the encoded input information. However, as suggested by Cho et al. [2014a], the performance of the encoder-decoder network can deteriorate rapidly as the length of the input sequence increases. Therefore, following the encoder with input attention, a temporal attention mechanism is used in the decoder to adaptively select relevant encoder hidden states across all time steps. Specifically, the attention weight of each encoder hidden state at time t is calculated based upon the previous decoder hidden state dt-1 ∈ Rp and the cell state of the LSTM unit s′t-1 ∈ Rp with

and

where [dt-1; s′t-1 ] ∈ R2p is a concatenation of the previous hidden state and cell state of the LSTM unit. vd ∈ Rm, Wd ∈ Rm×2p and Ud ∈ Rm×m are parameters to learn. The bias terms here have been omitted for clarity. The attention weight βi t represents the importance of the i-th encoder hidden state for the prediction. Since each encoder hidden state hi is mapped to a temporal component of the input, the attention mechanism computes the context vector ct as a weighted sum of all the encoder hidden states {h1, h2, · · · , hT },

Note that the context vector ct is distinct at each time step.

Once we get the weighted summed context vectors, we can combine them with the given target series (y1, y2, · · · , yT-1):

where [yt-1; ct-1] ∈ Rm+1 is a concatenation of the decoder input yt-1 and the computed context vector ct-1. Parameters ˜w ∈ Rm+1 and ˜b ∈ R map the concatenation to the size the decoder input. The newly computed ˜ yt-1 can be used for the update of the decoder hidden state at time t:

We choose the nonlinear function f2 as an LSTM unit [Hochreiter and Schmidhuber, 1997], which has been widely used in modeling long-term dependencies. Then dt can be updated as:

where [dt-1; ˜ yt-1] ∈ Rp+1 is a concatenation of the previous hidden state dt-1 and the decoder input ˜ yt-1. W′f , W′i , W′o , W′s ∈ Rp×(p+1) , and b′f , b′i , b′o , b′s ∈ Rp are parameters to learn. σ and ⊙ are a logistic sigmoid function and an elementwise multiplication, respectively.

For NARX modeling, we aim to use the DA-RNN to approximate the function F so as to obtain an estimate of the current output ˆ yT with the observation of all inputs as well as previous outputs. Specifically, ˆ yT can be obtained with

where [dT ; cT ] ∈ Rp+m is a concatenation of the decoder hidden state and the context vector. The parameters Wy ∈ Rp×(p+m) and bw ∈ Rp map the concatenation to the size of the decoder hidden states. The linear function with weights vy ∈ Rp and bias bv ∈ R produces the final prediction result.

Training procedure

We use minibatch stochastic gradient descent (SGD) together with the Adam optimizer [Kingma and Ba, 2014] to train the model. The size of the minibatch is 128. The learning rate starts from 0.001 and is reduced by 10% after each 10000 iterations. The proposed DA-RNN is smooth and differentiable, so the parameters can be learned by standard back propagation with mean squared error as the objective function:

where N is the number of training samples. We implemented the DA-RNN in the Tensorflow framework [Abadi et al., 2015].

3 Experiments

In this section, we first describe two datasets for empirical studies. Then, we introduce the parameter settings of DARNN and the evaluation metrics. Finally, we compare the proposed DA-RNN against four different baseline methods, interpret the input attention as well as the temporal attention of DA-RNN, and study its parameter sensitivity.

3.1 Datasets and Setup

To test the performance of different methods for time series prediction, we use two different datasets as shown in Table 1. SML 2010 is a public dataset used for indoor temperature

forecasting. This dataset is collected from a monitor system mounted in a domestic house. We use the room temperature as the target series and select 16 relevant driving series that contain approximately 40 days of monitoring data. The data was sampled every minute and was smoothed with 15 minute means. In our experiment, we use the first 3200 data points as the training set, the following 400 data points as the validation set, and the last 537 data points as the test set.

In the NASDAQ 100 Stock dataset 1 , we collected the stock prices of 81 major corporations under NASDAQ 100, which are used as the driving time series. The index value of the NASDAQ 100 is used as the target series. The frequency of the data collection is minute-by-minute. This data covers the period from July 26, 2016 to December 22, 2016, 105 days in total. Each day contains 390 data points from the opening to closing of the market except that there are 210 data points on November 25 and 180 data points on December 22. In our experiments, we use the first 35,100 data points as the training set and the following 2,730 data points as the validation set. The last 2,730 data points are used as the test set. This dataset is publicly available and will be continuously enlarged to aid the research in this direction.

3.2 Parameter Settings and EvaluationMetrics

There are three parameters in the DA-RNN, i.e., the number of time steps in the window T, the size of hidden states for the encoder m, and the size of hidden states for the decoder p. To determine the window size T, we conducted a grid search over T ∈ {3, 5, 10, 15, 25}. The one (T = 10) that achieves the best performance over validation set is used for test. For the size of hidden states for encoder (m) and decoder (p), we set m = p for simplicity and conduct grid search over m = p ∈ {16, 32, 64, 128, 256}. Those two (i.e, m = p = 64, 128) that achieve the best performance over the validation set are used for evaluation. For all the RNN based approaches (i.e., NARX RNN, Encoder-Decoder, Attention RNN, Input-Attn-RNN and DA-RNN), we train them 10 times and report their average performance and standard deviations for comparison.

1 http://cseweb.ucsd.edu/∼yaq007/NASDAQ100 stock data.html

To measure the effectiveness of various methods for time series prediction, we consider three different evaluation metrics. Among them, root mean squared error (RMSE) [Plutowski et al., 1996] and mean absolute error (MAE) are two scale-dependent measures, and mean absolute percentage error (MAPE) is a scale-dependent measure. Specifically, assuming yt is the target at time t and ˆ yt is the predicted value at time t, RMSE is defined as RMSE = √ 1N ∑Ni=1 (yi t - ˆ yi t )2 and MAE is denoted as MAE = 1N ∑Ni=1 |yi t - ˆ yi t |. When comparing the prediction performance across different datasets, mean absolute percentage error is popular because it measures the prediction deviation proportion in terms of the true values, i.e., MAPE = 1N ∑Ni=1 | yi t-ˆ yi t yi t | × 100%.

3.3 Results-I: Time Series Prediction

To demonstrate the effectiveness of the DA-RNN, we compare it against 4 baseline methods. Among them, the autoregressive integrated moving average (ARIMA) model is a generalization of an autoregressive moving average (ARMA) model [Asteriou and Hall, 2011]. NARX recurrent neural network (NARX RNN) is a classic method to address time series prediction [Diaconescu, 2008]. The encoder-decoder network (Encoder-Decoder) [Cho et al., 2014b] and attentionbased encoder-decoder network (Attention RNN) [Bahdanau et al., 2014] were originally used for machine translation tasks, in which each time step of the decoder output should be used to produce a probability distribution over the translated word codebook. To perform time series prediction, we modify these two approaches by changing the output to be a single scalar value, and use a squared loss as the objective function (as we did for the DA-RNN). The input to these networks is no longer words or word representations, but the n scalar driving series of length T. Additionally, the decoder has the additional input of the previous values of the target series as the given information.

Furthermore, we show the effectiveness of DA-RNN via step-by-step justification. Specifically, we compare dualstage attention-based recurrent neural network (DA-RNN) against the setting that only employs its input attention mechanism (Input-Attn-RNN). For all RNN-based methods, the encoder takes n driving series of length T as the input and the decoder takes the previous values of the target series as the given information for fair comparison. The time series prediction results of DA-RNN and baseline methods over the two datasets are shown in Table 2.

In Table 2, we observe that the RMSE of ARIMA is generally worse than RNN based approaches. This is because ARIMA only considers the target series (y1, · · · , yt-1) and ignores the driving series (x1, · · · , xt). For RNN based approaches, the performance of NARX RNN and EncoderDecoder are comparable. Attention RNN generally outperforms Encoder-Decoder since it is capable to select relevant hidden states across all the time steps in the encoder. Within DA-RNN, the input attention RNN (Input-Attn-RNN (128)) consistently outperforms Encoder-Decoder as well as Attention RNN. This suggests that adaptively extracting driving series can provide more reliable input features to make accurate predictions. With integration of the input attention mechanism as well as temporal attention mechanism, our DARNN achieves the best MAE, MAPE, and RMSE across two

128 256 and Attention RNN.

3.4 Results-II: Interpretation

To study the effectiveness of the input attention mechanism within DA-RNN, we test it with noisy driving (exogenous) series as the input. Specifically, within NASDAQ 100 Stock dataset, we generate 81 additional noisy driving series by randomly permuting the original 81 driving series. Then, we put these 81 noisy driving series together with the 81 original driving series as the input and test the effectiveness of DA-RNN. When the length of time steps T is 10 and the size of hidden states is m = p = 128, DA-RNN achieves MAE: 0.28 ± 0.007, MAPE: (0.56 ±0.01)×10-2 and RMSE: 0.42 ± 0.009, which are comparable to its performance in Table 2. This indicates that DA-RNN is robust to noisy inputs.

To further investigate the input attention mechanism, we plot the input attention weights of DA-RNN for the 162 input driving series (the first 81 are original and the last 81 are noisy) in Figure 3. The plotted attention weights in Figure 3 are taken from a single encoder time step and similar patterns can also be observed for other time steps. We find that the input attention mechanism can automatically assign larger weights for the 81 original driving series and smaller weights for the 81 noisy driving series in an online fashion using the activation of the input attention network to scale these weights. This demonstrates that input attention mechanism can aid DA-RNN to select relevant input driving series and suppress noisy input driving series.

To investigate the effectiveness of the temporal attention mechanism within DA-RNN, we compare DA-RNN to InputAttn-RNN when the length of time steps T varies from 3, 5, 10, 15, to 25. The detailed results over two datasets are shown in Figure 4. We observe that when T is relatively large, DA-RNN can significantly outperform Input-Attn-RNN. This suggests that temporal attention mechanism can capture longterm dependencies by selecting relevant encoder hidden states across all the time steps.

Figure 5: RMSE vs. size of hidden states of encoder/decoder over SML 2010 (left) and NASDAQ 100 Stock (right).

3.5 Results-III: Parameter Sensitivity

We study the sensitivity of DA-RNN with respect to its parameters, i.e., the length of time steps T and the size of hidden states for encoder m (decoder p). When we vary T or m (p), we keep the others fixed. By setting m = p = 128, we plot the RMSE versus different lengths of time steps in the window T in Figure 4. It is easily observed that the performance of DA-RNN and Input-Attn-RNN will be worse when the length of time steps is too short or too long while DA-RNN is relatively more robust than Input-Attn-RNN. By setting T = 10, we also plot the RMSE versus different sizes of hidden states for encoder and decoder (m = p ∈ {16, 32, 64, 128, 256}) in Figure 5. We notice that DA-RNN usually achieves the best performance when m = p = 64 or 128. Moreover, we can also conclude that DA-RNN is more robust to parameters than Input-Attn-RNN.

4 Conclusion

In this paper, we proposed a novel dual-stage attention-based recurrent neural network (DA-RNN), which consists of an encoder with an input attention mechanism and a decoder with a temporal attention mechanism. The newly introduced input attention mechanism can adaptively select the relevant driving series. The temporal attention mechanism can naturally capture the long-range temporal information of the encoded inputs. Based upon these two attention mechanisms, the DA-RNN can not only adaptively select the most relevant input features, but can also capture the long-term temporal dependencies of a time series appropriately. Extensive experiments on the SML 2010 dataset and the NASDAQ 100 Stock dataset demonstrated that our proposed DA-RNN can outperform state-of-the-art methods for time series prediction.

The proposed dual-stage attention-based recurrent neural network (DA-RNN) not only can be used for time series prediction, but also has the potential to serve as a general feature learning tool in computer vision tasks [Pu et al., 2016; Qin et al., 2015]. In the future, we are going to employ DA-RNN to perform ranking and binary coding [Song et al., 2015; Song et al., 2016].

Acknowledgments

GWC is supported in part by NSF cooperative agreement SMA 1041755 to the Temporal Dynamics of Learning Center, and a gift from Hewlett Packard. GWC and YQ were also partially supported by Guangzhou Science and Technology Planning Project (Grant No. 201704030051).