Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes
Authors: Alessio Mazzetto
Cristina Menghini
Andrew Yuan
Eli Upfal
Stephen Bach
Venue: NeurIPS 2022 Accept (2022)
Keywords: ZSL
theory
lower bound
Zero-Shot Learning
machine learning
learning with less data

Abstract: We develop a rigorous mathematical analysis of zero-shot learning with attributes. In this setting, the goal is to label novel classes with no training data, only detectors for attributes and a description of how those attributes are correlated with the target classes, called the class-attribute matrix. We develop the first non-trivial lower bound on the worst-case error of the best map from attributes to classes for this setting, even with perfect attribute detectors. The lower bound characterizes the theoretical intrinsic difficulty of the zero-shot problem based on the available information---the class-attribute matrix---and the bound is practically computable from it. Our lower bound is tight, as we show that we can always find a randomized map from attributes to classes whose expected error is upper bounded by the value of the lower bound. We show that our analysis can be predictive of how standard zero-shot methods behave in practice, including which classes will likely be confused with others.

Tight Lower Bounds on Worst-Case Guarantees for Zero-Shot Learning with Attributes
Alessio Mazzetto" Brown University
Cristina Menghini
Brown University
Andrew Yuan Brown University
Eli Upfal Brown University
Stephen H. Bach
Brown University
Abstract
We develop rigorous mathematical analysis of zero-shot learning with attributes. In this setting, the goal label novel classes with no training data, only detectors for attributes and description of how those attributes target classes, called the class-attribute matrix. We develop the first non-trivial lower bound on the worst-case errоr of the best map from attributes to classes for this setting, even with perfect attribute detectors. The lower bound characterizes the theoretical intrinsic difficulty of the zero-shot problem based on the available information the class-attribute matrix- and the bound practically computable from it. Our lower bound is tight, map from attributes to classes whose expected error is upper bounded by the value of the lower bound. We show that our analysis can be predictive of how standard zero-shot methods behave in practice, including which classes will likely be confused with others.
correlated with the
show that we can always find randomized
Introduction
Labeled training data is often scarce or unavailable, and it can be very costly obtain. For this reason, there is growing interest in developing methods that can exploit source of information other than labeled data, such zero-shot learning (ZSL). In ZSL, we want to recognize items of unseen classes, for which labeled data is not available. A ZSL model is trained on a disjoint set of similar classes, called seen classes, for which labeled data is available instead. The model trained to map examples to auxiliary information describing the seen classes. Then, at test time, predictions can be made using only descriptions of the unseen classes. While ZSI. is increasingly common in practice, from theoretical perspective ZSL is a hard problem that defies analysis, because in the worst case there can be an arbitrary shift between the distributions of the seen and unseen classes. In this work, we take step towards better theoretical understanding of ZSL. We investigate the question: Given only auxiliary information the form of altributes describing unseen classes, what is the smallest worst-case error than any method can guarantee? ? We provide the first non-trivial answer to this question by developing a framework based on adversarial optimization. We also show that this framework has practical application method for identifying when the predictions of ZSL methods on certain unseen classes are more likely to be incorrect.
ZSL models have obtained impressive accuracy in practice, both for vision Xian et al. 201 8a and language domains (Sanh al. 2022 Wei al. 2022 but they come with no theoretical
Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

characterization of their accuracy. To address this gap, we analyze the attribute- based ZSL setting that includes a large portion of the classic methods proposed in the literature KKomera-Paredes &
Torr 2015 Lampert et al. 2014, Akata et al., 2013 2016), as well as more recent end-to-end deep learning approaches (Kodirov al. 2017: Xian et al, 2018a; Huynh & Elhamitar 2020). While this setting does not include all varieties of ZSL (discussed further in Section 2 we view this work as critical first step towards building up a broader theory of ZSL. In attribute- baseb ZSL, an attribute is property of item to be classified. Each item can either exhibit a given attribute or not. For example, an image of a lion would often exhibit the attribute tail, while the image of a sheep would not. Attribute- baste- ZSL models are trained using attribute representations of the items of the seen classes, and a each attribute. At test time, predictions are made for the unseen classes given the items' attribute representation and a new class-attribute matrix.
matrix that describes pairwise relations between the seen classes and
Romera-Paredes & Torr (2055) is one of the few works to address theoretical questions related to ZSL. Studying baribuute-aseed ZSL., they show a pair of basic bounds that characterize sufficient conditions for either learning or impossibility: (1) if there is no shift from the seen to the unseen classes, then learning is trivial, and (2) if the vectors of attributes of the seen classes are mutually orthogonal with those of the unseen classes, then the error can be arbitrarily large in the worst case. In this paper, we provide the first non-trivin lower bound for ZSL with attributes, addressing the open problem posed by Romera- Comera-Paredess & Torr (2115).
We analyze ZSL with attributes by first observing that it a two stage process consisting of a training phase and an inference phase. In the training phase, we learn map from the items to the attribute space using the seen classes, while in the inference phase we use the class-attribute matrix to infer the correct class given the item-attribute representation. Based on this two-stage decomposition, we can identify two kinds of errors. The first kind, related to the training phase, is due to domain shift. The map from items to the attribute space that is trained on the seen classes might not generalize accurately to the unseen classes. This contribution to the error can be arbitrarily large without introducing strong assumptions, as no labeled data is available for the unseen classes. Thus it is impossible to characterize the domain shift between seen and unseen classes. The second kind, related to the inference phase, is due to the fact that the class-attriburt matrix might not fully differentiate among the unseen classes. In particular, there can be an item of the unseen classes with a set of attributes that according to the class-attribute matrix relation conforms with the description of two different classes. The first kind of error, domain shift, has been extensively studied both in the theory and the experimental literature (Mansour et al., 2009 Ben--David et al. 20T0; Sennr et al. 2016 Pinheuro 2018: Luo et al. 2019). In this work, for the first time, we theoretically characterize the contribution of the second kind of error. It is important understand and characterize this error for specific ZSL tasks because it corresponds to an inherent information gap in the problem setting that cannot be circumvented with a smarter algorithm.
We provide tight lower and upper bounds on the worst-case error of the best map from attribute representations to classes based the class-attribute matrix. Our analysis gives a lower bound in the sense that it bounds from below the minimum error that any method can guarantee given only the information of the class-atrribute matrix. The dasss-attribut matrix specifies the fraction of items in each class that exhibit each attribute. There is a range of class-attribute distributions that satisfy the constrains defined by a given matrix. We give lower bound on the error of the best possible method for the worst case distribution in that range. This distribution represents a worst case correlation between attributes that satisfies the class-attribute matrix while maximizing the difficulty to distinguish between atrribute-representatio of items belonging to distinct classes. Our analysis also gives an upper bound in the sense that we show a randomized classifier that achieves at most the error of the lower bound, assuming perfect fiem-to--ttribur mapping. This also shows that the lower bound is tight. Interestingly, the value of the lower bound can also be interpreted as the quality of the information provided by the class-attribuie matrix. To the best of our knowledge, this is the first work to quantify such information.
Contributions, Our main contributions are the following:
1. We show the first non-trivial lower bound for attribute-bssed ZSL (Section
2. We formulate the lower bound given a class-attribute matrix as linear program (Section
3. We show a closed form expression for the lower bound for binary classification (Section 4.2

---

4. We show that the lower bound is tight: we exhibit a randomized classifier whose expected error is upper bounded by the value of the lower bound (Section 4.3
5. We run extensive experiments comparing the theoretical results with the error of popular attribute-based ZSL. methods, on benchmark datasets. We show that information given by the bound can be predictive of how standard methods behave, including which classes will likely be confused with others (Section 5
2 Background and Related Work
Much early work ZSL focused on using logical descriptions of the classes as auxiliary information, including attributes (Chang et al. 2008; Lampert et al. 2009). Since then, an increasing number of ZSL methods have been proposed, which differ in methodology and the auxiliary information
they use. Examples of auxiliary information are symbolic descriptions of classes (Chang et al.
2008 Lampert al. 2009), pre-trained embedding of the classes (Frome et al. 2013), natural
language descriptions dencuiitossriittoosss
Obeidat et al. 20199; Brown et al. 2020). and knowledge graphs (Wang et al.
2018 Kampitmeyer et al. 2019 Nayak & Bach 2020). Recent ZSL methods can be grouped into
Two main categories: embedding- based and generation-based (Pourpanah et al. 2020). Seminal embedding-based works used two-layer neural networks to link the image feature space to the semantic one &oocher et al., 2013). Later, they evolved into deep neural networks that either map
semantic features into the visual space (Ba et al.) 2013 Zhang et al., 2017: Changpinyo al. 2017 or project both the image and semantic features into the same space (Zhag & Saligrama 2015 Radford et al., 202T). Generative-baser approaches employ various kind of Generative Adversarial Networks (GANs) (Mirza & Osindero, (014) to synthesize the features of the unseen classes, and use
them to train a ZSL classifier a supervised fashion (Felix et al. 2018 Li al. 2019 Xian et al.
2018b 2019,
Narayan et al. 2020).
ZSL with attributes generally consists of learning linear map from the item the attribute space, in the first stage. Then, we use the class-attribute matrix to infer the correct class given the item-attribute representation (Xian et al., 20T8a). ZSL with attributes can be seen special case of embedding- based ZSL, in which the class embeddings are the rows of the class-attribute matrix. Analyzing more general embedding- based or generation- based ZSL methods challenging because they rely on deep neural networks for which relatively little theory is available.
Inspired by previous work to describe classes using error-correcting output codes (Dieteerich & Bakiri 1994). Palatucci et al. (2009) were the first to propose ZSL algorithm for which they can provide a theoretical analysis. The algorithm learns linear classifiers individually for each binary attribute, and the attributes are mapped to the closest class-attribute representation. While they are able to provide PAC bound, their analysis relies on several strong assumptions that limit the problem setting. First, they assume that they can learn each attribute independently, but attribute dependency is a widely recognized problem for attribute detection (Jakulin & Bratko 2003). Second, they assume that each class has a unique attribute representation, i.c. each attribute must be either present or not in all the items of a given class. Finally, they also assume that they are able to sample classes from given distribution, and they are able to generalize to the non-sampled classes. That is, they do not separate beforehand between seen and unseen classes, which the common scenario observed in ZSL settings. Conversely, our lower bound does not assume a unique binary representation for each class, as we are given a class-atribute matrix that provides the probabilities to observe an attribute given an item of a class. Also, our lower bound takes into account the possible correlation between attributes, and it is computed based on the information provided on the given unseen classes.
In more recent work, Romera-Paredae & Torr (015)) draw a connection between transfer learning (Ben-David al. 2010) and ZSL to provide novel theoretical result. In particular, they show that their model is not able to generalize if the attribute representations of the seen classes are orthogonal to the one of the unseen classes. Intuitively, if those representations are orthogonal, the attribute map learned for the seen classes would fail to provide information for the unseen classes. This an impossibility result, and it is not able to arbitrarily quantify the information given for the unseen classes. Unfortunately, transfer learning or domain adaptation to estimate in a ZSL setting. In fact, a term of those bounds require access to labeled data for the unseen classes, which is unavailable in ZSI.. Another term, the discrepancy, depends on the difference between the attribute representations of the classes and the distribution of the items between seen and unseen. While it would be theoretically possible to compute the discrepancy based on the
are challenging
3

---

information available, its computation is very challenging and it has been possible only in very specific cases (Mansour et al. 2009p.
Our novel lower bound is developed using adversarial techniques that describe the worst-case scenario with respect to the information available. It is inspired by recent work on semi-supervised learning. where the goal is to use the information provided by weak supervision sources (Balsubramani & Freund 2013 Arachie & Huang 202T Mazzetto al. 202Ibla). The adversarial approach allows us to handle the possible dependencies between the attributes.
3 Preliminaries
We denote scalar and generic items using lowercase letters, vectors using lowercase bold letters, and matrices using bold uppercase letters. Given two vectors and v', we denote with wo' the N. we denote with [n] the set (I..... Due space
concatenation of the two vectors. For any constraints, all proof' are deferred to the appendix.
Let D be distribution defined over the classification domain X. A multiclass classification task is specified by a labeling function y : X' + 3 === [K] that maps each item x E X to a class j in the label space Y" where > 2. We say that multiclass classification task is balanced if for each holds that Pa>p(y(z) = j] 1/k. Unless otherwise stated, we assume that the classification task is balanced. This assumption is not restrictive, and a different prior is known on the class probabilities. We will show that our lower bound holds even if we do not assume balanced classes. We also assume have access 4h Uh. where vb: X' + {0. 1} for i E [n]. We say that classification item æ E X has attribute i [n]] if (x) 1. For ease of notation, we define vxxx) = (1/ (2), bi, (x))²² The codomain of 2b is f0, 1)", and it is referred to as attribute space. All the information about the target unseen classes available to the algorithm encoded a class-attribute matrix A E [0, 1| The matrix provides information the relations between classes and attributes. In particular for class j [k). and an attribute i E [n]. Ag, is the probability that (x) = given that y(æ) = j. i.e.
[K],
will observe later, it can be changed
attribute functions
P (+)()) 1ly(z) = RnD
An attribute-class classifier g is map from vectors in the attribute space to classes, i.e., g {0, 1}"
[k]. The error of is {gg = Fa-Dle plg <b(x) # y(x)]. Let G be a collection of all the possible deterministic maps {0, 1] - ik] from the attribute space to the classes. We are interested in evaluating mingeg (g) As we focus on the contribution of the information provided by the class- attribute matrix, we assume access to the attribute functions t'1..... 2/x- In practice, the map the attribute space is learned on the available labeled data for the seen classes (Lampert et al. 2014
Pareere-Prreess & Tom 2015), and is likely noisy, and can be cause of additional error.
Let pd be the (unknown) probability mass function (PMF) of the random vector (1/1 (x),.... ..., (h((z), where D. The support of p" is {0, 1] x
[K)). For E 10,
and j E [k], let petpppp (v. P (z=b((((x) = u (y())= = j). The error of g is a function of p":
E(g) = =(g.p") 1
Σ m
p((v)
(2)
A function 9" E G that attains minimum error E(g") = mingeg E(g) is a Bayes optimal classifier with respect to p", i.e. for each v E {0, we have that g (v) arg maxje (v. Thus,
min E(g) =1 gEG
Σ vE
maxp'(v.)) JElK]
(3)
We do not have access to labeled data for the unseen classes, so we cannot estimate p". Instead, we construct lower bound with respect to the set of all distributions that fit the available information.

---

4 Lower Bounds for Zero-Shot Learning with Attributes
In this section, we formally define our lower bound. Consider a PMF p with support over 1)" x [k] We say that p satisfies the class-attributt matrix A if (as constraints (T) for each i E [n] and [k]
Σ p(u,j) = A,,4 E p(u.j) 1
(4)
vE10,11"
Recall that p is balanced if for each j E [k], it holds that Ev p(v.j) j)- 1/k: Let ((4) be the set of all possible PMFs p with support over {0, 1] [k]] that satisfy 4 and are balanced. Clearly, the unknown true distribution. p" E P(AA). The set ((A) can be interpreted as the collection of all the PMFs of the random vector (th1,-..,, tin y) that satisfy the constraints imposed by the information available on the prediction task and on the attribute functions. While the matrix A the correlation between any pair of attribute function and class,
provides precise information fails to provide information on the correlation between attribute functions, i.e., it does not fully specify the distribution p². Without additional information, any PMF P(A) could be equal to p". Similarly to 2 given a PMF p E P(A) and an attribute-class classifier E G, we can define the error of g with respect to the distribution p as
E p) -
Σ p(v,g(o)) (0.1)
(5)
Following the computation in 3b. the error of the best map from attributes to classes with respect to p E P(A) is computed
(p) = min c(g, p) =1
Σ
max p(v. j) sE|k]
(6)
.EG
wa ve
We are interested the quantity
Q
max Q(p) PEP(A)
i.e. Q the maximum over all distributions p E P(A) of the error of the best algorithm for distribution In other words, Q is the worst Bayes error with respect to all the distributions that satisfy the constraints imposed by the class-attribute matrix and on the class probabilities. Since p" can be any vector in P(A), the value Q represents a lower bound to the best error rate that an algorithm can guarantee. In fact, without further information on the attribute functions or the prediction task, it is possible that p" attains the maximum of 7 that is in the worst-case we have that
<(g.p') = {()) 2 Q Vgg E
In other words, the quantity Q reflects a worst-case scenario where the attribute functions are correlated in such way that it is hard distinguish between the classes, even if the attribute functions still satisfy the constraints ① given by the class-attribute matrix A. In Section 4.3] we show that this lower bound is tight. In particular, prove that there exists randomized classifier from the attribute space f0, 1 to the classes [k] whose expected error is at most Q with respect to any distribution p E P(A).
Example. Consider a balanced binary classification task with two attributes. The class-attribute matrix A E R222 is such that Ar,; 1/2 for i,j E {1, 2}. Based on this class-attribute matrix, we consider two different scenario. the first scenario (best-cuse), we have that items from the first class have either both attributes none with probability 1/2, and items from the second class have only either the first attribute or the second attribute with probability 1/2. In this case, we can simply count the number of attributes that item has to assign it to the correct class. In the second scenario (worst-casee each item has either both attributes or none with probability 1/2 independently from the item class. In this case, any mapping from the attributes to the class is going to incur error of 1 1/2.
4.1 Computing the Lower Bound
In this subsection, we show how to compute Q as 7 through a Linear Program (LPP). To describe a generic PMF p. we introduce 2n x k variables qoo with v E {0, 1)"h and E [k]. We use additional
5

---

2" auxiliary variables λ. for a E {0, to denote the maximums of @ Xo ma te.j- The LP formulated as follows.
Q = min A
(8)
a
Σ
L AJ,
Σ
Vj [k], [n]
eE(o,1)";
=E(0,1}
m/1
1
(6)
Σ
qu
Aj E [k]
k
(0.1)
(c) 2 2 Tu.j 20
Vo E [0,1)",j
Theorem 4.1. The optimal value of the LP 8 is equal to Q. with Q is as in 6
By removing modifying constraint (b) of the LP, it is possible remove the assumption that the classes are balanced or provide different class weights. All the previous results still hold by changing the definition of (AA) accordingly. It is important point out that since a worst-case lower bound, the class weights provide significant information. Without constraints on the class weights, the worst-case distribution could concentrate all the probability mass on few classes that are hard to differentiate using the available class-attribute matrix A.
computing
The LP has O 2n) variables and constraints, and therefore it is computationally expensive for large number of attributes. The dependency on 2" is required to describe all the possible correlations between the output of the attribute functions. Nevertheless,
present efficient computation for the binary case the next subsection, and an efficient approximation for the general case in Appendix
4.2 Lower Bound for Binary Classification
this subsection, we show how to efficiently compute Q as task, i.e. k = 2 and A = [0, 1|28n For ease of notation, let
7 in the case of a binary classification
On B.,
B1
Theorem 4.2. Consider balanced binary classification task and let A be as in (.. Let Q be as in It holds that 1 (1 maxie[n] 13: asl). Moreover, let Ja be the attribute-clas classifier 2
U/.
if a4- < Bi-
(a(v)= = 1+
1-- Us-
af 2 Bi-
for each v E 13", where arg max, 133 - asl and Vs is the i-th component of the vector v. Then Egga, p) = Q for all p P(A), i.e. the lower bound Q is tight.
The theorem shows that the worst-case, the attributes could be correlated such a way that is not possible to do better than deciding solely based on the attribute with the largest gap between its probabilities in the two classes. This result also formally proves that for binary classification, the worst-case is determined by single attribute, and there is no compounded benefit in having multiple attributes in the case of perfect attribute detectors. This result in the context of weak supervision. In Mazzetto et al. 2021b), it is noted that while combining the output of different weak supervision sources to obtain a noisy label given input item, in the worst-case one cannot do better than just using the most accurate weak supervision source without additional information. In Appendix C, we show how to approximate the lower bound the multiclass setting by using Theorem 4.2
line with other worst-case analyses
4.3 Lower Bound is Tight
In this subsection, we prove that the worst-case lower bound 7 is tight. We show a randomized attribute-class classifier whose expected error is upper bounded by Q with respect to any distribution p E P(A). This classifier can be computed only based on the class-attribute matrix, and provides an upper bound the error of the best map from attributes to classes that matches the lower bound.

---

We consider the family GR of all randomized attribute-class classifiers, where each g E GR is random map from {0.1)" to [k). A attribute-class classifier in In described with right-stochastic matrix W E [0, 1]2"x,, where the rows are indexed by binary vectors E {0, 1)", and the columns are indexed by the classes j E [k]. The entry We.j represents the probability of the randomized classifier to output j given that the input is v. We will use gw to denote the randomized classifier in On that is described with the right-stochaste matrix W. Given a PMF p over {0, 1}" x [k], we
define the expected error of gw as
e(gw, p) = IP (nj))~p
Low (t) - =1
Σ
E
Wes p(u,))
(10)
WE (0 JElK
We can observe that the definition above extends definition 5 in fact a deterministic classifier, i.e. each row of W contains a 1.
10 coincides with 5 if gw
Theorem 4.3. There exists a randomized attribute- class classifier ga GR such that its worst-case expected error is upper bounded by Q, i.e. maXpeP(A) E(Ga.)) S Q, where Q is computed as in ①. Also, it holds randomized functions GR-
mingegæ (gg p) = Q, Lee. the lower bound Q also applies to the family of
It is possible to compute the randomized attribute-class classifier Ja that satisfies Theorem solely based on the matrix A through Linear Programming using O 2?) variables and constraints. Due to space constraints, we defer this computation to Appendix B
5 Empirical Applications
In this section we compare our novel theory with the performance of popular attribute-based ZSL methods. Our results quantify lower bound the lowest error rate that any attribute-based ZSL algorithm can guarantee based on the information provided by the class-attribute matrix. In practice, we show that the lower bound is still predictive of the performance and the behaviour of attribute-based ZSL algorithms. We run two set of experiments.
1. Comparing the lower bound and the empirical error (Section 5.2)
We compare the error rates of ZSL. models with attributes with the lower bound on the error from Section
2. Pairwise misclassification prediction (Section 5.3). We measure the predictive power of our lower bounds to identify pairs of classes that ZSL models are likely to misclassify. This hardness is measured using the lower bound on the error for pair of classes (Section
5.1 Experimental Setup
In this section, we briefly describe the experimental setup. Further details about the datasets and the methods can be found in Appendix D We choose the following four datasets with attributes
that are widely used benchmarks in ZSL: Animals with Attributes 2 (AwA2) (Xian et al. 201 Sa).
(CUB) (Wah et al. 2011), and SUN attribute database (SUN) (Patterson et al. 2014). We focus on classic ZSL algorithms with attributes that use at most the information in the class Mass-attribute matrix for the unseen classes: Cannera-Paredes & Torr 2015). SAE (Kodirov et al.) (017)). ALE AAkta et al. (016)) SJE (Akata et 2015). We choose these methods because they use the class-attribute matrix that is the focus of our theoretical analysis. Many other 7SI. methods have been proposed in recent years (see Section 2 ). but their comparison with our lower bound would be vacuous as they often not fit within our novel theoretical framework. They are beyond the scope of this first analysis of ZSL, However, we also run experiments more recent attribute-based method DAZLE (Huynh & Elhamifar 2020) which takes advantage of additional information, i.e., attribute semantic vectors.
aPascal-aYahbn (aPY) (Farhadi al. 2009). Caltech- UCSD Birds-200-200
DAP (Lappet et al. 2014), ESZSL
other source of auxiliary information the unseen classes, and thus do
5.2 Comparing Lower Bound and Empirical Error
In this section, we compare the lower bound presented in Section gl with the actual error of the 7SL models. To this end, we run two set of experiments: a first set using the ZSL. datasets mentioned in
Cooee is available at http://hhw..cooeeeeeeeeeeeeeeeaa
com/
7

---

APM: Errors
AINA7: Frrors
1.0-
10-
1.00
69-
DIZAL
1.00
E.7-
6.7
65
8.00
DATIC
DAZLC
Number atbrisutes
Number of atbributes
Number attributes
APY: Adversarial D stribution
AWAZ: Adversaral Distribution
Dea
0.5
010
Ereor
6.5
D4F
63
Number attrbbute
Number atbributes
Kumber attributes
Figure 1: Comparison of the lower bound with the empirical error. We plot the lower bound on the error (Q), and the error of ZSL methods with attributes (DAP, ESZSL, SAE, ALE, and DAZLE). The first row reports these values computed on the unseen classes of the aPY, AwA2, and CUB, varying the number of available attributes. The second row reports the values for the adversarially generated synthetic data. The bands indicate the standard errors on five runs with different seeds for randomized methods. These results validate that even in the absence of domain shift, there exists a distribution of the data that satisfy the constraints imposed by the class-attribute matrix for which no method can do better than the lower bound.
the previous subsection, and a second set using adversarially generated synthetic data that conform with the class-attribute matrices of those same ZSL datasets.
In the first set of experiments, we follow the standard way evaluate ZSL models. We train our model on the seen classes, and then compare our lower bound with the empirical error of the ZSL models on the unseen classes. Since the computation of the lower bound very expensive for a large number of attributes (Section 4. we focus on a subsets of them. We propose the following greedy strategy ensure selection of attributes that are informative with respect to the target classes. Starting with no attributes, we iteratively add the attribute that decreases the most the value of the lower bound, up to 15 attributes. Due to the large number of seen classes of SUN and CUB, we restrict them to a smaller random subset (see Appendix D). In the first row of Figure D we report results for aPY, AwA2, and CUB, due to space constraints. The results for SUN are similar and in Figure g in Appendix
We observe that the value of the lower bound can be significantly lower than the error rate of the ZSL models. This gap is most probably due to the fact that the learned map from images to attributes does not generalize perfectly the unseen classes. In fact, in this setting we can identify two main source of eтror for the ZSL models: (1) the arbitrary error due to the domain shift, and (2) the error due to how discriminative the attribute space to differentiate between the different classes. Our lower bound only addresses the latter, as no method can guarantee a smaller error than the lower bound to map from attributes to classes given only the information of the class-atrribute matrix. Nonetheless, for CUB and SUN we observe that the empirical error of ZSL models roughly follow the trend of the lower bound. This suggests that the lower bound can still be used as tool to capture how the additional information provided by an attribute leads to improvements of the 7SL models.
In the second set of experiments, we empirically demonstrate our theory by showing that even if we minimize the error due to domain shift, there exists data for which no method can do better than our lower bound. To this end, for each dataset we adversarially generate synthetic data with attribute values satisfying the dataset's 's matrix with 15 attributes as in the previous set of experiments in order to compute the adversarial distribution p over attributes and classes according to the linear program introduced in Section I. The data generated by sampling attribute-class pairs from this distribution, and using the attribute vector as the feature vector. In order to minimize the error due to domain shift, this distribution is used to generate data for both training and testing of the 7SI. methods, and the same atts-btt matrix is used for both seen and unseen classes. We report additional details on this experimental setup and
matrix. Specifically, we use the same
8

---

Fairw se Lewer Bound Error Matrix IL.
Misclassification error matrix DMP (M)
sclassification error matrix of ES25), (M
denkey
600
gat
.018
pecl
metorbiw
neterilo
nelen
ponoddtine
Figure 2: Pairwise miscassification matrices. For the unseen classes of aPY, we plot the pairwise
lower bound between pair of classes L (Section 4.2) and the misclassification error matrix M of two ZSL models: DAP and ESZSL. Darker squares indicate higher values, and light blue on the diagonal is O. High values of the lower bound indicate classes that are harder (in the worst-case) distinguish
in theory, and high values M indicate pair of classes that are often confused by the ZSL model.
synthetic data generation Appendix D We report the results of the experiments in the second row of Figure iterating over the same attributes greedily selected in the first set of experiments for each dataset. (For this set of experiments, we do not report results for DAZLE as this method relies on the input items being images, so it does not apply to our synthetic data.) In this case, the methods able to achieve errors that are comparable with the lower bound as we minimized the error due to domain shift. This experiment empirically validates that distribution of the data that satisfy the constraints imposed by the class-attribute matrix for which no method can do better than the lower bound. This adversarial distribution represent an intrinsic error gap due to the quality of the information provided by the class-attribute matrix. This is the first work to quantify such information in ZSL.
in the absence of domain shift, there exists
5.3 Pairwise Misclassification Prediction
Theorem shows how to efficiently compute the lower bound on the error to distinguish between pair of classes given the class-attribute matrix. In addition to the overall bound on error, it also gives us fine- aine-grained information about which classes are harder to distinguish among. We define the pairwise lower bound error matrix L, whose entry Lj j the lower bound on the error computed as in Section 4.2 for all classes j.j" E [k], j * j'. A large entry Lj.' between two classes j # j' indicates that hard (in the worst-case) to distinguish between them. In this section, we compare the matrix L with the classification errors made by the ZSL models discussed in Section 5.1 In particular, the misclassification
we want show the pairwise lower bounds on the errors are predictive errors made by the ZSL models. Specifically, a large lower bound on the error for pair of classes indicates that a ZSL model would likely confuse one class with the other. For a given dataset and ZSL method, we build a misclassification error matrix M. The entry Mj is computed as
IP (h(x)= = A v(x) = j'lu(x) E {1.5')) + P (h(x)) = 3' v()) = Aly()) e (i,1)) 2~D
DnD
for all j,j E [ j', where h(()) is the 7SL model. The entry Mj. represents the probability of the model to misclassify an item of the class j with the class j' or vice-versa. We estimate M using test data of the unseen classes.
In Figure we plot together with the misclassification matrices M of two ZSL methods: DAP and ESZSL, computed on the unseen classes of aPY. The pairwise lower bound matrix L has large values within multiple groups of semantically similar classes, e.g., animals and transportation means. This is in line with human intuition, as we expect visually similar classes to exhibit similar attributes. Correspondingly, the misclassification matrices of DAP and ESZSL highlight the presence of many emror for classes belonging to these groups. We also note that ZSI. models could misclassify other pairs of classes due to other source of errors, such as an inaccurate map from image to attributes. We report additional experimental analysis on all datasets in Appendix

---

Conclusions, Limitations, and Future Work
We present the first non-trivial lower bound on the best error that an attribute-based ZSL method can guarantee given the information provided-the class attribute matrix. While method is limited to class-attribute matrices, it constitutes a first theoretical building block to quantify the auxiliary information provided in ZSL. In general, theoretical evaluation of the error of ZSL models remains hard problem due to the arbitrary domain shift between seen and unseen classes, and the wide range of possible auxiliary information used. As future direction, it remains open problem to be able quantify this information for other families of ZSI. methods. However, our analysis readily extends to other variants of LSL,, such generalized 7SL., where we simply the class-attribute matrix of the union of both seen and unseen classes while computing our lower bound.
Broader Societal Impacts
Zero-shot learning is now popular scenario in research, with potential application real-world language and vision tasks. Worse-case guarantees have long been desired in ZSL. Any improvement in the rigor of claims about model performance has impact because it demonstrates both what performance can be achieved and that some solutions are invalid. However, such bounds do not cover many kinds of error, such generalization gap from domain shift label errors. Further, is important that bounds are correctly interpreted such that no false claims or confidences are drawn from our findings. An educated interpretation of the effect of these bounds upon any particular machine learning application is still required.
Acknowledgements
We thank Michael Littman and James Tompkin for many helpful and insightful discussions. This material is based research sponsored by Defense Advanced Research Projects Agency (DARPA) and Air Force Research I Laboratory (AFRL. under agreement number FA8750-19-22 1006 and by the National Science Foundation (NSF) under award IIS- The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of Defense Advanced Research Projects Agency (DARPA) and Air Force Research Laboratory (AFRL) or the U.S. Government. We gratefully acknowledge support from Google and Cisco. Disclosure: Stephen Bach is an advisor to Snorkel AI, company that provides software and services for weakly supervised machine learning.
References
Akata, Z., Reed, S. E., Walter, D., Lee, H., and Schiele, B. Evaluation of output embeddings for fine-grained image classification. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
Akata, Z., Perronnin, F., Harchaoui, Z., and Schmid, C. Label-embedding for image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2016.
Arachie, C. and Huang, B. A general framework for adversarial label learning. Journal of Machine Learning Research, 22(1 1-33, 2021.
Ba, J., Swersky, K., Fidler, S., and Salakhutdinov, R. Predicting deep zero-shot convolutional neural networks using textual descriptions. 2015 IEEE International Conference Computer Vision (ICCV), 2015.
Balsubramani, A. and Freund, Y. Optimally combining classifiers using unlabeled data. In Conference on Learning Theory, pp. 211-225. PMLR, 2015.
Ben-David, S., Blitzer, J., Crammer, K., Kulesza, A., Pereira, F., and Vaughan, J. W. theory of learning from different domains. Machine learning. 79(1)111-175,, 2010.
10

---

Brown, T. B., Mann, B., Ryder, N., Subbiah, M., Kaplan, J., Dhariwal, P., Neelakantan, A., Shyam, P.. Sastry, G., Askell, A., Agarwal, S., Herbert- Voss,, A., Krueger, G., Henighan, T., Child, R.. Ramesh, A., Ziegler, D. M., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Advances in Neural Information Processing Systems (NeurIPS) 2020, 2020.
Chang, M.-W., Ratinov, L.-A., Roth, D., and Srikumar, V. Importance of semantic representation: Dataless classification. In AAAI Conference Artificial Intelligence (AAAI), 2008
Changpinyo, S., Chao, W.-L., and Sha, F. Predicting visual exemplars of unseen classes for zero-shot learning. 2017 IEEE International Conference on Computer Vision (ICCV), pp. 3496-3505, 2017.
Dietterich, T. G. and Bakiri, G. Solving multiclass learning problems via error-correctigg output codes. Journal of artificial intelligence research, 2:263 286, 1994.
Edmonds, J. Paths, trees, and flowers. Canadian Journal of mathematics, 17:449-467 1965.
Farhadi, A., Endres, I., Hoiem, D., and Forsyth, D. Describing objects by their attributes. In 2009 IEEE conference on computer vision and pattern recognition, pp. 1778-1785. IEEE, 2009.
Felix, R., Kumar, B. V., Reid, I. D., and Carneir,, G. Multi-modal cycle-consistent generalized zero-shot learning. In ECCV, 2018.
Frome, A., Corrado, G. S., Shlens, J., Bengio, S., Dean, J., Ranzato. M., and Mikolov, T. Devise: deep visual-semantic embedding model. In Advances in Neural Information Processing Systems (NeurIPS), 2013.
He, K., Zhang, X., Ren, S., and Sun, Deep residual learning for image recognition. 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Huynh, D. and Elhamifar, E. Fine- Fine-grained generalized zero-shot learning via dense attribute- -ased attention. IEEE Conference on Computer Vision and Puttern Recognition, 2020.
Jakulin, A. and Bratko, I. Analyzing attribute dependencies. In PKDD, 2003.
Jayaraman, D. and Grauman, K. Zero-shot recognition with unreliable attributes. Advances in neural information processing systems, 27, 2014.
Kampffmeyer, M., Chen, Y., Liang, X., Wang, H., Zhang, Y., and Xing, E. P. Rethinking knowledge graph propagation for zero-shot learning., In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Kodirov, E., Xiang, T.,, and Gong, S. Semantic autoencoder for zero-shot learning. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2017.
Lampert, C. H., Nickisch, H., and Harmeling, S. Learning to detect unseen object classes by between- class attribute transfer. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pp. 951-958. IEEE, 2009.
Lampert, C. H., Nickisch, H., and Harmeling, S. Attribute-based classification for zero-shot visual object categorization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014.
Lawler, E. L. Combinatorial optimization: networks and matroids. Courier Corporation. 2001.
Li, J.. Jing, M., Lu, K., Ding, Z., Zhu, L., and Huang, Z. Leveraging the invariant side of generative zero-shot learning. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Luo, Y., Zheng, L.,, Guan, T., Yu, J., and Yang, Y. Taking a closer look at domain shift: Category-level adversaries for semantics consistent domain adaptation. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Mansour, Y., Mohri, M., and Rostamizadeh, Domain adaptation: Learning bounds and algorithms. arXiv preprint ar 030233090.,3430, 2009.

---

Mazzetto, A., Cousins, C., Sam, D., Bach, S. H., and Upfal, E. Adversarial multi class learning under weak supervision with performance guarantees. In International Conference on Machine Learning. pp. 7534-7543. PMLR, 2021a.
Mazzetto, A., Sam, D., Park, A., Upfal, E., and Bach, S. Semi-supervised aggregation of dependent weak supervision sources with performance guarantees. International Conference on Artificial Intelligence and Statisticy, pp. 3196-3204. PMLR, 2021b.
Mirza, M. and Osindero, S. Conditional generative adversarial nets. ArXiv, 2014.
Narayan, S., Gupta, A., Khan, F. S., Snoek, C. G. M., and Shao, L. Latent embedding feedback and discriminative features for zero-shot classification. ArXiv, 2020.
Nayak, N. V. and Bach, S. H. Zero-shot learning with common sense knowledge graphs. arXiv:2006. 10713 [cs.LG], 2020.
Neumann, J. v. Zur theorie der gesellschaftsspiele. Mathematische annalen, 100(1):295-33) 1928.
Obeidat, R., Fern, X., Shahbazi, H., and Tadepalli, P. Description- based zero-shot fine- ene-grained entity typing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies (NAACI-HIT)) 2019.
Palatucci, M., Pomerleau, D., Hinton, G. E., and Mitchell, T. M. Zero-shot learning with semantic output codes. Advances neural information processing systems, 22, 2009.
Patterson, G., Xu, C., Su, H., and Hays, J. The sun attribute database: Beyond categories for deeper scene understanding. International Journal of Computer Vision, 108(1-2):59 81, 2014.
Pinheiro, P. H. O. Unsupervised domain adaptation with similarity learning. 2018 IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2018.
Pourpanah, F., Abdar, M., Luo, Y.. Zhou, X., Wang. R., Lim, C., and Wang, X. review of generalized zero-shot learning methods. ArXiv, abs/201 1.08641, 2020.
Radford, A., Kim, J. W., Hallacy, C., Ramesh, A., Goh, G., Agarwal, S., Sastry, G., Askell, A., Mishkin, P., Clark, J., et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learening (ICML), 2021.
Pareees,, B. and Torr, P. H. S. An embarrassingly simple approach to zero-shot learning. In ICML,, 2015.
Sanh, V., Webson, A., Raffel, C., Bach, S. H., Sutawika, L., Alyafeai, Z., Chaffin, A., Stiegler, A.. Scao, T. L., Raja, A., Dey, M., Bari, M. S., Xu, C., Thakker, U.. Sharma, S. S.. Szezechla, E., Kim, T., Chhablani, G., Nayak, N., Datta, D., Chang, J., Jiang, T.-J., Wang, H., Manica, M., Shen, S., Yong, Z. X., Pandey, H., Bawden, R., Wang, T., Neeraj. T., Rozen, J., Sharma, A., Santilli, A., Fevry, T., Fries, A., Teehan, R., Biderman, S., Gao, L.., Bers, T., Wolf, T., and Rush, A. M. Multitask prompted training enables zero-shot task generalization. In International Conference on Learning Representations (ICLR), 2022.
Sener, O., Song, H. O., Saxena, A., and Savarese, S. Learning transferrable representations for unsupervised domain adaptation. In NIPS, 2016.
Socher, R., Ganjoo, M., Manning, C. D., and Ng, A. Zero-shot learning through cross-modal transfer. In NIPS, 2013.
Wah, C., Branson, S., Welinder, P., Perona, P., and Belongie, S. The Caltech- Birds-200-2011 Dataset. Technical Report 1---012--000000 California Institute of Technology, 2011.
Wang, X., Ye, Y., and Gupta, A. Zero-shot recognition via semantic embeddings and knowledge graphs. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2018.
Wang, Y., Kwok, T., Yao. Q. and Ni, attributes. In 2017 International Joint Conference on Neural Networks (ICNN), pp. 3777-3784. IEEE, 2017.
L. M. Zero-shot learning with partial set of observed
12

---

Wei, J., Bosma, M., Zhao, V. Y., Guu, K., Yu, A. W.. Lester, B., Du, N., Dai, A. M., and Le. Q. V. Finetuned language models are zero-shot learners. In International Conference on Learning Representations (ICIR), 2022.
Xian, Y., Lampert, C. H., Schiele, B., and Akata, Z. Zero-shot learning comprehensive evaluation of the good, the bad and the ugly. IEEE transactions on pattern analysis and machine intelligence, 41(9):2251 2265, 2018a.
Xian, Y., Lorenz, T., Schiele, B., and Akata, Z. Feature generating networks for zero-shot learning. 2018 IEEL/CVT Conference on Computer Vision and Pattern Recognition, 2018b.
Xian, Y., Sharma, S., Schiele, B., and Akata, Z. F-vaegan-d2: A feature generating framework for any-shot learning. 2019 IEEE/CVE Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
Zhang, L.,, Xiang, T., and Gong, S. Learning deep embedding model for zero-shot learning. 2017 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), 2017.
Zhang, Z. and Saligrama, V. Zero-shot learning via semantic similarity embedding. IEEE International Conference Computer Vision (CVPR), 2015.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] We describe limitations as they
appear, and repeat the major limitations the conclusion.
(c) Did you discuss any potential negative societal impacts of your work? [Yes] In the conclusion.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all thcoretical results? [Yes] Section 3-4 goes in details on describing our mathematical results.
(b) Did you include complete proofs of all theoretical results? [Yes] All the proofs are included the appendix in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] We give full details on experimental setup in the main paper and Appendix. We also provide the code as supplementary material. A public GitHub will be available upon acceptance. (b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] These details are provided in the Appendix. We use original data splits from the datasets and hyperparameters according to their original implementation and recommandation.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] For non-deterministic methods, report the standard deviation over runs.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] In the appendix.
4. If you using existing assets (e.g., code, data, models) curating/releasing
assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] In the appendix.
(c) Did you include any new assets either in the supplemental material URL? [Yes]
We provide our code in the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're rou're
using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "veJBjLdk7i", "reviewer": "Reviewer_Rmpv", "summary": "This paper presents a tight lower bound for attribute-based zero-shot learning based on the class-attribute matrix. When compared with previous bound from limit amount of work studying this, the proposed bound is the first non-trivial tight lower bound.  The proposed bound is empirically validated with several methods on popularly used benchmark datasets, and can be also used for pairwise misclassification prediction. ", "questions": "- Application of the bound, can it be used to improve the zero-shot learning performance? Or come up with new methods?", "limitations": "- This bound reveals the importance of class-attribute matrix, which itself is very hard to obtain in real-world application", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- First right non-trivial bound for attribute-based zero shot learning\n- Good empirical study to demonstrate the bound and its application\n- Source code provided \n\nWeakness\n- How can this bound used for improve zero-shot learning in addition to the pairwise misclassification prediction?\n- Any relationship between pairwise misclassification from this method and from confusion matrix? (PS: I know there is no samples for unseen class)", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Z6GBd756G6c", "reviewer": "Reviewer_9VLD", "summary": "This paper studies the generalization of zero-shot learners with access to attributes. In this work, zero-shot learning is decomposed into two stages as is typically done in practice. The first stage consists of learning to extract attributes from input data. In the second stage, new classes are presented and must be classified using the attribute information that was extracted during the first stage. The results presented in this paper are applicable to the second stage under the assumption that attribute extraction can be learned perfectly.\n\nThe authors derive the Bayes optimal classifier for this second stage in terms of an unknown joint distribution over attributes and labels. By considering constraints on this joint distribution in terms of the class-attribute matrix, they are able to produce a lower-bound, $Q$, on the error of a Bayes optimal classifier. A linear program is then designed whose optimal solution corresponds to this $1-Q$. They solve this LP for balanced binary classification and show that the lower-bound is tight in this case.\n\nThe authors then show that this lower bound is tight in general by showing that a randomized attribute-class classifier can be designed whose error is upper-bounded by the lower bound. Moreover, this classifier can be computed as the solution of a linear program.\n\nThe empirical analysis confirms the theoretical findings on a number of standard ZSL classification problems. Two sets of experiments are conducted: first using the standard ZSL setup, and second using synthetic attribute labels that are generated to match the class-attribute matrix for each task. The lower bound is respected in both cases.\n\n**Post-rebuttal:** Following the author's response, I have increased my score from Weak Accept to Accept. After reviewing the literature referenced by the authors, I am in agreement that the results are a great contribution than I thought them to be initially.", "questions": "My main concern with this work is the extent to which the results generalize to the true ZSL setting where there is a distribution shift and the attribute functions must be learned. I am also concerned that the results presented may already be known within the boolean function learning literature --- I hope that another reviewer has greater expertise in this area or that the authors themselves can comment on this comparison.\n\nThe authors write that \"this result also formally proves that for binary classification, the worst-case is determined by a single attribute, and there is no compounded benefit in having multiple attributes\". This statement is entirely dependent on the fact that all attribute functions are assumed to be given to the classifier. In a true ZSL setting, where these attribute functions must be learned, some attributes may be easier to recover than others and so we would certainly expect a compound effect from having access to multiple attributes.\n\n### Minor comments\n\nMinor comments:\n\nI personally find the concatenation notation to be confusing as it could be mistaken for a product. Perhaps consider adopting `[v, v']`, `cat(v, v')` or similar.\n\nSome extra structure (e.g. paragraph headings) in the preliminary chapter could make things easier to parse.\n\nBefore Equation 3, I would have found it useful to include a brief explanation in words of the optimal binary classifier. Something like: \"In words, the optimal classifier chooses the class which is most likely under the given attribute configuration.\"\n\n- L255: \"A[n] attribute-class classifier\"", "limitations": "The authors provide a thorough and balanced discussion of the limitations of their work. Here I include some additional minor suggestions.\n\nThe bounds presented are of the maximum of the minimum and not the more common minimax risk. The latter is more common in learning theory, as we want to know the performance of the best *learning* algorithm on the hardest problem we consider (thus the learner is problem-agnostic). The bound presented ignores learning and lower-bounds the best performance of a perfect classifier with all information of the task. In this case, by von Neumann's minimax theorem the two are equivalent (as is used in the proofs in the appendix). Perhaps this could be further discussed.\n\nAssuming access to the attribute functions is a strong assumption that moves away from the core of ZSL. The first stage of ZSL is typically to recover this attribute mapping. This two-stage decomposition is represented accurately in the fourth paragraph of the introduction, in the preliminaries. This limitation of the work is discussed in Section 6. It would be valuable to discuss this limitation in terms of the theoretical results that are presented too. What needs to be done to address both stages of learning? To what extent can errors in the attribute functions be incorporated into the proofs? Where does this fail?", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\nZSL is a particularly difficult area to establish theoretical results in. To my knowledge, the results presented in this work are novel and make progress towards understanding theoretical limitations of ZSL.\n\nThe empirical analysis is practically relevant and thorough. The authors evaluate their theoretical results on a good range of ZSL tasks. Further, they actively work towards matching the settings with their theoretical assumptions in their second set of experiments.\n\n## Weaknesses\n\nResults are interesting albeit simple in nature. The authors assume that the first stage of learning has been absolutely successful and the attribute functions have been recovered. They then analyze the worst-case error for the second phase where a classifier is learned from the attributes to classes. This is interesting and valuable but it excludes one of the key tenets of zero-shot learning: that some classes have no instances available at training time. This is addressed in the first phase of learning and is, arguably, the more interesting part of the ZSL paradigm. It is possible that the authors analysis can play a role in understanding the full ZSL pipeline, but no effort is made to understand this and I expect that the linear programs are too rigid to account for the necessary changes.\n\nThe authors are essentially studying classification with boolean functions with an additional distributional assumption. This is not an area of the literature that I know exceedingly well, but I would expect a discussion from the authors within their paper. Even initial work in this setting [1] capture the binary version of the classification problem that the authors consider.\n\n\n[1] A theory of the learnable. L. Valiant. Artificial Intelligence and Language Processing, 1984.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Xaahi2v--R1", "reviewer": "Reviewer_YtKa", "summary": "This paper studies a problem related to zero-shot learning. It aims to answer the question of what is the worst case performance of a classifier, if only given a binary attribute-class association matrix. The lower bound is expressed as a linear program that computes the maximum correlation between any pair of attributes. The paper presents a tight lower bound that can predict the performance of the best classifier given true attribute information of the inputs. However, there are also concerns that the problem being studied is too simple and constrained.", "questions": "- Why would the adversarial distribution generate a better error rate for other methods? Could you give an example of what the adversarial distribution looks like?\n\n- Is it correct to understand that all methods use images as input except the lower bound “Q”?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "--------------------------\nStrengths\n\n- The paper studies a simplified problem that frequently occurs in zero-shot learning and gives insight on when we expect the model to generalize to unseen classes that are defined by an attribute-class matrix.\n\n- The paper shows that the bound is tight.\n\n- The experiments show that the theory predicts the behavior relatively well, especially on adversarial distributions.\n\n-------------------------\nWeaknesses\n\n- The theory in the paper generates an intuitive explanation for binary classification (n=2). However, the linear program in general is hard to give an analytical interpretation.\n\n- Although the paper title mentions ZSL, the paper itself actually does not explicitly deal with ZSL but studies a much simpler form of error bound on using only input dimension statistics (probability of attribute i given class j). There might be a lack of mathematical depth for such a constrained problem.\n\n- The assumption might not be realistic enough. Many problems often give a couple attributes that “define” the class, rather than providing full statistics that span across all attribute dimensions. Many attributes are ones that we “don’t care”, and could be spurious attributes if they are provided to the classifier. For example, most of the zebras are on grass, and they are rarely in water. However, we shouldn’t consider these attributes in the classifier even if p(“grass” | zebra) might be close to 1.0, and p(\"grass\" | other animal) is small. This leads to the spurious feature problem, and the hope is that if we could learn disentangled attributes from the space, then it could be solved by focusing only on causal attributes. Now, with the framework presented here, it would be nice if it could be extended to cases where some entries in A are “don’t care”, which motivates the original formulation of ZSL. This might be a trivial modification to the paper but could make the setup more realistic. In the end, attribute-based ZSL should focus on attributes that define the class instead of attributes that correlate with the class.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "0wB1cgbZ-kN", "reviewer": "Reviewer_oqVB", "summary": "Authors derive a new bound for zero-shot learning (ZSL) corresponding to the worst-case Bayes Error, taken across all distributions that satisfy some given attribute-class matrix. The bound assumes access to a perfect item-to-attribute mapping. Authors show that computing the derived bound amounts to solving an LP problem. Authors show that this problem admits a closed-form solution in the binary case (given along with the expression of the actual classifier that achieves that bound), and can be approximated in the multi-class setting. They also show that the bound is tight in general.", "questions": "### Interpreting experimental results\n\nThe first row of Fig.1 is quite hard to interpret, because a large part of the gap between the lower bound and methods seems to be due to the poor item-to-attribute mapping generalization. I find the set of adversarial experiments more interesting. However, some methods do go below the lower bound, which lets me think that the actual \"best\" classifier could further 'break' the theoretical lower bound. Is this due to sampling / approximate computation of the bound in the multi-class setting ? Could authors clarify ?\n\n### Motivating the use of worst-case bounds\n\nI believe I'm not super clear with the motivation of using worst-case bounds for ZSL. The bound considers the performance of the best possible classifier in the worst-case distribution. However in practice, how likely is this to happen (such that the bound actually applies) ? The results on SUN dataset for instance, clearly show that the lower bound is way above most methods (even with the presence of training/testing shift), and the gap keeps increasing as the number of attributes increases. Would best-case lower bounds be trivial here? i.e. given some $\\textbf{A}$, how well could any method achieve, assuming the 'easiest' distribution compatible with $\\textbf{A}$ . I'd be curious to hear authors' thoughts.\n\n### Sanity checking\n\nBinary results would have been easier to sanity check / interpret, because less confounding factors. In particular, given that the found value Q neither depends on a particular distribution or on the number of attributes, there would be no need to adversarially choose the distribution or to worry about approximating Q, and a direct apple-to-apple comparison would have been possible. Is there any particular reason for not experimenting in a binary situation ?\n\n\n\n", "limitations": "Authors do discuss that the bound assumes perfect item-to-item mapping, which is far from true in real life. Authors also discuss the difficulty associated with computing the bound (scaling to multi-class and to multiple attributes).", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength\n\n- The paper is well written. As a non-expert for ZSL, I can say the notations and ideas were well introduced, and easy to follow. The proper amount of background on the problem was introduced.\n\n- The general problem of formally characterizing the difficulty of a zero-shot problem is an interesting one.\n\n- The work appears substantial to me. The formalization of the problem, the bound/its computation and the tightness results seem non-trivial and novel.\n\n- The result in the binary case appears non-trivial and could already be of practical relevance. If I understand correctly, authors provide a closed-form expression of a classifier $g_a(\\textbf{v})$ that is essentially optimal, independently of the distribution, i.e optimal $\\forall ~ p, ~ p \\in \\mathcal{P}(\\textbf{A})$. The classifier has a simple expresison that can be readily computed from the class-attribute matrix $\\textbf{A}$.\n\n## Weaknesses (c.f Questions below)\n\nC.f questions below\n", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}]

Author rebuttal:

Decision: Accept