QUANTIFYING TASK COMPLEXITY THROUGH GENER-
Year: 2020

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.

heading: 1 INTRODUCTION
text: 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 in a 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 of machine learning such as transfer learning, multi-task learning, un/semi/self-supervised learning, and domain adaptation.
In classical information theory, the entropy of a random variable X is a useful measure of complexity for tasks such as compression and transmission, which essentially require reconstructing X . However, the entropy ofX is insufficient for measuring the complexity of a supervised learning task TX,Y , where the goal is to predict an output Y from an input X , i.e., to estimate the conditional pY |X(y | x) from a finite set of samples from pXY (x, 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. Information-theoretic measures such as mutual information, information 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 & Vitá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., 2019a) proposes to quantify task complexity by measuring the information stored on 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 or assume trained models, but makes strict assumptions that limit its broad applicability.
In this work, we introduce a novel perspective on task complexity which generalizes classical measures from information theory. Specifically, one well-known interpretation of classical Shannon entropy is, given a 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, on the domain of X , then Shannon entropy essentially asks what is the optimal sequence of queries to compute {q1(X), q2(X), . . . : qi ∈ Q} (i.e., how to encode X as a 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 variable Y . Further, notions of complexity can potentially be made more relevant to a specific task by 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 a 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:
• Decision boundary complexity: Here,Q is the the set of all possible half-spaces in Rd (assuming X ∈ Rd) and q(x) is a binary function response indicating whether x lies in a particular half-space (q ∈ 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 q is of the form q(x) = xq , where xq is the value observed at the qth entry of x. 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 to 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 a 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 inherently 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 {q}q∈Q 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 a minimal set of questions by using the Information Pursuit (IP) algorithm, which selects questions sequentially, depending on previous questions and answers, in order of information 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 a tractable graphical model for p(X,Y ) and learn the required distributions using variational autoencoders and normalizing flows. In section 4 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 complexity 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 FashionMNIST dataset, something that isn’t obvious a priori. While these experiments are restricted to simple tasks and queries, the proposed framework is generally applicable provided that tractable models, inference and learning methods can be developed, which is the subject of ongoing and future work. Finally, we 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 can incorporate in Q the perception of complexity he/she wishes to measure.

heading: 2 QUANTIFYING TASK COMPLEXITY
text: 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 pY |X(y | x) from a finite set of samples from the joint distribution pXY (x, y).1 We propose to quantify the complexity of a task as the minimum expected number of queries needed to solve the task. Queries, q ∈ Q, are functions of the input data, whose answers for a given x are denoted as {q(x)}q∈Q. Naturally, the query set needs to be sufficiently rich so that the task is solvable based on answers to the queries. More formally, we say the set Q is sufficient for task TX;Y if ∀(x, y) ∈ X × Y ,
p(y | x) = p(y | {x′ ∈ X : q(x′) = q(x) ∀q ∈ 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 CQ(X,Y ) for task TX,Y .
Defining the Encoder function. Given a query set Q, an Encoder is a function, E : S∗ → Q where S∗ is the set of all finite-length sequences generated using elements from the set S = {(q, q(x)) | q ∈ Q, x ∈ X}. Additionally, we require that Q contains a special query qSTOP which signals the encoder to stop asking queries and outputs the code for x as the set of query-answer pairs that have been asked. The process can be described as follows, given E and input sample x.
1. q1 = E(∅). The first question is independent of x. 2. qk+1 = E({qi, qi(x)}1:k). All subsequent queries depend on the query-answer pairs ob-
served so far for x. 3. If qL+1 = qSTOP terminate and return CodeEQ(x) := (qi, qi(x))1:L as the code for x.
Note that each qi depends on x, but we drop this in the notation for brevity. Note also that the number of queries L = |CodeEQ(x)| for a particular x generalizes coding length in information theory. The query qSTOP constrains the code CodeEQ(x) to be prefix-free.
Defining task complexity. Given a joint distribution pXY (x, y) and a sufficient query set Q, we define task complexity, CQ(X;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:
CQ(X;Y ) := min E
EX [ |CodeEQ(X)| ] s.t. p(y | x) = p(y | CodeEQ(x)) ∀x ∈ X , y ∈ Y (Sufficiency) (2)
Figure 1: Schematic view of the overall framework for quantifying complexity of a task TX;Y .
The first constraint ensures sufficiency of the code ∀x ∈ X . By this we mean that there exists at least one Encoder E for which the first constraint of “sufficiency” is satisfied, where p(y | CodeEQ(x)) should be interpreted as the conditional probability of y given the event {x′ ∈ X | CodeEQ(x) = CodeEQ(x′)}. The solution to (2) provides the optimal encoder for task TX;Y , and Fig. 1 illustrates the overall framework in detail.
Connection with Shannon entropy H . It can be shown that when Q is taken as the set for all possible binary questions on X and if Y is a function of X (which it usually is for supervised classification problems (Kolchinsky et al., 2018)), then the solution, E∗, to (2) gives a coding length within one bit of the entropy of Y , denoted as H(Y ). More formally, one can show that
H(Y ) ≤ CQ(X;Y ) = EX [ |CodeE ∗ Q (X)| ] < H(Y ) + 1. (3)
1As commonly used, we denote random variables by capital letters and their realizations with small letters.
Note that one example of such an optimal encoder, E∗(x), is given by the Huffman code for Y .
Connection with task complexity & equivalence classes. Notions of complexity of an entity/object, often relate to the level of structural regularity present in the entity (Gell-Mann, 2002). CQ(X;Y ) measures the degree of regularity present in the structure of TX;Y . This structure is implicitly defined by the conditional pY |X(y | x) and the query set Q. Notice that any E partitions X into equivalence classes.
[x] = {x′ ∈ X | CodeEQ(x) = CodeEQ(x′)}. (4)
The prefix-free constraint on the codes generated by E (due to ) ensures that ∀x′ ∈ [x],∀y ∈ Y, pY |X=x′(y) = pY |X=x(y). It is then natural to relate task complexity with the number of equivalence 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(y | x′) for any one element x′ in each equivalence class is sufficient to predict Y . An extreme case of this would be the constant function which arguably has the simplest possible structure of any task TX,Y . The equivalence class in this case is just X since pY |X(y | x) is same for all x ∈ 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 a proof) relates CQ(X;Y ) and the number of equivalence classes, the latter being not easy to compute from finite samples.
Proposition 1. Given a finite query set Q, b-valued query-answers {q(X)}q∈Q and any δ > 0, the number of equivalence classes induced by the minimizer of (2) can be upper bounded by bCQ(X;Y )+|Q| √ 2 log( 1δ )) with probability of misclassifying X at most δ.
Proposition 1 indicates that for the sameQ, tasks with greaterCQ(X;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 CQ(X;Y ) = 1 (Observing intensities at all the pixels is 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, b would be the number of intensity values each pixel can take but CQ(X;Y ) ≥ 1.
Properties of CQ(X;Y ). The following proposition, whose proof can be found in Appendix A.2, establishes some key properties of our proposed measure of complexity.
Proposition 2. For any query setQ that is sufficient for task TX,Y , CQ(X;Y ) satisfies the following properties:
1. CQ(X;Y ) ≥ 0. (non-negativity)
2. CQ(X;Y ) = 0 iff X ⊥⊥ Y . (trivial structure)
3. If ∀x, x′ ∈ X , x 6= x′,∃y ∈ Y , such that pY |X=x(y) 6= pY |X=x′(y), then CQ(X;Y ) ≥ CQ(X; Ỹ ) for all tasks TX,Ỹ provided Q is sufficient for TX,Ỹ . (total structure)
4. CQ(X;Y1, Y2) ≤ CQ(X;Y1) + CQ(X;Y2) for any two tasks with X ∼ pX(x) and Y1 ⊥⊥ Y2 | X . (sub-additivity under union)
The property “trivial structure” captures the fact that if Y is 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=x(y) is different ∀x ∈ 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 a 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;Y1 and target task TX;Y2 have the same marginal for X ∼ pX(x) but different conditionals pY1|X(y1 | x) and pY2|X(y2 | x). CQ(X;Y1, Y2) refers to the complexity of
task TX;Y1,Y2 , defined by pXY1Y2(x, y1, y2), where the corresponding sufficiency constraint in (2) becomes
p(y1, y2|x) = p(y1, y2|CodeEQ(x)) ∀x ∈ X , y1 ∈ Y1, y2 ∈ Y2. (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 Y1 ⊥⊥ Y2 | X is not particularly strict as it simply implies given input X , knowledge of Y1 is not required to predict Y2 and vice-versa.
-approximate task complexity. In practice, we are often interested in solving a task “approximately” rather than “exactly”. To accommodate this, we extend the definition of Sufficiency in (2) to -Approximate Sufficiency by relaxing it to d ( p(y | x), p(y | CodeEQ(x)) ) ≤ ∀x ∈ X . Here, d 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 of our complexity measure, we note that unfortunately for any general query set Q, the problem in (2) is known to be NP-Complete and hence generally intractable (Laurent & Rivest, 1976). As a result, we instead consider a greedy approximation to CQ(X;Y ) via an algorithm called Information Pursuit (IP) introduced by Geman & Jedynak (1996), which we describe in detail next.

heading: 3 APPROXIMATING TASK COMPLEXITY USING INFORMATION PURSUIT
text: From this section onwards we will assume Q is a finite set. Information pursuit (IP) is a greedy algorithm introduced by Geman & Jedynak (1996) which provides an approximate solution to (2). The Encoder in IP, denoted as EIP , is recursively defined as follows,
q1 = E IP (∅) = arg max
q∈Q I(q(X);Y )
qk+1 = E IP ({qi, qi(x)}1:k)) = arg max q∈Q I(q(X);Y |Bx,k)
(6)
where x is an input data-point and I stands for mutual information. In other words, IP chooses the next query qk+1 as the one whose answer maximizes the mutual information with Y given the history of questions and answers about x chosen by IP till time k, i.e., given the eventBx,k := {x′ ∈ X | {qi, qi(x)}1:k = {qi, qi(x′)}1:k}. Ties in choosing qk are broken arbitrarily if the maximum is not unique. The algorithm stops when it satisfies the following condition:
qL+1 = qSTOP if max q∈Q I(q(X);Y |Bx,m) = 0 ∀m ∈ {L,L+ 1, ..., L+ T}, (7)
where T > 0 is a hyper-parameter chosen via cross-validation, with the rationale behind this choice provided in Appendix A.4. We will denote this sub-optimal solution EIP as C̃Q(X;Y ). To compute an approximation to C Q(X;Y ) we modify the stopping criteria in (7) to maxq∈Q I(q(X);Y |Bx,m) ≤ and call this estimate C̃ Q(X;Y ).

heading: 3.1 APPROXIMATION GUARANTEES FOR INFORMATION PURSUIT
text: While in general it 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(q(X) | Y ) = 0 ∀q ∈ Q and Y is a function of X , we have the following proposition (see Appendix A.6 for a proof).
Proposition 3. Given task TX;Y with Y being a discrete random variable. If there exists a function f such that Y = f(X) and Q is the set to all possible binary functions of X such that H(q(X) | Y ) = 0 ∀q ∈ Q then H(Y ) ≤ C̃Q(X;Y ) ≤ H(Y ) + 1.
While the above proposition is often considered to be true, this is the first time a rigorous proof has been presented (to the best of our knowledge). Thus, in this special case, from (3) we have that C̃Q(X;Y ) ≤ CQ(X;Y )+1 and thus the IP algorithm will be a tight approximation to our proposed complexity measure.

heading: 3.2 INFORMATION PURSUIT USING VARIATIONAL AUTOENCODERS + NORMALIZING FLOWS
text: IP requires probabilistic models relating query-answers and data to compute the required mutual information terms in (6). Specifically, computing qk+1 in (6) (for any iteration number k) requires computing the mutual information between q(X) and Y given the history Bx,k till time k. As histories become longer, we quickly run out of samples in our dataset which belong to the event Bx,k. As a 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-based approach to address this challenge for a general task TX;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) = {q(X) : q ∈ 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), Y, Z
pQ(X)ZY (Q(x), η, y) = ∏ q∈Q pq(X)|ZY (q(x) | η, y)pY (y)pZ(η). (8)
Throughout the paper η and q(x) denote the realizations of Z and q(X) respectively. Equation (8) is a reasonable assumption unless the answers q(X) are causally related to each other, (Reichenbach’s common cause principle (Hofer-Szabó 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. q(X) as object presence indicators evaluated at non-overlapping windows: Let Q be a set of non-overlapping windows in the image X with q(X) as the random variable indicating the presence of an object at the qth location. The correlation between the qs is entirely due to latent image generating factors Z, such as lighting, camera position, scene layout, and texture along with the scene description signal Y .
2. q(X) as snippets of speech utterances: A common assumption in speech recognition tasks is that the audio frame features (q(X)) are conditionally independent given latent phonemes Z (which is often modelled as a Hidden Markov Model).
This latent spaceZ is often a lower-dimensional space compared to the original high-dimensionalX . We learn Z from data in an unsupervised manner using variational inference. Note, this assumption of conditional independence will not hold in scenarios where q(X) directly cause each other, for instance, if in example 1, we considered overlapping patches.
Specifically, we parameterize the distributions {pω(q(x) | η, y) ∀q ∈ Q} with a neural network with shared weights ω and call it the Decoder Network. These weights are learnt using stochastic Variational Bayes (Kingma & Welling, 2013) by introducing an approximate posterior distribution p′φ(η | y,Q(x)) parameterized by another neural network with weights φ called the Encoder Network and priors pY (y) and pZ(η).
Implementing EIPQ using the generative model. Using the learnt Decoder network one can estimate the distribution pq(X)Y (q(x), y) via Monte Carlo Integration and compute q1 = EIP (∅). For subsequent queries (k > 1), the computation of qk+1 requires the mutual information conditioned on current history Bx,k, which can be calculated from the distribution
p(q(x), y | Bx,k) = ∫ p(q(x) | η, y)p(η | y,Bx,k)p(y | Bx,k)dη. (9)
To estimate the left-hand side of (9) via Monte Carlo integration, one needs to sample N i.i.d. samples ηi ∼ p(η | y,Bx,k) and compute 1N ∑N i=1 pω(q(x) | η(i), y)p(y | Bx,k), where the term p(y | Bx,k) can be estimated recursively with p(y | Bx,0) := pY (y). Appendix A.7 gives more details on these computations. Note, however, it is not straightforward to sample from this posterior p(η | y,Bx,k) without resorting to 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(η | y,Bx,k) by another neural network trained to learn this posterior.
Estimating p(η | y,Bx,k) with Normalizing Flows. We amortize the cost of modelling p(η | y,Bx,k) for each history encountered during the EIP recursion by assuming the existence of a function Ψ such that p(η | y,Bx,k) = Ψ({(qi, qi(x))}1:k, y, η) ∀x ∈ X for any iteration k.
Ψ̃, as the Conditional Inference Network (Refer Fig. 2). Refer Appendix A.8 for details on the training procedure.
Using the trained Ψ̃ one can sample from the posterior p(η | y,Bx,k), as required for (9) for any observed history Bx,k. The sampling procedure is as follows: (i) Sample η0 ∼ N (0, Id) (assuming η0 ∈ Rd); (ii) Compute η = Ψ̃−1({(qi, qi(x))}1:k, y, η0).

heading: 4 CASE STUDY: COMPLEXITY OF BINARY IMAGE CLASSIFICATION TASKS
text: 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 is two-fold: (i) Patches provide a sufficiently rich query set to compare different learning tasks on binary images and allow us to measure the task-specific input feature complexity of different tasks; (ii) From a practical stand-point, state-of-the-art deep generative models for binary images can be assumed to be “perfect” models allowing us to illustrate the usefulness of the framework with minimal modelling bias.
For all our experiments, we considered Q as index set to all 3× 3 overlapping patches in the image. This requires some modelling changes. Recall, (8) only holds if q(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 Xj (X denoting the binary image, and j the jth pixel), p(xj , η, y) = ∏ xj∈X p(xj | η, y)p(y)p(η). 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 C̃ Q(X;Y ) for MNIST classification by, (i) MNIST-α: randomly flipping pixels in MNIST images with probability α ∈ [0, 1]; (ii) MNIST-Translated: translating the digits by at most 4 pixels. Fig. 3a shows the results. The plot shows the trade-off between accuracy and task complexity for different values of . 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 accuracies obtained by predicting Y according to arg maxy∈Y p(y | Bx,L)2 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.05, 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 an expected “correct” trend (complexity increases as nuissance level increases), the complexity ordering is 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, FashionMNIST, KMNIST, and Caltech Silhouettes. Fig. 3b reports the results. Our findings indicate that MNIST < FashionMNIST < KMNIST < Caltech Silhoettes in terms of task complexity at almost all relative test accuracy levels.
2Recall L is the iteration after which IP terminates
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. 3c, d, e, & f illustrate this with an example. IP predicts the image label is “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. 3f reveals that EIP 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 a more indepth analysis would be required. This property of IP could be utilized to develop more interpretable ML algorithms.

heading: 5 CONCLUSION AND RELATED WORK
text: In this paper, we introduced a novel notion of task complexity intimately tied to a query set Q. In the following paragraphs, we will briefly discuss some relevant prior work with connections to our 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 et al. (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.
The problem of classifying objects by sequentially observing different image locations has been recently re-branded as Hard Attention in vision (Mnih et al., 2014; Elsayed et al., 2019; Li et al., 2016) and several deep learning solutions have been proposed. These methods typically try to learn a policy for iteratively choosing different parts of an image for solving different visual tasks. Optimization 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 interesting to see if IP can be combined with reinforcement learning-based approaches to design better reward functions to facilitate efficient policy search.
The information bottleneck (IB) method proposed by Tishby et 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. 1 & 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 is 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. In a sense, the choice of Q constrains the way information from X can be extracted to predict Y .
Task complexity measures based on Kolmogorov Complexity are not computable (Li, 2006; Achille et al., 2019b; Vereshchagin & Vitá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 (x, y) in the training dataset. This is in stark contrast to our definition which is a property of the joint distribution pXY (x, y) and not any given finite dataset. Computing CQ(X;Y ) is NP-Complete but not uncomputable. The implication of this is that there exist dynamic programming based solutions that exactly computeCQ(X;Y ). The complexity of these algorithms are typically exponential in |Q| and so feasible only when |Q| is small. For large |Q|, we must turn to approximations and Information Pursuit is one such strategy. On the other hand, an algorithm for computing Kolmogorov Complexity 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 is undesirable. Secondly, Kolmogorov complexity fails to distinguish between memorization and learning. A dataset sampled from pXY (x, y) where Y is independent of X will have the maximum Kolmogorov-based complexity measure. However, from a 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 0. Achille et al. (2019b) presents for a more detailed discussion on this. The proposed measure CQ(X;Y ) is not dataset permutation-sensitive since it is a property of the distribution pXY (x, y). Moreover, CQ(X;Y ) = 0 when Y is independent of X (See Proposition 2.2) and so distinguishes learning from memorization.
Our work is related in spirit to the work of Achille et al. (2019b) which introduces an alternate measure of task complexity based on the intuition that the information stored in the weights of a trained network can be used as a measure of task complexity. They show that their measure recovers Kolmogorov’s complexity, Shannon’s information, Fisher’s information as special cases, and is also related to PAC-Bayes generalization bounds.

heading: A APPENDIX
text: In proofs of propositions and lemmas we rewrite the statement for convenience.

heading: A.1 PROOF OF PROPOSITION 1
text: Proposition. Given a finite query set Q, b-valued query-answers {q(X)}q∈Q and any δ > 0, the number of equivalence classes induced by the minimizer of (2) can be upper bounded by bCQ(X;Y )+|Q| √ 2 log( 1δ )) with probability of misclassifying X at most δ.
Proof. Let dQ(X) be a random variable denoting the optimal code-length for X using E∗, the solution to (2). Since, 0 ≤ dQ(X) ≤ |Q|. From the definition, CQ(X;Y ) = EX [dQ(X)]. So, Hoeffding’s Lemma we have
dQ(X)− CQ(X;Y ) ∼ subG( |Q|2
4 ) (10)
Since dQ(X) is sub-gaussian, for any δ > 0
P ( dQ(X) > CQ(X;Y ) + |Q| √ 2 log 1
δ
) ≤ δ (11)
Notice, the prefix-free nature of E∗ naturally gives rise to a tree with d(X) being the depth of the corresponding tree TQ for input X . The number of equivalence classes is exactly the number of leaves of TQ. Given, each query-answer q(X) is b-valued. So we can upper bound the number of leaves by replacing TQ with a balanced b-ary tree with bCQ(X;Y )+|Q| √
2 log 1δ leaves called T̃Q. T̃Q can be constructed from TQ as follows:
1. For any leaf node with depth d(X) < CQ(X;Y ) + |Q| √
2 log 1δ vacuously increase the depth till equality is achieved by repeatedly asking the last query. For any internal node in TQ that is not balanced, add vacuous subtrees by randomly selecting queries from Q (no x ∈ X would be sent to these new subtrees) to make the tree balanced with each internal node having b children nodes. As a result, ∀x ∈ X with d(x) < CQ(X;Y )+ |Q| √ 2 log 1δ , T̃Q(X) would compute the same posterior as TQ(X), that is p(y | CodeE ∗
Q (x)), and thus not make an error.
2. For any leaf node with depth d(X) > CQ(X;Y ) + |Q| √ 2 log 1δ , cut the path at depth
u(X) = CQ(X;Y ) + |Q| √
2 log 1δ by merging the subtree rooted at depth u(X) and creating a leaf node. An input x ∈ X sent to this new leaf node would be misclassified. The probability of such an event is given by (11).

heading: A.2 PROOF OF PROPOSITION 2
text: Proposition. For any query set Q that is sufficient for task TX,Y , CQ(X;Y ) satisfies the following properties.
1. CQ(X;Y ) ≥ 0. (non-negativity)
2. CQ(X;Y ) = 0 iff X ⊥⊥ Y . (trivial structure)
3. If ∀x, x′ ∈ X , x 6= x′,∃y ∈ Y , such that pY |X=x(y) 6= pY |X=x′(y), then CQ(X;Y ) ≥ CQ(X; Ỹ ) for all tasks TX,Ỹ provided Q is sufficient for TX,Ỹ . (total structure)
4. CQ(X;Y1, Y2) ≤ CQ(X;Y1) + CQ(X;Y2) for any two tasks with X ∼ pX(x) and Y1 ⊥⊥ Y2 | X . (sub-additivity under union)

heading: Proof.
text: 1. Follows trivially from the definition.
2. For proving the “if” part, observe that ifX ⊥⊥ Y then pY |X=x(y) = pY (y) ∀y ∈ Y, x ∈ X . Choose E1 to be an encoder such that q1 = qSTOP . Then
EX ( |CodeE1Q (X)| ) = 0
E1 is trivially prefix-free (all x ∈ X gets mapped to the same code ∅). Recall that p(y|CodeE1Q (x)) should be interpreted as the conditional probability of y given the event {x′ ∈ X | CodeE1Q (x) = Code E1 Q (x
′)}. Since ∀x ∈ X , CodeE1Q (x) = ∅, p(y | CodeE1Q (x)) = p(y | X ) = p(y). Hence, E1 also provides a sufficient code and thus is a feasible solution to the optimization problem in (2). From property 1 we know that E1 achieves the optimal CQ(X;Y ). The proof for the “only if” part is very similar. Consider E∗ as the optimal solution to (2) and CQ(X;Y ) = 0. This implies CodeE ∗
Q (x) = ∅ ∀x ∈ X . Since E∗ is sufficient, p(y | x) = p(y | CodeE∗Q (x)) = p(y) ∀x ∈ X , y ∈ Y . This implies X ⊥⊥ Y .
3. Let ET denote the minimizer of (2) for the task TX;Y where Y given X is distributed as stated. From sufficiency we know that no two different inputs x, x′ ∈ X could have the same code, that is, CodeETQ (x) 6= Code ET Q (x
′) ∀x, x′ ∈ X , x 6= x′. Consider any other task TX,Ỹ defined by p(X, Ỹ ) with the same marginals X ∼ pX(x) but possibly different conditional Ỹ ∼ pỸ |X(ỹ | x) such that Q is also sufficient for TX,Ỹ . ET is a feasible solution for (2) with respect to task TX,Ỹ since p(ỹ | Code ET Q (x)) = p(ỹ | {x}). Thus,
CQ(X; Ỹ ) ≤ EX ( |CodeETQ (X)| ) for any other task TX;Ỹ for which Q is sufficient.
4. Let E1 and E2 be the optimal encoders for tasks TX;Y1 and TX;Y2 respectively. Construct an encoder E12 for that task TX;Y1,Y2 by concatenating the two codes. It is not hard to see that
EX ( |CodeE12Q (X)| ) ≤ EX ( |CodeE1Q (X)| ) + EX ( |CodeE2Q (X)| ) .
The inequality is due to the fact that (query,answer) tuples can overlap in the codes constructed by two encoders E1 and E2 for the same input x. E12 is prefix-free by construction. Now, for any observation y1 of output Y1
p(y1 | CodeE12Q (x))
= p(y1 | CodeE1Q (x) ∪ Code E2 Q (x))
= p(y1 | {x′ ∈ X : CodeE1Q (x ′) ∪ CodeE2Q (x ′) = CodeE1Q (x) ∪ Code E2 Q (x)})
= p(y1 | {x′ ∈ X : CodeE1Q (x ′) = CodeE1Q (x)} ∩ {x ′ ∈ X : CodeE2Q (x ′) = CodeE2Q (x)})
= p(y1 | x)
The last equality appeals to the fact that E1 satisfies the “sufficiency” constraint in (2) for task TX;Y1 . Similarly, p(y2 | Code E12 Q (x)) = p(y2 | x) for any observation y2 of output Y2. Given, Y1 ⊥⊥ Y2 | X . This implies ∀x ∈ X
p(y1, y2 | x) = p(y1 | x)p(y2 | x) = p(y1 | CodeE12Q (x))p(y2 | Code E12 Q (x))
= p(y1, y2 | CodeE12Q (x))
This proves E12 is sufficient for the task T (X;Y1, Y2). Since E12 is a feasible solution for the optimization problem with respect to T (X;Y1, Y2) we get the required inequality.

heading: A.3 -APPROXIMATE COMPLEXITY OF TASK
text: In practice, we are often interested in solving a task “approximately” rather than “exactly”. This requires introducing a notion of approximate sufficiency instead of exact sufficiency, and we extend the definition in (2) to incorporate this.
C Q(X;Y ) := min E
EX [ |CodeEQ(X)| ] (12)
s.t. d ( p(y | x), p(y | CodeEQ(x)) ) ≤ ∀x ∈ 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 satisfies the triangle-inequality then C Q(X;Y ) satisfies the properties in Proposition 2 with two key differences:
1. In Property 3, C Q(X;Y ) is the complexity of the task for which d ( pY |X=x(y), pY |X=x′(y) ) > 2 ∀x, x′ ∈ X , x 6= x′.
2. In Property 4, the relation is C Q(X;Y1, Y2) ≤ C 2 Q(X;Y1) + C 2 Q(X;Y2).
A.4 TERMINATION CRITERIA FOR EIPQ
Ideally we would like to terminate (EIP outputs qSTOP ) after L steps if
p(y | x) = p(y | x′) ∀x, x′ ∈ Bx,L, y ∈ Y (14) However, detecting this is difficult in practice. We have the following lemma. Lemma A.4.1. Assume Y ⊥⊥ q(X) | X ∀q ∈ Q. If event Bx,L satisfies the condition specified by (14) then for all subsequent queries qm, m ≥ L, maxq∈Q I(q(X);Y |Bx,m) = 0. Since ties are broken arbitrarily if the maximum not unique, EIP chooses any q ∈ Q as a subsequent query qm.
Refer to Appendix A.5 for a proof. The assumption Y ⊥⊥ q(Xx) | X ∀q ∈ Q is generally true since we have the following Markov Chain Y → X → q(X) ∀q ∈ Q. Using Lemma A.4.1, the correct stopping criteria should be
L = inf{k ∈ {1, 2, ..., |Q|} : max q∈Q I(q(X);Y |Bx,m) = 0 ∀m ≥ k,m ≤ |Q|} (15)
Evaluating (15) would be computationally costly since it would involve processing all the queries for every input x. We employ a more practically amenable criteria
qL+1 = qSTOP if max q∈Q I(q(X);Y |Bx,m) = 0 ∀m ∈ {L,L+ 1, ..., L+ T} (16)
T > 0 is a hyper-parameter chosen via cross-validation. Note, it 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 ∈ R2 and Y ∈ {0, 1}. Let Q be the set to two axis-aligned half-spaces. Both half-spaces have zero mutual information with Y . However, upon choosing any one as q1, the other half-space is suddenly informative about Y .

heading: A.5 PROOF OF LEMMA A.4.1
text: Lemma. Assume Y ⊥⊥ q(X) | X ∀q ∈ Q. If event Bx,L satisfies the condition specified by (14) then for all subsequent queries qm, m ≥ L, maxq∈Q I(q(X);Y |Bx,m) = 0. Since ties are broken arbitrarily, EIP chooses any q ∈ Q as a subsequent query qm.
Proof. Recall each query q partitions the set X and Bx,L is the event {x′ ∈ X | {qi, qi(x)}1:L = {qi, qi(x′)}1:L}. It is easy to see that if Bx,L satisfies the condition specified by (14) then
P (y | Bx,m) = P (y | x′) ∀x′ ∈ Bx,m ∀m ≥ L, ∀q ∈ Q (17)
This is because subsequent query-answers partition a set in which all the data points have the same posterior distributions3. Now, ∀q ∈ Q, ∀a ∈ Range(q), y ∈ Y
p(q(X) = a, y|Bx,m) = p(q(X) = a | Bx,m)p(y | q(X) = a,Bx,m) (18) eq: chain rule of prob is just an application of the chain rule of probability. The randomness in Aq(X) is entirely due to the randomness in X . For any a ∈ Range(Aq), y ∈ Y
p(y | q(X) = a,Bx,m) = ∑
x′∈Bx,m∩{x∈X|q(X)=a}
p(y, x′ | a,Bx,m)
= ∑
x′∈Bx,m∩{x∈X|q(X)=a}
p(y | x′, a, Bx,m)p(x′ | a,Bx,m)
= ∑
x′∈Bx,m∩{x∈X|q(X)=a}
p(y | x′)p(x′ | a,Bx,m)
= p(y | Bx,m) ∑
x′∈Bx,m∩{x∈X|q(X)=a}
p(x′ | a,Bx,m)
= p(y | Bx,m)
(19)
The first equality is an application of the law of total probability, third due to conditional independence of the history and the hypothesis given X = x′ (assumption) and the fourth by invoking ((17)).
Substituting (19) in (18) we obtain Y ⊥⊥ q(X) | Bx,m ∀m ≥ L, q ∈ Q. This implies that for all subsequent queries qm, m > L, maxq∈Q I(q(X);Y |Bx,m) = 0. Hence, Proved.

heading: A.6 PROOF OF PROPOSITION 3
text: Proposition. Given task TX;Y with Y being a discrete random variable. If there exists a function f such that Y = f(X) and Q is the index set to all possible binary functions of X such that H(q(X) | Y ) = 0 ∀q ∈ Q then H(Y ) ≤ C̃Q(X;Y ) ≤ H(Y ) + 1.
We make two remarks before turning to the proof. Remark 1:
The task is to determine the true state of a latent variable Y ∈ Y based on querying an observed data point x0. We assume Y = f(X) with f unknown. Were Y observable, the natural queries would be indexed by subsets D ⊂ Y , one query for every D ⊂ Y , namely q(Y ) = 1 if Y ∈ D and 0 otherwise. (This is essentially the classic “twenty questions game”, but with an “oracle” and “complete tests”.) There are 2|Y| such queries and obviously they collectively determine Y . Now since Y = f(X), these queries are, at least implicitly, functions of the data X , but we 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′ = f−1(D)) can be checked for inclusion of X , i.e., Y ∈ D if and only if X ∈ D′. Or, what is the same, a binary query q(X) (and still denoted q for simplicity) with q(X) = q(Y ). In 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.
Remark 2: The sequence of queries q1, q2, ... generated by the IP algorithm for a particular data point can be seen as one branch, root to leaf, of a decision tree constructed by the standard machine learning strategy based on successive reduction of uncertainty as measured by entropy:
3We refer to the distribution p(y | x) for any x ∈ X as the posterior distribution of x.
q1 = arg maxq∈Q I(q(X);Y ), qk+1 = arg maxq∈Q I(Aq(X);Y |Bx0,k) where the Bx0,k is the event that for the first k questions the answers agree with those for x0. We stop as soon as Y is determined. Whereas a decision tree accommodates all x simultaneously, the questions along the branch depends on having a particular, fixed data point. But the learning problem in the branch version (“active testing”) is exponentially simpler.
Proof of Proposition 3.1: The lower bound H(Y ) ≤ C̃Q(X;Y ) comes from Shannon’s source coding theorem for symbol codes. Now for the upper bound, since I(q(X);Y |Bx0,k) = H(q(X)|Bx0,k) − H(q(X)|Y,Bx0,k) and since Y determines q(Y ) and hence also q(X), the second entropy term is zero (since given H(Aq(X) | Y ) = 0). So our problem is maximize the conditional entropy of the binary random variable q(X) given Bx0,k. So the IP algorithm is clearly just “divide and conquer”:
q1 = arg max q∈Q H(q(X)),
qk+1 = arg max q∈Q
H(q(X)|Bx0,k).
Equivalently, since entropy of a binary random variable ρ is maximized when P (ρ) = 12 ,
qk+1 = arg min q∈Q |P (q(X) = 1|Bx0,k)−
1 2 |.
Let Yk be the set of “active hypotheses” after k queries (denoted as Ak), namely those y with positive posterior probability: P (Y = y|Bx0,k) > 0. Indeed,
P (Y = y|Bx0,k) = P (Bx0,k|Y = y)p(y)∑ y P (Bx0,k|Y = y)p(y)
= 1Ykp(k)∑ y∈Ak p(y)
since
P (Bx0,k|Y = y) = {
1, if y ∈ Ak 0, y /∈ Ak
In particular, the classes in the active set have the same relative weights as at the outset. In summary:
p(y|Bx0,k) = { p(y)/ ∑ Ak p(l), y ∈ Ak
0, otherwise
The key observation to prove the theorem is that if a hypothesis y generates the same answers to the first m or more questions as y0, and hence is active at step m, then its prior likelihood p(y) is at most 2−(m−1), m = 1, 2, . . .. This is intuitively clear: if y has the same answer as y0 on the first question, and p(y0) > 12 , then only one question is needed and the active set is empty at step two; if q1(y) = q1(y0) and q2(y) = q2(y0) and p(y0) > 14 , then only two question are needed and the active set is empty at step three, etc.
Finally, since C, the code length, takes values in the non-negative integers {0, 1, . . . , }:
C̃Q(X;Y ) := E[C]
= ∞∑ m=1 P (C ≥ m)
≤ ∞∑ m=1 P (p(Y ) < 2−(m−1))
= ∞∑ m=1 ∑ y:p(y)<2−(m−1) p(y)
= ∑ y∈Y ∞∑ m=1 1{p(y)<2−(m−1)}p(k)
= ∑ y∈Y p(k)(1− log p(k))
= H(Y ) + 1

heading: A.7 COMPUTING MUTUAL INFORMATION FOR (6)
text: A.7.1 IMPLEMENTING EIP : COMPUTING THE FIRST QUESTION q1
Once the Decoder network has been learnt using variational inference, the first question q1 can be calculated as per (6). Since the mutual information is completely determined by p(q(x), y), which is obtained by numerically marginalizing the nuisances Z from (8) using Monte Carlo integration. ∀q ∈ Q
pq(X)Y (q(x), y) = ∫ η pQ(X)ZY (Q(x), η, y)dη
= ∫ η pq(X)|ZY (q(x) | η, y)pY (y)pZ(η)dη
≈ 1 N N∑ i=1 pω(q(x) | y, η(i))pY (y)
(20)
In the last approximation, pω(q(x) | y, η(i)) is the distribution obtained using the trained Decoder network. N is the number of i.i.d. samples drawn and ηi ∼ pZ(η).
A.7.2 DERIVATION FOR (9)
. p(q(x), y | Bx,k) = ∫ p(q(x), η, y | Bx,k)dη
= ∫ p(q(x) | η, y,Bx,k)p(η | y,Bx,k)p(y | Bx,k)dη.
= ∫ p(q(x) | η, y)p(η | y,Bx,k)p(y | Bx,k)dη.
(21)
The first equality is an application of the law of total probability. The last equality appeals to the assumption that {q(X), q ∈ Q} are conditionally independent given Y,Z ((8)).
A.7.3 RECURSIVE ESTIMATION OF p(y | Bx,k)
Finally, p(y|Bk(x0)) (required for (9)) is computed recursively via the Bayes’ theorem.
p(y | Bx,k) ∝ p(y,Bx,k) = p(qk(x), y, Bx,k−1)
∝ p(qk(x) | y,Bx,k−1)p(y | Bx,k−1) (22)
Bx,0 = ∅ (since no evidence via queries has been gathered from x yet) and so p(y | Bx,0) = pY (y). p(y | Bx,k) is obtained by normalizing the last equation in (22) such that ∑ y p(y|Bx,k) = 1. p(qk(x) | y,Bx,k−1) can be estimated using (9).

heading: A.8 TRAINING THE CONDITIONAL INFERENCE NETWORK
text: A normalizing flow is a sequence of invertible transformations that takes a random variable from a 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 a richer family of distributions than the Gaussian/Uniform family. Specifically, we construct a sequence of invertible mappings of the form ηl = Ψ̃l({(qi, qi(x))}1:k, y, ηl+1; γl), each parameterized by a neural network with weights γl, such that η0 is constrained to be normally distributed. The composite function η0 = Ψ̃({(qi, qi(x))}1:k, y, η; γ) is a composition of N neural networks with parameters γ = {γl}l∈{1,2,...,N}.
We call this network, Ψ̃, as the Conditional Inference Network. (Refer Fig. 2 for a pictorial depiction). By the change-of-variables formula for probability densities, p(η | y,Bx,k) can be written as.
pη(η | y,Bx,k) = pη0(Ψ̃({(qi, qi(x))}1:k, y, η; γ)) |∇ηΨ̃({(qi, qi(x))}1:k, y, η; γ)|
(23)
To ensure Ψ̃(η, y, {(qi, qi(x))}1:k; γ) is invertible and the determinant in (23) is efficiently computable, the family of functions used is often constrained to those that admit an upper/lower triangular Jacobin. The normalizing flow model employed here is the realNVP model introduced in Dinh et al. (2016). For training we construct a dataset D∗ from given dataset D (of N i.i.d samples {xi, yi} ∼ pXY (x, 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 in Q = {q : q ∈ Q} and obtain the sample (Q(x), y). Sample k ∼ pK(k), then sample k random positions in Q(x) as mk ∼ pM (mk). pK(k) and pM (mk) are user-defined distributions. In our applications PK(k) is taken to be Poisson(λ = 10) and pM (mk) = U{1, 2, ..., |Q|}
2. Sample η ∼ qφ(η|y,Q(x)) using the trained Encoder network.
3. Mask Q(x) according to positions in mk to obtain k-length sequence {(q, q(x))q∈Q̃⊆Q}. In this way, we obtain samples from the desired joint p(K,BK(X), Y, η). BK(X) is a K-length random sequence {(q, q(X)) : q ∈ Q̃} for some Q̃ ⊆ Q.
The weights γ are then learnt using stochastic approximation by optimizing the following objective using D∗.
max γ EK,BK(X),Y,η[ log pη(η|Y,BK(X))] =
max γ EK,BK(X),Y,η[ log pη0(Ψ̃(BK(X), Y, η; γ))
log |∇ηΨ̃(BK(X), Y, η; γ)|]
(24)
The second equality is obtained by substituting (23) in (24). p(η0) = N (0, Id). To understand the objective in 24, assume general random variables ξ and ψ. Let our proposal distribution be p̃(ψ|ξ) and the true distribution be p(ψ|ξ). Consider a loss function
KL(p(ψ|ξ)||p̃(ψ|ξ)) = ∫ p(ψ|ξ)log p(ψ|ξ)dψ
− ∫ p(ψ|ξ)log p̃(ψ|ξ)dψ
(25)
Since (25) should hold ∀ξ, we take an expectation over ξ. Eξ[KL(p(ψ|ξ)||p̃(ψ|ξ))] = ∫ p(ξ)p(ψ|ξ)log p(ψ|ξ)dψdξ
− ∫ p(ξ)p(ψ|ξ)log p̃(ψ|ξ)dψdξ
= ∫ p(ξ, ψ)log p(ψ|ξ)dψdξ
− ∫ p(ξ, ψ)log p̃(ψ|ξ)dψdξ
(26)
min p̃(ψ|ξ)
Eξ[KL(p(ψ|ξ)||p̃(ψ|ξ))]
= max p̃(ψ|ξ)
∫ p(ξ, ψ)log p̃(ψ|ξ)dψdξ
= max p̃(ψ|ξ)
Eψ,ξ[log p̃(ψ|ξ)]
(27)
The first term in (26) disappears since it does not depend on p̃(ψ|ξ). Compare (27) and (24). Substitute ψ := η and ξ := (K,BK(X), Y ). The proposal p̃(.) is parameterized by the Conditional Inference Network as pη(η|y,Bx,k). The issue is that we don’t have access to the true distribution p(ψ|ξ) to generate samples for a training set and learn an optimal p̃(ψ|ξ) for each Ξ = ξ. However, we have access to the joint p(ξ, ψ) := p(k,Bk(x), y, η) from which we could generate data D∗ for optimizing (27) using stochastic approximation.

heading: A.9 NETWORK ARCHITECTURES AND TRAINING PROCEDURE

heading: A.9.1 ENCODER AND DECODER NETWORKS
text: For the Information Pursuit Generative Model in subsection 3.2, we implemented a β-VAE as introduced in Higgins et al. (2017). The encoder-decoder architecture used is depicted in Fig. 4.
Notation for Fig. 4:
• L(x, y) - Linear layer with x input units and y output units, followed by a BatchNorm layer and leakyRELU activation. • C x - Convolution layer with x 3×3 filters followed by a BatchNorm layer and leakyRELU
activation. • C x M - Same as C x, followed by a Maxpool layer. • DC x y z - Transposed Convolution layer with x y × y filters and stride z, followed by a
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. 4a). BatchNorm was not applied and the leakyRELU activation was replaced by Sigmoid in the output layer of the decoder network (Fig. 4).
Training. The β-VAE was trained by optimizing the Evidence Lower BOund (ELBO) objective,
max ω,φ n∑ i=1 [Eη∼p′φ(η|y(i),x(i))[log pω(x (i)|η, y(i))]
− βKL(p′φ(η|y(i), x(i))‖p(η))]. (28)
using ADAM with learning rate 0.001 and momentum parameters β1 = 0.9 & β2 = 0.999. β was taken as 4.0 for all experiments. The prior over latents pZ(η) is taken as N (0, I100) and pY (y) 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.

heading: A.9.2 CONDITIONAL INFERENCE NETWORKS
text: Unless stated otherwise, the notation for the figures in this section is the same as introduced in subsection A.9.1.
Network Architecture. For the Conditional Inference Network, introduced in Section 3.2, implemented a variant of the flow network introduced in Dinh et al. (2016). Fig. 5 depicts the overall architecture.
In Fig. 5 for our use-case with binary images and patch queries, {qi, qi(x)}1:k, represents a masked image (sequence of patches observed), y denotes the class label, η are the nuisances distributed according to the target complex distribution and η0 are the transformed random variables distributed according to a uni-modal standard Gaussian distribution. Each triplet of (Actnorm Layer, Permute Layer, Affine Layer) forms a layer of the flow network. The overall network is 25 layers deep. Each layer represents the function ηl = Ψ̃l({qi, qi(x)}1:k, y, ηl+1); γl), with weights γl. The weights of the flow network is denoted as γ = {γl}l∈{0,1,...,24}. In what follows, we describe in detail each of the layers in a triplet.
Actnorm Layer: It has been proposed in literature to add a Batchnorm style layer with learnable scale s and shift b parameters to stabilize network optimization. Fig. 6 depicts the Actnorm layer network architecture used.
Permute Layer: This layer implements a permutation operation.
ηpermutel−1 = Pη actnorm l−1 (29)
Here P is a permutation matrix which swaps the first 50 dimensions of ηactnorml−1 with the next 50 dimensions. Recall, ηl ∈ R100 ∀l ∈ {0, 1, . . . , 25}. Affine Layer: This layer implements the following operations.
h1l−1, h 2 l−1 = split(η permute l−1 ) (30)
s, t = NNaffine(h 1 l−1, Bk(x), y) (31)
α1l−1 = h 1 l−1
α2l−1 = h 2 l−1 ◦ s+ (1− s) ◦ t
(32)
◦ denotes element-wise multiplication.
ηl−1 = concat(α1l−1, α 2 l−1) (33)
The split operation in (30) divides ηpermutel−1 into two halves, such that, h 1 l−1 = η permute l−1 [0 : 50] and h2l−1 = η permute l−1 [50 : 100].
Fig. 7 depicts the network architecture used for the NNaffine in (31).
Notice, each of the layers are invertible functions and hence their compositions (the 25 layer deep flow network) is also invertible, which is a key requirement for (23).
Training. The dataset for optimizing (24) was generated as 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 β1 = 0.9 & β2 = 0.999. L2 regularization was added to stabilize the training and prevent gradients from exploding (a common problem in training normalizing flow networks). A scheduling was done for the regularization constant. Namely, we optimized (24) with L2 regularization parameter {1012, 108, 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.

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

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.