{'fraction_non_alphanumeric': 0.0337664595193603, 'fraction_numerical': 0.013776020164269263, 'mean_word_length': 4.751562109472632, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Partial Multi-label Learning with Noisy Label Identification

Partial multi-label learning (PML) deals with problems where each instance is assigned with a candidate label set, which contains multiple relevant labels and some noisy labels. Recent studies usually solve PML problems with the disambiguation strategy, which recovers ground-truth labels from the candidate label set by simply assuming that the noisy labels are generated randomly. In real applications, however, noisy labels are usually caused by some ambiguous contents of the example. Based on this observation, we propose a partial multi-label learning approach to simultaneously recover the ground-truth information and identify the noisy labels. The two objectives are formalized in a unified framework with trace norm and `1 norm regularizers. Under the supervision of the observed noise-corrupted label matrix, the multi-label classifier and noisy label identifier are jointly optimized by incorporating the label correlation exploitation and feature-induced noise model. Extensive experiments on synthetic as well as real-world data sets validate the effectiveness of the proposed approach.


Introduction
Multi-label learning (MLL) solves problems where each object is assigned with multiple class labels simultaneously (Zhang and Zhou 2014). For instance, an image may be annotated with labels sea, sunset and beach. A large number of recent works have witnessed the great successes that MLL has achieved in many research areas, e.g., music emotion recognition (Trohidis et al. 2008), text categorization (Lin et al. 2018) and image annotation .
In traditional multi-label studies, a basic assumption is that each training instance has been precisely annotated with all of its relevant labels. However, in many real-world scenarios, it is difficult and costly to obtain precise annotations. Instead, it is more common that a set of candidate labels are roughly assigned by noisy annotators. In addition to the relevant labels, the candidate set may also contain some noisy labels, where the number of relevant or noisy labels is unknown. For example, in crowdsourcing image tagging (as  Figure 1: An example of partial multi-label learning. The image is partially labeled by noisy annotators in crowdsourcing. Among the candidate labels, house, tree, car, light and cloud are ground-truth labels while flower, cat and people are noisy labels. shown in Figure 1), among the candidate labels annotated by annotators, only some of them are accurate ones owing to potential unreliable annotators. The scenario has been formalized as a learning framework called partial multi-label learning (PML) by .
To solve PML problems, one straightforward method is to simply treat all the candidate labels as relevant ones. Then the PML problem can be solved by standard multi-label learning algorithms, e.g., Binary Relevance (BR) (Boutell et al. 2004), ML-kNN (Zhang and Zhou 2007), CPLST (Chen and Lin 2012) and so on. However, such methods will be misled by the noisy labels in the candidate set, and fail to generalize well on future data.
In order to deal with the challenge, several PML techniques are proposed recently. Among them, the most commonly used strategy to learn from PML examples is disambiguation. It tires to recover ground-truth labeling information from candidate labels, by either introducing labeling confidences Fang and Zhang 2019) or employing low-rank and sparse decomposition scheme (Lijuan Sun and Jin 2019). Despite the advances these methods have achieved, a potential limitation is that they neglect the cause of noisy labels in the candidate set, which may be an important information for recovering the ground-truth labels. These methods typically assume that noisy labels are generated randomly, which may be not consistent with many real-world scenarios. In practice, we observe that noisy labels are usually caused by some ambiguous contents of the example and there thus existing some relationships between the noisy labels and feature representations. For example, in crowdsourcing annotation scenario, annotators may be misled by some ambiguous contents associated with the example in specific tasks. Figure 1 illustrates an example in crowdsourcing image tagging, annotators provided the image with noisy labels flower, cat and people due to the misleading objects marked by the red, green and blue boxes. Similar cases also happen in other tasks, such as ambiguous words in the text categorization and ambiguous melody fragments in the music emotion recognition.
Based on the observations mentioned above, in this paper, we propose a new approach for Partial Multi-label Learning with Noisy label Identification (PML-NI), which recovers the ground-truth labeling information and identifies the noisy labels simultaneously. Specifically, the multi-label classifier and noisy label identifier are learned jointly under the supervision of the observed noise-corrupted label matrix. On one hand, the multi-label classifier is constrained to be low rank by trace norm regularization to capture the correlation among labels; on the other hand, the noisy label identifier with sparsity regularization is trained to model the feature-induced noise labels. Comprehensive experiments on synthetic as well as real-world data sets from diverse domains validate that the proposed approach consistently outperforms the compared methods.
The rest of this paper is organized as follows: Section 2 reviews some related works; Section 3 introduces our proposed PML-NI approach; experimental results are reported in Section 4, followed by the conclusion in Section 5.

Related Works
Partial multi-label learning is a powerful framework to deal with partially labeled data in multi-label setting. It is derived from two popular learning frameworks: multi-label learning and partial label learning.
There are plenty of literature on multi-label learning. Among them, Binary Relevance is the most simple approach which decomposes the task into a set of binary classification problems (Boutell et al. 2004). There are many studies trying to exploit the label correlations for enhancing the multilabel learning (Zhu, Kwok, and Zhou 2017;Huang, Yu, and Zhou 2012). Some of them focus on pairwise correlation (Li, Song, and Luo 2017), while some others consider high order correlation among all labels (Burkhardt and Kramer 2018;Read et al. 2011).
Partial label learning (PLL) is a framework for learning from partially labeled data for single label tasks (Grandvalet and Bengio 2004;Jin and Ghahramani 2002). In PLL problem, the partial label set consists of exactly one ground-truth label and some other noisy labels. The most common strategy applied in PLL methods is disambiguation, which tries to recover the ground-truth label from the candidate set (Feng Lei 2019; Zhang, Zhou, and Liu 2016). The disambiguation strategy are mostly implemented in two ways: one is to assume certain parametric model and the ground-truth label is regarded as the latent variable which can be iteratively refined by optimizing certain objectives, such as the maximum likelihood criterion (Grandvalet and Bengio 2004;Jin and Ghahramani 2002;Liu and Dietterich 2012) or the maximum margin criterion (Yu and Zhang 2017); the other one is to assume equal importance of each candidate label and then make prediction by averaging their modeling outputs. For parametric models, the averaged outputs for all candidate labels are distinguished from the outputs for candidate labels (Cour, Sapp, and Taskar 2011). For non-parametric models, the predicted label for unseen instance is determined by averaging the candidate labeling information from its neighboring examples in the PL training set (Hüllermeier and Beringer 2006;Zhang and Yu 2015). Compared to partial label learning, PML is much more challenging owing to the number of ground-truth labels in the candidate set is unknown.
To solve PML problems, the most intuitive method is to treat all candidate labels as relevant ones. In this case, PML problem can be solved by off-the-shelf multi-label learning algorithms. Nevertheless, such methods will be misled by the noisy labels in the candidate set, which may lead to degraded performances. In order to overcome this problem, some techniques are designed to solve PML problems recently. For example,  propose two effective methods PML-lc and PML-fp by introducing a confidence value for each candidate label. The decomposition scheme is utilized to tackle PML data in (Lijuan Sun and Jin 2019). PARTICLE (Fang and Zhang 2019) identifies the credible labels with high labeling confidences by employing an iterative label propagation procedure. Despite the advances these methods have achieved, a potential limitation is that they do not consider the cause of noisy labels in the candidate set, which may be an essential information for solving PML problems.

The Proposed Approach
For each partially labeled training example, we denote by x i ∈ R d a feature vector and its corresponding label vector y ∈ {0, 1} q with q class labels. Let Y = [y 1 , y 2 , ..., y n ] ∈ {0, 1} q×n denote the noise-corrupted label matrix. In this setting, y ji = 1 means the j-th label is a candidate label to the i-th instance. We further denote by y ∈ {0, 1} q the unknown ground-truth label vector.

The PML-NI Framework
As mentioned in the above discussion, in many real-world scenarios, noisy labels are usually caused by some ambiguous contents of the example and there thus existing some relationships between noisy labels and feature contents. Here we model the noisy labels as the outputs of a linear mapping from the feature representations as follows: where y i − y i represents the noisy label vector for instance is a weight matrix and s = [s 1 , s 2 , ..., s q ] is a bias vector. For convenient describing, we set V = [ V , s] and φ i = [x i ; 1], in which we call V the noisy label identifier. Accordingly, the goal of our framework is to determine the optimal parameter V * that can correctly identify the noisy labels given the feature vector φ i . However, the ground-truth label y i here is unknown and the equation in Eq.
(1) is thus intractable. To solve the problem, we propose a joint learning framework that can identify the noisy labels while training the multi-label classifier simultaneously: Here, W is the joint learning model that consists of the multi-label classifier U and noisy label identifier V . The classifier U = [ U , t] tries to provide each training example φ i with its ground-truth label y i , where U = [ u 1 , u 2 , ..., u q ] and t = [t 1 , t 2 , ..., t q ] are weight matrix and bias vector, respectively. L is the loss function to minimize empirical loss between modeling outputs W Φ and is the feature matrix. R is a regularization term to control the model complexity, where λ is a balancing parameter. For simplicity, we choose the least square loss for model training and square Frobenius norm to control the model complexity, and then the optimization problem in eq. (2) can be re-written by: However, the classifier and identifier here are unconstrained and their individual abilities, i.e., ground-truth label prediction and noisy label identification are hardly considered. To deal with the problem, in the following content, we will show how to capture their intrinsic property and potential structure information by employing different regularizers for each of U and V . Therefore, the optimization problem in Eq.
(3) can be firstly reformulated as follows: Here, Ω and Ψ are regularizers to encourage the classifier and identifier to perform their individual abilities, where β and γ are balancing parameters.
In multi-label learning, a common assumption is that there existing the label correlations among different labels (Zhu, Kwok, and Zhou 2017;Lijuan Sun and Jin 2019) and the feature mapping matrix U is thus linearly dependent. The low-rank assumption is thus naturally used to capture this intrinsic property of the classifier. Therefore, the optimization problem can be defined by incorporating the label correlation exploitation: Note that the goal of identifier V is to correctly identify noisy labels mixed up in the candidate set. On one hand, as aforementioned, noisy labels are usually caused by some specific contents, i.e., only a few of ambiguous feature, which are sparse among the observed feature matrix; on the other hand, noisy labels occur occasionally and tend to be sparse among observed candidate labels. In order to make full use of these two kinds of sparsity, we assume that the feature mapping matrix V also contains some sparsity and employ 0 norm regularizer as a feature-induced noise model to capture such structure information. Therefore, the optimization problem can be defined by incorporating the feature-induced noise model: min However, it is difficult to solve the optimization problem in Eq.(5) due to the rank and cardinality operators are highly nonconvex and computationally NP-hard (Fazel, Hindi, and Boyd 2004;Wright et al. 2008). Therefore, these operators are relaxed by their convex surrogates, i.e., the trace norm (Candès and Recht 2009) and 1 -norm (Candes and Tao 2005). The final optimization problem can be re-written as follows: min The optimization problem in Eq.(6) can be solved effectively by alternating optimization.

Alternating Optimization
After substituting the constraint into Eq.(6), the optimization problem can be re-arranged as follows: +β U tr + γ V 1 which can be effectively solved by alternatively optimizing U and V .
When V is fixed, the optimization problem in Eq. (7) with respective to U can be reformulated as follows: The accelerated proximal gradient descend has been proved to be an effective optimization technique for trace norm minimization to solve this problem . Let The main steps are summarized as follows: • Choose θ 0 = θ −1 ∈ (0, 1], L > 1, U 0 = U −1 , η > 1. Set k = 0.
• In the k-th iteration, The iteration continues until convergence. In the above steps, we have omitted the procedures for obtaining U k+1 and next we will show this. The problem can be rewritten as This can be solved by Singular Value Thresholding (SVT) (Cai, Candès, and Shen 2010), which performs singular value decomposition on and then the solution is given by U Σ V.
When U is fixed, the optimization problem in Eq.(7) with respective to V can be reformulated as follows: The problem can be solved effectively by employing the shrinkage operator (Lin, Chen, and Ma 2010). Let which is called shrinkage operator and the optimal param- where L is the Lipschitz constant. And then the closed solution can be obtained (Combettes and Wajs 2005): where V ki and H ki are i-th dimensional values of k-th label for V and H.
The entire optimization procedure will be terminated when the overall loss converges.

Experiment Experimental Setting
We perform experiments on totally ten data sets including synthetic as well as real-world PML data sets 1 . These data sets spanned a broad range of applications: image and corel16k for image annotation, music emotion, music style and birds for music recognition, genbase for protein classification as well as medical, enron, bibtex and tmc2007 for text categorization. Table 1 illustrates the number of instances, number of class labels, cardinality and domain for each data set. We also did some pre-processing to facilitate the partially labeling as in Fang and Zhang 2019). Specifically, for data sets with too many class labels (more than 100 in our experiments), their rare labels are filtered out to keep under 15 labels, and instances without any relevant labels are filtered out.
There are different criteria for evaluating the performances of multi-label learning. In our experiments, we employ five commonly used criteria including ranking loss, hamming loss, one error, coverage and average precision. More detail about these evaluation metrics can be found in (Zhang and Zhou 2014). For the ranking loss, hamming loss, one error and coverage metrics, the smaller value, the better the performance. For the average precision metric, the larger the value, the better the performance.
To validate the effectiveness of the proposed PML-NI method, we compare with three state-of-the-art PML algorithms and two well-established MLL approaches as follows: • PARTICLE (Fang and Zhang 2019). It transforms the PML task into a multi-label problem through a label propagation procedure. Then a calibrated label ranking model is induced to instantiate two PML methods PAR-VLS and PAR-MAP. • PML-LRS (Lijuan Sun and Jin 2019). It utilizes low-rank and sparse decomposition scheme to capture the groundtruth label matrix and irrelevant label matrix from the observed candidate label matrix. • ML-kNN (Zhang and Zhou 2007). It is a nearest neighbor based multi-label classification method. ML-kNN is a very popular baseline method in multi-label learning literature owing to its simplicity. • CPLST (Chen and Lin 2012). It is a typical label embedding approach in MLL, which integrates the concepts of principal component analysis and canonical correlation analysis.
For the comparing methods, parameters are set as suggested in the original paper, i.e., PAR-VAL and PAR-MAP: balancing parameter α = 0.95 and credible label elicitation threshold thr = 0.9; PML-LRS: balancing parameters are set as γ = 0.01, β = 0.1 and η = 1. For CPLST, we take the first 5 principle components following the experimental setting in . k is set as 10 for all the nearest neighbor  (Chang and Lin 2011) is used as the base learner to instantiate PAR-VLS and PAR-MAP. For PML-NI, balancing parameters are set as λ = 1, β = 1 and γ = 0.5.
For the last 8 data sets, to construct partial multi-label assignments for the training data, we simulate the annotation process by using a svm classifier trained on original supervised multi-label data sets as the human annotator. Specifically, a svm classifier is firstly trained on the multi-label data set. Then, for each instance x i of the data set, we add the irrelevant noisy labels of x i with α% number of ground-truth labels according to their probabilities to be relevant labels predicted by the svm classifier and the α% is varied in the range {50%, 100%, 150%}. To examine the performance of the proposed approaches, we performed experiments with all possible percentages of the noisy labels. In the following content, we will show details of three groups of experiments on these totally 26 data sets including 24 synthetic and 2 real-world data sets.

Comparison Results
Due to the page limit, we follow the setting in (Fang and Zhang 2019) to only report detailed results of each comparing methods in terms of ranking loss and average precision in Table 2 and 3, while similar results can be observed in terms of other evaluation metrics (the detailed results in terms of hamming loss, one error and coverage are reported on supplementary materials). When compare PML-NI approach with other methods, our algorithm shows significant superiority. It achieves the best performance in most cases. Among the five comparing approaches, PML-LRS shows some superiority, and is better than PML-NI in three cases on enron in terms of ranking loss and one case on corel16k in terms of average precision, while losses for other cases.
PAR-MAP outperforms PML-NI in one case on genbase in terms of average precision, while losses for other cases.
To validate the effectiveness of PML-NI for real applications, we also perform experiments on real-world PML data sets music emotion and music style. The results show that PML-NI achieves the best results in almost all cases except for the data set music emotion where PAR-VAL and PAR-MAP outperform PML-NI in terms of average precision.
Furthermore, we also use Friedman test (Demsar 2006;Zhang, Zhong, and Zhang 2018;Lijuan Sun and Jin 2019) as the statistical test to analyze the relative performance among the comparing approaches. Table 4 reports the Friedman statistics F F and the corresponding critical value with respective to each evaluation metric. For each evaluation metric, the null hypothesis of indistinguishable performance among the comparing algorithm is rejected at 0.05 significance level.
Then, the post-hoc Bonferroni-Dunn test (Demsar 2006;Zhang, Zhong, and Zhang 2018;Lijuan Sun and Jin 2019) is utilized to illustrate the relative performance among comparing approaches. Here, PML-NI is regarded as the control method whose average rank difference against the comparing algorithm is calibrated with the critical difference (CD). Accordingly, PML-NI is deemed to have significantly different performance to one comparing algorithm if their average ranks differ by at least one CD (CD = 1.3912 in our experiment: # comparing algorithms k = 6, # data sets N = 8 × 3 = 24). Figure 2 shows the CD diagrams ((Demsar 2006)) 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 algorithms whose average rank is within one CD to that of PML-NI is interconnected to each other with a thick line. It can be observed that PML-NI achieves the best (lowest) average rank in terms of all evaluation metrics. These experimental results convincingly validate the significance of the superiority for our PML-NI approach.

Sensitive Analysis
In this section, we study the influences of three balancing parameters, λ, β and γ for the proposed approach on the real-world data sets. We conducted experiments by varying one parameter while keeping the other two parameters fixed. Due to the page limit, we only show the experimental results which are measured by the five evaluation metrics on realworld data set music emotion in Figure 3, while the results on real-world data set music style are reported on supplementary materials. As we can see, in general, performance is not sensitive to the parameters except for the parameter β, whose performance will be significantly degraded when the value of β is too large (approximates to 100 in the experiment). Therefore we can safely set them in a wide range in practice.

Conclusion
In this paper, we disclose the phenomenon that noise labels are usually caused by some ambiguous contents of the example. Based on this observation, we propose to learn partial multi-label problems in a novel strategy by exploiting the potential connections between noisy labels and feature contents. Under the supervision of the observed label matrix, the proposed PML-NI approach jointly learn the multilabel classifier and noisy label identifier by incorporating the label correlation exploitation and feature-induced noise model. Experiments results validate that the proposed approaches are superior to state-of-the-art approaches. In the future, we plan to improve the PML-NI method by considering various forms of noisy labels and utilizing more powerful learning models.