A Characteristic Function for Shapley-Value-Based Attribution of Anomaly Scores
Authors: Naoya Takeishi
Yoshinobu Kawahara
Venue: Accepted by TMLR ()

Abstract: In anomaly detection, the degree of irregularity is often summarized as a real-valued anomaly score. We address the problem of attributing such anomaly scores to input features for interpreting the results of anomaly detection. We particularly investigate the use of the Shapley value for attributing anomaly scores of semi-supervised detection methods. We propose a characteristic function specifically designed for attributing anomaly scores. The idea is to approximate the absence of some features by locally minimizing the anomaly score with regard to the to-be-absent features. We examine the applicability of the proposed characteristic function and other general approaches for interpreting anomaly scores on multiple datasets and multiple anomaly detection methods. The results indicate the potential utility of the attribution methods including the proposed one.

Published in Transactions on Machine Learning Research (07/2023)
A Characteristic Function for Shapley-Value-Basee Attribution of Anomaly Scores
Naoya Takeishi
ntakee@gj.ec..utoooooo....
The University of Tokyo
RIKEN Center for Advanced Intelligence Project
Kawahara Yoshinobu
kawaharn Cistt osttaaaaa.nttttoooooooa.u ac.jp
Osaka University
RIKEN Center for Advanced Intelligence Project
Reviewed on OpenReview: https: // openreview. net/ pet/ffrum? id= eLXbXrajXh
Abstract
In anomaly detection, the degree of irregularity is often summarized as a real-valued anomaly score. We address the problem of attributing such anomaly scores to input features for inter- preting the results of anomaly detection. We particularly investigate the use of the Shapley value for attributing anomaly scores of semi-supervised detection methods. We propose a characteristic function specifically designed for attributing anomaly scores. The idea is to approximate the absence of some features by locally minimizing the anomaly score with regard to the to-be-absent. features. We examine the applicability of the proposed charac- teristic function and other general approaches for interpreting anomaly scores multiple datasets and multiple anomaly detection methods. The results indicate the potential utility of the at tributiion methods hods including the proposed one.
1 Introduction
Anomaly detection has been one of the major tasks of machine learning and data mining, and number of different methods have been proposed (see, e.g., (.sadolaa et al.] 2009 Pimentel el. al. 2014). Anomaly localization (or root cause analysis) is a closely related task whose goal is to identify which features are the most responsible for the irrogularity of anomaly-detocted data. is obviously an essential problem in many applications; understanding why specific instances have been considered anomalous is highly valuable for decision-making. Rigorous localization of anomalies possible only with some physical or causal models of gentraenen process (Budhathoki et al. 2022). However, such models are not always available for complex natural and artificial systems, for which -eanning-based anomaly detection often has high demand. Hence, we focus on the latter, that is, the structure-agnostic setting.
We focus on the structure-agnostic interpretation of anomaly detection results, instead of the rigorous anomaly localization based on causal structures. We particularly study methods for post hoc attribution of anomaly scores to input features. Tn recent years, post hoc attribution of machine learning models, not only in anomaly detection but in general, an active arca of study. One of the most popular approaches refers
to the notion of the Shapley value, which has been originally discussed in game theory (Shapley 1953 and
applied machine learning (Lipovetsky 2006; Strumbelj & Kononenko 2014 Datta al. 2016 Lundberg
& Lee 2017 Sundararajan et al. 2017 Owen & Pricur) [017] Ancona et al. 2019 Olsen et al. 2022 It has
also been utilized for anomaly interpretation (Antwarg et al.) 2021 Giurgiu & Schumann, 2019 Takeishi
2019p. These studies have concluded affirmatively on the use of the Shapley value for the interpretation of anomaly detection based on the attribution of anomaly scores.
The previous studies on using the Shapley value for anomaly score attribution adopted general definitions of the characteristic function of the Shapley value. The characteristic function, namely 2d R, is

---

Published in Transactions on Machine Learning Research (07/2023)
set function that represents game's s gain under each coalition of players. In using the Shapley value for attributing machine learning models, it takes a subset of features (and their values) and should return the behavior of the model only with the selected features given as the model's input. Several working definitions of such a characteristic function for general machine learning models have been studied (see, e.g., Lundberg & Lee 2017 Sundararajan & Najmi 2020). However, when comes to applying them to the interpretation of anomaly detection, they do not take into account. the specific nature of anomaly scores, which might limit the utility of the attribution method.
In this paper, propose definition of the characteristic function for the Shapley value particularly for attributing anomaly scores. The idea is to approximate the absence of some features by minimizing an anomaly score in the proximity of the original data point to be interpreted. As the exact computation of such a characteristic function is usually prohibitively time-consuming, we also present practical relaxed definitions. We empirically examine not only the proposed characteristic function but also some existing definitions of the characteristic function by applying them to anomaly scores. We show the results of experiments on synthetic and real anomalies with multiple datasets and anomaly detection methods to discuss the applicability of attribution methods.
2 Background
2.1
Anomaly detection
We focus on the type of anomaly detection methods where some anomaly score computed. Semi-supervised anomaly detection usually falls into this category, where a mechanism to detect anomalies is sought given only normal data. typical solution of semi-supervised anomaly detection consists of two phases (see, e.g., Sections 4, 6, and 7 of Chandola et al., 2009). In the first phase (i.e., the training phase), model, such density estimator, a subspace-based model, and a set of clusters, is learned with the normal data. Then, in the second phase (i.c., the test phase), an anomaly score
e: X -
is computed using the learned model, where æ E X a test data sample in some data space X with d features such as X C Rd or X C 10, The anomaly score, e(x), should indicate a large value when x is anomalous. An alarm is issued if e(z) exceeds some threshold value, eth- Semi-supervise anomaly detection methods are useful in many practices, since they do not assume labeled anomalies and generally do not require storing all the data after the training phasc.
A popular choice of e(x:) is the negative log-likelihod, e(xx) = - log g(ar), where q is some approximation of data's density by models such as Gaussian mixture models (GMMs). Another popular choice is the roconstruction error of dimensionality reduction mothods such as principal component analysis (PCA) or autoencoders, e(x) = |æ ((f()) where f and g are an encoder and a decoder between the data and latent spaces, respectively. Moreover, these two views are not mutually exclusive. For example, Zong et al.) (2018) reported a good detection performance by using both the energy of the latent representations and the reconstruction errors of an autoencoder.
A straightforward way to interpret such anomaly scores is to examine decomposed marginal values of the scores. For example, reconstruction errors in Euclidean space are inherently decomposable into the errors of individual features. We may also refer to the marginal likelihood of each feature if the model admits such decomposition. However, we cannot always compute such quantitics in general; for example, marginal distributions are usually not tractable for nonlinear generative models.
2.2 Attribution with the Shapley value
The Shapley value Shaaley 1953 is a concept solution of coalitional games. Let 2d - R be set function that represents a game's 's gain obtained from each coalition (i.e., subset) of the game's players, and
1 Following the terminology of Chandola al. 2009 synonymous novelty detection (e.g.) Pimentel
2014
2

---

Published in Transactions on Machine Learning Research (07/2023)
let D= ........dddd d) denote the set of all players. This function e is called characteristic function. A game . is defined as a pair (v, D). The Shapley value of (v. D) is to distribute the total gain v(D) to each player in accordance with each one's contribution. The Shapley value of the player i E D, namely di, is the weighted average of the marginal contributions, that is,
ISIi |S| 1)! Σ
Φi =
(i)) -
(1)
d!
SCDVO
where S denotes subset of DV = (1, 1, 1,...,d,, d). and the sum is taken over all the subsets.
The Shapley value has been utilized for interpreting outputs of statistical machine learning (e.g.. Lipovetsky
2006 Strumbelj & Kononenko 2014 Datta et al., 2016; Lundberg & Lee 2017 Sundararajan et al., 2017;
Owen & Pricur 2017 Ancona et al.) 2019) Olsen et al., 2022), where the players of a game mean input Teatures, and the gain of the gare means the out a machine learning model.
Major challenges in utilizing the Shapley value include the following two points:
(i) How to compute the summation for O(2*) terms (i.e., Escoit in Eq. (1)
(1i) How to define a characteristic function v??
The former challenge, the exponential complexity, is a general difficulty and not limited to machine learn- ing interpretation. A common remedy is Monte Carlo approximations (see, e.g., Castro et al. 2017 and
references therein). In this work, we also use Monte Carlo approximation and compute ( using the
reformulation of Eq. 1 as a weighted least squares problem CCaarnes et al. 1988 Lundberg & Lec 2017 7
We will describe its concrete procedures later in Section 3.2
The latter challenge, the definition of v, rises specifically in interpreting machine learning because v(S) should simulate the "absence" of the features not in for a machine learning model. It is, in principle, a question that admits no unique solutions; the most straightforward definition would be based on re-training of models for all subsets of D, which is not realistic in practice. We will see the existing approaches in the next subsection, Section 2.3
2.3 Approaches to defining characteristic function
In the use of the Shapley value for machine learning model attribution in general, characteristic function v has often been defined in either of the following two approaches:
baferencc-based approach replaces the values of "absent." features by some reference values (Sundarara- jan et al., 2017 Lundberg & Lee 2017 Ancona et al. 2019). Suppose x = [ei,...,,,,, xzl E Rd. Let us denote the subvector of æ corresponding to index set S C (1, (1.....d) dd by ag E R RIST. Let 5e = (1,..... 1 be the complement of S. Then, the value of for a machine learning model h RR + Y, where y some output space, is defined the value of h on a sample where æs. is replaced by some reference value rs= RISI, A challenge here is to choose good reference vector rsc. Tse is often set to be zero or average of æse, but there is no unique definition.
Marginalization-basse based approach marginalizes out "absent" features (Strumbel] & Kononenko 2014 Datta et al.) [016 Lundberg & Lee] 2017] Olsen et al. 2022). That is, v is computed as the condi- tional expectation of h(x) given Øs, where Tge is marginalized over some distribution p(zg- xs). A challenge here the computation of the conditional expectation, which intractable in general. Typically, it approximated via nearest neighbors in training data. Mcanwhile, (Sundararajan & Najmi (2020) ar-
gues that the marginalizationn-aas not only the target function h but also the data distribution. If the features are independent, this approach reduces to (the average of) the reference-based one with multiple reference vectors.
approach loses some nice properties as attribution because it depends
Apart from the general point of view, we now brielly review how the Shapley value has been used for attributing anomaly scores. Giurgiu & Schumann (2019) and Antwarg et al. (2021) adopted the reference- basod approach to defining e for anomaly scores. Since good reference voctor r. depends on a query data point æ and a target feature set S, it should be determined adaptively to both and S. However, in Antwarg et al. (201)) the reference does not depend on æ nor in principle. Güurgiu & Schumann 2019) proposed to
3

---

Published in Transactions on Machine Learning Research (07 (07/202) 2023)
e(x:)
e e:
((; = ((='(S;
M
xs
Figure Proposod charactoristic function, v(S:x) in Eq. for attributing an anomaly score e R.
x has d features, which are split into disjoint sets S {1, (1,....00 d} and S fl,...,dd dd)) v(S;æ)) is defined local minimum of e(x) in the proximity of x (i.e., Me) with æş fixed at the original. Although the axes of ag and gee are depicted as one dimension, they are [S|- and |S1-mnnnsioonal in general.
choose reference value adaptively using the influence weights between query data point æ and training dataset. Such reference is adaptive to but not to S, mcaning the same reference value is used for every S. We also note that their method requires storing enough portion of training data, which may be undesirable in some applications of semi-supervised anomaly detection.
Takoishi 20199) adopted the marginalization-based approach to defining for the anomaly score computed with the probabilistic principal component analysis. Because the conditional expectation available for the probabilistie PCA models, the marginalization can be computed exactly. This approach is free from choosing reference value, but the type of applicable anomaly dctection models is obviously restrictive. Morcover, considering conditional distributions under the presence of anomalies is not necessarily meaningful because the learned distribution is no longer reliable for out-of-listribution data points.
3 Anomaly score attribution with the Shapley value
We propose a definition of the characteristic function that takes into account the nature of anomaly scores. We take the reference-based approach; differently from the existing studies, the proposed method determines the reference value, r., adaptively to both æ and and without referring to training data.
3.1 A characteristic function for anomaly scores
Let e X' + R be an anomaly score function that outputs a large value when the input, E Rd, is anomalous. We propose to define characteristic function, which we will denote by v(S; to manifest the dependency æ, for anomaly score as follows. Recall that want to design v(S:z) that simulates the "absence" of the features not in S. In other words, v(S; should represent how anomalous æs is with the remaining features ignored. To this end, we define v(S;z) as the smallest value of the anomaly score, e, achieved in a neighborhood of x with æs being fixed. Rephrasing the idea, v(S;z) is defined as follows:
v(S: ((==((s::)) where (S; = arg min ely) ME C C, ys Fg
The constraint of the optimization, Ma C X, is some compact neighborhood of æ E N. Figure I iillustrats the idea; while æs is fixed at the original value, g. is moved within Ma so that the value of e is minimized.
The characteristic function Eq. (2) enables us examine how e(x) becomes large solely due the features in S. Although falls in the category of reference- basedd characteristic functions, it is different from the general methods in which the absence of features is simulated by the replacement with predefined reference
4

---

Published in Transactions on Machine Learning Research (07/2023)
values (Antwarg et al. 2021 Giurgiu & Schumann, 2019 The proposed method automatically determines the reference values depending æs via solving the optimization problem in Eq.
Practically, it is unrealistic to determine Ma manually because it should depend both on the geometry of X and on the property of e(æ). Hence, we propose a variant of Eq. 2 that admits less complexity of manual tuning. Instead of taking a minimum in a compact neighborhood, we consider a local minimum of regularized by the distance from the original æg. That is, we define variant of v, namely 0, as follows:
((S;z)) (S; where x= (): == arg min (V)) s.t. E X, ys = IS.
(3)
and (1) cly) ely +
dist(ys.
S
The second term of f is a regularizer. The hyperparameter, 2 0, controls how far æg can move from the original value and semantically corresponds to the radius of Ma in Eq. (2) Selecting the value of y is not straightforward in general because depends on the geometry of the data space. A practical suggestion is to roughly set a reference value of y such that the magnitude of the two terms of fs. become similar and try different values around it. To evaluate each 7, one can create anomalous data artificially based on prior knowledge and see how well the artificial anomalies are attributed. Meanwhile, we empirically found that the performance of the attribution method was not so sensitive to the value of y, reported in Appendix B.1 dist(:;-) is some dissimilarity function in each dimension of X. It is to be defined by user in accordance with the nature of the data space, X. We set it as the Euclidean distance in the experiments in Section 5
Comparing Eq. (2) and Eq. (3), we can understand that the constraint in Eq. (2 (i.e., y E M₂) is relaxed to be the regularizer in Eq. (3) (i.e., the second term of {5,z).
Despite the relaxation from in Eq. 22 to in Eq. (3), the computation can still be prohibitively heavy for moderate number of features (e-g.; d 10) because computing needs to run the local minimization for O(24) times. We suggest heuristic relaxation that reduces the number of minimization runs to O(d). The bottleneck lies in computing 2² (S;z), a local minimun of &s Hence, instead of 4", we define an "ansatz" xx as follows:
('(2; ((2;:)++ >=((();)))) LES
(((S;o):= = s.b. zs 2g and Zge
(4)
|S| $1+1
The computation process in Eq. 4 can be rephrased in words as follows. The subvector of x= 2"(S;a x) corresponding to S (which will call the S-subvector of m²) is from the original (i.e., æg). This is the same with the S-subvector of ø*, and the difference between de and xx lies in the remaining part, the S"-subvector. While the S"-subvector of Æ* is defined dircetly as a minimizer of fs.z. the -ussubecctor of x is defined as the average of 4' computed for the singletons of S's elements and the emply set. It means that we need to compute the minimization in Eq. every afterward to compute x². Consequently, we define a relaxed characteristic function, namely z, as
3 only for |S] + times and that we can reuse its results for
u(S: = elz (S;
The relaxation from 4* in Eq. 3 to x² in Eq.
4 is heuristic, and the latter is not necessarily approxi- mation of the former in a proper sense. Meanwhile, we empirically found that the heuristic relaxation still works to some extent, as reported in Section 5 We note the idea of the relaxation as follows. First, recall that the original definition in Eq. 3 is the solution of the minimization problem with all the elements of æ indexed in S fixed. Then, in Eq. (4) we try to make its surrogate by averaging the local solution of minimization problems with each element of æ indexed in S fixed in each problem. We also counted the empty set as one of the cases of this process, thus the |S| cases in Eq. 4 appeared.
3.2 Overall algorithm
The main contribution of this paper lies the definition of the characteristic function for attributing anomaly scores, which we have presented so far. Meanwhile, we note the overall algorithm to approximately compute
5

---

Published in Transactions on Machine Learning Research (07/2023)
Algorithm 1 Shapley value approxination for anomaly score attribution
Input: Anomaly score function e, query data point hyperparameter 2 0, number of MC samples m Output: Shapley values for each feature, fØ1...., 0d]
1: for s s= 2. (1),,..... [d] do (=; f arg min (x yEX. n
2:
E5 Eq.
3: end for
for j 1, I,..,, m do
Sj +- Draw a random subset S of {I,..., with probability (d 1)]SI!(d - |S| 1)1/d!
xx ('); Fq.
end for
8: [ arg m E, (CKEEoos,, o)))
> Charnes et al. (1988) Lundberg & Lee 2017
the Shapley value, in Algorithm 1 for the completeness of the paper. The following are some noles on the algorithm:
It does not assume any specific types of anomaly detectors long (sub) difeerrifeeet anomaly score function is defined. The model can be GMMs, autoencoders, their combinations or ensembles, or anything else, and the anomaly score can be negative log-likelihoods, reconstruction errors, others.
Lines 1 8 of Algorithm I perform the Monte Carlo approximation of the Shapley value computation. Upon the approximation, we utilize the weighted least squares formulation of the Shapley value (Charnes et al. Lundberg & Lee
1988
2017 Aas et al. 2021)
The only hyperparameter specific to the proposed method is y. We found that the performance was not sensitive to y (sce the appendix). m is a hyperparamcter generally present in Shapley value approximation, and we used the value recommended in Lundberg & Lee (2017). m = 2d 2d+22 2
4 Related Work
As mentioned earlier, anomaly score attribution with the Shapley value has already been studied (Antwarg et al. 2021 Giurgiu & Schumann, 2019; Takeishi 2019). though the characteristic functions used in these studies are not necessarily specialized for anomaly scores. We will also try general methods of the Shapley value-based attribution in our experiments in Section 5 for comparison.
For semi-supervised anomaly detection, other types of interprctation mothods, not explicitly based on the Shapley value, have also been proposed. (iddiqui et al. (2019) formulated the sequential feature explanation, in which they seek a most convincing order of features to explain an anomaly. [Zhang et al. (2019) suggested using a linear surrogate model learned via perturbation around data point for explaining why the data point was regarded anomalous. We will also examine these methods in Section 5
The anomaly attribution method Tdé et al. 2021 is notable for its conceptual similarity with ours. Their method is for attributing anomalies found in regression model æ + y, where y is the regressed variable. It seeks a local correction of x such that æ + maximizes the likelihood p(y x + 5) under the regression model, and the elements of d are regarded as attributions. While the targeted type of anomaly detection is different from ours, their idca. reminds us of the intermodiate quantity of our approach, x", Eq. (2): we seek xt such that it minimiies the anomaly score in the vieinity of the original input. The method of Ide et al. (2021) could be roughly understood as using ô = x" (2: x)) the attribution based on the values of x= eS; a)) not only for S = Ø but also for different configurations of S.
attribution. In contrast, compute
Apart from the semi-supervised setting, many studies have been done on the interpretation of unsupervised anomaly detection (e.g., Knorr & Ng 1999 Kriegel et al.) 2012 Keller et al. 2012 Dang et al.) 2016 Vinh
ct al.) 2015 Liu al. 2018 Yepmo et al. 2022) or outlier detection. These methods could be adjustod for the supervupe setting, but how it should be done depends on each method. We did not include
these methods in the comparison in Section 5 since there already several methods (as exemplified above)
6

---

Published in Transactions on Machine Learning Research (07/2023)
Table 1: Datasets properties. d is the number of features. Note that [Dest] = 2 Dest = 2 (est
Name
Type
PDrrin
Pvalid
DDest
Thyroid
real 2869
717
186
BreastW
real
164
41
478
U2R
real
12310
3078
420
Lympho
59
binary
109
27
12
Musk
166
real
2294
574
194
Arrhythmia
274
real 256
54
132
that directly fit the semi-supervised setting. Adapting the interpretation methods for outlier detection to semi-supervised anomaly detection would be an independent study.
Budhathoki al. (022) address related problem with fundamentally different assumption; they assume to have the knowledge of the causal structure behind data. They compute the Shapley value of anomaly scores by referring to functional causal model. While their method is not applicable to our setting we
assume rather the absence of causal knowledge, exploring new problem settings between the two extrema (complete presence or absence of causal knowledge) would be an interesting future direction.
5 Experiments
We present the empirical performance of the proposed method and baseline methods for different datasets and anomaly detectors. We will summarize the implications of the results later in Section 6
5.1
Experimental setting
5.1.1 Datasets
We used six public datasets with different numbers of features as listed in Table The dataset is subset of the NSL-KDD dataset. (Tavallaee et al., 2009), which is modified version of the KDDCup '99 data. We created the U2R dataset by extracting the U2R attack type from the NSL-KDD dataset and by eliminating categorical and constant-valued features. The other datasets are from the ODDS repository (Rayana 2016).
For the Lympho dataset, we converted the categorical features into binary by one-hot encoding, which resulted in the 59-dimensional dataset.
We split each dataset into a training set Dirain; a validation set D and a lest set Drost Diest Danom We used the whole anomaly part of each dataset Dest and randomly chose the same size of normal data Dnorm. Dirain and Dvalid for training and selection of anomaly detectors, respectively, whereas D and Danom were secured for measuring the performance of attribution methods. We normalized the real-valued datasets using each training set's mean and standard average.
created from the remaining normal data. We used Derain and D
5.1.2 Anomaly scores
We examined the following types of anomaly detectors with corresponding e(x:) (details are the appendix):
GMM e(x) as the energy (i.e., negative log-likelihood) of GMM.
VAE-r e(x)) as the reconstruction error of VAE.
VAE-e e( e(x) as the negative empirical lower bound of VAE.
DAGMM e(x) as the energy of the deep autoencoding Gaussian mixture models (Zong et al. 2018
5.1.3 Attribution methods
We tried the following three baseline methods:

---

Published in Transactions on Machine Learning Research (07/2023)
MARG
Marginal scores of individual features. We examined the energy of marginal distributions for GMM and the reconstruction error of each feature for VAF-r. In principle, this baseline is not applicable to VAEle and DAGMM as they do not admit straightforward decomposition of the anomaly scores.
SFE
The sequential feature explanation (Siddiqui et al., 2019 We used the greedy algorithm named "sequential marginal". This method applicable only GMM and VAE-r, as with MARG.
ACE
The anomaly contribution explainer (Zhang et al. 2019
We also tried the following variants of the general Shapley value-based methods:
IG
The integrated gradients (Sundararajan al.) 2017), which can be regarded as realization of the Jumann-Shaples value. We used the mean of training data as reference value.
KSH
The kernel SHAP (Lundberg & Lee 2017). As suggested by the authors' implementation, we used the cluster centers computed by k-means (k: 8) on training data as reference values. We note that Antwarg et al. 2021 also used the kernel SHAP for anomaly scores.
wKSH
variant of the kernel SHAP, namely weighted kernel SHAP, in which we selected reference values by æ's k-nearest neighbors from training data with k 8. This approach is similar the method proposed by Giurgiu & Schumann 2019), where they used the influence weights instead.
Finally, with regard to our proposed method, we tried two variants:
COMP
Attribution as the absolute value of each element of ó = a= (2:x)= -x, where d" is the intermediate quantity of the proposed method in Eq. This conceptually similar to the method of Tdé et al.. 22021 (anomaly compensation).
ASH
The full proposed method, namely anomaly Shapley, outlined in Algorithm [ We used the most relaxed definition of our characteristic function, u in Eq. 5 and set 7 = 0.01, unless otherwisc stated.
5.2 Attribution for synthetic anomaly
We investigated the performance of the altribution methods under controlled conditions using the normal half of test data, Duarm. We generated synthetic anomalies by perturbing some features of the normal data and then tried to localize them with attribution results. We synthesized the anomalics as follows: for every data point of Deet, we selected a set of danom ures, and perturbed the values of the selected features by adding noise drawn uniformly from [-2, -1] [1.2] (for real-valued datasets). We set this magnitude of the noise because the real-valued datasets were normalized to have the unit standard deviation. For the binary-valued dataset (i.e., Lympho), instead of adding the real-valued noise, we flipped the values of the selected features.
All the anomaly detectors resulted in similarly good detection performances probably because the sesthes anomalies were obvious, so we focus only on the attribution performance. We defer the results with danom > 1 to the appendix, though the overall tendency the same as what we observed from the results with danom
For danom 1, we report the mean reciprocal rank (MRR) of the attribution of the perturbed feature. This is the average of the reciprocal of the rank of the perturbed feature's attribution in the descending order, so, if the largest value is attributed to the perturbed feature for every data point, then the MRR becomes 1. The MRR values are detailed for all the datascts and the detectors in Table 2 The proposed approach, ASH, is better than or comparable with the other methods in many datasel-detector pairs. It is worth noting that the simple strategy, MARG, works to some extent in most cases when applicable, though an obvious drawback is the limited applicability. We report the result with another criterion, Hits@ (i.c., the proportion of samples where the perturbed feature was in the top-3 attribution), in Table 3 for completeness, where we observe the same tendency.
8

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 2: MRR (the larger, the better) the synthetic anomalies, for danom 1. The percentiles shown at the bottom of the table are statistics of the values of all the dataset-detector pairs. We show the percentiles for MARG and SFE just for information and do compare them with the other methods' statistics because the applicable detectors different. The same applies to the following tables.
Setting
MRR
Dataset
Detector
MARG
SFE
ACE
IG
KSH
WKSH
COMP
ASH
GMM
0.57
0.59
0.73
0.70
0.48
0.71
0.48
0.78
VAž-r
0.75
0.75
0.77
0.75
0.58
0.77
0.75
0.75
Thyroid
VAF-e
0.74
0.76
0.56
0.77
0.46
0.75
DAGMM
0.39
0.23
0.38
0.46
0.66
0.51
GMM
0.78
0.79
0.77
0.78
0.42
0.76
0.47
0.78
VA
0.67
0.67
0.71
0.83
0.66
0.81
0.77
0.77
Breastw
VAE-e
0.72
0.86
0.66
0.80
0.52
0.85
DAGMM
0.37
0.13
0.38
0.68
0.49
0.57
GMM
0.84
0.82
0.70
0.86
0.36
0.90
0.57
0.86
VAE-r
0.84
0.84
0.88
0.87
0.36
0.91
0.81
0.89
U2R
VAE-e
0.83
0.89
0.37
0.90
0.41
0.88
DAGMM
0.58
0.11
0.29
0.74
0.78
0.71
GMM
0.48
0.56
0.16
0.89
0.08
0.08
0.15
0.73
VAE-r
0.92
0.92
0.16
0.66
0.08
0.08
0.03
0.87
Lympho
VAï-e
0.16
0.69
0.08
0.08
0.03
0.83
DAGMM
0.08
0.12
0.08
0.08
0.16
0.37
GMM
0.08
0.10
0.24
0.28
0.20
0.92
0.11
0.97
VAË-r
0.98
0.98
0.60
0.80
0.54
0.98
0.20
0.98
Musk
VAE-c
0.61
0.80
0.54
0.98
0.11
0.97
DAGMM
0.10
0.03
0.06
0.47
0.11
0.28
GMM
0.22
0.24
0.25
0.42
0.09
0.48
0.08
0.49
VAF-r
0.72
0.72
0.35
0.54
0.36
0.58
0.17
0.71
Arrhythmia
VAE-e
0.35
0.54
0.36
0.58
0.18
0.72
DAGMM
0.13
0.00
0.06
0.22
0.08
0.17
25th percentile
(0.55)
(0.58)
0.22
0.27
0.09
0.47
0.11
0.67
50th percentile
(0.73)
(0.73)
0.48
0.69
0.36
0.72
0.30
0.76
75th percentile
(0.84)
(0.82)
0.72
0.81
0.49
0.83
0.53
0.86
5.3 Comparison to attribution of supervised classifier
For assessing the performance of the attribution methods a more realistic situation, we use another half of the test data, Diss Although we know that Dama comprises somewhat anomalous data points, wo do not know which features are most anomalous for each data point, so the ground truth of anomaly score attribution is not available. Hence, we resort comparing the attributions of the semi-supervised anomaly scores with the attribution of supervised classifier's outputs, expecting that the supervised model capture richer information on the data than the semi-supervised models can do, since the former is explicitly informed by both normal and anomalous labeled data, while the latter is only informed by normal data.
For each dataset, we first train a binary classifier (specifically, SVM with the RBF kernel) using all the data, with the two classes being normal (Dirain DDaii test and anomalous (D As the two classes are imbalanced, we preprocessed the data using SMOTE (Chawla al.) 2002). We then compute the attribution of the classifier's output for cach data point of Denom using kernel SHAP (Lundberg & Loe 2017) and choose the feature with the largest absolute value of the altribution as the most anomalous leature for each dala point. We only use instances for which the following holds:
sup 2 2
(6)
We D both training attribution, which problematic hecause our purpose in predicting the lahel the supervised classifier; just works as reference of attribution.

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Table 3: Hits@3 (the larger, the better) of the syuthetic anomalies, for danom 1.
Setting
Hits@3
Dataset
Detector
MARG
SFE
ACE
IG
KSH
WKSH
COMP
ASH
GMM
0.79
0.81
0.85
0.89
0.66
0.89
0.46
0.88
VAE-r
0.86
0.86
0.88
0.86
0.78
0.84
0.86
0.86
Thyroid
VAl-e
0.85
0.85
0.72
0.85
0.44
0.85
DAGMM
0.39
0.15
0.48
0.47
0.79
0.57
GMM
0.85
0.90
0.85
0.88
0.55
0.82
0.44
0.88
VAE-r
0.78
0.78
0.76
0.92
0.71
0.89
0.89
0.80
Breasti
VAF-e
0.78
0.95
0.72
0.88
0.51
0.93
DAGMM
0.32
0.03
0.37
0.69
0.53
0.68
GMM
0.97
0.93
0.74
0.97
0.47
0.91
0.57
0.97
VAË-r
0.97
0.97
0.94
0.96
0.47
0.90
0.97
0.96
U2R
VAE-c
0.95
0.96
0.49
0.90
0.41
0.96
DAGMM
0.60
0.00
0.28
0.74
0.93
0.83
GMM
0.41
0.63
0.14
0.98
0.06
0.06
0.14
0.98
VAF-r
0.95
0.95
0.14
0.73
0.06
0.06
0.00
0.96
Lympho
VAE-e
0.14
0.82
0.06
0.06
0.00
0.84
DAGMM
0.06
0.13
0.06
0.06
0.14
0.46
GMM
0.05
0.07
0.24
0.28
0.25
0.93
0.14
0.97
VAE-r
0.98
0.98
0.64
0.82
0.60
0.99
0.24
0.99
Musk
VAE-e
0.63
0.82
0.59
0.99
0.14
0.97
DAGMM
0.10
0.03
0.04
0.56
0.14
0.30
GMM
0.21
0.23
0.27
0.49
0.07
0.57
0.07
0.53
VAE-r
0.75
0.75
0.41
0.70
0.45
0.71
0.18
0.78
Arrhythmia
VAF-e
0.41
0.70
0.45
0.71
0.22
0.79
DAGMM
0.14
0.00
0.04
0.26
0.06
0.17
25th percentile
(0.67)
(0.72)
0.21
0.25
0.07
0.54
0.14
0.76
50th percentile
(0.82)
(0.83)
0.51
0.82
0.46
0.78
0.32
0.85
75th percentile
(0.95)
(0.94)
0.80
0.90
0.59
0.89
0.54
0.96
Table 4: MRR of the most-attributed features by the supervised classifier for real anomalies.
Setting
MRR
Dataset Detector
MARG
SFE
ACE
TG
KSH
WKSH
COMP
ASH
GMM
0.52
0.44
0.64
0.57
0.54
0.75
0.68
0.91
VAE-r
0.87
0.87
0.86
0.87
0.71
0.76
0.87
0.87
Thyroid
VAE-e
0.82
0.87
0.77
0.75
0.68
0.87
DAGMM
0.47
0.18
0.42
0.36
0.64
0.68
GMM
0.72
0.69
0.48
0.73
0.37
0.45
0.82
0.73
VAE-r 0.64
0.64
0.70
0.65
0.38
0.37
0.71
0.66
U2R
VAE-e
0.69
0.69
0.39
0.40
0.14
0.66
DAGMM
0.55
0.13
0.54
0.43
0.70
0.51
GMM
0.02
0.03
0.26
0.01
0.05
0.16
0.64
0.04
VAE-r
0.06
0.06
0.24
0.14
0.20
0.12
0.63
0.10
Musk
VAE-e
0.18
0.14
0.20
0.12
0.64
0.01
DAGMM
0.24
0.01
0.02
0.18
0.64
0.14
25th percentile
(0.17)
(0.15)
0.26
0.14
0.20
0.17
0.64
0.13
50th percentile
(0.58)
(0.54)
0.52
0.38
0.39
0.39
0.66
0.66
75th percentile
(0.70)
(0.68)
0.69
0.70
0.54
0.53
0.70
0.77
where o and thu respectively denote the largest and the sccond-largest elements of set {Ø] ..... Suu which is the set of the supervised classifier's attribution the features. With Eq. (6) we can only use instances for which the ittth feature is significantly attributed than the runner-up iz-th feature. We
10

---

Published in Transactions on Machine Learning Research (07/2023)
finally evaluate how well such features can be localized by the attributions of the semi-supervised anomaly scores by methods listed in Section 5.3
In Table | we report the MRR of the attribution of the semi-supervised anomaly scores, with the features most attributed in the supervised classifier being the golden standard. The reciprocal rank is 1 when the attribution of the supervised classifier and that of the semi-supervised anomaly score assign the largest value to the same feature. Although ASH is competitive or better compared to other methods for the Thyroid and U2R datasets, it (as well as the other methods except COMP) fails for the Musk dataset. Meanwhile, the COMP baseline method is still successful to some extent for the Musk dataset. This is interesting, but the current data resource does not allow further analysis of why this was the case. We report the results only for the three datasets because, for the remaining datasets, only a few instances of each of them sufficed the condition in Eq. and thus the performance comparison for those datasets was less reliable.
In Fig. 2 we show examples of the anomaly score attributions. The right panel of the figure reports the normalized absolute values of the attributions for the GMM detector on the Thyroid dataset. Each row corresponds to each of four data points, which are emphasized in the scatter plot matrix in the left panel by the associated markers
and *). Here, we note that all of these four points are anomalous data points; attributing anomaly scores only makes sense for anomalous queries. In the first two examples and )) the largest, attribution by ASH successfully coincides with that of the supervised classifier. In contrast, they do not match in the last two examples and #).. We would note the following observations:
The Shapley- value--auee-uae based attributions (i.e., IG, KSH, WKSH, and ASH) tend to give relatively (close to) sparse attributions compared to the other methods. This tendency was commonly observed in other examples not shown here, too.
The attributions by KSH for the first two examples, and E, are similar. In contrast, the attributions by wKSH and ASH are very different. between these examples. Such a difference of the behavior can be explained by the fact that while KSH uses the fixed reference value in computing the characteristic function, the reference values used by WKSH and ASH are adaptive to the query data point.
In the third example (A), the attribution by ASH significantly deviates from the supervised classifier's attribution. This may be due to the extreme value of the corresponding data point, the point A in the scatter plot matrix. At the same time, the ASH's attribution (largest for Feature #3) is not necessarily meaningless because the point exhibits an extreme value also for Feature #3.
In contrast to the third example ) the data point of the fourth example (*) has no clear extreme values and rather lies in the proximity of points and M. This fact makes the reason why ASH failed with the point less clear. Mcanwhile, the failure is lighter than in the previous case because Feature #0 has the second largest value in the attribution by ASH.
5.4 Validity of heuristic relaxation
Recall that in Section 3.1 we introduced hcuristic relaxation of the characteristic function. We investigated the validity of the relaxation by comparing the original relaxed characteristic function (i.e., è in Eq. 3 and the heuristically approximated one (i.e., y in Eq. 5)) Tn Table 5 we compare the Shapley value-based attribution using i and v. In terms of the computation time for each æ, the attribution with y is significantly faster than that with 6, which is a natural consequence of the definitions. Meanwhile, the resulting MRRs with each characteristic function (in the setting of synthetic anomaly experiment in Section 5.2) are similar to each other. We report the comparison only for the two datasets in Table 5 because the computation of è for datasets with more features was basically infeasible.
6 Discussion
The proposed strategy, ASH, resulted in a relatively stably good performance. Nonetheless, it sometimes failed while others were good (though the same could be said for all the mothods; no one wins always). These observations tell us that using multiple attribution methods with multiple detection methods in ensembles may be good practice for interpreting anomaly detection.
11

---

Published in Transactions on Machine Learning Research (07/2023)
Sup
MARG
SFB
ACE
IG
KSH
WKSH
COMP
ASH
012345
012345
012345
012345
012345
012345
012345
012345 012345
012345
012345
012345
012345
012345
012345
012345
012345
012345
012345 012345
012345
012345
012345
012345
012345
012345
012345
3
012345 012345 012345 012345 012345 012345 012345 012345 012345
Figure 2: (Left) Scatter plot matrix of the Thyroid dataset (d=6) 6). The blue and orange points are from Duet and Dest", respectively. The labels from 0 to 5 are the feature index. (Right) Examples of the anomaly score attributions for the GMM detector. The normalized absolute values of the attributions are reported. "Sup" refers to the reference attribution of the supervised classifier, [o,"P]. Each row corresponds data point of the Thyroid dataset. The associated markers corresponding data points in the left panel. Note that the points with those markers anomalous data.
and x) point to the location of the
Table 5: Comparison of the two definitions of the characteristic functions for anomaly scores, (without the heuristics, in Eq. (3) and (with the heuristics, in Eq. ( The per-sample computation time and the performance of the attribution for the synthetic anomaly with danom are reported.
Average computation time (STD)
Setting
MRR
|sce/samplc]
Datasct Detector
with
with 2
with 6
with g
GMM
26.40 (13.19)
6.19 (3.05)
0.76
0.78
Thyroid d= 6
VAE-r
23.50 (12.06)
5.58 (3.04)
0.75
0.75
VAE-e
23.81 (13.50)
5.42 (3.28)
0.75
0.75
DAGMM
51.52
(37.19)
12.45 (8.43)
0.57
0.51
GMM
278.84 (169.07)
7.10 (4.28)
0.78
0.78
Breastw
VAE-r
397.87
(235.73)
14.76 (8.21)
0.81
0.77
d= 9
VAE-e
478.76
(272.03)
15.86 (8.94)
0.84
0.85
DAGMM
1071.99 (596.88)
18.37 (12.48)
0.57
0.57
Analysis of each method's failure is an important question, though it is out of the scope of this paper because such failure analysis is meaningful only with in-depth experimentation for each particular anomaly detector, characteristic function, data, and anomaly type. This paper, instead, has provided a general overview of the relevant attribution methods to investigate their applicability. Although we provided examples of attributions in Fig. 2 we think it is not safe to say anything more detailed than what we listed in Section 5.3 because the visualization reveals only limited aspects of the dataset, and the true cause of anomalies cannot necessarily be ascribed to single feature as we did.
In the experiment, we also observed that the simplest approach, MARG, worked well in some cases. It is, in sense, reassuring because MARG has been the only way anomaly attribution practiced in many use cases for long time. However, was sometimes substantially outperformed by other methods and can only be computed for limited types of anomaly scores, which motivates the use of the other attribution methods including the proposed one.
12

---

Published in Transactions on Machine Learning Research (07/2023)
Another general observation is that the anomaly score by DAGMM was relatively difficult to attribute, especially when d > 10, probably because of its strong non-additive nature. Such "attribution hardness" would be an interesting topic of future studies.
Finally, as stated earlier, the evaluation using the real anomaly data has inherent limitations (as often the case with the evaluation of interpretation methods), since the ground truth was a surrogate. More specific evaluations with real anomalies should be done in each application domain with experts' supervision.
Broader Impact Statement
This paper presents some methods for interpreting anomaly detection results, which can be utilized in various real-world domains including industrial sectors. The users must be constantly aware of the heuristic and data- driven nature of the methods; the correctness of the interpretation can never be guaranteed automatically. The methods can useful in helping the user's decision decision-making processes but cannot replace any critical roles of human operators. Morcover, as advised in the paper, multiple attribution methods should be used together in ensembles for gaining stability.
Acknowledgments
The major part of this work conducted when the first author was working at RIKEN Center for Advanced Intelligence Project. Afterward, major revision and additional experiments were done while the first author was at the University of Applied Sciences Western Switzerland.
References
Kjersti Aas, Martin Jullum, and Anders Loland. Explaining individual predictions when features are depen- dent: More accurate approximations to Shapley values. Artificial Intelligence, 298:103502, 2021.
Marco Ancona, Cengiz Öxtireli, and Markus Gross. Explaining deep neural networks with polynomial time algorithm for Shapley values approximation. In Proceedings of the 36th International Conference on Machine Learning, pp. 272 281, 2019.
Liat Antwarg, Ronnie Mindlin Miller, Bracha Shapira, and Lior Rokach. Explaining anomalics detected by autoencoders using Shapley Additive Explanations. Expert Systems with Applications, 186(30):115736,
2021.
Kailash Budhathoki, Lenon Minories, Patrick Blöbaum, and Dominik Janzing. Causal structure-based root cause analysis of outliers. In Proceedings of the 39th International Conference Machine Learning, pp. 2357-2368 2022.
Javier Castro, Daniel Gómez, Elisenda Molina, and Juan Tejada Improving polynomial estimation of the Shapley value by stratified random sampling with optimum allocation. Computers & Operations Research, 82:180 188, 2017.
Varun Chandola, Arindam Banerjee, and Vipin Kumar. Anomaly detection: A survey. ACM Computing Surveys, 41 (3):1-588 2009.
A. Charnes, B. Golany, M. Keane, and J. Rousscau. Extremal principle solutions of games in characteristic function form: Core, Chebychev and Shapley value generalizations. In Econometrics of Planning and Efficiency, volume 11 of Advanced Studies in Theoretical and Applied Econometrics, pp. 123-133. 1988.
Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer. Smote: Synthetic minority over-sampling technique. Journal of Artificial Intelligence Research, pp. 921-357, 2002.
Xuan-Hong Dang, Arlei Silva, Ambuj Singh, Ananthram Swami, and Prithwish Basu. Outlier detection from network data with subnetwork interpretation. In Proceedings of the 16th IEEE International Conference on Data Mining, pp. 847 847-852, 2016.
13

---

Published in Transactions on Machine Learning Research (07/2023)
Amupam Datta, Shayak Sen, and Yair Zick. Algorithmic transparency via quantitative input influence. In Proceedings of the 2016 IEFE Symposium on Securily and Prisacy, pp. 598-617, 2016.
Dheeru Dua and Casey Graff. UCT machine learning repository, 2017. URL http:://arci.e...ic../m ics www.iicc.....uuuuu edu/
m1
Ioana Giurgiu and Anika Schumann. Additive explanations for anomalies detected from multivariate tem- poral data. In Proceedings of the 28th ACM International Conference Information and Knowledge Munagement, pp-
2019.
Tsuyoshi Idé, Amit Dhurandhar, Jiří Navrátil, Moninder Singh, and Naoki Abe. Anomaly attribution with likelihood compensation. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pp. 4131 4138, 2021.
Fabian Keller, Emmanuel Muller, and Klemens Böhm. HICS: High contrast subspaces for density- outlier ranking. In Proceedings of the 28th IEEE International Conference on Data Engineering, pp. 1037-1048, 2012.
Edwin M. Knorr and Raymond T. Ng. Finding intensional knowledge distance-based outliers. In Proceed- ings of the 25th International Conference on Very Large Data Bases, pp. 211 222, 1999.
Hans-PPter Kriegel, Peer Kröger, Erich Schubert, and Arthur Zimek. Outlier detection in arbitrarily oriented subspaces. In Proceedings of the 12th IEEE International Conference Dato Mining, pp.
2012.
Stan Lipovetsky. Entropy criterion in logistic regression and Shapley value of predictors. Journal of Modern Applied Statistical Methods,
2006.
Ninghao Liu, Donghwa Shin, and Xia Hu. Contextual outlier interpretation. In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pp. 2461 2467, 2018.
Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Newral Information Processing Systems 30, pp. 4765-4774, 2017.
Lars Henry Berge Olsen, Ingrid Kristine Glad, Martin Jullum, and Kjersti Aas. Using Shapley values and variational autoencoders explain predictive models with dependent mixed features. Journal of Machine Learning Research, 23(213):1 51, 2022.
Art B. Owen and Clémentine Prieur. On Shapley value for measuring importance of dependent inputs. STAM/ASA Journal on Uncertainly Quantification, 6(1):986-1002) 2017.
Marco A. F. Pimentel, David A. Clifton, Lei Clifton, and Lionel Tarassenko. A review of novelty detection. Signal Processing, 99:215 229111299911111 2014.
Shebuti Rayana. ODDS library, 2016. URL http:///odd......stonrrooo
Lloyd S. Shapley. A value for n-person games. In Contributions to the Theory of Games, volume II of Annals of Mathematics Studies, pp. 307-317. Princeton University Press, 1953.
Md Amran Siddiqui, Alan Fern, Thomas G. Dietterich, and Weng-Keen Wong, Sequential feature explana- tions for anomaly detection. ACM Transactions on Knowledge Discovery from Data, 13(1):1-22 22, 2019.
Erik Strumbelj and Igor Kononenko. Explaining prediction models and individual predictions with feature contributions. Knowledge and Information Systems, 41(3):6447 665, 2014.
Mukund Sundararajan and Amir Najmi. The many Shapley values for model explanation. In Proceedings of the 37th International Conference on Machine Learning, pp. 9269-9278, 2020.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks, In Proceedings of the 34th International Conference Machine Learning, pp. 3319-3328, 2017.
14

---

Published in Transactions on Machine Learning Research (07 (07/2023)
Naoya Takeishi. Shapley values of reconstruction errors of PCA for explaining anomaly detection. In Proceedings of the 2019 International Conference on Dala Mining Workshops, pp- 793-799 2019.
Mahbod Tavallace, Ebrahim Bagheri, Wei Lu, and Ali A. Ghorbani. A detailed analysis of the KDD CUP 99 data set. In Proceedings of the 2009 IEEE Symposium Computational Intelligence for Security and Defense Applications, 2009.
Nguyen Xuan Vinh, Jeffrey Chan, James Bailey, Christopher Leckie, Kotagiri Ramamohanarao, and Jian Pei. Scalable sollying-inlling aspects discovery via feature ranking. In Advances in Knowledge Discovery and Data Mining, volume 9078 of Lecture Notes in Computer Science, pp. 422-434. 2015.
Véronne Yepmo, Grégory Smits, and Olivier Pivert. Anomaly explanation: A review. Data 8 Knowledge Engineering, 137:101946, 2022.
Xiao Zhang, Manish Marwah, I.-ta Lee, Martin Arlitt, and Dan Goldwasser. ACE An anomaly contribution explainer for cyber-security applications. In Proceedings of the 2019 IEEE International Conference Big Data, pp. 1991-2000 2019.
Bo Zong, Qi Song, Martin Renqiang Min, Wei Cheng, Cristian Lumezanu, Dacki Cho, and Haifeng Chen. Deep autoencoding Gaussian mixture model for unsupervised anomaly detection. In Proceedings of the 6th International Conference on Learning Representations, 2018.
A Experimental Settings
A.1 Datasets
2017); and used the reformatted dataset provided as part of the ODDS repository (Rayana 2016 The reformatted dataset comprises six real-valued features, eliminating the 15 categorical features of the original. The original task for which the dataset was prepared is to determine whether a patient is hypothyroid or not. For anomaly detection purposes, within the three classes of normal functioning, subnormal functioning, and hyperfunction, the first two are used as normal data, and the last is as anornalou data.
Thyroid is originally from the UCT machine learning repository (Dua & Graff
BreastW originally from the UCT machine learning repository, and we used the reformatted dataset provided part of the ODDS repository. The dataset comprises nine features that take categorical values from to 10. The original problem is the classification between benign and malignant classes. For anomaly detection purposes, the malignant class is used as anomalous data.
U2R is a part the NSL-KDD dataset (Tavallace et al. 2009 which is a modified version the KDD Cup 1999 dataset. From the NSL-KDD dalaset, we used the part of the datasel correspond- ing to the U2R attack type. We eliminated the six categorical features and real-valued feature that does not change in the dataset, which resulted in the following ten features (in the original names):
duration
6. num fule creations _
2. hot
7. srv_ srv_count
3. nam__ com____mrromieed
8. dst josthostt_. count
4. root_shed
9. dst host_ssvu_ourt
5. naomrroot
10. jatthost. mont__same_sm__prtt
Lympho is originally from the UCI machine learning repository, and used the reformatted dataset provided as part of the ODDS repository. The dataset comprises 18 categorical features, and we transformed them by one-hot encoding, which resulted in the 59-dimensional dataset. The original task is the classification between four classes, two of which are quite small. For anomaly detection purposes, these small classes are used as anomalous data.
Musk is originally from the UCI machine learning repository, and we used the reformatted dataset provided part of the ODDS repository. The dataset comprises 166 real-valued features. The original task is to
15

---

Published in Transactions on Machine Learning Research (07/2023)
classify molecules into musk and non-musk classes. For anomaly detection purposes, three non-musk classes are used as normal data, and two musk classes are anomalous data.
Arrhythmia is originally from the UCI machine learning repository, and we used the reformatted dataset provided as a part of the ODDS repository. The reformatted dataset comprises 274 real-valued features. The original task a 16-class classification to distinguish between the presence and absence of cardiac arrhythmia. For anomaly detection purposes, the eight smallest classes are used as anomalous data.
A.2 Anomaly detection methods
A.2.1
Gaussian mixture models (GMMs)
We selected best numbers of mixture components, K, from 2, 3, 4, based the validation likelihood. The corresponding anomaly score is the energy (i.e., negalive log-likelihood) of the GMMs:
( (0g((2 1 Tg exp
log (Et) 1 - sas)) T
(ar prc) )
e(ac) -lg
where ...,...., Øk} is the set of mixture weights, (MI,..., ,uk) is the of means, and (Ei,..., Σx} the set of covariance matrices.
A.2.2 Variational autoencoders (VAEs)
The encoder is a multilayer perceptron with one hidden layer, whereas the decoder is with two hidden layers. Every activation function is the softplus function. We selected the best values of the dimensionality of the latent variable, dim(z), and the number of the hidden units of the multilayer perceptrons, dim(MLP) based on the validation ELBO. The candidate of dim(z) was the rounded values of 0.2d, 0.4d, 0.6d, and 0.8d, where d is the dimensionality of each dataset. The candidate of dim(MLP) 2d. The loss function used for learning datasets or with the cross-entropy loss for the binary-valued dataset. We used the Adam optimizer with the learning rate 0.001 and stopped the optimization observing the validation set loss. The corresponding anomaly scores arc:
the rounded values of 0.5d, d, and the negative ELBO with the mean squared loss for the real-valued
e(x) x - f(g(x)))
and
e (x) (=(mm) log (a x) + logp(z) - log ( x)),
for VAË-r and VAE-e, respectively. 0 and up denote the sets of parameters of the decoder and the encoder, respectively. g and f are the decoder and the encoder's mean parameter function, respectively.
A.2.3 Deep autoencoding Gaussian mixture models (DAGMMs)
The architectures of the encoder and decoder are the same the VAEs above. What is specific to DAGMMs is the so-called estimation network that outputs the estimation of cluster assignment of a GMM learned on the latent representations and the reconstruction error values. In our experiments, the estimation network is a multilayer perceptron with one hidden layer using the softplus function as activation. The candidates of the hyperparameters were the same as the above cases, both for the autoencoder part and the GMM part. We used the Adam optimizer with the learning rate 0.0001 and stopped the optimization observing the validation set loss.
B Experimental Results
B.1 Sensitivity to hyperparameter
In Table we report results of the synthetic anomaly experiment (in Section 5.2 using the GMM detector with 7 being varied from 0.001 to 10. We observe that the performance is insensitive to 7-
16

---

Published in Transactions on Machine Learning Research (07/2023)
Table 6: MRR for the synthetic anomaly. The values for the GMM detector using different values y are reported.
MRR
Datasct
7 0.001 ? 0.01
?
0.1
7 == 1.0
7 10.0
Thyroid
0.77
0.78
0.78
0.75
0.74
Breastw
0.78
0.78
0.78
0.77
0.78
U2R
0.86
0.86
0.86
0.86
0.86
Lympho
0.73
0.73
0.73
0.73
0.74
Musk
0.98
0.97
0.95
0.93
0.92
Arrhythmia 0.49
0.49
0.49
0.50
0.50
Table 7: Per-sample computation time the allribution with the proposed characteristic function, g.
Sctting
Average computation time (STD)
[sec/sample]
Dataset
Detector
GMM
6.19 (3.05)
Thyroid
VAE-r
5.58 (3.04)
d
VAE-e
5.42 (3.28)
DAGMM
12.45 (8.43)
GMM
7.10 (4.28)
Breastw d=0
VAE-r
14.76 (8.21)
VAE-e
15.86 (8.94)
DAGMM
18.37 (12.48)
GMM
10.35 (7.64)
U2R
VAE-r
15.13 (7.30)
d d= 10
VAË-e
11.53 (6.36)
DAGMM
34.69 (18.01)
GMM
81.41 (33.14)
Lympho d = 59
VAE-r
213.68 (0.17)
VAE-e
226.29 (0.27)
DAGMM
96.68 (32.34)
GMM
217.82 (103.43)
Musk d 166
VAE-r
184.01 (62.34)
VAE-e
464.39 (92.27)
DAGMM
503.65 (85.80)
GMM
1187.44 (418.56)
Arrhythmia d = 274
VAE-r
580.67 (298.37)
VAE-e
1480.86 (161.63)
DAGMM
404.46 (270.18)
B.2 Runtime
With the heuristic relaxation we introduced (i.e., from Eq. (3) Eq. (4), the number of the minimization problems to be solved decreases from O(2d) Old). While the overall time complexity of the attribution algorithm certainly depends this number, the actual runtime depends also many other factors. Specif- ically, each of the minimization problems is solved with gradient descent, whose stopping rule refers to the empirical convergence of the objective, and thus the number of iterations significantly differs with different data. We report the average computation time of the attribution method with the proposed characteristic function (i.c., ASH) for the six datascts. The overall averages of the computation time over the four detec- are summarized in Fig. 3 Note that the evaluation for the last datasets (d 166 and 274) is difficult. because they show large variances.
17

---

Published in Transactions on Machine Learning Research (07 (0722)23)
Comp. time (s/ s/sample)
30
Comp. time (s/ ssample)
1,000
20
500
10
0
10
10
59
166
274
data dim d
data dim
Figure 3: Per-sample computation time reported in Table The overall averages over the four detectors are plotted. The left panel for the first three datasets, and the right panel for the last four datasets.
Table 8: Average AUROC for synthetic anomaly with danom 2.
Setting
AUC
Dataset
Detector
MARG
SFE
ACE
IG
KSH
WKSH
COMP
ASH
GMM
0.73
0.73
0.78
0.76
0.56
0.73
0.52
0.83
VAE-r
0.82
0.82
0.83
0.82
0.68
0.80
0.82
0.82
Thyroid
VAΣ-e
0.82
0.82
0.67
0.80
0.48
0.82
DAGMM
0.43
0.17
0.49
0.54
0.73
0.58
GMM
0.90
0.89
0.85
0.89
0.60
0.86
0.48
0.89
VAË-r
0.77
0.77
0.70
0.87
0.81
0.86
0.88
0.83
Breastw
VAF-e
0.68
0.89
0.81
0.85
0.51
0.86
DAGMM
0.48
0.13
0.58
0.73
0.53
0.68
GMM
0.95
0.88
0.68
0.90
0.53
0.86
0.54
0.89
VAE-r 0.91
0.91
0.89
0.92
0.59
0.89
0.94
0.93
U2R
VAE-e
0.87
0.93
0.60
0.88
0.46
0.92
DAGMM
0.59
0.06
0.50
0.71
0.92
0.73
GMM
0.89
0.93
0.70
0.97
0.50
0.50
0.63
0.95
VAE-r
0.99
0.99
0.71
0.90
0.50
0.50
0.29
0.95
Lympho
VAÉ-
0.71
0.93
0.50
0.50
0.29
0.93
DAGMM
0.60
0.40
0.50
0.50
0.71
0.86
GMM
0.69
0.69
0.65
0.81
0.74
0.95
0.48
0.96
VAE-r
0.99
0.99
0.92
0.95
0.90
0.99
0.75
1.00
Musk
VAΣ-e
0.91
0.95
0.90
0.99
0.48
0.99
DAGMM
0.64
0.25
0.55
0.75
0.48
0.77
GMM 0.90
0.87
0.86
0.90
0.73
0.90
0.48
0.91
VAË-r
0.98
0.98
0.92
0.94
0.89
0.93
0.85
0.96
Arrhythmia
VAF-e
0.92
0.94
0.89
0.93
0.52
0.95
DAGMM
0.57
0.11
0.62
0.67
0.48
0.68
25th percentile
(0.81)
(0.81)
0.65
0.67
0.52
0.70
0.48
0.82
50th percentile
(0.90)
(0.89)
0.71
0.89
0.60
0.82
0.52
0.89
75th percentile
(0.96)
(0.94)
0.86
0.93
0.76
0.89
0.73
0.95
B.3 Other performance measures
We show the results of the syuthetic anomaly experiment (in Section 5.2) with danom > Since the MRR and the Hits@3 are not nccessarily meaningful when danom > 1, we report the area under the receiver operator characteristic curve (AUROC) in Tables R and g given threshold value for the attributions from the largest attribution to the smallest attribution to define the ROCs, The overall tendency of the performance is the same as reported in Section 5.2
of altributions features, we sweep
18

---

Published in Transactions on Machine Learning Research (07/202) 2023)
Table 9: Average AUROC for syuthetic anomaly with danom 3.
Sctting
AUC
Dataset
Detector
MARG
SFE
ACE
IG
KSH
WKSH
COMP
ASH
GMM
0.74
0.71
0.77
0.75
0.58
0.71
0.50
0.82
VA
0.85
0.85
0.82
0.85
0.66
0.81
0.85
0.85
Thyroid
VAE-e
0.82
0.85
0.66
0.80
0.46
0.85
DAGMM
0.52
0.16
0.47
0.57
0.75
0.67
GMM
0.91
0.89
0.85
0.90
0.63
0.85
0.46
0.91
VAE-r
0.74
0.74
0.63
0.81
0.79
0.79
0.91
0.81
Breasti
VAE-e
0.63
0.84
0.79
0.80
0.53
0.81
DAGMM
0.53
0.10
0.60
0.69
0.53
0.66
GMM
0.96
0.82
0.64
0.87
0.53
0.84
0.48
0.83
VAE-r
0.92
0.92
0.89
0.94
0.57
0.92
0.94
0.94
U2R
VAF-e
0.85
0.95
0.57
0.91
0.52
0.94
DAGMM
0.56
0.06
0.52
0.66
0.92
0.68
GMM
0.89
0.91
0.71
0.96
0.50
0.50
0.58
0.93
VAE-r
0.97
0.97
0.71
0.88
0.50
0.50
0.29
0.91
Lympho
VAE-e
0.71
0.91
0.50
0.50
0.29
0.88
DAGMM
0.66
0.44
0.50
0.50
0.71
0.82
GMM
0.68
0.71
0.71
0.83
0.73
0.96
0.47
0.95
VAE-r
1.00
1.00
0.91
0.95
0.90
1.00
0.75
0.99
Musk
VAF-e
0.91
0.95
0.90
1.00
0.47
0.99
DAGMM
0.70
0.25
0.58
0.77
0.47
0.79
GMM
0.91
0.88
0.87
0.91
0.71
0.92
0.47
0.91
VAE-r
0.98
0.98
0.91
0.94
0.88
0.95
0.87
0.98
Arrhythmia
VAE-e
0.91
0.94
0.88
0.95
0.53
0.97
DAGMM
0.56
0.10
0.61
0.68
0.47
0.69
25th percentile
(0.82)
(0.80)
0.64
0.67
0.53
0.68
0.47
0.81
50th percentile
(0.91)
(0.89)
0.71
0.86
0.60
0.80
0.53
0.86
75th percentile
(0.96)
(0.93)
0.85
0.94
0.74
0.92
0.75
0.94
19


Reviews:
[{"review_id": "7kvRD581jQ", "reviewer": "Reviewer_mhYD", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "A-The idea of minimizing the score function over the other features seems very reasonable and one can say that it is a suitable approach in applications where false positive anomaly detection is costly.  \n\nB-My issue is that while the way the optimization in (2) on page 4 is formulated is rigorous, the modifications to (3) and (4) on page 5 feels very heuristic. But it seems that some of the methods here have already been used in the literature such as randomly sampling features in Lundberg et al. \n\nC-I mostly work on the theory side and I’m not that familiar with anamoly detection, so it is not clear to me how significant the contribution of this paper is. It seems to give a performance which is on par or at times better than previous methods. I believe that would be within the TMLR scope.  \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper is concerned with anomaly attribution. Specifically, while the Shapley value has been used for anomaly detection it is difficult to use it for anomaly attribution. The authors present a method for doing that where a minimization problem is solved over the ``absent’’ features. Since the problem in turn is computationally expensive to solve, algorithms to approximate this solution are used and validated empirically.   ", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A-In the definition of the Shapley value (in Eq(1) page 2), $S$ is not defined at all or mentioned which is confusing. \n\n\nMinor Points: \n\nB-I think that adding a citation for semi-supervised methods would be good for the presentation. Speicifically in the following sentence in the first paragraph of section 2.1: ``A typical solution of semi-supervised anomaly detection consists of two phases [references to this line of work] ''\n\nC-It seems to me that in the following sentences “and” should be replaced by ‘or’: \n\n1-2nd paragraph in section 2.1:  such as ``$X ⊂ R^d$ and $X ⊂ \\{0, 1}^d$ '' → such as $X ⊂ R^d$ or $X ⊂ \\{0, 1\\}^d$. \n\n2-3rd paragraph in section 2.1: ``such as principal component analysis (PCA) and autoencoders'' → such as principal component analysis (PCA) or autoencoders \n\n\nD-Section 6 (Discussion): ``$d \\ge O(10)$''. Asymptotic notation is meaningless for constants. \n\n\n", "broader_impact_concerns": "I don't think that there are any concerns about the broader impact. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "5MsZjoSyMc", "reviewer": "Reviewer_6xJf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The authors design a characteristic function for computing Shapley values that is specifically target at anomaly attribution.\n- Strong empirical performance in 2 different settings. It is not possible to compare attribution accuracy on real anomaly data because there is no ground truth to compare against, so the authors use both synthetically generated anomalies (where they can control the anomalous features) and real anomalies while treating the attributions from a supervised classifier as the \"ground truth\" for comparison.\n\nWeaknesses:\n- The paper does not show the computed Shapley values for any datasets. This is very strange given that the main purpose of this paper is about attribution, but then it doesn't show any attribution on real data.\n- No experimental validation of time complexity for the proposed heuristic relaxation is provided. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors consider the problem of attribution in anomaly detection. The objective is to identify which features lead to a particular sample being detected as anomalous. They propose to perform this attribution using Shapley values, which are frequently used for attribution in supervised learning tasks. To adapt the approach to anomaly detection, they propose a new characteristic function along with a faster heuristic relaxation for it. They demonstrate that their proposed anomaly Shapley (ASH) attribution method performs well for attributing synthetically generating anomalies by perturbing features on real data.\n\nThe main contributions I observe are as follows:\n- Proposal of a new reference-based characteristic function for anomaly scores to be used for computing Shapley values.\n- Proposal of a heuristic relaxation for the characteristic function that is computationally efficient.\n- Demonstration of effectiveness of proposed ASH relaxed characteristic function on real data sets using two different evaluation approaches.\n\n*After author revision:* I have changed Claims and Evidence from No to Yes given the newly added examples and experiment results. My concerns regarding the paper have been addressed.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Major issues:\n- I strongly recommend for the authors to add a case study showing Shapley values computed on one of the real datasets. Perhaps this could be done in the same setting as in Section 5.3, where they compare the attribution performance with that of a supervised classifier. It would be highly useful to see the distributions of Shapley values with the different attribution methods to see how they differ and perhaps why ASH performs well. This can be added without removing content from the current paper and staying within 12 pages of main body.\n- The authors state that analysis of each method's failure is out of the scope of this paper. I agree that a detailed analysis of the type they describe is out of scope; however, an illustration of instances where different attribution methods differ, perhaps as part of the case study I suggest above, would be useful and very informative.\n\nMinor issues:\n- An experiment validating the $O(d)$ time complexity of the heuristic relaxation compared to the $O(2^d)$ complexity without the relaxation would be useful as an addition to the appendix. We can get a limited idea of the empirical time complexity from Table 5, but it's only 2 data points for $d$.\n- In Table 1, it would be good to show also a column with the size of $\\mathcal{D}_{\\text{test}}^{\\text{anom}}$ so that the reader can see how balanced the nominal and anomalous classes are.\n- Why do you only extract U2R attack type from the NSL-KDD data rather than using all of the different attacks?\n", "broader_impact_concerns": "The included statement is reasonable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "YV8exYDS1n", "reviewer": "Reviewer_4agy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\nThe idea of \n\n- applying SV to the anomaly score rather than the prediction function and \n- using the local minimum as the reference point to define the characteristic function of SV\n\nis quite unique. I found the novelty and the originality of the paper very high. The idea alone definitely deserves immediate acceptance to top ML journals like TMLR.\n\n\n**Weakness**\n\nHowever, although this work indeed has the potential to become the first crucial work on SV-based attribution since SV's introduction to the ML community, I’d point out that the treatment after Eq. (3) looks rough. My biggest complaint is that the authors do not show the relationship between (3) and (4). I don’t even understand if it is an approximation or something else. More specifically,\n\n- I couldn’t find any clear description of the choice of dist().\n- I couldn’t find any clear description of the choice of $\\gamma$.\n- The second condition in (4) is not even the average, as the summation runs over $2S$ terms. A clear justification is needed.  \n- No clear justification is provided about mixing the two local minima between those for $\\{i\\}$ and $\\emptyset$.\n- No clear justification is given for the use of the least square “approximation” of SV. I’m not sure if Lundberg’s paper uses it as an approximation. This is not the authors’ fault, but Lundberg’s paper does not provide a clear-cut definition of the characteristic function, and its discussion is logically hard to follow. I do not think it is a good idea to use it blindly without justification.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a new framework for the task of model agnostic (black box) anomaly attribution based on Shapley value (SV). Unlike prior methods that simply use an existing implementation or formula ironically as a black box, the authors look deep into the very definition of SV. In particular, they propose a new definition of SV’s characteristic function that depends on the local minimum of the anomaly score. More specifically, the key ideas are:\n\n1. To use the SV value for the anomaly scoring function rather than the prediction function itself,\n2. To use a characteristic function that depends on a “reference vector”, and\n3. To determine the reference vector as a local minimum point of the anomaly score.\n\nAlthough they propose a well-defined optimization problem in Eq. (3) as the canonical definition of the proposed framework, it is not something they actually used in the empirical evaluation. To handle computational difficulties, the authors introduce two heuristic approaches. Instead of solving the regularized optimization problem (3), they propose to use a combination between the all-variable local minimum and one-variable conditional minima. Also, they use a SHAP-like least squared variant of SV.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "This paper can be accepted as-is. \n\nThis is not a mandatory request at all, but I encourage the authors to address the unclarity listed above. It will improve the readability of the paper significantly. ", "broader_impact_concerns": "Except for very few exceptions, almost all model-agnostic anomaly explanation papers for black-box models ironically use existing attribution formulas/codes as a black box. This paper shines in such unfortunate darkness. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of attribution in anomaly detection, aiming to identify the important features causing anomaly. The feature attribution is studied via adapting the Shapley values, and a new characteristic function as a faster heuristic relaxation. The approach shows performance gains on attributing synthetically generated anomalies. Three reviewers provided assessment reports for this paper, all favoring the technical contributions while proposing major concerns. These issues were well addressed in the revised version, and all reviewers in general agreed that the paper is accetable. The AE oversaw the reviewing process and all evidences, and supported the Accept decision.
Decision: Accept (poster)