*[inlinelist,1]label=(), *[inlinelistbullet,1]label=$\bullet$,

10(2,2) 18th Int. Conf. on Acc. and Large Exp. Physics Control Systems
ISBN: 978-3-95450-221-9 ISSN: 2226-0358  10(11.4,2) ICALEPCS2021, Shanghai,
China JACoW Publishing
doi:10.18429/JACoW-ICALEPCS2021-WEPV042

# Applying model checking to highly-configurable safety critical software: the
SPS-PPS PLC program

B. Fernández<EMAIL_ADDRESS>I. D. Lopez-Miguel  J-C. Tournier
E. Blanco
T. Ladzinski  F. Havart  CERN  Geneva  Switzerland

###### Abstract

An important aspect of many particle accelerators is the constant evolution
and frequent configuration changes that are needed to perform the experiments
they are designed for.

This often leads to the design of configurable software that can absorb these
changes and perform the required control and protection actions. This design
strategy minimizes the engineering and maintenance costs, but it makes the
software verification activities more challenging since safety properties must
be guaranteed for any of the possible configurations.

Software model checking is a popular automated verification technique in many
industries. This verification method explores all possible combinations of the
system model to guarantee its compliance with certain properties or
specification. This is a very appropriate technique for highly configurable
software, since there is usually an enormous amount of combinations to be
checked.

This paper presents how PLCverif, a CERN model checking platform, has been
applied to a highly configurable Programmable Logic Controller (PLC) program,
the SPS Personnel Protection System (PPS). The benefits and challenges of this
verification approach are also discussed.

##  1 Introduction

Model checking is a popular verification technique that has been applied in
many industries to guarantee that a critical system meets the specifications.
Model checking algorithms explore all possible combinations of a system model,
trying to find a violation of the formalized specification in the model. This
technique is very appropriate for highly configurable projects, since it is
necessary to guarantee the safety of the system for all possible
configurations.

When model checking shows a discrepancy between the PLC program and the
specification, it means that either the PLC program has a bug or the
specification is incomplete or incorrect.

In the domain of critical PLC programs, several researchers and engineers
published their experiences in the field. To name but a few, in
[Pavlovic:ICST2010] the authors translate the PLC program of an interlocking
railway system, written in the FBD (Function Block Diagrams) language, into
the input format language of NuSMV to verify their specification written as
CTL (Computation Tree Logic) properties. In [Moreira:MSc], the PLC program
that controls the doors’ opening and closing in the trains from the Metro in
Brasília, Brazil, was formally verified. In this case, a B model
[Abrial:Bbook] is created automatically from the PLC code. This model is
formally verified using the model checker ProB [Leuschel:FME03].

When applying model checking to PLC programs, three main challenges are faced:
(1) building the mathematical model of the program, (2) formalizing the
requirements to be checked and (3) the state-space explosion, i.e. the number
of possible input combinations and execution traces is too big to be
exhaustively explored. In our case, we use the open-source tool
PLCverif[BlancoViñuela:2777799], developed at CERN. It creates automatically
the models out of the PLC program and integrates three state-of-the-art model
checkers: nuXmv [Cavada:CAV2014], Theta [Toth:FMCAD2017] and CBMC
[Clarke:TACAS2004]. It also implements some reduction and abstraction
mechanisms to reduce the number of states to be explored and to speed up the
verification. Therefore, challenges 1 and 3 are transparent for the user.
There are certainly still limitations and large state-space PLC program models
cannot be verified. Regarding challenge 2, PLCverif also provides mechanisms
to help the users to formalize their requirements and provide a precise
specification. However, this is normally a difficult task, specially for
configurable programs. In this paper, we will show examples of functional
requirements formalization with PLCverif. More details about PLCverif can be
found in [Lopez:ICALEPCS2021, BlancoViñuela:2777799].

This paper aims to show the benefits of applying model checking to verify
highly configurable PLC programs. In such systems, it is usually unfeasible to
check all possible combinations by traditional testing methods and model
checking is a good complement to these methods, especially for module
verification.

In particular, this paper shows how PLCverif was applied to the PLC programs
of the SPS Personnel Protection System (PPS) [Ladzinski:ICALEPCS2019] and how
it helped to improve their original specification and correct PLC bugs before
the commissioning of the system.

##  2 SPS Personnel Protection System

The SPS-PPS is a large distributed control system in charge of the access
control and the personnel protection of the SPS accelerator.

The SPS has 16 access zones divided in different sectors and each access zone
has an access point. Several access zones are always interlocked with the same
elements inhibiting operation with beam when a hazardous event is detected.
This is the concept of a safety chain. Each safety chain contains the
"important safety elements" to stop the beam (EISb) when a hazardous event is
detected or to avoid access (EISa) when the accelerator is in Beam mode.

All details of the system can be found in [Ladzinski:ICALEPCS2019].

The SPS evolves with time as new access zones are added or existing ones
modified. For that reason, a configurable system was designed.

###  2.1 Hardware architecture

The SPS-PPS safety-interlock part is based on Siemens S7-1500F series of PLC
controllers. It is formed by the following 3 layers as shown in Figure 1:

The central layer is composed by the Global Interlock (GI) PLC. This PLC
receives the information of all the Site PLCs and computes, for example, the
conditions to allow Beam or Access modes to each safety chain and the
conditions to apply veto to all the EISa and EISb associated to the safety
chain.

The site layer is composed by 16 Site PLCs (1 PLC per access zone). These PLCs
monitor the EISa devices (doors, emergency handles, etc.), receive the status
from the AP PLCs, perform some automatic control procedures (e.g. patrol
management) and apply the safety interlock actions (e.g. stop the beam) with
the commands received from the GI PLC for each access zone.

The equipment layer is composed by 16 Access Point (AP) PLCs (1 PLC per access
point). They monitor and control the PAD (Personnel Access Device) and the MAD
(Material Access Device) of the access point.

Site 1Site 2Site 16Central layerSite layerGIEquipment layerAP 1AP 2AP 16

Figure 1: Simplified SPS-PPS PLC interlock architecture

###  2.2 Software architecture

All Site PLCs run the same generic PLC program, a common logic for all of them
with a specific configuration for each access zone. The logic is composed by a
set of Functions (FC) and Function Blocks (FBs) executed sequentially from a
cyclic interrupt every 300 ms. Each access zone has a different configuration,
indicating for example how many EISa and EISb are installed in each of them,
in which sector they are located and to which safety chain they belong.

A similar approach is in place for the AP PLCs.

The GI PLC contains less configurable parameters since it communicates with
all Site PLCs, having a global view of the system.

###  2.3 Software modules specification

The different program modules (FC and FBs) are specified in a detailed design
document. It contains 106 formulas that describe the requirements for the 29
FC and FBs.

The chosen formalism for the specification is a simple if-else conditional
statement that contains Boolean formulas, as shown in the example
specification 1. The goal was to have a simple pseudo-formal specification
providing precise and unambiguous requirements for each module of the system.

Specification 1 Template for specifying protection actions of the Safety
program

if (Boolean expression condition) then

$result\leftarrow 0$

else if (Boolean expression condition 2) then

$result\leftarrow 1$

else

$result\leftarrow result$

end if

##  3 Modules verification with PLCverif

PLCverif was the tool to apply model checking to the SPS-PPS modules (FC and
FBs). All the necessary model transformations to create the formal model of
the PLC program are done automatically. The user only needs to provide the
exported PLC program from the programming environment tool, Siemens TIA
Portal111https://new.siemens.com/global/en/products/automation/industry-
software/automation-software/tia-portal/software.html, import it into PLCverif
and finally formalize the requirements to be verified.

OpennessScripterSatisfiedViolatedTIA Portal - FBDXML -
FBDPLCverifSpecificationFormalized spec.Instruction ListnuXmvCBMCThetaUser

Figure 2: PLCverif workflow to verify TIA portal Safety programs

Figure 2 shows the workflow to verify a FC or FB from a TIA Portal safety PLC
project with PLCverif:

  1. 1.

The project is hosted in TIA Portal and the PLC program is written in the FBD
(Function Block Diagram) programming language. An example of how this language
looks like is shown in Figure 3. Here an AND gate and an OR gate are
displayed.

  2. 2.

Taking advantage of the Siemens OpennessScripter
tool222https://support.industry.siemens.com/cs/us/en/view/109742322, the
program is exported to XML (F_FBD XML format). An example of how an AND gate
is represented in this language is shown in listing 1.

  3. 3.

PLCverif can then import that XML code, translating it into STL code, which
can be understood by PLCverif. Subsequently, it creates the formal models.

  4. 4.

From the specification created by the process engineers, the user needs to
formalize the requirements, such as the assertion shown in Listing 2. This can
be direct input to PLCverif.

  5. 5.

Finally, PLCverif executes one of the model checking backends and generates a
report, stating whether the property is satisfied or violated. In case it is
violated, it shows the trace leading to that property failure (the
counterexample).

var1var2tmp1IN1IN2OUTANDINOUTNOTtmpnvarnresultIN1IN2OUTOR

Figure 3: FBD program example Listing 1: XML code exported from TIA portal
representing an AND gate

⬇

<!-- Input variables \-->

<Access Scope="LocalVariable" UId="21">

<Symbol>

<Component Name="var1"/>

</Symbol>

</Access>

<Access Scope="LocalVariable" UId="22">

<Symbol>

<Component Name="var2"/>

</Symbol>

</Access>

<!-- AND block \-->

<Part Name="And" UId="97">

<TemplateValue Name="Card" Type="Cardinality">2</TemplateValue>

<TemplateValue Name="SrcType" Type="Type">Word</TemplateValue>

</Part>

<!-- Connecting the inputs with the block \-->

<Wire UId="134">

<IdentCon UId="21" />

<NameCon UId="97" Name="in1" />

</Wire>

<Wire UId="135">

<IdentCon UId="22" />

<NameCon UId="97" Name="in2" />

</Wire>

<!-- Output variable \-->

<Wire UId="136">

<NameCon UId="97" Name="out" />

<IdentCon UId="23" />

</Wire>

Listing 2: Example of a PLCverif assertion

⬇

//#ASSERT (var1 AND var2) = result;

##  4 Verification results and analysis

Although various safety functions were verified during this project, due to
space limitations for this paper, only two of them will be shown here: the
SIF-X1 Function from the Site PLCs and the SIF-2 Function from the GI PLC.
Each of these PLC Functions implements several requirements of a similar
nature and each of these requirements was verified with PLCverif by including
an assertion which represents the mathematical Boolean formula given for that
requirement. After executing a verification case with PLCverif, the following
outcomes can occur:

  * •

Satisfied property. It will be shown in example 1 from SIF-X1.

  * •

Violated property. The reasons why this happens need to be further
investigated, leading to the following two possibilities:

    * –

Incomplete specification. Example 2 from SIF-2.

    * –

Bug in the program. Example 3 from SIF-2.

###  4.1 SIF-X1 Function

This function is in charge of monitoring all the EISa of the access zone and
computing the status (safe or unsafe) for each safety chain.

####  4.1.1 Example 1 - Satisfied property.

The selected requirement for this use case is the following: For each Safety
Chain, this Function monitors all the EISa that are installed in the access
zone and belong to the Safety Chain. It also receives the status from its
access point (PAD, MAD and token distributor status). If all these elements
are in a safe state, it returns a Boolean variable indicating that the Safety
Chain is safe.

The formalized requirement is shown in specification 2, where

$i$ is the EISa index,

$j$ is the safety chain index,

$N_{i}$ is the number of EISa assigned to the safety chain $j$ (the maximum
number of EISa per access zone is 32),

$I\\_EISa\\_Pos[i]\\_Stat$ represents the status of the EISa $i$: true if $i$
is closed,

$I\\_EISa\\_PU[i]\\_Stat$ represents the status of the emergency handle of the
EISa $i$: true if the emergency handle is armed, $I\\_EISa\\_Pos[i]$ is a
configuration variable: true if the EISa $i$ is installed in the access zone,

$I\\_EISa\\_PU[i]$ is configuration variable: true if the EISa $i$ has an
emergency handle,

$SC-S{j}[i]$ is configuration variable: true if the EISa $i$ belongs to the
Safety Chain $j$,

$S0\\_AP\\_Pos[j]$, $S0\\_AP\\_PU[j]$ and $S0\\_AP\\_Key\\_Distrib[j]$
represent the status of the access point: true if the access point is closed,
the emergency handle is armed and the token distributor is safe respectively,

$N\\_EISa\\_Safe[j]$ is the output variable of the Function and represents the
status of the safety chain $j$: true if $j$ is safe.

Specification 2 Partial, simplified requirement of SIF-X1

if (

$\displaystyle\prod_{i=1}^{N_{i}}\displaystyle\big{(}I\\_EISa\\_Pos\\_Stat[i]\
\vee\ I\\_EISa\\_Bypass[i]\big{)}$

$\scriptstyle\forall i\in[1,N_{i}]:(I\\_EISa\\_Pos[i]=1\ \wedge\
SC-S\\{j\\}[i]=1$

$\displaystyle\wedge$

$\displaystyle\prod_{i=1}^{N_{i}}\displaystyle\big{(}I\\_EISa\\_PU\\_Stat[i]\
\vee\ I\\_EISa\\_Bypass[i]\big{)}$

$\scriptstyle\forall i\in[1,N_{i}]:(I\\_EISa\\_PU[i]=1\ \wedge\
SC-S\\{j\\}[i]=1$

$\displaystyle\wedge$

$\displaystyle S0\\_AP\\_Pos[j]$ $\displaystyle\wedge$ $\displaystyle
S0\\_AP\\_PU[j]$ $\displaystyle\wedge$ $\displaystyle
S0\\_AP\\_Key\\_Distrib[j]$

) then

$\displaystyle N\\_EISa\\_Safe[j]\leftarrow 1$

else

$\displaystyle N\\_EISa\\_Safe[j]\leftarrow 0$

end if

The behaviour of this relatively complex specification is shown in Table 1
with an example. Here, 2 doors (EISa) are installed in this access zone
(indexes 1 and 4 of $EISa\\_Pos[i]$), only one of them has an emergency handle
(index 1 of $EISa\\_PU[i]$). One of the EISa belongs to the Safety Chain 0
(index 1 of $SC-S\\_0[i]$) and the other one to the Safety Chain 1 (index 4 of
$SC-S\\_1[i]$). For each safety chain $j$, the resultant $N\\_EISa\\_Safe[j]$
is true if the installed doors and emergency handles are in the safe state
($EISa\\_Pos\\_Stat[i]$ and $EISa\\_PU\\_Stat[i]$).

Table 1: SIF-X1 expected behaviour Source | Variable | Value
---|---|---
Input | $EISa\\_Pos\\_Stat$ | 0000 0000 0000 1001
Input | $EISa\\_PU\\_Stat$ | 0000 0000 0000 0001
… | … | …
Input (AP PLC) | $S0\\_AP\\_Pos$ | 0000 0000 0000 1001
… | … | …
Configuration | $EISa\\_Pos$ | 0000 0000 0000 1001
Configuration | $EISa\\_PU$ | 0000 0000 0000 0001
… | … | …
Configuration | $SC-S\\_0$ | 0000 0000 0000 0001
Configuration | $SC-S\\_1$ | 0000 0000 0000 1000
… | … | …
Output | $N\\_EISa\\_Safe$ | 0000 0000 0000 1001

The specification was translated into 16 verification cases (one per safety
chain), in order to guarantee that this property is respected in all safety
chains for all possible combinations of the input and configuration variables.
The example for the safety chain 0 can be seen in listing 3 (simplified
assertion).

The corresponding PLC program has 94 WORD (16-bit variable) and 4 BOOL
configuration variables, and 21 WORD and 2 BOOL input variables to implement
all the requirements. This implies approximately
$2^{16\cdot(94+21)+6}=2^{1846}\approx 5.0\cdot 10^{555}$ combinations to be
checked. The equivalent STL code of the original F-FBD version is around 700
lines of code.

PLCverif was able to validate the 16 verification cases in 41 seconds. The
result of all properties (assertions) was satisfied. This means that no
counterexamples were found and, hence, the properties always hold true.

Listing 3: SIF-X1 formalized requirement for PLCverif.

⬇

//#ASSERT

(((I_EISa_Pos_Stat OR I_EISa_Bypass) AND

(SC-S_0 AND I_EISa_Pos))

= (SC-S_0 OR I_EISa_Pos)) AND

(((I_EISa_PU_Stat OR I_EISa_Bypass) AND

(SC-S_0 AND I_EISa_PU))

= (SC-S_0 OR I_EISa_PU)) AND

(S0_AP_Key_Distrib.%X0 AND

S0_AP_PU.%X0 AND S0_AP_Pos.%X0)

= N_EISa_Safe.%X0

###  4.2 SIF-2 Function

The following two examples belong to the verification of the SIF-2 Function.
In this function, PLCverif was able to find several discrepancies between the
PLC program and the specification and two of them are presented here.

This function contains the transitions rules between the Beam and Access modes
for each safety chain $j$. In order to allow the transition between modes, the
function checks the status of the safety chain (computed variable calculated
by another GI PLC function) and the requests from the operator, via the OKP
(Operator Key Panel). When all safety conditions are met, this function
authorizes the change of mode. The function also contains the conditions to
lock or release the keys from the OKP.

The implementation of the SIF-2 Function Block has 19 WORD and 1 BOOL input
variables to implement all the requirements. This implies approximately
$2^{19\cdot 16+1}=2^{305}\approx 6.5\cdot 10^{91}$ combinations to be checked.

The equivalent STL code of the original F-FBD version is around 1200 lines of
code.

####  4.2.1 Example 2 - Incomplete specification.

This specification was related to the conditions to switch to Beam mode. The
property was formalized with the assertion shown in listing 4:

Listing 4: SIF-2 Beam mode activation formalized requirement for PLCverif

⬇

//#ASSERT

((NOT((N_EXT_ACCE_OK AND N_NO-SAFETY_ERR) AND

((I_PB_TEST_ON AND I_Key_TEST) OR

(I_PB_Acce_ON AND I_Key_Acce)))

OR (NOT N_MODE_BEAM)) = 16#FFFF)

This assertion was verified with PLCverif in 93 seconds and a counterexample
was found, meaning that the property was violated. The reason for this
violation was a missing variable in the formula from the documentation.

####  4.2.2 Example 3 - Bug in the PLC program.

In this case, the conditions to release an access key from the OKP for one of
the safety chains were used as specification. The formalized assertion was the
one shown in listing 5:

Listing 5: SIF-2 extractors access key release formalized requirement for
PLCverif

⬇

//#ASSERT

((N_SECU_NO-REQ_Down.%X15 AND N_EXT_BEAM_OK.%X15)

= (SIF-2_TAGS.O_RLS_ACCESS.%X15))

PLCverif was able to verify this assertion in 147 seconds. The result was not
satisfied and a counterexample was provided. After analysing the
counterexample and discussing with the SPS-PPS experts, it was concluded that
there was a problem in the PLC program. The program was modified accordingly
to include the missing variables before the commissioning of the system.

###  4.3 Analysis

PLCverif hides most of the complexity of applying model checking to PLC
programs. Nevertheless, a few manual steps were still needed in this project.
In particular to import the program in PLCverif and to create the formal
properties from the pseudo-formalized specification.

We also encounter the state-space explosion problem in other functions, where
the number of configurations and input variables was much bigger.

Overall, PLCverif helped to validate a few critical functions from the SPS-PPS
PLC program and it was a good complement to the testing activities performed
in the lab by the access control experts at CERN (e.g. the SIF-X1 function).

PLCverif was able to find discrepancies between some of the specifications and
the PLC program before the commissioning of the system, sometimes due to an
incomplete or erroneous specification, other times due to a bug in the program
(e.g. the SIF-2 function). Due to the complexity of some of the
specifications, it was sometimes very hard for experts to validate the desired
behaviour. By using model checking, the experts were able to find undesirable
corner cases, helping them to understand the behaviour of the system and
modifying the specification when necessary.

##  5 Conclusions

This paper presented a highly configurable PLC program and the benefits and
challenges of applying model checking to verify it. In general, we can
conclude that model checking contributed to this project to (1) detect bugs in
the PLC program before the commissioning, (2) identify deficiencies in the
specification, and (3) help experts to better understand the behaviour of the
program for all possible configurations.

There are still several challenges to overcome for model checking to become a
common practice in the industrial automation domain. Probably the more
important ones are: (1) the integration of model checking in PLC programming
environments (e.g. TIA portal) to minimize the number of manual steps and (2)
the improvement of verification performance with better algorithms and
abstraction techniques.

In the context of the PLCverif project, the future work will focus on the
following directions: (1) improve PLCverif to reduce the verification time,
(2) support more PLC manufacturers – we are currently working on supporting
Schneider ST and IL programs. More information about the current and future
work of PLCverif can be found in [Lopez:ICALEPCS2021].


###### Abstract

Machine learning has been proven to be effective in various application areas,
such as object and speech recognition on mobile systems. Since a critical key
to machine learning success is the availability of large training data, many
datasets are being disclosed and published online. From a data consumer or
manager point of view, measuring data quality is an important first step in
the learning process. We need to determine which datasets to use, update, and
maintain. However, not many practical ways to measure data quality are
available today, especially when it comes to large-scale high-dimensional
data, such as images and videos. This paper proposes two data quality measures
that can compute class separability and in-class variability, the two
important aspects of data quality, for a given dataset. Classical data quality
measures tend to focus only on class separability; however, we suggest that
in-class variability is another important data quality factor. We provide
efficient algorithms to compute our quality measures based on random
projections and bootstrapping with statistical benefits on large-scale high-
dimensional data. In experiments, we show that our measures are compatible
with classical measures on small-scale data and can be computed much more
efficiently on large-scale high-dimensional datasets.

###### keywords:

data quality; large-scale; high-dimensionality; linear discriminant analysis;
random projection; bootstrapping

1 1 0 31 October 2020 4 January 2021 https://doi.org/ Data Quality Measures
and Efficient Evaluation Algorithms for Large-Scale High-Dimensional DataData
Quality Measures and Efficient Evaluation Algorithms for Large-Scale High-
Dimensional Data Hyeongmin Cho 1 and Sangkyun Lee 1,* Hyeongmin Cho and
Sangkyun Lee Cho, H.; Lee, S. Correspondence<EMAIL_ADDRESS>
##  1 Introduction

We are witnessing the success of machine learning in various research and
application areas, such as vision inspection, energy consumption estimation,
and autonomous driving, just to name a few. One major contributor to the
success is the fact that the datasets are continuously accumulated and openly
published in several domains. Low data quality is very likely to cause
inferior prediction performance of machine learning models, and therefore
measuring data quality is an indispensable step in a machine learning process.
Especially in real-time and mission-critical cyber-physical-system, defining
appropriate data quality measures is critical since the low generalization
performance of a deployed model can result in system malfunction and possibly
catastrophic damages to the physical world. Despite the importance, there
exist only a few works for measuring data quality where most of them are hard
to evaluate on large-scale high-dimensional data due to computation
complexity.

A popular early work on data quality measures includes Ho and Basu (2002),
proposing 12 types of quality measures which are simple but powerful enough to
address different aspects of data quality. These measures have limitations,
however, in that it is difficult to compute them for large-scale high-
dimensional and multi-class datasets. Baumgartner and Somorjai (2006) proposed
a quality measure designed for high-dimensional biomedical datasets; however,
it does not work efficiently on large-scale data. Recently, Branchaud-Charron
et al. Branchaud-Charron et al. (2019) proposed a quality measure for high-
dimensional data using spectral clustering. Although this measure is adequate
for large-scale high-dimensional data, it requires an embedding network which
involves a large amount of computation time for training.

In this paper, we propose three new quality measures called $M_{sep}$,
$M_{var}$, and $M_{var_{i}}$, and their computation methods that overcome the
above limitations. Our approach is inspired by Fisher’s linear discriminant
analysis (LDA) Hancock et al. (2014), which is mathematically well-defined for
finding a feature subspace that maximizes class separability. Our computation
method makes use of the techniques from statistics, random projection Bingham
and Mannila (2001) and bootstrapping Efron (1979), to compute the measure for
large-scale high-dimensional data efficiently.

The contributions of our paper are summarized as follows:

  * •

We propose three new data quality measures that can be compuated directly from
a given dataset and can be compared across datasets with different numbers of
classes, examples, and features. Although our approach takes ideas from LDA
(linear discriminant analysis) and PCA (principal component analysis), the
techniques by themselves do not produce single numbers that are comparable
across different datasets.

  * •

We provide efficient algorithms to approximate the suggested data quality
measures, making them available for large-scale high-dimensional data.

  * •

The proposed class separability measure $M_{sep}$ is strongly correlated with
the actual classification performance of linear and non-linear classifiers in
our experiments.

  * •

The proposed in-class variability measures $M_{var}$ and $M_{var_{i}}$
quantify the diversity of data within each class and can be used to analyze
redundancy or outlier issues.

##  2 Related Work

In general, the quality of data can be measured by Kolmogorov complexity which
is also known as the descriptive complexity for algorithmic entropy Li and
Vitányi (2008). However, the Kolmogorov complexity is not computationally
feasible; instead, an approximation is used in practice. To our knowledge,
there are three main approaches for approximating the Kolmogorov complexity:
descriptor-based, classifier-based, and graph-based approaches. We describe
these three main categories below.

###  2.1 Descriptor-Based Approaches

Ho and Basu (2002) proposed simple but powerful quality measures based on
descriptors. They proposed 12 quality measures, namely $F1$, $F2$, $F3$, $L1$,
$L2$, $L3$, $N1$, $N2$, $N3$, $N4$, $T1$, and $T2$. The $F$ measures represent
the amount of feature overlap. In particular, $F1$ measures the maximum
Fisher’s ratio which represents the maximum discriminant power of between
features. $F2$ represents the volume of overlap region in the two-class
conditional distributions. $F3$ captures the ratio of overlapping features
using the maximum and minimum value. The $L$ measures are for the linear
separability of classes. $L1$ is a minimum error of linear programming (LP),
$L2$ is an error rate of a linear classifier by LP, and $L3$ is an error rate
of linear classifier after feature interpolation. The $N$ measures represent
mixture identifiability, the distinguishability of the data points belonging
to two different classes. $N1$ represents the ratio of nodes connected to the
different classes using the minimum spanning tree of all data points. $N2$ is
the ratio of the average intra-class distance and average inter-class
distance. $N3$ is the leave-one-out error rate of the nearest neighbor (1NN).
$N4$ is an error rate of 1NN after feature interpolation. The $T$ measure
represents the topological characteristic of a dataset. $T1$ represents the
number of hyperspheres adjacent to other class features. $T2$ is the average
number of data points per dimension. These quality measures can capture
various aspects of data quality; however, they are fixed for binary
classification and not applicable for multi-class problems. Furthermore,
quality measures, such as $N1$, $N2$, and $N3$, require a large amount of
computation time on large-scale high-dimensional data.

Baumgartner and Somorjai (2006) proposed a quality measure for high-
dimensional but small biomedical datasets. They used singular value
decomposition (SVD) with time complexity $\mathcal{O}(min(m^{2}n,mn^{2}))$,
where $m$ is the number of data points, and $n$ is the number of features.
Thus, it is computationally demanding to calculate their measures for the
datasets with large $m$ and $n$, such as recent image datasets.

There are other descriptor-based approaches, for example for meta learning
Leyva et al. (2015); Sotoca et al. (2006), for classifier recommendation
Garcia et al. (2018), and for synthetic data generation de Melo and Lorena
(2018). However, only a small number of data points in a low dimensional space
have been considered in these works.

###  2.2 Graph-Based Approaches

Branchaud-Charron et al. Branchaud-Charron et al. (2019) proposed a graph-
based quality measure using spectral clustering. First, they compute a
probabilistic divergence-based $K\times K$ class similarity matrix $S$, where
$K$ is the number of classes. Then, an adjacency matrix $W$ is computed from
the $S$ matrix. The quality measure is defined as a cumulative sum of the
eigenvalues gap which is called as cumulative spectral gradient ($CSG$), which
represents the minimum cutting cost of the $S$. The authors also used a
convolutional neural network-based auto-encoder and t-SNE Masci et al. (2011);
van der Maaten and Hinton (2008) to find an embedding that can represent data
points (images in their case) well. Although the method is designed for high-
dimensional data, it requires to train a good embedding network to reach
quality performance.

Duin and Pękalska (2006) proposed a quality measure based on a dissimilarity
matrix of data points. Since calculating the dissimilarity matrix is a time-
consuming process, the method is not adequate for large-scale high-dimensional
data.

###  2.3 Classifier-Based Approaches

Li et al. Li et al. (2018) proposed a classifier-based quality measure called
an intrinsic dimension, which is the minimum number of solutions for certain
problems. For example, in a neural network, the intrinsic dimension is the
minimum number of parameters to reach the desired prediction performance.

The method has a benefit that it can be applied to many different types of
data as long as one has trainable classifiers for the data; however, it often
incurs high computation cost since it needs to change the number of classifier
parameters iteratively during data quality evaluation.

Overall, the existing data quality measures are mostly designed for binary
classification in low dimension spaces with a small number of data points. Due
to their computation complexity, they tend to consume large amount of time
when applied to large-scale high-dimensional data. In addition, the existing
measures tend to focus only on the inter-class aspects of data quality. In
this paper, we propose two new data quality measures suitable for large-scale
high-dimensional data resolving the above mentioned issues.

##  3 Methods

In this section, we formally describe our data quality measures. We focus on
multi-class classification tasks where each data point is associated with a
class label out of $c$ categories ($c\geq 2$). Our measures are created by
adapting ideas from Fisher’s LDA Hancock et al. (2014). Fisher’s LDA is a
dimensionality reduction technique, finding a projection matrix that maximizes
the between-class variance and minimizes the within-class variance at the same
time. Motivated by the idea, we propose two types of data quality measures,
class separability $M_{sep}$ and in-class variability $M_{var}$ and
$M_{var_{i}}$. For efficient handling of large-scale high-dimensional data, we
also propose techniques to reduce both computation and memory requirements
taking advantage of statistical methods, bootstrapping Efron (1979) and random
projection Bingham and Mannila (2001).

###  3.1 Fisher’s LDA

The objective of Fisher’s LDA Hancock et al. (2014) is to find the feature
subspace which maximizes the linear separability of a given dataset. Fisher’s
LDA achieves the objective by minimizing the within-class variance and
maximizing the between-class variance simultaneously.

To describe the Fisher’s LDA formally, let us consider an input matrix
$X\in\mathbb{R}^{m\times n}$ where $m$ is the number of data points, $n$ is
the input dimension, and $x_{i,j}\in\mathbb{R}^{n}$ is a $j$-th data point in
the $i$-th class. The within-class scatter matrix $S_{w}\in\mathbb{R}^{n\times
n}$ is defined as follows:

$S_{w}=\sum^{c}_{i=1}\sum^{m_{i}}_{j=1}(x_{i,j}-\overline{x}_{i})(x_{i,j}-\overline{x}_{i})^{T}.\enspace$

Here, $c$ is the number of classes, $m_{i}$ is the number of data points in
the $i$-th class, and $\overline{x}_{i}\in\mathbb{R}^{n}$ is the mean of data
points in the $i$-th class. This formulation can be interpreted as the sum of
class-wise scatter matrices. A small determinant of $S_{w}$ indicates that
data points in the same class exist densely in a narrow area, which may lead
to high class separability.

Next, the between-class scatter matrix $S_{b}\in\mathbb{R}^{n\times n}$ is
defined as follows:

$S_{b}=\sum_{i=1}^{c}m_{i}\left(\overline{x}_{i}-\overline{x}\right)\left(\overline{x}_{i}-\overline{x}\right)^{T},\enspace$

where $\overline{x}$ is the mean of entire data points in the given dataset. A
large determinant of $S_{b}$ indicates that the mean vector $\overline{x}_{i}$
of each class is far from the $\overline{x}$, another condition hinting for
high class separability.

Using these two matrices, we can describe the objective of Fisher’s LDA as
follows:

$\Phi_{lda}\in\operatorname*{arg\,max}_{\Phi}\frac{|\Phi^{T}S_{b}\Phi|}{|\Phi^{T}S_{w}\Phi|}.\enspace$
(1)

Here, $\Phi_{lda}\in\mathbb{R}^{n\times d}$ is the projection matrix where $d$
is the dimension of feature subspace (in general, we choose $d\ll n$). The
column vectors of projection matrix $\Phi_{lda}$ are the axes of feature
subspace, which maximize the class separability. The term in the objective
function is also known as the Fisher’s criterion. By projecting $X$ onto these
axes, we obtain a $d$-dimensional projection of the original data
$X^{\prime}\in\mathbb{R}^{m\times d}$:

$X^{\prime}=X\Phi_{lda}.\enspace$

In general, if $S_{w}$ is an invertible matrix, we can calculate the
projection matrix which maximizes the objective of the Fisher’s LDA by
eigenvalue decomposition.

###  3.2 Proposed Data Quality Measures

Motivated by the ideas in Fisher’s LDA, we propose two types of new data
quality measures: $M_{sep}$ (class separability), $M_{var}$ and $M_{var_{i}}$
(in-class variability).

####  3.2.1 Class Separability

Our first data quality measure tries to capture the class separability of a
dataset by combining the within-class variance and between-class variance,
similarly to Fisher’s LDA (1) but more efficiently for large-scale and high-
dimensional data and comparable with other datasets.

We start from creating the normalized versions of the matrices $S_{w}$ and
$S_{b}$ in Fisher’s LDA (1) so that they will not be affected by the different
numbers of examples in classes ($m_{i}$ is the number of examples in the
$i$-th class) across different datasets. The normalized versions are denoted
by $\hat{S}_{w}$ and $\hat{S}_{b}$:

$\hat{S}_{w}:=\sum^{c}_{i=1}\frac{1}{m_{i}}\sum^{m_{i}}_{j=1}(x_{i,j}-\overline{x}_{i})(x_{i,j}-\overline{x}_{i})^{T},\qquad\hat{S}_{b}:=\sum^{c}_{i=1}\frac{m_{i}}{\sum^{c}_{j=1}m_{j}}(\overline{x}_{i}-\overline{x})(\overline{x}_{i}-\overline{x})^{T}.\enspace$
(2)

Considering the determinants of these $n\times n$ matrices as in the original
Fisher’s LDA will be too costly for a high-dimensional data where $n$ is
large, since the time complexity to compute the determinants will be
proportional nearly to $n^{3}$. Instead, we consider the direction of maximum
linear separation $v\in\mathbb{R}^{n}$ that maximizes the ratio of between-
class variance to the within-class variance being projected onto the vector.
Using the vector, we define our first data quality measure $M_{sep}$ for class
separability as follows:

$M_{sep}:=\max_{v\in\mathbb{R}^{n}:\|v\|=1}\frac{|v^{T}\hat{S}_{b}v|}{|v^{T}\hat{S}_{w}v|}.\enspace$
(3)

This formulation is almost the same as (1) in Fisher’s LDA except that (1)
finds the projection matrix $\phi_{lda}$ which maximizes the Fisher’s
criterion, while, in (3), we will focus on finding the maximum value of
Fisher’s criterion itself. Unlike Fisher’s criterion, our measure $M_{sep}$ is
comparable across datasets with different numbers of classes and examples due
to normalization, to check the relative difficulty of linear classification.

Solving (3) directly will be preventive for a large $n$ as in the original
LDA. If $\hat{S}_{w}$ is invertible, we can calculate the vector which
maximizes $M_{sep}$ as follows using simple linear algebra. To find the vector
$v$ which maximizes the equation in (3), first differentiate it with respect
to $v$ to get:

$(v^{T}\hat{S}_{b}v)\hat{S}_{w}v=(v^{T}\hat{S}_{w}v)\hat{S}_{b}v.\enspace$

This leads us to the following generalized eigenvalue problem in the form of:

$\hat{S}_{w}^{-1}\hat{S}_{b}v=\lambda v,\enspace$ (4)

where $\lambda=\frac{v^{T}\hat{S}_{b}v}{v^{T}\hat{S}_{w}v}$ can be thought as
an eigenvalue of the matrix $\hat{S}_{w}^{-1}\hat{S}_{b}$. The maximizer $v$
is the eigenvector corresponding to the largest eigenvalue of
$\hat{S}_{w}^{-1}\hat{S}_{b}$ which can be found rather efficiently by the
Lanczos algorithm Golub and Loan (1996). However, the overall time complexity
for computation can be up to $\mathcal{O}(n^{3})$, which makes it difficult to
calculate the optimal vector for high-dimensional data, such as images. In
Section 3.3, we provide an efficient algorithm to compute $M_{sep}$ using
random projection.

####  3.2.2 In-Class Variability

Our second data quality measure gauges the in-class variability. Figure 1
shows one of the motivating examples to consider in-class variability for data
quality. In the figure, we have two photos of the Bongeunsa temple in Seoul,
Korea, taken by the same photographer. The photographer had been asked to take
photos of Korean objects from several different angles, and it turned out that
quite a few of the photos were taken in only marginal angle differences. Since
the data creation was a government-funded project providing data for
developing object recognition systems in academia and industry, low data
variability was definitely an issue.

Figure 1: An example of low in-class variability that similar images in the
same class. The images are Bongeunsa temple in Seoul, Korea. (Source: Korean
Type Object Image AI Training Dataset at http://www.aihub.or.kr/aidata/132,
National Information Society Agency.)

Here, we define two types of in-class variability measure, the overall in-
class variability of a given dataset $M_{var}$ and the in-class variability of
the $i$-th class, $M_{var_{i}}$. First, the overall in-class variability
$M_{var}$ tries to capture the minimum variance of data points being projected
onto any direction, based on the matrix $\hat{S}_{w}$ defined in (2):

$M_{var}:=\min_{v\in\mathbb{R}^{n}:\|v\|=1}\frac{1}{c\cdot
n}v^{T}\hat{S}_{w}v,\enspace$

where $c$ is the number of class and $n$ is the dimension of data. Unlike
class separability, we added additional normalization factors $c$ and $n$,
since the value $\hat{S}_{w}$ is affected by the number of class and the data
dimension.

Second, the class-wise in-class variability $M_{var_{i}}$ is based on the
sample covariance matrix of each class:

$\hat{S}_{w_{i}}:=\frac{1}{m_{i}}\sum^{m_{i}}_{j=1}(x_{i,j}-\overline{x}_{i})(x_{i,j}-\overline{x}_{i})^{T},\enspace$

where $m_{i}$ is the number of data points in the $i$-th class. The class-wise
in-class variability measure $M_{var_{i}}$ is defined as follows:

$M_{var_{i}}:=\min_{v\in\mathbb{R}^{n}:\|v\|=1}\frac{1}{c\cdot
n}v^{T}\hat{S}_{w_{i}}v\enspace.$

The normalization factors $c$ and $n$ are required for the same reason as in
$M_{var}$. The measure $M_{var_{i}}$ represents the smallest variance of the
data points in the same class after being projected onto any direction.

As a matter of fact, $M_{var}$ and $M_{var_{i}}$ are the same as the smallest
eigenvalue of $\frac{1}{c\cdot n}\hat{S}_{w}$ and $\frac{1}{c\cdot
n}\hat{S}_{w_{i}}$ which can be computed for instance using the Lanczos
algorithm Golub and Loan (1996) on the inverse of them with
$\mathcal{O}(n^{3})$ computation, which will be preventive for large data
dimensions $n$. We discuss a more efficient way to estimate the value in the
next section, which can be computed alongside with our first data quality
measure without significant extra cost.

Using the $M_{var}$ and $M_{var_{i}}$, we can analyze the variety or
redundancy in a given dataset. For instance, a very small $M_{var}$ and
$M_{var_{i}}$ would indicate that we may have a small diversity issue where
data points in the invested class are mostly alike. On the other hand, the
overly large $M_{var}$ and $M_{var_{i}}$ may indicate a noise issue in the
class, possibly including incorrect labeling. The difference between $M_{var}$
and $M_{var_{i}}$ is that the $M_{var}$ aggregates the information of
diversity for each class, and the $M_{var_{i}}$ represents the information of
diversity for a specific class. Since the $M_{var}$ aggregates the information
of variability of data points in each class, we can use this for comparing the
in-class variability between datasets. On the other hand, we can use
$M_{var_{i}}$ for the datasets analysis, i.e., data points of a specific class
with less $M_{var_{i}}$ than other classes may cause low generalization
performance. We will discuss more details in Section 4.

###  3.3 Methods for Efficient Computation

One of the key properties required for data quality measures is that they
should be computable in a reasonable amount of time and computation resources
since the amount and the dimension of data are keep increasing as new advanced
sensing technologies become available. In this section, we describe how we
avoid a large amount of time and memory complexity to compute our suggested
data quality measures.

####  3.3.1 Random Projection

Random projection Bingham and Mannila (2001) is a dimension reduction
technique that can transform an $n$-dimensional vector into a $k$-dimensional
vector ($k\ll n$), while preserving the critical information of the original
vector. The idea behind of random projection is the Johnson-Lindenstrauss
lemma Dasgupta and Gupta (1999). That is, for any vectors
$\\{x,x^{\prime}\\}\in X$ from a set of $m$ vectors in
$X\subset\mathbb{R}^{n}$ and for $\epsilon\in(0,1)$, there exists a linear
mapping $f:\mathbb{R}^{n}\to\mathbb{R}^{k}$ such that the pairwise distances
of vectors are almost preserved after projection in the sense that:

$(1-\epsilon)\|x-x^{\prime}\|^{2}_{2}\leq\|f(x)-f(x^{\prime})\|^{2}_{2}\leq(1+\epsilon)\|x-x^{\prime}\|^{2}_{2},$

where $k>8\ln(m)/\epsilon^{2}$. It is known that when the original dimension
$n$ is large, a random projection matrix $P\in\mathbb{R}^{k\times n}$ can
serve as the feature mapping $f$ in the lemma, since random vectors in
$\mathbb{R}^{n}$ tend to be orthogonal to each other as $n$ increases Kaski
(1998).

Motivated by the above phenomenon, we use random projection to find a vector
that satisfies (3) instead of calculating the eigenvalue decomposition to
solve (4). The idea is that if the number of random vectors is sufficiently
large, the maximum value of the Fisher’s criterion calculated by random
projection can approximate the behavior of a true solution.

Furthermore, random projection makes it unnecessary to explicitly store
$\hat{S}_{w}$ and $\hat{S}_{b}$ since we can simply compute the denominator
and numerator of (3) as follows:

$w^{T}\hat{S}_{w}w=\sum^{c}_{i=1}\frac{1}{m_{i}}\sum^{m_{i}}_{j=1}w^{T}(x_{i,j}-\overline{x}_{i})(x_{i,j}-\overline{x}_{i})^{T}w,\enspace$

$w^{T}\hat{S}_{b}w=\sum_{i=1}^{c}\frac{m_{i}}{\sum_{j=1}^{c}m_{j}}w^{T}\left(\overline{x}_{i}-\overline{x}\right)\left(\overline{x}_{i}-\overline{x}\right)^{T}w,\enspace$

where $w$ is a random unit vector drawn from $\mathcal{N}(0,1)$. This
technique is critical for dealing with high-dimensional data, such as images,
in a memory-efficient way. In our experiments, ten random projection vectors
were sufficient in most cases to accurately estimate our quality measures.

####  3.3.2 Bootstrapping

Bootstrapping Efron (1979) is a sampling-based technique that estimates the
statistic of the population with little data using sampling with replacement.
For instance, bootstrapping can be used to estimate the mean and the variance
of a statistic from an unknown population. Let $s_{i}$ is a statistic of
interest that is calculated from a randomly drawn sample of an unknown
population. The mean and variance of the statistic can be estimated as
follows:

$\hat{\mu}=\frac{1}{B}\sum_{i=1}^{B}s_{i},\enspace\quad\hat{\sigma}^{2}=\frac{1}{B}\sum_{i=1}^{B}s_{i}^{2}-\left(\frac{1}{B}\sum_{i=1}^{B}s_{i}\right)^{2},\enspace$

where $B$ is the number of bootstrap samples, $\hat{\mu}$ is a mean estimate
of the statistic, and $\hat{\sigma}^{2}$ is the variability of the estimate.
By using a small $B$, we can reduce the number of data points to be considered
at once. We found that $B=100$ and making each bootstrap sample to be $25\%$
of a given dataset in size worked well overall our experiments. We summarized
the above procedure in Algorithm 1 (The implementation is available here:
https://github.com/Hyeongmin-Cho/Efficient-Data-Quality-Measures-for-High-
Dimensional-Classification-Data.)

Result: $M_{sep}$, $M_{var}$ and $M_{var_{i}}$ score

$\textbf{Dataset}=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}$

Args= the number of samples $B$, a sample ratio of each bootstrap sample
against a given dataset $R$, the number of random vector used in each sample
$nv$, an array storing the values of overall in-class variability $A_{var}$,
an array storing the values of class-wise in-class variability $A_{var_{i}}$
and an array storing the values of class separability $A_{sep}$.

’$\xleftarrow{}$’ symbol stands for variable assignment

$i\xleftarrow{}1$

$A_{var}\xleftarrow{}\\{\\}$

$A_{var_{i}}\xleftarrow{}\\{\\}$

$A_{sep}\xleftarrow{}\\{\\}$

while  _i $\leq$ B_ do

$j\xleftarrow{}1$

$i\xleftarrow{}i+1$

Calculate the number of class $c$ and data dimension $n$ from the dataset

Sampling with replacement using stratified sampling as much as R ratio from
the dataset

Standardize the sampled dataset

while  _j $\leq$ nv_ do

$j\xleftarrow{}j+1$

$w\xleftarrow{}$ a unit vector drawn from $\mathcal{N}(0,1)$

Compute $w^{T}\hat{S}_{w_{j,c}}w$

$w^{T}\hat{S}_{w_{j}}w\xleftarrow{}Sum(\\{w^{T}\hat{S}_{w_{j,1}}w,\dots,w^{T}\hat{S}_{w_{j,c}}w\\})$

$M_{var-j}\xleftarrow{}w^{T}\hat{S}_{w_{j}}w$

Compute $w^{T}\hat{S}_{b_{j}}w$

$M_{sep-j}\xleftarrow{}(w^{T}\hat{S}_{b_{j}}w)/(w^{T}\hat{S}_{w_{j}}w)$

end while

$A_{var_{i}}$.insert($\\{\frac{1}{c\cdot
n}\min(w^{T}\hat{S}_{w_{1,1}}w,\dots,w^{T}\hat{S}_{w_{nv,1}}w),\dots,\frac{1}{c\cdot
n}\min(w^{T}\hat{S}_{w_{1,c}}w,\dots,w^{T}\hat{S}_{w_{nv,c}}w)\\}$)

$A_{var}$.insert($\frac{1}{c\cdot n}\min(M_{var-1},\dots,M_{var-nv})$)

$A_{sep}$.insert($\max(M_{sep-1},\dots,M_{sep-nv})$)

end while

$M_{sep}\xleftarrow{}Mean(A_{sep})$

$M_{var}\xleftarrow{}Mean(A_{var})$

$M_{var_{i}}\xleftarrow{}ClassWiseMean(A_{var_{i}})$

Return $M_{sep},M_{var},M_{var_{i}}$

Algorithm 1 Algorithm of class separability and in-class variability.

##  4 Experiment Results

In this section, we show that our method can evaluate the data quality of the
large-scale high-dimensional dataset efficiently.

To verify the representative performance of $M_{sep}$ for class separability,
we calculated the correlation between the accuracy of chosen classifiers and
$M_{sep}$. Classifiers used in our experiments are as follows: a perceptron, a
multi-layer perceptron with one hidden layer and LeakyReLU (denoted by MLP-1),
and a multi-layer perceptron with two hidden layers and LeakyReLU (denoted by
MLP-2). To simplify the experiments, we trained the models with the following
settings: 30 epochs, a batch size of 100, a learning rate of 0.002, the Adam
optimizer, and the cross-entropy loss function. Additionally, we fixed the
hyperparameters of Algorithm 1 as $B=100$, $R=0.25$, and $nv=10$ since there
was no big difference in performance when larger hyperparameter values were
used.

For comparison with other quality measures, we chose $F1$, $N1$, and $N3$ from
Ho and Basu (2002) and $CSG$ from Branchaud-Charron et al. Branchaud-Charron
et al. (2019). Here, $N1$, $N3$, and $CSG$ are known to be highly correlated
with test accuracy of classifiers Branchaud-Charron et al. Branchaud-Charron
et al. (2019). $F1$ is similar to our $M_{sep}$ in its basic idea. Other
quality measures suggested in Ho and Basu (2002) showed very similar
characteristics to $F1$, $N1$, $N3$, and $CSG$ and are therefore not included
in the results.

###  4.1 Datasets

To evaluate the representative performance of $M_{sep}$ for class
separability, we used various image datasets that are high-dimensional and
popular in mobile applications. We chose ten benchmark image datasets for our
experiments: MNIST, notMNIST, CIFAR10, Linnaeus, STL10, SVHN, ImageNet-1,
ImageNet-2, ImageNet-3, and ImageNet-4. MNIST LeCun and Cortes (2010) consists
of ten handwritten digits from 0 to 9. The dataset contains 60,000 training
and 10,000 test data points. We sampled 10,000 data from the training data for
a model training and measuring the quality, and we sampled 2500 data from the
test data for assessing the model accuracy. The notMNIST Bulatov (2011)
dataset is quite similar to MNIST, containing English letters from A to J in
various fonts. It has 13,106 training and 5618 test samples. We sampled the
data in the same way as MNIST. Linnaeus Chaladz and Kalatozishvili (2017)
consists of five classes: berry, bird, dog, flower, and others. Although the
dataset is available in various image sizes, we chose $32\times 32$ to reduce
the computation time of $N1$, $N3$, and $CSG$. CIFAR10 Krizhevsky (2009) is
for object recognition with ten general object classes. It consists of 50,000
training data and 10,000 test data points. We sampled the CIFAR10 dataset in
the same way as MNIST. STL10 Coates et al. (2011) is also for object
recognition with ten classes, and it has $92\times 92$ images: we resized the
images into $32\times 32$ to reduce the computation time for the $N1$, $N3$,
and $CSG$. The dataset consists of 5000 training and 8000 test data points. We
combined these two sets into a single dataset, and then sampled 10,000 data
points from the combined set for model training and measuring quality. We also
sampled 2500 data points from the combined set for assessing prediction model
accuracy if necessary. SVHN Netzer et al. (2011) consists of street view house
number images. The dataset contains 73,200 data points. We sampled 10,000
training data for a model training and measuring the quality, and we sampled
2500 data for assessing the model accuracy. ImageNet-1, ImageNet-2, ImageNet-3
and ImageNet-4 are subsets of Tiny ImageNet dataset Deng et al. (2009). The
Tiny ImageNet dataset contains 200 classes, and each class has 500 images.
They are consist of randomly selected ten classes of the Tiny ImageNet dataset
(total 5000 data points). We used 4500 data points for model training and
measuring the quality and 500 data points for assessing the model accuracy,
respectively.

We summarized the details of datasets in Table 4.1. The accuracy values in the
Table 4.1 are calculated from the MLP-2 model since it showed good overall
performance compared to the perceptron and the MLP-1 models.

[H] Details of the datasets used in our experiments. The accuracy is from
MLP-2, and $M$ represents the total number of data used for training and
evaluation. Datasets Accuracy $M$ No. Classes Description MNIST 92.64% 12.5 k
10 Hand written digit notMNIST 89.24% 12.5 k 10 Fonts and glyphs similar to
MNIST Linnaeus 45.50% 4.8 k 5 Botany and animal class images CIFAR10 42.84%
12.5 k 10 Object recognition images STL10 40.88% 12.5 k 10 Object recognition
images SVHN 45.60% 12.5 k 10 House number images ImageNet-1 37.40% 5 k 10
Visual recognition images (Tiny ImageNet) ImageNet-2 40.60% 5 k 10 Visual
recognition images (Tiny ImageNet) ImageNet-3 34.20% 5 k 10 Visual recognition
images (Tiny ImageNet) ImageNet-4 36.20% 5 k 10 Visual recognition images
(Tiny ImageNet)

###  4.2 Representation Performance of the Class Separability Measure
$M_{Sep}$

Here, we show in experiments that how well our first quality measure $M_{sep}$
represents class separability, compared to simple but popular classifiers and
the existing data quality measures.

####  4.2.1 Correlation with Classifier Accuracy

To demonstrate how well $M_{sep}$ represents the class separability of given
datasets, we compared the absolute value of Pearson correlation and Spearman
rank correlation between quality measures $M_{sep}$, $N1$, $N3$, $F1$, and
$CSG$ to the prediction accuracy of three classification models: perceptron,
MLP-1, and MLP-2. Table 4.2.1 summarizes the results.

In the case of the perceptron, $M_{sep}$ has a similar Pearson correlation
with the shortest computation time to the $N1$ and $N3$ which have the highest
correlation with the accuracy of classifiers. Furthermore, $M_{sep}$ and $F1$
have the highest Spearman rank correlation. This is because $M_{sep}$ and $F1$
measure linear separability that is essentially the information captured by
the linear classifier, the perceptron in our case. In the case of MLP-1 and
MLP-2, $M_{sep}$ also showed a sufficiently high correlation with
classification accuracy although it is slightly lower in Pearson correlation
compared to the case of the perceptron. On the other hand, $CSG$ does not seem
to have noticeable benefits considering its computation time. This is because
$CSG$ is affected by an embedding network which requires a large amount of
training time.

In summary, the result shows that our measure $M_{sep}$ can capture
separability of data as good as the existing data quality measures, while
reducing computation time significantly.

[H]

The absolute Pearson and Spearman rank correlation between the quality
measures and the accuracy of three classifiers on the ten image datasets
(MNIST, CIFAR10, notMNIST, Linnaeus, STL10, SVHN, ImageNet-1, ImageNet-2,
ImageNet-3, and ImageNet-4). The computation time of our method $M_{sep}$ is
the fastest. Classifier Quality Measure Pearson Corr. Spearman Corr. Time (s)
Perceptron $F1$ 0.9386 0.7697 1253 $N1$ 0.9889 0.7333 5104 $N3$ 0.9858 0.7333
9858 $CSG$ 0.9452 0.8182 23,711 $M_{sep}$ (ours) 0.9693 0.8061 354 MLP-1 $F1$
0.9039 0.3455 1253 $N1$ 0.9959 0.9758 5104 $N3$ 0.9961 0.9030 9858 $CSG$
0.9295 0.5879 23,711 $M_{sep}$ (ours) 0.9261 0.3818 354 MLP-2 $F1$ 0.8855
0.3455 1253 $N1$ 0.9908 0.9273 5104 $N3$ 0.9912 0.8788 9858 $CSG$ 0.9127
0.5879 23,711 $M_{sep}$ (ours) 0.9117 0.4303 354

####  4.2.2 Correlation with Other Quality Measures

In order to check if our suggested data quality measure $M_{sep}$ is
compatible with the existing ones in quality, and therefore ours can be a
faster alternative to the existing data quality measures, we computed the
Pearson correlation between $F1$, $N1$, $N3$, $CSG$, and $M_{sep}$. The
results are summarized in Table 4.2.2. Our measure $M_{sep}$ showed a high
correlation with all four existing measures $F1$, $N1$, $N3$, and $CSG$,
indicating that $M_{sep}$ is able to capture the data quality information
represented by $F1$, $N1$, $N3$, and $CSG$.

[H] The absolute Pearson correlation between $M_{sep}$ and other quality
measures. $M_{sep}$ (Ours) $F1$ $N1$ $N3$ $CSG$ $M_{sep}$ (ours) 1.0000 0.9673
0.9322 0.9245 0.9199 $F1$ 0.9673 1.000 0.8909 0.8879 0.8806 $N1$ 0.9322 0.8909
1.0000 0.9988 0.9400 $N3$ 0.9245 0.8879 0.9988 1.000 0.9417 $CSG$ 0.9199
0.8806 0.9400 0.9417 1.0000

####  4.2.3 Computation Time

As mentioned above, our quality measure $M_{sep}$ represents the class
separability well, but much faster in computation than $F1$, $N1$, $N3$, and
$CSG$. Here, we show how the computation time changes according to data
dimension and sample sizes, in order to show that our suggested data quality
measure can be used for many big-data situations.

The computation time according to the data dimension is shown in Figure 2 and
Table 4.2.3. In all dimensions, our measure $M_{sep}$ was on average 3.8 times
faster than $F1$, 13.1 times faster than $N1$, 25.9 times faster than $N3$,
and 17.7 times faster than $CSG$. Since the $N1$, $N3$, and $CSG$ have to
calculate the MST and to train a 1NN classifier and embedding networks,
respectively, it is inevitable that they would take a large amount of
computation time (see more details in Sections 2.1 and 2.2). On the other
hand, since $M_{sep}$ utilizes random projection and bootstrapping to avoid
eigenvalue decomposition problem and to deal with the big-data situations, the
computation time of $M_{sep}$ is shortest in all cases.

Figure 2: Data dimension vs. computation time (CIFAR10).

[H] Data dimension vs. computation time (CIFAR10) in detail (the values in the
table represent seconds). Image Size Dimension $F1$ $N1$ $N3$ $CSG$ $M_{sep}$
(Ours) Speedup $16\times 16\times 3$ 768 49 246 445 1963 17 $\times 2.9\sim
115.5$ $32\times 32\times 3$ 3072 203 947 1850 2513 57 $\times 3.6\sim 44.1$
$48\times 48\times 3$ 6912 492 2144 4182 3132 122 $\times 4.0\sim 34.3$
$64\times 64\times 3$ 12,288 1011 3810 7466 5427 303 $\times 3.3\sim 24.6$
$80\times 80\times 3$ 19,200 1783 5973 11,674 6838 461 $\times 3.9\sim 25.3$
$96\times 96\times 3$ 27,648 2850 8652 17,346 9550 700 $\times 4.1\sim 24.8$

Figure 3 and Table 4.2.3 show how computation time changes for various sample
sizes. Our measure $M_{sep}$ was on average 2.8 times faster than $F1$, 47.0
times faster than $N1$, 94.5 times faster than $N3$, and 41.6 times faster
than $CSG$. $N1$ and $N3$ show extremely increasing computation time with
respect to the sample size, which is not suitable for large-scale high-
dimensional datasets.

All the above results show that our measure $M_{sep}$ is suitable for the big-
data situations and compatible with other well-accepted data quality measures.

Figure 3: Sample size vs. computation time (CIFAR10).

[H] Sample size vs. computation time (CIFAR10) in detail (the values in the
table represent seconds). Sample Size $F1$ $N1$ $N3$ $CSG$ $M_{sep}$ (Ours)
Speedup 10,000 205 939 1904 2645 56 $\times 3.7\sim 47.2$ 20,000 411 3719 7797
5674 136 $\times 3.0\sim 57.3$ 30,000 605 8572 17,177 9065 220 $\times 2.8\sim
78.1$ 40,000 825 14,896 29,813 11,843 293 $\times 2.8\sim 101.8$ 50,000 1006
23,235 46,541 16,208 387 $\times 2.6\sim 120.3$

####  4.2.4 Comparison to Exact Computation

In Section 3.2, we proposed to use random projections and bootstrapping for
fast approximation of the solution of (4), which can be computed exactly as an
eigenvalue. Here, we compare the values of $M_{sep}$ using the proposed
approximate computation (denoted by “Approx”) and the exact computation
(denoted by “Exact”) due to an eigensolver in the Python scipy package. One
thing is that, since we use only Gaussian random vectors for projection, it is
likely that they may not match the true eigenvectors; therefore, the
approximated quantity would differ from the exact value. However, we found
that the approximate quantities match well the exact values in their
correlation, as indicated in Table 4.2.4, and, therefore, can be used for fast
comparison of data quality of high-dimensional large-scale datasets.

[H] Comparison of Exact and Approx values and their correlations. Pearson and
Spearman are the Pearson and Spearman rank correlation between the Exact and
Approx.

|  $Exact$ |  $Approx$
---|---|---
MNIST |  0.1550 |  0.0535
CIFAR10 |  0.0331 |  0.0173
notMNIST |  0.2123 |  0.0625
Linnaeus |  0.0250 |  0.0118
STL10 |  0.0695 |  0.0207
SVHN |  0.0004 |  0.0010
ImageNet-1 |  0.0062 |  0.0131
ImageNet-2 |  0.0293 |  0.0145
ImageNet-3 |  0.0191 |  0.0125
ImageNet-4 |  0.0092 |  0.0076
Pearson |  0.9847
Spearman |  0.9152

###  4.3 Class-Wise In-Class Variability Measure, $M_{Var_{i}}$

In fact, many of the existing data quality measures are designed to measure
the difficulty of classification for a given dataset. However, we believe that
the in-class variability of data must be considered as another important
factor of data quality. One example to show the importance and usefulness of
our in-class variability measure $M_{var_{i}}$ is the generalization
performance of a classifier.

The generalization performance of the learning model is an important
consideration especially in mission-critical AI-augmented systems. There are
many possible reasons causing low generalization, and overfitting is one of
the troublemakers. Although we have techniques to alleviate overfitting, e.g.,
checking the learning curve, regularization Srivastava et al. (2014); Ioffe
and Szegedy (2015), and ensemble learning Opitz and Maclin (1999), it is
critical to check if there is an issue in data to begin with which may lead to
any inductive bias. For example, a very small value of $M_{var_{i}}$ in a
class compared to the others would indicate a lack of variability in the
class, which can lead to low generalization due to, e.g., unchecked input
noise, background signal, object occlusion, and angle/brightness/contrast
differences during training. On the other hand, the overly large $M_{var_{i}}$
may indicate outliers or even mislabeled data points likely to incur unwanted
inductive bias in training.

To show the importance and usefulness of in-class variability, we created a
degraded version of CIFAR10 (denoted by degraded-CIFAR10) by reducing the
variability of a specific class. The degraded-CIFAR10 is created by the
following procedure. First, we chose an image of the deer class in the
training data, then selected the nine mostly similar images in the angular
distance to the chosen one. Figure 4 shows the total ten images selected by
the above procedure that have similar backgrounds and shapes. Next, we created
1000 images by sampling with replacement from the ten images, while adding
random Gaussian noise with zero mean and unit variance, and we replaced the
original deer class data with sampled degraded deer class data.

Figure 4: Ten similar selected images in the deer class on degraded-CIFAR10.
Images with high similarity were selected using cosine similarity.

Table 4 shows that the value of $M_{var_{i}}$ is significantly small on the
degraded deer class compared to the other classes. That is, it can capture
small in-class variability. In contrast, Table 4 shows that the existing
quality measures $F1$, $N1$, $N3$, and $CSG$ may not be enough to signify the
degradation of the dataset. As we can see, all quality measures indicate that
class separability increased in degraded-CIFAR10 compared to the original
CIFAR10; however, the test accuracy from MLP-2 decreased. This is because the
reduction in in-class variability is very likely to decrease the
generalization performance. Therefore, class separability measures can deliver
incorrect information regarding data quality in terms of in-class variability,
which can be a critical problem for generating a trustworthy dataset or
training a trustworthy model.

[H] Our in-class variability measure for the degraded-CIFAR10 dataset. A class
with a smaller value than other classes has a lower variability. Class Measure
$M_{var_{i}}$ $\times$ 1000 Airplane 0.1557 Automobile 0.2069 Bird 0.1394 Cat
0.1803 Deer 0.0123 Dog 0.1830 Frog 0.1344 Horse 0.1775 Ship 0.1472 Truck
0.1997

[H] Quality measures on the degraded-CIFAR10 dataset. The existing quality
measures $F1$, $N1$, $N3$, and $CSG$ only capture the class separability and
fail to capture the degradation. Lower values of $N1$, $N3$, and $CSG$
represent higher class separability, whereas lower values of $F1$ represent
lower class separability. The test accuracy is from MLP-2 trained with
original and degraded-CIFAR10, respectively, and tested on the original
CIFAR10 test data. Data Quality Measure $F1$ $N1$ $N3$ $CSG$ $Test\ Accuracy\
(\%)$ Original CIFAR10 0.2213 0.7909 0.7065 0.7030 42.84 Degraded-CIFAR10
0.2698 0.7035 0.6096 0.6049 41.28

As we showed above, the small value of $M_{var_{i}}$ of a specific class
represents that similar images do exist in the invested class, which can lead
to low generalization performance of classifiers. Suppose we have generated a
dataset for an autonomous driving object classification task. The dataset has
been revealed that it has a high class separability through various quality
measures. Moreover, the training accuracy was also high. Therefore, one may
expect high generalization performance. Unfortunately, the exact opposite can
happen. If the variability in the specific class is small as in the degraded-
CIFAR10 example above, high generalization performance cannot be expected. For
instance, if a car with new colors and new shapes that have never been trained
is given as an input to the model, the probability of properly classifying the
car will be low. This example indicates that in-class variability plays an
important role in data quality evaluation.

###  4.4 Quality Ranking Using $M_{Sep}$ and $M_{Var}$

As we mentioned before, quality measures $M_{sep}$ and $M_{var}$ can be
compared among different datasets. The class separability $M_{sep}$ represents
the relative difficulty of linear classification, and the overall in-class
variability $M_{var}$ represents the average variability of data points in
classes.

Figure 5 shows a data quality comparison plot of datasets in our experiments.
The direction towards the lower-left corner indicates lower class separability
and lower in-class variability, and the upper-right direction is for higher
class separability and higher in-class variability. According to the plot, the
MNIST and the notMNIST dataset show very high linear separability compared to
other datasets, indicating that their classification might be easier than the
other datasets. The SVHN dataset is at the lower-left corner, indicating low
linear separability and possible redundancy issues (this could be just the
reflection of the fact that many SVHN images contain changing digits but the
same backgrounds). The four ImageNet datasets, Linnaeus, CIFAR10 and STL10
have similar class separability and in-class variability values. This appears
to be understandable considering their similar data construction designed for
object recognition.

Figure 5: Data quality plot using the two proposed quality measures.

##  5 Conclusions

In this paper, we proposed data quality measures $M_{sep}$, $M_{var}$ and
$M_{var_{i}}$, which can be applied efficiently on large-scale high-
dimensional datasets. Our measures are estimated using random projection and
bootstrapping and therefore can be applied efficiently on large-scale high-
dimensional data. We showed that $M_{sep}$ can be used as a good alternative
to the existing data quality measures capturing class separability, while
reducing their computational overhead significantly. In addition, $M_{var}$
and $M_{var_{i}}$ measures in-class variability, which is another important
factor to avoid unwanted inductive bias in trained models.

Conceptualization, H.C. and S.L.; methodology, H.C. and S.L.; validation,
H.C.; writing-original draft preparation, H.C.; writing-review and editing,
S.L.; supervision, S.L. Both authors have read and agreed to the published
version of the manuscript.

This research was supported by Basic Science Research Program through the
National Research Foundation of Korea(NRF) funded by the Ministry of
Education(2018R1D1A1B07051383), and also by the MSIT(Ministry of Science and
ICT), Korea, under the ITRC(Information Technology Research Center) support
program(IITP-2020-0-01749) supervised by the IITP(Institute of Information &
Communications Technology Planning & Evaluation).

The data presented in this study are openly available: MNIST
(http://yann.lecun.com/exdb/mnist/), notMNIST
(https://www.kaggle.com/lubaroli/notmnist), Linnaeus
(http://chaladze.com/l5/), CIFAR10
(https://www.cs.toronto.edu/~kriz/cifar.html), STL10
(https://ai.stanford.edu/~acoates/stl10/), SVHN
(http://ufldl.stanford.edu/housenumbers/), and ImageNet
(https://www.kaggle.com/c/tiny-imagenet).

The authors declare no conflict of interest.

References

## References

  * Ho and Basu (2002) Ho, T.K.; Basu, M.  Complexity measures of supervised classification problems.  IEEE Trans. Pattern Anal. Mach. Intell. 2002, _24_ , 289–300.
  * Baumgartner and Somorjai (2006) Baumgartner, R.; Somorjai, R.  Data complexity assessment in undersampled classification of high-dimensional biomedical data.  Pattern Recognit. Lett. 2006, 27, 1383–1389.
  * Branchaud-Charron et al. (2019) Branchaud-Charron, F.; Achkar, A.; Jodoin, P.M.  Spectral metric for dataset complexity assessment.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Long Beach. CA, USA, 15–21 June 2019\.
  * Hancock et al. (2014) Hancock, J.M., Zvelebil, M.J. and Cristianini, N.  Fisher Discriminant Analysis (Linear Discriminant Analysis).  Dict. Bioinform. Comput. Biol., 2014, https://doi.org/10.1002/9780471650126.dob0238.pub2.
  * Bingham and Mannila (2001) Bingham, E.; Mannila, H.  Random projection in dimensionality reduction: Applications to image and text data.  In Proceedings of the ACM Special Interest Group on Knowledge Discovery in Data, San Francisco, CA, USA, 26–29 August 2001\.
  * Efron (1979) Efron, B.  Bootstrap Methods: Another look at the jackknife.  Ann. Stat., 1979, _7_ , 1–26.
  * Li and Vitányi (2008) Li, M.; Vitányi, P.  An Introduction to Kolmogorov Complexity and Its Applications; Springer: Berlin, Germany, 2008.
  * Leyva et al. (2015) Leyva, E.; González, A.; Pérez, R.  A set of complexity measures designed for applying meta-learning to instance selection.  IEEE Trans. Knowl. Data Eng. 2015, _27_ , 354–367.
  * Sotoca et al. (2006) Sotoca, J.M.; Mollineda, R.A.; Sánchez, J.S.  A meta-learning framework for pattern classification by means of data complexity measures.  Intel. Artif. 2006, 10, 31–38.
  * Garcia et al. (2018) Garcia, L.P.F.; Lorena, A.C.; de Souto, M.C.P.; Ho, T.K.  Classifier recommendation using data complexity measures.  In Proceedings of the International Conference on Pattern Recognition, Beijing, China, 20–24 August 2018.
  * de Melo and Lorena (2018) de Melo, V.V.; Lorena, A.C.  Using complexity measures to evolve synthetic classification datasets.  In Proceedings of the IEEE International Joint Conference on Neural Network, Rio de Janeiro, Brazil, 8–13 July 2018.
  * Masci et al. (2011) Masci, J.; Meier, U.; Cireşan, D.; Schmidhuber, J.  Stacked Convolutional Auto-Encoders for Hierarchical Feature Extraction.  In Proceedings of the International Conference on Artificial Neural Networks, Espoo, Finland, 14–17 June 2011\.
  * van der Maaten and Hinton (2008) van der Maaten, L.; Hinton, G.  Visualizing Data using t-SNE.  J. Mach. Learn. Res. 2008, _9_ , 2579–2605.
  * Duin and Pękalska (2006) Duin, R.P.W.; Pękalska, E.  Object representation, sample size and dataset complexity.  Data Complexity in Pattern Recognition; Springer: Berlin, Germany, 2006.
  * Li et al. (2018) Li, C.; Farkhoor, H.; Liu, R.; Yosinski, J.  Measuring the intrinsic dimension of object landscapes.  In Proceedings of the International Conference on Learning Representations, Vancouver, BC, Canada, 30 April–3 May 2018.
  * Golub and Loan (1996) Golub, G.H.; Loan, C.F.V.  Matrix Computations.  Baltimore; Johns Hopkins University Press: Baltimore, MD, USA. 1996; pp. 470–507.
  * Dasgupta and Gupta (1999) Dasgupta, S.; Gupta, A.  _An Elementary Proof of the Johnson-Lindenstrauss Lemma_ ;  Technical Report; UC Berkeley: Berkeley, CA, USA, 1999.
  * Kaski (1998) Kaski, S.  Dimensionality reduction by random mapping: fast similarity computation for clustering.  In Proceedings of the IEEE International Joint Conference on Neural Networks, Anchorage, AK, USA, 4–9 May 1998.
  * LeCun and Cortes (2010) LeCun, Y.; Cortes, C.  _MNIST Handwritten Digit Database_ Available online:http://yann.lecun.com/exdb/mnist/ (25 October 2020).
  * Bulatov (2011) Bulatov, Y.  Notmnist Dataset.  Technical Report, Google (Books/OCR). 2011. Available online: http://yaroslavvb.blogspot.it/2011/09/notmnist-dataset.html (25 October 2020).
  * Chaladz and Kalatozishvili (2017) Chaladz, G.; Kalatozishvili, L.  _Linnaeus 5 Dataset for Machine Learning_ Available online:http://chaladze.com/l5/ (25 October 2020).
  * Krizhevsky (2009) Krizhevsky, A.  _Learning Multiple Layer of Features from Tiny Images_ ; Technical Report; Computer Science Department, University of Toronto: Toronto, ON, Canada, 2009.
  * Coates et al. (2011) Coates, A.; Lee, H.; Ng, A.Y.  An analysis of single layer networks in unsupervised feature learning.  J. Mach. Learn. Res. 2011, _15_ , 215–223
  * Netzer et al. (2011) Netzer, Y.; Wang, T.; Coates, A.; Bissacco, A.; Wu, B.; Ng, A.Y.  Reading Digits in Natural Images with Unsupervised Feature Learning.  In Proceedings of the NIPS Workshop on Deep Learning and Unsupervised Feature Learning, Granada, Spain, 16–17 December 2011.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.J.; Li, K.; Fei-Fei, L.  ImageNet: A large-scale hierarchical image database.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Miami, FL, USA, 20–25 June 2009; pp. 248–255.
  * Srivastava et al. (2014) Srivastava, N.; Hinton, G.; Krizhevsky, A.; Sutskever, I.; Salakhutdinov, R.  Dropout: A Simple Way to Prevent Neural Networks from Overfitting.  J. Mach. Learn. Res. 2014, 15, 1929–1958.
  * Ioffe and Szegedy (2015) Ioffe, S.; Szegedy, C.  Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift.  arXiv 2015, arXiv:1502.03167, 2015.
  * Opitz and Maclin (1999) Opitz, D.; Maclin, R.  Popular Ensemble Methods: An Empirical Study.  J. Artif. Intell. Res. 1999, 11, 169–198.