Wrapped Partial Label Dimensionality Reduction via Dependence Maximization

1 Introduction

Weakly supervised learning learns from data with limited supervision, where the annotations are usually incomplete (only a subset of data is labeled), inexact (ambiguous labels exist in data) or inaccurate (instances may be mislabeled) [Zhou et al., 2018]. Partial label learning is a typical weakly-supervised paradigm, where each instance is associated with a candidate label set, among which only one is true [Tian et al., 2023]. Compared with multi-class learning, partial label learning is more realistic and challenging [Gong et al., 2021b]. Accordingly, the need to learn from partial labeled data naturally arises in many real-world applications such as crowdsoucing tagging [Ren et al., 2024], part-of-speech tagging [Chen et al., 2017] and face naming [Xu et al., 2021], etc.

One intuitive approach towards partial label learning is label disambiguation, which aims to identify the only groundtruth label within candidate label set [He et al., 2022; Xu et al., 2023]. Generally, label disambiguation is pursued through two distinct strategies: averaging-based strategy [Ni et al., 2021] and identification-based strategy [Lyu et al., 2020a]. The former treats all potential positive labels in candidate label set equivalently, which distinguishes the averaged output on candidate labels labels from the outputs on non-candidate labels. On the other hand, identification-based disambiguation endeavors to recover the ground-truth label from candidate label set. This strategy treats the ground-truth label as latent variable and performs label disambiguation by optimizing the corresponding objective functions [Yu and Zhang, 2016], which are defined based on the maximum likelihood criterion log(∑y∈Si p(y|xi, θ)) or maximum margin criterion maxyj ∈Si f (xi, yj ) - maxyk /∈Si f (xi, yk).

Dimensionality reduction is an effective technique for enhancing the generalization capability across various learning systems through alleviating the issue of curse of dimensionality [Ximendes et al., 2022; Zhao et al., 2023]. Existing works [Huang et al., 2019] are mainly classified into two categories: unsupervised and supervised dimensionality reduction. Unsupervised dimensionality reduction aims to preserve the underlying structure and patterns in data without the help of supervision information [Niu et al., 2023; Yao et al., 2023]. As a representative algorithm, Principal component analysis (PCA) induces projection matrix by maximizing the variance of projected data [Hasan and Abdulazeez, 2021]. Supervised dimensionality reduction focuses on preserving class discriminative information, which utilizes the supervision information to guide the process of dimensionality reduction [Vogelstein et al., 2021]. For example, Linear Discriminant Analysis (LDA) achieves this by maximizing the intra-class scatter and minimizing the inter-class scatter simultaneously [Sachin and others, 2015].

Due to the requirement for explicit class membership in defining objective functions, prior works on supervised dimensionality reduction heavily rely on ground-truth labels to induce projection matrices. Consequently, the intrinsic challenge of ambiguous supervision within partially labeled data hinders the application of supervised dimensionality reduction methods. Remarkably, the adaptation of dimensionality reduction techniques to address partial label learning remains a relatively unexplored problem. To the best of our knowledge, DELIN [Zhang et al., 2022], CENDA [Bao et al., 2021] and PLDA [Yu et al., 2024] are the only existing dimensionality reduction designed for partial label learning, which induce projection matrix by adapting supervised dimensionality reduction methods into partial label learning. DELIN achieves dimensionality reduction through an alternating procedure that optimizes the LDA projection matrix based on disambiguationguided labeling confidences. CENDA achieves dimensionality reduction by maximizing the dependence between projected features and confidence vectors of candidate labels, where the dependence is quantified by the Hilbert-Schmidt Independence Criterion (HSIC). PLDA further utilizes the weakly-supervised characteristics of partially labeled data.

Given the inherent ambiguity of partially labeled data, DELIN, CENDA and PLDA substitute the ground-truth labels with label confidence. Additionally, these label confidences are dynamically updated based on weighted voting from neighboring instances in projected feature space. Consequently, these methods are confined to operate within a two-stage framework encompassing dimensionality reduction and partial label disambiguation. In this process, the dimensionality reduction phase operates independently from the partial label disambiguation, which may lead to the result of dimensionality reduction being less satisfactory. This paper introduces an wrapped framework that unifies dimensionality reduction and partial label disambiguation, which enables their simultaneous execution in a cohesive manner within one stage. To attain this goal, we present a novel approach termed WPLDR, signifying Wrapped Partial label Dimensionality Reduction through dependence maximization. Specifically, by incorporating the manifold consistency in both the embedded feature space and label space, we propose a unified objective function to conduct confidence-based dimensionality reduction and similarity-based label disambiguation simultaneously. WPLDR maximizes the interdependence between the embedded features and the label confidences, while ensures the manifold consistency between projected instances and the corresponding label confidence vectors. Comprehensive experiments over a broad range of synthetic and real-world partial label data sets validate the effectiveness of proposed WPLDR.

2 RelatedWork

Partial label learning aims to learn from instances with ambiguous supervision, where the ground-truth labels are concealed in candidate label set [Gong et al., 2022; Jia et al., 2024; Wang and Zhang, 2022]. Accordingly, one intuitive way is label disambiguation [Xie et al., 2021], which is usually achieved by two different strategies: averaging-based disambiguation [Cour et al., 2011] and identification-based disambiguation [Jin and Ghahramani, 2002]. Averaging-based disambiguation equally treats each label in candidate label set and attempts to differentiate between the candidate and noncandidate labels [Tang and Zhang, 2017] [Cour et al., 2011], and the prediction is made by aggregating the voting among the candidate labels of its neighboring examples [Xu et al., 2019; Zhang et al., 2016]. Although averaging-based disambiguation is intuitive and easy to implement, the output of ground-truth label is prone to be overwhelmed by the false positive labels in candidate label set, thereby leading to a degradation in the final predictive performance [Gong et al., 2021a].

Identification-based disambiguation aims to recover the ground-truth label, which is treated as a latent variable, achieving disambiguation through iterative optimization of the objective function that includes these latent variables. For example, maximum likelihood methods identify the model parameter by solving θ∗ = argmaxθ ∑mi=1 log(∑y∈Si p(y|xi, θ)), where the posterior probability is characterized by probabilistic graphical model [Liu and Dietterich, 2012; Dempster et al., 1977]. Maximum margin methods define the objective function by maximizing the margin between the ground-truth label and other labels, i.e., (wT yi · xi + byi ) -max ˜ yi̸=yi (wT˜ yi · xi + b ˜ yi ) [Yu and Zhang, 2016; Lyu et al., 2020b]. Despite identification-based disambiguation attempts to recover the ground-truth label, the recovery process can be affected by false positive labels, leading to the error accumulation. In addition, contrary to the above approaches, disambiguation-free approaches induce classification model from partial labeled instances via problem transformation. Specifically, this kind of approaches transform the partial label learning problem into a series of binary classification problems by exploring the opposite relationship between candidate label set Si and noncandidate labels Y \ Si [Zhang et al., 2017; Lin et al., 2022; Wu and Zhang, 2018].

The existing partial label learning literature mainly emphasizes the manipulation of label space. As a classic data preprocessing technique, dimensionality reduction exploits the manipulation in feature space, which is usually helpful to improve the generalization ability of learning algorithms. Depending on whether the label information is used, dimensionlity reduction can be classified into two categories, namely, unsupervised and supervised. Generally, unsupervised dimensionality reduction algorithms directly identify the projection matrix by preserving the underlying data structure. This kind of methods usually utilize manifold learning to achieve dimensionality reduction, including isometric mapping (ISOMAP) [Tenenbaum et al., 2000], locally linear embedding (LLE) [Roweis and Saul, 2000], laplacian eigenmaps (LE) [Belkin and Niyogi, 2006] and locality preserving projection (LPP) [Jia et al., 2023]. Supervised dimensionality reduction depends on ground-truth labels to determine within-class or between-class relationship and define objective function [Jia et al., 2022]. LDA is a representative algorithm, which induces the projection matrix by maximizing the intra-class similarity and minimizing the inter-class similarity simultaneously. In the past few decades, some advances in supervised dimensionality reduction have been studied, such as canonical correlation analysis (CCA), partial least square and latent semantic indexing [Wang et al., 2023]. However, due to the constraints of ambiguous supervision, existing supervised dimensionality reduction approaches are rarely used in partial label learning problem. To the best of our knowledge, DELIN, CENDA and PLDA are the only existing supervised dimensionality reduction approaches towards solving partial label learning. However, constrained by ambiguity supervision, these approaches are forced to utilize a two-stage learning strategy, which means that the dimensionality reduction process and partial label disambiguation process are independent from each other. Therefore, the inconsistency between these two processes may degrade the final performance.

3 The Proposed Approach

In this section, we first present our WPLDR framework, which performs dimensionality reduction and partial label disambiguation simultaneously. Then, an alternating optimization algorithm is introduced to solve the optimization problem.

3.1 Wrapped Partial Label Dimensionality Reduction

Let X = Rd be the d-dimensional instance space and Y = {y1, y2, . . . , yq} denote the label space with q labels. A partially labeled training set is denoted as D = {(xi, Si) | 1 ≤ i ≤ m}, where xi ∈ X is a d-dimensional feature vector (xi1, xi2, . . . , xid)T and Si ⊆ Y is the corresponding candidate label set among in which the ground-truth label yi is concealed. The task of partial label learning is to induce a multi-class classifier f : X ↦→ Y from training set D.

Denote X = [x1, x2, . . . , xm] ∈ Rd×m as the instance matrix and Y = [y1, y2, . . . , ym] ∈ Rm×q as the partial label matrix, where yij = 1 indicates that the j-th label belongs to the candidate label set of xi. Dimensionality reduction aims to seek a projection matrix P = [p1, p2, . . . , pd′ ] ∈ Rd×d′ (d′ ≪ d) to map the instance matrix X into an embedded feature space characterized by d′ -dimensional features, calculated as X′ = P⊤X. Constrained by the ambiguous supervision, previous approaches work in two-stage manner by firstly optimizing the projection matrix, and then leveraging the projected data to conduct candidate label disambiguation. Instead of two-stage dimensionality reduction framework, we attempt to perform dimensionality reduction and partial label disambiguation simultaneously in a unified framework.

To this end, we present a wrapped framework to jointly optimize label confidence, projection matrix and similarity weights to enhance the generalization performance. In this paper, we embrace the confidence-based HSIC as the dimensionality reduction term to induce projection matrix, and use the similarity matrix S ∈ Rm×m to characterize the manifold consistency between embedded feature space and label space. Then the objective function of proposed approach WPLDR is shown as follows:

where F denotes the label confidence matrix. W ∈ {0, 1}m×m is adjacency matrix, in which wij = 1 if there exists an edge iff x′i is among the k nearest neighbors of x′j , otherwise, wij = 0. S is a non-negative similarity matrix. In addition, α and β are the trade-off parameters to balance the dimensionality reduction and manifold information in label and projected feature space.

In the initial stage, the label confidence matrix F, owing to the deficiency of discriminative ground-truth label, is initialized as F0 according to candidate label set as follows:

The processed data set with lower-dimensional features is denoted as D′ = {(x′i , fi)|1 ≤ i ≤ m}, where x′i = P⊤xi. A weighted graph G = {V, E, S} is built on the low dimensional feature space. Here, V = {x′i |0 ≤ i ≤m} denotes the set of vertices, and E = {(x′i , x′j )|x′i ∈ kNN(x′j )} represents the set of edges between x′i and x′j . For the construction of E, there exists an edge iff x′i is among the k nearest neighbors of x′j . S characterizes the similarity weight between (x′i , x′j ), where sij > 0 if (x′i , x′j ) ∈ E, sij = 0 when (x′i , x′j ) /∈ E. Then, based on the graph structure and lowdimensional features, the similarity graph weight matrix S can be calculated by solving the following linear least square problem, which is defined as the reconstruction loss in embedded feature space:

where 1m is a m-dimensional all-ones column vector, the value of sij implies the relative contribution of instance x′i on x′j .

Following the smoothness assumption, which states that the manifold structure in projected feature space should be preserved in label space [Wang et al., 2021; Song et al., 2022], label confidence matrix F = [f1, f2, . . . , fm]⊤ can be optimized by solving the following problem:

In partial label learning, feature vector and label confidence vector elucidates each instance from two perspectives. In our framework, we achieve partial label dimensionality reduction by maximizing the dependence between projected feature and label information. WPLDR employs the HSIC to measure the dependence between them, and the corresponding empirical estimate of HSIC is denoted as:

where tr is the trace operator of matrix. H = I - 1m ee⊤, and e is a column vector with the same value 1. F and Q denote

Inputs:

• D: partial label training data set {(xi, Si) | 1 ≤ i ≤m} (X ∈ Rd , Y = {l1, l2, . . . , lq}, xi ∈ X, Si ⊆ Y)
• d′ : the number of retained dimension after dimensionality reduction
• k: the number of nearest neighbors used to update the label confidence matrix
• α: the feature space trade-off parameter
• β: the label space trade-off parameter
• µ: the constraints trade-off parameter

Outputs:

• P: the d × d′ projection matrix via the WPLDR
• D′ : the transformed lower-dimensional partial label training set {(x′i , Si) | 1 ≤ i ≤ m}

Process:

• 1: Initialize the m× q label confidence matrix F0 as shown in Eq. (2);
• 2: Cascade the training data into the instance matrix X = [x1, x2, . . . , xm];
• 3: Initialize the d × d′ projection matrix P0 via dependence maximization between embedded feature and label information as shown in Eq.(7);
• 4: repeat
• 5: Calculate the similarity matrix S according to the embedded feature vectors and label confidence matrix via Eq.(8);
• 6: Calculate H= I - 1m eeT ;
• 7: Update the label confidence matrix F as shown in Eq. (12), which is a transformed problem of WPLDR in Eq. (1);
• 8: Update projection matrix P, and solve the transformed problem in Eq.(13). Given the generalized eigenvalue problem in Eq.(16), then the projection matrix is obtained by concatenating the d′ eigenvectors w.r.t. the top d′ eigenvalues;
• 9: until convergence
• 10: Derive the lower-dimensional partial label training data sets D′ with d′ features via the projection matrix P, X′ = P⊤X;

Table 1: The pseudo-code of WPLDR.

the reproducing kernel Hilbert space mapped from X and Y respectively. Substituting K = X⊤PP⊤X and L = FF⊤ into Eq.(5) and dropping the normalization term, the objective function is rewritten as follows:

Then, to avoid the impact of scaling, constraint on l2 norm is imposed on p, i.e. p⊤p = 1. Furthermore, considering that the features in projected feature space still remains some redundant information, we introduce a constraint to ensure projected features maintain uncorrelated as pi⊤XX⊤pj = δij, where δij is Kronecker delta function. By combining the above two constraints, we can rewrite the optimization problem in Eq.(5) as:

where µ ∈ (0, 1) is the trade-off parameter to balance the weight of two constraints in inducing projection matrix.

3.2 Alternative Optimization

As shown in Eq.(1), the objective function of WPLDR contains three sets of variables with different constraints, which is hard to be solved directly. Thus, in this paper, we leverage alternative optimization to tackle this problem. Specifically, each set of variables will be iteratively optimized by fixing other sets of variables until convergence or the maximum number of iterations reaches.

Update S with fixed F and P, the objective function of WPLDR is rewritten as:

For each instance, the similarity vector is independent, which indicates that each column in S is independent of other columns. Thus, we optimize the similarity vector one by one. Accordingly, for the j-th instance x′j , the optimization problem of j-th column vector in S is defined as follows:

where x′i ∈ Rd′ denotes the feature vector from embed-

ded feature space. The value of sij in S characterizes the relative importance of neighboring instance x′i on x′j . Furthermore, denote matrix Efj = [fj - fNj(1) , fj - fNj(2) , . . . , fj - fNj(k) ]⊤ ∈ Rk×q and Ex′j = [x′j - x′Nj(1) , x′j - x′Nj(2) , . . . , x′j - x′Nj(k) ]⊤ ∈ Rk×d′ , then the optimization problem in Eq. (9) can be rewritten as follows:

where Gfj and Gx′j are Gram matrices on label space and projected feature space, i.e. Gfj = Efj (Efj )T and Gx′j = Ex′j (Ex′j )T . The optimization problem in Eq. (10) is a standard Quadratic Programming (QP) problem, which can be efficiently solved by off-the-shelf QP tools.

Update F with fixed P and S, the objective problem in Eq.(1) can be stated as follows:

Here, we define a square matrix T = β2 (Im×m -S)(Im×m -

S)⊤ - 1 2 HX⊤PP⊤XH. Although T is symmetric, it may be a indefinite matrix for some datasets. In fact, some optimization tools attempt to solve the indefinte QP problem like Gurobi, but the efficiency is less satisfactory. Fortunately, under close scrutiny, the first term in Eq.(12) is convex, and the last term is concave, thus, it is a constrained convex-concave problem. Accordingly, we can utilize the Convex-Concave Procedure (CCCP) to solve the problem, which solves the original nonconvex problem by optimizing a sequence of convex problems. Specifically, in each iteration, the second term in Eq. (12) is replaced by its first order Taylor approximation, which can be rewritten as the following form:

Update P with fixed S and F, the objective function can be stated as follows:

where µ ∈ (0, 1) is a trade-off parameter which balances the importance of the above two constraints.

By Lagrange method, the Lagrange function is induced as:

where Λ is a diagonal matrix whose entries are Lagrange multipliers. By setting the derivative of Eq.(14) as 0, we can obtain:

Finally, we induce the projection matrix by solving the following generalized eigenvalue problem:

where P is obtained by selecting the d′ eigen vectors of the top d′ eigenvalues.

4 Experiment

4.1 Experimental Setup

To evaluate the effectiveness of proposed WPLDR, we couple five state-of-the-art partial label learning algorithms with four partial dimensionality reduction approaches, DELIN, CENDA, PLDA and the proposed WPLDR. For each partial label learning method L, the coupled version is denoted as L-DELIN, L-CENDA and L-WPLDR respectively.

In this paper, we instantiate L with five well-established partial label learning algorithms, and their parameter configurations are set based on the recommendations provided in corresponding literatures.

• PL-KNN [H¨ullermeier and Beringer, 2006]: an averagingbased partial label learning algorithm, which makes prediction by weighted voting on candidate labels from kNN instances [suggested configuration: k=10].
• PL-SVM [Nguyen and Caruana, 2008]: an identificationbased partial label learning approach which induces classification model by adapting maximum margin [suggested configuration: regularization parameter pool with {10-3 , . . . , 103 }].
• IPAL [Zhang and Yu, 2015]: a disambiguation-based partial label learning method, which determines the valid label via label propagation on weighted graph [suggested configuration: k=10, balancing parameter α = 0.95].
• SURE [Feng and An, 2019]: a self-training partial label learning algorithm, under proper constraints, which unifies the model training and identification of pseudo label into one formulation [suggested configuration: regularization parameters λ = 0.3, β = 0.05].
• PL-AGGD [Wang et al., 2021]: an adaptive graph guided disambiguation algorithm, which jointly performs graph construction, model training and partial label disambiguation in a framework. [suggested configuration: k = 10, µ = 1 and γ = 0.05 ].

In the following subsections, for each dataset, we perform ten-fold cross-validation, while the mean and standard deviation of classification results are reported.

4.2 Results on Real-world Data Sets

Seven real-world partial label data sets have been collected from different tasks and domains. Due to page limit, Table 3 reports the experimental results on real-world as well as synthetic partial label data sets with different configurations. As shown in Table 3, the experimental results illustrate the classification accuracy of partial label algorithms before and after employing three dimensionality reduction approaches DELIN, CENDA, PLDA and WPLDR. According to the reported results on these real-world data sets, the following observations can be concluded:

• Compared with partial label learning algorithms L, across 35 statistical comparisons (7 data sets × 5 algorithms), the prediction accuracy has been significantly improved by employing WPLDR in 26 cases in pairwise t-test at 0.05 significance level. Furthermore, FG-NET is a challenging data set since it holds least number of examples but the second largest average number in candidate labels. The classification improvement by WPLDR indicates that WPLDR can significantly improve the performance in difficult circumstance with insufficient examples and high rate of false positive labels.
• Compared with DELIN, L-WPLDR achieves superior or at least statistically comparable performance against LDELIN across 31 cases out of 35 cases.
• Compared with CENDA, L-WPLDR achieves comparable or better performance in all cases, furthermore, among 35 cases, L-WPLDR achieves significant performance improvement in 22 cases in pairwise t-test at 0.05 significance level.

4.3 Synthetic Data Sets

Following the widely used controlling protocal in partial label learning, synthetic partial label data sets are generated from UCI multi-class data sets with controlling parameter r, which indicates the number of false positive labels added in candidate label set.

For each synthetic data set, we set r as {1, 2, 3} to evaluate the performance under different ambiguity levels.The detailed experimental results with r = 2 are reported in Table 2. In addition, the pairwise t-test at 0.05 significance level is conducted to show whether the performance difference between two comparison methods is significant in statistics, and the results of win/tie/loss counts with r = 1/2/3 are reported in Table 3. Based on these comparative results, the following observations can be concluded:

• Compared with partial label learning algorithms L, across the 105 statistical comparison cases (7 synthetic data sets × 3 configurations × 5 algorithms), the proposed WPLDR achieves superior or comparable classification performance in 98 cases.
• Compared with the existing partial label dimensionality reduction method DELIN, WPLDR achieves comparable or better performance in all cases, while it achieves significant performance improvement in 97 cases in pairwise t-test at 0.05 significance level.
• Compared with the existing PLDA, WPLDR achieves comparable or better performance in 95 cases, while the improvement is more impressive in most cases.
• Compared with the existing CENDA, among all the 105 cases, L-WPLDR achieves comparable or better classification performance in 95 cases.
• For high dimensional dataset amazon, where the dimen-

sion of feature vector exceeds 1,300, compared with L, the classification performance has been improved with WPLDR by more than 0.3 in 14 cases among 15 cases (3 configurations × 5 algorithms). These results indicate the superior performance of WPLDR in difficult settings.

4.4 Sensitivity Analysis

For WPLDR, k (the number of nearest neighbors) is an important paramter. Fig. 1 illustrates how the classification accuracy of each partial label learning algorithm changes as k increases from 3 to 10 with interval 1. As is shown, on these four datasets, the classification accuracy of all partial label learning algorithms coupled with WPLDR is very stable cross different settings of k. Furthermore, the trade-off factors α and β serve as important parameters. In Fig. 2, the values of α and β increase from 0.0001 to 100. As is shown, when coupling with WPLDR, classification accuracy of each partial label learning algorithm is relatively stable across different values of α and

β. According to the empirical studies, we suggest the value of α and β can be simply set as 0.01 and 0.01 in practice.

5 Conclusion

In this paper, we propose a wrapped partial label dimensionality reduction approach, which is the fist attempt towards integrating dimensionality reduction and partial label disambiguation in one stage. To achieve this, WPLDR maximizes the interdependence between the embedded feature space and confidence-based label information, while ensures the manifold consistency between the embedded feature space and label space. Extensive experiments over a broad range of synthetic and real-world partial label data sets validate that WPLDR can significantly enhance the generalization performance of well-established partial label learning algorithms. In future work, we will further investigate how to extend WPLDR to other weakly-supervised learning frameworks.

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 (62225602) and the Big Data Computing Center of Southeast University.