Weakly Supervised Multi-Label Learning via Label Enhancement

1 Introduction

Multi-label learning (MLL) [Zhang and Zhou, 2014] framework has been widely studied because of its success in fitting multiple semantic meanings problems. In MLL, each instance is associated with multiple labels simultaneously, so it requires investigation of a large number of candidate labels one by one, which is usually impracticable due to the high cost of data labeling process. Thus, labels are usually missing in the training set. To deal with the performance deterioration of MLL caused by the missing labels, a paradigm which is often called weakly supervised multi-label learning (WSML) [Xu et al., 2018a] is proposed. It is worth mentioning that semi-supervised MLL is a special case of WSML when the observed label sets of some instances are empty. Figure 1

∗Corresponding author.

graphically illustrates the data setting of WSML studied in this paper.

Formally speaking, let X = Rd be the d-dimensional feature space and Y = {1,-1}c be the c-dimensional label space. Given the WSML training set D = {(xi, yi) | 1 ≤ i ≤ n}, where xi ∈ X is the d-dimensional feature vector and yi ∈ Y is the corresponding c-dimensional binary label vector with some entries missing. The task of WSML is to learn a predictive model h : X → Y from D, which maps an instance to a relevant label set rather than a single label.

There are some previous work studying the WSML problem. Some approaches formulate this task transductively, i.e., assume the training instances with missing labels include the test instances [Goldberg et al., 2010; Xu et al., 2013; Wu et al., 2014], and others are inductive, i.e., try to assign a set of proper labels for any unseen instance [Yu et al., 2014; Wu et al., 2018; Dong et al., 2018; Zhu et al., 2018]. The accessible labeling information of the training set is logical, i.e., each label is either regarded to be relevant or irrelevant. Accordingly, the previous approaches deal with the WSML problem by exploiting such incomplete logical labels directly.

Nonetheless, logical label only reflects the absolute relationship between a label and an instance, but ignores the relative importance of each label to an instance, i.e., logical label is essentially a simplification of the semantic information. Furthermore, the missing labels worsen the inherent semantic deficiency of the logical training set, i.e., the exploitable information becomes less. To handle such problem, we assign description degrees to each label to enrich the information, which is similar to label distribution learning (LDL) [Geng, 2016]. Moreover, we adopt generalized description degree (GDD) [Xu et al., 2019] to accommodate more flexibility to WSML data. The GDDs of all the labels constitute a data form called generalized label distribution (GLD) for a particular instance. Specifically, GDD simulates the relative importance in two aspects:

• dij ∈ (0, 1) represents the relevant degree, which varies among the relevant labels. For example, a multi-scenery image may exhibit different region size for each scenery, so the relevant degree of each scenery label to the image is different.
• dij ∈ (-1, 0) denotes the irrelevant degree of the irrelevant label. For example, for an instance "chair", the irrelevant degree of label "television" is larger than the label "sofa".

A key yet under-addressed issue is that GLD is not explicitly available in the training set. It needs to be somehow recovered from the training set, a process which is named as Label enhancement (LE) [Xu et al., 2018b]. Accordingly, a novel two-stage approach named Weakly Supervised Multi-label Learning via Label Enhancement (WSMLLE) is proposed under the inductive setting. The basic strategy of WSMLLE is to recover GLDs by leveraging structural information modeled by sparse reconstruction in the feature space, where the local correlations in the label space are incorporated into an alternative optimization procedure. After that, the multi-label predictive model is induced from the training instances with the GLDs based on tailored multivariate regression techniques. To our best knowledge, it is the first attempt to unify the complement of missing labels and the recovery of GLDs into the same framework. Comprehensive experimental studies clearly validate the effectiveness of WSMLLE.

The rest of this paper is organized as follows. Firstly, related works on WSML 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

This work is related to two branches of studies, WSML and LE. WSML algorithms have been proposed in recent years, which were pioneered by [Sun et al., 2010]. Then, many algorithms are designed subsequently and they can be roughly categorized into two groups based on the different assumptions about test data.

A straightforward strategy to this problem is formulating it transductively, i.e., assuming the training data with missing labels include the test data. For example, Goldberg et al. [Goldberg et al., 2010] concatenate features and labels and apply the matrix completion technique to it. Xu et al. [Xu et al., 2013] utilize the side information to accelerate matrix completion and develop strong theoretical guarantees. Wu et al. [Wu et al., 2014] recover the missing labels through label consistency and label smoothness.

For better generalization to unseen instances, algorithms working in an inductive learning setting are also proposed, i.e., the test data are unknown when learning the predictive model. For example, Yu et al. [Yu et al., 2014] assume there is a linear relationship between the feature and label matrices. Wu et al. [Wu et al., 2018] decompose the whole label matrix as the sum of a sparse matrix and a low-rank matrix. Dong et al. [Dong et al., 2018] consider both instance similarity and label similarity and further employ ensemble learning to improve robustness. Zhu et al. [Zhu et al., 2018] exploit both global and local label correlations through learning a latent label representation.

LE aims at recovering the label distributions from the logical labels in the training set, which is conceptualized by Xu et al. [Xu et al., 2018b]. And they propose a dedicated algorithm named GLLE. There are also other algorithms with similar function to GLLE, such as FCM [El Gayar et al., 2006] and KM [Jiang et al., 2006], which build the membership degrees for the labels, whereas LP [Li et al., 2015] and ML [Hou et al., 2016] establish the relationship between instances and labels by graph to enhance the label distributions.

3 The Proposed Approach

3.1 ProblemDefinition

As shown in Section 1, suppose X = [x1, x2, . . . , xn] ∈ Rd×n is the feature matrix and Y = [y1, y2, . . . , yn] ∈ {1, 0,-1}c×n is the corresponding label matrix with randomly missing entries. yij = 1 indicates the i-th label is relevant to the j-th instance and yij = -1 otherwise. yij = 0 means the relationship between i-th label and xj is unknown. The task of WSML is to learn a predictive model h : X → Y from the training set D = {(xi, yi) | 1 ≤ i ≤ n}. Y is called observation matrix and D is the reasonable GLD matrix recovered from X and Y .

3.2 GLDMatrix Recovery

Our goal is to recover a complete GLD matrix D that satisfies the following three properties simultaneously. (1) The information in D is inherited from the observation matrix Y . (2) The recovery of D leverages the structural information transferred from the feature space. (3) Label correlations conduce to estimate a certain label.

Accordingly, we formulate this problem as

where L is a loss function and R is the function to mine the latent information from the feature space and the label space. λ is the parameter trading off the two terms.

Since the information in D is inherited from the observation matrix Y , the loss function is set as:

where the sign function sign(x) equals to 1 if x > 0, -1 if x < 0 and 0 if x = 0, which enforces the sign consistency of D with Y . We adopt the hyperbolic tangent function to approximate the sign function for solvability:

To characterize the underlying structure of the feature space, a weighted graph G =< V, E,W > is constructed, where V is the vertex set corresponding to the training instances, E is the sparsely connected edge set, and W = [w1, . . . ,wn] is the weight matrix encoding the structural information. According to the smoothness assumption that instance can be reconstructed by a linear combination of its neighboring instances, we instantiate W by modeling the relationship between one instance and all the other instances via sparse reconstruction, in whichWij is regarded as the influence of xj over xi. W can be obtained columnwisely by solving the minimization problem:

where X-i is the feature matrix excluding xi, i.e., X-i = [x1, . . . , xi-1, xi+1, . . . , xn] ∈ Rd×(n-1) . The second term guarantees the sparsity and α is the tradeoff parameter. Here we solve Eq.(4) by Alternating Direction Method of Multiplier (ADMM) [Ghadimi et al., 2015].

Suppose the structural information in the feature space is preserved in the label space, i.e., the influence of xj over xi can be transferred to dj over di. Then the GLD matrix can be learned through minimizing the reconstruction error in the label space L(D) = ∑ni=1 ‖D-iwi - di‖22 . This is a standard quadratic programming problem which can be efficiently solved by any off-the-shelf QP toolbox. Thus, from the perspective of feature structure, the recovered GLD is formulated as dj ≈ Dwj .

Moreover, the label correlations conduce to the recovery of GLDmatrix. Intuitively, the correlative labels tend to have similar description degrees. However, estimating label correlations from incomplete training set is noisy. Therefore, instead of specifying any label correlation matrix, we optimize the Laplacian matrices together with the GLD matrix iteratively. Inspired by the investigation of [Zhu et al., 2018] that label correlations may vary among regions, we partition the whole training set into g regions {X1 , . . . ,Xg } by clustering, where Xk ∈ Rd×nk has nk instances. Let Y k and Dk be the observation submatrix and GLD submatrix corresponding to Xk , and Rk be the Laplacian matrix of region k. Also, W k is calculated region by region. Accordingly, from the perspective of label correlations, the GLD in region k can be denoted as dkj ≈ Rk dkj . Synthesizing the feature structure and label correlations, the GLD matrix is characterized by Dk ≈ RkDkW k , which leads to the following function to minimize:

Substituting Eq.(3) and Eq.(5) into Eq.(1), we have the following objective function:

where Rk is replaced by LkLk⊤ and a constraint diag(LkLk⊤) = 1 is added for avoiding the trivial solution Rk = 0 and guaranteeing Rk to be a normalized Laplacian matrix.

Eq.(6) can be solved by alternating minimization. In each iteration, fix one of {D, L} and update the other with gradient descent. Specifically, with Lk s (i.e., Rk s) fixed, the target function of Dk yields:

The gradient of the objective w.r.t. Dk is

where ◦ is the Hadamard product. The superscripts k of {Y ,D,W,R} on the right-hand side of this equality are omitted for brevity. When Dk s are fixed, Eq.(6) reduces to:

so the gradient w.r.t. Lk is

where the superscripts k of {D,W,L} are also omitted. To satisfy the constraint diag(LiL⊤i ) = 1, each row of Li is projected onto the unit norm ball after each update.

3.3 Predictive Model Induction

Replace the observed labels with the recovered GLDs, the training set can be transformed into ˜D = {(xi, di)}. As the output di is real-valued, it is natural to induce the predictive model by employing multi-output regression techniques. Here we proposed a predictor based on multi-regression support vector machines. We tailor the following regression problem:

where Θ = [θ1, . . . , θc] is weight matrix and b = [b1, . . . , bc]⊤ is bias vector. β1, β2 and β3 balance the model complexity (the first term) and the empirical regression loss (the rest of terms). Specifically, the second term penalizes the case where the model predictions do not fit the GLDs:

ui = ||ei|| = √e⊤i ei with ei = di-Θ⊤ϕ(xi)-b. ϵ creates an insensitive zone around the estimate where the loss u less than ϵ is ignored. The third term restricts the sign consistency:

Here, vij = Dij (θ⊤ i ϕ(xj) + bj ). The last term ensures the average output from relevant labels to be larger than the average output from irrelevant ones, which has been widely used in inexact MLL algorithms [Cour et al., 2011]:

where Si and Si are the relevant and irrelevant label set of xi respectively. 1⊤Si (1⊤Si ) corresponds to a c-dimensional vector whose k-th entry equals to 1 if Dki > 0 (Dki < 0) and 0 otherwise.

To minimize Ω(Θ, b), we use an iterative quasi-Newton method called Iterative Re-Weighted Least Square [Tuia et al., 2011]. According to the Representer Theorem [Smola and Sch¨olkopf, 1998], under fairly general conditions, a learning problem can be expressed as a linear combination of the training examples in the feature space, i.e., θj = ∑ni=1 ϕ(xi)κij , and then kernel trick can be applied.

4 Experiments

To evaluate the effectiveness of WSMLLE, extensive experiments are conducted on 14 LDL datasets and 10 MLL datasets compared with several state-of-the-art LE algorithms and WSML algorithms respectively.

4.1 LE with Full Labels andMissing Labels

Experimental Setup

A total of 14 real-world LDL datasets are employed for performance evaluation 1 . The binarization method [Xu et al., 2018b] is adopted to get the logical labels from the real label distributions. Considering the missing ratio (M.Ratio) by randomly dropping {0%, 60%} logical labels, we recover the label distributions and compare them with the ground-truth label distributions. As mentioned in Section 3, in the training sets, Yij ∈ {1, 0,-1} where the missing labels are set to 0. The label distributions recovered by all algorithms are normalized before evaluation. All algorithms use the same data setting for each dataset.

According to [Geng, 2016], we choose 6 LDL evaluation metrics, i.e., Chebyshev distance (Cheb), Clark distance (Clark), Canberra metric (Canber), Kullback-Leibler divergence (KL), cosine coefficient (Cosine) and intersection similarity (Intersec). The first four are distance measures and the last two are similarity measures.

WSMLLE is compared with 5 LE approaches reviewed in Section 2, including FCM, KM, LP, ML and GLLE. The parameter λ in WSMLLE is chosen among {0.01, 0.1, 1} and the number of clusters g is chosen among {1, 2, · · · , 10}. The kernel function is Gaussian kernel. The clustering algorithm is k-means. The parameters of the comparing algorithms are the suggested configuration in [Xu et al., 2018b].

Results

For quantitative analysis, Table 1 and Table 2 tabulate the recovery results on Cheb and Cosine with 60% M.Ratio, and The best results are highlighted in bold face. For each evaluation metric, ↓ indicates the smaller the better while ↑ indicates the larger the better. The results on other evaluation metrics are similar and are not shown due to page limitation. The tables show that WSMLLE achieves the best performance in most cases excluding Natural Scene. This is because GDDs of relevant labels are very close and the GDDs of irrelevant labels are almost equal, but WSMLLE cannot exert its advantage fully.

1 http://palm.seu.edu.cn/xgeng/LDL/index.htm#data

The average rank of each algorithm on all datasets is shown in Table 3. As can be seen that WSMLLE achieves optimal (lowest) average rank in terms of all evaluation metrics. WSMLLE ranks 1st in 81.0% cases across all evaluation metrics with 0% M.Ratio, while ranks 1st in 92.9% cases with 60% M.Ratio. The success of WSMLLE can be attributed to the loosened contraint and simultaneous learning of the recovered label distributions, weighted graph encoding the structural information and Laplacian matrices encoding the label correlations. Specifically, WSMLLE loosens the least squares loss constraint to sign constraint, which accommodates more flexibility to description degrees. The weighted graph utilizes the topological structure of the feature space. And the learning of Laplacian matrices circumvents the difficulty of specifying label correlations manually. Overall, the above experimental results clearly show that WSMLLE can effectively recover the label distributions from the logical labels.

4.2 WSML withMissing Labels

Experimental Setup

To thoroughly evaluate the classification performance of learning from weakly supervised data, we conduct comparisons across 10 real-world datasets 2 3 with {20%, 40%, 60%} M.Ratio. Half of the instances in each dataset are randomly chosen as the training set while the other half as the test set. To reduce statistical variability, the mean results and the standard deviation over 10 independent repetitions are recorded. All algorithms use the same data setting for each dataset.

7 widely-used multi-label measures are employed for evaluating from various aspects, including one-error, coverage, ranking loss, average precision, instance-AUC, macroaveraging F1 and micro-averaging F1.

WSMLLE is compared with 4 state-of-the-art WSML algorithms described briefly in Section 2: GLOCAL [Zhu et al., 2018], MLML-APPROX [Wu et al., 2014], SSWL [Dong et al., 2018], WELL [Sun et al., 2010], and 2 representative MLL algorithms: RANK-SVM [Elisseeff and Weston, 2002] and MLkNN [Zhang and Zhou, 2007]. The setting in the first stage of WSMLLE is in accordance with Section 4.1, and β1, β2 and β3 chosen among {0.1, 1, 10}. For the comparing algorithms, parameter configurations suggested in the literatures are used, i.e., GLOCAL: tradeoff parameter λ = 1; MLML-APPROX: class similarity parameter η = 10, sample similarity parameters k = 20 and h = 7; SSWL: tradeoff parameters α, β and ζ chosen among {10-2 , · · · , 102 }; WELL: tradeoff parameters α = 100, β = 10, and γ chosen among {100 , · · · , 104 }; RANK-SVM: RBF kernel with h = 0.01; ML-kNN: neighbor size k = 10, smoothing parameter s = 1. What needs to be pointed out is that RANK-SVM and ML-kNN cannot handle the missing labels directly, so the missing labels must be recovered at first, here we use MAXIDE [Xu et al., 2013] and the resultant combinations are represented as MAX.+RANKSVM and MAX.+ML-kNN.

2 http://mulan.sourceforge.net/datasets-mlc.html

3 http://www.kecl.ntt.co.jp/as/members/ueda/yahoo.tar

Results

We roughly organize the 10 datasets with 5 being regularscale (the first five in Table 4, each of which includes no more than 5000 instances) and 5 being large-scale (the last five in Table 4, each of which includes more than 5000 instances). RANK-SVM has difficulty in large-scale datasets so it is not applied to the large-scale datasets. Due to page limitation, only parts of the most representative evaluation metrics are listed in Tabel 4 while other results are similar.

The two-tailed t-tests at the 5% significance level are performed. Based on the experimental results of comparative studies, it is impressive to observe that:

• Among these 1155 statistical tests (5 regular-scale datasets×3 kinds of M.Ratio×7 evaluation metrics×6 comparing algorithms + 5 large-scale datasets×3×7×5 comparing algorithms excluding RANK-SVM), WSMLLE achieves superior performance against the comparing approaches in 95.2% cases.
• On regular-scale datasets, WSMLLE is significantly better in 93.3% cases, and on large-scale datasets, WSMLLE is signficiantly better in 97.5% cases.
• On large-scale datasets, WSMLLE significantly outperforms all the comparing algorithms in terms of ranking loss, average precision, instance-AUC and macroaveraging F1, and is comparable to all the comparing algorithms in terms of other evaluation metrics.

Across all the datasets, WSMLLE performs better against other WSML algorithms, especially on large-scale datasets. It is because that the structural information and label correlations on large-scale datasets are easier to be fully utilized. These results further demonstrate that WSMLLE has strong capability to recover the missing labels and enhances the reasonable GLDs, and verify the effectiveness of these enhanced GLDs, which can offer richer labeling information to the subsequent learning process. Thus, the proposed approach can make more accurate multi-label predictions.

5 Conclusion

In this paper, the problem of WSML is studied where an innovative two-stage approach named WSMLLE is proposed. Different from existing approaches, WSMLLE considers GLDs which are not explicitly available in the training sets. WSMLLE recovers the missing labels and enhances the GLDs from the logical labels simultaneously through utilizing the structural information in the feature space and label correlations learned from the label space. Then a tailored predictive model is induced to make multi-label prediction. Comprehensive experiments over a range of tasks clearly validate the reasonability of the recovered GLDs and the effectiveness of these GLDs for weakly supervised multi-label learning.

Acknowledgements

This research was supported by the National Key Research & Development Plan of China (No. 2017YFB1002801), the National Science Foundation of China (61622203), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Collaborative Innovation Center of Wireless Communications Technology.