# Predictive Business Process Monitoring Approach Based on Hierarchical Transformer
## 3 Preliminaries and Methods
### Transformer  
Transformer was originally a Seq2 Seq model for machine translation tasks, which uses a self-attention mechanism to compute the correlation between words within an input sentence and extract the most important parts of the input sentence for the prediction target [12]. In recent years, Transformer has been widely used for a variety of tasks beyond machine translation and has achieved good results, especially in tasks related to time series analysis.  
Typically, the input to the Transformer is a sequence \(\mathbf{X}=\langle x_{1},x_{2},\cdots,x_{n}\rangle\), where \(x_{i}\) (\(1\leq i\leq n\)) denotes the \(i\)-th element in the sequence, and \(n\) denotes the length of the sequence. For example, in a natural language processing task such as machine translation, \(\mathbf{X}\) is a sentence composed of a series of words; in a time series analysis task, \(\mathbf{X}\) is a time series composed of a series of elements. In deep neural network models such as Transformer, each input element is represented by using a numerical vector. Formally, the input sequence can be represented as \(\mathbf{X}=(\mathbf{x}_{1},\mathbf{x}_{2},\cdots,\mathbf{x}_{n})^{T}\in\mathbb{R }^{n\times d}\), where \(\mathbf{x}_{i}\) is the vector representation of element \(x_{i}\), and \(d\) is the vector dimension. The Transformer's self-attention mechanism is shown in the following Equations (5) and (6).  
\[SelfAtt(\mathbf{Q},\mathbf{K},\mathbf{V})=softmax\bigg{(}\frac{\mathbf{Q}\mathbf{K}^{T}}{\sqrt{d^{ (K)}}}\bigg{)}\mathbf{V}, \tag{5}\]  
\[\mathbf{Q}=\mathbf{X}\mathbf{W}^{(\mathbb{Q})},\ \mathbf{K}=\mathbf{X}\mathbf{W}^{(K)},\ \mathbf{V}=\mathbf{X}\mathbf{W}^{(V)}\, \tag{6}\]  
where \(\mathbf{Q}\in\mathbb{R}^{n\times d^{(\mathbb{Q})}},\mathbf{K}\in\mathbb{R}^{n\times d ^{(K)}}\), and \(\mathbf{V}\in\mathbb{R}^{n\times d^{(V)}}\) are the original input after multiplying with matrices \(\mathbf{W}^{(\mathbb{Q})}\in\mathbb{R}^{d\times d^{(\mathbb{Q})}}\), \(\mathbf{W}^{(K)}\in\mathbb{R}^{d\times d^{(K)}}\) and \(\mathbf{W}^{(V)}\in\mathbb{R}^{d\times d^{(V)}}\) and are also known as the query matrix, the key matrix, and the value matrix, respectively. \(\sqrt{d^{(K)}}\) acts as a scaling factor.  
Due to the limited capability of modeling a single self-attention, multiple self-attention is usually calculated independently in Transformer, and the results are concatenated, which in turn forms a multi-head self-attention, calculated as shown in the following Equations (7) and (8).  
\[MultiHead(\mathbf{X})=\Big{(}head_{1}\bigoplus head_{2}\bigoplus\cdots\bigoplus head _{k}\Big{)}\mathbf{W}^{(\mathbb{O})} \tag{7}\]  
\[head_{i}=SelfAttn\Big{(}\mathbf{X}\mathbf{W}_{i}^{(\mathbb{Q})},\mathbf{X}\mathbf{W}_{i}^{(K) },\mathbf{X}\mathbf{W}_{i}^{(V)}\Big{)} \tag{8}\]  
After that, the Transformer integrates the multi-head self-attention encoding with the original encoding of the input sequence using residual concatenation. Then, we obtain the final encoding of the input sequence \(\mathbf{X}^{\prime}\) using Layer Normalization and a position-wise Feed-Forward Network, calculated as shown in the following Equations (9)-(11).  
\[\mathbf{X}^{\prime}=FFN\big{(}\mathbf{H}^{\prime}\big{)}=ReLU\Big{(}\mathbf{H}^{\prime} \mathbf{W}^{(1)}+b^{(1)}\Big{)}\mathbf{W}^{(2)}+\mathbf{b}^{(2)} \tag{9}\]  
\[\mathbf{H}^{\prime}=LayerNorm(FFN(\mathbf{H})+\mathbf{H}) \tag{10}\]  
\[\mathbf{H}=LayerNorm(MultiHead(\mathbf{X})+\mathbf{X}) \tag{11}\]  
The \(\mathbf{X}^{\prime}\) in Equation (9) can be used as a feature representation of the input sequence, which can subsequently be fed into the task-related network structure to complete the prediction target. The overall calculation cost of the Transformer model consists mostly of computing the attention matrix \(\mathbf{Q}\mathbf{K}^{T}\) in Equation (5), and its time complexity is \(\mathbf{O}\left(n^{2}\right)\), which makes the Transformer model less efficient when dealing with long sequences.