# Kalman Filter for Online Classification
of Non-Stationary Data

Michalis K. Titsias
Google DeepMind
<EMAIL_ADDRESS>
&Alexandre Galashov11footnotemark: 1
Google DeepMind
<EMAIL_ADDRESS>
&Amal Rannen-Triki
Google DeepMind
<EMAIL_ADDRESS>
&Razvan Pascanu
Google DeepMind
<EMAIL_ADDRESS>
&Yee Whye Teh
Google DeepMind
<EMAIL_ADDRESS>
&Jörg Bornschein
Google DeepMind
<EMAIL_ADDRESS>Joint first authorship

###### Abstract

In Online Continual Learning (OCL) a learning system receives a stream of data
and sequentially performs prediction and training steps. Important challenges
in OCL are concerned with automatic adaptation to the particular non-
stationary structure of the data, and with quantification of predictive
uncertainty. Motivated by these challenges we introduce a probabilistic
Bayesian online learning model by using a (possibly pretrained) neural
representation and a state space model over the linear predictor weights. Non-
stationarity over the linear predictor weights is modelled using a “parameter
drift” transition density, parametrized by a coefficient that quantifies
forgetting. Inference in the model is implemented with efficient Kalman filter
recursions which track the posterior distribution over the linear weights,
while online SGD updates over the transition dynamics coefficient allows to
adapt to the non-stationarity seen in data. While the framework is developed
assuming a linear Gaussian model, we also extend it to deal with
classification problems and for fine-tuning the deep learning representation.
In a set of experiments in multi-class classification using data sets such as
CIFAR-100 and CLOC we demonstrate the predictive ability of the model and its
flexibility to capture non-stationarity.

##  1 Introduction

Continual Learning [e.g. 18, 34] is an open problem that has been receiving
increasing attention in recent years. At its core, it aims to provide answers
on how to train and use models in non-stationary scenarios. A multitude of
different and sometimes conflicting desiderata have been considered for
continual learning, including forward transfer, backward transfer, avoiding
catastrophic forgetting and maintaining plasticity [18]. Training and
evaluation protocols highlight different constraints such as limited memory to
store examples, limited model size or computational constraints.

In this work we focus on the Online Learning (OL) [41, 21] scenario, where a
learner receives a sequence of inputs $x_{n}$ and prediction targets $y_{n}$.
At each time-step $n$, the model first observes $x_{n}$, makes a prediction
and then receives the associated loss and ground truth target for learning.
Within the deep learning community this scenario has also been referred to as
_Online Continual Learning_ (OCL) [10, 16], with the focus shifted more
towards obtaining the best empirical performance on some given data instead of
bounding the worst-case regret. Note that in OL/OCL each observation
$(x_{n},y_{n})$ is first used for evaluation before it is used for training.
No separate evaluation-sets are required and this objective naturally supports
task-agnostic and non-stationary scenarios. Depending on the nature of the
data stream, plasticity, not-forgetting and sample-efficiency all play a
crucial role during learning. Furthermore, when considering the cumulative
next-step log-loss under this protocol, it directly corresponds to the
prequential description length and is thus a theoretically well motivated
evaluation metric for non-stationary scenarios under the Minimum Description
Length principle [17, 4, 7].

In this paper, we propose a new method based on Kalman filters which
explicitly takes into account non-stationaries in the data stream. It assumes
a prior Markov model over the linear predictor weights that uses a “parameter
drift” transition density parametrized by a coefficient that quantifies
forgetting. The prior model is then combined with observations using online
Bayesian updates, implemented by computationally fast Kalman filter
recursions, that track the posterior distribution over the weights of the
linear predictor as the data distribution changes over time. These Bayesian
updates are also combined with online SGD updates over the forgetting
coefficient, thus allowing for more flexible adaptation to non-stationarity.
While the theoretical framework is developed assuming the tractable linear
Gaussian case, we also extend the method to classification and for updating
deep learning representations.

We follow the trend introduced by large scale pretrained models, sometimes
referred as foundation models [5], of separating the representation learning
from the readout classifier. These foundation models are seen as providing
generic representations that can be used across a multitude of tasks, and in
continual learning have been argued to provide stable representations, moving
the focus of dealing with the non-stationarity to the convex readout layer.
This separation of concerns allows a more natural integration of non-neural
solution to deal with the continual or online problem. Following this
perspective, we explore the performance of Kalman filter on top of a frozen
pretrained representation. Furthermore, we also demonstrate that
simultaneously online learning the representation and performing Kalman filter
updates leads to stable learning and provide strong results on online
continual learning benchmarks.

##  2 Online learning with Kalman filter

We first describe the method in an univariate regression setting and discuss
in Section 2.1 how we adapt it to classification. We assume a stream of data
arriving sequentially so that at step $n$ we receive $(x_{n},y_{n})$ where
$x_{n}\in\mathbb{R}^{d}$ is the input vector and $y_{n}\in\mathbb{R}$ is the
output. Our objective is to introduce an online learning model that captures
non-stationarities and learns a good predictor for future data. Our model
consists of two parts. The fist part is a deep neural network that outputs a
representation $\phi(x;\theta)\in\mathbb{R}^{m}$ so that
$\phi_{n}:=\phi(x_{n};\theta)$ denotes the feature vector of the $n$-th data
point. $\theta$ is a set of parameters that could be fixed, if the feature
extractor is a _pretrained_ network, or learnable, when it is either fine-
tuned or learnt from scratch. Given $\phi_{n}$ the output $y_{n}$ is modelled
by a Gaussian likelihood

$p(y_{n}|w_{n})=\mathcal{N}(y_{n}|w_{n}^{\top}\phi_{n},\sigma^{2}),$ (1)

where the $m$-dimensional vector of regression coefficients $w_{n}$ depends on
time index $n$. In other words, $w_{n}$ can change with time in order to
capture distributional changes that may occur.

The second part of model is an explicit prior assumption about how $w_{n}$ can
change over time. More precisely, we will use a simple Gaussian Markov model
over the parameters $w_{n}$, and model _parameter transition or drift_ by the
following process,

$\displaystyle p(w_{0})$ $\displaystyle=\mathcal{N}(w_{0}|0,\sigma_{w}^{2}I),\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \text{Initial parameter}$ (2) $\displaystyle p(w_{n}|w_{n-1})$
$\displaystyle=\mathcal{N}(w_{n}|\gamma_{n}w_{n-1},(1-\gamma_{n}^{2})\sigma_{w}^{2}I),\
\ n\geq 1.\ \ \ \ \text{Parameter drift}$ (3)

The time-dependent parameter $\gamma_{n}$ takes values in $[0,1]$ and
quantifies the _memory or forgetting_ of the process. For example, when
$\gamma_{n}=1$ then $w_{n}=w_{n-1}$, which means that at time step $n$ the
model re-uses (or copies forward) the parameter $w_{n-1}$ from the previous
step. Such extreme case is suitable when there is no distributional change at
time $n$. In the other extreme case, when $\gamma_{n}=0$ the parameter $w_{n}$
is fully refreshed, i.e. reset to the prior $\mathcal{N}(0,\sigma_{w}^{2}I)$,
which implies a sharp change in the distribution. Similarly, intermediate
values of $\gamma_{n}\in(0,1)$ can model more smooth or gradual changes.
Flexible learning of $\gamma_{n}$ through time will be a key element of our
method that we describe in Section 2.1.1 for the classification problem.
Furthermore, it is worth noting that the transition model in (3) is a
variance-preserving diffusion, so that when
$w_{n-1}\sim\mathcal{N}(0,\sigma_{w}^{2}I)$ the next state
$w_{n}=\gamma_{n}w_{n-1}+\sqrt{1-\gamma_{n}^{2}}\epsilon$
($\epsilon\sim\mathcal{N}(0,I)$) follows also
$\mathcal{N}(0,\sigma_{w}^{2}I)$. Hence, the variance $\sigma_{w}^{2}$ of the
regression parameters remains constant through time.

Having specified the observation model in (1) and the transition model over
the parameters $w_{n}$ in (2)-(3) we can write the full joint density up to
the $n$-th observation as

$p(w_{0})\prod_{i=1}^{n}p(y_{i}|w_{i})p(w_{i}|w_{i-1})=\mathcal{N}(w_{0}|0,\sigma_{w}^{2}I)\prod_{i=1}^{n}\mathcal{N}(y_{i}|w_{i}^{\top}\phi_{i},\sigma^{2})\mathcal{N}(w_{i}|\gamma_{i}w_{i-1},(1-\gamma_{i}^{2})\sigma_{w}^{2}I).$

Clearly, this is a type of a linear Gaussian state space model where exact
online Bayesian inference over $w_{n}$ can be solved with standard recursions.
Specifically, inference can be carried out by standard Kalman filter
prediction and update steps [45] to compute online the Bayesian posterior over
$w_{n}$. The prediction step requires computing the posterior over $w_{n}$
given all past data up to time $n-1$ (and excluding the current $n$-th
observation), which is a Gaussian density
$p(w_{n}|y_{1:n-1})=\mathcal{N}(w_{n}|m_{n}^{-},A_{n}^{-})$ with parameters

$m_{n}^{-}=\gamma_{n}m_{n-1},\ \ \
A_{n}^{-}=\gamma_{n}^{2}A_{n-1}+(1-\gamma_{n}^{2})\sigma_{w}^{2}I.$ (4)

The update step finds the updated Gaussian posterior
$p(w_{n}|y_{1:n})=\mathcal{N}(w_{n}|m_{n},A_{n})$ by modifying the mean vector
$m_{n}$ and the covariance matrix $A_{n}$ to incorporate the information
coming from the most recent observation $(x_{n},y_{n})$ according to

$m_{n}=m_{n}^{-}+\frac{A_{n}^{-}\phi_{n}}{\sigma^{2}+\phi_{n}^{\top}A_{n}^{-}\phi_{n}}(y_{n}-\phi_{n}^{\top}m_{n}^{-}),\
\ \
A_{n}=A_{n}^{-}-\frac{A_{n}^{-}\phi_{n}\phi_{n}^{\top}A_{n}^{-}}{\sigma^{2}+\phi_{n}^{\top}A_{n}^{-}\phi_{n}}.$
(5)

The initial conditions for the recursions are $m_{0}=0$ and
$A_{0}=\sigma_{w}^{2}I$. The cost per iteration is $O(m^{2})$ which means that
the Kalman recursions are computationally very efficient.

Further, if we remove the stochasticity from the transition dynamics by
setting $\gamma_{n}=1$ for any $n$, the above Kalman recursions reduces to
online Bayesian linear regression as detailed in Appendix A.

##### Prediction.

As the online model sequentially receives observations and updates its
Bayesian posterior distribution over $w_{n}$, it can also perform next step
predictions. Suppose that after $n-1$ steps the model has observed the data
$(x_{i},y_{i})_{i=1}^{n-1}$ and computed the posterior $p(w_{n}|y_{1:n-1})$.
Then for the next input data $x_{n}$ the model can predict its output $y_{n}$
based on the Bayesian predictive density

$p(y_{n}|y_{1:n-1})=\int
p(y_{n}|w_{n})p(w_{n}|y_{1:n-1})dw_{n}=\mathcal{N}(y_{n}|\phi_{n}^{\top}m_{n}^{-},\phi_{n}^{\top}A_{n}^{-}\phi_{n}+\sigma^{2}),$
(6)

which is analytic for this Gaussian regression case, while for the
classification case will require approximate inference and Monte Carlo
sampling as detailed in Section 2.1.1.

###  2.1 Application to classification

We now adopt the above online learning model to multi-class classification
problems. Suppose a classification problem with $K$ classes, where the label
$y_{n}$ is encoded as $K$-dimensional one-hot vector, i.e.
$y_{n}\in\\{0,1\\}^{K}$, $\sum_{k=1}^{K}y_{n,k}=1$. A suitable observation
model for classification is the standard softmax likelihood
$p(y_{n,k}=1|W_{n})=\frac{\exp\\{w_{n,k}^{\top}\phi_{n}\\}}{\sum_{j=1}^{K}\exp\\{w_{n,j}^{\top}\phi_{n}\\}},$
where $W_{n}=(w_{n,1},\ldots,w_{n,K})$ is a $m\times K$ matrix storing the
parameters $W_{n}$ which play a similar role to previous regression
coefficients. These parameters follow $K$ independent Markov processes so that
each $k$-th column $w_{n,k}$ of $W_{n}$ is independent from the other columns
and obeys the transition dynamics from (2)-(3). However, unlike the regression
case, exact online inference over the parameters $W_{n}$ using Kalman
recursions is intractable due to the non-Gaussian form of the softmax
likelihood. Thus, we need to rely on approximate inference. Next we derive a
fast and very easy to implement inference technique that still uses the exact
Kalman recursions. This consists of two main components described next.

##### (i) Maintain a fast and analytic Kalman recursion.

To achieve this we introduce a Gaussian likelihood that (as a means to
approximate inference) replaces the softmax likelihood. It has the form
$q(y_{n}|W_{n})=\prod_{j=1}^{K}\mathcal{N}(y_{n,j}|w_{n,j}^{\top}\phi_{n},\sigma^{2}),$
which explains the elements of the one-hot vector by a Gaussian density, a
trick that has been used successfully in the literature e.g. for Gaussian
process classification [38] and meta learning [35]. With this approximate
likelihood the Kalman recursions remain tractable and propagate forward an
approximate predictive posterior
$q(W_{n}|y_{1:n-1})=\prod_{k=1}^{K}\mathcal{N}(w_{n,k}|m_{n,k}^{-},A_{n}^{-})$
with mean parameters given by the $m\times K$ matrix
$M_{n}^{-}=(m_{n,1}^{-},\ldots,m_{n,K}^{-})$ and covariance parameters given
by the $m\times m$ matrix $A_{n}^{-}$:

$M_{n}^{-}=\gamma_{n}M_{n-1},\ \ \
A_{n}^{-}=\gamma_{n}^{2}A_{n-1}+(1-\gamma_{n}^{2})\sigma^{2}_{w}I.$ (7)

The corresponding updated posterior
$q(W_{n}|y_{1:n})=\prod_{k=1}^{K}\mathcal{N}(w_{n,k}|m_{n,k},A_{n})$ has
parameters

$M_{n}=M_{n}^{-}+\frac{A_{n}^{-}\phi_{n}}{\sigma^{2}+\phi_{n}^{\top}A_{n}^{-}\phi_{n}}\times(y_{n}^{\top}-\phi_{n}^{\top}M_{n}^{-}),\
\ \
A_{n}=A_{n}^{-}-\frac{A_{n}^{-}\phi_{n}\phi_{n}^{\top}A_{n}^{-}}{\sigma^{2}+\phi_{n}^{\top}A_{n}^{-}\phi_{n}}.$
(8)

The recursion is initialized at $M_{0}={\bf 0},A_{0}=\sigma^{2}_{w}I$, where
${\bf 0}$ denotes the $m\times K$ matrix of zeros. A full iteration costs
$O(Km+m^{2})$ and if the size $m$ of the feature vector is larger than the
number of classes $K$, the term $O(m^{2})$ dominates and the complexity is the
same as in univariate regression. The crucial factor to obtain such an
efficiency is that the covariances matrices $(A_{n}^{-},A_{n})$ are shared
among all $K$ classes, which is because the hyperparameter $\sigma^{2}$ in the
approximate Gaussian likelihood is shared among all $K$ dimensions.111If we
choose a different $\sigma_{k}^{2}$ per class the time and storage complexity
grows to $O(km^{2})$ which is too expensive in practice.

##### (ii) Kalman posteriors interact with softmax for prediction or parameter
updating.

We view the above Kalman recursion as an online approximate inference
procedure that provides an approximation to the exact posterior distribution.
For example, if $p(W_{n}|y_{1:n-1})$ is the exact intractable predictive
posterior (obtained by Bayes’ rule with the exact softmax likelihood) then
$q(W_{n}|y_{1:n-1})$ computed from Kalman recursion is an approximation to
$p(W_{n}|y_{1:n-1})$. Subsequently, by following standard approximate Bayesian
inference practices, whenever we wish to predict class probabilities or
compute a cross entropy-like loss to optimize parameters, the approximate
posterior will be combined with the exact softmax through Bayesian averaging
and Monte Carlo estimation. Below we make use of this in two cases, one for
online learning the forgetting coefficient $\gamma_{n}$ discussed in Section
2.1.1, and the second in Section 2.1.2 for computing accurate predictive
probabilities and fine-tuning the representation. For the second case we also
find it useful to introduce a Bayesian calibration procedure, which optimizes
online a calibration parameter and improves drastically the predictive
probability estimates.

####  2.1.1 Online updating the forgetting coefficient $\gamma_{n}$

An important aspect of our method is the online updating of the forgetting
coefficient $\gamma_{n}$, which is indexed by $n$ to indicate that it can
change over time to reflect the distributional changes seen in the data
stream. Instead of using a full Bayesian approach (that will require an extra
hierarchical prior assumption) over $\gamma_{n}$ we will follow a simple
empirical Bayes method where we update $\gamma_{n}$ by online point
estimation. For that, we first initialize $\gamma_{0}$ and then for any
subsequent time step $n\geq 1$, where we observe $(x_{n},y_{n})$, we first
copy the previous $\gamma_{n-1}$ value to the new step, i.e.
$\gamma_{n}=\gamma_{n-1}$, and then we apply an SGD update to change
$\gamma_{n}$ by maximizing the log predictive probability. Schematically, the
SGD update is written as

$\gamma_{n}\leftarrow\gamma_{n}+\rho_{n}\nabla_{\gamma_{n}}\log
p(y_{n,k}=1|y_{1:n-1}),$ (9)

where we further parametrize $\gamma_{n}=\exp(-0.5\delta_{n})$, with
$\delta_{n}\geq 0$, so that the update is applied to $\delta_{n}$.222The hard
constraint $\delta_{n}\geq 0$ is imposed through clipping. However, since the
log predictive probability is not tractable we consider the approximation

$\log p(y_{n,k}=1|y_{1:n-1})\approx\log\int
p(y_{n,k}=1|W_{n})q(W_{n}|y_{1:n-1})dW_{n},$ (10)

where $p(y_{n}|W_{n})$ is the softmax and
$q(W_{n}|y_{1:n-1})=\prod_{k=1}^{K}\mathcal{N}(w_{n,k}|m_{n,k}^{-},A_{n}^{-})$
is the Kalman analytic approximate posterior distribution. To estimate this we
can use the standard procedure to reparametrize the integral in terms of the
$K$-dimensional vector of logits $f_{n}=W_{n}^{\top}\phi_{n}$ which follows
the factorized Gaussian distribution $q(f_{n}|\mu_{n},s_{n}^{2}I)$ with mean
$\mu_{n}=(M_{n}^{-})^{\top}\phi_{n}$ and isotropic variance
$s_{n}^{2}=\phi_{n}^{\top}A_{n}^{-}\phi_{n}$. After this reparametrization,
(10) leads to the estimate

$\displaystyle\log p(y_{n,k}=1|y_{1:n-1})$
$\displaystyle=\log\int\frac{\exp\\{f_{n,k}\\}}{\sum_{j=1}^{K}\exp\\{f_{n,j}\\}}q(f_{n}|\mu_{n},s_{n}^{2}I)df_{n}$
(11)
$\displaystyle\approx\log\frac{1}{S}\sum_{s=1}^{S}\frac{\exp\\{\mu_{n,k}+s_{n}\epsilon^{(s)}_{k}\\}}{\sum_{j=1}^{K}\exp\\{\mu_{n,j}+s_{n}\epsilon^{(s)}_{j}\\}},\
\ \epsilon^{(s)}\sim\mathcal{N}(0,I),$ (12)

where to move from (11) to (12) we first reparametrize the integral to be an
expectation under the standard normal and then apply Monte Carlo. To update
$\gamma_{n}$ using SGD, we differentiate this final Monte Carlo estimate of
the loss $-\log p(y_{n,k}=1|y_{1:n-1})$ wrt the parameter $\delta_{n}$ in
$\gamma_{n}=\exp\\{-0.5\delta_{n}\\}$, where $\gamma_{n}$ appears in
$(\mu_{n},s_{n}^{2})$ through the computation
$M_{n}^{-}=\gamma_{n}M_{n-1},A_{n}^{-}=\gamma_{n}^{2}A_{n-1}+\sigma_{w}^{2}(1-\gamma_{n}^{2})I$,
while the parameters $(M_{n-1},A_{n-1})$ of the posterior up to time $n-1$ are
taken as constants.

####  2.1.2 Calibration of class probabilities and fine-tuning the
representation

Given that in classification the predictive posterior $q(W_{n}|y_{1:n-1})$ is
an (possibly crude) approximation to the true posterior, the log predictive
probability estimate in (12) can be inaccurate. We improve this estimate by
fine-tuning over a _calibration parameter_ that is optimized with gradient
steps. In the same step we can also fine-tune the neural network parameters
$\theta$ that determine the representation vector $\phi(x,\theta)$.
Specifically, for the calibration procedure we introduce a parameter
$\alpha>0$ that rescales the logits inside the softmax function, so that the
softmax in (11) is replaced by $\frac{\exp\\{\alpha
f_{n,k}\\}}{\sum_{j=1}^{K}\exp\\{\alpha f_{n,j}\\}}$ and the final Monte Carlo
estimate becomes

$\displaystyle\log
p(y_{n,k}=1|y_{1:n-1},\alpha,\theta)\approx\log\frac{1}{S}\sum_{s=1}^{S}\frac{\exp\\{\alpha\mu_{n,k}+\alpha
s_{n}\epsilon^{(s)}_{k}\\}}{\sum_{j=1}^{K}\exp\\{\alpha\mu_{n,j}+\alpha
s_{n}\epsilon^{(s)}_{j}\\}}.$ (13)

Then the negative log predictive probability, $-\log
p(y_{n,k}=1|y_{1:n-1},\alpha,\theta)$, is treated as a loss that is optimized
jointly over $(\alpha,\theta)$ with online SGD steps, i.e. as individual data
points $(x_{n},y_{n})$ arrive sequentially. This resembles the forward-
calibration described in [7]. Algorithm 1 summarizes the whole online learning
procedure that includes the Kalman filter recursion, update of coefficient
$\gamma_{n}$ and fine-tuning of the representation parameters $\theta$ and
calibration parameter $\alpha$. An ablation study in Appendix E shows that the
calibration procedure can significantly improve the log predictive probability
estimates.

The fully online process for fine-tuning the deep network parameters $\theta$
in Algorithm 1 can be expensive since modern hardware is computationally more
effective when forward and backpropagation passes in deep neural nets are
applied jointly to minibatches rather to individual data points. In practice,
we therefore also consider a faster version of Algorithm 1 where we predict
ahead a batch of $b$ data points by treating them as i.i.d. and then take a
gradient step over $(\alpha,\theta)$, i.e. we use as loss
$-\frac{1}{b}\sum_{i=1}^{b}\log
p(y_{n+i}|y_{1:n-1},\alpha,\theta),i=1,\ldots,b$. This creates two options for
the Markov dynamics: (i) either apply the transition "batch-wise" where the
transition is taken every $b$ data forming the minibatch (so that time index
$n$ corresponds to the number of minibatches), or (ii) the minibatch updating
only affects the prediction over future data (we predict ahead $b$ points
instead of only the next one) and the fine-tuning of $(\alpha,\theta)$, while
the subsequent Kalman recursion steps and SGD update over $\gamma_{n}$ are
applied online, i.e. by processing the $b$ data in the minibatch one by one.
Both schemes can be useful in practice, as further discussed in the Appendix.
For simplicity, Algorithm 1 presents the purely online version, while
pseudocode for the above minibatch-based variants is similar.

Algorithm 1 Kalman filter online learning

Input: Data stream $(x_{n},y_{n})_{n\geq 1}$; representation $\phi(x,\theta)$;
parameters $\theta$; hyperparameters $(\sigma^{2},\sigma_{w}^{2})$ with
default values $(1/K,1/m)$.

Initialise $M_{0}={\bf 0},A_{0}=\sigma_{w}^{2}I$ and $\delta_{0}$ (e.g. to
value 0.0 so that $\gamma_{0}=1$).

for data point $n=1,2,3,\ldots,$ do

Observe $x_{n}$, compute $\phi_{n}=\phi(x_{n},\theta)$ make a prediction for
the label $y_{n}^{*}$ via eq. (13)

Observe true class label $y_{n}$

(Optional) Fine-tune the deep neural network parameters $\theta$ together with
the calibration parameter $\alpha$, as described in Section 2.1.2

Update $\delta_{n}$ as described in Section 2.1.1 and set
$\gamma_{n}=\exp\\{-0.5\delta_{n}\\}$

$M_{n}^{-}=\gamma_{n}M_{n-1},\
A_{n}^{-}=\gamma_{n}^{2}A_{n-1}+(1-\gamma_{n}^{2})\sigma^{2}_{w}I$

Update Kalman statistics:
$M_{n}=M_{n}^{-}+\frac{A_{n}^{-}\phi_{n}}{\sigma^{2}+\phi_{n}^{\top}A_{n}^{-}\phi_{n}}\times(y_{n}^{\top}-\phi_{n}^{\top}M_{n}^{-}),\
A_{n}=A_{n}^{-}-\frac{A_{n}^{-}\phi_{n}\phi_{n}^{\top}A_{n}^{-}}{\sigma^{2}+\phi_{n}^{\top}A_{n}^{-}\phi_{n}}$

end for

##  3 Related Work

##### Continual learning to reduce forgetting.

Classical approaches for continual learning have been developed with a focus
on reducing forgetting [13, 34, 31]. Most of these approaches could be
separated into three different families: _Replay or sampling based approaches_
include [11, 3, 44, 2, 23, 30, 42, 48], _Regularization based approaches_
include [24, 49, 1, 28, 50, 8, 9] and _Parameter isolation approaches_ include
[32, 39, 40]. Other approaches have also been proposed, such as [27] where an
expansion-based approach is proposed, leveraging a set of experts trained and
expanded using a Bayesian non-parametric framework. More recently, the trend
moved the focus towards forward transfer and efficient adaptation [19, 6, 16,
20].

While a significant progress has been achieved through this line of research,
one major drawback, highlighted by different recent works [16, 10, 9], is the
focus on small-scale artificial benchmarks with abrupt and unnatural
distribution shift, and on metrics that fail to capture the capability of the
models to efficiently adapt to the non-stationarity in the input data. In this
work, we focus on fast adaptation and the next-step prediction problem from
OL/OCL.

##### Online continual learning and fast adaptation.

Different recent works considered the problem of fast adaptation and the set
of constraints and objectives that are realistic in an online scenario.
Different recent benchmarks, e.g. CLOC [10] and CLEAR [29], propose a sequence
of temporally sorted images with naturally shifting visual concepts. CLOC
leverages a subset of 39M images from YFCC100M [46] along with their
timestamps and geolocalisation tags, spanning a period of 9 years. The paper
also highlights the limits of the classical continual learning approaches, and
proposes simple baselines to overcome them, based mostly on adapting the
online learning rate and the replay buffer size. They focus on an online
evaluation protocol where each mini-batch is used for testing before adding it
to the training dataset. In this work, we largely follow the CLOC setting. We
evaluate our approach on the CLOC data and on modified CIFAR100 versions that
are inspired by it.

In [7] the authors highlight the theoretical and practical benefits of using
the sequential (online) next-step performance for model evaluation. They
emphasize the connection to compression based inference and to the prequential
Minimum Description Length principle [12, 36]. Empirically, they evaluate SGD
based techniques on the pareto-front of prediction loss vs. computational
requirements; and propose forward-calibration and specific rehearsal
approaches to improve results. We compare against their methods in our
experiments on CLOC.

The authors of [16] base their work on the observation that CL approaches have
been developed under unrealistic constraints, allowing for offline learning on
data with multiple passes without any limitation of computational cost. In
realistic settings where we aim at updating a model on continuously incoming
data, approaches that are slower than the stream would be impractical, or
reach suboptimal performance in the limited time and computational budget. The
authors propose an evaluation protocol that puts the computational cost at the
center. They propose adding a delay between model update and evaluation. This
delay is related to the computational cost of the updating method. Under the
same budget, a twice more expensive approach would update the model half as
often. With this realistic evaluation, the authors show that a simple baseline
based on experience replay outperforms state-of-the-art CL methods, due to
their complexity. In this work, we follow the protocol described in [16]. Our
approach has a relative complexity that requires no delay between training and
evaluation. We therefore compare against the baselines reported in [16] that
have the same properties, namely, ER [11], ER++ [16] and ACE [9].

##### Kalman filters.

The idea of relying on Kalman filters to estimate the posterior distribution
over the weights of a neural networks dates back to the 90s, with work such as
[e.g 43, 14, 37]. The focus in these works is to accelerate learning by
incorporating second order information in the step size, and the setting
typically considered is that of stationary learning. Kalman filter for dealing
with online learning has been explored in the linear case for example in [47,
25]. In contrast, in our work we focus on the ability of Kalman filter to help
with the online continual learning problem by relying on pretrained
representations.

##  4 Experiments

###  4.1 Illustrative time series example

We first apply our method to artificial time series data. The task is to track
a non-stationary data stream of scalar noisy observations $y_{n}$ without any
conditioning input $x_{n}$. We further assume a very simple model where the
feature is just an univariate constant value equal to unity, i.e. $\phi_{n}=1$
so that the observation likelihood simplifies as
$p(y_{n}|w_{n})=\mathcal{N}(y_{n}|w_{n},\sigma^{2})$ and the parameter
$w_{n}$, to be inferred through time, models the unknown expected value of
$y_{n}$.

Figure 1 shows the results of the Kalman model that was initialized with
$\gamma_{0}=1$ and learns it online, as described in Appendix B. The non-
stationary nature of the artificial series is such that the signal is piece-
wise (noisy) constant with seven change-points. As shown by the second row in
the left panel in Figure 1 the learned value of $\gamma_{n}$ is able to adjust
to this non-stationarity by dropping the value of $\gamma_{n}$ quite below the
value one (in order to refresh the Bayesian statistics over $w_{n}$) any time
there is a change-point. In contrast, if we remove the ability to capture non-
stationarity, i.e. by setting $\gamma_{n}=1$ for all $n$, the performance gets
much worse as shown by the accumulated log predictive density scores in Figure
1 and by Figure 4 in the Appendix C.

|
---|---
Figure 1: Results in a artificial time series example of $3058$ observations.
Top row in left panel shows the data (black dots) and the predicted mean and
uncertainty (orange lines) over $y_{n}$ (as data arrive sequentially from left
to right and we perform online next step prediction), while the bottom row
shows the optimized values of $\gamma_{n}^{2}=\exp(-\delta_{n})$. Right panel
shows the accumulated average log predictive density, i.e.
$\frac{1}{n}\sum_{i=1}^{n}\log p(y_{i}|y_{1:i-1})$, computed across time for
the model that learns $\gamma_{n}$ and the model that ignores non-stationarity
by setting $\gamma_{n}=1$ for all $n$.

###  4.2 Online classification

In this section, we study the behaviour of our method when applied to online
classification. We consider the OCL scenario where data arrives in small
batches (chunks) [10, 7, 16]: The learning algorithm is exposed to the stream
of data $\mathcal{S}$ such that every point of time $n$, a chunk of data
$S_{n}=\\{(x_{n,b+i},y_{n,b+i})\\}_{i=1}^{b}$ of size $b$ is revealed. The
algorithm first predicts the labels $y_{s},\;s=(nb+1),\ldots,(n+1)b$, and then
updates its parameters $\theta$ and $\alpha$ based on this chunk of data. Like
to before, we compute the _Average Online Accuracy_ :

$acc_{o}(n)=\frac{1}{nb}\sum_{s=1}^{nb}acc(y_{s},\hat{y_{s}}),$ (14)

where $y_{s}$ is the ground truth label and $\hat{y}_{s}$ is the prediction of
the model. This metric contains accuracies computed on the fly over the course
of training and quantifies how well the learning algorithm ingests new
knowledge.

####  4.2.1 Online classification on CIFAR-100

We evaluate the performance of the Kalman Filter on two variants of online
classification on CIFAR-100 [26]: _stationary online classifcation on
CIFAR-100_ and _non-stationary online classifaction on CIFAR-100_. In the
_stationary case_ , we follow the protocol described in [16] where the stream
$S$ is constructed by randomly shuffling CIFAR-100 dataset and split into
chunks, so that learning algorithm does one pass through CIFAR-100. This is
similar to One-Pass ImageNet [22] benchmark. Since it is randomly shuffled,
there is no non-stationarity. In the _non-stationary case_ , we consider a
task-agnostic class-incremental version of Split-CIFAR100 as in [27], where
CIFAR-100 is split into 10 tasks (task identity is not communicated to the
learning algorithm) each containing 10 different classes, concatenated into a
stream and split into chunks. At any time, the learning algorithm solves a
multi-classification problem with $100$ classes. In this setting, there is
very distinct non-stationarity related to the task changes. This benchmark is
also studied by many class incremental continual learning approaches which
focus on alleviating catastrophic forgetting [15, 33] and using average
_incremental_ accuracy as metric. Dealing with catastrophic forgetting goes
beyond the scope of this work and we only focus on average _online_ accuracy.
In both cases, we follow training/evaluation protocol described in [16]
dealing with chunks of size $10$. For more details, see Appendix D.

For Kalman filter variants we consider the following options. _Stationary
Kalman Filter ( $\gamma=1$)_, which could be seen as a form of Bayesian
Logistic Regression, _Non-stationary Kalman Filter with fixed $\gamma=0.999$_
and _Non-stationary Kalman Filter with learned $\gamma$_. On top of that, we
study performance of Kalman filter in three regimes: _no backbone finetuning_
, a regime with fixed randomly initialized features $\phi$ which is a linear
model, _backbone finetuning_ and _backbone finetuning with replay_. As
baselines, we consider ER and ER++ from [16] as well as ACE [9] (results are
taken from [16]). The results are only reported for stationary CIFAR-100 since
this was the only setting studied in [16]. The hyperparameters for methods are
selected by choosing the variant with highest cumulative log probabilities
following MDL principle from [7]. See Appendix D for more details.

The results are given in Table 1. In the stationary CIFAR-100 case, we observe
that stationary Kalman filter provides a reasonable performance and is
generally better than non-stationary Kalman filter with fixed $\gamma$. This
is consistent with our intuition that there is not much non-stationarity to
model and therefore we would not expect Kalman filter to help. We see that
Kalman Filter with learning $\gamma$ leads to slightly better results than
stationary case. Intuitively, it makes sense since in the worst case, this
variant could revert back to $\gamma=1$. Moreover, we see that replay-free
Kalman filter leads to very competitive results against external baselines.
Adding replay to Kalman improves results even further, beating ER++ baseline
which uses much more replay than ER (see [16]).

In the non-stationary CIFAR-100 case, we see that stationary Kalman filter
performs consistently worse than its non-stationary variants. This is
consistent with our intuition since in this case, there is very specific non-
stationarity which Kalman filter could capture. Moreover, we again see that
learning $\gamma$ generally leads to better performance. Figure 2 visualizes
the dynamics of learning $\gamma$ in case of _Backbone Finetuning_ setting,
with red dashed lines indicating task boundaries. We see that in many cases,
$\gamma$ drops at task boundaries, essentially pushing down probabilities of
classes from previous classes and focusing more on future data. This is the
desired behaviour of the method since it essentially captures non-
stationarity.

Table 1: CIFAR-100 results in stationary and non-stationary settings. The numbers in bold correspond to the best performing method in the group. Results for external baselines are taken from [16]. The amount of replay used for Kalman filter is similar to ER baseline. | Average Online Accuracy
---|---
Method | Stationary CIFAR-100 | Non-stationary CIFAR-100
_No backbone finetuning (Purely linear model)_ |  |
Stationary Kalman Filter ($\gamma=1.0$) | 10.9 % | 12.1 %
Non-stationary Kalman Filter (fixed $\gamma=0.999$) | 9.2 % | 31.9 %
Non-stationary Kalman Filter (learned $\gamma$) | 11.4 % |  32.7 %
_Backbone finetuning_ |  |
Stationary Kalman Filter ($\gamma=1.0$) | 16.4 % | 44.5 %
Non-stationary Kalman Filter (fixed $\gamma=0.999$) | 15.9 % | 50.5 %
Non-stationary Kalman Filter (learned $\gamma$) | 16.9 % | 51.2 %
_Backbone finetuning with Replay_ |  |
Stationary Kalman Filter ($\gamma=1.0$) | 18.5 % | 51.6 %
Non-stationary Kalman Filter (fixed $\gamma=0.999$) | 18.9 % | 55.5 %
Non-stationary Kalman Filter (learned $\gamma$) | 19.0 % | 55.5 %
_External baselines_ |  |
ACE [9] | 14.42% | –
ER | 13.62% | –
ER++ | 18.45% | –
Figure 2: Non-stationary CIFAR-100. The left plot shows the evolution of
$\gamma$, the right plot shows the corresponding average online accuracy. The
red dashed lines correspond to the task boundaries.

####  4.2.2 Online large-scale classification on CLOC

In CLOC [10], each image in a chronological data-sequence is associated with
the geographical location where it was taken, discretized to 713 (balanced)
classes. It is a highly non-stationary task on multiple overlapping time-
scales because, e.g., major sports events lead to busts of photos from certain
locations; seasonal changes effect the appearance of landmarks; locations
become more or less popular over time; etc. We use the version of CLOC
described in [7]: around 5% of the images could not be downloaded or decoded
which leaves us with a sequence of 37,093,769 images. This version of the
dataset is similar to the one considered in [16], but we are mindful of
potential small differences due to the downloading errors. We follow the same
protocol as in [16] and in [7].

We use a ResNet-50 backbone and receive the data in chunks of $128$ examples.
For the Kalman filter, we consider the variant with learned $\gamma$, which
performed always better than any fixed one, including $\gamma=1$. We either
keep the backbone fixed, or finetune it. The case of fixed backbone
corresponds to a linear model only. For more details and hyperparameters
selection, see Appendix D. We run experiments where we either start learning
on CLOC from scratch, or start with a ImageNet-pretrained backbone via
supervised loss. As baselines, we consider Online SGD with and without replay
from [7], and compare to the results from [16]: ER [11] and ACE [9]. In order
to produce the plots, we asked the authors of [16] to provide us the data from
their experiments. The results are shown in Figure 3. We see that Kalman
filter provides very strong performance compared to the baselines. When
learning from scratch, replay-free Kalman filter matches the performance of
Online SGD with replay. This is a strong result since Kalman filter does not
need to store additional data in memory. Moreover, even having Kalman filter
with fixed backbone performs much better than online SGD. When starting from
pretrained model, Kalman filter manages to learn more efficiently than any of
the baselines. Overall, this demonstrates the strong capabilities of our
method to do large-scale non-stationary learning.

Figure 3: CLOC results. On the left plot we present the results when we start
learning from scratch. On the right plot we present results when we start from
pretrained model. We also report results for external baselines taken from
[16]: ER and ACE [9]. Note that on the left, the top two curves that are on
top of each other are Online SGD with replay and Kalman filter with finetuned
backbone, while the Kalman Filter outperforms considerably on right plot.

##  5 Conclusion

We presented a probabilistic Bayesian online learning method that combines
efficient Kalman filter inference with online learning of deep learning
representations. We have demonstrated that this method is able to adapt to
non-stationarity of the data and it can give competitive next time-step data
predictions. Some possible directions for future research are: Firstly, it
would be useful to investigate alternative approximate inference approaches
for the classification case where we may construct a more accurate, but still
computationally efficient, online Gaussian approximation to the softmax
likelihood. Secondly, it would be interesting to extend the transition
dynamics to include higher order Markov terms, which could increase the
flexibility of the algorithm to model more complex forms of non-stationarity
and distribution drift.

## References

  * [1] Rahaf Aljundi, Francesca Babiloni, Mohamed Elhoseiny, Marcus Rohrbach, and Tinne Tuytelaars.  Memory aware synapses: Learning what (not) to forget.  In Proceedings of the European conference on computer vision (ECCV), pages 139–154, 2018.
  * [2] Rahaf Aljundi, Eugene Belilovsky, Tinne Tuytelaars, Laurent Charlin, Massimo Caccia, Min Lin, and Lucas Page-Caccia.  Online continual learning with maximal interfered retrieval.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
  * [3] Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio.  Gradient based sample selection for online continual learning.  Advances in neural information processing systems, 32, 2019.
  * [4] Léonard Blier and Yann Ollivier.  The description length of deep learning models.  February 2018.
  * [5] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, S. Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen A. Creel, Jared Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren E. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas F. Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, O. Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Benjamin Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, J. F. Nyarko, Giray Ogut, Laurel J. Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Robert Reich, Hongyu Ren, Frieda Rong, Yusuf H. Roohani, Camilo Ruiz, Jack Ryan, Christopher R’e, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishna Parasuram Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei A. Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang.  On the opportunities and risks of foundation models.  ArXiv, abs/2108.07258, 2021.
  * [6] Jorg Bornschein, Alexandre Galashov, Ross Hemsley, Amal Rannen-Triki, Yutian Chen, Arslan Chaudhry, Xu Owen He, Arthur Douillard, Massimo Caccia, Qixuang Feng, et al.  Nevis’22: A stream of 100 tasks sampled from 30 years of computer vision research.  arXiv preprint arXiv:2211.11747, 2022.
  * [7] Jorg Bornschein, Yazhe Li, and Marcus Hutter.  Sequential learning of neural networks for prequential mdl.  In The Eleventh International Conference on Learning Representations, 2022.
  * [8] Pietro Buzzega, Matteo Boschini, Angelo Porrello, Davide Abati, and Simone Calderara.  Dark experience for general continual learning: a strong, simple baseline.  Advances in neural information processing systems, 33:15920–15930, 2020.
  * [9] Lucas Caccia, Rahaf Aljundi, Nader Asadi, Tinne Tuytelaars, Joelle Pineau, and Eugene Belilovsky.  New insights on reducing abrupt representation change in online continual learning, 2022.
  * [10] Zhipeng Cai, Ozan Sener, and Vladlen Koltun.  Online continual learning with natural distribution shifts: An empirical study with visual data, 2021.
  * [11] Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and M Ranzato.  Continual learning with tiny episodic memories.  2019\.
  * [12] A Philip Dawid and Vladimir G Vovk.  Prequential probability: principles and properties.  Bernoulli, pages 125–162, 1999.
  * [13] Matthias De Lange, Rahaf Aljundi, Marc Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars.  A continual learning survey: Defying forgetting in classification tasks.  IEEE transactions on pattern analysis and machine intelligence, 44(7):3366–3385, 2021.
  * [14] Lee A. Feldkamp, Danil V. Prokhorov, Charles F. Eagen, and Fumin Yuan.  Enhanced Multi-Stream Kalman Filter Training for Recurrent Networks, pages 29–53.  Springer US, Boston, MA, 1998.
  * [15] Robert M. French.  Catastrophic forgetting in connectionist networks.  Trends in Cognitive Sciences, 3(4):128–135, 1999.
  * [16] Yasir Ghunaim, Adel Bibi, Kumail Alhamoud, Motasem Alfarra, Hasan Abed Al Kader Hammoud, Ameya Prabhu, Philip HS Torr, and Bernard Ghanem.  Real-time evaluation in online continual learning: A new paradigm.  arXiv preprint arXiv:2302.01047, 2023.
  * [17] Peter Grunwald.  A tutorial introduction to the minimum description length principle, 2004\.
  * [18] Raia Hadsell, Dushyant Rao, Andrei A. Rusu, and Razvan Pascanu.  Embracing change: Continual learning in deep neural networks.  Trends in Cognitive Sciences, 24(12):1028–1040, 2020.
  * [19] Raia Hadsell, Dushyant Rao, Andrei A Rusu, and Razvan Pascanu.  Embracing change: Continual learning in deep neural networks.  Trends in cognitive sciences, 24(12):1028–1040, 2020.
  * [20] Tyler L Hayes and Christopher Kanan.  Online continual learning for embedded devices.  arXiv preprint arXiv:2203.10681, 2022.
  * [21] Elad Hazan.  Introduction to Online Convex Optimization.  Foundations and Trends in Optimization. Now, Boston, 2017.
  * [22] Huiyi Hu, Ang Li, Daniele Calandriello, and Dilan Gorur.  One pass imagenet, 2021.
  * [23] Xisen Jin, Junyi Du, and Xiang Ren.  Gradient based memory editing for task-free continual learning.  In 4th Lifelong Machine Learning Workshop at ICML 2020, 2020.
  * [24] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, et al.  Overcoming catastrophic forgetting in neural networks.  Proceedings of the national academy of sciences, 114(13):3521–3526, 2017.
  * [25] Mark Kozdoba, Jakub Marecek, Tigran Tchrakian, and Shie Mannor.  On-line learning of linear dynamical systems: Exponential forgetting in kalman filters.  In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019.
  * [26] Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical Report 0, University of Toronto, Toronto, Ontario, 2009.
  * [27] Soochan Lee, Junsoo Ha, Dongsu Zhang, and Gunhee Kim.  A neural dirichlet process mixture model for task-free continual learning, 2020.
  * [28] Zhizhong Li and Derek Hoiem.  Learning without forgetting.  IEEE transactions on pattern analysis and machine intelligence, 40(12):2935–2947, 2017.
  * [29] Zhiqiu Lin, Jia Shi, Deepak Pathak, and Deva Ramanan.  The clear benchmark: Continual learning on real-world imagery.  In Thirty-fifth Conference on Neural Information Processing Systems Datasets and Benchmarks Track (Round 2), 2021.
  * [30] David Lopez-Paz and Marc’Aurelio Ranzato.  Gradient episodic memory for continual learning.  Advances in neural information processing systems, 30, 2017.
  * [31] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner.  Online continual learning in image classification: An empirical survey.  Neurocomputing, 469:28–51, 2022.
  * [32] Arun Mallya and Svetlana Lazebnik.  Packnet: Adding multiple tasks to a single network by iterative pruning.  In Proceedings of the IEEE conference on Computer Vision and Pattern Recognition, pages 7765–7773, 2018.
  * [33] Michael McCloskey and Neal J. Cohen.  Catastrophic interference in connectionist networks: The sequential learning problem.  volume 24 of Psychology of Learning and Motivation, pages 109–165. Academic Press, 1989.
  * [34] German I Parisi, Ronald Kemker, Jose L Part, Christopher Kanan, and Stefan Wermter.  Continual lifelong learning with neural networks: A review.  Neural networks, 113:54–71, 2019.
  * [35] Massimiliano Patacchiola, Jack Turner, Elliot J. Crowley, Michael Boyle, and Amos J. Storkey.  Bayesian meta-learning for the few-shot setting via deep kernels.  In Advances in Neural Information Processing Systems, 2020.
  * [36] Jan Poland and Marcus Hutter.  Asymptotics of discrete mdl for online prediction.  IEEE Transactions on Information Theory, 51(11):3780–3795, 2005\.
  * [37] G.V. Puskorius and L.A. Feldkamp.  Neurocontrol of nonlinear dynamical systems with kalman filter trained recurrent networks.  IEEE Transactions on Neural Networks, 5(2):279–297, 1994.
  * [38] Carl Edward Rasmussen and Christopher KI Williams.  Gaussian Processes for Machine Learning.  MIT Press, 2006.
  * [39] Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell.  Progressive neural networks.  arXiv preprint arXiv:1606.04671, 2016.
  * [40] Gobinda Saha, Isha Garg, and Kaushik Roy.  Gradient projection memory for continual learning.  arXiv preprint arXiv:2103.09762, 2021.
  * [41] Shai Shalev-Shwartz.  Online learning and online convex optimization.  Found. Trends Mach. Learn., 4(2):107–194, feb 2012.
  * [42] Hanul Shin, Jung Kwon Lee, Jaehong Kim, and Jiwon Kim.  Continual learning with deep generative replay.  Advances in neural information processing systems, 30, 2017.
  * [43] Sharad Singhal and Lance Wu.  Training multilayer perceptrons with the extended kalman algorithm.  In D. Touretzky, editor, Advances in Neural Information Processing Systems, volume 1. Morgan-Kaufmann, 1988.
  * [44] Shengyang Sun, Daniele Calandriello, Huiyi Hu, Ang Li, and Michalis Titsias.  Information-theoretic online memory selection for continual learning.  arXiv preprint arXiv:2204.04763, 2022.
  * [45] Simo Särkkä.  Bayesian Filtering and Smoothing.  Institute of Mathematical Statistics Textbooks. Cambridge University Press, 2013.
  * [46] Bart Thomee, David A Shamma, Gerald Friedland, Benjamin Elizalde, Karl Ni, Douglas Poland, Damian Borth, and Li-Jia Li.  Yfcc100m: The new data in multimedia research.  Communications of the ACM, 59(2):64–73, 2016.
  * [47] Anastasios Tsiamis and George Pappas.  Online learning of the kalman filter with logarithmic regret, 2020.
  * [48] Zifeng Wang, Zizhao Zhang, Chen-Yu Lee, Han Zhang, Ruoxi Sun, Xiaoqi Ren, Guolong Su, Vincent Perot, Jennifer Dy, and Tomas Pfister.  Learning to prompt for continual learning.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 139–149, 2022.
  * [49] Friedemann Zenke, Ben Poole, and Surya Ganguli.  Continual learning through synaptic intelligence.  In International conference on machine learning, pages 3987–3995. PMLR, 2017.
  * [50] Junting Zhang, Jie Zhang, Shalini Ghosh, Dawei Li, Serafettin Tasci, Larry Heck, Heming Zhang, and C-C Jay Kuo.  Class-incremental learning via deep model consolidation.  In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, pages 1131–1140, 2020.

##  Appendix A Connection with online Bayesian linear regression

When the forgetting coefficient is $\gamma_{n}=1$ for all $n$, the
stochasticity in the transitions is removed since the parameter transition
density becomes a point mass, i.e. $p(w_{n}|w_{n-1})=\delta(w_{n}-w_{n-1})$.
Then, the Kalman filter reduces to updating the Gaussian posterior density
$p(w|y_{1:n})=\mathcal{N}(w|m_{n},A_{n})$ where

$m_{n}=m_{n-1}+\frac{A_{n-1}\phi_{n}}{\sigma^{2}+\phi_{n}^{\top}A_{n-1}\phi_{n}}(y_{n}-\phi_{n}^{\top}m_{n-1}),\
\ \
A_{n}=A_{n-1}-\frac{A_{n-1}\phi_{n}\phi_{n}^{\top}A_{n-1}}{\sigma^{2}+\phi_{n}^{\top}A_{n-1}\phi_{n}},$
(15)

with the initial conditions $m_{0}=0$ and $A_{0}=\sigma_{w}^{2}I$. We see that
these recursions compute exactly in an efficient $O(m^{2})$ time the standard
Bayesian linear regression posterior given by
$p(w|y_{1:n})=\mathcal{N}(w|A_{n}\sigma^{-2}\sum_{i=1}^{n}\phi_{i}y_{i},A_{n})$,
with
$A_{n}=\left(\sigma^{-2}\sum_{i=1}^{n}\phi_{i}\phi_{i}^{\top}+\sigma_{w}^{-2}I\right)^{-1}$,
and where the connection with the online updates can be seen by applying the
Woodbury matrix identity. Obtaining the online Bayesian linear regression
recursion as a special of a Kalman filter is well known in the literature; see
for example Section 3.2 in the book of [45].

##  Appendix B Online updating the forgetting coefficient $\gamma_{n}$ for
regression

Learning online $\gamma_{n}$ for the regression case is simpler than in
classification since now the predictive density is a tractable Gaussian given
by (6). Thus, given that we parametrize $\gamma_{n}=\exp(-0.5\delta_{n})$,
with $\delta_{n}\geq 0$, the update for $\delta_{n}$ is written as

$\delta_{n}\leftarrow\delta_{n}+\rho_{n}\nabla_{\delta_{n}}\log\mathcal{N}(y_{n}|\phi_{n}^{\top}m_{n}^{-},\phi_{n}^{\top}A_{n}^{-}\phi_{n}+\sigma^{2}).$
(16)

The dependence of the log density on $\delta_{n}$ is through the parameters
$(m_{n}^{-},A_{n}^{-})$ given by (4) while the parameters $(m_{n-1},A_{n-1})$
of the posterior up to time $n-1$ are taken as constants.

##  Appendix C Further details about the time series example

We generated the time series dataset consisted of $3058$ observations
sequentially by using $8$ segments with mean values
$\\{1.3,1.0,1.3,0.95,0.6,0.25,0.8,0.5\\}$ and where the change-points between
these segments occurred (randomly) at the following $7$ time steps
$\\{451,709,958,1547,2147,2769,2957\\}$. To obtain each observed $y_{n}$ we
added Gaussian noise with variance $0.01$.

For these time series data we applied a modification of the Kalman updates so
that all updates remain the same, except for the update of the parameter
$m_{n}^{-}$ which now does not shrink to zero and it has the form

$m_{n}^{-}=m_{n-1},\ \ \ \text{(while before was}\
m_{n}^{-}=\gamma_{n}m_{n-1}).$

This is appropriate in this case because shrinking the predictive posterior
mean to zero by multiplying it by $\gamma_{n}\leq 1$ is a very strong prior
assumption that $w_{n}$ has zero mean which does not hold, since the time
series data can have arbitrary values away from zero. A more formal
justification of the above is that the Markov dynamics have now the form
$p(w_{0})=\mathcal{N}(w_{0}|0,\sigma_{w}^{2}I)$ and
$p(w_{n}|w_{n-1})=\mathcal{N}(w_{n}|(1-\gamma_{n})\mu_{n-1}+\gamma_{n}w_{n-1},\sigma_{w}^{2}(1-\gamma_{n}^{2})I)$
and each mean parameter $\mu_{n-1}$ when we transit from time step $n-1$ to
$n$ is found by empirical Bayes so that $\mu_{n-1}=m_{n-1}$ and where
$m_{n-1}$ is the mean of $p(w_{n-1}|y_{1:n-1})$.

The hypermarameters in the experiment were set to the following values:
$\sigma_{w}^{2}=0.01,\sigma^{2}=0.05$ while $\delta_{0}$ was intitialized to
$0.0$ (so that $\gamma_{0}=1.0$) and then updated at each step by performing
SGD steps with learning rate equal to $1.0$.

Figure 1 in the main paper shows the results when $\gamma_{n}$ is updated
online. For comparison, in Figure 4 we show the online predictions for the
case of having fixed $\gamma_{n}=1$ for any $n$, so that the ability to model
non-stationarity is removed. Clearly, when not learning $\gamma_{n}$ the model
is not able to adjust to non-stationarity.

---
Figure 4: Online prediction on the artificial time series example by applying
the Kalman filter model with fixed $\gamma_{n}=1$.

##  Appendix D Experimental details and hyperparameters selection

###  D.1 Hyperparameters selection

For hyperparameters we do the grid search over ranges. The hyperparameters for
methods are selected by choosing the variant with highest cumulative log
probabilities following MDL principle from [7]. When finetuning backbone
together with learning calibration parameter $\alpha$, we considered a
different relative scaling $\beta$ of the gradients of the backbone compared
to $\alpha$ \- meaning that if we use learning rate $\eta$ for $\alpha$, the
learning rate for backbone is $\beta*\eta$. In case where we learned $\gamma$,
we initialized $\gamma$ at $\gamma_{init}$ which is also a hyper-parameter.
For each of the method, we optimized the hyper-parameters separately. The
hyper-parameters and the considered values are given in the Table 2.

Table 2: Hyper-parameters and considered values. Hyperparameter | Considered values
---|---
Learning rate for backbone and $\alpha$, $\eta$ | [0.1, 0.01, 0.001, 0.0005, 0.0001]
Learning rate for $\gamma$, $\eta_{\gamma}$ | [0.5, 0.1, 0.01, 0.001]
Relative backbone-$\alpha$ gradient scaling, $\beta$ | [0.01, 0.1, 1., 10., 100.0]
Initial $\gamma_{init}$ | [0.9, 0.99, 0.999, 1.0]

###  D.2 Finetuning protocol

The algorithm 1 describes Kalman filter online learning where the learning
happens for each data point. We adapt this algorithm for chunk-based learning
in the following way. When we receive the chunk of data of certain size, we
use the available Kalman statistics in order to calculate predictive log-
probabilities (see Section 2.1.2) for each data point in the chunk
independently. After that, we do the gradient update on the backbone and
$\alpha$, leading us new backbone parameters and new $\alpha$. After that, we
re-compute the features on the same chunk of data and we do Kalman recursion
on this chunk going through it sequentially. This latter process only involves
updating statistics and $\gamma_{n}$ and doesn’t involve backbone or $\alpha$
finetuning. When we do this Kalman recursion, we consider two options on how
to apply Markov transition. In the first option, Always Markov, we apply
Markov transition for every data point during Kalman recursion. In the second
option, Last Step Markov, we only do Markov transition on the last point in
the chunk. The difference basically lies in what we consider a non-stationary
data point. In case of Always Markov, it is each data point in the chunk. In
case of Last Step Markov, it is the whole chunk. We found that for different
scenarios, different strategies led to different results.

###  D.3 Additional per-benchmark parameters

On top of the hyper-parameters which we selected for each of the baseline
separately, we also found that there was a group of hyper-parameters which
generally provided consistently good results for all the baselines for each
benchmark. These parameters are the following:

  * •

Transition type: Always Markov or Last Step Markov

  * •

Bias in features: Whether we add bias to the features or not

  * •

Features normalization: Whether we normalize features vector, i.e., whether we
divide it by the square root of its dimensionality.

  * •

Optimization algorithm: plain SGD or Adam with weight decay ($\lambda$)

These parameters were found empirically and similarly chosen via MDL
principle. The table 3 gives the summary.

Table 3: Per benchmark parameters. Benchmark | Transition type | Use Bias | Use normalization | Optimization alg.
---|---|---|---|---
Stationary CIFAR-100 | Last Step Markov | No | Yes | SGD
Non-Stationary CIFAR-100 | Always Markov | Yes | Yes | SGD
CLOC with pretrained backbone | Always Markov | No | No | SGD
CLOC from scratch | Last Step Markov | No | No |  AdamW ($\lambda=10^{-4}$)

###  D.4 CIFAR-100 experiments

In both cases of CIFAR-100 experiments, we follow protocol described in [16].
We use ResNet-18 as backbone model and SGD as learning algorithm. We split
data into chunks of size $10$. In some cases, we allow a replay strategy
suggested in [16], where we keep a memory of size $100$ containing most
recently seen examples. Then, for each learning iteration, we sample a chunk
of size $10$ from memory and append it to the right of the current chunk,
creating a chunk of size $20$.

###  D.5 CLOC experiments

Similar to [16] and [7], we considered ResNet-50 as backbone and chunk size
equal to $128$. Empirically, we found that SGD optimization worked much better
for pre-trained model whereas Adam with weight decay ($\lambda=10^{-4}$) was
working much better for learning from scratch. Moreover, we also found that
when learning from scratch, it worked much better if we used Last Step Markov
transition (see Appendix D.2). For pre-trained model, it worked better use
Always Markov transition (see Appendix D.2).

For baselines, we considered Online SGD baseline from [7], with EMA parameter
equal to 1 for fair comparison. The case of online SGD with replay corresponds
to using 8 replay streams on top of the learning stream which make sure that
the data distribution in the replay buffer is well behaved (see [7] for more
details).

##  Appendix E The effect of calibration on online classification

In Section 2.1.2, we describe a procedure to finetune the model backbone
$\phi$ as well as to finetune the parameter $\alpha$ which affects the
predictive log probability. This parameter $\alpha$ essentially allows us to
calibrate the predictive log probabilities. The effect of this calibration is
shown in Figure 5 for CLOC dataset and in Figure 6 for non-stationary
CIFAR-100. In both cases, we use the version of Kalman filter which finetunes
the backbone and learns $\gamma$. We see a very drastic positive effect of
calibration – calibrated log probabilities become much higher. Related to the
discussion of prequential MDL [7], it essentially allows to have a model with
lower description length. Moreover, since we use predictive log probability as
a learning signal for backbone, the calibration allows to tune the scaling of
this term.

Figure 5: CLOC log probabilitites for Kalman filter with finetuned backbone
and finetuned delta. We show the data (black dots) and the predicted mean and
uncertainty (orange lines) over $y_{n}$ (as data arrive sequentially from left
to right and we perform online next time step prediction). Figure 6: Non-
stationary CIFAR-100 log probabilitites for Kalman filter with finetuned
backbone and finetuned $\delta$.

##  Appendix F Chunk size ablation

In this section we provide the ablation of the impact of the chunk size on the
average online accuracy. We provide it for CIFAR-100 as well as for CLOC. We
use the Kalman filter variant with learned $\gamma$ with either fixed or
finetuned backbone. The results are given in Figure 7.

Figure 7: Chunk size ablation for CIFAR-100.