Geometry-Aware Adaptation for Pretrained Models
Authors: Nicholas Roberts
Xintong Li
Dyah Adila
Sonia Cromp
Tzu-Heng Huang
Jitian Zhao
Frederic Sala
Venue: NeurIPS 2023 poster (2023)
Keywords: structured prediction
learning on graphs
partially observed label spaces
high cardinality label spaces
TL;DR: We propose a simple adaptor for pretrained models to enable the prediction of unobserved classes using metric space information.

Abstract: Machine learning models---including prominent zero-shot models---are often trained on datasets whose labels are only a small proportion of a larger label space. Such spaces are commonly equipped with a metric that relates the labels via distances between them. We propose a simple approach to exploit this information to adapt the trained model to reliably predict new classes---or, in the case of zero-shot prediction, to improve its performance---without any additional training. Our technique is a drop-in replacement of the standard prediction rule, swapping $\text{argmax}$ with the Fréchet mean. We provide a comprehensive theoretical analysis for this approach, studying (i) learning-theoretic results trading off label space diameter, sample complexity, and model dimension, (ii) characterizations of the full range of scenarios in which it is possible to predict any unobserved class, and (iii) an optimal active learning-like next class selection procedure to obtain optimal training classes for when it is not possible to predict the entire range of unobserved classes. Empirically, using easily-available external metrics, our proposed approach, Loki, gains up to 29.7% relative improvement over SimCLR on ImageNet and scales to hundreds of thousands of classes. When no such metric is available, Loki can use self-derived metrics from class embeddings and obtains a 10.5% improvement on pretrained zero-shot models such as CLIP.

Geometry-Aware Adaptation for Pretrained Models
Nicholas Roberts, Xintong Li, Dyah Adila, Sonia Cromp,
Tzu-Heng Huang, Jitian Zhao, Frederic Sala
University of Wisconsin-Madison 1robertss fredsala]@cs. (x1i2224, adila, cromp, thuang273, j edu
wesec...iss..o wisc.
Abstract
Machine learning models innells-includin prominent zero-shot models are often trained on datasets whose labels are only small proportion of larger label space. Such spaces are commonly equipped with a metric that relates the labels via distances between them. We propose simple approach exploit this in- formation to adapt the trained model to reliably predict new classes-or, in the case of zero-shot prediction, improve its performance-witheeee training. Our technique is drop-in replacement of the standard prediction rule, swapping arg max with the Fréchet mean. We provide comprehensive theoretical analysis for this approach, studying (i) learning- theoorttttt results trading off label space diameter, sample complexity, and model dimension, (ii) characterizations of the full range of scenarios in which it is possible to predict any unobserved next class selection procedure
are
any additional
class, and (iii) an optimal active learning- obtain optimal training classes for when it is not possible to predict the entire range unobserved classes. Empirically, using easily-available external metrics, our proposed approach, LOKI, gains up to 29.7% relative improvement over SimCLR on ImageNet and scales to hundreds of thousands of classes. When no such metric is available, LOKI can use self-derived metrics from class embeddings and obtains a 10.5% improvement on pretrained zero-shot models such as CLIP.
1 Introduction
The use of pretrained models is perhaps the most significant recent shift in machine learning. Such models can be used out-of-thy of-the-box. either to predict classes observed during pretraining (as in ImageNet-traines ResNets [4] to perform zero-shot classification on any set of classes [32] While this is exciting, label spaces are often so huge that models are unlikely to have seen even single point with a particular label. Without additional modification, pretrained models will simply fail to reliably predict such classes. Instead, users turn to fine-tuning- -uning-which wwhich requires additional labeled data and training cycles and so sacrifices much of the promise zero-shot usage.
How can we adapt pretrained models to predict new classes, without fine-tuning or retraining? At first glance, this is challenging: predictive signal comes from labeled training data. However, relational information between the classes can be exploited to enable predicting class even when there are no examples with this label in the training Such relational data is commonly available, or can be constructed with the help of knowledge bases, ontologies, or powerful foundation models [39].
How best exploit relational structure remains unclear, with number of key challenges: We might wish to know what particular subset of classes rich enough to enable predicting many (or all) remaining labels. This is crucial in determining whether training set usable or, even with the aid of structure, insufficient. It is also unclear how approaches that use relational information interact with the statistical properties of learning, such as training sample complexity. Finally, performing adaptation requires an efficient and scalable algorithm.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

39
20
80
90
80
60
20
20
99
00 Tree Gragh
90
Grid Graph
96
Small-worls Graph
Figure 1: Classification regions in the probability simplex 3-class classifiers faced with a 100-class problem. The probability simplex using arg max prediction can only output of three classes. LOKI uses the entire probability vector to navigate the class metric space, leading to more prediction regions. (Left) regions from arg max prediction. (Centers, Right) classification regions from L.KT.
This work addresses these challenges. It proposes simple and practical approach to learning in structured label spaces, with theoretical guarantees. First, we offer a simple way to translate the soft outputs (i.e., probability vectors) produced by any supervised learning model into more general model that can exploit geometric information for label structure. In other words, our approach, called LOKI is simple adaptor for pretrained models. LOKI can be applied via fixed linear transformation of the model outputs. LOKI's simplicity makes it applicable to a broad range of settings while enabling very high-cardinan cardinality predictions subject to potentially small model output budget- we provide visualization of this key idea in Figure
Theoretically, provide rich of results for the metric-based adaptation setting. First, intro- duce a learning-theoretic result terms of the sample complexity of the pretrained model. It captures key tradeoff between the number of classes and metric structure, the problem dimensionality, and the number of samples used to train the model prior to adaptation. Next we exhaustively study the properties of training sets, determining for a wide class of relational structures the minimum number (and structure) of subsets that enable reliable prediction. Finally we show how to exploit this result in an active learning-like approach to selecting points that will improve deficient training datasets.
Experimentally, we show that using structural information improves prediction high-cardinaliis settings. We demonstrate the strength of the active learning-brit -asend approach to dataset expansion over random baselines. Finally, and most excitingly, we show that even in zero-shot models like CLIP, where it is possible to produce probability vectors any possible class, the of our adaptor leads to a 19.53% % relative improvement.
Background
First, introduce the problem setting, notation, and mathematical tools that will use. Afterward, we discuss how LOKI relates to prior work.
Problem Setting As in conventional supervised learning, we have dataset (x1 w,),...................... (In, Ma) drawn from a distribution on X' ), where and y are the input and label spaces. In our setting, N : | is finite but large; often N >> n so that many labels will simply not be found in the training dataset. We let C y with |A| K be the set of observed labels. For convenience of notation, also define X [
K 1 y [ to be the vectors of elements in A and y.
In addition to our dataset, we have access metric space with metric (distance) d y22 + I; d encodes the relational structure of the label space. Specifically, we model this metric space using a graph, G = ()), E) where C y x R. is a set of edges relating the labels and the standard shortest-path distance d : y22 - R2o. In addition to its use in prediction, the metric can be used for evaluating model by measuring, for example, E._, d² df the analogue of the empirical square loss.
relational structure on V. We assume that y is
Fréchet Mean Estimator Drawing on ideas from structured prediction 5 35
we use a simple
predictor that exploits the label metric. It relies on computing the Fréchet mean 8 given by
K
My (w) == arg min Σ
w..d(uu y:),
(1)
DEy
Refers to the 'locus' (plural: loci) of the Fréchet mean.

---

where E 220 is a set of weights. The Fréchet mean generalizes the barycenter to metric spaces and is often used in geometric machine learning [26].
Locus of the Fréchet mean. The locus of the Fréchet mean is the set of all Fréchet means under different weights (29) We write it (T UWEa (1mekk
(Ty) can be thought of the set of all labels in y that are reachable by the Fréchet mean given {yi j C and different choices of its parameter w. Intuitively, we can think of the locus for given dataset as describing how usable it is for predicting beyond the observed labels. Trivially, {y 1 = y, then l1(y) V. We are primarily interested in the case in which {y: H C y yet we still have lly = y. or that [II(y)) is at least sufficiently large.
2.1
Relation Prior work
LOKI is primarily related to two areas: zero-shot learning and structured prediction.
Zero-Shot Learning Like zero-shot learning (ZSL), LOKI is capable of predicting unobserved classes. Our framework is most closely related to generalized ZSL, which uses side information to predict both observed and unobserved classes, Many types of external knowledge are used in
34 10], ontologies [25], and logical rules [33]. Our work most closely related ZSL approaches that rely on knowledge graph information. Often, ZSL methods that use knowledge graph information rely on the use of graph neural network architectures 42 17 I8]. However, we note that these architectures can be hearyweight and can be challenging to scale up to extremely large graphs, whereas LOKI does not have architectural requirements and scales linearly in the size of the graph when K is small.
ZSL,, including text (28 38 9]. attributes 22 23 7 knowledge graphs 42
Structured Prediction Structured prediction (SP) operates in label spaces that are endowed with algebraic or geometrie structure 21).) This includes problems such predicting permutations [19]. non-Euclidean and manifold regression [31 and learning on graphs [2]. LOKI is the most immediately related to the latter, however, any finite metric space can be represented a graph, which further lends to the flexibility of our approach. Even in discrete structured prediction settings, the cardinality of the label space may be combinatorially large. As such, LOKI can be viewed simple method for adapting classifiers to structured prediction.
The Fréchet mean has been used in structured prediction but in approaches requiring training. In n - (z))d (v. y:), where azx) (K + nv1) Kg. K is the kernel
[5).f(2) f(z) arg mingey I matrix for a kernel k: X' x X IR, so that K., k(I;, ). (K ); = k(r, xi). v is regularization parameter. In other words, the weight wy corresponding to y; is the average produced by solving kernel regression problem at all points && in the dataset where l/k- = y:- It has also used in weak supervision (WS) for metric-equipped label spaces [1 (37, where the goal is produce labeled data for training structured prediction models.
Framework
We introduce our Seamwwor--Lok. We show how LOKI can be used to adapt any supervised classifier over set of K classes to much richer set of possible class predictions. It does so by weighting the Fréchet mean by the classifier's per-class prediction probabilities or logits, allowing to predict any class in the locus of the Fréchet mean- potentialy far more classes than the initial K. Next, we show how LOKI can be expressed as a fixed linear transformation of a model's I's outputs. Finally, we show that LOKI relates to standard classification.
3.1 LOKI: Adapting Pretrained Models
We describe our approach to adapting pretrained classifiersttrained on a set of classes A to the metric geometry of the label space Y enabling the prediction of unobserved classes.
We model unobserved classes y \ A using the Fréchet mean among observed classes weighted by their prediction probabilities Ply >1|æ and A). We denote the vector of model outputs as
3

---

P F//= == PA PA [P(y As/2 and E A)]
Then predictions using LOKI are given by
E MA arg min yey
Σ
PAdla df Ax).
3.2 LOKI as linear transformation of model outputs
Most standard classifiers output a vector of prediction probabilities, Pyla- whose entries conre spond to the confidence of predicting specific class. Predictions are typically given by ú e arg gl g (P
LOKI generalizes this prediction rule when viewed as a linear transformation
of g/a- Consider the LOKI prediction rule ú E ma ma (Pyl)) = arg min VEY Σ x (y, A:) = arg [ (DP u(=); where J,+ [-d A:)] D E R-NX is the matrix of negative squared distances between the observed classes and the rest of the label space. Thus LOKI can be used within standard classification pipelines when the model output P ylz is multiplied by the fixed matrix D.
3.3 Generalizing Standard Classification
We provide simple intuition for our approach. The fact that LOKI reduces to standard classification among the observed classes has several implications. This includes the idea that under our frame- work, forms of few-shot, zero-shot, hierarchical, and partial label learning all reduce to standard classification when additional metric information is introduced.
Generalizing the arg max prediction rule In the absence of this metric information-4 situation that we model using the complete graph and setting A = V--our framework also recovers standard classification. Indeed, both in terms of error modeling and in terms of inter-class similarity, the intuition of standard classification and of the 0-1 loss captured well by the unweighted complete graph-simply, treat all differences equally. This graph is given as K x = (V, y x {1))_i.e. every label equidistant from every other label. Plugging this into LOKI, we obtain the following:
9 mA MA y|z) arg min yEY
Σ PA (y, A.) arg min yEy
Σ PA A1 arg max Pa/
(E(K)
which is exactly the standard classification prediction rule.
Generalizing the 0-1 loss via the expected squared distance The expected squared distance E|d (y. 9)] is the standard loss function for many structured prediction problems. Note that accuracy fails in such settings since cannot distinguish between small and large errors. This is most clearly seen in the extreme case of regression, where test accuracy will virtually always be zero matter how good a trained model is. At the other extreme, the complete graph, this loss function becomes the standard 0-1 loss: E[d2 (y. 0)] E (y + 9}.. As adaptor for structured label spaces, use the empirical version of this loss to evaluate LOKI. Note that the expected squared distance I,
derive the standard MSE by setting d(y, 9) ly 5l. which is just the standard L1 distance metric. Other scores such as recall at top-k can be similarly obtained the cost of d(.,.) being true metric. In other words, Efd? ū)] is an very general metric that supports any metric space, and we use it throughout this work.
subsumes other metrics well. For example, when
4 Theoretical Results
Challenges and Opportunities The arg max of per-class model probabilities a ubiquitous component of classification pipelines in machine learning. In order to predict unobserved classes
using metric space information, LOKI replaces this standard component, As simple but significant change to standard pipelines, LOKI opens up new area for fundamental questions. There are three main flavors of theoretical questions that arise in this setting:
1. How does the performance of LOKI change function of the number of samples?
What minimal sets of observed classes are required to predict any class in the metric space?
3. How can acquire new classes that maximize the total number of classes predict?

---

Excitingly, we provide comprchensive answer to these questions for the most common metric spaces used in practice. First, we provide a general error bound terms of the number of samples, observed classes, problem dimension, and the diameter of the metric space, that holds for any finite metric space. Second, we characterize the sets of observed classes that are required enable prediction of any class, and show how this set differs for various types of metric spaces of interest. Finally, we provide an active learning algorithm for selecting additional classes to observe so as to maximize the number of classes that can be predicted and we characterize the types of metric spaces for which the locus can be computed efficiently. These results provide a strong theoretical grounding for LOKI.
4.1 Sample Complexity
What is the interplay between predicting unobserved classes based metric space information and standard Bearning-thhoree notions like the sample complexity needed to train a model? Our first result illustrates this tradeoff, and relates it to the squared distance loss. Suppose that only observe K S N of the classes at training time, and that we fit a K-class Gaussian mixture model. We use LOKI to adapt our pretrained classifier to enable classification of any of the N classes. We have that (a formal statement and interpretation are in the Appendix),
Theorem 4.1 (Informal LOKI sample complexity). Let Y be a set of classes represented by dimensional vectors under the Euclidean distance, and let A S y be the set of K observed classes. Assume that n training examples are generated by an identity covariance Gaussian mixture model over classes A. and that test examples generated over all classes V. Assume that estimate Gaussian mixture model on the training set and obtain probability estimates TP ysl (x) for E [K] for a sample (I, y.) from the test distribution. Then with high probability, under the following model,
D. mmx (((u)(/)))))))))))) = arg min
Σ
Pl (y,, (y,
yEY
(E[K]
the sample complexity of estimating target y. from the test distribution Dien with prediction ÿ. is:
Vd. )
log K/O
B(E.,))D.D. (d (y., U-)] 50
n1
log R1-3
R
where or is related to the sensitivity of the Fréchet variance to different node choices.
4.2 Optimal Label Subspaces
Next we characterize the subset of distinct labels required to predict any label using our label model with respect to various types of metric spaces.
We first consider label spaces whose metric is a tree graph-suse metrics are, for example, related to performing hierarchical classification and weak supervision (where only partial labels are available). We consider a special type of tree called phylogenetic tree, in which only the leaves can be designated as phyloe--pyloggeetiic trees are commonly used to relate the labels of image classification datasets. Afterwards we perform similar analysis for grid graphs, which are important for label spaces that encode spatial information. Finally, we discuss the case in which no useful metric information is available, i.c.. the complete graph.
Our goal in this section to characterize the properties and size of {A:) in each of these metric spaces such that we still have II(A) = y. We characterize 'optimal' subsets of classes in each of the spaces under a certain notions of optimality. We provide several relevant definitions pertaining to this concept, starting with notion of being able to predict any possible class using observed classes.
Definition 4.2 (Locus cover). Given set A C y for which we construct tuple of its elements A, if it holds that ITAA) y, then A is locus cover.
Definition 4.2 captures the main idea of LOKI- -usin some set of observed classes for which we can train classifiers, we would like to able to predict additional unobserved classes using the geometry that relates the observed and unobserved classes. Namely, elements of IT(A) are 'reachable" using LOKI. We refine this Definition to describe the trivial case that defaults to standard classification and the nontrivial case for which LOKI moves beyond standard classification.
5

---

Definition 4.3 (Trivial locus cover). If A = V, then A is the trivial locus cover.
This Definition captures the notion of observing all of the classes in the label space. Here, all of the elements of y are trivially reachable using LOKI.
Definition 4.4 (Nontrivial locus cover). A locus cover A is nontrivial if A + V.
LOKI is more useful and interesting when faced with a nontrivial locus cover under Definition 4.4 can some subset of classes A to predict any label in y.
Definition 4.5 (Minimum locus cover). Given set A _ Vf if A is the smallest set that is still locus cover, then it is a minimum locus cover.
In cases involving an extremely large number of classes, it is desirable to use LOKI the smallest possible set of observed classes A such that all labels in ) can still be predicted. Definition 4.5 characterizes these situations- later, we obtain the minimum locus covers for all trees and grid graphs. It is worth noting that the minimum locus cover need not be unique for a fixed graph.
Definition 4.6 (Identifying locus cover). Given set A C V. if A is a locus cover where Vy E ), Aw E A |||-1 such that mA ma(w) (w) = {v). then A is an identifying locus cover.
The Fréchet mean need not be unique-as an arg min, it returns set of minimizers. In certain metric spaces, the minimum locus cover can yield large sets of minimizers this is undesirable, as it makes predicting a single class challenging. Definition 4.6 apppeals the idea of finding some set of classes for which the Fréchet mean always returns a unique minimizer this is desirable in practice, and in some cases, moreso than Definition 4.5
Definition 4.7 (Pairwise decomposable). Given A V, IIA) is called pairwise decomposable when it holds that (A) = A (elx)
In many cases, the locus can be written in a more convenient form union of the locus of pairs of nodes. We refer to this definition as pairwise decomposability. Later, we shall see that pairwise decomposability is useful in computing the locus in polynomial time.
Trees Many label spaces are endowed with tree metric in practice: hierarchical classification, in which the label space includes both classes and superclasses, partial labeling problems in which internal nodes can represent the prediction of set of classes, and the approximation of complex or intractable metrics using a minimum spanning tree. We show that for our purposes, trees have certain desirable properties that make them easy to use with noml-n that we can easily identify locus cover that satisfies both Definition 4.5 and Definition 4.6 Conveniently, we also show that any
locus in any tree satisfies Definition 4.7
We first note that the leaves of any tree yield the minimum locus cover. This is a convenient property any label from any label space endowed with tree metric can be predicted using LOKI using only classifiers trained using labels corresponding to the leaves of the metric space. This can be especially useful if the tree has long branches and few leaves. Additionally, for metric spaces, the minimum locus cover (Definition 4.5) is also an identifying locus cover (Definition 4.6). This follows from the construction of the weights in the proof of Theorem (shown in the Appendix) and the property that all paths in trees are unique. Finally, we note that any locus in any tree is pairwise decomposable- proof of this is given in the Appendix (Lemma A.3) We will see later that this property yields an efficient algorithm for computing the locus.
Phylogenetic Trees only the leaves are actual classes, and internal nodes designated as superclasses expeells include the ImageNet [6] and CIFAR- 100 datasets 20) Tree graphs in which only the leaf nodes are labeled are referred to as phylogenetic trees [3] Often, these graphs are weighted, but unless otherwise mentioned, we assume that the graph is unweighted.
Image classification datasets often have hicrarchical tree structure, where
For any arbitrary tree T (V,E), the set of labels induced by phylogenetic tree graph is y Leaves(T). We provide a heuristic algorithm for obtaining locus covers for arbitrary phylogenetic trees in Algorithm B. (see Appendix). We prioritize adding endpoints of long paths to A, and continue adding nodes in this way until (TAA) y. Similarly to tree metric spaces, any phylogenetic tree metric space is pairwise decomposable. We prove the conrectness of Algorithm B.I and pairwise

---

decomposability of phylogenetic trees in the Appendix (Theorem A.6 and Lemma A.7p Later, we give algorithms for computing the set of nodes in an arbitrary locus arbitrary graphs if the locus is pairwise decomposable, the algorithm for doing so is efficient, and if not, it has time complexity exponential K. Due to the pairwise decomposability of phylogenetic trees, this polynomial-time algorithm to compute (A) applies.
Grid Graphs Classes often have a spatial relationship. For example, classification on maps or the discretization of a manifold both have spatial relationships grid graphs are well suited to these types of spatial relationships. We obtain minimum locus covers for grid graphs satisfying Definition [4.5] but we find that these are not generally identifying locus covers. On the other hand, we give an example of a simple identifying locus cover satisfying Definition 4.6] Again, we find that grid graphs are in general pairwise decomposable and hence follow Definition 4.7
We find that the pair of vertices on furthest opposite corners yields the minimum locus cover. While the set of vertices given by Theorem A.8 (found in the Appendix) satisfies Definition 4.5 this set does not in general satisfy Definition 4.6 This is because the path between any two vertices is not unique, so each minimum path of the same length between the pair of vertices can have an equivalent minimizer. On contrast, the following example set of vertices satisfies Definition 6.6. but it clearly does not satisfy Definition 4.5 Example: Given a grid graph, the set of all corners is an identifying locus cover. On the other hand, the vertices given by Theorem A.8 can be useful for other purposes. Lemma[A.) (provided in the Appendix) shows that subspaces of grid graphs can be formed by the loci of pairs of vertices in A. This turn helps to show that loci in grid graphs are pairwise decomposable in general (see Lemma A.10 in the Appendix).
The Complete Graph The standard classification setting does not use relational information between classes. As before, we model this setting using the complete graph, and we show the expected result that in the absence of useful relational information, LOKI cannot help, and the problem once again becomes standard multiclass classification among observed classes. To do so, we show that there is no nontrivial locus cover for the complete graph (Theorem A. in the Appendix).
4.3 Label Subspaces in Practice
While it is desirable for the set of observed classes to form a minimum or identifying locus cover, it often not possible to choose the initial set of observed classes a priori-these are often random. In this section, we describe the more realistic cases in which a random set of classes are observed and an active learning- based strategy to choose the next observed class. The aim of our active learning approach is. instead of randomly selecting the next observed class, to actively select the next class so as to maximize the total size of the locus-i.e.. the number of possible classes that can be output using LOKI. Before maximizing the locus via active learning, we must first address a much more basic question: can we even efficiently compute the locus?
Computing the Locus We provide algorithms for obtaining the set of all classes in the locus, given set of classes A. We show that when the locus is pairwise decomposable (Definition (.7). we can compute the locus efficiently using polynomial time algorithm. When the locus is not pairwise decomposable, we provide general algorithm that has time complexity exponential in W are not aware of a more efficient algorithm. We note that any locus for every type of graph that we consider in Section 4.2 is pairwise decomposable, so our polynomial time algorithm applies. Algorithms B.2 and B.3 along with their time complexity analyses can be found in the Appendix.
Large Locus via Active Next-Class Selection We now turn actively selecting the next class to observe in order to maximize the size of the locus. For this analysis, we focus on the active learning setting when the class structure is tree graph, as tree graphs are generic enough apply to wide variety of cases- includding approximating other graphs using the minimum spanning tree, Assume the initial set of K observed classes are sampled at random from some distribution. We would like to actively select the K + 1st class such that [[{) with A = { K-1 is as large as possible.
Theorem 4.8. Let T = (J), E) be a tree graph and let A C y with K- = [A]. Let T be the subgraph of the locus I[)). The vertex EY that maximizes [I[ U {o}) is the solution to the following optimization problem: arg max d(y, b) s.t. be T' and T(y b) (b) S y [(A). where T' is the inner boundary T' (all vertices in I' that share edge with vertices not in T
7

---

Table CIFAR-100. Improving CLIP predictions using LOKI. Results are reported as Eid (y, 9) in the respective metric space. CLIP-like zero-shot models can be improved using LOKI even without access to an external metric, and internal class embedding distances are used. When an external metric is available, LOKI outperforms CLIP using the default CIFAR-100 hierarchy and WordNet.
Model
Metric Space
arg max
LOKI
Relative Improvement
CLIP-RN50
32
Internal Internal
0.2922
0.2613
10.57
CLIP-ViT-L-14
32
0.1588
0.1562
1.63% %
ALIGN 16
Internal
0. 0.1475
0.1430
3.02% %
CLIP-RN50
32
1100 0.5941*
0.5941
0.0%
CLIP-RN50
32
Default tree
7.3528
7.1888
2.23% %
CLIP-RN50
32
WordNet tree
24.3017
19.5549
19.53% %
methods equivalent under the complete graph as LOKI reduces arg max prediction.
This procedure can be computed in polynomial time-solving the optimization problem in Theo- rem 4.8 simply requires searching over pairs vertices. Hence we have provided an efficient active leaming-based strategy to maximize the size of the locus for trees.
Experimental Results
In this section, we provide experimental results validate the following claims:
1. LOKI improves performance of zero-shot foundation models even with no external metric.
LOKI adapts label spaces with large number of unobserved classes.
3. The active approach given in Theorem 4.8 yields larger locus than the passive baseline.
The same active approach yields better performance on ImageNet.
5.
With LOKI, calibration can improve accuracy, even with external metric.
5.1 LOKI Improves Zero-Shot Models
We evaluate the capability of LOKI to improve upon zero-shot models where all classes are observed.
Setup Our experiment compares the zero-shot prediction performance of CLIP 32 on CIFAR- 100 220 to CLIP logits used with LOKI. First, we consider the setting in which no external metric relating the labels available, and instead derive internal metric information from Euclidean distances between text embeddings from the models using their respective text encoders. Second, we consider three external metric spaces for use with LOKI: the complete graph K 100 and two phylogenetic trees: the default CIFAR- 100 superclasses 20 and WordNet
Results The results of this experiment are given in Table I When no external metric information is available, LOKI still outperforms CLIP-like models that use the standard prediction rule-in other words, LOKI seems to unconditionally improve CLIP. As expected, under the complete graph, our method becomes equivalent to the standard prediction mechanism used by CLIP. On the other hand, LOKI outperforms CLIP when using the default CIFAR- tree hierarchy and even more so when using the WordNet geometry, with a 19.539 53% relative improvement in mean squared distance over the CLIP baseline. We postulate that the strong performance using WordNet is due to the richer geometric structure compared to that of the default CIFAR-100 hierarchy.
5.2 LOKI on Partially-Obsera Label Spaces
To validate approach on partially observed label spaces, evaluate the performance of adapting a logistic classifier trained on SimCLR embeddings of ImageNet (6) 5-NN models trained on a 9,419 class subset of the PubMed dataset and the 32660l6sss LSHTC dataset 30)

---

Class sampling under unitorm distribution on
Active next class selection
100
100
50
80
Locuz Size
K
60-
Class sampling under Gibbs distribution
150
SimCLa
50-
20
200
400
600
800
1000
selections
Active mext-class selection ImageNNet using SLR Loki
FaPPor 900
86
SimCult (pasicee) SimCLR LaM lacthre)
500
540
550
Figure 2: (Top left) ImageNet. Mean squared distances under uniform class sampling and under the Gibbs distribution LOKI improves upon the baseline SimCLR one me-sss-est classifier. (Top right) Synthetic. Active class selection consistently leads to larger loci compared to uniform sampling. (Bottom) Active selection on ImageNet. Active class selection improves performance on ImageNet.
Table 2: PubMed. LOKI improves baseline for all settings of K. The metric space is Euclidean distances applied to SimCSE embeddings.
Setup For ImageNet, we use the WordNet phylogenetic tree as the metric space 22 this setting, we sample random subsets of size K of the 1000 ImageNet classes and compare a baseline one-vs-rest classifier to the same classifier but us- ing LOKI to adapt predictions to classes beyond the original K. We conduct two sets of experiments. In the first, we sample K classes uniformly, while in the second, a more realistic sampler- wee sample from a Gibbs distribution: P() 2 exp(-td(AAA9)) where X my(1N) is the centroid of the metric space. 0 is the concentration parameter around the centroid, and Z is the normalizer. While the Gibbs distribution sampler is more realistic, it is also the more chal- lenging classes which have low probability according to this distribution are less likely to appear in the locus. For PubMed, derive our metric from Euclidean distances be- tween SimCSE class embeddings [.. Finally for LSHTC, we summarize the default graph by randomly selecting nodes and merging them with their neighbors until we obtain graph with 10,000 supernodes representing sets of classes.
K
5-NN
5-NN + LOKT
adopt
100
1,68666
1,42591
250
1.52374
1.47801
500
1.64074
1.45921
Table 3: LSHTC. LOKI improves
baseline for all settings of K. We summarize the metric space graph by generating 10,000 supernodes.
K
5-NN
5-NN LOKI
50
1.2519
0.2896
100
1.4476
0.3467
150
1.7225
0.3969
200
1.7092
0.3171
Results Figure2]showe the mean squared distances compared
250
1 1.6465
0.3995
to the baseline one-vs-rest classifiers, across various settings
300
1. 1.6465
0.4004
of K. We find that LOKI always significantly outperforms
the baseline, even in the more challenging setting of sampling
according to Gibbs distribution. Tables 2 andd] show our improvements when using LOkI over the
baseline 5-NN models. While LOKI consistently yields an improvement on PubMed and LSHTC, the improvement more dramatic on LSHTC
5.3 Large Loci via Active Learning
We evaluate active next class selection approach on increasing the locus size. We expect that compared to passive (random) selection, our active approach will lead to larger loci, and in practice, larger of possible classes that can be predicted using LOKI while observing fewer classes during training.
Setup compare with a baseline that randomly selects the next class. We first generate synthetic random tree with size N and fix initial K. In active selection, we use the approach described in Theorem to select the next node, As a passive baseline, we randomly sample (without replacement) the remaining nodes that are not in A.

---

ECE
erfor tradeoff
3.05
0.024
CUP selaut
Loc optrnal
-..00
0.70
Softmak temperatii
0.010
0.68
06-
Argmax prediction CLIP default
0.008
24
0.004
03
Lod spamma
11.0
0.60
644 1.0
5.24 0.10 0.13
3.16
0.26
0,20
0.29
Figure 3: CLIP on CIFAR-100 with no external metric. (Left) Reliability diagrams across range of Softmax temperatures. highlighting the CLIP default temperature. the optimal temperature for LOKI, and the minimizer of the Expected Calibration Error (ECE). All three are well-calibrated. (Center) Tradcoff between optimizing for ECE and the expected squared distance. As with the reliability diagrams, the CLIP default temperature, the LOKI-optimal temperature, and the ECE- optimal temperature are similar. (Right) Tradeoff between optimizing for zero-one error and the expected squared distance. Temperature can be tuned to improve accuracy when using LOKI.
We set N = 100 and the initial K = 3, then we average the result over independent trials. The active approach consistently outperforms the random baseline as it attains a larger locus with fewer nodes selected.
Results
The results are shown in Figure 2
5.4 Improving Performance via Active Learning
Next, we evaluate the our active next class selection approach on improving error on ImageNet. While we found that the the active approach indeed leads to an increased locus size compared to the passive baseline, we expect that this increased locus size will lead to improved performance.
Setup We randomly sample 500 ImageNet classes, and using the WordNet metric space, we use our active approach to iteratively sample more classes. We compare this to a passive baseline in which the 50 classes are sampled randomly. We repeat this experiment over 10 independent trials.
Results Figure 2 shows that our active approach yields improved error over the passive baseline. The gap between the active approach and the passive baseline widens with more selection rounds.
5.5 Improving Accuracy via Calibration
Finally, we evaluate the effect of calibrating the Softmax outputs on the performance of LOKI.
Setup We calibrate via Softmax temperature scaling 13]
using CLIP on CIFAR-100 100. We do not use an external metric space, and instead use Euclidean distance applied the CLIP text encoder.
The reliability diagram in Figure 3 shows that the optimal Softmax temperature for LOKI both close the default temperature used by CLIP and the sptimally-calibrate temperature. In Figure 3 (right), we find that appropriate tuning of the temperature parameter can lead to improved accuracy with CL/P, even when external metric space available.
Results
6 Conclusion
In this work, we proposed LOKI a simple adaptor for pretrained models to enable the prediction of additional classes that are unobserved during training by using metric space information. We comprehensively answered the space of new questions that arise under LOKI terms of learning, optimal metric space settings, and a practical active selection strategy. Experimentally, we showed that LOKT can be used to improve CLIP even without external metrie space information, can be used to predict large number of unobserved classes, and validation of our active selection strategy.
10

---

Acknowledgements
We are grateful for the support of the NSF under CCF2106707 (Program Synthesis for Weak Supervision) and the Wisconsin Alumni Research Foundation (WARF).
References
[1] Gökhan Bakir, Thomas Hofmann, Bernhard Schölkopf, Alexander J. Smola, Ben Taskar, and S.V.N Vishwanathan. Predicting Structured Data. The MIT Press, July 2007.
[2] Björ Barz and Joachim Denzler. Hierarchy-based image embeddings for semantic image retrieval. In 2019 IEEE Winter Conference on Applications of Computer Vision (WACV), pages 638 647, IEEE, 2019.
[3] Louis J. Billera, Susan P. Holmes, and Karen Vogtmann. Geometry of the space of phylogenetic trees. Advances in Applied Mathematics, 27(4):733-767, 2001.
[4] Yeshwanth Cherapanamjeri, Nicolas Flammarion, and Peter L. Bartlett. Fast mean estimation with sub-gausee gaussian rates. In Alina Beygelzimer and Daniel Hsu, editors, Proceedings of the Thirly-Second Conference on Learning Theory, volume 99 of Proceedings of Machine Learning Research, pages 786-806. PMLR, 25-28 Jun 2019.
[5] Carlo Ciliberto, Lorenzo Rosasco, and Alessandro Rudi. A consistent regularization approach for structured prediction. In Advances Neural Information Processing Systems 30 (NIPS 2016), volume 30, 2016.
[6] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large- scale hierarchical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pages 248-255, 2009.
[7] Ali Farhadi. Ian Endres, Derek Hoiem, and David Forsyth. Describing objects by their attributes. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 1778-1785, 2009.
[8] Maurice R. Fréchet. Les éléments aléatoires de nature quelconque dans un espace distancié. Annales de I' l'institut Henri Poincaré, 1948.
[9] Andrea Frome, Greg S Corrado, Jon Shlens, Samy Bengio, Jeff Dean, Marc' Aurelio Ranzato, and Tomas Mikolov. Devise: A deep visual-semantic embedding model. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[10] Junyu Gao, Tianzhu Zhang, and Changsheng Xu. I Know the Relationships: Zero-Shot Action Recognition via Two-Stream Graph Convolutional Networks and Knowledge Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01)88003-331, July 2019.
[11] Tianyu Gao, Xingcheng Yao, and Danqi Chen. SimCSE: Simple contrastive learning of sentence embeddings. In Empirical Methods in Natural Language Processing (EMNLP), 2021.
[12] Colin Graber and Alexander Schwing. Graph structured prediction energy networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-But E. Fox, and R. Garett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[13] Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1321-1330. PMLR, 06-11 Aug 2017.
[14] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. 20/6 IEEE Conference on Computer Vision and Puttern Recognition (CVPR), pages 770-778, 2016.
11

---

[15] Daniel Hsu and Sivan Sabato. Loss minimization and parameter estimation with heavy tails. Journal of Machine Learning Research, 17(18):1-40 2016.
[16] Chao Jia, Yinfei Yang. Ye Xia, Yi-Ting Chen, Zarana Parekh, Hieu Pham, Quoc Le, fun-Hsuan Sung, Zhen Li, and Tom Duerig. Scaling up visual and vision-language representation learning with noisy text supervision. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1904-4916. PMLR, 18-24 Jul 2021.
[17] Michael C. Kampffmeyer, Yinbo Chen, Xiaodan Liang, Hao Wang, Yujia Zhang, and Eric P. Xing. Rethinking knowledge graph propagation for zero-shot learning. 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 11479- 11488, 2018.
[18] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
[19] Anna Korba, Alexandre Garcia, and Florence d'Alché-Buc. A structured prediction approach for label ranking. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
R.
[20] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers 2009.
of features from tiny images.
[21] Volodymyr Kuleshov and Percy Liang. Calibrated structured prediction. C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
[22] Christoph H. Lampert, Hannes Nickisch, and Stefan Harmeling. Learning to detect unseen object classes by between-class attribute transfer. In 2009 IEEE Conference on Computer Vision and Puttern Recognition, pages 951-958, 2009.
[23] Christoph H. Lampert, Hannes Nickisch, and Stefan Harmeling. Attribute-based classification for zero-shot visual object categorization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(3):453-465, 2014.
[24] M. Lerasle and R. I. Oliveira. Robust empirical mean estimators, 2011.
[25] Juan Li, Ruoxu Wang, Ningyu Zhang, Wen Zhang, Fan Yang, and Huajun Chen. Logic- guided semantic representation learning for zero-shot relation classification. In Proceedings of the 28th International Conference on Computational Linguisties, pages 2967-2978, Barcelona, Spain (Online), December 2020. International Committee on Computational Linguistics.
[26) Aaron Lou, Isay Katsman, Qingxuan Jiang, Serge Belongie, Ser-Nam Lim, and Christopher De Sa. Differentiating through the fréchet mean. In Proceedings of the 37th International Conference on Machine Learning, pages 5393-6403, 2020.
[27] Stanislav Minsker. Geometric median and robust estimation in Banach spaces. Bernoulli, 21(4):2308 2335, 2015.
[28] Mohammad Norouzi, Tomas Mikolov, Samy Bengio, Yoram Singer, Jonathon Shlens, Andrea Frome, Greg Corrado, and Jeffrey Dean. Zero-shot learning by convex combination of semantic embeddings. In Yoshua Bengio and Yann LeCun, editors, ICLR, 2014.
[29] Tom M W Nye, Xiaoxian Tang, Grady Weyenberg, and Ruriko Yoshida. Principal component analysis and the locus of the fréchet mean the space of phylogenetic trees. Biometrika, 104(4):901-922, Dec 2017.
[30] Ioannis Partalas, Aris Kosmopoulos, Nicolas Baskiotis, Thierry Artières, Georgios Paliouras, Éric Gaussier, Ion Androutsopoulos, Massih-Reza Amini, and Patrick Gallinari. Lshte: A benchmark for large-scale text classification. ArXiv, abs/1553.008811 2015.
[31] Alexander Petersen and Hans-Georg Muller. Fréchet regression for random objects with cuclidean predictors. The Annals of Statistics, 2016.
12

---

[32] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International Conference on Machine Learning. pages 1748-87633 PMIR, 2021.
[33] Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge into embeddings for relation extraction. In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, pages 1119-1129, Denver, Colorado, May-June 2015, Association for Computational Linguistics.
[34] Abhinaba Roy, Deepanway Ghosal, Erik Cambria, Navonil Majumder, Rada Mihalcea, and Soujanya Poria. Improving Zero-Shot Learning Baselines with Commonsense Knowledge. Cognitive Computation, 14(6):2212-2222, November 2022.
[35] Alessandro Rudi, Carlo Ciliberto, GianMaria Marconi, and Lorenzo Rosasco. Manifold structured prediction. In Advances in Neural Information Processing Systems (NeurIPS 2018), volume 32, 2018.
[36] Alessandro Rudi, Carlo Ciliberto, GianMaria Marconi, and Lorenzo Rosasco. Manifold structured prediction. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
[37] Changho Shin, Winfred Li, Harit Vishwakarma, Nicholas Carl Roberts, and Frederic Sala. Universalizing weak supervision. In International Conference Learning Representations, 2022.
[38] Richard Socher, Milind Ganjoo, Christopher D Manning, and Andrew Ng. Zero-shot learning through cross modal transfer. C.J. Burges, Bottou, M. Welling, Ghahramani, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
[39] Russell Stewart and Stefano Ermon. Label-free supervision of neural networks with physics and domain knowledge. In Thirty-First AAAI Conference Artificial Intelligence, 2017.
[40] Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Com- pressed Sensing, 2010.
[41] Harit Vishwakarma and Frederic Sala. Lifting weak supervision to structured prediction. In Alice H. Oh, Alckh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[42] X. Wang, Y. Ye, and A. Gupta. Zero-shot recognition via semantic embeddings and knowledge graphs. In 2018 IEEF/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 6857-6866, Los Alamitos, CA, USA, jun 2018. 9.8. IEEE Computer Society.
13

---

The appendix is organized as follows: in Appendix A we provide proofs of the claims made in the main text. Next, in Appendix B we provide algorithms and time complexity analyses for the algorithms referenced in the main text. Appendix [ Appendix [ we provide additional details about our experimental setup. Then in Appendix [E] we discuss the broader impacts and limitations of LOKI. Finally, in Appendix we provide more details and examples of the locus visualizations shown Figure
contains additional experimental results. In
A Deferred Proofs
A.1 Proof of Theorem 4.1 (LOKI sample complexity)
In this section, we provide a formal statement and proof our sample complexity result for LOkI, including additional required definitions and assumptions.
First, we define the required tools to prove the sample complexity bound for LOkI. For the purposes of this proof, we define the Fréchet variance as the function over which the Fréchet mean returns the minimizer.
Definition A.1 (Fréchet variance). The Fréchet variance is defined
V (V)==
Σ KE[K]
wid2(V, (V, Vi).
Additionally, will require technical assumption related the sensitivity of the Fréchet variance to different node choices.
Assumption A.2 (Fréchet variance is 1 -ii--iischhtz). For a metric space defined by a graph G' (V,E), the Fréchet variance is K K-bi-Lipschitzz if there exists K such that
de (V, V) < w (V) - V VVI < K&(VVV) K
for all V, V. E V. and fixed w E A K-1 For our purposes, such K always exists: consider setting K diam(G) maxy, vvvv [ (Vi) V w (V2) However, this is a very conservative bound that holds for all graphs that we consider. Instead, we assume access to the largest K S 1 such that
ad ad (V. < (W)(V) - v (V)),
which may be problem dependent.
Theorem A.3 (LOKI sample complexity). Let y be of points the d dimensional 2-norm ball of radius R, and let A C y be the set of K observed classes. Assume that A forms 2R//VdK' (VdK 1)- net under the Euclidean distance. Assume that training examples are generated by drawing n samples from the following process: draw x NN, T) where y > Unif(A), and at test time, draw x ~ NNy I) where y ~ Uni Assume that we estimate a Gaussian mixture model with K components (each having identity covariance) on the training set and obtain probability estimates Py ()) for i [K] for sample (x, u-) from the test distribution. Then with high probability, under the following model,
arg min G. mA (A((PLM
Σ P(ylz)ddP Vi)
yEY KE[R]
the sample complexity of estimating target y. from the test distribution Dien with prediction ÿ. is:
log K/5
B(e.u.)-DD..dd ].]] 0
Va.
RR-
log R
H
where d is the dimensionality of the input and a is our parameter under Assumption A.2
Proof. We begin by detailing the data-generating process.
At training time, underlying data-generating process, D is as follows:
14

---

28 We begin with vak -1 -net, J/ on the d dimensional 2-norm ball of radius R under the Euclidean distance, and let A S y
Draw y Unif())
Discard draws if y & A.
Draw x ~ Ny.
At test time, we do not discard draws and allow for classes not in A and use the following data generating process, Dies:
We begin with vák net, V, on the d dimensional 2-norm ball of radius R under the Euclidean distance, and let C.y
Draw y Uni.())).
Draw x N(y. I).
Given a labeled training dataset D = { y:) containing points drawn from Duain with |A| K distinct classes, we would like fit K- K-component Gaussian mixture model with identity covariance. We first perform mean estimation of each of the classes separately using the median-of means estimator
[ 27 24 Using the estimator yields the following parameter estimation bound
27 4
(V dllog K/8
11:: - V:ll2 S
with probability 1 1-
Next, we consider the relationships between four quantities: Vr(y.), Mp(ū.), Vz(y.). Vp(ū.), where P is the vector of probabilities from the true Gaussian mixture, IP is the vector of probabilities from the estimated model, y/- ma (PP is the target class, and ÿ. ma (P) is the predicted class. While is problen-dependent as to whether Vz(U=) < Wp(ū.) or Up(y)) Vp(ū.). ), similar argument holds for both cases. So without loss generality, we assume that Fp(g)) S (g=)). Then by the definition of the Fréchet mean, the following inequalities hold:
Vy(N~ & (p()))= S Up(y-),
and consequently,
Vz (y-) S Vp(y.) Vr((.).
We proceed by obtaining upper and lower bounds of the existing bounds in Equation 2 First, we will obtain upper bound V=(()) (F(U.).
Vp(y-) v=(u-)]
Σ KE[K]
PP P)d Vs)
Σ (P(w)lz) F())(=)) 11v. vill2
KE[K]
P( ((())
P()ly)))(P)) 11..
Σ
vill3
EjEKK] P(rlu))P(())
Eje(K) F(aly)))(())
[E[K]
(3)
15

---

exp( 1 0il12) *
EjE(K]] exp ||00 83 11))
[E[K]
expl 1 ||100 Wal 1il131
11y. 1ill2
Σ EjE(K] exp( 2 31100 13l13t
exp( - 21100 - 0e1133
Σ JE[K] exp( 2 12 18)
[E|K]
expl - || wil
11y+ - 3/112
Σj{[K] exp -11100
-
For notational convenience, we define the following:
a, == e || 1112))
à. == expl || 1x112).
b Σ _jE[K] exp( -11o0= -)112)-
b ΣjE(K] exp( --21iz 23
and
C. == 1|0. - villa
Then becomes:
Σ KE|K]
à; ai
G
b
iE|K]
04
04
1
à
b
KE
à
aj
Σ
a
1
b
KE|K]
KE
aj
0
à
b
0;
1
4
+
b
b
C2
K
K
ai L ) (5)
02
à
a
Σ KE|K]
1
C
+
b
b
KE|K]
KE|K]
Now we define the following: L = || 11 with = E arg min, || y, the smallest distance
to class mean, and L + E, := || yil 12 with E, > 0. Similarly, define i := || 12 with
z E arg miny ||0 وツ 2 is the smallest distance an estimated class mean, and L E, =- 1| ū:
with É. 0. Finally, we define :=
: v
VL - E, VL VL+E.
Then we can bound the parts separately:
For * we have
exp( 1 || vell3
0: b
Σ [E][K] exp( _// My 123
exp( - (T. F2)}
expl
[1] expl {[ + E,)}
1
(6)
exp( F.)
and in the case of i = 2, we bound 4 < 1. So overall, we have 4/ S exp(1 E.}
for all i e [K].
16

---

G: = ll.. villé
S 21 - 3:112 + 2| x - 3-
2(L + E, + || yー 1
0,
exp
|
9il12
=11z - 0:112 1
+
||2
3ill2
|| 0e112
2
2
(0s
V/.
2x
8/ 0.)
(8)
1b0 will ||2r y/8 Mill
1 3/l
ll (1|
3/2 + ||: 0z 11)
1 yall
(| 3/ + ||ar
+ y1 3ill)
S VI yall (2| will + 119/ 5zll)
l will (2 L E, + 11 8ell)
(9)
Next, we must control E. Eg in order to obtain the bound for 4.s
F E (||=r || I) (1 0=11 i.)
I yıl 2| || xxll2 + ||x 12 2 || y/ 1
(0) ya. 2x - y: (.) + (ye G.. 2x 0: Us)
11:: yall |2x y1 àsll + 11y- 2=1l ||rx 92 y= I1
< 1 8all (1|= 8:ll + || -will + | - 32ll [1| U= + || - Gell)
log K/8
(1|x - 9:ll + || - 3ell + || - 321l + ||0 2z11)
T
log K/8
(Vi+ / VL VL+E,
ev
(
dlog K/6
È. 2 max
0, O, - V
Using 6 we obtain
à
1
exp 1 11/2 Faa]
(10)
cxp 1
1ize max
0, E.
cT. V
dlog K/8
2
Plugging 6 7 9
and 10 into 5 we obtain
Σ
à
+
Σ iE[K]
ag
à
Σ
cs
ic(K]
(E(K]
17

---

110 yell (2VL L + E, 1186 8:ll)
2(L + Es + 1|x vz1
exp( 1 2
KE[K]
11is will (2V I. + Fg 11 0sll)
exp( 11/2 2x)
[E[K]
2(T. + P.j ||
y- V-112)
Σ (E|K] exp
11 max
0, 00 Fi
CT
dog K/6
2
dlog K/8
Fg + || ya113
0
exp
1 1 Fss
{E|K]
Next, recalling the fact that our class means form an e-net on the radius- ball, we use Lemma 5.2 from [40] to bound I. as I. S 28
Vak-1
dlog K/8
R Vak
+ Ei + | 1o11
0
(II)
exp
(1zz
RE[R]
Next, we will consider cases on E, We will consider the cases which E, < log H2 and E, 2 log Rt.
We will begin with the case in which E, log R?, then Equation 11 becomes:
dlog K/8
R
0o
+
|| v-112 11
vdk
|E[K]
Next, the case in which E, 2 log R2, then Equation becomes:
log K/8
R
+ 2 2log R + ||x - 1011
Jak
00
R
xE[K]
dog K/8
0
Σ
+ +|1
v-112
vdk
KE[K]
Setting M < K to be the number of terms for which E, < log R² holds and by combining the two bounds, we obtain the following:
0o
dlo K/8
MR
K-M M
+ KK| v.113 )
Vak +
Vak
n
Ultimately, our bound is
(v dlog K/8 (
((
(MR
MR K M
+ K|| - 2-113) =
(=((=)) V vr(y+)] 50
Vdk +
(12)
Vak
n
Next, will obtain lower bound on Up((.) (e(()))
(0-) - ==(x+) 2 Me(ue) v=(0+) - (M,))).) - (P())))
triangle incquality
> and (-) - Vp(v.) Vr(y-))
Assumption A.2
18

---

Combining both of these bounds with Equation 2 we obtain
ad (y,, U-) (p(())) WF((-)] - V2(D-) (e(y)) - vp(y.) We(y.)
(Vp(N=) MP((+))
= ad Un) S 2 2/Vp(v,) - vr((a))
+ (v 50 50
d log K/6
VdK +
MR K-M M
+ K|| - (1l1))v11))
Vak
n
dlog K/6
MR
K- M
dk) dk))
= B.... (yo. (ya, (ya, U.)l s
a
Vdk
vdK
7
Next, obtain bound on M. Since M K is the number of terms for which E, log R have that M VK, where V E [0, 1] is the ratio of the volumes of the ball for which Eg < log R?, and the ball containing the entire set of classes y. We have
E = || yill2
|| v=1 < log R²
|| 3:l1 log R²² + L
2R
S log R² + vdK - S R²
2R
log R
S R
VdK -
which is an upper bound the radius of the ball for which F, < log R2 is true. Now we construct V:
log R2 +
2R
VdK 1
V
Combining this with our error bound, we have ((a.y.)>D... [d (y.. 0.)] S
Vlog 12+
y fug 112
vJk
R
1
vIX
1 d log K/8
It
O
+ dK
α
Vd
Vd
However, we can choose K to weaken our dependence on R.
v 1l0g
R²
2R
d
Vdk
V =
<
R
R
2
K 2
+1.
Vd
122 - 3
log
Finally, we have
d log K/8
Vd
)
Be 50
+
R
+
+ dl
a
Vd
vd
R
log
1t
log K/8
1
vd
< 0
+ dl
n
Vd
RR1-3
RR.
3
log ft
log K/8
0
+ Vd
71
[R-- 3
log
19

---

which completes the proof.
Discussion of Theorem A.3 The above bound contains several standard quantities, including the dimensionality of the inputs d, the radius Ht of the ball from which labels are drawn, the number of classes and samples used estimate the model and respectively, and which is used to control the probability that the bound holds. Naturally, the bound scales up with higher d and K, and improves with an increased number of samples n. The dependence on R is also related to its dependence on d - so long as we have that K' 2 2 (Vd(RR-
log R/ R)) + and for d 2 R increases, which improves the bound. The bound includes metric space dependent quantity which is related to the amount that the Fréchet variance can change subject to changes in its argument, i.e. which node is considered.
A.2 Proof of Theorem A.4 (minimum locus cover for trees)
Theorem A.4 (Minimum locus cover for trees). The minimum locus cover for tree graph T is = Leaves(T)
Proof. We would like show show two things:
any node can be resolved by an appropriate construction of w using only the leaves and
2. removing any leaf makes that leaf node unreachable, no matter what the other nodes are in y-i.c., we must use at least all of the leaf nodes.
If both of these conditions hold (i.e., that the leaves form locus cover and that they are the smallest such set), then the the leaves of any tree form minimum locus cover. To set up the problem, we begin with some undirected tree, T, whose nodes are set of labels: T (Y,, E) where A = (ccaves(T) S y is the set of leaf nodes. Moreover, let A be tuple of the leaf nodes. We will start by proving that A is locus cover. We will show this by cases on E V, the node that we would like to resolve:
1. If v E A, i.e is leaf node, then setting w; = 1(A, 2 yields
K
arg min mA (w)
Σ
1(A;
ofd
yey
==1
arg min d (v, [c]
yEy
2. If & A, we have bit more work to do. Since e is an internal node, consider any pair of leaves, 1, * lo such that is along the (unique) path between I and l2: E 124,22.. Then
d(v.fa) if A₁ l1,
set wn 30,
d(m.)) if A; = lz.
yields
0 otherwise
d(v, (1,12)d (v. 41) + d(c, (1.d()122))
mA ma(w)= arg min yEY
d(11,12)
= arg min d(v, (2, d(u, dd (g,
vEY
= fo}.
Thus A is locus cover. Next, we will show that is the smallest such set. Let ( A be any leaf node, and define A' = AA? \ {t}. We must show that A' is not locus cover. Assume for contradiction that A' is locus cover. This means that given some tuple y whose entries are the elements of A', we have IIAA) = y. This implies that the path between any two nodes in A is also contained in II(A', Since the leaves form a locus cover and any y E ) can be constructed by the appropriate choice of w along with path between two leaf nodes, 1 must either be one of the entries of A' (one of the endpoints of the path) or it must be an internal node. Both cases are contradictions-AN A' cannot include
I by assumption, and is assumed to be leaf node. It follows that A is minimum locus cover. D
20

---

A.3 Proof of Lemma A.5 (tree pairwise decomposability)
Lemma A.5 (Tree pairwise decomposabilityy, Lei T (),8) be a free and V. Then II(A) is pairwise decomposable.
Proof. Assume for contradiction that Hy" E Wheree M Then, y" E mA (w) for some w. Note that y" $ II( )33) implies y Ay)) Vi 2, A. because [ X₃1) = [(s, X;) due to the uniqueness of paths in trees. As such, (y", must contain an immediate relative of where
E I(A).
I Σ
w (,)
Σ
wi(d(y', +
[A wid (y/ Ax).
Therefore, y" & (A) because y" not minimizer of Σ |A| y" E (((Ai);))) for some X; A E A when II(A).
wid (y,, As). So, it must be that
A.4 Proof of Theorem A.6 (Algorithm B.I correctness)
Theorem A.6 (Algorithm B. correctness). Algorithm
B.1 returns locus cover for phylogenetic
trees.
Proof. We first prove that Algorithm B. will halt, then according the stopping criterion, it is guaranteed that Algorithm B. returns a locus cover. Suppose the algorithm keeps running until it reaches the case in which all the leaf nodes are included A (i.e. A Y), this results in the trivial locus cover of the phylogenetic tree and the algorithm halts.
A.5 Proof of Lemma A.7 (phylogenetic tree pairwise decomposability)
Lemma A.7 (Phylogenetic tree pairwise decomposability). Let TT' = (V,E) be tree with y Leaves(T) and A C Then II(A) pairwise decomposable.
Proof. Suppose reach contradiction that Ey* E Y where y" II(A), but II(A,, AY, Xj E A. In other words, y" is a Fréchet mean for some weighting on A, but y" not a Fréchet mean for any weighting for any two vertices within A.
For arbitrary di, >y E A, define the closest vertex to y" on the path between A and X, as
o' dA())))))= arg min d(y", v).
vET(A,Ay)
Also, let
(A1, 22) = arg min d(y", v ('; 27)),
X.AyEA
the pair of vertices in A whose path П(А A2) passes closest to y". To avoid notational clutter, define o'(A1,)2) Thus, o' represents the closest vertex to y² lying on the path between any two X5, A.
Because o' lies on the path I(A1, A2), there exists some weighting w for which
o' = arg min (widZ(u, A1) + wyd (v, A2)). vET(And22)
For this w, we have that A2) (w) arg min d(y, v²), the set of leaf nodes of smallest distance from o'. By the initial assumption that y" & II( A A2t), we have that y" & ({ (w). Let y be vertex of m(.d,)) (w) that is closest to y.. Clearly, d(y', "ig'.v') e²)² d' v2)2.
21

---

For any E V, respectively define the sets of vertices (1) shared in common on the two paths [(2,, y²) and [e, y²), (2) on the path [' y²) that are not on [(v, y²). and (3) on the path ['v y²) that are not on [v, v² as
dc(v) ((,, (T(r,))),
(v)(v) T(,, \ T(v,y'), and
(v)(v) I(u. \uu,,"
We have that [dy-(v) (v)] - |d (w)|+ + 1 | v/) (the difference by 1 represents the final vertex shared in common by both paths) and also that (dy (v')) < (dy (1') since y' is closer v' than y" is.
Suppose 3Y3 d E A yielding
v' o' d's,, (
such that dy" u') S (f/ u²).
This is to say that u' is defined analogously to v', with the additional restrictions that u' lie on the path l'(y", 1/' and u' be least close to y" to y'. Then, (dy (u')l < Id (v') implying (' w() d² (y" ,u'), which contradicts the definition v'.
Suppose now that 3A3 A4 E A yielding
='= (Aa, & I(y". such that d' "y"",u s &d))d(s (s'.
This is to say that is again defined analogously to v'. but u/ is not on r(y".y/) and is at least as close to y to y'. Then, either (xe # 0 (i.e. all lambdas lie in the same branch off of Tyy. D. in which case the path between any two lambdas will have the same closest node v' to y it is possible to choose Às A such that dc(As) n dc(As) = G. In this situation, it must be that [()s, As) (T y²) * 0, which implies there exists a vertex t E T(A3, As) such that ('y"", (t) <
(v": ud) which violates the definition of u'
Altogether, for all a E T(A;,A)) with arbitrary Ai, A E A, we have that d'(y' < dF , v). This implies that for all A, there exists a E y such that d2 A) < dB "(y",", A) and therefore that V" & IT(A) which contradicts that y" (T(A). It must be that Vy" E E where y² E [AA,, we have y" E [T((;,, 22)) VA, X3 A.
A.6 Proof of Theorem A.8 (minimum locus cover for grid graphs)
Theorem A.8 (Minimum locus cover for the grid graphs). The minimum locus cover for a grid graph the pair of vertices in the furthest opposite corners.
Proof. We would like to show two things:
1. any vertex can be resolved by construction of u using the furthest pair of two vertices (i.e. opposite corners) and
2. there does not exist locus cover of size one for grid graphs with more than one vertex.
Let G (V, be a grid graph and A {Ai, }2} be set of two vertices who are on opposite corners of G (i.e., perhipheral vertices achieving the diameter of G). For notational convenience, set = (A1, 22) We can reach any interior vertex by an appropriate setting the weight vector d(v.)2) d(v,A1)
w [wi, W2]. Then set w d(Ar.d))' d(Ar)da) ). Finally, the Fréchet mean is given by
d(v, (2 (v. A1) + d(v, A )d (v. A2)
mA(w) arg min yEy
d(>1, X2)
= arg min d(v, 12) (g. A1) + d(u, Ar (y. d2)
wEY
3 U.
Hence A is a locus cover. We can clearly see that A is a minimum locus cover the only way to obtain a smaller set A' is for it to include only a single vertex. However, A' [v'] contains only a single vertex, it cannot be a locus cover so long as G contains more than one vertex-o' is always guaranteed be a unique minimizer of the Fréchet mean under A' which misses all other vertices in G. Thus A is minimum locus cover.
22

---

A.7 Proof of Lemma A.9 (loci of grid subspaces)
Lemma A.9 (Locus of grid subspaces), Given any pair of vertices in A, we can find a subset G' of the original grid graph G (V,E) which takes the given pair as two corner. (I(A) equals all the points inside G'.
Proof.
The result follows from application of Theorem A.8 to the choice of metric subspace.
A.8 Proof of Lemma A.10 (grid pairwise decomposability)
Lemma A.10 (Grid pairwise decomposability). Ler G E) be grid graph and A C. Then I1(A) pairwise decomposable.
Proof. Suppose we have a grid graph G = (J), E) and a vertex ÿ E (T(A) with A C V. Due to the fact that ý E (A) and the fact that G is grid graph, have that 1 E I(Aa; for some Aa, AB E A. Then by Lemma A.I0
1 II( Aa)) S UA
Therefore loci on grid graphs are pairwise decomposable.
A.9 Proof of Theorem A.11 (no nontrivial locus covers for complete graphs)
Theorem A.11 (Trivial locus cover for the complete graph). There no non-trivial locus cover for the complete graph.
Proof. We show that there is nontrivial locus cover for complete graphs by showing that removing any vertex from the trivial locus cover renders that vertex unreachable. We proceed by strong induction on the number of vertices, n. Base case We first set n = 3. Let K₃ (V, v2) be the complete graph with three vertices: V -fe, 12, U3 ) and without loss of generality, let A {u2, U/ be our set of observed classes.
There are two cases on the weight vector w = [w02, wa]:
Case I: Suppose
& intA². This means that either W2 or wa 1-which leads to the Fréchet mean being either U2 or U3, respectively. Neither of these instances correspond to being a minimizer.
Case 2: Suppose w E 2 Then the Fréchet mean is given by
mx(w) arg min w2d (y, U2) + wzdd (y, U3)
yEY
Assume for contradiction that ei [[A)):
(21((11)22) + wzd 03)
W22 u1
W3
because w E int
=2d (12, v2) + wzd vz).
Therefore, 01 & II(A). This a contradiction. Thus there is no nontrivial locus cover for K3.
Inductive step: Let Kn-1 (V, v2) be the complete graph with - vertices. Assume that there no nontrivial locus cover for Kn We will show that there no nontrivial locus cover for corresponding to vertices U1,..., U E V with {Vi,..,, 1n-1). ). We want to show that on g (IA)). We proceed by cases on w.
Kn- Let the weight vector be w [......
Case I: Suppose
& n-2 where entries of u zero, then by strong induction we know "amm,.i. i.e. there no nontrivial locus cover for K Kn-m:
that v, @ (T(A)= = (2; } 1n-m
Case 2: Suppose w intA
23

---

Assume for contradiction that en E [I)... Using this assumption, we obtain the following
n-1
w (Un: 11)
because w int.""2 n-2
Σ wid (vn-1,
Therefore, Un a minimizer, Un $ II(A). This a contradiction, hence K,, has no nontrivial
locus cover.
A.10 Proof of Theorem 4.8 (active next-class selection for trees)
Proof. We will prove the result by showing that the two optimization problems are equivalent. Let e be solution to the following optimization problem:
arg max E y ITAA)
d(y.
s.t.
E OmT
r(b. 3) {b) E (
where 7' is the inner boundary of T", the subgraph of whose vertices are IT(A). This optimization problem can be equivalently rewritten as
arg
[Tv,
y E y' (IA)
s.t.
E Om T(b. v) (b) C ()
and furthermore introduce additional terms that do not change the maximizer
arg max ) (T() s.t.
|UXAAEEA T(),,Ay) (T(b y)l
be Om
[ v) \ (b) ((A).
Equivalently, we can also connect to one of the elements A
arg max y )/ ITAA) s.t.
|UXIAJEA I(A, 24) UT(A, 8) ubbb,)))
be 8'T" r(b v) \ (b} (TA)
Due to the uniqueness of paths in trees, this optimization problem also has the following equivalent form without any dependence on b:
arg max UALAAEEA T(Ai, A2) LUTTT T(),, y) arg max UAAAAEA (TT vEVAA
sEYiA
arg max UALAJEAUUM I[({,,);)) VEY'A
arg max [TT U (3))
VEyAA
using Lemma A.5
Therefore is a maximizer of [I[(A U [u})], required.

---

B Algorithms and Time Complexity Analyses
We provide time complexity analyses for Algorithms B.1
B.2 and B.3
B.1 Analysis of Algorithm B.1 (locus cover for phylogenetic trees)
We provide Algorithm B.I with comments corresponding the time complexity of each step.
Algorithm Locus cover for phylogenetic trees
Require: phylogenetic tree T (V,8). Leaves(T)
N + |/
P (TThylenggh((((/ww)))))))
N|E + N2 N > O(N2)
P reverse
A + (f
for (ys. yÚ) in do
O(N2) O(K2D max N2 log N))
if (T(A) y then
return A
else
+ AU 13.
end if
end for
Combining these, we obtain the following time complexity: O(N(E++N' log N=N2 max max log NJ) O(N3 max log N)).
B.2 Analysis of Algorithm B.2
(computing a pairwise decomposable locus)
We first provide Algorithm B.2 here, with comments corresponding to the time complexity of each step.
Algorithm 2 Computing pairwise decomposable locus
Require: A. G = (V,8)
II 0
D + diam(G. for Ar Ay E A do
> O(NIE) + 2 log N)
O(K2) DO(D)
for w1 in {
D D: do
W1, W1
I1 3 (w0)
& O(N[E) + N2 N2 N)
end for end for return
We first compute the diameter of the graph G = (V,E) with N = 13% which is done in O(NJE + 22 log N) time using Dijkstra's algorithm to compute the shortest paths between all pairs of vertices. We then iterate over all pairs of elements in A with K = |A], which amounts to O(K2) iterations. Within this, we perform O(D) computations of the Fréchet mean, for which each iteration requires ((N + l N) arithmetic operations or comparisons. Combining these, the final time complexity is
[(N 2 log + K2D(NEE) + 2
log N)) +2
2(K2 N1), log N)).
B.3 Analysis of Algorithm B.3 (computing generic locus)
We provide Algorithm B.3 with comments corresponding to the time complexity each step.
Following a similar argument from the analysis of Algorithm B.2 the time complexity is (N + + log N + * (N + 2 log N)) O(D*),
25

---

Algorithm 3 Computing a generic locus
Require: A, G (V,8)
II + 0
D - diam(G) (G)
O(N)E) + N2 log N))
for in
(D: D DJ
D |||
do
D D((K)
I IT ITU (mm))
OONNE N2
end for return
6.225
05
sokul: UMd eptoral
tradeoff
66028
0.04
044
CUP sebult
0.12
0.8-
0.
0..33
0.549
0.596
0.010
611
0.032
0.395
0.028
64
0.06
CLP soluE
speres
01
7:20
7.20
7.25
7.30
Expeccod aquared dislacc
Balenity
ECE Loki pert.
ECE estrra
error tradeoff
05
6.4
0,014
6.-
6,012
6.75
0.00
Argmax
0,008
02
0.538
6.70
0,006
ICE cctme
operr
0.005
0.65
0.004
0,002
Porfect
0.00
Confdince
Expected squared distance
Figure 4: CLIP CIFAR-100 with the WordNet hierarchy. (Lefft) Reliability diagrams across range of Softmax temperatures, highlighting the CLJP default temperature, the optimal temperature for LOKI, and the minimizer the Expected Calibration Error (ECE), All three are well-calibrated. (Center) Tradcoff between optimizing for ECE and the expected squared distance. As with the reliability diagrams, the CLIP default temperature, the LOKI-optimal temperature, and the ECE- optimal temperature are similar. (Right) Tradeoff between optimizing for zero-one error and the expected squared distance. Depending on the metric space, temperature scaling can improve accuracy.
where K is the number of observed classes.
C Additional Experiments
C.1 Additional calibration experiments
In the main text, we evaluated the effect of calibrating the Softmax outputs on the performance of LOKI using a metric space based on the internal features of the CLIP model. Here, we perform the same analysis using two external metric spaces.
Setup
We perform our calibration analysis using the default and WordNet tree.
Our results are shown in Figure Like our experiment using an internally-derived metric, we find that the optimal Softmax temperature is close to the CLIP default and the optimal temperature for calibration. For the default tree, we again found that temperature scaling can be used to improve accuracy using LOKI.
Results
Setup We calibrate via Softmax temperature scaling I3 using CLIP on CIFAR-100. We do not external metric space, and instead use Euclidean distance applied to the CLIP text encoder.
26

---

Results The reliability diagram in Figure shows that the optimal Softmax temperature for LOKI both close the default temperature used by CLIP and the optimally- temperature. In Figure 3 (right), we find that appropriate tuning of the temperature parameter can lead to improved accuracy with CLIP, even when no external metric space available.
C.2 Ablation of LOKT formulation
LOKI is based on the Fréchet mean, which is defined as arg min Et= PAileeP (y, X.). However, this is not the only approach that can be considered. For example, the Fréchet median, often used in robust statistics, defined as arg min yEy ΣK PA Py As), without squaring the distances. More generally, we define arg miy Di=1 P PA (y, A,) and evaluate different choices of B.
Setup We conduct this experiment on ImageNet using SimCLR as our pretrained classifier with K" 250, 500, and 750 randomly selected classes.
Results From this analysis, we conclude that using the Fréchet mean is the optimal formulation for Loki, as achieved the lowest mean squared distance for all settings of K.
Table Expected squared distances of SimCLR+Loki alternatives on ImageNet. We ablate over the
choice of distance exponent in LOKI (where / = 2, corresponding to the Fréchet mean), including
the Fréchet median (3 1). That is, tune 3 arg minyey Eie P
px df A₂) and find that
the optimal setting is 3 = 2, corresponding to LOKI.
B
K = 250
K = 500
K = 750
0.5
61.28
46.57
36.31
52.98
41.06
33.14
(Loki)
46.78
37.76
29.88
47.99
39.58
34.65
65.29
58.42
54.90
C,3
Comparison across metric spaces
Expected squared distances cannot be directly compared across metric spaces, as they may be on different scales. Our solution to form of normalization: distance by the square of the graph diameter. This brings all of the values to the ()1 range, and since E[d ú)) /ddiamm)) indeed also generalizes the 0-1 error, this enables comparison between O)- errors and those from different metric spaces. We provide these results in Table 1, again for our CLIP experiments on CIFAR- 100. This evaluation metric enables have geometry best 'fit' to our pretrained models.
divide the expected squared
determine which metric spaces
Setup Using Efd ()/ddimm(G)))) we re-evaluate our CLIP results on CIFAR-100 shown in Table for the ResNet-50 architecture.
Results For CIFAR- 100, we observe that the WordNet metric space resulted in the lowest error and therefore has the best geometry.
Table 5: Comparison across metric spaces for CLIP on CIFAR-100 by normalizing by the squared diameter of the metric space: EEd (g. 0)] [[]/diam(()))
Metric space G
diam G)2
Eld /oll/dimmGy
Complete graph
0.5941 (0-1 error)
Default tree
16
0.4493
WordNet tree
169
0.1157
CLIP features
0.9726
0.2686
27

---

D Experimental Details
In this section, we provide additional details about our experimental setup
D.1 CLIP experiments
All experiments are carried out using CLIP frozen weights. There are no training and hyperparameterrs involved in experiments involving CLIP, except for the Softmax temperature in the calibration analysis. We evaluted using the default CIFAR- 100 test set. The label prompt we use is "a photo of a cclas_nnamed
D.2 ImageNet experiments
To construct our datasets, we randomly sample 50 images for each class from ImageNet as our training dataset then the validation dataset in ImageNet to evaluate LOKI'S performance. We extract the image embeddings by using SimCLRv 1 and train a baseline one-vs-rest classifier. We WordNet phylogenetic tree the metric space. The structure of phylogenetic tree can be found at here We test different numbers of observed classes, K, from 1000 classes. Observed classes are sampled in two ways, uniformly and Gibbs distribution with the concentration parameter 0.5.
D.3 LSHTC experiments
We generate summary graph of the LSHTC class graph (resulting in supernodes representing many classes) by iteratively:
1. randomly selecting a node or supernode
2. merging its neighbors into the node to create a supernode
until the graph contains at most 10,000 supernodes. In the LSHTC dataset, each datapoint is assigned to multiple classes. We push each class to its supernode, then apply majority vote to determine the final class. We test different numbers of observed classes, K, from 10,000 classes. We collect datapoints which are in the observed classes. Then split half of dataset as training dataset and make the rest as testing dataset, including those datapoints which are not in the observed classes. We train a baseline classifier using a 5-NN model and compare its performance with LOKI.
E Broader Impacts and Limitations
As simple adaptor of existing classifiers, it is possible for method inherit biases and failure modes that might be present existing pretrained models. On the other hand, the possibility of harmful miscclassifications the metric space used by LOKI. Finally, while we have found that LOKI often works well in practice, it is possible for the per-class probabilities that are output by pretrained model to be sufficiently mis-specified relative to the metric over the label space, or for the metric itself to be mis- mis-specified. Nonetheless, we have found that off-the- the-thelff or self-derived metric spaces to work well in practice.
known a priori, information mitigate these harms can be baked into
F Random Locus Visualizations
and we provide visualizations of classification regions of the probability simplex when using LOKI with only three observed classes out of 100 total classes, and different types of random metric spaces. The first example in Figure shows the prediction regions on the probability simplex when using standard arg max prediction the three regions correspond to predicting of the three classes (0, 39, and 99) and regions corresponding to any of the other classes {I, 38, 40, ..., 98). We compute these regions using a version of Algorithm B.3 and while
In Figures 5 6
Codee implementing all of our experiments is available here: http::///gtauu..cco/bbbrccttttll 'Embeddings are extracted from checkpoints stored at: attp::///gituub.com//ooyyy//
simclr- conlertco
28

---

it does have exponential time complexity, the exponent is only three in this case since we consider only three observed classes.
On the other hand, the other three examples in Figure and Figures 5 prediction regions the probability simplex when using LOKT. Figure 5 shows this for random tree graphs. Here, the prediction regions are striped or contain single triangle-shaped region in the center-these correspond, respectively, to intermediate classes along branches of the leading up from the observed class and the prediction region formed by the common-most parent node. Figure 6 shows similar regions, although these are more complex and are thus more difficult to interpret, phylogenetic trees are metric subspaces equipped with the induced metric from trees. Furthermore, in order generate phylogenetic trees with 100 leaves, we needed to create much larger trees than the ones used for Figure 5 which led to narrower prediction regions due to the higher graph diameter. Finally, Figures 7 and
and all show the
9 each show the prediction regions using LOKI when the metric space is random graph produced using -atts-Strogatz, Erdós-Rényi, and Barabási-Alber models respectively. These prediction regions are more complex and represent complex relationships between the classes.
Crach
Then Sarieh
Teer Oueeh
Drree
Dlve
Thbe
Cruzh
Thee Stann
Tre Deep
Tree Ouep
Tee Duphh
Trx OupP
Tox Oruon
Tox Oraon
Tre Ctudh
Figure 5: Classification regions in the probability simplex of 3-class classifiers faced with 100-class problem where the classes are related by random trees graphs.
Fhee Geea!
Pil. Tiee Great
Pryso Traa Grigs
Fryds Stoel
Fayk: Creas
Thylo Drips
Fryts
Park Tep moooe
Mark Doaen
Mayy: toan
Pryik
Myyi tee
Wilhi 1100
Rryos T100 Dergg
Pryls Ieaa Sarggh
Figure 6: Classification regions in the probability simplex 3-class classifiers faced with a 100-class problem where the classes are related by random phylogenetic trees graphs.
29

---

'Small Rerid
Small Bodd Crach
Small World Grea
Ses Wode Greel
Mari Wold Cree
Omaal Wirdd Grop!
Small Gropl
Smell wede Grach
"Sac Work Neree
Sena
Para
'mnit Crash
Smndl Work Crach
'maal Werkd Crea
Seeal Wert Grazil
7Smal World Cruph
SmaalWWre Geup!
Smaa Gupl
SSeil Wode Grafi
Stark Drean
Work Srrek
World Freen
Swar WO Dhege
Figure 7: Classification regions in the probability simplex of 3-class classifiers faced with 100-class problem where the classes are related by random small-world graphs generated by Watts- Saats--trrgazzz model.
31
13
30
P
Pa
Gast-aag Grazt 24
"Soto koryy Grea"
usl Adrpy Grepk
"o Ronyl Grup
Mosz Appy Seea?
12 Keryy Grup?
"Ento Kitty Srap
Nay
Tery Sreak
Fony Ovech
Tewy Stesh
Rerye Grech
Reryl Ovgr
Figure 8: Classification regions in the probability simplex 3-class classifiers faced with a 100-class problem where the classes are related by random Erdōs-Rént graphs.
30

---

Sereed ken Greakeo
Eerendal eben Greeklo
Edioole dbon Crepming
Birbber Abort Grewk
Doretle Libr Gradke
Geretan Moott--totCCo Cresse
Sorbelt Vant Craa
deobest Greak
Whase Abbe S
2 Caass Kpein ao
Waaii Kaain Srag
He Get
Eroteal Alen Greselo
Eeussoi Aber oo
Deusio Mban Ovar
Bonthar Mitl Shaee
Dertio Staet Cuar
Baeta Cuasen
Sacton Craa
Chas
d2 bet Clep
Figure 9: Classification regions in the probability simplex of 3-class classifiers faced with a 100-class problem where the classes are related by random Barabási-Aie Albert graphs.
31


Reviews:
[{"review_id": "Y2EG1ASEmt", "reviewer": "Reviewer_zgY7", "summary": "This paper introduces a method capable of adapting a pre-trained model to a larger label space. To achieve this, it leverages the information of geometric distances between labels within the target larger space and replaces the common argmax operation with the Frechet mean. The paper also includes several theoretical analyses on sample complexity and optimal label subspaces.\n\nBased on the proposed locus definition, the paper presents an active learning paradigm with the objective of expanding the maximum label coverage by introducing new labels. The empirical results demonstrate that the proposed method outperforms the vanilla baseline method in tasks of zero-shot classification and partially-observed label spaces.", "questions": "As mentioned in the weakness section, here are few key questions left to answer:\n- How does Loki perform in terms of accuracy?\n- How does Loki perform compared to stronger baselines from recent literatures?\n- How does uncalibrated probability affect the final performance?\n- How useful is the proposed active learning in terms of final classification performance?", "limitations": "The authors have adequately discussed several limitations and negative societal impact in the appendix. ", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- the usage of Frechet mean is simple and intuitive for solving partial label classification tasks\n- the theoretical analyses are thorough and address several key questions in terms of sample complexity and optimal label subspace", "weaknesses": "- Evaluation Fairness: The empirical results from Table 1 and 2 are reported as $E[d^2(y, \\hat{y})]$ in the respective metric space that Loki is optimized for. It is not too surprising that Loki outperforms the argmax/one-vs-rest baseline trained without such information. The paper lacks more fair metrics like accuracy or a held-out metric space to demonstrate the overall effectiveness of Loki.\n- Stronger Baselines: Both zero-shot classification and partially-observed classification experiments only include vanilla baselines (e.g., CLIP argmax, SimCLR with one-vs-rest classifier). Considering the proposed method is pretty simple, the paper should compare against stronger baselines [1][2][3][4] in terms of performance and efficiency. Additionally, the claim that graph neural network architectures are heavyweight and challenging to scale up to extremely large graphs, where Loki performs better, needs quantitative measurements to support it (e.g., running efficiency, model size, etc.).\n- Uncalibrated Uncertainty in Loki Formulation: Often, the probability of outputs from classification is uncalibrated [5], and the paper lacks an ablation study examining how the correctness of uncertainty $P_{\\lambda}$ affects the final performance.\n- Effectiveness of Active Learning: While the final experiment indicates that the proposed active learning paradigm successfully leads to larger loci, there is no guarantee or proof on how well the paradigm affects the final performance in classification tasks.\n- Clarity: Section 4.2 is too wordy; consider emphasizing key statements and bringing several key algorithms from B.2, B.3 to the main text for better clarity.\n\n[1] X. Wang, Y. Ye, and A. Gupta. Zero-shot recognition via semantic embeddings and knowledge graphs. In 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 6857–6866, Los Alamitos, CA, USA, jun 2018. IEEE Computer Society.\n[2] Abhinaba Roy, Deepanway Ghosal, Erik Cambria, Navonil Majumder, Rada Mihalcea, and Soujanya Poria. Improving Zero-Shot Learning Baselines with Commonsense Knowledge. Cognitive Computation, 14(6):2212–2222, November 2022.\n[3] Christoph H. Lampert, Hannes Nickisch, and Stefan Harmeling. Learning to detect unseen object classes by between-class attribute transfer. In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 951–958, 2009.\n[4] Junyu Gao, Tianzhu Zhang, and Changsheng Xu. I Know the Relationships: Zero-Shot Action Recognition via Two-Stream Graph Convolutional Networks and Knowledge Graphs. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):8303–8311, July 2019.\n[5] Nixon, Jeremy, Michael W. Dusenberry, Linchuan Zhang, Ghassen Jerfel, and Dustin Tran. \"Measuring Calibration in Deep Learning.\" In CVPR workshops, vol. 2, no. 7. 2019.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the helpful comments, and for praising the simplicity of our method and the thoroughness of our theoretical analysis! \n\n**On evaluation fairness:**\n\nThis is an excellent point – we have added experimental results that address it in two ways. \n- First, in our new calibration results, we were excited to find that if the softmax temperature is tuned, **Loki can attain a better 0-1 loss than argmax prediction!** This result is illustrated in Figures 1 and 2 of our new results. \n- Second, we provide new results for our CLIP experiments that use a normalized version of our metric that allows us to **compare across metric spaces**: $\\mathbb{E}[d^2(y, \\hat{y})] / \\text{diam}(G)^2$. This metric allows us to compare across metric spaces by bringing all of the errors onto the same scale, and it also generalizes the 0-1 error when the complete graph is used, allowing us to compare against accuracy. See Table 1 in our new results. This new evaluation metric enables us to determine which metric spaces have geometry best ‘fit’ to our pretrained models. For example, for CIFAR-100, we observed that the WordNet metric space resulted in the lowest error and has the best geometry. \n\n**On baselines**\n\nOur work introduces a new problem setting: adapting a pretrained classifier to enable it to navigate a metric space, without any additional training. Note that **this setting is highly challenging due to the extreme paucity of resources** available for it: we do not get to train or fine-tune models, or, in most cases, observe any new data points, and sometimes cannot even access model internals such as embeddings. Existing approaches (including the suggested ones) require access to information not available in our scenario or require training a specialized model. In fact, _our motivation for developing Loki was our initial skepticism that class geometry alone was sufficient to improve pretrained models to any extent_. Fortunately, our empirical and theoretical results demonstrate that such improvements are often possible.\n\nThe papers suggested do not fit our setting for the following reasons:\n- The method proposed in [1] requires class embeddings, which are sufficient but not necessary to apply Loki, and it **requires training** whereas Loki does not. \n- The zero-shot method proposed in [2] **requires training** a graph convolutional autoencoder and is limited to classes in ConceptNet.\n- The method in [3] **requires attribute metadata**, which is different from our metric space assumption. \n- [4] also **requires training**. \n\nIn contrast to these existing methods, **Loki is a drop-in replacement for argmax prediction used in pretrained classifiers**. As far as we are aware, [1, 2, 3, 4] cannot operate in this setting. \n\n**However, we can evaluate alternatives to Loki** – Loki replaces the $\\text{arg max}$ with the Fréchet mean. We can use a different function instead of the Fréchet mean, e.g., the Fréchet median. As described in the common response, we compared four alternatives to Loki in our new experimental results (presented in Table 2) and found that Loki was optimal for minimizing the expected squared distance. \n\n**On graph neural network architectures being heavyweight**\n\nBy heavyweight, we mean that most other methods **require training, whereas ours does not**. Regarding the scaling to large graphs, we note that\n    \n- A forward pass using a graph convolutional network (GCN) [5] requires time complexity $O(|E|)$, where $|E|$ is the number of edges. \n- A forward pass using Loki requires time complexity $O(K|V|)$, and if the number of observed classes, $K$, using Loki is small $(K << |V|)$, then the time complexity is $O(|V|)$. \n\nFor problems where the graph is dense or when we only have access to pairwise distances in a finite metric space instead of a graph, the time complexity of using a GCN becomes $O(|E|) = O(|V|^2)$. This is a common setting that occurs, for example, when the metric space is derived from pretrained class-name embeddings. However in this setting, the time complexity of applying Loki is still $O(|V|)$ when $K$ is small. We conclude that the complexity of applying Loki is favorable in many graph settings. \n\n**On uncalibrated uncertainty**\n\nThis is also an excellent point, thank you for bringing this up! Since submission, we performed calibration via temperature scaling [6]. Excitingly, we found that calibration indeed led to improvements in our CLIP experiments, and that the optimal temperature for Loki was always close to the optimal temperature for calibration. We also found that adjusting the temperature allowed us to navigate a Pareto curve between optimizing for the 0-1 loss and for the expected squared distance, and in some cases we improved both. We are excited about these new insights, which can be found in Figures 1 and 2 of our new results. \n\n**On the effectiveness of active selection**\n\nThank you for bringing this up! We have included additional experimental results showing how our active strategy improves over a passive baseline both in terms of performance (expected squared distance) and expressivity (the size of the locus). This new result can be found in Figure 3 of our new experiments!.\n\n**On clarity**\n\nWe agree! We have updated the text to reflect this feedback. Thank you! \n\n[1] https://arxiv.org/abs/1803.08035 \n\n[2] https://arxiv.org/abs/2012.06236 \n\n[3] https://ieeexplore.ieee.org/document/5206594 \n\n[4] https://ojs.aaai.org/index.php/AAAI/article/view/4843\n\n[5] https://arxiv.org/abs/1609.02907 \n\n[6] https://arxiv.org/abs/1706.04599 "}, {"review_id": "ClrCZIyROu", "reviewer": "Reviewer_cqEn", "summary": "This paper considers the zero-shot model adaptation to testing tasks that include classes not seen during training. The authors propose a post-hoc method called LOKI, which applies a class-graph-based transformation to make predictions on these unseen classes. The authors also provide the theoretical analysis and experimental results to support the proposal.", "questions": "How can a reliable graph be obtained in real-world applications? The experiments implement it using hierarchical trees and WordNet. Does this limit the practical application of the proposal?\n\n\n--- \nThanks for the detailed clarifications, which have addressed my concerns. I would like to keep my score.", "limitations": "The authors do not provide a discussion about the limitations and potential negative societal impact.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The problem considered in this paper is significant in the machine learning community, and the proposed solution is technologically reasonable.  \nThe theoretical results are interesting and provide a solid justification for the proposed solution.   \nThe paper is well-written and easy to follow.", "weaknesses": "The graph of LOKI seems heavily rely on the prior knowledge of the classes. \nIn the Sections 5.1 and 5.2 of this paper, experiments were conducted on CIFAR100 and ImageNet, respectively. Are there any additional results on other datasets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and for noting the significance of the problem considered in our work! We have clarified points about our experimental results and the metric spaces that we use below. \n\n**On prior knowledge of the classes**\n\nMetrics relating the classes are often readily available, but **even when they are not, our method still works**. Our experimental results in Section 5 include two such examples:\n- In Table 1, the “Internal” metric space refers to using class embeddings from the pretrained CLIP model itself, and\n- In Table 2, the metric space for our PubMed results is derived from SimCSE embeddings. \n\nIn both of these cases, Loki improves over the baseline, which confirms that prior knowledge of the classes is not required.\n\n**On experimental results beyond CIFAR-100 and ImageNet**\n\nYes, our submission contains experiments on PubMed and the LSHTC datasets, please see Tables 2 and 3 in our submission. Both **datasets contain substantially more classes than CIFAR-100 and ImageNet (ILSVRC 2012)**, with PubMed containing almost 10,000 classes and LSHTC containing 325,000 classes. We chose these datasets in order to have diversity both in terms of the data domain and the size and structure of the metric space. \n\n**On obtaining metric spaces in the real world**\n\nGreat question! Our experiments include graphs from a variety of sources that are **not limited to hierarchies.** For example, our PubMed and CIFAR-100 experiments include metrics that were derived from models where we naively applied the Euclidean distance to off-the-shelf embeddings and internal representations of the class names. The resulting metric spaces are not hierarchical. Obtaining these graphs simply required applying a standard procedure rather than needing any specialized domain knowledge. This procedure can be followed in any setting where embeddings are available.\n\nA natural question to ask is whether different approaches to obtaining graphs lead to similar results. Excitingly, in our CIFAR-100 experiments, **we show that Loki can lead to improved performance across three different metric spaces for the same problem,** suggesting that Loki is robust to changes in the metric space. "}, {"review_id": "DeCONO6RSN", "reviewer": "Reviewer_4Uud", "summary": "The authors consider the problem of predicting examples from unseen but \"known\" classes. Taking inspiration from structured prediction, the paper intends to exploit the knowledge of structure in the full label space. The authors propose an alternative to the popular \"argmax-over-logits\" prediction, called Loki, by computing the Frechet mean with an appropriate distance metric in label space. A theoretical result on a simple logistic data model shows the sample complexity bound with Loki. Also considered is the important question of what training labels are necessary and sufficient to be able to span the whole label space during prediction. On the experimental effectiveness, the authors demonstrate reasonable percentage point improvement over baseline \"argmax\" standard prediction.", "questions": "Questions:\n1. Line 210: \"In cases involving an extremely large number of classes, it is desirable to use LOKI on the smallest 211 possible set of observed classes\" - is this because sample complexity of in Theorem 1 scales as K^2? Are there other considerations?\n2. I would prefer to get more explanation for the proposed use-case of grid graphs. While phylogenetic trees is more intuitive, grid graphs might benefit from a simple examples\n3. Does a counterpart of Theorem 4.8 hold for grid graphs?\n4. Sec 5.2: Is one-vs-rest the most competitive baseline?\n5. For the result on computing loci for partially oserved label spaces, are PubMed and LSHTC the standard datasets to consider? Please provide any reasoning behind this choice. Any references will be useful\n6. Fig 1 (and related ones in Appendix)- it is not immediately clear what the authors intend to demonstrate here.\n7. I am curious about the impact of Loki on calibration. ", "limitations": "Limitations:\nI did not see an explicit discussion on the limitations and scope for improvement", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Strengths:\n1. My knowledge in structured prediction is limited. However, it seems to me that the results in this paper are significant and interesting\n2. I found the method Loki to be a neat approach to predicting unseen classes, when the distance metric for th label space is known. It is a scalable method since the computation involved is a fixed linear transformation\n3. The authors have stated and and given proofs for the minimal locus cover for two non-trivial label space structures with clear motivation - phylogenetic trees and grid graphs\n4. An algorithm of a \"greedy\" nature through an active-learning framework is then given, which is polynomial time. \n5. Experimental results: it seems that Loki achieves strong results for CLIP\n6. While I have not checked the proofs in detail, the methodology appears sound and rigorous.\n", "weaknesses": "Weaknesses:\n1. It is not clear to me if there can be guarantees provided when the true label space metric is not available or only approximately known\n2. Theorem 1 is for the case of logistic regression. It is not clear whether this is a powerful enough model for practice. \n3. I have either missed this part or there needs to be a detailed discussion of the implications of Theorem 1\n4. I suggest providing \"error bars\" or significance level for the numbers reported in Table 1\n5. More experimental details would be helpful for reproducing the results \n6. It is unclear to me if there are other competitive structured prediction techniques applied to pretrained models and what gains Loki makes over them, if any.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful review and for **noting the significance, theoretical contributions, and scalability of our work!** \n\n**On the true label space metric vs. approximations**\n\nExcellent question! We find that there is not a single “correct” metric space for a given problem, and that many approximations can be made without significantly impacting performance (e.g. deriving a metric from pretrained class embeddings, graph summarization, or minimum spanning tree approximations). We hypothesize that this phenomenon is due to the presence of redundancy within many of the objects commonly used in ML (representations, graph structures, etc.). This redundancy enables a variety of potentially distinct metric spaces to contain enough geometric information to be successfully used by Loki. \n\n\n\n\n\n**On logistic regression in practice**\n\nNote that this logistic regression result (LR) holds in practice for a variant of our SimCLR experiments, which involves applying it to self-supervised feature embeddings. While simple, this result applies to the broad range of modern self-supervised learning techniques that use logistic regression as part of the learning pipeline. We believe that the result can also be extended beyond LR to richer distributions and model classes, but the machinery involved in such an analysis becomes more complex **without shedding additional light on the fundamental tradeoffs.** For example, we could perform a similar analysis for two-layer neural networks, but existing results, which must serve as a component in our result, are often unwieldy and only obscure the roles played by key quantities (e.g., the graph diameter). \n\n**On implications of Theorem 1**\n\nThank you for bringing this up – we added a detailed discussion of Theorem 1 in the updated draft. In short, we can bound individual errors in expected squared distance as a function of the squared diameter of the graph, the number of observed classes, the dimension of the features used to train the logistic classifier, the number of samples, and a problem-dependent constant. The squared errors relate to the squared diameter of the graph, as this is the maximum value that they can take on. The bound improves as we obtain more samples—as we would expect. Furthermore, since the bound has a quadratic dependence on K, we can also improve the bound if our classifier is trained on fewer classes. \n\n**On error bars and significance of Table 1**\n\nThe results of Table 1 are deterministic, as we cannot retrain CLIP over multiple seeds, although we will provide error bars for our other experiments in the final version. \n\n**On more experimental details and reproducibility**\n\nWe absolutely agree! We will include full experimental details and release code reproducing the results in the final version. \n\n**On other competitive structured prediction methods using pretrained models**\n\nWe are unaware of other structured prediction approaches that operate in our setting: adapting a pretrained classifier to enable the navigation of metric spaces without any additional training. **However, we evaluated alternatives to Loki**, such as the Fréchet median (see common response).\n\n**On applying Loki to the smallest number of observed classes.**\n\nThe reason for applying Loki to a small set of classes is twofold – practical usage (i.e., not needing to train a classifier on the entire, potentially large label space), and theoretically as a property of our bound, as you correctly pointed out. Consider the example of 2D grid graphs – in order to predict an arbitrarily large grid, we only need the four corners to form an identifying locus cover. In other words, we can predict an arbitrarily large number of classes using only a four-class classifier. \n\n\n**On real-world use-case of grid graphs**\n\nProblems in which classes represent points in space can be represented as grid graphs, e.g., predicting locations on a map, predicting the next move in a board game such as chess, and predicting atoms in a lattice where edges represent physical interactions [1]. \n\n**On Theorem 4.8 for grid graphs**\n\nFor bounded 2D rectangular grids, the result is trivial – over a constant four rounds of active selection, select the four corners. This leads to an identifying locus cover. If we relax the requirement that each node can be predicted uniquely, then this can be done in only two rounds of active selection by selecting opposite corners. This forms a minimal locus cover. We will include this example in the final version of the text. \n\n**On the one vs. rest baseline**\n\nWe used one vs. rest logistic regression for its simplicity, although a similar result can be obtained using multiclass logistic regression. Applying logistic regression to self-supervised embeddings is typical for self-supervised learning approaches. \n\n**On reasons to compute loci on partially observed label spaces such as PubMed and LSHTC**\n\nWe used these datasets because they 1. Have a large number of classes and 2. Either have a native metric space structure (LSHTC) or have class names where a metric space can be derived easily using pretrained class embeddings (PubMed). To our knowledge, there is no prior work on computing loci of label spaces in the machine learning literature from which we could have obtained datasets. \n\n**On the purpose of Figure 1**\n\nFig. 1 visualizes the locus of 100-node graphs when applying Loki to a 3-class classifier. For example, the leftmost simplex represents prediction using the argmax – in this case, there are three equally-sized regions corresponding to the Softmax outputs of the 3-class classifier. We will clarify this in the final version. \n\n**On calibration**\n\nThis is an excellent point! We have included a new analysis of the effect of calibration, as described in the common response. \n\n[1] https://arxiv.org/abs/2010.09990 \n\n[2] https://arxiv.org/abs/1706.04599 "}, {"review_id": "CwpNXw03Lz", "reviewer": "Reviewer_2m87", "summary": "This paper explores the concept of geometry-aware adaptation for label spaces. The paper introduces a method called \"LOKI\" that allows pretrained models to make predictions for classes that were not observed during training. LOKI utilizes metric space information to adapt the model's predictions to unobserved classes.\n\nThe paper discusses the theoretical foundations of LOKI, including the definition of loci and identifying locus covers in graphs. It presents algorithms for efficiently computing the locus and describes an active learning-based strategy to select the next class for observation in order to maximize the size of the locus.\n\nExperimental results demonstrate that LOKI improves the performance of zero-shot models even without external metric space information. It adapts to label spaces with a large number of unobserved classes and outperforms baseline models in terms of mean squared distances. The paper also validates the effectiveness of the active next class selection approach, showing that it leads to larger loci compared to random selection.\n\n\n\n\n\n\n", "questions": "1. While the paper briefly mentions the computational complexity of LOKI in term of label spaces, will time consumption of this method be also related with higher-dimensional metric spaces? When compared with original method without LOKI, how much is extra consumption of memory and runtime with LOKI? \n\n2. When multiple external metrics are provided, can we decide which metric is most suitable in advance?\n\n3. Is the property pairwise decomposable necessary for the improvement of LOKI? Does it only work on the dataset satisfying this property?", "limitations": "No potential negative societal impact of their work. Suggestions are provided in the weakness and questions.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. Originality: The paper exhibits a high degree of originality in several aspects. Firstly, it introduces the concept of geometry-aware adaptation for label spaces, which is a novel approach to address the challenge of predicting unobserved classes in pretrained models. The formulation of LOKl and its integration with metric space information is a unique contribution. Additionally, the paper presents novel definitions, algorithms, and strategies related to loci, identifying locus covers, and active learning-based class selection. These original contributions set the paper apart and make it a valuable addition to the field.\n\n2. Clarity: The paper excels in terms of clarity, making the research accessible to a wide range of readers. The authors provide clear explanations of concepts, definitions, and algorithms, ensuring that readers can understand the technical aspects of LOKI. The paper is well-structured, with logical flow and section organization. \n\n3. Quality: The paper demonstrates a high level of quality in terms of its theoretical foundations, experimental methodology, and presentation of results. The authors provide a thorough and rigorous analysis of the problem, offering formal definitions and proving relevant theorems. \n\n4. Significance: The paper holds significant importance in the field of machine learning and predictive modeling. It addresses a challenging problem of predicting unobserved classes in pretrained models, which has practical implications in various real-world scenarios. The introduction of LOKI and its ability to adapt predictions using metric space information expands the capabilities of pretrained models, enabling them to make more accurate predictions for classes that were not observed during training. The experimental results demonstrate the effectiveness of LOKI and its superiority over baseline models, further highlighting its significance in advancing the field.\n\n", "weaknesses": "1. Lack of Comparative Analysis: While the paper presents LOKI as a novel approach, it would benefit from a more comprehensive comparative analysis against existing methods or related works. Providing such a comparison would strengthen the paper's argument for the originality and effectiveness of LOKI.\n\n2. Scalability Analysis: The paper briefly mentions the computational complexity of LOKI, but a more detailed analysis of its scalability would be valuable. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review and for **noting the originality, clarity, quality, and significance of our work!** \n\n**On comparative analyses**\n\nWe are unaware of other approaches that operate in our setting: adapting a pretrained classifier to enable the navigation of metric spaces without any additional training. **However, we can evaluate alternatives to Loki** – Loki replaces the $\\text{arg max}$ with the Fréchet mean, such as the Fréchet median. We compared four alternatives to Loki in our new experimental results (see Table 2), and we found that Loki was optimal for minimizing the expected squared distance. \n\n**On scalability analyses and runtime**\n\nWe demonstrate that Loki can be scaled up to the ~325,000-class LSHTC dataset by using approximations such as graph summarization. We will provide a more thorough ablation of the scalability of Loki in the final version of the paper. \n\n\n**On choosing the best metric**\n\nThis is an important point! Typically, the answer would be to evaluate different metrics on a held-out validation set, but in this setting, the expected squared distance itself depends on the metric space. In order to make comparisons between metric spaces, we need the errors to be on the same scale. We provide new results that normalize all of the expected squared distances by the squared diameter of the metric space, bringing all of the errors onto the same 0-1 scale, and allows us to compare with other performance measures such as the 0-1 error. This enables tuning the choice of metric space as a hyperparameter – in the case of CLIP applied to CIFAR-100, we find that the WordNet tree is the optimal metric space of the ones that we evaluated. \n\n**On whether or not pairwise decomposability is necessary for Loki** \n\nPairwise decomposability is only needed for efficient computation of the active data selection strategy. Loki itself does not depend on this property – Loki can be applied using a linear transformation of the softmax probabilities regardless of the properties of the metric space or loci. "}, {"review_id": "BPL29h8vKy", "reviewer": "Reviewer_dZLD", "summary": "In this paper, the authors explore the adaptation of pretrained models from a geometric perspective. Specifically, this paper leverages the label information as a metric space and proposes a simple approach to predict new classes based on the pretrained models’ zero-shot prediction without any further training. This paper also provides some theoretical analysis w.r.t learning-theoretical results, locus cover and active next-class selection. In the empirical results, this paper conducts experiments on several datasets and verify the effectiveness of the proposed method.", "questions": "- As discussed in the Weaknesses, it is not clear whether the proposed LOKI is the optimal geometric adaptation method for enabling the prediction of unobserved classes. Are there any alternatives for Fréchet mean estimator to yielding more reliable predictions? (An example) It would benefit a lot if some empirical or theoretical comparison are added to demonstrate the effectiveness of the proposed LOKI.\n- I appreciate this paper that most claims are supported by theoretical results. It would further improve the paper if more empirical results were added to support these claims. For example, some toy experiments can be provided to verify Theorem 4.8.\n- In Table 1, the effectiveness of LOKI is explored on CIFAR-100. It would be more convincing to conduct experiments on more real-world datasets.\n- The experiments in Table 1 seems not comprehensive. From the results, we can see that LOKI presents limited improvements on ViT-L-14 backbone. It would be better to add more discussions and more comprehensive empirical results. \n", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "\n\n- The paper is generally well-written and easy to follow.\n- The topic of adaptation on the pretrained models from the geometric perspective is interesting.\n- The proposed method is simple and efficient.\n- The main claims are generally supported by theoretical results.\n\n\n\n", "weaknesses": "- The proposed method may require some additional information such as label relationship, which may not be applicable in some real-world situations.\n- It lacks theoretical analysis about the superiority of the proposed LOKI.\n- The empirical results are not adequate to support the main claims.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review! We have responded to your points below. \n\n**On the usage of the Fréchet mean estimator**\n\nWe made the choice to use the Fréchet mean because we have information about the relationships between classes. To ground our rationale in a different type of problem, consider a regression task: the output is a **scalar,** and it is possible to compare labels (e.g., one is larger than another, etc.). Labels can also be averaged, and indeed, the Bayes optimal linear predictor is just such an average—a mean. \n\nHowever, in our setting, we are in a far more general case than continuous spaces like $\\mathbb{R}$. In fact the only information we have access to is relationships between classes, which can be expressed as distances. So we need an analogue to the mean that operates using only distances, and the canonical analogue is the Fréchet mean. Indeed, it has beautiful theoretical [1] and optimization [2] properties. Other variations of the weighted Fréchet mean have been used in supervised learning in structured prediction settings [3], although since our problem does not permit training, we require a novel approach. \n\nHowever, it is not the only possible choice. For example, taking an exponent of 1 instead of 2 on the distance term produces the Fréchet median, which is known to have excellent robustness properties, but lacks some of the theoretical properties we rely on. Our framework is flexible—we could obtain a new version of Loki that uses such an object as well. **We include new experimental results that evaluate the effect of changing the exponent**; please see Table 2 in our new results. \n\n\n**On experiments to verify Theorem 4.8**\n\nWe agree and indeed our submission already includes exactly this! Figure 2 (right) is a synthetic experiment that shows how Theorem 4.8 can be used to optimally increase the size of the locus for tree graphs. In addition, since submission, we have included a new experiment that verifies Theorem 4.8 on ImageNet – a much more realistic setting. \n\n**On CIFAR-100 and more real world datasets** \n\nOur submission includes three real-world datasets in addition to CIFAR-100: ImageNet, PubMed, and LSHTC. While ImageNet (ILSVRC 2012) includes 1,000 classes, PubMed includes nearly 10,000, and LSHTC includes over 325,000 classes. \n\n**On limited improvements using the ViT-L-14 backbone**\n\nWe were excited to find that there are substantial gains to be had by applying Loki to a variety of pretrained models from different settings: supervised models, self-supervised models, and zero-shot models including CLIP and ALIGN. We hypothesize that even greater gains can be obtained for the ViT-L-14 CLIP backbone if we were to use a more refined approach for extracting the metric space or tune the softmax temperature. \n\n[1] https://arxiv.org/abs/1609.03045 \n\n[2] https://arxiv.org/abs/2003.00335 \n\n[3] https://arxiv.org/abs/1605.07588 "}]

Author rebuttal:
We thank all reviewers for their comments! We particularly appreciate reviewers **praising the significance of our work** (reviewers cqEn, 4Uud, and 2m87) and **praising the simplicity of our method** (reviewers zgY7 and dZLD). 

Given the novelty of our problem setting and approach, reviewers had several questions and suggestions for experimental improvements before recommending acceptance. 
These helpful comments have significantly improved the quality of our submission, and we respond to each of them individually below. **We are confident that our work offers an exciting and impactful new problem that invites future study and practical application, while introducing a strong baseline--Loki**. 

Before we proceed with these individual responses, we **highlight new results** added to the paper since submission, including several responding to reviewers’ questions and suggestions. These include a variety of exciting new experimental results that have significantly improved the paper: 

### New results

1. **New Calibration Analysis** (reviewers zgY7 and 4Uud). We perform this analysis on CIFAR-100 with the CLIP-ResNet-50 model. Calibration uses softmax temperature scaling [1]. Our results are shown in Figures 1 and 2 of our attached document. In Figure 1, we provide reliability diagrams and plots navigating the tradeoff between the expected calibration error (ECE). From these experiments, we **obtain the following new insights**: 
    - the optimal Softmax temperature for Loki is close to the optimal temperature for calibration,
    - tuning the temperature can lead to improvements in Loki’s performance, and
    - CLIP probabilities were already well-calibrated. 

    In Figure 2, we scale the softmax temperature to navigate the tradeoff curve between the 0-1 loss and the expected squared distance on which Loki is evaluated. **For two of the metric spaces, we find that temperature scaling can lead to higher accuracy using Loki,** and even when this is not the case, temperature scaling can be used to trade off between the two evaluation metrics. We appreciate the suggestion from the reviewers; this analysis revealed the softmax temperature as an important hyperparameter for improving the results from Loki. 

2. **Cross-Metric Space Comparison via a New Evaluation Metric** (reviewers zgY7 and 2m87). Expected squared distances cannot be directly compared across metric spaces, as they may be on different scales. Our solution is to use a form of normalization: we divide the expected squared distance by the square of the graph diameter. This brings all of the values to the 0-1 range, and since $\mathbb{E}[d^2(y, \hat{y})] / \text{diam}(G)^2$ indeed also generalizes the 0-1 error, this enables comparison between 0-1 errors and those from different metric spaces. We provide these results in Table 1, again for our CLIP experiments on CIFAR-100. This new evaluation metric enables us **to determine which metric spaces have geometry best 'fit' to our pretrained models**. For example, for CIFAR-100, we observed that the WordNet metric space resulted in the lowest error and has the best geometry. 

3. **Comparison of Loki Alternatives** (reviewers zgY7, 4Uud, and dZLD). Loki is based on the Fréchet mean, which is defined as $arg min_{y \in \mathcal{Y}} \sum_{i=1}^K P_{\lambda_i|x} d^2(y, \lambda_i)$. However, this is not the only approach that can be considered. For example, the Fréchet *median*, often used in robust statistics, is defined as $arg min_{y \in \mathcal{Y}} \sum_{i=1}^K P_{\lambda_i|x} d(y, \lambda_i)$, without squaring the distances. More generally, we can define $arg min_{y \in \mathcal{Y}} \sum_{i=1}^K P_{\lambda_i|x} d^\beta(y, \lambda_i)$, and evaluate different choices of $\beta$. We conduct this experiment on ImageNet using SimCLR as our pretrained classifier with 250, 500, and 750 randomly selected classes. From this analysis, we conclude that using the **Fréchet mean is the optimal formulation for Loki**. 

4. **Evaluation of Active Next-Class Selection Procedure on ImageNet** (reviewer zgY7). We had previously validated Theorem 4.8 in our submission using a toy example and showed that the size of the locus indeed increases optimally. In our new experiment, we validate that this optimal increase in locus size indeed results in improved performance over selection rounds. We do so on ImageNet (ILSVRC 2012) using SimCLR, beginning with 500 randomly sampled classes. Our passive baseline randomly selects a new class at each round, and our proposed approach actively selects the optimal next class at each round. Our results are shown in Figure 3. Over 50 selection rounds, we found that our active approach led to consistent and significant gains over the passive approach in expected squared distance. From this analysis, we have further evidence that our **active selection approach is effective for minimizing the expected squared distance over selection rounds**. 

Please let us know if we can answer any questions about these new results! We are excited to engage with you all during the discussion phase. 

[1] https://arxiv.org/abs/1706.04599 

Meta-review: There was consensus among the reviewers that this well-written paper tackles a challenging and relevant problem (ML model extrapolation to unseen classes), that the proposed solution is compelling and practical, and that the results sufficiently justify its feasibility. Some of the reviewers raised concerns about evaluation (additional baselines, fairness of comparison, etc), but the authors were able to convincingly address most of these in their thorough and thoughtful rebuttal. While no reviewer was particularly enthusiastic about this paper, it is nevertheless a correct, well-motivated, and exceptionally well-presented piece of work that introduced an algorithm that is likely to be useful for the broad ML community, which in my opinion justifies its acceptance into the conference.
Decision: Accept (poster)