summaries: Learning to discover novel class is a very challenging task and a new research topic in recent years. In this task, a known-class dataset can be used to help cluster novel classes. “Novel” means that there are no overlaps between novel classes and known classes. This setting looks ill-defined since it is not clear why we need known classes to help cluster novel classes. However, this paper answers this question based on a novel concept: K-epsilon separation and points out when this setting is ill-defined/well-defined. Based on this contribution, this paper is above the acceptance borderline.   Nevertheless, the presentation should be polished. Although I understand the setting and the contribution in the end, the presentation flow is not smooth. Some typos make me struggle when I read this paper. Besides, the connection between sampling process and Assumption (D) should be discussed deeply. I find that they might not the same thing.   The paper introduces meta-discovery as a way to adapt meta-learning strategies to the problem of learning to discover novel classes. It also presents a formalization of the problem that helps shading light on the conditions under which it is learnable.  The authors additionally introduce a novel sampling strategy aimed at sampling data having the same "dominant" view to help the following clustering procedure.  The experimental evaluation shows advantages over existing recent competitors when the number of examples for unseen classes is small. This paper considers the problem of novel class discovery (NCD). Different from the original setting of NCD, this paper reconsiders the assumptions behind NCD and defines a new yet more practical setting, which can significantly reduce the number of unlabeled data needed for training novel classes. In addition, this paper presents a meta-learning-based approach to address the new setting, which achieves consistent improvements on four public datasets. They also provide a theory to reveal why we need to assume that known and novel classes should share semantic features. The authors provide a formal definition of the L2DNC task, give proofs of useful insight into the problem, and empirically demonstrate novel methods. The authors use several baselines and ablation to demonstrate the value of the proposed methods. The theoretical insights suggest that common high level features are necessary to solve the L2DNC task, which motivates the proposed approaches based on low dimensional non-linear projection of the data. Similarly the clustering-centric definition of the problem motivates the similarity learning methods presented.
abstractText: In learning to discover novel classes (L2DNC), we are given labeled data from seen classes and unlabeled data from unseen classes, and we train clustering models for the unseen classes. However, the implicit assumptions behind L2DNC are still unclear. In this paper, we demystify assumptions behind L2DNC and find that high-level semantic features should be shared among the seen and unseen classes. Based on this finding, L2DNC is theoretically solvable under certain assumptions and can be naturally linked to meta-learning that has exactly the same assumption as L2DNC. Thus, we can empirically solve the L2DNC problem by meta-learning algorithms after slight modifications. This meta-learning-based methodology significantly reduces the amount of unlabeled data needed for training and makes it more practical, as demonstrated in experiments. The use of very limited data is also justified by the application scenario of L2DNC: since it is unnatural to label only seen-class data, L2DNC is sampling instead of labeling in causality. Therefore, unseen-class data should be collected on the way of collecting seen-class data, which is why they are novel and first need to be clustered.
references.authors: Horace B Barlow
references.title: Unsupervised learning
references.venue: Neural computation,
references.authors: Avrim Blum Tom M. Mitchell
references.title: Combining labeled and unlabeled data with co-training
references.venue: In COLT,
references.authors: Jiaxin Chen Xiao-Ming Wu Yanke Li Qimai LI Li-Ming Zhan Fu-Lai Chung
references.title: A closer look at the training strategy for modern meta-learning
references.venue: NeurIPS,
references.authors: Xiaohan Chen Zhangyang Wang Siyu Tang Krikamol Muandet
references.title: MATE: plugging in model awareness to task embedding for meta learning
references.venue: NeurIPS,
references.authors: Jia Deng Wei Dong Richard Socher Li-Jia Li Kai Li Fei-Fei Li
references.title: Imagenet: A large-scale hierarchical image database
references.venue: In CVPR,
references.authors: Tongtong Fang Nan Lu Gang Niu Masashi Sugiyama
references.title: Rethinking importance weighting for deep learning under distribution shift
references.venue: In NeurIPS,
references.authors: Chelsea Finn Pieter Abbeel Sergey Levine
references.title: Model-agnostic meta-learning for fast adaptation of deep networks
references.venue: In ICML,
references.authors: Spyros Gidaris Praveer Singh Nikos Komodakis
references.title: Unsupervised representation learning by predicting image rotations
references.venue: In ICLR,
references.authors: Kai Han Andrea Vedaldi Andrew Zisserman
references.title: Learning to discover novel visual categories via deep transfer clustering
references.venue: In ICCV,
references.authors: Kai Han Sylvestre-Alvise Rebuffi Sébastien Ehrhardt Andrea Vedaldi Andrew Zisserman
references.title: Automatically discovering and learning new visual categories with ranking statistics
references.venue: In ICLR,
references.authors: Kaiming He Xiangyu Zhang Shaoqing Ren Jian Sun
references.title: Deep residual learning for image recognition
references.authors: Timothy Hospedales Antreas Antoniou Paul Micaelli Amos Storkey
references.title: Meta-learning in neural networks: A survey
references.authors: Yen-Chang Hsu Zhaoyang Lv Zsolt Kira
references.title: Learning to cluster in order to transfer across domains and tasks
references.venue: In ICLR,
references.authors: Yen-Chang Hsu Zhaoyang Lv Joel Schlosser Phillip Odom Zsolt Kira
references.title: Multi-class classification without multi-class labels
references.venue: In ICLR,
references.authors: Sergey Ioffe Christian Szegedy
references.title: Batch normalization: Accelerating deep network training by reducing internal covariate shift
references.venue: In ICML,
references.authors: Yongcheng Jing Xiao Liu Yukang Ding Xinchao Wang Errui Ding Mingli Song Shilei Wen
references.title: Dynamic instance normalization for arbitrary style transfer
references.venue: In AAAI,
references.authors: Diederik P. Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In ICLR,
references.authors: Alex Krizhevsky Geoffrey Hinton
references.title: Learning multiple layers of features from tiny images
references.authors: Brenden M Lake Ruslan Salakhutdinov Joshua B Tenenbaum
references.title: Human-level concept learning through probabilistic program induction
references.authors: Aoxue Li Tiange Luo Tao Xiang Weiran Huang Liwei Wang
references.title: Few-shot learning with global class representations
references.venue: In ICCV,
references.authors: Yingming Li Ming Yang Zhongfei Zhang
references.title: A survey of multi-view representation learning
references.venue: IEEE Transactions on Knowledge and Data Engineering,
references.authors: Chenghao Liu Zhihao Wang Doyen Sahoo Yuan Fang Kun Zhang Steven C.H. Hoi
references.title: Adaptive task sampling for meta-learning
references.venue: In ECCV,
references.authors: Feng Liu Wenkai Xu Jie Lu Guangquan Zhang Arthur Gretton Danica J. Sutherland
references.title: Learning deep kernels for non-parametric two-sample tests
references.venue: In ICML,
references.authors: Lu Liu Tianyi Zhou Guodong Long Jing Jiang Chengqi Zhang
references.title: Attribute propagation network for graph zero-shot learning
references.venue: In AAAI,
references.authors: Lu Liu Tianyi Zhou Guodong Long Jing Jiang Xuanyi Dong Chengqi Zhang
references.title: Isometric propagation network for generalized zero-shot learning
references.venue: In ICLR,
references.authors: Yanbin Liu Juho Lee Minseop Park Saehoon Kim Eunho Yang Sung Ju Hwang Yi Yang
references.title: Learning to propagate labels: Transductive propagation network for few-shot learning
references.venue: In ICLR,
references.authors: James MacQueen
references.title: Some methods for classification and analysis of multivariate observations
references.venue: In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability,
references.authors: Andreas Maurer
references.title: Algorithmic stability and meta-learning
references.venue: Journal of Machine Learning Research,
references.authors: Yuval Netzer Tao Wang Adam Coates Alessandro Bissacco Bo Wu Andrew Y. Ng
references.title: Reading digits in natural images with unsupervised feature learning
references.venue: In NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning,
references.authors: Minseop Park Saehoon Kim Jungtaek Kim Yanbin Liu Seungjin Choi
references.title: Taeml: Task-adaptive ensemble of meta-learners
references.venue: In NeurIPS Workshop on Meta learning,
references.authors: Tiago Ramalho Marta Garnelo
references.title: Adaptive posterior learning: few-shot learning with a surprisebased memory module
references.venue: In ICLR,
references.authors: Sachin Ravi Hugo Larochelle
references.title: Optimization as a model for few-shot learning
references.venue: In ICLR,
references.authors: Kuniaki Saito Yoshitaka Ushiku Tatsuya Harada
references.title: Asymmetric tri-training for unsupervised domain adaptation
references.venue: In ICML,
references.authors: Adam Santoro Sergey Bartunov Matthew Botvinick Daan Wierstra Timothy P. Lillicrap
references.title: Meta-learning with memory-augmented neural networks
references.venue: In ICML,
references.authors: Karen Simonyan Andrew Zisserman
references.title: Very deep convolutional networks for large-scale image recognition
references.venue: In ICLR,
references.authors: Jake Snell Kevin Swersky Richard S. Zemel
references.title: Prototypical networks for few-shot learning
references.venue: In NeurIPS,
references.authors: Jie Song Yixin Chen Xinchao Wang Chengchao Shen Mingli Song
references.title: Deep model transferability from attribution maps
references.venue: In NeurIPS,
references.authors: Jie Song Yixin Chen Jingwen Ye Xinchao Wang Chengchao Shen Feng Mao Mingli Song
references.title: DEPARA: deep attribution graph for deep knowledge transferability
references.authors: Nitish Srivastava Geoffrey E. Hinton Alex Krizhevsky Ilya Sutskever Ruslan Salakhutdinov
references.title: Dropout: a simple way to prevent neural networks from overfitting
references.venue: Journal of Machine Learning Research,
references.authors: Dirk R. Walters
references.title: Vascular Plant Taxonomy
references.venue: Kendall/Hunt Publishing Company,
references.authors: Yaqing Wang Quanming Yao James T Kwok Lionel M Ni
references.title: Generalizing from a few examples: A survey on few-shot learning
references.venue: ACM Computing Surveys,
references.authors: Ying Wei Peilin Zhao Junzhou Huang
references.title: Meta-learning hyperparameter performance prediction with neural processes
references.venue: In ICML,
references.authors: Junyuan Xie Ross B. Girshick Ali Farhadi
references.title: Unsupervised deep embedding for clustering analysis
references.venue: In ICML,
references.authors: Huaxiu Yao Ying Wei Junzhou Huang Zhenhui Li
references.title: Hierarchically structured meta-learning
references.venue: In ICML,
references.authors: Huaxiu Yao Longkai Huang Linjun Zhang Ying Wei Li Tian James Zou Junzhou Huang Zhenhui Li
references.title: Improving generalization in meta-learning via task augmentation
references.venue: In ICML,
references.authors: Zhun Zhong Enrico Fini Subhankar Roy Zhiming Luo Elisa Ricci Nicu Sebe
references.title: Neighborhood contrastive learning
references.venue: In CVPR,
references.authors: Zhun Zhong Linchao Zhu Zhiming Luo Shaozi Li Yi Yang Nicu Sebe
references.title: Openmix: Reviving known knowledge for discovering novel visual categories in an open world
references.venue: In CVPR,
references.authors: Imtiaz Masud Ziko Jose Dolz Eric Granger Ismail Ben Ayed
references.title: Laplacian regularized few-shot learning
references.venue: In ICML,
references.authors: Xie
references.title: 2016) to learn the cluster assignments on unlabeled data. In RS (Han et al., 2020), they used the rank statistics to predict the pairwise similarity of data. To keep the performance on data of known classes, they pre-trained the data embedding network with self-supervised learning method (Gidaris et al., 2018
references.authors: meta-learning. Yao
references.title: 2019) assigned many tasks that are randomly sampled from different clusters using their similarities, and only used the most related task cluster for training. This method solves the task-sampling problem in the view of tasks. Liu et al. (2020a) proposed a greedy class-pair based sampling method, which selects difficult tasks according to the class-pair potentials. This method solves the sampling problem in the view of classes
sections.text: In learning to discover novel classes (L2DNC), we are given labeled data from seen classes and unlabeled data from unseen classes, and we train clustering models for the unseen classes. However, the implicit assumptions behind L2DNC are still unclear. In this paper, we demystify assumptions behind L2DNC and find that high-level semantic features should be shared among the seen and unseen classes. Based on this finding, L2DNC is theoretically solvable under certain assumptions and can be naturally linked to meta-learning that has exactly the same assumption as L2DNC. Thus, we can empirically solve the L2DNC problem by meta-learning algorithms after slight modifications. This meta-learning-based methodology significantly reduces the amount of unlabeled data needed for training and makes it more practical, as demonstrated in experiments. The use of very limited data is also justified by the application scenario of L2DNC: since it is unnatural to label only seen-class data, L2DNC is sampling instead of labeling in causality. Therefore, unseen-class data should be collected on the way of collecting seen-class data, which is why they are novel and first need to be clustered.
sections.heading: 1 INTRODUCTION
sections.text: With the development of high-performance computing, we can train deep networks to achieve various tasks well (Deng et al., 2009; Song et al., 2019; Jing et al., 2020; Song et al., 2020; Liu et al., 2020b). However, the trained networks can only recognize the classes seen in the training set (i.e., known/seen classes), and cannot identify and cluster novel classes (i.e., unseen classes) like human beings. A prime example is that human can easily tell a novel animal category (e.g., okapi) after learning a few seen animal categories (e.g., horse and dog). Namely, human can effortlessly discover (cluster) novel categories of animals. Inspired by this fact, previous works formulated a novel problem called learning to discover novel classes (L2DNC) (Hsu et al., 2018; Han et al., 2019), where we train a clustering model using plenty of unlabeled novel-class and labeled known-class data.
  However, if L2DNC is labeling in causality (X → Y ), there exists two issues: L2DNC might not be a theoretically solvable problem. For example, if novel classes are completely different from known classes, then it is unrealistic to use the known classes (like animals) to help precisely cluster novel classes (like cars, Figure 1(a)). Moreover, L2DNC might not be a realistic problem in some scenarios where novel classes might only be seen once or twice. This does not satisfy the assumptions considered in existing L2DNC methods. These issues naturally motivate us to find out when L2DNC can be theoretically solved and what assumptions are considered behind L2DNC.
  In this paper, we revisit L2DNC and find that L2DNC will be a well-defined problem if L2DNC is sampling in causality (Y → X), i.e., novel and known classes are sampled together (Figure 1(b)). In this sampling process, data are often obtained because of a given purpose, and novel classes and known classes are obtained in the same scenario. For instance, botanists sample plant specimens for research purposes in the forests. Except for the plants they are interested in (i.e., known classes), they also find scarce plants never seen before (i.e., finding novel classes (Smith, 1874)). Since a trip to forests is relatively costly and toilsome, botanists had better sampled these scarce plants passingly for future research. From this example, it can be seen that botanists will have plenty of labeled data with known classes, and few unlabeled data with novel classes. Since both data are sampled together from
  the same scenario (e.g., plants in the forests), it is reasonable to leverage knowledge of known classes to help cluster novel classes, which is like “discovering novel categories” happened in our daily life.
  Therefore, we argue that the key assumption behind L2DNC is that, known classes and novel classes share high-level semantic features. For example, known classes and novel classes are different plants but all of them have the leaf, the stem, and the roots (Walters, 1977). Then, we reformulate the L2DNC problem and show that L2DNC is theoretically solvable under mild assumptions (including the key assumption above). We also show an impossibility theorem for previous L2DNC setting. This theorem shows that it might not be necessary to introduce known-class data to help cluster novel-class data if known classes and novel classes do not share high-level semantic features. Namely, L2DNC might be an ill-defined problem if known and novel class do not share high-level semantic features.
  Although L2DNC is theoretically solvable under mild assumptions, we still need abundant data from known and novel classes to ensure L2DNC can be empirically solved. However, as we mentioned previously, the novel classes might only be seen once or twice in some scenarios. In such scenarios, we find that previous L2DNC methods do not work well (Figure 2). To address the L2DNC given very limited data (L2DNCL), we link L2DNC to meta-learning that also assumes that known and unknown (novel) classes share the high-level semantic features (Chen et al., 2020a; Maurer, 2005).
  The key difference between meta-learning and L2DNCL lies in their inner-tasks. In meta-learning, the inner-task is a classification task, while in L2DNCL, it is a clustering task. Thus, we can modify the training strategies of the inner-tasks of meta-learning methods such that they can discover novel classes, i.e., meta discovery. Specifically, we first propose a novel method to sample training tasks for meta-learning methods. In sampled tasks, labeled and unlabeled data share high-level semantic features and the same clustering rule (Figure 3). Then, based on this novel sampling method, we realize meta discovery using two representative meta-learning methods: model-agnostic meta-learning (MAML) (Finn et al., 2017) and prototypical network (ProtoNet) (Snell et al., 2017). Figure 2 demonstrates two realizations of meta discovery (i.e., meta discovery with MAML (MM) and meta discovery with ProtoNet (MP)) can perform much better than existing methods in L2DNCL.
  We conduct experiments on four benchmarks and compare our method with five competitive baselines (MacQueen et al., 1967; Hsu et al., 2018; 2019; Han et al., 2019; 2020). Empirical results show that our method outperforms these baselines significantly when novel-class data are very limited. Moreover, we provide a new practical application to the prosperous meta-learning community (Chen et al., 2020a), which lights up a novel road for L2DNCL.
sections.heading: 2 RELATED WORK
sections.text: Our proposal is mainly related to L2DNC and meta-learning that are briefly reviewed here. More detailed reviews can be found in Appendix A.
  0 20 40 60 80 100 Epoch
  25
  30
  35
  40
  45
  50
  55
  60
  A cc
  (% )
  0 20 40 60 80 100 Epoch
  25
  30
  35
  40
  45
  50
  55
  60
  A cc
  (% )
  0 20 40 60 80 100 Epoch
  20
  30
  40
  50
  60
  A cc
  (% )
  0 20 40 60 80 100 Epoch
  20
  30
  40
  50
  60
  A cc
  (% )
  MP MM RS KCL MCL DTC
  0 50 100 Epoch
  30
  40
  50
  60
  A cc
  (% )
  CIFAR-10
  (a) 5-way 5-observation
  0 50 100 Epoch
  30
  40
  50
  60
  A cc
  (% )
  CIFAR-10
  (b) 5-way 1-observation
  0 50 100 Epoch
  20
  30
  40
  50
  60
  A cc
  (% )
  SVHN
  (c) 5-way 5-observation
  0 50 100 Epoch
  20
  30
  40
  50
  60
  A cc
  (% )
  SVHN
  (d) 5-way 1-observation
  Figure 2: We conducted experiments on CIFAR-10 and SVHN and reported the average clustering accuracy (ACC (%), Section 5) when using existing and our methods to address the L2DNCL. We can observe that existing methods cannot address the L2DNCL, while our methods (MM and MP) can address the L2DNCL well.
  Learning to discover novel classes. L2DNC was proposed in recent years, aiming to cluster unlabeled novel-class data according to underlying categories. Compared to unsupervised learning (Barlow, 1989), L2DNC also requires labeled known-class data to help cluster novel-class data. The pioneering methods include the KL-Divergence-based contrastive loss (KCL) (Hsu et al., 2018), the meta classification likelihood (MCL) (Hsu et al., 2019), deep transfer clustering (DTC) (Han et al., 2019), and the rank statistics (RS) (Han et al., 2020). Compared to existing works (Hsu et al., 2018; Zhong et al., 2021b;a), we focus on clustering unlabeled data when their quantity is very limited.
  Meta-learning. Meta-learning is also known as learning-to-learn, which trains a meta-model over a wide variety of learning tasks (Yao et al., 2021; Wei et al., 2021; Ravi & Larochelle, 2017; Chen et al., 2020b). In meta-learning, we often assume that data share the same high-level features, which ensures that meta-learning can be theoretically addressed (Maurer, 2005). According to Hospedales et al. (2020), there are three common approaches to meta-learning: optimization-based (Finn et al., 2017), model-based (Santoro et al., 2016), and metric-based (Snell et al., 2017). In (Jiang & Verma, 2019), researchers trained a recurrent model that learns how to cluster given multiple types of training datasets. Compared to our meta discovery, Jiang & Verma (2019) learn a clustering model with multiple unlabeled datasets, while meta discovery aims to learn a clustering model with labeled known data and (abundant or few) unlabeled novel data from the same dataset.
sections.heading: 3 ASSUMPTIONS BEHIND L2DNC AND ANALYSIS OF SOLVABILITY
sections.text: Since L2DNC focuses on clustering novel-class data, we first show definitions regarding the separation of a random variable (r.v.) X ∼ PX defined on X ⊂ Rd. Then, we give a formal definition of L2DNC and introduce assumptions behind L2DNC. Finally, we present one theorem to show L2DNC is solvable in theory and one theorem to show a failure situation where previous setting encounters. The proofs of both theorems can be seen in Appendix B. Definition 1 (K- -Separable r.v.). Given the r.v. X ∼ PX , X is K- -separable with a non-empty function set F = {f : X → I} if ∀f ∈ F
  τ(X, f(X)) := max i,j∈I,i6=j
  PX(RX|f(X)=i ∩RX|f(X)=j) = , (1)
  where I = {i1, . . . , iK} is an index set, f(X) is an induced r.v. whose source of randomness is X exclusively, and RX|f(X)=i = supp(PX|f(X)=i) is the support set of PX|f(X)=i.
  In Eq. (1), τ(·, ·) represents the largest overlap between any different clusters in the sense of the probability measure PX . If = 0, then we can perfectly partition observations of X into K clusters using some distance-based clustering algorithm, e.g., K-means (MacQueen et al., 1967). However, when X is a complex space and the dimension d is much larger than the intrinsic dimension of X (e.g., images), it is not reliable to measure the distance between observations from X using original features (Liu et al., 2020b), which will result in poor clustering performance.
  Non-linear transformation. To overcome issues caused by the complex space, researchers suggest apply a non-linear transformation to extract high-level features of X (Fang et al., 2020; Liu et al., 2020b). Based on these features, we can measure the distance between two observations well (Liu et al., 2020b). Let π : X → Rdr be a transformation where dr is the reduced dimension and dr d, and we expect that the transformed r.v. π(X) can be K- -separable as well. Namely, we hope the following function set exists.
  Definition 2 (Consistent K- -separable Transformation Set). Given r.v. X that is K- -separable with a function set F , a transformed r.v. π(X) is K- -separable with F if ∀f ∈ F ,
  τ(π(X), f(X)) := max i,j∈I,i6=j
  Pπ(X)(Rπ(X)|f(X)=i ∩Rπ(X)|f(X)=j) = , (2)
  where π : X → Rdr is a transformation. Then, a consistent K- -separable transformation set is a non-empty set Π satisfying that ∀f ∈ F ,∀π ∈ Π, τ(π(X), f(X)) = . Remark 1. If dr d and = 0, we will need much less observations to estimate the density of π(X) compared to X , thus it will be much easier to perfectly separate π(X) than X . For example, there probably exists a linear function g : Rdr → I such that f(X) = g ◦ π(X). It is clear that such linear function g is easier to find than directly finding f using K-means.
  Problem Setup of L2DNC. Based on the above definitions, we will formally define the L2DNC problem below. In L2DNC, we have two r.v.s X l, Xu defined on X , the ground-truth labeling function f l : X → Y for X l and a function set F = {f : X → I}, where Y = {il1, . . . , ilK l} and I = {iu1, . . . , iuKu}. Based on Definitions 1 and 2, we have the following assumptions in L2DNC.
  (A) The support set of X l and the support set of Xu are disjoint, and underlying classes of X l are different from those of Xu (i.e., I ∩ Y = ∅);
  (B) X l is K l- l-separable with F l = {f l} and Xu is Ku- u-separable with Fu, where l = τ(X l, f l(X l)) < 1 and u = minf∈F τ(Xu, f(Xu)) < 1;
  (C) There exist a consistent K l- l-separable transformation set Πl for X l and a consistent Ku- u-separable transformation set Πu for Xu;
  (D) Πl ∩Πu 6= ∅.
  (A) ensures that known and novel classes are disjoint. (B) implies that it is meaningful to separate observations from X l and Xu. (C) means that we can find good high-level features for X l or Xu. Based on these features, it is much easier to separate X l or Xu. (D) says that the high-level features of X l and Xu are shared, as demonstrated in the introduction. Then, we can define L2DNC formally.
  Problem 1 (L2DNC). Given X l, Xu and f l defined above and assume (A)-(D) hold, in L2DNC, we aim to learn a function π̂ : X → Rdr via minimizingJ (π̂) = τ(π̂(X l), f l(X l))+τ(π̂(Xu), f u(Xu)), where f u ∈ F and dr d. We expect that π̂(Xu) is Ku- u-separable. Theorem 1 (L2DNC is Theoretically Solvable). Given X l, Xu and f l defined above and assume (A)-(D) hold, then π̂(Xu) is Ku- u-separable. If u = 0, then L2DNC is theoretically solvable.
  Theorem 1 means that it is possible to find a good transformation π̂ such that π̂(Xu) is separable although we introduce X l1. Then we show that L2DNC might be ill-defined if (D) does not hold. Theorem 2 (Impossibility Theorem). Given X l, Xu and f l defined above and assume (A)-(C) hold, if maxπ∈Πl τ(π(Xu), f u(Xu)) < minπ∈Π−Πl τ(π(X l), f l(X l)), (D) does not hold and l ≤ u, then τ(π̂(Xu), f u(Xu)) > u, where Π = {π : X → Rdr} and f u ∈ F . Remark 2. Condition maxπ∈Πl τ(π(Xu), f u(Xu)) < minπ∈Π−Πl τ(π(X l), f l(X l)) indicates that the worst case of clustering novel classes with transformations that are suitable for known classes is better than the best case of clustering known classes with transformations that are not suitable for known classes. Besides, l ≤ u indicates that the transformations in X l is more separable than Xu.
  In previous setting, data acquiring process is unclear. As we discussed, if L2DNC is labelling in causality, then novel and known classes might not share high-level semantic features (Figure 1(a)). Namely, (D) might not hold, resulting in that X l might bring negative effects under some conditions (Theorem 2). Thus, based on Theorems 1 and 2, it is clear that (D) plays a key role in L2DNC, which also justifies that L2DNC will be well-defined if it is sampling in causality. Noting that sampling in causality (Y → X) is the sufficient unnecessary condition of (D). For example, if there are some constraints to make the novel-class data (to be annotated) are obtained in the same scenario with known-class data, then data generated by labeling (X → Y ) also satisfy (D).
  1Note that, the objective of clustering problem is different from that of L2DNC. In clustering problem, we aim to find π̂ via minimizing τ(π̂(Xu), f u(Xu)) rather than τ(π̂(X l), f l(X l)) + τ(π̂(Xu), f u(Xu)).
  Based on Theorem 1, if there are abundant observations to estimate J (π̂), then we can find the optimal transformation π̂ to help obtain a good partition for observations from Xu. However, as discussed before, the novel classes might only be seen once or twice in some scenarios. In such scenarios, we find that previous L2DNC methods do not work well empirically (Figure 2). To address the L2DNC given very limited data (L2DNCL), we link L2DNC to meta-learning that also assumes that known and unknown (novel) classes share the high-level semantic features (Chen et al., 2020a), which is exactly the same as (D) in L2DNC. Thus, it is natural to address L2DNCL by meta-learning.
sections.heading: 4 META DISCOVERY FOR L2DNCL
sections.text: Meta-learning has been widely used to solve few-shot learning problems (Chen et al., 2020a; Wang et al., 2020). The pipeline of meta-learning consists of three steps: 1) randomly sampling data to simulate many inner-tasks; 2) training each inner-task by minimizing its empirical risk; 3) regarding each inner-task as a data point to update meta algorithm. Compared to meta-learning, the inner-task of L2DNCL is clustering instead of classification in meta-learning. Thus, we can modify the loss function of inner-task to be suitable for clustering and follow the framework of meta-learning, i.e., meta discovery. In Appendix C, we give L2DNCL a definition from the view of meta-learning and further prove L2DNCL is theoretically solvable. In this section, we let Sl = {(xli, yli) : i = 1, . . . , nl} be known-class data drawn from r.v. (X l, f l(X l)) and yli ∈ {1, . . . ,K l}, and let Su = {xui : i = 1, . . . , nu} be unlabeled novel-class data drawn from r.v. Xu, where 0 < nu nl. Due to the difference of inner-task, if we randomly sample data to compose an inner-task like existing meta-learning methods, these data may negatively influence each other in the training procedure. This is because these randomly sampled data in an inner-task have different clustering rules (Figure 3). Thus, in meta discovery, the key is to propose a new task sampler that takes care of clustering rules.
  CATA: Clustering-rule-aware Task Sampler. From the perspective of multi-view learning (Blum & Mitchell, 1998), data usually contain different feature representations. Namely, data have multiple views. However, there are always one view or a few views that are dominated for each instance, and these dominated views are similar with high-level semantic meaning (Li et al., 2019b; Liu et al., 2021; 2020c). Therefore, we propose to use dominated views to replace with clustering rules, and design a novel task-sampling method called clustering-rule-aware task sampler (CATA, Algorithm 1). CATA is based on a multi-view network containing a feature extractor G : X → Rds and M classifiers {Fi : Rds → Y}Mi=1 (Figure 4). M is empirically chosen according to the data complexity. Specifically, CATA learns a low-dimension projection and set of orthogonal classifiers. It then assigns each data point to a group defined by which of the orthogonal classifiers was most strongly activated by the observation, and inner tasks are sampled from each group.
  The feature extractor G provides the shared data representations for M different classifiers {Fi}Mi=1. Each classifier classifies data based on its own view. The feature extractor G learns from all gradients from {Fi}Mi=1. To ensure that different classifiers have different views, we constrain the weight vector of the first fully connected layer of each classifier to be orthogonal. Take Fi and Fj as an example, we add the term |WTi Wj | to the sampler’s loss function, where Wi and Wj denote the weight vectors of the first fully connected layer of Fi and Fj respectively. |WTi Wj | tending to 0 means that Fi and Fj are nearly independent (Saito et al., 2017). Thus, the loss function of CATA is defined as follows,
  LS(θG, {θFi}Mi=1) = 1
  MN M∑ j=1 N∑ i=1 `ce(Fj ◦G(xi), yi) + 2λ M(M − 1) ∑ i6=j |WTi Wj |, (3)
  where `ce is the standard cross-entropy loss function and λ is a trade-off parameter.
  Algorithm 1 Clustering-rule-aware task sampler (CATA)
  Input: known-class data Sl, feature extractor G, classifiers {Fi}M l
  i=1, learning rates ω1, ω2; view index: j. 1: Initialize θG and {θFi}M l
  i=1; for t = 1, . . . , T do
  2: Compute∇θGLS and {∇θFiLS} M l i=1 using S l and LS in Eq. (3); 3: Update θG = θG−ω1∇θGLS(θG, {θFi} M l i=1), θFi = θFi−ω2∇θFiLS(θG, {θFi} Kl i=1), i = 1, . . . ,M l;
  end 4: Compute {Fi(G(xl))}M l i=1 to obtain {Pi(yl|xl)}M l i=1 for each (x l, yl) ∈ Sl; 5: Compose Vi = {xl : V (xl) = i} using function V in Eq. (4), i = 1, . . . ,M l; 6: Sample an inner-task Ti = (Sl,tri , S l,ts i ) ∼ Vj Output: an inner-task Ti After we obtain the well-trained feature extractor G and classifiers {Fi}Mi=1, we input a training data point x to our sampler and then we will get the probabilities that x belongs to class y in each classifier, i.e. {Pi(y|x)}Mi=1, where y is the label of x. Therefore, the view which x belongs to is defined as
  V (x) = arg max i Pi(y|x). (4)
  Now we have assigned a data point to M subsets according to their views, i.e. {Vi = {x ∈ X : V (x) = i}}Mi=1. Then, we can directly randomly sample a certain number of data (e.g., N -way, K-observation) from one subset to compose an inner task. According to the number of data in each subset, we sample inner tasks from each subset with different frequencies. We also compare CATA with commonly used samplers in meta-learning in Appendix A. Note that, CATA is a heuristic method, and we will give clustering rule a formal definition and explore the reason why CATA succeed theoretically in the future.
  Realization of Meta Discovery with MAML (MM). Here, we solve the L2DNCL problem based on MAML. A feature extractor πmm : X → Rdr is given to obtain an embedding of data, following a classifier g with the output dimension equalling to the number of novel classes (Ku). As novel classes share the same high-level semantic features of known classes, the feature extractor πmm should be applicable to known and novel classes. The key idea is that similar data should belong to the same class. For data pair (xi, xj), let sij = 1 if they come from the same class; otherwise, sij = 0.
  Following Han et al. (2020), we adopt a more robust pairwise similarity called ranking statistics. For zi = πmm(xi) and zj = πmm(xj), we rank the values of zi and zj by the magnitude. Then we check if the indices of the values of top-k ranked dimensions are the same. Namely, sij = 1 if they are the same, and sij = 0 otherwise. We use the pairwise similarities {sij}1≤i,j≤nl as pseudo labels to train our feature extractor πmm and classifier g. As mentioned above, g is a classifier with the softmax layer, so the inner product g(zi)T g(zj) is the cosine similarity between xi and xj , which serves as the score for whether xi and xj belong to the same class. After sampling training tasks {Ti}ni=1, we train a model by the inner algorithm that optimizes the binary cross-entropy (BCE) loss function:
  LTi(θg◦πmm) = − 1
  nl 2 nl∑ i=1 nl∑ j=1 [sij log(g(zi) T g(zj)) + (1− sij) log(1− g(zi)T g(zj))]. (5)
  Algorithm 2 MM for L2DNCL. Input: known-class data: Sl; learning rate: α, η; feature extractor: πmm; classifier: g 1: Initialize θg◦πmm ; while not done do
  2: Sample tasks {Ti = (Sl,tri , S l,ts i ) ∼ S l}ni=1 by CATA (Alg. 1); for all Ti do
  3: Evaluate∇θg◦πmmLTi(θg◦πmm) using S l,tr i and LTi in Eq. (5);
  4: Compute adapted parameters: θ′g◦πmm,i = θg◦πmm − α∇θg◦πmmLTi(θg◦πmm); end 5: Update θg◦πmm = θg◦πmm − η∇θg◦πmmLA(θ ′ g◦πmm) using each S l,ts i and LA in Eq. (6);
  end Output: clustering algorithm Ā.
  Algorithm 3 MP for L2DNCL. Input: known-class data: Sl; learning rate: γ; feature extractor: πmp 1: Initialize θπmp ; while not done do
  for all episodes do 2: Sample Ku elements from {1, . . . ,K l} as set CI ; 3: Sample tasks Ti = (Sl,tri , S l,ts i ) ∼ S l |yl∈CI by CATA (Alg. 1);
  for s in CI do 4: Sample m training data of class-s, i.e., Sl,tri,s ∼ S l,tr i & |S l,tr i,s | = m;
  5: Compute ci,s(Sl,tri,s ) using Eq. (8); 6: Sample k test data of class-s, i.e., Sl,tsi,s ∼ S l,ts i & |S l,ts i,s | = k;
  end 7: Update θπmp = θπmp − γ∇θπmpLTi(θπmp) using {S l,ts i,s }s∈CI and LTi in Eq. (10);
  end end Output: feature extractor πmp.
  Entire procedures of L2DNCL by MAML are shown in Algorithm 2. Following MAML, the parameters of clustering algorithm A are trained by optimizing the following loss function:
  LA(θg◦πmm) = n∑ i=1 LTi(θg◦πmm − α∇θg◦πmmLTi(θg◦πmm)), (6)
  where α > 0 is the learning rate of the inner-algorithm. Then we conduct the meta-optimization to update the parameters of clustering algorithm A as follows:
  θg◦πmm ← θg◦πmm − η∇θg◦πmmLA(θg◦πmm), (7)
  where η > 0 denotes the meta learning rate. After finishing meta-optimization, we finetune the clustering algorithm A with the novel-class data to yield a new clustering algorithm that is adapted to novel classes. More specifically, we continue to perform line 4 and line 5 in Algorithm 2 with novel-class data Su.
  Realization of Meta Discovery with ProtoNet (MP). Following Snell et al. (2017), we denote πmp as a feature extractor, which maps data to their representations. In training task Ti, the mean vector of representations of data from class-s (i.e., Sl,tri,s ) is defined as prototype ck:
  ci,s(S l,tr i,s ) =
  1
  |Sl,tri,s | ∑ (xli,y l i)∈S l,tr i,s πmp(x l i). (8)
  Here, we define the Euclidean distance dist : Rdr×Rdr → [0,+∞) to measure the distance between data from the test set and the prototype. Then, we represent p(y = s|x) using the following equation.
  p(y = s|x) = exp(−dist(πmp(x), cs))∑ s′ exp(−dist(πmp(x), cs′)) . (9)
  0 20 40 60 80 100 Epoch
  25
  30
  35
  40
  45
  50
  55
  60
  A cc
  (% )
  0 20 40 60 80 100 Epoch
  25
  30
  35
  40
  45
  50
  55
  60
  A cc
  (% )
  0 20 40 60 80 100
  Epoch
  20
  30
  40
  50
  60
  A cc
  (% )
  0 20 40 60 80 100
  Epoch
  20
  30
  40
  50
  60
  A cc
  (% )
  MP MM RS KCL MCL DTC
  0 50 100 Epoch
  20
  30
  40
  50
  A cc
  (% )
  CIFAR-100
  (a) 20-way 1-observation
  0 50 100 Epoch
  20
  30
  40
  50
  A cc
  (% )
  CIFAR-100
  (b) 20-way 5-observation
  0 50 100 Epoch
  40
  60
  80
  100
  A cc
  (% )
  OmniGlot
  (c) 20-way 1-observation
  0 50 100 Epoch
  40
  60
  80
  100
  A cc
  (% )
  OmniGlot
  (d) 20-way 5-observation
  Figure 5: We conducted experiments on CIFAR-100 and OmniGlot and reported the average clustering accuracy (ACC (%), Section 5) when using existing and our methods to address the L2DNCL problem. The experimental results showed that MM and MP tend to outperform existing methods.
  Table 1: Results of K-means on all four datasets.
  Dataset CIFAR-10 (5-way) SVHN (5-way) CIFAR-100 (20-way) OmniGlot (20-way)
  1-observation 30.2±3.60 23.5±0.66 9.7±1.18 2.0±0.16 5-observation 32.8±2.13 23.7±0.35 12.4±1.15 2.8±0.13
  We train the feature extractor by optimizing the negative log-probability, i.e., − log p(y = s|x). So the loss function of ProtoNet is defined as follows:
  LTi = − 1
  k ∑ s∈[Ku] ∑ x∈Sl,tsi,s log p(y = s|x), (10)
  where [Ku] denotes the Ku classes selected from {1, . . . ,K l}. Sl,tsi,s is the test set of labeled data of class-s from task Ti. The full procedures of training πmp are shown in Algorithm 3. After training the feature extractor πmp well, we use the training set of Su to obtain the prototypes. For x in the test set of Su, we compute the distance between x and each prototype, and then the class corresponding to the nearest prototype is the class of x.
sections.heading: 5 EXPERIMENTS
sections.text: Baselines. To verify the performance of our meta-based L2DNCL methods (i.e., MM and MP), we compare them with 5 competitive baselines, including K-means (MacQueen et al., 1967), KCL (Hsu et al., 2018) , MCL (Hsu et al., 2019), DTC (Han et al., 2019), and RS (Han et al., 2020). We modify these baselines by only reducing the amount of novel-class data, with other configurations invariable. We clarify the implementation details of CATA, MM, and MP in Appendix E.
  Datasets. To evaluate the performance of our methods and baselines, we conduct experiments on four popular image classification benchmarks, including CIFAR-10 (Krizhevsky & Hinton, 2009), CIFAR-100 (Krizhevsky & Hinton, 2009), SVHN (Netzer et al., 2011), and OmniGlot (Lake et al., 2015). Detailed introductions and partitions of known classes and novel classes of these four datasets is in Appendix D. Following the protocol of few-shot learning (Wang et al., 2020; Ziko et al., 2020; Liu et al., 2019; Park et al., 2018), for SVHN and CIFAR-10, we perform the few-observation tasks of 5-way 1-observation and 5-way 5-observation, and we perform the few-observation tasks of 20-way 1-observation and 20-way 5-observation for CIFAR-100 and OmniGlot.
  Evaluation metric. For a clustering problem, we use the average clustering accuracy (ACC) to evaluate the performance of clustering, which is defined as follows,
  max φ∈ L
  1
  N N∑ i=1 1{ȳi = φ(yi)}, (11)
  where ȳi and yi denote the ground-truth label and assigned cluster indices respectively. L is the set of mappings from cluster indices to ground-truth labels.
  Results on CIFAR-10. As shown in Figures 2(a) and 2(b), MM and MP outperform all baselines significantly, and the ACC of MP is much higher than that of MM. The main reason is that MP makes
  full use of the labels of known-class data in the training process, while MM does not. MM only uses the labels of known-class data in the sampling process. Besides, as shown in Table 1, K-means performs better on CIFAR-10 than other datasets. The reason is that clustering rules contained in data of CIFAR-10 are simple and suitable for K-means.
  Results on SVHN. Figures 2(d) and 2(c) show that our methods still outperform all baselines. In the task of 5-way 1-observation, RS performs as well as MM (Figure 2(d)). The reason is that RS trains the embedding network with self-supervised learning method, RotationNet (Gidaris et al., 2018), under 1-observation case, which partly overcomes this problem by data augment. The SVHN is simpler than other datasets, thus such a data augmentation works better.
  Results on CIFAR-100. It is clear that we outperform all baselines. Differ from tasks on other datasets, MM performs equally even a little better than MP shown in Figure 5(a). The reason is that the amount of known classes is relatively large and the data distribution of CIFAR-100 is complex, so we cannot accurately compute prototypes with very limited data.
  Results on OmniGlot. As shown in Figures 5(c) and 5(d), our methods still have the highest ACC. We find that the ACC of K-means are merely 2.2% for both 1-observation and 5-observation, indicating that K-means hardly works on OmniGlot. Although this result looks very bad, this is reasonable. This is because the number of novel classes is too large (i.e., 659) and K-means is an unsupervised method that requires many training data. As a simple benchmark in few-shot learning, existing meta-learning methods (Ramalho & Garnelo, 2019; Li et al., 2019a) have completed solved it, which achieved the accuracy of 99.9% on 20-way 5-shot task. Thus our method MP also achieves a high accuracy of 98.4% without novel-class labels.
  Ablation study. To verify the effectiveness of CATA, we conduct ablation study by removing CATA from MM and MP. According to Table 2, CATA significantly improves the performance of MM and MP. However, there exists an abnormal phenomenon in OmniGlot, i.e., MM w/o CATA outperforms MM in the task of 20-way 1-observation. Although we need 16 (= |Sl,tr|+ |Sl,ts| = 1 + 15) data for each class in an inner-task, the total amount of data for each class is only 20. Therefore, there are not enough data for CATA to sample, which makes CATA cannot improve the ACC of MM.
  MM and MP to L2DNC. MM and MP can also address L2DNC. Results are shown in Table 3 (Appendix F), showing that MM is comparable with the representative methods but cannot outperform the RS and MP performs worse than MM. In Appendix F, we analyze this phenomenon in detail.
sections.heading: 6 CONCLUSIONS
sections.text: In this paper, we study an important problem called learning to discover novel classes (L2DNC) and demystify the key assumptions behind this problem. We find that L2DNC is sampling instead of labeling in causality, and, furthermore, data in the L2DNC problem should share high-level semantic features. This finding motivates us to link L2DNC to meta-learning, since meta-learning also assumes that the high-level semantic features are shared between seen and unseen classes. To this end, we propose to discover novel classes in a meta-learning way, i.e., the meta discovery. Results show that meta-learning based methods outperform all existing baselines when addressing a more challenging problem L2DNC given very limited data (L2DNCL) where only few novel-class data can be observed, which lights up a novel road for L2DNC/L2DNCL.
sections.heading: 7 ETHICS STATEMENT
sections.text: This paper does not raise any ethics concerns. This study does not involve any human subjects, practices to data set releases, potentially harmful insights, methodologies and applications, potential conflicts of interest and sponsorship, discrimination/bias/fairness concerns, privacy and security issues, legal compliance, and research integrity issues.
sections.heading: 8 REPRODUCIBILITY STATEMENT
sections.text: To ensure the reproducibility of experimental results, we will provide a link for an anonymous repository about the source codes of this paper in the discussion phase.
sections.heading: A DETAILED RELATED WORK
sections.text: Learning to discover novel classes. L2DNC is proposed in recent years, aiming to cluster unlabeled novel-class data according to their underlying categories. Compared with unsupervised learning (Barlow, 1989), L2DNC also requires labeled known-class data to help cluster novel-class data. The pioneering methods include KLD-based contrastive loss (KCL) (Hsu et al., 2018), meta classification likelihood (MCL) (Hsu et al., 2019), deep transfer clustering (DTC) (Han et al., 2019), and rank statistics (RS) (Han et al., 2020). In this paper, we update and present the results of our methods regarding L2DNC.
  In KCL (Hsu et al., 2018), a method based on pairwise similarity is introduced. They first pre-trained a similarity prediction network on labeled data of known classes and then use this network to predict the similarity of each unlabeled data pair, which acts as the supervision information to train the main model. Then, MCL (Hsu et al., 2019) changed the loss function of KCL (the KL-divergence based contrastive loss) to the meta classification likelihood loss.
  In DTC (Han et al., 2019), they first learned a data embedding with metric learning on labeled data, and then they employed the DEC (Xie et al., 2016) to learn the cluster assignments on unlabeled data.
  In RS (Han et al., 2020), they used the rank statistics to predict the pairwise similarity of data. To keep the performance on data of known classes, they pre-trained the data embedding network with self-supervised learning method (Gidaris et al., 2018) on both labeled data and unlabeled data.
  Meta-Learning. Meta-learning is also known as learning-to-learn, which train a meta-model over a large variety of learning tasks (Ravi & Larochelle, 2017). In meta-learning, we often assume that data share the same high-level features, which ensures that meta-learning can be theoretically addressed (Maurer, 2005). According to (Hospedales et al., 2020), there are three common approaches to metalearning: optimization-based (Finn et al., 2017), model-based (Santoro et al., 2016), and metric-based (Snell et al., 2017).
  Optimization-based methods include those where the inner-level task is literally solved as an optimization problem, and focus on extracting meta knowledge required to improve optimization performance. In model-based methods, the inner learning step is wrapped up in the feed-forward pass of a single model. Metric-based methods perform non-parametric learning at the inner-task level by simply comparing validation points with training points and predicting the label of matching training points. Since meta-learning and the L2DNCL have the same assumption that data share the same high-level semantic features (introduced in Section 1), we link L2DNCL to meta-learning problem, providing a way to formulate and analyze the L2DNCL.
  Compared to samplers in meta-learning. Tasks in meta-learning are heterogeneous in some scenarios, which can not be handled via globally sharing knowledge among data. Therefore, it is crucial to address the task-sampling problem in meta-learning. Yao et al. (2019) assigned many tasks that are randomly sampled from different clusters using their similarities, and only used the most related task cluster for training. This method solves the task-sampling problem in the view of tasks. Liu et al. (2020a) proposed a greedy class-pair based sampling method, which selects difficult tasks according to the class-pair potentials. This method solves the sampling problem in the view of classes. In our paper, we propose CATA based on clustering rules regarding data, which is in the view of data.
sections.heading: B PROOFS
sections.text: Proof of Theorem 1.
  Proof. The key to this proof is that the optimized π̂∗ is in Πl ∩Πu. Case1. When f u ∈ Fu, according to Problem 1, let
  π̂∗ = arg min π∈Π τ(π̂(X l), f l(X l)) + τ(π̂(Xu), f u(Xu)), (12)
  where Π = {π : X → Rdr} and f u ∈ Fu. Let τ∗ = minπ∈Π,f u∈Fu J (π). If π̂∗ /∈ Πl ∩ Πu, then, according to definitions of Πl and Πu, τ∗ > l + u. This means that there exists π′ ∈ Πl ∩ Πu
  such that J (π′) = τ(π′(X l), f l(X l)) + τ(π′(Xu), f u(Xu)) = l + u < τ∗. Namely, τ∗ is not the minimum value in the set {J (π) : π ∈ Π}, which leads to a contradiction to the definition of τ∗. Case2. When f u /∈ Fu, let τ∗∗ = minπ∈Π,f u /∈Fu J (π). According to definition of u, it is clear that τ∗∗ > l + u = J (π′). Namely, τ∗∗ is not the minimum value in the set {J (π) : π ∈ Π}. L2DNC is solvable. If u = 0, according to definition of Πu, τ(π̂∗(Xu), f u(Xu)) = 0, which means that we can perfectly separate π̂∗(Xu). Namely, L2DNC is theoretically solvable.
  Proof of Theorem 2.
  Proof. If f u /∈ Fu, then we naturally have τ(π̂(Xu), f u(Xu)) > u according to the definition of u. Then, the key to this proof is that the optimized π̂∗ is in Πl. According to Problem 1,
  π̂∗ = arg min π∈Π τ(π̂(X l), f l(X l)) + τ(π̂(Xu), f u(Xu)). (13)
  Let τ∗ = minπ∈Π J (π). If π̂∗ ∈ Π − Πl, then, according to definition of Πu, u ≥ l, and maxπ∈Πl τ(π(X u), f u(Xu)) < minπ∈Π−Πl τ(π(X l), f l(X l)), we have the following inequality.
  τ∗ = J (π̂∗) ≥ τ(π̂∗(X l), f l(X l)) + u > max π∈Πl τ(π(Xu), f u(Xu)) + l. (14)
  Let π′ = arg maxπ∈Πl τ(π(X u), f u(Xu)). Since π′ ∈ Πl, we know that τ(π′(X l), f l(X l)) = l according to definition of Πl. Thus we have
  max π∈Πl
  τ(π(Xu), f u(Xu)) + l = τ(π′(Xu), f u(Xu)) + τ(π′(X l), f l(X l)) = J (π′). (15)
  Hence, we find a π′ ∈ Π such that J (π′) < J (π̂∗) = τ∗, which leads to a contradiction to the definition of τ∗. Thus, π̂∗ ∈ Πl. Based on the definition of Πu, τ(π̂(Xu), f u(Xu)) > u.
sections.heading: C L2DNCL IN THE VIEW OF META-LEARNING
sections.text: Since we address L2DNCL based on the meta-learning framework, it is interesting to analyze if L2DNCL can be addressed based on the sampled tasks T = {Ti}ni=1. We show that, under some assumptions, L2DNCL can be well addressed.
  Problem Setup of L2DNCL in the View of Meta-learning. In L2DNCL, we have a task space T ∗ = {(X, f) : X is any r.v.s defined on X , f : X → C}, a task distribution P(T ∗) defined on T ∗, a r.v. Xu, sampled tasks Ti = {X li, f li} ∼ P(T ∗) (i = 1, . . . , n), an index set I = {iu1, . . . , iuKu}, a function set F = {f : X → C}, a transformation set Π = {π : X → Rdr}, and the loss function ` : Rdr ×F → R+ that is the loss function such that, ∀f ∈ F and ∀π ∈ Π, EPX [`(π(X), f(X))] = τ(π(X), f(X)), where f l : X → Y is the ground-truth labeling function for X li, Y = {il1, . . . , ilK l}, C = Y ∪ I and PX is the distribution corresponding to a r.v. X . Based on Definitions 1 and 2, we have the following assumptions in L2DNCL.
  (A1) The union of support set of X li (i = 1, . . . , n) and the support set of Xu are disjoint, and union of underlying classes of X li (i = 1, . . . , n) are different from those of X
  u; (B1) X li is K l- li-separable with F l = {f li} and Xu is Ku- u-separable with Fu, where li =
  τ(X li, f l i(X l i)) < 1, u = minf∈{f :X→I} τ(X u, f(Xu)) < 1;
  (C1) There exist a consistent K l- li-separable transformation set Πli for X li and a consistent Ku- u-separable transformation set Πu for Xu;
  (D1) ∩ni=1Πli ∩Πu 6= ∅; (E1) There exists fu ∈ Fu such that {Xu, fu} is also drawn from the task distribution P(T ∗).
  (A1) ensures that known and novel classes are disjoint. (B1) implies that it is meaningful to separate observations from X li and X
  u. (C1) means that we can find good high-level features for X li or Xu. Based on these features, it is much easier to separate X li or X
  u. (D1) says that the high-level features of X li and X
  u are shared, as demonstrated in the introduction. (E1) represents that our target task Tt = {Xu, fu} and sampled tasks {Ti}ni=1 are from the same task distribution P(T ∗). Then, we can define L2DNCL formally.
  Problem 2 (L2DNCL). Given {Ti = {X li, f li}}ni=1 and Xu defined above and assume (A1)-(E1) hold, let meta-samples Sl = {Sl,tri ∪S l,ts i }ni=1 are drawn from the {X li}ni=1, where S l,tr i ∼(X li)m and Sl,tsi ∼(X li)k are the training set and the test set of the task Ti with the sizes m and k, respectively, and each task Ti can output an inner-task clustering algorithm A(Sl) : Xm → Π. In L2DNCL, we aim to propose a meta-algorithm A to train an inner-task clustering algorithm A(Sl) with Sl
  via minimizingR(A(Sl), {Sl,tri , f li}ni=1) = ∑n i=1 τ(A(S l)(Sl,tri )(X l i), f l i(X l i))/n. We expect that A(Sl)(Sui )(X u) is Ku- u-separable, where Su are observations of Xu with size m. Remark 3. Compared to meta-learning, L2DNCL aims to train an inner-task clustering algorithm A(Sl) : Xm → Π rather than a classification algorithm often used in meta learning. Besides, in L2DNCL, we can only observe features from the target task, while we can observe the labeled data from the new task in the meta-learning. In L2DNCL, m is a very small number.
  Then, we show that the risk used in Problem 2 can be estimated under certain conditions. Based on Problem 2, we turn the objective functionR(A(Sl), {Sl,tri }ni=1) into a more general meta-learning risk:
  R(A(Sl), P (T ∗)) = ET=(X,f)∼P (T ∗)ES∼(PX)mEx∼PX `(A(S l)(S)(x), f(x)), (16)
  R(A(Sl), P (T ∗)) is the expectation of the generalized error w.r.t. the task distribution P (T ∗) and can measure the performance of each inner-task clustering algorithm. In practice, the meta-clustering algorithm of L2DNCL is optimized by minimizing the average of the empirical error on the training tasks, called the empirical multi-task error:
  R̂(A(Sl), {Sl,F l}) = 1 n n∑ i=1 1 k ∑ xij∈Sl,tsi `(A(Sl)(Sl,tri )(xij), f l i(xij)), (17)
  where and Sli = S l,tr i ∪ S l,ts i ∼ (PXli) m. Then, the generalization bound of inner-task clustering algorithm A(Sl) of meta-based L2DNCL algorithms can be obtained from the uniform stability β of the meta-algorithm A. Definition 3 (Uniform Stability (Maurer, 2005)). A meta-algorithm A has uniform stability β w.r.t. the loss function ` if the following holds for any meta-samples S and ∀i ∈ {1, . . . , n}, ∀T = {X, f} ∼ P̃ (T ), ∀Str ∼ PmX , ∀Sts ∼ PkX : |L̂(A(S)(Str)(Sts), f(Sts))− L̂(A(S\i)(Str)(Sts), f(Sts))| ≤ β, where
  L̂(A(S)(Str)(Sts), f(Sts)) = 1
  k ∑ xj∈Sts `(A(S)(Str)(xj), f(xj)).
  Given training meta-samples S = {Stri ∪Stsi }ni=1, we modify S by replacing the i-th element to obtain Si = {Str1 ∪Sts1 , . . . , Stri−1 ∪Stsi−1, Str ′ i ∪Sts ′ i , S tr i+1 ∪Stsi+1, . . . , Strn ∪Stsn }, where the replacement sample S′i is assumed to be drawn from D and is independent from S. In addition, we modify S by removing the i-th element to obtain S\i = {Str1 ∪Sts1 , . . . , Stri−1∪Stsi−1, Stri+1∪Stsi+1, . . . , Strn ∪Stsn } In the same way, given a training set S = {z1, . . . , zi−1, zi, zi+1, . . . , zn}, we can obtain Si = {z1, . . . , zi−1, z′i, zi+1, . . . , zn} and S\i = {z1, . . . , zi−1, zi+1, . . . , zn}. Lemma 1 (McDiarmid Inequality). Let S and Si defined as above, let F : Zn → R be any measurable function for which there exits constants ci (i = 1, . . . , n) such that
  sup S∈Zm,z′i∈Z
  |F (S)− F (Si)| ≤ ci,
  then
  PS [F (S)− ES [F (S)] ≥ ] ≤ exp( −2 2∑n i=1 c 2 i ).
  Theorem 3. For any task distribution P (T ∗) and meta-samples Sl with n tasks, if a meta-algorithm A has uniform stability β w.r.t. a loss function ` bounded by M , then the following statement holds with probability at least 1− δ for any δ ∈ (0, 1):
  R(A(Sl), P (T ∗)) ≤ R̂(A(Sl),Sl) + (n, β), (18) where (n, β) = 2β + (4nβ +M) √
  log(1/δ) 2n .
  Proof. The proof of Theorem 3 mainly follows (Chen et al., 2020a).
  Let F (Sl) = R(A(Sl), P (T ∗)) − R̂(A(Sl),Sl) and F (Sl,i) = R(A(Sl,i), P (T ∗)) − R̂(A(Sl,i),Sl,i). We have |F (Sl)−F (Sl,i)| ≤ |R(A(Sl), P (T ∗))−R(A(Sl,i), P (T ∗))|+|R̂(A(Sl),Sl)−R̂(A(Sl,i),Sl,i)|. (19) The first term in Eq. (19) can be written as |R(A(Sl), P (T ∗))−R(A(Sl,i), P (T ∗))| ≤ |R(A(Sl), P (T ∗))−R(A(Sl\i), P (T ∗))|
  + |R(A(Sl,i), P (T ∗))−R(A(Sl\i), P (T ∗))|. We can upper bound the first term in Eq. (19) by studying the variation when a sample set Sli of training task Ti is deleted, |R(A(Sl), P (T ∗))−R(A(Sl\i), P (T ∗))| ≤ ET=(X,f)∼P (T ∗)ES∼(PX)mEx∼PX |`(A(S
  l)(Sl)(x), f(x))− `(A(Sl\i)(Sl)(x), f(x))| ≤ sup T=(X,f)∼P (T ∗),S∼(PX)m,x∼PX |`(A(Sl)(Sl)(x), f(x))− `(A(Sl\i)(Sl)(x), f(x))|
  ≤ β. Similarly, we have |R(A(Sl,i), P (T ∗))−R(A(Sl\i), P (T ∗))| ≤ β. So the first term of Eq. (19) is upper bounded by 2β. The second factor in Eq. (19) can be guaranteed likewise as follows, |R̂(A(Sl), {Sl,F l})− R̂(A(Sl,i), {Sl,F l})|
  ≤ 1 n ∑ q 6=i ∣∣∣∣∣∣1k ∑
  xqj∈Sl,tsq
  (`(A(Sl)(Sl,trq )(xqj), f l q(xqj))− `(A(Sl,i)(Sl,trq )(xqj), f lq(xqj))) ∣∣∣∣∣∣ + 1
  nk ∣∣∣∣∣∣ ∑
  xij∈Sl,tsi
  `(A(Sl)(Sl,tri )(xij), f l q(xij))− ∑ xij∈S′,l,tsi `(A(Sl,i)(S′,l,tri )(xij), f l q(xij)) ∣∣∣∣∣∣ ≤ 2β + M
  n .
  Hence, |F (Sl)−F (Sl,i)| satisfies the condition of Lemma 1 with ci = 4β+ Mn . It remains to bound ESl [F (Sl)] = ESl [R(A(Sl), P (T ∗))]− ESl [R̂(A(Sl), {Sl,F l})]. The first term can be written as follows,
  ESl [R(A(Sl), P (T ∗))] = ESl,S′,l,tri ,S′,l,tsi 1
  k ∑ xij∈S′,l,tsi `(A(Sl)(S′,l,tri )(xij), f l i(xij)).
  Similarly, the second term is,
  ESl [R̂(A(Sl), {Sl,F l})] = ESl  1 n n∑ i=1 1 k ∑ xij∈Sl,tsi `(A(Sl)(Sl,tri )(xij), f l i(xij))  = ESl,S′,l,tri 1 k
  ∑ xij∈Sl,tsi `(A(Sl)(S′,l,tri )(xij), f l i(xij))  = ESl,S′,l,tri ,S′,l,tsi 1 k
  ∑ xij∈S′,l,tsi `(A(Sl,i)(S′,l,tri )(xij), f l i(xij))  , where F l = {f li}ni=1. Hence, ESl [F (Sl)] is upper bounded by 2β, ESl [R(A(Sl), P (T ∗))]− ESl [R̂(A(Sl), {Sl,F l})]
  = ESl,S′,l,tri ,S′,l,tsi 1 k
  ∑ xij∈S′,l,tsi `(A(Sl)(S′,l,tri )(xij), f l i(xij))− 1 k ∑ xij∈S′,l,tsi `(A(Sl,i)(S′,l,tri )(xij), f l i(xij))  ≤ 2β.
  Plugging the above inequality in Lemma 1, we obtain
  PSl [R(A(Sl), P (T ∗))− R̂(A(Sl),Sl) ≥ 2β + ] ≤ exp ( −2 2∑n
  i=1(4β + M n ) 2
  ) .
  Finally, setting the right side of the above inequality to δ, the following result holds with probability of 1− δ, R(A(Sl), P (T ∗)) ≤ R̂(A(Sl),Sl) + 2β + (4nβ +M) √ log(1/δ)
  2n .
  By Theorem 3, the generalization bound depends on the number of the training tasks n and the uniform stability parameter β. If β < O(1/ √ n), we have (n, β)→ 0 as n→∞. Hence, given a sufficiently small β, the error R(A(Sl), P (T ∗)) converges to training error R̂(A(Sl),Sl) as the number of training tasks n grows. Theorem 3 indicates that we can minimize the risk in the L2DNCL problem in probability if we can control the uniform stability of a meta-algorithm (like MAML did via support-query learning (Chen et al., 2020a)) and sample the assumed tasks for training (sampler matters in meta discovery).
sections.heading: D DATASET INTRODUCTIONS AND SPLITS
sections.text: CIFAR-10 dataset contains 60, 000 images with sizes of 32× 32. Following (Han et al., 2019), for L2DNCL, we select the first five classes (i.e. airplane, automobile, bird, cat, and deer) as known classes and the rest of classes as novel classes. The amount of data from each novel class is no more than 5. CIFAR-100 dataset contains 100 classes. Following (Han et al., 2020), we select the first 80 classes as known classes and select the last 20 classes as novel classes.
  SVHN contains 73, 257 training data and 26, 032 test data with labels 0-9. Following (Han et al., 2019), we select the first five classes (0-4) as known classes and select the (5-9) as novel classes. OmniGlot constains 1, 632 handwritten characters from 50 different alphabets. Following (Hsu et al., 2019), we select all the 30 alphabets in background set (964 classes) as known classes and select each of the 20 alphabets in evaluation set (659 classes) as novel classes.
  E IMPLEMENTATION DETAILS
  We implement all methods by PyTorch 1.7.1 and Python 3.7.6, and conduct all the experiments on two NVIDIA RTX 3090 GPUs.
  CATA. We use ResNet-18 (He et al., 2016) as the feature extractor and use three fully-connected layers with softmax layer as the classifier. We also use BN layer (Ioffe & Szegedy, 2015) and Dropout (Srivastava et al., 2014) in network layers. In this paper, we select the number of views M = 3 for all four datasets. In other words, there are three classifiers following by the feature extractor. Both the feature extractor and 3 classifier use Adam (Kingma & Ba, 2015) as their optimizer. The number of training steps is 50 and the learning rates of feature extractor and classifiers are 0.01 and 0.001 respectively. We use the tradeoff λ of 1/3.
  MM for L2DNCL. We use VGG-16 (Simonyan & Zisserman, 2015) as the feature extractor for all four datasets. We use SGD as meta-optimizer and general gradient descent as inner-optimizer for all four datasets. For all experiments, we sample 1000 training tasks by CATA for meta training and finetune the meta-algorithm after every 200 episodes with data of novel classes. We note that the inner-tasks of OmniGlot are sampled by in order, instead of randomly sampling like other three datasets. Thus the errors of OmniGlot only come from the training procedure, while the errors of other datasets come from both sampling procedure and training procedure. The output dimension of feature extractor πmm is set to dr = 512. The meta learning rate and inner learning are 0.4 and 0.001 respectively. We use a meta batch size (the amount of training tasks per training step) of 16\8 for {CIFAR-10,SVHN}\{CIFAR-100,Omniglot}. In addition, we choose k to be 10 which is suitable for all datasets. For each training task, we update the corresponding inner-algorithm by 10 steps.
  MP for L2DNCL. We use a neural network of four convolutional blocks as the feature extractor for all datasets following (Snell et al., 2017). Each block comprises a 64-filter 3 × 3 convolution, BN layer (Ioffe & Szegedy, 2015), a ReLU function and a 2 × 2 max-pooling layer. We use the same feature extractor for embedding both training data and test data and its output dimension is set to dr = 512. For all experiments, we train the models via Adam (Kingma & Ba, 2015), and we use an initial learning rate of 0.001 and cut the learning rate in half every 20 steps. We train the feature extractor for 200 steps with 1000 training tasks sampled by CATA. The difference in sampling procedure and error source are the same with MM for L2DNCL.
sections.heading: F RESULTS OF L2DNC
sections.text: In this section, we show the results of L2DNC with abundant novel-class data in Table 3. Table 3 shows that MM is comparable with the representative methods but cannot outperform the RS and MP performs worse than MM. Compared with RS, MM samples many inner-tasks for training, while RS uses the whole data. Incomplete data makes MM unable to learn the global distribution of novel classes. MP is not as well as MM on L2DNC tasks. As the absence of labels of novel class data, we cannot finetune the model used for calculating data embedding, which is trained by known-class data. Although this model cannot adapt to novel classes, we can calculate more accurately prototypes with abundant novel-class data. Hence, with MP, the results of L2DNC are obviously better than the results of L2DNCL.
sections.heading: G COMPLEXITY ANALYSIS
sections.text: We give a brief analysis of time complexity for each algorithm. As MM and MP are two-step methods, we first analyze the sampling algorithm CATA, and then analyze the main parts of MM and MP.
  CATA The time complexity of CATA is O(E ∗D/B ∗ T ), where F is number of training tasks, E is number of epochs, D is size of dataset, B is meta batch size, and T is the time complexity of each iteration. We can future decompose O(T ) = O(L ∗ n), where L is the average time complexity of each layer, and n is number of layers. Then, we can decompose O(L) = O(M ∗N ∗K2 ∗H ∗W ), where M and N are numbers of channels of input and output, K is size of convolutional kernel, and H and W are height and weight of feature space.
  MM (Main part) The time complexity of MM is O(F ∗ E ∗ D/B ∗ T ), where F is number of training tasks, E is number of epochs, D is size of dataset, B is meta batch size, and T is the time complexity of each iteration. We can future decompose O(T ) = O(L ∗ n), where L is the average time complexity of each layer, and n is number of layers. Then, we can decompose O(L) = O(M ∗N ∗K2 ∗H ∗W ), where M and N are numbers of channels of input and output, K is size of convolutional kernel, and H and W are height and weight of feature space.
  MP (Main part) The time complexity of MP isO(F ∗E∗D/B∗T ), where F is number of training tasks, E is number of epochs, D is size of dataset, B is meta batch size, and T is the time complexity of each iteration. We can future decomposeO(T ) = O(L∗n), whereL is the average time complexity of each layer, and n is number of layers. Then, we can decompose O(L) = O(M ∗N ∗K2 ∗H ∗W ), where M and N are numbers of channels of input and output, K is size of convolutional kernel, and H and W are height and weight of feature space.
sections.heading: H RUNNING TIME
sections.text: In this section, we list the running time of MM and MP for all four datasets. The results are shown in Tabel 4 and Table 5.
sections.heading: I LINK TO DATASETS
sections.text: SVHN dataset can be downloaded from http://ufldl.stanford.edu/housenumbers/ train.tar.gz and http://ufldl.stanford.edu/housenumbers/test.tar.gz.