# HyP2 Loss: Beyond Hypersphere Metric Space for Multi-label Image Retrieval

Chengyin Xu  SIGS, Tsinghua University ,  Zenghao Chai  SIGS, Tsinghua
University ,  Zhengzhuo Xu  SIGS, Tsinghua University ,  Chun Yuan  SIGS,
Tsinghua University Peng Cheng National Laboratory ,  Yanbo Fan  Tencent AI
Lab and  Jue Wang  Tencent AI Lab

(2022)

###### Abstract.

Image retrieval has become an increasingly appealing technique with broad
multimedia application prospects, where deep hashing serves as the dominant
branch towards low storage and efficient retrieval. In this paper, we carried
out in-depth investigations on metric learning in deep hashing for
establishing a powerful metric space in multi-label scenarios, where the pair
loss suffers high computational overhead and converge difficulty, while the
proxy loss is theoretically incapable of expressing the profound label
dependencies and exhibits conflicts in the constructed hypersphere space. To
address the problems, we propose a novel metric learning framework with Hybrid
Proxy-Pair Loss (HyP2 Loss) that constructs an expressive metric space with
efficient training complexity w.r.t. the whole dataset. The proposed HyP2 Loss
focuses on optimizing the hypersphere space by learnable proxies and
excavating data-to-data correlations of irrelevant pairs, which integrates
sufficient data correspondence of pair-based methods and high-efficiency of
proxy-based methods. Extensive experiments on four standard multi-label
benchmarks justify the proposed method outperforms the state-of-the-art, is
robust among different hash bits and achieves significant performance gains
with a faster, more stable convergence speed. Our code is available at
https://github.com/JerryXu0129/HyP2-Loss.

Image Retrieval, Deep Hashing, Multi-label, Metric Learning

††journalyear: 2022††copyright: rightsretained††conference: Proceedings of the
30th ACM International Conference on Multimedia; October 10–14, 2022; Lisboa,
Portugal††booktitle: Proceedings of the 30th ACM International Conference on
Multimedia (MM ’22), Oct. 10–14, 2022, Lisboa, Portugal††isbn:
978-1-4503-9203-7/22/10††doi: 10.1145/3503161.3548032††ccs: Computing
methodologies Image representations††ccs: Information systems Top-k retrieval
in databases \begin{overpic}[trim=0.0pt 0.0pt 0.0pt
0.0pt,clip,width=368.57964pt,grid=false]{imgs/teaser.png}
\put(18.0,46.0){\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{Proxy_anchor_loss}{\@@citephrase{,
}}{})}}
\put(18.0,38.0){\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{IDHN}{\@@citephrase{,
}}{})}}
\put(18.0,20.0){\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{Proxy_anchor_loss}{\@@citephrase{,
}}{})}}
\put(18.0,12.0){\cite[citep]{(\@@bibref{AuthorsPhrase1Year}{IDHN}{\@@citephrase{,
}}{})}} \end{overpic} Figure 1. Retrieval comparisons to previous methods
(Zhang et al., 2020; Kim et al., 2020) $\bm{\&}$ ours on the Flickr-25k
(Huiskes and Lew, 2008) dataset (top) $\bm{\&}$ NUS-WIDE (Chua et al., 2009)
dataset (bottom). The Top-$\bm{10}$ images are returned according to the
Hamming distance between the query image and the database. The number below
each retrieved image indicates the matched categories, green (red) box
indicates matched categories

$\bm{\geq 75\%}$

(

$\bm{\leq 25\%}$

). The proposed HyP2 Loss outperforms state-of-the-art (Kim et al., 2020;
Zhang et al., 2020) with fewer contradictions and misclassified results.

##  1\. Introduction

The past decades have witnessed the arrival of the era of big data, floods of
images are uploaded to social platforms and search engines day and night,
which calls for more efficient and accurate image retrieval in multimedia
applications (Feng et al., 2020; Xia et al., 2021; Tu et al., 2021; Cui et
al., 2021; Li et al., 2021). Real-world images typically contain more than one
attribute. Hence, the multi-label retrieval task (Rodrigues et al., 2020; Li
et al., 2021) serves as the crucial and more challenging branch in large-scale
image retrieval.

Hashing techniques (Datta et al., 2008; Zhang and Rui, 2013) are widely used
to accelerate retrieval due to the low storage and computation costs. The
retrieval system can utilize an efficient bit-wise XOR operation to estimate
the distance between hash code pairs. Following the prosperous progress of
Deep Neural Networks (DNNs) in visual recognition, deep hashing (Xia et al.,
2014; Cao et al., 2017) has achieved glary attention and become one of the
most substantial research topics in the image retrieval community (Wang et
al., 2018; Chen et al., 2021; Wang et al., 2016a). The target of deep hashing
is to project numerous samples into the hyper metric space and then convert
them into compact binary codes through hash functions. The parameterized
networks are optimized such that semantically similar data (_i.e_., images
with the same categories) are well clustered and distributed in the
established metric space. Such quality and expressiveness of the metric space
are optimized through elaborate-designed loss functions in a supervised manner
during metric learning.

Pair-based methods (Zhao et al., 2015; Lai et al., 2015; Huang et al., 2018;
Lai et al., 2016; Zhang et al., 2020) are predominant in multi-label
retrieval, which directly consider data-to-data connections in a mini-batch.
However, such approaches prohibitively confront high training complexity that
require square (Zhang et al., 2020; Chopra et al., 2005; Hadsell et al., 2006;
Harwood et al., 2017; Bromley et al., 1993) or even higher (Schroff et al.,
2015; Sohn, 2016; Song et al., 2016) complexity w.r.t. the number of training
samples. Furthermore, the data-to-data correlations in a mini-batch could
deteriorate the robustness and degrade the learned metric space because of the
increasing overfitting risks and training instability.

Compared to the pair-based methods, proxy-based methods (Kim et al., 2020;
Movshovitz et al., 2017) are more efficient and effective in single-label
retrieval to embed samples into a proxy-centered hypersphere space. However,
in multi-label scenarios, we observe and theoretically prove that they are
limited to expressing profound correlations. With the exponentially increasing
combination growth among labels, the inclusive (_i.e_., relevant categories)
and exclusive (_i.e_., irrelevant categories) relations cannot get well
established supervised by proxy loss. Hence, proxy-based methods exhibit
conflicts (see Fig. 2) and are unsatisfactory in such scenarios.

To overcome the above weaknesses, we propose Hybrid Proxy-Pair Loss (HyP2
Loss) to embed samples into expressive hyperspace to establish abundant label
correlations with an efficient training complexity. Concretely, we conceive
the first part of HyP2 Loss by setting the learnable proxy for each category
such that the established metric space roughly clusters samples of similar
categories. Note that simply adding the pair loss will introduce overwhelmed
training complexity and is fruitless to performance gains. We creatively
design additional irrelevant pair constraints as the second part to compensate
for the missing multi-label data-to-data correlations, such that enables HyP2
Loss to alienate irrelevant samples to avoid attribute conflicts effectively.
Finally, we design the overall loss function with the learning algorithm that
ensures more efficient training complexity than pair-based methods, since our
predominant part during training is linear correlated to the total training
dataset. The elaborate-designed loss functions and training framework
guarantee that the established metric space contains expressive multi-label
correlations.

To justify the effectiveness and efficiency of our framework, we conduct
comprehensive experiments on four multi-label benchmark datasets, _i.e_.,
Flickr-25k (Huiskes and Lew, 2008), VOC-2007 (Everingham et al., 2010),
VOC-2012 (Everingham et al., 2010), and NUS-WIDE (Chua et al., 2009). Compared
to existing state-of-the-art (Hoe et al., 2021; Zhang et al., 2020; Yuan et
al., 2020; Huang et al., 2018), the proposed method outperforms existing
techniques among different hash bits and backbones quantitatively and
qualitatively with better convergence speed and stability. Additionally, in-
depth ablation studies and visualization results justify the effectiveness of
our mechanism and the designed loss function.

To summarize, our main contributions are three-fold:

  * •

We prove that the hypersphere metric space established by existing proxy-based
methods is limited to expressing the profound inclusive and exclusive
relations in multi-label scenarios. To the best of our knowledge, this is the
first work to theoretically analyze the upper bound of distinguishable
hypersphere number in metric space in multi-label image retrieval task.

  * •

We propose HyP2 Loss, a novel loss function that integrates the efficient time
complexity of proxy-based methods and strong data correlations of pair-based
methods. Particularly, the elaborate-designed multi-label proxy loss,
irrelevant pair loss, and overall learning framework contribute well to
embedding multi-label images into expressive metric space.

  * •

We conduct extensive experiments on four benchmarks to demonstrate the
superiority and robustness of our proposed HyP2 Loss, which is also feasible
to various deep hashing methods and backbones. HyP2 Loss exhibits its
outperforming retrieval performance on both convergence speed and retrieval
accuracy compared to the existing state-of-the-art.

##  2\. Related Work

Many hashing algorithms (Datta et al., 2008; Zhang and Rui, 2013; Gong et al.,
2013; Weiss et al., 2008; Liu et al., 2012; Shen et al., 2015) have been
proposed to obtain compact binary codes, which are seminal solutions to reduce
the storage and calculation overhead in large-scale image retrieval. Deep
hashing (Chen et al., 2021; Wang et al., 2016a; Xia et al., 2014; Cao et al.,
2017) has become the mainstream for the superiority of CNNs (LeCun et al.,
1998; Krizhevsky et al., 2017; Szegedy et al., 2015) in feature extraction,
especially in scenarios where images are associated with more than one
attribute. The common to all is to design the loss functions to establish
powerful metric space and precise hashing positions.

Pair-based Methods. Pair-based methods (Zhao et al., 2015; Lai et al., 2016;
Wu et al., 2017; Huang et al., 2018; Zhang et al., 2020; Ma et al., 2021a) are
predominant in multi-label retrieval (Rodrigues et al., 2020), which focus on
exploring data-to-data relations from the paired samples through metric
learning. In the field of image retrieval, Constrictive loss (Chopra et al.,
2005; Hadsell et al., 2006) innovatively determines the gradient descent
directions by estimating the similarity between feature vector pairs. Based on
it, CNNH (Xia et al., 2014) and DPSH (Li et al., 2016) utilize CNNs to extract
the features of given images. To reveal the local optima risks in pair-wise
loss (Li et al., 2016), Triplet Loss (Schroff et al., 2015; Wang et al.,
2016b) associates the anchor with one positive and one negative sample for the
loss calculation process.

Recently, researchers concentrate on exploring the profound attribute
correlations in challenging multi-label retrieval (Rodrigues et al., 2020).
The seminal work DSRH (Zhao et al., 2015) introduces CNN-based Triplet Loss to
estimate the semantic distance according to the sorted labels. IAH (Lai et
al., 2016) divides hash codes into groups to separately excavate instance-
aware image representations. DMSSPH (Wu et al., 2017) and RCDH (Ma et al.,
2021a) further improve the performance by considering the semantic similarity
by supervision on grouped labels and additional regularization. Pair-based
methods fully excavate the data correlations and exhibit satisfactory
performance. However, the training complexity generally requires square or
cubic complexity related to the entire large-scale images. Hence, such
approaches suffer high computational consumption and converge difficulty,
especially are more serious and ineluctable in multi-label scenarios.

Proxy-based Methods. To address the challenging issues in pair-based methods,
proxy-based methods are proposed to improve model robustness with efficient
training complexity in single-label scenarios. Some methods (Yuan et al.,
2020; Hoe et al., 2021; Fan et al., 2020) attempt to alleviate the training
difficulty by fixing manually-selected or predefined hash centers. Such
predefined centers are regarded as specific proxies for corresponding
categories. Hence, the training complexity is affordable because each sample
only interacts with a few class proxies.

However, the artificially designed proxies ignore the semantic relationship
between intra-class and inter-class. To fill this gap, existing state-of-the-
art (Movshovitz et al., 2017; Aziere and Todorovic, 2019; Kim et al., 2020)
regard the hash centers as trainable parameters. Proxy NCA (Movshovitz et al.,
2017) calculates the distance between each proxy and positive & negative
samples, while Manifold Proxy Loss (Aziere and Todorovic, 2019) improves
performance with the manifold-aware distance to measure the semantic
similarity. Proxy Anchor Loss (Kim et al., 2020) integrates both advantages of
pair-based and proxy-based schemes with Log-SumExp function. It individually
considers the distances between different samples and proxies to tackle the
hard-pair challenges.

Although the proxy-based methods achieve performance better or on par with
pair-based ones with faster convergence speed and promising training overhead
in terms of single-label datasets (Krizhevsky et al., 2009; Russakovsky et
al., 2015), they always fail when come into multi-label scenarios and hence
haven’t been fully investigated before. We further elaborate on the reasons
and propose our novel HyP2 Loss solution further.

##  3\. Methodology

###  3.1. Task Definition

Given a training set
$\mathscr{D}_{M}\coloneqq\\{({\bm{x}}_{i},\bm{y}_{i})\\}_{i=1}^{M}$ composed
of $M$ data points
$\mathcal{X}\coloneqq\\{\bm{x}_{i}\\}_{i=1}^{M}\in\mathds{R}^{D\times M}$ and
corresponding label
$\mathcal{Y}\coloneqq\\{\bm{y}_{i}\\}_{i=1}^{M}\in\\{0,1\\}^{C\times M}$,
where $D$ represents the resolution of images and $C$ denotes the category
numbers, respectively. The image $\bm{x}_{i}$ contains the attribute of class
$y_{j}$ iff ${\bm{y}_{i}}_{(j)}=1$. In multi-label scenarios, each sample
contains at least one attribute, _i.e_.,
$\sum\nolimits_{j=1}^{C}{{\bm{y_{i}}}_{(j)}}\geq 1$. The target for deep
hashing is to learn a feature extractor $\mathcal{F}$ parameterized by
$\Theta$ that encodes each data point $\bm{x}_{i}$ into a compact $K$-bit
feature vector
$\bm{v}_{i}\coloneqq\mathcal{F}_{\Theta}(\bm{x}_{i})\in\mathds{R}^{K}$ in
metric space, and maps into $K$-bit binary hash code
$\bm{b}_{i}\coloneqq\mathcal{H}(\bm{v}_{i})\in\\{-1,1\\}^{K}$ through the
hashing function $\mathcal{H}$ in the Hamming space. Hence, the image-wise
similarity is preserved in the Hamming space. For given query image
$\bm{x}_{q}$, we sort the hash codes for all the samples in the database
according to their Hamming distance, and return the Top-$N$ images as the
query results. The core challenge of this task is to learn a reliable feature
extractor $\mathcal{F}_{\Theta}^{*}$ to cluster images of different categories
with proper and distinguishable hash positions.

\begin{overpic}[trim=0.0pt 0.0pt 0.0pt
0.0pt,clip,width=433.62pt,grid=false]{imgs/overview_v2.png}
\put(2.5,12.5){(a). Pair loss} \put(2.0,0.5){(b). Proxy loss}
\put(30.0,0.5){(c). Illustration of the proposed {{HyP${}^{2}$ Loss}}}
\put(80.0,0.5){(d). Retrieval results}
\par\par\put(57.0,11.3){\tiny{$\scalebox{0.8}{$\mathcal{L}_{proxy}$}$}}
\put(61.0,14.0){\tiny{$\scalebox{0.8}{$\mathcal{L}_{neg\\_pair}$}$}}
\par\put(25.0,4.5){\scriptsize CNN Feature Extractor}
\put(15.0,4.5){\scriptsize mini-batch} \put(16.0,3.5){\scriptsize Input}
\par\put(35.5,3.5){\scriptsize Corresponding } \put(35.5,2.0){\scriptsize
multi-label G.T.} \par\put(39.4,19.0){\scriptsize$K$-bits continuous}
\put(40.8,18.0){\scriptsize feature vector}
\par\par\put(60.0,22.5){\scriptsize$K$-dimensional metric space}
\par\par\put(53.0,15.5){\scriptsize$\bm{p}_{3}$}
\put(67.0,13.0){\scriptsize$\bm{p}_{4}$}
\put(54.0,13.0){\scriptsize$\bm{p}_{2}$}
\put(63.0,17.5){\scriptsize$\bm{p}_{1}$}
\par\put(57.3,17.0){\scriptsize$\bm{v}_{1}$}
\put(61.0,17.3){\scriptsize$\bm{v}_{2}$}
\par\put(61.0,20.5){\scriptsize$\bm{v}_{3}$}
\put(63.5,16.5){\scriptsize$\bm{v}_{4}$} \par\put(77.0,5.0){\scriptsize
Database} \par\put(75.8,15.0){\scriptsize Retrieve from}
\put(76.5,14.0){\scriptsize database} \par\put(78.5,22.5){\scriptsize{Query}}
\put(77.0,17.5){\scriptsize Dog \& Cat} \par\par\put(82.5,22.0){\scriptsize
Dog \& Cat} \put(88.0,22.0){\scriptsize Cow \& Sheep}
\put(93.0,20.5){\scriptsize Dog \& Sheep} \put(84.5,14.0){\scriptsize Dog}
\put(90.0,14.0){\scriptsize Cat} \put(93.5,14.5){\scriptsize{Proxy Loss}}
\par\put(82.5,12.0){\scriptsize Dog \& Cat} \put(89.0,12.0){\scriptsize Dog}
\put(93.0,10.5){\scriptsize Cow \& Sheep} \put(84.5,3.7){\scriptsize Cat}
\put(88.0,3.7){\scriptsize Dog \& Sheep} \put(95.5,4.2){\scriptsize{Ours}}
\par\put(84.0,2.0){\scriptsize{Top-$\bm{N}$ returned}} \par\end{overpic}
Figure 2. Difference and novelty of HyP2 Loss _vs_. previous losses. (a).
Pair-based methods require square or even cubic complexity w.r.t. the whole
dataset. (b). Proxy-based methods are efficient that only consider proxy-to-
data relations but ignore data-to-data relation and exhibits conflicts in
multi-label retrieval. (c). The novel HyP2 Loss extends proxy loss into multi-
label scenarios to construct powerful metric space beyond hypersphere ones.
The Multi-label Proxy Loss $\bm{\mathcal{L}_{proxy}}$ establishes a proper
metric space with training efficiency guaranteed, while the elaborate-designed
irrelevant pair constraint $\bm{\mathcal{L}_{neg\\_pair}}$ alienates
irrelevant pairs to address conflicts between $\bm{(v}_{1},\bm{v}_{2}\bm{)}$.
(d). Given the query, proxy-based methods misclassify the irrelevant samples
into the Top-$\bm{N}$ results. As a comparison, HyP2 Loss achieves more
accurate top returned retrieval results.

###  3.2. Motivation

Upper Bound of Distinguishable Hypersphere Number in Metric Space. Metric
learning serves as the substantial procedure for deep hashing. It focuses on
embedding the 2D images that consist of various attributes into the
$K$-dimensional metric space (_i.e_., through their feature vectors $\bm{v}$),
where similar samples (_i.e_., with closer categories) should get clustered.

For image retrieval, it is challenging to establish precise mapping that
encodes the input images into the ideal metric space, especially in large-
scale datasets (Russakovsky et al., 2015) that should consider training
complexity.

In single-label retrieval (_e.g_., ImageNet (Russakovsky et al., 2015), CIFAR
(Krizhevsky et al., 2009)), the label correlations are restricted among one
positive label with negative others. Hence, proxy-based methods (Movshovitz et
al., 2017; Aziere and Todorovic, 2019; Kim et al., 2020) are effective to
embed samples around the class proxies in the metric space. Ultimately,
samples tend to distribute in a hypersphere centered by predefined or
learnable proxies, where similar proxies are close while heterogeneous others
are well alienated. While in multi-label retrieval, the inclusive and
exclusive relations (_i.e_., the ability of metric space to distinguish its
relevant and irrelevant categories) is exponential w.r.t. category number $C$.

However, the isotropic (_i.e_., perfectly symmetrical) hypersphere has
inherent side-effect in such scenarios. When the labels of one sample larger
than two, the label correlations cannot get fully expressed in the hypersphere
space. Specifically, we have the following Theorem. A.1 to illustrate the
upper bound of distinguishable hypersphere number $\Omega(K,C)$ (or called the
maximum inclusive and exclusive relations) in multi-label scenarios. Please
refer to the supplementary for proof.

###### Theorem 3.1.

For the $K$-dimensional metric space $\mathds{R}^{K}$ with $C$ hypersphere
$\mathds{S}\in\mathds{R}^{K}$. The upper bound of distinguishable hypersphere
number $\Omega(K,C)$ cannot enumerate the ideal
$\Omega^{*}(K,C)=\sum\nolimits_{c=0}^{C}\tbinom{C}{c}=2^{C}$ when $C>K+1$. The
upper bound is limited at:

(1)
$\tilde{\Omega}(K,C)=\mathop{\sup}\nolimits_{\mathds{S}}{{\Omega}(K,C)}=\tbinom{C-1}{K}+\sum\nolimits_{k=0}^{K}\tbinom{C}{k}<2^{C}$

Embedding Position Conflicts in Multi-label Scenarios. Another limitation of
proxy-based methods in multi-label scenarios is that, some irrelevant samples
(_i.e_., without the same categories) are inevitable to be embedded into
nearby positions. The primary reason is that the proxy loss only considers the
proxy-to-data distance but misses the data-to-data constraints, the irrelevant
samples associated with different attributes will be potentially encoded into
the close positions nearby the middle of category proxies.

The proxy loss will enforce samples with multiple attributes embedded into the
middle among these proxies, because such hash position ensures images with
identical multi-label retrieved by query images in priority, second by images
containing partially same attributes. Hence, proxy loss encourages multi-label
samples to converge nearby the middle of proxies to achieve the optimal
solution. Intuitively, as illustrated in Fig. 2(c), suppose the proxy set
$\mathscr{P}_{4}=\\{\bm{p}_{1},\cdots,\bm{p}_{4}\\}$ is well embedded into the
metric space, where the proxy loss between any sample $(\bm{x},\bm{y})$ and
$\mathscr{P}$ has converged. Hence, image $\bm{x}_{1}$ associated with
$y_{1},y_{2}$ (_e.g_., dog & cat) will be embedded into the middle of
$\bm{p}_{1}$ and $\bm{p}_{2}$, while image $\bm{x}_{2}$ with $y_{3},y_{4}$
(_e.g_., cow & sheep) will be embedded into the middle of $\bm{p}_{3}$ and
$\bm{p}_{4}$. However, the missing data-to-data correlations ignore the
attribute conflicts between the irrelevant $\bm{x}_{1}$ and $\bm{x}_{2}$.
Although proxy loss explicitly alienates $\bm{x}_{1}$ and
$\bm{p}_{3},\bm{p}_{4}$, $\bm{x}_{1}$ is not guaranteed away from the middle
of $\bm{p}_{3}$ and $\bm{p}_{4}$, which is exactly the embedding position of
$\bm{x}_{2}$. Hence, the dissimilar samples $\bm{x}_{1}$ and $\bm{x}_{2}$ are
entangled in the metric space. For given query $\bm{x}_{q}$ with attributes
$y_{1},y_{2}$, $\bm{x}_{1}$ may get retrieved first, second by the closest
sample $\bm{x}_{2}$, but ignores some relevant samples $(\bm{x}_{3},y_{1})$ or
$(\bm{x}_{4},\\{y_{1},y_{4}\\})$. The misclassified conflicts among multi-
label datasets become more prominent. See Fig. 1 for some examples, the proxy-
based method wrongly retrieves the results of given multi-label images.

###  3.3. Hybrid Proxy-Pair Loss

Sec. 3.2 reveals the primary reasons that proxy-based methods are
unsatisfactory in multi-label scenarios, _i.e_., simply embedding samples
distributed among a proxy-centered hypersphere cannot comprehensively
introduce the combination among various categories, and the proxy-to-data
supervisions ignore data-to-data attribute conflicts. As a result, some
crucial label correlations may not be well-expressed, especially under large-
scale datasets with limited $K$-bit hash codes.

The above observations motivate us to consider the data-to-data relations that
contribute to a powerful metric space to represent the correlations among
various attributes. To avoid constructing the metric space into an isotropic
hypersphere without loss of training efficiency, we creatively propose Hybrid
Proxy-Pair Loss (HyP2 Loss) for metric learning to extend the proxy loss into
challenging multi-label scenarios, and compensate for the local optimum and
overfitting risks of pair loss in exploring data-to-data relations. The
carefully designed HyP2 Loss depicts a superior metric space to fully express
the profound label correspondences. The overview framework of HyP2 Loss is
illustrated in Fig. 2, and the details of each component are elaborated as
follows.

Multi-label Proxy Loss. Firstly, we set $C$ learnable proxies
$\mathscr{P}_{C}=\\{\bm{p}_{1},\cdots,\bm{p}_{C}\\}$, each
$\bm{p}_{i}\in\mathscr{P}_{C}$ is a compact $K$-bit vector that is exclusive
for each category. For a given feature vector
$\bm{v}_{i}\coloneqq\mathcal{F}_{\Theta}(\bm{x}_{i})$ and corresponding label
$\bm{y}_{i}$, the energy term between any $\bm{v}_{i}$ and $\bm{p}_{j}$ is
$\cos_{+}(\bm{v}_{i},\bm{p}_{j})\coloneqq-\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle=-\frac{|\bm{v}_{i}\cdot\bm{p}_{j}|}{|\bm{v}_{i}|\cdot|\bm{p}_{j}|}$
iff they are a positive pair, _i.e_., ${\bm{y}_{i}}_{(j)}=1$. Otherwise,
$\bm{v}_{i}$ and $\bm{p}_{j}$ are a negative pair. The energy term is defined
as
$\cos_{-}(\bm{v}_{i},\bm{p}_{j})\coloneqq\left(\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle-\zeta\right)_{+}=\max\left(\frac{|\bm{v}_{i}\cdot\bm{p}_{j}|}{|\bm{v}_{i}|\cdot|\bm{p}_{j}|}-\zeta,0\right)$,
where $\zeta=\zeta(C,K)$ is a margin term that follows HHF (Xu et al., 2021).
Then, the first term of HyP2 Loss is designed as Multi-label Proxy Loss
$\mathcal{L}_{proxy}$, which only optimizes the distance between proxies and
samples, as Eq. 2 illustrates.

(2) $\begin{aligned}
\mathcal{L}_{proxy}(\mathscr{D}_{M},\mathscr{P}_{C})&=\frac{{\sum\nolimits_{i=1}^{M}{\sum\nolimits_{j=1}^{C}{\mathds{1}({\bm{y}_{i}}_{(j)}=1){{\cos}_{+}}(\bm{v}_{i},\bm{p}_{j})}}}}{{\sum\nolimits_{i=1}^{M}{\sum\nolimits_{j=1}^{C}{\mathds{1}({\bm{y}_{i}}_{(j)}=1)}}}}\\\
&+\frac{{\sum\nolimits_{i=1}^{M}{\sum\nolimits_{j=1}^{C}{\mathds{1}({\bm{y}_{i}}_{(j)}=0){{\cos}_{-}}({\bm{v}_{i}},{\bm{p}_{j}})}}}}{{\sum\nolimits_{i=1}^{M}{\sum\nolimits_{j=1}^{C}{\mathds{1}({\bm{y}_{i}}_{(j)}=0)}}}}\end{aligned},$

where $\mathds{1}(\cdot)$ is the indicator function that equals to $1$ ($0$)
iff $(\cdot)$ is True (False). The denominator term balances $\cos_{+}(\cdot)$
and $\cos_{-}(\cdot)$, such that avoids the gradient bias introduced by
overmuch negative pairs. The Multi-label Proxy Loss is used for establishing a
primary metric space to ensure the samples are distributed among the cluster
centers (_c.f_. Fig. 4), where the correlated labels are properly clustered
and irrelevant sample-proxy pairs are roughly alienated.

Irrelevant Pair Loss. Secondly, we focus on exploring data-to-data
correlations to explicitly enforce irrelevant samples get alienated. To
achieve this, we define the irrelevant pairs as: $(\bm{v}_{i},\bm{v}_{j})$
associated with label $(\bm{y}_{i},\bm{y}_{j})$ is irrelevant pairs iff
$|\bm{y}_{i}\cdot\bm{y}_{j}|=0$ and $|\bm{y}_{i}|>1,|\bm{y}_{j}|>1$. Note that
the total number of such irrelevant pairs is far fewer than the total $M\times
M$ pairs, the ratio is defined as $\eta$ in Tab. 2. Suppose the subset
$\mathscr{D}_{M^{\prime}}^{\prime}\coloneqq\\{({\bm{x}}_{i},\bm{y}_{i})\\}_{i=1}^{M^{\prime}}\subseteq\mathscr{D}_{M}$
is composed of $M^{\prime}$ samples, where each sample contains more than one
category. Then the second term of HyP2 Loss is Irrelevant Pair Loss
$\mathcal{L}_{neg\\_pair}$, which is defined as Eq. 3.

(3)
$\mathcal{L}_{neg\\_pair}(\mathscr{D}_{M^{\prime}}^{\prime})=\frac{\sum\nolimits_{i=1}^{M^{\prime}}\sum\nolimits_{j=1}^{M^{\prime}}\mathds{1}(|\bm{y}_{i}\cdot\bm{y}_{j}|=0)\cos_{-}(\bm{v}_{i},\bm{v}_{j})}{\sum\nolimits_{i=1}^{M^{\prime}}\sum\nolimits_{j=1}^{M^{\prime}}\mathds{1}(|\bm{y}_{i}\cdot\bm{y}_{j}|=0)},$

where $\cos_{-}(\bm{v}_{i},\bm{v}_{j})$ indicates the pair-wise similarity of
given irrelevant samples. Compared to the entire $M\times M$ computation, the
proposed $\mathcal{L}_{neg\\_pair}(\mathscr{D}_{M^{\prime}}^{\prime})$ only
considers limited pairs to mine data-to-data correlations that alienates
irrelevant samples effectively without loss of efficiency.

Algorithm 1 The training algorithm of the proposed HyP2 Loss for metric
learning.

0: Training dataset

$\mathscr{D}_{M}$

, hash code length $K$, mini-batch $B$.

0: Optimized network

$\mathcal{F}_{\Theta}^{*}$

and proxy set

$\mathscr{P}^{*}_{C}$

.

1: Initialize

$\Theta\leftarrow\Theta^{(0)}$

,

$\mathscr{P}\leftarrow\mathscr{P}^{(0)}$

, Epoch $T\leftarrow 0$;

2: repeat

3: Randomly sample a mini-batch samples

$\mathscr{D}_{B}\coloneqq\\{(\bm{x}_{i},\bm{y}_{i})\\}_{i=1}^{B}$

;

4: Compute feature vector

$\bm{v}_{i}\coloneqq\mathcal{F}_{\Theta}^{(T)}(\bm{x}_{i})$

for each $(\bm{x}_{i},\bm{y}_{i})\in\mathscr{D}_{B}$ by forward propagation;

5: Compute Multi-label Proxy Loss

$\mathcal{L}_{proxy}(\mathscr{D}_{B},\mathscr{P}^{(T)}_{C})$

via Eq. 2;

6: Compute Irrelevant Pair Loss

$\mathcal{L}_{neg\\_pair}(\mathscr{D}_{B^{\prime}}^{\prime})$

via Eq. 3;

7: Compute Total Loss

$\mathcal{L}_{total}(\mathscr{D}_{B},\mathscr{P}^{(T)}_{C})$

via Eq. 4;

8: Compute gradient
$\frac{{\partial\mathcal{L}_{total}}}{{\partial{\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle}}}$
and
$\frac{{\partial\mathcal{L}_{total}}}{{\partial{\cos\langle\bm{v}_{i},\bm{v}_{j}\rangle}}}$
via Eq. 6;

9: Update

$\Theta^{(T+1)}$

and

$\mathscr{P}^{(T+1)}$

by back propagation;

10: $T\leftarrow T+1$;

11: until Convergence

12: Return

$\Theta^{*}\leftarrow\Theta^{(T)}$

,

$\mathscr{P}^{*}\leftarrow\mathscr{P}^{(T)}$

.

Overall Loss & Gradient of HyP2 Loss. Finally, the overall HyP2 Loss is the
weighted-assumption of the above two loss terms to obtain
$\mathcal{L}_{total}$, as Eq. 4 illustrates.

(4)
$\mathcal{L}_{total}(\mathscr{D}_{M},\mathscr{P}_{C})=\mathcal{L}_{proxy}(\mathscr{D}_{M},\mathscr{P}_{C})+\beta\mathcal{L}_{neg\\_pair}(\mathscr{D}_{M^{\prime}}^{\prime})$

where $\beta$ is a hyperparameter to balance the constraints between multi-
label proxy term and irrelevant pair term.

Hence, to optimize the parameterized network $\mathcal{F}_{\Theta}$ and proxy
set $\mathscr{P}_{C}$, the objective function is to minimize
$\mathcal{L}_{total}$ of the given training set and learnable proxy set, as
Eq. 5 illustrates.

(5)
$\Theta^{*},\mathscr{P}^{*}=\mathop{\arg\min}_{\Theta,\mathscr{P}}\mathcal{L}_{total}(\mathscr{D}_{M},\mathscr{P}_{C})$

To achieve this, the gradient of HyP2 Loss in Eq. 4 w.r.t.
$\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle$ and
$\cos\langle\bm{v}_{i},\bm{v}_{j}\rangle$ is given by Eq. 6.

(6)
$\displaystyle\frac{{\partial{\mathcal{L}_{total}}}}{{\partial{\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle}}}$
$\displaystyle=\left\\{\begin{array}[]{ll}-\frac{1}{\sum\nolimits_{i=1}^{M}{\sum\nolimits_{j=1}^{C}{\mathds{1}({\bm{y}_{i}}_{(j)}=1)}}},&{\bm{y}_{i}}_{(j)}=1\\\
\frac{1}{\sum\nolimits_{i=1}^{M}{\sum\nolimits_{j=1}^{C}{\mathds{1}({\bm{y}_{i}}_{(j)}=0)}}},&{\bm{y}_{i}}_{(j)}=0,\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle>\zeta\\\
0,&{\bm{y}_{i}}_{(j)}=0,\cos\langle\bm{v}_{i},\bm{p}_{j}\rangle\leq\zeta\end{array}\right.$
$\displaystyle\frac{{\partial{\mathcal{L}_{total}}}}{{\partial{\cos\langle\bm{v}_{i},\bm{v}_{j}\rangle}}}$
$\displaystyle=\left\\{\begin{array}[]{ll}\frac{\beta}{\sum\nolimits_{i=1}^{M^{\prime}}{\sum\nolimits_{j=1}^{M^{\prime}}{\mathds{1}(|\bm{y}_{i}\cdot\bm{y}_{j}|=0)}}},&|\bm{y}_{i}\cdot\bm{y}_{j}|=0,\cos\langle\bm{v}_{i},\bm{v}_{j}\rangle>\zeta\\\
0,&|\bm{y}_{i}\cdot\bm{y}_{j}|=0,\cos\langle\bm{v}_{i},\bm{v}_{j}\rangle\leq\zeta\end{array}\right.$

Eq. 6 shows that minimizing the HyP2 Loss enforces $\bm{v}_{i}$ and
$\bm{p}_{j}$ to get close if the two share the same attributes, and
distinguishes the irrelevant proxy-to-data/data-to-data pairs simultaneously.
When HyP2 Loss convergences, we thus construct the powerful metric space by
mapping the images from the database into continuous feature vectors, and
binarizing into hash codes in the Hamming space for efficient retrieval.

###  3.4. Overview of Learning Algorithm

Training Algorithm. With the novel HyP2 Loss, we ensure the constructed metric
space is more powerful than existing proxy-based methods (Movshovitz et al.,
2017; Aziere and Todorovic, 2019; Kim et al., 2020) both theoretically and
experimentally, because HyP2 Loss explicitly enforces the established metric
space considers the data-to-data correspondences that tackles the conflicts
effectively. To achieve this, we present the training algorithm in Algo. 1.
During the training process, the standard back-propagation algorithm
(Rumelhart et al., 1986) with mini-batch gradient descent method is used to
optimize the network.

Table 1. Training complexity of HyP  2 _vs_. previous state-of-the-art. Note
that proxy-based methods are unqualified for multi-label metric learning,
while pair-based methods require

$\bm{\mathcal{O}(M^{2})}$

or even

$\bm{\mathcal{O}(M^{3})}$

time complexity. As a comparison, HyP

2

costs more efficient training complexity since the irrelevant pairs are the
minority to the whole dataset.

Type | Method | Time Complexity
---|---|---
Proxy |  Proxy NCA (Movshovitz et al., 2017) | $\mathcal{O}(MC)$
Proxy Anchor (Kim et al., 2020) | $\mathcal{O}(MC)$
OrthoHash (Hoe et al., 2021) | $\mathcal{O}(MC)$
|  SoftTriple (Qian et al., 2019) | $\mathcal{O}(MCk^{2})$
Pair |  Constrastive (Chopra et al., 2005; Hadsell et al., 2006; Bromley et al., 1993) | $\mathcal{O}(M^{2})$
HashNet (Cao et al., 2017) | $\mathcal{O}(M^{2})$
DHN (Zhu et al., 2016) | $\mathcal{O}(M^{2})$
IDHN (Zhang et al., 2020) | $\mathcal{O}(M^{2})$
Triplet (Smart) (Harwood et al., 2017) | $\mathcal{O}(M^{2})$
Triplet (Semi-Hard) (Schroff et al., 2015) | $\mathcal{O}(M^{3}/B^{2})$
$N$-pair (Sohn, 2016) | $\mathcal{O}(M^{3})$
Lifted Structure (Song et al., 2016) | $\mathcal{O}(M^{3})$
Ours |  HyP2 Loss | $\mathcal{O}(MC+\eta M^{2})$

Table 2. Statistics of four benchmarks, where $\bm{\eta}$ indicates the ratio
of irrelevant sample pairs with multiple labels to all sample pairs in the
dataset.

Datasets | # Dataset | $C$ | # Database | # Train | # Query | $\eta$
---|---|---|---|---|---|---
Flickr-25k | 24,581 | 38 | 19,581 | 4,000 | 1,000 | 0.286
NUS-WIDE | 195,834 | 21 | 183,234 | 10,500 | 2,100 | 0.242
VOC-2007 | 9,963 | 20 | 5,011 | 5,011 | 4,952 | 0.062
VOC-2012 | 11,540 | 20 | 5,717 | 5,717 | 5,823 | 0.055

Time Complexity Analysis. The proposed method converges faster and is proven
more efficient and stable than those pair-based methods (Zhao et al., 2015;
Lai et al., 2016; Huang et al., 2018; Ma et al., 2021a; Zhang et al., 2020)
(as we will justify in Fig. 3). Below we analyze the training complexity of
HyP2 Loss. Note that $M$, $C$, $B$, and $k$ denote the training sample number,
category number, mini-batch size, and the proxy number of each category,
respectively. $\eta$ is specifically defined in HyP2 Loss, which indicates the
ratio of irrelevant sample pairs with multiple labels to all $M\times M$ pairs
in the dataset. We omit $k\equiv 1$ in single-proxy methods (Movshovitz et
al., 2017; Kim et al., 2020) and ours for simplicity. $k$ is nontrivial for
managing multiple proxies per class such as SoftTriple Loss (Qian et al.,
2019).

Tab. 1 comprehensively compares the training complexity of HyP2 Loss (ours) to
state-of-the-art pair-based and proxy-based methods. The complexity of HyP2
Loss is $\mathcal{O}(MC+\eta M^{2})$ since it compares each sample with
positive or negative proxies and its irrelevant samples (if exists) in a mini-
batch. More specifically, in Eq. 4, the complexity of the first summation
requires $M_{+}$ ($M_{-}$) times calculation for positive (negative) proxy-to-
data pairs, respectively. Hence the total training complexity is
$\mathcal{O}(M_{+}C+M_{-}C)=\mathcal{O}(MC)$. Then the second term requires
$\eta M^{2}$ times calculation for each irrelevant pair. The first term of
HyP2 Loss is linear correlated to $M$ and $C$, while the second term is
significantly degraded because $\eta$ is much less than $1$ in general.

##  4\. Experiment

Table 3. mAP performance by Hamming Ranking for different hash bits
($\bm{K\in\\{12,24,36,48\\}}$) in Flickr-25k (mAP@$\bm{1,000}$) and NUS-WIDE
(mAP@$\bm{5,000}$) with AlexNet. ∗: reported results with the same experiment
settings from (Zhang et al., 2020). †: our reproduced results through the
publicly available models. Bold font (underlined) values indicate the best
(second best).

Method | Dataset | Flickr-25k | NUS-WIDE
---|---|---|---
Pub. | 12 | 24 | 36 | 48 |  avg. $\Delta$ | 12 | 24 | 36 | 48 |  avg. $\Delta$
DLBHC (Lin et al., 2015)∗ | CVPR”15 | 0.724 | 0.757 | 0.757 | 0.776 | - | 0.570 | 0.616 | 0.621 | 0.635 | -
DQN (Cao et al., 2016)∗ | AAAI”16 | 0.809 | 0.823 | 0.830 | 0.827 | 0.069 | 0.711 | 0.733 | 0.745 | 0.749 | 0.124
DHN (Zhu et al., 2016)† | AAAI”16 | 0.817 | 0.831 | 0.829 | 0.851 | 0.079 | 0.720 | 0.742 | 0.741 | 0.749 | 0.128
HashNet (Cao et al., 2017)∗ | ICCV”17 | 0.791 | 0.826 | 0.841 | 0.848 | 0.073 | 0.643 | 0.694 | 0.737 | 0.750 | 0.095
DMSSPH (Wu et al., 2017)∗ | ICMR”17 | 0.780 | 0.808 | 0.810 | 0.816 | 0.050 | 0.671 | 0.699 | 0.717 | 0.727 | 0.093
IDHN (Zhang et al., 2020)† | TMM”20 | 0.827 | 0.823 | 0.822 | 0.828 | 0.071 | 0.772 | 0.790 | 0.795 | 0.803 | 0.180
Proxy Anchor (Kim et al., 2020)† | CVPR”20 | 0.796 | 0.831 | 0.834 | 0.853 | 0.075 | 0.767 | 0.802 | 0.809 | 0.815 | 0.188
CSQ (Yuan et al., 2020)† | CVPR”20 | 0.795 | 0.819 | 0.849 | 0.857 | 0.077 | 0.692 | 0.754 | 0.757 | 0.769 | 0.132
OrthoHash (Hoe et al., 2021)† | NeurIPS”21 | 0.837 | 0.869 | 0.877 | 0.891 | 0.115 | 0.770 | 0.802 | 0.810 | 0.825 | 0.191
DCILH (Ma et al., 2021b)† | TMM”21 | 0.852 | 0.879 | 0.884 | 0.888 | 0.122 | 0.775 | 0.793 | 0.797 | 0.804 | 0.182
HyP2 Loss (Ours) | - | 0.845 | 0.881 | 0.893 | 0.901 | 0.127 | 0.794 | 0.822 | 0.831 | 0.843 | 0.212

In this section, we describe the datasets used for evaluation, the test
protocols, and the implementation details. To evaluate our method, we fairly
conduct experiments against existing state-of-the-art (Zhang et al., 2020;
Yuan et al., 2020; Hoe et al., 2021; Huang et al., 2018; Kim et al., 2020) and
previous methods (Lin et al., 2015; Cao et al., 2016; Zhu et al., 2016; Cao et
al., 2017; Wu et al., 2017; Lai et al., 2015; Liu et al., 2019; Lai et al.,
2016) on four standard multi-label benchmarks, and justify the superiority of
the proposed method both quantitatively and qualitatively. Finally, we explore
and conduct in-depth analyses of how each component of the proposed framework
contributes to the performance.

###  4.1. Implementation Details

We implement the proposed method in the PyTorch framework (Paszke et al.,
2019) and train on a single NVIDIA RTX 3090 GPU. We comprehensively adopt
AlexNet (Krizhevsky et al., 2017) and GoogLeNet (Szegedy et al., 2015)
pretrained on ImageNet (Russakovsky et al., 2015) as the backbones to justify
the robustness of the proposed method. We fine-tune the pretrained backbones
for all layers up to the FC layer and map the output layer into
$K$-dimensional hash bits. We adopt stochastic gradient descent (SGD) (Bottou,
2010) to optimize the network with momentum $0.9$ and weight decay $5e-4$. The
initial learning rates for optimizing network $\mathcal{F}_{\Theta}$/proxies
$\mathscr{P}$ are $0.01$/$0.001$ in AlexNet and $0.02$/$0.02$ in GoogLeNet,
respectively. The learning rate decreases by $0.5$ every $10$ epochs with
$100$ epochs in total.

###  4.2. Dataset & Evaluation Metrics

Four standard benchmarks Flickr-25k (Huiskes and Lew, 2008), VOC-2007
(Everingham et al., 2010), VOC-2012 (Everingham et al., 2010), and NUS-WIDE
(Chua et al., 2009) are adopted for evaluation. The statistics of the four
datasets are summarized in Tab. 2, and the detailed descriptions are as
follows.

Flickr-25k. The Flickr-25k dataset contains $25,000$ images. We follow (Zhang
et al., 2020; Lai et al., 2015) to remove the noisy images that do not contain
any labels. The remaining $24,851$ images contained $38$ categories in total.
Among them, $4,000$ samples are randomly selected as the training set, $1,000$
samples as the query set and the rest images to construct the database.

VOC-2007 & VOC-2012. VOC-2007 (VOC-2012) contains $9,963$ ($11,540$) images in
total, each image attaches to a label containing several of the $20$
categories. We follow (Huang et al., 2018) to construct the training set and
database of the two datasets for the experiment separately, with $5,011$
($5,717$) samples in total. The officially provided query set with $4,952$
($5,823$) samples is used for evaluation.

NUS-WIDE. The NUS-WIDE dataset contains $269,648$ images, and each image is
assigned to several $81$ categories. We follow (Zhang et al., 2020; Lai et
al., 2015) to select the most frequent $21$ categories and $195,834$ images
containing these attributes. We randomly selected $10,500$ and $2,100$ samples
as the training and query set, respectively, and the rest samples are
constructed as the database.

Table 4. mAP performance by Hamming Ranking for different hash bits
($\bm{K\in\\{16,32,48,64\\}}$) in VOC-2007 (mAP@$\bm{5,011}$) and VOC-2012
(mAP@$\bm{5,717}$) with GoogLeNet. ∗: reported results with the same
experiment settings from (Huang et al., 2018). †: our reproduced results
through the publicly available models. Bold font (underlined) values indicate
the best (second best).

Method | Dataset | VOC-2007 | VOC-2012
---|---|---|---
Pub. | 16 | 32 | 48 | 64 |  avg. $\Delta$ | 16 | 32 | 48 | 64 |  avg. $\Delta$
DHN (Zhu et al., 2016)† | AAAI”16 | 0.735 | 0.743 | 0.737 | 0.728 | - | 0.722 | 0.721 | 0.718 | 0.701 | -
NINH (Lai et al., 2015)∗ | CVPR”15 | 0.746 | 0.816 | 0.840 | 0.851 | 0.077 | 0.731 | 0.788 | 0.809 | 0.822 | 0.072
DSH (Liu et al., 2019)∗ | CVPR”16 | 0.763 | 0.767 | 0.769 | 0.775 | 0.033 | 0.753 | 0.766 | 0.776 | 0.782 | 0.054
IAH (Lai et al., 2016)∗ | TIP”16 | 0.800 | 0.862 | 0.878 | 0.883 | 0.120 | 0.794 | 0.844 | 0.862 | 0.864 | 0.126
OLAH (Huang et al., 2018)∗ | TIP”18 | 0.849 | 0.899 | 0.906 | 0.914 | 0.156 | 0.830 | 0.887 | 0.904 | 0.908 | 0.167
IDHN (Zhang et al., 2020)† | TMM”20 | 0.772 | 0.801 | 0.796 | 0.772 | 0.050 | 0.785 | 0.805 | 0.797 | 0.785 | 0.078
Proxy Anchor (Kim et al., 2020)† | CVPR”20 | 0.752 | 0.802 | 0.836 | 0.841 | 0.072 | 0.722 | 0.795 | 0.804 | 0.823 | 0.071
OrthoHash (Hoe et al., 2021)† | NeurIPS”21 | 0.831 | 0.876 | 0.902 | 0.909 | 0.144 | 0.823 | 0.885 | 0.893 | 0.900 | 0.160
HyP2 Loss (Ours) | - | 0.862 | 0.917 | 0.932 | 0.937 | 0.176 | 0.841 | 0.903 | 0.917 | 0.925 | 0.181

Evaluation Protocol. We follow (Jang et al., 2021; Zhao et al., 2015; Lai et
al., 2015; Xu et al., 2021) to employ four metrics for quantitative
evaluation: 1). mean average precision (mAP@$N$), 2). precision w.r.t. Top-$N$
returned images (Top-$N$ curves), 3). the average $l_{2}$ distance of each
sample to the corresponding cluster centers ($d_{intra}$), and 4). the average
$l_{2}$ distance of each cluster to the closest irrelevant cluster centers
($d_{inter}$). Regarding mAP@$N$ score computation, we select the Top-$N$
images from the retrieval ranked-list results. The returned images and the
query image are considered similar iff they share at least one same label.

###  4.3. Quantitative Comparison

Baselines & Settings. We compare the proposed method with 1). standard
baselines, including HashNet (Cao et al., 2017), DMSSPH (Wu et al., 2017), DQN
(Cao et al., 2016), DLBHC (Lin et al., 2015), DHN (Zhu et al., 2016), NINH
(Lai et al., 2015), DSH (Liu et al., 2019), and IAH (Lai et al., 2016), 2).
state-of-the-art deep hashing methods, including IDHN (Zhang et al., 2020),
Proxy Anchor (Kim et al., 2020), CSQ (Yuan et al., 2020), OrthoHash (Hoe et
al., 2021), OLAH (Huang et al., 2018), and DCILH (Ma et al., 2021b). Note that
OLAH and DCILH are two state-of-the-art deep hashing methods specifically
designed for multi-label image retrieval. Besides, Proxy Anchor is the state-
of-the-art proxy-based method. We verify the robustness of such proxy-based
methods in multi-label scenarios to elaborate on how the proposed method
improves the metric space and retrieval performance effectively.

Specifically, to justify the effectiveness of the proposed method, we compare
methods using AlexNet in Flickr-25k and NUS-WIDE among hash bits
$K\in\\{12,24,36,48\\}$ in Tab. 3, and further compare on another backbone
(_i.e_., GoogLeNet) in VOC-2007 and VOC-2012 among $K\in\\{16,32,48,64\\}$ in
Tab. 4, respectively.

Figure 3. Convergence comparisons in Flickr-25k (left) $\bm{\&}$ NUS-WIDE
(right) (48 hash bits with AlexNet). x-axis: training time (sec.), y-axis:
mAP@

$\bm{1,000}$

(left) $\bm{\&}$

$\bm{5,000}$

(right) performance on the query dataset. HyP

2

Loss achieves a faster convergence speed with a more stable training process.

Results & Analysis. As Tab. 3 and Tab. 4 illustrate, HyP2 Loss outperforms
existing methods over different hash bits in the four benchmarks, which
justifies the robustness and effectiveness of the proposed method. Note that
when the hash bits are small (_e.g_., $12$-bit in Flickr-25k/NUS-WIDE and
$16$-bit in VOC-2007/VOC-2012), the proposed method achieves $10.20\%$
performance gains on average compared to Proxy Anchor (Kim et al., 2020), the
state-of-the-art proxy-based method in image retrieval.

We justify that the metric space established by proxy loss is insufficient to
express the profound label correlations, which achieves unsatisfactory mAP and
misclassified retrieval performance. As a comparison, HyP2 Loss effectively
improves the metric space by additional constraints to explicitly improve the
isotropic hypersphere space, and thus improves the retrieval accuracy
remarkably.

###  4.4. Qualitative Comparison

Convergence Comparison. To demonstrate that the convergence speed of the
proposed method outperforms existing methods, we compare (Zhu et al., 2016;
Zhang et al., 2020; Kim et al., 2020; Hoe et al., 2021) to HyP2 Loss in
Flickr-25k and NUS-WIDE datasets. The visualized results are presented in Fig.
3.

Fig. 3 shows that the proposed method achieves a more stable and faster
convergence speed with higher performance compared to the previous state-of-
the-art. Note that pair-based methods (Zhu et al., 2016; Zhang et al., 2020)
exhibit training disturbance because the loss function is restricted in a
mini-batch and thus lacks generalization, while OrthoHash (Hoe et al., 2021)
confronts overfitting risks. As a comparison, Proxy Anchor (Kim et al., 2020)
and ours show better stability during the whole training process.

(a) DHN (Zhu et al., 2016)

(b) IDHN (Zhang et al., 2020)

(c) Proxy Anchor (Kim et al., 2020)

(d) Pair Loss

\begin{overpic}[trim=0.0pt 0.0pt 0.0pt
0.0pt,clip,width=134.42113pt,grid=false]{imgs/proxy.png}
\put(35.0,22.0){\scriptsize bus} \put(30.0,17.0){\scriptsize\& car}
\put(50.0,38.0){\scriptsize person} \put(68.0,33.0){\scriptsize\& train}
\end{overpic} (e) Proxy Loss

\begin{overpic}[trim=0.0pt 0.0pt 0.0pt
0.0pt,clip,width=134.42113pt,grid=flase]{imgs/HyP.png}
\put(17.0,87.0){\scriptsize bus} \put(16.0,82.0){\scriptsize\& car}
\put(60.0,55.0){\scriptsize person} \put(66.0,50.0){\scriptsize\& train}
\end{overpic} (f) HyP2 Loss (Ours)

Figure 4. Visualized t-SNE comparisons in VOC-2007 dataset with $\bm{48}$ hash
bits. The scatters of the same color indicate the same categories. The red
circles indicate irrelevant samples.

t-SNE Plots. To observe how the proposed method contributes better metric
space, we use t-SNE (Van der Maaten and Hinton, 2008) to map $K$-dimensional
feature vectors into 2D plots. For each sample, we assign different colors
around its neighbourhood to present its attributes. Then, the visualized
comparisons among DHN (Zhu et al., 2016), IDHN (Zhang et al., 2020), Proxy
Anchor (Kim et al., 2020) and pair loss, proxy loss baselines to the proposed
HyP2 Loss in VOC-2007 dataset are illustrated in Fig. 4.

Fig. 4 shows that our method achieves visually better data distribution,
especially in the confusion samples. The red circles in Fig. 4(e) and Fig.
4(f) show how HyP2 Loss solves the conflicts in Proxy Loss. Specifically, the
proxy loss improperly embeds irrelevant samples with multiple labels (bus,
car) and (person, train) into nearby positions, which damages the retrieval
accuracy. As a comparison, HyP2 Loss could solve the irrelevant conflicts and
thereby achieves visually better metric space with superior performance.

Top-$\bm{N}$ curve. To further demonstrate that HyP2 Loss genuinely provides
quality search outcomes, we present the precision for the Top-$N$ retrieved
images in Fig. 5. We can observe that the proposed HyP2 Loss consistently
establishes the state-of-the-art retrieval performance with higher scores over
different hash bits.

Figure 5. Performance of different methods in Flickr-25k (top) and NUS-WIDE
(bottom) datasets. From left to right: Top-$\bm{N}$ curves (x-axis
(Top-$\bm{N}$): $\bm{100\rightarrow 1,000}$, y-axis (Precision):
$\bm{0\rightarrow 1}$) w.r.t. $\bm{12,24,36,48}$ hash bits, respectively. Our
HyP2 Loss outperforms previous methods in different datasets among various
hash bit lengths consistently. Table 5. Ablation study $\bm{\&}$
hyperparameter analysis of HyP

2

Loss. We report mAP@$\bm{1,000(5,011)}$ in Flicker-25k (VOC-2007) to show how
the proposed method improves the performance. $\bm{\beta=1(0.5)}$ is
empirically best for the two datasets.

Dataset | Flickr-25k | VOC-2007
---|---|---
Hash Bits | 12 | 24 | 36 | 48 | 16 | 32 | 48 | 64
Pair Loss | 0.779 | 0.832 | 0.837 | 0.847 | 0.732 | 0.766 | 0.777 | 0.781
Proxy Loss | 0.787 | 0.834 | 0.856 | 0.871 | 0.767 | 0.820 | 0.873 | 0.887
Proxy + Pair Loss | 0.817 | 0.851 | 0.857 | 0.870 | 0.818 | 0.843 | 0.875 | 0.881
HyP2 Loss $(\beta=0.50)$ | 0.838 | 0.876 | 0.893 | 0.896 | 0.862 | 0.917 | 0.932 | 0.937
HyP2 Loss $(\beta=0.75)$ | 0.842 | 0.877 | 0.891 | 0.896 | 0.859 | 0.915 | 0.930 | 0.935
HyP2 Loss $(\beta=1.00)$ | 0.845 | 0.881 | 0.893 | 0.901 | 0.857 | 0.912 | 0.926 | 0.934
HyP2 Loss $(\beta=1.25)$ | 0.841 | 0.877 | 0.891 | 0.897 | 0.843 | 0.909 | 0.927 | 0.935

###  4.5. Ablation Study

To justify how each component of HyP2 Loss contributes to a more powerful
metric space, we conduct in-depth ablation studies on investigating the
effectiveness of Multi-label Proxy Loss, Irrelevant Pair Loss, and the
combination of them with different $\beta$, the results of mAP, $d_{intra}$
and $d_{inter}$ are shown in Tab. 5 and Tab. 6.

As Tab. 5 and Tab. 6 illustrate, either pair loss or proxy loss fails to
achieve satisfactory performance due to its inherent limitations as we
analyzed before, and a simple combination of the two terms with $\beta$ is
invalid but confronts overwhelmed training overhead. Specifically, since
smaller $d_{intra}$ indicates better cluster performance, while larger
$d_{inter}$ indicates better disentangle ability on confusion samples. The
pair loss constructs a sparse metric space that fails to cluster samples
tightly, while the proxy loss fails to distinguish the confusing samples that
introduces misclassified results. As a comparison, the proposed HyP2 Loss not
only achieves remarkable performance gains, but also ensures better
$d_{intra}$ and $d_{inter}$ that establishes superior metric space compared to
others, which demonstrates its robustness and retrieval accuracy.

Table 6. Ablation study of HyP2 Loss. We report $\bm{d_{intra}}$ and
$\bm{d_{inter}}$ in Flickr-25k to show HyP2 Loss establishes a better metric
space that ensures the two metrics simultaneously.

Metric |  $d_{intra}$ $\downarrow$ |  $d_{inter}$ $\uparrow$
---|---|---
Hash Bits | 12 | 24 | 36 | 48 | 12 | 24 | 36 | 48
Pair Loss | 3.043 | 3.453 | 4.320 | 4.749 | 2.264 | 2.868 | 3.480 | 4.152
Proxy Loss | 2.094 | 2.695 | 3.174 | 3.763 | 2.564 | 3.322 | 4.144 | 4.890
Proxy + Pair Loss | 2.387 | 2.792 | 3.351 | 3.734 | 2.402 | 2.995 | 3.524 | 3.837
HyP2 Loss | 1.859 | 2.395 | 2.877 | 3.237 | 3.633 | 4.331 | 4.560 | 5.202

Finally, since the hyperparameter $\beta$ controls the contribution of each
component in HyP2 Loss, we investigate the influence of $\beta$ with different
values and find that $\beta$ should be adjusted in specific datasets but is
stable in different hash bits, while HyP2 Loss keeps relatively high
performance in a wide range $\beta\in[0.50,1.25]$. In Tab. 5, our empirical
study shows that HyP2 Loss performs best in Flickr-25k (VOC-2007) when
$\beta=1.00$ ($0.50$), respectively.

##  5\. Conclusion

In this paper, we focus on theoretically analyzing the primary reasons that
proxy-based methods are disqualified for multi-label retrieval, and propose
the novel HyP2 Loss to preserve the efficient training complexity of proxy
loss with the irrelevant constraint term, which compensates for the limitation
of the hypersphere metric space. We conduct extensive experiments to justify
the superiority of the proposed method in four standard benchmarks with
different backbones and hash bits. Both quantitative and qualitative results
demonstrate that the proposed HyP2 Loss enables fast, reliable and robust
convergence speed, and constructs a powerful metric space to improve the
retrieval performance significantly.

Acknowledgment. This work was supported by SZSTC Grant No.
JCYJ20190809172201639 and WDZC20200820200655001, Shenzhen Key Laboratory
ZDSYS20210623092001004.

## References

  * (1)
  * Aziere and Todorovic (2019) Nicolas Aziere and Sinisa Todorovic. 2019.  Ensemble Deep Manifold Similarity Learning Using Hard Proxies. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR_. Computer Vision Foundation / IEEE, 7299–7307.
  * Bottou (2010) Léon Bottou. 2010\.  Large-Scale Machine Learning with Stochastic Gradient Descent. In _19th International Conference on Computational Statistics, COMPSTAT 2010, Paris, France, August 22-27, 2010 - Keynote, Invited and Contributed Papers_. Physica-Verlag, 177–186.
  * Bromley et al. (1993) Jane Bromley, Isabelle Guyon, Yann LeCun, Eduard Säckinger, and Roopak Shah. 1993\.  Signature Verification Using a Siamese Time Delay Neural Network. In _Advances in Neural Information Processing Systems 6, [7th NIPS Conference, Denver, Colorado, USA, 1993]_. Morgan Kaufmann, 737–744.
  * Cao et al. (2016) Yue Cao, Mingsheng Long, Jianmin Wang, Han Zhu, and Qingfu Wen. 2016.  Deep Quantization Network for Efficient Image Retrieval. In _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence_ , Dale Schuurmans and Michael P. Wellman (Eds.). AAAI Press, 3457–3463.
  * Cao et al. (2017) Zhangjie Cao, Mingsheng Long, Jianmin Wang, and Philip S. Yu. 2017\.  HashNet: Deep Learning to Hash by Continuation. In _IEEE International Conference on Computer Vision, ICCV_. IEEE Computer Society, 5609–5618.
  * Chen et al. (2021) Wei Chen, Yu Liu, Weiping Wang, Erwin M. Bakker, Theodoros Georgiou, Paul W. Fieguth, Li Liu, and Michael S. Lew. 2021\.  Deep Image Retrieval: A Survey.  _arXiv preprint:abs/2101.11282_ (2021).
  * Chopra et al. (2005) Sumit Chopra, Raia Hadsell, and Yann LeCun. 2005\.  Learning a Similarity Metric Discriminatively, with Application to Face Verification. In _2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_. IEEE Computer Society, 539–546.
  * Chua et al. (2009) Tat-Seng Chua, Jinhui Tang, Richang Hong, Haojie Li, Zhiping Luo, and Yantao Zheng. 2009\.  NUS-WIDE: a real-world web image database from National University of Singapore. In _Proceedings of the 8th ACM International Conference on Image and Video Retrieval, CIVR_ , Stéphane Marchand-Maillet and Yiannis Kompatsiaris (Eds.). ACM.
  * Cui et al. (2021) Hui Cui, Lei Zhu, Jingjing Li, Zhiyong Cheng, and Zheng Zhang. 2021.  Two-pronged Strategy: Lightweight Augmented Graph Network Hashing for Scalable Image Retrieval. In _MM ’21: ACM Multimedia Conference_ , Heng Tao Shen, Yueting Zhuang, John R. Smith, Yang Yang, Pablo Cesar, Florian Metze, and Balakrishnan Prabhakaran (Eds.). ACM, 1432–1440.
  * Datta et al. (2008) Ritendra Datta, Dhiraj Joshi, Jia Li, and James Ze Wang. 2008\.  Image retrieval: Ideas, influences, and trends of the new age.  _ACM Comput. Surv._ 40, 2 (2008), 5:1–5:60.
  * Everingham et al. (2010) Mark Everingham, Luc Van Gool, Christopher K. I. Williams, John M. Winn, and Andrew Zisserman. 2010\.  The Pascal Visual Object Classes (VOC) Challenge.  _Int. J. Comput. Vis._ 88, 2 (2010), 303–338.
  * Fan et al. (2020) Lixin Fan, KamWoh Ng, Ce Ju, Tianyu Zhang, and Chee Seng Chan. 2020.  Deep Polarized Network for Supervised Learning of Accurate Binary Hashing Codes. In _Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020_ , Christian Bessiere (Ed.). ijcai.org, 825–831.
  * Feng et al. (2020) Fangxiang Feng, Tianrui Niu, Ruifan Li, Xiaojie Wang, and Huixing Jiang. 2020.  Learning Visual Features from Product Title for Image Retrieval. In _MM ’20: The 28th ACM International Conference on Multimedia_ , Chang Wen Chen, Rita Cucchiara, Xian-Sheng Hua, Guo-Jun Qi, Elisa Ricci, Zhengyou Zhang, and Roger Zimmermann (Eds.). ACM, 4723–4727.
  * Gong et al. (2013) Yunchao Gong, Svetlana Lazebnik, Albert Gordo, and Florent Perronnin. 2013.  Iterative Quantization: A Procrustean Approach to Learning Binary Codes for Large-Scale Image Retrieval.  _IEEE Trans. Pattern Anal. Mach. Intell._ 35, 12 (2013), 2916–2929.
  * Hadsell et al. (2006) Raia Hadsell, Sumit Chopra, and Yann LeCun. 2006\.  Dimensionality Reduction by Learning an Invariant Mapping. In _2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition_. IEEE Computer Society, 1735–1742.
  * Harwood et al. (2017) Ben Harwood, Vijay Kumar B. G, Gustavo Carneiro, Ian D. Reid, and Tom Drummond. 2017\.  Smart Mining for Deep Metric Learning. In _IEEE International Conference on Computer Vision, ICCV 2017, Venice, Italy, October 22-29, 2017_. IEEE Computer Society, 2840–2848.
  * Hoe et al. (2021) Jiun Tian Hoe, KamWoh Ng, Tianyu Zhang, Chee Seng Chan, Yi-Zhe Song, and Tao Xiang. 2021\.  One Loss for All: Deep Hashing with a Single Cosine Similarity based Learning Objective.  _CoRR_ abs/2109.14449 (2021).
  * Huang et al. (2018) Chang-Qin Huang, Shang-Ming Yang, Yan Pan, and Hanjiang Lai. 2018.  Object-Location-Aware Hashing for Multi-Label Image Retrieval via Automatic Mask Learning.  _IEEE Trans. Image Process._ 27, 9 (2018), 4490–4502.
  * Huiskes and Lew (2008) Mark J. Huiskes and Michael S. Lew. 2008.  The MIR flickr retrieval evaluation. In _Proceedings of the 1st ACM SIGMM International Conference on Multimedia Information Retrieval, MIR_ , Michael S. Lew, Alberto Del Bimbo, and Erwin M. Bakker (Eds.). ACM, 39–43.
  * Jang et al. (2021) Young Kyun Jang, Geonmo Gu, ByungSoo Ko, and Nam Ik Cho. 2021\.  Self-Distilled Hashing for Deep Image Retrieval.  _CoRR_ abs/2112.08816 (2021).
  * Kim et al. (2020) Sungyeon Kim, Dongwon Kim, Minsu Cho, and Suha Kwak. 2020\.  Proxy Anchor Loss for Deep Metric Learning. In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE, 3235–3244.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al. 2009\.  Learning multiple layers of features from tiny images.  (2009).
  * Krizhevsky et al. (2017) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton. 2017\.  ImageNet classification with deep convolutional neural networks.  _Commun. ACM_ 60, 6 (2017), 84–90.
  * Lai et al. (2015) Hanjiang Lai, Yan Pan, Ye Liu, and Shuicheng Yan. 2015\.  Simultaneous feature learning and hash coding with deep neural networks. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE Computer Society, 3270–3278.
  * Lai et al. (2016) Hanjiang Lai, Pan Yan, Xiangbo Shu, Yunchao Wei, and Shuicheng Yan. 2016.  Instance-Aware Hashing for Multi-Label Image Retrieval.  _IEEE Trans. Image Process._ 25, 6 (2016), 2469–2479.
  * LeCun et al. (1998) Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. 1998.  Gradient-based learning applied to document recognition.  _Proc. IEEE_ 86, 11 (1998), 2278–2324.
  * Li et al. (2016) Wu-Jun Li, Sheng Wang, and Wang-Cheng Kang. 2016.  Feature Learning Based Deep Supervised Hashing with Pairwise Labels. In _Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, IJCAI_ , Subbarao Kambhampati (Ed.). IJCAI/AAAI Press, 1711–1717.
  * Li et al. (2021) Ying Li, Hongwei Zhou, Yeyu Yin, and Jiaquan Gao. 2021\.  Multi-label Pattern Image Retrieval via Attention Mechanism Driven Graph Convolutional Network. In _MM ’21: ACM Multimedia Conference_ , Heng Tao Shen, Yueting Zhuang, John R. Smith, Yang Yang, Pablo Cesar, Florian Metze, and Balakrishnan Prabhakaran (Eds.). ACM, 300–308.
  * Lin et al. (2015) Kevin Lin, Huei-Fang Yang, Jen-Hao Hsiao, and Chu-Song Chen. 2015.  Deep learning of binary hash codes for fast image retrieval. In _2015 IEEE Conference on Computer Vision and Pattern Recognition Workshops, CVPR Workshops_. IEEE Computer Society, 27–35.
  * Liu et al. (2019) Haomiao Liu, Ruiping Wang, Shiguang Shan, and Xilin Chen. 2019\.  Deep Supervised Hashing for Fast Image Retrieval.  _Int. J. Comput. Vis._ 127, 9 (2019), 1217–1234.
  * Liu et al. (2012) Wei Liu, Jun Wang, Rongrong Ji, Yu-Gang Jiang, and Shih-Fu Chang. 2012.  Supervised hashing with kernels. In _2012 IEEE Conference on Computer Vision and Pattern Recognition_. IEEE Computer Society, 2074–2081.
  * Ma et al. (2021a) Cheng Ma, Jiwen Lu, and Jie Zhou. 2021a.  Rank-Consistency Deep Hashing for Scalable Multi-Label Image Search.  _IEEE Trans. Multim._ 23 (2021), 3943–3956.
  * Ma et al. (2021b) Cheng Ma, Jiwen Lu, and Jie Zhou. 2021b.  Rank-Consistency Deep Hashing for Scalable Multi-Label Image Search.  _IEEE Trans. Multim._ 23 (2021), 3943–3956.
  * Movshovitz et al. (2017) Yair Movshovitz, Alexander Toshev, Thomas K. Leung, Sergey Ioffe, and Saurabh Singh. 2017.  No Fuss Distance Metric Learning Using Proxies. In _IEEE International Conference on Computer Vision, ICCV_. IEEE Computer Society, 360–368.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. 2019.  PyTorch: An Imperative Style, High-Performance Deep Learning Library. In _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS_. 8024–8035.
  * Qian et al. (2019) Qi Qian, Lei Shang, Baigui Sun, Juhua Hu, Tacoma Tacoma, Hao Li, and Rong Jin. 2019.  SoftTriple Loss: Deep Metric Learning Without Triplet Sampling. In _2019 IEEE/CVF International Conference on Computer Vision, ICCV 2019_. IEEE, 6449–6457.
  * Rodrigues et al. (2020) Josiane Rodrigues, Marco Cristo, and Juan G Colonna. 2020\.  Deep hashing for multi-label image retrieval: a survey.  _Artificial Intelligence Review_ 53, 7 (2020), 5261–5307.
  * Rumelhart et al. (1986) David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. 1986.  Learning representations by back-propagating errors.  _nature_ 323, 6088 (1986), 533–536.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael S. Bernstein, Alexander C. Berg, and Fei-Fei Li. 2015\.  ImageNet Large Scale Visual Recognition Challenge.  _Int. J. Comput. Vis._ 115, 3 (2015), 211–252.
  * Schroff et al. (2015) Florian Schroff, Dmitry Kalenichenko, and James Philbin. 2015\.  FaceNet: A unified embedding for face recognition and clustering. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE Computer Society, 815–823.
  * Shen et al. (2015) Fumin Shen, Chunhua Shen, Wei Liu, and Heng Tao Shen. 2015\.  Supervised Discrete Hashing. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE Computer Society, 37–45.
  * Sohn (2016) Kihyuk Sohn. 2016\.  Improved Deep Metric Learning with Multi-class N-pair Loss Objective. In _Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems_. 1849–1857.
  * Song et al. (2016) Hyun Oh Song, Yu Xiang, Stefanie Jegelka, and Silvio Savarese. 2016\.  Deep Metric Learning via Lifted Structured Feature Embedding. In _2016 IEEE Conference on Computer Vision and Pattern Recognition_. IEEE Computer Society, 4004–4012.
  * Szegedy et al. (2015) Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott E. Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich. 2015.  Going deeper with convolutions. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE Computer Society, 1–9.
  * Tu et al. (2021) Rong-Cheng Tu, Xian-Ling Mao, Cihang Kong, Zihang Shao, Ze-Lin Li, Wei Wei, and Heyan Huang. 2021\.  Weighted Gaussian Loss based Hamming Hashing. In _MM ’21: ACM Multimedia Conference_ , Heng Tao Shen, Yueting Zhuang, John R. Smith, Yang Yang, Pablo Cesar, Florian Metze, and Balakrishnan Prabhakaran (Eds.). ACM, 3409–3417.
  * Van der Maaten and Hinton (2008) Laurens Van der Maaten and Geoffrey Hinton. 2008.  Visualizing data using t-SNE.  _Journal of machine learning research_ 9, 11 (2008).
  * Wang et al. (2016a) Jun Wang, Wei Liu, Sanjiv Kumar, and Shih-Fu Chang. 2016a.  Learning to Hash for Indexing Big Data - A Survey.  _Proc. IEEE_ 104, 1 (2016), 34–57.
  * Wang et al. (2018) Jingdong Wang, Ting Zhang, Jingkuan Song, Nicu Sebe, and Heng Tao Shen. 2018.  A Survey on Learning to Hash.  _IEEE Trans. Pattern Anal. Mach. Intell._ 40, 4 (2018), 769–790.
  * Wang et al. (2016b) Xiaofang Wang, Yi Shi, and Kris M. Kitani. 2016b.  Deep Supervised Hashing with Triplet Labels. In _Computer Vision - ACCV 2016 - 13th Asian Conference on Computer Vision_ _(Lecture Notes in Computer Science, Vol. 10111)_ , Shang-Hong Lai, Vincent Lepetit, Ko Nishino, and Yoichi Sato (Eds.). Springer, 70–84.
  * Weiss et al. (2008) Yair Weiss, Antonio Torralba, and Robert Fergus. 2008\.  Spectral Hashing. In _Advances in Neural Information Processing Systems 21, Proceedings of the Twenty-Second Annual Conference on Neural Information Processing Systems_ , Daphne Koller, Dale Schuurmans, Yoshua Bengio, and Léon Bottou (Eds.). Curran Associates, Inc., 1753–1760.
  * Wu et al. (2017) Dayan Wu, Zheng Lin, Bo Li, Mingzhen Ye, and Weiping Wang. 2017.  Deep Supervised Hashing for Multi-Label and Large-Scale Image Retrieval. In _Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval, ICMR_ , Bogdan Ionescu, Nicu Sebe, Jiashi Feng, Martha A. Larson, Rainer Lienhart, and Cees Snoek (Eds.). ACM, 150–158.
  * Xia et al. (2021) Haifeng Xia, Taotao Jing, Chen Chen, and Zhengming Ding. 2021\.  Semi-supervised Domain Adaptive Retrieval via Discriminative Hashing Learning. In _MM ’21: ACM Multimedia Conference_ , Heng Tao Shen, Yueting Zhuang, John R. Smith, Yang Yang, Pablo Cesar, Florian Metze, and Balakrishnan Prabhakaran (Eds.). ACM, 3853–3861.
  * Xia et al. (2014) Rongkai Xia, Yan Pan, Hanjiang Lai, Cong Liu, and Shuicheng Yan. 2014.  Supervised Hashing for Image Retrieval via Image Representation Learning. In _Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence_ , Carla E. Brodley and Peter Stone (Eds.). AAAI Press, 2156–2162.
  * Xu et al. (2021) Chengyin Xu, Zhengzhuo Xu, Zenghao Chai, Hongjia Li, Qiruyi Zuo, Lingyu Yang, and Chun Yuan. 2021.  HHF: Hashing-guided Hinge Function for Deep Hashing Retrieval.  _CoRR_ abs/2112.02225 (2021).
  * Yuan et al. (2020) Li Yuan, Tao Wang, Xiaopeng Zhang, Francis E. H. Tay, Zequn Jie, Wei Liu, and Jiashi Feng. 2020.  Central Similarity Quantization for Efficient Image and Video Retrieval. In _2020 IEEE/CVF Conference on Computer Vision and Pattern Recognition,CVPR_. Computer Vision Foundation / IEEE, 3080–3089.
  * Zhang and Rui (2013) Lei Zhang and Yong Rui. 2013.  Image search - from thousands to billions in 20 years.  _ACM Trans. Multim. Comput. Commun. Appl._ 9, 1s (2013), 36:1–36:20.
  * Zhang et al. (2020) Zheng Zhang, Qin Zou, Yuewei Lin, Long Chen, and Song Wang. 2020.  Improved Deep Hashing With Soft Pairwise Similarity for Multi-Label Image Retrieval.  _IEEE Trans. Multim._ 22, 2 (2020), 540–553.
  * Zhao et al. (2015) Fang Zhao, Yongzhen Huang, Liang Wang, and Tieniu Tan. 2015\.  Deep semantic ranking based hashing for multi-label image retrieval. In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR_. IEEE Computer Society, 1556–1564.
  * Zhu et al. (2016) Han Zhu, Mingsheng Long, Jianmin Wang, and Yue Cao. 2016\.  Deep Hashing Network for Efficient Similarity Retrieval. In _Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence_ , Dale Schuurmans and Michael P. Wellman (Eds.). AAAI Press, 2415–2421.

##  Appendix A Appendix

###  A.1. Missing Proof

###### Theorem A.1.

For the $K$-dimensional metric space $\mathds{R}^{K}$ with $C$ hypersphere
$\mathds{S}\in\mathds{R}^{K}$. The upper bound of distinguishable hypersphere
number $\Omega(K,C)$ cannot enumerate the ideal
$\Omega^{*}(K,C)=\sum\nolimits_{c=0}^{C}\tbinom{C}{c}=2^{C}$ when $C>K+1$. The
upper bound is limited at:

(7)
$\tilde{\Omega}(K,C)=\mathop{\sup}\nolimits_{\mathds{S}}{{\Omega}(K,C)}=\tbinom{C-1}{K}+\sum\nolimits_{k=0}^{K}\tbinom{C}{k}<2^{C}$

###### Proof.

To begin, we first deduce the optimal distinguishable hyperspace number
$\Omega^{*}(K,C)$ in the $K$-dimensional hyperspace with $C$ categories. Note
that each hyperspace represents one category’s cluster center. Hence, the
ideal distinguishable number of any $c\in\\{0,\cdots,C\\}$ hyperspheres is the
combination of them that is denoted as $n(K,c)$.

(8) $n(K,c)=\tbinom{C}{c}$

Hence, according to the binomial theorem, for $C$ hypersphere space, the
optimal distinguishable hyperspace number is the summation of each
$c\in\\{0,\cdots,C\\}$, as Eq. 9 illustrates.

(9) $\Omega^{*}(K,C)=\sum\nolimits_{c=0}^{C}\tbinom{C}{c}=2^{C}$

Then, note that the ideal distinguishable hyperspace number can only get
achieved when the hyperspace is unconstrained (_i.e_., it can have any
intersections to each other). When it comes to $K$-dimensional isotropic
hypersphere, we raise Lemma. A.2 to further demonstrate the upper bound in the
$C$ hypersphere metric space.

###### Lemma A.2.

When $K\geq 2$, two $K$-dimensional hyperspheres will intersect at one
$(K-1)$-dimensional hypersphere at maximum. Specifically, two 2D circles will
intersect at one $1$-dimensional hypersphere at maximum. The $1$-dimensional
hypersphere is a pair of two points, which are the boundary of a line segment.

We denote the $K$-dimensional hypersphere with the number of $C$ has the
maximum distinguishable regions as $\Omega(K,C)$. Then, the $K$-dimensional
hypersphere with the number of $C-1$ has the maximum distinguishable regions
$\Omega(K,C-1)$. When we add the $C$-th hypersphere into the existing
$K$-dimensional hyperspheres with the number of $C-1$, according to Lemma.
A.2, the $C$-th hypersphere will intersect with each hypersphere in the
hyperspace at one $(K-1)$-dimensional hypersphere at maximum, _i.e_.,
$(K-1)$-dimensional hyperspheres with the number of $C-1$ at maximum are added
into the $K$-dimensional hyperspace. These $(K-1)$-dimensional hyperspheres
thereby generate $(K-1)$-dimensional hypersurfaces with the number of
$\Omega(K-1,C-1)$ at maximum correspondingly, and each of these new
$(K-1)$-dimensional hypersurfaces bisects the $K$-dimensional space into two
parts. So we have the following recurrence relation:

(10) $\Omega(K,C)=\Omega(K,C-1)+\Omega(K-1,C-1)$

Note that one $K$-dimensional hypersphere can only separate hyperspace into
two regions, _i.e_., the inside and outside of the hypersphere, respectively.
Hence, we have the initial condition that for every $K\geq 2$ and $C\equiv 1$:

(11) $\Omega(K,1)\equiv 2$

Without loss of generalization, we first consider the simplest particular case
when $K=2$. Then, the $K$-dimensional hypersphere is degraded into a 2D circle
situation.

Suppose there are $C-1$ circles in the 2D space, when we have an additional
one circle in the space, such that each $C-1$ circle should intersect with the
additional one circle to achieve the maximum distinguishable hypersphere
number.

Then, according to Lemma. A.2, the circles will at most intersect with the
additional circle with $(C-1)$ intersected 1D point pairs. Hence, the
$2\times(C-1)$ points will introduce $2\times(C-1)$ lines that segment the
original regions into bisects. As a result, the additional one circle will
introduce additional $2\times(C-1)$ regions. We can obtain that:

(12) $\displaystyle\Omega(2,C)$ $\displaystyle=\Omega(2,C-1)+2\times(C-1)$
$\displaystyle=\Omega(2,C-2)+2\times(C-1)+2\times(C-2)$ $\displaystyle=\cdots$
$\displaystyle=\Omega(2,1)+2\times(C-1+C-2+\cdots+1)$

According to Eq. 11, we have $\Omega(2,1)=2$, _i.e_., one 2D circle can
represent two distinguishable regions at maximum, then:

(13) $\begin{aligned} \Omega(2,C)&=2+2\times(C-1+C-2+\cdots+1)\\\
&=2+C\times(C-1)\\\ &=C^{2}-C+2\\\
&=\frac{(C-1)(C-2)}{2}+\left(1+C+\frac{C(C-1)}{2}\right)\\\
&=\tbinom{C-1}{2}+\sum\nolimits_{k=0}^{2}\tbinom{C}{k}\end{aligned},$

which satisfies the proposition when $K=2$.

Then, we generalize into the $K$-dimensional situation and will prove Theorem.
A.1 by mathematical induction below.

• a). Considering the initial situation that for any $K\geq 2,K\in N_{+}$ and
$C=1$. As Eq. 11 illustrates, we have: (14)
$\Omega(K,C)=\Omega(K,1)=2=\tbinom{0}{K}+\sum\nolimits_{k=0}^{K}\tbinom{1}{k},$
which satisfies the proposition when $C=1$. $\triangleleft$ • b). For any
$K\geq 2,K\in N_{+}$ and a specific $C\geq 1,C\in N_{+}$, we assume the upper
bound of distinguishable hypersphere number $\Omega(K,C)$ satisfies: (15)
$\Omega(K,C)=\tbinom{C-1}{K}+\sum\nolimits_{k=0}^{K}\tbinom{C}{k},$
$\triangleleft$ • c). Then, considering the situation of $\Omega(K,C+1)$. When
$K=2$, as Eq. 13 illustrates, $\Omega(2,C+1)$ satisfies the proposition. When
$K>2$, according to Eq. 10, we have: (16)
$\displaystyle\Omega(K,C+1)=\Omega(K,C)+\Omega(K-1,C)$
$\displaystyle=\tbinom{C-1}{K}+\sum\nolimits_{k=0}^{K}\tbinom{C}{k}+\tbinom{C-1}{K-1}+\sum\nolimits_{k=0}^{K-1}\tbinom{C}{k}$
$\displaystyle=\tbinom{C-1}{K}+\tbinom{C-1}{K-1}+\tbinom{C}{0}+\sum\nolimits_{k=1}^{K}\tbinom{C}{k}+\sum\nolimits_{k=0}^{K-1}\tbinom{C}{k}$
$\displaystyle=\left(\tbinom{C-1}{K}+\tbinom{C-1}{K-1}\right)+\tbinom{C}{0}+\left(\tbinom{C}{0}+\tbinom{C}{1}\right)+\cdots+\left(\tbinom{C}{K-1}+\tbinom{C}{K}\right)$

Note that $\tbinom{m}{n}=\tbinom{m-1}{n}+\tbinom{m-1}{n-1}$, then we have:
(17) $\begin{aligned}
\Omega(K,C+1)&=\tbinom{C}{K}+\tbinom{C}{0}+\tbinom{C+1}{1}+\tbinom{C+1}{2}+\cdots+\tbinom{C+1}{K}\\\
&=\tbinom{C}{K}+\sum\nolimits_{k=0}^{K}\tbinom{C+1}{k}\end{aligned},$ which
satisfies the proposition when $C=C+1$. $\triangleleft$

Finally, according to mathematical induction, for any $K\geq 2,C\geq 1,K,C\in
N_{+}$, the upper bound of distinguishable hypersphere number in
$K$-dimensional metric space is obtained that:

(18)
$\displaystyle\tilde{\Omega}(K,C)=\mathop{\sup}\nolimits_{\mathds{S}}{{\Omega}(K,C)}=\tbinom{C-1}{K}+\sum\nolimits_{k=0}^{K}\tbinom{C}{k}$

When C = K + 1, we can see that the ideal distinguishable hyperspace number
${\Omega}^{*}(K,C)$ is equal to the upper bound $\tilde{\Omega}(K,C)$ because
the hash bit length is large enough to enumerate all possible situations, as
Eq. 19 illustrates.

(19) $\displaystyle\tilde{\Omega}(K,C)$
$\displaystyle=\tbinom{K+1-1}{K}+\sum\nolimits_{k=0}^{K}\tbinom{K+1}{k}$
$\displaystyle=\tbinom{K}{K}+\tbinom{K+1}{0}+\cdots+\tbinom{K+1}{K}$
$\displaystyle=\tbinom{K+1}{0}+\cdots+\tbinom{K+1}{K}+\tbinom{K+1}{K+1}$
$\displaystyle=\sum\nolimits_{k=0}^{K+1}\tbinom{K+1}{k}=2^{K+1}$
$\displaystyle=2^{C}={\Omega}^{*}(K,C)$

Then, we will prove that when $C\textgreater K+1$,
$\tilde{\Omega}(K,C)\textless{\Omega}^{*}(K,C)$ by mathematical induction
below.

• a). Considering the initial situation that for any $K\geq 2,K\in N_{+}$,
when $C=K+2$, according to Eq. 10, we have: (20)
$\displaystyle\Omega(K,C)=\Omega(K,K+2)$
$\displaystyle=\Omega(K,K+1)+\Omega(K-1,K+1)$
$\displaystyle=\Omega(K,K+1)+\Omega(K-1,K)+\Omega(K-2,K)$
$\displaystyle=\cdots$
$\displaystyle=\Omega(K,K+1)+\Omega(K-1,K)+\cdots+\Omega(3,4)+\Omega(2,4)$ As
Eq. 13 and Eq. 19 illustrate, we have: (21) $\displaystyle\Omega(K,C)$
$\displaystyle=2^{K+1}+2^{K}+\cdots+2^{4}+4^{2}-4+2$ $\displaystyle=2^{K+2}-2$
$\displaystyle=2^{C}-2$ $\displaystyle<2^{C}={\Omega}^{*}(K,C),$ which
satisfies the proposition when $C=K+2$. $\triangleleft$ • b). For any $K\geq
2,K\in N_{+}$ and a specific $I\geq 2,I\in N_{+}$, let $C=K+I$, we assume the
inequation $\tilde{\Omega}(K,C)<\Omega^{*}(K,C)$ satisfies: (22)
$\tilde{\Omega}(K,C)=\tilde{\Omega}(K,K+I)<\Omega^{*}(K,K+I)=2^{K+I},$
$\triangleleft$ • c). Then, when $C=K+I+1$, we have: (23)
$\displaystyle\Omega(K,C)=\Omega(K,K+I+1)$
$\displaystyle=\Omega(K,K+I)+\Omega(K-1,K+I)$
$\displaystyle=\Omega(K,K+I)+\Omega(K-1,K+I-1)+\Omega(K-2,K+I-1)$
$\displaystyle=\cdots$

$\displaystyle=\Omega(K,K+I)+\Omega(K-1,K+I-1)+\cdots+\Omega(3,3+I)$
$\displaystyle\quad+\Omega(2,3+I)$
$\displaystyle<2^{K+I}+2^{K+I-1}+\cdots+2^{3+I}+(3+I)^{2}-(3+I)+2$
$\displaystyle=2^{K+I+1}-2^{3+I}+I^{2}+5I+8$ Note that $2^{3+I}\textgreater
I^{2}+5I+8$ when $I\geq 2$, then we have: (24) $\displaystyle\Omega(K,C)$
$\displaystyle<2^{K+I+1}=\Omega^{*}(K,C),$ which satisfies the proposition
when $C=K+I+1$. $\triangleleft$

Finally, according to mathematical induction,
$\tilde{\Omega}(K,C)<{\Omega}^{*}(K,C)$ when $C\textgreater K+1$.

∎

###### Theorem A.3.

When the proxies have converged to fixed positions (i.e., the angles of proxy
pairs are constant), then the best position of $2$-label samples is the middle
of $2$ positive proxies. The $n$-label scenarios can be deduced in a similar
fashion.

###### Proof.

Suppose the feature vector $\bm{v_{x}}$ contains $2$ labels $y_{1}$, $y_{2}$,
with corresponding proxies $\bm{p}_{1}$, $\bm{p}_{2}$. Let
$\theta_{1}=\langle\bm{v_{x}},\bm{p}_{1}\rangle$,
$\theta_{2}=\langle\bm{v_{x}},\bm{p}_{2}\rangle$,
$\theta_{3}=\langle\bm{p}_{1},\bm{p}_{3}\rangle$, where
$\theta_{1},\theta_{2},\theta_{3}\in[0,\pi]$.

Note that the effect of negative proxies is negligible when about convergence,
because they are away from $\bm{v_{x}}$, so we only consider the gradient from
$\bm{p}_{1}$, $\bm{p}_{2}$.

Then we have $\mathcal{L}_{+}=-(\cos\theta_{1}+\cos\theta_{2})$, and the
objective function is $\arg\max(\cos\theta_{1}+\cos\theta_{2})$ accordingly.

If $\bm{v_{x}}$ is non-coplanar with $\bm{p}_{1}$, $\bm{p}_{2}$, we have the
projection $\bm{v_{x}}^{\prime}$ in the plane defined by
$\bm{p}_{1},\bm{p}_{2}$, and denote the corresponding angles with
$\bm{p}_{1}$, $\bm{p}_{2}$ as $\theta_{1}^{\prime}$, $\theta_{2}^{\prime}$,
such that
$\theta_{1}^{\prime}\textless\theta_{1},\theta_{2}^{\prime}\textless\theta_{2}\Rightarrow\cos\theta_{1}^{\prime}+\cos\theta_{2}^{\prime}\textgreater\cos\theta_{1}+\cos\theta_{2}$.

Hence, the optimal objective function is satisfied when
$\bm{v_{x}},\bm{p}_{1},\bm{p}_{2}$ are coplanar such that
$\theta_{1}^{\prime}=\theta_{1},\theta_{2}^{\prime}=\theta_{2}$, and ensures
$\theta_{3}=\theta_{1}+\theta_{2}$. Then we have:

(25)
$\arg\min\mathcal{L}_{+}=\arg\max((1+\cos\theta_{3})\cos\theta_{1}+\sin\theta_{3}\sqrt{1-\cos^{2}\theta_{1}})$

To obtain the extreme point of $\mathcal{L}_{+}$, let:

(26)
$\frac{\partial\mathcal{L}_{+}}{\partial\cos\theta_{1}}=1+\cos\theta_{3}-\sin\theta_{3}\frac{\cos\theta_{1}}{\sqrt{1-\cos^{2}\theta_{1}}}=0$

Note that $1+\cos\theta_{3}\geq 0$, $\sin\theta_{3}\geq 0$,
$\sqrt{1-\cos^{2}\theta_{1}}\geq 0$, we can get $\cos\theta_{1}\geq 0$. Thus
$\theta_{1}\in[0,\frac{\pi}{2}]$. Then, it is easy to obtain that:

(27)
$\displaystyle\frac{1-\cos^{2}\theta_{3}}{2+2\cos\theta_{3}}=1-\cos^{2}\theta_{1}$
$\displaystyle\Rightarrow\cos^{2}\theta_{1}=1-\frac{1-\cos^{2}\theta_{3}}{2+2\cos\theta_{3}}$
$\displaystyle=\cos^{2}\frac{\theta_{3}}{2}$

Considering the domain of $\theta_{1},\theta_{2},\theta_{3}$, we have
$\cos\theta_{1}=\cos\frac{\theta_{3}}{2}\Rightarrow\theta_{1}=\theta_{2}=\frac{\theta_{3}}{2}$,
_i.e_., $\bm{v_{x}}$ will be embedded into the middle of the two proxies.

Similarly, we can extend the conclusion into $n$-label scenarios where the
optimal solution is satisfied when $\bm{v_{x}}^{*}$ is in the middle of
$n$-proxies, as we claimed in the main paper.

∎