# An interlacing result for Hermitian matrices in Minkowski space

D.B. Janse van Rensburg111School of Mathematical and Statistical Sciences,
North-West University, Research Focus: Pure and Applied Analytics, Private Bag
X6001, Potchefstroom 2520, South Africa. E-mail:
<EMAIL_ADDRESS><EMAIL_ADDRESS>, A.C.M.
Ran222Department of Mathematics,Vrije Universiteit Amsterdam, De Boelelaan
1111, 1081 HV Amsterdam, The Netherlands and Research Focus: Pure and Applied
Analytics, North-West University, Potchefstroom, South Africa. E-mail:
<EMAIL_ADDRESS>M. van Straaten11footnotemark: 1

###### Abstract

In this paper we will look at the well known interlacing problem, but here we
consider the result for Hermitian matrices in the Minkowski space, an
indefinite inner product space with one negative square. More specific, we
consider the $n\times n$ matrix $A=\begin{bmatrix}J&u\\\
-u^{*}&a\end{bmatrix}$ with $a\in\mathbb{R}$, $J=J^{*}$ and
$u\in\mathbb{C}^{n-1}$. Then $A$ is $H$-selfadjoint with respect to the matrix
$H=I_{n-1}\oplus(-1)$. The canonical form for the pair $(A,H)$ plays an
important role and the sign characteristic coupled to the pair is also
discussed.

_Keywords_ interlacing, Minkowski space

_MSC_ 15A18, 15A42, 47B50

##  1 Introduction

The Hermitian matrix $H=I_{n-1}\oplus(-1)$ defines an indefinite inner product
space with one negative square, this is sometimes called the Minkowski space.
The formula $[x,y]=\langle Hx,y\rangle$, with $x,y\in\mathbb{C}^{n}$ and where
$\langle\cdot\,,\cdot\rangle$ denotes the standard inner product, defines an
indefinite inner product on $\mathbb{C}^{n}$. The function $[x,y]$ satisfies
all the properties of the standard inner product, with the exception that
$[x,x]$ may be nonpositive for $n\neq 0$. Basic elements of the theory of
indefinite inner product spaces are summarised in [2].

An $n\times n$ matrix $A$ is called $H$-selfadjoint if it is selfadjoint in
the indefinite inner product given by $H$, or equivalently, if $HA=A^{*}H$.
The spectrum $\sigma(A)$ of an $H$-selfadjoint matrix $A$ is symmetric
relative to the real axis. The sizes of the Jordan blocks in the Jordan normal
form of $A$ corresponding to eigenvalue $\lambda$ are equal to the sizes of
the Jordan blocks corresponding to eigenvalue $\bar{\lambda}$, see Proposition
4.2.3 in [2].

Canonical forms exist for pairs of matrices $(A,H)$ where $A$ is
$H$-selfadjoint, see for example [1]. However, for the specific pair of
matrices discussed in this paper, namely

$A=\begin{bmatrix}J&u\\\ -u^{*}&a\end{bmatrix}\quad\text{and}\quad
H=I_{n-1}\oplus(-1),$

the possible canonical forms are restricted to the ones below, see Section 5.6
in [2]. There exists an invertible matrix $S$ such that
$S^{-1}AS=A_{1}\oplus\cdots\oplus A_{k}$ and $S^{*}HS=H_{1}\oplus\cdots\oplus
H_{k}$, where the blocks in the canonical form are one of the following types:

  1. 1.

$A_{j}=\lambda$, $H_{j}=\pm 1$, with $\lambda\in\mathbb{R}$, and only for one
real eigenvalue the sign can be negative,

  2. 2.

$A_{j}=\begin{bmatrix}a+bi&0\\\ 0&a-bi\end{bmatrix}$,
$H_{j}=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$, with $a\in\mathbb{R}$ and
$b>0$,

  3. 3.

$A_{j}=J_{2}(\lambda)$, $H_{j}=\pm\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}$,
with $\lambda\in\mathbb{R}$,

  4. 4.

$A_{j}=J_{3}(\lambda)$, $H_{j}=\begin{bmatrix}0&0&1\\\ 0&1&0\\\
1&0&0\end{bmatrix}$, with $\lambda\in\mathbb{R}$.

In addition, only one block of the forms in either 2, 3, or 4 can occur.

Note that for the specific matrices $A$ and $H$, we have $J^{*}=J$ and
$a\in\mathbb{R}$. The goal of this paper is to find the relationship between
the eigenvalues of the matrix $A$ and the matrix $J$ and how they are
interlaced.

Interlacing problems for Hermitian matrices in a definite inner product space
are well known, and results can be found in Section 4.3 in [5]. Theorem 4.3.17
in [5] gives Cauchy’s interlacing theorem for a bordered Hermitian matrix. For
an application to graphs and subgraphs, see for example the paper by Haemers
[3] and references there.

Returning to the indefinite case, a different point of view is the inverse
eigenvalue problem, and more precisely the periodic Jacobi inverse eigenvalue
problem. See for example the paper by Xu, Bebiano and Chen, [6] and references
mentioned there. The paper [6] is concerned with the reconstruction of a
Jacobi matrix. We were inspired by some results in this paper and we were
curious about the sign associated to the specific eigenvalues. We therefore
explore this, applied to general $H$-selfadjoint matrices with one negative
square.

In our paper we are concerned with how the eigenvalues of the selfadjoint
matrix $J$ interlace with those of the $H$-selfadjoint matrix $A$, and with
the sign corresponding to the eigenvalues of $A$ in the canonical form of the
pair $(A,H)$. The proof for the interlacing of the eigenvalues follows the
same line of argument as Lemma 3.3 in [6].

We consider the characteristic polynomial of $A$. If $\lambda\notin\sigma(J)$,
we use a standard argument to write $\lambda I-A$ as

$\lambda I-A=\begin{bmatrix}\lambda I-J&-u\\\
u^{*}&\lambda-a\end{bmatrix}=\begin{bmatrix}\lambda I-J&0\\\
u^{*}&1\end{bmatrix}\begin{bmatrix}I&-(\lambda I-J)^{-1}u\\\
0&\lambda-a+u^{*}(\lambda I-J)^{-1}u\end{bmatrix}.$

Hence the characteristic polynomial of $A$ becomes

$p(\lambda)=\det(\lambda I-A)=\det(\lambda I-J)\cdot(\lambda-a+u^{*}(\lambda
I-J)^{-1}u).$ (1)

A part of the second term in (1) is a realization of the general form

$D+C(\lambda I_{n}-A)^{-1}B.$

This realization will be minimal if $n$ is as small as possible, or
equivalently, the pair $(A,C)$ is observable and the pair $(A,B)$ is
controllable. For our case this reduces to the observability of the pair
$(J,u^{*})$.

Recall, see Theorem 3.2.1 in [4], that a pair $(A,C)$ with $C$ an $m\times n$
matrix and $A$ an $n\times n$ matrix is observable if

$\mathcal{N}:=\textup{Ker}\begin{bmatrix}C\\\ CA\\\ CA^{2}\\\ \vdots\\\
CA^{n}\end{bmatrix}=\\{0\\}.$

The Hautus test for observability, see Theorem 3.2.2 in [4], states the
following: the matrix pair $(A,C)$ is observable if and only if

$\textup{rank}\begin{bmatrix}\lambda I-A\\\ C\end{bmatrix}=n\,\,\,\textrm{for
all }\,\,\lambda\in\sigma(A).$

The Hautus test for the pair $(J,u^{*})$ insures that all eigenvalues of $J$
appear as the poles of the expression $u^{*}(\lambda I-J)^{-1}u$,
multiplicities included.

Section 2 of this paper describes the relationships between observability and
the eigenvalues and Section 3 is concerned with the sign connected to the
eigenvalues in the pair $(A,H)$. Finally, in the last section a few examples
are given to verify and clarify some of the theory.

##  2 Observability

In this section we will prove several results following from the observability
of the matrix pair $(J,u^{*})$.

###### Proposition 2.1

Let $J=J^{*}\in\mathbb{C}^{n-1\times n-1}$ and $u\in\mathbb{C}^{n-1}$. If the
pair $(J,u^{*})$ is observable, i.e., $\textup{rank}\begin{bmatrix}\lambda
I-J\\\ u^{*}\end{bmatrix}=n-1$ then:

  * (i)

$J$ has $n-1$ distinct eigenvalues;

  * (ii)

$\sigma(J)\cap\sigma(A)=\emptyset$;

  * (iii)

$A$ is nonderogatory.

Proof. (i) This follows immediately from the Hautus test. Indeed, since
$J=J^{*}$ it only needs to be shown that for no eigenvalue $\lambda_{0}$ the
corresponding eigenspace ${\rm Ker\,}(\lambda_{0}I-J)$ has dimension two or
higher. However, if this would be the case, then
$\begin{bmatrix}\lambda_{0}I-J\\\ u^{*}\end{bmatrix}$ can have rank $n-2$ at
most, thus violating the assumption of observability.

(ii) From (1) and the fact that $(\lambda I-J)$ is invertible
($\lambda\notin\sigma(J))$, we have

$\frac{\det(\lambda I-A)}{\det(\lambda I-J)}=\lambda-a+u^{*}(\lambda
I-J)^{-1}u.$

Thus, if $\sigma(J)\cap\sigma(A)\neq\emptyset$, then for some
$\lambda_{0}\in\sigma(J)\cap\sigma(A)$, there will be a
$(\lambda-\lambda_{0})$ cancelling on the left, leaving us with a polynomial
of degree $n-2$ in the denominator. Hence, there are at most $n-2$ poles but
on the right-hand side we know there should be exactly $n-1$ poles, by the
observability. This contradiction proves (ii).

(iii) Let $\lambda_{0}\in\sigma(A)$, i.e., $Ax=\lambda_{0}x$, with
$x=\begin{bmatrix}x_{1}\\\ x_{2}\end{bmatrix}\neq 0$. For
$A=\begin{bmatrix}J&u\\\ -u^{*}&a\end{bmatrix}$ one obtains

$(\lambda_{0}I-J)x_{1}-ux_{2}=0\quad\textup{and}\quad
u^{*}x_{1}+(\lambda_{0}-a)x_{2}=0.$

If $x_{2}=0$, we have from the first equation that $(\lambda_{0}I-J)x_{1}=0$,
and since $\lambda_{0}\notin\sigma(J)$ by (ii), $(\lambda_{0}I-J)$ is
invertible and hence it implies $x_{1}=0$. This is a contradiction since $x$
is an eigenvector of $A$ belonging to $\lambda_{0}$, hence $x_{2}\neq 0$.
Thus, one can solve for $x_{1}$ in terms of $x_{2}$ from the first equation
which means the eigenvector corresponding to $\lambda_{0}$ is determined by
$x_{2}$. Therefore, the $\dim\textup{Ker}(\lambda_{0}I-A)=1$ and hence $A$ is
nonderogatory.

$\Box$

If $(J,u^{*})$ is not observable, the problem can be reduced to a situation
where observability is satisfied.

###### Proposition 2.2

Assume $(J,u^{*})$ is not observable, and let
$\mathcal{N}=\cap_{j=0}^{n-2}{\rm Ker\,}u^{*}J^{j}$ be the unobservable
subspace. With respect to
$\mathbb{C}^{n-1}=\mathcal{N}\oplus\mathcal{N}^{\perp}$, write $J=J_{1}\oplus
J_{2}$ as well as $u=\begin{bmatrix}0&u_{2}^{*}\end{bmatrix}$. Then
$\sigma(A)\cap\sigma(J)=\sigma(J_{1})$, and

$\sigma(A)=\sigma(J_{1})\cup\sigma\left(\begin{bmatrix}J_{2}&u_{2}\\\
-u_{2}&a\end{bmatrix}\right).$

Proof. Using the Kalman decomposition into the unobservable space and its
orthogonal complement we can reduce to a situation where observability is
satisfied, as the pair $(J_{2},u_{2}^{*})$ is observable. Writing

$A=\begin{bmatrix}J_{1}&0&0\\\ 0&J_{2}&u_{2}\\\ 0&-u_{2}^{*}&a\end{bmatrix}$

the statements in the proposition easily follow.

$\Box$

##  3 Interlacing

In this section the main result of this article is presente. It contains the
way the eigenvalues of matrices $A$ and $J$ are interlacing with each other,
together with the sign corresponding to the eigenvalues of the matrix $A$.
From Proposition 2.1 we have that the eigenvalues of $A$ are precisely the $n$
complex zeros of the function $\lambda-a+u^{*}(\lambda I-J)^{-1}u$ and this
function has $n-1$ real distinct poles. Denote the eigenvalues of $J$ by
$\mu_{n-1}<\mu_{n-2}<\cdots<\mu_{1}$ and introduce

$g(\lambda)=-u^{*}(\lambda I-J)^{-1}u.$

Since $J=J^{*}$, there is a unitary matrix $V$ such that $V^{*}JV=D={\rm
diag\,}(\mu_{j})_{j=1}^{n-1}$. Hence, one can write

$g(\lambda)=-u^{*}V^{*}(\lambda
I-D)^{-1}Vu=-\sum_{j=1}^{n-1}\frac{d_{j}}{\lambda-\mu_{j}},$

where $d_{j}=((Vu)_{j})^{2}>0$. Note that
$g^{\prime}(\lambda)=\sum_{j=1}^{n-1}\frac{d_{j}}{(\lambda-\mu_{j})^{2}}$ is
positive where it is defined, and that
$\lim_{\lambda\to\pm\infty}g(\lambda)=0$. Finally, the eigenvalues of $A$,
which we shall denote by $\lambda_{j}$, $j=1,\ldots,n$, are the solutions of
$h(\lambda)-g(\lambda)=0$, where $h(\lambda)=\lambda-a$.

###### Theorem 3.1

Let $A$ be an $H$-selfadjoint matrix with $H=I_{n-1}\oplus(-1)$ (Hermitian and
invertible) and let $A=\begin{bmatrix}J&u\\\ -u^{*}&a\end{bmatrix}$ with
$a\in\mathbb{R}$, $u\in\mathbb{C}^{n-1}$ and $J=J^{*}$. If the pair
$(J,u^{*})$ is observable, then the conditions of Proposition 2.1 hold.
Furthermore, let $\mu_{n-1}<\mu_{n-2}<\cdots<\mu_{1}$ denote the $n-1$
distinct real eigenvalues of $J$ and let $\lambda_{1},\ldots,\lambda_{n}$ be
the eigenvalues of $A$. Then the eigenvalues of $A$ and $J$ interlace in the
following possible ways coupled with the appropriate sign for $\varepsilon$.

  * 1a

$\lambda_{n}<\lambda_{n-1}<\mu_{n-1}<\lambda_{n-2}<\cdots<\lambda_{1}<\mu_{1}$,
where the sign $\varepsilon=-1$ is associated with the Jordan block of size
$1$ for the eigenvalue $\lambda_{n}$;

  * 1b

$\lambda_{n}=\lambda_{n-1}<\mu_{n-1}<\lambda_{n-2}<\cdots<\lambda_{1}<\mu_{1}$,
where the sign $\varepsilon=-1$ is associated with a Jordan block of size $2$
with eigenvalue $\lambda_{n}=\lambda_{n-1}$;

  * 2a

$\mu_{n-1}<\lambda_{n-2}<\cdots<\lambda_{1}<\mu_{1}$, and
$\lambda_{n}=\overline{\lambda_{n-1}}\notin\mathbb{R}$,

  * 3a

$\mu_{n-1}<\lambda_{n}<\mu_{n-2}<\cdots<\lambda_{3}<\mu_{1}<\lambda_{2}<\lambda_{1}$,
where the sign $\varepsilon=-1$, is associated with the Jordan block of size
$1$ for eigenvalue $\lambda_{1}$;

  * 3b

$\mu_{n-1}<\lambda_{n}<\mu_{n-2}<\cdots<\lambda_{3}<\mu_{1}<\lambda_{2}=\lambda_{1}$,
where the sign $\varepsilon=1$ is associated with a Jordan block of size $2$
with eigenvalue $\lambda_{1}=\lambda_{2}$;

  * 4a

$\mu_{n-1}<\lambda_{n}<\mu_{n-2}<\cdots<\mu_{j+1}<\lambda_{j+2}<\lambda_{j+1}<\lambda_{j}<\mu_{j}<\cdots<\mu_{2}<\lambda_{1}<\mu_{1}$,
where the sign $\varepsilon=-1$ is associated with the Jordan block of size
$1$ for eigenvalue $\lambda_{j+1}$;

  * 4b

$\mu_{n-1}<\lambda_{n}<\mu_{n-2}<\cdots<\mu_{j+1}<\lambda_{j+2}=\lambda_{j+1}<\lambda_{j}<\mu_{j}<\cdots<\mu_{2}<\lambda_{1}<\mu_{1}$,
where the sign $\varepsilon=1$ is associated with the Jordan block of size $2$
with eigenvallue $\lambda_{j+2}=\lambda_{j+1}$;

  * 4c

$\mu_{n-1}<\lambda_{n}<\mu_{n-2}<\cdots<\mu_{j+1}<\lambda_{j+2}<\lambda_{j+1}=\lambda_{j}<\mu_{j}<\cdots<\mu_{2}<\lambda_{1}<\mu_{1}$,
where the sign $\varepsilon=-1$ is associated with the Jordan block of size
$2$ with eigenvalue $\lambda_{j+1}=\lambda{j}$;

  * 4d

$\mu_{n-1}<\lambda_{n}<\mu_{n-2}<\cdots<\mu_{j+1}<\lambda_{j+2}=\lambda_{j+1}=\lambda_{j}<\mu_{j}<\cdots<\mu_{2}<\lambda_{1}<\mu_{1}$
where the sign $\varepsilon=1$ is associated with a Jordan block of size $3$
with eigenvalue $\lambda_{j+2}=\lambda_{j+1}=\lambda_{j}$.

Proof. The interlacing of the eigenvalues of $A$ and $J$, i.e., the way
$h(\lambda)$ and $g(\lambda)$ intersect, follows a similar result by Lemma 3.3
in [6]. Because of the fact that $A$ is nonderogatory, in cases 1b, 3b, 4b and
4c there is a Jordan block of size two corresponding to the two eigenvalues
that coincide, while in case 4d there is a Jordan block of size three
corresponding to the three eigenvalues that coincide. See Section 5.6 in [2].
We would like to know in the cases 1a, 3a and 4a in the list, which one of the
eigenvalues has the negative sign in the sign characteristic, and in cases 1b,
3b, 4b and 4c what the sign corresponding to the Jordan block of size two is.
In order to answer these questions we first recall one of the descriptions of
the sign characteristic, see Section 5.1 in [2]. First note that for every
real $\lambda$, the matrix $\lambda H-HA$ is an $n\times n$ Hermitian matrix,
and hence has $n$ real eigenvalues, which are denoted by
$\nu_{1}(\lambda),\ldots,\nu_{n}(\lambda)$. It turns out that these can be
chosen to be analytic functions of the real variable $\lambda$, and this will
be done for now. Let $\lambda_{1},\ldots,\lambda_{r}$ be the real eigenvalues
of $A$, and write for every $i=1,\ldots,r$ and $j=1,\ldots,n$ the function
$\nu_{j}(\lambda)$ as

$\nu_{j}(\lambda)=(\lambda-\lambda_{i})^{m_{ij}}\rho_{ij}(\lambda),$

where $\rho_{ij}(\lambda_{i})\not=0$ and is a real number. Then the nonzero
numbers among $m_{i1},\ldots,m_{in}$ are the sizes of the Jordan blocks of $A$
corresponding to $\lambda_{i}$, and the sign in the sign characteristic of the
pair $(A,H)$ corresponding to the block of size $m_{ij}\not=0$ is the sign of
the real number $\rho_{ij}(\lambda_{i})$. In particular,

if $m_{ij}=1$, then $\rho_{ij}(\lambda_{i})=\nu_{j}^{\prime}(\lambda_{i})$,

if $m_{ij}=2$, then
$\rho_{ij}(\lambda_{i})=\frac{1}{2}\nu_{j}^{\prime\prime}(\lambda_{i})$.

In order to find the signs in the particular situation we have at hand, we
argue as follows. The fact that $\nu(\lambda)$ is an eigenvalue of $\lambda
H-HA$ implies that

$\displaystyle 0$ $\displaystyle=\det(\nu I-(\lambda
H-HA))=\det\begin{bmatrix}\nu I-\lambda I+J&u\\\
u^{*}&\nu+\lambda-a\end{bmatrix}$
$\displaystyle=\det\left(\begin{bmatrix}(\nu-\lambda)I+J&0\\\
u^{*}&1\end{bmatrix}\begin{bmatrix}I&((\nu-\lambda)I+J)^{-1}u\\\
0&(\nu+\lambda)-a-u^{*}((\nu-\lambda)I+J)^{-1}u\end{bmatrix}\right)$
$\displaystyle=\det((\nu-\lambda)I+J)\cdot\left((\nu+\lambda)-a-u^{*}((\nu-\lambda)I+J)^{-1}u\right)$
$\displaystyle=\det((\nu-\lambda)I+J)\cdot\left((\nu+\lambda)-a+u^{*}((\lambda-\nu)I-J)^{-1}u\right).$

It follows that $\nu$ satisfies
$(\nu+\lambda)-a+u^{*}((\lambda-\nu)I-J)^{-1}u=0$, in other words,

$h(\nu+\lambda)-g(\lambda-\nu)=0,$

or more explicitly,

$\nu+\lambda-a=\sum_{j=1}^{n-1}\frac{d_{j}}{\lambda-\nu-\mu_{j}}.$

This determines $\nu$ implicitly as a function of $\lambda$. For fixed
$\lambda$ we know that there have to be $n$ real solutions. Introduce

$H(\lambda,\nu)=h(\lambda+\nu)-g(\lambda-\nu).$

When $m_{ij}\not=0$, we have $\nu_{j}(\lambda_{i})=0$ and
$H(\lambda_{i},0)=0$. Applying the implicit function theorem we obtain

$\nu_{j}^{\prime}(\lambda_{i})=-\left({\frac{\partial
H}{\partial\lambda}}/{\frac{\partial
H}{\partial\nu}}\right)\rfloor_{\lambda=\lambda_{i}\atop\nu=0}.$

Now

$\displaystyle\frac{\partial
H}{\partial\lambda}\rfloor_{\lambda=\lambda_{i}\atop\nu=0}=1-g^{\prime}(\lambda-\nu)\rfloor_{\lambda=\lambda_{i}\atop\nu=0}=1-g^{\prime}(\lambda_{i}),$
$\displaystyle\frac{\partial
H}{\partial\nu}\rfloor_{\lambda=\lambda_{i}\atop\nu=0}=1+g^{\prime}(\lambda-\nu)\rfloor_{\lambda=\lambda_{i}\atop\nu=0}=1+g^{\prime}(\lambda_{i}),$

so

$\nu_{j}^{\prime}(\lambda_{i})=-\left(\frac{1-g^{\prime}(\lambda_{i})}{1+g^{\prime}(\lambda_{i})}\right).$

Recall that $g^{\prime}(\lambda)>0$ whenever $\lambda$ is not one of the
$\mu_{j}$’s. Thus, if $m_{ij}=1$ the sign of $\nu_{j}^{\prime}(\lambda_{i})$,
and therefore also the sign attached to $\lambda_{i}$, is equal to the sign of
$g^{\prime}(\lambda_{i})-1$. We conclude that for an eigenvalue of
multiplicity one, the sign in the sign characteristic is determined by how $h$
and $g$ intersect at $\lambda_{i}$ as follows:

if $g^{\prime}(\lambda_{i})>1$ then the sign is $+1$ at eigenvalue
$\lambda_{i}$;

if $g^{\prime}(\lambda_{i})<1$ then the sign is $-1$ at eigenvalue
$\lambda_{i}$.

It remains to consider the signs of the Jordan blocks of order two. For that
we first recall that $\nu(\lambda)$ satisfies $H(\lambda,\nu(\lambda))=0$.
Taking the first derivative we have

$\frac{\partial H}{\partial\lambda}+\frac{\partial
H}{\partial\nu}\cdot\nu^{\prime}(\lambda)=0,$

and differentiating this again gives

$\frac{\partial^{2}H}{\partial\lambda^{2}}+\frac{\partial^{2}H}{\partial\lambda\partial\nu}\cdot\nu^{\prime}(\lambda)+\frac{\partial
H}{\partial\nu}\cdot\nu^{\prime\prime}(\lambda)=0.$

A Jordan block of size two corresponds to a situation where
$\nu_{j}(\lambda_{i})=0$ and $\nu^{\prime}_{j}(\lambda_{i})=0$, because $h$
and $g$ touch at $\lambda_{i}$. Solving the above equation for
$\nu_{j}^{\prime\prime}(\lambda_{i})$, we have

$\nu_{j}^{\prime\prime}(\lambda_{i})=-\left(\frac{\partial^{2}H}{\partial\lambda^{2}}/\frac{\partial
H}{\partial\nu}\right)\rfloor_{\lambda=\lambda_{i}\atop\nu=0}=-\frac{g^{\prime\prime}(\lambda_{i})}{1+g^{\prime}(\lambda_{i})}.$

Hence the sign corresponding to a block of size two with eigenvalue
$\lambda_{i}$ is the sign of $-g^{\prime\prime}(\lambda_{i})$. A little
analysis shows that if the graph of $g$ locally around $\lambda_{i}$ lies
above the graph of $h$, then the sign is $-1$ at eigenvalue $\lambda_{i}$,
while if the graph of $g$ locally around $\lambda_{i}$ lies below the graph of
$h$, then the sign is $+1$ at eigenvalue $\lambda_{i}$. $\Box$

##  4 Examples

As an example, consider the case where $J$ has eigenvalues $1,2,3,4$, where
the $d_{j}$’s are given by $0.01,0.02,0.001,1$, respectively. Thus,

$g(\lambda)=-\left(\frac{0.01}{\lambda-1}+\frac{0.02}{\lambda-2}+\frac{0.001}{\lambda-3}+\frac{1}{\lambda-4}\right).$

In Figure 1, the functions $g(\lambda)$ and $h(\lambda)=\lambda-a$ are plotted
for several values of $a$, namely $a=0,\,0.4591,\ 0.8319,\ 1.2631,\ 1.7485,\
2.0087,\ 6.0097,\ 6.5$.

Figure 1: On the left, some possible configurations of $h(\lambda)$ and
$g(\lambda)$, on the right $g^{\prime}(\lambda)$ and the line $y=1$ to
determine the points where there is a Jordan block of size two.

We can draw the following conclusions regarding the sign of the eigenvalues
depending on the choice of $a$:

  1. 1.

In case 1a ($a=0)$ $\lambda_{n}$ comes with a negative sign, in case 3a
($a=6.5$) $\lambda_{1}$ comes with a negative sign, in case 4a (this would
occur, e.g., for $a=1$) $\lambda_{j+1}$, the middle one of the three crossings
in $(\mu_{j+1},\mu_{j})$ comes with a negative sign.

  2. 2.

In case 1b ($a\approx 0.4591$) the sign corresponding to the block of order
two with eigenvalue $\lambda_{n}=\lambda_{n-1}\approx 0.8934$ is $-1$, in case
3b ($a\approx 6.0097$) the sign corresponding to the block of order two with
eigenvalue $\lambda_{1}=\lambda_{2}\approx 5,00155$ is $+1$, in case 4b
($a\approx 0.8319$ and $a\approx 1.7485$) the sign corresponding to the block
of order two with eigenvalue $\lambda_{j+2}=\lambda_{j+1}\approx 1.10815$,
respectively, $\lambda_{j+2}=\lambda_{j+1}\approx 2.1699$, is $+1$, and
finally, in case 4c ($a\approx 1.2631$ and $a\approx 2.0087$) the sign
corresponding to the block of order two with eigenvalue
$\lambda_{j+1}=\lambda_{j}\approx 1.83895$, respectively,
$\lambda_{j+1}=\lambda_{j}\approx 2.91185$, is $-1$.

In general, we can formulate the following when we view $a$ as a parameter.
There is a value $a^{-}_{1}$ such that for $a<a^{-}_{1}$ we are in situation
1a, while for $a=a^{-}_{1}$ we are in situation 1b. Then there is a value
$a^{-}_{2}$ such that for $a^{-}_{1}<a<a^{-}_{2}$ we are in case 2, while for
$a=a^{-}_{2}$ we have either 4b for some $j$ between $n-2$ and $1$, or 4d, or
3b. From the other end, there is an $a^{+}_{1}$ such that for $a>a^{+}_{1}$ we
are in the situation 3a, while for $a=a^{+}_{1}$ we are in the situation 3b.
Finally, there is an $a^{+}_{2}$ such that for $a^{+}_{2}<a<a^{+}_{1}$ we are
in the situation 2, while for $a=a^{+}_{2}$ we are either in the situation 4c,
or in the situation 4d, or in 1b. Eventually, for large positive $a$ there is
one eigenvalue moving to $+\infty$, while there are $n-1$ eigenvalues
approximating the eigenvalues of $J$ from the right.

To check the latter statement, consider the equation
$G(\lambda,a)=h(\lambda)-g(\lambda)=0$ as an equation determining $\lambda$
locally as a function of $a$. Then by the implicit function theorem

$\lambda_{i}^{\prime}(a)=-\left(\frac{\partial G}{\partial a}/\frac{\partial
G}{\partial\lambda}\right)\rfloor_{\lambda=\lambda_{i}}=\frac{1}{1-g^{\prime}(\lambda_{i})}.$

As for large values of $a$ the derivative $g^{\prime}(\lambda_{i})>1$ (as can
be seen from the graph of $g$) apart from the largest eigenvalue, we have
$\lambda_{i}$ decreasing for $i=2,\ldots,n$ and increasing for $i=1$. Using
the main result of [7] we obtain that the eigenvalues of $A$ as function of
$a$ approximate the eigenvalues of $J$ as $a\to\infty$, with the exception of
one, which goes to plus infinity.

The following example demonstrates a third order block when we take
$\mu_{1}=1,\mu_{2}=-1$ and $u=[1/\sqrt{2},1/\sqrt{2}]$. In this case we have

$A=\begin{bmatrix}1&0&1/\sqrt{2}\\\ 0&-1&1/\sqrt{2}\\\
-1/\sqrt{2}&-1/\sqrt{2}&a\end{bmatrix}.$

For $a=0$ there is a Jordan block of order three at the eigenvalue $0$. In the
left-hand graph in Figure 2 the eigenvalues of $A$ are plotted for varying
values of $a$. The dots in the circular-like shape are the complex eigenvalues
that can occur, as the graph of $h(\lambda)$ moves from left to right over the
curve of $g(\lambda)$ as function of $a$.

.

Figure 2: The situation with a Jordan block of order three.

Acknowledgement. The work of the first and third author is supported in part
by the DSI-NRF Centre of Excellence in Mathematical and Statistical Sciences
(CoE-MaSS, Grant Number 2022-012-ALG-ILAS). The work of the second author is
based on research supported in part by the National Research Foundation of
South Africa (Grant Number 145688).

## References

  * [1] Y. Bolshakov, C.V.M. van der Mee, A.C.M. Ran, B. Reichstein and L. Rodman. Polar decompositions in finite dimensional indefinite scalar product spaces: General theory, Linear Algebra Appl., 216, (1997), 91–141.
  * [2] I. Gohberg, P. Lancaster and L. Rodman. Indefinite Linear Algebra and Applications, Birkhäuser Verlag, Basel, 2005.
  * [3] W.H. Haemers. Interlacing Eigenvalues and Graphs. Linear Algebra Appl., 226–228, (1995), 593–616.
  * [4] C. Heij, A.C.M. Ran, F. van Schagen. _Introduction to Mathematical Systems Theory,_ 2nd edition, Birkhäuser Verlag, 2020.
  * [5] R.A. Horn, C.R. Johnson. _Matrix Analysis_ , 2nd edition, Cambridge University Press, Cambridge, 2013.
  * [6] W.-R. Xu, N. Bebiano, G.-L. Chen. A reduction algorithm for reconstructing periodic Jacobi matrices in Minkowski spaces. _Applied Math. and Comp_. 419, (2022), 126853.
  * [7] A.C.M. Ran, M. Wojtylak. Global properties of eigenvalues of parametric rank one perturbations for unstructured and structured matrices II. _Complex Anal. Oper. Theory_ 16:91, (2022).


# On Orderings of Probability Vectors and Unsupervised Performance Estimation

Muhammad Maaz1,2 Rui Qiao1 Yiheng Zhou1 &Renxian Zhang1
1Amazon Science
2University of Toronto
<EMAIL_ADDRESS>
###### Abstract

Unsupervised performance estimation, or evaluating how well models perform on
unlabeled data is a difficult task. Recently, a method was proposed by Garg et
al. (2022) which performs much better than previous methods. Their method
relies on having a score function, satisfying certain properties, to map
probability vectors outputted by the classifier to the reals, but it is an
open problem which score function is best. We explore this problem by first
showing that their method fundamentally relies on the ordering induced by this
score function. Thus, under monotone transformations of score functions, their
method yields the same estimate. Next, we show that in the binary
classification setting, nearly all common score functions - the $L^{\infty}$
norm; the $L^{2}$ norm; negative entropy; and the $L^{2}$, $L^{1}$, and
Jensen-Shannon distances to the uniform vector - all induce the same ordering
over probability vectors. However, this does not hold for higher dimensional
settings. We conduct numerous experiments on well-known NLP data sets and
rigorously explore the performance of different score functions. We conclude
that the $L^{\infty}$ norm is the most appropriate.111Code available at:
https://github.com/mmaaz-git/acc-estim.

##  1 Introduction

When a machine learning model is trained, typically (in the supervised or
semi-supervised cases), we have labels on the data and can easily calculate
any number of popular metrics to evaluate the model’s performance on some
held-out test set, e.g., accuracy, true positive rate, precision, etc.
Furthermore, performance on a labeled validation set can be used for model
tuning. When labels are present, evaluating models is extremely
straightforward.

However, in many real-world applications of machine learning, not all data is
unlabeled, and in fact the amount of unlabeled data may vastly outnumber the
amount of labeled data. For example, a chatbot may be trained on some number
of queries that have been labeled by humans, but all possible queries cannot
possibly be labeled. In many cases, human labeling of all data is too
expensive, either costing too much time or too much money. However, for the
deployer, knowing how well your model is performing on this unlabeled data is
of prime importance, especially in the context of model performance
degradation when faced with real-world data, which is often noisier and from a
different distribution than the original data set.

More formally, we have a source domain on which the model is trained and a
target domain on which it is deployed. This problem is referred to in the
literature as unsupervised accuracy estimation, or more generally unsupervised
performance estimation. Here, unsupervised refers to the fact that the target
domain has no labels, and thus other information has to be used in order to
evaluate the model’s performance. Unsupervised performance estimation is
related to the well-known problem of unsupervised domain adaptation, which
seeks to appropriately deploy a model on to an unlabeled target domain,
instead of explicitly estimating its performance. However, the two problems
are quite related in spirit.

A recent contribution of Garg et al. (2022) proposes a simple method for
unsupervised performance estimation, called average thresholded confidence
(ATC), which leverages the class probabilities outputted by a classifier.
While their method outperforms previous baselines, several questions about the
method are left open. In this paper, we provide several theoretical extensions
of their work, which may be of independent interest, and expand our claims by
testing their method on natural language processing (NLP) data sets.

###  1.1 Related Literature

Arguably, the theory of unsupervised performance estimation began with the
seminal contribution of Ben-David et al. (2010a, b), which first showed that
the error on a target domain can be bounded by a function of the error on the
source domain and a measure of discrepancy between the source and target
domains. In Ben-David et al. (2010a), the $\mathcal{H}$-divergence is
introduced as this measure of discrepancy. Later works explored other notions
of distance and derived similar bounds.

Based on this notion, many methods of estimating accuracy have been proposed
which essentially seek to align the source and target domains in a common
feature space, and thus calculate the discrepancy between them. Guillory et
al. (2021), Deng and Zheng (2021), and Deng et al. (2021) use this notion, by
finding a linear relationship between discrepancy and performance drop via a
validation set. To quantify this discrepancy, Deng and Zheng (2021) uses the
Fréchet distance between feature vectors, while Guillory et al. (2021) uses
differences in classifier probabilities.

Jiang et al. (2022) estimates error as the expected disagreement between two
separately trained models, while Chen et al. (2021) uses importance
reweighting. It is again worth noting that both of these methods come from the
domain adaptation literature. The notable work of Platanios et al. (2016)
introduced a Bayesian approach which uses a graphical model to estimate the
error.

These methods make some assumptions which may not necessarily hold. For
example, Guillory et al. (2021) assumes a linear relationship between
discrepancy and performance. While we may model a non-linear relationship as
seen in Deng and Zheng (2021), if linearity does not hold, there still remains
the issue that calculating discrepancy between data is fraught with
complexities, especially in language data, where finding an appropriate
feature space is difficult due to well-known issues of sparsity and loss of
semantics with common embedding methods. It is perhaps for this reason that
generative adversarial networks (GANs) are the most common method of domain
adaptation for NLP models (Ramponi and Plank, 2020). As well, the method of
Jiang et al. (2022) doubles computational overhead by training two separate
models.

Recently, Garg et al. (2022) proposed the ATC method, which will be the focus
of this paper. In their experiments, they outperformed the methods of Guillory
et al. (2021), Deng and Zheng (2021), Jiang et al. (2022), and Chen et al.
(2021).

Our Contribution. Garg et al. (2022)’s method is parameterized by the choice
of a certain score function, whose properties we will discuss below. While
they perform several experiments comparing two possible score functions, they
still leave open some questions about their method. In this paper, we propose
several appropriate score functions from the literature. We develop a
theoretical basis for analyzing the estimations yielded by these different
score functions. Based on this, we show that in the binary classification
setting, (almost all) possible score functions yield the same estimate.
Lastly, we perform multiple experiments in multiclass settings, showing with
repeated experiments that the differences between these functions are small.

##  2 Theory

###  2.1 Background

Our setting is of a $k$-class classifier. To adopt the notation of Garg et al.
(2022), we have an input domain $\mathcal{X}\subseteq\mathbb{R}^{d}$ and a
label space $\mathcal{Y}$ containing $k$ distinct labels (e.g., for a binary
classification problem, $\mathcal{Y}=\\{0,1\\}$). Denote $\mathcal{D}^{s}$ and
$\mathcal{D}^{t}$ to be the source and target domains over
$\mathcal{X}\times\mathcal{Y}$. We assume that we have labels in the source
domain, but no labels in the target domain - i.e., it is an unsupervised
domain adaptation problem. We have some performance metric $\Gamma^{s}$ and
$\Gamma^{t}$ on the source and target domains, where they must be in the
interval $[0,1]$. In Garg et al. (2022), they particularly take $\Gamma$ to be
the classification error, but we will keep it more general for now. Let
$\mathcal{F}$ be a set of hypotheses mapping
$\mathcal{X}\mapsto\Delta^{k-1}\subset\mathbb{R}^{k}$, i.e., the input space
to the $(k-1)$-dimensional probability simplex. Our goal is, given
$f\in\mathcal{F}$, validation data from $D^{s}$, a source performance metric
$\Gamma^{s}$, and unlabeled data from $D^{t}$, estimate $\Gamma^{t}$.

The method introduced by Garg et al. (2022) depends on having a score function
$s:\Delta^{k-1}\mapsto\mathbb{R}$ which takes the softmax output of
$f\in\mathcal{F}$ and (roughly) gives a higher value if the classifier is more
confident in its prediction. It should be minimized at the centroid of
$\Delta^{k-1}$ (the uniform probability vector) and maximized on the vertices
of $\Delta^{k-1}$, which corresponds to a single element of the vector being
$1$ and all other elements being $0$. Two such functions studied by Garg et
al. (2022) are the maximum confidence $s(f(x))=\max_{j\in\mathcal{Y}}f_{j}(x)$
and negative entropy $s(f(x))=\sum_{j}f_{j}(x)\log(f_{j}(x))$. We study
several such functions.

Garg et al. (2022)’s method is as follows. First, learn a threshold $t$ such
that:

$\mathbb{P}_{x\in D^{s}}[s(f(x))<t]=\Gamma^{s}$ (1)

Note that $\mathbb{P}[\bullet]$ is equivalent to
$\mathbb{E}[\mathbb{I}[\bullet]]$. So we learn a threshold such that the
proportion of points in $D^{s}$ that have a score less than $t$ is equal to
our source performance metric. In practice, we do:

$t=\operatorname*{arg\,min}_{t\in\operatorname{ran}{s(f(x))},\ x\in
D^{s}}|\Gamma^{s}-\mathbb{P}_{x\in D^{s}}[s(f(x))<t]|$ (2)

where $\operatorname{ran}$ is the range, i.e., all possible values of $s$ over
$D^{s}$.

This means we calculate the threshold $t$ by minimizing the absolute
difference between the two sides of Equation 1, letting $t$ take on the values
of the range of the score function outputted for the values in $D^{s}$.

Then we estimate $\Gamma^{t}$ as follows:

$\Gamma^{t}=\mathbb{P}_{x\in D^{t}}[s(f(x))<t]$ (3)

###  2.2 Orderings

From the method identified above, we can see that the probability vectors are
first mapped to a real number, and then ordered by the usual ordering of the
reals. The threshold $t$ depends exactly on this ordering. Thus, the way the
score function maps vectors to the reals determines the threshold. In
particular, if for the same set of vectors we have two different score
functions, then the estimate $\Gamma^{t}$ should be the same (albeit the
actual threshold may differ). First, we introduce some terminology.

######  Definition 1 (Order-isomorphism).

Two score functions $s,\hat{s}:\Delta^{k-1}\mapsto\mathbb{R}$ are said to be
_order-isomorphic_ if, for all $p,q\in\Delta^{k-1}$:

  * •

$s(p)<s(q)\iff\hat{s}(p)<\hat{s}(q)$

  * •

$s(p)=s(q)\iff\hat{s}(p)=\hat{s}(q)$

  * •

$s(p)>s(q)\iff\hat{s}(p)>\hat{s}(q)$

The definition above, from order theory222Technically, an order-isomorphism is
a bijective function defined between two posets that preserves and reflects
orderings. This is slightly different from our setting, where we have a single
set without an ordering ($\Delta^{k-1}$) and define two separate orderings on
it.. This captures the idea that if two different score functions do not
change the ranking of a set of vectors, then they can be considered to be
basically the same. Note that the third point in the definition is implied by
the first two.

We now introduce our lemma.

######  Lemma 1 (Ordering Lemma).

If two score functions $s,\hat{s}$ are order-isomorphic then, for a fixed $f$,
$D^{s}$, $D^{t}$, and $\Gamma^{s}$, we have that
$\Gamma^{t}=\hat{\Gamma^{t}}$, where $\Gamma^{t}$ and $\hat{\Gamma^{t}}$ are
the target performance estimates given by $s$ and $\hat{s}$ respectively.

###### Proof.

Denote $t$ and $\hat{t}$ the threshold obtained by $s$ and $\hat{s}$
respectively. Recall that $t$ and $\hat{t}$ take on the possible values of the
range of their respective score functions, calculated for data in $D^{s}$. Of
course, they are possibly different. However, there exists a probability
vector $p\in\operatorname{ran}f(x)$ such that both $t=s(p)$ and
$\hat{t}=\hat{s}(p)$. To see why this is, observe that the set
$q\in\operatorname{ran}f(x)$ such that $s(q)<s(p)$ is exactly the same as
$\hat{s}(q)<\hat{s}(q)$ due to order-isomorphism. Thus, while $t$ and
$\hat{t}$ are possibly different, they must come from the same vector $p$.

Next, for $x\in D^{t}$, due to order-isomorphism, $s(f(x))<t=s(p)$ if and only
if $\hat{s}(f(x))<\hat{t}=\hat{s}(p)$. Thus, the sets $\\{s(f(x))<t\mid x\in
D^{t}\\}$ and $\\{\hat{s}(f(x))<\hat{t}\mid x\in D^{t}\\}$ are the same. Thus
$\Gamma^{t}=\hat{\Gamma^{t}}$. ∎

The Ordering Lemma allows us to explore a variety of score functions, and show
that they yield the same estimate simply by showing that they are order-
isomorphic. In the next section, we do just that. We conclude with two lemmas
that will play a role in future results.

######  Lemma 2.

The property of being order-isomorphic is an equivalence relation on the set
of score functions.

###### Proof.

A score function is clearly order-isomorphic with itself, and if $s$ is order-
isomorphic with $\hat{s}$ then $\hat{s}$ is order-isomorphic with $s$. Lastly,
if $s$ is order-isomorphic with $\hat{s}$ and $\hat{s}$ is order-isomorphic
with $\hat{s}$, then $s$ is order-isomorphic with $\hat{s}$ by transitivity of
the biconditional (see the definition of order-isomorphic). Hence, we have
reflexivity, symmetry, and transitivity. ∎

In this paper, we use monotone in the order-theoretic sense, i.e.,
monotonically increasing, or order-preserving.

######  Lemma 3.

Consider two score functions $s$ and $\hat{s}$ such that $\hat{s}=g(s)$, where
$g$ is strictly monotonic. Then $s$ and $\hat{s}$ are order-isomorphic.

###### Proof.

Follows from definition of monotonicity. ∎

######  Remark.

The above lemma seems quite obvious but we state it here to formally state
that $\Gamma^{t}$ is invariant under monotone transformations of the score
function. Namely, scaling, square root, etc., have no effect. This is
important as there are some potential score functions, discussed in the
section below, which are actually just monotone transformations of other score
functions. This lemma allows us to collapse them as one case.

###  2.3 Exploring Score Functions

For a practitioner of the ATC method, an important question that may arise is
which score function to use. Indeed, the literature contains many examples of
score functions that capture the rough intuition of being higher when more
skewed and lower when more uniform. Below is a list of such score
functions333Note that the use of score function here is not the same as a
score function in decision theory. seen in the literature, given a vector $p$
with components $(p_{i})_{1}^{k}$:

  * •

$L^{\infty}$ norm, or maximum confidence: $\max_{1}^{k}p_{i}$

  * •

Negative entropy: $\sum_{1}^{k}p_{i}\log(p_{i})$

  * •

$L^{2}$ norm: $\sqrt{\sum_{1}^{k}p_{i}^{2}}$. Of course, we can take the
squared $L^{2}$, which is order-isomorphic due to strict monotonicty of square
root (Lemma 3). The squared $L^{2}$ is quite prevalent in many different
fields: in economics it is called the Herfindahl-Hirschman index and measures
market concentration (Rhoades, 1993), in ecology it is called the Simpson
index and measures wildlife diversity (Simpson, 1949). The underlying
principle is that it captures how uniform or skewed a probability vector is.
The $L^{2}$ norm has a deep connection to the $\chi^{2}$ statistical test.

  * •

$L^{1}$ distance to the uniform vector $\mathcal{U}_{k}=(1/k,\dots,1/k)$:
$\sum_{1}^{k}|p_{i}-1/k|$. Note that half the $L^{1}$ distance gives the total
variation distance, and these two are clearly order-isomorphic (Lemma 3).

  * •

$L^{2}$ distance to $\mathcal{U}_{k}$: $\sqrt{\sum_{1}^{k}(p_{i}-1/k)^{2}}$

  * •

Other distances or divergences to $\mathcal{U}_{k}$, e.g., Jensen-Shannon

Thus, the method of Garg et al. (2022) has numerous possible implementations,
depending on the chosen score function. It is not clear whether there is a
best score function, or how to go about choosing one. Certainly, different
score functions capture different information about the vector. The task for
the practitioner then is seeing which score function works best for their
particular case, through experimentation.

###  2.4 The Case of Binary Classification

While choosing the best score function seems to be a difficult problem that
can only be solved experimentally, in the particular case of binary
classification, or $\mathbb{R}^{2}$, we can get a simple characterization. We
can show that a large class of natural score functions are order-isomorphic.
This result shows that in the binary classification case, the choice becomes
quite easy, and it follows to simply choose the most computationally cheap
score function. In particular, we have the following theorem.

######  Theorem 1.

In $\mathbb{R}^{2}$, on the probability simplex $\Delta^{1}$, the following
score functions are order-isomorphic:

  1. 1.

$L^{\infty}$ norm

  2. 2.

$L^{2}$ norm

  3. 3.

$L^{1}$ distance to the uniform vector $(1/2,1/2)$

  4. 4.

$L^{2}$ distance to the uniform vector $(1/2,1/2)$

  5. 5.

negative entropy

  6. 6.

Jensen-Shannon distance to the uniform vector $(1/2,1/2)$

###### Proof.

Let $p,q\in\mathbb{R}^{2}$, particularly $p,q\in\Delta^{1}$, meaning that
their $L^{1}$ norm is $1$. Parameterize them as $p=(a,1-a)$ and $q=(b,1-b)$.
Without loss of generality, $a\geq 1-a$ and $b\geq 1-b$. Based on the $L^{1}$
norm constraint, $a,b\in[0.5,1]$. Observe that with this parameterization,
$\|p\|_{\infty}=a$ and $\|q\|_{\infty}=b$.

We will show that each of score functions (2) - (6) are order-isomorphic to
(1), as numbered above. This will then imply that all of them are order-
isomorphic to each other by Lemma 2.

Our proof strategy is as follows: from our parameterization, we can consider
the score function to only be a function of the first component (e.g., $a$ or
$b$). If the score function is strictly monotone in this argument, then it
follows that $a<b$ iff $s(a)<s(b)$. Another way of looking at it is that the
score function is a strictly monotone transformation of $L^{\infty}$ and so by
Lemma 3, they are order-isomorphic.

We now show this for each of the score functions listed above from (2) - (6).

  1. 2.

We work with the squared $L^{2}$ for ease of computation. We have
$a^{2}+(1-a)^{2}=2a^{2}-2a+1$, which is strictly monotone on the interval
$a\in[0.5,1]$. Thus, the result follows. To make this clear, observe that
$\|p\|_{2}<\|q\|_{2}\iff 2a^{2}+1-2a<2b^{2}+1-2b\iff a^{2}-a<b^{2}-b\iff a<b$,
as the function $g(y)=y^{2}-y$ is strictly increasing for $y\in[0.5,1]$.

  2. 3.

$\|p-(1/2,1/2)\|_{1}=|a-0.5|+|(1-a)-0.5|=a-0.5+0.5-1+a=2a-1$ which is strictly
monotone in $a$ over $[0.5,1]$ hence the result follows.

  3. 4.

We work with squared $L^{2}$. We have
$(a-0.5)^{2}+(1-a-0.5)^{2}=2(a-0.5)^{2}=2a^{2}-2a+0.5$, which is strictly
monotone for $a\in[0.5,1]$.

  4. 5.

We have $a\log(a)+(1-a)\log(1-a)$. Taking the first derivative, we get
$\log(a)-\log(1-a)$, which is $>0$ for $a\in[0.5,1]$ as $\log$ is strictly
monotone. It then follows that $a\log(a)+(1-a)\log(1-a)$ is strictly monotone
for $a\in[0.5,1]$.

  5. 6.

We have
$\frac{1}{2}[a\log\frac{a}{0.5}+(1-a)\log\frac{1-a}{0.5}+0.5\log\frac{0.5}{a}+0.5\log\frac{0.5}{1-a}]$,
which is strictly increasing on $a\in[0.5,1]$ (can be seen by taking the first
derivative or graphing).

Thus, all of (2) - (6) are order-isomorphic with (1), and hence they are all
order-isomorphic with each other.

∎

To summarize, the commonly used score functions — $L^{\infty}$, $L^{2}$ (and
its squared form, known variously as the Herfindahl-Hirschman index or the
Simpson index), $L^{1}$ to uniform (and its scaled by $1/2$ form, the total
variation distance), $L^{2}$ to uniform, negative entropy, and Jensen-Shannon
to uniform — all induce the same orderings over probability vectors in
$\mathbb{R}^{2}$.

###  2.5 The Case of Multi-Class Classification ($\mathbb{R}^{\geq 3}$)

Unfortunately, Theorem 1 does not hold for $\mathbb{R}^{3}$. For a simple
counterexample showing that $L^{2}$ and $L^{\infty}$ are not order-isomorphic,
consider $p=(0.5,0.2,0.3)$ and $q=(0.5,0.5,0)$. Then, $\|p\|_{2}^{2}=0.38$,
$\|q\|_{2}^{2}=0.5$, and $\|p\|_{\infty}=\|q\|_{\infty}=0.5$. So
$\|p\|_{2}<\|q\|_{2}$ but $\|p\|_{\infty}\nless\|q\|_{\infty}$. It is possible
to construct counterexamples for the other score functions as well. As well,
as $\mathbb{R}^{3}$ is a subspace of $\mathbb{R}^{>3}$, it does not hold for
$\mathbb{R}^{\geq 3}$.

The order-isomorphism that still holds in $\mathbb{R}^{\geq 3}$ is between the
$L^{2}$ norm and $L^{2}$ distance to uniform, shown below.

######  Theorem 2.

In $\mathbb{R}^{k}$, on the probability simplex $\Delta^{k-1}$, the score
functions $\|\bullet\|_{2}$ ($L^{2}$ norm) and $\|\bullet-1/k\|_{2}$ ($L^{2}$
distance to uniform) are order-isomorphic.

###### Proof.

Let $p\in\Delta^{k-1}$ be written as $(p_{i})_{1}^{k}$. We have the constraint
that $\sum_{1}^{k}p_{i}=1$. To enforce this constraint, we can substitute
$p_{k}=1-\sum_{1}^{k-1}p_{i}$. For ease of computation, we work with the
squared forms of the score functions, which we denote by $s$ and $\hat{s}$
respectively. So $s(p)=\sum_{1}^{k-1}p_{i}^{2}+(1-\sum_{1}^{k-1}p_{i})^{2}$,
and
$\hat{s}(p)=\sum_{1}^{k-1}(p_{i}-\frac{1}{k})^{2}+(1-\frac{1}{k}-\sum_{1}^{k-1}p_{i})^{2}$.

Instead of expanding these expressions, we can analyze their gradients. Now,
$s$ and $\hat{s}$ are functions of $k-1$ independent variables (because of our
substitution for $p_{k}$). For some variable $p_{j}$, we have $\frac{\partial
s}{\partial p_{j}}=2p_{j}-2(1-\sum_{1}^{k-1}p_{i})$, and
$\frac{\partial\hat{s}}{\partial
p_{j}}=2(p_{j}-\frac{1}{k})-2(1-\frac{1}{k}-\sum_{1}^{k-1}p_{j})$. By
expanding the $1/k$ term, we can cancel them. Thus, $\forall p_{i}$,
$\frac{\partial s}{\partial p_{i}}=\frac{\partial\hat{s}}{\partial p_{i}}$.

Hence, $\nabla s=\nabla\hat{s}$, and by the mean value theorem, $s$ and
$\hat{s}$ differ only by a constant, and thus $\hat{s}$ is a monotone
transformation of $s$, which by Lemma 3 completes the proof. ∎

######  Remark.

In fact, Theorem 2 holds for the $L^{2}$ distance to a vector whose components
are all the same, as this will allow the gradients to be equal. As we are on
$\Delta^{k-1}$, the only such vector is the uniform probability vector. In
general, $L^{2}$ norm and $L^{2}$ distance to a fixed vector are not order-
isomorphic. For example, fix $r=(0.3,0.7)$. Take $p=(0.4,0.6)$ and
$q=(0.5,0.5)$. Then observe $\|p\|_{2}^{2}=0.52>\|q\|_{2}^{2}=0.5$, but
$\|p-r\|_{2}^{2}=0.02<\|q-r\|_{2}^{2}=0.08$.

However, because in general the other score functions from Theorem 1 do not
induce the same orderings, we cannot guarantee that they will yield the same
estimate. Hence, in the multi-class setting, we once again have to ponder
which score function will give us the best estimate. As we cannot know this
theoretically, in the next section, we run experiments on three well-known NLP
data sets with different score functions.

##  3 Experiments

###  3.1 Methods

We ran experiments on three NLP data sets for multi-class classification:
Emotion (Saravia et al., 2018), a data set of tweets labeled with one of 6
emotions, TweetEval (Barbieri et al., 2018), a data set of tweets labeled with
one of 20 emojis, and Banking77 (Casanueva et al., 2020), a data set of online
banking queries labeled with one of 77 intents. The data sets came with train,
validation, and testing splits; if not, a validation set of 20% of the
training set was created and set aside.

The basic schema of the experiment is that we finetuned DistilBERT-base-
uncased (Sanh et al., 2019) on the training set. The hyperparameters used are
learning rate: 2e-5; batch size: 256; epochs: 5; weight decay: 0.01. We then
used the validation set to estimate performance on the testing set, and then
actually tested the model on the testing set. We calculated and stored the
absolute difference between the estimated accuracy and the true accuracy. We
present our methodology in the algorithm box.

Algorithm 1 Experiment pseudocode

Dataset with $k$ classes labeled $\\{0,1,...,k-1\\}$, split into training
$\mathcal{T}$, testing $\mathcal{S}$, and validation sets $\mathcal{V}$; pre-
trained DistilBERT-base-uncased model

Results $\leftarrow$ empty list

for $d\in\\{2,3,...k\\}$ do

$T\leftarrow$ subset of $\mathcal{T}$ with labels $<d$

$S\leftarrow$ subset of $\mathcal{S}$ with labels $<d$

$V\leftarrow$ subset of $\mathcal{V}$ with labels $<d$

Finetune DistilBERT-base-uncased on $T$

$a\leftarrow$ accuracy of model on $S$

for $m$ in {ATC-Max, ATC-NE, ATC-L2n, ATC-L1, ATC-L2, ATC-JS, DoC} do

for $n=1$ to $1000$ do

$V^{*}\leftarrow$ bootstrap $V$ with $|V|$ samples

$\tilde{a}\leftarrow$ estimated accuracy on $S$ using $V^{*}$ using method $m$

$\epsilon\leftarrow|a-\tilde{a}|$

Append list $[i,m,n,\epsilon]$ to Results

end for

end for

end for

return Results

We tested 6 different score functions for Garg et al. (2022)’s method, which
is referred to in the results as ATC (average thresholded confidence) per
their paper. The score functions we tested are: $L^{\infty}$ (ATC-Max),
negative entropy (ATC-NE), $L^{2}$ norm (ATC-L2n), $L^{1}$ distance to uniform
(ATC-L1), $L^{2}$ distance to uniform (ATC-L2), and Jensen-Shannon distance to
uniform (ATC-JS). We also implemented an older baseline for accuracy
estimation, the difference-in-confidence (DoC) method (Guillory et al., 2021),
as a comparison. Briefly, this method uses the difference in average of max
confidence (hence, DoC) as a distance between distributions. By fitting a
linear regression using validation data, this method estimates accuracy on the
test set by the DoC between the test set and a held-out set.

We also wanted to explore the performance of different score functions for
varying numbers of dimensions. The data sets we use have 6, 20, and 77
dimensions respectively. To simulate other dimensions, we simply just took the
first $\hat{k}$, $2\leq\hat{k}\leq k$ classes, where $k$ is the total number
of classes: e.g., the Emotion data set has labels $\\{0,1,...,5\\}$, we take
$\\{0,1\\},\\{0,1,2\\},\\{0,1,2,3\\}$, etc, to make, respectively, a 2-class,
3-class, a 4-class problem, etc.

Therefore, for each dimension, we tried 7 total methods. For each dimension-
method pair, we did 1000 runs of the experiment, by taking a subset of the
validation set via bootstrap sampling for each run. This makes our results
more statistically robust and allows us to quantify a confidence interval.

###  3.2 Results

For sake of space, we only present the full table of results for the Emotion
experiment, which we see in Table 1. The full table of results for TweetEval
and Banking77 are in the appendix. The bolded value corresponds to the lowest
mean absolute error for that dimension. First of all, ATC outperforms the DoC
baseline no matter the chosen score function. Second of all, as expected per
Theorem 1, for 2 dimensions, all the ATC score functions yielded exactly the
same result for every run. Looking at Table 1, the best score function is
still unclear. It seems that Jensen-Shannn performs best for dimensions 3, 4,
and 6, but is beat for dimension 4. It seems the best as it wins in most
dimensions.

Table 1: Mean [95% confidence interval] absolute error of accuracy prediction for Emotion data set. Bolded cells are the lowest mean absolute error for that dimension. # Dimensions |  ATC-JS |  ATC-L1 |  ATC-L2 |  ATC-L2n |  ATC-Max |  ATC-NE |  DoC
---|---|---|---|---|---|---|---
2 |  0.49 [0.16,1.02] |  0.49 [0.16,1.02] |  0.49 [0.16,1.02] |  0.49 [0.16,1.02] |  0.49 [0.16,1.02] |  0.49 [0.16,1.02] |  1.98 [0.06,5.79]
3 |  1.28 [0.00,3.07] |  1.37 [0.07,2.93] |  1.37 [0.07,2.93] |  1.38 [0.07,2.93] |  1.37 [0.07,2.93] |  1.29 [0.07,3.00] |  3.09 [0.11,8.14]
4 |  1.31 [0.06,2.69] |  1.33 [0.12,2.75] |  1.33 [0.06,2.75] |  1.33 [0.06,2.75] |  1.33 [0.12,2.75] |  1.32 [0.12,2.69] |  3.11 [0.14,8.20]
5 |  0.84 [0.05,2.48] |  0.66 [0.00,1.71] |  0.66 [0.05,1.76] |  0.66 [0.05,1.76] |  0.66 [0.00,1.71] |  0.87 [0.05,2.02] |  2.73 [0.14,7.82]
6 |  1.22 [0.25,2.65] |  1.33 [0.30,2.85] |  1.33 [0.30,2.85] |  1.33 [0.30,2.85] |  1.33 [0.30,2.85] |  1.26 [0.20,2.80] |  2.97 [0.11,7.74]

However, this is only for the Emotion data set. Indeed, in experiments on
TweetEval and Banking77, a rather different picture emerges. To look at this
more rigorously, we calculated, for each of the three data sets, the
proportion of dimensions that each method yields the lowest mean absolute
error. In this calculation, we exclude the 2-class setting, per Theorem 1. We
consider a tie by awarding all tied functions a win; thus the counts may not
add up to the total number of dimensions being used as “rounds” in this
comparison.

Table 2: Number of dimensions for which each method achieves the lowest mean absolute error. Total is the number of dimensions for which comparisons were made (excludes 2-class setting). Existence of ties means that counts do not necessarily add to total. Method | Emotion | TweetEval | Banking77
---|---|---|---
ATC-JS | 3 | 1 | 2
ATC-L1 | 1 | 5 | 12
ATC-L2 | 0 | 4 | 9
ATC-L2n | 0 | 4 | 2
ATC-Max | 0 | 7 | 39
ATC-NE | 0 | 1 | 4
DoC | 0 | 0 | 8
Total | 4 | 18 | 75

Some interesting observations can be noted here. First, ATC-JS performs poorly
for TweetEval and Banking77, contradicting our initial excitement with
Emotion. Secondly, ATC-Max wins a plurality of dimensions for TweetEval, and
wins an even larger plurality for Banking77. Interestingly, Banking77 is the
only data set for which DoC bests the ATC methods at least once. This may be
because it is a more complicated data set. In fact, the mean absolute error on
Banking77 is much higher than the other data sets for the same method and
dimension.

We also see, as expected by Theorem 2, that ATC-L2 and ATC-L2n yield equal (or
equal up to several decimal places, reflecting computational precision)
estimates. For TweetEval, ATC-L2 is always tied with ATC-L2n, while for
Banking77 they are within $10^{-6}$ of each other.

Now, in our discussion so far we have only been comparing the actual means of
the absolute error. However, as we took bootstrap samples, we have a bootstrap
distribution. We can therefore use the entire distribution of errors to make
comparisons. Figure 1 shows violin plots of the distribution of errors for
each method and dimension for the TweetEval data set. Firstly, we can see that
the DoC distribution is much wider than the ATC distributions. They also show
considerable overlap between the distributions, and so it is difficult to say
whether one is really lower or higher than the other. We are therefore
interested in using this distribution to test if the differences between
methods are statistically significant.

Figure 1: Distribution of absolute errors for TweetEval, represented as violin
plot with overlayed box plot to show quartiles. Headings refer to number of
dimensions.

Hence, we performed ANOVA tests on the experimental results for our three data
sets. We performed a two-way ANOVA on the mean absolute error, using the
dimension and method as independent variables. Our ANOVA was appropriately
powered at a significance level of 0.05, power 0.99, and minimum detectable
effect size of 0.1 (what Cohen (2013) calls a “small” effect size for the
$f^{2}$ statistic). For all three data sets, the two-way ANOVA detected a
significant difference between methods. We then performed post-hoc analysis
with Tukey’s Honestly Significant Difference (HSD) method, which tests
pairwise differences. For Emotion, the only significant differences were seen
between DoC and the other ATC methods. For TweetEval and Banking77,
significant differences were observed for all pairwise comparisons except for
ATC-L2 and ATC-L2n, as expected due to Theorem 2. It may be that significant
differences were yielded for TweetEval and Banking77 as the experimental
results data set is much larger than for Emotion (e.g., for Banking77, we have
1000 runs $\times$ 76 possible dimensions $\times$ 7 methods $=$ 532,000 data
points). Looking at the comparisons between score functions for ATC, even when
there is a significant difference, the differences are on the magnitude of
$10^{-1}$, suggesting that different score functions, while they may yield
different estimates, yield estimates within one decimal point of each other.

##  4 Discussion and Conclusion

In this paper we explored the average thresholded confidence (ATC) method of
Garg et al. (2022), specifically the question of how to choose the score
function, an important hyperparameter in their method. We presented some
theoretical results about how different score functions can give the same
estimate. Our results on orderings of probability vectors, namely that several
score functions induce the same ordering, may also be of independent interest.
Because a clean theoretical result does not exist for $\mathbb{R}^{\geq 3}$,
we conducted several large-scale experiments on three NLP data sets to analyze
which score function best predicts the true accuracy on a test set. Our ANOVA
results show that while there are significant differences between the score
functions, they are on the magnitude of $10^{-1}$, which suggests that the
choice of score function may not be important. Therefore, we would suggest to
use the computationally fastest score function, which, in our benchmarks, is
the $L^{\infty}$ norm. In our tests, this was implemented in Python by the
numpy library. We compared this against all the other score functions,
variously implemented in numpy and scipy. The negative entropy and Jensen-
Shannon were by far the slowest, likely owing to the difficulty in calculating
logarithms. However, compared to the computational cost of inference, these
differences may be negligible.

Therefore, for a practitioner of Garg et al. (2022)’s method, we conclude that
the $L^{\infty}$ is the best score function to use. In the binary case, the
choice definitely does not matter; and in the multi-class case, it may, but
not so much, and the $L^{\infty}$ is fastest to compute.

It is important to note that our comparisons between methods were predicated
on taking bootstrap samples of the validation set, and calculating a mean,
which the original paper of Garg et al. (2022) did not do. We therefore
suggest that this is a simple modification to their method which decreases
random error.

There are still several interesting avenues of study. First of all, it is not
clear why the score function in Garg et al. (2022)’s method has to measure the
“confidence” of the classifier. A justification is not provided in Garg et al.
(2022), and our results simply show the importance of the induced ordering.
Elucidating if the score function needs to necessarily fulfill this property,
and why, would be a gainful line of research. The ATC method outperforms
several previous baselines in Garg et al. (2022), and we reinforce that in our
paper by showing it outperforms DoC - however, it is still unclear why it
seems to work so well. As well, the method of Garg et al. (2022) is quite new,
and thus has not necessarily been corroborated and tested extensively. In this
paper we tested its performance on NLP data sets. It will be interesting to
see if the superiority of ATC continues.

## Acknowledgements

Muhammad Maaz was an intern at Amazon at the time this work was done. Muhammad
Maaz would also like to acknowledge support through the Vanier Canadian
Graduate Scholarship, administered by the Natural Sciences and Engineering
Research Council of Canada.

## References

  * Garg et al. [2022] Saurabh Garg, Sivaraman Balakrishnan, Zachary Lipton, Behnam Neyshabur, and Hanie Sedghi.  Leveraging unlabeled data to predict out-of-distribution performance.  In _International Conference on Learning Representations (ICLR)_ , 2022.
  * Ben-David et al. [2010a] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan.  A theory of learning from different domains.  _Machine learning_ , 79(1):151–175, 2010a.
  * Ben-David et al. [2010b] Shai Ben-David, Tyler Lu, Teresa Luu, and David Pal.  Impossibility theorems for domain adaptation.  In Yee Whye Teh and Mike Titterington, editors, _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , volume 9 of _Proceedings of Machine Learning Research_ , pages 129–136, Chia Laguna Resort, Sardinia, Italy, 13–15 May 2010b. PMLR.  URL https://proceedings.mlr.press/v9/david10a.html.
  * Guillory et al. [2021] Devin Guillory, Vaishaal Shankar, Sayna Ebrahimi, Trevor Darrell, and Ludwig Schmidt.  Predicting with confidence on unseen distributions.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pages 1134–1144, 2021.
  * Deng and Zheng [2021] Weijian Deng and Liang Zheng.  Are labels always necessary for classifier accuracy evaluation?  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 15069–15078, 2021.
  * Deng et al. [2021] Weijian Deng, Stephen Gould, and Liang Zheng.  What does rotation prediction tell us about classifier accuracy under varying testing environments?  In _International Conference on Machine Learning_ , pages 2579–2589. PMLR, 2021.
  * Jiang et al. [2022] Yiding Jiang, Vaishnavh Nagarajan, Christina Baek, and J Zico Kolter.  Assessing generalization of SGD via disagreement.  In _International Conference on Learning Representations_ , 2022.  URL https://iclr.cc/virtual/2022/spotlight/6301.
  * Chen et al. [2021] Mayee Chen, Karan Goel, Nimit S Sohoni, Fait Poms, Kayvon Fatahalian, and Christopher Ré.  Mandoline: Model evaluation under distribution shift.  In _International Conference on Machine Learning_ , pages 1617–1629. PMLR, 2021.
  * Platanios et al. [2016] Emmanouil Antonios Platanios, Avinava Dubey, and Tom Mitchell.  Estimating accuracy from unlabeled data: A bayesian approach.  In _International Conference on Machine Learning_ , pages 1416–1425. PMLR, 2016.
  * Ramponi and Plank [2020] Alan Ramponi and Barbara Plank.  Neural unsupervised domain adaptation in nlp—a survey.  _arXiv preprint arXiv:2006.00632_ , 2020.
  * Rhoades [1993] Stephen A Rhoades.  The herfindahl-hirschman index.  _Fed. Res. Bull._ , 79:188, 1993.
  * Simpson [1949] Edward H Simpson.  Measurement of diversity.  _Nature_ , 163(4148):688–688, 1949.
  * Saravia et al. [2018] Elvis Saravia, Hsien-Chi Toby Liu, Yen-Hao Huang, Junlin Wu, and Yi-Shin Chen.  CARER: Contextualized affect representations for emotion recognition.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 3687–3697, Brussels, Belgium, October-November 2018. Association for Computational Linguistics.  doi: 10.18653/v1/D18-1404.  URL https://www.aclweb.org/anthology/D18-1404.
  * Barbieri et al. [2018] Francesco Barbieri, Jose Camacho-Collados, Francesco Ronzano, Luis Espinosa-Anke, Miguel Ballesteros, Valerio Basile, Viviana Patti, and Horacio Saggion.  Semeval 2018 task 2: Multilingual emoji prediction.  In _Proceedings of The 12th International Workshop on Semantic Evaluation_ , pages 24–33, 2018.
  * Casanueva et al. [2020] Iñigo Casanueva, Tadas Temcinas, Daniela Gerz, Matthew Henderson, and Ivan Vulic.  Efficient intent detection with dual sentence encoders.  In _Proceedings of the 2nd Workshop on NLP for ConvAI - ACL 2020_ , mar 2020.  URL https://arxiv.org/abs/2003.04807.  Data available at https://github.com/PolyAI-LDN/task-specific-datasets.
  * Sanh et al. [2019] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf.  Distilbert, a distilled version of BERT: smaller, faster, cheaper and lighter.  _arXiv preprint arXiv:1910.01108_ , 2019.
  * Cohen [2013] Jacob Cohen.  _Statistical power analysis for the behavioral sciences_.  Routledge, 2013.

##  Appendix A Appendix

###  A.1 Full results on TweetEval

Below are the full results on the TweetEval dataset.

Table 3: Mean [95% confidence interval] absolute error of accuracy prediction for TweetEval data set. # Dimensions |  ATC-JS |  ATC-L1 |  ATC-L2 |  ATC-L2n |  ATC-Max |  ATC-NE |  DoC
---|---|---|---|---|---|---|---
2 |  2.00 [0.08, 5.24] |  2.00 [0.08, 5.24] |  2.00 [0.08, 5.24] |  2.00 [0.08, 5.24] |  2.00 [0.08, 5.24] |  2.00 [0.08, 5.24] |  6.32 [0.23,17.69]
3 |  1.46 [0.10, 4.14] |  1.94 [0.09, 4.67] |  1.85 [0.09, 4.95] |  1.85 [0.09, 4.95] |  1.94 [0.09, 4.67] |  1.62 [0.04, 4.44] |  5.80 [0.28,16.10]
4 |  1.38 [0.03, 4.22] |  1.27 [0.11, 3.55] |  1.29 [0.10, 3.52] |  1.29 [0.10, 3.52] |  1.24 [0.10, 3.42] |  1.35 [0.07, 3.68] |  5.22 [0.26,14.62]
5 |  2.36 [0.22, 5.20] |  1.69 [0.05, 4.01] |  2.11 [0.22, 4.67] |  2.11 [0.22, 4.67] |  1.98 [0.06, 4.67] |  2.10 [0.07, 5.34] |  4.92 [0.20,13.85]
6 |  1.33 [0.12, 3.71] |  1.17 [0.02, 3.50] |  1.37 [0.03, 3.77] |  1.37 [0.03, 3.77] |  1.23 [0.06, 3.86] |  1.34 [0.11, 3.77] |  4.98 [0.34,13.74]
7 |  1.00 [0.03, 3.06] |  0.95 [0.03, 2.84] |  1.27 [0.05, 3.40] |  1.27 [0.05, 3.40] |  1.56 [0.08, 3.92] |  1.15 [0.05, 3.52] |  4.86 [0.20,14.07]
8 |  1.65 [0.09, 4.17] |  1.53 [0.07, 3.85] |  1.34 [0.04, 3.61] |  1.34 [0.04, 3.61] |  1.46 [0.06, 3.87] |  1.48 [0.03, 4.28] |  4.67 [0.20,12.95]
9 |  1.78 [0.09, 4.12] |  1.68 [0.15, 3.94] |  1.40 [0.03, 3.82] |  1.40 [0.03, 3.82] |  1.80 [0.12, 4.18] |  1.61 [0.08, 4.36] |  4.50 [0.23,13.12]
10 |  1.07 [0.03, 3.07] |  1.23 [0.10, 3.35] |  1.12 [0.04, 3.13] |  1.12 [0.04, 3.13] |  1.16 [0.07, 2.99] |  1.05 [0.06, 2.97] |  4.24 [0.20,11.53]
11 |  1.18 [0.05, 3.22] |  1.13 [0.03, 2.84] |  1.20 [0.11, 3.01] |  1.20 [0.11, 3.01] |  1.39 [0.02, 3.52] |  1.43 [0.09, 3.44] |  4.25 [0.13,11.72]
12 |  2.14 [0.41, 4.35] |  1.83 [0.15, 4.25] |  1.26 [0.08, 3.28] |  1.26 [0.08, 3.28] |  1.31 [0.07, 3.47] |  1.47 [0.04, 3.36] |  4.17 [0.15,11.99]
13 |  2.07 [0.08, 4.29] |  1.37 [0.05, 3.55] |  1.44 [0.07, 3.61] |  1.44 [0.07, 3.61] |  1.44 [0.05, 3.50] |  1.62 [0.15, 3.58] |  4.24 [0.19,11.63]
14 |  1.65 [0.13, 3.69] |  1.05 [0.06, 2.93] |  0.96 [0.04, 2.75] |  0.96 [0.04, 2.75] |  1.06 [0.07, 2.82] |  1.15 [0.07, 2.92] |  3.90 [0.20,11.58]
15 |  1.87 [0.15, 4.16] |  2.44 [0.12, 4.84] |  1.05 [0.04, 3.18] |  1.05 [0.04, 3.18] |  0.93 [0.01, 2.67] |  1.56 [0.05, 3.69] |  3.89 [0.20,10.79]
16 |  1.69 [0.20, 3.90] |  1.57 [0.05, 3.61] |  1.14 [0.05, 2.96] |  1.14 [0.05, 2.96] |  1.08 [0.08, 2.85] |  1.32 [0.05, 3.51] |  3.68 [0.15,10.58]
17 |  2.19 [0.12, 4.70] |  2.32 [0.28, 4.49] |  1.74 [0.12, 4.22] |  1.74 [0.12, 4.22] |  1.37 [0.14, 3.40] |  2.15 [0.24, 4.52] |  3.68 [0.14,10.27]
18 |  2.14 [0.13, 4.36] |  2.06 [0.15, 4.04] |  1.35 [0.06, 3.21] |  1.35 [0.06, 3.21] |  0.93 [0.04, 2.74] |  1.74 [0.08, 4.01] |  3.75 [0.12,10.78]
19 |  2.34 [0.36, 4.64] |  2.36 [0.31, 4.53] |  1.90 [0.19, 4.07] |  1.90 [0.19, 4.07] |  1.84 [0.22, 3.67] |  1.94 [0.22, 4.28] |  3.64 [0.17,10.41]
20 |  1.52 [0.08, 3.56] |  1.38 [0.02, 3.42] |  0.92 [0.03, 2.54] |  0.92 [0.03, 2.54] |  0.91 [0.06, 2.49] |  1.24 [0.02, 3.38] |  3.67 [0.12,10.11]

###  A.2 Full results on Banking77

Below are the full results on the Banking77 dataset.

Table 4: Mean [95% confidence interval] absolute error of accuracy prediction for Banking77 data set. # Dimensions |  ATC-JS |  ATC-L1 |  ATC-L2 |  ATC-L2n |  ATC-Max |  ATC-NE |  DoC
---|---|---|---|---|---|---|---
2 |  11.02 [1.25,22.50] |  11.02 [1.25,22.50] |  11.02 [1.25,22.50] |  11.02 [1.25,22.50] |  11.02 [1.25,22.50] |  11.02 [1.25,22.50] |  36.19 [1.53,94.85]
3 |  4.25 [0.83,10.00] |  4.26 [0.83,10.00] |  4.16 [0.00,10.00] |  4.16 [0.00,10.00] |  4.26 [0.83,10.00] |  4.15 [0.00,10.00] |  21.00 [0.74,54.33]
4 |  12.08 [1.84,26.88] |  11.45 [0.62,26.92] |  12.51 [0.62,26.25] |  12.51 [0.62,26.25] |  13.56 [3.12,29.38] |  12.25 [1.25,26.25] |  27.18 [1.07,70.96]
5 |  9.74 [0.50,22.50] |  10.06 [1.00,20.50] |  10.38 [1.00,24.00] |  10.38 [1.00,24.00] |  16.33 [4.00,26.00] |  9.92 [1.00,22.50] |  25.26 [0.89,67.67]
6 |  9.95 [2.08,22.93] |  10.90 [2.07,25.00] |  10.15 [2.50,21.67] |  10.15 [2.50,21.67] |  11.11 [0.00,21.25] |  10.00 [2.08,22.92] |  21.16 [0.80,57.49]
7 |  15.18 [6.79,21.82] |  14.02 [6.07,25.00] |  15.91 [6.79,23.57] |  15.91 [6.79,23.57] |  15.61 [2.14,23.93] |  15.47 [6.79,23.21] |  20.92 [1.29,57.63]
8 |  7.89 [0.00,18.12] |  7.54 [1.23,19.38] |  8.23 [0.62,19.69] |  8.23 [0.62,19.69] |  8.64 [0.31,18.12] |  8.01 [0.31,18.12] |  18.85 [0.75,51.12]
9 |  13.53 [3.89,24.17] |  14.13 [4.17,25.56] |  13.21 [3.33,23.89] |  13.21 [3.33,23.89] |  14.20 [3.61,21.94] |  13.39 [3.89,23.89] |  18.07 [1.00,52.34]
10 |  8.35 [1.25,17.25] |  9.37 [1.00,18.25] |  8.12 [0.50,17.25] |  8.12 [0.50,17.25] |  6.39 [0.75,14.00] |  8.32 [1.00,17.00] |  16.52 [0.70,44.82]
11 |  6.34 [0.22,14.55] |  5.26 [0.45,11.59] |  7.38 [0.45,13.41] |  7.38 [0.45,13.41] |  12.26 [2.73,17.95] |  6.83 [0.91,14.32] |  16.63 [0.53,43.67]
12 |  15.07 [6.01,21.25] |  13.07 [4.58,19.17] |  13.93 [5.60,22.71] |  13.94 [5.60,22.72] |  11.03 [2.71,20.42] |  14.84 [6.65,21.46] |  15.60 [0.95,43.44]
13 |  14.65 [8.26,20.19] |  11.40 [4.04,17.88] |  14.61 [10.35,21.35] |  14.62 [10.35,21.35] |  14.15 [5.96,20.19] |  14.96 [8.65,20.58] |  16.27 [0.79,44.72]
14 |  14.41 [9.46,19.64] |  16.66 [10.00,25.89] |  14.81 [9.29,20.91] |  14.82 [9.29,21.61] |  14.28 [7.32,22.68] |  14.53 [8.75,19.29] |  15.85 [0.58,42.72]
15 |  6.98 [0.50,14.83] |  7.68 [0.67,16.17] |  7.08 [1.83,15.50] |  7.09 [2.16,15.50] |  5.18 [0.00,13.17] |  7.02 [1.00,14.50] |  13.47 [0.29,36.89]
16 |  10.17 [2.03,17.03] |  10.32 [3.28,17.34] |  10.17 [1.88,17.03] |  10.18 [1.88,17.03] |  12.37 [3.44,18.28] |  10.33 [1.25,16.56] |  15.25 [0.85,40.44]
17 |  12.98 [5.29,18.68] |  12.09 [3.37,18.38] |  12.30 [5.29,19.27] |  12.31 [5.29,19.27] |  10.89 [2.50,18.53] |  12.83 [5.15,18.68] |  13.87 [0.38,39.30]
18 |  15.93 [10.69,21.11] |  15.60 [9.03,22.22] |  15.60 [9.58,21.39] |  15.61 [9.58,21.25] |  13.99 [4.31,20.84] |  15.81 [9.86,20.97] |  15.75 [0.56,39.51]
19 |  15.22 [7.76,21.71] |  13.55 [7.76,19.61] |  15.71 [7.49,23.82] |  15.71 [7.62,23.82] |  16.21 [9.47,21.84] |  15.70 [6.84,21.97] |  14.83 [0.55,40.29]
20 |  11.17 [6.12,17.88] |  12.64 [6.50,18.75] |  10.54 [5.38,17.75] |  10.54 [5.38,17.75] |  11.50 [2.12,17.62] |  10.95 [5.12,17.75] |  12.88 [0.54,34.25]
21 |  10.87 [2.86,17.50] |  9.28 [1.31,15.12] |  11.59 [5.00,18.10] |  11.59 [5.00,18.10] |  11.73 [6.06,17.98] |  10.99 [2.50,18.33] |  12.11 [0.58,32.72]
22 |  8.14 [2.84,12.62] |  8.31 [3.86,13.53] |  8.02 [2.05,13.30] |  8.03 [2.05,13.30] |  8.03 [1.36,13.30] |  8.13 [2.95,13.64] |  11.21 [0.73,30.96]
23 |  14.91 [9.02,20.11] |  16.21 [11.29,20.76] |  13.72 [7.28,21.63] |  13.72 [7.28,21.63] |  11.06 [4.67,16.85] |  14.66 [9.02,20.87] |  13.08 [0.63,35.23]
24 |  17.30 [10.00,23.44] |  17.79 [11.35,24.69] |  17.57 [11.15,23.12] |  17.58 [11.15,23.12] |  16.40 [8.23,24.06] |  17.32 [10.10,23.33] |  15.14 [0.70,39.56]
25 |  9.57 [3.80,16.00] |  9.16 [4.60,15.70] |  9.50 [4.60,15.70] |  9.51 [4.60,15.70] |  10.44 [4.50,15.30] |  9.59 [4.10,15.50] |  11.91 [0.52,33.70]
26 |  14.14 [7.69,19.52] |  14.91 [8.85,19.42] |  14.88 [5.87,21.25] |  14.89 [5.87,21.25] |  13.04 [5.58,20.29] |  14.51 [7.40,20.38] |  12.53 [0.39,32.96]
27 |  9.45 [5.83,12.97] |  10.18 [6.30,12.96] |  8.69 [4.17,12.78] |  8.70 [4.17,12.78] |  10.90 [3.15,17.13] |  8.18 [4.35,13.24] |  10.64 [0.31,29.46]
28 |  11.45 [7.41,16.34] |  11.37 [5.62,15.80] |  12.68 [6.70,18.93] |  12.68 [6.70,18.93] |  8.62 [3.21,16.34] |  12.26 [7.77,17.41] |  11.21 [0.48,30.88]
29 |  13.67 [9.66,18.53] |  12.95 [8.79,16.55] |  14.85 [9.83,20.09] |  14.85 [9.83,20.09] |  14.40 [7.84,18.62] |  13.98 [9.74,18.02] |  12.20 [0.53,31.21]
30 |  9.85 [5.00,15.33] |  12.44 [7.42,17.25] |  9.50 [4.08,14.92] |  9.51 [4.08,14.92] |  9.59 [4.58,14.50] |  9.65 [4.49,14.00] |  10.85 [0.66,29.41]
31 |  12.91 [8.15,16.87] |  12.29 [7.90,15.97] |  10.82 [5.97,16.29] |  10.82 [5.97,16.29] |  8.21 [2.50,14.52] |  12.07 [6.05,16.61] |  10.12 [0.39,27.73]
32 |  11.61 [7.27,15.16] |  12.50 [8.05,16.56] |  10.86 [7.34,14.61] |  10.86 [7.34,14.61] |  10.33 [4.21,14.77] |  11.50 [7.58,13.98] |  10.27 [0.41,26.97]
33 |  7.98 [3.79,12.20] |  9.20 [4.55,14.55] |  6.50 [3.11,10.61] |  6.50 [3.11,10.61] |  5.47 [0.76,9.93] |  7.15 [3.26,11.36] |  9.05 [0.34,25.48]
34 |  9.90 [5.81,13.82] |  10.85 [7.20,15.59] |  10.46 [6.47,13.98] |  10.47 [6.47,14.26] |  9.44 [4.93,12.87] |  9.95 [6.03,13.90] |  10.20 [0.45,27.38]
35 |  8.24 [4.50,11.71] |  9.87 [5.21,14.00] |  6.97 [3.07,10.71] |  6.97 [3.07,10.71] |  7.02 [2.79,11.71] |  7.86 [3.50,10.93] |  9.83 [0.35,27.80]
36 |  5.81 [1.67,10.56] |  8.89 [4.58,12.36] |  5.97 [2.01,11.74] |  5.97 [2.01,11.74] |  6.72 [2.08,12.36] |  5.60 [1.32,10.76] |  9.09 [0.31,25.31]
37 |  9.80 [6.55,12.97] |  10.34 [6.89,14.67] |  10.32 [5.95,14.12] |  10.32 [5.95,14.12] |  7.73 [3.11,12.91] |  10.12 [6.76,13.38] |  9.14 [0.39,25.21]
38 |  7.42 [2.11,12.83] |  10.90 [4.74,15.72] |  6.66 [1.12,12.90] |  6.66 [1.12,12.90] |  8.22 [3.95,12.44] |  6.81 [2.37,12.04] |  9.64 [0.45,25.95]
39 |  6.41 [1.22,11.67] |  6.41 [1.03,11.35] |  6.31 [1.47,10.64] |  6.31 [1.47,10.64] |  5.33 [0.64,9.29] |  6.50 [1.09,11.35] |  8.77 [0.32,23.10]
40 |  6.77 [2.00,11.44] |  7.25 [2.50,13.06] |  6.46 [2.75,10.38] |  6.46 [2.75,10.38] |  4.08 [0.25,8.64] |  6.91 [1.87,10.25] |  8.41 [0.40,23.84]
41 |  9.86 [5.00,14.21] |  13.37 [9.57,16.46] |  9.27 [5.18,13.41] |  9.27 [5.18,13.41] |  6.85 [2.32,11.71] |  9.89 [4.63,14.88] |  8.73 [0.30,23.70]
42 |  10.36 [7.14,14.82] |  10.53 [6.43,14.46] |  8.87 [5.42,12.14] |  8.87 [5.42,12.14] |  8.12 [4.35,12.32] |  9.67 [6.25,13.51] |  8.68 [0.39,24.11]
43 |  9.19 [4.82,13.55] |  9.91 [6.74,13.31] |  9.32 [4.83,13.72] |  9.32 [4.83,13.72] |  8.81 [3.95,13.02] |  9.65 [5.04,13.20] |  9.04 [0.41,24.58]
44 |  14.83 [11.08,17.61] |  13.81 [9.77,18.07] |  12.92 [9.20,16.93] |  12.92 [9.20,16.93] |  11.73 [7.33,16.43] |  14.12 [10.00,16.99] |  11.46 [0.45,27.87]
45 |  10.83 [7.00,14.40] |  10.62 [5.83,15.06] |  11.41 [6.50,15.61] |  11.41 [6.50,15.61] |  9.57 [4.94,14.11] |  11.49 [7.78,15.89] |  9.21 [0.52,24.59]
46 |  9.87 [6.90,13.37] |  10.08 [6.30,13.42] |  10.51 [7.17,14.51] |  10.52 [7.17,14.51] |  9.20 [3.85,13.70] |  10.17 [6.68,13.10] |  9.63 [0.40,25.13]
47 |  9.75 [4.95,13.72] |  9.22 [6.06,12.66] |  8.49 [4.52,13.40] |  8.49 [4.52,13.41] |  7.02 [1.65,11.70] |  9.12 [4.26,14.52] |  8.35 [0.50,22.93]
48 |  8.86 [4.64,13.18] |  8.45 [5.62,11.72] |  9.47 [4.74,12.81] |  9.47 [4.74,12.81] |  7.51 [3.49,11.25] |  8.91 [5.31,13.54] |  8.63 [0.37,23.22]
49 |  9.33 [5.51,13.11] |  8.24 [5.00,11.28] |  7.45 [4.69,11.12] |  7.45 [4.69,11.12] |  7.21 [3.82,10.71] |  8.65 [5.15,11.79] |  8.75 [0.33,23.38]
50 |  10.19 [7.50,13.30] |  10.06 [6.30,14.75] |  9.13 [5.75,13.90] |  9.13 [5.75,13.90] |  8.00 [4.05,13.10] |  10.04 [7.05,12.80] |  8.80 [0.31,23.04]
51 |  6.90 [2.40,11.18] |  5.98 [2.55,9.46] |  8.17 [4.16,12.26] |  8.17 [4.16,12.26] |  7.00 [3.43,11.67] |  7.54 [3.19,12.60] |  8.24 [0.29,22.34]
52 |  10.27 [6.54,14.09] |  10.16 [7.07,13.89] |  10.01 [5.53,13.99] |  10.01 [5.53,13.99] |  9.64 [4.52,13.32] |  9.49 [6.44,13.61] |  9.10 [0.42,24.08]
53 |  11.37 [7.87,14.48] |  12.33 [8.25,15.90] |  11.49 [6.84,14.72] |  11.49 [6.84,14.72] |  9.09 [4.01,13.58] |  11.52 [7.22,14.76] |  9.41 [0.44,25.15]
54 |  7.87 [4.12,11.95] |  8.99 [5.46,12.08] |  6.96 [2.77,11.02] |  6.96 [2.77,11.02] |  6.61 [2.36,10.83] |  6.70 [2.92,11.71] |  7.79 [0.34,20.88]
55 |  10.33 [7.32,13.27] |  9.07 [5.86,12.36] |  8.97 [6.04,12.37] |  8.98 [6.04,12.37] |  6.76 [3.82,10.27] |  9.84 [6.73,13.32] |  7.80 [0.32,21.06]
56 |  7.35 [3.62,11.03] |  5.84 [2.05,9.60] |  7.65 [3.30,11.25] |  7.65 [3.30,11.25] |  6.93 [2.01,11.56] |  7.23 [3.62,10.80] |  7.54 [0.35,20.22]
57 |  6.28 [2.15,10.44] |  5.99 [2.45,9.47] |  5.52 [1.49,8.42] |  5.52 [1.49,8.42] |  4.66 [0.53,8.73] |  5.74 [1.67,8.86] |  7.15 [0.34,19.90]
58 |  8.74 [5.82,11.51] |  8.65 [5.43,11.51] |  7.89 [5.30,11.21] |  7.89 [5.30,11.21] |  7.66 [3.36,11.34] |  8.44 [5.52,10.82] |  7.59 [0.39,21.15]
59 |  6.75 [2.75,10.42] |  5.74 [2.62,9.07] |  6.02 [2.36,10.51] |  6.02 [2.36,10.51] |  5.49 [1.19,10.60] |  6.39 [2.84,10.59] |  7.86 [0.33,21.16]
60 |  6.29 [3.46,9.21] |  6.98 [2.92,10.71] |  6.42 [3.17,8.96] |  6.42 [3.17,8.96] |  6.49 [1.91,10.54] |  5.94 [3.17,9.54] |  6.80 [0.20,19.85]
61 |  9.03 [5.57,11.52] |  8.53 [5.45,11.93] |  7.74 [4.75,10.16] |  7.74 [4.75,10.16] |  6.49 [2.83,10.04] |  7.84 [5.41,11.40] |  7.12 [0.29,20.17]
62 |  6.69 [2.66,10.44] |  6.78 [2.82,11.66] |  7.63 [3.91,10.89] |  7.63 [3.91,10.89] |  5.84 [1.53,10.81] |  7.17 [3.27,11.01] |  7.33 [0.34,20.45]
63 |  5.12 [1.94,8.77] |  6.57 [3.17,9.25] |  5.13 [2.46,8.30] |  5.13 [2.46,8.30] |  4.09 [0.28,8.06] |  5.33 [1.94,9.80] |  7.18 [0.22,19.68]
64 |  8.85 [5.03,11.29] |  8.85 [5.16,12.07] |  8.78 [4.92,11.88] |  8.78 [4.92,11.88] |  6.39 [2.50,9.73] |  8.45 [5.04,11.80] |  7.24 [0.25,20.36]
65 |  7.55 [4.31,11.04] |  8.98 [6.04,11.92] |  6.64 [3.27,10.19] |  6.64 [3.27,10.19] |  5.64 [1.77,10.23] |  7.09 [3.54,10.54] |  7.04 [0.36,20.32]
66 |  7.36 [4.51,10.04] |  8.54 [5.08,12.46] |  7.06 [4.39,9.85] |  7.06 [4.39,9.85] |  6.58 [3.45,9.28] |  7.37 [4.13,9.62] |  7.10 [0.23,20.07]
67 |  5.84 [3.21,8.02] |  7.41 [4.70,9.93] |  5.65 [2.50,8.10] |  5.65 [2.50,8.10] |  4.93 [0.82,8.99] |  6.05 [2.76,8.51] |  6.74 [0.21,18.22]
68 |  6.57 [4.45,9.49] |  7.78 [4.23,11.18] |  5.53 [2.50,9.26] |  5.53 [2.50,9.26] |  4.16 [0.26,7.87] |  6.67 [4.01,9.49] |  6.71 [0.34,17.90]
69 |  7.35 [4.20,11.56] |  8.53 [4.71,11.67] |  7.54 [4.78,10.62] |  7.54 [4.78,10.62] |  6.47 [2.50,10.47] |  7.61 [4.82,10.88] |  6.89 [0.21,19.35]
70 |  6.44 [3.50,9.61] |  4.59 [0.93,7.79] |  7.36 [3.46,10.64] |  7.36 [3.46,10.64] |  6.77 [3.00,10.39] |  6.90 [3.61,11.22] |  7.28 [0.30,19.11]
71 |  7.16 [4.26,9.86] |  4.10 [1.34,6.59] |  7.00 [4.08,10.21] |  7.00 [4.08,10.21] |  6.03 [2.46,9.23] |  6.97 [4.23,10.18] |  6.77 [0.24,18.51]
72 |  5.29 [2.40,8.65] |  5.18 [2.22,7.68] |  4.37 [1.63,7.22] |  4.37 [1.63,7.22] |  4.38 [0.76,8.12] |  5.28 [2.05,8.58] |  6.42 [0.29,17.73]
73 |  7.11 [3.59,10.51] |  6.90 [4.04,10.27] |  7.11 [3.84,10.27] |  7.11 [3.84,10.27] |  5.67 [1.16,9.11] |  7.16 [3.83,10.27] |  6.81 [0.26,19.34]
74 |  5.74 [3.01,9.05] |  6.79 [3.55,8.99] |  5.66 [2.50,8.24] |  5.66 [2.50,8.24] |  7.05 [2.94,10.41] |  5.66 [2.73,8.86] |  6.80 [0.29,19.09]
75 |  5.25 [2.23,8.20] |  5.62 [2.93,8.17] |  4.63 [1.00,7.94] |  4.63 [1.00,7.94] |  4.77 [1.00,7.23] |  5.66 [1.73,8.43] |  6.23 [0.25,17.98]
76 |  5.87 [2.47,9.18] |  6.25 [3.45,8.95] |  4.79 [1.87,8.16] |  4.80 [1.87,8.16] |  3.50 [0.99,7.17] |  5.88 [2.70,8.98] |  6.12 [0.22,17.48]
77 |  4.10 [0.32,7.24] |  4.67 [1.46,7.92] |  1.92 [0.10,5.07] |  1.92 [0.10,5.07] |  1.86 [0.00,4.74] |  4.12 [0.97,6.63] |  6.00 [0.19,17.90]