# Improved Anomaly Detection by Using the Attention-Based Isolation Forest
## 4 Attention-Based Isolation Forest
### Keys, Values, and Queries in iForests  
First, we can point out that the outcome of each isolation tree is the path length \(h_{k}(\mathbf{x})\), \(k=1,\ldots,n\). This implies that this outcome can be regarded as the value in the attention mechanism. Second, we define the queries and keys in iForest. Suppose that the feature vector \(\mathbf{x}\) falls into the \(i\)-th leaf of the \(k\)-th tree. Let \(\mathcal{J}_{i}^{(k)}\) be a set of indices of \(n_{i}^{(k)}\) training instances \(\mathbf{x}_{j}\) that also fall into the same leaf. The distance between the vector \(\mathbf{x}\) and all vectors \(\mathbf{x}_{j},j\in\mathcal{J}_{i}^{(k)}\), shows how the vector \(\mathbf{x}\) is in agreement with the corresponding vectors \(\mathbf{x}_{j}\) and how close it is to the vectors \(\mathbf{x}_{j}\) from the same leaf. If the distance is small, then we can conclude that the vector \(\mathbf{x}\) is well performed by the \(k\)-th tree. The distance between the vector \(\mathbf{x}\) and all vectors \(\mathbf{x}_{j},j\in\mathcal{J}_{i}^{(k)}\), can be represented as a distance between the vector \(\mathbf{x}\) and the mean values of all vectors \(\mathbf{x}_{j}\) with indices \(j\in\mathcal{J}_{i}^{(k)}\). The mean vector of \(\mathbf{x}_{j}\) with indices \(j\in\mathcal{J}_{i}^{(k)}\) can be viewed as a characteristic of the corresponding path, i.e., this vector characterizes a group of instances that fall into the corresponding leaf. Hence, the mean vector shows how the vector \(\mathbf{x}\) is in agreement with this group. If we denote the mean value of \(\mathbf{x}_{j},j\in\mathcal{J}_{i}^{(k)}\) as \(\mathbf{A}_{k}(\mathbf{x})\), then it holds that  
\[\mathbf{A}_{k}(\mathbf{x})=\frac{1}{n_{i}^{(k)}}\sum_{j\in\mathcal{J}_{i}^{(k) }}\mathbf{x}_{j}. \tag{7}\]  
We omit the index \(j\) in \(\mathbf{A}_{k}(\mathbf{x})\) because the instance \(\mathbf{x}\) can fall only into one leaf of each tree. The vectors \(\mathbf{A}_{k}(\mathbf{x})\) and \(\mathbf{x}\) can be regarded as the key and the query, respectively. Then, (6) can be rewritten by using the attention weights \(\alpha(\mathbf{x},\mathbf{A}_{k}(\mathbf{x}),\mathbf{w})\) as follows:  
\[E[h(\mathbf{x})]=\sum_{k=1}^{T}\alpha(\mathbf{x},\mathbf{A}_{k}(\mathbf{x}), \mathbf{w})\cdot h_{k}(\mathbf{x}), \tag{8}\]where \(\alpha(\mathbf{x},\mathbf{A}_{k}(\mathbf{x}),\mathbf{w})\) conforms with the relevance of the \"mean instance\" \(\mathbf{A}_{k}(\mathbf{x})\) for the vector \(\mathbf{x}\) and satisfies the following condition:  
\[\sum_{k=1}^{T}\alpha(\mathbf{x},\mathbf{A}_{k}(\mathbf{x}),\mathbf{w})=1,\ \alpha( \mathbf{x},\mathbf{A}_{k}(\mathbf{x}),\mathbf{w})\geq 0,\ k=1,\ldots,T. \tag{9}\]  
We replaced the expected path length (6) with the weighted sum of path lengths (8) such that the weights \(\alpha\) depend on \(\mathbf{x}\), the mean vector \(\mathbf{A}_{k}(\mathbf{x})\), and the vector of parameters \(\mathbf{w}\). The vector \(\mathbf{w}\) in the attention weights represents the trainable attention parameters. Their values depend on the dataset and on the isolation tree's properties. If we return to the Nadaraya-Watson kernel regression model, then the expected path length \(E[h(\mathbf{x})]\) can be viewed as the regression output, and the path lengths \(h_{k}(\mathbf{x})\) of all trees for query \(\mathbf{x}\) are predictions (values in terms of the attention mechanism [26]). Suppose that the trainable parameters \(\mathbf{w}\) belong to a set \(\mathcal{W}\). Then, they can be found by solving the following optimization problem:  
\[\mathbf{w}_{opt}=\arg\min_{\mathbf{w}\in\mathcal{W}}\ \sum_{s=1}^{n}L(E[h( \mathbf{x}_{s})],\mathbf{x}_{s},\mathbf{w}). \tag{10}\]  
Here, \(L(E[h(\mathbf{x}_{s})],\mathbf{x}_{s},\mathbf{w})\) is the loss function, whose definition, as well as the definition of \(\alpha(\mathbf{x},\mathbf{A}_{k}(\mathbf{x}),\mathbf{w})\), is the next task. A general scheme of ABIForest is shown in Figure 1. The red branches show the paths of an anomalous instance \(\mathbf{x}\) that falls into the corresponding red leaves.