# Open-World Continual Learning: Unifying Novelty Detection and Continual
Learning

Gyuhak Kim111Equal contribution<EMAIL_ADDRESS>University of Illinois at
Chicago, 851 S Morgan St, Chicago, Illinois, 60607, United States  Changnan
Xiao222Equal contribution<EMAIL_ADDRESS>ByteDance, Building 24, Zone
B, 1999 Yishan Road, Shanghai, 201100, China  Tatsuya Konishi333The work was
done when this author was visiting Bing Liu’s group at University of Illinois
at Chicago. The original affiliation and address of this author are KDDI
Research, Inc., 2-1-15 Ohara, Fujimino-shi, Saitama, 356-8502, Japan tt-
<EMAIL_ADDRESS>Zixuan Ke<EMAIL_ADDRESS>Bing Liu<EMAIL_ADDRESS>
###### Abstract

As AI agents are increasingly used in the real open world with unknowns or
novelties, they need the ability to (1) recognize objects that (i) they have
learned and (ii) detect items that they have not seen or learned before, and
(2) learn the new items incrementally to become more and more knowledgeable
and powerful. (1) is called novelty detection or out-of-distribution (OOD)
detection and (2) is called class incremental learning (CIL), which is a
setting of continual learning (CL). In existing research, OOD detection and
CIL are regarded as two completely different problems. This paper
theoretically proves that OOD detection actually is necessary for CIL. We
first show that CIL can be decomposed into two sub-problems: within-task
prediction (WP) and task-id prediction (TP). We then prove that TP is
correlated with OOD detection. The key theoretical result is that regardless
of whether WP and OOD detection (or TP) are defined explicitly or implicitly
by a CIL algorithm, good WP and good OOD detection are necessary and
sufficient conditions for good CIL, which unifies novelty or OOD detection and
continual learning (CIL, in particular). A good CIL algorithm based on our
theory can naturally be used in open world learning, which is able to perform
both novelty/OOD detection and continual learning. Based on the theoretical
result, new CIL methods are also designed, which outperform strong baselines
in terms of CIL accuracy and its continual OOD detection by a large margin.

###### keywords:

Open world learning , continual learning , OOD detection

††journal: Artificial Intelligence

##  1 Introduction

The current dominant machine learning paradigm (ML) makes the closed-world
assumption, which means that the classes of objects seen by the system in
testing or in deployment must have been seen during training [54, 53, 6, 15,
37], i.e., there is nothing novel occurring during testing or deployment. This
assumption is invalid in practice as the real environment is an open world
that is full of unknowns or novel objects. In order to make an AI agent thrive
in the open world, it has to detect novelties and learn them incrementally to
make the system more knowledgeable and adaptable over time. This process
involves multiple activities, such as novelty/OOD detection, novelty
characterization, adaption, risk assessment, and continual learning of the
detected novel items or objects [38]. Novelty detection, also called out-of-
distribution (OOD) detection, aims to detect unseen objects that the agent has
not learned. On detecting the novel objects or situation, the agent has to
respond or adapt its actions. But in order to adapt, it must first
characterize the novel object as without it, the agent would not know how to
respond or adapt. For example, it may characterize a detected novel object as
looking like a dog. Then, the agent may react like what it would react to a
dog. In the process, the agent also constantly assesses the risk of its
actions. Finally, it also learns to recognize the new object incrementally so
that it will not be surprised when it sees the same kind of object in the
future. This incremental learning function is called continual learning (CL)
or lifelong learning [14]. Note that before learning, the agent must obtain
labeled training data, which can be collected by the agent through interaction
with the environment or with human users. This aspect is out of the scope of
this paper. See [38] for details.

This paper focuses only on the key learning aspects of the open world
scenario: (1) OOD/novelty detection and (2) continual learning, more
specifically class incremental learning (CIL) (see the definition below). In
the research community, (1) and (2) are regarded as two completely different
problems, but this paper theoretically unifies them by proving that good OOD
detection is, in fact, necessary for CIL. Thus, a good CIL algorithm can
naturally be used in the open world to perform both (1) and (2). Below, we
first define the concepts of OOD detection and continual learning.

Out-of-distribution (OOD) detection: Given the training data
$\mathcal{D}=\\{(x^{i},y^{i})_{i=1}^{n}\\}$, where $n$ is the number of data
samples, and $x^{i}\in\mathbf{X}$ is an input sample and $y^{i}\in\mathbf{Y}$
(the set of all class labels in $\mathcal{D}$) is its class label, our goal is
to build a classifier $f:\mathbf{X}\rightarrow\mathbf{Y}\cup\\{O\\}$ that can
detect test instances that do not belong to any classes in $\mathbf{Y}$
(called OOD detection), which are assigned to the class $O$. $\mathbf{Y}$ is
often called the in-distribution (IND) classes.

Note that as we can see from the definition, an OOD detection algorithm can
also classify test instances belonging to $\mathbf{Y}$ to their respective
classes, which is called IND classification, although most OOD detection
papers do not report the IND classification results.

Continual learning (CL) aims to incrementally learn a sequence of tasks. Each
task consists of a set of classes to be learned together (the set may contain
only a single class). Once a task is learned, its training data (at least a
majority of it) is no longer accessible. Thus, unlike multitask learning, in
learning a new task, CL will not be able to use the data of the previous
tasks. A major challenge of CL is catastrophic forgetting (CF), which refers
to the phenomenon that in learning a new task, the neural network model
parameters need to be modified, which may corrupt the knowledge learned for
previous tasks in the network and cause performance degradation for the
previous tasks [43]. Although a large number of CL techniques have been
proposed, they are mainly empirical. Little theoretical work has been done on
how to solve CL. This paper performs such a theoretical study about the
necessary and sufficient conditions for effective CL. There are two main CL
settings that have been extensively studied: class incremental learning (CIL)
and task incremental learning (TIL) [60]. In CIL, the learning process builds
a single classifier for all tasks/classes learned so far. In testing, a test
instance from any class may be presented for the model to classify. No prior
task information (e.g., task-id) of the test instance is provided. Formally,
CIL is defined as follows.

Class incremental learning (CIL). CIL learns a sequence of tasks, $1,2,...,T$.
Each task $k$ has a training dataset
$\mathcal{D}_{k}=\\{(x_{k}^{i},y_{k}^{i})_{i=1}^{n_{k}}\\}$, where $n_{k}$ is
the number of data samples in task $k$, and $x_{k}^{i}\in\mathbf{X}$ is an
input sample and $y_{k}^{i}\in\mathbf{Y}_{k}$ (the set of all classes of task
$k$) is its class label. All $\mathbf{Y}_{k}$’s are disjoint
($\mathbf{Y}_{k}\cap\mathbf{Y}_{k^{\prime}}=\emptyset,\,\forall k\neq
k^{\prime}$) and $\bigcup_{k=1}^{T}\mathbf{Y}_{k}=\mathbf{Y}$. The goal of CIL
is to construct a single predictive function or classifier
$f:\mathbf{X}\rightarrow\mathbf{Y}$ that can identify the class label $y$ of
each given test instance $x$.

In the TIL setup, each task is a separate or independent classification
problem. For example, one task could be to classify different breeds of dog
and another task could be to classify different types of animal (the tasks may
not be disjoint). One model is built for each task in a shared network. In
testing, the task-id of each test instance is provided and the system uses
only the specific model for the task (dog or animal classification) to
classify the test instance. Formally, TIL is defined as follows.

Task incremental learning (TIL). TIL learns a sequence of tasks, $1,2,...,T$.
Each task $k$ has a training dataset
$\mathcal{D}_{k}=\\{((x_{k}^{i},k),y_{k}^{i})_{i=1}^{n_{k}}\\}$, where $n_{k}$
is the number of data samples in task $k\in\mathbf{T}=\\{1,2,...,T\\}$, and
$x_{k}^{i}\in\mathbf{X}$ is an input sample and
$y_{k}^{i}\in\mathbf{Y}_{k}\subset\mathbf{Y}$ is its class label. The goal of
TIL is to construct a predictor
$f:\mathbf{X}\times\mathbf{T}\rightarrow\mathbf{Y}$ to identify the class
label $y\in\mathbf{Y}_{k}$ for $(x,k)$ (the given test instance $x$ from task
$k$).

This paper focuses on CIL as it incrementally learns new (or novel) classes of
objects, which is a core function of open world learning. Although the
proposed methods also work for TIL, TIL is not a core part of open world
learning as it builds a model for each task separately and independently in a
shared neural network and the tasks are given by users. TIL is also much
simpler. Several existing techniques can effectively overcome CF for TIL (with
almost no CF) [55, 61]. However, CIL remains to be highly challenging due to
the additional problem of Inter-task Class Separation (ICS), i.e., how to
establish decision boundaries between the classes of the new task and the
classes of the previous tasks in learning the new tasks without accessing the
training data of the previous tasks.

Problem Statement (open-world continual learning (OCL)): OCL is defined as CIL
with the OOD detection capability. At any time, the resulting CIL model is
able to classify test instances belonging to the classes learned so far in CIL
to their respective classes and also detect OOD instances that do not belong
to any of the learned classes so far.

We note that OOD detection in CIL is slightly different from the traditional
OOD detection (which sees the full IND data together) because in CIL, the
model does not see all the IND data together. In CIL, the IND data comes in a
sequence of tasks incrementally and in learning each task, the model does not
see any data (or only a very small sample) of the previous tasks.

The main contribution of this paper is two-fold. First, it makes a theoretical
contribution by proving the necessary and sufficient conditions for solving
the CIL problem. It shows that a good OOD detection performance is one of the
necessary conditions. Thus, the proposed theory is also applicable to open-
world learning as novelty (OOD) detection is a key function of open-world
learning and open-world learning should also learn continually, i.e., open-
world continual learning. Second, based on the theory, several new CIL
algorithms are designed, which are also able to detect novel (or OOD)
instances for open-world continual learning (OCL).

Theory. We conduct a theoretical study of CIL, which is applicable to any CIL
classification model. Instead of focusing on the traditional PAC
generalization bound [48] or neural tangent kernel (NTK) [25], we focus on how
to solve the CIL problem. We first decompose the CIL problem into two sub-
problems in a probabilistic framework: Within-task Prediction (WP) and Task-id
Prediction (TP). WP means that the prediction for a test instance is only done
within the classes of the task to which the test instance belongs, which is
basically the TIL problem. TP predicts the task-id. TP is needed because in
CIL, task-id is not provided in testing. This paper then proves based on the
popular cross-entropy loss that (i) the CIL performance is bounded by WP and
TP performances, and (ii) TP and task OOD detection performance bound each
other (which connects CIL and OOD detection).

Key theoretical result: Regardless of whether WP and TP or OOD detection are
defined explicitly or implicitly by a CIL algorithm, good WP and good TP or
OOD detection are necessary and sufficient conditions for good CIL
performances.444This result is applicable to both batch/offline and
online/stream CIL and to CIL problems with blurry task boundaries which means
that some training data of a task may come later together with a future task.

The intuition of the theory is simple because if a CIL model is perfect at
detecting OOD samples for each task, which solves the ICS problem, then CIL is
reduced to WP, which is just the traditional single-task supervised learning
for each task and as indicated earlier, many OOD algorithms can also perform
IND classification, which is basically WP.

New CIL Algorithms for OCL. The theoretical result provides a principled
guidance for solving the CIL problem. Based on the theory, several new CIL
methods are designed, including (1) techniques based on the integration of a
TIL method and an OOD detection method, which outperforms strong baselines in
both the CIL and TIL settings by a large margin. This combination is
particularly attractive because TIL has achieved no forgetting, and we only
need a strong OOD detection technique that can perform both IND prediction and
OOD detection to learn each task to achieve strong CIL results. Note that we
do not propose a new OOD detection technique as there are numerous such
techniques in the literature. We will use two existing ones. (2) Another
method is based on a pre-trained model and an OOD replay technique, which
performs even better, outperforming existing baselines markedly in both CIL
and OOD detection in the OCL setting.

##  2 Related Work

Although a large number of algorithms have been proposed to solve the CIL
problem, they are mainly empirical. There are two works that focus on the
traditional PAC generalization bound [48] or NTK [25], but they do not tell
how to solve the CL problem. This paper focuses on how to solve the CIL
problem. To the best of our knowledge, we are not aware of any work that have
proposed a theory on how to solve CIL. Also, none of the existing work has
connected CIL and OOD detection. Our work shows that a good CIL algorithm can
naturally perform OOD detection in the open world. Below, we first survey four
popular families in CL approaches, which are mainly for overcoming
catastrophic forgetting (CF). We then discuss related works about open world
learning.

(1). Regularization-based methods prevent forgetting by restricting the
learned parameters for previous tasks from being modified significantly by
using a regularization term to penalize such changes [29, 68] or regularize
the representation or outputs from the previously learned network [35, 69].

(2). Replay-based methods [51, 11, 8, 7, 64] prevent forgetting by saving a
small amount of training data from previous tasks in a memory buffer and
jointly train the network using the current data and the previous task data
saved in the memory. Some methods in this family also study which samples in
memory should be used in replay [2] or which samples in the training data
should be saved for later reply [51, 40].

(3). Generative methods construct a generative network to generate raw
training data [56, 44, 4]. The generated data are used with the current task
training data to jointly train the classification network. [69] generates
features instead of raw data. The generated samples in these methods are used
to prevent forgetting in both the generative network and the discriminative
network.

(4). Parameter-isolation methods [55, 61] train a set of task-specific
parameters to effectively protect the important parameters of each task, which
thus has almost no forgetting. A limitation of the approach is that the
correct task-id of each test instance must be known to the system to select
the corresponding task-specific parameters at inference. These methods are
thus mainly used for TIL. Some CIL methods also used these methods [1, 45, 49,
22] and they have separate mechanisms to predict the task-id (more on this
below). However, their CIL performances are still far below that of recent
replay-based counterparts (see Sections 4.2 and 5.2 for details).

Two of our proposed CIL methods use two parameter-isolation methods (HAT [55]
and SupSup [61]) for task incremental learning (TIL) as one of the components.
As mentioned above, some recent CIL approaches have already used TIL methods.
In such cases, task-id needs to be predicted. CCG [1] constructs an additional
network to predict the task-id. iTAML [49] identifies the task-id of the test
data in a batch. A serious limitation of this is that it requires the test
data in a batch to belong to the same task. Our methods are different as they
can predict (implicitly) for a single test instance at a time. HyperNet [45]
and PR [22] propose an entropy based task-id prediction method. SupSup [61]
predicts task-id by finding the optimal superpositions at inference. However,
these methods perform poorly because they do not know OOD detection is the key
for accurate task-id prediction, although our methods do not explicitly
predict task-id for each test instance.

Open world learning has been studied by many researchers [54, 53, 6, 15, 37,
38]. However, the existing research mainly focused on novelty detection, also
called open set recognition or out-of-distribution (OOD) detection. Some
researchers have also studied learning the novel objects after they are
detected and manually labeled [6, 15, 63, 24]. However, none of them perform
continual learning, which has additional challenges of catastrophic forgetting
(CF) and inter-task class separation (ICS). Excellent surveys of novelty
detection or OOD detection and open world learning can be found in [65, 46,
47, 24]. [17] did novelty detection and also continual learning, but its
continual learning uses the regularization based method. It is quite weak
because it has serious forgetting. A position paper [31] recently presented
some nice blue sky ideas about open world learning, but it does not propose or
implement any algorithm.

Our proposed algorithms are quite different. In training, based on our theory,
we use two existing OOD detection methods to verify that our theory can guide
us to design new and much more effective CIL algorithms. In testing, our OOD
detection is in the open-world continual learning (OCL) setting, which has
been described in the introduction section.

There are also several papers that study novel class discovery [18], which is
defined as discovering the hidden classes in the detected novel or OOD
instances. Our work does not perform this function. We assume that the
training data for each new task is given. Performing automatic class label
discovery is still very challenging as in many cases, the class assignments
can be subjective and are determined by human users. For example, for a dog,
whether it should just be labeled as dog or a specific breed of dog is a
subjective decision and is depending on applications.

##  3 A Theoretical Study on Solving CIL

This section presents our theory for solving CIL, which also covers novelty or
OOD detection in the open world. It first shows that the CIL performance
improves if the within-task prediction (WP) performance and/or the task-id
prediction (TP) performance improve, and then shows that TP and OOD detection
bound each other, which indicates that CIL performance is controlled by WP and
OOD detection. This connects CIL and OOD detection. Finally, we study the
necessary conditions for a good CIL model, which includes a good WP, and a
good TP or OOD detection.

###  3.1 CIL Problem Decomposition

This sub-section first presents the assumptions made by CIL based on its
definition and then proposes a decomposition of the CIL problem into two sub-
problems. A CIL system learns a sequence of tasks
$\\{(\mathbf{X}_{k},\mathbf{Y}_{k})\\}_{k=1,\dots,T}$, where $\mathbf{X}_{k}$
is the domain of task $k$ and $\mathbf{Y}_{k}$ are classes of task $k$ as
$\mathbf{Y}_{k}=\\{\mathbf{Y}_{k,j}\\}$, where $j$ indicates the $j$th class
in task $k$. Let $\mathbf{X}_{k,j}$ to be the domain of $j$th class of task
$k$, where $\mathbf{X}_{k}=\bigcup_{j}\mathbf{X}_{k,j}$. For accuracy, we will
use $x\in\mathbf{X}_{k,j}$ instead of $\mathbf{Y}_{k,j}$ in probabilistic
analysis. Based on the definition of class incremental learning (CIL) (Section
1), the following assumptions are implied,

######  Assumption 1.

The domains of classes of the same task are disjoint, i.e.,
$\mathbf{X}_{k,j}\cap\mathbf{X}_{k,j^{\prime}}=\emptyset,\,\forall j\neq
j^{\prime}$.

######  Assumption 2.

The domains of tasks are disjoint, i.e.,
$\mathbf{X}_{k}\cap\mathbf{X}_{k^{\prime}}=\emptyset,\,\forall k\neq
k^{\prime}$.

For any ground event $D$, the goal of a CIL problem is to learn
$\mathbf{P}(x\in\mathbf{X}_{k,j}|D)$. This can be decomposed into two
probabilities, within-task IND prediction (WP) probability and task-id
prediction (TP) probability. WP probability is
$\mathbf{P}(x\in\mathbf{X}_{k,j}|x\in\mathbf{X}_{k},D)$ and TP probability is
$\mathbf{P}(x\in\mathbf{X}_{k}|D)$. We can rewrite the CIL problem using WP
and TP based on the two assumptions,

$\displaystyle\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D)$
$\displaystyle=\sum_{k=1,\dots,n}\mathbf{P}(x\in\mathbf{X}_{k,j_{0}}|x\in\mathbf{X}_{k},D)\mathbf{P}(x\in\mathbf{X}_{k}|D)$
(1)
$\displaystyle=\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|x\in\mathbf{X}_{k_{0}},D)\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
(2)

where $k_{0}$ means a particular task and $j_{0}$ a particular class in the
task.

Some remarks are in order about Eq. 2 and our subsequent analysis to set the
stage.

######  Remark 1.

Eq. 2 shows that if we can improve either the WP or TP performance, or both,
we can improve the CIL performance.

######  Remark 2.

It is important to note that our theory is not concerned with the learning
algorithm or training process. But we will propose some concrete CIL
algorithms based on the theoretical result in the experiment section.

######  Remark 3.

Note that the CIL definition and the subsequent analysis are applicable to
tasks with any number of classes (including only one class per task) and to
online CIL where the training data for each task or class comes gradually in a
data stream and may also cross task boundaries (blurry tasks [5]) because our
analysis is based on an already-built CIL model after training. Regarding
blurry task boundaries, suppose dataset 1 has classes {dog, cat, tiger} and
dataset 2 has classes {dog, computer, car}. We can define task 1 as {dog, cat,
tiger} and task 2 as {computer, car}. The shared class dog in dataset 2 is
just additional training data of dog appeared after task 1.

######  Remark 4.

Furthermore, CIL = WP * TP in Eq. 2 means that when we have WP and TP (defined
either explicitly or implicitly by implementation), we can find a
corresponding CIL model defined by WP * TP. Similarly, when we have a CIL
model, we can find the corresponding underlying WP and TP defined by their
probabilistic definitions.

In the following sub-sections, we develop this further concretely to derive
the sufficient and necessary conditions for solving the CIL problem in the
context of cross-entropy loss as it is used in almost all supervised CIL
systems.

###  3.2 CIL Improves as WP and/or TP Improve

As stated in Remark 2 above, the study here is based on a trained CIL model
and not concerned with the algorithm used in training the model. We use cross-
entropy as the performance measure of a trained model as it is the most
popular loss function used in supervised CL. For experimental evaluation, we
use accuracy following CL papers. Denote the cross-entropy of two probability
distributions $p$ and $q$ as

$\displaystyle H(p,q)\overset{def}{=}-\mathbb{E}_{p}[\log
q]=-\sum_{i}p_{i}\log q_{i}.$ (3)

For any $x\in\mathbf{X}$, let $y$ to be the CIL ground truth label of $x$,
where $y_{k_{0},j_{0}}=1$ if $x\in\mathbf{X}_{k_{0},j_{0}}$ otherwise
$y_{k,j}=0$, $\forall(k,j)\neq(k_{0},j_{0})$. Let $\tilde{y}$ be the WP ground
truth label of $x$, where $\tilde{y}_{k_{0},j_{0}}=1$ if
$x\in\mathbf{X}_{k_{0},j_{0}}$ otherwise $\tilde{y}_{k_{0},j}=0$, $\forall
j\neq j_{0}$. Let $\bar{y}$ be the TP ground truth label of $x$, where
$\bar{y}_{k_{0}}=1$ if $x\in\mathbf{X}_{k_{0}}$ otherwise $\bar{y}_{k}=0$,
$\forall k\neq k_{0}$. Denote

$\displaystyle H_{WP}(x)$
$\displaystyle=H(\tilde{y},\\{\mathbf{P}(x\in\mathbf{X}_{k_{0},j}|x\in\mathbf{X}_{k_{0}},D)\\}_{j}),$
(4) $\displaystyle H_{CIL}(x)$
$\displaystyle=H(y,\\{\mathbf{P}(x\in\mathbf{X}_{k,j}|D)\\}_{k,j}),$ (5)
$\displaystyle H_{TP}(x)$
$\displaystyle=H(\bar{y},\\{\mathbf{P}(x\in\mathbf{X}_{k}|D)\\}_{k})$ (6)

where $H_{WP}$, $H_{CIL}$ and $H_{TP}$ are the cross-entropy values of WP, CIL
and TP, respectively. We now present our first theorem. The theorem connects
CIL to WP and TP, and suggests that by having a good WP or TP, the CIL
performance improves as the upper bound for the CIL loss decreases.

######  Theorem 1.

If $H_{TP}(x)\leq\delta$ and $H_{WP}(x)\leq\epsilon$, we have
$H_{CIL}(x)\leq\epsilon+\delta.$

The detailed proof is given in A.1. This theorem holds regardless of whether
WP and TP are trained together or separately. When they are trained
separately, if WP is fixed and we let $\epsilon=H_{WP}(x)$, $H_{CIL}(x)\leq
H_{WP}(x)+\delta$, which means if TP is better, CIL is better. Similarly, if
TP is fixed, we have $H_{CIL}(x)\leq\epsilon+H_{TP}(x)$. When they are trained
concurrently, there exists a functional relationship between $\epsilon$ and
$\delta$ depending on implementation. But no matter what it is, when
$\epsilon+\delta$ decreases, CIL gets better.

Theorem 1 holds for any $x\in\mathbf{X}=\bigcup_{k}\mathbf{X}_{k}$ that
satisfies $H_{TP}(x)\leq\delta$ or $H_{WP}(x)\leq\epsilon$. To measure the
overall performance under expectation, we present the following corollary.

######  Corollary 1.

Let $U(\mathbf{X})$ represents the uniform distribution on $\mathbf{X}$. i) If
$\mathbb{E}_{x\sim U(\mathbf{X})}[H_{TP}(x)]\leq\delta$, then
$\mathbb{E}_{x\sim U(\mathbf{X})}[H_{CIL}(x)]\leq\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{WP}(x)]+\delta$. Similarly, ii) $\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{WP}(x)]\leq\epsilon$, then $\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{CIL}(x)]\leq\epsilon+\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{TP}(x)]$.

The proof is given in A.2. The corollary is a direct extension of Theorem 1 in
expectation. The implication is that given TP performance, CIL is positively
related to WP. The better the WP is, the better the CIL is as the upper bound
of the CIL loss decreases. Similarly, given WP performance, a better TP
performance results in a better CIL performance. Due to the positive relation,
we can improve CIL by improving either WP or TP using their respective methods
developed in each area.

###  3.3 Task Prediction (TP) to OOD Detection

Building on Eq. 2, we have studied the relationship of CIL, WP and TP in
Theorem 1. We now connect TP and OOD detection. They are shown to be dominated
by each other to a constant factor.

We again use cross-entropy $H$ to measure the performance of TP and OOD
detection of a trained network as in Section 3.2. To build the connection
between $H_{TP}(x)$ and OOD detection of each task, we first define the
notations of OOD detection. We use
$\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)$ to represent the probability
distribution predicted by the $k$th task’s OOD detector. Notice that the task
prediction (TP) probability distribution $\mathbf{P}(x\in\mathbf{X}_{k}|D)$ is
a categorical distribution over $T$ tasks, while the OOD detection probability
distribution $\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)$ is a Bernoulli
distribution. For any $x\in\mathbf{X}$, define

$\displaystyle H_{OOD,k}(x)=\left\\{\begin{aligned}
H(1,\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D))=-\log\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D),\
x\in\mathbf{X}_{k},\\\
H(0,\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D))=-\log\mathbf{P}^{\prime}_{k}(x\notin\mathbf{X}_{k}|D),\
x\notin\mathbf{X}_{k}.\end{aligned}\right.$ (7)

In CIL, the OOD detection probability for a task can be defined using the
output values corresponding to the classes of the task. Some examples of the
function is a sigmoid of maximum logit value or a maximum softmax probability
after re-scaling to 0 to 1. It is also possible to define the OOD detector
directly as a function of tasks instead of a function of the output values of
all classes of tasks, i.e. Mahalanobis distance. The following theorem shows
that TP and OOD detection bound each other.

######  Theorem 2.

i) If $H_{TP}(x)\leq\delta$, let
$\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)=\mathbf{P}(x\in\mathbf{X}_{k}|D)$,
then $H_{OOD,k}(x)\leq\delta,\forall\,k=1,\dots,T$. ii) If
$H_{OOD,k}(x)\leq\delta_{k},k=1,\dots,T$, let
$\mathbf{P}(x\in\mathbf{X}_{k}|D)=\frac{\mathbf{P}_{k}^{\prime}(x\in\mathbf{X}_{k}|D)}{\sum_{k}\mathbf{P}_{k}^{\prime}(x\in\mathbf{X}_{k}|D)}$,
then
$H_{TP}(x)\leq(\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}e^{\delta_{k}})(\sum_{k}1-e^{-\delta_{k}})$,
where $\mathbf{1}_{x\in\mathbf{X}_{k}}$ is an indicator function.

See A.3 for the proof. As we use cross-entropy, the lower the bound, the
better the performance is. The first statement (i) says that the OOD detection
performance improves if the TP performance gets better (i.e., lower $\delta$).
Similarly, the second statement (ii) says that the TP performance improves if
the OOD detection performance on each task improves (i.e., lower
$\delta_{k}$). Besides, since
$(\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}e^{\delta_{k}})(\sum_{k}1-e^{-\delta_{k}})$
converges to $0$ as $\delta_{k}$’s converge to $0$ in order of
$O(|\sum_{k}\delta_{k}|)$, we further know that $H_{TP}$ and
$\sum_{k}H_{OOD,k}$ are equivalent in quantity up to a constant factor.

In Theorem 1, we studied how CIL is related to WP and TP. In Theorem 2, we
showed that TP and OOD bound each other. Now we explicitly give the upper
bound of CIL in relation to WP and OOD detection of each task. The detailed
proof can be found in A.4.

######  Theorem 3.

If $H_{OOD,k}(x)\leq\delta_{k},\,k=1,\dots,T$ and $H_{WP}(x)\leq\epsilon$, we
have

$H_{CIL}(x)\leq\epsilon+(\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}e^{\delta_{k}})(\sum_{k}1-e^{-\delta_{k}}),$

where $\mathbf{1}_{x\in\mathbf{X}_{k}}$ is an indicator function.

###  3.4 Necessary Conditions for Improving CIL

In Theorem 1, we showed that good performances of WP and TP are sufficient to
guarantee a good performance of CIL. In Theorem 3, we showed that good
performances of WP and OOD are sufficient to guarantee a good performance of
CIL. For completeness, we study the necessary conditions of a well-performed
CIL in this sub-section.

######  Theorem 4.

If $H_{CIL}(x)\leq\eta$, then there exist i) a WP, s.t. $H_{WP}(x)\leq\eta$,
ii) a TP, s.t. $H_{TP}(x)\leq\eta$, and iii) an OOD detector for each task,
s.t. $H_{OOD,k}\leq\eta,\,k=1,\dots,T$.

The detailed proof is given in A.5. This theorem tells that if a good CIL
model is trained, then a good WP, a good TP and a good OOD detector for each
task are always implied. More importantly, by transforming Theorem 4 into its
contraposition, we have the following statements: If for any WP,
$H_{WP}(x)>\eta$, then $H_{CIL}(x)>\eta$. If for any TP, $H_{TP}(x)>\eta$,
then $H_{CIL}(x)>\eta$. If for any OOD detector,
$H_{OOD,k}(x)>\eta,\,k=1,\dots,T$, then $H_{CIL}(x)>\eta$. Regardless of
whether WP and TP (or OOD detection) are defined explicitly or implicitly by a
CIL algorithm, the existence of a good WP and the existence of a good TP or
OOD detection are necessary conditions for a good CIL performance.

######  Remark 5.

It is important to note again that our study in this section is based on a CIL
model that has already been built. In other words, our study tells the CIL
designers what should be achieved in the final model. Clearly, one would also
like to know how to design a strong CIL model based on the theoretical
results, which also considers catastrophic forgetting (CF). One effective
method is to make use of a strong existing TIL algorithm, which can already
achieve no or little forgetting (CF), and combine it with a strong OOD
detection algorithm (as mentioned earlier, most OOD detection methods can also
perform WP). Thus, any improved method from the OOD detection community can be
applied to CIL to produce improved CIL systems (see Sections 4.2.3 and 4.2.4).

Recall in Section 2, we reviewed prior works that have tried to use a TIL
method for CIL with a task-id prediction method [45, 3, 49, 1, 22]. However,
since they did not know that the key to the success of this approach is a
strong OOD detection algorithm, they are quite weak (see Sections 4.2 and
5.2).

######  Remark 6.

Since good OOD detection for each task is necessary for CIL, our theory thus
covers novelty (OOD) detection for open world learning.

##  4 Proposed Approach 1: Combining TIL and OOD Detection

Based on the above theoretical result, we designed two approaches (three
different methods) to solve CIL that employ OOD detection. One more method
will also be discussed in Section 4.2, which is a weaker post-processing OOD
detection technique. This section presents the first approach, which combines
a task incremental learning (TIL) method and an OOD detection method. The
approach does not save any training data from previous tasks. In the next
section, we present the second approach, which is based on replay and needs to
save some training data from previous tasks.

Figure 1:  Overview of prediction and training framework of HAT+CSI and
Sup+CSI. (a) HAT+CSI: The CIL prediction is made by argmax over the
concatenated output from each task. The training of each task uses CSI. That
is, the training batch is augmented to give different views of the samples for
contrastive training. The training consists of two steps following CSI. The
first step learns the feature extractor by using the hard attention algorithm
[55], which applies task embeddings to find hard masks at each layer. Then
given the learned feature representations, it fine-tunes the classifier in
step 2. (b) Sup+CSI: The CIL prediction is also made by taking argmax over the
concatenated output values from each task as HAT+CSI. The model training for
each task is similar to HAT+CSI except that it uses the Edge Popup algorithm
of SupSup [50] to find a sparse network for each task. The sparse networks,
which are indicated by edges of different colors in the diagram. The second
step fine-tunes the classifier only with the fixed feature extractor.

###  4.1 Combining a TIL Method and an OOD Detection Method

As mentioned earlier, several existing TIL methods can overcome CF. This
proposed approach basically leverages the CF prevention ability in two TIL
methods (HAT [55] and SupSup (Sup) [61]) and replaces their task learning
methods with an OOD detection technique, called CSI [58], which can perform
both within-task or IND prediction (WP) and OOD instance detection. Below, we
first introduce the two TIL methods, HAT and SupSup, and the OOD detection
method, CSI. The combinations give two new CIL methods, HAT+CSI and Sup+CSI.
None of these methods needs to save any data from previous tasks.

Figure 1 shows the overall training frameworks of HAT+CSI and Sup+CSI. Note
that both HAT and Sup are multi-head methods (one head for each task) designed
for task incremental learning (TIL).

####  4.1.1 HAT: Hard Attention Masks

To prevent forgetting of the trained OOD detection model $f^{k}\circ h^{k}$
for each task $k$ in subsequent task learning, the hard attention mask (HAT)
[55] for TIL is employed (which prevents forgetting in the feature extractor).
Specifically, in learning a task, a set of embeddings are trained to protect
the important neurons so that the corresponding parameters are not interfered
by subsequent tasks. The importance of a neuron is measured by the 0-1 pseudo-
step function, where 0 indicates not important and 1 indicates important (and
thus protected).

The hard attention mask is an output of sigmoid function $u$ with a hyper-
parameter $s$

$\displaystyle a_{l}^{k}=u(se_{l}^{k}),$ (8)

where $e_{l}^{k}$ is a learnable embedding at layer $l$ of task $k$. Since the
step function is not differentiable, a sigmoid function with a large $s$ is
used to approximate it. Sigmoid is approximately a 0-1 step function with a
large $s$. The attention is multiplied to the output
$h_{l}=\text{ReLU}(W_{l}h_{l-1}+b_{l})$ of layer $l$,

$\displaystyle h^{\prime}_{l}=a_{l}^{k}\otimes h_{l}$ (9)

The $j$th element $a_{j,l}^{k}$ in the attention mask blocks (or unblocks) the
information flow from neuron $j$ at layer $l$ if its value is $0$ (or $1$).
With 0 value of $a_{j,l}^{k}$, the corresponding parameters in $W_{l}$ and
$b_{l}$ can be freely changed as the output values $h^{\prime}_{l}$ are not
affected. The neurons with non-zero mask values are necessary to perform the
task, and thus need a protection for catastrophic forgetting.

We modify the gradients of parameters that are important in performing the
previous tasks $(1,\cdots,k-1)$ during training task $k$ so they are not
interfered. Denote the accumulated mask by

$\displaystyle a_{l}^{<k}=\max(a_{l}^{<k-1},a_{l}^{k-1})$ (10)

where $\max$ is element-wise maximum and the initial mask $a_{l}^{0}$ is a
zero vector. It is a collection of mask values at layer $l$ where a neuron has
value 1 if it has ever been activated previously. The gradient of parameter
$w_{ij,l}$ is modified as

$\displaystyle\nabla
w_{ij,l}^{\prime}=\left(1-\min\left(a_{i,l}^{<k},a_{j,l-1}^{<k}\right)\right)\nabla
w_{ij,l}$ (11)

where $a_{i,l}^{<k}$ is the $i$th unit of $a_{l}^{<k}$. The gradient flow is
blocked if both neurons $i$ in the current layer and $j$ in the previous layer
have been activated. We apply the mask for all layers except the last layer.
The parameters in last layer do not need to be protected as they are task-
specific parameters.

A regularization is introduced to encourage sparsity in $a_{l}^{k}$ and
parameter sharing with $a_{l}^{<k}$. The capacity of a network depletes when
$a_{l}^{<k}$ becomes 1-vector in all layers. Despite a set of new neurons can
be added in network at any point in training for more capacity, we utilize
resources more efficiently by minimizing the loss

$\displaystyle\mathcal{L}_{r}=\lambda\frac{\sum_{l}\sum_{i}a_{i,l}^{k}\left(1-a_{i,l}^{<k}\right)}{\sum_{l}\sum_{i}\left(1-a_{i,l}^{<k}\right)}$
(12)

where $\lambda$ is a hyper-parameter. The final objective to train a
comprehensive task network without forgetting is

$\displaystyle\mathcal{L}=\mathcal{L}_{ce}+\mathcal{L}_{r}$ (13)

where $\mathcal{L}_{ce}$ is the cross-entropy loss. The overall framework of
the algorithm is shown in Figure 1(a).

Note that for TIL, HAT needs the task-id for each test instance in order to
choose the right task model for prediction or classification. However, by
replacing the original model building method for each task in HAT with the OOD
detection method in CSI (more specifically, $\mathcal{L}_{c}$) during
training, HAT+CSI does not require to know the task-id of each test instance
at inference, which makes HAT+CSI suitable for CIL (class incremental
learning). We will see the detailed prediction/classification method in
Section 4.2.

####  4.1.2 SupSup: Supermasks in Superposition

SupSup (Sup) [61] is also a highly effective method that can overcome
forgetting in the TIL setting. Sup trains supermasks by Edge Popup algorithm
in [50]. More precisely, given initial $\mathbf{W}$, find binary masks
$\mathbf{M}_{k}$ for task $k$ to minimize the cross-entropy loss

$\displaystyle\mathcal{L}=-\frac{1}{|\mathbf{X}_{k}|}\sum\log p(y|x,k),$ (14)

where $\mathbf{X}_{k}$ is the training data for task $k$, and

$\displaystyle p(y|x,k)=f(h(x;\mathbf{W}\otimes\mathbf{M}_{k})),$ (15)

where $\otimes$ indicates element-wise product. The masks are obtained by
selecting the top $p$% of entries in the score matrices $\mathbf{V}$. The $p$
value determines the sparsity of the mask $\mathbf{M}_{k}$. The subnetwork
found by Edge Popup algorithm is indicated by different colors in Figure 1(b).

Like HAT, Sup is also for TIL and needs the task-id $k$ of each test instance
at inference. With $k$, the system (which is referred to as Sup GG in the
original Sup paper) uses the task-specific mask $\mathbf{M}_{k}$ to obtain the
classification output. Like HAT+CSI, by replacing the cross-entropy loss in
mask finding with the OOD detection loss in CSI, Sup+CSI also does not require
the task-id of each test instance, which makes Sup+CSI applicable to CIL
(class incremental learning). We will discuss the detailed
prediction/classification method in Section 4.2.

####  4.1.3 CSI: Contrasting Shifted Instances for OOD Detection

We now explain the OOD detection method CSI. CSI is based on contrastive
learning [13, 27] and data and class augmentations due to their excellent
performance [58]. Since here we focus on how to learn a single task based on
OOD detection, we omit the task-id unless necessary. The OOD training process
is similar to that of contrastive learning. It consists of two steps: Step 1
learns the feature representation by the composite $g\circ h$, where $h$ is
the feature extractor and $g$ is the projection to contrastive representation,
and Step 2 learns/fine-tunes the linear classifier $f$, mapping the feature
representation of $h$ to the label space (the classifier is the OOD model)).
This two-step training process is outlined in Figure 1(b). In the following,
we first describe the two-step training process and then explain how to make a
prediction based on an ensemble method to further improve prediction.

Step 1 (Contrastive Loss for Feature Learning). Supervised contrastive
learning is used to try to repel data of different classes and align data of
the same class more closely to make it easier to classify them. A key
operation is data augmentation via transformations.

Given a batch of $N$ samples, each sample ${x}$ is first duplicated. Each
version then goes through three initial augmentations (horizontal flip, color
changes, and Inception crop [57]) to generate two different views ${x}^{1}$
and ${x}^{2}$ (they keep the same class label as ${x}$). Denote the augmented
batch by $\mathcal{B}$, which now has $2N$ samples. In [21] and [58], it was
shown that using image rotations is effective in learning OOD detection models
because such rotations can effectively serve as out-of-distribution (OOD)
training data. For each augmented sample ${x}\in\mathcal{B}$ with class $y$ of
a task, we rotate ${x}$ by $90^{\circ},180^{\circ},270^{\circ}$ to create
three images, which are assigned three new classes $y_{1},y_{2}$, and $y_{3}$,
respectively. This results in a larger augmented batch $\tilde{\mathcal{B}}$.
Since we generate three new images from each ${x}$, the size of
$\tilde{\mathcal{B}}$ is $8N$. For each original class, we now have 4 classes.
For a sample ${x}\in\tilde{\mathcal{B}}$, let
$\mathcal{\tilde{B}}({x})=\mathcal{\tilde{B}}\backslash\\{{x}\\}$ and let
$P({x})\subset\tilde{\mathcal{B}}\backslash\\{{x}\\}$ be a set consisting of
the data of the same class as ${x}$ distinct from ${x}$. The contrastive
representation of a sample ${x}$ is ${z}_{x}=g(h({x,k}))/\|g(h({x,k}))\|$,
where $k$ is the current task. In learning, we minimize the supervised
contrastive loss.

$\displaystyle\mathcal{L}_{c}$
$\displaystyle=\frac{1}{8N}\sum_{{x}\in\tilde{\mathcal{B}}}\frac{-1}{|P({x})|}\sum_{{p}\in
P({x})}\log{\frac{\text{exp}({z}_{{x}}\cdot{z}_{{p}}/\tau)}{\sum_{{x}^{\prime}\in\tilde{\mathcal{B}}({x})}\text{exp}({z}_{{x}}\cdot{z}_{{x}^{\prime}}/\tau)}},$
(16)

where $\tau$ is a scalar temperature, $\cdot$ is dot product, and $\times$ is
multiplication. The loss is reduced by repelling ${z}$ of different classes
and aligning ${z}$ of the same class more closely. $\mathcal{L}_{c}$ basically
trains a feature extractor with good representations for learning an OOD
classifier.

Since the feature extractor is shared across tasks in continual learning, a
protection is needed to prevent catastrophic forgetting. HAT and Sup use their
respective techniques to protect their feature extractor from forgetting.
Therefore, the losses $\mathcal{L}$ of Eq. 14 and $\mathcal{L}_{ce}$ of Eq. 13
are replaced by Eq. 16 while the forgetting prevention mechanisms still hold.

Step 2 (Fine-tuning the Classifier). Given the feature extractor $h$ trained
with the loss in Eq. 16, we freeze $h$ and only fine-tune the linear
classifier $f$, which is trained to predict the classes of task $k$ and the
augmented rotation classes. $f$ maps the feature representation to the label
space in $\mathcal{R}^{4|\mathcal{C}^{k}|}$, where $4$ is the number of
rotation classes including the original data with $0^{\circ}$ rotation and
$|\mathcal{C}^{k}|$ is the number of original classes in task $k$. We minimize
the cross-entropy loss,

$\displaystyle\mathcal{L}_{\text{ft}}=-\frac{1}{|\tilde{\mathcal{B}}|}\sum_{({x},y)\in\tilde{\mathcal{B}}}\log\tilde{p}(y|{x},k),$
(17)

where ft indicates fine-tune, and

$\displaystyle\tilde{p}(y|{x},k)=\text{softmax}\left(f(h({x},k))\right)$ (18)

where $f(h({x,k}))\in\mathcal{R}^{4|\mathcal{C}^{k}|}$. The output
$f(h({x,k}))$ includes the rotation classes. The linear classifier is trained
to predict the original and the rotation classes. Since individual classifier
is trained for each task and the feature extractor is frozen, no protection is
necessary.

Ensemble Class Prediction. We now discuss the prediction of class label $y$
for a test sample ${x}$. Note that the network $f\circ h$ in Eq. 18 returns
logits for rotation classes (including the original task classes). Note also
for each original class label $j_{k}\in\mathcal{C}^{k}$ (original classes) of
a task $k$, we created three additional rotation classes. For class $j_{k}$,
the classifier $f$ will produce four output values from its four rotation
class logits, i.e., $f_{j_{k},0}(h({x_{0},k}))$,
$f_{j_{k},90}(h({x_{90},k}))$, $f_{j_{k},180}(h({x_{180},k}))$, and
$f_{j_{k},270}(h({x_{270},k}))$, where 0, 90, 180, and 270 represent
$0^{\circ},90^{\circ},180^{\circ}$, and $270^{\circ}$ rotations respectively
and ${x}_{0}$ is the original ${x}$. We compute an ensemble output
$f_{j_{k}}(h({x}))$ for each class $j_{k}\in\mathcal{C}^{k}$ of task $k$,

$\displaystyle
f(h({x,k}))_{j_{k}}=\frac{1}{4}\sum_{\text{deg}}f(h({x}_{\text{deg}},k))_{j_{k},\text{deg}}.$
(19)

###  4.2 Experiments

We now present the experimental results of the combination techniques HAT+CSI
and Sup+CSI for class incremental learning (CIL). We will also use another OOD
detection method ODIN [36] to show that better OOD detection method leads to
better CIL results. We do not conduct extensive experiments on ODIN as it is
much weaker than CSI in terms of ODD detection. Note that we will not report
the ODD detection results for HAT+CSI and Sup+CSI in the open world in the
continual learning process as the proposed method MORE in the next section
performs better.

####  4.2.1 Experimental Datasets and Baselines

Datasets and CIL tasks: We use three standard image classification benchmark
datasets and construct five different CIL experiments.

(1). CIFAR-10 [30]: This dataset consists of 32x32 color images of 10 classes
with 50,000 training and 10,000 testing samples. We construct an experiment
(C10-5T) of 5 tasks with 2 classes per task.

(2). CIFAR-100 [30]: This dataset consists of 32x32 color images of 100
classes with 50,000 training and 10,000 testing samples. We construct two
experiments of 10 tasks (C100-10T) and 20 tasks (C100-20T), where each task
has 10 classes and 5 classes, respectively.

(3). Tiny-ImageNet [32]: This is an image classification dataset with 64x64
color images of 200 classes with 100,000 training and 10,000 validation
samples. Since the dataset does not provide labels for testing data, we use
the validation data for testing. We construct two experiments of 5 tasks
(T-5T) and 10 tasks (T-10T) with 40 classes per task and 20 classes per task,
respectively.

Baselines: We use 18 diverse continual learning baselines:

(1). One projection method (OWM [67]).

(2). Two exemplar-free (no replay data is saved) regularization methods (MUC
[39] and PASS [69]).

(3). Nine replay-based methods (LwF [35], iCaRL [51], A-GEM [11], EEIL [8], GD
[34], Mnemonics [40], BiC [62], DER++ [7]], and HAL [10]).

(4). Three parameter-isolation methods (HAT [55], HyperNet [45], and SupSup
[61]).

(5). Additionally, we report the accuracies of replay-based method Co2L [9]
and parameter isolation methods CCG [1] and PR-Ent [22] from their original
papers as CCG has not released the code and we are unable to run Co2L and PR-
Ent on our machines.

####  4.2.2 Training Details and Evaluation Metrics

Training Details. For the backbone structure, we follow [61, 69, 7] and use
ResNet-18 [19]. For CIFAR-100 and Tiny-ImageNet, the number of channels are
doubled to fit more classes. For all baselines, the same ResNet-18 backbone
architecture is employed except for OWM and HyperNet, for which we use their
original architectures. OWM uses AlexNet. It is not obvious how to apply its
orthogonal projection technique to the ResNet structure. HyperNet uses
ResNet-32 and we are unable to replace it due to model initialization
arguments unexplained in the original paper. For the replay methods, we use
memory buffer 200 for CIFAR-10 and 2000 for CIFAR-100 and Tiny-ImageNet as in
[51, 7]. We use the hyper-parameters suggested by the authors. If we could not
reproduce any result, we use 10% of the training data as a validation set to
grid-search for good hyper-parameters. For our proposed methods, we report the
hyper-parameters in F. All the results are averages over 5 runs with random
seeds.

Evaluation Metrics.

(1). Average classification accuracy over all classes after learning the last
task. The final class prediction depends prediction methods (see below). We
also report forgetting rate in G.

(2). Average AUC (Area Under the ROC Curve) over all task models for the
evaluation of OOD detection. AUC is the main measure used in OOD detection
papers. Using this measure, we show that a better OOD detection method will
result in a better CIL performance. Let $\textit{AUC}_{k}$ be the AUC score of
task $k$. It is computed by using only the model (or classes) of task $k$ to
score the test data of task $k$ as the in-distribution (IND) data and the test
data from other tasks as the out-of-distribution (OOD) data. The average AUC
score is: $AUC=\sum_{k}\textit{AUC}_{k}/n$, where $n$ is the number of tasks.

It is not straightforward to change existing CL algorithms to include a new
OOD detection method that needs training, e.g., CSI, except for TIL (task
incremental learning) methods like HAT and Sup. For HAT and Sup, we can simply
switch their methods for learning each task with CSI (see Section 4.1.1 and
Section 4.1.2).

Prediction Methods. The theoretical result in Section 3 states that we use Eq.
2 to perform the final prediction. The first probability (WP) in Eq. 2 is easy
to get as we can simply use the softmax values of the classes in each task.
However, the second probability (TP) in Eq. 2 is tricky as each task is
learned without the data of other tasks. There can be many options. We take
the following approaches for prediction (which are a special case of Eq. 2,
see below):

(1). For those approaches that use a single classification head to include all
classes learned so far, we predict as follows (which is also the approach
taken by the existing papers.)

$\displaystyle\hat{y}=\operatorname*{arg\,max}f(x)$ (20)

where $f(x)$ is the logit output of the network.

(2). For multi-head methods (e.g., HAT, HyperNet, and Sup), which use one head
for each task, we use the concatenated output as

$\displaystyle\hat{y}=\operatorname*{arg\,max}\bigoplus_{k}f(x)_{k}$ (21)

where $\bigoplus$ indicate concatenation and $f(x)_{k}$ is the output of task
$k$.555The Sup paper proposed an one-shot task-id prediction assuming that the
test instances come in a batch and all belong to the same task like iTAML. We
assume a single test instance per batch. Its task-id prediction results in
accuracy of 50.2 on C10-5T, which is much lower than 62.6 by using Eq. 21. The
task-id prediction of HyperNet also works poorly. The accuracy by its task-id
prediction is 49.34 on C10-5T while it is 53.4 using Eq. 21. PR uses entropy
to find task-id. Among many variations of PR, we use the variations that
perform the best for each dataset with exemplar-free and single sample per
batch at testing (i.e., no PR-BW).

These methods (in fact, they are the same method used in two different
settings) are a special case of Eq. 2 if we define $OOD_{k}$ as $\sigma(\max
f(x)_{k})$, where $\sigma$ is the sigmoid. Hence, the theoretical results in
Section 3 are still applicable. We present a detailed explanation about this
prediction method and some other options in C. These two approaches work quite
well.

####  4.2.3 Better OOD Detection Produces Better CIL Performance

The key theoretical result in Section 3 is that better OOD detection will
produce better CIL performance. We compare a weaker OOD method ODIN with the
strong CSI. ODIN is a post-processing method for OOD detection [36]. Note that
it does not always improves the OOD detection performance compared to without
the ODIN post-processing (see below).

Table 1: Performance Comparison bewteen the Original Output and ODIN

| AUC | CIL
---|---|---
Method | Original | ODIN | Original | ODIN
OWM | 71.31 | 70.06 | 28.91 | 28.88
MUC | 72.69 | 72.53 | 30.42 | 29.79
PASS | 69.89 | 69.60 | 33.00 | 31.00
LwF | 88.30 | 87.11 | 45.26 | 51.82
A-GEM | 78.01 | 79.00 | 9.29 | 13.48
EEIL | 83.37 | 79.73 | 48.99 | 41.74
GD | 85.37 | 82.98 | 49.67 | 47.28
BiC | 87.89 | 86.73 | 52.92 | 48.65
DER++ | 85.99 | 88.21 | 53.71 | 55.29
HAL | 64.21 | 64.83 | 15.59 | 21.01
HAT | 77.72 | 77.80 | 41.06 | 41.21
HyperNet | 71.82 | 72.32 | 30.23 | 30.83
Sup | 79.16 | 80.58 | 44.58 | 46.74

Performance comparison based on C100-10T between the original output and the
output post-processed with OOD detection technique ODIN. Note that ODIN is not
applicable to iCaRL and Mnemonics as they are not based on softmax but some
distance functions. As mentioned earlier, for Co2L, CCG, and PR-Ent, they
either have no code or their codes do not run on our machine. The results for
other datasets are in B.

Applying ODIN. We first train the baseline models using their original
algorithms, and then apply temperature scaling and input noise of ODIN at
testing for each task (no training data needed). More precisely, the output of
class $j$ in task $k$ changes by temperature scaling factor $\tau_{k}$ of task
$k$ as

$\displaystyle
s(x;\tau_{k})_{j}=e^{f(x)_{kj}/\tau_{k}}/\sum_{j}e^{f(x)_{kj}/\tau_{k}}$ (22)

and the input changes by the noise factor $\epsilon_{k}$ as

$\displaystyle\tilde{x}=x-\epsilon_{k}\text{sign}(-\nabla_{x}\log
s(x;\tau_{k})_{\hat{y}})$ (23)

where $\hat{y}$ is the class with the maximum output value in task $k$. This
is a positive adversarial example inspired by [16]. The values $\tau_{k}$ and
$\epsilon_{k}$ are hyper-parameters and we use the same values for all tasks
except for PASS, for which we use a validation set to tune $\tau_{k}$ (see B).

Table 1 gives the results for C100-10T. The CIL results clearly show that the
CIL performance increases if the AUC increases with ODIN. For instance, the
CIL of DER++ and Sup improves from 53.71 to 55.29 and 44.58 to 46.74,
respectively, as the AUC increases from 85.99 to 88.21 and 79.16 to 80.58. It
shows that when this method is incorporated into each task model in existing
trained CIL network, the CIL performance of the original method improves. We
note that ODIN does not always improve the average AUC. For those experienced
a decrease in AUC, the CIL performance also decreases except LwF. The
inconsistency of LwF is due to its severe classification bias towards later
tasks as discussed in BiC [62]. The temperature scaling in ODIN has a similar
effect as the bias correction in BiC, and the CIL of LwF becomes close to that
of BiC after the correction. Regardless of whether ODIN improves AUC or not,
the positive correlation between AUC and CIL (except LwF) verifies the
efficacy of Theorem 3, indicating better OOD detection results in better CIL
performances.

Table 2: Average CIL and AUC after Applying OOD Detection Methods ODIN and CSI

CL | OOD | C10-5T | C100-10T | C100-20T | T-5T | T-10T
---|---|---|---|---|---|---
|  | AUC | CIL | AUC | CIL | AUC | CIL | AUC | CIL | AUC | CIL
HAT | ODIN | 82.5 | 62.6 | 77.8 | 41.2 | 75.4 | 25.8 | 72.3 | 38.6 | 71.8 | 30.0
CSI | 91.2 | 87.8 | 84.5 | 63.3 | 86.5 | 54.6 | 76.5 | 45.7 | 78.5 | 47.1
Sup | ODIN | 82.4 | 62.6 | 80.6 | 46.7 | 81.6 | 36.4 | 74.0 | 41.1 | 74.6 | 36.5
CSI | 91.6 | 86.0 | 86.8 | 65.1 | 88.3 | 60.2 | 77.1 | 48.9 | 79.4 | 45.7

Average CIL and AUC of HAT and Sup with OOD detection methods ODIN and CSI.
ODIN is a traditional OOD detection method while CSI is a recent OOD detection
method known to be better than ODIN. As CL methods produce better OOD
detection performance by CSI, their CIL performances are better than the ODIN
counterparts.

Applying CSI. We now apply the OOD detection method CSI. Due to its
sophisticated data augmentation, supervised constrative learning and results
ensemble, it is hard to apply CSI to other baselines without fundamentally
change them except for HAT and Sup (SupSup) as these methods are parameter
isolation-based TIL methods. We can simply replace their model for training
each task with CSI wholesale. As mentioned earlier, both HAT and Sup as TIL
methods have almost no forgetting.

Table 2 reports the results of using CSI and ODIN. ODIN is a weaker OOD method
than CSI. Both HAT and Sup improve greatly as the systems are equipped with a
better OOD detection method CSI. These experiment results empirically
demonstrate the efficacy of Theorem 3, i.e., the CIL performance can be
improved if a better OOD detection method is used.

####  4.2.4 Full Comparison of HAT+CSI and Sup+CSI with Baselines

Table 3: Average Accuracy (CIL) of All Methods

| Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T | Avg.
---|---|---|---|---|---|---|---
(a) | OWM | 51.8  $\pm$0.05 | 28.9  $\pm$0.60 | 24.1  $\pm$0.26 | 10.0  $\pm$0.55 | 8.6  $\pm$0.42 | 24.7
(b) | MUC | 52.9  $\pm$1.03 | 30.4  $\pm$1.18 | 14.2  $\pm$0.30 | 33.6  $\pm$0.19 | 17.4  $\pm$0.17 | 29.7
PASS† | 47.3  $\pm$0.98 | 33.0  $\pm$0.58 | 25.0  $\pm$0.69 | 28.4  $\pm$0.51 | 19.1  $\pm$0.46 | 30.6
(c) | LwF | 54.7  $\pm$1.18 | 45.3  $\pm$0.75 | 44.3  $\pm$0.46 | 32.2  $\pm$0.50 | 24.3  $\pm$0.26 | 40.2
iCaRL∗ | 63.4  $\pm$1.11 | 51.4  $\pm$0.99 | 47.8  $\pm$0.48 | 37.0  $\pm$0.41 | 28.3  $\pm$0.18 | 45.6
A-GEM | 20.0  $\pm$0.37 | 9.3  $\pm$0.17 | 4.1  $\pm$0.89 | 13.5  $\pm$0.08 | 7.7  $\pm$0.07 | 10.9
EEIL | 57.1  $\pm$0.28 | 49.0  $\pm$1.27 | 33.5  $\pm$0.08 | 14.7  $\pm$0.40 | 9.8  $\pm$0.19 | 32.8
GD | 58.7  $\pm$0.31 | 49.7  $\pm$0.33 | 38.9  $\pm$0.02 | 16.4  $\pm$1.40 | 11.7  $\pm$0.25 | 35.1
Mnemonics†∗ | 64.1  $\pm$1.47 | 51.0  $\pm$0.34 | 47.6  $\pm$0.74 | 37.1  $\pm$0.46 | 28.5  $\pm$0.72 | 45.7
BiC | 61.4  $\pm$1.74 | 52.9  $\pm$0.64 | 48.9  $\pm$0.54 | 41.7  $\pm$0.74 | 33.8  $\pm$0.40 | 47.7
DER++ | 66.0  $\pm$1.20 | 53.7  $\pm$1.30 | 46.6  $\pm$1.44 | 35.8  $\pm$0.77 | 30.5  $\pm$0.47 | 46.5
HAL | 32.8  $\pm$2.17 | 15.6  $\pm$0.31 | 13.5  $\pm$1.53 | 3.4  $\pm$0.35 | 3.4  $\pm$0.38 | 13.7
Co2L | 65.6 |  |  |  |  |
(d) | CCG | 70.1 |  |  |  |  |
HAT | 62.7  $\pm$1.45 | 41.1  $\pm$0.93 | 25.6  $\pm$0.51 | 38.5  $\pm$1.85 | 29.8  $\pm$0.65 | 39.5
HyperNet | 53.4  $\pm$2.19 | 30.2  $\pm$1.54 | 18.7  $\pm$1.10 | 7.9  $\pm$0.69 | 5.3  $\pm$0.50 | 23.1
Sup | 62.4  $\pm$1.45 | 44.6  $\pm$0.44 | 34.7  $\pm$0.30 | 41.8  $\pm$1.50 | 36.5  $\pm$0.36 | 44.0
PR-Ent | 61.9 | 45.2 |  |  |  |
(e) | HAT+CSI | 87.8  $\pm$0.71 | 63.3  $\pm$1.00 | 54.6  $\pm$0.92 | 45.7  $\pm$0.26 | 47.1  $\pm$0.18 | 59.7
Sup+CSI | 86.0  $\pm$0.41 | 65.1  $\pm$0.39 | 60.2  $\pm$0.51 | 48.9  $\pm$0.25 | 45.7  $\pm$0.76 | 61.2
HAT+CSI+c | 88.0  $\pm$0.48 | 65.2  $\pm$0.71 | 58.0  $\pm$0.45 | 51.7  $\pm$0.37 | 47.6  $\pm$0.32 | 62.1
Sup+CSI+c | 87.3  $\pm$0.37 | 65.2  $\pm$0.37 | 60.5  $\pm$0.64 | 49.2  $\pm$0.28 | 46.2  $\pm$0.53 | 61.7

Average accuracy after all tasks are learned. The baselines are grouped into
(a), (b), (c), and (d) for projection, regularization, replay, and parameter-
isolation methods, respectively. Our proposed methods are grouped into (e).
Exemplar-free methods are italicized. $\dagger$ indicates that in their
original papers, PASS and Mnemonics are pre-trained with the first half of the
classes. Their results with pre-train are 50.1 and 53.5 on C100-10T,
respectively, which are still much lower than the proposed HAT+CSI and Sup+CSI
without pre-training. We do not use pre-training in our experiment for
fairness. $*$ indicates that iCaRL and Mnemonics report average incremental
accuracy in their original papers. We report average accuracy over all classes
after all tasks are learned. The last column Avg. shows the average CIL
accuracy of each method over all datasets.  Table 4: TIL Accuracy

Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T | Avg.
---|---|---|---|---|---|---
BiC | 95.4  $\pm$0.35 | 84.6  $\pm$0.48 | 88.7  $\pm$0.19 | 61.5  $\pm$0.60 | 62.2  $\pm$0.45 | 78.5
HAT | 96.7  $\pm$0.18 | 84.0  $\pm$0.23 | 85.0  $\pm$0.98 | 61.2  $\pm$0.72 | 63.8  $\pm$0.41 | 78.1
Sup | 96.6  $\pm$0.21 | 87.9  $\pm$0.27 | 91.6  $\pm$0.15 | 64.3  $\pm$0.24 | 68.4  $\pm$0.22 | 81.8
HAT+CSI | 98.7  $\pm$0.06 | 92.0  $\pm$0.37 | 94.3  $\pm$0.06 | 68.4  $\pm$0.16 | 72.4  $\pm$0.21 | 85.2
Sup+CSI | 98.7  $\pm$0.07 | 93.0  $\pm$0.13 | 95.3  $\pm$0.20 | 65.9  $\pm$0.25 | 74.1  $\pm$0.28 | 85.4

TIL (WP) results of 3 best performing baselines and our methods. The full
results are given in E. The calibrated versions (+c) of our methods are
omitted as calibration does not affect TIL performances.

We now make a full comparison of the two proposed systems HAT+CSI and Sup+CSI
designed based on the theoretical results with baselines. Since HAT and Sup
are exemplar-free CL methods, HAT+CSI and Sup+CSI do not need to save any
previous task data for replaying. Table 3 shows that HAT and Sup equipped with
CSI outperform the baselines by large margins. DER++, the best replay method,
achieves 66.0 and 53.7 on C10-5T and C100-10T, respectively, while HAT+CSI
achieves 87.8 and 63.3 and Sup+CSI achieves 86.0 and 65.1. The large
performance gap remains consistent in more challenging problems, T-5T and
T-10T.

Due to the definition of OOD in the prediction method and the fact that each
task is trained separately in HAT and Sup, the outputs $f(x)_{k}$ from
different tasks can be in different scales, which will result in incorrect
predictions. To deal with the problem, we can calibrate the output as
$\alpha_{k}f(x)_{k}+\beta_{k}$ and use
$OOD_{k}=\sigma(\alpha_{k}f(x)_{k}+\beta_{k})$. The optimal $\alpha_{k}^{*}$
and $\beta_{k}^{*}$ for each task $k$ can be found by optimization with a
memory buffer to save a very small number of training examples from previous
tasks like that in the replay-based methods. We refer the calibrated methods
as HAT+CSI+c and Sup+CSI+c. They are trained by using the memory buffer of the
same size as the replay methods (see Section 4.2.2). Table 3 shows that the
calibration improves from their memory free versions, i.e., without
calibration. We provide the details about how to train the calibration
parameters $\alpha_{k}$ and $\beta_{k}$ in D.

As shown in Theorem 1, the CIL performance also depends on the TIL (WP)
performance. We compare the TIL accuracies of the baselines and our methods in
Table 4. Our systems again outperform the baselines by large margins on more
challenging datasets (e.g., CIFAR100 and Tiny-ImageNet).

##  5 Proposed Approach 2: Out-of-Distribution Replay

The approach presented above does not save any training data from previous
tasks except for the optional step of calibration. The method presented in
this section is based on the replay approach to solving CIL, which saves a
small number of training data from each previous task. The proposed method is
called Multi-head model for continual learning via OOD REplay (MORE).

###  5.1 The Proposed MORE Technique

Recall a replay-based method for continual learning works by memorizing or
saving a small subset of the training samples from each previous task in a
memory buffer. The saved data is called the replay data. In learning a new
task, the new task data and the replay data are trained jointly to update the
model. Clearly, using the replay data can partially deal with the inter-class
separation (ICS) problem because the model sees some data from all classes
learned so far. However, it cannot solve the ICS problem completely because
the amount of the replay data is often very small.

Unlike existing replay-based CIL methods, which simply use the replay data to
update the decision boundaries between the old class and the new classes (in
the new task), the proposed method uses the replay data to build an OOD
detection model for each task in continual learning, which gives the name of
the proposed method, i.e., out-of-distribution replay. Further, unlike
existing OOD detection methods, which usually do not use any OOD data in
training, the proposed method uses the replay data from previous tasks as the
OOD data for the current new task in building its OOD detection model.

Unlike HAT+CSI and Sup+CSI, which do not use a pre-trained network, MORE
trains a multi-head network as an adapter [23] to a pre-trained network (see
Figure 2(b)). Note that using a pre-trained transformer network and adapter
modules is a common practice in existing continual learning methods in the
natural language processing community [26]. Here we also leverage this
approach for image classification tasks. In continual learning, the pre-
trained network is frozen, only the adapters and the norm layers are
trainable. Similar to HAT+CSI, hard attention mask (HAT) is again employed to
protect each task model or classifier to avoid forgetting. Each head is also
an OOD detection model for a task, but, as mentioned above, MORE uses the
replay data as the OOD data to build an OOD detection model. Since HAT has
been described in Section 4.1.1, we will not discuss it further except to
state that we need to use $\mathcal{L}_{ood}$ in Eq. 24 to replace
$\mathcal{L}_{ce}$ in Eq. 13 after incorporating the trainable embedding
${\bm{e}}^{k}$. We describe the whole training and prediction process in H.

####  5.1.1 Training an OOD Detection Model

At task $k$, the system receives the training data
$\mathcal{D}_{k}=\\{(x_{k}^{i},y_{k}^{i})_{i=1}^{n_{k}}\\}$, where $n_{k}$ is
the number of samples, and $x_{k}^{i}\in\mathbf{X}_{k}$ is an input sample and
$y_{k}^{i}\in\mathbf{Y}_{k}$ (the set of all classes of task $k$) is its class
label. We train the feature extractor $z=h(x,k;\theta)$ and task specific
classifier $f(z;\phi_{k})$ using $\mathcal{D}_{k}$ and the samples in the
memory buffer $\mathcal{M}$. We treat the buffer data as OOD data to encourage
the network to learn the current task and also detect ODD samples (the models
or classifiers of the previous tasks are not touched). We achieve it by
maximizing $p(y|x,k)=\text{softmax}f(h(x,k;\theta);\phi_{k})$ for an IND
sample $x\in\mathbf{X}_{k}$ and maximizing $p(ood|x,k)$ for an OOD sample
$x\in\mathcal{M}$. The additional label $ood$ is reserved for previous and
possible future unseen classes. Figure 2(a) shows the overall idea of the
proposed approach. We formulate the problem as follows.

Figure 2:  (a) We train the feature extractor and the task classifier $k$ at
task $k$. The output values of the classifier correspond to
$|\mathbf{Y}_{k}|+1$ classes, in which the last class is for OOD (i.e.,
representing previous and unseen future classes). At inference/testing, the
probability values of each task model without the OOD class are concatenated
and the system chooses the class with the maximum score. (b) Transformer and
adapter module. The masked adapter network consists of 2 fully connected
layers and task specific masks. During training, only the masked adapters and
norm layers are updated and the other parts in the transformer layers remain
unchanged.

Given the training data $\mathbf{X}_{k}$ of size $n_{k}$ at task $k$ and the
memory buffer $\mathcal{M}$ of size $M$, we minimize the loss

$\displaystyle\small\begin{split}\mathcal{L}_{ood}(\theta,\phi_{k})=-\frac{1}{M+N}\left(\sum_{(x,y)\in\mathcal{M}}\log
p(ood|x,k)+\sum_{(x,y)\in\mathcal{D}^{k}}\log p(y|x,k)\right)\end{split}$ (24)

It is the sum of two cross-entropy losses. The first loss is for learning OOD
samples while the second loss is for learning the classes from the current
task. We optimize the shared parameter $\theta$ in the feature extractor. The
task specific classification parameters $\phi_{k}$ are independent of other
tasks. The learned representation on the current data should be robust to OOD
data. The classifier thus can classify both IND and OOD data.

In testing, we perform prediction by comparing the softmax probability output
values using all the task classifiers from task 1 to $k$ without the OOD class
as

$\displaystyle\hat{y}=\operatorname*{arg\,max}\bigoplus_{1\leq j\leq
k}p(\mathbf{Y}_{j}|x,j)$ (25)

where $\bigoplus$ is the concatenation over the output space. Figure 2(a)
shows the prediction rule. We are basically choosing the class with the
highest softmax probability over all classes from all learned tasks.

####  5.1.2 Back-Updating the Previous OOD Models

Each task model works better if more diverse OOD data is provided during
training. As in a replay-based approach, MORE saves an equal number of samples
per class after each task [12]. The saved samples in the memory are used as
OOD samples for each new task. Thus, in the beginning of continual learning
when the system is trained on only a small number of tasks, the classes of
samples in the memory are less diverse than after more tasks are learned. This
makes the performance of OOD detection stronger for later tasks, but weaker in
earlier tasks. To prevent this asymmetry, we update the model of each previous
task so that it can also identify the samples from subsequent classes (which
were unseen during the training of the previous task) as OOD samples.

At task $k$, we update the previous task models $(j=1,\cdots,k-1)$ as follows.
Denote the samples of task $j$ in memory $\mathcal{M}$ by
$\tilde{\mathbf{X}}_{j}$. We construct a new dataset using the current task
dataset and the samples in the memory buffer. We randomly select
$|\mathcal{M}|$ samples from the training data $\mathcal{D}_{k}$ and pool them
with the remaining samples in $\mathcal{M}$ after removing the IND samples
$\tilde{\mathcal{D}_{j}}$ of task $j$ from $\mathcal{M}$. We do not use the
entire training data $\mathcal{D}_{k}$ as we do not want a large sample
imbalance between IND and OOD. Denote the new dataset by
$\tilde{\mathcal{M}}$. Using the data, we update only the parameters
$\phi_{j}$ of the classifier for task $j$ with the feature representations
frozen by minimizing the loss

$\displaystyle\mathcal{L}(\phi_{j})=-\frac{1}{2M}\left(\sum_{(x,y)\in\tilde{\mathcal{M}}}\log
p(ood|x,j)+\sum_{(x,y)\in\tilde{\mathcal{D}}_{j}}\log p(y|x,j)\right)$ (26)

We reduce the loss by updating the parameters of classifier $j$ to maximize
the probability of the class if the sample belongs to task $j$ and maximize
the OOD probability otherwise.

####  5.1.3 Improving Prediction Performance by a Distance Based Technique

We further improve the prediction in Eq. 25 by introducing a distance based
factor used as a coefficient to the softmax probabilities in Eq. 25. It is
quite intuitive that if a test instance is close to a class, it is more likely
to belong to the class. We thus propose to combine this new distance factor
and the softmax probability output of the task $j$ model to make the final
prediction decision. In some sense, this can be considered as an ensemble of
the two methods.

We define the distance based coefficient $s_{j}(x)$ of task $j$ for the test
instance $x$ by the maximum of inverse Mahalanobis distance [33] between the
feature of $x$ and the Gaussian distributions of the classes in task $j$
parameterized by the mean $\mu_{j}^{i}$ of the class $i$ in task $j$ and the
sample covariance $S_{j}$. They are estimated by the features of class $i$’s
training data for each class $i$ in task $j$. If a test instance is from the
task, its feature should be close to the distribution that the instance
belongs to. Conversely, if the instance is OOD to the task, its feature should
not be close to any of the distributions of the classes in the task. More
precisely, for task $j$ with class $y_{1},\cdots,y_{|\mathbf{Y}_{j}|}$ (where
${|\mathbf{Y}_{j}|}$ represents the number of classes in task $k$), we define
the coefficient $s_{j}(x)$ as

$\displaystyle
s_{j}(x)=\max\left[1/\text{MD}(x;\mu_{j}^{y_{1}},S_{j}),\cdots,1/\text{MD}(x;\mu_{j}^{y_{|\mathbf{Y}_{j}|}},S_{j})\right]$
(27)

$\text{MD}(x;\mu_{j}^{i},S_{j})$ is the Mahalanobis distance. The coefficient
is large if at least one of the Mahalanobis distances is small but the
coefficient is small if all the distances are large (i.e. the feature is far
from all the distributions of the task). The parameters $\mu_{j}^{i}$ and
$S_{j}$ can be computed and saved when each task is learned. The mean
$\mu_{j}^{i}$ is computed using the training samples $\mathcal{D}^{i}_{j}$ of
class $i$ as follows,

$\displaystyle\mu_{j}^{i}=\sum_{x\in\mathcal{D}^{i}_{j}}h(x,i)/|\mathcal{D}^{i}_{j}|$
(28)

and the covariance $S_{j}$ of task $j$ is the mean of covariances of the
classes in task $j$,

$\displaystyle S_{j}=\sum_{i\in\mathbf{Y}_{j}}S^{i}_{j}/|\mathbf{Y}_{j}|$ (29)

where
$S^{i}_{j}=\sum_{x\in\mathcal{D}^{i}_{j}}(x-\mu_{j}^{i})^{T}(x-\mu_{j}^{i})/|\mathcal{D}^{i}_{j}|$
is the sample covariance of class $i$. By multiplying the coefficient
$s_{j}(x)$ to the original softmax probabilities $p(\mathbf{Y}_{j}|x,j)$, the
task output $p(\mathbf{Y}_{j}|x,j)s_{j}(x)$ increases if $x$ is from task $j$
and decreases otherwise. The final prediction is made by (which replaces Eq.
25)

$\displaystyle y=\operatorname*{arg\,max}\bigoplus_{1\leq j\leq
k}p(\mathbf{Y}_{j}|x,j)s_{j}(x),$ (30)

where $k$ is the last task that we have learned.

###  5.2 Experiments

We now report the experiment results of the proposed method MORE. For
experimental datasets, we use the same three image classification benchmark
datasets as in Section 4.2.1. For baselines, the same systems are used as well
(see Section 4.2.1) except Mnemonics, HyperNet, CCG, Co2L, and PR-Ent.
Mnemonics requires optimization of training instances and it is not clear how
to implement for images after interpolation for a given input size of a pre-
trained model (see below). For HyperNet, it is due to the reason explained in
Training Details in Section 4.2.2. For CCG, Co2L, and PR-Ent, CCG has no code
and the codes of Co2L, and PR-Ent do not run in our environment and thus we
could not convert their codes to use a pre-trained model. Finally, we are left
with 13 baselines. Note that HAT-CSI and Sup+CSI are not included as they are
much weaker (up to 15% lower than MORE in accuracy) as CSI’s approach of using
contrastive learning and data augmentations does not work well with a pre-
trained model.

Evaluation Metrics. We still use the same evaluation measures as we used in
Section 4.2.2. (1). Average classification accuracy over all classes after
learning the last task. (2). Average AUC (Area Under the ROC Curve) for
evaluating OOD detection performance of continual learning in the open world.
See Section 5.2.4 for more details.

####  5.2.1 Pre-trained Network

We pre-train a vision transformer [59] using a subset of the ImageNet data
[52] and apply the pre-trained network/model to all baselines and our method.
To ensure that there is no overlapping of data between ImageNet and our
experimental datasets, we manually removed 389 classes from the original 1000
classes in ImageNet that are similar/identical to the classes in CIFAR-10,
CIFAR-100, or Tiny-ImageNet. We pre-train the network with the remaining
subset of 611 classes of ImageNet.

Using the pre-trained network, both our system and the baselines improve
dramatically compared to their versions without using the pre-trained network.
For instance, the two best baselines (DER++ and PASS) in our experiments
achieve the average classification accuracy of 66.89 and 68.25 (after the
final task) with the pre-trained network over 5 experiments while they achieve
only 46.88 and 32.42 without using the pre-train network.

We insert an adapter module at each transformer layer to exploit the pre-
trained transformer network in continual learning. During training, the
adapter module and the layer norm are trained while the transformer parameters
are unchanged to prevent forgetting in the pre-trained network.

####  5.2.2 Training Details

For all experiments, we use the same backbone architecture DeiT-S/16 [59] with
a 2-layer adapter [23] at each transformer layer, and the same class order for
both baselines and our method. The first fully-connected layer in adapter maps
from dimension 384 to bottleneck. The second fully-connected layer following
ReLU activation function maps from bottleneck to 384. The the bottleneck
dimension is the same for all adapters in a model. For our method, we use SGD
with momentum value 0.9. The back-updating method in Section 5.1.2 is also a
hyper-parameter choice. If we apply it, we train each classifier for 10 epochs
by SGD with learning rate 0.01, batch size 16, and momentum value 0.9. We
choose 500 for $s$ in Eq. 8 and 0.75 for $\lambda$ in Eq. 12 as recommended in
[55]. We find a good set of learning rate and number of epochs on the
validation set made of 10% of the training data. We follow [12] and save an
equal number of random samples per class in the replay memory. Following the
experiment settings in [51, 69], we fix the size of memory buffer and reduce
the saved samples to accommodate a new set of samples after a new task is
learned. We use the class order protocol in [51, 7] by generating random class
orders for the experiments. The baselines and our method use the same class
ordering. We also report the size of memory required for each experiment in I.

For CIFAR-10, we split 10 classes into 5 tasks (2 classes per task). The
bottleneck size in each adapter is 64. Following [7], we use the memory size
200, and train for 20 epochs with learning rate 0.005, and apply the back-
updating method in Section 5.1.2.

For CIFAR-100, we conduct 10 tasks and 20 tasks experiments, where each task
has 10 classes and 5 classes, respectively. We double the bottleneck size of
the adapter to learn more classes. We use the memory size 2000 following [51]
and train for 40 epochs with learning rate 0.001 and 0.005 for 10 tasks and 20
tasks, respectively, and apply the back-updating method in Section 5.1.2.

For Tiny-ImageNet, two experiments are conducted. We split 200 classes into 5
and 10 tasks, where each task has 40 classes and 20 classes per task,
respectively. We use the bottleneck size 128, and save 2000 samples in memory.
We train with learning rate 0.005 for 15 and 10 epochs for 5 tasks and 10
tasks, respectively. There is no need to use the back-updating method as the
earlier tasks already have diverse OOD classes.

####  5.2.3 Accuracy and Forgetting Rate Results and Analysis

Table 5: Average Accuracy after the Final Task

| Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T | Avg.
---|---|---|---|---|---|---|---
(a) | OWM | 41.69  $\pm$6.34 | 21.39  $\pm$3.18 | 16.98  $\pm$4.44 | 24.55  $\pm$2.48 | 17.52  $\pm$3.45 | 24.43
(b) | MUC | 73.95  $\pm$7.24 | 57.87  $\pm$1.11 | 43.98  $\pm$2.68 | 62.47  $\pm$0.34 | 55.79  $\pm$0.49 | 58.81
PASS | 86.21  $\pm$1.10 | 68.90  $\pm$0.94 | 66.77  $\pm$1.18 | 61.03  $\pm$0.38 | 58.34  $\pm$0.42 | 68.25
(c) | LwF | 67.59  $\pm$4.27 | 66.50  $\pm$1.93 | 67.54  $\pm$0.97 | 33.51  $\pm$4.36 | 36.85  $\pm$4.46 | 54.40
iCaRL | 87.55  $\pm$0.99 | 68.90  $\pm$0.47 | 69.15  $\pm$0.99 | 53.13  $\pm$1.04 | 51.88  $\pm$2.36 | 66.12
A-GEM | 56.33  $\pm$7.77 | 25.21  $\pm$4.00 | 21.99  $\pm$4.01 | 30.53  $\pm$3.99 | 21.90  $\pm$5.52 | 31.20
EEIL | 82.34  $\pm$3.13 | 68.08  $\pm$0.51 | 63.79  $\pm$0.66 | 53.34  $\pm$0.54 | 50.38  $\pm$0.97 | 63.59
GD | 89.16  $\pm$0.53 | 64.36  $\pm$0.57 | 60.10  $\pm$0.74 | 53.01  $\pm$0.97 | 42.48  $\pm$2.53 | 61.82
BiC | 67.44  $\pm$3.93 | 64.47  $\pm$1.30 | 67.69  $\pm$1.97 | 38.78  $\pm$1.26 | 40.98  $\pm$2.39 | 55.87
DER++ | 84.63  $\pm$2.91 | 69.73  $\pm$0.99 | 70.03  $\pm$1.46 | 55.84  $\pm$2.21 | 54.20  $\pm$3.28 | 66.89
HAL | 84.38  $\pm$2.70 | 67.17  $\pm$1.50 | 67.37  $\pm$1.45 | 52.80  $\pm$2.37 | 55.25  $\pm$3.60 | 65.39
(d) | HAT | 83.30  $\pm$1.54 | 62.34  $\pm$0.93 | 56.72  $\pm$0.44 | 57.91  $\pm$0.72 | 53.12  $\pm$0.94 | 62.68
Sup | 80.91  $\pm$2.99 | 62.49  $\pm$0.49 | 57.32  $\pm$1.11 | 58.43  $\pm$0.67 | 54.52  $\pm$0.45 | 62.74
| MORE | 89.16  $\pm$0.96 | 70.23  $\pm$2.27 | 70.53  $\pm$1.09 | 64.97  $\pm$1.28 | 63.06  $\pm$1.26 |  71.59

Average accuracy after the final task. ‘-XT’ means X number of tasks. Our
system MORE and all baselines used the pre-trained network. The baselines are
grouped into (a), (b), (c), and (d) for projection, regularization, replay,
and parameter-isolation methods, respectively. The last column show the
average accuracy of each method over all datasets and experiments. We
highlight the best results in each column in bold.

Average Accuracy. Table 5 shows that our method MORE consistently outperforms
the baselines. All the reported results are the averages of 5 runs. The last
column gives the average of each row. We compare with the replay-based methods
first. The best replay-based method on average over all the datasets is DER++.
Our method MORE achieves the accuracy of 71.59, much better than 66.89 of
DER++. This demonstrates that the existing replay-based methods utilizing the
replay samples to update all learned classes are inferior to our MORE method
using samples for OOD learning. The best baseline is the generative method
PASS. Its average accuracy over all the datasets is 68.25, which is still
poorer than our method’s performance of 71.59. The performance of the multi-
head method HAT [55] using task-id prediction is only 62.68, which is lower
than many other baselines. Its performance is particularly low in experiments
where the number of classes per task is small. For instance, its accuracy on
C100-20T is 56.72, much lower than our method of 70.53 trained based on OOD
detection.

Accuracy with Smaller Memory Sizes. For all the datasets, we run additional
experiments with half of the original memory size and show that our method is
even stronger with a smaller memory. The new memory sizes are 100, 1000, and
1000 for CIFAR-10, CIFAR-100, and Tiny-ImageNet, respectively. Table 6 shows
that MORE has experienced almost no performance drop with the reduced memory
size while the memory-based baselines suffer from major performance reduction.
The accuracy of the best memory-based baseline (DER++) has decreased the
accuracy from 66.89 to 62.16, while MORE only decreases from 71.59 to 71.44,
which shows that a small number of OOD samples is enough to enable the system
to produce a robust OOD detection model.

Table 6: Average Accuracy with Smaller Memory Sizes

| Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T | Avg.
---|---|---|---|---|---|---|---
(a) | OWM | 41.69  $\pm$6.34 | 21.39  $\pm$3.18 | 16.98  $\pm$4.44 | 24.55  $\pm$2.48 | 17.52  $\pm$3.45 | 24.43
(b) | MUC | 73.95  $\pm$7.24 | 57.87  $\pm$1.11 | 43.98  $\pm$2.68 | 62.47  $\pm$0.34 | 55.79  $\pm$0.49 | 58.81
PASS | 86.21  $\pm$1.10 | 68.90  $\pm$0.94 | 66.77  $\pm$1.18 | 61.03  $\pm$0.38 | 58.34  $\pm$0.42 | 68.25
(c) | LwF | 63.01  $\pm$4.19 | 56.76  $\pm$3.72 | 63.53  $\pm$2.86 | 26.79  $\pm$2.36 | 28.08  $\pm$4.88 | 47.63
iCaRL | 86.08  $\pm$1.19 | 66.96  $\pm$2.08 | 68.16  $\pm$0.71 | 47.27  $\pm$3.22 | 49.51  $\pm$1.87 | 63.60
A-GEM | 56.64  $\pm$4.29 | 23.18  $\pm$2.54 | 20.76  $\pm$2.88 | 31.44  $\pm$3.84 | 23.73  $\pm$6.27 | 31.15
EEIL | 77.44  $\pm$3.04 | 62.95  $\pm$0.68 | 57.86  $\pm$0.74 | 48.36  $\pm$1.38 | 44.59  $\pm$1.72 | 58.24
GD | 85.96  $\pm$1.64 | 57.17  $\pm$1.06 | 50.30  $\pm$0.58 | 46.09  $\pm$1.77 | 32.41  $\pm$2.75 | 54.39
BiC | 56.28  $\pm$3.31 | 58.42  $\pm$2.48 | 62.19  $\pm$1.20 | 33.29  $\pm$2.65 | 28.44  $\pm$2.41 | 47.72
DER++ | 80.09  $\pm$3.00 | 64.89  $\pm$2.48 | 65.84  $\pm$1.46 | 50.74  $\pm$2.41 | 49.24  $\pm$5.01 | 62.16
HAL | 79.16  $\pm$4.56 | 62.65  $\pm$0.83 | 63.96  $\pm$1.49 | 48.17  $\pm$2.94 | 47.11  $\pm$6.00 | 60.21
(d) | HAT | 83.30  $\pm$1.54 | 62.34  $\pm$0.93 | 56.72  $\pm$0.44 | 57.91  $\pm$0.72 | 53.12  $\pm$0.94 | 62.68
Sup | 80.91  $\pm$2.99 | 62.49  $\pm$0.49 | 57.32  $\pm$1.11 | 58.43  $\pm$0.67 | 54.52  $\pm$0.45 | 62.74
| MORE | 88.13  $\pm$1.16 | 71.69  $\pm$0.11 | 71.29  $\pm$0.55 | 64.17  $\pm$0.77 | 61.90  $\pm$0.90 |  71.44

Accuracy performances of the baselines and our method MORE with smaller memory
sizes. We reduce the size of the memory buffer by half. The new sizes are 100,
1000, 1000 for CIFAR10, CIFAR100, and Tiny-ImageNet. Numbers in bold are the
best results in each column.  Figure 3: Average forgetting rate (%). The lower
the rate, the better the method is.

Average Forgetting Rate. The average forgetting rate is defined as follows
[40]:
$\mathcal{F}^{t}=\sum_{k=1}^{t-1}(\mathcal{A}^{\text{init}}_{k}-\mathcal{A}^{t}_{k})/(t-1)$,
where $\mathcal{A}_{k}^{\text{init}}$ is the classification accuracy on
samples of task $k$ right after learning the task $k$. We do not consider the
task $t$ as it is the last task.

We compare the forgetting rate of our method MORE against the baselines using
C10-5T, C100-10T, and C100-20T. Figure 3 shows that the performance drop of
our method as more task are learned is relatively lower than many baselines.
MUC, A-GEM, HAT, and Sup achieve lower drop than our method. However, they are
not able to adapt to new tasks well as the accuracy values of the four methods
on C100-10T are 57.87, 25.21, 62.34, and 62.49, respectively, while our method
MORE achieves 70.23. The performance gaps remains consistent in the other
dataset. PASS experiences smaller drop in performance on C100-10T and C100-20T
than our method, but its accuracy of 68.90 and 66.77 are significantly lower
than 70.23 and 70.53 of our MORE.

####  5.2.4 Out-of-Distribution Detection Results

As we explained in the introduction section, since our method MORE is based on
OOD detection in building each task model, our method can naturally be used to
detect test samples that are out-of-distribution for all the classes or tasks
learned thus far. We are not aware of any existing continual learning system
that has done such an evaluation. We evaluate the performance of the baselines
and our system in this out-of-distribution scenario, which is also called the
open set setting.

This OOD detection ability is highly desirable for a continual learning system
because in a real-life environment in the open world, the system can be
exposed to not only seen classes, but also unseen classes. When the test
sample is from one of seen classes, the system should be able to predict its
class. If the sample does not belong to any of the training classes seen so
far (i.e., the sample is out-of-distribution), the system should detect it.

We formulate the performance of OOD detection of a continual learning system
as the following. A continual learning system accepts and classifies a test
sample after training task $k$ if the test sample is from one of the classes
in tasks $1,\cdots,k$. If it is from one of the classes of the future tasks
$k+1,\cdots,t$, it should be rejected as OOD (where $t$ is the last task in
each evaluation).

Table 7: AI-AUC Results

| Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T | Avg.
---|---|---|---|---|---|---|---
(a) | OWM | 70.02  $\pm$3.59 | 63.17  $\pm$1.06 | 59.42  $\pm$1.26 | 67.24  $\pm$0.92 | 62.17  $\pm$0.35 | 64.41
(b) | MUC | 85.47  $\pm$3.97 | 79.28  $\pm$1.15 | 74.82  $\pm$1.91 | 83.91  $\pm$0.54 | 81.42  $\pm$0.47 | 80.98
PASS | 84.57  $\pm$1.54 | 77.74  $\pm$1.40 | 77.42  $\pm$1.44 | 77.07  $\pm$2.14 | 74.79  $\pm$2.36 | 78.32
(c) | LwF | 72.18  $\pm$4.15 | 74.95  $\pm$0.39 | 75.40  $\pm$0.64 | 66.44  $\pm$1.14 | 65.52  $\pm$0.64 | 70.90
iCaRL | 82.12  $\pm$5.38 | 77.42  $\pm$0.45 | 76.91  $\pm$1.30 | 71.86  $\pm$1.57 | 74.24  $\pm$1.66 | 76.06
A-GEM | 74.92  $\pm$5.62 | 64.19  $\pm$0.86 | 60.23  $\pm$0.95 | 67.88  $\pm$1.28 | 63.08  $\pm$1.12 | 66.06
EEIL | 87.19  $\pm$2.31 | 78.89  $\pm$1.32 | 77.69  $\pm$1.40 | 74.82  $\pm$0.79 | 73.45  $\pm$1.33 | 78.39
GD | 89.71  $\pm$1.85 | 77.31  $\pm$1.03 | 75.19  $\pm$0.87 | 75.36  $\pm$0.78 | 70.90  $\pm$1.75 | 77.69
BiC | 71.29  $\pm$3.57 | 74.49  $\pm$0.72 | 75.71  $\pm$0.60 | 67.45  $\pm$0.89 | 66.63  $\pm$0.77 | 71.11
DER++ | 84.61  $\pm$2.64 | 78.42  $\pm$0.64 | 78.37  $\pm$0.42 | 74.80  $\pm$1.72 | 74.86  $\pm$1.93 | 78.09
HAL | 84.09  $\pm$3.30 | 77.37  $\pm$0.55 | 77.66  $\pm$0.31 | 74.52  $\pm$1.93 | 75.47  $\pm$2.35 | 77.82
(d) | HAT | 87.83  $\pm$2.44 | 79.57  $\pm$0.29 | 77.20  $\pm$0.74 | 79.78  $\pm$1.59 | 78.25  $\pm$1.68 | 80.53
Sup | 87.06  $\pm$3.68 | 80.54  $\pm$0.12 | 77.81  $\pm$0.66 | 80.01  $\pm$0.71 | 78.96  $\pm$0.64 | 80.87
| MORE | 88.06  $\pm$1.84 | 81.67  $\pm$1.27 | 80.97  $\pm$0.80 | 80.72  $\pm$3.38 | 79.73  $\pm$2.97 |  82.23

Numbers in bold are the best results in each column.

We use maximum softmax probability (MSP) [20] as the OOD score of a test
sample for the baselines and use maximum output with coefficient in Eq. 30 for
our method MORE. We employ Area Under the ROC Curve (AUC) to measure the
performance of OOD detection as AUC is the standard metric used in OOD
detection papers [65].We report average incremental AUC (AI-AUC) which is the
average AUC result at all tasks except the last one as there is no more OOD
data after the last task.

Table 7 shows that our method MORE outperforms all baselines consistently
except MUC and GD. For MUC, it performs better than MORE on Tiny-ImageNet, but
on average, it is poorer (80.98) than MORE (82.23). For GD, it outperforms
MORE on C10-5T, but its overall performance is much lower as it achieves the
average of only 77.69 over the 5 experiments.

####  5.2.5 Ablation Study

We conduct an ablation study to measure the performance gain by each proposed
technique, back-updating in previous models in Section 5.1.2 and the distance-
based coefficient in Section 5.1.3, using three experiments. The back-updating
by Eq. 26 is to improve the earlier task models as they are trained with less
diverse OOD data than later models. The modified output with coefficient in
Eq. 27 is to improve the classification accuracy by combining the softmax
probability of the task networks and the inverse Mahalanobis distances.

Table 8 compares accuracy obtained after applying each method. Both distance
based coefficient and back-updating show large improvements from the original
method without any of the two techniques. Although the performance is already
competitive with either technique, the performance improves further after
applying them together.

Table 8: Ablation Study

| C10-5T | C100-10T | C100-20T
---|---|---|---
Original | 91.01  $\pm$2.48 | 76.93  $\pm$1.58 | 75.76  $\pm$2.35
Coefficient (C) | 93.86  $\pm$1.12 | 80.31  $\pm$1.02 | 80.77  $\pm$1.36
Back (B) | 93.36  $\pm$0.79 | 80.35  $\pm$1.08 | 80.32  $\pm$0.82
C + B | 94.23  $\pm$0.82 | 81.24  $\pm$1.24 | 81.59  $\pm$0.98

Performance gains with the proposed techniques. The row Original indicates the
method without the coefficient and back-updating and the row Back means the
back-updating method.

##  6 Conclusion

This paper studied open world continual learning, which is necessary for
learning in the open world. An open world learning algorithm first needs to
detect novel or out-of-distribution (OOD) items and then learn them
continually or incrementally. This type of learning is called class
incremental learning (CIL), which is a challenging setting of continual
learning. Another popular setting is task incremental learning (TIL).
Traditionally, novelty/OOD detection and CIL are regarded as two completely
different problems. This paper theoretically showed that the two problems can
be unified. In particular, we first decomposed the CIL prediction problem into
within-task prediction (WP) and task-id prediction (TP). WP is basically TIL.
The paper further theoretically demonstrated that TP is correlated with out-
of-distribution (OOD) detection. It then proved that a good performance of the
two is both necessary and sufficient for good CIL performances. Since OOD
detection is basically novelty detection in open-world learning, our theory
connects and unifies open-world novelty detection and continual learning (CIL
in particular). Their combination gives us the paradigm of open-world
continual learning. The theoretical result also provides a principled guidance
for designing better continual learning algorithms. Based on the result,
several new CIL methods have been designed. They outperform strong baselines
in CIL by a large margin and also perform novelty (or OOD) detection well in
the open world continual learning setting.

## Author Contributions

Gyuhak Kim conceived the idea, developed the algorithms, conducted
experiments, and led the writing of the paper. Changnan Xiao developed the
mathematical framework and derived proofs. Tatsuya Konishi and Zixuan Ke
contributed in discussions and helped edit the paper. Bing Liu supervised the
project and helped write the paper.

## Acknowledgements

The work of Gyuhak Kim, Zixuan Ke and Bing Liu was supported in part by a
research contract from KDDI, a research contract from DARPA (HR001120C0023),
and three NSF grants (IIS-1910424, IIS-1838770, and CNS-2225427).

##  Appendix A Proof of Theorems and Corollaries

###  A.1 Proof of Theorem 1

###### Proof.

Since

$\displaystyle H_{CIL}(x)$
$\displaystyle=H(y,\\{\mathbf{P}(x\in\mathbf{X}_{k,j}|D)\\}_{k,j})$
$\displaystyle=-\sum_{k,j}y_{k,j}\log\mathbf{P}(x\in\mathbf{X}_{k,j}|D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D),$
$\displaystyle H_{WP}(x)$
$\displaystyle=H(\tilde{y},\\{\mathbf{P}(x\in\mathbf{X}_{k_{0},j}|x\in\mathbf{X}_{k_{0}},D)\\}_{j})$
$\displaystyle=-\sum_{j}y_{k_{0},j}\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j}|x\in\mathbf{X}_{k_{0}},D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|x\in\mathbf{X}_{k_{0}},D),$

and

$\displaystyle H_{TP}(x)$
$\displaystyle=H(\bar{y},\\{\mathbf{P}(x\in\mathbf{X}_{k}|D)\\}_{k})$
$\displaystyle=-\sum_{k}\bar{y}_{k}\log\mathbf{P}(x\in\mathbf{X}_{k}|D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D),$

we have

$\displaystyle H_{CIL}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|x\in\mathbf{X}_{k_{0}},D)-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=H_{WP}(x)+H_{TP}(x)$ $\displaystyle\leq\epsilon+\delta.$

∎

###  A.2 Proof of Corollary 1.

###### Proof.

By proof of Theorem 1, we have

$H_{CIL}(x)=H_{WP}(x)+H_{TP}(x).$

Taking expectations on both sides, we have i)

$\displaystyle\mathbb{E}_{x\sim U(\mathbf{X})}[H_{CIL}(x)]$
$\displaystyle=\mathbb{E}_{x\sim U(\mathbf{X})}[H_{WP}(x)]+\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{TP}(x)]$ $\displaystyle\leq\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{WP}(x)]+\delta.$

and ii)

$\displaystyle\mathbb{E}_{x\sim U(\mathbf{X})}[H_{CIL}(x)]$
$\displaystyle=\mathbb{E}_{x\sim U(\mathbf{X})}[H_{WP}(x)]+\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{TP}(x)]$ $\displaystyle\leq\epsilon+\mathbb{E}_{x\sim
U(\mathbf{X})}[H_{TP}(x)].$

∎

###  A.3 Proof of Theorem 2.

###### Proof.

i) Assume $x\in\mathbf{X}_{k_{0}}$. For $k=k_{0}$, we have

$\displaystyle H_{OOD,k_{0}}(x)$
$\displaystyle=-\log\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=H_{TP}(x)\leq\delta.$

For $k\neq k_{0}$, we have

$\displaystyle H_{OOD,k}(x)$
$\displaystyle=-\log\mathbf{P}^{\prime}_{k}(x\notin\mathbf{X}_{k}|D)$
$\displaystyle=-\log(1-\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D))$
$\displaystyle=-\log(1-\mathbf{P}(x\in\mathbf{X}_{k}|D))$
$\displaystyle=-\log\mathbf{P}(x\in\cup_{k^{\prime}\neq
k}\mathbf{X}_{k^{\prime}}|D)$
$\displaystyle\leq-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=H_{TP}(x)\leq\delta.$

ii) Assume $x\in\mathbf{X}_{k_{0}}$. For $k=k_{0}$, by
$H_{OOD,{k_{0}}}(x)\leq\delta_{k_{0}}$, we have

$-\log\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)\leq\delta_{k_{0}},$

which means

$\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)\geq
e^{-\delta_{k_{0}}}.$

For $k\neq k_{0}$, by $H_{OOD,{k}}(x)\leq\delta_{k}$, we have

$-\log\mathbf{P}^{\prime}_{k}(x\notin\mathbf{X}_{k}|D)\leq\delta_{k},$

which means

$\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)\leq 1-e^{-\delta_{k}}.$

Therefore, we have

$\displaystyle\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=\frac{\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)}{\sum_{k^{\prime}}\mathbf{P}^{\prime}_{k^{\prime}}(x\in\mathbf{X}_{k^{\prime}}|D)}$
$\displaystyle\geq\frac{e^{-\delta_{k_{0}}}}{1+\sum_{k\neq
k_{0}}1-e^{-\delta_{k}}}$
$\displaystyle=\frac{e^{-\delta_{k_{0}}}}{e^{-\delta_{k_{0}}}+\sum_{k}1-e^{-\delta_{k}}}$
$\displaystyle=\frac{1}{1+e^{\delta_{k_{0}}}\sum_{k}1-e^{-\delta_{k}}}.$

Hence,

$\displaystyle H_{TP}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle\leq-\log\frac{1}{1+e^{\delta_{k_{0}}}\sum_{k}1-e^{-\delta_{k}}}$
$\displaystyle=\log[1+e^{\delta_{k_{0}}}\sum_{k}1-e^{-\delta_{k}}]$
$\displaystyle\leq e^{\delta_{k_{0}}}(\sum_{k}1-e^{-\delta_{k}})$
$\displaystyle=(\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}e^{\delta_{k}})(\sum_{k}1-e^{-\delta_{k}}).$

∎

###  A.4 Proof of Theorem 3.

###### Proof.

Using Theorem 1 and 2,

$\displaystyle H_{CIL}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|x\in\mathbf{X}_{k_{0}},D)-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=H_{WP}(x)+H_{TP}(x)$ $\displaystyle\leq\epsilon+H_{TP}(x)$
$\displaystyle\leq\epsilon+(\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}e^{\delta_{k}})(\sum_{k}1-e^{-\delta_{k}})$

∎

###  A.5 Proof of Theorem 4.

###### Proof.

i) Assume $x\in\mathbf{X}_{k_{0},j_{0}}\subset\mathbf{X}_{k_{0}}$. Define
$\mathbf{P}(x\in\mathbf{X}_{k,j}|x\in\mathbf{X}_{k},D)=\mathbf{P}(x\in\mathbf{X}_{k,j}|D)$.
According to proof of Theorem 1,

$\displaystyle H_{WP}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|x\in\mathbf{X}_{k_{0}},D),$
$\displaystyle H_{CIL}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D).$

Hence, we have

$\displaystyle H_{WP}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|x\in\mathbf{X}_{k_{0}},D)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D)$
$\displaystyle=H_{CIL}(x)\leq\eta.$

ii) Assume $x\in\mathbf{X}_{k_{0},j_{0}}\subset\mathbf{X}_{k_{0}}$. Define
$\mathbf{P}(x\in\mathbf{X}_{k}|D)=\sum_{j}\mathbf{P}(x\in\mathbf{X}_{k,j}|D)$.
According to proof of Theorem 1,

$\displaystyle H_{TP}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D),$ $\displaystyle
H_{CIL}(x)$ $\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D).$

Hence, we have

$\displaystyle H_{TP}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=-\log\sum_{j}\mathbf{P}(x\in\mathbf{X}_{k_{0},j}|D)$
$\displaystyle\leq-\log\mathbf{P}(x\in\mathbf{X}_{k_{0},j_{0}}|D)$
$\displaystyle=H_{CIL}(x)\leq\eta.$

iii) Assume $x\in\mathbf{X}_{k_{0},j_{0}}\subset\mathbf{X}_{k_{0}}$. Define
$\mathbf{P}^{\prime}_{i}(x\in\mathbf{X}_{k}|D)=\mathbf{P}(x\in\mathbf{X}_{k}|D)=\sum_{j}\mathbf{P}(x\in\mathbf{X}_{k,j}|D)$.
According to proof of Theorem 4 ii), we have

$H_{TP}(x)\leq\eta.$

According to proof of Theorem 2 i), we have

$H_{OOD,i}(x)\leq H_{TP}(x).$

Therefore,

$H_{OOD,i}(x)\leq H_{TP}(x)\leq\eta.$

∎

##  Appendix B Additional Results and Explanation Regarding Table 1 in the
Main Paper

In Section 4.2.3, we showed that a better OOD detection improves CIL
performance. For the post-processing method ODIN, we only reported the results
on C100-10T. Table 9 shows the results on the other datasets.

Table 9: Performance Comparison between the Original Output and ODIN

|  | C10-5T | C100-20T | T-5T | T-10T
---|---|---|---|---|---
Method | CIL | AUC | CIL | AUC | CIL | AUC | CIL | AUC | CIL
OWM | Original | 81.33 | 51.79 | 71.90 | 24.15 | 58.49 | 10.00 | 59.48 | 8.57
ODIN | 71.72 | 40.65 | 68.52 | 23.05 | 58.46 | 10.77 | 59.38 | 9.52
MUC | Original | 79.49 | 52.85 | 66.20 | 14.19 | 68.42 | 33.57 | 62.63 | 17.39
ODIN | 79.54 | 53.22 | 65.72 | 14.11 | 68.32 | 33.45 | 62.17 | 17.27
PASS | Original | 66.51 | 47.34 | 70.26 | 24.99 | 65.18 | 28.40 | 63.27 | 19.07
ODIN | 63.08 | 35.20 | 69.81 | 21.83 | 65.93 | 29.03 | 62.73 | 17.78
LwF | Original | 89.39 | 54.67 | 89.84 | 44.33 | 78.20 | 32.17 | 79.43 | 24.28
ODIN | 88.94 | 63.04 | 88.68 | 47.56 | 76.83 | 36.20 | 77.02 | 28.29
A-GEM | Original | 85.93 | 20.03 | 74.48 | 4.14 | 72.33 | 13.52 | 76.42 | 7.66
ODIN | 86.43 | 34.03 | 75.12 | 6.99 | 72.46 | 14.69 | 76.75 | 8.50
EEIL | Original | 89.72 | 57.09 | 85.96 | 33.46 | 64.82 | 14.67 | 64.87 | 9.79
ODIN | 89.20 | 59.47 | 85.46 | 35.16 | 57.01 | 11.92 | 55.42 | 6.88
GD | Original | 91.23 | 58.69 | 86.76 | 38.83 | 68.63 | 16.36 | 69.61 | 11.73
ODIN | 90.39 | 60.53 | 86.64 | 42.33 | 60.75 | 13.43 | 63.92 | 11.83
BiC | Original | 90.89 | 61.41 | 89.46 | 48.92 | 80.17 | 41.75 | 80.37 | 33.77
ODIN | 91.86 | 64.29 | 87.89 | 47.40 | 74.54 | 37.40 | 76.27 | 29.06
DER++ | Original | 90.16 | 66.04 | 85.44 | 46.59 | 71.80 | 35.80 | 72.41 | 30.49
ODIN | 87.08 | 63.07 | 87.72 | 49.26 | 73.92 | 37.87 | 72.91 | 32.52
HAL | Original | 86.16 | 32.82 | 65.59 | 13.51 | 53.00 | 3.42 | 57.87 | 3.36
ODIN | 76.27 | 44.75 | 64.46 | 17.40 | 53.26 | 4.80 | 58.13 | 4.74
HAT | Original | 82.47 | 62.67 | 75.35 | 25.64 | 72.28 | 38.46 | 71.82 | 29.78
ODIN | 82.45 | 62.60 | 75.36 | 25.84 | 72.31 | 38.61 | 71.83 | 30.01
HyperNet | Original | 78.54 | 53.40 | 72.04 | 18.67 | 54.58 | 7.91 | 55.37 | 5.32
ODIN | 79.39 | 56.72 | 73.89 | 23.8 | 54.60 | 8.64 | 55.53 | 6.91
Sup | Original | 79.16 | 62.37 | 81.14 | 34.70 | 74.13 | 41.82 | 74.59 | 36.46
ODIN | 82.38 | 62.63 | 81.48 | 36.35 | 73.96 | 41.10 | 74.61 | 36.46

Performance comparison between the original output and output post-processed
with OOD detection technique ODIN. Note that ODIN is not applicable to iCaRL
and Mnemonics as they are not based on softmax but some distance functions.
The result for C100-10T are reported in the main paper.

A continual learning method with a better AUC shows a better CIL performance
than other methods with lower AUC. For instance, original HAT achieves AUC of
82.47 while HyperNet achieves 78.54 on C10-5T. The CIL for HAT is 62.67 while
it is 53.40 for HyperNet. However, there are some exceptions that this
comparison does not hold. An example is LwF. Its AUC and CIL are 89.39 and
54.67 on C10-5T. Although its AUC is better than HAT, the CIL is lower. This
is due to the fact that CIL improves with WP and TP according to Theorem 1.
The contraposition of Theorem 4 also says if the cross-entropy of TIL is
large, that of CIL is also large. Indeed, the average within-task prediction
(WP) accuracy for LwF on C10-5T is 95.2 while the same for HAT is 96.7.
Improving WP is also important in achieving good CIL performances.

For PASS, we had to tune $\tau_{k}$ using a validation set. This is because
the softmax in Eq. 22 improves AUC by making the IND (in-distribution) and OOD
scores more separable within a task, but deteriorates the final scores across
tasks. To be specific, the test instances are predicted as one of the classes
in the first task after softmax because the relative values between classes in
task 1 is larger than the other tasks in PASS. Therefore, larger $\tau_{1}$
and smaller $\tau_{k}$, for $k>1$, are chosen to compensate the relative
values.

##  Appendix C Definitions of TP

As noted in the main paper, the class prediction in Eq. 2 varies by definition
of WP and TP. The precise definition of WP and TP depends on implementation.
Due to this subjectivity, we follow the prediction method in the existing
approaches in continual learning, which is the $\operatorname*{arg\,max}$ over
the output. In this section, we show that the $\operatorname*{arg\,max}$ over
output is a special case of Eq. 2. We also provide CIL results using different
definitions of TP.

We first establish another theorem. This is an extension of Theorem 2 and
connects the standard prediction method to our analysis.

######  Theorem 5 (Extension of Theorem 2).

i) If $H_{TP}(x)\leq\delta$, let
$\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)=\mathbf{P}(x\in\mathbf{X}_{k}|D)^{1/\tau_{k}}$,
$\forall\tau_{k}>0$, then
$H_{OOD,k}(x)\leq\max(\delta/\tau_{k},-\log(1-(1-e^{-\delta})^{1/\tau_{k}}),\forall\,k=1,\dots,T$.

ii) If $H_{OOD,k}(x)\leq\delta_{k},k=1,\dots,T$, let
$\mathbf{P}(x\in\mathbf{X}_{k}|D)=\frac{\mathbf{P}_{k}^{\prime}(x\in\mathbf{X}_{k}|D)^{1/\tau_{k}}}{\sum_{j}\mathbf{P}_{j}^{\prime}(x\in\mathbf{X}_{j}|D)^{1/\tau_{j}}}$,
$\forall\tau_{k}>0$, then
$H_{TP}(x)\leq\sum_{k}\frac{\mathbf{1}_{x\in\mathbf{X}_{k}}\delta_{k}}{\tau_{k}}+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}(1-(1-e^{-\delta_{k}})^{1/\tau_{k}})}$,
where $\mathbf{1}_{x\in\mathbf{X}_{k}}$ is an indicator function.

In Theorem 5 (proof appears later), we can observe that $\delta/\tau_{k}$
decreases with the increase of $\tau_{k}$, while
$-\log(1-(1-e^{-\delta})^{1/\tau_{k}})$ increases. Hence, when TP is given,
let $\delta=H_{TP}(x)$, we can find the optimal $\tau_{i}$ to define OOD by
solving $\delta/\tau_{k}=-\log(1-(1-e^{-\delta})^{1/\tau_{k}})$. Similarly,
given OOD, let $\delta_{k}=H_{OOD,k}(x)$, we can find the optimal
$\tau_{1},\dots,\tau_{T}$ to define TP by finding the global minima of
$\sum_{k}\frac{\mathbf{1}_{x\in\mathbf{X}_{k}}\delta_{k}}{\tau_{k}}+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}(1-(1-e^{-\delta_{k}})^{1/\tau_{k}})}$.
The optimal $\tau_{k}$ can be found using a memory buffer to save a small
number of previous data like that in a replay-based continual learning method.

In Theorem 5 (ii), let
$\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)=\sigma(\max f(x)_{k})$, where
$\sigma$ is the sigmoid and $f(x)_{k}$ is the output of task $k$ and choose
$\tau_{k}\approx 0$ for each $k$. Then $\mathbf{P}(x\in\mathbf{X}_{k}|D)$
becomes approximately 1 for the task $k$ where the maximum logit value appears
and 0 for the rest tasks. Therefore, Eq. 2 in the paper

$\displaystyle\mathbf{P}(x\in\mathbf{X}_{k,j}|D)=\mathbf{P}(x\in\mathbf{X}_{k,j}|x\in\mathbf{X}_{k},D)\mathbf{P}(x\in\mathbf{X}_{k}|D)$

is zero for all classes in tasks $k^{\prime}\neq k$. Since only the
probabilities of classes in task $k$ are non-zero, taking
$\operatorname*{arg\,max}$ over all class probabilities gives the same class
as $\operatorname*{arg\,max}$ over output logits.

We have also tried another definition of WP and TP. The considered WP is

$\displaystyle\mathbf{P}(x\in\mathbf{X}_{k,j}|x\in\mathbf{X}_{k},D)=\frac{e^{f(x)_{kj}/\nu_{k}}}{\sum_{j}e^{f(x)_{kj}/\nu_{k}}},$
(31)

where $\nu_{k}$ is a temperature scaling parameter for task $k$, and the TP is

$\displaystyle\mathbf{P}(x\in\mathbf{X}_{k}|D)=\frac{\mathbf{P}_{k}^{\prime}(x\in\mathbf{X}_{k}|D)}{\sum_{k}\mathbf{P}_{k}^{\prime}(x\in\mathbf{X}_{k}|D)},$
(32)

where
$\mathbf{P}_{k}^{\prime}(x\in\mathbf{X}_{k}|D)=\max_{j}e^{f(x)_{kj}/\tau_{k}}/\sum_{j}e^{f(x)_{kj}/\tau_{k}}$
and $\tau_{k}$ is a temperature scaling parameter. This is the maximum softmax
of task $k$. We choose $\nu_{k}=0.1$ and $\tau_{k}=5$ for all $k$. A good
$\tau$ and $\nu$ can be found using grid search on a validation set. However,
one can also find the optimal values by optimization using some past data
saved for memory buffer. The CIL results for the new prediction method is in
Table 10.

Table 10: Average Accuracy with a Different Prediction Method

Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T
---|---|---|---|---|---
OWM | 40.6  $\pm$0.47 | 28.6  $\pm$0.82 | 22.9  $\pm$0.32 | 10.4  $\pm$0.54 | 9.2  $\pm$0.35
MUC | 53.2  $\pm$1.32 | 30.6  $\pm$1.21 | 14.0  $\pm$0.12 | 33.1  $\pm$0.18 | 17.2  $\pm$0.13
PASS† | 33.6  $\pm$0.71 | 18.5  $\pm$1.85 | 20.8  $\pm$0.85 | 21.4  $\pm$0.44 | 13.0  $\pm$0.55
LwF | 63.0  $\pm$0.34 | 51.9  $\pm$0.88 | 47.5  $\pm$0.62 | 35.9  $\pm$0.32 | 27.8  $\pm$0.29
iCaRL∗ | 65.3  $\pm$0.83 | 52.9  $\pm$0.39 | 48.2  $\pm$0.70 | 34.8  $\pm$0.34 | 27.3  $\pm$0.17
A-GEM | 34.0  $\pm$1.86 | 14.5  $\pm$0.55 | 7.3  $\pm$1.78 | 15.4  $\pm$0.24 | 9.0  $\pm$0.30
EEIL | 59.5  $\pm$0.41 | 41.8  $\pm$0.78 | 37.9  $\pm$6.11 | 15.1  $\pm$0.00 | 7.5  $\pm$0.19
GD | 68.0  $\pm$0.75 | 47.2  $\pm$0.33 | 41.8  $\pm$0.25 | 15.7  $\pm$2.08 | 12.2  $\pm$0.14
Mnemonics†∗ | 65.6  $\pm$1.55 | 50.7  $\pm$0.72 | 47.9  $\pm$0.71 | 36.3  $\pm$0.30 | 27.7  $\pm$0.78
BiC | 65.5  $\pm$0.81 | 50.8  $\pm$0.69 | 47.2  $\pm$0.71 | 37.0  $\pm$0.58 | 29.1  $\pm$0.34
DER++ | 63.1  $\pm$1.12 | 54.6  $\pm$1.21 | 48.9  $\pm$1.18 | 37.4  $\pm$0.72 | 32.1  $\pm$0.44
HAL | 43.0  $\pm$3.10 | 20.0  $\pm$1.15 | 17.0  $\pm$0.83 | 4.6  $\pm$0.58 | 4.8  $\pm$0.50
HAT | 62.6  $\pm$1.31 | 41.5  $\pm$0.80 | 25.9  $\pm$0.56 | 38.9  $\pm$1.62 | 30.1  $\pm$0.52
HyperNet | 56.7  $\pm$1.23 | 32.4  $\pm$1.07 | 24.5  $\pm$1.12 | 8.9  $\pm$0.58 | 7.0  $\pm$0.52
Sup | 62.6  $\pm$1.11 | 46.8  $\pm$0.34 | 36.0  $\pm$0.32 | 41.5  $\pm$1.17 | 35.7  $\pm$0.40
HAT+CSI | 85.2  $\pm$0.92 | 62.9  $\pm$1.07 | 53.6  $\pm$0.84 | 47.0  $\pm$0.38 | 46.2  $\pm$0.30
Sup+CSI | 87.4  $\pm$0.40 | 66.6  $\pm$0.23 | 60.5  $\pm$0.89 | 47.7  $\pm$0.30 | 46.3  $\pm$0.30
HAT+CSI+c | 85.2  $\pm$0.94 | 63.6  $\pm$0.69 | 55.4  $\pm$0.79 | 51.4  $\pm$0.38 | 46.5  $\pm$0.26
Sup+CSI+c | 86.2  $\pm$0.79 | 67.0  $\pm$0.14 | 60.4  $\pm$1.04 | 48.2  $\pm$0.35 | 46.1  $\pm$0.32

Average classification accuracy. The results are based on class prediction
method defined with WP and TP in Eq. 31 and Eq. 32, respectively. The results
can improve by finding optimal temperature scaling parameters.

###### Proof of Theorem 5..

i) Assume $x\in\mathbf{X}_{k_{0}}$.

For $k=k_{0}$, we have

$\displaystyle H_{OOD,k_{0}}(x)$
$\displaystyle=-\log\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=-\frac{1}{\tau_{k_{0}}}\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=\frac{1}{\tau_{k_{0}}}H_{TP}(x)\leq\frac{\delta}{\tau_{k_{0}}}.$

For $k\neq k_{0}$, we have

$\displaystyle H_{OOD,k}(x)$
$\displaystyle=-\log\mathbf{P}^{\prime}_{k}(x\notin\mathbf{X}_{k}|D)$
$\displaystyle=-\log(1-\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D))$
$\displaystyle=-\log(1-\mathbf{P}(x\in\mathbf{X}_{k}|D)^{1/\tau_{k}})$
$\displaystyle=-\log(1-(1-\mathbf{P}(x\in\cup_{k^{\prime}\neq
k}\mathbf{X}_{k^{\prime}}|D))^{1/\tau_{k}})$
$\displaystyle\leq-\log(1-(1-\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D))^{1/\tau_{k}})$
$\displaystyle=-\log(1-(1-e^{-H_{TP}(x)})^{1/\tau_{k}})$
$\displaystyle\leq-\log(1-(1-e^{-\delta})^{1/\tau_{k}}).$

ii) Assume $x\in\mathbf{X}_{k_{0}}$.

For $k=k_{0}$, by $H_{OOD,{k_{0}}}(x)\leq\delta_{k_{0}}$, we have

$-\log\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)\leq\delta_{k_{0}},$

which means

$\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)\geq
e^{-\delta_{k_{0}}}.$

For $k\neq k_{0}$, by $H_{OOD,{k}}(x)\leq\delta_{k}$, we have

$-\log\mathbf{P}^{\prime}_{k}(x\notin\mathbf{X}_{k}|D)\leq\delta_{k},$

which means

$\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)\leq 1-e^{-\delta_{k}}.$

Therefore, we have

$\displaystyle\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle=\frac{\mathbf{P}^{\prime}_{k_{0}}(x\in\mathbf{X}_{k_{0}}|D)^{1/\tau_{k_{0}}}}{\sum_{k}\mathbf{P}^{\prime}_{k}(x\in\mathbf{X}_{k}|D)^{1/\tau_{k}}}$
$\displaystyle\geq\frac{e^{-\delta_{k_{0}}/\tau_{k_{0}}}}{1+\sum_{k\neq
k_{0}}(1-e^{-\delta_{k}})^{1/\tau_{k}}}$
$\displaystyle=\frac{e^{-\delta_{k_{0}}/\tau_{k_{0}}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}+\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}$
$\displaystyle=\frac{e^{-\delta_{k_{0}}/\tau_{k_{0}}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}}\cdot\frac{1}{1+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}}}.$

Hence,

$\displaystyle H_{TP}(x)$
$\displaystyle=-\log\mathbf{P}(x\in\mathbf{X}_{k_{0}}|D)$
$\displaystyle\leq-\log\frac{e^{-\delta_{k_{0}}/\tau_{k_{0}}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}}\cdot\frac{1}{1+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}}}$
$\displaystyle=\frac{\delta_{k_{0}}}{\tau_{k_{0}}}+\log[1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}]+\log\left[1+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}}\right]$
$\displaystyle\leq\frac{\delta_{k_{0}}}{\tau_{k_{0}}}+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{1-(1-e^{-\delta_{k_{0}}})^{1/\tau_{k_{0}}}}$
$\displaystyle=\sum_{k}\frac{\mathbf{1}_{x\in\mathbf{X}_{k}}\delta_{k}}{\tau_{k}}+\frac{\sum_{k}(1-e^{-\delta_{k}})^{1/\tau_{k}}}{\sum_{k}\mathbf{1}_{x\in\mathbf{X}_{k}}(1-(1-e^{-\delta_{k}})^{1/\tau_{k}})}.$

∎

##  Appendix D Output Calibration

In this section, we discuss the output calibration technique used in Section
4.2.4 to improve the final prediction accuracy. Even if an OOD detection of
each task was perfect (i.e. the model accepts and rejects IND and OOD samples
perfectly), the system could make incorrect class prediction if the magnitudes
of outputs across different tasks are different. To ensure that the output
values are comparable, we calibrate the outputs by scaling $\alpha_{k}$ and
shifting $\beta_{k}$ for each task. The optimal parameters
$(\alpha_{k},\beta_{k})\in R\times R$ can be found by solving optimization
problem using samples in memory buffer. More precisely, denote the memory
buffer $\mathcal{M}$ and calibration parameters $(\alpha,\beta)\in R^{T}\times
R^{T}$, where $T$ is the number of learned tasks. After training $T$th task,
we find optimal calibration parameters by minimizing the cross-entropy loss,

$\displaystyle\mathcal{L}=-\frac{1}{|\mathcal{M}|}\sum_{(x,y)\in\mathcal{M}}\log
p(y|x)$ (33)

where $p(c|x)$ is computed using the softmax,

$\displaystyle\text{softmax}\bigoplus[\alpha_{k}f(x)_{k}+\beta_{k}]$ (34)

where $\bigoplus$ indicates the concatenation and $f(x)_{k}$ is the output of
task $k$ as Eq. 21. Given the optimal parameters $(\alpha^{*},\beta^{*})$, we
make final prediction as

$\displaystyle\hat{y}=\operatorname*{arg\,max}\bigoplus[\alpha_{k}^{*}f(x)_{k}+\beta_{k}^{*}]$
(35)

If we use $OOD_{k}=\sigma(\alpha_{k}^{*}f(x)_{k}+\beta_{k}^{*})$, where
$\sigma$ is the sigmoid, and
$TP_{k}=OOD_{k}/\sum_{k^{\prime}}OOD_{k^{\prime}}$, the theoretical results in
Section 3 hold.

##  Appendix E TIL (WP) Results

The TIL (WP) results of all the systems are reported in Table 11. HAT and Sup
show strong performances compared to the other baselines as they leverage
task-specific parameters. However, as shown in Theorem 1, the CIL depends on
TP (or OOD). Without an OOD detection mechanism in HAT or Sup, they perform
poorly in CIL as shown in the main paper. The contrastive learning in CSI also
improves the IND prediction (i.e., WP), and this along with OOD detection
results in the strong CIL performance.

Table 11: The TIL Results of All the Systems.

Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T | Avg.
---|---|---|---|---|---|---
OWM | 85.0  $\pm$0.07 | 59.6  $\pm$0.83 | 65.4  $\pm$0.48 | 22.4  $\pm$0.87 | 28.1  $\pm$0.55 | 52.1
MUC | 95.1  $\pm$0.10 | 77.3  $\pm$0.83 | 73.4  $\pm$9.16 | 55.9  $\pm$0.26 | 47.2  $\pm$0.22 | 69.8
PASS† | 83.8  $\pm$0.68 | 72.1  $\pm$0.70 | 76.8  $\pm$0.32 | 49.9  $\pm$0.56 | 46.5  $\pm$0.39 | 65.8
LwF | 95.2  $\pm$0.30 | 86.2  $\pm$1.00 | 89.0  $\pm$0.45 | 56.4  $\pm$0.48 | 55.3  $\pm$0.35 | 76.4
iCaRL | 94.9  $\pm$0.34 | 84.2  $\pm$1.04 | 85.7  $\pm$0.68 | 54.5  $\pm$0.29 | 52.7  $\pm$0.37 | 74.4
A-GEM | 82.5  $\pm$4.19 | 58.9  $\pm$2.14 | 56.4  $\pm$7.03 | 32.1  $\pm$0.90 | 30.1  $\pm$0.29 | 52.0
EEIL | 93.4  $\pm$0.02 | 83.1  $\pm$3.13 | 88.4  $\pm$2.07 | 30.3  $\pm$0.89 | 25.9  $\pm$0.04 | 64.2
GD | 94.4  $\pm$0.09 | 82.2  $\pm$0.18 | 85.7  $\pm$0.20 | 30.7  $\pm$1.79 | 32.2  $\pm$0.37 | 65.0
Mnemonics†∗ | 94.5  $\pm$0.46 | 82.3  $\pm$0.30 | 86.2  $\pm$0.46 | 54.8  $\pm$0.16 | 52.9  $\pm$0.66 | 74.1
BiC | 95.4  $\pm$0.35 | 84.6  $\pm$0.48 | 88.7  $\pm$0.19 | 61.5  $\pm$0.60 | 62.2  $\pm$0.45 | 78.5
DER++ | 92.0  $\pm$0.54 | 84.0  $\pm$9.43 | 86.6  $\pm$9.44 | 57.4  $\pm$1.31 | 60.0  $\pm$0.74 | 76.0
HAL | 82.8  $\pm$1.94 | 49.5  $\pm$1.51 | 61.1  $\pm$1.43 | 13.2  $\pm$0.77 | 21.2  $\pm$0.41 | 26.2
HAT | 96.7  $\pm$0.18 | 84.0  $\pm$0.23 | 85.0  $\pm$0.98 | 61.2  $\pm$0.72 | 63.8  $\pm$0.41 | 78.1
HyperNet | 94.6  $\pm$0.37 | 76.8  $\pm$1.22 | 83.5  $\pm$0.98 | 23.9  $\pm$0.60 | 28.0  $\pm$0.69 | 61.4
Sup | 96.6  $\pm$0.21 | 87.9  $\pm$0.27 | 91.6  $\pm$0.15 | 64.3  $\pm$0.24 | 68.4  $\pm$0.22 | 81.8
HAT+CSI | 98.7  $\pm$0.06 | 92.0  $\pm$0.37 | 94.3  $\pm$0.06 | 68.4  $\pm$0.16 | 72.4  $\pm$0.21 | 85.2
Sup+CSI | 98.7  $\pm$0.07 | 93.0  $\pm$0.13 | 95.3  $\pm$0.20 | 65.9  $\pm$0.25 | 74.1  $\pm$0.28 | 85.4

The calibrated versions (+c) of our methods are omitted as calibration does
not affect TIL performance. Exemplar-free methods are italicized. The last
column Avg. shows the average TIL accuracy of each method over all datasets.

##  Appendix F Hyper-parameters

Here we report the hyper-parameters that we did not report in the main paper
due to space limitations. We mainly report the hyper-parameters of the
proposed methods, HAT+CSI, Sup+CSI, and their calibrated versions. For all the
experiments of the proposed methods, we use the values chosen by the original
CSI [58]. We use LARS [66] optimization with learning rate 0.1 for training
the feature extractor. We linearly increase the learning rate by 0.1 per epoch
for the first 10 epochs. After that, we use cosine scheduler [42] without
restart as in [58, 13]. After training the feature extractor, we train the
linear classifier for 100 epochs with SGD with learning rate 0.1 and reduce
the rate by 0.1 at 60, 75, and 90 epochs. For all the experiments except
MNIST, we train the feature extractor for 700 epochs with batch size 128.

For the following hyper-parameters, we use 10% of training data for validation
to find a good set of values. For the number of epochs and batch size for
MNIST, Sup+CSI trains for 1000 epochs with batch size of 32 while HAT+CSI
trains for 700 epochs with batch size of 256. The hard attention
regularization penalty $\lambda_{i}$ in HAT is different by experiments and
task $i$. For MNIST, we use $\lambda_{1}=0.25$, and
$\lambda_{2}=\cdots=\lambda_{5}=0.1$. For C10-5T, we use $\lambda_{1}=1.0$,
and $\lambda_{2}=\cdots=\lambda_{5}=0.75$. For C100-10T, $\lambda_{1}=1.5$,
and $\lambda_{2}=\cdots=\lambda_{10}=1.0$ are used. For C100-20T,
$\lambda_{1}=3.5$, and $\lambda_{2}=\cdots=\lambda_{20}=2.5$ are used. For
T-5T, $\lambda_{i}=0.75$ for all tasks, and lastly, for T-10T,
$\lambda_{1}=1.0$, and $\lambda_{2}=\cdots=\lambda_{10}=0.75$ are used. We use
larger $\lambda_{1}$ for the first task than the later tasks as we have found
that the larger regularization on the first task results in better accuracy.
This is by the definition of regularization in HAT. The earlier task gives
lower penalty than later tasks. We manually give larger penalty to the first
task. We did not search hyper-parameter $\lambda_{t}$ for tasks $t\geq 2$. For
sparsity in Sup+CSI, we simply choose the least sparsity value of 32 used in
the original Sup paper without parameter search.

Calibration methods (HAT+CSI+c and Sup+CSI+c) are based on its memory free
versions (i.e. HAT+CSI and Sup+CSI). Therefore, the model training part uses
the same hyper-parameters as their calibration free counterparts. For
calibration training, we use SGD with learning rate 0.01, 160 training
iterations, and batch size of 15 for HAT+CSI+c for all experiments. For
Sup+CSI+c, we use the same values for all the experiments except for MNIST.
For MNIST, we use learning rate 0.05, batch size of 8, and run 280 iterations.

For the baselines, we use the hyper-parameters reported in the original papers
or in their code. If the hyper-parameters are unknown or the code does not
reproduce the result (e.g., the baseline did not implement a particular
dataset or the code had undergone significant version change), we search for
the hyper-parameters as we did for HAT+CSI and Sup+CSI.

##  Appendix G Forgetting Rate

We discuss forgetting rate (i.e., backward transfer) [41], which is defined
for task $t$ as

$\displaystyle\mathcal{F}^{t}=\frac{1}{t-1}\sum_{k=1}^{t-1}\mathcal{A}_{k}^{\text{init}}-\mathcal{A}_{k}^{t},$
(36)

where $\mathcal{A}_{k}^{\text{init}}$ is the classification accuracy of task
$k$’s data after learning it for the first time and $\mathcal{A}_{k}^{t}$ is
the accuracy of task $k$’s data after learning task $t$. We report the
forgetting rate after learning the last task.

Figure 4:  Average forgetting rate (%). The lower the value, the better the
method is on forgetting.

Figure 4 shows the forgetting rates of each method. Some methods (e.g., OWM,
iCaRL) experience less forgetting than the proposed methods HAT+CSI and
Sup+CSI on M-5T. On this dataset, all the systems performed well. For
instance, OWM and iCaRL achieve 95.8% and 96.0% accuracy while HAT+CSI and
HAT+CSI+c achieve 94.4 and 96.9% accuracy. As we have noted in the main paper,
Sup+CSI and Sup+CSI+c achieve only 80.7 and 81.0 on M-5T although they have
improved drastically from 70.1% of the base method Sup.

OWM and HyperNet show lower forgetting rates than HAT+CSI+c and Sup+CSI+c on
T-5T and T-10T. However, they are not able to adapt to new classes as OWM and
HyperNet achieve the classification accuracy of only 10.0% and 7.9%,
respectively, on T-5T and 8.6% and 5.3% on T-10T. HAT+CSI+c and Sup+CSI+c
achieves 51.7% and 49.2%, respectively, on T-5T and 47.6% and 46.2% on T-10T.

In fact, the performance reduction (i.e., forgetting) in our proposed methods
occurs not because the systems forget the previous task knowledge, but because
the systems learn more classes and the classification naturally becomes
harder. The continual learning mechanisms (HAT and Sup) used in the proposed
methods experience little or no forgetting because they find independent
subset of parameters for each task, and the learned parameters are not
interfered during training. For the forgetting rate results in the TIL
setting, refer to our earlier workshop paper [28].

##  Appendix H Pseudo-Code

For task $k$, Let
$p(y|{\bm{x}},k)=\text{softmax}f(h({\bm{x}},k;\theta,{\bm{e}}^{k});\phi_{k})$,
where $\theta$ is the parameters for adapter, ${\bm{e}}^{k}$ is the trainable
embedding for hard attentions, and $\phi_{k}$ is the set of parameters of the
classification head of task $k$. Algorithm 1 and Algorithm 2 describe the
training and testing processes, respectively. We add comments with the symbol
“//”.

Algorithm 1 Training MORE

1:Memory $\mathcal{M}$, learning rate $\lambda$, a sequence of tasks
$\mathcal{D}=\\{\mathcal{D}^{k}\\}_{k=1}$, and parameters
$\\{\theta,{\bm{e}},\phi\\}$, where ${\bm{e}}$ and $\phi$ are collections of
task embeddings ${\bm{e}}^{k}$ and task heads $\phi_{k}$

2:// CL starts

3:for each task data $\mathcal{D}^{k}\in\mathcal{D}$ do

4: // Model training

5: for a batch $({\bm{X}}_{i}^{k},{\bm{y}})$ in $\mathcal{D}^{k}$, until
converge do

6: ${\bm{X}}_{s}$ = $sample(\mathcal{M})$

7: Compute loss (Eq. 24$+$Eq. 13) and gradients of parameters

8: Modify the model parameters $\nabla\theta\leftarrow\nabla\theta^{\prime}$
using Eq. 11

9: Update parameters as $\theta\leftarrow\theta-\lambda\nabla\theta,\
{\bm{e}}^{k}\leftarrow{\bm{e}}^{k}-\lambda\partial\mathcal{L},\
\phi_{k}\leftarrow\phi_{k}-\lambda\partial\mathcal{L}$

10: end for

11: // Back-updating in Section 5.1.2

12: Randomly select $\tilde{\mathcal{D}}\subset\mathcal{D}^{k}$, where
$|\tilde{\mathcal{D}}|=|\mathcal{M}|$

13: for each task $j$, until converge do

14: minimize $\mathcal{L}(\phi_{j})$ of Eq. 26

15: end for

16: // Obtain statistics in Section 5.1.3

17: Compute ${\bm{\mu}}^{k}_{j}$ using Eq. 28 and ${\bm{S}}^{k}$ using Eq. 29

18:end for

Algorithm 2 MORE Prediction

1:Test instance ${\bm{x}}$ and parameters $\\{\theta,{\bm{e}},\phi\\}$

2:for each task $k$ do

3: Obtain $p(\mathcal{Y}^{k}|{\bm{x}},k)$

4: Obtain $s^{k}({\bm{x}})$ using Eq. 27

5:end for

6:// Concatenate outputs for final prediction $y$ and OOD score $s$

7:$y=\operatorname*{arg\,max}\bigoplus_{1\leq k\leq
t}p(\mathcal{Y}^{k}|{\bm{x}},k)s^{k}({\bm{x}})$ (i.e. Eq. 30)

8:$s=\max\bigoplus_{1\leq k\leq
t}p(\mathcal{Y}^{k}|{\bm{x}},k)s^{k}({\bm{x}})$

##  Appendix I Size of Memory Required

In this section, we report sizes of memory required by each method in Section
5.2. The sizes include network size, replay buffer, all other parameters or
example kept in memory simultaneously for a model to be functional.

We use an ‘entry’ to refer to a parameter or element in a vector or matrix to
calculate the total memory required to train and test. The pre-trained
backbone uses 21.6 million (M) entries (parameters). The adapter modules use
1.2M entries for CIFAR10 and 2.4M for other datasets. The baselines and our
method use 22.9M and 24.1M entries for the model on CIFAR10 and other
datasets, respectively. The unique technique of each method may add additional
entries for training and test/inference.

The total memory required for each method without considering the replay
memory buffer is reported in Table 12. Our method is competitive in memory
consumption. Baselines such as OWM and A-GEM take considerably more memory
than our system. iCaRL and DER++ take the least amount of memory, but the
differences between our method and theirs are only 0.8M, 1.8M, 3.6M, 1.0M, and
1.8M for C10-5T, C100-10T, C100-20T, T-5T and T-10T.

Table 12: Required Memory

Method | C10-5T | C100-10T | C100-20T | T-5T | T-10T
---|---|---|---|---|---
OWM | 26.6M | 28.1M | 28.1M | 28.2M | 28.2M
MUC | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
PASS | 22.9M | 24.2M | 24.2M | 24.3M | 24.4M
LwF | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
iCaRL | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
A-GEM | 26.5M | 31.4M | 31.4M | 31.5M | 31.5M
EEIL | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
GD | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
BiC | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
DER++ | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
HAL | 22.9M | 24.1M | 24.1M | 24.1M | 24.1M
HAT | 23.0M | 24.7M | 25.4M | 24.6M | 25.1M
Sup | 24.7M | 33.7M | 45.7M | 27.7M | 33.7M
MORE | 23.7M | 25.9M | 27.7M | 25.1M | 25.9M

Total memory (in entries) required for each method without the replay memory
buffer.

Many replay based methods (e.g., iCaRL, HAL) need to save the previous network