# Demystifying Assumptions in
Learning to Discover Novel Classes

Haoang Chi Equal contributions. Institute for Quantum Information $\&$ State
Key Laboratory of High Performance Computing, National University of Defense
Technology  Feng Liu∗ DeSI Lab, AAII, University of Technology Sydney  Wenjing
Yang  Institute for Quantum Information $\&$ State Key Laboratory of High
Performance Computing, National University of Defense Technology  Long Lan
Institute for Quantum Information $\&$ State Key Laboratory of High
Performance Computing, National University of Defense Technology  Tongliang
Liu  TML Lab, University of Sydney  Bo Han  Department of Computer Science,
Hong Kong Baptist University
Gang Niu  RIKEN Center for Advanced Intelligence Project  Mingyuan Zhou
University of Texas at Austin  Masashi Sugiyama  RIKEN Center for Advanced
Intelligence Project  Graduate School of Frontier Sciences, University of
Tokyo

###### Abstract

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 rigorous definition of
L2DNC is _unexplored_ , which results in that its implicit assumptions 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. This naturally motivates us to link L2DNC to _meta-learning_ that has
exactly the same assumption as L2DNC. Based on this finding, L2DNC is not only
theoretically solvable, but can also be empirically solved by meta-learning
algorithms after slight modifications. This L2DNC 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.

##  1 Introduction

With the development of high-performance computing, we can train deep networks
to achieve various tasks well [5, 36, 16, 37, 22]. 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)
[12], where we train a clustering model using _plenty of_ unlabeled novel-
class and labeled known-class data.

(a) Experts annotate data (labelling in causality).

(b) Experts sample data (sampling in causality).

Figure 1: Two ways to obtain data in L2DNC: (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 can go through all images and find out
novel classes. However, the novel classes (like cars) might be totally
different from known classes (like animals), which makes L2DNC a theoretically
unsolvable problem. In this paper, we revisit L2DNC from (b), where novel-
class data are collected on the same way of sampling known-class data. In this
view, L2DNC can be theoretically solved, since novel classes and known classes
are highly related. The yellow rectangles represent the identified _novel_
classes.

However, there exists two issues in L2DNC: 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_ , 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) [34]. 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 [39]. After demystifying the key assumption
behind L2DNC, we find that this assumption is exactly the same as the
underlying assumption of meta-learning [3, 27]. Hence, we naturally link L2DNC
to meta-learning.

Based on the definition of meta-learning, we formulate the L2DNC problem
rigorously. As a result, L2DNC is not only theoretically solvable (Theorem 1),
but can also be empirically addressed by wisely modified meta-learning
approaches. More importantly, based on our formulation and meta-learning
mechanism, we can focus on a more challenging problem setting: _L2DNC given
very limited data_ (L2DNCL), i.e., how to cluster novel classes given very
limited data, which is the most challenging part in L2DNC and previous methods
cannot address this situation well (Figure 2). Recall the issues mentioned
previously, it is clear that both issues are well addressed after finding the
key assumption behind L2DNC and linking L2DNC to meta-learning.

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_ (MEDI). 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 MEDI using two representative meta-learning methods: _model-agnostic
meta-learning_ (MAML) [6] and _prototypical network_ (ProtoNet) [35]. Figure 2
demonstrates that existing L2DNC methods cannot address L2DNCL tasks well;
while our methods (i.e., MEDI-MAML and MEDI-PRO) can perform much better.

We conduct experiments on four benchmarks and compare our method with five
competitive baselines [26, 12, 13, 9, 8]. 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 [3], which lights up a novel road for
L2DNCL.

##  2 Problem Formulation

This section presents a plain definition and a rigorous definition for the
L2DNCL problem.

(a) C-$10$ $5$-way $5$-obsv

(b) C-$10$ $5$-way $1$-obsv

(c) S $5$-way $5$-obsv

(d) S $5$-way $1$-obsv

Figure 2: We conducted experiments on CIFAR-10 (C-10) and SVHN (S) and
reported the _average clustering accuracy_ (ACC (%), Section 6) when using
existing and our methods to address the L2DNCL problem. Note that “obsv” means
observation, which is the number of novel-class data per class we can observe.
We can observe that existing methods cannot address the L2DNCL problem, while
our methods (MEDI-MAML and MEDI-PRO) can address the L2DNCL problem well.

A plain definition. In L2DNCL, we have a dataset consisting of labeled known-
class data
$S^{\mathrm{l}}=\\{(x_{i}^{\mathrm{l}},y_{i}^{\mathrm{l}}):i=1,\dots,n^{\mathrm{l}}\\}$
and unlabeled novel-class data
$S^{\mathrm{u}}=\\{x_{i}^{\mathrm{u}}:i=1,\dots,m\\}$, where $0<m\ll n^{l}$.
The label space of $S^{\mathrm{l}}$ and the label space of $S^{\mathrm{u}}$
are disjoint but $S^{\mathrm{l}}$ and $S^{\mathrm{u}}$ share high-level
semantic features. The number of classes in $S^{\mathrm{l}}$ and the number of
classes in $S^{\mathrm{u}}$ are $K^{\mathrm{l}}$ and $K^{\mathrm{u}}$,
respectively. Our goal is to leverage the prior knowledge of $S^{\mathrm{l}}$
to assign the data in $S^{\mathrm{u}}$ into a certain number of clusters
(denoted as $C^{\mathrm{u}}$) according to their categories. In the following,
we give a rigorous definition of L2DNCL according to the definition of meta-
learning.

A rigorous definition. Let
$\mathcal{T}^{*}=(\mathcal{D}^{\mathrm{l}},\ell,\mathcal{H})$ be the task
space, where $\mathcal{D}^{\mathrm{l}}$ is a distribution over domain
$\mathcal{X}\times\mathcal{C}$,
$\mathcal{H}=\\{h:\mathcal{X}\rightarrow\mathcal{C}\\}$ is the hypothesis
space, $\mathcal{C}$ contains indices of categories (including known and novel
categories), and the loss function
$\ell:\mathcal{H}\times\mathcal{X}\rightarrow\mathbb{R}^{+}$ means the loss
incurred by predicting an output $h(x)$ when the ground-truth cluster index is
$c$. The rigorous definition of the L2DNCL problem is given as follows.

######  Problem 1 (L2DNCL).

Given the training tasks
$\bm{T}=\\{\mathcal{T}_{i}=(\mathcal{D}_{i}^{\mathrm{l}},\ell,\mathcal{H})\\}_{i=1}^{n}$
drawn from a task distribution $P(\mathcal{T}^{*})$, meta-samples
$\bm{S}^{\mathrm{l}}=\\{S_{i}^{\mathrm{l,tr}}\cup
S_{i}^{\mathrm{l,ts}}\\}_{i=1}^{n}$ are drawn from the training tasks
$\bm{T}$, where
$S_{i}^{\mathrm{l,tr}}{\sim}(\mathcal{D}_{i}^{\mathrm{l}})^{m}$ and
$S_{i}^{\mathrm{l,ts}}{\sim}(\mathcal{D}_{i}^{\mathrm{l}})^{k}$ are the
training set and the test set of the task $\mathcal{T}_{i}$ with the sizes $m$
and $k$, respectively, and each task $\mathcal{T}_{i}$ can output an inner-
task clustering algorithm
$\bm{A}(\bm{S}^{\mathrm{l}}):\mathcal{X}^{m}\to\mathcal{H}$. In L2DNCL, we aim
to propose a meta-algorithm $\bm{A}$ to train an inner-task clustering
algorithm $\bm{A}(\bm{S}^{\mathrm{l}})$ with the meta-samples
$\bm{S}^{\mathrm{l}}$. The trained $\bm{A}(\bm{S}^{\mathrm{l}})$ should have a
good performance on the new task
$\mathcal{T}_{\mathrm{ne}}=(\mathcal{D}_{\mathrm{ne}}^{\mathrm{l}},\ell,\mathcal{H})\sim
P(\mathcal{T}^{*})$ where we can only observe features (i.e.,
$x\in\mathcal{X}$) from the distribution
$\mathcal{D}_{\mathrm{ne}}^{\mathrm{l}}$. Specifically, the trained
$\bm{A}(\bm{S}^{\mathrm{l}})$ should learn a hypothesis
$h^{*}=\bm{A}(\bm{S}^{\mathrm{l}})(S^{\mathrm{u,tr}}_{\mathrm{ne}}):\mathcal{X}\to\mathcal{C}$
with $S^{\mathrm{u,tr}}_{\mathrm{ne}}$ such that $h^{*}(x)$ is the right
cluster index of $x$, where $S^{\mathrm{u,tr}}_{\mathrm{ne}}$ is the feature
set of
$S^{\mathrm{tr}}_{\mathrm{ne}}\sim(\mathcal{D}_{\mathrm{ne}}^{\mathrm{l}})^{m}$
and $(x,c)\sim\mathcal{D}_{\mathrm{ne}}^{\mathrm{l}}$.

######  Remark 1.

Compared to meta-learning, L2DNCL aims to train an inner-task clustering
algorithm $\bm{A}(\bm{S}^{\mathrm{l}}):\mathcal{X}^{m}\to\mathcal{H}$ rather
than a classification algorithm often used in meta learning. Besides, in
L2DNCL, we can only observe features from the new task, while we can observe
the labeled data from the new task in the meta-learning. Since we can only
observe few data from the new task in L2DNCL, $m$ is a very small number.

##  3 Meta Discovery (MEDI) for L2DNCL

According to Problem 1, 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, the inner-task 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_ (MEDI).

In L2DNCL, sampling training tasks $\bm{T}$ from the distribution of known
classes $P(\mathcal{T}^{*})$ is important, which affects the final results
directly. Since the clustering rules may not be unique (Figure 3), different
data take on various rules. If we sample data with different rules to compose
a training task, these data will influence each other, resulting in misleading
the training procedures of the inner-tasks. Namely, sampling independently and
identically (like MAML) cannot contribute to obtaining a good performance when
addressing the L2DNCL problem. Thus, in MEDI, it is a key to propose a new
task sampler that takes care of clustering rules.

###  3.1 CATA: Clustering-rule-aware Task Sampler

From the perspective of multi-view learning [2], data usually contain
different feature representations. Namely, data have multiple views. However,
there are always one view or a few views that are dominate for each instance,
and these dominated views are similar in the high-level semantic meaning [20,
23, 24]. Therefore, we propose to use dominated views to replace with
clustering rules. To this end, we propose a novel task-sampling method called
_clustering-rule-aware task sampler_ (CATA, Algorithm 1), which is based on a
multi-view network that contains a feature extractor
$G:\mathcal{X}\to\mathbb{R}^{h}$ and $K$ classifiers
$\\{F_{i}:\mathbb{R}^{h}\to\mathcal{Y}\\}_{i=1}^{K}$ (Figure 4).

We can cluster these objects using at least three rules, i.e., colors, shapes
and frames. Motivated by the rule of clustering, when addressing the L2DNCL
problem, we need to sample inner-level tasks, where data share the same rule
(Algorithm 1).

Figure 3: When sampling tasks for MEDI, we need to care about clustering
rules.

The feature extractor $G$ provides the shared data representations for $K$
different classifiers $\\{F_{i}\\}_{i=1}^{K}$. Each classifier classifies data
based on its own view. The feature extractor $G$ learns from all gradients
from $\\{F_{i}\\}_{i=1}^{K}$. 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_{i}$ and $F_{j}$ as an
example, we add the term $|W_{i}^{T}W_{j}|$ to the sampler’s loss function,
where $W_{i}$ and $W_{j}$ denote the weight vectors of the first fully
connected layer of $F_{i}$ and $F_{j}$ respectively. $|W_{i}^{T}W_{j}|$
tending to $0$ means that $F_{i}$ and $F_{j}$ are nearly independent [31].
Therefore, the loss function of our sampler is defined as follows,

$\mathcal{L}_{\mathrm{S}}(\theta_{G},\\{\theta_{F_{i}}\\}_{i=1}^{K})=\frac{1}{NK}\sum_{j=1}^{K}\sum_{i=1}^{N}\ell_{\mathrm{ce}}(F_{j}\circ
G(x_{i}),y_{i})+\frac{2\lambda}{K(K-1)}\sum_{i\neq j}|W_{i}^{T}W_{j}|,$ (1)

where $\ell_{\mathrm{ce}}$ is the standard cross-entropy loss function and
$\lambda$ is a trade-off parameter.

After we obtain the well-trained feature extractor $G$ and classifiers
$\\{F_{i}\\}_{i=1}^{K}$, 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. $\\{P_{i}(y|x)\\}_{i=1}^{K}$, where $y$ is the label of $x$.
Therefore, the view which $x$ belongs to is defined as

$V(x)=\arg\max\limits_{i}P_{i}(y|x).$ (2)

Now we have assigned a data point to $K$ subsets according to their views,
i.e. $\\{V_{i}=\\{x\in\mathcal{X}:V(x)=i\\}\\}_{i=1}^{K}$. Then, we can
directly randomly sample a certain number of data (e.g., $N$-way, $K$-obsv)
from one subset to compose a training task $\mathcal{T}_{i}$. According to the
proportion of the number of data in each subset, we sample training tasks with
different frequencies.

###  3.2 Two Realizations of MEDI

We consider two representative meta-learning methods, MAML and ProtoNet to
solve the L2DNCL problem. Namely, we will realize MEDI using MAML (MEDI-MAML)
and ProtoNet (MEDI-PRO).

MEDI-MAML. Here, another feature extractor $\Psi$ is given to obtain an
embedding of data, following a classifier $g$ with the softmax layer. As
novel-class data come from the same distribution as known-class data, the
feature extractor $\Psi$ should be applicable to the known and novel classes
as well. The key idea is that similar data should belong to the same class.
For data pair $(x_{i},x_{j})$, we denote by the symbol $s_{ij}=1$ if they come
from the same class; otherwise, $s_{ij}=0$.

Following [8], we adopt a more robust pairwise similarity called _ranking
statistics_. For $z_{i}=\Psi(x_{i})$ and $z_{i}=\Psi(x_{j})$, we rank the
values of $z_{i}$ and $z_{j}$ by the magnitude. Then we check if the indices
of the values of top-$k$ ranked dimensions are the same. Namely, $s_{ij}=1$ if
they are the same, and $s_{ij}=0$ otherwise.

CATA is a novel sampling method of meta-learning for L2DNCL. Here we show the
inference process of assigning labeled data of known classes to three
different views with the well-trained $G$ and $\\{F_{i}\\}_{i=1}^{3}$. $V(x)$
is the voting function defined as Eq. (2). The weights of the first layers of
$F_{1}$, $F_{2}$, and $F_{3}$ are constrained to orthogonal mutually.

Figure 4: The structure of the _clustering-rule-aware task sampler_ (CATA).

Input: known-class data $S^{\mathrm{l}}$, feature extractor $G$, classifiers
$\\{F_{i}\\}_{i=1}^{K^{\mathrm{l}}}$, learning rates $\omega_{1}$,
$\omega_{2}$ .

1: Initialize $\theta_{G}$ and $\\{\theta_{F_{i}}\\}_{i=1}^{K^{\mathrm{l}}}$;

for  _$t=1,\dots,T$_ do

2: Compute $\nabla_{\theta_{G}}\mathcal{L}_{\mathrm{S}}$ and
$\\{\nabla_{\theta_{F_{i}}}\mathcal{L}_{\mathrm{S}}\\}_{i=1}^{K^{\mathrm{l}}}$
using $S^{\mathrm{l}}$ and $\mathcal{L}_{\mathrm{S}}$ in Eq. (1);

3: Update
$\theta_{G}=\theta_{G}-\omega_{1}\nabla_{\theta_{G}}\mathcal{L}_{\mathrm{S}}(\theta_{G},\\{\theta_{F_{i}}\\}_{i=1}^{K^{\mathrm{l}}})$
and

$\theta_{F_{i}}=\theta_{F_{i}}-\omega_{2}\nabla_{\theta_{F_{i}}}\mathcal{L}_{\mathrm{S}}(\theta_{G},\\{\theta_{F_{i}}\\}_{i=1}^{K^{\mathrm{l}}})$,
$i=1,\dots,K^{\mathrm{l}}$;

end for

4: Compute $F_{i}(G(x))$ to obtain $\\{P_{i}(y|x)\\}_{i=1}^{K^{\mathrm{l}}}$
for each $x\in S^{\mathrm{l}}$;

5: Compose $V_{i}=\\{x:V(x)=i\\}$ using $V$ in Eq. (2),
$i=1,\dots,K^{\mathrm{l}}$;

Output: $\\{V_{i}\\}_{i=1}^{K^{\mathrm{l}}}$

Algorithm 1 Clustering-rule-aware task sampler (CATA)

We use the pairwise similarities $\\{s_{ij}\\}_{1\leq i,j\leq N}$ as pseudo
labels to train our feature extractor $\Psi$ and classifier $g$. Therefore, we
convert L2DNCL from a clustering problem to a classification problem. As
mentioned above, $g$ is a classifier with the softmax layer, so the inner
product $g(z_{i})^{T}g(z_{j})$ is the cosine similarity between $x_{i}$ and
$x_{j}$, which serves as the score for whether $x_{i}$ and $x_{j}$ belong to
the same class. After sampling training tasks
$\\{\mathcal{T}_{i}\\}_{i=1}^{n}$, we will train a model by the inner
algorithm that optimizes the following _binary cross-entropy_ (BCE) loss
function:

$\mathcal{L}_{\mathcal{T}_{i}}(\theta_{g\circ\Psi})=-\frac{1}{N^{2}}\sum_{i=1}^{N}\sum_{j=1}^{N}[s_{ij}\log(g(z_{i})^{T}g(z_{j}))+(1-s_{ij})\log(1-g(z_{i})^{T}g(z_{j}))].$
(3)

Entire procedures of L2DNCL by MAML are shown in Algorithm 2. Following MAML,
the parameters of clustering algorithm $\bm{A}$ are trained by optimizing the
following loss function:

$\begin{split}\mathcal{L}_{\bm{A}}(\theta_{g\circ\Psi})=\sum_{i=1}^{n}\mathcal{L}_{\mathcal{T}_{i}}(\theta_{g\circ\Psi}-\alpha\nabla_{\theta_{g\circ\Psi}}\mathcal{L}_{\mathcal{T}_{i}}(\theta_{g\circ\Psi})),\end{split}$
(4)

where $\alpha>0$ is the learning rate of the inner-algorithm. Then we conduct
the meta-optimization to update the parameters of cluster algorithm $\bm{A}$
as follows:

$\theta_{g\circ\Psi}\leftarrow\theta_{g\circ\Psi}-\eta\nabla_{\theta_{g\circ\Psi}}\mathcal{L}_{\bm{A}}(\theta_{g\circ\Psi}),$
(5)

where $\eta>0$ denotes the meta learning rate.

Input: task distribution: $P(\mathcal{T}^{*})$; learning rate: $\alpha$,
$\eta$; feature extractor: $\Psi$; classifier: $g$

1: Initialize $\theta_{g\circ\Psi}$;

while  _not done_ do

2: Sample tasks
$\\{\mathcal{T}_{i}=(\mathcal{D}_{i}^{\mathrm{l}},\ell,\mathcal{H})\\}_{i=1}^{n}$
by CATA (Alg. 1);

for  _all $\mathcal{T}_{i}$_ do

3: Sample $m$ training data
$S_{i}^{\mathrm{l,tr}}\sim(\mathcal{D}_{i}^{\mathrm{l}})^{m}$;

4: Evaluate
$\nabla_{\theta_{g\circ\Psi}}\mathcal{L}_{\mathcal{T}_{i}}(\theta_{g\circ\Psi})$
using $S_{i}^{\mathrm{l,tr}}$ and $\mathcal{L}_{\mathcal{T}_{i}}$ in Eq. (3);

5: Compute adapted parameters with gradient descent:
$\theta_{g\circ\Psi,i}^{\prime}=\theta_{g\circ\Psi}-\alpha\nabla_{\theta_{g\circ\Psi}}\mathcal{L}_{\mathcal{T}_{i}}(\theta_{g\circ\Psi})$;

6: Sample $k$ test data
$S_{i}^{\mathrm{l,ts}}\sim(\mathcal{D}_{i}^{\mathrm{l}})^{k}$;

end for

7: Update
$\theta_{g\circ\Psi}=\theta_{g\circ\Psi}-\eta\nabla_{\theta_{g\circ\Psi}}\mathcal{L}_{\bm{A}}(\theta_{g\circ\Psi}^{\prime})$
using each $S_{i}^{\mathrm{l,ts}}$ and $\mathcal{L}_{\bm{A}}$ in Eq. (4);

end while

Output: clustering algorithm $\bar{\bm{A}}$.

Algorithm 2 MEDI-MAML for L2DNCL.

Input: task distribution: $P(\mathcal{T}^{*})$; feature extractor: $f$

1: Initialize $\theta_{f}$;

while  _not done_ do

2: Sample tasks
$\\{\mathcal{T}_{i}=(\mathcal{D}_{i}^{\mathrm{l}},\ell,\mathcal{H})\\}_{i=1}^{n}$
by CATA (Alg. 1);

for  _all $\mathcal{T}_{i}$_ do

3: Sample $K^{\mathrm{u}}$ elements from $\\{1,\dots,K^{\mathrm{l}}\\}$ as set
$C_{I}$;

for  _$s$ in $C_{I}$_ do

4: Sample $m$ training data of $s^{th}$ class
$S_{i,s}^{\mathrm{l,tr}}\sim(\mathcal{D}_{i,s}^{\mathrm{l}})^{m}$;

5: Compute $\bm{c}_{i,s}(S_{i,s}^{\mathrm{l,tr}})$ using Eq. (6)

6: Sample $k$ test data of $s^{th}$ class
$S_{i,s}^{\mathrm{l,ts}}\sim(\mathcal{D}_{i,s}^{\mathrm{l}})^{k}$;

end for

7: Update
$\theta_{f}=\theta_{f}-\gamma\nabla_{\theta_{f}}\mathcal{L}_{\mathcal{T}_{i}}(\theta_{f})$
using $S_{i,s}^{\mathrm{l,ts}}$ and $\mathcal{L}_{\mathcal{T}_{i}}$ in Eq.
(8);

end for

end while

Output: feature extractor $f$.

Algorithm 3 MEDI-PRO for L2DNCL.

MEDI-PRO. Following [35], we denote $f:\mathcal{X}\to\mathbb{R}^{M}$ as an
embedding function, which maps data to their representations. In training task
$\mathcal{T}_{i}$, the mean vector of representations of data from class-$s$
(i.e., $S_{i,s}^{\mathrm{l,tr}}$) is defined as prototype $\bm{c}_{k}$:

$\bm{c}_{i,s}(S_{i,s}^{\mathrm{l,tr}})=\frac{1}{|S_{i,s}^{\mathrm{l,tr}}|}\sum\limits_{(x_{i}^{\mathrm{l}},y_{i}^{\mathrm{l}})\in
S_{i,s}^{\mathrm{l,tr}}}f(x_{i}^{\mathrm{l}}).$ (6)

Here, we define a distance
$d:\mathbb{R}^{M}\times\mathbb{R}^{M}\to[0,+\infty)$ to measure the distance
between data from the test set and the prototype. In this paper, the Euclidean
distance as $d$. Then, we produce a distribution over classes for a test data
point $\bm{x}$ based on softmax over the distances to the prototypes in the
embedding space:

$p(y=s|\bm{x})=\frac{\text{exp}(-d(f(\bm{x}),\bm{c}_{s}))}{\sum_{s^{\prime}}\text{exp}(-d(f(\bm{x}),\bm{c}_{s^{\prime}}))}.$
(7)

We train the embedding function by optimizing the negative log-probability,
i.e., $-\log p(y=s|\bm{x})$. So the loss function of ProtoNet is defined as
follows:

$\mathcal{L}_{\mathcal{T}_{i}}=-\frac{1}{k}\sum\limits_{s\in[K^{\mathrm{u}}]}\sum\limits_{\bm{x}\in
S_{i,s}^{\mathrm{l,ts}}}\log p(y=s|\bm{x}),$ (8)

where $[K^{\mathrm{u}}]$ denotes the number $K^{\mathrm{u}}$ of classes
selected from $\\{1,\dots,K^{\mathrm{l}}\\}$. $S_{i,s}^{\mathrm{l,ts}}$ is the
test set of labeled data of class-$s$ from task $\mathcal{T}_{i}$. The full
procedures of training $f$ are shown in Algorithm 3. After training the
embedding function $f$ well, we use the training set of $S^{\mathrm{u}}$ to
obtain the prototypes. For $\bm{x}$ in the test set of $S^{\mathrm{u}}$, we
compute the distance between $\bm{x}$ and each prototype, and then the class
corresponding to the nearest prototype is the class of $\bm{x}$.

##  4 Theoretical Guarantees for L2NDCL

This section presents that L2DNCL is theoretically solvable (Theorem 1)
according to the meta learning theory. Based on Problem 1, we aim to minimize
the following risk in L2DNCL:

$\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T^{*}}))=\mathbb{E}_{\mathcal{T}\sim
P(\mathcal{T}^{*})}\mathbb{E}_{S\sim(\mathcal{D}^{\mathrm{l}})^{m}}\mathbb{E}_{(x,c)\sim\mathcal{D}^{\mathrm{l}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S^{\mathrm{X,l}}),x),$
(9)

where $S^{\mathrm{X,l}}$ denotes the feature set of
$S^{\mathrm{l}}\sim(\mathcal{D}^{\mathrm{l}})^{m}$.
$\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T^{*}}))$ is the
expectation of the generalized error w.r.t. the task distribution
$P(\mathcal{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_ :

$\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})=\frac{1}{n}\sum\limits_{i=1}^{n}\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{i}^{\mathrm{X,l,tr}}),x_{ij}),$
(10)

where $S_{i}^{\mathrm{X,l,tr}}$ denotes the feature set of
$S_{i}^{\mathrm{l,tr}}$ and $S_{i}^{\mathrm{l}}=S_{i}^{\mathrm{l,tr}}\cup
S_{i}^{\mathrm{l,ts}}\sim(\mathcal{D}^{\mathrm{l}}_{i})^{m}$. Then, the
generalization bound of inner-task clustering algorithm
$\bm{A}(\bm{S}^{\mathrm{l}})$ of meta-based L2DNCL algorithms can be obtained
from the uniform stability $\beta$ of the meta-algorithm $\bm{A}$.

######  Definition 1 (Uniform Stability [27]).

A meta-algorithm $\bm{A}$ has uniform stability $\beta$ w.r.t. the loss
function $\ell$ if the following holds for any meta-samples $\bm{S}$ and
$\forall i\in\\{1,\dots,n\\}$, $\forall\mathcal{T}\sim\tilde{P}(\mathcal{T})$,
$\forall S^{\mathrm{tr}}\sim\mathcal{D}^{m}$, $\forall
S^{\mathrm{ts}}\sim\mathcal{D}^{k}$:

$\displaystyle|\hat{L}(\bm{A}(\bm{S})(S^{\mathrm{tr}}),S^{\mathrm{ts}})-\hat{L}(\bm{A}(\bm{S}^{\backslash
i})(S^{\mathrm{tr}}),S^{\mathrm{ts}})|\leq\beta,$

where

$\displaystyle\hat{L}(\bm{A}(\bm{S})(S_{i}^{\mathrm{tr}}),S_{i}^{\mathrm{ts}})=\frac{1}{k}\sum\limits_{z_{ij}\in
S_{i}^{\mathrm{ts}}}\tilde{\ell}(\bm{A}(\bm{S})(S_{i}^{\mathrm{tr}}),z_{ij}).$

######  Theorem 1.

For any task distribution $P(\mathcal{T}^{*})$ and meta-samples
$\bm{S}^{\mathrm{l}}$ with $n$ tasks, if a meta-algorithm $\bm{A}$ has uniform
stability $\beta$ w.r.t. a loss function $\ell$ bounded by $M$, then the
following statement holds with probability at least $1-\delta$ for any
$\delta\in(0,1)$:

$\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))\leq\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})+\epsilon(n,\beta),$
(11)

where $\epsilon(n,\beta)=2\beta+(4n\beta+M)\sqrt{\frac{\log(1/\delta)}{2n}}$.

By Theorem 1, the generalization bound depends on the number of the training
tasks $n$ and the uniform stability parameter $\beta$. If
$\beta<O({1}/{\sqrt{n}})$, we have $\epsilon(n,\beta)\to 0$ as $n\to\infty$.
Hence, given a sufficiently small $\beta$, the error
$\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))$ converges to
training error
$\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})$ as the
number of training tasks $n$ grows. The proof of Theorem 1 can be found in
Appendix A. Theorem 1 indicates that L2DNCL can be theoretically solved if we
can control the uniform stability of a meta-algorithm (like MAML did via
support-query learning [3]).

######  Remark 2.

The only difference between L2DNC and L2DNCL is the number of novel-class
data, which does not affect the results from Theorem 1. Thus, L2DNC can be
theoretically solved if data used in L2DNC are sampled in causality (Figure
1(b)).

##  5 Related Work and Discussion

Our proposal is mainly related to L2DNC and meta-learning. We briefly
summarize the most representative works and discuss the relationship between
these works and our work.

Learning to discover novel classes. L2DNC was proposed in recent years, aiming
to cluster unlabeled novel-class data according to their underlying
categories. Compared with unsupervised learning [1], L2DNC also requires
labeled known-class data to help cluster novel-class data. The pioneering
methods include the _KL-Divergence-based contrastive loss_ (KCL) [12], the
_meta classification likelihood_ (MCL) [13], _deep transfer clustering_ (DTC)
[9], and the _rank statistics_ (RS) [8]. Detailed introduction of these four
methods is in Appendix B. Comparing existing works [12, 46, 45] with ours, we
aim to cluster unlabeled data when their quantity is few.

Meta-learning. Meta-learning is also known as learning-to-learn, which trains
a meta-model over a wide variety of learning tasks [43, 41, 30, 4]. In meta-
learning, we often assume that data share the same high-level features, which
ensures that meta-learning can be theoretically addressed [27]. According to
[11], there are three common approaches to meta-learning: optimization-based
[6], model-based [32], and metric-based [35]. Review of meta learning methods
is in Appendix B.

Sampler for 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. [44] 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_. [21] 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
(Section 3.1) based on clustering rules regarding data, which is _in the view
of data_.

Clustering via meta-learning. In [15], researchers trained a recurrent model
that learns how to cluster given multiple types of training datasets. Compared
with MEDI, [15] learns a clustering model with multiple unlabeled datasets,
while MEDI learns a clustering model with labeled known data and (abundant or
few) unlabeled novel data from the same dataset.

##  6 Experiments

In this section, we test the efficacy of our methods and possible baselines on
four datasets.

(a) C-$100$ $20$-way $1$-obsv

(b) C-$100$ $20$-way $5$-obsv

(c) O $20$-way $1$-obsv

(d) O $20$-way $5$-obsv

Figure 5: We conducted experiments on CIFAR-100 (C-100) and OmniGlot (O) and
reported the _average clustering accuracy_ (ACC (%), Section 6) when using
existing and our methods to address the L2DNCL problem. The experimental
results showed that MEDI-MAML and MEDI-PRO tend to outperform existing
methods.

#### Datasets.

To evaluate the performance of our methods, we conduct experiments on four
popular image classification benchmarks, including CIFAR-$10$ [18],
CIFAR-$100$ [18], SVHN [28], and OmniGlot [19]. Detailed introductions and
partitions of known classes and novel classes of these four datasets is in
Appendix C. Following the protocol of few-shot learning [40, 47, 25, 29], for
SVHN and CIFAR-$10$, we perform the few-obsv tasks of $5$-way $1$-obsv and
$5$-way $5$-obsv, and we perform the few-obsv tasks of $20$-way $1$-obsv and
$20$-way $5$-obsv for CIFAR-$100$ and OmniGlot.

#### Baselines.

To verify the performance of our meta-based L2DNCL methods (i.e., MEDI-MAML
and MEDI-PRO), we compare them with $5$ competitive baselines, including
K-means [26], KCL [12] , MCL [13], DTC [9], and RS [8]. We modify these
baselines by only reducing the amount of novel-class data, with other
configurations invariable. We clarify the implementation details of CATA,
MEDI-MAML, and MEDI-PRO in Appendix D.

#### 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\limits_{\phi\in\
L}\frac{1}{N}\sum_{i=1}^{N}\mathbbm{1}\\{\bar{y_{i}}=\phi(y_{i})\\},$ (12)

where $\bar{y_{i}}$ and $y_{i}$ denote the ground-truth label and assigned
cluster indices respectively. $L$ is the set of mappings from cluster indices
to ground-truth labels.

Table 1: Ablation Study on four datasets. Methods | MM | MM w/o C | MP | MP w/o C
---|---|---|---|---
SVHN (5-way) | 5-obsv |  47.3$\pm$0.3 |  40.1$\pm$0.3 |  61.0$\pm$0.5 |  60.5$\pm$0.2
1-obsv |  42.7$\pm$0.3 |  39.7$\pm$0.4 |  52.8$\pm$0.4 |  50.2$\pm$0.3
CIFAR-10 (5-way) | 5-obsv |  45.3$\pm$0.1 |  42.7$\pm$0.3 |  58.5$\pm$0.2 |  57.9$\pm$0.1
1-obsv |  41.3$\pm$0.4 |  40.3$\pm$0.3 |  51.7$\pm$0.2 |  47.6$\pm$0.2
CIFAR-100 (20-way) | 5-obsv |  42.0$\pm$0.4 |  39.9$\pm$0.3 |  45.5$\pm$0.3 |  44.1$\pm$0.1
1-obsv |  39.2$\pm$0.2 |  37.1$\pm$0.3 |  38.8$\pm$0.4 |  37.0$\pm$0.2
OmniGlot (20-way) | 5-obsv |  82.1$\pm$0.4 |  80.1$\pm$0.4 |  98.4$\pm$0.2 |  96.7$\pm$0.3
1-obsv |  77.3$\pm$0.4 |  78.5$\pm$0.4 |  94.6$\pm$0.3 |  91.2$\pm$0.2

In this table, we report the ACC (%)$\pm$standard deviation of ACC (%) on four
datasts, where MM and MP represent MEDI-MAML and MEDI-PRO, respectively, and C
represents CATA and w/o represents “without”. It is clear that CATA improves
the ACC.

#### Results on CIFAR-$\bm{10}$.

As shown in Figures 2(a) and 2(b), MEDI-MAML and MEDI-PRO outperform all
baselines significantly, and the ACC of MEDI-PRO is much higher than that of
MEDI-MAML. The main reason is that MEDI-PRO makes full use of the labels of
known-class data in the training process, while MEDI-MAML does not. MEDI-MAML
only uses the labels of known-class data in the sampling process. Besides,
K-means performs better than it on other datasets significantly. The reason is
that clustering rules contained in CIFAR-$10$ are 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$-obsv, RS performs as well as MEDI-MAML (Figure 2(d)).
The reason is that RS trains the embedding network with self-supervised
learning under $1$-obsv case, which partly overcomes this problem by data
augment.

#### Results on CIFAR-$\bm{100}$.

It is clear that we outperform all baselines. Differ from tasks on other
datasets, MEDI-MAML performs equally even a little better than MEDI-PRO 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 $1.15\%$ and $1.30\%$. Namely, K-means
hardly works on OmniGlot. The number of novel classes of OmniGlot ($659$) is
too large for K-means.

#### Results analysis of L2DNC with _abundant_ novel-class data.

Other than L2DNCL, MEDI can also address L2DNC efficiently. Results of L2DNC
are shown in Table 2 (Appendix E). Table 2 shows that MEDI-MAML is comparable
with the representative methods but cannot outperform the RS. Compared with
RS, MEDI-MAML samples many inner-tasks for training, while RS uses the whole
data. Incomplete data makes MEDI-MAML unable to learn the global distribution
of novel classes. MEDI-PRO is not as well as MEDI-MAML 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 MEDI-PRO, the results
of L2DNC are obviously better than the results of L2DNCL.

#### Ablation study.

To verify the effectiveness of CATA, we conduct ablation study by removing
CATA from MEDI-MAML and MEDI-PRO. According to Table 1, CATA significantly
improves the performance of MEDI-MAML and MEDI-PRO. However, there exists an
abnormal phenomenon in OmniGlot, i.e., MM w/o C outperforms MM in the task of
$20$-way $1$-obsv. Although we need $16$
($=|S^{\mathrm{l,tr}}|+|S^{\mathrm{l,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 MEDI-MAML.

##  7 Conclusions

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_ (MEDI). After
realizing MEDI using MAML and ProtoNet, we find 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. Moreover, based on this finding, L2DNC/L2DNCL can be
theoretically solved, which lights up a novel road for L2DNC/L2DNCL.

## References

  * [1] Horace B Barlow.  Unsupervised learning.  Neural computation, 1(3):295–311, 1989.
  * [2] Avrim Blum and Tom M. Mitchell.  Combining labeled and unlabeled data with co-training.  In COLT, 1998.
  * [3] Jiaxin Chen, Xiao-Ming Wu, Yanke Li, Qimai LI, Li-Ming Zhan, and Fu-Lai Chung.  A closer look at the training strategy for modern meta-learning.  In NeurIPS, 2020.
  * [4] Xiaohan Chen, Zhangyang Wang, Siyu Tang, and Krikamol Muandet.  MATE: plugging in model awareness to task embedding for meta learning.  In NeurIPS, 2020.
  * [5] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li.  Imagenet: A large-scale hierarchical image database.  In CVPR, 2009.
  * [6] Chelsea Finn, Pieter Abbeel, and Sergey Levine.  Model-agnostic meta-learning for fast adaptation of deep networks.  In ICML, 2017.
  * [7] Spyros Gidaris, Praveer Singh, and Nikos Komodakis.  Unsupervised representation learning by predicting image rotations.  In ICLR, 2018.
  * [8] Kai Han, Sylvestre-Alvise Rebuffi, Sébastien Ehrhardt, Andrea Vedaldi, and Andrew Zisserman.  Automatically discovering and learning new visual categories with ranking statistics.  In ICLR, 2020.
  * [9] Kai Han, Andrea Vedaldi, and Andrew Zisserman.  Learning to discover novel visual categories via deep transfer clustering.  In ICCV, 2019.
  * [10] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In CVPR, 2016.
  * [11] Timothy Hospedales, Antreas Antoniou, Paul Micaelli, and Amos Storkey.  Meta-learning in neural networks: A survey.  arXiv:2004.05439, 2020.
  * [12] Yen-Chang Hsu, Zhaoyang Lv, and Zsolt Kira.  Learning to cluster in order to transfer across domains and tasks.  In ICLR, 2018.
  * [13] Yen-Chang Hsu, Zhaoyang Lv, Joel Schlosser, Phillip Odom, and Zsolt Kira.  Multi-class classification without multi-class labels.  In ICLR, 2019.
  * [14] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In ICML, 2015.
  * [15] Yibo Jiang and Nakul Verma.  Meta-learning to cluster.  arXiv:1910.14134, 2019.
  * [16] 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.
  * [17] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In ICLR, 2015.
  * [18] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  2009\.
  * [19] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum.  Human-level concept learning through probabilistic program induction.  Science, 350(6266):1332–1338, 2015.
  * [20] Yingming Li, Ming Yang, and Zhongfei Zhang.  A survey of multi-view representation learning.  IEEE Transactions on Knowledge and Data Engineering, 31(10):1863–1883, 2019.
  * [21] Chenghao Liu, Zhihao Wang, Doyen Sahoo, Yuan Fang, Kun Zhang, and Steven C. H. Hoi.  Adaptive task sampling for meta-learning.  In ECCV, 2020.
  * [22] Feng Liu, Wenkai Xu, Jie Lu, Guangquan Zhang, Arthur Gretton, and Danica J. Sutherland.  Learning deep kernels for non-parametric two-sample tests.  In ICML, 2020.
  * [23] Lu Liu, Tianyi Zhou, Guodong Long, Jing Jiang, Xuanyi Dong, and Chengqi Zhang.  Isometric propagation network for generalized zero-shot learning.  In ICLR, 2021.
  * [24] Lu Liu, Tianyi Zhou, Guodong Long, Jing Jiang, and Chengqi Zhang.  Attribute propagation network for graph zero-shot learning.  In AAAI, 2020.
  * [25] Yanbin Liu, Juho Lee, Minseop Park, Saehoon Kim, Eunho Yang, Sung Ju Hwang, and Yi Yang.  Learning to propagate labels: Transductive propagation network for few-shot learning.  In ICLR, 2019.
  * [26] James MacQueen et al.  Some methods for classification and analysis of multivariate observations.  In Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 1967.
  * [27] Andreas Maurer.  Algorithmic stability and meta-learning.  Journal of Machine Learning Research, 6:967–994, 2005.
  * [28] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y. Ng.  Reading digits in natural images with unsupervised feature learning.  In NeurIPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
  * [29] Minseop Park, Saehoon Kim, Jungtaek Kim, Yanbin Liu, and Seungjin Choi.  Taeml: Task-adaptive ensemble of meta-learners.  In NeurIPS Workshop on Meta learning, 2018.
  * [30] Sachin Ravi and Hugo Larochelle.  Optimization as a model for few-shot learning.  In ICLR, 2017.
  * [31] Kuniaki Saito, Yoshitaka Ushiku, and Tatsuya Harada.  Asymmetric tri-training for unsupervised domain adaptation.  In ICML, 2017.
  * [32] Adam Santoro, Sergey Bartunov, Matthew Botvinick, Daan Wierstra, and Timothy P. Lillicrap.  Meta-learning with memory-augmented neural networks.  In ICML, 2016.
  * [33] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In ICLR, 2015.
  * [34] EJ A’Court Smith.  Discovery of remains of plants and insects.  Nature, 11(266):88–88, 1874.
  * [35] Jake Snell, Kevin Swersky, and Richard S. Zemel.  Prototypical networks for few-shot learning.  In NeurIPS, 2017.
  * [36] Jie Song, Yixin Chen, Xinchao Wang, Chengchao Shen, and Mingli Song.  Deep model transferability from attribution maps.  In NeurIPS, pages 6179–6189, 2019.
  * [37] 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.
  * [38] 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):1929–1958, 2014.
  * [39] Dirk R. Walters.  Vascular Plant Taxonomy.  Kendall/Hunt Publishing Company, 1977.
  * [40] Yaqing Wang, Quanming Yao, James T Kwok, and Lionel M Ni.  Generalizing from a few examples: A survey on few-shot learning.  ACM Computing Surveys, 53(3):1–34, 2020.
  * [41] Ying Wei, Peilin Zhao, and Junzhou Huang.  Meta-learning hyperparameter performance prediction with neural processes.  In Proceeding of the Thirty-eighth International Conference on Machine Learning, 2021.
  * [42] Junyuan Xie, Ross B. Girshick, and Ali Farhadi.  Unsupervised deep embedding for clustering analysis.  In ICML, 2016.
  * [43] Huaxiu Yao, Longkai Huang, Linjun Zhang, Ying Wei, Li Tian, James Zou, Junzhou Huang, and Zhenhui Li.  Improving generalization in meta-learning via task augmentation.  In Proceeding of the Thirty-eighth International Conference on Machine Learning, 2021.
  * [44] Huaxiu Yao, Ying Wei, Junzhou Huang, and Zhenhui Li.  Hierarchically structured meta-learning.  In ICML, 2019.
  * [45] Zhun Zhong, Enrico Fini, Subhankar Roy, Zhiming Luo, Elisa Ricci, and Nicu Sebe.  Neighborhood contrastive learning.  In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2021.
  * [46] Zhun Zhong, Linchao Zhu, Zhiming Luo, Shaozi Li, Yi Yang, and Nicu Sebe.  Openmix: Reviving known knowledge for discovering novel visual categories in an open world.  In CVPR, 2021.
  * [47] Imtiaz Masud Ziko, Jose Dolz, Eric Granger, and Ismail Ben Ayed.  Laplacian regularized few-shot learning.  In ICML, 2020.

##  Appendix A Proof of Theorem 1

The proof of Theorem 1 mainly follows [3]. Given training meta-samples
$\bm{S}=\\{S_{i}^{\mathrm{tr}}\cup S_{i}^{\mathrm{ts}}\\}_{i=1}^{n}$, we
modify $\bm{S}$ by replacing the $i$-th element to obtain
$\bm{S}^{i}=\\{S_{1}^{\mathrm{tr}}\cup
S_{1}^{\mathrm{ts}},\dots,S_{i-1}^{\mathrm{tr}}\cup
S_{i-1}^{\mathrm{ts}},S_{i}^{\mathrm{tr}^{\prime}}\cup
S_{i}^{\mathrm{ts}^{\prime}},S_{i+1}^{\mathrm{tr}}\cup
S_{i+1}^{\mathrm{ts}},\dots,S_{n}^{\mathrm{tr}}\cup S_{n}^{\mathrm{ts}}\\}$,
where the replacement sample $S_{i}^{\prime}$ is assumed to be drawn from
$\mathcal{D}$ and is independent from $\bm{S}$. In the same way, given a
training set $S=\\{z_{1},\dots,z_{i-1},z_{i},z_{i+1},\dots,z_{n}\\}$, we
modify $S$ by replacing the $i$-th element to obtain
$S^{i}=\\{z_{1},\dots,z_{i-1},z^{\prime}_{i},z_{i+1},\dots,z_{n}\\}$.

######  Lemma 1 (McDiarmid Inequality).

Let $S$ and $S^{i}$ defined as above, let $F:\mathcal{Z}^{n}\to\mathbb{R}$ be
any measurable function for which there exits constants $c_{i}$
($i=1,\dots,n$) such that

$\sup\limits_{S\in\mathcal{Z}^{m},z_{i}^{\prime}\in\mathcal{Z}}|F(S)-F(S^{i})|\leq
c_{i},$

then

$P_{S}[F(S)-\mathbb{E}_{S}[F(S)]\geq\epsilon]\leq\text{exp}(\frac{-2\epsilon^{2}}{\sum_{i=1}^{n}c_{i}^{2}}).$

######  Theorem 1′.

For any task distribution $P(\mathcal{T}^{*})$ and meta-samples
$\bm{S}^{\mathrm{l}}$ with $n$ tasks, if a meta-algorithm $\bm{A}$ has uniform
stability $\beta$ w.r.t. a loss function $\ell$ bounded by $M$, then the
following statement holds with probability of at least $1-\delta$ for any
$\delta\in(0,1)$:

$\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))\leq\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})+\epsilon(n,\beta),$
(13)

where $\epsilon(n,\beta)=2\beta+(4n\beta+M)\sqrt{\frac{\log(1/\delta)}{2n}}$.

###### Proof.

Let
$F(\bm{S}^{\mathrm{l}})=\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))-\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})$
and
$F(\bm{S}^{\mathrm{l},i})=\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l},i}),P(\mathcal{T}^{*}))-\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l},i}),\bm{S}^{\mathrm{l},i})$.
We have

$|F(\bm{S}^{\mathrm{l}})-F(\bm{S}^{\mathrm{l},i})|\leq|\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))-\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l},i}),P(\mathcal{T}^{*}))|+|\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})-\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l},i}),\bm{S}^{\mathrm{l},i})|.$
(14)

The first term in Eq. (14) can be written as

$\displaystyle|\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))-\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l},i}),P(\mathcal{T}^{*}))|$
$\displaystyle\leq|\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))-\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}\backslash
i}),P(\mathcal{T}^{*}))|$
$\displaystyle+|\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l},i}),P(\mathcal{T}^{*}))-\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}\backslash
i}),P(\mathcal{T}^{*}))|.$

We can upper bound the first term in Eq. (14) by studying the variation when a
sample set $S^{\mathrm{l}}_{i}$ of training task $\mathcal{D}_{i}$ is deleted,

$\displaystyle|\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))-\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}\backslash
i}),P(\mathcal{T}^{*}))|$ $\displaystyle\leq\mathbb{E}_{\mathcal{T}\sim
P(\mathcal{T}^{*})}\mathbb{E}_{S\sim(\mathcal{D}^{\mathrm{l}})^{m}}\mathbb{E}_{(x,c)\sim\mathcal{D}^{\mathrm{l}}}|\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S^{\mathrm{X,l}}),x)-\ell(\bm{A}(\bm{S}^{\mathrm{l}\backslash
i})(S^{\mathrm{X,l}}),x)|$ $\displaystyle\leq\sup\limits_{\mathcal{T}\sim
P(\mathcal{T}^{*}),S\sim(\mathcal{D}^{\mathrm{l}})^{m},(x,c)\sim\mathcal{D}^{\mathrm{l}}}|\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S^{\mathrm{X,l}}),x)-\ell(\bm{A}(\bm{S}^{\mathrm{l}\backslash
i})(S^{\mathrm{X,l}}),x)|$ $\displaystyle\leq\beta.$

Similarly, we have
$|\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l},i}),P(\mathcal{T}^{*}))-\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}\backslash
i}),P(\mathcal{T}^{*}))|\leq\beta$. So the first term of Eq. (14) is upper
bounded by $2\beta$. The second factor in Eq. (14) can be guaranteed likewise
as follows,

$\displaystyle|\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})-\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l},i}),\bm{S}^{\mathrm{l},i})|$
$\displaystyle\leq\frac{1}{n}\sum_{q\neq
i}\left|\frac{1}{k}\sum\limits_{(x_{qj},c_{qj})\in
S_{q}^{\mathrm{l,ts}}}(\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{q}^{\mathrm{X,l,tr}}),x_{qj})-\ell(\bm{A}(\bm{S}^{\mathrm{l},i})(S_{q}^{\mathrm{X,l,tr}}),x_{qj}))\right|$
$\displaystyle\quad+\frac{1}{nk}\left|\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{i}^{\mathrm{X,l,tr}}),x_{ij})-\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\prime,\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l},i})(S_{i}^{\prime,\mathrm{X,l,tr}}),x_{ij})\right|$
$\displaystyle\leq 2\beta+\frac{M}{n}.$

Hence, $|F(\bm{S}^{\mathrm{l}})-F(\bm{S}^{\mathrm{l},i})|$ satisfies the
condition of Lemma 1 with $c_{i}=4\beta+\frac{M}{n}$. It remains to bound
$\mathbb{E}_{\bm{S}^{l}}[F(\bm{S}^{l})]=\mathbb{E}_{\bm{S}^{l}}[\mathcal{R}(\bm{A}(\bm{S}^{l}),P(\mathcal{T}^{*}))]-\mathbb{E}_{\bm{S}^{l}}[\hat{\mathcal{R}}(\bm{A}(\bm{S}^{l}),\bm{S}^{l})]$.
The first term can be written as follows,

$\mathbb{E}_{\bm{S}^{\mathrm{l}}}[\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))]=\mathbb{E}_{\bm{S}^{\mathrm{l}},S_{i}^{\prime,\mathrm{X,l,tr}},S_{i}^{\prime,\mathrm{l,ts}}}\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\prime,\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{i}^{\prime,\mathrm{X,l,tr}}),x_{ij}).$

Similarly, the second term is,

$\displaystyle\mathbb{E}_{\bm{S}^{\mathrm{l}}}[\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})]$
$\displaystyle=\mathbb{E}_{\bm{S}^{\mathrm{l}}}\left[\frac{1}{n}\sum_{i=1}^{n}\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{i}^{\mathrm{X,l,tr}}),x_{ij})\right]$
$\displaystyle=\mathbb{E}_{\bm{S}^{\mathrm{l}}}\left[\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{i}^{\mathrm{X,l,tr}}),x_{ij})\right]$
$\displaystyle=\mathbb{E}_{\bm{S}^{\mathrm{l}},S_{i}^{\prime,\mathrm{X,l,tr}},S_{i}^{\prime,\mathrm{l,ts}}}\left[\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\prime,\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l},i})(S_{i}^{\prime,\mathrm{X,l,tr}}),x_{ij})\right].$

Hence, $\mathbb{E}_{\bm{S}^{\mathrm{l}}}[F(\bm{S}^{\mathrm{l}})]$ is upper
bounded by $2\beta$,

$\displaystyle\mathbb{E}_{\bm{S}^{\mathrm{l}}}[\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))]-\mathbb{E}_{\bm{S}^{\mathrm{l}}}[\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})]$
$\displaystyle=\mathbb{E}_{\bm{S}^{\mathrm{l}},S_{i}^{\prime,\mathrm{X,l,tr}},S_{i}^{\prime,\mathrm{l,ts}}}\left[\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\prime,\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l}})(S_{i}^{\prime,\mathrm{X,l,tr}}),x_{ij})-\frac{1}{k}\sum\limits_{(x_{ij},c_{ij})\in
S_{i}^{\prime,\mathrm{l,ts}}}\ell(\bm{A}(\bm{S}^{\mathrm{l},i})(S_{i}^{\prime,\mathrm{X,l,tr}}),x_{ij})\right]$
$\displaystyle\leq 2\beta.$

Plugging the above inequality in Lemma 1, we obtain

$\displaystyle
P_{\bm{S}^{\mathrm{l}}}[\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))-\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})\geq
2\beta+\epsilon]\leq\text{exp}\left(\frac{-2\epsilon^{2}}{\sum_{i=1}^{n}(4\beta+\frac{M}{n})^{2}}\right).$

Finally, setting the right side of the above inequality to $\delta$, the
following result holds with probability of $1-\delta$,

$\mathcal{R}(\bm{A}(\bm{S}^{\mathrm{l}}),P(\mathcal{T}^{*}))\leq\hat{\mathcal{R}}(\bm{A}(\bm{S}^{\mathrm{l}}),\bm{S}^{\mathrm{l}})+2\beta+(4n\beta+M)\sqrt{\frac{\log(1/\delta)}{2n}}.$

∎

##  Appendix B Detailed Related Work

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 [1], L2DNC also requires
labeled known-class data to help cluster novel-class data. The pioneering
methods include _KLD-based contrastive loss_ (KCL) [12], _meta classification
likelihood_ (MCL) [13], _deep transfer clustering_ (DTC) [9], and _rank
statistics_ (RS) [8]. In this paper, we update and present the results of our
methods regarding L2DNC.

In KCL [12], 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 [13] changed the loss function of KCL (the KL-divergence based contrastive
loss) to the meta classification likelihood loss.

In DTC [9], they first learned a data embedding with metric learning on
labeled data, and then they employed the DEC [42] to learn the cluster
assignments on unlabeled data.

In RS [8], 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 [7] 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 [30]. In meta-learning, we
often assume that data share the same high-level features, which ensures that
meta-learning can be theoretically addressed [27]. According to [11], there
are three common approaches to meta-learning: optimization-based [6], model-
based [32], and metric-based [35].

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.

Table 2: Results of L2DNC with abundant novel class data. In this table, we report the ACC (%)$\pm$standard deviation of ACC (%) of baselines and our methods (MEDI-MAML and MEDI-PRO) given abundant 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 | MEDI-MAML | MEDI-PRO
---|---|---|---|---|---|---|---
SVHN |  42.6$\pm$0.0 |  21.4$\pm$0.6 |  38.6$\pm$10.8 |  60.9$\pm$1.6 |  95.2$\pm$0.2 |  93.1$\pm$2.1 |  77.1$\pm$0.8
CIFAR-10 |  65.5$\pm$0.0 |  66.5$\pm$3.9 |  64.2$\pm$0.1 |  87.5$\pm$0.3 |  91.7$\pm$0.9 |  92.3$\pm$0.9 |  73.2$\pm$1.9
CIFAR-100 |  56.6$\pm$1.6 |  14.3$\pm$1.3 |  21.3$\pm$3.4 |  56.7$\pm$1.2 |  75.2$\pm$4.2 |  69.8$\pm$1.3 |  58.3$\pm$2.2
OmniGlot | 77.2 | 82.4 | 83.3 | 89.0 | 89.1 |  88.6$\pm$0.7 |  98.4$\pm$0.2

##  Appendix C Dataset Introductions and Splits

CIFAR-$10$ dataset contains $60,000$ images with sizes of $32\times 32$.
Following [9], 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 [8], 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 [9], 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 [13], 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.

##  Appendix D 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$ [10] as the feature extractor and use three fully-connected
layers with softmax layer as the classifier. We also use BN layer [14] and
Dropout [38] in network layers. In this paper, we select the number of views
$K=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 [17] 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 $\lambda$ of $1/3$.

#### MEDI-MAML for L2DNCL.

We use VGG-$16$ [33] 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. 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\backslash 8$ for
$\\{$CIFAR-$10$,SVHN$\\}\backslash\\{$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.

#### MEDI-PRO for L2DNCL.

We use a neural network of four convolutional blocks as the embedding function
for all datasets following [35]. Each block comprises a $64$-filter $3\times
3$ convolution, BN layer [14], a ReLU function and a $2\times 2$ max-pooling
layer. We use the same embedding function for embedding both training data and
test data. For all experiments, we train the models via Adam [17], and we use
an initial learning rate of $0.001$ and cut the learning rate in half every 20
steps. We train the embedding function for $200$ steps with $1000$ training
tasks sampled by CATA.

##  Appendix E Results of L2DNC

In this section, we show the results of L2DNC with abundant novel-class data
in Table 2. Detailed analysis is in Section 6.

##  Appendix F Complexity Analysis

We give a brief analysis of time complexity for each algorithm. As MEDI-MAML
and MEDI-PRO are two-step methods, we first analyze the sampling algorithm
CATA, and then analyze the main parts of MEDI-MAML and MEDI-PRO.

#### 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*K^{2}*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.

#### MEDI-MAML (Main part)

The time complexity of MEDI-MAML 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*K^{2}*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.

#### MEDI-PRO (Main part)

The time complexity of MEDI-PRO 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*K^{2}*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.

##  Appendix G Running Time

In this section, we list the running time of MEDI-MAML and MEDI-PRO for all
four datasets. The results are shown in Tabel 3.

Table 3: Average running time of MEDI-MAML and MEDI-PRO. We denote h as hours. Methods |  SVHN ($5$-way) |  |  CIFAR-10 ($5$-way) |  |  CIFAR-100 ($20$-way) |  |  OmniGlot ($20$-way)
---|---|---|---|---|---|---|---
$5$-obsv |  $1$-obsv |  |  $\quad 5$-obsv |  $\quad 1$-obsv |  |  $\quad 5$-obsv |  $\quad 1$-obsv |  |  $\quad 5$-obsv |  $\quad 1$-obsv
MM |  $5.3$h |  $4.6$h |  |  $3.1$h |  $2.7$h |  |  $3.1$h |  $2.8$h |  |  $3.0$h |  $2.7$h
MP |  $6.2$h |  $6.0$h |  |  $2.1$h |  $1.6$h |  |  $2.0$h |  $1.6$h |  |  $1.2$h |  $1.0$h

##  Appendix H Link to Datasets

SVHN dataset can be downloaded from
http://ufldl.stanford.edu/housenumbers/train.tar.gz and
http://ufldl.stanford.edu/housenumbers/test.tar.gz.

CIFAR-$10$ and CIFAR-$100$ datasets can be downloaded from
https://www.cs.toronto.edu/~kriz/cifar-10-python.tar.gz and
https://www.cs.toronto.edu/~kriz/cifar-100-python.tar.gz.

OmniGlot dataset can be downloaded from
https://github.com/brendenlake/omniglot/tree/master/python.