{'fraction_non_alphanumeric': 0.037419891801914275, 'fraction_numerical': 0.013882646691635456, 'mean_word_length': 4.567747914735866, 'pattern_counts': {'":': 0, '<': 10, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Exploring the Learning Difficulty of Data Theory and Measure

As learning difficulty is crucial for machine learning (e.g., difficulty-based weighting learning strategies), previous literature has proposed a number of learning difficulty measures. However, no comprehensive investigation for learning difficulty is available to date, resulting in that nearly all existing measures are heuristically defined without a rigorous theoretical foundation. In addition, there is no formal definition of easy and hard samples even though they are crucial in many studies. This study attempts to conduct a pilot theoretical study for learning difficulty of samples. First, a theoretical definition of learning difficulty is proposed on the basis of the bias-variance trade-off theory on generalization error. Theoretical definitions of easy and hard samples are established on the basis of the proposed definition. A practical measure of learning difficulty is given as well inspired by the formal definition. Second, the properties for learning difficulty-based weighting strategies are explored. Subsequently, several classical weighting methods in machine learning can be well explained on account of explored properties. Third, the proposed measure is evaluated to verify its reasonability and superiority in terms of several main difficulty factors. The comparison in these experiments indicates that the proposed measure significantly outperforms the other measures throughout the experiments.


Introduction
The partition of training data into different subsets according to their learning difficulties and adoption of separate learning schemes (e.g., weighting) are proven to be useful in many learning tasks [21,43,46,68]. The learning difficulty investigated in this study refers to the degrees of easy or hard to learn of training samples in a given learning task. Although learning difficulty has no formal and consensus definition, it has been widely discussed and utilized in previous machine learning literature, including noise-aware, curriculum, and metric learning.
Numerous methods are proposed to measure the learning difficulty of a training sample. The most common practice is to leverage the training output (e.g., loss and the predicted value on the true category) of a sample to construct the measurements. In Self-paced Learning (SPL) [26,68], the training loss is used to determine whether a sample is easy or not, and easy samples are first learned. We assume that p i,yi is the prediction on the ground-truth category for a training sample x i . In object detection, the value of (1 − p i,yi ) is used to indicate the learning difficulty for x i [43] . Given that the training output in an epoch may be unreliable, some methods utilize the average training output of a sample during the training to measure the difficulty. Huang et al. [33] designed a cyclic training procedure, and the model is trained from underfitting to over-fitting in one cycle. The average training loss in the whole cyclic procedure is used as the noisy indicator for a training sample. Feng et al. [20] utilized the magnitude of the loss gradient to measure the learning difficulty of a training sample. A large gradient magnitude indicates a high degree of difficulty.
Due to lack of a theoretical basis, different learning difficulty measures are based on different heuristic cues or empirical observations, resulting that each measure usually only suits specific application scenarios. A clearer understanding of the essence of a sample's learning difficulty can at least facilitate explaining difficulty-based weighting methods and designing more effective learning difficulty measures. However, we are still far from concluding that we have a comprehensive understanding of learning difficulty: (1) There is no formal definition of the learning difficulty of a sample. Different studies exhibit different understandings of learning difficulty. A one-sided understanding usually results in a biased measure. (2) There is no formal definition of the easy and hard samples in a learning task.
In most existing studies, easy and hard samples are heuristically judged. Consequently, it is nearly impossible to conduct a theoretical analysis for difficulty-based weighting strategies with existing heuristic considerations. (3) There has been few experimental studies particularly on the learning difficulty measure. Most studies only refer to the noisy learning or uncertainty settings. An extensive empirical evaluation under different settings is useful for the understanding the learning difficulty.
This study attempts to establish a preliminary theoretical definition for learning difficulty on the basis of the basic machine learning theory, namely bias-variance trade-off theory, for generalization errors of samples. The proposed definition leverages the optimal model complexity of a sample to capture its learning difficulty, inspired by previous observations that easy samples are modeled by simple patterns [6]. The definitions of easy, medium and hard samples are subsequently proposed based on our theoretical definition. As it is nearly infeasible to calculate the optimal model complexity, a practical approach is proposed to approximate the theoretical definition. Then, the properties for difficulty-based weighting learning methods are explored to support the rationality of the theoretical definitions. Several typical weighting strategies, including SPL and Focal loss, are theoretically analyzed and explained. The results of the extensive experiments verify the superiority of the proposed measure.
Our contributions are summarized as follows: • An attempt in theoretical definition of learning difficulty is made based on the basic machine learning theory, namely, bias-variance trade-off. To our knowledge, this work is the first step on the formal description of learning difficulty. • Formal definitions of easy and hard samples are established. As far as we are aware, this is the first attempt on this formalization. • A measure of learning difficulty is proposed and is attested to be rational and exceptional. • The theoretical properties of difficulty-aware weighting strategies in machine learning are explored, and the theoretical explanations based on definition of learning difficulty are presented for several typical weighting methods, which enhance understanding over effective strategies.
2 Related Work

Learning Difficulty Measurement
Learning difficulty is considered as an intrinsic property of data in machine learning [46,75]. Existing measurements are usually based on heuristic cues or inspirations, and they can be divided into the following main categories: • Loss-based measurement. This category directly uses the loss as the measure. Most measures fall into this category because it is simple yet effective in various learning tasks. Some methods [68] directly utilize the loss in one epoch as the degree of difficulty. Accordingly, the degrees for the same samples vary in different epochs. Some others utilize the average loss [45] during the partial or whole training procedure for measurement. • Cross-validation-based measurement. This category adopts a crossvalidation strategy [65]. For example, five-fold cross-validation is performed, and the whole cross-validation is repeated ten times. Consequently, each training sample receives ten predictions. The value of error predictions is used as the indicator of difficulty. • Uncertainty-based measurement. This category uses the (model) uncertainty of a sample to measure the difficulty. Aguilar et al. [3] identified hard samples based on the epistemic uncertainty (also known as the model uncertainty). They leveraged the Bayesian Neural Network [67] to infer the epistemic uncertainty. • Margin-based measurement. This category uses the margin (distance) of a sample to the underlying decision surface as the measurement. The rationale is that a small margin denotes a large difficulty [42,68]. • Gradient-based measurement. This category uses the loss gradient of a sample to measure the difficulty. Agarwal and Hooker [2] proposed the variance of gradients (VOG) across different epochs to rank data from difficult to easy. They considered that samples with high VOG values are far more difficult for the model to learn. Santiago et al. [54] applied the norm of the gradients to measure the difficulty, and high norms indicate large difficulty for learning.
The above-mentioned categories are highly correlated. For example, margin-based measurement is indeed a loss-based one when margin-based loss (e.g., hinge loss) is used.

Noisy-label Learning
Noisy labels are inevitable even in benchmark data sets [28,33,34,40]. Various methods are explored to detect noisy labels. Existing noise detection methods are usually based on the information used for learning difficulty measurements, such as loss and gradient, because samples with noisy labels are usually considered as quite hard samples. Some studies model the generation process of the noisy labels to detect them [18,38]. A recent survey can be referred to [27].

Curriculum Learning
Curriculum learning [10] draws lessons from the human learning process, which begins with the simplest and progresses to more difficult courses. Easier samples should be learned at the beginning of a learning process and gradually advance towards harder samples. SPL pertains to curriculum learning and the difficulty is measured by loss.

Uncertainty-aware Learning
Uncertainty in learning mainly refers to aleatoric uncertainty and epistemic uncertainty. Aleatoric uncertainty is also called data uncertainty. A related work [4] wisely estimated uncertainty in labeling, which is also recognized as aleatoric uncertainty, since accurate and consistent labeling has high unsureness in real-world. To reduce the influence of high-uncertainty samples, they lower the weights of samples with high density and label entropy. Epistemic uncertainty is also called model uncertainty. It occurs when there is no fixed annotation for a given training sample in some learning tasks. The predictive entropy [35] and Bayesian Neural Network [67] have been used to measure epistemic uncertainty.

Theoretical Definition of Learning Difficulty
Existing learning difficulty measurements mentioned in Section 2.1 are empirically utilized in diverse situations. Despite the effect emerges under difficulty-based learning schemes, there is still a lot of room of improvement. Because existing measurements are proposed heuristically without a theoretical basis. Moreover, incentives of difference between learning difficulty of samples are multifarious. Existing measurements are mainly of unilateral considerations, which could not cover the majority incentives.
Arpit et al. [6] gave a descriptive definition for easy (as well as hard) samples that "easier examples are explained by some simple patterns, which are reliably learned within the first epoch of training". This definition implies that easy samples can be modeled by simple models, which motivates us to build a theoretical description with model complexity. Model complexity is a key concept in the classical bias-variance trade-off theory, which is the basis of machine learning and is about the generalization error of a learning task.

Bias-Variance Trade-Off for Generalization Error
Bias-variance trade-off is a basic theory for the qualitative analysis of the generalization error in machine learning [31]. It is initially constructed on regression and mean square error (MSE) is used [31]. The features and the label of a sample are seen as two random variables, and are denoted as x and y respectively. Realizations of a sample are in form of {(x i , y i )}. We assume that x and y conform to the joint distribution P (x, y), where (x, y) ∈ Ω with Ω = Ω X × Ω Y = {(x, y)|x ∈ Ω X , y ∈ Ω Y } . Let T be a random training set and λ h ∈ R λ be the hyper-parameter(s), where R λ is the feasible region 1 . Simplify (x, y) as x in the rest of paper. Given a basic learner f and a fixed value of λ h , a model can be trained on T and is denoted by f (x; T, λ h ). The generalization error over different realizations of the training samples [43] is Eq. (1) can be factorized into and δ e is known as the irreducible noise, and is independent of the basic learner and λ h . The first and the second terms of the right side of Eq. (2) are the learning bias and variance terms, respectively, shown as follows: In classification, the above derivation becomes complex [73]. Nevertheless, the following expression holds, with BiasT and V arT denoting the bias and the variance terms respectively: Variable y is categorical in classification. We suppose that x is continuous in order to consider in the total space, and facilitate the inference for classification. Therefore, the generalization error for a region Ω r ⊂ Ω s.t.
where l(·, ·) measures the error between the label and a prediction. P (y) signifies the probability when the label equals to y and p(x|y) is the conditional probability density function of x when the label equals to y. Denote m(·) as the model complexity defined by a function of parameters of a specific model f (x; T, λ h ) trained on a sampled training set T with λ h . Let c be the expectation of the model complexities given λ h . It is defined as follows: In the rest of the paper, the model complexity expectation is briefly termed as "model complexity". c depends on the base network (e.g., AlexNet, Transformer, and ResNet-34), λ h (e.g., learning rate and the maximum learning epoch), and the distribution of T . When f and the distribution are fixed, c is the function of λ h , i.e., In this study, the base network is assumed to be fixed. Therefore, Err(λ h ) can be seen as the function of c according to Eqs. (1) and (10). The following widely accepted assumption 2 holds for both regression and classification.

Assumption 1
The bias term is a decreasing function of the expectation of model complexity c, whereas the variance term is an increasing function of c when the basic learner is fixed. The generalization error decreases first and then increases.
An example of non-linear regression learning is utilized to empirically support Assumption 1. Letŵ t = (ŵ t,1 , · · · ,ŵ t,10 ) T be the model parameter learnt on a training set T t . The model complexity of a learnt model fŵ t parameterized byŵ t is calculated as follows: and the model complexity expectation is calculated as: Details of the calculation are presented in Appendix A.
The bias, variance, and generalization error curves of Example 1 are given in Fig. 1. Assumption 1 holds with regard to this example. A clear bias-variance trade-off is presented. The bias curve decreases with respect to the employed model complexity while the variance term increases. The generalization error first decreases to its minimum, and then increases. The minimum of the average generalization error over all samples is 0.018 and is attained around the intersection of the bias curve and the variance curve.
According to Assumption 1, the minimum generalization error is achieved when the partial derivatives of generalization error with respect to c equals to zero, i.e., the sum of the partial derivatives of its bias term and the corresponding variance term with respect to c equals to zero. A diagrammatic drawing of the bias-variance curve is shown in Fig. 2 [25,29]. In the rest of the paper, the model complexity expectation is briefly termed as "model complexity".
The optimal λ h and c are obtained with

Definition of Learning Difficulty
Eq. (1) is defined on the whole space Ω. P (x, y) is often unknown. According to Eq. (1) we define the generalization error for a sample as follows: Definition 1 Generalization error for x with label y: where l(·, ·) measures the error between the label and a prediction.

Accordingly,
Similar to Assumption 1, we have the following assumption: Assumption 2 Assume that the basic model is given and fixed. The bias term for x is a decreasing function of c, whereas the variance term for x is an increasing function of c. The generalization error for x decreases first and then increases.
An example of non-linear regression learning is still utilized to empirically support Assumption 2. The imbalance sampling aims to generate three regions comprising easy, medium, and hard samples, respectively. Samples with x ∈ [0, 1.5) are relatively easy and those with x ∈ [3.5, 5] are relatively hard. The learning curves are shown in Figs. 3 and 4. Fig. 3 shows the bias-variance trade-off curves for the entire data set ( Fig. 3(a)), the samples from [0, 1.5) ( Fig. 3(b)), the samples from [1.5, 3.5) (Fig. 3(c)), and the samples from [3.5, 5] ( Fig. 3(d)), respectively. Under all cases, the bias term decreases with respect to the employed model complexity, while the variance term increases. The generalization error firstly decreases to its minimum, and then increases. The minimum values of generalization error varies: 0.022 for the entire data set ( Fig. 3(a)), 0.018 for the majority sampling part ([0, 1.5)) ( Fig. 3(b)), 0.025 for the medium sampling part ([1.5, 3.5)) ( Fig. 3(c)), and 0.05 for the minority sampling part ([3.5, 5]) ( Fig. 3(d)). Comparing the minimum of generalization errors of three cases above( Fig. 3(b-d)), the learned models perform the worst in the hard region ([3.5, 5]) shown in Fig. 4(d), as the learned models under various λ can hardly match the target model. The learned models perform the best in the easy region shown in Fig. 4(b), as the learned models basically coincide with the target model. Alternatively, both Assumptions 1 and 2 hold in this example.
According to Assumption 2, the minimum of Err(x, λ h ), denoted as Err * x , is also attained when the partial derivatives of generalization error for x on c equals to zero, i.e., the sum of the partial deviation of the bias term and the variance term for x on c is zero. The corresponding value of c for sample x is denoted by c * x . Accordingly, we define a theoretical measure for the learning difficulty.
Definition 2 Given a fixed basic learner 3 f , the theoretical learning difficulty for a sample x is The relative learning difficulty between two samples x 1 and x 2 is obtained according to Definition 2. If LD(x 1 ) > LD(x 2 ), then x 1 is more difficult than x 2 , and vice versa.
We also define a learning difficulty coefficient as follows: Definition 3 Given the optimal model complexity c * on the whole space Ω and the learning difficulty of the sample x, the learning difficulty coefficient (LDC) is defined as The larger the value of LDC is, the more difficult the sample x will be. The succeeding subsection will define the easy and hard samples based on LDC.

Definitions of Easy and Hard Samples
Many existing studies are based on the two or three splits for training samples, namely easy/hard and easy/medium/hard, respectively. With LDC, the dichotomy is defined as follows: Definition 4 Given a sample x and its learning difficulty coefficient Definition 4 is flexible because the threshold can be a parameter instead of a fixed value. Let τ be the threshold. If LDC(x) ≤ τ , then x is an easy sample; if LDC(x) > τ , then x is a hard sample.
In the trichotomy, distinguishing between easy and medium or medium and hard is difficult. Accordingly, we propose the following definition for these partitions: Definition 5 Given a sample x and its learning difficulty coefficient LDC(x), let τe and τ h be two positive parameters and 0 < τe < 1 < τ h . If LDC(x) ≤ τe, then x is The two parameters depend on the concrete application tasks and data characteristics. The above two definitions describe the dichotomy and trichotomy for samples as shown in Fig. 5. Some samples are quite hard and are harmful to learning process. We can also define quite-hard samples if LDC(x) > τ q and τ q > τ h .
Our definition for easy/medium/hard samples is consistent with the descriptive definition given by Arpit et al. [6], as the model complexity will increase with the increasing of training epoch gradually. Some other studies also hold the similar view. For example, Charrerjee and Zielinskix [15] observed that easy ImageNet samples are learned early and hard ImageNet samples are learned late.
This section mathematically defines learning difficulty of samples as well as easy/medium/hard samples. Unfortunately, these mathematical definitions are not ready for algorithmic implementation due to lack of a consensus calculation for model complexity (the function m(·) in Eq. 7). There are two strategies to measure the learning difficulty with the illumination of our definitions. The first is to seek an existing measure that best suits our definitions; the second is to derive a new measure on the basis of the definitions. This study chooses the second path. Results in Example 2 indicate a positive correlation between optimal model complexity and minimum generalization error. Moreover, the definition of optimal model complexity is closely related to the generalization error. As a consequence, we propose a new measure for learning difficulty with generalization error.

The Proposed Measure for Learning Difficulty
The learning difficulties of samples depend on various factors 4 . Each of existing measures focuses on one or partial factors. This section first summaries the main factors that determine the learning difficulty of a sample. Then, the connection between the model complexity and generalization error is analyzed based on the summarized influential factors. Finally, the concrete measure is introduced and the algorithmic steps are presented.

Influential Factors for Learning Difficulty
So far, there has been no study that comprehensively summarizes the factors that determine the learning difficulty of a sample. In machine learning, differences among samples mainly lie in noise level, spacial location, neighbourhood, and overall distribution. Illuminated by these differences and the heuristic inspirations considered in previous measures for learning difficulty, the main influential factors are roughly summarized as follows: • Data quality. Both feature and label noises affect the learning difficulty of samples. Young et al. [71] found that high signal-to-noise ratio signifies high feature noise level and generates low data quality, which hinders the optimization of the learning task and is harder to be well learnt. Su et al. [58] revealed that mislabeled images are low-quality data for the learning task and are of high difficulty. • Sample margin. The sample margin is defined as the distance between the sample and the true decision boundary. Huang and Yang [32] considered that samples with small margins are hard to learn. • Uncertainty. The (model) uncertainty of a sample is usually measured by the information entropy of its prediction [19]. The higher the information entropy is, the ampler the information is contained by the sample. Samples with higher uncertainty are more difficult to adequately learn [69]. • Category distribution. Oinar et al. [51] showed that category with fewer samples, which is also called tail category, is usually more challenging than category with more samples, which is known as head category.
The learning difficulty of a specific sample is usually determined simultaneously by two or more factors. A measure that only considers partial factors will perform poorly when the application scenario changes.

Connection Between Model Complexity and Generalization Error
To our knowledge, there is no study that directly investigates the connection between model complexity and generalization error for a sample 5 . Nevertheless, a positive correlation can be approximately established for them bridging by the four influential factors.
First, previous studies explicitly mention a positive correlation between the aforementioned influential factors and the optimal model complexity (defined as learning difficulty of a sample in this study). 1) Noisy samples result in a higher model complexity if these samples are well-learned [53,56]. 2) To ELDD correctly learn a sample in tail categories, strategies such as over-sampling is usually introduced and leads to a higher model complexity [1,47]. 3) To well learn the sorts of small-margin samples, the learned boundary turns to be more complex [48,72]. 4) A more uncertain sample has a larger variance of prediction. A more complex model is needed to reduce its variance, which is to correctly classifying [4,5,17].
Second, the positive relationship between the influential factors and the generalization error is also discussed in previous literature 6 . In terms of data quality, Wang et al. [62] revealed that negative impacts of noisy implicit feedback occurs to the minimization of generalization error. Castells et al. [14] concluded that noisy samples tend to be harder and injure the model generalization. In terms of sample margin, Zhang et al. [73] concluded that samples close to boundary, are further from reaching near-zero generalization error than samples away from boundary. In terms of uncertainty, Pagliardini et al. [52] improved the model's generalization by estimating uncertainty quantification and perturbing high uncertain samples. In terms of category distribution, Gautheron et al. [23] derived a bound of generalization error in metric learning by involving the proportion of minority examples who throw higher generalization error values.
Based on above-mentioned analysis, an approximately positive correlation between generalization error (Err * x ) and model complexity (c * x ) is drawn and motivates a practical measure of learning difficulty. Indeed, Fig. 3 also demonstrates a direct and positive correlation between Err * x and c * x . A higher Err * x corresponds to a larger c * x . A solid proof under typical cases is left as our future work.

The Proposed Measure
Under the discussion in Section 4.2, an approximate approach is proposed based on Err * x , and is utilized as the practical measure of learning difficulty. Most existing measurement methods utilize the training loss (or loss variance) which can be considered as an approximation of the bias (or the variance) term of Err * x as a measurement of learning difficulty. Nevertheless, few studies consider the bias and the variance terms simultaneously.
Considering that it is also infeasible to calculate Err * x traversing all values of λ h , we only calculate the generalization errors Err(x, λ h ) for each sample with the same 7 reasonable λ h to approximate the learning difficulty. Specifically, the proposed approach adopts the cross-validation strategy to calculate the average learning errors for each sample. First, the whole training set is divided into M folds. M − 1 folds are alternatively used for training, and the trained model is used to predict the label of all training samples. This cross-validation process is repeated for K times. Each sample receives K * M predictions, with which can we calculate the average prediction of each sample. Second, average losses and variance of losses for each training sample are calculated using corresponding average predictions.
Let p k i,m be the prediction of x i in the m th cross-validation of the k th repeat. Then, according to [70], we calculate: Subsequently, the bias and the variance terms are calculated as follows where l CE is the standard cross-entropy loss. The actual value of learning difficulty of where µ is a tuning factor for the variance. The value of Err(x i , λ h ) is used as the learning difficulty for x i . This approach is called generalization errorbased learning difficulty (GELD) measurement. The detailed steps of GELD are shown in Algorithm 1. The primary difference between our approach and the existing loss-based/cross-validation-based methods lies in that our approach does not discard the variance term but combines the importance of both term of generalization error. If µ = 0, then GELD is similar to the conventional cross-validation-based methods. Several existing methods including O2UNet [33] also point out that hard samples have high loss variances.

2:
Randomly split T into T Select the model with the validation data;

6:
Predict p k i,m of each x i . 7: Calculate p i using Eq. (17) for each x i . 8: Calculate Bias i and V ar i using Eqs. (18) and (19).

Theoretical Analysis Based on Theoretical Definitions
Definitions 1-5 theoretically describe our learning difficulty measure and clarify easy, medium, and hard samples. This section conducts a theoretical analysis for the weighting strategies to further illuminate the rationality and intrinsic value of our theorem, given that the weighting strategies in machine learning are mainly based on learning difficulties, such as Adaboost [21], SPL [26,68], and Focal loss [43]. Under our definition of learning difficulty, above-mentioned weighting strategies can be better rationalised and further comprehended. First, the weighted generalization error 8 is defined as follows: where the non-negative weighting function ω(x) is defined over the entire sample space Ω, and δ e is the irreducible noise.

Propositions
Both the bias and the variance terms will change when the weighting strategy is used on samples as shown in Eq. (21). Thus, a special case is first analyzed.
Proposition 1 Assume that BiasT (λ h ) and V arT (λ h ) change. Let BiasT (λ h ), V arT (λ h ), and Err(λ h ) be the new bias, variance terms, and the generalization error, respectively. If the partial deviation of Err(λ h ) on the current c * is negative, then the new optimal model complexity c * will be larger then c * , and vice the versa.
The proof is contained in Section B.1. in Appendix. The proof is simple and omitted.
Proposition 3 Consider a sample region Ω r ⊂ Ω in which the value of LDC for each sample in Ω r is larger than one. If a constant weight ω larger than one is placed on each sample of Ω r and the weights of other samples in Ω remain one, then the new optimal model complexity will become larger.
The proof is contained in Section B.2. in Appendix. This proposition is in accordance with the idea that when the weights of hard samples are increased, the learned model will become more complex than the original model. Based on this proposition, we could extend a corollary more generalized.
Corollary 1 Consider a sample region Ω r ⊂ Ω whose learning difficulty coefficient LDC for each sample in Ω r is larger than one. If a weight larger than the original weight is placed on each sample in Ω r , and the weights on other regions remain unchanged, the new optimal complexity will become larger.
The proof is contained in Section B.3. in Appendix.
Proposition 4 Consider a sample region Ω r ⊂ Ω whose value of LDC for each sample in Ω r is smaller than one. If a constant weight larger than one is placed on each sample of Ω r , and the weights of other samples in Ω remain one, then the new optimal model complexity c * will become smaller.
The proof is similar to that for Proposition 3 and Corollary 1 and omitted. In numerous weighting strategies, the rationale is to modify the contributions of easy, medium, and hard samples. Therefore, the following propositions are presented.
Proposition 5 Assuming that the original weight of each sample is ω 0 (x). Let ω(x) = u(LD(x)) be a new weighting function for a sample x. If u is non-decreasing and satisfies that 0 ≤ min ω(x) < max ω(x), then the new optimal complexity is larger than the original optimal complexity.
The proof is contained in Section B.4. in Appendix.

Corollary 2
Let Ω e , Ω m , and Ω h be a trichotomy for the whole space Ω, and they represent the regions for easy, medium, and hard samples, respectively. Let ω(·, ·) be a region weighting function over the three data regions, and assume that the weights in each region are identical for each sample. Note x ∈ Ω e ; x ∈ Ω m ; x ∈ Ω h . If ω(x) ≤ ω(x ) ≤ ω(x ) and ω(x) < ω(x ) hold, then the new optimal complexity will become larger.
The proof is simple and omitted. ELDD Proposition 6 Assume that the original weight of each sample is ω 0 (x). Let ω(x) = u(LD(x)) be a weighting function for a sample x. If u is non-increasing and satisfies that 0 ≤ min ω(x) < max ω(x), then the new optimal complexity is smaller than the original optimal complexity.

Corollary 3
Let Ω e , Ω m , and Ω h be a trichotomy for the whole region Ω and they are the regions for easy, medium, and hard samples, respectively. Let ω(·, ·) be a region weighting function over the three data regions, and assume that the weights in each region are identical for each sample. Note x ∈ Ω e ; x ∈ Ω m ; x ∈ Ω h . If ω(x) ≥ ω(x ) ≥ ω(x ) and ω(x) > ω(x ) hold, then the new optimal complexity will become smaller.
Propositions 1-6 and the associated corollaries are about the weighting on generalization errors and also the losses. They establish a theoretical framework for the analysis of the learning difficulty-aware weighting strategies in learning.

Explanations for Several Classical Methods
We rationalises several typical learning methods which assign weights on samples based on learning difficulties 9 .

Adaboost
Adaboost is a classical ensemble learning algorithm. In each epoch, it learns a new model based on the updated weights on samples defined as follows: where ω t i is the weight in the t th epoch, z t−1 is a normalized factor, f t−1 is the learned weak classifier in the (t − 1) th epoch, and α is a positive weight for f t−1 . According to Eq. (22), if x i is mis-predicted by f t−1 , then the weight of x i will become larger in the next epoch. If x i is correctly predicted by f t−1 , then the weight of x i will become smaller in the next epoch. In essence 10 , the weight in Eq. (22) can be written as follows: 9 It should be noted that the difficulty measures in these methods are not equal to our proposed theoretical measure. Nevertheless, we assume that their employed measures are in accordance with ours in their contexts to facilitate further theoretical investigation. 10 Indeed, the LDC(xi) can be seen as being approximated by exp(yif (xi)) in Adaboost. where Obviously, u(LD(x i )) is an increasing function over learning difficulty. According to Proposition 5, the new model complexity becomes larger than the original one. Specially, the learned new classifier f t is more complex than that in the (t − 1) th epoch if the learner is not as simple as the decision trump. Therefore, the new classifier and the whole ensemble classifier become more complex with the increase in epoch.
Two aspects determine the complexity of the final ensemble model greatly: • Power of the basic model. If the basic model has strong classifier, such as SVM, the learned model will become highly complex with the increase in epoch and overfitting is inevitable. A weak learner can avoid this situation. • Number of maximum epochs. If the maximum epoch is large, then the ensemble model in the last few epochs will become highly complex when noises exist. Accordingly, overfitting may occur.
A natural improvement is that high weights above a threshold are restricted. This condition makes the model less complex. A famous modification with solid theoretical basis is soft margin boosting [74]. The weight is calculated as follows: where C(≥ 0) is a hyper-parameter, ζ t−1 i is the average weight of the i th sample up until the (t−1) th iteration, and b t−1 is a factor that reflects the classification performance in the (t−1) th iteration. If C > 0, then the above weight is smaller than the weight in Eq. (22) when the sample is often misclassified up until the (t − 1) th iteration, and vice versa. Based on Corollary 1, on the contrary, the optimal complexity of the learned model based on the above weighting scheme will be smaller than that of the model based on Eq. (22).

SPL
SPL trains models from easy samples and adds hard samples with the increasing training epoch. Its objective function is as follows: where Θ is the model parameter, v i is the sample weight, and λ > 0 is a hyperparameter and increased with the epoch. Theoretically 11 , the weight in SPL is defined as follows In each new epoch, the weights of some hard samples are changed from zero to one with the increase in λ. According to the Corollary 1, the optimal model complexity will become larger. Alternatively, SPL obtains simple models in the initial epochs and gradually yields complex models.

Focal loss
Focal loss assigns each sample a weight as follows: where p i,yi is the estimated SoftMax value of x i on the ground-truth label in the current model, and γ is positive. The motivation of Focal loss is to exert (relatively) larger weights on hard samples than simple ones. Focal loss utilizes the value of 1 − p i,yi as an indicator of learning difficulty. To better understand Focal loss, we first theoretically define a weight: According to Proposition 5 and Corollary 2, the new optimal complexity will be increased. We further obtain the following conclusion: The larger the value of γ, the larger the optimal complexity will be, i.e., ∀γ 1 < γ 2 , c * (γ 1 ) < c * (γ 2 ).
The proof is similar to that for Proposition 4. Alternately, γ controls the model complexity. Consequently, if γ is quite large, then the learned model will be quite complex which affects the generalization capability of the model. If γ is smaller than zero, then the learned model will be simpler than the learned model when no weights are used (i.e., γ = 0). Fig. 6 shows the curves of Focal loss when γ is searched in {−4, −3, −2, −1, 0, 1, 2, 3, 4}. Corollary 4 is also supported by the empirical observations [11] shown in Fig. 7. A small(large) γ will result in under-fitting(over-fitting).
Focal loss is actually the strategy that uses the weight in Eq. (28) to approximate the weight defined in Eq. (29):

Remark 1
The proposed propositions and corollaries in Section 5.1 are in accordance with intuitions on the model complexity variations when applying weighting for learning. The explanations for the three classical methods are also reasonable and partially supported by empirical observations as shown in Fig. 7. The above analysis and explanations support the rationale of our proposed learning difficulty theory.

Experiments
As previously mentioned, learning difficulty is heavily affected by the data quality, sample margin, uncertainty, and category distribution. Therefore, four different scenarios are designed to evaluate the effectiveness of the proposed practical measure.

Measurement under Noise Detection
Two benchmark image classification data sets [36], namely, CIFAR10 and CIFAR100 are used. There are 10 classes in CIFAR10 and 100 classes in CIFAR100. On both sets, there are 50,000 images for training and 10,000 images for testing. The test images are used as the validation data for CIFAR10 and CIFAR100. In this scenario, noises contain two types. The first type is noisy labels (y), while the second consists of noisy images (x). The competing methods are as follows: • Loss. The losses for each sample in the epoch with the highest validation accuracy are used for measurement. • Average loss (AveLoss). The average values of losses of the last 100 epochs are used for measurement. • O2UNet [33]. As previously introduced, this method adopts a cyclical training procedure and the average loss of each sample in the procedure is used. • MentorNet [34]. This method pertaining to curriculum learning, uses the output weights of the teacher network with the highest accuracy on the validation set to present the possibility of being correct. A smaller weight indicates the sample is more difficult to learn. • Co-teaching [28]. Two networks are trained. For each sample, the smaller one of the two losses given by the two networks is regarded as the learning difficulty. • Variance of gradients (VOG) [2]. This method relies on the variances of the gradient norms of each sample cross different training epochs. A high VOG value indicates a large difficulty for a sample. • Our proposed method GELD. The detailed steps are presented in Algorithm 1.
In the methods of Loss, AveLoss, O2UNet, VOG, and our GELD, ResNet-34 [30] is used as the base network. The hyper-parameters of ResNet-34 used in [30] are followed. Specifically, the batch-size is 128, the SGD optimizer has a momentum of 0.9, and the weight decay is 1e-4. The learning rate of the first 40 epochs is 0.1 and is multiplied by 0.1 for every 40 epochs. Each model is learned for 200 epochs. The default settings of MentorNet and Co-teaching are borrowed from the corresponding papers [28,34]. O2UNet and VOG contain specific hyper-parameters other than those of ResNet-34. These parameters follow the setting in the original paper [2,33]. In our GELD, K and M are set as 5 and 6 respectively, for GELD, except for the part E (the discussion of the impact of (K, M ) value). The tuning factor µ of GELD is set as 1.
Let v be the noise rate. The result evaluation scheme used for O2UNet [33] is followed. In each method, the top-50000 * v * r samples are selected as its detected noisy samples according to its estimated difficulties, where r ∈ {0.8, 0.9, 1, 1.1, 1.2}. Then, the whole detection is repeated three times for each method and the average F1 values on the detection results are calculated and compared. A high F1 value indicates a good performance in noisy label detection and thus the learning difficulty measurement.

Noisy Label Detection
Two sub-types of noises are used, namely, symmetric and pair-flip. The symmetric noise describes mislabeling to each other classes of equal possibility. In pair-flip, labelers may make mistakes only within very similar class. The noise rate is set as 20%, 40%, and 60%, respectively. The detailed noise setting in [28] is followed. Figs. 8 and 9 show the detection performances of the competing methods on CIFAR10 and CIFAR100, respectively. Our proposed approach GELD achieves the highest F1 values in most cases. Although O2UNet outperforms GELD under the symmetric noise sub-type on CIFAR100 (Figs. 9(a), (b) and (c)), its performances are quite poor under the pair-flip noises. The performance of the widely-used method Loss is poor and it achieves the worst F1 scores in several cases. Loss is not an ideal measurement for the easy and hard samples even though it does not require additional computational cost.
In our approach GELD, µ can be tuned. Table 1 shows the performance variations of GELD under the pair-flip noise sub-type and different values of µ in Eq. (20). When the value is larger than one, higher F1 values are achieved. These results reveal the importance of the variance term during the evaluation of the learning difficulty.

Noisy Image Detection
In this experiment, salt-and-pepper noises are leveraged [22]. The noise is simulated by adding white (salt) or black (pepper) noises into the original RGB ELDD  images with a parameter of signal-to-noise ratio (SNR). In our experiment, the SNR is set as 0.4 for each image. Fig. 10 shows an example for nosiy images with different SNR levels. The noise rate on the whole data is set as 20% and 40%, respectively.    11 shows the performances of the competing methods on CIFAR10 and CIFAR100, respectively. The settings of competing methods remain unchanged compared with the label noise experiments. Our method GELD still achieves the highest F1 values under all the noise rates. Few noisy data were detected by methods that rely merely on the loss.

Measurement under Small-margin Data Detection
A sample with a small margin (the distance to the oracle decision boundary) is considered to be hard in learning [68]. This experiment evaluates a learning difficulty measure in terms of the detection of small-margin samples.
In this experiment, four UCI [8] data sets are used, namely, Iris, Mammographic, Haberman, and Abalone. To better construct the ground-truth, only binary classification is considered. Only two categories are selected for both Iris (the "Setosa" and "Versicolour" categories) and Abalone (the "9" and "10" categories). Mammographic and Haberman contain only two categories. The details of used data in this experiment are presented in Table 2. The classical margin-based learning method SVM [16] is used to construct the ground truth, i.e., the small-margin samples. Specifically, the SVM with RBF kernel is used. Two parameters C and g are searched in {10 −3 , 10 −2 , 10 −1 , 1, 10, 10 2 , 10 3 } and {10 −3 , 10 −2 , 10 −1 , 1, 10, 10 2 , 10 3 }, respectively, via five-fold cross-validation. The optimal parameter setting is used and the SVM is trained on the whole training set. Constantly, the margin of each sample is calculated as the groundtruth difficulty. The margin is yf (x) for the sample x, where y is the label and f (x) is the output of the kernel SVM. Let N be the #Instances. The top-N * v samples with small margins are selected as the ground-truth samples to detect. ELDD Table 2 Details of the four UCI data sets. Iris  4  2  100  Mammographic  5  2  961  Haberman  3  2  360  Abalone  8 2 1323 Fig. 12 Histograms of F1 scores (%) under various data sets using margin as ground-truth.

Data set #Dimensions #Classes #Instances
As the base network ResNet-34 is inappropriate in this experiment, a three-layer perception with the Sigmoid activation function is used as the base network. The number of epoch is set as 10000. Its hyper-parameters are also pursed via five-fold cross-validation. Considering that MentorNet and Coteaching are quite complex for this scenario, they are not compared in this experiment. The competing methods include Loss, AveLoss, O2UNet, and our GLED. The evaluation criteria and the whole calculate scheme follow the setting in the previous experiments. The value of v is set as 20%, 40%, and 60%, respectively; r is set as one.
The results are shown in Fig. 12. Our approach GELD achieves the highest F1 values on all data sets. In addition, GELD is stable across different vs and different data sets. By contrast, the other methods are not stable.

Measurement under Epistemic Uncertainty Detection
In this experiment, a data corpus containing epistemic uncertainty is required. An image aesthetic assessment data corpus, namely, AVA benchmark image aesthetic data corpus [49], is then utilized and each photo receives multiple rating scores from multiple different users. The variance of user rating scores of a photo reflects the epistemic uncertainty on the photo using each user as a gold model. A large variance indicates a large uncertainty for a photo. Specifically, the former 50,000 samples in the AVA corpus are downloaded and each sample receives 210 rates on average counting from 1 to 10.
We use ResNet-101 as the base network as the image quality of AVA is much higher than CIFAR10 and CIFAR100. Given that the Bayesian Neural Network (BNN) [67] is particularly designed for modeling uncertainty, we import BNN as one of the competing methods, and its outputting confidence coefficient is used to detect uncertain photos. Therefore, the competing methods include Loss, AveLoss, O2UNet, BNN, and our GELD. The top-50, 000 * v photos with high uncertain scores are taken as the objective samples to detect.
The v values are set as 20%, 40%, and 60%. The r value is set as one. In the BNN method, the dropout strategy described in [67] is followed. The parameter setting of ResNet-101 reported in [30] is adopted. The photos are resized into shape of (3,192,192) to fit in the ResNet-101. Table 3 shows the F1 scores of the competing methods in high uncertain sample detection. GELD still performs the best and slightly outperforms BNN. The rest of the three methods poorly perform in this detection task. Fig. 13 shows the top-5 high uncertain photos and the top-5 photos detected by our GELD approach. The aforementioned figure (Fig. 14) also shows the last five photos with small uncertainty and the last five photos detected by our GELD.

Measurement for Imbalance Data
The long-tail versions of the CIFAR10 and CIFAR100 are used in this experiment. Buda et al. [13] compiled a series of data sets under different imbalance ratios. The two data sets under the 20 : 1 ratio for CIFAR10 and CIFAR100 are used. There is no ground-truth information for the learning difficulties because the head categories can also contain difficult samples. Consequently, we only plot the histograms of the numbers of hard samples detected by the competing methods in the head and tail categories. The competing methods are Loss, AvgLoss, O2UNet, VOG, and our proposed GLED. The base network and the concerning setting in part A are followed.
The top-40% samples detected by each competing methods are regarded as their detected hard samples. Figs. 15 and 16 show the histograms of the detected hard samples by each method on CIFAR10 and CIFAR100 (the top five head categories and the last five tail categories), respectively. All the competing methods identically behave on the tail categories on both data corpora. ELDD  This condition is reasonable and accords well with the primary motivation for imbalance learning that samples in tail categories are hard to learn. There are slight differences between our GELD and other competing methods on the head categories. The numbers of hard samples detected by GELD are larger than those of other methods, which is reasonable because head categories still contain hard samples.

Discussion
The above experiments on the four scenarios, namely, noise detection, small-margin sample detection, uncertain sample detection, and hard sample detection in imbalance learning, verify the superiority of the proposed GELD  approach over existing classical and state-of-the-art methods. As previously introduced, the primary difference between GELD and many existing methods lies in that GELD explicitly considers variances. Fig. 17 shows the histograms of the bias values and the variance values achieved by GELD on clean samples and label noisy samples under both pair-flip and symmetric noise types on CIFAR10. The variance values between clean and noisy samples are also considerably distinct as shown in Figs. 17 (b) and (d), which demonstrates the usefulness of the variance term utilized in our GELD method. In addition, the difference consist in histograms of noisy and clean samples under the pairflip noises is trivial, which rationalises the poor performances of the loss-based methods such as O2UNet.
Although good results are achieved, GELD is only an appropriation for theoretical difficulty in Definition 1. We evaluate the robustness of the method ELDD   in terms of the variations on the two key parameters, namely, K and M . Table  4 shows the performances of pair-flip noise detection (r = 1) on CIFAR10 and CIFAR100. The results show that the performances of GELD are stable when the value of (K, M ) is set in {(4, 5), (5,6), (5,8), (5, 10)}. We are interested in whether a simple model can also obtain better results. A simple network, namely, AlexNet [37], is used as the basic leaner in pair-flip noisy label. The base network and setting of other methods follow the previous setting of the corresponding experiments in part A. The training setting of AlexNet in [50] is followed, and the output-size is modified into 100 while training CIAFR100. The results are shown in Table 5. GELD (AlexNet) is inferior to GELD (ResNet-34). However, it is comparable to Co-teaching and outperforms the rest of the methods. A large real-world data set, namely, Clothing1M [36], is used to further evaluate the performance of our GELD measure in terms of image classification. There are 14 classes in Clothing1M containing 1,000,000 training images with real noisy labels, 48,000 training samples verified to be clean, and 10,000 testing images. The 48,000 clean training samples are used as the validation data for Clothing1M. Clothing1M has a noise proportion of 38% approximately. ResNet-101 is used and the settings of the network in [33] are employed. (K, M ) are set as (50,50). Each model is learned for 50 epochs for GELD. The model is selected using the 48,000 clean training samples. The learning rate remains constant as 1e − 6. The batch size is set as 16 during the GELD calculation. Other hyper-parameters follow the settings in [33]. The top 10% samples with the highest Err(x i , λ h ) values are removed as detected noisy samples. Remaining samples are used to learn the final image classifier. The batch size is set as 128 and the maximum epoch is set as 10 during this procedure. The settings of other methods in [33] are followed. Table 7 shows the comparison of classification accuracies (%) among the four competing methods. GELD outperforms the other three methods. Results of methods beside GELD are directly from the O2UNet study [33].
The computational cost of GELD is relatively high as K * M models should be trained. However, it is still smaller than another SOTA method O2U-Net. Moreover, several ways can significantly reduce the complexity. First, the task can be performed in parallel. Four NVIDIA GeForce RTX 3090 GPUs are used in our experiments. The average time costs for our GELD using different number of GPUs on CIFAR10 using ResNet-34 as base network are shown in Table 6. The settings follow the pair-flip label noise experiments' in part A with (K, M ) is set as (5,6). The time consumption is considerably reduced when GELD is run on more GPUs in parallel. The time cost of O2UNet is also large. More over, O2UNet cannot be performed in parallel. Second, a relatively small training set instead of the entire can be used when dealing with large corpora. Third, a dropout-based strategy (like the quantifying uncertainties in BNN) can also reduce the time cost. To sum up, the time complexity of GELD doesn't hinder its applications based on these strategies. Although four key factors, namely, data quality, sample margin, uncertainty, and category distribution, are summarized and the proposed method achieves quite competing performance, a directly theoretical connection between the four factors and the learning difficulty is not established in this study. We leave this theoretical investigation as our future work.

Conclusion
This study has conducted a comprehensive investigation on learning difficulty of data in machine learning. We established a theoretical definition of learning difficulties of data based on the bias-variance trade-off on generalization error. The well discussed and explored concepts, easy and hard samples, are formally described based on the theoretical definition and the associated difficulty coefficients. Influential factors of learning difficulty are summarized and correlations between generalization error, model complexity, and influential factors are surveyed and analysed. A practical measure, namely, the generalization error-based learning difficulty (GELD) measurement, is then proposed in virtue of influential factors to calculate the learning difficulty of each training sample. Finally, the properties of the weighted learning strategy are presented and three classical methods are explained on the basis of the theoretical formalization. Extensive experiments validate the effectiveness of our proposed measure, which outperforms existing state-of-the-art methods under different scenarios considering concluded influential factors.
This study conducts an attempt to establish a theory for learning difficulty of samples. Our future work aims to reveal the mathematical correlations between the theoretical definition (i.e., optimal model complexity) and the measure (i.e., generalization error) for learning difficulty.

Declarations Funding
Not applicable.

Conflict of interest
We declare that we have no financial and personal relationships with other people or organizations that can inappropriately influence our work, there is no professional or other personal interest of any nature or kind in any product, service and/or company that could be construed as influencing the position presented in, or the review of, the manuscript entitled.

Ethics approval
Not applicable.

Consent to participate
Not applicable.

Consent for publication
Not applicable.

Availability of data and materials
The data sets used or analysed during the current study are available from the corresponding author on reasonable request. All data generated or analysed during this study are included in this published article.

Authors' contributions
Wu Ou contributed to the conception of the study; Wu Ou and Zhu Weiyao contributed significantly to analysis and manuscript preparation; Zhu Weiyao performed the experiment; Su Fengguang performed the data analyses and wrote the manuscript; Deng Yingjun helped perform the analysis with constructive discussions.
The model complexity used in this study is on the basis of minimum description length (MDL) [9] and the Kolmogorov complexity [41]. MDL and Kolmogorov complexity are combined and used to describe the model complexity under various learning tasks in [19].
Let w = (w 1 , .., w d−1 ) T be the model parameter of a regression model where d signifies the dimension of inputs. Let p(w) be the probability density of w. According to MDL, the model complexity expectation c(w) is the expectation of model complexity m(w) = − log p(w), over different training set T , i.e., c(w) = E T [m(w)]. Suppose that each component of w is independent to each other and follows the identical Gaussian distribution w i ∼ N (0, σ 2 ). Therefore, the model complexity defined on the basis of MDL equals to When the construction of the basic learner and σ 2 is fixed, the model complexity only concerns w 2 2 .
Under the ridge regression, with the input denoted as x and its label denoted as y, the objective function is L = N n=1 l(f (x; w), y) + λ w 2 2 , and the estimated parameters are given bŷ w(λ) = (x T x + λI) −1 x T y.
Based on the Assumption 1, the variance term is an increasing function with respect to the model complexity, and as the loss function normally used during the training procedure is in fact the bias term in the bias-variance trade-off, the generalization error can be estimated by the following form: Accordingly, an enlargement of λ leads to a reducing of w 2 2 , and moreover, a lower model complexity. The above analysis indicates that the MDL-based model complexity well explains the ridge regression. However, the former calculation is based on the identical distribution assumption for each w i . When the model is a polynomial function, the contributions of each component of w to the whole model complexity are not identical. For example, when using a polynomial function g(x) ∼ O(3) to perform ridge regression, w 3 should contributes more to the model complexity comparing to w 0 . Therefore, an identical distribution for all components of w is unreasonable. A more reasonable assumption is that w i ∼ N (0, σ 2 i ) with the condition that σ 2 i < σ 2 j if i > j. From Eq. (A.1), we have m(w) = − log p(w) In our practical calculation, let σ 2 i = ( Given M training sets, the model complexity expectation is

B.1 Proof of Proposition1
Proof According to Assumption 1, the partial derivatives of the generalization error with respect to c is negative before the generalization error achieve the minimum. Accordingly, if ∂Err(λ h ) ∂c | c=c * < 0, then c * should be larger than c * .
According to Proposition 1, the new optimal model complexity c * will be larger than c * .

B.3 Proof of Corollary1
Proof The optimal complexity c * under the original weights ω can be theoretically inferred under the (original) weighted distribution P 1 ∼ ωP . The learning with new weightsω equals to the learning with the weightsω/ω for each sample in Ω r under the distribution P 1 . Because the new weights are larger than the original weights on Ω r ,ω/ω is larger than one on Ω r . According to Proposition 3, the new optimal complexity becomes larger.