Anomaly Detection techniques find application in various domains but they fail to explain anomalous from domain perspective. In this paper, we attempt to provide explanation for anomalousness of a point which in our case is a company having misinformation in its financial statements. We propose 3 novel methods and experiment with a publicly available real dataset of financial statements of 4091 companies listed on Indian stock market. We also propose a novel evaluation method for evaluating significance of generated explanations in absence of the ground truth. We show that our method Explanation using Maximal Isolation (EMI) generates precise and statistically significant explanations as compared to baseline methods.
Anomaly detection (AD) has been considered as a crucial task in various applications. It helps us to identify the scenarios which could lead to possible failure of a system as well as to obtain novel insights about it. The field covers various application domains like fraud detection, intrusion detection, fault detection, failure detection etc. Many times, the users of an application are unable to understand why a particular instance could be termed as anomalous from the domain perspective. For example, in intrusion detection, sudden rise in the CPU and memory usage could be termed as anomalous. However, only by careful analysis of other parameters like network flow, trafic congestion etc. the anomaly can be diferentiated between intrusion or computation expensive process execution. Similarly, in fraudulent Financial Statements (FS) detection, if a company is susceptible of being fraudulent, auditors of FS would prefer to know what fields from the company filings are making that company susceptible of the fraud. Such justifications or explanations help to perform further investigations to know if the company is really fraudulent or it is just a false alarm which would save company’s reputation. Such additional knowledge helps to understand the anomalous nature from the domain’s point of view.
CIKM’22: Advances in Intepretable Machine Learning and Artifical Intelligence (AIMLAI), October 17–21, 2022, Atlanta, Georgia ∗Corresponding author. †These authors contributed equally. nEvelop-O [2], we have attempted to show detection of misinformation from the FS. We take it ahead to provide explanation for the reported companies. We illustrate the technique by performing the experiments on a real dataset.
Contributions of the paper are as follows: • 3 novel methods for explanation generation. • A novel evaluation method for generated explanations in the absence of the ground truth.
The most basic form of explanation for an outlier is the subspace in which the point is highly discriminated from other points. The outlying aspects [3] are identified either by selecting top subspaces with the highest measure of anomalous behavior, called as Score and Search or selecting a small relevant subspace aligned with the traditional feature selection problem of classification called Feature Selection [4]. Authors of [3] used distancebased outlying degree (OD) and a framework of dynamic subspace search, called HOS-miner to determine the subspace in which a query object is an outlier. A heuristic based search framework called OAMiner, developed in [5], searches the subspaces efectively. They rank all subspaces based on a kernel density estimation of a query object in that subspace. Authors of [6] propose density Zscore and iPath as dimensionally unbiased methods of determining outlying aspects and a beam search algorithm to tackle the challenge of search through exponentially work developed in [7] leverages the eficiency of feature selection approaches and the efectiveness and versatility of score-and-search based methods. In first stage, the features are ranked according to the potential to make the point outlying and in second stage score-and-search is performed on a smaller subset of the top ranked « features where is the total number of features.
Local Outliers with Graph Projection (LOGP) [8] deifnes a set of objective functions that learn the local discriminating subspace for a point in the transformed form of a graph. Outlying score of a point is computed as statistical distance of a point to its neighboring points in the transformed subspace. Authors of [9] proposed a novel criteria that measures the probability density function (pdf) associated with attribute value of an outlier with respect to pdf associated with same attribute values of other instances. Lower the pdf, more likely an instance is outlier. Anomaly Contribution Explainer (ACE) [10] and ACE-KL give contributions of each feature as a vector of real numbers. ACE approximates neighborhood of an outlier by generating neighboring points and then tries to fit a linear regression model to those neighbors with a modified loss function. Additional regularizer introduced in ACE-KL model tries to maximize the KL divergence between a uniform distribution and the calculated distribution of contributions. Authors of [11] propose sequential feature explanations (SFE), obtained by solving an optimization problem, wherein features are presented to the users one at a time until a confident judgment can be made about the anomaly.
The Explainer [12] provides expalanation in the form of disjunction of rules learnt by decision trees in random forest for a given anomalous point. Given a set of outliers and corresponding feature set, LOOKOUT [13] produces a set of optimal number of 2-D focus-plots based on the budget provided by the user in such a way that some of the anomalies have maximum anomaly score and are visually incriminated in the plot. Authors propose an approximation algorithm to solve the NP-Hard problem of generating optimal number of plots.
None of the above methods including [14] and [15], perform qualitative evaluation of the explanation in absence of ground truth. Some of the methods are model dependent therefore quality of the generated explanations depends on accuracy of the model. Our method EiForest uses iForest as a data structure and extracts other novel features from it as against using only the path length as scoring mechanism of a subspace as in iPath [6]. Use of only path length limits correctness of the explanations to the accuracy of the iForest algorithm. Rule set produced by our EMI method gives a subspace in -dimensional space where the anomalous point is most isolated and there is no learning involved as against Explainer [12] in which rules are in disjunctive form and decision trees Algorithm 1: EMD input :, , , output : begin s.t. for each ∈ , ⊆
0, ; s.t. 1 ≤ 0 ≤ | |; = 1.0 = ∅ for = 0 to 0 do foreach ∈ 2 and || = do foreach ∈
do = () − \ () ; if > 0 and > + ⋅ then =
∪ ; return
We have a -dimensional dataset = { each ∈ and = { 1, 2, .., } denotes feature set.
Let us consider we have an anomalous instance such that ∈ , which is obtained by some technique unknown to us. The objective is to generate an explanation that makes the point anomalous. could be set of
1, 2, .., } where features i.e. ⊆ or set of rules. dimensional feature vector. is an anomalous company that is susceptible of having misinformation in its FS.
As mentioned earlier, is dataset of companies leading and containing . Refer Table 1 for detailed dewhere each company is represented in the form of 18- scription. We construct the set of summary vectors
We sort all the points in in descending order of their Mahalanobis distance from the mean vector of . () , defined as
Mahalanobis rank, is the rank of the point ∈
in this sorted list. For any proper subset ⊂ of features, the function \ () is similarly defined, except that the Mahalanobis distance for points in is computed after removing values of all features in from every point in . Note that a lower (smaller) rank indicates that the point is far from the mean vector in terms of Mahalanobis distance.
Potentially, explanation ⊆ can be any set from diference is greater than a predefined threshold of power set 2 . Algorithm EMD produces set of candidate explanations for such that for each set ∈ , rank where and are mean and standard deviation of all rank diferences; and hence explains why is anomalous. We We compute the belief of an explanation ∈ by using the standard deviation of the diference in () and \ () for all the instances. We compute the belief as (, ) = \ ()− ()
of standard deviations the rank diference \ ()− () is away from the mean of all the rank diferences for . In other terms, it is the Mahalanobis distance of the rank diference for from the mean of all rank diferences. Each set and it’s respective belief value is given as an input to Dempster-Shafer evidence combination [16] method. Output set with highest belief given by this method is considered as valid . 4.2. Explanation using iForest (EiForest) iForest [17] recursively partitions the data by randomly selecting the features and its values for splitting. The data instances which get isolated in earlier splits are considered as anomalies. We tried to exploit this randomization concept with the help of iForest. We constructed a forest of trees. Let be set of paths that lead to . For a given instance we found the set of features ⊆ that appeared on at least one path in , leading to isolation of . For each variable ∈ we constructed a 8-dimensional summary feature vector using the paths for all points for all variables in the dataset. We then compute the Mahalanobis distance ( ) from the mean of for each ∈ . Once we get the distances for all ∈ , the top variables are selected as an explanation when sorted in the decreasing order of distances.
We propose a method based on Integer Linear Programming (ILP) that isolates an anomalous point to maximum possible extent. The explanation generated by EMI is conjunction between specified number of conditions. These conditions when applied as filters on the entire dataset, would minimize the number of points other than the anomalous point which satisfy all the conditions. Given set of features and an anomalous point which is to be explained, the explanation would be in the form ( (≤ | ≥) and ⊂ ; || = ); ∈
where is value of for feature . These conditions can be considered as an explanation for anomalous nature of the point + ⋅ , , because they describe in what way the point is different from the rest of the points in the data-set. Table 3 describes the ILP formulation in detail. Constraints 3, explanation. The objective function maximizes the number of such points. Efectively, it minimizes the number of other points which satisfy all the conditions in the explanation along with z which is the anomalous point
In this paper, we use the dataset similar to the one used in [2]. FS and other financial documents such as annual restrict size of candidate set to 0. If no such subset is 4, 5, and 6 enforce that y[] becomes 1 if and only if the ℎ point breaks at least one condition used in the . is nothing but the number to be explained.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 size matrix representing whether other points have lower values than 5.3. Evaluation using ground truth •x1: length binary array such that x1[] = 1 implies that the ℎ feature is included verse comments from auditors are labeled as anomalous3. •x2: length binary array such that x2[] = 1 implies that the ℎ feature is included Variables which are mentioned in the auditor comments •y[] = 1 only if ∃ (( 1[, ] = 1) ∧ ( x1[] = 1)) ∨ (( 2014 and extracted 18 variables from their balance sheet and income statement. Refer table 2 for their summary statistics (values are in units of Rupees 10 million).
We compare our methods with SHAP [18] and LIME [19] which are widely used in the literature of explainability for the task of classification and regression. To generate explanation for the task of anomaly detection, we created a labeled dataset of 282 companies. Among which, 49 companies having ‘qualified audit opinion’ were identiifed as anomalous and marked as class label ‘1’. Other companies were labeled with class label ‘0’. Then we trained a Random Forest Classifier on the labeled dataset and generated explanations for the anomalous instances. We chose 10 qualified companies as query points and generated explanations using all the methods. Parameter settings: Parameter values for EMD algorithm are set as = 1.0 and 0 = 3. For EiForest, we set = 1000 and retain top 5 features ( = 5 ). For EMI, first we experiment with = 2 . If the point is not suficiently isolated we experiment with = 3 . For SHAP and LIME we have retained top 5 features having non-negative weight to maintain uniformity in the results. 2https://www.moneycontrol.com/ 3Annotated ground truth data can be made available on request We have extracted audit reports for 4091 companies as mentioned in section 5.1. Companies which receive adfor those companies and are also part of the 18 variables, are extracted manually. These extracted variables act as ground truth or gold standard. Refer table 4 for generated explanations along with ground truth. Variables that are part of the ground truth are highlighted.
To judge the accuracy of the generated explanation, we consider precision , recall and 1 measure for each explanation. We computed the , and 1 measure for each generated explanation using the ground truth we extracted manually. Results of this evaluation are presented in table 5. This choice of selecting top 5 features for SHAP, LIME and EiForest afects the precision values. However, what should be optimal length of the explanation can be disputable. It can be observed that SHAP and LIME are able to detect at least 1 variable for most of the companies (8 out of 10 for both SHAP and LIME). EMI has given precision of 0.33 or above for 6 out of 10 companies. SHAP and LIME have the highest recall. However, average and 1 is highest for EMI method.
Few points that are worth mentioning are as follows: A company can be susceptible of having misinformation because of multiple reasons. Not all reasons can be captured in the given set of 18 variables. Also, we have manually extracted variables from audit reports based on our knowledge of the domain. Any domain supervision can improve the ground truth. Each method of explanation generation can discover diferent aspects of misinformation. Hence, considering ensemble of all results is also possible.
We propose a novel method to evaluate quality of the generated explanations in the absence of ground truth. The intuition behind this method is that the anomalousness of a company should be significantly dependent on the variables given in the explanation. So a better explanation would contain the variables which have the ′. Therefore, Δ, () = () − ( ′). For example, for Winsome Diamond if original anomaly score using anomaly detection technique is 0.8 and score obtained after perturbing variables 5 and 14 (explanation pro= 0.8 − 0.6 = 0.2. In our experiments we have used autoencoder based anomaly detector from pyOD package [20]. Practically, any anomaly detection technique can be used. Depending on how well explains , Δ, can be positive, negative or even zero. Positive value indicates that ′ is more ‘normal’ than and negative () 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10
Sr no.
Company 1 2 3 4 5 6 7 8 9 10
Winsome Diamond Ashapura Mine Western Ministi Oudh Sugar Mill Sarda Papers Nicco Uco Fin
Atlanta Samtel Color Aruna Hotels CFL Capital
Avearge Winsome Diamond Ashapura Mine Western Ministi Oudh Sugar Mill Sarda Papers Nicco Uco Fin
Atlanta Samtel Color Aruna Hotels CFL Capital
Total (1,1) (0,0) (0,1) (0,0) (0,0) (0,0) (0,0) (1,1) (0,1) (0,1) (2,5) vided by EMI) is 0.6 then Δ{ 5, 14}, (Winsome Diamond) If the p-value is less than significance level = 0.05 , the null hypothesis is rejected and Δ,
() is accepted to be statistically significant and hence is a good explanation for the anomalousness of the selected company. In table 6, we mark 1 as the first value of each tuple wherever explanation obtained is found to be significant with respect to this method.
EiForest 0.00 0.50 0.25 0.00 0.50 0.33 0.00 0.33 0.33 0.00 0.23 Δ, 1 0.00 0.29 0.22 0.00 0.44 0.25 0.00 0.25 0.33 0.00 0.18 0.50 1.00 0.00 0.00 0.33 1.00 0.00 0.50 0.00 0.50 0.38
EMI 0.50 1.00 0.00 0.00 0.25 0.67 0.00 0.33 0.00 1.00 0.38 1 0.50 1.00 0.00 0.00 0.29 0.80 0.00 0.40 0.00 0.67 0.37 value indicates other way round. Zero implies that there is no change in the nature of the point. To determine whether the diference
() , is statistically significant or not, we use the following two methods. 5.4.1. Method A: Comparison with “normal”
companies In this method, we judge the efect of variable perturbation on other companies.
We randomly choose 30 companies = {| ≠ } and compute Δ,
() for all these companies by perturbing variables in . Note that, here we are checking for given by some method for an anomalous company , e.g. { 5, 14} for Winsome diamond. So we perturb values of { 5, 14} for these 30 companies and obtain the score diference values as set . Therefore, statistical significance of = {Δ, Δ, ()| ∈ }; |
| = 30. The () with respect to is determined using one-sided one sample -test where the null and alternate hypotheses are as follows: 0 : mean of = Δ, () 1 : mean of < Δ, ()