Label Distribution Learning with Label Correlations via Low-Rank Approximation

1 Introduction

Most machine learning algorithms can be viewed as building a mapping from the sample space to the label space. There are two main traditional integrated paradigms for establishing a mapping: single-label learning (SLL) and multi-label learning (MLL) [Tsoumakas et al., 2007]. The former assumes that each instance is associated with a single label, while the latter considers that each instance may have a variety of semantic meanings and be related to a set of labels simultaneously. However, both SLL and MLL can only solve the issue of "what describes the instance"; and cannot determine the relative importance of each label to a particular instance. Sometimes, we are more concerned about the intensity of each label, to determine "how to describe the instance". To solve this problem, a novel learning paradigm named label distribution learning (LDL) was proposed [Geng et al., 2010]. Different from MLL to output a set of labels, LDL learns a label distribution. Each component in the distribution represents the relevance of the corresponding label to the instance.

∗Corresponding Author: Xiuyi Jia ( jiaxy@njust.edu.cn ).

Since the label distribution can be viewed as a type of label relations, the correlation among labels should not be ignored in the learning process. For example, in image annotations, assuming that sky and cloud are strongly related, an image is more likely to be correlated with cloud, when it is strongly correlated with sky. In view of this, some researchers have considered label correlations in LDL. Zhou et al. [2015] captured the label correlation by using Pearson's correlation coefficient for facial emotion recognition. Based on the Plutchik's theory, Zhou et al. [2016] explored the label correlation for text emotion distribution learning. Moreover, the label correlation was encoded into a distance to measure the similarity of any two labels [Jia et al., 2018]. For incomplete LDL problem, a low-rank structure was employed to capture the label correlations [Xu and Zhou, 2017]. However, all above works exploited the label correlations in a global way. In reality, label correlations are usually appeared in a local way. For example, in text annotations, the relevance between Puma and animal appears in journals of ecology and environment with a high probability, while Puma is usually related to brand in fashion magazines.

To solve above problems, we try to learn the global and the local label correlations simultaneously. Furthermore, the global correlation is captured through a low-rank approximation and the local correlation is concerned by clustering, in which the samples with similar discrimination will be clustered into one group. Then, we can predict the label distributions for unknown instances based on the high-order label correlations encoded in one correlation matrix.

Our work was inspired by ML-LRC [Xu et al., 2014]. There are two major differences between our method and ML-LRC: (1) ML-LRC only considers the global label correlation. However, as we mentioned, some correlations are only shared by a part of instances. In view of this, in addition to introducing a correlation matrix to utilize the global label correlation, we also try to learn the local label correlations simultaneously. (2) ML-LRC is mainly concerned about the traditional multi-label learning to learn a set of related labels for each instance. Our work tries to propose a novel algorithm in label distribution learning, which places more emphasis on how relevant each label is to a particular instance, rather than focusing on what label is relevant to a specific instance only.

The main contribution of this paper is three folds:

• We propose a novel method to deal with LDL problems by considering global correlations and local correlations simultaneously.
• One correlation matrix is introduced to encode the highorder correlation, in which the global correlation is utilized by low-rank approximation while the local label correlation is exploited by clustering.
• We assume that if the distance between two label distributions is small enough, they should be strongly related to each other.

2 RelatedWorks

The LDL framework can be viewed as the generalization of MLL. It might provide more information than traditional paradigms on model learning. In recent years, LDL has been successfully applied in many applications. This novel learning paradigm was usually exploited to estimate facial age [Gao et al., 2018; Geng et al., 2010; He et al., 2017]. A multivariate label distribution algorithm was used to estimate the head pose [Geng and Xia, 2014]. Considering that crowd images with adjacent class labels contain similar features, the crowd counting problem can be transformed into an LDL problem [Zhang et al., 2015]. Furthermore, the LDL paradigm was applied to identify multiple emotions and their intensities from texts [Zhou et al., 2016]. A deep label distribution learning algorithm by combining LDL with deep learning was proposed to handle the problem of apparent age estimation [Gao et al., 2017].

Existing LDL algorithms can be divided into three categories: problem transformation, algorithm adaptation and specialized algorithms. Problem transformation based algorithms transform the LDL problem into traditional problems and then use existing learners to solve it, such as PTSVM and PT-Bayes [Geng, 2016]. The main idea of algorithm adjustment is to adapt traditional algorithms to fit for LDL paradigm, such as AA-BP [Geng, 2016] and logistic boosting regression method [Xing et al., 2016]. In addition, there are some specialized algorithms designed for LDL can directly model the relative importance of each label to the particular instance [Geng et al., 2014; Geng et al., 2013; Zhao and Zhou, 2018].

To construct a specialized LDL algorithm, we need to consider three parts: the objective function, the output model and the optimization method. Difference between the groundtruth distribution and the predicted distribution can be measured by some distances which can be viewed as objective functions, such as Kullback-Leibler Divergence [Geng et al., 2014; Huo et al., 2016; Jia et al., 2018] and Jeffery divergence [Zhou et al., 2015]. The LDL algorithms mainly use the maximum entropy model as the output model [Geng, 2016; Zheng et al., 2018]. To solve the optimization problem, many methods have been applied to LDL. For example, the improved iterative scaling method can be used as the optimization method [Geng et al., 2010], so does the limited-memory quasi-Newton method (L-BFGS) [Zhou et al., 2016].

3 The LDL-LCLRAlgorithm

3.1 Framework

The main goal of LDL is to learn a mapping from the input space X = [x1; x2; · · · ; xn] ∈ Rn×d to the label distribution over a finite set of labels Y = {y1, y2, · · · , yl}, where n is the number of instances and l is the number of labels. Given a training set T = {(x1,D1), (x2,D2), · · · , (xn,Dn)}, where Di = [dy1 xi , dy2 xi , · · · , dyl xi ] is the label distribution associated with xi, we use the description degrees dyx , which satisfies dyx ∈ [0, 1] and ∑y dyx = 1, to indicate the importance of label y to instance x, where x ∈ X and y ∈ Y . It is noticed that dyx is not the probability that y correctly labels x, but the proportion that y accounts for in a full description of x. The LDL approach can learn a conditional probability mass function p(y|x) from T and use the learned model to predict the label distributions for unseen instances.

Without loss of generality, we choose the maximum entropy model as the output model. Then the component of the predicted label distribution ˆ dyj xi , which is the description degree of the j-th label y to the i-th instance x, can be expressed as follows:ˆ

where w is the model parameter that needs to be learned and Zi = ∑j exp(∑r wjrxir) is a normalization term to satisfy that the sum of all description degrees of an instance equals 1. The performance of Kullback-Leibler (KL) divergence is the most stable in the field of LDL according to comparison experiments [Zhao and Geng, 2017]. Therefore, we adopt the KL divergence as the basic objective function:

where DKL(Di|| ˆDi) = Di ln Di ˆDi is the KL divergence to measure the distance between the predicted label distribution ˆDi = { ˆ dy1 xi , ˆ dy2 xi , · · · , ˆ dyl xi } and the ground-truth label distribution Di. The second term aims to prevent the model from over-fitting. λ1 is the balance factor.

Inspired by the work in [Xu et al., 2014], we adopt a correlation matrix S to model the dependencies among different labels. A simple example is shown in Figure 1, we can obtain that the relative importance of "cloud" is changed from 0.15 to 0.535 (It needs to be normalized) for the high correlation between "cloud" and "sky" shown in matrix S, i.e., the reconstructed distribution matrix ˆDS can provide more information and assign a new relevance of a label to a particular instance based on the global label correlations. To exploit the dependence among labels, Eq. (2) can be rewritten as Eq. (3):

where λ2 and λ3 are balance factors. The regularization term on E controls the difference between the reconstructed distribution ˆDS and the ground-truth distribution D. Since labels are related to each other globally, one can be represented by a linear combination of other labels, which implies a low-rank structure of S. Considering that the low-rank function is difficult to optimize, we use the nuclear norm ‖ · ‖∗ as a convex approximation of the low-rank function.

Nevertheless, some label correlations are only shared by partial samples. Thus, we try to consider the local relevance among labels simultaneously. The k-means method is introduced to cluster samples into different groups. In one group, we assume that if the distance between two label distributions is small enough, they should be strongly related to each other. Then, the framework of LDL that exploits both the global and local correlation among labels can be formulated as:

where λ4 is the balance factor and k is the number of clusters. Sm,n is the correlation between the m-th label D·m and the n-th label D·n. It is worth mentioning that for Sm,n, we want to find a larger correlation value for two correlated labels with a smaller distance, thus the last term in the objective function is a maximization problem.

3.2 Optimization

Since the optimization problem in Eq. (4) is convex, it can be optimized globally. In this section, we exploit the ADMM (Alternating Direction Method of Multipliers) [Boyd et al., 2011], which can convert the multi-parameter problem into multiple single-parameter problems, to obtain the model parameter W .

Here, we introduce an auxiliary variable Z to make the objective function separable for the two non-smooth regularization terms in Eq. (4):

Then, the Lagrange multiplier method is used to transform the constrained problem into an unconstrained problem:

where Γ1 and Γ2 are the Lagrange multipliers, ρ is the penalty parameter and 〈·, ·〉 is the Frobenius dot-product.

Eq. (6) can be solved by ADMM. Each iteration of ADMM involves updating one variable, with the other variables fixed to their most recent values. The following gives the updating rules of each parameter during one round of iteration.

To solve for W, Eq. (6) can be reduced to the following alternative methods,

In the same way, S can be solved by optimizing the following sub-problem,

Both Eq. (7) and Eq. (8) can be solved by the limited-memory quasi-Newton method effectively [Yuan, 1991]. The basic idea is to avoid explicit calculation of the inverse Hessian matrix, which is required in the Newton method. For the optimization of Eq. (7) and Eq. (8), the computation of L-BFGS is mainly related to the first-order gradient, which can be obtained by

Similarly, E and Z can be obtained by solving the problems as follows:

Both Eq. (11) and Eq. (12) have a closed solution [Liu et al., 2010; Cai et al., 2010]. The multipliers Γ1 and Γ2 can be updated directly by

The overall procedure of Label Distribution Learning with Label Correlations via Low-Rank approximation (LDLLCLR) is summarized in Algorithm 1.

4 Experiments

In this part, we will evaluate the proposed method on 15 realworld data sets with seven state-of-the-art LDL approaches over six different measurements. These 15 data sets [Geng, 2016] cover the fields of natural scene recognition, biological information classification and emotional analysis, among others. Six different measures [Geng, 2016] are used to evaluate the performances of the LDL algorithms, i.e., Sφrensen, Squared-chord, Kullback-Leibler, Chebyshev, Intersection and Cosine.

4.1 Experimental Setting

The proposed LDL-LCLR algorithm is compared with seven LDL algorithms: PT-SVM, AA-kNN, BFGS-LLD [Geng, 2016], IIS-LLD [Geng et al., 2010], CPNN [Geng et al., 2013], LDLLC [Jia et al., 2018] and LDL-SCL [Zheng et al., 2018]. These seven algorithms can be divided into three groups. The first group is the Problem Transformation (PT, e.g., PT-SVM), methods in this group transform the LDL problem into traditional problem and then use existing learners to solve it. The second group is the Algorithm Adjustment (AA, e.g., AA-kNN), the main idea of AA is to adapt traditional algorithms to fit for LDL paradigm. The others are specialized algorithms designed for LDL, which can directly model the relative importance of each label to the particular instance. IIS-LLD aims to minimize the Kullback-Leibler divergence between the ground truth and the predicting distribution by using improved iterative scaling method (IIS). Since IIS often performs worse than several other optimization algorithms [Malouf, 2002], an improved method BFGSLLD is proposed to optimize the target function through the quasi-Newton method BFGS. The main assumption made in both IIS-LLD and BFGS-LLD is that the relationship between the feature space and the label distribution space is consistent with the maximum entropy model. CPNN removes this assumption by using a three layer neural network to approximate the relationship. LDLLC and LDLSCL are two LDL algorithms considering the label correlation. LDLLC exploits the Pearson's correlation to capture global label relevance while LDL-SCL utilizes the local label correlation to obtain more potential supervised information. All the codes are shared by original authors, and we use the suggested parameters reported in corresponding literature, except that we tune the regularization parameters from 10{-4,-3,-2,-1,0,1,2,3} for LDLLC and LDL-SCL using tenfold cross-validation. The number of cluster is set to 6 in LDL-SCL.

In LDL-LCLR, the parameters λ1, λ2, λ3, λ4 and k are set to 0.0001, 0.001, 0.001, 0.001 and 4, respectively. Besides, ρ is simply set as 1. We use k-means to cluster samples. The details of parameter selections are shown in the parameter analysis section. The maximum iteration is set to be 100. Besides, S and Z are initialized by the identity matrix. The initialization of other variables is all-zero.

4.2 Results and Discussion

Due to page limitation, we only provide detailed results of two measures, which are shown in Table 2 and Table 3. The best performance among the comparing algorithms on each measure is marked in bold. On each data set, ten times tenfold cross-validation is conducted and the mean value and standard deviation of each evaluation criterion is recorded.

To perform comparative analysis in more well-founded ways, Friedman test is further examined which is a favorable statistical test for comparisons of more than two algorithms over multiple data sets [Demˇsar, 2006]. Table 1 summarizes the Friedman statistics FF and the corresponding critical value on each measure. As shown in Table 1, for each evaluation criterion, the null hypothesis of indistinguishable performance at 0.05 significance level among the comparing algorithms is clearly rejected. Consequently, Bonferroni-Dunn test [Demˇsar, 2006] at 0.05 significance level is employed to test whether our proposed method LDL-LCLR achieves competitive performance against the comparing algorithms, where LDL-LCLR is considered as the control algorithm. The performance between two algorithms is significantly different if their average ranks over all data sets differ by at least one critical difference (CD). Figure 2 shows the CD diagrams on each evaluation criterion. In each sub-figure, any comparing algorithm whose average rank is within one CD to that of LDL-LCLR is connected. Otherwise, any algorithm not connected with LDL-LCLR is considered to have significantly different performance between them.

Based on these experimental results, the following observations can be made: (1) As shown in Table 2 and Table 3, it can be observed that the proposed method LDL-LCLR is superior to the baselines in general. (2) The correlationdriven methods LDLLC, LDL-SCL and LDL-LCLR generally outperform other algorithms. And the performance of LDL-LCLR is better than LDLLC and LDL-SCL on all data sets except for s-JAFFE. The results are as expected since the proposal simultaneously exploits the global and the local label correlations. (3) The specialized LDL algorithms generally outperform the algorithms that are obtained by problem transformation and algorithm adaptation.

In summary, the proposed LDL-LCLR algorithm achieves a competitive performance against other well-established label distribution algorithms. The results demonstrate the effectiveness of LDL-LCLR.

4.3 Sensitivity Analysis of Parameters

Next, we investigate the sensitivity of the proposed LDLLCLR method to the parameter setting, including λ1, λ2, λ3, λ4 in (6) and the number of clusters k. Figure 3 shows the influence of λ1 and λ2 with measures K-L and intersection on data set Yeast-alpha. We can observe that the performance is relatively stable if the parameters λ1 and λ2 respectively falls in a certain range (i.e., λ1 ∈ [0.00001, 0.001], λ2 ∈ [0.00001, 0.001]) and the performance deteriorates when they fall outside of the range. Besides, we can see that the influence of λ2 is smaller than the influence of λ1.

Considering that parameters λ3 and λ4 determine the global correlation and local correlation in (6), we design a set of experiments to investigate how these two parameters jointly affect the prediction performance of LDL-LCLR. As shown in Figure 4, we can notice that the proposed method is very sensitive to the variations of the parameters λ3 and λ4. When λ3 ∈ [0.001, 0.1], in general, the performance rises gradually with the increase of λ4, which demonstrates the importance of local correlations among labels in LDL learning process. Moreover, when λ3 is set to 10-5 , the performance of our method deteriorates firstly and then becomes better as λ4 increases.

In addition, we run LDL-LCLR with k varying from 1 to 9 with step size of 1. We present the experimental results on data set Yeast-alpha with 4 evaluation measures in Figure 5. Notice that, for criteria Sφrensen and K-L, the smaller the value, the better the performance; but for criteria Intersection and Cosine, the larger the value, the better the performance. First, we can observe that the performance rises rapidly when k is less than 4. After that, the performance of the algorithm fluctuates in a certain range (i.e, Sφrensen ∈ [0.0365, 0.0370], Intersection ∈ [0.9630, 0.9635]). Therefore, we set k = 4 in LDL-LCLR.

5 Conclusion

Label distribution learning is a generalized and effective method to deal with label ambiguity problems. Many LDL algorithms have concerned the label correlations to improve the performances. However, most of them apply the label correlations either in a global or a local way. In this paper, different from previous works, we propose a novel LDL algorithm that simultaneously exploits the global and the local label correlations. In the proposed LDL-LCLR method, the global correlations are captured through a low-rank approximation and the local correlations are utilized by clustering samples. The experimental results on several data sets show that LDL-LCLR outperforms many state-of-the-art LDL algorithms.

Acknowledgements

This work is jointly supported by the National Key R&D Program of China (No. 2018YFB1003902), Natural Science Foundation of Jiangsu Province (No. BK20170809), the National Natural Science Foundation of China (Nos. 61773208, 61876001, 71671086), and Jiangsu Key Laboratory of Big Data Security and Intelligent Processing (NJUPT).