# Recent studies on the super edge-magic deficiency of graphs

Rikio Ichishima  S.C. López  Francesc A. Muntaner-Batle  Yukio Takahashi

###### Abstract

A graph $G$ is called edge-magic if there exists a bijective function
$f:V\left(G\right)\cup
E\left(G\right)\rightarrow\left\\{1,2,\ldots,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right\\}$
such that $f\left(u\right)+f\left(v\right)+f\left(uv\right)$ is a constant for
each $uv\in E\left(G\right)$. Also, $G$ is said to be super edge-magic if
$f\left(V\left(G\right)\right)=\left\\{1,2,\ldots,\left|V\left(G\right)\right|\right\\}$.
Furthermore, the super edge-magic deficiency $\mu_{s}\left(G\right)$ of a
graph $G$ is defined to be either the smallest nonnegative integer $n$ with
the property that $G\cup nK_{1}$ is super edge-magic or $+\infty$ if there
exists no such integer $n$. In this paper, we introduce the parameter
$l\left(n\right)$ as the minimum size of a graph $G$ of order $n$ for which
all graphs of order $n$ and size at least $l\left(n\right)$ have
$\mu_{s}\left(G\right)=+\infty$, and provide lower and upper bounds for
$l\left(G\right)$. Imran, Baig, and Fen̆ovc̆íková established that for
integers $n$ with $n\equiv 0\pmod{4}$, $\mu_{s}\left(D_{n}\right)\leq 3n/2-1$,
where $D_{n}$ is the cartesian product of the cycle $C_{n}$ of order $n$ and
the complete graph $K_{2}$ of order $2$. We improve this bound by showing that
$\mu_{s}\left(D_{n}\right)\leq n+1$ when $n\geq 4$ is even. Enomoto, Lladó,
Nakamigawa, and Ringel posed the conjecture that every nontrivial tree is
super edge-magic. We propose a new approach to attak this conjecture. This
approach may also help to resolve another labeling conjecture on trees by
Graham and Sloane.

###### keywords:

super edge-magic labeling , super edge-magic deficiency , super edge-magic
tree conjecture , well spread set , weak Sidon set , $\alpha$-valuation ,
graph labeling , combinatorial optimization

###### MSC:

05C78 , 43A46 , 90C27

††journal: Discrete Applied Mathematics

[label1]organization=Department of Sport and Physical Education, Faculty of
Physical Education, Kokushikan University, addressline=7-3-1 Nagayama,
city=Tama-shi, postcode=206-8515, state=Tokyo, country=Japan

[label2]organization=Departament de Matemàtica, Universitat de Lleida,
addressline=C/Jaume II, 69, 25001, city=Lleida, country=Spain
[label3]organization=Graph Theory and Applications Research Group, School of
Electrical Engineering and Computer Science, Faculty of Engineering and Built
Environment, The University of Newcastle, addressline=NSW 2308,
country=Australia [label4]organization=Department of Science and Engineering,
Faculty of Electronics and Informations, Kokushikan University,
addressline=4-28-1 Setagaya, city=Setagaya-ku, postcode=154-8515, state=Tokyo,
country=Japan

##  1 Introduction

Unless stated otherwise, the graph-theoretical notation and terminology used
here will follow Chartrand and Lesniak [2]. In particular, the _vertex set_ of
a graph $G$ is denoted by $V\left(G\right)$, while the _edge set_ of $G$ is
denoted by $E\left(G\right)$. The _cycle_ of order $n$ and the _complete
graph_ of order $n$ are denoted by $C_{n}$ and $K_{n}$, respectively.

For the sake of brevity, we will use the notation $\left[a,b\right]$ for the
interval of integers $x$ such that $a\leq x\leq b$. Kotzig and Rosa [28]
initiated the study of what they called magic valuations. This concept was
later named edge-magic labelings by Ringel and Lladó [29] and this has become
the popular term. A graph $G$ is called _edge-magic_ if there exists a
bijective function $f:V\left(G\right)\cup
E\left(G\right)\rightarrow\left[1,\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right]$
such that $f\left(u\right)+f\left(v\right)+f\left(uv\right)$ is a constant for
each $uv\in E\left(G\right)$. Such a function is called an _edge-magic
labeling_. More recently, they have also been referred to as edge-magic total
labelings by Wallis [33].

Enomoto, Lladó, Nakamigawa, and Ringel [4] introduced a particular type of
edge-magic labelings, namely, super edge-magic labelings. They defined an
edge-magic labeling of a graph $G$ with the additional property that
$f\left(V\left(G\right)\right)=\left[1,\left|V\left(G\right)\right|\right]$ to
be a _super edge-magic labeling_. Thus, a _super edge-magic graph_ is a graph
that admits a super edge-magic labeling.

Lately, super edge-magic labelings and super edge-magic graphs are called by
Wallis [33] strong edge-magic total labelings and strongly edge-magic graphs,
respectively. According to the latest version of the survey on graph labelings
by Gallian [10] available to the authors, Hegde and Shetty [16] showed that
the concepts of super edge-magic graphs and strongly indexable graphs (see [1]
for the definition of a strongly indexable graph) are equivalent.

The following result found in [5] provides necessary and sufficent conditions
for a graph to be super edge-magic, which will prove later to be useful.

######  Lemma 1.1.

A graph $G$ is super edge-magic if and only if there exists a bijective
function
$f:V\left(G\right)\rightarrow\left[1,\left|V\left(G\right)\right|\right]$ such
that the set

$S=\left\\{f\left(u\right)+f\left(v\right)\left|uv\in
E\left(G\right)\right.\right\\}$

consists of $\left|E\left(G\right)\right|$ consecutive integers. In such a
case, $f$ extends to a super edge-magic labeling of $G$ with magic constant
$k=\left|V\left(G\right)\right|+\left|E\left(G\right)\right|+s$, where
$s=\min\left(S\right)$ and

$S=\left[k-\left(\left|V\left(G\right)\right|+\left|E\left(G\right)\right|\right),k-\left(\left|V\left(G\right)\right|+1\right)\right]\text{.}$

Enomoto, Lladó, Nakamigawa, and Ringel [4] showed that caterpillars are super
edge-magic and posed the following conjecture.

######  Conjecture 1.

Every nontrivial tree is super edge-magic.

Lee and Shan [24] have verified the above conjecture for trees with up to $17$
vertices with a computer. Fukuchi and Oshima [9] have shown that if $T$ is a
tree of order $n\geq 2$ such that $T$ has diameter greater than or equal to
$n-5$, then $T$ is super edge-magic. Various classes of banana trees (see [10]
for the definition) that have super edge-magic labelings have been found
independently by Swaminathan and Jeyanthi [32], and Hussain, Baskoro, and
Slamin [17]. Fukuchi [8] showed how to recursively create super edge-magic
trees from certain kinds of existing super edge-magic trees. Ngurah, Baskoro,
and Simanjuntak [26] provided a method for constructing new (super) edge-magic
graphs from existing ones. For further knowledge on the progress of Conjecture
1, the authors suggest that the reader consult the extensive survey by Gallian
[10].

For every graph $G$, Kotzig and Rosa [28] proved that there exists an edge-
magic graph $H$ such that $H=G\cup nK_{1}$ for some nonnegative integer $n$.
This motivated them to define the edge-magic deficiency of a graph. The _edge-
magic deficiency_ $\mu\left(G\right)$ of a graph $G$ is the smallest
nonnegative integer $n$ for which $G\cup nK_{1}$ is edge-magic. Inspired by
Kotzig and Rosa’s notion, the concept of _super edge-magic deficiency_
$\mu_{s}\left(G\right)$ of a graph $G$ was analogously defined in [6] as
either the smallest nonnegative integer $n$ with the property that $G\cup
nK_{1}$ is super edge-magic or $+\infty$ if there exists no such integer $n$.
Thus, the super edge-magic deficiency of a graph $G$ is a measure of how
“close” (“ far ”) $G$ is to (from) being super edge-magic.

An alternative term exists for the super edge-magic deficiency, namely, the
vertex dependent characteristic. This term was coined by Hedge and Shetty
[15]. In [15], they gave a construction of polygons having same angles and
distinct sides using the result on the super edge-magic deficiency of cycles
provided in [7].

##  2 Lower and upper bounds

It is known from [7] that $\mu_{s}\left(K_{n}\right)=+\infty$ for every
integer $n\geq 5$. It follows that for every integer $n$ with $n\neq 1,2,3,4$,
there exists a positive integer $l\left(n\right)$ with the property that if
$G$ is a graph of order $n$ and size at least $l\left(n\right)$, then
$\mu_{s}\left(G\right)=+\infty$. It is interesting to determine the exact
value of $l\left(n\right)$. However, it seems that this is a very hard
problem. In this section, we present lower and upper bounds for this value.

We begin with the following lower bound for $l\left(n\right)$.

######  Theorem 2.1.

For every integer $n\geq 4$,

$l\left(n\right)\geq\lceil n/2\rceil\left(\lfloor
n/2\rfloor+1\right)+1\text{.}$

###### Proof.

Define the graph $G$ with

$V\left(G\right)=\left\\{x_{i}\left|\right.i\in\left[1,\lceil
n/2\rceil\right]\right\\}\cup\left\\{y_{i}\left|\right.i\in\left[1,\lfloor
n/2\rfloor\right]\right\\}$

and

$\displaystyle E\left(G\right)$ $\displaystyle=$
$\displaystyle\left\\{x_{i}x_{j}\left|i\right.\in\left[1,\lceil
n/2\rceil\right]\text{ and }j\in\left[1,\lfloor n/2\rfloor\right]\right\\}$
$\displaystyle\cup\left\\{x_{1}x_{i}\left|\right.i\in\left[2,\lceil
n/2\rceil\right]\right\\}\cup\left\\{y_{1}y_{\lfloor
n/2\rfloor}\right\\}\text{.}$

Now, consider the vertex labeling $f:V\left(G\right)\rightarrow\left[1,\lceil
n/2\rceil\lfloor n/2\rfloor+1\right]$ such that

$f\left(v\right)=\left\\{\begin{tabular}[]{ll}$i$&if $v=x_{i}$ and
$i\in\left[1,\lceil n/2\rceil\right]$\\\ $\lceil n/2\rceil i+1$&if $v=y_{i}$
and $i\in\left[1,\lfloor n/2\rfloor\right]$\end{tabular}\right.$

Then

$\left\\{f\left(x_{1}\right)+f\left(x_{i}\right)\left|\right.i\in\left[2,\lceil
n/2\rceil\right\\}=\left[3,\lceil n/2\rceil+1\right]\right.\text{,}$
---
$\left\\{f\left(x_{i}\right)+f\left(y_{j}\right)\left|\right.i\in\left[1,\lceil
n/2\rceil\right]\right.\text{ and }j\in\left[1,\lfloor
n/2\rfloor\right]=\left[\lceil n/2\rceil+2,\lceil n/2\rceil\left(\lfloor
n/2\rfloor+1\right)+1\right]\text{,}$
$\left\\{f\left(y_{1}\right)+f\left(y_{\lfloor
n/2\rfloor}\right)\right\\}=\left\\{\lceil n/2\rceil\left(\lfloor
n/2\rfloor+1\right)+2\right\\}$.

Since $\left|E\left(G\right)\right|=\lceil n/2\rceil\left(\lfloor
n/2\rfloor+1\right)$, it follows that the set

$S=\left\\{f\left(x\right)+f\left(y\right)\left|\right.xy\in
E\left(G\right)\right\\}$

is a set of $\left|E\left(G\right)\right|$ consective integers. This shows
that $\mu_{s}\left(G\right)<+\infty$. Hence, there exists a graph $G$ of order
$n$ and size $\lceil n/2\rceil\left(\lfloor n/2\rfloor+1\right)$ so that
$\mu_{s}\left(G\right)<+\infty$. Therefore, $l\left(n\right)\geq\lceil
n/2\rceil\left(\lfloor n/2\rfloor+1\right)+1$. ∎

For a finite set $S$ of integers, we define the _gap_ $\Gamma\left(S\right)$
of $S$ to be

$\Gamma\left(S\right)=\left(\max(S)-\min(S)+1\right)-\left|S\right|\text{.}$

Then the following fact is a consequence of the above defition.

######  Observation 1.

Let $S$ be a finite set of integers. Then $S$ is a set of consecutive integers
if and only if $\Gamma\left(S\right)=0$.

To study graphs for which the clique number $\omega\left(G\right)$ of a graph
$G$ (the largest order among the complete subgraph of $G$) is large in
relation to the size of the graph, we have resorted to the theory of well
spread sets introduced by Kotzig [27]. A set
$\left\\{x_{i}\left|\right.i\in\left[1,n\right]\right\\}\subset\mathbb{N}$
with $x_{1}<x_{2}<\cdots<x_{n}$ is a _well spread set_ or _a weak Sidon set_
(WS-set for short) by Ruzsa [31] if the sums $x_{i}+x_{j}$ ($i<j$) are all
different. Furthermore, we define the _smallest span of pairwise sums_
$\rho^{*}\left(n\right)$ of cardinality of $n$ to be

$\rho^{*}\left(n\right)=\min\left\\{x_{n}+x_{n-1}-x_{2}-x_{1}+1\left|\right.\\{x_{1}<x_{2}<\cdots<x_{n}\\}\text{
is WS-set}\right\\}\text{.}$

The following lemma found by Kotzig [27] provides a lower bound of
$\rho^{*}\left(n\right)$ for every integer $n\geq 7$.

######  Lemma 2.1.

For every integer $n\geq 7$,

$\rho^{*}\left(n\right)\geq n^{2}-5n+14\text{.}$

With the aid of Lemma 2.1, it is possible to present the following result.

######  Theorem 2.2.

For every integer $n\geq 7$,

$\mu_{s}\left(K_{n+1}-e\right)=+\infty\text{,}$

where $e\in E\left(K_{n+1}\right)$.

###### Proof.

Assume, to the contrary, that $\mu_{s}\left(K_{n+1}-e\right)=k$ for some
positive integer $k$. Then there exists a bijective function
$f:V\left(\left(K_{n+1}-e\right)\cup
kK_{1}\right)\rightarrow\left[1,n+1+k\right]$ such that the set

$S=\left\\{f\left(x\right)+f\left(y\right)\left|xy\in
E\left(\left(K_{n+1}-e\right)\cup kK_{1}\right\\}\right.\right.$

is a set of $\tbinom{n+1}{2}-1$ consective integers, that is,
$\Gamma\left(S\right)=0$ by Obsrvation 1.

Now, assume that $u,v\in V\left(K_{n+1}-e\right)$ but $uv\notin
E\left(K_{n+1}-e\right)$. Also, consider the subgraph of $K_{n+1}-e$ obtained
by elminating vertex $u$ so that the resulting subgraph is $K_{n}$ and
consider the set

$S^{\prime}=\left\\{f\left(x\right)+f\left(y\right)\left|xy\in
E\left(\left(K_{n+1}-e\right)\cup
kK_{1}\right)\backslash\left\\{u\right\\}\right\\}\text{.}\right.$

Since the sums considered in $S^{\prime}$ are the same sums as the sums
considered in $S$ but for $\left(n-1\right)$ sums (the ones corresponding to
edges incident with $u$), it follows that $\Gamma\left(S^{\prime}\right)\leq
n-1$. On the other hand, the set

$\Omega=\left\\{f\left(x\right)\left|x\in
V\left(\left(K_{n+1}-e\right)\backslash\left\\{u\right\\}\right\\}\right.\right.$

is a well spread set of cardinality $n$. It follows from Lemma 2.1 that

$\max(W)-\min(W)+1\geq n^{2}-5n+14\text{,}$

where
$W=\left\\{f\left(x\right)+f\left(y\right)\left|f\left(x\right),f\left(y\right)\in\Omega\text{
and }f\left(x\right)\neq f\left(y\right)\right\\}\right.$. This implies that

$\Gamma\left(S^{\prime}\right)\geq
n^{2}-5n+14-\dbinom{n}{2}=\left(n^{2}-9n+28\right)/2\text{.}$

Therefore,

$\left(n^{2}-9n+28\right)/2\leq\Gamma\left(S^{\prime}\right)\leq n-1$

for all integers $n\geq 7$. However, since $\left(n^{2}-9n+28\right)/2>n-1$
for all integers $n\geq 7$, it follows that
$\Gamma\left(S^{\prime}\right)>n-1$, producing a contradiction. ∎

In fact, for any integer $n\geq 8$, the preceding result provides us with an
upper bound on $l\left(n\right)$, since for these values of $n$, we know that
$\mu_{s}\left(K_{n}\right)=\mu_{s}\left(K_{n}-e\right)=+\infty$, where $e\in
E\left(K_{n}\right)$. Therefore, we have the following upper bound for
$l\left(n\right)$.

######  Corollary 2.1.

For every integer $n\geq 7$,

$l\left(n\right)\leq\dbinom{n}{2}-2\text{.}$

From now on, let $K_{n}-\alpha e$ denote the set of all graphs obtained from
$K_{n}$ by removing exactly $\alpha$ edges, where $\alpha$ is a positive
integer. Our next theorem generalizes the preceding result.

######  Theorem 2.3.

For a fixed positive integer $\alpha$, there exists some positive integer
$j\left(\alpha\right)$ such that if $n>j\left(\alpha\right)$, then
$\mu_{s}\left(G\right)=+\infty$ for all $G\in K_{n}-\alpha e$, where
$n>2\alpha$.

###### Proof.

For a fixed positive integer $\alpha$, assume that $n>2\alpha$, where $n$ is a
positive integer. Let $G\in K_{n}-\alpha e$ and suppose, to the contrary, that
for every integer $n\in\mathbb{N}$, there exists some $G\in K_{n}-\alpha e$
such that $\mu_{s}\left(G\right)<+\infty$. Then there exists an injective
function $f:V\left(G\right)\rightarrow\mathbb{N}$ such that the set

$S=\left\\{f\left(x\right)+f\left(y\right)\left|xy\in
E\left(G\right)\right\\}\right.$

is a set of $\left|E\left(G\right)\right|$ consective integers. Also, notice
that there are at most $2\alpha$ vertices that have degree at most $n-2$,
since there are exactly $\alpha$ edges missing to form $K_{n}$. So, if we
elminate all vertices of degree at most $\left(n-2\right)$, then the resulting
graph is a complete graph. If it is $K_{n-2\alpha}$, then we are done;
otherwise, keep elminating vertices until we arrive at $K_{n-2\alpha}$.

Now, consider the set
$S^{\prime}=\left\\{f\left(x\right)+f\left(y\right)\left|xy\right.\in
E\left(K_{n-2\alpha})\right\\}\right.$. Since $S^{\prime}$ comes from the set
$S$ by removing at most $2\alpha\left(n-1\right)$ sums induced by edges, it
follows that

$\Gamma\left(S^{\prime}\right)\leq 2\alpha\left(n-1\right)\text{.}$

On the other hand, it follows from Lemma 2.1 that

$\Gamma\left(S^{\prime}\right)\geq\left(n-2\alpha\right)^{2}-5\left(n-2\alpha\right)+14-\dbinom{n-2\alpha}{2}\text{.}$

This together with the preceding inequality implies that

$\left(n-2\alpha\right)^{2}-5\left(n-2\alpha\right)+14-\dbinom{n-2\alpha}{2}\leq\Gamma\left(S^{\prime}\right)\leq
2\alpha\left(n-1\right)\text{.}$

However, since the inequality

$\left(n-2\alpha\right)^{2}-5\left(n-2\alpha\right)+14-\dbinom{n-2\alpha}{2}>2\alpha\left(n-1\right)$

is valid for all integers

$n>\dfrac{\left(8\alpha+9\right)+\sqrt{\left(8\alpha+9\right)^{2}-\left(16\alpha^{2}+88\alpha+112\right)}}{2}\text{,}$

this produces a contradiction. ∎

Observe that if we let $\alpha=2$ and we compute the minimum value of $n$ that
satisfies the previous inequality, we get $n\geq 21$. This means that for
$n\geq 21$, we have $\mu_{s}\left(G\right)=+\infty$ for any graph $G\in
K_{n}-2e$. However, it is also known that
$\mu_{s}\left(K_{n}\right)=\mu_{s}\left(K_{n}-e\right)=+\infty$. Therefore,
$l\left(n\right)\leq\tbinom{n}{2}-2$ for $n\geq 21$. Continue in this manner,
we can obtain upper bounds on $l\left(n\right)$ for sufficiently large
integers $n$ as the next result indicates.

######  Corollary 2.2.

For sufficiently large integers $n$,

$l\left(n\right)\leq\dbinom{n}{2}-\alpha\text{,}$

where $\alpha$ is a fixed positive integer such that $n>2\alpha$.

##  3 An improved upper bound

The _prism_ $D_{n}$ is defined to be the cartesian product of $C_{n}$ and
$K_{2}$. The prism is also known to be the Cayley graph of the dihedral group
$D_{n}$ with respect to the generating set $\left\\{x,x^{-1},y\right\\}$. It
was proved in [5] that if $n\geq 3$ is odd, then $D_{n}$ is super edge-magic,
that is, $\mu_{s}\left(D_{n}\right)=0$ in this case. Ngurah and Baskoro [25]
showed that if $n\geq 4$ is even, then $D_{n}$ is not edge-magic, implying
that $\mu_{s}\left(D_{n}\right)\geq\mu\left(D_{n}\right)\geq 1$ by
definitions. Imran, Baig, and Fen̆ovc̆íková [22] established the following
upper bound for $\mu_{s}\left(D_{n}\right)$.

######  Theorem 3.1.

For integers $n$ with $n\equiv 0\pmod{4}$,

$\mu_{s}\left(D_{n}\right)\leq 3n/2-1\text{.}$

In this section, we provide an improved upper bound for
$\mu_{s}\left(D_{n}\right)$ when $n\geq 4$ is even, and propose an open
problem for $\mu_{s}\left(D_{n}\right)$ when $n\geq 6$ is even. To proceed, we
introduce some additional definitions and results next.

The graph labeling method that has received the most attention over the years
was originated with a paper by Rosa [30] who called them $\beta$-valuations. A
few years later, Golomb [14] called these labelings graceful and this is the
term that has been used since then. For a graph $G$, an injective function
$f:V\left(G\right)\rightarrow\left[1,\left|E\left(G\right)\right|\right]$ is
called a _graceful labeling_ if each $uv\in E\left(G\right)$ is labeled
$\left|f\left(u\right)-f\left(v\right)\right|$ and the resulting edge labels
are distinct. Rosa [30] also introduced the concept of $\alpha$-valuations (a
particular type of graceful labelings) as a tool for decomposing the complete
graph into isomorphic subgraphs. A graceful labeling $f$ is called an
$\alpha\emph{-valuation}$ if there exists an integer $\lambda$ so that

$\min\left\\{f\left(u\right),f\left(v\right)\right\\}\leq\lambda<\max\left\\{f\left(u\right),f\left(v\right)\right\\}$

for each $uv\in E\left(G\right)\text{.}$

Douglas and Reid [3] obtained the following result.

######  Theorem 3.2.

For every integer $n\geq 2$, the prism $D_{2n}$ has an $\alpha$-valuation.

The following result found in [21] shows how $\alpha$-valuations are useful
for computing the super edge-magic deficiency of certain graphs.

######  Theorem 3.3.

Let $G$ be a graph without isolated vertices that has an $\alpha$-valuation.
Then

$\mu_{s}\left(G\right)\leq\left|E\left(G\right)\right|-\left|V\left(G\right)\right|+1\text{.}$

For every integer $n\geq 3$, we have $\left|V\left(D_{n}\right)\right|=2n$ and
$\left|E\left(D_{n}\right)\right|=3n$. Thus, the next result is redily
followed from the preceding theorems. This improves the bound given in Theorem
3.1.

######  Theorem 3.4.

For even integers $n$ with $n\geq 4$,

$\mu_{s}\left(D_{n}\right)\leq n+1\text{.}$

It is known from [21] that $\mu_{s}\left(Q_{3}\right)=5$, where $Q_{3}$ is the
$3$-cube. Since $D_{4}=Q_{3}$, it follows that $\mu_{s}\left(D_{4}\right)=5$.
This indicates that the bound given in Theorem 3.4 is attained for $n=4$.
However, there is no knowledge whether $\mu_{s}\left(D_{n}\right)=n+1$ for
even integers $n$ with $n\geq 6$ so far. This motivates us to propose the
following problem.

######  Problem 1.

Determine whether

$\mu_{s}\left(D_{n}\right)=n+1$

for even integers $n$ with $n\geq 6$.

##  4 A new approach

In this section, we propose a new approach to attak Conjecture 1. For this
reason, we now provide the definition for the key concept to be discussed
below.

For a graph $G$, a _numbering_ $f$ of $G$ is a labeling that assigns distinct
elements of the set $\left[1,\left|V\left(G\right)\right|\right]$ to the
vertices of $G$, where each $uv\in E\left(G\right)$ is labeled
$f\left(u\right)+f\left(v\right)$. The _strength_ str${}_{f}\left(G\right)$
_of a numbering_
$f:V\left(G\right)\rightarrow\left[1,\left|V\left(G\right)\right|\right]$ of
$G$ is defined by

$\mathrm{str}_{f}\left(G\right)=\max\left\\{f\left(u\right)+f\left(v\right)\left|uv\in
E\left(G\right)\right.\right\\}\text{,}$

that is, $\mathrm{str}_{f}\left(G\right)$ is the maximum edge label of $G$ and
the _strength_ str$\left(G\right)$ of a graph $G$ itself is

$\mathrm{str}\left(G\right)=\min\left\\{\mathrm{str}_{f}\left(G\right)\left|f\text{
is a numbering of }G\right.\right\\}\text{.}$

This type of numberings was introduced in [18] as a generalization of the
problem of finding whether a graph is super edge-magic or not (see Lemma 1.1
or consult [1] for alternative and often more useful definitions of the same
concept).

There are other related parameters that have been studied in the area of graph
labelings. Excellent sources for more information on this topic are found in
the extensive survey by Gallian [10], which also includes information on other
kinds of graph labeling problems as well as their applications.

Several bounds for the strength of a graph have been found in terms of other
parameters defined on graphs (see [11, 20, 18, 19]). The strengths of familiar
classes of graphs were found in [18]. The strength of trees was also
determined by Gao, Lau, and Shiu [11] as the next result indicates.

######  Theorem 4.1.

For every nontrivial tree $T$,

$\mathrm{str}\left(T\right)=\left|V\left(T\right)\right|+1\text{.}$

We are now ready to state the following conjecture, which may give us a viable
approach towards settling Conjecture 1.

######  Conjecture 2.

For every nontrivial tree $T$, there exists some positive constant $c$ such
that

$\mathrm{str}\left(T\right)\geq
c\cdot\mu_{s}\left(T\right)+\left|V\left(T\right)\right|+1\text{.}$

It is now immediate that if Conjecture 2 is true, then Theorem 4.1 impies
Conjecture 1.

We next consider a graph labeling that is related to super edge-magic
labelings. Harmonious labelings have been defined and studied by Graham and
Sloane [13] as part of their study of additive bases and are applicable to
error-correcting codes. A _harmonious labeling_ of a graph $G$ with
$\left|E\left(G\right)\right|\geq\left|V\left(G\right)\right|$ is an injective
function
$f:V\left(G\right)\rightarrow\left[1,\left|E\left(G\right)\right|-1\right]$
satisfying the condition that the induced edge labeling given by
$f\left(u\right)+f\left(v\right)\pmod{\left|E\left(G\right)\right|}$ for each
$uv\in E\left(G\right)$ is also an injective function. Furthermore, $G$ is
said to be _harmonious_ if such a labeling exists. This definition extends to
trees (for which
$\left|E\left(G\right)\right|=\left|V\left(G\right)\right|-1$) if at most one
vertex label is allowed to be repeated.

Grace [12] introduced sequential graphs, a subclass of harmonious graphs, and
showed that any tree admitting an $\alpha$-valuation is sequential and hence
is harmonious. On the other hand, Lee, Schmeichel, and Shee [23] introduced a
generalization of harmonious graphs, namely, felicitous graphs. The following
relation among labelings of trees was established in [5].

######  Theorem 4.2.

If $T$ is a super edge-magic tree, then $T$ is sequential and harmonious.

As with super edge-magic labelings, many classes of trees have been shown to
be harmonious (see [10] for a detailed list of trees), but whether all trees
are harmonious is not known.

######  Conjecture 3.

Every nontrivial tree is harmonious.

Of course, if Conjecture 2 is true, so is Conjecture 1. Ineed, in light of
Theorem 4.2, the truth of Conjecture 1 in turn implies that every nontrivial
tree is sequential and the truth of the above conjecture due to Graham and
Sloane [13] as well as the fact that every nontrivial tree is felicitous.

## References

  * [1] B.D. Acharya and S.M. Hegde, Strongly indexable graphs, Discrete Math., 93 (1991) 123–129.
  * [2] G. Chartrand and L. Lesniak, Graphs & Digraphs 3th ed. CRC Press (1996).
  * [3] S.J, Douglas and M. Reid. Labeling grids, Ars Combin., 34 (1992) 167–182.
  * [4] H. Enomoto, A. Lladó, T. Nakamigawa, and G. Ringel, Super edge-magic graphs, SUT J. Math., 34 (1998) 105–109.
  * [5] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, The place of super edge-magic labelings among other classes of labelings, Discrete Math., 231 (2001) 153–168.
  * [6] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, On the super edge magic deficiency of graphs, Electron. Notes Discrete Math., 11 (2002) 299–314.
  * [7] R.M. Figueroa-Centeno, R. Ichishima, and F.A. Muntaner-Batle, On the super edge-magic deficiency of graphs, Ars Combin., 78 (2006) 33–45.
  * [8] Y. Fukuchi, A recursive theorem for super edge-magic labelings of trees, SUT J. Math., 36 (2000) 279–285.
  * [9] Y. Fukuchi and A. Oshima, Super-edge-magic labeling of trees with large diameter, Far East J. Math. Sci., 28 (2008) 497–571.
  * [10] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin., (2021) #DS6.
  * [11] Z.B. Gao, G.C. Lau, and W.C. Shiu, Graphs with minimal strength, Symmetry 13 (2021) #513.
  * [12] T. Grace, On sequential labelings of graphs J. Graph Theory, 7 (1983), no. 2, 195–201.
  * [13] R.L. Graham and N.J. Sloane, On additive bases and harmonious graphs, SIAM J. Alg. Discrete Meth.. 1 (1980) 382–-404.
  * [14] S.W. Golomb, How to number a graph, in Graph Theory and Computing, (ed. R.C. Read), Academic Press, New York (1972) 23–37.
  * [15] S.M. Hegde and S. Shetty, Strongly indexable graphs and applications, Discrete Math., 309 (2009) 6160–6168.
  * [16] S. Hegde and S. Shetty, Strongly $k$-indexable and super edge magic labelings are equivalent, unpublished.
  * [17] M. Hussain, E. Baskoro, and Slamin, On super edge-magic total labeling of banana trees, Util. Math., 79 (2009) 243–251.
  * [18] R. Ichishima, F.A. Muntaner-Batle, and A. Oshima, Bounds for the strength of graphs, Australas. J. Combin., 72 (2018) 492–508.
  * [19] R. Ichishima, F.A. Muntaner-Batle, A. Oshima, and Y. Takahashi, The strength of graphs and related invariants, Memoirs Kokushikan Univ. Inf. Sci., 41 (2020) 1–8.
  * [20] R. Ichishima, F.A. Muntaner-Batle, and Y. Takahashi, On the strength and independence number of graphs, Contrib. Math., 6 (2022) 25–29.
  * [21] R. Ichishima and A. Oshima, On the super edge-magic deficiency and $\alpha$-valuations of graphs, J. Indones. Math. Soc., Special edition (2011) 59–69.
  * [22] M. Imran, A.Q. Baig, and A.S, Fen̆ovc̆íková, Some results on super edge-magic deficiency of graphs, Kragujevac J. Math., 44 no. 2 (2020) 237–249.
  * [23] S.M. Lee, E. Schmeichel, and S.C. Shee, On felicitous graphs, Discrete Math., 93 (1991) 201–209.
  * [24] S.M. Lee and Q.X. Shan, All trees with at most 17 vertices are super edge-magic, 16th MCCCC Conference, Carbondale, University Southern Illinois, Nov. 2002.
  * [25] A.A.G. Ngurah and E.T. Baskoro, On magic and antimagic total labelings of generalized Petersen graph, Util. Math., 63 (2003) 97–107.
  * [26] A.A.G. Ngurah, E. Baskoro, and R. Simamjuntak, On new families of (super) edge-magic graphs, Util. Math., 74 (2007) 111–120.
  * [27] A. Kotzig, On well spread sets of integers, Publications du Centre de Recheres Mathemátiques Universitéde Montréal,161 (1972) CRM-175.
  * [28] A. Kotzig and A. Rosa, Magic valuations of finite graphs, Canad. Math. Bull., 13 (1970) 451–-461.
  * [29] G. Ringel and A. Lladó, Another tree conjecture, Bull. Inst. Combin. Appl., 18 (1996) 83–85.
  * [30] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y and Dunod Paris (1967) 349–55.
  * [31] I.Z. Ruzsa, Solving a linear equation in a set of integers, I. Acta Arith., 65 (1993), no. 3, 259–282.
  * [32] V. Swaminathan and P. Jeyanthi, Super edge-magic strength of fire crackers, banana trees and unicyclic graphs, Discrete Math., 306 (2006) 1624–1636.
  * [33] W.D. Wallis, Magic Graphs, Birkhäuser, Boston (2001).


multicitedelim compcitedelim postnotedelim mydate mydate 210mm5.5in* [] []
*26pc1.618**1*** 2.5 *2* 2ex10mm0pt [nearest] 0pt manaartplain manaart0.5
manaartDyrland, Lundervold, Porta ManaDoes the evaluation stand up to
evaluation? manaart0 plain0

This document is designed for screen reading and two-up printing on A4 or
Letter paper

plain figure #1

# Does the evaluation stand up to evaluation?
A first-principle approach to the evaluation of classifiers

K. Dyrland
<gmail.com>
A. S. Lundervold $\dagger$
<hvl.no>
P.G.L. Porta Mana
<portamana.org>
(listed alphabetically)
Dept of Computer science, Electrical Engineering and Mathematical Sciences,
Western Norway University of Applied Sciences, Bergen, Norway
$\dagger$& Mohn Medical Imaging and Visualization Centre, Dept of Radiology,
Haukeland University Hospital, Bergen, Norway  kjetil.dyrland
alexander.selvikvag.lundervold pgl

(27 May 2022; updated 21 February 2023)

How can one meaningfully make a measurement, if the meter does not conform to
any standard and its scale expands or shrinks depending on what is measured?
In the present work it is argued that current evaluation practices for
machine-learning classifiers are affected by this kind of problem, leading to
negative consequences when classifiers are put to real use; consequences that
could have been avoided. It is proposed that evaluation be grounded on
Decision Theory, and the implications of such foundation are explored. The
main result is that every evaluation metric must be a linear combination of
confusion-matrix elements, with coefficients – ‘utilities’ – that depend on
the specific classification problem. For binary classification, the space of
such possible metrics is effectively two-dimensional. It is shown that popular
metrics such as precision, balanced accuracy, Matthews Correlation
Coefficient, Fowlkes-Mallows index, $F_{1}$-measure, and Area Under the Curve
are never optimal: they always give rise to an in-principle _avoidable_
fraction of incorrect evaluations. This fraction is even larger than would be
caused by the use of a decision-theoretic metric with moderately wrong
coefficients.

##  0 Prologue: a short story

The manager of a factory which produces a sort of electronic component wishes
to employ a machine-learning classifier to assess the durability of each
produced component. The durability determines whether the component will be
used in one of two possible kinds of device. The classifier should take some
complex features of the component as input, and output one of the two labels
‘0’ for ‘long durability’, or ‘1’ for ‘short durability’, depending on the
component type.

Two candidate classifiers, let us call them and , are trained on available
training data. When employed on a separate evaluation set, they yield the
following confusion matrices, written in the format

$\rotatebox[origin={c}]{90.0}{
\clap{{\parbox{50.00008pt}{\centering\scriptsize classifier\\\ output\\\
$1\quad 0$\@add@centering}} }}\
\overbracket{\begin{bmatrix}[r]\text{\footnotesize True 0}&\text{\footnotesize
False 0}\\\ \text{\footnotesize False 1}&\text{\footnotesize True
1}\end{bmatrix}}^{\clap{\textit{\parbox{42.00009pt}{\centering\scriptsize true
class\\\ $0\hskip 21.00005pt1$\@add@centering}}}}$

and normalized over the total number of evaluation data:

$\displaystyle\text{classifier $\Alpha$:}\quad\begin{bmatrix}[r]0.27&0.15\\\
0.23&0.35\end{bmatrix}\ ,$ (1) $\displaystyle\text{classifier
$\Beta$:}\quad\begin{bmatrix}[r]0.43&0.18\\\ 0.07&0.32\end{bmatrix}\ .$ (2)

These matrices show that the factory produces, on average, 50% short- and 50%
long-durability components.

The confusion matrices above lead to the following values of common evaluation
metrics[Balanced accuracy:][]brodersenetal2010[$F_{1}$
measure:][]vanrijsbergen1974[Matthews correlation
coefficient:][]matthews1975[Fowlkes-Mallows index:][]fowlkesetal1983 for the
two classifiers. Class $0$ is ‘positive’, $1$ ‘negative’. Blue bold indicates
the classifier favoured by the metric, red the disfavoured:

?tablename? 1:  Metric | classifier | classifier
---|---|---
Accuracy (also balanced accuracy) | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.62}$ | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.75}}$
Precision | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.64}$ | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.70}}$
$F_{1}$ measure | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.59}$ | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.77}}$
Matthews Correlation Coefficient | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.24}$ | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.51}}$
Fowlkes-Mallows index | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.59}$ | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.78}}$
True-positive rate (recall) | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.54}$ | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.86}}$
True-negative rate (specificity) | ${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{0.70}}$ | ${\color[rgb]{0.66796875,0.19921875,0.46484375}0.64}$

The majority of these metrics favour classifier , some of them by quite a wide
relative difference. Only the true-negative rate favours classifier , but only
by a relative difference of 9%.

The developers of the classifiers therefore recommend the employment of
classifier .

The factory manager does not fully trust these metrics, asking, “how do I know
they are appropriate?”. The developers assure that these metrics are widely
used. The manager (of engineering background) comments, “I don’t remember
‘widely used’ being a criterion of scientific correctness – not after Galileo
at least”, and decides to employ both classifiers for a trial period, to see
which factually leads to the best revenue. The two classifiers are integrated
into two separate but otherwise identical parallel production lines.

During the trial period, the classifiers perform according to the
classification statistics of the confusion matrices (1) and (2) above. At the
end of this period the factory manager finds that the average net gains per
assessed component yielded by the two classifiers are111‘$’ represents a
generic currency or value unit; this is why it is not written in front of the
gains.

classifier | classifier
---|---
${\color[rgb]{0.265625,0.46484375,0.66796875}\bm{3.5}}$ $ |  ${\color[rgb]{0.66796875,0.19921875,0.46484375}-3.5}$ $
(3)

That is, classifier actually led to a _loss_ of revenue. The manager therefore
decides to employ classifier , commenting with a smug smile that it is always
unwise to trust the recommendations of developers, unacquainted with the
nitty-gritty reality of a business.

The average gains above are easy to calculate from some additional
information. The final net gains caused by the correct or incorrect
classification of one electronic component are as follows:

$\rotatebox[origin={c}]{90.0}{
\clap{{\parbox{50.00008pt}{\centering\scriptsize classifier\\\ output\\\
$1\quad 0$\@add@centering}} }}\
\overbracket{\begin{bmatrix}[r]15\,\text{\$}&-335\,\text{\$}\\\
-35\,\text{\$}&165\,\text{\$}\end{bmatrix}}^{\clap{\textit{\parbox{42.00009pt}{\centering\scriptsize
true class\\\ $0\hskip 21.00005pt1$\@add@centering}}}}$ (4)

The reason behind these values is that short-durability components (class 1)
provide more power and are used in high-end, costly devices; but they cause
extreme damage and consequent repair costs and refunds if used in devices that
require long-durability components (class 0). Long-durability components
provide less power and are used in low-end, cheaper devices; they cause some
damage if used in devices that require short-durability components, but with
lower consequent costs.

Taking the sum of the products of the gains above by the respective
percentages of occurrence – that is, the elements of the confusion matrix –
yields the final average gain. The final average gain returned by the use of
classifier , for example, is

$15\,\text{\$}\times 0.27-335\,\text{\$}\times 0.15-35\,\text{\$}\times
0.23+165\,\text{\$}\times 0.35=3.5\,\text{\$}\ .$

In the present case, the confusion matrices (1) and (2) lead to the amounts
(3) found by the manager.

##  1 Issues in the evaluation of classifiers

The story above illustrates several well-known issues of currently popular
evaluation procedures for machine-learning classifiers:

  1. (a)

We are swept by an avalanche of possible evaluation metrics. Often it is not
clear which is the most compelling. In the story above, for example, one could
argue that the true-negative rate was the appropriate metric, in view of the
great difference in gains between correct and wrong classification for class
1, compared with that for class 0. But at which point does this qualitative
reasoning fail? Imagine that the net gains had been as follows instead:

$\rotatebox[origin={c}]{90.0}{
\clap{{\parbox{50.00008pt}{\centering\scriptsize classifier\\\ output\\\
$1\hskip 10.50002pt0$\@add@centering}} }}\
\overbracket{\begin{bmatrix}[r]45\,\text{\$}&-335\,\text{\$}\\\
-65\,\text{\$}&165\,\text{\$}\end{bmatrix}}^{\clap{\textit{\parbox{42.00009pt}{\centering\scriptsize
true class\\\ $0\hskip 28.00006pt1$\@add@centering}}}}\ .$ (5)

Also in this case one could argue that there is a greater economic difference
between correct and wrong classification for class 1 than for class 0. The
true-negative rate should, therefore, again be the appropriate metric. Yet a
simple calculation analogous to the one of §  ‣ 0 Prologue: a short story
shows that classifier actually leads to the best average revenue:
$7.3\,\text{\$/component}$, vs $4.7\,\text{\$/component}$ for classifier .
Hence the true-negative rate is _not_ the appropriate metric in this case: our
qualitative reasoning failed us.

  2. (b)

A classifier favoured by the majority of available metrics can still turn out
_not_ to be the best one in practice.

  3. (c)

Most popular metrics are introduced by intuitive reasoning, ad hoc
mathematical operations, special assumptions (such as Gaussianity[e.g.][§ 31
p. 183 for the Matthews correlation coefficient]fisher1925_r1963 or other
statistical assumptions), and an analysis of special cases only. Unfortunately
this kind of derivations does not guarantee generalization to all cases, nor
that the proposed metric is uniquely determined by the chosen assumptions, nor
that it satisfies more general consistency requirements.

By contrast, consider the kind of derivation that starts from specific
qualitative requirements and mathematically proves the _uniqueness_ of a
particular formula satisfying them. Examples are the derivation of the Shannon
entropy as the _unique_ metric universally satisfying a set of basic
requirements for the amount of information shannon1948[§
3.2]woodward1953_r1964[also][]goodetal1968. Or the derivation of the
probability calculus as the _unique_ set of rules satisfying general rational
requirements for inductive reasoning, learning, and
prediction222cox1946,fine1973,halpern1999b,snow1998,snow2001[chs
1–2]jaynes1994_r2003; see also selfetal1987,cheeseman1988[ch.
12]russelletal1995_r2022.. Or the derivation of decision theory as the unique
framework guaranteeing a rational and optimal decision under uncertainty [§
15.2]russelletal1995_r2022[chs 2–3]vonneumannetal1944_r1955.

  4. (d)

Let us assume that some of the popular metrics identify the best algorithm ‘in
the majority of cases’ – although it is difficult to statistically define such
a majority, and no real surveys have ever been conducted to back up this
assumption. Yet, do we expect the end-user to simply _hope_ not to belong to
the unlucky minority? Is such uncertainty inevitable?

We cannot have a cavalier attitude towards this problem: life and death can
depend on it in some machine-learning applications [cf.][]howard1980. Imagine
a story analogous to the factory one, but in a medical setting instead. The
classifiers should distinguish between two tumour types, requiring two
different types of medical intervention. The confusion matrices are the same
(1) and (2). Correct and incorrect classification lead to the following
expected remaining life lengths for patients in a specific age range: [cf. the
discussion in][§ 11.2.9]soxetal1988_r2013

$\rotatebox[origin={c}]{90.0}{
\clap{{\parbox{50.00008pt}{\centering\scriptsize classifier\\\ output\\\
$1\hskip 10.50002pt0$\@add@centering}} }}\
\overbracket{\begin{bmatrix}[r]350\,\text{months}&0\,\text{months}\\\
300\,\text{months}&500\,\text{months}\end{bmatrix}}^{\clap{\textit{\parbox{56.00012pt}{\scriptsize\centering
true class\\\ $0\hskip 49.0001pt1$\@add@centering}}}}\ .$ (6)

These values might arise in several scenarios. For example, tumours of class 0
and 1 may require very different kinds of treatment. If a class 0 tumour is
misdiagnosed and not properly treated, it leads to immediate death (0 months);
if correctly diagnosed, its treatment is usually successful, leading to high
life expectancy (500 months). Class 0 tumours can be treated, but they lead to
a shorter life expectancy (350 months). If they are misdiagnosed as class 1,
however, the damage caused by class 1 treatment shortens this life expectancy
even further (300 months).

This matrix above is numerically equivalent to (4) up to a common additive
constant of $335$, so the final net gains are also shifted by this amount. It
is easy to see that the metrics are exactly as in Table 1, the majority
favouring classifier . And yet the use of classifier leads to a more than six-
month longer expected remaining life than classifier .

  5. (e)

Often it is not possible to temporarily deploy all candidate classifiers, as
our fictitious manager did, in order to observe which factually leads to the
best results. Or it may even be unethical: consider a situation like the
medical one above, where a classifier may lead to a larger number of immediate
deaths than another.

  6. (f)

Finally, all issues listed above are not caused by class imbalance (the
occurrence of one class with a higher frequency than another). In our story,
for example, the two classes were perfectly balanced. Class imbalance can make
all these issues worse jenietal2013,zhu2020.

But our story also points to a possible solution for all these issues. The
‘metric’ that ultimately proved to be relevant to the manager was the average
net monetary gain obtained by using a candidate classifier. In the medical
variation discussed in issue (d) above, it was the average life expectancy. In
either case, such metric could have been easily calculated beforehand, upon
gathering information about the average gains and losses of correct and
incorrect classification, collected in the matrix (4) or (6), and combining
these with statistics collected in the confusion matrix associated with the
classifier. Denoting the former kind of matrix by $(U_{ij})$ and the confusion
matrix by $(C_{ij})$, where $i$ indexes the classifier outputs (rows) and $j$
the true classes (columns), such a metric would have the formula

$\sumop\slimits@_{i,j}U_{ij}\ C_{ij}$ (7)

the sum extending to all matrix elements.

In the present work, we argue that formula (7) is indeed the only acceptable
metric for evaluating and comparing the performance of two or more
classifiers, each with its own confusion matrix $(C_{ij})$ collected on
relevant test data. The coefficients $U_{ij}$, called _utilities_ , are
problem-dependent. This formula is the _utility yield_ of a classifier having
confusion matrix $(C_{ij})$.

Our argument is based on _Decision Theory_ , an overview of which is given in
§ 2.

The utility yield (7) is a linear combination of the confusion-matrix
elements, with coefficients independent of the elements themselves. In § 3 we
explore some properties of this formula and of the space of such metrics for
binary classification. We also show that some common metrics such as
precision, $F_{1}$-measure, Matthews correlation coefficient, balanced
accuracy, and Fowlkes-Mallows index _cannot_ be written as a linear
combination of this kind (or a one-one function thereof). This impossibility
has two consequences. First, it means that these metrics are likely affected
by some kind of cognitive bias. Second, there exists _no_ classification
problem for which these metrics can correctly rank the performance of all
pairs of classifiers. Using any one of these metrics leaves open the
possibility that the evaluation is incorrect _a priori_. In § 5 we show that
this is also true for the Area Under the Curve of the Receiver Operating
Characteristic, and we offer some additional remarks about it from the
standpoint of decision theory.

On the other hand, metrics such as accuracy, true-positive rate, true-negative
rate can be written in the form (7). Consequently, each one has a set of
classification problems in which it correctly ranks the performance of _all_
pairs of classifiers.

What happens if we are uncertain about the utilities appropriate to a
classification problem? And what happens if the utilities are incorrectly
assessed? We show in § 4 that uncertainty about utilities still leads to a
metric of the form (7). We also show that an evaluation using incorrect
utilities, even with relative errors as large as 20% of the maximal utility,
still leads to a higher amount of correctly ranked classifiers than the use of
any of the popular metrics mentioned above.

We summarize and discuss our results in the final § 6.

##  2 Brief overview of decision theory

###  2.1 References

Here we give a brief overview of decision theory. We only focus on the notions
relevant to the problem of evaluating classifiers, and simply state the rules
of the theory. These rules are quite intuitive, but it must be remarked that
they are constructed in order to be logically and mathematically self-
consistent: see the following references. For a presentation of decision
theory from the point of view of artificial intelligence and machine learning,
see [russelletal1995_r2022, ch. 15]. Simple introductions are given by
north1968,raiffa1968_r1970,lindley1971_r1988[ch. 8]tribus1969jeffrey1965; and
a discussion of its foundations and history by [steeleetal2015_r2020]. For
more thorough expositions see [raiffaetal1961_r2000, fentonetal2019,
berger1980_r1985, savage1954_r1972]; and [soxetal1988_r2013,
huninketal2001_r2014] for a medical perspective. See also Ramsey’s
[*]ramsey1926 insightful and charming pioneering discussion.

###  2.2 Decisions and classes

Decision theory makes a distinction between

  * •

the possible situations we are uncertain about: in our case, the possible
classes;

  * •

the possible decisions we can make.

This distinction is important because it prevents the appearance of various
cognitive biases kahnemanetal1982_r2008,gilovichetal2002_r2009,kahneman2011 in
evaluating the probabilities and frequencies of the possible situations on the
one hand, and the values of our decisions on the other. Examples are the
scarcity biascamereretal1989,kimetal1999,mittoneetal2009 “this class is rare,
_therefore_ its correct classification must lead to high gains”, and plain
wishful thinking: “this event leads to high gains, _therefore_ it is more
probable”.

Often even the number of classes and the number of decisions differ. But in
using machine-learning classifiers, one typically considers situations where
the set of available decisions and the set of possible classes have some kind
of natural correspondence and equal cardinality. In a ‘cat vs dog’ image
classification, for example, the classes are ‘cat’ and ‘dog’, and the
decisions could be ‘put into folder Cats’ vs ‘put into folder Dogs’. In a
medical application the classes could be ‘ill’ and ‘healthy’ and the decisions
‘treat’ vs ‘dismiss’. As already mentioned, most of our discussions and
examples focus for simplicity on binary classification.

###  2.3 Utilities and maximization of expected utility

To each decision we associate several _utilities_ , depending on which of the
possible classes is actually true. A utility may, for instance, equal a gain
or loss in money, energy, number of customers, life expectancy, or quality of
life, measured in appropriate units; or it may equal a combination of such
quantities.

These utilities are collected into a _utility matrix_ $(U_{ij})$, like the
ones shown in formulae (4), (5), (6). The component $U_{ij}$ is the utility of
the decision corresponding to class $i$ if class $j$ is true, or simply the
utility of class $i$ conditional on class $j$.

In an individual classification instance, if we know which class is true, then
the optimal decision is the one having maximal utility among those conditional
on the true class. If, on the other hand, we are uncertain about which class
is true, with probability $p_{j}$ for class $j$ such that
$\sumop\slimits@_{j}p_{j}=1$, then decision theory states that the optimal
decision is the one having maximal _expected_ utility $\bar{U}_{i}$, defined
as the expected value of the utility of decision $i$ with respect to the
probabilities of the various classes:

$\bar{U}_{i}\coloneqq\sumop\slimits@_{j}U_{ij}\ p_{j}\ .$ (8)

In formulae, this principle of _maximization of expected utility_ is

$\text{choose class}\quad
i^{*}=\operatorname*{arg\,max}_{i}\\{\bar{U}_{i}\\}\equiv\operatorname*{arg\,max}_{i}\bigg{\\{}\sumop\slimits@_{j}U_{ij}\
p_{j}\bigg{\\}}\ .$ (9)

A very important result in decision theory is that basic requirements of
rational decision-making imply that there _must_ be a set of utilities
underlying the decisions of a rational agent, and the decisions must obey the
principle of maximization of expected utility[§ 15.2]russelletal1995_r2022[chs
2–3]vonneumannetal1944_r1955.

How are utilities determined? They are obviously problem-specific and cannot
be given by the theory (which would otherwise be a model rather than a
theory). Utilities can be obvious in decision problems involving gains or
losses of measurable quantities such as money or energy (the utility of money
is usually not equal to the amount of money, the relationship between the two
being somewhat logarithmic [e.g.][pp. 203–204]north1968[ch.
4]raiffa1968_r1970). In medical problems they can correspond to life
expectancy and quality of life; see for example [soxetal1988_r2013, esp. ch. 8
and § 11.2.9] and [huninketal2001_r2014, esp. ch. 4] on how such health
factors are transformed into utilities.

The final utility of a single classification instance may depend, in some
cases, on a sequence of further uncertain events and further decisions. In the
story of §  ‣ 0 Prologue: a short story, for instance, the misclassification
of a short-durability component as a long-durability one leads the final
device to break only in a high fraction of cases, and in such cases the end
customer requires a refund in a high fraction of subcases; the refunded amount
may even depend on further circumstances. The negative utility
$U_{01}=-335\,\text{\$}$ in table (4) comes from a statistical average of the
losses in all these possible end results. This is the topic of so-called
decision networks or influence diagrams [Besides the general references
already given:][§ 15.5]russelletal1995_r2022howardetal1984b_r2005[for a step-
by-step tutorial:][]raiffa1968_r1970. The decision-theory subfield of _utility
theory_ gives rules that guarantee the mutual consistency of a set of
utilities in single decisions or decision networks. For simple introductions
to utility theory see [russelletal1995_r2022, § 15.2], [north1968, pp.
201–205], and the references given at the beginning of the present section.

In the present work, we do not worry about such rules in order not to
complicate the discussion: they should be approximately satisfied if the
utilities of a problem have been carefully assessed.

##  3 Evaluation of classifiers from a decision-theoretic perspective

###  3.1 Admissible evaluation metrics for classification problems

Maximization of expected utility is the ground rule for rational decision
making [We discuss and use it in our companion work][]dyrlandetal2022b. In the
present work we focus on the stage where a large number of classifications
have already been made by a classifier on a test dataset with $N$ data. Denote
by $F_{ij}$ the number of instances in which the classifier chose class $i$
and the true class was $j$. Then $(F_{ij})$ is the confusion matrix of the
classifier on this particular test set. For all instances in which the
classifier chose class $i$ and the true class was $j$, a utility $U_{ij}$ is
eventually gained. The total utility yielded by the classifier on the test set
is therefore $\sumop\slimits@_{ij}U_{ij}\ F_{ij}$. Dividing by $N$ we obtain
the average utility per datum, which we call the _utility yield_ ; it can be
written as

$\sumop\slimits@_{ij}U_{ij}\ C_{ij}$ (10)

where $C_{ij}\coloneqq F_{ij}/N$ is the relative frequency of choice $i$ and
true class $j$, and $(C_{ij})$ is the normalized confusion matrix.

_The utility yield, formula ( 10), is therefore the natural metric to evaluate
and compare the performance of classifiers on a test set for a classification
problem characterized by the utility matrix $(U_{ij})$_.

Note how the utilities $U_{ij}$ do depend on the frequencies $F_{ij}$ or
$C_{ij}$. If they did, it would mean that we had waited until _all_
classification instances had been made in order to assess the value of each
_single_ instance. In virtually all classification problem we can think of,
this would be a source of evaluation bias, such as the scarcity bias mentioned
in § 2.2. It would, moreover, be an impossible procedure in contexts where the
consequence of a single classification is manifest before the next
classification is made.

If we modify the elements of a utility matrix by a common additive constant or
by a common positive multiplicative constant,

$U_{ij}\mapsto a\ U_{ij}+b\qquad a>0\ ,$ (11)

then the final utilities yielded by a classifier with a particular confusion
matrix are modified by the same constants. The ranking of any set of
classifiers will therefore be the same. After all, an additive constant or a
positive factor represent only changes in the zero or the measurement unit of
our utility scale [cf.][§ 15.2.2]russelletal1995_r2022. Such changes should
not affect a decision problem. Indeed, the fact that they do not is another
example of the logical consistency of decision theory.

###  3.2 Space of utility matrices for binary classification

Let us consider a problem of binary classification. It is characterized by a
matrix of $2\times 2$ utilities. We suppose that they are not all equal; the
choice of class would be immaterial otherwise, and the classification problem
trivial. We can use the freedom of choosing a zero and measurement unit to
bring the utility matrix to a standard form. Let us choose them such that the
maximum utility is $1$ and the minimum utility is $0$ (note that this value
may still correspond to an actual monetary loss, for example). That is, we are
effecting the transformation

$U_{ij}\mapsto\frac{U_{ij}-\min(U_{ij})}{\max(U_{ij})-\min(U_{ij})}\ .$ (12)

With this convention, it is clear that we only have two degrees of freedom in
choosing the utility matrix of a binary-classification problem. As a
consequence, _the space (more precisely: manifold) of possible evaluation
metrics for binary classifications is two-dimensional_. In order to evaluate
candidate classifiers for a binary-classification problem, we must choose a
point from this space.

?figurename? 1: Space of utility matrices for binary classification.

We can represent this space as in fig. 1. The centre is the utility matrix
with equal maximum utilities for correct classification and equal minimum
utilities for incorrect classification; we shall see later that it corresponds
to the use of accuracy as the evaluation metric. Moving to the left from the
centre, the utility for correct classification of class 1 decreases with
respect to class 0; vice versa moving to the right. Moving upwards from the
centre, the utility for misclassification of class 1 increases; moving
downwards, the utility for misclassification of class 0 increases. We have
excluded utility matrices in which misclassification has a higher utility than
correct classification (although they may occur in some situations); they
would appear in the missing upper-left and lower-right corners. Fixing $(x,y)$
axes through the centre of the set, a utility matrix has coordinates

$\begin{bmatrix}1-x\ \deltaup(x>0)&y\ \deltaup(y>0)\\\ -y\ \deltaup(y<0)&1+x\
\deltaup(x<0)\end{bmatrix}\ ,\qquad\lvert x\rvert,\lvert y\rvert\leqslant 1\
.$ (13)

Note that this representation is _not_ meant to reflect any convex or metric
properties, however. No metric or distance is defined in the space of utility
matrices. Convex combination is defined if we drop the normalization (12) but
it is not correctly reflected in the representation of fig. 1.

###  3.3 Relationship with common metrics

In § 3.1 we found that the most general evaluation metric according to
decision theory must be a linear combination of the confusion-matrix elements.
The coefficients of this linear combination do not depend on the confusion-
matrix elements themselves; such a dependence usually reflects some sort of
cognitive bias. Which common popular metrics adhere to this mathematical form?
We want to answer this question in the binary-classification case while giving
as much allowance as possible in the typical context in which popular metrics
are used.

Consider the case in which we are comparing several classifiers _on the same
test set_. The number of data $N$ and the relative frequencies $f_{0},f_{1}$
with which the two classes ‘$0$’, ‘$1$’ occur in the test set are fixed and
constant for all classifiers under evaluation.

A classifier yields a normalized confusion matrix $(C_{ij})$ which we write in
the format

$\rotatebox[origin={c}]{90.0}{
\clap{{\parbox{50.00008pt}{\centering\scriptsize classifier\\\ output\\\
$1\hskip 10.50002pt0$\@add@centering}} }}\
\overbracket{\begin{bmatrix}[r]C_{00}&C_{01}\\\
C_{10}&C_{11}\end{bmatrix}}^{\clap{\textit{\parbox{42.00009pt}{\centering\scriptsize
true class\\\ $0\hskip 21.00005pt1$\@add@centering}}}}\ .$

Owing to the constraints $C_{00}+C_{10}\equiv f_{0}$ and $C_{01}+C_{11}\equiv
f_{1}$ we can always make two elements of the confusion matrix appear or
disappear from any formula, replacing them with expressions involving the
remaining two elements and the class frequencies. To avoid ambiguities in
interpreting the functional form of mathematical formulae, let us agree to
always express them in terms of $C_{00}$ and $C_{11}$ only, making the
replacements $C_{10}=f_{0}-C_{00}$, $C_{01}=f_{1}-C_{11}$ wherever necessary.

Recall that, given a utility matrix, we can always modify its elements by a
common positive multiplicative constant $a$ and by a common additive constant
$b$, eq. (11), because such a modification corresponds to a change of unit and
zero of the utility scale. With such a modification the evaluation metric (10)
takes the equivalent form

$a\ \sumop\slimits@_{ij}\ U_{ij}\ C_{ij}+b$ (14)

because $\sumop\slimits@_{ij}C_{ij}\equiv 1$. Writing the sum explicitly and
rewriting the elements $C_{10},C_{01}$ in terms of $C_{00},C_{11}$ as
discussed above, this formula becomes

$a\ (U_{00}-U_{10})\ C_{00}\ +\ a\ (U_{11}-U_{01})\ C_{11}\ +\ a\ f_{0}\
U_{10}+a\ f_{1}\ U_{01}+b\ .$ (15)

Since in the present context $N,f_{0},f_{1}$ are constants, we are free to
construct the arbitrary constants $a>0$ and $b$ from them in any way we
please:

$a=a(N,f_{0},f_{1})>0\ ,\qquad b=b(N,f_{0},f_{1})\ .$ (16)

We can also use this freedom to include the term $a\ f_{0}\ U_{10}+a\ f_{1}\
U_{01}$ into $b$ in the formula above. We conclude that _an evaluation metric
for binary classification complies with decision theory if and only if it can
be written in the general form_

$a(N,f_{0},f_{1})\ X\ C_{00}+a(N,f_{0},f_{1})\ Y\ C_{11}+b(N,f_{0},f_{1})$
(17)

_where $X,Y$ are real constants that do not depend on
$C_{00},C_{11},N,f_{0},f_{1}$; and $a(\mathord{\,\cdot\,})>0$,
$b(\mathord{\,\cdot\,})$ are arbitrary functions of $N,f_{0},f_{1}$ only._

A monotonic function (such as an exponential) of the expression above is also
admissible if we only require a comparison score to rank several classifiers
from best to worst.

Let us examine some common evaluation metrics for binary classification from
this point of view. We write their formulae in terms of $C_{00},C_{11}$.

The following metrics are particular instances of formula (17):

  * 3

_Accuracy:_ $C_{00}+C_{11}$. We have $a=1$, $X=Y=1$, $b=0$. Indeed it
corresponds to the utility yield based on the identity utility matrix
$(U_{ij})=\begin{bmatrix}[r]1&0\\\ 0&1\end{bmatrix}$ (or equivalently a
utility matrix that assigns the same utility to the correct classification of
any class, and the same, lower utility to the misclassification of any class).

  * 3

_True-positive rate (recall):_ $C_{00}/f_{0}$. Here $a=1/f_{0}$, $X=1$, $Y=0$,
$b=0$. It corresponds to using the utility matrix $\begin{bmatrix}[r]1&0\\\
0&0\end{bmatrix}$.

  * 3

_True-negative rate (specificity):_ $C_{11}/f_{1}$. Here $a=1/f_{1}$, $X=0$,
$Y=1$, $b=0$. It corresponds to using the utility matrix
$\begin{bmatrix}[r]0&0\\\ 0&1\end{bmatrix}$.

The following metrics instead _cannot_ be written in the form (17), nor as
monotonic functions of that form:

  * 7

_Precision:_ $C_{00}/(C_{00}-C_{11}+f_{1})$. Non-linear in $C_{00},C_{11}$.

  * 7

_$F_{1}$ -measure:_ $2C_{00}/(C_{00}-C_{11}+1)$. Non-linear in
$C_{00},C_{11}$. The same is true for the more general $F$-measures.

  * 7

_Matthews correlation coefficient:_
$\frac{f_{1}\,C_{00}+f_{0}\,C_{11}}{\sqrt{f_{0}\ f_{1}\ (f_{1}+C_{00}-C_{11})\
(f_{0}+C_{11}-C_{00})}}$. Non-linear in $C_{00},C_{11}$.

  * 7

_Fowlkes-Mallows index:_ $C_{00}/\sqrt{f_{0}\ (f_{1}+C_{00}-C_{11})}$. Non-
linear in $C_{00},C_{11}$.

  * 7

_Balanced accuracy:_ $C_{00}/(2f_{0})+C_{11}/(2f_{1})$. Despite being linear
in $C_{00},C_{11}$ and an average of two metrics (true-positive and true-
negative rate) that are instances of formula (17), it is not an instance of
that formula, because the two averaged metrics involve different
$a(\mathord{\,\cdot\,})$ functions.

We see that many popular evaluation metrics do not comply with the principles
of decision theory. Any such metric suffers from two problems.

First, as discussed in § 2, the metric involves an interdependence of
utilities and classification frequencies, which typically implies some form of
cognitive bias[discuss such biases regarding the $F_{1}$-measure]handetal2018.

Second, the ranking of confusion matrices yielded by the metric does not fully
agree with that yielded by any utility matrix – a full agreement would
otherwise imply that the metric could be written in the form (17). Some
confusion matrices must therefore be incorrectly ranked. Since any rational
classification problem is characterized by some underlying utility matrix,
this means that the non-compliant metric will always lead to some wrong
evaluations. By contrast, compliant metrics such as the accuracy give
completely correct rankings for all pairs of confusion matrices in specific
sets of classification problems.

The second phenomenon is illustrated in the plots of figs 2–3.

?figurename? 2: Relationship between various evaluation metrics and actual
utility yields for two different binary-classification problems with
underlying utility matrices $\begin{bmatrix}[r]1&0\\\ 0&1\end{bmatrix}$ (left
column) and $\begin{bmatrix}[r]1&0\\\ 0&0\end{bmatrix}$ (right column). All
confusion matrices (blue dots) are obtained from a dataset with 50%/50% class
balance. Pairs of red triangles in a plot show two confusion matrices that are
wrongly ranked by the metric (y-axis) with respect to the actual utility yield
(x-axis). Clearly, there can even be three or more confusion matrices ranked
in completely reverse order by the metric. The accuracy gives correct
evaluations for the classification problem on the left column; and the true-
positive rate, for the one on the right.
?figurename? 3: As for fig. 2 but for confusion matrices obtained from an
imbalanced dataset with 90% occurrence of class 0 (‘positive’) and 10% of
class 1 (‘negative’).

Each blue dot in a plot represents a hypothetical confusion matrix obtained
from a test dataset in a binary classification. The dot’s coordinates are the
utility yield of that confusion matrix according to a particular utility
matrix underlying the classification problem, and the score of the confusion
matrix according to another metric. The underlying utility matrix is
$\begin{bmatrix}[r]1&0\\\ 0&1\end{bmatrix}$ for all plots in the left column,
and $\begin{bmatrix}[r]1&0\\\ 0&0\end{bmatrix}$ for all plots in the right
column. The other metrics considered, one for each row of plots, are accuracy,
true-positive rate (recall, class 0 being ‘positive’), $F_{1}$-measure,
Matthews correlation coefficient.

The confusion matrices are selected by first fixing a proportion of classes in
the dataset, which is 50%/50% (balanced dataset) for all plots in fig. 2 and
90%/10% (imbalanced dataset) for all plots in fig. 3. Then a true-positive
rate and a true-negative rate are independently selected  from the range
$[1/2,1]$, with a probability linearly increasing in the rate (median of 0.85,
lower and upper quartiles at 0.75 and 0.93; see side plot). These confusion
matrices therefore represent the classification statistics produced by
classifiers that tend to have high true-negative and true-positive rates – as
is clear from the fact that the points tend to accumulate on the upper-right
corners of the plots.

We see that the accuracy (first-row plots) always gives correct relative
evaluations of all confusion matrices when the underlying utility matrix is
equivalent to $\begin{bmatrix}[r]1&0\\\ 0&1\end{bmatrix}$ (left column): the
y-coordinate is a monotonically increasing function – in fact a linear
function – of the x-coordinate. Accuracy is indeed the utility yield
corresponding to the identity utility matrix. The true-positive rate (second-
row plots) always gives correct relative evaluations (provided the test set is
the same) when the underlying utility matrix is equivalent to
$\begin{bmatrix}[r]1&0\\\ 0&0\end{bmatrix}$ (right column).

On the other hand, if any of these two metrics is used for a problem having a
different underlying utility matrix, then there is no deterministic
relationship between the metric’s score and the actual utility yield. In this
case it is always possible to find two or more confusion matrices for which
the metric gives completely reversed evaluations with respect to the actual
utility yield. In other words, the confusion matrix – and associated algorithm
– which is worst according to the true utility, is ranked best by the metric;
and vice versa. Pairs of red triangular shapes in a plot are examples of such
confusion matrices wrongly ranked by the y-axis metric.

Metrics such as accuracy and true-positive rate, complying with formula (17),
thus require us to rely on evaluation _luck_ only when they are used in the
wrong classification problem.

The plots for the $F_{1}$-measure (third-row plots) and Matthews correlation
coefficient (fourth-row plots) show that these two metrics do not have any
functional relationship with the actual utility yield. It is again always
possible to find two or more confusion matrices for which either metric gives
completely reversed evaluations with respect to the actual utility yield. But
for these two metrics, unlike accuracy and true-positive rate, cases of
incorrect evaluation will _always_ occur in _every_ classification problem.

Metrics such as $F_{1}$-measure and Matthews correlation coefficient, not
complying with formula (17), thus _always require us to rely on luck in our
evaluations_. There are no classification problems for which these metrics
lead to always correct evaluations.

A metric non-compliant with decision theory can lead to a large number of
correct results for some classification problems and test sets. The bottom-
left plot of fig. 2, for instance, shows that the Matthews correlation
coefficient is almost a monotonically increasing deterministic function of the
utility yield when the underlying utility matrix is the identity and the
dataset is balanced (but it is not when the underlying utility matrix is
$\begin{bmatrix}[r]1&0\\\ 0&0\end{bmatrix}$ or the dataset is imbalanced; see
corresponding plots). Such an occasional partial agreement is useless,
however. Knowledge of the utility matrix is a prerequisite for relying on such
partial agreement– but given such knowledge we can directly use the actual
utility yield instead, which has an exact agreement and is easier to compute.

##  4 Unknown or incorrect utilities

So far, we have argued that the natural evaluation metric for a classifier is
the utility yield of its confusion matrix, according to the utilities
underlying the classification problem of interest. We have also argued that
many popular metrics, those not complying with formula (17), must always a
priori lead to instances of incorrect evaluation. Our arguments are based on
the principles of decision theory.

Several interrelated questions spring from our arguments, though:

  * •

What to do when we are uncertain about the utilities underlying a
classification problem?

  * •

What happens if the utilities we use are actually wrong, that is, not the true
ones underlying the problem?

  * •

How often do uncompliant metrics such as $F_{1}$-measure or Matthews
correlation coefficient lead to incorrect results, on average?

In fact, if a small error in the assessment of the utilities led to a large
number of wrong evaluations, while non-compliant metrics led to a small number
of wrong evaluations on average, then all the rigorousness of decision-
theoretic metrics would be useless in practice, and non-compliant metrics
would be best for real applications.

This is not the case, however. We now discuss how to deal with uncertainty
about the utilities and present an important result: Using wrong utilities,
even with relative errors almost as large as 20% of the maximum utility, still
leads to fewer incorrect relative evaluations on average than using many
currently popular metrics.

###  4.1 Unknown utilities; average performance on several classification
problems

Dealing with unknown utilities is straightforward. Suppose we are uncertain
whether the utility matrix appropriate to a classification problem is
$\textbf{{{U}}}^{(1)}\equiv\bigl{(}U^{(1)}_{ij}\bigr{)}$, or
$\textbf{{{U}}}^{(2)}$, or $\textbf{{{U}}}^{(3)}$, and so on, where the number
of alternatives can even be infinite or continuous. Each alternative
$\textbf{{{U}}}^{(a)}$ has a probability $q_{a}$, or probability density
$q(a)\ \mathrm{d}a$ in the continuous case. Then _for this classification
problem, we should use the expected utility matrix_

${\mkern 1.5mu{\hat{\mkern-1.5mu\textbf{{{U}}}\mkern-1.5mu\mkern
2.0mu}\mkern-2.0mu}{}\mkern 1.5mu}\coloneqq q_{1}\ \textbf{{{U}}}^{(1)}+q_{2}\
\textbf{{{U}}}^{(2)}+q_{3}\ \textbf{{{U}}}^{(3)}+\dotsb$ (18)

_or ${\mkern 1.5mu{\hat{\mkern-1.5mu\textbf{{{U}}}\mkern-1.5mu\mkern
2.0mu}\mkern-2.0mu}{}\mkern 1.5mu}\coloneqq\int
q(a)\,\textbf{{{U}}}^{(a)}\,\mathrm{d}a$ in the continuous case_.

We only give a sketch of the proof of this intuitive result [see e.g.][esp.
ch. 3]raiffa1968_r1970. If we are uncertain about the utility matrix, then we
have a double decision problem: choosing the optimal utility and choosing the
optimal class. If the true utility matrix is, for instance,
$\textbf{{{U}}}^{(2)}\equiv\bigl{(}U^{(2)}_{ij}\bigr{)}$, and the true class
is class $0$, then choosing class $1$ would yield a utility $U^{(2)}_{10}$,
choosing class $0$ would yield a utility $U^{(2)}_{00}$, and so on. Our double
decision problem is thus characterized by a rectangular utility matrix that is
the row-concatenation of the utility matrices $\textbf{{{U}}}^{(a)}$. We make
the realistic judgement that the probabilities $q_{a}$ of the utility matrices
and the probabilities $p_{j}$ of the classes are independent, so that
$q_{a}\cdot p_{j}$ is the probability that the true utility matrix is
$\textbf{{{U}}}^{(a)}$ and the true class is $j$. The principle of maximum
expected utility, § 2.3 eq. (9), then leads to the maximization of the
expected utilities

$\bar{U}_{i}\coloneqq\sumop\slimits@_{j,a}U^{(a)}_{ij}\ q_{a}\cdot
p_{j}\equiv\sumop\slimits@_{j}\biggl{[}\underbrace{\sumop\slimits@_{a}q_{a}\
U^{(a)}_{ij}}_{{\mkern 1.5mu{\hat{\mkern-1.5mu\textbf{{{U}}}\mkern-1.5mu\mkern
2.0mu}\mkern-2.0mu}{}\mkern 1.5mu}}\biggr{]}\ p_{j}$ (19)

in which the expected utility matrix (18) appears as an ‘effective’ utility
matrix to be used for the class-decision problem alone.

If our uncertainty is symmetric with respect to the utilities conditional on
the different classes – for instance, our uncertainty about the utilities
conditional on class $0$ is the same as on class $1$ – then the expected
utility matrix is equivalent to the identity matrix. The utility yield is in
this case equal to the accuracy. The accuracy is therefore the natural
evaluation metric to use if we are in a complete state of uncertainty
regarding the underlying utilities. This fact is indeed reflected in some
results discussed in § 4.2.

For binary classification the set of possible utility matrices can be
represented as in fig. 1, as discussed in § 3.2. Our uncertainty about the
true underlying utility matrix corresponds to a discrete or continuous
distribution of probability over this set. Note, however, that the expected
utility matrix (18) does _not_ correspond to the mass-centre of the
distribution, because of the peculiar coordinate system used in that figure.
The actual mass-centre is obtained by representing the set of utility matrices
as a two-dimensional surface (a tetrahedron) in three-dimensional space. For
brevity we do not discuss this representation in the present work.

The procedure of averaging utilities, formula (18), also applies if we want to
evaluate how a classifier performs on average on several classification
problems, which differ in their utility matrices. Again, what we need to use
is the average of their utility matrices.

###  4.2 Consequences of wrong utility assessments and comparison with common
metrics

It may happen that our assessment of the utility matrix of a classification
problem is incorrect, especially if it has been made on semi-quantitative
grounds owing to a lack of information. Then our comparative evaluations of
classifiers may also end up being incorrect. What is the probability of an
incorrect comparative evaluation, on average, in such cases? and how does it
depend on the amount of error in the utilities? Is it higher than the
probability of incorrect evaluation by other metrics?

A precise answer to these questions is extremely difficult if not impossible
because to define ‘on average’ we would need to conduct a survey of
classification problems of any kind, collecting statistics about their
underlying utility matrices, about the confusion matrices of candidate
classification algorithms for their solution, and about the errors committed
in assessing utilities. We try to give a cursory answer to the questions above
for the binary-classification case, based on the following assumptions and
judgements:

  1. (i)

Two possible distributions of true utility matrices on the set of fig. 1 (in
that coordinate system):  1. a uniform distribution;  2. a bivariate
(truncated) gaussian distribution centred on the identity matrix
$\begin{bmatrix}[r]1&0\\\ 0&1\end{bmatrix}$ and with standard deviation $1/3$
in the $x$ and $y$ coordinates of eq. (13), illustrated in fig. 5.

  2. (ii)

A distribution of confusion matrices for which the fraction of one class is
uniformly distributed in $[0,1]$, and the true-positive and true-negative
rates are independently distributed in $[0.5,1]$ with linearly increasing
probabilities (median of 0.85, lower and upper quartiles at 0.75 and 0.93; see
side plot on p. 3.3). This means that we consider problems with highly
imbalanced data to be as common as problems with balanced data (a realistic
assumption, according to our experience), and candidate classifiers to be
generally good.

  3. (iii)

A truncated gaussian distribution of error around each true utility-matrix
element, centred on the true utility value. We consider standard deviations
ranging from $0$ to $0.3$. The gaussian must be truncated because each true
utility has a value between $0$ and $1$, and because we require the utilities
of correct classifications to be larger than those of incorrect ones. Figure 5
illustrates the extent of such an error in the space of utility matrices, for
standard deviations equal to $0.1$ (blue triangles) and $0.2$ (red squares).

?figurename? 4: Truncated gaussian distribution in the space of utility
matrices of fig. 1, described in item (i).

?figurename? 5: Extents of errors having standard deviations $0.1$ (blue
triangles) and $0.2$ (red squares), around the utility matrices
$\begin{bmatrix}[r]0.5&0.5\\\ 0&1\end{bmatrix}$ and $\begin{bmatrix}[r]1&0\\\
0.5&0.5\end{bmatrix}$ (black diamonds).

Under these assumptions, we calculate how often a pair of classifiers, having
two confusion matrices with the same class proportions, is evaluated in
reverse order, with respect to their true utility yield, when an incorrect
utility matrix or another metric is used for the evaluation. This calculation
is an integration problem that we solve by Monte Carlo sampling. The procedure
is intuitive:

  1. 1.

Select a ‘true’ utility matrix according to the distribution (i).

  2. 2.

Select errors around the elements of the true utility matrix, according to the
distribution (iii), and add them to it.

  3. 3.

Select a class proportion and then two confusion matrices having that class
proportion (the class proportion must be the same since the matrices are
obtained from the same data), according to the distributions (ii).

  4. 4.

Calculate the signed difference between the true utility yield of the second
confusion matrix and that of the first confusion matrix, using the true
utility from step 1. If this difference is positive, then the second confusion
matrix has higher utility than the first; if negative, then the first
confusion matrix has higher utility than the second.

  5. 5.

    1. a.

Consider several metrics (precision, Matthews correlation coefficient, and so
on). For each, calculate the signed difference between the score it gives to
the second confusion matrix, and the score it gives to the first.

    2. b.

Consider the erroneous utility matrix from step 2. Calculate the signed
difference between the utility yield of the second confusion matrix and that
of the first confusion matrix, using this erroneous utility matrix.

In either case, a positive difference means that the second confusion matrix
is ranked ‘best’ and the second ‘worst’, and vice versa for a negative
difference.

  6. 6.

Now go through the signed differences obtained in step 5, and compare them, in
turn, with the signed difference obtained in step 4. If the difference from
step 5 has opposite sign to that of step 4, then the two confusion matrices
are oppositely and incorrectly ranked by the corresponding metric or by the
erroneous utility matrix.

The results of this sampling procedure for the case of uniform distribution of
true utility matrices, several metrics, and utilities affected by errors with
$0.1$ standard deviation, are shown in fig. 6.

?figurename? 6: Relationship between difference in utility yields according to
a ‘true’ utility matrix, and difference in scores according to other metrics
including an incorrectly assessed utility matrix (error with $0.1$ standard
deviation). Points landing in the II or IV quadrants represent pairs of
confusion matrices that were wrongly compared.

?figurename? 7: Dependence of the proportion of incorrectly ranked pairs of
confusion matrices, on the standard deviation of the assessment error on the
utilities. Top plot: case with uniform distribution of true utility matrices.
Bottom plot: case with gaussian distribution of true utility matrices, as in
fig. 5.

Each point represents a pair of confusion matrices (step 3); its coordinates
are the true utility yield and either the score given by a metric or (last
plot) the yield according to the incorrect utility matrix. The red or yellow
triangular points in the II and IV quadrants (discordant signs) are
incorrectly ranked pairs. The percentages of incorrect rankings are calculated
from $10^{6}$ samples, giving slightly more than one decimal significant
digit; fewer samples are shown in the plots.

The plots are displayed in order (left-right, top-bottom) of decreasing
percentages of incorrect rankings. The accuracy metric proves to be the best
among the ones considered, leading to $8.7\%$ incorrect pairwise rankings. But
we see that a utility matrix affected by gaussian errors with $0.1$ standard
deviation is even better, yielding $4\%$ incorrect pairwise rankings.

The dependence of the fraction of incorrect rankings on the standard deviation
of the error affecting the utilities is shown in the plots of fig. 7, for the
case of uniform distribution (top plot) and gaussian distribution (bottom
plot) of true utility matrices. It is approximately linear. The plots also
report the fractions of incorrect rankings for the other metrics. We see that
evaluations based on a utility matrix affected by errors with standard
deviation up to $0.15$ or even $0.25$ are still more reliable than evaluations
based on the other reported metrics. This is a remarkable fact, considering
that errors with such standard deviations are quite large, as was shown in
fig. 5.

A utility error with standard deviations around $0.25$ covers the whole space
of utility matrices almost uniformly (cf fig. 5). Such a large error means
that we are almost completely uncertain about the utilities to start with. It
therefore makes sense that the accuracy, equivalent to using the identity
utility matrix, becomes a more reliable metric when this error level is
reached: as we saw in § 4.1, the identity utility matrix is the natural one to
use in a state of complete uncertainty about the utilities. This result is
just another example of the internal consistency of Decision Theory.

##  5 What about the area under the curve of the receiver operating
characteristic?

Another very common metric for evaluating binary classifiers is the Area Under
the Curve of the Receiver Operating Characteristic, or ‘area under the curve’
for short. This metric can only be used for particular classifying algorithms,
and its meaning is different from that of the metrics reviewed so far. For
these reasons, we leave a full discussion of it to future works and only offer
a couple of remarks here.

The area under the curve can only be computed for classifiers that output a
continuous variable rather than a class. A threshold for this variable
determines whether its value predicts one class or the other. Different
choices of threshold lead to different pairs of false-positive rate $f$ (which
is $1-{}$true-negative rate) and true-positive rate $t$ in a given test set.
These pairs can be plotted as a curve $f\mapsto t(f)$ on a graph with
corresponding axes. Given the proportion of classes in the test set, every
point on the curve corresponds to a possible confusion matrix $C_{ij}(f)$ that
the classifier can produce depending on the threshold chosen. The area
subtended by the curve is a weighted average of true-positive rates with a
peculiar choice of weights; the weights are uniform as a function of the
false-positive rate, but generally not uniform as a function of the threshold,
for example. The meaning and proper use of the receiver operating
characteristic are discussed in a classic by metz1978, see especially p. 290.

From the standpoint of decision theory, two remarks can be made[similar points
are made by][]bakeretal2001,loboetal2008. First, according to the principle of
maximum expected utility, § 2.3, we should choose a threshold and
corresponding false-positive rate $f^{*}$ such as to maximize the utility
yield, given by eq. (10):

$\text{\small choose}\quad
f^{*}=\operatorname*{arg\,max}_{f}\bigg{\\{}\sumop\slimits@_{i,j=0}^{1}U_{ij}\
C_{ij}(f)\bigg{\\}}\ .$ (20)

Any other values of $f$ and of the threshold are irrelevant. Averages over $f$
values are therefore irrelevant as well. Second, suppose our goal is to
evaluate the average performance over several possible classification
problems. In that case, the quantities to be averaged are the utility matrices
of those classification problems, as discussed in § 4.1, yielding a unique
expected utility matrix. Once this is computed, we go back to a single choice
of $f$ according to our first remark.

Owing to these issues, the area under the curve suffers from the same problems
as the non-compliant metrics discussed in § 3.3: in every classification
problem, it always leads to cases of incorrect evaluation.

A correct use of the receiver-operating-characteristic curve $t(f)$ can be
made, however. It is explained in [metz1978, section _Cost/Benefit Analysis_
p. 295], and in [soxetal1988_r2013, § 5.7.4] (curiously Sox et al. also
mention the generally erroneous criterion of the area under the curve).

Denote the proportion of class $0$ (positive) in the test set by $B$. The
confusion matrix as a function of $f$ is then

$\begin{bmatrix}[r]C_{00}(f)&C_{01}(f)\\\
C_{10}(f)&C_{11}(f)\end{bmatrix}=\begin{bmatrix}B\ t(f)&(1-B)\ f\\\ B\
[1-t(f)]&(1-B)\ (1-f)\end{bmatrix}\ .$ (21)

The sum in formula (20) above can then be explicitly written, rearranging some
terms,

$\sumop\slimits@_{i,j=0}^{1}U_{ij}\ C_{ij}(f)\equiv(U_{00}-U_{10})\ B\
t(f)-(U_{11}-U_{01})\ (1-B)\ f+{}\\\\[-6.0pt] U_{10}\ B\ +U_{11}\ (1-B)\ .$
(22)

The principle of maximum expected utility (20) is then equivalent to the
following condition, obtained using the explicit sum above but dropping the
constant term on the second line for simplicity:

$\text{\small choose}\quad
f^{*}=\operatorname*{arg\,max}_{f}\big{\\{}(U_{00}-U_{10})\ B\
t(f)-(U_{11}-U_{01})\ (1-B)\ f\big{\\}}\ .$ (23)

The function in braces is monotonically increasing because $t(f)$ is (we
assume, as always, that the utility of correct classification of a class is
higher than that of misclassification, so $U_{00}-U_{10}\geqslant 0$ and
$U_{11}-U_{01}\geqslant 0$). Its maximum can thus be found by setting its
derivative to zero:

$\text{\small choose }f^{*}\text{\small\ such that}\quad
t^{\prime}(f^{*})=\frac{(U_{11}-U_{01})\ (1-B)}{(U_{00}-U_{10})\ B}\ .$ (24)

?figurename? 8: Receiver-operating-characteristic curves of two classifiers.
The red dashed curve clearly subtends a larger area than the blue solid curve.
Yet the classifier with the latter curve yields a higher utility, because it
touches the family of parallel lines, eq. (25), at a higher point. This
example arises for a utility matrix equal to $\begin{bmatrix}[r]4&0\\\
0&1\end{bmatrix}$ and a test set with $B=0.5$ (balanced), or for a utility
matrix equal to $\begin{bmatrix}[r]1&0\\\ 0&1\end{bmatrix}$ and a test set
with $B=0.8$.

If we have several classifiers, each with its own curve $t(f)$, then _the best
is the one tangent to the line_

$t=\frac{(U_{11}-U_{01})\ (1-B)}{(U_{00}-U_{10})\ B}f+\text{\small const.}$
(25)

_that has the highest intercept._

From this criterion it can be seen geometrically that if a classifier has its
curve $t(f)$ _completely above_ the curve of another classifier, then it must
have a higher utility yield. But nothing, in general, can be said if the
curves of the two classifiers cross. It is the tangent of a receiver-
operating-characteristic curve that matters, not its subtended area. Figure 8
shows an example of this.

##  6 Summary and discussion

The evaluation and ranking of classification algorithms is a critical stage in
their development and deployment. Without such evaluation we cannot even say
whether an algorithm is better than another, or whether a set of parameter
values for a specific algorithm is better than another set.

And yet, at present, we have not an evaluation theory but only an evaluation
folklore: different procedures, proposed only out of intuition and of analysis
of special cases, with fuzzy criteria to decide which should be used, and
without rigorous theoretical foundations that should guarantee uniqueness,
universality properties, and absence of biases. We believe that some of the
surprising failures of machine learning _in actual applications_[see
e.g.][]varoquauxetal2022 come not only from biases in the choice of test
datasets and other similar biases, but also from the use of wrong evaluation
metrics in the development stage.

In the present work, we have argued that theoretical foundations for the
evaluation process are available in _Decision Theory_. Its main notions and
principle – utilities and their maximization – are very intuitive, as shown
(we hope) by the introductory story.

These are the main results of the application of decision theory to the
evaluation of classifiers:

  * •

The evaluation metric must depend on the specific classification problem.

  * •

Such metric is completely defined by $n^{2}$ parameters, called utilities,
collected in a utility matrix; $n$ is the number of classes. Two parameters
are arbitrary and represent a zero and measurement unit of the utility scale.
In the binary-classification case, this means that we have a two-dimensional
set of possible metrics.

  * •

The score of a classifier on a test set is simply given by its utility yield:
the grand sum of the products of the elements of the utility matrix and the
confusion matrix of the classifier. It is a simple linear expression in the
confusion-matrix elements.

  * •

A utility matrix, obtained from an average, is also used when we are uncertain
about the utilities underlying a classification problem or when we want to
consider the average performance over several classification problems.

  * •

Some popular metrics such as precision, balanced accuracy, Matthews
correlation coefficient, Fowlkes-Mallows index, $F_{1}$-measure, and area
under the receiver-operating-characteristic curve do not comply with decision
theory. As a consequence, they always lead to some erroneous comparative
evaluations of classifiers in every classification problem, even when all
utilities and frequencies are correctly assessed; are they are likely affected
by cognitive biases.

  * •

Using a utility matrix with incorrectly assessed utilities still leads, on
average, to fewer wrong comparative evaluations than using other popular
metrics.

We believe that the decision-theoretic evaluation of classifiers also has
remarkable advantages:

First, it translates the fuzzy problem “which of the numerous scores should I
rely on?” into a more structured, thus easier to confront, one: to assess, at
least semi-quantitatively, how many times more valuable, desirable, or useful
is the correct classification of a class than its incorrect classification,
than the correct classification of another class, and so on. Such utilities
usually have a more immediate, problem-dependent interpretation than other
metrics.

Second, it leads to a mathematically simple, computationally convenient
metric: a linear combination of confusion-matrix elements – no need for non-
linear functions or integration of curves.

Third, the principles of the underlying theory guide us if we have to face new
peculiar problems. Imagine, for instance, a classification problem where we
cannot say, in general, whether true positives are more important than true
negatives and so on, because such valuation can _vary from one tested item to
another_. Decision theory, in this case, requires an item-wise assessment of
utilities, and still provides an item-wise score, which can be accumulated
across items to obtain a total evaluation score for the performance of
candidate classifiers.

The theory, remarks, and results of the present work generalize beyond
classification: to regression and more complex classification-like problems
such as image segmentation, with important applications in medicine
lundervoldetal2019. It would be interesting to examine whether popular metrics
in the latter field, such as Dice score dice1945,fleiss1975,zijdenbosetal1994
and Hausdorff distance altetal2000, comply with decision-theoretic principles,
and which alternatives could be used otherwise.

In a companion work dyrlandetal2022b we apply the general ideas presented here
to improve the performance of machine-learning classifiers.

## Author contributions

All authors have contributed equally to the present work.

###### Acknowledgements.

KD and ASL acknowledge support from the Trond Mohn Research Foundation, grant
number BFS2018TMT07, and PGLPM from The Research Council of Norway, grant
number 294594. KD would like to thank family for endless support; partner
Synne for constant love, support, and encouragement; and the developers and
maintainers of Python, FastAi, PyTorch, scikit-learn, NumPy and RDKit for free
open source software and for making the experiments possible. PGLPM thanks
Iván Davidovich for useful comments on previous drafts of this work; Maja,
Mari, Miri, Emma for continuous encouragement and affection; Buster Keaton and
Saitama for filling life with awe and inspiration; and the developers and
maintainers of LaTeX, Emacs, AUCTeX, Open Science Framework, R, Python,
Inkscape, LibreOffice, Sci-Hub for making a free and impartial scientific
exchange possible.

prenote(‘de $X$’ is listed under D, ‘van $X$’ under V, and so on, regardless
of national conventions.)