DIME: AN INFORMATION-THEORETIC DIFFICULTY MEASURE FOR AI DATASETS
Authors: Peiliang Zhang
Huan Wang
Nikhil Naik
Caiming Xiong
Richard Socher
Venue:  (2020)
Keywords: Information Theory
Fano’s Inequality
Difficulty Measure
Donsker-Varadhan Representation
Theory

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 proposeDIME, an information-theoretic 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.

Under review as a conference paper at ICLR 2020
DIME: AN INFORMATION-THEOREN DIFFICULTY MEASURE FOR AI DATASETS
Anonymous authors Paper under double-blind review
ABSTRACT
Evaluating the relative difficulty of widely-used benchmark datasets across time and across data modalities is important for accurately measuring progress ma- chine learning. To help tackle this problem, we propose DIME, an information- theoretic DIfficulty MEasure for datasets, based on conditional entropy estimation of the sample-label distribution. Theoretically, we prove model-agnostic and modality-agnostie lower bound on the 0-1 error by extending Fano's 's inequality the common supervised learning scenario where labels are discrete and features are continuous. Empirically, we estimate this lower bound using a neural network 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 both vision and language datasets, we show that DIME is well-aligned with empirically observed perfor- mance of statc-of-the- of-the-art machine learning models. We hope that DIME can aid future dataset design and model-training strategies.
INTRODUCTION
Empirical machine learning research relies heavily on comparing performance of algorithms on 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 language and vision. So, for instance, is difficult to compare the relative progress made on a sentiment analysis benchmark such the Stanford Sentiment Treebank (SST) (Socher et al., 2013) and an image classification benchmark, like CIFAR-10 (Krizhevsky) 2009). With these challenges in mind, propose model-agnostic and modality-agnostie measure for comparing how difficult it is to perform supervised learning on a given dataset.
Intuitively, assuming that dataset examples sampled i..dd from static true distribution, argue that the difficulty of a dataset can be decoupled into two relatively independent (aurces:(a) approximation complexity, the number of samples required 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, turn the information-tee colomattion-thooetiic 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 's in- equality suggests the probability of 0-1 error is bounded by terms related to the conditional entropy H((Y))), where X the random variable representing the features and is the label. When both the features X and label Y are continuous, results differential entropy also suggest the expected L2 error is lower-bounded. However, in most of the supervised learning datasets where the fea- tures continuous and the labels are discrete, it is unknown how the lowest possible error can be controlled regardless models.
In this paper, show that even for the hybrid case where labels discrete and features continuous, with some additional assumptions, Fano's inequality still holds. Moreover, we show that the lowest possible probability P. of the (1-1 error for given data distribution is lower bounded

---

Under review as a conference paper at ICLR 2020
DIME
X
4
2
IMDb
9
Toy Data
Toy Data
MNIST
Toy Data 3
IMDb
CIFAR-10
SST-5
Figure 1: We propose DIME, model- and mogaoity difficulty metric for datasets
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 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 neural network. However, we empirically show that, for most image and natural language datasets, 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 exten- sively studied, research has focused purely discrete continuous data. Nair et al. (2006) were among the first to study the theoretical properties for the case mixture of discrete and continuous variables. Ross (2014), Gao et al. (2017) and [Beknazaryan estimating mutual information for the mixture case based on density ratio estimation .iinningg kNN or kernel methods), which is unsatisfactory for high dimensional data such image and text. We use neural network estimation (Belghazi et al.) (018) to avoid these issues. More importantly, are the first connect the hybrid conditional entropy with the lowest classification error and able to use it as a difficulty measure for datasets.
al. (2019) proposed approaches for
DESIGNING DATASET DIFFICULTY MEASURE
For supervised learning across data modalities such images and text, data samples can usually be viewed as feature-label pairs (z. y) where x E X' C Rd=, and y E D. We focus on classification problems where the labels y are discrete, i.e.. z We denote the joint distribution of the fcature-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:
The feature-labed pairs (x, y) in the datasets, both training and testing, are sampled i..dd from a static distribution (x, y) ~ Pxy.
Assumption 1.
Intuitively, there are many possible indicators for the potential difficulty of 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 I if the samples (z, are sampled i.idd. from Pxy. where y discrete, 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 (Model-Agnostic Error). P. = inf, Pay~Pxy (fx) + vl
The measure straightforward, but unfortunately 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

---

Under review as a conference paper at ICLR 2020
2.1 DISCRETE FEATURES
In the case where the features X are discrete, according Fano's theorem, Pe is lower bounded:
Fano's inequality. If both X and Y are discrete random variables, then Pa 2 [ is the cardinality of the label set y, and (X) is the conditional entropy.
HY x-1 log D
where
However, even though data can be represented using discrete integers, treating the features as dis- crete 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 long, the feature dimension becomes large very quickly.
2. Given the large feature space, finding matching of features between training and testing data from the limited number training and test samples would be unlikely. As a result, probability mass estimation each discrete value would be impractical, since we may only see most one sample for each discrete configuration.
2.2 CONTINUOUS FEATURES
As opposed to treating the features x as discrete random variables, we view them as i.i.d. samples from continuous distribution with probability density Pa, we can estimate the conditional entropy [[ 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 with the continuous features and discrete labels, it has not been shown how Pe can be controlled. In this paper, we prove generalized version of Fano's inequality that holds for the continuous-featte discrete-label scenario. Formally, for the continuous- -disserrte-------------- case: Definition 2. Hybrid Conditional Entropy
H(Y|X)= == Ex
Σ
P(Y log P( = y/x)
where P-Y = y|X) :- =[)((=))){]
This definition of XY 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, connect Pe and the hybrid [[Y|)), we introduce an assumption on the function f Definition 3. Smooth Discretization Property: The function f X + y satisfies the smooth discretization property for every y E Y, almost every I E X (xr a.e. in X),
f(x) = = 36 > O S.I. Vi E Bs(x), f(ō)= = y.
where = := E | x 8) is a 8 neiighhorrood of x in X.
This assumption on the classifier function f is not unnatural considering f maps a continuous vari- able to discrete variable. Without this assumption, it would be extremely hard to quantify the population eиrог probability (Xf(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 is constant in each neighborhood. In this sense the assumption f is pretty minimal. Now we are ready to extend Fano's 's inequality:
Theorem 1. Fano's 's Inequality for Continuous Features: Let Pe be the minimum error probability i.e.
P. inf Pn=inf 4Y)
where f is any estimator of Y based on the observation X that satisfies the smooth discretization property. Then we have
H((P.) + PP log( m 1) 2 HY())),
where HH(()) -Pe log P. - ((1-P))ooge P.)-
3

---

Under review as a conference paper at ICLR 2020
Proof. See appendix B
3 ESTIMATING THE LOWER BOUND
natural consider Pa defined Theorem 1 as a measure of dataset difficulty. Unfortunately, direct estimation of Pa is impractical since one has to evaluate the estimation error against all pos- sible estimators. However, theorem provides an alternative towards estimating lower bound on Pe through estimating the hybrid conditional entropy HYY (X) defined in Equation I
3.1 CONDITIONAL ENTROPY ESTIMATION
In real applications, direct calculation of hybrid conditional entropy [XX) according to Defini- tion is impossible since P(Y x| unknown. However, similar to the conditional entropy for discrete random variables, the hybrid conditional entropy HX)) can also be written as
H(Y (YY
Σ P(Y g)KL(X x)
Please refer to Appendix A for detailed proof of Equation information Y), which compatible with (
We also define the hybrid mutual
D
I(X;Y) Σ y))=X)X(XXY- x
(4)
In some benchmark datasets with balanced classes (e.g., CIFAR-10 and MNIST), X
log [3|| | Σn KL(X|Y = X). This indicates that if a dataset has more classes and the features for different classes closer to each other 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 Even though there are non- parametric KL divergence estimators such as &NN based techniques (Noshad 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 dimension of the raw features and is hard to estimate. As an alternative, we design neural network- based estimator for KI. divergence estimation, inspired by Belghazi al. (2018). The estimator based on the following theorem:
the data manifold is usually much smaller than
Donsker-Varadhar representation.
KTL(PIIQ)=
sup Ep[7] log Egle ) T-R-RR
(5)
we parameterize the function T using a neural network, we obtain:
KL(P|10) 2 Sp log Eg[e""],
(6)
where 0 represents the neural network parameters.
In our empirical evaluation, we optimize the empirical average instead of the expectation. However this may cause issues such overfitting. To mitigate this issue, 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 T for details.
4

---

Under review as a conference paper at ICLR 2020
Algorithm DIME
......., , yi one per class. Initialize class counters h1 = 0, ....... li = 0, one per class. Initialize the sample counter A: = 0.
Initialize | neural networks: To, Toz.....
for t in .....,7 do
Draw batch of b training examples { y1) and b evaluation examples {(=}, }
for each class e E {l...., } do
Find samples of the c-th class: S. fily; c). St filyf =} Train 0g
arg maxe.
[5.] Es. To. (ri) logl E, exp To. (x,))
Evaluate KT.
Ese To. (xf) logl : E, exp To. (x:))
[571
IKLLs stops increasing, pause the training for To.. Update counters: ke+ |- end for Update the sample counter: ++ = If all neural networks stop updating, break.
end for
Estimate the class probability P. :/, f1,....,177
Calculate [i()X) using (3). Po. and KKL,,, c {l, [/}
Solve and output the solution.
3.3 DIME AS DIFFICULTY MEASURE
Given that are using a neural network model estimate the KL divergence between PyXly) and P(X), according to Equation 6 [L y X) < (L xX) As consequence, the estimated mutual information I(X; Y) < I): which leads to 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 estimate lower bound instead. The hope is, if the function class of the neural network is large enough, the gap between (L X) and (L |y| XX) is small enough so that DIME won't t deviate too much from the true lower bound of Pa. We now describe experiments for DIME using vision and language benchmark datasets.
EXPERIMENTS AND RESULTS
We try to answer the following questions through our experiments: Is the neural net estimator tight- enough? How does DIME align with the -fateoof-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), Ex- tended MNIST (EMNIST) (Cohen et al. 2017). Fashion MNIST (Xiao et al. (017a). CIFAR- 10 Krizhevsky 2.09). CIFAR-I00 (Krizhevsky 2009). Tiny ImageNef" and SVHN (Netzer al., 2011) The EMNIST dataset has several different splits, which include splits by digits, letters, merge. class, and balanced. For controlled evaluation study, we also add the PyTorch Fakedata datase which contains 10-classes of randomly-generated -eeeratted 32 x 32 grayscale images.
Among natural language processing datasets, we investigate three supervised scenarios: senti- ment analysis, text classification, and language modeling. For sentiment analysis, we analyze IMDb (Maas et al. (011), and Stanford Sentiment Treebank (SST) (Socher et al.) (013). In the case of SST, we utilize both fine-grained labels (SST-5) and binary labels (SST-2). For the text clas- sification task, we use the TREC dataset (Li & Roth 20022). AG News, DBPedia, as well as Yelp Review dataset (Zhang al. 2015). For language modeling task, analyze the character level
modeling for Penn Tree Bank Marcus et al. 1994).
httra:///iioyyiaagneeeerrrrrrrr https://qi thub. http:://wh...tooo.coccccc//t/taa
Fakedata.pp
5

---

Under review as a conference paper at ICLR 2020
For DIME estimation, do not perform any preprocessing 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 HH [X] and Pe 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 resid- ual 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, fol- lowed by three layers of 256 hidden neurons with residual connections and ReLU activations. We found that higher dimension of the embedding helps achieve tighter bound. The embedding layer is initialized with concatenation of five pretrained embedding vectors: GloVe-840B-3000 GloVe-42B-300.,
FastText-en-300d and CharNGram- 100d. The input sequences are truncated or padded to the length of 128. The MLP is operating the token dimension instead of the embedding dimension take the order of the sequence into consideration. For example, the first layer of MI. is 128-by-256 instead of 1500-by-256. The last fully-connected layer flattens everything into vector and projects it to 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 evaluation set, described in Algorithm
--eetwitter--77 200d, GloVe-6B-
0.5
0.8
0.4
0.6
DIME
DIME
0.3
0.4
CIFAR-10
0.2
MNIST
0.2
FASHION
SVHN
0.1
EMNIST-LETTERS
0
0.2
0.4
0.6
0.8
0.2
0.4
0.6
0.8
Label Corruption Rate
Fraction of Samples
Figure 2: DIME increases with increase the amount of label corruption (left). DIME becomes reasonably stable as the fraction of samples from the dataset used for estimation increase (right).
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 []. Samples in Toy Data 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 separated, gets DIME of 0.001. Toy Data 2, which is bit harder due to small overlapping region around the axis origin, gets DIME of 0.013. And Toy Data 3, which 0.263. In sum, DIME accurately reflects the relative difficulty of the toy examples.
hardest due to overlapping supports of the two class, gets a DIME of
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. from 0 to 1. We observe consistent increase in DIME across all the datasets with increasing label corruption (Figure (left). For some datasets such as MNIST, DIME is almost tight given the fraction of randomly comrupted labels.

---

Under review as a conference paper at ICLR 2020
Corpus
#classes
HY))
((X;Y)
H X)
DIME
SOTA Error
Image Classification
EMNIST (digits)
10
2.303
2.255
0.048
0.006
0.002
MNIST
10
2.301
2.192
0.109
0.015
0.002
EMNIST (letters)
26
3.258
2.872
0.386
0.054
0.056
EMNIST (bymerge)
47
3.554
3.098
0.456
0.060
0.190
Fashion-MNIST
10
2.303
1.912
0.391
0.066
0.033
EMNIST (byclass)
62
3.679
3.126
0.553
0.072
0.240
EMNIST (balanced)
47
3.850
3.212
0.638
0.089
0.095
SVHN
10
2.223
1.436
0.786
0.159
0.010
CIFAR-10
10
2.303
0.915
1,388
0.340
0.010
CIFAR--00-Subclas
10
2.303
0.503
1.800
0.504
N/A
CIFAR-100
100
4.605
1.239
3.366
0.585
0.087
Tiny ImageNet
200
5.298
0.692
4.606
0.768
0.268
FakeData
10
2.303
-0.003
2.306
0.900
0.900
Sentiment Analysis
IMDb
2
0.693
0.224
0.469
0.178
0.038
SST-2
2
0.693
0.224
0.469
0.179
0.032
SST-5
5
1.573
0.230
1.342
0.470
0.356
Text Classification
DBPedia
14
2.639
2.387
0.252
0.037
0.013
TREC
6
1.638
1.185
0.453
0.092
0.019
YelpReview (Polarity)
2
0.693
0.371
0.322
0.098
0.044
AG News
4
1.386
0.808
0.579
0.147
0.076
Language Modeling
Penn Treebank
42
2.966
1.876
1.090
0.165
1.083 (ppl)
Table 1: We evaluate DIME on vision and language datasets and rank them by relative difficulty. Comparisons with prediction performance of state-of-the-art neural network models shows that DIME roughly aligned with empirically observed performance. (ppl: perplexity)
4.4 EVALUATING BENCHMARK DATASETS IN VISION AND LANGUAGE
We evaluate DIME using popular image and language domain datasets for various classification tasks. In addition dataset statistics, report the estimated label entropy V. the estimated hybrid mutual entropy (Eq. 4). the estimated hybrid conditional entropy H (Eq. 1). and DIME. We also report the state-of-the of-the-art error on the dataset from recent literature (Wan et al., 2013 Huang al. 2018 Cubuk al.) 2019 Yang al. 2019 Patro et al. 2018 Cer et al. 2018 8: Melis et al.,
2019
From the results summarized in Table we make the following empirical observations:
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-an error for all the variants of EM- NIST. This could indicate that since EMNIST is relatively new, less-investigated dataset, might see model performance improving over time.
First, DIME align well with the state-of-ther
Second, larger number of classes lead to a higher value of DIME in general, which is expected given its dependence on HY) But (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, Mashion-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 difffcuut than MNIST, though not 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 discussed in Section 3 DIME could be larger than the true lower bound P. since we constrain the function space be a neural network model. While the relative order of difficulty suggested by DIME reasonable, its large value also suggests

---

Under review as a conference paper at ICLR 2020
CIFAR-10
automabile
Fashion-MNIST
sneaker
ankle-boot
sandal
trouser
horse
truck
airplane
frog
ship
pullover
coat
f-shirt
dress
bag
shirt
bird
dog
deer
cat
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 an open question how to choose a model that is large enough to approximate Pe yet casy to optimize, Equation (6) suggests that as the model size grows, the gap between DIME and true lower bound of Pa becomes smaller. We verify this by calculating DIME with increasing number of neurons for three-layer MLP. See Figure Appendix for details.
4.5 ADDITIONAL USE CASES FOR DIME
Dataset diffficulty per class: Algorithm can also estimate the relative difficulty of classes within dataset. For this purpose, simply rank the classes by their (L XX) A smaller value of (x) indicates the class harder classify. As examples in Figure show, 'cat' and 'bird' are the most difficult classes in CIFAR-I0, while 'automobile' and 'ship' are the easiest. In addition, 'shirt' and 'pullover' are the most difficult classes Fashion MNIST, while 'sandal' and 'trouser' the easiest.
Controlled Study with CIFAR Subsets: We obtain 10-class subset from CIFAR-100 by choos- ing 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 100 subset 0.504, significantly larger than a DIME of 0.340 for CIFAR-IO.
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 decreasing value of DIME with increasing number of samples ( (right). But we also observe that our measure becomes stable with increasing number of samples. This suggests that our method can used to estimate the relative difficulty of new datasets in domains where data is hard to collect (e.g., medical datasets, fine- mne-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. should become smaller. We experiment with different sizes of MLP and find that DIME generally decreases with increasing number neurons. However for easier datasets such as MNIST and Fashion MNIST, DIME stabilizes fairly quickly. See Figure from Appendix Cor details.
5 CONCLUSION
We extend Fano's 's inequality to the case of continuous features and discrete labels and prove a model- and modality-agnostte lower bound on the 0-1 errors. We further design DIME, an empirical dif- ficulty measure for datasets. We note that, even though our lower bound is model-agnostic, our estimator based on a neural network and the estimates are affected by choices about the neural network design. Designing better estimators remains avenue for future exploration. However, hope that this work can aid dataset-design 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.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Alcksandr Beknazaryan, Xin Dang, and Hailin Sang. On mutual information estimation for mixed- pair random variables. Statistics Probability Letters, 2019.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. Mutual information neural estimation. International Conference on Machine Learning, 2018.
Daniel Cer, Yinfei Yang, Sheng-yi Kong, Nan Hua, Nicole Limtiaco, Rhomni St. John, Noah Con- stant, Mario Guajardo-Cespedes Steve Yuan, Chris Tar, Yun-Hsuan Sung, Brian Strope, and Ray Kurzweil. Universal sentence encoder. CoRR, abs/1803, 1115, 2018.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andr van Schaik. Emnist: an extension of 130../////000007333 2017.
mnist to handwritten letters. Retrieved from
Thomas M Cover and Joy A Thomas. Elements of information theory. John Wiley & Sons, 2012.
Ekin Dogus Cubuk, Barret Zoph, Dandelion Mane, Vijay Vasudevan, and Quoc V. Le. Autoaugment: Learning augmentation policies from data. CoRR, abs/1805.00 905.09501, 2019.
Weihao Gao, Sreeram Kannan, Sewoong Oh, and Pramod Viswanath. Estimating mutual informa- tion for discrete-comtinuous mixtures. Advances in neural information processing systems, 2017.
Yanping Huang, Yonglong Cheng, Dehao Chen, HyoukJoong Lee, Jiquan Ngiam, Quoc V. Le, and Zhifeng Chen. Gpipe: Efficient training of giant neural networks using pipeline parallelism. CoRR, abs//8l abb/118 2018.
Alex Krizhevsky. Learning multiple layers of features from tiny images. tech report, 2009.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- basde learning applied to document recognition. Proceedings of the IEEE, 1998.
Xin Li and Dan Roth. Learning question classifiers. International Conference on Computational Linguistics (COLING), 2002.
Andrew L. Maas, Peter T. Pham Raymond E. Daly, Andrew Y. Ng Dan Huang, and Christopher Potts. Learning word vectors for sentiment analysis. Association for Computational Linguistics (ACI.), 2011.
Mitchell Marcus, Grace Kim, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Fer- guson, Karen Katz, and Britta Schasberger. The penn treebank: Annotating predicate argument structure. Proceedings of the Workshop on Human Language Technology, 1994.
Gbor Melis, Tom Koisk, and Phil Blunsom. Mogrifier lstm. CoRR, abs/1909.01192, 2019. 2019.
Chandra Nair, Balaji Prabhakar, and Devavrat Shah. On entropy for mixtures of discrete and tinuous variables. arXiv preprint cs/0607075, 2006.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng. Reading digits in natural images with unsupervised feature learning. NIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Morteza Noshad, Kevin R. Moon, Salimeh Yasaei Sekeh, and Alfred O. Hero III. Direct estima- tion of information divergence using nearest neighbor ratios. IEEE International Symposium on Information Theory, 2017.
Badri N. Patro, Vinod K. Kurmi, Sandeep Kumar, and Vinay Namboodiri. Learning semantic sentence embeddings using pair-wise discriminator. CoRR, abs/1 abss/806..00m 806.00807, 2018.
Fernando Perez-Crur Kullback-leibler divergence estimation of continuous distributions. IEEE International Symposium Information Theory, 2008
Brian C Ross. Mutual information between discrete and continuous data sets. PLoS ONE, 2014.

---

Under review as a conference paper at ICLR 2020
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment tree- bank. Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013.
Antonio Torralba, Rob Fergus, and William T Freeman. 80 million tiny images: A large data set for nonparametric object and scene recognition. IEEE transactions on paltern analysis and machine intelligence, 2008.
Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus. Regularization of neural networks using dropconnect. International Conference on Machine Learning, 2013.
Qing Wang, Sanjeev R Kulkarni, and Sergio Verdú. Divergence estimation for multidimensional densities via k-nearest-neighhor distances. IEEE Transactions on Information Theory, 55(5): 2392 2405, 2009.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion a novel image dataset for benchmark- ing machine learning algorithms. CoRR, (bs/1700.007447,0111 2017a.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint arXiv:/708.0777 1708.07747, 2017b.
Zhilin Yang, Zihang Dai, Yiming Yang. Jaime G. Carbonell, Ruslan Salakhutdinov, and Quoc V. Le. Xlnet: Generalized autoregressive pretraining for language understanding. CoRR, abs/1906.08227,, 2019.
Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text clas- sification. Neural Information Processing Systems, 2015.
10

---

Under review as a conference paper at ICLR 2020
A HYBRID CONDITIONAL ENTROPY
Consider the usual classification setting, X, representing the feature, is random vector in RP; Y, representing the label, is a random variable(or vector) in fl...., [31]}- .)))) Assume X is continuous variable with density Px (x) for x in some compact domain f2 C X' C R.. Can we define hybrid conditional entropy H)) while X continuous and Y discrete? We give a formal definition for this mixed-pair case and demonstrate that HI) defined in our way can be a good indicator for the hardness of classification on the data (X, 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 given X.
Our definition is
DI
H(Y = Ex
Σ 8=1
P(Y = log) = v|x)
(7)
where P(Y = x|X) :|| = y)|x By the definition of conditional expectation (or probabil-
ity), is easy to check that
[ x] P(Y ())(X =)
(x(
where p(x|Y = y), E R is the conditional density function of X given Y = y. Denote Py := P(Y y), have
D
X(YIX)
1
Σ
Pup(a Y v) log
Pup(xel =y) dx
s/
px(x)
13'
p(a:Y = = dx px (x)
Σ Py log Py
Σ
Py
p(x = v)
H(Y)
Σ
Pry (X =
y=1
This proves 3
We summerize some basic properties [H)))X) under our definition
Lemma 1. (i) S HY| s HY) S log D/.
(ii) XX) = HY) if and only if X and Y are independent.
(ii)) XX) = 0 if and only if Y is function of X. That is. there exist ||] subsets of 22 such that P(X O2 n 1&y for any y # y (1,..., ()),
Ω: .1....,
P(X E u.pi Rgy) and P(Y v|X E Q2y) for any y (1,..., ('I).
Proof.
This is trivial by 7
9 and the fact that KL divergence is always nonnegative.
(ii) By is easy to get
H(|[)) = III(
-
X d X, Vy (l,.,....,
P(X E A, P(X A)P(Y y), for any
measurable set A in X, any E (1,....,111 X.Y are independent.
(iii Sufficiency: If Y is function of X, then by assumptions, for any yı # y2, we have
P(X Syys Y y2) P(X Pgy)) P(X E Ωy y yn 0.
11

---

Under review as a conference paper at ICLR 2020
Therefore, p(z|Y V2) 0 for E (a.e.). Then for any y {1, (I,...,//!)), have
(L = v) / p(a|Y lo p(x y)
dr
(10)
px
Notice that for x E (a.(a.)), px(x) = > =1 11 Py/(p = = = Pyp(x = y). and thus
KI(XIY= y) -log
(11)
Then by 99. HC X)= O.
Necessity: Assume (X 0. Notice that px(x:) >nj Pop(xll = -y) E Ω. Therefore, for any y E {1.....)))
( = -)1x) I p(x/\ p(x|Y= y1) v) p(x|1 y) dx
Px(x)
p(x = =y pup(E = =1) de
(12)
$ a pla|V== = log
=loog lygPy-
Combing and 12 we know if (X) = then
(x(x) = Pap(a|Y = v), Vx {x 22 p(>/ y) > (a.ee.), v1 v v V%. (13)
Define fy fo Ω p(=|Y v) 0}. for every y f1, fi.....,DD. D'I.. Without loss of generality, we assume (x)))= > for every x E Ω. (Otherwise, we can replace Q by Ωn (px >> 0} and the following argument is still true.) Then have
P(X 2 = P(X e 22) =
By 13
we have
P(X E 2,y== / px px(x)dz - Pop(x1l =yddr
Sq
(14)
= Py P(X &2 = y) P Y y)-
Therefore, P(Y = x|X E 22y) = 1. Lastly, we show P(X E S2y n Puy = 0 for any y + y' This is immediate if we notice that by replacing Sy in [4] with S2 0 Ogy. we can have
P(X E Oly (la)= P(X E S2 nsy = =))
Changing the postion of y and y/, we have
P(X fg P P(X E Fy n =)-)
Thus, P(X E Szy ( 0.
Before the end of the proof, we want to add a remark that the condition P(X E )g 0 is actually just consequence of P(Y y|X E 22y) 1, Vy. We add it explicitly in the conditions to make it clear that Ω2 2I...., 24p1 a partition of Ω according to the value of Y.
B PROOF OF FANO'S INEQUALITY FOR CONTINUOUS FEATURES
We see the above essential properties for HI have been preserved for the mixture case. Fur- thermore, prove Fano's inequality still holds for case. Let restate Theorem 1 here:
Theorem 2. Let Pe be the minimum error probability i.e.
P = inf P(f(X) +Y)
12

---

Under review as a conference paper at ICLR 2020
Figure 4: An example of f with Smooth Discretization Property given the data and classifier. Red points represent {æi, (o( 2; UO0 1], fo is some given classifier in practice.
where is any "continuous" " estimator of based on the observation satisfying that for any 1,...,13/,, almost every x E 2, (x a.e. in 92)
That is, f any function
E Bb(x), f(3) = y. f(x) = 38 s.t.
where Bs(z):= E Ω: ||= = 8} a neigghhbodooo of x in X. Then have
H(P)) + Pe log( - 11) (Y)
(15)
Here, H(P.) : PP log - - P1) log(1 Pe).
Proof. We basically follow the idea in the classical proof in Cover & Thomas (0012). although many details need to dealt with carefully under our definition. Assume there exists a function achieves the minimum error probability, i.e. P([(X) + Y) P.llf such ʃ doesn't 't exist, we can always find some such that (X)()) Y) S Pe + e for some little e 0, then let e + we can get the same result). Define error random variable,
1, if (X)#Y 0, if f(X)=
E
(16)
we have (in what follows, we use the notation for i 1,..., | instead of Y y remind the reader that Y is discrete.)
Under our definition 7
D ΣΣ P(Y = = = E =i,==
H(E,YIX) = Ex
(17)
1=
easy to check that
P(Y = -,
P(Y=i,, = F= j|x)
(18)
(x
13

---

Under review as a conference paper at ICLR 2020
where p(z|Y E j) is the conditional density function of X given Y i, j. Similarly, one may check that
P( j|Y i, P(Y =,,==]]=([[[1 = =iE
(19)
P(Y=i)p(X]) =
Combining the above two equations and 8
we have
P(Y i, E = j|X) = P(Y =
(20)
Plug it in 17 and use the notation
| ΣΣ 1=
HE = Ex
= j|y = i,
(21)
we get
= = +
(22)
For any x E =2,i=11 1,..., 13% we know 36 0, such that
P(X e Bs(x), i), if f(x)= =1
P(X Bs(x), = -i 0,
(23)
if f(z)
Let + 0, we have p(r|Y = = P0Y = i, 0) = p(x P) = i) or for any
E Ω and 1 < i < m. Therefore, by 19 we know PPE 0 = i, X) is always for any
1 S i < [ So is P(E = 1 = X). Then by (1]. we have
H(E X) 0.
(24)
Similar to
22
we have
=
(25)
where
H((EX = Ex
- Σ
[(E)
(26)
1=0
and
D
H(Y = Ex
P(Y = = =l1))) = i|EE
j, j,x)
(27)
0
Notice that X) < H(E)= ([)))) it suffices show
H(Y X) < P. log(()) 1).
(28)
Similar to 23 we know for any Ωt 1, 1.... 1). 0. such that
P(X E Bs(x), E 0), if f(x) =i if f(x) #i.
P(X E B8(x), Y
0) 0,
(29)
Then we get P(Y = iiE = 0, X) is always 0 or for any i = 1,...,11%.. Therefore,
H = 0, = Ex
- log = iE = 0, X)
=
(30)
3 Strictly speaking, by the definition of conditional expectation probability, we should have P(E (=x=___))((Xxxx_-_____ 1(Y * i). P(Y PLY
y = x) = P(Y P(Y P(Y=Op((][==3 -=___._))((XXX_______ 1( = i)
'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 i, X) as PFF /| XY = i) in this context. Similar for PY F j. X) below.
14

---

Under review as a conference paper at ICLR 2020
For the case E 1, we have
P(X E Bs(x), if f(x) #
-,E P(X E = =i,
(31)
0,
if [x)=
Thus, have
P(Y = i|E = 1,X) = P(Y -i = =
(32)
1(
PI f(X) #1
P(E P
(33)
if f(X)= =i.
Similar to 20 we have
P(Y E PCE 11 1,
(34)
Plug in the above two equations to H(YBE = X), we get
= 11, = Ex
Σ
11E=1|X)P(( = = 1, P(Y = =iiE E =1,)=
log P(Y = i = 1:x0) }
P(E = 1|x) (-
= Ex
P(Y -
(f(x)
< Ex [P(E- = 1|X) log( - 1)]
Pe logglo/ 1). 1).
Therefore,
H(Y X) = H(Y|E X) HY 1, s Pe log(1>) 1).
C MODEL COMPLEXITY EXPERIMENT
Equation (6) suggests when the model class is larger the gap between DIME and the true lower bound on P. becomes smaller. This is verified in our experiment shown the middle 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 expected. Still on CIFAR- the decrease is pretty monotonic. For simple datasets such as MNIST, Fashion MNIST and EMNIST (byletters) the numbers got stabilized pretty quickly.
15

---

Under review as a conference paper at ICLR 2020
0.87
DIMB
0.56
3000
# of hidden neurons per layer
(a) DIME decreases on CIFAR-10 as model size grows.
0.28
0.20
DIMME
0.21
0.28
2000
3000
f
hidden neurons per layer
(b) DIME decreases on SVHN as model size grows.
MNIST
FASHION
0.06
EMNIST-LETTERS
0.06
DIMB
0.08
1000
2000
3000
4000
hidden neurons per layer
(c) DIME decreases MNIST, Fashion MNIST, and EMNIST(hyletter)) the model size grows.
Figure 5: DIME as the model size increases.
16


Reviews:
[{"review_id": "rkxJiNHptH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper suggests a measure for the inherent difficulty of datasets: DIME.  Fano's inequality gives\na lower bound on the best possible predictor in terms of the conditional entropy of the labels\ngiven the input.  The paper uses a MINE style estimator for this conditional entropy to give dataset\ncomplexity measures.\n\nThe 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.  \n\nHowver, 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.\n\nAny fit model's log loss also provides a variational upper bound on the conditional entropy due to the positivity of KL:  \n$$ \\int dx\\, p(x) \\int dy\\, p(y|x) \\log \\frac{p(y|x)}{q(y|x)}  \\geq 0   \\implies  \\int dx\\, p(x) \\int dy\\, p(y) p(y|x) \\log p(y|x) \\geq  \\int dx\\, p(x) \\int dy\\, p(y|x) \\log q(y|x)  \\implies H(Y|X) \\leq \\mathbb{E}_{p(y,x)}[-\\log q(y|x)]$$\nThe 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.\n\nAdditionally, 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 \nhttp://artem.sobolev.name/posts/2019-08-10-thoughts-on-mutual-information-more-estimators.html\n\nThe 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.\n\nIn 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.\n\nI 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. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "SklMdajpFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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]\n\nI am inclined to accept (weak) this paper for the following reasons:\n1. The paper extends Fano's inequality for the case of real-valued vectors and discrete labels, under the assumption of smoothness of the estimators.\n2. The proposed approach for difficulty measure estimation is simple and clear and primarily based on [B].\n3. 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.\n\nSome suggestions for improvement:\n1. 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\n2. It would also be good to see some correlation numbers like Pearson correlation etc. between DIME and SOTA errors.\n\n[A] Spectral Metric for Dataset Complexity Assessment, CVPR 2019\n[B] Mutual Information Neural Estimation, ICML 2018\n[C] Complexity Measures of Supervised Classification Problems, PAMI 2002\n\n---\nUpdate:\n\nThanking authors for all the thoughtful rebuttal made to other reviewers.\n\nBased 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.", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJeCgWQ6tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThat said, I have some (potentially serious) concerns about some of the assumptions and approaches that may harm the validity of the proposal / results.\n\n1) The smooth discretization property assumption seems to directly contradict results from adversarial examples, as these examples precisely a consequence of lacking smoothness. It seems that some constraints on the family of f are necessary to ensure this property (e.g., Lipschitz continuous using weight clipping, gradient penalty, spectral norm, etc).\n\n2) The MINE estimator you use is asymptotically unbiased, and represents a *upper bound* of a lower bound of the KL when the number of samples is \"small\". The bound found in f-GAN is unbiased, yet tends not to perform well. I would also consider estimators found in [1] or use the bias-correcting found in MINE.\n\n3) I feel like the model-agnostic claims are weak, due to the use of a particular family of functions used in the estimation part. Inductive bias must play a part in this, and some datasets \"difficulty\" is intimately connected to the class of functions we optimize our classifiers over. Some of these datasets may work better with some inductive biases, so it would be worth also looking at scores using convnets / LSTMs / transformers.\n\n4) It might be better to relate \"difficult\" to real measures found in the literature. For example, one could remove examples known to be misclassified, etc. It would be good to see that removing these also lowers the DIME score.\n\nOther comments:\nEq 2: m mysteriously appears\npage 6, first paragraph: not normalizing the input worries me quite a bit. Did you show that the score is independent of normalization? This might have real consequences in conjunction with weight initialization, learning rates, etc.\nFigure 2: it is good to see that label corruption correctly correlates with DIME score.\nTable 1: it would be good to report a correlation between DIME and SOTA error.\n\nFull disclosure, I did not go through the proofs in the appendix.\n\n[1] On Variational Bounds of Mutual Information\n\nUpdate:\nThank you for the responses to my questions. So since MINE is a central component to this work, I think it's value hinges on ensuring that the estimator bounds the thing that you're saying it should. The bias might not be a practical problem as far as optimizing or using this thing, but it does throw some of the numbers into question. Bias correcting or using / comparing to another optimizer is essential.\n\nIn addition, the inductive bias issue is still an important one, and I would expect this to be at least addressed in this type of work. The fact that your other models didn't work is an important point: why and what are the ingredients for a successful model?", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a measure of inherent difficulty of datasets. While reviewers agree that there are good ideas in this paper that is worth pursuing, several concerns has been risen by reviewers, which are mostly acknowledged by the authors. We look forward to seeing an improved version of this paper soon!

Decision: Reject