Quantifying Task Complexity Through Generalized Information Measures
Authors: Aditya Chattopadhyay
Benjamin David Haeffele
Donald Geman
Rene Vidal
Venue:  (2021)
Keywords: Task Complexity
Information Pursuit
Deep Generative Models
Information Theory
Variational Autoencoders
Normalizing Flows

Abstract: How can we measure the “complexity” of a learning task so that we can compare one task to another? From classical information theory, we know that entropy is a useful measure of the complexity of a random variable and provides a lower bound on the minimum expected number of bits needed for transmitting its state. In this paper, we propose to measure the complexity of a learning task by the minimum expected number of questions that need to be answered to solve the task. For example, the minimum expected number of patches that need to be observed to classify FashionMNIST images. We prove several properties of the proposed complexity measure, including connections with classical entropy and sub-additivity for multiple tasks. As the computation of the minimum expected number of questions is generally intractable, we propose a greedy procedure called “information pursuit” (IP), which selects one question at a time depending on previous questions and their answers. This requires learning a probabilistic generative model relating data and questions to the task, for which we employ variational autoencoders and normalizing flows. We illustrate the usefulness of the proposed measure on various binary image classification tasks using image patches as the query set. Our results indicate that the complexity of a classification task increases as signal-to-noise ratio decreases, and that classification of the KMNIST dataset is more complex than classification of the FashionMNIST dataset. As a byproduct of choosing patches as queries, our approach also provides a principled way of determining which pixels in an image are most informative for a task.

Under review as a conference paper at ICLR 2021
QUANTIFYING TASK COMPLEXITY THROUGH GENER- ALIZED INFORMATION MEASURES
Anonymous authors Paper under double-blind review
ABSTRACT
How can we measure the "complexity" of learning task so that we can compare one task to another? From classical information theory, we know that entropy is a useful measure of the complexity of a random variable and provides lower bound on the minimum expected number of bits needed for transmitting its state. In this paper, we propose to measure the complexity of a learning task by the minimum expected number of questions that need to be answered to solve the task. For example, the minimum expected number of patches that need to be observed to classify FashionMNIST images. We prove several properties of the proposed com- plexity measure, including connections with classical entropy and sub-additivity for multiple tasks. As the computation of the minimum expected number of ques- tions is generally intractable, we propose a greedy procedure called "information pursuit" (IP), which selects one question tions and their answers. This requires learning probabilistic generative model relating data and questions to the task, for which we employ variational autoen- coders and normalizing flows. We illustrate the usefulness of the proposed mea- sure on various binary image classification tasks using image patches as the query set. Our results indicate that the complexity of classification task increases as signal-to-noise ratio decreases, and that classification of the KMNIST dataset is more complex than classification of the FaShionMNIST dataset. As a byproduct choosing patches as queries, our approach also provides a principled way of determining which pixels in image most informative for a task.
time depending on previous ques-
INTRODUCTION
Deep networks have shown remarkable progress in both simple and complex machine learning tasks. But how does one measure the "complexity" of a learning task? Is it possible to ascertain principled manner which tasks are "harder" to solve than others? How "close" is one task to another? Answers to these questions would have implications in many fields machine learning such as transfer learning, multi-task learning, btasemm/self-superiisee learning, and domain adaptation.
In classical information theory, the entropy of a random variable X is a useful measure of com- plexity for tasks such as compression and transmission, which essentially require reconstructing X. However, the entropy of is insufficient for measuring the complexity of a supervised learning task Tx,y, where the goal is predict output Y from input X, i.e., to estimate the conditional Pyix x) from a finite set of samples from Pxy(2; y). which we refer to as solving the learning task. Complexity measures provided by statistical learning theory like VC-dimension or covering numbers are also inadequate for this purpose because they ignore the dependence between X and Y for the particular task at hand. feormation-thhorette measures such mutual information, infor- mation bottleneck (Tishby et al.) (2000) and its variants (Strouse & Schwab) 2017) have been used to study the trade-off between model complexity and accuracy, but have not been developed to focus on assessing task complexity and can provide unsatisfactory results when comparing different tasks (see Section 5 for details). Measures based on Kolmogorov complexity (Li) 2006 Vereshchagin & Vitányi 2004) could in principle be used to compare different tasks, but they are dataset permutation sensitive and not easily computable. The work of (Achille et al.) 201 9a) proposes to quantify task complexity by measuring the information stored the network weights, but the approach depends on the specific neural network architecture used for training. The work of (Tran et al.) 2019) does not require assume trained models, but makes strict assumptions that limit its broad applicability.

---

Under review as a conference paper at ICLR 2021
In this work, we introduce a novel perspective task complexity which generalizes classical mea- sures from information theory. Specifically, one well-known interpretation of classical Shamnon entropy is, given random variable X, find the minimum number of bits that are needed on average to encode instances of X so that the instances can be perfectly recovered from the binary code. Stated differently, if one lets Q be defined as the set of all possible binary functions, of X, then Shannon entropy essentially asks what is the optimal sequence of queries to compute (x)),,()))) (x(). qi E Q) (i.e., how encode X binary string) so that X can be perfectly recovered from the shortest (on average) sequence of binary answers to the queries (see Section 2 for more discussion of this interpretation). As discussed above, however, in most learning tasks we are not interested in simply compressing X but rather making a prediction about some other vari- able Y. Further, notions of complexity can potentially not having Q to be the set of all possible binary functions on X but rather a smaller set of queries specific to a measure of interest. From this intuition, we define the complexity of a learning task as the minimum expected number of queries, selected from fixed set Q, one needs to ask to predict Y (to some user-defined level of confidence) from the respective answers to the queries. As a few specific examples of potential query sets:
the domain
made more relevant to a specific task by
Decision boundary complexity: Here, Q is the the set of all possible half-spaces in Rd (assuming X E IR and (zx) is binary function response indicating whether lies in particular half-space (q E Q) Then task complexity formalizes the intuition of "level of non-linearity" of the decision boundary. For example, the complexity of any linearly-separable binary classification task is 1, whereas, for a non-linearly separable task, this value depends on the curvature of the decision boundary.
Task-specific input feature complexity: Here, Q is the set of projection functions of X and is of the form ((x)) = Zeg. where xg is the value observed at the yd entry of Then task complexity formalizes the intuition "the greater the redundancy between the input features the easier it is to solve the task". For example, Y being a constant function of X would be the simplest task with complexity 0, since no feature needs to be queried predict it. This notion of complexity would help in answering questions such as "which input features are most important for solving a given task?" and could in turn help in developing more "interpretable" learning algorithms.
Visual semantic complexity: Given a vocabulary V of different possible entities, their attributes and relations in a visual scene, Q could be the set of all binary functions indicating the presence or absence of an entity, its attribute or its relation with other entities (supplied by V) in a designated region of the image X. For example, a particular q could be the function implementing the query "Is there person in the top left corner of the image?". This notion of complexity would allow one to gauge the semantic complexity of a visual task. For instance, tasks which ask complex questions like "Is there a person playing with his dog, next to a river in the image?" would inher- ently be more complex than simple object detection tasks, "Where is the dog in this image?" and could be quantified by semantically relevant queries.
While our proposed formal definition of task complexity will be applicable to all such choices of query functions {4) and enjoys several nice theoretical properties that we discuss in section 2 its computation will generally be intractable. As a result, in section 3 we propose to reduce the complexity of selecting minimal set of questions by using the Information Pursuit (IP) algorithm, which selects questions sequentially, depending on previous questions and answers, in order of in- formation gain. While IP is generally applicable to any task and query set, its implementation is still intractable depending on the complexity of the model p(X, Y) and of the set Q. To address this issue, we posit tractable graphical model for p(X, Y) and learn the required distributions using variational autoencoders and normalizing flows. In section D we evaluate our approach on various binary image classification tasks (MNIST, KMNIST, FashionMNIST, Caltech Silhouettes) that can be tackled using a common set of queries (the set of image patches). Our results show that complex- ity computed using patch queries aligns with the intuition that the complexity of a classification task increases as signal-to-noise ratio decreases, and that classification of the KMNIST dataset is more complex than classification of the MNSHI dataset, something that isn't obvious a priori. While these experiments are restricted to simple tasks and queries, the proposed framework is gen- erally applicable provided that tractable models, inference and learning methods can be developed, which is the subject of ongoing and future work. Finally, note that to the best of our knowledge, this is the first time that a subjective notion of task complexity has been proposed in literature, where the user incorporate in Q the perception of complexity he/she wishes measure.
2

---

Under review as a conference paper at ICLR 2021
2 QUANTIFYING TASK COMPLEXITY
Let the input data be represented by random variable X and the corresponding output/hypothesis by random variable Y with sample spaces X' and Y respectively. A supervised learning task Tx:y is defined as the task of estimating the conditional distribution pylx x) from a finite set of samples from the joint distribution Pxy (z. y) We propose to quantify the complexity of a task as the minimum expected number of queries needed to solve the task. Queries, q E Q, are functions of the input data, whose answers for given z are denoted as (q(=)) Naturally, the query set needs to be sufficienlly rich so that the task is solvable based on answers to the queries. More formally, we say the set Q is sufficient for task T T if V(x, v) E X x y
ply x) - ply {x' X q(x') ( Vq Q}).
(1)
In other words, Q is sufficient for task Tx.y if whenever two points x and x have identical answers for all queries in Q, then their true posteriors must be equal, p(y x)) p(y x').
Given a fixed query set Q, we now formally define an encoding function Eq. which we refer to as a Q-Coder, along with our proposed complexity measure Co X Y) for task Tx,y.
Defining the Encoder function. Given a query set Q, an Encoder is function, F : -> Q where St is the set of all finite-length sequences generated using clements from the set S = {lg, q(x)) q E Q, E X). Additionally, we require that Q contains a special query QSTOP which signals the encoder to stop asking queries and outputs the code for the set of query-answer pairs that have been asked. The process can be described as follows, given E and input sample x.
1. @1 = E(0). The first question is independent of x.
2. @k+1 = =E((,, (.))) All subsequent queries depend on the query-answer pairs ob- served so far for x.
3. If fL+1 QSTOP terminate and return (x)) (qi, (x))1.z as the code for x.
Note that each depends on æ, but we drop this in the notation for brevity. Note also that the number of queries L (Cooe((=)) for particular æ generalizes coding length in information theory. The query QSTOP constrains the code Code5(2) (I)) to prefix-free.
Defining task complexity. Given a joint distribution (xy y) and sufficient query set Q, we define task complexity, CX; Y), as the minimum over all encoders E (which are mappings from X to a subset of queries in Q) of the mean coding length:
Co(X;Y)= min Ex [ICode5(XXI]
s.t. plu x) p(y Code Vo E EX, (Sufficiency)
(2)
The first constraint ensures sufficiency of the code Vo E X. By this we mean that there ex- ists at least one Encoder E for which the first constraint of "sufficiency" is satisfied, where p'y (ode should be interpreted as the conditional probability of y given the event {x' E Code ( (x) = Codee((')). The solution to (2) provides the optimal encoder for task Tx,Y, Y, and Fig. illustrates the overall framework in detail.
X
Encoder (E)
NY (odeg(x)) Y
Input
4. Q
Output
Code (1)
Queries
from
.... (8 (X))]
user-specified cuery set
Figure I: Schematic view of the overall framework for quantifying complexity of a task T Txy..
Connection with Shannon entropy H. It can be shown that when Q is taken as the set for all possible binary questions X and if Y is function of X (which usually is for supervised classification problems (Kolchissyy et al., 2018)), ), then the solution, E*, to (2) gives a coding length within one bit of the entropy of Y. denoted as (Y). More formally, one can show that
H(Y) < C)(X;Y) = Ex [[Code E0 (X)] (x)] < H(Y +1.
(3)
As commonly used, we denote random variables by capital letters and their realizations with small letters.
3

---

Under review as a conference paper at ICLR 2021
Note that example of such an optimal encoder, E (z), is given by the Huffman code for Y.
Connection with task complexity & equivalence classes. Notions of complexity of an en- tity/object, often relate to the level of structural regularity present in the entity (Gell-Mann) (002). Co(X;Y) measures the degree of regularity present in the structure of Tx:y. This structure is im- plicitly defined by the conditional py]x (y r) and the query set Q. Notice that any partitions X' into equivalence classes.
[x] = (o' E x Code Code
The prefix-free constraint on the codes generated by E (due to ) ensures that Vz' E [2]], Vy e V. Pr|X=x/(y) = Pr|x=x(1)) (y). is then natural relate task complexity with the number of equiv- alence classes induced by the optimal E". The greater the number of equivalence classes, the higher the complexity of the task. This is because knowing the distribution py x²) for any one ele- ment x' in each equivalence class is sufficient predict Y. An extreme case of this would be the constant function which arguably has the simplest possible structure of any task Tx,.. The equiv- alence class in this case just X' since Pr|x y 2) is same for all x E X. Thus, the number of equivalence classes for the constant function is 1 (the minimum possible). This is expected since for a constant function there is no structure to learn from data whatsoever!
The following lemma (see Appendix A.1 for proof) relates CQ(X;Y) and the number of equiva- lence classes, the latter being not easy to compute from finite samples.
Proposition 1. Given a finite query set Q, b-valued query-answers {g(X)) and any 8 > O, the number of equivalence classes induced by the minimizer of (2) can be upper bounded by ([e(x)+)+QQ1/ 2 (x]) with probability of misclassifying X at most
Proposition | indicates that for the same Q, tasks with greater Co(X;Y) Y) will have larger complexity (by comparing the upper bound on the number of equivalence classes). This also illustrates the role different bases play. For example, in visual recognition tasks if one queries intensities of all the pixels in the image at once then YY = 1 (Öbserving intensities at all the pixels sufficient information to predict Y from X). However b in that case would be large (exponential in the size of the image). Instead if one queries individual pixels, would be the number of intensity values each pixel can take but Cx(X;T 1.
Properties of (X; The following proposition, whose proof can be found in Appendix A.2 establishes some key properties of our proposed measure of complexity.
A.2
Proposition 2. For any query set Q that is sufficient for task Tx,Y, Co(X; Y) satisfies the following properties:
1. Co(X;Y) 2 0. (non-negativity)
2. Co(X;Y)= = 0 iff X IL Y. (trivial structure)
3. Vf E X, F x', Zy E V. such that pr|x=z(v) # (v) then Co(X; Y) 2 Co(X; foral all tasks xx provided Q is sufficient for Tx.-. (total structure)
4. CQ(X:YY,y)) Y2) S Co(X;K) + C4(X:Y2) for any two tasks with px(x) and 1 X. (sub-additivity under union)
The property "trivial structure" captures the fact that Y independent of X, the learning task is trivial (i.e., there is nothing to be learned about Y from observing X or functions of X).
The property "total structure" captures the intuition that if for a given task Tx,Y, the conditional distribution functioini Py]x==(y) (v) is different Vz E X, then learning is "impossible" (assume Y is a categorical variable, which it is for most classification tasks) as no inductive bias would help in generalization to unseen inputs for such task. For example, Y f(X) where f x + y is injective.
The last property "sub-additivity under union" is especially interesting in transfer learning settings where source task Tx,v, and target task Txyy have the same marginal for X px (x) but dif- ferent conditionals PY,XX(11 5)) and PY.X (V2 It). Cq(X; V2) refers to the complexity of
4

---

Under review as a conference paper at ICLR 2021
task Tx: defined by PxY (z, U1 V2), where the corresponding sufficiency constraint in becomes
p(y1, v2/x) p(y 1/2 (ode (x))) Vo X, y1 V1,32 2/2
(5)
This property could potentially be exploited to predict the success of transfer learning for different choices of source and target tasks. Further, the assumption Yi Y2 X is not particularly strict as it simply implies given input X, knowledge of Yi is not required to predict Y2 and vice-versa.
c-approximate task complexity. In practice we are often interested in solving a task "approxi- mately" rather than "exactly". To accommodate this, we extend the definition of Sufficiency in 2 to e-Approximate Sufficiency by relaxing it to d (p(y x), Codeδ()))) S Ver E X.. Here, is any distance-like metric on distributions such as the KL-divergence, total variation, Wasserstein distance, etc. (Refer Appendix A.3
Having established the above properties our complexity measure, we note that unfortunately for any general query Q, the problem in 2 is known to be NP-Complete and hence generally intractable (Laurent & Rivest, 1976). As a result, we instead consider greedy approximation to Cx; Y) via an algorithm called Information Pursuit (IP) introduced Geman & Jedynak (1996). which we describe in detail next.
APPROXIMATING TASK COMPLEXITY USING INFORMATION PURSUIT
From this section onwards we will assume Q is finite set. Information pursuit (IP) is a greedy algorithm introduced by Geman & Jedynak (999) which provides approximate solution to The Encoder in IP, denoted as ETP, is recursively defined as follows,
Q1 E P (0) arg max (g((); QEQ
(6)
9k+1 ((q.
arg max QEQ
where an input data-point and stands for mutual information. In other words, IP chooses the next query qk+1 the one whose answer maximizes the mutual information with Y given the history questions and answers about chosen by IP till time k; i.e., given the event Bz,a := {a' X' (%i % h- = {9i, (xx")) h..). Ties in choosing qe are broken arbitrarily if the maximum is not unique. The algorithm stops when it satisfies the following condition:
OL+1 = ISTOP if max ((((X); B., = Vm E L + 11,,,1,,,,14777 L.T),
(7)
where T > 0 is hyper-paramette chosen via cross-validation, with the rationale behind this choice provided in Appendix A.4 We will denote this sub-optimal solution E'P as C)(X; To compute an approximation to (X; we modify the stopping criteria in to max T(a(X); Y| S and call this estimate C% (X;
3.1 APPROXIMATION GUARANTEES FOR INFORMATION PURSUIT
While in general is difficult to have any performance guarantees of IP, in the specialized setting in which Q indexes the set of all possible binary functions of X, such that H (g(X)) YY 44 E Q and Y is a function X, we have the following proposition (see Appendix A.6 for a proof).
Proposition 3. Given task Tx, with Y being a discrete random variable. If there exists a function such that Y fXX and Q is the set to all possible binary functions of X such that H (xg(X) Y) Vq then HYY < Co(X:Y) < +TY)+1
While the above proposition is often considered be true, this is the first time rigorous proof has been presented (to the best of our knowledge). Thus, in this special case, from 3 we have that Co(X; Y) < Cx(X;Y) + and thus the algorithm will be a tight approximation to our proposed complexity measure.
5

---

Under review as a conference paper at ICLR 2021
3.2 INFORMATION PURSUIT USING VARIATIONAL AUTOENCODERS NORMALIZING FLOWS
IP requires probabilistic models relating query-answers and data to compute the required mutual information terms in (6) Specifically, computing 9k+1 in (6) (for any iteration number k) requires computing the mutual information between ((X) and Y given the history Bz,* till time k. As histories become longer, we quickly run out of samples in our dataset which belong to the event Br..- As result, non-parametric sample-based methods to estimate mutual information (such as Belghazi et al. (2018)) would be impractical. In this subsection, we propose a model-basee approach to address this challenge for general task 7 Y and query set Q. In section 4 we adapt this model to the specific case where Q indexes image patches.
Information Pursuit Generative Model. Let Q(X) (x( E Q}. To make learning
tractable, we introduce latent variables Z to account for all the dependencies between different query answers and posit the following factorization of Q(X),
PQ(x)ar(((Ex),n.)) = II
Po(x))2y((()) (g(x) v)py (v)pz(n).
(8)
rEQ
Throughout the paper 1 and q(x) denote the realizations of Z and (X) respectively. Equation 8 is a reasonable assumption unless the answers (XX) are causally related to each other, (Reichenbach's common cause principle (Hofer-Szabó et al. 1999)).
In other words, assuming that the query-answers are conditionally independent given the hypothesis and "some" latent vector is benign and ubiquitous in many machine learning applications.
1. ((X) as object presence indicators evaluated at non-overlapping windows: Let Q be a set of non-overlapping windows in the image X with g(X) as the random variable indicating the presence of an object at the 9th location. The correlation between the qs is entirely due latent image generating factors Z, such as lighting, camera position, scene layout, and texture along with the scene description signal Y.
2. ((X) snippets of speech utterances: A common assumption in speech recognition tasks is that the audio frame features (g(X)) are conditionally independent given latent phonemes Z (which is often modelled Hidden Markov Model).
This latent space Z is often a lower- dive-dimensional space compared to the original high-dimensional X. We learn Z from data in an unsupervised manner using variational inference. Note, this assumption of conditional independence will not hold in scenarios where (XX) directly cause each other, for instance, in example 1, we considered overlapping patches.
Specifically, we parameterize the distributions (g(a) 77, Vy Q} with a neural network with shared weights w and call the Decoder Network. These weights are learnt using stochastic Variational Bayes (Kingma & Welling 2013) by introducing an approximate posterior distribution (7 y, Q(x)) parameterized by another neural network with weights & called the Encoder Net- work and priors py (y) and (2()).
Implementing E using the generative model. Using the learnt Decoder network mate the distribution Pu(x)y (q(x), y) via Monte Carlo Integration and compute 91 = E For subsequent queries (k >> 1), the computation of qu+11 requires the mutual information conditioned on current history B which can be calculated from the distribution
esti-
plg(x), y Br,k) = p(a(z)) (.. (r.)p((1 y, Br,)p Br,x)
(9)
To estimate the left-hand side of (9) via Monte Carlo integration, one needs sample N i.i.d. samples 17" ~ p(n y, Br,x) and compute + N pw(((x) rf(0) .yp(y Br.x), where the term p(y Br.a) can be estimated recursively with ply Br.o) : (y)) Appendix A.7 gives more details on these computations. Note, however, it is not straightforward to sample from this posterior p(1 y, B2,k) without resorting advanced Markov Chain Monte Carlo sampling techniques, which often suffers from the curse of dimensionality and is computationally intensive. To mitigate this issue we implement p(n) y, Bz,x) by another neural network trained learn this posterior.

---

Under review as a conference paper at ICLR 2021
y, Bo,k) with Normalizing Flows. We amortize the cost of modelling p(n y, B2,x) for each history encountered during the ExP recursion by assuming the existence of a function vu such that p(1) y, Bz,k) = Vl(lg, (.(x)) y. 11) Vz X for any iteration k.
Estimating p(1
We employ Normalizing Flows (Dinh from construct quence of invertible mappings of the form 7h = Vi([(y q: (x)))) y, 7)+1; each parameterized by neural network with weights n. such that To is constrained to be normally distributed. The composite function To (f(g (x))))==. y. n7; 7) a compo- sition of N neural networks with parameters {nthre(.......)) We call this network, Refer Appendix A.8 for details on the
et al. 2016) to approximate
data. Specifically,
Lag
V/ V-
xx-2
%
Figure 2: Conditional Inference Network.
L as the Conditional Inference Network (Refer Fig. training procedure.
Using the trained V one can sample from the posterior p(n) I y, Br,k), as required for ② for any observed history B2 The sampling procedure is as follows: (i) Sample no ~ N Ia) (assuming %o R2);; (ii) Compute 17- ' (L(s, (xx))) 1:ke V, no).
4 CASE STUDY: COMPLEXITY OF BINARY IMAGE CLASSIFICATION TASKS
As a practical instantiation of our theory, we concentrate on the task of classifying binary images. We choose Q as the set of image patches with answers being the intensities observed at the patch. The reason for this choice two-fold: (i) Patches provide a sufficiently rich query set to compare different learning tasks binary images and allow us to measure the task-specific input feature complexity of different tasks; (ii) From a practical stand-point, otate-of-the-art deep generative mod- els for binary images be assumed to be "perfect" models allowing to illustrate the usefulness of the framework with minimal modelling bias.
For all our experiments, we considered Q as index set all 3 x 3 overlapping patches in the image. This requires some modelling changes. Recall, (8) only holds if ((X) are not causally related. In case of overlapping patches, this assumption is clearly violated. So instead we model (8) at the level of pixels X, (X denoting the binary image, and j the jth pixel), p(z,, n,3) = II, ex P(r, 7. v))()))(n). Further network training details in Appendix A.9
Complexity increases with decrease in signal-to-noise ratio. We tested the effect of two different task-specific nuisances on O% (Y; for MNIST classification by, (i) MNIST-o:: randomly flipping pixels in MNIST images with probability a [0, 1]: (ii) MNIST-Translated: translating the digits by at most 4 pixels. Fig. 3 shows the results. The plot shows the trade-off between accuracy and task complexity for different values of e. To normalize for the effect of different datasets having different Bayes error rates, we report the trade-off using relative test accuracies which are the ac- curacies obtained by predicting Y according to arg max ply Bz, L. divided by the prediction made upon observing the entire image (all the patches indexed by Q). The results indicate that for almost all desired relative accuracy levels, MNIST, MNIST-0.0 and MNIST-0.1 are in increasing level of complexity. Our experiments also indicate that the complexity of non-centered MNIST digit classification is the greatest (evaluated at any fixed accuracy level).
Comparing different classification tasks. While in the previous experiment, there was ex- pected "correct" trend (complexity increases as nuissance level increases), the complexity ordering not so clear intuitively when comparing across datasets. We evaluated our framework to compute complexities of image classification on four different datasets of binary images, namely, MNIST, MushionMNIS' KMNIST, and Caltech Silhouettes. Fig. [3p reports the results. Our findings indi- cate that MNIST < FashionMNIST < KMNIST < Caltech Silhoettes in terms of task complexity at almost all relative test accuracy levels.
Recall L. is the iteration after which IP terminates

---

Under review as a conference paper at ICLR 2021
(8)
1.2
8.8-
08
0.00
0.6
Fashion MNSST
Caltach
MNIST
MNST--0.5
MINSS-LL1
MNIST
KMNIST
Sthouettes
0.4
04-
0.2
022
10
aapproximate Complexity (x(X)))
90
C-approximete Complexity Cg/X;3')
20
30
501
60
70
80
(d)
(f)
1.0
0.5
0.2
0.0
Figure 3: The plots (a) & (b) show the trade-off between accuracy and complexity as is varied (c). (d). (e) & (f) pertain to our discussion on interpretabiliry. (a) Complexity results on MNIST with different levels of nuissances; (b) Complexity results for different image classification tasks; (c) test image v² from Caltech Silhouettes dataset with class "Motorbike": (d) patches queried by FiP before lermination for d (shown by the overlayed coloured x 3 boxes); (e) Part of image x. observed through the queried patches; (f) Heatmap for probability a pixel would be visited by the IP Encoder for randomly chosen image with label "Motorbike" from the Caltech Silhouettes dataset.
Connections with interpretability. A common theme in all the different notions of interpretability in ML literature is a "short description length". An interesting consequence of our formulation is that when evaluated using queries that index image patches, it gives a principled way of selecting the most important parts of an image for a task. Fig. 3e. d, e, & fillustrate this with example. IP predicts the image label "motorbike" by just observing the edges of the silhouette which intuitively should be the most important parts of the image for this task. Indeed, Fig. 3 reveals that E visits these edges with high probability for any random image that has label "Motorbike". This heatmap makes sense since the data set only has centered images, for the general case depth analysis would required. This property IP could utilized to develop more interpretable MI. algorithms.
in-
5 CONCLUSION AND RELATED WORK
In this paper, we introduced a novel notion of task complexity intimately tied to query set Q. In the following paragraphs, will briefly discuss some relevant prior work with connections to proposed measure.
The information pursuit algorithm has roots in the seminal work of (Geman & Jedynak 1996). which proposes an active testing framework for tracking roads in an image. That algorithm was extended in (Sznitman & Jedynak] 2010) for face detection and localization, in Sznitman (2012) for detection and tracking of surgical instruments, and in (Jahangiri et al. 2017) for scene interpretation. Also, while (Sznitman & Jedynak 2010, Jahangiri et al., 2017) learn generative models for their tasks, their models are radically different from ours.
al.
The problem of classifying objects by sequentially observing different image locations has been recently re- re-branded as Hard Attention in vision (Mnih et al., 2014) Elsayed et al.) [019 Li et al.) 2016) and several deep learning solutions have been proposed. These methods typically try to learn policy for iteratively choosing different parts of image for solving different visual tasks. Opti- mization techniques from reinforcement learning are often employed to achieve this. High variance in the gradient estimates and scalability issues prevent their widespread adoption. It would be inter- esting to see IP can be combined with reinforcement learning- cearning-based approaches to design better reward functions to facilitate efficient policy search.
8

---

Under review as a conference paper at ICLR 2021
The information bottleneck (IB) method proposed by Tishby al. (2000) is perhaps the closest to our work. They define complexity in terms of the mutual information (MI) between input X and its representations X such that X preserves a certain amount (determined by a user-defined parameter) of information about the output variable Y. In a way, their measure of complexity accounts for the relationship between X and Y. However, this complexity isn't very useful for comparing different learning tasks. For instance, in Fig. & 2 in Kolchinsky et al. (2019) the MI between X and X for FashionMNIST and MNIST datasets are roughly the same for the same level of accuracy. This is a problem since we know from practical experience that MNIST is a much "simpler" than Fashion-MNIST. Interestingly, when Q is taken to be the set all possible binary functions of X our proposed measure recovers IB and its variants (Strouse & Schwab, 2017). That discussion however out of the scope of this paper. We note in passing that there has recently been work on quantifying information of a system under limited computation and model constraints (Xu et al. 2020) which could potentially be explored in the future in conjunction with our framework. of Q constrains the way information from X can be extracted to predict Y.
sense, the choice
Task complexity measures based on Kolmogorov Complexity are not computable (Li) 2006 Achille et al., 2019b] Vereshchagin & Vitányi 2004). These measures are based on the idea of finding the minimum length computer program that given input x outputs label y for every (I, in the training dataset. This is in stark contrast to definition which is a property of the joint distri- bution Pxy (x. 3) and not any given finite dataset. Computing (X; Y) is NP-Complete but not uncomputable. The implication of this is that there exist dynamic programming based solutions that exactly compute Co(;; LX;Y Y). The complexity of these algorithms are typically exponential in [Q] and so feasible only when IQ] is small. For large IQ), must turn approximations and Information Pursuit is one such strategy. On the other hand, an algorithm for computing Kolmogorov Com- plexity does not exist, let alone an efficient one. Besides computability, the more pressing issues with Kolmogorov complexity is that the measures are sensitive to permutations of the dataset which undesirable. Secondly, Kolmogorov complexity fails to distinguish between memorization and learning. A dataset sampled from Pxy (z. y) where Y is independent of X will have the maximum Kolmogorov-base complexity measure. However, from learning point of view there is nothing to learn an optimal strategy is to simply predict p(Y X)= p(Y) regardless of the value of X! So, the task complexity of such tasks should be O. [Achille et al. (2019b) presents for a more detailed discussion this. The proposed measure (X; is not dataset permutation--senstive since it is a property of the distribution pxy (z. y). Moreover, Co(X; = 0 when Y is independent of X (See Proposition 2 2) and distinguishes learning from memorization.
Our work is related in spirit to the work of Achille et al. (009bb which introduces an alternate measure of task complexity based on the intuition that the information stored in the weights of trained network can be used as a measure of task complexity. They show that their measure recovers Kolmogorov's 's complexity, Shannon's 's information, Fisher's information special cases, and is also related to TAC-Bayes generalization bounds.
REFERENCES
Alessandro Achille, Michael Lam, Rahul Tewari, Avinash Ravichandran, Subhransu Maji, Char- less C Fowlkes, Stefano Soatto, and Pietro Perona. Task2vec: Task embedding for meta-learning In Proceedings of the IEEE International Conference on Computer Vision, pp.
2019a.
Alessandro Achille, Giovanni Paolini, Glen Mbeng, and Stefano Soatto. The information complexity of learning tasks, their structure and their distance. arXiv preprint arXiv:1904.03292 2019b.
Mohamed Ishmael Belghazi, Aristide Baratin, Sai Rajeswar, Sherjil Ozair, Yoshua Bengio, Aaron Courville, and R Devon Hjelm. Mine: mutual information neural estimation. arXiv preprint 10Xi::8001.0402. 2018
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint arXiv: 08803, 2016.
Gamaleldin Elsayed, Simon Komblith, and Quoc V Le. Saccader: improving accuracy of hard attention models for vision. In Advances in Neural Information Processing Systems, pp. 702- 714, 2019.

---

Under review as a conference paper at ICLR 2021
Murray Gell-Mann. What is complexity? In Complexity and industrial clusters, pp. 13-24. Springer, 2002.
Donald Geman and Bruno Jedynak. An active testing model for tracking roads in satellite images. IEEE Transactions on Puttern Analysis and Machine Intelligence, 18(1):1-14, 1996.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. ICLR, 2(5):6, 2017.
Gábor Szabór-Szabó, Miklós Rédei, and László E Szabó. On reichenbach's 's common cause principle and reichenbach's 's notion of common cause. The British Journal for the Philosophy of Science, 50(3):377-399, 1999.
Ehsan Jahangiri, Erdem Yoruk, Rene Vidal, Laurent Younes, and Donald Geman. Information pursuit: A bayesian framework for sequential scene parsing. arXiv preprint arXiv:1701.02343. 2017.
Diederik P Kingma and Max Welling. 13Xiv:1312.6114 2013.
Auto-encoding variational bayes.
arXiv preprint
Artemy Kolchinsky, Brendan Tracey, and Steven Van Kuyk. Caveats for information bottleneck in deterministic scenarios. arXiv preprint arXiv:/808.0 07593, 2018.
Artemy Kolchinsky, Brendan D Tracey, and David H Wolpert. Nonlinear information bottleneck. Entropy, 21(12):1181, 2019.
Hyafil Laurent and Ronald L. Rivest. Constructing optimal binary decision trees is np-complete. Information processing letters, 5(1):15-17, 1976.
Ling Li. Data complexity machine learning and novel classification algorithms. PhD thesis, California Institute of Technology, 2006.
Mingming Li, Shuzhi Sam Ge, and Tong Heng Lee. Glance and glimpse network: A stochastic attention model driven by class saliency. In Asian Conference on Computer Vision, pp. 572-587. Springer, 2016.
Volodymyr Mnih, Nicolas Heess, Alex Graves, et al. Recurrent models of visual attention. In Advances in neural information processing systems, pp. 2204-2222 2014.
DJ Strouse and David J Schwab. The deterministic information bottleneck. Neural computation, 29 (6):1611-1630, 2017.
Raphael Sznitman and Bruno Jedynak. Active testing for face detection and localization. 1EEE Transactions on Pattern Analysis and Machine Intelligence, 32(10):1914-1920 2010.
Raphael Sznitman, Rogerio Richa, Russell H Taylor, Bruno Jedynak, and Gregory Hager. Unified detection and tracking of instruments during retinal microsurgery. IEEE transactions pattern analysis and machine intelligence, 3565):1263- 2012.
Naftali Tishby, Fernando Percira, and William Bialek. The information bottleneck method. arXiv preprint physics/0004077, 2000.
Anh T Tran, Cuong V Nguyen, and Tal Hassner. Transferability and hardness of supervised clas- sification tasks. In Proceedings of the IEEE International Conference on Computer Vision, pp- 1395-1405, 2019.
Nikolai K Vereshchagin and Paul MB Vitányi. Kolmogorov's structure functions and model selec- tion. IEEE Transactions Information Theory, 50 50(12):3265-33990 2004.
Yilun Xu, Shengjia Zhao, Jiaming Song, Russell Stewart, and Stefano Ermon. A theory of usable information under computational constraints. arXiv preprint 17X1192002,10689, 2020.
10

---

Under review as a conference paper at ICLR 2021
A APPENDIX
In proofs of propositions and lemmas we rewrite the statement for convenience.
A.1 PROOF PROPOSITION 1
Proposition. Given finite query set Q, b-valued query-answers {a(X) and any å > 0. the number of equivalence classes induced by the minimizer of (2 can be upper bounded by (a(XxY)+)QQ//2ox(() with probability of misclassifying X most
Proof. Let (X) be a random variable denoting the optimal code-length for X using E", the solution to 2 Since, S dx( [Q). From the definition, Co(X;Y) = Ex (de(X)) So,
Hoeffding's s Lemma we have
dg(X) CQ((x:Y) subG( 1012
(10)
4
Since (x) is sub- sabbgaussian, for any > 0
IP (o(x))Co(X) + log
8
(11)
Notice, the prefix-free nature of E naturally gives rise to tree with d(X) being the depth of corresponding tree TQ for input X. The number of equivalence classes is exactly the number of leaves of TQ. Given, each query-answer ((X) is b-valued. So we can upper bound the number of
leaves by replacing Te with balanced b-ary tree with (C leaves called To- To can be constructed from To follows:
1. For any leaf node with depth d(X) < CQ(X;Y) +1Ix) 2 log 3 vacuously increase the depth till equality achieved by repeatedly asking the last query. For any internal node in To that is not balanced, add vacuous subtrees by randomly selecting queries from Q (no x E X' would sent to these new subtrees) to make the tree balanced with each internal
node having b children nodes. As a result, Va E X' with d(x) < Co(X; Y) +Q)+ log }.
To (X) would compute the same posterior as (X(X), that is pvy Code (z)). and thus not make error.
2. For any leaf node with depth d(X)= Co(X;Y) IQ) log 1.- cut the path at depth u(X) Co(X;Y) 1Q) / log f by merging the subtree rooted depth u(X) and creating a leaf node. An input E X' sent to this new leaf node would be misclassified. The probability of such an event given by (IT).
A.2 PROOF OF PROPOSITION
2
Proposition. For any query set Q that is sufficient for task Tx,,, CY(X;Y) satisfies the following properties.
1. Co(X;Y) 2 0. (non-negativity)
2. ColX;Y) = iff 11 Y. (trivial structure)
3. IfV x' E X,x + x', By E V, such that pv)x=z(V) + PY|X=x( (2), then (X;Y)) 2 Co(X; Y) for all tasks T x provided Q is sufficient for T X (total structure)
11

---

Under review as a conference paper at ICLR 2021
4. Y,, < Co(X;K) + Cx(X:Y)) for any two tasks with X px(x) and Y1 1 Y2 X. (sub-additivity under union)
Proof.
1. Follows trivially from the definition.
2. For proving the "if" part, observe that if X TL Y then Pv|x = py vy) Choose Ej to be an encoder such that q1 gSTOP. Then
Ex
@oode Pa (x))) =0
E1 is trivially prefix-free (all æ E X' gets mapped to the same code 0). Recall that MyyCoode Ei (x)) should be interpreted as the conditional probability of y given the event far X Code Bi (x)
Code (x'))- Since Vr E X, Code Bi (x) = 0, p(y Code Fi (x)) (x)) = p(y X) = p(u). Hence, E, also provides a sufficient code and thus is feasible solution to the optimization problem in (2). From property 1 we know that E achieves the optimal (x;X;
The proof for the "only if" part is very similar. Consider E' as the optimal solution to l" (z) = 0 Va E X. Since E is sufficient, ply x) ply Code (x)) p(y) Vx E X, y E y. This implies X 11 Y.
and CQ(X;Y) = O. This implies Code
3. Let Er denote the minimizer of (2) for the task Tx,y where Y given is distributed as stated. From sufficiency we know that no two different inputs x' E X could have the same code, that is, Code Er (x) * Code Er (x') Vx, E Xx + x'. Consider any other task Tx,y defined by p(X, Y) with the same marginals X ~ "Px (I) but possibly different conditional Y "Pix (g x) such that Q is also sufficient for T Tx,y- ET feasible solution for 2 with respect to task Tx,y since p(ū Code Er (z)) p(ū {x))) Thus, C)(X; < Ex (Codee (X))) for any other task Tx,y for which Q is sufficient.
4. Let Ej and Eg be the optimal encoders for tasks Tx,y, and Tx:ya respectively. Construct an encoder E12 for that task Tx:y,.y, by concatenating the two codes. It not hard to see that
Euz The inequality is due to the fact that (query.answer) tuples can overlap in the codes con- structed by two encoders E₁ and Eg for the same input x. E12 is prefix-free by construc- tion. Now, for any observation of output Y1
Ex (rood55e(X)) s Ex ([Code E. (x)) Ex (C
p(un Code (x))))
= p(1 [Code Ei (x) U Code
p(vi I (a' X: Code Es (x') Code (x'))
(x') = Code (x) U Code
Ea =((11 {x' E Code En (x') = Code Ei Q (x)} n fa' E X Code Fs (x') Code Q (x)))
p(v1 x:)
The last equality appeals to the fact that En satisfies the "sufficiency" constraint in 2 for
task Tx:y- Similarly, p(yz Code Fu2 (xx)) = p(yz x) for any observation y/2 of output Yz. Given, Y1 11 Y2 X. This implies Vo E X
p(y,, 92 | x) p(y1 xx)((12 x)) p(y) |
Code Er2 (x) )lua Code
P(U1,02 U2 Code E1e (x))
12

---

Under review as a conference paper at ICLR 2021
This proves E12 is sufficient for the task T(X;Y; Y2). Since E12 is a feasible solution for the optimization problem with respect to T(X; Y1, Y2) we get the required inequality.
A.3 C-APPROXIMATE COMPLEXITY OF TASK
In practice, we are often interested in solving a task "approximately" rather than "exactly". This requires introducing notion of approximate sufficiency instead of exact sufficiency, and extend the definition (2) to incorporate this.
(X; == min E [[Code[(X]]
(12)
E
s.t. d (p(y v), ply Code@(x))) Se Vor E X (Approx. Sufficiency)
(13)
Here, d is any distance-like metric on distributions such as the KL-divergence, total variation, Wasserstein distance, etc. Additionally, if d is convex in both its arguments, symmetric and sat- isfies the triangle-inequality then C5 (X;) satisfies the properties Proposition with two key differences:
1. In Property
C)(X;Y) is the complexity of the task for which d (Prjx= x (v)) 2c Vx, o' =x
2. In Property 4, the relation is
12) s c)(x:N) +
A.4 TERMINATION CRITERIA FOR E
Ideally we would like terminate (E'P outputs QSTOP) after steps if ply æ) = ply x²) Vr, E BR,L, y E E However, detecting this is difficult in practice. We have the following lemma.
(14)
Lemma A.4.1. Assume IL ((X) X Vqq E Q. If event Br, satisfies the condition specified by (44 then for all subsequent queries Jms m 2 L, maxzeQ (g(();; [a.m) 0. Since ties are broken arbitrarily the maximum not unique, EIP chooses any q E Q as subsequent query qm-
Refer to Appendix A.5 for a proof. The assumption Y 1L ((xx) X Vy E Q is generally true since we have the following Markov Chain Y - X (X) bq E Q.
Using Lemma A the correct stopping criteria should be |0) max [gg(X); Ba,,) Vm 2 k, S IQ)) rEQ
== (n: (1,2,....
(15)
Evaluating (15) would be computationally costly since it would involve processing all the queries for every imput x. We employ a more practically amenable criteria
f1 4STOP if max (g((); () 0 Vm E (L, 1, L T
(16)
qEQ
T 0 is a hyper-parameter chosen via valsda-aliitionn. Note, is possible that there does not exist any informative query in one iteration, but upon choosing a question there suddenly appears informative queries in the next iteration. For example, consider the XOR problem. X R and Y E 1J. Let Q be the set two axis-aligned half-spaces. Both half-spaces have zero mu- tual information with Y. However, upon choosing any one as Qı, the other half-space suddenly informative about Y.
A.5 PROOF OF LEMMA A.4.I
Lemma Assume IL (X)) X 4q E Q. If event B satisfies the condition specified by (4 then for all subsequent queries qms m 2 L, max arbitrarily, F.P chooses any Q as subsequent query qu-
O. Since ties are broken
13

---

Under review as a conference paper at ICLR 2021
Proof. Recall each query 9 partitions the set X' and B is the event fa' X {q: q((x)) {ge, (u(x))::)) It is easy to see that if Bz, satisfies the condition specified by (44 then
P(y Ba.m)= Ply x²) Va' E Ban Vm 2 L, Vq E Q
(17)
This is because subsequent query-answers partition set in which all the data points have the same posterior distributions Now, Vy E Q, Va E Rangel1); E E
p()(X) = a, v Bz,m) = p(a(X) =a aal Br,n) ((X) a, Br,m)
(18)
eq: chain rule of prob is just an application of the chain rule of probability. The randommess in (X)) is entirely due to the randomness in X. For any E Range( (Ag) y E
p(y (X) a, Bz,m)=
E
ply, x6 Bu,m)
e' (f
plu x', a, Ba.n a Ba,m)
s'E Ba, ((EXX1(())=
E
ply x' a')p(a' a, Be.m
(19)
s' w.B.e.meeeEeeee... ((EE))(())=
= =p(y Ba.m)
p(e' a, Ba.)
= ply Br,m)
The first equality an application of the law of total probability, third due to conditional indepen- dence of the history and the hypothesis given X x' (assumption) and the fourth by invoking
(17))
we obtain Y 1 q(X) Brm Vm L. Q. This implies that for all subsequent queries qm m > L, max,cQ (q((); B2, = Hence, Proved.
Substituting 19
18
A.6 PROOF OF PROPOSITION 3
Proposition. Given task T with Y being discrete random variable. If there exists a function such that Y f(X) and Q is the index to all possible binary functions of X. such that ((((X) Y) Vig E Q then H(Y) I Co(X;Y) S H(Y)+ +1
We make remarks before turning the proof. Remark 1:
The task is to determine the true state of latent variable Y E based querying observed data point æ. We assume Y f(X) with f unknown. Were Y observable, the natural queries would be indexed by subsets D c yi, one query for every D V, namely q(Y) and 0 otherwise. (This is essentially the classic "twenty questions game", but with an "oracle" and "complete tests".) There are 2D such queries and obviously they collectively determine Y. Now since Y f(X), these queries are, least implicitly, functions of the data X, but need realizable functions, not requiring knowledge of f. So our fundamental assumption is that for each subset D y the corresponding subset D' X (D' ff (D)) can be checked for inclusion of X, i.e., Y E D if and only if X E D'. Or, what is the same, binary query ((X) (and still denoted q for simplicity) with (XX = (Y)). effect, we are assuming that whereas we cannot determine Y directly from X, we can answer simple binary queries which determine Y and can be expressed as observable data features.
if D.
The sequence of queries q1, 0.. generated by the IP algorithm for a particular data point can be seen as one branch, root to leaf, of decision tree constructed by the standard machine learning strategy based on successive reduction of uncertainty measured by entropy:
Remark 2:
We refer the distribution p(y for any X the posterior distribution of
14

---

Under review as a conference paper at ICLR 2021
Q1 arg m [(g(X);)) 9h+1 arg ma (AA where the _ is the event that for the first & questions the answers agree with those for z". We stop determined. Whereas a decision tree accommodates all æ simultancously, the questions along the branch depends having a particular, fixed data point. But the learning problem in the branch version ("active testing") is exponentially simpler.
Y is
Proof of Proposition 3.1: The lower bound H(Y) - Co(X:Y) comes from Shannon's 's source coding theorem for symbol codes.
- 11 (g()) =() since Y determines g and hence also g the second entropy term zero (since given H (X) YY) 0). So our problem is maximize the conditional entropy of the binary random
Now for the upper bound, since (
B2o,k) and
variable ((X) given a, So the IP algorithm clearly just "divide and conquer":
91 arg max (g())),
QEQ
M++1 = arg max H (g(X) Ba
QEQ
Equivalently, since entropy binary random variable is maximized when P(p) = 2'
1 2
4k+1 arg min P(g(X) = =1 QEQ
Let Va. the set of "active hypotheses" after queries (denoted as As), namely those with positive posterior probability: P(Y y| > 0. Indeed,
P(B y)p(y)
P(Y = B/ E, P(B v)p(u)
lysp(k)
EvEAL p(y)
since
P(Baa = = 1, e y $ A
In particular, the classes in the active set have the same relative weights as the outset. In summary:
p(u)/ EA.. p()), E A 0,
otherwise
The key observation to prove the theorem that if hypothesis y generates the same answers the first more questions as yº, and hence is active at step m, then its prior likelihood p(v) is at most 2 (m-1)) m 1, 1,2, ... This is intuitively clear: if y has the same answer as y on the first question, and p()²) > J. then only one question is needed and active set empty at step two; qi (v) = qı () and (3) = 42(x²) and p(y") > 1. then only two question are needed and the active set is empty at step three,
15

---

Under review as a conference paper at ICLR 2021
Finally, since C, the code length, takes values in the non-negative integers {0, 1....,
Co(X:Y) E[C]
= Σ P(C 2 m)
P(p(Y) < < (m-1))
Σ
p(u)
m= y-p(1) <2 (m-1)
E (p())<2-(m-11)
VEY m=1
Σ p(k)(1 log)(
NEY
H(Y)+1 +1
A.7 COMPUTING MUTUAL INFORMATION FOR (6)
A.7.1 IMPLEMENTING E!P; COMPUTING THE FIRST QUESTION
Once the Decoder network has been learnt using variational inference, the first question @i be calculated as per (6). Since the mutual information is completely determined by p(g(x), y). which obtained by numerically marginalizing the nuisances Z from (8) using Monte Carlo integration.
dy E Q
P)(x)((((2)) PQ(X)zY (Q(z),
((()))((((())) v)py (n)
(20)
N
Σ
(g(x)) y. (7 Jpr (v)
N
In the last approximation, (=)((()) y, ()) is the distribution obtained using the trained Decoder network. N the number of i.i.d. samples drawn and 17¹ pz (1))
A.7.2 DERIVATION
/ pla(x). n.y Br,k)dn
p(a(x),u1 Bz,k)
/ p(a(z) n.y, B y, Bouyp(y Ba,x)dn.
(21)
/ pla(z) 17.)p(1 y, B2,)((( B2
The first equality is an application of the law of total probability. The last equality appeals to the assumption that {g(X), E Q} are conditionally independent given Y, Z (8).
A.7.3 RECURSIVE ESTIMATION OF p(y Bz.k)
Finally, pvy) Bx(x))) (required for (9) is computed recursively via the Bayes' theorem.
ply Br.k) x ply, Br,k)
(g)n())1)) y, Br,K-1)
(22)
(()((2) Be.k-1)p(( B2R--1)
16

---

Under review as a conference paper at ICLR 2021
Bz,u 0 (since no evidence via queries has been gathered from yet) and ply B2.u) py (v). p(y Bx,k) is obtained by normalizing the last equation in such that Σy ply) Bz,k) =
P(gx (x) Ba, can be estimated using 9
A.8 TRAINING THE CONDITIONAL INFERENCE NETWORK
A normalizing flow is a sequence of invertible transformations that takes a random variable from simple source distribution (say Uniform or Gaussian) to an arbitrarily complex multi-modal target distribution. These invertible transformations are parameterized by deep neural networks that can express richer family of distributions than the Faussian/Uniform family. Specifically, we construct sequence of invertible mappings of the form r7 ( (9. (1=))]1ss- y, 71+1:70) each parame- terized by a neural network with weights "M, such that iuu is constrained to be normally distributed. The composite function foo (V(((, (a))) U, T7 is composition of N neural networks with parameters 7 = (EE...1......
We call this network, V, as the Conditional Inference Network. (Refer Fig, for a pictorial depic- tion). By the Ohtange-ff-varabee formula for probability densities, p(n y, B2,x) can be written as.
Pn(n y, Br,k)) Pmo (()(()((((())))))))))))))))))))) V V, (..))
(23)
7) is invertible and the determinant 23 is efficiently com- putable, the family of functions used is often constrained to those that admit an upper/lower tri- angular Jacobin. The normalizing flow model employed here is the realNVP model introduced in Dinh et al. (2016). For training construct dataset DD from given dataset D (of N i.i.d samples (xr, y²)
To ensure (n. y, (gg qx))) ((a)))
pxy xr y)) in the following manner.
1. Since we assumed Q is finite, fix an enumeration. For every (x. y) in D, evaluate all the functions Q = {q E Q) and obtain the sample (Q(x), Sample k pk(k), then sample k random positions in Q(x) as my ~ Par (mr)) pk(k) and pM are user-defined distributions. In our applications PR Pk(k) is taken to be Poisson(A 10) and
PM (m²) [1,, 2, .... (Q}}
2. Sample (nly. (x))) using the trained Encoder network.
3. Mask (xx) according to positions in my to obtain k-length sequence {(g, g(x))) In this way, we obtain samples from the desired joint p( (K, Bx (x))), Y,n). Bx (X( is K-length random sequence ((g, ((X)) E Q) for some Q Q.
The weights y are then learnt using stochastic approximation by optimizing the following objective using D*
max EK, Bx M.
max E (x, (Bxx(X), Y,
(24)
log V " 1 [Bx (X), Y,n,))
The second equality is obtained by substituting 23 in 24
p(7)) = (0,
To understand the objective [4 assume general random variables & and v. Let our proposal distribution be p(wlg) and the true distribution be p(vlE). Consider loss function
KL(P(((E) = / p(vlE)oog p(vlE)d
(25)
/ p((l)E)og d)
17

---

Under review as a conference paper at ICLR 2021
Since 25
should hold Vξ, take expectation over &.
E [[LKL((((())
p(E)p(v(())og pl
/ ((E)p(ulE))) E)g d(vlE)
(26)
/ p(c, Vloog pl
/ ple, lbg p(uld)
min Eg (y( P((NE)
/
max ((PEE)
plc, v/ Yog ((vbl)d
(27)
max p(vIE)
B log p({({))
The first term in 26 disappears since it does not depend on p( Compare (7p and 22 Sub- stitute vp == and C = (K, Bx (x), (X),)) The proposal j(-) is parameterized by the Conditional Inference Network P.y (nly, B2,k)-
The issue that we don't have access to the true distribution p(t(() to generate samples for a training and learn an optimal p(v(E) for each =\t However, have access to the joint plE, v) == p(k, (x)),, y, n) from which we could generate data D for optimizing (27) using stochastic approximation.
A.9 NETWORK ARCHITECTURES AND TRAINING PROCEDURE
A.9.1
ENCODER AND DECODER NETWORKS
For the Information Pursuit Generative Model in subsection troduced in Higgins et al. (2017). The encoder-decoder architecture used depicted in Fig.
3.2 we implemented a B-VAE as in-
Notation for Fig.
L(x, y) Linear layer with x input units and output units, followed by a BatchNorm layer and YeakyRELU activation.
C_æ - Convolution layer with æ x filters followed by BatchNorm layer and IcakyRELU activation.
C.x Same as C.z. followed by a Maxpool layer.
DC___uy_ Transposed Convolution layer with x y x y filters and stride 2, followed by BatchNorm layer and leakyRELU activation.
Slope for leakyRELU activation was taken to be 0.3. BatchNorm and leakyRELU activation was not applied to the output layer of the encoder network (Fig. 44). BatchNorm was not applied and the leakyRELU activation was replaced by Sigmoid in the output layer of the decoder network (Fig. 4).
Training. The 3-VAE was trained by optimizing the Evidence Lower BOund (ELBO) objective,
maxx 6.,0)
E By (nlv
200 2o pm (z. In, (
(28)
3KL (0 ())(()
using ADAM with learning rate 0.001 and momentum parameters 3 0.9 & B2 - 0.999. was taken as 4.0 for all experiments. The prior over latents Pz (1) is taken as (0 J100) and py (v) estimated from the empirical distribution of the outputs from the training data. Data augmentation was performed on MNIST and its variants via elastic deformations. No Data augmentation was done for the other datasets. The network was trained for 200 epochs.
18

---

Under review as a conference paper at ICLR 2021
Sigmold]i
D
C32
C128
DC64_2.2
C256
D064
L/30,256)
Aug. Poo120
3_128,3.1
DC256
(51222048)
(/512,2048)
4,1
(2048.100)
((20481000)
L(100226))
Z -2
N(0,1)
Figure 4: The encoder-decoder architecture used in the 3-VAE network. Recall from section 3.2 X, are the image pixels, Y is the class label and are the nuisances. (a) Encoder Network: Takes the image (1....2
and class label Y inputs and predicts the mean μ and diagonal covariance matrix 2 of the nuisances Z. The weights of this network are denoted as w in the main text; Decoder Network: Takes the nuisance and class label Y inputs and predicts the Bernoulli parameters of each pixel X, in the image. The weights of this network are denoted as in the main text. Best viewed in colour.
A.9.2 CONDITIONAL INFERENCE NETWORKS
Unless stated otherwise, the notation for the figures in this section is the same as introduced in subsection A.9.
Network Architecture. For the Conditional Inference Network, introduced in Section 3.2 imple- mented variant of the flow network introduced in Dinh et al. (2016). Fig. depicts the overall architecture.
In Fig. 5 for our use-case with binary images and patch queries, {g:, (=)))== represents a masked image (sequence of patches observed), y denotes the class label, 1) are the nuisances distributed according to the target complex distribution and 7) are the transformed random variables distributed according to uni-modal standard Gaussian distribution. Each triplet of (Actnorm Layer, Permute Layer, Affine Layer) forms layer of the flow network. The overall network is 25 layers deep. Each layer represents the function Y ( q(x)) 1is, M ); 7), with weights 7r. The weights of the flow network is denoted as = {' hee 20.1,....24. In what follows, we describe in detail each of the layers in triplet.
Actnorm Layer: has been proposed in literature to add a Batchnorm style layer with learnable scale and shift parameters stabilize network optimization. Fig. 6 depicts the Actnorm layer network architecture used.
Permute Layer: This layer implements permutation operation.
1
permotee
Pnp-
actnorm
(29)
19

---

Under review as a conference paper at ICLR 2021
Actnorm Layer
(1i (x())
Layer
y
Affine Layer
n
Figure 5: Overall architecture of the Conditional Inference Network used based on RealNVP normalizing flows. The network takes {g. (;))) Y and nj as inputs and performs 25 trans-
formations 1) + 924 + 1/23 DNN (x(3)) ) 1sk 1441 ()) in Fig.
Yo. Each transformation is referred to as i
{ai q: (2) Fi:k
C32
C64_MM
y
C256_M M
L(10,256)
PoolDD
Concat
4S512,1024)
L(1024,256)
L(256,1)
L(256,1)
b
aetnorn
b
n
Figure 6: The Actnorm layer used in each layer of the Conditional Inference Network. This layer takes n, fgt, (=*)))::)) and
input and outputs np- aotnorm denotes element-wise multiplication.
Here P is a permutation matrix which swaps the first 50 dimensions of n--1 dimensions. Recall, TI e 100 VI E (O, 253..
petnorm with the next 50
Affine Layer: This layer implements the following operations.
11 11 split Split(ypeenn permute
(30)
20

---

Under review as a conference paper at ICLR 2021
8, = NN (h (z)
(31)
0 h
(32)
af 1 ost (1 - s)
denotes element-wise multiplication.
T --1 concat 10
(33)
The split operation in (30p divides m into two halves, such that, h2_1 l6 m [0 50) and
h²_ = 7 permute [50 100].
Fig. depicts the network architecture used for the N Nafine in 31
{gi Qá (a) 1:kk
C32
C64_M
C128
h
y
C256 M
L(10,256)
Avo_PD
L(50,256)
Concat
L/768,2048)
(/2048,1024)
((1024,50)
L(1024,50)
Sigmoid()
Figure 7: The N Nagine used each Affine layer (31 of the Conditional Inference Network. This layer takes h111 (gc, ( (1)))s)) 1.k and y as inputs and outputs scale vector and shift vector t.
Notice, each of the layers are invertible functions and hence their compositions (the 25 layer deep flow network) is also invertible, which is key requirement for (23)
Training. The dataset for optimizing 24
generated outlined in section A.8 (denoted as D*). The Conditional Inference Network was trained by optimizing this objective using ADAM with learning rate 0.001 and momentum parameters 81 0.9 32 0.999. L2 regularization was added to stabilize the training and prevent gradients from exploding (a common problem in training normalizing flow networks).
scheduling was done for the regularization constant. Namely, we optimized (24) with L.2 regularization parameter {1012 10a 102) for 5 epochs each. Finally, the L2 regularization was relaxed (that is, regularization constant was made 0) and the network was trained for 500 epochs.
21


Reviews:
[{"review_id": "w15-fGETE_", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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 claims that existing measures of complexity such as entropy are not suitable for measuring task complexity since they focus on the complexity of X rather than the predictive relationship from X to Y. The paper argues that mutual information is not useful for comparing different learning tasks, as two tasks (MNIST vs Fashion-MNIST) can have similar MI but intuitively different complexity (second-to-last paragraph in related work). The paper proposes a measure for task complexity based on the number of queries required to predict a label of an input. The form of the queries is not specified, and the provided examples include half-space queries, single feature (decision-tree-like) queries, or high level semantic queries.  The proposed method instead considers a query generator E, then encoding X as the answers to the sequence of queries generated by E, and predicting Y from the answers. The complexity of a task is related to the number of equivalence classes induced by the input X and the query generator E.\n\nI think the general premise is interesting, although I am not familiar with the related work (eg Achille, Tran) so I can't comment on how novel or different the idea of this paper is. Although the paper claims to have the first subjective notion of task complexity, to me this seems like more of a drawback since measures of complexity should be as standardized as possible, so as to allow comparison between different works. It may have been useful to cement down the three versions of complexity described on page 2, so future works can use them directly (for example provide details of measuring visual semantic complexity; and if it relies on extracting latent features of a neural net, i also wonder how close/different this is to [Achille]). \n\nAlso, the paper claims the drawback of Kolmogorov complexity is that it is not easily computable, but the methods described to compute the paper's proposed complexity are also highly involved, and requires multiple layers of approximations. It would have been helpful to have a more in-depth discussion of how (if at all) the proposed method is easier computationally compared to the other methods.\n\nIn proposition 1, epsilon seems not to have been motivated yet? The task complexity in Eq2 did not seem to have any notion of error, so why is there a probability of misclassification in prop 1?\n\nThe notation in Equation 1 looks off to me, since the RHS conditions on the set of all x's with the same encoding. Don't we want something to the effect of: p(y|x) = p(y|x')  for all x, x' such that A_q(x) = A_q(x') \\forall q ?\n\nThe prefix-free constraint seems like it can be avoided if we just include q_STOP in the code? This seems more natural to me, and you can avoid the extra notation and sentences of explanation on the bottom of page 3.\n\nCondition 2 in Prop3: we are assuming that y is categorical, and p_{Y|X=x} is a distribution over the labels in Y? Or does p_{Y|X=x} have all its probability mass on a single label? I assume it is the latter case, but writing it in terms of two inputs disagreeing \\forall labels y is confusing when they are only assigned to one label each (in fact, shouldn't it be \\exists y where x and x' disagree, instead of \\forall y?).\n\nI also didn't quite understand how the conditional inference network takes in {q, A_q(x)}_{1:k}. Isn't this not a fixed length sequence, in fact we don't even know the length of it beforehand since we decide when to stop at runtime based on the stopping condition? So in Fig2, how are the \\Psi's able to take in variable-length sequences?\n\nI'm curious about the exact cost of each iteration of the information pursuit algorithm. Given p(A_q(x), y | B) in Eq.9, do you compute p(A_q(x) | B) and p(y | B) exactly to get the mutual information, or do some sample-based approach? How many values can A_q(x) take on? And we need to do this for every possible query q \\in Q in order to get argmax_q, so if A_q(x) can take on m values, are you doing O( |Q| m ) number of queries of the distribution p?\n\nOn the point of mutual information not being directly useful to predict difficulty in mapping X to Y, it seem that this paper \"A Theory of Usable Information under Computational Constraints\" Xu et al. [ICLR 2020] is very relevant. For example under a limited computational model, perhaps MNIST will have higher mutual information than Fashion-MNIST.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Uc2Cs8WgaoR", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 1, "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 proposes a new measurement for the complexity of learning tasks. The proposed method measures the complexity of a learning task by the minimum expected number of questions that need to be answered to solve the task.\n\nStrengths:  \nThe idea of using the minimum expected number of questions that need to be solved for measuring the task complexity is an interesting idea to me.\nThe paper provides theoretical justifications and connections with existing information theories. \nThe paper is generally clear and well constructed.\n\nWeakness:\nThe experimental analysis is weak, only a simple case study is provided in the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "HFDLlTPlyni", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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 proposes a method to quantify the complexity of a learning task. The paper is motivated from the “20 questions“ game where an agent computes the answer (label) via a sequence of questions asked on the input data with answers given by an Oracle (simple functions of the data, in this case). The authors formalize this process and define the complexity of a learning task as the smallest number of questions from a given set Q necessary to predict the labels accurately averaged across the dataset. Information Pursuit (IP) of Geman & Jedynak 1996 is used to instantiate this definition using variational and normalizing-flow based models to learn the conditional distributions. Experimental results are shown for MNIST, Fashion-MNIST, KMNIST and Caltech Silhouettes datasets.\n\nThe main intellectual novelty of the paper is to define the complexity of a learning task using the number of questions. This comes with certain caveats that are discussed in the detailed comments below. While the paper is understandably a first step in this interesting program, more crisp experimental results are necessary before we can ascertain the utility of these ideas.\n\nDetailed comments.\n\n1. I have a philosophical gripe about this framework. It is widely observed that ensembles of decision trees which have been expanded until there is only sample at each leaf or, more recently, over-parameterized deep networks generalize better for machine learning tasks. The definition of task complexity developed in this paper does not relate to “learning” tasks. Indeed the complexity of the same task under decision made by above over-complete decision tree would be very large. The present paper is an attempt at computing the complexity of the conditional distribution p(Y | X) using a different “basis” that comes from the Oracle’s answers to the queries.\n2. The complexity of a learning task should also be a function of the hypothesis class that is being used for the task. This is exactly the benefit for using quantities like VC-dimension. Why not, for instance, define the complexity of a task as the minimum-description-length (MDL) of the model that achieves at least a generalization gap of epsilon? Indeed, the prior over the hypothesis class in MDL is similar to the prior over the query set Q in this paper. There is recent work that captures the complexity of transfer learning while incorporating the hypothesis class, e.g., https://arxiv.org/abs/2011.00613, that the authors could seek synergies with.\n3. The above two points are also seen in the claim about sub-additivity. Sub-additivity is a difficult property to have in general. If the tasks Y1 and Y2 conflict with each other, e.g., if they do not share any features and the model does not have sufficient capacity to learn both sets of features then the complexity of learning the two tasks simultaneously tasks should be _larger_ than the sum of their individual complexities.\n4. The factorization in (8) need not be assumed. Since variational Bayes is used to approximate the true distribution on the left-hand side, one may simply say that the right-hand side is a particular variational family. This also applies to the paragraph above Fig. 3.\n5. More refined experimental evidence is necessary before we can understand the merits of this definition. I find the current results difficult to appreciate, e.g., MNIST-0.05 and MNIST-0.1 should essentially have the same test error using any off-the-shelf CNN. Why is there is a gap between the relative test accuracy around, say, epsilon = 10 in Fig. 3a? I suspect this is an artifact of the variational/normalizing flow framework which does not learn good representations with noisy data and thereby results in a degradation of the validation error.\n6. The learning task for classifying images in MNIST-translated should have the same complexity as that of MNIST because CNNs are translationally invariant. That this definition leads to a higher complexity for the former indicates that the setup where the agent searches for patches of input images is the real reason for this seeming increase in complexity.\n7. It would be good to compare the ordering in complexity of these tasks using some other baseline method in the literature to compute the task distance, e.g., Task2Vec.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a measure of task complexity based on a decision-DAG like "encoder" where we iteratively branch on some test on the input and the selection of future tests depends on the answer to previous tests until we reach a terminal node in the DAG.  We require that if $x$ and $x'$ reach the same terminal node then $P(y|x) = P(y|x')$.  The complexity of the task (the complexity of the distribution $p(x,y)$) is the minimum over all such DAGs of the expected depth of the terminal node for $x$ when drawing $x$ from the marginal $p(x)$.

The reviewers are not enthusiastic and I agree.
Decision: Reject