# Post-discovery Analysis of Anomalous Subsets

Isaiah Onando Mulang’
IBM Research Africa
<EMAIL_ADDRESS>
&William Ogallo
IBM Research Africa
<EMAIL_ADDRESS>
&Girmaw Abebe Tadesse
IBM Research Africa
<EMAIL_ADDRESS>
&Aisha Walcott-Bryant
IBM Research Africa
<EMAIL_ADDRESS>

###### Abstract

Analyzing the behavior of a population in response to disease and
interventions is critical to unearth variability in healthcare as well as
understand sub-populations that require specialized attention, but also to
assist in designing future interventions. Two aspects become very essential in
such analysis namely: i) Discovery of differentiating patterns exhibited by
sub-populations, and ii) Characterization of the identified subpopulations.
For the discovery phase, an array of approaches in the anomalous pattern
detection literature have been employed to reveal differentiating patterns,
especially to identify anomalous subgroups. However, these techniques are
limited to describing the anomalous subgroups and offer little in form of
insightful characterization, thereby limiting interpretability and
understanding of these data-driven techniques in clinical practices. In this
work, we propose an analysis of differentiated output (rather than discovery)
and quantify anomalousness similarly to the counter-factual setting. To this
end we design an approach to perform post-discovery analysis of anomalous
subsets, in which we initially identify the most important features on the
anomalousness of the subsets, then by perturbation, the approach seeks to
identify the least number of changes necessary to lose anomalousness. Our
approach is presented and the evaluation results on the 2019 MarketScan
Commercial Claims and Medicare data, show that extra insights can be obtained
by extrapolated examination of the identified subgroups.

##  1 Introduction

Healthcare is known for its variations in the population, treatment, and
outcome domains [1, 2]. Examples of such variations include diversity in the
population (e.g., a particular subgroup being vulnerable or at high risk),
heterogeneous effects of a treatment regime across a given population, or
different interventions across population segments in response to a specific
disease.

To improve clinical practice and the quality of interventions, there is a need
to trace and reconstruct such variations. However, large-scale observational
health data and longitudinal clinical records are characterized by complex
interactions of patient characteristics and interventions, making challenging
to analyze and interpret non-random variations of patient populations, care
delivery, and outcomes. Manual approaches heavily rely on domain expertise
that requires pre-assumption of features responsible for variations and lack
scalability for large and complex interactions expected in clinical data. In
addition, manual approaches cannot readily unearth complex, non-obvious
variations in healthcare.

Fortunately, researchers have sought to develop automatic and data-driven
approaches for the scalable discovery of differentiated patterns of care.
Particularly, machine learning techniques in the anomalous pattern detection
literature could be employed to encode variations in healthcare. Subset
scanning [3, 4] is one of these approaches that aim to identify anomalous
subgroups in a population with divergent characteristics compared to the
expected baseline in an efficient manner. In subset scanning, anomalousness is
quantified by a scoring function, typically a log-likelihood ratio statistic,
that is maximized over the subsets in a multidimensional array to identify the
subset with the highest score [3]. This scoring function must satisfy the
Linear-Time Subset Scanning (LTSS) so that the search is efficiently conducted
in linear time [3].

The typical input to a subset scanning algorithm is a set of
discrete/discretized features e.g. Gender: Male/Female, Race:
Black/Brown/White, Smoking: Yes/No, and Weight: Low/Mid/High; and target
variable of interest e.g. Mortality. The typical output of subset scanning
consists of 3 main items: 1) the highest scoring (most anomalous) subset
characterized by specific feature values (e.g. Gender: Female, Race:
Black/White, Smoking: Yes, and Weight: High), (2) the score of the highest-
scoring subset, and (3) the empirical p-value evaluating the significance of
the identified subset. This output is thus merely descriptive and there is
still a significant concern related to the characterization of the findings
into practices, particularly in clinical care. The characterization includes
understanding the dynamics associated with anomalousness of a particular sub-
population in response to variation in patient features. In other words, there
is an implicit next step necessary to assist better utilization of these
methods and inform actions.

In this paper, we propose the post-discovery analysis of anomalous subsets
aimed at enhancing the clinical usefulness of subset scanning results and
triggering a paradigm shift from description to actionable insights. To this
end, we tackle two major research questions as our contributions:

  1. 1.

Which of the features (and their values) describing the identified subset have
the greatest impact on the anomalous score?

  2. 2.

What is the smallest change in feature values that causes a loss in
anomalousness?

This paper describes our initial step towards a larger agenda of post-
discovery analysis of anomalous subsets. Our proposed solution involves a two-
step approach that first identifies the features and feature values that
contribute most significantly to the anomalous behavior of the identified
subset, then performs cross-substitution of these feature values to attain a
significant drop in anomalousness. The rest of this paper is structured as
follows: Section 2 offers a summary of related work followed by the details of
the proposed method in Section 3. The data and experiments are described in
Section 4, finally, Section 5 concludes and offers future directions.

##  2 Related Work

Although our work is an initial step towards post-discovery analysis, being
the first proposal in this direction, it lies in the intersection between two
fields namely: Subgroup analysis and counterfactual explanations. We view our
work as a special form of counterfactual analysis that operates on
unsupervised scenarios. Hereafter, we discuss existing work in these two areas
in literature.

###  2.1 Subset Scanning

Subset Scanning algorithms [3, 5, 6] identify the subset of records with the
most significant difference in the distribution of the observed outcome
compared to the expected outcome and have been applied across a variety of use
cases. Neil et al. applied subset scanning in disease surveillance to detect
geolocations and data streams suggestive of emerging outbreaks [3, 4]. Zheng
et al. developed a subset scanning approach for detecting predictive bias in
binary classifiers [7]. McFowland et al. proposed a subset scanning algorithm
for detecting heterogeneous treatment effects in clinical trial data [8].
Somanchi et al. developed the anomalous patterns of care scan that combines
propensity score modeling with subset scanning to enable anomalous pattern
detection in anomalous pattern detection in observational health data [5].
Each of these methods optimizes a scoring function, such as a log-likelihood
ratio statistic, over all subsets in a dataset and selects the highest scoring
subset. The scoring function is constrained to a mathematical property
referred to as Linear-Time Subset Scanning (LTSS) that enables the search to
be conducted in linear as opposed to exponential time [3].

###  2.2 Counterfactual Analysis

Traditionally, counterfactual explanations have been employed to help
understand the limitations of machine learning methods. To this end, methods
for counterfactual explanations try to find an example that is as close as
possible to the data points in the training set of a model. Counterfactual
explanation methods can either be model-specific or model-agnostic. Model-
specific methods utilize the internal training characteristic (e.g., the
hyperparameters) of the underlying machine learning model [9, 10, 11]. Model-
agnostic methods separate the explanations from the machine learning model.
They encompass functionality that apply to any arbitrary models[12, 13, 14,
15], generally by only accessing the prediction function of a fitted model
[16]. Schölkopf et. al. [17] discuss causal representation learning as an
avenue for counterfactual explanation. These methods operate on supervised
machine learning models and attempt to find examples close to one of the data
points.

In our study, the discovery methods that identify the subgroups (e.g.
anomalous subsets) are inherently model-agnostic search algorithms. We work
with a similar research question: What features describing the individual
would need to change to achieve the desired output? [13] However, we aim to
identify the exact changes that can be made to the characteristics of a
subgroup of individual to achieve a desired output (in our case, a significant
change in the anomalous score). Our objective is therefore slightly different
from traditional counterfactual explanation, in two ways: i) Given a subgroup
that has been identified as anomalous (e.g, having a significantly higher rate
of an outcome than a global average), we seek to find the least number of
perturbations to the subgroup’s features and feature values of that would lead
to loss of anomalousness; and ii) As opposed to finding the counterfactual
example, we find the feature values from the complement subset.

##  3 Methods

Figure 1 illustrates our proposed pipeline for the Post-Discovery Analysis of
Anomalous Subsets. The approach takes in as input, an anomalous subset
together with the original dataset and aims to identify feature substitutions
that result in loss of anomalousness. It consists of two major subtasks
namely: i) Feature relevance ranking: takes an anomalous subset and identifies
the most significant features and feature values contributing to anomalousness
; ii) Cross-substitution: Identifies the possible permutations of feature
values within the anomalous subsets by scoring minimally altered subsets
obtained through replacing values of the anomalous features with alternatives
from the nonanomalous set . In this section, we describe these steps in
detail.

Figure 1:  Pipeline for Post-Discovery Analysis of Anomalous Subsets

###  3.1 Problem formulation

The post-discovery analysis task assumes that there is an output from prior
discovery search through a given dataset that produced a descriptive anomalous
subset, and aims to identify the extent to which the feature values can be
perturbed to achieve a loss of anomalousness. Formally, if we let
$\mathcal{D}=(X,Y)=\\{(x_{i},y_{i})|i=1,2,\cdots,N\\}$ denote a dataset of
length $N$, where each data-point $x_{i}$ is characterized by a set of $M^{i}$
features $\mathcal{F}^{i}=[f^{i}_{1},f^{i}_{2},\cdots,f_{M^{i}}]$ such that
the whole feature space set $\mathcal{F}$ in $\mathcal{D}$ is given by
$\bigcup\limits_{i=1}^{N}\mathcal{F}_{i}$ and $y_{i}$ represents the outcome
label, there exists, by definition, a set
$X^{a}=\\{(x^{a}_{i}|i=1,2,\cdots,P\\}$ s.t. $P\leq N$ and $X^{a}\subseteq X$,
called the anomalous subset, and characterized by the anomalous feature values
$\mathcal{F}^{a}=\\{f^{a}_{j}\\}_{j=1}^{Z}$, $Z<M$ and the complete anomalous
features description is
$\hat{\mathcal{F}}^{a}=\bigcap\limits_{z=1}^{Z}(\bigcup\limits_{h=1}^{H_{z}}\hat{f^{a}_{zh}})$,
where $\hat{f^{a}_{zh}}$ represents the $h^{th}$ value of the $z^{th}$ feature
in $\mathcal{F}^{a}$ that contributes to the anomalousness of $X^{a}$, e.g.,
$f^{a}_{1}=$ Smoking and $\hat{f^{a}_{1,1}}=$ Yes. The tuple
$A=(X^{a},\mathrm{s}^{a}=\Gamma(X^{a}),\mathcal{O}^{a})=S(\mathcal{D}))$ is
the output of subset scanning function $S(\mathcal{D})$, where $\Gamma(X^{a})$
is a scoring function that obtains the anomalous score $s^{a}$, and
$\mathcal{O}^{a}$ is a set containing the measures of effect such as the odds
ratio and the p-value. The post-discovery analysis is denoted as
$A^{norm}=(X^{norm},\Gamma(X^{norm}),\mathcal{O}^{norm})=g(\beta(A),\mathcal{D})$
where $g(.)$ is a cross-substitution function, that performs substitutions of
the form $[\hat{f^{a}_{j}}\rightarrow f^{\prime}_{l}]$, where
$\hat{f^{a}_{j}}\in\hat{\mathcal{F}}^{a}$ and
$f^{\prime}_{l}\in(\hat{\mathcal{F}}\setminus\hat{\mathcal{F}}^{a})$. The
function $\beta$ is a feature selection routine, that identifies a set of
features that most contribute to anomalousness. The output
$\hat{\mathcal{F}}^{norm}\subset(\hat{\mathcal{F}}\setminus\hat{\mathcal{F}}^{a})$
is a minimalistic set of feature values that substitute in the anomalous
subset to cause a loss in anomalousness.

###  3.2 Multi-Dimensional Subset Scanning(MDSS)

To corroborate our post-discovery analysis approach to insightful analysis of
anomalous subgroups, we apply the Multi-Dimensional Subset Scanning(MDSS) [18]
from the anomalous pattern detection literature. Specifically, we use
Automatic stratification (AutoStrat), a version of MDSS where the deviation
between average outcomes in $\mathcal{D}$ ($\mu_{D}$) and each sample
($\mu_{i}$) is evaluated by maximizing a Bernoulli likelihood ratio scoring
statistic, $\Gamma(S)$. The null hypothesis assumes that the likelihood of the
outcome in each sample $x_{i}^{r}\in\mathcal{D}^{r}$ similar to expected
($\mu_{g}$), i.e., $H_{0}:odds(y_{i})=\frac{\mu_{g}}{1-\mu_{g}}$; while the
alternative hypothesis assumes a constant multiplicative increase in the
outcome odds for some given subgroup,
$H_{1}:odds(y_{i})=q\frac{\mu_{g}}{1-\mu_{g}}$ where $q>1$. The scoring
function, $\Gamma(S)$ for a subset, $S$, which contains $N_{S}$ samples, is
computed as:

$\Gamma(S)=\max_{q}log(q)\sum_{i\in S}y_{i}-N_{S}*log(1-\mu_{g}+q\mu_{g})$

Consequently, subsets in which the average of $y_{i}$ ($\mu_{y}$) is greater
than $\mu_{g}$ will have higher scores. Subset selection is iterated until
convergence to a local maximum is found, and the global maximum is
subsequently optimized using multiple random restarts. Once the differentiated
subset of samples $X^{a}$ is identified using MDSS, empirical p-value (via
randomization testing) is computed to evaluate the significance of the
differentiation. Moreover, subset characterization is conducted to provide
interpretation of these anomalous features $\mathcal{F}^{a}$ and subset
$X^{a}$.

###  3.3 Quantifying Feature Relevance to Anomalousness of a Subset

The anomalous subsets produced by the subset scanning approaches described
above are characterized by features and feature values contributing to the
anomalousness. The intuition behind feature selection is that not all feature
values contribute equally to the anomalousness of a subset, measured by the
anomalous score. The feature selection, therefore, strives to identify the set
of features and feature values in the anomalous subset that induce the
greatest impact on the anomalous score. Such features are prime candidates for
analysis as a change in their values has a higher likelihood of resulting in a
significant drop in the anomalous score. Taking the Output tuple
$A=(X^{a},\mathrm{s}^{a},\mathcal{O}^{a}))$ from a discovery method, and the
dataset $\mathcal{D}$. The feature selection routine $\beta(.)$ proceeds by
first obtaining the marginal expected values of the results conditioned on
each feature value. Therefore, for each anomalous feature value,
$\hat{f^{a}_{j}}$, we calculate its expected value as
$e_{j}=\mathbb{E}(f^{a}_{j})=\frac{\sum_{i}(y_{i}|f^{i}_{j}=f^{ai}_{j})}{|{x_{i}|f^{i}_{j}=f^{ai}_{j}}|}$.
We then calculate the deviations of $e_{j}$ from the mean expected value of
the dataset $\bar{e}=\frac{\sum_{i}y_{i}}{|\mathcal{D}|}$, the deviation
$\delta_{j}=e_{j}-\bar{e}$. In the next step, we rank the feature values based
on their calculated deviations. $rank(\hat{f^{a}_{j}})<rank(\hat{f^{a}_{k}})$
if $\delta_{j}>\delta_{k}$ . A threshold value ($\delta_{0}$) is used to
select a set of most deviating feature values, to form the selected features
$\mathcal{F^{R}}={\hat{f^{a}_{j}}|\delta_{j}>\delta_{0}}$.

Input: $\langle
X^{a},s^{a},\mathcal{O}^{a},\mathcal{D},\mathcal{F^{R}}\rangle$; $\langle
X^{a}\leftarrow$ anomalous subset; $\mathcal{D}\leftarrow$ dataset;
$\mathcal{F^{R}}\leftarrow$ selected feature set

Output: ($X^{norm},\mathrm{s}^{norm},\mathcal{O}^{norm}$)

$X^{norm}\leftarrow X^{a}$

$\alpha\leftarrow\alpha^{a}\in\mathcal{O}^{a}$

$\mathcal{F}^{\prime}\leftarrow(\mathcal{F}\setminus\mathcal{F}^{a}$)

$N\leftarrow|\mathcal{F^{R}}|$

$Q=enqueue(\mathcal{F^{R}})$

while  _$s^{norm} >Threshold$ and $Q\neq\emptyset$_ do

$f^{r}=$ Q.dequeue

$f^{\prime r}\leftarrow f^{\prime}\in F^{\prime}|(\exists f\in F|f=f^{r}\cup
f^{\prime}r)$

for  _each $\hat{f^{r}_{i}}\in f^{r}$_ do

for  _each $\hat{f^{\prime r}_{j}}\in f^{\prime r}$_ do

$X^{norm}\leftarrow(X^{norm}\;|\;[\hat{f^{r}_{i}}\rightarrow\hat{f^{\prime
r}_{j}}])$

$s^{norm}\leftarrow\Gamma(X^{norm})$ // score from a Bernoulli likelihood
scoring function $\Gamma(.)$

$\Gamma(X^{norm})=\max_{q}log(q)\sum_{i\in
S}y_{i}-|X^{norm}|*log(1-\mu_{g}+q\mu_{g})$

$\alpha\leftarrow p\\_value(s^{norm})$

$Oddr\leftarrow oddsRatio(s^{norm},H_{0})$

$\mathcal{O}^{norm}=(\alpha,Oddr)$

return _( $X^{norm},\mathrm{s}^{norm},\mathcal{O}^{norm}$)_

Algorithm 1 Cross-Substitution

###  3.4 Cross Substitution

After identifying the features and feature values that are most relevant to
the anomalousness of a subset, we then perform the cross substitution process.
The aim is to find minimal changes in the anomalous subset that results in a
significant drop in the anomalous score. This is achieved by drawing values
from the compliment set to substitute feature values in the anomalous subset.
Assume, for example, an anomalous subset described in Table2 and its
complement described in Table2.

Table 1: Anomalous Subset Feature | Value(s) | E.g. | E.g.
---|---|---|---
|  | Feature | Values
$f^{a}_{1}$ | $\hat{f^{a1}_{1}}$ | Gender | Female
$f^{a}_{2}$ | $\hat{f^{a2}_{1}},\hat{f^{a2}_{2}}$ | Race |  Black, White
$f^{a}_{3}$ | $\hat{f^{a3}_{2}}$ | Smoking | Yes
$f^{a}_{4}$ | $\hat{f^{a4}_{2}}$ | Weight | High

Table 2: Complement Subset Value(s) | E.g. | E.g.
---|---|---
| Feature | Values
$f^{\prime 1}_{1}$ | Gender | Male
$f^{\prime 2}_{1}$ | Race | Brown
$f^{\prime 3}_{1}$ | Smoking | No
$f^{\prime 4}_{1}$,$f^{\prime 4}_{2}$ | Weight |  Low, Mid

The possible substitutions include: {$[\hat{f^{a}_{1}}\rightarrow f^{\prime
1}_{1}]$, $[\hat{f^{a2}_{1}}\rightarrow f^{\prime 2}_{1}]$,
$[\hat{f^{a2}_{2}}\rightarrow f^{\prime 2}_{1}]$,
$[(\hat{f^{a2}_{1}},\hat{f^{a2}_{2}})\rightarrow f^{\prime 2}_{1}]$,
$[\hat{f^{a3}_{2}}\rightarrow f^{\prime 3}_{1}]$,
$[\hat{f^{a4}_{2}}\rightarrow f^{\prime 4}_{1}]$,
$[\hat{f^{a4}_{2}}\rightarrow f^{\prime 4}_{2}]$ }. A single substitution
results in a new subset that is different from the anomalous subset. These
perturbations are recursively carried out until we exhaust the space of
possible substitutions. If this space is vastly complex, the results of the
feature selection phase become invariably important.The cross-substitution
therefore begins alteration in order of the feature ranking obtained from the
feature selection. Each of the generated subsets are then scored with same
scoring function used by the discovery method $\Gamma(.)$ (e.g. Bernoulli
likelihood ratio scoring statistic). This scoring aims to generate new
measures of effect $\mathcal{O}$. Statistical significance test is used to
determine whether the new subset loses the anomalousness (typically a p-value
statistic or odds ratio is used, obtained i similar procedure as described in
section 2). The stopping criterion is attained when the statistical
significance of a subset surpasses a given threshold. Algorithm 1 elaborates
the cross-substitution analysis.

##  4 Experiments and Results

To validate our proposed methodology, we conducted a study whose objectives
were twofold. First, we aimed to identify the subpopulation of osteoarthritis
of the knee (OA Knee) with the most evidence of having higher-than-expected
rates of major joint replacement (MJR) surgeries. Second, we aimed to identify
the smallest perturbations in the characteristics of the identified anomalous
subset that resulted in a significant loss of anomalousness.

###  4.1 Dataset and Experimental Setup

We analyzed the 2019 MarketScan Commercial Claims and Medicare data in the IBM
MarketScan Research Databases (https://www.ibm.com/products/marketscan-
research-databases). The database is fully deidentified, hence this study did
not require Institutional Review Board approval. We defined our target cohort
as newly diagnosed OA Knee patients receiving outpatient services in 2019; and
our outcome cohort as outpatient OA Knee patients who underwent any MJR
surgery in 2019. The final analytic dataset consisted of $337,078$ OA Knee
patients, of whom $13,651$ ($3.9\%$) had MJR surgeries.

We extracted 5 discrete features with different cardinalities as follows: age
group (18 to 34, 35 to 44, 45 to 54, 55 to 64, 65 and Older), gender (Female,
Male), region (North Central, Northeast, South, Unknown, West), metropolitan
statistical area (Rural, Urban), and employment status (Active Full Time,
Active Part-Time or Seasonal, COBRA Continuee, Early Retiree, Long Term
Disability, Medicare Eligible Retiree, Other/Unknown, Retiree (Status
Unknown), Surviving Spouse/Dependendant). We defined the observed outcome as a
binary indicator variable $y_{i}$ such that $y_{i}=1$ for OA Knee patients who
underwent an MJR surgery, and $y_{i}=0$ otherwise. We defined the expected
outcome as a simple mean of the observed outcome. Accordingly, our final
analysis dataset consisted of 5 features, 1 observed outcome, and one expected
outcome.

###  4.2 Identification and characteristics of the highest scoring (most
anomalous) subset

We used our automatic stratification approach to identify the highest-scoring
subset with the most evidence of having higher rates of MJR surgeries than the
global average in our dataset. To correct for multiple hypothesis testing and
estimate the statistical significance of the identified anomalous subset, we
used parametric bootstrapping to compute the empirical p-value of the
subset[6].

Using this approach, we discovered that OA Knee patients who are 55 to 64
years old, reside in the West, North Central or South regions of the United
States, and have an employment status as Full-time, Medicare retiree, Early
Retiree, COBRA Continue, or Long Term Disability, were most likely to undergo
MJR surgeries. Among this subpopulation consisting of $135,115$ OA Knee
patients, the rate of MJR surgeries was significantly higher ($6\%$ in the
subpopulation compared to $3\%$ in the complement subpopulation; odds ratio
2.09, $95\%$ confidence interval, 2.02 to 2.17, p-value <0.001).

###  4.3 Post-discovery characteristics of the highest scoring (most
anomalous) subset

To perform post-discovery analysis, we first determined the relevance of
features to the anomalous score. For the MJR dataset, the expected value of
the output in $\mathcal{D}$ was $\bar{e}=0.0389$. The expected value of the
anomalous subset was $e^{a}=1.0$, denoting that all records with the
combination of features in the anomalous subset underwent MJR surgery. We
proceeded by calculating the expected output for each feature-value in the
anomalous subset. For example in the anomalous subset, one of the feature
values for the feature Employment Status (EESTATU) was "Medicare Retiree". We
found that the expected value of the this feature value in the dataset is
$e_{1}=0.057$.

Consequently, we calculate two deviation statistics: i) A subset deviation:
deviation of the feature value from the anomalous subset
$\delta_{1\\_s}=e_{1}-e^{a}=-0.943$. ii) Global deviation: deviation of the
feature value from the expected value of the dataset
$\delta_{1\\_\mathcal{D}}=e_{1}-e_{\mathcal{D}}=0.018$. The deviation ratio of
the two deviations
$\delta_{r1}=\frac{\delta_{1\\_s}}{\delta_{1\\_\mathcal{D}}}=-52.21$ is then
used to score and rank each feature value against the other feature values in
the anomalous subset.

Table 3 show the results of the feature relevance and the cross-substitution
steps respectively. In the feature relevance stage, we observe that the
feature values with a negative deviation ratio are more relevant than a
feature with positive deviation ratios. Overall the feature values with larger
negative ratios are less important than those with lower negative ratio
scores. For our MJR use case, the ranking of feature relevance is therefore as
follows: 1\. Employment Medicare Retiree, 2\. Early Retiree, 2\. Early
Retiree.

Table 3: Feature Relevance Ranking

Feature | Value | D.R
---|---|---
EESTATU | Medical Retiree | -52.21
EESTATU | Early Retiree | -62.27
EESTATU | L.T Disability | -78.06
EESTATU | COBRA Continue | -91.79
REGION | West | -91.96
AGEGRP | 55-64 | -92.20
REGION | N. Cent | -92.95
EESTATU | Full Time | 15293.85
REGION | South | 798.75

In the Cross-Substitution stage, we perturbed the anomalous subset by changing
feature values. Of note is that when we cross-substitute a feature value from
the complement for an anomalous feature value, we effectively create a new
subset. Consequently, we calculated a new anomalous score $s^{a}$, the
empirical p-value of the score, and the odds ratio of the outcome in the new
subset compared to its complement. For example, in the MJR dataset, the
anomalous subset exhibited a score of $500.22$, empirical p-value $0.019608$,
and an odds ratio of $2.09$. By substituting the employment status value
"Medicare Retiree"  in the anomalous subset with "Other Unknown"  in the
complement subset, we obtain new subset with anomalous score of $465.92$,
empirical p-value of $.019608$, and an odds ratio of $2.20$. These statistics
are obtained using the same scoring method used in the discovery stage to
allow for consistency in comparison. Table 4 shows the post-discovery scores
for single substitutions of the two most significant anomalous feature values.
Although the p-values stay constant as seen in figure 2, we observe a
considerable degradation of the anomalous score and the Odds Ratio.

Table 4: Observing Changes in Anomalous Scores for Substituting two Feature Values Feature Value | Substitute | O_Score | N_Score | O_OR | N_OR
---|---|---|---|---|---
Medicare Retiree | Other/Unknown | 500.22 | 465.92 | 2.09 | 2.20
Medicare Retiree | Part Time | 500.22 | 477.93 | 2.09 | 2.05
Medicare Retiree | Retiree (Status Unk) | 500.22 | 482.87 | 2.09 | 2.05
Medicare Retiree | Spouse/Dependent | 500.22 | 483.34 | 2.09 | 2.06
Early Retiree | Other/Unknown | 500.22 | 352.94 | 2.09 | 1.86
Early Retiree | Part Time | 500.22 | 360.09 | 2.09 | 1.81
Early Retiree | Retiree (Status Unk) | 500.22 | 364.57 | 2.09 | 1.82
Early Retiree | Spouse/Dependent | 500.22 | 365.37 | 2.09 | 1.82

Figure 2 portrays the effects of making substitutions to single feature
values. Two measures of effect are plotted namely: the statistical p-value of
the anomalous score, and the odds ratio. For the single substitutions, we
observe that the p-value statistic remains relatively the same for most
feature value perturbations. However there is a few single substitutions that
cause a statistically significant change in the anomalous score namely, the
substitutions on the feature: AGEGRP: 55-64 -> 18-34, 55-64 -> 35-44, 55-64 ->
45-54, 55-64 -> $\geqslant 65$. From this result we can conclude thus: "if the
sub-population that belong to the anomalous subgroup had been changed form the
specific age group 55-64 to the ages -> 18-34, 45-54, $\geqslant 65$, there
would not have been a major joint replacement surgery. Note that single value
perturbations to the most relevant feature: Medicare Retiree did not cause any
statistically significant change to the anomalous score. This can be
attributed to the fact that the feature employment status (EESTATU) is multi-
valued in the anomalous subset, a single change in one of the feature values
has little effect especially since there are 3 more feature values considered.
We expect that higher combination substitutions will reveal better insights
into this phenomenon. The odds ratio, on the other hand, indicates a variation
of the score from the substitutions. For example the odds ratio for 55-64 ->
$\geqslant 65$ is relatively higher than 55-64 -> 18-34 meaning that the
former is more likely to occur in this dataset as opposed to the latter.
Similarly, the substitution: Medical Retiree -> Other Unknown, has a very high
odds ratio, attesting to the possibility of such a change in this dataset,
albeit with no change in the statistical significant measure (Already
explained).

Figure 2: Plotting Cross-Substitution of Single Feature Values in the
Anomalous Subset against the two Measures of Effect : P-Value and Odds Ratio

##  5 Conclusion

In this paper, we discuss a new view to interpreting population responses to
disease interventions, that has the potential to improve clinical practice, As
well as assist in understanding the output of subgroup analysis methods like
the Autostrat. The post-discovery analysis seeks to unearth insights presented
in the otherwise descriptive discovery methods outputs, by performing
sufficient perturbations to the feature values. The aim thereof is to obtain
the smallest changes that can lead to a loss of anomalousness. As avenues for
extension, we view our method for determining feature relevance that uses
expected value weighting as a pointer characterization technique that can be
extended by investigating other statistical measures related to the features
in the identified subset. In addition, our current experiments on cross-
substitution perform only single substitutions of the feature values. This
leaves an avenue for improvement, by considering the space of all possible
combinations of feature values and substitutions. Such an approach would
require consideration of the cost and complexity of cross-substitution. Akin
to the work in the Subset Scanning literature, we envisage the need for an
approach that reduces the search in this space to Linear Time. This work lays
a foundation for the discussion concerning the design of interventions, such
post-discovery analysis has great potential to inspire the better design of
interventions beyond clinical Care and Public Health.

## References

  * [1] John Appleby, Veena Raleigh, Francesca Frosini, Gwyn Bevan, Haiyan Gao, and Tom Lyscom.  Variations in health care.  The good, the bad and the inexplicable. London: The King’s Fund, 2011.
  * [2] Harlan M Krumholz.  Variations in health care, patient preferences, and high-quality decision making.  Journal of the American Medical Association, 310(2):151–152, 2013\.
  * [3] Daniel B Neill.  Fast subset scan for spatial pattern detection.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 74(2):337–360, 2012.
  * [4] Daniel B Neill, Edward McFowland III, and Huanian Zheng.  Fast subset scan for multivariate event detection.  Statistics in medicine, 32(13):2185–2208, 2013.
  * [5] Edward Somanchi, Sriram McFowland III and Daniel B Neill.  Detecting anomalous patterns of care using health insurance claims.  Presented at Conference on Information Systems and Technology, 2017\.
  * [6] Edward McFowland, Skyler Speakman, and Daniel B Neill.  Fast generalized subset scan for anomalous pattern detection.  The Journal of Machine Learning Research, 14(1):1533–1561, 2013\.
  * [7] Zhe Zhang and Daniel B Neill.  Identifying significant predictive bias in classifiers.  arXiv preprint arXiv:1611.08292, 2016.
  * [8] Edward McFowland III, Sriram Somanchi, and Daniel B Neill.  Efficient discovery of heterogeneous treatment effects in randomized experiments via anomalous pattern detection.  arXiv preprint arXiv:1803.09159, 2018.
  * [9] Arnaud Van Looveren and Janis Klaise.  Interpretable counterfactual explanations guided by prototypes.  CoRR, abs/1907.02584, 2019.
  * [10] Ramaravind K. Mothilal, Amit Sharma, and Chenhao Tan.  Explaining machine learning classifiers through diverse counterfactual explanations.  In Proceedings of the 2020 Conference on Fairness, Accountability, and Transparency, FAT* ’20, page 607–617, New York, NY, USA, 2020. Association for Computing Machinery.
  * [11] Chris Russell.  Efficient search for diverse coherent explanations.  FAT* ’19, New York, NY, USA, 2019. Association for Computing Machinery.
  * [12] Amit Dhurandhar, Tejaswini Pedapati, Avinash Balakrishnan, Pin-Yu Chen, Karthikeyan Shanmugam, and Ruchir Puri.  Model agnostic contrastive explanations for structured data.  CoRR, abs/1906.00117, 2019.
  * [13] Amir-Hossein Karimi, Gilles Barthe, Borja Balle, and Isabel Valera.  Model-agnostic counterfactual explanations for consequential decisions.  ArXiv, abs/1905.11190, 2020.
  * [14] Shubham Sharma, Jette Henderson, and Joydeep Ghosh.  Certifai: A common framework to provide explanations and analyse the fairness and robustness of black-box models.  In Proceedings of the AAAI/ACM Conference on AI, Ethics, and Society, AIES ’20, page 166–172, New York, NY, USA, 2020. Association for Computing Machinery.
  * [15] Adam White and Artur S. d’Avila Garcez.  Measurable counterfactual local explanations for any classifier.  In ECAI, 2020.
  * [16] Susanne Dandl, Christoph Molnar, Martin Binder, and Bernd Bischl.  Multi-objective counterfactual explanations.  In International Conference on Parallel Problem Solving from Nature, pages 448–469, 2020.
  * [17] B. Schölkopf, F. Locatello, S. Bauer, N. R. Ke, N. Kalchbrenner, A. Goyal, and Y. Bengio.  Toward causal representation learning.  Proceedings of the IEEE - Advances in Machine Learning and Deep Neural Networks, 109(5):612–634, 2021.
  * [18] Daniel B. Neill and Tarun Kumar.  Fast multidimensional subset scan for outbreak detection and characterization.  Online Journal of Public Health Informatics, 5(1):e91, Apr 2013\.


11institutetext: Portland State University, Portland OR 97207, U.S.A.
11email<EMAIL_ADDRESS>
http://www.cs.pdx.edu/~singh

# Multi-Class Anomaly Detection

Suresh Singh  0000-0002-1509-0497 Minwei Luo  Yu Li

###### Abstract

We study anomaly detection for the case when the normal class consists of more
than one object category. This is an obvious generalization of the standard
one-class anomaly detection problem. However, we show that jointly using
multiple one-class anomaly detectors to solve this problem yields poorer
results as compared to training a single one-class anomaly detector on all
normal object categories together. We further develop a new anomaly detector
called DeepMAD that learns compact distinguishing features by exploiting the
multiple normal objects categories. This algorithm achieves higher AUC values
for different datasets compared to two top performing one-class algorithms
that either are trained on each normal object category or jointly trained on
all normal object categories combined. In addition to theoretical results we
present empirical results using the CIFAR-10, fMNIST, CIFAR-100, and a new
dataset we developed called RECYCLE.

###### Keywords:

Out of Distribution Anomaly Multi-Class Anomaly.

##  1 Introduction

To motivate this formulation of anomaly detection, let us consider several
applications: imagine a roadside garbage container that automatically
separates any discarded trash into recycles (glass, cans, plastic, etc.) or
garbage; machines used to separate normal blood cells (monocytes, neutrophils,
basophils, etc.) from bacteria in the blood (sepsis); generic classification
problems such as separating all species of cats from any other animal;
separating sounds of different mosquito species from any other sound; and
many, many more. In all these examples, the normal class in fact consists of
several different object categories.

It is trivial to see that one-class anomaly detection algorithms [28, 13, 11,
17, 10], [2, 20, 30, 33, 26] can be easily applied to this problem. In a
typical one-class formulation, the classifier is only trained on in-
distribution samples and it learns a probability density function $P$ that
captures normal behavior. Points that then map to a low probability region are
classified as anomalous. Generalizing to the case when $m$ different object
categories are all considered normal, we can train $m$ separate one-class
anomaly detectors $P_{1},\cdots,P_{m}$ and use them together to classify any
new object. However, we show that this approach is not as good as training a
single one-class anomaly detector on all the $m$ categories combined. This
result is demonstrated empirically as well as theoretically. The intuition is
that errors in classification of each of the $m$ one-class detectors are
cumulative thus resulting in poor joint performance.

Novelty detection [24, 19, 34] and out-of-distribution (OOD) detection [12,
25, 15, 16], [18, 35] are related to anomaly detection but our model has
significant differences. A common model used in OOD is to consider, for
example, the fMNIST data set as normal and MNIST as OOD or CIFAR-10 as normal
and natural images as OOD, etc. This model for defining what constitutes OOD
has recently come under criticism [3, 25]. As [3] notes, different datasets
are created and curated differently and thus it is likely that OOD algorithms
are learning to identify these idiosyncrasies rather than meaningful features.
Similarly, they argue that the context of the OOD task also matters – what is
OOD in one context may not be OOD in another. [25] also argues for more
realistic benchmarks for OOD (they use a bacteria genome database) observing
that distributional shifts learned in traditional OOD tasks may have learned
the background and thus have high error when used for realistic tasks.
Finally, [3] proposes testing OOD algorithms by sticking to the same dataset.
They study the case when 9 out of 10 CIFAR-10 classes are normal and the tenth
is treated as anomalous. We note that our model follows this approach. We
study cases when 2, 5, 9 classes of CIFAR-10, MNIST, and fMNIST are normal
while the others are anomalous.

In novelty detection, a data point is considered an outlier if it differs
significantly from a collection of normal data points (e.g., a mammogram with
a lump is an outlier in a collection of normal mammograms). The outlier and
the normal data points can be seen as being similar and what distinguishes the
outlier is its distance from a majority of normal points. A multi-class
novelty model is an extension where the number of outliers is large enough to
form a separate cluster but all the points are still similar. In our multi-
class model, on the other hand, the normal classes can be arbitrary (e.g., the
normal classes may be dog and truck images).

There are two variations of the multi-class anomaly detection problem – the
class labels of normal samples may either be unknown or known during training.
We call these two formulations inseparable and separable respectively and we
study both in this paper. The major results of our paper can be summarized as
follows:

  * •

We prove that training a one-class classifier in the inseparable case yields a
higher AUC (Area Under the Curve) value than training multiple single-class
classifiers for the separable case and combining their outputs. Our proof uses
the formulation for combining probabilities from the theory of belief
functions, Lemma 1.

  * •

We illustrate these results using two recent one-class anomaly detection
algorithms DROCC [11] and DeepSVDD [27] for the task of multi-class anomaly
detection. We did not use OOD algorithms such as [12] because, as noted
previously [3], these algorithms train on one dataset and test on another and
likely learn dataset idiosyncrasies rather than meaningful image features.

  * •

We present a new algorithm called DeepMAD for the separable case and compare
the accuracy of DeepMAD and two versions of each of DROCC and DeepSVDD (in one
version we train $m$ separate one-class classifiers and in the other we train
a single one-class classifier by combining training data from all $m$ normal
classes). These five algorithms are compared using CIFAR-10, fMNIST,
CIFAR-100, and RECYCLE. The RECYCLE dataset is one we created to study the
problem of classifying recycles described in the first paragraph of this
section. We show that DeepMAD performs well above all other algorithms by a
wide margin.

##  2 Related Work

A variety of one-class novelty detection algorithms exist [36, 19, 5, 29, 23,
1] but, as noted previously [21], these algorithms are not directly applicable
to the single-class anomaly detection problem. In the latter case we assign
labels whereas in the former we learn a latent space that separates the normal
class effectively from outliers. There have been a few additional works that
consider a multi-class novelty detection problem [22] where the dataset is
split into two subsets of classes with one treated as normal. A large
reference labeled dataset is used in conjunction with normal samples during
training. Our problem formulation differs from this in that we do not use any
reference dataset as a comparator to extract features. We also consider cases
when the split of normal/anomaly classes is variable.

In OOD detection, out of distribution samples are detected via the basic
predictive confidence of the classifier (MSP score) [12] or measures such as
temperature-scaled softmax scores (ODIN) [18] or confidence calibration [8].
Approaches as in [13] use other datasets as proxies for OOD examples while
[16] uses a GAN to generate negative examples for training. Other methods to
improve the representation of in-distribution data includes using self-
supervised approaches such as contrastive learning [5], alternative training
strategies such as margin loss [35], or metric learning [19]. [4] splits
normal data into $M$ and learns features to separate them.

Recently, deep learning based methods have been used for anomaly detection.
For instance [27, 26] describes DeepSVDD in which a deep neural network is
trained to map the in-class data into a sphere of minimal volume, while [9]
maps to multiple spheres. DROCC [11] trains the network to distinguish
manufactured out of distribution points that are perturbations of in-
distribution points as a way to learn more discriminating features. Another
approach has been to train auto encoders to learn a lower dimensional
representation [17, 20, 30]. An entirely different way of looking at the
problem is to use self-supervision by learning transformations where a new
sample is classified as normal if transforms applied to it can be correctly
identified [10, 14, 32].

##  3 Generalizing Single-Class Anomaly Detection to the Multi-Class Case

Table 1: Probability estimates for sample $x\in{\cal X}$ provided by $m$ classifiers. | {1} | {2} | $\cdots$ | $\\{m\\}$ | $\neg\\{1\\}$ | $\neg\\{2\\}$ | $\cdots$ | $\neg\\{m\\}$
---|---|---|---|---|---|---|---|---
$({\cal F}_{1},D_{1})$ | $P_{1}(1|x)$ | 0 | $\cdots$ | 0 | $1-P_{1}(1|x)$ | 0 | $\cdots$ | 0
. | . | . | $\cdots$ | . | . | . | $\cdots$ | .
$({\cal F}_{m},D_{m})$ | 0 | 0 | $\cdots$ | $P_{m}(m|x)$ | 0 | 0 | $\cdots$ | $1-P_{m}(m|x)$

Typically, anomaly detection methods learn a mapping ${\cal F}$ from the input
space ${\cal X}$ to some lower dimensional feature space ${\cal Y}$. Inputs
are then assigned a probability of being normal or anomalous via some function
$D$. ${\cal F}$ is learned using the normal class examples while $D$ may be
static (e.g., a distance measure of points in feature space) or jointly
learned. If we consider using one-class anomaly detectors for the multi-class
case where there are $1\leq i\leq m$ normal classes, for each class we learn
one classifier giving us a set $\\{({\cal F}_{i},D_{i})\\}_{i=1}^{m}$ of one-
class anomaly detectors. The question then is how to use these $m$ detectors
for the multi-class case.

We can use the theory of belief functions in risk analysis [6] to provide a
framework for combining these $m$ classifiers. In this theory, the assumption
is that $m$ experts provide their own assessment of risk among a set of
choices. In order to develop a final estimate of risk, these $m$ estimates are
combined. In the standard formulation of the problem, as applied to our case,
let $U=\\{1,2,\cdots,m,\Lambda\\}$ denote the set of $m$ normal classes (1 to
$m$) and a catchall class labeled $\Lambda$ which represents all anomalies. A
general classifier assigns a probability $P(u|x)$ for the probability that an
image $x$ belongs to the set of classes $u$, where $u\in 2^{U}$ is an element
of the powerset of $U$. For example if $u=\\{1,5\\}$ then this is the
probability that $x$ belongs to either of the classes 1 or 5.

This general formulation simplifies considerably for our case because the one-
class classifiers will only assign a non-zero probability to two instances, as
illustrated in Table 2. In other words, $P_{i}(u|x)=0$ for all cases except
when $u=\\{i\\}$ or $u=\neg\\{i\\}=\\{1,2,\cdots,i-1,i+1,\cdots,m,\Lambda\\}$.
In order to combine the predictions of the $m$ one-class classifiers to
compute the probability that $x$ is anomalous, we need to determine
$P(\Lambda|x)$. According to the Dempster-Schafer Theory [7, 31],

$P(\Lambda|x)=\frac{1}{K}\sum_{\neg\\{1\\}\cap\neg\\{2\\}\cap\cdots\neg\\{m\\}=\Lambda}\prod_{i=1}^{m}P_{i}(\neg\\{i\\}|x)$
(1)

which simplifies to,

$P(\Lambda|x)=\frac{1}{K}\prod_{i=1}^{m}P_{i}(\neg\\{i\\}|x)$ (2)

since there is just one case when the intersection of the predictions of the
$m$ classifiers yields $\Lambda$. $K$ is given by,

$K=1-\sum_{u_{1}\cap u_{2}\cap\cdots u_{m}=\phi}\prod_{i=1}^{m}P_{i}(u_{i}|x)$
(3)

where $u_{i}\in\\{\\{i\\},\neg\\{i\\}\\}$ (because all other probabilities are
zero from Table 1, these are the only non-trivial cases). The above equation
simplifies to,

$K=\prod_{i=1}^{m}P_{i}(\neg\\{i\\}|x)+\sum_{i=1}^{m}P_{i}(\\{i\\}|x)\prod_{j=1,j\neq
i}^{m}P_{j}(\neg\\{j\\}|x)$ (4)

From the above formulation it follows that an input $x$ is classified as
normal if any of the $m$ classifiers say it is normal and it is classified as
anomalous if all classifiers classify it as anomalous. Thus, it is easy to
construct a multi-class anomaly detection algorithm using $m$ one-class
anomaly detectors as shown in Algorithm 1.

Algorithm 1: (Using $m$ Single-Class Anomaly Detectors)

Training: Let $({\cal F},D)$ be any one-class anomaly detection algorithm.
Given training set $X=\\{X_{1},X_{2},\cdots,X_{m}\\}$ consisting of training
examples from $m$ classes $X_{i}\subset{\cal X}_{i}$, train $({\cal F},D)$
separately on each class producing $m$ classifiers, $({\cal F}_{i},D_{i})1\leq
i\leq m$.

Testing: Given $x\in{\cal X}$, classify it with each of the $m$ classifiers.
Declare $x$ anomalous if all classifiers classify it as anomalous.

Another approach for training a one-class classifier for the $m$ class case is
to simply combine the training data from all $m$ classes and treat that as a
single class. Doing so gives us Algorithm 2.

###### Lemma 1

Algorithm 2 has a higher AUC value than Algorithm 1 when the same one-class
anomaly detection algorithm is used in both cases.

###### Proof

Recall that the AUC value is the integral of the True Positive Rate (TPR) vs
False Positive Rate (FPR) curve (each point on the curve corresponds to a
different value for the detection threshold $T$). For Algorithm 1 we can write
the TPR and FPR as,

$\begin{array}[]{lcl}\mbox{TPR}_{1}&=&1-\mbox{False Negative Rate}\\\
\lx@intercol\hfil=1-\frac{1}{K}\sum_{x_{j}\in\cup_{i=1}^{m}{\cal
X}_{i}}p(x_{j})\prod_{i=1}^{m}(1-P_{i}(\\{i\\}|x_{j}))\hfil\lx@intercol\\\
\mbox{FPR}_{1}&=&1-\mbox{True Negative Rate}\\\
\lx@intercol\hfil=1-\frac{1}{K}\sum_{x_{j}\in{\cal
X}\setminus\cup_{i=1}^{m}{\cal
X}_{i}}p(x_{j})\prod_{i=1}^{m}(1-P_{i}(\\{i\\}|x_{j}))\hfil\lx@intercol\\\
\end{array}$

Note that the difference in the two expressions is in the sets that $x_{j}$ is
selected from. The similar expressions for Algorithm 2 are,

$\begin{array}[]{lcl}\mbox{TPR}_{2}&=&1-\mbox{False Negative Rate}\\\
\lx@intercol\hfil=1-\frac{1}{K}\sum_{x_{j}\in\cup_{i=1}^{m}{\cal
X}_{i}}p(x_{j})(1-P(\mbox{Normal}|x_{j}))\hfil\lx@intercol\\\
\lx@intercol\hfil=1-\frac{1}{K}\sum_{x_{j}\in\cup_{i=1}^{m}{\cal
X}_{i}}p(x_{j})\sum_{i=1}^{m}\frac{1}{m}(1-P_{i}(\\{i\\}|x_{j}))\hfil\lx@intercol\\\
\mbox{FPR}_{2}&=&1-\mbox{True Negative Rate}\\\
\lx@intercol\hfil=1-\frac{1}{K}\sum_{x_{j}\in{\cal
X}\setminus\cup_{i=1}^{m}{\cal
X}_{i}}p(x_{j})(1-P(\mbox{Normal}|x_{j})\hfil\lx@intercol\\\
\lx@intercol\hfil=1-\frac{1}{K}\sum_{x_{j}\in{\cal
X}\setminus\cup_{i=1}^{m}{\cal
X}_{i}}p(x_{j})\sum_{i=1}^{m}\frac{1}{m}(1-P_{i}(\\{i\\}|x_{j}))\hfil\lx@intercol\\\
\end{array}$

The difference in the TPR (and FPR) values of this set of expressions is that
for Algorithm 1 we take a product of the form
$\prod_{i}(1-P_{i}(\\{i\\}|x_{j}))$ whereas for Algorithm 2 this is a mean of
the same probabilities. As $m$ increases, we would expect the product term to
decrease rapidly. Indeed, the values of TPR and FPR for Algorithm 1 approach 1
as $m$ increases resulting in a purely random classifier. On the other hand,
the TPR and FPR for Algorithm 2 remain relatively unchanged since they use an
arithmetic mean of the probability rather than a geometric mean as in
Algorithm 1.

Corollary 3.1.1: As $m$ increases, the AUC value for Algorithm 1 decreases.

###### Proof

This is easy to see since we note that the FPR and TPR values approach 1 as
$m$ increases.

Note that this corollary is not true for Algorithm 2.

Algorithm 2: (Training a single classifier by combining all $m$ classes)

Training: Given a training set $X=X_{1}\cup X_{2}\cup\cdots\cup X_{m}$, train
a single classifier $({\cal F},D)$ on this set (see Notes in Algorithm 1).

Testing: An example $x$ is classified as normal or anomalous by this
classifier (just like any single-class classifier).

### Algorithms Studied

In this paper, we use two recent and high performing single-class anomaly
detection algorithms – DROCC [11] and DeepSVDD [27]. For each algorithm we
consider two variations corresponding to Algorithms 1 & 2 above. Thus,
DROCC($m$) and DeepSVDD($m$) correspond to Algorithm 1 while DROCC and
DeepSVDD correspond to Algorithm 2. We use the author provided code for our
experiments.

##  4 DeepMAD: Deep Multi-class Anomaly Detection

Our algorithm DeepMAD is based on Algorithm 1 above, but with important
changes. The key insights we applied are the following:

  * •

For any single-class algorithm, AUC values increase if the variance of the pdf
of the normal class is reduced because it increases the TPR (True Positive
Rate) without affecting the FPR (False Positive Rate), assuming the means of
the normal and anomaly classes do not shift.

  * •

In the absence of anomalies, the features learned represent what is common
among the examples. DROCC attempts to learn discriminating features by using
the manufactured examples. Similarly, algorithms that add noise to training
examples or that learn transformations etc. are all attempting to reduce
variance by learning discriminating features..

  * •

When moving to the multi-class case, observe that Algorithm 2 will likely
learn features common among the normal classes in addition to features common
to examples within each class, potentially resulting in larger variance.

In DeepMAD, we train $m$ one-class anomaly detectors. However, rather than
train $P_{i}$ only on the $i$th normal class, we train it on all $m$ classes
where we use the training examples from classes $\neg\\{i\\}$ as anomalous.

Algorithm 3: DeepMAD

Training: Randomly initialize $m$ autoencoders $A_{i}$; For every $A_{i}$,
train $A_{i}$ on provided examples $X_{i}$; Using the encoder part $E_{i}$ of
the autoencoder, identify a point $c_{i}$, the ”center” for this class;

For every encoder $E_{i}$, create labeled training data $\\{(x,l)|$ if $x\in
X_{i}$ then $l=+1$ else if $x\in\bigcup_{j=1,j\neq i}^{m}X_{j}$ then
$l=-1\\}$. Then train $E_{i}$ on this data using loss function ${\cal L}$

Result: $m$ trained encoders $E_{i}$

Testing: Given $x$ to classify, compute
$d(x)=\min_{i=1}^{m}||c_{i}-E_{i}(x;\theta_{i})||_{2}$; If $d(x)<\gamma$ then
$x$ is normal else $x$ is anomalous

The algorithm for training proceeds in two steps. For every class $i$, we
first train an autoencoder $A_{i}$ using MSE between the original and
reconstructed image as the loss. Next, we train only the encoder $E_{i}$ using
the other $m-1$ classes as anomalies and class $i$ as normal. For this, we
identify a ”center” $c_{i}$ for this class and learn a representation that
maps points in $X_{i}$ to a sphere around it and maps other points from the
remaining classes far away. We use the following loss function,

$\begin{array}[]{l}{\cal
L}(\theta_{i})=\frac{1}{N}\sum_{j=1}^{N_{i}}||E_{i}(x_{j};\theta_{i})-c_{i}||^{2}+\\\
\frac{\eta}{N}\sum_{x_{k}\in(\bigcup_{j}X_{j})\setminus X_{i}}(\mbox{max
}(0,\delta-||E_{i}(x_{k};\theta_{i})-c_{i}||_{2})^{2})\\\
+\frac{\lambda}{2}\sum_{l=1}^{L}||W^{l}||_{F}^{2}\end{array}$

where $N=|X_{1}|+\cdots+|X_{m}|$ is the total number of normal class samples
and $N_{i}=|X_{i}|$ is the number of examples from normal class $i$.
$\delta,\eta$ and $\lambda$ are hyperparameters where $\eta$ controls the
weight given to the constrastive loss term, $\delta$ is a distance from the
identified center beyond which we would like to map points not in $X_{i}$, and
$\lambda$ is a regularization parameter. The first term above attempts to
learn a small sphere about the center for normal points in class $i$ while the
second term attempts to maximize the distance of the remaining normal points
(all except points in $X_{i}$) far away. The ensemble method in [35] also
trains multiple classifiers and uses a mean of their softmax outputs for OOD
detection. Unlike out work, they train on one dataset and test on another
(recall the criticism from [3] which notes that detecting anomalies within the
same dataset is much harder than between dastasets). It is also unclear how
well their method would scale down to few normal classes (say 2).

##  5 Empirical Evaluation

Table 2: AUC range for CIFAR-10 (10 repetitions for each). | 2-in, 8-out | 5-in, 5-out | 9-in, 1-out
---|---|---|---
DROCC | $0.4728\longleftrightarrow 0.7252$ | $0.4316\longleftrightarrow 0.7219$ | $0.4107\longleftrightarrow 0.7146$
| $\pm 0.0119\hskip 8.5359pt\pm 0.0081$ | $\pm 0.0257\hskip 8.5359pt\pm 0.0039$ | $\pm 0.0454\hskip 8.5359pt\pm 0.0079$
Outlier | $(0,8)\hskip 8.5359pt0.8359\pm 0.0117$ |  |
DROCC($m$) | $0.4216\longleftrightarrow 0.6912$ | $0.3806\longleftrightarrow 0.7023$ | $0.3439\longleftrightarrow 0.6896$
| $\pm 0.0424\hskip 8.5359pt\pm 0.0188$ | $\pm 0.0047\hskip 8.5359pt\pm 0.0648$ | $\pm 0.1034\hskip 8.5359pt\pm 0.0453$
Outlier | $(0,8)\hskip 8.5359pt0.8255\pm 0.0137$ |  |
DeepSVDD | $0.4088\longleftrightarrow 0.7623$ | $0.3382\longleftrightarrow 0.7105$ | $0.3058\longleftrightarrow 0.6844$
| $\pm 0.0068\hskip 8.5359pt\pm 0.0193$ | $\pm 0.0076\hskip 8.5359pt\pm 0.0077$ | $\pm 0.0169\hskip 8.5359pt\pm 0.0144$
DeepSVDD($m$) | $0.4147\longleftrightarrow 0.7516$ | $0.3482\longleftrightarrow 0.6909$ | $0.3580\longleftrightarrow 0.5864$
| $\pm 0.0129\hskip 8.5359pt\pm 0.0093$ | $\pm 0.0123\hskip 8.5359pt\pm 0.0133$ | $\pm 0.0166\hskip 8.5359pt\pm 0.0167$
DeepMAD | 0.5396$\longleftrightarrow$ 0.7647 | 0.4929 $\longleftrightarrow$ 0.7738 | 0.5437 $\longleftrightarrow$ 0.7230
| $\pm 0.0031\hskip 8.5359pt\pm 0.0014$ | $\pm 0.0046\hskip 8.5359pt\pm 0.0022$ | $\pm 0.0028\hskip 8.5359pt\pm 0.0084$

We compare the performance of five algorithms – DROCC, DROCC($m$), DeepSVDD,
DeepSVDD($m$), and DeepMAD using four data sets: CIFAR-10, fMNIST, RECYCLE,
and CIFAR-100. For DROCC and DeepSVDD we used the code provided by the authors
while for the $m$ normal classes case we simply replicated the code and
modified the main() function appropriately. For all the experiments with
DROCC, we used parameters radius $r=8$, $\mu=1$, learning rate = 0.001, ascent
step = 0.001 and the Adam optimizer. The reason for this choice is that the
ablation study reported in [11] shows a fairly stable AUC value for this
parameter setting across classes (though the specific value for $r$ that
achieves optimal AUC for the single-class case can vary by class). The
parameter settings for DeepSVDD used $\eta=1$, learning rate of 0.0001 and the
Adam optimizer as well. We consider three multi-class anomaly detection cases
for CIFAR-10 and fMNIST – (2/8), (5/5), and (9/1) which correspond to 2, 5, 9
normal classes respectively. For CIFAR-100 we used the 20 super-classes and
studied the (2/18) case. For the RECYCLE dataset (described below) we have 5
classes of recyclables and one that is assorted trash. We considered two
cases: in one, we study the (4/1) case using only the recycles; we then study
the case when the 5 recycles are all normal and the trash is the anomaly. In
all cases we repeated the experiments with random seeds and report the 95%
confidence intervals of the achieved AUC values.

Table 3: AUC range for fMNIST (10 repetitions each). | 2-in, 8-out | 5-in, 5-out | 9-in, 1-out
---|---|---|---
DROCC | $0.6873\leftrightarrow 0.9774$ | $0.5738\leftrightarrow 0.9260$ | $0.5408\leftrightarrow 0.8247$
| $\pm 0.0937\pm 0.0049$ | $\pm 0.0397\pm 0.0307$ | $\pm 0.0961\pm 0.0507$
Mean | 0.8161 | 0.7448 | 0.6992
Deep | $0.6622\leftrightarrow 0.9871$ | $0.5438\leftrightarrow 0.9279$ | $0.4551\leftrightarrow 0.8825$
SVDD | $\pm 0.0502\pm 0.0033$ | $\pm 0.0274\pm 0.0325$ | $\pm 0.0285\pm 0.0137$
Mean | 0.8538 | 0.7269 | 0.6523
Deep | $0.6434\leftrightarrow 0.9714$ | $0.5732\leftrightarrow 0.8832$ | $0.4860\leftrightarrow 0.9395$
MAD | $\pm 0.0640\pm 0.0011$ | $\pm 0.0485\pm 0.0137$ | $\pm 0.0267\pm 0.3466$
Mean | 0.8329 | 0.7739 | 0.7613
Table 4: AUC range for RECYCLE, and CIFAR-100 (10 repetitions each). | RECYCLE | CIFAR-100
---|---|---
| 4-in, 1-out | 5-in, 1-out | 2-in, 18-out
DROCC |  0.4447 $\leftrightarrow$ 0.7997 | 0.9056 | $0.3548\leftrightarrow 0.7329$
| $\pm 0.0176\pm 0.0719$ |  | $\pm 0.0006\pm 0.0971$
Mean | 0.6128 |  | 0.5638
Deep |  0.3703 $\leftrightarrow$ 0.8728 | 0.9012 | $0.4196\leftrightarrow 0.7185$
SVDD | $\pm 0.0207\pm 0.0079$ |  | $\pm 0.0077\pm 0.0180$
Mean | 0.5791 |  | 0.5559
Deep |  0.5906 $\leftrightarrow$0.8283 | 0.9838 | $0.5384\leftrightarrow 0.8213$
MAD | $\pm 0.0035\pm 0.0073$ |  | $\pm 0.0018\pm 0.0012$
Mean | 0.6966 |  | 0.6580

Figure 1: Examples of objects from the five (5) recycle classes.

Figure 2: Examples of trash (images are all random trash and cannot be divided
into classes).

The RECYCLE dataset contains 5 classes of recycles – glass bottles, plastic
bottles, cans, crushed cans, and cardboard boxes. The original images were
3008x2000x3 but we downsampled them to 32x32x3. There are a total of 11,000
images evenly divided among the five classes. 10,000 are used for training and
1,000 for testing. Samples of these images are shown in Figure 1. We also
created 300 trash images to use for testing. Some examples are shown in Figure
2.

Figure 3: 2 in and 8 out case (CIFAR-10).

Table 2 summarizes the AUC values achieved by each of the five algorithms on
CIFAR-10. For the (2/8) case, there are 45 combinations, for (5/5) there are
252 and for (9/1) there are ten. In the table we report on the range of values
with their confidence intervals. For all three cases we note that DeepMAD has
the best AUC values (with the exception of an outlier for DROCC). But more
importantly, observe that DROCC performs better than DROCC($m$) and DeepSVDD
performs better than DeepSVDD($m$), which is what the theoretical results from
the previous section predicted. Figure 3 provides a scatter plot of all 45
combinations for the five algorithms for the case when two classes are normal.
It is clear that which classes are considered normal has a huge impact on AUC
values. For all but DeepMAD, some cases have an AUC value below 0.5 which is
very poor. Its noteworthy that the case when classes 0 and 8 are normal DROCC
has a very high AUC value (labeled an outlier in the table). Figure 4 plots
the AUC values for the ten best and ten worst cases (out of 252) for when 5
classes are normal. The specific class combinations that have the best and
worst values are different for the algorithms (details are in the
supplementary materials). Aside from the fact that DeepMAD performs better, it
also shows considerably low variance. This points to it learning very good
discriminating features.

We ran DROCC, DeepSVDD, and DepMAD on the fMNIST, RECYCLE, and CIFAR-100
datasets as well. We did not run DROCC($m$) and DeepSVDD($m$) because, as we
have seen, training over all classes jointly performs better. Tables 3, 4
provides AUC values for CIFAR-100 where we see that DeepMAD has about 10%
improvement over the other algorithms. In this case we considered the 20
super-classes and considered just a single case when 2 of the 20 classes are
considered normal. The tables also provides AUC values for fMNIST. Here the
picture is more mixed. For the case when 2 classes are normal, all algorithms
are very similar with DeepSVDD holding a 2% edge when averaged over 45
combinations. DeepMAD performs better on average for the other two cases. For
the RECYCLE dataset, DeepMAD performs well above the other two algorithms. The
(4/1) case is when we only consider the five recycle classes and use four of
them as defining normal with the fifth being the anomaly. We also considered
the case when the five recycle classes were all normal and trash was
considered as the anomaly. This is the (5/1) case in the table. All algorithms
perform considerably better because trash images are very different from
recycles. However, DeepMAD is about 8% better than the other two.

Figure 4: 5 in 5 out case (CIFAR-10).

##  6 Conclusions

The problem of multi-class anomaly detection occurs naturally in many
settings, making it an important model to study. In this paper we adapt two
one-class anomaly detection algorithms to the multi-class setting and develop
a new algorithm DeepMAD. Our paper reports two significant results. First, we
show that jointly learning a classifier (using single-class anomaly detection
algorithms) for all the normal classes provides higher classification accuracy
as compared to using several single-class classifiers. And second, we show
that using supervised learning by treating $m-1$ out of $m$ normal classes as
anomalous results in much compact representations and hence uniformly higher
accuracy. We compare our algorithm against two recent single-class classifiers
adapted to the multi-class scenario and show improvements in AUC values for
almost all cases for CIFAR-10, fMNIST, and and CIFAR-100. However, we still
see AUC values below 0.7 for many cases and addressing this constitutes a
major thrust of future work. We also take a first step in analyzing the
feature vectors as a way to understand where the algorithms fail. We hope that
the methodology we use for this analysis of feature vectors can be extended by
others. Our code is available at
https://anonymous.4open.science/r/DeepMAD-16D4/

## References

  * [1] Abati, D., Porrello, A., Calderara, S., Cucchiara, R.: And: Autoregressive novelty detectors. In: Proceedings CVPR (2019)
  * [2] Ackay, A., Atapour-Abarghouei, A., Breckopn, T.P.: Ganomaly: semi-supervised anomaly detection via adversarial training. In: Proceedings ACCV. pp. 622–637 (2018)
  * [3] Ahmed, F., Courville, A.: Detecting semantic anomalies. In: Proceedings of AAAI. vol. 34, pp. 3154–3162 (2020)
  * [4] Bergman, L., Hoshen, Y.: Classification-based anomaly detection for general data. In: Proceedings ICLR (2020)
  * [5] Chen, T., Kornblith, S., Norouzi, M., Hinton, G.: A simple framework for contrastive learning of visual representations. In: Proceedings ICML (2020)
  * [6] Clemen, R.T., Winkler, R.L.: Combining probability distributions from experts in risk analysis. Risk Analysis 19(2), 187–203 (1999)
  * [7] Dempster, A.P.: Upper and lower probabilities induced by a multivalued mapping. Annals of Mathematical Statistics 38(2), 325–339 (1967)
  * [8] DeVries, T., Taylor, G.W.: Learning confidence for out-of-distribution detection in neural networks (2018)
  * [9] Ghafoori, Z., Leckie, C.: Deep multi-sphere support vector data description. In: SIAM SDM (2020)
  * [10] Golan, I., El-Yaniv, R.: Deep anomaly detection using geometric transformations. In: Proceedings NeurIPS (2018)
  * [11] Goyal, S., Raghunathan, A., M.Simhadri, Jain, P.: Drocc: Deep robust one-class classification. In: Proceedings ICML (2020)
  * [12] Hendrycks, D., Gimpel, K.: A baseline for detecting misclassified and out-of-distribution examples in neural networks. In: Proceedings of ICLR (2017)
  * [13] Hendrycks, D., Mazeika, M., Dietterich, T.: Deep anomaly detection with outlier exposure. In: Proceedings ICLR (2019)
  * [14] Hendrycks, D., Mazeika, M., Kadavath, S., Song, D.: Using self-supervised learning can improve model robustness and uncertainity. In: Proceedings NeurIPS (2019)
  * [15] Lakshminarayanan, B., Pritzel, A., Blundell, C.: Simple and scalable predictive uncertainity estimation using deep ensembles. In: 31st Conference on Neural Information Processing Systems (2017)
  * [16] Lee, K., Lee, H., Lee, K., Shin, J.: Training confidence-calibrated classifiers for detecting out-of-distribution samples (2018)
  * [17] Li, D., Chen, D., Goh, J., k. Ng, S.: Anomaly detection with generative adversarial networks for multivariate time series. In: 7th International Workshop on Big Data, Streams and Heterogeneous Source Mining: Algorithms, Systems, Programming Models and Applications (ACM KDD) (August 2018)
  * [18] Liang, S., Li, Y., Srikant, R.: Enhancing the reliability of out-of-distribution image detection in neural networks. In: Proceedings International Conference on Learned Representations (ICLR ’18) (Feb 2018)
  * [19] Masana, M., Ruiz, I., Serrat, J., van de Weijer, J., Lopez, A.M.: Metric learning for novelty and anomaly detection. In: British Machine Vision Conference (2018)
  * [20] Nguyen, D.T., Lou, Z., Klar, M., Brox, T.: Anomaly detection with multiple-hypothesis predictions. In: Proceedings ICML (2019)
  * [21] Perera, P., Nallapati, R., Xiang, B.: Ocgan: one-class novelty detection using gans with constrained latent representations. In: Proceedings CVPR (2019)
  * [22] Perera, P., Patel, V.M.: Deep transfer learning for multiple class novelty detection. In: Proceedings CVPR (2019)
  * [23] Pidhorskyi, S., Almohsen, R., Adjeroh, D.A., Doretto, G.: Generative probabilistic novelty detection with adversarial autoencodres. In: Proceedings NeurIPS (2018)
  * [24] Pimentel, M.A.F., Clifton, D.A., Clifton, L., Tarassenko, L.: A review of novelty detection. Signal Processing pp. 215–249 (2014)
  * [25] Ren, J., et al: Likelihood ratios for out-of-distribution detection. In: 33rd Conference on Neural Information Processing Systems (2019)
  * [26] Ruff, L., et al.: Deep one-class classification. In: Proceedings 35th International Conference on Machine learning (ICML). Stockholm, Sweeden (2018)
  * [27] Ruff, L., et al.: Deep semi-supervised anomaly detection. In: Proceedings ICLR (2020)
  * [28] Ruff, L., et al.: A unifying review of deep and shallow anomaly detection. arXiv:2009.11732v2 (September 2020)
  * [29] Sabokrou, M., Khalooei, M., Fathy, M., Adeli, E.: Adversarially learned one-class classifier for novelty detection. In: Proceedings CVPR. pp. 3379–3388 (2018)
  * [30] Schlegl, T., Seebock, P., Waldstein, S.M., Schmidt-Erfurth, U., Langs, G.: Unsupervised anomaly detection with generative adversarial networks to guide marker discovery. In: International Conference on Information Processing in Medical Imaging. pp. 146–157 (2017)
  * [31] Shafer, G.: Mathematical Theory of Evidence. Princeton University Press (1976)
  * [32] Sohn, K., Li, C.L., Yoon, J., Jin, M., Pfister, T.: Learning and evaluating representations for deep one-class classification. In: Proceedings ICLR (2021)
  * [33] Song, H., Jiang, Z., Men, A., Yang, B.: A hybrid semi-supervised anomaly detection model for high-dimensional data. Computational Intelligence and Neuroscience (2017)
  * [34] Tack, J., Mo, S., Jeong, J., Shin, J.: CSI: novelty detection via contrastive learning on distributionally shifted instances. NeurIPS (2020)
  * [35] Vyas, A., Jammalamadaka, N., Zhu, X., Das, D., Kaul, B., Wilke, T.L.: Out-of-distribution detection using an ensemble of self-supervised leave-out classifiers. In: Proceedings ECCV. pp. 550–564 (2018)
  * [36] Zhang, H., Li, A., Guo, J., Guo, Y.: Hybrid models for open set recognition (2020)