# An Integrated Real-time UAV Trajectory Optimization with Potential Field
Approach for Dynamic Collision Avoidance

D. M. K. K. Venkateswara Rao, Hamed Habibi Member, IEEE, Jose Luis Sanchez-
Lopez, and Holger Voos This research was partially supported by the European
Union’s Horizon 2020 project Secure and Safe Multi-Robot Systems (SESAME)
under the grant agreement no. 101017258 and by the Department of Media,
Telecommunications and Digital Policy (SMC) of the Government of the Gran
Duchy of Luxembourg under the project reference SMC/CFP-2019/010/IRANATA,
”Interference and RAdiation in Network PlAnning of 5G AcTive Antenna
Systems.”D. M. K. K. Venkateswara Rao, H. Habibi, J. L. Sanchez-Lopez, and H.
Voos are with Automation and Robotics Research Group, Interdisciplinary Centre
for Security, Reliability and Trust, University of Luxembourg, Luxembourg. H.
Voos is also with Faculty of Science, Technology and Medicine (FSTM),
Department of Engineering, University of Luxembourg,
{mohan.dasari,hamed.habibi,holger.voos,
<EMAIL_ADDRESS>
###### Abstract

This paper presents an integrated approach that combines trajectory
optimization and Artificial Potential Field (APF) method for real-time optimal
Unmanned Aerial Vehicle (UAV) trajectory planning and dynamic collision
avoidance. A minimum-time trajectory optimization problem is formulated with
initial and final positions as boundary conditions and collision avoidance as
constraints. It is transcribed into a nonlinear programming problem using
Chebyshev pseudospectral method. The state and control histories are
approximated by using Lagrange polynomials and the collocation points are used
to satisfy constraints. A novel sigmoid-type collision avoidance constraint is
proposed to overcome the drawbacks of Lagrange polynomial approximation in
pseudospectral methods that only guarantees inequality constraint satisfaction
only at nodal points. Automatic differentiation of cost function and
constraints is used to quickly determine their gradient and Jacobian,
respectively. An APF method is used to update the optimal control inputs for
guaranteeing collision avoidance. The trajectory optimization and APF method
are implemented in a closed-loop fashion continuously, but in parallel at
moderate and high frequencies, respectively. The initial guess for the
optimization is provided based on the previous solution. The proposed approach
is tested and validated through indoor experiments.

Experiment video link: https://youtu.be/swSspfvYjJs

###### Index Terms:

Artificial Potential Field, Dynamic Collision Avoidance, Pseudospectral
Method, Trajectory Optimization, UAV.

##  I Introduction

Trajectory planning is one of the most important features for autonomous
Unmanned Aerial Vehicle (UAV) in cluttered environments, defined as a time-
parameterized motion reference, i.e., geometric values of position, heading,
derivatives associated with time law, passing through the waypoints,
considering geometrical feasibility, collision avoidance, kinematics and
dynamics [1]. One of the main objectives of the trajectory planner is
collision avoidance with obstacles, humans, and other robots. These,
generally, can be titled as static and dynamic obstacles [2]. So, the
information on the obstacles is to be implemented into the proposed solution.
Collision avoidance is considered as the geometrical feasibility of the
planning. Most of the planning approaches are constructed as an on/offline
optimization problem, obtaining a trajectory with the optimized feature [3].
Mostly, the time that the UAV takes between two given points is minimized,
aiming at the agile maneuver. More importantly, the real-time implementation
is more desirable for navigation in dynamic environments [4, 5]. This implies
the need for an algorithm that converges to a feasible solution with a low
computational burden. In terms of technical development, the representation of
the optimization problem with the considered constraints usually determines
the reliability of the solution in practice.

Trajectory optimization has been widely investigated in the last two decades
[6]. Hard-constrained methods are pioneered, in which piecewise polynomial
trajectories are generated through quadratic programming [7]. Free space can
be represented by a sequence of cubes [8], spheres [3] or polyhedrons [9].
Improper time allocation of polynomials, e.g., naive heuristics, leads to
unsatisfying results. Fast marching [10] and kinodynamic [11, 10] are used to
find a feasible initial guess, ensuring global optimality by the convex
formulation. However, distance to obstacles in the free space is ignored,
which often results in trajectories being close to obstacles. Moreover,
kinodynamic constraints are conservative, making the trajectory’s speed
deficient for fast flight [12]. A feasible solution can only be obtained by
iteratively adding more constraints and solving the quadratic programming
problem, which is undesirable for real-time applications.

Soft-constrained methods translate the problem to a non-linear optimization
problem with smoothness and safety [13]. Since the time parameterization is
continuous, it avoids numeric differentiation errors, with more accuracy to
represent motions. However, it suffers from a low success rate. As a
resolution, in [14] a feasible initial path is found using an informed
sampling-based path-searching method. In [15], uniform B-spline is used for
the trajectory parameterization, as B-spline is continuous by nature, the
continuity constraint is avoided. Moreover, it is beneficial for local re-
planning, due to its locality property. Soft-constrained methods might stick
in local minima and cannot guarantee of success rate and kinodynamic
feasibility.

Gradient-based method is the mainstream approach [4, 5], as a non-linear
optimization, taking into account smoothness, feasibility, and safety using
various parameterization methods, including polynomial and B-spline. The
computation time can be reduced by compact environment representation [16].
Furthermore, it is effective for local re-planning, which is useful for high-
speed flight in unknown environments. However, the local minima are still an
issue. The stochastic sampling strategy partially overcomes this issue with
the cost of computationally intensive [17]. The quality of the initial guess
can improve the success rate [14]. [18] used an iterative post-process to
improve the success rate of [19].

Topological path planning method utilises the idea of topologically distinct
paths for planning, in which paths belonging to different homotopy are used to
escape local minima. Trajectory planning is presented in [20] in distinctive
topologies using Voronoi and sampling-based front-ends and Timed-Elastic-Bands
local planner [21] as back-ends. Based on [22], in [4] a real-time topological
planning is proposed by efficient topology equivalence checking. In most of
the similar works, collision avoidance in dynamic environments is considered,
considering the velocity of obstacles [23], decentralized Nonlinear Model
Predictive Control (NMPC) [24] and sequential NMPC [25]. Uncertainties can be
handled by enlarging bounding volumes [26], which might lead to conservative
or infeasible solutions. Moreover, the chance-constrained approaches are
computationally intensive and thus not eligible for real-time collision
avoidance [27].

Motivated by the above-mentioned considerations, in this paper we design an
integrated solution for trajectory optimization with the Artificial Potential
Field (APF), satisfying real-time minimum-time UAV trajectory planning and
dynamic collision avoidance. The problem is transcribed into a nonlinear
programming problem using Chebyshev pseudospectral methods. The state and
control histories are approximated by using Lagrange polynomials and
collocation is used to satisfy the dynamics constraints. The obstacle
avoidance constraint is modelled by a novel sigmoid function to overcome the
drawbacks of Lagrange polynomial approximation in pseudospectral methods that
only guarantees inequality constraint satisfaction only at nodal points. It
also guarantees the feasibility of the optimization problem. Furthermore, to
reduce the computational complexity, automatic differentiation is used to
obtain the gradient of cost function and Jacobian of constraints. An APF
method is used to update the optimal control inputs for guaranteeing collision
avoidance. The proposed framework structure can overcome convergence issues,
by having the components run in parallel but at moderate and high frequencies.

The rest of the paper is organized as follows. The UAV dynamics model,
optimization formulation, and NLP transcription are covered in Sec. II. Sec.
III comprises the novel constraint formulation for collision avoidance, the
APF method for guaranteed collision avoidance, and computational
implementation. The proposed architecture is also presented. Indoor lab setup,
and experimental results are presented in IV. Finally, the paper ends with
conclusions in Sec. V.

##  II Problem Formulation and Preliminaries

###  II-A Dynamics Model

Consider an approximate dynamics model for the UAV as a first-order dynamics
system in terms of the position vector
$\underline{x}(t)=[x(t),y(t),z(t)]^{T}\in\mathbb{R}^{3}$ and commanded
position vector
$\underline{u}_{cmd}(t)=[x_{cmd}(t),y_{cmd}(t),z_{cmd}(t)]^{T}\in\mathbb{R}^{3}$,
both presented in the inertial frame of reference, as

$\dot{\underline{x}}(t)=diag(K_{x},K_{y},K_{z})\left(\underline{u}_{cmd}(t)-\underline{x}(t)\right),$
(1)

where $K_{x}$, $K_{y}$, and $K_{z}$ are constant dynamics gains.

The model (1) assumes that the position of the UAV converges to the commanded
position asymptotically [1]. The low-level controller in the autopilot
computes the required motor inputs based on the error between current and
commanded positions, with desirable performance.

###  II-B Optimization Problem Formulation

The trajectory planning problem is to determine the control inputs required to
transfer the UAV from the given initial to final positions in minimum time.
The trajectory planning problem is formulated to determine optimal position
vector
$\underline{x}_{opt}(t)=[x_{opt}(t),y_{opt}(t),z_{opt}(t)]^{T}\in\mathbb{R}^{3}$
and corresponding commanded position vector $\underline{u}_{cmd}(t)$, such
that to steer $\underline{x}(t)$ towards $\underline{x}_{opt}(t)$, in minimum
time, starting from the initial position
$\underline{x}(t_{0})=\underline{x}_{0}\in\mathbb{R}^{3}$ to the final
position $\underline{x}(t_{f})=\underline{x}_{f}\in\mathbb{R}^{3}$, where
$t_{f}$ is the unknown terminal time. Also, it is aimed to avoid $n_{o}$
moving obstacles with the position vector
$\underline{x}_{obs,k}(t)=[x_{obs,k}(t),y_{obs,k}(t),z_{obs,k}(t)]^{T}\in\mathbb{R}^{3}$,
for $k\in\\{1,...,n_{o}\\}$, by keeping the UAV outside of safety spheres,
considered around the obstacles. Furthermore, there are $n_{w}$ waypoints that
UAV is supposed to pass through before reaching $\underline{x}_{f}$. This
optimization problem is mathematically formulated as

$[\underline{x}_{opt}(t),\underline{u}_{cmd}(t)]=\operatornamewithlimits{argmin}_{\underline{u}_{cmd}(t)}{J\left(x(t),\underline{u}_{cmd}(t),\underline{x}_{0},\underline{x}_{f}\right)},$
(2)

where

$J(\cdot)=t_{f}\left(\underline{x}(t),\underline{u}_{cmd}(t),\underline{x}_{f}\right)-t_{0},$
(3)

subject to dynamics (1) and boundary conditions

$\displaystyle\underline{x}(t_{0})$ $\displaystyle=\underline{x}_{0},$ (4a)
$\displaystyle\underline{x}(t_{f})$ $\displaystyle=\underline{x}_{f},$ (4b)
$\displaystyle\underline{x}(t_{j})$ $\displaystyle=w_{j},$ (4c)

bound constraints on position and speed

$\displaystyle\underline{x}_{L}\leq\underline{x}(t)\leq\underline{x}_{U}$ (5a)
$\displaystyle\underline{u}_{L}\leq\underline{u}_{cmd}(t)\leq\underline{u}_{U}$
(5b)
$\displaystyle\underline{\dot{x}}_{L}\leq\underline{\dot{x}}(t)\leq\underline{\dot{x}}_{U}$
(5c)

and obstacle avoidance constraints

$\displaystyle R_{k}\leq\norm{\underline{x}(t)-\underline{x}_{obs,k}(t)},$ (6)

for $j\in\\{1,...,n_{w}\\}$ and $k\in\\{1,...,n_{o}\\}$, where, $t_{0}\leq
t_{j}\leq t_{f}$, are increasing time sequence, and
$w_{j}=[x_{j}(t),y_{j}(t),z_{j}(t)]^{T}\in\mathbb{R}^{3}$ is the position of
the $j^{th}$ waypoint. $X_{L}$ and $X_{U}$ denote the element-wise lower and
upper bound vectors on the variable vector $X(t)$. Finally, $R_{k}$ for
$k\in\\{1,...,n_{o}\\}$, represents safety radius of $k^{th}$ obstacle. In
fact, $R_{k}\leq\norm{x(t)-x_{obs,k}(t)}$ imposes the constraint to keep the
position of the UAV outside of the safety sphere around the obstacle.

###  II-C NLP Transcription:

The continuous-time trajectory optimization problem (2) is transcribed into a
nonlinear programming (NLP) problem using Chebyshev pseudospectral method
[28]. In this method, the state and control histories between the initial and
final waypoints are approximated by Lagrange polynomials in non-
dimensionalized time, as illustrated in Figure 1

$\displaystyle{\underline{x}}(\tau)\approx\sum_{i=1}^{n}{\underline{x}}_{i}\phi_{i}(\tau),$
(7a)
$\displaystyle{\underline{u}}_{cmd}(\tau)\approx\sum_{i=1}^{n}\underline{u}_{i}\phi_{i}(\tau),$
(7b)

where $\tau\in[0,1]$ is the non-dimensionalized time; $n$ is the order of the
polynomial; $\underline{x}_{i}$ and $\underline{u}_{i}$ are state and control
approximation vectors at nodes; $i$ denotes node number; and $\phi_{i}(\tau)$
is the basis function given by

$\displaystyle\phi_{i}(\tau)=\prod_{j=1,j\neq
i}^{n}\frac{\tau-\tau_{j}}{\tau_{i}-\tau_{j}},$ (8)

where $\tau_{i}$ and $\tau_{j}$ are roots of shifted Chebyshev polynomials
obtained by

$\displaystyle\tau_{i}=\frac{1+\tilde{\tau}_{i}}{2}.$ (9)

The roots of the Chebyshev polynomial are determined as

$\displaystyle\tilde{\tau}_{i}=\cos\left(\pi k/n\right),~{}~{}~{}k=0,1,...,n$
(10)

Let $\Delta t$ be the maneuver time. The actual and non-dimensionalized times
are related as

$\displaystyle\tau$ $\displaystyle=\frac{t}{\Delta t},$ (11) $\displaystyle
d\tau$ $\displaystyle=\frac{dt}{\Delta t}.$ (12)

The Lagrange polynomials are collocated at the interpolation points to result
in a set of algebraic equations

$\underline{x}_{i}\dot{\phi}_{i}(\tau)=\dot{\underline{x}}(\tau).$ (13)

This can be rewritten as

$\sum_{i=1}^{n}\underline{x}_{i}\dot{\phi}_{i}(\tau)=\Delta
tf(\underline{x}_{i},\underline{u}_{i}).$ (14)

Then, the cost function $J$, in (2) reduces to

$\displaystyle J=\Delta t.$ (15)

Figure 1: Illustration of trajectory approximation using Chebyshev
pseudospectral method.

The problem (2) with cost function (15) with boundary conditions (4), bound
constraints (5), and obstacle avoidance constraints (6), constitute the NLP
problem. This NLP problem is solved using interior point algorithm [29]
implemented in IPOPT solver [30] interfaced with Matlab. Moreover, CasADi [31]
is used for the automatic differentiation to determine the gradient and
Jacobian of cost function and constraints, respectively, for speeding up the
computation of the solution, which is vital for real-time implementation.

##  III Collision Avoidance

In this section the modifications applied to the optimization problem (15),
are addressed that guarantee the feasibility of the problem and the fast
convergence of the solver, aiming at the real-time re-optimization. The
overall computational architecture is presented in Figure 2.

Figure 2: Computational architecture.

###  III-A Constraints Formulation

To apply the obstacle avoidance constraint (6) to the collocation points, the
common condition to be checked is the distance of the points from $i^{th}$
obstacle to be greater than the safety radius $R_{i}$ for
$i\in\\{1,...,n_{o}\\}$. However, this might lead to the safety violation as
illustrated in Figure 3. Evidently, the collocation points $C_{j,1}$ and
$C_{j,2}$ are outside of the safety sphere, i.e., $r_{i,j,1}>R_{i}$ and
$r_{i,j,2}>R_{i}$. However, the line segment $\overline{C_{j,1}C_{j,2}}$ is
still passing through the safety sphere. The trivial solution is to increase
the number of collocation points and apply the distance constraint. However,
this increases the computational burden. More importantly, it is still not
geometrically guaranteed that connecting lines are moved outside.

Figure 3: Violation of safety region for the case the waypoints and
collocation points are still outside.

A resolution is to consider the perpendicular distance for each line segment
from the obstacle, i.e., $d_{i,j,k}$, for $k=0,\ldots,N$, where $N$ represents
the number of collocation points, $C_{j,0}=w_{j}$ and $C_{j,N+1}=w_{j+1}$, as
illustrated in Figure 4, where, $d_{i,j,k}$, for $k=0,\ldots,4$, are all same
for all the segments, as they are on the same straight line. Considering only
perpendicular distance as the constraint $d_{i,j,k}>R_{i}$ leads to a very
conservative approach, as it moves all points $C_{j,1}$ and $C_{j,4}$ to
satisfy the constraint, as shown in Figure 5. This takes a lot of workspace
and might lead to an infeasible optimization problem after applying the other
constraints. Therefore, we only need the constraint to be applied to $C_{j,2}$
and $C_{j,3}$ in Figure 5, as they lie within the safety sphere. The solution
we propose is to first check if the projection of $i^{th}$ obstacle position
on the line segment $\overline{C_{j,k}C_{j,k+1}}$ lies on the segment or its
extension. To do so, we compute

$t_{i,j,k}=\frac{\left(\underline{x}_{obs,i}-C_{j,k}\right).\left(C_{j,k+1}-C_{j,k}\right)}{\left(C_{j,k+1}-C_{j,k}\right).\left(C_{j,k+1}-C_{j,k}\right)},$
(16)

where $\cdot$ represents the inner product. If $0<t_{i,j,k}<1$, then the
projection point is on the line segment $\overline{C_{j,k}C_{j,k+1}}$.
Otherwise, it is on its extension. Accordingly, the collision avoidance
constraint, illustrated in Figure 7, is as follows.

if $0<t_{i,j,k}<1$ $\&$ $d_{i,j,k}<R_{i}$ then

Move the $C_{j,k}$ , for $k=1,\ldots,N$, such that
$\overline{C_{j,l}C_{j,l+1}}$, for $l=0,\ldots,N$ is outside of the safety
sphere.

end if

Figure 4: Perpendicular distance check. Figure 5: Applying the perpendicular
distance check to all the points. The points with superscript (′) represent
the new position of the points in grey. Figure 6: Applying the projection
point check.

This approach theoretically solves the mentioned problem, however, it imposes
a practical implementation issue. This stems from the presence of the _if_
condition in the construction of constraints which is a common approach for
obstacle avoidance constraints [5]. Using _if_ condition changes the structure
and size of the constraints at every iteration. This is due to the fact that
by moving collocation points, the constraint might be satisfied and it is
removed from the constraints matrix. More importantly, _if_ condition is not a
smooth condition which might make a problem with the convergence of the
solver. To resolve this problem, we propose a smooth constraint avoiding the
use of _if_ condition, as

$f_{i,j,k}:=\frac{1}{2}\Gamma_{i,j,k}\left(R_{i}-d_{i,j,k}\right)\leq 0,$ (17)

where
$\Gamma_{i,j,k}=\tanh{\left(\frac{t_{i,j,k}}{\delta}\right)-}\tanh{\left(\frac{t_{i,j,k}-1}{\delta}\right)}$
and $\delta>0$ is a small scalar. It is readily shown that for
$0<t_{i,j,k}<1$, $\Gamma_{i,j,k}\approx 1$. Therefore,
$f_{i,j,k}=R_{i}-d_{i,j}$. Then the constraint $f_{i,j,k}\leq 0$ is equivalent
to $R_{i}-d_{i,j,k}\leq 0$. On the other hand, for $t_{i,j,k}\leq 0$ or $1\leq
t_{i,j,k}$, the term $\Gamma_{i,j,k}=0$ and, hence, $f_{i,j,k}=0$. Moreover,
the condition $0\leq 0$ is already satisfied in numerical solvers and it does
not apply the distance constraint on the points $C_{j,k}$ and $C_{j,k+1}$. So,
the constraint (17) encapsulates both conditions for the line segment on which
the projection point lies, without using _if_ condition. More importantly,
this constraint is smooth at points $t_{i,j,k}=0$ and $t_{i,j,k}=1$.
$f_{i,j,k}$ is illustrated in Figure for $\delta=0.05$ and $R_{i}=1.5$.

Figure 7: Smooth obstacle avoidance constraint.

Another improvement to guarantee real-time feasibility with fast convergence
is to make sure, the initial guess does not go through the safety sphere. To
address this, we first radially move the collocation points of the initial
guess out of the sphere. For each point, we check if it is inside of the
sphere, if so, that point is moved in the direction of the carrying radius,
i.e., connecting the centre to the point. However, this does not necessarily
guarantee that the connecting line does not pass through the sphere.
Therefore, we can consider the perpendicular distance of the centre to each
line. However, just moving all the points according to the perpendicular
distance might make lead to a conservative initial guess which is away from
the optimal solution. So, we only move the lines, on which the projection
point lies, not on their extension, in the perpendicular direction. This
improvement might make the initial guess non-smooth and longer than the direct
connecting line. So, finally, we shorten the guess, i.e., we check if the
direct line between the collocation points pas through the sphere. if not, the
direct line is replaced.

###  III-B Artificial Potential Field

An APF method using sigmoid function [32] is used to make minor corrections to
the optimal control inputs to improve safety and guarantee collision avoidance
in case of any unexpected delays in the computation of the optimization
solution. In the case of any unexpected delay in communication or convergence
issue, this ensures obstacle avoidance and safety. APF method, as illustrated
in Figure 8, creates a virtual field around the obstacle that increases or
decreases in strength as the distance to it decreases or increases,
respectively. In this paper, the sigmoid function is used to design the APF,
as

$\displaystyle F_{k}(t)$ $\displaystyle=\frac{1}{2}\left(1+tanh(\alpha
R_{k}-\norm{r_{k}(t)})\right)-\eta$ (18)

for $k\in\\{1,...,n_{o}\\}$, where $F_{k}(t)$ is the repelling force, $\alpha$
and $\eta$ are tuning parameters, and
$r_{k}(t)={\underline{x}(t)-\underline{x}_{obs,k}(t)}$. By solving the
optimization problem (2) with cost function (15) with boundary conditions (4),
bound constraints (5), and obstacle avoidance constraints (17), the optimal
control inputs, i.e. $\underline{u}_{opt}(t)$, is obtained. Then
$\underline{u}_{cmd}(t)$ is obtained by modifying $\underline{u}_{opt}(t)$
with the repelling force from APF, as

$\displaystyle\underline{u}_{cmd}(t)$
$\displaystyle=\underline{u}_{opt}(t)+\sum_{k=1}^{n_{o}}F_{k}(t)\frac{r_{k}(t)}{\norm{r_{k}(t)}}.$
(19)

Figure 8: Illustration of APF for $\alpha=1.875$ and $\eta=0.029$.

###  III-C Parallelization

APF (18) can be implemented at a very high frequency due to its simplicity.
However, solving the optimization problem (2) is numerically expensive. It
should be noted that it is not always required to solve the optimization
problem at a high rate, and the trajectory can be slightly modified by APF.
Therefore, we propose to implement these two components to run simultaneously
in parallel, with different frequencies. In fact, the higher frequency of APF
always guarntees the obstacle avoidance and, hence, the safety of the
solution. The proposed parallelization is shown in a pseudocode in Table I.

At first, the optimization problem is solved once by defining the initial
guess and boundary conditions based on the initial and final UAV positions and
obstacle location. Then, parallel implementation of the two methods begins in
a while loop. If no optimization code is running, the control inputs at
initial time $(t=0)$ are obtained from the solution and are treated as inputs
to be commanded. The optimization solution along with the co-state multipliers
are used to make a new initial guess. The initial boundary condition is
updated based on the new UAV position and the optimization solver begins
running in the background until a new solution is computed. The APF method is
used to determine the necessary repulsive corrections to the initial control
inputs, obtained from the optimization solution, and it is commanded to the
UAV. The process is repeated until the UAV reaches its desired position.

TABLE I: Pesudocode for Optimization and APF Parallelization. | Initialization
---|---
1. |  $\underline{x}(0)\leftarrow\underline{x}_{0}$ Initial condition
2. |  $\underline{x}(t_{f})\leftarrow\underline{x}_{f}$ Final condition
3. | Solve an initial NLP
4. | $d(t)\leftarrow\norm{\underline{x}_{f}-\underline{x}(t)}$
| Start parallelization
5. |  while $d(t)>Threshold$, do
6. |  if NLP solved
7. |  $\underline{u}_{opt}\leftarrow\underline{u}(0)$
8. |  $\underline{x}(0)\leftarrow\underline{x}_{uav}$
9. |  $\underline{x}(t_{f})\leftarrow\underline{x}_{f}$
10. |  Solve NLP in background
11. |  end
12. |  Compute (19)
13. |  Command $\underline{u}_{cmd}(t)$ to UAV dynamics (1)
14. |  $d(t)\leftarrow\norm{\underline{x}_{f}-\underline{x}(t)}$
15. | end

##  IV Experimental Results and Discussion

###  IV-A Experimental Setup

The setup of the UAV used for the experiments in this paper, onboard
components, indoor positioning system, and communication network is
illustrated in Figure 9. The UAV is a quadrotor vehicle, equipped with Pixhwak
CUAV V5 Nano autopilot running the PX4 operating system. It also has a small
onboard computer, Raspberry Pi Model B, running an Ubuntu server. The obstacle
is a small DJI Tello drone. Positioning of the UAV and obstacle is carried out
by the Optitrack system, which comprises 12 infrared cameras fixed to the
ceiling at a height of around 5 $m$ and a high-performance desktop computer
running Motive software. The Optitrack system is calibrated to detect the
circular reflective markers fixed on the UAV and obstacle asymmetrically and
determines their position and orientation with respect to a predefined FLU
inertial coordinate system at a frequency of 120 Hz. The UAV’s onboard
computer runs roscore and acts as an interface for communication between the
Optitrack system, autopilot, and the ground control station (GCS). It receives
the position and orientation from the Motive software over WiFi and relays it
to mavros node. The mavros node further sends it to the autopilot, which
internally fuses it with the IMU’s high-frequency acceleration, and angular-
rate measurements and receives the PX4-estimated position, and orientation in
the inertial frame to make it available to GCS. The GCS initiates ROS in
Matlab and has access to all the ROS topics, including obstacle’s pose, UAV’s
pose, and IMU data published by mavros. The trajectory optimization code runs
in Matlab to determine the control inputs. The computed control inputs are
commanded to the UAV by publishing them to relevant topics in mavros, which
relays them to the autopilot. The Tello drone is controlled by a separate
computer interfaced with both Tello and Optitrack system simultaneously by
Tello’s WiFi and ethernet connections, respectively. A custom ROS node is
developed to interface with the Tello driver and gain access to its control.

Figure 9: Illustration of the UAV positioning and control network architecture
in the lab.

a)  b)

Figure 10: Evolution of UAV trajectories with respect to moving obstacle: a)
$t\in[0.3,9.33]$ and b) $t\in[96.03,103.86]$.

###  IV-B Experimental Results

A single Tello drone is used as a dynamic obstacle and controlled to fly in a
circular trajectory at an angular speed of 1.0 $rad/s$. The radius, height,
and yaw angle were maintained to be constant at 0.5 $m$, 0.75 $m$, and zero
$deg$, respectively. Two points $(-1.5,-1.5,0.75)$ and $(1.5,1.5,0.75)$ in the
FLU frame of reference are chosen as the boundary points. The values of
$\alpha$ and $\eta$ in (18) are chosen as 1.875 and 0.029, respectively.

The UAV is commanded to take off and reach the first boundary point. Once it
reached, the trajectory optimization and APF method run in parallel
iteratively. In the first iteration, an optimal trajectory is computed with
boundary conditions and constraints defined appropriately. To prevent abrupt
accelerations to UAV, the initial velocity is constrained not to have large
values. The initial control input obtained from the optimization solution was
corrected using APF method and commanded to the UAV. In the second iteration,
a new optimization problem is created with the new UAV and obstacle positions.
By using the warmstart feature of IPOPT, the optimization solution and
corresponding co-state multipliers of constraints from the first iteration are
specified as the initial guess. The optimization problem runs in the
background using the parfeval function in Matlab. The initial control input
from the first iteration is still used to make corrections using APF method
and commanded. In the subsequent iterations, it was checked if the
optimization code running in the background is solved or not. If so, the
routine in the second iteration is repeated. Otherwise, only the APF method is
implemented. Process is repeated until the UAV reached its final point.

To ensure that the proposed approach is robust and works for different
obstacle positions and approaching scenarios, the UAV is continued to fly even
after reaching the final point. However, the boundary points were switched.
Based on the experimental analysis, the optimization solver is so robust in
computing the solution. Every time the boundary points are switched, the
solution from the previous iteration is an incorrect initial guess. However,
the solver is able to compute a new solution without any noticeable delays.

The experiment was carried out for 150 seconds. Throughout the experiment, the
UAV was able to fly back and forth between the two boundary points without
having any collision with the moving obstacle. UAV trajectories and optimal
trajectories computed from 135 $s$ to the end were recorded in a
video111https://youtu.be/swSspfvYjJs. It should be noted that $y$ and $x$ axes
in the figure correspond to $F$ and $-L$ axes in the FLU frame of reference.
This was done to have consistency between the UAV motion in the video and the
plotting axes. During the experiment, the optimization solver was able to run
at a frequency of around 10 Hz. The APF method was run at around 60 Hz.
Despite the differences in the frequencies of their runtime, it appears that
the trajectories are getting updated in real-time without any noticeable
delays. The APF method can run at a much higher frequency, but most of the
time was consumed reading messages from ROS topics and publishing the control
commands.

The paths and trajectories of the UAV and the obstacle from 0.3 to 9.33 $s$
and 96.03 to 103.86 $s$ are presented in Figure 10. It can be seen that the
UAV and obstacle trajectories (shown as circular disks) never intersected with
each other. At the beginning of the maneuver in both cases, the obstacle was
not on the line segment joining the two boundary points. Therefore, the
computed optimal trajectory was a straight line. During the course of the
maneuver, the obstacle started approaching the UAV and intersecting its path.
The optimization solver was able to quickly compute new trajectories avoiding
the obstacle. As soon as the obstacle started moving away from the UAV, the
computed trajectories became almost straight again. The UAV continued reaching
its final point along this straight line. Occasionally, slightly curved
trajectories are computed due to the effects of the sub-optimal previous
solution chosen as the initial guess. Overall, the proposed approach and the
computational framework developed were shown to work effectively for real-time
optimal UAV trajectory planning and dynamic collision avoidance.

##  V Conclusions

In this paper, we presented an approach for real-time optimal UAV trajectory
planning in the presence of dynamic obstacles, combining trajectory
optimization with APF method. The optimization problem minimized the flying
time between the initial and final positions. We transcribed the problem into
a nonlinear programming problem using Chebyshev pseudospectral method. The
state and control histories are approximated by using Lagrange polynomials and
Chebyshev nodes. More importantly, we presented a novel sigmoid-type collision
avoidance constraint. Automatic differentiation of cost function and
constraints were used for fast convergence. The APF method was for
guaranteeing collision avoidance. We also presented a parallel architecture
running at moderate and high frequencies. Indoor experiments were conducted
which confirmed the effectiveness of the proposed approach.

## References

  * [1] M. Castillo-Lopez, P. Ludivig, S. A. Sajadi-Alamdari, J. L. Sanchez-Lopez, M. A. Olivares-Mendez, and H. Voos, “A real-time approach for chance-constrained motion planning with dynamic obstacles,” IEEE Robot. Autom. Lett., vol. 5, no. 2, pp. 3620–3625, 2020.
  * [2] J. L. Sanchez-Lopez, M. Castillo-Lopez, M. A. Olivares-Mendez, and H. Voos, “Trajectory tracking for aerial robots: an optimization-based planning and control approach,” J. Intell. Robot. Syst., vol. 100, no. 2, pp. 531–574, 2020.
  * [3] F. Gao, W. Wu, W. Gao, and S. Shen, “Flying on point clouds: Online trajectory generation and autonomous navigation for quadrotors in cluttered environments,” Journal of Field Robotics, vol. 36, no. 4, pp. 710–733, 2019.
  * [4] B. Zhou, F. Gao, J. Pan, and S. Shen, “Robust real-time uav replanning using guided gradient-based optimization and topological paths,” in 2020 IEEE International Conference on Robotics and Automation (ICRA), pp. 1208–1214, IEEE, 2020.
  * [5] X. Zhou, J. Zhu, H. Zhou, C. Xu, and F. Gao, “Ego-swarm: A fully autonomous and decentralized quadrotor swarm system in cluttered environments,” in 2021 IEEE International Conference on Robotics and Automation (ICRA), pp. 4101–4107, IEEE, 2021.
  * [6] M. Hoy, A. S. Matveev, and A. V. Savkin, “Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey,” Robotica, vol. 33, no. 3, pp. 463–497, 2015.
  * [7] C. Richter, A. Bry, and N. Roy, “Polynomial trajectory planning for aggressive quadrotor flight in dense indoor environments,” in Robotics research, pp. 649–666, Springer, 2016.
  * [8] J. Chen, K. Su, and S. Shen, “Real-time safe trajectory generation for quadrotor flight in cluttered environments,” in 2015 IEEE International Conference on Robotics and Biomimetics (ROBIO), pp. 1678–1685, IEEE, 2015.
  * [9] S. Liu, M. Watterson, K. Mohta, K. Sun, S. Bhattacharya, C. J. Taylor, and V. Kumar, “Planning dynamically feasible trajectories for quadrotors using safe flight corridors in 3-d complex environments,” IEEE Robotics and Automation Letters, vol. 2, no. 3, pp. 1688–1695, 2017.
  * [10] F. Gao, W. Wu, Y. Lin, and S. Shen, “Online safe trajectory generation for quadrotors using fast marching method and bernstein basis polynomial,” in 2018 IEEE International Conference on Robotics and Automation (ICRA), pp. 344–351, IEEE, 2018.
  * [11] W. Ding, W. Gao, K. Wang, and S. Shen, “An efficient b-spline-based kinodynamic replanning framework for quadrotors,” IEEE Transactions on Robotics, vol. 35, no. 6, pp. 1287–1306, 2019.
  * [12] J. Tordesillas, B. T. Lopez, M. Everett, and J. P. How, “Faster: Fast and safe trajectory planner for navigation in unknown environments,” IEEE Transactions on Robotics, vol. 38, no. 2, pp. 922–938, 2021.
  * [13] M. Zucker, N. Ratliff, A. D. Dragan, M. Pivtoraiko, M. Klingensmith, C. M. Dellin, J. A. Bagnell, and S. S. Srinivasa, “Chomp: Covariant hamiltonian optimization for motion planning,” The International Journal of Robotics Research, vol. 32, no. 9-10, pp. 1164–1193, 2013.
  * [14] F. Gao, Y. Lin, and S. Shen, “Gradient-based online safe trajectory generation for quadrotor flight in complex environments,” in 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 3681–3688, IEEE, 2017.
  * [15] V. Usenko, L. Von Stumberg, A. Pangercic, and D. Cremers, “Real-time trajectory replanning for mavs using uniform b-splines and a 3d circular buffer,” in 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 215–222, IEEE, 2017.
  * [16] X. Zhou, Z. Wang, H. Ye, C. Xu, and F. Gao, “Ego-planner: An esdf-free gradient-based local planner for quadrotors,” IEEE Robotics and Automation Letters, vol. 6, no. 2, pp. 478–485, 2020.
  * [17] H. Oleynikova, M. Burri, Z. Taylor, J. Nieto, R. Siegwart, and E. Galceran, “Continuous-time trajectory optimization for online uav replanning,” in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pp. 5332–5339, IEEE, 2016.
  * [18] F. Gao, L. Wang, B. Zhou, X. Zhou, J. Pan, and S. Shen, “Teach-repeat-replan: A complete and robust system for aggressive flight in complex environments,” IEEE Transactions on Robotics, vol. 36, no. 5, pp. 1526–1545, 2020.
  * [19] B. Zhou, F. Gao, L. Wang, C. Liu, and S. Shen, “Robust and efficient quadrotor trajectory generation for fast autonomous flight,” IEEE Robotics and Automation Letters, vol. 4, no. 4, pp. 3529–3536, 2019.
  * [20] C. Rösmann, F. Hoffmann, and T. Bertram, “Integrated online trajectory planning and optimization in distinctive topologies,” Robotics and Autonomous Systems, vol. 88, pp. 142–153, 2017.
  * [21] C. Rösmann, W. Feiten, T. Wösch, F. Hoffmann, and T. Bertram, “Trajectory modification considering dynamic constraints of autonomous robots,” in ROBOTIK 2012; 7th German Conference on Robotics, pp. 1–6, VDE, 2012.
  * [22] L. Jaillet and T. Siméon, “Path deformation roadmaps: Compact graphs with useful cycles for motion planning,” The International Journal of Robotics Research, vol. 27, no. 11-12, pp. 1175–1188, 2008.
  * [23] J. Alonso-Mora, T. Naegeli, R. Siegwart, and P. Beardsley, “Collision avoidance for aerial vehicles in multi-agent scenarios,” Autonomous Robots, vol. 39, no. 1, pp. 101–121, 2015.
  * [24] D. H. Shim, H. J. Kim, and S. Sastry, “Decentralized nonlinear model predictive control of multiple flying robots,” in 42nd IEEE International Conference on Decision and Control (IEEE Cat. No. 03CH37475), vol. 4, pp. 3621–3626, IEEE, 2003.
  * [25] T. Nägeli, L. Meier, A. Domahidi, J. Alonso-Mora, and O. Hilliges, “Real-time planning for automated multi-view drone cinematography,” ACM Transactions on Graphics (TOG), vol. 36, no. 4, pp. 1–10, 2017.
  * [26] B. Gopalakrishnan, A. K. Singh, M. Kaushik, K. M. Krishna, and D. Manocha, “Chance constraint based multi agent navigation under uncertainty,” in Proceedings of the Advances in Robotics, pp. 1–6, 2017.
  * [27] L. Blackmore, M. Ono, A. Bektassov, and B. C. Williams, “A probabilistic particle-control approximation of chance-constrained stochastic predictive control,” IEEE transactions on Robotics, vol. 26, no. 3, pp. 502–517, 2010\.
  * [28] F. Fahroo and I. M. Ross, “Direct trajectory optimization by a chebyshev pseudospectral method,” Journal of Guidance, Control, and Dynamics, vol. 25, no. 1, pp. 160–166, 2002.
  * [29] R. H. Byrd, M. E. Hribar, and J. Nocedal, “An interior point algorithm for large-scale nonlinear programming,” SIAM Journal on Optimization, vol. 9, no. 4, pp. 877–900, 1999.
  * [30] A. Wächter and L. T. Biegler, “On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming,” Mathematical programming, vol. 106, no. 1, pp. 25–57, 2006.
  * [31] J. A. Andersson, J. Gillis, G. Horn, J. B. Rawlings, and M. Diehl, “Casadi: a software framework for nonlinear optimization and optimal control,” Mathematical Programming Computation, vol. 11, pp. 1–36, 2019.
  * [32] J. Ren, K. A. McIsaac, R. V. Patel, and T. M. Peters, “A potential field model using generalized sigmoid functions,” IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), vol. 37, no. 2, pp. 477–484, 2007\.


# SINCERE: Supervised Information Noise-Contrastive Estimation REvisited

Patrick Feeney and Michael C. Hughes

###### Abstract

The information noise-contrastive estimation (InfoNCE) loss function provides
the basis of many self-supervised deep learning methods due to its strong
empirical results and theoretic motivation. Previous work suggests a
supervised contrastive (SupCon) loss to extend InfoNCE to learn from available
class labels. This SupCon loss has been widely-used due to reports of good
empirical performance. However, in this work we suggest that the specific
SupCon loss formulated by prior work has questionable theoretic justification,
because it can encourage images from the same class to repel one another in
the learned embedding space. This problematic behavior gets worse as the
number of inputs sharing one class label increases. We propose the Supervised
InfoNCE REvisited (SINCERE) loss as a remedy. SINCERE is a theoretically
justified solution for a supervised extension of InfoNCE that never causes
images from the same class to repel one another. We further show that
minimizing our new loss is equivalent to maximizing a bound on the KL
divergence between class conditional embedding distributions. We compare
SINCERE and SupCon losses in terms of learning trajectories during pretraining
and in ultimate linear classifier performance after finetuning. Our proposed
SINCERE loss better separates embeddings from different classes during
pretraining while delivering competitive accuracy.

##  1 Introduction

|  | Loss | Equation | Effect of $q,r$
---|---|---
SupCon |  $\frac{e^{z_{t}\cdot z_{p}}}{e^{z_{t}\cdot z_{p}}+e^{z_{t}\cdot\color[rgb]{0,0.88,0}{z_{q}}}+e^{z_{t}\cdot\color[rgb]{0,0.88,0}{z_{r}}}+\sum_{i\in\mathcal{N}_{t}}e^{z_{t}\cdot z_{i}}}$ | Repel $t$
SINCERE |  $\frac{e^{z_{t}\cdot z_{p}}}{e^{z_{t}\cdot z_{p}}+\sum_{i\in\mathcal{N}_{t}}e^{z_{t}\cdot z_{i}}}$ | None
Figure 1:  _Left:_ Example images in one batch for supervised contrastive
learning. Color indicates whether image’s class label matches the target class
(green) or a non-target noise class (red). Images $t$ and $p$ (light green)
are chosen as the image pair that represents the target class for the loss,
while $q$ and $r$ (dark green) are not. _Right:_ Equations for our new
proposed loss (SINCERE) and the previous SupCon by Khosla et al. (2020), when
$t$ is the target image and $p$ is the chosen partner. Both losses attempt to
move embeddings from the target class closer to each other. However, SupCon
loss treats $q$ and $r$ as though they were from a noise class. This
problematically _repels_ the learned embedding of $t$ from $q$ and $r$ despite
$q$ and $r$ truly belonging to the target class. Our SINCERE loss avoids this
problem by not involving $q$ or $r$ at all when computing loss for target
image $t$ with partner $p$. Not shown: both SINCERE and SupCon average over
pairs $t,p$ from the target class.

Self-supervised learning (SSL) has been crucial in creating pretrained
computer vision models that can be efficiently adapted to a variety of tasks
(Jing and Tian 2020; Jaiswal et al. 2021). The conceptual basis for many
successful pretraining methods is the instance discrimination task (Wu et al.
2018), where the model learns to classify each training image as a unique
class. Self-supervised methods solve this task by _contrasting_ different
augmentations of the same image with other images, seeking a learned vector
representation in which each image is close to augmentations of itself but far
from others. Among several possible contrastive losses in the literature
(Caron et al. 2020; Schroff, Kalenichenko, and Philbin 2015), one that has
seen particularly wide adoption is information noise-contrastive estimation
(InfoNCE) loss (van den Oord, Li, and Vinyals 2019). InfoNCE variants such as
MOCO (Chen, Xie, and He 2021), SimCLR (Chen et al. 2020a, b), and BYOL (Grill
et al. 2020) have proven empirically effective.

The above methods are all for _unsupervised_ pretraining of representations
from unlabeled images. To create more effective representations for
applications where labeled images are available, we may wish to extend
instance discrimination methods so that learned representations are informed
by the available class labels. A natural way forward is to contrast images of
the same class with images from other classes (Schroff, Kalenichenko, and
Philbin 2015). Following the noise contrastive estimation framework (Gutmann
and Hyvärinen 2010), we assume that images from the same class are drawn from
a target distribution while images from other classes come from a noise
distribution.

††footnotetext:  Open-source Code: https://github.com/tufts-ml/SupContrast

Khosla et al. (2020) previously proposed the Supervised Contrastive (SupCon)
loss as a supervised extension of the InfoNCE loss. They examined two
straightforward ways of averaging an InfoNCE-like loss over image pairs with
the same class label. Their recommended loss, named SupCon, was chosen because
it performed best empirically in top-1 classification on the ImageNet dataset
(Deng et al. 2009). SupCon loss has been applied to problems such as
contrastive open set recognition (Xu, Shen, and Zhao 2023) and generalized
category discovery (Vaze et al. 2022).

In light of this empirical success, in this work we investigate the
theoretical justification for SupCon. We find that the SupCon loss violates
InfoNCE’s core assumption that the target and noise distributions should be
_separated_. Consider a class with at least 3 member images, labeled $t$, $p$,
and $q$, as illustrated in Fig. 1. When target image $t$ is partnered with
$p$, SupCon by construction will push $t$’s representation away from $q$,
effectively treating $q$ as a noise image. This problematic behavior makes it
difficult to separate target and noise distribution in the embedding space.
Moreover, the problem will get worse as the number of images belonging to the
same target class increases.

To resolve this issue, this paper proposes the Supervised InfoNCE REvisited
(SINCERE) loss. See Fig. 1 for an illustration of SINCERE’s differences from
SupCon. Unlike SupCon, our SINCERE loss by definition excludes image $q$ (and
all other members of the same class, like the image labeled $r$ in Fig. 1)
from the noise distribution, thus ensuring the core assumption underlying
InfoNCE remains intact.

To begin, we offer a first-principles derivation of SINCERE, thereby providing
a conceptual justification for this loss function as a well-founded
generalization of InfoNCE to supervised learning. We then demonstrate SupCon
loss’ problematic behavior using both a formal analysis of gradients as well
as by investigating the cosine similarity between learned embeddings from
different classes. We find that the problematic repulsion that can happen
between members of the same class under SupCon is not present when using our
SINCERE loss. Instead, as desired our proposed SINCERE loss better separates
the target and noise distributions. Finally, we observe that a linear
classifier using SINCERE features maintains the accuracy seen with SupCon
loss.

Overall, our main contributions are:

  1. 1.

The SINCERE loss function, which is a drop-in replacement for SupCon loss for
representation learning informed by available class labels. The SINCERE loss
arises from a derivation that enforces a core assumption of noise-contrastive
estimation: images known to be from target distribution should not be treated
as examples of the noise distribution.

  2. 2.

A proof that SINCERE loss acts as a bound on the KL divergence between target
and noise distributions. This bound becomes tighter as the amount of data
samples used by the loss increases. This bound provides a supervised extension
to the information-theoretic bound presented in the original InfoNCE paper.

  3. 3.

Empirical results showing that SINCERE loss eliminates problematic behavior
from SupCon loss, while still delivering competitive accuracy for a fine-tuned
linear classifier. SINCERE users can thus anticipate improved separation of
target and noise distributions in learned embeddings. Code for reproducing all
experiments is available via the GitHub link on the first page of this paper.

##  2 Background

###  2.1 Noise-Contrastive Estimation

Noise-contrastive estimation (NCE) (Gutmann and Hyvärinen 2010) provides a
general framework for modeling a target distribution of interest given a set
of samples from it. This framework utilizes a binary classifier to contrast
the target distribution samples with samples from a noise distribution. This
noise distribution is an arbitrary distribution different from the target
distribution, although in practice the noise distribution must be similar
enough to the target distribution to make the classifier learn the structure
of the target distribution. Later work maintains the focus on contrasting
target and noise distributions while defining these distributions as
generating disjoint subsets of a dataset of interest.

###  2.2 Self-Supervised Contrastive Learning

Consider an observed dataset $(\mathcal{X},\mathcal{Y})$ of $n$ elements,
composed of data (e.g. images or features) in set
$\mathcal{X}=(x_{1},x_{2},...,x_{n})$ each paired with one of $k$ categorical
labels $\mathcal{Y}=(y_{1},y_{2},...,y_{n})$, where $2\leq k\leq n$. Let
integer interval $\mathcal{I}=\llbracket 1,n\rrbracket$ denote the set of
indices for elements in $\mathcal{X}$ or $\mathcal{Y}$. Let
$z_{i}\in\mathbb{R}^{d}$ be an embedding vector representation of data element
$x_{i}$ produced by a neural network.

Self-supervised contrastive learning pursues an _instance discrimination_ task
(Wu et al. 2018), which involves classifying each point in the dataset as a
separate class. Therefore each data point $x_{i}$ has a unique label $y_{i}$
and the number of unique labels $k$ is equal to $n$.

To set up the instance discrimination problem, select index $t$ as the only
member of the target distribution in the dataset. Let the rest of the dataset
$\mathcal{N}_{t}=\mathcal{I}\setminus\\{t\\}$ be drawn from the noise
distribution. Applying NCE produces the Information Noise-Contrastive
Estimation (InfoNCE) loss (van den Oord, Li, and Vinyals 2019)

$L_{\text{InfoNCE}}(x_{t},y_{t})=-\log\frac{e^{s(z_{t},y_{t})}}{e^{s(z_{t},y_{t})}+\sum_{i\in\mathcal{N}_{t}}e^{s(z_{i},y_{t})}}$
(1)

where $s(z_{i},y_{j})$ is a classification score function which outputs a
scalar score for image $x_{i}$ under label $y_{j}$. The loss
$L_{\text{InfoNCE}}(x_{i},y_{j})$ defined above thus calculates the negative
log-likelihood that $x_{i}$ has label $y_{j}$. More specifically,
$L_{\text{InfoNCE}}(x_{t},y_{t})$ is the negative log-likelihood that $x_{t}$
is part of the target distribution.

The score $s(z_{t},y_{t})$ is often chosen to be cosine similarity by
representing $y_{t}$ as a vector in embedding space $z_{t}^{\prime}$ (Wu et
al. 2018; Chen et al. 2020a; Chen, Xie, and He 2021). $z_{t}^{\prime}$ can be
produced by embedding a data augmented copy of $x_{t}$ (Le-Khac, Healy, and
Smeaton 2020; Chen et al. 2020a), embedding $x_{t}$ via older (Wu et al. 2018)
or averaged embedding function parameters (Chen, Xie, and He 2021), or a
combination of these techniques (Jaiswal et al. 2021).

Rewriting $L_{\text{InfoNCE}}$ in terms of a data augmented $z_{i}^{\prime}$
and setting $s(z_{i},z_{i}^{\prime})=z_{t}\cdot z_{t}^{\prime}/\tau$, with
$\tau$ acting as a temperature hyperparameter, produces the self-supervised
contrastive loss proposed by Wu et al. (2018):

$L_{\text{self}}(z_{t},z_{t}^{\prime})=-\log\frac{e^{z_{t}\cdot
z_{t}^{\prime}/\tau}}{e^{z_{t}\cdot
z_{t}^{\prime}/\tau}+\sum_{i\in\mathcal{N}_{t}}e^{z_{t}\cdot z_{i}/\tau}}$ (2)

Throughout, we assume each embedding vector is normalized so the inner product
with itself equals one: $z_{t}\cdot z_{t}=1$.

InfoNCE and the subsequent self-supervised contrastive losses cited above are
all theoretically motivated by NCE. The larger instance discrimination problem
is posed as a series of binary classification problems between instance-
specific target and noise distributions. This clear distinction between target
and noise underlies our later SINCERE loss.

###  2.3 Supervised Contrastive Learning (SupCon)

Khosla et al. (2020) considers supervised classification where more than one
element in $\mathcal{X}$ is drawn from the target distribution. Let
$\mathcal{T}_{t}=\\{i\in\mathcal{I}|y_{i}=y_{t}\\}$ be the set of elements
drawn from the same target distribution as $x_{t}$, such that
$|\mathcal{T}_{t}|<|\mathcal{X}|$. The possible set of same-class partners for
index $t$ is $\mathcal{P}_{t}=\mathcal{T}_{t}\setminus\\{t\\}$. The set of
indices modeled as noise is
$\mathcal{N}_{t}=\mathcal{I}\setminus\mathcal{T}_{t}$. Based on empirical
results, Khosla et al. (2020) propose an average of $L_{\text{self}}$ over
$\mathcal{P}_{t}$ as their supervised contrastive loss
$L_{\text{SupCon}}(z_{t})$:

$\frac{-1}{|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}\log\frac{e^{z_{t}\cdot
z_{p}/\tau}}{(\sum_{i\in\mathcal{P}_{t}}e^{z_{t}\cdot
z_{i}/\tau})+(\sum_{i\in\mathcal{N}_{t}}e^{z_{t}\cdot z_{i}/\tau})}.$ (3)

When $|\mathcal{P}_{t}|>1$, this loss contains terms from the target
distribution in the denominator that are not in the numerator. In contrast, in
the self-supervised losses defined above, all target terms appear in both
numerator and denominator. The members of $\mathcal{P}_{t}$ that only appear
in the denominator of Eq. (3) are effectively being used as part of the noise
distribution, which causes the SupCon loss to penalize similarity between
embeddings from the target distribution. This problematic behavior complicates
analysis of the loss (Graf et al. 2021) and limits the loss’ ability to
separate embeddings from different classes.

##  3 Method

In this section, we develop a new loss we call SINCERE for supervised
contrastive learning. We derive and justify our SINCERE loss in Section 3.1,
showing how it arises from applying noise-contrastive estimation to a
supervised problem via the same principles that justify InfoNCE for the self-
supervised case. Next, we cover practical implementation of SINCERE in Sec.
3.2, including complexity analysis. Sec. 3.3 contrasts the gradient of SINCERE
with the gradient of SupCon loss. Sec. 3.4 motivates the loss via an
information-theoretic bound. Finally, Sec. 3.5 examines how SINCERE loss
relates to other works building on InfoNCE and SupCon losses.

###  3.1 Derivation and Justification

We first establish a “true” data-generating model for both self-supervised and
supervised cases. We then show how noise contrastive estimation under this
assumed model leads to our proposed SINCERE loss in the supervised case, and
reduces to the InfoNCE loss in the self-supervised case.

#### Model for self-supervised case.

Assume we observe a dataset $\mathcal{X}$ of $n$ examples, without any labels.
The target class of interest is denoted $y_{t}$. Exactly one example’s data is
drawn from the target distribution with pdf function $p(x|y_{t})$. All other
examples are drawn i.i.d. from the noise distribution, with pdf function
denoted $p(x|{\neq}_{t})$, where symbol $\neq_{t}$ is shorthand for
conditioning on the event that $Y\neq y_{t}$, which means the instance’s label
$Y$ does not match the target class. Let random variable $S$ indicate the
index of the example from the target distribution. The assumed “true” model
accounts for both $S$ and $\mathcal{X}$ as random variables. First, set
$p(S{=}i|y_{t})$ to uniform over $i\in\mathcal{I}$. Then, generate the data as

$\displaystyle p(\mathcal{X}|S{=}i,y_{t})=p(x_{i}|y_{t})\prod_{l\neq
i}p(x_{l}|{\neq}_{t})$ (4)

######  Lemma 1.

Likelihood for Self-Supervised NCE (van den Oord, Li, and Vinyals 2019). For
any index $i\in\mathcal{I}$, the probability that $x_{i}$ was drawn from the
target, given that there is only one sample in $\mathcal{X}$ drawn from the
target, is

$\displaystyle p(S=i|\mathcal{X},y_{t})$
$\displaystyle=\frac{p(x_{i}|y_{t})\prod_{l\neq
i}p(x_{l}|{\neq}_{t})}{\sum_{j\in\mathcal{I}}p(x_{j}|y_{t})\prod_{l\neq
j}p(x_{l}|{\neq}_{t})}$ (5)
$\displaystyle=\frac{\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq}_{t})}}{\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq}_{t})}+\sum_{j\in\mathcal{N}_{t}}\frac{p(x_{j}|y_{t})}{p(x_{j}|{\neq}_{t})}}.$
(6)

_Proof:_ Bayes theorem produces the first formula given the joint
$p(S,\mathcal{X}|y_{t})$ defined in and above Eq. 4. The second formula
reduces via algebra, recalling $\mathcal{I}=\mathcal{N}_{t}\cup\\{i\\}$.

#### Model for supervised case.

Suppose multiple elements of $\mathcal{X}$ are drawn from the target class of
interest $y_{t}$. We assume known the indices $\mathcal{P}_{t}$ of all but one
target example. Let random variable $S\in\mathcal{I}\setminus\mathcal{P}_{t}$
indicate the index of the final example of the target class. The remaining
indices $\mathcal{N}_{t}$ are assumed from the noise. The assumed “true” model
is keeps $p(S=i|\mathcal{P}_{t},y_{t})$ uniform over
$\mathcal{I}\setminus\mathcal{P}_{t}$, then generates data as

$\displaystyle
p(\mathcal{X}|S=i,\mathcal{P}_{t},y_{t})=p(x_{i}|y_{t})\prod_{p\in\mathcal{P}_{t}}p(x_{p}|y_{t})\prod_{j\in\mathcal{N}_{t}}p(x_{j}|{\neq_{t}})$
(7)

######  Lemma 2.

Likelihood for Supervised NCE. Given an $\mathcal{X}$ from the model defined
above with target $y_{t}$ and known indices $\mathcal{P}_{t}$, the probability
that some index $i\in\mathcal{I}\setminus\mathcal{P}_{t}$ is the final target
sample is

$\displaystyle
p(S=i|\mathcal{P}_{t},\mathcal{X},y_{t})=\frac{\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq_{t}})}}{\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq_{t}})}+\sum_{j\in\mathcal{N}_{t}}\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq_{t}})}}$
(8)

_Proof:_ We first derive an expression for the likelihood of all indices of
the target class: $p(S=i,\mathcal{P}_{t}|\mathcal{X},y_{t})$ from the joint in
and above Eq. (7). Standard probability operations (sum rule, product rule)
then allow obtaining the desired $p(S=i|\mathcal{P}_{t},\mathcal{X},y_{t})$
For details, see App. B.

#### Tractable model.

In practice, we will not know the true density functions for target or noise
distributions. Instead, we can build an alternative tractable model of random
variable $S\in\mathcal{I}\setminus\mathcal{P}_{t}$, indicating the index of
the single unknown member of the target class. Let neural net $f_{\theta}$ map
any input data $x_{i}$ to a strictly positive value. Then, our tractable model
for $S$ given data $\mathcal{X}$ and known class members $\mathcal{P}_{t}$ is

$\displaystyle
p_{\theta}(S=i|\mathcal{P}_{t},\mathcal{X},y_{t})=\frac{f_{\theta}(x_{i})}{f_{\theta}(x_{i})+\sum_{j\in\mathcal{N}_{i}}f_{\theta}(x_{j})}.$
(9)

Suppose we can observe many samples of $\mathcal{X},\mathcal{P}_{t},S$ from
the true model in Eq. (7). We can fit $f_{\theta}$ by minimizing the following
_idealized_ loss

$\displaystyle
L_{\text{SINCERE}}(\theta)=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},S\sim
p_{\text{true}}}\left[-\log
p_{\theta}(S|\mathcal{P}_{t},\mathcal{X},y_{t})\right]$ (10)

This loss, which we call SINCERE, provides a principled way to fit a tractable
neural model $f_{\theta}$ to identify the last remaining member of a target
class when given other class member indices $\mathcal{P}_{t}$. Minimizing the
loss has an equivalent interpretation as maximizing the log likelihood of $S$
under the tractable model.

The following two propositions justify the chosen form of function $f$ in Eq.
(9) and loss $L$ in Eq. (10). We emphasize that our two-proposition
justification for the loss holds for both the supervised case that is our main
focus, as well for the self-supervised case (where $\mathcal{P}_{t}$ is the
empty set). This justification can be viewed as a formalization of the
arguments in van den Oord, Li, and Vinyals (2019) that has been extended to
handle the supervised case in a principled way.

######  Proposition 3.1.

If $f$ is sufficiently flexible, there exists parameter $\theta^{*}$ such that
the tractable model can match the true likelihood of $S$. Proof: Fix $k>0$,
then set $\theta^{*}$ such that

$\displaystyle f_{\theta^{*}}(x)$
$\displaystyle=k\frac{p(x|y_{t})}{p(x|{\neq_{t}})},~{}\textnormal{for all
possible}~{}x.$ (11)

This implies
$p_{\theta^{*}}(S{=}i|\mathcal{P}_{t},\mathcal{X},y_{t})=p_{true}(S{=}i|\mathcal{X},\mathcal{P}_{t},y_{t})$
by construction for all valid values of
$i\in\mathcal{I}\setminus\mathcal{P}_{t}$.

######  Proposition 3.2.

The truth-matching parameter $\theta^{*}$ is a minimizer of the SINCERE loss
$L_{\textnormal{SINCERE}}(\theta)$ in Eq. (10). Proof sketch: We recognize our
loss minimization objective in Eq. (10) as equivalent to maximizing the log
likelihood $p_{\theta}$ under samples from the true model. Using the theory of
maximum likelihood estimation under possible model misspecification (White
1982; Fan 2016), we can view this as minimizing the KL-divergence
$D_{\text{KL}}(p_{true}(S|\mathcal{P}_{t},\mathcal{X},y_{t})||p_{\theta}(S|\mathcal{P}_{t},\mathcal{X},y_{t}))$.
KL-divergence is minimized when its two arguments are equal, and we’ve shown
that $\theta^{*}$ can match the truth in Prop 3.1. Thus, setting
$\theta=\theta^{*}$ will attain the optimal loss.

#### Comparison to SupCon.

Attempting to translate SupCon loss into the noise-contrastive paradigm
suggests that it assigns probability to the data point at index $i$ out of all
possible data points via

$\frac{\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq_{t}})}}{\frac{p(x_{i}|y_{t})}{p(x_{i}|{\neq_{t}})}+\sum_{p\in\mathcal{P}_{t}}\frac{p(x_{p}|y_{t})}{p(x_{p}|{\neq_{t}})}+\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}}.$

We emphasize that this does _not_ correspond to a principled derivation from a
coherent probabilistic model. In contrast, our derivation of SINCERE follows
directly from the model in Eq. (7). Furthermore, this framing of SupCon makes
clear that it penalizes similarity between embeddings from the target
distribution, which results in the problematic within-class repulsion behavior
described in Fig. 1. We formalize this analysis later in Sec. 3.3.

###  3.2 SINCERE Loss in Practice

To compute SINCERE loss in practice, we take the expectation over
stochastically-sampled batches $(\mathcal{X}_{b},\mathcal{Y}_{b})$ of fixed
size $n$ from a large labeled dataset $(\mathcal{X},\mathcal{Y})$. Each data
point in the mini-batch is reduced to an embedding vector representation by a
neural network with weights $\theta$. Then, each embedding is treated in turn
as the target example $z_{t}$ for one computation of the SINCERE loss.
Overall, we fit neural net weights $\theta$ by minimizing this expected loss
over batches:

$\displaystyle L(\theta)$
$\displaystyle=\mathbb{E}_{\mathcal{X}_{b},\mathcal{Y}_{b}}\left[\sum_{t=1}^{n}\frac{L_{\text{SINCERE}}(z_{t})}{n}\right],$
(12) $\displaystyle L_{\text{SINCERE}}(z_{t})$
$\displaystyle=\frac{-1}{|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}\log\frac{e^{z_{t}\cdot
z_{p}/\tau}}{e^{z_{t}\cdot z_{p}/\tau}+\sum_{j\in\mathcal{N}_{t}}e^{z_{t}\cdot
z_{j}/\tau}}.$

Here, $\mathcal{P}_{t}$ defines all data points other than $t$ _in the current
batch_ that share class label $y_{t}$. Similarly, $\mathcal{N}_{t}$ defines
data points in the current batch with any other class label. Our
implementation of SINCERE loss uses the cosine similarity function proposed by
Wu et al. (2018), although other choices of similarity functions may be used.

By averaging over the elements of $\mathcal{P}_{t}$ we can nonparametrically
represent the target class $y_{t}$ and encourage $z_{t}$ to have similar
embeddings as its fellow members. However, no member of $\mathcal{P}_{t}$ ever
appears in the denominator without also appearing in the numerator. This
avoids any “repulsion” between two members of the same class in the embedding
space seen with SupCon loss. Intuitively, our SINCERE loss restores NCE’s
assumption that the input used in the numerator belongs to the target
distribution while all other inputs in the denominator belong to the noise
distribution.

#### Runtime and memory complexity.

We emphasize that SINCERE’s complexity exactly matches SupCon’s complexity in
both speed and memory. Given a batch of $n$ data points, each with a
$d$-dimensional embedding, SINCERE loss can be computed in $O(n^{2}d)$ time,
with quadratic complexity arising due to need for computation of dot products
between many pairs $z_{t},z_{j}$. An implementation that was memory sensitive
could be done with $O(nd)$ memory, which is the cost of storing all embedding
vectors. Our implementation has memory cost of $O(n^{2}+nd)$, as we find
computing all $n^{2}$ pairwise similarities at once has speed advantages due
to vectorization. In our experiments with a batch size of 512, we find the
runtime of computing embeddings far exceeds the runtime of computing SINCERE
given embeddings.

###  3.3 Analysis of Gradients

We study the gradients of both SINCERE and SupCon to gain additional
understanding of their relative properties.

The gradient of the SINCERE loss with respect to $z_{t}$ is

$\displaystyle\frac{\delta}{\delta
z_{t}}L_{\text{SINCERE}}(z_{t})=\frac{1}{\tau|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}g_{p},$
(13) $\displaystyle g_{p}\triangleq z_{p}\left(\frac{e^{z_{t}\cdot
z_{p}/\tau}}{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot
z_{i}/\tau}}-1\right)+$
$\displaystyle\frac{\sum_{n\in\mathcal{N}_{t}}z_{n}e^{z_{t}\cdot
z_{n}/\tau}}{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot z_{i}/\tau}}.$

The first term of $g_{p}$ involves a _negative_ scalar times $z_{p}$. The
second term involves a _positive_ scalar times each noise embedding $z_{n}$.
Thus during gradient descent each update to $z_{t}$ encourages it to move
_towards_ each target embedding $z_{p}$ and _away_ from each noise embedding
$z_{n}$. The magnitude of these movements is determined by the softmax of
cosine similarities. For a complete derivation and further analysis, see App.
Sec. C.

This behavior is different from the gradient dynamics of SupCon loss. Khosla
et al. (2020) provide SupCon’s gradient with respect to $z_{t}$ as
$\frac{\delta}{\delta z_{t}}L_{\text{SupCon}}(z_{t})=$

$\frac{1}{\tau}\sum\limits_{p\in\mathcal{P}_{t}}z_{p}\left(\frac{e^{z_{t}\cdot
z_{p}/\tau}}{\sum_{i\in\mathcal{I}}e^{z_{t}\cdot
z_{i}/\tau}}-\frac{1}{|\mathcal{P}_{t}|}\right)+\frac{1}{\tau}\frac{\sum_{n\in\mathcal{N}_{t}}z_{i}e^{z_{t}\cdot
z_{n}/\tau}}{\sum_{i\in\mathcal{I}}e^{z_{t}\cdot z_{i}/\tau}}.$ (14)

Studying this SupCon gradient, we see that the scalar multiplying $z_{p}$ in
Eq. 14 will be in the range
$[\frac{-1}{|\mathcal{P}_{t}|},1-\frac{1}{|\mathcal{P}_{t}|}]$. The
possibility of positive values implies $z_{t}$ could be _pushed away_ from
$z_{p}$ when applying gradient descent. In contrast, the scalar multiplier for
$z_{p}$ will always by in $[-1,0]$ for SINCERE in Eq. 13, which effectively
performs hard positive mining (Schroff, Kalenichenko, and Philbin 2015).

SupCon’s problematic behavior (possible repulsion between members of the same
class) increases in severity as $|\mathcal{P}_{t}|$ increases, resulting in a
scalar in $[0,1]$ as $|\mathcal{P}_{t}|$ approaches positive infinity. Khosla
et al. (2020) previously hypothesized that the $\frac{-1}{|\mathcal{P}_{t}|}$
term came from the softmax of $z_{t}$ and the mean of the embeddings
$z_{p}\in\mathcal{P}_{t}$ . Our analysis suggests it is actually due to
improperly including target class examples other than $p$ in the loss’
denominator.

A similar issue arises from the summation over the noise distribution in Eq.
14. Each softmax includes the noise distribution and the entire target
distribution in the denominator instead of only the noise distribution and
$z_{p}$ as in Eq. 13. Reducing the weight put onto the noise distribution
causes the SupCon loss to reduce the separation between the noise and target
distributions.

###  3.4 SINCERE Bounds KL Divergence

van den Oord, Li, and Vinyals (2019) motivate the self-supervised InfoNCE loss
via an information-theoretic bound. Revisiting this analysis, we suggest that
SINCERE loss and also InfoNCE loss can be understood as a bound on the KL
divergence between the target and noise distributions. This bound becomes
tighter as the number of negative examples $|\mathcal{N}_{t}|$ increases, or
as the loss $L_{\text{SINCERE}}(z_{t})$ decreases.

######  Theorem 3.

Bound on KL Divergence

$L(\theta)$ bounds the KL divergence between the noise and target
distributions, where $L(\theta)$ is $L_{\text{InfoNCE}}(\theta)$ when self-
supervised and $L_{\text{SINCERE}}(\theta)$ when supervised:

$L(\theta)\geq\mathbb{E}_{\mathcal{P}_{t},t}\left[\log|\mathcal{N}_{t}|-\text{KL}(p(x_{t}|y_{t})||p(x_{t}|{\neq_{t}}))\right].$
(15)

Proof: See App. Sec. D.

Maximizing the KL divergence ensures that the distributions are separable.
Therefore Theorem 3 shows performance improves with more negative samples, as
has been observed in self-supervised contrastive learning (Henaff 2020; Chen,
Xie, and He 2021; Chen et al. 2020a; Tian, Krishnan, and Isola 2020). More
positive samples removes bias from the estimation of the KL divergence,
ensuring the entire target distribution is separable from the noise
distribution.

###  3.5 Related Work on Supervised Contrastive

Several works have expanded on SupCon loss in order to apply it to new
problems. Feng et al. (2022) limit the target and noise distributions to
K-nearest neighbors to allow for multi-modal class distributions. Kang et al.
(2021) explicitly set the number of samples from the target distribution to
handle imbalanced datasets. Li et al. (2022b) introduce a regularization to
push target distributions to center on uniformly distributed points in the
embedding space. Yang et al. (2022) and Li et al. (2022a) utilize pseudo-
labeling to address semi-supervised learning and supervised learning with
noisy labels respectively. SINCERE loss can easily replace the use of SupCon
loss in these applications.

Terms similar to the SINCERE loss have previously been used as a part of more
complex losses. Barbano et al. (2023) proposed $\epsilon$-SupInfoNCE loss,
which eliminated the problematic denominator terms from SupCon for being non-
contrastive and introduced a margin hyperparameter. However, it is unclear how
the loss handles the target distribution. $\epsilon$-SupInfoNCE loss
eliminates the average over data points from the same class used in SupCon and
SINCERE losses and there is no code at time of writing to show their
alternative approach. Chen et al. (2022) utilizes a loss like our SINCERE loss
as one term of an overall loss function meant to spread out embeddings that
share a class. Neither of these works provide detailed discussion or
motivation for the changes they make to SupCon loss.

Figure 2:  Average cosine similarity for pairs of CIFAR-10 test set images,
with one image from the row class and the other from the column class. SINCERE
loss better separates embeddings from other classes (off-diagonal entries are
much lower). We also observe that SINCERE does not group embeddings from the
same class (on diagonal) as tightly as SupCon loss.

Figure 3:  Histograms of cosine similarity values for image pairs in the
CIFAR-10 test set, comparing SupCon (top) and SINCERE (bottom). The target
“Truck” distribution is formed by evaluating image pairs where both are
labeled truck. The noise distribution is formed by computing similarity
between truck, non-truck pairs. SINCERE loss lowers the cosine similarity of
the noise distribution, suggesting better target-noise separation.

##  4 Experiments

We evaluate SINCERE and SupCon losses for supervised pretraining on CIFAR-10
and CIFAR-100 (Krizhevsky 2009). These datasets were selected in order to
reproduce previous results for the SupCon loss (Khosla et al. 2020).

Following the PyTorch code released by Khosla et al. (2020), a ResNet-50 for
each loss is pretrained for 1,000 epochs then frozen. Each frozen model is
then used as a feature extractor for a linear classifier that is trained for
100 epochs with cross-entropy loss. Section 4.3 provides a detailed
explanation of the training process to enable others to reproduce these
results. Our code is available: see page one.

Section 4.1 contrasts the behavior of the losses throughout pretraining by
contrasting loss values and the learned embeddings. Section 4.2 validates that
SINCERE loss embeddings are as effective as SupCon loss embeddings for
finetuning a linear classifier.

###  4.1 Supervised Pretraining

| CIFAR-10 | CIFAR-100
---|---|---
Pretraining Loss | Initial | Final | Initial | Final
SupCon | 6.93 | 4.69 | 6.91 | 2.43
SINCERE | 6.82 | 0.24 | 6.90 | 0.14
Table 1:  Average pretraining loss values for initial and final training
epochs.

Table 1 reports loss values from pretraining. SupCon and SINCERE losses return
very similar values during the first training epoch because the target and
noise distributions are not yet separable. However they differ significantly
by the final training epoch, when the target and noise distributions are
separable. SINCERE loss ends with lower loss values for both datasets. SupCon
loss on CIFAR-100 is lower than SupCon loss on CIFAR-10, when there are fewer
inputs sharing a class per batch. This confirms the analysis of SupCon loss’
gradient in Section 3.3: including the target distribution as part of the
noise distribution produces problematic behavior that increases in severity as
the number of inputs sharing a class increases.

Figure 2 examines the average cosine similarity for CIFAR-10 test set image
pairs. Pairs made up of the same image are excluded when the row and column
class are the same, as these would always evaluate to a cosine similarity of
1. SINCERE loss learns embeddings with a lower cosine similarity than SupCon
loss, with a mean decrease of 0.06 when pairs are from the same class and 0.11
when pairs are from different classes. Therefore SINCERE loss better separates
the target and noise distributions despite spreading out the target
distribution embeddings.

Figure 3 visualizes the cosine similarity of the truck class and its noise
distribution composed of the other 9 classes. The truck class was chosen as a
representative sample as the other classes follow the same trends seen here.
SINCERE loss’ lower means are seen in the shift of the target and noise
distributions. Additionally, SINCERE loss spreads both distributions across
more cosine similarity values, which is seen in the lower peaks. The similar
shape of the cosine similarity distributions confirms that the trends seen in
Figure 2 arise from better separation of the target and noise distributions
and not from differently shaped distributions, such as comparing a unimodal
and bimodal distribution.

###  4.2 Classification Accuracy

| CIFAR-10 | CIFAR-100
---|---|---
Pretraining Loss | Top-1 | Top-5 | Top-1 | Top-5
SupCon | 95.78 | 99.84 | 75.96 | 92.33
SINCERE | 95.93 | 99.78 | 75.86 | 92.54
Table 2:  Test set accuracy of a linear classifier trained using frozen
pretrained features. SINCERE’s performance is essentially indistinguishable
from SupCon. No results are boldfaced, as we did _not_ find any differences to
be statistically significant in our bootstrap interval analysis..

We report top-1 and top-5 accuracy results. Top-1 accuracy was chosen to
reproduce the previous SupCon results (Khosla et al. 2020), which are within
$0.6$ percentage points of our results. Top-5 accuracy was chosen to provide a
broader view of the models’ predictions than top-1 accuracy.

Table 2 reports the top-1 and top-5 accuracy of the finetuned linear
classifiers on the test set. Accuracy results are the mean of 1,000 iterations
of test set bootstrapping. No results are boldfaced because the difference
between accuracies is not statistically significant according to a 95%
confidence interval of the bootstrapped results (Foody 2009). In further
analysis, Supplementary Figure A.1 provides side-by-side confusion matrices
for the two methods on the CIFAR-10 test set. The two confusion matrices are
quite similar (e.g. cat and dog as the most confused classes). Therefore, we
suggest that our new SINCERE loss after fine-tuning maintains the good
accuracy previously reported by Khosla et al. (2020) with SupCon loss plus
fine-tuning.

###  4.3 Training Details

Models were trained on a Red Hat Enterprise Linux 7.5 server with a A100 GPU
with 40 GiB of memory and 16 Intel Xeon Gold 6226R CPUs with 1TB of memory
each. Many of the CPUs were primarily used for parallelization of data
loading, so fewer or smaller CPUs could be used easily. PyTorch 2.0.1 and
Torchvision 0.15.2 for CUDA 11.7 were used for model and loss implementations.

A single training procedure was done for each SupCon and SINCERE loss. Models
were pretrained with the hyperparameters suggested by Khosla et al. (2020):
1,000 epochs of stochastic gradient descent with 0.9 momentum, 0.0001 weight
decay, 512 batch size, and a cosine annealed learning rate schedule with warm-
up, which spends 10 epochs warming up from 0.0005 to 0.5 then cosine anneals
back to 0.0005 at the last epoch. Temperature ($\tau$) was set to 0.1.
Additional learning rates were tested to ensure that pretraining results were
robust, applying similar warm-up and annealing schedules. Results similar to
those reported were found when using 0.005, 0.05, or 0.1 as the learning rate.
Both models produce worse results with learning rates of 1 or 5.

Linear models were trained with the hyperparameters suggested by Khosla et al.
(2020): 100 epochs of stochastic gradient descent with 0.9 momentum, 0 weight
decay, 512 batch size, and a cosine annealed learning rate schedule with warm-
up, which spends 10 epochs warming up from 0.05 to 5 then cosine anneals back
to 0.05 at the last epoch.

##  5 Discussion

The proposed SINCERE loss is a theoretically motivated loss for supervised
noise contrastive estimation. SINCERE loss eliminates the problematic behavior
seen in SupCon loss, as shown through examination of the loss gradients and
empirical results. Additionally, SINCERE loss bounds the KL divergence between
target and noise distributions, with the tightness of the bound increasing
with more data. SINCERE loss can easily replace SupCon loss, only requiring
refitting of loss weight hyperparameters for multi-objective losses due to
SINCERE loss’ broader range of loss values.

Future work may explore an alternative supervised loss which removes the
conditioning on the target distribution. This would correspond to predicting
all entries of the target distribution at once instead of individually. A
naive approach to this problem would involve an exponential increase in the
number of terms in the denominator. Abstracting the classes via prototypes or
sampling terms from the full denominator could resolve that issue. Such a loss
could potentially model higher-order interactions between sets of samples
instead of averaging over pair-wise interactions as is done currently.

## References

  * Barbano et al. (2023) Barbano, C. A.; Dufumier, B.; Tartaglione, E.; Grangetto, M.; and Gori, P. 2023\.  Unbiased Supervised Contrastive Learning.  In _The Eleventh International Conference on Learning Representations_.
  * Caron et al. (2020) Caron, M.; Misra, I.; Mairal, J.; Goyal, P.; Bojanowski, P.; and Joulin, A. 2020\.  Unsupervised Learning of Visual Features by Contrasting Cluster Assignments.  In _Advances in Neural Information Processing Systems_ , volume 33, 9912–9924. Curran Associates, Inc.
  * Chen et al. (2022) Chen, M.; Fu, D. Y.; Narayan, A.; Zhang, M.; Song, Z.; Fatahalian, K.; and Re, C. 2022.  Perfectly Balanced: Improving Transfer and Robustness of Supervised Contrastive Learning.  In Chaudhuri, K.; Jegelka, S.; Song, L.; Szepesvari, C.; Niu, G.; and Sabato, S., eds., _Proceedings of the 39th International Conference on Machine Learning_ , volume 162 of _Proceedings of Machine Learning Research_ , 3090–3122. PMLR.
  * Chen et al. (2020a) Chen, T.; Kornblith, S.; Norouzi, M.; and Hinton, G. 2020a.  A Simple Framework for Contrastive Learning of Visual Representations.  In III, H. D.; and Singh, A., eds., _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , 1597–1607. PMLR.
  * Chen et al. (2020b) Chen, T.; Kornblith, S.; Swersky, K.; Norouzi, M.; and Hinton, G. E. 2020b.  Big Self-Supervised Models are Strong Semi-Supervised Learners.  In _Advances in Neural Information Processing Systems_ , volume 33, 22243–22255. Curran Associates, Inc.
  * Chen, Xie, and He (2021) Chen, X.; Xie, S.; and He, K. 2021.  An Empirical Study of Training Self-Supervised Vision Transformers.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 9640–9649.
  * Deng et al. (2009) Deng, J.; Dong, W.; Socher, R.; Li, L.-J.; Li, K.; and Fei-Fei, L. 2009.  ImageNet: A large-scale hierarchical image database.  In _2009 IEEE Conference on Computer Vision and Pattern Recognition_ , 248–255.
  * Fan (2016) Fan, Z. 2016.  MLE under model misspecification.  Technical report, Stanford University.
  * Feng et al. (2022) Feng, Y.; Jiang, J.; Tang, M.; Jin, R.; and Gao, Y. 2022.  Rethinking Supervised Pre-Training for Better Downstream Transferring.  In _International Conference on Learning Representations_.
  * Foody (2009) Foody, G. M. 2009.  Classification accuracy comparison: Hypothesis tests and the use of confidence intervals in evaluations of difference, equivalence and non-inferiority.  _Remote Sensing of Environment_ , 113(8): 1658–1663.
  * Graf et al. (2021) Graf, F.; Hofer, C.; Niethammer, M.; and Kwitt, R. 2021.  Dissecting Supervised Contrastive Learning.  In Meila, M.; and Zhang, T., eds., _Proceedings of the 38th International Conference on Machine Learning_ , volume 139 of _Proceedings of Machine Learning Research_ , 3821–3830. PMLR.
  * Grill et al. (2020) Grill, J.-B.; Strub, F.; Altché, F.; Tallec, C.; Richemond, P.; Buchatskaya, E.; Doersch, C.; Avila Pires, B.; Guo, Z.; Gheshlaghi Azar, M.; Piot, B.; kavukcuoglu, k.; Munos, R.; and Valko, M. 2020.  Bootstrap Your Own Latent - A New Approach to Self-Supervised Learning.  In _Advances in Neural Information Processing Systems_ , volume 33, 21271–21284. Curran Associates, Inc.
  * Gutmann and Hyvärinen (2010) Gutmann, M.; and Hyvärinen, A. 2010.  Noise-contrastive estimation: A new estimation principle for unnormalized statistical models.  In Teh, Y. W.; and Titterington, M., eds., _Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics_ , volume 9 of _Proceedings of Machine Learning Research_ , 297–304. Chia Laguna Resort, Sardinia, Italy: PMLR.
  * Henaff (2020) Henaff, O. 2020.  Data-Efficient Image Recognition with Contrastive Predictive Coding.  In III, H. D.; and Singh, A., eds., _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , 4182–4192. PMLR.
  * Jaiswal et al. (2021) Jaiswal, A.; Babu, A. R.; Zadeh, M. Z.; Banerjee, D.; and Makedon, F. 2021.  A Survey on Contrastive Self-Supervised Learning.  _Technologies_ , 9(1).
  * Jing and Tian (2020) Jing, L.; and Tian, Y. 2020.  Self-supervised visual feature learning with deep neural networks: A survey.  _IEEE transactions on pattern analysis and machine intelligence_ , 43(11): 4037–4058.
  * Kang et al. (2021) Kang, B.; Li, Y.; Xie, S.; Yuan, Z.; and Feng, J. 2021.  Exploring Balanced Feature Spaces for Representation Learning.  In _International Conference on Learning Representations_.
  * Khosla et al. (2020) Khosla, P.; Teterwak, P.; Wang, C.; Sarna, A.; Tian, Y.; Isola, P.; Maschinot, A.; Liu, C.; and Krishnan, D. 2020.  Supervised Contrastive Learning.  In Larochelle, H.; Ranzato, M.; Hadsell, R.; Balcan, M.; and Lin, H., eds., _Advances in Neural Information Processing Systems_ , volume 33, 18661–18673. Curran Associates, Inc.
  * Krizhevsky (2009) Krizhevsky, A. 2009.  Learning multiple layers of features from tiny images.
  * Le-Khac, Healy, and Smeaton (2020) Le-Khac, P. H.; Healy, G.; and Smeaton, A. F. 2020.  Contrastive Representation Learning: A Framework and Review.  _IEEE Access_ , 8: 193907–193934.
  * Li et al. (2022a) Li, S.; Xia, X.; Ge, S.; and Liu, T. 2022a.  Selective-Supervised Contrastive Learning With Noisy Labels.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 316–325.
  * Li et al. (2022b) Li, T.; Cao, P.; Yuan, Y.; Fan, L.; Yang, Y.; Feris, R. S.; Indyk, P.; and Katabi, D. 2022b.  Targeted Supervised Contrastive Learning for Long-Tailed Recognition.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 6918–6928.
  * Schroff, Kalenichenko, and Philbin (2015) Schroff, F.; Kalenichenko, D.; and Philbin, J. 2015.  FaceNet: A Unified Embedding for Face Recognition and Clustering.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Tian, Krishnan, and Isola (2020) Tian, Y.; Krishnan, D.; and Isola, P. 2020.  Contrastive Multiview Coding.  In Vedaldi, A.; Bischof, H.; Brox, T.; and Frahm, J.-M., eds., _Computer Vision – ECCV 2020_ , 776–794. Cham: Springer International Publishing.  ISBN 978-3-030-58621-8.
  * van den Oord, Li, and Vinyals (2019) van den Oord, A.; Li, Y.; and Vinyals, O. 2019.  Representation Learning with Contrastive Predictive Coding.  arXiv:1807.03748.
  * Vaze et al. (2022) Vaze, S.; Han, K.; Vedaldi, A.; and Zisserman, A. 2022.  Generalized Category Discovery.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 7492–7501.
  * White (1982) White, H. 1982.  Maximum likelihood estimation of misspecified models.  _Econometrica: Journal of the econometric society_.
  * Wu et al. (2018) Wu, Z.; Xiong, Y.; Yu, S. X.; and Lin, D. 2018.  Unsupervised Feature Learning via Non-Parametric Instance Discrimination.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Xu, Shen, and Zhao (2023) Xu, B.; Shen, F.; and Zhao, J. 2023.  Contrastive Open Set Recognition.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 37(9): 10546–10556.  Number: 9.
  * Yang et al. (2022) Yang, F.; Wu, K.; Zhang, S.; Jiang, G.; Liu, Y.; Zheng, F.; Zhang, W.; Wang, C.; and Zeng, L. 2022.  Class-Aware Contrastive Semi-Supervised Learning.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 14421–14430.

##  Appendix A Confusion Matrix

See Figure A.1.

Figure A.1:  Confusion matrices for the CIFAR-10 test set. Both pretraining
methods produce very similar results.

##  Appendix B Proofs of Lemma 2

We first assume that we only know the number of samples from the target
distribution $|\mathcal{T}_{t}|$ in addition to the information used in the
self-supervised case. The probability that a set of indices $I$ is
$\mathcal{T}_{t}$, given $|I|=|\mathcal{T}_{t}|$, is
$p(I=\mathcal{T}_{t}|\mathcal{X},y_{t})$

$\displaystyle=\frac{(\prod_{i\in
I}p(x_{i}|y_{t}))(\prod_{l\in\mathcal{I}-I}p(x_{l}|Y\neq
y_{t}))}{\sum_{J\in\mathbb{P}_{|\mathcal{T}_{t}|}(\mathcal{I})}(\prod_{j\in
J}p(x_{j}|y_{t}))(\prod_{l\in\mathcal{I}-J}p(x_{l}|Y\neq y_{t}))}$ (16)
$\displaystyle=\frac{\prod_{i\in I}\frac{p(x_{i}|y_{t})}{p(x_{i}|Y\neq
y_{t})}}{\sum_{J\in\mathbb{P}_{|\mathcal{T}_{t}|}(\mathcal{I})}\prod_{j\in
J}\frac{p(x_{j}|y_{t})}{p(x_{j}|Y\neq y_{t})}}$ (17)

where $\mathbb{P}_{k}(\mathcal{I})$ denotes the set of subsets of
$\mathcal{I}$ with $k$ elements.

Next, we assume knowledge of $\mathcal{P}_{t}$, which leaves $t$ as the only
unknown index in $\mathcal{T}_{t}$. Applying the product rule then the sum
rule produces

$\displaystyle p(i=t|\mathcal{X},y_{t},\mathcal{P}_{t})$
$\displaystyle=\frac{p(i\cup\mathcal{P}_{t}=\mathcal{T}_{t}|\mathcal{X},y_{t})}{p(\mathcal{P}_{t}\subset\mathcal{T}_{t}|\mathcal{X},y_{t})}$
(18)
$\displaystyle=\frac{p(i\cup\mathcal{P}_{t}=\mathcal{T}_{t}|\mathcal{X},y_{t})}{\sum_{j\in\mathcal{I}\setminus\mathcal{P}_{t}}p(j\cup\mathcal{P}_{t}=\mathcal{T}_{t}|\mathcal{X},y_{t})}.$
(19)

Plugging in Equation 17 and canceling the terms dependent on $\mathcal{P}_{t}$
produces Equation 8.

Equation 8 is ideal when the class conditional distributions are known.
SINCERE loss approximates the ratio of these distributions when they are
unknown.

##  Appendix C Detailed Analysis of Gradients

The gradient of the SINCERE loss with respect to $z_{t}$ is
$\frac{\delta}{\delta z_{t}}L_{\text{SINCERE}}(z_{t})$

$\displaystyle=\frac{\delta}{\delta
z_{t}}\frac{-1}{|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}\log\frac{e^{z_{t}\cdot
z_{p}/\tau}}{e^{z_{t}\cdot z_{p}/\tau}+\sum_{i\in\mathcal{N}_{t}}e^{z_{t}\cdot
z_{i}/\tau}}$ (20) $\displaystyle=\frac{\delta}{\delta
z_{t}}\frac{-1}{|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}(\frac{z_{t}\cdot
z_{p}}{\tau}-\log\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot
z_{i}/\tau})$ (21)
$\displaystyle=\frac{-1}{\tau|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}(z_{p}-\frac{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}z_{i}e^{z_{t}\cdot
z_{i}/\tau}}{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot z_{i}/\tau}})$
(22)
$\displaystyle=\frac{-1}{\tau|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}(z_{p}-\frac{z_{p}e^{z_{t}\cdot
z_{p}/\tau}+\sum_{i\in\mathcal{N}_{t}}z_{i}e^{z_{t}\cdot
z_{i}/\tau}}{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot z_{i}/\tau}})$
(23)
$\displaystyle=\frac{1}{\tau|\mathcal{P}_{t}|}\sum\limits_{p\in\mathcal{P}_{t}}(z_{p}(\frac{e^{z_{t}\cdot
z_{p}/\tau}}{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot
z_{i}/\tau}}-1)$ (24)
$\displaystyle\quad+\frac{\sum_{i\in\mathcal{N}_{t}}z_{i}e^{z_{t}\cdot
z_{i}/\tau}}{\sum_{i\in\mathcal{N}_{t}\cup\\{p\\}}e^{z_{t}\cdot
z_{i}/\tau}}).$

##  Appendix D Proof of Bounds

Assume the target class $y_{t}$ is known and fixed throughout this derivation.
We start with the definition of the loss as an expected negative log
likelihood from Eq. (10).

$\displaystyle L(\theta)$
$\displaystyle=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t\sim p_{true}}[-\log
p_{\theta}(S=t|\mathcal{P}_{t},\mathcal{X},y_{t})]$ (25)

where the expectation is with respect to samples
$\mathcal{X},\mathcal{P}_{t},t$ from the joint of the “true” model defined in
and above Eq. (7). Here, we use $t\in\mathcal{I}\setminus\mathcal{P}_{t}$ to
indicate the realized value (via sampling) of r.v. $S$. The value of $t$
defines the specific final index of the target class in $\mathcal{X}$.

Plugging in the optimal tractable model with weights $\theta^{*}$ defined via
target-to-noise density ratios in Prop. 3.1, we find that by simplifying via
algebra

$\displaystyle L(\theta^{*})$
$\displaystyle=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}[-\log
p_{\theta^{*}}(S=t|\mathcal{P}_{t},\mathcal{X},y_{t})]$ (26)
$\displaystyle=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}[-\log\frac{\frac{p(x_{t}|y_{t})}{p(x_{t}|{\neq_{t}})}}{\frac{p(x_{t}|y_{t})}{p(x_{t}|{\neq_{t}})}+\sum_{j\in\mathcal{N}_{t}}\frac{p(x_{j}|y_{t})}{p(x_{j}|{\neq_{t}})}}]$
$\displaystyle=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}[-\log\frac{1}{1+\frac{1}{\frac{p(x_{t}|y_{t})}{p(x_{t}|{\neq_{t}})}}\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}}]$
$\displaystyle=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}[\log\left(1+\frac{p(x_{t}|{\neq_{t}})}{p(x_{t}|y_{t})}\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}\right)]$

We now invoke a bound, using the fact that $\log 1+p\geq\log p$ for any $p>0$
(log is a monotonic increasing function).

$\displaystyle L(\theta^{*})$
$\displaystyle\geq\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}[\log\left(\frac{p(x_{t}|{\neq_{t}})}{p(x_{t}|y_{t})}\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}\right)]$
(27)
$\displaystyle=\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}\underbrace{[\log\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}]}_{A}+\mathbb{E}_{\mathcal{X},t}\underbrace{[[\log\frac{p(x_{t}|{\neq_{t}})}{p(x_{t}|y_{t})}]}_{B}$

We handle terms B then A separately below.

#### Term B:

The right-hand term B only involves the target index $x_{t}$ and not any other
terms in $\mathcal{X}$. Simplifying that term gives

$\displaystyle\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}[\log\frac{p(x_{t}|{\neq_{t}})}{p(x_{t}|y_{t})}]$
(28)
$\displaystyle=\mathbb{E}_{\mathcal{P}_{t},t}\left[\int_{\mathcal{X}}\log(\frac{p(x_{t}|{\neq_{t}})}{p(x_{t}|y_{t})})p(x_{t}|y_{t})\cancelto{1}{\prod_{p\in\mathcal{P}_{t}}p(x_{p}|y_{t})}\right.$
$\displaystyle\quad\left.\cancelto{1}{\prod_{j\in\mathcal{N}_{t}}p(x_{j}|{\neq_{t}})}d\mathcal{X}\right]$
(29)
$\displaystyle=-\mathbb{E}_{\mathcal{P}_{t},t}[\text{KL}(p(x_{t}|y_{t})||p(x_{t}|{\neq_{t}}))]$

Here, our expectation over the size-$n$ dataset $\mathcal{X}$ reduces to an
expectation over the marginal $p(x_{t}|y_{t})$ on the data vector at the
target index $x_{t}$. This reveals an interpretation of term B as a negative
KL divergence from target to noise.

#### Term A:

Term A requires an approximation. First, note that given knowledge that $S=t$,
all entries in $\mathcal{N}_{t}$ are generated as iid draws from the noise.
Following van den Oord, Li, and Vinyals (2019), we approximate this sum as

$\displaystyle\mathbb{E}_{\mathcal{X}|S=t}[\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}]$
$\displaystyle\approx|\mathcal{N}_{t}|\mathbb{E}_{x\sim
p(x|{\neq_{t}})}[\frac{p(x|y_{t})}{p(x|{\neq_{t}})}]$
$\displaystyle=|\mathcal{N}_{t}|\int_{x}p(x|{\neq_{t}})\frac{p(x|y_{t})}{p(x|{\neq_{t}})}dx$
$\displaystyle=|\mathcal{N}_{t}|\int_{x}p(x|y_{t})dx$
$\displaystyle=|\mathcal{N}_{t}|$ (30)

where we’ve exploited that any valid pdf integrates to one over its domain.

We use the above to argue that the A term is roughly

$\displaystyle\mathbb{E}_{\mathcal{X},\mathcal{P}_{t},t}\log\sum_{n\in\mathcal{N}_{t}}\frac{p(x_{n}|y_{t})}{p(x_{n}|{\neq_{t}})}]\approx\mathbb{E}_{\mathcal{P}_{t},t}\left[\log|\mathcal{N}_{t}|\right]$
(31)

#### Combining A and B.

Putting it all together, we find

$\displaystyle L(\theta)\geq
L(\theta^{*})\geq\mathbb{E}_{\mathcal{P}_{t},t}\left[\log|\mathcal{N}_{t}|-\text{KL}(p(x_{t}|y_{t})||p(x_{t}|{\neq_{t}}))\right]$
(32)

we can thus interpret an evaluation of the loss as providing an upperbound on
the negative KL divergence from target to noise distribution. By minimizing
the loss via gradient descent, we push the KL larger and larger, thus
separating the target from the noise.

#### Relation to previous bounds on InfoNCE.

The bound proposed by van den Oord, Li, and Vinyals (2019) for the self-
supervised case only is similar, but is expressed in terms of mutual
information due to their choice to write the noise distribution as $p(x_{i})$,
implying it is related to the target $p(x_{i}|y_{t})$ by simply _removing_ the
condition that $Y_{i}=y_{t}$. We believe this is incorrect: inspecting the
generative model in Eq. (7), the noise distribution is assumed to be
_distinct_ from the target. By conditioning on the fact that the label $Y$ is
explicitly _not_ the target, our derivation above using the noise PDF as
$p(x_{i}|Y_{i}\neq y_{t})$ is more appropriate. Note that in our shorthand,
this same noise PDF is denoted $p(x_{i}|{\neq_{t}})$.