# Map Matching Based on Seq2 Seq with Topology Information
## 3 Model Design  
In [PERSON]'s work [15], a unidirectional LSTM (Long short-term memory) was used as the recurrent neural network for state transfer in seq2 seq. Although LSTM has slightly higher accuracy in processing large-scale data, it is extremely time consuming. Related experiments have shown that in situations where the data volume is moderately large, the effect of GRU is comparable to that of LSTM, and it has the advantage of faster processing time. The structure of GRU is shown in Figure 5.  
The GRU uses a reset gate to control the amount of data in the current and memory information. It uses an update gate to calculate the output of the current hidden state, generating new memory information to continue forward propagation. The relevant mathematical formulas are shown in Equations (3)-(6).  
\[z_{t}=\sigma(W_{z}x_{t}+U_{z}h_{t-1}).\]  
Figure 5: GRU structure diagram.  
\[r_{t}=\sigma(W_{z}x_{t}+U_{z}h_{t-1}+b_{z}). \tag{4}\]  
\[\stackrel{{\sim}}{{h}}=\tan h(WX_{t}+r_{t}Ulh_{t-1}+b_{h}). \tag{5}\]  
\[h_{t}=(1-z_{t})h_{t}+z_{T}h_{t-1}, \tag{6}\]  
where \(h_{t-1}\) is the hidden layer of the previous time, \(x_{t}\) is the current input, and the output is the hidden layer information \(h_{t}\) of the current time. \(r_{t}\) is the reset gate, used to calculate the candidate hidden layer \(\stackrel{{\sim}}{{h}}\), in order to retain how much \(h_{t-1}\) information. \(z_{t}\) is the update gate, which is used to control how much \(\stackrel{{\sim}}{{h}}\) information is added to get the output \(h_{t}\).  
In this paper, Bi-GRU is used to transfer the state of model coding phase. Its main feature is that it can absorb historical and future information, so as to capture information of a complete trajectory sequence. The structure of Bi-GRU is shown in Figure 6. In the Figure 6, FD represents the last GRU unit of forward propagation, and BD represents the last GRU unit of backward propagation.  
In addition, in order to enhance the ability of the model to capture the dependency between noisy trajectories and real road network trajectories, this article applies the Bahdanau [18] attention mechanism, as shown in Figure 7.  
Figure 6: Bi-GRU Structure Diagram.  
First, a weight coefficient \(\alpha_{ij}\) is generated for each hidden state \(h_{j}\). The weight coefficients are then subjected to a Softmax operation to obtain the attention weights \(\alpha_{ij}\) for each hidden state. The attention vector context is obtained by calculating the weighted sum of the attention weights and each hidden state. Finally, the attention vector is integrated with a fully connected layer to form the output value. The calculation process is shown in Equations (7)-(9).  
\[e_{t,j}=a\big{(}s_{t-1},h_{j}\big{)}. \tag{7}\]  
\[\alpha_{t,j}=softmax\big{(}e_{t,j}\big{)}=\frac{\exp\big{(}e_{t,j}\big{)}}{ \sum_{k=1}^{n}\exp(e_{tk})}. \tag{8}\]  
\[context=\sum_{t=1}^{T}(\alpha_{t,j}s_{t}). \tag{9}\]  
The final output value will be calculated using a Softmax function to obtain a probability matrix for the grid. The highest probability value for each grid will be outputted to form a grid sequence. By converting it to the real coordinates using the dictionary of the road network, the actual trajectory output can be obtained. The overall structure of the algorithmic model is shown in Figure 8.  
Figure 7: Attention structure diagram.