Privileged label enhancement with multi-label learning

1 Introduction

In recent years, the multi-label learning (MLL) framework has been studied for fitting multi-semantic problems successfully [Zhou and Zhang, 2017]. However, MLL can not express the relative importance of each label (i.e., label importance) to an instance, that is a more general label ambiguity problem. It is worth noting that label distribution learning (LDL) [Jia et al., 2018; Ren et al., 2019a; Ren et al., 2019b; Jia et al., 2019a] has been an active research area for the past few years due to its potential to address the label ambiguity problem as well as successful applications in many real-world tasks [Ling and Geng, 2019; Jia et al., 2019b]. In LDL, an instance x is assigned a real number dyx to each possible label y, representing the degree to which y describes x. The LDL model has a stronger expression ability but also puts forward higher requirements for the presentation of training data, resulting in a high cost for labelling the datasets with distribution information. Fortunately, we have many multi-label datasets containing simple logical labels. To utilize existing mutli-label datasets, Xu et al. [2018] proposed a learning paradigm called label enhancement (LE), which aims to recover the hidden label distribution value from the logical labels of the datasets.

∗Corresponding author: Xiuyi Jia. This work is jointly supported by the National Key R&D Program of China (2018YFB1003902), the National Natural Science Foundation of China (61773208, 61906090), the Natural Science Foundation of Jiangsu Province (BK20170809, BK20191287), the Fundamental Research Funds for the Central Universities (30920021131), and the China Postdoctoral Science Foundation (2018M632304).

Label enhancement is to recover the label distributions from the logical labels in the training set via leveraging the topological information of the feature space and the correlation among the labels. One recent attempt is the GLLE [Xu et al., 2018] algorithm which uses a common measurement method to construct a local similarity matrix based on the manifold hypothesis and adds it to the model training as prior knowledge. Another typical algorithm named ML [Hou et al., 2016] assumes that each instance can be optimally reconstructed by using a linear combination of its neighbors, and according to the smoothness assumption, the topological structure of the feature space can be transferred to the label space local by local. In summary, how to mine and leverage additional information is one of the key problems that label enhancement concerns.

In this paper, we propose a privileged label enhancement method with multi-label learning (PLEML). Firstly, we apply a multi-label learning model to generate additional information for LE, which has two advantages: one is that the multilabel learning model itself can capture the mapping relationship between the feature space and the label space, and the predictions given on the instances imply the complex structure information of the data. Another one is that it is an implicit way to leverage additional information, which can avoid introducing noise by constructing structured information manually and lose the structured information of the data itself. Besides, in the multi-label learning procedure, we also adopt the low-rank structure to implicitly exploit the correlation of the labels. Secondly, inspired by [Vapnik and Vashist, 2009], we use LUPI (learning with privileged information) paradigm to make reasonable use of additional information. LUPI focuses on improving the learning with the auxiliary information which is supplied by a teacher about instances at the training stage. Since this auxiliary information will not be available at the test stage, it is referred to as privileged information. Finally, we apply the RSVM+ model as the final prediction model, which is a support vector machine discriminative model implementing the LUPI paradigm. We also compare our proposed method with existing LE methods on 12 real-world datasets. In summary, the major contributions of this paper are:

1. We propose a novel privileged label enhancement method with multi-label learning, named PLEML, which can fully and accurately utilize the additional information to recover label distributions from logical labels.
2. We apply the multi-label learning model to generate the privileged information, which can implicitly capture the complex structural information of the data itself.
3. We introduce the LUPI paradigm to make reasonable use of the generated privileged information. To the best of our knowledge, this is the first try of applying LUPI into the field of LE.

The rest of this paper is organized as follows. Firstly, related works are briefly reviewed. Secondly, the technical details of the proposed approach is presented. Thirdly, the comparative experimental results on different tasks are reported. Finally, we conclude this paper.

2 RelatedWork

The existing LE algorithms are mainly divided into two categories. The first category is fuzzy-based label enhancement, which utilizes the idea of fuzzy mathematics, and uses methods such as fuzzy clustering, fuzzy operation, and nuclear membership to dig out relevant information between labels and convert logical labels into label distributions. For example, the fuzzy clustering-based LE algorithm FCM [Gayar et al., 2006] and kernel-based LE algorithm KM [Jiang et al., 2006]. Another category is graph-based label enhancement, which uses graph models to represent topological structures between instances, and enhances logical labels of an instance to its corresponding label distribution by establishing the relationship between instance correlations and label correlations. Typical graph-based label enhancement methods include label propagation-based LE algorithm (LP) [Li et al., 2015], manifold learning-based LE algorithm (ML) [Hou et al., 2016], and graph laplacian-based label enhancement algorithm (GLLE) [Xu et al., 2018].

Learning Using Privileged Information (LUPI) was first introduced by Vapnik and Vashist [2009], which assumes a teacher-student learning scenario, where a teacher can provide descriptive information (privileged information) about a course (primary data) to assist a student (model) to learn through the guidance of similarity control and knowledge transfer. And the privileged information stands for the information which is only available in the training stage but not available in the testing stage. Besides classification [Yao et al., 2019], privileged information has also been used for clustering [Marcacini et al., 2014], hashing [Zhou et al., 2016], and etc. This paper is the first work to use multi-label learning to generate privileged information for label enhancement.

3 ProposedMethod

3.1 Formulation of Label Enhancement

The main notations used in this paper are listed as follows. Let X = {x1, x2, . . . , xn} ∈ Rn×d denote the feature space, where n denotes the number of instances, d denotes the dimension of the feature. Y = {0, 1}c represents the complete set of logical labels where c is the number of all possible labels. For each instance xi ∈ X, the logical label vector of xi is denoted by yi = {yi1, yi2, . . . , yic}, each element yik = 1 if the label yk is related to xi, otherwise yik = 0. The description degree of y to x is denoted by dyx , and the ground-truth label distribution of xi is denoted by di = {dy1 xi , dy2 xi , . . . , dyc xi }.

Given a training set M = {(xi, yi)|1 ≤ i ≤ n}, LE recovers the label distribution ˆ di of xi from the logical label vector yi, convertingM to label distribution data ˆD = {(xi, di)|1 ≤ i ≤ n}, satisfying ˆ dyk xi ∈ [0, 1] and ∑ck=1 ˆ dyk xi = 1, making the prediction label distribution ¯D as close as possible to the the true label distribution D.

3.2 Privileged Information Learning

With the previous discussion, our goal is to get the prediction value Y ∗ = [y∗ 1 , y∗ 2 , · · · , y∗n ] by utilizing the complex structure information between instances implicitly through multilabel learning, and add Y ∗ to the training of the label enhancement model as privileged information. Therefore, this privileged information should have the following characteristics: 1) Y ∗ is the instance's prediction value, which is not inherited from its original logical labels; 2) The generation process of Y ∗ utilizes structural information transferred from the instance feature space implicitly; 3) Y ∗ has a low-rank property since the labels are related.

To solve this problem, we consider using a linear model for prediction.

here, we add an additional dimension with a constant value of 1 for each data xi(1 ≤ i ≤ n), so xi = [xi1, xi2, · · · , xid, 1]. The offset term ¯bk has been expanded into ¯Wk, and ¯Wk = [ ¯W1k, ¯W2k, · · · , ¯Wdk,¯bk]T represents the weight parameters of the linear model corresponding to the k-th label.

Accordingly, the goal of our method is to determine the best parameter ¯W that can generate the privileged information Y ∗ given the instance xi. Thus our goal becomes to find the optimal model ¯W which minimizes:

where L is the loss function defined on the training data, Ω is a regularizer to control the complexity of the output model, Z is a regularizer to enforce the characteristic of label correlations, and λ1 and λ2 are two parameters to balance the three terms. Here, for easy computation, we use the square of the Euclidean distance as the loss function defined by:

where ‖ · ‖2F denotes the Frobenius norm of a matrix, Y ∗ and Y denote the predicted value and the logical value of the training set, respectively. For the second term of Eq. (2), we simply implement it as follows:

The third term of Eq. (2) is employed to enforce the lowrank structure of the predicted label value, which implicitly exploits the label correlations. However, the rank of a matrix is difficult to optimize, therefore, the trace norm ‖ · ‖tr is utilized in this paper as a convex approximation of the rank of a matrix. The trace norm ‖ · ‖tr is defined as the sum of singular values, i.e., ‖ · ‖tr = ∑i σi(·), where σi is the i-th singular value of the matrix. Thus, the final term of Eq. (2) based on low-rank label correlations is derived as follows:

Formulating the multi-label problem into an optimization framework over Eq. (3), Eq. (4) and Eq. (5), the following optimization problem is obtained:

If the best parameter ¯W is determined, the prediction value of the test instance y∗ i can be generated through Eq. (1). For simplicity, we divide the datasets into 4/5 training set and 1/5 testing set. Therefore, after 5-fold cross-validation, we can get the prediction value of each instance.

Eq. (6) can be optimized by using ADMM [Boyd et al., 2011], thus, we first rewrite our objective into the following equivalent form:

The augmented Lagrangian function of Eq. (7) is:

where Λ is the Lagrange multiplier, ρ is the penalty parameter, and < ·, · > is the Frobenius dot-product. The optimization problem of Eq. (8) can be solved using the alternating solution method.

L-BFGS [Yuan, 1991] can be applied to optimize Eq. (9), and the closed-form solution of Eq. ( 10) can be solved by the singular value thresholding (SVT) algorithm.

3.3 Label Enhancement using Privileged Information

Following the first stage of privileged information learning, the original datasets can be transformed into its essential counterpart: ˜D = {(xi, y∗ i , yi)|1 ≤ i ≤ n}, where xi represents available information, y∗ i represents privileged information, and yi represents logical label values, n represents the number of instances. Here we use the LUPI (learning with privileged information) paradigm to deal with the problem of label enhancement with privileged information. This paradigm focuses on using privileged information about the instances provided by the teacher during the training phase to improve learning. In [Vapnik and Vashist, 2009], RSVM+ model based on the LUPI paradigm for regression is introduced. The main idea of RSVM+ is to define a linear or nonlinear correction function in the privileged space, and use this

Algorithm 1 The PLEML algorithm

Input: Feature matrix X; logical label matrix Y.

Parameter: λ1, λ2, γ, C.

Output: The regression parameters matrix W.

• 1: Initialize Λ,Z, ρ and ¯W;
• 2: solve ¯W in Eq. (8) using ADMMmethod;
• 3: obtain Y ∗ by the Eq. (1).
• 4: Initialize W,W ∗ , ¯W ∗ ;
• 5: solve W in Eq. (12) using penalty function method;
• 6: returnW.

correction function to estimate slack variables in support vector regression methods. Therefore, by converting it to the LUPI paradigm based on RSVM+, we develop a novel label enhancement model. The decision rule and correcting (slack) function are defined as linear functions ˆ dyk xi = xiWk+bk and ξi = y∗ i W ∗ k + b∗k , ˆ ξi = y∗ i ˆW ∗ k + ˆb∗k , respectively. So the objective function of PLEML can be expressed as:

where θ = {Wk,W ∗ k , ˆW ∗ k } are the parameters to be optimized, and {γ,C} are the weighted coefficients. Particularly, we absorb the bias term to obtain a compact variant of the original RSVM+, because it is turned out to have a simpler form in the dual space and can be solved more efficiently. Specifically, for each xi and y∗ i , an additional dimension with a constant value of 1 is added, so the Wk = {W1k,W2k, · · · ,Wdk, bk}, W ∗ k = {W ∗ 1k , W ∗ 2k , · · · ,W ∗ ck , b∗k } and ˆW ∗ k = { ˆW ∗ 1k , ˆW ∗ 2k , · · · , ˆW ∗ ck , ˆb∗k }.

Eq. (12) is an optimization problem with inequality constraints. Therefore, we can choose the penalty function method to solve it [Sun and Yuan, 2006]. The basic idea of the penalty function method is to use a penalty function to convert a constraint problem into an unconstrained problem, and then use the unconstrained optimal method to solve it. The framework of our PLEML is shown in Figure 1 and the detailed algorithm of the proposed method is shown in Algorithm 1.

4 Experiments

4.1 Datasets

There are 12 real-world label distribution datasets in our experiments, including two facial expression datasets SJAFFE [Lyons et al., 1998] and SBU 3DFE [Yin et al., 2006], ten biological experiments datasets Yeast [Eisen et al., 1998]. Some basic statistics about these 12 datasets are given in Table 1.

4.2 EvaluationMeasures

To measure the distance or similairy between the recovered label distributions and the ground-truth label distributions, according to Geng's suggestion [Geng, 2016], six LDL measures are adopted, i.e., Chebyshev distance (Cheb), Clark distance(Clark), Canberra metric (Canber), Kullback-Leibler divergence (KL), Cosine coefficient (Cosine) and Intersection similarity (Intersec). The former four are distance measures and the last two are similarity measures. For Cheb, Clark, Canberra and KL, the smaller the value, the better the generalization performance. For Cosine and Intersec, the larger the value, the better the performance.

4.3 Methodology

We implemented two groups of experiments. In the first group, we use the same binarization method [Xu et al., 2018] to generate the logical labels from the ground-truth label distributions for the regular-scale datasets. Then, we recover the label distributions from the logical labels via the LE algorithms. Finally, we compare the recovered label distributions with the ground-truth label distributions. In the second group, in order to further test the effectiveness of LDL after the LE pre-process on the logical-labeled datasets, we first recover the label distributions from the logical labels via the LE algorithms and then use the recovered label distributions for LDL training. We choose LDL-SCL [Zheng et al., 2018] as the LDL algorithm in this experiment. Finally, the label distributions predicted by LDL-SCL on the recovered data are compared with those predictions made on the original data with ground-truth label distributions.

4.4 Experimental Setting

The performance of PLEML is compared against five label enhancement learning algorithms, including FCM [Gayar et al., 2006], KM [Jiang et al., 2006], LP [Li et al., 2015], ML [Hou et al., 2016], and GLLE [Xu et al., 2018].

With the previous discussion, FCM, KM and LP are fuzzy-based label enhancement, and ML, GLLE are graphbased label enhancement. For the comparison algorithms, parameter configurations suggested in corresponding literatures are used, for GLLE, the parameter Λ is chosen among

{10-2 , 10-1 , · · · , 102 } and the number of neighbors k is set to c+1. The kernel function in GLLE is Gaussian kernel. The parameter α in LP is set to 0.5. The number of neighbors k for ML is set to c+1. The parameter β in FCM is set to 2. The kernel function in KM is Gaussian kernel. For PLEML, the values of the parameters λ1 and λ2 are selected among {2-4 , 2-3 , · · · , 28 }, and γ = 0.1,C = 0.1. For LDL-SCL algorithm, the parameters are set to λ1 = 0.001, λ2 = 0.001, and m = 5.

It is worth mentioning that, for the first group of experiments, it is not necessary to divide the dataset into training set and testing set because LE is a kind of unsupervised learning procedure. Therefore, we can directly apply the privilege information to the whole data. For the second group of experiments, 10 times 10 fold cross-validation is employed for each dataset and the average results are recorded.

4.5 Experimental Results

The experimental result of the first group is summarized in Table 2. For the second group of experiments, due to page limitation and refer to [Xu et al., 2018], we only show the effect on the two evaluation measures of Chebyshev and Cosine in Table 3 and Table 4, respectively. The results of other measures are similar.

From Table 2, we can see that PLEML significantly outperforms FCM, ML, LP, KM on the most measures. Compared with the GLLE algorithm, PLEML performs slightly worse on the SJAFFE and Yeast-spo datasets on all the measures, and performed slightly worse on the Yeast-spoem dataset in terms of Cosine. However, in other cases, the PLEML algorithm is better than the GLLE algorithm. From Table 3

and Table 4, we can find that the PLEML algorithm significantly outperforms other comparison algorithms in terms of Cheb and Cosine. Therefore, we can obtain the following three conclusions: 1) The specialized LE algorithms generally perform better than those algorithms obtained from algorithm adaptation; 2) The predicted label distribution obtained by PLEML fits best with the ground-true label distribution; 3) The LDL model trained with the label distribution dataset obtained by PLEML has the best performance. In summary, the proposed PLEML algorithm has obvious advantages over other well-established label enhancement algorithms.

4.6 Validation

In order to verify that the privileged information obtained through multi-label learning can effectively improve model performance. We conducted an experiment using random values in the range (0, 1) as privileged information combined with the RSVM+ model. The comparison results are shown in Table 5, and "random PI" indicates that only random values in the range (0, 1) are used as the privilege information to learn. From the comparison results of the two experiments, the privileged information obtained through multi-label learning can significantly improve the performance of the label enhancement model. However, the result of PLEML is slightly worse than "random PI" on the dataset SJAFFE in terms of Canberra, because the number of instances is 213, which is relatively small. This may cause the multi-label model to not fully capture the mapping relationship between features and labels, and the resulting privileged information will be inaccurate.

5 Conclusion

In this paper, we studied LE problem and proposed a novel PLEML method by using privileged information, which mainly solves the problem of how to fully and accurately use additional information to enhance model performance in label enhancement. Different from existing methods, PLEML utilizes complex structure information to generate additional information through a multi-label model. RSVM+ based on LUPI paradigm is first introduced to LE problem to utilize the privileged information. The experimental results on several real-world datasets demonstrate the effectiveness of PLEML.