A Density-driven Iterative Prototype Optimization for Transductive Few-shot Learning

1 Introduction

Recently, the significance of employing powerful feature embedding has been comprehensively investigated in FSL [Chen et al., 2019; Dhillon et al., 2019; Chen et al., 2020; Tian et al., 2020]. The initial step in most typical FSL methods is to pretrain a feature extractor using the base classes. Then, for each meta-testing task, the features extracted from all images in the support set are utilized to construct a task-specific classifier, facilitating the recognition of image categories within the query set. Although a powerful feature extractor can acquire a suitable feature space for clustering unseen data, the domain shift between training and testing [Lichtenstein et al., 2020; Tao et al., 2022], along with the information gap between support and query [Liu et al., 2022; Dang et al., 2023], pose a formidable challenge for estimating novel class distributions using limited support data. Consequently, the classification performance is directly influenced by the sample quality of the class prototype. If the prototype lacks adequate recognizable information to represent the entire class and contains excessive intra-class diversity to be outlier data, then the constructed classifier may exhibit bias.

∗Corresponding author

The supplementary material is available at: https://zenodo.org/ records/11102557.

In our work, we investigate the correlation between sample quality and density, revealing that sample density plays a crucial role. Intuitively speaking, the direction of sample density growth can be considered the direction in which recognizable information aggregates. In higher-density regions, samples are tightly clustered within a class, which indicates the wealth of recognizable information (or the representative pattern) contained in those regions. Conversely, samples are sparsely observed in lower-density regions. The increased intra-class distance in those regions suggests that the samples tend to be more diverse and have less recognizable information. In other words, the class-specific prototypes in lower-density regions have a lower quality that may confuse the classifier, as shown in Figure 1(left). Thus, to enhance the quality of the prototype, refining it in the direction of sample density growth is necessary. However, only knowing limited support data is inadequate for obtaining a reliable approximation, the estimation of sample density within a class is biased. To minimize the bias of empirical estimation, introducing query samples is the most straightforward way to expand the support set. Unfortunately, this may suffer because of the potentially large information gap between support and query, i.e., the non-estimable intra-class diversity of the novel class, leading to the wrong direction of sample density growth within a class, as shown in Figure 1(right).

Here, we propose a similarity-evaluating strategy to evaluate the information gap between support and query. The similarity-evaluating strategy seeks the base classes for assistance based on the insight: in the feature space, samples from a novel class tend to cluster in a certain direction [Tao et al., 2022], which may indicate that the novel class skewed to that direction has a strong correlation with these base classes. Besides, the covariance matrix contains the underlying distribution information that can effectively assess the intra-class diversity of samples from the same feature distribution [Li et al., 2019; Gao et al., 2018]. Thus, we estimate the covariance matrix of the novel class using the most similar k base classes to the support data (with the closest angular similarity). By normalizing the feature distribution of the novel class using the covariance matrix, the similarity-evaluating strategy can reshape the feature manifold, thus effectively evaluating the information gap between support and query. In addition, we propose a density-driven strategy to improve the quality of the prototype in the direction of density growth. As the prototype progressively gets closer to the region with the local density maximum, the intra-class diversity of the class prototype declines and its representativeness rises.

The similarity-evaluating strategy and the density-driven strategy constitute the Density-driven Iterative Prototype Optimization (DIPO) that we propose in this work. The DIPO is generic, flexible, and can be applied agnostic to the pretrained feature extractor without any extra learnable parameters. By evaluating the information gap between labeled and unlabeled samples and refining the quality of class prototypes, DIPO can effectively enhance the decision boundary of the nearest neighbor classifier. The main contributions of our paper are as follows:

1. We introduce a novel prototype rectifying method by refining the quality of the prototype in the direction of sample density growth for FSL problem.
2. A similarity-evaluating strategy is proposed to adeptly capture the intra-class diversity to evaluate the information gap between labeled and unlabeled samples. Furthermore, a density-driven strategy is proposed to iteratively refine the prototype in the direction of density growth.
3. The proposed method could reach or even exceed the state-of-the-art performance on four benchmark datasets, including miniImageNet, tieredImageNet, CUB, and CIFAR-FS.

2 RelatedWork

Recently, many FSL techniques can be broadly categorized into three groups: optimization-based methods, metric-based methods, and generation-based methods. The optimizationbased approaches, such as MAML [Finn et al., 2017] and LEO [Rusu et al., 2019], concentrate on learning a set of model parameters that allow for fast gradient updates of the initial model for quick adaptation to new tasks. The metricbased methods aim to encode data in a suitable feature embedding space and predict them using distance-based classifiers, such as MatchingNet [Vinyals et al., 2016], ProtoNet [Snell et al., 2017], RelationNet [Sung et al., 2018], etc. The generation-based methods aim to address data scarcity by learning data generation strategies, including AFHN [Li et al., 2020], Matchinggan [Hong et al., 2020], and DC [Yang et al., 2021]. More recently, some works [Chen et al., 2019; Dhillon et al., 2019; Chen et al., 2020; Tian et al., 2020] reveal the significance of employing powerful feature embedding in FSL. This paradigm typically trains a general feature extractor on base classes and then learns a class-specific classifier with the novel classes.

More recently, some studies have explored transductive inference in FSL. Unlike the inductive setting, which can only utilize labeled samples, the transductive setting can access all the query data to restrict the hypothesis space for the novel classes. Based on this observation, some methods have attempted to learn high-quality prototypes in a transductive setting. BD-CSPN [Liu et al., 2020b] is proposed for prototype rectification by label propagation and feature shifting. Lichtenstein [Lichtenstein et al., 2020] aims to utilize subspace learning to extract discriminant features and then perform classification with the prototypes. PT+MAP [Hu et al., 2021] utilizes an optimal-transport-inspired algorithm to adjust the class prototypes. MetaNODE [Zhang et al., 2022] employs a meta-learning-based optimization framework to rectify prototypes. protoLP [Zhu and Koniusz, 2023] improves prototype estimation through prototype-based label propagation. Although these methods exhibit effectiveness to some extent, they are also affected by the information gap [Liu et al., 2022] between labeled and unlabeled samples, leading to bias in prototype estimation. Different from them, our method aims to diminish the damage caused by the potential information gap and proposes a novel perspective for prototype estimation in FSL by refining the quality of the prototype in the direction of sample density growth.

3 Method

3.1 ProblemDefinition

We follow a common few-shot classification framework. Given a dataset with data-label pairs {(xi, yi)} where xi ∈ Rd is the d-dimensional feature vector of a sample and yi ∈ C is the corresponding label. C represents the set of all base classes Cb, validation classes Cv, and novel classes Cn, where Cb ∩ Cv ∩ Cn = ∅ and Cb ∪ Cv ∪ Cn = C. For the N-way K-shot task T , there are a support set S = {(xi, yi)}N×K i=1 and a query set Q = {(xi, yi)}N×q i=1 , where N is the number of classes within the task, and K and q are the labeled support samples and unlabeled query samples per novel class, respectively. The novel class dataset Dnovel is defined as Dnovel = S ∪ Q. Furthermore, there is a fully annotated dataset comprising abundant labeled images from base classes, designated as Dbase = {(xi, yi)}Bi=1 , where B denotes the total number of images within Dbase.

3.2 Similarity-Evaluating Strategy

Many transductive FSL methods focus on leveraging the latent relationships between support and query samples, aiming to maximize the utility of few-shot datasets. However, given that a few labeled samples can solely represent the local feature distribution (especially in a 1-shot setting), the intra-class diversity of the novel class is hard to estimate. Consequently, these methods suffer from the information gap between support and query, i.e., the non-estimable intra-class diversity of the novel class, which makes it difficult to model the latent relationships between labeled and unlabeled samples. We propose an easy-plug-in similarity-evaluating strategy to effectively capture the information gap between support and query.

Step 1: Seeking the relevant base classes. The similarityevaluating strategy is based on the insight that the domain shift between the base and novel classes results in the skewness of the novel class distribution in a certain direction [Tao et al., 2022].This may indicate that the novel class skewed in that direction has a strong correlation with these base classes. Inspired by the insight, we employ a mechanism to transfer the diversity of the relevant base classes, thereby quantifying the non-estimable intra-class diversity inherent in the novel class. Specifically, we first calculate the mean feature of each novel class using the following formulation:

where Sj denotes the subset of samples belonging to the j-th novel class within the support set, expressed as S = {S1, ..., SN}. The notation |Sj| signifies the count of samples contained within Sj , xi represents the feature vector corresponding to the sample i, and yi denotes the assigned label.

We then select the top k base classes based on the closest angular similarity between the mean of the support features and the mean of the features from base classes, as quantified by the cosine distance:

where µbi is the mean of the features from base class i, the notation cos(·, ·) represents the cosine distance, and Topk(·) represents the operator for selecting k elements possessing the highest values from Dj. Ij contains the most relevant k base classes with respect to the mean feature µj .

Step 2: Making the distribution more Gaussian-like. We assume that the features of each class follow a multivariate Gaussian distribution, where the intra-class diversity can be effectively embedded in a covariance matrix. To reduce the domain shift as mentioned above and improve the consistency of the feature distribution with the Gaussian distribution, we transform the features in base and novel classes using Tukey's Algorithm 1 The prediction procedure of the proposed DIPO for an N-way-K-shot task

Require: Dbase

Require: Dnovel = S ∪Q

• 1: Select the most similar base classes for each novel class (Equation 1, 2).
• 2: Transform the features from Dbase and Dnovel with Tukey's Ladder of Power Transform (Equation 3).
• 3: Approximate the covariance matrix for each novel class (Equation 4, 5).
• 4: Calculate the initial prototype for each novel class (Equation 7).
• 5: for iter in {1, · · · ,Niter} do
• 6: Select the most similar query neighbors to form the neighborhood set for each novel class (Equation 8, 9).
• 7: Refine the initial prototype in the global direction of sample density growth for each novel class (Equation 10, 11).
• 8: end for
• 9: Predict the labels of query samples via a nearest neighbor classifier (Equation 12).

Ladder of Power transform [Tukey, 1977]:

where β denotes a hyperparameter utilized to fine-tune the skewness of the feature distribution. Modifying the value of β brings the distribution closer to a Gaussian-like distribution and makes the intra-class diversity across different classes more relevant. After the Tukey's transformation, the support set and the query set in the novel classes are updated to S = {(ˆxi, yi)}N×K i=1 and Q= {(ˆxi, yi)}N×q i=1 .

Step 3: Normalizing the feature distribution for the novel class. We evaluate the information gap between support and query by normalizing the feature distribution for each novel class. More precisely, we first approximate the covariance matrix for each novel class using the weighted covariance of the relevant base classes. The weight factor is expressed as follows:

The approximated covariance of the novel class j is formulated as:

where Σbi is the corresponding covariance matrix of the base class i after Tukey's transformation, and ¯σ is the average diagonal variance of Σj, as the regularization term to prevent Σj from being non-invertible. By this approximation, the covariance of the novel class j is more accurate and stable than the covariance calculated using the support set. With only a few labeled samples (especially in a 1-shot setting), the covariance of the support set is unable to capture the entire intra-class diversity of the novel class. Given the correlation between the novel class and the relevant base classes, extrapolating the intra-class diversity of the novel class from the base classes is considered a more accurate alternative.

For a feature vector within a class, there are locations encoding class-specific information and locations encoding class-independent information, thus reflecting the intra-class diversity. Values at class-specific locations tend to demonstrate high correlations, playing a significant role in distinguishing the class. Conversely, values derived from classindependent locations are similar among all samples, which indicates redundant information and has little effect on classification. To emphasize the locations encoding class-specific information and mitigate interference from the locations encoding class-independent information, we normalize the feature distribution for the novel class j as follows:

where ˆxi is the unlabeled feature after Tukey's transformation corresponding to the sample i in the query set, ˆxj is the labeled feature after Tukey's transformation corresponding to the sample j in Sj, and Σj is the approximated covariance matrix of the novel class j. And the information gap across features under the same distribution is represented by the d(·, ·), which is known as the Mahalanobis distance. Through this normalization process, the feature manifold for the novel feature distribution is reshaped to amplify the distinctions between features. This effectively evaluates the information gap between features, thus facilitating the modeling of latent relationships between support and query.

3.3 Density-Driven Strategy

The sample quality of the class-specific prototype has a direct impact on the classification performance. We propose a density-driven strategy to improve the quality of the prototype. The density-driven strategy is based on the insight: in the feature space, there are higher-density regions and lowerdensity regions. Samples from higher-density regions are tightly clustered within a class to distinguish them well. Samples are sparsely observed in lower-density regions, which indicates they have a lower quality to separate well between classes. Therefore, the direction of sample density growth can be seen as the direction in which recognizable information aggregates. Consequently, we enhance the sample quality of the prototype in the direction of density growth.

The overview of the proposed density-driven strategy is shown in Figure 2, which consists of three steps at the nth iteration: 1) Given the prototype of the novel class, we identify the lower-density region A for the novel class using the high-confident query neighbors from the query set. 2) We determine the local direction of sample density growth by locating the center of higher-density region B. 3) We refine the initial prototype by the global direction of sample density growth. As the initial prototype progressively gets closer to the higher-density regions, the intra-class diversity of the prototype declines and its representativeness rises. Specifically, the initial class prototype for the novel class j is computed as the mean of support features after Tukey's transformation:

Unfortunately, with only a few samples, the prototype based on the mean of the support features is prone to overfitting on the support data and far from representing the whole novel class. Subsequently, the prototype is iteratively re-estimated in the manner described below:

Step 1: Seeking the query neighbors to identify the lower-density region. To estimate the sample density for novel class j around the prototype, we select some high-confident pseudo-labeled neighbors from the query set. Specifically, the confidence in classifying the query sample ˆxi into the novel class j at the n-th iteration is calculated as follows:

where c(n) j is the prototype of novel class j at the n-th iteration, and the d(·, ·) is the information gap between the query sample ˆxi and the prototype as formulated in Equation 6 in the similarity-evaluating strategy. As the similarityevaluating strategy adeptly captures the information gap between features, it enables the generation of pseudo-labels with high quality. Subsequently, we select the top m(n) pseudo-labeled query samples with the highest confidence for each novel class, thereby constituting the neighborhood set as follows:

where Topm(·) represents the operator for selecting m(n) elements with the highest confidence from each column of the matrix, and the hyperparameter m(n) denotes the total number of samples within the neighborhood set per novel class at the n-th iteration. Q denotes the unlabeled query set after Tukey's transformation. Aj contains the indices of the top m(n) high-confident query neighbors with respect to the prototype c(n) j . Nj is the neighborhood set of novel class j, which comprises the query samples corresponding to the indices stored in Aj. The neighborhood set represents the local neighborhood information of the prototype, which can be used to describe the density. Thus, the lower-density region A for novel class j is delineated by the prototype c(n) j and the query neighbors within the neighborhood set Nj , as shown in Figure 2(1).

Step 2: Determining the local direction of sample density growth. Inspired by the mean shift [Fukunaga and Hostetler, 1975], we determine the local direction of sample density growth by locating the center of the higher-density region. More precisely, the center of the higher-density region B for novel class j at the n-th iteration is calculated as:

where Nj is the neighborhood set of novel class j, andm(n) is the number of samples within the neighborhood set Nj. The higher-density region B for novel class j is located by the center C (n) B and the query neighbors within the neighborhood set Nj , as shown in Figure 2(2).

The direction from the center of the lower-density region to the center of the higher-density region is the mean shift vector, which always points towards the direction of the maximum increase in the density [Fukunaga and Hostetler, 1975]. Consequently, the direction from the prototype c(n) j to the center C (n) B can be interpreted as the local direction of density growth.

Step 3: Refining the initial prototype in the global direction of density growth. For a more stable and accurate estimation, we refine the prototype by taking into account all local directions of sample density growth from previous iterations. Specifically, the refined prototype is formulated as:

where c(0) j is the initial prototype of novel class j, C (n) B is the center of the higher-density region B for novel class j at the n-th iteration, and λ = m(n) |Sj|+m(n) . This indicates that as the hyperparameter m(n) increases, the refined prototype gradually moves closer to C (n) B from c(0) j , which can be interpreted as the global direction of sample density growth, as shown in Figure 2(3). To avoid making risky decisions in the early iterations and to obtain a more stable and accurate prototype, we propose to slowly increase the number of query neighbors m(n) during the iterations. For simplicity, we define a tuple (m, Niter, step) to illustrate m(n) at each iteration, where m indicates the number of query neighbors for the first iteration, Niter denotes the number of iterations, and step represents the incremental increase in m for each subsequent iteration in the density-driven strategy. Therefore, the refined prototype c(Niter) j can be regarded as the final prototype of novel class j.

3.4 Final Classification

We employ a nearest neighbor classifier as the task-specific classifier for each meta-test task. Specifically, the confidence of the query sample ˆxi belonging to class j is estimated based on the information gap between it and the prototype as follows:

where c(Niter) j is the final prototype of class j obtained through the density-driven strategy, and the information gap d(·, ·) is evaluated using Equation 6 in the similarityevaluating strategy. Algorithm 1 shows the prediction procedure of the proposed DIPO.

4 Experiments

4.1 Experimental Setup

Datasets. We evaluate our approach on four representative few-shot classification benchmarks, including miniImageNet, tieredImageNet, CIFAR-FS, and CUB. miniImageNet constitutes a subset of ImageNet [Russakovsky et al., 2014]. Following the previous work [Ravi and Larochelle, 2017], the dataset is categorized into 64 base classes, 16 validation classes, and 20 novel classes. tieredImageNet represents a more extensive subset of ImageNet [Russakovsky et al., 2014], featuring 608 classes derived from a hierarchical category structure. Consistent with the previous work [Ren et al., 2018], the dataset is partitioned into 351 base classes, 97 validation classes, and 160 novel classes. CUB is a fine-grained dataset that encompasses 200 distinct bird classes. Following [Welinder et al., 2010], we divide the dataset into 100 base classes, 50 validation classes, and 50 novel classes. Following [Bertinetto et al., 2018], CIFAR-FS is split into 64 base classes, 16 validation classes, and 20 novel classes.

Implementation Details. For the feature extractor, we employ the ResNet-18 [Chen et al., 2019], ResNet-12 [Rizve et al., 2021] and WRN-28-10 [Mangla et al., 2020] to show the effectiveness of our method. Note that the features are extracted from the penultimate layer (with a ReLU activation function) of the feature extractor, ensuring that all values are non-negative to maintain the validity of Tukey's transformation in Equation 3. For the task-specific classifier, we employ a nearest neighbor classifier to establish the effective decision boundaries for the novel classes. The hyperparameters of the proposed method contain the number of relevant base classes k, the power of Tukey's transformation β, and the tuple (m, Niter, step), where m is the number of query neighbors for each novel class at the first iteration, Niter is the number of iterations, and step is the incremental increase in m for each subsequent iteration. More detailed information on the hyperparameter settings and the hyperparameter tuning is presented in the supplementary material. We follow the 5-way 1-shot and 5-way 5-shot settings and use the top-1 accuracy as the evaluation metric to evaluate the performance of our method. Unless otherwise specified, there are 15 query samples per class in each task. The reported results represent the average accuracy (%) along with the 95% confidence interval, computed over 10,000 tasks randomly selected from the novel classes.

4.2 Experimental Results

Few-shot image classification. We compare the proposed DIPO with state-of-the-art methods in the 5-way 1-shot and 5-way 5-shot settings. Table 1 shows the results on miniImageNet and tieredImageNet, and Table 2 shows the results on CUB and CIFAR-FS. Our DIPO is insensitive to feature extractors, and we employ the algorithms proposed in Baseline [Chen et al., 2019], Inv-Equ [Rizve et al., 2021], and S2M2-R[Mangla et al., 2020] to obtain the pre-trained feature extractor to show the effectiveness of our method. Compared to the baseline models [Chen et al., 2019; Rizve et al., 2021; Mangla et al., 2020], our method exhibits an average improvement of nearly 16% in the 1-shot task and nearly 6% in the 5-shot task. Among the state-of-the-art methods, BDCSPN, SIB, MetaNODE, PT+MAP, and protoLP are our strong competitors since they also focus on learning highquality prototypes for the novel classes. Compared to the competitors, we can observe that the DIPO achieves consistent improvements on different datasets. And the improvements are larger in the 1-shot task than the 5-shot task since the prototype is more biased in the 1-shot setting. This further illustrates the effectiveness of our approach in refining the prototypes. From these experiments, we can conclude that our proposed DIPO could reach or exceed the state-of-the-art methods under the 5-way 1-shot and 5-way 5-shot settings of miniImageNet, tieredImageNet, CIFAR-FS, and CUB.

Cross-domain (miniImageNet → CUB). Cross-domain is a challenging scenario in few-shot classification due to the large domain shift between the base and novel domains. To show the effectiveness of our method in the cross-domain scenario, we conduct the tests on miniImageNet →CUB. In particular, we follow the steps to train ResNet-18 described by [Chen et al., 2019], where the base classes are drawn from miniImageNet, and the novel classes are drawn from CUB. Table 3 shows the 5-way 5-shot results achieved using ResNet-18 as the feature extractor for a fair comparison. These results show that the proposed DIPO outperforms others by about 3% margins. Our method employs a mechanism to transfer the diversity of the top k relevant base classes to facilitate the recognition of novel classes. By selecting the number of relevant base classes k, it is adept at handling scenarios where the base and novel domains exhibit differences.

The class-unbalanced setting [Veilleux et al., 2021] is presented in the supplementary material.

4.3 Ablation Study

We conduct the comparison experiments to show the effectiveness of the similarity-evaluating strategy and the densitydriven strategy proposed in our DIPO. Since the similarityevaluating strategy employs the Mahalanobis distance to measure the information gap between the labeled and unlabeled samples, we compare it with the cosine distance and Euclidean distance for better illustration. Results are presented in Table 4. The application of the density-driven strategy results in improvement gains of 14.16%, 12.92%, and 24.10% for the cosine distance, Euclidean distance, and similarity-evaluating strategy, respectively, in the 5-way 1shot task. Since the density-driven strategy utilizes the query samples for transductive inference, it can derive a more accurate prototype than the initial prototype obtained solely from support samples. The first three rows and the last three rows in Table 4 compare the cosine distance, Euclidean distance, and similarity-evaluating strategy without and with the density-driven strategy, respectively. The similarityevaluating strategy can adeptly capture the information gap between features compared to the other two distance metrics: 1) it amplifies the bias in the initial prototype, resulting in lower performance as shown in the first three rows; 2) it contributes to a greater improvement based on the higher-quality prototype as shown in the last three rows. The comparison results further demonstrate the effectiveness of our method.

4.4 Visualization of DIPO

We visualize the prototypes refined by our DIPO for a 5-way 1-shot task on miniImageNet by means of t-SNE [van der Maaten and Hinton, 2008], as shown in Figure 3. Note that the initial prototype is the support sample since there is only one support sample in each novel class. It can be seen that the initial prototypes are biased and far away from the class centers. By refining the prototypes in the direction of density growth, the prototypes progressively get closer to the class centers. This indicates that our DIPO effectively learns highquality prototypes.

5 Conclusion

In this paper, we investigate the correlation between sample quality and density and propose a Density-driven Iterative Prototype Optimization (DIPO) to improve the quality of the prototypes. We show that the proposed method brings consistent performance improvements over multiple baselines and could reach or exceed the state-of-the-art performance on four benchmark datasets, including miniImageNet, tieredImageNet, CUB, and CIFAR-FS. The visualization of the refined prototypes by DIPO shows that our method can effectively learn high-quality prototypes.

Acknowledgments

This work was supported by the STI 2030-Major Projects under grant 2022ZD0208900, the Guangdong Basic and Applied Basic Research Foundation under grant 2024A151501052.