STDI-Net: Spatial-Temporal Network with Dynamic Interval Mapping for Bike Sharing Demand Prediction

The spatial module of the network aims to extract the joint features of all stations in each demand matrix. For each data node in one sequential input, we apply a residual convolutional block to operate on it. Inspired by (He et al. 2016) that proposed the residual link to solve problems brought by very deep networks, like the vanishing gradient problem, we utilize a similar idea in our spatial module. With a concatenation between different levels of layers, the block can not only extract more abstracted representations of the demand matrix in a deep layer but also consider context information connected through different layers from the sparse input as the number of orders to the compact spatial relationships among different stations. More details are shown in Figure 4 and the process $\mathcal{F}_{s}$ can be denoted as

where $X_{0}\in\mathbb{R}^{c_{0}\times i\times j}$ denotes the input of a ResUnit. $X_{1}\in\mathbb{R}^{c_{1}\times i\times j}$ and $X_{2}\in\mathbb{R}^{c_{2}\times i\times j}$ are the outputs of the first and second convolutional layers in the ResUnit respectively. $X_{3}\in\mathbb{R}^{c_{3}\times i\times j}$ represents the output of the ResUnit. The $f(\cdot)$ denotes the non-linear activation function like $ReLU$. $W_{1}$, $b_{1}$, $W_{2}$, and $b_{2}$ represent the weights and biases of the first and second convolutional layers in the ResUnit separately.

To further consider that matrices in each sequential data serves different roles based on their indexes, we create multiple independent Conv Blocks with the same structure and each of the block is responsible for one corresponding demand matrix. We denote the process as

where $M^{l}\in\mathbb{R}^{2\times i\times j}$ is the two-channel demand matrix as original input on time interval $l$ and $ConvM^{l}\in\mathbb{R}^{c\times i\times j}$ is the output from $M^{l}$ operated by the Conv Block $\mathcal{F}_{s}^{l}$. $l$ represents the index of both sequential inputs and Conv Blocks, and $L$ denotes the length of the input sequence. Therefore, the number of different convolutional blocks is equal to the number of intervals in a sequential input. Each block captures the discriminative information hidden in the indexes of the data.

After the convolutional operation, we apply flatten layers to transform $ConvM^{l}$ that outputs from Conv Block $\mathcal{F}_{s}^{l}$ to a feature vector $\alpha_{l}\in\mathbb{R}^{cij}$, where $c$ is the number of channels of the output matrix. The whole output $S_{t}\in\mathbb{R}^{l\times cij}$ represents all features extracted from temporal demand matrices separately, which can be denoted as:

Since the transportation data is a type of time series, we apply the temporal module to capture the temporal dependence of the sequential demand matrices. In the task of sequence learning, Recurrent Neural Networks (RNN) have achieved good results (Sutskever, Vinyals, and Le 2014). The incorporation of Long Short-Term Memory (LSTM) overcomes the shortage of traditional recurrent networks that learning long-term dependencies is difficult (Informatik et al. 2003). Some previous works (Qiu et al. 2019; Yao et al. 2018) have proved the great performance of LSTM in processing traffic sequential data. To follow them, we apply the LSTM network for the BSS sequential data in our temporal module.

Briefly speaking, LSTM maintains a memory cell $c_{t}$ to accumulate the previous sequence information. Specifically, at time $t$, given an input $x_{t}$, the LSTM uses an input gate $i_{t}$ and a forget gate $f_{t}$ to update its memory cell $c_{t}$, and uses an output gate $o_{t}$ to control the hidden state $h_{t}$. The formulation is defined as follows:

where $\circ$ denotes the Hadamard product, and $\sigma$ represents the sigmoid function. $W_{\alpha\beta},b_{\alpha\beta}(\alpha\in(i,h),\beta\in(i,f,g,o))$ are the learnable parameters of the LSTM while $c_{t-1}$ and $h_{t-1}$ are the memory cell state and the hidden state at time $t-1$. Please refer to (Hochreiter and Schmidhuber 1997; Informatik et al. 2003) for more details.

In our model, the LSTM net takes $S_{t}$ as input, which is the output of the spatial module. We use $\beta^{t}\in\mathbb{R}^{d}$ to represent the output of the LSTM net in our temporal module.

Though the sequential demand data of BSS holds a kind of trend during the day, their changes will vary according to different time intervals. Therefore, we propose a dynamic interval module that extracts temporal information from each hour and then apply them to influence the learning strategies of the main spatial-temporal network directly.

To encourage such a learning mode, some meta-learning methods (Bertinetto et al. 2016; Wang et al. 2019) have been proposed to create a siamese-like network in which one network is responsible for generating learning weights for another. Inspired by these advanced works, we also apply a similar network structure to map (time) to be directly the learning weights of the top fully connected layer in the main network.

In our module, for the input number of hours ranging from $0$ to $23$, we first use $GloVe$ (Pennington, Socher, and Manning 2014) to embed the numbers into feature vectors $V_{t}\in\mathbb{R}^{h}$. After that, our Interval Net in the module transforms embedding vectors to features whose dimension is the same as the learnable parameters in the fully connected layer of the main network, including weights and biases. The generated vectors are then directly assigned to be the values in the fully connected layer, and the Dynamic Interval Module participates in the back-propagation process in an end-to-end manner.

However, it is too difficult and too large for parameters in Interval Net to learn, since the parameters space of the Interval Net grows quadratically with the number of the output units. Following (Bertinetto et al. 2016), we construct a factorized representation of the output weights that is decomposed of 2 operating matrices and a diagonal matrix as Figure 5 shows, which is analogous to the Singular Value Decomposition. By this way, the parameters in the Interval Net needed to be learned only grow linearly with the number of output units. The whole process can be formulated as

where $W_{FC}\in\mathbb{R}^{k\times d}$ is the generated weights for the fully connected layer. $W(V)\in\mathbb{R}^{a}$ represents the output vector of the Linear layer $W$ in Interval Net while $diag(\cdot)$ is the diagonal operating to transform the vector $W(V)$ to a diagonal matrix. As a consequence, the net only needs to generate low-dimensional parameters for each time interval. In addition, two matrices $O\in\mathbb{R}^{a\times d}$ and $O^{\prime}\in\mathbb{R}^{k\times a}$, where $k=2\times i\times j$, project $diag(W(V))$ again to keep the same dimension with the fully connected layer.

Similarly, biases of the fully connected layer are also generated as following:

where $b_{FC}$ represents the generated biases for the fully connected layer. $b(V)\in\mathbb{R}^{k}$ denotes the output vector of the linear layer $b$ in Interval Net. After the above operation, we obtain $\langle W_{FC},b_{FC}\rangle$ as the parameters $P$ in Figure 3 of the fully connected layer (FC).

To get the final results, the fully connected layer takes the output of temporal module $\beta^{t}\in\mathbb{R}^{d}$ as input for the time interval $t$. As we mentioned, $P$ consists of the weights $W_{FC}\in\mathbb{R}^{k\times d}$ and biases $b_{FC}\in\mathbb{R}^{k}$ where $k=2\times i\times j$. Therefore, the formulation of the layer can be expressed as follows:

where the $f(\cdot)$ denotes the non-linear activation function of prediction layer. $\hat{M_{t}}\in\mathbb{R}^{k}$ represents the predicted demand matrix of the ground truth $M_{t}$.

In the experiments, we set the length of the input sequence $L$ to 3. In the spatial module, each Conv Block has 2 ResUnits with the same structure. That is, it contains 2 convolutional layers with each layer followed by a batch normalization (BN) (Ioffe and Szegedy 2015) and a residual link. All the convolutional layers in the Conv Block have 32 filters. The size of each filter is set to $3\times 3$ with $stride=1$. In the temporal module, the LSTM net has 1 hidden layer with 1024 neurons. The activation functions used in the fully connected layer and Conv Blocks are $ReLU$ while $LeakyReLU$ is used as the activation function at the linear layers in the dynamic interval module. We optimize our model via Adam (Kingma and Ba 2014) optimization by minimizing the Mean Squared Error (MSE) loss between the predicted result and the ground truth. The learning rate and the weight decay are set to $10^{-3}$ and 5e-5 respectively. For the training data, 90% of it is for training and the remaining 10% is chosen as a validation set for early-stop. We implement our network with Pytorch (Paszke et al. 2019) and train it for 200 epochs on 2 NVIDIA 1080Ti GPUs.

In the paper, we use the NYC Bike dataset in 2014, from Apr. 1st to Sept. 30th. We treat the data for the last 10 days as the testing data and others as training data. We set one hour as the length of a time interval. The total number of orders and time intervals in the dataset are 5,359,944 and 4,392 respectively. And the number of stations used in the dataset is 128. The dataset can be collected from the website of Citi-Bike system¹¹1https://www.citibikenyc.com/system-data.

We use Rooted Mean Square Error (RMSE) and Mean Absolute Error (MAE) as the metrics to evaluate the performance of our model and the baselines, which are defined as:

where $\hat{y_{i}}$ and ${y_{i}}$ denote the predicted value and ground truth respectively, and ${z}$ is the number of all predicted values.

We compare our STDI-Net with the following seven baselines:

• •

  Historical average (HA): Historical Average (HA) predicts the future demand by averaging the historical demands.

• •

  Auto-regressive integrated moving average (ARIMA): Auto-Regression Integrated Moving Average (ARIMA) is a well-known model used for time series prediction.

• •

  Lasso regression (Lasso): Lasso regression is a linear regression method with $L_{1}$ regularization.

• •

  Ridge regression (Ridge): Ridge regression is a linear regression method with $L_{2}$ regularization.

• •

  Multiple layer perception (MLP): MLP is a neural network with four hidden layers. The number of hidden units are 256, 256, 128, 128 respectively. The MLP predicts the demand matrix $M^{t}$ by taking a sequence of the previous $l$ demand matrix $[M^{t-l},…,M^{t-2},M^{t-1}]$ as input.

• •

  ST-ResNet (Zhang, Zheng, and Qi 2017): ST-ResNet is a CNN-based model with residual blocks for traffic prediction, which used multiple CNN components to extract features from the historical data sequence.

• •

  DMVST-Net (Yao et al. 2018): DMVST-Net is a deep learning model which based on CNN and LSTM for taxi demand prediction. It also contains graph embedding to capture similar demand patterns among regions.

• •

  DeepSTN+ (deepstn+): DeepSTN+ is a deep learning-based convolutional model for crowd flow prediction, which contains long range spatial dependence modeling, POI-based spatial information capturing, and a fusion mechanism for features extracted from different aspects.

Table 1 shows the testing results of our proposed model and baselines on the dataset. We can see that our STDI-Net achieves the lowest RMSE and MAE(4.6339 and 2.1946) among all the competing methods. The HA and ARIMA perform poorly, as they only consider the historical demand values for prediction. Because of the consideration of more context relationships among sequence, the linear regression methods (Lasso and Ridge) perform better than the above two methods. However, they do not extract more spatial-temporal information for prediction. The MLP further extracts features from the sequence and performs better than the above methods. However, the MLP does not model spatial or temporal dependency. The ST-ResNet achieves 5.1249 and 2.7206 for RMSE and MAE which is better than MLP due to the extracting of spatial features. Compared with ST-ResNet, DMVST-Net extracts joint spatial-temporal feature and similar demand patterns among regions, which further improve its performance for prediction. Compared with previous methods, DeepSTN+ explores spatial correlations from different aspects to reduce the prediction error. However, it doesn’t consider about the influence of different time intervals. Our model further contributes a dynamic interval module which further improves the performance.

Our full model consists of three modules for three types of information modeling. To explore the influence of different modules combinations on the task, we combine them and implement the following networks:

• •

  Spatial module + FC: This network contains the spatial module of our proposed model and a fully connected layer. This network only extracts spatial features for prediction.

• •

  Temporal module + FC: This network only uses the temporal module of our proposed model to capture the temporal information, and a fully connected layer is used to output the predicted results.

• •

  Spatial module + Temporal module + FC: This method is the combination of the spatial module, temporal module, and a fully connected layer. In this method, we model joint spatial-temporal information without considering the influence of different time intervals.

• •

  Spatial module + Dynamic Interval module: In this network, we combine the spatial module and the dynamic interval module of our proposed model, to capture spatial information, and the dynamic mappings for different time intervals.

• •

  Temporal module + Dynamic Interval module: For this network, we use the temporal module and the dynamic interval module of our proposed model. This network models the temporal information, and generates the dynamic mappings for different time intervals.

• •

  STDI-Net: Our proposed model, which models joint spatial-temporal information, and generates dynamic mappings for different time intervals.

Table 2 shows the results of the test. The RMSE and MAE of the spatial module + FC are 5.6558 and 2.6218 respectively, while that of the spatial module + dynamic interval module are 4.9077 and 2.3457. The results of the temporal module + FC achieve 5.2614 and 2.3914 while the RMSE and MAE of the temporal module + dynamic interval module are 4.7788 and 2.2582 respectively. We can see that compared with separate spatial or temporal module + fully connected layer, the performance of the combination with the dynamic interval module improves significantly. Furthermore, the spatial module + temporal module + FC achieves the results of 5.0832 and 2.3476, which are worse than that of our complete model. The results show that our dynamic interval module improves the performance significantly.

The above experiments show that our proposed dynamic interval module achieves a good result in the demand prediction of BSS. However, we have not proved the rationality of the parameters-generated mode in the dynamic interval module. Besides, we also need to evaluate the effectiveness of the time-specific convolutional layers in our spatial module. In addition, the advantage of using $GloVe$ need to be proved by comparing with the model that embed time intervals into vectors without the pre-trained $GloVe$. To address these two questions, we construct the following three variants of our proposed model:

• •

  STDI-Net-fusion: In this network, we apply a Linear layer in the Interval Net to transform the interval embedding vector to a feature, and then we concatenate it with the output of the temporal module. After that, a fully connected layer is used to output the predicted results.

• •

  Unified-Spatial Net: This network is the variant of our proposed spatial module, which is used to evaluate the performance of applying the same filters in different temporal indexes. This model Net applies unified filters for each index of the sequence in all convolutional layers, and a fully connected layer is used after convolutional layers. Note that, in the Unified-spatial Net, we use the same Conv Blocks structure as our proposed STDI-Net.

• •

  STDI-Net-embedding: In this model, we apply a learnable embedding layer to embed the hours’ number instead of using the pre-trained $GloVe$ to embed them.

Table 3 shows the results of the above three variants of our model. We can see that our spatial module + FC (5.6558 and 2.6218 for RMSE and MAE) outperforms Unified-Spatial Net (6.1493 and 2.9533 for RMSE and MAE), that means, our proposed time-specific convolution layers perform better than applying same convolutional filters in different temporal indexes. Otherwise, STDI-Net-fusion achieves 4.8149 for RMSE and 2.2995 for MAE, which are worse than our STDI-Net (4.6339 and 2.1946 respectively). Therefore, our parameters-generated mode is better than the fusion way.

Due to applying a trainable embedding layer instead of using a pre-trained model ($GloVe$), the STDI-Net-embedding (4.6154 and 2.1783) has more learnable parameters than STDI-Net (4.6339 and 2.1946). Therefore it can perform better than our STDI-Net. However, its performance has not improved significantly (0.4$\%$ and 0.7$\%$ for RMSE and MAE respectively) with additional parameters. That means, our STDI-Net can perform almost as well as STDI-Net-embedding with less parameters than it. To reduce the number of learnable weights, we apply $GloVe$ to embed hours instead of using an additional embedding layer to embed them.