No Regularization Is Needed: Efficient and Effective Incomplete Label Distribution Learning

1 Introduction

In real applications, labels may be associated with a sample to some degree, thus soft labels are preferred rather than the hard ones to describe the label ambiguity [Rupprecht et al., 2017], where Label Distribution Learning (LDL) [Geng, 2016] originated from. LDL is a learning paradigm that assigns a sample with different label description degrees, i.e., the relevance of a sample belonging to different labels, which satisfy the probability simplex constraint. However, obtaining complete label degrees is always laborious and challenging in real-world, thus the desire to get rid of such predicament drives the emergence of Incomplete LDL (InLDL) [Xu and Zhou, 2017]. To date, InLDL has wide applications in facial expression recognition [Yang et al., 2017; Chen et al., 2020], age estimation [Hou et al., 2017; Gao et al., 2018], and multi-label ranking [Geng et al., 2021; Lu et al., 2023].

(b) Incomplete label distribution in practice.

Figure 1: An illustration of incomplete label distribution in practice. Figure 1(a) is an image from real-world and Figure 1(b) is the corresponding label distribution. Note that, labels with small degrees, like "house" and "wire pole" are harder to recognize compared to those with large degrees. This suggests that label degrees are not randomly missing but small degrees are more likely to be missing.

In the pioneer InLDL work [Xu and Zhou, 2017], the authors assume that label degrees are uniformly random missing, and subsequent works [Jia et al., 2019a; Li et al., 2022; Wang and Geng, 2023] just simply follow this assumption. However, it is often not the case in practice. As shown in Figure 1, when annotating such a picture from real-world, labels with small degrees such as "house" and "wire pole" are much more difficult to recognize compared to those with large degrees such as "sky" and "cloud". This suggests that label degrees are not randomly missing but small degrees are more likely to be missing in practice, which arises the first issue.

Besides, to compensate the degree incompleteness, existing InLDL methods always have to make various assumptions, which are then translated into one or more explicit regularization terms in their objective functions. For example, in [Xu and Zhou, 2017], the authors assume that the label degree matrix is low-rank in characterizing the correlation between labels, and adopt the trace norm as a regularization term; in

[Wang and Geng, 2023], the authors assume that the predictions of their model lie in the same manifold, and exploit both the global and local label correlations with three different regularization terms. Obviously, each imposed regularization term associates with a hyper-parameter, which leads to burdensome parameter tuning and extra computation cost for model selection, causing the second issue.

To address the first issue, we consider a more practical setting in this paper, i.e., small degrees are more likely to be missing, instead of adopting the uniformly random missing assumption as in existing InLDL methods. Our setting is more reasonable since labels with smaller degrees are harder to recognize as shown in Figure 1, rendering them more susceptible to being missing, which is more in line with practicality. To our best knowledge, this is the first work that considers non-random missing scenario in the InLDL field.

To tackle the second issue, we argue that label distribution itself already contains abundant knowledge including label correlation and ranking order, thus it may have provided enough prior for learning. Existing methods mainly focus on mining label correlations while overlooking such a useful prior that leads to the forced adoption of explicit regularization. Contrary to these methods, we highlight the benefits and importance of the label degrees prior in this paper. Intriguingly, we discover that when this prior is appropriately leveraged, the InLDL problem can be resolved even without any explicit regularization, thereby exempting from parameter tuning and additional computational overhead.

Subsequently, a pivotal question naturally arises: how to effectively leverage the aforementioned prior? Our solution is straightforward: we design a properly weighted objective function by directly integrating the label degrees into a weighting matrix. Reasons of this solution lie in four aspects. (1) Intuitively, labels with large degrees are likely to receive more concern, while those with small degrees are easily overwhelmed or even overlooked, making them more difficult to be recognized. (2) Empirically, we conduct experiments to validate the above intuition. From Figure 2, it is evident that the mean relative errors are higher for degrees below 0.5 compared to those degrees above 0.5. This observation indicates that small degrees are underfitted in comparison to those large degrees. (3) Generally, in label distribution learning, the goal is to learn a distribution of all labels. Given that small degrees are underfitted, it is imperative to allocate more attention on them so as to learn a more accurate label distribution. A natural and straightforward way is to design a weighting scheme that puts more emphasis on small degrees. (4) By directly integrating the label degrees into a weighting matrix, we not only make a rational use of the label degree prior, but also save additional overhead of learning a weighted matrix.

Based on the above analyses and with the aim to learn an accurate label distribution for all labels, we impose larger weights on the losses of the smaller observed degrees. For missing degrees, we gradually increase the weights on their losses, since these degrees should become more reliable as the training progresses. To make theoretical explanations of why the proposed method could work without any explicit regularization, we first define a weighted empirical risk and derive data-dependent upper bounds between the expected risk and the weighted empirical risk. These upper bounds explicitly depend on the weighted matrix, and the generalization error can be bounded by this weighted matrix, implying that such weighting plays a role of implicit regularization as no explicit regularization is really imposed. Note that, by utilizing the Alternating Direction Method of Multipliers (ADMM) [Boyd et al., 2011] for optimization, we derive the closed form solution of each sub-problem and implement the codes in just a few lines. Interestingly, the computational complexity is linear in the number of samples, making our method fast and scalable to large datasets.

To sum up, our main contributions are threefold:

1. We propose an efficient, effective, and easy-to-implement Weighted method for InLDL, abbreviated as WInLDL, which is free of any explicit regularization, to the best of our knowledge, this is the first time in the InLDL field.
2. We theoretically derive a data-dependent upper bound between the expected risk and the weighted empirical risk with the help of Rademacher complexity, which contains the classical risk bounds under single-label and unweighted settings as our special cases.
3. We empirically verify the effectiveness of WInLDL on ten real-world datasets, and experiments show that it is competitive with state-of-the-art methods in both random and non-random missing scenarios.

2 RelatedWork

In this section, we review the most relevant works to ours. InLDL was first proposed by [Xu and Zhou, 2017] to address the problem with incomplete annotations. They assume that the matrix formed by the label degrees is low-rank to combat the incompleteness, and adopt the trace norm as a regularization term to formulate the label correlations. Later, in [Jia et al., 2019b], the authors assume the clusters of samples are low-rank and also utilize the trace norm to characterize such local label correlations. Recently, in [Wang and Geng, 2023], the authors argue that the low-rank assumption may not hold, instead, they assume that the predictions of their model lie on the same manifold whose structure may encode the correlations among labels. Further, they exploit both the global and local correlations to learn the label distribution in the InLDL setting. All the above methods focus on mining label correlations while ignoring the fact that label distribution itself provides useful even sufficient prior knowledge, as we dissected in the Introduction. We contend that the degree prior should not be overlooked but rather utilized rationally. To the best of our knowledge, [Wang et al., 2022] is the only work that considers the label degrees to do the weighting. Compared with our work, there are three main differences, 1) their task focuses on classification, the goal is to learn the top label(s), thus they put large weights on large degrees, which will be verified in Table 5 that in the InLDL setting, such a weighting performs worse than our WInLDL; 2) they discard the weighting scheme in their theoretical analysis, thus they do not provide a theoretical guarantee for weighting, which is a main contribution of this paper; 3) they use the product between the entropy (Ex = -∑y∈Y dyx lndyx ) of degree and degree itself as the weights. While in the InLDL setting, the missing degrees are set to 0, and lndyx will be meaningless in such a situation. Therefore, their weighting scheme cannot be applied to the InLDL setting. There are other works in the field of InLDL [Jia et al., 2021; Teng and Jia, 2021; Zhang et al., 2022; Qian et al., 2022a; Qian et al., 2022b] that either adopt different settings such as semi-supervised paradigm, or focus on different tasks such as feature selection. Consequently, they are not highly relevant to the scope of this work. Due to the page limitations, we have omitted discussing these works here, and interested readers are referred to these literatures for further details.

3 ProposedMethod

3.1 Problem Setting

Let X ⊆ Rk be the feature space and Y = {y1, y2, · · · , yC} be the label space, where k is the dimension of the feature, and C is the number of labels. In LDL, each sample x ∈ X is assigned with a label distribution dx = [dy1 x , dy2 x , · · · , dyC x ]⊤, where dyi x is called the label description degree, which indicates the relevance of sample x belonging to the i-th label. Note that, dx satisfies the probability simplex constraints, i.e., dyj x ≥ 0 and ∑Cj=1dyj x = 1. Given a training dataset S = {(xi, dxi )}Ni=1 , where N is the number of samples, X = [x1, x2, · · · , xN]⊤ ∈ RN×k is the feature matrix, D = [dx1 , dx2 , · · · , dxN ]⊤ ∈ RN×C is the label distribution matrix. The goal of LDL is to learn a function f : X ↦→ RC , which minimizes the difference between the prediction of f and the ground-truth label distribution, i.e., minf L(f(X),D), where L is the loss function.

In the scenario of InLDL, label degrees may be incomplete. In this paper, we consider a more practical scenario, i.e., small degrees are more prone to be missing. Formally, let Ω ∈ [N] × [C] and U ∈ [N] × [C] denote the indices of the observed and the unobserved entries from D, respectively. The unobserved entries of the label distribution matrix are set to 0, i.e., the observed label matrix ˜D can be defined as, ∀(i, j) ∈ [N] × [C],

Then in InLDL, the goal is to minf L(f(X), ˜D). Note that, to eliminate any potential bias for our WInLDL, we also conduct experiments in the random missing scenario as in the compared methods for a fair comparison.

3.2 ProposedWInLDL

In this subsection, we first design a weighted method named WInLDL and then apply the ADMM to solve the objective, by which an efficient algorithm is derived.

Specifically, given a feature matrix X and an observed label matrix ˜D, let f(X) = XW and L be the ℓ2 loss, then we can define the following weighted function,

where W ∈ Rk×C is the transformation matrix to be optimized, and ⊙ is the Hadamard product. Since the label distribution satisfies the probability simplex constraint, then XW1C = 1N and XW ≥ 0N×C should hold, where 1C and 1N are column vectors of size C and N with all ones, "≥" here means that all elements are greater than or equal to 0. For simplicity of notation, let Q = P 1 2 , and ProS(Z) := {Z ∈ RN×C |Z1C = 1N,Z ≥ 0N×C}. By incorporating the probability simplex constraint, the final objective function of WInLDL can be written as:

Remark 1. Eq. (5) is not an additional regularization that we impose on our method, but a constraint inherent in label distribution learning by its definition, and all label distribution learning algorithms must satisfy such a probability simplex constraint. To deal with it, we can utilize off-the-shelf projection methods[Wang and Carreira-Perpin´an, 2013; Condat, 2016] to avoid introducing extra model hyper-parameters.

With WInLDL in hand, our main concern in the following is how to design the weighting matrix Q. Motivated by the intuition mentioned in the Introduction, to learn an accurate label distribution for InLDL, it is crucial not to ignore the small observed degrees but to impose large weights on them, while gradually increasing the weights of the missing degrees. In order to directly exploit the degree prior of the label distribution, we subtract the observed degrees from 1 to give large weights on small degrees, formally, the weighting matrix Q composed of QΩ and QU is defined as:

where DUij = 1N ∑Ni=1 ˜Dij, that is, the missing label degrees are estimated by the mean value of the observed degrees in the corresponding column.

Moreover, to gradually increase the weights of the missing degrees, we take a number greater than 1 that increases monotonically with the number of iterations as the base of the power function. Since the observed degrees are more reliable than the missing ones, the base of its power function is set at 2, which is larger than the number "a" during the whole iterations.

where maxIter is the maximum iterations, in this paper, fixed at 50. By such a design, three benefits can be obtained, 1) smaller degrees are imposed with larger weights, 2) the weights of the observed degrees are larger than the missing ones, 3) the weights of the missing degrees are gradually increased. Note that the above three benefits can also be regarded as three principles for designing the weighting matrix. Any matrix that satisfies three principles can be utilized as a weighting matrix. In the experimental section, we report the performance of various weighting matrices in Table 5. It is important to highlight that the main focus of this paper is to leverage the useful prior knowledge of label distribution to create an efficient and effective method, rather than extensively exploring the design of an optimal weighting matrix.

3.3 Optimization

In this subsection, we apply ADMM to design an efficient algorithm for solving the objective of WInLDL. Let Z = XW, the augmented Lagrangian function can be written as:

where tr is the trace operator, and µ is a penalty factor. Note that, µ is NOT a model hyper-parameter BUT a parameter of the ADMM algorithm, it is introduced for the convenience of optimization. In this paper, µ is fixed at 2, which does not need to be tuned. We also conduct experiments in section 4.6 to verify that µ only affects the convergence rate and does not affect performance.

Sub-problem of W. With Z and Λ fixed, W can be updated by,

Sub-problem of Z. With W and Λ fixed, Z can be updated by,

where IN×C is a matrix with all ones, and the division in Eq. (11) is element wise. Eq. (12) projects Z onto the probability simplex to satisfy the constraint of Eq. (9), and the proj is a projection operator that can be found in [Wang and Carreira-Perpin´an, 2013; Condat, 2016].

Sub-problem of Λ. With W and Z fixed, Λ can be updated by,

Complexity Analysis. The computational complexity of the ADMM algorithm is dominated by matrix multiplication and inverse operations. In each iteration, the complexity of updating W in Eq. (10) is O(Nk2 ) + O(k3 ) + O(NkC), the complexities of updating Z in Eq. (11) and Eq. (12) are O(NkC) + O(NC) and O(NC) [Condat, 2016], respectively, the complexity of updating Λ in Eq. (13) is O(NkC), and the complexity of updating QU in Eq. (7) is O(|U|), where |U| is the cardinality of set U, usually smaller than NC. Thus, the total computational complexity is O(max(Nk2 ,NkC) + k3 ), which is linear in the number of samples N. In Table 1, we list computational complexities of different methods, where 'g' of LDM is the number of the clusters. While the computational complexity of LDM is also linear in the number of samples, it involves clustering, thus in practice, its running time is much longer than our WInLDL, details can be referred to Figure 3.

3.4 Theoretical Analyses

To make theoretical explanations of why the proposed WInLDL could work without any explicit regularization, we first define a weighted empirical risk. Formally, the definition is detailed as follows.

Definition 1. Given a training dataset S = {(xi, dxi )}Ni=1 , a class of functions F, a loss function L, and a weighted matrix P ∈ RN×C , the weighted empirical risk of function f ∈ F can be defined as:

where f(xi)j denotes the j-th element of f(xi). Suppose the population data follow an underlying probability distribution D, then the expected risk can be written as:

Before deriving the risk bound, we also provide the definition of empirical Rademacher complexity and Rademacher complexity for self-containment.

Definition 2. [Koltchinskii, 2001; Bartlett and Mendelson, 2002] Let F be a class of functions, S = {(xi, dxi )}Ni=1 be a fixed size dataset with N samples, and L be a loss function. Then, the empirical Rademacher complexity of F with respect to the sample set S is defined as:

where σ = (σ1, σ2, · · · , σN)⊤, with independent rademacher random variables σis uniformly taking values in {-1,+1}. Then the Rademacher complexity of F is the expectation of the empirical Rademacher complexity over all samples of size N drawn according to the distribution D:

In the following, we will derive an upper bound between the expected risk and the weighted empirical risk with the help of Rademacher complexity.

Theorem 1. Let F be a class of functions, L = ∑Cj=1 ℓ(f (x)j , dyj x ) is a loss function, where ℓ is bounded by a constant B, and ∥P∥∞ = maxij Pij. Then, ∀δ > 0, with probability at least 1 - δ over the draw of an i.i.d. sample S of size N from the distribution D, the following bound holds for all f ∈ F:

The proof of this theorem primarily relies on the McDiarmid inequality [McDiarmid and others, 1989], and details can be found in the Appendix. Notably, the above bound can be seen as a generalization of the single-label and unweighted cases. When C = 1 (single-label), and P is a matrix with all ones (unweighted), Eq. (18) degenerates into the classical form in [Bartlett and Mendelson, 2002; Shalev-Shwartz and Ben-David, 2014; Mohri et al., 2018]. Moreover, the derived upper bound between the expected risk and the weighted empirical risk explicitly depends on the weighted matrix P, and the generalization error can be bounded by this weighted matrix, which implies that the weighting plays an implicit regularization role since no explicit regularization is really imposed. Theorem 1 provides a rational explanation why our WInLDL could work even without any explicit regularization.

Furthermore, let F be a linear function class and assume that L is Lipschitz continuous, then we can derive the following theorem.

Theorem 2. Let F be a linear function class with a bounded linear transformation W, defined as F = {x ↦→ Wx : ∥W∥F ≤ B0}, where ∥·∥F is the Frobenius norm. Assume L = ∑Cj=1 ℓ(f(x)j, dyj x ), where ℓ is a Lipschitz continuous loss function with Lipschitz constant L, and ℓ is bounded by a constant B. ∥P∥∞ = maxij Pij. Then, ∀δ > 0, with probability at least 1 - δ/2 over the draw of an i.i.d. sample S of size N from the distribution D, the following bound holds for all f ∈ F:

Theorem 2 can be proven by leveraging the main results of [Maurer, 2016], and the detailed proof is provided in the Appendix. By further assuming L is ℓ∞ continuous, another relevant bound can be obtained, interested readers can refer to [Foster and Rakhlin, 2019] for details.

4 Experiments

4.1 Experiments Settings

Datasets. In this paper, we use 10 real datasets covering fields of biology, natural scene recognition, facial expression, movie-rating, and image visual sentiment. The statistics of the datasets are summarized in Table 2. The first five datasets are collected by Geng [Geng, 2016], the sixth to tenth datasets are from [Peng et al., 2015], [Liang et al., 2018], [Yang et al., 2017], [Li and Deng, 2019], [Xie et al., 2015], respectively.

Compared methods. We compare WInLDL with six methods, including two baselines named BFGS-LDL [Geng, 2016] and IIS-LDL [Geng, 2016], and four SOTA methods named InLDL-p [Xu and Zhou, 2017], InLDL-a [Xu and Zhou, 2017], EDL-LRL [Jia et al., 2019b], and LDM [Wang and Geng, 2023]. BFGS-LDL and IIS-LDL are two maximum entropy models optimized with the BFGS [Fletcher, 2013] and the IIS [Della Pietra et al., 1997] algorithm. InLDL-p and InLDL-a are two InLDL models that optimized by the proximal gradient descend and ADMM algorithms, respectively. EDL-LRL assumes local low-rank structure on clusters of samples, and LDM exploits both the global and local label correlations. All the compared methods consider the incomplete setting in the LDM paper. Codes of the compared methods are shared by the original authors, and the best parameters suggested by their papers are used.

Evaluation metrics. Five commonly used metrics are applied to evaluate the performance in this paper, including Cosine, Intersection, Chebyshev, Clark, and Canberra. The first two compute the similarity between two vectors, thus they are the higher the better, whereas the last three quantify the distance between two vectors, thus they are the lower the better. For two vectors p, q ∈ RC , the definitions of the five metrics are listed as below. 1) Cosine ↑: p⊤q/(∥p∥2∥q∥2); 2) Intersection ↑: ∑i min (pi, qi); 3) Chebyshev ↓: maxi |pi - qi|; 4) Clark ↓: √∑i (pi - qi)2 / (pi + qi)2 ; 5) Canberra ↓: ∑i |pi - qi| /(pi + qi), where ↑ means the higher the better, and ↓ means the lower the better. Here we omit the KLdivergence metric just as in [Xu and Zhou, 2017], since KLdivergence is calculated by log(dyx / ˆ dyx ), and in InLDL, the ˆ dyx may be zero, which makes the KL-divergence meaningless.

Two incomplete scenarios. We conduct experiments in two different incomplete scenarios. The first one is the nonrandom missing scenario, i.e., 50% of the smallest degrees are missing. For fair comparisons, we also consider the second scenario, i.e., 50% of the degrees are uniformly random missing, just as in the compared InLDL work [Xu and Zhou, 2017]. Each method is run for five times with five random data partitions, and for each partitions, 80% of the data are used for training, and the remaining 20% are used for testing. In each trial, all methods are run with exactly the same missing and partitioned dataset. Finally, both the mean and the standard deviation of the results are reported 1 .

4.2 Results of the Non-RandomMissing Scenario

In this subsection, we report the results of different methods in the non-random missing scenario (50% of the smallest degrees are missing) on ten real datasets. Due to the page limitations, here we only list the results of the Cosine ↑ metric, and results of other metrics can be found in the Appendix.

From Table 3 we can discover that our WInLDL ranks first on eight datasets, and the average rank is 1.5. Overall, we win 55 times out of 60 comparisons, with a 91.67% rate to win. Besides, we also conduct the Nemenyi test [Nemenyi, 1963; Demˇsar, 2006] as the statistic significance test, due to the page limitations, details can be found in the Appendix.

1 Code is available at https://github.com/EverFAITH/WInLDL

4.3 Results of the RandomMissing Scenario

For fair comparisons, we also report the results of different methods in the random missing scenario (50% of the degrees are uniformly random missing) as in the compared methods.

Table 4 has shown that our WInLDL ranks first on eight datasets and second on one dataset, and the average rank is 1.4. Overall, we win 57 times out of 60 comparisons, with a 95% rate to win.

From Tables 3 and 4, we can conclude that WInLDL achieves better performance in most cases, which verifies its effectiveness in addressing the InLDL problem in both random missing and non-random missing scenarios. The reason may be attributed to the weighting scheme adopted by WInLDL, which can better solve the issue that small degrees are easily overlooked, whereas other methods either only focus on mining the correlations between labels or merely adopt an entropy maximization strategy to learn the label distribution, neither of them can well address the above issue, thus leading to the suboptimal performance.

4.4 Different Weighting Schemes

To verify the effectiveness of imposing large weights on the small degrees, we conduct experiments on five different weighted schemes and list the results in Table 5. The formal definitions are: (1) InLDL-U: Qij = 1, if (i, j) ∈ Ω, and Qij = 0, if (i, j) ∈ U; (2) InLDL-I: Qij = ˜Dij, if (i, j) ∈ Ω, and Qij = DUij , if (i, j) ∈ U; (3) InLDL-II:

Qij = 2 ˜Dij , if (i, j) ∈ Ω, and Qij = aDUij , if (i, j) ∈ U, a = 1 + iter/maxIter; (4) InLDL-Rand: Q = Ra, where Ra is a random matrix whose entries are uniformly distribute in (0, 1), for WInLDL, referring to Eq. (7). First, the results show that WInLDL consistently performs better than InLDLI, InLDL-II, and InLDL-Rand, where InLDL-I and InLDLII impose large weights on large degrees, and InLDL-Rand adopts random weighting. These comparisons demonstrate that imposing large weights on the small degrees is effective. Besides, WInLDL wins 7 times out of 10 comparisons with InLDL-U. Note that, some LDL datasets are transformed from multi-label datasets, thus the ground truth of some degrees may be 0, and in the setting of InLDL, the missing degrees are also set to 0. In such a situation, WInLDL may put too much emphasis on the degrees whose ground truth is 0, while InLDL-U happens to treat these missing degrees as 0, which may explain why WInLDL is inferior to InLDL-U on some datasets.

4.5 Running Time Comparisons

In this subsection, we compare the running time of the different methods and report the total time for ten datasets. All the methods are running on a Linux server with an Intel Xeon(R) W-2255 3.70GHz CPU and 64GB memory. The running time of our WInLDL is 10.95 seconds, which is orders of magnitude faster than most of the compared methods and verifies the efficiency of WInLDL.

4.6 Impacts Study of µ

In this subsection, we conduct experiments to confirm that the parameter µ in the ADMM algorithm does not change the performance of our method. From Figure 4(a) we find that all the five metrics remain the same regardless of variations in µ, and from Figure 4(b) we can see that µ only affects the convergence rate. In our WInLDL method, we fix µ at 2, eliminating the need for tuning. Consequently, µ does not impose any additional burden.

5 Conclusion

We propose an efficient, effective, and easy-to-implement method called WInLDL without any explicit regularization by properly utilizing the label distribution prior. More importantly, we present two upper bounds between the expected risk and weighted empirical risk, which explicitly depend on the weighted matrix. Furthermore, the generalization error can be bounded by the weighted matrix, implying that such weighting plays an implicit regularization role and may explain why WInLDL still works without any explicit regularization. Besides, by conducting extensive experiments, we have verified that WInLDL achieves better performance in both random missing and non-random missing scenarios. Finally, a promising research in future work would be the nonlinearization of the proposed method and its corresponding theoretical study, potentially through its kernelized version, which may overcome the limitations of the linear model and uncover the complex non-linear relationships.

Acknowledgments

This work is supported by NSFC under Grant No. 62376126.