# HV-Net: Hypervolume Approximation based on DeepSets

Ke Shang, Weiyu Chen, Weiduo Liao, Hisao Ishibuchi This work was supported by
National Natural Science Foundation of China (Grant No. 62002152, 61876075),
Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program
for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No.
2017ZT07X386), The Stable Support Plan Program of Shenzhen Natural Science
Fund (Grant No. 20200925174447003), Shenzhen Science and Technology Program
(Grant No. KQTD2016112514355531). (Corresponding Author: Hisao Ishibuchi.)K.
Shang, W. Liao, and H. Ishibuchi are with Guangdong Provincial Key Laboratory
of Brain-inspired Intelligent Computation, Department of Computer Science and
Engineering, Southern University of Science and Technology, Shenzhen 518055,
China (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>hisao@sustech.edu.cn).W. Chen is with Department of Computer Science and
Engineering, The Hong Kong University of Science and Technology, Hong Kong,
China (e-mail: wchenbx@cse.ust.hk).K. Shang and W. Chen contribute equally to
this work.

###### Abstract

In this letter, we propose HV-Net, a new method for hypervolume approximation
in evolutionary multi-objective optimization. The basic idea of HV-Net is to
use DeepSets, a deep neural network with permutation invariant property, to
approximate the hypervolume of a non-dominated solution set. The input of HV-
Net is a non-dominated solution set in the objective space, and the output is
an approximated hypervolume value of this solution set. The performance of HV-
Net is evaluated through computational experiments by comparing it with two
commonly-used hypervolume approximation methods (i.e., point-based method and
line-based method). Our experimental results show that HV-Net outperforms the
other two methods in terms of both the approximation error and the runtime,
which shows the potential of using deep learning technique for hypervolume
approximation.

###### Index Terms:

Hypervolume indicator, approximation, evolutionary multi-objective
optimization, DeepSets.

##  I Introduction

In the filed of evolutionary multi-objective optimization (EMO), there are
many performance indicators which are used to evaluate the performance of EMO
algorithms [1]. Some representative performance indicators include GD [2], IGD
[3], hypervolume [4], R2 [5], etc. Among them, the hypervolume indicator is
the most widely investigated one since it has rich theoretical properties and
mature applications. For example, it is able to evaluate both the convergence
and diversity of a solution set simultaneously [6]. It is Pareto compliant
[7]. Furthermore, it can also be used in EMO algorithms for environmental
selection. Representative hypervolume-based EMO algorithms include SMS-EMOA
[8, 9], FV-MOEA [10], HypE [11], and R2HCA-EMOA [12].

The main drawback of the hypervolume indicator is that it is computationally
more expensive than other performance indicators. Some efficient hypervolume
calculation methods have been proposed such as WFG [13], QHV [14], and HBDA
[15]. However, these methods aim to exactly calculate the hypervolume
indicator. They will become inefficient when the number of objectives is large
(e.g., $>10$) since the calculation of the hypervolume indicator is #P-hard
[16]. Therefore, some hypervolume approximation methods have been proposed to
overcome this drawback [17, 16, 18, 19, 20, 21, 22, 23].

Two representative approximation methods are the point-based method and the
line-based method. The point-based method is also known as Monte Carlo
sampling method [17, 23]. In this method, a large number of points are sampled
in the sampling space, and the hypervolume is approximated based on the
percentage of the points lying inside the hypervolume region. The line-based
method is also known as the R2 indicator method [19] or the polar coordinate
method [20]. In this method, a set of line segments with different directions
are used to approximate the hypervolume.

In this letter, we propose HV-Net, a new hypervolume approximation method. HV-
Net is a deep neural network where the input is a non-dominated solution set
and the output is the hypervolume approximation of this solution set. HV-Net
has two characteristics. 1) It is permutation invariant to the order of
elements in the input set (i.e., the output of HV-Net does not depend on the
order of solutions in the input solution set). 2) It can handle an input
solution set with an arbitrary number of solutions (i.e., the number of
solutions in the input solution set is not fixed). These characteristics make
sure that HV-Net is flexible and general for hypervolume approximation.

The main contribution of this letter is that we develop a new type of
hypervolume approximation method based on a deep neural network. Our
experimental results are promising and encouraging. This will bring new
opportunities for the development of the EMO field.

The rest of this letter is organized as follows. Section II presents the
preliminaries of the study. Section III introduces the new hypervolume
approximation method, HV-Net. Section IV conducts experimental studies.
Section V concludes the letter.

##  II Preliminaries

###  II-A Hypervolume Indicator

The hypervolume indicator is a widely used performance indicator in the field
of evolutionary multi-objective optimization (EMO). Formally, for a solution
set $S$ in the objective space, the hypervolume of $S$ is defined as

$HV(S,\mathbf{r})=\mathcal{L}\left(\bigcup_{\mathbf{s}\in
S}\left\\{\mathbf{s}^{\prime}|\mathbf{s}\prec\mathbf{s}^{\prime}\prec\mathbf{r}\right\\}\right),$
(1)

where $\mathcal{L}(.)$ is the Lebesgue measure of a set,
$\mathbf{r}\in\mathbb{R}^{m}$ is a reference point which is dominated by all
solutions in $S$, and $\mathbf{s}\prec\mathbf{s}^{\prime}$ denotes that
$\mathbf{s}$ Pareto dominates $\mathbf{s}^{\prime}$ (i.e., $s_{i}\leq
s^{\prime}_{i}$ for all $i=1,...,m$ and $s_{j}<s^{\prime}_{j}$ for at least
one $j=1,...,m$ in the minimization case, where $m$ is the number of
objectives).

Fig. 1 gives an illustration of the hypervolume of a solution set
$S=\\{\mathbf{a}^{1},\mathbf{a}^{2},\mathbf{a}^{3}\\}$ in a two-dimensional
objective space where each objective is to be minimized.

Figure 1: An illustration of the hypervolume indicator. The shaded area is the
hypervolume of the solution set
$S=\\{\mathbf{a}^{1},\mathbf{a}^{2},\mathbf{a}^{3}\\}$ based on reference
point $\mathbf{r}$, i.e., $HV(S,\mathbf{r})$.

###  II-B Hypervolume Approximation Methods

The main drawback of the hypervolume indicator is that it is computationally
expensive in high-dimensional spaces [16], which limits its applicability to
many-objective optimization. In order to overcome this drawback, some
hypervolume approximation methods have been proposed [17, 16, 18, 19, 20, 21,
22, 23]. Two representative methods are the point-based method and the line-
based method. These two methods are briefly explained bellow.

####  II-B1 Point-based method

The point-based method is also known as Monte Carlo sampling method [17, 23].
In this method, a large number of points are sampled in the sampling space and
the hypervolume is approximated based on the percentage of the points lying
inside the hypervolume region.

Fig. 2 (a) illustrates this method. The sampling space is determined by the
reference point and the ideal point of the solution set $S$. The volume of the
sampling space can be easily calculated since it is a cuboid. We assume the
volume of the sampling space is $V$. Then $k$ points are uniformly sampled in
the sampling space. Suppose that there are $k^{\prime}$ points dominated by
$S$ (i.e., these points lie in the hypervolume region of $S$), then the
hypervolume of $S$ is approximated as

${HV}(S,\mathbf{r})\approx\frac{k^{\prime}}{k}V.$ (2)

(a) Point-based method (b) Line-based method

Figure 2: Illustration of the hypervolume approximation methods.

####  II-B2 Line-based method

The line-based method is also known as the R2 indicator method [19] or the
polar coordinate method [20]. In this method, a set of line segments with
different directions are used to approximate the hypervolume.

Fig. 2 (b) illustrates this method. A set of line segments with different
directions are drawn from the reference point to the boundary of the
hypervolume region. Suppose that we have $n$ line segments and the length of
each line segment in the hypervolume region is $l_{i},i=1,...,n$, then the
hypervolume of $S$ is approximated as

${HV}(S,\mathbf{r})\approx\frac{\pi^{m/2}}{mn2^{m-1}\Gamma(m/2)}\sum_{i=1}^{n}l_{i}^{m},$
(3)

where $\Gamma(x)=\int_{0}^{\infty}z^{x-1}e^{-z}dz$ is the Gamma function.

The directions of the line segments can be defined using a direction vector
set $\Lambda=\\{\boldsymbol{\lambda}^{1},...,\boldsymbol{\lambda}^{n}\\}$
where each direction vector satisfies
$\left\|{\boldsymbol{\lambda}^{i}}\right\|_{2}=1$, $\lambda^{i}_{j}\geq 0$,
$i=1,...,n$, $j=1,...,m$. The length of each line segment in the hypervolume
region can be calculated as

$l_{i}=\max_{\mathbf{s}\in
S}\min_{j\in\\{1,...,m\\}}\left\\{\frac{|r_{j}-s_{j}|}{\lambda^{i}_{j}}\right\\},i=1,...,n.$
(4)

For more information about the derivation of (3) and (4), please refer to [19,
20].

##  III HV-Net

In this section, we propose a new type of hypervolume approximation method,
HV-Net. HV-Net is based on DeepSets [24], which is a fundamental architecture
to deal with sets as inputs. The architecture of HV-Net is shown in Fig. 3.
The input of HV-Net is a non-dominated solution set
$S=\\{\mathbf{s}_{1},\mathbf{s}_{2},...,\mathbf{s}_{N}\\}$. First, each of $N$
solutions $\mathbf{s}_{i}\in S$ is presented to the network $\phi$ and
transformed to $\phi(\mathbf{s}_{i})$. Then, these $N$ transformed vectors are
added up as one vector $\sum_{i=1}^{N}\phi(\mathbf{s}_{i})$. This vector is
further presented to another network $\rho$, and the hypervolume of $S$ is
approximated as
$\widetilde{HV}_{\boldsymbol{\theta}}(S,\mathbf{r})=\rho\left(\sum_{i=1}^{N}\phi(\mathbf{s}_{i})\right)$
where $\boldsymbol{\theta}$ is the parameter vector of HV-Net.

Figure 3: The architecture of HV-Net.

The most important property of HV-Net is that it is permutation invariant to
the order of elements in the set (i.e., the sequence of solutions in $S$ in
this paper). That is, the output of HV-Net is the same for any two sets as
long as they have the same elements. Another property of HV-Net is that it can
handle any solution set with an arbitrary number of solutions, which is
important since we usually need to approximate the hypervolume of many
solution sets with different number of solutions, and we want to use a single
neural network to do this. These two properties make sure that HV-Net is
suitable and flexible for hypervolume approximation.

In the next subsections, we discuss in detail how to train and use HV-Net for
hypervolume approximation.

###  III-A How to Train HV-Net

In HV-Net, we implicitly assume the minimization case where the reference
point for hypervolume calculation is set to $\mathbf{r}=(1,...,1)$, and all
solutions in $S$ are located in $[0,1]^{m}$. For the training of HV-Net, we
prepare the training data as follows. First, we prepare $L$ non-dominated
solution sets $\\{S_{1},S_{2},...,S_{L}\\}$ where each solution set is located
in $[0,1]^{m}$. Then, we calculate the hypervolume of each solution set based
on the reference point $\mathbf{r}=(1,...,1)$. That is, we obtain the target
output $HV(S_{i},\mathbf{r})$ for each solution set $S_{i}$ $(i=1,2,...,L)$
for the learning of HV-Net. For hypervolume calculation, we use the WFG
algorithm [13].

Based on the training data (i.e., $L$ input-ouput pairs
$(S_{i},HV(S_{i},\mathbf{r}))$, $i=1,2,...,L$), we define the loss function of
HV-Net as follows:

$\mathcal{L}(\boldsymbol{\theta})=\frac{1}{L}\sum_{i=1}^{L}\left(\log\widetilde{HV}_{\boldsymbol{\theta}}(S_{i},\mathbf{r})-\log
HV(S_{i},\mathbf{r})\right)^{2}.$ (5)

We will discuss in detail why we use (5) as the loss function for training in
Section IV-D. Based on (5), our target is to find the optimal parameter vector
$\mathbf{\boldsymbol{\theta}}^{*}=\arg\min\mathcal{L}(\boldsymbol{\theta})$
for HV-Net. More details about the training of HV-Net are provided in Section
IV-A.

###  III-B How to Use HV-Net

Suppose that we have a well-trained HV-Net. The question is how to use it for
hypervolume approximation when the solution set and the reference point are
both arbitrarily given. The basic idea is to first transform the solution set
and the reference point so that the reference point is $\mathbf{r}=(1,...,1)$
and the solution set is located in $[0,1]^{m}$. Then we use HV-Net to
approximate the hypervolume of the transformed solution set. Lastly, we
calculate the hypervolume approximation of the original solution set based on
the output of HV-Net.

We realize the above described procedure based on the following properties of
the hypervolume indicator. To the best of our knowledge, this is the first
study to explicitly show the following properties for the hypervolume
indicator in the literature.

######  Property 1.

For any positive vector $\boldsymbol{\alpha}\in\mathbb{R}^{m}_{>0}$,
$HV(S,\mathbf{r})=\frac{1}{\prod_{i=1}^{m}\alpha_{i}}HV(\boldsymbol{\alpha}\odot
S,\boldsymbol{\alpha}\odot\mathbf{r})$, where $\odot$ denotes the element-wise
multiplication111For two vectors $\mathbf{a}=(a_{1},...,a_{m})$ and
$\mathbf{b}=(b_{1},...,b_{m})$,
$\mathbf{a}\odot\mathbf{b}=(a_{1}b_{1},...,a_{m}b_{m})$. For a set $B$,
$\mathbf{a}\odot B$ means $\mathbf{a}\odot\mathbf{b}$ for all $\mathbf{b}\in
B$..

######  Property 2.

For any real vector $\boldsymbol{\beta}\in\mathbb{R}^{m}$,
$HV(S,\mathbf{r})=HV(S+\boldsymbol{\beta},\mathbf{r}+\boldsymbol{\beta})$.

######  Property 3.

$HV(S,\mathbf{r})=HV(-S,-\mathbf{r})$ where $HV(-S,-\mathbf{r})$ is calculated
for maximization problems whereas $HV(S,\mathbf{r})$ is calculated for
minimization problems.

The above three properties can be easily derived based on the properties of
the Lebesgue measure [25]. Using the above three properties, we can transform
any solution set and any reference point so that they meet the requirement of
HV-Net. Thus we can calculate the hypervolume approximation of the original
solution set. Next, we give a toy example to illustrate how to use HV-Net for
hypervolume approximation.

######  Example 1.

Suppose that we have a solution set $S=\\{(10,1),(7,3),(4,7)\\}$, and the
reference point $\mathbf{r}=(11,9)$. First, we transform the solution set and
the reference point to $S^{\prime}=\\{(10-4,1-1),(7-4,3-1),(4-4,7-1)\\}$ and
$\mathbf{r}^{\prime}=(11-4,9-1)$ so that the minimum value of each objective
becomes zero. Based on Property 2, we know that
$HV(S,\mathbf{r})=HV(S^{\prime},\mathbf{r}^{\prime})$. Then we transform the
solution set and the reference point to
$S^{\prime\prime}=\\{(6/7,0/8),(3/7,2/8),(0/7,6/8)\\}$ and
$\mathbf{r}^{\prime\prime}=(1,1)$ so that the reference point becomes $(1,1)$.
Based on Property 1, we know that $HV(S^{\prime},\mathbf{r}^{\prime})=7\times
8\times HV(S^{\prime\prime},\mathbf{r}^{\prime\prime})$. Now we can use HV-Net
to approximate the hypervolume of $S^{\prime\prime}$ as
$\widetilde{HV}_{\boldsymbol{\theta}}(S^{\prime\prime},\mathbf{r}^{\prime\prime})$.
The hypervolume of $S$ is approximated as $HV(S,\mathbf{r})=56\times
HV(S^{\prime\prime},\mathbf{r}^{\prime\prime})\approx
56\times\widetilde{HV}_{\boldsymbol{\theta}}(S^{\prime\prime},\mathbf{r}^{\prime\prime})$.

Property 3 is used to deal with the maximization case for hypervolume
calculation. That is, we can transform maximization to minimization based on
Property 3.

##  IV Experiments

In this section, we evaluate the performance of HV-Net by comparing it with
the other two hypervolume approximation methods (i.e., the point-based and
line-based methods).

###  IV-A Experimental Settings

####  IV-A1 HV-Net specifications

In HV-Net in Fig. 3, two networks $\phi$ and $\rho$ need to be specified. In
our experiments, $\phi$ and $\rho$ are specified as two feedforward neural
networks. Both of them have three hidden layers where each hidden layer has
128 neurons. The input dimension of $\phi$ is set to $m$ (i.e., the number of
objectives). The output dimension of $\phi$ is set to 128. The input dimension
of $\rho$ is the same as the output dimension of $\phi$ (i.e., 128). The
output dimension of $\rho$ is set to 1. Fig. 4 shows the structures of $\phi$
and $\rho$.

(a) Network $\phi$ (b) Network $\rho$

Figure 4: Networks $\phi$ and $\rho$ in HV-Net. The number in the parentheses
indicates the number of neurons in each layer. The activation function used in
each layer is shown under each layer.

####  IV-A2 Training and testing data generation

We consider 3, 5, 8, and 10-objective cases (i.e., $m=3,5,8,10$). To generate
training solution sets $\\{S_{1},S_{2},...,S_{L}\\}$ for each case, we set
$L=1,000,000$. Each solution set is generated using the following procedure:

  * •

Step 1: Randomly sample an integer $num\in[1,100]$ where $num$ denotes the
number of solutions in the solution set.

  * •

Step 2: Randomly sample 1000 solutions in $[0,1]^{m}$ as candidate solutions.

  * •

Step 3: Apply non-dominated sorting to these 1000 solutions and obtain
different fronts $\\{F_{1},F_{2},...\\}$ where $F_{1}$ is the first front
(i.e., the set of non-dominated solutions in the 1000 solutions) and $F_{2}$
is the set of non-dominated solutions after all solutions in $F_{1}$ are
removed.

  * •

Step 4: Start from $F_{1}$ until the front $F_{l}$ with no less than $num$
solutions is found. If there is no front satisfies this condition, go back to
Step 2.

  * •

Step 5: Randomly select $num$ solutions from the front $F_{l}$ to construct
one solution set.

This procedure is used in order to select a wide variety of non-dominated
solution sets. On average, about 10,000 solution sets with the same size are
generated (1,000,000 solution sets in total for 100 different sizes). Some
statistical information of the training solution sets is provided in Section I
of the supplementary material. Readers can refer there to gain more insights
on the training solution sets.

We also use the above procedure to generate testing solution sets. The number
of testing solution sets is 10,000 for each objective case. These 10,000
solution sets form one group. We generate a total number of 20 different
groups for each objective case.

####  IV-A3 Parameter settings

For the training of HV-Net, we use Adam [26], an effective gradient-based
optimization method with an adaptive learning rate. The learning rate is set
to $10^{-4}$. For all the other parameters in Adam, we use their default
settings in PyTorch [27]. The batch size during training is set to 100. The
number of epochs for training is set to 100.

As the number of sampling points in the point-based method, we examine 20
different specifications: 100, 200, …, 2000. As the number of lines in the
line-based method, we examine 20 different specifications: 10, 20, …, 200. To
generate the direction vector set $\Lambda$ used in the line-based method, we
use the unit normal vector (UNV) method [20] since it has a good approximation
quality among different direction vector set generation methods [28].

####  IV-A4 Performance metrics

To compare the performance of different hypervolume approximation methods, we
use the approximation error which is defined as follows:

$\varepsilon=\left|\frac{\widetilde{HV}(S,\mathbf{r})-{HV}(S,\mathbf{r})}{HV(S,\mathbf{r})}\right|,$
(6)

where $\widetilde{HV}(S,\mathbf{r})$ denotes the hypervolume approximation.
The smaller the approximation error, the better the approximation quality of a
method.

We also record the runtime of the three methods to compare their efficiency.
Here the runtime of HV-Net means the evaluation time on the testing solution
sets, not its training time.

####  IV-A5 Platforms

All the methods are coded in Python and tested on a server with Intel(R)
Xeon(R) Gold 6130 CPU @ 2.10GHz, GeForce RTX 2080 GPU, and Ubuntu 18.04.6 LTS.
HV-Net is implemented based on PyTorch version 1.9.0.

###  IV-B The Training of HV-Net

Fig. 5 shows the training curve of HV-Net in each objective case. We can see
that the loss becomes very small at the end of the training process in each
objective case, which shows the success of the training of HV-Net.

(a) 3-objective

(b) 5-objective

(c) 8-objective

(d) 10-objective

Figure 5: The training curve of HV-Net in each objective case.

Table I shows the computation time used for training HV-Net. All the training
can be completed within 40 GPU hours.

TABLE I: The time (GPU hours) used for training HV-Net in each case. 3-objective |  5-objective |  8-objective |  10-objective
---|---|---|---
39.077 |  39.017 |  35.820 |  37.930

###  IV-C Performance Comparison

We apply the three hypervolume approximation methods on the testing solution
sets. For fair comparison, all the methods are tested on CPU. That is, we
disable GPU when using HV-Net for evaluation.

Fig. 6 shows the comparison results for each case. We can see that HV-Net
clearly dominates the other two methods in most cases in terms of both the
approximation error and the runtime, which shows the advantage of using HV-Net
for hypervolume approximation.

However, we can also see that only a single point is obtained for HV-Net in
each case. This is because the structure of HV-Net is fixed. We cannot obtain
a set of tradeoff points in each case. For example, we cannot choose another
HV-Net for further improving the approximation quality by using more
computation time (whereas the computation time can be adjusted in the other
methods through the number of points and lines). This is one disadvantage of
HV-Net compared with the other two methods.

Figure 6: Comparison results of the three hypervolume approximation methods on
the testing solution sets in each case. The runtime means the total time for
evaluating 10,000 testing solution sets. The approximation error means the
average error for 10,000 testing solution sets. All the results are the
average over 20 groups of testing solution sets.

###  IV-D Further Investigations

In Section III-A, we defined the loss function $\mathcal{L}$ in (5) for HV-
Net. Now, we further investigate the following two loss functions:

$\displaystyle\mathcal{L}_{1}(\boldsymbol{\theta})=\frac{1}{L}\sum_{i=1}^{L}\left(\widetilde{HV}_{\boldsymbol{\theta}}(S_{i},\mathbf{r})-HV(S_{i},\mathbf{r})\right)^{2},$
(7)
$\displaystyle\mathcal{L}_{2}(\boldsymbol{\theta})=\frac{1}{L}\sum_{i=1}^{L}\left|\frac{\widetilde{HV}_{\boldsymbol{\theta}}(S_{i},\mathbf{r})-HV(S_{i},\mathbf{r})}{HV(S_{i},\mathbf{r})}\right|,$

where $\mathcal{L}_{1}$ is the standard mean squared error (MSE) loss
function, and $\mathcal{L}_{2}$ is the mean absolute percentage error (MAPE)
loss function [29].

We investigate $\mathcal{L}_{1}$ since it is more commonly used as the loss
function, and $\mathcal{L}_{2}$ since it is directly related to the
approximation error in (6). We follow the experimental settings described in
Section IV-A. The HV-Net trained by $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$
are denoted as HV-Net1 and HV-Net2, respectively.

Figure 7: Comparison results of HV-Net, HV-Net1, and HV-Net2 on the testing solution sets in each case. TABLE II: The average approximation error achieved by the three HV-Nets on the testing solution sets in each case. $m$ |  HV-Net |  HV-Net1 |  HV-Net2
---|---|---|---
3 |  0.018541 |  0.055279 |  0.015878
5 |  0.037459 |  2.270159 |  0.032067
8 |  0.042566 |  187.189718 |  1.000000
10 |  0.050867 |  2212.552783 |  1.000000
TABLE III: The average approximation error achieved by the three HV-Nets on the training solution sets in each case. $m$ |  HV-Net |  HV-Net1 |  HV-Net2
---|---|---|---
3 |  0.018489 |  0.056103 |  0.015699
5 |  0.030241 |  4.777839 |  0.030650
8 |  0.036301 |  1094.425093 |  1.000000
10 |  0.042178 |  6848.726503 |  1.000000

Fig. 7 and Table II show the performance comparison of HV-Net, HV-Net1, and
HV-Net2 on the testing solution sets. We can see that HV-Net1 achieves much
worse approximation errors than HV-Net in all cases. HV-Net2 achieves similar
approximation errors to HV-Net in 3- and 5-objective cases, but worse
approximation errors than HV-Net in 8- and 10-objective cases. We also show
their results on the training solution sets in Table III. We can see that the
poor approximation performance on testing data of HV-Net1 and HV-Net2 (in
Table II) is due to their poor fitting performance on training data (in Table
III). The results in Fig. 7 and Tables II-III show the ineffectiveness of
using $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ for training HV-Net. The reasons
for the ineffectiveness of $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ are
explained as follows.

  1. 1.

For $\mathcal{L}_{1}$, the minimization of $\mathcal{L}_{1}$ does not mean the
minimization of the approximation error $\varepsilon$. If the true and
approximated hypervolume values of a solution set are both very small but in
different order of magnitude (e.g., true value is $10^{-6}$ and approximated
value is $10^{-4}$), we will have a very small $\mathcal{L}_{1}\approx
10^{-8}$ but a large $\varepsilon\approx 99$. This motivates us to propose
$\mathcal{L}$ as the loss function. By calculating the logarithm of each
value, we will have a large $\mathcal{L}\approx 21$ which can properly reflect
the large approximation error.

  2. 2.

For $\mathcal{L}_{2}$, although the minimization of $\mathcal{L}_{2}$ leads to
the minimization of the approximation error $\varepsilon$, it is difficult to
train HV-Net using $\mathcal{L}_{2}$ in high-dimensional cases. Fig. 8 shows
the training curve of HV-Net2. We can observe that the training loss gets
stuck at $10^{0}$ for 8- and 10-objective cases. This means that the output of
HV-Net2 is always very close to zero222The output of HV-Net2 cannot be zero
since the activation function in the output layer is Sigmoid as shown in Fig.
4. for any input solution set, and the parameters of HV-Net2 cannot be further
updated to escape from this trap.

(a) 3-objective

(b) 5-objective

(c) 8-objective

(d) 10-objective

Figure 8: The training curve of HV-Net2 in each case.

We also provide the training curve of HV-Net1 in Section II of the
supplementary material. Interested readers can refer there for more
information.

##  V Conclusions

We showed that HV-Net is a promising method for hypervolume approximation.
Compared with the point-based and line-based methods, HV-Net achieved better
performance in terms of the approximation error and the runtime. We also
showed the effectiveness of the proposed loss function over the other two loss
functions for training HV-Net. The experimental results are promising and
encouraging. We believe that HV-Net can bring new opportunities for the
development of the EMO field.

One disadvantage of HV-Net is that its structure is prespecified before
training. Therefore, we can only obtain a single approximation result for each
solution set based on a trained HV-Net. This disadvantage elicits our future
research: multi-objective HV-Net. That is, we can train a set of HV-Nets with
different structures, so that a tradeoff between the approximation error and
the runtime can be obtained. The multi-objective neural architecture search
technique (e.g., NSGA-Net [30]) can be useful to realize this goal.

## References

  * [1] M. Li and X. Yao, “Quality evaluation of solution sets in multiobjective optimisation: A survey,” _ACM Computing Surveys_ , vol. 52, no. 2, pp. 1–38, 2019.
  * [2] D. A. Van Veldhuizen, “Multiobjective evolutionary algorithms: classifications, analyses, and new innovations [Ph.D. thesis],” _Department of Electrical and Computer Engineering. Graduate School of Engineering, Air Force Institute of Technology, Wright-Patterson AFB, Ohio_ , 1999\.
  * [3] C. A. C. Coello and M. R. Sierra, “A study of the parallelization of a coevolutionary multi-objective evolutionary algorithm,” in _Mexican International Conference on Artificial Intelligence_. Springer, 2004, pp. 688–697.
  * [4] E. Zitzler, L. Thiele, M. Laumanns, C. Fonseca, and V. da Fonseca, “Performance assessment of multiobjective optimizers: an analysis and review,” _IEEE Transactions on Evolutionary Computation_ , vol. 7, no. 2, pp. 117–132, 2003.
  * [5] M. P. Hansen and A. Jaszkiewicz, _Evaluating the quality of approximations to the non-dominated set_. IMM, Department of Mathematical Modelling, Technical Universityof Denmark, 1998.
  * [6] K. Shang, H. Ishibuchi, L. He, and L. M. Pang, “A survey on the hypervolume indicator in evolutionary multiobjective optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 25, no. 1, pp. 1–20, 2021.
  * [7] E. Zitzler, D. Brockhoff, and L. Thiele, “The hypervolume indicator revisited: On the design of Pareto-compliant indicators via weighted integration,” in _International Conference on Evolutionary Multi-Criterion Optimization_. Springer, 2007, pp. 862–876.
  * [8] M. Emmerich, N. Beume, and B. Naujoks, “An EMO algorithm using the hypervolume measure as selection criterion,” in _International Conference on Evolutionary Multi-Criterion Optimization_ , 2005, pp. 62–76.
  * [9] N. Beume, B. Naujoks, and M. Emmerich, “SMS-EMOA: Multiobjective selection based on dominated hypervolume,” _European Journal of Operational Research_ , vol. 181, no. 3, pp. 1653–1669, 2007.
  * [10] S. Jiang, J. Zhang, Y.-S. Ong, A. N. Zhang, and P. S. Tan, “A simple and fast hypervolume indicator-based multiobjective evolutionary algorithm,” _IEEE Transactions on Cybernetics_ , vol. 45, no. 10, pp. 2202–2213, 2015\.
  * [11] J. Bader and E. Zitzler, “HypE: An algorithm for fast hypervolume-based many-objective optimization,” _Evolutionary Computation_ , vol. 19, no. 1, pp. 45–76, 2011.
  * [12] K. Shang and H. Ishibuchi, “A new hypervolume-based evolutionary algorithm for many-objective optimization,” _IEEE Transactions on Evolutionary Computation_ , vol. 24, no. 5, pp. 839–852, 2020.
  * [13] L. While, L. Bradstreet, and L. Barone, “A fast way of calculating exact hypervolumes,” _IEEE Transactions on Evolutionary Computation_ , vol. 16, no. 1, pp. 86–95, 2012.
  * [14] L. M. S. Russo and A. P. Francisco, “Quick hypervolume,” _IEEE Transactions on Evolutionary Computation_ , vol. 18, no. 4, pp. 481–502, 2014\.
  * [15] R. Lacour, K. Klamroth, and C. M. Fonseca, “A box decomposition algorithm to compute the hypervolume indicator,” _Computers & Operations Research_, vol. 79, pp. 347–360, 2017.
  * [16] K. Bringmann and T. Friedrich, “Approximating the volume of unions and intersections of high-dimensional geometric objects,” _Computational Geometry Theory and Applications_ , vol. 43, no. 6, pp. 601–610, 2010.
  * [17] J. Bader, K. Deb, and E. Zitzler, “Faster hypervolume-based search using Monte Carlo sampling,” in _Multiple Criteria Decision Making for Sustainable Energy and Transportation Systems_. Springer, 2010, pp. 313–326.
  * [18] H. Ishibuchi, N. Tsukamoto, Y. Sakane, and Y. Nojima, “Hypervolume approximation using achievement scalarizing functions for evolutionary many-objective optimization,” in _IEEE Congress on Evolutionary Computation_. IEEE, 2009, pp. 530–537.
  * [19] K. Shang, H. Ishibuchi, M.-L. Zhang, and Y. Liu, “A new R2 indicator for better hypervolume approximation,” in _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, 2018, pp. 745–752.
  * [20] J. Deng and Q. Zhang, “Approximating hypervolume and hypervolume contributions using polar coordinate,” _IEEE Transactions on Evolutionary Computation_ , vol. 23, no. 5, pp. 913–918, 2019.
  * [21] J. E. Fieldsend, “Efficient real-time hypervolume estimation with monotonically reducing error,” in _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, 2019, pp. 532–540.
  * [22] W. Tang, H.-L. Liu, L. Chen, K. C. Tan, and Y.-m. Cheung, “Fast hypervolume approximation scheme based on a segmentation strategy,” _Information Sciences_ , vol. 509, pp. 320–342, 2020.
  * [23] J. Deng and Q. Zhang, “Combining simple and adaptive Monte Carlo methods for approximating hypervolume,” _IEEE Transactions on Evolutionary Computation_ , vol. 24, no. 5, pp. 896–907, 2020.
  * [24] M. Zaheer, S. Kottur, S. Ravanbhakhsh, B. Póczos, R. Salakhutdinov, and A. J. Smola, “Deep Sets,” 2017, pp. 3394–3404.
  * [25] Wikipedia contributors, “Lebesgue measure — Wikipedia, the free encyclopedia,” https://en.wikipedia.org/w/index.php?title=Lebesgue_measure&oldid=1061315833, 2021, [Online; accessed 16-January-2022].
  * [26] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv preprint arXiv:1412.6980_ , 2014.
  * [27] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga _et al._ , “Pytorch: An imperative style, high-performance deep learning library,” _Advances in Neural Information Processing Systems_ , vol. 32, pp. 8026–8037, 2019.
  * [28] Y. Nan, K. Shang, and H. Ishibuchi, “What is a good direction vector set for the R2-based hypervolume contribution approximation,” in _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, 2020, pp. 524–532.
  * [29] A. De Myttenaere, B. Golden, B. Le Grand, and F. Rossi, “Mean absolute percentage error for regression models,” _Neurocomputing_ , vol. 192, pp. 38–48, 2016.
  * [30] Z. Lu, I. Whalen, V. Boddeti, Y. Dhebar, K. Deb, E. Goodman, and W. Banzhaf, “NSGA-Net: neural architecture search using multi-objective genetic algorithm,” in _Proceedings of the Genetic and Evolutionary Computation Conference_. ACM, 2019, pp. 419–427.


# Rethinking the Optimization of Average Precision:
Only Penalizing Negative Instances before Positive Ones is Enough

Zhuo Li1,2, Weiqing Min1,2, Jiajun Song1,2, Yaohui Zhu1,2, Liping Kang3,
Xiaoming Wei3, Xiaolin Wei3 and Shuqiang Jiang1,2 Work done during an
internship at Meituan.Corresponding author.

###### Abstract

Optimizing the approximation of Average Precision (AP) has been widely studied
for image retrieval. Limited by the definition of AP, such methods consider
both negative and positive instances ranking before each positive instance.
However, we claim that only penalizing negative instances before positive ones
is enough, because the loss only comes from these negative instances. To this
end, we propose a novel loss, namely Penalizing Negative instances before
Positive ones (PNP), which can directly minimize the number of negative
instances before each positive one. In addition, AP-based methods adopt a
fixed and sub-optimal gradient assignment strategy. Therefore, we
systematically investigate different gradient assignment solutions via
constructing derivative functions of the loss, resulting in PNP-I with
increasing derivative functions and PNP-D with decreasing ones. PNP-I focuses
more on the hard positive instances by assigning larger gradients to them and
tries to make all relevant instances closer. In contrast, PNP-D pays less
attention to such instances and slowly corrects them. For most real-world
data, one class usually contains several local clusters. PNP-I blindly gathers
these clusters while PNP-D keeps them as they were. Therefore, PNP-D is more
superior. Experiments on three standard retrieval datasets show consistent
results with the above analysis. Extensive evaluations demonstrate that PNP-D
achieves the state-of-the-art performance. Code is available at
https://github.com/interestingzhuo/PNPloss

## Introduction

Image retrieval (Radenović, Tolias, and Chum 2019; Min et al. 2020) refers to
finding all images containing relevant content with the query from the
database. One important issue is to design the training objective. Recently,
some works propose to directly optimize the Average Precision (AP) (Revaud et
al. 2019; Brown et al. 2020; Cakir et al. 2019) to achieve end-to-end
training. Considering AP is non-differentiable and can’t be directly optimized
by the gradient descent, these works leverage some transformations to
approximate AP to make it differentiable. These methods greatly promote the
development of retrieval.

Figure 1: The functional image of AP-based loss $L_{AP}$: $R(i,S_{P})$ and
$R(i,S_{N})$ are the number of positive and negative instances before the
instance $i$, respectively, where $S_{P}$ is the similarity set between the
query and positive instances and $S_{N}$ is the similarity set between the
query and negative instances. Arrows are the optimal path of positive
instances.  Figure 2: Penalizing Negative instances before Positive ones
(PNP): PNP directly improves the retrieval performance by penalizing negative
instances before positive ones. Each arrow indicates the penalty of each
negative instance. Each negative instance will receive penalties from all
positive ones after it, thus the negative instance before more positive ones
will receive stronger penalty and be quickly corrected.

However, there are two problems for AP-based methods: (1) Redundancy exists in
the optimization of AP. Fig. 1 shows the functional image of AP-based loss
$L_{AP}$. As shown in Fig. 1, the goal of minimizing $L_{AP}$ is equivalent to
minimize $R(i,S_{N})$, because $L_{AP}=0$ only when $R(i,S_{N})$ = 0.
Therefore, the computation of $R(i,S_{P})$ is redundant. (2) Sub-optimal
gradient assignment strategy. Limited by the definition of AP, AP-based
methods only adopt one specific gradient assignment strategy. Specifically,
AP-based losses assign smaller gradient to larger $R(i,S_{N})$, as shown in
Fig. 1. Different gradient assignment strategies may result in different
performance. Therefore, it leaves room for us to systematically explore
different gradient assignment solutions to find potential better ones.

For the first problem, we propose a novel loss, namely Penalizing Negative
instances before Positive ones (PNP), which directly minimizes the number of
negative instances before each positive one. Therefore, each negative instance
will receive penalties from all positive ones after it. In terms of each
negative instance, if it ranks before more positive ones, it will receive more
penalties and be corrected more quickly. As shown in Fig. 2, image (a) will
receive more penalty because there are more positive instances after it and it
will be quickly corrected. In contrast, image (e) will be slowly corrected
because that there are fewer positive instances (image (f)) after it.

For the second problem, we systematically investigate different gradient
assignment solutions. We find that the derivative function of the loss
function defines different gradient assignment solutions. To this end, we
construct different derivative functions, which result in two different types
of PNP, namely PNP-I with increasing derivative functions and PNP-D with
decreasing ones. PNP-I assigns larger gradients to the positive instances with
more negative ones before and tries to gather all relevant samples together.
In contrast, PNP-D assigns smaller gradients to such positive instances.
Therefore, PNP-D will slowly correct these instances, which probably belong to
another center of the corresponding category. As shown in Fig. 2, PNP-I
assigns larger gradients to image (f) and tries to quickly correct it, because
there are more negative instances before it. In contrast, PNP-D assigns
smaller gradient to image (f) by considering it probably belongs to another
center of the corresponding category. For the real-world data, one class
usually contains several local clusters, and PNP-D is more suitable for such
case, thus may be more superior. Extensive evaluation on three standard
retrieval datasets shows that PNP-D achieves the state-of-the-art performance.

In summary, our major contributions are as follows:

  * •

We propose a novel loss function named PNP, which can improve the
approximation of AP by simply ignoring positive instances before the target
positive one.

  * •

To our knowledge, we are the first research to design loss functions via the
construction of their derivative functions. Based on the proposed method, we
systematically investigate different gradient assignment solutions and obtain
more appropriate loss functions.

  * •

Experimental results on three benchmark datasets demonstrate that the proposed
method achieves the state-of-the-art performance.

## Related Work

Image Retrieval. How to obtain a compact image descriptor for retrieval has
been widely studied (Radenović, Tolias, and Chum 2019; Min et al. 2020;
Tolias, Jenicek, and Chum 2020; Cao, Araujo, and Sim 2020). Previous works
bend their efforts for generating descriptors through an aggregation of local
features, such as Fisher vectors (Perronnin et al. 2010) and VLAD
(Arandjelovic and Zisserman 2013; Jégou et al. 2010). More recently, CNNs have
made impressive progress for image retrieval (Arandjelović et al. 2018;
Babenko et al. 2014; Albert et al. 2016; Radenović, Tolias, and Chum 2016;
Wang et al. 2014), because of their powerful nonlinear fitting capabilities.
Besides studying the design of neural network structure to generate
discriminative descriptors, there are also many researches on how to design
the training objective (Revaud et al. 2019; Hadsell, Chopra, and Lecun 2006;
Guiver and Snelson 2008; Sohn 2016; Sun et al. 2020; Qian et al. 2019; Gu, Ko,
and Kim 2021), which brings out another research topic, deep metric learning.

Deep Metric Learning. Deep metric learning has been widely studied because of
its important role in many tasks (Kim and Park 2021; Fu et al. 2021), such as
image retrieval. How to design the objective for such task is one important
topic. A wide variety of loss functions have been proposed in previous works.
These loss functions (Schroff, Kalenichenko, and Philbin 2015; Ji et al. 2017;
Engilberge et al. 2019) minimize the intra-class distance while maximize the
inter-class distance by considering the constructed pairs, tuples, etc. For
example, the triplet loss (Schroff, Kalenichenko, and Philbin 2015) directly
optimizes the relative ranking of positive and negative instances given an
anchor. However, there are too many pairs or tuples, and most of them are
useless for training. To solve this problem, many methods have been proposed,
such as pretraining for classification, combining multiple losses (Milbich et
al. 2020a, b) and using complex sample mining strategies (Manmatha et al.
2017).

Figure 3: PNP Loss: Derivative functions and loss functions of different
variants. PNP-Iu and PNP-Ib have increasing derivative functions, while PNP-Ds
and PNP-Dq have decreasing derivative functions.

Optimizing Average Precision (AP). Directly optimising AP has been widely
studied in the retrieval community. Various methods (Cakir et al. 2019; He et
al. 2018; He, Lu, and Sclaroff 2018; Revaud et al. 2019) have been proposed to
overcome the non-differentiability in optimizing AP, such as optimizing a
structured hinge-loss upper bound to the AP (Mohapatra et al. 2018),
optimizing an approximation of AP derived from distance quantization (Cakir et
al. 2019) and smoothing the path towards optimization (Brown et al. 2020).
These approximations rely on the definition of AP to achieve better retrieval
performance.

Different from above works, we propose the PNP loss, which directly minimizes
the number of negative instances before each positive one to improve the
retrieval performance. We further investigate different variants of PNP to
explore potential better gradient assignment solutions via the construction of
derivative functions. Extensive evaluations demonstrate that the proposed PNP
loss achieves the state-of-the-art performance on three benchmark datasets.

## Methodology

Given a query, the goal of retrieval systems is to rank all instances in a
retrieval set $\Omega=\\{I_{i},i=0,...,m\\}$ based on their similarities to
the query, where $I_{i}$ is an instance and $m$ is the size of the retrieval
set. For each query $I_{q}$, the set is split into a positive set $P_{q}$ and
a negative set $N_{q}$, which are composed by instances of the same class and
of different classes, respectively.

For the query $I_{q}$, the similarity set $S_{\Omega}$ of all instances in the
retrieval set are measured via a chosen similarity. In this paper, we use the
cosine similarity, and $S_{\Omega}$ can be defined as:

$S_{\Omega}=\\{s_{i}=cos(v_{q},v_{i}),i=0,...,m\\}$ (1)

where $v_{q}$, $v_{i}$ are the embeddings of $I_{q}$ and $I_{i}$,
respectively. $S_{\Omega}$ can be divided into $S_{P}$ and $S_{N}$, i.e.,
$S_{\Omega}=S_{P}\cup S_{N}$, where $S_{P}=\\{s_{i},\forall i\in P_{q}\\}$ and
$S_{N}=\\{s_{i},\forall i\in N_{q}\\}$ denote the positive and negative
similarity set, respectively.

Based on the similarity set, the number of negative instances before $I_{i}$
can be defined as:

$R(i,S_{N})=\sum_{j\in S_{N},j\neq i}\mathbb{I}\\{s_{j}-s_{i}>0\\}$ (2)

where $\mathbb{I}\\{\cdot\\}$ is an Indicator function.

Note that $R(i,S_{N})$ is not differentiable due to the Indicator function.
Similar to (Brown et al. 2020), we relax the Indicator function with a sigmoid
function $G(\cdot;\tau)$, where $\tau$ refers to the temperature for adjusting
the sharpness:

$G(x;\tau)=\frac{1}{1+e^{-\frac{x}{\tau}}}$ (3)

Substituting $G(\cdot;\tau)$ into Eq. 2, we can easily make $R(i,S_{N})$
differentiable.

### Definition of PNP

AP-based loss is defined as Eq. 4. The goal of minimizing $L_{AP}$ is
equivalent to minimize $R(i,S_{N})$, and thus the computation of $R(i,S_{P})$
in Eq. 4 is redundant.

$L_{AP}=1-\frac{1}{|S_{P}|}\sum_{i\in
S_{P}}\frac{1+R(i,S_{P})}{(1+R(i,S_{P})+R(i,S_{N}))}$ (4)

Therefore, we propose a PNP loss to directly minimize $R(i,S_{N})$. An
intuitive loss function $L_{O}$ can be defined as the number of negative
instances before each positive one:

$L_{O}=\frac{1}{|S_{P}|}\sum_{i\in S_{P}}R(i,S_{N})$ (5)

where $|S_{P}|$ is the normalization factor to remove the influence of the
number of positive instances in each mini-batch. Substituting Eq. 2 into Eq.
5, we can get the original PNP. As shown in Fig. 2, each negative instance
will receive penalties from all the positive ones ranking after it. Therefore,
negative instance with more positive ones after will receive more penalties
and will be quickly corrected. The PNP-O and its derivative function are shown
in Fig. 3 (a), and the gradient assignment of PNP-O is constant.

### Variants of PNP

Different gradient assignment strategies can result in different performance.
In this section, we systematically investigate different gradient assignment
solutions. Specifically, we design different variants of PNP by constructing
their derivative functions, resulting in PNP-Increasing (PNP-I) with
increasing derivative functions and PNP-Decreasing (PNP-D) with decreasing
ones.

#### PNP-Increasing (PNP-I)

According to the above definition, we should guarantee that the derivative
function of PNP-I is increasing. Without losing generality, we can divide
PNP-I into PNP-Iu with unbounded derivative function and PNP-Ib with bounded
derivative functions.

As for PNP-Iu, we use Eq. 6 as its derivative functions. The value of this
function will go down to zero when the loss is zero and go up to infinite when
the loss tends to be infinity. Then we get PNP-Iu via infinitesimal analysis,
shown in Eq. 7. $L_{I_{u}}$ has no hyper-parameters, and thus reduces the
difficulty of training.

$\frac{\partial L_{I_{u}}}{\partial R(i,S_{N})}=log(1+R(i,S_{N}))$ (6)
$L_{I_{u}}=\frac{1}{|S_{P}|}\sum_{i\in S_{P}}(1+R(i,S_{N}))*log(1+R(i,S_{N}))$
(7)

As for PNP-Ib, in order to satisfy the two requirements: increasing and
bounded, we use Eq. 8 as its derivative function. We introduce the parameter b
to achieve an adjustable boundary. Then we can also get PNP-Ib as Eq. 9.

$\frac{\partial L_{I_{b}}}{\partial
R(i,S_{N})}=\frac{R(i,S_{N})}{1+bR(i,S_{N})}$ (8)
$L_{I_{b}}=\frac{1}{|S_{P}|}\sum_{i\in
S_{P}}\frac{1}{b^{2}}(bR(i,S_{N})-log(1+bR(i,S_{N})))$ (9)

Loss functions and their derivative functions are shown in Fig. 3 (b)&(c). The
derivative functions of these two functions are both increasing, which means
that positive instances with more negative ones before will receive more
penalties and these two loss functions will try to make such hard positive
instances closer to the query.

#### PNP-Decreasing (PNP-D)

Specifically, we choose a common used decreasing function as the derivative
functions of PNP-D, shown in Eq. 10 and Eq. 11. The introduced parameter
$\alpha$ controls the speed of the descent, and larger $\alpha$ leads to
faster speed. These two derivative functions result in PNP-Ds with slow speed
and PNP-Dq with fast speed. After infinitesimal analysis, the PNP-Ds and PNP-
Dq will be Eq. 12 and Eq. 13, respectively.

Figure 4: Comparison between PNP-I and PNP-D: The dashed arrows represent the
directions of optimization. Different colors represent different categories. b
and y represent centers of different categories. It is worth mentioning that
b1 and b2 are different centers of class b. PNP-I blindly makes b1 and b2
closer while PNP-D keeps such instances distribute into two clusters.

$\frac{\partial L_{D_{s}}}{\partial R(i,S_{N})}=\frac{1}{(1+R(i,S_{N}))}$ (10)
$\frac{\partial L_{D_{q}}}{\partial
R(i,S_{N})}=\frac{\alpha}{(1+R(i,S_{N}))^{\alpha+1}}\quad(\alpha\geq 1)$ (11)

$L_{D_{s}}=\frac{1}{|S_{P}|}\sum_{i\in S_{P}}log(1+R(i,S_{N}))$ (12)
$L_{D_{q}}=1-\frac{1}{|S_{P}|}\sum_{i\in
S_{P}}\frac{1}{(1+R(i,S_{N}))^{\alpha}}\quad(\alpha\geq 1)$ (13)

Loss functions and their derivative functions of PNP-D are shown in Fig. 3
(d)&(e). The derivative functions of these two functions are both decreasing,
which means that positive instances with fewer negative ones before will
receive more penalties and these two loss functions will quickly correct such
instances.

Method | R@1 (%) | R@10 (%) | R@100 (%) | R@1K (%) | Dists@intra | Dists@inter | NMI (%)
---|---|---|---|---|---|---|---
PNP-O | 77.9 | 90.5 | 96.3 | 98.9 | 0.318 | 0.793 | 90.0
PNP-Iu | 76.3 | 89.6 | 96.0 | 98.9 | 0.301 | 0.771 | 89.6
PNP-Ib | 77.9 | 90.4 | 96.3 | 98.9 | 0.302 | 0.756 | 90.0
PNP-Ds | 79.6 | 91.4 | 96.6 | 99.0 | 0.363 | 0.849 | 90.3
PNP-Dq | 80.1 | 91.5 | 96.7 | 99.0 | 0.380 | 0.946 | 90.4
Table 1: Results on different variants of the PNP loss on SOP (BS = 112).  Method | Small (%) | Medium (%) | Large (%) | Dists@intra | Dists@inter | NMI (%)
---|---|---|---|---|---|---
R@1 | R@5 | R@1 | R@5 | R@1 | R@5
PNP-O | 93.6 | 97.1 | 91.6 | 95.9 | 89.2 | 95.4 | 0.165 | 0.791 | 90.5
PNP-Iu | 92.4 | 96.9 | 90.4 | 95.4 | 87.6 | 94.8 | 0.137 | 0.727 | 90.0
PNP-Ib | 94.0 | 97.3 | 92.0 | 96.0 | 89.9 | 95.4 | 0.144 | 0.674 | 90.6
PNP-Ds | 94.3 | 97.3 | 92.7 | 96.4 | 91.0 | 95.9 | 0.203 | 0.865 | 90.8
PNP-Dq | 94.6 | 97.4 | 92.9 | 96.3 | 91.4 | 95.9 | 0.204 | 0.974 | 91.0
Table 2: Results on different variants of the PNP loss on VehicleID (BS =
112).

#### Discussion

PNP-I assigns larger gradients to positive instances with more negative ones
before, while PNP-D assigns smaller gradients to such positive instances.
PNP-I tries to make all the relevant instances together. In contrast, PNP-D
only quickly corrects positive instances with fewer negative ones before,
because such samples are considered to belong to the same center with the
query. As shown in Fig. 4, if $b_{1}$ and $b_{2}$ are sampled into one batch.
PNP-I will try to make them gather by assigning larger gradients. In contrast,
considering too many negative instances (yellow) between them, PNP-D will
assign smaller gradients to them and keep the multi-center distribution for
the blue class. PNP-D can satisfy such distribution which is also mentioned by
(Qian et al. 2019), and thus is superior to PNP-I. Such analysis has been
further verified via our comprehensive experimental evaluation.

We just conduct above four variants of PNP. Actually, our proposed design
strategy is general and similar strategies can be further explored to find
more solutions.

Figure 5: Relation between PNP and AP-based loss: The gradients of AP-based
loss with respect to $R(i,S_{N})$ when $R(i,S_{P})$ = 0,1,2,3. The gradients
of PNP-D ($\alpha$ = 2) is steeper than AP-based loss.

### Relation between PNP and AP

In this section, we investigate the relation between PNP and AP. The
derivative function of AP-based loss with respect to $R(i,S_{N})$ is shown in
Eq. 14 and its functional image is shown in Fig. 5. AP-based methods have
similar gradient assignment with PNP-D.

$\frac{\partial L_{AP}}{\partial
R(i,S_{N})}=\frac{1+R(i,S_{P})}{(1+R(i,S_{P})+R(i,S_{N}))^{2}}$ (14)

However, AP-based methods use different gradient assignments by considering
the positions of positive instances. When too many positive instances rank
before the target positive instance ($R(i,S_{P})=3$), the gradient respect to
$R(i,S_{N})$ is almost to be equal for different $R(i,S_{N})$. It weakens the
advantage of such gradient assignment, probably leading to worse retrieval
performance for AP. In contrast, PNP can further enhance such advantage and
finally achieve competitive performance.

## Experiment

### Dataset

We use the following three popular datasets as the benchmark datasets.

Stanford Online Products (SOP) (Song et al. 2016) contains 120,053 product
images divided into 22,634 classes. The training set contains 11,318 classes
with 59,551 images and the rest 11,316 classes with 60,502 images are for
testing.

VehicleID (Liu et al. 2016) contains 221,736 images of 26,267 vehicle
categories, where 13,134 categories with 110,178 images are used for training.
Following the same test protocol as (Liu et al. 2016), three test sets of
increasing sizes are used for evaluation (termed small, medium, large), which
contain 800 classes (7,332 images), 1,600 classes (12,995 images) and 2,400
classes (20,038 images), respectively.

INaturalist (Van Horn et al. 2018) is a large-scale animal and plant species
classification dataset with 461,939 images from 8,142 classes. We follow the
setting from (Brown et al. 2020) by keeping 5,690 classes for training, and
2,452 unseen classes for testing.

### Experimental Setup

We use the convolutional layers of ResNet-50 pretrained on ImageNet (He et al.
2016) to perform the training. The models are optimized using Adam (Kingma and
Ba 2015), we set the initial learning rate $10^{-5}$, weight decay 4 ×
$10^{-4}$. During training, we randomly sample k classes and $|P|$ samples per
class to form each mini-batch. Following standard practice, we resize images
to 256 × 256, and randomly crop them to 224 × 224 as input. Random flipping
($p=0.5$) is used during training for data augmentation, and a single center
crop of 224 × 224 is used during evaluation. We use 0 as the fixed random seed
for all experiments to avoid seed-based performance fluctuations. During
training, we directly set $\tau$ in Eq. 3 to 0.01 which is explored in (Brown
et al. 2020).

For all the datasets, every instance from each class is used in turn as the
query $I_{q}$, and the retrieval set $\Omega$ is formed as all the remaining
instances. Recall@k (R@k) is adopted as the main evaluation metric. In order
to evaluate the generalization of the model, we also display dists@intra (Mean
Intraclass Distance), dists@inter (Mean Interclass Distance) (Roth et al.
2020) and Normalized Mutual Information (NMI) (Schütze, Manning, and Raghavan
2008) for further performance analysis. BS represents mini-batch size.

### Performance of Different PNP Variants

In this section, we investigate different variants of PNP on two popular
benchmark datasets. The batch size of experiments in Table 1 and Table 2 are
both 112. We report the best performance of different variants and the impact
of hyper-parameters is shown in Fig. 8.

We present R@k, Distance and NMI in Table 1 and Table 2. PNP-D consistenly
outperforms PNP-O and PNP-I on two benchmark datasets for R@k and achieves
larger dists@intra, dists@inter and NMI, which shows better generalization of
the model (Roth et al. 2020). Specifically, PNP-D is 2.1% higher than PNP-O on
SOP benchmark and 0.9% higher on VehicleID for R@1. In contrast, PNP-I is
worse than PNP on R@1, and it is about 1% lower than PNP on SOP benchmark 1-2%
on VehicleID for R@1.

Figure 6: Illustration of the effect of different variants. (a) training and
test data (b) The network trained with PNP-I fails to separate all test
classes due to the aggregation of all relevant instances. (c) The PNP-D
successfully separates the test classes by keeping the intra-class variance.

PNP-I assigns larger gradients to positive instances which have more negative
ones before, thus it will enforce relevant images to gather and result in
smaller dists@intra and dists@inter. In contrast, PNP-D assigns smaller
gradients to such instances and slowly optimizes them by considering that they
have a high probability of belonging to other centers of the corresponding
category, and therefore it has larger dists@intra and dists@inter. By this
strategy, PNP-D can adaptively achieve “multi-centers” for each category if
necessary and automatically adjust the number of clusters. Such strategy also
solves the error correction of noise by considering the noisy data as another
center.

Previous works have found that larger dists@intra and dists@inter will produce
better generalization (Roth et al. 2020). The results shown in Table 1 and
Table 2 further confirm such conclusion. Compared to PNP-I, PNP-D has larger
dists@intra and dists@inter, and results in larger NMI, which shows better
generalization of the model. Similar to (Roth et al. 2020), we conduct one
experiment to illustrate the performance of two loss functions. Specifically,
we use a fully-connected network with two layers and 30 neurons for each
layer. The dimensions of input and embeddings are both 2D, and the embeddings
are normalized on a unit circle. As shown in Fig. 6 (a), each of four training
and test classes contains 150 samples, respectively. We train the networks
using PNP-Ib and PNP-Dq, respectively. Fig. 6 illustrates the effect of two
loss functions. PNP-I fails to separate all test classes in Fig. 6 (b) while
PNP-D successfully separates them (with larger intra-class variance) in Fig. 6
(c) . It shows that PNP-D enables the model to capture more information and
exhibits stronger generalization to the unseen test classes by retaining the
variance within the class in the training process.

Figure 7: Image retrieval examples on three datasets. Images with green border are positive instances and these with red border are negative ones for the query. Method | R@1 | R@10 | R@100 | R@1K
---|---|---|---|---
Hist. (Ustinova and Lempitsky 2016) | 72.4 | 86.1 | 94.1 | 98.3
Margin (Manmatha et al. 2017) | 72.7 | 86.2 | 93.8 | 98.0
Divide (Sanakoyeu et al. 2019) | 75.9 | 88.4 | 94.9 | 98.1
FastAP (Cakir et al. 2019) | 76.4 | 89.0 | 95.1 | 98.2
MIC (Brattoli et al. 2019) | 77.2 | 89.4 | 95.6 | -
SoftTriplet (Qian et al. 2019) | 78.3 | 90.3 | 95.9 | -
RankMI (Kemertas et al. 2020) | 74.3 | 87.9 | 94.9 | 98.3
Blackbox AP (Rolínek et al. 2020) | 78.6 | 90.5 | 96.0 | 98.7
Cont. w/M (Wang et al. 2020) | 80.6 | 91.6 | 96.2 | 98.7
Pnca++ (Teh, DeVries, and Taylor 2020) | 80.7 | 92.0 | 96.7 | 98.9
Smooth-AP (Brown et al. 2020) | 80.1 | 91.5 | 96.6 | 99.0
DCML-MDW (Zheng et al. 2021) | 79.8 | 90.8 | 95.8 | -
PNP-Dq (BS = 112) | 80.1 | 91.5 | 96.7 | 99.0
PNP-Dq (BS = 384) | 81.1 | 92.2 | 96.8 | 99.0
Table 3: Performance comparison on SOP (%).

### Comparison with State-of-the-art

We compare PNP loss to the recent AP-based methods and a series of state-of-
the-art deep metric learning methods on three standard benchmarks.

#### SOP

For fair comparison, we use the same setting with (Brown et al. 2020). Table 3
shows the performance on SOP, we observe that PNP-Dq achieves the state-of-
the-art results. In particular, our model outperforms other methods on all
evaluation metrics and outperforms AP approximating methods by 0.5 - 4% on R@1
when the same batch size (384) and dimension (512) are used. Note that,
although current work (Cont. w/M (Wang et al. 2020)) uses memory techniques to
sample from many mini-batches simultaneously for each iteration, our best
model still outperforms this method, only using a single mini-batch on each
iteration.

Method | Small | Medium | Large
---|---|---|---
R@1 | R@5 | R@1 | R@5 | R@1 | R@5
Divide (Sanakoyeu et al. 2019) | 87.7 | 92.9 | 85.7 | 90.4 | 82.9 | 90.2
MIC. (Brattoli et al. 2019) | 86.9 | 93.4 | - | - | 82.0 | 91.0
FastAP (Cakir et al. 2019) | 91.9 | 96.8 | 90.6 | 95.9 | 87.5 | 95.1
Cont. w/M (Wang et al. 2020) | 94.7 | 96.8 | 93.7 | 95.8 | 93.0 | 95.8
Smooth-AP (Brown et al. 2020) | 94.9 | 97.6 | 93.3 | 96.4 | 91.9 | 96.2
PNP-Dq (BS = 112) | 94.6 | 97.4 | 92.9 | 96.3 | 91.4 | 95.9
PNP-Dq (BS = 384) | 95.5 | 97.8 | 94.2 | 96.9 | 93.2 | 96.6
Table 4: Performance comparison on VehicleID (%). Method | R@1 | R@4 | R@16 | R@32
---|---|---|---|---
Triplet (Manmatha et al. 2017) | 58.1 | 75.5 | 86.8 | 90.7
Proxy NCA (Yair et al. 2017) | 61.6 | 77.4 | 87.0 | 90.6
FastAP (Cakir et al. 2019) | 60.6 | 77.0 | 87.2 | 90.6
Blackbox AP (Rolínek et al. 2020) | 62.9 | 79.0 | 88.9 | 92.1
Smooth-AP (Brown et al. 2020) | 65.9 | 80.9 | 89.8 | 92.7
PNP-Dq (BS = 224) | 66.6 | 81.1 | 89.7 | 92.6
Table 5: Performance comparison on INaturalist (%). Method | R@1 | R@10 | R@100 | R@1K
---|---|---|---|---
Smooth-AP | 73.2 | 86.4 | 93.6 | 97.5
PNP-Iu | 67.5 | 82.7 | 92.3 | 97.5
PNP-Dq | 73.8 | 87.1 | 94.2 | 98.0
Table 6: Evaluation of robustness on SOP (%). Method | Small | Medium | Large
---|---|---|---
R@1 | R@5 | R@1 | R@5 | R@1 | R@5
Smooth-AP | 89.9 | 95.8 | 88.6 | 94.3 | 85.2 | 93.2
PNP-Iu | 86.9 | 94.0 | 85.0 | 92.6 | 80.8 | 90.7
PNP-Dq | 92.6 | 96.3 | 90.8 | 95.3 | 88.6 | 94.6
Table 7: Evaluation of robustness on VehicleID (%). Figure 8: Impact of
different hyper-parameters on SOP and VehicleID. (a) steepness $\alpha$, (b)
boundary b, (c) samples per class during mini batch sampling $|P|$.

#### VehicleID

We further conduct experiments on VehicleID to verify the performance of PNP
on large-scale retrieval datasets. Table 4 shows the results on the VehicleID
dataset. For the same batch size (384) and dimension (512), we observe that
PNP-Dq again achieves state-of-the-art performance on the large-scale
VehicleID dataset on all the evaluation metrics. Such result shows that PNP-D
also works better on large-scale datasets.

#### INaturalist

As shown in Table 5, our method also outperforms the best method by 0.7% on
R@1 for the experiments on INaturalist with the same batch size (224) and
dimension (512). These results demonstrate that PNP is particularly suitable
for large-scale retrieval datasets, which demonstrates its scalability to
real-world retrieval problems.

### Impact of Hyper-parameters

To investigate the effect of different hyper-parameter settings, i.e.,
steepness $\alpha$ in Eq. 13, boundary $b$ in Eq. 8, samples per class $|P|$,
we train ResNet-50 on SOP and VehicleID. The random seed is fixed to 0 and the
batch size is set to 112 for all experiments in this section.

Steepness $\alpha$: The influence of $\alpha$ of PNP-Dq is shown in Fig. 8
(a). We can find that larger $\alpha$ results in larger R@1. It can be
explained that larger $\alpha$ corresponds to more stable optimization
(correct positive instances with sufficient confidence), and thus achieves
better performance. However, when $\alpha$ is too large, the training phrase
will crash due to the gradient exploding. Therefore, we use as larger $\alpha$
as possible to get better performance.

Boundary $b$: The influence of $b$ for PNP-Ib is shown in Fig. 8 (b). $b=4$ is
the best on SOP while $b=1$ is the best on VehicleID. $b$ controls the biggest
gradient of the PNP-Ib with respect to $R(i,S_{N})$, and different datasets
require different adjusting range. We report the best value for the comparison
of different variants.

Samples Per Class $|P|$: The influence of the samples per class $|P|$ in a
mini-batch is shown in Fig. 8 (c). We observe that $|P|$ = 4 results in the
highest R@1. The probable reason is that mini-batches are formed by sampling
from each class, where a low value means a larger number of sampled classes
and a higher probability of sampling hard-negative instances that violate the
correct ranking order. Increasing the number of classes in the batch results
in a better batch approximation of the true class distribution, allowing each
training iteration to enforce a more optimally structured embedding space.
However, too small value ($|P|$ = 2) leads to worse performance because it can
not give enough positive instances to violate the correct ranking order for
training.

### Evaluation of Robustness

In order to evaluate the robustness and the performance of multi-centers per
class, we perform extensive experiments on constructed datasets in this
section. Specifically, we use the train set of SOP and VehicleID as benchmark
datasets and merge every three categories to form one new class with multi-
centers (at least three centers per class). As for evaluation, we still use
original test set to evaluate the model. During the training, we use PNP-Ib,
PNP-Dq and Smooth-AP as loss functions.

The results are shown in Table 6, 7. Compared with using original training
set, these three methods all have performance loss on two benchmark datasets.
Generally, PNP-Dq and Smooth-AP with similar gradient assignment strategy have
less performance loss than PNP-Ib because of their adaptability to multi-
centers, and PNP-D achieves the best performance. Specifically, for VehicleID,
PNP-D exceeds the performance of Smooth-AP by 2 - 3% and PNP-I by a
significant 6 - 8% on R@1.

The above results show better robustness of PNP-D. Noisy data is inevitable in
the real-world data and it will leads to the instability of training. The
above experiments show that PNP-D can achieve comparable performance, even if
there are a lot of wrong annotations in datasets. This is because PNP-D can
automatically remove the interference of noisy data by putting it in a single
center.

## Conclusions

In this paper, we propose a novel PNP loss, which directly improves the
retrieval performance by penalizing negative instances before positive ones.
Moreover, we find that different derivative functions of losses correspond to
different gradient assignments. Therefore, we systematically investigate
different gradient assignment solutions via constructing derivative functions
of losses, resulting in PNP-I and PNP-D. PNP-D consistently achieve state-of-
the-art performance on three benchmark datasets. We just provide four variants
and will explore more forms via similar strategy in the future. In addition,
we hope the proposed strategy for designing loss functions can also be applied
to other tasks.

## Acknowledgments

This work was supported in part by Beijing Natural Science Foundation under
Grant L182054, in part by the National Natural Science Foundation of China
under Grant 62125207, 61972378, 61532018, U1936203, U19B2040. This research
was also supported by Meituan-Dianping Group.

## References

  * Albert et al. (2016) Albert, G.; Jon, A.; Jerome, R.; and Larlus, D. 2016.  Deep Image Retrieval: Learning Global Representations for Image Search.  In _European Conference on Computer Vision_ , 241–257.
  * Arandjelovic and Zisserman (2013) Arandjelovic, R.; and Zisserman, A. 2013.  All About VLAD.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 1578–1585.
  * Arandjelović et al. (2018) Arandjelović, R.; Gronat, P.; Torii, A.; Pajdla, T.; and Sivic, J. 2018\.  NetVLAD: CNN Architecture for Weakly Supervised Place Recognition.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 40(6): 1437–1451.
  * Babenko et al. (2014) Babenko, A.; Slesarev, A.; Chigorin, A.; and Lempitsky, V. 2014.  Neural Codes for Image Retrieval.  In _European Conference on Computer Vision_ , 584–599.
  * Brattoli et al. (2019) Brattoli, B.; Roth, K.; Ommer; and Bjorn. 2019.  MIC: Mining Interclass Characteristics for Improved Metric Learning.  In _IEEE International Conference on Computer Vision_ , 7999–8008.
  * Brown et al. (2020) Brown, A.; Xie, W.; Kalogeiton, V.; and Zisserman, A. 2020.  Smooth-AP: Smoothing the Path Towards Large-Scale Image Retrieval.  In _European Conference on Computer Vision_ , 677–694.
  * Cakir et al. (2019) Cakir, F.; He, K.; Xia, X.; Kulis, B.; and Sclaroff, S. 2019.  Deep Metric Learning to Rank.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 1861–1870.
  * Cao, Araujo, and Sim (2020) Cao, B.; Araujo, A.; and Sim, J. 2020.  Unifying Deep Local and Global Features for Image Search.  In _European Conference on Computer Vision_ , 726–743.
  * Engilberge et al. (2019) Engilberge, M.; Chevallier, L.; Perez, P.; and Cord, M. 2019.  SoDeep: A Sorting Deep Net to Learn Ranking Loss Surrogates.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 10792–10801.
  * Fu et al. (2021) Fu, Z.; Li, Y.; Mao, Z.; Wang, Q.; and Zhang, Y. 2021.  Deep Metric Learning with Self-Supervised Ranking.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 1370–1378.
  * Gu, Ko, and Kim (2021) Gu, G.; Ko, B.; and Kim, H.-G. 2021.  Proxy Synthesis: Learning with Synthetic Classes for Deep Metric Learning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 1460–1468.
  * Guiver and Snelson (2008) Guiver, J.; and Snelson, E. 2008.  Learning to rank with SoftRank and Gaussian processes.  In _Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , 259–266.
  * Hadsell, Chopra, and Lecun (2006) Hadsell, R.; Chopra, S.; and Lecun, Y. 2006.  Dimensionality Reduction by Learning an Invariant Mapping.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 1735 – 1742.
  * He et al. (2018) He, K.; Cakir, F.; Bargal, S.; and Sclaroff, S. 2018.  Hashing as Tie-Aware Learning to Rank.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 4023–4032.
  * He, Lu, and Sclaroff (2018) He, K.; Lu, Y.; and Sclaroff, S. 2018.  Local Descriptors Optimized for Average Precision.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 596–605.
  * He et al. (2016) He, K.; Zhang, X.; Ren, S.; and Sun, J. 2016.  Deep Residual Learning for Image Recognition.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 770–778.
  * Ji et al. (2017) Ji, X.; Wang, W.; Zhang, M.; and Yang, Y. 2017.  Cross-Domain Image Retrieval with Attention Modeling.  In _Proceedings of the ACM Multimedia Conference_ , 1654–1662.
  * Jégou et al. (2010) Jégou, H.; Douze, M.; Schmid, C.; and Perez, P. 2010.  Aggregating local descriptors into a compact image representation.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 3304 – 3311.
  * Kemertas et al. (2020) Kemertas, M.; Pishdad, L.; Derpanis, K. G.; and Fazly, A. 2020.  RankMI: A Mutual Information Maximizing Ranking Loss.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 14362–14371.
  * Kim and Park (2021) Kim, Y.; and Park, W. 2021.  Multi-level Distance Regularization for Deep Metric Learnin.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , 1827–1835.
  * Kingma and Ba (2015) Kingma, D.; and Ba, J. 2015.  Adam: A Method for Stochastic Optimization.  In _International Conference on Learning Representations_ , 1–15.
  * Liu et al. (2016) Liu, H.; Tian, Y.; Wang, Y.; Pang, L.; and Huang, T. 2016.  Deep Relative Distance Learning: Tell the Difference Between Similar Vehicles.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 2167–2175.
  * Manmatha et al. (2017) Manmatha, R.; Wu, C.-Y.; Smola, A.; and Krahenbuhl, P. 2017.  Sampling Matters in Deep Embedding Learning.  In _IEEE International Conference on Computer Vision_ , 2859–2867.
  * Milbich et al. (2020a) Milbich, T.; Roth, K.; Bharadhwaj, H.; Sinha, S.; Bengio, Y.; Ommer, B.; and Cohen, J. P. 2020a.  DiVA: Diverse Visual Feature Aggregation for Deep Metric Learning.  In _European Conference on Computer Vision_ , 590–607.
  * Milbich et al. (2020b) Milbich, T.; Roth, K.; Brattoli, B.; and Ommer, B. 2020b.  Sharing Matters for Generalization in Deep Metric Learning.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , PP(99): 1–1.
  * Min et al. (2020) Min, W.; Mei, S.; Li, Z.; and Jiang, S. 2020.  A Two-Stage Triplet Network Training Framework for Image Retrieval.  _IEEE Transactions on Multimedia_ , 22(12): 3128–3138.
  * Mohapatra et al. (2018) Mohapatra, P.; Rolinek, M.; Jawahar, C. V.; Kolmogorov, V.; and Kumar, M. P. 2018\.  Efficient Optimization for Rank-Based Loss Functions.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 3693–3701.
  * Perronnin et al. (2010) Perronnin, F.; Liu, Y.; Sánchez, J.; and Poirier, H. 2010.  Large-scale image retrieval with compressed Fisher vectors.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 3384–3391.
  * Qian et al. (2019) Qian, Q.; Shang, L.; Sun, B.; Hu, J.; Tacoma, T.; Li, H.; and Jin, R. 2019.  SoftTriple Loss: Deep Metric Learning Without Triplet Sampling.  In _IEEE International Conference on Computer Vision_ , 6449–6457.
  * Radenović, Tolias, and Chum (2016) Radenović, F.; Tolias, G.; and Chum, O. 2016.  CNN Image Retrieval Learns from BoW: Unsupervised Fine-Tuning with Hard Examples.  In _European Conference on Computer Vision_ , 3–20.
  * Radenović, Tolias, and Chum (2019) Radenović, F.; Tolias, G.; and Chum, O. 2019.  Fine-tuning CNN Image Retrieval with No Human Annotation.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 41(7): 1655–1668.
  * Revaud et al. (2019) Revaud, J.; Almazan, J.; Rezende, R.; and De Souza, C. 2019.  Learning With Average Precision: Training Image Retrieval With a Listwise Loss.  In _IEEE International Conference on Computer Vision_ , 5107–5116.
  * Rolínek et al. (2020) Rolínek, M.; Musil, V.; Paulus, A.; Vlastelica, M.; Michaelis, C.; and Martius, G. 2020.  Optimizing Rank-Based Metrics With Blackbox Differentiation.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 7617–7627.
  * Roth et al. (2020) Roth, K.; Milbich, T.; Sinha, S.; Gupta, P.; Ommer, B.; and Cohen, J. P. 2020.  Revisiting training strategies and generalization performance in deep metric learning.  In _International Conference on Machine Learning_ , 8242–8252.
  * Sanakoyeu et al. (2019) Sanakoyeu, A.; Tschernezki, V.; Büchler, U.; and Ommer, B. 2019.  Divide and Conquer the Embedding Space for Metric Learning.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 471–480.
  * Schroff, Kalenichenko, and Philbin (2015) Schroff, F.; Kalenichenko, D.; and Philbin, J. 2015.  FaceNet: A unified embedding for face recognition and clustering.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 815–823.
  * Schütze, Manning, and Raghavan (2008) Schütze, H.; Manning, C. D.; and Raghavan, P. 2008.  _Introduction to information retrieval_ , volume 39.  Cambridge University Press Cambridge.
  * Sohn (2016) Sohn, K. 2016.  Improved deep metric learning with multi-class n-pair loss objective.  In _Advances in Neural Information Processing Systems_ , 1857–1865.
  * Song et al. (2016) Song, H. O.; Xiang, Y.; Jegelka, S.; and Savarese, S. 2016.  Deep metric learning via lifted structured feature embedding.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 4004–4012.
  * Sun et al. (2020) Sun, Y.; Cheng, C.; Zhang, Y.; Zhang, C.; Zheng, L.; Wang, Z.; and Wei, Y. 2020.  Circle Loss: A Unified Perspective of Pair Similarity Optimization.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 6397–6406.
  * Teh, DeVries, and Taylor (2020) Teh, E. W.; DeVries, T.; and Taylor, G. W. 2020.  ProxyNCA++: Revisiting and Revitalizing Proxy Neighborhood Component Analysis.  In _European Conference on Computer Vision_ , 448–464.
  * Tolias, Jenicek, and Chum (2020) Tolias, G.; Jenicek, T.; and Chum, O. 2020.  Learning and Aggregating Deep Local Descriptors for Instance-Level Recognition.  In _European Conference on Computer Vision_ , 460–477.
  * Ustinova and Lempitsky (2016) Ustinova, E.; and Lempitsky, V. 2016.  Learning Deep Embeddings with Histogram Loss.  In _Annual Conference on Neural Information Processing Systems_ , 4170–4178.
  * Van Horn et al. (2018) Van Horn, G.; Mac Aodha, O.; Song, Y.; Cui, Y.; Sun, C.; Shepard, A.; Adam, H.; Perona, P.; and Belongie, S. 2018.  The inaturalist species classification and detection dataset.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 8769–8778.
  * Wang et al. (2014) Wang, J.; Song, Y.; Leung, T.; Rosenberg, C.; Wang, J.; Philbin, J.; Chen, B.; and Wu, Y. 2014.  Learning Fine-Grained Image Similarity with Deep Ranking.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 1386–1393.
  * Wang et al. (2020) Wang, X.; Zhang, H.; Huang, W.; and Scott, M. R. 2020.  Cross-Batch Memory for Embedding Learning.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 6387–6396.
  * Yair et al. (2017) Yair, M.-A.; Toshev, A.; Leung, T.; Ioffe, S.; and Singh, S. 2017.  No Fuss Distance Metric Learning Using Proxies.  In _IEEE International Conference on Computer Vision_ , 360–368.
  * Zheng et al. (2021) Zheng, W.; Wang, C.; Lu, J.; and Zhou, J. 2021.  Deep Compositional Metric Learning.  In _IEEE Conference on Computer Vision and Pattern Recognition_ , 9320–9329.