# Representation Extraction and Deep Neural Recommendation for Collaborative
Filtering

Arash Khoeini<EMAIL_ADDRESS>Saman Haratizadeh<EMAIL_ADDRESS>Ehsan
Hoseinzade<EMAIL_ADDRESS>Faculty of New Sciences and Technologies,
University of Tehran, North Kargar Street, 1439957131 Tehran, Iran  School of
Computing Science, Simon Fraser University, 8888 University Drive, Burnaby,
Canada

###### Abstract

Many Deep Learning approaches solve complicated classification and regression
problems by hierarchically constructing complex features from the raw input
data. Although a few works have investigated the application of deep neural
networks in recommendation domain, they mostly extract entity features by
exploiting unstructured auxiliary data such as visual and textual information,
and when it comes to using user-item rating matrix, feature extraction is done
by using matrix factorization. As matrix factorization has some limitations,
some works have been done to replace it with deep neural network. but these
works either need to exploit unstructured data such item’s reviews or images,
or are specially designed to use implicit data and don’t take user-item rating
matrix into account. In this paper, we investigate the usage of novel
representation learning algorithms to extract users and items representations
from rating matrix, and offer a deep neural network for Collaborative
Filtering. Our proposed approach is a modular algorithm consisted of two main
phases: REpresentation eXtraction and a deep neural NETwork (RexNet). Using
two joint and parallel neural networks in RexNet enables it to extract a
hierarchy of features for each entity in order to predict the degree of
interest of users to items. The resulted predictions are then used for the
final recommendation. Unlike other deep learning recommendation approaches,
RexNet is not dependent to unstructured auxiliary data such as visual and
textual information, instead, it uses only the user-item rate matrix as its
input. We evaluated RexNet in an extensive set of experiments against state of
the art recommendation methods. The results show that RexNet significantly
outperforms the baseline algorithms in a variety of data sets with different
degrees of density.

###### keywords:

Recommender System , Representation Learning , Deep Learning , Collaborative
Ranking

##  1 Introduction

The massive amount of available products in e-commerce websites had made
Recommendation System a crucial need for those businesses. Collaborative
Filtering is the dominant approach for recommendation when the sole available
data is the user-item interactions matrix. The core idea of CF methods is to
estimate the favorite items for a specific target user, based on previous
implicit or explicit evaluations of the users about items of the system.

A recent approach in recommendation systems is deep Learning. Deep learning
([1]) methods have been extremely successful in different research areas like
image processing ([2]), natural language processing ([3]), face detection
([4]) and stock market prediction ([5], [6]). Inspired by these successes of
deep learning algorithms in mentioned domains, some researchers have tried to
introduce novel deep learning approaches for recommendation systems. These
methods use deep models such as deep neural networks to map the available data
about users and items to a prediction about unknown user-item relations. For
example, some approaches use reviews written by users about item to capture
representations for those entities through deep models ([7] , [8]). Some other
approaches integrate different data sources e.g. images, texts, etc to capture
representations ([9] , [10]) to estimate user preferences. Although there have
been various successful works among these attempts, they heavily rely on using
unstructured content data, such as reviews or images, mainly because the deep
models have already been designed to handle such sort of data. This makes
these approaches inapplicable when the only available source of information is
user-item rating matrix[11].

Deep Neural Networks are efficient tools for automatic feature extraction
probably due to their ability of extracting features hierarchically [2]. In
this hierarchical feature extraction approach, each layer aggregates the
features that are extracted by its previous layers into a higher level
features. These neural networks usually have a tower architecture, where there
is fewer number of neurons in top layers.

In this paper we introduce Deep Joint Feature eXtraction (RexNet), a novel
recommendation approach which is composed of three main training steps. First,
it transform the user-item matrix into sentence-like sequences. Each sequence
comprises all the items that a user has shown interest to. In the second step,
RexNet uses the sequences of last step to extract representations for items
and users using a representation learning method, such as Skip-gram ([12]) or
GloVe ([13]). Although Skip-gram has already been adopted for content-based
representation learning in recommender systems, here we suggest to apply GloVe
for entity representation learning from user-item data. For the third step, a
deep feed forward neural network structure is introduced which is composed of
two parallel deep neural networks that are connected through their output
neuron. Each of these neural networks are responsible for implicitly
extracting features for either users or items. They receive the captured
representations of a user-item pair from previous step, and are trained to
jointly predict the unknown relation between users and items through their
common output neuron. Based on these predictions the system can sort the items
for any target user and recommend the top rated items to that user.

The contributions of this work can be summarized as below:

  * 1.

suggesting a new model-based framework for recommendation in collaborative
filtering domain that outperforms other state of the art approaches.

  * 2.

Suggesting a new approach for using GloVe and SkipGram, to extract vector
representations for users and items when the sole available information is the
user-item relation matrix.

  * 3.

Proposing a special deep neural network architecture that uses the extracted
vectors for each user/item pair, to implicitly extract a hierarchy of features
for them and then predict the unknown interest of the user about the item.

##  2 Related Work

Collaborative Filtering is the most successful and applied approach in
Recommendation Systems. Collaborative Filtering methods use users previous
interactions to find similar users or items to recommend a target item to the
target user, and there are various approaches that can be used to reach this
goal. For instance, matrix factorization methods ([14], [15], [16], [17],
[18], [19]) factorize user-item interaction matrix to estimate the unknown
user-item interactions, or graph-based approaches ([20], [21], [22], [23],
[24]) use entities relation networks to find similar users and items.

One of first attempts on using neural networks in recommendation area was done
by Geoffery Hinton et. al. in 2007 ([25]). In this work authors used
Restricted Boltzmann Machine (RBM) to model users rating of movies. They
proposed an efficient inference procedure that could outperform SVD, which was
the dominant method of Collaborative Filtering. A more recent usage of RBM in
improving recommendation systems is [26], where authors used RBM to learn
representation for users and preferences. Another attempt that used deep
neural network in recommendation area was done by Sander Deileman et. al.[27]
where they trained a Convolutional Neural Network(CNN) to recommend musics to
users. They trained the CNN to predict the music latent factors from its audio
signal. This attempt is one of the examples of training a deep model by
content information to improve recommendations. Another example is [7] in
which authors used items reviews to train to parallel CNN. One of these
networks is in charge for modeling latent factors of users and another one for
items. These two networks were connected in a shared fully connected layer and
in the shared layer a Factorization Machine were used to predict users unknown
rankings. Recurrent Neural Networks are also used in the domain of
recommendation systems. For example, [28] applies RNNs to session-based
recommender systems, or [29] uses LSTM networks ([30]) for the the task of
predicting downloads in academic search.

As deep neural networks are very powerful in extracting features from
unstructured data, some recent methods have designed modular models which
combine different source of information such as text, image and audio. In one
of these works [9] authors propose an architecture which ends in a fusion
step. This fusion step helps the model to keep a modular architecture where
each module is trained to use a different kind of content information, such as
images or texts. The other example is [10] where authors use different
auxiliary information to solve the sparsity problem, which is one main
challenge in collaborative filtering. They adopt a heterogeneous network
embedding method, termed as TransR, to extract items’ structural
representations by considering the heterogeneity of both nodes and
relationships. They apply stacked denoising auto-encoders and stacked
convolutional auto-encoders, which are two types of deep learning based
embedding techniques, to extract items’ textual representations and visual
representations, respectively.

Although the mentioned attempts have been successful in using auxiliary
information, they are inapplicable when the only available source of
information is user-item rating matrix. Some other works has been done to use
neural networks in these situations, when all we know about users and item is
just a rating matrix. A notable approach is NeuMF ([31]) where authors propose
a neural network to generalize matrix factorization on implicit data. An
example work of using neural network on rating data is [32], were authors
propose AutoRec, which is a novel autoencoder framework for collaborative
filtering. AutoRec can be user-based or item-based. In each situation it uses
an Auto Encoder to learn compact representations of users or items. AutoRect
then uses these compact representations to estimate user or item full vector
of rating estimations.

Another example of learning representation to do recommendation is [33] where
items are mapped to a dense vector space using Skip-gram with Negative
Sampling and then a recommendation is done by a nearest-neighbor approach.

Skip-gram with Negative Sampling and Glove are two main Representation
Learning approaches in Natural Language Processing. As we will use these
methods in our work, we will explain both methods briefly in the following sub
sections.

###  2.1 SkipGram with Negative Sampling

Figure 1: The Skip-gram model architecture. The training objective is to learn
word vector representations that are good at predicting the nearby words [12]

Skip-gram is a Word2Vec tool which was introduced in [12]. Skip-gram
architecture is a neural network with a hidden layer which tries to maximize
function 1.

$\frac{1}{T}\sum^{T}_{t=1}\sum_{-c\leq j\leq c,j\neq 0}logp(w_{t+j}|w_{j})$
(1)

where c is the size of training context. Skip-gram defines $p(w_{t+j}|w_{j})$
using the softmax function:

$p(w_{O}|w_{I})=\frac{exp(v^{\prime
T}_{w_{O}}v_{w_{I}})}{\sum^{W}_{w=1}exp(v^{\prime T}_{w}v_{w_{I}})}$ (2)

where $v_{w}$ and $v^{\prime}_{w}$ are the input and output vector
representations of w and W is the the size of vocabulary. Since this approach
is impractical for very large vocabularies, Negative Sampling is proposed in
original paper. Skip-gram with negative sampling has the objective function 3
which is used to replace every $logP(w_{O}|w_{I})$ term.

$log\sigma(v^{\prime T}_{w_{O}}v_{W_{I}})+\sum^{k}_{i=1}E_{w_{i}\sim
P_{n}(w)}[log\sigma(-v^{\prime T}_{w_{i}}v_{w_{I}})]$ (3)

Where k is number of negative samples, $\sigma$ is the Sigmoid function and
$p(w)$ is a probability distribution for negative samples.

Skip-gram slides a fixed-size window over corpus sentences and tries to
maximize equation 1 on each window location. After training, the matrix $W$
will contain captured representation for words in vocabulary based on their
co-occurrences. Using a fixed-size window size seems reasonable in Natural
Language Processing tasks where the aim is to capture word similarities based
on appearance of words in a word sequence such as a sentence or a paragraph.
However it might limit the model from utilizing some co-occurrences in
Collaborative Filtering systems in which usually such a sequential structure
does not exist.

###  2.2 GloVe

Although GloVe captures word representations for words as Skip-gram, it uses a
different approach to achieve this goal. GloVe first scans the whole corpus of
sentences and builds a matrix X, where $X_{ij}$ is the number of times word
$i$ has been seen in the context of word $j$. Context is defined in a fixed-
size window of words here and its size is a hyper parameter of the algorithm.
After building matrix X, GloVe learns word vectors by minimizing the following
cost function:

$J=\sum^{V}_{i,j=1}f(X_{ij})(w^{T}_{i}\tilde{w}_{j}+b_{i}+\tilde{b}_{j}-\log
X_{ij})^{2}$ (4)

where $f(x_{ij})$ is defined as follows:

$f(x)=\left\\{\begin{array}[]{ll}(x/x_{max})^{\alpha}&\mbox{if }x<x_{max}\\\
1&\mbox{if }otherwise\end{array}\right.$ (5)

Although GloVe uses fixed-size window to build matrix $X$, it gives the
flexibility to change the definition of $X$ as long as it satisfies some
constrains ( [13] ). In our method, we will use GloVe to capture base
representations for users and items, which will be fed to our deep neural
network.

##  3 RexNet

In the big picture, RexNet first captures dense representations of users and
items. Then the captured representations are used to train a neural network
for user-item relevance prediction.

To capture dense representations, we can use GloVe or Skip-gram with Negative
Sampling (SGNS). As we mentioned before, these methods are used in Natural
Language Processing tasks, and they use massive sets of sentences as input. So
in order to use any of these methods, first we need to build a corpus. One way
of building that is defining sentences from user profiles. For example, if a
user has rated twelve items, this user will add a sentence of size twelve to
our corpus, where each word represents an item. The problem with this method
is that the sentence structure will not distinguish low-rated items form high-
rated ones. To address this problem, we allow each item appear in the sentence
several times. The number of appearance is equal to the rate given to that
item by the corresponding user.

(a) An example of user-item rating matrix

(b) Extracted sentences from user-item rating matrix

Figure 2(a) shows an example of a user-item rating matrix and figure 2(b)
shows the extracted sentences of that matrix.

Another concern about the transforming the profiles to sentences is that
usually there is no sequence among items in a user profile while a sentence is
naturally a sequence of words. To avoid any biases that this may cause, we use
a shuffled version of the resulted sentences.

After building a corpus of items, we can use this corpus to train GloVe or
SGNS and capture dense representations for users. Since the prediction model
needs users’ representations as well, we need a way to derive user
representations. One interesting characteristics of representations learned by
GloVe or SNGS, is that they allow vector-oriented reasoning based on the
offset between entities. For example when we are dealing with word entities,
the male/female relationship is automatically learned, and with the induced
vector representations, ”King - Man + Woman” results in a vector very close to
”Queen” [34]. Using this view, we argue that user item relationship is
automatically learned when we use these techniques in Collaborative Filtering,
and a user’s taste can be define by all the items they have rated. So a user’s
representation can be defined as equation 6.

$u_{i}=\sum_{k\in M_{i}}(r_{i,k}-\lambda_{i})v_{k},$ (6)

where $M_{i}$ is the set of items that user $i$ has rated. $r_{i,k}$ is the
rate user $i$ has given to item $k$ and $\lambda_{i}$ is the average of
ratings given by user $i$.

As the third module, we introduce a deep and parallel feed forward neural
network to extract hierarchical features of items and users. Using neural
networks for hierarchical feature extraction have shown massive success in
different areas of deep learning. These neural networks usually have a tower
structure, where bottom layers are the widest and each successive layer has
smaller number of neurons. The initial wider layers of the neural network
extract more general and basic features while the higher layers with small
number of hidden units extract more abstract features [35].

Figure 3: Parallel Feed Forward Neural Network: the upper one is the user
network and lower one is the item network. These two networks are connected in
the shared layer.

The architecture of the proposed neural network is presented in figure 4. As
we can see, this neural network consists of two parallel deep multi-layer
perceptrons which are connected in one shared output neuron. The aim of
choosing this architecture is to give our model the opportunity to extract
features for users and items separately. As we can see in figure 4, the upper
module of the neural network receives the item’s base representations in its
input and extract items’ features in several layers. The user’s module does
the same thing for users. The number of layers and size of neurons in each
layer are hyper parameters of the model and depend on the properties of the
available training data. Being connected in the output neuron, enables the
model to back-propagate the same final error through the layers of both
modules. Using this approach of learning forces both modules to extract
features in a way that the final interaction yield the user preference for the
item.

To train this neural network, we feed it with a user and an item base
representations that are captured as we explained before. The target value
which the neural network should learn to estimate is the preference level of
the user about the item. We have defined the preference as the rate given by
the user to that item minus the average of ratings given by the user. For
example if a user with average rating of 3.5 has rated an item 4, the
preference will be 0.5 and our neural network will learn to estimate it.
Output neuron uses linear combination of final high level features of users
and items to estimate the preference. If we consider $a^{u}_{n}$ the output
vector of the last hidden layer in user’s neural network (user’s abstract
feature vector), and $a^{i}_{n}$ the output vector of the last hidden layer in
item’s neural network (item’s abstract feature vector), the final output will
be calculated as function 7

$f(u_{i},v_{j})=V\left[\begin{array}[]{c}a^{u}_{n}\\\
a^{i}_{n}\end{array}\right]+b_{n+1}$ (7)

where $V$ is the weight vector of the output neuron and $a^{i}_{n}$ and
$a^{u}_{n}$ are defined as functions 8 and 9 respectively. In these functions,
$u_{j}$ denotes the captured representation for user $j$ and $v_{k}$ denotes
the captured representation for item $k$.

$a^{n}_{u}=ReLU(W^{u}_{n}ReLU(W^{u}_{n-1}(...ReLU(W^{u}_{1}u_{j}+b^{u}_{1})...)+b^{u}_{n-1})+b^{u}_{n})$
(8)

$a^{n}_{i}=ReLU(W^{i}_{n}ReLU(W^{i}_{n-1}(...ReLU(W^{i}_{1}v_{k}+b^{i}_{1})...)+b^{i}_{n-1})+b^{i}_{n})$
(9)

Where $W^{u}_{j}$ and $W^{i}_{j}$ are weights of jth layer of user’s and
item’s neural network respectively. Biases of these layers are also indicated
by $b^{u}_{j}$ and $b^{i}_{j}$.

Figure 4 illustrates whole RexNet structure. As we can see, the algorithm’s
input is only user-item rating matrix. As we explained earlier, first this
matrix is turned to a sentence-like sequences and then a deep representation
learning method is used to capture item representations. After that, these
representations and user-item matrix are used to capture users’
representations based on equation 6, and finally all these representations are
used to feed and train a deep joint neural network. This procedure is also
explained more formally by pseudo-codes. Pseudo-code 2, 3 and 4 show the
procedure of three modules respectively, and algorithm 1 is the main function
of RexNet that uses all other modules.

Figure 4: RexNet

Input: user-item rating matrix

Output: trained joint neural network

// build corpus

sentences $\leftarrow$ build-corpus(user-item-ratings)

$\textit{user-averages}\leftarrow\text{calculate-average({user-item-matrix})}$

// capture users’ and item’s representations

item-representations , user-representations $\leftarrow$ capture-
representations(sentences, user-averages)

// train deep joint neural network

neural-model $\leftarrow$ train-deep-neural-network(user-item-rating, item-
representations, user-representations, user-averages )

ALGORITHM 1 RexNet main

Input: user-item-rating matrix

Output: corpus

Function  _build-corpus(_user-item-rating_)_:

$\textit{sentences}\leftarrow initialize-list(size=\text{number-of-users})$

foreach  _rate[user,item] $\in$ user-item-rating_ do

$sentences[user].append(\text{repeat item {rate} times})$

end foreach

return sentences

ALGORITHM 2 RexNet Module 1: build corpus

Input: sentences, user-averages

Output: users’ and items’ representations

Function  _capture-representations(_user-item-rating, user-averages_)_:

// using SGNS or GloVe as representation learning algorithm

$\textit{item-representations}\leftarrow\text{representations-
learning({sentences})}$

// infer user representations using equation 6

foreach  _user $\in$ users_ do

$\textit{user-rated-movies , rates}\leftarrow\text{get-movies-and-
rates({user})}$

$\textit{user-vector}=(\textit{rates}-\textit{user-
averages}[\textit{user}])*\textit{item-representations}[\textit{user-rated-
movies}]$ $\textit{user-representations}.append(\textit{user-vector)}$

end foreach

return item-representations, user-representations

ALGORITHM 3 RexNet Module 2: capture representations

Input: user’s and items’ representations, user-averages

Output: deep joint model

Function  _train-deep-neural-network(_user-item-rating, item-representations,
user-representations, user-averages_)_:

$\textit{neural-network-data}\leftarrow\text{initialize-list()}$

foreach  _rate[user,item] $\in$ user-item-rating_ do

neural-network-data.append((user-representations[user], item-
representations[item], user-item-matrix[user,item] - user-averages[user]))

end foreach

// train joint neural network

$\textit{neural-model}\leftarrow\text{build-and-train-deep-neural-
network({neural-network-data})}$

return trained-deep-model

ALGORITHM 4 RexNet Module 3: train deep joint neural network

##  4 Experiments

We compared the performance of RexNet against different methods of
Collaborative Filtering on two datasets with different degrees of sparsity:
MovieLens 100k and MovieLens 1M datasets. We used the rating data of these
datasets and ignored timestamps. MovieLens-100K contains 100 thousands ratings
of 943 users with at least 20 rated movies for each user and there are 1682
distinct movies in it. MoveiLens-1M contains 1 Million ratings by 6040 users
with at least 20 rated movies for each user. There are 3952 distinct movies in
MoveiLens-1M.

For each user, a fixed number (UPL) of movies that he/she has rated are
selected for training and the remaining ratings are left for the testing
process. A user’s profile size is the number of items in his/her train set.
Different sizes of user profiles are used to compare our method with baseline
methods. We used UPL sizes of 10, 20 and 50 in our experiments.

###  4.1 Parameter Setting

For the representation learning, we fixed the representation size to 100 and
the window size to 25 and did not explore other sizes as our main focus was in
the performance of the neural network module. We chose to use four hidden
layers for each neural networks with 30, 20, 10, and 5 neurons for the first
through the last layer. All hidden layers use ReLU activation function and the
output neuron has no activation function.

###  4.2 Evaluation Metric

We have used NDCG for evaluating the performance of the recommendation
algorithms in our experiments. NDCG is a metric for measuring the performance
of rank-based recommender systems, which is used to evaluate top-n
recommendations in the recommendation lists. The more the top-n
recommendations are similar to real top-n items ranked by the user, the NDCG
gets closer to 1. NDCG for top-n items are calculated as below:

$NDCG_{u}=\frac{1}{\beta_{u}}\Sigma^{top-n}_{i=1}\frac{2^{r^{u}_{i}}-1}{log^{i}_{2}+1}$
(10)

,

where $r^{u}_{i}$ is the rate of the $i^{th}$ ranked item and $\beta$ is a
normalizing factor that makes sure that NDCG is between 0 and 1.

##  5 Baseline Algorithms

In our experiments, RexNet is compared with the following model-based
Collaborative Filtering algorithms:

  * 1.

AutoRec [32] that is a neural-network-based algorithm which uses an Auto
Encoder to estimate user ratings.

  * 2.

ListRank [36] which is a ranking-oriented Collaborative Filtering approach.

  * 3.

CofiRank [37], that uses a Matrix Factorization Collaborative Ranking
approach.

  * 4.

PushAtTop [38] which is a Matrix Factorization algorithm which weights
pairwise comparisons according to their position in the total ranking of items
for users. PushAtTop contains three different algorithms: push-inf, push-p,
push-reverse.

###  5.1 Parameter Setting

The input layer of RexNet has 100 neurons in both modules, which means
embedding vectors of users and items also have 100 dimensions. We used three
hidden layers for both user’s and item’s networks where the number of hidden
neurons are 30, 20, 10, and 5 respectively.

We also used a Dropout layer of 0.4 after both hidden layers of size 5. The
number of neurons in the the shared layer is 5 and we have a Dropout layer of
0.2 after it. Output layer contains just one neuron with no activation
function. Neurons in all other layers use Rectified Linear Unit (ReLU) as
activation function. Parameters of the baseline algorithms are set as follows:

  * 1.

In AutoRec, the number of hidden neurons is 500, and the epoch number is 10.

  * 2.

In ListRank, dimension of latent features (d) is 10 and regularization
parameter is set to 0.1.

  * 3.

In CofiRank, publicly available framework is used and the best parameters
reported from [37] is used.

  * 4.

For three different algorithms of PushAtTop, All the optimal algorithms
reported in [38] are used.

###  5.2 Results

Tables 1 and 2 show the NDCG of RexNet and other state-of-art algorithms on
MoveLens 100K and 1M respectively. In each dataset we trained RexNet using the
embeddings captured by GloVe and Skip-gram separately. As we can see in both
tables, RexNet performs better than all the baseline methods in terms of NDCG.

Table 1: Performance comparison in terms of NDCG between RexNet and state of
the art recommendation algorithms on MovieLens 100k dataset.

| UPL = 10 | UPL = 20 | UPL = 50
---|---|---|---
algorithm | NDCG@5 | NDCG@10 | NDCG@5 | NDCG@10 | NDCG@5 | NDCG@10
RexNet (using GloVe) | 0.680 $\pm$ 0.011 | 0.697 $\pm$ 0.005 | 0.690 $\pm$ 0.004 | 0.700 $\pm$ 0.003 | 0.707 $\pm$ 0.004 | 0.709 $\pm$ 0.004
RexNet (using Skip-gram) | 0.673$\pm$0.010 | 0.693$\pm$0.012 | 0.681$\pm$0.010 | 0.691 $\pm$ 0.005 | 0.692 $\pm$ 0.009 | 0.695 $\pm$ 0.007
AutoRec | 0.614 $\pm$ 0.002 | 0.648 $\pm$ 0.002 | 0.644 $\pm$ 0.001 | 0.671 $\pm$ 0.002 | 0.682 $\pm$ 0.003 | 0.692 $\pm$ 0.001
ListRank | 0.672 $\pm$ 0.005 | 0.693 $\pm$ 0.005 | 0.682 $\pm$ 0.006 | 0.691 $\pm$ 0.004 | 0.687 $\pm$ 0.008 | 0.684 $\pm$ 0.004
CofiRank | 0.602 $\pm$ 0.020 | 0.631 $\pm$ 0.013 | 0.603 $\pm$ 0.014 | 0.620 $\pm$ 0.024 | 0.609 $\pm$ 0.010 | 0.616 $\pm$ 0.004
push-inf | 0.611 $\pm$ 0.030 | 0.640 $\pm$ 0.023 | 0.629 $\pm$ 0.015 | 0.647 $\pm$ 0.012 | 0.658 $\pm$ 0.003 | 0.667 $\pm$ 0.002
push-reverse | 0.594 $\pm$ 0.043 | 0.623 $\pm$ 0.033 | 0.621 $\pm$ 0.018 | 0.640 $\pm$ 0.016 | 0.664 $\pm$ 0.012 | 0.668 $\pm$ 0.013
push-p | 0.519 $\pm$ 0.021 | 0.561 $\pm$ 0.015 | 0.580 $\pm$ 0.034 | 0.602 $\pm$ 0.029 | 0.681 $\pm$ 0.012 | 0.679 $\pm$ 0.011

Table 2: Performance comparison in terms of NDCG between RexNet and state of
art recommendation algorithms on MovieLens 1M dataset.

| UPL = 10 | UPL = 20 | UPL = 50
---|---|---|---
algorithm | NDCG@5 | NDCG@10 | NDCG@5 | NDCG@10 | NDCG@5 | NDCG@10
RexNet (using GloVe) | 0.734 $\pm$ 0.004 | 0.738 $\pm$ 0.004 | 0.742$\pm$ 0.005 | 0.743$\pm$ 0.003 | 0.747 $\pm$ 0.001 | 0.746$\pm$ 0.001
RexNet (using Skip-gram) | 0.741 $\pm$ 0.002 | 0.744 $\pm$ 0.001 | 0.746$\pm$ 0.001 | 0.747$\pm$ 0.001 | 0.751$\pm$ 0.001 | 0.752 $\pm$ 0.006
AutoRec | 0.625 $\pm$ 0.015 | 0.634 $\pm$ 0.008 | 0.627 $\pm$ 0.008 | 0.637 $\pm$ 0.007 | 0.648 $\pm$ 0.009 | 0.659 $\pm$ 0.006
ListRank | 0.647 $\pm$ 0.002 | 0.654 $\pm$ 0.002 | 0.683 $\pm$ 0.003 | 0.688 $\pm$ 0.003 | 0.751 $\pm$ 0.002 | 0.751 $\pm$ 0.002
CofiRank | 0.685 $\pm$ 0.002 | 0.684 $\pm$ 0.001 | 0.676 $\pm$ 0.008 | 0.685 $\pm$ 0.024 | 0.641 $\pm$ 0.005 | 0.644 $\pm$ 0.003
push-inf | 0.690 $\pm$ 0.008 | 0.699 $\pm$ 0.002 | 0.691 $\pm$ 0.017 | 0.697 $\pm$ 0.012 | 0.695 $\pm$ 0.011 | 0.695 $\pm$ 0.008
push-reverse | 0.640 $\pm$ 0.004 | 0.713 $\pm$ 0.023 | 0.717 $\pm$ 0.029 | 0.713 $\pm$ 0.023 | 0.738 $\pm$ 0.010 | 0.734 $\pm$ 0.010
push-p | 0.696 $\pm$ 0.008 | 0.706 $\pm$ 0.003 | 0.699 $\pm$ 0.026 | 0.705 $\pm$ 0.021 | 0.714 $\pm$ 0.025 | 0.714 $\pm$ 0.022

##  6 Discussion

In the first and second phases of RexNet, it learns users and items
representations only based on the user-item matrix, however, in the suggested
approach any method of representation learning can be used to infer in this
phase. In this work we applied two different methods; Skip-gram and GloVe, and
one important observation is the influence of these different approaches on
the final performance. As we can observe by comparing tables 1 and 2, using
GloVe yields a better performance on Movielens 100k while Skip-gram results
surpass those of GloVe in Movielens 1M. One reason of can be that the
difference in sparsity of Movelens 100K and Movelens 1M. Table 3 shows the
density of both datasests. As we can see, Movielens 1M is sparser than
Movielens 100K. The observed improvement in the performance of Glove in denser
data set can be due to the fact that it heavily relies on global statistical
information that it collects. In sparser datasets the available statistical
information is not reliable enough and that may avoid Glove from inferring
valid representations for some entities. But when we have a denser user-item
matrix, GloVe’s usage of statistical information helps it to infer embeddings
that better represent the nature of entities. That can lead to better
predictions in the next step and a higher overall recommendation performance.
Another observation is the significant superiority of RexNet over AutoRec.
AutoRec uses an Auto Encoder to capture user’s representations to predict user
ratings, while RexNet captures item’s and user’s representations to learn
their hierarchical features. To examine the ranking performance of AutoRec, we
implemented it with the same setting of our algorithm to calculate NDCG.
AutoRec’s input is the sparse vector of users or items while RexNet first
captures dense representations and then trains the neural network. It seems
that having multiple layers in the neural network and also utilizing dense
vectors of users and items helps RexNet to learn features that AutoRec is
unable to capture.

Table 3: Density of Movielens 100K and Movielens 1M.

DATASET | USERS | MOVIES | RATINGS | DENSITY
---|---|---|---|---
MovieLens 100K | 943 | 1682 | 100,000 | 0.0630
MovieLens 1M | 6040 | 3706 | 1,000,000 | 0.0446

##  7 Conclusion

In this paper, we introduced a modular approach for collaborative filtering
and our experiments showed that the suggested method outperforms the state-of-
the-art CF algorithms in terms of NDCG. We showed that learning
representations in a Collaborative Filtering environment can be done using
well-known methods of word embedding such as Skip-gram and GloVe. The results
showed that while Skip-gram performs better in sparser dataset while GloVe
outperforms it in the denser one. We also argued that hierarchical feature
extraction can be applied to recommendation systems and to do so, we
introduced a deep parallel neural network architecture to capture hierarchical
features of items and users in order to predict user preferences. Experimental
results showed that the suggested approach performs quite well in two
recommendation data sets. One future study can be validating different
settings for the suggested structure to achieve better results. We tried GloVe
and Skip-gram, that are well-known word embedding tools, for learning initial
linear representations for users and items. The performance of the framework
can possibly be further improved by designing special representation learning
approaches which also takes collaborative filtering concerns into account.

## References

  * [1] Y. LeCun, Y. Bengio, G. Hinton, Deep learning, nature 521 (7553) (2015) 436.
  * [2] A. Krizhevsky, I. Sutskever, G. E. Hinton, Imagenet classification with deep convolutional neural networks, in: Advances in neural information processing systems, 2012, pp. 1097–1105.
  * [3] T. Mikolov, M. Karafiát, L. Burget, J. Černockỳ, S. Khudanpur, Recurrent neural network based language model, in: Eleventh Annual Conference of the International Speech Communication Association, 2010.
  * [4] F. Schroff, D. Kalenichenko, J. Philbin, Facenet: A unified embedding for face recognition and clustering, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2015, pp. 815–823.
  * [5] E. Hoseinzade, S. Haratizadeh, Cnnpred: Cnn-based stock market prediction using a diverse set of variables, Expert Systems with Applications 129 (2019) 273–285.
  * [6] E. Hoseinzade, S. Haratizadeh, A. Khoeini, U-cnnpred: A universal cnn-based predictor for stock markets, arXiv preprint arXiv:1911.12540.
  * [7] L. Zheng, V. Noroozi, P. S. Yu, Joint deep modeling of users and items using reviews for recommendation, in: Proceedings of the Tenth ACM International Conference on Web Search and Data Mining, ACM, 2017, pp. 425–434.
  * [8] T. K. Paradarami, N. D. Bastian, J. L. Wightman, A hybrid recommender system using artificial neural networks, Expert Systems with Applications 83 (2017) 300–313.
  * [9] T. Nedelec, E. Smirnova, F. Vasile, Specializing joint representations for the task of product recommendation, in: Proceedings of the 2nd Workshop on Deep Learning for Recommender Systems, ACM, 2017, pp. 10–18.
  * [10] F. Zhang, N. J. Yuan, D. Lian, X. Xie, W.-Y. Ma, Collaborative knowledge base embedding for recommender systems, in: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2016, pp. 353–362.
  * [11] J. Bennett, S. Lanning, et al., The netflix prize, in: Proceedings of KDD cup and workshop, Vol. 2007, New York, NY, USA, 2007, p. 35.
  * [12] T. Mikolov, I. Sutskever, K. Chen, b. S. Corrado, J. Dean, Distributed representations of words and phrases and their compositionality, in: Advances in neural information processing systems, 2013, pp. 3111–3119.
  * [13] J. Pennington, R. Socher, C. Manning, Glove: Global vectors for word representation, in: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), 2014, pp. 1532–1543.
  * [14] A. Mnih, R. R. Salakhutdinov, Probabilistic matrix factorization, in: Advances in neural information processing systems, 2008, pp. 1257–1264.
  * [15] Y. Koren, R. Bell, C. Volinsky, Matrix factorization techniques for recommender systems, Computer (8) (2009) 30–37.
  * [16] D. Xiao, Y. Ji, Y. Li, F. Zhuang, C. Shi, Coupled matrix factorization and topic modeling for aspect mining, Information Processing & Management 54 (6) (2018) 861–873.
  * [17] M. Jamali, M. Ester, A matrix factorization technique with trust propagation for recommendation in social networks, in: Proceedings of the fourth ACM conference on Recommender systems, ACM, 2010, pp. 135–142.
  * [18] C. Xu, A novel recommendation method based on social network using matrix factorization technique, Information Processing & Management 54 (3) (2018) 463–474.
  * [19] Z. Meng, H. Shen, H. Huang, W. Liu, J. Wang, A. K. Sangaiah, Search result diversification on attributed networks via nonnegative matrix factorization, Information Processing & Management 54 (6) (2018) 1277–1291.
  * [20] B. Shams, S. Haratizadeh, Item-based collaborative ranking, Knowledge-Based Systems 152 (2018) 172–185.
  * [21] B. Shams, S. Haratizadeh, Reliable graph-based collaborative ranking, Information Sciences 432 (2018) 116–132.
  * [22] B. Shams, S. Haratizadeh, Graph-based collaborative ranking, Expert Systems with Applications 67 (2017) 59–70.
  * [23] C. Musto, P. Basile, P. Lops, M. de Gemmis, G. Semeraro, Introducing linked open data in graph-based recommender systems, Information Processing & Management 53 (2) (2017) 405–435.
  * [24] M. K. Najafabadi, A. Mohamed, C. W. Onn, An impact of time and item influencer in collaborative filtering recommendations using graph-based model, Information Processing & Management 56 (3) (2019) 526–540.
  * [25] R. Salakhutdinov, A. Mnih, G. Hinton, Restricted boltzmann machines for collaborative filtering, in: Proceedings of the 24th International Conference on Machine Learning, ICML ’07, ACM, New York, NY, USA, 2007, pp. 791–798.
  * [26] N. Hazrati, B. Shams, S. Haratizadeh, Entity representation for pairwise collaborative ranking using restricted boltzmann machine, Expert Systems with Applications 116 (2019) 161–171.
  * [27] A. Van den Oord, S. Dieleman, B. Schrauwen, Deep content-based music recommendation, in: Advances in neural information processing systems, 2013, pp. 2643–2651.
  * [28] B. Hidasi, A. Karatzoglou, L. Baltrunas, D. Tikk, Session-based recommendations with recurrent neural networks, International Conference on Learning Representations.
  * [29] X. Li, M. de Rijke, Characterizing and predicting downloads in academic search, Information Processing & Management 56 (3) (2019) 394–407.
  * [30] S. Hochreiter, J. Schmidhuber, Long short-term memory, Neural computation 9 (8) (1997) 1735–1780.
  * [31] X. He, L. Liao, H. Zhang, L. Nie, X. Hu, T.-S. Chua, Neural collaborative filtering, in: Proceedings of the 26th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, 2017, pp. 173–182.
  * [32] S. Sedhain, A. K. Menon, S. Sanner, L. Xie, Autorec: Autoencoders meet collaborative filtering, in: Proceedings of the 24th International Conference on World Wide Web, WWW ’15 Companion, ACM, New York, NY, USA, 2015, pp. 111–112.
  * [33] O. Barkan, N. Koenigstein, Item2vec: neural item embedding for collaborative filtering, in: Machine Learning for Signal Processing (MLSP), 2016 IEEE 26th International Workshop on, IEEE, 2016, pp. 1–6.
  * [34] T. Mikolov, W.-t. Yih, G. Zweig, Linguistic regularities in continuous space word representations, in: Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2013, pp. 746–751.
  * [35] K. He, X. Zhang, S. Ren, J. Sun, Deep residual learning for image recognition, in: Proceedings of the IEEE conference on computer vision and pattern recognition, 2016, pp. 770–778.
  * [36] Y. Shi, M. Larson, A. Hanjalic, List-wise learning to rank with matrix factorization for collaborative filtering, in: Proceedings of the fourth ACM conference on Recommender systems, ACM, 2010, pp. 269–272.
  * [37] M. Weimer, A. Karatzoglou, Q. V. Le, A. J. Smola, Cofi rank-maximum margin matrix factorization for collaborative ranking, in: Advances in neural information processing systems, 2008, pp. 1593–1600.
  * [38] K. Christakopoulou, A. Banerjee, Collaborative ranking with a push at the top, in: Proceedings of the 24th International Conference on World Wide Web, International World Wide Web Conferences Steering Committee, 2015, pp. 205–215.


# Label Delay in Continual Learning

Botos Csaba1 Wenxuan Zhang2∗ Matthias Müller3 Ser-Nam Lim4 Mohamed Elhoseiny2
Philip H.S. Torr1 Adel Bibi1

1University of Oxford, 2KAUST, 3Intel Labs, 4Meta Equal contribution.e-mail:
<EMAIL_ADDRESS>
###### Abstract

Online continual learning, the process of training models on streaming data,
has gained increasing attention in recent years. However, a critical aspect
often overlooked is the label delay, where new data may not be labeled due to
slow and costly annotation processes. We introduce a new continual learning
framework with explicit modeling of the label delay between data and label
streams over time steps. In each step, the framework reveals both unlabeled
data from the current time step $t$ and labels delayed with $d$ steps, from
the time step $t-d$. In our extensive experiments amounting to 1060 GPU days,
we show that merely augmenting the computational resources is insufficient to
tackle this challenge. Our findings underline a notable performance decline
when solely relying on labeled data when the label delay becomes significant.
More surprisingly, when using state-of-the-art SSL and TTA techniques to
utilize the newer, unlabeled data, they fail to surpass the performance of a
naïve method that simply trains on the delayed supervised stream. To this end,
we introduce a simple, efficient baseline that rehearses from the labeled
memory samples that are most similar to the new unlabeled samples. This method
bridges the accuracy gap caused by label delay without significantly
increasing computational complexity. We show experimentally that our method is
the least affected by the label delay factor and in some cases successfully
recovers the accuracy of the non-delayed counterpart. We conduct various
ablations and sensitivity experiments, demonstrating the effectiveness of our
approach.

##  1 Introduction

Machine learning models have become the de facto standard for a wide range of
applications, including social media, finance, and healthcare. However, these
models usually struggle when data is constantly changing over time in a never-
ending stream, which is a common norm in real-world scenarios. This challenge
continues to be an active area of research known as Continual Learning (CL).
However, most CL prior art examine this problem with a presumption of the
immediate availability of labels once the data is collected. This assumption
can clash with the realities of practical applications.

Consider the task of monitoring recovery trends in patients after surgeries.
Doctors gather health data from numerous post-operative patients regularly.
However, this collective data does not immediately indicate broader recovery
trends or potential common complications. To make informed determinations,
several weeks of extensive checks and tests across multiple patients are
needed. Only after these checks can they label the gathered data as indicating
broader “recovery” or “complication” trends. However, by the time they gather
data, assess it, label it, and train the model, new patient data or health
scenarios may emerge. This leads to a repeating cycle: collecting data from
various patients, assessing the trends, labeling the data, training the model,
and then deploying it on new patients. The longer this cycle takes, the more
likely it is going to affect the model’s reliability, a challenge we refer to
as label delay.

In this paper, we propose a CL setting that explicitly accounts for the delay
between the arrival of new data and obtaining the corresponding labels. In our
proposed setting, the model is trained continually over time steps with label
delay of $d$ steps. In each step, the model is revealed two sets of data one
that is unlabeled from this current time step $t$, in addition to labels of
the samples revealed from the step $t-d$. In the first part of our
experiments, we analyze the naïve approach of simply waiting for the labels
and training exclusively on supervised data. We show that this is a
challenging setting where the performance of the CL model consistently
degrades as the delay increases. Moreover, we find that simply increasing the
number of parameter updates per time step does not resolve the problem. In the
second part, we propose to utilize the unlabeled data from the most recent
distribution by integrating two promising paradigms into our setting: Self-
Supervised Learning (SSL) and Test-Time Adaptation (TTA). Surprisingly, out of
the 6 SSL methods and 4 TTA methods considered, none could outperform the
naïve baseline given the same computational budget. To this end, we propose a
simple baseline that samples from previously rehearsed labeled data to match
the distribution of the newest data distribution. We show that for some of the
experiments, this approach successfully closes the accuracy gap caused by the
label delay.

In summary, our contributions are:

  * •

We propose a new formal Continual Learning setting that factors label delays
between the arrival of new data and their corresponding labels due to the
annotation latency of the annotation process.

  * •

We conduct extensive experiments ($\sim 25,000$ of GPU hours) on various
Online Continual Learning datasets, such as CLOC (Cai et al., 2021) and CGLM
(Prabhu et al., 2023b). Following recent prior art on Budgeted Continual
Learning (Prabhu et al., 2023a; Ghunaim et al., 2023), we compare the best
performing Self-Supervised Learning (Balestriero et al., 2023) and Test Time
Adaptation (Liang et al., 2023) methods and find that none of them outperforms
the naïve baseline that simply ignores the label delay and trains a model on
the delayed labeled stream.

  * •

We propose Importance Weighted Memory Sampling to rehearse past labeled data
most similar to the most recent unlabeled data, bridging the gap in
performance. IWMS outperforms the naïve method significantly and improves over
SSL and TTA method over diverse delay and computational budget scenarios with
a negligible increase in computational complexity. We further present an in-
depth analysis of the proposed method.

Figure 1:  Illustration of label delay. This figure shows a typical Continual
Learning setup with label delay due to annotation. At every time step $t$, the
data stream $\mathcal{S}_{\mathcal{X}}$ reveals unlabeled data $x^{t}$, on
which the model $f_{\theta}$ is evaluated (highlighted with green borders).
Followed by that, the data is sent to the annotator
$\mathcal{S}_{\mathcal{Y}}$ who takes an equivalent of $d$ time steps to
provide the corresponding labels. Consequently, at time-step $t$ the label
$y^{t-d}$ becomes available for the input data from $d$ time steps before. The
Continual Learning model can be trained using the delayed supervised data
(shown in color) and the newest unsupervised data (shown in grayscale). In
this example, the stream reveals three samples at each time step and the
annotation delay is $d=2$.

##  2 Related Work

Label Delay in Online Learning. While the problem of delayed feedback has been
studied in Online Learning literature (Weinberger & Ordentlich, 2002;
Mesterharm, 2005), the scope is strongly limited to toy problems of spam
detection and other synthetically generated, low-complexity data (Hu &
Kantardzic, 2017; Gomes et al., 2022). Furthermore, methods and error bounds
proposed in (Kuncheva & Sánchez, 2008; Quanrud & Khashabi, 2015; Plasse &
Adams, 2016; Gao & Ding, 2022) do not guarantee better results than a random
classifier on large-scale datasets. Interestingly, none of the prior art
differentiates between past and future unsupervised data. In our proposal, all
unsupervised data is newer than the last supervised data. We provide further
visual explanation of this conceptual difference in Figure 12.

Continual Learning. Early work on continual learning primarily revolved around
task-based continual learning, where models adapt to new tasks as they are
presented sequentially. These approaches heavily rely on task boundaries,
aiding models in recognizing and adapting to each task separately (Caccia et
al., 2021; Aljundi et al., 2019a). Conversely, recent work is done in the
task-free continual learning setting, where explicit task boundaries are
absent, and data distributions evolve over time (Aljundi et al., 2019b; c; Cai
et al., 2021). This scenario poses a challenge for models to adapt without
clear task demarcations. Prabhu et al. (2020; 2023a) illustrated that
minimalistic methods can outperform both offline and online continual learning
approaches. This was also later observed recently by RealtimeOCL by Ghunaim et
al. (2023), which reports experience replay as the most effective method when
realistic computational constraints are considered and methods are normalized
by their corresponding complexities. An essential distinction between the
complexity-normalized framework introduced in RealtimeOCL and our delayed
label setting lies in the concept of delay. In RealtimeOCL, delay arises from
model complexity: in their fast-stream scenario, the stream releases input-
label pairs quicker than models can update, causing models to train on a
belated batch of samples. In essence, while in Ghunaim et al. (2023) the delay
emerges from model evaluation constraints, labels are still instantly
available. In contrast to both RealtimeOCL and prior online continual learning
approaches, our work examines delays attributed to the non-instantaneous
arrival of labels , while under normalized computational budget. The delay in
our setup creates a distribution discrepancy between training and evaluation
samples due to the time-varying stream distribution. Hammoud et al. (2023)
highlighted the exploitation of label-correlation in online continual learning
methods, with a focus on improving online accuracy metrics through future
samples evaluation. In contrast, our work models the real-world annotation
time cost and leverages unlabeled data to enhance performance on the standard
evaluation metric.

Self-Supervised Learning. There is a rich literature of self-supervised
learning (SSL) over the recent years. Early works such as MOCO (He et al.,
2020; Chen et al., 2021) and SimCLR (Chen et al., 2020) focused on
differentiating between positive and negative examples through maximizing
similarity among positive pairs and minimizing it among negative pairs. BYOL
(Grill et al., 2020) and SimSiam (Chen & He, 2021) further investigate the
necessity of negative sampling and explore using a copy of the model for
target representations instead. Barlow Twins (Zbontar et al., 2021) and VICReg
(Bardes et al., 2022) encourage similarity between distorted versions of an
example as alternatives of contrastive loss. As such, a growing line of work
adapts SSL to continual learning to make use of unlabeled data, such as CaSSLe
(Fini et al., 2022) in task-agnostic setting and SCALE (Yu et al., 2023) in
task-free setting. However, most previous work did not perform comprehensive
examination of the abovementioned three typical categories of SSL methods
(Balestriero et al., 2023). We will bridge this gap in our work.

Test Time Adaptation. While SSL methods are mainly used as computationally
extensive pre-training techniques, TTA methods are designed to adjust models
efficiently from their original training distribution to the distribution from
which the evaluation samples are drawn from. Given our problem formulation,
TTA methods appear suitable; hence, it is crucial to assess the efficacy of
these methods within our framework. Entropy regularization methods like SHOT
(Liang et al., 2020) and TENT (Wang et al., 2021) update the feature extractor
or learnable parameters of the batch-normalization layers (Ioffe & Szegedy,
2015) to minimize the entropy of the predictions. Nguyen et al. (2023)
introduced TIPI, a method that finds input transformations that can simulate
the domain shifts to enforce the model to be robust to the distribution
shifts. SAR (Niu et al., 2023) incorporates an active sampling scheme to
filter samples with noisy gradients. More recent works consider Test Time
Adaptation in online setting (Alfarra et al., 2023) or Continual Learning
setting (Wang et al., 2022). In this work, we extend this by applying test
time adaptation in scenarios where the distribution of future test samples is
unknown and cannot be assumed to be stationary.

##  3 Problem Formulation

We follow the conventional online continual learning problem definition
proposed by Cai et al. (2021). In such a setting, we seek to learn a model
$f_{\theta}:\mathcal{X}\to\mathcal{Y}$ on a stream $\mathcal{S}$ where for
each time step $t\in\\{1,2,\dots\\}$ the stream $\mathcal{S}$ reveals data
from a time-varying distribution $\mathcal{D}_{t}$ sequentially in batches of
size $n$. At every time step, $f_{\theta}$ is required to predict the labels
of the coming batch $\\{x_{i}^{t}\\}_{i=1}^{n}$ first. Followed by this, the
corresponding labels $\\{y_{i}^{t}\\}_{i=1}^{n}$ are immediately revealed by
the stream. Finally, the model is updated using the most recent training data
$\\{(x_{i}^{t},y_{i}^{t})\\}_{i=1}^{n}$.

This setting, however, assumes that the annotation process is instantaneous,
_i.e._ the time it takes to provide the ground truth for the input samples is
negligible. In practice, this assumption rarely holds. It is often the case
that the rate at which data is revealed from the stream $\mathcal{S}$ is
faster than the rate at which labels for the unlabeled data can be collected,
as opposed to it being instantaneously revealed. To account for this delay in
accumulating the labels, we propose a setting that accommodates this lag in
label availability while still allowing for the model to be updated with the
most recent unlabeled data.

We modify the previous setting in which labels of the data revealed at time
step $t$ will only be revealed after $d$ time steps in the future. Or
equivalently, the stream $\mathcal{S}$ can be decoupled into two streams, one
revealing the data $\mathcal{S}_{\mathcal{X}}$ and the other revealing the
labels $\mathcal{S}_{\mathcal{Y}}$, where the amount of delay between the two
streams is effectively the relative speed between the rate at which data is
revealed and at which it can be annotated. Consequently, at every time step,
the stream reveals the labels for the samples from $d$ time steps before
$\\{(x_{i}^{t-d},y_{i}^{t-d})\\}_{i=1}^{n}$ and the input data of the current
time step $\\{x_{i}^{t}\\}_{i=1}^{n}$.

Following recent prior art (Prabhu et al., 2020; 2023a) that argues for
normalized computation for fair comparisons, the models are given a fixed
computational budget $\mathcal{C}$ to update the model parameters from
$\theta_{t}$ to $\theta_{t+1}$ for every time step $t$. To that end, our new
proposed setting can be formalized, alternatively to the classical OCL
setting, as follows: per time step $t$,

  1. 1.

The stream $\mathcal{S}_{\mathcal{X}}$ reveals a batch of images
$\\{x_{i}^{t}\\}_{i=1}^{n}\sim\mathcal{D}_{t}$;

  2. 2.

The model $f_{\theta_{t}}$ makes predictions $\\{\hat{y}_{i}^{t}\\}_{i=1}^{n}$
for the new revealed batch $\\{x_{i}^{t}\\}_{i=1}^{n}$;

  3. 3.

The  stream $\mathcal{S}_{\mathcal{Y}}$ reveals true labels
$\\{{y}_{i}^{{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}t-d}}\\}_{i=1}^{n}$;

  4. 4.

The model $f_{\theta_{t}}$ is evaluated by comparing the predictions
$\\{\hat{y}_{i}^{t}\\}_{i=1}^{n}$ and true labels
$\\{{y}_{i}^{t}\\}_{i=1}^{n}$, where the true labels are only for testing;

  5. 5.

The model $f_{\theta_{t}}$ is updated to $f_{\theta_{t+1}}$ using labeled data
$\cup_{\tau=1}^{t-d}\\{(x_{i}^{\tau},y_{i}^{\tau})\\}_{i=1}^{n}$ and unlabeled
data $\cup_{\tau=t-d}^{t}\\{x_{i}^{\tau}\\}_{i=1}^{n}$ under a computational
budget $\mathcal{C}$.

Note that this means at each time step $t$, the stream reveals a batch of non-
corresponding images $\\{{x}_{i}^{t}\\}_{i=1}^{n}$ and labels
$\\{{y}_{i}^{t-d}\\}_{i=1}^{n}$, as illustrated in Figure 1. With the label
delay of $d$ time steps, the images themselves revealed from time step $t-d$
to time step $t$ can be used for training, despite that labels are not
available. A naïve way to solve this problem is to discard the unlabeled
images and only train on labeled data
$\cup_{\tau=1}^{t-d}\\{(x_{i}^{\tau},y_{i}^{\tau})\\}_{i=1}^{n}$. However,
note that the evaluation is still done on the most recent samples, from
$\mathcal{S}_{\mathcal{X}}$. This effectively means, that the model, while
being evaluated on the newest data, is trained on older data (in particular,
at least $d$ time steps older). Since in our setting, the distribution from
which the training and evaluation samples are drawn from is not stationary,
this discrepancy is highly likely to hinder the model’s performance.

##  4 Practical Implications Of Label Delay

We first introduce our experimental setup in Section 4.1. Then, we demonstrate
in Section 4.2 that the label delay in an online continual learning setting
poses a difficult challenge to continual learning algorithms by showing that
performance degrades as the label delay increases. Moreover, we investigate
how much of the performance gap can be bridged by increasing the computational
budget $\mathcal{C}$ in Section 4.3.

###  4.1 Experimental Setup

Datasets. We conduct our experiments on two large-scale online continual
learning datasets. The first, Continual Localization (CLOC) (Cai et al., 2021)
which contains $39\text{M}$ images from $712$ geolocation ranging from 2007 to
2014. The second is Continual Google Landmarks (CGLM) (Prabhu et al., 2023b)
which contains $430\text{K}$ images over $10788$ classes. The task is to
localize the input image to one of the $712/10788$ locations, respectively,
for CLOC and CGLM. We follow the same split as in the common use of CLOC (Cai
et al., 2021) and CGLM (Prabhu et al., 2023b) and report the Online Accuracy
metric detailed in (Cai et al., 2021)

Architecture and Optimization. We use ResNet18-BN (He et al., 2016) for
backbone architecture. Similarly to (Ghunaim et al., 2023; Prabhu et al.,
2023a), in our experiments, the stream reveals a mini-batch, with the size of
$n=128$ for CLOC and $n=64$ for CGLM. We use SGD with the learning rate of
$0.005$, momentum of $0.9$, and weight decay of $10^{-5}$. We apply random
cropping and resizing to the images, such that the resulting input has a
resolution of $224\times 224$. In our experiments, we refer to the Naïve
method, which discards the unlabeled samples and uses uniformly sampled images
from a fixed sized memory replay buffer. The memory buffer size is
consistently $2^{19}$ samples throughout our experiments unless stated
otherwise. The First-In-First-Out mechanism to add and discard samples to and
from the buffer follows Cai et al. (2021) throughout all of our experiments.
On the CLOC dataset, during a single forward and backward pass, the naive
model processes the 128 most recent labeled samples and 128 random samples
from the replay buffer, thus the effective batch size is 256. Due to the
difference in size of the two datasets, on CGLM we follow the same procedure
with half of the number of samples, thus resulting in an effective training
batch size of 128. As our primary performance metric, we report the accuracy
computed at each time step as per Step 4 from Section 3 which is referred to
as Online Accuracy (Cai et al., 2021).

Computational Budget. Prabhu et al. (2023a) and Ghunaim et al. (2023) argue
that normalizing the computational budget is necessary for fair comparison
across CL methods; thus, we follow this common practice and normalize the
number of FLOPs required to make one backward pass with a ResNet18 (He et al.,
2016) to $\mathcal{C}=1$. When performing experiments with a larger
computational budget, we take integer multiplies of $\mathcal{C}$, and in such
scenarios we apply multiple parameter update steps per stream time-steps. The
proposed label delay factor $d$ represents the amount of time-steps the labels
are delayed with. Note that, for $\mathcal{C}=1,d=0$, our experimental setting
is identical to that of Cai et al. (2021) and Ghunaim et al. (2023).

###  4.2 Accuracy Degradation Caused By Label Delay

Figure 2: Effects of Varying Label Delay. The performance of a Naïve Online
Continual Learner model gradually degrades with increasing values of delay
$d$.

In Figure 2, we analyze how varying the label delay $d\in\\{0,10,50,100\\}$
impacts the performance of the Naïve continual learning model on both CLOC and
CGLM. We show that the delay factor does not cause immediate performance
degradation. Moreover, there is a clear correspondence between $d$ and the
extent of accuracy drop.

More specifically, we see that in both datasets the final accuracy score
gradually drops from 14.8% to 12.0%, 10.0%, and 9.1% over $d=10,50,100$,
respectively, leading to more than $38\%$ drop in performance in the worst-
case scenario on CLOC. Similarly, on CGLM increasing the label delay from
$d=10$ to $50$ and $100$ leads to consistently decreasing accuracy 13.4%,
12.5% and 12.0% respectively. However, in comparison to CLOC, on CGLM we
observe a more rapid decrease in performance from even the smallest delay
$d=10$ leading to a $25\%$ relative accuracy drop, while in the largest label
delay scenario we report a $32\%$ relative accuracy gap between the delayed
and the non-delayed model.

We note that the performance of the model is relatively low, and we argue that
it is because the models illustrated in Figure 2 are trained under the hard
computational constraints ($\mathcal{C}=1$ in CLOC and $\mathcal{C}=4$ in
CGLM) , where only a limited number of parameter updates takes place between
each time step. Our hypothesis is that the performance degradation is caused
by the label delay due to the induced distribution shift between the
evaluation and the training data. In the next section, we study whether the
performance drop can be resolved by simply increasing the computational
budget.

###  4.3 Can We Bridge The Gap With Increased $\mathcal{C}$?

Figure 3:  Increasing the Computational Budget $\mathcal{C}$ under varying
Label Delay $d$ settings. We report our scores on two datasets, CLOC (top) and
CGLM (bottom) across three delay scenarios $d=10,50,100$ on the left, middle,
and right respectively. In the easiest setting, $d=10$ the accuracy gap can be
bridged by simply spending more 8$\times$ more compute. In more challenging
scenarios, $d=50,100$ naively increasing the number of updates shows
diminishing returns, motivating us to find better use of the increased
computational budget. For brevity, we refer to the non-delayed $d=0$ Naïve
method as “w/o delay”.

Despite not being always feasible, we examine one potential solution to
recover the performance of the Naïve Baseline when $d>0$, which is increasing
the computational budget $\mathcal{C}$ and performing multiple parameter
updates per time step. In Figure 3, we show results when the computational
budget of the Naïve is doubled in three steps, _i.e._ , $\mathcal{C}=2,4,8$
under three delays of $d\in\\{10,50,100\\}$. In Figure 3, we observe the
performance improvement of the Naïve method is proportional to the budget
$\mathcal{C}$ under all delays. For example, when $d=10$, the model can
recover the performance of the Naïve accuracy in the $d=0$ setting by
increasing the computational budget from $1\rightarrow 8$ and $4\rightarrow
8$, on CLOC and CGLM, respectively. On the CLOC dataset (top row of Figure 3)
where the label delay is significant ($d=50,100$), the Naïve does not reach
the performance of its non-delayed counterpart, even when the computational
budget is increased from ${\mathcal{C}}=1\rightarrow 8$ (solid orange curve).
On the other hand, increasing from $\mathcal{C}=4\rightarrow 32$ on CGLM
(solid orange curve in the bottom row of Figure 3) results in the delayed
Naïve consistently outperforming its non-delayed counterpart with the original
budget $\mathcal{C}=4$ (solid blue curve). However, when compared against the
non-delayed Naïve method with matched computational budget (dashed orange
curve), the delay causes increased accuracy gaps: $-16.6\%,-18.1\%$ and
$-18.9\%$, with respect to the delay factor $d=10,50,100$.

Section Conclusion. To facilitate a comprehensive understanding of the
implications, we compared the Naïve method with increased $\mathcal{C}$
against its non-delayed counterpart, under both the original and matched
computational budgets. Under matched computational budget, the performance is
still significantly worse, motivating us to find methods that can leverage the
more recent unlabeled data to bridge the gap. We have shown that increasing
the computational budget of an Online Continual Learning model alleviates the
problem of the label delay, but that such a solution not only faces
diminishing returns but becomes less effective under larger delays. This
motivates our next set of experiments, in which we augment the Naïve model
training by utilizing the input images before their corresponding labels
become available.

##  5 Utilizing Data Prior to Label Arrival

In our proposed online continual learning with label delay, as observed
earlier, the larger the delay the more challenging it is for Naïve, a method
that relies only on older labeled data, to effectively predict new samples.
This is due to a larger gap in distribution between the samples the model is
trained on and the ones the model is evaluated on. The drop in accuracy caused
by this discrepancy can be partially resolved by training the models longer,
nevertheless this approach is not satisfactory for multiple reasons. First, in
many real-world scenarios, the computational budget is fixed. Furthermore,
even if it can be increased, we showed that, due to the diminishing returns,
the accuracy gap remains substantial. This begs the question of whether the
new unlabeled data can be used for training to improve over Naïve, as it is
much more similar to the data that the model is evaluated on.

In our experiments, we explore the techniques of the two most promising
paradigms for utilizing the unlabeled data, namely, Self-Supervised Learning
(SSL) and Test Time Adaptation (TTA). We integrate several of each family of
methods into our setting and evaluate them under various delays and
computational budgets. In particular, we augment the Naïve method by
optimizing the supervised objective $\mathcal{L}_{S}$ (which is the standard
Cross Entropy loss over the labeled data in our case) and an unsupervised
regularization term $\mathcal{L}_{U}$ provided by the underlying methods.

###  5.1 Self-Supervised Learning to handle label delay?

Experimental Setup. When it comes to integrating SSL methods in our setting,
there are multiple possible ways to utilize the learning methods, leading to
vastly different results. We find the overall best performing variant
iteratively optimizes $\mathcal{L}_{S}$ and $\mathcal{L}_{U}$. More
specifically, we optimize $\mathcal{L}_{S}$ on the labeled data (identically
to naive) and optimize the contrastive loss $\mathcal{L}_{U}$ on the unlabeled
data in an alternating fashion, until the computational budget $\mathcal{C}$
is not consumed. We experiment with the three main families of SSL, _i.e._ ,
Deep Metric Learning Family (MoCo (He et al., 2020), SimCLR (Chen et al.,
2020),and NNCLR (Dwibedi et al., 2021)), Self-Distillation (BYOL (Grill et
al., 2020) and SimSIAM (Chen & He, 2021), and DINO (Caron et al., 2021)), and
Canonical Correlation Analysis (VICReg (Bardes et al., 2022), BarlowTwins
(Zbontar et al., 2021), SWAV (Caron et al., 2020), and W-MSE (Ermolov et al.,
2021)). Furthermore, we conduct hyperparameter tuning on the first
$10\text{K}$ iterations of the training data over all methods, including a
scalar constant $\lambda_{U}$ that rescales $\mathcal{L}_{U}$. For further
explanation, see Figure 13 in the Supplementary Material.

Computational Budget. For fair comparison, and following Prabhu et al.
(2023a); Ghunaim et al. (2023), we normalise the computational complexity of
the compared methods. We find that while SSL methods may take multiple forward
passes, potentially with varying input sizes, the backward pass is
consistently done only once among the variants; therefore we choose the number
of backward passes to measure the computational complexity of the resulting
methods. According to this computational complexity metric, the Naïve method
augmented with SSL at each time step takes two backward passes, one for
computing the gradients of $\mathcal{L}_{U}$ and one for $\mathcal{L}_{S}$,
thus $\mathcal{C}_{\text{SSL}}=2$.

Observations. In Figure 4, we report the results of the best of ten SSL
methods on both CLOC (top row) and CGLM (bottom row). We compare the SSL based
approaches against Naïve under varying computational budget and label delay
scenarios. As discussed earlier, the SSL based methods have an effective
computational cost of $\mathcal{C}_{\text{SSL}}=2$. To maintain fair
comparison, we report the Naïve variant with an increased computational budget
$\mathcal{C}_{\text{Naïve}}=2$, _i.e._ performing twice as many supervised
parameter updates. Under such settings, the best performing SSL based method,
ReSSL (Zheng et al., 2021) (see the Supplementary Material A.1 for an in-depth
comparison) underperforms Naïve (on CLOC) $-1.2\%,-0.2\%$ and $-0.1\%$ over
$d=10,50,100$, respectively. Similarly, on CGLM, for all delay scenarios, the
best performing SSL method, underperforms the Naïve counterpart: $-2.3\%,-2\%$
and $-2.1\%$ in terms of online accuracy. We hypothesize this is due to
several reasons: (1) SSL methods generally are sample inefficient and require
a few magnitudes more iterations than the supervised method to achieve the
same downstream accuracy. (2) The contrastive objective aids learning low
level visual concepts, features that are less important for the downstream
task of CLOC and CGLM, _i.e._ geo-localization and landmark detection
respectively.

Figure 4:  Comparison of various unsupervised methods. The performance of the
Naïve model augmented with various unsupervised adaptation methods under
varying label delay $d$ settings on two datasets (top: CLOC (Cai et al.,
2021), bottom: CGLM (Prabhu et al., 2023a)). We report the best performing
methods in each category, ReSSL (Chen et al., 2021) and CoTTA (Wang et al.,
2022) for SSL and TTA respectively. Our proposed method, described in Section
5.3, consistently outperforms all categories under all delay settings on both
datasets.

###  5.2 Test-Time Adaptation

Experimental Setup. Similarly to SSL, there are multiple ways to integrate TTA
methods in our setting. We find the following setup resulting in the best
performance: we continuously train the model with the supervised data as in
the Naïve method, and before each evaluation step we adapt the model using a
single parameter update on the unsupervised data $\\{x^{t}_{i}\\}^{n}_{i=1}$.
We implement and compare the following TTA methods: TENT (Wang et al., 2021),
EATA (Niu et al., 2022), SAR (Niu et al., 2023), and CoTTA (Wang et al.,
2022), in Figure 4. For an extensive comparison of the methods under various
delay scenarios, see Section A.2.

Computational Budget. Similarly to SSL based approaches, we normalise the
computational budget for all TTA approaches by counting the full backward
passes made on the unlabeled samples when optimizing $\mathcal{L}_{U}$.
Following this complexity metric, the implemented TTA methods fall under the
same associated cost; therefore, we can use the same normalization factor for
all TTA methods across our experiments.

Observations. In Figure 4, we find that the best performing TTA method, CoTTA
(Wang et al., 2022), consistently underperforms both the Naïve and the SSL
baseline under every delay scenario on both datasets, from $3.1\%$ up to
$-6.3\%$ performance drop. We hypothesize that the TTA methods fail to
outperform the Naïve counterpart because the common assumptions among the
settings on which TTA methods are evaluated are broken. The common assumptions
of TTA methods are: (1) before the adaptation takes place, the model has
already converged and achieved a good performance on the training data, (2)
the test data distribution is stationary and a sufficient amount of
unsupervised data is available for adaptation. In contrast, in our setting the
source model is continuously updated between time steps and only a limited
number of samples are available from the newest distribution for adaptation.

###  5.3 Rehearsing On Relevant Samples

When utilizing unsupervised samples to enhance the Naïve method, we have shown
that directly spending the computational budget to optimize a generic
objective over the unlabeled images does not seem to help to outperform the
Naïve method. This suggests a solution that leverages supervised samples
directly, rather than spending the computational budget on unlabeled data.
Although we cannot directly adapt the model to the newest distribution of the
stream, we can adapt the sampling process from the memory buffer to match the
desired distribution. We propose a very simple, yet effective method to
achieve a data efficient and therefore computationally efficient solution to
the challenges imposed by label delay that we dub Importance Weighted Memory
Sampling (IWMS).

When sampling the supervised training data, using the most recent labeled
samples leads to fitting the model to an outdated distribution (we further
discuss this in 6). Thus, we replace the newest supervised data by a batch
which we sample from the memory buffer, such that the distribution of the
selected samples matches the newest unlabeled data distribution. More
specifically, our sampling process consists of three stages. First, at each
time step $t$, for every unsupervised sample $x^{t}_{j}$ in the batch of size
$n$, we compute the prediction $\tilde{y}^{t}_{j}$, and select every labeled
sample from the memory buffer $(x_{i}^{M},y_{i}^{M})$ such that the true label
of the selected samples matches the predicted label
$y^{M}_{i}=\tilde{y}^{t}_{j}$. Then, we compute the pairwise cosine feature
similarities $K_{i,j}$ between the unlabeled sample $x^{t}_{j}$ and the
selected labeled samples $x_{i}^{M}$ by
$K_{i,j}=\text{cos}\left(h(x^{M}_{i}),h(x^{t}_{j})\right)$, where $h$
represents the feature extractor directly before the final classification
layer. Lastly, we select the most relevant supervised samples
$(x^{M}_{i^{\prime}},y^{M}_{i^{\prime}})$ by sampling
$i^{\prime}\in\\{1\ldots|M|\\}$ from a multinomial distribution with
parameters $K_{:,j}$. Thus, we rehearse samples from the memory which (1)
share the same true labels as the predicted labels of the unlabeled samples,
(2) have high feature similarity with the unlabeled samples.

Implementation Details. To avoid re-computing the feature representation $h$
for each sample in the memory buffer at every iteration, during the evaluation
phase, we store each input sample and their corresponding features in the
memory buffer. We only compute the features once, when adding them to the
replay buffer.

Computational Budget. Since our method simply replaces the newest supervised
samples with the most similar samples from the replay buffer, we do not
require any additional backward passes to compute the auxiliary objective.
Therefore, the computational budget of our method is identical to the Naïve
baseline, _i.e._ , $\mathcal{C}_{\text{Ours}}=1$.

Observations. First, in Figure 4 on CLOC (top row), we show that our method is
the only method that can outperform the Naïve baseline, by
$+1.5\%,+1.4\%,+1.4\%$ improvement on $d=10,50,100$ settings respectively.
Although our method outperforms every delayed method, there is still a
considerable gap between the non-delayed Naïve counterpart, on which we
provide further explanation in the Supplementary Material A.4. In contrast, on
CGLM (Fgiure 4 bottom row) we show that our method can close gap between the
non-delayed Naïve method under all delay settings ($d=10,50,100$, shown in
increasing order from left to right), thus the performance drop due to the
label delay is minimized to $-0\%,-0.6\%$ and $-1.4\%$ respectively.

###  5.4 Analysis Of Importance Weighted Memory Sampling

In this section, we first perform an ablation study of our IWMS to show the
effectiveness of the importance sampling. Then, we show our performances under
different computational budgets and buffer sizes.

Figure 5:  Effect of sampling strategy (left), memory sizes (middle) and
computational budget (right). We report the Online Accuracy under the least
(top: $d=10$) and the most challenging (bottom: $d=100$) label delay scenarios
on CGLM (Prabhu et al., 2023b).  Figure 6: Backward transfer in various
scenarios. Measuring forgetting on the withheld validation set.

Analysis on Memory Sampling Strategies. During training, the Naïve method uses
the most recent labeled data and a randomly sampled mini-batch from the memory
buffer for each parameter update. Our method provides a third option for
constructing the training mini-batch, which picks the labeled memory sample
that is most similar to the unlabeled data. When comparing sampling
strategies, we refer to the newest batch of data as (N), the random batch of
data as (R) and the importance weighted memory samples as (W). In Figure 5
left, we first show that in both delay scenarios ($d=10$ and $d=100$)
replacing the newest batch (N) with (W) results in almost doubling the
performance: $+8.5\%$ and $+9.1\%$ improvement over Naïve, respectively.
Interestingly enough, when we replace the (N) with uniformly sampled random
buffer data (R) we report a significant increase in performance. We attribute
this phenomenon to the detrimental effects of label delay: even though Naïve
uses the most recent supervised samples for training, the increasing
discrepancy caused by the delay $d=10$ and $d=100$ forces the model to over-
fit on the outdated distribution.

Analysis on Computational Budget. We study our algorithm under various
computational budgets, ranging from ${\mathcal{C}}=4$ to ${\mathcal{C}}=32$
(shown in Figure 5 middle). Under both delays, the performances of our
algorithm improve as the computational budget improves. However, our required
computational budget for the algorithm to converge is relatively small. When
we increase the budget from $\mathcal{C}=8$ to $\mathcal{C}=32$, the
performances only increase around $+3\%$. Thus, our algorithm can efficiently
cope with continual learning settings where the budget is limited.

Analysis on the Memory Size. We study the influence of buffer size on our
proposed IWMS. In particular, we show the performance of our algorithm under
the buffer size from 10k to 80k in Figure 5 (right). Even though IWMS relies
on the images sampled from the buffer to represent the new coming
distribution, its performances remain robust under different buffer sizes.
Under both delay of 10 and 100, the performance gap of our algorithm between
the buffer size of 10k and 80k is only around 2.5%. This means our algorithm
is flexible in coping with various buffer assumption.

Analysis on forgetting over past samples In Figure 6, we observe that our
method outperforms the SSL, Naïve and non-delayed Naïve baseline achieving 2x
better accuracy on CGLM, whereas on CLOC all methods perform similarly (due to
poor data quality as reported in the supplementary material Sec A.4).

##  6 Discussion

In this work, we have addressed label delay in online continual learning. We
show that merely augmenting the computational resources is insufficient to
tackle this challenge. Our findings underline a notable performance decline
when solely relying on labeled data when the label delay becomes significant.
Moreover, state-of-the-art SSL and TTA techniques fail to surpass the
performance of the naïve method of simply training on the delayed supervised
stream. To address these challenges, we propose IWMS, which not only mitigates
the accuracy discrepancies due to label delay, but also significantly exceeds
the performance of its non-delayed counterpart, particularly in extreme delay
and computational constraint conditions. Although our continual learning
framework assumes a constant label delay factor and eventually provides labels
for all samples revealed by the stream, in more complex applications the
labeling process may exhibit variable durations and the samples selected for
labeling can be guided. By looking into these scenarios, we might find ways to
use Active Learning to improve sample selection in Continual Learning,
pointing to a new research direction.

##  7 Acknowledgement

This work is supported by a UKRI grant Turing AI Fellowship (EP/W002981/1) and
EPSRC/MURI grant: EP/N019474/1. Adel Bibi has received funding from the Amazon
Research Awards. The authors thank Razvan Pascanu and João Henriques for their
insightful feedback. We also thank the Royal Academy of Engineering.

## References

  * Alfarra et al. (2023) Motasem Alfarra, Hani Itani, Alejandro Pardo, Shyma Alhuwaider, Merey Ramazanova, Juan C Pérez, Zhipeng Cai, Matthias Müller, and Bernard Ghanem.  Revisiting test time adaptation under online evaluation.  _arXiv preprint arXiv:2304.04795_ , 2023.
  * Aljundi et al. (2019a) Rahaf Aljundi, Eugene Belilovsky, Tinne Tuytelaars, Laurent Charlin, Massimo Caccia, Min Lin, and Lucas Page-Caccia.  Online continual learning with maximal interfered retrieval.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019a.
  * Aljundi et al. (2019b) Rahaf Aljundi, Klaas Kelchtermans, and Tinne Tuytelaars.  Task-free continual learning.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2019b.
  * Aljundi et al. (2019c) Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio.  Gradient based sample selection for online continual learning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2019c.
  * Balestriero et al. (2023) Randall Balestriero, Mark Ibrahim, Vlad Sobal, Ari Morcos, Shashank Shekhar, Tom Goldstein, Florian Bordes, Adrien Bardes, Gregoire Mialon, Yuandong Tian, et al.  A cookbook of self-supervised learning.  _arXiv preprint arXiv:2304.12210_ , 2023.
  * Bardes et al. (2022) Adrien Bardes, Jean Ponce, and Yann LeCun.  VICReg: Variance-invariance-covariance regularization for self-supervised learning.  In _International Conference on Learning Representations (ICLR)_ , 2022.
  * Caccia et al. (2021) Lucas Caccia, Rahaf Aljundi, Nader Asadi, Tinne Tuytelaars, Joelle Pineau, and Eugene Belilovsky.  New insights on reducing abrupt representation change in online continual learning.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Cai et al. (2021) Zhipeng Cai, Ozan Sener, and Vladlen Koltun.  Online continual learning with natural distribution shifts: An empirical study with visual data.  In _International Conference on Computer Vision (ICCV)_ , 2021.
  * Caron et al. (2020) Mathilde Caron, Ishan Misra, Julien Mairal, Priya Goyal, Piotr Bojanowski, and Armand Joulin.  Unsupervised learning of visual features by contrasting cluster assignment.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020\.
  * Caron et al. (2021) Mathilde Caron, Hugo Touvron, Ishan Misra, Hervé Jégou, Julien Mairal, Piotr Bojanowski, and Armand Joulin.  Eemerging properties in self-supervised vision transformers.  In _International Conference on Computer Vision (ICCV)_ , 2021.
  * Chen et al. (2020) Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Chen et al. (2021) X. Chen, S. Xie, and K. He.  An empirical study of training self-supervised vision transformers.  In _International Conference on Computer Vision (ICCV)_ , 2021.
  * Chen & He (2021) Xinlei Chen and Kaiming He.  Exploring simple siamese representation learning.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021.
  * Dwibedi et al. (2021) Debidatta Dwibedi, Yusuf Aytar, Jonathan Tompson, Pierre Sermanet, and Andrew Zisserman.  With a little help from my friends: Nearest-neighbor contrastive learning of visual representations.  In _International Conference on Computer Vision (ICCV)_ , 2021.
  * Ermolov et al. (2021) Aleksandr Ermolov, Aliaksandr Siarohin, Enver Sangineto, and Nicu Sebe.  Whitening for self-supervised representation learning.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Fini et al. (2022) Enrico Fini, Victor G Turrisi da Costa, Xavier Alameda-Pineda, Elisa Ricci, Karteek Alahari, and Julien Mairal.  Self-supervised models are continual learners.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Gao & Ding (2022) Haoran Gao and Zhijun Ding.  A novel machine learning method for delayed labels.  In _2022 IEEE International Conference on Networking, Sensing and Control (ICNSC)_ , pp. 1–6. IEEE, 2022.
  * Ghunaim et al. (2023) 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 hope.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Gomes et al. (2022) Heitor Murilo Gomes, Maciej Grzenda, Rodrigo Mello, Jesse Read, Minh Huong Le Nguyen, and Albert Bifet.  A survey on semi-supervised learning for delayed partially labelled data streams.  _ACM Computing Surveys_ , 55(4):1–42, 2022.
  * Grill et al. (2020) Jean-Bastien Grill, Florian Strub, Florent Altché, Corentin Tallec, Pierre H. Richemond, Elena Buchatskaya, Carl Doersch, Bernardo Avila Pires, Zhaohan Daniel Guo, Mohammad Gheshlaghi Azar, Bilal Piot, Koray Kavukcuoglu, Rémi Munos, and Michal Valko.  Bootstrap your own latent a new approach to self-supervised learning.  In _Advances in Neural Information Processing Systems (NeurIPS)_ , 2020.
  * Hammoud et al. (2023) Hasan Abed Al Kader Hammoud, Ameya Prabhu, Ser-Nam Lim, Philip H. S. Torr, Adel Bibi, and Bernard Ghanem.  Rapid adaptation in online continual learning: Are we evaluating it right?  In _International Conference on Computer Vision (ICCV)_ , 2023.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016.
  * He et al. (2020) Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2020.
  * Hu & Kantardzic (2017) Hanqing Hu and Mehmed Kantardzic.  Sliding reservoir approach for delayed labeling in streaming data classification.  2017\.
  * Ioffe & Szegedy (2015) Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  _arXiv preprint arXiv:1502.03167_ , 2015.
  * Kuncheva & Sánchez (2008) Ludmila I Kuncheva and J Salvador Sánchez.  Nearest neighbour classifiers for streaming data with delayed labelling.  In _2008 Eighth IEEE International Conference on Data Mining_ , pp. 869–874. IEEE, 2008.
  * Liang et al. (2020) Jian Liang, Dapeng Hu, and Jiashi Feng.  Do we really need to access the source data? source hypothesis transfer for unsupervised domain adaptation.  In _International Conference on Machine Learning (ICML)_ , 2020.
  * Liang et al. (2023) Jian Liang, Ran He, and Tieniu Tan.  A comprehensive survey on test-time adaptation under distribution shifts.  _arXiv preprint arXiv:2303.15361_ , 2023.
  * Mesterharm (2005) Chris Mesterharm.  On-line learning with delayed label feedback.  In _International Conference on Algorithmic Learning Theory_ , pp. 399–413. Springer, 2005.
  * Nguyen et al. (2023) A. Tuan Nguyen, Thanh Nguyen-Tang, Ser-Nam Lim, and Philip Torr.  Tipi: Test time adaptation with transformation invariance.  _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023\.
  * Niu et al. (2022) Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Yaofo Chen, Shijian Zheng, Peilin Zhao, and Mingkui Tan.  Efficient test-time model adaptation without forgetting.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Niu et al. (2023) Shuaicheng Niu, Jiaxiang Wu, Yifan Zhang, Zhiquan Wen, Yaofo Chen, Peilin Zhao, and Mingkui Tan.  Towards stable test-time adaptation in dynamic wild world.  In _International Conference on Learning Representations (ICLR)_ , 2023.
  * Plasse & Adams (2016) Joshua Plasse and Niall Adams.  Handling delayed labels in temporally evolving data streams.  In _2016 IEEE International Conference on Big Data (Big Data)_ , pp. 2416–2424. IEEE, 2016.
  * Prabhu et al. (2020) Ameya Prabhu, Philip HS Torr, and Puneet K Dokania.  Gdumb: A simple approach that questions our progress in continual learning.  In _European Conference on Computer Vision (EECV)_ , 2020.
  * Prabhu et al. (2023a) Ameya Prabhu, Hasan Abed Al Kader Hammoud, Puneet K Dokania, Philip HS Torr, Ser-Nam Lim, Bernard Ghanem, and Adel Bibi.  Computationally budgeted continual learning: What does matter?  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023a.
  * Prabhu et al. (2023b) Ameya Prabhu, Zhipeng Cai, Puneet Dokania, Philip Torr, Vladlen Koltun, and Ozan Sener.  Online continual learning without the storage constraint.  _arXiv preprint arXiv:2305.09253_ , 2023b.
  * Quanrud & Khashabi (2015) Kent Quanrud and Daniel Khashabi.  Online learning with adversarial delays.  _Advances in neural information processing systems_ , 28, 2015.
  * Wang et al. (2021) Dequan Wang, Evan Shelhamer, Shaoteng Liu, Bruno Olshausen, and Trevor Darrell.  Tent: Fully test-time adaptation by entropy minimization.  In _International Conference on Learning Representations (ICLR)_ , 2021.
  * Wang et al. (2022) Qin Wang, Olga Fink, Luc Van Gool, and Dengxin Dai.  Continual test-time domain adaptation.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2022.
  * Weinberger & Ordentlich (2002) Marcelo J Weinberger and Erik Ordentlich.  On delayed prediction of individual sequences.  _IEEE Transactions on Information Theory_ , 48(7):1959–1976, 2002.
  * Yu et al. (2023) Xiaofan Yu, Yunhui Guo, Sicun Gao, and Tajana Rosing.  Scale: Online self-supervised lifelong learning without prior knowledge.  In _Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2023.
  * Zbontar et al. (2021) Jure Zbontar, Li Jing, Ishan Misra, Yann LeCun, and Stéphane Deny.  Barlow twins: Self-supervised learning via redundancy reduction.  In _International Conference on Machine Learning (ICML)_ , 2021.
  * Zheng et al. (2021) Mingkai Zheng, Shan You, Fei Wang, Chen Qian, Changshui Zhang, Xiaogang Wang, and Chang Xu.  Ressl: Relational self-supervised learning with weak augmentation.  _Advances in Neural Information Processing Systems (NeurIPS)_ , 2021\.

##  Appendix A Supplementary Material

###  A.1 Breakdown of SSL methods

Figure 7: Comparison of the best performing SSL based methods after hyper-
parameter tuning

In Figure 7 we show the performance of the best performing SSL based methods
after hyper-parameter tuning. We observe that the performance of the SSL
methods is highly dependent on the dataset and the delay setting. However, we
apart from MoCo v3 (Chen et al., 2021), the methods perform similarly to Naïve
on CLOC. On the other hand on CGLM they have insignificant differences in
performance, but consistently underperform Naïve.

###  A.2 Breakdown of TTA methods

Figure 8: Comparison of the best performing TTA based methods after hyper-
parameter tuning

In Figure 8 we show the performance of the best performing TTA based methods
after hyper-parameter tuning. We observe that the performance of the TTA
methods are consistently worse than Naïve on both CLOC and CGLM, under all
delay settings. We observe that in the most severe delay scenario ($d=100$)
the performance of EAT (Niu et al., 2022) and SAR (Niu et al., 2023) is
comparable to Naïve on CLOC, while CoTTA (Wang et al., 2022) avoids the
catastrophic performance drop.

###  A.3 Comparison of SSL based methods to Naïve when using same amount of
supervised data

Figure 9: Detailed breakdown of various SSL methods from each family. Results
are shown across varying number of parameter updates $\mathcal{C}=2,10,20$
under the $d=10$ scenario.

In Figure 9, we show that when trained on equal amount of supervised data, SSL
based methods perform outperform Naïve, however the performance gap is not as
significant as in the case of using the same computational budget, as shown in
the main Figure 4.

###  A.4 Examples of the Importance Weighted Memory Sampling on CLOC

Figure 10: Correctly labeled memory recalls. In the subfigure’s caption
“Newest” refers to the newest unsupervised image observed by the model and
“iwm” refers to the sample drawn from the memory by our proposed sampling
method. The numbers refer to the corresponding true label IDs. Figure 11:
Incorrectly labeled memory recalls. In the subfigure’s caption “Newest” refers
to the newest unsupervised image observed by the model and “iwm” refers to the
sample drawn from the memory by our proposed sampling method. The numbers
refer to the corresponding true label IDs.

On CLOC, we report similar scores to Naïve due to high noise in the data. To
provide evidence for our claims we visualize the supervised data sampled from
the memory buffer by our Importance Weighted Memory Sampling method. In Figure
10, we show that our method is capable of guessing the correct location of the
unsupervised sample (the left hand side of the image pairs) and recalling a
relevant sample from memory. In contrast, the incorrect memory recalls hurt
the performance even though the content of the samples might match. We
illustrate such cases in Figure 11, where it is obvious that in some cases the
underlying image content has no information related to the location where the
picture was taken at. In such scenarios, the only way a classifier can
correctly predict the labels is by exploiting label correlations, _e.g._
classifying all close-up images of flowers to belong to the same geo-location,
even though the flowers are not unique to the location itself. Or consider the
pictures taken at social gatherings (second row, second column from the
right), where a delayed classifier without being exposed to that specific
series of images has no reason to correctly predict the location ID. Our
claims are reinforced by the findings of Hammoud et al. (2023).

###  A.5 Visual Explanation of our Experimental Framework

We provide visual guides for explaining our experimental framework. In Figure
12, we emphasize the main difference between our setting and the general
setting of partially labeled data-streams: while prior art does not
differentiate between old and new unsupervised data, our work focuses
specifically on the scenario when all unsupervised data is newer then the
supervised data. In Figure 13, we show the two types of data that our models
work with: outdated supervised data, and newer, unsupervised data. The task is
to find a way to utilize the newer unsupervised data to augment the Naïve
approach, that simply just waits for the labels to become available to update
its parameters. The most challenging component in our experiments is the
computational budget factor that allows only a certain amount of forward and
backward passes through the backbone.

Figure 12:  Top - our framework: After a fixed amount of time steps all labels
become available. This allows us to focus on utilizing future unsupervised
samples effectively. Bottom - partial labeling framework: in the generic
setting, when the data collection rate is higher than the annotation rate,
some samples might never receive labels.  Figure 13: Experimental setup: in
our experiments we show how increased label delay affects the Naïve approach
that simply just waits for the labels to arrive. To counter the performance
degradation we evaluate three paradigms (Self-Supervised Learning, Test-Time
Adaptation, Importance Weighted Memory Sampling) that can augment the Naïve
method by utilizing the newer, unsupervised data.