Exploiting Multi-Label Correlation in Label Distribution Learning

1 Introduction

Label distribution learning (LDL) [Geng, 2016] is a novel learning paradigm that provides fine-grained label information for each instance. Unlike traditional learning paradigms, it introduces the label description degree [Geng, 2016] that is a real value and quantifies the relevance of one label to a specific instance. The label description degrees of all labels form a label distribution, which provides a comprehensive representation of label information. Fig.1 showcases an image from a natural-scene dataset [Geng and Luo, 2014]. The average ratings are rescaled to form a label distribution {0.25, 0.4, 0.25, 0.1}, effectively capturing the varying degrees of importance assigned to labels. LDL utilizes label description degrees to solve label ambiguity [Gao et al., 2017].

∗Corresponding authors.

LDL has an overwhelming output space, exponentially growing with the number of potential labels [Wang and Geng, 2023]. To address this, label correlation has emerged as a promising solution. Many LDL works have proposed to leverage label correlation in the learning processes. To name a few, [Xu and Zhou, 2017] captured the low-rank structure of the label distribution matrix to incorporate label correlation. [Jia et al., 2021] leveraged the low-rank assumption to capture label correlations shared by different groups of samples. They captured label correlations in a local context. Additionally, [Ren et al., 2019] utilized a low-rank matrix to capture global label correlation and further updated it based on different clusters to explore local label correlations. Label correlation helps improve the performance of these LDL methods.

The above LDL algorithms assumed that label distribution has a low-rank structure and relied on it to exploit label correlation. However, [Wang and Geng, 2023] has demonstrated that label distribution matrices are usually full-rank, which challenges the suitability of these approaches with low-rank assumptions. So, we may raise the following question: Is it possible to exploit the low-rank label correlation in LDL more efficiently?

Our work is mainly inspired by two observations. The first one is that low-rank has been extensively applied to multilabel learning (MLL) to capture label correlation [Jing et al., 2015; Liu et al., 2021; Wu et al., 2020; Xu et al., 2016; Yu et al., 2018] since MLL matrices are typically low-rank. The second one is that label distribution has rich supervision information and implicitly contains multi-label. To see that, for the example in Fig. 1, we can observe that the given label distribution contains implicit multi-labels of {tree, mountain, water}. Our basic idea is to introduce an auxiliary MLL process in LDL and then exploit the low-rank label correlation on the MLL part, for example, by assuming the MLL matrix is low-rank. That is, the low-rank assumption is added to the MLL part instead of the LDL part.

Following the strategy, we propose two novel LDL methods, TLRLDL and TKLRLDL, to exploit low-rank label correlation. First, we propose two methods to generate multilabel from label distribution. The first one utilizes a threshold to separate label distribution into multi-label, and the second one selects the top-k labels having the most significant label description degrees as the positive labels. Next, we simultaneously learn label distribution and the generated multi-label and capture the low-rank label correlation in the MLL process. We conduct extensive experiments to justify that the proposed methods outperform existing LDL approaches. Besides, the ablation studies validate the advantages of exploiting the low-rank label correlation in the auxiliary MLL process. To sum up, our significant contributions are as follows:

• As far as we know, this is the first work to introduce an auxiliary MLL process in LDL and exploit the MLL label correlation for LDL to relieve the unsuitability of low-rank label correlation of LDL.
• We exploit label correlation in LDL by capturing the low-rank structure in an auxiliary MLL process, which is more reasonable than directly exploiting the low-rank label correlation of LDL.
• We conduct extensive experiments to validate the advantages of our methods over existing LDL algorithms and the superiority of exploiting the low-rank label correlation in the auxiliary MLL process.

2 RelatedWork

2.1 Label Distribution Learning

As a novel learning paradigm, LDL introduces label distribution to capture the crucial degrees of labels, attracting much interest in machine learning. In this section, we provide a brief overview of the existing studies of LDL.

The existing LDL [Le et al., 2023; Tan et al., 2023] algorithms can be broadly classified into three categories. The first category involves transforming the LDL problem into a single-label learning problem by assigning weights to the training samples. Representative algorithms in this category include PT-SVM and PT-Bayes, which utilize SVM and Bayes classifiers to solve the transformed weighted singlelabel learning problems. The second category focuses on adapting traditional machine learning algorithms to handle the LDL problem. For instance, AA-kNN identifies the k nearest neighbors of an instance and predicts its label distribution by averaging the labels of these neighbors. AABP learns label distribution through the Back-Propagation (BP) algorithm. The third category includes specialized algorithms, such as IIS-LDL and BFGS-LDL, which primarily consider label distribution characteristics. However, these algorithms ignore label correlation.

2.2 Label Correlation in LDL

In recent years, researchers have recognized the challenge of the vast output space of LDL [Gao et al., 2017; Wang and Geng, 2019; Shen et al., 2017; Wang and Geng, 2021; Ren and Geng, 2017] and have developed various approaches to address this issue. These methods can be categorized into three types: (1) global label correlation, (2) local label correlation, and (3) both global and local label correlations. In the first category, [Zhou et al., 2015] introduced a weighted Jeffrey's divergence [Cha, 2007] to capture label correlation by assigning weights based on the Pearson correlation coefficient. [Xu and Zhou, 2017] incorporated the low-rank structure of label distribution by applying trace-norm regularization. In the second category, [Jia et al., 2019] utilized a local low-rank structure to capture the local label correlations implicitly. In the third category, [Ren et al., 2019] introduced LDL-LCLR, a method that leverages global and local label correlations. It utilizes a low-rank matrix to capture global label correlation and updates the matrix based on different clusters to explore local label correlation.

However, many of these works rely on the assumption of low-rank to exploit label correlation. As reported by [Wang and Geng, 2023], the label distribution matrix is generally full rank, which poses a challenge to those exploiting lowrank label correlation of LDL. Instead of directly exploiting the low-rank label correlation of LDL, this study introduces an auxiliary MLL. It exploits the low-rank label correlation on the MLL process, which can efficiently solve the problem mentioned above.

3 The ProposedMethods

Notations Let X = [x1, x2, . . . , xn] ∈ Rn×d be the feature matrix and Y = {y1, y2, . . . , ym} be the label space, where n, m, and d denote the numbers of instances, labels, and the dimension of features, respectively. The training set of the LDL is represented as T = {(x1, d1) , (x2, d2) , . . . , (xn, dn)}, where di = [dy1 xi , dy2 xi , . . . , dym xi ] is the label distribution of the ith sample xi. dyxi is the label description degree of y to xi, which satisfies dyxi ∈ [0, 1] and ∑y dyx = 1. The label distribution matrix is denoted as D = [d1, d2, . . . , dn] ∈ Rm×n . LDL aims to learn a mapping function from T and predict the label distribution for unseen instances.

3.1 Transforming Label Distribution to Multi-Label

This subsection will introduce two methods for transforming label distribution into multi-label. The first is threshold-based degradation, and the second is top-k degradation. Next, we provide details of these two methods.

Threshold-Based Multi-Label Generation

To convert label distribution into multi-label, we simulate users' labelling process when assigning labels to images or adding keywords to texts. Users continue adding the most relevant labels until they perceive the labelling is sufficiently comprehensive [Xu et al., 2019]. Based on that, we can derive multi-label from label distribution through this iterative labelling procedure. The process is outlined as follows:

• For each instance x, find the label yj with the highest description degree dyj x and add it to relevant label set.

• Calculate the sum of the description degrees of all the currently relevant labels H = ∑yj∈Y + dyj x , where Y + is the set of the currently relevant labels.
• If H is less than a predefined threshold T, continue finding the label with the highest description degree from the labels not included in Y, and add it to Y. Repeat this process until H > T .

Following this process, we can generate multi-label from label distribution that mimics how users label data.

Top-k Based Multi-Label Generation

Specifically, for any instance xi, we first sort the label description degrees in descending order. Then, we select the top-k labels with the highest label description degrees as relevant labels and assign the remaining labels as irrelevant labels. The top-k labels with the highest label description degrees are considered relevant for each instance, while the rest are deemed irrelevant.

3.2 AuxiliaryMLL and Label Correlation

Initially, we employ the least square method to learn label distribution and minimize the F -norm loss between the groundtruth label distribution and prediction, which can be formalized as the following:

where W ∈ Rm×d is the parameter matrix, ∥ · ∥F represents the Frobenius norm, and λ is a regularization parameter. Next, we establish the mapping relationship between label distribution and multi-label generated in the previous section. This linear mapping is formulated as follows:

where L ∈ Rm×n is the ML matrix, and O ∈ Rn×n is the transformation matrix. Nonlinear mapping is left for future work. Accordingly, we utilize the low-rank label correlation. However, given the full-rank nature of the label distribution matrix, assuming a low-rank structure does not suit LDL. To address that, we encourage the low-rank structure of the MLL process, which has been widely accepted in MLL literature. That is, the predicted ML matrix is assumed to be low-rank, which further casts Eq. (2) as:

where Rank(A) represents the rank of A, and α is a balance parameters. By jointly optimizing Problem (1) and Problem (3), we obtain the final formulation as follows:

Rank(·) is difficult to solve due to the discrete nature of the rank function. Fortunately, as suggested by [Cand`es et al., 2011], the nuclear-norm [Fazel, 2002] is a good surrogate for the rank function. Replacing the rank function with the nuclear norm, we obtain the next optimization problem:

The method learning multi-label by threshold is called TLRLDL, and the other one learning multi-label from top-k is called TKLRLDL.

3.3 Optimization

We utilize ADMM to address the problem (5), which is proficient in managing equality constraints. First, we introduce an auxiliary variable G ∈ Rm×n and rewrite Eq. (5) as

We introduce the augmented Lagrangian function for Eq. (6)

where µ is a positive penalty parameter, and Γ1 ∈ Rm×n denotes the Lagrangian multipliers. It can be solved by alternately optimizing three sub-problems as follows. The whole process is summarized in Algorithm 1.

Solving G-Subproblem

The subproblem w.r.t. G is

It is a nuclear norm minimization problem and has a closedform solution [Cai et al., 2010]:

where T = WX⊤O+ Γ1 µ , and S(·) is single value thresholding operator. It first performs singular value decomposition on WX⊤O + Γ1 µ = UˆΣV⊤, and then gives the solution as UˆΣV⊤, where ˆΣii = max (0, Σii - α/µ).

Solving W-Subproblem

The subproblem w.r.t. W is

which is a quadratic optimization problem. The optimal solution is obtained by setting the derivative to zero and equals

Solving O-Subproblem

The subproblem w.r.t. O is

which is a quadratic optimization problem. The optimal solution is obtained by setting the derivative to zero and equals

Updating Multipliers and Penalty Parameter

Finally, the Lagrange multiplier matrix and penalty parameter are updated based on following rules:

where µmax is the maximum value of µ.

Algorithm 1 The pseudo-code for TLRLDL and TKLRLDL

Input: training set T, parameters α, λ, and text data x∗ . Output: Predict the label distribution of x∗ .

• 1: Transforming label distribution matrix into multi-label matrix according to the method in the preceding section;
• 2: InitializeW, O, G, Γ1, and µ;
• 3: t=1;
• 4: repeat
• 5: Update G according to Eq. (7);
• 6: UpdateWaccording to Eq. (8);
• 7: Update O according to Eq. (10);
• 8: Update Γ1 and µ according to Eq. (11);
• 9: t=t+1;
• 10: until stopping criterion is satisfied
• 11: return the label distribution d∗ =W(x∗ ).

4 Experiments

4.1 Experimental Configuration

Experimental Datasets: The experiments are conducted on 16 real-world datasets with label distribution. The key characteristics of these datasets are summarized in Table 1. Geng collects the first 12 datasets [Geng, 2016]. Among these, the first eight (from Spoem to Alpha) are from the clustering analysis of genome-wide expression in Yeast Saccharomyces cerevisiae [Eisen et al., 1998]. The SJAFFE is collected from JAFFE [Lyons et al., 1998], and the SBU 3DFE is obtained from BU 3DFE [Yin et al., 2006]. The Gene is obtained from the research on the relationship between genes and diseases [Yu et al., 2012]. The Scene consists of multi-label images, where the label distributions are transformed from rankings [Geng and Xia, 2014]. Besides, the SCUT-FBP, M2B, and fbp5500 are about facial beauty perception [Ren and Geng, 2017]. The last one, RAF-ML is a facial expression dataset

[Li and Deng, 2019] with six-dimension expression distribution.

Evaluation Metrics: We adopt six metrics to evaluate the performance of LDL methods, including Chebyshev (↓), Clark (↓), Kullback-Leibler (KL) (↓), Canberra (↓), Intersection (↑), and Cosine (↑) [Geng, 2016]. Here, ↓ indicates that smaller values are better, and ↑ indicates that larger values are better.

Comparing Methods: We compare the proposed methods with seven LDL methods, including IIS-LDL, LDLLDM, EDL-LRL, IncomLDL, Adam-LDL-SCL, LCLR, and LDLLC, which are briefly introduced as follows:

• IIS-LDL [Geng, 2016]: It utilizes the maximum entropy model and KL divergence to learn the label distribution and does not consider label correlation.
• LDLLDM [Wang and Geng, 2023]: It learns the global and local label distribution manifolds to exploit label correlations and can handle incomplete label distribution learning.
• EDL-LRL [Jia et al., 2019]: It captures the low-rank structure locally when learning the label distribution to exploit local label correlations.
• IncomLDL [Xu and Zhou, 2017]: It utilizes trace-norm regularization and the alternating direction multiplier to exploit low-rank label correlation.
• Adam-LDL-SCL [Jia et al., 2021]: It incorporates local label correlation by encoding it as additional features and simultaneously learns the label distribution and label correlation encoding.
• LCLR [Ren et al., 2019]: It first models global label correlation using a low-rank matrix and then updates the matrix on clusters of samples to consider local label correlation.
• LDLLC [Zheng et al., 2018]: LDLLC leverages local label correlation to ensure that prediction distributions between similar instances are as close as possible.

The parameters of the methods are as follows. The suggested parameters are used for IIS-LLD, EDL-LRL, LDLLC, and LDL-LCLR. For LDLLDM, λ1, λ2, and λ3 are tuned from {10-3 , . . . , 103}, and g is tuned from 1 to 14. For IncomLDL, λ is selected from the range {2-10 , . . . , 210}, and ρ = 1. For Adam-LDL-SCL, λ1, λ2, and λ3 are tuned from the set {10-3 , . . . , 103}, and m is tuned from 0 to 14. For TLRLDL and TKLRLDL, α, λ are tuned from {0.005, 0.01, 0.05, 0.1, 0.5, 1, 10}, T is selected from 0.1 to 0.5, and k is tuned from 0 to m. We run each method for ten-fold cross-validation.

4.2 Results and Discussion

Table 2 presents the experimental results (mean±std) of the LDL algorithms on all datasets in terms of Clark, KL, and Cosine (due to limited space, the results in terms of other metrics are reported in the supplementary material 1 ), with the best results highlighted in boldface. Moreover, the last row summarizes the top-one times of each method.

First, we conduct the Friedman test [Demˇsar, 2006] to study the comparative performance of all methods. Table 3 shows the Friedman statistics for each metric and the critical value. At a confidence level of 0.05, the null hypothesis that all algorithms achieve equal performance is rejected. Next, we apply a posthoc test, i.e., the Bonferroni-Dunn test [Demˇsar, 2006], to compare the relative performance of TLRLDL against the other algorithms with it as the control algorithm 2 . One algorithm is deemed to achieve significantly different performance from TLRLDL if its average rank differs from that of TLRLDL by at least one critical difference (CD) [Demˇsar, 2006]. Figure 2 illustrates the CD diagrams for each measure. If the average rank of a comparing algorithm is within one CD to that of TLRLDL, they are connected with a thick line; otherwise, it is considered to have a significantly different performance from TLRLDL.

According to Table 2, TLRLDL demonstrates remarkable performance; ranking first in 70.83% (34 out of 48) of the cases and achieving the best mean performance across all metrics. TLRLDL and TKLRLDL reach the top position in 85.4% (41 out of 48) of the evaluations, underscoring the methods' effectiveness. Additionally, observations from Figure 2 include:

• TLRLDL significantly outperforms IIS-LLD across all metrics due to its utilization of label correlation, underscoring its importance for LDL.
• TLRLDL shows superior performance over IncomLDL, ED-LRL, and LCLR, suggesting the potential limitation of low-rank label correlation in LDL. However, TLRLDL's application of low-rank label correlation in the auxiliary MLL process appears to be more appropriate and effective for LDL.
• In contrast toLDLLC, LDLLDM, andAdam-LDL-SCL, TLRLDL's success further supports the competitiveness of employing low-rank label correlation within the auxiliary MLL process as a strategy for LDL.

1 https://github.com/users/zhiqiang-kou/projects/1

2 The test results with TKLRLDL as the control algorithm are presented in the supplementary material

In summary, the experimental results substantiate the competitive performance of the proposed algorithms.

4.3 Ablation Study

Next, we study the advantages of exploiting the low-rank label correlation on the auxiliary MLL. First, we derive TLRLDL-a by

Second, we derive TLRLDL-b by keeping Eq.'s first and fourth items (5). TLRLDL-a exploits low-rank label correlation on LDL, and TLRLDL-b ignores label correlation. We then compare TLRLDL with TLRLDL-a and TLRLDL-b.

Figure 3 presents the comparison results regarding Clark, KL, Cosine, and Intersection. Further, we conduct the Wilcoxon signed-rank tests [Demˇsar, 2006] for TLRLDL against TLRLDL-a and TLRLDL-b and report the results of the tests in Table 4. According to Figure 3 and Table 4, TLRLDL and TLRLDL-a have better performance than TLRLDL-b. TLRLDL-b ignores label correlation, while TLRLDL and TLRLDL-a consider label correlation, which improves their performance. This observation further justifies the importance of label correlation for LDL. Besides, TLRLDL statistically outperforms TLRLDL-a. Since the difference between TLRLDL and TLRLDL-a lies in that the former (respective the latter) exploits low-rank label correlation on MLL (respective LDL), this observation clearly justifies the benefits of exploiting low-rank label correlation on the auxiliary MLL. To summarize, exploiting the low-rank multi-label correlation is more suitable for LDL.

4.4 Parameter Sensitivity Analysis

TLRLDL has two trade-off parameters, including α and λ. Next, we analyze the sensitivity of them. First, we run TLRLDL with α varying from the candidate set {0.005, 0.01, 0.05, 0.1, 0.5, 1, 10} and report its performance on SCUT-FBP, M2B, SJAFFE, SBU 3DFE, and Alpha in Figure 4. As seen from Figure 4, TLRLDL shows robustness w.r.t. α. As a result, we can set α to 0.1 to get a satisfying performance. Likewise, we also run TLRLDL with λ ranging from the same candidate set and present its performance in Figure 4. As shown in Figure 4, TLRLDL is robust w.r.t. λ. Therefore, we may expect satisfying performance for λ = 0.1.

5 Conclusion

LDL has an exponential-size output space-with a size of Rm-which may decrease the performance of existing algorithms. To solve that, many LDL studies have proposed to exploit label correlation. Among these, some have suggested using low-rank label correlation of label distribution, which may not hold as disclosed by [Wang and Geng, 2023] because LDL matrices are typically full-rank. Addressing this, we've implemented an auxiliary MLL process within LDL, utilizing low-rank label correlation there, enhancing our methods' performance over current LDL approaches. Our results and further studies confirm the benefits of this low-rank exploitation. Future work will continue exploring this innovative direction, focusing on local low-rank label correlations.

Acknowledgements

This work was supported by the National Natural Science Foundation of China (62125602, 62076063, 62106044, 62306073), the Natural Science Foundation of Jiangsu Province (BK20210221, BK20230832), the China Postdoctoral Science Foundation (2022M720028), the ZhiShan Youth Scholar Program from Southeast University (2242022R40015), and the Jiangsu Funding Program for Excellent Postdoctoral Talent (2022ZB121).

Contribution Statement

Zhiqiang Kou and Jing Wang contributed equally to this work.