# A Spatial-Temporal-Semantic Neural Network Algorithm for Location Prediction on Moving Objects
## 3 Methodology
### Long Short-Term Memory Network Model for Location Prediction  
#### 3.2.1 Model Description  
The recurrent neural networks can handle sequential data and have become a hot spot in the fields of machine learning [22; 27]. They are networks with loops of several hidden layers that can change monotonously along with the position in a sequence, as shown in Figure 10a. It enables RNN to learn sequential data and [PERSON] [23] has utilized RNN in location prediction with check-in data. Figure 10 shows the structure of RNN. \(\mathbf{x}\) is the vector of the value of the input layer. \(\mathbf{s}\) represents the value of the hidden layer and \(\mathbf{o}\) is the value of the output layer. \(U\), \(V\) are the weight matrix between \(\mathbf{x}\) and \(\mathbf{s}\), \(\mathbf{s}\) and \(\mathbf{o}\). \(W\) is the weight matrix between the value of the hidden layer at time \(t-1\) and time \(t\). The RNN can be expressed as Equations (5) and (6), where \(g\) and \(f\) are the activation functions. The output of the RNN, namely \(o_{t}\), is affected by the input \(x_{t},\ x_{t-1},\ \ldots,x_{1}\). This is the reason why the RNN can take advantage of historical sequential data. Moreover, parameters in the RNN can be further learned with the back propagation through time (BPTT) algorithm [28]. The error term \(\delta_{k}^{T}\) during the weight gradient computing has the property shown in Equation (7), where \(t-k\) is the time interval between the current time and historical time. Other parameters is introduced in [29]. When \(t-k\) is large (locations that are long time ago), the value of \(\delta_{k}^{T}\) will grows or shrinks very quickly (depending on \(\beta\) greater or less than 1). This may cause the learning problems described in [29]. \[s_{t}=f(Ux_{t}+Ws_{t-1}) \tag{5}\]  
Figure 10: The structure of the RNN. Figure 9: A running example of the spatial-temporal-semantic feature extraction. (**a**) The blue dots are the original trajectory. The red dots is the track points after temporal matching. (**b**) The red dots are the location sequences after the geographical and semantic feature matching. \[ \begin{array}{rl}o_{t}&=g(Vs_{t})\\ &=Vf(Ux_{t}+Ws_{t-1})\\ &=Vf(Ux_{t}+Wf(Ux_{t-1}+Ws_{t-2}))\\ &=Vf(Ux_{t}+Wf(Ux_{t-1}+Wf(Ux_{t-2}+\ldots)))\\ \\ &\|\delta_{t}^{T}\|\leq\|\delta_{t}^{T}\|\prod\limits_{i=k}^{t-1}\|W\|\|diag[f ^{\prime}(net_{i})]\|\\ &\leq\|\delta_{t}^{T}\|\left(\beta W\beta_{f}\right)^{t-k}\end{array}  \tag{7}\]  
However, location sequences generated by the STS feature extraction could be very long. The RNN may not perform with long sequences. Long short-term memory networks (LSTMs) are a special kind of RNN, capable of learning information for long periods of time [30]. Instead of the simple \(tan\)\(h\) hidden layer in RNN, LSTM has a more complicated repeating module, as shown in Figure 11. The LSTM uses gates to control the cell states passed from long time ago. The gate is a full connection layer expressed as \(g(\mathbf{x})=\sigma(W\mathbf{x}+\mathbf{b})\), where \(W\) is the weight vector and \(\mathbf{b}\) is the bias. \(\sigma\) is the sigmoid function so that the output of the gate is 0 to 1. LSTM utilizes two gates to control the cell state. The forget gate decides how much information of the last cell state \(\mathbf{c}_{t-1}\) will keep to the current time \(\mathbf{c}_{t}\). The other is the input gate, which decides how much information of the input of the current networks \(\mathbf{x}_{t}\) will keep to cell state \(\mathbf{c}_{t}\). LSTM uses the output gate to control how much information of the cell state \(\mathbf{c}_{t}\) will output to \(\mathbf{h}_{t}\). The expression of the forget gate is shown in Equation (8), where \(W_{f}\) is the weight matrix and \(\mathbf{b}_{f}\) is the bias of the forget gate. Similar calculations can be used in the input gate and output gate, as shown in Equations (9) and (12). The cell state of the current input \(\widetilde{\mathbf{c}}_{t}\) is calculated by the last output and the current input, as shown in Equation (10).