Classification with Label Distribution Learning

1 Introduction

Learning with ambiguity, especially label ambiguity [Gao et al., 2017], has become one of the hot topics among the machine learning communities. Traditional supervised learning paradigms include single-label learning (SLL) and multilabel learning (MLL) [Zhang and Zhou, 2014], which label each instance with one or multiple labels. MLL assumes that each instance is associated with multiple labels, which compared with SLL takes the label ambiguity into consideration somewhat. Essentially, both SLL and MLL consider the relation between instance and label to be binary, i.e., whether or not the label is relevant with the instance. However, there are a variety of real-world tasks that instances are involved with labels with different importance degree, e.g., image annotation [Zhou and Zhang, 2006], emotion recognition [Zhou et al., 2015], age estimation [Geng et al., 2013]. Consequently, a soft label instead of a hard one seems to be a reasonable solution. Inspired by this, recently a novel learning paradigm, called Label Distribution Learning (LDL) [Geng, 2016], is proposed. LDL tackles label ambiguity with the definition of label description degree. Formally speaking, given an instance x, LDL assigns each y ∈ Y a real value dyx (label description degree), which indicates the importance of y to x. To make the definition proper, [Geng, 2016] suggests that dyx ∈ [0, 1] and ∑y∈Y dyx = 1, and the real value function d is called the label distribution function. Since LDL extends the supervision from binary to label distribution, which is more applicable for real-world scenarios.

∗Corresponding author.

Due to the utility of dealing with ambiguity explicitly, LDL has been extensively applied in varieties of real-world problems. According to the source of label distribution, applications can be mainly classified into three classes. The first one includes emotion recognition [Zhou et al., 2015], pre-release rating prediction on movies [Geng and Hou, 2015], et. al, where the label distribution is from the data. Applications of the second class include head pose estimation [Huo and Geng, 2017], crowd counting [Zhang et al., 2015], et. al, label distribution of which are generated by pre-knowledge. Representative applications of the third one include beauty sensing [Ren and Geng, 2017], label enhancement [Xu et al., 2018], where the label distribution is learned from the data. Notice that the aforementioned applications of LDL fall into the scope of classification, and we find that a learned LDL model is generally treated as a classification model, with the label corresponding to the highest model output as the prediction, which unfortunately draws an inconsistency between the aim of the training phrase and the goal of test phrase of LDL. In the training phrase, the aim of LDL is to minimize the distance between the model output and the ground-truth label distribution, while in the test phrase, the object is to minimize the 0/1 error.

We tackle the inconsistency in this paper. In order to alleviate the inconsistency, we come up with three improvements, i.e., absolute loss, re-weighting with entropy information, and large margin. The proposal of applying absolute loss and introducing large margin are inspired by theory arguments, and re-weighting samples with information entropy is based on observing the gap between the metric of LDL and that of the corresponding classification model. Since improvements are mainly originated from well-established theory tools, we are able to provide theoretical analysis of the proposed method. Consequently, the proposed algorithm LDL4C is well-designed and theoretically sound.

The main contributions of this paper are summarized as followings,

1. We propose three key components for improving classification performance for LDL, i.e, absolute loss, reweighting samples with information entropy, and large margin.
2. We establish upper bounds for 0/1 error and error probability of the proposed algorithms. Theoretical and empirical studies show that LDL4C enjoys generalization and discrimination.

The rest of the paper is organized as follows. Firstly, related works are briefly reviewed. Secondly details of the proposed method are presented. Then we give the theoretical analysis of the proposed method. Next experimental results are reported. Finally, we conclude the paper.

2 RelatedWork

Existing studies on LDL are primarily concentrated on designing new algorithms for LDL, and many algorithms have already been designed for LDL. [Geng, 2016] suggests three strategies for designing LDL algorithms. The first one is Problem Transformation (PT), which generates SL dataset according to the label distribution and then learns the transformed dataset with SL algorithms. Algorithms of the first strategy include PT-SVM and PT-Bayes, which apply SVM and Bayes classifier respectively. The second one is Algorithm Adaptation (AA), algorithms of which adapt existing learning algorithms to deal with label distribution straightly. Two representative algorithms are AA-kNN and AA-BP. For AA-kNN, mean of label distribution of k nearest neighbors is calculated as the predicted label distribution, and for AA-BP, one-hidden-layer neural network with multi-output is adapted to minimize the sum-squared loss of output of the network compared with the ground-truth label distribution. The last one is Specialized Algorithm (SA). This category of algorithms take characteristics of LDL into consideration. Two representative approaches of SA are IIS-LDL and BFGSLDL, which apply the maximum entropy model to learn the label distribution. Besides, [Geng and Hou, 2015] treats LDL as a regression problem, and proposes LDL-SVR, which embraces SVR to deal with the label distribution. Furthermore, [Shen et al., 2017] proposes LDLF, which extends random forest to learn label distribution. In addition, [Gao et al., 2017] provides the first deep LDL model DLDL. Notice that compared with the classic LDL algorithms, LDLF and DLDL support end-to-end training, which are suitable for computer vision tasks. Notice that none of aforementioned algorithms ever consider the inconsistency as we previously discussed.

There are few work on inconsistency between the training and the test phrase of LDL. [Gao et al., 2018] firstly recognizes the inconsistency in the application of age estimation, and designs a lightweight network to jointly learn the age distribution and the ground-truth age to bridge the gap. However the method is only suitable for real-valued label space and no theory guarantee is provided. Besides, one recent work [Wang and Geng, 2019] provides a theoretical analysis of the relation between the risk of LDL (absolute loss) and error probability of the corresponding classification function, discovering that LDL with absolute loss dominates classification. However, the major motivation of the paper is to understanding LDL theoretically, and no algorithm design to improve classification precision is provided.

3 The ProposedMethod

3.1 Preliminary

Let X be the input space, and Y = {y1, y2, . . . , ym} be the label space. Denote the instance by x. The label distribution function d ∈ RX×Y is defined as d : X × Y ↦→ R, satisfying the constraints dyx > 0 and ∑y∈Y dyx = 1, where dyx = d(x, y) for convenience of notations. Given a training set S = {(x1, [dy1 x1 , . . . , dym x1 ]), . . . , (xn, [dy1 xn , . . . , dym xn ])}, the goal of LDL is to learn the unknown function d, and the object of LDL4C is to make a prediction.

3.2 Classification via LDL

In real-world applications we generally regard a learned LDL model as a classification mode. Formally speaking, denote the learned LDL function by h and the corresponding classification function by ˆh, for a given instance x, then we have

i.e, the prediction is the label with the highest output. Intuitively if h is near the ground-truth label distribution function d, then the corresponding classification function ˆh is close to the Bayes classification (we assume d is the conditional probability distribution function), thereby LDL is definitely related with classification. The mathematical tool which quantifies the relation between LDL and classification is the plugin decision theorem [Devroye et al., 1996]. Let h∗ be the Bayes classification function, i.e.,

then we have

Theorem 1. [Devroye et al., 1996; Wang and Geng, 2019] The error probability difference between ˆh and h∗ satisfies

The theorem says that if h is close to d in terms of absolute loss, then error probability of ˆh is close to that of h∗ . Theoretically LDL with absolute loss is directly relevant with classification. Also absolute loss is tighter than KL-divergence, since |p - q| ≤ 2√KL(p, q), for p, q ∈ Rm [Cover and Thomas, 2012]. Accordingly we propose to use absolute loss in LDL for classification, instead of KL-divergence. Similar with [Geng, 2016], we use maximum entropy model to learn the label distribution. Maximum entropy mode is defined as

where Z = ∑j exp(wj ·x) is the normalization factor. Absolute loss is applied as the measure for LDL, and consequently the problem can be formulated as

whereW= [w1,w2, . . . ,wm] is the set of parameters.

3.3 Re-weighting with Information Entropy

After taking a second look at the Theorem (1), we will find out that model (2) actually optimizes the upper bound for error probability. This really brings a gap between absolute loss for LDL and 0/1 loss for classification. Fig. 1 is an illustrative example to demonstrate the gap, where ℓ1 denotes absolute loss and ℓep denotes error probability defined as Eq. (15). As we can see from the figure, (b) is superior to (a) from the perspective of absolute loss. However (b) is inferior to (a) in terms of error probability. For (a), y3 has the highest label distribution both for d and h, thus prediction of ˆh coincides with that of the Bayes classification function h∗ . For (b), y3 has the highest label distribution for d and y2 has the highest label distribution for h, thus the corresponding classification result is different with that of the Bayes classification. Essentially for label distribution which is multimodal (like (b) of Fig.1), the corresponding classification function is much more sensitive to the loss of LDL. While, for label distribution which is unimodal (like (a) of Fig.1), there is more room to manoeuvre. Information entropy seems to be a reasonable tool to quantize this sensitiveness, since a multimodal distribution generally brings higher information entropy compared with a unimodal one. Precisely, for the label distribution with higher information entropy (i.e., multimodal), the corresponding classification model is much more sensitive to the LDL loss, and vice verse. In other words, samples with high information entropy deserves more attention, which reminds us to re-weight samples with information entropy. Reweighted with information entropy will penalize large loss for samples with high information entropy, and leave more room for samples with low information entropy. Recall the definition of entropy information , for x,

Accordingly the problems is then formulated as

3.4 LDL with Large Margin

To further boost the classification precision, we borrow the margin theory. Formally speaking, let the model output corresponding to the Bayes prediction has a large margin over other labels, which pushes the corresponding classification model consistent with the Bayes classification model. Let y∗ i be the Bayes prediction for xi, i.e., y∗ i = h∗ (xi). Then we assume a margin ρ between hy∗ i xi and maxy∈{Y-y∗ i } hyxi , and the problem can be formulated as

where C1, C2 are the balance coefficients for margin loss and regularization respectively. Large margin turns out to be a reasonable assumption since the ultimate goal of LDL4C is to pursuit the Bayes classifier. Overall, model (4) seeks a balance between LDL and large margin classifier.

3.5 Optimization

To start, for x, define

and ρ-margin loss as ℓρ (α) = max{0, 1- αρ }. By introducing margin loss, model (4) can be re-formed as

which can be optimized efficiently by gradient-based method (ℓρ is differential). We optimize the target function by BFGS [Nocedal and Wright, 2006]. Define φ as the step function,

and denote the target function by T , gradient of which is obtained through

Moreover, gradient of h is got through

4 Theoretical Results

In this section, we will demonstrate that, theoretically LDL4C seeks a trade-off between generalization and discrimination, where generalization is due to the LDL process, and discrimination is credited to the large margin classifier.

4.1 Generalization

Here by generalization we mean that the error probability of LDL4C converges to that of the Bayes classifier, by developing an upper bound for error probability of LDL4C. The basic steps are providing an upper bound for risk of LDL4C (with absolute loss) firstly, and then converting the risk bound into error probability bound by Theorem 1.

Notice that maximum entropy model, i.e., Eq. (1) can be regarded as function combination of softmax function and multi-output linear regression function. Formally, let SF be the softmax function, F be a family of functions for multioutput linear regression. Denote the family of functions for the maximum entropy model by H, then H = {x ↦→ SF ◦ f(x) : f ∈ F}. To bound the risk of LDL4C, it suffices to derive an upper bound on the Rademacher complexity [Bartlett and Mendelson, 2003] of the model.

Theorem 2. Define F as F = {x ↦→ [w1 · x, . . . , wm · x]T : ||wj || ≤ 1}. Rademacher complexity of ℓ1 ◦ H satisfies

Proof. Firstly, according to [Wang and Geng, 2019], ℓ1◦SF is shown to be 2m-Lipschitz. And according to [Maurer, 2016], with ℓ1 ◦ SF being 2m-Lipschitz, then

where Fj = {x ↦→ wj · x : ||wj|| ≤ 1}. Moreover, according to [Kakade et al., 2009], Rademacher complexity of Fj satisfies

Finally substitute Eq. (9) into Eq. (8), and we finish the proof for Theorem (2).

Then data-dependent error probability for LDL4C is as following,

Theorem 3. Define ˆH = {x ↦→maxy∈Y hyx : h ∈ H}. Then for any δ > 0, with probability at least 1 - δ, for any ˆh ∈ ˆH, such that

Proof. Firstly, according to [Bartlett and Mendelson, 2003; Mohri et al., 2012], and ∑y |dyx - hyx | ≤ 2 (triangle inequality), data-dependent risk bound for LDL4C is as

Secondly combine Theorem (1) and Eq. (3), which completes the proof for the theorem.

4.2 Discrimination

In this part, we will borrow margin theory to demonstrate that LDL4C enjoys discrimination. By discrimination, we mean the ability to output the same prediction as the Bayes prediction. According to [Bartlett and Mendelson, 2003], with margin loss, we have

Theorem 4. Define ˜H as ˜H = {(x, y∗ ) ↦→ h(x, y∗ ) - maxy∈{Y-y∗ } h(x, y) : h ∈ H}. Fix ρ > 0. Then, for any δ > 0, with probability at least 1-δ, for all h ∈ H, such that

Since ℓρ satisfies 1/ρ-Lipschitzness, we have ˆRn(ℓρ ◦ ˜H) ≤ 1ρ ˆRn( ˜H). And according to [Mohri et al., 2012], ˆRn( ˜H) ≤ 2m ˆRn(Π1(H)), where Π1(H) is defined as

Since 1{h(x)̸=y∗ } < ℓρ (α), thus we have

And ˆRn(Π1(H)) can be bounded as

where γ = 2maxi∈[n] ||xi||, which leads to

Theorem 5. Fix ρ > 0. Then for any δ > 0, with probability at least 1 - δ, for all h ∈ H such that

5 Experiments

5.1 Experimental Configuration

Real-word datasets. The experiments are extensively conducted on seventeen datasets totally, among which fifteen are from [Geng, 2016], and M2B is from [Nguyen et al., 2012], and SCUT-FBP is from [Xie et al., 2015]. Note that M2B and SCUT-FBP are transformed to label distribution as [Ren and Geng, 2017]. Datasets are from a variety of fields, and statistics about the datasets are listed as Table 1.

Comparing algorithms. We compare LDL4C with six popular LDL algorithms, i.e., PT-Bayes, PT-SVM, AABP, AA-kNN, LDL-SVR [Geng and Hou, 2015], BFGSLDL, and two state-of-the-art LDL algorithms, i.e., StructRF [Chen et al., 2018] and LDL-SCL [Zheng et al., 2018]. For LDL4C, the balance parameter C1 and C2 are selected from {0.001, 0.01, 0.1, 1, 10, 100} and ρ is chosen from {0.001, 0.01, 0.1} by cross validation. Moreover for AABP, the number of hidden-layer neurons is set to 64, and for AA-kNN, the number of nearest neighbors k is selected from {3, 5, 7, 9, 11}. Furthermore, for BFGS-LDL, we follow the same settings with [Geng, 2016]. Besides, the insensitive parameter ϵ is set to 0.1 as suggested by [Geng and Hou, 2015], and rbf kernel is used for both PT-SVM and LDLSVR. For StructRF, depth is set to 20 and number of trees is set to 50, and sampling ratio is set to 0.8 as suggested by [Chen et al., 2018]. In addition, for LDL-SCL, λ1 = 0.001, λ2 = 0.001, λ3 = 0.001 and number of clusters m = 6 as given in [Zheng et al., 2018]. Finally, all algorithms are examined on 17 datasets with 10-fold cross validation, and average performance is reported.

Evaluation metrics. We test algorithms in terms of two measures, 0/1 loss and error probability. For 0/1 loss, we regard the label with the highest label distribution as the ground-truth label. Given an instance x with prediction y, the error probability is defined as

5.2 Experimental Results

Firstly, to validate the three key components (i.e., absolute loss, re-weighting with information entropy, and large margin) for boosting classification precision, we add each of the components into BFGS-LDL and compare 0/1 loss with BFGS-LDL. The performance is reported in Table 2. Due to the page limitation, we only report part of the results. Here "LDL" is short for BFGS-LDL. "LDL+ℓ1" represents BFGSLDL with absolute loss, and "LDL+RW" represents BFGSLDL with information entropy re-weighting, and "LDL+LM" stands for BFGS-LDL with large margin. As we can see from the table, armed with three key components, the corresponding LDL model can achieve better classification performance compared with the original BFGS-LDL model. Secondly we conduct extensive experiments of LDL4C and comparing methods on 17 real-world datasets in terms of 0/1 loss and error probability, and the experimental results are presented as in Table 3 and Table 4 respectively. The pairwise t-test at 0.05 significance level is conducted, with the best performance marked in bold face. From the tables, we can get that:

• In terms of 0/1 loss, LDL4C rank 1st among 13 datasets, and is significantly superior to other comparing methods in 70% cases, which validates the ability of LDL4C for performing classification.
• In terms of error probability, LDL4C ranks 1st among 12 datasets, and achieves significant better performance in 46% cases, which discloses that LDL4C has better generalization.

6 Conclusions

This paper tackles the inconsistency between the training and test phrase of LDL when applied in applications. In the training phrase of LDL, aim of which is to learn the given label distribution, i.e., minimizing (maximizing) distance (similarity) between the model output and the given label distribution. However, for applications of LDL, a learned LDL model is generally treated as a classification model, with the label corresponding to the highest output as the prediction. The proposed algorithm LDL4C alleviates the inconsistency with three key improvements. The first one is inspired by the plug-in decision Theorem 1, which states that absolute loss is directly related with classification error, thereby absolute loss is applied as the loss function for LDL4C. The second one stems from noticing the gap between absolute loss and the classification error, which suggests re-weighting samples with information entropy to pay more attention to multimodal distribution. The last one is due to margin theory, which introduces a margin between hy∗ x and maxy∈{Y-y∗ } hyx to enforce the corresponding classification model approaching the Bayes decision rule. Furthermore, we explore the effectiveness of LDL4C theoretically and empirically. Theoretically, LDL4C enjoy both generalization and discrimination, and empirically extensive comparing experiments clearly manifest the advantage of LDL4C in classification.

Acknowledgments

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

A Proof for Eq. (13)

Proof. Recall the definition of Rademacher complexity

where σ1, σ2, . . . , σn are n independent random variables with P(σi = -1) = P(σi = 1) = 1/2, and W = [w1, w2, . . . , wm] with ||wj || < 1, and the third inequality is according to the 1-Lipschitzness of function 1/x for x > 1. And for each j ̸= y,

where the first inequality is according to the ea -Lipschitzness of function ex for x < a, and the second one is according to [Kakade et al., 2009] by noticing that ||wj -wy|| < 2, which concludes the proof for Eq. (13).