Learning Label-Specific Multiple Local Metrics for Multi-Label Classification

1 Introduction

Different from multi-class classification[Jia et al., 2023], multi-label classification aims to model real-world objects with rich semantics, where each multi-label example is represented by an instance while associated with multiple labels simultaneously [Zhang and Zhou, 2014; Liu et al., 2021]. As a practical machine learning paradigm, multi-label classification has been widely applied in various real-world application, such as text categorization [Xu et al., 2023], bioinformatics analysis [Li et al., 2023], etc.

∗Corresponding author.

Similarity is a crucial concept in machine learning that reveals the degree of connectedness between objects. The predefined similarity metric, such as the Euclidean distance, face challenges in universal adaptation across diverse scenarios. In response, Distance metric learning [Xing et al., 2002] has emerged as a solution to learn task-specific distance metrics by leveraging side information such as linkages and comparisons derived from examples. This approach autonomously refines similarity measurements beyond the limitations of the predefined metric. The learned distance metrics align with the inherent relationships between examples, ensuring that similar intra-class instances exhibit proximity, while distances between dissimilar inter-class instances are sufficiently large. Through the utilization of adaptively learned distance metrics, the efficacy of distance metric learning has been substantiated in enhancing k-nearest neighbor (KNN) classifiers on single-label examples[Song et al., 2021; Li and Lu, 2022; Chen et al., 2023]. Given the effective modeling of semantic similarity among examples achieved through distance metric learning, there exist the potential for simple KNN classifiers to achieve state-of-the-art classification performance.

In light of the remarkable capability for measuring semantic similarities, distance metric learning has been extended to multi-label scenarios in recent years, a.k.a. multi-label metric learning [Liu and Tsang, 2015; Gouk et al., 2016; Sun and Zhang, 2021; Mao et al., 2023]. Multi-label metric learning aims to assess the more intricate semantic similarities among examples with rich semantics. Experimental evidence has demonstrated its capability to enhance the performance of KNN-based multi-label classifiers, such as BRKNN [Boutell et al., 2004] and ML-KNN [Zhang and Zhou, 2007], thereby facilitating multi-label classification. Existing multi-label metric learning approaches learn consistent metrics across all multi-label instances in the label space. Although such consistent multi-label metric learning framework has achieved favorable outcomes, it might be suboptimal as they neglect the fact that multi-label instances exhibit nonlinear distribution characteristics in each label space. For example, in multimedia annotation, the label "sun" is applicable to images depicting forests as well as those representing urban environments. Likewise, in text categorization, the label "president" manifests in both political and economic textual contexts. This implies that in each label space, the distribution of multi-label instances exhibits a high degree of nonlinearity. Consequently, in such cases, employing a single consistent metric encounters formidable challenges in simultaneously pushing similar instances closer while pulling dissimilar instances further away.

With the above observations, we present LSMM, a LabelSpecific Multi-Metric learning framework for multi-label classification, where nonlinear distribution characteristics of multi-label instances are considered by learning label-specific multiple local metrics for different instances on the shoulder of a global one. Specifically, multi-label instances within each label space can be divided into several disjoint partitions through either semantic-based or cluster-based partition strategies, in each of which a local metric is trained to separate the instances locally. To take label correlation into consideration, a global metric is introduced to implicitly exploit high-order label correlations across all labels. The global metric serves as the foundation to reveal the common characteristics among multi-label examples, while the label-specific local metrics act as local biases, depicting the individuality of different instances in each label space. The combination of the global metric and label-specific local metrics is utilized to measure the semantic similarities between multi-label instances in each label space, under which similar intra-class instances are pushed closer and inter-class instances are pulled apart. Comprehensive experiments on benchmark multi-label datasets validate the superiority of LSMM in learning effective similarity 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 LSMM framework. Section 4 reports experimental results of comparative studies over benchmark multilabel datasets. Section 5 concludes this paper.

2 RelatedWork

Multi-Label Classification. In the last decades, numerous approaches have been proposed to tackle multi-label classification problem [Zhang and Zhou, 2014; Liu et al., 2021]. To deal with the challenge of an exponential-sized output space, modeling label correlations has become a mainstream strategy to solve this problem. Generally speaking, these approaches can be grouped into three categories, differing in the order of label correlations under consideration. The order of label correlations 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 [Zhu et al., 2017; Yu and Zhang, 2021], and a high-order manner by exploiting relations among a subset or all labels [Zhang et al., 2021; Si et al., 2023]. BR-KNN [Boutell et al., 2004] and MLKNN [Zhang and Zhou, 2007], as the most classic first-order multi-label classification methods, extend KNN to the multilabel scenario and have achieved certain results in multi-label classification tasks. However, due to the neglect of label correlations, their performance is usually inferior to secondorder and high-order methods. In addition, another significant reason for their insufficient performance is their heavy reliance on the chosen similarity metric. In the absence of prior knowledge, the predefined Euclidean metric used in BRKNN and ML-KNN is often unsuitable for all scenarios.

Distance Metric Learning. To address the limitations imposed by predefined metrics, distance metric learning is proposed to learn task-specific similarity metrics, mainly for single-label examples [Xing et al., 2002; Weinberger et al., 2005; Schroff et al., 2015]. By leveraging various types of supervision extracted from examples, such as linkages and comparisons, distance metric learning aims to align the learned distance metrics with the intrinsic relationships between examples, i.e. similar instances are close to each other and dissimilar instances are far away from each other. In distance metric learning, the Mahalanobis metric is extensively employed as a substitute for the Euclidean metric due to its broad applicability as a general form of the Euclidean metric and its efficient optimization capabilities [Ye et al., 2019; Ye et al., 2020; Ren et al., 2022; Zhao and Yang, 2023]. The Mahalanobis distance between instances is essentially equivalent to the Euclidean distance within the metric space. The superiority of distance metric learning has been substantiated in improving KNN classifiers on single-label examples [Liao et al., 2021; Song et al., 2021; Li et al., 2022; Chen et al., 2023]. With the effective modeling of semantic similarity among examples accomplished by distance metric learning, there is the potential for simple KNN classifiers to achieve state-of-the-art classification performance.

Multi-Label Metric Learning. In recent years, distance metric learning has been extended to the multi-label scenario to measure the more complicated semantic similarities between multi-label examples. To the best of our knowledge, there are four available multi-label metric learning approaches, namely LM [Liu and Tsang, 2015], LJE [Gouk et al., 2016], COMMU [Sun and Zhang, 2021], and LIMIC [Mao et al., 2023]. LM utilizes a large margin formulation to create a shared metric space, preserving the similarity relationships from the feature space to the label space. LJE learns a metric that projects instances into a metric space, where the Euclidean distance is a good approximation of the Jaccard distance between labels. COMMU constructs a compositional metric by modeling structural interactions between the feature and label spaces, exploring the integrated semantics of all labels. LIMIC learns a consistent metric in each label space and employs label co-occurrence to constrain the dependencies between multiple metrics. The multi-label metric learning approaches above all learn consistent metrics across all instances in the label space, which might be suboptimal as they neglect the fact that multi-label instances exhibit nonlinear distribution characteristics in each label space. In the next section, our proposed LSMM framework is introduced.

3 The LSMM Framework

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 qdimensional indicator vector y = [y1 , y2 , . . . , yq ] ∈ {0, 1}q is 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.

Let Sd+ denotes the cone of Positive Semi-Definite (PSD) d×d matrices. Given a metric M ∈ Sd+, the (squared) Mahalanobis distance between a pair (xi, xj ) is (xi-xj )⊤M(xixj) = ⟨M, Aij⟩ = Tr(MAij). The outer product of the pair difference is Aij = (xi -xj)(xi -xj)⊤ ∈ Sd+ [Bellet et al., 2015]. 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, i.e.

Generally speaking, there are several advantages to learning transformation L rather than metric M. On one hand, transformation L does not have a PSD constraint, eliminating the need for a PSD projection step, in turn, accelerates the optimization process [Kulis, 2013]. In addition, the transformation decomposition often leads to low-rank metrics, proving advantageous in many real-world applications [Zhang and Zhang, 2017]. It is also noteworthy that although the decomposition leads to non-convex problems, satisfactory solutions can still be obtained. Based on the above consideration, we learn transformation L rather than metric M in this paper.

3.2 Label-Specific Multi-Metric Learning

To begin with, we introduce the construction procedure of label-specific side information, which is used to direct the learning process of metrics.

For the p-th label lp, the set of positive examples Pp as well as the set of negative examples Np are determined by considering the relevance of each example to lp, i.e.

The label-specific side information w.r.t the label lp is constructed from all possible pairwise combinations of training examples, denoted as Tp = {(xi, xj, θp ij )}, where θp ij ∈ {-1, 1} indicates whether xi and xj share relevance w.r.t the label lp. Specifically, θp ij = 1 implies that instances xi and xj are considered similar due to their simultaneous presence (or absence) of the label lp, i.e. (xi ∈ Pp ∧xj ∈ Pp)∨(xi ∈ Np ∧ xj ∈ Np), while θp ij equals -1 otherwise. Let Tp represent the number of pairs in Tp, and (xi, xj) ∼ Tp denote the enumeration of a total of Tp pairs from the label-specific side information Tp. In practice, there is no need to compute all pairs of side information, as this may lead to substantial computational burden. Opting for a judicious selection of targets (denoted as kt) and imposters (denoted as ki) among the nearest neighbors can mitigate computational load and enhance the efficiency of the training procedure, where targets indicate instances similar to an anchor and imposters otherwise. [Weinberger and Saul, 2009; Ye et al., 2019; Ye et al., 2020]. In this paper, kt and ki are set to 20.

Next, we present two simple yet effective partition strategies, i.e. semantic-based partition and cluster-based partition, designed to divide each label space into several disjoint partitions. In each partition, a local metric is trained to separate the instances locally. Furthermore, a global metric is introduced to implicitly exploit high-order label correlations across all labels. In this way, different instances can be measured with the combination of a global metric and corresponding labelspecific local metrics, as opposed to a consistent metric.

Semantic-based Partition. The first strategy is to assign different local metrics to positive and negative examples in each label space. For the p-th label lp, the (squared) distance between a pair (xi, xj) is calculated as

Here, s(xi) = yp i ∈ {0, 1} is a semantic indicator function. L0 serves as the foundation to reveal the common characteristics among multi-label examples, while the label-specific local metric Ls(xi) p act as a local bias, depicting the individuality of xi in the p-th label space. Our purpose is to push similar instances closer, while dissimilar instances far away from each other. Therefore, we formulate the following optimization problem:

Here, γ and α are predefined non-negative threshold values, which can differ for similar and dissimilar pairs. ℓ(·) is a convex and non-increasing loss function. If two instances xi, xj possess (or do not possess) the label lp simultaneously, i.e. θp ij = 1, then the loss equals 0 when their distance is smaller than γ/α. Conversely, when they are dissimilar (θp ij = -1), their distance should exceed γ/α. By optimizing Eq.(4), the learned metrics require that similar instances have small distances, while dissimilar instances are sufficiently far apart. Besides, λ1 and λ2 serve as non-negative weights to balance the impact of the regularization terms. Intuitively, for a fixed value of λ2, a large value of the ratio λ1/λ2 tends to make the model learn a single global metric L0 across all labels ( Ltp are nearly equal to zero). Conversely, for a fixed λ1, a small value of the ratio λ1/λ2 tends to make all label-specific local metrics unrelated (L0 nearly equal to zero). In this paper,

γ and α are fixed to 2 and 0.4 respectively, and 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 besides γ and α, which further improves the generalization ability of the learned metrics.

Cluster-based Partition. The second strategy is to assign different metrics to different clusters. In this paper, the popular k-means algorithm [Jain et al., 1999] is adopted due to its effectiveness and simplicity. Assuming that all multi-label instances are divided into C disjoint clusters D = C 1 ∪C 2 . . . ∪ C C , the (squared) distance between a pair (xi, xj) in the p-th label space is calculated as

Here, c(xi) ∈ {0, 1, . . . ,C} is a cluster indicator function. The optimization problem is formulated as follows:

In this paper, C is set to 3. Besides, the similar instantiations and properties have been elaborated on in the previous paragraph. Therefore, we do not repeat them here.

3.3 Optimization Procedure

In order to solve the unconstrained nonlinear optimization problems as shown in Eq.(4) and Eq.(7), we employ the Limited-memory Broyde-Fletcher-Golfarb-Shanno (L-BFGS) algorithm [Liu and Nocedal, 1989], which is particularly suited for problems with a large number of optimization variables. Let Lse and Lcl denote the objective functions of the semantic-based and cluster-based partition strategies in Eq.(4) and Eq.(7) respectively. L-BFGS iteratively optimizes the objective functions with resort to the first-order derivatives of the functions.

For the semantic-based partition strategy, the first-order derivatives of Lse w.r.t L0 and {L1p , L0p}qp=1 respectively are

where σp ij is a piecewise function defined as follows:

For the cluster-based partition strategy, the first-order derivatives of Lcl w.r.t L0 and {L1p , L2p , . . . , LCp }qp=1 respectively are

where ζ p ij is a piecewise function defined as follows:

The complete procedure of LSMM can be found in Appendix A. After learning the global metric and label-specific multiple local metrics with the above LSMM framework, the distances between multi-label instances can be measured with the combination of the global metric and corresponding labelspecific local metrics according to Eq.(3) and Eq.(6). Therefore, the associated label set of an unseen multi-label instance can be easily predicted by resorting to KNN-based multi-label classifiers, such as BR-KNN and ML-KNN.

• 1 http://mulan.sourceforge.net/datasets.html

2 http://palm.seu.edu.cn/zhangml/Resources.htm#data

3 https://waikato.github.io/meka/datasets/

Table 1: Characteristics of experimental datasets.

4 Experiments

4.1 Experimental Setup

Datasets. Nine benchmark multi-label datasets with diversified properties are employed for comprehensive performance evaluation. Table 1 summarizes the characteristics of each experimental dataset D, including the number of examples |D|, number of features dim(D), number of labels L(D), label cardinality LCard(D), and domain of datasets. For all the datasets except emotions and birds, we use principal component analysis as a preprocessing to reduce the dimensionality and retain 95% of the information.

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 LSMM framework in learning effective similarity metrics for multi-label classification, BR-KNN [Boutell et al., 2004] and ML-KNN [Zhang and Zhou, 2007] are introduced as subsequent multilabel classification methods after learning similarity metrics. Our semantic-based and cluster-based partition approaches are denoted as LSMM-SE and LSMM-CL respectively.

Given a KNN-based multi-label classification approach A ∈ {BR-KNN,ML-KNN} and a multi-label metric learning algorithm B, the coupling version of them is denoted as A-B. The predictive performance of A-LSMM-SE and ALSMM-CL are compared against other state-of-the-art multilabel metric learning algorithms coupled with A to manifest whether the proposed LSMM framework does learn effective similarity metrics and improve the generalization performance of KNN-based multi-label classification.

In this paper, four state-of-the-art multi-label metric learning algorithms are employed to instantiate B with suggested parameter configurations in respective literature:

• LM [Liu and Tsang, 2015]: A margin-based multi-label metric learning approach that learns a shared metric by
• preserving the similarity relation from the feature to label space [suggested configuration: η = 0.4, C = 10].
• LJE [Gouk et al., 2016]: An integration-based multilabel metric learning approach that employs Jaccard distance between labels to provide more fine-grained side information [suggested 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 the feature and label space [suggested configuration: α, θ ∈ {0.2, 0.4, . . . , 0.8}, C = 10].
• LIMIC [Mao et al., 2023]: A decomposition-based multi-label metric learning approach that learns a consistent metric in each label space and employs label cooccurrence to constrain the dependencies between multiple metrics [suggested configuration: γ = 2, λ1, λ2 ∈ {10-3 , 10-1 , . . . , 103 }].

For the proposed LSMM-SE and LSMM-CL approaches, regularization parameters λ1 and λ2 are searched in {10-1 , 1, . . . , 103 } and {10-3 , 10-2 , . . . , 10} respectively. The number of nearest neighbors (denoted as k) in KNN and ML-KNN is set to 10, which is consistent with previous multilabel metric learning works for fair comparisons. We take out 10% examples in each dataset as a hold out validation set for hyperparameter searching and perform ten-fold crossvalidation on the remaining 90% examples to evaluate the above approaches on the nine benchmark multi-label datasets.

Due to page limit, Table 2 reports detailed experimental results in terms of Hamming loss and Ranking loss. The results on other metrics can be found in Appendix B.1. Furthermore, pairwise t-test [Dietterich, 1998] at 0.05 significance level is conducted to demonstrate whether the performance difference between LSMM-SE (LSMM-CL) and other comparing multi-label metric learning algorithms coupled with A ∈ {BR-KNN,ML-KNN} is significant statistically, where the resulting win/tie/loss counts are also reported in Appendix B.1. Based on these results, it is impressive to observe that:

• The prediction performance of BR-KNN and ML-KNN is significantly improved after coupling multi-label metric learning algorithms. In particular, our proposed LSMMSE (LSMM-CL) approach significantly enhances the performance of BR-KNN and ML-KNN in 88.9% (92.6%) and 94.4% (92.6%) of cases, respectively. The results clearly demonstrate the effectiveness of multi-label metric learning for improving KNN-based multi-label classification methods.
• Across all evaluation metrics, our proposed LSMM-SE and LSMM-CL approaches have demonstrated significantly improved performance compared to other multilabel metric learning algorithms. One one hand, in terms of BR-KNN, LSMM-SE (LSMM-CL) significantly outperforms LM, LJE, COMMU, and LIMIC in 75.9% (87%), 94.4% (100%), 87% (88.9%), and 77.8% (85.2%) of cases, respectively. On the other hand, in terms of MLKNN, LSMM-SE (LSMM-CL) significantly outperforms them in 81.5% (85.2%), 100% (100%), 94.4% (94.4%), and 72.2% (75.9%) of cases, respectively. The superior

performance provides persuasive evidence for our proposed LSMM framework in learning effective similarity metrics for multi-label classification.

In addition to comparing our proposed LSMM-SE and LSMM-CL with state-of-the-art multi-label metric learning algorithms, we further evaluate LSMM-enhanced BR-KNN and ML-KNN against four state-of-the-art non-metric learning multi-label classification approaches with different order of label correlations under consideration:

• LIFT [Zhang and Wu, 2014]: A first-order multi-label classification approach that exploits label-specific features [suggested configuration: r = 0.1].
• RELIAB [Zhang et al., 2021]: A high-order multi-label classification approach that leverages implicit relative labeling-importance information [suggested configuration: mode = global, τ ∈ {0.1, 0.2, . . . , 0.5}, and λ ∈ {10-3 , 10-2 , . . . , 10}].
• WRAP [Yu and Zhang, 2021]: A second-order multi-label classification approach that jointly performs label-specific feature generation and classification model induction [suggested configuration: λ1, λ2 ∈ {0, 1, . . . , 10}, λ3 = 10, and α = 0.9].
• HOMI [Si et al., 2023]:A high-order multi-label classification approach that constrains the high-rank of

the label matrix and depict high-order label correlations explicitly [suggested configuration: β, γ, ∈ {10-2 , 10-1 , . . . , 102 }, λ = 1, s = 10].

Detailed experimental results and resulting win/tie/loss counts of pairwise t-test at 0.05 significance in terms of six evaluation metrics are reported in Table 3 and Appendix B.2. The results clearly demonstrate that, although the performance of simple BR-KNN and ML-KNN are inferior to stateof-the-art multi-label classification approaches, the LSMMenhanced version achieve statistically superior or at least comparable performance against state-of-the-art multi-label classification approaches. The results once again validate the superiority of our proposed LSMM framework in learning effective similarity metrics for multi-label classification.

4.3 Further Analysis

Ablation study. To validate the usefulness of the introduced global metric when learning label-specific multiple local metrics, two variants called LSMM-SE-N and LSMM-CLN are implemented by learning label-specific multiple local metrics directly. Table 4 reports detailed experimental results of BR-KNN coupled with LSMM-SE, LSMM-CL, and variants in terms of Average precision. We can observe clear performance degradation with variants, demonstrating the usefulness of the global metric in LSMM framework. Similar results can be observed on other evaluation metrics.

Sensitivity analysis. λ1 and λ2 serve as primary trade-off parameters in LSMM, balancing the impact of the global and label-specific multiple local metrics. Figure 1 provides an illustrative example of how the performance of BR-KNNLSMM-SE changes with varying values of λ1 and λ2 (dataset: emotions, image; evaluation metric: Average precision). As shown in Figure 1, the performance of BR-KNN-LSMM-SE is quite sensitive to the values of λ1 and λ2. This demonstrates again the effectiveness of the global metric in exploiting label correlation. Similar results can be found in other cases.

Complexity analysis. In LSMM, the main computation lies in the gradient calculation and update for the global and labelspecific multiple local metrics. The training complexity of one iteration for LSMM-SE, LSMM-CL are O(q(nktkid2 + 2dn2 +2d3 )), O(q(nktkid2 +Cdn2 +Cd3 )) respectively. It is noteworthy that LSMM learns multiple metrics of which the number equals 2q + 1 (for LSMM-SE) or Cq + 1 (for LSMMCL), which could be hard to generalize to datasets with huge labels, i.e. extreme multi-label learning [Liu et al., 2021]. This is unavoidable if considering label-specific metrics. We will leave efficiency improvement for future work.

5 Conclusion

In this paper, we present a novel label-specific multi-metric learning framework LSMM for multi-label classification, where nonlinear distribution characteristics of multi-label instances are considered by learning label-specific multiple local metrics for different instances on the shoulder of a global one. Comprehensive experiments verify LSMM outperforms existing consistent multi-label metric learning algorithms in learning effective similarity metrics. Furthermore, we observe that when coupled with LSMM, simple BR-KNN and ML-KNN also have the potential to approach or even surpass state-of-the-art multi-label classification methods. However, LSMM learns multiple metrics, which could be hard to generalize to extreme multi-label learning. This is unavoidable 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.

Acknowledgements

The authors wish to thank the anonymous reviewers for their helpful comments and suggestions. This work was supported by the National Science Foundation of China (62176055), and the Big Data Computing Center of Southeast University.