# An LSTM-Based Method Considering History and Real-Time Data for Passenger Flow Prediction
## 3 Materials and Methods  
### Basic Methods  
We choose the Xgboost algorithm [21] to train the best model for each bus line. Xgboost is a boosting tree model, which means this method tries to form several tree models for prediction. The sum of the predicted values of each tree is the predicted value of the sample. The function can be expressed as [21]:  
\[\overline{y}=\phi(x_{i})=\sum_{t=1}^{T}f_{t}(x_{i}) \tag{1}\]  
where \(f_{t}\) is the \(t\)th tree for prediction. The Xgboost algorithm uses the following methods to form the \(t\)th tree. The loss function at the \(t\)th iteration can be expressed as:  
\[L^{(t)}=\sum_{i=1}^{n}l\left(y_{i},y_{i}^{(t-1)}+f_{t}(x_{i})\right)+\Omega(f_{ t}) \tag{2}\]  
where \(x_{i}\) represents sample of data, \(y_{i}\) is the true value of \(x_{i}\), \(y_{i}^{(t-1)}\) is the predicted value of the \((t-1)\)th iteration, and \(f_{t}(x_{i})\) is the model at the \(t\)th iteration. The second term \(\Omega(f_{t})\) penalizes the complexity of the model. Second-order approximation can be used to quickly optimize the objective in the general setting. \[L^{(t)}\simeq\sum_{i=1}^{n}[l(y_{i},\overline{y}_{i}^{(t-1)})+g_{i}f_{t}(x_{i} )+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t}) \tag{3}\]where  
\[g_{i}=\frac{\partial l(y_{i},\overline{y}_{i}^{(t-1)})}{\partial\overline{y}_{i}^ {(t-1)}},\ h_{i}=\frac{\partial^{2}l(y_{i},\overline{y}_{i}^{(t-1)})}{\partial \overline{y}_{i}^{(t-1)}}.\]  
We can remove the constant terms to obtain the following simplified objective at step \(t\). \[L^{(t)}=\sum\limits_{i=1}^{n}[g_{i}f_{i}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{ i})]+\Omega(f_{t}) \tag{4}\]  
Defining \(I_{j}=\{i|x_{i}\in j\}\) as the instance set of leaf \(j\), we can rewrite Equation (4) by expanding \(\Omega(f_{t})\) as follows:  
\[ \begin{array}{ll}L^{(t)}&=\sum\limits_{i=1}^{n}\left[g_{i}f_{t}(x_{i})+ \frac{1}{2}h_{i}f_{t}^{2}(x_{i})\right]+\gamma T+\frac{1}{2}\lambda\sum\limits _{j=1}^{T}w_{j}^{2}\\ &=\sum\limits_{j=1}^{T}\left[(\sum\limits_{i\in I_{j}}g_{i})w_{j}+\frac{1}{2} (\sum\limits_{i\in I_{j}}h_{i}+\lambda)w_{j}^{2}\right]+\gamma T\end{array}  \tag{5}\]  
For a fixed structure \(q(x)\), we can compute the optimal weight \(w_{j}^{*}\) of leaf \(j\) by \(w_{j}^{*}=-\frac{G_{i}}{H_{i}+\lambda}\). Then,  
\[L^{(t)}=-\frac{1}{2}\sum\limits_{j=1}^{T}\frac{G_{i}}{H_{i}+\lambda}+\gamma T\]  
The LSTM [22] is an artificial recurrent neural network (RNN) architecture used in the field of deep learning. Unlike standard feed forward neural networks, the LSTM has a feedback connection. It can not only process a single data point (such as images), but also entire sequences of data (such as speech and video). A common LSTM unit is composed of a cell, an input gate, an output gate, and a forget gate. The cell remembers the values over arbitrary time intervals, and the three gates regulate the flow of the information into and out of the cell. The basic structure of a signal LSTM cell is shown in Figure 1.  
The compact forms of the equations for the forward pass of an LSTM unit with a forget gate are:  
\[i_{t}=\sigma(W_{ix}x_{t}+W_{ih}h_{t-1}+b_{i}) \tag{6}\]  
Figure 1: The basic LSTM cell. \[f_{t}=\sigma\Big{(}W_{fx}x_{t}+W_{fh}h_{t-1}+b_{f}\Big{)} \tag{7}\] \[o_{t}=\sigma(W_{ox}x_{t}+W_{ohl}h_{t-1}+b_{o})\] (8) \[\widetilde{C_{t}}=\tanh(W_{Cx}x_{t}+W_{Ch}h_{t-1}+b_{C})\] (9) \[C_{t}=i_{t}\otimes\widetilde{C_{t}}+f_{t}\otimes C_{t-1}\] (10) \[h_{t}=o_{t}\otimes\tanh(C_{t}) \tag{11}\]  
where \(t\) stands for \(t\)th timestamp. \(i_{t}\) refers to the output of the input gate. \(f_{t}\) refers to the output of forget gate, and \(o_{t}\) is the output of output gate. \(x_{t}\) is the input vector. \(C_{t}\) is the state vector, and \(h_{t}\) is the hidden vector. \(h_{t-1}\) is the former output of \(h_{t}\), and \(C_{t}\) is the input state and output state of memory cell. \(\sigma\) and \(\tanh\) are activation functions between different layers. \(\otimes\) is the Hadamard product. Other variables like \(W_{ix}\), \(W_{ih},b_{i}\) are needed to be solved by minimizing the loss function.