Label Embedding Based on Multi-Scale Locality Preservation

1 Introduction

Learning with label ambiguity, i.e., one instance sometimes can not be fully described by only one label, is a hot topic in recent machine learning research as more and more real applications encounter that. Compared to the traditional SingleLabel Learning (SLL), Multi-Label Learning (MLL) allows an instance to be assigned with multiple labels simultaneously so as to tackle the problem of label ambiguity to some extent [Zhang and Zhou, 2014]. However, MLL merely considers whether the label is positive (assigned with '1') or negative (assigned with '0'), but fails to point out the concrete relevant degree of the positive labels. Also, MLL can not deal with some applications where the overall distribution of the whole series of labels matters. Recently, a general learning paradigm named Label Distribution Learning (LDL) has been proposed to deal with such cases [Geng, 2016]. Unlike SLL

∗Corresponding author

and MLL, LDL shows more flexibility in tackling label ambiguity because it annotates each instance with a label distribution rather than a binary label vector. Fig. 1 shows an example of LDL in the filed of natural scene annotation. This natural scene image can be integrally described by all these listed labels with different relevant degrees. LDL shares some similarities with multi-output regression [Borchani et al., 2015] and multi-ordinal regression [Zeng et al., 2017] for they all annotate instances with numerical labels. To formulize LDL, let S = {xi, yi}Ni=1 be a dataset with N samples, where xi ∈ X = RM and the corresponding yi ∈ Y = RL. The description degree yc i ∈ [0, 1] represents howmuch the cth label is relevant to the instance xi. Meanwhile, all the description degrees of an instance sum up to 1, i.e. ∑Lc=1 yc i = 1, which means that each instance can be fully described by using the whole series of labels. Given XN∗M = [x1, ..., xN]t and YN∗L = [y1, ..., yN]t , the aim of LDL is to learn the function g : X → Y from the training dataset and use it to predict the label distributions for the unseen instances.

Many LDL algorithms have already been proposed. Observing that the faces at the close ages own quite similar look, Geng et al. [2010] propose IIS-LDL to estimate the facial age, which is the first proposal of the LDL algorithm. Due to the lack of label distribution in the original data, they generate the age distribution manually through the Gaussian distribution. The improved algorithm BFGS-LDL and the neural network based approach CPNN for LDL are also proposed later [Geng et al., 2013]. Then, Geng formulizes LDL as a general learning paradigm and puts forward four more algorithms [2016]: AA-BP, AA-KNN, PT-SVM and PT-Bayes. Some initial efforts are also made to realize LDL by deep learning and ensemble learning. For example, Gao et al. [2017] develop a DNN based model called Deep LDL. Shen et al. [2017] propose LDL Forests based on differentiable decision trees. In addition, some well designed algorithms, such as LDSVR [Geng and Hou, ], view LDL as a regression problem. Besides, LDL has also been applied to many real-world applications successfully. For example, Zhou et al. [2015] utilize the emotion distribution to recognize facial expressions. Ren and Geng [] use the distribution of ratings to portray the human sense toward facial beauty. LDL has also been studied in the field of natural scene annotation [Geng and Luo, 2014], crowd counting [Zhang et al., 2015], video parsing [Geng and Ling, 2017], etc.

Label Embedding (LE) has become a popular research topic in SLL and MLL. LE usually embeds the original labels into a new space and then conducts the learning from the features to the embedded labels. Finally, a specific label decoder recovers the predicted embeddings to the original label space. LE owns the advantage in addressing the problematical label space as well as capturing the high-order label correlations. The labels in LDL may encounter problems such as the redundancy and the noise. Also, the effective exploitation of the label correlations is considered to be crucial for the success for LDL. However, almost all existing LE approaches are proposed for SLL and MLL [Hsu et al., 2009; Tai and Lin, 2012; Chen and Lin, 2012; Lin et al., 2014; Bhatia et al., 2015; Yeh et al., 2017; Zhang and Schneider, 2012; Ferng and Lin, 2013], i.e., they focus on the embedding of binary labels whose values are whether positive or negative. The corresponding decoders also aim at recovering the binary labels from the encoded ones. These algorithms thus can not be applied to LDL directly for the special label domain of LDL. Moreover, many leading LE methods assume that the training label matrix is sparse or low-rank, for there are usually less positive labels than vast negative labels. However, such assumption is violated in LDL case. In order to realize LE in LDL, at least two main issues should be tackled properly: 1) How to exploit the information of label distributions efficiently. Compared to binary labels, the numerical labels usually contain more abundant information that is beneficial for subsequent prediction. 2) How to design a decoder that restricts the recovered label vector to satisfy the constraints of the label distribution.

This paper takes an initial attempt to combine LE with LDL and proposes a specially designed LE approach named MSLP. Inspired by the typical manifold learning method Laplacian Eigenmaps [Belkin and Niyogi, 2002], MSLP tries to conduct locality-preserving label embedding. That is, MSLP aims to search the embedded label vectors y′ ∈ Y′ = Rl that maintain the neighborhood relationship among label distributions of data points. After obtaining the embedded labels, most LE methods need to choose an extra model to learn the mapping from the features to the embedded labels. By assuming an explicit mapping y′ = xT V when conducting embedding, MSLP omits that additional learning process and becomes feature-aware. In order to maintain the label neighborhood structure better through xT V , MSLP restricts that the neighbors of one point found in the label space should be only determined within its neighbors in the feature space. The benefit of this restriction will be explained in Section 2. Combining the locality information of data points in both the spaces of label and feature with different locality granularity, MSLP achieves the Multi-Scale Locality Preserving label embedding for LDL. For real-world data, some data points may violate the smoothness assumption [Chapelle et al., 2006], which is caused by the noises that arise unavoidably during the collection and the preparation of data. MSLP is designed to be insensitive to the existing of such data points so as to alleviate this problem.

The rest of the paper is organized as follows. The proposed algorithm MSLP is derived and discussed in Section 2. Then, the experimental results are reported in Section 3. Finally, the conclusion is drawn in Section 4.

2 The ProposedMethod

Unlike SLL and MLL, labels in LDL are numerical, which enables MSLP to exploit the label structure hidden in the label space. Inspired by Laplacian Eigenmaps [Belkin and Niyogi, 2002], MSLP also aims to perform locality preserving embedding. Focusing on the label space, it tries to maintain the neighborhood structure of label distributions in the embedding space. Such embedded label vectors can be obtained through minimizing the following objective:

where W + y is an N ∗ N weight matrix incorporating neighborhood information, D+ is an N ∗N diagonal matrix whose entries D+ ii = ∑j W + y,ij , Y ′N∗l = [y′1 , ..., y′N ]t is the embedded label matrix, and I is a l ∗ l unit matrix. The goal of the constraint above is to remove an arbitrary scaling factor of the embedded labels while D+ provides an natural measurement on the data points [Belkin and Niyogi, 2002]. Here, we adopt the form of heat kernel as the weight matrix, i.e.,

where σ > 0 is a scalar parameter, and dis() is an optional function measuring the distance between probability distributions. Here, we first define the set Neiy for a specific data point pi = (xi, yi) in the training set S as follow:

The function ψy with variables above returns the k+ nearest neighbors of the point pi in the label space among the point set {pj | pj ̸= pi ∧ pj ∈ S}.

As mentioned above, most LE approaches need an additional learning process from the features to the embedded labels. Avoiding that, MSLP assumes y′ = V T x, where VD∗l is the regression matrix to be learned. By substituting y′ for V T x into Eq. (1) and introducing a regulation term to avoid overfitting, the objective becomes

where λ is a regulation parameter and ‖ . ‖F means Frobenious norm. For an unseen instance xu, we first compute its corresponding embedded label vector ̂ y′u = V T xu. Then, the knn-based decoder recovers the predicted label distribution ̂ yu by averaging the label distributions of k nearest neighbors of ̂ y′u among the embedded label matrix Y ′ .

Neiy andW + y are yet determined by the distance of label distributions between data points but ignore their distance in the feature space. Viewing regression matrix V as the projection directions for the feature, we can see from the objective (4) that the solution for V will tend to be dominated by the large feature distances of data pairs where W + y,ij ̸= 0. As an example showed in Fig. 2, this may lead to the overlap of points with dissimilar label distributions and the scatter of points with similar label distributions. The bad resulting embeddings will result in an overall low prediction accuracy, because the decoder of MSLP is knn-based in the embedded label space.

This problem happens either when some outliers are within some data points' Neiy set, or when data points are essentially distributed in different feature areas but share quite similar label distribution. To overcome it, we introduce another parameter α ≥ 1 and restrict that the k+ nearest neighbors of one data point in the label space should be found within its αk+ nearest neighbors in the feature space. That is, utilizing different locality granularity in the label space and the feature space, the locality information of data points in both spaces are integrated. The set Neiy is now redefined as follow:

The function ψx is similar to ψy except that it finds neighbors in the feature space. Now each point will focus on data points with similar label distribution in its neighboring feature space, as the circle for pi shows in Fig. 2. Therefore, the label embedding is achieved by the multi-scale locality preserving.

According to the smoothness assumption [Chapelle et al., 2006], the neighboring data points in the feature space are more likely to share the similar labels. But for real-world data, the noise is usually an unavoidable problem, affecting the collection and the preparation of data. To reduce negative influences caused by that, MSLP tries to keep each data point far away from its hetero-neighbors after embedding. Here, we define the hetero-neighbors of one data point pi as points which keep very close to it in the feature space, but keep far away from it in the label space. Specifically, the heteroneighbor set HNei of pi is defined as

where k- (0 ≤ k- ≤ αk+ -k+) controls the maximum possible number of hetero-neighbors we may find for pi. And ψy with -k- means finding k- farthest points from pi among the given set of points. Note that there may be no heteroneighbor around pi which is reflected by an empty intersection HNei(i). Fig. 3 illustrates the computation process of sets Neiy and HNei for pi. We denote W - to show the existing of hetero-neighbor pairs, i.e.,

Then, the final objective becomes:

Algorithm 1 MSLP

Input: Training dataset S = {X, Y }, testing instance xu, embedding dimensionality l, distance function dis(), parameters {k+, k-, α, β, λ} for the encoder and k for the knn-based decoder.

Output: Predicted label distribution ̂ yu.

• 1: Compute the sets Neiy and HNei for each point in S.
• 2: Compute correspondingW + andW -.
• 3: Obtain the optimal V via eigen-decomposition of (10).
• 4: Compute the embedded label vector ̂ y′u = V T xu.
• 6: Decode ̂ yu from ̂ y′u by averaging the label distributions of these k nearest points found above.
• 5: Find k nearest neighbors of ̂ y′u within XV .

where β ∈ [0, 1] balances the importance of the first two terms of Eq. (8).

The first term in (8) can be reduced to

Through similar computing, the second term in (8) becomes (1-β)tr[V T XT (D- -W -)XV ], where Dii = ∑j W - ij . Then, by simple algebraic operations, the final objective

becomes

where M + = D+ -W + and M - = D- -W -. Applying the Lagrangian method, the problem can be transfered into a general eigen-decomposition problem, i.e.

where M = βM + - (1 - β)M - and the closed-form solution of optimal V consists of the first l normalized eigenvectors corresponding to the top l smallest eigenvalues of above. The procedures of MSLP are summarized in Algorithm 1.

One thing deserves to be mentioned is the relationship between MSLP and Feature Embedding (FE) methods. FE mainly focuses on maintaining the characteristic of the feature space (unsupervised) or finding a new feature space easier for subsequent learning (supervised). Instead, MSLP concentrates on the label space essentially, although utilizes V T x to approximate y′ via an explicit linear assumption. On the other hand, MSLP and many FE methods all compute a transformation matrix for the feature to map data points into a subspace. Under this perspective, MSLP can be viewed to transfer the information of label neighborhood structure to guide the process of feature embedding. In the following section, we will also do experiments to show the different performances of MSLP and some popular FE methods.

3 Experiment

To validate the effectiveness of MSLP, we visualize the embedding results of MSLP and also conduct extensive experiments on five real-world datasets among different fields.

3.1 Experiment Configuration

Real-world Datasets The LDL dataset Natural Scene (NS) [2014] is utilized. NS includes 2,000 natural scene images and each image is represented by 294 features and a 9dimensional label distribution. Fig. 1 has showed one image of NS. Two widely used facial expression datasets s-JAFFE and s-BU 3DFE are used here, for they have been extended to the standard LDL datasets by Zhou et al. [2015]. There are 213 facial images in s-JAFFE and 2500 in s-BU 3DFE. Each image is described by 6 basic emotions, as an example image showed in Fig. 4 (a). The 243 features are extracted for each image by the same method used in [Zhou et al., 2015]. In detail, images are manually cropped to make eyes at the same positions and resized to 110*140 pixels. Then, the features are extracted by LBP. We also collect two facial beauty datasets SCUT-FBP and Multi-Modality Beauty (M2B) with the information of label distributions [Ren and Geng, ]. The beauty distribution of each image consists of five rates '1'- '5'. And a higher rate indicates a more intensive sense about beauty. Fig. 4 (b) displays a typical image of that. Following the same way as Ren and Geng [] did, we extract 300 features for 1500 images in SCUT-FBP by LBP, HOG and Gabor filter, and 250 features for 1240 images in M2B by LBP, Gabor filter and Color moment.

Comparing Algorithms We compare MSLP with eight popular LDL methods: IIS-LDL, CPNN, BFGS-LDL, LDSVR, AA-BP, AA-KNN, PT-SVM and PT-Bayes. For MSLP, the squared Euclidean distance is chosen as dis(), and the σ is set to the average of squared Euclidean distances among all pairs whose W + y,ij ̸= 0. k+, α is chosen from {5, 10} and k- = k+ simply, β is selected from {0, 0.1, 0.5}, λ is chosen from {0, 0.01, 0.1}, and k for decoding is chosen from {5, 10, 15}. The number of hidden-layer neurons for CPNN and AA-BP is set to 50, and k for AA-KNN is selected from {5, 10, 15}. BFGS-LDL and IIS-LDL follow the advised settings in [Geng, 2016]. The rbf kernel is used for LDSVR and PT-SVM with its width set to the average Euclidean distance among training instances. Also, aiming to show the superiority of MSLP versus FE, four typical FE methods CCA [Hardoon et al., 2003], LPP [He and Niyogi, 2004], NPE [He et al., 2005] and PCA [Jolliffe, 1986] are compared, and AA-KNN is used as their subsequent predictor. The number of neighbors for LPP and NPE is selected from {5, 10, 15} and the width of heat kernel for LPP is also set to the average squared Euclidean distances among its neighbor pairs. Moreover, the compared FE methods are allowed to be extended to their kernel version with the rbf kernel, which gives them full chances to beat MSLP. To be fair, the ratio u of the embedding dimensionality over the original feature dimensionality for MSLP and FE methods ranges over {10%, 20%, ..., 100%}, and the best one is adopted. For all datasets and algorithms, the 10-fold cross validation is conducted and the average performance is recorded.

Evaluation Metrics As Geng suggests [2016], we select four distance metrics (Chebyshev, Clark, Kullback-Leibler and Canberra) and two similarity metrics (Cosine and Intersection), which are widely-used in LDL, to evaluate the performance of different approaches.

3.2 Visualization

The proposed MSLP is motivated by the Laplacian Eigenmaps, and they share some similar spirits in some way. To visually show the embedding effect of MSLP and its difference from FE, we compare MSLP with LPP - the linear version of the Laplacian Eigenmaps. As being a popular manifold learning method, LPP aims to find the embedded features that optimally preserves the locality of data points in the original feature space. We generate a toy LDL dataset with 3 features and 3 labels in the similar way to [Geng, 2016]. The label distribution y = {y1 , y2 , y3 } of the corresponding x = {x1 , x2 , x3 } is created as follows:

We generate 3000 data points to form the dataset. The first two components of x are randomly sampled within [-1, 1] and the third one x3 = exp[-(x1 )2 - (x2 )2 ]. We transfer these points into a 2-dimensional embedding space with different methods and utilize RGB colors to show their label distributions. In addition, a noisy toy dataset is also formed by adding the Gaussian noise with a zero mean and a variance of 0.1 to the features. The results are displayed in Fig 5 ∼ 6. As these figures show, MSLP maintains the structure of label neighborhood well within the local feature space, while LPP ignores the label locality and results in a mess in color areas.

Using s-JAFFE as an example, we also conduct the visualization for real-world datasets. We use black color to describe facial images with neutral expression (i.e., the emotion distribution is close to the uniform distribution) as these images have been labeled by Lyons et al. [1998]. Besides, other six different colors are used to display images according to the highest description degree of six different basic emotions. Fig. 7 shows the results. Again, MSLP gathers points sharing similar emotion distributions and forms some evident color areas. In contrast, LPP leads to the chaos of colors. Moreover, the distribution of emotion areas in Fig. 7 (b) is also consistent to the human intuition. For example, the points of 'Neutrality' are closer to the points of 'Sadness' than 'Happiness', for it is usually much easier for a neutral face to be judged as expressing negative other than positive emotions in the real world. Also, points of 'Anger' and 'Disgust' are near, as well as the points of 'Surprise' and 'Fear', for these emotions usually appear simultaneously.

3.3 Experimental Results

The quantitative experimental results are presented in Table 1 ∼ 3. For each evaluation metric, ↓' indicates "the smaller the better", while '↑' indicates "the larger the better". The pairwise t-tests at 90% significance level is conducted and the best performance of each column is highlighted in boldface. Across all metrics, MSLP ranks 1st in 93.3% cases, which reveals the superiority of MSLP against many state-of-theart well-established LDL algorithms. Note that FE methods compared here are even allowed to be extended to their kernel version, ensuring to make the embedding nonlinear. But even so, MSLP still achieves better performance, which proves the effectiveness of exploiting multi-scale locality. It can be seen that no approach can hold the 1st place over all six metrics in the field of facial beauty sense. Unlike the task of expression recognition and scene annotation, the sense about beauty is a quite personal feeling and shows much ambiguities, thus it is a harder task for a method to perform well in all metrics.

Also, across all five datasets, MSLP reaches the best performance with the embedding ratio u = 10% consistently, while the best ratios of compared FE methods vary from 10% to 90% in different datasets. Observing the datasets collected here, the possible reason of such phenomenon is that MSLP essentially performs embedding for the label, which owns much lower dimensionality compared to that of the feature. Thus, MSLP usually needs less embedding dimensions than FE methods to maintain the beneficial information or property of the original label space in the embedding space.

4 Conclusion

This paper proposes a novel LE approach named MSLP for LDL. Unlike most previous works, MSLP deals with the numerical labels and integrates the neighborhood structure of points in both the spaces of label and feature. MSLP is also insensitive to the presence of hetero-neighbors. Experimental results reveal the effectiveness of MSLP in gathering points with similar label distributions in the embedding space, i.e., the label locality is well preserved through MSLP. Although proposed for LDL, it is also interesting to note that MSLP can be directly shifted to some other learning paradigms (e.g., multi-output regression) which own numerical labels. In the future, we will explore if there exist better ways to utilize the structure information described by the label distributions.

Acknowledgments

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