Surprisal Driven $k$-NN for Robust and Interpretable Nonparametric Learning

Anomaly detection, also known as outlier detection, is a field in data analysis and machine learning that focuses on identifying instances that deviate significantly from the expected behavior of a given dataset. In recent years, the utilization of anomaly detection techniques has expanded across a diverse range of domains. These methods have found application in detecting fraudulent activities within credit cards, insurance, and healthcare sectors, as well as identifying intrusions in cyber-security, pinpointing faults in safety-critical systems, etc. Some of the well known methods for anomaly detection for tabular data include (Liu et al., 2008; Li et al., 2022; He et al., 2003; Li et al., 2003; Breunig et al., 2000) and (Ruff et al., 2018). Traditional methods like Isolation Forests randomly select features and split points to recursively partition data points into subsets, marking path lengths that effectively ’isolate’ a datapoint as anomalies. This approach is an ensemble method. Isolation Forests assume that anomalies are sparse and can be isolated easily. If the dataset contains clusters of anomalies that are not well-separated from normal instances, the algorithm’s performance may suffer. There are probabilistic methods such as ECOD (Unsupervised Outlier Detection Using Empirical Cumulative Distribution Functions) uses empirical distribution functions to sort the data points and assigns probabilities based on their order. CBLOF (Clustering-Based Local Outlier Factor) assesses the local density deviation of a data point with respect to its neighbors to identify outliers and is a proximity based outlier detection method. While ECOD performs well with unimodal distribution data, it is sensitive to feature dimension noise and may encounter difficulties in accurately identifying outliers in datasets with multiple modes. Additionally, it may face challenges in high-dimensional scenarios, as it focuses on one-dimensional projections. CBLOF on the other hand focuses on local clusters, potentially missing the global context of the dataset. It necessitates a priori specification of the cluster number, posing a challenge. Unevenly sized clusters may impede its ability to distinguish between normal and outlier instances, particularly within smaller clusters. Recently there have been deep learning based approaches such as DeepSVDD which projects high-dimensional data into a latent space using an autoencoder architecture. Anomalies are detected by measuring the distance of data points to the center of a constructed hypersphere in the latent space, employing a threshold to flag anomalous cases based on this distance. These methods relying on training deep neural networks may exhibit sensitivity to noisy labels when mislabeled instances are present in the training data. This sensitivity can have adverse effects on the model’s generalization and its accuracy in detecting outliers. Additionally, these approaches often lack interpretability, making it challenging to understand the rationale behind classifying certain instances as outliers. Furthermore, their performance is often contingent on the careful tuning of hyperparameters within the neural network.

Like many other approaches to $k$-NN, we use Minkowski distance as a starting point

where $p$ is the parameter for the Lebesgue space, $\Xi$ is the feature set, and $w_{i}$ is the weight for each feature. One problem with this distance metric, however, is that distinguishing points becomes more and more difficult in higher dimensions. One proposed solution is to use a fractional norm heading towards zero to enable points to be distinguished more easily in high dimensional space (Aggarwal et al., 2001). Motivated by this, we derived the Minkowski distance as $p\rightarrow 0$ expressed over the feature set $\Xi$

assuming that the weights $w$ sum to 1.

The above is a geometric mean, which has the useful property of being scale invariant. This derivation presents a problem, however. If any of the differences are zero, the entire distance metric will become zero. In order to solve this problem, we use the Łukaszyk–Karmowski metric as a distance term rather than absolute error. Given two random variables $X$ and $Y$ with probability density functions $f(x)$ and $g(x)$ respectively, the LK metric is defined as

We assume that if both points (say $x$ and $y$) are near enough to be worth determining the distance between them, then the distributions and parameters for the probability density functions should represent the local data. The two simple maximum entropy distributions on $(-\infty,\infty)$ given a point and a distance around the point are the Laplace distribution (double exponential), where the distance is represented as mean absolute error (MAE), and the Gaussian distribution (normal), where the distance is represented as the standard deviation. We choose the Laplace distribution and derive a closed-form solution of equation 3 for it. Letting $\mu\equiv|x-y|$ and with $b$ being the expected deviation,

the full derivation of which can be found in the appendix.

In order to employ this measure for our method, we need a value for $b$. Measurement error may not always be readily available, and it does not take into account the additional error among the relationships within the model. Hence, residuals are calculated for each prediction. The MAE is be calculated for each observation using a leave-one-out approach, where instances are removed from the model and each of the held out instance’s features are predicted using the rest of the data. (The idea is to quantify the uncertainty in the model). These errors can be locally aggregated or can be aggregated across the entire model to obtain the expected residual, $r$, for predicting each feature, $i$, as $r_{i}$. This results in a Minkowski distance metric which uses the derived distance term of

We have found that using the residuals in the $k$-NN system with the above distance metric, calculating new residuals, and then feeding these back in, generally yields convergence of the residual values with notable convergence after only 3 or 4 iterations. Measuring a distance value for each feature further enables parameterization regarding the type of data a feature holds. For example, nominal data can result in a distance of 1 if the values are not equal and 0 if they are equal. Thus, one-hot encoding, the expansion of nominal values into multiple features, is not needed. Ordinal data can use a distance of 1 between each ordinal type.

Having established a distance metric, we can determine distances between points, but the units of measurement and scales of each feature may be entirely different. We propose Inverse Residual Weighting (IRW), a maximum entropy method of transforming these each feature difference into surprisal space so that the entire distance itself becomes expected surprisal.

Using our assumption that absolute prediction residuals follow the exponential distribution where the mean value is the feature residual, we can describe the probability a single prediction residual, $v$, being within the feature residual, $r$ as

It then follows that the probability of the prediction residual being outside the feature residual is

and the surprisal of observing the prediction residual larger than the feature residual is

expanded as

In light of this, we observe that to find the surprisal of an observed residual, we can simply divide by the feature residual. This is the motivation for using IRW, where the inverse of feature residuals are used for feature weights when computing distances.

As previously described, we are able to compute a residual for each feature as the mean absolute deviation between the observed values and predicted values for the feature. We can express the feature residual $r_{i}$ as

where $x_{i,j}$ represents the $i^{th}$ feature value of case $x_{j}$ and $\hat{x}_{i,j}$ represents the prediction for that specific value. Then this feature residual can be used to determine feature weights, $w_{i}$, which can then be expressed as

Using the inverse of the residual as the weight for each feature allows the distance contributed by each feature to be in the same space as one another. This gives the distance function scale invariance across varying feature types and scales, which solves one common challenge of using nearest neighbors approaches. Additionally, using IRW allows the model to emphasize features with strong relationships and reduce the influence features that appear to be significantly noisy or generally unpredictable. For models with a designated target feature, feature weights can further augmented using Mean Decrease in Accuracy (MDA) or similar techniques that attempt to capture the predictive power of a feature. Additionally, we are actively researching methods of incorporating MDA techniques alongside IRW in targetless applications of our methods.

Furthermore, scaling by the inverse residual feature weights enables the system to interpret distances in surprisal space. Being in surprisal space allows us to utilize a maximum entropy assumption and the Laplace distribution to measure observed residuals in terms of surprisal. These surprisal values can then be utilized for various metrics and downstream tasks. Specifically we use these surprisal values to compute surprisal ratios that we refer to as convictions, which is covered in detail in the concepts section.

The distance contribution reflects how much distance a point contributes to a graph connecting the nearest neighbors, which is the inverse of the density of points over a unit of distance in the Lebesgue space. The harmonic mean of the distance contribution reflects the inverse of the inverse distance weighting often employed with $k$-NN, though other techniques may be substituted if inverse distance weighting is not employed. We define the distance contribution as:

where $X_{k}$ is the set of nearest neighbors to point $x$ and $d$ is the distance function. This is a harmonic mean over the distances to each nearest neighbor. Note that the properties of the previously defined distance metric are useful here to prevent divisions by zero.

We can quantify the information needed to express a distance contribution $\phi(x)$ by transforming it into a probability. We begin by selecting the exponential distribution to describe the distribution of residuals as it is the maximum entropy distribution constrained by the first moment. We represent this in typical nomenclature for the exponential distribution using $p$ norms.

We can directly compare the distance contribution and p-normed magnitude of the residual. This is because the distance contribution and the norm of the residual are both on the same scale, with the distance contribution being the expected distance of new information that the point adds to the model, and the norm of the residual is the expected distance of deviation. Given the entropy maximizing assumption of the exponential distribution of the distances, we can then determine the probability that a distance contribution is greater than or equal to the magnitude of the residual $\|r(x)\|_{p}$ in the form of cumulative residual entropy (Rao et al., 2004) as

We then convert the probability to self-information as

which simplifies to

If we have some form of prior distribution of data given all of the information observed up to that point, the surprisal is the amount of information gained when we observe a new sample, event, case, or state change and update the prior distribution to form a new posterior distribution after the event. The surprisal of an event of observing a random variable $x\sim X$ is defined as $I(x)=-\ln p(x)$. Thus, the conviction, $\pi$, can be expressed as

By computing this ratio for different types of information, we derive several different types of conviction with different uses in various applications: familiarity conviction, similarity conviction, and residual conviction.

We conducted a comprehensive series of experimental comparisons on a diverse set of algorithms. We first perform classification and regression across 308 PMLB datasets (Romano et al., 2021). (146 for classification and 162 for regression) ¹¹1Kindly refer to the appendix for more information on the datasets used and for additional experiments and details.. and compare our approach across gradient boosted trees, traditional $k$-nearest neighbors, logistic regression (for classification), regularized least squares (for regression), neural networks, random forests and Light-GBM. A stratified sampling of data having cells $N\cdot d\leq 400000$ was chosen. To ensure robustness and reliability, each classification and regression experiment was iterated 30 times with varying random seeds, and the resulting metric averages were computed for statistical significance. For classification tasks, we present mean, precision, recall, and Matthews Correlation Coefficient (MCC) as evaluation metrics. In regression, Mean $R^{2}$, mean absolute error (MAE), mean square error (MSE) and Spearman coefficient were calculated. The consolidated results are detailed in Table 1 and Table 2, providing a comparative perspective against a diverse set of algorithms. It is worth noting that our proposed method consistently outperforms all other classification algorithms in terms of accuracy and precision, while also demonstrating competitive results in regression.

Using the defined conviction metrics, we can judge whether or not a data point is an anomaly on a standardized scale. To evaluate the the accuracy of this method, we present results on anomaly detection on 20 datasets from Outlier Detection Datasets (ODDS) ²²2Kindly refer to the appendix for dataset related details. (Rayana, 2016). These datasets have ground truth labels indicating which data points are anomalous, which makes them ideal for this analysis. We utilize the previously established method of evaluating the conviction values of each point and compare to the results of using many of the popular anomaly detection methods as shown in Table 3. Specifically, we trained our model by splitting our dataset into two parts (train and test). The training set comprised solely of inliers, and a test set encompassing both inliers and outliers, with a notable prevalence of inliers. Since the ODDS dataset has ground truth labels for both inliers and outliers, we used the ground truth labels to compute F1 scores to measure the performance of the anomaly detection benchmark routine. For our methods, we simply computed the conviction (similarity conviction or familiarity conviction) and compared it to a threshold of 0.7. If the conviction fell below the threshold, then it was classified as an anomaly. In practice we would recommend tuning this threshold per dataset, but here we show that picking a conviction level of 0.7 for all datasets (wihout choosing it in a dataset specific manner), our method achieves the highest $F1$ scores in 12 of the 20 datasets, surpassing the performance of all other outlier detection methods.

In Table 3, we show the average F1 score for each method across the 20 ODDS datasets. To see the results per dataset, please refer to the appendix.

It is worth noting that certain methodologies, such as CBLOF (Clustering-Based Local Outlier Factor), LOF (Local Outlier Factor), and ECOD (Extended Connectivity-Based Outlier Detection) usually incorporate a distinct partition exclusively composed of inliers during the training phase. Though this is not necessary, these methods can benefit from inlier-based training partitions. In contrast, our approach which harnesses the notion of familiarity conviction, allows us the capability to identify anomalies without necessitating an explicit ‘inlier’ dataset. This innovation enables us to gauge the uncertainty inherent in our model and promptly identify anomalous instances in a real-time manner.

We demonstrate this on a toy dataset as shown in Figure 1.

Consider a toy training dataset $D$ in Figure 1 which is sampled from a random variable $X\sim\mathcal{N}(0,\Sigma^{2})$ and we observe two points $(x_{1},y_{1})$ (blue) and $(x_{2},y_{2})$ (green) within the data. Given this data, familiarity conviction allows us to measure how close a point is to existing data. Using our notion of surprisal, we can observe that $(x_{2},y_{2})$ has high surprisal and therefore low conviction. Moreover, the distance contribution is higher than the mean distance contribution of the entire dataset. This allows for us to detect it as anomalous without having requirement of a separate inlier partition.