Incomplete Label Distribution Learning

1 Introduction

Classical machine learning tasks assume that one label is either associated with an instance or not. However, in some real applications, labels may be associated with an instance to some degree, thus each instance is annotated by soft labels rather than a single label or a set of labels. Label Distribution Learning (LDL) [Geng, 2016], which learns a mapping from a particular instance to a distribution across all the labels, can assign the relevance of a label to a particular instance. In recent years, LDL has been successfully used in facial age estimation [Geng et al., 2013], action detection in videos [Geng and Ling, 2017], facial expression recognition [Zhou et al., 2015], crowd opinion prediction [Geng and Hou, 2015] et al.

Despite the fact that LDL has been applied successfully in recent years, one problem with existing LDL methods is that they are designed for data with complete supervised information. Nevertheless, in reality, annotation information may be incomplete. In practice, annotations are often given by human annotators, thus assigning each label a real value to indicate its association with a particular instance will result in a large cost in labor and time, especially when there is a large number of labels and instances. On the other hand, for some labels, it may be difficult to give an accurate value to indicate how they are related to a particular instance. All these phenomena will result in training data with incomplete supervised information, thus one question is put forward, that is, how to do LDL with incomplete annotation (IncomLDL).

∗This work was supported by the NSFC (61333014), the Collaborative Innovation Center of Novel Software Technology and Industrialization, and the Huawei Fund (YBN2017030027).

At first glance, it may be trivial to adapt existing LDL algorithms to fit for the IncomLDL problem. Some of the LDL algorithms are based on maximum entropy model [Geng et al., 2010; 2013; Geng, 2016]. This type of algorithms can be adapted by optimizing the sum of entropy of observed labels only. There are some other LDL algorithms transforming the LDL problem into binary classification by sampling labels according to their relevance degree [Geng, 2016]. They can also be adapted to incomplete case by using the observed supervised information as sampling weights. Even if these algorithms can be adapted to solve the IncomLDL problem, note that they treat each label separately, ignoring the fact that LDL is used in scenarios when labels are interlaced with each other [Geng and Ling, 2017]. Without considering the correlation between labels, when facing the severe incomplete annotation, training instances for each single label will be tremendously reduced, thus we need much more training instances to learn a classifier as good as that learned from complete data. Thus label correlations should be exploited to reduce the effect of lacking training data in IncomLDL. Moreover, although one advantage of LDL is that this learning paradigm can take label correlation into consideration by assigning similar relevances to similar labels, however, when annotations are missing, such similarities would also lost. Without such similarity, we need find new ways to characterize the label correlation in IncomLDL.

Multi-label learning (MLL) [Zhou and Zhang, 2017], which assumes each instance is associated with multiple labels, is highly related to LDL problem. However, there is a fundamental difference between MLL and LDL. MLL assumes one label is either related to an instance or not, while in LDL, the relative importance of each label is used in describing the instances. Similar to LDL, MLL also faces the incomplete annotation problem, and various algorithms are proposed based on low-rank assumption [Xu et al., 2013], instance-level smoothness [Wu et al., 2016], and label embedding [Bi and Kwok, 2014]. However, these algorithms are required to give the hard 0/1 label for multi-label data, while in LDL, the prediction is constrained to be within a probability simplex for a particular instance. Furthermore, adding the probability simplex constraint to the non-smooth unconstrained incomplete MLL problem will result in difficulty in optimizing, thus new optimization algorithms are need to be exploited to solve the new problem.

In this paper, we will solve the IncomLDL problem by considering the correlation between labels, which has never been considered by previous LDL algorithms. Considering labels are correlated and determined by a few factors, we will assume the label distribution matrix is low-rank and propose an optimization objective based on trace norm minimization [Cai et al., 2010]. Our optimization objective will require the entries in the observed positions of the recovered label distribution matrix to be close to those observed values, under the constraint that the recovered label distribution for every instance should form a probability simplex. By showing that following the standard analysis of convex optimization, it is non-trivial to get the optimum solution using the accelerated proximal gradient descend technique [Tseng, 2008], we will additionally develop an alternating direction method of multipliers [Boyd et al., 2011] algorithm. Experiments on 15 real label distribution data sets with various missing percentages validate the effective of the proposed algorithms.

The paper is organized as follows. In Section 2 we will briefly review related work. Our proposed two algorithms IncomLDL-prox and IncomLDL-admm will be introduced in Section 3. We will show experimental results in Section 4, followed by conclusion in Section 5.

2 RelatedWork

Label distribution learning (LDL) [Geng, 2016] is first proposed to solve the facial age estimation problem [Geng et al., 2010; 2013] by noticing the fact that instances at neighboring ages are similar. In such problems, a distribution across all ages is more desirable than a single age for a face. Later on, [Geng, 2016] discovers that in some real applications the distribution across all labels is more desirable than the association of a single label to an instance. For example, in biology experiments, the gene expression level across all time period is more desirable than the expression level at a particular time point [Geng, 2016]; in facial expression recognition, we can hardly use a particular pure emotion to describe an expression, but a mixture of several basic emotions [Zhou et al., 2015]. Additionally, for some applications, there is natural uncertainty in annotation, thus the instance is annotated by a distribution across labels rather than a single label or a set of labels. One example is crowdsourcing data such as movie ratings [Geng and Hou, 2015], in which different people may have different attitudes, thus the crowd opinion will naturally form a distribution across labels.

Various algorithms have been proposed for LDL, divided into three groups. One group is based on optimizing the sum of log-likelihood of all training labels and instances. Two representative algorithms, IIS-LDL [Geng et al., 2013] and BFGS-LDL [Geng, 2016] belong to this group, using improved iterative scaling [Pietra et al., 1997] and BFGS [Nocedal and Wright, 2006] respectively to do optimization. Another group of algorithms is based on problem transformation [Geng, 2016], transforming LDL into binary classification problem by sampling from the original LDL data using the description degree of that label as sampling weight. After sampling, base learners such as SVM or Naive Bayes are used to do binary classification, forming algorithms PT-SVM and PT-Bayes respectively. The final group of LDL algorithms are those based on algorithm adaptation. Existing algorithms such as kNN [Geng, 2016] and boosting [Xing et al., 2016] are adapted to fit the LDL schema.

When facing the training data with incomplete annotation, some of these algorithms can be adapted to deal with it. However, these algorithms treat each label separately, ignoring the fact that LDL is used in scenarios when labels are interlaced with each other [Geng and Ling, 2017]. Without considering the correlation between labels, when facing the incomplete annotation, training data for a particular label will be dramatically reduced, thus we will require much more training data to give a satisfactory classifier. Moreover, although LDL can naturally exploit label correlation [Geng, 2016] by assigning similar description degrees to similar labels, we want to state that when there are missing data in the label distribution matrix (for example up to 90% in our experiments), most of the annotation will be missing. It is hard for LDL to acquire the similarity information from the incomplete annotations, thus the classical way how LDL exploit label correlation cannot be used, we need to find new ways to characterize label correlation for IncomLDL.

Multi-label learning (MLL) [Zhou and Zhang, 2017] assumes each instance is associated with a set of labels. Label distribution learning is a natural extension of multi-label learning, by extending the crisp 0/1 label belongingness to soft probabilistic label belongingness. There are abundant studies about multi-label learning with incomplete label assignments [Sun et al., 2010; Yang et al., 2013; Bi and Kwok, 2014; Wu et al., 2016]. Trace norm minimization [Goldberg et al., 2010; Zhao and Guo, 2015; Xu et al., 2013; Yu et al., 2014] has been popularly used, for that it equals to the low-rank assumption on label matrix, which implicitly exploits the label correlation. These approaches are not directly applicable to LDL, because rather than crisp 0/1 label outputs, the LDL outputs are constrained to follow a probability simplex.

To summarize, we need to propose new LDL algorithms which can deal with incomplete supervised information. By considering the label correlation, our proposed algorithms should give a better result than existing LDL algorithms.

3 The IncomLDLMethods

3.1 Formalization

We will give a more formal definition of LDL. LDL assigns a value dyx called description degree to instance x for a particular label y, which indicates the relevance of the label y to the instance x. In LDL, all dyx -s for a particular instance form a probability simplex. Note that dyx is not the probability that y correctly labels x, but the proportion that y accounts for in a full description of x [Geng, 2016]. All labels with non-zero dyx -s are actually the correct labels to describe the instance, where their relative importance is measured by dyx .

Let X ∈ Rn×d be the feature matrix, where n is the number of instances and d is the number of features, thus the ith row of X will be instance xi. D ∈ Rn×m is the label distribution matrix, where m is the number of labels and Dij is dyj xi . Since the supervised information for one instance should follow the probability simplex, we have ∑mj=1 Dij = 1 ∀i ∈ [n] and Dij ≥ 0 ∀(i, j) ∈ [n] × [m].

When we are dealing with the incomplete annotation, we assume that entries in label distribution matrix D are uniformly random missing. Let Ω ∈ [n] × [m] denote the indices of observed entries sampled uniformly at random from D. We denote the observed label distribution matrix by ˜D, which has equal size of D, with entries in the observed positions same as D and entries in unobserved positions 0. Specially, we will have linear operator RΩ : Rn×m → Rn×m defined as,

Finally, we will use ‖ · ‖F to denote the Frobenius norm of a matrix, and ‖ · ‖tr to denote the trace norm of the matrix, which is the sum of all singular values.

Based on the above notation, to solve the IncomLDL problem, we will propose a learning objective based on squared loss and a regularizer exploiting label correlations. Specially, we will have the following optimization objective,

where W ∈ Rd×m is our learning objective. 1n and 1m are the length n and m vectors with all its entries equaling one, respectively. 0n×m is an all-zero matrix of size n ×m.

In Eq. 1, we assume that there is a linear relationship between the label matrix D and feature matrix X since linear classifiers have acquired good performance in previous studies [Geng, 2016]. In this way, the recovered label matrix will be ˆD = XW, where W is the linear coefficients and will be our learning objective.

To exploit the correlation between labels, we assume that D is low-rank, i.e. XW has a small trace norm. λ is the regularization parameter trading off the importance between trace norm and the difference in Frobenius norm in those observed positions. Because the recovered supervised information for each matrix need to be in the probability simplex, that is, nonnegative and summing up to one, we add constraint XW× 1m = 1n to make sure that each row of ˆDwill sum up to one and XW ≥ 0n×m to constraint all entries to be nonnegative. Combining all these aspects, we will have Eq. 1 as our learning objective for IncomLDL problem.

3.2 Optimizing using Proximal Gradient Descend

Following [Xu et al., 2013], we will first use Accelerated Proximal Gradient Descend to optimize Eq. 1, which can achieve a convergence rate of O(1/T 2 ) [Tseng, 2008], where T is the number of iterations. Since it is difficult to handle the trace norm of XW, we will assume X is orthonormal without losing of generality. If X is not orthonormal, we can do SVD on X and use the top right singular vectors as a replacement for X. After assuming X is orthonormal, the optimization will become,

Ignoring the constraints, Accelerated Proximal Gradient Descend will optimize Eq. 2 iteratively. In the tth iteration, it will introduce an auxiliary variable Yt, which is,

After introducing Yt, we have the following subproblem in the tth iteration,

which has closed form solution by SVT [Cai et al., 2010].

Note that here L is the Lipschitz constant which can be found by linear search, i.e., we will initialize L and increase it until the following is violated.

where ℓ(Wt+1) = ‖RΩ(XW- ˜D)‖2F /2.

One problem with the above procedure is that, it is used for unconstrained problem, while in our setting, the problem is constrained. One straightforward solution is to project the solution Wt onto the set defined by the constraints, that is, we will project each row of ˆDt = XWt onto the probability simplex. Assuming the ith row of ˆDt is ˆdit , to do projection, we will solve the following problem,

while without misunderstanding, we will omit i and t in ˆdit .

The above problem has an O(m log m) solution by sorting all the elements in ˆd in descending order into u. Then we find the maximum position index ρ such that θ = uρ + (1 - ∑ρi=1 ui)/ρ > 0. With ρ, we will get the optimal d in which dj = max{ ˆ dj + θ, 0}, ∀j ∈ [m]. The proof of correctness of the projection procedure can be found in [Duchi et al., 2008; Wang and Carreira-Perpi˜n´an, 2013].

After we get the Rprob( ˆDt) which project each row of ˆDt onto a probability simplex, we will recover Wt as follows,

which has closed-form solution as (X⊤X)† [X⊤Rprob( ˆDt)].

Algorithm 1 IncomLDL-prox

• 1: Initialization: θ1 = θ2 ∈ (0, 1], W1 =W2, L, γ > 1, and stopping criterion ϵ
• 2: t = 2;
• 3: while stopping criterion is not satisfied do
• 4: Calculate Yt by Eq. 3
• 5: CalculateWt+1 by Eq. 4
• 6: while Eq. 5 is satisfied do
• 7: L = L ∗ γ
• 8: UpdateWt+1 by Eq. 4 with the new L
• 9: end while
• 10: θt+1 = (√θ4 t +4θ2 t - θ2 t )/2 11: t = t +1
• 12: ˆDt =XWt
• 13: Calculate each row of Rprob( ˆDt) by solving Eq. 6
• 14: UpdateWt by Eq. 7
• 15: end while

The IncomLDL-prox algorithm which uses accelerated proximal gradient descend with a projection onto the probability simplex is shown in Alg. 1.

There remains one question, that is, does the projection procedure really lead to a minimum of the following constrained optimization problem in the tth iteration?

where Qt = Yt - X⊤RΩ(XYt-1 - ˜D)/L

Note the Lagrange dual problem of Eq. 8 is as following,

where α and B are Lagrange multipliers associated with the equality constraint and inequality constraint respectively. A ∈ Rn×m is the catenation of m α-s. Dλ/L[·] is the SVT solver [Cai et al., 2010].

To solve Eq. 8, we will first solve α and B for the Lagrange dual problem. With the optimal solution α∗ and B∗ , the original unconstrained optimizer W∗ can be calculated. However, maximizing Dλ/L[·] does not have closed-form solution for α and B. Although Algo. 1 solves the problem by calculating Dλ/L[Qt] and then projecting the solution to a probability simplex, it cannot be guaranteed to find the optimal solution following the standard analysis of convex optimization [Boyd and Vandenberghe, 2004]. Thus we need to find new optimization strategy to optimize Eq. 1.

3.3 Optimizing using ADMM

ADMM (Alternating Direction Method of Multipliers) [Boyd et al., 2011] which is suitable to those objectives summing up a smooth function and a non-smooth function, is proper for solving Eq. 1. To use ADMM, we first rewrite our objective into the following equivalent form,

where

Eq. 9 can be solved by the following alternative methods in iteration t,

in which Eq. 11 can be rewritten into

which has closed form solution. Thus the problem remained is how to solve Eq. 10.

Assuming M = XW, we rewrite Eq. 10 here,

We can decompose the above problem into optimizing each row of M, while the ith row of M is denoted as Mi, so is Λi, ˜Di, Zi and Ωi,

Although in [Duchi et al., 2008; Wang and CarreiraPerpi˜n´an, 2013], the projection onto a probability simplex problem is solved using an O(mlogm) algorithm by brute force searching through [m] from the largest entry to the smallest one for a particular j satisfying the KKT condition, the algorithm is inefficient to be used here. The reason is the m entries in Mi are divided into Ωi and ¯Ωi, and the non-zero Mijs will have different weights and different projection objectives due to the KKT condition, thus we need to search all possible positions in Ωi and ¯Ωi for a pair of perfect solution, which will cost a lot of time (O(m2 ) for the worst case) and cannot guarantee a unique optimal solution. Thus we will solve Eq. 13 by forming it into a standard QP problem, and use state-of-the-art QP solvers, such as interior-point-method.

Algorithm 2 IncomLDL-admm

After we get M∗ , we can project it back into the space defined by X through (X⊤X)† [X⊤M∗ ]. We will summarize the proposed IncomLDL-ADMM algorithm in Alg. 2

According to [He and Yuan, 2012], our IncomLDL-admm will converge at O(1/T) rate to the optimum solution. Although it is slow compared to the O(1/T 2 ) rate by accelerated proximal gradient descend method, in practice, a good approximate solution is sufficient to obtain satisfactory performance [Boyd et al., 2011].

4 Experiment

We evaluate the proposed algorithms for IncomLDL problem on 15 real data sets. We implement our approaches in Matlab. All the results were obtained on a Linux server with CPU 2.53GHz and 48GB memory.

The algorithm is evaluated on 15 data sets covering fields of biochemistry, natural scene recognition, facial expression and movie-rating. Details of them can be found in [Geng, 2016]. Here we summarize their statistics in Table 1.

Settings andBaselines Tomake these data sets incomplete, we will use two kinds of settings. In the first setting, we will make all elements in the label distribution matrix uniformly random missing and call it the (general) incomplete setting. We vary the observed rate ω% from 10% to 40%, and measure the difference between the groundtruth and the predicted label distribution matrix. We will then test our proposed algorithm in the second setting, the transductive setting, in which we have 10% test data with no supervised information, accompanied by incomplete training data, while the observed rate ω% will also vary from 10% to 40%. We will use the incomplete training data and features of the test data together to give a prediction. Difference between the ground truth and the predicted distribution matrix for test data will be measured. We will repeat each experiments 10 times and report the results averaged over 10 trials.

In IncomLDL-prox, the regularization parameter is selected from 2{-10,-9,...,9,10} by cross-validation on training data. Parameters γ and ϵ are set to be 2 and 10-5 respectively. The maximum iteration is set to be 100. In IncomLDL-admm, regularization parameter λ and number of maximum iteration are selected in the same way as IncomLDL-prox. ρ1 is simply set as 1 and all the variables are initialized to be all-zero. The stopping criterion parameters ϵabs and ϵrel are set as 10-4 and 10-2 as suggested in the survey [Boyd et al., 2011].

We will compare our proposed IncomLDL algorithm with several baselines. They are all adapted from existing label distribution algorithms to fit for the incomplete situation. Note that although these algorithms can solve the incomplete label distribution problem, they consider each label separately thus are expected to work worse than our proposal. These algorithms include two maximum entropy algorithms IIS-LDL [Geng et al., 2013], BFGS-LDL [Geng, 2016] and two problem transformation algorithms PT-Bayes and PT-SVM [Geng, 2016]. All the codes are shared by original authors, and we use the default parameter suggested there, except that we tune the regularization parameter for the PTSVM algorithm using 10-folder cross-validation in the same way as in IncomLDL-prox.

Following [Geng, 2016], we will use five measurements for incomplete label distribution problem. Among them, Chebyshev, Clark and Canberra measure the distance between two vectors, thus they are the lower the better. Cosine and Intersection measure the similarity between two vectors, thus they are the higher the better. Details of these measurements can be found in [Geng, 2016]. Note that there is one additional measurement proposed in [Geng, 2016], which measures the KL-divergence between two vectors. For KL-divergence is calculated by log(dyx / ˆ dyx ), and it will be meaningless when ˆ dyx is zero, we will not use it here.

Results Due to space limitation, here we only present representative results. Other results are similar and we will put them in a longer version. Note that we have done experiments on 4 different ω% within both incomplete and transductive setting, measured on 5 measurements. Here we will present the Chebyshev (the lower the better) results for incomplete setting on all the data with ω = 10 in Table 2 and the Intersection (the higher the better) results for transductive setting on test data only with ω = 30 in Table 3.

We can see in both these two scenarios, our proposed two algorithms are superior to the baselines. The results are as expected since these two methods exploit the label correlation when there are insufficient training data facing the incomplete annotation. However, although we cannot give a guarantee that IncomLDL-prox does optimize our objective Eq. 1, IncomLDL-prox's performance is comparable with that of IncomLDL-admm, even though IncomLDL-admm get the best results most of the time. We plan to study this phenomenon in our future work.

For those baseline methods, PT-SVM and IIS-LDL perform the best. BFGS-LDL, although reported to be better than IIS-LDL when data are complete [Geng, 2016], however, are not suitable for incomplete case, especially on Natural Scene and SJAFFE data sets. Comparing Table 2 and Table 3, we can see that for the incomplete setting, all algorithms except PT-Bayes are more stable. Thus it is much difficult to predict the total unlabeled test data in the transductive setting.

5 Conclusion

In this paper, we solve the problem of Incomplete Label Distribution Learning (IncomLDL) where the supervised information are incomplete. To solve the problem of data deficiency when facing incomplete data, we propose to use the trace normminimization technique, thus we can exploit label correlation, reducing the effect of lacking training data. Two algorithms are then proposed based on proximal gradient descend and alternative direction method of multipliers. Experiments on all 15 data sets show the merits of the proposed algorithms compared to baselines.