Partial Multi-Label Learning via Multi-Subspace Representation

1 Introduction

Partial Multi-Label Learning (PML) is a weakly supervised multi-label learning framework, where each instance is associated with a set of labels contained redundant information. The task of PML is to learn a precise predictor for unseen instances from the training data with redundant label information. A straightforward way to solve the problem is applying off-the-shelf MLL methods to train the model [Gibaja and Ventura, 2015]. However, the redundant noise labels mixed in training data will degenerate the performance.

To overcome the problem, [Xie and Huang, 2018] proposed the first PML framework, which provided an effective

∗ Indicates equal contribution.

†Corresponding author.

solution to cope with the redundant candidate labels. Existing PML methods can be roughly classified into two categories: unified strategy and two-stage strategy. For unified strategy-based methods, the whole training process is unified, the prediction model is learned with optimizing candidate labels simultaneously. PML-fp and PML-lc [Xie and Huang, 2018] optimized label confidence values and trained the model by minimizing the ranking loss and exploiting data structure information. fPML [Yu et al., 2018] adopted a feature and label coherent matrix to factorize the original matrix for prediction model training. PML-LRS [Sun et al., 2019] utilized the idea of low-rank and sparse decomposition to get the ground-truth labels and trained the model simultaneously. For two-stage strategy-based methods, the whole training process is divided into two stages, including reliable label selection by disambiguating strategy and model training by using the reliable labels. PARTICLE [Fang and Zhang, 2019] developed iterative label propagation to extract credible labels with high-confidence values, then used the credible labels to train the prediction model. DRAMA [Wang et al., 2019] performed the feature manifold to get the reliable labels with high-confidence values and introduced a gradient boost model for training.

Obviously, existing PML methods mainly focus on the noise in label space while the noise concealed in feature space is regrettably ignored, such as shadow and blurry in multi-label image recognition field. If we directly learn the PML model from such ambiguous features, the performance of the learned model would degenerate inevitably. For example, in Figure 1, due to high speed motion, the blue train's feature information is blurred. If the blurred feature information is utilized in the training process directly, the performance of the prediction model will be affected. To get a robust PML model for feature noise, we propose a novel method named partial multi-label learning via MUltiSubspacE Representation(MUSER), which simultaneously utilizes the feature mapping and label decomposition to train the desired model. Specifically, we firstly decompose the original label matrix into a low-dimensional label subspace matrix and a corresponding label correlation matrix. Secondly, we introduce a graph Laplacian regularization to constrain the latent label subspace matrix to keep the intrinsic structure information among feature information. Thirdly, to resist the feature noise information during training process, we employ a low-dimensional feature subspace matrix mapped by feature correlation matrix to train the model, which can reduce the negative effects in feature space and boost performance by offering a more accurate feature matrix. Meanwhile, to ensure the feature subspace space more discriminative, an orthogonality constraint is imposed on the feature correlation matrix. Finally, the unified prediction model is optimized in an alternative manner by minimizing the least square loss. Extensive experiments have demonstrated that our proposed method can achieve superior performance against state-of-the-art methods.

2 RelatedWork

As a weakly supervised multi-label learning framework, partial multi-label learning aims to learn a precise multi-label predictor from training data with redundant labels. Actually, PML can be seen as a fusion of two popular learning frameworks: multi-label learning and partial label learning.

Multi-Label Learning (MLL) aims to predict the groundtruth labels for unseen instances, where each instance is associated with a set of accurate labels [Liu and Tsang, 2017; Liu et al., 2018; Feng et al., 2019]. Existing MLL methods can be roughly divided into two categories: 1) Problem transformation methods tackle MLL problem by processing the multi-label training samples to other learning problems [Boutell et al., 2004]. 2) Algorithm adaptation methods tackle MLL problem by adopting the improvment of the commonly used supervised algorithms [Elisseeff and Weston, 2001; Zhang and Zhou, 2007]. Recently, some weakly supervised MLL frameworks are proposed, but most of them are designed to solve missing labels, such as [Sun et al., 2010; Chen et al., 2015].

Partial Label Learning (PLL) is a weakly supervised multi-class learning framework, where each instance is associated with a set of candidate labels and only one label is correct [Feng and An, 2019a; Feng and An, 2019b; Lyu et al., 2019; Lyu et al., 2020]. Existing PLL methods can be roughly divided into three categories: 1) Averaging disambiguation strategy-based methods predict the groundtruth label by the average outputs from the whole candidate label set [Zhang and Yu, 2015]. 2) Identification disambiguation strategy-based methods predict the ground-truth label by refining the model latent parameters [Jin and Ghahramani, 2003]. 3) Disambiguation-free strategy-based methods learn the PLL model by adapting off-the-shelf learning techniques directly without disambiguation process [Zhang et al., 2017; Wu and Zhang, 2018].

Partial Multi-Label Learning (PML) combines the characteristics of MLL and PLL, where each instance is associated with a set of candidate labels and only a part of the them are relevant. Existing PML methods can be roughly divided into two categories: 1) Unified strategy-based methods tackle the PML problem in a unified framework, where the prediction model is trained with optimizing candidate labels simultaneously [Xie and Huang, 2018; Yu et al., 2018; Sun et al., 2019]. 2) Two-stage strategy-based methods decompose PML problem into two subproblems, refining the candidate labels and training the predictor with the refined candidate labels [Wang et al., 2019; Fang and Zhang, 2019].

3 The ProposedMethod

Formally speaking, we denote X=[x1, x2, ..., xn] ∈Rd×n as the instance-feature matrix for n instances, Y = [y1; y2; ...; yn] ∈ {0, 1}n×q as the candidate label matrix where yi corresponds to i-th instance's label vector, yij = 1 means the j-th label is included in the candidate label set of instance xi, yij = 0, otherwise. PML aims to learn a multilabel model from the feature matrix together with candidate label matrix and assign the predictive labels for unseen instances.

3.1 Formulation

MUSER is a novel PML framework based on multi-subspace representation, which can reduce the negative effects caused by redundant labels and noisy features during training process.

Label Subspace We suppose ˜Y ∈ {0, 1}n×q is the groundtruth label matrix, and it is not accessible to PML algorithm during the training process. Inspired by the low-rank label matrix in multi-label learning that labels are correlated [Yu et al., 2018], the ground-truth label matrix ˜Y can also be assumed to be low-rank in PML. Thus, ˜Y can be reduced to a lower-dimensional label subspace U, which is approximated as the product of two matrices:

where U ∈ Rn×c denotes the instances representation in cdimensional latent label subspace and P ∈ Rc×q encodes the label correlation between q labels and c latent labels. Each original label may be affected by all c latent labels, which implies high-order one-to-all label correlation.

To learn ˜Y effectively, we minimize the reconstruction error between the candidate label matrix Y and the product of U and P as follows:

where R(U,P) denotes the regularization to control the model complexity.

Usually, the ideal latent label subspace is expected to be consistent with intrinsic structural among features [Zhu et al., 2017]. In our model, a graph Laplacian regularization is introduced to ensure such consistency between features and latent labels. Specifically, we define S ∈ Rn×n as a pairwise similarity matrix, where Sij = exp(-‖xi - xj‖22 /σ2 ) if instance i and instance j are the mutually k-nearest neighbors, Sij = 0, otherwise. Then we can get the following regularization term:

where L = E- 12 (E-S)E- 12 is a graph Laplacian matrix and E is a diagonal matrix with Eii = ∑nj=1 Sij . By combining the regularization Eq. (3), the formulation can be updated as follows:

here α, β denote the trade-off parameters.

Feature Subspace As mentioned before, most existing PML methods just focus on the noisy information in label space and lack the consideration of noise in feature space. Actually, in the real-world application, feature information can be often corrupted by outliers and noise, just like label space. Therefore, we introduce the second subspace representation, latent feature subspace, in our prediction model. A feature correlation matrix Q ∈ Rd×m is learned to map the original feature space to a low-dimensional feature subspace, which can provide compact and discriminative feature information for reducing the negative effects caused by noisy feature information. Here m is the dimension of feature subspace. The latent feature representation in m-dimensional subspace can be formulated as X⊤Q.

We further introduce a model coefficient matrixW∈Rm×c , which can map the instance from latent feature subspace to latent label subspace. Accordingly, we can obtain the final objective function for the proposed partial multi-label learning method MUSER:

where R(W, U, P) = γ2 (‖W‖2F + ‖U‖2F + ‖P‖2F ), and the orthogonality constraint for Q is to ensure the latent feature subspace be more compact after mapping.

In summary, MUSER utilizes both label and feature subspace representations to train the desired model. For the label subspace representation, it can reduce the negative effects caused by redundant labels. For the feature subspace representation, it can reduce the feature noise and generate a discriminative feature information. Combining above two subspaces, the trained PML model is desired to be more effective and robust to both feature and label noises.

Prediction In the predict stage, we firstly adopt the obtained feature correlation matrix Q to map the unseen instances matrix X∗ to a latent feature subspace, then we utilize the coefficient matrixW to predict the latent semantics in label subspace, finally we use the label correlation matrix P to recover the ground-truth labels from the label subspace.

here ̂Y is the prediction label matrix corresponding to the X∗ .

3.2 Optimization

Our proposed method is convex and it can be solved effectively by an alternating optimization scheme.

Step 1: Calculate P. With U, Q,W fixed, Eq. (5) can be reduced to:

and we can get the closed form solution:

Step 2: Calculate U. With P, Q,W fixed, we can calculate U by minimizing the following objective function:

The objective function is differentiable, thus U can be optimized via the standard gradient descent algorithm:

∇U is the gradient of Eq (9), λU is the stepsize of gradient descent which is obtained by armijo rule [Bertsekas, 1999].

Step 3: Calculate Q. With U,P,W fixed, the subproblem to variable Q is simplified as:

Similarity to Step 2, we can get Q as follows:

To satisfy the constraint Q⊤Q = I, we map each row of Q onto the unit norm ball after each iteration:

where Qi,: is the i-th row of Q.

Step 4: Calculate W. With P, U, Q fixed, Eq. (5) can be reformulated as follows:

and we can get the closed form solution:

During the entire process of optimization, we first initialize the required variables, then repeat the above steps until the function converges or reach the maximum iterations.

4 Experiments

4.1 Experimental Setup

We conduct experiments on seven PML datasets, which are synthesized from widely-used MLL datasets including Emotions [Trohidis et al., 2008], Genbase [Diplaris et al., 2005], Medical [Pestian et al., 2007], Corel5k [Duygulu et al., 2002], Bibtext [Katakis et al., 2008], Eurlex-dc and Eurlexsm [Menc´ıa and F¨urnkranz, 2008]. These datasets are added with redundant noise labels by the controlling parameter r. Here, r ∈ {1, 2, 3} represents the average number of false positive labels for training examples. Table 1 shows the characteristics of the experimental datasets.

To highligt the strengths of MUSER method, we compare it with six state-of-the-art methods, including MLL methods ML-KNN [Zhang and Zhou, 2007], RankSVM [Elisseeff and Weston, 2001], PML methods PML-fp [Xie and Huang, 2018], fPML [Yu et al., 2018], PARTICLE [Fang and Zhang, 2019], DRAMA [Wang et al., 2019]. We also set the trade-off parameters according to the suggestions in respective literatures. Parameters in MUSER method including α, β, γ are chosen from {10-3 , 10-2 , ..., 102 , 103 } with a grid search manner. Five widely-used multi-label metrics are employed to evaluate each comparing method, including Hamming Loss, Ranking Loss, One-Error, Coverage and Average Precision. Meanwhile, we use 10-fold cross-validation to train the model.

4.2 Experimental Results

Table 3 and Table 4 illustrate the experimental comparisons between our MUSER and other six methods. Due to page limited, we just report part of results, the extra results are reported in the supplementary materials. Out of 735 (7 datasets × 3 configurations × 5 metrics × 7 methods) statistical comparisons, the following observations can be made:

• On twenty-one datasets (7 datasets × 3 configurations) across all evaluation metrics, MUSER ranks 1st in 74.29% cases and ranks 2nd in 17.14% cases.
• For each comparing method, MUSER obviously outperforms the counterpart PML methods including PML-fp, fPML, PARTICLE and DRAMA in 99.05%, 87.62%, 91.43% and 89.52% cases, and significantly outperforms the tailored MLL methods including ML-KNN and RankSVM in 90.48% and 99.05% cases.
• For each evaluation metric, MUSER achieves almost optimal in terms of all evaluation metrics. MUSER is superior to other comparing methods in 96.03% cases on Ranking Loss, 89.68% cases on Hamming Loss, 92.86% cases on One Error, 91.27% cases on Coverage, 96.83% cases on Average Precision.

Furthermore, Friedman test [Demˇsar, 2006] is utilized as the statistical test to analyze the relative performance among the comparing methods in this paper. Table 2 reports the Friedman statistics FF and the corresponding critical value. Then the post-hoc Bonferroni-Dunn test [Demˇsar, 2006] is also utilized to show the relative performance among the comparing methods. Here, MUSER is used as the control method whose average rank difference against the comparing algorithm is calibrated with the critical difference (CD). Accordingly, MUSER is deemed to have a significantly different performance to one comparing method if their average ranks differ by at least one CD (CD = 1.759 in this paper: # comparing methods k = 7, # datasets N = 7 × 3 = 21). Figure 3 illustrates the CD diagrams on each evaluation metric, where the average rank of each comparing algorithm is marked along the axis (lower ranks to the right). In each subfigure, any comparing methods whose average rank is within one CD to that of MUSER is interconnected to each other with a thick line. Obviously, MUSER performs significant superiority against other comparing methods.

4.3 Further Analysis

Robust Analysis: In order to learn the influence of the varying subspace dimensions, we choose the dimension of label subspace c from {10%q, 30%q, ..., 90%q} and feature subspace m from {10%d, 30%d, ..., 90%d}. Figure 2 shows the results of MUSER with different values of m and c over Corel5k. According to the experimental results, it is noted that the performance of MUSER is less sensitive to both m and c, and thus in our experiment, m and c are set to 50% of original feature and label space.

Complexity Analysis: For our proposed model, at each iteration of the method, the main computational complexity includes matrix inversion and multiplication operations. The cost complexity of matrix inversion is O(c3 +m3 ), and generally, m < d and c < q, the overall complexity of MUSER is O(ndq + nq2 + n2 q + nd2 + c3 + m3 ).

Convergence Analysis: We conduct the convergence analysis of MUSER on Medical dataset, where the convergence curve is shown in the left sub-figure of Figure 4. We can observe that the objective function value gradually decreases to a stationary state as the number of iteration increases. Therefore, the convergence of MUSER is demonstrated.

Parameter Analysis: There are three trade-off parameters in MUSER, including α, β, γ. We chose them from {10-3 , 10-2 , ..., 102 , 103 }. To learn the influence of parameters, we show the experimental results of the three parameters under different configurations on Medical dataset. The right three sub-figures of Figure 4 show the performance of MUSER changes as each parameter increases with other parameter fixed. According to the experimental results, the parameters usually follow the optimal configurations (α =

1, β = 1, γ = 1) but vary with minor adjustments on different datasets.

5 Conclusion

In this paper, we propose a novel PML framework named MUSER, which trains a robust model by considering the noise in both feature space and label space. Specially, we use low-rank decomposition to reduce the negative effects of redundant labels and introduce graph Laplacian regularization to ensure the label subspace be in consistent with features, then we utilize feature subspace mapping and orthogonal subspace projection to provide a discriminative feature information. Empirical studies on various datasets demonstrate the superiority of MUSER.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (Nos. 61872032), in part by the Beijing Natural Science Foundation (Nos. 4202058, 9192008), in part by National Key Research and Development Project (No. 2018AAA0100300), and in part by the Fundamental Research Funds for the Central universities (Nos. 2020YJS026, 2019JBM020).