:
2023 Machine Learning for Healthcare

# Sample-Specific Debiasing for Better Image-Text Models

###### Abstract

Self-supervised representation learning on image-text data facilitates crucial
medical applications, such as image classification, visual grounding, and
cross-modal retrieval. One common approach involves contrasting semantically
similar (positive) and dissimilar (negative) pairs of data points. Drawing
negative samples uniformly from the training data set introduces false
negatives, i.e., samples that are treated as dissimilar but belong to the same
class. In healthcare data, the underlying class distribution is nonuniform,
implying that false negatives occur at a highly variable rate. To improve the
quality of learned representations, we develop a novel approach that corrects
for false negatives. Our method can be viewed as a variant of debiased
constrastive learning that uses estimated sample-specific class probabilities.
We provide theoretical analysis of the objective function and demonstrate the
proposed approach on both image and paired image-text data sets. Our
experiments demonstrate empirical advantages of sample-specific debiasing.

##  1 Introduction

In this paper, we propose and demonstrate a novel approach for contrastive
learning of image-text representations. Our method achieves state-of-the-art
performance by estimating sample-specific class probabilities to compensate
for false negative samples in the learning procedure.

Self-supervised representation learning on paired image-text data uses text as
“labels”, requiring no further annotations beyond what has been routinely
documented (Radford et al., 2021). By leveraging natural language to reference
visual concepts and vice versa, the resulting image-text models trained using
self-supervised objectives can perform a diverse set of vision-language tasks.
When applied to the medical domain, image-text models can (i) retroactively
label images to select relevant patients for a clinical trial, (ii) help
physicians verify the accuracy of a report by noting whether the referred
location (i.e., visual grounding of the text) is consistent with their
impression of the image, and (iii) enable informed interpretation of medical
images by retrieving similar previously imaged patients from a database.
Moreover, the abundance of paired image-text data (e.g., radiographs and
radiology reports, histology slides and pathology reports) suggests the broad
applicability of self-supervision using image-text data to improve healthcare.

In this paper, we focus on contrastive learning, a self-supervised approach
that encourages the representations of semantically similar or positive pairs
of data to be close, and those of dissimilar or negative pairs to be distant.
Contrastive learning has been applied in the medical domain, demonstrating
impressive transfer capabilities on a diverse set of downstream tasks (Chauhan
et al., 2020; Huang et al., 2021; Liao et al., 2021; Müller et al., 2022;
Zhang et al., 2022b; Boecking et al., 2022; Wang et al., 2023; Bannur et al.,
2023). The biggest improvements come from addressing challenges unique to this
domain. Examples include using cross-attention to localize areas of interest
to handle the lack of effective pathology detectors (Huang et al., 2021),
fine-tuning language models on medical corpora to address linguistic
challenges in clinical notes (Boecking et al., 2022), and removing ambiguities
that arise from references to previous imaging events by explicitly using
these comparisons as a form of self-supervision (Bannur et al., 2023). In a
similar spirit, our work aims to address the nonuniform class distribution
typical of clinical data.

Figure 1: False negatives in paired image-text data. Drawing negative image
samples $x_{n}^{-}$ from the data distribution $\mathcal{D}$ may result in
samples that are semantically similar to the text $x$ (“Heart is enlarged” and
“Cardiomegaly” imply the same pathology). False negative samples occur at an
uneven rate (e.g., depending on the pathology type) and degrade the
performance of image-text models on downstream tasks.

Using text as “labels” implies a nonuniform class distribution with large
support. Specifically, natural language descriptions of medical images can
represent a vast number of possible classes. Most descriptions belong to only
a small number of common classes (e.g., cardiomegaly) while the remaining
descriptions are spread across many rare classes (e.g., left apical
pneumothorax). For example, CheXpert labels (Irvin et al., 2019) that
represent frequently occurring classes in chest radiographs are mentioned in
$10\text{-}25\%$ of the radiology reports in MIMIC-CXR, a large collection of
chest X-ray images and radiology reports (Johnson et al., 2019) . The rare
classes can be more descriptive and may be associated with high risk, which
makes their accurate identification important in clinical applications. Our
goal is to handle the highly nonuniform class distribution that presents a
challenge for many existing modeling approaches.

When training an image-text model using contrastive learning, each text is
positively paired with the associated image from the same imaging event and
negatively paired with a batch of images uniformly drawn from the training
data set (Li et al., 2019; Lu et al., 2019; Chen et al., 2020; Radford et al.,
2021; Liao et al., 2021; Zhang et al., 2022b; Wang et al., 2023). If a
negatively paired image is semantically similar to the text, it is considered
as a false negative (Saunshi et al., 2019), as shown in Figure 1. It has been
shown previously that false negatives result in a substantial decline in
downstream classification performance when using image representations trained
with contrastive learning (Chuang et al., 2020).

One approach to alleviating the problem of false negatives is to identify
false negative pairs explicitly and to reduce their effect. In some
applications, ground truth class labels are available and can be used to
ensure that no false negative pairs are generated (Khosla et al., 2020;
Dwibedi et al., 2021). Unfortunately, deriving categorical labels from text is
challenging because it can be difficult to determine the appropriate level of
granularity and ensure sufficient coverage when the class distribution has a
large support. Label imputation with nearest neighbor methods (Zheng et al.,
2021) or clustering (Chen et al., ) introduces non-trivial implementation and
computational burden. In the absence of hard labels, negative samples whose
embeddings are close to positive samples are treated as false negatives and
are eliminated (Huynh et al., 2022; Zhang et al., 2022a; Zhou et al., 2022;
Wang et al., 2022). This approach is easy to implement but it overlooks
valuable information captured by text if only image embedding is used.
Moreover, rejecting negative samples whose embeddings are close to positive
samples runs the risk of removing valuable “hard negatives”, i.e., visually
similar true negative samples.

Debiased contrastive learning takes a different approach that uses (possibly)
extra positive samples to offset the influence of false negatives without
explicitly identifying them (Chuang et al., 2020). It assumes a uniform class
distribution and applies a constant correction to each sample. This strategy
can be suboptimal for healthcare data where the class distribution is highly
nonuniform. We observe that naively applying debiased contrastive learning
introduces a performance trade-off between coarse-grained tasks (e.g.,
classifying pneumonia) and fine-grained tasks (e.g., cross-modal retrieval of
rare classes).

In this paper, we propose to reduce the effects of false negatives in
contrastive representation learning that makes no assumption on the underlying
class distribution. Specifically, we estimate the class probability (or level
of correction) for each data point based on the likelihood of the text
provided by a language model. Our method (i) does not require or attempt to
infer class labels, (ii) requires a few extra lines of code to implement when
compared with contrastive objectives typically used in practice, (iii) incurs
minimal computational overhead, and (iv) takes the advantage of the class
information implicitly represented by the text “labels” to mitigate the
problem of false negatives in image-text contrastive learning. We study the
advantages of using sample-specific class probability estimates on a small-
scale image data set constructed with a nonuniform class distribution. We
evaluate our approach on a large set of chest X-ray images and associated
radiology reports (Johnson et al., 2019), demonstrating superior performance
on image classification, visual grounding, and cross-modal retrieval tasks.

### Generalizable Insights about Machine Learning in the Context of Healthcare

Our work (i) provides direct value to those interested in using self-
supervised representation learning for healthcare applications, (ii)
highlights the importance of considering the distinct characteristics of
healthcare data that can pose challenges for methods designed for simpler
scenarios (in our case, false negatives degrade the performance of image-text
models trained on clinical data), and (iii) shows that a language model
provides a useful prior that can be employed in other image-text modeling
problems (e.g., brain tumor CT scans with imaging reports) or inspire future
research to solve related problems in other data modalities.

##  2 Methods

In this section, we introduce notation and provide a brief overview of the
debiased contrastive learning (Chuang et al., 2020), followed by the
derivation of our method to compensate for potential false negative samples
and analysis of the relationship between our approach and the original
formulation.

###  2.1 Notation and Problem Setup

We assume that the training data is generated from a mixture distribution with
$c\in\mathcal{C}$ denoting the latent class whose distribution $\rho(\cdot)$
is defined over a (potentially large) finite alphabet $\mathcal{C}$. Given
$c_{x}\in\mathcal{C}$, a data point $x$ is generated from a conditional
distribution $\mathcal{D}_{c_{x}}(\cdot)$ over the set of all data points
$\mathcal{X}$. A training set comprises i.i.d samples from the marginal
distribution
$\mathcal{D}(x)=\sum_{c\in\mathcal{C}}\rho(c)\,\mathcal{D}_{c}(x).$ Classes
$c_{x}$ is unknown for any data point $x$ in the data set.

In contrastive learning, we generate “positive samples” $(x,x^{+})$ where $x$
and $x^{+}$ are guaranteed to belong to the same class by construction. This
is achieved for example by applying data augmentation that does not change the
(unobserved) class $c$ (e.g., object identity) to generate $x^{+}$ from $x$.
In image-text alignment, $x^{+}$ is the image associated with the radiology
report $x$. Generating “negative samples” $(x,x^{-})$ where $x$ and $x^{-}$
are guaranteed to belong to different classes is more challenging. Formally,
if $x$ is generated from class $c_{x}$, $x^{-}$ should be generated from
distribution

$\displaystyle\mathcal{E}_{c_{x}}(x^{\prime})\triangleq p(x^{\prime}|c\neq
c_{x})=\sum_{c\neq
c_{x}}\frac{\rho(c)}{1-\rho(c_{x})}\,\mathcal{D}_{c}(x^{\prime}),$ (1)

which is infeasible since we don’t know class $c_{x}$. It is straightforward
to show that
$\mathcal{D}(x^{\prime})=\rho(c_{x})\,\mathcal{D}_{c_{x}}(x^{\prime})+(1-\rho(c_{x}))\,\mathcal{E}_{c_{x}}(x^{\prime})$
and therefore

$\displaystyle\mathcal{E}_{c_{x}}(x^{\prime})$
$\displaystyle=\frac{1}{1-\rho(c_{x})}\,\mathcal{D}(x^{\prime})-\frac{\rho(c_{x})}{1-\rho(c_{x})}\,\mathcal{D}_{c_{x}}(x^{\prime}).$
(2)

In computer vision applications, the number of classes is large and
$\rho(c_{x})$ is likely to be small for any $c_{x}$. Thus using $\mathcal{D}$
instead of $\mathcal{E}_{c_{x}}$ for sampling negative examples is reasonable.
Moreover, it is natural to assume that all classes are equally (un)likely.
Unfortunately, neither assumption is true in the healthcare setting. In
clinical image sets, the probability of common pathologies in a randomly
chosen image is not negligible and moreover, common pathologies appear an
order of magnitude more frequently than uncommon ones. Debiased contrastive
learning (Chuang et al., 2020) addresses the former problem by modifying the
optimization function to explicitly account for the chance of false negatives
uniformly across classes. We build on that formulation to address the latter
challenge by introducing class-specific modified contrastive loss.

###  2.2 Debiased Contrastive Learning

The contrastive learning objective forces representations of positive pairs to
be closer than those of negative pairs (van den Oord et al., 2018) by
minimizing

$\displaystyle\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}},\\{x_{n}^{-}\\}\sim\mathcal{D}^{N}}\left[-\log\frac{e^{s(x,x^{+})}}{e^{s(x,x^{+})}+\sum_{n=1}^{N}e^{s(x,x_{n}^{-})}}\right],$
(3)

where the bounded function $s\colon\mathcal{X}\times\mathcal{X}\to\mathbb{R}$
measures the similarity (e.g., a dot-product) between learned representations
captured by encoder function $f:\mathcal{X}\to S^{d-1}(\gamma)$ that maps data
from $\mathcal{X}$ to a hypersphere of radius $\gamma$, i.e.,
$S^{d-1}(\gamma)=\left\\{x\in\mathbb{R}^{d}\mid\left\lVert
x\right\rVert_{2}=\gamma\right\\}$. The parameter $\tfrac{1}{\gamma^{2}}$ is
the typical temperature scaling hyperparameter during learning to avoid
gradient saturation. For image-text contrastive learning,
$\mathcal{D}_{\text{sim}}(x,x^{+})$ is a distribution of image-text pairs and
$f$ performs either image or text encoding, depending on the nature of the
input data. Without access to class labels, the negative samples are typically
uniformly drawn from the data distribution $\mathcal{D}$. Thus for $x$
generated from (unknown) class $c_{x}$, sample $x_{n}^{-}$ is a false negative
with latent probability $\rho(c_{x})$.

The asymptotic debiased contrastive learning objective (Chuang et al., 2020)
considers the case where the number $N$ of negative samples from
$\mathcal{E}_{c_{x}}$ goes to infinity:

$\displaystyle\tilde{\mathcal{L}}\triangleq\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[-\log\frac{e^{s(x,x^{+})}}{e^{s(x,x^{+})}+N\,\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]}\right].$
(4)

Given $N$ samples $\left\\{u_{n}\right\\}$ from $\mathcal{D}$ and $M$ samples
$\left\\{v_{m}\right\\}$ from $\mathcal{D}_{c_{x}}$, the expected value in the
denominator of Equation 4 can be estimated with

$\displaystyle
g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\};\eta)\triangleq\frac{1}{1-\eta}\left[\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}\right]-\frac{\eta}{1-\eta}\left[\frac{1}{M}\sum_{m=1}^{M}e^{(x,v_{m})}\right].$
(5)

To avoid numerical issues, the estimator
$g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\};\eta)$ is lower bounded by
its theoretical minimum $e^{-\gamma^{2}}$ (Chuang et al., 2020). $\eta$ is the
prior class probability (for the uniform distribution) and is treated as a
hyperparameter. The resulting debiased contrastive loss reweights the positive
and negative term in the denominator:

$\displaystyle\mathcal{L}\triangleq\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}},\\{u_{n}\\}\sim\mathcal{D}^{N},\\{v_{m}\\}\sim\mathcal{D}_{c_{x}}^{M}}\left[-\log\frac{e^{s(x,x^{+})}}{e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\};\eta)}\right].$
(6)

###  2.3 Sample-specific Class Probability Function $\eta$

The formulation above use a single hyperparameter $\eta$ to correct for false
negatives uniformly for every data point. We propose to employ an estimate of
the class probability $\rho(c_{x})$ with a sample-specific class probability
function $\eta(\cdot)$. We replace $\eta$ with $\eta(x)$ in Equation 5

$\displaystyle
g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\};\eta)\triangleq\frac{1}{1-\eta(x)}\left[\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}\right]-\frac{\eta(x)}{1-\eta(x)}\left[\frac{1}{M}\sum_{m=1}^{M}e^{(x,v_{m})}\right]$
(7)

and use the objective function defined in Equation 6 with $g$ in Equation 7.
In practice, $\eta$ may be an imperfect estimator for $\rho(c_{x})$. The
following proposition informs us how $\eta$ affects the approximation error.

######  Proposition 2.1.

Let $f(\cdot)$ and $\eta(\cdot)$ be arbitrary functions, $N$ and $M$ be
finite. Then,

$\displaystyle\left|\tilde{\mathcal{L}}-\mathcal{L}\right|$
$\displaystyle\leq\frac{3e^{2}\sqrt{\pi/2}}{\sqrt{N}}\,\mathbb{E}_{x\sim\mathcal{D}}\left[\frac{1}{1-\rho(c_{x})}\right]+\frac{2e^{2}}{\sqrt{M}}\,\mathbb{E}_{x\sim\mathcal{D}}\left[\frac{\rho(c_{x})}{1-\rho(c_{x})}\right]$
(8)
$\displaystyle\quad+2e^{2}\mathbb{E}_{x\sim\mathcal{D}}\left[\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right].$
(9)

Proof is provided in Appendix A.1.

Proposition 2.1 bounds the approximation error due to (i) finite sample
approximation in Equation 5 (first two terms
$\mathcal{O}(\tfrac{1}{\sqrt{N}}+\tfrac{1}{\sqrt{M}})$ and (ii)
misspecification of the sample-specific class probability $\eta(x)$ (last
term). When $\rho$ is uniform and $\eta(x)=\rho(c_{x})$ is a constant,
Proposition 2.1 reduces to the result in Chuang et al. (2020), up to a
constant factor. Assuming access to $c_{x}$ and using the correct class
distribution $\rho$, i.e., $\eta(x)=\rho(c_{x})$, yields a tighter error bound
since the last term in the upper bound (Equation 9) vanishes. Therefore, we
aim to use $\eta(x)$ that closely matches the true sample-specific class
probability $\rho(c_{x})$.

In Appendix A.2, we show classification generalization bounds on
representations trained using debiased contrastive loss with the sample-
specific probability function $\eta$ (in Equation 7), for arbitrary class
distribution setup.

###  2.4  Language Model Estimate of Class Probability

We employ the likelihood of the text $p_{\text{LM}}(x)$ provided by a language
model (LM) for text $x$ to construct the estimate $\eta(x)$ of the class
probability $\rho(c_{x})$. Language models naturally provide estimates of
token sequence probabilities. The estimates get better if the language model
is fine-tuned on the data $\mathcal{D}$. We assume a log-linear relationship
between text and class probabilities, i.e., $\eta_{\text{LM}}(x)=a\cdot
p_{\text{LM}}(x)^{k}$ where $a$ and $k$ are hyperparameters.

##  3 Experiments

We evaluate the advantages of estimating sample-specific class probability for
contrastive learning in two different experiments.

###  3.1 CIFAR10

In this experiment, we evaluate image-only representations on data sets with a
controlled class distribution. We do not attempt to estimate the class
probabilities (since no text information is available and would not be helpful
since we control the frequency with which each class is included in the data
set) but instead use the true class distribution during training and examine
the effect of class distribution of the data set on the resulting
representations.

##### Data

For each $r\in\\{0.05,0.1,0.25,0.5,0.75,0.9\\}$, we generate a CIFAR10-$r$
subset of the CIFAR10 data set (Krizhevsky, 2009) as follows. The original
data set includes 6,000 images for each class. For each of $5$ selected
classes (dog, frog, horse, ship, truck), we randomly draw and include $r$
fraction of the images. We keep all images for each of the remaining $5$
classes. The CIFAR10-$r$ data set has a class probability of
$\eta_{\text{High}}=0.2r/(1+r)$ for each of the 5 selected classes and
$\eta_{\text{Low}}=0.2/(1+r)$ for the remaining classes. Larger values of $r$
leads to a more uniform class distribution.

##### Representation Learning

Similar to Chuang et al. (2020), we use SimCLR (Chen et al., ) for contrastive
learning of image representations. We employ ResNet-18 (He et al., 2016) as
the image encoder $f$ and dot-product as the similarity function $s$. The
encoder is followed by a $2$-layer perceptron to create a $128$-dimensional
embedding. For a reference image $x$, we employ data augmentation to generate
positive samples $x^{+}$ and use $\left\\{v_{m}\right\\}=x^{+}$ to avoid
needing additional samples ($M=1$). We draw samples $\left\\{u_{n}\right\\}$
and $\left\\{x_{n}^{-}\right\\}$ randomly from the data set ($N=254$). We set
$\gamma=\sqrt{2}$. We use the Adam optimizer (Kingma and Ba, 2014) with a
learning rate of $10^{-3}$ and weight decay of $10^{-6}$. Each model is
trained for $300$ epochs.

##### Contrastive Loss Variants

We learn image representations using four different types of contrastive
objectives: (i) baseline contrastive learning without correction for false
negatives (CL), (ii) debiased contrastive learning that uses a constant
$\eta_{\text{Low}}$ providing the true class probabilities for the $5$
subsampled classes (DCL-$\eta_{\text{Low}}$) and misspecified class
probabilities for the remaining classes (iii) debiased contrastive learning
that uses a constant $\eta_{\text{High}}$ providing misspecified class
probabilities for the subsampled classes and the true class probability for
the remaining 5 classes (DCL-$\eta_{\text{High}}$), and (iv) debiased
contrastive learning with the true sample-specific class probability function
for all samples (DCL-$\eta_{\text{True}}$).

##### Image Classification

We evaluate the quality of image representations with linear evaluation. We
train a linear classifier with cross-entropy loss with the fixed pretrained
image encoder. We use the Adam optimizer with a learning rate of $10^{-3}$ and
weight decay of $10^{-6}$. Each model is trained for $100$ epochs. We report
classification accuracy with varying number of annotated examples available
for training the classifier.

Figure 2: Evaluation using downstream classification task for CIFAR10
experiment. Left: Classification accuracy as a function of class distribution
uniformity $r$. Right: Classification accuracy as a function of the fraction
of images for which labels where provided for classifier training on
CIFAR10-$0.5$ data set. Fine-grain debiased contrastive learning with true
class probabilities (DCL-$\eta_{\text{True}}$) consistently outperforms
baseline contrastive learning (CL) and debiased contrastive learning with
misspecified class probabilities (DCL-$\eta_{\text{Low}}$ and
DCL-$\eta_{\text{High}}$). The effect is more pronounced when fewer labels are
used for training the classifier.

##### Results

Figure 2 reports the effects of the choice of sample-specific class
probability function $\eta$ on classification accuracy. When the class
distribution is nonuniform (i.e., smaller $r$), we observe that
DCL-$\eta_{\text{True}}$ consistently outperforms CL, DCL-$\eta_{\text{Low}}$,
and DCL-$\eta_{\text{High}}$. When the class distribution is close to uniform
(i.e., $r$ is close to 1), all contrastive loss variants result in similar
accuracy. Figure 2 also shows that the gain from using the true sample-
specific class probability is more pronounced when the classifier is trained
with fewer labels. Figure 4 provides t-SNE (van der Maaten and Hinton, 2008)
visualizations of the representations learnt by contrastive and debiased
contrastive objectives on CIFAR10-$0.1$. Using the true sample-specific class
probability function $\eta_{\text{True}}$ leads to better class separation,
especially for the subsampled classes.

###  3.2 MIMIC-CXR

We learn image and text encoders for frontal chest X-ray images and associated
radiology reports respectively and evaluate the resulting representations in a
set of downstream tasks.

##### Data

We use a subset of 234,073 frontal chest X-ray images and reports from MIMIC-
CXR (Johnson et al., 2019). We normalize the images and resize them to 512x512
resolution. We apply random image augmentations, i.e., 480x480 random crops,
brightness and contrast variations. We use PySBD (Sadvilkar and Neumann, 2020)
for sentence tokenization. In all experiments, the data used for
representation learning and downstream tasks are disjoint.

##### Representation Learning

We employ ResNet-18 (He et al., 2016) as the image encoder and CXR-BERT
(Boecking et al., 2022) as the sentence encoder. Each encoder is followed by a
linear mapping to a $128$ dimension embedding space. We use LSE+NL (Wang et
al., 2023) as the similarity function $s$. Given a reference text $x$, we
assign $x^{+}$ to be the associated image and sample
$\left\\{x^{-}_{n}\right\\}$ randomly from the data set. For debiased
contrastive learning, we use all unpaired images in a batch as
$\left\\{u_{n}\right\\}$ ($N=63$) and use $v_{1}=x^{+}$ to avoid generating
additional positive samples ($M=1$). After a grid search, we set $a=0.2$ and
$k=0.35$. We precompute $p_{\text{LM}}(x)$ for all sentences $x$ in the data
set using CXR-BERT. Masked language models (e.g., CXR-BERT) cannot estimate
sentence probabilities via the chain rule. Instead, we use pseudo-log-
likelihood (Salazar et al., 2020) that scores a sentence $x$ by adding the
predicted log probabilities of every masked token as $\log p_{\text{LM}}(x)$.
We use the AdamW optimizer (Loshchilov and Hutter, ) and decay the initial
learning rate of $10^{-5}$ using a cosine schedule with 2k warmup steps. We
initialize $\gamma$ to 200 and optimize this hyperparameter alongside the
encoder parameters. We employ a batch size of 64.

#### Baseline Methods

We compare our method (DCL-$\eta_{\text{LM}}$) with strong baselines BioViL
(Boecking et al., 2022) and LSE$+$NL (Wang et al., 2023) developed
specifically for medical vision-language tasks. BioViL is an image-text model
trained using symmetric contrastive learning and masked language modeling
objective. LSE$+$NL is another image-text model that uses log-sum-exp and non-
local aggregators for the similarity function $s$. Neither model corrects for
the false negatives explicitly.

Figure 3:  Our method (DCL-$\eta_{\text{LM}}$) outperforms debiased
contrastive learning that applies a fixed amount of correction $\eta$ to all
samples (DCL-$\eta$) and LSE$+$NL that does not correct for the false
negatives (Baseline). For each value of $\eta$, an image-text model is trained
and subsequently evaluated in all three downstream tasks. Our method achieves
consistently better performance than alternative approaches.

We also include in the evaluation several methods that explicitly identify
false negatives based on the similarity measure between the positive sample
$x^{+}$ and negative samples $x_{n}^{-}$, such as the intersection of their
CheX5 labels (CheX5 Labels) or similarity of their text embeddings (Text
Sim.). Negative samples that are too similar (i.e., above some threshold) are
removed (Khosla et al., 2020; Huynh et al., 2022; Zhang et al., 2022a; Zhou et
al., 2022). Alternatively, we can reweight the negative samples or even reduce
the set of negative samples based on their similarity score (Robinson et al.,
; Wang et al., 2022). We perform grid searches to select hyperparameters
(e.g., the similarity threshold or the resampling size) and select the best
model for each setup.

In addition, we include the original debiased contrastive learning objective
that uses a constant $\eta$ (Chuang et al., 2020).

#### Downstream Tasks

##### Image Classification

We assess the zero-shot image classification performance of $5$ CheXpert
labels (Cardiomegaly, Edema, Pleural Effusion, Pneumonia, Pneumothorax) on the
MIMIC-CXR data set (Johnson et al., 2019) that we refer to as CheX5. There is
roughly 1k images for each binary classification task. We first tokenize and
encode class-specific text prompts (e.g., “No signs of pneumonia.” or
“Findings suggesting pneumonia.”). Table 2 provides the prompts for each
category. For every image, we assign a binary label that corresponds to the
prompt with the higher image-sentence score. We report classification accuracy
(ACC) and AUC.

##### Visual Grounding

We evaluate visual grounding performance using the MS-CXR region-sentence
annotations (Boecking et al., 2022). This data set consists of 1,448 bounding
boxes over 1,162 images, where each bounding box is associated with a sentence
that describes its dominant radiological feature. We compute region-sentence
scores to quantify how well the sentence is localized in the image. We report
a measure of discrepancy between region-sentence scores inside and outside the
bounding box, i.e., contrast-to-noise ratio (CNR) (Boecking et al., 2022), and
how well the thresholded region-sentence scores overlap with the bounding box
on average, i.e., mean intersection over union (mIoU). We use thresholds that
span $[-1,1]$ in $0.05$ increments to compute the mIoU.

Method | Classification | Grounding | Retrieval |
---|---|---|---|---
|  AUC$\uparrow$ |  ACC$\uparrow$ |  CNR$\uparrow$ |  mIoU$\uparrow$ |  Recall$\uparrow$ |  MedR$\downarrow$ |
No Correction BioViL |  0.783 |  0.622 |  1.14 |  0.174 |  0.246 |  148 |
No Correction LSE$+$NL |  0.788 |  0.646 |  1.40 |  0.190 |  0.289 |  115 |
Remove by CheX5 Labels |  0.856 |  0.708 |  1.37 |  0.190 |  0.293 |  113 |
Resample by Text Sim. |  0.816 |  0.705 |  1.37 |  0.190 |  0.302 |  111 |
Remove by Text Sim. |  0.840 |  0.720 |  1.39 |  0.191 |  0.298 |  112 |
Reweight by Text Sim. |  0.844 |  0.686 |  1.40 |  0.191 |  0.293 |  113 |
DCL-$\eta$ w/ $\eta=0.05$ |  0.802 |  0.718 |  1.46 |  0.193 |  0.302 |  104 |
DCL-$\eta$ w/ $\eta=0.1$ |  0.846 |  0.719 |  1.45 |  0.193 |  0.289 |  111 |
DCL-$\eta_{\text{LM}}$ (Ours) |  0.862 |  0.724 |  1.49 |  0.195 |  0.304 |  104 |
Table 1: Zero-shot performance of the learned representations on downstream
image classification, visual grounding, and cross-modal retrieval tasks.
Debiased contrastive learning with sample-specific class probability
$\eta_{\text{LM}}$ (DCL-$\eta_{\text{LM}}$ (Ours)) outperforms state of the
art baseline methods BioViL and LSE$+$NL (no false negative correction) and
alternative approaches to false negative correction. While methods that
correct for false negatives by removing, resampling, or reweighting are
effective in improving image classification results for commonly occuring
classes, they do not yield comparable improvements in visual grounding or
retrieval results.

##### Cross-Modal Retrieval

We evaluate cross-modal retrieval performance using the MS-CXR data set. To
evaluate retrieval, we compute the bounding box features from the region
features with RoIAlign (He et al., 2017). We compute box-sentence scores and
sort them to retrieve items in one modality given a query from the other
modality. The correctly retrieved item is the one that is paired with the
query item. We compute the fraction of times the correct item was found in the
top $K$ results (R@K), the median rank of the correct item in the ranked list
(MedR), and the average recall over $K=10,50,100$ and over both the image-to-
text and the text-to-image retrieval direction (Recall).

#### Results

Figure 3 illustrates performance trade-off for debiased contrastive learning
that uses a constant class probability function $\eta$. Increasing the value
of $\eta$ improves image classification but harms cross-modal retrieval
performance. Conversely, decreasing the value of $\eta$ enhances cross-modal
retrieval performance but harms image classification performance.
DCL-$\eta_{\text{LM}}$ provides an overall superior solution on all three
tasks.

Table 1 reports the performance of DCL-$\eta_{\text{LM}}$ and competing image-
text models. Training LSE$+$NL with DCL-$\eta_{\text{LM}}$ significantly
improves its performance on these tasks compared to BioViL and LSE$+$NL. Using
a sample-specific class probability function $\eta_{\text{LM}}$ is more
effective than using a constant function $\eta=0.05$ and $0.1$. The methods
that identify and remove, resample, or reweight the false negatives improve
image classification performance but do not offer any gain for visual
grounding and minimal improvement for cross-modal retrieval. Tables 3, 4, and
5 in Appendix C provide additional statistics for each task.

##  4 Discussion

We introduced a novel, sample-specific approach to correcting the effects of
false negative samples on the contrastive loss function. Consistent with prior
work (Chuang et al., 2020), this approach offers empirical advantages when the
learned representation is used in downstream tasks. We also show that sample-
specific approach to correcting for false negatives improves the performance
over the original variant of debiased contrastive learning that applied the
same correction for all data points.

Our experiments also demonstrate that reducing false negatives for tasks with
varying levels of granularity is nuanced. In particular, the methods that
attempt to remove or reweight likely false negative examples might improve
image classification performance but offer minimal or no improvement for
visual grounding and cross-modality retrieval. We hypothesize that this is due
to fine-grain classes that must be also handled for the latter two tasks and
are harder to identify when selecting false negative samples. Similarly, the
performance of representations learned via debiased constrastive learning with
a fixed correction factor was sensitive to the value of the assumed class
probability and varied substantially across the range of possible values.
Moreover, the optimal choice of the correction factor varied across downstream
tasks, making it challenging to train universally useful representations. In
contrast, the proposed fine-grain approach produces representations that
achieve superior performance across all tasks by automatically estimating the
sample-specific class probability.

Using all CheX5 labels to remove false negatives consistently improves the
performance of classifying the CheX5 classes. However, doing so has minimal
impact on visual grounding and cross-modal retrieval tasks that require the
ability to distinguish rare classes beyond those specified in CheX5. Methods
that require a clear definition of the latent classes (Khosla et al., 2020;
Dwibedi et al., 2021) are not easily adaptable to situations where there are
many classes or when the classes are difficult to define concretely. In
contrast, methods that implicitly define the latent classes via clustering
(Chen et al., ), or do not assume access to the latent classes (Chuang et al.
(2020) or our approach) show promise in improving model performance on vision-
language tasks.

In addition to the task itself, evaluation metrics are also sensitive to
different aspects of the representation. In our experiments, visual grounding
and cross-modal retrieval tasks use the MS-CXR data set that contains
infrequently occurring sentences. Thus one would assume both tasks would
benefit from using smaller values of $\eta$ than classification of commonly
occurring pathologies. However, the observed performance improvement for
grounding is less noticeable than for retrieval. One reason is that the
overlap-based metrics (e.g., IoU) used to evaluate grounding may be less
sensitive to the variations in text embeddings representing different but
related classes. In contrast, to achieve a high value of ranking-based metrics
(e.g., recall) requires the model to rank the correct sentence higher than
closely related alternatives. This unexpected result suggests that in addition
to the class distribution, target performance metrics that capture how the
model will be used in the clinical application are also important when
developing representation learning approaches. To the best of our knowledge,
our work is the first to identify these differences in performance of
downstream tasks due to the choices in compensating for the effect of false
negatives during representation learning. Limited evaluation of the downstream
performance in prior work led to the omission of the trade-off we observed in
our experiments.

Our work emphasizes the need to consider the unique characteristics of
healthcare data that pose challenges for methods designed for simpler
scenarios. When working with paired image-text data, we observe that false
negatives occur at an uneven rate, making methods designed to address false
negatives assuming a uniform class distribution less effective. Furthermore,
our work shows the potential of using language models to develop more
effective algorithms. Language models are versatile, i.e., capable of
processing noisy language inputs, and can serve as powerful priors.

### Limitations

While the theory presented in this paper is informative, it has limitations.
For example, the generalization bounds provided in Appendix A.2 assume a
specific similarity function (e.g., dot product) that may not represent the
various similarity functions used in practice. Moreover, the generalization
bounds only apply to downstream classification tasks while we also evaluate on
visual grounding and cross-modal retrieval tasks. While these tasks can be
interpreted as nearest neighbor classification, the theoretical results do not
trivially extend to these scenarios and more analysis is needed to provide
similar generalization guarantees for these tasks.

We use a language model to score text as a proxy for the sample-specific class
probability. However, it is unclear how to apply this strategy to data that
does not include associated text. While we can estimate data density with
certain types of models (e.g., flow-based or autoregressive models), it is not
well understood whether these estimates correlate well with the underlying
class probabilities. Natural language data is unique in that it is created by
humans, capturing important variations in data that align well with the types
of problems that users typically wish to solve.

Moreover, it is uncertain how well our assumption that class probability is
log-linear with respect to text sequence probability holds in practice.
Verifying this assumption requires defining a concrete set of latent classes
and annotating text with the defined classes. However, the latent classes are
difficult to define in practice, and we do not have access to the mapping from
a data point to its latent class in most clinically important problems as
having access to such mapping would eliminate the need for self-supervised
learning.

##  5 Conclusion

We present a debiased contrastive learning framework that accommodates
arbitrary class distributions and mitigates the impact of false negatives. We
offer theoretical and empirical evidence for using accurate sample-specific
class probabilities. We introduce a specific debiased contrastive objective
that employs a language model to estimate the sentence likelihood as a proxy
for the class probability. When applied to paired image-text data, our method
outperforms state-of-the-art models on image classification, visual grounding,
and cross-modal retrieval tasks.

## References

  * Bannur et al. (2023) Shruthi Bannur, Stephanie Hyland, Flora Liu, Fernando Pérez-García, Maximilian Ilse, Daniel Coelho de Castro, Benedikt Boecking, Harshita Sharma, Kenza Bouzid, Anja Thieme, Anton Schwaighofer, Maria Teodora Wetscherek, Matthew Lungren, Aditya Nori, Javier Alvarez-Valle, and Ozan Oktay.  Learning to exploit temporal structure for biomedical vision-language processing.  In _The IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Boecking et al. (2022) Benedikt Boecking, Naoto Usuyama, Shruthi Bannur, Daniel C. Castro, Anton Schwaighofer, Stephanie Hyland, Maria Wetscherek, Tristan Naumann, Aditya Nori, Javier Alvarez-Valle, Hoifung Poon, and Ozan Oktay.  Making the~Most of~Text Semantics to~Improve Biomedical Vision–Language Processing.  In _Computer Vision – ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXXVI_ , 2022.
  * Chauhan et al. (2020) Geeticka Chauhan, Ruizhi Liao, William Wells, Jacob Andreas, Xin Wang, Seth Berkowitz, Steven Horng, Peter Szolovits, and Polina Golland.  Joint Modeling of Chest Radiographs and Radiology Reports for Pulmonary Edema Assessment.  _Med Image Comput Comput Assist Interv_ , 2020.
  * (4) Tsai-Shien Chen, Wei-Chih Hung, Hung-Yu Tseng, Shao-Yi Chien, and Ming-Hsuan Yang.  Incremental false negative detection for contrastive learning.  In _International Conference on Learning Representations_.
  * Chen et al. (2020) Yen-Chun Chen, Linjie Li, Licheng Yu, Ahmed El Kholy, Faisal Ahmed, Zhe Gan, Yu Cheng, and Jingjing Liu.  UNITER: UNiversal Image-TExt Representation Learning.  In Andrea Vedaldi, Horst Bischof, Thomas Brox, and Jan-Michael Frahm, editors, _Computer Vision – ECCV 2020_. 2020.
  * Chuang et al. (2020) Ching-Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka.  Debiased Contrastive Learning.  In _Advances in Neural Information Processing Systems_ , 2020\.
  * Dwibedi et al. (2021) Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman.  With a Little Help from My Friends: Nearest-Neighbor Contrastive Learning of Visual Representations.  In _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick.  Mask R-CNN.  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , 2017.
  * Huang et al. (2021) Shih-Cheng Huang, Liyue Shen, Matthew P. Lungren, and Serena Yeung.  GLoRIA: A Multimodal Global-Local Representation Learning Framework for Label-Efficient Medical Image Recognition.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021.
  * Huynh et al. (2022) Tri Huynh, Simon Kornblith, Matthew R. Walter, Michael Maire, and Maryam Khademi.  Boosting Contrastive Self-Supervised Learning with False Negative Cancellation.  In _2022 IEEE/CVF Winter Conference on Applications of Computer Vision (WACV)_ , 2022.
  * Irvin et al. (2019) Jeremy Irvin, Pranav Rajpurkar, Michael Ko, Yifan Yu, Silviana Ciurea-Ilcus, Chris Chute, Henrik Marklund, Behzad Haghgoo, Robyn Ball, Katie Shpanskaya, et al.  Chexpert: A large chest radiograph dataset with uncertainty labels and expert comparison.  In _Proceedings of the AAAI conference on artificial intelligence_ , 2019.
  * Johnson et al. (2019) Alistair E. W. Johnson, Tom J. Pollard, Seth J. Berkowitz, Nathaniel R. Greenbaum, Matthew P. Lungren, Chih-ying Deng, Roger G. Mark, and Steven Horng.  MIMIC-CXR, a de-identified publicly available database of chest radiographs with free-text reports.  _Sci Data_ , 2019.
  * Khosla et al. (2020) Prannay Khosla, Piotr Teterwak, Chen Wang, Aaron Sarna, Yonglong Tian, Phillip Isola, Aaron Maschinot, Ce Liu, and Dilip Krishnan.  Supervised Contrastive Learning.  In _Advances in Neural Information Processing Systems_ , 2020\.
  * Kingma and Ba (2014) Diederik Kingma and Jimmy Ba.  Adam: A Method for Stochastic Optimization.  _International Conference on Learning Representations_ , 2014.
  * Krizhevsky (2009) Alex Krizhevsky.  Learning Multiple Layers of Features from Tiny Images.  2009\.
  * Li et al. (2019) Liunian Harold Li, Mark Yatskar, Da Yin, Cho-Jui Hsieh, and Kai-Wei Chang.  VisualBERT: A Simple and Performant Baseline for Vision and Language.  _arXiv:1908.03557 [cs]_ , 2019.
  * Liao et al. (2021) Ruizhi Liao, Daniel Moyer, Miriam Cha, Keegan Quigley, Seth Berkowitz, Steven Horng, Polina Golland, and William M Wells.  Multimodal representation learning via maximization of local mutual information.  In _Medical Image Computing and Computer Assisted Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France, September 27–October 1, 2021, Proceedings, Part II 24_ , 2021.
  * (19) Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization.  In _International Conference on Learning Representations_.
  * Lu et al. (2019) Jiasen Lu, Dhruv Batra, Devi Parikh, and Stefan Lee.  ViLBERT: Pretraining Task-Agnostic Visiolinguistic Representations for Vision-and-Language Tasks.  In _Advances in Neural Information Processing Systems_ , 2019\.
  * Müller et al. (2022) Philip Müller, Georgios Kaissis, Congyu Zou, and Daniel Rueckert.  Joint learning of localized representations from medical images and reports.  In _Computer Vision–ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23–27, 2022, Proceedings, Part XXVI_ , 2022.
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever.  Learning Transferable Visual Models From Natural Language Supervision.  In _Proceedings of the 38th International Conference on Machine Learning_ , 2021.
  * (23) Joshua David Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive learning with hard negative samples.  In _International Conference on Learning Representations_.
  * Sadvilkar and Neumann (2020) Nipun Sadvilkar and Mark Neumann.  PySBD: Pragmatic Sentence Boundary Disambiguation.  In _Proceedings of Second Workshop for NLP Open Source Software (NLP-OSS)_ , 2020.
  * Salazar et al. (2020) Julian Salazar, Davis Liang, Toan Q. Nguyen, and Katrin Kirchhoff.  Masked Language Model Scoring.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , 2020.
  * Saunshi et al. (2019) Nikunj Saunshi, Orestis Plevrakis, Sanjeev Arora, Mikhail Khodak, and Hrishikesh Khandeparkar.  A Theoretical Analysis of Contrastive Unsupervised Representation Learning.  In _Proceedings of the 36th International Conference on Machine Learning_ , 2019.
  * van den Oord et al. (2018) Aäron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation Learning with Contrastive Predictive Coding.  _ArXiv_ , 2018.
  * van der Maaten and Hinton (2008) Laurens van der Maaten and Geoffrey Hinton.  Visualizing Data using t-SNE.  _Journal of Machine Learning Research_ , 2008.
  * Wang et al. (2023) Peiqi Wang, William M. Wells, Seth Berkowitz, Steven Horng, and Polina Golland.  Using Multiple Instance Learning to Build Multimodal Representations.  In _Information Processing in Medical Imaging: 27th International Conference, IPMI 2021, San Carlos De Bariloche, Argentina, June 18–June 23, 2023, Proceedings_ , 2023.
  * Wang et al. (2022) Yuyang Wang, Rishikesh Magar, Chen Liang, and Amir Barati Farimani.  Improving Molecular Contrastive Learning via Faulty Negative Mitigation and Decomposed Fragment Contrast.  _Journal of Chemical Information and Modeling_ , 2022.
  * Zhang et al. (2022a) Shiwei Zhang, Jichao Sun, Yu Huang, Xueqi Ding, and Yefeng Zheng.  Medical Symptom Detection in Intelligent Pre-Consultation Using Bi-directional Hard-Negative Noise Contrastive Estimation.  In _Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining_ , 2022a.
  * Zhang et al. (2022b) Yuhao Zhang, Hang Jiang, Yasuhide Miura, Christopher D. Manning, and Curtis P. Langlotz.  Contrastive Learning of Medical Visual Representations from Paired Images and Text.  In _Proceedings of Machine Learning Research_ , 2022b.
  * Zheng et al. (2021) Mingkai Zheng, Fei Wang, Shan You, Chen Qian, Changshui Zhang, Xiaogang Wang, and Chang Xu.  Weakly Supervised Contrastive Learning.  In _2021 IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * Zhou et al. (2022) Kun Zhou, Beichen Zhang, Xin Zhao, and Ji-Rong Wen.  Debiased Contrastive Learning of Unsupervised Sentence Representations.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , 2022.

##  Appendix A Theoretical Results

In this section. We use use $g_{0}$ to denote the estimator in Equation 7

$\displaystyle
g_{0}(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})\triangleq\frac{1}{1-\eta(x)}\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\eta(x)\frac{1}{M}\sum_{m=1}^{M}e^{(x,v_{m})}\right)$
(10)

and
$g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})=\max(g_{0}(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\}),e^{-\gamma^{2}})$
as the version of estimator lower bounded by its theoretical minimum.

###  A.1 Proof for Proposition 2.1

######  Proof A.1.

The goal is to show how well debiased contrasive loss $\mathcal{L}$
approximates the asymptotic debiased contrastive loss $\tilde{\mathcal{L}}$.
Without loss of generality, we assume $\gamma=1$. The proof holds as long as
$s$ is bounded. For simplicity, we assume
$s(x,x^{\prime})=f(x)^{T}f(x^{\prime})$, implying $s(x)\in[-1,1]$.

Let $\varepsilon>0$ and $x,x^{+}\in\mathcal{X}$ be arbitrary. We are
interested in the tail probability of the difference between the integrands of
$\mathcal{L}$ and $\tilde{\mathcal{L}}$, i.e.,
$\mathbb{P}(\triangle\geq\varepsilon)$ where

$\displaystyle\triangle=\left|-\log\frac{e^{s(x,x^{+})}}{e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})}+\log\frac{e^{s(x,x^{+})}}{e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]}\right|.$

Note, $\triangle$ implicitly depends on $x,x^{+}$.
$\left\\{u_{n}\right\\},\left\\{v_{m}\right\\}$ are random samples. Now
simplify:

$\displaystyle\mathbb{P}\left(\triangle\geq\varepsilon\right)$
$\displaystyle=\mathbb{P}\left(\left|\log\left(e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})\right)-\log\left(e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\right|\geq\varepsilon\right)$
$\displaystyle=\mathbb{P}\left(\log\left(e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})\right)-\log\left(e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{D}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\geq\varepsilon\right)$
$\displaystyle\quad+\mathbb{P}\left(-\log\left(e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})\right)+\log\left(e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{D}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\geq\varepsilon\right).$

The first term can be bounded, i.e.,

$\displaystyle\mathbb{P}\left(\log\left(e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})\right)-\log\left(e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\geq\varepsilon\right)$
$\displaystyle=\mathbb{P}\left(\log\frac{e^{s(x,x^{+})}+Ng(x,\left\\{u_{n}\right\\}.\left\\{v_{m}\right\\})}{e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]}\geq\varepsilon\right)$
$\displaystyle\leq\mathbb{P}\left(\frac{Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})-N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]}{e^{s(x,x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]}\geq\varepsilon\right)$
( $\log x\leq x-1$ for $x>0$ )
$\displaystyle=\mathbb{P}\left(g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})-\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\geq\varepsilon\left(\frac{1}{N}e^{s(x,x^{+})}+\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\right)$
$\displaystyle\leq\mathbb{P}\left(g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})-\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\geq\varepsilon
e^{-1}\right).$ (
$\frac{1}{N}e^{s(x,x^{+})}+\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\geq\frac{1}{N}e^{-1}+e^{-1}\geq
e^{-1}$ )

Similarly, the second term is bounded in a similar manner. Since both term can
be bounded,

$\displaystyle\mathbb{P}\left(\triangle\geq\varepsilon\right)$
$\displaystyle\leq\mathbb{P}\left(\left|g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})-\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right|\geq\varepsilon
e^{-1}\right)$
$\displaystyle\leq\mathbb{P}\left(\left|g_{0}(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})-\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right|\geq\varepsilon
e^{-1}\right).$ (for any $b\geq e^{-1}$, $|\max(a,e^{-1})-b|\leq|a-b|$ )

We decompose the term inside the absolute value into 3 terms:

$\displaystyle
g_{0}(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})-\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{s(x,x^{-})}\right]$
$\displaystyle=\frac{1}{1-\eta(x)}\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\eta(x)\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}\right)$
$\displaystyle\quad-\frac{1}{1-\rho(c_{x})}\left(\mathbb{E}_{x^{-}\sim\mathcal{D}}\left[e^{s(x,x^{-})}\right]-\rho(c_{x})\mathbb{E}_{x^{-}\sim\mathcal{D}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)$
$\displaystyle=\frac{1}{1-\rho(c_{x})}\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\mathbb{E}_{x^{-}\sim\mathcal{D}}\left[e^{(x,x^{-})}\right]\right)+\frac{\rho(c_{x})}{1-\rho(c_{x})}\left(\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}-\mathbb{E}_{x^{-}\sim\mathcal{D}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)$
$\displaystyle\quad+\left(\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right)\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}\right).$

Continue where we left off,

$\displaystyle\mathbb{P}\left(\triangle\geq\varepsilon\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\frac{1}{1-\rho(c_{x})}\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\mathbb{E}_{x^{-}\sim\mathcal{D}}\left[e^{s(x,x^{-})}\right]\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right)$
$\displaystyle\quad+\mathbb{P}\left(\left|\frac{\rho(c_{x})}{1-\rho(c_{x})}\left(\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}-\mathbb{E}_{x^{-}\sim\mathcal{D}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right)$
$\displaystyle\quad+\mathbb{P}\left(\left|\left(\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right)\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right).$

Hoeffding’s Inequality states that given indepedent bounded random variable
$Z_{1},\cdots,Z_{n}$ where $Z_{i}\in[a,b]$ for all $i$, then
$\mathbb{P}(|\frac{1}{n}\sum_{i=1}^{n}Z_{i}-\mathbb{E}\left[Z_{i}\right]|\geq
t)\leq 2\exp(-2nt^{2}/(b-a)^{2})$. Since $e^{-1}\leq e^{s(x,x^{\prime})}\leq
e$ for all $x^{\prime}\in\mathcal{X}$, the first two terms can be bounded by
Hoeffding’s Inequality

$\displaystyle\mathbb{P}\left(\left|\frac{1}{1-\rho(c_{x})}\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\mathbb{E}_{x^{-}\sim\mathcal{D}}\left[e^{s(x,x^{-})}\right]\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right)$ $\displaystyle\leq
2\exp\left(-\frac{2N\varepsilon^{2}}{9e^{4}}\left(1-\rho(c_{x})\right)^{2}\right),$
$\displaystyle\mathbb{P}\left(\left|\frac{\rho(c_{x})}{1-\rho(c_{x})}\left(\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}-\mathbb{E}_{x^{-}\sim\mathcal{D}_{c_{x}}}\left[e^{s(x,x^{-})}\right]\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right)$ $\displaystyle\leq
2\exp\left(-\frac{2M\varepsilon^{2}}{9e^{4}}\left(\frac{1-\rho(c_{x})}{\rho(c_{x})}\right)^{2}\right).$

The last term can be upper bounded with an indicator

$\displaystyle\mathbb{P}\left(\left|\left(\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right)\left(\frac{1}{N}\sum_{n=1}^{N}e^{s(x,u_{n})}-\frac{1}{M}\sum_{m=1}^{M}e^{s(x,v_{m})}\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right)$
$\displaystyle\leq\mathbb{P}\left(\left|\left(\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right)\left(e-e^{-1}\right)\right|\geq\frac{\varepsilon
e^{-1}}{3}\right)$ $\displaystyle\leq\mathbbm{1}\left\\{\varepsilon\leq
3e^{2}\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right\\}.$

Combine these 3 upper bounds together we have

$\displaystyle\mathbb{P}\left(\triangle\geq\varepsilon\right)$
$\displaystyle\leq
2\exp\left(-\frac{2N\varepsilon^{2}}{9e^{4}}\left(1-\rho(c_{x})\right)^{2}\right)+2\exp\left(-\frac{2M\varepsilon^{2}}{9e^{4}}\left(\frac{1-\rho(c_{x})}{\rho(c_{x})}\right)^{2}\right)$
$\displaystyle\quad+\mathbbm{1}\left\\{\varepsilon\leq
3e^{2}\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right\\}.$

Now we bound the approximation error using the tail probability we just
derived.

$\displaystyle\left|\tilde{\mathcal{L}}-\mathcal{L}\right|$
$\displaystyle\leq\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[\triangle\right]$
(Jensen’s Inequality)
$\displaystyle=\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[\mathbb{E}\left[\triangle\mid
x,x^{+}\right]\right]$
$\displaystyle=\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[\int_{0}^{\infty}\mathbb{P}\left(\triangle\geq\varepsilon\mid
x,x^{+}\right)\,d\varepsilon\right]$ (Write $\mathbb{E}$ using CDF)
$\displaystyle\leq\mathbb{E}_{x\sim\mathcal{D}}\left[\int_{0}^{\infty}2\exp\left(-\frac{2N\varepsilon^{2}}{9e^{4}}\left(1-\rho(c_{x})\right)^{2}\right)\,d\varepsilon\right]$
$\displaystyle\quad+\mathbb{E}_{x\sim\mathcal{D}}\left[\int_{0}^{\infty}2\exp\left(-\frac{2M\varepsilon^{2}}{9e^{4}}\left(\frac{1-\rho(c_{x})}{\rho(c_{x})}\right)^{2}\right)\,d\varepsilon\right]$
$\displaystyle\quad+\mathbb{E}_{x\sim\mathcal{D}}\left[\int_{0}^{\infty}\mathbbm{1}\left\\{\varepsilon\leq
3e^{2}\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right\\}\,d\varepsilon\right]$
$\displaystyle=3e^{2}\sqrt{\frac{\pi}{2N}}\mathbb{E}_{x\sim\mathcal{D}}\left[\frac{1}{1-\rho(c_{x})}\right]+3e^{2}\sqrt{\frac{\pi}{2M}}\mathbb{E}_{x\sim\mathcal{D}}\left[\frac{\rho(c_{x})}{1-\rho(c_{x})}\right]$
$\displaystyle\quad+3e^{2}\mathbb{E}_{x\sim\mathcal{D}}\left[\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right].$
(Use identity
$\int_{0}^{\infty}e^{-cz^{2}}\,dz=\frac{1}{2}\sqrt{\frac{\pi}{c}}$)

###  A.2 Classification Generalization Bounds

To show relationship between the different loss functions, we re-define the
losses to show their dependence on the encoder $f$ and some additional
parameters

$\displaystyle\tilde{\mathcal{L}}(f,Q)$
$\displaystyle\triangleq\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[-\log\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+Q\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{f(x)^{T}f(x^{-})}\right]}\right],$
(11) $\displaystyle\mathcal{L}(f,N,M)$
$\displaystyle\triangleq\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}},\\{u_{n}\\}\sim\mathcal{D}^{N},\\{v_{m}\\}\sim\mathcal{D}_{c_{x}}^{M}}\left[-\log\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})}\right]$
(12)

where the similarity function is dot product, i.e.,
$s(x,x^{\prime})=f(x)^{T}f(x^{\prime})$.

Following Saunshi et al. (2019); Chuang et al. (2020), we characterize a
representation $f$ on $K$-way classification task $\mathcal{T}$ consisting of
$K$ classes $\left\\{c_{1},\cdots,c_{K}\right\\}\subset\mathcal{C}$. The
supervised dataset is generated from
$\mathcal{D}_{\mathcal{T}}(x,c)\propto\mathcal{D}_{c}(x)\rho(c)$.
Specifically, we fix the representations and train a linear classifier
$h(x)\triangleq Wf(x)$ on task $\mathcal{T}$ with softmax cross entropy loss
$\mathcal{L}_{\text{softmax}}(\mathcal{T},h)$. The supervised loss for
classifier $h$ on task $\mathcal{T}$ is

$\displaystyle\mathcal{L}_{\text{sup}}(\mathcal{T},h)\triangleq\min_{W\in\mathbb{R}^{K\times
D}}\mathcal{L}_{\text{softmax}}(\mathcal{T},h).$ (13)

We focus on the supervised loss of the mean classifier, where rows of $W$ are
the means of the representations of inputs with label $c$, i.e.,
$W_{\mu}\triangleq\begin{bmatrix}\mu_{1},\cdots,\mu_{K}\end{bmatrix}^{T}$
where $\mu_{c}=\mathbb{E}_{x\in\mathcal{D}_{c}}\left[f(x)\right]$. The
supervised loss for the mean classifier is

$\displaystyle\mathcal{L}_{\text{sup}-\mu}(\mathcal{T},f)\triangleq\mathcal{L}_{\text{sup}}(\mathcal{T},W_{\mu}f)=\mathbb{E}_{(x,c)\sim\mathcal{D}_{\mathcal{T}}}\left[-\log\frac{e^{f(x)^{T}\mu_{c}}}{\sum_{c^{-}\in\mathcal{T}}e^{f(x)^{T}\mu_{c^{-}}}}\right].$
(14)

We consider the average classification performance over the distribution of
$K$-way multi-class classification tasks
$p_{\mathcal{T}}(\left\\{c_{i}\right\\}_{k=1}^{K})\propto\prod_{k=1}^{K}\rho(c_{i})\cdot\mathbbm{1}\left[c_{i}\neq
c_{j}\,\forall i\neq j\right]$. The average supervised loss over tasks is

$\displaystyle\mathcal{L}_{\text{sup}}(f)\triangleq\mathbb{E}_{\mathcal{T}\sim
p_{\mathcal{T}}}\mathcal{L}_{\text{sup}}(\mathcal{T},f).$ (15)

The following lemma bounds the supervised loss $\mathcal{L}_{\text{sup}}$ with
the asymptotic contrastive loss $\mathcal{L}$.

######  Lemma A.2.

For any encoder $f$, whenever
$N\geq\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}$ where
$\rho_{\text{min}}\triangleq\min_{c\in\mathcal{C}}\rho(c)$, we have

$\displaystyle\mathcal{L}_{\text{sup}}(f)\leq\mathcal{L}_{\text{sup}-\mu}(f)\leq\tilde{\mathcal{L}}(f,N)$
(16)

######  Proof A.3.

We first show that $N=\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}$ gives the
smallest loss:

$\displaystyle\tilde{\mathcal{L}}(f,N)$
$\displaystyle=\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[-\log\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+N\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{f(x)^{T}f(x^{-})}\right]}\right]$
(17)
$\displaystyle\geq\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[-\log\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{f(x)^{T}f(x^{-})}\right]}\right]$
(18)
$\displaystyle=\tilde{\mathcal{L}}\left(f,\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\right).$
(19)

The task-specific class distribution is
$\rho_{\mathcal{T}}(\left\\{c_{k}\right\\})\propto\prod_{k=1}^{K}\rho(c_{k})$.
Now we show the asymptotic debiased loss upper bounds the supervised
classification loss:

$\displaystyle\tilde{\mathcal{L}}\left(f,\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\right)$
(20)
$\displaystyle=\mathbb{E}_{(x,x^{+})\sim\mathcal{D}_{\text{sim}}}\left[-\log\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\mathbb{E}_{x^{-}\sim\mathcal{E}_{c_{x}}}\left[e^{f(x)^{T}f(x^{-})}\right]}\right]$
(21) $\displaystyle=\mathbb{E}_{\mathcal{T}\sim
p_{\mathcal{T}},c\sim\rho_{\mathcal{T}},x,x^{+}\sim\mathcal{D}_{c}^{2}}\left[-\log\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\mathbb{E}_{\mathcal{T}\sim
p_{\mathcal{T}},c^{-}\sim\rho_{\mathcal{T}}(\cdot\mid c^{-}\neq
c),x^{-}\sim\mathcal{D}_{c^{-}}}\left[e^{f(x)^{T}f(x^{-})}\right]}\right]$
(22) $\displaystyle\geq\mathbb{E}_{\mathcal{T}\sim
p_{\mathcal{T}},(x,c)\sim\mathcal{D}_{\mathcal{T}}}\left[-\log\frac{e^{f(x)^{T}\mu_{c^{+}}}}{e^{f(x)^{T}\mu_{c^{+}}}+\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\mathbb{E}_{c^{-}\sim\rho_{\mathcal{T}}(\cdot\mid
c^{-}\neq c)}\left[e^{f(x)^{T}\mu_{c^{-}}}\right]}\right]$ (Jensen’s
Inequality) $\displaystyle\geq\mathbb{E}_{\mathcal{T}\sim
p_{\mathcal{T}},(x,c)\sim\mathcal{D}_{\mathcal{T}}}\left[-\log\frac{e^{f(x)^{T}\mu_{c^{+}}}}{e^{f(x)^{T}\mu_{c^{+}}}+\sum_{c^{-}\in\mathcal{T}:c^{-}\neq
c}e^{f(x)^{T}\mu_{c^{+}}}}\right]$
($\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}\geq\frac{\sum_{c_{k}:c_{k}\neq
c}\rho(c_{k})}{\rho(c^{-})}$ for any
$c^{-},c_{1},\cdots,c_{K}\in\mathcal{C}^{K+1}$)
$\displaystyle=\mathcal{L}_{\text{sup}-\mu}(f).$ (23)

We have showed the second inequality in the Lemma. The first inequality
follows from the definition of $\mathcal{L}_{\text{sup}}$, i.e.,
$\mathcal{L}_{\text{sup}}$ is the minimal loss over all weight matrices $W$
including that of the mean classifier $W_{\mu}$.

We wish to derive a data dependent bound. We follow the proof strategy
detailed in Saunshi et al. (2019). We assume that the class-specific
probability function depends on the represerntation, i.e.,
$\eta(x)=\kappa(f(x))$ for some
$\kappa:\mathbb{R}^{D}\to[\eta_{\text{min}},\eta_{\text{max}}]$. This
assumption is introduced to use theoretical results from prior work; We leave
generalization to arbitrary $\eta$ to future work. First, we express the
debiased contrastive loss in an alternative form:

$\displaystyle\mathcal{L}(f,N,M)=\mathbb{E}_{(x,x^{+}\sim\mathcal{D}_{\text{sim}}),\left\\{u_{n}\right\\}\sim\mathcal{D}^{N},\left\\{v_{m}\right\\}\sim\mathcal{D}_{c_{x}}^{M}}\left[\ell\left(\phi(f(x),f(x^{+}),\left\\{f(u_{n})\right\\}_{n},\left\\{f(v_{m})\right\\}_{n})\right)\right].$
(24)

In Equation 24, $\phi:\mathbb{R}^{D(M+N+2)}\to\mathbb{R}^{M+N+2}$ computes
some statistics of the representations

$\displaystyle\phi(\overline{x},\overline{x}^{+},\left\\{\overline{u}_{n}\right\\},\left\\{\overline{v}_{m}\right\\})\triangleq\left(\left\\{\overline{x}^{T}(\overline{u}_{n}-\overline{x}^{+})\right\\}_{n},\left\\{\overline{x}^{T}(\overline{v}_{m}-\overline{x}^{+})\right\\}_{m},\overline{x}^{T}\overline{x}^{+},\kappa(\overline{x})\right),$
(25)

In Equation 24, $\ell:\mathbb{R}^{N+M+2}\to\mathbb{R}$ is the loss function

$\displaystyle\ell(\left\\{a_{n}\right\\},\left\\{b_{m}\right\\},c,d)\triangleq\log\left[1+N\max\left(\frac{1}{1-d}\left(\frac{1}{N}\sum_{n=1}^{N}e^{a_{n}}-d\frac{1}{M}\sum_{m=1}^{M}e^{b_{m}}\right),e^{-1-c}\right)\right].$
(26)

We can verify that Equation 24 is correct by noting that the integrand in
Equation 12 can be expressed using a composition of $\ell$ and $\phi$

$\displaystyle-\log\left[\frac{e^{f(x)^{T}f(x^{+})}}{e^{f(x)^{T}f(x^{+})}+Ng(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})}\right]=\log\left[1+N\frac{g(x,\left\\{u_{n}\right\\},\left\\{v_{m}\right\\})}{e^{f(x)^{T}f(x^{+})}}\right]$
(27)
$\displaystyle\quad=\log\Bigg{[}1+N\max\Bigg{\\{}\frac{1}{1-\kappa(f(x))}\left(\frac{1}{N}\sum_{n=1}^{N}e^{f(x)^{T}(f(u_{n})-f(x^{+}))}-\kappa(f(x))\frac{1}{M}\sum_{m=1}^{M}e^{f(x)^{T}(f(v_{m})-f(x^{+}))}\right)$
(28)
$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad,e^{-1-f(x)^{T}f(x^{+})}\Bigg{\\}}\Bigg{]}$
(29)
$\displaystyle\quad=\ell\left(\phi(f(x),f(x^{+}),\left\\{f(u_{n})\right\\}_{n},\left\\{f(v_{m})\right\\}_{n})\right).$
(30)

Given a data set
$\mathcal{S}\triangleq(x_{t},x_{t}^{+},\left(u_{tn}\right)_{n},\left\\{v_{tm}\right\\}_{m})\in\mathcal{D}_{\text{sim}}\times\mathcal{D}^{N}\times\mathcal{D}_{c_{x_{t}}}^{M}$
with $T$ samples, the empirical estimate of the debiased contrastive loss in
Equation 24 is

$\displaystyle\hat{\mathcal{L}}(f,N,M)\triangleq\frac{1}{T}\sum_{t=1}^{T}\ell\left(\phi(f(x_{t}),f(x_{t}^{+}),\left\\{f(u_{tn})\right\\}_{n},\left\\{f(v_{tm})\right\\}_{n})\right).$
(31)

The learning process finds a representation from a function class
$\mathcal{F}$ with bounded norm, i.e.,
$\mathcal{F}\triangleq\left\\{f:\mathcal{X}\to\mathbb{R}^{D}\mid\left\lVert
f(\cdot)\right\rVert\leq 1\right\\}$. For example, $\mathcal{F}$ can contain
all functions that map to unit hypersphere. Specifically, the algorithm finds
the encoder function $\hat{f}$ via empirical risk minimization, i.e.,
$\hat{f}\in\operatorname*{arg\,min}_{f\in\mathcal{F}}\hat{\mathcal{L}}(f,N,M)$.

The following Lemma is a more specific version of Lemma A.2 in Saunshi et al.
(2019), to account for the differences in our definition of $\phi,\ell$ The
goal is to bound the debiased contrastive loss for the risk minimizer
$\hat{f}$.

First we introduce some notations. $\sigma$ are Rademacher random variables.
The restriction of $f$ onto $\mathcal{S}$ is

$\displaystyle
f_{|\mathcal{S}}\triangleq(f_{d}(x_{t}),f_{d}(x_{t}^{+}),\left\\{f_{d}(u_{n})\right\\}_{n},\left\\{f_{d}(v_{m})\right\\}_{m})_{d\in\left[D\right],t\in\left[T\right]}.$
(32)

$\mathcal{R}_{\mathcal{S}}(\mathcal{F})$ is the empirical Rademacher
complexity of the function class $\mathcal{F}$ with respect to the training
data $\mathcal{S}$, i.e.,

$\displaystyle\mathcal{R}_{\mathcal{S}}(\mathcal{F})\triangleq\mathbb{E}_{\sigma\sim\left\\{\pm
1\right\\}^{(M+N+2)DT}}\left[\sup_{f\in\mathcal{F}}\langle\sigma,f_{|\mathcal{S}}\rangle\right].$
(33)

$h:\mathbb{R}^{(M+N+2)D}\to\mathbb{R}$ as $h\triangleq\ell\circ\phi$ is a
function that computes the loss given the embeddings.

######  Lemma A.4.

If $h$ is $L_{h}$-Lipschitz and $\ell$ bounded by $B$. With probability
$1-\delta$, for all $f\in\mathcal{F}$

$\displaystyle\mathcal{L}(\hat{f},N,M)\leq\mathcal{L}(f,N,M)+\mathcal{O}\left(\frac{L_{h}\mathcal{R}_{\mathcal{S}}(\mathcal{F})}{T}+B\sqrt{\frac{\log\left(\frac{1}{\delta}\right)}{T}}\right).$
(34)

Specifically,

$\displaystyle B$ $\displaystyle=\mathcal{O}\left(\log N\right)$ (35)

and $L_{h}=L_{\ell}\cdot L_{\phi}$ where

$\displaystyle L_{\ell}$
$\displaystyle=\mathcal{O}\left(\sqrt{\frac{1}{(1-\eta_{\text{max}})^{2}N}+\frac{\eta_{\text{max}}^{2}}{(1-\eta_{\text{max}})^{2}M}+\frac{1}{(1-\eta_{\text{max}})^{4}}}\right),$
(36) $\displaystyle L_{\phi}$
$\displaystyle=\mathcal{O}\left(\sqrt{N+M+\left\lVert\nabla\kappa\right\rVert_{2}^{2}}\right).$
(37)

######  Proof A.5.

The first part of the Lemma is simply Lemma A.2 in Saunshi et al. (2019)
without computing the Lipschitz constant for their definition of
$\phi^{\prime}(\overline{x},\overline{x}^{+},\left\\{\overline{x}_{n}^{-}\right\\}_{n})=(\overline{x}^{T}(\overline{x}_{n}^{-}-\overline{x}^{+}))_{n}$.
We refer reader to Saunshi et al. (2019) for more details.

Note $\ell$ in Equation 26 is lower bounded by $\log(1)=0$. Note
$a_{n},b_{m}\in[-2,2]$, $c\in[-1,1]$, and
$d\in[\eta_{\text{min}},\eta_{\text{max}}]$. By plugging in $a_{n}=2$,
$b_{m}=2$, $c=-1$, and $d=\eta_{\text{max}}$, the upper bound of $\ell$ is

$\displaystyle\ell(\left\\{a_{n}\right\\},\left\\{b_{m}\right\\},c,d)\leq\log\left(1+N\max\left(\frac{1}{1-\eta_{\text{max}}}\left(e^{2}-\eta_{\text{max}}e^{-2}\right),1\right)\right)=\mathcal{O}(\log
N).$ (38)

Therefore, $B=\mathcal{O}(\log N)$.

To compute the Lipschitz constant for $\ell$, we express $\ell$ as composition
of two functions $\psi,\omega$, i.e., $\ell=\omega\circ\psi$ where
$\psi:\mathbb{R}^{N+M+2}\to\mathbb{R}$ and $\omega:\mathbb{R}\to\mathbb{R}$
are defined as

$\displaystyle\omega(z)$ $\displaystyle=\log(1+Nz),$ (39)
$\displaystyle\psi(\left\\{a_{n}\right\\},\left\\{b_{m}\right\\},c,d)$
$\displaystyle=\max\left(\frac{1}{1-d}\left(\frac{1}{N}\sum_{n=1}^{N}e^{a_{n}}-d\frac{1}{M}\sum_{m=1}^{M}e^{b_{m}}\right),e^{-1-c}\right).$
(40)

Note $z\geq e^{-1-c}\geq e^{-2}$ due to max in Equation 40. Therefore, we can
bound the Lipschitz constant for $\omega$ with

$\displaystyle
L_{\omega}\leq\left|\frac{d\omega}{dz}\right|\leq\frac{N}{1+Ne^{-2}}\leq
e^{-2}.$ (41)

To bound the Lipschitz constant for $\psi$, we compute the Frobenius norm of
the Jacobian $J_{\psi}$ of $\psi$. We use facts $a_{n},b_{m}\in[-2,2]$,
$c\in[-1,1]$, and $d\in[\eta_{\text{min}},\eta_{\text{max}}]$ to derive upper
bounds to the absolute value of the partial derivatives:

$\displaystyle\left|\frac{\partial\psi}{\partial a_{n}}\right|$
$\displaystyle\leq\frac{e^{a_{n}}}{(1-d)N}\leq\frac{e^{2}}{(1-\eta_{\text{max}})N}\quad\quad
n\in\left[N\right]$ (42) $\displaystyle\left|\frac{\partial\psi}{\partial
b_{m}}\right|$ $\displaystyle\leq\frac{d\cdot
e^{b_{m}}}{(1-d)M}\leq\frac{\eta_{\text{max}}e^{2}}{(1-\eta_{\text{max}})M}\quad\quad
m\in\left[M\right]$ (43) $\displaystyle\left|\frac{\partial\psi}{\partial
c}\right|$
$\displaystyle=\frac{1}{(1-d)^{2}}\left(\frac{1}{N}\sum_{n=1}^{N}e^{a_{n}}-\frac{1}{M}\sum_{m=1}^{M}e^{b_{m}}\right)\leq\frac{e}{(1-\eta_{\text{max}})^{2}}$
(44) $\displaystyle\left|\frac{\partial\psi}{\partial d}\right|$
$\displaystyle\leq e^{-1-c}\leq 1.$ (45)

We use the Frobeninus norm of the Jacobnian to bound the Lipschitz constant

$\displaystyle L_{\psi}\leq\left\lVert J_{\psi}\right\rVert_{2}\leq\left\lVert
J_{\psi}\right\rVert_{F}\leq\sqrt{\sum_{n=1}^{N}\frac{e^{4}}{(1-\eta_{\text{max}})^{2}N^{2}}+\sum_{m=1}^{M}\frac{\eta_{\text{max}}^{2}}{(1-\eta_{\text{max}})^{2}M^{2}}+\frac{e^{2}}{(1-\eta_{\text{max}})^{4}}+1}.$
(46)

Combine Lipschitz constants $L_{\omega}$ in Equation 41 and $L_{\psi}$ in
Equation 46, a Lipschitz constant $L_{\ell}=L_{\omega}\cdot L_{\psi}$ for
$\ell$ in Equation 36 follows directly.

To compute a Lipschitz constant for $\phi$, we use similar tactic as previous
by computing the Jacobnian $J_{\phi}$ of $\phi$. We first expand out the inner
products in Equation 25,

$\displaystyle\phi(\overline{x},\overline{x}^{+},\left\\{\overline{u}_{n}\right\\},\left\\{\overline{v}_{m}\right\\})=\left(\left\\{\sum_{d}\overline{x}_{d}(\overline{u}_{dn}-\overline{x}^{+}_{d})\right\\}_{n},\left\\{\sum_{d}\overline{x}_{d}(\overline{v}_{dm}-\overline{x}^{+}_{d})\right\\}_{m},\sum_{d}\overline{x}_{d}\overline{x}_{d}^{+},\kappa(\overline{x})\right).$
(47)

The partial derivatives of this vector-valued function $\phi$, given
$d\in\left[D\right]$, are

$\displaystyle\frac{\partial\phi_{i}}{\partial\overline{x}_{d}}$
$\displaystyle=\begin{cases}(\overline{u}_{di}-\overline{x}^{+}_{d})&i\in\left[N\right]\\\
(\overline{v}_{d(i-N)}-\overline{x}^{+}_{d})&i=N+1,\cdots,N+M\\\
\overline{x}^{+}_{d}&i=N+M+1\\\
\frac{\partial\kappa}{\partial\overline{x}_{d}}&i=N+M+2\end{cases}$ (48)
$\displaystyle\frac{\partial\phi_{i}}{\partial\overline{x}^{+}_{d}}$
$\displaystyle=\begin{cases}-\overline{x}_{d}&i\in[N+M]\\\
\overline{x}_{d}&i=N+M+1\\\ 0&\text{o.w.}\end{cases}$ (49)
$\displaystyle\frac{\partial\phi_{i}}{\partial\overline{u}_{dj}}$
$\displaystyle=\begin{cases}\overline{x}_{d}&i=j,j\in\left[N\right]\\\
0&\text{o.w.}\\\ \end{cases}$ (50)
$\displaystyle\frac{\partial\phi_{i}}{\partial\overline{v}_{dj}}$
$\displaystyle=\begin{cases}\overline{x}_{d}&i=j+N,j\in[M]\\\ 0&\text{o.w.}\\\
\end{cases}.$ (51)

We use the Frobenius norm of the Jacobian to bound the Lipschitz constant

$\displaystyle L_{\phi}$ $\displaystyle\leq\left\lVert
J_{\phi}\right\rVert_{2}\leq\left\lVert J_{\phi}\right\rVert_{F}$ (52)
$\displaystyle\leq\sqrt{\begin{aligned}
\sum_{i=1}^{N}\sum_{d}(\overline{u}_{di}-\overline{x}_{d}^{+})^{2}+\sum_{i=N+1}^{N+M}\sum_{d}(\overline{v}_{d(i-N)}-\overline{x}_{d}^{+})^{2}+\sum_{d}(\overline{x}_{d}^{+})^{2}+\\\
\sum_{d}\left(\frac{\partial\kappa}{\partial\overline{x}_{d}}\right)^{2}+(N+M)\sum_{d}(\overline{x}_{d})^{2}+\sum_{d}(\overline{x}_{d})^{2}+N\sum_{d}(\overline{x}_{d})^{2}+M\sum_{d}(\overline{x}_{d})^{2}\end{aligned}}$
(53)
$\displaystyle\leq\sqrt{4N+4M+1+\left\lVert\nabla\kappa\right\rVert_{2}^{2}+(N+M)+1+N+M}$
(54)
$\displaystyle=\mathcal{O}\left(\sqrt{N+M+\left\lVert\nabla\kappa\right\rVert_{2}^{2}}\right)$
(55)

Here, norm of representations is bounded, i.e.,
$\left\lVert\overline{x}\right\rVert_{2},\left\lVert\overline{x}^{+}\right\rVert_{2},\left\lVert\overline{u}_{n}\right\rVert_{2},\left\lVert\overline{v}_{m}\right\rVert_{2}\leq
1$.

We can compute a Lipschitz constant for $h$ by multiplying that for
$\ell,\phi$, i.e., $L_{h}=L_{\ell}\cdot L_{\phi}$.

The following theorem provides the generalization bounds on classification
tasks.

######  Theorem A.6.

With probability at least $1-\delta$, for all $f\in\mathcal{F}$, and
$N\geq\frac{1-\rho_{\text{min}}}{\rho_{\text{min}}}$,

$\displaystyle\mathcal{L}_{\text{sup}}(\hat{f})\leq\mathcal{L}(f,N,M)+\mathcal{O}\left(\sqrt{\frac{1}{M}}+\sqrt{\frac{1}{N}}+\mathbb{E}_{x\sim\mathcal{D}}\left[\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right]+\frac{L_{h}\mathcal{R}_{\mathcal{S}}(\mathcal{F})}{T}+B\sqrt{\frac{\log(\frac{1}{\delta})}{T}}\right)$
(56)

######  Proof A.7.

Simply combine the results that we proved so far gives us the result

$\displaystyle\mathcal{L}_{\text{sup}}(\hat{f})$
$\displaystyle\leq\tilde{\mathcal{L}}(\hat{f},N)$ ( Use Lemma A.2 )
$\displaystyle\leq\mathcal{L}(\hat{f},N,M)+\mathcal{O}\left(\sqrt{\frac{1}{M}}+\sqrt{\frac{1}{N}}+\mathbb{E}_{x\sim\mathcal{D}}\left[\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right]\right)$
( Use Proposition 2.1 )
$\displaystyle\leq\mathcal{L}(f,N,M)+\mathcal{O}\left(\sqrt{\frac{1}{M}}+\sqrt{\frac{1}{N}}+\mathbb{E}_{x\sim\mathcal{D}}\left[\left|\frac{1}{1-\eta(x)}-\frac{1}{1-\rho(c_{x})}\right|\right]+\frac{L_{h}\mathcal{R}_{\mathcal{S}}(\mathcal{F})}{T}+B\sqrt{\frac{\log(\frac{1}{\delta})}{T}}\right).$
( Use Lemma A.4 )

This bound states that if (i) the function class $\mathcal{F}$ is sufficiently
rich (i.e., contains some encoder function for which $\mathcal{L}(f,N,M)$ is
small), (ii) trained over large data (i.e., $T$ is large), (iii) the number of
negatives sampled is large (i.e., large $N,M$), and (iv) $\eta$ provides a
good estimate of sample-specific class probabilities, then the encoder
$\hat{f}$ will perform well on the downstream classification tasks.

##  Appendix B Additional Details for Experiments

Label | Negative Prompt | Positive Prompt
---|---|---
pneumonia | “No signs of pneumonia” | “Findings suggesting pneumonia”
cardiomegaly | “Heart size normal” | “Cardiomegaly”
edema | “No pulmonary edema” | “Pulmonary edema”
effusion | “No pleural effusions” | “Pleural effusions”
pneumothorax | “No pneumothorax” | “Pneumothorax”
Table 2: Zero-shot image classification prompts.

##  Appendix C Additional Results

Figure 4: t-SNE visualization of learned representations on CIFAR10-0.1. Subsampled classes are in shades of red and the remaining classes are in shades of blue. Using the true sample-specific class probability function (DCL-$\eta_{\text{True}}$) leads to better class separation than both contrastive learning (CL) and using the incorrect sample-specific class probability function (DCL-$\eta_{\text{High}}$), especially for the subsampled classes.  Method |  Cardiomegaly |  Edema |  Effusion |  Pneumonia |  Pneumothorax |  Avg |
---|---|---|---|---|---|---|---
BioViL |  0.752 |  0.887 |  0.914 |  0.768 |  0.594 |  0.783 |
LSE+NL |  0.888 |  0.876 |  0.798 |  0.853 |  0.526 |  0.788 |
w/ DCL-$\eta_{\text{LM}}$ |  0.884 |  0.889 |  0.913 |  0.861 |  0.760 |  0.862 |
Table 3: Zero-shot image classification performance. We report the AUC for 5 common radiology findings and their average (Avg) on CheX5 data set. Image-text model trained with our method outperforms state-of-the-art baselines.  Method |  CNR$\uparrow$ |  mIoU$\uparrow$ |
---|---|---|---
BioViL |  1.142 |  0.174 |
LSE+NL |  1.400 |  0.190 |
w/ DCL-$\eta_{\text{LM}}$ |  1.486 |  0.195 |
Table 4: Visual grounding performance. We report a measure of the discrepancy between region-sentence scores inside and outside the ground truth bounding box (contrast-to-noise ratio or CNR) and the mean IoU of a thresholded region-sentence map and the ground truth bounding box over a set of threshold (mIoU). Image-text model trained with our method outperforms BioViL and LSE+NL on both measures. Method |  Image $\rightarrow$ Text |  Text $\rightarrow$ Image |
---|---|---|---
|  R@10 $\uparrow$ |  R@50 $\uparrow$ |  R@100 $\uparrow$ |  MedR$\downarrow$ |  R@10 $\uparrow$ |  R@50 $\uparrow$ |  R@100 $\uparrow$ |  MedR$\downarrow$ |
BioViL |  0.07 |  0.26 |  0.40 |  151 |  0.08 |  0.26 |  0.40 |  146 |
LSE+NL |  0.09 |  0.29 |  0.44 |  123 |  0.10 |  0.32 |  0.49 |  107 |
w/ DCL-$\eta_{\text{LM}}$ |  0.10 |  0.31 |  0.48 |  106 |  0.10 |  0.33 |  0.50 |  102 |
Table 5: Cross-modal retrieval performance. We report recall for the top 10,
50 and 100 answers returned by the method (R@k), as well as the median rank of
the ground truth element for sentence retrieval based on region queries and
for region retrieval based on sentence queries (MedR). Our method improves the
baselines.