# Class Conditional Gaussians for Continual Learning

Thomas L. Lee
School of Informatics
University of Edinburgh
<EMAIL_ADDRESS>
&Amos Storkey
School of Informatics
University of Edinburgh
<EMAIL_ADDRESS>

###### Abstract

Dealing with representation shift is one of the main problems in online
continual learning. Current methods mainly solve this by reducing
representation shift, but leave the classifier on top of the representation to
slowly adapt, in many update steps, to the remaining representation shift,
increasing forgetting. We propose DeepCCG, an empirical Bayesian approach to
solve this problem. DeepCCG works by updating the posterior of a class
conditional Gaussian classifier such that the classifier adapts instantly to
representation shift. The use of a class conditional Gaussian classifier also
enables DeepCCG to use a log conditional marginal likelihood loss to update
the representation, which can be seen as a new type of replay. To perform the
update to the classifier and representation, DeepCCG maintains a fixed number
of examples in memory and so a key part of DeepCCG is selecting what examples
to store, choosing the subset that minimises the KL divergence between the
true posterior and the posterior induced by the subset. We demonstrate the
performance of DeepCCG on a range of settings, including those with
overlapping tasks which thus far have been under-explored. In the experiments,
DeepCCG outperforms all other methods, evidencing its potential.

##  1 Introduction

Real world use of deep learning methods can often necessitate dynamic updating
of solutions on non-stationary data streams [11, 3]. This is one of the main
problems studied in continual learning and as a result, continual learning has
become of increasing interest to the machine learning community, with many
proposed approaches [30] and settings [18, 3, 8]. Currently, one of the
biggest challenges in continual learning is catastrophic forgetting.
_Catastrophic forgetting_ describes the common occurrence in learning where
unconstrained deep models easily forget information derived from previous data
after updating on other data. While there have been significant steps taken to
solve this problem [8, 25], in many settings there are still gains to be made
[11].

The setting considered here is _online continual learning_ [5, 2] where a data
stream is split into a sequential set of _tasks_. Each task is encapsulated by
a representative dataset (sampled i.i.d. from a task distribution) which is
given to a method _batch by batch_. Different tasks will generally be
associated with different distributions, as well as different target problems.
Target problems are summarised in a task objective function. Here, the task
objective is classification [18], where the classes being considered vary
between tasks. The objective of any method, after sequentially seeing the
tasks, is to perform well on all of them, given constraints on the memory used
by the method.

Most continual learning methods can be seen as a composition of an encoder and
classifier. The encoder maps data instances to a representation and the
classifier given a example in representation space assigns a class to it. In
online continual learning when the encoder is updated, the representation of
data from previous tasks shift, which can lead to catastrophic forgetting.
Therefore, many standard online continual learning methods aim to minimise
representation shift of data from old tasks. For instance, many methods reduce
representation shift by storing previous data points in a memory buffer and
using them to regularise the update of the representation [8, 36]. However,
these methods do not fully prevent representation shift (indeed doing so
entirely would severely hinder model flexibility) and it takes many update
steps for them to adapt their classifier to representation shift, impeding
learning and causing forgetting (see Figure 1 and analysis of representation
shift in Section 1).

The point of this paper is to identify a clean way to immediately adapt a
classifier to representation shift, while at the same time enabling learning
of better and better representations. To do this we propose a new method
DeepCCG which leverages a Bayesian class-conditional Gaussian model for
classification. The use of such a classifier has three main effects. First,
the posterior of the parameters of the class-conditional model can be
recomputed to instantly adjust to representation shift. This means that the
classifier and the shifted representation will be better aligned, removing the
potential for the representation to unnecessarily change to better fit the
outdated classifier. Second, it allows for the tractable use of a conditional
marginal likelihood for optimizing the parameters of the embedding function.
This can be seen as a new type of replay; replay methods have been shown to
reduce representation shift, increasing performance [36, 40, 8]. Third, a
fixed subset of data is chosen to track representation shift, by selecting the
subset that best recreates the posterior distribution. This method for
selecting samples is shown to be robust to general kinds of representation
shift (see Section 4) and is required for DeepCCG to perform well (see
ablation study in Section 5.2).

In our experiments we look at two specific settings, the commonly used
disjoint tasks setting, where each task contains different classes to any
other [8] and an underexplored shifting window setting, where there is an
overlap between what classes are in each task. The reason we look at a setting
with an overlap between tasks is to explore each method’s ability to exploit
shared information between tasks, which is a beneficial property for methods
to have [4]. The results of our experiments show that DeepCCG performed best
out of all methods tested, highlighting the potential of the approach.

The main contributions of this work are: 1) An online continual learning
approach DeepCCG, which by learning the classifier in a tractable Bayesian
manner adapts to representation shift in one step and performs best in our
experiments; 2) Use of a log conditional marginal likelihood loss term to fit
the embedding function, which to our knowledge is the first likelihood loss
conditioned on part of the data to be used in continual learning; 3) A new
method to select what samples to store in memory, by minimising the KL-
divergence between the true posterior and the one induced by the subset of
data to be stored in memory; 4) An unexplored experimental setting, the
shifting window setting, which explores how well methods do when there is
increased shared information between tasks.

Figure 1: Diagram showing that when updating a model on new data current
online continual learning methods only slowly adapt the classifier, i.e.
decision boundary in representation space, to this representation shift. On
the other hand, DeepCCG quickly adapts the decision boundary, improving
learning as the classifier is better matched to the current representation.

##  2 Related work

There are three main paradigms for solving continual learning problems:
_regularisation_ , _parameter-isolation_ and _replay_ [8]. _Regularisation_
methods aim to prevent catastrophic forgetting by adding terms to the loss
which try to prevent the network from erasing the information of previous
tasks [21, 19]. _Parameter-Isolation_ methods look at controlling what
parameters of a neural network are used for what tasks and contain methods
which dynamically expand neural networks [26]. Finally, _Replay_ methods aim
to solve continual learning problems by storing a subset of previously seen
samples, which are then trained on alongside new incoming data. This is the
approach our method is part of. Replay methods have been shown to have
competitive if not the best performance across many settings [36, 40, 27]. The
standard replay method is experience replay (ER) [7, 6, 1], which in the
online setting looked at in this work, selects samples to store using
reservoir sampling [38], we call this variant ER-reservoir [7]. One of the
main questions to be answered by a replay-based approach is how to select what
samples to store in memory. While reservoir sampling has been shown to be very
effective [39] there have been other methods proposed for sample selection,
for example ones which use information-theoretic criteria [39] and others
maximising the diversity of the gradients of stored examples [2]. There has
also been a Bayesian method proposed to select samples called InfoGS [34],
which is somewhat similar to our method but only uses the probability model to
select samples, not for prediction or training. Additionally, their exists
methods to select what examples to replay at each update step [1, 33] which
are complementary/orthogonal to this work.

There has been considerable work on using Bayesian methods in continual
learning [28, 9, 23], perhaps inspired by the fact that true online Bayesian
inference cannot suffer from catastrophic forgetting [28]. Bayesian
perspectives have mainly been used for regularisation based methods, where a
popular approach is to use variational inference [28, 12, 42]. These
variational inference methods focus on the offline continual learning setting
where a learner has access to all of the data of a task at the same time and,
in previous work, are often limited to being used in conjunction with small
neural networks, mainly due to the need to sample multiple networks when
calculating the loss [16, 28]. Therefore, these methods are not suited to the
settings we consider in this paper. Bayesian methods have also been used in
generative replay based approaches, where instead of storing and replaying
real samples they use generated pseudo-samples [32]. Generative replay methods
focus on the offline scenario, where it is possible to iterate over the whole
of a task’s data to fit a generator, while we look at the more realistic
online scenario in this work. Finally, when it comes to replay with real
examples, there has been relatively little work on using Bayesian methods,
specifically for empirical Bayesian methods where there is a requirement to
prevent forgetting when fitting the embedding function, which we aim to help
to fill in by proposing DeepCCG.

In this work we look at two types of settings, one where the sets of class
labels are disjoint between tasks and another where there is an overlap been
the classes seen in each task. Disjoint tasks is a commonly explored setting
[8] while having some class overlap between tasks is not often studied, but
arguably is more realistic. Slightly tangential to the settings considered
here, there has been some work looking at class overlap settings where blurry
tasks are considered [31, 4, 2], that is when a disjoint task setting is
modified by adding to each task a small number of samples sampled from any
class, often around $10\%$ of the original task’s size.

##  3 Online continual learning

_Online continual learning_ is when a learner is sequentially given batches of
data one by one, along with a task identifier for each batch, and cannot
revisit previous batches. Different batches may be drawn from different tasks
according to some unknown non-stationary process. The goal of the learner is
to be able to perform well on all tasks at the end of training. We consider
two cases, _task-incremental_ and _class-incremental_ learning, respectively
corresponding to whether the learner can access task identifiers or not at
test time [18, 31].

Specifically, we consider classification tasks. Let $X$ denote a shared data
space, and $C$ denotes the set of all classes being considered. Let $t\in T$
denote a particular task, which generates data
$S_{t}=\\{(x_{i},y_{i})|i=1,2,\ldots\\}$, containing data instances $x_{i}\in
X$ and labels $y_{i}\in C_{t}$, where $C_{t}\subset C$ are the subset of
classes relevant for this task. For simplicity, we follow previous work [8]
and assume the number of classes in each task is the same, i.e.
$|C_{t}|=k,\forall t$.

The learner is provided with a temporal sequence (length $N$) of data batches
and task identifiers $((D_{j},t_{D_{j}})|j=1,2,\ldots,N)$, where $j$ indexes
batches and $t_{D_{j}}$ denotes the task identifier for batch $D_{j}$. At each
time step $j$, the batch $D_{j}$ is a sample from a single task and the _task
identifier_ $t_{D_{j}}$ determines this task, indicating the classes
$C_{t_{D_{j}}}$ which are relevant for that task. We use the notation $D_{<j}$
to denote $\\{D_{1},D_{2},\ldots,D_{j-1}\\}$, the data from all batches seen
prior to the time step $j$.

During training, the learner receives each batch in sequential order; after
training on a batch the learner must discard all the data it does not store in
its fixed-size memory buffer. At test time, the learnt model is given an
unseen test set from all the classes seen during training and is provided with
task identifiers in the task-incremental learning scenario or without in the
class-incremental learning scenario. This experimental setup is commonly used
in the continual learning literature [5, 31].

##  4 Deep class conditional Gaussians

Figure 2: Diagram of DeepCCG’s training routine. At time $j$ the learner is
given a sample of data $D_{j}$ and has a memory of stored datapoints $M_{j}$.
The memory is randomly split into replay data $R_{j}$ and the rest
$M_{j}/R_{j}$. Learning happens by taking a gradient step on the parameters of
the embedding function $\phi$ using a log conditional marginal likelihood
function over $D_{j}$ and $R_{j}$, where $M_{j}/R_{j}$ is used to induce a
posterior over the means of the per-class Gaussians and so define the
conditional marginal likelihood function used. Therefore, training aims to
move the data points into per-class clusters, by drawing the embedded examples
of $D_{j}$ and $R_{j}$ towards their own class means and away from the other
class means, as shown by the coloured arrows in the figure. Algorithm 1
DeepCCG update step at time $j$

input $D_{j}$ (training batch), $t_{D_{j}}$ (task identifier for batch),
$M_{j}$ (memory), $f_{\phi_{j}}$ (embedding function)

Update class-conditional Gaussian classifier and embedding function:

$R_{j}=\mathrm{UniformSample}(M_{j})$

Calculate posterior of class-conditional Gaussian classifier:
$p(\mu_{c}|M_{j}/R_{j})$ for each class $c$

Calculate $\log(p(y|z=f_{\phi_{j}}(x),t_{(x,y)},M_{j}/R_{j}))$ using Eq. 6 and
posteriors $p(\mu_{c}|M_{j}/R_{j})$

Update embedding function:
$\phi_{j+1}=\phi_{j}+\eta\nabla_{\phi}\sum_{(x,y)\in D_{j}\cup
R}\log(p(y|z=f_{\phi_{j}}(x),t_{(x,y)},M_{j}/R_{j}))$

Update memory:

for each class $c$ in $M_{j}$ do

initialise $\beta$

for $1$ to $B$ do

$\beta\leftarrow\beta+\eta\nabla_{\beta}\mathcal{L}(\beta;D_{j,c},M_{j,c})$,
where $\mathcal{L}(\beta;D_{j,c},M_{j,c})$ is defined in Eq. 11

end for

Set $M_{j+1}$ to be the set of samples, with their task identifiers, with the
$m$ largest $\beta$ values

end for

We propose an empirical Bayesian method, DeepCCG, to approach the online
continual learning problem. DeepCCG consists of three main parts. Firstly, a
class-conditional Gaussian classifier is used on top of a neural network
embedding function. The classifier is learnt using in a Bayesian manner, where
by recomputing its posterior it adjusts instantly to representation shift.
Secondly, DeepCCG’s embedding function is learnt using a log conditional
marginal likelihood loss which minimises unnecessary representation shift. The
loss used to learn the embedding function calculates the learnt classifier and
so the learning of the whole method can be seen as end-to-end. Finally,
DeepCCG uses a new method based on minimising information loss to select a
subset of examples to store in memory, these examples are needed when updating
both the classifier and the embedding function, to model and reduce
representation shift. The sample selection mechanism is shown to be robust to
certain kinds of representation shift. These three parts are described in
detail below and additionally a pseudocode description of the learning of
DeepCCG is presented in Algorithm 1.

Probabilistic classifier The probabilistic model of DeepCCG is defined as
follows. Let $Z$ denote a representation space. We assume that we have a
neural network embedding function $f_{\phi}:X\rightarrow Z$ and a fixed memory
of size $m$. The memory buffer stores as one element an example $(x,y)$ and
its associated task identifier $t_{(x,y)}$—in common with previous work [5].
We define a class-conditional Gaussian model in the representation space $Z$,

$\displaystyle y|t$
$\displaystyle\sim\mathrm{Cat}(C_{t},(1/|C_{t}|)\mathbf{1})$ (1)
$\displaystyle z|y$ $\displaystyle\sim\mathcal{N}(\mu_{y},\mathbf{I})$ (2)
$\displaystyle\mu_{y}$
$\displaystyle\sim\mathcal{N}(\mathbf{0},\mathbf{V}_{0}),$ (3)

where $t$ is a given task identifier, $z=f_{\phi}(x)$, $\\{\mu_{y}|y\in C\\}$
are the parameters of the classifier being the per-class means in $Z$ and
$\mathrm{Cat}(C_{t},(1/|C_{t}|)\mathbf{1})$ is the uniform categorical
distribution over the classes of task $t$. We choose
$\mathbf{V}_{0}=a\mathbf{I}$, where in practice we take $a\rightarrow\infty$.
We do not specify a model where the covariance matrix is also a parameter as
we learn the embedding function, hence the case of a global shared covariance
is implicitly covered through learning a linear remapping to a fixed
covariance, meaning we do not lose flexibility by assuming fixed covariances.
The probalistic classifier is defined as the posterior predictive distribution
of the model, given some data $D$,

$p(y|x,t_{(x,y)},D)=\int p(y|z=f_{\phi}(x),t_{(x,y)},\theta=\\{\mu_{c}|c\in
C\\})p(\theta=\\{\mu_{c}|c\in C\\}|D)d\theta,$ (4)

where

$p(y|z=f_{\phi}(x),t_{(x,y)},\theta=\\{\mu_{c}|c\in
C\\})=\frac{p(z|y,\mu_{y})p(y|t_{(x,y)})}{\sum_{c\in
C}p(z|c,\mu_{c})p(c|t_{(x,y)})}.$ (5)

We assume the labels are conditionally independent given the task, the per-
class means $\\{\mu_{c}|c\in C\\}$ and the data instances (each an element of
$X$) and that $z$ is independent of the task given its class $y$.

To learn the classifier, DeepCCG needs to compute the posterior of the per-
class means, while being able to adapt to representation shift. The posterior
is tractable and easy to compute in one step, as shown in Appendix D Eq. 13,
as we use a class-conditional Gaussian model and a conjugate prior for the
per-class means, which is the main reason we use this model along with its
good performance when used on top of neural network embeddings [29, 15]. If
$f_{\phi}$ is fixed, so there is no representation shift, we can update our
beliefs about the per-class means on seeing batch $D_{j}$ and its task
identifier $t_{D_{j}}$ by simply using Bayes rule, calculating the posterior
$p(\\{\mu_{c}|c\in C\\}|D_{j},D_{<j})$. However, in our setting, we need to
update $f_{\phi}$ continually and so there is representation shift, which
changes the value of $p(\\{\mu_{c}|c\in C\\}|D_{j},D_{<j})$. We cannot
recompute $p(\\{\mu_{c}|c\in C\\}|D_{j},D_{<j})$ as we are unable to store all
the previous examples in memory. Therefore, DeepCCG stores in memory a set of
representative examples $M$ with which we can compute an approximate posterior
$p(\\{\mu_{c}|c\in C\\}|M)$ after a change in $f_{\phi}$. It is important to
note that we can compute this posterior in one step and hence that we can
quickly adapt the classifier to representation shift, reducing forgetting and
improving learning as the classifier and representation are better matched.

Learning the embedding DeepCCG uses an empirical Bayesian procedure to update
the embedding function $f_{\phi}$, that is, it uses a novel log conditional
marginal likelihood loss term. At time $j$, in response to the arrival of
batch $D_{j}$, with task identifier $t_{D_{j}}$, and having received the
memory buffer $M_{j}$, DeepCCG takes the following steps to update the
embbeding function (shown in Figure 2). First, it selects a random set
$R_{j}\subset M_{j}$, of size $r$, from the memory buffer to replay. Then it
calculates the output of the classifier for each example $(x,y)\in D_{j}\cup
R_{j}$, which is the posterior predictive distribution
$p(y|f_{\phi_{j}}(x),t_{(x,y)},M_{j}/R_{j})$, conditioning on the rest of the
examples $M_{j}/R_{j}$ and where $\phi_{j}$ are the current parameters of the
embedding function and $t_{(x,y)}$ is the task identifier for the example. The
posterior predictive distributions are calculated using the embedded data
instances and the posterior of the per-class means. It can be shown to be, by
using Eq. 4 (see Appendix D for the derivation):

$p(y|z=f_{\phi_{j}}(x),t_{(x,y)},M_{j}/R_{j})=\frac{\mathcal{N}\left(z|\overline{M_{j,y}^{Z}/R_{j}^{Z}},(1+\frac{1}{m-r})\mathbf{I}\right)}{\sum_{c\in
C_{t_{(x,y)}}}\mathcal{N}\left(z|\overline{M_{j,c}^{Z}/R_{j}^{Z}},(1+\frac{1}{m-r})\mathbf{I}\right)}$
(6)

where $M_{j,y}^{Z}=\\{f_{\phi_{j}}(x)|(x,y^{\prime})\in M_{j}\land
y^{\prime}=y\\}$ are the embeddings of samples in the memory buffer of class
$y$. $R_{j}^{Z}$ is defined likewise and we use the notation $\overline{S}$ to
denote the mean of the elements of a set $S$. As in meta-learning [13, 17],
the posterior predictive distributions are used as a fixed likelihood term for
each individual unseen data item. This leads to a conditional log-marginal
likelihood as the objective in DeepCCG’s embedding update rule:

$\phi_{j+1}=\phi_{j}+\eta\nabla_{\phi}\sum_{(x,y)\in D_{j}\cup
R_{j}}\log(p(y|z=f_{\phi_{j}}(x),t_{(x,y)},M_{j}/R_{j})).$ (7)

The reason DeepCCG uses a conditional log-marginal likelihood loss is because
conditioning the likelihood on some examples $M_{j}/R_{j}$ stabilises the
output of the probabilistic classifier and hence the loss term used. This is
because by conditioning the marginal likelihood on $M_{j}/R_{j}$, the
posterior DeepCCG averages over is more informative than using the
unconditioned prior, having some belief of where the position of embedded data
instances should be and so provides a better signal to fit the embedding
function. Additionally by replaying the examples $R_{j}$, treating them like
new data, the loss leverages a new type of replay, where performing replay is
widely known to be effective at reducing forgetting and minimising unnecessary
representation shift [36, 40, 27].

Sample selection A key component to DeepCCG is how to select samples to store
in the memory buffer. We focus on ensuring the least amount of information is
lost about the position of the per-class means of the class conditional
Gaussian classifier, after a shift in representation. Hence, because all the
information available to inform the value of the classifiers per-class mean
parameters is encapsulated in the full posterior over the seen data, we target
choosing a set of memory samples that best recreate that posterior, preventing
as much information loss as possible. Therefore, to perform sample selection
we minimise the KL divergence between two posterior distributions: the
posterior over parameters induced by the new memory being optimized, and the
posterior induced by the current batch and the old memory. We keep the number
of samples in memory for each class balanced, so minimising the KL divergence
is equivalent to minimising the per-class KL divergence which reduces to the
squared Euclidean distance between the means of a class’s embedded data.
Formally, we select the new memory using,

$\displaystyle M_{j+1,y}$
$\displaystyle=\operatorname*{arg\,min}_{M^{\prime}_{y}}(\mathrm{KL}(p(\mu_{y}|D_{j,y},M_{j,y})\lVert
p(\mu_{y}|M^{\prime}_{y})))$ (8)
$\displaystyle=\operatorname*{arg\,min}_{M^{\prime}_{y}}(\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime Z}}\rVert^{2}_{2}),$ (9)

where $M^{\prime}_{y}\subseteq(D_{j,y}\times\\{t_{D_{j}}\\})\cup M_{j,y}$,
$M_{j+1,y}$ is the new memory to be selected for class $y$, $M_{j,y}$ is the
is the set of samples of class $y$ in memory when receiving the current batch
of data and $D_{j,y}$ is the set of samples of class $y$ in the current batch.
Importantly, this sample selection mechanism is robust to representation
shift, when modeled as an additive i.i.d. change in representation. This is
because, given the shifted representations $z^{*}=z+\epsilon_{z}$, where $z\in
D^{Z}\cup M^{Z}$ and $\epsilon_{z}$ is i.i.d. sampled from an arbitrary
distribution with bounded mean and variance, we have that (proved in Appendix
E):

$\mathbb{E}[\mathrm{KL}(p(\mu_{y}|D^{Z^{*}}_{j,y},M^{Z^{*}}_{j,y})\lVert
p(\mu_{y}|M^{\prime Z^{*}}_{y})))]=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime Z}}\rVert^{2}_{2}+\nu(\frac{1}{|M^{\prime
Z}_{y}|}-\frac{1}{|D_{j,y}^{Z}\cup M_{j,y}^{Z}|}),$ (10)

where the expectation is taken over the additive shift terms $\epsilon$, $\nu$
is the sum over the per-dimension variances of the shift distribution,
$D^{Z^{*}}_{j,y}=\\{z^{*}=z+\epsilon_{z}|z\in D^{Z}_{j,y}\\}$ and
$M^{*Z}_{j,y}$ is defined likewise. Therefore, in expectation, the samples
selected to be stored in memory after a shift in representation are still the
best samples to store in memory, in terms of preserving posterior information.
Hence, our sample selection mechanism is robust to this type of representation
shift.

Performing the minimization in Eq. 9 is computationally hard, so we utilise a
relaxation of the problem using _lasso_ [14], whereby our method selects the
new memory by assigning to each embedded input $z_{i}$ a zero-to-one weight
$\beta_{i}$ and performing gradient decent on the loss

$\mathcal{L}(\beta;D_{j,y},M_{j,y})=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\frac{1}{\lVert\beta\rVert_{1}}\sum_{\stackrel{{\scriptstyle
i|(x_{i},y_{i})\in}}{{D_{j,y}\cup
M_{j,y}}}}\beta_{i}z_{i}\rVert^{2}_{2}+\lambda\lVert\beta\rVert_{1}.$ (11)

Then, after termination, our method selects the $m$ examples with the largest
weights to be the examples stored in memory, where they are stored along with
their task identifiers.

##  5 Experiments

###  5.1 Experimental setup

#### Benchmarks

In our experiments we look at task and class incremental learning in both the
disjoint tasks and shifting window settings. Furthermore, we consider three
different datasets: CIFAR-100 [22], MiniImageNet [37] and CIFAR-10 [22], where
both CIFAR-100 and MiniImageNet contain 100 classes, while CIFAR-10 contains
10 classes. For disjoint tasks, we split data evenly across a certain number
of tasks while assigning all samples with a particular class to only one
task—this is often called the ‘split tasks’ setting in previous work [8, 5].
We split CIFAR-10 into 5 tasks where there are 2 classes per task and for
CIFAR-100 and MiniImageNet we split the dataset into 20 tasks with 5 classes
per task. In the alternative shifting window setting, we split the datasets up
into tasks by fixing an ordering of the classes $c_{1},\ldots,c_{k}$ and
construct the $t$th task by selecting a set of samples from classes
$c_{t},\ldots,c_{t+l}$, where $l$ is the window length. No two tasks contain
the same example and each task has the same number of samples per-class. For
CIFAR-10 we use a window length of $2$ and for CIFAR-100 and MiniImageNet we
use a window length of $5$. Additionally, for all experiments we train with
$500$ samples per-class. We evaluate the methods using a standard metric for
continual learning, average accuracy[5]. The average accuracy of a method is
the mean accuracy on a reserved set of test data across all tasks after
training on all tasks.

Methods We compare DeepCCG to representative methods of the main paradigms of
continual learning. For regularisation methods we compare against a fixed
memory variant of EWC [19, 21]; for parameter-isolation methods we compare to
PackNet [26], but only in the task-incremental setting as it requires task
identifiers at test time. For replay methods, which includes DeepCCG, we
compare against ER-Reservoir [7], A-GEM [5], EntropySS [39], and GSS [2];
EntropySS and GSS are different memory sample selection strategies for ER.
When training, all methods are given task identifiers which state what classes
are in a task. Task identifiers are also given at test time in the task-
incremental scenario while in class-incremental learning the task-identifier
at test time is treated as stating a data instance can belong to any class. We
also compare against two baselines: SGD which is when learning is performed
using SGD with no modification and Multi-Task which is an upper bound and is
when we learn the base neural network offline—with task identifiers for the
task-incremental experiments and without for the class-incremental
experiments. All methods use the same embedding network for all experiments
which is a ResNet18 with six times fewer filters and Instance Normalisation
[35] instead of Batch Normalisation layers [20], which is similar to other
work [27, 10]. A batch size of $10$ is used throughout, with all replay
methods having a replay size of $10$. A memory size of $10$ samples per-class
is used for the task-incremental setting, and $30$ for the harder class-
incremental setting. Further experimental details are proviced in Appendix F.

###  5.2 Results

In the task-incremental experiments, we see from Table 1 that DeepCCG performs
the best out of the methods compared. For example, DeepCCG on CIFAR-100
achieves mean average accuracies of $56.62\%$ and $60.46\%$ for the shifting
window and disjoint tasks settings, respectively, which are $2.57\%$ and
$2.15\%$ better than any other method. ER-reservoir and GSS are the next best
performing methods, which alternate in achieving the second best performance
in the task-incremental experiments, except for the results on MiniImageNet in
the disjoint tasks setting where EntropySS performs second best. This shows
that which memory selection method for experience replay is best depends on
the dataset and setting, with not one performing always better than the rest.
Overall, DeepCCG had an average performance improvement of $2.145\%$ over the
other methods in the task-incremental experiments, this shows that DeepCCG
performs well in the task-incremental scenario where, especially for the
disjoint tasks setting, it is hard to get large performance improvements [31].

Table 1: Results of task-incremental learning experiments on CIFAR-10, CIFAR-100 and MiniImageNet, where SW and DT stand for the shifting window and disjoint tasks settings, respectively. We report mean average accuracy with their standard errors across three independent runs. | CIFAR-10 | CIFAR-100 | MiniImageNet
---|---|---|---
Method | SW | DT | SW | DT | SW | DT
EWC | $58.68_{\pm 1.88}$ | $63.33_{\pm 0.87}$ | $36.65_{\pm 1.07}$ | $42.39_{\pm 0.79}$ | $32.42_{\pm 1.13}$ | $29.57_{\pm 0.69}$
PackNet | $69.29_{\pm 2.27}$ | $66.97_{\pm 1.47}$ | $40.21_{\pm 0.96}$ | $50.28_{\pm 0.58}$ | $34.15_{\pm 1.28}$ | $37.86_{\pm 1.71}$
ER-reservoir | $70.44_{\pm 0.81}$ | $66.71_{\pm 0.90}$ | $54.05_{\pm 0.63}$ | $58.31_{\pm 1.08}$ | $41.04_{\pm 1.54}$ | $40.29_{\pm 1.08}$
A-GEM | $57.63_{\pm 2.16}$ | $57.28_{\pm 2.61}$ | $29.01_{\pm 1.45}$ | $39.00_{\pm 0.75}$ | $26.97_{\pm 1.26}$ | $30.08_{\pm 1.86}$
EntropySS | $67.93_{\pm 0.63}$ | $64.96_{\pm 0.91}$ | $51.80_{\pm 0.70}$ | $56.75_{\pm 0.81}$ | $40.03_{\pm 0.61}$ | $41.12_{\pm 0.51}$
GSS | $71.55_{\pm 1.45}$ | $67.30_{\pm 1.27}$ | $48.20_{\pm 0.33}$ | $49.92_{\pm 0.50}$ | $37.91_{\pm 0.49}$ | $38.77_{\pm 0.98}$
DeepCCG (ours) | $\mathbf{74.65_{\pm 2.00}}$ | $\mathbf{69.29_{\pm 0.89}}$ | $\mathbf{56.62_{\pm 0.29}}$ | $\mathbf{60.46_{\pm 0.24}}$ | $\mathbf{42.18_{\pm 0.45}}$ | $\mathbf{43.04_{\pm 0.64}}$
SGD | $63.21_{\pm 2.09}$ | $63.58_{\pm 0.31}$ | $35.63_{\pm 1.27}$ | $42.50_{\pm 1.40}$ | $33.23_{\pm 0.67}$ | $31.61_{\pm 0.70}$
Multi-Task (UB) | $96.20_{\pm 0.69}$ | $73.37_{\pm 1.82}$ | $90.42_{\pm 1.87}$ | $59.76_{\pm 0.49}$ | $89.81_{\pm 0.25}$ | $48.46_{\pm 1.21}$
Table 2: Results of class-incremental learning experiments on CIFAR-10, CIFAR-100 and MiniImageNet, where SW and DT stand for the shifting window and disjoint tasks settings, respectively. We report mean average accuracy with their standard errors across three independent runs. | CIFAR-10 | CIFAR-100 | MiniImageNet
---|---|---|---
Method | SW | DT | SW | DT | SW | DT
EWC | $14.36_{\pm 1.64}$ | $13.85_{\pm 2.17}$ | $3.77_{\pm 0.39}$ | $4.51_{\pm 0.19}$ | $2.73_{\pm 0.21}$ | $2.84_{\pm 0.19}$
ER-reservoir | $18.96_{\pm 1.18}$ | $16.29_{\pm 0.75}$ | $7.76_{\pm 0.91}$ | $7.19_{\pm 0.56}$ | $5.93_{\pm 1.05}$ | $5.15_{\pm 0.22}$
A-GEM | $11.98_{\pm 0.82}$ | $14.88_{\pm 0.52}$ | $1.92_{\pm 0.04}$ | $3.01_{\pm 0.13}$ | $1.21_{\pm 0.16}$ | $1.83_{\pm 0.04}$
EntropySS | $8.93_{\pm 1.11}$ | $15.69_{\pm 0.78}$ | $5.85_{\pm 0.47}$ | $7.87_{\pm 0.71}$ | $2.93_{\pm 0.45}$ | $5.63_{\pm 0.40}$
GSS | $16.11_{\pm 1.23}$ | $17.61_{\pm 0.30}$ | $6.34_{\pm 0.20}$ | $5.18_{\pm 0.44}$ | $4.52_{\pm 0.25}$ | $4.84_{\pm 0.16}$
DeepCCG (ours) | $\mathbf{26.87_{\pm 0.47}}$ | $\mathbf{24.27_{\pm 0.44}}$ | $\mathbf{18.00_{\pm 0.72}}$ | $\mathbf{17.32_{\pm 0.27}}$ | $\mathbf{11.71_{\pm 0.39}}$ | $\mathbf{11.88_{\pm 0.71}}$
SGD | $13.59_{\pm 1.76}$ | $13.76_{\pm 1.22}$ | $4.09_{\pm 0.14}$ | $3.93_{\pm 0.29}$ | $1.28_{\pm 0.06}$ | $2.14_{\pm 0.22}$
Multi-Task (UB) | $40.57_{\pm 2.33}$ | $40.57_{\pm 2.33}$ | $20.22_{\pm 0.42}$ | $20.22_{\pm 0.42}$ | $12.41_{\pm 0.69}$ | $12.41_{\pm 0.69}$

For the experiments on class-incremental learning, we see that DeepCCG
performs well, outperforming the other methods. The results of the class-
incremental experiments are shown in Table 2 and displays for instance that
DeepCCG on CIFAR-100 achieves mean average accuracies of $18.00\%$ and
$17.32\%$ on the shifting window and disjoint tasks settings, respectively.
The performance of DeepCCG on CIFAR-100 are $10.40\%$ and $9.45\%$ better than
any other method. Overall, DeepCCG across all datasets and settings in class-
incremental learning has an average performance improvement of $7.72\%$, which
shows that the method performs well and with the results on task-incremental
learning shows that DeepCCG is effective in both scenarios. Also, it is
interesting to note that DeepCCG performs better, in terms of performance
improvement over the other methods, in the class-incremental experiments than
the task-incremental experiments, achieving an average performance improvement
of $2.145\%$ in task-incremental learning and $7.72\%$ in class incremental
learning. This finding is surprising as in DeepCCG there is no interaction
between the mean parameters of classes which do not appear together in a
training task. Therefore, these non-interacting mean parameters could be close
together, harming performance in class-incremental learning, but this does not
seem to be the case in practice and improving upon this is a direction for
future work.

Shifting window setting The results on the shifting window setting show that
current methods do not exploit the increased task overlap in the setting and
hence do not utilize the increased ability to transfer knowledge between
tasks. This is shown in the results as the performance of the methods are very
similar between the shifting window and disjoint tasks settings; while, in the
task-incremental experiments, the difference between the multi-task upper
bound’s performance and the methods is much larger in the shifting window
setting than that for the disjoint tasks setting.111In the class-incremental
experiments the multi-task upper bound does not use task identifiers, hence we
can only observe the differences in upper bound performance in the task-
incremental experiments. This suggests that current methods do not perform
between-task transfer well and so in settings of increased task overlap, where
between-task knowledge transfer is more beneficial, current methods do not
achieve accuracies near to that which is possible. Therefore, in these
settings, where similar tasks are located temporally near to each other, a
common real world property, there is a large space for new continual learning
methods to be proposed which can more effectively perform between-task
transfer.  Figure 3: Binned scatter plot showing for the MiniImageNet disjoint
tasks setting the change in accuracy against the mean change in representation
after learning on a batch for the test data of the first task. Table 3:
Results of performing an ablation on DeepCCG, where we report results on
DeepCCG using reservoir sampling instead of its own sample selection method
(DeepCCG-reservoir), when we replace the class-conditional Gaussian model with
a standard classifier head (DeepCCG-standardHead) and when we do both
modifications, in which case our method reduces to the ER-reservoir method. We
report the mean average accuracy with their standard errors across three
independent runs on the CIFAR-100 shifting window setting using task-
incremental learning. Method Average Accuracy ER-reservoir $54.05_{\pm 0.626}$
DeepCCG-reservoir $49.95_{\pm 0.743}$ DeepCCG-standardHead $44.05_{\pm 0.264}$
DeepCCG $56.62_{\pm 0.288}$ Analysis of representation shift As part of our
experiments we assess how well DeepCCG’s classifier update adapts to
representation shift compared to other methods, showing that DeepCCG’s
performance is more stable with respect to representation shift. To measure
representation shift, after learning on the first task and for each incoming
batch of data, we recorded the mean distance over the first task’s test data
between its representation before and after updating on the incoming batch.
Additionally, we measure the change in accuracy on first task’s test data
before and after updating the method on the incoming batch. We present these
results for task-incremental learning on MiniImageNet in Figure 3, displaying
the best performing methods from our experiments. We also recorded results for
EntropySS but as they were very similar to ER-reserviors we do not include
them in the figure to aid clarity; instead they are shown in Appendix G.2.
Figure 3 shows that for the same amount of representation shift DeepCCG’s
accuracy changes less than the other methods, as its line of best fit is the
least steep. This demonstrates that the classifier of DeepCCG is more robust
and better adapts to representation shift, validating DeepCCGs use of a
Bayesian classifier which in one step adapts to representation shift.

Ablation study One way to view DeepCCG is as a relative of ER-reservoir, where
the methods differ in the sample section mechanism used and the type and
learning of the probabilistic classifier and embedding function. Therefore, to
analyse DeepCCG, we perform an ablation, creating two adaptations of our
method, DeepCCG-reservoir and DeepCCG-standardHead, by changing components of
DeepCCG to what they are in ER-reservoir. DeepCCG-reservoir is when we select
samples to store in memory using reservoir sampling. DeepCCG-standardHead is
when we replace the class conditional Gaussian model with a standard output
head (a fully connected layer, then a softmax) and learn the embedding
function using the standard ER loss, while still using DeepCCG’s sample
selection method. The results for the ablation are presented in Table 3 and
show that both DeepCCG-reservoir and DeepCCG-standardHead perform much worse
than DeepCCG. Therefore, we have shown that all of DeepCCG’s novel components
are needed in conjunction for DeepCCG to perform well. We also perform an
ablation on the size of memory in Appendix G.1, where we show that DeepCCG
performs the best over all the memory sizes tested on.

##  6 Conclusions

In this work we have demonstrated that using a replay-based empirical Bayesian
procedure, DeepCCG, for online continual learning is a promising direction,
reducing the effect of representation shift when training. A key part of
DeepCCG is to select samples to store in memory by approximately selecting the
best subset that minimises the KL divergence between the posterior induced by
all the currently accessible data and the posterior induced by the subset.
This sample selection mechanism was found to be robust to general types of
representation shift. The results show that DeepCCG performs well for online
continual learning, outperforming all other methods in the commonly used
disjoint tasks setting [18] as well as the under-explored shifting window
setting, where there is an increased overlap between the tasks. For future
work, potential directions would be to look at applying this approach to other
probabilistic models and applying it to settings with imbalanced and/or noisy
data [34, 41, 2].

## Acknowledgments and Disclosure of Funding

## References

  * Aljundi et al. [2019a] Rahaf Aljundi, Lucas Caccia, Eugene Belilovsky, Massimo Caccia, Min Lin, Laurent Charlin, and Tinne Tuytelaars.  Online Continual Learning with Maximal Interfered Retrieval.  In _Proceedings of the 33rd Conference on the Advances in Neural Information Processing Systems_ , pages 11849–11860, 2019a.
  * Aljundi et al. [2019b] Rahaf Aljundi, Min Lin, Baptiste Goujaud, and Yoshua Bengio.  Gradient Based Sample Selection for Online Continual Learning.  In _Proceedings of the 33rd Conference on the Advances in Neural Information Processing Systems_ , pages 11816–11825, 2019b.
  * Antoniou et al. [2020] Antreas Antoniou, Massimiliano Patacchiola, Mateusz Ochal, and Amos Storkey.  Defining Benchmarks for Continual Few-shot Learning.  _arXiv preprint arXiv:2004.11967_ , 2020.
  * Bang et al. [2021] Jihwan Bang, Heesu Kim, YoungJoon Yoo, Jung-Woo Ha, and Jonghyun Choi.  Rainbow Memory: Continual Learning with a Memory of Diverse Samples.  In _Proceedings of the 2021 IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 8218–8227, 2021.
  * Chaudhry et al. [2019a] Arslan Chaudhry, Marc’Aurelio Ranzato, Marcus Rohrbach, and Mohamed Elhoseiny.  Efficient Lifelong Learning with A-GEM.  In _Proceedings of the 7th International Conference on Learning Representations_ , 2019a.
  * Chaudhry et al. [2019b] Arslan Chaudhry, Marcus Rohrbach, Mohamed Elhoseiny, Thalaiyasingam Ajanthan, Puneet K Dokania, Philip HS Torr, and Marc’Aurelio Ranzato.  On Tiny Episodic Memories in Continual Learning.  _arXiv preprint arXiv:1902.10486_ , 2019b.
  * Chaudhry et al. [2020] Arslan Chaudhry, Naeemullah Khan, Puneet Dokania, and Philip Torr.  Continual Learning in Low-rank Orthogonal Subspaces.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, _of the 34th Conference on the Advances in Neural Information Processing Systems_ , volume 33, pages 9900–9911, 2020.
  * Delange et al. [2021] Matthias Delange, Rahaf Aljundi, Marc Masana, Sarah Parisot, Xu Jia, Ales Leonardis, Greg Slabaugh, and Tinne Tuytelaars.  A Continual Learning Survey: Defying Forgetting in Classification Tasks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021.  doi: 10.1109/TPAMI.2021.3057446.
  * Ebrahimi et al. [2020] Sayna Ebrahimi, Mohamed Elhoseiny, Trevor Darrell, and Marcus Rohrbach.  Uncertainty-guided Continual Learning with Bayesian Neural Networks.  In _Proceedings of the 8th International Conference on Learning Representations_ , 2020.
  * Farajtabar et al. [2019] Mehrdad Farajtabar, Navid Azizan, Alex Mott, and Ang Li.  Orthogonal Gradient Descent for Continual Learning.  _arXiv preprint arXiv:1910.07104_ , 2019.
  * Farquhar and Gal [2018] Sebastian Farquhar and Yarin Gal.  Towards Robust Evaluations of Continual Learning.  _arXiv preprint arXiv:1805.09733_ , 2018.
  * Farquhar and Gal [2019] Sebastian Farquhar and Yarin Gal.  A Unifying Bayesian View of Continual Learning.  _arXiv preprint arXiv:1902.06494_ , 2019.
  * Garnelo et al. [2018] Marta Garnelo, Dan Rosenbaum, Christopher Maddison, Tiago Ramalho, David Saxton, Murray Shanahan, Yee Whye Teh, Danilo Rezende, and S. M. Ali Eslami.  Conditional Neural Processes.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80 of _Proceedings of Machine Learning Research_ , pages 1704–1713, 2018.
  * Hastie et al. [2009] Trevor Hastie, Robert Tibshirani, and Jerome H Friedman.  _The Elements of Statistical Learning: Data Mining, Inference, and Prediction_.  Springer, 2nd edition, 2009.
  * Hayes and Kanan [2020] Tyler L Hayes and Christopher Kanan.  Lifelong machine learning with deep streaming linear discriminant analysis.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition workshops_ , pages 220–221, 2020.
  * Henning et al. [2021] Christian Henning, Maria Cervera, Francesco D' Angelo, Johannes von Oswald, Regina Traber, Benjamin Ehret, Seijin Kobayashi, Benjamin F. Grewe, and João Sacramento.  Posterior Meta-Replay for Continual Learning.  In _Proceedings of the 35th conference on the Advances in Neural Information Processing Systems_ , pages 14135–14149, 2021.
  * Hospedales et al. [2021] Timothy M Hospedales, Antreas Antoniou, Paul Micaelli, and Amos J Storkey.  Meta-Learning in Neural Networks: A Survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2021.  doi: 10.1109/TPAMI.2021.3079209.
  * Hsu et al. [2018] Yen-Chang Hsu, Yen-Cheng Liu, Anita Ramasamy, and Zsolt Kira.  Re-evaluating Continual Learning Scenarios: A Categorization and Case for Strong Baselines.  In _Proceedings of the 3rd Continual Learning Workshop, at the 32nd Conference on the Advances in Neural Information Processing Systems_ , 2018\.
  * Huszár [2018] Ferenc Huszár.  Note on the Quadratic Penalties in Elastic Weight Consolidation.  _Proceedings of the National Academy of Sciences_ , 115(11):E2496–E2497, 2018.  doi: 10.1073/pnas.1717042115.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift.  In _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pages 448–456, 2015.
  * Kirkpatrick et al. [2017] James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinska, et al.  Overcoming Catastrophic Forgetting in Neural Networks.  _Proceedings of the national academy of sciences_ , 114(13):3521–3526, 2017.
  * Krizhevsky [2009] Alex Krizhevsky.  Learning Multiple Layers of Features from Tiny Images.  _Preprint_ , 2009.
  * Kurle et al. [2020] Richard Kurle, Botond Cseke, Alexej Klushyn, Patrick van der Smagt, and Stephan Günnemann.  Continual Learning with Bayesian Neural Networks for Non-Stationary Data.  In _Proceedings of the 8th International Conference on Learning Representations_ , 2020.
  * Lotfi et al. [2022] Sanae Lotfi, Pavel Izmailov, Gregory Benton, Micah Goldblum, and Andrew Gordon Wilson.  Bayesian Model Selection, the Marginal Likelihood, and Generalization.  _arXiv preprint arXiv:2202.11678_ , 2022.
  * Mai et al. [2021] Zheda Mai, Ruiwen Li, Jihwan Jeong, David Quispe, Hyunwoo Kim, and Scott Sanner.  Online Continual Learning in Image Classification: An Empirical Survey.  _arXiv preprint arXiv:2101.10423_ , 2021.
  * Mallya and Lazebnik [2018] Arun Mallya and Svetlana Lazebnik.  PackNet: Adding Multiple Tasks to a Single Network by Iterative Pruning.  In _Proceedings of the 2018 IEEE Conference on Computer Vision and Pattern Recognition_ , pages 7765–7773, 2018.
  * Mirzadeh et al. [2020] Seyed Iman Mirzadeh, Mehrdad Farajtabar, Razvan Pascanu, and Hassan Ghasemzadeh.  Understanding the Role of Training Regimes in Continual Learning.  In _Proceedings of the 33rd conference on the Advances in Neural Information Processing Systems_ , pages 7308–7320, 2020.
  * Nguyen et al. [2018] Cuong V. Nguyen, Yingzhen Li, Thang D. Bui, and Richard E. Turner.  Variational Continual Learning.  In _International Conference on Learning Representations_ , 2018.
  * Ostapenko et al. [2022] Oleksiy Ostapenko, Timothee Lesort, Pau Rodríguez, Md Rifat Arefin, Arthur Douillard, Irina Rish, and Laurent Charlin.  Foundational models for continual learning: An empirical study of latent replay.  _arXiv preprint arXiv:2205.00329_ , 2022.
  * Parisi et al. [2019] German I. Parisi, Ronald Kemker, Jose L. Part, Christopher Kanan, and Stefan Wermter.  Continual Lifelong Learning with Neural Networks: A review.  _Neural Networks_ , 113:54 – 71, 2019.  ISSN 0893-6080.
  * 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 _Procceding of the 16th European Conference on Computer Vision_ , pages 524–540, 2020.
  * Rao et al. [2019] Dushyant Rao, Francesco Visin, Andrei Rusu, Razvan Pascanu, Yee Whye Teh, and Raia Hadsell.  Continual Unsupervised Representation Learning.  In _Proceedings of the 33rd Conference on the Advances in Neural Information Processing Systems_ , 2019.
  * Shim et al. [2021] Dongsub Shim, Zheda Mai, Jihwan Jeong, Scott Sanner, Hyunwoo Kim, and Jongseong Jang.  Online Class-Incremental Continual Learning with Adversarial Shapley Value.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence_ , 2021.
  * Sun et al. [2022] Shengyang Sun, Daniele Calandriello, Huiyi Hu, Ang Li, and Michalis Titsias.  Information-Theoretic Online Memory Selection for Continual Learning.  In _Proceedings of the 10th International Conference on Learning Representations_ , 2022.
  * Ulyanov et al. [2016] Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky.  Instance Normalization: the Missing Ingredient for Fast Stylization.  _arXiv preprint arXiv:1607.08022_ , 2016.
  * van de Ven and Tolias [2019] Gido M van de Ven and Andreas S Tolias.  Three Scenarios for Continual Learning.  _arXiv preprint arXiv:1904.07734_ , 2019.
  * Vinyals et al. [2016] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, and Daan Wierstra.  Matching Networks for One Shot Learning.  In _Proceedings of the 30th Conference on the Advances in neural information processing systems_ , 2016.
  * Vitter [1985] Jeffrey S Vitter.  Random Sampling with a Reservoir.  _ACM Transactions on Mathematical Software_ , 11(1):37–57, 1985.
  * Wiewel and Yang [2021] Felix Wiewel and Bin Yang.  Entropy-Based Sample Selection for Online Continual Learning.  In _Proceedings of the 28th European Signal Processing Conference_ , pages 1477–1481, 2021.  doi: 10.23919/Eusipco47968.2020.9287846.
  * Wu et al. [2022] Tongtong Wu, Massimo Caccia, Zhuang Li, Yuan-Fang Li, Guilin Qi, and Gholamreza Haffari.  Pretrained Language Models in Continual Learning: A Comparative Study.  In _Proceedings of the 10th International Conference on Learning Representations_ , 2022.
  * Yoon et al. [2022] Jaehong Yoon, Divyam Madaan, Eunho Yang, and Sung Ju Hwang.  Online Coreset Selection for Rehearsal-based Continual Learning.  In _Proceedings of the 10th International Conference on Learning Representations_ , 2022.
  * Zeno et al. [2018] Chen Zeno, Itay Golan, Elad Hoffer, and Daniel Soudry.  Task Agnostic Continual Learning Using Online Variational Bayes.  _arXiv preprint arXiv:1803.10123_ , 2018.

##  Appendix A Reproducibility statement

To aid in the reproduction of our experiments, we provide a detailed
explanation in Section 5.1 of the experimental setup and provide additional
experimental details in Appendix F. Also, we provide the code used for the
experiments in the supplementary material.

##  Appendix B Ethics statement

Continual Learning is a growing field and has the potential to have a large
societal impact in the future. For example, a potential application of
continual learning is for privacy-aware machine learning on mobile devices,
where resource constraints mean that often a continual learning solution is
necessary. Another example of the potential use of continual leaning is for
the adaptation of large models, as re-training large models from scratch when
new data becomes available is expensive and environmentally costly, therefore
continual learning methods may provide a way of updating these large models
with minimal resource costs. So, this means that research in continual
learning could have a positive impact on society, however it is also important
to realise that without conscious effort continual learning may have negative
impacts as well. For instance, when deploying continual learning in the real
world, mitigating social bias will be a problem and importantly solutions
proposed when using static datasets—for example, modifying the dataset in some
way—are often not straightforwardly applicable in continual learning.
Therefore, before continual learning methods can be used fully in the real
world many problems, known and potentially unknown, need to be addressed but
if through future research they are addressed, continual learning can have a
positive societal impact.

##  Appendix C Limitations

We mention the limitations of DeepCCG throughout the paper. For example, we
show that none of the methods, including DeepCCG, achieve performances close
offline training performance for the task-incremental shifting window setting.
This shows that there is much work to be done in this setting and for settings
like it, where there is greater informational overlap between tasks,
suggesting the need for new methods that are better at performing across task
knowledge transfer. Also, we point out that we do not adapt our method when
changing between task-incremental and class-incremental learning. This is
notable as in DeepCCG there is no interaction between the mean parameters and
associated Gaussians of classes that do not appear in the same task at
training time and so it could be the case that some of these classes’
Gaussians significantly overlap, degrading performance in the class-
incremental scenario. However, in our experiments this does not seem to be the
case, but still a possible direction for future work would be to create a
modification of DeepCCG that is specialised to class-incremental learning.

##  Appendix D Details of learning the embedding function

For DeepCCG, at time $j$, to compute the update to the embedding function
$f_{\phi_{j}}$, when given a batch $D_{j}$ and a corresponding memory $M_{j}$,
we proceed using the following steps. Firstly, we randomly sample
$R_{j}\subset M_{j}$ of size $r$ from memory. Then using only the other
samples in memory, $M_{j}/R_{j}$, we compute the posterior density for each
class mean— $\mu_{c}$, with $c\in C$:

$\displaystyle p(\mu_{c}|M_{j}/R_{j})$
$\displaystyle=p(\mu_{c}|M_{j,c}^{z}/R_{j}^{z})$ (12)
$\displaystyle=\mathcal{N}\left(\mu_{y}|\overline{M_{j,c}^{z}/R_{j}^{z}},\frac{1}{m-r}\mathbf{I}\right),$
(13)

where $M_{j,c}^{z}=\\{f_{\phi_{j}}(x)|(x,y)\in M_{j}\land y=c\\}$ are the
embeddings of points in the memory buffer with class $y$. $R_{j}^{z}$ is
defined likewise and we use the notation $\overline{S}$ to denote the mean of
the elements of a set $S$. Then we compute the posterior distribution of the
embedded inputs $z\in D_{j}^{z}\cup R_{j}^{z}$ for each class $c\in C$
utilizing

$\displaystyle p(z|c,M_{j}/R_{j})$
$\displaystyle=p(z|c,M_{j,c}^{z}/R_{j}^{z})$ (14) $\displaystyle=\int
p(z|c,\mu_{c})p(\mu_{c}|M_{j,c}^{z}/R_{j}^{z})d\mu_{c}$ (15)
$\displaystyle=\mathcal{N}\left(z|\overline{M_{j,c}^{z}/R_{j}^{z}},(1+\frac{1}{m-r})\mathbf{I}\right).$
(16)

Next, we compute the posterior predictive for each sample $(x,y)\in D_{j}\cup
R_{j}$ with a task identifier $t_{(x,y)}$, which is known for samples in the
current batch and is stored by our method for samples stored in memory, and
where $z=f_{\phi_{j}}(x)$ using

$\displaystyle p(y|z,t_{(x,y)},M_{j}/R_{j})$
$\displaystyle=\frac{p(z|y,M_{j,y}^{z}/R_{j}^{z})p(y|t_{(x,y)})}{\sum_{c\in
C}p(z|Y=c,M_{j,c}^{z}/R_{j}^{z})p(Y=c|t_{(x,y)})}$ (17)
$\displaystyle=\frac{p(z|y,M_{j,y}^{z}/R_{j}^{z})}{\sum_{c\in
C_{t_{(x,y)}}}p(z|Y=c,M_{j,c}^{z}/R_{j}^{z})}$ (18)

Finally, we update the embedding function by performing a gradient step using
the formula

$\phi_{j+1}=\phi_{j}+\eta\nabla_{\phi}\sum_{(x,y)\in D_{j}\cup
R_{j}}\log(p(y|z=f_{\phi_{j}}(x),t_{(x,y)},M_{j}/R_{j})),$ (19)

which can be seen as a per-sample log conditional marginal likelihood [24].

By using Eq. 16 and 18, the closed form of the posterior predictive
distribution for a sample $(x,y)$ with task identifier $t_{(x,y)}$ and where
$z=f_{\phi_{j}}(x)$ is

$\displaystyle p(y|z,t_{(x,y)},M_{j}/R_{j})$
$\displaystyle=\frac{p(z|y,M_{j,y}^{z}/R_{j}^{z})}{\sum_{c\in
C_{t_{(x,y)}}}p(z|Y=c,M_{j,c}^{z}/R_{j}^{z})}$ (20)
$\displaystyle=\frac{\mathcal{N}\left(z|\overline{M_{j,y}^{z}/R_{j}^{z}},(1+\frac{1}{m-r})\mathbf{I}\right)}{\sum_{c\in
C_{t_{(x,y)}}}\mathcal{N}\left(z|\overline{M_{j,c}^{z}/R_{j}^{z}},(1+\frac{1}{m-r})\mathbf{I}\right)}$
(21)

##  Appendix E Proof of robustness of sample selection mechanism to i.i.d.
representation shift

We show that given a shift in representation that DeepCCG’s sample selection
mechanism maintains the property in expectation that is minimises the KL-
Divergence between the posterior over the currently accessible data and the
posterior induced by the samples selected to be store in memory. The proof is
as follows: Let $Z$ be the representation space and assume we are given a
batch $D_{j,y}^{Z}=$ and memory $M_{j,y}^{Z}=\\{f_{\phi}(x)|(x,y^{\prime})\in
M_{j}\land y^{\prime}=y\\}$ of data points in $Z$ for a given class $y$. We
define the representations shift as $z^{*}=z+\epsilon_{z}$ where $z\in
D_{j,y}^{Z}\cup M_{j,y}^{Z}$ and $\epsilon_{z}$ is i.i.d. sampled from an
arbitrary distribution with bounded mean and variance (i.e.
$\mathbb{E}[\epsilon_{z}]<\infty$ and
${\textrm{Var}}\,(\epsilon_{z})<\infty)$). Furthermore, define
$\nabla_{z}=\epsilon_{z}-\mathbb{E}[\epsilon_{z}]$, hence it is $\epsilon$
shifted to have zero mean. Additionally, let
$D_{j,y}^{Z^{*}}=\\{z^{*}=z+\epsilon_{z}|z\in D_{j,y}^{Z}\\}$ and define
$M^{Z^{*}}_{j,y}$ and $M_{y}^{\prime Z^{*}}$ likewise. Therefore we have that,

$\displaystyle\mathbb{E}[\mathrm{KL}(p(\mu_{y}|D^{Z^{*}}_{j,y},M^{Z^{*}}_{j,y})\lVert
p(\mu_{y}|M^{\prime
Z^{*}}_{y})))]=\mathbb{E}[\lVert\overline{D_{j,y}^{Z^{*}}\cup
M_{j,y}^{Z^{*}}}-\overline{M_{y}^{\prime Z^{*}}}\rVert^{2}_{2}]$ (22)
$\displaystyle=\mathbb{E}[\lVert\frac{1}{|D_{j,y}^{Z^{*}}\cup
M_{j,y}^{Z^{*}}|}\sum_{z^{*}\in D_{j,y}^{Z^{*}}\cup
M_{j,y}^{Z^{*}}}z^{*}-\frac{1}{|M_{y}^{\prime Z^{*}}|}\sum_{z^{*}\in
M_{y}^{\prime Z^{*}}}z^{*}\rVert^{2}_{2}]$ (23)
$\displaystyle=\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z^{*}}\cup
M_{j,y}^{Z^{*}}|}\sum_{z^{*}\in D_{j,y}^{Z^{*}}\cup
M_{j,y}^{Z^{*}}}z^{*}_{k}-\frac{1}{|M_{y}^{\prime Z^{*}}|}\sum_{z^{*}\in
M_{y}^{\prime Z^{*}}}z^{*}_{k})^{2}]$ (24)
$\displaystyle=\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}(z_{k}+\mathbb{E}[\epsilon_{z,k}]+\eta_{z,k})-\frac{1}{|M_{y}^{\prime
Z}|}\sum_{z\in M_{y}^{\prime
Z}}(z_{k}+\mathbb{E}[\epsilon_{z,k}]+\eta_{z,k}))^{2}]$ (25)
$\displaystyle=\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}(z_{k}+\eta_{z,k})-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in
M_{y}^{\prime Z}}(z_{k}+\eta_{z,k})$ (26)
$\displaystyle\;+(\frac{1}{|D_{j,y}^{Z}\cup M_{j,y}^{Z}|}\sum_{z\in
D_{j,y}^{Z}\cup M_{j,y}^{Z}}\mathbb{E}[\epsilon_{z,k}]-\frac{1}{|M_{y}^{\prime
Z}|}\sum_{z\in M_{y}^{\prime Z}}\mathbb{E}[\epsilon_{z,k}]))^{2}]$ (27)
$\displaystyle=\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}(z_{k}+\eta_{z,k})-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in
M_{y}^{\prime Z}}(z_{k}+\eta_{z,k}))^{2}]\text{\; (as }\epsilon_{z,k}\text{
are i.i.d)}$ (28)
$\displaystyle=\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}z_{k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}z_{k}$ (29) $\displaystyle+\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\eta_{z,k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}\eta_{z,k})^{2}]$ (30)
$\displaystyle=\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}z_{k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}z_{k})^{2}]$ (31) $\displaystyle+2\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}z_{k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}z_{k})(\frac{1}{|D_{j,y}^{Z}\cup M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\eta_{z,k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}\eta_{z,k})]$ (32) $\displaystyle+\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\eta_{z,k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}\eta_{z,k})^{2}]$ (33)
$\displaystyle=\sum_{k=0}^{d}(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}z_{k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}z_{k})^{2}$ (34)
$\displaystyle+\sum_{k=0}^{d}\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\eta_{z,k}-\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}\eta_{z,k})^{2}]\text{\; (as }\mathbb{E}[\eta_{z,k}]=0\text{)}$ (35)
$\displaystyle=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime
Z}}\rVert^{2}_{2}+\sum_{k=0}^{d}\left(\mathbb{E}[(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\eta_{z,k})^{2}]+\mathbb{E}[(\frac{1}{|M_{y}^{\prime
Z}|}\sum_{z\in M_{y}^{\prime Z}}\eta_{z,k})^{2}]\right.$ (36)
$\displaystyle-2\mathbb{E}[(\left.\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\eta_{z,k})(\frac{1}{|M_{y}^{\prime Z}|}\sum_{z\in M_{y}^{\prime
Z}}\eta_{z,k})]\right)$ (37) $\displaystyle=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime
Z}}\rVert^{2}_{2}+\sum_{k=0}^{d}\left(\frac{{\textrm{Var}}\,(\epsilon_{k})}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}+\frac{{\textrm{Var}}\,(\epsilon_{k})}{|M_{y}^{\prime
Z}|}\right.$ (38) $\displaystyle-\left.\frac{2}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}||M_{y}^{\prime Z}|}\sum_{z\in D_{j,y}^{Z}\cup
M_{j,y}^{Z}}\sum_{z^{\prime}\in M_{y}^{\prime
Z}}\mathbb{E}[\eta_{z,k}\eta_{z^{\prime},k}]\right)\text{\; (using formula for
variance of means)}$ (39) $\displaystyle=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime
Z}}\rVert^{2}_{2}+(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}+\frac{1}{|M_{y}^{\prime
Z}|})\sum_{k=0}^{d}{\textrm{Var}}\,(\epsilon_{k})$ (40)
$\displaystyle+\frac{2}{|D_{j,y}^{Z}\cup M_{j,y}^{Z}||M_{y}^{\prime
Z}|}\sum_{k=0}^{d}\sum_{z\in M_{y}^{\prime Z}}\mathbb{E}[\eta_{z,k}^{2}]$ (41)
$\displaystyle=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime
Z}}\rVert^{2}_{2}+(\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}+\frac{1}{|M_{y}^{\prime
Z}|})\sum_{k=0}^{d}{\textrm{Var}}\,(\epsilon_{k})-\frac{2}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|}\sum_{k=0}^{d}{\textrm{Var}}\,(\epsilon_{k})$ (42)
$\displaystyle=\lVert\overline{D_{j,y}^{Z}\cup
M_{j,y}^{Z}}-\overline{M_{y}^{\prime
Z}}\rVert^{2}_{2}+(\frac{1}{|M_{y}^{\prime Z}|}-\frac{1}{|D_{j,y}^{Z}\cup
M_{j,y}^{Z}|})\sum_{k=0}^{d}{\textrm{Var}}\,(\epsilon_{k})$ (43)

which completes the proof and where in the main paper we define
$\nu=\sum_{k=0}^{d}{\textrm{Var}}\,(\epsilon_{k})$.

##  Appendix F Additional experimental details

In addition to the experimental details mentioned in the main body of the
paper, there are a few more details to mention. Firstly, for methods with
hyperparameters we performed a grid search using the same experimental set up
as the real experiments and $10\%$ of the training data as validation data.
This led to the selection of the hyperparameters of EWC and PackNet, the two
methods with free hyperparameters, shown in Tables 4 and 5. Secondly, we use
the same learning rate of $0.1$ and the standard gradient decent optimiser for
all methods. These were chosen by looking at the commonly selected values in
previous work [27] and were shown to be performative for all methods tested.
Lastly, for the multi-task upper bound we train using two epochs in the task-
incremental scenario and three epochs in the class-incremental scenario, to
more fairly upper bound the performance of the methods.

Table 4: Values selected for the hyperparameters of EWC and PackNet in the task-incremental learning experiments, which are the regularisation coefficient and the percentage of available filters to be used per task, respectively. SW stands for shifting window and DT stands for disjoint tasks. | CIFAR-10 | CIFAR-100 | MiniImageNet
---|---|---|---
Method | SW | DT | SW | DT | SW | DT
EWC | $1$ | $6$ | $6$ | $6$ | $2$ | $9$
PackNet | $0.3$ | $0.3$ | $0.1$ | $0.1$ | $0.05$ | $0.2$
Table 5: Values selected for the hyperparameters of EWC in the class-incremental learning experiments, which is the regularisation coefficient. SW stands for shifting window and DT stands for disjoint tasks. | CIFAR-10 | CIFAR-100 | MiniImageNet
---|---|---|---
Method | SW | DT | SW | DT | SW | DT
EWC | $1$ | $1$ | $6$ | $1$ | $6$ | $1$

##  Appendix G Additional results

###  G.1 Results on using different memory sizes

Table 6: Results of experiments looking at the effect of memory buffer size $m$ for the replay methods tested, using the shifting window setting on CIFAR-100 in task-incremental learning scenario. We report mean average accuracy with their standard errors across three independent runs. Method | m=750 | m=1000 | m=1250
---|---|---|---
ER-reservoir | $53.17_{\pm 0.656}$ | $54.05_{\pm 0.626}$ | $55.22_{\pm 0.592}$
A-GEM | $27.18_{\pm 1.091}$ | $29.01_{\pm 1.449}$ | $27.87_{\pm 0.172}$
EntropySS | $50.52_{\pm 0.725}$ | $51.80_{\pm 0.700}$ | $53.34_{\pm 0.372}$
GSS | $47.15_{\pm 0.766}$ | $48.20_{\pm 0.332}$ | $46.18_{\pm 0.341}$
DeepCCG (ours) | $\mathbf{53.42_{\pm 0.460}}$ | $\mathbf{56.62_{\pm 0.288}}$ | $\mathbf{57.98_{\pm 0.514}}$

One additional useful experiment is looking at the relationship between
performance and the size of memory used for DeepCCG. Therefore, in Table 6 we
show the performance of DeepCCG and the other replay methods compared against
with varying memory size. Table 6 shows that when the memory size is increased
to $m=1250$, DeepCCG has an improvement in average accuracy relative to other
methods, as it achieves $2.76\%$ better than any other method for $m=1250$,
while for $m=1000$ it achieves $2.57\%$ better than any other method, a
$0.19\%$ improvement. When the memory size is decreased to $m=750$, we see
that DeepCCG’s performance drops more than other methods as it is only
$0.25\%$ better than other methods in this case. Therefore, our experiments
show that compared to other replay methods DeepCCG’s performance increases the
most when $m$ increases and that for small buffer sizes DeepCCG performs less
well, potentially due to the fact that the examples in the memory buffer are
used to infer the posterior over the means of the per-class Gaussians and so
the method needs a given amount of examples to specify the means well. We also
note that in our experiments the performance ranking of the methods does not
change with $m$.

###  G.2 Additional representation shift results

Figure 4: Binned scatter plot showing for the MiniImageNet disjoint tasks
setting the change in accuracy against the mean change in representation after
learning on a batch for the test data of the first task.


# Limits of random trees††thanks: MSC2010 Subject Classification: 05C80

Attila Deák
<EMAIL_ADDRESS>MTA-ELTE ”Numerical Analysis and Large Networks” Research
Group, 1117 Budapest, Pázmány P. s. 1/c., Hungary

###### Abstract

Local convergence of bounded degree graphs was introduced by Benjamini and
Schramm [2]. This result was extended further by Lyons [6] to bounded average
degree graphs. In this paper, we study the convergence of a random tree
sequence $(T_{n})$, where the probability of a given tree $T$ is proportional
to $\prod_{v_{i}\in V(T)}d(v_{i})!$. We show that this sequence is convergent
and describe the limit object, which is a random infinite rooted tree.

Keywords: sparse graph limits, random trees, degree sequence

††Research was supported by the ERC Grant Nr.: 227701††The final publication
is available at http://link.springer.com/article/10.1007%2Fs10474-013-0321-0

##  1 Introduction

Limits of graph sequences with bounded degree have been studied extensively
over the last decade. A natural extension is to study the case when we only
require bounded average degree. For instance trees have average degree less
than $2$, but in general a sequence of trees can have unbounded maximum
degree. A limit theory for trees has been established by Aldous [1] and also
by Elek and Tardos [5].

We do not follow their path, but use the limit theory for bounded average
degree graphs, described by Lyons [6]. Define $T_{n}$ as the random tree on
the nodes $\\{1,2,\cdots,n\\}$ so that for a given tree $T$ with degrees
$d_{i}$ we have

$\mathds{P}(T_{n}=T)={\prod_{i=1}^{n}d_{i}!\over(n-2)!{3n-3\choose n-2}}.$

We will show that $T_{n}$ converges and has a limit, a random infinite rooted
tree. Let ${\cal A}_{n}$ denote the set of trees with $n$ nodes. For
motivation consider the following process on ${\cal A}_{n}$:

  * •

Choose a random edge and also one of its endpoints uniformly $(X,V_{old})$.

  * •

Take a uniformly chosen neighbor of $V_{old}$: $V_{new}$.

  * •

If $X=V_{new}$, then do nothing, or else remove the edge $(X,V_{old})$ and add
a new edge $(X,V_{new})$.

This clearly defines a Markov chain $(A_{t}^{n})$ on ${\cal A}_{n}$. Let
$\Pi_{n}$ denote the stationary distribution of the process defined above. It
is easy to prove that the Markov chain defined above is reversible and
aperiodic. From the reversibility we can also compute the stationary
distribution:

$\Pi_{n}(T)=\frac{\prod_{i=1}^{n}d_{i}!}{C},$

where $C=(n-2)!{3n-3\choose n-2}$, see Remark 1 below.

The distribution of $T_{n}$ depends only on the degrees of its vertices and
not on the exact structure of the tree itself. The natural question is:
Considering only trees, can the degree sequence alone determine the
convergence of a tree sequence? We show that with the above distribution the
random tree sequence converges. We do not know how much this result can be
extended by defining other distributions, which ensure random local
convergence.

Our paper is organized as follows. In Section 2 we give the basic definitions
and state the main theorem of this paper. Then in Section 3 we prove basic
bounds and asymptotics for the degrees of $T_{n}$, such as the expected number
of degree $d$ vertices and the expected value of the maximum degree. In
Section 4 we investigate subgraph densities and in Section 5 we describe the
limit object.

##  2 Basic definitions

For a finite simple graph $G$, let $B_{G}(v,R)$ be the rooted $R$-ball around
the node $v$, that is the subgraph induced by the nodes at distance at most
$R$ from $v$. Given a positive integer $R$, a finite rooted graph and a
probability distribution $\rho$ on rooted graphs, let $p(R,F,\rho)$ denote the
probability that the graph $F$ is rooted isomorphic to the $R$-ball around the
root of a rooted graph chosen with distribution $\rho$. For a finite graph
$G$, let $U(G)$ denote the distribution of rooted graphs obtained by choosing
a uniform random node of $G$ as the root.

######  Definition 1.

Let $(G_{n})$ be a sequence of random finite graphs, $\rho$ a probability
distribution on rooted graphs. We say that the random local limit of $G_{n}$
is $\rho$, if for any positive integer $R$ and finite rooted graph $F$, we
have

$\lim_{n\rightarrow\infty}\mathds{P}(|p(R,F,U(G_{n}))-p(R,F,\rho)|>\epsilon)=0.$

######  Theorem 1.

Let $X_{n}$ be a random tree from the distribution $\Pi_{n}$. $X_{n}$ has a
random local limit, which is an infinite rooted random tree.

Let $T$ be a tree on $n$ nodes and denote by $X_{n}$ a random tree with
distribution $\Pi_{n}$. We know that

$\mathds{P}(X_{n}=T)={1\over C}\prod_{i=1}^{n}d_{i}!,$

where $d_{i}$ is the degree of the $i$th vertex of the tree $T$. It is easy to
see that there are ${n-2\choose d_{1}-1,d_{2}-1,\cdots,d_{n}-1}$ trees that
realize the same degree sequence. From this it follows that for a given degree
sequence $(d_{i})_{i=1}^{n}$, we get

$\mathds{P}((d_{i})_{i=1}^{n})=\frac{1}{C}\prod_{i=1}^{n}d_{i}!{n-2\choose
d_{1}-1,d_{2}-1,\cdots,d_{n}-1}=\\\
=\frac{1}{C}\prod_{i=1}^{n}d_{i}!\frac{(n-2)!}{\prod_{i=1}^{n}(d_{i}-1)!}=\frac{(n-2)!}{C}\prod_{i=1}^{n}d_{i}.$
(1)

To be able to compute probabilities about the degree sequence, we need to
calculate the sum of the product of possible degree sequences. The following
lemma states an easy result about this.

######  Lemma 1.

$\sum_{\begin{subarray}{c}\sum_{i=1}^{n}d_{i}=m\\\
d_{i}>0\end{subarray}}\prod_{i=1}^{n}d_{i}={n+m-1\choose m-n}.$

Proof. Let $f(x)=\left(\sum_{i=1}^{\infty}ix^{i}\right)^{n}$ and denote the
sum in the lemma by $M$. It is easy to see that $M$ is the coefficient of
$x^{m}$ in:

$f(x)=\left(\sum_{i=1}^{\infty}ix^{i}\right)^{n}=\left({x\over(1-x)^{2}}\right)^{n}={x^{n}\over(1-x)^{2n}},$

hence it follows that $M=(-1)^{m-n}{-2n\choose m-n}={m+n-1\choose m-n}$. ∎

######  Remark 1.

From Lemma 1, it follows that $\sum_{(d_{i})}\prod_{i}d_{i}={3n-3\choose
n-2}$, where the summation is over the possible degree sequences. From this
using (1) $C=(n-2)!{3n-3\choose n-2}$ also follows.

##  3 Degree distribution and the maximum degree

Using Lemma 1 we can compute the expected number of degree $d$ vertices and
the maximum degree.

######  Lemma 2.

Let $M=\sum_{i=1}^{k}x_{i}$ and assume that $M\leq n+k-2$. Then the
probability that the $i$th vertex has degree $x_{i}$ ($i=1,\ldots,k$) is

$\mathds{P}(d_{i}=x_{i};\,i=1,\cdots,k)=\frac{{3n-M-k-3\choose
n-M+k-2}}{{3n-3\choose n-2}}\prod_{i=1}^{k}x_{i}.$

Proof. Using the above notions with (1) we get:

${3n-3\choose
n-2}\mathds{P}(d_{i}=x_{i}\,;i=1,\cdots,k)=\sum_{\begin{subarray}{c}\sum
d_{i}=2n-2\\\ d_{j}=x_{j}\,j\leq k\end{subarray}}\prod_{i}d_{i}=$
$\prod_{i=1}^{k}x_{i}\sum_{\begin{subarray}{c}\sum_{j=k+1}^{n}d_{j}=\\\
=2n-M-2\end{subarray}}\prod_{j=k+1}^{n}d_{j}={3n-M-k-3\choose
n-M+k-2}\prod_{i=1}^{k}x_{i},$

where the last equation follows from Lemma 1 and this is what we wanted to
prove. ∎

Let us denote the maximum degree in a tree $T$ by $D(T)=\max_{i}d_{i}$. Now
the following theorem is true:

######  Theorem 2.

For every $\epsilon>0$, we have

$(1-\epsilon-o(1))\log_{3}n\leq\mathds{E}(D(X_{n}))\leq(1+\epsilon+o(1))\log_{3}n,\textrm{
as }n\rightarrow\infty.$

We bound the expected value by bounding the probabilities $\mathds{P}(D>k)$
and $\mathds{P}(D\leq k)$ with Lemma 3 and Lemma 4 respectively. To simplify
the notation, we let $D=D(X_{n})$.

######  Lemma 3.

For every $\delta>0$, there exists $n_{0}$, such that $\forall n>n_{0}$

$\mathds{P}(D>k)<(1+\delta)\frac{4}{3}\frac{k}{3^{k}}n.$

Proof: From Lemma 2 it follows that

$\mathds{P}(d_{i}=k)=k\frac{{3n-k-4\choose n-k-1}}{{3n-3\choose n-2}}<{4\over
3}{(1+\delta)k\over 3^{k}},\ \forall\delta>0,n>n_{0}(\delta),$

and so

$\mathds{P}(d_{i}>k)<\sum_{j=k+1}^{n}{4\over 3}{(1+\delta)j\over
3^{j}}<\sum_{j=k+1}^{\infty}{4\over 3}{(1+\delta)j\over
3^{j}}=(1+\delta){2k+3\over 3^{k+1}}.$

Now the statement of the lemma follows, as
$\mathds{P}(D>k)<n\mathds{P}(d_{i}>k)$. ∎

######  Lemma 4.

$\mathds{P}(D\leq k)<{1\over 9}\sqrt{n}\,\exp\left\\{-n{4\over 9}{(k+1)\over
3^{k}}\right\\}$

Proof: It is easy to see that

$\mathds{P}(D\leq k)={1\over{3n-3\choose
n-2}}\sum_{\begin{subarray}{c}d_{i}\leq k\\\
\sum_{i}d_{i}=2n-2\end{subarray}}\prod_{i=1}^{n}d_{i}.$

Here the sum is just the coefficient of $x^{n-2}$ in
$P(x)=\Bigl{(}1+2x+3x^{2}+\ldots+kx^{k-1}\Bigr{)}^{n}$. As $P(x)=\sum
a_{i}x^{i}$ and $\forall i,\ a_{i}\geq 0$, we get an upper bound on $a_{i}$:

$a_{i}\leq{P(x_{0})\over x_{0}^{i}},$

for any $x_{0}>0$. Hence it follows that

${3n-3\choose n-2}\mathds{P}(D\leq k)\leq P({1\over
3})3^{n-2}=3^{n-2}\left(\sum_{i=1}^{k}{i\over 3^{i-1}}\right)^{n}\leq
3^{n-2}\left({9\over 4}-{k+1\over 3^{k}}\right)^{n}=$ $=3^{n-2}\left({9\over
4}\right)^{n}\left(1-{4\over 9}{k+1\over 3^{k}}\right)^{n}<{1\over
9}\left({27\over 4}\right)^{n}\exp\left\\{-n{4\over 9}{k+1\over
3^{k}}\right\\}.$

By using Stirling’s formula, we get

$\mathds{P}(D\leq k)<{1\over 9}\sqrt{n}\,\exp\left\\{-n{4\over 9}{k+1\over
3^{k}}\right\\},$

the desired inequality. ∎

Now we can upper bound the expected value as follows:

$\mathds{E}(D)\leq k_{1}\mathds{P}(D\leq
k_{1})+k_{2}\mathds{P}(D>k_{1})+(n-1)\mathds{P}(D>k_{2}),$

where

$k_{1}=(1+\epsilon)\log_{3}n\textrm{ and }k_{2}=\log^{3}_{3}n,$

Therefore it follows from Lemmas 3 and 4 that

$\mathds{E}(D)\leq(1+\epsilon)\log_{3}n+{\log^{3}_{3}n\over
n^{\epsilon+o(1)}}+{\log^{3}_{3}n\over n}=(1+\epsilon+o(1))\log_{3}n,\textrm{
as }n\rightarrow\infty.$

Also

$\mathds{E}(D)\geq(1-\epsilon)\log_{3}n\mathds{P}\left(D>(1-\epsilon)\log_{3}n\right)\geq(1-\epsilon-o(1))\log_{3}n,\textrm{
as }n\rightarrow\infty,$

which proves our theorem. ∎

##  4 Labeled subgraph densities

Form now on let $T$ be a fixed tree on $k$ nodes. Assign values $r_{i}$ to
each node $i$ of $T$ and call it the remainder degree of node $i$. Let
$S=\\{s_{1},s_{2},\ldots,s_{k}\\}$ be an ordered subset of
$[n]=\\{1,2,\ldots,n\\}$ $(s_{i}\neq s_{j},\,i\neq j)$. Now by $T_{S}$ we
denote the tree $T$, with label $s_{i}$ at node $i$.

Similarly let $F$ be a forest with $m_{F}$ nodes and $c_{F}$ connected
components. Denote these components by $C_{1},\cdots C_{c_{F}}$. As above,
define the remainder degrees for $F$, and denote them by $(r_{1},\ldots
r_{m_{F}})$. Denote by $F_{S}$ the labeled forest with label $s_{i}$ at node
$i$.

For two labeled trees $T_{S},T^{\prime}_{S^{\prime}}$, with remainder degrees
$r,r^{\prime}$ we define the operation gluing in the usual way. We identify
nodes $i\in V(T),j\in V(T^{\prime})$ if $s_{i}=s^{\prime}_{j}$ and keep the
label $s_{i}(=s^{\prime}_{j})$. For nodes $i\ (j)$, where $s_{i}\notin
S^{\prime}(s^{\prime}_{j}\notin S)$, we do nothing. If $S\cap
S^{\prime}=\emptyset$, then the resulting graph is just the disjoint union. We
say that a gluing is valid, if it results in a forest and
$s_{i}=s^{\prime}_{j}\Rightarrow r_{i}=r^{\prime}_{j}\,\forall i,j$, and
denote it by $g(T_{S},T^{\prime}_{S^{\prime}})$. We define the gluing of two
labeled forests similarly. Let

$X_{S}^{T}=I\\{\phi:i\mapsto s_{i}\text{ is a homomorphism from }T\text{ to
}X_{n}\text{, and }\forall i,\ d_{s_{i}}=d^{T}_{i}+r_{i}\\}$
$X_{n}^{T}=\sum_{S\subseteq[n]}X_{S}^{T}=inj(T,X_{n}).$

We define $X^{F}_{S},X^{F}_{n}$ similarly for a forest $F$. Also let
$A_{S}^{T}=X^{T}_{S}-\mathds{E}(X^{T}_{S})$. If it does not make any
confusion, we use $m_{1},c_{1},X_{S},A_{S}$ instead of
$m_{F_{1}},c_{F_{1}},X_{S}^{T},A_{S}^{T}$.

######  Theorem 3.

For an arbitrary tree $T$ on $k$ nodes with remainder degrees
$(r_{i})_{i=1}^{k}$ and $\forall\epsilon>0$, we have

$\mathds{P}\left({|X^{T}_{n}-\mathds{E}(X^{T}_{n})|\over
n}>\epsilon\right)\leq{c_{k,r}\over n^{2}\epsilon^{4}}.$

We want to bound the deviation from the expectation by bounding the $4$th
moment of $X_{n}^{T}$.

######  Lemma 5.

With the above notions

$\mathds{E}\left(\left(X_{n}^{T}-\mathds{E}(X^{T}_{n})\right)^{4}\right)=O(n^{2}).$

######  Remark 2.

Theorem 3 is a direct corollary of Lemma 5 as

$\mathds{P}\left({|X^{T}_{n}-\mathds{E}(X^{T}_{n})|\over
n}>\epsilon\right)\leq{\mathds{E}\left(\left(X_{n}^{T}-\mathds{E}(X^{T}_{n})\right)^{4}\right)\over
n^{4}\epsilon^{4}}={c_{k,r}\over n^{2}\epsilon^{4}}.$

To get this bound we regard $X_{n}^{T}$ as a sum of indicator variables
$X_{S}^{T}$, so we need to compute only probabilities
$\mathds{P}(X_{S}^{T}=1)$ and
$\mathds{P}(X_{S}^{F}=1|X_{S^{\prime}}^{F^{\prime}}=1)$ for special forests
$F,F^{\prime}$.

######  Lemma 6.

Let $F$ be an arbitrary forest on $m$ nodes with remainder degrees
$r=(r_{1},\cdots,r_{m})$. Let $R=\sum_{i}r_{i}$ and denote by $c$ the number
of connected components of $F$. The probability that on an ordered subset
$S=(s_{1},\cdots,s_{m})$ of the nodes of $X_{n}$ we see the forest $F$ and
$\forall i,\ d_{s_{i}}=d^{F}_{i}+r_{i}$ is

$\mathds{P}(X_{S}^{F}=1)=\frac{(n-m+c-2)!}{(n-2)!}{{3n-R-3m+2c-3\choose
n-R-m+2c-2}\over{3n-3\choose n-2}}H(r,F),$

where $H(r,F)$ is a constant depending only on $F$ and $r$.

Proof: First we want to compute
$\mathds{P}(X_{S}^{F}=1\,\big{|}\,(d_{i})_{i=1}^{n})$. Given the degree
sequence $(d_{i})$, the distribution of $X_{n}$ is uniform on the possible
trees realizing $(d_{i})$. It is easy to check (simply by contracting the
connected components to one node, counting the trees and blowing back the
components) that the number of trees, with degree sequence $(d_{i})$ and
having $F$ on the first $m$ vertices and having $r_{i}$ edges going out from
the forest at the $i$th node is

$\displaystyle\prod\limits_{i=1}^{c}\left[{R_{i}!\over\prod\limits_{j\in
C_{i}}r_{j}!}\right]{n-m+c_{F}-2\choose
R_{1}-1,\cdots,R_{c}-1,d_{m+1}-1,\cdots,d_{n}-1}.$ (2)

Here $R_{i}=\sum_{j\in C_{i}}r_{j}$. Since the number of trees realizing
$(d_{i})$ is ${n-2\choose d_{1}-1,d_{2}-1,\cdots,d_{n}-1}$, it follows that

$\mathds{P}(X_{\\{1,\cdots,m\\}}^{F}=1|d_{i})=\\\
={\displaystyle{n-m+c-2\choose
R_{1}-1,\cdots,R_{c}-1,d_{m+1}-1,\cdots,d_{n}-1}\over\displaystyle{n-2\choose
d_{1}-1,d_{2}-1,\cdots,d_{n}-1}}\displaystyle\prod\limits_{i=1}^{c}{R_{i}!\over\prod\limits_{j\in
C_{i}}r_{j}!}.$

After simplifying, and using symmetry, we get the following equation:

$\mathds{P}(X_{S}^{F}=1|d_{i})=\\\
={(n-m+c-2)!\over(n-2)!}\prod_{i=1}^{c}\left[R_{i}\prod_{j\in
C_{i}}(d_{j}^{F}+r_{j}-1)\cdot\ldots\cdot(r_{j}+1)\right].$ (3)

Now to get the desired probability, we use Lemma 2 with $k=m$ and
$M=(2m-c)+R$:

$\mathds{P}(X_{S}^{F}=1)=\sum_{d_{i}}\mathds{P}(X_{S}^{F}=1|d_{i}){\prod_{i=1}^{n}d_{i}\over{3n-3\choose
n-2}}=\\\ ={(n-m+c-2)!\over(n-2)!}{{3n-R-3m+2c-3\choose
n-R-m+2c-2}\over{3n-3\choose n-2}}\prod_{i=1}^{c}\left[R_{i}\prod_{j\in
C_{i}}\left[(d_{j}^{F}+r_{j})\cdots(r_{j}+1)\right]\right]=\\\
={(n-m+c-2)!\over(n-2)!}{{3n-R-3m+2c-3\choose n-R-m+2c-2}\over{3n-3\choose
n-2}}H(r,F),$

which is the claimed equation. ∎

######  Lemma 7.

Let $F_{1},F_{2}$ be two forests with remainder degrees $r,r^{\prime}$ and
labels $S_{1},S_{2}$. If there is a valid gluing of the labeled forests
$F_{1}$ and $F_{2}$ then let $F_{1,2}=g(F_{1},F_{2})$. Also let
$m_{1,2}=|V(F_{1,2})|$, $c_{1,2}=\\{$the number of components of $F_{1,2}\\}$,
$R_{1,2}=\sum_{V(F_{1,2})}r_{i}$. We have

$\mathds{P}(X_{S_{1}}^{F_{1}}=1|X_{S_{2}}^{F_{2}}=1)=\\\
{(n-m_{1,2}+c_{1,2}-2)!\over(n-m_{2}+c_{2}-2)!}{{3n-R_{1,2}-3m_{1,2}+2c_{1,2}-3\choose
n-R_{1,2}-m_{1,2}+2c_{1,2}-2}\over{3n-R_{2}-3m_{2}+2c_{2}-3\choose
n-R_{2}-m_{2}+2c_{2}-2}}{H(r_{1,2},F_{1,2})\over H(r^{\prime},F_{2})},$ (4)

Proof: The proof follows in a straightforward way from the definition of the
conditional probability. ∎

######  Remark 3.

It is easy to see that ${H(r_{1,2},F_{1,2})\over
H(r^{\prime},F_{2})}=H(r,F_{1})$ if $S_{1}\cap S_{2}=\emptyset$.

######  Remark 4.

We can rewrite equation (4) as a rational polynomial in $n$ as follows.

$\mathds{P}(X_{S_{1}}^{F_{1}}=1|X_{S_{2}}^{F_{2}}=1){H(r^{\prime},F_{2})\over
H(r_{1,2},F_{1,2})}=\\\
={(n-m_{1,2}+c_{1,2}-2)!\over(n-m_{2}+c_{2}-2)!}{{3n-R_{1,2}-3m_{1,2}+2c_{1,2}-3\choose
n-R_{1,2}-m_{1,2}+c_{1,2}-2}\over{3n-R_{2}-3m_{2}+2c_{2}-3\choose
n-R_{2}-m_{2}+c_{2}-2}}=\\\ {2^{2(m_{1,2}-m_{2})}\over
3^{R_{1,2}-R_{2}+3(m_{1,2}-m_{2})-2(c_{1,2}-c_{2})}}{P(n;R_{1,2},m_{1,2},c_{1,2},R_{2},m_{2},c_{2})\over
Q(n;R_{1,2},m_{1,2},c_{1,2},R_{2},m_{2},c_{2})}$ (5)

Where

$P(n;x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})=\\\
=n^{x_{1}-x_{4}+3(x_{2}-x_{5})-2(x_{3}-x_{6})}-n^{x_{1}-x_{4}+3(x_{2}-x_{5})-2(x_{3}-x_{6})-1}\\\
\left[(x_{1}+x_{4}+x_{2}+x_{5}-x_{3}-x_{6}+3){(x_{1}-x_{4}+x_{2}-x_{5}-x_{3}+x_{6})\over
2}+\right.\\\
\left.+(2(x_{2}+x_{5})-x_{3}-x_{6}+1){2(x_{2}-x_{5})-x_{3}+x_{6}\over
4}\right]+O(n^{x_{1}-x_{4}+3(x_{2}-x_{5})-2(x_{3}-x_{6})-2})$

and

$Q(n;x_{1},x_{2},x_{3},x_{4},x_{5},x_{6})=\\\
=n^{x_{1}-x_{4}+4(x_{2}-x_{5})-3(x_{3}-x_{6})}-n^{x_{1}-x_{4}+4(x_{2}-x_{5})-3(x_{3}-x_{6})-1}\\\
\left[(x_{2}+x_{5}-x_{3}-x_{6}+3){(x_{2}-x_{5}-x_{3}+x_{6})\over 2}+\right.\\\
\left.+(x_{1}+x_{4}+3(x_{2}+x_{5})-2(x_{3}+x_{6})+5){x_{1}-x_{4}+3(x_{2}-x_{5})-2(x_{3}-x_{6})\over
6}\right]+\\\ +O(n^{x_{1}-x_{4}+4(x_{2}-x_{5})-3(x_{3}-x_{6})-2}).$

From this it also follows that

$\mathds{E}(X_{S_{1}}^{F_{1}}|X_{S_{2}}^{F_{2}}=1)=O(n^{m_{2}-m_{1,2}+c_{1,2}-c_{2}})$
(6)

and

$\mathds{E}(X_{S_{1}}^{F_{1}}|X_{S_{2}}^{F_{2}}=1)-\mathds{E}(X_{S_{1}}^{F_{1}})=O(n^{m_{2}-m_{1,2}+c_{1,2}-c_{2}-1})=O(n^{-m_{1}+c_{1}-1}),$
(7)

if $S_{1}\cap S_{2}=\emptyset$ (since in this case $m_{1,2}-m_{2}=m_{1}$ and
$c_{1,2}-c_{2}=c_{1}$).

Now we have arrived at the main lemma of Chapter 4. Here we want to bound the
following sum

$\sum_{S_{1},S_{2},S_{3},S_{4}}\mathds{E}(A^{T}_{S_{1}}A^{T}_{S_{2}}A^{T}_{S_{3}}A^{T}_{S_{4}}).$

We split this sum in 5 parts, depending on the sizes of the intersections
$S_{i}\cap S_{j},\ (1\leq i<j\leq 4)$. We can change the indeces so that one
of the following holds:

  * •

Case I: $S_{i}$’s are disjoint

  * •

Case II: $|S_{3}\cap S_{4}|=i,\ i\leq k$ and $S_{1},S_{2},S_{3}\cup S_{4}$ are
disjoint

  * •

Case III: $|S_{1}\cap S_{2}|=i,\ |S_{3}\cap S_{4}|=j$ and $(S_{1}\cup
S_{2})\cap(S_{3}\cup S_{4})=\emptyset$

  * •

Case IV: $|S_{2}\cap S_{3}|=i,\ |S_{3}\cap S_{4}|=j,\ |S_{2}\cap S_{3}\cap
S_{4}|=l,\ i,j\geq 1,l\geq 0$ and $|S_{1}\cap\\{S_{2}\cup S_{3}\cup
S_{4}\\}|=\emptyset$

  * •

Case V.: $|S_{i}\cap S_{i+1}|\geq 1,\ i=1,2,3$

When $S_{i}$’s are disjoint then the variables
$X_{S_{1}},X_{S_{2}},X_{S_{3}},X_{S_{4}}$ are not independent for a fixed $n$,
but if $n$ tends to infinity, then they get independent, that is
$|\mathds{P}(X_{S_{i}}=1|X_{S_{j}}=1)-\mathds{P}(X_{S_{i}}=1)|\leq
o(1)\mathds{P}(X_{S_{i}}=1)$. So in Case I we can bound the sum because
disjoint $S_{i}$’s are asymptotically independent. In cases II-V, we can use
the fact that the number of intersecting quadruples decreases as we increase
the size of the intersection.

Proof of Lemma 5: Let us fix $T$, the tree on $k$ nodes, with $r=(r_{1},\ldots
r_{k})$. Denote the gluing (considering the remainder degrees $r_{i}$ also) of
two copies of $T$ along the set $S_{i},S_{j}$ by
$T_{i,j}=g(T_{S_{i}},T_{S_{j}})$ (if there is a valid gluing resulting in a
forest). $m_{i,j}=|V(T_{i,j})|$ and $c_{i,j}$ is just the number of components
of $T_{i,j}$.

$R_{i,j}=2(\sum_{l=1}^{k}r_{l})-\sum_{l\in S_{i}\cap S_{j}}r_{l}.$

We define similarly
$T_{i,j,h},T_{1,2,3,4},m_{i,j,h},m_{1,2,3,4},R_{i,j,h},R_{1,2,3,4}\ (i\neq
j\neq h,i\neq h)$.

$\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=\\\
=\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}X_{S_{4}})-\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}})\mathds{P}(X_{S_{4}}=1)=\\\
=\mathds{P}(X_{S_{4}}=1)\Bigl{(}\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}|X_{S_{4}}=1)-\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}})\Bigr{)}=\\\
=\mathds{P}(X_{S_{4}}=1)\Bigl{(}\mathds{P}(X_{S_{3}}=1)(\mathds{E}(A_{S_{1}}A_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1)-\mathds{E}(A_{S_{1}}A_{S_{2}}|X_{S_{4}}=1))-\\\
-\mathds{P}(X_{S_{3}}=1)(\mathds{E}(A_{S_{1}}A_{S_{2}}|X_{S_{3}}=1)-\mathds{E}(A_{S_{1}}A_{S_{2}}))\Bigr{)}=\\\
=\mathds{P}(X_{S_{4}}=1)\mathds{P}(X_{S_{3}}=1)\Bigl{(}\mathds{E}(A_{S_{1}}A_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1)-\mathds{E}(A_{S_{1}}A_{S_{2}}|X_{S_{4}}=1)-\\\
-\mathds{E}(A_{S_{1}}A_{S_{2}}|X_{S_{3}}=1)+\mathds{E}(A_{S_{1}}A_{S_{2}})\Bigr{)}$

Let

$f_{S_{3},S_{4}}(X,Y)=\mathds{E}(XY|X_{S_{3}}=1,X_{S_{4}}=1)-\mathds{E}(XY|X_{S_{4}}=1)-\\\
-\mathds{E}(XY|X_{S_{3}}=1)+\mathds{E}(XY),$
$f_{S_{4}}(X,Y,Z)=\mathds{E}(XYZ|X_{S_{4}}=1)-\mathds{E}(XYZ)\text{ and}$

$\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=\mathds{P}(X_{S_{4}}=1)\mathds{P}(X_{S_{3}}=1)(f_{S_{3},S_{4}}(X_{S_{1}},X_{S_{2}})-\\\
-f_{S_{3},S_{4}}(\mathds{E}X_{S_{1}},X_{S_{2}})-f_{S_{3},S_{4}}(X_{S_{1}},\mathds{E}X_{S_{2}})+f_{S_{3},S_{4}}(\mathds{E}X_{S_{1}},\mathds{E}X_{S_{2}}))$

Case I.: $S_{i}$’s are disjoint

When $S_{i}$’s are disjoint, we have
$R_{1,2,3,4}=4R,\,R_{3,4}=2R,\,m_{1,2,3,4}=4k,\,m_{3,4}=2k,\,c_{1,2,3,4}=4,\,c_{3,4}=2$.

Using Equation 5

$\mathds{E}(X_{S_{1}}X_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1){H(r_{3,4},T_{3,4})\over
H(r_{1,2,3,4},T_{1,2,3,4})}={2^{4k}\over 3^{2R+6k-4}}\\\
{n^{2R+6k-4}-n^{2R+6k-5}(6R^{2}+12kR-9R+18k^{2}-20k+{11\over
2})+O(n^{2R+6k-6})\over n^{2R+8k-6}-n^{2R+8k-7}(2R^{2}+12kR-{19\over
3}R+24k^{2}-28k+{23\over 3})+O(n^{2R+8k-8})}$ (8)

$\mathds{E}(X_{S_{1}}X_{S_{2}}|X_{S_{3}}=1){H(r_{3},T_{3})\over
H(r_{1,2,3},T_{1,2,3})}={2^{4k}\over 3^{2R+6k-4}}\\\
{n^{2R+6k-4}-n^{2R-6k-5}(4R^{2}+8kR-5R+12k^{2}-12k+{5\over
2})+O(n^{2R-6k-6})\over n^{2R+8k-6}-n^{2R+8k-7}({4\over 3}R^{2}+8kR-{11\over
3}R+16k^{2}-16k+3)+O(n^{2R-8k-8})}$ (9)

${\mathds{E}(X_{S_{1}}X_{S_{2}})\over H(r_{1,2},T_{1,2})}={2^{4k}\over
3^{2R+6k-4}}\\\ {n^{2R+6k-4}-n^{2R+6k-5}(2R^{2}+4kR-1R+6k^{2}-4k-{1\over
2})+O(n^{2R+6k-6})\over n^{2R+8k-6}-n^{2R+8k-7}({2\over
3}R^{2}+4kR-R+8k^{2}-4k-{5\over 3})+O(n^{2R+8k-8})}$ (10)

$\mathds{E}(\mathds{E}(X_{S_{1}})X_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1)=\mathds{P}(X_{S_{1}}=1)\mathds{E}(X_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1)$

$\mathds{E}(X_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1){H(r_{3,4},T_{3,4})\over
H(r_{2,3,4},T_{2,3,4})}={2^{2k}\over 3^{R+3k-2}}\\\
{n^{R+3k-2}-n^{R+3k-3}({5\over 2}R^{2}+5kR-{7\over 2}R+{25\over
2}k^{2}-{25\over 2}k+3)+O(n^{R+3k-4})\over n^{R+4k-3}-n^{R+4k-4}({5\over
6}R^{2}+5kR-{5\over 2}R+10k^{2}-11k+{8\over 3})+O(n^{R+4k-5})}$ (11)

$\mathds{E}(X_{S_{1}}|X_{S_{3}}=1){H(r,T)\over
H(r_{1,3},T_{1,3})}={2^{2k}\over 3^{R+3k-2}}\\\ {n^{R+3k-2}-n^{R+3k-3}({3\over
2}R^{2}+3kR-{3\over 2}R+{15\over 2}k^{2}-{13\over 2}k+1)+O(n^{R+3k-4})\over
n^{R+4k-3}-n^{R+4k-4}({1\over 2}R^{2}+3kR-{7\over 6}R+6k^{2}-5k+{1\over
3})+O(n^{R+4k-5})}$ (12)

${\mathds{E}(X_{S_{1}})\over H(r,t)}={2^{2k}\over 3^{R+3k-2}}\\\
{n^{R+3k-2}-n^{R+3k-3}({1\over 2}R^{2}+kR+{1\over 2}R+{5\over 2}k^{2}-{1\over
2}k-1)+O(n^{R+3k-4})\over n^{R+4k-3}-n^{R+4k-4}({1\over 6}R^{2}+kR+{1\over
6}R+2k^{2}+k-2)+O(n^{R+4k-5})}$ (13)

It is easy to verify that from (8)-(10) we get that

$f_{S_{3},S_{4}}(X_{S_{1}},X_{S_{2}})=O(n^{-2k}),$

and using (11)-(13)

$f_{S_{3},S_{4}}(\mathds{E}(X_{S_{1}}),X_{S_{2}})=f_{S_{3},S_{4}}(X_{S_{1}},\mathds{E}(X_{S_{2}}))=O(n^{-2k}),\
\mathrm{and}$
$f_{S_{3},S_{4}}(\mathds{E}(X_{S_{1}}),\mathds{E}(X_{S_{2}}))=0.$

Hence $\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{-4k+2})$ and
since the number of disjoint $S_{i}$ quadruples is just $n^{4k}$,

$\sum_{S_{i},\,S_{i}\cap S_{j}=\emptyset,\,i\neq
j}\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{2}).$

Case II.: $|S_{3}\cap S_{4}|=i,\ i\leq k$ and $S_{1},S_{2},S_{3}\cup S_{4}$
are disjoint

The number of such quadruples is $n^{4k-i}$. Similarly as above, we want to
bound $F(S_{1},S_{2},S_{3},S_{4})$.

From (7) we get

$\mathds{E}(X_{S_{1}}X_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1)-\mathds{E}(X_{S_{1}}X_{S_{2}})=\\\
=O(n^{m_{3,4}-m_{1,2,3,4}+c_{1,2,3,4}-c_{3,4}-1})=O(n^{2k-i-(4k-i)+3-1-1})=O(n^{-2k+1})$
(14)

$\mathds{E}(X_{S_{1}}X_{S_{2}}|X_{S_{3}}=1)-\mathds{E}(X_{S_{1}}X_{S_{2}})=\\\
=O(n^{m_{3}-m_{1,2,3}+c_{1,2,3}-c_{3}-1})=O(n^{k-3k+3-1-1})=O(n^{-2k+1})$ (15)

$\mathds{E}(X_{S_{1}}|X_{S_{3}}=1,X_{S_{4}}=1)-\mathds{E}(X_{S_{1}})=\\\
=O(n^{m_{3,4}-m_{1,3,4}+c_{1,3,4}-c_{3,4}-1})=O(n^{2k-i-(3k-i)+2-1-1})=O(n^{-k})$
(16)

$\mathds{E}(X_{S_{1}}|X_{S_{3}}=1)-\mathds{E}(X_{S_{1}})=\\\
=O(n^{m_{3}-m_{1,3}+c_{1,3}-c_{3}-1})=O(n^{k-2k+2-1-1})=O(n^{-k})$ (17)

From (14)-(17) it follows that
$\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{-4k+3})$ and so

$\sum_{S_{i},\,|S_{1}\cap
S_{2}|=i}\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{2}).$

Case III.: $|S_{1}\cap S_{2}|=i,|S_{3}\cap S_{4}|=j$ and $(S_{1}\cup
S_{2})\cap(S_{3}\cup S_{4})=\emptyset$.

As before, using (7) we get:

$\mathds{E}(X_{S_{1}},X_{S_{2}}|X_{S_{3}}=1,X_{S_{4}}=1)-\mathds{E}(X_{S_{1}},X_{S_{2}})=\\\
=O(n^{m_{3,4}-m_{1,2,3,4}+c_{1,2,3,4}-c_{3,4}-1})=O(n^{2k-j-(4k-i-j)+2-1-1})=O(n^{-2k+i})$
(18)

$\mathds{E}(X_{S_{1}},X_{S_{2}}|X_{S_{3}}=1)-\mathds{E}(X_{S_{1}},X_{S_{2}})=\\\
=O(n^{m_{3}-m_{1,2,3}+c_{1,2,3}-c_{3}-1})=O(n^{k-(3k-i)+2-1-1})=O(n^{-2k+i})$
(19)

Now it follows from (16)-(19) that
$\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{-4k+i+2})$ and so

$\sum_{|S_{1}\cap S_{2}|=i,|S_{3}\cap
S_{4}|=j}\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{2}).$

Case IV.: $|S_{1}\cap\\{S_{2}\cup S_{3}\cup S_{4}\\}|=\emptyset,|S_{2}\cap
S_{3}|=i,|S_{3}\cap S_{4}|=j,|S_{2}\cap S_{3}\cap S_{4}|=l,$ with $i,j\geq
1,l\geq 0$. Note, that $S_{2}\cup S_{4}\setminus S_{3}=\emptyset$, because
otherwise there will be no valid gluing of the trees $T$ along the $S_{i}$’s
($g(T_{S_{1}}T_{S_{2}}T_{S_{3}}T_{S_{4}})$ is not a tree).

The number of such $S_{i}$ quadruples is $n^{4k-i-j+l}$. We want to bound

$\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=\mathds{P}(X_{S_{1}}=1)\left(\mathds{E}(A_{S_{2}}A_{S_{3}}A_{S_{4}}|X_{S_{1}}=1)-\mathds{E}(A_{S_{2}}A_{S_{3}}A_{S_{4}})\right).$
(20)

Using (7) we get:

$\mathds{E}(X_{S_{2}}X_{S_{3}}X_{S_{4}}|X_{S_{1}}=1)-\mathds{E}(X_{S_{2}}X_{S_{3}}X_{S_{4}})=\\\
=O(n^{m_{1}-m_{1,2,3,4}+c_{1,2,3,4}-c_{1}-1})=O(n^{k-(4k-i-j+l)+2-1-1})=O(n^{-3k+i+j-l})$
(21)

$\mathds{E}(X_{S_{2}}X_{S_{3}}|X_{S_{1}}=1)-\mathds{E}(X_{S_{2}}X_{S_{3}})=\\\
=O(n^{m_{1}-m_{1,2,3}+c_{1,2,3}-c_{1}-1})=O(n^{k-(3k-i)+2-1-1})=O(n^{-2k+i})$
(22)

$\mathds{E}(X_{S_{3}}X_{S_{4}}|X_{S_{1}}=1)-\mathds{E}(X_{S_{3}}X_{S_{4}})=\\\
=O(n^{m_{1}-m_{1,3,4}+c_{1,3,4}-c_{1}-1})=O(n^{k-(3k-j)+2-1-1})=O(n^{-2k+j})$
(23)

$\mathds{E}(X_{S_{2}}X_{S_{4}}|X_{S_{1}}=1)-\mathds{E}(X_{S_{2}}X_{S_{4}})=O(n^{m_{1}-m_{1,2,4}+c_{1,2,4}-c_{1}-1})=\\\
=O(n^{k-(3k-l)+c_{1,2,4}-1-1})=\left\\{\begin{array}[]{ll}O(n^{-2k+l})&l\geq
1\\\ O(n^{-2k+1})&l=0\end{array}\right.$ (24)

Now from (17) and (21)-(24) we get that

$\sum_{S_{1},S_{2},S_{3},S_{4}}\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{2}),$

where the summation is over all quadruples $S_{i}$ satisfying the conditions
of Case IV.

Case V.: $|S_{i}\cap S_{j}|=s_{i,j}$ and $s_{i,i+1}\geq 1\ i=1,2,3$

$\mathds{E}(X_{S_{1}}X_{S_{2}}X_{S_{3}}X_{S_{4}})=O({1\over n^{|S_{1}\cup
S_{2}\cup S_{3}\cup S_{4}|-1}})$ (25)

$\mathds{E}(X_{S_{i}}X_{S_{j}}X_{S_{l}})=O({1\over n^{|S_{i}\cup S_{j}\cup
S_{l}|-1}})$ (26)

$\mathds{E}(X_{S_{i}}X_{S_{j}})=O({1\over n^{|S_{i}\cup S_{j}|-c_{i,j}}})$
(27)

From the above it follows that

$\sum_{S_{1},S_{2},S_{3},S_{4}}\mathds{E}(A_{S_{1}}A_{S_{2}}A_{S_{3}}A_{S_{4}})=O(n^{2}),$
(28)

where the summation is over all quadruples $S_{i}$ satisfying the conditions
of Case V.

From the above the claim of Lemma 5 follows ∎

##  5 The limit of $X_{n}$

Let $U^{l}$ denote the set of all finite $l$-deep rooted tree. Consider an
$l$-deep rooted tree with root $x$: $T^{l}_{x}\in U^{l}$, with
$|T^{l}_{x}|=k$. Let us denote the nodes at the $i$th level with $T_{i}$, and
$|T_{i}|=t_{i}$ ($t_{0}$ is just $1$, $t_{1}$ is the degree of the root and
$t_{l}$ is the number of leafs). As before $B_{G}(v,l)$ is the rooted $l$-ball
around $v$ in $G$ and $X_{n}$ is a random tree on $n$ nodes with distribution
$\Pi_{n}$.

If we assign remainder degrees $r$ to the rooted tree $T_{x}^{l}$ and forget
the root, then using Lemma 6 we get

$\mathds{E}(X_{n}^{T})=\mathds{E}\left(\sum_{S\subseteq[n]}X_{S}^{T}\right)={n!\over(n-k)!}\mathds{P}(X_{S}^{T}=1)=n{n-1\over
n-k}{{3n-R-3k-1\choose n-R-k}\over{3n-3\choose n-2}}H(r,T).$ (29)

Now the number of vertices $v\in X_{n}$ for which $B_{X_{n}}(v,l)\cong
T_{x}^{l}$ is just

${1\over|Aut(T^{l}_{x})|}\sum_{r_{k}=1}^{n}\sum_{r_{k-1}=1}^{n}\cdots\sum_{r_{k-t_{l}+1}=1}^{n}X_{n}^{T}$
(30)

Where the remainder degrees are $0$ except for the leafs of $T^{l}_{x}$
($r_{i}=0,\ \forall i\notin T_{l}$) and $Aut(T^{l}_{x})$ means the set of all
rooted automorphisms of $T^{l}_{x}$.

######  Remark 5.

Using lemma 3 we have that the maximum degree is almost surely less than
$3\log_{3}n$. For a tree $T$ with remainder degree $r$, if there exists $i$,
s.t. $r_{i}>3\log_{3}n$, then $X_{n}^{T}=0$ almost surely. So we can omit the
terms with $r_{i}>3\log_{3}n$ in 30.

Now if $v$ is a uniform random vertex of $X_{n}$, then using remark 5 we have

$\mathds{P}(B_{X_{n}}(v,l)=T_{x}^{l}|X_{n})={1\over|Aut(T^{l}_{x})|}\sum_{r_{k}=1}^{3\log_{3}n}\sum_{r_{k-1}=1}^{3\log_{3}n}\cdots\sum_{r_{k-t_{l}+1}=1}^{3\log_{3}n}{X_{n}^{T}\over
n},$ (31)

Now from Theorem 3, we get that

$\mathds{P}(B_{X_{n}}(v,l)=T_{x}^{l})={1\over|Aut(T^{l}_{x})|}\sum_{r_{k}=1}^{3\log_{3}n}\sum_{r_{k-1}=1}^{3\log_{3}n}\cdots\sum_{r_{k-t_{l}+1}=1}^{3\log_{3}n}\left({\mathds{E}(X_{n}^{T})\over
n}+o({1\over n^{{1\over 8}}})\right)=\\\
=o(1)+{1\over|Aut(T^{l}_{x})|}\sum_{r_{k}=1}^{3\log_{3}n}\sum_{r_{k-1}=1}^{3\log_{3}n}\cdots\sum_{r_{k-t_{l}+1}=1}^{3\log_{3}n}{\mathds{E}(X_{n}^{T})\over
n}.$

$\lim_{n\rightarrow\infty}{n-1\over n-k}{{3n-R-3k-1\choose
n-R-k}\over{3n-3\choose n-2}}H(r,T)=9\left({4\over
27}\right)^{\sum_{0}^{l}t_{j}}{\sum_{i\in T_{l}}r_{i}\prod_{i\in
T_{l}}(r_{i}+1)\over 3^{\sum_{i\in T_{l}}r_{i}}}\prod_{j\notin T_{l}}d_{j}!,$

so it follows that

$\lim_{n\rightarrow\infty}\mathds{P}(B_{X_{n}}(v,l)=T_{x}^{l})=\\\
=9\left({4\over 27}\right)^{\sum_{0}^{l-1}t_{j}}{t_{l}\over
3^{t_{l}}}{1\over|Aut(T_{x}^{l})|}\prod_{j\notin T_{l}}d_{j}!=p(T_{x}^{l}).$
(32)

Let $\cal{G}$ denote the set of all countable connected rooted trees. Let
${\cal T}({\cal G},T_{x}^{l}):=\\{(G,v)\in{\cal G}:B_{G}(v,l)\cong
T_{x}^{l}\\}$. Now consider a measure $\mu$ on the sets ${\cal T}({\cal
G},T_{x}^{l})$:

$\mu({\cal T}({\cal G},T_{x}^{l})=p(T_{x}^{l})$

######  Lemma 8.

$\mu$ extends to a probability measure on $\cal G$.

Proof: We only need to show that

$p(T_{x}^{l-1})=\sum_{\displaystyle T_{x}^{l}:B_{T_{x}^{l}}(x,l)\cong
T_{x}^{l-1}}p(T_{x}^{l})$ (33)

Let $\sigma,\rho\in Aut(T_{x}^{l})$ be two automorphisms of the rooted tree
$T_{x}^{l}$. We say that $\sigma\sim\rho$ if and only if there exists $\tau\in
Aut(T_{x}^{l})$, such that $\tau$ fixes every vertex not in $T_{l}$ and
$\sigma\circ\tau=\rho$. $\sim$ is an equivalence. The equivalence classes have
$\prod_{i\in T_{l}}(d_{i}-1)!$ elements, hence it follows

$|Aut(T_{x}^{l})|=|Aut(T_{x}^{l}\setminus T_{l})|\prod_{i\in
T_{l}}(d_{i}-1)!.$

Now we get equation 33 easily from the following:

$\sum_{d_{n-t_{l}-t_{l-1}+1}=1}^{\infty}\sum_{d_{n-t_{l}-t_{l-1}+2}=1}^{\infty}\cdots\sum_{d_{n-t_{l}}=1}^{\infty}{9\left({4\over
27}\right)^{\sum_{0}^{l-1}t_{j}}{t_{l}\over 3^{t_{l}}}\prod_{j\notin
T_{l}}d_{j}!\over|Aut(T_{x}^{l})|}=\\\ ={9\left({4\over
27}\right)^{\sum_{0}^{l-1}t_{j}}\left({9\over
4}\right)^{t_{l-1}}t_{l-1}\prod_{j\notin T_{l}\cup
T_{l-1}}d_{j}!\over|Aut(T_{x}^{l}\setminus T_{l})|}.$

∎

From Lemma 8 it follows that $\mu$ is indeed the limit of the random tree
sequence $X_{n}$. This completes the proof of Theorem 1.

## References

  * [1] D. Aldous, _The Continuum Random Tree III_ , Ann. Probab. Volume 21, Number 1 (1993), 248-289.
  * [2] I. Benjamini, O. Schramm, _Recurrence of Distributional Limits of Finite Planar Graphs_ , Electronic j. Probab. 6 (2001), paper no. 23, 1-13
  * [3] I. Benjamini, O. Schramm, A. Shapira, _Every Minor-Closed Property of Sparse Graphs is Testable_ , 40th Ann. ACM Symp. on Th. Comp. (2008), 393-402.
  * [4] G. Elek, _On Limits of Finite Graphs_ , Combinatorica 27 (2007), 503-507.
  * [5] G. Elek, G. Tardos, _Limits of Trees_ , Oberwolfach Report No. 11/2010, 566-568
  * [6] R. Lyons, _Asymptotic Enumeration of Spanning Trees_ , Combinatorics, Probability and Computing 14 (2005), 491-522