Prototype-Based Support Example Miner and Triplet Loss for Deep Metric Learning

Abstract

Deep metric learning aims to learn a mapping function that projects input data into a high-dimensional embedding space, facilitating the clustering of similar data points while ensuring dissimilar ones are far apart. The most recent studies focus on designing a batch sampler and mining online triplets to achieve this purpose. Conventionally, hard negative mining schemes serve as the preferred batch sampler. However, most hard negative mining schemes search for hard examples in randomly selected mini-batches at each epoch, which often results in less-optimal hard examples and thus sub-optimal performances. Furthermore, Triplet Loss is commonly adopted to perform online triplet mining by pulling the hard positives close to and pushing the negatives away from the anchor. However, when the anchor in a triplet is an outlier, the positive example will be pulled away from the centroid of the cluster, thus resulting in a loose cluster and inferior performance. To address the above challenges, we propose the Prototype-based Support Example Miner (pSEM) and Triplet Loss (pTriplet Loss). First, we present a support example miner designed to mine the support classes on the prototype-based nearest neighbor graph of classes. Following this, we locate the support examples by searching for instances at the intersection between clusters of these support classes. Second, we develop a variant of Triplet Loss, referred to as a Prototype-based Triplet Loss. In our approach, a dynamically updated prototype is used to rectify outlier anchors, thus reducing their detrimental effects and facilitating a more robust formulation for Triplet Loss. Extensive experiments on typical Computer Vision (CV) and Natural Language Processing (NLP) tasks, namely person re-identification and few-shot relation extraction, demonstrated the effectiveness and generalizability of the proposed scheme, which consistently outperforms the state-of-the-art models.

1. Introduction

Deep metric learning aims to develop a similarity metric superior to traditional Euclidean distance by focusing on the derivation of high-dimensional data representations [1]. Contemporary research underscores the criticality of designing batch samplers [2,3,4] and employing online triplet mining [5,6,7,8], with hard negative mining schemes [9,10,11] traditionally serving as the preferred choice, proving their crucial role in significantly refining the similarity metric in deep metric learning. For an understanding of key concepts related to hard example mining and Batch Samplers, see the Section 3. These techniques have found utility in various tasks, including face recognition [12,13,14,15,16], person re-identification (ReID) [2] within Computer Vision, and Natural Language Processing tasks such as few-shot relation extraction [17], few-shot text classification [18], text clustering [19], and sentence embedding [20], thereby boosting performance. Although certain methods, including the batch sampler and online triplet mining, have indeed demonstrated admirable performance, two significant challenges persist that invite further scholarly exploration.

Challenge 1: Traditional batch samplers struggle to identify hard examples situated at cluster intersections. To the best of our knowledge, existing types of batch samplers include the standard PK sampler (PK) [21] and the sampler associated with hard negative mining (HNM) schemes. The PK, while randomly selecting P classes and K examples from each class, experiences compromised efficiency in sampling hard examples due to the randomness of its approach. To circumvent this limitation, certain HNM schemes construct mini-batches for each epoch by mining hard examples from the entire training datasets, thereby achieving significant results [2,3,22,23]. These schemes primarily identify hard classes by creating Nearest Neighbor Graphs (NNGs) at instance-to-instance [3] or instance-to-class [22,23] (e.g., state-of-the-art Graph Sampling (GS) [2]) levels. Subsequently, examples (e.g., the examples in the red rectangular box as depicted in Figure 1) are randomly chosen from these hard classes to compose the mini-batch [2]. It is worth noting that the direct mining of hard examples, such as those enclosed by the rectangle in Figure 1 situated at the intersections of clusters (i.e., groups of data objects belonging to the same class as represented by green circles in Figure 1), is often overlooked in much of the existing research due to the prevalence of random sampling from hard classes. Importantly, these examples pose significant classification challenges for the model. Although they may seem analogous to the ‘support vectors’ in SVM [24] due to their positions and influences on the model, they play a different role in our context because of their distinct definitions and usages. We refer to these hard examples as ‘support examples’ and their corresponding classes as ‘support classes’. The necessity of studying the construction of prototype-based NNGs arises, aiming to identify the support classes and select support examples located at the intersections of support class clusters. Details on prototype acquisition will be thoroughly discussed in the Section 4. As depicted in

Table 1. Comparison of methods for constructing mini-batch.

Scheme	Hard Class Selection	Hard Example Selection
PK	Random	Random
GS	Non-random	Random
Our pSEM	Non-random	Non-random

, we compared the PK, GS [2], and our proposed Prototype-based Support Example Miner (pSEM), detailed subsequently. Since the PK and GS randomly sample hard examples, they are incapable of mining support examples. In contrast, our non-random pSEM focuses on intersections between clusters, directly mining support examples, as illustrated in Figure 1.

Challenge 2: Online Triplet Mining overlooks the issue of excessively loose clusters caused by outliers serving as anchors. The Online Triplet Mining (OTM) scheme, proposed by Triplet Loss [5], operates on triplets of examples (anchor, positive, negative) and generally aims to minimize the distance between the anchor and the positive example while maximizing the distance between the anchor and the negative example within the mini-batch [5,7,8,25]. Nonetheless, when the anchor is an outlier, it can lead to overly loose clusters, which are not preferable in deep learning due to their potential detriment to model classification. Specifically, the positive example distances itself from the class cluster as the distance between the outlier anchor and the positive example is minimized, as illustrated in Figure 2(1). This scenario may consequently result in an excessively loose cluster to which the positive example belongs. This adverse outcome also arises when the distance between the outlier anchor and the negative example is maximized. Inspired by stochastic optimization strategies, our approach integrates the concept of historical gradients—a technique that uses previously computed gradients to curb oscillation and stabilize the learning process [26]—to effectively address the challenges associated with outlier anchors and excessively loose clusters. To tackle these issues, we introduce the notion of ‘historical normal anchors’, which we define as the normal anchors derived from previous mini-batches during the training process. In an innovative twist, we merge these historical normal anchors with outlier anchors, utilizing the exponentially weighted average formula [26] to create a corrected, normal anchor. Through this merging process, the outlier anchors are infused with the intrinsic structure characteristic of historical normal anchors—a structure embodying inherent patterns, similarities, and clusters within the data. This maneuver not only brings outlier anchors closer to both historical normal anchors and cluster centers but also facilitates better alignment with the underlying structure of the data. Ultimately, this method significantly enhances the representational quality of outlier anchors within the intrinsic structure, demonstrating its robustness and innovation in addressing the outlined challenges. As depicted in Figure 2(2), the corrected outlier anchor pulls the positive example, alleviating the aforementioned adverse outcome.

To address the challenges encountered in the two stages of deep metric learning, we propose a Prototype-based Support Example Miner and Triplet Loss. Initially, the Prototype-based Support Example Miner (pSEM) identifies support classes by building the NNGs with the prototype and mines the support examples at the cluster intersections of support classes. Secondly, to alleviate the problem of excessively loose clusters caused by outlier anchors, we design the Prototype-based Triplet Loss (pTriplet Loss). pTriplet Loss can detect the outlier anchor and subsequently correct it by integrating the outlier anchor with the historical normal anchor. We showcase the effectiveness and generalizability of our schemes through experiments on Person Re-identification (ReID) and Few-shot Relation Extraction (FSRE), which are typical tasks in Computer Vision (CV) and Natural Language Processing (NLP), respectively.

2. Related Work

In the domain of deep metric learning, several studies focus on the design of batch samplers and OTM to learn a similarity metric function. These methods are specifically engineered to mine hard examples from the training set, thereby enabling the model to concentrate on learning these examples during the training process [1].

Batch sampler designing. The standard methodologies include typical PK samplers and HNM schemes. The PK sampler fails to mine hard examples, as elaborated in the Section 1. HNM schemes, on the other hand, stabilize the deep neural network after a few iterations or each epoch and then leverage the updated model to detect hard examples across the entire training set. This model constructs hard examples within each mini-batch for training at each step. Bootstrapping [27] is a technique that employs the updated model every few iterations to find hard examples within the training set while training deep neural networks, although this dramatically decelerates the training progress. Recent work aims to expedite the training progress by adapting training strategies. SmartMining [3], for instance, establishes approximate Nearest Neighbor Graphs (NNGs) grounded in the instance-to-instance distance at the outset of each training epoch. However, considering all examples makes constructing instance-to-instance level NNGs resource-consuming. Wang et al. [22] suggests randomly sampling hard examples from hard classes determined by K-means clustering. Nonetheless, K-means can easily converge to a local optimal solution [28], implying that the hard class obtained might not necessarily be the support class. Suh et al. [23] procures hard classes from NNGs constructed based on instance-to-class distances, and then the hard example is obtained through random sampling from the hard class. As this operation is conducted at each iteration, it results in enormous computational costs. To mitigate these shortcomings, GS [2] randomly samples a single example per class for NNG construction based on instance-to-instance distance. Despite its effectiveness, it is not without flaws. For instance, when a class encompasses tens of thousands of training examples, a randomly selected example may poorly represent the class. Moreover, the selected hard examples, randomly sampled from the hard classes, may not be situated at the intersection between clusters, as discussed in Section 1. Hence, the hard examples obtained by such methods are the non-support examples. Distinct from the aforementioned methods, our proposed Prototype-based Support Example Miner (pSEM) builds the NNGs predicated on the prototype (i.e., class-to-class distance). It identifies the support classes across the entire training dataset and then selects examples at the intersection between clusters, thus effectively mining the support example.

Online Triplet Mining. Schroff et al. [5] introduced OTM, which mines hard positives and hard negatives in each mini-batch based on the loss value to form a triplet (anchor, hard positive, hard negative). These triplets are then utilized to update the model. A substantial number of the remaining triplets do not participate in the model update process, significantly accelerating the model’s convergence rate. To address the ’local optimal solutions’ concern—which arises when the Triplet Loss method mines hard samples within a mini-batch, not the entire training set, potentially leading to the less accurate identification of truly hard samples or understating their hardness level—Ge [7] proposed a solution. They suggested constructing a hierarchical class tree encompassing all classes in the training set, thereby expanding the mining scope for a more accurate hard sample identification. Cai et al. [25] proposed the Hard Exemplar Reweighting Triplet Loss, which assigns weights to the triplets according to their difficulty level. The t-Distributed Stochastic Triplet Embedding (t-STE) [29] algorithm adeptly refines data embeddings by enforcing similarity triplet constraints while concurrently amalgamating similar instances and diverging dissimilar ones, thereby unearthing the genuine structure of underlying data. Vasudeva et al. [8] presented LoOp, which can be employed to alleviate the biased embedding caused by Triplet Loss. To the best of our knowledge, existing research has not addressed the problem of excessively loose clusters resulting from anchors being outliers. In response, we propose pTriplet Loss, which amalgamates outlier anchors and prototypes to generate a typical anchor near the cluster center, thereby alleviating this issue.

3. Background

To ensure our paper is readily comprehensible for the general reader, we provide definitions of key concepts in this section.

3.1. Batch Sampler

Batch Samplers, in the context of machine learning, act as components of a data loader that are responsible for grouping individual data points into batches and retrieving these batches of data points during each iteration of model training or inference.

3.2. Hard Example Mining

Hard Example Mining refers to an insightful approach in deep metric learning, systematically identifying instances in the training set that pose significant challenges to accurate model classification. This approach plays a pivotal role in pushing the boundaries of model performance, fostering the cultivation of a superior similarity metric [30].

Hard Example. Hard examples, typically instances the model tends to misclassify in the training set, often lead to performance bottlenecks. By shifting the model’s learning emphasis towards these challenging cases, much in the same way human learners stress their own mistakes, we can enhance the model’s learning proficiency in the face of difficulties, thereby more effectively advancing the development of a superior similarity metric, a key objective in deep metric learning [31].

Hard Class. Hard classes can be defined as groups of examples that share common traits but are inherently complex or ambiguous to classify, often posing substantial challenges to the accuracy and efficiency of machine learning models.

Hard Negtive Mining. The Hard Negative Mining schemes construct mini-batches for each epoch by mining hard examples from the entire training datasets [27,32,33].

4. Methodology

Figure 3 illustrates the architecture of our proposed framework, comprising primarily the Prototype-based Support Example Miner (pSEM) and Triplet Loss components. In Step 1, we utilize pSEM to mine support examples, which, in the context of pedestrian re-identification, refer to pedestrians with similar appearances. Initially, we derive a prototype for each class within the training set using the model updated at the end of the previous epoch. Subsequently, we identify support classes by constructing Nearest Neighbor Graphs (NNGs) based on these prototypes. Finally, we mine support examples from the intersections between clusters of support classes, which are then used to assemble the mini-batch. In Step 2, we refine the anchor using pTriplet Loss. For the current epoch, the input mini-batch is processed through the backbone network to obtain the feature vectors of the examples. Our pTriplet Loss detects the outlier anchor and then amends it by fusing the outlier anchor with the historical normal anchor to generate a new, standard anchor. Ultimately, the pTriplet Loss integrates other loss functions (e.g., cross-entropy loss function) for back-propagation. Upon completion of the current epoch’s training, this process is repeated until model convergence.

Formally, given a training set ${\displaystyle \mathbb{T}=x_1,x_2,x_3,\dots ,x_n}$ consisting of C classes, we extract the support example set ${\displaystyle \mathbb{H}=h_1,h_2,h_3,\dots ,h_m}$ from ${\displaystyle \mathbb{T}}$. The pSEM identifies the support example set ${\displaystyle \mathbb{H}}$ on the training set ${\displaystyle \mathbb{T}}$ prior to the commencement of each epoch and utilizes these examples to construct the mini-batch for subsequent model training. The mini-batch encompasses M classes, with N examples from each class. Additionally, pTriplet Loss combines the outlier anchor $f_{\theta }\left(x^o\right)$ and prototype $V_P$ to produce a new, standard anchor $V_u$.

4.1. Prototype-Based Support Example Miner

The pSEM mines support examples at the intersections of clusters belonging to support classes on NNGs to construct mini-batches for model training.

Formulation of Nearest Neighbor Graphs (NNGs) for Support Class Determination. NNGs, which are prevalent graph structures, are formulated for all classes within the training set using their respective prototypes. Each prototype is depicted as a node, with edges connecting it to its ‘nearest neighbors’, which are ascertained via a distance metric such as cosine similarity. To elaborate, the cosine similarity between classes is computed utilizing the class-specific prototype, conceived as the mean of the feature vectors corresponding to each class’s instances.

$$V_{P_i}=\frac{{\sum }_{j=1}^k{f}_{\theta }\left(x_{i,j}\right)}{k},i\in [1,C]$$

(1)

where f denotes the backbone, i signifies the i-th class, and k represents the number of examples in the i-th class. Moreover, $f_{\theta }\left(x_{i,j}\right)$ is the feature vector of the j-th example in the i-th class, and $V_{P_i}$ represents the prototype of the i-th class.

For any class in the training set, we identify its nearest-neighbor class by comparing the cosine distance between the prototype of this class and the prototypes of all other classes. Each class and its nearest neighbors, being the closest in the feature vector space and challenging for the model to distinguish, are considered support classes and grouped into a set of support classes.

$${\displaystyle {\mathbb{S}}_i=\{s_1,s_2,\dots ,s_l\},i\in [1,C]}$$

(2)

where ${\displaystyle {\mathbb{S}}_i}$ represents the set of support classes consisting of the i-th class and its neighbors, l is the size of the ${\displaystyle {\mathbb{S}}_i}$, and $s_i$ denotes the i-th support class. Thus, the NNGs are constructed as

$${\displaystyle \mathcal{G}=(\mathbb{V},\mathbb{E}),\mathbb{V}=\{v_1,v_2,\dots ,v_C\},\mathbb{E}=\{(v_i,v_j)\mid v_i\in \mathbb{S}\left(v_j\right)\}.}$$

(3)

In this case, ${\displaystyle \mathbb{V}}$ refers to all classes in the training set, and ${\displaystyle \mathbb{E}}$ refers to the set of edges. The ${\displaystyle \mathbb{S}\left(v_j\right)}$ represents the support classes of class $v_j$.

Mining Support Examples. To identify the support example, we explore the intersection between clusters of support classes on ${\displaystyle \mathcal{G}}$. Specifically, for any two support classes that are nearest neighbors, we compute the vector $V_m$ of their midpoints based on the prototype $V_P$.

$${\displaystyle V_m=\frac{(V_{P_a}+V_{P_b})}{2},a,b\in {\mathbb{S}}_i}$$

(4)

where $V_{P_a}$ and $V_{P_b}$ denote the prototypes of support class a and support class b, respectively.

We consider the sphere centered at $V_m$ with radius $\delta$ as the region encompassing the intersection between clusters of support classes. Subsequently, we calculate the cosine distance between $V_m$ and each example within the support classes. Ultimately, the example with a distance less than the threshold $\delta$ is selected as the support example.

$$\begin{array}{c}{\displaystyle {\mathbb{T}}_{a_b}={\mathbb{T}}_a\cup {\mathbb{T}}_b}\hfill \\ {\displaystyle {\mathbb{T}}_{a_b}=\{t\in {\mathbb{T}}_{a_b}\mid 1-cos(f_{\theta }\left(x_t\right),V_m)<=\delta \}}\hfill \end{array}$$

(5)

where ${\displaystyle {\mathbb{T}}_i}$ represents the set of examples corresponding to the i-th class and ${\displaystyle {\mathbb{H}}_{a_b}}$ represents the set of support examples. By adjusting the value of $\delta$, we can effectively select support examples of varying degrees of difficulty. Refer to the hyper-parameter sensitivity analysis in Section 5.8.3 for further details.

4.2. Prototype-Based Triplet Loss

The aim of pTriplet Loss is to enhance the efficacy of Triplet Loss by identifying and rectifying outlier anchors.

Identification of Outlier Anchors. We compute the distance d between each example in the cluster and the prototype, defining those examples with a cosine distance d exceeding the threshold $\lambda$ as outlier anchors, while the remaining are treated as normal anchors.

$$\begin{array}{c}{d}_j=1-cos(V_{p_i},x_j)\hfill \\ {\displaystyle \mathbb{O}=\{o\in {\mathbb{T}}_i\mid d_j>\lambda \}}\hfill \\ {\displaystyle \mathbb{N}=\{n\in {\mathbb{T}}_i\mid d_j<=\lambda \}}\hfill \end{array}$$

(6)

In this case, ${\displaystyle \mathbb{O}}$ and ${\displaystyle \mathbb{N}}$ correspond to the outlier anchor set and the set of normal anchors, respectively.

Prototype Updating. In each step of the model learning process, we employ an exponentially weighted average formula, a weighted average strategy [26]. This involves initializing an average value and a decay factor ($\alpha$), and at each step, a new value is obtained and combined with the previous average using the decay factor. The exponentially weighted average formula assigns decreasing weights to the values over time, giving more importance to recent values. By applying this formula and considering the neural network’s improved updates, which lead to better and more accurate representations of the normal anchors obtained in the current step, we fuse the normal anchor and prototype within the mini-batch, resulting in the update of the prototype vector, capturing more precise representations.

$$V_{P_i}^{\left(t\right)}=\alpha \times V_{P_i}^{(t-1)}+(1-\alpha )\times f_{\theta }\left(x_{i,j}^{\left(n\right)}\right),\alpha \in [0,1]$$

(7)

where f represents the backbone, i refers to the i-th class, j signifies the j-th example, and $f_{\theta }\left(x_{i,j}^{\left(n\right)}\right)$ is the feature vector of the normal anchors $x_{i,j}^{\left(n\right)}$. The term $V_{P_i}^{\left(t\right)}$ is the prototype of the i-th class after t iterations, while $\alpha$ is the adjustment factor controlling the proportion of $V_{P_i}^{(t-1)}$ in the updated prototype $V_{P_i}^{\left(t\right)}$. This prevents the proportion of prototype $V_{P_i}^{(t-1)}$ from becoming too large, which could result in over-compaction of clusters and over-fitting. The prototype derived via pSEM prior to each epoch serves as the initial value of $V_P$ for the current epoch.

Outlier Anchor Correction. By employing the exponentially weighted average formula, we generate a corrected normal anchor, denoted as $V_u$, through the weighted averaging of updated prototypes $V_P^{\left(t\right)}$ and detected outlier anchors $x^{\left(o\right)}$, where the prototypes are derived from historical normal anchors. The correction process imbues the outlier anchors with the intrinsic structure that is characteristic of normal anchors—a structure that encompasses inherent patterns, similarities, and clusters within the data. Consequently, this process propels outlier anchors closer to both normal anchors and cluster centers, thereby enabling better alignment with the inherent structure of the data. As a result, this methodology markedly enhances the representation quality of outlier anchors within the intrinsic structure.

$$\begin{array}{c}{V}_u=\beta \times V_{p_i}^{\left(t\right)}+(1-\beta )\times f_{\theta }\left(x_{i,j}^{\left(o\right)}\right),\hfill \\ {\displaystyle x_{i,j}^{\left(o\right)}\in \mathbb{O},\beta \in [0,1]}\hfill \end{array}$$

(8)

Formulation of pTriplet Loss. Given the above discussion, the Prototype-based Triplet Loss can be formalized as follows:

$$\begin{array}{ccc}\hfill {\mathcal{L}}_{\mathrm{pTriplet}}(\theta ;x)=\sum _{i=1}^M\sum _{a=1}^N[m& +\underset{p=1\dots K}{max}D\left(V_a^i,f_{\theta }\left(x_p^i\right)\right)\hfill & \hfill -\underset{\begin{array}{c}j=1\dots M\\ n=1\dots N\\ j\ne i\end{array}}{min}D\left(V_a^i,f_{\theta }\left(x_n^j\right)\right){]}_{+}\end{array}$$

(9)

where D represents the Euclidean distance and $f_{\theta }\left(x_p^i\right)$ and $f_{\theta }\left(x_n^j\right)$ are the features of positive and negative examples, respectively. $V_a^i$ is either the corrected outlier anchor $V_u$ or the normal anchor $V_n$, and m represents a margin between positive and negative pairs. The Batch Size is $M\times N$. pTriplet Loss seeks to minimize the distance between the anchor and the positive example and maximize the distance between the anchor and the negative example during training within the mini-batch.

5. Experiment

To validate the effectiveness and generalizability of our approach, we performed a range of empirical experiments, including quantitative performance comparisons, qualitative analyses, ablation studies, and sensitivity analyses of hyperparameters. These experiments were carried out on typical Computer Vision and Natural Language Processing tasks, specifically person re-identification and few-shot relation extraction.

Annotation: In Tables 4–6, ① signifies the use of the PK sampler and Triplet Loss, while ② indicates the usage of the GS [2] sampler and Triplet Loss during the training phase.

5.1. Overview of the Person Re-Identification Experiment

5.1.1. Introduction of Hard Examples for ReID

People exhibiting similar appearances are categorized as hard examples.

5.1.2. Datasets, Evaluation Metrics, Baseline, Comparison Scheme, and Experimental Settings

Datasets: In person re-identification and generalizable person re-identification tasks, we employ four datasets to validate our proposed scheme: Market1501 [34], DukeMTMC-ReID [35], MSMT17 [36], and CUHK [37]. The specifics of these datasets are summarized in

Table 2. The dataset statistics of the person ReID ${}^{\mathrm{a}}$.

Dataset	${\mathit{ID}}_{\mathit{q}}$	${\mathit{ID}}_{\mathit{g}}$	${\mathit{ID}}_{\mathit{t}}$	${\mathit{IMG}}_{\mathit{q}}$	${\mathit{IMG}}_{\mathit{g}}$	${\mathit{IMG}}_{\mathit{t}}$	${\mathit{CAM}}_{\mathit{n}}$
MSMT17	3060	3060	1041	11,659	82,161	32,621	15
Market1501	750	750	751	3368	19,732	12,936	6
DukeMTMC	702	702	702	2228	17,661	16,522	8
CUHK03-NP	700	700	767	1400	5332	7365	2

${}^{\mathrm{a}}$ $I{D}_q$, $I{D}_g$, and $I{D}_t$ represent the number of IDs (pedestrians) in the query set, gallery set, and training set, respectively. $IM{G}_q$, $IM{G}_g$, and $IM{G}_t$ denote the number of images in the query set, gallery set, and training set, respectively. $CA{M}_n$ represents the number of cameras in the dataset.

. Notably, the generalizable person-re-identification task can assess the model’s generalization ability using hard negative schemes and online Triplet Loss. Cross-dataset evaluation is conducted by training the model on the training set of the source dataset and then evaluating it on the test set of the target dataset.

Evaluation Metrics: We employ Rank-1 (R1) and mean average precision (mAP) as our evaluation metrics. R1 denotes the accuracy rate of the first result in the retrieved outcomes, while mAP measures the overall ranking accuracy of the retrieved results. Detailed descriptions of these two evaluation metrics are provided below.

mAP: 

Let us denote $query$ as the set of images to be retrieved, hypothetically containing N images, where $q_i$ represents the i-th query image. Thus, the dataset is represented as $Q=\{q_1,q_2,\dots ,q_n\}$. Similarly, $gallery$ refers to the image database, hypothetically encompassing M images, with $g_i$ standing for the i-th image. The dataset is represented as: $G=\{g_1,g_2,\dots ,g_i,\dots ,g_M\}$. Let us denote the number of the query image $q_i$ in G as $K_{q_i}$. For each query process, after extracting the feature vector from $q_i$, the algorithm computes the distance by comparing this vector with the feature vectors of each image in G. Subsequently, the $gallery$ is sorted in ascending order based on this distance, resulting in a sorted $gallery$ dataset represented as $G_{q_i}$. The dataset composed of the hit images for $q_i$ is denoted as $\widehat{G_{q_i}}=\left\{\widehat{g_1},\widehat{g_2},\dots ,\widehat{g_j},\dots ,\widehat{g_{K_{q_i}}}\right\}$, which is a subset of $G_{q_i}$. Let us assume $\widehat{g_j}$ ranks as $r_j$ in $G_{q_i}$ and $\widehat{r_j}$ in $\widehat{G_{q_i}}$. By repeating this process for all query images, we can formulate the precision calculation as follows:

$$mAP=\frac{1}{N}\sum _{i=1}^N\sum _{j=1}^{K_{q_i}}\left(\widehat{r_j}/r_j\right)$$

(10)

R1: 

For a given query, denoted as $q_i$, if the top-ranked image in $G_i$ (the $gallery$) corresponds to the same ID/person, we say $q_i$ achieves first-rank accuracy. Let $\widehat{N}$ represent the number of all queries in Q that satisfy this first-rank accuracy condition. Then, Rank-1’s accuracy is calculated as

$$R1=\widehat{N}/N$$

(11)

Baseline: We adopt the widely-used PK sampler as the HNM baseline, which randomly selects P pedestrians from the training set, with each pedestrian randomly picking K images to construct a mini-batch. For online hard example mining, we utilize Triplet Loss as the baseline [5].

Comparison Scheme: For the comparison of HNM strategies, we utilize Cluster [22] and the state-of-the-art (SOTA) GS [2]. It should be mentioned that as the Cluster [22] does not provide open-source code, we only reference its experimental results on the generalized person re-identification task from [2].

Experimental Settings: Our approach is based on the official PyTorch code of TransReID [38] (https://github.com/damo-cv/TransReID, accessed on 27 May 2021) and GS [39] (https://github.com/ShengcaiLiao/QAConv, accessed on 1 May 2022). In the person re-identification task, we employ ViT [40] as the backbone, and the data augmentation strategy comprises random horizontal flipping, padding, random cropping, and random erasing [41]. The backbone for the generalizable person re-identification task is ResNet50 [42], augmented with IBN-b layers. The data augmentation strategies involve random cropping, flipping, occlusion, and color jittering. The input image is resized to dimensions 384 × 128, and the loss function is either Triplet Loss or cross-entropy loss. The remaining hyperparameters, such as batch size and the learning rate of the optimizer, are set according to the settings of TransReID [38] and GS [39]. Some table columns are left empty, indicating that the method has not been tested on the corresponding datasets. The parameter values mentioned in the Section 4, including $\delta$, $\lambda$, $\alpha$, and $\beta$, are empirically determined. For reference values, please consult the sample values provided in the project code linked in the Abstract section.

5.2. Overview of the Few-Shot Relation Extraction Experiment

5.2.1. Introduction of Hard Examples for the Few-Shot Relation Extraction Task

During the training phase, we mine sentences from various categories that share similar semantics, classifying them as hard examples.

5.2.2. Datasets, Evaluation Metrics, Baseline and Comparison Scheme, Experimental Settings

Dataset: To validate our proposed approach, we utilize the extensively employed FewRel few-shot relation extraction dataset [43]. This dataset encompasses 100 relations and 70,000 instances extracted from Wikipedia and a concealed test set comprising 20 relations. Adhering to the procedure delineated in prior work [44], we reorganize the available 80 relations into 50 for training, 14 for validation, and 16 for testing.

Evaluation Metrics: The N-way-K-shot (N-w-K-s) paradigm is routinely used to simulate the distribution of few-shot relation extraction across diverse scenarios. Here, N and K denote the number of classes and the number of examples per class, respectively. In the N-w-K-s framework, accuracy is the prime performance measure.

Baseline: The PK sampler is widely used as the baseline for Hard Negative Mining (HNM), while Triplet Loss is adopted as the benchmark for online hard example mining [5].

Comparison Scheme: To the best of our knowledge, there are no specialized HNM and OTM strategies designed particularly for few-shot relation extraction. A majority of the HNM and OTM approaches employed in Natural Language Processing (NLP) originate from the field of Computer Vision (CV). Consequently, we have chosen the GS scheme for comparison. We also consider the noteworthy model ConceptFERE [44] as our principal point of comparison.

Experimental Settings: We initialize the parameters for BERT [45] using the BERT-base-uncased model with a hidden size of 768. Hyperparameters, including the learning rate, adhere to the settings prescribed in ConceptFERE [44].

5.2.3. Model Training Details

For instance, taking 5-w-1-s as an example, during the data sampling stage of mining support examples, our scheme randomly samples a target class. Subsequently, we identify the top-4 nearest neighbors in the training set to serve as the support class. Each of the sampled five classes discovers its support examples and then randomly assigns support examples to the query and support sets. Both our proposed scheme and GS are implemented on ConceptFERE (https://github.com/LittleGuoKe/ConceptFERE, accessed on 1 May 2022).

5.3. Comparison with State-of-the-Art HNM Schemes on the Generalizable ReID Task

Due to the limited size of the CUHK03-NP and Market1501 test sets, variations in the Rank-1 (R1) rate by a few percentage points cannot accurately reflect the model’s performance. Nevertheless, the mean average precision (mAP) metric measures the overall retrieval performance; thus, we prioritize mAP as the main evaluation metric on both datasets. Notably, our method outperforms all other approaches in terms of mAP, as illustrated in

Table 3. Comparison of different HNM schemes.

Method	Training Set	MSMT17		Market1501		CUHK03-NP
		R1	mAP	R1	mAP	R1	mAP
PK	Market1501	43.6	15.7	-	-	17.9	17.6
Cluster [22]	Market1501	44.0	15.8	-	-	18.4	17.3
GS [2]	Market1501	45.9	17.2	-	-	19.1	18.1
Ours	Market1501	48.4	18.3	-	-	19.2	18.5
PK	MSMT17	-	-	75.9	45.3	16.4	17.0
Cluster [22]	MSMT17	-	-	77.2	47.6	18.4	19.2
GS [2]	MSMT17	-	-	79.1	49.5	20.9	20.6
Ours	MSMT17	-	-	79.2	50.1	21.1	21.3
PK	MSMT17 (all)	-	-	79.5	52.3	22.8	23.3
Cluster [22]	MSMT17 (all)	-	-	80.4	54.2	26.3	26.3
GS [2]	MSMT17 (all)	-	-	82.4	56.9	27.6	28.0
Ours	MSMT17 (all)	-	-	82.6	58.1	30.2	30.3
GS [2]	CUHK03-NP	46.9	15.4	68.2	37.3	-	-
Ours	CUHK03-NP	48.4	16.3	69.8	38.2	-	-

. Specifically, the PK sampler underperforms due to its reliance on random sampling for mini-batch construction, which yields minimal support examples for mining. On the other hand, the Cluster [22] and GS [2] schemes yield improved performance as they obtain non-random hard classes. Our scheme delivers a significant improvement over the state-of-the-art GS, with gains of 2.5% and 1.5% in R1, and 1.1% and 0.9% in mAP for Market1501→MSMT17 and CUHK03-NP→MSMT17 transfers, respectively (where A→B indicates training on dataset A and testing on dataset B). This demonstrates that our method can effectively enhance the baseline in large-scale settings. The superior performance of our scheme, particularly in terms of mAP, can be attributed to the following factors: our proposed pSEM can mine the support examples at cluster intersections, and the pTriplet Loss corrects outliers to compact clusters, simplifying classification. For an in-depth quantitative analysis of our proposed scheme’s superiority, readers are referred to the cases of hard example mining depicted in Figure 4 and the distribution of intra-class similarity, as detailed in Section 5.8.1. The presented results in Figure 4, obtained by random sampling from mini-batches constructed using the standard PK sampler, the state-of-the-art GS [2] sampler, and our pSEM, compare their effectiveness in mining support examples during the ReID task training. We employed a random sampling method to ensure a fair comparison. Owing to space limitations, only a portion of the selected results is displayed.

5.4. Performance Comparison of HNM and OTM Schemes on Person Re-Identification Tasks

As demonstrated in

Table 4. Comparison of various schemes’ evaluation results.

Backbone	Method	Size	MSMT17		Market ${}^{\mathbf{a}}$		Duke ${}^{\mathbf{b}}$
			mAP	R1	mAP	R1	mAP	R1
CNN	CBN [46]	256 × 128	42.9	72.8	77.3	91.3	67.3	82.5
	OSNet [47]	256 × 128	52.9	78.7	84.9	94.8	73.5	88.6
	MGN [48]	384 × 128	52.1	76.9	86.9	95.7	78.4	88.7
	RGA-SC [49]	256 × 128	57.5	80.3	88.4	96.1	-	-
	SAN [50]	256 × 128	55.7	79.2	88.0	96.1	75.7	87.9
	SCSN [51]	384 × 128	58.5	83.8	88.5	95.7	79.0	91.0
	ABDNet [52]	384 × 128	60.8	82.3	88.3	95.6	78.6	89.0
	PGFA [53]	256 × 128	-	-	76.8	91.2	65.5	82.6
	HOReID [54]	256 × 128	-	-	84.9	94.2	75.6	86.9
	ISP [55]	256 × 128	-	-	88.6	95.3	80.0	89.6
DeiT-B/16	DeiT [56] + ①	256 × 128	61.4	81.9	86.6	94.4	78.9	89.3
	TransReID [38] + ①	384 × 128	66.3	84.5	88.5	95.1	82.1	91.1
ViT-B/16	ViT [40] + ①	256 × 128	61.0	81.8	86.8	94.7	79.3	88.8
	TransReID [38] + ①	384 × 128	69.4	86.2	89.5	95.2	82.6	90.7
ViT-B/16	TransReID + ②	384 × 128	70.0	86.9	89.6	95.6	83.4	91.2
	TransReID + Ours	384 × 128	70.7	87.8	90.0	95.5	83.6	91.5

${}^{\mathrm{a}}$ Market refers to Market1501. ${}^{\mathrm{b}}$ Duke means DukeMTMC.

, our proposed scheme outperforms other approaches across various datasets. Specifically, we observe a performance improvement of 1.3% in Rank-1 accuracy (R1) and 1.6% in mean Average Precision (mAP) on the MSMT17 dataset when compared to the TransReID scheme. Furthermore, our method registers gains of 0.7% in R1 and 0.9% in mAP on the MSMT17 dataset relative to the GS scheme [2]. Two possible reasons contribute to our method’s superior performance over GS. First, our methodology builds the Nearest Neighbour Graphs (NNGs) based on the prototype, while GS forms the NNGs at the instance level. Hence, the nearest neighbors determined by our method are the support classes and not the non-support classes. Secondly, our proposed scheme pSEM focuses on support examples at the intersection between clusters, which are overlooked by GS.

5.5. Performance Comparison of HNM and OTM Schemes on General Person-Re-Identification Tasks

Table 5. Direct cross-dataset evaluation results ${}^{\mathrm{a}}$.

Method	Training Set	CUHK03-NP		Market1501		MSMT17
		R1	mAP	R1	mAP	R1	mAP
M${}^3$L [57]	Multi	33.1	32.1	75.9	50.2	36.9	14.7
MGN [48]	Market1501	8.5	7.4	-	-	-	-
MuDeep [58]	Market1501	10.3	9.1	-	-	-	-
QAConv [39]	Market1501	9.9	8.6	-	-	22.6	7.0
OSNet-AIN [59]	Market1501	-	-	-	-	23.5	8.2
CBN [46]	Market1501	-	-	-	-	25.3	9.5
QAConv [39] + ②	Market1501	19.1	18.1	-	-	45.9	17.2
QAConv [39] + Ours	Market1501	19.2	18.5	-	-	48.4	18.3
PCB [60]	MSMT17	-	-	52.7	26.7	-	-
MGN [48]	MSMT17	-	-	48.7	25.1	-	-
ADIN [61]	MSMT17	-	-	59.1	30.3	-	-
SNR [62]	MSMT17	-	-	70.1	41.4	-	-
CBN [46]	MSMT17	-	-	73.7	45.0	-	-
QAConv [39] + ②	MSMT17	20.9	20.6	79.1	49.5	-	-
QAConv [39] + Ours	MSMT17	21.1	21.3	79.2	50.1	-	-
		R1	mAP	R1	mAP	R1	mAP
OSNet-IBN [47]	MSMT17 (all)	-	-	66.5	37.2	-	-
OSNet-AIN [59]	MSMT17 (all)	-	-	70.1	43.3	-	-
QAConv [39] + ①	MSMT17 (all)	25.3	22.6	72.6	43.1	-	-
QAConv + ②	MSMT17 (all)	27.6	28.0	82.4	56.9	-	-
QAConv [39] + Ours	MSMT17 (all)	30.2	30.3	82.6	58.1	-	-
QAConv [39] + ②	CUHK03-NP	-	-	68.2	37.3	46.9	15.4
QAConv [39] + Ours	CUHK03-NP	-	-	69.8	38.2	48.4	16.3

^a Note: “MSMT17 (all)” implies that the model utilizes both the test set and the training set for training. M³L selects three datasets from CUHK03, Market1501, DukeMTMC-ReID, and MSMT17 for training and leaves the remaining one for testing.

presents the state-of-the-art (SOTA) direct cross-dataset evaluation results, with each group reflecting a model trained on the source dataset’s training set and tested on the target dataset’s test set. As can be seen, our proposed scheme delivers the most impressive performance across all groups. For instance, with the MSMT17(all)→CUHK03-NP transfer, our proposed scheme records gains of 2.6% in R1 and 2.3% in mAP over GS. The primary reason for our scheme’s superiority is its consideration of support examples at the intersection between clusters, which is not a feature of GS as it randomly samples examples from each class that are not necessarily support examples. Our proposed loss function, pTriplet Loss, corrects outlier anchors when computing loss, thereby encouraging clusters to converge more compactly. As a result, the model’s classification surface becomes more distinguishable and generalizable on the general person-re-identification task.

5.6. Performance Comparison of HNM and OTM Schemes on Few-Shot Relation Extraction Tasks

Table 6. Accuracies (%) of different models on the test set ${}^{\mathrm{a}}$.

Backbone	Sampler	Model	5-w-1-s	10-w-1-s
CNN	PK	Gnearest neighbor [63]	67.30	54.10
		SNAIL [64]	71.13	50.61
		Proto [65]	74.29	61.15
		HATT-Proto [66]	74.84	62.05
		MLMAN [67]	78.21	65.70
BERT	PK	Bert-PAIR [68]	82.57	73.37
		TD-Proto [69]	84.76	74.32
		ConceptFERE (Simple) [44]	84.28	74.00
		ConceptFERE [44]	89.21	75.72
BERT	GS	ConceptFERE + ②	89.37	75.75
BERT	Ours	ConceptFERE + Ours	90.24	78.85

${}^{\mathrm{a}}$ Note: Owing to the inherent variability in the Few-Shot Relation Extraction (FSRE) experiment, we consider the average of ten experimental results as the final outcome.

presents the performance of different hard example mining schemes on the FewRel [43] dataset test set. Our proposed scheme outperforms all comparator methods, with gains of 1.03% and 3.13% in the scenarios of 5-way-1-shot (5-w-1-s) and 10-way-1-shot (10-w-1-s), respectively, compared to ConceptFERE, the best-performing model in the second group. The potential reason for this improvement is that the PK Sampler randomly selects classes and examples, making it virtually impossible to mine support examples. More importantly, our proposed scheme yields gains of 0.87% and 3.1% over GS in the 5-w-1-s and 10-w-1-s scenarios, respectively. This superior performance can be attributed to GS’s limitations in the NLP scene, where each class has thousands of examples and complex semantics. By building an NNG at the instance level, GS may not accurately model the inter-class relationships, making it challenging to mine support classes. Furthermore, it overlooks support examples at the cluster intersections.

5.7. Ablation Study

This section substantiates the efficacy of the proposed Prototypical Semantic Mining (pSEM) and Prototypical Triplet Loss (pTriplet Loss), elaborated in Section 4.1 and Section 4.2, respectively. As demonstrated in

Table 7. Ablation study results on the MSMT17 dataset for the person ReID task.

Scheme	R1	mAP
TransReID + Ours	87.8	70.7
w/o pSEM	87.4	70.3
w/o pTriplet Loss	87.3	70.2
w/o pSEM & pTriplet Loss	86.2	69.4

and

Table 8. Ablation study results for the FSRE task. Accuracy (%) is used as the performance evaluation metric.

Scheme	10-w-1-s
ConceptFERE + Ours	78.85
w/o pSEM	76.81
w/o pTriplet Loss	77.12
w/o pSEM & pTriplet Loss	75.72

, the absence of pSEM and pTriplet Loss results in a significant performance drop for both TransReID and ConceptFERE. This evidence confirms that the pSEM effectively mines support examples and that pTriplet Loss aptly corrects outlier anchors, optimizing the performance of Triplet Loss.

5.8. Qualitative Analysis

5.8.1. Evidence of Cluster Compactness

To validate that our proposed pTriplet Loss engenders more compact clusters, we present the intra-class variance distributions resulting from both Triplet Loss and pTriplet Loss in

Table 9. Variance distribution of intra-class similarity on MSMT17.

Model	Variance	Sampler	Online Hard Example Loss
TransReID	45.2	PK	Triplet Loss
	32.9	PK	pTriplet Loss

. Lower variance indicates higher example similarity within a class, suggesting a closer spatial grouping and hence more compact clusters. The intra-class variance in the ReID task, defined as the variance of the cosine distance between any two examples within a class, is portrayed in Table 9. A perusal of this table confirms the superior compactness of clusters produced by pTriplet Loss.

5.8.2. Comparative Analysis of Predictive Results

To provide an intuitive understanding of the effects of different Hard Negative Mining (HNM) and Other Training Methods (OTM) on the model’s ability to classify challenging examples, we use the person ReID task as an illustration. Specifically, we randomly select a group from the retrieval results, as displayed in Figure 5. These retrieval results have been randomly sampled from predictions made by models trained using the PK sampler, GS, and our method (pSEM), all showcasing their top five outcomes. The images marked with yellow, green, and red boxes denote the query, positive example, and negative example, respectively, with a random sampling approach adopted to ensure a fair comparison.

An examination of the case presented in Figure 5 reveals that models trained with our method demonstrate a superior ability to discriminate support examples. For a detailed theoretical analysis, refer to Section 5.8.1.

5.8.3. Hyper-Parameter Sensitivity Analysis

• Sensitivity Analysis of $\mathbf{\delta }$ in Equation (5) In our evaluation, the influence of $\delta$ in determining the difficulty level of the mined support examples is evident. As illustrated in Figure 6, a decrement in the $\delta$ value leads to an increase in the complexity of the examples extracted by pSEM, and a lower $\delta$ value results in the extraction of examples lying closer to the intersection of clusters, thereby augmenting the challenge of identification. Accordingly, by adjusting the $\delta$ value, we enabled the selection of support examples with varying difficulty levels. To ensure an unbiased comparison, the outcomes were randomly selected from pSEM, employing different delta values.
• Sensitivity Analysis of $\mathbf{\lambda }$ in Equation (6) $\lambda$ is utilized to detect outliers at varying distances from the cluster center. As depicted in Figure 7, an increase in the value of $\lambda$ incrementally enhances the model’s performance until it reaches a stable state. This behavior suggests that the identification of outliers distant from the cluster center contributes to the improvement in the model’s performance.
• Sensitivity Analysis of $\mathbf{\alpha }$ in Equation (7) In the process of prototype updating, we assess the impact of the proportion of the current normal anchor in the updated prototype $V_{P_i}^{\left(t\right)}$ on model performance. This is accomplished by adjusting the $\alpha$ value as demonstrated in Figure 8. An excessive proportion adversely impacts the model’s performance, leading to overfitting.
• Sensitivity Analysis of $\mathbf{\beta }$ in Equation (8) $\beta$ determines the proportion of prototypes in the corrected outlier anchors. Figure 9 illustrates that an increment in $\beta$ value results in diminished model performance, a consequence of overfitting.

5.9. Training Time Comparison

Table 10. Comparison of training times when QAConv employs PK, GS, and pSEM samplers, respectively.

	Training		CUHK3		Market		MSMT17
	Data	Hours	R1	mAP	R1	mAP	R1	mAP
PK	Market	1.07	13.3	14.2	-	-	40.9	14.7
GS	Market	0.25	19.1	18.1	-	-	45.9	17.2
pSEM	Market	0.24	19.2	18.5	-	-	48.4	18.3
PK	MSMT17	2.37	15.6	16.2	72.9	44.2	-	-
GS	MSMT17	0.73	20.9	20.6	79.1	49.5	-	-
pSEM	MSMT17	0.70	21.1	21.3	79.2	50.1	-	-
PK	MSMT17 (all)	17.85	25.1	24.8	79.5	52.3	-	-
GS	MSMT17 (all)	3.42	27.6	28.0	82.4	56.9	-	-
pSEM	MSMT17 (all)	3.31	30.2	30.2	82.6	58.1	-	-

presents a comparison of training times when employing the QAConv [39] backbone, following GS [2], while using PK, GS, and pSEM as samplers. Our pSEM significantly accelerates the training process compared to PK and GS samplers. This increased efficiency is attributed to QAConv’s ability to learn the support examples positioned at the intersection of clusters, selectively picked by our pSEM.

6. Conclusions

In this work, we examined the challenges associated with hard negative learning and online triplet mining schemes, both of which are integral components of deep metric learning. Our developed pSEM successfully mines support examples utilizing prototype-based NNGs. Additionally, the designed pTriplet Loss corrects outlier anchors for Triplet Loss, enabling the production of more compact clusters, which is advantageous for model classification. The efficacy and generalizability of our method are evident from the experimental results. As a future direction, we aim to develop a fine-grained discrimination module at the model level to distinguish hard examples more effectively.