##  1 Introduction

Unsupervised Anomaly Detection (AD) is used in diverse societal applications
such as identifying fraudulent credit card transactions and intrusions in
computer networks making it critical to correctly identify anomalies
minimizing costly false positives and dangerous false negatives. Ensembles
have proven effective in increasing the performance accuracy of many algorithm
classes. A significant challenge in unsupervised anomaly detection is that we
do not know the anomalies, that is, the ground truth or the class labels are
unknown. Because of this, the proven and tested ensemble frameworks that use
the class labels cannot be applied for anomaly detection. We propose a novel
ensemble framework based on Item Response Theory (IRT), which models the
ground truth as a latent trait.

Unsupervised anomaly detection ensembles can be broadly categorized into 3
types based on their ensemble strategy. These are subsampling, feature bagging
and the use of different combination functions (Aggarwal and Sathe, 2015).
Subsampling strategies (Zimek et al., 2013) generally use different samples of
observations from the dataset to build a model and average the predictions
from various observation samples. Feature bagging (Lazarevic and Kumar, 2005)
uses different subsets of features of the dataset to build the model. Again
the prediction scores are averaged. Generally, both subsampling and feature
bagging use the same base algorithm on different subsets of observations
and/or features to produce a final consensus. The use of different combination
functions such as the average, maximum and other correlation based functions
have also been explored in ensemble learning. Combination function ensemble
methods are generally used with a set of heterogeneous anomaly detectors. The
proposed IRT ensemble framework in effect constitutes a new combination
function that can be used on set of heterogeneous AD methods.

Combination functions are often used in supervised machine learning ensembles.
For example, gradient boost algorithms combine the output of a series of
models, each predicting the residuals of a prior model. It is difficult to
emulate such a process in the unsupervised AD ensemble regime, because the
class labels are not known. Some AD ensemble techniques use pseudo-ground-
truth labels (Rayana and Akoglu, 2016; Campos et al., 2018; Zhang et al.,
2019), which are generally defined as averaged anomaly scores, in place of the
unknown ground truth. The use of pseudo-ground-truth labels in AD ensembles
gives rise to a circular argument because the ensemble mimics the pseudo-
ground-truth labels, which affects the ensemble nuts and bolts in terms of the
choice of AD methods and their weights. Therefore, if the pseudo-ground-truth
labels are not true representatives of the actual ground-truth, which often
they are not, their use constitutes a serious limitation.

The proposed ensemble method steers away from the limitations of pseudo-
ground-truth by modeling the ground truth as a latent variable. Latent
variables are variables which are not directly observed, but inferred from a
mathematical model. Thus, they are hidden. For example, the market volatility
can be modeled as a latent variable using the observed stock prices; a
student’s ability can be modeled as a latent variable using the student’s
responses to a test. Similarly, the unknown ground truth of anomalies can be
modeled as a latent variable using the observed scores of AD methods.

Item Response Theory (IRT) encompasses a family of latent trait models that
has traditionally been used in educational psychometrics to determine the
ability of test participants and the difficulty and discrimination of test
questions. Recently, IRT has been used for algorithm and dataset evaluation
(Martínez-Plumed et al., 2019; Chen et al., 2020; Kandanaarachchi and Smith-
Miles, 2020), and classification ensemble construction (Chen and Ahn, 2020)
broadening the applicability of IRT to the machine learning and artificial
intelligence domain. Of particular interest is the IRT ensemble proposed by
Chen and Ahn (2020). Their ensemble, which was used for classification
algorithms can be also extended for other supervised machine learning
algorithms. However, it cannot be extended to unsupervised tasks because they
use accuracy measures in their IRT model. That is, they assign $y_{ij}=1$ if
classifier $i$ correctly classifies observation $j$, or assign $y_{ij}=0$
otherwise. As we do not have the class labels or the ground truth of the
observations, we cannot utilize this IRT ensemble for unsupervised anomaly
detection.

In this paper we propose an IRT ensemble for unsupervised anomaly detection
that uses its latent trait continuum to uncover the ground truth. This is
different from the ensemble proposed by Chen and Ahn (2020) because we use a
different mapping of the IRT framework to ensemble learning. In their mapping
the latent trait denotes the ability of the classifiers, whereas in our
mapping the latent trait determines the hidden ground truth of observations.
It is this different mapping that enables ensemble learning for unsupervised
anomaly detection. Before examining different mappings, we discuss the problem
of AD ensemble learning and introduce IRT briefly in Section 2. In Section 3
we discuss different ways that IRT is mapped to machine learning problems and
introduce our mapping for ensemble learning. Then, we compare different
ensemble techniques on synthetic data in Section 4 and using an extensive real
data repository, conduct more comparisons in Section 5. Finally, we present
our conclusions in Section 6. As an additional contribution, we make these
ensembles available in the R package outlierensembles (Kandanaarachchi, 2021).

##  2 Problem Statement and Background

###  2.1 Unsupervised Anomaly Detection Ensembles

Unsupervised Anomaly Detection (AD) methods generally give anomaly scores for
each observation in the dataset with larger scores indicating anomalous
observations. Thus, we have a ranking of observations in terms of
anomalousness. Figure 1 shows an example of AD ensembling using a synthetic
dataset of 100 points. The table shows the anomaly scores of 7 different
methods, M1 to M7, on a selected set of 7 points – the top 5 anomalous points
and the bottom 2 anomalous points according to M1. These points are denoted by
green triangles and blue rectangles respectively. We see that the anomaly
score ranks as well as the score ranges are different for each method. For
example, M1 has much larger anomaly scores compared to the other methods.
Also, M5 and M6 have scores between 0 and 1, while M2 and M3 have some scores
greater than 1. The top ranked anomaly by M1 is ranked lower by M2 - M6.

Figure 1: A synthetic example of 100 points and the resulting anomaly scores
of 7 different AD methods denoted by M1 to M7. The table gives the anomaly
scores of a set of selected points. These points are the top 5 and the bottom
2 anomalous points according to M1. These are marked in the figure by green
triangles and blue rectangles respectively.

Given these heterogeneous methods and their anomaly scores, the task is to
construct an ensemble score. As the anomaly scores of different methods have
different scales, normalized AD scores are used to compute an ensemble score.
Combination functions such as the average, the maximum or others based on
correlation and feature selection are typically used. We investigate the
research problem of combining anomaly scores of multiple AD methods with the
aim of achieving better performance compared to existing combination methods.
To compare the performance of different combination functions, we use
synthetic and real datasets with known labels or ground truth. Given that no
single ensemble will outperform all other ensembles for all problem instances,
we are interested in constructing an AD ensemble that is effective for a large
proportion of the problem instances, surpassing the effectiveness of other
ensembles. We state this formally as follows:

Problem Statement.  Let $X$ be a dataset with $n$ observations and let
$\bm{t}$ denote the ground truth vector of these observations with
$\bm{t}\in\mathbb{R}^{n}$. Let $\bm{u}_{1},\bm{u}_{2},\ldots,\bm{u}_{\ell}$
denote the anomaly scores of $\ell$ different AD methods on $X$ with
$\bm{u}_{i}\in\mathbb{R}^{n}$ for $i\in\\{1,\ldots,\ell\\}$. Let
$f_{1},f_{2},\ldots,f_{k}$ denote $k$ ensemble combination functions with
$\bm{v}_{1}=f_{1}\left(\bm{u}_{1},\ldots,\bm{u}_{\ell}\right)$, …,
$\bm{v}_{k}=f_{k}\left(\bm{u}_{1},\ldots,\bm{u}_{\ell}\right)$ denoting their
respective ensemble scores where $\bm{v}_{j}\in\mathbb{R}^{n}$ for
$j\in\\{1,\ldots,k\\}$. Let $\xi$ denote an AD performance metric such that
$\xi\left(\bm{t},\bm{v}_{j}\right)\in\mathbb{R}$. If a combination function
$f_{b}$ with ensemble output
$\bm{v}_{b}=f_{b}\left(\bm{u}_{1},\ldots,\bm{u}_{\ell}\right)$ satisfies

$\xi\left(\bm{t},\bm{v}_{b}\right)>\xi\left(\bm{t},\bm{v}_{j}\right)\,,$ (1)

for all $j\in\\{1,\ldots,k\\},j\neq b$, then we say that $f_{b}$ is the best
performing ensemble for $X$. For a collection of datasets $\chi$, let $p_{i}$
be the proportion of datasets for which $f_{i}$ performs best according to
equation (1). Then, we seek an ensemble combination function $f_{b}$ for which

$p_{b}>p_{j}\,,$

for all $b\neq j$ for any given collection of datasets $\chi$.

####  2.1.1 The variables in the problem statement

We use a set of nearest neighbor based AD methods to build the ensemble: KNN-
AGG (Angiulli and Pizzuti, 2002), LOF (Breunig et al., 2000), COF (Tang et
al., 2002) INFLO (Jin et al., 2006), KDEOS (Schubert et al., 2014), LDF
(Latecki et al., 2007) and LDOF (Zhang et al., 2009). We use the
implementation in the R package DDoutlier (Madsen, 2018) to compute the
anomaly scores using these methods. These 7 methods either have a parameter
$k$ or two parameters $k_{\min}$ and $k_{\max}$, which define the neighborhood
for distance and density computations. We have used the default parameters
$k_{\min}=k=5$ and $k_{\max}=10$ for all synthetic experiments. For
experiments with real data, we have used two different parameter settings.

As for ensemble methods, which are denoted by $f_{1},\ldots,f_{k}$ in the
Problem Statement, we compare the performance of the following 7 ensembles:

  1. 1.

IRT ensemble is the proposed ensembling method, which we will discuss in
detail in Section 3.4.

  2. 2.

Average ensemble computes the mean of the anomaly scores. We use the Average
ensemble as a benchmark because the mean of the anomaly scores is often a
useful indicator of anomalousness.

  3. 3.

Greedy ensemble (Schubert et al., 2012) selects methods to include in the
ensemble based on correlation values and requires a parameter $\kappa$, which
is an estimate of the number of anomalies.

  4. 4.

Averaged Greedy (Greedy-Avg) ensemble runs the Greedy ensemble for different
values of $k$ and computes the average.

  5. 5.

Inverse Cluster Weighted Averaging (ICWA) (Chiang et al., 2017) is a cluster
based ensembling method that uses affinity propagation (BJ and Dueck D.,
2007).

  6. 6.

Maximum Scoring (Max) (Aggarwal and Sathe, 2015) uses the maximum of the
anomaly scores for each observation.

  7. 7.

Threshold Sum (Thresh) (Aggarwal and Sathe, 2015) uses the summation of
anomaly scores above the mean.

As our performance metric $\xi$, we use the area under the ROC curve denoted
by AUC. For our dataset collections $\chi$, we use two collections from two
separate approaches:  1. synthetic data, for which we generate the anomalies
using statistical methods and  2. a data repository containing more than
12,000 AD datasets (Kandanaarachchi et al., 2019).

Next, we briefly introduce IRT.

###  2.2 IRT

Item Response Theory (IRT) (Embretson and Reise, 2013; van der Linden and
Hambleton, 2013) refers to a family of latent trait models that is used to
explain the relationship between unobservable characteristics such as
intelligence or verbal ability and their observed outcomes such as responses
to questionnaires. The underlying attributes such as intelligence or racial
prejudice, which cannot be measured directly are modeled as latent variables.

An IRT model is fitted using the responses of participants to test items,
which are typically test questions. Depending on the type of response,
different types of models are fitted. If the response is binary, a dichotomous
IRT model is fitted. A polytomous model is fitted to discrete valued responses
and a continuous model to continuous valued responses. Furthermore, the term
“response”, which is traditionally used in the IRT literature can be somewhat
misleading. For example, in educational testing a score derived from the
participant’s answers are used as responses in the IRT model.

####  2.2.1 Dichotomous IRT

Suppose there are $i=1,2,\ldots,N$ participants and $j=1,2,\ldots,n$ test
items. Let $y_{ij}\in\\{0,1\\}$ denote the score or response of the
$i^{\text{th}}$ participant to the $j^{\text{th}}$ test item. The
discrimination parameter for test item $j$ is denoted by $\alpha_{j}$ and the
difficulty parameter by $\beta_{j}$. These two parameters are used to build
the 2-Parameter Logistic (2PL) model, giving the probability of a correct
response for each item given the ability level $\theta_{i}$ as

$\Phi\left(y_{ij}=1|\theta_{i},\alpha_{j},\beta_{j}\right)=\frac{1}{1+\exp\left(-\alpha_{j}\left(\theta_{i}-\beta_{j}\right)\right)}\,.$
(2)

Figure 2: The probability of the correct response for a test item using
equation (2). The discrimination $\alpha_{j}$ is proportional the slope of the
tangent line at $\Phi=0.5$.

Figure 2 shows an example item characteristic curve fitted using a 2PL model.
The discrimination of this test item $\alpha_{j}$ is proportional to the slope
of the tangent line drawn at $\Phi=0.5$. When $\theta_{i}=\beta_{j}$,
$\Phi=0.5$, that is when the difficulty of the test question equals the
ability of the participant, the probability of obtaining the correct answer is
0.5. If the participant ability is higher than the item difficulty, then the
probability of getting the correct answer is higher than 0.5 and vice versa.

####  2.2.2 Continuous IRT

Next, we consider the continuous response model formulation proposed by Wang
and Shojima (Wang and Zeng, 1998; Shojima, 2005), which extends the continuous
model introduced by Samejima (Samejima, 1969). Suppose there are
$i=1,2,\ldots,N$ participants and $j=1,2,\ldots,n$ test items. As before, let
$y_{ij}$ denote the score or response of the $i^{\text{th}}$ participant to
the $j^{\text{th}}$ test item. Then we scale $y_{ij}\in(0,k)$ by defining
$x_{ij}=y_{ij}/k$, so that $x_{ij}\in(0,1)$. Let $\theta_{i}$ denote the trait
variable of the $i^{\text{th}}$ participant and
$\bm{\lambda}_{j}=(\alpha_{j},\beta_{j},\gamma_{j})^{T}$ denote the item
parameters of the $j^{\text{th}}$ test item where $\alpha_{j}$ denotes the
discrimination, $\beta_{j}$ difficulty and $\gamma_{j}$ a scaling coefficient.
Using the Gaussian, the probability of a participant with ability $\theta$
obtaining a score $x$ or higher for item $j$ is modeled as

$P\left(X\geq
x|\theta\right)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{v}e^{-\frac{t^{2}}{2}}dt\,,$
(3)

where

$v=\alpha_{j}\left(\theta-\beta_{j}-\gamma_{j}\ln\frac{x}{1-x}\right)\,.$ (4)

With the reparametrization

$z=\ln\frac{x}{1-x}\,,$ (5)

the probability density function $f\left(z|\theta\right)$ obtained by
differentiating the cumulative density function $1-P\left(X\geq
x|\theta\right)$ using equation (3) is given by

$f\left(z|\theta\right)=\frac{\alpha_{j}\gamma_{j}}{\sqrt{2\pi}}\exp\left(-\frac{\alpha_{j}^{2}}{2}\left(\theta-\beta_{j}-\gamma_{j}z\right)^{2}\right)\,.$
(6)

Equation (6) prescribes a surface of probabilities for every test item $j$ as
shown in Figure 3. That is, $f\left(z|\theta\right)$ is a function of the
normalized scores $z$ and the latent trait $\theta$ for fixed values of
$\alpha_{j}$, $\beta_{j}$ and $\gamma_{j}$.

Figure 3: The probability of the normalized response $z$ for test item $j$
using equation (6) with $\alpha_{j}=1$, $\beta_{j}=0$ and $\gamma_{j}=1$.

Both test items in Figures 2 and 3 have positive discrimination. That is, as
the participant ability $\theta$ increases, the probability of getting a
higher score increases. If an item has negative discrimination, the slope of
the line in Figure 2 would be negative and similarly, the high density yellow
region in Figure 3 will have a negative slope. In educational testing, items
with negative discrimination are considered non-value adding because
participants with higher ability obtain lower scores than participants with
lower ability for such items. As such, these items are removed before the
model is fitted. We have extended the present educational testing model
(Shojima, 2005) to include negative discrimination items (Kandanaarachchi and
Smith-Miles, 2020) as our focus is on algorithms and their performance and as
such we do not want to remove negative discrimination items from the pool.

The continuous IRT model (Shojima, 2005) maximizes the log-likelihood

$\displaystyle E$
$\displaystyle=N\sum_{j=1}^{n}\left(\ln\alpha_{j}+\ln\gamma_{j}\right)$
$\displaystyle-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{n}\alpha_{j}^{2}\left(\left(\beta_{j}+\gamma_{j}z_{ij}-\mu_{i}^{(t)}\right)^{2}+\sigma^{(t)2}\right)$
$\displaystyle+\ln p\left(\bm{\Lambda}\right)+\text{const}\,,$ (7)

where $\alpha_{j},\gamma_{j}>0$ for all $j$, $\mu_{i}^{(t)}$ and
$\sigma^{(t)}$ denote the mean and standard deviation of $\theta_{i}$ computed
in the $t^{\text{th}}$ iteration,
$\bm{\Lambda}=\left(\bm{\lambda_{1}},\ldots,\bm{\lambda_{n}}\right)$ with
$\bm{\lambda_{j}}=\left(\alpha_{j},\beta_{j},\gamma_{j}\right)^{T}$ and $p$
denotes a prior distribution. While fitting the IRT model if $\alpha_{j}$ or
$\gamma_{j}$ becomes negative, then it stops the convergence process as
equation (2.2.2) becomes undefined due to the logarithm. However, the
probability density function given in equation (6) is well defined if both
$\alpha_{j}$ and $\gamma_{j}$ are negative. Thus, equation (2.2.2) only
accommodates half of the possible $\alpha_{j}$ and $\gamma_{j}$ values,
because the real constraint is that the product $\alpha_{j}\gamma_{j}>0$. We
correct this problem by updating the log-likelihood function as follows:

$\displaystyle E$
$\displaystyle=N\sum_{j=1}^{n}\left(\ln|\alpha_{j}|+\ln|\gamma_{j}|\right)$
$\displaystyle-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{n}\alpha_{j}^{2}\left(\left(\beta_{j}+\gamma_{j}z_{ij}-\mu_{i}^{(t)}\right)^{2}+\sigma^{(t)2}\right)$
$\displaystyle+\ln p\left(\bm{\Lambda}\right)+\text{const}\,.$ (8)

This modified function agrees with the real constraint
$\alpha_{j}\gamma_{j}>0$ and involves minor updates to the parameter values.
Following through the computation (Shojima, 2005), the discrimination
parameter $\alpha_{j}$ changes to

$\alpha_{j}^{(t+1)}=\operatorname{sign}\left(\gamma_{j}^{(t+1)}\right)\alpha_{j,\text{ori}}^{(t+1)}\,,$
(9)

where $\alpha_{j,\text{ori}}$ denotes the discrimination parameter in the
original computation and $t$ denotes the iteration. The parameter
$\gamma_{j}$, which is a scaling coefficient can obtain negative values in
this formulation, while the other parameters remain unchanged. More details of
this update are available at Kandanaarachchi and Smith-Miles (2020).

The maximum likelihood estimate of the latent trait parameter $\theta_{i}$ is
computed using the converged estimates of the item parameters
$\hat{\alpha}_{j}$, $\hat{\beta}_{j}$ and $\hat{\gamma}_{j}$ as follows:

$\theta_{i}=\frac{\sum_{j}\hat{\alpha}_{j}^{2}\left(\hat{\beta}_{j}+\hat{\gamma}_{j}z_{ij}\right)}{\sum_{j}\hat{\alpha}_{j}^{2}}\,.$
(10)

We see that the latent trait parameter $\theta_{i}$, which denotes the ability
of participant $i$ is a function of item discrimination $\alpha_{j}$,
difficulty $\beta_{j}$, scaling factor $\gamma_{j}$ as well as the test scores
$z_{ij}$.

##  3 Mapping IRT to ensemble learning

We start this Section by discussing the traditional IRT mapping used in
educational testing and psychometrics. Then we introduce newer IRT mappings
currently used for machine learning tasks including our proposed IRT mapping
for ensemble learning.

###  3.1 Educational testing and psychometrics

In educational testing participants sit for tests, and the test item scores
are used to fit the IRT model. In this setting $y_{ij}$ is the score of the
$i^{\text{th}}$ participant to the $j^{\text{th}}$ test item. This is shown in
Figure 4 with the forward arrow indicating the action of doing each test item.
From this IRT model we obtain item discrimination and difficulty for test
items, and and participant ability for participants.

Participant 1Participant NItem 1Item n⋮⋮ Matrix of derived scores $Y_{N\times
n}$ IRT Model Figure 4: Participants doing test items in the educational
testing scenario. The matrix of derived test scores/marks are used to fit the
IRT model.

In educational testing, the test item scores or marks that are derived from
the original user responses are used in the IRT model. In some branches of
psychometrics such as self esteem or personality assessment studies, the
original responses are used in the IRT model (Gray-Little et al., 1997). This
is because in such scenarios the test items are statements such as I feel that
I have a number of good qualities or I take a positive attitude toward myself
(Rosenberg, 1965), and thus requires the user to agree or disagree with the
statements using a rating scale. In such instances there is nothing to derive
in terms of the responses, i.e. there is no correct or wrong answer for any
question. Therefore, the original responses are used in the IRT model.
Similarly, the original responses are also used in studies investigating
underlying prejudice. Villano et al. (2017) use IRT to explore stereotyping
Roma people or gypsies in Italy. They used surveys having statements such as
Roma people do not want to integrate and prefer to be marginalized. Again, the
original responses are used in these IRT models. Figure 5 shows this model.
The latent trait in this IRT model determines a hidden quality such as self
esteem, a hidden prejudice or some personality trait of the participants.

Participant 1Participant NItem 1Item n⋮⋮ Matrix of original responses
$Y_{N\times n}$ IRT Model Figure 5: Participants doing a psychometrics
questionnaire. The matrix of original responses are used to fit the IRT model.

Here, we make a distinction between the original responses and the derived
scores. Derived scores are obtained using an accuracy measure on the original
responses. Traditional IRT uses both; educational testing uses derived scores
which is an accuracy measure while personality trait studies uses original
responses.

###  3.2 Algorithm evaluation

In algorithm evaluation the standard approach is to map the participants to
algorithms, and test items to dataset observations (Martínez-Plumed et al.,
2019; Chen et al., 2020). This is illustrated in Figure 6. In this setting
$y_{ij}$ denotes an accuracy measure such as classification accuracy of the
$i^{\text{th}}$ algorithm on the $j^{\text{th}}$ observation making the rows
of matrix $Y$ depict the algorithms and the columns, observations. The
resulting IRT model gives the ability of the algorithms and the difficulty and
discrimination of the observations.

Algorithm 1Algorithm NObservation 1Observation n⋮⋮ Matrix of derived
accuracies $Y_{N\times n}$ IRT Model Figure 6: Algorithms acting on dataset
observations in the standard algorithm evaluation setting. An accuracy measure
is used in matrix $Y_{N\times n}$.

We used a different, inverted mapping that uses datasets instead of
observations to evaluate algorithm performance (Kandanaarachchi and Smith-
Miles, 2020). In this mapping participants were mapped to datasets and test
items were mapped to algorithms. We used an accuracy measure depending on the
class of algorithms. In this setting $y_{ij}$ denotes the accuracy of dataset
$i$ to algorithm $j$ making the rows of matrix $Y$ give the datasets and the
columns, algorithms. The resulting IRT model gives the discrimination and
difficulty of the algorithms and the ability parameter for the datasets, which
in essence denotes dataset easiness/difficulty.

Dataset 1Dataset NAlgorithm 1Algorithm n⋮⋮ Matrix of derived accuracies
$Y_{N\times n}$ IRT Model Figure 7: Datasets acting on algorithms in the
algorithm evaluation setting. An accuracy measure is used in the IRT model.

###  3.3 Chen’s classification ensemble

Chen and Ahn (2020) use the mapping shown in Figure 6 for their classification
ensemble. They use classification accuracy in their model, that is $y_{ij}=1$
if classifier $i$ correctly classifies observation $j$, or $y_{ij}=0$
otherwise. From this mapping they obtain the algorithm ability parameter
$\theta_{i}$ and compute a weight for each algorithm as

$w_{i}=\frac{e^{\theta_{i}}}{\sum_{i=1}^{N}e^{\theta_{i}}}\,.$ (11)

The weights $w_{i}$ are computed from a training set and applied to a test set
to obtain the ensemble output as a weighted sum.

This ensemble framework cannot be employed for unsupervised algorithms because
it uses an accuracy measure, which is computed by comparing the algorithm
output to the ground truth. When an accuracy measure is used in the IRT model,
the parameter $\bm{\theta}=\\{\theta_{i}\\}_{i=1}^{N}$ denotes the ability of
the algorithm/participant in the standard sense of the word, that is, it is
indeed a skill. When the original responses are used, $\bm{\theta}$ denotes a
hidden quality such as self-esteem, a prejudice or a personality trait.

###  3.4 Proposed AD ensemble

Observation 1Observation NAlgorithm 1Algorithm n⋮⋮ Matrix of original
responses $Y_{N\times n}$ IRT Model Figure 8: The proposed IRT mapping for AD
ensemble learning. Observations acting on algorithms with original responses
used in matrix $Y_{N\times n}$.

We propose the following IRT mapping for unsupervised AD ensemble learning.

  1. 1.

We use the original responses instead of an accuracy measure. Specifically, we
use the standardized original responses of algorithms. The standardization is
done to effectively compare the output of different algorithms. Especially in
anomaly detection, the anomaly responses of different algorithms may be vastly
different (see Figure 1) and as such standardizing the output of each
algorithm to the interval $[0,1]$ places all algorithms on the same scale.

  2. 2.

We map participants to dataset observations and test items to algorithms.

This mapping is shown in Figure 8. In this setting $y_{ij}$ denotes the scaled
response of observation $i$ to algorithm $j$. This is different from the
algorithm evaluation mapping in Figure 7, because it uses the original
responses instead of accuracy measures and also it is constructed at an
observational level instead of at a dataset level. Furthermore, the goal of
the mapping in Figure 7 is to evaluate a portfolio of algorithms using an
accuracy measure, whereas here we are interested in constructing an ensemble
using the latent trait continuum.

IRT Mappings Accuracy Measures Original Responses Traditional IRT Educational
testing IRT in Machine Learning Standard mapping Inverted mapping Algorithm
evaluation (Martínez-Plumed et al., 2019; Chen et al., 2020) Classification
ensemble (Chen and Ahn, 2020) Algorithm evaluation (Kandanaarachchi and Smith-
Miles, 2020) Traditional IRT IRT in Machine Learning Personality trait studies
Unsupervised AD ensemble (this work) Figure 9: Different IRT mappings in
traditional and machine learning settings.

We summarize the different IRT configurations or mappings in Figure 9. Then we
examine the IRT parameters of the AD ensemble framework.

####  3.4.1 The latent trait

In educational testing, the latent trait continuum holds participants ordered
by their ability. As test item scores are used to fit the IRT model, the
ability generally increases with the test item scores. However, ability is not
perfectly correlated with the total score, because the hardness of the test
items is taken into account. For example a participant who obtains correct
answers for more difficult test items and misses a couple of easy test
questions will have a higher ability than a participant who misses the harder
questions but gets all the easy test questions correct.

When the original responses are used in the IRT model, the latent trait
continuum holds a hidden quality such as self esteem, which is tested by the
survey. Again, the participants are ordered in the latent trait continuum by
this quality. When participants are mapped to observations in the ensemble
setting, the parameter $\bm{\theta}$ denotes a certain quality about the
observations. In addition, when the standardized algorithm response is used
instead of an accuracy measure, the new trait parameter increases with the
algorithm response. But the algorithm response is the anomaly score assigned
to each observation. As such, $\bm{\theta}$ increases with the anomaly score,
which is a measure of the anomalousness of the observations. Thus, the
parameter $\theta_{i}$ denotes the level of anomalousness of observation $i$,
taking into account all the AD methods. Therefore, it is an ensemble score.

####  3.4.2 The difficulty parameter $\beta$

The interpretation of the difficulty parameter does not change much. For
positively discriminated algorithms, if an observation $i$ has
$\theta_{i}>\beta_{j}$, then it makes the normalized response $z>0$ more
probable. Therefore, $\beta_{j}$ is the anomalousness threshold of algorithm
$j$ for obtaining $z=0$. For anomaly detection a higher anomalousness
threshold $\beta$ is preferred as this would result in fewer anomalies.
However, we need to consider the discrimination parameter as well to get a
better understanding of the algorithm.

Figure 10: The probability $f(z|\theta)$ for test item $j$ using equation (6)
with $\alpha_{j}=1$, $\beta_{j}=3$ and $\gamma_{j}=1$ on the left and
$\alpha_{j}=2$, $\beta_{j}=3$ and $\gamma_{j}=1$ on the right.

####  3.4.3 The discrimination parameter $\alpha$

Similar to the difficulty parameter, the interpretation of the discrimination
parameter remains unchanged with higher values of $\alpha$ denoting sharper
transitions in probability for different values of $z$ or $\theta$. This is
illustrated in Figure 10. The plot on the left has $\alpha_{j}=1$ and the plot
on the right has $\alpha_{j}=2$. Both have $\beta_{j}=3$. An anomaly detection
method with a lower discrimination parameter would give similar scores for
anomalies and non-anomalies. Therefore, a higher discrimination parameter is
preferred.

####  3.4.4 The scaling parameter $\gamma$

The parameter $\gamma$ is not a traditional IRT parameter. Instead it is used
for scaling purposes to assure that $f(z|\theta)$ is indeed a probability
density function, i.e. the area under the curve for any fixed $\theta$ adds up
to 1. Even though it does not have a traditional IRT meaning, the scaling
parameter $\gamma_{j}$ plays a part in determining the latent trait spectrum.
Going back to equation (10) we see that the latent trait parameter,

$\displaystyle\theta_{i}$
$\displaystyle=\frac{\sum_{j}\hat{\alpha}_{j}^{2}\left(\hat{\beta}_{j}+\hat{\gamma}_{j}z_{ij}\right)}{\sum_{j}\hat{\alpha}_{j}^{2}}\,,$
$\displaystyle=\sum_{j}\left(\frac{\hat{\alpha}_{j}^{2}\hat{\beta}_{j}}{\sum_{j}\hat{\alpha}_{j}^{2}}+\frac{\hat{\alpha}_{j}^{2}\hat{\gamma}_{j}}{\sum_{j}\hat{\alpha}_{j}^{2}}z_{ij}\right)\,,$
$\displaystyle=\sum_{j}\left(\zeta_{j}+\omega_{j}z_{ij}\right)\,,$ (12)

with
$\zeta_{j}=\frac{\hat{\alpha}_{j}^{2}\hat{\beta}_{j}}{\sum_{j}\hat{\alpha}_{j}^{2}}$
and
$\omega_{j}=\frac{\hat{\alpha}_{j}^{2}\hat{\gamma}_{j}}{\sum_{j}\hat{\alpha}_{j}^{2}}$.
Noting that $\sum_{j}\zeta_{j}$ and $\sum_{j}\hat{\alpha}_{j}^{2}$ are
constant for a given IRT model, we see that the anomaly response of the
$i^{\text{th}}$ observation to the $j^{\text{th}}$ algorithm, $z_{ij}$ gets
weighted by $\omega_{j}$, which is a scaled product of the discrimination and
the scaling parameters $\alpha_{j}$ and $\gamma_{j}$ of AD algorithm $j$.
Therefore, if an AD method has high discrimination and scaling parameters, the
anomaly responses of that method are weighted higher and contribute more to
the ensemble score.

##  4 Experiments with synthetic data

First we discuss the parameters of the ensemble methods. The Greedy ensemble
requires a parameter $\kappa$, which is an estimate of the number of anomalies
in the dataset. In our synthetic experiments, we have set $\kappa$ to the
exact number of anomalies so that we evaluate the Greedy ensemble at its best.
However, as we do not know the number of anomalies in practice, we consider
the averaged Greedy ensemble, which runs the Greedy ensemble for different
values of $\kappa$ and averages the output. For the synthetic examples we vary
$\kappa$ from 1 to 10. The clustering based ensemble method ICWA can be used
with various similarity measures. Of the similarity measures listed in Chiang
et al. (2017), we use Pearson’s correlation.

Using these parameters, we illustrate the performance of the ensembles using a
simple example in $\mathbb{R}^{2}$. Then we conduct 3 iterated experiments,
which are set up so that the anomalies become more marked with each iteration.
We compare the performance of the ensemble methods for these iterated
experiments.

###  4.1 Example

We consider a simple example of an annulus with 3 anomalies placed at the
center. We obtain the anomaly responses from the AD methods and construct the
AD ensembles. Figure 11 shows the scaled ensemble scores of the 7 ensemble
methods. The Greedy ensemble is used twice with different parameters,
$\kappa=3$ and $\kappa=10$.

Figure 11: The AD ensemble scores for the Example. Annulus with 3 anomalies at
the center.

The Average ensemble performs reasonably well obtaining high ensemble scores
for the anomalies in the center. However, it also obtains high scores for at
least 2 more points on the boundary of the annulus. The Greedy ensemble with
$\kappa=3$, labeled Greedy1, also gives good performance. But by setting
$\kappa=3$, we have selected the best value for parameter $\kappa$ as there
are exactly 3 anomalies. When we use $\kappa=10$, the Greedy ensemble performs
poorly as seen in the pane labeled Greedy2. Thus, the Greedy ensemble is very
sensitive to parameter selection. As Greedy-Avg averages the ensemble scores
for different values of $\kappa$, its performance lies in between Greedy1 and
Greedy2. ICWA finds two boundary points as most anomalous, disregarding the
real anomalies. IRT gives high ensemble scores to the anomalies and low scores
to the other points. The Max ensemble gives poor performance, while Thresh is
similar to the Average ensemble.

A point of interest is that the IRT ensemble gives a low ensemble score to the
observation positioned approximately at $(5,7.5)$, while Average, Thresh and
ICWA gives relatively high scores to that observation. Upon inspection we see
that the scaled anomaly responses for KNN-AGG, LOF, COF, INFLO, KDEOS, LDF and
LDOF are 0.48, 0.56, 0.62, 1, 0.98, 0.74 and 1 respectively, where all anomaly
responses are scaled to the interval $[0,1]$. Thus, INFLO, KDEOS and LDOF have
very high anomaly responses for this observation. But, as seen from Table 1
the discrimination parameter $\alpha_{j}$ is small for LDOF, INFLO and KDEOS
compared with the $\alpha_{j}$ values for LOF and LDF. As a result, these
responses get discounted when computing the latent score. This illustrates how
the IRT ensemble downplays certain methods while highlighting other methods.

Table 1: IRT parameters discrimination $(\alpha)$, difficulty $(\beta)$ and the scaling parameter $(\gamma)$ for the example and the synthetic experiments. Method | Example | EX1 | EX2 | EX3
---|---|---|---|---
$\alpha$ | $\beta$ | $\gamma$ | $\alpha$ | $\beta$ | $\gamma$ | $\alpha$ | $\beta$ | $\gamma$ | $\alpha$ | $\beta$ | $\gamma$
KNN-AGG | 1.6 | 3.3 | 0.7 | 1.4 | 2.6 | 0.7 | 1.3 | 2.1 | 0.7 | 2.1 | 1.8 | 0.8
LOF | 14.0 | 3.3 | 0.9 | 2.7 | 1.7 | 0.9 | 5.0 | 2.3 | 0.8 | 2.3 | 1.9 | 0.9
COF | 0.9 | 2.7 | 0.5 | 1.1 | 1.1 | 0.7 | 1.0 | 2.3 | 0.6 | 1.2 | 1.5 | 0.6
INFLO | 0.3 | 7.7 | 0.1 | 0.6 | 2.6 | 0.4 | 0.5 | 3.7 | 0.3 | 0.7 | 3.2 | 0.4
KDEOS | 1.1 | 0.0 | 1.3 | 0.9 | 0.0 | 1.2 | 0.8 | 0.0 | 1.2 | 1.0 | 0.0 | 1.3
LDF | 6.2 | 2.4 | 0.9 | 1.4 | 1.0 | 0.9 | 2.1 | 1.1 | 0.8 | 1.6 | 0.6 | 0.9
LDOF | 0.6 | 5.8 | 0.4 | 0.8 | 2.4 | 0.6 | 0.6 | 4.1 | 0.5 | 0.9 | 2.3 | 0.6

###  4.2 Experiment 1

The first experiment consists of two normal distributions in $\mathbb{R}^{6}$
with one distribution signifying the anomalies, slowly moving out of the main
distribution with each iteration. We consider 5 anomalies and 400 non-
anomalies. In each dimension the non-anomalies are distributed as
$\mathcal{N}\left(0,1\right)$. In the first dimension, the anomalies are
distributed as $\mathcal{N}\left(2+(i-1)/2,0.2\right)$ where $i$ denotes the
iteration of the experiment. Thus, in the first iteration the anomalies start
with $\mathcal{N}\left(2,0.2\right)$ and in the $10^{\text{th}}$ iteration
they are distributed as $\mathcal{N}\left(6.5,0.2\right)$ in the first
dimension. Figures 12(a) and (b) show the anomalies in the first two
dimensions in the $5^{\text{th}}$ and the $10^{\text{th}}$ iterations. In
other dimensions the anomalies are distributed similar to the non-anomalies. A
lower standard deviation is chosen for the anomalous distribution in dimension
1, so that they are apart from the non-anomalies for higher iterations. In
order to account for randomness, we repeat each iteration 10 times.

Figure 12: Experiment 1: the anomalies moving out in each iteration. (a) The
$X_{1}X_{2}$ plane in the $5^{\text{th}}$ iteration. (b) The $X_{1}X_{2}$
plane in the $10^{\text{th}}$ iteration. (c) Comparison of the AUC scores
using IRT and 6 benchmark ensemble methods.

Figure 12(c) shows the average AUC over 10 repetitions for each iteration. We
see that the IRT ensemble achieves better results compared to the other 6
ensemble methods. Student’s t-tests conducted on the differences in
performance values, such as IRT performance - Greedy performance, are given in
Table 2. All t-tests were statistically significant with $p$-values less than
$10^{-6}$ in favor of the IRT ensemble. From Table 2 we see that IRT ensemble
achieves better performance compared to the benchmarks.

Table 2: Student’s t-test results of the performance differences (%) for the synthetic experiments Performance Difference | EX1 | EX2 | EX3
---|---|---|---
IRT - Average | 3.73 | 4.63 | 4.86
IRT - Greedy | 3.84 | 4.63 | 6.95
IRT - Greedy_Avg | 4.97 | 4.97 | 5.95
IRT - ICWA | 13.26 | 9.99 | 16.98
IRT - Max | 5.78 | 8.58 | 10.20
IRT - Thresh | 6.10 | 6.83 | 7.52

###  4.3 Experiment 2

For this experiment we consider data points in $\mathbb{R}^{4}$ that are
distributed in an annulus in the first two dimensions and normally distributed
with mean 0 and standard deviation 1 in the third and fourth dimensions.
Similar to the previous experiment we consider two distributions with the
anomalous distribution moving into the center. The anomalies only differ in
the first two coordinates $x_{1}$ and $x_{2}$ with
$x_{1}\sim\mathcal{N}\left(5-(i-1)/2,0.1\right)$ and
$x_{2}\sim\mathcal{N}(0,0.1)$. We consider 805 points, which includes 5
anomalies. Figures 13(a) and (b) show the data on the $X_{1}X_{2}$ plane in
its $5^{\text{th}}$ and $10^{\text{th}}$ iterations.

Figure 13: Experiment 2: the anomalies moving into the annulus in each
iteration. (a) The $X_{1}X_{2}$ plane in the $5^{\text{th}}$ iteration. (b)
The $X_{1}X_{2}$ plane in the $10^{\text{th}}$ iteration. (c) Comparison of
the AUC scores using IRT and 6 benchmark ensemble methods.

Figure 13(c) shows the AUC results for each iteration of Experiment 2. We see
that the IRT ensemble outperforms the other six ensembles. This is further
confirmed by the Student’s t-tests conducted on the AUC results. All t-tests
were statistically significant with $p$-values less than $10^{-10}$. From
Table 2 we see that the IRT ensemble performs better than the other ensembles
by 4.6% to 9.9%.

###  4.4 Experiment 3

For this experiment we consider two normal distributions in $\mathbb{R}^{6}$,
each having $400$ points centered at $(-5,0,0,0,0,0,0,0)$ and
$(5,0,0,0,0,0,0,0)$ with standard deviation 1 in each dimension. This is a
bimodal distribution in the $x_{1}$ coordinate. A set of 5 anomalies,
distributed normally with mean $3-(i-1)*0.3$ and standard deviation $0.2$ in
the $x_{1}$ coordinate, where $i$ denotes the iteration, moves into the trough
with each iteration. In other dimensions all data points are distributed as
$\mathcal{N}\left(0,1\right)$. Figures 14(a) and (b) show the data points on
the $X_{1}X_{2}$ plane in its $5^{\text{th}}$ and $10^{\text{th}}$ iterations.
As in previous experiments, we repeat each iteration 10 times to account for
randomness.

Figure 14: Experiment 3: the anomalies moving into the trough in each
iteration. (a) The $X_{1}X_{2}$ plane in the $5^{\text{th}}$ iteration. (b)
The $X_{1}X_{2}$ plane in the $10^{\text{th}}$ iteration. (c) Comparison of
the AUC scores using IRT and 6 benchmark ensemble methods.

Figure 14(c) shows the AUC results of all 10 iterations. From the first
iteration the IRT ensemble surpasses the other ensemble methods. Table 2 gives
the t-test results of the performance differences, which are all statistically
significant with $p$-values less than $10^{-14}$. The IRT ensemble performs
better by 4.6% to 16%.

Table 1 gives the discrimination, difficulty and scaling parameters of the IRT
model for the example in Section 4.1 and the last iteration of the 3
experiments EX1 - EX3. For the experiments, we see that LOF, LDF and KNN-AGG
have higher discrimination parameters showing that they contribute more to the
latent trait computation and thus the anomaly ensemble score. In contrast, the
output of LDOF, KDEOS and INFLO are discounted.

##  5 Real-world experiments

We now evaluate our IRT ensemble on 12433 publicly available anomaly detection
datasets (Kandanaarachchi et al., 2019), which have been prepared from 119
source datasets by downsampling different classes. The minority class in each
downsampled dataset is considered anomalous. Similar to the synthetic
experiments, we compute the anomaly scores using the methods KNN-AGG, LOF,
COF, INFLO, KDEOS, LDF and LDOF and evaluate the performance using AUC. We
conduct this experiment twice with different parameter settings for the AD
methods. The first parameter setting uses small values of $k$ and the second
uses large values of $k$. We refer to these two takes of the experiment as T1
and T2:

  1. 1.

T1 uses the default values for $k=k_{\min}=5$ and $k_{\max}=10$, and

  2. 2.

T2 uses $k=k_{\min}=\max(\lceil N/10\rceil,50)$ and $k_{\max}=k+10$, making
$k$ larger for the second take of the experiment. The quantity $N$ denotes the
number of observations in the dataset.

We used a high performance computing facility to run T1 and T2. For each
dataset we allowed a maximum time limit of 60 minutes to complete the task.
While T1 was completed by all datasets, T2 was completed only by 11194
datasets belonging to 107 dataset sources due to increased computations
required by large $k$ values.

###  5.1 By individual dataset

Figure 15: The number of datasets grouped by the best performing ensemble for
T1 and T2.

Each dataset gives its best performance for a certain ensemble. Figure 15
shows the number of datasets grouped by the best performing ensemble for T1
and T2. Table 3 gives the percentages of datasets for the best performing
ensemble for these two tasks. We see that for both T1 and T2, IRT ensemble
surpasses the other ensembles by a big margin.

Table 3: Percentage of datasets for the best performing ensemble for T1 and T2 Experiment | Average | Greedy | Greedy-Avg | ICWA | IRT | Max | Thresh
---|---|---|---|---|---|---|---
T1 | 6.0 | 14.4 | 8.0 | 13.9 | 29.4 | 15.5 | 12.7
T2 | 5.1 | 13.4 | 6.3 | 12.7 | 33.0 | 18.3 | 11.1

###  5.2 By dataset source

Each dataset is obtained from a source dataset using a downsampling process.
As each dataset source has many variants, we compute the mean AUC by dataset
source. For each dataset source, the ensemble with the highest mean AUC is
called the best ensemble for that dataset source. Table 4 gives the best
ensemble performance percentages by dataset source and Figure 16 gives the
number of dataset sources grouped by the best performing ensemble. Again, we
see that IRT outperforms other algorithms. From Tables 3 and 4 we see that
IRT, Max and Thresh algorithms generally perform similarly both at the dataset
and the dataset source level. We also note that Average and Greedy-Avg
algorithms have larger percentages at the dataset source level compared to the
dataset level, while Greedy and ICWA have larger percentages at the dataset
level.

Figure 16: Best performance for dataset sources by the ensemble method.  Table 4: Percentage of dataset sources for the best performing ensembles for T1 and T2 Experiment | Average | Greedy | Greedy-Avg | ICWA | IRT | Max | Thresh
---|---|---|---|---|---|---|---
T1 | 11.8 | 8.4 | 14.3 | 9.2 | 28.6 | 15.1 | 12.6
T2 | 11.3 | 9.4 | 14.2 | 8.5 | 39.6 | 11.3 | 5.7

###  5.3 Statistically significant top 2 ensembles by dataset source

Next, we perform significance testing to further analyze these results. For
each dataset source, we select the top 2 algorithms and conduct a Student’s
t-test to check if there is a significant difference between them. That is, if
the mean performance of the best algorithm is $\mu_{1}$ and the mean
performance of the second best algorithm is $\mu_{2}$, we conduct a hypothesis
test with the null hypothesis $H_{0}:\,\mu_{1}=\mu_{2}$ against the
alternative $H_{a}:\,\mu_{1}>\mu_{2}$, for each dataset source. We use a
significance level $\alpha=0.05$.

Figure 17: T1 significant dataset sources. The IRT ensemble performs
significantly better for annthyroid, image, led, libras, mice, parkinson,
seeds, spambase and texture dataset sources. Greedy-Avg performs better for
banana and tao. Max performs better for forest and ICWA performs better for
wilt2.

To give some perspective of this statistical analysis, we conduct a simulated
experiment. We simulate equal performance values for 7 methods for 1190
dataset sources, which is 10 times the number of dataset sources we have. For
each dataset source we consider 100 datasets. Then, for each dataset source we
compare the top 2 performing methods with a significance level $\alpha=0.05$.
For all 1190 dataset sources we obtained 8 sources with significant
differences between the top 2 performing methods. These are false positives,
since we simulated equal performance values for all methods. When we repeat
this simulation 30 times, we get a mean false positive rate of 8.7 with a
standard deviation of 2.89. Therefore, for 119 dataset sources we can expect
$0.87\pm 0.29$ false positives.

We obtain 13 dataset sources with significant results in favor of the best
algorithm for T1. For T2, 10 dataset sources had significant results in favor
of the best algorithm. Table 5 gives these results. For T1, the IRT ensemble
significantly outperforms others in 9 of the 13 dataset sources. Greedy-Avg
performs best for 2 dataset sources and Max and ICWA perform best for 1
dataset source each. For T2, IRT gives the best results for 7 out of 10
dataset sources while Max performs best for 2 dataset sources and Greedy
performs best for 1 dataset source. We note that the number of competing
algorithms directly affect the number of dataset sources with significant
performance differences between the top 2 methods. For example, when we
compare IRT with Max, which is the next best algorithm (Figure 16(a)) for T1
in terms of dataset sources, we obtain 39 dataset sources with significant
differences, of which 32 are in favor of IRT.

Table 5: T1 and T2 significant dataset sources and the best algorithms T1 | T2
---|---
Source |  Best Algorithm | p-value |  Source |  Best Algorithm | p-value
annthyroid |  IRT | $<10^{-5}$ |  cardio10 |  Greedy | 0.031
banana |  Greedy-Avg | $<10^{-4}$ |  cardiotocography |  IRT | 0.042
forest |  Max | 0.023 |  ecoli |  IRT | 0.001
image |  IRT | $<10^{-4}$ |  first |  IRT | 0.020
led |  IRT | $<10^{-16}$ |  image |  IRT | $<10^{-3}$
libras |  IRT | 0.017 |  led |  Max |  ¡ $10^{-7}$
mice |  IRT | 0.005 |  phoneme |  IRT | 0.029
parkinson |  IRT | 0.038 |  robot5 |  IRT | $<10^{-3}$
seeds |  IRT | 0.025 |  spambase |  Max | 0.034
spambase |  IRT | $<10^{-4}$ |  texture |  IRT | 0.003
tao |  Greedy-Avg | 0.013 |  |  |
texture |  IRT | $<10^{-6}$ |  |  |
wilt2 |  ICWA | 0.003 |  |  |

Figure 18: T2 significant dataset sources. The IRT ensemble performs
significantly better for cardiotocography, ecoli, first, image, phoneme,
robot5 and texture dataset sources. Max performs better for led and spambase
while Greedy performs better for cardio10.

Figures 17 and 18 show the box plots for all 7 ensemble methods for the
significant dataset sources for T1 and T2. The randomness of the downsampling
process used in AD dataset preparation has resulted in high IQR and standard
deviation performance values for certain dataset sources. This is because when
we randomly downsample a certain class and label observations of that class as
anomalies, there is a chance that these observations are not actually
anomalous. Such a dataset would yield low performance values for all AD
methods, making the AD ensemble methods perform poorly on that dataset. This
is clearly seen in Figure 18. The image datasets have larger IQR values
compared to cardiotocography and the AUC values for image datasets range from
0.5 to 1 for many ensemble methods. In fact, large IQR or standard deviation
values are common in AD evaluation studies as a result of the downsampling
process. For example, we see large standard deviations per dataset source in
studies conducted by Campos et al. (2018) and Chiang et al. (2017). But,
because we conduct pairwise t-tests between the top 2 methods for each dataset
source, the difference in AUC values by dataset is considered. As we see in
Figure 19 the differences between the top 2 methods do not exhibit large IQR
values compared to previously. For example, we see that the large IQR values
for image datasets in Figure 18 is considerably reduced in Figure 19(b). Even
the relatively large IQR values present in datasets libras and led in Figure
19 are smaller than their original counterparts in Figures 17 and 18.
Generally, we obtain much lower IQR values for most dataset sources by using
pairwise differences between the top 2 ensemble methods. We also see that the
individual boxplots are mostly situated in the greater than zero region, which
explains why these dataset sources are significant.

Figure 19: AUC differences between the top 2 methods for each dataset source
for T1 and T2

###  5.4 Exploring correlation

To better understand the performance differences of AD ensemble methods, we
investigate the correlation matrix $\mathop{\text{cor}}(Y)$ of each dataset,
where matrix $Y$ contains the original anomaly responses from the 7 AD
methods. For each dataset we compute $\mathop{\text{cor}}(Y)$ and count the
number of entries greater than 0.9, 0.8 and 0.7 respectively. From these
counts, we deduct the number of ones on the diagonal, as this is redundant
information. We denote these values by Cor90, Cor80 and Cor70, and
collectively refer to them as correlation counts. Thus, if the anomaly
responses of different AD methods are highly correlated for a given dataset,
it would result in high correlation counts. Figure 20 shows the boxplots of
Cor70, Cor80 and Cor90 for significant datasets in T1 and T2. From these plots
we see that IRT performs well on datasets with both low and high correlation
counts. But we also see that only IRT performs well on datasets with very low
correlation counts. For example in Figure 20(a) the dataset sources with zero
median values for Cor70, Cor80 and Cor90 are texture, mice, libras and image.
And, IRT is the best algorithm for these dataset sources. Similarly, in Figure
20(b) the dataset sources with zero median values for Cor90 are texture, first
and cardiotocography. Again, IRT is the best ensemble method for these dataset
sources.

Figure 20: Correlation counts for significant dataset sources in T1 and T2

These observations may indicate a possible strength of the IRT ensemble for
datasets with low correlation counts. However, the significant dataset sources
are heavily dominated by IRT in terms of best performance, which can induce a
random result in favor of IRT for datasets with low correlation counts.
Therefore, we explore this further using the full data repository of 12000+
datasets. For both T1 and T2, we focus on the datasets with $Cor70=0$, that
is, the correlation matrix of the anomaly responses $\mathop{\text{cor}}(Y)$
of that dataset has no correlation values above 0.7, which also implies that
$Cor80=Cor90=0$. Let us call this group of datasets Low_Cor and the rest
High_Cor. We compare the proportion of the best performing algorithms for
Low_Cor and High_Cor datasets for both T1 and T2. Figure 21 shows these
results. For T1, there were 3394 Low_Cor datasets and for T2 there were 189.
From Figures 21(a) and (b) we see that IRT not only has the highest, best
performance proportion when we consider all datasets, it has even better
performance for Low_Cor datasets.

Figure 21: High_Cor, Low_Cor and overall dataset performance for different
ensemble algorithms for T1 and T2.

Going back to traditional IRT, correlation values can be low in educational
testing. For example, the correlation of marks between a very easy question
and a very difficult question can be extremely low. By computing difficulty
and discrimination of test items, IRT has built in capability to accommodate
low correlated items. We see this as a particular strength of IRT when
computing an ensemble score.

##  6 Conclusions

Most ensemble techniques use the ground truth or the class labels to construct
an ensemble score. As the ground truth is not known in unsupervised anomaly
detection, constructing an ensemble using a set of heterogeneous AD methods is
a challenge. We have introduced a novel ensemble framework for anomaly
detection using Item Response Theory that uses IRT’s latent trait, which
denotes an underlying characteristic, to compute the ground truth. Latent
trait modeling has not been used before in AD ensembles to the best of our
knowledge.

Using 6 other AD ensemble techniques, we evaluated the IRT ensemble on
synthetic and real-world data. The results demonstrated that our method is
very attractive for anomaly detection ensembling tasks. Furthermore, we see
that the IRT ensemble has a unique strength for datasets with low correlation
values in $\mathop{\text{cor}}(Y)$. This is advantageous when constructing an
ensemble using diverse methods. As future research avenues, we plan to
consider IRT ensembles for other unsupervised machine learning tasks and to
extend this framework for supervised tasks.

## Supplementary Material

The IRT ensemble and the other AD ensembles are available in the R package
outlierensembles (Kandanaarachchi, 2021). The programming scripts are
available at
https://github.com/sevvandi/supplementary_material/anomalyensembles.

## References

  * (1)
  * Aggarwal and Sathe (2015) Aggarwal, C. C. and Sathe, S. (2015), ‘Theoretical Foundations and Algorithms for Outlier Ensembles’, ACM SIGKDD Explorations Newsletter 17(1), 24–47.
  * Angiulli and Pizzuti (2002) Angiulli, F. and Pizzuti, C. (2002), ‘Fast outlier detection in high dimensional spaces’, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2431 LNAI, 15–27.
  * BJ and Dueck D. (2007) BJ, F. and Dueck D. (2007), ‘Clustering by passing messages between data points’, Science 315(5814), 972–976.
  * Breunig et al. (2000) Breunig, M. M., Kriegel, H. P., Ng, R. T. and Sander, J. (2000), LOF: Identifying density-based local outliers, in ‘SIGMOD Record (ACM Special Interest Group on Management of Data)’, Vol. 29, pp. 93–104.
  * Campos et al. (2018) Campos, G. O., Zimek, A. and Meira, W. (2018), ‘An unsupervised boosting strategy for outlier detection ensembles’, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 10937, LNAI 564–576.
  * Chen et al. (2020) Chen, Y., Filho, T. S., Prudêncio, R. B., Diethe, T. and Flach, P. (2020), ‘$\beta^{3}$-IRT: A new Item Response Model and its Applications’, AISTATS 2019 - 22nd International Conference on Artificial Intelligence and Statistics .
  * Chen and Ahn (2020) Chen, Z. and Ahn, H. (2020), ‘Item Response Theory Based Ensemble in Machine Learning’, International Journal of Automation and Computing 17(5), 621–636.
  * Chiang et al. (2017) Chiang, A., David, E., Lee, Y. J., Leshem, G. and Yeh, Y. R. (2017), ‘A study on anomaly detection ensembles’, Journal of Applied Logic 21, 1–13.
  * Embretson and Reise (2013) Embretson, S. E. and Reise, S. P. (2013), Item Response Theory, Psychology Press.
  * Gray-Little et al. (1997) Gray-Little, B., Williams, V. S. and Hancock, T. D. (1997), ‘An item response theory analysis of the Rosenberg self-esteem scale’, Personality and Social Psychology Bulletin 23(5), 443–451.
  * Jin et al. (2006) Jin, W., Tung, A. K., Han, J. and Wang, W. (2006), Ranking outliers using symmetric neighborhood relationship, in ‘Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)’, Vol. 3918 LNAI, pp. 577–593.
  * Kandanaarachchi (2021) Kandanaarachchi, S. (2021), outlierensembles: A Collection of Outlier Ensemble Algorithms.  R package version 0.0.0.9000.
https://github.com/sevvandi/outlierensembles

  * Kandanaarachchi et al. (2019) Kandanaarachchi, S., Muñoz Acosta, M., Smith-Miles, K. and Hyndman, R. (2019), ‘Datasets for outlier detection’.
https://monash.figshare.com/articles/Datasets_12338_zip/7705127/4

  * Kandanaarachchi and Smith-Miles (2020) Kandanaarachchi, S. and Smith-Miles, K. (2020), ‘Evaluating algorithms using Item Response Theory’, Pre-print .
https://www.researchgate.net/publication/341150504_Evaluating_algorithms_using_Item_Response_Theory

  * Latecki et al. (2007) Latecki, L. J., Lazarevic, A. and Pokrajac, D. (2007), Outlier detection with kernel density functions, in ‘Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)’, Vol. 4571 LNAI, pp. 61–75.
  * Lazarevic and Kumar (2005) Lazarevic, A. and Kumar, V. (2005), ‘Feature bagging for outlier detection’, Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining pp. 157–166.
  * Madsen (2018) Madsen, J. H. (2018), DDoutlier: Distance & Density-Based Outlier Detection.  R package version 0.1.0.
https://CRAN.R-project.org/package=DDoutlier

  * Martínez-Plumed et al. (2019) Martínez-Plumed, F., Prudêncio, R. B., Martínez-Usó, A. and Hernández-Orallo, J. (2019), ‘Item Response Theory in AI: Analysing machine learning classifiers at the instance level’, Artificial Intelligence 271, 18–42.
  * Rayana and Akoglu (2016) Rayana, S. and Akoglu, L. (2016), ‘Less is more: Building selective anomaly ensembles’, ACM Transactions on Knowledge Discovery from Data 10(4).
  * Rosenberg (1965) Rosenberg, M. (1965), ‘Rosenberg self-esteem scale (RSE)’, Acceptance and commitment therapy. Measures package 61(52), 18.
  * Samejima (1969) Samejima, F. (1969), ‘Estimation of latent ability using a response pattern of graded scores.’, Psychometrika monograph supplement 34, 1–97.
  * Schubert et al. (2012) Schubert, E., Wojdanowski, R., Zimek, A. and Kriegel, H. P. (2012), On evaluation of outlier rankings and outlier scores, in ‘Proceedings of the 12th SIAM International Conference on Data Mining, SDM 2012’, pp. 1047–1058.
  * Schubert et al. (2014) Schubert, E., Zimek, A. and Kriegel, H. P. (2014), Generalized outlier detection with flexible kernel density estimates, in ‘SIAM International Conference on Data Mining 2014, SDM 2014’, Vol. 2, pp. 542–550.
  * Shojima (2005) Shojima, K. (2005), ‘A noniterative item parameter solution in each EM cycle of the continuous response model’, Educational technology research 28(1), 11–22.
  * Tang et al. (2002) Tang, J., Chen, Z., Fu, A. W. C. and Cheung, D. W. (2002), ‘Enhancing effectiveness of Outlier detections for low Density Patterns’, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 2336, 535–548.
  * van der Linden and Hambleton (2013) van der Linden, W. J. and Hambleton, R. K. (2013), Handbook of modern Item Response Theory, Springer Science & Business Media.
  * Villano et al. (2017) Villano, P., Fontanella, L., Fontanella, S. and Donato, M. D. (2017), ‘Stereotyping Roma people in Italy: IRT models for ambivalent prejudice measurement’, International Journal of Intercultural Relations 57, 30–41.
  * Wang and Zeng (1998) Wang, T. and Zeng, L. (1998), ‘Item parameter estimation for a continuous response model using an EM algorithm’, Applied Psychological Measurement 22(4), 333–344.
  * Zhang et al. (2019) Zhang, J., Li, Z., Nai, K., Gu, Y. and Sallam, A. (2019), ‘DELR: A double-level ensemble learning method for unsupervised anomaly detection’, Knowledge-Based Systems 181.
  * Zhang et al. (2009) Zhang, K., Hutter, M. and Jin, H. (2009), A new local distance-based outlier detection approach for scattered real-world data, in ‘Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)’, Vol. 5476 LNAI, pp. 813–822.
  * Zimek et al. (2013) Zimek, A., Gaudet, M., Campello, R. J. and Sander, J. (2013), Subsampling for efficient and effective unsupervised outlier detection ensembles, in ‘Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining’, Vol. Part F128815, pp. 428–436.


#  Multi-CrossRE
A Multi-Lingual Multi-Domain Dataset for Relation Extraction

Elisa Bassignana Filip Ginter[regular] Sampo Pyysalo[regular]
Rob van der Goot Barbara Plank
Department of Computer Science, IT University of Copenhagen, Denmark
[regular]TurkuNLP, Department of Computing, University of Turku, Finland
MaiNLP, Center for Information and Language Processing, LMU Munich, Germany
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Most research in Relation Extraction (RE) involves the English language,
mainly due to the lack of multi-lingual resources. We propose Multi-CrossRE,
the broadest multi-lingual dataset for RE, including 26 languages in addition
to English, and covering six text domains. Multi-CrossRE is a machine
translated version of CrossRE Bassignana and Plank (2022a), with a sub-portion
including more than 200 sentences in seven diverse languages checked by native
speakers. We run a baseline model over the 26 new datasets and—as sanity
check—over the 26 back-translations to English. Results on the back-translated
data are consistent with the ones on the original English CrossRE, indicating
high quality of the translation and the resulting dataset.

##  1 Introduction

Binary Relation Extraction (RE) is a sub-field of Information Extraction
specifically aiming at the extraction of triplets from text describing the
semantic connection between two entities. The task gained a lot of attention
in recent years, and different directions started to be explored. For example,
learning new relation types from just a few instances (few-shot RE; Han et
al., 2018; Gao et al., 2019; Sabo et al., 2021; Popovic and Färber, 2022), or
evaluating the models over multiple source domains (cross-domain RE;
Bassignana and Plank, 2022b; Bassignana and Plank, 2022a). However, a major
issue of RE is that most research so far involves the English language only.

After the very first multi-lingual work from the previous decade—the ACE
dataset Doddington et al. (2004) including English, Arabic and Chinese—recent
work has started again exploring multi-lingual RE. Seganti et al., 2021
published a multi-lingual dataset, built from entity translations and
Wikipedia alignments from the original English version. The latter was
collected from automatic alignment between DBpedia and Wikipedia. The result
includes 14 languages, but with very diverse relation type distributions: Only
English contains instances of all the 36 types, while the most low-resource
Ukrainian contains only 7 of them (including the ‘no_relation’). This setup
makes it hard to directly compare the performance on different languages.
Kassner et al., 2021 translated TREx Elsahar et al. (2018) and
GoogleRE,111https://code.google.com/archive/p/relation-extraction-corpus both
consisting of triplets in the form (object, relation, subject) with the aim of
investigating the knowledge present in pre-trained language models by querying
them via fixed templates. In the field of distantly supervised RE, Köksal and
Özgür, 2020 and Bhartiya et al., 2022 introduce new datasets including
respectively four and three languages in addition to English.

Figure 1: Example sentence with color-coded entity markup. From top to bottom:
The original English text, its translation to German, and translation back to
English. In the first translation step the entity classification is not
transferred to German. In the second translation step the entity machine
learning is (wrongly) expanded by a comma—later corrected in our post-
processing.

In this paper, we propose Multi-CrossRE, to the best of our knowledge the most
diverse RE dataset to date, including 27 languages and six diverse text
domains for each of them. We automatically translated CrossRE Bassignana and
Plank (2022a), a fully manually-annotated multi-domain RE corpus, annotated at
sentence level. We release the baseline results on the proposed dataset and,
as quality check, on the 26 back-translations to English. Additionally, we
report an analysis where native speakers in seven diverse languages manually
check more than 200 translated sentences and the respective entities, on which
the semantic relations are based. Multi-CrossRE allows for the investigation
of sentence-level RE in the 27 languages included in it, and for direct
performance comparison between them. Our contributions are: 1 We propose a
practical approach to machine-translate datasets with span-based annotations
and apply it to produce Multi-CrossRE, the first multi-lingual and multi-
domain dataset for RE including 27 languages and six text
domains.222https://github.com/mainlp/CrossRE 2 Multi-lingual and multi-domain
baselines over the proposed dataset. 3 Comprehensive experiments over the
back-translations to English. 4 A manual analysis by native speakers over more
than 200 sentences in seven diverse languages.

##  2 Multi-CrossRE

### CrossRE

As English base, we use CrossRE Bassignana and Plank (2022a),333Released with
a GNU General Public License v3.0. a recently published multi-domain dataset.
CrossRE is entirely manually-annotated, and includes 17 relation types
spanning over six diverse text domains: artificial intelligence (), literature
(), music (), news (), politics (), natural science (). The dataset was
annotated on top of CrossNER Liu et al. (2021), a Named Entity Recognition
(NER) dataset. Table 1 reports the statistics of CrossRE.

| sentences | relations
---|---|---
| train | dev | test | tot. | train | dev | test | tot.
| 164 | 350 | 400 | 914 | 175 | 300 | 396 | 871
| 101 | 350 | 400 | 851 | 502 | 1,616 | 1,831 | 3,949
| 103 | 351 | 400 | 854 | 355 | 1,340 | 1,393 | 3,088
| 100 | 350 | 399 | 849 | 496 | 1,861 | 2,333 | 4,690
| 100 | 400 | 416 | 916 | 397 | 1,539 | 1,591 | 3,527
| 100 | 350 | 431 | 881 | 350 | 1,006 | 1,127 | 2,483
tot. | 668 | 2,151 | 2,446 | 5,265 | 2,275 | 7,662 | 8,671 | 18,608

Table 1: CrossRE Statistics. Number of sentences and number of relations for
each domain.

### Translation Process

With the recent progress in the quality of machine translation (MT), utilizing
machine-translated datasets in training and evaluation of NLP methods has
become a standard practice Conneau et al. (2018); Kassner et al. (2021). As
long as the annotation is not span-bound, producing a machine-translated
dataset is rather straightforward. The task however becomes more involved for
datasets with annotated spans, such as the named entities in our case of the
CrossRE dataset, or e.g. the answer spans in a typical question answering (QA)
dataset. Numerous methods have been developed for transferring span
information between the source and target texts Chen et al. (2022). These
methods are often tedious and in many cases rely on language-specific
resources to obtain the necessary mapping. Some methods also require access to
the inner state of the MT system, e.g. its attention activations, which is
generally not available when commercial MT systems are used.

|  lang2vec | translation (EN $\rightarrow$ X) |  back-translation (X $\rightarrow$ EN) |  $\Delta_{\textsc{bt}}$ |  $\Delta_{\textsc{or}}$
---|---|---|---|---|---
| eval on back-translated data | eval on original CrossRE data
Language |  |  |  |  |  |  | avg. |  |  |  |  |  |  | avg. |  |  |  |  |  |  | avg.
German | 0.18 | 24.6 | 27.6 | 29.6 | 9.7 | 19.7 | 21.1 | 22.0 | 24.9 | 31.5 | 27.9 | 10.5 | 19.3 | 21.2 | 22.5 | 25.1 | 30.7 | 27.7 | 10.4 | 19.6 | 21.5 | 22.5 | 0.0 | 0.8
Danish | 0.18 | 25.5 | 30.8 | 33.0 | 11.9 | 19.8 | 21.4 | 23.7 | 25.6 | 31.4 | 34.6 | 8.4 | 20.0 | 21.4 | 23.6 | 25.6 | 30.6 | 33.8 | 8.6 | 20.1 | 20.6 | 23.2 | 0.4 | 0.1
Portuguese_BR | 0.18 | 26.2 | 30.7 | 29.2 | 10.7 | 20.0 | 21.2 | 23.0 | 24.9 | 34.7 | 32.1 | 10.1 | 18.2 | 21.5 | 23.6 | 25.3 | 32.5 | 32.5 | 10.1 | 17.9 | 21.4 | 23.3 | 0.3 | 0.0
Portuguese_PT | 0.18 | 28.2 | 32.9 | 31.7 | 10.5 | 20.1 | 22.9 | 24.4 | 24.4 | 34.7 | 28.0 | 10.1 | 19.9 | 21.9 | 23.2 | 25.1 | 34.5 | 28.9 | 10.0 | 19.7 | 22.3 | 23.4 | 0.2 | 0.1
Dutch | 0.19 | 25.8 | 30.9 | 29.3 | 9.7 | 18.5 | 20.7 | 22.5 | 25.0 | 32.1 | 30.3 | 10.5 | 19.9 | 21.6 | 23.2 | 25.7 | 32.2 | 30.3 | 10.7 | 20.4 | 21.8 | 23.5 | 0.3 | 0.2
Ukrainian | 0.21 | 26.7 | 29.1 | 27.5 | 9.0 | 19.4 | 20.4 | 22.0 | 24.8 | 31.4 | 29.9 | 10.4 | 16.1 | 22.5 | 22.5 | 24.6 | 30.9 | 30.5 | 10.8 | 16.2 | 23.3 | 22.7 | 0.2 | 0.6
Swedish | 0.21 | 25.8 | 33.4 | 31.1 | 10.6 | 18.6 | 21.6 | 23.5 | 25.7 | 32.1 | 33.4 | 8.0 | 17.4 | 20.5 | 22.9 | 25.2 | 31.3 | 32.4 | 8.3 | 17.8 | 20.2 | 22.5 | 0.4 | 0.8
Slovenian | 0.22 | 27.0 | 32.3 | 28.1 | 7.9 | 15.0 | 20.1 | 21.7 | 25.3 | 32.4 | 28.4 | 10.5 | 19.8 | 21.1 | 22.9 | 25.1 | 31.3 | 30.2 | 10.1 | 20.0 | 20.2 | 22.8 | 0.1 | 0.5
Italian | 0.22 | 27.1 | 32.5 | 31.3 | 12.8 | 19.1 | 22.3 | 24.2 | 26.3 | 34.6 | 32.0 | 11.3 | 19.9 | 19.7 | 24.0 | 26.7 | 34.3 | 31.5 | 11.3 | 20.2 | 20.0 | 24.0 | 0.0 | 0.7
Romanian | 0.23 | 26.5 | 33.0 | 30.2 | 10.3 | 16.6 | 21.3 | 23.0 | 24.0 | 33.7 | 29.8 | 10.8 | 20.7 | 19.4 | 23.1 | 24.3 | 30.5 | 30.4 | 10.8 | 20.0 | 19.2 | 22.5 | 0.6 | 0.8
Bulgarian | 0.23 | 28.1 | 34.4 | 27.2 | 9.0 | 20.4 | 20.9 | 23.3 | 24.3 | 31.5 | 29.2 | 10.8 | 19.1 | 21.4 | 22.7 | 24.3 | 31.1 | 30.9 | 10.9 | 19.0 | 21.5 | 22.9 | 0.2 | 0.4
French | 0.23 | 29.6 | 33.5 | 32.3 | 11.3 | 19.3 | 23.5 | 24.9 | 25.5 | 33.5 | 31.4 | 11.2 | 19.8 | 21.8 | 23.9 | 25.5 | 32.1 | 31.2 | 10.9 | 20.1 | 21.7 | 23.6 | 0.3 | 0.3
Slovak | 0.23 | 23.1 | 32.7 | 28.2 | 9.2 | 18.6 | 18.2 | 21.7 | 24.4 | 32.6 | 31.6 | 10.2 | 19.2 | 19.8 | 23.0 | 24.1 | 33.6 | 31.7 | 10.3 | 17.8 | 20.1 | 22.9 | 0.1 | 0.4
Indonesian | 0.24 | 26.0 | 34.6 | 33.2 | 9.6 | 19.7 | 20.7 | 24.0 | 25.2 | 32.9 | 32.6 | 9.7 | 16.9 | 20.9 | 23.0 | 26.1 | 32.9 | 32.4 | 9.8 | 16.5 | 20.7 | 23.1 | 0.1 | 0.2
Latvian | 0.25 | 24.8 | 32.3 | 25.0 | 11.0 | 15.9 | 19.1 | 21.4 | 24.3 | 32.6 | 27.6 | 8.7 | 18.8 | 20.5 | 22.1 | 24.4 | 30.9 | 28.7 | 8.5 | 19.1 | 20.5 | 22.0 | 0.1 | 1.3
Spanish | 0.27 | 27.6 | 32.2 | 29.9 | 9.7 | 19.2 | 22.5 | 23.5 | 24.5 | 32.4 | 29.1 | 9.2 | 19.5 | 23.9 | 23.1 | 24.6 | 31.9 | 28.6 | 9.5 | 20.2 | 23.3 | 23.0 | 0.1 | 0.3
Hungarian | 0.27 | 22.4 | 28.9 | 26.0 | 8.5 | 19.2 | 18.4 | 20.6 | 21.2 | 31.0 | 28.5 | 8.6 | 18.5 | 21.2 | 21.5 | 22.2 | 30.2 | 29.1 | 8.5 | 19.3 | 21.3 | 21.8 | 0.3 | 1.5
Greek | 0.27 | 28.3 | 33.3 | 31.8 | 9.1 | 20.3 | 22.7 | 24.2 | 24.1 | 30.7 | 32.9 | 11.2 | 18.6 | 19.8 | 22.9 | 24.7 | 31.9 | 33.6 | 10.9 | 19.2 | 20.8 | 23.5 | 0.6 | 0.2
Estonian | 0.27 | 23.4 | 29.3 | 27.4 | 8.3 | 17.1 | 19.0 | 20.8 | 22.7 | 31.8 | 29.2 | 8.5 | 15.8 | 19.4 | 21.2 | 23.8 | 30.6 | 30.4 | 8.5 | 16.4 | 18.4 | 21.3 | 0.1 | 2.0
Lithuanian | 0.27 | 26.2 | 31.5 | 26.3 | 9.9 | 18.9 | 16.2 | 21.5 | 24.5 | 31.3 | 26.4 | 10.8 | 18.8 | 21.4 | 22.2 | 25.3 | 30.0 | 27.6 | 10.3 | 18.6 | 21.2 | 22.2 | 0.0 | 1.1
Polish | 0.27 | 24.6 | 34.3 | 28.7 | 10.4 | 19.5 | 19.9 | 22.9 | 24.4 | 31.6 | 27.9 | 9.7 | 16.6 | 20.4 | 21.8 | 24.5 | 30.9 | 28.6 | 9.6 | 16.6 | 20.8 | 21.8 | 0.0 | 1.5
Finnish | 0.28 | 22.9 | 30.2 | 24.7 | 8.8 | 17.0 | 18.1 | 20.3 | 21.4 | 29.5 | 27.1 | 8.8 | 17.4 | 20.5 | 20.8 | 24.9 | 34.7 | 32.1 | 10.1 | 18.2 | 21.5 | 23.6 | 2.8 | 0.3
Czech | 0.29 | 25.0 | 30.1 | 28.4 | 10.1 | 19.4 | 18.1 | 21.8 | 23.8 | 30.8 | 29.0 | 9.8 | 20.2 | 19.6 | 22.2 | 24.4 | 31.9 | 29.5 | 9.7 | 19.6 | 20.0 | 22.5 | 0.3 | 0.8
Chinese | 0.30 | 22.2 | 33.4 | 25.0 | 9.0 | 20.1 | 18.7 | 21.4 | 23.1 | 28.4 | 27.1 | 9.5 | 18.9 | 22.0 | 21.5 | 23.8 | 28.7 | 27.4 | 9.9 | 18.7 | 21.3 | 21.6 | 0.1 | 1.7
Turkish | 0.38 | 23.8 | 29.4 | 26.7 | 10.6 | 20.4 | 18.2 | 21.5 | 23.4 | 23.2 | 28.4 | 9.3 | 17.6 | 19.1 | 20.2 | 24.5 | 23.2 | 29.8 | 9.2 | 17.9 | 20.3 | 20.8 | 0.6 | 2.5
Japanese | 0.41 | 22.6 | 29.2 | 20.1 | 8.9 | 19.5 | 12.9 | 18.9 | 21.1 | 27.4 | 21.7 | 8.0 | 16.1 | 15.2 | 18.3 | 20.5 | 27.9 | 23.4 | 8.1 | 16.1 | 16.2 | 18.7 | 0.4 | 4.6

Table 2: Multi-CrossRE Baseline Results. Macro-F1 scores of the baseline model
ordered by increasing lang2vec distance from English. $\Delta_{\textsc{bt}}$:
delta between back-translated and original evaluation when model trained on
back-translated data. $\Delta_{\textsc{or}}$: delta between model trained on
back-translated data and on original CrossRE data when evaluated on original
CrossRE English.

|  |  |  |  |  |  | avg.
---|---|---|---|---|---|---|---
English | 20.8 | 36.4 | 30.7 | 10.1 | 20.0 | 21.6 | 23.3

Table 3: CrossRE Baseline Results. Macro-F1 scores of the RC baseline over the
original CrossRE English dataset.

In this work, we demonstrate a practical and simple approach to the task of
machine translating a span-based dataset. We capitalize on the fact that
DeepL,444https://www.deepl.com/translator a commercial machine translation
service very popular among users thanks to its excellent translation output
quality, is capable of translating document markup. This feature is crucial
for professional translators—the intended users of the service—who need to
translate not only the text of the source documents, but also preserve their
formatting. In practice, this means that the input of DeepL can be a textual
document with formatting (a Word document) and the service produces its
translated version with the formatting preserved.

For the CrossRE dataset, we only need to transfer the named entities, which
can be trivially encoded as colored text spans in the input documents, where
the color differentiates the individual entities. This is further facilitated
by the fact that the entities do not overlap in the dataset, allowing for a
simple one-to-one id-color mapping. Observing that oftentimes the entities are
over-extended by a punctuation symbol during translation, the only post-
processing we apply is to strip from each translated entity any trailing
punctuation not encountered in the suffix of the original named entity. The
process is illustrated in Figure 1, with details about two typical issues with
this approach (later analysed in Section 4).555The overall translation process
cost is $\approx 60$€.

##  3 Experiments

### Model Setup

In order to be able to directly compare our results with the original CrossRE
baselines on English, we follow the model and task setup used by Bassignana
and Plank, 2022a. We perform Relation Classification Han et al. (2018);
Baldini Soares et al. (2019); Gao et al. (2019), which consists of assigning
the correct relation types to the ordered entity pairs which are given as
semantically connected. The model follows the current state-of-the-art
architecture by Baldini Soares et al., 2019 which augments the sentence with
four entity markers $e_{1}^{start}$, $e_{1}^{end}$, $e_{2}^{start}$,
$e_{2}^{end}$ surrounding the two entities. Following Zhong and Chen (2021)
the entity markers are enriched with information about the entity types. The
augmented sentence is then passed through a pre-trained encoder (XLM-R large;
Conneau et al., 2020), and the classification made by a linear layer over the
concatenation of the start markers
$[\hat{s}_{e_{1}^{start}},\hat{s}_{e_{2}^{start}}]$. We run all our
experiments over five random seeds. See Appendix A for reproducibility and
hyperparameters settings.

### Results

The original CrossRE study reports the baseline experiments by using the mono-
lingual BERT Devlin et al. (2019) language encoder. In order to be able to
compare the original baseline with the results on our Multi-CrossRE dataset,
we re-run the English experiments by using the multi-lingual XLM-R large
Conneau et al. (2020) language encoder, and report the results in Table 3.

In Table 2 we report the results of our experiments over Multi-CrossRE. The
left-most columns are the results of the models trained and evaluated over the
translated data (from English to language X). As a sanity check, we back-
translated the data from each of the 26 new languages to English (from
language X to English). We train and evaluate new models on this data in the
middle columns. Finally, on the right-most columns we evaluate the same
models—trained on back-translated data—over the original CrossRE test sets. We
sort the languages by increasing distance to English, computed as the cosine
distance between the syntax, phonology and inventory vectors of lang2vec
Littell et al. (2017).

For our analysis we consider the average of the six domains.666Bassignana and
Plank, 2022a discuss the lower scores of news () attributing them to the data
coming from a different data source and the fewer amount of relation instances
with respect to the other domains. Our scores on the translated data reveal a
relatively small drop in respect to the English baseline in Table 3. The
difference range goes from an improvement of $+1.6$ Macro-F1 points on French,
to a maximum drop of $-4.4$ on Japanese—which has the largest lang2vec
distance with respect to English ($0.41$). The results of the models trained
on the back-translated data present essentially the same trend between
evaluating on the back-translations and on the original CrossRE English
data—with a Pearson’s correlation coefficient of $0.88$—confirming the high
quality of the proposed translation. The only exception if Finnish, with a
difference of $2.8$ points between the two evaluations. All the other
languages report a smaller difference in a range between $0.0$ and $0.6$. The
lang2vec distance is not informative of the quality of the individual
translations (Pearson’s correlation $-0.59$). However, other factors should be
taken into account, e.g. the language model performances on each individual
language.

##  4 Manual Analysis

We performed a manual analysis for further inspecting the quality and
usability of Multi-CrossRE for studying multi-lingual RE. We manually checked
210 sentences from a diverse set of seven languages, including one North
Germanic (Danish), one Uralic (Finnish), one West Slavic (Czech), two Germanic
(German and Dutch), one Latin (Italian), and one Japonic (Japanese). For each
of them, native speakers annotated the following: 1 In how many sentences is
the overall meaning preserved? 2 How many entities are transferred to language
X? 3 How many entities are correctly translated? 4 How many entities are
marked with the correct entity boundaries?

We annotated 30 sentences for each language. Table 4 reports the statistics of
our analysis. Overall, we find a surprisingly high quality of entity
translations (96% are judged as correct by our human annotators). Out of the
seven languages, Japanese is the one suffering the most by the translation
process and, as we discussed above, this is reflected in the lowest scores in
Table 2. Some entities are not transferred. These are mostly due to compounds
typical for some languages. For example, the English snippet “the Nobel
laureate” (where only Nobel is marked as entity), is translated to Danish as
“nobelpristageren”, and to Dutch as “Nobelprijswinnaar”. In Italian, which in
this regard behaves more similarly to English, all the entities are correctly
transferred. In Appendix B we report the total per-language percentages of
transferred entities and relations. Regarding the entity translations and the
entity boundaries, the latter is a bigger challenge for the translation tool,
often including surrounding function words—e.g. the writer Pat Barker in
Danish is extended to the entity Pat Barker er. These could easily be post-
processed, but since the Relation Classification model relies on the injected
entity markers, it is not much influenced by this type of error (see baseline
discussion in Section 3).

Language | Sent. Transl. | # entities | Ent. Transl. | Ent. Bound.
---|---|---|---|---
English | 30 | 160 | - | -
Czech | 28 | 158 | 152 | 143
Danish | 27 | 158 | 143 | 136
Dutch | 28 | 158 | 156 | 141
Finnish | 30 | 150 | 141 | 137
German | 27 | 151 | 148 | 139
Italian | 29 | 160 | 157 | 152
Japanese | 19 | 150 | 145 | 82

Table 4: Statistics of the Manual Analysis. At the top, total amount of
original English sentences and annotated entities within them. Below, for each
sample set, amount of correct instances in the four categories of sentence
translation, number of entities, entity translations, and entity boundaries.

##  5 Conclusion

We introduce Multi-CrossRE, the most diverse RE dataset to date, including 26
languages in addition to the original English, and six text domains. The
proposed span-based MT approach could be easily applied to similar cases. We
report baseline results on the proposed resource and, as quality check, we
back-translate Multi-CrossRE to English and run the baseline model again over
it. Our manual analysis reveals that the higher challenge during the
translation is transferring the correct entity boundaries. However, given the
model architecture, this does not influence the scores.

## Acknowledgments

We thank the MaiNLP/NLPnorth group for feedback on an earlier version of this
paper, and ITU’s High-performance Computing cluster for computing resources.

EB and BP are supported by the Independent Research Fund Denmark (Danmarks
Frie Forskningsfond; DFF) Sapere Aude grant 9063-00077B. BP is supported by
the ERC Consolidator Grant DIALECT 101043235. FG and SP were supported by the
Academy of Finland.

## References

  * Baldini Soares et al. (2019) Livio Baldini Soares, Nicholas FitzGerald, Jeffrey Ling, and Tom Kwiatkowski. 2019\.  Matching the blanks: Distributional similarity for relation learning.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 2895–2905, Florence, Italy. Association for Computational Linguistics.
  * Bassignana and Plank (2022a) Elisa Bassignana and Barbara Plank. 2022a.  CrossRE: A cross-domain dataset for relation extraction.  In _Findings of the Association for Computational Linguistics: EMNLP 2022_ , pages 3592–3604, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
  * Bassignana and Plank (2022b) Elisa Bassignana and Barbara Plank. 2022b.  What do you mean by relation extraction? a survey on datasets and study on scientific relation classification.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics: Student Research Workshop_ , pages 67–83, Dublin, Ireland. Association for Computational Linguistics.
  * Bhartiya et al. (2022) Abhyuday Bhartiya, Kartikeya Badola, and Mausam . 2022.  DiS-ReX: A multilingual dataset for distantly supervised relation extraction.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 849–863, Dublin, Ireland. Association for Computational Linguistics.
  * Chen et al. (2022) Yang Chen, Chao Jiang, Alan Ritter, and Wei Xu. 2022.  Frustratingly easy label projection for cross-lingual transfer.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Conneau et al. (2018) Alexis Conneau, Ruty Rinott, Guillaume Lample, Adina Williams, Samuel Bowman, Holger Schwenk, and Veselin Stoyanov. 2018.  XNLI: Evaluating cross-lingual sentence representations.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 2475–2485, Brussels, Belgium. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * Doddington et al. (2004) George Doddington, Alexis Mitchell, Mark Przybocki, Lance Ramshaw, Stephanie Strassel, and Ralph Weischedel. 2004.  The automatic content extraction (ACE) program – tasks, data, and evaluation.  In _Proceedings of the Fourth International Conference on Language Resources and Evaluation (LREC’04)_ , Lisbon, Portugal. European Language Resources Association (ELRA).
  * Elsahar et al. (2018) Hady Elsahar, Pavlos Vougiouklis, Arslen Remaci, Christophe Gravier, Jonathon Hare, Frederique Laforest, and Elena Simperl. 2018.  T-REx: A large scale alignment of natural language with knowledge base triples.  In _Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018)_ , Miyazaki, Japan. European Language Resources Association (ELRA).
  * Gao et al. (2019) Tianyu Gao, Xu Han, Hao Zhu, Zhiyuan Liu, Peng Li, Maosong Sun, and Jie Zhou. 2019\.  FewRel 2.0: Towards more challenging few-shot relation classification.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6250–6255, Hong Kong, China. Association for Computational Linguistics.
  * Han et al. (2018) Xu Han, Hao Zhu, Pengfei Yu, Ziyun Wang, Yuan Yao, Zhiyuan Liu, and Maosong Sun. 2018.  FewRel: A large-scale supervised few-shot relation classification dataset with state-of-the-art evaluation.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 4803–4809, Brussels, Belgium. Association for Computational Linguistics.
  * Kassner et al. (2021) Nora Kassner, Philipp Dufter, and Hinrich Schütze. 2021.  Multilingual LAMA: Investigating knowledge in multilingual pretrained language models.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 3250–3258, Online. Association for Computational Linguistics.
  * Köksal and Özgür (2020) Abdullatif Köksal and Arzucan Özgür. 2020.  The RELX dataset and matching the multilingual blanks for cross-lingual relation classification.  In _Findings of the Association for Computational Linguistics: EMNLP 2020_ , pages 340–350, Online. Association for Computational Linguistics.
  * Littell et al. (2017) Patrick Littell, David R. Mortensen, Ke Lin, Katherine Kairis, Carlisle Turner, and Lori Levin. 2017.  URIEL and lang2vec: Representing languages as typological, geographical, and phylogenetic vectors.  In _Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers_ , pages 8–14, Valencia, Spain. Association for Computational Linguistics.
  * Liu et al. (2021) Zihan Liu, Yan Xu, Tiezheng Yu, Wenliang Dai, Ziwei Ji, Samuel Cahyawijaya, Andrea Madotto, and Pascale Fung. 2021.  Crossner: Evaluating cross-domain named entity recognition.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 35(15):13452–13460.
  * Popovic and Färber (2022) Nicholas Popovic and Michael Färber. 2022.  Few-shot document-level relation extraction.  In _Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 5733–5746, Seattle, United States. Association for Computational Linguistics.
  * Sabo et al. (2021) Ofer Sabo, Yanai Elazar, Yoav Goldberg, and Ido Dagan. 2021.  Revisiting few-shot relation classification: Evaluation data and classification schemes.  _Transactions of the Association for Computational Linguistics_ , 9:691–706.
  * Seganti et al. (2021) Alessandro Seganti, Klaudia Firlag, Helena Skowronska, Michał Satława, and Piotr Andruszkiewicz. 2021.  Multilingual entity and relation extraction dataset and model.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 1946–1955, Online. Association for Computational Linguistics.
  * Zhong and Chen (2021) Zexuan Zhong and Danqi Chen. 2021.  A frustratingly easy approach for entity and relation extraction.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 50–61, Online. Association for Computational Linguistics.

## Appendix

##  Appendix A Reproducibility

We report in Table 5 the hyperparameter setting of our RC model (see Section
3). All experiments were ran on an NVIDIA® A100 SXM4 40 GB GPU and an AMD
EPYC™ 7662 64-Core CPU.

Parameter | Value
---|---
Encoder | xlm-roberta-large
Classifier | 1-layer FFNN
Loss | Cross Entropy
Optimizer | Adam optimizer
Learning rate | $2e^{-5}$
Batch size | 32
Seeds | 4012, 5096, 8878, 8857, 9908

Table 5: Hyperparameters Setting. Model details for reproducibility of the
baseline.

##  Appendix B Per-language Analysis

In table 6 we report the percentages of entities which are transferred during
the translation process from the original English to language X, and the
percentage of relations which do not involve missing entities (i.e. are
transferred during the translation process).

Language | % Entities | % Relations
---|---|---
German | 96.7 | 91.4
Danish | 97.5 | 93.9
Portuguese_BR | 99.8 | 99.5
Portuguese_PT | 99.8 | 99.6
Dutch | 98.5 | 95.8
Ukrainian | 99.1 | 97.7
Swedish | 97.6 | 94.1
Slovenian | 99.1 | 98.0
Italian | 99.8 | 99.5
Romanian | 98.8 | 96.7
Bulgarian | 99.5 | 98.9
French | 99.6 | 99.4
Slovak | 99.2 | 98.1
Indonesian | 99.8 | 99.5
Latvian | 99.4 | 98.6
Spanish | 99.3 | 98.3
Hungarian | 98.2 | 95.8
Greek | 98.8 | 98.0
Estonian | 97.9 | 94.6
Lithuanian | 99.4 | 98.8
Polish | 99.4 | 98.6
Finnish | 96.0 | 90.7
Czech | 99.0 | 98.0
Chinese | 99.3 | 98.4
Turkish | 99.4 | 98.5
Japanese | 94.9 | 88.9

Table 6: Transferred Entities and Relations. Percentages of entities and of
relations transferred during the translation process for each language.