Year: 2019

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.

heading: 1 INTRODUCTION
text: 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 L2 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 Pe of the 0-1 error for a given data distribution is lower bounded
by terms related to a hybrid conditional entropy H(Y |X). We further design an estimator for the lower bound of Pe based on our generalized Fano’s inequality. The estimator uses neural networks to approximate the KL divergence based on Donsker-Varadhan representation, which is then used to estimate the hybrid conditional entropy H(Y |X) as well as the lower bound of Pe. 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.

heading: 2 DESIGNING A DATASET DIFFICULTY MEASURE
text: 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 ⊂ Rdx , 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 PXY . The marginal distributions of the features and labels are denoted as PX and PY 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) ∼ PXY .
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 PXY , 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). Pe = inff Px,y∼PXY [f(x) 6= 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.

heading: 2.1 DISCRETE FEATURES
text: In the case where the features x ∈ X are discrete, according to Fano’s theorem, Pe is lower bounded: Fano’s inequality. If both X and Y are discrete random variables, then Pe ≥ H(Y |X)−1log |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.

heading: 2.2 CONTINUOUS FEATURES
text: 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 px, we can estimate the conditional entropy H(Y |X) under some smoothness assumptions and also infer the model-agnostic error Pe. 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 Pe 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
H(Y |X) := EX − |Y|∑ y=1 P(Y = y|X) logP(Y = y|X)  , (1) 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 Pe 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) 6= 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 Pe be the minimum error probability, i.e.,
Pe = inf f P (f(X) 6= Y )
where f is any estimator of Y based on the observation X that satisfies the smooth discretization property. Then we have
H(Pe) + Pe log(m− 1) ≥ H(Y |X), (2) where H(Pe) := −Pe logPe − (1− Pe) log(1− Pe).
Proof. See appendix B.

heading: 3 ESTIMATING THE LOWER BOUND
text: It is natural to consider Pe defined in Theorem 1 as a measure of dataset difficulty. Unfortunately, direct estimation of Pe 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 Pe through estimating the hybrid conditional entropy H(Y |X) defined in Equation (1).

heading: 3.1 CONDITIONAL ENTROPY ESTIMATION
text: 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):
I(X;Y ) = |Y|∑ y=1 P (Y = y)KL(X|Y = y||X) (4)
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.

heading: 3.2 A VARIATIONAL KL DIVERGENCE ESTIMATOR USING NEURAL NETWORKS
text: 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; PerezCruz, 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 EP [T ]− logEQ[eT ] (5)
If we parameterize the function T using a neural network, we obtain:
KL(P||Q) ≥ sup θ∈Θ EP [Tθ]− logEQ[eTθ ], (6)
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.
Algorithm 1 DIME Initialize |Y| neural networks: Tθ1 , Tθ2 , . . . , Tθ|Y| , one per class. Initialize class counters k1 = 0, . . . , kc = 0, one per class. Initialize the sample counter k = 0. for t in 0, . . . , T do
Draw a batch of b training examples {(xi, yi)}, and b evaluation examples {(xei , yei )}. for each class c ∈ {1, . . . , |Y|} do
Find samples of the c-th class: Sc = {i|yi = c}, Sec = {i|yei = c} Train θc = arg maxθc 1 |Sc| ∑ Sc Tθc(xi)− log[ 1b ∑ j expTθc(xj)]
Evaluate K̂Lθc = 1|Sec | ∑ Sec Tθc(x e i )− log[ 1b ∑ j expTθc(x e j)] If K̂Lθc stops increasing, pause the training for Tθc . Update counters: kc+ = |Sec |.
end for Update the sample counter: k+ = b If all neural networks stop updating, break.
end for Estimate the class probability p̂c = kck , c = {1, . . . , |Y|}. Calculate Ĥ(Y |X) using (3), p̂c, and K̂Lθc , c = {1, . . . , |Y|}. Solve (2) and output the solution.

heading: 3.3 DIME AS A DIFFICULTY MEASURE
text: 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), K̂L(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 Pe. The caveat is that Pe 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 K̂L(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 Pe. We now describe our experiments for DIME using vision and language benchmark datasets.

heading: 4 EXPERIMENTS AND RESULTS
text: 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?

heading: 4.1 DATA PREPARATION
text: 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), CIFAR10 (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).
1https://tiny-imagenet.herokuapp.com/ 2https://github.com/pytorch/vision/blob/master/torchvision/datasets/
fakedata.py
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 Pe since the rescaling function is invertible.

heading: 4.2 CHOICE OF NEURAL NETWORK ESTIMATOR
text: 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 CharNGram100d. 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.

heading: 4.3 SANITY-CHECK EXPERIMENTS
text: 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, CIFAR10, 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-(left)). For some datasets such as MNIST, DIME is almost tight given the fraction of randomly corrupted labels.

heading: 4.4 EVALUATING BENCHMARK DATASETS IN VISION AND LANGUAGE
text: 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 EMNIST. 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 Pe 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
cat
CIFAR-10
dog de er a
irpl ane hor se truc k frog aut
om obi le ship
bird
Fashion-MNIST
shi rt pul lov er coa t t-sh
irt sne ake
r
dre ss bag ank
le-b oot
san dal trou
ser
Figure 3: DIME can rank classes within datasets for difficulty. A lower height of the bar indicates higher relative difficulty.
than an MLP may not have enough capacity for accurate Pe estimation. While it is an open question how to choose a model that is large enough to approximate Pe yet easy to optimize, Equation (6) suggests that as the model size grows, the gap between DIME and true lower bound of Pe 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.

heading: 4.5 ADDITIONAL USE CASES FOR DIME
text: 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 K̂L(X|y||X). A smaller value of K̂L(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 onPe 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.

heading: 5 CONCLUSION
text: 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.

heading: A HYBRID CONDITIONAL ENTROPY
text: Consider the usual classification setting, X , representing the feature, is a random vector in Rp; Y , representing the label, is a random variable(or vector) in {1, . . . , |Y|}. Assume X is a continuous variable with density pX(x) for x in some compact domain Ω ⊂ X ⊂ Rp. 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
H(Y |X) := EX − |Y|∑ y=1 P(Y = y|X) logP(Y = y|X)  , (7) where P(Y = y|X) := E[1(Y = y)|X]. By the definition of conditional expectation (or probability), it is easy to check that
E[1(Y = y)|X] = P (Y = y)p(X|Y = y) pX(X) , (8)
where p(x|Y = y), x ∈ Rp is the conditional density function of X given Y = y. Denote py := P (Y = y), we have
H(Y |X) = ∫
Ω − |Y|∑ y=1 pyp(x|Y = y) log pyp(x|Y = y) pX(x) dx
= − |Y|∑ y=1 py log py − |Y|∑ y=1 py ∫ Ω p(x|Y = y) log p(x|Y = y) pX(x) dx = H(Y )− |Y|∑ y=1 pyKL(X|Y = y||X). (9)
This proves (3).
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 ) if and 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 6= y′ ∈ {1, . . . , |Y|}, P (X ∈ ∪|Y|y=1Ωy) = 1 and P (Y = y|X ∈ Ωy) = 1 for any y ∈ {1, . . . , |Y|}.
Proof. (i) This is trivial by (7), (9) and the fact that KL divergence is always nonnegative.
(ii) By (9), it is easy to get
H(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.
(iii) Sufficiency: If Y is a function of X , then by assumptions, for any y1 6= y2, we have
P (X ∈ Ωy1 , Y = y2) ≤ P (X ∈ Ωy1)− P (X ∈ Ωy1 , Y = y1) = 0.
Therefore, p(x|Y = y2) = 0 for x ∈ Ωy1 (a.e.). Then for any y ∈ {1, . . . , |Y|}, we have KL(X|Y = y) = ∫
Ωy
p(x|Y = y) log p(x|Y = y) pX(x) dx (10)
Notice that for x ∈ Ωy(a.e.), pX(x) = ∑|Y| y′=1 py′p(x|Y = y′) = pyp(x|Y = y), and thus
KL(X|Y = y) = − log py. (11)
Then by (9), H(Y |X) = 0. Necessity: Assume H(Y |X) = 0. Notice that pX(x) = ∑|Y| y=1 pyp(x|Y = y),∀x ∈ Ω. Therefore, for any y ∈ {1, . . . , |Y|},
KL(X|Y = y||X) = ∫
Ω
p(x|Y = y) log p(x|Y = y) pX(x) dx
≤ ∫
Ω
p(x|Y = y) log p(x|Y = y) pyp(x|Y = y) dx
= − log py.
(12)
Combing (9) and (12), we know if H(Y |X) = 0, then
pX(x) = pyp(x|Y = y),∀x ∈ {x ∈ Ω : p(x|Y = y) > 0}(a.e.),∀1 ≤ y ≤ |Y|. (13)
Define Ωy := {x ∈ Ω : p(x|Y = y) > 0}, for every y ∈ {1, . . . , |Y|}. Without loss of generality, we assume pX(x) > 0 for every x ∈ Ω. (Otherwise, we can replace Ω by Ω ∩ {pX(x) > 0} and the following argument is still true.) Then we have
P (X ∈ ∪|Y|y=1Ωy) = P (X ∈ Ω) = 1.
By (13), we have P (X ∈ Ωy) = ∫
Ωy
pX(x)dx = ∫ Ωy pyp(x|Y = y)dx
= pyP (X ∈ Ωy|Y = y) = P (X ∈ Ωy, Y = y). (14)
Therefore, P (Y = y|X ∈ Ωy) = 1. Lastly, we show P (X ∈ Ωy ∩ Ωy′) = 0 for any y 6= y′. This is immediate if we notice that by replacing Ωy in (14) with Ωy ∩Ωy′ , we can have
P (X ∈ Ωy ∩ Ωy′) = P (X ∈ Ωy ∩ Ωy′ , Y = y).
Changing the postion of y and y′, we have
P (X ∈ Ωy ∩ Ωy′) = P (X ∈ Ωy ∩ Ωy′ , Y = y′).
Thus, P (X ∈ Ωy ∩ Ωy′) = 0. Before the end of the proof, we want to add a remark that the condition P (X ∈ Ωy∩Ωy′) = 0 is actually just a consequence of P (Y = y|X ∈ Ωy) = 1,∀y. We add it explicitly in the conditions to make it clear that Ω1, . . . ,Ω|Y| is a partition of Ω according to the value of Y .

heading: B PROOF OF FANO’S INEQUALITY FOR CONTINUOUS FEATURES
text: We see the above essential properties for H(Y |X) have been preserved for the mixture case. Furthermore, we prove Fano’s inequality still holds for our case. Let us restate Theorem 1 here:
Theorem 2. Let Pe be the minimum error probability, i.e.
Pe = inf f P (f(X) 6= Y )
where f is any ”continuous” estimator of Y based on the observation X . That is, f is any function satisfying that for any y = 1, . . . , |Y|, almost every x ∈ Ω, (x a.e. in Ω)
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 . Then we have
H(Pe) + Pe log(|Y| − 1) ≥ H(Y |X). (15)
Here, H(Pe) := −Pe logPe − (1− Pe) log(1− Pe).
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) 6= Y ) = Pe(If such f doesn’t exist, we can always find some f such that P (f(X) 6= Y ) ≤ Pe + for some little > 0, then let → 0 we can get the same result). Define an error random variable,
E = { 1, if f(X) 6= Y 0, if f(X) = Y.
(16)
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.)
H(E, Y |X) := EX − |Y|∑ i=1 1∑ j=0 P(Y = i, E = j|X) logP(Y = i, E = j|X)  . (17) It is easy to check that
P(Y = i, E = j|X) = P (Y = i, E = j)p(X|Y = i, E = j) pX(X) , (18)
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
P(E = j|Y = i,X) = P (Y = i, E = j)p(X|Y = i, E = j) P (Y = i)p(X|Y = i)
(19)
Combining the above two equations and (8), we have
P(Y = i, E = j|X) = P(Y = i|X)P(E = j|Y = i,X). (20) Plug it in (17), and use the notation
H(E|Y,X) := EX − |Y|∑ i=1 1∑ j=0 P(Y = i, E = j|X) logP(E = j|Y = i,X)  , (21) we get
H(E, Y |X) = H(Y |X) + H(E|Y,X) (22) For any x ∈ Ω, i = 1, . . . , |Y|, we know ∃δ > 0, such that
P (X ∈ Bδ(x), Y = i, E = 0) = { P (X ∈ Bδ(x), Y = i), if f(x) = i 0, if f(x) 6= i. (23)
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 have
H(E|Y,X) = 0. (24)
Similar to (22), we have
H(E, Y |X) = H(E|X) + H(Y |E,X), (25) where
H(E|X) := EX − 1∑ j=0 P(E = j|X) logP(E = j|X)  (26) and
H(Y |E,X) := EX − |Y|∑ i=1 1∑ j=0 P(Y = i, E = j|X) logP(Y = i|E = j,X)  . (27) Notice that H(E|X) ≤ H(E) = H(Pe), it suffices to show
H(Y |E,X) ≤ Pe log(|Y| − 1). (28)
Similar to (23), we know for any x ∈ Ω, i = 1, . . . , |Y|, ∃δ > 0, such that P (X ∈ Bδ(x), Y = i, E = 0) = { P (X ∈ Bδ(x), E = 0), if f(x) = i 0, if f(x) 6= 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) := EX − |Y|∑ i=1 P(Y = i, E = 0|X) logP(Y = i|E = 0, X)  = 0. (30) 3 Strictly 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 6=i)p(X|Y 6=i) 1(Y 6= i).
4For 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.
For the case E = 1, we have
P (X ∈ Bδ(x), Y = i, E = 1) = { P (X ∈ Bδ(x), Y = i), if f(x) 6= i 0, if f(x) = i.
(31)
Thus, we have
P(Y = i|E = 1, X) = P (Y = i, E = 1)p(X|Y = i, E = 1) P (E = 1)p(X|E = 1)
(32)
= { P (Y=i)p(X|Y=i) P (E=1)p(X|E=1) , if f(X) 6= i 0, if f(X) = i.
(33)
Similar to (20), we have
P(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 get
H(Y |E = 1, X) = EX − |Y|∑ i=1 P(E = 1|X)P(Y = i|E = 1, X) logP(Y = i|E = 1, X)  = EX P(E = 1|X) − ∑
i6=f(X)
P(Y = i|E = 1, X) logP(Y = i|E = 1, X)  ≤ EX [P(E = 1|X) log(|Y| − 1)] = Pe log(|Y| − 1).
Therefore,
H(Y |E,X) = H(Y |E = 0, X) + H(Y |E = 1, X) ≤ Pe log(|Y| − 1).

heading: C MODEL COMPLEXITY EXPERIMENT
text: Equation (6) suggests when the model class is larger the gap between DIME and the true lower bound on Pe 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.

Review summaries:
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]

So this paper is interesting. It's sort of pursuing a similar path as recent works that use neural networks to evaluate (e.g., inception score, FID), notably those that optimize some lower bound of an information measure (e.g., MINE). In this case, the setting is "datasets", and the thing they are trying to quantify is the difficulty of the dataset as expressed by a lower bound to the lowest possible probability of the 0-1 error, which they should is related to the conditional entropy of the underlying input / label random variables (which makes sense). This direction seems very useful, and using neural network optimization to attempt to crack defining "dataset complexity" or "difficulty" seems a worthwhile venture.