Noise-Resistant Label Reconstruction Feature Selection for Partial Multi-Label Learning

1 Introduction

PML [Xie and Huang, 2018] is a recently emerging paradigm of weakly supervised learning aiming to construct a multiclass classifier with uncertain data. Specifically, PML attempts to learn the model from partially labeled samples: a sample is assigned with a candidate label set, and at least one label in the candidate label set is truly related to the sample but the total number of truly related labels is unknown [Sun et al., 2019; Yu et al., 2018]. Compared to multi-label learning [Li et al., 2023a; Gao et al., 2023], PML can better handle situations where labels are missing or ambiguous, which is quite common in real-world scenarios.

∗ corresponding author

Currently, methods for PML can be broadly classified into two categories [Xie and Huang, 2021; Wang et al., 2019; Durand et al., 2019]. The first ones treat all labels in candidate set as correct annotations, ignore noises in labels and directly utilize models for learning such as ML-KNN [Zhang and Zhou, 2007]. The second ones consider the noises in candidate label set and reduce the influence of noises through matrix decomposition and low-rank confidence matrix approximation [Sun et al., 2019].

Candidate labels

• cloud
• people
• mountain
• tree
• car
• sea
• beach

However, the formers are highly affected by noises, while the latters often rely on the low-rank assumption (i.e. assuming that the low-rank matrix generated after dimension reduction is consistent with the original high-order matrix) and reduce the dimension of the feature/label matrix to reduce the influence of noises. While previous studies have shown that the requirements of the low-rank assumption are relatively strict and often not fully applicable in practical situations [Liu et al., 2015; Xu et al., 2016]. Compared to the original matrix, a low-rank matrix inevitably loses some highorder structural information. In addition, the consistency between the low-rank matrix and the original high-order matrix is also difficult to maintain because of the structural complexity of the original high-dimensional data space.

Another challenge arises from the inherent sparsity of positive labels within multi-label datasets [Liu et al., 2021]. This characteristic of datasets poses a significant hurdle, diminishing the efficacy of many multi-label methods in identifying positive labels due to the lack of samples with positive labels. Consequently, the performance of the methods in recognizing positive labels tends to be suboptimal. However, accurate identification of positive labels is important in prediction tasks in various domains such as disease diagnosis [Pham et al., 2022], sentiment analysis [Yilmaz et al., 2021], and gene detection [Wang et al., 2021]. Thus it is necessary for methods capable of addressing this challenge. The sparsity of positive labels demands that we make the most of the available information. Feature selection can enhance the representativeness of the selected features with respect to positive labels, making it easier for the model to capture the underlying pattern.

To address these two challenges, we propose a novel PML feature selection framework based on two crucial characteristics of the datasets. The first one is the noise-resistance of the label relationship: The relationship of the label space is relatively stable and won't be affected by small amount of noise in it. This is because a group-level perspective can smooth out anomalies or noises in individual data points, thereby providing more stable and trustworthy information. Leveraging the relationship information of label space can effectively reduce noisy labels. Another is the label connectivity of label space: Labels in the dataset are not isolated entities but part of a network of interrelations that can significantly influence their importance in the dataset. In this network, the importance of a label is associated with the number of labels it is connected to and the intensity of their connections. The more numerous and stronger these connections, the higher the perceived importance of the labels. If the model can accurately identify an important label, then the model could also identify the highly connected labels accurately. Thus identifying these important labels can effectively enhance the model's precision.

To make use of these two characteristics, mutual information is introduced to measure this structural stability as it can effectively quantifies both linear and nonlinear relationships between variables [Shannon, 1948]. We propose a Partial Multi-label Feature Selection model based on Mutual Information Reconstruction (PML-FSMIR). The whole process is illustrated in Figure 2. Consequently, the of noise-resistance of the label relationship is utilized to reconstruct the label set, numerical values derived from mutual information matrix are employed to represent the reliability of candidate labels. Subsequently, the reconstructed label set is adopted as input for model learning, ensuring that the dimensions of the feature and label spaces remain unchanged throughout the learning process at the same time. Then with the label connectivity, this method reconstructs the learned weight matrix through mutual information matrix. Through this step, we identify important labels and increase their weights to enhance the performance of the model. Experimental validations on datasets from diverse domains affirm the method's efficacy. Our main contributions are:

• We have creatively proposed a method that couples mutual information and sparse learning to make use of collective label characteristics.
• This method breaks free the low-rank assumption commonly used in the past for PML, maintaining the dimensions of the sample space and preserving the highdimensional information within it.
• Extensive experiments have been conducted on datasets in different fields, and the experimental results have demonstrated the superiority of the model.

2 RelatedWork

2.1 Multi-label Feature Selection

Over the past years, many traditional multi-label feature selection methods have been proposed. They can be broadly categorized into three main types: filters, wrappers and embeddings. Filter methods select important features by designing a metric, and this process is independent of the subsequent task. Some methods employ mutual information as the metric

[Gao et al., 2018; Zhou et al., 2022]. MDMR combines mutual information with a max-dependency and min-redundancy method to select superior feature subset for multi-label learning [Lin et al., 2015]. Others utilize structural similarity as the metric [Zhang et al., 2021a; Zhang and Gao, 2021; Li et al., 2024]. Others design new evaluation criteria based on existing metrics. Zhang et. al. propose a method that distinguishes three types of label relationships (independence, redundancy and supplementation) and considers changes of label relationships based on different features [Zhang et al., 2021b]. GMM proposes geometric mean to aggregate the mutual information of multiple labels [Gonzalez-Lopez et al., 2020].

Wrapper methods evaluate the performance of feature subsets by training a specific model [Chandra and Bedi, 2021; Rigatti, 2017]. Due to their time-consuming nature and the need for specific model, they are not used as comparative methods in this paper.

Embedding methods assess features by designing specific models and integrate the process of feature selection with learning method. A typical idea is to design a function to carry out the process of learning and feature selection at the same time and then optimize this function [Li et al., 2023b]. MIFS decomposes multi-label information into a low-dimensional space and then employ the reduced space to steer feature selection process [Jian et al., 2016a]. Hu et. al. propose a method utilizes Coupled Matrix Factorization (CMF) to extract the shared common mode between feature matrix and label matrix, considering the comprehensive data information in two matrices [Hu et al., 2020b].

However, the above-mentioned works are unable to select optimal features in partially multi-label datasets as they are built on the assumption that all observed labels are correct.

2.2 Partial Multi-label learning

Partial Multi-label Learning (PML) addresses the issue in which each example is assigned to a candidate label set, and only a part of them is considered correct. To handle PML problem, one approach is to treat the candidate set as ground truth labels directly so that multi-label learning methods can be applied in dealing with PML problem. Nevertheless, these methods are susceptible to being misled by false positive labels concealed within the candidate label set. Hence, there have been proposals for methods specifically tailored to address the challenges of PML. Two effective methods PML-LC and PML-FP are first proposed by estimating a confidence value for each candidate label and training a classifier by optimizing the label ranking confidence matrix [Xie and Huang, 2018]. These methods identify noisy labels by the relationship between labels and features [Li et al., 2021]. Yu et. al. propose a method utilizes a low-rank matrix approximation and latent dependencies between labels and features to identify noisy labels and train a multi-label classifier [Yu et al., 2018]. PARTICAL-MAP and PARTICAL-VLS elicit credible labels from the candidate label set for model induction [Zhang and Fang, 2020]. From the other view, Xu et. al. propose a method leverages the topological information of the feature space and the correlations among the labels to recover label distributions [Xu et al., 2020]. Another view is how to exploit the negative information like the non-candidate set. Li and Wang propose a method that recovers the ground-truth labels by estimating the ground-truth confidences from the label enrichment, which is composed of the relevance degrees of candidate labels and irrelevance degrees of non-candidate labels [Li and Wang, 2020]. PML-LFC estimates the confidence values of relevant labels for each instance using the similarity from both the label and feature spaces, and trains the desired predictor with the estimated confidence values [Yu et al., 2020].

However, the above methods haven't considered the problem of sparse positive labels in the dataset. In order to strengthen the identification ability of positive labels, we propose PML-FSMIR.

3 The ProposedMethod

The proposed method consists of three stages: (1) label matrix reconstruction stage aims to reduce noises in labels; (2) reformed low-rank assumption stage aims to exploit cleaned information for feature selection with reformed low-rank assumption; (3) weight matrix reconstruction stage aims to enhance sensitivity to key labels for final feature selection.

3.1 Label Matrix Reconstruction

In the first stage, to reduce the influence of noises in the label set, the label mutual information matrix is introduced to reconstruct the label matrix. Label relationship is more stable than a single label, which means it is less likely to be affected by the noises in the label set. Thus label mutual information matrix which reflects the degree of the label relationship is adopted to reduce the noises.

The input consists of two parts: the feature matrix X = [x1, x2, . . . xn] ∈ Rn×d where d is the dimension of feature vector and n is the number of training instances and label matrix Y = [y1, y2, . . . yn] ∈ [0, 1]n×q , where q is the dimension of label vector. In label matrix, yij = 1 means that the j-th label is a candidate label of the i-th instance.

Initially, we compute the mutual information between labels and form them into a q-dimensional square matrix Z:

Zij denotes the mutual information between i-th and j-th label. As mutual information can quantify relationship between two variables and structure of the label is more stable and less likely to be influenced by noises in single sample, the mutual information between labels can be employed with candidate labels to determine the reliability of candidate labels. Then we can introduce the label reconstruction matrix T :

Simply using the dot product of Y and Z would causes noncandidate labels to be assigned with non-zero values, the sign(Y ) is further employed so that non-candidate labels will remain as zero. In this matrix, Tij can be expressed as:

Compared to yij, Tij comprehensively considers the relationship between labels and the candidate label set in the sample: the more labels in the candidate label set that are highly associated with it, the greater the value. For candidate label yij, if the labels that are structurally similar to it in the label space are included in the candidate set, then Tij will be large, indicating that the possibility of it being noise is low. Conversely, if the labels similar to it are not in the candidate set, then Tij will be small, suggesting that it is very likely to be noise. After normalization, this matrix T can replace the original matrix Y to the subsequent stages. The effectiveness of this step would be demonstrated in ablation experiments.

3.2 Reformed Low-rank Assumption

In the second stage, we hope to construct the objective function while avoiding the possible problems of the traditional low-rank assumption. For the label matrix Y , we have reconstructed the label matrix T in the first stage for disambiguation, thus no operations is needed in this stage. However, the noises and redundancy issues that exist in X still exist. So we adpot the reformed low-rank assumption to simultaneously remove noises and avoid redundancy and potential issues in low-rank assumption:

Where U ∈ Rn×k , V ∈ Rk×d and W ∈ Rd×q represent cluster matrix, cluster weight matrix, and feature weight matrix respectively. The traditional low-rank assumption uses matrix decomposition to remove redundancy and noises in the original matrix. We retain this matrix decomposition term, but adopt UV instead of the decomposed U to replace the original X. The dimension of X is preserved, and the goal of removing noises is achieved without losing the highdimensional structural information of X. In this way, the lowrank assumption is reformed.

To ensure the weight matrix W have the same structure as the original data points. We apply a manifold regularization term to W. Specifically, the mutual information matrix Z ′ of T is employed to replace the affinity matrix as this matrix is less sensitive to noises. It can be expressed as:

So the formula is changed as follow:

Where LT = A - Z ′ is graph laplacian matrix of T and A is a diagonal matrix. Finally, to achieve feature selection, we further add a l2,1-norm of W to Formula 6 [Nie et al., 2010]:

For optimization, this formula involves three variables W, U and V . After relax the W2,1 into Tr(W)T Q(W) where Q is a diagonal matrix: Qii = 1 2√W T i Wi+ϵ , (ϵ → 0). The objective function can be rewritten as:

Multiplicative gradient descent strategy is adopted to solve Formula 8 [Beck and Teboulle, 2009], in each iteration, each variable is updated while fixing other variables. By taking derivative of Formula 8 based on KKT conditions, we have:

In real implementation, a small positive value is added to the denominator to avoid zero values.

Algorithm 1 Pseudo code of PML-FSMIR

Input: Feature matrix X and label matrix Y , regularization parameters α, β, and γ.

Output: Return the ranked features.

• 1: Construct mutual information matrix Z of Y ;
• 2: Calculate T by Formula 2;
• 3: Construct mutual information matrix Z ′ and graph laplacian matrix of T ;
• 4: while not coverage do
• 5: Calculate Q;
• 6: Update U by Formula 9 with other variables fixed;
• 7: Update V by Formula 10 with other variables fixed;
• 8: Update W by Formula 11 with other variables fixed;
• 9: end while
• 10: Reconstruct W by Formula 12;
• 11: return Return features according to ∥Wi.∥2 .

3.3 Weight Matrix Reconstruction

In partial multi-label datasets, positive labels are often more sparse but more important than negative labels [Liu et al., 2006]. To further enhance the predicting ability of selected features of positive labels, we design this stage using mutual information matrix Z ′ to reconstruct the weight matrix.

To this end, the keypoint is to identify some representative labels which are related to more labels compared to other labels. If we can find those labels that are highly connected with a large number of labels and select these features that can identify these labels, the experimental results will significantly improve. As shown in Figure 3, since features is considered as equal after the end of the second stage, the feature weights are not correctly ranked as expected. Therefore, the weight matrix needs to be reconstructed using label connection, so that the reconstructed weight matrix can better identify the features that are more important to the representative labels. In weight matrix W, Wij is the weight of the i-th feature to the j-th label, so the sum of the rowWi can be regarded as the importance of the i-th feature to the label set. To enhance the identification ability of the selected feature to the representative labels, we utilize the mutual information between labels to reconstruct W:

Through this equation, Wij, the weight of i-th feature to jth label is updated according to the relevance of this labels to other labels. After this operation, those features that have higher weight to representative labels would be selected. According to final value of ∥Wi·∥2 (i = 1, . . . , d) in a descending order, the top ranked features are obtained. The pseudo code is presented in Algorithm 1. Subsequent ablation experiments have demonstrated the necessity of this stage.

4 Experiments

4.1 Datasets

We perform experiments on eight datasets from a broad range of applications: Birds for audio, CAL500 for music classification, Corel5K for image annotation, LLOG F and Slashdot for text categorization, Water for chemistry, Yeast for gene function prediction, and CHD49 for medicine. We keep the noisy level of every dataset at 20%. On each dataset, ten-fold cross-validation is performed where the mean metric values as well as standard deviations are recorded for each compared method. Detailed information is shown in Table 1.

4.2 Experimental Setup

Evaluation Metrics: We adopt five widely used multi-label metrics including Ranking Loss, Coverage, Average Precision, Marco-F1, and Micro-F1. For Ranking Loss and Coverage, the smaller value, the better the performance. For Average Precision, Marco-F1, and Micro-F1, the larger the value, the better the performance.

Baselines: We implement eight state-of-the-art methods of multi-label learning and PML for comparison and record the feature selection result with twenty points of different percentages. They are one Partial Multi-label Feature Selection methods (PML-FSSO [Hao et al., 2023]), five Partial Multi-label Learning methods (PML-LC [Xie and Huang, 2018], PML-FP [Xie and Huang, 2018], PAR-VLS [Zhang and Fang, 2020], PAR-MAP [Zhang and Fang, 2020] and FPML [Yu et al., 2018]) and two Multi-label Feature Selection methods (MIFS [Jian et al., 2016b] and DRMFS[Hu et al., 2020a]). Due to the lack of feature selection method in partial multi-label learning, the weight matrix is extracted from model to reflect the importance of features. We adopt ten-fold cross-validation to train these models and the selected features are compared on SVM classifier 1 .

4.3 Results

The tables below show the detail of the experiment result, for all datasets except Water, we select specified number of features according to the importance as descending order from one to twenty percent for each percentage of the features, the five used metrics for each dataset are recorded in form of mean and standard deviation among different percentages. We also illustrate one dataset for the detail of all metrics in Figure 4 to show our performance clearly. As for Water only has 16 features, we select 1 to 16 features. From overall results, we make following observations:

1 The code is available at https://github.com/typsdfgh/PMLFSMIR

• On eight datasets across all evaluation metrics, PMLFSMIR ranks first in all cases except Coverage on CHD 49 and Average Precision on LLOG F, while in these two cases PML-FSMIR all ranks second. These results fully demonstrate the superiority of PML-FSMIR.
• For the superiority in Ranking Loss, Coverage, and Average Precision. We attribute it to the reconstruction of the label matrix through mutual information matrix in the first stage. This step effectively reduces the noises in the labels, making the selected features more helpful for subsequent work. The subsequent ablation experiments further confirmed its function.
• For the superiority in Mirco-F1 and Marco-F1. We attribute it to the reconstruction of the weight matrix through mutual information matrix in the third stage. This step improves the weight of features with strong ability to determine key labels by reconstructing the weight matrix through mutual information matrix. The results in Table 4 and 5 show that this step significantly improves the F1-score, which improves the best results of the baselines at least by 15.2%. The subsequent ablation experiments further confirmed this opinion.

(a) Ranking Loss Bi CA CH Co LL Sl Wa Ye

(b) Average Precision

Figure 6: The results of the comparison experiment between the first two stage and the second stage.

4.4 Parameter Analysis

In PML-FSMIR, there are three parameters α, β, and γ that affect experimental results. Figure 5 shows how these three parameters affect the performance of the model on the LLOG F in terms of Ranking Loss. Each parameter is independently tuned from 0.001 to 1000, and we selected the performance of the model when selecting 8% of the features to 20% of the features. From the figure, it can be seen that the model is obviously insensitive to the parameters, which shows the robustness of the model.

4.5 Ablation Study

To prove the necessity of reconstructing objective matrix using mutual information matrix in first stage and third stage, we set up two ablation experiments: (1) we employ the first two stage compared to directly conducting the second stage to verify the superiority of the first stage; (2) we employ whole procedure compared to conducting the first two stage to verify the superiority of the third stage. In the first experiments we employ Ranking Loss, Coverage, and Average Precision as evaluate metrics. In the second experiments Mirco-F1 and Marco-F1 are used as evaluate criteria. The result are shown in Figures 6, 7. The Figure 6 proves the effectiveness of first stage. In all the datasets, the results of the first two stage are better than the second stage, which indicates that using mutual information matrix to reconstruct label matrix can effectively reduce the influence of noises in the labels.

The Figure 7 proves the effectiveness of the third stage. It clearly shows the significant improvement of weight matrix reconstruction. The method with the first two stage even cannot identify positive labels in six out of eight datasets while after the third stage it can do so in all datasets. This experiment enhances the correctness of our core idea: there are some labels in the label set that are more important than others. Finding features related to these labels can effectively improve the model's ability to identify positive labels.

5 Conclusion

In this paper, we tackle the challenges of label noise and sparsity in partial multi-label data by introducing a novel threestage feature selection method PML-FSMIR). This method first reduce the noises in the label sets by reconstructing label matrix using mutual information matrix. Then it trains a weight matrix under a reformed low-rank assumption, which helps to prevent overfitting and ensures a more accurate reflection of the data's underlying structure. Finally the weight matrix is reconstructed to enhance the ability of the selected features in effectively identifying key labels, thereby improving the model's overall performance. Extensive experimental results validate the superiority of our method. In the future, we plan to explore how to exploit mutual information and other methods to reduce noises and improve the identification of positive labels furthermore.

Acknowledgments

This work was supported by the Science Foundation of Jilin Province of China under Grant YDZJ202501ZYTS286, and in part by Changchun Science and Technology Bureau Project under Grant 23YQ05.