# Ensemble Kalman Inversion for General Likelihoods

Samuel Duffield 111Corresponding author<EMAIL_ADDRESS>Sumeetpal S. Singh
Department of Engineering, University of Cambridge, CB2 1PZ, UK

###### Abstract

In this letter we generalise Ensemble Kalman inversion techniques to general
Bayesian models where previously they were restricted to additive Gaussian
likelihoods - all in the difficult setting where the likelihood can be sampled
from, but its density not necessarily evaluated.

###### keywords:

Ensemble Kalman Inversion , Approximate Bayesian Computation , Bayesian
Inference , Intractable Likelihoods

##  1 Introduction

Approximate Bayesian computation (ABC) refers to a collection of Monte Carlo
methods for inference in Bayesian models

$x\sim p(x),\qquad y\sim p(y\mid x),$ (1)

where $x$ is an unknown parameter to be inferred, $y$ is some data that is
known, $p(x)$ is a prior distribution and $p(y\mid x)$ is a likelihood
function describing the data generating process. With ABC, we have the further
restriction that the likelihood function cannot be evaluated pointwise and
therefore the likelihood is said to be intractable \- this rules out classical
techniques such as Markov chain Monte Carlo (MCMC) or importance sampling.
Instead, ABC techniques rely on the ability to simulate synthetic data from
the likelihood $y^{(i)}\sim p(y\mid x^{(i)})$. Here the superscript indicates
that $(x^{(i)},y^{(i)})$ are the $i$th pair from a collection of $N$
parameter-simulated data pairs $\\{(x^{(i)},y^{(i)})\\}_{i=1}^{N}$.

The majority of ABC techniques have focused on adapting classical techniques
to target an extended distribution that can be sampled from without evaluating
the likelihood. Simulated data $\\{y^{(i)}\\}_{i=1}^{N}$ can then be compared
to the true observed data $y$ and subsequently only those parameter values
$\\{x^{(i)}\\}_{i=1}^{N}$ with generated data sufficiently close to the true
data are retained (where the measure of closeness is typically defined by a
combination of summary statistics, distance function and tolerance level).
Popular ABC variants are based on rejection sampling (Pritchard et al., 1999),
MCMC (Marjoram et al., 2003) or sequential Monte Carlo (SMC) (Jasra et al.,
2011), whilst there have also been approaches to incorporate machine learning
techniques (Lueckmann et al., 2019) and alternative posteriors (Matsubara et
al., 2021). For a thorough review of ABC techniques, see Beaumont (2019). ABC
methods are asymptotically biased, however this bias is typically quantifiable
and controllable (at the expense of further computational cost).

This setting of intractable likelihoods is challenging. As yet, ABC methods
have been restricted to relatively low-dimensional Bayesian models and are
renowned for requiring many likelihood simulations and therefore long run-
times. The development of efficient and scalable ABC methods remains a
prominent research goal.

In contrast, ensemble Kalman techniques (Evensen, 1994; Iglesias et al., 2013)
are a class of Monte Carlo algorithms that have become very popular for
inference in high-dimensional models with the restriction of additive Gaussian
likelihoods

$x\sim p(x),\qquad y\sim\mathbf{N}(y\mid\mathcal{H}(x),\mathrm{R}),$ (2)

where $\mathcal{H}$ a deterministic forward operator and $\mathrm{R}$ a noise
covariance matrix which are both assumed known. As noted in Nott et al.
(2012), ensemble Kalman methods make no use of likelihood evaluations and
therefore they are themselves ABC techniques in the specific setting of
additive Gaussian noise (2).

In this letter, we remove this restriction and apply ensemble Kalman
techniques to general likelihoods (1). Thus developing an extremely general
algorithm for inference in Bayesian models with intractable likelihoods that
can perform well even with few likelihood simulations and is scalable to
higher dimensions compared to conventional ABC techniques. The rest of the
letter is structured as follows. Section 2 provides a brief account of
existing ensemble Kalman techniques. We then introduce our generalised
ensemble Kalman method in Section 3 before examining its performance
numerically for both optimisation and uncertainty quantification in Section 4.
Section 5 concludes and discusses future work.

##  2 Ensemble Kalman Approach

Ensemble Kalman techniques were first introduced (Evensen, 1994) for
generating online Monte Carlo approximations for state-space models.

For simplicity, let us consider the offline setting of (2) where where the
likelihood takes the form $p(y\mid
x)=\mathbf{N}(y\mid\mathcal{H}(x),\mathrm{R})$ with $x\in\mathbb{R}^{d_{x}}$
and $y\in\mathbb{R}^{d_{y}}$. Then a single update step of the ensemble Kalman
filter as described in Houtekamer and Mitchell (2001) takes the form

$\displaystyle\begin{split}x_{1}^{(i)}&=x_{0}^{(i)}+\mathrm{C}^{x\mathrm{H}}_{0}\left(\mathrm{C}^{\mathrm{HH}}_{0}+\mathrm{R}\right)^{-1}(y-\mathcal{H}(x_{0}^{(i)})-\eta^{(i)}),\\\
\eta^{(i)}&\sim\mathbf{N}(\eta\mid 0,\mathrm{R}),\end{split}$ (3)

with prior samples $x_{0}^{(i)}\sim p(x)$, empirical covariance matrices

$\displaystyle\begin{split}\mathrm{C}^{x\mathrm{H}}_{0}&=\frac{1}{N-1}\sum_{i=1}^{N}(x_{0}^{(i)}-\bar{x}_{0})(\mathcal{H}(x_{0}^{(i)})-\bar{\mathcal{H}}_{0})^{\mathrm{T}},\\\
\mathrm{C}^{\mathrm{HH}}_{0}&=\frac{1}{N-1}\sum_{i=1}^{N}(\mathcal{H}(x_{0}^{(i)})-\bar{\mathcal{H}}_{0})(\mathcal{H}(x_{0}^{(i)})-\bar{\mathcal{H}}_{0})^{\mathrm{T}},\end{split}$
(4)

and empirical means $\bar{x}_{0}=\frac{1}{N}\sum_{i=1}^{N}x_{0}^{(i)}$ and
$\bar{\mathcal{H}}_{0}=\frac{1}{N}\sum_{i=1}^{N}\mathcal{H}(x_{0}^{(i)})$.

This ensemble Kalman update is asymptotically unbiased in the special case of
Gaussian prior $p(x)=\mathbf{N}(x\mid m,\mathrm{Q})$ and linear Gaussian
likelihood $p(y\mid x)=\mathbf{N}(y\mid\mathrm{H}x,\mathrm{R})$ which gives

$\displaystyle p(x,y)$ $\displaystyle=\mathbf{N}\left(\begin{pmatrix}x\\\
y\end{pmatrix}\mid\begin{pmatrix}m\\\
\mathrm{H}m\end{pmatrix},\begin{pmatrix}\mathrm{Q}&\mathrm{QH}^{\mathrm{T}}\\\
\mathrm{HQ}&\mathrm{HQH}^{\mathrm{T}}+\mathrm{R}\end{pmatrix}\right).$ (5)

This model has an analytically tractable posterior distribution $p(x\mid
y)=\mathbf{N}(x\mid m^{y},\mathrm{Q}^{y})$ where

$\displaystyle m^{y}$
$\displaystyle=m+\mathrm{QH}^{\mathrm{T}}\left(\mathrm{HQH}^{\mathrm{T}}+\mathrm{R}\right)^{-1}(y-\mathrm{H}m),$
$\displaystyle\mathrm{Q}^{y}$
$\displaystyle=\mathrm{Q}-\mathrm{QH}^{\mathrm{T}}\left(\mathrm{HQH}^{\mathrm{T}}+\mathrm{R}\right)^{-1}\mathrm{HQ}.$

Outside of this special linear Gaussian case, the ensemble Kalman update (3)
is known to be asymptotically biased. There is however, a vast amount of
empirical evidence demonstrating stability in a variety of complex non-linear
state-space models with a very small number of particles, e.g. Houtekamer et
al. (2005), Roth et al. (2017). In our view, this summarises the ensemble
Kalman paradigm:

Where the term empirically stable represents the ability of the ensemble
$\\{x^{(i)}\\}_{i=1}^{N}$ to cover the true underlying value of the state
without degenerating to a single particle. Naturally, the acceptance of a bias
induced by this paradigm could be extreme in some problems, however as
mentioned, there is still very much a practical desire for these numerically
efficient but biased methods in this difficult setting of intractable
likelihoods.

For non-Gaussian priors and non-linear Gaussian likelihoods (1), the
distribution of particles from a single step ensemble Kalman update may be
quite different from the true posterior. As noted in Iglesias et al. (2013),
this can be mitigated by iterating the ensemble Kalman update in (3). The idea
was refined in Iglesias (2015) to be more in line with the tempered likelihood
approach of SMC samplers (Del Moral et al., 2006; Jasra et al., 2011). This
iterative ensemble Kalman approach is termed ensemble Kalman inversion (EKI)
and a single iterate takes the form

$\displaystyle\begin{split}x_{\ell}^{(i)}&=x_{\ell-1}^{(i)}+\mathrm{C}^{x\mathrm{H}}_{\ell-1}\left(\mathrm{C}^{\mathrm{HH}}_{\ell-1}+h_{\ell}^{-1}\mathrm{R}\right)^{-1}(y-\mathcal{H}(x_{\ell-1}^{(i)})-\eta^{(i)}_{\ell}),\\\
\eta^{(i)}_{\ell}&\sim\mathbf{N}(\eta_{\ell}\mid
0,h_{\ell}^{-1}\mathrm{R}),\end{split}$ (6)

where $\mathrm{C}^{x\mathrm{H}}_{\ell-1}$ and
$\mathrm{C}^{\mathrm{HH}}_{\ell-1}$ are as in (4) applied to the particles
$\\{x_{\ell-1}^{(i)}\\}_{i=1}^{N}$, the subscript indicates the iteration of
the algorithm, i.e. $\ell=0,\dots,L$ where $L$ is the total number of
iterations. The parameter $h_{\ell}^{-1}$ can be considered a stepsize
parameter or equally $h_{\ell}$ as an incremental inverse temperature
parameter. In the fully linear Gaussian case (5), the particles
$\\{x_{\ell}^{(i)}\\}_{i=1}^{N}$ at each step are asymptotically unbiased for
a tempered version of the posterior

$\displaystyle p_{\ell}(x)$ $\displaystyle\propto p(x)p(y\mid
x)^{\lambda_{\ell}}\propto\mathbf{N}(x\mid m_{\ell},\mathrm{Q}_{\ell}),$
$\displaystyle m_{\ell}$
$\displaystyle=m+\mathrm{QH}^{\mathrm{T}}\left(\mathrm{HQH}^{\mathrm{T}}+\lambda_{\ell}^{-1}\mathrm{R}\right)^{-1}(y-\mathrm{H}m),$
(7) $\displaystyle\mathrm{Q}_{\ell}$
$\displaystyle=\mathrm{Q}-\mathrm{QH}^{\mathrm{T}}\left(\mathrm{HQH}^{\mathrm{T}}+\lambda_{\ell}^{-1}\mathrm{R}\right)^{-1}\mathrm{HQ},$

where $\lambda_{\ell}=\sum_{r=1}^{\ell}h_{r}$ is the inverse temperature. The
tempered posterior can also be defined iteratively

$\displaystyle\begin{split}m_{\ell}&=m_{\ell-1}+\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}\left(\mathrm{H}\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}+h_{\ell}^{-1}\mathrm{R}\right)^{-1}(y-\mathrm{H}m_{\ell-1}),\\\
\mathrm{Q}_{\ell}&=\mathrm{Q}_{\ell-1}-\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}\left(\mathrm{H}\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}+h_{\ell}^{-1}\mathrm{R}\right)^{-1}\mathrm{H}\mathrm{Q}_{\ell-1}.\end{split}$
(8)

Thus, iterating for $L$ steps with stepsizes such that
$\lambda_{L}=\sum_{r=1}^{L}h_{r}=1$ obtains particles
$\\{x_{L}^{(i)}\\}_{i=1}^{N}$ that are asymptotically unbiased for the true
posterior in the linear Gaussian case.

Iterating until $\lambda_{L}=1$ is only one possible method of termination,
another approach is to adopt an optimisation style stopping criterion, for
example Iglesias (2015) suggest terminating when the average of the forward
operations $\bar{\mathcal{H}}_{L}$ is suitably close the true data, e.g. when
$(y-\bar{\mathcal{H}}_{L})^{\mathrm{T}}\mathrm{R}^{-1}(y-\bar{\mathcal{H}}_{L})<\tau$
for some stopping parameter $\tau$.

##  3 Generalised Ensemble Kalman Inversion

In this section, we generalise ensemble Kalman inversion to the case where
data is generated according to any likelihood $p(y\mid x)$ rather than the
setting described in Section 2 which is restricted to likelihoods of the form
$\mathbf{N}(y\mid\mathcal{H}(x),\mathrm{R})$. The resulting algorithm only
requires samples from the prior $p(x)$ and the ability to simulate from the
likelihood $p(y\mid x)$ for a given parameter $x$, as in approximate Bayesian
computation. The final particle approximation is asymptotically biased for the
true posterior with the exception of the fully linear Gaussian case (5) and
therefore remains faithful to the ensemble Kalman paradigm.

###  3.1 General Likelihoods

In this more general case, we can no longer form the empirical covariance
matrices in (4) as we do not have access to the deterministic $\mathcal{H}$.
Instead we can form

$\displaystyle\mathrm{C}^{xx}_{\ell}$
$\displaystyle=\frac{1}{N-1}\sum_{i=1}^{N}(x_{\ell}^{(i)}-\bar{x}_{\ell})(x_{\ell}^{(i)}-\bar{x}_{\ell})^{\mathrm{T}},$
(9a) $\displaystyle\mathrm{C}^{xy}_{\ell}$
$\displaystyle=\frac{1}{N-1}\sum_{i=1}^{N}(x_{\ell}^{(i)}-\bar{x}_{\ell})(y_{\ell}^{(i)}-\bar{y}_{\ell})^{\mathrm{T}},$
(9b) $\displaystyle\mathrm{C}^{yy}_{\ell}$
$\displaystyle=\frac{1}{N-1}\sum_{i=1}^{N}(y_{\ell}^{(i)}-\bar{y}_{\ell})(y_{\ell}^{(i)}-\bar{y}_{\ell})^{\mathrm{T}},$
(9c)

and $\mathrm{C}^{yx}_{\ell}=\mathrm{C}^{xy\,\mathrm{T}}_{\ell}$. Here we have
simulated data $y_{\ell}^{(i)}\sim p(\cdot\mid x_{\ell}^{(i)})$ and means
$\bar{x}_{\ell}=\frac{1}{N}\sum_{i=1}^{N}x_{\ell}^{(i)}$,
$\bar{y}_{\ell}=\frac{1}{N}\sum_{i=1}^{N}y_{\ell}^{(i)}$.

In the fully linear Gaussian case (5) or rather the tempered version (2, 8) we
have $\mathrm{C}^{xy}_{\ell}\to\mathrm{HQ}_{\ell}$ and
$\mathrm{C}^{yy}_{\ell}\to\mathrm{HQ}_{\ell}\mathrm{H}^{\mathrm{T}}+\mathrm{R}$.
We now note that we can also calculate

$\displaystyle\mathrm{C}^{y|x}_{\ell}=\mathrm{C}^{yy}_{\ell}-\mathrm{C}^{yx}_{\ell}\mathrm{C}^{xx\,-1}_{\ell}\mathrm{C}^{xy}_{\ell},$
(10)

and observe that in the linear Gaussian case
$\mathrm{C}^{y|x}_{\ell}\to(\mathrm{H}\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}+\mathrm{R})-(\mathrm{H}\mathrm{Q}_{\ell-1})\mathrm{Q}_{\ell-1}^{-1}(\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}})=\mathrm{R}.$
Thus we can use the particles to approximate the covariance of the likelihood
empirically. We therefore adjust the tempered ensemble Kalman iteration (6) to
the following

$\displaystyle x_{\ell}^{(i)}$
$\displaystyle=x_{\ell-1}^{(i)}+\mathrm{C}^{xy}_{\ell-1}\left(\mathrm{C}^{yy}_{\ell-1}+(h_{\ell}^{-1}-1)\mathrm{C}^{y|x}_{\ell-1}\right)^{-1}\left(y-y_{\ell-1}^{(i)}-\eta^{(i)}_{\ell}\right),$
$\displaystyle y_{\ell-1}^{(i)}$ $\displaystyle\sim p(y_{\ell-1}\mid
x_{\ell-1}^{(i)}),$ (11) $\displaystyle\eta^{(i)}_{\ell}$
$\displaystyle\sim\mathbf{N}(\eta\mid
0,(h_{\ell}^{-1}-1)\mathrm{C}^{y|x}_{\ell-1}).$

In the linear Gaussian case and large sample limit, the above ensemble Kalman
move becomes

$\displaystyle x_{\ell}^{(i)}$
$\displaystyle=x_{\ell-1}^{(i)}+\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}\left((\mathrm{H}\mathrm{Q}_{\ell-1}\mathrm{H}^{\mathrm{T}}+\mathrm{R})+(h_{\ell}^{-1}-1)\mathrm{R}\right)^{-1}(y-y_{\ell-1}^{(i)}-\eta^{(i)}_{\ell}),$
$\displaystyle y_{\ell-1}^{(i)}$
$\displaystyle\sim\mathbf{N}(y_{\ell-1}\mid\mathrm{H}x_{\ell-1}^{(i)},\mathrm{R}),$
$\displaystyle\eta^{(i)}_{\ell}$ $\displaystyle\sim\mathbf{N}(\eta_{\ell}\mid
0,(h_{\ell}^{-1}-1)\mathrm{R}).$

Where the $(h_{\ell}^{-1}-1)$ scaling has been chosen to ensure that the
statistics $\mathbb{E}[x_{\ell}^{(i)}]$ and $\textrm{Cov}[x_{\ell}^{(i)}]$
match those in (8). Therefore the ensemble Kalman update in (11) is
asymptotically unbiased in the linear Gaussian case, and consistent with the
ensemble Kalman paradigm. The full procedure is listed in Algorithm 1.

Algorithm 1 Ensemble Kalman Inversion for General Likelihoods

1:Given a sequence of inverse temperatures $\\{\lambda_{\ell}\\}_{\ell=0}^{L}$
and stopping criterion - which may both be adaptive, see Sections 3.2 and 3.3.

2:Sample from prior  $x_{0}^{(i)}\sim p(x)$ $i=1,\dots,N$

3:for $\ell=1,\dots,L$ do

4: Simulate observations  $y_{\ell-1}^{(i)}\sim p(y\mid x_{\ell-1}^{(i)})$
$i=1,\dots,N$

5: Form sample covariances
$\mathrm{C}^{xx}_{\ell-1},\mathrm{C}_{\ell-1}^{xy},\mathrm{C}^{yy}_{\ell-1}$
(9) and $\mathrm{C}^{y|x}_{\ell-1}$ (10).

6: Set stepsize $h_{\ell}=\lambda_{\ell}-\lambda_{\ell-1}$

7: Generate observation perturbations
$\eta_{\ell}^{(i)}\sim\mathbf{N}\left(\eta\mid
0,\left(h_{\ell}^{-1}-1\right)\mathrm{C}^{y|x}_{\ell-1}\right)$ $i=1,\dots,N$

8: Move particles
$x_{\ell}^{(i)}=x_{\ell-1}^{(i)}+\mathrm{C}^{xy}_{\ell-1}\left(\mathrm{C}^{yy}_{\ell-1}+(h_{\ell}^{-1}-1)\mathrm{C}^{y|x}_{\ell-1}\right)^{-1}\left(y-y_{\ell-1}^{(i)}-\eta^{(i)}_{\ell}\right)$
$i=1,\dots,N$

9:return $\\{x_{L}^{(i)}\\}_{i=1}^{N}$

###  3.2 Stepsize Selection

The motivation for iterative ensemble Kalman inversion is that for difficult
non-Gaussian problems, moving directly from prior to posterior in one step is
an extremely difficult task. By taking many smaller steps the particles can
explore the state-space and have a better chance of settling in regions of
high posterior probability. There is, therefore, a trade-off to be made - more
steps means greater exploration but also more likelihood simulations and a
longer runtime.

The stepsizes $\\{h_{\ell}\\}_{\ell=1}^{L}$ equivalently define an inverse
temperature schedule $0=\lambda_{0}<\lambda_{1}<\dots<\lambda_{L}$ where
$h_{\ell}=\lambda_{\ell}-\lambda_{\ell-1}>0$ for $\ell=1,\dots,L$.

For SMC samplers (Del Moral et al., 2006), it is common for the next inverse
temperature to be selected adaptively (Jasra et al., 2011) such that the
effective sample size (of the sequential importance weights
$\\{w^{(i)}_{\ell}\\}_{i=1}^{N}$) decreases by a fixed amount at each
iteration. That is, select $\lambda_{\ell}$ such that
$\text{ESS}(\\{w^{(i)}_{\ell}\\}_{i=1}^{N})=(\sum_{i=1}^{N}w^{(i)\,2}_{\ell})^{-1}\approx\rho
N$, where the normalised weights are a function of $\lambda_{\ell}$ and
$\rho\in(0,1)$ is a tuning parameter that controls the size of the steps. The
root for $\lambda_{\ell}$ can be found using a numerical bisection algorithm
in $(\lambda_{\ell-1},\lambda_{L}]$ and requires no additional likelihood
evaluations. This way the algorithm smoothly transitions from prior to
posterior whereas simply using a constant stepsize might induce a degenerate
series of intermediate distributions unless an excessively small stepsize is
used. This idea was ported to ensemble Kalman inversion in Iglesias et al.
(2018) where the following psuedo-weights are used
$\hat{w}^{(i)}_{\ell}\propto\exp\left(-\frac{1}{2}(\lambda_{\ell}-\lambda_{\ell-1})\left(y-\mathcal{H}(x_{\ell-1}^{(i)})\right)^{\mathrm{T}}\mathrm{R}^{-1}\left(y-\mathcal{H}(x_{\ell-1}^{(i)})\right)\right),$
as ensemble Kalman inversion does not compute importance weights inherently.
Here we directly adapt these pseudo-weights to the general likelihood case

$\hat{w}^{(i)}_{\ell}\propto\exp\left(-\frac{1}{2}(\lambda_{\ell}-\lambda_{\ell-1})\left(y-y_{\ell-1}^{(i)}\right)^{\mathrm{T}}\mathrm{C}^{y|x\,-1}_{\ell-1}\left(y-y_{\ell-1}^{(i)}\right)\right).$
(12)

As noted in Iglesias et al. (2018), the lack of resampling means the user can
be more aggressive with the choice of $\rho$, in our experiments we set
$\rho=\frac{1}{2}$.

###  3.3 Stopping Criteria

We consider two stopping criteria.

  * 1.

Sampling \- terminate when $\lambda_{L}=1$. This stopping criterion mimics
that of tempered likelihood approaches for tractable likelihoods and is
applied to ensemble Kalman inversion in Iglesias et al. (2018). This approach
is asymptotically unbiased for the true posterior in the linear Gaussian case
and aims to quantify uncertainty around parameters.

  * 2.

Optimisation \- terminate when the marginal variance (of the particles) in
each dimension becomes sufficiently small, i.e. when
$[\mathrm{C}^{xx}_{\ell}]_{kk}<\upsilon[\mathrm{C}^{xx}_{0}]_{kk},\forall
k\in\\{1,\dots d_{x}\\}$ for a predefined $\upsilon\in[0,1]$ (which we set to
$10^{-2}$). Here the notation $[A]_{ij}$ indexes the $i,j$ coordinate in the
matrix $A$. Under this approach the algorithm is iterated until the particles
form a consensus approaching a single point estimate, which in the linear
Gaussian case will (asymptotically) be the maximum likelihood estimator.

##  4 Numerical Experiments

We now examine the performance of both ensemble Kalman inversion for sampling
and optimisation versus approximate Bayesian computation methods for two
static Bayesian inference problems with intractable likelihoods.

We consider two ABC techniques, the first of which being that of ABC-SMC (Del
Moral et al., 2012). In ABC-SMC, a series of importance weighted Monte Carlo
approximations are generated iteratively to target

$\nu_{\kappa_{\ell}}(x,y^{\prime})\propto p(x)p(y^{\prime}\mid
x)\mathbb{I}[||y-y^{\prime}||<\kappa_{\ell}],$ (13)

for a series of decreasing parameters
$\kappa_{0}>\kappa_{1}>\dots>\kappa_{L}$. Here $y$ is the true data,
$y^{\prime}$ is simulated data, whilst $\mathbb{I}[\cdot]$ is the indicator
function and $||\cdot||$ is the Euclidean norm. As in Del Moral et al. (2006),
particles are rejuvenated using a random-walk Metropolis-Hastings kernel, with
covariance adapted to $2.38^{2}d_{x}^{-1}\mathrm{C}^{xx}_{\ell-1}$ a scaled
version of the empirical covariance of the previous particles and threshold
parameters $\kappa_{\ell}$ adaptively chosen such that ESS $\approx 0.9N$.
Particles are resampled when the ESS drops below $0.5N$ and the algorithm
terminates when the acceptance rate of the Metropolis-Hastings kernel first
falls below 1.5%.

For our second ABC technique, we run the random-walk Metropolis-Hastings
kernel directly as an ABC-MCMC algorithm. As described in Vihola and Franks
(2020) we use a Robbins-Monro schedule to adaptively tune the stepsize,
preconditioner combination to $2.38^{2}d_{x}^{-1}\hat{\mathrm{\Sigma}}$ where
$\hat{\mathrm{\Sigma}}$ is the empirical covariance of the historical chain
and adapt the threshold parameter $\kappa$ from (13) such that 10% of samples
are accepted.

As mentioned, for EKI we determine the stepsize $h_{\ell}$ (equivalently the
next inverse temperature $\lambda_{\ell}$) adaptively such that the ESS of the
pseudo-weights (12) is approximately $0.5N$. We examine both the sampling and
optimisation stopping criteria discussed in Section 3.3. All simulations are
ran with mocat Duffield (2021), which includes open source implementations for
all the discussed algorithms.

###  4.1 $g$-and-$k$ distribution

Popular as a benchmark for ABC algorithms, the g-and-k distribution family is
defined by the quantile function

$F^{-1}(u)=A+B\left(1+c\frac{1-\exp(-gz(u))}{1+\exp(-gz(u))}\right)(1+z(u)^{2})^{k}z(u),$
(14)

where $z(\cdot)$ is the quantile function of a standard normal distribution.
The constant $c$ is typically set to 0.8 and considered known. We set the
remaining parameters $x=(A,B,g,k)$ with true values $(3,1,2,1/2)$ but consider
them unknown (to be inferred) each with prior $\mathcal{U}(\cdot\mid 0,10)$.
The g-and-k likelihood is defined implicitly by the quantile function (14).
This likelihood function cannot be obtained analytically and thus we cannot
easily utilise traditional posterior inference methods such as MCMC or
importance sampling - although their ABC counterparts are still possible as
the likelihood can be easily simulated for given parameters by simply
evaluating the quantile function (14) at a sampled standard uniform random
variable.

We assume we have data of 1000 i.i.d. samples from (14) which we summarise
into 100 evenly spaced order statistics for both EKI and ABC. It is common
practice for Monte Carlo algorithms to apply a transformation converting
constrained variables to ones in $\mathbb{R}$, this alleviates the possibility
of parameters being moved outside of the bounded domain, here we unconstrain
all parameters using the transformation $z(\cdot/10)$ for both ABC and EKI
(other transformations are possible although the choice is not typically
considered a significant factor in performance).

Figure 1: $g$-and-$k$ marginal posteriors for EKI sampling and ABC-SMC,
$N=500$, truth in red.

Figure 2: $g$-and-$k$ convergence of EKI for optimisation, $N=500$, truth in
red. Boxes display range and quartiles of ensemble.

In Figure 2, we compare the marginal distributions produced by EKI for
sampling and those from ABC-SMC. We observe that EKI has centred on the
vicinity of the truth for all 4 parameters whereas ABC-SMC has failed to
concentrate in the $g$ variable in particular. We note that the two posteriors
differ quite significantly - an indication of the high levels of non-linearity
in the $g$-and-$k$ likelihood - yet the EKI posterior remains informative.

We then examine the second EKI stopping criterion, that of optimisation. The
EKI optimisation procedure, Section 3.3, iterates beyond $\lambda_{\ell}=1$
until a consensus is reached on a single point approximation for the maximum
likelihood estimator. Figure 2 displays 7 equally spaced iterations as the
inverse temperature (which is adaptively selected at each iteration based on
the distance of between simulated and true data (12)) increases above
$\lambda_{\ell}=1$ before terminating when all standard deviations are
suitably small, note the increasing stepsizes as the ensemble converges to a
point estimate. The particles converge quickly and very closely to the true
underlying parameter values.

Figure 3: Root mean squared error versus number of likelihood simulations
induced by varying $N$ (from 200 to 5000), on $g$-and-$k$ distribution.
Repeated over 10 randomly generated sets of observations.

Finally, we vary the sample size $N$ between 200 and 5000 then repeat the
experiment 10 times. We plot the root mean squared error against the number of
likelihood simulations utilised by each algorithm as $N$ changes in Figure 3.
Note that the adaptive stopping of the EKI and ABC-SMC techniques means that
the number of iterations and therefore likelihood simulations can vary across
seeds. We observe that both EKI stopping criteria are consistently
outperforming both ABC-MCMC and ABC-SMC for the same computational cost.
Curiously, we observe that the performance of EKI for sampling deteriorates as
$N$ increases although this is not the case for the optimisation approach. We
posit that this might be due to the smaller sample sizes under estimating the
noise covariance (a common occurrence in ensemble Kalman techniques Tong et
al. (2016)) and therefore moving the particles further.

###  4.2 Stochastic Lorenz 96

Figure 4: Lorenz 96 marginal densities for EKI sampling and ABC-SMC, $N=500$,
truth in red.

Figure 5: Lorenz 96 coonvergence of EKI for optimisation, $N=500$, truth in
red. Boxes display range and quartiles of ensemble.

We now consider the task of inferring the initial conditions of a noisy
version of the Lorenz 96 model (Lorenz, 1995). The Lorenz 96 model is a
simplified representation of oceanic flows that is commonly used as a testbed
for high-dimensional data assimilation techniques.

The Lorenz 96 dynamics (with added stochasticity) are defined by the SDE

$dx_{t}[m]=(-x_{t}[m-2]\,x_{t}[m-1]+x_{t}[m-1]\,x_{t}[m+1]-x_{t}[m]+F)dt+dW_{t},$

for $m=1,\dots,d_{x}$ with cyclic coordinates $x_{t}[0]=x_{t}[d_{x}]$,
$x_{t}[-1]=x_{t}[d_{x}-1]$ and $x_{t}[d_{x}+1]=x_{t}[1]$. Here the notation
$x[i]$ simply accesses the $i$th coordinate of the vector $x$. We adopt the
common high-dimensional setup of $d_{x}=40$ and $F=8$, which is known to
produce challenging, chaotic dynamics.

Figure 6: Root mean squared error for number of likelihood simulation induced
by varying $N$ (from 200 to 5000), on Lorenz 96 example. Repeated over 10
randomly generated sets of observations.

We define our inference goal as obtaining the initial conditions
$x_{0}\in\mathbb{R}^{d_{x}}$ given observations of every other dimension,
perturbed by Gaussian noise with variance 0.1, at times $t=1,2,3,4,5$ \-
resulting in $d_{y}=100$ observations. We set the prior to
$p(x_{0})=\mathbf{N}(x_{0}\mid F,5\mathbb{I}_{40})$ and simulate from the
likelihood with an Euler-Maruyama scheme (stepsize 0.001). The stochasticity
in the Lorenz 96 dynamics provides a more realistic influence of uncertainty
but the iterative addition of noise in the Euler-Maruyama scheme makes
evaluating the likelihood density intractable.

In our experiments, underlying true values for the initial conditions are
sampled from the prior and then observations generated using the same Euler-
Maruyama scheme as above.

Recall that odd dimensions are directly observed whereas even dimensions are
unobserved. We see in Figure 5 that EKI for sampling converges very closely
around the truth in observed dimensions and is understandably less certain
about unobserved dimensions. In contrast ABC-SMC, performs similarly for all
dimensions and is likely struggling with the dimensionality of the problem.

When we push the EKI into high inverse temperatures in Figure 5 we first see
that the particles struggle to collapse in unobserved dimensions. This is an
indication that the given observations are insufficient to provide a confident
point estimate in those unobserved dimensions. We also notice that the
particles converge in the second dimension away from the true underlying value
of the parameter - this may be an indication that the true maximum likelihood
is not necessarily guaranteed to be close to the truth (for all dimensions)
under this model setup.

In Figure 6, we also observe the phenomenon of decreasing performance in EKI
for sampling as $N$ increases for the L96 example - although less so. However,
again we see that EKI consistently outperforms ABC, although this is perhaps
not surprising in a high-dimensional example given the regular use of ensemble
Kalman techniques in similar settings. In this case, the EKI for optimisation
utilised significantly more likelihood simulations as it requires more
iterations to converge - it also suffered high variance results whereas the
performance of the EKI for sampling was more stable.

##  5 Conclusion

We have extended the work of ensemble Kalman inversion (Iglesias et al., 2013,
2018) to problems with general likelihoods as opposed to the common
restriction of additive Gaussian noise. In doing so, we remain faithful to the
ensemble Kalman paradigm, i.e. our generalisation remains asymptotically
unbiased in the linear Gaussian case. We described how to apply the technique
for both optimisation and for sampling or uncertainty quantification. We have
demonstrated both speed and accuracy of the novel ensemble Kalman inversion
algorithm in a difficult benchmark problem as well as a high dimensional
spatial example. The computational cost of the ensemble Kalman inversion is
$O(Ld_{x}^{3}+LNd_{x}^{2})$ and only requires $LN$ likelihood simulations
which is the typical computational bottleneck for problems within approximate
Bayesian computation.

We observe the curious phenomenon that increasing the number of particles
fails to increase accuracy when applying ensemble Kalman inversion for
sampling - at least in terms of mean square error. An outstanding question is
how to correct for this. This phenomenon is not entirely new but is not well
understood, it would be intriguing to investigate whether it could potentially
be mitigated by covariance regularisation (Houtekamer and Mitchell, 2001) or
moment-matching ideas (Lei and Bickel, 2011).

A natural extension of the stochastic ensemble Kalman inversion algorithm
presented in this chapter would be the conversion to the square-root ensemble
Kalman variants (Bishop et al., 2001; Anderson, 2001) that instead
deterministically move particles in a way that remains asymptotically unbiased
for fully linear Gaussian problems. By removing a layer of stochasticity we
hope to increase the numerical stability of the inversion algorithm.

Outside of linear Gaussian problems, ensemble Kalman inversion is
asymptotically biased. It would interesting to investigate embedding an
ensemble Kalman kernel within an ABC-SMC sampler. This way, the ensemble
Kalman inversion would inherit the theory of approximate Bayesian computation
and become asymptotically unbiased for $\nu_{\kappa}$. However, it is not
clear how to choose the backward kernel to induce stable importance weights.

A further application of the presented ensemble Kalman inversion would be to
investigate its use within state-space models. It may be that utilising an
iterative tempered approach to the update step within an ensemble Kalman
filter may improve sample quality. Additionally, we could adapt ensemble
Kalman inversion to be used in the online setting of state-space models with
intractable observation densities (Jasra et al., 2012).

## Acknowledgements

This work was supported by the UK Engineering and Physical Sciences Research
Council (EPSRC) grant EP/M508007/1 for the Department of Engineering,
University of Cambridge.

## References

  * Anderson (2001) Anderson, J.L., 2001.  An Ensemble Adjustment Kalman Filter for Data Assimilation.  Monthly Weather Review 129, 2884 – 2903.  doi:10.1175/1520-0493(2001)129<2884:AEAKFF>2.0.CO;2.
  * Beaumont (2019) Beaumont, M.A., 2019.  Approximate Bayesian Computation.  Annual Review of Statistics and Its Application 6, 379–403.  doi:10.1146/annurev-statistics-030718-105212, arXiv:https://doi.org/10.1146/annurev-statistics-030718-105212.
  * Bishop et al. (2001) Bishop, C.H., Etherton, B.J., Majumdar, S.J., 2001.  Adaptive Sampling with the Ensemble Transform Kalman Filter. Part I: Theoretical Aspects.  Monthly Weather Review 129, 420 – 436.  doi:10.1175/1520-0493(2001)129<0420:ASWTET>2.0.CO;2.
  * Del Moral et al. (2006) Del Moral, P., Doucet, A., Jasra, A., 2006.  Sequential Monte Carlo Samplers.  Journal of the Royal Statistical Society. Series B (Statistical Methodology) 68, 411–436.
  * Del Moral et al. (2012) Del Moral, P., Doucet, A., Jasra, A., 2012.  An Adaptive Sequential Monte Carlo method for Approximate Bayesian Computation.  Statistics and Computing 22, 1009–1020.  doi:10.1007/s11222-011-9271-y.
  * Duffield (2021) Duffield, S., 2021.  mocat: All things monte carlo, written in jax.
  * Evensen (1994) Evensen, G., 1994.  Sequential Data Assimilation with a Nonlinear Quasi-geostrophic Model using Monte Carlo Methods to Forecast Error Statistics.  Journal of Geophysical Research: Oceans 99, 10143–10162.  doi:https://doi.org/10.1029/94JC00572, arXiv:https://agupubs.onlinelibrary.wiley.com/doi/pdf/10.1029/94JC00572.
  * Houtekamer and Mitchell (2001) Houtekamer, P.L., Mitchell, H.L., 2001\.  A Sequential Ensemble Kalman Filter for Atmospheric Data Assimilation.  Monthly Weather Review 129, 123 – 137.  doi:10.1175/1520-0493(2001)129<0123:ASEKFF>2.0.CO;2.
  * Houtekamer et al. (2005) Houtekamer, P.L., Mitchell, H.L., Pellerin, G., Buehner, M., Charron, M., Spacek, L., Hansen, B., 2005.  Atmospheric Data Assimilation with an Ensemble Kalman Filter: Results with Real Observations.  Monthly Weather Review 133, 604 – 620.  doi:10.1175/MWR-2864.1.
  * Iglesias (2015) Iglesias, M., 2015.  Iterative Regularization for Ensemble Data Assimilation in Reservoir Models.  Computational Geosciences 19, 177–212.  doi:10.1007/s10596-014-9456-5.
  * Iglesias et al. (2013) Iglesias, M., Law, K.J.H., Stuart, A.M., 2013.  Ensemble Kalman Methods for Inverse Problems.  Inverse Problems 29, 045001\.  doi:10.1088/0266-5611/29/4/045001.
  * Iglesias et al. (2018) Iglesias, M., Park, M., Tretyakov, M.V., 2018.  Bayesian Inversion in Resin Transfer Molding.  Inverse Problems 34, 105002\.  doi:10.1088/1361-6420/aad1cc.
  * Jasra et al. (2012) Jasra, A., Singh, S.S., Martin, J.S., McCoy, E., 2012\.  Filtering via Approximate Bayesian Computation.  Statistics and Computing 22, 1223–1237.  doi:10.1007/s11222-010-9185-0.
  * Jasra et al. (2011) Jasra, A., Stephens, D.A., Doucet, A., Tsagaris, T., 2011\.  Inference for Lévy-Driven Stochastic Volatility Models via Adaptive Sequential Monte Carlo.  Scandinavian Journal of Statistics 38, 1–22.  doi:https://doi.org/10.1111/j.1467-9469.2010.00723.x, arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-9469.2010.00723.x.
  * Lei and Bickel (2011) Lei, J., Bickel, P., 2011.  A Moment Matching Ensemble Filter for Nonlinear Non-Gaussian Data Assimilation.  Monthly Weather Review 139, 3964–3973.
  * Lorenz (1995) Lorenz, E.N., 1995.  Predictability: A Problem Partly Solved, in: Seminar on Predictability, 4-8 September 1995, ECMWF. ECMWF, Shinfield Park, Reading. pp. 1–18.
  * Lueckmann et al. (2019) Lueckmann, J.M., Bassetto, G., Karaletsos, T., Macke, J.H., 2019\.  Likelihood-free Inference with Emulator Networks, in: Symposium on Advances in Approximate Bayesian Inference, PMLR. pp. 32–53.
  * Marjoram et al. (2003) Marjoram, P., Molitor, J., Plagnol, V., Tavaré, S., 2003\.  Markov Chain Monte Carlo without Likelihoods.  Proceedings of the National Academy of Sciences 100, 15324–15328.  doi:10.1073/pnas.0306899100, arXiv:https://www.pnas.org/content/100/26/15324.full.pdf.
  * Matsubara et al. (2021) Matsubara, T., Knoblauch, J., Briol, F.X., Oates, C., 2021\.  Robust Generalised Bayesian Inference for Intractable Likelihoods.  arXiv preprint arXiv:2104.07359 .
  * Nott et al. (2012) Nott, D.J., Marshall, L., Ngoc, T.M., 2012.  The Ensemble Kalman Filter is an ABC Algorithm.  Statistics and Computing 22, 1273–1276.  doi:10.1007/s11222-011-9300-x.
  * Pritchard et al. (1999) Pritchard, J.K., Seielstad, M.T., Perez-Lezaun, A., Feldman, M.W., 1999\.  Population Growth of Human Y Chromosomes: A Study of Y Chromosome Microsatellites.  Molecular biology and evolution 16, 1791—1798.  doi:10.1093/oxfordjournals.molbev.a026091.
  * Roth et al. (2017) Roth, M., Hendeby, G., Fritsche, C., Gustafsson, F., 2017\.  The Ensemble Kalman Filter: A Signal Processing Perspective.  EURASIP Journal on Advances in Signal Processing 2017, 56.  doi:10.1186/s13634-017-0492-x.
  * Tong et al. (2016) Tong, X.T., Majda, A.J., Kelly, D., 2016.  Nonlinear Stability and Ergodicity of Ensemble based Kalman Filters.  Nonlinearity 29, 657–691.  doi:10.1088/0951-7715/29/2/657.
  * Vihola and Franks (2020) Vihola, M., Franks, J., 2020\.  On the Use of Approximate Bayesian Computation Markov Chain Monte Carlo with Inflated Tolerance and Post-correction.  Biometrika 107, 381–395.  doi:10.1093/biomet/asz078, arXiv:https://academic.oup.com/biomet/article-pdf/107/2/381/33218096/asz078.pdf.


# Negative Sampling for Contrastive Representation Learning: A Review

Lanling Xu1,3 Jianxun Lian1 Wayne Xin Zhao4111Corresponding author Ming Gong2
Linjun Shou2 Daxin Jiang2 Xing Xie1&Ji-Rong Wen3,4 1Microsoft Research Asia
2Microsoft STC Asia
3School of Information, Renmin University of China
4Gaoling School of Artificial Intelligence, Renmin University of China
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
{migon, lisho, djiang<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The “learn-to-compare” paradigm of contrastive representation learning (CRL),
which compares positive samples with negative ones for representation
learning, has achieved great success in a wide range of domains, including
natural language processing, computer vision, information retrieval and graph
learning. While many research works focus on data augmentations, nonlinear
transformations or other certain parts of CRL, the importance of negative
sample selection is usually overlooked in literature. In this paper, we
provide a systematic review of negative sampling (NS) techniques and discuss
how they contribute to the success of CRL. As the core part of this paper, we
summarize the existing NS methods into four categories with pros and cons in
each genre, and further conclude with several open research questions as
future directions. By generalizing and aligning the fundamental NS ideas
across multiple domains, we hope this survey can accelerate cross-domain
knowledge sharing and motivate future researches for better CRL.

##  1 Introduction

In deep learning, to make a good representation, a series of methods
collectively referred to as contrastive learning (CL) provide a simple yet
effective “learn-to-compare” paradigm. Despite its success in recent self-
supervised learning Liu et al. (2021), contrastive learning is not a new idea,
with related works stretching back for over a decade Chopra et al. (2005),
ranging from supervised, semi-supervised to self-supervised methods in texts,
images, retrievals, graphs, etc. Generally speaking, we consider all methods
that contrast between positive and negative pairs to learn representations as
contrastive representation learning (CRL) Le-Khac et al. (2020).

The induced representations of CRL consist of two key properties: alignment of
features from positive pairs and uniformity of representation on the
hypersphere Wang and Isola (2020), and the latter mainly depends on separation
of negative pairs. That is to say, solely minimizing the distance between
positive samples will make the distance between any samples close to zero, and
the quality of negative pairs has a decisive impact on the representation from
catastrophic collapse. Due to expensive manual labeling and the lack of
explicit negative signals in most cases, the strategy of negative sampling
(NS) is to select (or generate) negative samples for a given positive pair
from negative candidates.

Motivation: why is negative sampling important?

As described above, “negative” samples are introduced to keep the uniformity
property to avoid representation collapse Gao et al. (2021), while “sampling”
is a useful and practical strategy from both efficient and effective
perspective. On the one hand, sampling greatly improves the computational
efficiency. Specifically, the number of candidate negatives is generally equal
to or even far more than the whole data set (e.g., over 2 billion candidates
for each pair Ying et al. (2018)). Therefore, the computational burden of
comparing each positive pair with all negative pairs is too heavy to accept
with limited computing power, which may also submerge the gradient of positive
pairs against too many negative samples Girshick et al. (2014). On the other
hand, sampling informative negatives further promotes the training results. In
objective optimization, it is the informative negative that plays a crucial
role, while most negatives are easy to discriminate with minor gradient
contributions and a few negatives are even counter-productive Cai et al.
(2020). Regardless of efficiency, taking all candidates equally as negative
samples is not the optimal solution in most cases.

Owing to success of CRL, steady progress has been made in developing
algorithms for data augmentations Chen et al. (2020), nonlinear
transformations Wang et al. (2019) or other certain parts of CRL. However, the
choice of negative samples gets less attention, which is usually ignored or
simplified by random selection Chopra et al. (2005). Since the naive strategy
is independent with model parameters, easy negatives are chosen by random
sampling with high probability, resulting in slow convergence and significant
performance loss. For instance, the convergence rate of an adaptive sampling
strategy for item recommendation is more than 10 times faster than that of
random selection with better results Rendle and Freudenthaler (2014), and
sometimes the results can be even improved by nearly 50% for entity alignment
Sun et al. (2018). Numerous empirical results have shown that CRL benefits
from more intelligent negative sampling strategies.

Concentration: what makes a good negative sampler?

Given the important role of negative sampling for CRL, we review a
comprehensive set of related methods across various fields, summarize their
advantages and disadvantages, and conclude that the core properties for
negative samplers can be evaluated in four dimensions.

  * •

Efficient. The negative sampler should have low time and space complexity,
which hardly affects overall resources.

  * •

Effective. The informative samples from the negative sampler should lead the
model towards a constringent acceleration and gradient change on the aspect of
rationality.

  * •

Stable. The negative sampler shall be robust and data-insensitive with little
probability to collapse.

  * •

Data-independent. The negative sampler should not rely heavily on the side
information. Otherwise, data availability will greatly restrict the practical
applicability.

At present, there is no method that meets all the above requirements, raising
the question of trade-offs among various properties in employing negative
sampling for CRL.

Contributions. Due to the prevalence of contrastive learning in self-
supervised representation learning (SSL), there exist several comprehensive
surveys on CLJaiswal et al. (2021), SSLLiu et al. (2021) or CRLLe-Khac et al.
(2020). However, none of them concentrate on negative sampling, which is a
must for generalized CRL based on “learn-to-compare” paradigm. To the best of
our knowledge, this paper is the first review focusing on negative sampling
methods for CRL, and the main contributions of this work are summarized below:

  * •

We formulate the general task of negative sampling for CRL in texts, images,
retrievals and graphs, providing a up-to-date review and compendious sum-up.
Through this article, one can easily grasp the development history and
frontier ideas of negative sampling across multiple AI fields.

  * •

We divide negative sampling methods into four categories according to
distinguishing features, and the advantages and disadvantages of each one are
discussed systematically.

  * •

We conclude several open research problems in this field, in order to present
a pointer to relevant researches on the application of negative sampling for
but not limited to CRL.

Category | Subcategory | Representative Approaches
---|---|---
Static NS | Random NS |  Random selection Chopra et al. (2005)
Popularity-biased NS |  Word2vec Mikolov et al. (2013); PNS Rendle and Freudenthaler (2014)
Dynamic NS | Query-dependent DNS |  |  DNS Zhang et al. (2013) Chen et al. (2018); ANCE Xiong et al. (2020)
---
PinSage Ying et al. (2018); IS Robinson et al. (2020)
Positive-dependent DNS |  |  Max-sampling Rao et al. (2016); GNEG Zhang and Zweigenbaum (2018)
---
$\epsilon-$Truncated UNS Sun et al. (2018); TransEdge Sun et al. (2019)
Hybrid DNS |  |  FaceNet Schroff et al. (2015); WAPR Weston et al. (2010)
---
MoChi Kalantidis et al. (2020); MixGCF Huang et al. (2021)
Adversarial NS | Discrete Sampling |  |  IRGAN Wang et al. (2017); GraphGAN Wang et al. (2018a)
---
KBGAN Cai and Wang (2017); KGPolicy Wang et al. (2020)
Continuous Sampling |  |  DAML Duan et al. (2018); AdvIR Park and Chang (2019)
---
HeGAN Hu et al. (2019); AdCo Hu et al. (2021)
Efficient NS | In-Batch NS |  |  SimCLR Chen et al. (2020); PBG Lerer et al. (2019)
---
ABS Choi et al. (2021); GraphVite Zhu et al. (2019)
Caching Mechanism |  NSCaching Zhang et al. (2019); MoCo He et al. (2020)
Table 1: Categorization of negative sampling approaches for CRL.

##  2 Task Formulation and Typical Applications

The ultimate goal of CRL is to learn distinguishable information to pull
together positive pairs (similar ones), and push apart negative pairs
(dissimilar ones). To contrast between positive and negative pairs, InfoNCE
Oord et al. (2018) is widely accepted as a generalized form of other
comparison-based losses Liu et al. (2021). Without loss of generality, we
formulate negative sampling for CRL as follows:

$\displaystyle\mathcal{L(\theta)}$
$\displaystyle=\mathbb{E}_{p(x,y^{+},y^{-})}l_{\theta}(x,y^{+},y^{-})$
$\displaystyle=\mathbb{E}_{\mathop{}_{\boldsymbol{y^{-}\sim
p(y^{-})}}^{(x,y^{+})\in\mathcal{T}}}[-{\rm
log}(\dfrac{e^{\phi_{\theta}(x,y^{+})}}{e^{\phi_{\theta}(x,y^{+})}+\sum_{k=1}^{K}e^{\phi_{\theta}(x,y^{-}_{(k)})}})]$

where $x$ is the anchor or query, $y^{+}$ is the positive sample and $y^{-}$
denotes the negative sample. $\mathbb{E}_{p(x,y^{+},y^{-})}$ is the
expectation with respect to the joint distribution $p(x,y^{+},y^{-})$ of
samples. $\phi_{\theta}(\cdot)$ is used to measure the score of samples, such
as distance and similarity with parameters $\theta$ in the latent space.
$l(\cdot)$ captures the loss that scores a positive tuple $(x,y^{+})$ against
$K$ negative ones in the form of InfoNCE.

Focusing on negative sampling, despite the variation in form, the essence is
to learn the distribution of negative samples (i.e., $y^{-}\sim p(y^{-})$) for
contrastive comparison, and $\sim$ denotes sampling from the specific
distribution. As is classified in Section 3, different kinds of negative
distributions correspond to different negative sampling approaches for CRL.

In general, the existing CRL methods involving negative sampling can all be
reduced into our formulation, and the target set $\mathcal{T}$ vary from task
to task. As follows, we introduce four representative applications in
different fields.

  * •

In natural language processing (NLP), typical CRL tasks include word embedding
Mikolov et al. (2013) and sentence embedding Gao et al. (2021).
$\mathcal{T}=\\{(\omega_{I},\omega_{O})\\}$ where $\omega_{I}$ means the input
such as context words, and $\omega_{O}$ is the output such as the target word.
Given $\omega_{I}$, negative sample $\omega_{i}$ is selected from corpus based
on certain strategies, i.e., negative sampling.

  * •

In computer vision (CV), CRL has been applied in tasks such as image
classification Chen et al. (2020), $\mathcal{T}=\\{(q,p)\\}$ where $q$ and $p$
denote two augmented views of the same image, or the query image and the
related one. Without supervision signals, negative samples are mainly utilized
for pushing apart views from different images, while label information can be
leveraged in a supervised setting.

  * •

In information retrieval (IR), $\mathcal{T}=\\{(q,d)\\}$ where $q$ is the
query and $d$ is the relevant document. In specific tasks such as implicit
collaborative filtering (ICF) Zhang et al. (2013),
$\mathcal{T}=\\{(u,i)|u\in\mathcal{U},i\in\mathcal{I}\\}$, where $u$ and $i$
denotes the user and item of an interaction. $\mathcal{U}$ and $\mathcal{I}$
are user and item sets. With pairwise inputs, negative sampling aims at
selecting negative samples for users from non-interactive items.

  * •

In graph representation learning (GRL), the encoded node representation can be
learned in a similar way as word embeddings Tang et al. (2015). Particularly
in knowledge graph embedding (KGE) tasks Sun et al. (2018),
$\mathcal{T}=\\{(h,r,t)|h,t\in\mathcal{E},r\in\mathcal{R}\\}$. $h$, $r$ and
$t$ denotes the head entity, relation and tail entity of a triple. The
corrupted false triples are constructed by replacing the head or tail entity
with a certain negative sampling strategy.

##  3 Negative Sampling Approaches for CRL

In this section, we systematically review representative negative sampling
methods from different domains, and divide them into four categories, with
particular genres in each one, for better understanding and comparisons. The
general categorization is illustrated in Table 1.

###  3.1 Static Negative Sampling

As is shown in Algorithm 1, static negative sampling assigns a static, global
probability for each candidate to be sampled, where $\mathcal{E}_{x}$ denotes
positive samples of $x$ and $\mathcal{E}_{y^{-}}$ denotes the sampled
negatives, the same below. Typically, the uniform and popularity-biased
distribution correspond to the random negative sampling (RNS) and popularity-
biased negative sampling (PNS) respectively. To make it more formal,
$p(y^{-})\propto deg(y^{-})^{\alpha}$, namely, the probability selected as the
negative is proportional to $\alpha$ power of $y^{-}$’s popularity value (such
as word frequency in word embedding). RNS can be regarded as a simple case of
PNS at $\alpha=0$.

#### Random Negative Sampling.

RNS is the most basic negative sampling method, which is often used as the
default sampling strategy and basic baseline for its simplicity and plainness.
It is generally believed that a strategy which cannot stably outperforms RNS
is of no practical use. In a broad sense, a random negative selection can all
be regarded as the applications of RNS though it is not explicitly stated.

#### Popularity-biased Negative Sampling.

Pan et al. (2008) introduces user-oriented and item-oriented sampling to
adjust the negative distribution according to the number of interactions in
one-class collaborative filtering, which is an early attempt to consider data
frequency in negative sampling. In the later recommendation systems Rendle and
Freudenthaler (2014), PNS usually takes the popularity of items as the unigram
negative distribution, that is, it tends to choose popular items as the
negative samples. Negative sampling in natural language processing originates
from word2vec Mikolov et al. (2013), which finds that the popularity-biased
distribution at $\alpha=3/4$ (i.e.,
$P_{n}(w)=U(w)^{3/4}/\Sigma_{i}^{|vocab|}U(w_{i})^{3/4}$) significantly
outperforms the unigram and uniform distributions according to experimental
experience of authors. The training paradigm and hyper parameter of word2vec
is also used in tasks such as graph learning Tang et al. (2015) and word
embeddings Zhang and Zweigenbaum (2018). Despite its wide application,
$\alpha=3/4$ is an empirical value that lacks theoretical explanation, the
best results can even be achieved when $\alpha$ is negative in Caselles-Dupré
et al. (2018), indicating the uncertainty of popularity on the quality of
negative samples.

#### Pros and cons.

Static NS is the most simple approach for implementation. It is stable, fast,
and auxiliary data-independent. As formulated by Oord et al Oord et al.
(2018), more negative samples lead to a tighter lower bound on mutual
information. When the number of negative samples is large enough, static NS
can achieve satisfying performance. However, in many cases such as pre-
training large NLP models, only a small number of negative samples can be
afforded during training with GPUs. In addition, the static setting of
candidate probability distribution means that negative samples do not change
dynamically in pace with the training process or adaptively adjust the
negative distribution tailored to each query, resulting in low-quality
negative samples along with sub-optimal data representations.

###  3.2 Dynamic Negative Sampling

Due to the inherent limitations of easy negative samples, quite a few
researchers have studied how to mine hard negatives which are difficult to
distinguish from the positive samples. Related works can be traced back to
Sung and Poggio (1998), which adds the images misjudged by the current
classifier as negative samples to expand the negative sample set so as to
improve model performance. This bootstrapping-like approach lays foundations
for subsequent dynamic negative sampling (DNS) methods for CRL, such as hard
example mining (HEM) Shrivastava et al. (2016) in computer vision.

In general, DNS is an extension of bootstrapping, it dynamically selects
contrastive pairs that are difficult to discriminate for the current model. In
this way, the samples confusing the model can be highlighted in the training
process, so that model parameters can be fully optimized. Formally, the
selection of negative samples is determined by candidates’ propensity scores,
which reflect the quality of samples and will vary with the training process:
$y^{-}\sim p(y^{-}|(x,y^{+}))\propto f(x,y^{+},y^{-})$, where $f(\cdot)$ is a
scorer that produces a propensity score for $y^{-}$. Specifically, it is a
mutually reinforcing feedback mechanism that negative sampler selects high-
quality contrastive pairs for the model, and the gradually optimized model
provides guidance for distribution of candidates. The dynamic negative
sampling framework can be generalized as in Algorithm 2. According to the
propensity function of DNS, relevant methods can be roughly divided into
Query-dependent DNS, Positive-dependent DNS and Hybrid DNS.

#### Query-dependent DNS.

The propensity score is based on the predictive score of the pair $\langle$
query, sample candidate $\rangle$. A higher score implies the current model
mis-classifies the candidate sample as a positive one, so this candidate will
be selected as the negative with a greater probability, i.e., $y^{-}\sim
p(y^{-}|x)\propto{\phi}_{\theta}(x,y^{-})$. One of the representative methods
is dynamic negative sampling (DNS) Zhang et al. (2013), which selects hard
samples with higher predicted scores during each update and significantly
outperforms RNS, revealing the importance of adaptive sampling methods
according to model parameters. The idea of DNS can also be applied to other
tasks including but not limited to word representation Chen et al. (2018) and
dense text retrieval Xiong et al. (2020). For simplicity, some methods further
utilize heuristic measures to calculate weights, such as PageRank score in
PinSage Ying et al. (2018). Without supervision, the distribution of hard
negative pairs whose embeddings are similar to the query, can also be
approximated by importance sampling (IS) strategy for SSL, and one can control
the hardness of negative samples by hyperparameters Robinson et al. (2020).

#### Positive-dependent DNS.

Utilizing model scoring is to select more difficult negative samples from the
perspective of objective optimization, while positive-dependent DNS makes
intuitive use of the similarity between candidates and the positive sample,
i.e., $y^{-}\sim p(y^{-}|y^{+})$. For example, max sampling Rao et al. (2016)
selects the most relevant negative answers by maximizing their similarities to
the positive one for answer selection. Sun et al. propose a similar approach
named $\epsilon$-Truncated UNS Sun et al. (2018) to choose positive entity’s
nearest neighbors in the embedding space as candidate negatives, and this
strategy is commonly adopted in subsequent KGE models such as TransEdge Sun et
al. (2019). Besides the induced representation in the embedding space, the
semantic and structural information of existing or constructed graphs can also
be employed for similarity measures. As the improvement of negative sampling
in word2vec, GNEG Zhang and Zweigenbaum (2018) first constructs a co-
occurrence network according to the semantic concurrence information of words
in the corpus, and then obtains hard negative samples through random walk on
the positive node.

#### Hybrid DNS.

Combined with the two above, queries and positive samples can both be utilized
for DNS at the same time, which we call Hybrid DNS. In this case, a proposal
set of negative samples are generated by a query-dependent DNS, then positive
samples will be used to filter out inappropriate candidates or incorporate new
hard candidates. On the one hand, the predicted scores of positive pair can be
employed as the standard to avoid hardest negatives. For instance, FaceNet
Schroff et al. (2015) selects semi-hard negative samples nearest to the query
in the embedding space while they are still farther than the positive-query
pairs. On the other hand, positive samples can be further utilized to mine
harder negatives, such as uniform sampling until a rejection in WARP Weston et
al. (2010). Considering both hard negatives and positive samples, another
promising line of research involves hard negative synthesis in the embedding
space as needed. Motivated by success of data mixing techniques in images,
MoChi Kalantidis et al. (2020) synthesizes harder negative samples by mixing
existing Query-dependent hard negative embeddings and the positive embedding
directly in the latent space. Similar to MoChi’s mechanism, MixGCF Huang et
al. (2021) makes use of the neighborhood aggregation in graph neural network
and designs positive mixing and hop mixing strategies. The former incorporates
the positive embedding with candidate negatives, while the latter generates
the synthetic negative embedding by combining hardest hops of the samples
mixed before.

Algorithm 1 A generalized framework for static NS

Input: $x$, $\mathcal{E}_{x}$, $p(y^{-})\propto deg(y^{-})^{\alpha}$
Output: $\mathcal{E}_{y^{-}}$

1: $\mathcal{E}_{y^{-}}\leftarrow\emptyset$;

2: for $k$ $\leftarrow$ $1$ to $K$ do

3: sample $y^{k}\sim p(y^{-})$ from $\mathcal{E}\setminus\mathcal{E}_{x}$;

4: insert($\mathcal{E}_{y^{-}},y^{k}$);

5: end for

Algorithm 2 A generalized framework for hard NS

Input: $x$, $y^{+}$, $\mathcal{E}_{x}$
Output: $\mathcal{E}_{y^{-}}$

1: Uniformly sample $Neg$ from $\mathcal{E}\setminus\mathcal{E}_{x}$;

2: $\mathcal{E}_{y^{-}}\leftarrow\emptyset$;

3: for $l$ $\leftarrow$ $1$ to length($Neg$) do

4: $score$ $\leftarrow f(x,y^{+},y^{l})$;

5: end for

6: $p(y^{-}|(x,y^{+}))$ $\leftarrow$ normalize($score$);

7: for $k$ $\leftarrow$ $1$ to $K$ do

8: if Sampling then

9: Sample $y^{k}\sim p(y^{-}|(x,y^{+}))$ from $Neg$;

10: else if Synthesis then

11: Mix several $y^{-}\sim p(y^{-}|(x,y^{+}))$ from $Neg$ and combine with
$y^{+}$ to synthesize $y^{k}$ in latent space;

12: end if

13: insert($\mathcal{E}_{y^{-}},y^{k}$);

14: end for

#### Pros and cons.

As the opposite of easy negatives that have already been discriminated as the
negative, those easily confused hard negative samples bring greater gradient
contribution to the model optimization and accelerate the convergence Robinson
et al. (2020). Compared with static ways, relevant studies in multiple fields
have shown the effectiveness of DNS for CRL.

However, although DNS can accelerate the convergence speed during training, it
takes more time to calculate or update propensity scores. More importantly,
the hardness of DNS is determined by hyperparameters such as the size of
candidate sampling pool, and hard samples are more likely to become false
negative samples (i.e., positive ones in the future data) than easy negatives.
Therefore, achieving stable results of DNS has been a matter of trial and
error. Actually, hardness is not the aim but the means to get informative
samples, while false negatives are difficult enough with information loss. To
alleviate the false negative problem, DNS usually adopts an indirect way to
avoid the hardest negatives, such as empirically selecting samples whose
scores are within the predefined range Ying et al. (2018), but the problem
remains unresolved. Due to the existence of false negatives, blindly seeking
for harder negative samples may even degrade the performance Cai et al.
(2020), which is the biggest challenge and limitation of DNS.

Algorithm 3 A generalized framework for adversarial NS

Input: $\mathcal{T}=\\{(x,y^{+})\\}$, $G$, $D$
Output: $\theta_{G}$, $\theta_{D}$

1: Initialize or Pretrain $\theta_{G}$ and $\theta_{D}$ for $G$ and $D$;

2: repeat

3: for Discriminator $D$ training do

4: Sample a mini-batch $\mathcal{T}_{batch}$ from $\mathcal{T}$;

5: Generate $y^{-}\sim p_{G}$ for each query $x$ in $\mathcal{T}_{batch}$;

6: Update $\theta_{D}$ to discriminate samples;

7: end for

8: for Generator $G$ training do

9: Sample a mini-batch $\mathcal{T}_{batch}$ from $\mathcal{T}$;

10: Generate $y^{-}\sim p_{G}$ for each query $x$ in $\mathcal{T}_{batch}$;

11: Calculate accuracy $r$ of $D$ on sampled data;

12: Update $\theta_{G}$ to minimize the accuracy $r$;

13: end for

14: until convergence

###  3.3 Adversarial Negative Sampling

Inspired by the popular generative adversarial networks (GAN) Goodfellow et
al. (2014) in recent years, researchers have proposed adversarial negative
sampling methods in multiple domains. The training process of GAN can be
viewed as two players playing a minimax game: one produces fake positive
samples (i.e., the generator), while the other tries to discriminate them from
real positive samples (i.e., the discriminator). The optimization target for
the minimax game can be formalized as follows:

$\mathop{\rm min}\limits_{G}\mathop{\rm
max}\limits_{D}(\mathbb{E}_{p_{data}(y^{+})}[{\rm
log}D(y^{+})]+\mathbb{E}_{p_{G}(y^{-})}[{\rm log}(1-D(G(y^{-}))])$

where $G$ and $D$ denote the generator and the discriminator respectively,
$p_{data}$ is the real data distribution and $p_{G}$ is the pseudo
distribution generated by $G$.

When GAN is applied to negative sampling, the generator usually serves as a
sampler to provide high-quality negative samples for confusing the
discriminator, and adaptively appropriates the underlying distribution of
negative samples with an alternating training procedure. In essence, dynamic
negative sampling can be viewed as a simplified form of adversarial negative
sampling, in which the target model itself plays as the generator to provide
the distribution of negatives. Therefore, the main goal of adversarial
negative sampling is still to generate hard negative samples, and the
adversarial negative sampling can be generalized in Algorithm 3. Based on GAN,
the related methods can be roughly divided into two categories: 1) to select
from existing samples by the generated distribution (i.e., discrete sampling
strategy), and 2) to generate new samples from the continuous embedding space
as hard negatives (i.e., continuous sampling strategy).

#### Discrete Sampling Strategy.

Discrete means the generator just samples discrete indexes of existing samples
instead of generating a vector with continuous values Zhou et al. (2021) like
traditional GANs. As one of the first attempts to apply GAN in information
retrieval, the generator in IRGAN Wang et al. (2017) employs policy gradient
based reinforcement learning to perform discrete negative sampling for
confusing the discriminator, providing a direction for the subsequent
applications such as GraphGAN Wang et al. (2018a) and NMRN Wang et al.
(2018b). Similar methods can also be applied to KGE tasks (e.g., KBGAN Cai and
Wang (2017)), where the generator approximates the score distribution of
candidates to provide discrete negative triples, and the KG embedding model
measures the quality of sampled data. With the help of high-order connectivity
in the knowledge graph (KG), KGPolicy Wang et al. (2020) works as a discrete
sampler and adaptively receives knowledge-aware rewards to provide high-
quality samples for the target RS model.

#### Continuous Sampling Strategy.

Limited by finite samples, the advantage of adversarial training to mine high-
quality negatives cannot be fully exploited by discrete sampling strategy,
while another key research direction is to generate or synthesize negative
samples from the continuous space. Incorporating easy negatives that are often
overlooked, DAML Duan et al. (2018) generates synthetic negative samples
adversarial to the learned metric with regularization, which taps the
potential of adversarial methods to mine hard negatives in the feature space.
Based on top of adversarially sampled negative samples, AdvIR Park and Chang
(2019) generates informational negatives by adding adversarial perturbation to
them. Not confined to the original data, HeGAN Hu et al. (2019) further
leverages a generalized generator to directly sample latent nodes from a
continuous distribution on heterogeneous information networks. In an
adversarial end-to-end manner, AdCo Hu et al. (2021) presents that challenging
negative samples can also be adversarially generated together with the
representation network.

#### Pros and cons.

DNS methods in Section 3.2 can be regarded as some specific forms of GAN-based
NS, with query-aware scorers or positive sample-aware scorers serving as
generators. By formulating the negative sampler and the contrastive learner as
two different models playing a minimax game, GAN-based NS creates more room
for exploring and exploiting high-quality negative samples, in a fully self-
adjusted manner, rather than constrained by some fixed patterns set by
heuristics. However, the additional generator module inevitably causes extra
complexity in computational cost. Besides, the training process of minimax
games are often not stable, so the final ideal equilibrium status can not
always be guaranteed. To make the generator and discriminator play games with
each other instead of unilaterally training, the parameters may need pre-
training Cai and Wang (2017), which further limits efficiency of the model.
Meanwhile, adversarial negative sampling also suffers from false negative
problems like DNS Wang et al. (2020). Solving the inherent problems of
instability and inefficiency for adversarial sampling may lead to a long-
awaited breakthrough.

###  3.4 Efficient Negative Sampling

Besides accuracy, another frequently desired characteristic of NS methods is
the efficiency. In many real-world applications, such as pre-training large
models in NLP or large-scale graph embedding, we cannot simply assume that the
resource is unlimited and the full scope of candidate samples can be freely
accessed. How to conduct efficient NS become an important and practical
question. In this thread, related works can be summarized into two groups.

#### In-Batch Negative Sampling.

An effective way to avoid resource reallocation is to reuse the samples within
the same mini-batch for negative candidates, such as PBG Lerer et al. (2019)
in large-scale graph embeddings and SimCLR Chen et al. (2020) in visual
representation learning. In this case, strategies can still be utilized to
select hard negative samples, such as stratified sampling and negative sharing
for collaborative filtering Chen et al. (2017), and adaptive batch scheduling
(ABS) Choi et al. (2021) for dual encoders. In a distributed environment, a
parallel negative sampling is proposed by GraphVite Zhu et al. (2019) to
cooperate multiple GPUs, which can also be regarded as the in-batch negative
sampling with orthogonal sample blocks. Since batches are generated randomly,
plain in-batch negative sampling is also a variant of RNS considering
efficiency but the candidate set is limited by batch sizes.

#### Caching Mechanism.

Another widely used method is to maintain a cache, such as a memory bank or
queue, to store negative samples with asynchronous update mechanism, so that
the in-batch sampling restriction is eliminated and more negative candidates
can be involved during training. In knowledge graph embedding, NSCaching Zhang
et al. (2019) maintains a cache for the head and tail entity respectively, and
randomly selects negative samples from the cache at each time. In each epoch,
NSCaching updates the memory bank with the model’s current predictive scores
as distribution probability. However, refreshing all samples’ probabilities is
still time-consuming. Momentum Contrast (MoCo) He et al. (2020) further stores
the calculated representations in a queue following the rules of first-in-
first-out (FIFO). Taking dynamic alteration into consideration, just updating
the oldest representations is not enough. Therefore, there is still a trade-
off between efficiency and effectiveness.

##  4 Conclusion and Open Research Directions

This paper presents an overview of negative sampling methods for contrastive
representation learning, with a brief summary in Table 1. We generalize the
task across various fields and systematically divide the existing methods into
four categories. Meanwhile, we discuss the advantages and limitations for each
category of method for better comparisons.

Taking into account the demonstrated challenges as well as the research
progress in negative sampling, we summarize the following open research
directions to advance this field.

#### Alleviating False Negatives.

As mentioned in Section 3.2, the so-called false negatives refer to the
negative samples that will be positive in the future, which poses challenges
for future research on negative sampling approaches. Although it is impossible
to completely eliminate false negatives, some strategies can be employed to
alleviate this problem beyond experimental settings. With a decomposition of
true negative distribution, Chuang et al. Chuang et al. (2020) propose a
contrastive learning goal to mitigate the negative sampling bias with a
decomposition of true negative distribution. The method is empirically
effective but limited to self-supervised learning. On the whole, the
generalized method to eliminate false negatives is still an open problem to be
solved.

#### Integrating Both Easy and Hard Negatives.

Though hard negative samples are critical in model training, it is
inappropriate not to consider easy negative samples at all. Numerous easy
negatives can not only exploited for generating hard negatives Duan et al.
(2018), but also maintain stability in the early training stage. Along with
the training process of the target model, incorporating both the easy and hard
negatives at multiple hard levels may lead to a more fine-grained
representation. CuCo Chu et al. (2021) integrates the concept of curriculum
learning into negative sampling, which sorts the candidates based on the
scoring function and learns from the easy to the difficult successively. In
more fields considering negative sampling, arranging hardness of negative
samples for better model optimization is worth exploring.

#### Trade-off between Quality and Quantity.

Negative sampling approaches are mainly utilized to improve the quality of
negative samples, while the sampling ratio between the positive samples and
the negative ones determines the quantity. SimpleX Mao et al. (2021) proves
that the most basic collaborative filtering method can be better than the
state-of-the-art recommendation algorithm with the help of appropriate
negative sampling ratio and loss function. Based on empirical evidence, more
careful selection of the number and hardness of negative samples can both
benefit CRL, while more or harder negative samples often imply lower
efficiency. To some extent, the quality and quantity of negative samples can
complement each other, which raises a question of balancing between the two.
While there lacks a systematic study to realize the dynamic adjustment, a
quality versus quantity trade-off is also a direction that needs to be fully
explored.

#### Without Negative Sampling.

Considering unresolved trade-offs involved in negative sampling, another
direction is to obviate the need for negative sampling with efficient non-
sampling strategy or even without negative samples. On the one hand, several
methods (e.g., NS-KGE Li et al. (2021)) consider the whole data set as
negative samples with dynamic weights with a controllable time complexity. On
the other hand, without explicitly employing negative pairs over iterations,
BYOL Grill et al. (2020) discards negative samples in self-supervised learning
and imposes additional regularization to avoid collapse of the representation,
which achieves an even better result than negative-dependent methods such as
SimCLR Chen et al. (2020). Therefore, an exciting and promising research
direction is to explore effective ways that can get rid of explicit negative
sampling for CRL.

## References

  * Cai and Wang [2017] Liwei Cai and William Yang Wang.  Kbgan: Adversarial learning for knowledge graph embeddings.  arXiv preprint arXiv:1711.04071, 2017.
  * Cai et al. [2020] Tiffany Tianhui Cai, Jonathan Frankle, David J Schwab, and Ari S Morcos.  Are all negatives created equal in contrastive instance discrimination?  arXiv preprint arXiv:2010.06682, 2020.
  * Caselles-Dupré et al. [2018] Hugo Caselles-Dupré, Florian Lesaint, and Jimena Royo-Letelier.  Word2vec applied to recommendation: Hyperparameters matter.  In ACM Conference on Recommender Systems, pages 352–356, 2018.
  * Chen et al. [2017] Ting Chen, Yizhou Sun, Yue Shi, and Liangjie Hong.  On sampling strategies for neural network-based collaborative filtering.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 767–776, 2017.
  * Chen et al. [2018] Long Chen, Fajie Yuan, Joemon M Jose, and Weinan Zhang.  Improving negative sampling for word representation using self-embedded features.  In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pages 99–107, 2018.
  * Chen et al. [2020] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In ICML, pages 1597–1607. PMLR, 2020.
  * Choi et al. [2021] Donghyun Choi, Myeongcheol Shin, Eunggyun Kim, and Dong Ryeol Shin.  Adaptive batch scheduling for open-domain question answering.  IEEE Access, 9:112097–112103, 2021.
  * Chopra et al. [2005] Sumit Chopra, Raia Hadsell, and Yann LeCun.  Learning a similarity metric discriminatively, with application to face verification.  In CVPR. IEEE, 2005.
  * Chu et al. [2021] Guanyi Chu, Xiao Wang, Chuan Shi, and Xunqiang Jiang.  Cuco: Graph representation with curriculum contrastive learning.  In Proc. IJCAI, 2021.
  * Chuang et al. [2020] Ching-Yao Chuang, Joshua Robinson, Yen-Chen Lin, Antonio Torralba, and Stefanie Jegelka.  Debiased contrastive learning.  Advances in neural information processing systems, 33:8765–8775, 2020.
  * Duan et al. [2018] Yueqi Duan, Wenzhao Zheng, Xudong Lin, Jiwen Lu, and Jie Zhou.  Deep adversarial metric learning.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2018.
  * Gao et al. [2021] Tianyu Gao, Xingcheng Yao, and Danqi Chen.  Simcse: Simple contrastive learning of sentence embeddings.  arXiv preprint arXiv:2104.08821, 2021.
  * Girshick et al. [2014] Ross Girshick, Jeff Donahue, Trevor Darrell, and Jitendra Malik.  Rich feature hierarchies for accurate object detection and semantic segmentation.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 580–587, 2014.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  Advances in neural information processing systems, 27, 2014.
  * Grill et al. [2020] Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Guo, Mohammad Gheshlaghi Azar, et al.  Bootstrap your own latent-a new approach to self-supervised learning.  NIPS, 33:21271–21284, 2020.
  * He et al. [2020] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In CVPR, 2020.
  * Hu et al. [2019] Binbin Hu, Yuan Fang, and Chuan Shi.  Adversarial learning on heterogeneous information networks.  In ACM SIGKDD, pages 120–129, 2019.
  * Hu et al. [2021] Qianjiang Hu, Xiao Wang, Wei Hu, and Guo-Jun Qi.  Adco: Adversarial contrast for efficient learning of unsupervised representations from self-trained negative adversaries.  In CVPR, 2021.
  * Huang et al. [2021] Tinglin Huang, Yuxiao Dong, Ming Ding, Zhen Yang, Wenzheng Feng, Xinyu Wang, and Jie Tang.  Mixgcf: An improved training method for graph neural network-based recommender systems.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 665–674, 2021.
  * Jaiswal et al. [2021] Ashish Jaiswal, Ashwin Ramesh Babu, Mohammad Zaki Zadeh, Debapriya Banerjee, and Fillia Makedon.  A survey on contrastive self-supervised learning.  Technologies, 9(1):2, 2021.
  * Kalantidis et al. [2020] Yannis Kalantidis, Mert Bulent Sariyildiz, Noe Pion, Philippe Weinzaepfel, and Diane Larlus.  Hard negative mixing for contrastive learning.  NIPS, 33:21798–21809, 2020.
  * Le-Khac et al. [2020] Phuc H Le-Khac, Graham Healy, and Alan F Smeaton.  Contrastive representation learning: A framework and review.  IEEE Access, 2020.
  * Lerer et al. [2019] Adam Lerer, Ledell Wu, Jiajun Shen, Timothee Lacroix, Luca Wehrstedt, Abhijit Bose, and Alex Peysakhovich.  Pytorch-biggraph: A large scale graph embedding system.  PMLS, 1:120–131, 2019.
  * Li et al. [2021] Zelong Li, Jianchao Ji, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Chong Chen, and Yongfeng Zhang.  Efficient non-sampling knowledge graph embedding.  In WWW, 2021.
  * Liu et al. [2021] Xiao Liu, Fanjin Zhang, Zhenyu Hou, Li Mian, Zhaoyu Wang, Jing Zhang, and Jie Tang.  Self-supervised learning: Generative or contrastive.  IEEE Transactions on Knowledge and Data Engineering, 2021.
  * Mao et al. [2021] Kelong Mao, Jieming Zhu, Jinpeng Wang, Quanyu Dai, Zhenhua Dong, Xi Xiao, and Xiuqiang He.  Simplex: A simple and strong baseline for collaborative filtering.  In ACM CIKM, 2021.
  * Mikolov et al. [2013] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean.  Distributed representations of words and phrases and their compositionality.  In NIPS, pages 3111–3119, 2013.
  * Oord et al. [2018] Aaron van den Oord, Yazhe Li, and Oriol Vinyals.  Representation learning with contrastive predictive coding.  arXiv preprint arXiv:1807.03748, 2018.
  * Pan et al. [2008] Rong Pan, Yunhong Zhou, Bin Cao, Nathan N Liu, Rajan Lukose, Martin Scholz, and Qiang Yang.  One-class collaborative filtering.  In 2008 Eighth IEEE ICDM, pages 502–511. IEEE, 2008.
  * Park and Chang [2019] Dae Hoon Park and Yi Chang.  Adversarial sampling and training for semi-supervised information retrieval.  In WWW, pages 1443–1453, 2019.
  * Rao et al. [2016] Jinfeng Rao, Hua He, and Jimmy Lin.  Noise-contrastive estimation for answer selection with deep neural networks.  In Proceedings of the 25th ACM International on Conference on Information and Knowledge Management, pages 1913–1916, 2016.
  * Rendle and Freudenthaler [2014] Steffen Rendle and Christoph Freudenthaler.  Improving pairwise learning for item recommendation from implicit feedback.  In Proceedings of the 7th ACM international conference on Web search and data mining, pages 273–282, 2014.
  * Robinson et al. [2020] Joshua Robinson, Ching-Yao Chuang, Suvrit Sra, and Stefanie Jegelka.  Contrastive learning with hard negative samples.  arXiv preprint arXiv:2010.04592, 2020.
  * Schroff et al. [2015] Florian Schroff, Dmitry Kalenichenko, and James Philbin.  Facenet: A unified embedding for face recognition and clustering.  In CVPR, 2015.
  * Shrivastava et al. [2016] Abhinav Shrivastava, Abhinav Gupta, and Ross Girshick.  Training region-based object detectors with online hard example mining.  In CVPR, pages 761–769, 2016.
  * Sun et al. [2018] Zequn Sun, Wei Hu, Qingheng Zhang, and Yuzhong Qu.  Bootstrapping entity alignment with knowledge graph embedding.  In IJCAI, volume 18, 2018.
  * Sun et al. [2019] Zequn Sun, Jiacheng Huang, Wei Hu, Muhao Chen, Lingbing Guo, and Yuzhong Qu.  Transedge: Translating relation-contextualized embeddings for knowledge graphs.  In International Semantic Web Conference, pages 612–629. Springer, 2019.
  * Sung and Poggio [1998] K-K Sung and Tomaso Poggio.  Example-based learning for view-based human face detection.  IEEE Transactions on PAMI, 20(1):39–51, 1998.
  * Tang et al. [2015] Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei.  Line: Large-scale information network embedding.  In WWW, pages 1067–1077, 2015.
  * Wang and Isola [2020] Tongzhou Wang and Phillip Isola.  Understanding contrastive representation learning through alignment and uniformity on the hypersphere.  In ICML, pages 9929–9939. PMLR, 2020.
  * Wang et al. [2017] Jun Wang, Lantao Yu, Weinan Zhang, Yu Gong, Yinghui Xu, Benyou Wang, Peng Zhang, and Dell Zhang.  Irgan: A minimax game for unifying generative and discriminative information retrieval models.  In ACM SIGIR, pages 515–524, 2017.
  * Wang et al. [2018a] Hongwei Wang, Jia Wang, Jialin Wang, Miao Zhao, Weinan Zhang, Fuzheng Zhang, Xing Xie, and Minyi Guo.  Graphgan: Graph representation learning with generative adversarial nets.  In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
  * Wang et al. [2018b] Qinyong Wang, Hongzhi Yin, Zhiting Hu, Defu Lian, Hao Wang, and Zi Huang.  Neural memory streaming recommender networks with adversarial training.  In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2467–2475, 2018.
  * Wang et al. [2019] Xiang Wang, Xiangnan He, Meng Wang, Fuli Feng, and Tat-Seng Chua.  Neural graph collaborative filtering.  In Proceedings of the 42nd international ACM SIGIR conference on Research and development in Information Retrieval, pages 165–174, 2019.
  * Wang et al. [2020] Xiang Wang, Yaokun Xu, Xiangnan He, Yixin Cao, Meng Wang, and Tat-Seng Chua.  Reinforced negative sampling over knowledge graph for recommendation.  In Proceedings of The Web Conference 2020, 2020.
  * Weston et al. [2010] Jason Weston, Samy Bengio, and Nicolas Usunier.  Large scale image annotation: learning to rank with joint word-image embeddings.  Machine learning, 81(1):21–35, 2010.
  * Xiong et al. [2020] Lee Xiong, Chenyan Xiong, Ye Li, Kwok-Fung Tang, Jialin Liu, Paul Bennett, Junaid Ahmed, and Arnold Overwijk.  Approximate nearest neighbor negative contrastive learning for dense text retrieval.  arXiv preprint arXiv:2007.00808, 2020.
  * Ying et al. [2018] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In ACM SIGKDD, 2018.
  * Zhang and Zweigenbaum [2018] Zheng Zhang and Pierre Zweigenbaum.  Gneg: Graph-based negative sampling for word2vec.  In Annual Meeting of the Association for Computational Linguistics, pages 566–571, 2018.
  * Zhang et al. [2013] Weinan Zhang, Tianqi Chen, Jun Wang, and Yong Yu.  Optimizing top-n collaborative filtering via dynamic negative item sampling.  In ACM SIGIR, 2013.
  * Zhang et al. [2019] Yongqi Zhang, Quanming Yao, Yingxia Shao, and Lei Chen.  Nscaching: simple and efficient negative sampling for knowledge graph embedding.  In 2019 IEEE 35th ICDE, pages 614–625. IEEE, 2019.
  * Zhou et al. [2021] Yao Zhou, Jianpeng Xu, Jun Wu, Zeinab Taghavi, Evren Korpeoglu, Kannan Achan, and Jingrui He.  Pure: Positive-unlabeled recommendation with generative adversarial network.  In ACM SIGKDD, 2021.
  * Zhu et al. [2019] Zhaocheng Zhu, Shizhen Xu, Jian Tang, and Meng Qu.  Graphvite: A high-performance cpu-gpu hybrid system for node embedding.  In WWW, 2019.