Prototype Propagation Networks (PPN) for Weakly-supervised Few-shot Learning on Category Graph

1 Introduction

Machine learning (ML) has achieved breakthrough success in a great number of application fields during the past 10 years, due to more expressive model structures, the availability of massive training data, and fast upgrading of computational hardware/infrastructure. Nowadays, with the support of expensive hardware, we can train super-powerful deep neural networks containing thousands of layers on millions or even trillions of data within an acceptable time. However, as AI becomes democratized for personal or small business use, with concerns about data privacy, demand is rapidly growing for instant learning of highly customized models on edge/mobile devices with limited data. This brings new challenges since the big data and computational power that major ML techniques rely on are no longer available or affordable. In such cases, ML systems that can quickly adapt to new tasks and produce reliable models by only seeing few-shot training data are highly preferable.

This few-shot learning problem can be addressed by a class of approaches called "meta-learning". Instead of independently learning each task from scratch, the goal of metalearning is to learn the common knowledge shared across different tasks, or "learning to learn". The knowledge is at learning/algorithm-level and is task-independent, and thus can be applied to new unseen tasks. For example, it can be shared initialization weights [Finn et al., 2017], an optimization algorithm [Ravi and Larochelle, 2017], a distance/similarity metric [Vinyals et al., 2016], or a generator of prototypes [Snell et al., 2017] that compose the support set of the K-nearest neighbor (KNN) predictor. Therefore, new tasks can benefit from the accumulated meta-knowledge extracted from previous tasks. In contrast to single-task learning, the "training data" in meta-learning are tasks, i.e., tasks from a certain distribution are sampled across all possible tasks. It then tries to maximize the validation accuracy of these sampled tasks. Meta-learning shares ideas with life-long/continual/progressive learning in that the metaknowledge can be re-used and updated for future tasks. It generalizes multi-task learning [Caruana, 1997] since it can be applied to any new task drawn from the same distribution.

Although recent studies of meta-learning have shown its effectiveness on few-shot learning tasks, most of them do not leverage weakly-supervised information, which is usually free or cheap to collect, and has been proved to be helpful when training data is insufficient, e.g., in weakly-supervised [Zhou, 2017] and semi-supervised learning [Belkin et al., 2006; Zhu and Ghahramani, 2002]. In this paper, we show that weakly-supervised information can significantly improve the performance of meta-learning on fewshot classification. In particular, we leverage weakly-labeled data that are annotated by coarse-class labels, e.g., an image of a Tractor with a coarse label of Machine. These data are usually cheap and easy to collect from web tags or human annotators. We additionally assume that a category graph describing the relationship between fine classes and coarse classes is available, where each node represents a class and each directed edge connects a fine-class to its parent coarseclass. An example of a category graph is given in Figure 2. It is not necessary for the graph to cover all the possible relationships and graph containing partial relationship is usually easy to obtain, e.g., the ImageNet category tree built based on the synsets fromWordNet.

We propose a meta-learning model called prototype propagation network (PPN) to explore the above weaklysupervised information for few-shot classification tasks. PPN produces a prototype per class by propagating the prototype of each class to its child classes on the category graph, where an attention mechanism generates the edge weights used for propagation. The learning goal of PPN is to minimize the validation errors of a KNN classifier built on the propagated prototypes for few-shot classification tasks. The prototype propagation on the graph enables the classification error of data belonging to any class to be back-propagated to the prototype of another class, if there exists a path between the two classes. The classification error on weakly-labeled data can thus be back-propagated to improve the prototypes of other classes, which later contribute to the prototype of few-shot classes via prototype propagation. Therefore, the weaklylabeled data and coarse classes can directly contribute to the update of prototypes of few-shot fine classes, offsetting the lack of training data. The resulting graph of prototypes can be repeatedly used, updated and augmented on new tasks/classes as an episodic memory. Interestingly, this interplay between the prototype graph and the quick adaptation to new few-shot tasks (via KNN) is analogous to the complementary learning system that reconciles episodic memory with statistical learning inside the human hippocampus [Schapiro et al., 2017], which is believed to be critical for rapid learning.

Similar to other meta-learning methods, PPN learns from the training processes of different few-shot tasks, each defined on a subset of classes sampled from the category graph. To fully explore the weakly-labeled data, we develop a levelwise method to train tasks, generated by subgraph sampling, for both coarse and fine classes on the graph. In addition, we introduce two testing/inference settings that are common in different practical application scenarios: one (PPN+) is allowed to use weakly-labeled data in testing tasks and is given the edges connecting test classes to the category graph, while the other (PPN) cannot access any extra information except for the few-shot training data of the new tasks. In experiments, we extracted two benchmark datasets from ILSVRC12 (ImageNet) [Deng et al., 2009], specifically for weaklysupervised few-shot learning. In different test settings, our method consistently and significantly outperforms the three most recently proposed few-shot learning models and their variants, which also trained on weakly-labeled data. The prototypes learned by PPN is visualized in Figure 1. The code is available at: https://github.com/liulu112601/PPN.

2 RelatedWorks

A great number of meta-learning approaches have been proposed to address the few-shot learning problem. There are usually two main ideas behind these works: 1) learning a component of a KNN predictor applied to all the tasks, e.g., the support set [Snell et al., 2017], the distance metric [Vinyals et al., 2016], or both [Mishra et al., 2018]; 2) learning a component of an optimization algorithm used to train different tasks, e.g., an initialization point [Finn et al., 2017]. Another straightforward approach is to generate more training data for few-shot tasks by a data augmentation technique or generative model [Lake et al., 2015; Wong and Yuille, 2015]. Our method follows the idea of learning a small support set (prototypes) for KNN, and differs in that we leverage the weakly-labeled data by relating prototypes of different classes.

Auxiliary information: unlabeled data [Ren et al., 2018] and inter/intra-task relationship [Nichol and Schulman, 2018; Liu et al., 2019; Ravi and Beatson, 2019] have recently been used to improve the performance of few-shot learning. Cotraining on auxiliary tasks [Oreshkin et al., 2018] has also been applied to improve the learning of the similarity metric. In contrast, to the best of our knowledge, we are the first to utilize the weakly-labeled data as the auxiliary information to bring significant improvement.

The prototype propagation in our method inherits ideas from random walk, message passing, belief propagation, and label propagation [Wu et al., 2019; Zhou et al., 2017; Dong and Yang, 2019]. A similar idea has also been used in more recent graph neural networks (GNN) such as graph attention networks (GAT) [Veliˇckovi´c et al., 2018]. GNN are mainly designed for tasks on graph-structured data such as node classification [Hamilton et al., 2017], graph embedding [Yu et al., 2018], graph generation [Dai et al., 2018] and graph clustering [Wang et al., 2017]. Although our method uses an attention mechanism similar to GAT for propagation, we have a different training scheme (Algorithm 1) that only requires one-step propagation on a specific directed acyclic graph (DAG). GNN has been applied to meta-learning in [Garcia and Bruna, 2018], but the associated graph structure is defined on samples instead of classes/prototypes, and is handcrafted with fully connected edges.

3 Prototype Propagation Networks (PPN)

3.1 Weakly-Supervised Few-Shot Learning

In weakly-supervised few-shot learning, we learn from two types of data: the few-shot data X annotated by the target fine-class labels and the weakly-labeled data X w annotated by coarse-class labels. Each x ∈ X is associated with a fineclass label y ∈ Y, while each x ∈ X w is associated with a coarse-class label yw ∈ Y w . We assume that there exists a category graph describing the relationship between fine classes and coarse classes. This is a directed acyclic graph (DAG) G = (Y ∪ Y w ,E), where each node y ∈ Y ∪ Y w denotes a class, and each edge (or arc) z → y ∈ E connects a parent class z to one of its child classes y. An example of the category graph is given in Figure 2: the few-shot classes Y are the leaves of the graph, while the weakly-labeled classes Y w are the parents 1 or ancestors 2 of the few-shot classes; for example, the parent class of "Tractor" is "FarmMachine", while its ancestors include "FarmMachine" and "Machine". A child class can belong to multiple parent classes, e.g., the class "Organ" has two parent classes, "Wind Instrument" and "Keyboard Instrument".

We follow the setting of few-shot learning, which draws training tasks T ∼ T from a task distribution T and assumes that the test tasks are also drawn from the same distribution. For few-shot classification, each task T is defined by a subset of classes, e.g., an N-way k-shot task refers to classification over N classes and each class only has k training samples. It is necessary to sample the training classes and test classes from two disjoint sets of classes to avoid overlapping. In our problem, as shown by Figure 2, the few-shot classes used for training and test (colored light blue and deep blue respectively) are also non-overlapping, but we allow them to share some parents on the graph. We also allow training tasks to cover any classes on the graph. Since finer-class labels can provide more information about the targeted fewshot classes but are more expensive to obtain, we assume that the amount of weakly-labeled data is reduced exponentially when the class becomes finer. The training aims to solve the following risk minimization (or likelihood maximization) of "learning to learn":

where each task T is defined by a subset of classes Y T ⊆ Y ∪ Y w , DT is the distribution of data-label pair (x, y) with y ∈ Y T , Pr(y|x;w(T;Θ)) is the likelihood of (x, y) produced by model w(T;Θ) for task T, where Θ is the meta-learner parameter shared by all the tasks drawn from T .

1 Parents: directly connected coarse classes.

2 Ancestors: coarse classes not connected but linked via paths.

In our method, Pr(y|x;w(T;Θ)) is computed by a softversion of KNN, where w(T ; Θ) is the set of nearest neighbor candidates (i.e., the support set of KNN) for task T, and Θ defines the mechanism generating the support set. Similar to prototypical networks [Snell et al., 2017], the support set w(T;Θ) is composed of prototypes PY T ≜ {Py ∈ Rd : y ∈ Y T }, each of which is associated with a class y ∈ Y T . Given a data point x, we first compute its representation f(x) ∈ Rd , where f(·) is convolutional neural networks (CNN) with parameter Θcnn , then Pr(y|x;w(T;Θ)) = Pr(y|x;PY T ) is computed as:

In the following, we will introduce prototype propagation which generates PY T for any task T ∼ T . An overall of all procedures in our model is shown in Figure 3.

3.2 Prototype Propagation

In PPN, each training task T is a level-wise classification on a sampled subgraph Gi ⊆ G, i.e., a classification task over Y T = Y Gj i , where G j i denotes the level-j of subgraph Gi and Y Gj i is the set of all the classes on G j i .

The prototype propagation is defined on each subgraph Gi, which covers classes Y Gi . Given the associated training data X y for class y ∈ Y Gi , the prototype of the class y is initialized as the average of the representations f(x) of the samples x ∈ X y , i.e.,

For each parent class z of class y on Gi, we propagate P 0 z to class y with edge weight a(P 0 y ,P 0 z ) measuring the similarity between class y and z, and aggregate the propagation (the messages) from all the parent classes by

where P Gi y denotes the set of all parent classes of y on the subgraph Gi, and the edge weight a(P 0 y ,P 0 z ) is a learnable similarity metric defined by a dot-product attention [Vaswani et al., 2017], i.e.,

where g(·) and h(·) are learnable transformations applied to prototypes with parameters Θatt , e.g., linear transformations g(p) = Wgp and h(q) = Whq. The prototype after propagation is a weighted average of P 0 y and P + y with weight λ ∈ [0, 1], i.e.,

For each classification task T on subgraph Gi, Py is used in Eq. (2) to produce the likelihood probability. The likelihood maximization in Eq. (1) aims to optimize the parameters Θcnn from f(·) and Θatt from the attention mechanism across all the training tasks.

3.3 Level-wise Training of PPN on Subgraphs

The goal of meta-training is to learn a parameterized propagation mechanism defined by Eq. (3)-Eq. (6) on few-shot tasks. In each iteration, we randomly sample a subset of fewshot classes, which together with all their parent classes and edges on G form a subgraph Gi. A training task T is drawn from each level G j i ∼ Gi as the classification over classes Y T = Y Gj i . The meta-learning in Eq. (1) is approximated by

where DGj i is the data distribution of data-label pair (x, y) from classes Y Gj i . Since the prototype propagation is defined on the whole subgraph, it generates a computational graph relating each class to all of its parent classes. Hence, during training, the classification error on each class is backpropagated to the prototypes of its parent classes, which will be updated to improve the validation accuracy of finer classes and propagated to generate the prototypes of the few-shot classes later. Therefore, the weakly-labeled data of a coarse class will contribute to the few-shot learning tasks on the leafnode classes.

The complete level-wise training procedure of PPN is given in Algorithm 1, each of whose iterations comprises two main stages: prototype propagation (lines 9-11) which builds a computational graph over prototypes of the classes on a sampled subgraph Gi, and level-wise training (lines 1216) which updates the parameters Θcnn and Θatt on per-level classification task. In the prototype propagation stage, the prototype of each class is merged with the information from the prototypes of its parent classes, and the classification error

Algorithm 1 Level-wise training of PPN

Input: few-shot data X with labels fromY, weakly-labeled data X w with labels from Y w , category graph G = (Y ∪ Y w , E), learning rate scheduler for SGD, λ, m; 1: Initialize: randomly initialize P, Θcnn , Θatt , τ ← 0; 2: while not converge do 3: if τ mod m = 0 then 4: for class y ∈ Y ∪ Y w do 5: Lazily update P 0 y by Eq. (3) and save it in buffer; 6: end for 7: end if 8: Sample a subgraph Gi ∼ G; 9: for class y ∈ Y Gi do 10: Get P 0 y from buffer, and propagation by Eq. (4)-(6); 11: end for 12: initialize loss L ← 0; 13: for level-j G j i ∼ Gi do 14: L←L+ ∑ (x,y)∼DGj i - log Pr(y|x; PY Gj i ) by Eq. (2); 15: end for 16: Mini-batch SGD to minimize L, update Θcnn , Θatt ; 17: τ ← τ +1; 18: end while

using the merged prototypes will be backpropagated to update the parent prototypes during the level-wise training stage. To improve the computational efficiency, we do not update P 0 y for every propagation. Instead, we lazily update P 0 y for all classes y ∈ Y ∪ Y w every m epochs, as shown in lines 3-7.

3.4 Meta-Test: Apply PPN to New Tasks

We study two test settings for weakly-supervised few-shot learning, both of which will be used in the evaluation of PPN in our experiments. They differ in whether or not the weakly-supervised information, i.e., the weakly-labeled data and the connections of new classes to the category graph, is still accessible in the test tasks. The first setting (PPN+) is allowed to access this information within test tasks while the second setting (PPN) is unable to access the information. In other words, for PPN+, the edges (i.e., the yellow arrows in Figure 3) between each test class and any other classes are known during test phase, while these edges are unknown and needed to be predicted in the PPN setting. The second setting is more challenging but is preferred in a variety of applications, for example, where the test tasks happen on different devices, whereas the first setting is more appropriate for lifelong/continual learning on a single machine.

In the second setting, we can still leverage the prototypes achieved in the training phase and use them for the propagation of prototypes for test classes. In particular, for an unseen test class y (and its associated samples X y ), we find the Knearest neighbors of P 0 y among all the prototypes achieved during training, and treat the training classes associated with the K-nearest neighbor prototypes as the parents of y on G. These parent-class prototypes serve to provide weaklysupervised information to the test classes via propagation on the category graph.

In both settings, for each class y in a test task T, we apply the prototype propagation in Eq. (3)-(6) on a subgraph composed of y and its parents P G y . This produces the final prototype Py, which is one of the candidates for the nearest neighbors for PY T in KNN classification on task T. In the first setting (PPN+), the hierarchy covering both the training and test classes is known so the parent class of each test class y may come from either the training classes or the weaklylabeled test classes. When a parent class y′ ∈ P G y is among the training classes, we use the buffered prototype P 0 y′ from training for propagation; otherwise, we use Eq. (3) to compute P 0 y′ over weakly-labeled samples belonging to class y′ for this task. In the second setting (PPN), since the edges connecting test classes are unknown and are predicted by KNN as introduced in the last paragraph, we assume that all the parents of y are from training classes. We directly use the parents' buffered prototypes from training for propagation.

4 Experiments

We compare PPN/PPN+ to three baseline methods, i.e., Prototypical Networks, GNN and Closer Look [Chen et al., 2019], and their variants of using the same weakly-labeled data as PPN/PPN+. For their variants, we apply the same level-wise training on the same weakly-labeled data as in PPN/PPN+ to the original implementations, i.e., we replace the original training tasks with level-wise training tasks. We always tune the initial learning rate, the schedule of learning rate, and other hyperparameters of all the baselines and their variants on a validation set of tasks. The results are reported in Table 3 and Table 4, where the variants of baselines are marked by "*" following the baseline name.

In PPN/PPN+ and all the baseline methods (as well as their variants), we use the same backbone CNN (i.e., f(·; θcnn )) that has been used in most previous few-shot learning works [Snell et al., 2017; Finn et al., 2017; Vinyals et al., 2016]. It has 4 convolutional layers, each with 64 filters of 3 × 3 convolution, followed by batch normalization [Ioffe and Szegedy, 2015], ReLU nonlinearity, and 2 × 2 max-pooling. The transformation g(·) and h(·) in the attention module are fully connected linear layers.

In PPN/PPN+, the variance of P 0 y increases when the number of samples (i.e., the "shot") per class reduces. Hence, we set λ = 0 in Eq. (6) for N-way 1-shot classifications, and λ = 0.5 for N-way 5-shot classification. During training, we lazily update P 0 y for all the classes on the graph G every m = 5 epochs and choose the nearest K = 3 neighbours as parents among all prototypes gained after training for PPN. Adam [Kingma and Ba, 2015] is used to train the model for 150k iterations, with an initial learning rate of 10-3 , a weight decay of 10-4 , and a momentum of 0.9. We reduce the learning rate by a factor of 0.7× every 15k iterations starting from the 10k-th iterations.

4.1 WS-ImageNet-Pure

WS-ImageNet-Pure is a subset of ILSVRC-12. On the ImageNet WordNet Hierarchy, we extract 80% classes from level-7 as leaf nodes of the category graph G and use them as the targeted classes Y in few-shot tasks. The ancestor nodes of these classes on G are then sampled from level-6 to level-3, which compose weakly-labeled classes Y w . We sub-sample the data points for classes on G in a bottom-up manner: for any level-7 (bottom) level class y, we directly sample a subset from all the images belonging to y in ImageNet; for any class y on lower level-j with j < 7, we sample from all the images that belong to y and have not been sampled into its descendant classes. Hence, we know that any data point sampled into class y belongs to all the ancestor classes of y but we do not know its labels on any targeted class of y. In addition, we sample each candidate data point for any class on level j with probability 0.6j . Hence, the number of data points associated with each class thus reduces exponentially when the level of the class increases. This is consistent with many practical scenarios, i.e., samples with finer-class labels can provide more information about targeted few-shot tasks, but they are much more expensive to obtain and usually insufficient.

For training-test splitting of few-shot classes 3 , we divide the classes from level-7 into two disjoint subsets with ratio 4:1 (4 for training and 1 for test). This ensures that any class in any test task has never been learned in training tasks. However, we allow training classes and test classes to share some parent classes. The detailed statistics of WS-ImageNet-Pure are given in Table 3.

The experimental results of PPN/PPN+ and all the baselines (and their weakly-supervised variants ending with "*") on WS-ImageNet-Pure are shown in Table 3. PPN/PPN+ outperform all other methods. The table shows that PPN/PPN+ are more advantageous in 1-shot tasks, and that PPN+ achieves ∼ 15% improvement compared to other methods. This implies that the weakly-supervised information can be more helpful when supervised data is highly insufficient, and our method is able to significantly boost performance by exploring the weakly-labeled data. Although all the weaklysupervised variants of baselines are trained on the same data as PPN/PPN+, they do not achieve similar improvement because their model structures do not have such mechanisms as the prototype propagation in PPN which relates different classes and tasks. In addition, training on unrelated tasks can be distracting and even detrimental to performance. In contrast, PPN/PPN+ build a computational graph of prototypes associated with both coarse and fine classes, and the error on any class can be used to update the prototypes of other classes via backpropagation on the computational graph.

3 Each training task is classification defined on a randomly sampled subset of training classes, while each test task is classification defined on a randomly sampled subset of test classes.

4.2 WS-ImageNet-Mix

To verify if PPN can still learn from weakly-labeled data that belong to other fine classes not involved in the few-shot tasks, we propose another subset of ILSVRC-12, WS-ImageNetMix, whose detailed statistics are given in Table 2. We extract WS-ImageNet-Mix by following the same procedure as extracting WS-ImageNet-Pure except that: 1) data points sampled for a coarse (non-leaf) class can belong to the remaining ∼ 20% level-7 classes outside of the ∼ 80% level-7 classes used for generating few-shot tasks; and 2) for any class on level-j, we sample each data point with probability 0.7j instead of 0.6j .

The experimental results are reported in Table 4, which shows that PPN/PPN+ still outperform all baselines, and PPN+ outperforms them by ∼ 10% for 1-shot classification. This indicates that PPN/PPN+ is robust to (and might be able to leverage) weakly-labeled data unrelated to the final fewshot tasks.

4.3 Effects of Prototype Propagation

To study whether and how the propagation in Eq. (4) improves few-shot learning, we evaluate PPN using different λ in Eq. (6). Specifically, we try different weights 1-λ (x-axis in Figure 4) for P + y in Eq. (6) between [0, 0.9], and report the validation accuracy (y-axis in Figure 4) on test tasks for Nway1shot tasks and the two datasets. In all scenarios, increasing the weight of P + y in the given range consistently improves the accuracy (although the accuracy might drop if the weight gets too close to 1 though), which demonstrates the effectiveness of prototype propagation.

4.4 Time Cost

The average per-iteration time (in seconds) on a single TITAN XP for PPN/PPN+ and the baselines are listed as Table 5. PPN has moderate time cost comparing to other baselines. Compared to prototypical network, our propagation procedure only requires ∼10% extra time cost but significantly improves the performance.

5 Future Studies

In this work, we propose to explore weakly-labeled data by developing a propagation mechanism generating class prototypes to improve the performance of few-shot learning. Empirical studies verifies the advantage of exploring the weakly-labeled data and the effectiveness of the propagation mechanism. Our model can be extended to multi-steps propagation and assimilate more weakly-labeled information. The graph can be more general than a class hierarchy, and the node on the graph is not limited to be a class: it can be extended to any output attribute.

Acknowledgements

This research was funded by the Australian Government through the Australian Research Council (ARC) under grants 1) LP160100630 partnership with Australia Government Department of Health and 2) LP150100671 partnership with Australia Research Alliance for Children and Youth (ARACY) and Global Business College Australia (GBCA). We also acknowledge the support of NVIDIA Corporation and MakeMagic Australia with the donation of GPUs.