Meta Discovery: Learning to Discover Novel Classes given Very Limited Data
Authors: Haoang Chi
Feng Liu
Wenjing Yang
Long Lan
Tongliang Liu
Bo Han
Gang Niu
Mingyuan Zhou
Masashi Sugiyama
Venue: ICLR 2022 Spotlight (2022)

Abstract: In novel class discovery (NCD), 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 NCD are still unclear. In this paper, we demystify assumptions behind NCD and find that high-level semantic features should be shared among the seen and unseen classes. Based on this finding, NCD is theoretically solvable under certain assumptions and can be naturally linked to meta-learning that has exactly the same assumption as NCD. Thus, we can empirically solve the NCD 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 NCD: since it is unnatural to label only seen-class data, NCD 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.

Published as a conference paper at ICLR 2022
META DISCOVERY: LEARNING TO DISCOVER NOVEL CLASSES GIVEN VERY LIMITED DATA
Haoang Chi Feng Li Bo Han? Wenjing Yang"t f Long Lan't Tongliang Liu"
Gang Niu Mingyuan Zhou Masashi Sugiyama 5.7
National University of Defense Technology "Hong Kong Baptist University
University of Technology Sydney "The University of Sydney 'RIKEN AIP
'The University of Texas at Austin "The University of Tokyo
[haoangehi61e, Ennggii,,,,enenu fengliu. ml, gang. meiiumml aemmmmmmammm.m com, b comp hkbu edu. hx, [wenjing. yang, long lan @nudt edu. en, tongliang 1iu0 sydney..y..y.......... eeeddddyyy.d.eee.e.ee eddu.au mingyuan, zhou@mcccombs utexas edu,
ABSTRACT
In novel class discovery (NCD), 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 NCD are still unclear. In this paper, we demystify assumptions behind NCD and find that high-level semantic features should be shared among the seen and unseen classes. Based on this finding, NCD is theoretically solvable under certain assumptions and can be naturally linked to meta- meta-learning that has exactly the same assumption as NCD. Thus, we can empirically solve the NCD problem by meta-learning algorithms after slight modifications. This weta-leerningg-asee methodology significantly reduces the amount of unlabeled data needed for training and makes it more practical, as demonstrated experiments. The use of very limited data also justified by the application scenario of NCD: since it is unnatural to label only seen-class data, NCD 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.
INTRODUCTION
With the development of nigh-perffrmance computing, we can train deep networks to achieve various tasks well (Deng et al., 2009; Liu & Tao, 2015; Song et al., 2019; Jing et al., 2020; Song al., 2020; Liu et al., 2020b; Han et al., 2020a; Xia et al., 2020). 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 (c.g., okapi) after learning a few seen animal categories (c.g., horse and dog). Namely, human effortlessly discover (cluster) novel categories of animals. Inspired by this fact, previous works formulated a novel problem called novel class discovery (NCD) (Hsu et al., 2018; Han et al., 2019), where we train clustering model using plenty of unlabeled novel-class and labeled known-class data.
However, if NCD is labeling in causality (X + Y), there exists two issues: NCD might not be theoretically solvable problem. For example, if novel classes are completely different from known classes, then is unrealistic to use the known classes (like animals) help precisely cluster novel classes (like cars, Figure (()).. Moreover, NCD might not be a realistic problem in some scenarios where novel classes might only be seen once twice. This does not satisfy the assumptions considered in existing NCD methods. These issues naturally motivate us to find out when NCD can be theoretically solved and what assumptions are considered behind NCD.
In this paper, we revisit NCD and find that NCD will be well-defined problem if NCD is sampling in causality (Y + X), i.e., novel and known classes are sampled together (Figure 1(b)). In this
"Equal contribution. Work done when Haoang Chi remotely visited HKBU. 1 "Correponndigg author.

---

Published as a conference paper at ICLR 2022
X
Y
X
Y
Horse
Bird
Horse
Bird
Dissovering
Cat
Fish
Cat.
Fish
(a) Experts annotate data (labelling in causality).
(b) Experts sample data (sampling in causality).
Figure I: NCD aims discover novel classes (i.c., clustering novel-class data) with the help of labeled known-class data. There exists two ways to obtain data in NCD: (a) labeling in causality, e.g., we first obtain unlabeled images and then hire experts to label them and (b) sampling in causality, e.g., we are given a label set, and then sample images regarding these labels. In (a), experts have to go through all images and find novel classes. However, the novel classes (like cars) might be totally different from known classes (like animals), which makes NCD become a theoretically unsolvable problem. In this paper, we revisit NCD from (b), where novel-class data are collected on the same way of sampling known-class data. In this view, NCD can be theoretically solved, since novel classes and known classes are highly related. The yellow rectangles represent the identified novel classes.
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). Since trip to forests is relatively costly and toilsome, botanists had better sampled these scarce plants passingly for future research. From this example, 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 NCD 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. Then, we reformulate the NCD problem and show that NCD is theoretically solvable under mild assumptions (including the key assumption above). We also show an impossibility theorem for previous NCD setting. This theorem shows that 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, NCD might be an ill-defined problem if known and novel class do not share high-level semantic features.
Although NCD is theoretically solvable under mild assumptions, we still need abundant data from known and novel classes to ensure NCD can be empirically solved. However, previously, the novel classes might only be seen once or twice in some scenarios. In such scenarios, we find that previous NCD methods do not work well (Figure 2). To address the NCD given very limited data (NCDL), we link NCD to meta-learning that also assumes that known and unknown (novel) classes share the high-level semantic features (Maurer, 2005; Chen al., 2020a).
mentioned
The key difference between meta-learning and NCDL lies in their inner-tasks, In meta-learning, the inner-task a classification task, while in NCDL, it 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, 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 ProtoNer (MP)) can perform much better than existing methods in NCDL.
We conduct experiments four benchmarks and compare method with five competitive baselines (MacQueen et al., 1967; Hsu et al., 2018; 2019; Han et al., 2019; 2020b). Empirical results show that method outperforms these baselines significantly when novel-class data are very limited.
2

---

Published as a conference paper at ICLR 2022
MP
MM
RS
KCL
MCL
DTC
R-P1
CIFAR-10
SV HY
SVHN
60
60
Acc (96)
Acc (%)
60
20
50
100
50
100
50 Epoch
100
50
100
Epoch
Epoch
Epoch
(a) 5-way 5-observation (b) 5-way 1-observation
(c) 5-way 5-observation
(d) 5-way 1-observation
Figure 2: We conducted experiments on CIFAR-I0 10 and SVHN and reported the average clustering accuracy
(ACC (%), Section 5) when using existing and our methods to address the NCDL. We can observe that existing
methods cannot address the NCDL, while our methods (MM and MP) can address the NCDL well.
Moreover, we provide a new practical application the prosperous meta-learning community (Chen et al., 2020a), which lights up a novel road for NCDL.
RELATED WORK
Our proposal is mainly related to NCD, transfer learning and meta-learning that are briefly reviewed here. More detailed reviews be found in Appendix A.
Novel class discovery. NCD was proposed recent years, aiming to cluster unlabeled novel-class data according underlying categories. Compared to unsupervised learning (Barlow, 1989), NCD also requires labeled known-class data to help cluster novel-class data. The pioneering methods include the KL-Divergence-De based contrastive loss (KCL) (Hsu 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 al., 2020b). Compared to existing works (Hsu al., 2018; Zhong et al., 2021c;b), we focus on clustering unlabeled data when their quantity is very limited.
Transfer learning. Transfer learning aims leverage knowledge contained in source domains to improve the performance of tasks in target domain, where both domains are similar but different (Gong et al., 2016). Representative transfer learning works are domain adaptation (Long et al., 2018) and hypothesis transfer (Liang et al., 2020), where mainly focus on classification or prediction tasks in the target domain. NCD problem can be also regarded a transfer learning problem that aims to complete the clustering task in target domain via leveraging knowledge in source domains.
Meta-learning, Meta-learning is also known as learning-to-learn, which trains a meta-model over a wide variety of learning tasks (Ravi & Larochelle, 2017; Chen et al., 2020b; Yao et al., 2021; Wei et al., 2021). 1). 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 Hospedales et al. (2020), there are three common approaches to meta-learning: optimization-base 2017). model-based (Santoro 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 few) unlabeled novel data from the same dataset.
(Finn et al.,
3 ASSUMPTIONS BEHIND NCD AND ANALYSIS OF SOLVABILITY
Since NCD focuses on clustering novel-class data, we first show definitions regarding the separation of random variable (r.v.) X ~ IPx defined on X C RRd. Then, we give formal definition of NCD and introduce assumptions behind NCD. Finally, we present one theorem to show NCD 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 (K---Separable r.v.). Given the E.. X ~ Px, X is K-c-separable with a non-empty function set F = (f X + if F
f(X,f(X))
max (X BxI(()==) =c,
(1)
i.jELizj
3

---

Published as a conference paper at ICLR 2022
Color
Frame
We can cluster these objects using at least three rules, i.e, colors, shapes and frames. Motivated by the rule of clustering, when ad- dressing the NCDL problem, need to sam- ple inner-tasks, where data share the rule (Algorithm 1).
Shape
Figure 3: When sampling tasks for meta discovery, need to about clustering rules.
where I = fii,-. ,,,] is index set, f(X) is induced r.v. whose source of randomness is X exclusively, and Rx|s(x)== = (I)())))))) is the support set of P Px)s(X)=i.
In equation 1, .): represents the largest overlap between any different clusters in the sense of the probability measure Px. c 0, then we can perfectly partition observations of X into K clusters using some distance-basee based clustering algorithm, c.g., , K K-means (MacQueen et al., 1967). However, when X' is complex space and the dimension d is much larger than the intrinsic dimension of X (e.g., images), is not reliable to measure the distance between observations from 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 non-linear transformation 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 al., 2020b). Let π X' + Rd. be a transformation where d, is the reduced dimension and d, < and we expect that the transformed r.v. (XX) can be K Kee-separable as well. Namely, we hope the following function set exists.
Definition 2 (Consistent K- K-e-separable Transformation Set). Given E... X that is K K-e-separable with a function set F, a transformed Ev. x(X) is -esparbbe with F Fff F,
T (X), == max P PT(X) (Rx (Xx(1XX))))) n ( =6, i.JEI,tj
(2)
where π. : > Rd a trunsformation. Then, a consistent K-e-sepurable transformation set is non-emply set II satisfying that VJ E F,Vn TI,,(x((),
Remark 1. If dr < and = O, we will need much less observations to estimate the density of (X) compared to X, thus it will be much easier perfectly separate (XX) than X. For example, there probably exists a linear function Rd. + I such that S(X)
T(X). )). It is clear that such linear function g is easier to find than directly finding f using K-means.
Problem Setup of NCD. Based on the above definitions, we will formally define the NCD problem below. In NCD, we have two r.v.s X X defined on X, the ground-truth labeling function f X + Y for X and function set F = {f X + I}. where y = (i...... i and I = {i).... K Based on Deñinitions and 2, we have the following assumptions NCD.
(A) The support set of X and the support set of X" are disjoint, and underlying classes of X are different from those of X (i.e., I n y 0);
(B) X is K Re---baearable with F { and X is K" seear-bee with Fu, where el 7 T(X,, (x')) < and e" = min 7 7(X", (xx") < 1;
(C) There exist a consistent sepe--eeera transformation set 11f for X and consistent leeh----eprableee transformation set IT for X":
(D) II' 1 + 0.
(A) ensures that known and novel classes are disjoint. (B) implies that it is meaningful to separate observations from X and X (C) means that we can find good high-level features for X' or X Based on these features, it is much easier to separate X' or X". (D) says that the high-level features of X and X" are shared, as demonstrated in the introduction. Then, we can define NCD formally.
Problem 1 (NCD). Given X!, X" and fl defined above and assume (A)-(D) hold, in NCD, we aim to learn function î X - Rd. via minimizing J(t) (()) where fe E F and d, & d. We expect that 7 (X") is K" -separabe....le.
+ (ff(X"), (X")))
Theorem 1 (NCD is Theoretically Solvable). Given X!, X" and f defined above and assume (A)-(D) hold, then 7t (X") is K" -eparrbee If 0, then NCD is theoretically solvable.
4

---

Published as a conference paper at ICLR 2022
Theorem I means that it is possible to find good transformation ā such that (X") is separable although we introduce X Then we show that NCD might be ill-defined if (D) does not hold.
Theorem (Impossibility Theorem). Given X3, X and f defined above and assume (A)-(C) hold, < min II (x(X',, fo (X')),, (D) does not hold and é¹ S c", then (I(X"), > e", where 11 { X + [R and f" F..
m'max=em (
Remark 2. Condition =ax ((x()x),, f"(x)) < minzen-m (x"). ((XX)) 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, e' S E" indicates that the transformations in X is more separable than X".
In previous setting, data acquiring process is unclear. As we discussed, if NCD is labelling in causality, then novel and known classes might not share high-level semantic features (Figure (a)). Namely, (D) might not hold, resulting in that X might bring negative effects under some conditions (Theorem 2). Thus, based
Theorems and 2, it is clear that (D) plays key role in NCD, which also justifies that NCD 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 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).
Based on Theorem 1, if there are abundant observations to estimate J(+), then we can find the optimal transformation मे to help obtain good partition for observations from X However, as discussed before, the novel classes might only be seen once or twice in some scenarios. In such scenarios, we find that previous NCD methods do not work well empirically (Figure 2). To address the NCD given very limited data (NCDL), we link NCD 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 NCD. Thus, it is natural to address NCDL by meta-learning.
4 META DISCOVERY FOR NCDL
Meta-leamnng has been widely used to solve few-shot learning problems (Chen 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 a data point to update meta algorithm. Compared to meta-learning, the inner-task of NCDL 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 NCDL a definition from the view of meta-learning and further prove NCDL is theoretically solvable. In this section, we let S = {(a), u²) i = 1, I,..., I,...,n') be known-class data drawn from r.v. (X), ('(x')) and y! E (1...., K.). and let Su {œ.] : == 1...., , } be unlabeled novel-class data drawn from r.v. X", where 0 < n" < n!
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-ulle-wware 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 always one view few views that dominated for each instance, and these dominated views are similar with high-level semantic meaning (Li et al., 2019b; Liu et al., 2020d; 2021a). Therefore, we propose to use dominated views to replace with clustering rules, and design a novel task-sampling method called clustering-rule-awee Algorithm 1). CATA is based on a multi-view network containing feature extractor G X - Rd. and M classifiers {F; Rdd, + Y), (Figure 4). M is empirically chosen according to the data complexity. Specifically, CATA learns 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
task sampler (CATA,
Note that, the objective of clustering problem is different from that of NCD. In clustering problem, we aim find via minimizing (fx()", f" (XX)) rather than ((())),, f(x))) (("))))
5

---

Published as a conference paper at ICLR 2022
R
View
View2
CATA novel sampling method of meta-lcarning for NCDL. Here we show the inference process of assigning labeled data of known classes to three different views with the well-trained G and {F.) V(x) is the voting function defined as Eq. (4). The weights of the first layers of Fi, F2, and P's are constrained or- thogonal mutually.
View
S
G
E
DNN
V x
Well-trained
bail-ba
Figure 4: The structure of the clustering seeeiiing-ree-aweee rule-aware task sampler (CATA).
The feature extractor G provides the shared data representations for M different classifiers {F, {F.), JMM Each classifier classifies data based on its own view. The feature extractor G learns from all gradients from (F.) 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 F; and Fj as an example, we add the term [WTW,l to the sampler's ' loss function, where W; and Wj denote the weight vectors of the first fully connected layer of F; and F, respectively. [W tending to means that F; and Fj are nearly independent (Saito et al., 2017). Thus, the loss function of CATA is defined follows,
M N
Ls(Oc, (100):00p)))) (
Σ MN i=
(o G(a)))))))
2A
Σ if
WTW,,
(3)
M(M 1)
where lee the standard cross-entropy loss function and À is trade-off parameter.
After we obtain the well-trained feature extractor G and classifiers (F; M we input training data point to our sampler and then we will get the probabilities that belongs to class y each classifier, i.e.
where y is the label of x. Therefore, the view which belongs to is defined as
V (x) = arg max P.(y)a))
Now we have assigned a data point to M subsets according to their views, i.c. (V. E V(x) = +J,, 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 a heuristic method, and we will give clustering rule formal definition and explore the reason why CATA succeed thcoretically in the future.
Realization of Meta Discovery with MAML (MM). Here, we solve the NCDL problem based on MAML. A feature extractor Tmm X' + Rdd is given to obtain an embedding of data, following a classifier g with the output dimension equalling to the number of novel classes (K")), As novel classes share the same high-level semantic features of known classes, the feature extractor Tam should be applicable to known and novel classes. The key idea that similar data should belong to the same class. For data pair 1y), let 8ij = 1 if they come from the same class; otherwise, Sij = 0.
Following Han et al. (2020b), we adopt more robust pairwise similarity called ranking statistics. For 24 mmm (x,) and 2; mm mm,(x, we rank the values of 2; and 2, by the magnitude. Then we check if the indices of the values of top-k ranked dimensions are the same. Namely, $; = if they are the same, and 8ij = 0 otherwise. We use the pairwise similarities to train feature extractor Tum and classifier layer, so the inner product g(24)T9(( 9(2)) is the cosine similarity between 2; and Zy. which serves as the score for whether I; and vy belong to the same class. After sampling training tasks [Ti we train model by the inner algorithm that optimizes the binary cross-entropy (BCE) loss function:
as pseudo labels As mentioned above, is a classifier with softmax
LT, (fgormm)) n!!
Biy log(o(z)) g(())) + -ii) log(1 - g(z,)" 9(2,)))
(5)

---

Published as a conference paper at ICLR 2022
Algorithm 1 Clustering-mlle-aware task sampler (CATA)
Input: known-class data 5", feature extractor classifiers Fi Fihe1 learning rates w1, W2; view index: j. Initialize 0g (0r, )
for 1,...,T do
2: Compute Le and (Vo,, Ls fi using St and Ls in Eq. (3);
3: Update 8. 90 wh V (0a; {0p, pad 0r, = dr. w2 Vor, Ls(Oo, (0p, 141 h=1). I,..,, M.
end
4: Compute (F:(C(z'))} to obtain (P: w ] for each (a' .2) E s Compose V/= f (V = ff using function in Eq. (4), = 1,..., M
6: Sample an inner-task (S ,./1t) ~~ V Output: an inner-task T,
Algorithm 2 MM for NCDL.
Input: known-class data: S" learning rate: a, 1/: feature extractor: Tmmi classifier: I: Initialize 0g gom=mm² while done do
2: Sample tasks {Ti (S) s/iht) ~ S by CATA (Alg. 1);
for all T, do
3: Evaluate Vogenmm LT, (mgo using Sh and LT, in Eq. (5);
Compute adapted parameters: Og 0gammm a Aggmmmm CT, (0go
end
5: Update Ogommm
0gammm V Mynrmm Ca (fgoxmm) using each St.t and LA in Eq. (6);
end
Output: clustering algorithm A.
Entire procedures of NCDL by MAML are shown in Algorithm Following MAML, the parameters of clustering algorithm A are trained by optimizing the following loss function:
LA (fggommmm)) ) = Σ (6. guTmm
V
Ogommm Ly.
(ggmmm)) )),
(6)
1=1
where a >> 0 is the learning rate of the inner-algorithm. Then we conduct the meta-optimization to update the parameters of clustering algorithm A follows:
0 000 OgosTam 17 @gommm LA (0(Oromam)
where 17 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 perform line 4 and line in Algorithm with S
Realization of Meta Discovery with ProtoNet (MP). Following Snell et al. (2017), we denote Tmp as feature extractor, which maps data their representations. In training task T,, the mean vector of representations data from class-s (i.e., $1.5
is defined as prototype Ca:
sl.t Ci.a (S
Σ (ala))es))
Tmp (mp(2))
(8)
| a
Here, we define the Euclidean distance dist Rdd x Rd [0, +00) measure the distance between data from the test set and the prototype. Then, we represent p(y = s(x) using the following equation.
exp( Aop(-dis((TTam)) Tmp (x), c.))
p(y = s|æ:) Σ. exp(- dist( mp (x) c,)))
We train the feature extractor by optimizing the negative log- log-probability. i.c. logp(y s|x). So the loss function of ProtoNet is defined as follows:
Lr, 1
Σ
Σ
logp(y = s|x),
(10)
KE(KY) mEs
7

---

Published as a conference paper at ICLR 2022
Algorithm 3 MP for NCDL.
Input: known-class data: 5" learning rate: "y; feature extractor: Tmp
1: Initialize 'xmpp' while done do
for all episodes do
2: Sample K" elements from {1, ,l,...,K K'} set Cs;
3: Sample tasks T. = (S) S/ ~ St I'EE, by CATA (Alg. 1);
for in C2 do
4: Sample m training data of class-a, i.c., S/ S & |s| m;
Compute e; ( using Eq. (8); Sample test data class-s, ie.. S/.52 s/:t | end
7: Update 0mpp
Oxmp
VV 0rmp Lr, (Bamp) using haec,
hee, and C in Eq. (10);
end
end
Output: feature extractor Tmp-
MP
MM
RS
KCL
MCL
DTC
CIFAR-100
100
OmniGlot
100
Ommü]ot
Acc (50)
Acc (%)
Acc (1)
Acc (16)
80
30
60
50
100
50
100
50
100
100
Epoch
Epoch
Epoch
Epoch
(a) 20- 20-way 1-observation (b) 20-way 5-observation (c) 20-way 1-observation (d) 20-way 5-observation
Figure 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 NCDL problem. The experimental results showed that MM and MP tend to outperform existing methods.
where [K"] denotes the K" classes selected from {I...., K'). sl.ta is the test set of labeled data of class-s from task T. The full procedures of training mp are shown Algorithm 3, After training the feature extractor Tmp well, we use the training set of S to obtain the prototypes. For æ in the test set of S" we compute the distance between x and each prototype, and then the class corresponding to the nearest prototype is the class of œ.
5 EXPERIMENTS
Baselines. To verify the performance of our meta-based NCDL methods (i.e., MM and MP), we compare them with competitive baselines, including K-means (MacQueen al., 1967), KCL (Hsu et al., 2018), MCL (Hsu et al., 2019), DTC (Han et al., 2019), and RS (Han et al., 2020b). 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., 201 1), and OmniGlot (Lake et al., 2015). Detailed introductions and partitions of known classes and novel classes of these four datasets Appendix D. Following the protocol few-shot learning (Park et al., 2018; Liu et al., 2019b; Wang et al., 2020; Ziko et al., 2020), for SVHN and CIFAR-11 10, we perform the few-observation tasks of 5-way L-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 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 follows,
1 d(v))}.
(11)
E N
8

---

Published as a conference paper at ICLR 2022
Table 1: Ablation Study on four datasets. In this table, we report the ACC standaad deviation of
ACC (%) on four datasts, where w/o represents "without". is clear that CATA improves the ACC.
Methods
MM
MM w/o CATA
MP
MP wio CATA
S-observation
47.3++0.3
40,1=0,3 39.7#0044
61,0+:05
60.50022
SVHN (5-way)
1-observation
42.7=0.33
52.8004
50.2=00.3
5 observvttion
45.3:20.1
42.7::0.3
58.51002
$7.9:2.11
CIFAR- (5 (S-way)
observation
41.3:10.4
4..3..0.3
51.710.2
4..6....2
S-observation
42.0:10.4
39.9:10.3
45.5+10.3
44.1=20.1
CIFAR-100 (20-way)
1-observation
39.2=00.2
37.1
38.8+0.4
37.0=0.2
S.observation
82.1
80.1 78.5+0.44
98.440022 94.6+-0.3
96.7-0.33
OmniGlot (20-way)
1-observation
77.3=+0.4
91.2=002
where yi 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- R-10. As shown 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-clas, data in the sampling process. Besides, as shown in Table 2 in Appendix F, 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- 5-way 1-observation, RS performs 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 relatively large and the data distribution of CIFAR- 1000 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- K-means is an unsupervised method that requires many training data. As a simple benchmark 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. Note that, we also show results of all methods on NCD problem in Table 3 (Appendix G).
Ablation study. To verify the effectiveness of CATA, we conduct ablation study by removing CATA from MM and MP. According to Table 1, 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 (= | + |St.ta| = + 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.
6 CONCLUSIONS
In this paper, we study an important problem called novel class discovery (NCD) and demystify the key assumptions behind this problem. We find that NCD is sampling instead of labeling in causality, and, furthermore, data in the NCD problem should share high-level semantic features. This finding motivates us to link NCD 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-learnigg based methods outperform all existing baselines when addressing more challenging problem NCD given very limited data (NCDL) where only few novel-class data can be observed, which lights up a novel road for NCD/NCLL.

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENTS
This work was partially supported by the National Natural Science Foundation of China (No. 91948303-1, No. 61803375, No. 12002380, No. 62106278, No. 62101575, No. 61906210) and the National Grand R&D Plan (Grant No. 2020AAA0103501), BH was supported by NSFC Young Scientists Fund No. 62006202 and RGC Early Career Scheme No. 22200720. TLL was supported by Australian Research Council Projects DE-19010144 and DP-220102122 MS was supported by JST CREST Grant Number JPMJCR18A2.
8 ETHICS STATEMENT
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, discriminationniis//aaiin concerns, privacy and security issues, legal compliance, and research integrity issues.
REPRODUCIBILITY STATEMENT
To ensure the reproducibility of experimental results, we have provided codes of MM and MP at github.com//aoangg//MED..
REFERENCES
Horace Barlow. Unsupervised learning. Neural computation, 1(3):295-111, 1989.
Avrim Blum and Tom M. Mitchell. Combining labeled and unlabeled data with co-training. In COLT; 1998.
Jiaxin Chen, Xiao-Ming Wu, Yanke Li, Qimai LII, Li-Ming Zhan, and Fu-Lai Chung. A closer look at the training strategy for modern meta-learning. NeurlPS, 2020a.
Xiaohan Chen, Zhangyang Wang, Siyu Tang, and Krikamol Muandet. MATE: plugging in model awareness to task embedding for meta learning. NeurlPS, 2020b
Haoang Chi, Feng Liu, Wenjing Yang, Long Lan, Tongliang Liu, Bo Han, William K. Cheung, and James T. Kwok. TOHAN: one-step approach towards sew-shot hypothesis adaptation. In NeurlPS, 2021.
Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large-scale hicrarchical image database. In CVPR, 2009.
Jiahua Dong, Yang Cong. Gan Sun, Bineng Zhong, and Xiaowei Xu. What can be transferred: Unsupervised domain adaptation for endoscopic lesions segmentation. In CVPR, 2020.
Jiahua Dong, Yang Cong, Gan Sun, Zhen Fang, and Zhengming Ding. Where and how to transfer: Knowledge aggregation-induued transfcrability perception for. unsupervised domain adaptation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021a.
Jiahua Dong, Zhen Fang, Anjin Liu, Gan Sun, and Tongliang Liu. Confidemt-nncho--nnduueed multi-source-free free domain adaptation. In NeurIPS, 202
Charles Elkan and Keith Noto. Learning classifiers from only positive and unlabeled data. In KDD, 2008.
Tongtong Fang, Nan Lu, Gang Niu, and Masashi Sugiyama. Rethinking importance weighting for deep learning under distribution shift. In NeurlPS, 2020.
Zhen Fang, Jie Lu, Anjin Liu, Feng Liu, and Guangquan Zhang. Learning bounds for open-set learning. In ICML, 2021a.
10

---

Published as a conference paper at ICLR 2022
Zhen Fang, Jie Lu, Feng Liu, Junyu Xuan, and Guangquan Zhang. Open set domain adaptation: Theoretical bound and algorithm. IEEE Transactions on Neural Networks and Learning Systems, pp. -3092 2021b.
Enrico Fini, Enver Sangineto, Stéphane Lathuilière, Zhun Zhong, Moin Nabi, and Elisa Ricci. unified objective for novel class discovery. In ICCV, 2021.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In ICML, 2017.
Spyros Gidaris, Praveer Singh, and Nikos Komodakis. Unsupervised representation learning by predicting image rotations. In ICLR, 2018.
Mingming Gong, Kun Zhang, Tongliang Liu, Dacheng Tao, Clark Glymour, and Bernhard Schölkopf. Domain adaptation with conditional transferable components. In ICML, 2016.
Bo Han, Gang Niu, Xingrui Yu, Quanming Yao, Miao Xu, Ivor Tsang, and Masashi Sugiyama. Sigua: Forgetting may make learning with noisy labels more robust. In ICML,, 2020a.
Kai Han, Andrea Vedaldi, and Andrew Zisserman. Learning to discover novel visual categories via deep transfer clustering. In ICCV, 2019.
Kai Han, Sylvestre-Alviss Rebuffi, Sébastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Automatically discovering and learning new visual categories with ranking statistics. In ICLR. 2020b.
Kai Han, Sylvestre-Alvise Rebuffi, Sébastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman. Autonovel: Automatically discovering and learning novel visual categories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2021.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recogmition. CVPR, 2016.
Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey. Meta-learning in neural networks: survey, WxXYv:2004.05439, 2020.
Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira. Learning to cluster in order to transfer across domains and tasks. In ICLR, 2018.
Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira. Multi-class classification without multi-class labels. In ICLR, 2019.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In ICML, 2015.
Xuhui Jia, Kai Han, Yukun Zhu, and Bradley Green. Joint representation learning and novel category discovery on single- and multi-modal data. In ICCV, 2021.
Yibo Jiang and Nakul Verma. Meta-learning to cluster. arXiv: 1rXiv:1910.111 1910. 2019.
Yongcheng Jing, Xiao Liu, Yukang Ding, Xinchao Wang, Errui Ding, Mingli Song, and Shilei Wen. Dynamic instance normalization for arbitrary style transfer. In AAAI, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR, 2015.
Ryuichi Kiryo, Gang Niu, Marthinus C Du Plessis, and Masashi Sugiyama. Positive-unlabeled learning with non-negative risk estimator. NeurIPS, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. 2009.
IIja Kuzborskij and Francesco Orabona. Stability and hypothesis transfer learning. In ICML. 2013.
Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 132262266)1132-133336 2015.

---

Published as a conference paper at ICLR 2022
Aoxue Li, Tiange Luo, Tao Xiang, Weiran Huang, and Liwei Wang. Few-shot learning with global class representations. In ICCV, 2019a.
Xiao-Li Li and Bing Liu. Learning from positive and unlabeled examples with different data distributions. In ECML, 2005.
Yingming Li, Ming Yang, and Zhongfei Zhang. A survey of multi-view representation learning. IEEE Transactions Knowledge and Data Engineering, 31(100)1863-1188 2019b.
Jian Liang, Dapeng Hu, and Jiashi Feng. Do we really need access the source data? source hypothesis transfer for unsupervised domain adaptation. In ICML, 2020.
Chenghao Liu, Zhihao Wang, Doyen Sahoo, Yuan Fang, Kun Zhang, and Steven C. H. Hoi. Adaptive task sampling for meta-learning. In ECCV, 2020a.
Feng Liu, Jie Lu, Bo Han, Gang Niu, Guangquan Zhang, and Masashi Sugiyama. Butterfly: A panacea for all difficulties in wildly unsupervised domain adaptation. In NeurlPS Workshop on Learning Transferable Skills, 2019a.
Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J. Sutherland. Learning deep kernels for non-parametric two-sample tests. ICML, 2020b.
Feng Liu, Guangquan Zhang, and Jie Lu. Heterogeneous domain adaptation: An unsupervised approach. IEEE Transactions on Neural Networks and Learning Systems, 31(12):5588-562. 2020c.
Lu Liu, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang. Attribute propagation network for graph zero-shot learning. In AAAI, 2020d.
Lu Liu, Tianyi Zhou, Guodong Long, Jing Jiang, Xuanyi Dong, and Chengqi Zhang. Isometric propagation network for generalized zero-shot learning. In ICLR, 2021a.
Tongliang Liu and Dacheng Tao. Classification with noisy labels by importance reweighting. IEEE Transactions pattern analysis and machine intelligence, 38(3)4477-41,, 2015.
Yanbin Liu, Juho Lee, Minseop Park, Saehoon Kim, Funho Yang, Sung Ju Hwang, and Yi Yang. Learning to propagate labels: Transductive propagation network for few-shot learning. In ICLR, 2019b.
Yanbin Liu, Juho Lee, Linchao Zhu, Ling Chen, Humphrey Shi, and Yi Yang. multi-mode modulator for multi-domain few-shot classification. In ICCV, 2021b.
Mingsheng Long, Zhangjie Cao, Jianmin Wang, and Michael I. Jordan. Conditional adversarial domain adaptation. In NeurIPS, 2018.
James MacQueen et al. Some methods for classification and analysis of multivariate observations. In Proceedings of the fifth Berkeley symposiun on mathematical statistics and probability, 1967.
Andreas Maurer. Algorithmic stability and meta-learning. Journal of Machine Learning Research, 967-994, 2005.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Ng. Reading digits in natural images with unsupervised feature learning. In NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Gang Niu, Marthinus Christoffel du Plessis, Tomoya Sakai, Yao Ma, and Masashi Sugiyama. Theo- retical comparisons of positive-unlabeled learning against positive-negative learning. NeurIPS, 2016.
Minseop Park, Saehoon Kim, Jungtaek Kim, Yanbin Liu, and Seungjin Choi. Taeml: Task-adaptive ensemble of meta-learners. In NeurlPS Workshop on Meta learning, 2018.
Tiago Ramalho and Marta Garnelo, Adaptive posterior learning: few-shot learning with a surprise- based memory module. In ICLR, 2019.
12

---

Published as a conference paper at ICLR 2022
Sachin Ravi and Hugo Larochelle. Optimization as model for few-shot learning. In ICLR, 2017.
Kuniaki Saito, Yoshitaka Ushiku, and Tatsuya Harada. Asymmetric tri-training for unsupervised domain adaptation. In ICML, 2017.
Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy P. Lillicrap. Meta-leaming with memory-augmenteer neural networks. In ICML, 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. In ICLR, 2015.
Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning. In NeurlPS, 2017.
Jie Song, Yixin Chen, Xinchao Wang, Chengchao Shen, and Mingli Song. Deep model transferability from attribution maps. In NeurlPS, 2019.
Jie Song, Yixin Chen, Jingwen Ye, Xinchao Wang, Chengchao Shen, Feng Mao, and Mingli Song. DEPARA: deep attribution graph for deep knowledge transferability. In CVPR, 2020.
Nitish Srivastava, Geoffrey E. Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(1): 19091999999988 2014.
Boyu Wang, Jorge A. Mendez, Mingbo Cai, and Eric Eaton. Transfer learning via minimizing the performance gap between domains. In NeurlPS, 2019.
Yaqing Wang, Quanming Yao, James T Kwok, and Lionel M Ni. Generalizing from a few examples: survey on few-shot learning. ACM Computing Surveys, 53(3)1-34, 2020.
Ying Wei, Peilin Zhao, and Junzhou Huang. Meta-learning hyperparameter performance prediction with neural processes. In ICML, 2021.
Xiaobo Xia, Tongliang Liu, Bo Han, Nannan Wang, Mingming Gong, Haifeng Liu, Gang Niu, Dacheng Tao, and Masashi Sugiyama. Part-dependent label noise: Towards instance-dependent label noise. NeurIPS, 2020.
Junyuan Xie, Ross B. Girshick, and Ali Farhadi. Unsupervised deep embedding for clustering analysis. In ICML, 2016.
Huaxiu Yao, Ying Wei, Junzhou Huang, and Zhenhui Li. Hierarchically structured meta-learning In ICML., 2019.
Huaxiu Yao, Longkai Huang, Linjun Zhang, Ying Wei, Li Tian, James Zou, Junzhou Huang, and Zhenhui Li. Improving generalization meta-learning via task augmentation. In ICML, 2021.
Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neighborhood contrastive learning for novel class discovery. In CVPR, 2021a.
Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe. Neighborhood contrastive learning. In CVPR, 2021b.
Zhun Zhong, Linchao Zhu, Zhiming Luo, Shaozi Li, Yi Yang, and Nicu Sebe. Openmix: Reviving known knowledge for discovering novel visual categories an open world. In CVPR, 2021c.
Joey Tianyi Zhou, Ivor W. Tsang, Sinno Jialin Pan, and Mingkui Tan. Multi-class heterogeneous domain adaptation. Journal of Machine Learning Research, 20(57): 2019.
Imtiaz Masud Ziko, Jose Dolz, Eric Granger, and Ismail Ben Ayed. Laplacian regularized few-shot learning. /CML, 2020.
13

---

Published as a conference paper at ICLR 2022
A DETAILED RELATED WORK
Novel class discovery. NCD is proposed in recent years, aiming to cluster unlabeled novel-class data according to their underlying categories (Han al., 2021; Jia et al., 2021). Compared with unsupervised learning (Barlow, 1989), NCD also requires labeled known-class data to help cluster novel-class data. The pioneering methods include KI.D-based contrastive loss (KCL) (Hsu et al., 2018), meta classification likelihood (MCL) (Hsu et al., 2019), deep transfer clustering (DTC) (Han ct al., 2019), rank statistics (RS) (Han et al., 2020b), OpenMix (Zhong et al., 2021c), neighborhood contrastive learning (NCL) (Zhong et al., 2021a), and unified objective (UNO) (Fini et al., 2021). In this paper, we update and present the results of our methods regarding NCD.
In KCL (Hsu et al., 2018), method based on pairwise similarity is introduced. They first pre-treeee tre-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 the supervision information to train the main model. Then, MCL (Hsu et al., 2019) changed the loss function of KCL (the KI.-divergence based contrastive loss) 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., 2020b), 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.
In OpenMix (Zhong et al., 2021c), they proposed mix known-class and novel-class data to learn a joint label distribution, benefiting to find their finer relations.
In NCL (Zhong et al., 2021a), they used neighborhood contrastive learning to learn discriminate features with both the labeled and unlabeled data with the local neighborhood to take the knowledge from more positive samples. In addition, they used the hard negative generation to produce hard negative to improve NCL..
In UNO (Fini et al., 2021), they used pseudo-labels in combination with ground-trute labels in a UNified Objective function (UNO) that enabled better cooperation and less interference without self-supervised learning.
Meta-Lcarning, Meta-learning is also known as learning-to-learn, which train a meta-model over large variety of learning tasks (Ravi & Larochelle, 2017; Liu et al., 2019b; 2021b). In meta-learning, often assume that data share the same high-level features, which ensures that meta- meta-learning can be theoretically addressed (Maurer, 2005). According to (Hospedales et al., 2020), there are three common approaches to meta-learning: optimization-base (Finn al., 2017), model-based (Santoro et al., 2016), and metric-based (Snell et al., 2017).
Optimization-basee methods include those where the inner-level task is literally solved as optimiza- tion problem, and focus on extracting meta knowledge required to improve optimization performance. In model- 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 NCDL have the same assumption that data share the same high-level semantic features (introduced in Section 1), we link NCDL to meta- leta-learning problem, providing a way to formulate and analyze the NCDL.
Positive-unlabeldd learning, Dositive-unlabeld (PU) learning (Li Liu, 2005) an important branch of semi-supervised learning, aiming to learn a binary classifier with positive data and unlabeled data. Thus, PU learning is a special case of NCD, where there exists only one known class and one novel class. The basic solution is to view unlabeled data negative data to train standard classifier (Elkan & Noto, 2008). Niu et al. (2016) gives the conditions when PU learning outperforms supervised learning through upper bounds estimation errors. Kiryo et al. (2017) proposes non-negative risk estimator to prevent flexible models overfitting on negative data in PU learning.
Transfer learning. Transfer learning aims to leverage knowledge contained in source domains to improve the performance of tasks in a target domain, where both domains are similar but different (Gong al., 2016; Long al., 2018; Zhou al., 2019; Liu et al., 2019a; Wang et al., 2019; Liu et al.,
14

---

Published as a conference paper at ICLR 2022
2020c; Liang et al., 2020; Chi et al., 2021; Fang et al., 2021a:b). Representative transfer learning works are domain adaptation (Gong et al., 2016; Long et al., 2018: Zhou et al., 2019; Liu et al., 2019a; 2020c; Dong et al., 2020; 2021b;a) and hypothesis transfer (Kuzborskij & Orabona, 2013; Liang et al., 2020; Chi et al., 2021), which mainly focus on classification or prediction tasks in the target domain. NCD problem can be also regarded transfer learning problem that aims complete the clustering task in a target domain via leveraging knowledge in source domains.
Compared to samplers in meta-lcarning. 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 task- sampling problem in meta-learning. Yao 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.
B MAIN THEORETICAL RESULTS
Theorem 1 (NCD is Theoretically Solvable). Given X) X and f defined above and assume (A)-(D) hold, then (X") is K" -eeea-separable If = 0, then NCD is theoretically solvable.
Proof. The key to this proof is that the optimized R" is in II' II..
Casel. When f E F2, according Problem let
-arg min TEl
+
(12)
where =I= (TT: X + Rd. } and 1 E Fi. Let m [TT). If & II' n II. then, according to definitions of IT' and IT. r² > c This means that there exists x' E IT' ITu such that [xx) = ((T((X)),, ((')) + (f"), minimum value in the set (J(x)
e' + <². Namely, T" is not the 11), which leads to a contradiction to the definition of r"
Case2. When f" & Fu, let 7M = mi /upp [TT). According to definition of e", is clear that T" > d e" = J (T'). Namely, 7" is not the minimum value in the set (J(x): π E II}.
NCD is solvable. If e" O, according to definition of 111, -(* (X"))) 0, which means that we can perfectly separate A (X"). Namely, NCD is theoretically solvable.
Theorem 2 (Impossibility Theorem). Given X\, X and f desinedd above and assume (A)-(C) hold, ((x")) < min -I r(x(()) (x))),, (D) does not hold and èl < c", then
if famaxeem (x("),, ('())) T("(X") (((X)) > c", where II {i X - Rd and fü E F.
Proof. If fd & Fu, then we naturally have (x(",, " (x"))) > c" according to the definition of c". Then, the key to this proof is that the optimized A* is in 11 According to Problem 1,
A
arg min T (*(X)), tlll
(*("",,,,""
(13)
Let T* = enn e I (T). i E Il - 11', then, according to definition of 11", e" 2 d. and max (TT(X",, (x))) min min ((T( (('')), we have the following inequality.
7" J (** 2 T ( (x'), (x)))
max T (X"),, sem
+ cd.
(14)
Let n = arg max T( (X"), (X")). Since E II', we know that T( fx)) = c
((()))
according to definition of II' Thus we have
+ ((x)) (T'). max (6 TEI
(15)
Hence, we find x E II such that J(T') < J(*)) = -" which leads to a contradiction to the definition of 7 Thus, 4 E IT. Based on the definition of IT", ((*"), ((x) > e". n
15

---

Published as a conference paper at ICLR 2022
C NCDL IN THE VIEW OF META-LEARNING
Since we address NCDL based the meta-learning framework, it is interesting analyze if NCDL can be addressed based on the sampled tasks T = {Ti We show that, under some assumptions, NCDL can be well addressed.
Problem Setup of NCDL in the View of Meta-learning. NCDL., we have a task space T {(X, X is any r.v.s defined on X, f X + C), task distribution P(T defined on T L.V. X", sampled tasks T, = fX] ~ P(T') (i l.......... n), an index set I = { k= a function set F = {f: X + C). transformation set II {Ir X + RR }. and the loss function
f: Rd F R that is the loss function such that, Vff E F and VT II, Ep [X( f(x))
(() f())), where f X + y is the ground-truti tround-truth labeling function for X. 3' (o...... kit.
C= UUU and Px is the distribution corresponding to r.v. X. Based Definitions 1 and have the following assumptions in NCDI..
(A1) The union of support set of X! (i 1, ,,..., and the support set of X are disjoint, and union of underlying classes of X! (i = 1, 1,..., n) are different from those of X":
(B1) x is T TX,, f(()))
with F {ft} and X" is K""-"-separabll with F", where cj = 1, e" min T(X", f(x") <;
(C1) There exist consistent K- -eparabee transformation set NI for X! and consistent K -eeea-see transformation set 11" for X";
(D1) 11 II" II / 0;
(E1) There exists f" E F" such that (X", fr} 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! and X". (C1) means that we can find good high-level features for X! or X". Based on these features, it is much easier to separate X! or X (D1) says that the high-level features of X! and X" are shared, as demonstrated in the introduction. (E1) represents that our target task T = {X", [r] and sampled tasks (Ti) are from the same task distribution P(T*). Then, we can define NCDL formally.
Problem 2 (NCDL). Given (T; (X,, fiD= and X defined above and assume (AI)-(EI) hold, let meta- metp-ss S = {S..tu U S. are drawn from the {X!]==> where -(()) and s/ (X!)" are the training set and the test set of the task Ti with the sizes m and k, respectively, and each task To can output an inner-task clustering algorithm A(S') : xm + II. In NCDL, we aim to propose a meta-algorithm to train an inner-task clustering algorithm A(S') with S! via minimizing R, f..Yim) = E.= (AA (x!). (xx)))((()))/++ We expect that (( (X")) is -e=-"-separable, where St are observations of X" with size m.
Remark 3. Compared to meta-learning, NCDL aims to train an inner-task clustering algorithm A(S m - II rather than a classification algorithm often used in meta learning. Besides, in NCDL, 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 NCDL, m a very small number.
Then, we show that the risk used in Problem can be estimated under certain conditions. Based on Problem 2, turn the objective function R(A(S"), (S/ > into a more general meta-learning risk:
R(AAS)), = BT-....- E.r
(16)
R(A(S)), P(T))) ) is the expectation of the generalized error w.r.t. the task distribution P(T*) and measure the performance of each inner-task clustering algorithm. In practice, the meta-clustering
algorithm of NCDL is optimized by minimizing the average of the empirical error on the training tasks, called the empirical multi-task error:
(SA
Σ (A(())(s)"))(a)) ((rg)), B.yES)
(17)
16

---

Published as a conference paper at ICLR 2022
where and S S U S
(Fx!) Then, the generalization bound of inner-task clustering
algorithm A(S)) of meta-based NCDL 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 B w.r.t. the loss function if the following holds for any mamalss S and Vi {l....,n} VT = fx. P(T). 4SS ~ P VS ~ x
L(A ((A(S)(5)(())) ((A(S))("""((SS))((( 3
where
(5*))) 1 Σ (A(S))")(o))(())))) EYESU
Given training meta-samples S= {S Ji- we modify by replacing the i-th element obtain
S = (Stt U Si...... S U. S US S US Sh U 5%h,, where the replacement sample S is assumed to be drawn from D and is independent from S. In addition, modify S by removing the i-th element to obtain S { US$ ................................ S US i-1 i4 US 1 Str U
In the same way, given training set S {-1,...; 24 R1; Ze4
obtain S
{21,-.., 21 2/1 2. Zn) and S (21, 2i-1; 2.,1,...; 2
Lemma 1 (McDiarmid Inequality). Let S and S defined above, let F n - measurable function funcaioon
TR be any
for which there exits constants C, (i = 1...., n) such that
[F(S) F(S') s cz. SEZM,2EE
sup
then
Ps(F(S) - Bs(FF() 2 expl -2e²
Σ c2
Theorem For any task distribution P(T*) and meta-samples 5 with n tasks, if meta-algorithm A has uniform stability 3 w.r.. a loss function E bounded by M, then the following statement holds with probability at least for any (0. 1):
R(A(S)) )(T))) S S)) -
(18)
where 3)n,3) = =5 + (4nB + M)
log 1/5)
2n
Proof. The proof of Theorem mainly follows (Chen et al., 2020a).
Let F(S)) = R(A(S)), P(T")) R(A(S)), and F(S = R(A(SL))
R. We have
|F(S))FF(S S
(19)
The first term in Eq. (19) be written
((AA(S), ) -
+
- -(AT))))(()))
We can upper bound the first term in Eq. (19) by studying the variation when sample set S of training task To is deleted,
RR(ASS)) - )
< E PTS En ((AAA//1(111)))00000000001111111
<
T=0X.D)-PTT)S--PP-"" KAA191GH1O..TTD)--AAA44s1yy111,0
sup
$ S.
17

---

Published as a conference paper at ICLR 2022
Similarly, have (R(A(S)), P(T))) - ), P(T))) 2 3. So the first term of Eq. (19) is upper bounded by 23. The second factor in Eq. (19) can be guaranteed likewise as follows, RR(ASS)), (, F)) ") F
Σ
Σ
(((A (Ias) (((x)))) ((A(S)))))))))))))) (Eas)) (( fg f((()))))
$ 9tt
1
Σ
Σ (5, ((r)) fo my
+ nk
M
$ 28
n
x. Egi [F(S)) = Es: (AA Es (R(A(S)), (8), FI])]. The first term can be written as follows,
Hence,
[F(S)) - F( (().i) satisfies the condition of Lemma I with ai 4, + M It remains to bound
(R(AA()),
s of k aig ES
1
Σ ((A ((s))
Similarly, the second term is,
Es (R(A(S)), (S), [')] = Ess
Σ (A( A(rrs)))
ZGES
E ht
Σ ((t")) (xts), f((or))))
aisEst
= E st st st
Σ
((s (xxs)) ((ass)
Z.JEST
where Fl (f.) Hence, Es [F(S)] is upper bounded by 23,
Eg (R(A(R))) P(T)))
1
Σ TISES
1 k
Σ (( (xis)) A(xs)))
k
28.
Plugging the above inequality in Lemma 1, we obtain
-2c
Pst (s(RR((()) - - S 2 23 + + exp
Di=1
(4, +
Finally, setting the right side of the above inequality to 8, the following result holds with probability of 1-55 5,
log(1/6)
R(A(S'),P(T)) < R(A(())) 23 + (4n M)
2n
By Theorem 3, the generalization bound depends on the number of the training tasks and the uniform stability parameter 3. If B < 0(1/v/) we have c(n, - 0 as - 0o. Hence, given sufficiently small B, the error R(A(S),, P(T*)) converges to training enror Ri R(A(S)), S as the number training tasks n grows. Theorem indicates that we can minimize the risk in the NCDL problem in probability if we control the uniform stability of meta-algorithm (like MAML did via support-quer learning (Chen et al., 2020a) and sample the assumed tasks for training (sampler matters in meta discovery).
18

---

Published as a conference paper at ICLR 2022
Table 2: Results of K-means on all four datasets.
Dataset
CIFAR-I0 (5-way)
SVHN (5-way)
CIFAR-10 (20-way)
OmniGlot (20-way)
1-observation
30.2.13.60
23.5=0.66
9.711118
1.010.16 2.8.1..13
5-observation
32.8.12.13
23.7-0.35
12.4.11.15
D DATASET INTRODUCTIONS AND SPLITS
CIFAR-10 dataset contains 60, 000 images with sizes of 32 x 32. Following (Han et al., 2019), for NCDL, 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-T00 dataset contains 100 classes. Following (Han al., 2020b), 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 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 R8 (He et al., 2016) as the feature extractor and use three fully-connecter 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 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 NCDL. We use VGG-16 (Simonyan & Zisserman, 2015) as the feature extractor for all four datasets. We SGD meta-optimizer and general gradient descent 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 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 Tym is set to d, 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, 10,SVHN) (CIFAR 100, Omniglot)
addition, we choose be 10 which suitable for all datasets. For each training task, we update the corresponding inner-algorithm by 10 steps.
MP for NCDL. We use neural network of four convolutional blocks as the feature extractor for all datasets following (Snell et al., 2017). Each block comprises 64-filter 3 x convolution, BN layer (loffe & Szegedy, 2015), a ReLU function and a 2 x 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 d,- = 512. For all experiments, we train the models via Adam (Kingma & Ba, 2015), and learning rate of 0.001 and cut the learning rate 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 NCDL.
an initial
F RESULTS OF K-MEANS
This section shows the results of our methods and all the baselines in Table 2.
19

---

Published as a conference paper at ICLR 2022
Table 3: Results of NCD with abundant novel class data. In this table, we report the ACC standard deviation of ACC (%) of baselines and our methods (MM and MP) given abun- dant novel class data. We still evaluate these methods on four benchmarks (SVHN, CIFAR-10, CIFAR-100, and OmniGlot).
Methods
K-means
KCL
MCL
DTC
RS
MM
MP
SVHN
42.6#0.0
21.4#0.6
38.6+10.8
6.99
95.2=0.2
93.1 77.1
CIFAR-10
65.5+10.0
66.5
64.24+0.1
87.5++0.3
91.7.10.9
92.34.0.9 73.2+:1.
CIFAR 100 56.6#1.6
1..3+1.3
21.333
56.7+1.2
75.2=4.2
6.
58.3+2.2
OmniGlot
77.2
82.4
83.3
89.0
89.1
88.6++0.7
98.4+-0.2
G RESULTS OF NCD
In this section, we show the results of NCD 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 well MM on NCD tasks. As the absence of labels of novel class data, cannot finetune the model used for calculating data embedding, which is trained by known-class data. Although this model cannot adapt novel classes, abundant novel-class data. Hence, with MP, the results of NCD are obviously better than the results of NCDL.
calculate more accurately prototypes with
H COMPLEXITY ANALYSIS
We give 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.
The time complexity CATA is O(E D/B * T), where 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) = ( * n), where I. is the average time complexity of each layer, and n is number of layers. Then, can decompose ((L)
CATA
number of training tasks, E
O(M N K2 x 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.
D/B * T), where F is number of training tasks, E is number of epochs. D is size of dataset, B 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 (LL) = 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 and W are height and weight of feature space.
MM (Main part) The time complexity of MM O(F D E
MP (Main part) The time complexity of MP is O(F E+ D/+T)T) where F is number of training tasks, E is number of epochs, 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 (L)) O(M N & K2 * Hf * 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.
size of dataset, B is meta batch size, and is the time complexity
20


Reviews:
[{"review_id": "vz6UmQ100oW", "reviewer": "Reviewer_iZHD", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n+ This paper is well-written and easy to follow. The motivation of the new setting of NCD is clear.\n\n+ This paper considers the problem of NCD in a new perspective and rigorously formulates the NCD setting. \n\n+ A theoretical analysis is provided to demonstrate when the NCD setting can be solved. In addition, they reveal that NCD can be solved if known and novel classes are related. They also show a result to see how NCD fails if one key assumption is not satisfied. The authors give detailed algorithms and the source code, which can help readers better understand and reproduce the proposed method.\n\n+ Extensive experiments are provided to verify the effectiveness of the proposed method. Also, all the results include the standard deviation, which is important for reflecting the real improvements on the CIFAR and SVHN datasets.\n\nCons:\n\n- It is interesting to see a formulation of NCD problem. In this formulation, we can know when the labeled data can help cluster novel-class data. However, the connection between the theory and solution is not very strong. It is better to move some parts in the Appendix to the main context. Using meta-learning to define L2DNCL is also an interesting part. \n\n- In Definition 1, why do you need to set an equation here? Is it better to consider an inequality? It is like that the separation is less and \\epsilon? A similar question follows in Definition 2.\n\n- It is not appropriate to say “Impossibility Theorem for Previous Setting”. I admit that previous studies do not consider NCD based on some basic assumptions, but they still propose many working algorithms for NCD. Thus, I recommend deleting the “Previous Setting”. You can add some explanations below Theorem 2. \n\n- The pipeline of meta-learning should be introduced clearly. The connection between Sections 3 and 4 is somehow weak. I understand that meta-learning is suitable for few-shot situations. However, it is not good to use this as the motivation of your method. It is not easy to know how to use the output of Algorithm 2. I found that L2DNCL is demonstrated in Appendix, which is much clear. You can consider swapping some descriptions from Appendix to the main context.\n\n- When training the pairwise loss, did you use different outputs for the labeled data and unlabeled data? That is, using outputs with C_l-dim for the labeled data while outputs with C_u-dim for the unlabeled data.\n\n- How to sample the training data without the CATA? I did not see the trivial sampling procedure for MEDI.\n\n- How about include the results of K-means in all figures? I did not get the point why you need Table 1.", "summary_of_the_paper": "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.", "summary_of_the_review": "Overall, this is an interesting paper, which reformates the problem of NCD to a more realistic setting. In addition, this paper builds a connection between meta-learning and NCD and presents an effective approach to address the introduced problem. Extensive experiments are provided to verify the effectiveness of the proposed method. Some statements and implementation details are not very clear, I would like to see the response of the authors.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "TgYd8uHaGYJ", "reviewer": "Reviewer_ueqR", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I found this paper very interesting. The authors provide a definition and insight into a problem that is often approach with little rigor or formalization. Further, the formalization gives good motivation for the proposed methods MM and MP. However, CATA is less well explained.\n\nMy understanding is that CATA learns a low-dimension projection and set of orthogonal classifiers. It then assigns each training point to a group defined by which of the orthogonal classifiers was most strongly activated by the observation. Meta learning inner tasks are then sampled from each group. It is unclear to me what exactly this aims to accomplish. I think the authors should explain the task-sampling problem in meta learning more completely. \n\nTypo on page 6. \"For $z_i = \\pi_{mm}(x_i)$ and $z_i = \\pi_{mm}(x_j)$\" should be $z_i = \\pi_{mm}(x_i)$ and $z_j = \\pi_{mm}(x_j)$\".\n\n", "summary_of_the_paper": "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.", "summary_of_the_review": "The theoretical framing of the L2DNC problem is valuable, as it can help us understand what is necessary to solve this problem effectively. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5NMuDDudqcL", "reviewer": "Reviewer_V9Yq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Learning to discover novel classes (L2DNC) is a challenging task,\nwhere the learnability conditions are not entirely clear. The work\ncontributes to formalize some intuitive notions of learnability in\nterms of epsilon-separation and consistent transformation sets,\nlisting the assumptions that are needed for L2DNC to be learnable.\n\nThe need for a shared transformation/representation, that is one of\nthe results of the formalization, is sensible but clearly not\nnovel. On the other hand, the author introduce a multi-view learning\nthat intuitively makes sense as a way to help clustering to focus on\nthe correct semantic features, but its connection with the formal\ntreatment is less clear. \n\nResults are reasonably well-discussed, and include both few-data (the\nsetting of the paper) and large-data results (where performance\ndifference shrink, as expected) are well as ablation studies.\n\nMinor points:\n\nWhy \"X is K-epsilon-separation\" ? should it be K-epsilon-separable or something?\n\n", "summary_of_the_paper": "The paper introduces meta-discovery as a way to adapt meta-learning\nstrategies to the problem of learning to discover novel classes. It\nalso presents a formalization of the problem that helps shading light\non the conditions under which it is learnable.\n\nThe authors additionally introduce a novel sampling strategy aimed at\nsampling data having the same \"dominant\" view to help the following\nclustering procedure.\n\nThe experimental evaluation shows advantages over existing recent\ncompetitors when the number of examples for unseen classes is small.", "summary_of_the_review": "A useful formalization of the conditions under which L2DNC works.\n\nAn intuitively sensible multi-view based meta discovery algorithm\nshown to outperform existing alternatives in the low-data regime.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "3eTULa9zNZ8", "reviewer": "Reviewer_o2Tq", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Pros:\n\n1.  The analysis of solvability is very interesting. Since we only need to cluster novel classes, it seems that introducing additional data is useless. In this paper, the authors answer this question and point when L2DNC is a meaningless problem. This point might affect the development of the L2DNC. Confirming the boundary of solvability of L2DNC is important since we can naturally do the clustering task with novel classes themselves.\n\n2. Considering few-observation situations make L2DNC methods be used in more practical scenarios.\n\n3. The proposed method can improve the performance with large margins, which is important to the field. CATA is also a new sampler to the meta-learning field (ablation studies verify the effectiveness of CATA as well).\n\n4. Interacting with meta-learning provides more possibilities to improve the performance according to SOTA meta-learning methods. The meta discovery is a general framework to address L2DNCL.\n\nCons:\n\n1. I feel struggling when I first read this paper. Figure 1(a) misleads me and lets me think that L2DNC aims to detect novel classes. You should explain L2DNC at first in the caption of Figure 1.\n\n2. I cannot follow the benefits of the sampling process (Y->X). The difference between X->Y and Y->X should be discussed in detail in introduction (it is important to make readers understand them in the introduction).\n\n3. K-epsilon-separation r.v. is a very interesting concept. However, I am not sure why we need \\tau=\\epsilon rather than \\tau<\\epsilon. The latter seems more natural.\n\n4. There is a typo in (2), it should be \\mathbb{P}_{\\pi(X)} rather than \\mathbb{P}_{X}, which makes me very confused when I read (2).\n\n5. From two theorems, Assumption (D) is indeed an important assumption for L2DNC problem. However, the connection between (D) and Y->X is not very clear. I find that (D) is not the sufficient and necessary condition of Y->X. More discussions are needed here. You cannot simply say that Y->X means (D). From my experience, (D) contains more situations. So, what are these situations?\n\n6. The condition used in Theorem 2 should be explained in natural language. \n\n7. Directly introducing meta-learning (using “few”) is not good. At least, you should introduce meta-learning based on (D) or Y->X.\n\n8. Expect for CATA, are there new components in MM or MP?  \n\n9. Experiments look nice, but I am interesting to know why MP can have such good performance in OmniGolt.\n", "summary_of_the_paper": "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. \n\nNevertheless, 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. \n", "summary_of_the_review": "The current version is a borderline paper because some important parts seem unclear to me. The presentation should be polished, and the connections among sections should be strengthened. I expect a better version after the discussion period.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers believe that this paper is valuable, and the authors have made a significant, careful contribution.

Some suggestions from the area chair:
- "in causality" is not a standard technical term and also not non-technical idiomatic English, so it should be explained the first time it is used.
- The authors should briefly cite and discuss research on so-called positive and unlabeled (PU) learning. This seems like the special case where there is exactly one known class and one novel class. The distinction between sampling in causality and labeling in causality appears in the PU literature, though not under this name.
- The authors could also mention the obvious but surprising point that if data are generated by two clusters, then a classifier can be learned using exactly one labeled example--not even one from each class.
- I have read the reference EJ A’Court Smith. Discovery of remains of plants and insects. _Nature_, 1874 and I fail to see its relevance. It is only one paragraph. Work from the 1800s should not be cited merely to suggest a veneer of scholarliness.
- The writing uses italics for emphasis much too often.
Decision: Accept (Spotlight)