EMMS: Evidential Multi-Label Multi-Dimensional Selection

1 Introduction

Multi-label data, in which each instance is associated with multiple labels simultaneously, is prevalent in real-world applications [Zhang and Zhou, 2006; Lin et al., 2015]. For example, in image classification tasks, a single image may simultaneously be labeled as "sky," "building," and "person" [Wang et al., 2016]. Multi-label data is often highdimensional, containing redundant or irrelevant features, and may also include noisy or outlier instances. Furthermore, because obtaining accurate label annotations for every instance is expensive and often requires expert knowledge, the resulting labels are often subject to noise. These characteristics can lead to the curse of dimensionality, increase the risk of overfitting, and ultimately degrade the performance of downstream tasks [Lin et al., 2015; Li et al., 2022c]. Therefore, how to select discriminative features, representative instances, and informative labels from high-dimensional multilabel data that contains noisy instances and labels has become an urgent problem in many practical applications.

∗Corresponding Author

To address this issue, data reduction techniques for multilabel data, an important area of research in multi-label learning, have been extensively investigated from multiple perspectives [Zhang et al., 2023; Del Castillo et al., 2021; Pan et al., 2022]. Depending on the dimension being reduced, existing approaches for multi-label data can be broadly categorized into feature selection, instance selection, and label selection. Multi-label feature selection aims to identify a subset of informative features from multi-label data to alleviate the curse of dimensionality [Zhang et al., 2023; Zhang et al., 2025; Wang et al., 2025], while multi-label instance selection focuses on choosing representative instances to reduce sample size [Del Castillo et al., 2021; Ougiaroglou et al., 2023; Li et al., 2024]. Additionally, label selection for multi-label data seeks to preserve the most informative labels, thus reducing label redundancy [Pan et al., 2022; Nguyen et al., 2024]. Although these methods are effective when applied to features, samples, or labels individually, they often need to be combined when dealing with multi-label data containing high-dimensional features, outlier samples, and noisy labels. However, such a combined approach tends to overlook the interactions among these dimensions, which can ultimately limit overall performance.

In addition to the aforementioned dimension-specific data reduction methods, there are few multi-label co-selection approaches that simultaneously select discriminative features and representative instances from multi-label data, such as MAVNS [Lin et al., 2021] and MLVQ-JMR [Li et al., 2023]. Despite the advances made by these co-selection methods, their effectiveness is fundamentally limited by the assumption that the observed labels are entirely accurate, which is rarely the case in practice. In real-world applications, obtaining precise label annotations for every instance is often costly and may even be infeasible. As a result, annotators typically provide label sets that include the ground-truth labels as well as noisy ones [Xie et al., 2025; Li et al., 2022c]. The presence of noisy labels can adversely affect the performance of data reduction methods. This can be validated by Fig. 1, which compares the performance of our proposed method EMMS with two combined data reduction approaches SILS and MALS. SILS integrates three data reduction methods for multi-label data: feature selection (SPLDG [Zhang et al., 2025]), instance selection (CHC-IS [Del Castillo et al., 2021]), and label selection (Inf-LS [Pan et al., 2022]). MALS combines a multi-label feature and instance co-selection method (MAVNS [Lin et al., 2021]) with the same label selection method Inf-LS. It can be observed that the proposed EMMS significantly outperforms the combined methods under different noisy label ratios. These results demonstrate that simple combination methods are hardly effective for multi-label data containing high-dimensional features, outlier instances, and noisy labels.

To address the aforementioned issues, we propose a novel multi-label data reduction method called Evidential Multilabel Multi-dimensional Selection (EMMS) that simultaneously selects features, instances, and labels. Specifically, EMMS introduces a dual projection mechanism with sparsity constraints that first maps high-dimensional data into a latent space and then into the label space. Meanwhile, the projection residuals are explicitly modeled to facilitate the identification of representative instances, thereby enabling the joint selection of features, instances, and labels. Furthermore, we utilize Dempster-Shafer theory [Dempster, 2008] to assign belief masses, assessing the reliability of learned labels based on both instance-level and label-level evidence. These belief masses are then aggregated to refine the learned labels and mitigate the impact of noisy labels, which in turn leads to more effective multi-dimensional selection. The overall framework of the proposed EMMS is illustrated in Fig. 2. The main contributions of this paper are as follows:

• To the best of our knowledge, this is the first work to propose and investigate the joint selection of features, instances, and labels from high-dimensional multi-label data with noisy instances and labels, thereby advancing data reduction towards more realistic scenarios.
• An evidence-based label refinement mechanism is proposed that integrates two complementary sources of evidence to enhance the reliability of learned labels and thereby facilitate multi-dimensional selection.
• An effective alternative optimization algorithm is developed for the proposed EMMS. Comprehensive experiments demonstrate that EMMS consistently outperforms state-of-the-art approaches.

2 The ProposedMethod

2.1 Notations and ProblemDefinition

Throughout this paper, matrices and vectors are denoted by bold uppercase and lowercase letters, respectively. Given a matrix A ∈ Rn×p , its trace and transpose are denoted by Tr (A) and AT . The Frobenius norm of A is defined as ∥A∥F = √∑ni=1 ∑pj=1 |aij|2 , and the ℓ1-norm as ∥A∥1 = ∑ni=1 ∑pj=1 |aij|, where aij denotes the (i, j)-th entry of A. 1n×c represents an n × c matrix whose entries are all ones.

To clearly define the problem, consider a multi-label dataset D = {(X, ˆ Y )}, where X ∈ Rn×d denotes the feature matrix containing n instances and d features, and ˆ Y ∈ Rn×l is the observed label matrix corrupted by noise, with l being the number of label classes. In ˆ Y , ˆ yij = 1 indicates that the j-th label is either relevant to instance xi. or is a noisy label, whereas yij = 0 indicates that the j-th label is irrelevant to xi.. This study aims to simultaneously select the b most informative features, g representative instances, and h reliable labels fromD.

2.2 Dual-Projection-basedMulti-Dimensional Selection for Multi-Label Data

Conventional multi-label feature selection methods [Nie et al., 2010; Lei et al., 2023] typically learn a direct mapping from features to labels by incorporating a regularization term, as illustrated below:

where W ∈ Rd×l denotes the feature projection matrix and Ω is the regularization term that controls model complexity. Despite their effectiveness in simple settings, such formulations face two main limitations in real-world scenarios. First, data often contain noisy and outlier samples, which can dominate the reconstruction loss and bias the learned projection toward non-representative samples, resulting in unreliable feature selection. Second, the high cost and subjectivity involved in obtaining label annotations often result in noisy labels, as limited resources and subjective judgments can introduce errors into the annotation process. Directly learning from these labels may introduce misleading supervision signals, distorting the projection matrix learning process and ultimately degrading the performance of downstream tasks.

To address the above issues, we propose a unified multi-dimensional selection framework that introduces a sparsity-regularized dual projection mechanism to map highdimensional features first into a latent space and subsequently into the label space. In addition, projection residuals are explicitly modeled to identify representative instances, enabling the joint selection of features, instances, and labels. This can be formulated as follows:

where P ∈ Rd×c is the feature projection matrix that maps the original high-dimensional features into a latent space, and Q⊤ ∈ Rc×l serves as a projection from the latent feature space to the label space. Besides, R is a projection residual matrix that captures instance-level deviations, while Y and N denote the learned ground-truth label matrix and a sparse, non-negative noise matrix, respectively, such that ˆ Y = Y +N. The ℓ1-norm regularization terms imposed on P, Q, R, and N promote sparsity, thereby suppressing irrelevant features, non-representative instances, and noisy labels, respectively, within a unified framework. Meanwhile, λ1, λ2, and λ3 are three regularization parameters. Then, based on Eq. (2), we can select the top b features, g instances, and h labels by ranking the row-wise ℓ2-norms in P , R, and Q in descending, ascending, and descending order, respectively. Hence, Eq. (2) utilizes a dual projection mechanism with sparse regularization to enable the simultaneous selection of features, instances, and labels.

Furthermore, we integrate two manifold regularization terms into Eq. (2) to preserve the local neighborhood structures in both the feature and label spaces, leading to the following formulation:

+ λ3(∥R∥1+∥N∥1) + 1

2 Tr(P ⊤LF P ) + 12 Tr(Y ⊤LXY )

s.t. P,Q,R, Y ,N ≥ 0, ˆ

Y = Y +N,

(3)

where LF = DF - SF and LX = DX - SX denote the Laplacian matrices constructed from the cosine similarity matrices SF ∈ Rd×d and SX ∈ Rn×n over features and samples, respectively. The corresponding degree matrices DF and DX have diagonal entries ∑dj=1 (SF )ij and ∑nj=1 (SX)ij, respectively. The last two terms in Eq. (3) encourage similar features to stay close in the latent space and correlated instances to share similar labels. This facilitates the learning of more accurate projections and labels, thereby enhancing the effectiveness of joint feature, instance, and label selection [Li et al., 2022a; Braytee et al., 2017].

2.3 Evidence-based Label Refinement

Label manifold regularization encourages neighboring instances to have similar label predictions. However, if an instance is assigned incorrect labels, this constraint can propagate noisy label information to its neighbors, resulting in an unreliable learned label matrix Y , which in turn reduces performance on downstream tasks.

To address this issue, we incorporate Dempster-Shafer theory (DST) [Denœux, 2019; Li et al., 2022b] to refine the learned label matrix Y in a reliability-aware manner. By associating each label assignment with a belief mass and refining unreliable predictions through the fusion of multiple sources of evidence, our approach provides more reliable supervision for multi-dimensional selection. Specifically, since each entry in Y corresponds to a binary label, learning Y can naturally be decomposed into a set of binary label assignment problems, which allows DST to be applied in a label-wise manner. Hence, for each label assignment yij, we define a binary frame of discernment Θ = {+,-}, where "+" and "-" denote the hypotheses that the j-th label is relevant or irrelevant to the i-th instance, respectively. The corresponding power set is given by 2Θ = {∅, {+}, {-}, {+,-}}, where the universal set {+,-} represents uncertainty regarding the current label assignment. Then, a basic probability assignment (BPA) is constructed for each yij , which allocates belief masses to the positive, negative, and uncertain hypotheses as follows:

where m(·) is a mapping from 2Θ to [0, 1], satisfying m(∅) = 0 and ∑A∈2Θ m(A) = 1. Thus, m(A) represents the belief mass assigned to the event A, where A ∈ 2Θ . cij ∈ [0, 1] denotes the confidence in the current label assignment, where higher confidence concentrates more belief on specific hypotheses, while lower confidence results in more mass being assigned to uncertainty.

To comprehensively assess the confidence of the current label assignment yij, we leverage two complementary sources of evidence derived from instance-level and label-level structural information, based on the following assumptions. First, from the instance perspective, if instances similar to the i-th instance are assigned the j-th label, the assignment of yij as positive is considered more reliable. Second, from the label perspective, if labels correlated with the j-th label also cooccur in the i-th instance, assigning label j is deemed more credible. Hence, the instance correlations are captured by the similarity matrix SX, while the label correlations SY ∈ Rl×l are computed as the cosine similarity between label representations derived from Q. Based on these two sources of evidence, the confidence for yij is calculated as follows:

where e(1) ij = SX(i, ·)y.j and e(2) ij = yi.SY (·, j) denote the instance-level and label-level evidence, respectively, and σ(k) controls the sensitivity of confidence estimation.

Based on the confidence values c(k) ij (k = 1, 2), two corresponding BPAs m(k) ij (k = 1, 2) are constructed using Eq. (4), each encoding the belief masses for the positive, negative, and uncertain hypotheses from different perspectives. These two BPAs are then fused to aggregate consistent evidence and normalize conflicting information, using the following combination rules:

where m(f ) ij denotes the aggregated beliefmass, andKij is the conflict coefficient between the two evidence sources. Thus, the aggregated belief mass m(f) ij provides a reliability-aware refinement of the learned label assignment, as given by:

where τ ∈ [0, 1] controls the contribution of uncertainty. During subsequent optimization, these refined labels are iteratively updated, allowing the model to gradually suppress noisy assignments and strengthen reliable ones, thereby enhancing the overall quality of the learned label matrix Y .

3 Optimization and Analyses

Since the objective function in Eq. (3) is non-convex with respect to all variables, we develop an iterative optimization algorithm that updates each variable in turn while keeping the others fixed.

Update P and fix others. With the other variables fixed, following [Ma and Chow, 2018], the objective function with respect to P can be rewritten as:

By differentiating Eq. (8) w.r.t. P, we can obtain the following update rule for P :

Update Q and fix others. When the other variables are fixed, optimizing Q in Eq. (3) can be reformulated as follows:

Analogous to the update of P, the update rule for Q can be derived as follows:

Update R and fix others. After fixing the other variables, R can be updated by solving the following optimization problem:

Algorithm 1 Iterative Algorithm of EMMS

Inputs: Multi-label data D = {(X, ˆ Y )}, and parameters λ1, λ2 and λ3.

• 1: Initialize P, Q, R, N, and Y .
• 2: Compute similarity matrices SF and SX.
• 3: while not converge do
• 4: Update P via Eq. (9);
• 5: Update Q via Eq. (11);
• 6: Update R via Eq. (13);
• 7: Update Y via Eq. (15);
• 8: Refine Y according to Eq.(7);
• 9: Update N via Eq. (17);

10: end while

Output: The top b features, g instances, and h labels are jointly selected by ranking the row-wise ℓ2-norms of P in descending order, R in ascending order, and Q in descending order, respectively.

Taking the derivative of Eq. (12) with respect to R, we obtain the following update rule for R:

Update Y and fix others. Following the same approach as for updating P , we derive the optimization problem for Y as

Then, the update rule for Y is given by:

After updating Y according to Eq. (15), its elements are subsequently refined using Eq. (7).

Update N and fix others. By fixing the other variables, the optimization problem for N is reformulated as follows:

Using the same approach as for updating P, N can be updated according to the following rule:

Algorithm 1 summarizes the overall optimization procedure of the proposed EMMS. In this algorithm, P , Q, R, and N are randomly initialized to non-negative matrices, while Y is initialized to ˆ Y .

Complexity and Convergence Analysis. The computational complexity of Algorithm 1 is mainly due to matrix multiplication operations. Specifically, updating P and Q each requires complexity of O(nd2 ). For updating R, the time complexity is O(ndc). Updating Y has a complexity of O(ndc + n2 l), and its refinement step takes O(n2 l) complexity. The update of N consists solely of element-wise operations, whose computational cost can be ignored. Therefore, the overall computational complexity of Algorithm 1 is O(nd(c+d)+n2 l). Due to space limitations, the convergence proof of Algorithm 1 is provided in the supplementary material 1 .

4 Experiments

4.1 Experimental Settings

Datasets. We conduct experiments on six real-world multilabel datasets: Stackex philosophy 2 (Staexp), Corel5k 2 , Arts 3 , Science 3 , Social 3 , and Corel16k001 2 (Co16k1). Details of these datasets are summarized in Table 1, where "Card." denotes the average number of labels per instance and "Dens." represents the label density of each dataset.

Compared Methods. To evaluate the effectiveness of the proposed EMMS, we compared it with several state-of-theart (SOTA) methods. These include the multi-label tripleselection method mFILS [Mansouri and Benabdeslem, 2021], as well as nine combination-based methods for multi-label data that integrate feature selection, instance selection, and label selection: SILS (SPLDG [Zhang et al., 2025] with CHC-IS [Del Castillo et al., 2021] and Inf-LS [Pan et al., 2022]); NILS (NMMFS [Wang et al., 2025] with CHC-IS and Inf-LS); PILS (PML-FSLA [Pan et al., 2025] with CHC-IS and Inf-LS); RILS (ROAD [Zhang et al., 2023] with CHCIS and Inf-LS); IFLS (IS-FS [Kusy and Zajdel, 2024] with Inf-LS); FILS (FS-IS [Kusy and Zajdel, 2024] with Inf-LS); MJLS (MLVQ-JMR [Li et al., 2023] with Inf-LS); s2LS (sCOs2 [Benabdeslem et al., 2022] with Inf-LS); and MALS (MAVNS [Lin et al., 2021] with Inf-LS).

Comparison Schemes. For a fair comparison, all methods are tuned using grid search, and their best results are reported. The parameters λ1, λ2, and λ3 in our method are selected from {10-3 , 10-2 , 10-1 , 1, 10, 102 }, while those for the compared methods are set as recommended in their respective papers. Since it is challenging to determine the optimal number of selected features, instances, and labels [Siblini et al., 2019; Ros and Guillaume, 2019], we set their selection ratios to range from 10% to 50% in increments of 10%. Consistent with previous methods [Sun et al., 2019; Xie and Huang, 2021], false-positive labels are randomly introduced for each instance at a rate equal to 50% of the number of relevant labels to simulate a noisy environment. Following [Mansouri and Benabdeslem, 2021], we first apply the proposed methods to identify the most informative features, instances, and labels across all datasets. Each dataset is then represented using these selected features and labels. An ML-KNN classifier [Zhang and Zhou, 2007] is trained on the selected instances and their corresponding labels, and is subsequently used to predict the labels of the remaining samples. Five widely used metrics, including Ranking Loss (RL), Hamming Loss (HL), Average Precision (AP), MacroF1 (MaF), and Micro-F1 (MiF), are used to evaluate the results, with lower HL and RL and higher AP, MaF, and MiF indicating better performance. Each experiment is repeated five times, and the average values are reported.

1 https://github.com/yangdali706/SupplementaryMaterial

2 http://www.uco.es/kdis/mllresources

3 http://www.lamda.nju.edu.cn/code MDDM.ashx

4.2 Experimental Results and Analysis

Performance Comparison. Table 2 presents the performance of different methods in terms of AP and RL on six datasets, with 10% of the instances, features, and labels are selected. The best results are highlighted in bold, while the second-best results are underlined. Due to limited space, the results for MaF, MiF, and HL are included in the supplementary material. As shown in Table 2, EMMS consistently outperforms all other competing methods across all datasets. EMMS achieves more than a 20% improvement in AP over the second-best method on Corel5k and Co16k1 datasets, and at least a 10% improvement on the remaining datasets. Additionally, EMMS reduces RL by more than 15%

on Arts, Science, Social, and Co16k1 datasets compared to the second-best methods. Furthermore, supplementary results from the Friedman and Nemenyi post-hoc tests demonstrate that EMMS significantly outperforms other methods.

Furthermore, to provide a comprehensive evaluation of EMMS, we also present the results for all methods across all datasets using five metrics, with varying ratios of feature, instance, and label selection. Figs. 3, 4, and 5 show the results for the Co16k1 dataset with different feature selection ratios (FSR), instance selection ratios (ISR), and label selection ratios (LSR), respectively. The results for the other five datasets are available in the supplementary material. As illustrated in these figures, the proposed EMMS outperforms the other methods in most cases. The superior performance of EMMS can be attributed to the joint selection of features, instances, and labels, combined with evidence-based label refinement, as these components mutually reinforce each other.

Ablation Study. We conduct an ablation study to evaluate the contributions of the key modules in EMMS. Table 3 reports the AP results, where EMMS-I and EMMS-II are the variants without the evidence-based label refinement module and the manifold learning module, respectively. As shown in Table 3, EMMS outperforms both variants, confirming the effectiveness of the two modules.

Case Study. We conduct an experiment on the Scene dataset [Boutell et al., 2004] with noisy labels to evaluate EMMS's ability to identify relevant labels. Fig. 6 shows an image from the Scene dataset, featuring two ground-truth labels (green) and two noisy labels (red). Table 4 presents the label selection results for different methods. As shown, EMMS identifies relevant labels more accurately than other methods, which tend to select noisy or irrelevant labels. This demonstrates the effectiveness of EMMS in handling multilabel data with noisy labels.

Parameter Sensitivity and Convergence Analysis. The proposed EMMS includes three tuning parameters, namely λ1, λ2, and λ3. Fig. 7 illustrates the sensitivity of the AP

Table 4: Selected labels by different methods.

metric on Science dataset under different parameters, showing that the performance of EMMS is relatively stable with respect to λ1 and λ3, and generally performs better with smaller values of λ2. Additionally, Fig. 8 presents the convergence curves of EMMS on Staexp, Arts, and Co16k1 datasets. As shown in the figure, EMMS decreases rapidly during the initial iterations and stabilizes after about 10 iterations.

5 Conclusion

In this paper, we propose a novel multi-label data reduction method called EMMS to simultaneously select features, instances, and labels from high-dimensional multi-label data with noisy labels. Unlike existing approaches that treat feature, sample, and label selection separately, we integrate them into a unified framework through a dual projection mechanism with sparsity constraints. Meanwhile, we employ an evidence-based label refinement module to improve the reliability of learned labels and reduce the influence of noisy labels, thereby enhancing the effectiveness of joint selection. Extensive experiments demonstrate the superiority of EMMS compared to SOTA methods.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 72495122), and the Natural Science Foundation Project of Sichuan Province (No. 2024NSFSC0504). The author Yanyong Huang gratefully acknowledges the support of K. C. Wong Education Foundation and DAAD.