TASK AFFINITY WITH MAXIMUM BIPARTITE MATCH-
Year: 2022

Abstract:
We propose an asymmetric affinity score for representing the complexity of utilizing the knowledge of one task for learning another one. Our method is based on the maximum bipartite matching algorithm and utilizes the Fisher Information matrix. We provide theoretical analyses demonstrating that the proposed score is mathematically well-defined, and subsequently use the affinity score to propose a novel algorithm for the few-shot learning problem. In particular, using this score, we find relevant training data labels to the test data and leverage the discovered relevant data for episodically fine-tuning a few-shot model. Results on various few-shot benchmark datasets demonstrate the efficacy of the proposed approach by improving the classification accuracy over the state-of-the-art methods even when using smaller models.

heading: 1 INTRODUCTION
text: Leveraging the knowledge of one task in training the other related tasks is an effective approach to training deep neural networks with limited data. In fact, transfer learning, multi-task learning (Standley et al., 2020), and meta-learning (Finn et al., 2017) are examples of training a new task using the knowledge of others. In fact, a strong piece of work (Standley et al., 2020) has shown that training similar tasks together in multi-task learning often achieves higher accuracy on average. However, characterizing the similarity between tasks remains a challenging problem. In this paper, we present a task similarity measure representing the complexity of utilizing the knowledge of one task for learning another one. Our measure, called Task Affinity Score (TAS), is non-commutative and is defined as a function of the Fisher Information matrix, which is based on the second-derivative of the loss function with respect to the parameters of the model under consideration. By definition, the TAS between two tasks is always greater or equal to 0, where the equality holds if and only if both tasks are identical. For the classification tasks, the TAS is invariant to the permutation of the data labels. In other words, modifying the numeric order of the data labels does not affect the affinity score between tasks. Additionally, TAS is mathematically well-defined, as we will prove in the sequel.
Following the introduction of TAS, we propose a few-shot learning method based on the similarity between tasks. The lack of sufficient data in the few-shot learning problem has motivated us to use the knowledge of similar tasks for our few-shot learning method. In particular, our approach is capable of finding the relevant training labels to the ones in the given few-shot target tasks, and utilizing the corresponding data samples for episodically fine-tuning the few-shot model. Similar to recent few-shot approaches (Chen et al., 2021; Tian et al., 2020), we first use the entire training dataset to train a Whole-Classification network. Next, this trained model is used for extraction of the feature vectors for a set of constructed source task(s) generated from the training dataset. The purpose of the sources task(s) is to establish the most related task(s) to the target task defined according to the test data. In our framework, TAS with a graph matching algorithm is applied to find the affinity scores and the identification of the most related source task(s) to the target task. Lastly, we follow the standard few-shot meta-learning in which a set of base tasks are first constructed, and a few-shot model is fine-tuned according to the query set of these base tasks. Our approach has a unique distinguishing property from the common meta-learning approaches: our base tasks are constructed only based on the previously discovered related source tasks to episodically finetune the few-shot model. Specifically, the feature vectors of the query data from the base tasks are extracted by the encoder of the Whole-Classification network, and a k-nearest neighbors (k-NN) is applied to classify the features into the correct classes by updating the weights in the encoder.
Using extensive simulations, we demonstrate that our approach of utilizing only the related training data is an effective method for boosting the performance of the few-shot model with less number of parameters in both 5-way 1-shot and 5-way 5-shot settings for various benchmark datasets. Experimental results on miniImageNet (Vinyals et al., 2016), tieredImageNet (Ren et al., 2018), CIFARFS (Bertinetto et al., 2018), and FC-100 (Oreshkin et al., 2018) datasets are provided demonstrating the efficacy of the proposed approach compared to other state-of-the-art few-shot learning methods.

heading: 2 RELATED WORK
text: The similarity between tasks has been mainly studied in the transfer learning literature. Many approaches in transfer learning (Silver & Bennett, 2008; Finn et al., 2016; Mihalkova et al., 2007; Niculescu-Mizil & Caruana, 2007; Luo et al., 2017; Razavian et al., 2014; Pan & Yang, 2010; Mallya & Lazebnik, 2018; Fernando et al., 2017; Rusu et al., 2016; Zamir et al., 2018; Kirkpatrick et al., 2017; Chen et al., 2018) are based on the assumption that similar tasks often share similar architectures. However, these works mainly focus on transferring the trained weights from the previous tasks to an incoming task, and do not seek to define the measurement that can identify the related tasks. Though the relationship between visual tasks has been recently investigated by various papers (Zamir et al., 2018; Pal & Balasubramanian, 2019; Dwivedi & Roig, 2019; Achille et al., 2019; Wang et al., 2019; Standley et al., 2020), these works only focus on the weight-transferring and do not use task similarity for discovering the closest tasks for improving the overall performance. Additionally, the measures of task similarity from these papers are often assumed to be symmetric, which is not typically a realistic assumption. For example, it is easier to utilize the knowledge of a comprehensive task for learning a simpler task than the other way around.
In the context of the few-shot learning (FSL), the task affinity (similarity) has not been explicitly considered. Most of the recent few-shot learning approaches are based on the meta-learning frameworks (Santoro et al., 2016; Finn et al., 2017; Vinyals et al., 2016; Snell et al., 2017). In these approaches, episodic learning is often used in the training phase, in which the FSL models are exposed to data episodes. Each episode, consisting of the support and query sets, is characterized by the number of classes, the number of samples per class in the support set, and the number of samples per class in the query set. During the training phase, the loss over these training episodes is minimized. Generally, these episodic learning approaches can be divided into three main categories: metric-based method, optimization-based method, and memory-based method. In metricbased methods (Vinyals et al., 2016; Snell et al., 2017; Koch et al., 2015; Sung et al., 2018), a kernel function learns to measure the distance between data samples in the support sets, then classifies the data in the query set according to the closest data samples in the support set. On the other hand, the goal of optimization-based methods (Finn et al., 2017; Grant et al., 2018; Rusu et al., 2018; Lee et al., 2019; Nichol et al., 2018) is to find the models with faster adaption and convergence. Lastly, the memory-based methods (Santoro et al., 2016; Ravi & Larochelle, 2017; Munkhdalai et al., 2018) use the network architectures with memory as the meta-learner for the few-shot learning. Overall, episodic learning in FSL has achieved great success on various few-shot meta-datasets.
Recently, several methods with a pre-trained Whole-Classification network have achieved state-ofthe-art performance on multiple FSL benchmarks (Chen et al., 2021; Tian et al., 2020; Rodrı́guez et al., 2020; Rizve et al., 2021). Instead of initializing the FSL model from scratches, these methods focus on leveraging the entire training labels for pre-training a powerful and robust classifier. The pre-trained model, by itself, outperforms several meta-learning approaches in numerous FSL datasets (e.g., miniImageNet, tieredImageNet, CIFAR-FS, etc.). Next, the Whole-Classification network is used as a feature extractor for a simple base learner (e.g., logistic regression, K-nearest neighbor, etc.) and is often fine-tuned using episodic learning. Various efforts have been investigated to improve the Whole-Classification network for the few-shot learning, including manifold mixup as self-supervised loss (Mangla et al., 2020), knowledge distillation on the pre-trained classifier (Verma et al., 2019; Tian et al., 2020), and data-augmentation with combined loss functions (Rodrı́guez et al., 2020; Rizve et al., 2021). However, none of these approaches consider the task affinity in their training procedure. Here, we propose a task affinity measure that can identify the related tasks to a target task, given only a few data samples. Then we utilize the data samples in the related tasks for episodically fine-tuning the final few-shot classifier.

heading: 3 PRELIMINARIES
text: In this section, we present the definition of the task affinity score. First, we need to define some notations and definitions used throughout this paper. We denote the matrix infinity-norm by ||B||∞ = maxi,j |Bij |. We also denote a task T and its dataset X jointly by a pair (T,X). To be consistent with the few-shot terminologies, a dataset X is shown by the union of the support set, Xsupport and the query set, Xquery, i.e., X = Xsupport ∪ Xquery. Let PNθ (T,Xquery) ∈ [0, 1] be a function that measures the performance of a given model Nθ, parameterized by θ ∈ Rd on the query setXquery of the task T . We define an ε-approximation network, representing the task-dataset pair (T,X) as follows: Definition 1 (ε-approximation Network). A model Nθ is called an ε-approximation network for a pair task-dataset (T,X) if it is trained using the support dataXsupport such thatPNθ (T,Xquery) ≥ 1− ε, for a given 0 < ε < 1.
In practice, the architectures for the ε-approximation networks for a given task T are selected from a pool of well-known hand-designed architectures, such as ResNet, VGG, DenseNet, etc. We also need to recall the definition of the Fisher Information matrix for a neural network. Definition 2 (Fisher Information Matrix). For a neural network Nθ with weights θ, data X , and the negative log-likelihood loss function L(θ) := L(θ,X), the Fisher Information matrix is defined as:
F (θ) = E [ ∇θL(θ)∇θL(θ)T ] = −E [ H ( L(θ) )] , (1)
where H is the Hessian matrix, i.e., H ( L(θ) ) = ∇2θL(θ), and expectation is taken w.r.t the data.
In practice, we use the empirical Fisher Information matrix computed as follows:
F̂ (θ) = 1 |X| ∑ i∈X ∇θLi(θ)∇θLi(θ)T , (2)
where Li(θ) is the loss value for the ith data point in X . Next, we define the task affinity score, which measures the similarity from a source task, Ta to a target task, Tb. Definition 3 (Task Affinity Score (TAS)). Let (Ta, Xa) be the source task-dataset pair with Nθa denotes its corresponding ε-approximation network. Let Fa,a be the Fisher Information matrix of Nθa with the query data X query a from the task Ta. For the target task-dataset pair (Tb, Xb), let Fa,b be the Fisher Information matrix of Nθa with the support data X support b from the task Tb. We define the TAS from the source task Ta to the target task Tb based on Fréchet distance as follows:
s[a, b] := 1√ 2
Trace ( Fa,a + Fa,b − 2(Fa,aFa,b)1/2 )1/2 . (3)
Here, we use the diagonal approximation of the Fisher Information matrix since computing the full Fisher matrix is prohibitive in the huge space of neural network parameters. We also normalize these matrices to have unit trace. As a result, the TAS in equation (3) can be simplified by the following formula:
s[a, b] = 1√ 2 ∥∥∥F 1/2a,a − F 1/2a,b ∥∥∥ F = 1√ 2 [∑ i ( (F iia,a) 1/2 − (F iia,b)1/2 )2]1/2 , (4)
where F ii denotes the ith diagonal entry of the Fisher Information matrix. The TAS ranges from 0 to 1, with the score s = 0 denotes a perfect similarity and the score s = 1 indicates a perfect dissimilarity. In the next section, we present our few-shot approach based on the above TAS.

heading: 4 FEW-SHOT APPROACH
text: In the few-shot learning problem, a few-shot task of M -way K-shot is defined as the classification of M classes, where each class has only K data points for learning. One common approach (sometimes called meta-learning) to train a model for M -way K-shot classification is to first construct some training tasks from the training dataset, such that each task has a support set with M × K
samples and a separate query set of data points with the same M labels in the support set. The goal is to use the training data (the support set for training and the query set for evaluating the performance of the training tasks), and the support set of the test data to train a model to achieve high performance on the query set of the test data. Recently, there is another few-shot approach called Whole-Classification (Chen et al., 2021; Tian et al., 2020) is proposed to use the whole training dataset for training a base classifier with high performance. Here the assumption is that the training set is a large dataset, which is sufficient for training a high accuracy classifier with all the labels in the training set. On the other hand, the test set, which is used to generate the few-shot test tasks, is not sufficiently large to train a classifier for the entire labels. Here, our proposed few-shot learning approach, whose pseudo-code is shown in Algorithm 1, consists of three phases:
1. Training Whole-Classification Network and Feature Extraction. In phase 1 (steps (i) and (ii) in Figure 1), we construct a Whole-Classification network to represent the entire training set. To do so, we use the standard ResNet-12 as a common backbone used in many few-shot approaches for constructing the Whole-Classification network. Next, we train this network to classify the whole classes in the training set. Additionally, the knowledge distillation technique can be applied in order to improve the classification accuracy and generalization of the extracted features (Sun et al., 2019). Next, we define a set of few-shot training tasks (i.e.source tasks) and a target task with the number of classes equals to the number of labels in the test data. Using the encoder of the trained Whole-Classification network, we extract the embedded features and compute the mean of each label.
Algorithm 1: Few-Shot Learning with Task Affinity Score Data: (Xtrain, ytrain, ntrain), ({Xsupporttest ∪X query test }, ytest, ntest) Input: The Whole-Classification network Nθ Output: Few-shot classifier model fθ∗
1 Function mTAS(Xa, Ca, Xb, Cb, Nθa): 2 Obtain the mapping order: mapping = MaximumMatching(Ca, Cb) 3 Fine-tune Nθa using Xa with mapped labels (building the ε-approximation network) 4 Compute Fa,a, Fa,b using Nθa with Xa, Xb, respectively 5 return s[a, b] = 1√ 2 ∥∥∥F 1/2a,a − F 1/2a,b ∥∥∥ F
6 Function Main: 7 Train Nθ with the entire ntrain labels in Xtrain . Beginning of phase 1 8 Construct S source tasks, where each has ntest labels from Xtrain 9 Construct target task using ntest labels in X support test
10 Extract set Csource of class centroids for each source task using the encoder fθ of Nθ 11 Extract set Ctarget of class centroids for the target task using the encoder fθ of Nθ
. Beginning of phase 2
12 for i = 1, 2, . . . , S do 13 si = mTAS(Xsourcei , Csourcei , X support test , Ctarget, Nθ) 14 return closest tasks: i∗ = argmin i si 15 Define set L which consists of labels from closest tasks . Beginning of phase 3 16 Define a subset data Xrelated = {Xtrain|ytrain ∈ L} 17 Construct M -way K-shot base tasks and fine-tune fθ episodically using Xrelated
2. Task Affinity. Using the computed mean of the feature vectors from the previous phase, phase 2 (steps (iii), (iv) and (v) in Figure 1) identifies the closest source tasks to the target task by applying the TAS and a pre-process step called matching labels.
3. Episodic Fine-tuning. After obtaining the closest source tasks, we construct a training dataset called related-training set, consisting of samples only from the labels in the closest source tasks. In phase 3 (step (vi) in Figure 1), we follow the standard meta-learning approach by constructing the M -way K-shot base tasks from the related-training set to episodically fine-tune the classifier model. Since the classifier model is fine-tuned only with the labels of the related-training set, the complexity of training of the few-shot model is reduced; hence, the overall performance of the few-shot classification increases.

heading: 4.1 PHASE 1 - TRAINING WHOLE-CLASSIFICATION NETWORK AND FEATURE EXTRACTION
text: Recent few-shot learning approaches (e.g., Chen et al. (2021); Tian et al. (2020)) have shown advantages of a pre-trained Whole-Classification network on the entire training dataset. In this paper, we train a classifier network, Nθ using the standard architecture of ResNet-12 with the entire training classes. The Whole-Classification network Nθ can be described as concatenation of the encoder fθ and the last fully-connected layer (illustrated in Figure 1(i)). Since Nθ is trained on the entire training set Xtrain, it can extract meaningful hidden features for the data samples in the training set. Next, we construct a target task using ntest classes and its corresponding data points in the support set of the test data (i.e., Xsupporttest ). We also construct a set of S few-shot source tasks using the training set, Xtrain, where each task has ntest labels sampled from ntrain classes of the training set. This results in a set of source tasks with their corresponding training data, i.e., (Tsourcei , Xsourcei) for i = 1, 2 . . . , S. Using the encoder part of Nθ denoted by fθ, we extract the feature centroids from Xsourcei and X support test . Finally, we compute the mean (or centroid) of the extracted features for every class in Xsourcei of the source task Tsourcei , and similarly for X support test of the target task.
That is, we compute 1|Xc| ∑ x∈Xc fθ(x), whereXc denotes the set of data samples belonging to class c in either source tasks, or the target task. In phase 2, we use the computed centroids to find the best way to match the classes in source tasks to the target task.

heading: 4.2 PHASE 2 - TASK AFFINITY
text: In this phase, our goal is to find the most related source task(s) in the training set to the few-shot target task in the test set. To do this end, we apply the proposed task affinity score. However, naively applying the TAS on the extracted centroids may result in finding a non-related source task(s) to the target task. This is because neural networks are not invariant to the label’s permutation (Zhang et al., 2021). For instance, consider task I of classifying cat images as 0 and dog images as 1 and consider the ε-approximation network NθI with zero-error (i.e., ε = 0). Also, let task J be defined as the classification of the dog images encoded as 0 and cat images as 1. Assume that the dataset used for both tasks I and J is the same. If we use NθI to predict the data from task J, the prediction accuracy will be zero. For human perception, these tasks are the same. However, the neural network NθI can only be a good approximation network for task I, and not for task J. A naive approach to overcome this issue is to try all permutations of labels. However, it is not a practical approach, due to the intense computation requirement. As a result, we propose a method of pre-processing the labels in the source tasks to make the task affinity score invariant to the permutation of labels.

heading: 4.2.1 MAXIMUM BIPARTITE MATCHING
text: We use the Maximum Bipartite Graph Matching algorithm to match each set of ntest centroids of source tasks to the ones in the target task based on the Euclidean distance from each centroid to another. The goal is to find a matching order so that the total distance between all pairs of centroids to be minimized. We apply the Hungarian maximum matching algorithm (Kuhn, 1955), as shown in Figure 1(iii). The result of this algorithm is the way to match labels in the source tasks to the classes in the target task. After the matching, we modify the labels of the source tasks according to the matching result and use them to construct an ε-approximation network Nθ′ for the source task, as marked (iv) in Figure 1. Please note that the weights are fine-tuned using the modified matched labels; hence, we use θ′ instead of θ for the parameters of the ε-approximation network.

heading: 4.2.2 TASK AFFINITY SCORE
text: Now, we can find the closest source tasks to the target task. To do so, for each source task, we compute two Fisher Information matrices (Figure 1(v)) by passing the source tasks’ and target task’s datasets through the ε-approximation network Nθ′ , and compute the task affinity score defined in the equation (4) between two tasks. Since we use the matched labels of source tasks w.r.t. the target task, the resulted TAS is consistent and invariant to the permutation of labels. The helper function mTAS() in the Algorithm 1 implements all the steps in the second phase. Finally, the top-R scores and their corresponding classes are selected. These classes and their corresponding data points are considered as the closest source task(s) to the target task. Next, we show that our definition of the task affinity score is mathematically well-defined under some assumptions. First, from the equation (4), it is clear that the TAS of a task from itself always equals zero. Now assume that the objective function corresponding to the ε-approximation network is strongly convex. In the Theorem 1, we show that the TAS from task A to task B calculated using the Fisher Information matrix of the approximation network of task A on different epochs of the SGD algorithm converges to a constant value given by the TAS between the above tasks when the Fisher Information matrix is computed on the global optimum of the approximation network1.
Theorem 1. Let XA be the dataset for the task TA with the objective function L, and XB be the dataset for the task TB . Assume XA and XB have the same distribution. Consider an εapproximation network Nθ for the pair task-dataset (TA, XA) with the objective functions L and with the SGD algorithm to result weights θt at time t. Assume that the function L is strongly convex, and its 3rd-order continuous derivative exists and bounded. Let the noisy gradient function in training Nθ network using SGD algorithm be given by: g(θt, t) = ∇L(θt) + t, where θt is the estimation of the weights for network N at time t, and ∇L(θt) is the true gradient at θt. Assume that t satisfies E[ t| 0, ..., t−1] = 0, and satisfies s = lim t−→∞ ∣∣∣∣[ t tT | 0, . . . , t−1]∣∣∣∣∞ <∞ almost surely (a.s.). Then the task affinity score between TA and TB computed on the average of estimated
1As mentioned in the Theorem 1, we assume that loss function of the approximation network is strongly convex; hence, it has a global optimum.
weights up to the current time t converges to a constant as t→∞. That is,
st = 1√ 2 ∥∥∥F̄A1/2t − F̄B1/2t ∥∥∥ F D−→ 1√ 2 ∥∥∥F ∗A1/2 − F ∗B1/2∥∥∥ F , (5)
where F̄At = F (θ̄t, X query A ), F̄Bt = F (θ̄t, X support B ) with θ̄t = 1 t ∑ t θt. Moreover, F ∗ A = F (θ∗, XqueryA ) and F ∗ B = F (θ
∗, XsupportB ) denote the Fisher Information matrices computed using the optimum approximation network (i.e., a network with the global minimum weights, θ∗).
To prove Theorem 1 (please see the appendix for the complete proof), we use the Polyak & Juditsky (1992) theorem for the convergence of the SGD algorithm for strongly convex functions. Although the loss function in a deep neural network is not strongly convex, establishing the fact that the TAS is mathematically well-defined for this case is an important step towards the more general deep neural networks and a justification for the success of our empirical observations. Furthermore, some recent works try to generalize Polyak & Juditsky (1992) theorem for the convex or even some non-convex functions in an (non)-asymptotic way (Gadat & Panloup, 2017). However, we do not pursue these versions here.

heading: 4.3 PHASE 3 - EPISODIC FINE-TUNING
text: After obtaining the closest source tasks, we construct a training dataset called related-training set, consisting of samples only from the labels in the closest source tasks. Following the standard metalearning approach, we consider various M -way K-shot base tasks from the related-training dataset, we fine-tune the encoder fθ from the original Whole-Classification network in phase 1. To be more precise, we extract the feature vectors from data samples in the support set and the query set of the base task(s). The embedded features from the support set serve as the training data for the k-NN classifier. We utilize the k-NN model to predict the labels for the data samples in the query set of the base task under consideration using their feature vectors. Finally, the cross-entropy loss is used to update the encoder fθ by comparing the predicting labels and the labels of the query set, and backpropagating the error to the model fθ. Then this process can be repeated for several base tasks until fθ achieves a high accuracy2. Figure 1(vi) shows the above process for the jth base task.

heading: 5 EXPERIMENTAL STUDY
text: In this section, we present our experimental results in various few-shot learning benchmarks, including miniImageNet (Vinyals et al., 2016), tieredImageNet (Ren et al., 2018), CIFAR-FS (Bertinetto et al., 2018), and FC-100 (Oreshkin et al., 2018) 3. The miniImageNet dataset consists of 100 classes, sampled from ImageNet (Russakovsky et al., 2015), and randomly split into 64, 16, and 20 classes for training, validation, and testing, respectively. Similarly, the tieredImageNet dataset is also a derivative of ImageNet, containing a total of 608 classes from 34 categories. It is split into 20, 6, and 8 categories (or 351, 97, and 160 classes) for training, validation, and testing, respectively. Each class, in both miniImageNet and tieredImageNet, includes 600 colorful images of size 84×84. We use the architecture of ResNet-12 as the Whole-Classification network, which consists of 4 residual blocks, each block has 3 convolutional layers and a max-pooling layer. There are different variations of ResNet-12 in the literature, each with different size of parameters (e.g., [64, 128, 256, 512], [64, 160, 320, 640]). In our experiments, we report the number of parameters for all the models we use and for those ones compare with. For training the Whole-Classification network, the SGD optimizer is applied with the momentum of 0.9, and the learning rate is initialized at 0.05 with the decay factor of 0.1 for all experiments. In miniImageNet experiment, we train the model for 100 epochs with a batch size of 64, and the learning rate decaying at epoch 90. For tieredImageNet, we train for 120 epochs with a batch size of 64, and the learning rate decaying two times at epochs 40 and 80.
For miniImageNet, we define S = 2000 source tasks by randomly drawing samples from 20 labels (number of labels of the target task) out of 64 training labels from the whole training set. Next, we use the Whole-Classification network to extract the feature vectors from S source tasks, and match them with labels of the target task. Next, we construct the ε-approximation network using the
2The final fine-tuned few-shot model is denoted by fθ∗ in the Algorithm 1. 3Due to page limits, we discuss the experiments on CIFAR-FS and FC-100 in the appendix.
encoder fθ of the Whole-Classification network, and use it to compute the TAS in the task affinity phase. The distribution of the TAS found from the 2000 generated source tasks in the miniImageNet is shown in Figure 2a. As we can seen, the probability distribution of the task affinity is not a non-informative or uniform distribution. Only a few source tasks, with particular sets of labels, can achieve the small TAS and are considered as the related tasks. Now, we plot the frequency of all 64 labels in the training set which exist in the top-8 closest source tasks in Figure 2b. This shows that the class with the label 6 has 8 samples in the top-8 closest sources task, and this class is the most relevant one to the labels in the target task. Moreover, there are only 49 unique classes that construct the top-8 closest source tasks. This means that there are some classes which do not have any samples among the top-8 closest sources tasks. These labels are the ones with the least similarity to the labels in target task. Similarly, we define S = 1000 source tasks in tieredImageNet by randomly drawing samples from 160 labels out of entire 351 training labels. The distribution of the TAS from these 1000 generated source tasks is shown in Figure 2c. Similar to the miniImageNet case, Figure 2d illustrates the frequency of the 351 training classes in the top-6 closest source tasks. Among 351 training classes, there are only 293 unique classes that construct the top-6 closest source tasks.
In the episodic fine-tuning phase, we use the SGD optimizer with momentum 0.9, and the learning rate is set to 0.001. The batch size is set to 4, where each batch of data includes 4 few-shot tasks. The loss is defined as the average loss among few-shot tasks. After we trained our few-shot model, we tested it on the query sets of test tasks. Table 1 and Table 2 show the performance of our approach in 5-way 1-shot and 5-way 5-shot on miniImageNet and tieredImageNet datasets, respectively. In both cases, our approach with the standard ResNet-12 is comparable to or better than IE-distill (Rizve et al., 2021), while outperforming RFS-distill (Tian et al., 2020), EPNet (Rodrı́guez et al., 2020) and other methods with a significantly smaller classifier model in terms of the number of parameters. Note that, EPNet (Rodrı́guez et al., 2020) and IE-distill (Rizve et al., 2021) also utilize the data augmentation during pre-training for better feature extraction.

heading: 6 CONCLUSIONS
text: A task affinity score, which is non-commutative and invariant to the permutation of labels is introduced in this paper. The application of this affinity score in the few-shot learning is investigated. In particular, the task affinity score is applied to identify the related training classes, which are used for episodically fine-tuning a few-shot model. This approach helps to improve the performance of the few-shot classifier on various benchmarks. Overall, the task affinity score shows the importance of selecting the relevant data for training the neural networks with limited data and can be applied to other applications in machine learning.

heading: ACKNOWLEDGMENTS
text: This work was supported in part by the Army Research Office grant No. W911NF-15-1-0479.

heading: A APPENDIX
text: Here, we fist present the proof of the Theorem 1, and then we provide more experimental results on CIFAR-FS and FC-100 datasets. Additionally, we present the ablation study to show the efficacy of our proposed task affinity score. Moreover, we also discuss about the computation complexity of our approach, and the future works.
A.1 PROOF OF THEOREM 1
In the proof of Theorem 1, we invoke the Polyak & Juditsky (1992) theorem on the convergence of the average sequence of estimation in different epochs from the SGD algorithm. Since the original form of this theorem has focused on the strongly convex functions, we have assumed that the objective function in the training of the approximation network is strongly convex. However, there are some recent works that try to generalize Polyak & Juditsky (1992) theorem for the convex or even some non-convex functions in an (non)-asymptotic way Gadat & Panloup (2017). Here, we apply only on the asymptotic version of the theorem proposed originally by Polyak & Juditsky (1992). We first recall the definition of the strongly convex function. Definition 4 (Strongly Convex Function). A differentiable function f : Rn → R is strongly convex if for all x, y ∈ Rn and some µ > 0, f satisfies the following inequality:
f(y) ≥ f(x) +∇(f)T (y − x) + µ||y − x||22. (6)
Theorem 1. Let XA be the dataset for the task TA with the objective function L, and XB be the dataset for the task TB . Assume XA and XB have the same distribution. Consider an εapproximation network Nθ for the pair task-dataset (TA, XA) with the objective functions L and with the SGD algorithm to result weights θt at time t. Assume that the function L is strongly convex, and its 3rd-order continuous derivative exists and bounded. Let the noisy gradient function in training Nθ network using SGD algorithm be given by: g(θt, t) = ∇L(θt) + t, where θt is the estimation of the weights for network N at time t, and ∇L(θt) is the true gradient at θt. Assume that t satisfies E[ t| 0, ..., t−1] = 0, and satisfies s = lim t−→∞ ∣∣∣∣[ t tT | 0, . . . , t−1]∣∣∣∣∞ <∞ almost surely (a.s.). Then the task affinity score between TA and TB computed on the average of estimated weights up to the current time t converges to a constant as t→∞. That is,
st = 1√ 2 ∥∥∥F̄A1/2t − F̄B1/2t ∥∥∥ F D−→ 1√ 2 ∥∥∥F ∗A1/2 − F ∗B1/2∥∥∥ F , (7)
where F̄At = F (θ̄t, X query A ), F̄Bt = F (θ̄t, X support B ) with θ̄t = 1 t ∑ t θt. Moreover, F ∗ A = F (θ∗, XqueryA ) and F ∗ B = F (θ
∗, XsupportB ) denote the Fisher Information matrices computed using the optimum approximation network (i.e., a network with the global minimum weights, θ∗).
Proof of Theorem 1. Consider task TA as the source task and task TB as the target task. Let θt be the set of weights at time t from the ε-approximation network N trained using dataset
XsupportA with the objective functions L. Since the objective function L is strongly convex, the set of weights θ will obtain the optimum solutions θ∗ after training a certain number of epochs with stochastic gradient descend. By the assumption on the conditional mean of the noisy gradient function and the assumption on S, the conditional covariance matrix is finite as well, i.e., C = limt−→∞ E[ t tT | 0, . . . , t−1] <∞; hence, we can invoke the following result due to Polyak et al. Polyak & Juditsky (1992):
√ t(θ̄t − θ∗) D−→ N ( 0,H ( L(θ∗) )−1 CHT ( L(θ∗) )−1) , (8)
as t −→ ∞. Here, H is Hessian matrix, θ∗ is the global minimum of the loss function, and θ̄t = 1 t ∑ t θt. In other words, for the network N , √ t(θ̄t − θ∗) is asymptotically normal random vector:
√ t(θ̄t − θ∗) D−→ N (0,Σ), (9)
where Σ = H ( L(θ∗) )−1 CHT ( L(θ∗) )−1 . For a given dataset X , the Fisher Information FX(θ) is a continuous and differentiable function of θ, and it is also a positive definite matrix; thus, FX(θ)1/2 is well-defined. Now, by applying the Delta method to Equation (9) with dataset XA of task TA, we have:
(F̄ 1/2 At − F ∗ A 1/2)
D−→ N ( 0, 1 t ΣA ) , (10)
where F̄At = FXA(θ̄t), F̄ ∗ A = FXA(θ ∗), and the covariance matrix is given by ΣA =
Jθ
( vec ( FXA(θ ∗)1/2 )) ΣJθ ( vec ( FXA(θ ∗)1/2 ))T . Here, vec() is the vectorization operator, θ∗ is a n× 1 vector of the optimum parameters, FXA(θ∗) is a n× n Matrix evaluated at the minimum using dataset XA, and Jθ(vec(FXA(θ
∗)1/2)) is a n2 × n Jacobian matrix of the Fisher Information Matrix. Likewise, from Equation (9) with dataset XB of task TB , we have:
(F̄ 1/2 Bt − F ∗ B 1/2)
D−→ N ( 0, 1 t ΣB ) , (11)
where F̄Bt = FXB (θ̄t), F̄ ∗ B = FXB (θ ∗), and the covariance matrix is given by ΣB =
Jθ
( vec ( FXB (θ ∗ B) 1/2 )) Jθ ( vec ( FXB (θ ∗ B) 1/2 ))T . From Equation (10) and (11), we obtain:
(F̄ 1/2 At − F̄ 1/2 Bt )
D−→ N ( µ, V ) , (12)
where µ = (F ∗A 1/2 − F ∗B 1/2) and V = 1t (ΣA + ΣB). Since (F̄ 1/2 At − F̄ 1/2 Bt )− (F ∗A 1/2 − F ∗B 1/2) is asymptotically normal with the covariance goes to zero as t approaches infinity, all of the entries go to zero, we conclude that:
st = 1√ 2 ∥∥∥F̄ 1/2At − F̄ 1/2Bt ∥∥∥ F D−→ 1√ 2 ∥∥∥F ∗A1/2 − F ∗B1/2∥∥∥ F . (13)
A.2 EXPERIMENTS ON CIFAR-FS AND FC-100
Here, we conduct the experiments on the CIFAR-FS and the FC-100 datasets. The CIFAR-FS dataset (Bertinetto et al., 2018) is derived from the original CIFAR-100 dataset (Krizhevsky et al., 2009) by splitting 100 classes into 64 training classes, 16 validation classes, and 20 testing classes. The FC-100 dataset (Oreshkin et al., 2018) is also a subset of the CIFAR-100 and consists of 60 training classes, 20 validation classes, and 20 testing classes. The size of data sample in both of these datasets is 32× 32. Similar to previous experiments on miniImageNet and tieredImageNet, we train the ResNet-12 for 100 epochs with batch size of 64, and the learning rate decaying at epoch 60. Next, we compare our proposed few-shot approach with other state-of-the-art methods on CIFAR-FS and FC-100 datasets. The results in Table 3, and Table 4 indicates the competitiveness of our method in both datasets. Our approach with standard ResNet-12 is comparable to IE-distill (Rizve et al., 2021) and outperforms RFS-distill (Tian et al., 2020) while having a significantly smaller classifier model in term of the number of parameters.
A.3 ABLATION STUDY
First, we show the stability of the TAS by applying our distance on various classification tasks in CIFAR-10, CIFAR-100, ImageNet datasets using ResNet-18, and VGG-16 as the backbone for the ε-approximation networks. For each dataset, we define 4 classification tasks, all of which are variations of the full class classification task. For each task, we consider a balanced training dataset. That is, except for the classification tasks with all the labels, only a subset of the original training dataset is used such that the number of training samples across all the class labels to be equal. Additionally, we use 3 different ε values for the ε-approximation networks, ranging from 0.2 (good) to 0.6 (bad). To make sure that our results are statistically significant, we run our experiments 10 times with each of the ε-approximation networks being initialized with a different random seed each time and report the mean and the standard deviation of the computed distance.
In CIFAR-10, we define 4 tasks as follow:
• Task 0 is a binary classification of indicating 3 objects: automobile, cat, ship (i.e., the goal is to decide if the given input image consists of one of these three objects or not).
• Task 1 is a binary classification of indicating 3 objects: cat, ship, truck. • Task 2 is a 4-class classification with labels bird, frog, horse, and anything else. • Task 3 is the standard 10 objects classification.
In Figure 3, the mean and standard deviation of the TAS between CIFAR-10 tasks over 10 trial runs, using 3 different ε values for the ResNet-18 approximation networks. For ε = 0.2, the approximation network’s performance on the corresponding task’s test data is at least 80% and it is considered to be a good representation. As shown in Figure 3(a), the standard deviation of TAS is relatively
small and the TAS is stable (or consistent) regardless of the network’s initialization. Thus, we can easily identify the closest tasks to target tasks. The result for ε = 0.4, shown in Figure 3(b), the order of tasks remains the same for most cases, however, the standard deviations are much larger than the previous case. Lastly, Figure 3(c) shows the results for ε = 0.6. In this setup, TAS between tasks fluctuates widely and it is considered to be unreliable. Consequently, if the TAS between a pair of tasks is computed only once, the order of the closest tasks to the target task would easily be incorrect. Similarly, we conduct the experiment in CIFAR-10 using VGG-16 as the backbone. In Figure 4, we observe similar trend as the approximation network with smaller ε value will obtain the more stable and consistent task distances.
In CIFAR-100, which consisting of 100 objects equally distributed in 20 sub-classes, each sub-class has 5 object, we define 4 tasks as follow:
• Task 0 is a binary classification of detecting an object that belongs to vehicles 1 and 2 subclasses or not (i.e., the goal is to decide if the given input image consists of one of these 10 vehicles or not).
• Task 1 is a binary classification of detecting an object that belongs to household furniture and household devices or not.
• Task 2 is a multi-classification with 11 labels defined on vehicles 1, vehicles 2, and anything else.
• Task 3 is a multi-classification with the 21-labels in vehicles 1, vehicles 2, household furniture, household devices, and anything else.
In Figure 5, the mean and standard deviation of the TAS between CIFAR-100 tasks over 10 trial runs, using 3 different ε values for the ResNet-18 approximation networks. For ε = 0.2, the approximation network’s performance on the corresponding task’s test data is at least 80% and it is considered to be a good representation. As shown in Figure 5(a), TAS is stable regardless of the network initialization. As ε increases from 0.2 to 0.6, we observe the significant rise in standard deviation. For ε = 0.6, the TAS results are widely fluctuating and unreliable. In particular, consider Task 0 as the incoming task, and Task 1, 2, 3 are the base tasks. From the approximation network ε = 0.2 in Figure 5(a), the closest task to Task 0 is Task 2. However, the approximation network
ε = 0.6 in Figure 5(c) identifies Task 1 as the closest task of Task 0. Thus, in order to achieve a meaningful TAS between tasks, we first need to make sure that we represent the tasks correctly by the approximation networks. If the approximation network is not good in term of performance (i.e., ε is large), then, that network is not a good representation for the task. Similarly, we conduct the experiment in CIFAR-100 using VGG-16 as the backbone. In Figure 6, we observe similar trend as the approximation network with smaller ε value will obtain the more stable and consistent task distances.
In ImageNet, we define four 10-class classification tasks in ImageNet dataset. For each class, we consider 800 for training and 200 for the test samples. The list of 10 classes for each task is described below:
• Task 0 includes tench, English springer, cassette player, chain saw, church, French horn, garbage truck, gas pump, golf ball, parachute.
• Task 1 is similar to Task 0; however, instead of 3 labels of tench, golf ball, and parachute, it has samples from the grey whale, volleyball, umbrella classes.
• In Task 2, we also replace 5 labels of grey whale, cassette player, chain saw, volleyball, umbrella in Task 0 with another 5 labels given by platypus, laptop, lawnmower, baseball, cowboy hat.
• Task 3 includes analog clock, candle, sweatshirt, birdhouse, ping-pong ball, hotdog, pizza, school bus, iPod, beaver.
In Figure 7 and Figure 8, we demonstrate the mean and standard deviation of the TAS between 4 ImageNet tasks over 10 runs using ResNet-18 and VGG-16 as the backbone. For each backbone, we conduct 3 different ε values and report results as the above experiments. Similar to the CIFAR-10 and CIFAR-100, we observe that the approximation network with better performance (or smaller ε value) will results more stable TAS. Additionally, regardless of the architecture backbone, the trend of distance between these tasks is consistent across all experiments.
Next, we want to analyze the effectiveness of our approach of choosing the most related data classes by performing several few-shot learning experiments with different number of related classes. Ad-
ditionally, we conduct the few-shot experiment with non-related classes and randomized classes to show the efficacy of our proposed method. Table 5 shows the performances of our proposed fewshot method with different settings. We achieve the best performance with 49 related tasks in both 5-way 1-shot and 5-way 5-shot classification. We observe a drop in performance when the number
of related classes increases to 54 classes. As we reduce the number of related classes from 49 to 32 classes, the overall performance of our model reduces significantly in both 1-shot and 5-shot. As the result, selecting the optimal number of relevant classes is crucial to the overall performance of our few-shot approach. Additionally, we observe a drop in performance when the model utilizing 29 non-related classes as well as 32 random classes. Therefore, we show that using a relevant classes can boost the performance of the few-shot model. Moreover, we conduct the similar analysis for the tieredImageNet dataset, in which the results are shown in Table 6. Here, we observe the same trend as in previous experiments. Briefly, by selecting the relevant classes, we consistently achieve higher performances when compare with selecting non-relevant or randomized classes.
A.4 COMPUTATION COMPLEXITY
Below are the complexity of 3 phases in our approach:
• Phase 1 consists of 2 operations: (i) Train Whole-Classification net. (ii) Feature extraction. These 2 operations is executed only once, and the complexity is constant.
• Phase 2 consists of 3 operations: (iii) Matching labels (iv) Constructing approx. net. (v) Fisher Information matrix. The operation (iii) is based on the Hungarian algorithm and the complexity is O(n3), where n is the number of tasks. For each base task, (iv) is done once, and the complexity of finding FIM in (v) is linear with respect to the number of parameters due to the fact that we only consider the diagonal entries of the matrix. Note that all the tasks are few-shot and only consists of few data samples. These operations can be effectively implemented in GPU.
• Phase 3 is (vi) Episodic fine-tuning, which is often used in few-shot approach [R3, R4]. Here, we use the k-NN as the clustering algorithm. The complexity of k-NN is linear with respect to the number of samples.
A.5 FUTURE WORKS
In this paper, we propose a novel task similarity measure that inherently asymmetric and invariant to label permutation, called Task Affinity Score (TAS). Next, we introduce the TAS measure to the
few-shot learning approach and achieve significant improvements over the current state-of-the-art methods. In future work, we would like to extend the applications of TAS to other few-shot learning frameworks, and also to other meta-learning areas, e.g., multi-task learning, continual learning. Additionally, we wish to establish theoretical justification for the TAS measure in convex or nonconvex cases.

Review summaries:
The authors propose a task affinity score based on maximum bipartite matching algorithm and Fisher information matrix. And then utilize this score to find the closest training data labels to the test data and leverage the discovered relevant data for episodically fine-tuning the few-shot model. Experimental results on few-shot learning setting achieve the state-of-the-art performance on four widely-used benchmarks.

This paper presents a new affinity score based on the Fisher Information matrix from a source to a target task. The authors also develop a few-shot learning procedure based on a pre-trained Whole-Classification network approach. In this procedure, training labels are matched via a maximum matching algorithm, and the target task for training is selected using the proposed affinity score. The effectiveness of the proposed score is demonstrated using benchmark datasets in the problem of few-shot learning.

This paper proposes a few shot learning method, which tries to measure the affinity degree between different tasks. Based on the affinity score, the relevant tasks are exploited for training to boost the performance of target tasks. The Task Affinity Score (TSA) is proposed, which is novel  to measure the dependency between different tasks. The reasonability of TSA is also validated with mathematical proof.