Label Distribution Learning from Logical Label

1 Introduction

Multi-label learning (MLL) [Tsoumakas and Katakis, 2007; Zhang and Zhou, 2014] is a well-studied machine learning paradigm where each sample is associated with a set of labels. In MLL, each label is denoted as a logical value (0 or 1), indicating whether a label can describe a sample. However, the logical label cannot precisely describe the relative importance of each label to a sample. To this end, label distribution learning (LDL) [Geng, 2016] was proposed, in which real numbers are used to demonstrate the relative importance of a label to a certain sample. For example, Fig. 1(a) is a natural scene image, which is annotated with three positive labels ("Sky", "Mountain" and "Sea") and one negative label

("Human") as shown in Fig. 1(b). Since the relative importance of each label to this image is different, for example, the label "Mountain" is more important than the label "Sea", the real numbers (also known as the label description degree) in Fig. 1(c) can better describe this image. The description degrees of all labels constitute a label distribution (LD). Specifically, if dlx represents the description degree of the label l to the instance x, it's subject to the non-negative constraint dlx ∈ [0, 1] and the sum-to-one constraint ∑l dlx = 1. LDL aims to predict the LD for unseen samples, which is a more general paradigm than the traditional MLL.

In LDL, a training set with samples annotated by LDs is required to train an LDL model. Unfortunately, the acquisition of label distributions of instances is a very costly and time-consuming process. Moreover, in reality, most datasets are only annotated by logical labels, which cannot be used directly by the existing LDL methods. Then a question naturally arises: can we directly train an LDL model from the logical labels?

Recently, label enhancement (LE) [Xu et al., 2021] was proposed to partially answer this question. Specifically, LE first recovers the label distributions of training samples from the logical labels and then performs an existing LDL algorithm on the recovered LDs. Following [Xu et al., 2021], many variants of LE were proposed, such as [Shao et al., 2018], [Zheng et al., 2023] and [Zhang et al., 2021]. We refer the readers to the related work section for more details. To achieve LE, those methods generally construct a linear mapping from the features to the logical labels directly, and then normalize the output of the linear mapping as the recovered LDs. However, those LE methods may assign positive description degrees to some negative logical labels. Moreover, as all the positive logical labels are annotated as 1, simply building a mapping from features to the logical labels is not the best choice, which will not differentiate the description degrees of different labels. Last but not least, the LE-based strategy is a step-wise manner to predict LD for unseen samples, which may lose the connection between LE and LDL model training.

In this paper, we come up with a novel model named DLDL, i.e., Directly Label Distribution Learning from the logical label, which gives a favorable answer to the question "can we directly train an LDL model from the logical labels". The major contributions of our method are summarized as

follows:

• Our model combines LE and LDL into a single model, which can learn an LDL model directly from the instances annotated by the logical labels. By the joint manner, the LE and LDL processes will better match each other.
• We strictly constrain the description degree dlx to be 0 when the logical value corresponding to the label l is 0. The constraint will avoid assigning positive description degrees to the negative logical labels.
• The existing LE methods usually minimize a least squares loss between the recovered LD and the logical label, which can not well differentiate the description degrees of different labels. The proposed model discards this fidelity term, and uses KL-divergence to minimize the difference between the recovered LD and the predictive LD, which is a better difference measure for two distributions.
• By using the Rademacher complexity, we show the generalization bound of the proposed model and theoretically prove that it is possible to construct an LDL model directly from the logical labels for the first time.

Extensive experiments on six benchmark datasets clearly show that the LD recovered by our method is better than that recovered by state-of-the-art LE methods on the training set, and the prediction performance of our model on the testing set is also better than the traditional step-wise strategy.

2 RelatedWorks

Notations: Let n, m and c represent the number of samples, the dimension of features, and the number of labels. Let x ∈ Rm denote a feature vector and y ∈ {0, 1}c denote its corresponding logical label vector. The feature matrix and the corresponding logical label matrix can be denoted by X = [x1; x2; . . . ; xn] ∈ Rn×m and Y = [y1; y2; . . . ; yn] ∈ {0, 1}n×c , respectively. Let Y = {l1, l2, . . . , lc} be the complete set of labels. The description degree of the label l to the instance x is denoted by dlx, which satisfies dlx ∈ [0, 1] and ∑l dlx = 1, and the label distribution of xi is denoted by di = (dl1 xi , dl2 xi , . . . , dlc xi ).

2.1 Label Distribution Learning

LDL is a new machine learning paradigm that constructs a model to predict the label distribution of samples. At first, LDL were achieved through problem transformation that transforms LDL into a set of single label learning problems such as PT-SVM, PT-Bayes [Geng, 2016], or through algorithm adaptation that adopts the existing machine learning algorithms to LDL, such as AA-kNN and AA-BP [Geng, 2016]. SA-IIS [Geng, 2016] is the first model that specially designed for LDL, whose objective function is a mixture of maximum entropy loss [Berger et al., 1996] and KLdivergence. Based on SA-IIS, SA-BFGS [Geng, 2016] adopts BFGS to optimize the loss function, which is faster than SAIIS. Sparsity conditional energy label distribution learning (SCE-LDL) [Yang et al., 2016] is a three-layer energy-based model for LDL. In addition, SCE-LDL is improved by incorporating sparsity constraints into the objective function. To reduce feature noise, latent semantics encoding for LDL (LSE-LDL) [Xu et al., 2019] converts the original data features into latent semantic features, and removes some irrelevant features by feature selection. LDL forests (LDLFs) [Shen et al., 2017] is based on differentiable decision trees and may be combined with representation learning to provide an end-to-end learning framework. LDL by optimum transport (LDLOT) [Zhao and Zhou, 2018] builds an objective function using the optimal transport distance measurement and label correlations. L2 [Liu et al., 2021a] is the first attempt to combine LE and LDL into a unified model, utilizing the manifold structure of samples and label correlations to learn the prediction model.

2.2 Label Enhancement

The above mentioned LDL methods all assume that in the training set, each sample is annotated with label distribution. However, precisely annotating the LDs for the training samples is extremely costly and time-consuming. On the contrary, many datasets annotated by logical labels are readily available. To this end, LE was proposed, which aims to convert the logical labels of samples in training set to LDs. GLLE [Xu et al., 2021] is the first LE algorithm, which assumes that the LDs of two instances are similar to each other if they are similar in the feature space. LEMLL [Shao et al., 2018] adopts the local linear embedding technique to evaluate the relationship of samples in the feature spaces. Generalized label enhancement with sample correlations (gLESC) [Zheng et al., 2023] tries to obtain the sample correlations from both of the feature and the label spaces. Bidirectional label enhancement (BD-LE) [Liu et al., 2021b] takes the reconstruction errors from the label distribution space to the feature space into consideration.

All of these LE methods and LE loss of L2 [Liu et al., 2021a] can be generally formulated as

where X and Y are the feature matrix and logical label matrix, ∥ · ∥F denotes the Frobenius of a matrix, W ∈ Rm×c builds a linear mapping from features to logical labels, and ϕ(XW,X) models the geometric structure of samples, which is used to assist LD recovery. After minimizing Eq. (1), those methods usually normalize XW as the recovered LD.

Although those LE methods have achieved great success, they still suffer from the following limitations. Firstly, the fidelity term that minimizes the distance between the recovered LD (i.e., XW) and the logical label Y is inappropriate because the logical labels are annotated as the same value, and the linear mapping will not differentiate the description degrees for different labels. Besides, the Frobenius norm is also not the best choice to measure the difference between two distributions. Secondly, Eq. (1) doesn't consider the physical restriction of the label distribution, i.e., ∀i, 0 ≤ di ≤ yi, ∑l dlxi = 1. Although those methods perform a post-normalization to satisfy those constraints, they may assign positive description degrees to some negative logical labels. Furthermore, to predict the LD for unseen samples, those methods need to first perform LE and then carry out an existing LDL algorithm. The step-wise manner does not consider potential connections between LE and LDL.

3 The Proposed Approach

To solve the above-mentioned issues, we propose a novel model named DLDL. Different from the previous two-step strategy, our method can generate a label distribution matrix D = [d1; d2; . . . ; dn] ∈ Rn×c for samples annotated by logical labels and at the same time construct a weight matrix W ∈ Rm×c to predict LD for unseen samples.

We use the following priors to recover the LD matrix D from the logical Y. First, as each row of D (e.g., di) denotes the recovered LD for a sample, it should obey the nonnegative constraint and the sum-to-one constraint to make it a well-defined distribution, i.e., 0c ≤ di ≤ 1c and di1c = 1, where 0c, 1c ∈ Rc denote an all-zeros vector and an all-ones vector, and 0 ≤ di ≤ 1 means each element of di is nonnegative and no more than 1. Moreover, to avoid assigning a positive description to a negative logical label, we require that 0 ≤ di ≤ yi, ∀i. Reformulating the above constraints in the matrix form, we have 0m×c ≤ D ≤ Y, D1c = 1n, where 0m×c is an all-zeros matrix with size m× c, and the above inequalities are held element-wisely.

Second, we utilize the geometric structure of the samples to help recover the LDs from the logical labels, i.e., if two samples are similar to each other in the feature space, they are likely to own the similar LDs. To capture the similarity among samples, we define the local similarity matrix A = [Aij]n×n as

N (xi) denotes the k-nearest neighbors of xi, and σ is the hyper-parameter of the RBF kernel. Based on the constructed local similarity matrix A, we can infer that the value of ||di - dj||2 is small when Aij is large, i.e.,

in which tr (·) denotes the trace of a matrix, and G = ˆA-A is the graph Laplacian matrix [Jia et al., 2020b; Jia et al., 2020a] and ˆA is a diagonal matrix with the elements ˆ Aii = ∑nj=1 Aij .

By taking the above priors into consideration, the LD matrix D can be inferred from the logical label matrix Y, i.e.,

where an additional term ∥D∥2F is imposed as regularization. Different from the previous LE methods in Eq. (1), we discard the fidelity term ∥Y-WX∥2F. But as we strictly constrain that 0 ≤ D ≤ Y, it will have a similar effect as the above fidelity term, i.e., encouraging the description degree of the valid labels to be large. But our approach avoids the drawbacks of the fidelity term, i.e., assigning label distribution degree to some negative logical labels and not differentiating the description degrees of different labels.

Based on the recovered LD, we adopt a non-linear model that maps the features to the recovered LD, which can be used to predict the LD for unseen samples. Specifically, the nonlinear model is formulated as

where W is the weight matrix, P = [Pij ]n×c is the prediction matrix, and Z = ∑cj=1 exp (∑mk=1 XikWkj) is a normalization term. To infer the weight matrix W, we minimize the KL-divergence between the recovered label distribution matrix D and the prediction matrix P, because KL-divergence is a good metric to measure the difference between the two distributions. Accordingly, the loss function for inferringW becomes

where the widely-used squared Frobenius norm is imposed to control the model complexity.

To directly induce an LD prediction model from the logical labels, we combine Eqs. (4) and (6) together and the final optimization problem of our method becomes:

in which α, β and γ are hyper-parameters to adjust the contributions of different terms. By minimizing Eq. (7), the proposed model can recover the LD for samples with logical labels, and simultaneously, can predict LD for unseen samples through Eq. (5).

3.1 Optimization

Eq. (7) has two variables, we solve it by an alternative and iterative process, i.e., updateWwith fixed D, and then update D with fixed W.

1) Update WWhen D is fixed, the optimization problem (7) with respect toW is formulated as

Expanding the KL-divergence and substituting Pij in Eq. (5) into Eq. (8), we obtain the objective function of W as

Eq. (9) is a convex problem, we use gradient descent algorithm to update W, where the gradient is expressed as

2) Update D With fixed W, the optimization problem (7) regarding D is formulated as

Eq. (11) involves multiple constraints and diverse losses, we introduce an auxiliary variable B = D ∈ Rn×c to simplify it, and the corresponding augmented Lagrange equation becomes

where Φ ∈ Rn×c is the Lagrange multiplier, and τ is parameter to introduce the augmented equality constraint. Eq. (12) can be minimized by solving the following sub-problems iteratively.

a) D-subproblem: Removing the irrelated terms regarding D, the D-subproblem of Eq. (12) becomes

then its gradient regarding D can be expressed as:

b) B-subproblem: When D is fixed, the problem (12) can be written as

Let ˆb = [bT1 ; bT2 ; · · · ; bTn ] ∈ Rnc = vec(B), where bi is the i-th row of B and vec(·) is the vectorization operator. Then, the problem (15) is equivalent to:

in which ˆd, ˆϕ and ˆy represent vec(D), vec(Φ) and vec(Y), respectively, and ˆbj is the j-th element of ˆb. Eq. (16) is a quadratic programming (QP) problem that can be solved by off-the-shelf QP tools.

The detailed solution to update D in Eq. (11) is summarized in Algorithm 1 and the pseudo code of DLDL is finally presented in Algorithm 2. In this paper, we initialize W as an identity matrix and initialize D according to the method in [Wang et al., 2023].

3.2 Generalization Bound

In this section, we first provide Rademacher complexity for DLDL, which is a commonly used tool for comprehensive analysis of data-dependent risk bounds.

Definition 1. Let H be a family of functions mapping from X to [0,1] and S be a set of fixed samples with size n. Then, the empirical Rademacher complexity of H with respective to S is defined as

Lemma 1. Let H be a family of functions. For a loss function ℓ upper bounded by Θ, then for any δ > 0, with probability at least 1 - δ, for all h ∈ H such that

where L(h) and LS(h) are the generalization risk and empirical risk with respective to h.

Theorem 1. The KL-divergence loss function ℓ can be written as KL(D, P), where D ∈ Rn×c and P ∈ Rn×c are the recovered LD matrix and the prediction matrix respectively, in which P can be expressed by the prediction weight matrix W ∈ Rm×c . Let H = D ×W represent the family of functions for DLDL, with functions (D,W) ∈ H. Our algorithm further encourages the complexity of W and the rank of D are upper bounded by ϵ1 and ϵ2 respectively, i.e., ||W||F ≤ ϵ1 and rank(D) ≤ ϵ2. According to Definition 1, the Rademacher complexity of DLDL with KL-divergence loss ℓ is upper bounded as follows:

Algorithm 1 Solve the Problem in (11)

Input: The initial label distribution matrix D, the initial weight matrix W, and B = Φ = 0n×c.

Parameter: ρ = 1.2, τ = 0.001 and τmax = 0.002.

Output: The updated D.

• 1: while ||B-D||∞ > 10-3 do
• 2: Update D by Eq. (14);
• 3: Update B by solving Eq. (16);
• 4: Update Φ=Φ+ τ(B-D) and τ =min(ρτ, τmax);
• 5: end while
• 6: D=B; returnD.

in which Xmax, Xmin are the maximum and minimum element in the feature matrix X respectively.

The proof is given in section A of the supplementary file. According to Lemma 1 and Theorem 1, the Rademacher complexity of DLDL is controlled by the number of training samples n. Because the numerator is a finite number, when DLDL has infinite training samples (n tends to infinity), its Rademacher complexity tends to zero.

Theorem 2. Denote D ∈ Rn×c and W ∈ Rm×c as the recovered LD matrix and the prediction weight matrix, and the complexity of W and the rank of D are upper bounded by ϵ1 and ϵ2 respectively. Then we have the upper bound of Θ:

The proof is given in section A of the supplementary file. The right side of Eq.(20) is also a finite number, so when n tends to infinity, the term 3Θ√ log 2/δ 2n in Lemma 1 tends to zero.

According to Lemma 1, Theorem 1 and Theorem 2, we finally have

in which ϵ is a finite number. From Eq.(21), we can clearly see that when the number of training samples tends to infinity, the generalization risk of h will be upper-bounded by the empirical risk of it.

The above generalized error bound is based on that the recovered label distribution matrix D is just the ground-truth one, so the last thing to prove is that under some certain conditions, DLDL can recover ground-truth label distribution from logical label.

Theorem 3. If the number of zeros in the ground-truth label distribution matrix Dg is large enough, then the average difference between D and Dg has an upper bound:

in which p2 ∈ [0, 1] and p3, ϵ, λ Σk are small positive numbers.

Algorithm 2 The DLDL Algorithm

Input: The feature matrix X and the logical label matrix Y.

Parameter: α, β, λ and σ.

Output: The label distribution matrix D and the weight matrix

W.

• 1: InitializeWand D;
• 2: repeat
• 3: UpdateWby using Eq. (10);
• 4: Update D by Algorithm 1;
• 5: until convergence or reaches maximum number of iterations;
• 6: returnD andW.

The detailed proof of Theorem 3 is given in section B of the supplementary file. The average difference between D andDg tends to zero when p3, ϵ, λ Σk are small enough, which indicates that DLDL can precisely recover the ground-truth label distribution from logical label under this circumstance. Combining all the lemmas and theorems together, we conclude that directly learning label distribution learning from logical label is theoretically feasible.

4 Experiments

We select six real-world datasets from various fields for experiment. Natural Scene (abbr. NS) [Geng, 2016; Geng et al., 2022] is generated from the preference distribution of each scene image, SCUT-FBP (abbr. SCUT) [Xie et al., 2015] is a benchmark dataset for facial beauty perception, RAF-ML (abbr. RAF) [Shang and Deng, 2019] is a multi-label facial expression dataset, SCUT-FBP5500 (abbr. FBP) [Liang et al., 2018] is a big dataset for facial beauty prediction, Ren CECps (abbr. REN) [Quan and Ren, 2009] is a Chinese emotion corpus of weblog articles, and Twitter LDL (abbr. Twitter) [Yang et al., 2017] is a visual sentiment dataset. Some basic statistics about these datasets are given in section C of the supplementary file.

To verify whether our method can directly learn an LDL model from the logical labels, we generate the logical labels from the ground-truth LDs. Specifically, when the description degree is higher than a predefined threshold δ, we set the corresponding logical label to 1; otherwise, the corresponding logical label is 0. In this paper, δ is fixed to 0.01.

4.1 Baselines and Settings

In this paper, we split each dataset into three subsets: training set (60%), validation set (20%) and testing set (20%). The training set is used for recovery experiments, that is, we performLEmethods to recover the LDs of training instances; the validation set is used to select the optimal hyper-parameters for each method; the testing set is used for predictive experiments, that is, we use an LDL model learned from the training set with the recovered LDs to predict the LDs of testing instances.

In the recovery experiment, for DLDL, α and γ are chosen among {10-3 , 10-2 , · · · , 10, 102 }, β is selected from {10-3 , 10-2 , · · · , 1, 10}, the maximum of iterations t is fixed to 5, the number of neighbors k is set to 20. We compare DLDL with five state-of-the-art LE methods and a unified method, each configured with suggested configurations in respective literature: 1) FLE [Wang et al., 2023]: α, β, λ, γ are chosen among {10-3 , 10-2 , · · · , 10, 102 }; 2) GLLE [Xu et al., 2021]: λ is chosen among {10-3 , 10-2 , · · · , 1}; 3): LEMLL [Shao et al., 2018]: the number of neighbors K is set to 10 and ϵ is set to 0.2; 4) LESC [Zheng et al., 2023]: β is set to 0.001 and γ is set to 1; 5) FCM [Gayar et al., 2006]: the number of clustering centers is set to 10 times of the number of labels. 6) L2 [Liu et al., 2021a]: α, γ, λ are chosen among {10-5 , 10-3 , · · · , 103 , 105 }, k is set to 20 and β, µ keep the default value.

In the predictive experiment, we apply SA-BFGS [Geng, 2016] algorithm to predict the LDs of testing instances based on the recovered LDs by performing the five baseline LE methods. Note that DLDL and L2 can directly predict the LDs without an external LDL model.

As suggested in [Geng, 2016], we adopt three distance metrics (i.e., Chebyshev, Clark and One-error) and one similarity metric (i.e., Intersection) to evaluate the recovery and the predictive performances. The formulas of these evaluation metrics are summarized in section C of the supplementary file.

4.2 Visualization of the Recovered Label Distributions

In this subsection, we present the visualization of two typical recovery results of all the models on two different datasets in Fig. 2. From it we can observe that DLDL has a better performance on the recovery of non-positive labels, and the recovery results of it are also more close to the ground-truth label distributions than the other comparison algorithms. For example, on the Twitter dataset, the logical values corresponding to the label 1, 4, 5, 6, 8 are all 0, indicating that these labels cannot describe this sample. However, the six comparison methods still assign positive description degrees for these invalid labels. Differently, DLDL avoids this problem, and produces differentiated description degrees fairly close to the ground-truth values.

4.3 Results

Recovery Results

In this subsection, we calculate the distances and similarities between the ground-truth LD and the LD recovered by each LE method via four evaluation metrics on each dataset. Table 1 shows the detailed recovery results, where all methods are ranked according to their performance and the best average rank on each metric is shown in boldface. In addition, the "↓" after the metrics means "the smaller the greater", while the "↑" means "the larger the greater". Based on the recovery results, we have the following observations:

• DLDL achieves the lowest average rank in terms of all the four evaluation metrics. To be specific, out of the 24 statistical comparisons (6 datasets × 4 evaluation metrics), DLDL ranks 1st in all cases, which clearly shows the superiority of our approach in LE.
• On some datasets, our method achieves superior performance. For example, on FBP, REN and Twitter, DLDL significantly improves the results compared with other algorithms in terms of the Chebyshev, One-error and Intersection.
• Under the metric of One-error, DLDL shows overwhelming advantages. This is attributed to the constraint 0 ≤ di ≤ yi, which avoids assigning label description degrees to the negative logical labels.

Predictive Results

In this subsection, SA-BFGS is used as the predictive model to generate the LDs of testing instances for the five LE methods, while DLDL and L2 can directly predict the LDs of testing instances. Then, we rank all methods and highlight the best average rank on each metric in boldface. The detailed predictive results are presented in Table 2. In addition, SABFGS is trained on the ground-truth LDs of the training instances and its results are recorded as the upper bound of the predictive results. From the reported results, we observe that:

• DLDL achieves the lowest average rank in terms of the three evaluation metrics (i.e., Clark, Canberra and Intersection). Specifically, out of the 24 statistical comparisons, DLDL ranks 1st in 87.5% cases and ranks 2nd in the remaining 12.5% cases. In general, DLDL performs better than most comparison algorithms.
• In some cases, the performance of our approach even exceeds the upper bound. For example, on SCUT dataset, DLDL performs better than the SA-BFGS trained on the ground-truth LDs in terms of Chebyshev, Clark, Intersection and slightly on One-error, which shows that our model has considerable potential in learning from logical labels directly.
• Although L2 is also a joint model, it doesn't consider the restriction of label distribution, and adopts an inappropriate fidelity term. Compared to L2 , our method DLDL gets lower average ranks in terms of all the four metrics both in recovery and predictive results, indicating the effectiveness and superiority of our method.

4.4 Further Analysis

Ablation Study

In order to verify the necessity of the involved terms of our approach, we conduct ablation experiments and present the results on Chebyshev in Table 3, where α, β and γ are hyper-parameters to adjust the contributions of different terms. When one of hyper-parameters is fixed to 0, the remaining ones are determined by the performance on the validation set. From the results, we observe that the performance of DLDL becomes poor when the term controlled by β is missing, indicating that it is critical to control the smoothness of the label distribution matrix D. In general, DLDL outperforms its variants without some terms, which verify the effectiveness and rationality of our model.

Significance Test

In this subsection, a Bonferroni-Dunn test is applied to check whether DLDL achieves competitive performance compared to other algorithms. Through this test, we find that DLDL performs significantly better than the compared algorithms on the four metrics. For detailed significance test results, please refer to Section E in the supplementary file.

5 Conclusion and FutureWork

This paper gives a preliminary positive answer to the question "can we directly train an LDL model from the logical labels" both theoretically and empirically. Specifically, we propose a new algorithm called DLDL, which unifies the conventional label enhancement and label distribution learning into a joint model. Moreover, our method avoids some common issues faced by the previous LE methods. Extensive experiments validate the advantage of DLDL against other LE algorithms in label enhancement, and also confirm the effectiveness of our method in directly training an LDL model from the logical labels. Nevertheless, our method is still inferior to the traditional LDL model when the ground-truth LD of the training set is available. In the future, we will explore possible ways to improve the predictive performance of our algorithm.

Acknowledgements

This work was supported by the National Natural Science Foundation of China under Grant (62106044) and the Natural Science Foundation of Jiangsu Province under Grant (BK20210221).