Title: DIME: AN INFORMATION-THEORETIC DIFFICULTY MEASURE FOR AI DATASETS

Abstract: Evaluating the relative difficulty of widely-used benchmark datasets across time and across data modalities is important for accurately measuring progress in machine learning. To help tackle this problem, we propose DIME, an informationtheoretic DIfficulty MEasure for datasets, based on conditional entropy estimation of the sample-label distribution. Theoretically, we prove a model-agnostic and modality-agnostic lower bound on the 0-1 error by extending Fano's inequality to the common supervised learning scenario where labels are discrete and features are continuous. Empirically, we estimate this lower bound using a neural network to compute DIME. DIME can be decomposed into components attributable to the data distribution and the number of samples. DIME can also compute per-class difficulty scores. Through extensive experiments on both vision and language datasets, we show that DIME is well-aligned with empirically observed performance of state-of-the-art machine learning models. We hope that DIME can aid future dataset design and model-training strategies.

1. INTRODUCTION:

Empirical machine learning research relies heavily on comparing performance of algorithms on a few standard benchmark datasets. Moreover, researchers frequently introduce new datasets that they believe to be more challenging than existing benchmarks. However, we lack objective measures of dataset difficulty that are independent of the choices made about algorithm-and model-design. Moreover, it is also hard to compare algorithmic progress across data modalities, such as language and vision. So, for instance, it is difficult to compare the relative progress made on a sentiment analysis benchmark such as the Stanford Sentiment Treebank (SST) (Socher et al., 2013) and an image classification benchmark, like CIFAR-10 (Krizhevsky, 2009) . With these challenges in mind, we propose a model-agnostic and modality-agnostic measure for comparing how difficult it is to perform supervised learning on a given dataset.

Intuitively, assuming that dataset examples are sampled i.i.d. from a static true distribution, we argue that the difficulty of a dataset can be decoupled into two relatively independent sources:(a) approximation complexity, the number of samples required to approximate the true distribution up to certain accuracy, and (b) distributional complexity, the intrinsic difficulty involved in modeling the statistical relationship between the labels and features.

We focus our analysis on the second source of the intrinsic difficulty in supervised learning, where both features and labels are available. To provide a model-agnostic measure, we turn to the information-theoretic approach. Indeed, there already exist lower bounds on the lowest possible errors given the distribution of the data. If both the samples and labels are discrete, Fano's inequality suggests the probability of 0-1 error is bounded by terms related to the conditional entropy H(Y |X), where X is the random variable representing the features and Y is the label. When both the features X and label Y are continuous, results on differential entropy also suggest the expected L 2 error is lower-bounded. However, in most of the supervised learning datasets where the features are continuous and the labels are discrete, it is unknown how the lowest possible error can be controlled regardless of models.

In this paper, we show that even for the hybrid case where labels are discrete and features are continuous, with some additional assumptions, Fano's inequality still holds. Moreover, we show that the lowest possible probability P e of the 0-1 error for a given data distribution is lower bounded We emphasize that even though our lower bound is model-agnostic, the proposed estimator is based on a neural network. However, we empirically show that, for most image and natural language datasets, a multilayer perceptron-based estimator produces a measure that effectively captures the difficulty of the data and aligns well with the performance of state-of-the-art models.

Related Work: Although conditional entropy and mutual information estimation have been extensively studied, research has focused on purely discrete or continuous data. Nair et al. (2006) were among the first to study the theoretical properties for the case of mixture of discrete and continuous variables. Ross (2014) , Gao et al. (2017) and Beknazaryan et al. (2019) proposed approaches for estimating mutual information for the mixture case based on density ratio estimation (e.g.,binning, kNN or kernel methods), which is unsatisfactory for high dimensional data such as image and text. We use neural network estimation (Belghazi et al., 2018) to avoid these issues. More importantly, we are the first to connect the hybrid conditional entropy with the lowest classification error and are able to use it as a difficulty measure for datasets.

2. DESIGNING A DATASET DIFFICULTY MEASURE:

For supervised learning across data modalities such as images and text, data samples can usually be viewed as feature-label pairs (x, y) where x ∈ X ⊂ R dx , and y ∈ Y. We focus on classification problems where the labels y are discrete, i.e., Y ⊂ Z + . We denote the joint distribution of the feature-label pairs as P X Y . The marginal distributions of the features and labels are denoted as P X and P Y respectively. We make the following widely adopted assumption from learning theory literature about how samples are generated: Assumption 1. The feature-label pairs (x, y) in the datasets, both training and testing, are sampled i.i.d. from a static distribution (x, y) ∼ P X Y .

Intuitively, there are many possible indicators for the potential difficulty of a dataset: the number of features, the number of classes, the number of samples, the distinguishability of samples across classes, as well as the difference between the data distributions of the training set and the testing set. However, none of these indicators alone can fully describe the relative difficulty of a dataset.

From Assumption 1, if the samples (x, y) are sampled i.i.d. from P X Y , where Y is discrete, a natural measure that characterizes the difficulty of the data distribution is the best probability of the 0-1 error that can be achieved by any estimator.

Definition 1 (Model-Agnostic Error) .

P e = inf f P x,y∼P X Y [f (x) = y]

The measure 1 is straightforward, but unfortunately it is hard to compute since it involves evaluations against all possible estimators. However, with mild assumptions, it can be lower bounded by terms related to the conditional entropy, which is much easier to evaluate.

2.1. DISCRETE FEATURES:

In the case where the features x ∈ X are discrete, according to Fano's theorem, P e is lower bounded: Fano's inequality. If both X and Y are discrete random variables, then P e ≥ H(Y |X)-1 log |Y| , where |Y| is the cardinality of the label set Y, and H(Y |X) is the conditional entropy.

However, even though data can be represented using discrete integers, treating the features as discrete random variables leads to the following difficulties:

1. The cardinality of the feature space becomes extremely large if discrete features are used. For image data, since each pixel is represented as an integer, the (raw) feature dimension would become the number of pixels in the image, which can be extremely large. Similarly, for language data, when the sequence length is long, the feature dimension becomes large very quickly. 2. Given the large feature space, finding a matching set of features between training and testing data from the limited number of training and test samples would be unlikely. As a result, probability mass estimation on each discrete value would be impractical, since we may only see at most one sample for each discrete configuration.

2.2. CONTINUOUS FEATURES:

As opposed to treating the features x as discrete random variables, if we view them as i.i.d. samples from a continuous distribution with probability density p x , we can estimate the conditional entropy H(Y |X) under some smoothness assumptions and also infer the model-agnostic error P e .

However, classical Fano's inequality only holds for discrete random variables. For the case with the continuous features and discrete labels, it has not been shown how P e can be controlled. In this paper, we prove a generalized version of Fano's inequality that holds for the continuous-featurediscrete-label scenario. Formally, for the continuous-X-discrete-Y case: Definition 2. Hybrid Conditional Entropy

EQUATION

where

P(Y = y|X) := E[1(Y = y)|X].

This definition of H(Y |X) is consistent with the classical definition, in the sense that both of them give the intuition that how much information or uncertainty is left for Y given X.

Next, to connect P e and the hybrid H(Y |X), we introduce an assumption on the function f Definition 3. Smooth Discretization Property: The function f : X → Y satisfies the smooth discretization property if for every y ∈ Y, almost every x ∈ X (x a.e. in X ),

f (x) = y ⇐⇒ ∃δ > 0 s.t. ∀x ∈ B δ (x), f (x) = y, where B δ (x) := {x ∈ Ω : x -x 2 < δ} is a δ-neighborhood of x in X .

This assumption on the classifier function f is not unnatural considering f maps a continuous variable to a discrete variable. Without this assumption, it would be extremely hard to quantify the population error probability P (f (X) = Y ) since the behavior of f may be erratic. Furthermore, in the real data setting, this assumption is always satisfied for every classifier f , as we can always construct a small enough neighborhood of each data point such that they are disjoint and assume f is a constant in each neighborhood. In this sense the assumption on f is pretty minimal. Now we are ready to extend Fano's inequality: Theorem 1. Fano's Inequality for Continuous Features: Let P e be the minimum error probability, i.e.,

P e = inf f P (f (X) = Y )

where f is any estimator of Y based on the observation X that satisfies the smooth discretization property. Then we have

H(P e ) + P e log(m -1) ≥ H(Y |X),

(2) where H(P e ) := -P e log P e -(1 -P e ) log(1 -P e ).

3. ESTIMATING THE LOWER BOUND:

It is natural to consider P e defined in Theorem 1 as a measure of dataset difficulty. Unfortunately, direct estimation of P e is impractical since one has to evaluate the estimation error against all possible estimators. However, theorem 1 provides an alternative towards estimating a lower bound on P e through estimating the hybrid conditional entropy H(Y |X) defined in Equation (1).

3.1. CONDITIONAL ENTROPY ESTIMATION:

In real applications, direct calculation of hybrid conditional entropy H(Y |X) according to Definition 2 is impossible since P(Y = y|X) is unknown. However, similar to the conditional entropy for discrete random variables, the hybrid conditional entropy H(Y |X) can also be written as

H(Y |X) = H(Y ) - |Y| y=1 P (Y = y)KL(X|Y = y||X).

(3)

Please refer to Appendix A for a detailed proof of Equation ( 3). We also define the hybrid mutual information I(X; Y ), which is compatible with H(Y |X):

EQUATION

In some benchmark datasets with balanced classes (e.g., CIFAR-10 and MNIST),

H(Y |X) = log |Y| -1 |Y| |Y| y=1 KL(X|Y = y||X).

This indicates that if a dataset has more classes and the features for different classes are closer to each other on average, then H(Y |X) would be larger.

3.2. A VARIATIONAL KL DIVERGENCE ESTIMATOR USING NEURAL NETWORKS:

We now discuss the practical design of an estimator for KL(X|Y ). Even though there are nonparametric KL divergence estimators such as kNN based techniques (Noshad et al., 2017; Perez-Cruz, 2008; Wang et al., 2009) , they rely on some knowledge of the internal dimension of the data manifold. However, the internal dimension of the data manifold is usually much smaller than the dimension of the raw features and is hard to estimate. As an alternative, we design a neural networkbased estimator for KL divergence estimation, inspired by Belghazi et al. (2018) . The estimator is based on the following theorem:

Donsker-Varadhan representation. KL(P||Q) = sup T :X →R E P [T ] -log E Q [e T ]

(5)

If we parameterize the function T using a neural network, we obtain:

EQUATION

where θ represents the neural network parameters.

In our empirical evaluation, we optimize the empirical average instead of the expectation. However this may cause issues such as overfitting. To mitigate this issue, we split the data into separate training and validation sets. The neural network models are trained on the training set and the estimation is made using the validation set. See Algorithm 1 for details. 

3.3. DIME AS A DIFFICULTY MEASURE:

Given that we are using a neural network model to estimate the KL divergence between P(X|y) and P(X), according to Equation ( 6), KL(X|y||X) ≤ KL(X|y||X). As a consequence, the estimated mutual information I(X; Y ) ≤ I(X; Y ), which leads to a larger H(Y |X). In the end, DIME could be larger as compared to true lower bound on P e .

The caveat is that P e is defined as a model-agnostic measure, but we use a neural network model to estimate its lower bound instead. The hope is, if the function class of the neural network is large enough, the gap between KL(X|y||X) and KL(X|y||X) is small enough so that DIME won't deviate too much from the true lower bound of P e . We now describe our experiments for DIME using vision and language benchmark datasets.

4. EXPERIMENTS AND RESULTS:

We try to answer the following questions through our experiments: Is the neural net estimator tightenough? How does DIME align with the state-of-the-art benchmarks across modalities? What are the practical applications for DIME in evaluating machine learning progress?

4.1. DATA PREPARATION:

We evaluate the following image classification datasets: MNIST (LeCun et al., 1998) , Extended MNIST (EMNIST) (Cohen et al., 2017) , Fashion MNIST (Xiao et al., 2017a) , CIFAR-10 (Krizhevsky, 2009) , CIFAR-100 (Krizhevsky, 2009) , Tiny ImageNet1 , and SVHN (Netzer et al., 2011) . The EMNIST dataset has several different splits, which include splits by digits, letters, merge, class, and balanced. For a controlled evaluation study, we also add the PyTorch Fakedata dataset2 which contains 10-classes of randomly-generated 32 × 32 grayscale images.

Among natural language processing datasets, we investigate three supervised scenarios: sentiment analysis, text classification, and language modeling. For sentiment analysis, we analyze IMDb (Maas et al., 2011) , and Stanford Sentiment Treebank (SST) (Socher et al., 2013) . In the case of SST, we utilize both fine-grained labels (SST-5) and binary labels (SST-2). For the text classification task, we use the TREC dataset (Li & Roth, 2002) , AG News, DBPedia, as well as Yelp Review dataset (Zhang et al., 2015) . For language modeling task, we analyze the character level modeling for Penn Tree Bank (Marcus et al., 1994) .

For DIME estimation, we do not perform any preprocessing on the data except for simple rescaling. For image data we rescale all the pixel values to floats in [0, 1]. By data processing inequality (Cover & Thomas, 2012) , the rescaling will not cause any change on H(Y |X) and P e since the rescaling function is invertible.

4.2. CHOICE OF NEURAL NETWORK ESTIMATOR:

To estimate DIME for image datasets, we use a simple multi-layer perceptron (MLP) with residual layers with Rectified Linear Unit (ReLU) activation functions. The network has three hidden layers of 4096 neurons. For language datasets, we use an embedding layer of dimension 1500, followed by three layers of 256 hidden neurons with residual connections and ReLU activations. We found that a higher dimension of the embedding helps achieve a tighter bound. The embedding layer is initialized with a concatenation of five pretrained embedding vectors: GloVe-840B-300d, GloVe-42B-300d, GloVe-twitter-27B-200d, GloVe-6B-300d, FastText-en-300d, and CharNGram-100d. The input sequences are truncated or padded to the length of 128. The MLP is operating on the token dimension instead of the embedding dimension to take the order of the sequence into consideration. For example, the first layer of MLP is 128-by-256 instead of 1500-by-256. The last fully-connected layer flattens everything into a vector and projects it to a scalar. For optimizing the MLP, we use SGD with initial learning rate of 0.1 and anneal it to 0.01 and 0.001 if the objective stops updating. We use the test set as evaluation set, as described in Algorithm 1. 

4.3. SANITY-CHECK EXPERIMENTS:

Experiments with toy datasets: We generate three two-dimensional 2-class toy datasets with 20,000 samples each with increasing level of difficulty (Figure 1 ). Samples in Toy Data 1 and Toy Data 2 are generated using random Gaussian variables by scaling differently in different dimensions and then by rotating, while the two classes in Toy Data 3 are simply uniform and Gaussian random variables. Toy Data 1, which is relatively easy to be separated, gets a DIME of 0.001. Toy Data 2, which is a bit harder due to a small overlapping region around the axis origin, gets a DIME of 0.013. And Toy Data 3, which is the hardest due to overlapping supports of the two class, gets a DIME of 0.263. In sum, DIME accurately reflects the relative difficulty of the toy examples.

Label corruption test: Next, we estimate DIME for the case of label corruption. If we assign random labels to a fraction of the training samples, intuitively the dataset should become more difficult. We experiment with five datasets with ten classes each-MNIST, Fashion MNIST, CIFAR-10, EMNIST (digits), and SVHN-and perform label corruption on their training sets in steps of 0.1 from 0 to 1. We observe a consistent increase in DIME across all the datasets with increasing label corruption (Figure 2 We evaluate DIME using popular image and language domain datasets for various classification tasks. In addition to dataset statistics, we report the estimated label entropy Y, the estimated hybrid mutual entropy (Eq. 4), the estimated hybrid conditional entropy H(Y |X) (Eq. 1), and DIME. We also report the state-of-the-art error on the dataset from recent literature (Wan et al., 2013; Huang et al., 2018; Cubuk et al., 2019; Yang et al., 2019; Patro et al., 2018; Cer et al., 2018; Melis et al., 2019) . From the results summarized in Table 1 , we make the following empirical observations:

First, DIME align well with the state-of-the-art results on the benchmark datasets, indicating that the relative difficulty of datasets is reflected in the performance of latest machine learning algorithms. However, notably, DIME is lower than the reported state-of-the-art error for all the variants of EM-NIST. This could indicate that since EMNIST is a relatively new, less-investigated dataset, we might see model performance improving over time.

Second, a larger number of classes lead to a higher value of DIME in general, which is expected given its dependence on H(Y ). But H(Y ) does not always dominate the value of the measure. For example, MNIST has 10 classes, but its DIME is much smaller compared to IMDb which has only two classes. This relative difference in difficulty of MNIST and IMDb is also reflected in their SOTA errors, validating our measure.

Third, we can also evaluate the relative difficulty of similar datasets introduced over time. For instance, Fashion-MNIST, which was designed to be more challenging than MNIST (Xiao et al., 2017b) , can be compared with MNIST on the basis of DIME. We find that Fashion MNIST is indeed more difficult than MNIST, though not as difficult as SVHN, indicating that with more exploration, we might see SOTA error approaching zero on Fashion MNIST.

Finally, for datasets such as MNIST, Fashion MNIST, EMNIST, FakeData, and DBPedia, DIME provides a tight error bound. But for certain datasets such as CIFAR-10, CIFAR-100, and Tiny ImageNet, DIME seem slightly pessimistic. As we discussed in Section 3.3, DIME could be larger than the true lower bound of P e since we constrain the function space to be a neural network model. While the relative order of difficulty suggested by DIME is reasonable, its large value also suggests than an MLP may not have enough capacity for accurate P e estimation. While it is an open question how to choose a model that is large enough to approximate P e yet easy to optimize, Equation ( 6) suggests that as the model size grows, the gap between DIME and true lower bound of P e becomes smaller. We verify this by calculating DIME with increasing number of neurons for a three-layer MLP. See Figure 5 in Appendix C for details.

4.5. ADDITIONAL USE CASES FOR DIME:

Dataset difficulty per class: Algorithm 1 can also estimate the relative difficulty of classes within a dataset. For this purpose, we simply rank the classes by their KL(X|y||X). A smaller value of KL(X|y||X) indicates the class is harder to classify. As examples in Figure 3 show, 'cat' and 'bird' are the most difficult classes in CIFAR-10, while 'automobile' and 'ship' are the easiest. In addition, 'shirt' and 'pullover' are the most difficult classes in Fashion MNIST, while 'sandal' and 'trouser' are the easiest.

Controlled Study with CIFAR Subsets: We obtain a 10-class subset from CIFAR-100 by choosing subclasses from the 'large carnivores' and 'large omnivores and herbivores' superclasses. These classes-bear, leopard, lion, tiger, wolf, camel, cattle, chimpanzee, elephant, and kangaroo-should be intuitively harder to classify as compared to CIFAR-10, which includes disparate classes such as bird, truck, and ship. Note that the image data for both of these datasets comes from the same, larger '80 million tiny images' dataset (Torralba et al., 2008) . We find that the DIME for this 10-class CIFAR-100 subset is 0.504, significantly larger than a DIME of 0.340 for CIFAR-10.

Effect of number of samples: With increasing number of samples, the empirical distribution of both training and testing tend towards the population distribution, making the distance between them smaller. It should also make the dataset easier, which is indeed reflected in a decreasing value of DIME with increasing number of samples (Figure 2-(right) ). But we also observe that our measure becomes stable with increasing number of samples. This suggests that our method can be used to estimate the relative difficulty of new datasets in domains where data is hard to collect (e.g., medical datasets, fine-grained image classification) and make determinations if additional data collection is required to make the problem easier to solve.

Effect of model size::

We investigate the effect of model size on DIME optimization. Equation ( 6) suggests that as the estimator model becomes larger, the gap between DIME and the true lower bound on P e should become smaller. We experiment with different sizes of MLP and find that DIME generally decreases with increasing number of neurons. However for easier datasets such as MNIST and Fashion MNIST, DIME stabilizes fairly quickly. See Figure 5 from Appendix C for details.

5. CONCLUSION:

We extend Fano's inequality to the case of continuous features and discrete labels and prove a modeland modality-agnostic lower bound on the 0-1 errors. We further design DIME, an empirical difficulty measure for datasets. We note that, even though our lower bound is model-agnostic, our estimator is based on a neural network and the estimates are affected by choices about the neural network design. Designing better estimators remains an avenue for future exploration. However, we hope that this work can aid dataset-design in the future and help objectively compare the progress in machine learning algorithms across modalities. We will release code for DIME estimation and DIME estimates for many common computer vision and natural language datasets to help further research.

A HYBRID CONDITIONAL ENTROPY:

Consider the usual classification setting, X, representing the feature, is a random vector in R p ; Y , representing the label, is a random variable(or vector) in {1, . . . , |Y|}. Assume X is a continuous variable with density p X (x) for x in some compact domain Ω ⊂ X ⊂ R p . Can we define a hybrid conditional entropy H(Y |X) while X is continuous and Y is discrete? We give a formal definition for this mixed-pair case and demonstrate that H(Y |X) defined in our way can be a good indicator for the hardness of classification on the data (X, Y ), which is consistent with the classical definition in the sense that both of them give the intuition that how much information or uncertainty is left for Y given X.

Our definition is

EQUATION

where

P(Y = y|X) := E[1(Y = y)|X]

. By the definition of conditional expectation (or probability), it is easy to check that Proof.

EQUATION

(i) This is trivial by (7), ( 9) and the fact that KL divergence is always nonnegative. (iii) Sufficiency: If Y is a function of X, then by assumptions, for any y 1 = y 2 , we have 

P (X ∈ Ω y1 , Y = y 2 ) ≤ P (X ∈ Ω y1 ) -P (X ∈ Ω y1 , Y = y 1 ) = 0.

Here, H(P e ) := -P e log P e -(1 -P e ) log(1 -P e ).

Proof. We basically follow the idea in the classical proof in Cover & Thomas (2012), although many details need to be dealt with carefully under our definition. Assume there exists a function f achieves the minimum error probability, i.e. P (f (X) = Y ) = P e (If such f doesn't exist, we can always find some f such that P (f (X) = Y ) ≤ P e + for some little > 0, then let → 0 we can get the same result). Define an error random variable,

EQUATION

Under our definition (7), we have (in what follows, we use the notation Y = i for i = 1, . . . , |Y| instead of Y = y to remind the reader that Y is discrete.)

EQUATION

It is easy to check that

EQUATION

where p(x|Y = i, E = j) is the conditional density function of X given Y = i, E = j. Similarly, one may check that 3 4

EQUATION

Combining the above two equations and (8), we have

EQUATION

Plug it in (17), and use the notation

EQUATION

we get

EQUATION

For any x ∈ Ω, i = 1, . . . , |Y|, we know ∃δ > 0, such that 1(Y = i). 4 For the consistency of the notations, we still use P(E = j|Y = i, X) to denote the right side of (19). So actually, one should understand P(E = j|Y = i, X) as P(E = j|Y = i, X)1(Y = i) in this context. Similar for P(Y = i|E = j, X) below.

EQUATION

For the case E = 1, we have C MODEL COMPLEXITY EXPERIMENT Equation ( 6) suggests when the model class is larger the gap between DIME and the true lower bound on P e becomes smaller. This is verified in our experiment shown in the middle of Figure ( 5), where we use neural networks with three hidden layers of varying number of neurons to calculate DIME. In the experiment we try 32, 64, 128, 256, 512, 1024, and 2048 neurons for each hidden layer. As the number of hidden neurons grows, DIME roughly decreases as expected. Still on CIFAR-10 the decrease is pretty monotonic. For simple datasets such as MNIST, Fashion MNIST and EMNIST (byletters) the numbers got stabilized pretty quickly.

EQUATION

:

https://tiny-imagenet.herokuapp.com/

https://github.com/pytorch/vision/blob/master/torchvision/datasets/ fakedata.py

Figures and Tables:

Figure 1: We propose DIME, a model-and modality-agnostic difficulty metric for datasets

Algorithm 1 DIME Initialize |Y| neural networks: T θ1 , T θ2 , . . . , T θ |Y| , one per class. Initialize class counters k 1 = 0, . . . , k c = 0, one per class. Initialize the sample counter k = 0. for t in 0, . . . , T do Draw a batch of b training examples {(x i , y i )}, and b evaluation examples {(x e i , y e i )}. for each class c ∈ {1, . . . , |Y|} do Find samples of the c-th class: S c = {i|y i = c}, S e c = {i|y e i = c} Train θ c = arg max θc 1 |Sc| Sc T θc (x i ) -log[ 1 b j exp T θc (x j )] Evaluate KL θc = 1 |S e c | S e c T θc (x e i ) -log[ 1 b j exp T θc (x e j )] If KL θc stops increasing, pause the training for T θc . Update counters: k c + = |S e c |. end for Update the sample counter: k+ = b If all neural networks stop updating, break. end for Estimate the class probability p c = kc k , c = {1, . . . , |Y|}. Calculate H(Y |X) using (3), p c , and KL θc , c = {1, . . . , |Y|}. Solve (2) and output the solution.

Figure2: DIME increases with increase in the amount of label corruption (left). DIME becomes reasonably stable as the fraction of samples from the dataset used for estimation increase (right).

Figure 3: DIME can rank classes within datasets for difficulty. A lower height of the bar indicates higher relative difficulty.

where p(x|Y = y), x ∈ R p is the conditional density function of X given Y = y. Denote p y := P (Y = y), we have We summerize some basic properties of H(Y |X) under our definition (7):Lemma 1. (i) 0 ≤ H(Y |X) ≤ H(Y ) ≤ log |Y|. (ii) H(Y |X) = H(Y ) ifand only if X and Y are independent. (iii) H(Y |X) = 0 if and only if Y is a function of X. That is, there exist |Y| subsets of Ω: Ω 1 , . . . , Ω |Y| such that P (X ∈ Ω y ∩ Ω y ) = 0 for any y = y ∈ {1, . . . , |Y|}, P (X ∈ ∪ |Y| y=1 Ω y ) = 1 and P (Y = y|X ∈ Ω y ) = 1 for any y ∈ {1, . . . , |Y|}.

ii) By (9), it is easy to getH(Y |X) = H(Y ) ⇐⇒ X|Y = y d == X, ∀y ∈ {1, . . . , |Y|}. ⇐⇒ P (X ∈ A, Y = y) = P (X ∈ A)P (Y = y),for any measurable set A in X , any y ∈ {1, . . . , |Y|}. ⇐⇒ X,Y are independent.

Figure 4: An example of f with Smooth Discretization Property given the data and classifier. Red points represent {xi , f 0 (x i )} 10 i=1 , x i ∼ U [0, 1],f 0 is some given classifier in practice.

)Let δ → 0, we have p(x|Y = i, E = 0)P (Y = i, E = 0) = p(x|Y = i)P (Y = i) or 0 for any x ∈ Ω and 1 ≤ i ≤ m. Therefore, by (19), we know P(E = 0|Y = i, X) is always 0 or 1 for any 1 ≤ i ≤ |Y|. So is P(E = 1|Y = i, X). Then by (21), we haveH(E|Y, X) = 0.(24)Similar to (22), we haveH(E, Y |X) = H(E|X) + H(Y |E, X), = i, E = j|X) log P(Y = i|E = j, X) that H(E|X) ≤ H(E) = H(P e ), it suffices to show H(Y |E, X) ≤ P e log(|Y| -1). (28)Similar to (23), we know for any x ∈ Ω, i = 1, . . . , |Y|, ∃δ > 0, such thatP (X ∈ B δ (x), Y = i, E = 0) = P (X ∈ B δ (x), E = 0), if f (x) = i 0, if f (x) = i. (29)Then we get P(Y = i|E = 0, X) is always 0 or 1 for any i = 1, . . . , |Y|. Therefore,H(Y |E = 0, X) := E XStrictly speaking, by the definition of conditional expectation or probability, we should have P(E = j|Y = i, X) = P (Y =i,E=j)p(X|Y =i,E=j) P (Y =i)p(X|Y =i)1(Y = i) + P (Y =i,E=j)p(X|Y =i,E=j) P (Y =i)p(X|Y =i)

to (20), we haveP(Y = i, E = 1|X) = P(E = 1|X)P(Y = i|E = 1, X). (34)Plug in the above two equations to H(Y |E = 1, X), we getH(Y |E = 1, X) = E X = 1|X)P(Y = i|E = 1, X) log P(Y = i|E = 1, X) = i|E = 1, X) log P(Y = i|E = 1, X) E X [P(E = 1|X) log(|Y| -1)] = P e log(|Y| -1).Therefore,H(Y |E, X) = H(Y |E = 0, X) + H(Y |E = 1, X)≤ P e log(|Y| -1).

-(left)). For some datasets such as MNIST, DIME is almost tight given the fraction of randomly corrupted labels. We evaluate DIME on vision and language datasets and rank them by relative difficulty.

Table content: <table><tr><td>Corpus</td><td colspan="5">#classes H(Y ) I(X; Y ) H(Y |X) DIME SOTA Error</td></tr><tr><td>Image Classification</td><td/><td/><td/><td/><td/></tr><tr><td>EMNIST (digits)</td><td>10</td><td>2.303 2.255</td><td>0.048</td><td>0.006</td><td>0.002</td></tr><tr><td>MNIST</td><td>10</td><td>2.301 2.192</td><td>0.109</td><td>0.015</td><td>0.002</td></tr><tr><td>EMNIST (letters)</td><td>26</td><td>3.258 2.872</td><td>0.386</td><td>0.054</td><td>0.056</td></tr><tr><td>EMNIST (bymerge)</td><td>47</td><td>3.554 3.098</td><td>0.456</td><td>0.060</td><td>0.190</td></tr><tr><td>Fashion-MNIST</td><td>10</td><td>2.303 1.912</td><td>0.391</td><td>0.066</td><td>0.033</td></tr><tr><td>EMNIST (byclass)</td><td>62</td><td>3.679 3.126</td><td>0.553</td><td>0.072</td><td>0.240</td></tr><tr><td>EMNIST (balanced)</td><td>47</td><td>3.850 3.212</td><td>0.638</td><td>0.089</td><td>0.095</td></tr><tr><td>SVHN</td><td>10</td><td>2.223 1.436</td><td>0.786</td><td>0.159</td><td>0.010</td></tr><tr><td>CIFAR-10</td><td>10</td><td>2.303 0.915</td><td>1.388</td><td>0.340</td><td>0.010</td></tr><tr><td>CIFAR-100-Subclass</td><td>10</td><td>2.303 0.503</td><td>1.800</td><td>0.504</td><td>N/A</td></tr><tr><td>CIFAR-100</td><td>100</td><td>4.605 1.239</td><td>3.366</td><td>0.585</td><td>0.087</td></tr><tr><td>Tiny ImageNet</td><td>200</td><td>5.298 0.692</td><td>4.606</td><td>0.768</td><td>0.268</td></tr><tr><td>FakeData</td><td>10</td><td>2.303 -0.003</td><td>2.306</td><td>0.900</td><td>0.900</td></tr><tr><td>Sentiment Analysis</td><td/><td/><td/><td/><td/></tr><tr><td>IMDb</td><td>2</td><td>0.693 0.224</td><td>0.469</td><td>0.178</td><td>0.038</td></tr><tr><td>SST-2</td><td>2</td><td>0.693 0.224</td><td>0.469</td><td>0.179</td><td>0.032</td></tr><tr><td>SST-5</td><td>5</td><td>1.573 0.230</td><td>1.342</td><td>0.470</td><td>0.356</td></tr><tr><td>Text Classification</td><td/><td/><td/><td/><td/></tr><tr><td>DBPedia</td><td>14</td><td>2.639 2.387</td><td>0.252</td><td>0.037</td><td>0.013</td></tr><tr><td>TREC</td><td>6</td><td>1.638 1.185</td><td>0.453</td><td>0.092</td><td>0.019</td></tr><tr><td colspan="2">YelpReview (Polarity) 2</td><td>0.693 0.371</td><td>0.322</td><td>0.098</td><td>0.044</td></tr><tr><td>AG News</td><td>4</td><td>1.386 0.808</td><td>0.579</td><td>0.147</td><td>0.076</td></tr><tr><td>Language Modeling</td><td/><td/><td/><td/><td/></tr><tr><td>Penn Treebank</td><td>42</td><td>2.966 1.876</td><td>1.090</td><td>0.165</td><td>1.083 (ppl)</td></tr></table>

Peer review (iclr2020):
The paper proposes a measure of difficulty for datasets. Prior work in this space has often utilized certain indicators like the overlap of samples across different classes etc. [A] While this work defines a model-agnostic error as the measure of difficulty, which should encompass all possible indicators of error. Then, the paper provides a lower bound on this error which can be estimated using neural network [B] I am inclined to accept (weak) this paper for the following reasons: 1. The paper extends Fano*s inequality for the case of real-valued vectors and discrete labels, under the assumption of smoothness of the estimators. 2. The proposed approach for difficulty measure estimation is simple and clear and primarily based on [B]. 3. The estimates seem to correlate well with the errors of state of the art models, particularly on sentiment and text classification dataset. On the image datasets, it is still reasonably well correlated. Some suggestions for improvement: 1. Add prior work on measuring data complexity to the references, e.g. [A, C] etc. and add some details contrasting prior work with this paper 2. It would also be good to see some correlation numbers like Pearson correlation etc. between DIME and SOTA errors. [A] Spectral Metric for Dataset Complexity Assessment, CVPR 2019 [B] Mutual Information Neural Estimation, ICML 2018 [C] Complexity Measures of Supervised Classification Problems, PAMI 2002 --- Update: Thanking authors for all the thoughtful rebuttal made to other reviewers. Based on the concerns raised by the other reviewers and looking through the comments, I am inclined to lower my scores to a weak reject. There is definitely quite a lot of good ideas in this paper and it might just be a matter of bulking up with more analysis at this point as suggested by other reviewers.