# Non-Autoregressive Sparse Transformer Networks for Pedestrian Trajectory Prediction
## 3 Methods
### Sparse Spatial Transformer  
The spatial transformer encoder is composed of \(L\) layers, each with a multi-head adaptive sparse self-attention module and a feed forward network. The encoder receives the embeddings of historical trajectory as input and produces a sequence of embeddings of the same dimension. Actually, pedestrians in one frame could be formulated as a directed spatial graph \(G=\left(V^{t},E^{t}\right)\), where each node \(v^{t}_{i}\in V^{t},i\in\{1,\dots,N\}\) corresponds to the \(i\)th pedestrian  
Figure 1: Overview architecture of the proposed Non-autoregressive Sparse Transformer (NaST) networks for pedestrian trajectory prediction. at time \(t\), and the weighted edge \(\left(v_{i}^{t},v_{j}^{t}\right)\in E^{t}\) represents the potential influence from pedestrian \(v_{j}\) to \(v_{i}\) at time \(t\). The spatial relation of pedestrians at each time is modeled as an asymmetric edge weight matrix in this task. It reviews the unequal influence from nodes \(v_{i}\) to \(v_{j}\) and \(v_{j}\) to \(v_{i}\). Therefore, instead of constructing graphs with undirected spatial distances, we introduce relative spatial locations as prior edge feature knowledge of the edge weight matrix at time \(t\) (the superscript \(t\) is omitted for simplification):  
\[e_{ij}=\left\{ \begin{aligned} \varphi\big{(}\big{(}x_{i}-x_{j} \big{)},\big{(}y_{i}-y_{j}\big{)}\big{)},&\ d\big{(}v_{i},v_{j} \big{)}<D\\ 0,&\ d\big{(}v_{i},v_{j}\big{)}\geq D\end{aligned} \right. \tag{1}\]  
where \(d\big{(}v_{i},v_{j}\big{)}\) represents the distance between pedestrians \(i\) and \(j\), and \(D\) is the threshold. \(\varphi(\cdot)\) embeds the relative distance features with a linear transformation. The process of message passing is illustrated in Figure 2. The feature of node \(v_{i}\) is represented as \(h_{i}(\ i=1,\ldots,N)\) at time \(t\). Then, we feed the learnable edge weights \(e_{ij}\) into the spatial transformer to compute the spatial interaction together with the node embedding. Given feature \(h_{i}\) of node \(v_{i}\), we can represent its corresponding query vector as \(Q_{i}=f_{Q}(h_{i})\), its key vector as \(K_{i}=f_{K}(h_{i})\), and its value vector as \(V_{i}=f_{V}(h_{i})\). The self-attention in the original transformer [22] is computed by  
\[\alpha_{ij}^{0}=\frac{Q_{i}K_{j}^{T}}{\sqrt{d_{k}}} \tag{2}\]  
where \(d_{k}\) represents the dimensions of the query vector \(Q_{i}\) and the key vector \(K_{i}\). However, the attention is only computed by the features (the coordinates embedded in the trajectory prediction task) of the node itself. It neglects the interaction from other nodes. In order to consider the directed interactions between nodes, we define the message from nodes \(v_{j}\) to \(v_{i}\) in the directed spatial graph as  
\[\hat{\alpha}_{ij}=\frac{Q_{i}K_{j}^{T}}{\sqrt{d_{k}}}+e_{ij} \tag{3}\]  
where \(d_{k}\) is the dimensions of query vector \(Q_{i}\) and the key vector \(K_{i}\). The self-attention (Equation (2)) in the original transformer can be modified as  
\[\alpha_{ij}=\frac{\exp(\hat{\alpha}_{ij})}{\sum_{n\in N_{i}\cup\{i\}}\exp(\hat {\alpha}_{in})} \tag{4}\]  
where \(N_{i}\) is the neighbor set of the node \(v_{i}\). In this way, \(\alpha_{ij}\) gives the importance weight of neighbor \(j\) to pedestrian \(i\) dynamically via the node feature itself and the spatial relation (edge feature) between the neighbors. Hence, the spatial interaction at time \(t\) can be computed by Equation (4) and represented by the asymmetric attention score matrix \(A_{SI}^{t}\), where its \((i,\ j)-\)th element, and \(\alpha_{ij}\) represents the influence from node \(v_{j}\) to node \(v_{i}\). The \(i-\)th row in the attention matrix \(A_{SI}^{t}\) represents the \(i-\)th pedestrian's initiative relations to others. The \(i-\)th column in \(A_{SI}^{t}\) represents the passive relation from others. Figure 2: The illustration of message passing mechanism in directed spatial graph.