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):
This paper suggests a measure for the inherent difficulty of datasets: DIME. Fano*s inequality gives a lower bound on the best possible predictor in terms of the conditional entropy of the labels given the input. The paper uses a MINE style estimator for this conditional entropy to give dataset complexity measures. The idea of using Fano*s inequality and tight estimates of conditional entropy to give us a sense of how good we are doing on different datasets is a good one. Howver, I believe this paper should be rejected. While the idea of using Fano*s inequality to give a complexity score for datasets is interesting, this paper does not provide what appears to be a close measure of this conditional entropy. Any fit model*s log loss also provides a variational upper bound on the conditional entropy due to the positivity of KL: The log loss of any model provides a variational upper bound on the conditional entropy H(Y|X). In table 1, for all but EMNIST there exist models that give tighter upper bounds on the conditional entropy than DIME does. While in principle an independent estimate of the conditional entropy might provide a useful signal that there is room to go in terms of the classification task (as it seems to do here in the case of EMNIST), in general the estimates provided by their MINE style estimator seem to not perform well. Additionally, MINE does not provide a valid bound on the conditional entropy, (see e.g. *On variational bounds of mutual information* arXiv:1905.06922) as it when used as suggested it requires taking a monte carlo expectation inside a negative log. A monte carlo estimate of a log expectation provides a stochastic lower bound of the log expectation (by Jensen*s) so provides a stochastic upper bound of the proposed lower bound on KL, breaking the bound. Couple this with the observation that MINE provides very high variance estimates of mutual information, in particular when the values are large, along with the general failure of the estimates in Table I and the specific combination of using MINE to give useful upper bounds on conditional entropy seems not to work well in practice, even on datasets with rather small expected conditional entropy (e.g. MNIST). I suggest leveraging the known marginal in this instance to use an IWHVI style mutual information lower bound, as in http://artem.sobolev.name/posts/2019-08-10-thoughts-on-mutual-information-more-estimators.html The paper extends Fano*s inequality to the mixed discrete-continuous case. I always thought Fano*s inequality would just carry over to the mixed discrete-continuous case because it doesn*t rely at all on the cardinality of the input (X in this case). Shouldn*t a simple sup over all finite partitions of X give a natural extension (as it does to mutual information and conditional entropy in Cover & Thomas). While there is utility in a careful extension or even clarifying note on the role of Fano*s inequality in the mixed case, it*s not clear it requires an entire paper, perhaps a note on the arxiv would help others who were interested in the extension. In general, it doesn*t seem as though the suggested method provides utility in giving better estimates of the difficulty of datasets than can already be gotten from our observed model log losses. The MINE estimator is flawed and using it to estimate DIME is likely (and demonstrated in the paper) to give worse estimates than just training a conditional discriminative model and comparable cost, so I have to vote to reject the paper in its current form. I do still think it is an interesting idea to try to assess whether or not we are within spitting distance of the optimal performance we could expect on our datasets. To provide a proper lower bound would require a lower bound on the conditional entropy, for which I*m not sure of any general purpose results that could be leveraged, but in these settings it*s not too dangerous to assume we have access to at least a known marginal over the labels and there is some hope that a decent lower bound on the conditional entropy might be able to be formed in this case. For upper bounds, I really believe just the log loss of the best model the community has garnered is going to provide the tightest upper bound in almost all cases. Could we still use this to figure out whether or not we have room to go? While I have observed that in general for most models there isn*t the best correlation between log loss and accuracy, the result of Fano*s inequality suggests that when we really nail a dataset we might expect that the log loss provides a very tight upper bound on the true conditional entropy and the observed error rates provides a tight upper bound to the optimal Fano rate. This suggest that it might be useful to collect paired results of the log loss and error from a whole slew of models and scatter the log loss versus ( H(e) + P(e) log (|Y|-1) ). Then as just a sort of visual test as to whether the community is within spitting distance of the true discriminative density would be whether the best models start to show a linear relationship between their log loss and the transformed error rate.