Label Specific Multi-Semantics Metric Learning for Multi-Label Classification: Global Consideration Helps

1 Introduction

Multi-label classification deals with the problem where an instance can be associated with multiple labels simultaneously [Zhang and Zhou, 2014; Liu et al., 2021]. As a practical learning paradigm involving instances with multiple semantics, multi-label classification has been widely driven by realworld applications, such as multimedia annotation [You et al., 2020], text categorization [Tang et al., 2020], bioinformatics analysis [Chen et al., 2017], information retrieval [Gopal and Yang, 2010], and so on.

∗The work was done when Wei Wang was with Southeast University.

†Corresponding author.

Similarity elucidates the closeness of connections between instances and is usually reflected by their distances. The predefined distance measurement between instances, e.g. Euclidean distance, is difficult to be adapted for all scenarios [Bellet et al., 2015]. Therefore, metric learning [Xing et al., 2002; Shental et al., 2002; Goldberger et al., 2004] was proposed to take advantage of side information like linkages and comparisons between instances. It automatically learns better distance measurement than the Euclidean one, with which the distance between a pair of instances is consistent with their given relationship, i.e. similar intra-class instances are close to each other, and the distances between dissimilar inter-class instances are large enough. With an adaptively learned distance measurement, the superiority of metric learning has been verified on single-label data for improving similarity/distance-based classification models [Davis et al., 2007; Weinberger and Saul, 2009; Schroff et al., 2015]. Under the single-label scenario, semantic similarity/dissimilarity is easily available by considering whether two instances have the same label. Nevertheless, in the multi-label scenario, it is impractical to measure semantic similarity/dissimilarity by considering each label as an equivalent contribution due to the complicated semantics of multi-label data. As a result, it is much more difficult to learn appropriate metrics to characterize the latent semantic similarity/dissimilarity between multi-label data than single-label ones.

In view of the powerful representation capability of latent semantic space, metric learning has been applied to multilabel classification in recent years [Liu and Tsang, 2015; Gouk et al., 2016; Sun and Zhang, 2021], a.k.a. multi-label metric learning, for characterizing more complicated semantic similarity between multi-semantics instances. Existing multi-label metric learning approaches have focused on fusing multi-semantic label information to construct a common distance measurement across all the labels, and then learn one single global metric to characterize the underlying semantic similarity/dissimilarity. Nevertheless, such single-semantics metric exploitation strategies are not consistent with the intrinsic properties of multi-label data possessed of rich semantics. To capitalize on the inherent multi-semantic properties of multi-label data, it is reasonable and important to consider multiple label-specific distance measurements to demonstrate data structures and relationships when constructing latent label semantic space.

Based on the above observations, this paper presents the first attempt towards multi-semantics metric learning for multi-label classification. A novel approach named LIMIC, i.e. Label SpecIcs Multi-SemantIcs MetriC Learning for Multi-Label Classification, is proposed accordingly. Different from existing multi-label metric learning approaches considering only one single global metric, LIMIC learns multiple label-specific semantic metrics on the shoulder of the global one. The global metric plays a fundamental role in LIMIC, which considers the side information generated across all the labels to reveal the common characteristics of multilabel data, while each label-specific local metric is a local bias, which depicts the individuality of the corresponding semantic space. In this way, the relationship between instances w.r.t each specific label can be measured in the latent semantic space formed by the combination of the global metric and the corresponding label-specific local metric. To take label correlation into consideration, a metric-based label correlation regularization is further introduced based on label co-occurrence to maintain consistency between correlated label spaces. Extensive experiments on benchmark multi-label data sets validate the superiority of LIMIC in learning effective distance metrics for multi-label classification.

The rest of this paper is organized as follows. Section 2 briefly reviews related works. Section 3 presents details of the proposed LIMIC approach. Section 4 reports experimental results of comparative studies over benchmark multi-label data sets. Section 5 concludes this paper.

2 RelatedWork

Multi-Label Classification. As a practical and challenging machine learning paradigm, multi-label classification has been studied extensively in recent years [Zhang and Zhou, 2014; Liu et al., 2021]. To tackle the challenge of exponential-sized output space, label correlation exploitation has been adopted as the most popular strategy. Generally speaking, these approaches can be roughly grouped into three categories, which differ in the order of label correlation considered. The order of label correlation can be considered in a first-order manner by treating each label independently [Boutell et al., 2004; Zhang and Zhou, 2007], a second-order manner by exploiting pairwise interactions between labels [F¨urnkranz et al., 2008; Zhu et al., 2017], and a high-order manner by exploiting relations among a subset or all labels [Tsoumakas et al., 2010; Feng et al., 2019]. In addition to label correlation exploitation, another effective strategy to facilitate multi-label classification is to manipulate the feature space. Dimensionality reduction [Siblini et al., 2021] and feature selection [Pereira et al., 2018] over the original feature space serve as the most common strategies for feature manipulation. Furthermore, there are other feature manipulation strategies such as generating discriminative meta-level features from original features [Canuto et al., 2016], aligning latent space for features and labels [Yeh et al., 2017; Chen et al., 2019a], and exploiting multi-view representation [Xing et al., 2018] or label-specific features [Zhang and Wu, 2014; Hang and Zhang, 2021; Hang et al., 2022] for multi-label data.

Metric Learning. Different from the traditional feature manipulation strategies mentioned above, metric learning has been proposed as an alternative feature manipulation strategy. The superiority of metric learning has been verified on single-label data for improving similarity/distance-based classification approaches [Niu et al., 2014; Ye et al., 2019; Ye et al., 2020]. With supervision from various types of side information like linkages and comparisons between instances, metric learning resorts to a suitable similarity or distance measure between instances [Xing et al., 2002; Weinberger and Saul, 2009]. In metric learning, Mahalanobis metric is widely used to replace the Euclidean measurement since it generalizes the Euclidean measurement and can be optimized efficiently [Kulis and others, 2013; Bellet et al., 2015]. Furthermore, Euclidean distance in the transformed space can be viewed as Mahalanobis distance in the original space equivalently. By leveraging such a metric, similar instances tend to have small distances while dissimilar ones are pushed away from each other. Besides, the metric contributes to discovering semantic relationships between instances effectively. Generally speaking, the single metric characterizes the average of data [Weinberger et al., 2005; Davis et al., 2007], which represents correlation patterns making relationships between instances in accordance with the provided side information.

Multi-Label Metric Learning. To the best of our knowledge, there are three multi-label metric learning approaches available, namely LM [Liu and Tsang, 2015], LJE [Gouk et al., 2016], and COMMU [Sun and Zhang, 2021]. LM exploits a large margin formulation to construct a common metric space, in which the similarity relationship in the input space should be preserved in the output space. LJE aims at learning a metric that can project instances into the feature space where the Euclidean distance provides an estimation of the Jaccard distance between corresponding label vectors. COMMU constructs a compositional metric by modeling structural interactions between feature and label space to explore the integrated semantics of multiple labels. The multi-label metric learning approaches above all focus on fusing multi-semantic label information to construct a common distance measurement across all the labels, and then learn one single global metric to characterize the underlying semantic similarity/dissimilarity. However, these strategies are not consistent with the intrinsic properties of multi-label data possessed of rich semantics and might lead to suboptimal performance in learning distance metrics. In the next section, the first attempt towards multi-semantics metric learning for multi-label classification is introduced

3 The LIMIC Approach

3.1 Preliminaries

Let X = Rd denote the input space and Y = {l1, l2, . . . , lq} denote the label space with q labels. A multi-label example is denoted as (x, Y ), where x ∈ X is its feature vector and Y ⊆ Y corresponds to the set of its relevant labels. Here, a q-dimensional vector y = [y1, y2, . . . , yq] ∈ {0, 1}q can be utilized to denote Y , where yp = 1 when lp ∈ Y and yp = 0 otherwise. Generally speaking, multi-label classification aims to induce a multi-label prediction function h : X → 2Y from a multi-label data set D = {(xi, Yi) | 1 ≤ i ≤ n}. Given an unseen instance x′ ∈ X, its associated label set is predicted as h(x′ ) ⊆ Y.

Meanwhile, let Sd+ denotes the space of d × d Positive Semi-Definite (PSD) matrices. Given a metric M ∈ Sd+, the (squared) Mahalanobis distance between pair (xi, xj) is (xi-xj )⊤M(xi-xj ) = ⟨M, Aij ⟩ = Tr(MAij ). The outer product of the pair difference is Aij = (xi-xj)(xi-xj)⊤ ∈ Sd+. 1 By decomposing the metric into the inner product of transformations L (L ∈ Rd×d′ , d′ ≤ d) as M = LL⊤, the (square) Mahalanobis distance between two instances is equal to their Euclidean distance in a projected space:

Generally speaking, there are several advantages in learning transformation L rather than metric M. Since there is no PSD constraint on transformation L, no PSD projection step is required, which can accelerate the optimization procedure. In addition, the transformation decomposition often leads to low-rank metrics, which can be advantageous in many real-world applications, such as information retrieval. It is also noteworthy that although the decomposition leads to non-convex problems, satisfactory solutions can be obtained as well [Weinberger and Saul, 2009; Parameswaran and Weinberger, 2010; Ye et al., 2020]. Based on the above consideration, we learn the transformation L rather than the metric M in this paper.

3.2 Label-Specific Multi-Semantics Metric Learning

For the p-th label lp, the set of positive training instances Pp as well as the set of negative training instances Np are determined by considering the relevance of each example to lp:

The label-specific local side information w.r.t the label lp is composed of all pairwise combinations between all the training examples as Tp = {(xi, xj , θp ij )} where θp ij ∈ {-1,+1} indicates whether xi and xj have the same relevance w.r.t the label lp. Concretely, θp ij = 1 means the instances xi and xj are similar because they are (or not) in possession of the label lp simultaneously, i.e. (xi ∈ Pp ∧ xj ∈ Pp) ∨ (xi ∈ Np ∧ xj ∈ Np) and θp ij equals -1 otherwise. Let (xi, xj) ∼ Tp denote the enumeration of totally n(n - 1) pairs from the label-specific local side information Tp. Let Tp denote the number of pairs in Tp, and Tp = n(n- 1). In practice, there is no need to compute all the tuples of side information, which may suffer from a severe computational burden. A reasonable amount of targets and imposters selected among the nearest neighbors can retrench computation and facilitate the training procedure, where targets indicate similar instances w.r.t. the anchor and imposters otherwise [Weinberger and Saul, 2009; Chen et al., 2019b; Ye et al., 2019; Ye et al., 2020].

1 In the following descriptions, we do not differentiate "metric" and "transformation", which can be determined from the context.

To take both global and local semantic relationships into consideration, we take advantage of the sum of global transformation L0 and local bias Lp as the distance metric for the label space of the p-th label lp. In this combination, the global transformation represents a common view of semantic measurement, while the local bias conducts adaptation for the individuality of each label-specific semantic space. Specifically, given the global transformation L0 which construct the commonality across all the labels, the p-th local label-specific transformation Lp can be determined by solving the following optimization problem:

Here, γ is a pre-defined non-negative threshold value and can be different for similar and dissimilar pairs. ℓ(·) is a convex and non-increasing loss function. If two instances xi, xj are (or not) in possession of the label lp simultaneously, i.e. θp ij = 1, then the loss equals 0 if their distance with Lp is smaller than γ. On the other hand, when they are dissimilar (θp ij = -1), their distance should be larger than γ. By optimizing Eq.(3), the learned transformation requires similar instances to have small distances, while instances from different classes are far away enough. Besides, λ is a non-negative weight to balance the influence of the regularization term. In this paper, the smooth hinge loss is used to instantiate ℓ(·), which is defined as

The smoothness property of this loss function will facilitate the optimization process. Besides, ℓ(·) also keeps a small margin, which further improves the generalization of Lp.

Based on the above modeling procedures for a single label, we can easily extend the objective function Eq.(3) to the whole label space with q labels. The global transformation L0 and q label-specific local biases L1, L2, . . ., and Lq can be determined by solving the following optimization problem:

3.3 Label Correlation Exploitation

Label co-occurrence is an essential semantic relationship in multi-label classification, which has been proven to be effective prior information for label correlation exploitation [Kurata et al., 2016; Hang and Zhang, 2021]. In this section, we capitalize on the label co-occurrence information to establish the relationship of label-specific metrics, where labels with strong co-occurrence possess similar transformations.

Specifically, we construct a label relation graph based on statistics of label co-occurrence. Let G = (V, E) denote such a label relation graph, where V denotes the set of labels and E denotes the set of edges between label pairs. The adjacency matrix W denotes the weights associated with each edge, representing the strength of the co-occurrence relationship between pairs of labels. We formulate the adjacency matrix W as the symmetric conditional probability matrix. 2 Each element inW is calculated as

where P(lj|li) is the probability that label lj appears when label li appears and the diagonal elements of adjacency matrix W are set to 0. We calculate the adjacency matrix W from the training set.

Intuitively, the stronger the correlation between two labels li, lj is, the more similar the corresponding two label-specific transformations Li, Lj are. On the contrary, if two labels li, lj have a low frequency of co-occurrence, the corresponding label transformations Li,Lj should be dissimilar. Therefore, the objective function for modeling the relation between different label-specific local transformations L1, L2, . . ., and Lq can be formulated as

By introducing the label correlation exploitation strategy shown above into Eq.(5), the overall LIMIC framework can be achieved as follows:

3.4 Optimization Procedure

Let L denote the objective of the LIMIC framework in Eq.(8). Following traditional implementation methods of metric learning algorithms [de Vazelhes et al., 2020; Su´arez et al., 2020], we optimize the LIMIC framework with gradientbased optimization strategies. The detailed procedures are discussed as follows.

2 Actually, the adjacency matrix W can be constructed in numerous alternative ways or even can be implemented in a learnable formulation. We attempt to focus on the label-specific multi-semantics exploitation process and will leave it for further work.

Algorithm 1 The pseudo-code of LIMIC.

Input:

D: a multi-label training set {(xi, Yi) | 1 ≤ i ≤ n} (X = Rd , Y = {l1, l2, . . . , lq} , xi ∈ X , Yi ⊆ Y) λ1, λ2: regularization parameters in Eq.(8)

Output:

L0,L1, . . . , Lq: the learned global and label-specific local transformations

Process:

• 1: Initialize L0 with I or employmulti-label metric learning approaches;
• 2: Initialize L1,L2, . . . , Lq with 0;
• 3: Compute adjacency matrix W according to Eq.(6);
• 4: for p = 1 to q do
• 5: Generate positive set Pp and negative set Np according to Eq.(2);
• 6: Generate label-specific local side information tuples Tp;
• 7: end for
• 8: repeat
• 9: Optimize Eq.(8) over L0,L2, . . . , Lq with accelerated gradient descent according to Eq.(9) and Eq.(10);
• 10: until convergence or maximum number of iterations being reached
• 11: Return L0,L1, . . . , Lq

Initialization. For the global transformation L0, it can be initialized in two ways. We can instantiate the global transformation as an identity matrix, i.e. L0 = I, which equals the Euclidean distance metric. It can also be initialized using existing multi-label metric learning approaches such as LM. In our experiments, we adopt the first strategy. Label-specific local transformations L1, L2, . . ., and Lq can be initialized as zero metrics since they are only complementary components based on L0 for label-specific local distance metrics.

Gradient-based optimization. We utilize accelerated gradient descent [Nesterov, 2003; Boyd et al., 2004] to optimize the global transformation L0 and local transformations L1,L2, . . ., and Lq simultaneously. Let δi,j,p = θp ij (γ - Dis2L0+Lp (xi, xj) and the derivations of L w.r.t L0 and Lp respectively are

where σi,j,p is a piecewise function defined as follows:

Table 1: Characteristics of experimental data sets.

The complete procedure of LIMIC is summarized in Algorithm 1. Firstly, global and label-specific local transformations L0,L1, . . ., and Lq are initialized (Step 1-2). After that, the adjacency matrix W is computed for label correlation exploitation (Step 3) and label-specific side information is generated from the label semantic information (Step 4-7). Finally, an accelerated gradient descent procedure is invoked to optimize L0, L1, . . ., and Lq iteratively (Step 8-10).

After learning the global transformation L0 and multiple label-specific local transformations L1,L2, . . ., and Lq with the LIMIC approach, it is straightforward to calculate the distance between instances in the semantic space of each label according to Eq.(1). Therefore, the associated label set of an unseen instance can be predicted by resorting to classic similarity/distance-based classification strategies such as the k-nearest neighbor (KNN) algorithm.

4 Experiments

4.1 Experimental Setup

Data sets. In this paper, eight benchmark multi-label data sets have been employed for comprehensive performance evaluation. Table 1 summarizes the characteristics of each experimental data set S, including the number of examples |S|, number of features dim(S), number of class labels L(S), feature type F(S), label cardinality LCard(S), i.e. the average number of labels per instance, label density (label cardinality over L(S)) LDen(S), number of distinct label sets DL(S), and proportion of distinct label sets PDL(S).

Evaluation metrics. For performance evaluation, six widely-used evaluation metrics are utilized for multi-label classification, including Hamming loss, Ranking loss, Coverage, Average precision, Macro-F1, and Macro-averaging AUC. Detailed definitions of these metrics can be found in [Zhang and Zhou, 2014].

4.2 Comparative Studies

To validate the effectiveness of the proposed LIMIC approach in learning effective distance metrics for multi-label classification, three similarity/distance-based multi-label classification strategies are introduced as subsequent classification methods after learning the distance metric:

• BR-KNN [Boutell et al., 2004]: A classic multi-label classification approach that decomposes the multi-label
• classification into a set of binary KNN classification tasks [parameter configuration: K = 10].
• ML-KNN [Zhang and Zhou, 2007]: A popular lazy learning approach for multi-label classification with Bayesian inference. [parameter configuration: K = 10].
• RELIAB-KNN [Zhang et al., 2021]: A KNN-based multi-label classification approach that leverages the implicit relative labeling-importance information with local KNN reconstruction [parameter configuration: K = 10, ρ = 0.3, λ ∈ {10-3 , 10-2 , 10-1 , 0, 1, 10}].

Given a similarity/distance-based multi-label classification strategy A ∈ {BR-KNN,ML-KNN, RELIAB-KNN} and a multi-label metric learning algorithm B, the coupling version of them is denoted as A-B. The predictive performance of A-LIMIC is compared with other multi-label metric learning algorithms coupled with A to manifest whether the proposed multi-label metric learning technique does learn effective distance metrics and improve the generalization performance for multi-label classification.

In this paper, three well-established multi-label metric learning algorithms are employed to instantiate B with suggested configurations in respective literature:

• LM [Liu and Tsang, 2015]: A margin-based multi-label metric learning approach that learns a common semantic metric by employing a large margin formulation [parameter configuration: η = 0.4, C = 10].
• LJE [Gouk et al., 2016]: An integration-based multilabel metric learning approach that employs Jaccard distance between label vectors to provide more fine-grained side information [parameter configuration: t = 32, e = 5].
• COMMU [Sun and Zhang, 2021]: A composition-based multi-label metric learning approach that learns a compositional metric by modeling structural interactions between feature and label space [parameter configuration: α, θ ∈ {0.2, 0.4, . . . , 0.8} and C = 10].

For the proposed LIMIC approach, regularization parameters λ1 and λ2 are searched in {10-3 , 10-2 , . . . , 103 }. The number of targets and imposters is fixed to 10 and γ in Eq.(8) is set to 2 which is consistent with conventional metric learning approaches [Weinberger and Saul, 2009; Ye et al., 2020]. Ten-fold cross-validation is employed to evaluate the above approaches on the 8 benchmark multi-label data sets.

Due to page limit, Table 2 reports detailed experimental results in terms of Hamming loss, Ranking loss, and Coverage. The results on other metrics can be found in the supplementary material. Our proposed LIMIC approach coupled with A ∈ {BR-KNN, ML-KNN, RELIAB-KNN} are compared with other coupling versions of multi-label metric learning approaches B ∈ {LM, LJE, COMMU} respectively. Meanwhile, the original version of BR-KNN, ML-KNN, and RELIAB-KNN which adopt the Euclidean metric are also included as compared approaches. For each evaluation, "↓" indicates "the smaller the better" while "↑" indicates "the larger the better". The best performance among compared algorithms is shown in boldface. Furthermore, pairwise t-test at 0.05 significance level is conducted to demonstrate whether the performance difference between A-LIMIC and A-B is significant statistically, where the resulting win/tie/loss counts are reported in the supplementary material. Based on the experimental results reported in Table 2, it is impressive to observe that:

• For similarity/distance-based multi-label classification strategies A ∈ {BR-KNN,ML-KNN, RELIAB-KNN}, the generalization performance has been greatly improved after coupling multi-label metric learning algorithms. Especially, BR-KNN-LIMIC, ML-KNN-LIMIC, and RELIAB-KNN-LIMIC achieve better performance than BR-KNN, ML-KNN, RELIAB-KNN in 89.6%, 81.3% and 87.5% cases respectively. The results validate the effectiveness of metric learning for improving similarity/distance-based classification methods.
• Across all evaluation metrics, BR-KNN-LIMIC, MLKNN-LIMIC, and RELIAB-KNN-LIMIC achieve the best performance in 87.5%, 81.3%, 83.3% respectively over all the multi-label data sets. Meanwhile, BR-KNNLIMIC (ML-KNN-LIMIC, RELIAB-KNN-LIMIC) significantly outperforms corresponding coupled versions of other multi-label metric learning algorithms B ∈ {LM, LJE, COMMU} in 70.8% (62.5%, 83.3%), 79.2% (72.9%, 87.5%), and 47.9% (54.2%, 79.2%) cases respectively. The superior performance of LIMIC provides persuasive evidence for the effectiveness of the labelspecific multi-semantics metric exploitation strategy in learning distance metrics for multi-label classification.

4.3 Further Analysis

Ablation study. In this subsection, the ablation study on several variants of LIMIC is further conducted to analyze the effectiveness of each constituent part. To validate the usefulness of global metric consideration, LIMIC-NG is implemented by learning label-specific local metrics directly. In addition, we implement a variant named LIMIC-NL by removing the label correlation regularization in Eq.(8). Furthermore, LIMIC-NGL is implemented by ignoring both the global metric and label correlation regularization. Table 3 reports detailed experimental results coupled with BR-KNN in terms of Average precision. Pairwise t-test results can be found in the supplementary material. Based on these results, the significant usefulness of global metric consideration and label-correlation exploitation procedures can be validated.

Sensitivity analysis. As shown in Algorithm 1, λ1 and λ2 serve as hyperparameters for LIMIC which indicate the relative importance of the semantic metric and label correlation exploitation parts. To investigate the performance sensitivity of LIMIC approach, Figure 1 gives an illustrative example of how the performance of BR-KNN-LIMIC changes with varying configurations of the hyperparameters λ1 and λ2 (data set: CAL500 and birds; evaluation metric: Average precision). As shown in Figure 1, the performance of BR-KNN-LIMIC is relatively stable as λ1 and λ2 change within a reasonable range, which demonstrates the stability of our approach.

Complexity analysis. Let k, kt, ki, and t denote the number of selected neighbors, number of targets, number of imposters, and dimension of projection. The training complexity of one iteration for LM, LJE, COMMU, and LIMIC are O(q3 + kndq2 ), O(tn2 + tdnlog(n)), O((d + q2 )nktki), and O(q(dn2 + nd2 + d3 )). For LIMIC, the main computation lies in the gradient calculation and update for the global metric and label-specific local metrics. It is noteworthy that LIMIC learns multiple metrics of which the number equals q + 1, which may be slow when applied to date sets with a large number of labels. This is inevitable if considering label-specific metrics. We will leave efficiency improvement for future work.

5 Conclusion

In this paper, the first attempt towards multi-semantics metric learning for multi-label classification is investigated. Different from existing single-metric exploitation strategies, we propose a novel approach LIMIC which exploits multiple latent label-specific semantics for multi-label classification. LIMIC learns one global and multiple label-specific local metrics simultaneously to characterize label-specific semantic space, in which similar intra-class instances are closer while inter-class distances are far away. Comprehensive experiments demonstrate that LIMIC outperforms other wellestablished multi-label metric learning approaches in learning effective distance metrics for multi-label classification. However, LIMIC learns #labels+1 metrics, which could be hard to generalize to extreme multi-label learning. It is inevitable if considering label-specific metrics. It is interesting to investigate towards this dilemma to achieve better performance and tolerable scalability for multi-label metric learning. Furthermore, it is promising to extend our approach to weakly supervised and open-environment scenarios [Zhou, 2022].

Acknowledgements

The authors sincerely express gratitude to all the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Science Foundation of China (62176055). We thank the Big Data Center of Southeast University for providing the facility support on the numerical calculations in this paper.