OTTER: Effortless Label Distribution Adaptation of Zero-shot Models

We are grateful to the reviewer for noting the strengths of our work and providing useful comments. The reviewer appreciated our work, recognizing the novelty of our method, its solid theoretical foundation, and extensive empirical validation.

• On dependence on estimated label distribution: While our method requires estimated label distribution, the requirement for improvement is not heavy---the estimated distribution just needs to be better than zero-shot label distribubtion. Furthermore, label distribution estimation algorithms have been developed in other works (e.g. [1,2,3,4,5]). Any availble method can be plugged into OTTER. For example, we used BBSE [1] as a label distribution estimation method in linear probing setting.

• On more detailed analysis of performance across different types of datasets: We reported information about datasets in Appendix E.1 Table 6, which shows that experiments cover diverse datasets with respect to the number of data points, the number of classes and the imbalance level. Additionally, we provide further analysis illustrating the relationship between (n, K, Imbalance) and OTTER's performance gains in Figure 3 of the attached pdf. In summary, accuracy tends to increase as dataset size increases, the number of classes decreases, and imbalance level increases.

• On comparison with recent methods: Thank you for suggesting useful references. The suggested papers share commonalities in seeking to perform test-time adapation without any labeled data. [6] fine-tunes zero-shot models using pseudo-labels generated by text classifiers trained on LLM-generated text descriptions and class names. [7] uses CLIP scores as reward signals in reinforcement learning, facilitating task-specific fine-tuning of VLMs. [8] uses test-time prompt tuning with alignment loss to effectively align representations with pretraining data. While OTTER is indeed also a test-time alignment method, it offers a much more lightweight way to update predictions without any parameter updates, while [6, 7, 8] require additional training for some parts of models. Additionally, OTTER can be easily combined with [6, 7, 8], giving further improvement. We include a mini experiment with [6] in three datasets: Caltech101, DTD, OxfordFlowers.

OTTER is comparable to LaFTer (but, as we described, more lightweight) and provides further improvements when combined with LaFTer.

• On scalability: As mentioned in the common response, we reported computation time in Appendix E.3. Table 10. While it is true that our inference-time adaptation approach requires additional computation, the computational overhead is not heavy --- the linear programming version of OT can run with subqudratic computation comlexity. In practice, we observed our method gives modified predictions within 0.05 ms per sample---a negligible overhead Additionally, for massive-scale inference, batch optimal transport with parallel computing can be used. Figure 1 in the attached file shows the accuracy and computation time (per batch) depending on the batch size. Note that this result can be further improved with more advanced batch optimal transport methods.

[1] Saerens, Marco, Patrice Latinne, and Christine Decaestecker. "Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure." Neural computation 14.1 (2002): 21-41.

[2] Lipton, Zachary, Yu-Xiang Wang, and Alexander Smola. "Detecting and correcting for label shift with black box predictors." ICML'18.

[3] Azizzadenesheli, Kamyar, et al. "Regularized Learning for Domain Adaptation under Label Shifts." ICLR'18.

[4] Alexandari, Amr, Anshul Kundaje, and Avanti Shrikumar. "Maximum likelihood with bias-corrected calibration is hard-to-beat at label shift adaptation." ICML'20.

[5] Garg, Saurabh, et al. "A unified view of label shift estimation." NeurIPS'20.

[6] Mirza, Muhammad Jehanzeb, et al. "Lafter: Label-free tuning of zero-shot classifier using language and unlabeled image collections." NeurIPS'24.

[7] Zhao, Shuai, et al. "Test-time adaptation with clip reward for zero-shot generalization in vision-language models." arXiv preprint arXiv:2305.18010.

[8] Abdul Samadh, Jameel, et al. "Align your prompts: Test-time prompting with distribution alignment for zero-shot generalization." NeurIPS'24.

[1] Saerens, Marco, Patrice Latinne, and Christine Decaestecker. "Adjusting the outputs of a classifier to new a priori probabilities: a simple procedure." Neural computation 14.1 (2002): 21-41.

[2] Lipton, Zachary, Yu-Xiang Wang, and Alexander Smola. "Detecting and correcting for label shift with black box predictors." ICML'18.

[3] Azizzadenesheli, Kamyar, et al. "Regularized Learning for Domain Adaptation under Label Shifts." ICLR'18.

[4] Alexandari, Amr, Anshul Kundaje, and Avanti Shrikumar. "Maximum likelihood with bias-corrected calibration is hard-to-beat at label shift adaptation." ICML'20.

[5] Garg, Saurabh, et al. "A unified view of label shift estimation." NeurIPS'20.

[6] Lee, Yin Tat, and Aaron Sidford. "Path finding methods for linear programming: Solving linear programs in $\tilde{O}(\sqrt{rank})$ iterations and faster algorithms for maximum flow." IEEE 55th Annual Symposium on Foundations of Computer Science. IEEE, 2014.

We appreciate the thoughtful comments and references. We will include links to proofs and will clarify the statements corresponding to the reviewer's questions in our updated draft.

• On the proposal saying that Bayes optimal classifier can be derived through optimal transport: The statement in L151 means OTTER does not cause harm when the cost matrix has the true target posterior $P_t(Y|X)$; we do not need $P_t(Y|X)$ to make OTTER work well. This result is connected to Theorem 4.2 in Section 4.1. Since the assumption in Theorem 4.2 makes OTTER with $C_{ij}=P_{\theta}(Y|X)$ and OTTER with $C_{ij}^*=P_{t}(Y|X)$ equivalent, OTTER can achieve the Bayes optimal classifier performance. We will make this connection clear.

• On the interpretation of Figure 2: In Figure 2(a), $\delta$ represents noise in prediction scores, which affects calibration. Such errors may affect the performance of OTTER. Without perturbation ($\delta=0$), OTTER remains unaffected by the label distribution shift (L265-266), achieving a Bayes optimal classifier.

Additional questions:

• Considering each cell ... assigning true label?: Our theorem shows that even when the cost matrix is biased to the source data distribution, optimal transport can fix the bias from the source data distribution using the label distribution specification. It does not necessarily assign true labels---it yields better predictions when the label distribution specification is better than the label distribution of biased zero-shot predictions, given proper calibration. We validate this finding by observing the performance gain in our experiments.

• How can the true label distribution of the target, $\nu^*$, be accessible?: This is not necessary---see our common response and additional experiments. We also note that there are many label distribution estimation algorithms (e.g. [1,2,3,4,5]). Any available method can be plugged into OTTER. For example, we used BBSE [1] as a label distribution estimation method in the linear probing setting.

• More details for the equation of section 4.1?: On Equation in Section 4.1. Equation in Section 4.1. mainly proceeds with Bayes Rule and invariance assumption $P_s(X|Y)$=$P_t(X|Y)$.

$\tilde{s}_{\theta}$

$=s_{\theta}\frac{P_t(Y=j)}{P_s(Y=j)} \qquad \because$ by adjustments

$=P_s(Y=j|X=x)\frac{P_t(Y=j)}{P_s(Y=j)} \qquad \because$ by the assumption $s_{\theta}=P_s(Y=j|X=x)$

$=\frac{P_s(X=x|Y=j)P_s(Y=j)}{P_s(X=x)}\frac{P_t(Y=j)}{P_s(Y=j)} \quad \because$ by Bayes rule

$=\frac{P_s(X=x|Y=j)P_t(Y=j)}{P_s(X=x)}$

$=\frac{P_t(X=x|Y=j)P_t(Y=j)}{P_s(X=x)} \quad \because$ by the assumption $P_s(X=x|Y=j)=P_t(X=x|Y=j)$

$\propto P_t(X=x|Y=j)P_t(Y=j)$

$=\frac{P_t(Y=j|X=j)P_t(X=x)}{P_t(Y=j)}P_t(Y=j) \quad \because$ by Bayes rule

$=P_t(Y=j|X=j)P_t(X=x)$

$\propto P_t(Y=j|X=j)$

Here, $P_s(X=x)$ and $P_t(X=x)$ can be omitted using $\propto$ as they do not affect the classification output.

• In table 1, what happened to Caltech256 Prior matching?: We found that prior matching is sensitive to the learning rate and temperature hyperparameters---but hyperparameter tuning with plentiful data is typically not an option for zero-shot models. In the experiments for Table 1, we selected hyperparameters of prior matching via grid search, by evaluating their performance on small validation data (10 shots per class). Prior matching's accuracy in Caltech256 shows the case hyperparameter search fails, which leads to suboptimal solutions in the optimization of the weights $r$ (L557-558).

• In figure 2, Why OTTER shows acc increase...: The Bayes error rate changes with the label shift. Thus accuracy of Bayes optimal classifier changes, and OTTER follows the accuracy of Bayes optimal classifier. Specifically, given $\mathcal{N}(-1,1)$ and $X|Y=1 \sim \mathcal{N}(1,1)$, the error rate $\int_x1-\max_yP(Y=y|X=x)$ is maximized at $\nu^s_0$=$\nu^s_1$=0.5. Total variation 0.4 corresponds to this point, and the Bayes error rate is reduced after that. OTTER achieves the Bayes error regardless of label distribution shift, while naive classification deteriorates with the magnitude of the label distribution shift.

• How long does it take to apply OTTER? I suppose it will take quadratically proportional to the dataset size.: We report computation time in Appendix E.3. Table 10. The computational complexity depends on implementation. The linear programming version of the optimal transport algorithm can run in $\tilde{O}(nk\sqrt{n+k})$ time via minimum cost flow [6], where $n$ is the number of data points and $k$ is the number of classes. Thus, computation time subquadratically increases in the number of data points. In practice, we observed our method gives modified predictions within 0.05 ms per sample---a negligible overhead. Additionally, a batched version with parallel computing is an option for massive inference. We included an experiment where the performance of optimal transport changes depending on batch size in Figure 1 of the attached pdf. The result shows that reasonable accuracy improvements can be obtained even when randomly partitioning data and applying OTTER.

We appreciate the reviewer's consideration and are more than willing to address any further concerns. If we have adequately resolved the issues, we would be grateful if the reviewer could consider raising their score.

Dear reviewer,

Thank you for your assistance in the review process. Could you please read the author rebuttal ASAP and let them / fellow reviewers know if it addressed your concerns?

We sincerely thank the reviewer for their kind words, constructive feedback, and useful suggestions. We appreciate the reviewer recognizing the novelty of our work and its strong theoretical foundation. We plan to include the suggested related works and fix typos.

• On additional related works (Major 1): Thank you for providing more related works. We plan to include the suggested papers in our related works with the following discussion. [1, 2, 3] address the bias induced by the concept distribution in pretraining data, in a similar context as OTTER. [1] tackles word frequency bias in pretraining and spurious concept frequency bias in test data in prompt ensembles. This work normalizes/debiases logit scores with the logits from the pretraining data to reweight/select prompts. [2] addresses concept frequency bias in pretraining data as well via retrieval augmented prompting, i.e. retrieving the most frequent concept from synonyms of the label. First, they propose a new concept frequency estimation method with LLMs. By concept frequency estimation, they re-confirm long-tailed concept distribution, and they propose retrieval-based prompting/linear classifier training. Similarly, [3] adjusts logits to debias pretraining / fine-tuning label distribution. They propose a pretraining label distribution estimation method with an optimization formulation and show that the proposed adjustment make the finetuning. The main distinction of OTTER from these works is that it does not require access to the pretraining data distribution, as long as the label distribution specification is properly given. This is particularly advantageous because pretraining data is often inaccessible due to proprietary or privacy issues.

• On the comparison with [3] (Major 2): [3] tackles a similar problem in the sense they try to mitigate bias from pretraining, but there are several key differences: 1) [3] mainly considers fine-tuned models and uses ensembles of these fine-tuned models and zero-shot models, while our work focuses exclusively on zero-shot models. 2) [3] assumes a uniform label distribution in target distribution for their Bayes classifier result. If we make such an assumption, OTTER can achieve the Bayes classifier performance without access to the pretraining distribution. [3] presented an extension for label shifts in the target distribution in its appendix, which requires the target label distribution as well. Also, while our method often uses the entire test set, batch optimal transport can be applied in the case the large-scale inference is required (as we described in the common response). In practice, applying OTTER to inference set with $n<20000$ usually takes less than 1 second, as can be seen in Appendix E.3. Table 10. We added additional experimental results with the batched version of OTTER (randomly partition test data and apply OTTER with the global label distribution specification) in Figure 2 (attached pdf). The results show that batched version still improves accuracy, enabling parallel processing. We expect batched OTTER can be further improved with more recent works on batched optimal transport [4, 5].

• On the label shift assumption that P(X|Y) does not change: If P(X|Y) changes, the invariance result does not hold (it is the same for [3]). Instead, our error bound in Section 4.3. provides an accuracy bound. Suppose the posterior ratio is given by $\epsilon_{ij}=\frac{P_t(X=x_i|Y=j)}{P_s(X=x_i|Y=j)}$ in the setup of Appendix D.2. Proof of Theorem 4.2. Then, the proof lines change as follows

$C^*_{ij}$

$= - \log P_t(Y=j|X=x_i)$

$= - \log \frac{P_t(X=x_i|Y=j)P_t(Y=j)}{P_t(X=x_i)}$

$= - \log \frac{\epsilon_{ij}P_s(X=x_i|Y=j)P_t(Y=j)}{P_t(X=x_i)}$

$= - \log \frac{\epsilon_{ij}P_s(Y_j|X=x_i)P_s(X=x_i)P_t(Y=j)}{P_s(Y=j)P_t(X=x_i)}$

$= -\log\epsilon_{ij}-\log P_s(Y=j|X=x_i)\frac{P_s(X=x_i)P_t(Y=j)}{P_t(X=x_i)P_s(Y=j)} -\log P_s(Y=j|X=x_i) + \log P_s(Y=j)$

$= -\log\epsilon_{ij}+C_{ij} + E_{\cdot j} + F_{i \cdot}$

This shows that when the label shift assumption is violated, OTTER with $C_{ij}=-\log P_{\theta}(Y=j|X=x_i)$ yields equivalent predictions with $C_{ij}^* + \log{\epsilon_{ij}}$ rather than $C^*_{ij}$, making it suboptimal. The similar deviation can be observed in the Proof of Proosition of [3] by plugging $\epsilon_{yz}=\frac{P_t(z|y)}{P_p(z|y)}$ into Equation (28), (29). However, in our analysis, Theorem 4.3. shows the additional error rate linearly depends on the log ratio of $P_t(X|Y)$ and $P_s(X|Y)$ by defining cost matrix gap as $\Delta_{C_{ij}} = \log \epsilon_{ij}$. Thus, if the deviation is not significant, we can expect near-invariant results. In practice, as we can see in ImageNet-Sketch results, OTTER works well even when P(X|Y) invariance is violated.

We appreciate the reviewer's consideration and are more than willing to address any further concerns. If we have adequately resolved the issues, we would be grateful if the reviewer could consider raising their score.

[1] Allingham, James Urquhart, et al. "A simple zero-shot prompt weighting technique to improve prompt ensembling in text-image models." ICML'23.

[2] Parashar, Shubham, et al. "The Neglected Tails in Vision-Language Models." CVPR'24.

[3] Zhu, Beier, et al. "Generalized logit adjustment: Calibrating fine-tuned models by removing label bias in foundation models." NeurIPS'23

[4] Nguyen, Khai, et al. "Improving mini-batch optimal transport via partial transportation." ICML'22.

[5] Nguyen, Khai, et al. "On Transportation of Mini-batches: A Hierarchical Approach." ICML'22.

Thank you for your response. Regarding your reply to W2, if I understand correctly, the authors suggest that the proposed OTTER method at least requires a batch of test samples to produce an unbiased prediction. My question is, if we are given a set of i.i.d. validation data with zero-shot predictions $y_{zs}$ and debiased predictions $y_{otter}$, is it possible to use these terms to derive $(\log\frac{P_t(y)}{P_s(y)}$such that the requirement of using all test data or a batch of test samples can be avoided?