#  Register Your Forests: Decision Tree Ensemble Optimization by Explicit CPU
Register Allocation

Daniel Biebert<EMAIL_ADDRESS>TU DortmundGermany ,  Christian
Hakert<EMAIL_ADDRESS>TU DortmundGermany ,  Kuan-Hsun Chen
<EMAIL_ADDRESS>University of TwenteNetherlands and  Jian-Jia Chen  jian-
<EMAIL_ADDRESS>TU DortmundGermany

(2024)

###### Abstract.

Bringing high-level machine learning models to efficient and well-suited
machine implementations often invokes a bunch of tools, e.g. code generators,
compilers, and optimizers. Along such tool chains, abstractions have to be
applied. This leads to not optimally used CPU registers. This is a
shortcoming, especially in resource constrained embedded setups. In this work,
we present a code generation approach for decision tree ensembles, which
produces machine assembly code within a single conversion step directly from
the high-level model representation. Specifically, we develop various
approaches to effectively allocate registers for the inference of decision
tree ensembles. Extensive evaluations of the proposed method are conducted in
comparison to the basic realization of C code from the high-level machine
learning model and succeeding compilation. The results show that the
performance of decision tree ensemble inference can be significantly improved
(by up to $\approx 1.6\times$), if the methods are applied carefully to the
appropriate scenario.

††journalyear: 2024††copyright: cc

##  1\. Introduction

Decision tree ensembles are top candidates for lightweight machine learning,
especially in the field of resource constrained systems, e.g., classification
in astrophysics (Buss et al., 2016) and nanopartical analysis with biosensors
(Yayla et al., 2019). Decision trees inherently provide optimization
potential, since on different executions of the tree, different paths are
followed. Thus, the tree inference potentially can be optimized for certain
paths, e.g., several attempts have been applied to ranking models at Facebook
to boost the evaluation of decision tree
models111https://engineering.fb.com/2017/03/27/ml-applications/evaluating-
boosted-decision-trees-for-billions-of-users/.

Training and execution of machine learning models, so-called inference, is a
data-centric task and therefore usually realized in a platform independent
manner. Hence, productive programming languages as Python are popular for
training the models (Pedregosa et al., 2011). However, high level programming
environments are likely not available in resource constrained systems, and an
interpreted language also consumes considerably more energy and time (Pereira
et al., 2017). In addition, recent trends show that the execution of the
trained models are usually not as efficient as with a platform specific
implementation. To bridge this gap, various solutions exist to transform the
high-level models after training into platform specific models. Although these
solutions are highly tuned towards performance (Dato et al., 2016; Lucchese et
al., 2016; Ye et al., 2018; Kim et al., 2010; Buschjäger and Morik, 2017;
Buschjager et al., 2018; Chen et al., 2021), usually a large tool-chain needs
to be employed. However, within the tool-chain, the output of the different
tools need to be sufficiently abstract and generic to serve as inputs for next
tools. Such abstractions also induce possible information loss, causing a
diminished potential for architectural optimization.

In this work, we investigate if a direct implementation generation with fewer
abstraction layers is capable to optimize the execution performance of
decision tree ensembles. With a certain amount of explicitly allocatable
hardware registers, our objective is to manage the register allocation in the
implementation to achieve a performance improvement, by accelerating multiple
accesses to the same value. Towards that, we distinguish native trees, in
which each tree is an array-based implementation of tree nodes, and if-else
trees, in which each tree is a representation of tree nodes with nested if-
else statements. The two variants put stress on different parts of the CPU. A
native tree loads all tree data from data memory and therefore utilizes data
caches, while an if-else tree loads all values from instruction memory,
employing instruction caches. We further propose a third alternative,
implementing a part of the tree as an if-else tree and executing the rest of
the tree as a native tree. This approach could make use of the different
advantages of both variants while leveling the load over the different caches.

Our contributions:

  * •

An implementation of decision trees to store node values in CPU registers for
X86 and ARMv8

  * •

Strategies for choosing which node values to store in registers for native
trees and if-else trees and a hybrid combination of both

  * •

Extensive experimental evaluation of the performance gain on a large set of
ensembles and data sets

##  2\. Related Work

Although training and execution of decision trees are famous on a abstract
level, related work investigates the possibilities to implement decision trees
on hardware. Van Essen et al. compare different ad-hoc realizations across
varying computing architectures, including CPUs, GPUs and FPGAs (Van Essen et
al., 2012). Nakandaka et al. bring decision trees even more specific to
parallel execution architectures, by converting trees into tensor operations
and exploit massive parallelism (Nakandala et al., 2020). As a generic, hence
optimized CPU based implementation, Asadi et al. introduce the popular
approaches of native and if-else tree implementations (Asadi et al., 2014).
Dato et al. optimize decision tree inference by keeping the models itself
untouched, but reorder the execution sequence in the implementation (Dato et
al., 2016). Lucchese et al. further include vectorization into the
implementation in order to accelerate parallel execution of multiple examples
(Lucchese et al., 2016). Different concepts in order to accelerate machine-
specific execution are further proposed. Ye et al. introduce run length
encoding for the tree execution in order to compact the data representation
(Ye et al., 2018). Kim et al. propose a tree implementation, which is
optimized to the memory hierarchy on modern CPUs and GPUs (Kim et al., 2010).
Buschjaeger and Morik consider different realization schemes for tree
traversal and theoretically analyze their execution time, based on a
probabilistic view (Buschjäger and Morik, 2017).

Considering a broader scope beyond decision tree ensembles, C / C++ generators
for other machine learning models (e.g. neural networks) have emerged recently
(David et al., 2020; Warden and Situnayake, 2019). Architecture-aware software
designs also demonstrate their great benefit to speed up the inference of
other machine learning models in the literature, e.g., most for various neural
networks (Ham et al., 2021; Yazdanbakhsh et al., 2018; Huang et al., 2021;
Gobieski et al., 2019; Ren et al., 2019), and some for random forests
(Buschjager et al., 2018; Chen et al., 2021). Although these architecture-
aware approaches exist, to the best of our knowledge, no method exists, which
transforms random forests to platform-specific assembly code by exploiting
hardware features and performing explicit register allocation. Khorasani et
al. perform explicit register management in GPUs (Khorasani et al., 2018),
which is a different approach to explicit CPU register allocation.

##  3\. Decision Tree Models and Implementations

Generally, two implementation types can be distinguished for decision trees:
1) native trees, where tree nodes become data objects and a narrow loop
iterates over them and 2) if-else trees, where tree nodes become nested if-
else blocks and the tree is visited by directly jumping into the if or the
else block (Asadi et al., 2014). In this section, we lay out a logical model
of a decision tree first and afterwards describe how both implementations can
be derived.

###  3.1. Probabilistic Model

We assume decision tree $X$ consist of nodes $\\{n_{0},n_{1},...,n_{m-1}\\}$,
where $n_{0}$ is the root node. Each node has a feature index $FI(n_{i})$, a
split value $S(n_{i})$ and a left and right child index $LC(n_{i}),RC(n_{i})$.
The tree is then visited in such a way, that subsequently after node $i$, node
$n_{j}=\left\\{\begin{array}[]{c|c}LC(n_{i})&input\\_data[FI(n_{i})]\leq
S(n_{i})\\\ RC(n_{i})&input\\_data[FI(n_{i})]>S(n_{i})\end{array}\right.$ is
accessed, where $input\\_data$ is the feature vector to be inferred. Once a
leaf node is reached, it contains a prediction value $P(n_{i})$, which forms
the output of the decision tree.

During training, how many data tuples leading to the left or the right child
can be traced, resulting in a relative probability of the left and right child
node. We denote by $prob(n_{i})$ the probability of node $n_{i}$ to be
accessed from the parent node. Naturally,
$prob(LC(n_{i}))+prob(RC(n_{i}))=100\%$ and $prob(n_{0})=100\%$. Every node in
the tree has a unique access path
$path(n_{i})=\\{pn_{0},pn_{1},...,pn_{j}\\}$, where
$pn_{0}=n_{0},pn_{j}=n_{i}$ and $pn_{k+1}=LC(pn_{k})$ or
$pn_{k+1}=RC(pn_{k})$. With the help of this path, we can define an absolute
node probability $absprob(n_{i})$:

(1) $absprob(n_{i})=\Pi_{pn_{j}\in path(n_{i})}prob(pn_{j})$

This allows to rank nodes of the decision tree according to their probability
to be accesses in the training data-set. We expect a similar distribution of
accesses in a productive test data-set, thus when optimization is applied
according to this node ranking, it is expected to also optimize the tree for
test data.

###  3.2. Tree Implementation

In the realization of native trees every node is stored as a tuple of all its
element, namely the feature index, the split value and the left and right
indices. These values are stored in a data array. The inference is performed
by a small loop over the data array. Starting with the root of the tree as the
current node, the feature value is compared to the split value and depending
on the outcome the next current node will be the left or the right child. This
is repeated until a leaf is reached. At that point the prediction is returned.
This tree realization intensively uses data memory and only allocates a small
footprint of instruction memory. The code, however, is also fixed for all
nodes, which makes it harder to modify single nodes.

In the realization of if-else trees every node becomes a single piece of code.
The nodes then become nested if-else blocks in the inference code. All values
are used as immediates and therefore also stored in instruction memory.
Although this has the clear advantage to utilize fewer data memory and to
provide modified source code for single nodes, the order of nodes in memory
cannot be arbitrarily changed. Child nodes of a certain node must always
appear in the if or in the else branch. Within this realization, feature and
split and prediction are constants, which are assigned at compile time and are
therefore immediately present in the source code.

Both approaches can also be combined, where a set of nodes in an if-else tree
can be realized as a native tree. Within one ensemble, trees can be
arbitrarily implemented as native trees, if-else trees or a combination of
both. To the best of our knowledge, such hybrid realizations have not been
explored in the literature.

##  4\. Problem Analysis

In this work, we present novel implementations of decision trees, where we
utilize available registers to realize a custom caching of decision tree
contents within the CPU registers. Usually, such registers are managed by the
compiler, following ABI conventions. The execution of tree inference, however,
can be realized as a single function in C / C++. The registers, which are not
written or read by compiler-generated code, can be reserved for arbitrary
usage via inline assembly within a function. We explicitly use them in the
generated custom code.

###  4.1. System Model

We assume a generic structure of registers, where a system has a number $\\#R$
of registers. To adapt to general technical limitations, we assume $r<\\#R$ of
them can be arbitrarily used. We assume that we can load memory content into
each of these registers with a corresponding load instruction and can store
contents to memory. We further assume that we can perform the required
arithmetic operations on the registers, which are required for decision tree
inference. This includes comparison of a register value with another register
or with a memory content and succeeding conditional branches. Real systems
usually provide different types of registers, e.g. general purpose registers
(GPR), floating point registers (FLP), vector registers, etc. By keeping track
of the register type, corresponding assembly code can be generated to perform
the aforementioned operations on all types of registers. Since we explicitly
allocate registers during inference, the developed implementations are also
broadly compatible with parallelization on the granularity of trees.

###  4.2. Problem Definition

Given a trained ensemble, consisting of decision trees with profiled
probabilities on the training data set and an amount $r$ of arbitrarily
allocatable registers, the problem is to realize an implementation, which
stores tree contents in the registers without altering the logic tree
structure Data tuples are processed in a batch manner for each decision tree,
by which certain nodes are likely accessed multiple times. If values are
repeatedly accessed, a value from a register can be faster accessed compared
to a value from memory. On the downside, a value in a register blocks this
register for other usage and therefore potentially can slow down the entire
program.

##  5\. Feature Value Storing and Caching

As one approach towards solving the defined problem, we first investigate how
to handle the temporary input data with custom register allocation. In each
run of the ensemble, one input tuple is classified (for inference) utilizing
the decision trees. Depending on the size of the trees and the number of
tuples, some values might be accessed multiple times while following the trees
on one path.

We propose two methods to store the most suitable feature values in registers.
First, a static approach (referenced with _static feature_), where the feature
values of a native tree are loaded into registers before utilizing the tree
and reside in the registers for the duration of following a path in each tree
of the ensemble. Secondly, a dynamic approach (referred to as _dynamic
feature_), in which the feature values are dynamically allocated to registers
in an if-else tree.

###  5.1. Selection Policy

Input tuples potentially have high dimensions, where certain entries may be
accessed more frequently than others. Thus, we propose a metric to select a
subset of the tuple entries to be forced to registers.

(2) $S_{i}=\sum_{j=1}^{depth(tree)}p_{i,j}*j$

Equation 2 determines the suitability of a feature value at index $i$.
$p_{i,j}$ is the probability of the feature value index $i$ to be accessed $j$
times. These probabilities are then added for every possible $j$, being
weighted by $j$ itself. This ensures that the probability of a feature value
being used more often during one single inference is weighted higher. We then
pick the $n$ highest scored values for register storing. These values reside
in the register for the duration of the inference within one function call. To
check whether a feature value is in a register or in memory, the index of the
to access feature value can be compared. The feature value is either loaded
from memory or directly used from a register.

###  5.2. Dynamic Feature Caching

Alternatively, we develop an approach that allows registers to cache feature
values dynamically. This can be utilized in an if-else tree without
significant efforts, because every node in an if-else tree receives its own
distinct code. Suitable access code to a certain register can be directly
integrated. To fully use this attribute, we dynamically cache the feature
values inside the registers during run time. The feature values are loaded
into registers when being used first. If it is already in a register, it can
be used directly from the register itself. In case there are no spare
registers for storing, the oldest cached value is replaced accordingly.
Although this type of register management introduces large overheads, they are
all present during code generation. Once the tree is constructed, the register
caching allocation can be statically defined, and the corresponding code is
directly generated into the if-else blocks.

##  6\. Node Storing

Besides storing feature values in registers, we investigate an alternative
approach where nodes of the tree data structure are stored in registers. To
select the nodes to be stored in registers, we order tree nodes along their
absolute access probability $absprob(n_{i})$ and select the first $r$ nodes.
To improve the performance, the part of the tree loaded into registers is kept
in registers when the tree is visited multiple times.

###  6.1. Realization of Register Cached Nodes

Implementing the whole tree as a native tree and accessing the correct values
using a comparison chain is the first version, proposed in this paper (_native
node_): Every time a new node is accessed, a comparison with the current index
is performed to determine the location of the node values. These are then
either loaded from the corresponding register or loaded from memory. We
further proposed another approach where the nodes picked for register storage
are implemented and visited as nodes from an if-else subtree (we refer to such
nodes as if-else nodes) within the native tree. Here, two different subsets of
the tree can be implemented as if-else nodes. Firstly, implementing the first
layer nodes (_hybrid layer_) and secondly implementing the most probable nodes
(_hybrid node_) as if-else nodes. Ultimately, the full tree can be implemented
as an if-else tree with the most probable nodes stored in registers. We call
this approach the _if-else node_ method. Consequently, the data in the nodes,
which are stored in a register, is used directly, omitting the need to load
this value from instruction memory.

###  6.2. Tree Construction and Inference

Registers have limited space, so not all node values should be stored, but
only the ones necessary for inference. The most important value in a node is
the split value. It is used to compare with the feature value. As such, it is
used in every node except leaf nodes. If the split value does not fill the
register completely, more values can be stored. Three values are of key
interest here: left, right child indices and the feature index. Depending on
the size of the register, not all can be stored at once. Different
realizations are possible. If the node is executed as part of a native subtree
(referenced by native node), the indices for the left and right children are
required to load the new node. Therefore, left and right child indices are
loaded into the register. In some situations, left and right child indices are
not needed. If the children are implemented as an if-else nodes, the indices
of the children are superfluous. In these situations, the rest of the register
is filled with the feature index. When implementing the _hybrid node_ method,
some nodes may have one child as an if-else node and another one as a native
node. In these situations, the index of the child implemented as a native node
and the feature index can both be loaded into the the register. To access the
nodes in registers, different implementations are required for native nodes
and if-else nodes. In native trees, the individual nodes are identified by
their index. To access the node data inside registers, comparisons with the
index of the current node determines, where to load the data from. No further
implementation is needed for if-else nodes, as each node receives separate
code accessing the node data.

##  7\. Evaluation

Figure 1. Native tree methods on X86 for server class (top) and desktop class
(down) - 100 Trees with max. depth 15

To assess the improvement in terms of execution time of the proposed methods,
extensive tests are run on different hardware and multiple kinds of trees: 9
data-sets under 6 proposed methods. The data-sets (adult, bank, covertype,
letter, magic, satlog, sensorless-drive, spambase and wine-quality) are taken
from the UCI Machine Learning Repository (Dua and Graff, 2017) and trained
using sklearn. Analyzing the effect the depth of the tree can have on the
performance, experiments are run with a single decision tree and a random
forest with 25 trees, using a maximum depth of 5, 10, 15 and 20. Further, the
experiments are also run with a random forest with maximum depth 15 and using
different numbers of trees: 10, 25, 50 and 100. To serve as a baseline, all
configurations are run once with a basic C++ implementation of both a native
tree and an if-else tree. All experiments are compiled with gcc on default
settings.

These experiments are run on both server and desktop class CPUs using the X86
and ARMv8 architecture. For the X86 machines, we use an AMD EPYC 7742 system
(256GB DDR4 RAM) for the server and an Intel Core I7-8550U system (16GB DDR4
RAM) for the desktop. For the ARMv8 machines, we use a Cavium Thunder X2
system (256GB DDR4 RAM) for the server and an Apple M1 system (16GB DDR4 RAM)
for the desktop. The X86 systems feature 16 general purpose registers with 64
bit and 16 floating point registers with 128 bit, while the ARMv8 systems
feature 32 general purpose 64 bit registers and 32 64 bit floating point
registers, respectively.

###  7.1. Native Tree Modifications

Our proposed methods can be roughly categorized into methods modifying native
trees (_hybrid node_ (HN), _hybrid layer_ (HL), _native node_ (NN)) and into
methods modifying if-else trees (_if-else node_ (IN) and _dynamic feature_
(DF)). Please note that the _hybrid layer_ and _hybrid node_ methods implement
native trees for the major part, though they introduce partial if-else trees,
resulting in hybrid trees.

Focusing on the native tree methods, Figure 1 depicts normalized results to
the basic native tree implementation on the X86 machine. We run all
experiments in a row and normalize the execution time of the various methods
to the basic baseline. We print the number of elements allocated in registers
on the x axis and the normalized execution time (larger than 1 means slower
than the baseline) on the y axis. We consider all data-sets and print the
average as a point together with the variance. Every plot depicts a concrete
ensemble configuration with a fixed number of trees and a limited maximal
height of the trees. Note that for the _hybrid layer_ method registers can be
only allocated in numbers of powers of 2, since entire tree layers are
allocated to registers. The figures illustrate only one particular ensemble
configuration for a maximum tree depth of 15 and an ensemble of 100 trees on
the X86 machine and 50 on the ARMv8 machine, where effects of the different
methods can be observed. Effects on the execution time across all ensemble
sizes can be observed in the reported geometric means of normalized execution
time for both all depths and small trees (limited depth up to $10$) and large
trees (limited depth above $10$) separately (Table 1).

Table 1. Geometric mean of normalized execution time, compared to native and if-else for small ($D\leq 10$) and large ($D>10$) trees (-S: Server, -D: Desktop, s: small, l: large) Method | X86-S | X86-D | ARM-v8-S | ARM-v8-D
---|---|---|---|---
| native baseline
NN | $0.86$ | $0.87$ | $1.29$ | $1.00$
ST | $1.04$ | $1.19$ | $1.22$ | $0.88$
HN | 0.71 | $0.71$ | $0.74$ | $0.62$
HL | 0.74 | $0.74$ | $0.82$ | $0.66$
| s | l | s | l | s | l | s | l
NN | $0.86$ | $0.85$ | $1.32$ | $1.01$ | $0.86$ | $0.88$ | $1.27$ | $9.99$
SF | $0.99$ | $1.03$ | $1.07$ | $0.82$ | $1.07$ | $1.30$ | $1.32$ | $0.92$
HN | 0.66 | $0.62$ | $0.63$ | $0.54$ | 0.75 | $0.77$ | $0.81$ | $0.66$
HL | 0.68 | $0.66$ | $0.72$ | $0.57$ | 0.78 | $0.79$ | $0.88$ | $0.72$
| if-else baseline
IN | $0.95$ | $0.96$ | $1.06$ | $0.99$
DF | $0.91$ | $0.92$ | $1.04$ | $0.88$
HN | 1.77 | $2.00$ | $1.66$ | $1.75$
HL | 1.84 | $2.08$ | $1.84$ | $1.87$
| s | l | s | l | s | l | s | l
IN | $0.94$ | $0.96$ | $1.06$ | $0.93$ | $0.95$ | $0.95$ | $1.06$ | $1.03$
DF | $0.92$ | $0.94$ | $1.07$ | $0.81$ | $0.90$ | $0.91$ | $1.02$ | $0.92$
HN | 1.47 | $1.65$ | $1.43$ | $1.36$ | 1.97 | $2.23$ | $1.81$ | $2.03$
HL | 1.52 | $1.75$ | $1.63$ | $1.41$ | 2.06 | $2.29$ | $1.97$ | $2.20$

It can be observed that the _static feature_ method cannot improve the
performance in most configurations among the basic native tree. The overheads,
introduced to distinguish if a feature value should be loaded from a register
or memory overshoots the improvement in the access latency. The _native node_
method can be observed to behave different on both CPU architectures. On X86,
this method can reduce the total execution time to $\approx 85\%$ of the basic
native tree, which makes a speedup of $\approx 1.17\times$. On the ARMv8
server contrarily, this method diminishes the performance overall while it
also features no significant improvement on the ARMv8 desktop. This suggests
the conclusion that the efficiency of the comparison chain is architecture
dependent and thus, this method should be considered depending on the
architecture. These trends are also consistent with considering the geometric
mean across ensembles sizes, data-sets, register sizes $r\geq 5$ and storing
full nodes or only split values. These values can be found in table 1. The
_static feature_ reports an average increase of $1.11\times$ on X86, an
increase of $1.22\times$ on the ARMv8 server and actually decreases to
$0.88\times$ on the ARMv8 desktop. Examining the _native node_ method, the
explained results of a measurable performance improvement on X86 can be seen.
On the ARMv8 desktop, the performance stays roughly the same.

The _hybrid layer_ and _hybrid node_ methods both achieve significant
execution time improvements on both machines for a sufficient number of
available registers, even up to a reduction to $\approx 60\%$ of the basic
tree, which is a speedup of $\approx 1.66\times$. As before Table 1 shows the
explained geometric mean across all data-sets. A significant improvement of
the execution time can be observed for all considered systems. According to
Table 1 it can be further observed, that most methods perform better on
smaller trees than on larger trees. This can be caused by the fact that more
values can reside in registers during repetitive inference on smaller trees.

Investigating these results, we report that careful attention has to be put to
the setup, when explicit register management is used to improve the
performance of native tree ensembles. Not only a wrong approach can diminish
the overall performance, depending on the CPU architecture various approaches
can result in different speedups. However, insights from this evaluation can
be used to chose appropriate methods for a certain CPU architecture (e.g. the
_hybrid node_ method for a large amount of allocated registers) and reduce the
total execution time for inference down to $\approx 58\%$ of the basic method.
It can also be reported that this improvement can be gained for a sufficient
number of available registers and is not linearly scaling down for more
available registers.

###  7.2. If-Else Tree Modifications

Figure 2. If-else tree methods on X86 for server class (top) and desktop class
(down) - 25 Trees with maximum depth 5

The proposed methods implementing if-else trees are _dynamic feature_ , where
nodes are stored in registers during inference in a cache wise manner and _if-
else node_ , with nodes stored in registers statically. LABEL:fig:ielse86
illustrates the same ensemble size as before for the if-else tree methods.
Thus, the reported numbers are also normalized to the basic if-else tree
implementation. We further investigate the _hybrid node_ and _hybrid layer_
method in comparison to basic if-else trees, since these methods partially
implement if-else trees.

Investigating this case, highlights that the performance of the _hybrid node_
method introduces larger overheads in comparison to a native if-else tree,
which cannot be leveraged by the performance benefit. The same trend can be
observed for the _hybrid layer_ method. Consequently, the _hybrid node_ and
_hybrid layer_ method offer a trade-off between native trees and if-else
trees, but cannot outperform if-else trees. The _if-else node_ and _dynamic
feature_ method can improve the performance down to $70\%$ of the basic if-
else tree, but only for a particular system and ensemble configuration.

Considering the geometric means across all configurations and datasets (Table
1), on X86, it reports to a decrease of $0.86\times$ for the if-else tree
registers method on the server and $0.87\times$ on the desktop and of
$0.91\times$ (server) and $0.91\times$ (desktop) for the _dynamic feature_
method, compared to the basic if-else tree. On the ARMv8 server, the increase
reports as $1.06\times$ for the _if-else node_ method and $1.04\times$ for the
_dynamic feature_ method, respectively. On the ARMv8 desktop, performance is
decreased to $0.99\times$ for the _if-else node_ method and $0.88\times$ for
the _dynamic feature_ method. The _hybrid node_ and _hybrid layer_ methods
report a consistent increase of execution time. These results conclude that,
explicit register allocation can significantly improve performance, but it is
highly dependent on the system architecture and the ensemble configuration. If
a wrong method is deployed, performance can be drastically decreased.

Overall, for the considered data sets, CPU architectures and ensemble
configurations, the _hybrid node_ method achieves the best performance for
native trees, while the _dynamic feature_ method and the _if-else node_ method
achieve the best performance for if-else trees. The results further suggest
choosing these methods with a sufficient amount of registers. For the native
trees, the results show a number of $\approx 20$ registers to be a good
choice, while for if-else trees fewer registers ($\approx 10$) report to be
sufficient.

##  8\. Conclusion and Outlook

In this paper, we present an approach to generic and platform independent
tool-chains for decision tree ensemble implementations, where we directly
generate machine specific assembly code from the high-level model
representation. Thereby, we explicitly take over the control of the allocation
of CPU registers and allocate certain decision tree nodes permanently to a
register. We do this for both, native trees and if-else trees. Experimental
evaluation clearly points out that explicit register allocation does not
unconditionally improve the performance of decision tree inference, but with
careful attention to the scenario, significant performance improvement can be
achieved. If the right method is applied to the right scenario, the execution
times of native trees can be decreased down to $0.58\times$ and the execution
time of if-else trees down to $0.7\times$, respectively.

For future work, we plan to expand the scope of explicit register allocation
to the entire ensemble. Scheduling the execution of multiple trees may open a
huge design space for further optimization.

## Acknowledgement

This paper has been supported by Deutsche Forschungsgemeinshaft (DFG), as part
of the projects OneMemory (405422836), SPP 2377: Disruptive Main-Memory
Technologies (460954224), and Memory Diplomat (502384507).

## References

  * (1)
  * Asadi et al. (2014) N. Asadi, J. Lin, and A. P. de Vries. 2014.  Runtime Optimizations for Tree-Based Machine Learning Models.  _IEEE Transactions on Knowledge and Data Engineering_ 26, 9 (Sept 2014), 2281–2292.  https://doi.org/10.1109/TKDE.2013.73
  * Buschjager et al. (2018) Sebastian Buschjager, Kuan-Hsun Chen, Jian-Jia Chen, and Katharina Morik. 2018.  Realization of random forest for real-time evaluation through tree framing. In _2018 IEEE International Conference on Data Mining (ICDM)_. IEEE, 19–28.
  * Buschjäger and Morik (2017) S. Buschjäger and K. Morik. 2017.  Decision Tree and Random Forest Implementations for Fast Filtering of Sensor Data.  _IEEE Transactions on Circuits and Systems I: Regular Papers_ PP, 99 (2017), 1–14.  https://doi.org/10.1109/TCSI.2017.2710627
  * Buss et al. (2016) Jens Buss, Christian Bockermann, Katharina Morik, Wolfgang Rhode, and Tim Ruhe. 2016.  FACT-Tools – Processing High-Volume Telescope Data. In _26th Astronomical Data Analysis Software and Systems conference (ADASS)_.  ADASS.
  * Chen et al. (2021) Kuan-Hsun Chen, ChiaHui Su, Christian Hakert, Sebastian Buschjäger, Chao-Lin Lee, Jenq-Kuen Lee, Katharina Morik, and Jian-Jia Chen. 2021.  Efficient Realization of Decision Trees for Real-Time Inference.  _ACM Trans. Embed. Comput. Syst._ (dec 2021).  https://doi.org/10.1145/3508019 Just Accepted.
  * Dato et al. (2016) Domenico Dato, Claudio Lucchese, Franco Maria Nardini, Salvatore Orlando, Raffaele Perego, Nicola Tonellotto, and Rossano Venturini. 2016\.  Fast ranking with additive ensembles of oblivious and non-oblivious regression trees.  _ACM Transactions on Information Systems_ (2016).  https://doi.org/10.1145/2987380
  * David et al. (2020) Robert David, Jared Duke, Advait Jain, Vijay Janapa Reddi, Nat Jeffries, Jian Li, Nick Kreeger, Ian Nappier, Meghna Natraj, Shlomi Regev, et al. 2020\.  Tensorflow lite micro: Embedded machine learning on tinyml systems.  _arXiv preprint arXiv:2010.08678_ (2020).
  * Dua and Graff (2017) Dheeru Dua and Casey Graff. 2017.  UCI Machine Learning Repository.  http://archive.ics.uci.edu/ml
  * Gobieski et al. (2019) Graham Gobieski, Brandon Lucia, and Nathan Beckmann. 2019\.  Intelligence Beyond the Edge: Inference on Intermittent Embedded Systems. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ (Providence, RI, USA) _(ASPLOS ’19)_. Association for Computing Machinery, New York, NY, USA, 199–213.  https://doi.org/10.1145/3297858.3304011
  * Ham et al. (2021) Tae Jun Ham, Yejin Lee, Seong Hoon Seo, Soosung Kim, Hyunji Choi, Sung Jun Jung, and Jae W. Lee. 2021.  ELSA: Hardware-Software Co-design for Efficient, Lightweight Self-Attention Mechanism in Neural Networks. In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. 692–705.  https://doi.org/10.1109/ISCA52012.2021.00060
  * Huang et al. (2021) Jiayi Huang, Pritam Majumder, Sungkeun Kim, Abdullah Muzahid, Ki Hwan Yum, and Eun Jung Kim. 2021.  Communication Algorithm-Architecture Co-Design for Distributed Deep Learning. In _2021 ACM/IEEE 48th Annual International Symposium on Computer Architecture (ISCA)_. 181–194.  https://doi.org/10.1109/ISCA52012.2021.00023
  * Khorasani et al. (2018) Farzad Khorasani, Hodjat Asghari Esfeden, Nael Abu-Ghazaleh, and Vivek Sarkar. 2018\.  In-register parameter caching for dynamic neural nets with virtual persistent processor specialization. In _2018 51st Annual IEEE/ACM International Symposium on Microarchitecture (MICRO)_. IEEE, 377–389.
  * Kim et al. (2010) C. Kim, J. Chhugani, N. Satish, E. Sedlar, A. Nguyen, T. Kaldewey, V. Lee, S. Brandt, and P. Dubey. 2010\.  FAST: Fast architecture sensitive tree search on modern CPUs and GPUs. In _Proceedings of the 2010 ACM SIGMOD International Conference on Management of data_. ACM, 339–350.
  * Lucchese et al. (2016) Claudio Lucchese, Raffaele Perego, Franco Maria Nardini, Nicola Tonellotto, Salvatore Orlando, and Rossano Venturini. 2016.  Exploiting CPU SIMD extensions to speed-up document scoring with tree ensembles. In _SIGIR 2016 - Proceedings of the 39th International ACM SIGIR Conference on Research and Development in Information Retrieval_.  https://doi.org/10.1145/2911451.2914758
  * Nakandala et al. (2020) Supun Nakandala, Karla Saur, Gyeong-In Yu, Konstantinos Karanasos, Carlo Curino, Markus Weimer, and Matteo Interlandi. 2020.  A tensor compiler for unified machine learning prediction serving. In _14th USENIX Symposium on Operating Systems Design and Implementation (OSDI 20)_. 899–917.
  * Pedregosa et al. (2011) F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ 12 (2011), 2825–2830.
  * Pereira et al. (2017) Rui Pereira, Marco Couto, Francisco Ribeiro, Rui Rua, Jácome Cunha, João Paulo Fernandes, and João Saraiva. 2017\.  Energy Efficiency across Programming Languages: How Do Energy, Time, and Memory Relate?. In _Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering_ (Vancouver, BC, Canada) _(SLE 2017)_. Association for Computing Machinery, New York, NY, USA, 256–267.  https://doi.org/10.1145/3136014.3136031
  * Ren et al. (2019) Ao Ren, Tianyun Zhang, Shaokai Ye, Jiayu Li, Wenyao Xu, Xuehai Qian, Xue Lin, and Yanzhi Wang. 2019\.  ADMM-NN: An Algorithm-Hardware Co-Design Framework of DNNs Using Alternating Direction Methods of Multipliers. In _Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems_ (Providence, RI, USA) _(ASPLOS ’19)_. Association for Computing Machinery, New York, NY, USA, 925–938.  https://doi.org/10.1145/3297858.3304076
  * Van Essen et al. (2012) B. Van Essen, C. Macaraeg, M. Gokhale, and R. Prenger. 2012\.  Accelerating a random forest classifier: Multi-core, GP-GPU, or FPGA?. In _Field-Programmable Custom Computing Machines (FCCM), 2012 IEEE 20th Annual International Symposium on_. IEEE, 232–239.
  * Warden and Situnayake (2019) Pete Warden and Daniel Situnayake. 2019.  _TinyML_.  O’Reilly Media, Incorporated.
  * Yayla et al. (2019) Mikail Yayla, Anas Toma, Kuan-Hsun Chen, Jan Eric Lenssen, Victoria Shpacovitch, Roland Hergenröder, Frank Weichert, and Jian-Jia Chen. 2019.  Nanoparticle Classification Using Frequency Domain Analysis on Resource-Limited Platforms.  _Sensors_ 19, 19 (2019).  https://doi.org/10.3390/s19194138
  * Yazdanbakhsh et al. (2018) Amir Yazdanbakhsh, Kambiz Samadi, Nam Sung Kim, and Hadi Esmaeilzadeh. 2018.  GANAX: A Unified MIMD-SIMD Acceleration for Generative Adversarial Networks. In _2018 ACM/IEEE 45th Annual International Symposium on Computer Architecture (ISCA)_. 650–661.  https://doi.org/10.1109/ISCA.2018.00060
  * Ye et al. (2018) Ting Ye, Hucheng Zhou, Will Y. Zou, Bin Gao, and Ruofei Zhang. 2018.  RapidScorer: Fast tree ensemble evaluation by maximizing compactness in data level parallelization. In _Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.  https://doi.org/10.1145/3219819.3219857


11institutetext: Kyoto University, Kyoto, Japan
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
22institutetext: Fujitsu Research, Fujitsu Ltd., Kanagawa, Japan
22email: $\\{$t.arseny,tyamamo,okajima.seiji,
<EMAIL_ADDRESS>
# Crowdsourcing Evaluation of Saliency-based
XAI Methods

Xiaotian Lu ✉ 11 0000-0002-4118-2301 Arseny Tolmachev 22 Tatsuya Yamamoto 22
Koh Takeuchi 11 Seiji Okajima 22 Tomoyoshi Takebayashi 22
Koji Maruhashi 22 Hisashi Kashima 11

###### Abstract

Understanding the reasons behind the predictions made by deep neural networks
is critical for gaining human trust in many important applications, which is
reflected in the increasing demand for explainability in AI (XAI) in recent
years. Saliency-based feature attribution methods, which highlight important
parts of images that contribute to decisions by classifiers, are often used as
XAI methods, especially in the field of computer vision. In order to compare
various saliency-based XAI methods quantitatively, several approaches for
automated evaluation schemes have been proposed; however, there is no
guarantee that such automated evaluation metrics correctly evaluate
explainability, and a high rating by an automated evaluation scheme does not
necessarily mean a high explainability for humans. In this study, instead of
the automated evaluation, we propose a new human-based evaluation scheme using
crowdsourcing to evaluate XAI methods. Our method is inspired by a human
computation game, ”Peek-a-boom”, and can efficiently compare different XAI
methods by exploiting the power of crowds. We evaluate the saliency maps of
various XAI methods on two datasets with automated and crowd-based evaluation
schemes. Our experiments show that the result of our crowd-based evaluation
scheme is different from those of automated evaluation schemes. In addition,
we regard the crowd-based evaluation results as ground truths and provide a
quantitative performance measure to compare different automated evaluation
schemes. We also discuss the impact of crowd workers on the results and show
that the varying ability of crowd workers does not significantly impact the
results.

###### Keywords:

Explainable AI Interpretability Evaluation Crowdsourcing

##  1 Introduction

Recent significant advances in AI technologies have introduced innovations in
various fields. In particular, deep neural networks (DNNs) exhibit remarkable
performance in a wide range of real-world applications, such as natural
language processing [8, 27], image classification [16, 7, 29, 6], and human
action recognition [15, 19]. DNNs can extract intricate underlying patterns
from large and high-dimensional datasets and have reduced the demand for
feature engineering. However, the internal mechanism of DNNs is a black box,
i.e., it is difficult to understand the relationships between their inputs and
outputs. In low-risk environments, errors made by DNNs do not have severe
impacts; for example, in movie recommendation systems, the impact of making a
recommendation error is relatively low. However, in other fields such as
healthcare, a single misdiagnosis can be fatal; therefore, it is essential to
explain the predictions. In regulated industries such as the judicial system
and financial markets, a mandate for explanations in addition to model
predictions is emerging in legal norms. However, most current DNN models are
opaque and provide no information about their decision-making process, which
has been a significant obstacle to the implementation of AI in essential
applications. Understanding the reasons behind their predictions is critical
for gaining human trust in many important applications [22], which is
reflected in the increasing demand for explainability in AI (XAI) in recent
years.

To satisfy the requirements of XAI, various explanation and interpretation
methods have emerged, especially for black-box predictions made by already-
trained neural networks. One of the major approaches to this problem involves
the estimation of the influence of a subset of input features on the
predictions of a model. By understanding the important features, the model can
be improved, model predictions can be trusted, and undesirable behaviors can
be isolated [12]. For example, in image classification tasks, the generation
of saliency maps, which assign an importance measure for each part (or pixel)
of an input image, is a major research direction; the representative methods
include Vanilla Gradients [3, 10, 25], SmoothGrad [26], Guided-Backpropagation
[28], and Grad-CAM [24, 30] (Figure 1).

(a) Original image

(b) Vanilla Gradients

(c) SmoothGrad

(d) Guided-Backpropagation

(e) Grad-CAM

Figure 1:  Different saliency maps produced by different XAI methods. The
bright areas indicate important areas.

While various XAI methods have been proposed, their evaluation strategy has
not been established well, and there is an urgent demand for quantitative
measures to answer the question “Given several XAI methods of a black-box
prediction model, which one yields the best interpretations?” Several
automated evaluation schemes have been proposed [12, 23, 21]; they usually
delete or replace pixels that are said important by an XAI method, and check
the deterioration in the prediction performance. However, as pointed out by a
recent research [20], high interpretability for machines does not imply the
same for humans. A machine may recognize an object based on its relation to
the background rather than the object itself. For example, the background of
an image of an airplane is often the sky. This is a reasonable strategy for
machines to make decisions based on statistical information, but it is
probably different from how humans recognize objects. After all,
interpretability for humans can ultimately only be evaluated by humans.

(a) Exposure rate of 5% (b) Exposure rate of 10%

(c) Exposure rate of 15% (d) Exposure rate of 30%

Figure 2:  Example of how the proposed evaluation interface gradually reveals
an image to crowd workers at different exposure rates (5%. 10%, 15%, and 30%).

In this study, we perform human-based evaluation of XAI methods by using
crowdsourcing. Our XAI evaluation approach is based on a human computation
game. In human computation [18], some approaches embed human intelligence
tasks into games, usually referred to as game with a purpose (GWAP). Peek-a-
boom is a type of GWAP with two players named Peek and Boom; Boom reveals a
part of a given image and Peek guesses the image object from the revealed
part. We use a Peek-a-boom-based XAI evaluation in which a human plays the
Peek, and an XAI method plays the Boom instead of another human.

We implement a crowd-based evaluation interface (Figure 2)111Our crowdsourcing
evaluation interface can be tried at
https://17bit.github.io/crowddemo/index.html ., recruit crowd workers for
executing evaluation tasks of four popular XAI methods on two real datasets,
and compare the results with those by four automated evaluation schemes.

The results show that the proposed scheme gives different evaluations from the
automated evaluation schemes. Subsequently, We consider the proposed crowd-
based scheme as ground truths and evaluate the automated evaluation schemes in
terms of interpretability for humans. Finally, we analyze the ability of crowd
workers and find that, even if their ability may vary considerably, the final
results are not significantly affected.

The contributions of this study are summarized as follows:
1) We propose a new crowd-based evaluation scheme for XAI methods.
2) We experimentally investigate the difference between automated and crowd-
based evaluation schemes.
3) We provide a performance measure for automated evaluation schemes based on
their similarity to the proposed crowd-based evaluation scheme.
4) We examine the impact of the number and ability of crowd workers on the
results.

##  2 Related Work

We briefly review the XAI methods used in this study, automated evaluation
schemes that can automatically evaluate the XAI methods, and existing crowd-
based evaluation schemes.

###  2.1 XAI methods

Most of the existing XAI methods attribute the output of a pre-trained neural
network to a part of its input. For a multi-class classification problem with
$C$ classes, let $f:\mathbb{R}^{D}\to\mathbb{R}^{C}$ be a pre-trained neural
network which takes an input feature vector $x\in\mathbb{R}^{D}$ and output a
vector representing the degree of classification into each class. A typical
XAI method provides a saliency map $s:\mathbb{R}^{D}\to\mathbb{R}^{D}$ that
maps an input feature vector to a vector whose $d$-th element indicates the
importance of the $d$-th feature of input $x$ [1].

Vanilla gradient [3, 10, 25] is the most basic method to create a saliency map
as $s^{\text{Vanilla}}(x)=\frac{\partial f}{\partial x}$, which quantifies the
influence of a small change in each input dimension on the output of the
network. One of the drawbacks of this method is that the results are sensitive
to the noise in the original image (Figure 1b).

SmoothGrad [26] is an improved version of the vanilla gradient which estimates
the gradient more robustly. It takes the average of the vanilla gradient over
perturbed inputs,
$s^{\text{Smooth}}(x)=\frac{1}{N}\sum_{i=1}^{N}s^{\text{Vanilla}}(x+\Delta_{i})$,
where the perturbation of the input $\Delta_{i}$ is sampled by a Gaussian
distribution, which results in clearer saliency maps than the vanilla gradient
(Figure 1c).

Guided-Backpropagation [28] gives the contribution of an input dimension of a
neuron to the output by distributing the output back to the input. For better
interpretability, it back-propagates the output of “active” ReLU units, which
highlights important edges in images (Figure 1d).

Grad-CAM [24] focuses on the last convolution layer of a CNN (Convolutional
Neural Network) and visualizes the globally-average-pooled gradients In
contrast with the previously mentioned XAI methods, only Grad-CAM relies on
both gradients and feature maps of the convolutional layer. The results focus
more on important “areas” rather than edges as shown in Figure 1e. A recent
research shows that these saliency maps based on only the gradients will not
change greatly even if the parameters of DNN model are randomized [1].
However, saliency map of GradCAM is different from saliency maps based on
gradients. Our experiments also show that GradCAM performs the best in our
crowd-based evaluation scheme.

###  2.2 Automated evaluation schemes for XAI methods

Most automated evaluation schemes work by modifying (either train or test)
data, and compare the differences in the prediction performance of models.
Hooker et al. [12] proposed several automated evaluation schemes for XAI
methods. In their studies, they argued that by removing data features from the
training set, better evaluation robustness can be archived in comparison to
schemes that modify the test set.

In the Remove and Retrain (ROAR) scheme, the top-ranked pixels given by XAI
methods are removed from the images in the training dataset, a new model is
trained on the modified training set, and the resulting model is evaluated on
the non-modified test dataset. The ROAR scheme was mainly compared to the Keep
and Retrain (KAR) scheme, in which the bottom-ranked pixels were removed from
the training set. It should be noted that Hooker et al. did not perform
comparisons to crowd-based evaluation schemes.

In our experiments (Section 4), we also test two schemes that change the test
set while leaving the training set unchanged, namely, Remove and Evaluate
(ROAE) and Keep and Evaluate (KAE) [23, 21]. Table 1 summarizes the comparison
between the automated evaluation schemes.

Table 1: Dataset split modification of automated evaluation schemes. “top” indicates that the top-ranked pixels are modified first, “bottom” implies that the bottom-ranked pixels are removed first, and ‘-’ means that the dataset split is used without modification.  XAI method |  test set |  training set
---|---|---
ROAR [12] | - | top
KAR [12] | - | bottom
ROAE [23, 21] | top | -
KAE [23, 21] | bottom | -

###  2.3 Crowd-based evaluation schemes for XAI methods

Several crowd-based evaluation schemes have been proposed to measure the
ability of XAI methods. Hutton et al. [13] used crowdsourcing to assess the
explanations for supervised text classification. Crowd workers were asked to
compare human-generated and XAI method-generated explanations and indicate
which they preferred and why. Selvaraju et al. [24] and Jeyakumar et al. [14]
asked crowd workers to choose better explanations directly. Similarly, Can et
al. [5] asked crowd workers to rate the saliency maps of Grad-CAM on the
visual characteristics of venues.

Doshi-Velez and Kim [9] concluded that there are three different types of
crowd-based evaluation schemes: 1) binary forced choices in which humans are
presented with pairs of explanations and choose better ones, 2) forward
simulation/prediction in which humans are presented with an explanation and an
input, and simulate the output of the model, and 3) counterfactual simulation
in which humans are presented with an explanation, an input, and an output,
and tell what must be changed to change the prediction to a desired output.

Our proposed scheme is similar to none of the aforementioned schemes. We do
not directly show the saliency maps to workers nor force them to make a binary
choice; instead, we transform into a simpler task, which makes it easier for
workers to make objective choices that are less dependent on subjective
judgments of workers.

##  3 Proposed crowd-based evaluation scheme for XAI methods

We propose a crowd-based evaluation scheme for XAI methods based on Peek-a-
boom [2] which is an online human computation game as shown in Figure 3. As
suggested by the name, this cooperative game has two players, namely, ”Peek”
and ”Boom.”

Peek starts with a blank screen, while Boom starts with an image and a word
related to it. At each round of the game, Boom can specify a small area in the
image and reveals the area to Peek, and Peek enters a guess of the word on the
basis of the revealed parts. The both players get more points when Peek
correctly answers the word earlier; therefore, Boom has an incentive to reveal
only the areas of the image necessary for Peek to guess the correct word.

We use a Peek-a-boom style Web interface, in which a crowd worker plays the
Peek, and an XAI method plays the Boom instead of another human. In the web
interface, crowd workers are asked to perform an image classification task,
i.e., assigning a label to an image from a set of labels. First, we reveal a
small percentage of image pixels with an option to reveal more if it is
impossible to assign a label with confidence. We show a correct label, several
randomly selected wrong labels, and an “I don’t know” button. If the worker
cannot provide a confident answer, they can select “I don’t know”; then, more
parts of the image will be revealed. In the case of an incorrect answer, more
parts will be revealed as well. Once the worker selects the right answer, or
“I don’t know” is selected with a fully-shown image, we give the worker a new
image. For a given image, XAI methods rank the pixels in descending order of
their importance. For each crowd worker, our crowdsourcing interface starts
from an almost blank image (i.e., exposure rate $=0.05$); gradually, the
pixels are revealed in order of importance (i.e., increase the exposure rate)
(Figure 2). At each exposure rate $r\in[0,1]$, the crowd worker is asked to
guess the object in the image, typically in terms of multiple-choice
questions. We consider that if an XAI method is ”interpretable” enough, the
crowd worker can correctly answer the question at a small exposure rate $r$.

Specifically, the evaluation procedure consists of the following steps: 1)
Prepare a pre-trained prediction model, a dataset, and several XAI methods to
be evaluated.
2) Apply all XAI methods and a random baseline to each image.
3) Get a saliency map from each XAI method and the random baseline.
4) A series of images with a part of top importance pixel features are
generated from the saliency map (Figure 4).
5) Start with the smallest percentage of pixels (e.g., 5%) and ask the crowd
workers about the class of object. If they do not know, show more pixels and
record the percentage of images when the worker answers correctly.

Figure 3:  Interface of Peek-a-boom human computation game [2]. Peek sees the left screen, and Boom sees the right one. Boom determines which parts are exposed to Peek so that Peek correctly guess the image content (that is a cow in this example.)  |  Exposure Rate
---|---
| 5% | 10% | 15% | 20% | 30% | 50% | 75%
Grad-CAM |  |  |  |  |  |  |
Guided-BP |  |  |  |  |  |  |
SmoothGrad |  |  |  |  |  |  |
VanillaGrad |  |  |  |  |  |  |
Random |  |  |  |  |  |  |
Figure 4:  “Explanations” for a cat image provided by five XAI methods (Grad-
CAM, Guided-BP, SmoothGrad, VanillaGrad, and Random) at different exposure
rates (5%, 10%, 15%, 20%, 30%, 50%, and 75%).

##  4 Results

We conduct experiments to answer the following four questions:
Q1. Are human and automated evaluations really different?
Q2. Which XAI methods are deemed better by humans?
Q3. Which automated evaluation scheme is closer to humans?
Q4. How does the number and ability of crowd evaluators affect the evaluation
results?

###  4.1 Experimental settings

We use two datasets for the evaluation; namely, Food101 [4] and Animal95.
Animal95 is a subset of OpenImages v6 dataset [17]. We use bounding box data
to filter the dataset to extract object areas. Subsequently, we select only
images with either single animals or multiple animals of the same class.
Images with multiple classes (multiple types of animals) are not included, but
those with several animals of a single class (e.g., three dogs) or non-animal
classes are included.

We shortlist the 30 most common food classes from all the classes in Food101,
and randomly select ten images in each class. Similarly, we select 95 most
frequent animals from OpenImages for the Animal95 dataset.

The XAI methods used in our experiments include GradCAM, Guided-
backpropagation, SmoothGrad, and Vanilla Gradient. We implement the four XAI
methods as well as the random baseline with a pre-trained ResNet50 model [11].
In total, 1500 pairs and 4750 of (image, XAI method) are generated for Food101
and Animal95, respectively222$30\text{ classes}\times 10\text{ images}\times
5\text{ XAI methods}=1500$ for Food101, and $95\text{ classes}\times 10\text{
images}\times 5\text{ XAI methods}=4750$ for Animal95..

We use Amazon Mechanical Turk (AMT)333https://www.mturk.com/ and
Lancers444https://www.lancers.jp/ as the crowdsourcing platforms for crowd-
based evaluation. Each (image, XAI method)-pair is evaluated ten times. Each
crowd worker is required to evaluate 20 pairs for a reward of USD 0.5 in AMT,
or JPY 40 in Lancers. To avoid biases, we randomly sample (image, XAI
method)-pairs assigned to each worker. Approximately 3200 crowd workers
participate in the evaluation tasks.

We compare ROAR, KAR, ROAE, and KAE schemes (introduced in 2.2) as the
representatives of automated evaluation schemes. The performance of each XAI
method is evaluated by an accuracy-exposure curve. For the crowd-based
evaluation, We calculate the average accuracy of crowd answers at each
exposure rate, while the human evaluators are replaced by a machine classifier
in the automated evaluation.

In addition, we also provide the area under curve (AUC) of each accuracy-
exposure curve. Let a series of exposure rates be
$r_{1}=0,r_{2},r_{3},\ldots,r_{n}=1$, where $r_{i}<r_{j}$ for $i<j$. Let
$a_{i}^{k}$ denote the accuracy at exposure rate $r_{i}$ for XAI method $k$
both in crowd-based and automated evaluations. The value of AUC in XAI method
$k$ denoted by $\text{AUC}^{k}$ is defined as

$\text{AUC}^{k}=\sum_{i=2}^{n}\frac{1}{2}(r_{i}-r_{i-1})(a_{i}^{k}+a_{i-1}^{k}).$

###  4.2 Results

####  4.2.1 Q1. Are human and automated evaluations really different?

The first question we investigate is the difference between automated and
crowd-based evaluation schemes, because the latter requires higher time and
financial costs, and there is no reason to resort to human evaluation if they
both give the same results.

Figure 5 shows the accuracy-exposure curves of different XAI methods at
different exposure rates by different evaluation methods. For the crowd-based
evaluation scheme (denoted by Crowd) and two automated evaluation schemes (KAR
and KAE), higher curves indicate better performance. In contrast, for the
other two automated evaluation schemes, ROAR and ROAE, lower curves indicate
better performance.

Figure 5:  Performance curves of different XAI methods on the two datasets
(Food101 and Animal95). The horizontal and vertical axis indicates the
exposure rate and accuracy, respectively. For the crowd-based evaluation
(Crowd), KAR, and KAE, upper curves indicate better performance. In contrast,
for ROAR and ROAE, lower curves are better.

Table 2 shows the AUCs of each scheme; each row and column correspond to an
evaluation scheme and an XAI method, respectively. The numbers in the brackets
show the ranks. The bold numbers show the best results. Although we can see
some consistency between the ranking of AUC by the crowd-based ranking and
those by the automatic evaluation schemes, no automated evaluation scheme
obtains the same ranking of AUC as the crowd-based evaluation. (We will see
more detailed comparisons later.)

(a) Image difficulty (Food101)

(b) Image difficulty (Animal95)

(c) Worker ability (Food101)

(d) Worker ability (Animal95)

Figure 6:  Histograms of average exposure rates of correct answers. The
horizontal and vertical axes indicate the exposure rate and frequency,
respectively; the top and bottom rows indicate the frequencies of images and
workers, which show the distributions of “image difficulty” and “worker
ability”, respectively. Comparing (a) and (b), the mean image difficulty of
Animal95 dataset is higher than that of Food101, indicating the Animal95
dataset is relatively easier than Food101. In the bottom row ((c) and (d)),
the variance of the worker ability in the Food 101 dataset is higher than that
of Animal95, which is probably because the difficulty of recognizing food can
be significantly affected by cultural differences. In spite of the large
variations in the worker ability, Table 3 shows they have no significant
impacts on the results.

(a) Spearman@Food101 (b) Kendall@Food101

(c) Spearman@Animal95 (d) Kendall@Animal95

Figure 7:  Correlations of XAI methods ranking between the crowd-based evaluation and the four automated evaluations at different exposure rates in the Food101 and Animal95 datasets (the higher, the better). The correlations are given both in the Spearman ranking correlation and the Kendall ranking correlation. The horizontal and vertical axes indicate the exposure rate and the ranking correlation value, respectively.  Table 2: AUCs of different methods by different evaluation schemes. The numbers in the bracket show the rank of the XAI method. The bold numbers show the best results. For the crowd-based evaluation (Crowd), KAR, and KAE, larger AUC values show better performance, that is, important areas of images are shown earlier. On the other hand, for ROAR and ROAE, smaller AUCs indicate better performance, that is, important areas are removed earlier. (Also see Figure 5.)  Dataset | Scheme | GradCAM | Guided-bp | SmoothGrad | Vanilla Gradients | Random
---|---|---|---|---|---|---
Food101 | Crowd (ours) |  0.639 (1) | 0.469 (2) | 0.425 (3) | 0.396 (4) | 0.334 (5)
KAR |  0.667 (1) | 0.494 (3) | 0.478 (4) | 0.570 (2) | 0.340 (5)
KAE |  0.669 (1) | 0.340 (2) | 0.265 (4) | 0.316 (3) | 0.136 (5)
ROAR | 0.211 (2) |  0.140 (1) | 0.258 (3) | 0.346 (4) | 0.366 (5)
ROAE | 0.159 (5) |  0.060 (1) | 0.072 (2) | 0.087 (3) | 0.140 (4)
Animal95 | Crowd (ours) |  0.752 (1) | 0.696 (2) | 0.592 (4) | 0.608 (3) | 0.354 (5)
KAR |  0.627 (1) | 0.456 (3) | 0.445 (4) | 0.515 (2) | 0.365 (5)
KAE |  0.619 (1) | 0.311 (3) | 0.294 (4) | 0.354 (2) | 0.137 (5)
ROAR | 0.142 (2) |  0.088 (1) | 0.194 (3) | 0.200 (4) | 0.385 (5)
ROAE | 0.115 (4) |  0.048 (1) | 0.054 (2) | 0.059 (3) | 0.137 (5)

Now, we discuss the impact of different datasets on the results. It is evident
from Table 2 that the values of AUC are different among the two datasets,
Food101 and Animal95. The AUCs for Animal95 datasets are generally better than
those for Food101 in all the schemes. This is probably because it is rather
easier to recognize animals than foods; this is also suggested by Figure 6
showing the distribution of the “difficulty” of the images.

In contrast, Figure 5 shows that the ranking of XAI methods is not entirely
different among the datasets, except for the slight difference in SmoothGrad
and Vanilla Gradients. This shows that the difference of datasets does not
significantly impact the relative superiority or inferiority of the different
schemes. However, this conclusion is drawn from only two datasets and needs to
be validated with more datasets in the future.

####  4.2.2 Q2. Which XAI methods are deemed better by humans?

Because different XAI methods provide different pixel rankings, the next
question we investigate is which XAI method is more reliable. It can be
observed from Table 2 that GradCAM exhibits the best performance in the crowd-
based evaluation scheme. This is probably because GradCAM produces low
resolution feature maps (e.g., $7\times 7$ for ResNet family when the input
size is $224\times 224$), which are then linearly interpolated to the
resolution of the input image, thereby producing mostly connected regions
rather than distributed regions.

In addition, this result is also consistent with the conclusion of previous
work on sanity checking [1].

####  4.2.3 Q3. Which automated evaluation scheme is closer to humans?

Once we assume that the human assessments are the ground truths, automated
evaluation scheme which is closer to the crowd-based evaluation scheme
indicates better performance. Quantifying the goodness of automated evaluation
schemes is not only useful for evaluating them but will also help improving
themselves.

We investigate the ranking similarity between the four automated evaluations
and the crowd-based evaluations. Figure 7 shows the correlations of XAI
methods ranking between the crowd-based evaluation and the four automated
evaluations at different exposure rates in the Food101 and Animal95 datasets.

Most of the automated evaluation schemes show positive correlations with
crowd-based evaluation, but only ROAE shows the lowest correlations, and even
gives negative correlations for high exposure rates; this is probably because
the mechanism of ROAE equals adding white noises to the images at high
exposure rates, which is also known as an approach for generating adversarial
examples.

ROAR shows the better performance than ROAE, which is consistent with the
report in the previous study [12], which implies the importance of re-
training. KAE consistently performs well independent of the change of
datasets, correlation types, and exposure rates. KAR performs sub-optimally,
but it maintains almost the same performances at high exposure rates, while
other automated evaluation schemes tend to decrease the performance at high
exposure rates.

####  4.2.4 Q4. How does the number and ability of crowd evaluators affect the
evaluation results?

Finally, we investigate the stability of the proposed crowd-based evaluation
scheme in terms of the number of crowd workers participating in the
evaluation. Crowd workers have different abilities and diligence; for example,
some crowd workers do not work seriously on tasks. Figure 6c and Figure 6d
show the histograms of the average exposure rate at which each crowd worker
made a correct answer, which can be considered as the distribution of the
worker ability; large variations are observed in the ability of the workers.

Table 3 summarizes the AUC values of the performance curves when the average
number of workers per (XAI method, image)-pair is changed. Some variations are
observed in the results when the average number of workers was changed;
however, no significant change was found in the qualitative results, which
shows the stability and efficiency of the proposed crowd evaluation scheme.

Table 3: AUCs for different average numbers of crowd workers per (image, XAI method)-pair. The numbers in the bracket show the rank of the XAI method. Although the performance of crowd workers varies greatly due to their different ability and diligence (Figure 6 (c)(d)), the ranking of XAI methods does not change according to the number of workers.  Dataset | Workers per image | GradCAM | Guided-bp | SmoothGrad | Vanilla Gradients | Random
---|---|---|---|---|---|---
Food101 | 0.3 | 0.647 (1) | 0.492 (2) | 0.474 (3) | 0.422 (4) | 0.337 (5)
0.5 | 0.618 (1) | 0.468 (2) | 0.450 (3) | 0.419 (4) | 0.348 (5)
1 | 0.610 (1) | 0.465 (2) | 0.446 (3) | 0.422 (4) | 0.331 (5)
3 | 0.632 (1) | 0.462 (2) | 0.421 (3) | 0.395 (4) | 0.330 (5)
5 | 0.636 (1) | 0.470 (2) | 0.431 (3) | 0.399 (4) | 0.332 (5)
7 | 0.638 (1) | 0.469 (2) | 0.428 (3) | 0.397 (4) | 0.333 (5)
10 | 0.639 (1) | 0.469 (2) | 0.425 (3) | 0.396 (4) | 0.334 (5)
Animal95 | 0.3 | 0.742 (1) | 0.675 (2) | 0.624 (3) | 0.622 (4) | 0.367 (5)
0.5 | 0.752 (1) | 0.667 (2) | 0.591 (4) | 0.616 (3) | 0.347 (5)
1 | 0.745 (1) | 0.683 (2) | 0.603 (4) | 0.622 (3) | 0.339 (5)
3 | 0.758 (1) | 0.695 (2) | 0.604 (4) | 0.608 (3) | 0.365 (5)
5 | 0.755 (1) | 0.696 (2) | 0.596 (4) | 0.608 (3) | 0.357 (5)
7 | 0.752 (1) | 0.696 (2) | 0.593 (4) | 0.609 (3) | 0.358 (5)
10 | 0.752 (1) | 0.696 (2) | 0.592 (4) | 0.608 (3) | 0.354 (5)

##  5 Conclusion

In this study, we investigated schemes for evaluation of XAI methods. Based on
the hypothesis that interpretability for humans can ultimately only be
assessed by humans, We proposed a new human-based evaluation scheme using
crowdsourcing and compared it with existing automated evaluation schemes. We
convened a total of 3,200 crowd workers to conduct experiments using four XAI
methods and two datasets. The results showed that there are differences
between the crowd-based evaluation and automatic evaluation. Among the various
automatic evaluation schemes, KAE gave the most similar XAI evaluations to
human evaluation.

In the report by Hooker et al. [12], ROAR performed better than KAR, but the
results of our experiment indicate the opposite, which can be further
investigated in the future.

In addition, among the four XAI methods, Grad-CAM was found to be the XAI
method closest to human evaluation. This is rather counter intuitive if we
focus only on saliency maps because Guided-Backpropagation and SmoothGrad
highlight the outline of objects more accurately (as shown in Figure 1);
however, in our scheme, we present a combination of the original image and the
saliency map so that Grad-CAM can convey more information with the fewer
pixels.

We also confirmed that the number of crowd workers and datasets did not
significantly impact the results; however, larger-scale experiments using more
datasets will be desirable in the future.

## References

  * [1] Adebayo, J., Gilmer, J., Muelly, M., Goodfellow, I., Hardt, M., Kim, B.: Sanity checks for saliency maps. Advances in Neural Information Processing Systems 31, 9505–9515 (2018)
  * [2] von Ahn, L., Liu, R., Blum, M.: Peekaboom: a game for locating objects in images. In: Proceedings of the SIGCHI conference on Human Factors in Computing Systems (CHI). pp. 55–64 (2006)
  * [3] Baehrens, D., Schroeter, T., Harmeling, S., Kawanabe, M., Hansen, K., Müller, K.R.: How to explain individual classification decisions. Journal of Machine Learning Research 11, 1803–1831 (2010)
  * [4] Bossard, L., Guillaumin, M., Van Gool, L.: Food-101 – mining discriminative components with random forests. In: Proceedings of the 13th European Conference on Computer Vision (ECCV) (2014)
  * [5] Can, G., Benkhedda, Y., Gatica-Perez, D.: Ambiance in social media venues: visual cue interpretation by machines and crowds. In: Proceedings of the 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). pp. 2363–2372 (2018)
  * [6] Ciregan, D., Meier, U., Schmidhuber, J.: Multi-column deep neural networks for image classification. In: Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR). pp. 3642–3649 (2012)
  * [7] Ciresan, D., Giusti, A., Gambardella, L., Schmidhuber, J.: Deep neural networks segment neuronal membranes in electron microscopy images. Advances in Neural Information Processing Systems 25, 2843–2851 (2012)
  * [8] Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., Kuksa, P.: Natural language processing (almost) from scratch. Journal of Machine Learning Research 12(76), 2493–2537 (2011)
  * [9] Doshi-Velez, F., Kim, B.: Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08608 (2017)
  * [10] Erhan, D., Bengio, Y., Courville, A., Vincent, P.: Visualizing higher-layer features of a deep network. University of Montreal 1341(3), 1 (2009)
  * [11] He, K., Zhang, X., Ren, S., Sun, J.: Deep residual learning for image recognition. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 770–778 (2016)
  * [12] Hooker, S., Erhan, D., Kindermans, P.J., Kim, B.: A benchmark for interpretability methods in deep neural networks. Advances in Neural Information Processing Systems 32, 9737–9748 (2019)
  * [13] Hutton, A., Liu, A., Martin, C.: Crowdsourcing evaluations of classifier interpretability. In: 2012 AAAI Spring Symposium Series (2012)
  * [14] Jeyakumar, J.V., Noor, J., Cheng, Y.H., Garcia, L., Srivastava, M.: How can i explain this to you? an empirical study of deep neural network explanation methods. Advances in Neural Information Processing Systems 33, 4211–4222 (2020)
  * [15] Ji, S., Xu, W., Yang, M., Yu, K.: 3D convolutional neural networks for human action recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence 35(1), 221–231 (2012)
  * [16] Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. Advances in Neural Information Processing Systems 25, 1097–1105 (2012)
  * [17] Kuznetsova, A., Rom, H., Alldrin, N., Uijlings, J., Krasin, I., Pont-Tuset, J., Kamali, S., Popov, S., Malloci, M., Kolesnikov, A., Duerig, T., Ferrari, V.: The Open Images Dataset V4: Unified image classification, object detection, and visual relationship detection at scale. International Journal of Computer Vision 128, 1956–1981 (2020)
  * [18] Law, E., Ahn, L.v.: Human Computation. Morgan & Claypool Publishers (2011)
  * [19] Le, Q.V., Zou, W.Y., Yeung, S.Y., Ng, A.Y.: Learning hierarchical invariant spatio-temporal features for action recognition with independent subspace analysis. In: Proceedings of the IEEE conference on Computer Vision and Pattern Recognition (CVPR). pp. 3361–3368 (2011)
  * [20] Narayanan, M., Chen, E., He, J., Kim, B., Gershman, S., Doshi-Velez, F.: How do humans understand explanations from machine learning systems? an evaluation of the human-interpretability of explanation. arXiv preprint arXiv:1802.00682 (2018)
  * [21] Nguyen, T.T., Le Nguyen, T., Ifrim, G.: A model-agnostic approach to quantifying the informativeness of explanation methods for time series classification. In: International Workshop on Advanced Analytics and Learning on Temporal Data. pp. 77–94. Springer (2020)
  * [22] Ribeiro, M.T., Singh, S., Guestrin, C.: “Why should I trust you?” explaining the predictions of any classifier. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD). pp. 1135–1144 (2016)
  * [23] Samek, W., Binder, A., Montavon, G., Lapuschkin, S., Müller, K.R.: Evaluating the visualization of what a deep neural network has learned. IEEE Transactions on Neural Networks and Learning Systems 28(11), 2660–2673 (2016)
  * [24] Selvaraju, R.R., Cogswell, M., Das, A., Vedantam, R., Parikh, D., Batra, D.: Grad-CAM: Visual explanations from deep networks via gradient-based localization. In: Proceedings of the IEEE international Conference on Computer Vision (ICCV). pp. 618–626 (2017)
  * [25] Simonyan, K., Vedaldi, A., Zisserman, A.: Deep inside convolutional networks: Visualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 (2013)
  * [26] Smilkov, D., Thorat, N., Kim, B., Viégas, F., Wattenberg, M.: SmoothGrad: removing noise by adding noise. arXiv preprint arXiv:1706.03825 (2017)
  * [27] Socher, R., Perelygin, A., Wu, J., Chuang, J., Manning, C.D., Ng, A.Y., Potts, C.: Recursive deep models for semantic compositionality over a sentiment treebank. In: Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP). pp. 1631–1642 (2013)
  * [28] Springenberg, J.T., Dosovitskiy, A., Brox, T., Riedmiller, M.: Striving for simplicity: The all convolutional net. arXiv preprint arXiv:1412.6806 (2014)
  * [29] Szegedy, C., Liu, W., Jia, Y., Sermanet, P., Reed, S., Anguelov, D., Erhan, D., Vanhoucke, V., Rabinovich, A.: Going deeper with convolutions. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 1–9 (2015)
  * [30] Zhou, B., Khosla, A., Lapedriza, A., Oliva, A., Torralba, A.: Learning deep features for discriminative localization. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR). pp. 2921–2929 (2016)