# Minimal Learning Machine for Multi-Label Learning

Joonas Hämäläinen
University of Jyvaskyla
Faculty of Information Technology
<EMAIL_ADDRESS>
&Amauri Souza
Federal Institute of Education,
Science and Technology of Ceará—IFCE
Department of Computer Science
<EMAIL_ADDRESS>
&César L. C. Mattos
Federal University of Ceará—UFC
Department of Computer Science
<EMAIL_ADDRESS>
&João P. P. Gomes
Federal University of Ceará—UFC
Department of Computer Science
<EMAIL_ADDRESS>
&Tommi Kärkkäinen
University of Jyvaskyla
Faculty of Information Technology
<EMAIL_ADDRESS>

###### Abstract

Distance-based supervised method, the minimal learning machine, constructs a
predictive model from data by learning a mapping between input and output
distance matrices. In this paper, we propose methods and evaluate how this
technique and its core component, the distance mapping, can be adapted to
multi-label learning. The proposed approach is based on combining the distance
mapping with an inverse distance weighting. Although the proposal is one of
the simplest methods in the multi-label learning literature, it achieves
state-of-the-art performance for small to moderate-sized multi-label learning
problems. Besides its simplicity, the proposed method is fully deterministic
and its hyper-parameter can be selected via ranking loss-based statistic which
has a closed form, thus avoiding conventional cross-validation-based hyper-
parameter tuning. In addition, due to its simple linear distance mapping-based
construction, we demonstrate that the proposed method can assess predictions’
uncertainty for multi-label classification, which is a valuable capability for
data-centric machine learning pipelines.

_K_ eywords Multi-Label Learning $\cdot$ Multi-Label Classification $\cdot$
Inverse-Distance Weighting $\cdot$ Minimal Learning Machine $\cdot$
Uncertainty

##  1 Introduction

Multi-label classification (MLC, [1, 2, 3]) refers to a supervised machine
learning task where an instance can be associated with more than one class.
This is different from the more common machine learning task, the single-label
classification (SLC), where each instance is associated with one class—and
represented with one active label—only. This simplification means that all the
other possible class labels are irrelevant, which can be a naive assumption
since many real-world problems are inherently multi-label.

Indeed, there exists a multitude of relevant application areas of multi-label
classification. These include (but are not limited to) categorization of texts
and documents [4, 5, 6, 7, 8, 9, 10], medical imaging [11, 12, 13, 14], health
and bioinformatics [15, 16, 17, 18, 19], remote sensing [20], cybersecurity
[21], brain research [22], power load monitoring [23], and applications in
computational chemistry [24, 25].

Formally, in the MLC, each instance is associated with a bipartition of the
possible labels into a set of relevant and irrelevant labels. Typically, an
MLC method predicts this bipartition via scoring and/or ranking the labels
with thresholding. Therefore, the MLC is closely related to the multi-label
ranking. Together these two tasks are below the umbrella concept of multi-
label learning [26].

Typically, conventional supervised methods are not directly applicable to MLC
problems. The two main approaches to handle these problems are [1] $i)$
algorithm adaptation and $ii)$ problem transformation. In the first one, a SLC
approach is modified for the MLC, referring that the SLC approach is adjusted
so that the correlating labels are somehow handled in training. In the second
approach, the label space is transformed to be suitable for any SLC method.
Such a step may consider a second layer of hyper-parameters, in addition to
the core SLC method’s hyper-parameters.

In this paper, we evaluate distance regression-based methods for the MLC
problems. Our main claim of the paper is that linear distance mapping is
beneficial construction for multi-label learning. The main proposal is to
construct a multi-label classifier by integrating the distance regression step
from the minimal learning machine (MLM) [27] and the inverse distance
weighting (IDW) method [28]. This combination, referred to as multi-label
minimal learning machine (ML-MLM ), constructs a simple MLC method that is
fully deterministic and whose hyper-parameter can be selected via ranking
loss-based statistic which has a closed form. In addition, we demonstrate that
ML-MLM can assess the uncertainty of prediction intuitively which we see as a
valuable property for data-centric machine learning pipelines.

In order to support our main claim and demonstrate the proposed methods’
viability, we present theoretical and extensive experimental results. Firstly,
we show theoretical results to support and motivate our method’s integration
of the linear distance mapping and IDW scheme. Secondly, we show an extensive
experimental study (ten benchmark datasets, eight core MLC performance
metrics) regarding four distance regression-based variants and compared our
results to the state-of-the-art. We focus on comparing our methods to a random
forest based method (random forest of predictive clustering trees) [29] which
has been one the best performing methods in extensive experimental comparisons
[26, 3]. The experimental results indicate that ML-MLM and other distance
regression-based methods are competitive with the state-of-the-art for small
to moderate-sized MLC problems, besides being one of the simplest methods in
the MLC literature. In addition, according to the experimental results, the
distance regression-based methods outperform multi-label kNN (ML-kNN) [30]
clearly.

Bemporad [31] integrated IDW and radial basis functions (RBF) to probe
expensive objective function evaluations in the field of global optimization.
This IDW and RBF integration has some methodological similarity with ML-MLM
since RBF and MLM are closely related [32]. Another closely related
contribution to ours is from Zhang and Zhou [30]. This paper proposed ML-kNN,
which is similar to our proposal, because ML-kNN also uses feature space
distances for multi-label learning. In the MLC taxonomy, ML-kNN belongs to
same category with our method, however, the Bemporad’s contribution is more
closer to ours. Moreover, this paper was inspired by the promising preliminary
results of MLM in MLC [33].

The rest of the paper is structured as follows. First, in Section 2, we review
MLC methods and experimental comparisons, and, summarize the most closely
related papers to our work. Then, in Section 3, notations and basic
methodology are introduced. In addition, we present theoretical results for
MLM. Next, the main proposal of the paper, ML-MLM , is introduced in Section
4. This is followed by the experimental part of the paper in Section 5.
Finally, Sections 6 and 7 discuss and conclude the paper.

##  2 Related work

In this Section, we first review the most central MLC methodology in
Subsection 2.1. Next, in Subsection 2.2 we review the most closely related
papers concerning our main proposal. Finally, in Subsection 2.3, we review
experimental landscape of MLC.

###  2.1 A brief review of multi-label classification

The most straightforward approach for tackling the multi-label classification
(MLC) problems is the so-called binary relevance (BR) problem transformation
method [34, 1]. In the BR, models are trained for each label separately with
the one-vs-all approach. The prediction is then directly determined by these
label-wise SLC models’ predictions. For the BR, there are well-known
shortcomings. For a large number of labels, BR, and also other problem
transformation methods, can have high computational cost. In addition, it is
assumed in the BR that the information of label dependencies is not needed in
the training, i.e., each predicted label is solely determined by the input
data. Despite its shortcomings, the BR is an important methodological baseline
for the MLC.

As depicted in [1] and Section 1, techniques for the MLC can be basically
divided into _problem transformation (PT)_ and _algorithm adaptation (AA)_
methods. Besides the BR, another classical example of the PT is the label
powerset (LP) [35], where each distinct combination of labels in the training
set is treated as a different and single class. Actually, there exist many
open-source software packages based on the PT techniques which provide
implementations for the MLC algorithms via interfacing with standard single-
label methods [36, 37, 38].

According to [2], the AA methods can be further divided into first- and
second-order methods, where the classical k-nearest-neighbor (kNN) MLC
extension, the ML-kNN [30], is an example of the former, and the rank-SVM with
a modified kernel [39], of the latter. The first-order AA methods, also a
straightforward extension of single-label multiclass classifiers, can produce
by construction an output-vector reflecting class probabilities—like shallow
and deep neural networks with 1-of-$k$ class encoding—, but with a modified
labelling strategy [40]. In the simplest case, one could just return all
certain-enough labels, which can be selected using a threshold [39, 40, 41],
using a complete rejection of the unreliable predictions [42], or via the
estimated posterior probabilities, according to Bayes’ rule, as in ML-kNN
[30].

In addition to the AA and PT, a third category of the MLC approaches can be
also defined, the ensemble methods [26]. These methods refer to different
kinds of combinations of the common problem transformation and algorithm
adaptation methods. A prime example is the RAKEL (RAndom k-labELsets) method,
by Tsoumakas et al. [1]. Ensembles for the PT that better address the
multiscale nature of the MLC problems, by taking into account label
dependencies, are provided by the classifier chains (CC), i.e., cascade
combinations of single label models [43, 44, 45]. These and other ensembles
are based on a base classifier which may be trained for different label
subsets [46, 47], different training examples [48, 49], using different
feature subsets [50, 51, 52], or via combinations of these divisive strategies
[53]. Features and/or labels could also be transformed into a lower dimension
space, either for a single MLC model or within an ensemble [54, 55, 56, 57].
There exist multiple ways to integrate different base classifiers in
ensembles, such as direct mean-output [46], selection and use of the most
prominent one [58], and the weighted stacking strategy [59]. Note that the new
proposed MLM classifier for MLC could be also naturally used as a base
classifier in ensembles, as demonstrated in [33].

As depicted in [60, 32], the MLM technique can be linked to random NN
techniques, which for the MLC problems were addressed in [61]. There,
functional link networks and broad learning systems were used as the NN
architectures with two variants each. Final results after training were
computed using a trained threshold function, similarly to [39]. Comparison
with 12 benchmark datasets was performed against three other random basis
techniques using five evaluation metrics (Hamming loss, one error, coverage,
ranking loss, and average precision). Good quality and especially high
computational efficiency were concluded from the experiments.

Many new methods and approaches have been suggested for the MLC during recent
years. One popular area, similarly to ML in general (see [62]), has been to
use and develop further feature selection (FS) methods, both as filter [63,
64], wrapper [65], or hybrid/embedded form [66]. One can also select both
features and instances, for example, based on their dependency in the latent
topic space [67, 68]. General reviews on FS for the MLC, as provided in [69,
70, 50], were summarized in [62, Section 2.6]. In conclusion, $i)$ most of the
FS methods were of filter type; $ii)$ FS methods for the MLC problems could be
categorized according to four perspectives: label, search strategy,
interaction with the learning algorithm, and data format; and $iii)$ there
exists a direct relation between filter, wrapper, and embedded FS methods with
the single and internal/external BR techniques for the MLC problems. For
instance, label-specific FS techniques were suggested in [52, 71]. FS using
iterative search strategies for the MLC problems, like evolutionary [72] or
multi-objective optimization [73, 74] approaches, have also been proposed. The
use of rough sets for feature ranking and selection was suggested in [75].

In summary, a plethora of different methods, with novel components and/or
integration and modification of existing techniques with heterogeneous data
sources, have been proposed and experimented for the MLC problems over the
years. The basic categories of PT and AA have evolved and hybridized. For
instance, one can construct new labels [69], address semi-supervised scenarios
with incomplete multi-label information [76], address streaming data and
online/incremental learning [77, 78], apply active learning techniques with an
incremental query of the most relevant instances to improve the model’s
performance [79], and extract higher-level features [80, 81].

###  2.2 Distance regression and distance weighting schemes

In this subsection, we will review related research more closely associated
with our proposal. We consider closely related works the ones that use
distance regression-based construction for MLC. We also review the most
relevant works concerning IDW.

Our proposed method uses a distance regression step from MLM [27]. Therefore,
the most closely related work is [33], where MLM was adapted to the MLC
problems with a simple nearest neighbor heuristic. In this method, the
multilateration problem is solved approximately to obtain a classification.
This method differs from NN-MLM [82] only with the label space assumptions.
This difference is further considered in Proposition 1 (Section 3).
Furthermore, in [33], a clustering-based NN-MLM approach for MLC was proposed
to enable the scaling of MLM for large-scale data sets. The preliminary
results in there showed that the proposed methods outperformed ML-kNN in the
accuracy and Hamming loss metrics and that the performance was comparable to a
random forest-based state-of-the-art method. In this paper, we will not
consider this clustering-based NN-MLM approach for MLC further, since we focus
on the evaluation of the proposed method thoroughly with several MLC metrics
for small to moderate-sized data sets. Note that the state-of-the-art is
different compared to these for large-scale MLC problems. Most of the recent
state-of-the-art methods for large-scale MLC problems (including extreme MLC)
are based on deep learning [83, 84]. However, a few clustering-based methods,
such as SLEEC [85], still perform well in the comparisons [86].

Due to it’s simplicity, IDW has been used in several data-driven methods and
applications [87, 88, 89, 90, 31, 91]. However, different from our proposal,
these works only use IDW in the feature space. In our proposal, we use IDW in
the output space to add the ranking loss optimized regression layer to the
method, which is used to form the local weighting of the output space vectors
for classification purposes.

Joseph and Kang [87] integrated IDW with linear regression for improved
prediction accuracy. The proposed approach was tailored for regression tasks
with large-scale data sets and high-dimensional input spaces. The proposed
approach was able to provide confidence intervals for the prediction. Shi et
al. [91] adapted IDW to detect anomalies in distributed photovoltaic power
stations. The IDW method was used nearly in the original form and with the
power parameter selection $P=2$ suggested in the literature (e.g., [28]). The
main idea of the method is to predict the power station’s output with IDW and
then compare it to the actual value to determine via thresholding whether the
station is working anomalously. Chen and Liu [88] applied IDW to a spatial
regression task (rainfall prediction) and studied the behavior of power and
radius of influence parameters. The power parameter value was tuned via cross-
validation, with optimal values being in the interval $[0,5]$.

Chen et al. [89] integrated IDW with the mixed-effect model to construct a
two-step method for missing data handling. This approach was further
integrated with extreme gradient boosting to develop a robust method (missing
data handling) for regression. The method was successfully applied to predict
small ambient particle concentrations on a ground level for high levels of
missing data (nearly $90\%$). In [90] Cevik proposed an IDW-based local
descriptor for facial recognition. Similar to the goals in [89], the
descriptor aimed for a more robust presentation of the feature space. More
precisely, it aims to tackle rotation variances and noise effects of the
feature space. The IDW approach was adjusted with an additional distance decay
parameter for a better match on a local pixel region depending on the
distances and pixel intensities. The proposed method was found to perform well
in classification accuracy compared with the state-of-the-art. Bemporad [31]
integrated IDW and radial basis functions (RBF) to develop an acquisition
function based on that global optimization algorithm for improved probing of
expensive objective function evaluations. Exclusively from a methodological
point of view, this IDW and RBF combination is somewhat close to the proposed
method in this paper, since there are similarities between MLM and RBF. For
instance, the universal approximation proof for RBF can be applied for MLM as
well [32].

###  2.3 Experimental landscape

Next, without being exhaustive, we summarize the most relevant experimental
comparisons of different methods during the last decade in comparison to our
own experiments as reported in Section 5. The reviewed experiments took place
since 2016 and are considered extensive based on the following two criteria:
$i)$ at least ten datasets were used, with at least one of them with more than
10 000 instances; $ii)$ at least five other algorithms were included in the
comparison.

In [41], the authors proposed a hierarchical tree-based ensemble with an SVM
base classifier, referred as _ML-Forest_. The work provided a comparison with
eight other state-of-the-art algorithms using five-fold cross-validation (CV)
for the parameter tuning based on the Hamming loss. The experiments included
12 datasets, with the maximum number of training instances c. 21 500
(’Tmc2007’). Based on nine bipartition-based quality metrics, the proposed
technique, balanced clustering-based hierarchy of multi-label classifiers
(HOMER, [48]), and the random forest of predictive clustering trees (RF-PCT,
[49]) provided the best performances. However, for the four ranking-based
metrics, the two stage architecture (TSA, [92]) and the BR method from [1]
showed slightly better performances, compared to the RF-PCT and ML-Forest
methods. Concerning the training time, RF-PCT (with the number of models fixed
to 50) was the fastest among the best performers.

Two variants of a label selection strategy to obtain balanced label subsets in
ensemble learning were developed in [47], using SVM with the RBF kernel as the
base classifier with a one-versus-all multi-class classification strategy. The
extensive experiments and the related comparison with other methods were based
on 30 datasets with at most c. 44 000 examples (’Mediamill’) and even almost
13 000 features (’EukaryoteGo’). The proposed two algorithms were compared
with altogether 12 other MLC-related methods using five repetitions of ten-
fold CV with four quality criteria: label-based accuracy (1-Hamming loss),
example-based F-measure, and label-based macro/micro F-measures. As
conclusions, all methods performed equally and satisfactorily with respect to
the accuracy, but the proposed methods outperformed the traditional PT methods
providing similar quality than the state-of-the-art ensemble methods for the
example- and label-based F-measures. Interestingly, a couple of datasets (’CS’
and ’Chess’ with only binary features) were encountered where none of the
methods provided satisfactory results. Moreover, it was also concluded that
the micro F-measure is more stable than the Macro F-measure to evaluate and
compare different methods.

While introducing and experimenting with the label-specific FS method [71], a
comparison with 16 benchmark datasets and seven other reference methods, based
on Hamming loss, one-error, ranking loss, average precision, and macro-
averaging AUC quality metrics, was provided. The compared estimates and their
variability were computed using a five-fold CV. The experiments were concluded
in favor of the proposed WRAP (WRAPping multi-label classification with label-
specific features generation) approach.

A recent very thorough comparison of 26 methods using 42 benchmark datasets
was reported in [3]. The predictive performance of the methods was assessed
using 20 evaluation metrics. The comparison concluded that the tree-based
ensembles based on random forests, especially the RF-PCT and RFDTBR (Binary
Relevance with Random Forest of Decision Trees) problem transformation method,
were always among the best-performing strategies. The difficulty of nominating
one best method based on multiple evaluation criteria and perspectives was
emphasized. Such a conclusion is also typically given in FS reviews [62].

The most recent experiments were reported in [58], where an approach (MLDE)
for a dynamic selection and combination of base classifiers of an ensemble,
through assessing both accuracy and ranking loss of the generated ones on-the-
fly, was proposed. The presented comparison was based on 24 datasets (all from
http://www.uco.es/kdis/mllresources/) and it used 9 other baseline methods:
RAKEL [1], ML-kNN [30], ECC [43], ACkELo [47], MLWSE [59], LF-LELC [93], ELIFT
[94], BOOMER [95], and DECC [96]. Logistic regression, decision tree, Bayes
network, and SVM were used as the base classifiers and accuracy, F1-measure,
Hamming loss, one error, and average precision as the quality metrics. Based
on five times repeated 2/3-1/3 division of data into training and test sets,
it was concluded that the proposed method MLDE always performed as one of the
best.

##  3 Methodological background

##### Problem and notation

We are interested in MLC tasks, which correspond to supervised learning
problems where inputs can be associated with multiple class labels. Formally,
we are given a dataset
$\mathcal{D}=\\{(\mathbf{x}_{i},\mathbf{y}_{i})\\}_{i=1}^{N}$ of input-output
pairs $(\mathbf{x}_{i},\mathbf{y}_{i})\in\mathbb{R}^{M}\times\mathbb{Y}$
representing i.i.d. samples from an unknown joint distribution
$p^{\star}(\mathbf{x},\mathbf{y})$. The set $\mathbb{Y}$ denotes the universe
of all possible multilabel assignments, which we denote as
$\mathbb{Y}=\\{0,1\\}^{L}$ — $L$ is the total number of classes, and the
$c$-th component of an output $\mathbf{y}$ is set to 1 if the corresponding
example belongs to class $c$ and $0$ otherwise. We want to find a
mapping/model $h:\mathbb{R}^{M}\rightarrow\mathbb{Y}$ such that
$h(\mathbf{x})=\mathbf{y}$ with high probability for any
$(\mathbf{x},\mathbf{y})\sim p^{\star}$.

##### Minimal learning machine

Minimal learning machine (MLM, [27]) is a supervised method whose training
consists of fitting a multiresponse linear regression model between distances
computed in the input and output spaces. Predictions for new incoming inputs
are achieved by estimating distances using the underlying linear model,
followed by a search procedure in the space of possible outputs.

Formally, let $\mathcal{X}=\\{\mathbf{x}_{i}\\}_{i=1}^{N}$ be a set of input
vectors $\mathbf{x}_{i}\in\mathbb{R}^{M}$ and
$\mathcal{Y}=\\{\mathbf{y}_{i}\\}_{i=1}^{N}$ their corresponding outputs
$\mathbf{y}_{i}$. Also, let
$\mathcal{R}=\\{\mathbf{r}_{i}\\}_{i=1}^{K}\subset\mathcal{X}$ be a $K$-length
subset of $\mathcal{X}$ with corresponding outputs
$\mathcal{T}=\\{\mathbf{t}_{i}\\}_{i=1}^{K}\subset\mathcal{Y}$. The prediction
$\hat{\mathbf{y}}$ for an input $\mathbf{x}$ obtained from a MLM with
parameters $\mathbf{B}\in\mathbb{R}^{K\times K}$ is given by

$\displaystyle\hat{\mathbf{y}}=h(\mathbf{x})=\operatorname*{argmin}_{\mathbf{y}\in\mathbb{Y}}\left\\{J(\mathbf{y})=\sum_{k=1}^{K}\left[\|\mathbf{y}-\mathbf{t}_{k}\|^{2}-\left(\sum_{i=1}^{K}B_{i,k}\|\mathbf{x}-\mathbf{r}_{i}\|\right)^{2}\right]^{2}\right\\}.$
(1)

The term $\sum_{i=1}^{K}B_{i,k}\|\mathbf{x}-\mathbf{r}_{i}\|$ corresponds to
the estimate of the distance between $\mathbf{y}$ and $\mathbf{t}_{k}$ — we
also denote it by $\hat{\delta}_{k}$. Notably, Equation 1 can be viewed as a
multilateration problem — finding the coordinates of a query point from
distance estimates to fixed (anchor) points.

Before solving the optimization problem described in Equation 1, we need to
determine the parameters $\mathbf{B}$. Let us define
${\mathbf{D_{x}}}\in\mathbb{R}^{N\times K}$ as the pairwise euclidean distance
matrix between $\mathcal{X}$ and $\mathcal{R}$, i.e.,
$D_{ij}=\|\mathbf{x}_{i}-\mathbf{r}_{j}\|$. Similarly,
${\mathbf{D_{y}}}\in\mathbb{R}^{N\times K}$ denotes the pairwise distance
matrix between $\mathcal{Y}$ and $\mathcal{T}$. In its original formulation,
MLM adopts
$\hat{\mathbf{B}}=({\mathbf{D_{x}}}^{T}{\mathbf{D_{x}}})^{-1}{\mathbf{D_{x}}}^{T}{\mathbf{D_{y}}}$,
which corresponds to the ordinary least-square solution for a linear model
between input and output distances.

For SLC tasks where classes are balanced, [82] shows that the minimization in
Equation 1 is equivalent to selecting the nearest output reference point (or
class label) approximated with the distance regression model, i.e., we can
simply compute

$\displaystyle\hat{\mathbf{y}}=\mathbf{t}_{k^{\star}}\quad\text{ with }\quad
k^{\star}=\operatorname*{argmin}_{k=1,\dots,K}\left\\{\hat{\delta}_{k}=\sum_{i=1}^{K}\hat{B}_{i,k}\|\mathbf{x}-\mathbf{r}_{i}\|\right\\}.$
(2)

This strategy was called nearest neighbor MLM (NN-MLM), which was proposed for
multi-label settings in [33]. In this regard, Proposition 1 shows that this
nearest neighbor procedure does not yield optimal solutions for MLC for
general values of $\hat{\delta}_{k}$. However, the NN-MLM does correspond to
the solution of the multilateration problem in Equation 1 when estimates of
the output distance are accurate. This explains the high predictive
performance of the NN-MLM for MLC reported in [33]. We provide a proof in
Appendix A.

######  Proposition 1 (Nearest neighbor MLM for multi-label learning).

Let $L\geq 2$ denote the number of classes in a MLC problem with
$\mathbb{Y}=\\{0,1\\}^{L}$. Also, assume that the set of output reference
points $\mathcal{T}$ contain all possible multi-label assignments. Then, the
following holds:

  1. 1.

For arbitrary values of $\hat{\delta}_{k}$, NN-MLM does not always yield
optimal solutions to the optimization problem in Equation 1.

  2. 2.

If $\hat{\delta}_{k}=\|\mathbf{y}^{\prime}-\mathbf{t}_{k}\|$ for some
$\mathbf{y}^{\prime}\in\mathbb{Y}$, then NN-MLM returns an optimal solution to
the minimization in Equation 1.

##  4 Multi-label minimal learning machine

In practice, meeting the requirements that ensure optimality of the NN
procedure (Proposition 1) is often hard. In addition, the greedy nearest label
choice limits the usage of the NN-MLM only for a seen set of labels, i.e.,
predictions are limited to those cases which have been observed during
training. Thus, here we take an alternative choice and leverage the full set
of labels, going from $1$-NN to $N$-NN. To do so, we need to define a way to
combine the labels. In summary, our solution relies on computing a convex
combination where importance weights are given as a function of distances in
the label space (estimated using the values $\hat{\delta}$’s). Motivated by
the success of nearest neighbors in multi-label settings [33], we target at
weighting schemes where the first nearest neighbor should have higher
importance than the second one, and so on.

A natural way to implement this is via IDW [28]. This scheme allows us to
control the weighting of the convex combination of label sets with a single
parameter. the power parameter. In the following, we formulate this idea and
introduce the ML-MLM (multi-label MLM) — a new distance-based method for MLC
which combines the distance regression step from the standard MLM with IDW.

###  4.1 Formulation

Similarly to MLMs, the ML-MLM assumes the existence of a linear mapping
between distances computed from the input and output/label data spaces. Under
the least-square criterion, we can obtain a closed-form estimate of the linear
coefficients. Consider the sets $\mathcal{X}$, $\mathcal{Y}$, $\mathcal{R}$,
and $\mathcal{T}$ as in the original MLM, except for the fact that
$\mathcal{T}=\mathcal{Y}$ — all observed targets are also output reference
points. Also, let ${\mathbf{D_{x}}}\in\mathbb{R}_{+}^{N\times K}$ be the
pairwise $\ell_{2}$-distance matrix between the $\mathcal{X}$ and
$\mathcal{R}$, whereas ${\mathbf{D_{y}}}\in\mathbb{R}_{+}^{N\times N}$ is the
distance matrix between the elements of $\mathcal{Y}$. The training of ML-MLM
consists of simply computing
$\hat{\mathbf{B}}=({\mathbf{D_{x}}}^{T}{\mathbf{D_{x}}})^{-1}{\mathbf{D_{x}}}^{T}{\mathbf{D_{y}}}$,
where $\hat{\mathbf{B}}\in\mathbb{R}^{K\times N}$ denotes the model
parameters.

To obtain a multi-label prediction for a new input $\mathbf{x}$, ML-MLM first
applies the distance regression model to get the distance estimates
$\hat{\bm{\delta}}=[\hat{\delta}_{1},\cdots,\hat{\delta}_{N}]$ with respect to
the observed set of multi-label targets $\mathcal{Y}$, i.e.,

$\hat{\bm{\delta}}=\left[\left\|\mathbf{x}-\mathbf{r}_{1}\right\|_{2},\cdots,\left\|\mathbf{x}-\mathbf{r}_{K}\right\|_{2}\right]\hat{\mathbf{B}},$
(3)

where $\mathbf{r}_{i}$ denotes the $i$-th element of $\mathcal{R}$. We then
use these distance estimates to define the importance weight [28] for each
target in $\mathcal{Y}$, and compute a weighted average over the observed
multi-label targets:

$\displaystyle\bar{\mathbf{y}}=\frac{1}{Z}\sum_{i=1}^{N}w_{P}(\hat{\delta}_{i})\mathbf{y}_{i},\quad\text{
with }\quad
w_{P}(\hat{\delta}_{i})=\begin{cases}\hat{\delta}_{i}^{-P},&\text{if
}\hat{\delta}_{i}>0,\\\ 1,&\text{if }\hat{\delta}_{i}=0,\end{cases}$ (4)

where $Z=\sum_{i=1}^{N}w_{P}(\hat{\delta}_{i})$ and $0<P\in\mathbb{R}$ is a
hyper-parameter. Notably, the variable $P$ controls how fast the importance
weight decays with the distance $\hat{\delta}_{i}$. Finally, we achieve the
multi-label prediction
$\hat{\mathbf{y}}=[\hat{y}_{1},\ldots,\hat{y}_{L}]\in\\{0,1\\}^{L}$ by
thresholding the values of $\bar{\mathbf{y}}$:

$\displaystyle\hat{y}_{c}=\mathbbm{1}[\bar{y}_{c}>t]\quad\quad\forall
c=1,\dots,L,$ (5)

where $\mathbbm{1}[\cdot]$ denotes the indicator function that returns 1 if
its argument is true and 0 otherwise, and $t$ is a hyper-parameter. Algorithms
1 and 2 summarize the ML-MLM’s training and prediction procedures. In Figure
1, Algorithm 2’s prediction workflow is illustrated with a toy dataset.

Algorithm 1 Distance regression (training)

1:Input data $\mathcal{X}$, output labels $\mathcal{Y}$, input space reference
points $\mathcal{R}$

2:Distance regression model $\mathbf{\hat{B}}$

3:${\mathbf{D_{x}}}\leftarrow$ compute $N\times K$ input space distance matrix
between $\mathcal{X}$ and $\mathcal{R}$

4:${\mathbf{D_{y}}}\leftarrow$ compute $N\times N$ distance matrix for
$\mathcal{Y}$

5:$\hat{\mathbf{B}}\leftarrow$ solve
$({\mathbf{D_{x}}}^{T}{\mathbf{D_{x}}})^{-1}{\mathbf{D_{x}}}^{T}{\mathbf{D_{y}}}$

Algorithm 2 ML-MLM prediction

1:Input vector $\mathbf{x}^{*}$, distance regression model $\mathbf{\hat{B}}$,
reference points $\mathcal{R}$, output labels $\mathcal{Y}$, power parameter
$P$, classification threshold $t$

2:label vector $\mathbf{y}^{*}$

3:$\mathbf{d}\leftarrow$
$[~{}\|\mathbf{x}^{*}-\mathbf{r}_{1}\|,...,\|\mathbf{x}^{*}-\mathbf{r}_{K}\|~{}]$
// Compute input space distances

4:$\bm{\hat{\delta}}\leftarrow$ $\mathbf{d}\mathbf{\hat{B}}$ // Predict output
space distances

5:$\bar{\mathbf{y}}\leftarrow\sum_{i}w_{P}(\hat{\delta}_{i})\mathbf{y}_{i}/Z$
// Compute label scores (Eq. 4)

6:$\mathbf{y^{*}}\leftarrow$ $\mathbbm{1}[\bar{\mathbf{y}}>t]$ // Threshold
relevant labels

Figure 1: The main components of the ML-MLM ’s prediction in action are
illustrated for a model trained on a toy dataset. The dataset consists of four
instances associated with four unique label sets. A distance regression model
$\mathbf{B}$ has been trained with four input space reference points
$\\{\mathbf{r}_{i}\\}_{i=1}^{4}$ with corresponding label space vectors
$\\{\mathbf{y}_{i}\\}_{i=1}^{4}$ (treated as output space reference points
regarding the MLM context). The IDW weighting is computed with $P=2$. The
sample images here were created by Stable Diffusion.

###  4.2 Model selection

We now discuss how we tune the hyper-parameters $P$ (power) and $t$ (global
class threshold). Regarding the selection of $P$, we employ a broadly used
evaluation metric for multi-label problems: Ranking Loss [2]. The Ranking Loss
is an appropriate choice for methods that provide label scores as the ML-MLM
since it measures the overall quality of the ranking. We combine this loss
with a CV scheme, or more specifically, leave-one-out CV (LOOCV). Notably, due
to the linear nature of the ML-MLM distance regression step, we can leverage
the prediction sum of squares (PRESS) statistic [97] to compute the LOO error
in a closed form. As a result, we only need to run the MLM’s training
algorithm once.

In Algorithm 1, the coefficient matrix $\mathbf{\hat{B}}$ can be solved with
the Moore-Penrose pseudoinverse. For
$\mathbf{U}={\mathbf{D_{x}}}^{T}{\mathbf{D_{x}}}+\alpha\mathbf{I}$, we have
$\mathbf{\hat{B}}=\mathbf{U}^{\dagger}{\mathbf{D_{x}}}^{T}{\mathbf{D_{y}}}$.
For each training set observation $i\in\\{1,...,N\\}$, we can determine the
corresponding out-of-sample distance prediction
$\mathbf{\hat{\bm{\delta}}}_{i}^{LOO}$ as

$\mathbf{\hat{\bm{\delta}}}_{i}^{LOO}=\frac{\hat{\mathbf{D}}_{\mathbf{y}(i,:)}-\mathbf{H}_{(i,i)}\mathbf{D}_{\mathbf{y}(i,:)}}{1-\mathbf{H}_{(i,i)}},$
(6)

where a hat matrix
$\mathbf{H}={\mathbf{D_{x}}}\mathbf{U}^{\dagger}{\mathbf{D_{x}}}^{T}$ and
$\hat{\mathbf{D}}_{\mathbf{y}}=\mathbf{H}{{\mathbf{D_{y}}}}$. Therefore, the
LOOCV Ranking Loss (LRL) statistic for ML-MLM is given by

$\textsc{LRL}=\frac{1}{N}\sum_{i=1}^{N}\frac{|\\{(j,k)~{}|~{}\bar{\mathbf{y}}_{i(j)}<\bar{\mathbf{y}}_{i(k)},~{}j\in
g_{i}^{+},~{}k\in g_{i}^{0}\\}|}{|g_{i}^{+}||g_{i}^{0}|},$ (7)

where
$\bar{\mathbf{y}}_{i}=\sum_{i}w_{P}(\mathbf{\hat{\bm{\delta}}}_{i}^{LOO})\mathbf{y}_{i}/Z$
is a score vector determined by a power parameter value and an out-of-sample
distance prediction, $g_{i}^{+}=\\{j:\mathbf{g}_{i(j)}=1\\}$ is a set of label
indices referring to relevant ground truth labels for an instance $i$, and,
correspondingly, $g_{i}^{0}=\\{j:\mathbf{g}_{i(j)}=0\\}$ is a set of label
indices referring to irrelevant ground ground truth labels for an instance
$i$. Hence, the objective of ML-MLM training is to find a
$P^{*}=\operatorname*{argmin}_{P}\textsc{LRL}$. The exploitation of Allen’s
PRESS formulation in ML-MLM differs from a conventional use case where the
mean squared error calculation for each hyper-parameter value requires solving
the least-squares problem each time again [98, 99]. In the ML-MLM training,
the least-squares problem has to be solved only once for tuning the hyper-
parameter. This difference is even more significant if we use a naive LOOCV
implementation where the least-squares problem is solved $N$ times for each
hyper-parameter value.

Thresholding for the MLC models can be performed generally with label-wise or
global thresholding. In [100], the authors concluded that there is no
significant difference between the multiple and single thresholding
approaches. The global threshold can be selected in an intuitive way by
matching prediction’s label cardinality [1] to a ground truth label
cardinality.

After finding $P^{*}$, thresholding $t$ can be tuned for
${{\mathcal{Y}}_{t}}=\mathbbm{1}[\bar{\mathcal{Y}}>t]$, where
$\bar{\mathcal{Y}}=\\{\bar{\mathbf{y}}_{i}\\}_{i=1}^{N}$ so that

$\textsc{Card}({\mathcal{Y}_{t}})=\textsc{Card}(\mathcal{Y}),$ (8)

where $\textsc{Card}(\cdot)$ computes label cardinality (see Eq. (9) for the
Card measure) for a given set of label vectors.

##  5 Experiments and Results

In this section, we center on comparing the proposed method (ML-MLM), three
other distance regression-based (DRB) methods, and five reference methods with
ten benchmark datasets. Implementations for the new methods are available in
https://github.com/jookriha/ml-mlm. In our experiments, we focus on comparing
the proposed method to a state-of-the-art method, RF-PCT, which was concluded
to belong among the best performers in the extensive comparison by
Bogatinovski et al. [3] (see Section 2). Regarding the DRB methods, we are
especially interested in comparing ML-MLM and LLS-MLM. In addition, we analyze
the uncertainty of the proposal’s prediction and its time complexity. In
Section 5.1, the experimental setup is described. In Section 5.2, experimental
comparison results with four ranking-based and four bipartition-based
evaluations are given. In Section 5.3, we demonstrate how the prediction’s
uncertainty can be assessed. Finally, in Section 5.4 we analyze and compare
the computational costs.

###  5.1 Experimental Setup

In MLC, datasets are often characterized with the label cardinality and label
density metrics [1], which summarize how many labels are relevant per instance
on average. The label cardinality is defined as

$\textsc{Card}=\frac{1}{N}\sum_{i=1}^{N}\mathbf{1}^{T}\mathbf{y}_{i},$ (9)

where $\mathbf{1}\in\\{1\\}^{L}$. The label density is given by

$\textsc{Dens}=\frac{1}{N}\sum_{i=1}^{N}\frac{\mathbf{1}^{T}\mathbf{y}_{i}}{L}.$
(10)

Datasets used in the experiments are summarized in Table 1, where the Card and
Dens metrics have been computed for the union of training and test set label
vectors. In addition to these metrics and common data characteristics, we
computed the number of unique label vectors for the union of the training and
test sets, denoted as $L_{u}$, and, the number of distinct combinations of
labels (#novel label vectors) in the test set, denoted as $L_{n}$. All the
datasets are available in http://mulan.sourceforge.net/datasets-mlc.html (the
Mulan repository).

The relevant background to follow and understand the empirical work in
relation to MLC problems is to select and understand the quality metrics that
are used in evaluating and comparing different methods. Clearly, the solution
of an MLC problem itself is of multi-criteria nature because the simplest
model, which is the fastest to train and provides the best performance by
means of all possible metrics, should be obtained. This landscape was
thoroughly evaluated in [101], and the most relevant metrics used in our and
others’ experiments are summarized in Appendix B. Implementations for the
metrics are available in https://github.com/jookriha/ml-mlm.

Since we compare our results to the ones given in [26], the selected datasets
are the same, with the expectation that we excluded the Bookmarks dataset,
since some of the reference results for it were missing. Moreover, for this
dataset, training BR-MLM with nearly a full set of reference points would have
been very expensive. Note that the Scene dataset is close to being a single-
label classification problem since the label cardinality is $1.074$.
Therefore, its relevance for MLC comparisons is somewhat questionable.

For the comparison, we computed the results for the following four DRB
methods:

  * •

BR-MLM uses cubic equations MLM (C-MLM) [82] as a base model for the BR
approach. In C-MLM, a closed-form solution for a label-wise multilateration
problem is used. Each C-MLM model outputs directly a real-valued score for
label ranking and classification. Since we use the local RCut thresholding,
this method does not require hyperparameter tuning. Integration of these three
elements is proposed in this paper.

  * •

LLS-MLM solves the MLM’s multilateration problem via the localization linear
system (LLS) [32] approach, where predicted distances, benchmark anchor node
(BAN), and output space reference points (all but not BAN) construct a linear
system of equations. A solution to the linear system of equations with BAN
transition outputs real-valued scores for all labels. These scores are
directly used for label ranking and classification. We used the corresponding
reference point to the smallest predicted distance as a BAN. Since we also use
the local RCut thresholding for this method, hyper-parameter tuning is not
needed. Integration of these three elements is proposed in this paper.

  * •

ML-MLM  is the main proposal of this paper. The method uses the IDW [28]
approach to form a convex combination of the set of training label vectors.
The two hyper-parameters, power parameter and global thresholding, can be
selected straightforwardly. The out-of-sample distance predictions can be
solved from closed-form solutions based on the ideas from the PRESS statistic
[97]. These predictions from the closed-form solution enable a one-shot
training process using the LRL statistic for selecting both the power
parameter and the label cardinality-based global thresholding parameter.

  * •

NN-MLM predicts a set of labels directly given by the corresponding reference
point to the smallest predicted distance. This method was proposed in [33].
Note that this method is a direct adaptation of the original NN-MLM [82] to
multi-label settings. Therefore, we will refer to it here with the same name
as in the SL domain. The main difference is that for NN-MLM in MLC, there are
no theoretical guarantees in solving the multilateration problem optimally
(Proposition 1).

For all these four DRB methods, we use the same set of input space reference
points $\mathbf{R}$. We selected all the unique training instances as
reference points $\mathbf{R}$. We kept the full set of output reference points
since the singularity issues concern only the inverse of the matrix
${\mathbf{D_{x}}}^{T}{\mathbf{D_{x}}}$. In 6, we fixed the $\alpha$ parameter
as the lower 1000-quantile of the pair-wise input space reference point
distances and with an exclusion of a reference point’s distance to itself (all
the pair-wise distances are non-zero). We observed that this heuristic
improved unique solving of the inverse of
${\mathbf{D_{x}}}^{T}{\mathbf{D_{x}}}$. For LLS-MLM, ML-MLM , and NN-MLM, we
always use the same distance regression model.

In the LLS-MLM prediction algorithm (in [32], see Algorithm 1), we select the
benchmark-anchor-node (BAN) as an output space reference point corresponding
to the smallest predicted distance. We performed an extensive experimental
study regarding the BAN selection. As a result, we observed the proposed
selection strategy outperformed the originally proposed random-based selection
in the MLC problems. Due to this BAN selection, the LLS-MLM prediction is
deterministic in our experiments. Therefore, all four DRB methods used here
are fully deterministic with respect to training and prediction. For the BR-
MLM, we used the C-MLM [82] for each SLC model, since we cannot get a label
scoring/ranking from the nearest neighbor MLM [82] method. For ML-MLM , we
employed the LOOCV Ranking Loss statistic to tune the power parameter. Our
preliminary exploration of Ranking Loss values as a function of the power
parameter revealed the largest rate of change for lower-end values.
Consequently, we searched for the power parameter value from the base of two
$2^{s}$ values, where $s={0,0.1,0.2,...,8}$.

For the BR-MLM and LLS-MLM methods, we observed that classification results
were suboptimal with a fixed $0.5$ thresholding. Therefore, we proposed a new
thresholding approach which we refer as ‘local rank cut’ (local RCut), where
labels corresponding to $K_{cut}$ highest scores are labelled as relevant.
Differently from the Rcut thresholding [100], in local RCut, $K_{cut}$ value
is given by the cardinality of the NN-MLM model’s predicted set of labels. For
the BR-MLM and LLS-MLM methods, we omitted the label cardinality-based
thresholding, since it would increase the training complexity significantly
for these methods. The local RCut does not require any hyper-parameter tuning
in the training for the BR-MLM and LLS-MLM methods.

For ML-MLM , we used the label cardinality-based global thresholding, as
described in Section 4.2. For ML-MLM , available out-of-sample distance
predictions can be straightforwardly exploited for cardinality-based
thresholding. Moreover, ranking performance for the Ranking Loss and Coverage
metrics indicated that ML-MLM ’s thresholding should be tuned so that it aims
to retrieve labels from deeper in the ranking than BR-MLM and LLS-MLM. We
experimentally compared the label-cardinalities for the predicted set of
labels between the cardinality-based and local RCut thresholding approaches
with ML-MLM and observed that an average predicted label-cardinality was lower
for the local RCut thresholding. Hence, local RCut is a more conservative
approach than cardinality-based thresholding.

As recommended in [26], we compare our methods to BR [1, 102], CC [43, 103],
HOMER [104], and RF-PCT [29]. Note that the RF-PCT method was identified as
one the best-performing methods in both the studies [26, 3]. In addition, we
included the ML-kNN [30] method also for the comparison, because it belongs to
the same group as the proposed method in the MLC method taxonomy [1, 3].

Results for BR, CC, and HOMER were produced with SVM as a base model [26]. The
CC method builds on using the BR model predictions to extend feature space
with a chaining structure. In this chaining structure, a BR model is trained
to predict a target label with a full set of features and a subset of
predicted labels (at least the target label is excluded). The HOMER method is
based on using a label power set type of construction with a hierarchical
structure of the label space. In the structure, a set of binary classifiers
are trained with the divide-and-conquer paradigm to predict meta labels (a
label power set of a subset of labels). In the training phase, the
hierarchical structure of the labels is obtained via balanced k-means
clustering. The RF-PCT method uses a decision tree with a hierarchical
clustering structure as a base classifier for the Random Forests (RF) ensemble
approach. In RF, the ensemble is constructed by randomizing the learning
process both on an observation and feature direction with bootstrapping and
random feature selection, correspondingly. The clustering structure of RF-PCT
is obtained by maximizing variance reduction in a top-to-bottom direction.

We used the given train-test splits for the datasets in order to compare our
results to the results given in [26]. In statistical testing, we used the
Friedman test followed by the Nemeneyi posthoc test (if the null hypothesis
was rejected) [105]. The statistical significance level was set to $0.05$.

Table 1: Characteristics of datasets. On the top row of the table, $N$ is the
number of instances in the training set, $N_{ts}$ is the number of instances
in the test set, $M$ is the number of features, $L$ is the number of labels,
$Q$ is the number of novel labels in the test set, Card is the label
cardinality, Dens is the label density, $L_{u}$ is the number of unique label
vectors, and $L_{n}$ is the number of novel label vectors in the test set.

Dataset $N$ $N_{ts}$ $M$ $L$ $Q$ Card Dens $L_{u}$ $L_{n}$ Medical 333 645
1449 45 7 1.245 0.028 94 54 Emotions 391 202 72 6 0 1.869 0.311 27 4 Enron
1123 579 1001 53 1 3.378 0.064 753 225 Scene 1211 1196 294 6 0 1.074 0.179 15
1 Yeast 1500 917 103 14 0 4.237 0.303 198 38 Corel5k 4500 500 499 374 3 3.522
0.009 3175 252 Bibtex 4880 2515 1836 159 0 2.402 0.015 2856 836 Delicious
12920 3185 500 983 0 19.020 0.019 15806 3095 Tmc2007 21519 7077 500 22 0 2.220
0.101 1172 0 Mediamill 30993 12914 120 101 0 4.376 0.043 6555 2223

###  5.2 Results

In this section, we show experimental results for comparison. We analyze
results for the ranking-based and bipartition-based metrics separately.
Detailed results for each method, dataset and evaluation metric are given in
eight tables, in Appendix D and Appendix E, for the ranking-based and
bipartition-based results, correspondingly. The results from these tables are
visualized with Nemeneyi diagrams in Figures 2 and 3.

####  5.2.1 Ranking-based metrics

(a) Ranking Loss

(b) Coverage

(c) One Error

(d) Average Precision

Figure 2: Results for ranking-based metrics.

For all four ranking-based metrics, the Friedman null hypothesis was rejected
with a clear margin. Therefore, we conducted the Nemenyi posthoc tests for all
four result tables (Tables 3-6 in Appendix D). Statistical testing results for
these tests are presented in Figure 2 with the Nemenyi diagram, where the
horizontal axis represents the average rank of a method for a given metric. A
smaller rank refers to better performance. A horizontal connection line on top
of the axis indicates which methods do not have statistically significant
difference according to the Nemenyi post-hoc test.

In Figures 2(c) and 2(d), we can see that ML-MLM have the highest average
ranks for the Ranking Loss and Coverage metrics and the differences to ML-kNN
and HOMER are statistically significant. In addition, there is a statistically
significant difference between the ML-MLM and LLS-MLM regarding Coverage. For
the One Error and Average Precision, BR-MLM has the highest ranks. For these
metrics, BR-MLM and ML-MLM are both in the first group, thus having no
statistically significant differences. Also for these two ranking-based
metrics, ML-MLM differs statistically from the ML-kNN and HOMER.

From Tables 3 \- 6 and the data characteristics Table 1, a few observations
can be made. All the DRB methods have nearly perfect scores for all the
ranking-based metrics for the Tmc2007 dataset. In Table 1, this dataset has
$L_{n}=0$, meaning that all the label vectors in the test set were presented
in the training set. Furthermore, consider the top four datasets with the
lowest ratio $L_{n}/N_{ts}$: Tmc2007 (0), Scene (0.001), Emotions (0.020), and
Yeast (0.041). For these datasets, ML-MLM outperforms the state-of-the-art
method RF-PCT for all the ranking-based metrics. This trend can also be
observed in the upper end of the $L_{n}/N_{ts}$ ratios. For example, RF-PCT
has better ranking performance than ML-MLM for the Delicious (0.972) and Enron
(0.389) datasets.

According to the results, ML-MLM ’s performance is the strongest for Coverage.
Based on solely the average ranks, an average rank difference between ML-MLM
and RF-PCT is largest for Coverage. Good performance regarding this metric
indicates that if thresholding for ML-MLM is properly set, it should give an
edge for ML-MLM in the bipartition-based comparison at least for the Accuracy
metric.

In summary, for the ranking-based metrics, there are no statistically
significant differences between ML-MLM and RF-PCT. Although, ML-MLM has a
better average rank than RF-PCT for each of the metrics.

####  5.2.2 Bipartition-based metrics

The Friedman null-hypothesis tests were also rejected with clear margins for
all the bipartition-based results. Hence, similarly to Section 5.2.1, the
Nemenyi posthoc test procedure was performed for Tables 7-10. The results of
these tests are again summarized with the critical diagram visualizations
given in Figure 3. Note that differently from Section 5.2.1, we now have
included NN-MLM in this comparison, so we have nine methods in total, compared
to eight in the previous one. Critical distance is therefore slightly larger
in statistical testing regarding this section.

According to Figure 3, ML-MLM has the best average rank for the Accuracy,
Micro F1, and Macro F1 metrics. Moreover, a ranking difference between ML-MLM
and RF-PCT is statistically significant for all these three metrics. For
Hamming Loss, BR-MLM has the best performance, and, it is statistically
significant with respect to HOMER and ML-KNN. Although ML-MLM has a worse
average rank for Hamming Loss than BR-MLM and RF-PCT, this difference is not
statistically significant. Note that there are no statistically significant
differences between the DRB methods. Moreover, ML-MLM and HOMER do not differ
statistically in any of the metrics.

As expected, based on the high Coverage-performance, ML-MLM performs best in
Accuracy compared to the other methods. A statistical interpretation between
ML-MLM and a group of methods RF-PCT, CC, ML-kNN, and BR, is the same for
Accuracy and Micro. However, if we solely inspect the average rank differences
between this group and ML-MLM , regarding Accuracy these differences are
larger. Moreover, from Figure 3(a) and Figure 3(c), we can see that ML-MLM
have the highest Accuracy value for six out of ten datasets and the highest
Micro F1 value for seven out of ten datasets. The results for label-wise
bipartition-based metrics, Micro F1 and Macro F1, show that the predicted set
of labels outputted by ML-MLM is accurate and well-balanced for all labels.

A minor drawback of ML-MLM is the performance regarding Hamming Loss, for
which the average rank is worse compared to all the other DRB methods, BR, and
RF-PCT. Since ML-MLM performs better in Accuracy and worse in Hamming Loss, it
might be greedier than the other methods when choosing the labels, which rises
the number of false positives. However, since the average rank is not
statistically different from the higher-performing methods and it is smaller
compared to CC, ML-KNN, and HOMER, we argue that this trade-off is reasonable.
Note that even the Hamming Loss’s absolute values are small for all the
experimented methods in many of the datasets. This is mostly due to the
normalization with the number of all possible labels.

Overall, the results show that ML-MLM is statistically better than the state-
of-the-art method RF-PCT for three out of four bipartition-based metrics and
it is statistically equal for the Hamming Loss. All the DRB methods perform
well in the comparison, and also the simplest method (NN-MLM), which is
statistically equal in three metrics and better in one metric than RF-PCT.

(a) Accuracy

(b) Hamming Loss

(c) Micro F1

(d) Macro F1

Figure 3: Results for bipartition-based metrics.

###  5.3 Assessing uncertainty and interpreting ML-MLM

Understanding of how ML-MLM predicts can be interpreted via the selected power
parameter values and predicted distances. These results are summarized in
Table 2, where the distance corresponding to the predicted nearest neighbor is
squared and averaged over the test set for each dataset. We squared the
predicted distance in Table 2 for better interpretability of the label
differences (see Appendix C for more details). In Figure 4, the distributions
of the predicted distances (without squaring) are presented with box plots.

From Table 2, we can see that the selected power parameter values vary
significantly between the datasets. The smallest value was set for the Scene
dataset ($P=4$), while the largest value was set for the Medical dataset
($P\approx 222.9$). In the latter, ML-MLM is predicting the set of labels
highly similar to NN-MLM, since almost all the weight is given to the
predicted nearest neighbor. We verified this for Medical by comparing
bipartition-based metric results between NN-MLM and ML-MLM with the local RCut
thresholding. The results for this comparison were identical. The results
regarding Medical and the ML-MLM and NN-MLM methods in Tables 7-10 are
different due to ML-MLM ’s using the cardinality-based thresholding (Eq. 8)
instead of the local RCut thresholding. For the Medical dataset, NN-MLM gives
better results for three out of four metrics, which indicates that the
cardinality-based thresholding could be suboptimal for large power parameter
values.

From Table 2 and the dataset characteristics (Table 1), we can notice that ML-
MLM may select large power parameter values for highly different types of
datasets, such as Bibtex ($P=128$) and Tmc2007 ($P=59.7$). However, if we
combine information from the predicted distances and the power parameter
values, we can interpret for Tmc2007 that ML-MLM does not benefit much from
increasing the contribution of other reference points in the convex
combination, since the nearest predicted neighbor already contains a
significant amount the information for a nearly optimal prediction. Since both
the predicted distances and the power parameter are large for Bibtex, the ML-
MLM is mostly extrapolating and does not benefit much from combining label
information from multiple reference points.

Regarding the predicted distances in Table 2 and the overall ranking (Tables 3
\- 6) and classification (Tables 7 \- 10) results of ML-MLM , we can summarize
the following. For a given instance, the predicted distance can be used
directly as an uncertainty estimate of how reliable the ranking or
classification is. Higher distances reflect that the instance is probably far
away from data and the model is extrapolating. Thus, the prediction is
probably unreliable. In this way, predictions could be straightforwardly
categorized in different uncertainty categories (e.g., low: $distance<1$,
medium: $1<distance<\sqrt{2}$, high: $distance>\sqrt{2}$) based on the
predicted distance(s). Moreover, for a given dataset, we could use the squared
predicted distance to characterize the difficulty of the ML problem in an
intuitive way.

Table 2: Selected power parameter $P$ values and average minimum predicted
squared Euclidean distances for ML-MLM .

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill P $2^{7.8}$ $2^{2.9}$ $2^{3.8}$ $2^{2}$ $2^{3.2}$ $2^{4.1}$ $2^{7}$
$2^{4.2}$ $2^{5.9}$ $2^{4.4}$ $\approx 222.9$ $\approx 7.5$ $\approx 13.9$
$\approx 4$ $\approx 9.2$ $\approx 17.1$ $\approx 128$ $\approx 18.4$ $\approx
59.7$ $\approx 21.1$ Distance $0.6\pm 0.4$ $0.8\pm 0.4$ $1.7\pm 1.1$ $0.3\pm
0.3$ $2.1\pm 0.9$ $3.7\pm 0.5$ $1.9\pm 0.9$ $16.6\pm 5.4$ $0.2\pm 0.2$ $2.4\pm
1.1$

Figure 4: Distance regression prediction’s minimum distances for the test
sets. Predicted distances closer to zero reflect that the distance regression
model is interpolating more. Distance regression model’s overall interpolation
ability is strongest for Tmc2007 and worst for Delicious.

###  5.4 Time complexities of distance regression based methods

Distance regression step with Moore-Penrose pseudoinverse has a
$\mathcal{O}(NK^{2})$ time complexity. Since we are selecting nearly all
distinct points as reference points, the time complexity for LLS-MLM, ML-MLM ,
and NN-MLM is $\mathcal{O}(N^{3})$ for datasets that have $N$ distinct input
instances. With these same assumptions, training time complexity for BR-MLM is
$\mathcal{O}(LN^{3})$, since a distinct Moore-Penrose pseudoinverse is needed
for each label. Therefore, for the DBR methods, the BR-MLM method has the
highest time complexity in training due to the $L$ dependency. From now on, we
will handle the prediction time complexity analysis with the assumption of
distinct input instances, meaning that $K=N$. This assumption corresponds to
the worst-case scenario regarding the time complexity.

The LLS’s linear system can be solved via an OLS solution, which has a cost of
$\mathcal{O}(L^{2}N)$ [32]. Therefore, for a large number of labels, this cost
dominates the overall time complexity, and it has to be considered in MLC
problems. Similar to ML-MLM , LLS predicts label space distances which has a
cost of $\mathcal{O}(N^{2})$. Then, the computational cost for LLS prediction
is $\mathcal{O}(L^{2}N+N^{2})$. Thus, in the MLC context, ML-MLM has a lighter
computational cost than LLS with respect to the number of labels.

For the DBR methods, NN-MLM is the fastest in prediction, because, after the
given distance predictions, the predicted set labels can be searched with
$\mathcal{O}(L_{u})$ cost [82], where $L_{u}$ is the number of distinct label
vectors in the training set. However, due to the distance prediction step, the
overall computational complexity is still $\mathcal{O}(N^{2})$ for the NN-MLM.

Similar to NN-MLM, ML-MLM ’s prediction time complexity is driven by the
distance prediction step. Therefore, ML-MLM ’s time complexity is also
$\mathcal{O}(N^{2})$. A naive implementation of step 2 (Algorithm 2) requires
$\mathcal{O}(KN)$ cost. However, similar to NN-MLM, this can be reduced to
$\mathcal{O}(C_{u}L_{u})$, where $L_{u}$ is the number of unique label vectors
in the training set and $C_{u}$ is the label cardinality of these label
vectors. This label cardinality dependency is due to applying sparse
structures for label vectors. Furthermore, for the MLC problems where label
cardinality is small, this complexity is reduced to $\mathcal{O}(L_{u})$.

Besides training, the BR-MLM method has also the highest computational cost
for prediction. The time complexity for BR-MLM’s prediction is
$\mathcal{O}(L^{2}N)$ because distance predictions are estimated for each
label separately with $L$ models.

As a reminder, note that these training and prediction time complexities can
be significantly alleviated with the clustering-based distance regression
construction [33]. Here, we were interested in comparing the core models’
costs under simplifying assumptions.

##  6 Discussion

All the DRB methods performed well in the bipartition-based metrics
comparison. This result indicates that the selected thresholding approaches
are well-suited for the DRB methods. The proposed thresholding method, local
RCut, gives a straightforward way to set the threshold adaptively during
prediction via the cardinality of the NN-MLM’s prediction. Note that this does
not add complexity to the prediction if local RCut thresholds a DRB model with
the same core distance regression model. We observed that the local RCut
thresholding outperforms the standard fixed $0.5$ thresholding for the DRB
methods. Therefore, we recommend avoiding this fixed thresholding for the DRB
methods. This observation aligns with the results and recommendations
presented in [100]. For improving ML-MLM classification performance for higher
power parameter values, a hybrid approach of the global and local RCut
thresholding could be considered.

The proposed method ML-MLM performed overall better than the other DRB methods
in the comparison based on the average ranks. However, ML-MLM was found
statistically different from other DRB methods only regarding the Coverage
metric. In Section 3, we showed that the NN-MLM method’s prediction does not
guarantee multilateration problem-solving for MLC. However, based on the
highly similar classification results (Figure 3 and Tables 7-10) for the LLS-
MLM and NN-MLM, this simple nearest neighbor based heuristic is very close to
solving the multilateration problem similarly as the more complex LLS
approach. Based on plainly on these results, there seems to be no reason to
use LLS-MLM instead of NN-MLM. However, the main limitation of NN-MLM is that
it is not able to provide the ranking/scoring of the predicted labels,
therefore its usability is limited. In addition, NN-MLM’s predictions are
limited to the training set label vectors. Moreover, although the DRB methods
predict the set of labels via highly different approaches, they all performed
well in the comparison. This indicates that the DRB construction is beneficial
for the MLC problems and that the distance predictions from this can be used
in many ways to end up with a good solution.

Taking into account the ranking and classification performances and
training/prediction time complexities, the most viable option from the DRB
methods is ML-MLM . As pointed out in the previous paragraph, there are clear
benefits of using ML-MLM instead of NN-MLM and BR-MLM. When comparing ML-MLM
to LLS-MLM, ML-MLM improves the ranking performance for the Ranking Loss and
Coverate metrics. Moreover, the prediction phase time complexity of ML-MLM is
linear with respect to the number of labels compared to LLS-MLM’s quadratic
time complexity.

##  7 Conclusion

In this paper, we proposed a simple distance regression-based method for
multi-label learning referred to ML-MLM . The proposed method’s core idea is
to learn label ranking via distance regression and inverse distance weighting.
Besides being one of the simplest methods in the multi-label classification
(MLC) literature, our experimental evaluation showed that it achieves the
state-of-the-art level of multi-label ranking and classification performance
for small to moderate-sized MLC problems. Furthermore, in the classification
performance evaluation, the proposed method outperformed a random forest-based
method, which is considered one of the state-of-the-art methods in the latest
MLC literature. In the ranking performance evaluation, the proposed method
performed equally to the random forest-based method. Moreover, we showed that
the proposed method outperforms the ML-kNN method, which is considered to
belong to the same group as our method in the MLC taxonomy.

Although the proposed method’s training time complexity is independent of the
number of labels, it has a cubic training time complexity with respect to the
number of observations for the basic Cholesky decomposition methods. With the
basic algorithms, it is a bottleneck of the proposed method concerning its
scalability. However, our main goal in this work was to show a proof of
concept that a simple distance regression-based approach can achieve high
accuracy in the MLC problems. Therefore, we omitted reducing the cubic
training time complexity which rises from solving a large-scale ordinary least
squares problem. Moreover, even though the training time is cubic,
sophisticated implementations exist for these problems due to their popularity
and long history. For instance, random approximation and GPU computing-
oriented methods [106, 107] can be used to improve the efficiency of this
step.

In general, the results showed and strengthened previous observations that
exploiting the linear distance mapping between feature and multidimensional
output spaces is beneficial for multi-output learning problems. In this
paper’s formalism, connections between all the distinct points are represented
via these distance mappings. This means that we simplify the learning on a
feature level with dissimilarity, but explore the whole dissimilarity
structure of data for prediction. In other words, we assume that features are
equally important, but holding on the possibility that every dissimilarity
between the observations might contribute to the prediction.

Clearly, the proposed method could be improved using similar technical
enlargements and modifications, as summarized in Section 2. Especially,
ensemble techniques already depicted in [33] with the MLM techniques can be
used to introduce more specific models for subsets of the training data that
could be selected based on features (input) or labels (output), or their
dependencies (see Section 2). For both the global and local models, feature
selection can be used to further specify the models to encapsulate the
relevant behavior of the multi-label data. Moreover, because the core
construct of MLM is distance regression, which is based on pairwise
dissimilarities in the input space, other data modalities and corresponding
dissimilarity measures should be further tested. For textual data, which was
considered for the multi-label classification tasks in [4, 5, 6, 7, 8, 9, 10],
one could apply many similarity measures [108]. The same is true for imaging
data, considered in [11, 12, 13, 14], by using, e.g., a patch-based
dissimilarity [109].

## Author Contributions

JH developed the proposed methods, wrote the implementations, designed and
performed the experiments, analyzed the results, and wrote the majority of the
paper. AH conceptualized the theoretical results, wrote the proofs, and
contributed to the writing of the method sections and the initial draft. TK
performed literature search, wrote majority of the related work section, and
contributed to writing of the initial draft. CLCM, TK and JPPG revised and
commented on the initial draft. JPPG provided a reference implementation of
the LLS algorithm. All authors contributed to the writing and editing of the
final draft.

## Funding

This work was supported by the Academy of Finland through the grant 351579 in
the EuroHPC Research Programme.

## Declarations

The authors declare that they have no conflict of interest.

## References

  * [1] Grigorios Tsoumakas and Ioannis Katakis.  Multi-label classification: An overview.  International Journal of Data Warehousing and Mining (IJDWM), 3(3):1–13, 2007.
  * [2] Min-Ling Zhang and Zhi-Hua Zhou.  A review on multi-label learning algorithms.  IEEE Transactions on Knowledge and Data Engineering, 26(8):1819–1837, 2013.
  * [3] Jasmin Bogatinovski, Ljupčo Todorovski, Sašo Džeroski, and Dragi Kocev.  Comprehensive comparative study of multi-label classification methods.  Expert Systems with Applications, 203:117215, 2022.
  * [4] Shuhua Monica Liu and Jiun-Hung Chen.  A multi-label classification based approach for sentiment classification.  Expert Systems with Applications, 42(3):1083–1093, 2015.
  * [5] Mingchu Jiang, Zhisong Pan, and Na Li.  Multi-label text categorization using l21-norm minimization extreme learning machine.  Neurocomputing, 261:4–10, 2017.
  * [6] Alex M.G. Almeida, Ricardo Cerri, Emerson Cabrera Paraiso, Rafael Gomes Mantovani, and Sylvio Barbon Junior.  Applying multi-label techniques in emotion identification of short texts.  Neurocomputing, 320:35–46, 2018.
  * [7] Md Aslam Parwez, Muhammad Abulaish, et al.  Multi-label classification of microblogging texts using convolution neural network.  IEEE Access, 7:68678–68691, 2019.
  * [8] Jingcheng Du, Qingyu Chen, Yifan Peng, Yang Xiang, Cui Tao, and Zhiyong Lu.  ML-Net: multi-label classification of biomedical texts with deep neural networks.  Journal of the American Medical Informatics Association, 26(11):1279–1285, 2019.
  * [9] Dong Zhang, Shu Zhao, Zhen Duan, Jie Chen, Yanping Zhang, and Jie Tang.  A multi-label classification method using a hierarchical and transparent representation for paper-reviewer recommendation.  ACM Transactions on Information Systems (TOIS), 38(1):1–20, 2020\.
  * [10] Qingyu Chen, Alexis Allot, Robert Leaman, Rezarta Islamaj, Jingcheng Du, Li Fang, Kai Wang, Shuo Xu, Yuefu Zhang, Parsa Bagherzadeh, et al.  Multi-label classification for biomedical literature: an overview of the biocreative vii litcovid track for covid-19 literature topic annotations.  Database, 2022, 2022.
  * [11] Haomin Chen, Shun Miao, Daguang Xu, Gregory D Hager, and Adam P Harrison.  Deep hierarchical multi-label classification of chest x-ray images.  In International conference on medical imaging with deep learning, pages 109–120. PMLR, 2019.
  * [12] Haomin Chen, Shun Miao, Daguang Xu, Gregory D Hager, and Adam P Harrison.  Deep hiearchical multi-label classification applied to chest X-ray abnormality taxonomies.  Medical image analysis, 66:101811, 2020.
  * [13] Xiangji Pan, Kai Jin, Jing Cao, Zhifang Liu, Jian Wu, Kun You, Yifei Lu, Yufeng Xu, Zhaoan Su, Jiekai Jiang, et al.  Multi-label classification of retinal lesions in diabetic retinopathy for automatic analysis of fundus fluorescein angiography based on deep learning.  Graefe’s Archive for Clinical and Experimental Ophthalmology, 258(4):779–785, 2020.
  * [14] Lei Bi, David Dagan Feng, Michael Fulham, and Jinman Kim.  Multi-label classification of multi-modality skin lesion via hyper-connected convolutional neural network.  Pattern Recognition, 107:107502, 2020.
  * [15] Konstantinos Pliakos, Celine Vens, and Grigorios Tsoumakas.  Predicting drug-target interactions with multi-label classification and label partitioning.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 18(4):1596–1607, 2019.
  * [16] Hiba Chougrad, Hamid Zouaki, and Omar Alheyane.  Multi-label transfer learning for the early diagnosis of breast cancer.  Neurocomputing, 392:168–180, 2020.
  * [17] Liang Zhou, Xiaoyuan Zheng, Di Yang, Ying Wang, Xuesong Bai, and Xinhua Ye.  Application of multi-label classification models for the diagnosis of diabetic complications.  BMC Medical Informatics and Decision Making, 21(1):1–10, 2021\.
  * [18] Israel Elujide, Stephen G Fashoto, Bunmi Fashoto, Elliot Mbunge, Sakinat O Folorunso, and Jeremiah O Olamijuwon.  Application of deep and machine learning techniques for multi-label classification performance on psychotic disorder diseases.  Informatics in Medicine Unlocked, 23:100545, 2021.
  * [19] Junxian Cai, Weiwei Sun, Jianfeng Guan, and Ilsun You.  Multi-ECGnet for ECG arrythmia multi-label classification.  IEEE Access, 8:110848–110858, 2020.
  * [20] Ajay Kumar, Kumar Abhishek, Amit Kumar Singh, Pranav Nerurkar, Madhav Chandane, Sunil Bhirud, Dhiren Patel, and Yann Busnel.  Multilabel classification of remote sensed satellite imagery.  Transactions on Emerging Telecommunications Technologies, 32(7):e3988, 2021.
  * [21] Shuoyao Wang, Suzhi Bi, and Ying-Jun Angela Zhang.  Locational detection of the false data injection attack in a smart grid: A multilabel classification approach.  IEEE Internet of Things Journal, 7(9):8218–8227, 2020.
  * [22] Zhanquan Sun, Chaoli Wang, Yangyang Zhao, and Chao Yan.  Multi-label ECG signal classification based on ensemble classifier.  IEEE Access, 8:117986–117996, 2020.
  * [23] Ding Li and Scott Dick.  Non-intrusive load monitoring using multi-label classification methods.  Electrical Engineering, 103(1):607–619, 2021.
  * [24] Michael R Maser, Alexander Y Cui, Serim Ryou, Travis J DeLano, Yisong Yue, and Sarah E Reisman.  Multilabel classification models for the prediction of cross-coupling reaction conditions.  Journal of Chemical Information and Modeling, 61(1):156–166, 2021\.
  * [25] Kushagra Saini and Venkatnarayan Ramanathan.  Predicting odor from molecular structure: a multi-label classification approach.  Scientific Reports, 12(1):1–11, 2022.
  * [26] Gjorgji Madjarov, Dragi Kocev, Dejan Gjorgjevikj, and Sašo Džeroski.  An extensive experimental comparison of methods for multi-label learning.  Pattern Recognition, 45(9):3084–3104, 2012.
  * [27] Amauri Holanda de Souza Junior, Francesco Corona, Guilherme A. Barreto, Yoan Miche, and Amaury Lendasse.  Minimal learning machine: A novel supervised distance-based approach for regression and classification.  Neurocomputing, 164:34–44, 2015.
  * [28] Donald Shepard.  A two-dimensional interpolation function for irregularly-spaced data.  In Proceedings of the 1968 23rd ACM national conference, pages 517–524, 1968.
  * [29] Dragi Kocev, Celine Vens, Jan Struyf, and Sašo Džeroski.  Ensembles of multi-objective decision trees.  In European conference on machine learning, pages 624–631. Springer, 2007.
  * [30] Min-Ling Zhang and Zhi-Hua Zhou.  Ml-knn: A lazy learning approach to multi-label learning.  Pattern Recognition, 40(7):2038–2048, 2007.
  * [31] Alberto Bemporad.  Global optimization via inverse distance weighting and radial basis functions.  Multimedia Tools and Applications, 77(2):571–595, NOV 2020.
  * [32] Joonas Hämäläinen, Alisson SC Alencar, Tommi Kärkkäinen, César LC Mattos, Amauri H Souza Júnior, and Joao PP Gomes.  Minimal learning machine: Theoretical results and clustering-based reference point selection.  The Journal of Machine Learning Research, 21, 2020.
  * [33] Joonas Hämäläinen, Paavo Nieminen, and Tommi Kärkkäinen.  Instance-based multi-label classification via multi-target distance regression.  In European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning. ESANN, 2021.
  * [34] Matthew R Boutell, Jiebo Luo, Xipeng Shen, and Christopher M Brown.  Learning multi-label scene classification.  Pattern Recognition, 37(9):1757–1771, 2004.
  * [35] Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas.  Random k-labelsets for multilabel classification.  IEEE Transactions on Knowledge and Data Engineering, 23(7):1079–1089, 2010.
  * [36] Jesse Read, Peter Reutemann, Bernhard Pfahringer, and Geoffrey Holmes.  Meka: a multi-label/multi-target extension to weka.  The Journal of Machine Learning Research, 17(1):1–5, 2016.
  * [37] Piotr Szymanski and Tomasz Kajdanowicz.  Scikit-multilearn: a scikit-based python environment for performing multi-label classification.  The Journal of Machine Learning Research, 20(1):209–230, 2019.
  * [38] Marcel Wever, Alexander Tornede, Felix Mohr, and Eyke Hüllermeier.  Automl for multi-label classification: Overview and empirical evaluation.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 43(9):3037–3054, 2021.
  * [39] André Elisseeff and Jason Weston.  A kernel method for multi-labelled classification.  Advances in Neural Information Processing Systems, 14, 2001.
  * [40] Isaac Triguero and Celine Vens.  Labelling strategies for hierarchical multi-label classification techniques.  Pattern Recognition, 56:170–183, 2016.
  * [41] Qingyao Wu, Mingkui Tan, Hengjie Song, Jian Chen, and Michael K Ng.  ML-FOREST: A multi-label tree ensemble method for multi-label classification.  IEEE Transactions on Knowledge and Data Engineering, 28(10):2665–2680, 2016.
  * [42] Ignazio Pillai, Giorgio Fumera, and Fabio Roli.  Multi-label classification with a reject option.  Pattern Recognition, 46(8):2256–2266, 2013.
  * [43] Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank.  Classifier chains for multi-label classification.  Machine Learning, 85(3):333–359, 2011.
  * [44] Eleftherios Spyromitros-Xioufis, Grigorios Tsoumakas, William Groves, and Ioannis Vlahavas.  Multi-target regression via input space expansion: treating targets as inputs.  Machine Learning, 104(1):55–98, 2016.
  * [45] Xie Jun, Yu Lu, Zhu Lei, and Duan Guolun.  Conditional entropy based classifier chains for multi-label classification.  Neurocomputing, 335:185–194, 2019.
  * [46] Lior Rokach, Alon Schclar, and Ehud Itach.  Ensemble methods for multi-label classification.  Expert Systems with Applications, 41(16):7507–7523, 2014.
  * [47] Ran Wang, Sam Kwong, Xu Wang, and Yuheng Jia.  Active k-labelsets ensemble for multi-label classification.  Pattern Recognition, 109:107583, 2021.
  * [48] Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas.  Effective and efficient multilabel classification in domains with large number of labels.  In Proc. ECML/PKDD 2008 Workshop on Mining Multidimensional Data (MMD’08), volume 21, pages 53–59, 2008.
  * [49] Dragi Kocev, Celine Vens, Jan Struyf, and Sašo Džeroski.  Tree ensembles for predicting structured outputs.  Pattern Recognition, 46(3):817–833, 2013.
  * [50] Rafael B Pereira, Alexandre Plastino, Bianca Zadrozny, and Luiz HC Merschmann.  Categorizing feature selection methods for multi-label classification.  Artificial Intelligence Review, 49(1):57–78, 2018.
  * [51] Jianghong Ma, Haijun Zhang, and Tommy WS Chow.  Multilabel classification with label-specific features and classifiers: A coarse-and fine-tuned framework.  IEEE Transactions on Cybernetics, 51(2):1028–1042, 2019.
  * [52] Wei Weng, Yan-Nan Chen, Chin-Ling Chen, Shun-Xiang Wu, and Jing-Hua Liu.  Non-sparse label specific features selection for multi-label classification.  Neurocomputing, 377:85–94, 2020.
  * [53] Jun Huang, Guorong Li, Qingming Huang, and Xindong Wu.  Learning label-specific features and class-dependent labels for multi-label classification.  IEEE Transactions on Knowledge and Data Engineering, 28(12):3309–3323, 2016.
  * [54] Vikas Kumar, Arun K Pujari, Vineet Padmanabhan, and Venkateswara Rao Kagita.  Group preserving label embedding for multi-label classification.  Pattern Recognition, 90:23–34, 2019.
  * [55] Ming Huang, Fuzhen Zhuang, Xiao Zhang, Xiang Ao, Zhengyu Niu, Min-Ling Zhang, and Qing He.  Supervised representation learning for multi-label classification.  Machine Learning, 108(5):747–763, 2019.
  * [56] Wissam Siblini, Pascale Kuntz, and Frank Meyer.  A review on dimensionality reduction for multi-label classification.  IEEE Transactions on Knowledge and Data Engineering, 33(3):839–857, 2019.
  * [57] Guoqiang Wu, Ruobing Zheng, Yingjie Tian, and Dalian Liu.  Joint ranking svm and binary relevance with robust low-rank learning for multi-label classification.  Neural Networks, 122:24–39, 2020.
  * [58] Xiaoyan Zhu, Jiaxuan Li, Jingtao Ren, Jiayin Wang, and Guangtao Wang.  Dynamic ensemble learning for multi-label classification.  Information Sciences, 623:94–111, 2023.
  * [59] Yuelong Xia, Ke Chen, and Yun Yang.  Multi-label classification with weighted classifier selection and stacked ensemble.  Information Sciences, 557:421–442, 2021.
  * [60] Tommi Kärkkäinen.  Extreme minimal learning machine: Ridge regression with distance-based basis.  Neurocomputing, 342:33–48, 2019.
  * [61] Vikas Chauhan and Aruna Tiwari.  Randomized neural networks for multilabel classification.  Applied Soft Computing, 115:108184, 2022.
  * [62] Joakim Linja, Joonas Hämäläinen, Paavo Nieminen, and Tommi Kärkkäinen.  Feature selection for distance-based regression: An umbrella review and a one-shot wrapper.  Neurocomputing, 2022.
  * [63] Jaesung Lee and Dae-Won Kim.  Feature selection for multi-label classification using multivariate mutual information.  Pattern Recognition Letters, 34(3):349–357, 2013.
  * [64] Wenbin Qian, Chuanzhen Xiong, and Yinglong Wang.  A ranking-based feature selection for multi-label classification with fuzzy relative discernibility.  Applied Soft Computing, 102:106995, 2021.
  * [65] Zhi-Fen He, Ming Yang, Yang Gao, Hui-Dong Liu, and Yilong Yin.  Joint multi-label classification and label correlations with missing labels and feature selection.  Knowledge-Based Systems, 163:145–158, 2019.
  * [66] Lin Sun, Tianxiang Wang, Weiping Ding, Jiucheng Xu, and Yaojin Lin.  Feature selection using fisher score and multilabel neighborhood rough sets for multilabel classification.  Information Sciences, 578:887–912, 2021.
  * [67] Jianghong Ma and Tommy WS Chow.  Topic-based instance and feature selection in multilabel classification.  IEEE Transactions on Neural Networks and Learning Systems, 33(1):315–329, 2022.
  * [68] Jianghong Ma, Bernard Chi Yuen Chiu, and Tommy WS Chow.  Multilabel classification with group-based mapping: a framework with local feature selection and local label correlation.  IEEE Transactions on Cybernetics, 52(6):4596–4610, 2022.
  * [69] Newton Spolaôr, Maria Carolina Monard, Grigorios Tsoumakas, and Huei Diana Lee.  A systematic review of multi-label feature selection and a new method based on label construction.  Neurocomputing, 180:3–15, 2016.
  * [70] Shima Kashef, Hossein Nezamabadi-pour, and Bahareh Nikpour.  Multilabel feature selection: A comprehensive review and guiding experiments.  Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, 8(2):e1240, 2018.
  * [71] Ze-Bang Yu and Min-Ling Zhang.  Multi-label classification with label-specific feature generation: A wrapped approach.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5199–5210, 2022.
  * [72] Hamid Bayati, Mohammad Bagher Dowlatshahi, and Amin Hashemi.  Mssl: A memetic-based sparse subspace learning algorithm for multi-label classification.  International Journal of Machine Learning and Cybernetics, 13(11):3607–3624, 2022.
  * [73] Hongbin Dong, Jing Sun, Xiaohang Sun, and Rui Ding.  A many-objective feature selection for multi-label classification.  Knowledge-Based Systems, 208:106456, 2020.
  * [74] Amin Hashemi, Mohammad Bagher Dowlatshahi, and Hossein Nezamabadi-pour.  An efficient pareto-based feature selection algorithm for multi-label classification.  Information Sciences, 581:428–447, 2021.
  * [75] Wenbin Qian, Jintao Huang, Yinglong Wang, and Yonghong Xie.  Label distribution feature selection for multi-label classification with rough set.  International Journal of Approximate Reasoning, 128:32–55, 2021\.
  * [76] Qiaoyu Tan, Yanming Yu, Guoxian Yu, and Jun Wang.  Semi-supervised multi-label classification using incomplete label information.  Neurocomputing, 260:192–202, 2017.
  * [77] Tien Thanh Nguyen, Thi Thu Thuy Nguyen, Anh Vu Luong, Quoc Viet Hung Nguyen, Alan Wee-Chung Liew, and Bela Stantic.  Multi-label classification via label correlation and first order feature dependance in a data stream.  Pattern Recognition, 90:35–51, 2019.
  * [78] Tien Thanh Nguyen, Manh Truong Dang, Anh Vu Luong, Alan Wee-Chung Liew, Tiancai Liang, and John McCall.  Multi-label classification via incremental clustering on an evolving data stream.  Pattern Recognition, 95:96–113, 2019.
  * [79] Felipe Kenji Nakano, Ricardo Cerri, and Celine Vens.  Active learning for hierarchical multi-label classification.  Data Mining and Knowledge Discovery, 34(5):1496–1530, 2020.
  * [80] Marilyn Bello, Gonzalo Nápoles, Ricardo Sánchez, Rafael Bello, and Koen Vanhoof.  Deep neural network to extract high-level features and labels in multi-label classification problems.  Neurocomputing, 413:259–270, 2020.
  * [81] Dongjoo Yun, Jongbin Ryu, and Jongwoo Lim.  Dual aggregated feature pyramid network for multi label classification.  Pattern Recognition Letters, 144:75–81, 2021.
  * [82] Diego P. P. Mesquita, João P. P. Gomes, and Amauri H. Souza Junior.  Ensemble of efficient minimal learning machines for classification and regression.  Neural Processing Letters, pages 1–16, 2017.
  * [83] Weiwei Liu, Haobo Wang, Xiaobo Shen, and Ivor Tsang.  The emerging trends of multi-label learning.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021\.
  * [84] K. Bhatia, K. Dahiya, H. Jain, P. Kar, A. Mittal, Y. Prabhu, and M. Varma.  The extreme classification repository: Multi-label datasets and code, 2016\.
  * [85] Kush Bhatia, Himanshu Jain, Purushottam Kar, Manik Varma, and Prateek Jain.  Sparse local embeddings for extreme multi-label classification.  Advances in Neural Information Processing Systems, 28, 2015.
  * [86] Wenjie Zhang, Junchi Yan, Xiangfeng Wang, and Hongyuan Zha.  Deep extreme multi-label learning.  In Proceedings of the 2018 ACM on international conference on multimedia retrieval, pages 100–107, 2018.
  * [87] V. Roshan Joseph and Lulu Kang.  Regression-based inverse distance weighting with applications to computer experiments.  Technometrics, 53(3):254–265, AUG 2011.
  * [88] Feng-Wen Chen and Chen-Wuing Liu.  Estimation of the spatial rainfall distribution using inverse distance weighting (idw) in the middle of taiwan.  Paddy and Water Environment, 10(3, SI):209–222, SEP 2012.
  * [89] Zhao-Yue Chen, Tian-Hao Zhang, Rong Zhang, Zhong-Min Zhu, Jun Yang, Ping-Yan Chen, Chun-Quan Ou, and Yuming Guo.  Extreme gradient boosting model to estimate pm2.5 concentrations with missing-filled satellite data in china.  Atmospheric Environment, 202:180–189, APR 1 2019.
  * [90] Nazife Cevik.  A dynamic inverse distance weighting-based local face descriptor.  Multimedia Tools and Applications, 79(41-42):31087–31102, NOV 2020\.
  * [91] Yucheng Shi, Weiguo He, Jian Zhao, Aoyu Hu, Jingna Pan, Haizheng Wang, and Honglu Zhu.  Expected output calculation based on inverse distance weighting and its application in anomaly detection of distributed photovoltaic power stations.  Journal of Cleaner Production, 253, APR 20 2020.
  * [92] Gjorgji Madjarov, Dejan Gjorgjevikj, and Sašo Džeroski.  Two stage architecture for multi-label learning.  Pattern Recognition, 45(3):1019–1034, 2012.
  * [93] Chunyu Zhang and Zhanshan Li.  Multi-label learning with label-specific features via weighting and label entropy guided clustering ensemble.  Neurocomputing, 419:59–69, 2021.
  * [94] Xiaoya Wei, Ziwei Yu, Changqing Zhang, and Qinghua Hu.  Ensemble of label specific features for multi-label classification.  In 2018 IEEE International Conference on Multimedia and Expo (ICME), pages 1–6. IEEE, 2018.
  * [95] Michael Rapp, Eneldo Loza Mencía, Johannes Fürnkranz, Vu-Linh Nguyen, and Eyke Hüllermeier.  Learning gradient boosted multi-label classification rules.  In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2020, Ghent, Belgium, September 14–18, 2020, Proceedings, Part III, pages 124–140. Springer, 2020.
  * [96] Pawel Trajdos and Marek Kurzynski.  Dynamic classifier chains for multi-label learning.  In Pattern Recognition: 41st DAGM German Conference, DAGM GCPR 2019, Dortmund, Germany, September 10–13, 2019, Proceedings 41, pages 567–580. Springer, 2019.
  * [97] David M. Allen.  The relationship between variable selection and data agumentation and a method for prediction.  Technometrics, 16(1):125–127, 1974.
  * [98] Emil Eirola, Andrey Gritsenko, Anton Akusok, Kaj-Mikael Björk, Yoan Miche, Dušan Sovilj, Rui Nian, Bo He, and Amaury Lendasse.  Extreme learning machines for multiclass classification: refining predictions with gaussian mixture models.  In International Work-Conference on Artificial Neural Networks, pages 153–164. Springer, 2015.
  * [99] Alisson SC Alencar, Ajalmar R Rocha Neto, and João Paulo P Gomes.  A new pruning method for extreme learning machines via genetic algorithms.  Applied Soft Computing, 44:101–107, 2016.
  * [100] Reem Alotaibi and Peter Flach.  Multi-label thresholding for cost-sensitive classification.  Neurocomputing, 436:232–247, 2021.
  * [101] Rafael B Pereira, Alexandre Plastino, Bianca Zadrozny, and Luiz HC Merschmann.  Correlation analysis of performance measures for multi-label classification.  Information Processing & Management, 54(3):359–369, 2018.
  * [102] Min-Ling Zhang, Yu-Kun Li, Xu-Ying Liu, and Xin Geng.  Binary relevance for multi-label learning: an overview.  Frontiers of Computer Science, 12(2):191–202, APR 2018.
  * [103] Jesse Read, Bernhard Pfahringer, Geoff Holmes, and Eibe Frank.  Classifier chains: A review and perspectives.  Journal of Artificial Intelligence Research, 70:683–718, 2021.
  * [104] Grigorios Tsoumakas, Ioannis Katakis, and Ioannis Vlahavas.  Effective and efficient multilabel classification in domains with large number of labels.  In Proc. ECML/PKDD 2008 Workshop on Mining Multidimensional Data (MMD’08), volume 21, pages 53–59, 2008.
  * [105] Janez Demšar.  Statistical comparisons of classifiers over multiple data sets.  The Journal of Machine Learning Research, 7:1–30, 2006.
  * [106] Joakim Linja, Joonas Hämäläinen, Paavo Nieminen, and Tommi Kärkkäinen.  Do randomized algorithms improve the efficiency of minimal learning machine?  Machine Learning and Knowledge Extraction, 2(4):533–557, 2020.
  * [107] Xiaoping Lai, Jiuwen Cao, Xiaofeng Huang, Tianlei Wang, and Zhiping Lin.  A maximally split and relaxed admm for regularized extreme learning machines.  IEEE Transactions on Neural Networks and Learning Systems, 31(6):1899–1913, 2019.
  * [108] Jiapeng Wang and Yihong Dong.  Measurement of text similarity: a survey.  Information, 11(9):421, 2020.
  * [109] Alessia Amelio and Clara Pizzuti.  A patch-based measure for image dissimilarity.  Neurocomputing, 171:362–378, 2016.

##  Appendix A Proofs

For clarity, we split the proof of Proposition 1 into two parts, corresponding
to the numbered statements.

Part I: for arbitrary $[\hat{\delta}_{k}]_{k},$ NN-MLM does not yield optimal
solutions

###### Proof.

To show that for arbitrary $[\hat{\delta}_{k}]_{k}$ NN-MLM does not always
yield optimal solutions, it suffices to provide a counterexample. Thus,
consider $L=2$,
$\mathbf{y}_{1}=[0,0]^{\top},\mathbf{y}_{2}=[0,1]^{\top},\mathbf{y}_{3}=[1,0]^{\top},\mathbf{y}_{4}=[1,1]^{\top}$,
and $\mathbf{t}_{i}=\mathbf{y}_{i}$ for all $i$. Also, let us define
$\hat{\delta}_{1}=1,\hat{\delta}_{2}=10,\hat{\delta}_{3}=2,\hat{\delta}_{4}=2$.

In this case, the prediction from NN-MLM is
$\hat{\mathbf{y}}=\mathbf{y}_{1}=[0,0]^{\top}$ with associated loss equal to

$\displaystyle J(\mathbf{y}_{1})$
$\displaystyle=(-\hat{\delta}_{1}^{2})^{2}+(1-\hat{\delta}_{2}^{2})^{2}+(1-\hat{\delta}_{3}^{2})^{2}+(2-\hat{\delta}_{4}^{2})^{2}$
$\displaystyle=1+99^{2}+3^{2}+2^{2}=9815$

Now, consider the value $J(\mathbf{y}_{3})$:

$\displaystyle J(\mathbf{y}_{3})$
$\displaystyle=(1-\hat{\delta}_{1}^{2})^{2}+(2-\hat{\delta}_{2}^{2})^{2}+(0-\hat{\delta}_{3}^{2})^{2}+(1-\hat{\delta}_{4}^{2})^{2}$
$\displaystyle=0+98^{2}+4^{2}+3^{2}=9629$

Therefore, since $J(\mathbf{y}_{3})<J(\mathbf{y}_{1})$,
$\hat{\mathbf{y}}=\mathbf{y}_{1}$ is not an optimal solution to the
multilateration problem in Equation 1. ∎

Part II: If $\hat{\delta}_{k}=\|\mathbf{y}^{\prime}-\mathbf{t}_{k}\|$ for some
$\mathbf{y}^{\prime}\in\mathbb{Y}$, then NN-MLM returns an optimal solution

###### Proof.

Recall that our loss function is
$J(\mathbf{y})=\sum_{k=1}^{K}\left(\|\mathbf{y}-\mathbf{t}_{k}\|^{2}-\hat{\delta}_{k}^{2}\right)^{2}$.
We can rewrite $J$ as:

$\displaystyle
J(\mathbf{y})=\sum_{l=1}^{2^{L}}N_{l}\left(\|\mathbf{y}-\mathbf{y}_{l}\|^{2}-\hat{\delta}_{l}^{2}\right)^{2}$

where $\mathbf{y}_{l}$ is the $l$-th multilabel assignment, and
$\hat{\delta}_{l}^{2}$ is the estimate of the distance between $\mathbf{y}$
and a reference point associated with $l$-th multilabel assignment
$\mathbf{y}_{l}$. The value $N_{l}$ denotes the number of output reference
points equal to $\mathbf{y}_{l}$.

We are interested in the setting where
$\hat{\delta}_{l}^{2}=\|\mathbf{y}^{\prime}-\mathbf{y}_{l}\|^{2}$ for some
$\mathbf{y}^{\prime}\in\mathbb{Y}$, which gives

$\displaystyle\operatorname*{argmin}_{\mathbf{y}\in\mathbb{Y}}\sum_{l=1}^{2^{L}}N_{l}\left(\|\mathbf{y}-\mathbf{y}_{l}\|^{2}-\|\mathbf{y}^{\prime}-\mathbf{y}_{l}\|^{2}\right)^{2}.$

A minimizer to the equation above is $\mathbf{y}=\mathbf{y}^{\prime}$, which
produces $J(\mathbf{y}^{\prime})=0$. To conclude the proof, we only need to
recover the value $\mathbf{y}^{\prime}$ from $[\hat{\delta}_{k}]_{k}$. We
achieve that by computing $\mathbf{y}^{\prime}=\mathbf{t}_{k^{\star}}$ such
that $\hat{\delta}_{k^{\star}}=0$, Notably, this corresponds to the prediction
from the NN-MLM method. ∎

##  Appendix B Evaluation metrics

In the traditional single-label classification SLC, comparing different
machine learning methods’ classification performance is straightforward. In
SLC, an input for the evaluation metrics from the machine learning model is
just a set of labels with the same label cardinality as the test set. Many
machine learning models have an intermediate layer that gives predicted scores
for individual labels, which are then utilized to predict the relevant label
by selecting the label corresponding to the largest score. Typically, these
intermediate scores are not used with the SLC evaluation metrics. From the
perspective of a classifier model with this kind of intermediate layer, MLC
and SLC differ in the prediction phase only by how the intermediate values are
handled. In MLC, we do not have a global fixed value for the number of
relevant labels per instance. The MLC metrics can be divided into two main
categories: $1)$ ranking-based and $2)$ bipartition-based. The bipartition-
based metrics can be further divided into two subcategories: $2.1)$ example-
based and $2.2)$ label-based.

For a test set of instances
${\mathbf{X}}_{ts}=\\{\mathbf{x}_{i}^{*}\\}_{i=1}^{N_{ts}}$ and a set of
ground truth labels ${\mathbf{Y}}_{gt}=\\{\mathbf{g}_{i}\\}_{i=1}^{N_{ts}}$,
where ${\mathbf{X}}_{ts}\subset{\mathbb{R}}^{M}$ and
${\mathbf{Y}}_{gt}\subset\\{0,1\\}^{L}$. For a classifier model $h$, we get a
set of multi-label predictions
${\mathbf{Y}}_{pr}=\\{\mathbf{y}_{i}^{*}\\}_{i=1}^{N_{ts}}$, where
$\mathbf{y}_{i}^{*}=h(\mathbf{x}_{i}^{*})\in\\{0,1\\}^{L}$.

Hamming Loss is an example-based evaluation metric and it is one of the most
popular MLC metrics. It is defined as

$\textsc{Hamming
Loss}=\frac{1}{N_{ts}L}\sum_{i=1}^{N_{ts}}\mathbf{y}_{i}^{*}\Delta\mathbf{g}_{i}$
(11)

where $\Delta$ denotes the symmetric difference, which is defined as
$\sum_{j=1}^{L}\mathbf{a}_{(j)}\oplus\mathbf{b}_{(j)}$, for
$\mathbf{a},\mathbf{b}\in\\{0,1\\}^{L}$. In the MLC problems, accuracy is
defined as

$\textsc{Accuracy}=\frac{1}{N_{ts}}\sum_{i=1}^{N_{ts}}\frac{\mathbf{y}_{i}^{*}\cdot\mathbf{g}_{i}}{\mathbf{y}_{i}^{*}\cdot\mathbf{y}_{i}^{*}+\mathbf{g}_{i}\cdot\mathbf{g}_{i}-\mathbf{y}_{i}^{*}\cdot\mathbf{g}_{i}}$
(12)

Micro recall and micro precision metrics are defined as

$\textsc{Micro
Recall}=\frac{\sum_{j=1}^{L}TP_{j}}{\sum_{j=1}^{L}TP_{j}+\sum_{j=1}^{L}FP_{j}},$
(13) $\textsc{Micro
Precision}=\frac{\sum_{j=1}^{L}TP_{j}}{\sum_{j=1}^{L}TP_{j}+\sum_{j=1}^{L}FN_{j}},$
(14)

where, for a label $j$ and over $N_{ts}$ instances, $TP_{j}$ refers to #True
Positives, $FP_{j}$ to #False Positives, and $FN_{j}$ to #False Negatives.
Corresponding macro metrics are defined as

$\textsc{Macro Recall}=\frac{1}{L}\sum_{j=1}^{L}\frac{TP_{j}}{TP_{j}+FP_{j}},$
(15) $\textsc{Macro
Precision}=\frac{1}{L}\sum_{j=1}^{L}\frac{TP_{j}}{TP_{j}+FN_{j}},$ (16)

where $TP_{j}$, $FP_{j}$, and $FN_{j}$ are same as for the micro metrics
(Equations (13)-(14)). Besides Hamming Loss, other popular bipartition-based
MLC metrics are Micro F1 and Macro F1 [101, 26] which are defined via the
harmonic mean of the corresponding recall and precision as

$\textsc{Micro F1}=\textsc{Hmean}~{}(\textsc{Micro Precision},\textsc{Micro
Recall}),$ (17) $\textsc{Macro F1}=\textsc{Hmean}~{}(\textsc{Macro
Precision},\textsc{Macro Recall}),$ (18)

where $\textsc{Hmean}(a,b)=\frac{2ab}{a+b}$ for $a,b\in{\mathbb{R}}_{+}$.

For the given classifier $h$, lets denote $h_{0}$ as function that assigns a
label score for each label. Then, for the classifier $h$, a predicted set of
label scores $\mathbf{Z}=\\{\mathbf{z}_{i}\\}_{i=1}^{N_{test}}$, where
$\mathbf{z}_{i}=h_{0}(\mathbf{x}_{i})\in{\mathbb{R}}^{L}$ and
$\mathbf{x}_{i}\in{\mathbf{X}}_{test}$.

Ranking loss is a ranking-based MLC evaluation metric that represents overall
quality of a classifier independently from the threshold selection. The
ranking loss metric is given as

$\textsc{Ranking
Loss}=\frac{1}{N_{ts}}\sum_{i=1}^{N_{ts}}\frac{|\\{(j,k)~{}|~{}\mathbf{z}_{i(j)}<\mathbf{z}_{i(k)},~{}j\in
g_{i}^{+},~{}k\in g_{i}^{0}\\}|}{|g_{i}^{+}||g_{i}^{0}|},$ (19)

where $g_{i}^{+}$ and $g_{i}^{0}$ are sets of the relevant and irrelevant
ground truth labels, correspondingly. Another popular ranking-based metric,
coverage, is defined as

$\textsc{Coverage}=\frac{1}{N_{ts}}\sum_{i=1}^{N_{ts}}|\\{j~{}|~{}\min\limits_{k\in
g_{i}^{+}}\mathbf{z}_{i(k)}\leq\mathbf{z}_{i(j)}\\}|,$ (20)

where $g_{i}^{+}=\\{j~{}|~{}j=\\{1,...,L\\},g_{i(j)}=1\\}$ denotes the active
ground truth labels for an instance $i$. In short, this metric represents
steps required to capture all actual labels from the ranking.

One error represents missclassification error for the highest ranked label. It
is defined as

$\textsc{One
error}=\frac{1}{N_{ts}}\sum_{i=1}^{N_{ts}}1-\mathbf{g}_{i(j^{*})},$ (21)

where $j^{*}=\operatorname*{argmax}\limits_{j}\mathbf{z}_{i(j)}$. Note that
One error possess the same information as the precision at $k=1$ ($P@1$)
metric, since $\textsc{One error}=1-P@1$.

Average precision is defined as

$\textsc{Average
Precision}=\frac{1}{N_{ts}}\sum_{i=1}^{N_{ts}}\frac{1}{|g_{i}^{+}|}\sum_{j\in
g_{i}^{+}}\frac{|\\{m~{}|~{}\mathbf{z}_{i(j)}\leq\mathbf{z}_{i(m)},m\in
g_{i}^{+}\\}|}{|\\{k~{}|~{}\mathbf{z}_{i(j)}\leq\mathbf{z}_{i(k)}\\}|}.$ (22)

This metric computes an average ratio of the relevant labels ranked above a
label $j$ over Coverage plus one for the label $j$ (coverage above).

##  Appendix C Power parameter effects

(a)

(b)

Figure 5: (a) shows how weight values changes as a function MLM’s predicted
distances with different power parameter values. (b) shows how Ranking Loss
changes as a function of power parameter $P$ for Yeast dataset.

Figure 5 shows how the power parameter affects to the weights and overall
ranking performance. In Figure 5(a), weights for a sample of eight predicted
distances are shown with $P=1,2,4,8,16,32$. This set of predicted distances is
sampled from a MLM model’s prediction for the Yeast dataset. Note that since
we are using the Euclidean distance as a distance measure and the binary
representation of the labels, distance $\sqrt{m}$ corresponds to $m$ label
difference. In the illustration, the smallest predicted distance is near to
$\sqrt{2}$ which corresponds to two label difference. Note that this gives
estimation how much the model is extrapolating. Increasing the power parameter
value, gives relatively more weight to smaller predicted distances, meaning
that the prediction is relying more on a predictions given by smaller set
reference points. In Figure 5(b), the proposed method’s Ranking Loss (see eq.
(19)) is shown as a function of $P$ for a Yeast dataset’s test set. For a
smaller $P$ values, Ranking Loss decreases until it reaches the optimal value
at $P=13$. After this point, the Ranking Loss starts to slightly increase,
which indicates that smaller predicted distances are being given too much
weight in the convex combination of label vectors, causing deviations from the
optimal ranking of the labels.

##  Appendix D Results for ranking-based metrics

Table 3: Results for Ranking Loss

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.021 0.246 0.084 0.060 0.164 0.117 0.068 0.114 0.003 0.061 CC
0.019 0.245 0.083 0.064 0.170 0.118 0.067 0.117 0.003 0.062 HOMER 0.090 0.297
0.183 0.119 0.205 0.352 0.255 0.379 0.028 0.177 RF-PCT 0.024 0.151 0.079 0.072
0.167 0.117 0.093 0.106 0.006 0.047 ML-kNN 0.045 0.283 0.093 0.093 0.172 0.130
0.217 0.129 0.031 0.055 BR-MLM 0.024 0.146 0.089 0.066 0.167 0.184 0.080 0.132
0.000 0.061 ML-MLM 0.030 0.142 0.081 0.065 0.166 0.115 0.078 0.118 0.000 0.051
LLS-MLM 0.029 0.155 0.111 0.068 0.174 0.194 0.089 0.148 0.000 0.082

Table 4: Results for Coverage.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 1.610 2.307 12.530 0.399 6.330 104.800 20.926 530.126 1.311
20.481 CC 1.471 2.317 12.437 0.417 6.439 105.428 21.078 537.388 1.302 20.333
HOMER 5.324 2.634 24.190 0.739 7.285 250.800 65.626 933.956 2.369 47.046 RF-
PCT 1.619 1.827 12.074 0.461 6.179 107.412 25.854 504.999 1.219 16.926 ML-kNN
2.844 2.490 13.181 0.569 6.414 113.046 56.266 589.898 2.155 18.719 BR-MLM
1.592 1.792 14.143 0.439 6.339 157.048 25.883 664.122 1.208 22.412 ML-MLM
2.026 1.743 11.827 0.426 6.022 101.548 24.094 510.747 1.207 17.956 LLS-MLM
2.008 1.847 16.057 0.450 6.610 166.308 29.010 715.828 1.207 27.611

Table 5: Results for One Error.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.135 0.386 0.237 0.180 0.236 0.660 0.346 0.354 0.029 0.188 CC
0.123 0.376 0.238 0.204 0.268 0.674 0.342 0.367 0.026 0.193 HOMER 0.216 0.411
0.314 0.216 0.248 0.652 0.466 0.509 0.050 0.219 RF-PCT 0.174 0.262 0.221 0.210
0.248 0.608 0.433 0.332 0.006 0.159 ML-kNN 0.279 0.406 0.280 0.242 0.234 0.706
0.576 0.416 0.190 0.182 BR-MLM 0.153 0.267 0.230 0.194 0.236 0.600 0.341 0.309
0.002 0.113 ML-MLM 0.146 0.257 0.295 0.195 0.234 0.626 0.357 0.422 0.002 0.121
LLS-MLM 0.158 0.262 0.275 0.191 0.236 0.598 0.345 0.356 0.002 0.129

Table 6: Results for Average Precision.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.896 0.721 0.693 0.893 0.768 0.303 0.597 0.351 0.978 0.686 CC
0.901 0.724 0.695 0.881 0.755 0.293 0.599 0.343 0.981 0.672 HOMER 0.786 0.698
0.604 0.848 0.740 0.222 0.407 0.231 0.945 0.583 RF-PCT 0.868 0.812 0.698 0.874
0.757 0.334 0.525 0.395 0.996 0.737 ML-kNN 0.784 0.694 0.635 0.851 0.758 0.266
0.349 0.326 0.844 0.703 BR-MLM 0.884 0.820 0.709 0.883 0.766 0.327 0.608 0.407
0.999 0.745 ML-MLM 0.882 0.827 0.685 0.883 0.767 0.321 0.587 0.345 0.999 0.727
LLS-MLM 0.876 0.813 0.683 0.883 0.760 0.322 0.597 0.391 0.999 0.724

##  Appendix E Results for bipartition-based metrics

Table 7: Results for Accuracy.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.206 0.361 0.446 0.689 0.520 0.030 0.348 0.136 0.891 0.403 CC
0.211 0.356 0.334 0.723 0.527 0.030 0.352 0.137 0.899 0.390 HOMER 0.713 0.471
0.478 0.717 0.559 0.179 0.330 0.207 0.888 0.413 RF-PCT 0.591 0.519 0.416 0.541
0.478 0.009 0.166 0.146 0.914 0.441 ML-kNN 0.528 0.319 0.319 0.629 0.492 0.014
0.129 0.102 0.574 0.421 BR-MLM 0.767 0.598 0.470 0.767 0.545 0.168 0.393 0.150
0.992 0.463 ML-MLM 0.762 0.609 0.473 0.764 0.568 0.197 0.411 0.223 0.994 0.466
LLS-MLM 0.767 0.586 0.465 0.770 0.543 0.173 0.400 0.149 0.993 0.465 NN-MLM
0.775 0.586 0.455 0.770 0.553 0.178 0.399 0.143 0.993 0.467

Table 8: Results for Hamming loss.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.077 0.257 0.045 0.079 0.190 0.017 0.012 0.018 0.013 0.032 CC
0.077 0.256 0.064 0.082 0.193 0.017 0.012 0.018 0.013 0.032 HOMER 0.012 0.361
0.051 0.082 0.207 0.012 0.014 0.022 0.015 0.038 RF-PCT 0.014 0.189 0.046 0.094
0.197 0.009 0.013 0.018 0.011 0.029 ML-kNN 0.017 0.294 0.051 0.099 0.198 0.009
0.014 0.018 0.058 0.031 BR-MLM 0.011 0.194 0.047 0.078 0.193 0.010 0.013 0.018
0.001 0.029 ML-MLM 0.013 0.186 0.054 0.078 0.195 0.014 0.018 0.025 0.001 0.036
LLS-MLM 0.011 0.201 0.049 0.077 0.195 0.010 0.013 0.018 0.001 0.029 NN-MLM
0.011 0.202 0.050 0.077 0.193 0.010 0.013 0.018 0.001 0.029

Table 9: Results for Micro f1.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.343 0.509 0.564 0.761 0.652 0.059 0.457 0.234 0.932 0.533 CC
0.350 0.503 0.482 0.757 0.650 0.059 0.462 0.236 0.936 0.509 HOMER 0.773 0.588
0.591 0.764 0.673 0.275 0.429 0.339 0.927 0.553 RF-PCT 0.693 0.672 0.537 0.669
0.617 0.018 0.230 0.248 0.945 0.563 ML-kNN 0.634 0.457 0.466 0.661 0.625 0.030
0.206 0.175 0.682 0.545 BR-MLM 0.788 0.705 0.580 0.775 0.663 0.256 0.437 0.275
0.994 0.586 ML-MLM 0.765 0.715 0.571 0.781 0.678 0.285 0.408 0.348 0.996 0.588
LLS-MLM 0.784 0.695 0.570 0.778 0.659 0.259 0.435 0.272 0.994 0.583 NN-MLM
0.794 0.693 0.554 0.778 0.663 0.261 0.432 0.260 0.995 0.585

Table 10: Results for Macro f1.

Dataset Medical Emotions Enron Scene Yeast Corel5k Bibtex Delicious Tmc2007
Mediamill BR 0.361 0.440 0.143 0.765 0.392 0.021 0.307 0.096 0.942 0.056 CC
0.371 0.420 0.153 0.762 0.390 0.021 0.316 0.100 0.947 0.052 HOMER 0.282 0.570
0.167 0.768 0.447 0.036 0.266 0.103 0.924 0.073 RF-PCT 0.207 0.650 0.122 0.658
0.322 0.004 0.055 0.083 0.857 0.112 ML-kNN 0.192 0.385 0.087 0.692 0.336 0.010
0.065 0.051 0.493 0.113 BR-MLM 0.297 0.694 0.216 0.780 0.422 0.038 0.265 0.159
0.993 0.180 ML-MLM 0.315 0.703 0.212 0.789 0.406 0.038 0.299 0.160 0.994 0.193
LLS-MLM 0.303 0.683 0.218 0.783 0.422 0.040 0.266 0.162 0.993 0.192 NN-MLM
0.307 0.681 0.213 0.783 0.423 0.042 0.259 0.160 0.993 0.195