Year: 2021

Abstract:
Multi-label classification is a challenging structured prediction task in which a set of output class labels are predicted for each input. Real-world datasets often have natural or latent taxonomic relationships between labels, making it desirable for models to employ label representations capable of capturing such taxonomies. Most existing multi-label classification methods do not do so, resulting in label predictions that are incoherent w.r.t the taxonomic constraints, thus failing to accurately represent the fundamentals of the problem setting. In this work we introduce the multi-label box model (MBM), a multi-label classification method that combines the encoding power of neural networks with the inductive bias and probabilistic semantics of box embeddings (Vilnis et al., 2018), which can be understood as trainable Venn-diagrams based on hyper-rectangles. Representing labels by boxes rather than vectors, MBM is able to capture taxonomic relations among labels. Furthermore, since box embeddings allow these relations to be learned by stochastic gradient descent from data, and to be read as calibrated conditional probabilities, our model provides a high degree of interpretability. This interpretability also facilitates the injection of partial information about label-label relationships into model training, to further improve its consistency. We provide theoretical grounding for our method and show experimentally the model’s ability to learn the true latent taxonomic structure from data. Through extensive empirical evaluations on both small and large-scale multi-label classification datasets, we show that MBM can significantly improve taxonomic consistency while preserving or surpassing state-of-the-art predictive performance.

heading: 1 INTRODUCTION
text: Multi-label classification is a machine learning task in which an input is associated with multiple categories. Many real-world multi-label classification datasets in modalities such as text categorization (Lewis et al., 2004), image classification (Lin et al., 2015; Krishna et al., 2016), entity typing (Murty et al., 2018; Onoe et al., 2021), functional genomics (Barutcuoglu et al., 2006; Clare, 2003), and so on, have a rich inter-dependent label structure that can be expressed using a taxonomy graph or a hierarchy. To be useful in practice, a model should produce predictions that are coherent with respect to the label taxonomy. For example, if a book is classified as drama, it should also be classified as fiction according to the label taxonomy of book genres in the left-hand side of Figure 1. More formally, we are given a label taxonomy in the form of a directed acyclic graph G = (L, T ), where (a, b) ∈ T if and only if a is a parent of b in the taxonomy. A model will assign scores sℓ(x) for each label ℓ ∈ L. We say the scores are coherent with respect to the taxonomy if, for all edges (a, b) ∈ T , sa(x) ≥ sb(x), and the model is consistent if this is the case for all inputs x. In the case of the book genre classification example, this implies that sfiction must be greater than or equal to sdrama, regardless of the input.
The problem of producing coherent predictions for multi-label classification has garnered a lot of attention in the machine learning literature (Wehrmann et al., 2018c; Giunchiglia & Lukasiewicz, 2020; Murty et al., 2018; Cerri et al., 2014). Most methods that proposed to improve the coherence in predictions require the complete label taxonomy at inference time, and occasionally at training time as well, making these models hard to scale to large label spaces (Giunchiglia & Lukasiewicz, 2020; Wehrmann et al., 2018c). This brings forth a question: Can we utilize representation learning to model the label-label relationships implicitly in the embedding space?
Vilnis et al. (2018) show that probabilistic box embeddings, which represent concepts as high dimensional hyper-rectangles, can embed DAGs efficiently using the explicit information about the edges. Box embeddings represent edges by box-box containment as shown in Figure 1b. Representing the input and output labels in the same geometric space of boxes allows the multi-label taxonomy to be learned without an explicit taxonomic training signal. Moreover, there exists a large space of possible configurations that represent the same taxonomy, and if the label embeddings in the model gets close to any such configuration, then the model will always produce classifications that are coherent w.r.t the taxonomy, regardless of the input. We show through empirical evidence this is the case, and provide a formal proof for latter.
In this work, we propose the multi-label box model (MBM) that utilizes the geometry and probabilistic semantics of box embeddings to model label-label interactions in multi-label classification. MBM represents labels as boxes using free parameters and uses a deep neural network to embed the inputs in the same space. We perform coherence analysis of the model using two measures and show that MBM not only achieves state-of-the-art predictive performance but it also significantly improves the coherence of predicted scores w.r.t latent label taxonomy. Our analysis further shows that it is possible to retrieve the latent label-label relationships solely by analysing the learnt label representations inside the MBM, endowing the model with high degree of interpretability. Finally, we also present a way to utilize the interpretability of MBM to inject partial information about label-label relationships into the model thereby improving the coherence even further.

heading: 2 RELATED WORK
text: Multi-label classification tasks that exhibit strong label space structure in the form of explicit label taxonomy are termed hierarchical multi-label classification (HMLC) in machine learning literature. Most approaches for such tasks make use of the complete hierarchy at training time. These approaches can be categorized into two buckets (Silla & Freitas, 2010): (1) Local approaches that focus on local information for each label or clusters of labels in the hierarchy and classify them independently (Cerri et al., 2014; Huang et al., 2019), and (2) Global approaches that treat the problem as a structured classification task and take global interactions into account (Belanger & McCallum, 2016). In the most general setting, however, both local and global interactions between labels exist. The recent advances in deep learning (Wehrmann et al., 2018a) propose a specialized neural network architecture called Hierarchical Multi-Label Classification Network (HMCN-R and HMCN-F) that takes into account both local and global interactions by creating an ensemble of classifiers that can be trained using end-to-end gradient based training. However, HMCN does not try to enforce coherence strongly, focusing solely on predictive performance. In order to improve prediction coherence, recent works employ special loss functions on top of a neural network classifier to enforce coherence w.r.t the label taxonomy (Murty et al., 2018; Giunchiglia & Lukasiewicz, 2020). While effective, these approaches still use the label taxonomy explicitly, making them difficult to scale to very large label spaces.
Recent advances in representation learning provide various methods to embed large graphs and taxonomies parsimoniously in non-euclidean spaces (Nickel & Kiela, 2017; Vilnis et al., 2018; Vilnis & McCallum, 2015; Gu et al., 2019). The most prominent of these embedding methods include hyperbolic embeddings (Nickel & Kiela, 2017; Ganea et al., 2018a;b) and box embedding (Vilnis et al.,
2018; Li et al., 2019; Dasgupta et al., 2020a). The use of representations other than Euclidean vectors for improving the coherence of multi-label classification has been limited to specific domains like text (Chatterjee et al., 2021) or specific tasks like entity typing (Onoe et al., 2021). Moreover, while both hyperbolic and box embedding can model hierarchical relationships, it has been shown that the box embedding can also model more general graphs like DAGs much more efficiently than hyperbolic embeddings (Patel et al., 2020). Hence, we propose a model that uses box embedding to capture general label-label relationships without the explicit use of label taxonomy to improve the coherence of model predictions.

heading: 3 OVERVIEW OF BOX EMBEDDINGS
text: Notations: In the problem of multi-label classification, we are given a set of labels L where L = |L|, and an instance can be labeled with an element s ∈ {0, 1}L, where projection to the ith coordinate πi(s) = 1 means that the ith label is true. We call the set of all such labelings S, and the associated probability space (S,P(S), PS). We use I to denote the set of all finite closed intervals [µ−, µ+] in Ω ⊂ R plus the empty set, i.e. I := {[µ−, µ+] ⊂ Ω |µ+ ≥ µ−} ∪ ∅. We denote the smallest σ-algebra containing I as σ(I) and, given a valid finite measure ν, we consider the measure space (Ω, σ(I), ν). As a high dimensional generalization, Id will denote a d-dimensional Cartesian product of I. Definition 1 (Box Embedding (Vilnis et al., 2018)). Let B : Id → S be a measurable function such that B−1 ◦ π−1i (1) = ∏d i [µ − i , µ + i ] ∈ Id. A box embedding is defined as the function Box : L → Id which maps a label ℓ ∈ L to B−1 ◦ π−1ℓ ({1}) ∈ Id.
The definition of box embeddings induces a push-forward measure Q on S such that for any R ⊆ S, Q(S) = ν ◦ B−1(R). The complete joint probability distribution over the labels can be modeled using Q as defined above; however, computing B−1(R) requires the use of inclusion-exclusion principle and hence is intractable for a general R.
In order to avoid local identifiability issues in training, Dasgupta et al. (2020b) interpret µ−i (resp. µ+i ) as the location parameters of random variables M − i (resp. M + i ) that are distributed according to GumbelMax (resp. GumbelMin) distributions, leading to a meta-probabilistic generalization of box embedding which they call Gumbel Box Process. Since GumbelMax (resp. GumbelMin) is a max (resp. min) stable distribution, it enables the computation of the location parameters of the intersection box as given in the following definition.
Definition 2 (Intersection Box (Dasgupta et al., 2020b)). Let A = ∏d i=1[a − i , a
+ i ] and B =∏d
i=1[b − i , b + i ] be two gumbel boxes expressed using their location parameters, then the location
parameters of the intersection of these two gumbel boxes are given as
A∩̃B = d∏ i=1 [ β lse ( a−i β , b−i β ) , − β lse ( −a + i β ,−b + i β )] , (1)
where lse(x, y) = log(exp(x) + exp(y)).
The expected volume of Gumbel boxes involves the Bessel Function of the Second Kind, however, as shown in Dasgupta et al. (2020b), this integral can be reasonably approximated using softplus function leading to the following definition for approximate bessel volume. Definition 3 (Approximate Bessel Volume (Dasgupta et al., 2020b)). For a gumbel box B =∏d i=1[b − i , b + i ] we define the approximate Bessel volume λ : Id → R+ as
λ(B) := d∏ i=1 log ( 1 + exp ( b+i − b − i β − 2γ )) .
In the next section, we formally demonstrate the suitability of box embeddings for capturing taxonomic label relationships, and for that we first prove a couple of useful facts regarding the Gumbel intersection and Bessel approximate volume.
Proposition 1. Approximate bessel volume is monotonic with respect to set containment. That is for two Gumbel boxes A,B,
a−i ≥ b − i and a + i ≤ b + i , ∀i ∈ {1, . . . , d} ⇐⇒ λ(A) ≤ λ(B). (2)
Proof. Follows from the monotonicity of log(1 + exp(.)).
Proposition 2. For any two Gumbel boxes A,B, λ(A∩̃B) ≤ λ(B). Proof. The fact that max(x, y) ≤ lse(x, y), and the statement of proposition 1 together imply the desired result.
Since λ is neither normalized nor additive, it cannot be used as a probability measure on (Ω, σ(Id)). However, we can use proposition 1 and 2 to define a conditional probability model as follows.
Corollary 1. For two gumbel boxes A,B, let PBox(A |B) = λ(A∩̃B)λ(B) , then
(i) For any two gumbel boxes A,B, we have 0 ≤ PBox(A |B) ≤ 1.
(ii) PBox(A |C) ≤ PBox(B |C) for any three gumbel boxesA,B,C, with a−i ≥ b − i , a + i ≤ b + i .

heading: 4 MULTI-LABEL BOX MODEL
text: In order to perform the task of multi-label classification we need to model the conditional probabilities P (Y |X) where Y ∈ S and X is the input. Using definition 1, we define label box embeddings Boxψ : L → Id as
Boxψ(ℓi) := d∏ j=1 [ψ−i,j , ψ − i,j + log(1 + expψ + i,j)],
where ψ−, ψ+ ∈ RL×d are trainable parameters. The input instance X is encoded as a fixed-width element of Id using a parametric instance box embedding Boxθ = Id ◦ Fθ : X → Id, where Fθ : X → Rd is a neural network with parameters θ and Id : Rd → Id defined as
Id(x) := d∏ i=1 [xi − δ, xi + δ],
where δ = 10−5. The conditional probability for Y ∈ S given input X is computed using conditional probability under the Gumbel box model as
PMBM(Y |X;ψ, θ) = L∏ i=1 PMBM(Yi|X,ψ, θ) := L∏ i=1 PBox(B −1 ◦ π−1i ({Y }) |Boxθ(X))
Using the definition of PBox as stated through corollary 1, we get the following expression for the conditional probability of Yi under the model, where the intersection ∩̃ is the Gumbel Intersection and measure λ is Approximate Bessel Volume.
PMBM(Yi = 1|X;ψ, θ) = λ (Boxψ(ℓi) ∩̃ Boxθ(X))
λ(Boxθ(X))

heading: 4.1 MODELING LABEL-SPACE INTERACTIONS
text: In Section 1, we alluded to the fact that the inductive bias of the MBM allows it to efficiently model partially specified first-order label interactions. Now we make this remark more concrete. If the partial specification of label interaction is defined using a taxonomy that can be represented as a directed acyclic graph (DAG), the following proposition shows that MBM has a strong inductive bias towards maintaining coherence in its scores. Proposition 3. LetG = (L, T ) denote a DAG defined over the labels where L is the set of all labels and T = {(ℓi, ℓj) | ℓi, ℓj ∈ L, PD(yi = 1 | yj = 1) = 1} is the set of edges. Then there exists some ψ such that P(ψ,θ)(yi = 1 |x) ≥ P(ψ,θ)(yj = 1 |x), for all x, θ. Proof. For all (ℓi, ℓj) ∈ T , let ψ be such that Boxψ(ℓj) ⊆ Boxψ(ℓi). Note that such ψ exists since for each i ∈ {1, . . . , L}, Boxψ(ℓi) is defined using only ψi. It follows from corollary 1 that PBox(Boxψ(ℓi) |Boxθ(X)) ≥ PBox(Boxψ(ℓj) |Boxθ(X)) for any X, θ.

heading: 4.2 LEARNING
text: The entire MBM is specified using parameters (ψ, θ) where ψ ∈ R2d×L are the label embedding parameters and θ are the parameters of the instance encoder neural network Fθ. Given data D = {(x(1), y(1)), . . . , (x(N), y(N))}, the model parameters are learnt by minimizing negative loglikelihood loss
Lnll(ψ, θ;D) = − D∑ i=1 L∑ j=1 logP (y (i) j |x (i);ψ, θ), (3)
using the ADAM optimizer (Kingma & Ba, 2017). In order to empirically verify the intuition behind proposition 3, we also propose the use of label interaction loss
LG(ψ) = − ∑
(ℓi,ℓj)∈T
s(ℓi, ℓj) + ∑
(ℓi,ℓj )̸∈T
s(ℓi, ℓj) (4)
that utilizes the geometry of box embeddings to inject partial information about label interactions specified using a label taxonomy G = (L, T ). When label interaction loss is applied (MBM-T), the total loss is LT = Lnll + νLG, where ν is a hyperparameter. For the Box model, label interaction score for a pair of labels is defined as
sMBM(ℓi, ℓj) := logPBox(Boxψ(ℓi) |Boxψ(ℓj)). (5)

heading: 5 BASELINES
text: Our choice of baselines reflects the focus of this work, i.e., introducing coherence in prediction using suitable representation spaces. To this end, our baselines consist of a high-performing neural network that only uses Euclidean vector representations (MVM), and another that uses hyperbolic representations (MHM). In order to test the importance of the probabilistic semantics used to formulate MBM, we also include as baseline, a non-probabilistic box model as defined in Abboud et al. (2020). The base input encoder architecture Fθ in all these baselines is same as the one used in MBM.
Multi-label Vector Model (MVM) An input encoder neural network Fθ : X → Rd is used to encode the inputs and a label embedding matrix ψ is used to represent the labels. The conditional probability of labels given the input and label interaction scores are given as
PMVM(yl = 1 |x;ψ, θ) := σ(Fθ(X)TMθ ψl), and sMVM(li, lj) := σ(ψTliMθ ψlj ),
respectively, where σ is the logistic sigmoid function, and Gθ ∈ Rd×d is a matrix of trainable parameters. The parameters (θ, ψ) are learnt through LT (Eq. 3,4). Note that, when label interaction is not being explicitly modeled i.e., ν = 0, M is fixed as the identity matrix and MVM reduces to a special case of multi-layer perceptron.
Multi-label Hyperbolic Model (MHM) As discussed in Chatterjee et al. (2021), the isometry between the Lorentz model and Poincare disk model for hyperbolic geometry can be used produce the retraction formula used to project d-dimensional euclidean vectors to d-dimensional Poincaré ball Bd = { x ∈ Rd | ∥x∥ < 1 } . Here the projection operator Π : Rd → Bd and the distance
d : Bd × Bd → R+ in the hyperbolic space are given as:
Π(x) := x 1 + √ 1 + ∥x∥22 , d(u, v) := arcosh
( 1 + 2
∥u− v∥ (1− ∥u∥22)(1− ∥v∥22)
) .
Specifically, the input is first encoded using Fθ and then projected into Bd. The unnormalized score for each label is computed as the negative of the distance between the hyperbolic projections of encoded input and label representation. Since the hyperbolic distance function consists of arcosh, the negative distance is interpreted as log-probability score. Hence, the conditional log-probability of the labels and the label interaction score is given, respectively, by the following expressions, which are then used to learn the parameters (ψ, θ) in the same way as MVM and MBM.
logPMHM(yl = 1 |x) = −d(Π(Fθ(x)),Π(ψl)) and sMHM(li, lj) := −d(Π(ψli),Π(ψlj )),
Non-probabilistic box model (BoxE): In order to test the importance of the probabilistic semantics used to formulate the MBM, we also include as baseline, a box model that does not use probabilistic semantics. For this, we replace the PMBM with the non-probabilistic score defined in Abboud et al. (2020) and replace the log-likelihood loss (Lnll) with a margin based loss Lmargin. 1

heading: 6 EVALUATION AND RESULTS
text: We evaluate the performance of MBM using 12 real-world multi-label classification datasets (Dimitrovski et al., 2011; Clare, 2003) spanning across three domains: text (Enron), images (Imclef07a, Imclef07d, Diatoms), and functional genomics (Expr, Cellcycle, Derisi, Spo) . These datasets are the ideal test bed as they provide explicit label taxonomies with different connectivity: trees, forests, and more general DAGs. Moreover, all the labels of all training and test instances respect the label taxonomy. THe datasets include both categorical and continuous input features. We convert the categorical features into one-hot feature vectors and standardize all continuous features. The input encoder Fθ uses a common architecture for all models consisting of an MLP with a maximum of 3 layers. We perform a grid search over activations, hidden dimensions, dropout, learning rate and use the best parameters for each model.1 The Mean Average Precision (MAP), that is the mean over the average precision values across instances in the test set, is used to evaluate the predictive performance of the models. Table 1 reports average metric values across 5 runs with different random seeds (the standard error intervals are small and are omitted for the sake of readability).
As seen in Table 1, the predictive performance (MAP) of MBM is better than all other methods on at least 9 out of 12 datasets. To check the statistical significance of our results, following Demšar (2006), we first perform the Friedman test and obtain a p-value of 2× 10−9. The critical diagram of the post-hoc Nemenyi test (Figure 2a) performed after the Friedman test allows us to conclude that difference in predictive performance between MBM and all other models except MVM is statistically significant. Through the more powerful pairwise Wilcoxon test, we find that the performance of MBM and MVM is comparable (p-value of 0.1). Furthermore, from these results, one can conclude with confidence that MBM with its probabilistic formulation preforms significantly better than BoxE, which is the non-probabilistic variant of box embeddings. In the following section, we discuss another important aspect of performance, that is, the coherence of predictions.

heading: 6.1 COHERENCE ANALYSIS
text: MAP is a good metric for predictive performance, however it does not take into account the inconsistencies in the predicted scores w.r.t. the label taxonomy. For instance, recalling the earlier example in Figure 1, a consistent model would always assign higher score to fiction when compared to drama, since a book classified as drama should also be classified as fiction. Since MAP is incapable of capturing such coherence conditions, we perform further analysis to check the coherence of the predicted scores. This is done by considering two opposite perspectives towards coherence evaluation. The first one is a punitive approach, where we count the number of instances that are given inconsistent scores w.r.t the taxonomy. In the second one, a more constructive approach, we try to check the amenability of the model, by applying post-hoc corrections to the predicted scores to enforce coherence. The results of these two approaches are presented by using Constraint Violation (CV) and Mean Average Precision post Coherence correction (CMAP), which are described below. Note that we do not recommend the use of either CV or CMAP as the sole metrics to evaluate the model, we present these as measures to analyse the coherence of the model predictions.
Constraint violation is a punitive measure that quantifies the extent to which the label scores generated by the model violate the partial ordering of the latent label taxonomy regardless of true labels for the instances. Hence, lower value of CV implies higher taxonomic coherence in the predictions.
CV(s) = 1
|D||T | |D|∑ k=1 ∑ (li,lj)∈T 1 ( s (k) i − s (k) j < 0 ) . (6)
Mean Average Precision post Coherence correction (CMAP): Given a complete or partial taxonomy G = (L, T ) for the labels, coherence can be imposed post-hoc by applying a modification
1Please see the Reproducibility Statement after Section 8, for further details on the implementation of the baselines and the experiments.
Table 1: Performance comparison of MBM models with the baselines for the 12 feature based multilabel classification datasets. The left section compares the models that do not require explicit taxonomy, i.e., BoxE, MVM, MHM and MBM. In the left section, the models with the best performance
w.r.t. MAP are highlighted. The right section shows the performance when we include taxonomy information in training through LG(MVM-T, MHM-T and MBM-T), where the highlighted cells indicate an improvement in performance (MAP and CV) w.r.t. the respective non-T model. All metrics reported are averaged across five runs with different seeds.
Dataset Metric BoxE MVM MHM MBM MVM-T MHM-T MBM-T C-HMCNN
MAP↑ 48.41 49.11 39.44 48.35 41.70 38.23 47.88 46.29 CMAP↑ 48.96 46.47 37.54 48.60 38.16 38.47 48.13 46.29ExprFUN CV↓ 5.07 2.75 0.72 2.21 4.12. 1.61 1.52 0
MAP↑ 43.41 42.80 38.68 44.77 38.43 38.54 44.91 42.8 CMAP↑ 43.65 42.55 36.94 44.94 37.15 36.78 45.07 42.8CellcycleFUN CV↓ 2.73 1.73 0.79 1.57 2.68 0.96 0.4 0
MAP↑ 40.23 40.09 37.96 40.81 36.50 37.44 40.67 40.02 CMAP↑ 40.52 39.50 37.25 40.93 32.16 37.43 40.72 40.02DerisiFUN CV↓ 2.54 2.01 0.77 1.34 3.77 1.23 0.05 0
MAP↑ 40.98 40.12 38.21 41.35 35.36 37.24 41.37 33.60 CMAP↑ 41.17 40.07 37.23 41.51 32.59 37.31 41.53 33.60SpoFUN CV↓ 2.21 1.42 0.86 1.53 4.74 2.68 1.21 0
MAP↑ 47.57 58.31 57.05 57.79 52.41 52.08 57.13 56.44 CMAP↑ 48.33 51.64 51.67 57.94 47.09 52.23 57.29 56.44ExprGO CV↓ 4.63 4.46 3.94 3.02 4.51 2.06 3.13 0
MAP↑ 50.48 55.14 52.06 55.93 52.33 52.07 55.14 53.90 CMAP↑ 50.92 49.34 52.24 56.08 47.28 52.26 55.22 53.90CellcycleGO CV↓ 3.57 3.10 1.92 2.93 4.14 2.03 0.62 0
MAP↑ 46.41 53.23 52.23 53.92 51.87 52.22 53.79 52.98 CMAP↑ 47.21 46.77 52.25 54.02 46.79 52.26 53.87 52.98DerisiGO CV↓ 5.26 2.82 1.93 2.66 7.71 2.06 2.55 0
MAP↑ 46.03 53.34 52.18 53.95 51.48 52.25 53.23 52.32 CMAP↑ 45.65 46.82 52.22 54.04 45.71 52.29 53.29 52.32SpoGO CV↓ 5.31 3.28 1.94 2.40 8.56 1.99 0.71 0
MAP↑ 83.43 83.76 79.61 82.08 76.73 79.60 81.32 82.29 CMAP↑ 83.43 75.65 79.63 82.12 59.93 79.63 81.34 82.29Enron CV↓ 0.46 0.79 0.35 0.12 3.02 0.48 0.04 0
MAP↑ 79.38 78.40 47.63 83.47 52.26 47.71 82.75 62.1 CMAP↑ 79.72 71.21 47.65 83.55 45.63 47.73 82.66 62.1Diatoms CV↓ 6.40 7.23 2.03 3.48 4.59 1.93 0.19 0
MAP↑ 72.48 73.97 65.16 74.3 67.51 65.65 74.94 74.64 CMAP↑ 72.44 73.87 64.78 74.52 63.46 64.56 75.14 74.64Imclef07a CV↓ 3.17 2.98 2.27 2.92 12.62 2.49 2.83 0
MAP↑ 83.70 84.04 71.73 85.33 70.16 71.71 84.89 84.69 CMAP↑ 84.15 77.56 71.88 85.58 57.39 71.86 85.25 84.69Imclef07d CV↓ 8.24 9.39 4.47 5.48 8.95 5.44 5.24 0
MAP 4.8 2.9 6.2 1.8 6.8 6.7 2.4 4.4 CMAP 4.2 5.4 6.0 1.6 7.6 5.5 2.0 3.7Avg. Rank ↓ CV 6.9 6.2 2.9 4.6 7.5 4.0 2.7 1.0
function δ : RL → RL to the label-scores produced by the model such that δ(si) − δ(sj) < 0 for all (li, lj) ∈ T . This can be achieved by modifying the score si for each label li to be either the maximum (δMG ) of the scores of any of its descendants or the minimum of the scores of its ancestors (δmG ) in the taxonomy G. Concretely, given the scores s ∈ RL produced by a model, for an input, the two modification functions are given as
δmG (s)i = min lj∈AncG(li)∪{li} sj , δ M G (s)i = max lj∈DesG(li)∪{li} sj , (7)
where AncG(l) and DesG(l) is the set of ancestors and descendants, respectively, of l in the graph G. In practice, one would select whichever post-hoc modification performs better, and we refer to the maximum MAP obtained after applying one of the modification functions δmG , δ M G to the scores as CMAP.2 Intuitively, a CMAP value close to MAP value implies that the model is more perceptive of the latent hierarchy in the label space. As seen from the critical diagram of the Nemenyi test (Figure 2b), when coherence is considered along with the predictive performance (CMAP), MBM outperforms MVM and MHM (with statistical significance) indicating that MBM is much more perceptive of the latent taxonomy compared to MVM. In conclusion, while on one extreme there is MVM, which exhibits good predictive performance but fails to maintain coherence w.r.t the taxonomy, on the other extreme we have MHM that exhibits lowest constraint violations but gives inadequate predictive performance. MBM, however, demonstrates good characteristics on both fronts–predictive performance as well as coherence.
Comparison with the state-of-the-art: C-HMCNN (Giunchiglia & Lukasiewicz, 2020), is the current state-of-the-art method for hierarchical MLC, and includes the modification function δMG (called MCM in their work) in their model directly, applying it to scores produced by a multi-layer perceptron at training as well as inference time.3 This is done by cleverly modifying BCE loss to MCLoss which works well with the modification function during training. There are two key differences between C-HMCNN and MBM that one needs to keep in mind when comparing performance. First, C-HMCNN does not attempt to use the label representations themselves to increase coherence. Second, unlike MBM, C-HMCNN requires the complete label taxonomy at training and inference time. Due to the use of label taxonomy at inference time, C-HMCNN has 0 constraint violations. However, as seen from the Table 1 and the Figure 2, MBM performs significantly better than C-HMCNN w.r.t MAP as well as CMAP (with p-value of 0.002 in Wilcoxon test).

heading: 7 ANALYSIS OF LEARNED LABEL EMBEDDINGS
text: In this section, we analyze the geometry of the learned label embeddings, finding that the simple geometry of box embeddings endows the MBM model with high degree of interpretability. In order to verify that label box embeddings are producing consistent scores by using inclusion in the box space, we inject into the model the taxonomy information through the additional loss term (Eq. 4). As seen from the two right most columns in Table 1, injecting explicit taxonomic information into the label embeddings further reduces the extent of constrain violation for MBM and MHM models. However, it does not aid the MVM model and even drops its predictive performance significantly. This underscores the importance of embedding geometry for inducing taxonomic coherence, and validates our intuition about the arrangement of label embeddings in MBM.
To determine the extent to which the label embeddings capture the latent label taxonomy without it being explicitly provided, we perform ancestor-descendant classification solely using the learned label embeddings. Each pair of labels (li, lj) get a score β(i, j) that is determined using their corresponding label embeddings ψi, ψj . Since MVM and MBM have different geometrical interpretations, we use different scoring for each. Specifically, βMVM(i, j) =
ψi·ψj ∥ψj∥ ,
βMBM(i, j) = sMBM(li, lj). These scores are then compared to true ancestor-descendant relations
2We find that δmG produces lesser change in the scores predicted by all the models (MBM, MVM and MHM), and hence is used as the modification function for this analysis (see Appendix E for further discussion on this)
3Comparision with another competitive baseline HMCN is provided in Appendix D.
in the taxonomy to obtain respective ROC curves as shown in Figure 3. As seen in Table 3, MBM captures the true label taxonomy the best (AUC ≥ 0.87) for all datasets. Furthermore, for hyperberbolic space, it is suggested that the magnitude of embeddings relate to the level of generality in taxonomy (Nickel & Kiela, 2017). We show that the same observation holds for box embeddings, with the vector embedding magnitude replaced by box embedding volume. To see this, we compute the Spearman rank correlation between the number of descendants of a node in the true taxonomy and the embedding magnitude, negative embedding magnitude, and embedding volume for MVM, MHM, and MBM, respectively. The correlation values reported in Table 2 confirm our intuition regarding box embeddings stated above.4 It is interesting to note that as shown by good correlation between the vector magnitude and level of the label node as well as low constraint violations, the MHM model does capture the depth of the label nodes in the taxonomy. However, as shown by the ROC curves in Figure 3, unlike MBM, it fails to capture the exact connectivity of the nodes at different depths in the taxonomy.

heading: 8 CONCLUSION
text: In this work, we demonstrate that box embeddings with its probabilistic formulation can effectively capture taxonomic relations present between labels in multi-label classification without requiring explicit access to the taxonomy. The multi-label box model achieves a fine balance between predictive performance and coherence. Furthermore, we find that the graph relationships between labels can be easily injected via extra supervision during training, increasing the coherence of the model predictions. Since the model has the same computational complexity as a simple vector neural network model (MVM), and unlike C-HMCNN it does not require the label taxonomy, we believe that the proposed model can be scaled to work with extremely large label spaces. Moreover, due to the flexibility of using any neural network encoder this model can be easily extended to different input modalities, such as raw text, images, etc. We wish to pursue these two directions in our future work.
4Refer to Appendix H for scatter plots of box embedding volume vs. the number of children in the label taxonomy.
REPRODUCIBILITY STATEMENT
We have strove make the results reported in this work easily reproducible. In this section, we provide pointers to information necessary to reproduce the results mentioned in this paper. The description of the datasets with various statistics, links to download them, and instructions to pre-process them are provided in Appendix B. The BoxE baseline is further described with expressions for distance and the margin based loss function in Appendix A.1. The hyper-parameter settings for each modeldataset combination (all 96 settings) used to produce the reported results are provided in 3. We also include a discussion on computational complexity of the models in Appendix A.2. Finally, an anonymized version of the code used in this paper is publicly available and can be obtained by following the instructions in A.3.

heading: B DATASETS
text: The 12 datasets used in this work wary greatly in terms of domain, number of labels, number of instances, and the connectivity of label taxonomy. The characteristics of each dataset w.r.t these properties is summarized in 6. These datasets do not require a licence and are available for public usage. The links to the sources for all the datasets are provided in Table 7 below. The continuous features are standardized by removing mean and scaling to unit variance, and the categorical features are encoded as one-hot vectors.

heading: C SIGNIFICANCE TESTING
text: In section 6, we provide the results for Friedman test followed by post-hoc Nemenyi test, and also the result of pairwise Wilcoxon test where the former are not sufficient, i.e. for the case of MVM vs MBM w.r.t MAP. For the sake of completeness, here in table 8, we provide the complete table of pairwise Wilcoxon test from comparing all models with MBM and MBM-T w.r.t all three metrics.

heading: D COMPARISON TO C-HMCNN AND HMCN
text: In our experiments with the official code of C-HMCNN(Giunchiglia & Lukasiewicz, 2020) as well as our re-implementation of the same, we found that C-HMCNN consistently gets lower MAP compared to a well tuned MVM (note that the base MVM results are not reported in the C-HMCNN or HMCN paper). In Giunchiglia & Lukasiewicz (2020), C-HMCNN was shown to outperform HMCN(Wehrmann et al., 2018c). Based on these observations, we considered a well-tuned MVM to be the stronger baseline and only included the results of C-HMCNN (our implementation) in table
Table 6: Summary of the datasets used in experiments. The feature based multi-label datasets span across 3 domains: functional genomics, image and text.
Dataset Domain Input/FeatureType Label Taxonomy #Labels #Instances Train Val Test
Expr FUN Genomics Continuous Forest 500 1636 849 1288 Cellcycle FUN Genomics Continuous Forest 500 1628 848 1281 Derisi FUN Genomics Continuous Forest 500 1608 842 1275 Spo FUN Genomics Continuous Forest 500 1600 837 1266 Expr GO Genomics Continuous DAG 4132 1636 849 1288 Cellcycle GO Genomics Continuous DAG 4126 1625 848 1278 Derisi GO Genomics Continuous DAG 4120 1605 842 1272 Spo GO Genomics Continuous DAG 4120 1597 837 1263 Diatoms Image Continuous Tree 399 1500 565 1054 Imclef07a Image Continuous Tree 97 7000 3000 1006 Imclef07d Image Continuous Tree 47 7000 3000 1006 Enron Text Binary Tree 57 650 338 600
Table 7: The table provides the links to download the data from original source.
Dataset(s) Download Links
Imclef07a, Imclef07d, Enron, Diatoms http://kt.ijs.si/DragiKocev/PhD/resources/doku.php?id=hmc_classification Expr, Spo, Derisi, Cellcycle (FUN/GO) https://dtai.cs.kuleuven.be/clus/hmcdatasets/

heading: CV MBM 0.0004 0.0014 0.0209 - 0.0004 0.0522 0.0034 0.0004MBM-T 0.0004 0.0004 0.30 0.0034 0.0004 0.0639 - 0.0004
text: 1. Table 9 compares our models to the C-HMCNN and HMCN models. Here, the columns with * are taken from their respective papers and these models use the union of train and validation set to train their final model. However, in all of our experiments, we only train on the train set to obtain the final test performance. As seen from the table, except for Imclef07a, MBM performs better than HMCN and C-HMCNN (even with lesser training data).

heading: E MAP AND CMAP
text: In MCL problems, where predictions consistent with a taxonomy are necessary, the model designer might be ready to sacrifice some absolute predictive performance for increased coherence, where the predictive performance can be measure using Mean Average Precision (MAP). First recall that Average Precision (AP) for an instance is the weighted mean of precisions achieved at each threshold, with the increase in recall from the previous threshold used as the weight, and Mean Average Precision (MAP) is the mean of AP across instances. Given data D, let s(k)i = P (yi = 1|x(k)) denote the score generated by the model for label i given the input x(k). Then MAP is computed as
As described in Section 6.1, given the scores s ∈ RL produced by a model, for an input, the two post-hoc modification functions that can be applied to make these score coherent are given as
δmG (s)i = min lj∈AncG(li)∪{li} sj , δ M G (s)i = max lj∈DesG(li)∪{li} sj , (9)
where AncG(l) and DesG(l) is the set of ancestors and descendants, respectively, of l in the graph G.
One can compute MAP after applying either one of the two modification functions. If a human were to make consistent score corrections based on the complete hierarchy, they would either pick the score of a label to be the minimum of its ancestors or maximum of its descendants. Once picked, the same approach has to be applied to all the labels. We argue that in terms of correlation with human judgment, both these methods are equivalent. Hence, one can pick the modification function based on empirical performance of the post-hoc correction algorithm. We observe that δmG , i.e., “min of ancestors” approach, produced higher MAP with both MVM and MBM models compared to δMG . as can be seen in table 10. We believe that ”min of ancestors” works better because it promotes sparsity in predictions, which is essential for the task of MLC.

heading: F PERFORMANCE ON LONG TAIL OF LABELS
text: Since MVM and MBM both are embedding based models, we expect the performance of the MBM model to wary with the label frequency in the same manner as MVM. This hypothesis is corroborated by the following table which shows the spearman rank correlation between the label frequency and the mean average precision (MAP) for that label. The high positive correlation for all the models suggests that the performance of both MVM and MBM often degrades as the frequency of the labels drop. However, as shown by the table 11, both the models perform reasonably well for extremely low frequency labels. Here, tail MAP is the mean average precision for labels with frequency 0.001% or lower.

heading: G EFFECT OF EMBEDDING DIMENSION
text: To study the effect of embedding dimensions on the performance, we plot the MAP, CMAP and CV vs the hidden dimension size for a subset of the datasets. As shown in figure 4, at extremely low dimensions, the MBM model consistently outperforms the MVM. This shows that the favorable inductive bias of the box space induces parsimonious representations.
H EFFECT OF HIERARCHY ON THE MARGINAL SCORE

Review summaries:
The problem tackled in this paper is that of multi-label classification, where class labels form a taxonomy (i.e., a hierarchy), and the goal is to enforce the predictions to comply with the label taxonomy.  This is a well-known problem in machine learning and it is important as it imposes a more structured learning space, by implicitly enforcing predictions to be consistent with the label taxonomy. The approach taken in this paper is based on box embeddings, where the idea is to view classes as boxes in the space, and apply a certain probabilistic semantics of box embeddings to eventually model taxonomic relations between classes. 

Most existing multi-label classification methods predict labels without considering natural/latent taxonomic constraints. This work introduces the multi-label box model (MBM), a method for multi-label classification that combines the encoding power of neural networks with the inductive bias and probabilistic semantics of box embeddings (trainable Venn-diagrams based on hyper-rectangles). MBM has some nice properties: they can be trained via gradient descent from data, and box embeddings can be read as calibrated conditional probabilities. Experiments are conducted on seven benchmark datasets with promising results, and results suggest that the label embeddings seem to capture the latent label taxonomy.

In this work the authors propose a new model for multi-label classification problems. In their model, the authors represent the labels as boxes and they use neural networks to embed the input datapoints in the same space. Thanks to the box representation, the model achieves higher interpretability, and the authors can inject background knowledge (in the form of taxonomies) into the model to improve the coherence of the learnt labels representation with the taxonomy.  The model has been tested on 7 publicly available datasets, and evaluated using three different metrics, namely, CMAP, CV and and MAP.