# Taming the Sigmoid Bottleneck:
Provably Argmaxable Sparse Multi-Label Classification

Andreas Grivas1, Antonio Vergari$\dagger$2, Adam Lopez$\dagger$1

###### Abstract

Sigmoid output layers are widely used in multi-label classification (MLC)
tasks, in which multiple labels can be assigned to any input. In many
practical MLC tasks, the number of possible labels is in the thousands, often
exceeding the number of input features and resulting in a _low-rank_ output
layer. In multi-class classification, it is known that such a low-rank output
layer is a bottleneck that can result in _unargmaxable_ classes: classes which
cannot be predicted for any input. In this paper, we show that for MLC tasks,
the analogous _sigmoid bottleneck_ results in exponentially many unargmaxable
label combinations. We explain how to detect these unargmaxable outputs and
demonstrate their presence in three widely used MLC datasets. We then show
that they can be prevented in practice by introducing a Discrete Fourier
Transform (DFT) output layer, which guarantees that all sparse label
combinations with up to $k$ active labels are argmaxable. Our DFT layer trains
faster and is more parameter efficient, matching the F1@k score of a sigmoid
layer while using up to $50\%$ fewer trainable parameters. Our code is
publicly available at https://github.com/andreasgrv/sigmoid-bottleneck.

††$\dagger$ Joint supervision.

##  1 Introduction

Sigmoid classifiers for Multi-Label Classification (MLC) are simple to
implement: just append a linear layer with sigmoid activations to your neural
feature encoder of choice. They are widely used in neural MLC with thousands
of output labels; applications include clinical coding (Mullenbach et al.
2018), image classification (Baruch et al. 2020), fine-grained entity typing
(Choi et al. 2018) and protein function prediction (Kulmanov and Hoehndorf
2019). Moreover, they are the default for MLC in frameworks such as Scikit-
learn (Pedregosa et al. 2011) and Keras (Paul and Rakshit 2014). In this paper
we highlight an overlooked weakness of this layer. If, as is common for
computational efficiency, we make the number of features smaller than the
number of labels, the result is a Bottlenecked Sigmoid Layer (BSL), in which
_exponentially many label combinations cannot be predicted irrespective of
input_. We say that such label combinations are unargmaxable (Grivas,
Bogoychev, and Lopez 2022). Fig. 1(a) illustrates how a BSL can give rise to
unargmaxability even in low dimensions, with only two features and three
labels.

clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$

(a) Unargmaxability:

clr1$\bm{\svsign}$clr0$\bm{\svsign}$

and

clr1$\bm{\svsign}$clr0$\bm{\svsign}$

cannot be predicted.

038.9: Unspecified septicemia 200.80: Other named variants of lymphosarcoma
and reticulo… 285.9: Anemia, unspecified 487.1: Influenza with other
respiratory manifestations 682.9: Cellulitis and abscess of unspecified sites
782.1: Rash and other nonspecific skin eruption 995.91: Sepsis 480.9: Viral
pneumonia, unspecified $\vdots$
ClinicalDocument$\bm{+}$$\bm{+}$$\bm{+}$$\bm{+}$$\bm{+}$$\bm{+}$$\bm{+}$$\bm{-}$$\bm{-}$
(b) Unargmaxable test example from MIMIC-III for BSL with
$d=50$.22footnotemark: 2

Figure 1:  Problem: When we have more labels ($n$) than features ($d$), some
label combinations are unargmaxable, i.e. impossible to predict. Left: in a
$d=2$ feature space with $n=3$ classification hyperplanes through the origin,
only 6 out of 8 label combinations can be predicted.444The hyperplanes will
not meet at the origin if the BSL includes a bias term, but this is
mathematically equivalent to adding a single (fixed) input feature: the
problem persists. Right: in the MIMIC-III clinical coding dataset with
$n=8921$ and $d=50$, a classifier is unable to correctly predict the $7$
depicted ICD-9 code labels as active $(+)$ and the remaining labels as
inactive $(-)$.

But unargmaxable label combinations are only a problem if our application
requires those combinations. As we show in this paper, they often do. For
example, in the safety-critical application of clinical coding (see Section
5), unargmaxability can make it impossible to label a report with a specific
combination of findings, as illustrated with a real example in Footnote 2.
This would be surprising and unacceptable to users of the system when such
label combinations do indeed occur in data. Since BSLs are widely used, it is
critical for developers and users of a model to be aware of this problem and
to be able to guarantee that all meaningful outputs for a task are argmaxable.

Previous work has shown that bottlenecked output layers have restrictions on
expressivity, but focused only on multi-class classification (Yang et al.
2018; Ganea et al. 2019) and not MLC. But for multi-class classification, the
consequences are minor: classes can be unargmaxable in theory (Demeter,
Kimmel, and Downey 2020) but rarely are in practice (Grivas, Bogoychev, and
Lopez 2022). In MLC, we will show that exponentially many label combinations
are unargmaxable, and as we have already seen in Footnote 2, meaningful
outputs can be unargmaxable. While a BSL can in principle learn to represent
any particular output, it comes with no guarantees. And although we can obtain
post hoc guarantees by verifying whether specific meaningful outputs are
argmaxable, there may be too many outputs to check exhaustively. To sidestep
this limitation, we show how to construct an output layer that guarantees that
meaningful outputs are argmaxable by construction. To do so, we provide
guarantees for a superset of outputs: those with up to $k$ active labels,
where we choose $k$ based on the statistics of the dataset. This is possible
since for most MLC tasks $k$ is bounded (Jain et al. 2019), either empirically
(e.g. $k$=80 for MIMIC-III) or by construction (e.g. $k$=50 for BioASQ
(Tsatsaronis et al. 2015)).

In summary, our contributions are: i) We formalize the argmaxability problem
for MLC and expose the limitations of BSLs which are widely used in practice
(Section 2); ii) We provide ways of verifying if a label combination is
argmaxable for a model (Section 3) and show that for three widely used MLC
datasets BSLs can have unargmaxable test set label combinations (Section 5).
iii) We prove that this need not be the case; we can guarantee that any output
with up to $k$ active labels is argmaxable by constraining the output layer
parametrisation to a family of matrices. The Discrete Fourier Transform (DFT)
matrix is in this family and we use it to parametrise our DFT layer, an
efficient replacement output layer with such guarantees (Section 4). iv)
Through experiments on three MLC datasets we show that our DFT layer
guarantees that meaningful outputs are argmaxable while converging faster and
being more parameter efficient than a BSL (Section 5).

##  2 Multi-label Classification

We consider a MLC model that predicts a complete label assignment
$\mathbf{y}\in\\{+,-\\}^{n}$ for a label vocabulary of size $n$, and where
each $\mathbf{y}_{i}\in\\{+,-\\}$ denotes if a single label is active (+) or
inactive (-). Many neural MLC models for problems with large label
vocabularies employ an output layer that is linear, e.g., for fine-grained
entity typing (Choi et al. 2018), protein function prediction (Kulmanov and
Hoehndorf 2019), clinical coding (Mullenbach et al. 2018) and multi-label
image classification (Baruch et al. 2020).

##### Bottlenecked Sigmoid Layers.

A linear sigmoid layer takes as input a feature vector
$\mathbf{x}\in\mathbb{R}^{d}$ and predicts $\mathbf{y}$ by assuming that all
labels are independent given $\mathbf{x}$. The idea is that a powerful encoder
does the “heavy lifting” and projects inputs to meaningul embeddings in
$\mathbb{R}^{d}$ such that they can be easily separated by $n$ different
hyperplanes. When $n$ is large, due to computational constraints it is popular
to realize such a layer as a Bottlenecked Sigmoid Layer (BSL) which is
parametrized by a low-rank $\mathbf{W}\in\mathbb{R}^{n\times d}$ and
associates with each label the probability
$P(\mathbf{y}_{i}\mid\mathbf{x})=\operatorname{\sigma}\left(\mathbf{w}_{i}^{\top}\mathbf{x}\right)$
if $\mathbf{y}_{i}=+$ and
$1-\operatorname{\sigma}\left(\mathbf{w}_{i}^{\top}\mathbf{x}\right)$
otherwise. Here, $\sigma$ is the logistic sigmoid and $\mathbf{w}_{i}$ is the
weight vector of the $i$-th classifier (hyperplane), i.e., the $i^{th}$ row of
$\mathbf{W}$. Note that all $\mathbf{w}_{i}$ see the same shared $\mathbf{x}$.
We focus on such a setup and discuss its limitations because it is the default
in mainstream ML libraries such as scikit-learn (Pedregosa et al. 2011) and
largely used as a simple classifier (Mullenbach et al. 2018; Baruch et al.
2020; Kulmanov and Hoehndorf 2019). In the following, we will denote a whole
multi-label classifier by the parametrization of its last layer, e.g., by
saying “a classifier $\mathbf{W}$”, as our analysis is agnostic to the feature
encoder.

##### Argmaxable Label Assignments.

Making a prediction with a BSL boils down to predicting every label
independently by computing
$\mathbf{y}^{*}_{i}=\,\arg\\!\max\,_{\mathbf{y}_{i}}P(\mathbf{y}_{i}\mid\mathbf{x})$.
This is equivalent to taking the sign of the logits of the $i$-th classifier,
i.e., computing
$\mathbf{y}_{i}^{*}=\operatorname{sign}{\left(\mathbf{w}_{i}^{\top}\mathbf{x}\right)}$
where $\operatorname{sign}{\left(\mathbf{z}_{i}\right)}=+$ if
$\mathbf{z}_{i}>0$ and $-$ if $\mathbf{z}_{i}<0$. Therefore,
$\mathbf{y}^{*}=\operatorname{sign}{\left(\mathbf{W}\mathbf{x}\right)}.$

######  Definition 1.

A label assignment $\mathbf{y}$ is argmaxable for a classifier $\mathbf{W}$ if
there exists an input $\mathbf{x}$ for which thresholding the output
probabilities using the argmax decision rule
$\operatorname{sign}{\left(P(\mathbf{y}_{i}=+\mid\mathbf{x})-\frac{1}{2}\right)}$
produces $\mathbf{y}_{i}$.555Due to monotonicity of sigmoid
$\operatorname{\sigma}\left(a\right)>\frac{1}{2}\iff a>0$., i.e.,
$\mathbf{y}\,\text{is
argmaxable}\iff\exists\mathbf{x}:\operatorname{sign}{\left(\mathbf{W}\mathbf{x}\right)}=\mathbf{y}$.

From a geometric perspective, we can interpret the $n$ rows of $\mathbf{W}$ as
the normal vectors, $\mathbf{w}_{i}$, of $n$ hyperplanes that tesselate
feature space into regions. We can identify each region by assigning it a sign
vector which identifies on which side of each hyperplane it is (Footnote 4,
left). Under this view, a label assignment $\mathbf{y}$ is argmaxable if the
halfspaces intersect in such a way that the corresponding region is formed.
For example, the region clr1$\bm{\svsign}$clr0$\bm{\svsign}$ is formed as an
intersection of the negative halfspaces. For a classifier parameterized by a
full rank $\mathbf{W}\in\mathbb{R}^{n\times n}$, all $2^{n}$ label
combinations are argmaxable. However, since $d\ll n$ in many real-world
applications, as discussed in Section 1, $\mathbf{W}$ will be low rank, and
therefore only a (small) subset of label combinations is argmaxable.

Figure 2: The number of argmaxable label configurations shrinks exponentially
as $d\ll n$. We plot the percentage of the $2^{1000}$ label combinations that
are argmaxable for a BSL with $n=1000$ labels as we vary the feature
dimensionality $d$. For $d\ll n$ there is a fast dip when $d<500$ (see left
side).

###  2.1 Hyperplane Overcrowding

For a low-rank classifier $\mathbf{W}\in\mathbb{R}^{n\times d}$ and $d\ll n$,
we have a large number of hyperplanes finely slicing a lower dimensional
feature space. The natural question is, out of the $2^{n}$ label combinations
$\mathbf{y}$, how many can such a classifier actually represent? To elaborate
on this, let us define the set of argmaxable label combinations for a
classifier $\mathbf{W}$ as:

$\mathcal{A}\left(\mathbf{W}\right)=\\{\operatorname{sign}{\left(\mathbf{W}\mathbf{x}\right)}\quad\forall\mathbf{x}\in\mathbb{R}^{d}\\}$
(1)

We can exactly count the number of argmaxable label combinations, i.e.
$\left|\mathcal{A}\left(\mathbf{W}\right)\right|$ if $\mathbf{W}$ is in
general position.

######  Definition 2.

$\mathbf{W}\in\mathbb{R}^{n\times d}$ is in general position if no subset of
$d$ rows is linearly dependent. See Appendix 9.

######  Theorem 1.

(Cover 1965, Thm 2) If $\mathbf{W}$ is in general position, the number of
argmaxable label combinations is:

$\left|\mathcal{A}\left(\mathbf{W}\right)\right|=2\sum\nolimits_{d^{\prime}=0}^{d-1}\binom{n-1}{d^{\prime}}.$
(2)

It follows that i) the number of argmaxable label combinations depends only on
$n$ and $d$, not the specific $\mathbf{W}$, and ii) most label combinations
will be unargmaxable for $d\ll n$ as Eq. 2 indicates an exponential growth
(see Fig. 2).

While we can count the number of (un)argmaxable label combinations, it remains
an open problem to verify if a specific set of label combinations can ever be
predicted by a given classifier. We provide a solution in the next section.

##  3 Verifying Argmaxable Label Assignments

Given a low-rank classifier $\mathbf{W}$, we are interested in verifying if a
set of $L$ label combinations of interest $\\{\mathbf{y}^{(j)}\\}_{j=1}^{L}$
is (un)argmaxable. These labels can belong to a held out set, as in our
experiments (Section 5), and help quantify the generalizability and
trustworthiness of the given classifier, as we would expect it to be able to
predict all $L$ outputs.

A simple strategy is to verify the argmaxability of each $\mathbf{y}^{(j)}$.
For that, we use a Chebyshev Linear Programme (LP), which also gives us a
proxy for the size of a region, as we explain next. The LP aims to find the
Chebyshev center (Boyd and Vandenberghe 2004, p. 417) of the region encoded by
$\mathbf{y}^{(j)}$: the center of the largest ball of radius $\epsilon$ that
can be embedded within it (see Fig. 3). As a constrained optimization problem,
we want to solve:

maximise $\displaystyle\epsilon$ (3) subject to
$\displaystyle\mathbf{w}_{i}^{\top}\mathbf{x}+\epsilon\|\mathbf{w}_{i}\|_{2}\leq
0,\quad 1\leq i\leq n,$ $\displaystyle-10^{4}\leq\mathbf{x}_{j}\leq
10^{4},\quad 1\leq j\leq d,\quad\epsilon>\text{eps}$

where we constrain each entry of $\mathbf{x}$ in a bounded region, since the
Chebyshev center is not defined otherwise. If the LP is feasible it returns
the maximum radius $\epsilon$ and we verify that $\mathbf{y}$ is argmaxable.
Note that we add an additional constraint, $\epsilon>\text{eps}$, where eps is
the numerical accuracy that an LP solver can operate with.666We use Gurobi
Optimization (2021) which has eps=$10^{-8}$. This tells us that while
argmaxability can be defined in absolute terms, in practice it can only be
verified up to some numerical precision: $\mathbf{y}$ can be argmaxable as per
Section 2, but an LP might not be able to detect it if there is only a tiny
neighbourhood around a certain embedding $\mathbf{x}$. As such, we define
$\epsilon$-argmaxability to characterise robustly argmaxable label
combinations.

clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$

Figure 3: Our example from Figure 4 with n=3 and d=2. We include the balls
found by the Chebyshev LP for each argmaxable label combination. When we have
a narrow sigmoid bottleneck, most balls will have a tiny radius.

######  Definition 3.

A label assignment $\mathbf{y}$ is $\bm{\epsilon}$-argmaxable for a classifier
$\mathbf{W}$ if it is argmaxable even under the presence of a noise vector
$\bm{\delta}$ having magnitude
$\left\lVert\bm{\delta}\right\rVert_{2}\leq\epsilon$:

$\mathbf{y}\,\text{is
$\epsilon$-argmaxable}\iff\exists\mathbf{x}:\operatorname{sign}{\left(\mathbf{W}\left(\mathbf{x}+\mathbf{\bm{\delta}}\right)\right)}=\mathbf{y}.$

Our Chebyshev LP is able to verify $\epsilon$-argmaxability and therefore
argmaxability, as the first implies the second. Note, however, that the
reverse is not true. While verifying that a classifier is able to argmax a
certain set of labels is of extreme importance, verification can be
computationally expensive, as LPs become intractable as we scale $n$, $d$ and
$L$. To avoid this, we devise a classifier that guarantees that all labels of
interest are argmaxable by design.

##  4 DFT Layers for $k$-Active MLC

Designing a low-rank BSL that guarantees argmaxability for all $2^{n}$
possible label combinations is impossible, according to Theorem 1. However,
for most MLC datasets the label combinations are sparse; only a handful of
labels are active for any given example. As such, herein we choose an upper
bound $k$ on the number of active labels for each dataset and show how to
modify the parametrisation of a BSL so that any $k$-active label assignment is
guaranteed to be argmaxable. We first define sufficient criteria by specifying
a _broad family of parametrisations_ for which our result holds: the weight
matrix should have at least $2k+1$ input features and all its maximal minors
should be non-zero and have the same sign. Next, we specify an implementation
satisfying these criteria, the Discrete Fourier Transform (DFT) layer, which
is computationally appealing and is accurate in practice.

Figure 4: Visual evidence of Theorem 3. a) We construct a BSL having $n=4$
labels and $d=2$ features parametrised by $\mathbf{W}\in\mathbb{R}^{4\times
2}$ such that all maximal minors are positive, i.e.
$\mathbf{W}\in{Gr}^{+}_{n=4,d=2}$. (b) The rows of the matrix are binary
classifiers, we demarcate the decision boundaries for each classifier using a
dashed line. (c) We assign each region a sign vector corresponding to which
labels the BSL would flag as active for an input falling in that region. As
per Theorem 3, exactly the $(d-1)=1$-alternating outputs are argmaxable. More
generally, for $d=2k+1$, all $k$-active outputs are argmaxable (see Appendix
K).

$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$${{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1.0}}$${{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}0.0}}$${{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}0.5}}$${{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}0.7}}$${{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}0.0}}$${{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}1.0}}$${{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}-0.5}}$${{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}0.5}}$$\left[\vbox{\hrule
height=29.75389pt,depth=29.75389pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=29.75389pt,depth=29.75389pt,width=0.0pt}\right]$$\mathbf{W}=$ (a) All
$\binom{4}{2}=6$ maximal minors, $\Delta_{I}$, are positive, hence
$\mathbf{W}\in{Gr}^{+}_{4,2}$.

$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\mathbf{w}_{1}$$\mathbf{w}_{2}$$\mathbf{w}_{3}$$\mathbf{w}_{4}$
(b) Correspondence of $\mathbf{W}$ and geometric picture: each normal vector
is a row of $\mathbf{W}$.

$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$clr1$\bm{\svsign}$clr0$\bm{\svsign}$
(c) The Argmaxable label assignments are the 1-alternating vectors,
$\mathcal{A}\left(\mathbf{W}\right)={V}_{4,1}$.

###  4.1 $k$-Active Label Assignments

Label combinations in real-world MLC datasets are often sparse (Babbar and
Schölkopf 2019); it is unlikely an image will contain more than $k$ objects or
that a clinical document will be assigned more than $k$ clinical codes, where
$k\approx\mathcal{O}(\log n)$ is a dataset dependent upper bound on the number
of active labels. We now show how to guarantee that all $k$-active outputs are
argmaxable by controlling the parametrisation of a BSL. We first formalize
what a $k$-active label combination is below.

######  Definition 4.

For a label assignment $\mathbf{y}$ we define
$\operatorname{act}{\left(\mathbf{y}\right)}$ to be the number of active
labels in $\mathbf{y}$, i.e:

$\operatorname{act}{\left(\mathbf{y}\right)}=\sum\nolimits_{i=1}^{n}\mathbf{1}_{\mathbf{y}}\left\\{\mathbf{y}_{i}=+\right\\},\quad
i\in[n]$ (4)

e.g. $\operatorname{act}{\left(-----\right)}=0$ and
$\operatorname{act}{\left(+--+-\right)}=2$.

######  Definition 5.

The set of $k$-active label combinations on $n$ labels is:

${A}_{n,k}=\left\\{\mathbf{y}:\operatorname{act}{\left(\mathbf{y}\right)}\leq
k\right\\}$ (5)

For example, the MIMIC-III dataset (Johnson et al. 2016; Mullenbach et al.
2018) has $n=8921$ labels, but no example has more than $80$ active labels.
Next we show how to guarantee that all labels in ${A}_{8921,80}$ are
argmaxable.

###  4.2 $k$-Active Argmaxability Guarantees

Our goal in this section is to prove Theorem 4, which states that a general
criterion for guaranteeing all $k$-active labels are argmaxable is that the
weight matrix $\mathbf{W}\in\mathbb{R}^{n\times d},\,d\geq 2k+1$ that
parametrises the BSL has _maximal minors that agree in sign and are non-zero_.
As such, we next introduce maximal minors and the family of matrices with the
above property. We prove our result by showing that the argmaxable label
assignments for this family of matrices are “$2k$-alternating” and that these
subsume the $k$-active ones.

A maximal minor $\Delta_{I}$ of a $n\times d$ matrix, $n>d$, is the
determinant of any $d\times d$ submatrix formed by selecting any $d$ rows
(indexed by $I$), without permuting them. For example, in Fig. 4(a), all
maximal minors are positive. We denote with ${Gr}^{+}_{n,d}$ the set of all
matrices $\mathbf{W}\in\mathbb{R}^{n\times d}$ whose maximal minors are non-
zero and have the same sign (see Appendix C). To prove Theorem 4, we build on
facts known about $k$-alternating outputs, which we introduce below.

######  Definition 6.

For a label assignment $\mathbf{y}$ we define
$\operatorname{alt}{\left(\mathbf{y}\right)}$ to be the number of sign changes
encountered when reading the sequence of labels from left to right, i.e:

$\operatorname{alt}{\left(\mathbf{y}\right)}=\sum_{i=1}^{n}\mathbf{1}_{\mathbf{y}}\\{\mathbf{y}_{i}\neq\mathbf{y}_{i+1}\\},\quad
i\in[n-1]$ (6)

e.g: $\operatorname{alt}{\left(++---\right)}=1$ and
$\operatorname{alt}{\left(++-+-\right)}=3$.

######  Definition 7.

The set of $k$-alternating label assignments is:

${V}_{n,k}=\left\\{\mathbf{y}:\operatorname{alt}{\left(\mathbf{y}\right)}\leq
k\right\\}$ (7)

######  Lemma 1.

$\mathbf{y}$ is $k$-active $\implies\mathbf{y}$ is at most $2k$-alternating.

See Section D.1 for reasoning.

######  Theorem 2.

(Gantmakher and Kreĭn 1961) see (Karp 2017, Theorem 1.1). If all maximal
minors of $\mathbf{W}\in\mathbb{R}^{n\times d}$ are non-zero and have the same
sign, all label assignments $\mathbf{y}$ computed as
$\mathbf{y}=\operatorname{sign}{\left(\mathbf{Wx}\right)},\,\mathbf{x}\in\mathbb{R}^{d}$
are at most $d-1$ alternating.
$\mathbf{W}\in{Gr}^{+}_{n,d}\implies\operatorname{alt}{\left(\mathbf{y}\right)}\leq
d-1$ .

######  Theorem 3.

For $\mathbf{W}\in{Gr}^{+}_{n,d}$ the argmaxable label assignments are exactly
the $(d-1)$-alternating vectors.
$\mathbf{W}\in{Gr}^{+}_{n,d}\implies\mathcal{A}\left(\mathbf{W}\right)={V}_{n,d-1}$.

See Section D.2 for a proof and Fig. 4(c) for intuition.

######  Theorem 4.

Consider a BSL parametrised by $\mathbf{W}\in{Gr}^{+}_{n,2k+1}$ which predicts
label assignments using argmax prediction,
$\mathbf{y}=\operatorname{sign}{\left(\mathbf{Wx}\right)}$. All $k$-active
label assignments are argmaxable:
${A}_{n,k}\subset\mathcal{A}\left(\mathbf{W}\right)$.

###### Proof.

From Theorem 3, for $\mathbf{W}$ in ${Gr}^{+}_{n,2k+1}$ the set of
$2k$-alternating label assignments ${V}_{n,2k}$ is argmaxable. Then, from
Lemma 1, we have
${A}_{n,k}\subseteq{V}_{n,2k}=\mathcal{A}\left(\mathbf{W}\right)$, and
therefore all $k$-active labels are argmaxable. ∎

In summary, we showed that if $\mathbf{W}\in{Gr}^{+}_{n,2k+1}$, all $k$-active
outputs are argmaxable, but we have not given a concrete implementation. We
next introduce the DFT layer, a practical and efficient member of the
${Gr}^{+}_{n,2k+1}$ family.

###  4.3 DFT Layers

Herein we engineer a specific BSL parametrisation that satisfies Theorem 4 and
relies on the Discrete Fourier Transform (DFT). In addition to this property,
the DFT is appealing also because: a) it allows to reduce the number of
learnable parameters as the DFT coefficients can be fixed 777In early
experiments we parametrised and learned the $t_{i}$ of the DFT matrix but
found little impact on the results.  and b) we can compute the activation of
the DFT Layer in $\mathcal{O}(n\log{n})$ time via the Fast Fourier Transform
(see Appendix E) instead of a more expensive $\mathcal{O}(n^{2})$ generic
matrix-vector product. We next describe a truncated DFT matrix and show that
it provides the guarantees we seek. For the DFT matrix, we truncate
frequencies larger than $k$:

$\displaystyle\bm{W}^{\mathsf{DFT}}_{n,2k+1}=$
$\displaystyle\begin{bmatrix}\frac{1}{\sqrt{n}}&\sqrt{\frac{2}{n}}\cos{t_{1}}&\sqrt{\frac{2}{n}}\sin{t_{1}}&\cdots&\sqrt{\frac{2}{n}}\cos{kt_{1}}&\sqrt{\frac{2}{n}}\sin{kt_{n}}\\\
\frac{1}{\sqrt{n}}&\sqrt{\frac{2}{n}}\cos{t_{2}}&\sqrt{\frac{2}{n}}\sin{t_{2}}&\cdots&\sqrt{\frac{2}{n}}\cos{kt_{2}}&\sqrt{\frac{2}{n}}\sin{kt_{n}}\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
\frac{1}{\sqrt{n}}&\sqrt{\frac{2}{n}}\cos{t_{n}}&\sqrt{\frac{2}{n}}\sin{t_{n}}&\cdots&\sqrt{\frac{2}{n}}\cos{kt_{n}}&\sqrt{\frac{2}{n}}\sin{kt_{n}}\\\
\end{bmatrix},$ $\displaystyle t_{i}=\frac{2\pi(i-1)}{n},\,i\in[n]$ (8)

######  Lemma 2.

A truncated DFT matrix $\bm{W}^{\mathsf{DFT}}_{n,2k+1}\in{Gr}^{+}_{n,2k+1}$.

We need to show that the maximal minors of $\bm{W}^{\mathsf{DFT}}_{n,2k+1}$
are non-zero and agree in sign. See Section D.3 for a proof.

##### Problem: Regions can become too small.

While in practice we could use the fixed DFT Layer as defined above and rely
on an expressive feature encoder to do the heavy lifting, if the number of
labels $n$ is much greater than the number of features $2k+1$, it becomes hard
to classify some label assignments with large confidence. This is because
segmenting a low dimensional space with very many hyperplanes induces regions
that become arbitrarily small shards. In argmaxability terms, if we fix an
$\epsilon$ and increase the number of labels, all $k$-active labels are
argmaxable but increasingly more are not $\epsilon$-argmaxable, see left in
Fig. 5. This is a problem for any classifier $\mathbf{W}$, because for
training and for generalisation we need to project points into large enough
regions. However, we found that DFT layers are more susceptible to it (Section
F.2) than general BSL (see Appendix I for a more rigorous explanation).

##### Solution: Slack variables.

A practical way to deal with small regions is to increase the dimensionality
of the feature vectors, by adding slack variables, see bottom of Fig. 5.
Importantly, as we show next in Lemma 3, we can do so while retaining our
guarantees.

Figure 5: Left: As we increase the number of labels $n$ for the DFT Layer, the
radii of the regions shrink, making them harder to predict in practice. Right:
Adding slack variables ameliorates this problem. We plot
$\epsilon$-argmaxability (Definition 3), measured here for the 1% of labels
that have radius less than that plotted. For the DFT Layer, i.e.
$\mathbf{W}=\bm{W}^{\mathsf{DFT}}_{n,2k+1}$, all $k$-active label assignments
are argmaxable, but as we increase $n$, some (see $k\geq 3$) cannot be
detected at the precision of the LP ($10^{-8}$). Adding 16 randomly
initialised slack columns, i.e.
$\mathbf{W}=\begin{bmatrix}\bm{W}^{\mathsf{DFT}}_{n,2k+1}\,\,\mathbf{S}\end{bmatrix}$,
makes the regions $\epsilon$-argmaxable with larger $\epsilon$.

######  Lemma 3.

Assume a label $\mathbf{y}$ is argmaxable for a classifier
$\mathbf{W}\in\mathbb{R}^{n\times d}$. Consider increasing the dimensionality
of the features of the classifier $\mathbf{W}$ by adding $s$ more randomly
initialised slack columns $\mathbf{S}\in\mathbb{R}^{n\times s}$. The label
$\mathbf{y}$ is also argmaxable in
$\mathbf{W}^{\prime}=\begin{bmatrix}\mathbf{W}\,\,\mathbf{S}\end{bmatrix},\,\mathbf{W}^{\prime}\in\mathbb{R}^{n\times(d+s)}$.

###### Proof.

Consider the input feature vector for $\mathbf{W}^{\prime}$,
$\mathbf{x}^{\prime}=\begin{bmatrix}\mathbf{x}\\\
\mathbf{x}_{s}\end{bmatrix},\,\mathbf{x}\in\mathbb{R}^{d},\,\mathbf{x}_{s}\in\mathbb{R}^{s}$.
Set $\mathbf{x}_{s}=\mathbf{0}$. Then notice that
$\mathbf{y}=\operatorname{sign}{\left(\begin{bmatrix}\mathbf{W}\,\,\mathbf{S}\end{bmatrix}\begin{bmatrix}\mathbf{x}\\\
\mathbf{0}\end{bmatrix}\right)}=\operatorname{sign}{\left(\mathbf{W}\mathbf{x}\right)}$
is equivalent to the original classifier, so if $\mathbf{y}$ is argmaxable in
$\mathbf{W}$ it is also argmaxable in $\mathbf{W}^{\prime}$ by setting
$\mathbf{x}_{s}$ to zero. ∎

As such, we propose the DFT layer, which has $(2k+1)\times n$ fixed parameters
which enforce argmaxability and $s\times n$ learnable parameters which give it
flexibility.

##  5 Experiments

We now empirically evaluate the BSL and DFT layers on three MLC datasets and
answer the following research questions: RQ1) Do BSLs have unargmaxable labels
in practice? RQ2) Can DFT layers guarantee that meaningful labels are
argmaxable in practice? RQ3) What is the trade-off between performance and the
number of trainable parameters? We answer the above after introducing the
models and datasets.

###  5.1 Model Setup

We define the two MLC output layers we will compare, the _BSL Layer_ that is
unconstrained and does not guarantee argmaxability of $k$ active outputs, and
our _DFT layer_ which does. In our experiments we want to study the effect of
varying the bottleneck width, $d$, irrespective of the feature dimensionality
of the encoder which varies across datasets and models. We therefore introduce
an _affine projection layer_ (parametrised by $\mathbf{P}$ and $\mathbf{b}$)
between the feature encoder and the _linear classifier_ (parametrised by
$\mathbf{W}$). For simplicity, we do not include bias terms for the
classifiers. For both models, we compute the logits
$\mathbf{z}\in\mathbb{R}^{n}$ from the encoder activation
$\mathbf{e}\in\mathbb{R}^{e}$ as:

$\quad\mathbf{z}=\mathbf{W}\mathbf{x},\quad\mathbf{x}=\mathbf{P}\mathbf{e}+\mathbf{b}$
(9)

but the parametrisations differ, as we discuss next.

#### BSL Output Layer

For the BSL, the projection layer maps from $e$, the dimensionality of the
encoder embeddings, to $d$, the feature dimensionality using
$\mathbf{P}\in\mathbb{R}^{e\times d}$ and bias $\mathbf{b}\in\mathbb{R}^{d}$.
This is followed by the linear classifier $\mathbf{W}\in\mathbb{R}^{n\times
d}$.

#### DFT Output Layer

For the DFT, we first pick the maximum number of active labels, $k$, depending
on the statistics of the dataset. We then set the number of slack dimensions
to be $d$ so we can directly compare to the BSL.

For the DFT, we have $\mathbf{P}\in\mathbb{R}^{e\times(2k+1+d)}$ and
$\mathbf{b}\in\mathbb{R}^{(2k+1+d)}$ since we include $2k+1$ more features
that map to the DFT columns of the classifier. The learnable parameters of the
classifier comprise $d$ slack columns. Conceptually, and for the purposes of
checking the classifier with our LP, we construct the classifier by
concatenating the fixed DFT matrix to the slack columns, i.e.
$\mathbf{W}=\begin{bmatrix}\bm{W}^{\mathsf{DFT}}_{n,2k+1}\,\,\mathbf{S}\end{bmatrix}$,
$\mathbf{W}\in\mathbb{R}^{n\times(2k+1+d)}$. In practice we compute the logits
$\mathbf{z}$ efficiently as
$\mathbf{z}=\operatorname{FFT}(\mathbf{x}_{:2k+1})+\mathbf{S}\mathbf{x}_{2k+1:}$
(see Appendix E).

##### Initialisation Trick

For the DFT, we can speed up training by exploiting the fact that a) we know
$\mathbf{W}^{\mathsf{DFT}}$ and it is fixed and b) we know that outputs are
$k$-active. The key insight is that due to the outputs being $k$-active, we
would prefer to assign a probability $\frac{k}{n}$ to all labels when we start
training. To achieve this, we can exploit the fact that the first column of
$\mathbf{W}^{\mathsf{DFT}}$ is $\frac{1}{\sqrt{n}}$ and initialise the bias
vector of the projection layer to be
$[\sqrt{n}\operatorname{logit}(\frac{k}{n}),0,\ldots,0]$, where the logit
function is the inverse of sigmoid. This way, assuming logits are close to
zero when we begin training, the model will assign probability approximately
$\frac{k}{n}$ to each label instead of $\frac{1}{2}$. A similar bias
initialisation idea for MLC was discussed in (Schultheis and Babbar 2022), but
it was not used in a neural network.

##### Computational Cost of DFT

Compared to the BSL, the cost of the DFT layer with $n$ labels is a cheap
$\mathcal{O}(n\log{n})$ matrix vector multiplication and an increase in
trainable parameters in the projection layer.

While the DFT has $e\times(2k+1)$ more trainable parameters in the projection
layer than a BSL, as we will see in our results, it can have a much lower
trainable parameter count overall because it is more parameter efficient to
allocate more parameters in the projection layer than the classifier. To
elaborate, the MIMIC-III CNN models (Mullenbach et al. 2018) have $n=8921$ and
$e=500$, which means that the number of trainable parameters grows $9$ times
more if we increase $d$ compared to increasing $k$. More precisely, for
$k=80$, the number of added parameters in the projection layer is $161\times
500$, which we can match by decreasing $d$ in the output layer of a BSL by
only $9$.

###  5.2 MLC Tasks (Datasets)

$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$Argmaxability$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$

(a) Our DFT layer does not suffer from unargmaxable test examples. BSLs cannot
provide any such guarantees.

$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$Parameter
Efficiency$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2}\right\\}}=.7$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=1.$$\Delta_{\left\\{{\color[rgb]{0.89453125,0.1015625,0.109375}\definecolor[named]{pgfstrokecolor}{rgb}{0.89453125,0.1015625,0.109375}1},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3}\right\\}}=.5$$\Delta_{\left\\{{\color[rgb]{0.21484375,0.4921875,0.72265625}\definecolor[named]{pgfstrokecolor}{rgb}{0.21484375,0.4921875,0.72265625}2},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.6$$\Delta_{\left\\{{\color[rgb]{0.30078125,0.6875,0.2890625}\definecolor[named]{pgfstrokecolor}{rgb}{0.30078125,0.6875,0.2890625}3},{\color[rgb]{0.59765625,0.3046875,0.640625}\definecolor[named]{pgfstrokecolor}{rgb}{0.59765625,0.3046875,0.640625}4}\right\\}}=.5$

(b) Our DFT layer is more parameter efficient. F1 is overall better than the
BSL, so we can match BSL’s F1 with fewer trainable parameters (smaller $d$).

Figure 6:  Comparison of BSL and our DFT output layer on three MLC datasets.
We vary, $d$, the number of trainable dimensions and plot the mean and std
(shaded) over 3 runs with different random seeds. Left: We use the LP to
verify the output layers on the test sets. When $d<200$ a large percentage of
label configurations becomes unargmaxable for the BSL, in contrast to our DFT.
Right: Performance in F1@8 or F1@10 (left axis) in terms of the number of
trainable parameters (right axis, dashed lines). Our DFT is better ($d\leq
200$) or comparable to the BSL (MIMIC-III, $d>200$). We can therefore retain a
high F1@k score for DFT even if we reduce the number of trainable parameters
by making the bottleneck narrower. For example, on BioASQ we can surpass the
F1@10 of the BSL that has $d=200$ with a DFT of $d=100$, which has about 50%
fewer trainable parameters.

We next introduce the three datasets and summarise important attributes in
Table 1, see Appendix H for detailed dataset construction and Section H.2 for
more dataset statistics.

Table 1: Setup: Number of labels, $n$, max number of active labels, $k$, and
number of training examples, $N$.

MLC Dataset | n | k | N | encoder | modality
---|---|---|---|---|---
MIMIC-III | $8921$ | 80 | 44k | CNN (e=500) | text
BioASQ task A | $20000$ | 50 | 100k | PubMedBERT (e=768) | text
OpenImagesV6 | $8933$ | 50 | 108k | TResnet (e=2432) | images

#### Clinical Coding (MIMIC-III)

We first test the DFT layer on MIMIC-III (Johnson et al. 2016). For this
safety critical application of clinical coding, the goal is to tag each
clinical note with a set of relevant ICD-9 codes which describe findings (see
Footnote 4). We retrain the CNN encoder model defined in Mullenbach et al.
(2018) which has $n=8921$ and $e=500$. We use the same word embeddings,
preprocessed data, data splits, metrics (Prec@8) and hyperparameters reported
in the paper (Mullenbach et al. 2018), we only change the learning rate of the
Adam optimiser to $0.001$, as this improves results (as also found by Edin et
al. (2023)).

#### Semantic Indexing (BioASQ Task A)

We next turn to MLC on the $2021$ BioASQ semantic indexing challenge
(Tsatsaronis et al. 2015; Nentidis et al. 2021; Krithara et al. 2023). For
this task, we are given PubMed abstracts and asked to predict a set of
relevant MeSH headings 888https://www.nlm.nih.gov/mesh/meshhome.html for each
article. We create dataset splits (see Table 5 for details) which cover
$n=20000$ labels, making sure that all individual labels occur in both the
train and test sets. We do so to avoid claiming a label assignment is
unargmaxable when in fact it would be impossible to predict the labels that
constitute it. We use $k=50$ since this is by construction the maximum number
of active labels per example for this dataset. We finetune PubMedBERT (Gu et
al. 2021), a domain specific uncased BERT (Devlin et al. 2019) encoder that
has $e=768$ and has been pretrained on PubMed abstracts. We use early stopping
with a patience of $10$ on the validation crossentropy loss.

#### Image MLC (OpenImages v6)

We use the OpenImages v6 dataset (Kuznetsova et al. 2020)
999https://storage.googleapis.com/openimages/web/download˙v6.html where the
goal is to tag each image with objects that appear in it. Similar to the
BioASQ case, we choose the label vocabulary $n=8933$ such that all examples in
the train, validation and test set are covered. We pick $k=50$ since the
training data has at most $45$ active labels per example. We finetune the
TResnet (Ridnik et al. 2020) with $e=2432$ that Baruch et al. (2020)
pretrained for MLC on this dataset. We use early stopping with a patience of
$10$ on the validation crossentropy loss.

###  5.3 Results

RQ1) BSL: Unargmaxable outputs We use the LP to verify the BSL on the test
sets. As can be seen in Fig. 6(a), for $d>200$ all the examples in the test
set are argmaxable for the BSL. However, as we reduce $d$, the number of
unargmaxable label assignments increases for all datasets. More specifically,
we first get unargmaxable outputs at $d=200$ for MIMIC-III (see Appendix F).
Analogous considerations can be drawn for BioASQ and OpenImages (Fig. 6(a)).
As such, we conclude that unargmaxability can indeed be an issue when $d$ is
not large enough. Note that one can never determine a $d$ that can always
guarantee all label configurations of interest to be argmaxable: even an
exhaustive verification on all test samples does not imply that future unseen
configurations will be argmaxable. RQ2) DFT: Argmaxability While we know that
the DFT layer guarantees argmaxability in theory, we also see that it works in
practice (apart from a handful of outputs when $d=25$, which are
$\epsilon$-unargmaxable, see Section F.2). Crucially, these guarantees also
apply to unseen $k$-active label assignments; this would be impossible to
enforce with BSLs, as discussed. RQ3) Parameter Efficiency In addition, we
turn to Fig. 6(b), and see that the DFT layer outperforms the BSL layer by a
wide margin for small $d$. This allows us to match the performance of the BSL
using a DFT with smaller $d$ and hence fewer trainable parameters. As can be
seen, in some cases DFT layers obtain better or comparable performance with up
to 50% less trainable parameters. Convergence speed Lastly, DFT layers
converge faster due to the initialisation trick, see Appendix G.

##  6 Related Work

Low-rank Parametrisations in MLC. Low-rank one-vs-all classifiers (Jain et al.
2019) are a common parametrisation in MLC due to their simplicity. Previous
work has highlighted that low-rank parametrisations can be problematic (Bhatia
et al. 2015; Xu, Tao, and Xu 2016; Tagami 2017), but the argument has been
from a matrix factorisation perspective, e.g. that low-rank factorisations
reconstruct the label matrix with high error when there are long-tail labels.
Herein, we highlight a more tangible limitation of low-rank parametrisations
for bottlenecked classifiers: meaningful label assignments can be
unargmaxable. While we prove that we can retain argmaxability with a very low-
rank matrix, we agree that low-rank parametrisations can still be problematic,
since the matrix must be higher rank in order to retain
$\epsilon$-argmaxability which is needed in practice both for training and
prediction.

Graph Embeddings in Euclidean Space. Our work is also connected to whether a
graph can be embedded in Euclidean space. Alon, Moran, and Yehudayoff (2015)
study the rank of sets of sign vectors and whether they can be embedded in $d$
dimensions. In a similar vein to our theoretical results for $k$-active MLC,
Chanpuriya et al. (2020) use a Vandermonde construction to prove the existence
of a factorisable adjacency matrix for any graph of bounded degree $k$.
Vandermonde matrices also satisfy the criteria we presented in Section 4.2,
bridging our more general result with theirs may be an interesting direction.

##  7 Discussion and Conclusion

Through extensive experiments on three multi-label classification datasets we
have shown that bottlenecked multi-label classifiers – which are still
ubiquitous in large MLC scenarios (Mullenbach et al. 2018; Baruch et al. 2020)
– can have unargmaxable label assignments when the label vocabulary is much
larger than the dimensionality of the input features (Section 5). We believe
practitioners should at the very least be aware that selecting the feature
dimension of a BSL is not an innocuous hyperparameter search: by lowering the
rank of the output layer they are potentially making some label assignments
impossible to predict. Unargmaxability impacts the generalization and
trustworthiness of these classifiers since BSLs cannot guarantee that
meaningful label assignments will not be missed at test time or that the
classifiers will not be targetted by adversarial attacks (Zhu et al. 2019;
Aghakhani et al. 2021).

However, we showed that this does _not_ have to be the case. We provided a
family of parametrisations that guarantee that all label assignments having up
to $k$ active labels are argmaxable (Section 4.2) and implemented our DFT
output layer which converges faster than a BSL, is up to 50% more parameter
efficient, and outperforms or matches the BSL on three widely used MLC
datasets. At the same time, our findings prompt several avenues for future
work. For example, it is an open question whether there are more efficient or
more expressive parametrisations that satisfy the criteria we outlined in
Section 4.2. Additionally, as we make the Sigmoid Bottleneck narrower, labels
get assigned to smaller and smaller regions that are harder to predict, and
harder to verify (Section 3). This highlights an important research direction:
parametrise output layers in a way that guarantees $\epsilon$-argmaxability
for large values of $\epsilon$.

## Acknowledgements

We would like to thank Lorenzo Loconte, Rickey Liang, Emile van Krieken and
Marina Potsi for feedback on early drafts. Furthermore, Asif Khan for many
discussions and help connecting the Cyclic Polytope to truncated DFT, Jesse
Sigal for discussions on cyclic permutations, Matúš Falis for discussing
multi-label classification and datasets, Tom Sherbourne for discussing DFT and
low-pass filters and Ivan Titov and Henry Gouk for helpful suggestions and
advice.

AG was supported by the Engineering and Physical Sciences Research Council
(EP/R513209/1). AV was supported by the “UNREAL: Unified Reasoning Layer for
Trustworthy ML” project (EP/Y023838/1) selected by the ERC and funded by UKRI
EPSRC.

## References

  * Aghakhani et al. (2021) Aghakhani, H.; Meng, D.; Wang, Y.-X.; Kruegel, C.; and Vigna, G. 2021.  Bullseye polytope: A scalable clean-label poisoning attack with improved transferability.  In _2021 IEEE European Symposium on Security and Privacy (EuroS &P)_, 159–178. IEEE.
  * Alon, Moran, and Yehudayoff (2015) Alon, N.; Moran, S.; and Yehudayoff, A. 2015.  Sign rank versus VC dimension.  In _Annual Conference Computational Learning Theory_.
  * Babbar and Schölkopf (2019) Babbar, R.; and Schölkopf, B. 2019.  Data scarcity, robustness and extreme multi-label classification.  _Machine Learning_ , 1–23.
  * Baruch et al. (2020) Baruch, E. B.; Ridnik, T.; Zamir, N.; Noy, A.; Friedman, I.; Protter, M.; and Zelnik-Manor, L. 2020.  Asymmetric Loss For Multi-Label Classification.  _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 82–91.
  * Bhatia et al. (2015) Bhatia, K.; Jain, H.; Kar, P.; Varma, M.; and Jain, P. 2015.  Sparse Local Embeddings for Extreme Multi-label Classification.  In Cortes, C.; Lawrence, N.; Lee, D.; Sugiyama, M.; and Garnett, R., eds., _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc.
  * Björner et al. (1999) Björner, A.; Las Vergnas, M.; Sturmfels, B.; White, N.; and Ziegler, G. M. 1999\.  _Oriented Matroids_.  Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2 edition.
  * Boyd and Vandenberghe (2004) Boyd, S. P.; and Vandenberghe, L. 2004.  _Convex optimization_.  Cambridge University Press.
  * Chanpuriya et al. (2020) Chanpuriya, S.; Musco, C.; Sotiropoulos, K.; and Tsourakakis, C. 2020.  Node Embeddings and Exact Low-Rank Representations of Complex Networks.  In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., _Advances in Neural Information Processing Systems_ , volume 33, 13185–13198. Curran Associates, Inc.
  * Choi et al. (2018) Choi, E.; Levy, O.; Choi, Y.; and Zettlemoyer, L. 2018.  Ultra-Fine Entity Typing.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 87–96. Melbourne, Australia: Association for Computational Linguistics.
  * Cordovil and Duchet (2000) Cordovil, R.; and Duchet, P. 2000.  Cyclic Polytopes and Oriented Matroids.  _Eur. J. Comb._ , 21: 49–64.
  * Cover (1965) Cover, T. M. 1965.  Geometrical and Statistical Properties of Systems of Linear Inequalities with Applications in Pattern Recognition.  _IEEE Trans. Electron. Comput._ , 14: 326–334.
  * Demeter, Kimmel, and Downey (2020) Demeter, D.; Kimmel, G.; and Downey, D. 2020.  Stolen Probability: A Structural Weakness of Neural Language Models.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 2191–2197. Online: Association for Computational Linguistics.
  * Devlin et al. (2019) Devlin, J.; Chang, M.-W.; Lee, K.; and Toutanova, K. 2019.  BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , 4171–4186. Minneapolis, Minnesota: Association for Computational Linguistics.
  * Edin et al. (2023) Edin, J.; Junge, A.; Havtorn, J. D.; Borgholt, L.; Maistro, M.; Ruotsalo, T.; and Maaløe, L. 2023.  Automated Medical Coding on MIMIC-III and MIMIC-IV: A Critical Review and Replicability Study.  _Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval_.
  * Gale (1963) Gale, D. 1963.  Neighborly and cyclic polytopes.  In _Proceedings of Symposia in Pure Mathematics_ , volume 7, 225–232.
  * Ganea et al. (2019) Ganea, O.; Gelly, S.; Bécigneul, G.; and Severyn, A. 2019.  Breaking the Softmax Bottleneck via Learnable Monotonic Pointwise Non-linearities.  In _ICML_ , 2073–2082.
  * Gantmakher and Kreĭn (1961) Gantmakher, F.; and Kreĭn, M. 1961.  _Oscillation Matrices and Kernels and Small Vibrations of Mechanical Systems_.  AMS/Chelsea Publication Series. USAEC Office of Technical Information.  ISBN 9780821882412.
  * Grivas, Bogoychev, and Lopez (2022) Grivas, A.; Bogoychev, N.; and Lopez, A. 2022.  Low-Rank Softmax Can Have Unargmaxable Classes in Theory but Rarely in Practice.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 6738–6758. Dublin, Ireland: Association for Computational Linguistics.
  * Gu et al. (2021) Gu, Y.; Tinn, R.; Cheng, H.; Lucas, M.; Usuyama, N.; Liu, X.; Naumann, T.; Gao, J.; and Poon, H. 2021.  Domain-Specific Language Model Pretraining for Biomedical Natural Language Processing.  _ACM Trans. Comput. Healthcare_ , 3(1).
  * Gurobi Optimization (2021) Gurobi Optimization. 2021.  Gurobi Optimizer Reference Manual.
  * Jain et al. (2019) Jain, H.; Balasubramanian, V.; Chunduri, B.; and Varma, M. 2019.  Slice: Scalable Linear Extreme Classifiers Trained on 100 Million Labels for Related Searches.  _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_.
  * Järvelin and Kekäläinen (2002) Järvelin, K.; and Kekäläinen, J. 2002.  Cumulated gain-based evaluation of IR techniques.  _ACM Trans. Inf. Syst._ , 20: 422–446.
  * Johnson et al. (2016) Johnson, A. E. W.; Pollard, T. J.; Shen, L.; Lehman, L.-W. H.; Feng, M.; Ghassemi, M.; Moody, B.; Szolovits, P.; Celi, L. A.; and Mark, R. G. 2016.  MIMIC-III, a freely accessible critical care database.  _Sci. Data_ , 3(1): 160035.
  * Karp (2017) Karp, S. N. 2017.  Sign variation, the Grassmannian, and total positivity.  _Journal of Combinatorial Theory, Series A_ , 145: 308–339.
  * Krithara et al. (2023) Krithara, A.; Mork, J. G.; Nentidis, A.; and Paliouras, G. 2023.  The road from manual to automatic semantic indexing of biomedical literature: a 10 years journey.  _Frontiers in Research Metrics and Analytics_ , 8.
  * Kulmanov and Hoehndorf (2019) Kulmanov, M.; and Hoehndorf, R. 2019.  DeepGOPlus: improved protein function prediction from sequence.  _Bioinformatics_ , 36: 422 – 429.
  * Kuznetsova et al. (2020) Kuznetsova, A.; Rom, H.; Alldrin, N.; Uijlings, J.; Krasin, I.; Pont-Tuset, J.; Kamali, S.; Popov, S.; Malloci, M.; Kolesnikov, A.; Duerig, T.; and Ferrari, V. 2020.  The Open Images Dataset V4: Unified image classification, object detection, and visual relationship detection at scale.  _IJCV_.
  * Mullenbach et al. (2018) Mullenbach, J.; Wiegreffe, S.; Duke, J. D.; Sun, J.; and Eisenstein, J. 2018.  Explainable Prediction of Medical Codes from Clinical Text.  In _NAACL_.
  * Nentidis et al. (2021) Nentidis, A.; Katsimpras, G.; Vandorou, E.; Krithara, A.; and Paliouras, G. 2021\.  Overview of BioASQ Tasks 9a, 9b and Synergy in CLEF2021.  In _Conference and Labs of the Evaluation Forum_.
  * Paul and Rakshit (2014) Paul, S.; and Rakshit, S. 2014.  Large-scale multi-label text classification.  [Online; accessed 15-August-2023].
  * Pedregosa et al. (2011) Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; and Duchesnay, E. 2011.  Scikit-learn: Machine Learning in Python.  _Journal of Machine Learning Research_ , 12: 2825–2830.
  * Postnikov (2006) Postnikov, A. 2006.  Total positivity, Grassmannians, and networks.  _arXiv: Combinatorics_.
  * Ridnik et al. (2020) Ridnik, T.; Lawen, H.; Noy, A.; and Friedman, I. 2020.  TResNet: High Performance GPU-Dedicated Architecture.  _2021 IEEE Winter Conference on Applications of Computer Vision (WACV)_ , 1399–1408.
  * Schultheis and Babbar (2022) Schultheis, E.; and Babbar, R. 2022.  Speeding-up one-versus-all training for extreme classification via mean-separating initialization.  _Machine Learning_ , 111(11): 3953–3976.
  * Tagami (2017) Tagami, Y. 2017.  AnnexML: Approximate Nearest Neighbor Search for Extreme Multi-label Classification.  _Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.
  * Tsatsaronis et al. (2015) Tsatsaronis, G.; Balikas, G.; Malakasiotis, P.; Partalas, I.; Zschunke, M.; Alvers, M. R.; Weissenborn, D.; Krithara, A.; Petridis, S.; Polychronopoulos, D.; Almirantis, Y.; Pavlopoulos, J.; Baskiotis, N.; Gallinari, P.; Artières, T.; Ngomo, A.-C. N.; Heino, N.; Gaussier, É.; Barrio-Alvers, L.; Schroeder, M.; Androutsopoulos, I.; and Paliouras, G. 2015\.  An overview of the BIOASQ large-scale biomedical semantic indexing and question answering competition.  _BMC Bioinformatics_ , 16.
  * Xu, Tao, and Xu (2016) Xu, C.; Tao, D.; and Xu, C. 2016.  Robust Extreme Multi-label Learning.  _Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_.
  * Yang et al. (2018) Yang, Z.; Dai, Z.; Salakhutdinov, R.; and Cohen, W. W. 2018.  Breaking the Softmax Bottleneck: A High-Rank RNN Language Model.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_.
  * Zhu et al. (2019) Zhu, C.; Huang, W. R.; Li, H.; Taylor, G.; Studer, C.; and Goldstein, T. 2019.  Transferable clean-label poisoning attacks on deep neural nets.  In _International Conference on Machine Learning_ , 7614–7623. PMLR.
  * Ziegler (1994) Ziegler, G. M. 1994.  _Lectures on Polytopes_.  Springer New York, NY.

##  Appendix A Points in General Position

######  Definition 8.

We say $n$ points are in general position in $\mathbb{R}^{d}$ if any subset of
$d$ or fewer points is linearly independent.

Intuitively, this means that the points are no more dependent than they need
to be in $\mathbb{R}^{d}$. No 2 points lie on a line through the origin, no 3
points lie on a plane through the origin, no $d$ points lie in a $d-1$
subspace. Algebraically, it means that a $d\times d$ matrix formed by stacking
any $d$ points together has non-zero determinant.

######  Definition 9.

Consider n points in $\mathbb{R}^{d}$ stacked in the rows of
$\mathbf{W}\in\mathbb{R}^{n\times d}$. The points are linearly dependent if:

$\exists\mathbf{\mathbf{z},\,\mathbf{z}\neq\mathbf{0}}:\,\mathbf{z}^{\top}\mathbf{W}=\mathbf{0}$
(10)

##  Appendix B The Cyclic Polytope

To prove Lemma 2 in the next section, we leverage the theorem in Cordovil and
Duchet (2000), who present their result in terms of the homogenisation of the
Cyclic Polytope. Herein we highlight the equivalence of the homogenisation of
the Cyclic Polytope to a DFT matrix with total order constraints on the
$t_{i}$. We will need this to make claims about the maximal minors of the DFT
matrix.

##### The Cyclic Polytope

We start with the standard definition. The $\bm{\mathcal{C}}_{n,d}$ with $n$
vertices in $\mathbb{R}^{d}$ is defined as the convex hull of $n>d$ distinct
points on the moment curve in $\mathbb{R}^{d}$ (Ziegler 1994, Example 0.6,
p.11). The moment curve is a map $m(t):\mathbb{R}\mapsto\mathbb{R}^{d}$
defined as:

$\displaystyle\bm{\mathcal{C}}_{n,d}=$
$\displaystyle\operatorname{conv}\left(m(t_{1}),m(t_{2}),\ldots,m(t_{n})\right)$
(11) $\displaystyle\text{where}\quad m(t)=$ $\displaystyle\begin{bmatrix}t\\\
t^{2}\\\ \vdots\\\ t^{d}\end{bmatrix},\quad t_{1}<t_{2}<\ldots<t_{n}$ (12)

##### Homogenisation

We move from affine to linear space by appending an extra dimension and fixing
it to $1$, i.e. we have
$\operatorname{hom}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d+1},\,\operatorname{hom}(\mathbf{x})=\begin{pmatrix}1\\\
\mathbf{x}\end{pmatrix}$. To conform with earlier notation, we will stack the
vertices of the Cyclic Polytope in the rows of the matrix. For the standard
Cyclic Polytope on the moment curve we get a Vandermonde matrix:

$\displaystyle\bm{\mathcal{C}}_{n,d}$
$\displaystyle=\begin{bmatrix}t_{1}&t_{1}^{2}&\cdots&t_{1}^{d}\\\
t_{2}&t_{2}^{2}&\cdots&t_{2}^{d}\\\ \vdots&\vdots&\ddots&\vdots\\\
t_{n}&t_{n}^{2}&\cdots&t_{n}^{d}\\\ \end{bmatrix}$ (13)
$\displaystyle\operatorname{hom}\left(\bm{\mathcal{C}}_{n,d}\right)$
$\displaystyle=\begin{bmatrix}1&t_{1}&t_{1}^{2}&\cdots&t_{1}^{d}\\\
1&t_{2}&t_{2}^{2}&\cdots&t_{2}^{d}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
1&t_{n}&t_{n}^{2}&\cdots&t_{n}^{d}\\\ \end{bmatrix}$ (14)

##### Trigonometric Cyclic Polytope

Instead of the moment curve, Gale (1963) used the trigonometric moment curve
to construct the Cyclic Polytope. We note that its homogenisation is the
truncated DFT matrix.

$\displaystyle\bm{\mathcal{C}}_{n,2k}$
$\displaystyle=\begin{bmatrix}\cos{t_{1}}&\sin{t_{1}}&\cdots&\cos{kt_{1}}&\sin{kt_{1}}\\\
\cos{t_{2}}&\sin{t_{2}}&\cdots&\cos{kt_{2}}&\sin{kt_{2}}\\\
\vdots&\vdots&\ddots&\vdots\\\
\cos{t_{n}}&\sin{t_{n}}&\cdots&\cos{kt_{n}}&\sin{kt_{n}}\\\ \end{bmatrix}$
(15) $\displaystyle\operatorname{hom}\left(\bm{\mathcal{C}}_{n,2k}\right)$
$\displaystyle=\begin{bmatrix}1&\cos{t_{1}}&\sin{t_{1}}&\cdots&\cos{kt_{1}}&\sin{kt_{1}}\\\
1&\cos{t_{2}}&\sin{t_{2}}&\cdots&\cos{kt_{2}}&\sin{kt_{2}}\\\
\vdots&\vdots&\vdots&\ddots&\vdots\\\
1&\cos{t_{n}}&\sin{t_{n}}&\cdots&\cos{kt_{n}}&\sin{kt_{n}}\\\ \end{bmatrix}$
$\displaystyle t_{i}=\frac{2\pi(i-1)}{n},\,i\in[n]$ (16)

In Section D.3, we will use the connection between the DFT matrix and the
Cyclic Polytope to prove Lemma 2.

##  Appendix C Grassmanians

The Grassmanian ${Gr}_{n,d}$ is the set of all $d$-dimensional subspaces of
$\mathbb{R}^{n}$. We will think of $Gr_{n,d}$ as the space of rank $d$
matrices $\mathbf{W}\in\mathbb{R}^{n\times d}$ with $1\leq d\leq n$. More
precisely, a single member of $Gr_{n,d}$ defines a subspace and corresponds to
all $\mathbf{W}$ that form a basis for that subspace, i.e. all matrices
obtained by multiplying the basis on the right by any invertible $d\times d$
matrix. 101010Column operations change the basis of the columnspace but not
the subspace itself. We can subdivide the whole Grassmanian into more granular
matrix families by considering the sign of the maximal minors. For the scope
of this paper, we are specially interested in the Totally Positive Grassmanian
${Gr}^{+}_{n,d}$, the space of $n\times d$ matrices for which all maximal
minors are non-zero and have the same sign (see also Postnikov (2006,
Definition 3.1)).

##  Appendix D Proofs

###  D.1 Lemma 1

$\mathbf{y}$ is $k$-active $\implies\mathbf{y}$ is at most $2k$-alternating.

###### Proof.

Construct a $k$-active $\mathbf{y}$ of length $n$ from the all inactive
$\mathbf{y}$ by flipping all signs after any of the $n-1$ positions between
labels. We need at most $2k$ distinct flips, i.e. when the active labels are
not adjacent and do not include the $1^{st}$ or $n^{th}$ label and less
otherwise. For example, ${{\scriptstyle-+--}}$ can be produced with 2 flips
starting from the all inactive vector:
${{\scriptstyle----}}\rightarrow{{\scriptstyle-+++}}\rightarrow{{\scriptstyle-+--}}$.
∎

###  D.2 Theorem 3

###### Proof.

Since $\mathbf{W}\in{Gr}^{+}_{n,d}$, all maximal minors are non-zero and hence
the rows of $\mathbf{W}$ are in general position (see Definition 2). By
invoking Theorem 1, the number of argmaxable label assignments is
$\left|\mathcal{A}\left(\mathbf{W}\right)\right|=2\sum\nolimits_{d^{\prime}=0}^{d-1}\binom{n-1}{d^{\prime}}$.
Note that this is exactly the number of $(d-1)$-alternating label assignments
$\left|{V}_{n,d-1}\right|$ as we elaborate on next. The binomial coefficient
comes from choosing $d^{\prime}$ out of the $n-1$ positions between labels to
flip the sign and we sum over all possible number of sign changes up to $d-1$.
For each alternating $\mathbf{y}$, we can produce another by flipping all
signs, hence the leading multiplier $2$. Now, from Theorem 2, none of the
label assignments can have more than $d-1$ sign changes; hence they must be
exactly the $(d-1)$-alternating label assignments:
$\mathcal{A}\left(\mathbf{W}\right)={V}_{n,d-1}$. ∎

###  D.3 Lemma 2

###### Proof.

The DFT matrix corresponds to the homogenisation of the vertices of a Cyclic
Polytope (Gale 1963; Cordovil and Duchet 2000), see Appendix B, where the
vertices of the Cyclic Polytope are in $2k$ dimensions before being
homogenised. Cyclic Polytopes in $2k$ dimensions (even dimension) are rigid:
their face structure determines their geometric structure (Cordovil and Duchet
2000, Theorem 5.1). Their geometric structure is that of a Uniform Alternating
Oriented Matroid. Any matrix realisation of a Uniform Alternating Oriented
Matroid has maximal minors that agree in sign and are non-zero (Cordovil and
Duchet 2000, Proposition 3.1) (from the chirotope representation of Oriented
Matroids (Björner et al. 1999, Section 9.4)). Any normalisation of the DFT
matrix obtained by scaling columns using non-zero scalars does not alter the
columnspace of the matrix, and hence the oriented matroid structure is
unchanged: the orthants intersected by the columnspace are the same. ∎

##  Appendix E DFT Layer as FFT

We can use the FFT to speed up computations, as we will show that computing
the logits $\mathbf{z}$ is equivalent to computing the truncated inverse DFT
of the input $\mathbf{x}$, if we reinterpret the vector $\mathbf{x}$ that has
$2k+1$ entries as the coefficients of $k+1$ complex numbers. Let us start from
the inverse DFT, that computes the complex signal in the time domain from the
frequency domain. We use $n^{\prime},d^{\prime}$ and $k^{\prime}$ as variables
to avoid confusion with $n,d$ and $k$, which we have already defined as
constants throughout the paper. Denote the complex frequency component for
frequency $k^{\prime}$ by $X_{k^{\prime}}$ and the signal at time $n^{\prime}$
by $x_{n^{\prime}}$, we have:

$x_{n^{\prime}}=\sum_{k^{\prime}=0}^{n-1}X_{k^{\prime}}\left[\cos\left(\frac{2\pi
n^{\prime}}{n}k^{\prime}\right)+i\sin\left(\frac{2\pi
n^{\prime}}{n}k^{\prime}\right)\right]$ (17)

We take the real part of the iDFT, to obtain:

$\displaystyle x_{n^{\prime}}$
$\displaystyle=\sum_{k^{\prime}=0}^{n-1}X_{k^{\prime}}\left[\cos\left(k^{\prime}t_{n^{\prime}}\right)+i\sin\left(k^{\prime}t_{n^{\prime}}\right)\right]$
$\displaystyle=\sum_{k^{\prime}=0}^{n-1}(a_{k^{\prime}}+ib_{k^{\prime}})\left[\cos\left(k^{\prime}t_{n^{\prime}}\right)+i\sin\left(k^{\prime}t_{n^{\prime}}\right)\right]$
$\displaystyle=\sum_{k^{\prime}=0}^{n-1}\left[a_{k^{\prime}}\cos\left(k^{\prime}t_{n^{\prime}}\right)-b_{k^{\prime}}\sin\left(k^{\prime}t_{n^{\prime}}\right)\right]$

If we truncate the iDFT to the first $k$ frequencies, we get:

$\displaystyle x_{n^{\prime}}$
$\displaystyle=\sum_{k^{\prime}=0}^{k}\left[a_{k^{\prime}}\cos\left(k^{\prime}t_{n^{\prime}}\right)-b_{k^{\prime}}\sin\left(k^{\prime}t_{n^{\prime}}\right)\right]$

We will now match the coefficients $a_{k^{\prime}}$ and $b_{k^{\prime}}$ to
corresponding elements in $\mathbf{x}$ (ignoring scaling factors). From the
earlier computation of $\mathbf{W}\mathbf{x}$, we rewrite the logits
$\mathbf{z}$ as below:

$\displaystyle\mathbf{z}_{n^{\prime}}$
$\displaystyle=\mathbf{w}_{n^{\prime}}^{\top}\mathbf{x}$ (18)
$\displaystyle=\mathbf{x}_{1}+\sum_{k^{\prime}=1}^{k}\left[\mathbf{x}_{2k^{\prime}}\cos\left(k^{\prime}t_{n}\right)+\mathbf{x}_{2k^{\prime}+1}\sin\left(k^{\prime}t_{n}\right)\right]$
(19)

From which we see that we can write the DFT layer as a truncated Inverse DFT
by matching the coefficients of the sines and cosines:
$\mathbf{x}_{1}=a_{0},\,\mathbf{x}_{2k^{\prime}}=a_{k^{\prime}}$ and
$\mathbf{x}_{2k^{\prime}+1}=-b_{k^{\prime}}$. See also our code
test_dft_equivalence.py. From this perspective, this paramatrisation is a low-
pass filter.

##  Appendix F Unargmaxable Test Examples

We now introduce two fine-grained measurements of argmaxability, eps-
argmaxability and $1$-argmaxability. We discuss a few additional insights in
the results section below.

###  F.1 Argmaxability Measurements

##### eps-argmaxable

This is the estimate of argmaxability we can get at the precision of our LP,
which is _eps_ =$10^{-8}$. This roughly means that we can only detect regions
which can contain a ball with a radius that is larger than $10^{-8}$.

##### 1-argmaxable

As we discussed in the paper, some label assignments may be
$\epsilon$-argmaxable with a very small $\epsilon$, which makes it hard to
predict such label assignments in practice. We therefore also report
$1$-argmaxability, assuming – by a fairly large margin – that regions with
radius $1$ are large enough to be easily predicted in practice.

###  F.2 Results

In Tables 3, 2 and 4 we tabulate the number of argmaxable label combinations
on the MIMIC-III, BioASQ and OpenImages v6 test sets. We obtain the following
insights.

a) For the DFT, when we make $d$ very small, e.g. $d=25$, a handful of label
combinations in BioASQ are not eps-argmaxable according to the LP. Out of
these, one example was found to be infeasible, while for the remaining ones
numerical difficulties were encountered by the LP, i.e. Gurobi returned status
12: “ _Operation terminated due to unrecoverable numerical difficulties_ ”.
The above issues are likely caused because of dimensionality pressures, the
label combinations are $\epsilon$-argmaxable but with a very small $\epsilon$
that cannot be detected with the precision of current LPs (eps=$10^{-8}$, as
we discussed in Section 3). This highlights the importance of our proofs,
since our results would be tricky to verify using empirical methods alone.
Moreover, as we discussed in Section 7, being able to guarantee
$\epsilon$-argmaxability with a large $\epsilon$ is important future work,
since while we showed that our current solution of adding slack variables
works in practice, if we increase the pressure on the bottleneck by making $d$
small enough, we can still run into $\epsilon$-argmaxability issues.

b) We note that the behaviour of BSLs in terms of eps-argmaxability and
$\epsilon$-argmaxability is quite different when compared to DFT. For BSLs, if
a label combination is argmaxable, it is very often also
$\epsilon$-argmaxable. On the other hand, for the DFT some label combinations
are argmaxable but are not $\epsilon$-argmaxable, highlighting that the
regions do indeed exist, but they can shrink quite a bit in size due to the
reduced dimensionality.

Table 2: Median number of $eps$-argmaxable and $1$-argmaxable label assignments over 3 random seeds on the dev and test sets of MIMIC-III. Takeaway: BSL layers have unargmaxable labels starting from $d=200$ but it does not have to be this way. DFT layers resolve this problem and make all examples argmaxable, but when slack dimensionality is very small, the regions are too small to detect with the precision of the LP. Note that even if a BSL is able to argmax all test label configurations, this does not imply it will be able to guarantee so for meaningful but unseen future configurations. split |  $d$ | # $eps$-Argmaxable |  $1$-Argmaxable
---|---|---|---
BSL | DFT | BSL | DFT
dev | 25 | 128 |  1631 | 128 | 1572
| 50 | 781 |  1631 | 781 | 1625
| 100 | 1533 |  1631 | 1533 | 1631
| 200 | 1631 |  1631 | 1631 | 1631
| 500 | 1631 |  1631 | 1631 | 1631
test | 25 | 229 |  3371 | 229 | 3216
| 50 | 1515 |  3371 | 1515 | 3356
| 100 | 3137 |  3371 | 3137 | 3370
| 200 | 3370 |  3371 | 3370 | 3371
| 500 | 3371 |  3371 | 3371 | 3371
Table 3: Median number of $eps$-argmaxable and $\epsilon$-argmaxable label assignments over 3 random seeds on the test set of BioASQ. Note that even if a BSL is able to argmax all test label configurations, this does not imply it will be able to guarantee so for meaningful but unseen future configurations. split | d | # $eps$-Argmaxable | # $1$-Argmaxable
---|---|---|---
out of 10000 | out of 10000
BSL | DFT | BSL | DFT
test | 25 | 880 | 9995 | 879 | 8174
| 50 | 6498 | 10000 | 6483 | 9925
| 100 | 9951 | 10000 | 9950 | 10000
| 200 | 10000 | 10000 | 10000 | 10000
| 400 | 10000 | 10000 | 10000 | 10000
Table 4: Median number of $eps$-argmaxable and $\epsilon$-argmaxable label assignments over 3 random seeds on the test set of OpenImages. Note that even if a BSL is able to argmax all test label configurations, this does not imply it will be able to guarantee so for meaningful but unseen future configurations. split | d | # $eps$-Argmaxable | # $1$-Argmaxable
---|---|---|---
out of 10000 | out of 10000
BSL | DFT | BSL | DFT
test | 25 | 2758 | 10000 | 2757 | 9981
| 50 | 8439 | 10000 | 8435 | 10000
| 100 | 9997 | 10000 | 9997 | 10000
| 200 | 10000 | 10000 | 10000 | 10000
| 400 | 10000 | 10000 | 10000 | 10000

##  Appendix G DFT Train Efficiency

Herein we provide more information showing how the DFT layer speeds up
convergence and requires less training time to reach equivalent performance.
We focus on the most demanding datasets, BioASQ and OpenImages v6, and
highlight two perspectives. In Fig. 7, we show how the training loss evolves
over time. Meanwhile, in Fig. 8 we compare the number of hours it took for the
BSL and DFT models to converge on BioASQ and OpenImages v6. Both figures show
that the DFT layer leads to faster convergence, as it starts training with a
lower loss due to the initialisation trick and maintains its lead over the BSL
throughout training.

Figure 7: Comparison of BSL and DFT for $d=100$, in terms of the training
cross entropy loss (y-axis, log scale) as training evolves (x-axis). Due to
the initialisation trick, the DFT starts training at a lower loss and
converges faster.

Figure 8: Comparison of BSL and DFT in terms of training time (in hours) to
convergence. As can be seen, the DFT converges about 25% faster.

##  Appendix H Reproducibility

###  H.1 Dataset Access and Preprocessing

#### MIMIC-III

While de-identified, the MIMIC-III dataset (Johnson et al. 2016) contains
sensitive and detailed information on the clinical care of patients. As such,
permission to access this dataset needs to be requested, as explained
here.111111https://mimic.mit.edu/docs/gettingstarted/ We used the same
preprocessing, setup and train, validation and test splits as (Mullenbach et
al. 2018). See their github repository for more
details.121212https://github.com/jamesmullenbach/caml-
mimic/blob/master/notebooks/dataproc˙mimic˙III.ipynb

#### BioASQ Task A 2021

The BioASQ Task A dataset (Tsatsaronis et al. 2015; Nentidis et al. 2021) is
available after registering for the task on the BioASQ
website.131313http://participants-area.bioasq.org/ We created dataset splits
which cover $n=$20k labels using a 1m subset of the 2021 BioASQ task A
dataset. We construct train, validation and test split by sampling examples,
making sure that all individual labels (not label combinations) occur in both
the train and test sets. We encode the concatenation of the journal, title and
abstract as text input. Due to the context size limitation of BERT, we
truncate the input to the first $512$ subwords. See our code for more details.

#### OpenImages v6

The OpenImages v6 dataset (Kuznetsova et al. 2020) can be accessed from the
project website.141414https://storage.googleapis.com/openimages/web/index.html
We downloaded the images from CVDF, which was linked from the website. Since
the dataset is very large, we only used $N=108228$ images, these had hashes
that started with $1$ and were available as a single zip download from CVDF.
Since the validation and test sets are also large, we validate and test on the
first 5k examples of the validation set and the first 10k examples of the test
set, correspondingly. For preprocessing, we simply reshape all images to
448x448, as done in Baruch et al. (2020).

###  H.2 Dataset Statistics

We tabulate the sizes of the dataset splits in Table 5. A histogram of the
number of active labels can be seen in Fig. 9.

Figure 9: Comparison of the number of active labels on the training sets of
MIMIC-III, BioASQ and OpenImages datasets. All three datasets have a long tail
of high cardinality labels, but MIMIC-III has the longest with some examples
having more than $60$ active labels.

Table 5: Dataset attributes and model hyperparameters.

| Datasets
---|---
| MIMIC-III | BioASQ task A | OpenImagesV6
n | 8921 | 20000 | 8933
d | 25-400 | 25-400 | 25-400
encoder | CNN | PubmedBERT | T-Resnet-L
pretrained | no | yes | yes
encoder dim $e$ | 500 | 768 | 2432
lr (encoder) | 0.001 | 0.00005 | 0.0001
lr (classifier) | 0.001 | 0.001 | 0.001
batch size | 16 | 32 | 64
patience | 10 | 10 | 10
eval every | 1 epoch | 500 steps | 250 steps
criterion | P@8 | Valid loss | Valid loss
# train | 44k | 100k | 108k
# valid | 1.6k | 5k | 5k
# test | 3.3k | 10k | 10k

###  H.3 Hyperparameters

In order to study the sensitivity of our methods to random initialisation we
ran all experiments three times, once per random seed in (0, 1, 2). We train
all models using binary crossentropy loss. We summarise all hyperparameters in
Table 5. We use early stopping for all models with a patience of $10$. The
stopping criterion is Prec@8 for MIMIC-III and Validation Loss for BioASQ and
OpenImages.

###  H.4 Training Resources and Train time

We train and evaluate our models on GPUs. For the MIMIC-III dataset we used a
NVIDIA 3090 GPU that has 24Gb of RAM and for the remaining two datasets we
used an NVIDIA RTX A6000 which has 48Gb of RAM. The experiments took about two
weeks of compute. More specifically, the MIMIC-III runs took 9 hours, the
OpenImages runs took 85 hours and the BioASQ runs took 188 hours. We verified
our models using the LP on CPU on a cluster with an AMD EPYC 7452 32-Core
Processor and 500GB of RAM. We parallelised verification by running the LP for
each label in parallel to others of the same model. With this setup and
running on 50 threads the verification of 10k examples takes from between 20
minutes to 3 hours, depending on the dimensionality (slower for large $d$).

##  Appendix I Why DFT Regions Become Very Small

For a matrix $\mathbf{W}$ to have the Uniform Alternating Oriented Matroid
structure, all its maximal minors have to be non-zero and have the same sign.
Let us assume they are all positive. For the matrix to “robustly” have this
structure, the maximal minors should be large, the larger they are the more
the row vectors will have to change until two hyperplanes cross and change the
Oriented Matroid structure.

However, the DFT matrix is also an orthonormal matrix; all columns have an
$l_{2}$-norm of $1$ and all pairs of columns have dot product $0$.
Importantly, an orthonormal matrix $\mathbf{M}\in\mathbb{R}^{n\times d},\,d<n$
with maximal minors $\Delta_{I}$ indexed by $d$-subsets of rows, has the
property that the sum of squares of the maximal minors is bounded and equals
1:

$\sum_{I\in\binom{[n]}{d}}\Delta_{I}(\mathbf{M})^{2}=1$ (20)

Therefore, we have a bound of $1$ on the sum of squares of maximal minors, and
since there are $\binom{n}{d}$ maximal minors, a lot of them will have to be
very small as we increase the difference between $n$ and $d$ with $d<<n$.

##  Appendix J Evaluation Metrics

###  J.1 MLC Metrics

##### F1

We compute Micro F1 by computing Precision and Recall across all labels and
then computing F1. We compute Macro F1 by computing Precision, Recall and F1
score for each label individually and then averaging them. Macro F1 does not
allow label imbalance to skew the results.

##### Precision@$k$ (Prec@$k$)

Prec@$k$ computes the percentage of the $k$ retrieved labels that are indeed
correct. We compute the metric by ranking the labels by their assigned
probabilities and take the top $k$ as active. We then compute the percentage
that is active in the gold data, i.e. we divide the number of correct active
labels by $k$. Prec@k is not sensitive to the relative ordering of the labels
within the top-k.

##### Recall@$k$ (Rec@$k$)

Rec@$k$ computes how many of the actual active labels are actually retrieved
in the top $k$. As in Prec@k, we rank the labels by their assigned
probabilities and take the top $k$ as active, but this time we divide by the
number of labels that are actually active.

##### F1@$k$ (F1@$k$)

As is common with metrics, it is useful to distil as much information as
possible into a single number. To achieve this, it is common to use the
harmonic mean of Prec@k and Rec@k which captures the intuition that we want
both Prec@k and Rec@k to be high:

$\text{F1@k}=2\frac{\text{Prec@k}\,\text{Rec@k}}{\text{Prec@k}+\text{Rec@k}}$
(21)

##### Normalised Discounted Cumulative Gain @$k$ (nDCG@$k$)

nDCG (Järvelin and Kekäläinen 2002) is sensitive to the relative ranking of
examples within the $k$-top subset, due to the use of discounting. To compute
it, we rank the labels according to their assigned probabilities, take the top
$k$ and sum their truth values, which for MLC is $1$ if the label is active
and $0$ otherwise. However, as opposed to Prec@k, DCG@k adds a logarithmic
discount factor such that ranking an irrelevant label above a relevant one is
penalised. We use nDCG, which includes normalisation such that the score is in
$[0,1]$, with $1$ being optimal.

###  J.2 More Results

Figure 10: Test set Precision@k across datasets. For MIMIC-III, Mullenbach et
al. (2018) report 58.1 Prec@8 for their CNN baseline. We showed that their
result can be improved by: a) Making the learning rate 0.001 b) adding a
projection layer after the CNN and c) using the DFT layer.

Figure 11: Test set Recall@k across datasets.

Figure 12: Test set Micro F1 across datasets.

Figure 13: Test set Macro F1 across datasets.

Figure 14: Test set nDCG across datasets.

##  Appendix K Illustration of Argmaxable Regions

In the figures to the right, we provide an illustration of the structure of
the label assignments for $\bm{W}^{\mathsf{DFT}}_{6,3}$. In Fig. 15(a), we
illustrate the subset of label assignments that are argmaxable. We represent
each label assignment as a sign vector where $+$ denotes an active label and
$-$ an inactive one. We color the node green if the corresponding label
assignment is argmaxable. We can inspect the consequences of Theorem 4
visually, the $1$-active label assignments are argmaxable. In Fig. 15(b), we
illustrate the geometric realisation of $\bm{W}^{\mathsf{DFT}}_{6,3}$, where
each row of the matrix is a normal vector to a hyperplane. To simplify the
plot, instead of plotting the hyperplanes, we plot the Chebyshev balls that
correspond to each region. Lastly, in Fig. 15(c) we show the hyperplanes to
make it clearer how the balls in the regions are constructed. For an
interactive visualisation see
https://grv.unargmaxable.ai/static/files/alternahedron/index.html.

(a) Visual check that for $\mathbf{W}=\bm{W}^{\mathsf{DFT}}_{6,3}$ all
$2$-alternating, and hence all $1$-active labels are argmaxable. Each node
corresponds to a label assignment, and it is green if it is argmaxable and red
if not. We order the labels in levels in terms of $k$, the number of active
labels. As can be seen, the levels for $k=0$ and $k=1$ only have green nodes,
with unargmaxable label assignments first occurring for $k=2$.

(b) Geometric realisation of $\mathbf{W}=\bm{W}^{\mathsf{DFT}}_{6,3}$ in 3D
space. The 6 hyperplanes defined by the rows of $\mathbf{W}$ tesselate 3D
space into $32$ regions. For the illustration, we drop the hyperplanes and
only plot the Chebyshev regions: each ball is the largest ball that fits in
the corresponding region, as discovered by the Chebyshev LP. Each argmaxable
label assignment from the plot on the left has a corresponding ball. The six
1-active label assignments from above are the light blue balls, arranged like
petals.

(c) Same plot as above but with hyperplanes drawn.