Semi-Supervised Multi-Label Learning with Incomplete Labels

1 Introduction

Multi-label classification is an essential problem in many application domains, including image annotation [Huiskes and Lew, 2008], video classification [Snoek et al., 2006], document categorization [Srivastava and Zane-Ulman, 2002], and gene function prediction [Elisseeff and Weston, 2002]. Different from standard multi-class classification problems, a multi-label prediction function maps an input instance to a vector of interdependent multiple labels. Although multilabel classification can be transformed into a set of independent binary classification problems [Joachims, 1998], this mechanism fails to take the label interdependency into account. Many multi-label learning methods hence have been developed with a central theme of capturing label dependence; e.g., [Guo and Schuurmans, 2011; Elisseeff and Weston, 2002; Minh and Sindhwani, 2011]. A few works have also investigated exploiting unlabeled data to perform semisupervised multi-label learning [Guo and Schuurmans, 2012; Luo et al., 2013]. These methods nevertheless have all assumed training data with complete label assignments.

Complete training labels however are hard to collect in real world problems. In many applications training labels are obtained via crowd-sourcing, which typically leads to label incompleteness [Heymann et al., 2008]. For example, in image or text tagging, human labelers tend to provide only a few keyword labels that describe the most obvious visual or semantic contents, while contents that are rare or ambiguous can be simply omitted. Moreover, the keyword labels provided by different labelers for even similar objects can be different, which can also lead to incomplete labels in the unified label vocabularies from multiple labelers. Label incompleteness can severely degrade the performance of the learned multi-label classification models, since it will build negative prediction patterns between the input instances and the missing labels and further propagate the mistakes into the prediction phase on the test data. This raises the need for learning multi-label classification models that handle incomplete labels. Although standard multi-label learning has received significant attention, multi-label learning with incomplete labels is still far from being well investigated. A number of previous methods only take label imputation as a preprocessing step [Lin et al., 2013; Wu et al., 2013; Zhu et al., 2010; Liu et al., 2010; Sun et al., 2010], which recover labels that are not optimized for the target prediction models. A few others have attempted to take the process of imputing missing labels as part of the prediction model training [Qi et al., 2011; Bucak et al., 2011; Chen et al., 2013], which however either involve complex local training or are limited to supervised learning over the sparsely labeled data.

In this paper, we propose a novel semi-supervised approach to perform multi-label learning with incomplete labels based on a manifold regularized vector-valued learning framework. The approach conducts automatic label imputation with a low-rank matrix recovery model that encodes the natural properties of label existence, while simultaneously performing vector-valued multi-label learning on the completed label matrix by exploiting label correlations. The unlabeled data is incorporated into the learning process by enforcing a vector-valued Laplacian manifold regularization. We formulate the learning process as a joint convex optimization problem, and develop a fast proximal gradient descent with continuation algorithm to solve the optimization problem for a global solution. Experiments are conducted on a variety types of multi-label datasets, and the proposed method demonstrates superior performance over a number of stateof-the-art multi-label methods with incomplete labels.

2 RelatedWork

Multi-label learning with incomplete labels is a problem that hinders information retrieval in many application domains, and has been addressed in a number of previous works. One class of methods attempts to complete the missing labels before classifier training as a pre-processing step; for example, by training only on the labels provided [Yu et al., 2014], performing label completion based on visual similarity and label co-occurrence [Wu et al., 2013; Zhu et al., 2010], performing image-specific and tag-specific linear sparse reconstructions [Lin et al., 2013], enriching an incomplete tagging with synonyms and hypernyms [Liu et al., 2010], or employing label graph propagation [Sun et al., 2010]. Unfortunately, these methods do not directly consider the consequences on multilabel prediction accuracy, which limits their effectiveness.

A few other works have attempted to consider prediction accuracy as part of the process of imputing missing labels. For example, Qi et al. [2011] developed a statistical generative model for mining partially annotated images. This approach however involves complex EM training for local optimal solutions, and is not discriminatively optimized for the target prediction task. Bucak et al. [2011] proposed a ranking based multi-label learning method for image annotation with incomplete labels. Their method exploits the group lasso regularizer to handle incompletely labeled training data when estimating the errors in ranking the assigned labels against unassigned labels. This method however focuses on the prediction model training without exploiting label correlations for label imputation. It does not exploit the unlabeled data either. Chen et al. [2013] proposed a fast image tagging method for multi-label learning from incompletely labeled data. It learns two classifiers to predict tag annotations: one attempts to reconstruct the (unknown) complete tag (label) set from the few observed tags; the other learns a linear mapping from image features to the reconstructed tag set. The two classifiers are combined within a joint convex loss function via coregularization. Their method again is limited to supervised training on the sparse and partially labeled data.

Our proposed method in this paper shares similarity with the work [Chen et al., 2013] in simultaneously learning classifiers from the input features and reconstructing the labels in the label space. But our method provides a principled framework for exploiting key properties of multi-label learning problems, including the natural label sparsity property of multi-label data, and the low-rank property of label matrix induced by the existence of label correlations. Moreover, our method exploits a vector-valued and kernelized multi-label classifier to capture label dependence in the learning process and exploit the unlabeled data via manifold regularization.

3 Approach

In this section, we present a semi-supervised method that simultaneously performs manifold regularized vector-valued multi-label learning and low-rank label matrix recovery on the given training data. By integrating label imputation and multi-label prediction in a mutually beneficial manner, this approach is expected to exploit unlabeled data and label interdependencies to improve multi-label prediction performance. In particular, we consider a set of ℓ labeled instances Dℓ = {(xi, yi)}ℓi=1 and a large set of u unlabeled instances Du = {xi}N=ℓ+u i=ℓ+1 for multi-label learning, where xi ∈ Rd is the input feature vector for the i-th instance, and yi ∈ {+1,-1}n is the label vector for the i-th instance. With incomplete labels, the +1 value in the label vector yi indicates the i-th instance is assigned into the corresponding class, but -1 value only indicates the unknown status of the corresponding label.

3.1 Vector-valuedMulti-label Learning

Multi-label prediction functions map each instance x into a label vector y ∈ Y in the vector space Y, where Y = Rn and n is the number of classes. That is, given labeled training data, we aim to learn a vector-valued function f : X ↦→ Y. The formalism of vector-valued Reproducing Kernel Hilbert Spaces (RKHS) [Micchelli and Pontil, 2005] can be naturally adopted for multi-label function estimation. With regularized least squares loss function, the multi-label learning in the vector-valued RKHS [Minh and Sindhwani, 2011] can be formulated as

for γA > 0, where K denotes an operator-valued positive definite kernel and HK is a Y-valued RKHS with reproducing kernel K. We expect the operator-valued kernel K can provide a mechanism to capture the dependencies among the multiple labels. Hence in this work, we consider the following matrix-valued kernel employed in [Minh and Sindhwani, 2011]

where k(·, ·) is a scalar-valued kernel function, In is an n×n identity matrix, L†out is the pseudo-inverse of the n×n Laplacian matrix Lout over the output label graph. The output nearest-neighbor label graph can be constructed from the label matrix,

by taking each label, i.e., each column of Yℓ, as a data point. The Laplacian matrix Lout can then be computed on this label graph. The trade-off parameter γO satisfies γO ∈ [0, 1], and Q is thus a symmetric and positive semi-definite matrix. The solution of (1) takes the form of f ∗ = ∑ℓi=1 Kxi ai with {ai, i = 1, · · ·, ℓ} ⊆ Y [Micchelli and Pontil, 2005].

3.2 LaplacianManifold Regularization

To exploit the geometric structural information from the large number of unlabeled instances for prediction function learning, graph Laplacian based manifold regularization [Belkin et al., 2005; 2006] can be incorporated into the learning process. Let W ∈ {0, 1}N×N be the adjacency matrix of the knearest-neighbor graph constructed from the input data, such that Wij = Wji = 1 if i ∈ Nk(j) or j ∈ Nk(i), and Wij = Wji = 0 otherwise, where Nk(i) denotes the index set of the k nearest neighbors of the i-th instance. The Laplacian L of the input graph can then be obtained as L = D-W with the diagonal matrix Dii = ∑Nj=1 Wij .

Let Y N denote the N-direct product of Y. For f ∈ HK, the function prediction over all the data instances is f = (f(x1), . . . , f(xN)) ∈ Y N . Then based on the Laplacian matrix, the semi-supervised multi-label learning with vectorvalued manifold regularization can be formulated as

where γA, γI>0. The matrix M is a symmetric positive operator that satisfies 〈y,My〉Y N ≥ 0. Here it will be set as M = L ⊗ In, where ⊗ denotes the Kronecker matrix product, In is the n × n identity matrix, L is the N ×N graph Laplacian matrix described above.

Let G be the N × N symmetric and positive semi-definite Gram matrix produced by the scalar kernel k(·, ·) over all the N data points. Following [Minh and Sindhwani, 2011], we have the following proposition.

Proposition 1. The minimization problem (5) has a unique solution

for vectors ai ∈ Y that satisfy the following linear equation

where J N ℓ is an N × N diagonal matrix, whose first ℓ diagonal entries have value 1, and the rest have value 0. The matrices A and Y are defined as

Proof: The unique solution (6) can be obtained through Representer Theorem [Micchelli and Pontil, 2005; Minh and Sindhwani, 2011]. We can then have

By plugging the instantiations of (9) over all data points back into the objective function (5), and then setting its derivative regarding A to zeros, one can get (7). □

3.3 Semi-supervised Learning with Incomplete Labels

When the label matrix Yℓ in (4) is incomplete, that is, Yij = -1 may either indicate that the i-th instance does not have the j-th label or the j-th label is omitted for the i-th instance, the performance of semi-supervised multi-label learning (5) based on Yℓ will inevitably degrade. To address this problem, we propose to recover the underlying true label matrix Z from Yℓ by augmenting Yℓ via Z = Yℓ + E, where E is an ℓ × n nonnegative augmenting matrix that contains the labels missed from Yℓ, and perform vector-valued multi-label learning over the latent true label matrix Z. Since labels generally present strong correlation patterns and dependence relationships, the latent true label matrix Z should naturally be low-rank. Moreover, since each instance is normally assigned only a few positive labels, Z should also be sparse. Hence we formulate the learning process with incomplete labels as the following joint optimization problem

where Z = [z1, . . . , zℓ]⊤, µ and λ are trade-off parameters, other parameters are same as in (5); ‖ · ‖∗ and ‖ · ‖1 denote the trace norm and L1-norm over matrix respectively. Trace norm is a convex envelope of the rank function. By adding ‖Z‖∗ into the minimization objective function, we encode the low-rank property of the underlying true label matrix Z to capture label correlations. Since Yℓ is given, the L1-norm regularization over E will encode the sparsity property of Z. This joint minimization problem simultaneously performs label matrix recovery within a low-rank sparse matrix recovery framework and conducts semi-supervised multi-label learning with the manifold regularized vector-valued model.

Note the minimization over f ∈ HK in (10) will again lead to the solution in (6) or (9). By plugging the instantiations of (9) over the training data back into the objective function in (10), the optimization problem above can be transformed into the following concrete formulation:

where SN ℓ = [Iℓ, 0ℓ,u] is a ℓ × N selection matrix, which has a left identity matrix of size ℓ and zeros in all other entries; A ∈ RN×n is the parameter matrix defined in (8); ‖ · ‖F denotes the Frobenius norm. Note after solving this optimization problem for A, a new test instance x can be classified by using the kernelized prediction function in (9).

4 Learning Algorithm

The joint optimization problem in (11) is convex, but nonsmooth, due to the existence of the trace norm and L1-norm operators. We develop a fast proximal gradient with continuation algorithm to solve this minimization problem.

For the convenience of optimization, we first consider a relaxed intermediate formulation of (11) by replacing the equality constraint with a penalty regularization term

where ρ is a parameter that controls the enforcement degree of the equality constraint. With a continuation optimization algorithm below, we can gradually increase ρ to enforce the equality constraint in (11) and solve (12) as an intermediate step for solving the optimization problem (11).

For simplicity of presentation, we use Θ to denote all the parameters such that Θ = [A; Z; E]. Then the objective function of (12) can be expressed as the sum of two functions, such as

where

The first function h(Θ) is a convex and smooth function and the second function g(Θ) is convex but non-smooth.

To develop a proximal gradient optimization method, we consider the second order approximation of the objective function F(Θ). For ν > 0, at a given point Θ(t) , we define

where ∇h(Θ(t) ) is the gradient function of h(·) with respect to Θ at the point Θ(t) . Let ℓc(h) denote the Lipschitz constant of ∇h(Θ). Then for ν ≥ ℓc(h), this approximate function becomes an upper bound such that Mν(Θ,Θ(t) ) ≥ F(Θ) [Beck and Teboulle, 2009]. By minimizing Mν(Θ,Θ(t) ), we can reach the next point Θ(t+1)

where ̂Θ(t) = Θ(t) - 1 ν ∇h(Θ(t) ). It is equivalent to the following sub-problems

which have closed-form solutions. The solution for (18) is simply pν(A(t) ) = ̂ A(t) . For the convex minimization with trace norm in (19), its solution can be computed via singular value decomposition ̂ Z (t) = UΣV ⊤ such that

Algorithm 1 Fast Proximal Gradient with Continuation

The closed-form solution of the minimization problem (20) with sparsity inducing norm and nonnegativity constraint can be computed by applying soft-thresholding operator

where abs(·) is the absolute value function, and the operator (·)+ = max(·, 0).

By setting the next point as Θ(t+1) = pν(Θ(t) ), and conducting iterative proximal gradient updates according to (17), a sequence of points, {Θ(0) ,Θ(1) , . . .}, can be obtained to minimize the objective function F(Θ). To speed up the convergence of the optimization procedure, we further adopt the fast proximal gradient update scheme from [Beck and Teboulle, 2009]. Moreover, to enforce the equality constraint Z = Yℓ + E, the ρ parameter in (12) needs to be set as a large value. To improve the convergence speed, we employ a batch-mode continuation strategy which starts with a relatively smaller ρ and then gradually increases the ρ value after a certain number of iterations. The overall algorithm is given in Algorithm 1. In this algorithm, we set λ parameter as λ = 1/√max(ℓ, n), where (ℓ, n) is the dimension size of Yℓ, according to [Wright et al., 2009], to ensure a robust label matrix recovery.

5 Experiments

We report our experimental setting and results in this section.

5.1 Experimental Setting

Datasets. We conducted experiments with six multi-label datasets: corel5k, msrc, mirflickr, mediamill, tmc2007 and yeast. Msrc is a Microsoft Research labeled image dataset with 591 images in 23 object classes. Each image is represented as a vector with 960 GIST [Oliva and Torralba, 2001]

features. Corel5k [Duygulu et al., 2002] is a scene classification dataset. Some labels in this dataset rarely appear, and we selected its top 30 labels to use. This leads to a subset with 4609 images, each of which is expressed as a vector with 499 features. Mirflickr [Huiskes and Lew, 2008] is a large collection of images. We randomly sampled a subset of 5000 images to use, which has 38 labels, and each image is represented as a vector of 512 GIST features. Mediamill [Snoek et al., 2006] is a large video dataset. We used the top 30 labels, which leads to 42,023 instances. Each of its instances is expressed with 120 low-level features. Tmc2007 dataset [Srivastava and Zane-Ulman, 2002] is a large text dataset with 28,596 instances and 22 labels in total. We used its short version with 500 features. Yeast dataset [Elisseeff and Weston, 2002] is a gene function classification dataset with 2417 genes and 14 classes. Each gene is expressed with 103 microarray expression features. The statistical information of the six datasets are summarized in Table 1, where label cardinality (label card.) denotes the average number of labels assigned to each instance.

Approaches. In the experiments, we compared our proposed approach to the following methods: (1) the multi-label ranking method with group lasso regularizer (MLR-GL) [Bucak et al., 2011]; (2) the fast tagging method (FastTag) [Chen et al., 2013]; (3) the large scale empirical risk minimization method with missing labels (LEML) [Yu et al., 2014]; (4) the baseline method, binary relevance (BR); and (5) binary relevance with complete labels (BR-C). The first two methods are state-ofthe-art methods for multi-label learning with incomplete labels. LEML was used to handle missing labels directly in [Yu et al., 2014]. The BR is a baseline method, where we train a binary SVM classifier for each label on the observed incompletely labeled data. The BR-C is same as BR except that we use complete labels. We used libsvm [Chang and Lin, 2011] as implementation for BR and BR-C. For the proposed approach, we used RBF kernels as the input kernel k(·, ·), and set γO=0.5 to compute the matrix-valued kernel. We used 5 nearest neighbor graph to construct the Laplacian matrix on the input data, and set the number of nearest neighbors approximately as 30% of the label dimension size to construct the Laplacian matrix on the output label matrix.

Experiment Setup. For each dataset, we simulate the incomplete label condition by randomly dropping 30% of the observed labels on the labeled training data. For msrc, we randomly selected 80% of the data for training (30% labeled and 50% unlabeled) and used the rest 20% for testing. For all the other five datasets, we randomly selected 500 instances as labeled data and 1000 instances as unlabeled data, and used the remaining data for testing. We compared all methods using the same data setting, and repeated each experiment five times with different random partitions.

For all the methods, we conducted parameter selection by performing 5-fold cross-validation on the training set. We further dropped 20% labels on the labeled training data of each cross-validation to simulate the missing label situation. For our proposed approach, we selected the trade-off parameters γA and γI from {10-7 , 10-6 , 10-5 , 10-4 , 10-3}, and selected µ from {10-5 , 10-4 , 10-3 , 10-2 , 10-1}. Parameter selections via cross validation are also conducted for the other comparison methods accordingly.

5.2 Experiment Results

We measure the classification results in terms of two standard multi-label evaluation criteria: micro-F1 measure and macro-F1 measure, which take both precision and recall into

µ

Figure 2: Parameter sensitivity analysis on msrc.

accounts. The average classification results and their standard deviations in terms of these two criteria are reported in Table 2 and Table 3 respectively.

From Table 2, we can see the three methods, Proposed, MLR-GL and FastTag, which handle incomplete labels, consistently outperform the baseline BR method across all the datasets. The LEML also outperforms BR with large margins on four datasets. This suggests that it is important to address the missing label problem when learning multilabel classifiers on data with incomplete labels. Among the advanced learning methods, MLG-GL, FastTag and LEML demonstrated strengths over each other on different datasets. Our proposed approach on the other hand produced the best results and outperform all the other methods with large margins over five out of the total six datasets. Even on the remaining dataset, mediamill, our result is still very good. Moreover, the proposed approach also consistently outperforms BR-C, which used the complete labels for training. Similar results are presented in Table 3 as well, where the values are given in terms of the macro-F1 score. Among all the methods that handle incomplete labels, the proposed approach produces the best results on four out of the six datasets, while producing the second best results on the other two datasets. The proposed approach also outperforms BR-C on four datasets.

Overall, these results demonstrate the benefit of handling incomplete labels in the learning process. It also clearly shows the advantage of our proposed semi-supervised learning approach which is able to exploit unlabeled data and simultaneously perform label imputation and multi-label learning by exploiting the label correlations.

Impact of missing labels fractions. The results above were conducted with a given label missing fraction. There is one remaining question: How do the comparison methods, especially our proposed approach, perform with different fractions of missing labels? To answer this question, we conducted another set of experiments on the msrc and tmc2007 datasets with a number of different fraction values of missing labels on the labeled training data: ζ ∈ {10%, 20%, 30%, 40%, 50%}. For each given missing label fraction value ζ, we randomly dropped ζ portion of the original observed labels from the labeled training instances, and conducted experiments using the same setting as above. The average and standard deviation results in terms of the two F1 measures are reported in Figure 1.

From the results on both msrc and tmc2007, we can see that the proposed approach greatly outperforms all the other methods in terms of the micro-F1 measure across the whole range of different missing label fractions. In terms of macro-F1, the proposed approach outperforms the other four methods across ζ ∈ {10%, 20%, 30%, 40%} on the msrc dataset, and outperforms all the other methods on the tmc2007 dataset. These results again verified the efficacy of the proposed approach on addressing multi-label learning with incomplete labels.

Parameter sensitivity analysis. We have also conducted parameter sensitivity analysis for the proposed approach on the msrc dataset over the trade-off parameters, γA, γI and µ. The sensitivity analysis results in terms of micro-F1 regarding each parameter are reported in Figure 2, given the other two parameters fixed (γA = 10-5 , γI = 10-5 , µ = 10-3 ). We can see, within the considered range of values, the approach is quite robust in γA and γI given their values are no bigger than 10-5 . The µ parameter that controls the level of lowrank and sparse properties of the label matrix however does not have a very robust value zone and hence needs a good parameter selection procedure such as cross-validation.

6 Conclusion

In this paper, we proposed a semi-supervised method to address multi-label learning with incomplete labels, which integrates two functions, label imputation and multi-label prediction, in a mutually beneficial manner. Specifically, the proposed method conducts automatic label imputation within a low-rank and sparse matrix recovery framework, while simultaneously performing vector-valued multi-label learning and exploiting unlabeled data with vector-valued manifold regularization. With a least squares loss function, we formulated this problem as a joint convex optimization problem over the latent label matrix and the classification model parameters. We then developed a fast proximal gradient descent with continuation algorithm to solve it. We conducted experiments on a variety types of multi-label datasets, and compared our proposed approach with a few related methods. Our experimental results suggest the proposed approach can effectively improve multi-label classification performance on datasets with incomplete labels over the existing state-of-the-art methods.

Acknowledgments

This research was supported in part by NSF grant IIS1422127.