# Adaptive Inducing Points Selection for Gaussian Processes

Théo Galy-Fajou  Manfred Opper

###### Abstract

Gaussian Processes (GPs) are flexible non-parametric models with strong
probabilistic interpretation. While being a standard choice for performing
inference on time series, GPs have little techniques to work in a streaming
setting. (Bui et al., 2017) developed an efficient variational approach to
train online GPs by using sparsity techniques: The whole set of observations
is approximated by a smaller set of inducing points (IPs) and moved around
with new data. Both the number and the locations of the IPs will affect
greatly the performance of the algorithm. In addition to optimizing their
locations we propose to adaptively add new points, based on the properties of
the GP and the structure of the data.

Machine Learning, ICML, Gaussian Process, Streaming, Online

1 Technical University of Berlin

##  1 Introduction

Gaussian Processes (GPs) are flexible non-parametric models with strong
probabilistic interpretation. They are particularly fitted for time-series
(Roberts et al., 2013) but one of their biggest limitations is that they scale
cubically with the number of points (Williams & Rasmussen, 2006). Quinonero-
Candela & Rasmussen (2005) introduced the notion of sparse GPs, models
approximating the posterior by a smaller number $M$ of inducing points (IPs)
and reducing the inference complexity from $\mathcal{O}(N^{3})$ to
$\mathcal{O}(M^{3})$ where $M$ is the number of IPs. Titsias (2009) introduced
them later in a variational setting, allowing to optimize their locations.
Based on this idea, (Bui et al., 2017) introduced a variational streaming
model relying on inducing points. One of their algorithm’s features is that
hyper-parameters can be optimized and more specifically the number of inducing
can vary between batches of data. However in their work, the number of IPs is
fixed and their locations are simply optimized against the variational bound
of the marginal likelihood. Having a fixed number of IPs limits the model’s
scope if the total data size is unknown. A gradient based approach leads to
two problems:
\- IP’s locations need to be optimized until convergence for every batch.
Therefore batches need to be sufficiently large to get a meaningful
improvement. If the new data comes in very far from the original positions of
the IPs, the optimization will be extremely slow.
\- The number of IPs being fixed, there is no way to know how many will be
required to have a desired accuracy. Finding the optimal number of IPs is also
not an option as it is an ill-posed problem: the objective will only decrease
with more IPs, i.e. the optimum is obtained when every data point is an IP.

Figure 1: Illustration of the inducing point selection process. Blue points
represent inducing points, green points data and the orange line represent the
mean of the prediction from the GP model surrounded by one standard error. The
dashed represent the space covered by the existing IPs, only points seen
outside those areas are selected as new IPs.

We propose a different approach to this problem with a simple algorithm,
Online Inducing Points Selection (OIPS), requiring only one parameter to
select automatically both the number of inducing points and their location.
OIPS naturally takes into account the structure of the data while the
performance trade-off and the expected number of IPs can be inferred.

Our main contributions are as follow :
\- We develop an efficient online algorithm to automatically select the number
and location of inducing points for a streaming GP.
\- We give theoretical guarantees on the expected number of inducing points
and the performance of the GP.

In section 2 we present existing methods to select inducing points, as well as
an online inference for GPs. We present our algorithm and its theoretical
guarantees in section 3. We show our experiments in comparison with popular
inducing points selection methods in section 4. Finally we summarize our
findings and explore outlooks in section 5.

##  2 Background

###  2.1 Sparse Variational Gaussian Processes

#### Gaussian Processes:

Given some training data $\mathcal{D}=\\{X,\boldsymbol{y}\\}$ where
$X=\\{x_{i}\\}_{i=1}^{N}$ are the inputs $x_{i}\in\mathbb{R}^{D}$ and
$\boldsymbol{y}=\\{y_{i}\\}_{i=1}^{N}$ are the labels, we want to compute the
predictive distribution $p(y^{*}|D,x^{*})$ for new inputs $x^{*}$. In order to
do this we try to find an optimal distribution over a latent function $f$. We
set the latent vector $\boldsymbol{f}$ as the realization of $f(X)$, where
$f_{i}=f(x_{i})$, and put a GP prior $\mathcal{GP}(\mu_{0},k)$ on
$\boldsymbol{f}$, with $\mu_{0}$ the prior mean (set to 0 without loss of
generality) and $k$ a kernel function. In this work we are going to use an
isotropic squared exponential kernel (SE kernel) :
${k(x,x^{\prime})=\exp(-||x-x^{\prime}||^{2}/l^{2})}$, but it is generally
applicable to all translation-invariant kernels. We then compute the
posterior:

$\displaystyle
p(\boldsymbol{f}|\mathcal{D})=\frac{\prod_{i=1}^{N}p(y_{i}|f_{i})p(\boldsymbol{f})}{p(\mathcal{D})}$
(1)

Where $p(\boldsymbol{f})\sim\mathcal{N}(0,K_{XX})$ and $K_{XX}$ is the kernel
matrix evaluated on $X$ (in later notation we use $K_{X}$ instead of
$K_{XX}$). For a Gaussian likelihood the posterior
$p(\boldsymbol{f}|\mathcal{D})$ is known analytically in closed-form.
Prediction and inference have nonetheless a complexity of $\mathcal{O}(N^{3})$

#### Sparse Variational Gaussian Processes:

When the likelihood is not Gaussian, there is no tractable solution for the
posterior. One possible approximation is to use variational inference : a
family of distributions over $\boldsymbol{f}$ is selected, e.g. the
multivariate Gaussian $q(\boldsymbol{f})=\mathcal{N}(\boldsymbol{m},S)$, and
one optimizes the variational parameters $\boldsymbol{m}$ and $S$ by
minimizing the negative ELBO, a proxy for the KL divergence
$\mathrm{KL}(q(\boldsymbol{f})||p(\boldsymbol{f}|\mathcal{D}))$. However the
computational complexity still grows cubically with the number of samples, and
is therefore inadequate to large datasets.

Quinonero-Candela & Rasmussen (2005) and Titsias (2009) introduced the notion
of sparse variational GPs (SVGP). One adds inducing variables $\boldsymbol{u}$
and their inducing locations $Z=\\{Z_{i}\\}_{i=1}^{M}$ to the model. In this
work we restrict $Z_{i}$ to be in the same domain as $X_{i}$ but inter-domain
approaches also exist (Hensman et al., 2017). The relation between
$\boldsymbol{u}$ and $\boldsymbol{f}$ is given by the distribution
$p(\boldsymbol{f},\boldsymbol{u})=p(\boldsymbol{f}|\boldsymbol{u})p(\boldsymbol{u})$
where

$\displaystyle
p(\boldsymbol{f}|\boldsymbol{u})=\mathcal{N}(\boldsymbol{f}|K_{XZ}K_{Z}^{-1}\boldsymbol{u},\widetilde{K}),\,p(\boldsymbol{u})=\mathcal{N}(0,K_{Z})$
(2)

where $\widetilde{K}=K_{X}-K_{XZ}K_{Z}^{-1}K_{ZX}$

Then we approximate $p(\boldsymbol{f},\boldsymbol{u})$ with the variational
distribution
$q(\boldsymbol{f},\boldsymbol{u})=p(\boldsymbol{f}|\boldsymbol{u})q(\boldsymbol{u})$
where $q(\boldsymbol{u})=\mathcal{N}(\boldsymbol{\mu},\Sigma)$ by optimizing
$\mathrm{KL}(q(\boldsymbol{f},\boldsymbol{u})||p(\boldsymbol{f},\boldsymbol{u}|\mathcal{D}))$.

Note that if the likelihood is Gaussian, the optimal variational parameters
$\boldsymbol{\mu}^{*}$ and $\Sigma^{*}$ are known in closed-form. The only
parameters left to optimize are the kernel parameters as well as selecting the
number and the location of the inducing variables.

###  2.2 Inducing points selection methods

Titsias (2009) initially proposed to select the points location via a greedy
selection : A small batch of data is randomly sampled, each sample is
successively tested by adding it to the set of inducing points and evaluating
the improvement on the ELBO. The sample bringing the best performance is added
to the set of inducing points and the operation is repeated until the desired
number of inducing points is reached. This greedy approach has the advantage
of selecting a set which is already close to the optimum set but is extremely
expensive and is not applicable to non-conjugate likelihoods as it relies on
estimating the optimal bound.

The most popular approach currently is to use the $k$-means++ algorithm
(Arthur & Vassilvitskii, 2007) and take the optimized clusters centers as
inducing points locations. The clustering nature of the algorithm allows to
have good coverage of the whole dataset. However the $k$-means algorithm have
a complexity of $\mathcal{O}(NMDT)$ on the whole dataset where $T$ is the
number of $k$-means iterations. Another issue is that it might allocate
multiple centers in a region of high density leading to very close inducing
points and no significant performance improvement. It is also not applicable
online and does not solve the problem of choosing the number of inducing
points.

Another classical approach is to simply take a grid. For example Moreno-Muñoz
et al. (2019) use a grid in an online setting by updating the bounds of a
uniform grid. Using a grid is unfortunately limited a small number of
dimensions and does not take into account the structure of the data.

###  2.3 Online Variational Gaussian Process Learning

(Bui et al., 2017) developed a streaming algorithm for GPs (SSVGP) based the
inducing points approach of (Titsias, 2009). The method consists in
recursively optimizing the variational distribution
$q_{t}(\boldsymbol{u}_{t},\boldsymbol{f})$ for each new batch of data
$\mathcal{D}_{t}$ given the previous variational distribution
$q_{t-1}(\boldsymbol{u}_{t-1},\boldsymbol{f})$. $q_{t}$ initially approximates
the posterior :

$\displaystyle
p(\boldsymbol{u}_{t},\boldsymbol{f}|\mathcal{D}_{1:t})=\frac{p(\mathcal{D}_{t}|\boldsymbol{f})p(\mathcal{D}_{1:(t-1)}|\boldsymbol{f})p(\boldsymbol{u}_{t},\boldsymbol{f}|\theta_{t})}{p(\mathcal{D}_{1:t})}$
(3)

where $\theta_{t}$ are the set of hyper-parameters. Since $D_{1:(t-1)}$ is not
accessible anymore, the likelihood on previously seen data is approximated
using the previous variational approximation $q_{t-1}(\boldsymbol{u}_{t-1})$
and the previous hyper-parameters $\theta_{t-1}$:

$\displaystyle
p(\mathcal{D}_{1:(t-1)}|\boldsymbol{f})\approx\frac{q_{t-1}(\boldsymbol{u}_{t-1})p(\mathcal{D}_{1:(t-1)})}{p(\boldsymbol{u}_{t-1}|\theta_{t-1})}.$

The distribution approximated by $q_{t}$ is in the end:

$\displaystyle\begin{split}&q_{t}(\boldsymbol{u}_{t},\boldsymbol{f}|\mathcal{D}_{1:t})\approx\\\
&\quad\frac{p(\mathcal{D}_{t}|\boldsymbol{f})q_{t-1}(\boldsymbol{u}_{t-1})p(\boldsymbol{u}_{t},\boldsymbol{f}|\theta_{t})}{p(\boldsymbol{u}_{t-1}|\theta_{t-1})}\frac{p(\mathcal{D}_{1:(t-1)})}{p(\mathcal{D}_{1:t})}\end{split}$
(4)

The optimization of the (bound on the) KL divergence between the two
distributions for each new batch will preserve the information of
$\mathcal{D}_{1:(t-1)}$ via $q_{t-1}$ and ensure a smooth transition of the
hyper-parameters, including the number of inducing points. We give all
technical details including the hyper-parameter derivatives and the ELBO in
full form in appendix A.

##  3 Algorithm

The idea of our algorithm is that to give a good approximation, a large
majority of the samples should be ”close” (in the reproducing kernel Hilbert
space (RKHS)) to the set $Z$ of IPs locations. Additionally, $Z$ should be as
diverse as possible, since IP degeneracy will not improve the approximation.
This intuition is supported by previous works:
\- Bauer et al. (2016) showed that the most substantial improvement obtained
by adding a new inducing point was through the reduction of the uncertainty of
$q(\boldsymbol{f})$, which decreases quadratically with $K_{XZ}$.
\- Burt et al. (2019) showed that the quality of the approximation made with
inducing points is bounded by the norm of
${Q_{X}=K_{X}-K_{XZ}K_{Z}^{-1}K_{ZX}}$.
Therefore by ensuring that $K_{XZ}$ and $|K_{Z}|$ are sufficiently large, we
can expect an improvement on the approximation of the non-sparse problem.

###  3.1 Adding New Inducing Points

A simple yet efficient strategy is to verify that for each new data point $x$
seen during training, there exists a close inducing point. We first compute
$K_{xZ}=[k(x,Z_{1}),\ldots,k(x,Z_{M})]$. If the maximum value of $K_{xZ}$ is
smaller than a threshold parameter $\rho$, the sample is added to the set of
IPs $Z$. If not, the algorithm passes on to the next sample. We summarize all
steps in Algorithm 1.

The streaming nature of the algorithm makes it perfectly suited for an online
learning setting : it needs to see samples only once, whereas other algorithms
like $k$-means need to parse all the data multiple times before converging. It
is fully deterministic for a given sequence of samples and therefore
convergence guarantees are given under some conditions. This approach was
previously explored in a different context by Csató & Opper (2002), but was
limited to small datasets.

Algorithm 1 Online Inducing Point Selection (OIPS)

Input: sample $x$, set of inducing points $Z=\\{Z_{j}\\}_{j=1}^{M}$,acceptance
threshold $0<\rho<1$, kernel function $k$

$d\leftarrow\max_{j}(k(x,Z_{j}))$

if $d<\rho$ then

$\\{Z_{j}\\}\leftarrow\\{Z_{j}\\}\bigcup x$$M\leftarrow M+1$

end if

return $\\{Z_{j}\\}$

The extra cost of the algorithm is virtually free since $K_{XZ}$ needs to be
computed for the variational updates of the model.

One of our claims is that our algorithm is model and data agnostic. The reason
is that as kernel hyper-parameters are optimized, the acceptance condition
changes as well

Note that this method can be interpreted as a half-greedy approach of a
sequential sampling of a determinantal point process (Kulesza & Taskar, 2012).
In appendix B, we show that for the same number of points, the probability of
our selected set is higher than the one of a k-DPP.

###  3.2 Theoretical guarantees

The final size of $Z$ is depending on many factors: the selected threshold
$\rho$, the chosen kernel, the structure of the data (distribution, sparsity,
etc) and the number of points seen. However by having some weak assumptions on
the data we can prove a bound on the expected number of inducing points as
well as on the quality of the variational approximation.

#### Expected number of inducing points :

Since the selection process is directly depending on the data, it is
impossible to give an arbitrary bound. However by adding assumptions on the
distribution of $x$ one can

######  Theorem 1.

Given a dataset i.i.d and uniformly distributed, i.e.
$x\sim\mathcal{U}(0,a)^{D}$, and a SE kernel with lengthscale $l^{D}\ll 1$,
the expected number of selected inducing points $M$ after parsing $N$ points
is

$\displaystyle\mathbb{E}\left[M|N\right]\leq\frac{a^{D}-(a^{D}-\alpha)^{N+1}}{\alpha},$
(5)

where $\alpha=\left(\frac{l\sqrt{-D\log\rho}}{2}\right)^{D}$.

The proof is given in the appendix C. As $N\rightarrow\infty$, this bound will
converge to $a^{D}/\alpha$ which is the estimated number of overlapping hyper-
spheres of radius $l\sqrt{-D\log\rho_{in}}$ to fill a hypercube of dimension
$D$ with side length $a$. This can be used as an upper bound for any data
lying in a compact domain. This confirms the intuition that the number of
selected inducing points will grow faster with larger dimensions and a larger
$\rho$ and with smaller lengthscales.

#### Expected performance on regression :

Burt et al. (2019) derived a convergence bound for the inducing points
approach of (Titsias, 2009). Even if they show this bound in an offline
setting, their bound is still relevant for online problems. They show that
when $Z$ is sampled via a k-DPP process (Kulesza & Taskar, 2011), i.e. a
determinantal point process conditioned on a fixed set size, the difference
between the ELBO and the log evidence $\log p(\mathcal{D})$ is bounded by

$\displaystyle\mathbb{E}_{Z}\left[\|K_{X}-Q_{X}\|\right]\leq(M+1)\sum_{i=M+1}^{N}\lambda_{i}(K_{X})$
(6)

where $\lambda_{i}(K_{X})$ is the $i$-th largest eigenvalue of $K_{X}$ and
$Q_{X}=K_{XZ}K_{Z}^{-1}K_{ZX}$ is the Nyström approximation of $K_{X}$.

We derive a similar bound when using our algorithm instead of k-DPPsampling:

######  Theorem 2.

Let $Z$ be the set of inducing points locations of size $M$ selected via
Algorithm 1 on the dataset $X$ of size $N$.

$\displaystyle\|K_{X}-Q_{X}\|\leq(N-M)\left(1-\frac{\rho^{2}}{1+M(M-1)\rho}\right)$
(7)

where $K_{X}$ is the kernel matrix on $X$ and $Q_{X}$ is the Nyström
approximation of $K_{X}$ using the subset $Z$

The proof and an empirical comparison are given in the appendix D.

##  4 Experiments

In this section we get a quick look on how our algorithm performs in different
settings compared to approaches described in section 2.2. We compare the
online model SSVGP described in section 2 with different IP selection
techniques. We select from the first batch via k-means and then optimize them
(k-means/opt), select them via our algorithm and optimize them (OIPS/opt),
select them via our algorithm but don’t optimize them (OIPS) and finally
create a Grid that we adapt according to new bounds. We consider 3 different
toy datasets, from which two are displayed in figure 2. The dataset A is a
uniform time series and the output function is a noisy sinus. The dataset B is
an irregular time-series, with a gap in the inputs. The output function is
also a noisy sinus. Dataset C inputs are random samples from an isotropic
multivariate 3D Gaussian and the output function is given by
$\sin(||x||)/||x||$. All datasets contain 200 training points and 200 test
points. For all experiments we use an isotropic SE kernel with fixed
parameters. For datasets A and B, Grid and $k$-means has 25 IPs while OIPS
converged to around 20 IPs. For dataset C, Grid has $10^{3}$ IPs, $k$-means
50, and both OIPS converged to 10 IPs Figure 2 shows the evolution on the
average negative log likelihood on test data after every batch has been seen.
On a uniform time-series context all methods are pretty much equivalent. The
presence of a gap, blocks the optimization of IP locations and impede
inference of future points. Whereas the grid suffers from being in high-
dimensions and All details on the datasets, different training methods, hyper-
parameters and optimization parameters used are to be found in appendix E.

Figure 2: Toy datasets A and B, divived in 4 batches. Average Negative Test
Log-Likelihood on a test set in function of number of batches seen. In a
uniform streaming setting all methods perform similarly but having a gap
blocks the convergence of a simple position optimization whereas in a non-
compact situation the adaptive grid suffers in performance.

##  5 Conclusion

We presented a new algorithm, OIPS, able to select inducing points
automatically for a GP in an online setting. The theoretical bounds derived
outperforms the previous work based on DPPs. There is yet to improve the
selection process to make it robust to outliers and to variations of the
hyper-parameters. Using for instance a threshold on the median or a mean on
the $k$-nearest IPs could help to avoid picking adversarial points such as
outliers. We have only considered regression but our algorithm is also
compatible with non-conjugate likelihoods. Using augmentations approaches
(Wenzel et al., 2019; Galy-Fajou et al., 2019), same performance can be
attained. Finally the most interesting improvement would be to use a non-
stationary kernel (Remes et al., 2017) and be able to automatically adapt the
number of inducing points across the dataset.

## References

  * Arthur & Vassilvitskii (2007) Arthur, D. and Vassilvitskii, S.  k-means++: The advantages of careful seeding.  In _Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms_ , pp. 1027–1035. Society for Industrial and Applied Mathematics, 2007.
  * Bauer et al. (2016) Bauer, M., van der Wilk, M., and Rasmussen, C. E.  Understanding probabilistic sparse gaussian process approximations.  In _Advances in neural information processing systems_ , pp. 1533–1541, 2016.
  * Belabbas & Wolfe (2009) Belabbas, M.-A. and Wolfe, P. J.  Spectral methods in machine learning and new strategies for very large datasets.  _Proceedings of the National Academy of Sciences_ , 106(2):369–374, 2009.
  * Bui et al. (2017) Bui, T. D., Nguyen, C., and Turner, R. E.  Streaming sparse gaussian process approximations.  In _Advances in Neural Information Processing Systems_ , pp. 3299–3307, 2017.
  * Burt et al. (2019) Burt, D., Rasmussen, C. E., and Van Der Wilk, M.  Rates of convergence for sparse variational gaussian process regression.  In _International Conference on Machine Learning_ , pp. 862–871, 2019.
  * Csató & Opper (2002) Csató, L. and Opper, M.  Sparse on-line gaussian processes.  _Neural computation_ , 14(3):641–668, 2002.
  * Galy-Fajou et al. (2019) Galy-Fajou, T., Wenzel, F., Donner, C., and Opper, M.  Multi-class gaussian process classification made conjugate: Efficient inference via data augmentation.  _arXiv preprint arXiv:1905.09670_ , 2019.
  * Hensman et al. (2017) Hensman, J., Durrande, N., and Solin, A.  Variational fourier features for gaussian processes.  _The Journal of Machine Learning Research_ , 18(1):5537–5588, 2017.
  * Kulesza & Taskar (2011) Kulesza, A. and Taskar, B.  k-dpps: Fixed-size determinantal point processes.  In _Proceedings of the 28th International Conference on Machine Learning (ICML-11)_ , pp. 1193–1200, 2011.
  * Kulesza & Taskar (2012) Kulesza, A. and Taskar, B.  Determinantal point processes for machine learning.  pp. 1–120, 2012.  ISSN 1935-8237.  doi: 10.1561/2200000044.  URL http://arxiv.org/abs/1207.6083%0Ahttp://dx.doi.org/10.1561/2200000044.  ZSCC: 0000516 arXiv: 1207.6083 ISBN: 9781601986283.
  * Moreno-Muñoz et al. (2019) Moreno-Muñoz, P., Artés-Rodríguez, A., and Álvarez, M. A.  Continual multi-task gaussian processes.  _arXiv preprint arXiv:1911.00002_ , 2019.
  * Quinonero-Candela & Rasmussen (2005) Quinonero-Candela, J. and Rasmussen, C. E.  A Unifying View of Sparse Approximate Gaussian Process Regression.  _Journal of Machine Learning Research_ , 6:1939–1959, 2005\.  ZSCC: NoCitationData[s0].
  * Remes et al. (2017) Remes, S., Heinonen, M., and Kaski, S.  Non-stationary spectral kernels.  In _Advances in Neural Information Processing Systems_ , pp. 4642–4651, 2017.
  * Roberts et al. (2013) Roberts, S., Osborne, M., Ebden, M., Reece, S., Gibson, N., and Aigrain, S.  Gaussian processes for time-series modelling.  _Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences_ , 371(1984):20110550, February 2013.  ISSN 1364-503X, 1471-2962.  doi: 10.1098/rsta.2011.0550.  URL https://royalsocietypublishing.org/doi/10.1098/rsta.2011.0550.
  * Stewart & guang Sun (1990) Stewart, G. W. and guang Sun, J.  _Matrix Perturbation Theory_.  Academic Press, 1990.
  * Titsias (2009) Titsias, M.  Variational learning of inducing variables in sparse gaussian processes.  In _Artificial Intelligence and Statistics_ , pp. 567–574, 2009\.
  * Wenzel et al. (2019) Wenzel, F., Galy-Fajou, T., Donner, C., Kloft, M., and Opper, M.  Efficient gaussian process classification using pòlya-gamma data augmentation.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 5417–5424, 2019.
  * Williams & Rasmussen (2006) Williams, C. K. and Rasmussen, C. E.  _Gaussian processes for machine learning_ , volume 2.  MIT press Cambridge, MA, 2006.

##  Appendix A Derivations online GPs

###  A.1 ELBO

Following Bui et al. (2017), the ELBO for variational inference is defined as
:

$\displaystyle\mathcal{L}=$
$\displaystyle-\mathrm{KL}\left(q_{t}(\boldsymbol{u}_{t})||p(\boldsymbol{u}_{t}|\theta_{t})\right)+\mathbb{E}_{q_{t}(\boldsymbol{u}_{t},\boldsymbol{f}_{t})}\left[\log
p(y_{t}|\boldsymbol{f}_{t})\right]$
$\displaystyle-\mathrm{KL}(q_{t}(\boldsymbol{u}_{t-1})||q_{t-1}(\boldsymbol{u}_{t-1}))$
$\displaystyle+\mathrm{KL}(q_{t}(\boldsymbol{u}_{t-1})||p(\boldsymbol{u}_{t-1}|\theta_{t-1}))$

The terms of the first line correspond to a classical SVGP problem and the
second line express the KL divergence with the previous variational posterior.
The distributions are defined as :

$\displaystyle q_{t}(\boldsymbol{u}_{t})=$
$\displaystyle\mathcal{N}\left(\boldsymbol{\mu}_{t},\Sigma_{t}\right)$
$\displaystyle p(\boldsymbol{u}_{t}|\theta_{t})=$
$\displaystyle\mathcal{N}\left(0,K_{Z_{t}}\right)$ $\displaystyle
q_{t}(\boldsymbol{u}_{t-1})=$ $\displaystyle\int
p(\boldsymbol{u}_{t-1}|\boldsymbol{u}_{t})q_{t}(\boldsymbol{u}_{t})d\boldsymbol{u}_{t}$
$\displaystyle=$
$\displaystyle\mathcal{N}\left(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t},\widetilde{K}_{Z_{t-1}}\right)$
$\displaystyle\widetilde{K}_{Z_{t-1}}=$ $\displaystyle
K_{Z_{t-1}}+\kappa_{Z_{t-1}Z_{t}}\Sigma_{t}\kappa_{Z_{t-1}Z_{t}}^{\top}$
$\displaystyle-K_{Z_{t-1}Z_{t}}K^{-1}_{Z_{t}}K_{Z_{t}Z_{t-1}}$ $\displaystyle
q_{t-1}(\boldsymbol{u}_{t-1})=$
$\displaystyle\mathcal{N}\left(\boldsymbol{\mu}_{t-1},\Sigma_{t-1}\right)$
$\displaystyle p(\boldsymbol{u}_{t-1}||\theta_{t-1})=$
$\displaystyle\mathcal{N}(0,\underbrace{K^{\prime}_{Z_{t-1}}}_{\text{Given
}\theta_{t-1}})$

The first terms ares

$\displaystyle\mathrm{KL}(q_{t}(\boldsymbol{u}_{t})||p(\boldsymbol{u}_{t}|\theta_{t})=$
$\displaystyle\quad\frac{1}{2}\left(\log\left|K_{Z_{t}}\right|-\log\left|\Sigma_{t}\right|-M_{t}\right.$
$\displaystyle\quad+\left.\text{tr}(K_{Z_{t}}^{-1}\Sigma_{t})+\boldsymbol{\mu}_{t}^{\top}K^{-1}_{Z_{t}}\boldsymbol{\mu}_{t}\right)$

And for
$p(\boldsymbol{y}_{t}|\boldsymbol{f}_{t})=\prod_{i=1}^{B}\mathcal{N}(y_{i}|f_{i},\sigma)$.
The expected log-likelihood is given by L

$\displaystyle\mathbb{E}_{q_{t}(\boldsymbol{u}_{t},\boldsymbol{f}_{t})}\left[\log
p(\boldsymbol{y}_{t}|\boldsymbol{f}_{t})\right]=-\frac{B}{2}\log
2\pi\sigma^{2}$
$\displaystyle\quad-\frac{1}{2\sigma^{2}}\sum_{i=1}^{B}(y_{i}-\kappa_{X_{i}Z_{t}}\mu_{t})^{2}+\widetilde{K}+\kappa_{X_{i}Z_{t}}\Sigma_{t}\kappa_{X_{i}Z_{t}}^{\top}$

Writing the second terms fully we get :

$\displaystyle\mathrm{KL}(q_{t}(\boldsymbol{u}_{t-1})||p(\boldsymbol{u}_{t-1}|\theta_{t-1}))=$
$\displaystyle\quad\frac{1}{2}\left(\log|K^{\prime}_{Z_{t-1}}|-\log|\widetilde{K}_{t-1}|-M_{t-1}\right.$
$\displaystyle\quad+\text{tr}((K^{\prime}_{Z_{t-1}})^{-1}\widetilde{K}_{Z_{t-1}})$
$\displaystyle\quad\left.+(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t})^{\top}(K^{\prime}_{Z_{t-1}})^{-1}\kappa_{Z_{t}Z_{t-1}}\boldsymbol{\mu}_{t}\right)$
$\displaystyle\mathrm{KL}(q_{t}(\boldsymbol{u}_{t-1})||q_{t-1}(\boldsymbol{u}_{t-1}))=$
$\displaystyle\quad\frac{1}{2}\left(\log|\Sigma_{t-1}|-\log|\widetilde{K}_{Z_{t-1}}|-M_{t-1}\right.$
$\displaystyle\quad+\text{tr}(\Sigma_{t-1}^{-1}\widetilde{K}_{Z_{t-1}})$
$\displaystyle\quad\left.+(\boldsymbol{\mu}_{t-1}-\kappa_{Z_{t}Z_{t-1}}\boldsymbol{\mu}_{t})^{\top}\Sigma_{t-1}^{-1}(\boldsymbol{\mu}_{t-1}-\kappa_{Z_{t}Z_{t-1}}\boldsymbol{\mu}_{t})\right)$

Subtracting the second term to the first we get:

$\displaystyle\mathrm{KL}_{t:t-1}=$
$\displaystyle\quad\mathrm{KL}(q_{t}(\boldsymbol{u}_{t-1})||p(\boldsymbol{u}_{t-1}|\theta_{t-1}))-\mathrm{KL}(q_{t}(\boldsymbol{u}_{t})||q_{t-1}(\boldsymbol{u}_{t-1}))$
$\displaystyle=\frac{1}{2}\left(\log|K^{\prime}_{Z_{t-1}}|-\log|\Sigma_{t-1}|-\text{tr}((\Sigma_{t-1}^{-1}-(K^{\prime}_{Z_{t-1}})^{-1})\widetilde{K}_{Z_{t-1}})\right.$
$\displaystyle\quad-\boldsymbol{\mu}_{t-1}^{\top}\Sigma_{t-1}^{-1}\boldsymbol{\mu}_{t-1}+2\boldsymbol{\mu}_{t-1}\Sigma_{t-1}^{-1}\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t}$
$\displaystyle\quad\left.-(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t})^{\top}(\Sigma_{t-1}^{-1}-(K^{\prime}_{Z_{t-1}})^{-1})(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t})\right)$
$\displaystyle=\frac{1}{2}\left(\log|K^{\prime}_{Z_{t-1}}|-\log|\Sigma_{t-1}|-\text{tr}(D_{t-1}^{-1}\widetilde{K}_{t-1})\right.$
$\displaystyle\quad-\boldsymbol{\mu}_{t-1}^{\top}\Sigma_{t-1}^{-1}\boldsymbol{\mu}_{t-1}+2\boldsymbol{\mu}_{t-1}\Sigma_{t-1}^{-1}\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t}$
$\displaystyle\quad\left.-(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t})^{\top}D_{t-1}^{-1}(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t})\right)$

Where $D_{t}=\left(\Sigma_{t}^{-1}-K_{Z_{t}}^{-1}\right)^{-1}$.

Taking the derivative of $\mathcal{L}$ given $\boldsymbol{\mu}_{t}$ and
$\Sigma_{t}$ gives us directly the optimal solution for Gaussian regression:

$\displaystyle\Sigma^{*}_{t}=$
$\displaystyle\left(\sigma^{-2}\kappa_{X_{t}Z_{t}}^{\top}\kappa^{\phantom{\top}}_{X_{t}Z_{t}}+\kappa_{Z_{t-1}Z_{t}}^{\top}D_{t-1}^{-1}\kappa^{\phantom{\top}}_{Z_{t-1}Z_{t}}+K_{Z_{t}}^{-1}\right)^{-1}$
$\displaystyle\boldsymbol{\mu}^{*}_{t}=$
$\displaystyle\Sigma_{t}\left(\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\boldsymbol{y}_{t}+\kappa_{Z_{t-1}Z_{t}}^{\top}\Sigma_{t-1}\boldsymbol{\mu}_{t-1}\right)$

Rewritten in natural parameters terms:

$\displaystyle\eta_{1}^{t}=$
$\displaystyle\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\boldsymbol{y}_{t}+\kappa_{Z_{t-1}Z_{t}}^{\top}\eta_{1}^{t-1}$
$\displaystyle\eta_{2}^{t}=$
$\displaystyle-\frac{1}{2}\left(\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}I\kappa_{X_{t}Z_{t}}\right.$
$\displaystyle\left.+\kappa_{Z_{t-1}Z_{t}}^{\top}\left(-2\eta_{2}^{t-1}-K_{Z_{t-1}}^{-1}\right)\kappa_{Z_{t-1}Z_{t}}+K_{Z_{t}}^{-1}\right)$

###  A.2 Hyper-parameter derivatives

Given $\theta$ a kernel hyperparameter and
$J_{\Box\Box}=\frac{dK_{\Box\Box}}{d\theta}$ the derivatives are given by:

$\displaystyle\frac{d\mathrm{KL}_{t:t-1}}{d\theta_{t}}=$
$\displaystyle-\frac{1}{2}\text{tr}\left(D_{t-1}^{-1}\frac{d\widetilde{K}_{Z_{t-1}}}{d\theta_{t}}\right)$
$\displaystyle+\boldsymbol{\mu}_{t-1}\Sigma_{t-1}^{-1}\frac{d\kappa_{Z_{t-1}Z_{t}}}{d\theta_{t}}\boldsymbol{\mu}_{t}$
$\displaystyle-(\kappa_{Z_{t-1}Z_{t}}\boldsymbol{\mu}_{t})^{\top}D_{t-1}^{-1}(\frac{d\kappa_{Z_{t-1}Z_{t}}}{d\theta_{t}}\boldsymbol{\mu}_{t})$
$\displaystyle\frac{d\kappa_{Z_{t-1}Z_{t}}}{d\theta_{t}}=$
$\displaystyle\frac{dK_{Z_{t-1}Z_{t}}}{d\theta_{t}}K_{Z_{t}}^{-1}+K_{Z_{t}Z_{t-1}}\frac{dK_{Z_{t}}^{-1}}{d\theta_{t}}$
$\displaystyle=$
$\displaystyle(J_{Z_{t}Z_{t-1}}-\kappa_{Z_{t}Z_{t-1}}J_{Z_{t}})K_{Z_{t}}^{-1}=\iota_{Z_{t-1}Z_{t}}$
$\displaystyle\frac{d\widetilde{K}_{Z_{t-1}}}{d\theta_{t}}=$
$\displaystyle\frac{dK_{Z_{t-1}}}{d\theta_{t}}+2\frac{d\kappa_{Z_{t-1}Z_{t}}}{d\theta_{t}}\Sigma_{t}\kappa_{Z_{t}Z_{t-1}}^{\top}$
$\displaystyle-\frac{d\kappa_{Z_{t-1}Z_{t}}}{d\theta_{t}}K_{Z_{t}Z_{t-1}}-\kappa_{Z_{t-1}Z_{t}}\frac{dK_{Z_{t}Z_{t-1}}}{d\theta_{t}}$
$\displaystyle=$ $\displaystyle
J_{Z_{t-1}}+2\iota_{Z_{t-1}Z_{t}}\Sigma_{t}\kappa_{Z_{t-1}Z_{t}}^{\top}$
$\displaystyle-\iota_{Z_{t-1}Z_{t}}K_{Z_{t}Z_{t-1}}-\kappa_{Z_{t-1}Z_{t}}J_{Z_{t}Z_{t-1}}$
$\displaystyle\frac{d\mathrm{KL}(q_{t}(\boldsymbol{u}_{t})||p(\boldsymbol{u}_{t}|\theta_{t})}{d\theta_{t}}$

Special derivative given the variance :

$\displaystyle\frac{dKL_{a}}{dv}=$
$\displaystyle-\frac{1}{2}\left(\text{tr}\left(D_{a}^{-1}\left[\frac{1}{v}(K_{aa}-K_{ab}K_{bb}^{-1}K_{ba})\right]\right)\right)$

###  A.3 Comparison with SVI

If we take the special case where inducing points do not change between
iterations, then $\kappa_{Z_{t-1}Z_{t}}=I$ and ${K_{Z_{t-1}}=K_{Z_{t}}}$. The
updates become

$\displaystyle\eta_{1}^{t}=$
$\displaystyle\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\boldsymbol{y}_{t}+\eta_{1}^{t-1}$
$\displaystyle\eta_{2}^{t}=$
$\displaystyle-\frac{1}{2}\left(\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\kappa_{X_{t}Z_{t}}+\left(-2\eta_{2}^{t-1}-K_{Z_{t}}^{-1}\right)+K_{Z_{t}}^{-1}\right)$
$\displaystyle=$
$\displaystyle-\frac{1}{2}\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\kappa_{X_{t}Z_{t}}+\eta_{2}^{t-1}$

Compared to the SVI updates:

$\displaystyle\eta_{1}^{t}=$
$\displaystyle\eta_{1}^{t-1}+\rho\left(\frac{N}{|B|}\left(\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\boldsymbol{y}_{t}\right)-\eta_{1}^{t-1}\right)$
$\displaystyle\eta_{2}^{t}=$
$\displaystyle\eta_{2}^{t-1}+\rho\left(-\frac{1}{2}\left(\frac{N}{|B|}\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\kappa_{X_{t}Z_{t}}+K_{Z_{t}}^{-1}\right)-\eta_{2}^{t-1}\right)$

If we ignore $\rho$ by setting it as 1:

$\displaystyle\eta_{1}^{t}=$
$\displaystyle\frac{N}{|B|}\left(\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\boldsymbol{y}_{t}\right)$
$\displaystyle\eta_{2}^{t}=$
$\displaystyle-\frac{1}{2}\left(\frac{N}{|B|}\kappa_{X_{t}Z_{t}}^{\top}\sigma^{-2}\kappa_{X_{t}Z_{t}}+K_{Z_{t}}^{-1}\right)$

We forget completely the previous $\eta_{1}$.
To make it directly comparable to streaming:

SVI $\displaystyle\eta_{1}^{t+1}=$
$\displaystyle(1-\rho)\eta_{1}^{t}+\rho\left(\frac{N}{|B|}\left(\kappa_{f}^{\top}\sigma^{-2}y\right)\right)$
$\displaystyle\eta_{2}^{t+1}=$
$\displaystyle(1-\rho)\eta_{2}^{t}+-\frac{1}{2}\rho\left(\frac{N}{|B|}\kappa_{f}^{\top}\sigma^{-2}\kappa_{f}+K_{bb}^{-1}\right)$
$\displaystyle\eta_{1}^{t}=$
$\displaystyle(1-\rho)^{t}\eta_{0}+\sum_{i=1}^{t}(1-\rho)^{i-1}\rho\frac{N}{|B|}\kappa_{f}^{\top}\sigma^{-2}y^{i}$
Streaming $\displaystyle\eta_{1}^{t+1}=$
$\displaystyle\eta_{1}^{t}+\kappa_{f}^{\top}\sigma^{-2}y$
$\displaystyle\eta_{2}^{t+1}=$
$\displaystyle\eta_{2}^{t}-\frac{1}{2}\kappa_{f}^{\top}\sigma^{-2}\kappa_{f}$

##  Appendix B Deterministic algorithm as a DPP half-greedy sampling

We proceed to a simple experiment, where given a dataset, Abalone
($N=4177,D=7$), we repeatedly shuffle the data. We apply algorithm 1 parsing
all the data to get the subset $Z_{OIPS}$. We use the resulting number of
inducing points $k$ as a parameter to sample from a k-DPP and obtain
$Z_{kDPP}$. We compute the probabilities of $\log p(Z_{OIPS}|M=k)$ and $\log
p(Z_{kDPP}|M=k)$ and report the histogram of the probabilities on figure 3 One
can observe that the probability given by the OIPS algorithm is consistently
higher as well as more narrow then the sampling. This can be explained by the
fact that we deterministically constrain all the points to have a certain
distance from each other and therefore put a deterministic limit on the
determinant of $K_{Z}$.

Figure 3: Histogram of $p(Z|k=M)$ for the OIPS algorithm and k-DPPsampling

##  Appendix C Proof Theorem 1 : Bound on the number of points

Algorithm 1 can be interpreted as filling a domain with closed balls, where
balls intersections are allowed but no center can be inside another ball. For
a SE kernel we can compute the radius $r$ (in euclidean space) of these balls
:

$\displaystyle k(x,x^{\prime})$ $\displaystyle=\rho_{in}$
$\displaystyle\exp\left(-\frac{||x-x^{\prime}||^{2}}{h^{2}}\right)$
$\displaystyle=\rho_{in}$ $\displaystyle||x-x^{\prime}||^{2}$
$\displaystyle=-h^{2}\log\rho_{in}$ $\displaystyle r$
$\displaystyle=h\sqrt{-\log\rho_{in}}$

We can bound the volume of the union of the balls by the union of inscribed
hypercubes. The length of an inscribed hypercube in an hypersphere of radius
$r$ is $l=r\sqrt{D}/2$. Since the volume of the hypercube is defined to be
smaller, this gives us an upper bound on the expected number of inducing
points. Defining as $K_{n}$ the number of inducing points at time $n$, the
probability of having a point outside of the union of all $k$ hypercubes is

$\displaystyle p(K_{n+1}=k+1|K_{n}=k)=$
$\displaystyle\max\left(a^{D}-\sum_{i=1}^{k}l^{D}\right)$ $\displaystyle=$
$\displaystyle\max\left(a^{D}-kl^{D},0\right)$ $\displaystyle p_{k}^{+}=$
$\displaystyle\max\left(a^{D}-k\alpha,0\right)$ Where
$\alpha=\left(\frac{r\sqrt{D}}{2}\right)^{D}$, is the volume of one hypercube
and therefore the probability of a new sample to appear in it. The probability
of keeping the same number of points is $\displaystyle p(K_{n+1}=k|K_{n}=k)=$
$\displaystyle\min\left(\sum_{i=1}^{k}l^{D},1\right)$ $\displaystyle
p_{k}^{=}=$ $\displaystyle\min(k\alpha,1)$

We now consider the problem as a Markov chain where the state $p$ is
represented by a vector $\\{p_{i}\\}_{i=1}^{N}$ where $p_{i}=1$ if there are
$i$ inducing points. The transition matrix $P$ is given by :

$\displaystyle P=\left(\begin{array}[]{cccc}p_{1}^{=}&0&0&0\\\
p_{1}^{+}&p_{2}^{=}&0&0\\\ 0&p_{2}^{+}&\ddots&0\\\ 0&0&\ddots&0\\\
0&0&p_{N-1}^{+}&p_{N}^{=}\end{array}\right)$

If we define that we start with inducing points the initial state is
$p^{1}=\\{1,0,\ldots,0\\}^{\top}$, the probability of having $k$ balls after
$n$ steps is $p(K_{n}=k|p^{1})=\left(P^{n}p^{1}\right)_{k}$ while the expected
number of pointsis given by ${\sum_{k}k\cdot p(K_{n}=k|p^{1})}$.

These sequence can be complex to compute. Instead we can approximate the final
expectation by recursively computing the update given the expectation at the
previous step:

$\displaystyle\mathbb{E}_{p(K_{n+1}|K_{n}=\mathbb{E}\left[K_{n}\right])}\left[K_{n+1}\right]$
$\displaystyle=\mathbb{E}\left[K_{n}\right]\mathbb{E}\left[K_{n}\right]\alpha+(\mathbb{E}\left[K_{n}\right]+1)(a^{D}-\mathbb{E}\left[K_{n}\right]\alpha)$
$\displaystyle=a^{D}\mathbb{E}\left[K_{n}\right]+a^{D}-\mathbb{E}\left[K_{n}\right]\alpha=a^{D}+\mathbb{E}\left[K_{n}\right](a^{D}-\alpha)$

This is an arithmetico-geometric suite and given the original condition
$\mathbb{E}\left[K_{0}\right]=1$ and since $\alpha<a^{D}$ we can get a closed
form solution for $\mathbb{E}\left[K_{n}\right]$:

$\displaystyle\mathbb{E}\left[K_{n}\right]=$
$\displaystyle(a^{D}-\alpha)^{n}\left(1-\frac{a^{D}}{\alpha}\right)+\frac{a^{D}}{\alpha}$
$\displaystyle=$ $\displaystyle\frac{a^{D}-(a^{D}-\alpha)^{n+1}}{\alpha}$

###  C.1 Empirical Comparison

We show the realization of this bound on uniform data with 3 dimensions,
$\rho=0.7$ and $l=0.3$ on figure 4.

Figure 4: Bound on the number of inducing points accepted $M$ given the number
of seen points $N$ vs the empirical estimation

##  Appendix D Proof theorem 2 : Bounding the ELBO

We follow the approach of Burt et al. (2019) and Belabbas & Wolfe (2009). Burt
et al. (2019) showed that the error between the ELBO and the log evidence was
bounded by $\|K_{X}-K_{XZ}K_{Z}^{-1}K_{ZX}\|$. Where $\|\cdot\|$ is the
Froebius norm. Using a k-DPP sampling (Kulesza & Taskar, 2011), they were able
to show a bound on the expectation of this norm. We follow similar
calculations with our deterministic algorithm for fixed kernel parameters. Let
be $K_{X}$ the kernel matrix of the full dataset and $K_{Z}$ the submatrix
given the set of points $\\{Z_{i}\\}_{i=1}^{M}$. The Schur complement of
$K_{ZZ}$, $S_{C}(K_{ZZ})$ in $K_{XX}$ is given by
$K_{X}-K_{XZ}K_{Z}^{-1}K_{ZX}$. Following a similar approach then Belabbas &
Wolfe (2009) we bound the norm by the trace:

$\displaystyle\|S_{C}(K_{ZZ})\|=\sqrt{\sum_{j=1}^{N-M}\overline{\lambda}_{j}}\leq\sum_{j=1}^{N-M}\overline{\lambda}_{j}=\text{tr}(S_{C}(K_{ZZ}))$

Using the definiton of $S_{C}(K_{ZZ})$ we get :

$\displaystyle\text{tr}(S_{C}(K_{ZZ}))=\sum_{i=1}^{N-M}K_{X_{i}}-K_{X_{i}Z}K_{Z}^{-1}K_{ZX_{i}}$

where every element of the sum is a scalar. Taking
$W^{\top}\overline{\Lambda}W$ the eigendecomposition of $K_{Z}^{-1}$,
$w_{i}=WK_{X_{i}Z}$ and assuming a kernel variance $v$ of 1 (although
generalizable to all variances) and a translation invariant kernel such that
$k(x,x)=1$ we get :

$\displaystyle K_{X_{i}}-K_{X_{i}Z}K_{Z}^{-1}K_{ZX_{i}}=1-w_{i}^{\top}\Lambda
w_{i}=1-\sum_{j=1}^{M}\overline{\lambda_{j}}(w_{i})_{j}^{2}$
$\displaystyle\leq
1-\overline{\lambda}_{\min}\|w_{i}\|^{2}=1-\overline{\lambda}_{\min}\|K_{X_{i}Z}\|^{2}\leq
1-\overline{\lambda}_{\min}\rho^{2}$

Where we used the fact that at least $X_{i}$ was close enough to at least one
$Z_{j}$ such that $k(X_{i},Z_{j})>\rho$. For clarity we replace
$\overline{\lambda}_{\min}=\lambda^{-1}_{\max}$ where $\lambda_{\max}$ is the
largest eigenvalue of $K_{Z}$. When summing over the trace we get the final
bound :

$\displaystyle\|K_{X}-K_{XZ}K_{Z}^{-1}K_{ZX}\|\leq(N-M)\left(1-\frac{\rho^{2}}{\lambda_{\max}}\right)$

Now by construction all off-diagonal terms of $K_{Z}$ are smaller than $\rho$.
Using the equality (Stewart & guang Sun, 1990)

$\displaystyle|\lambda_{i}(A)-\lambda_{i}(B)|\leq\|A-B\|,\quad\forall
i=1,\ldots,N$

We get that

$\displaystyle|\lambda_{\max}(K_{Z})-1|\leq$
$\displaystyle\|K_{Z}-I\|_{2}=\sqrt{\sum_{i\neq
j}\left(K_{Z}\right)^{2}_{ij}}$ $\displaystyle\leq$ $\displaystyle M(M-1)\rho\
$

Assuming $\lambda_{\max}(K_{Z})\geq 1$, we get

$\displaystyle\lambda_{\max}(K_{Z})\leq 1+M(M-1)\rho_{out}$

Getting then the final bound :

$\displaystyle\|K_{X}-Q_{X}\|\leq(N-M)\left(1-\frac{\rho^{2}}{1+M(M-1)\rho}\right)$

###  D.1 Empirical Comparison

These bounds are difficult to compare due to the different parameters
characterizing them. Nevertheless we give an example by comparing the bound
and the empirical value on toy data drawn uniformly in 3 dimensions in figure
5. For each $N$ we ran our algorithm and input the required $M$ in the bounds
as the resulting number of selected inducing points. We show in the section 4
the empirical effect on the accuracy and on the number of points given the
choice of $\rho$.

Figure 5: Evaluation of the $\|K_{X}-Q_{X}\|$ given the OIPS algorithm and
computation of the bound from Burt et al. (2019) given in equation 6 and our
bound given in equation 7

##  Appendix E Experiments parameters

For every problem we use an isotropic Squared Exponential Kernel :

$\displaystyle
k(\mathbf{x},\mathbf{x}^{\prime})=v\exp\left(-\frac{\|\mathbf{x}-\mathbf{x}^{\prime}\|^{2}}{h^{2}}\right)$

Where $h$ is initialized by taking the median of the lower triangular part of
the pairwise distance matrix of the first subset of points and fixed for the
rest of the training. Future work will involve working with kernel parameter
optimization as well. We fix the noise of the Gaussian likelihood to
$\sigma^{2}=0.01$.

IPs were optimized via ADAM ($\alpha=10^{-2}$).


# MaAST: Map Attention with Semantic Transformers
for Efficient Visual Navigation

Zachary Seymour† Kowshik Thopalli∗ Niluthpol Mithun† Han-Pang Chiu† Supun
Samarasekera† Rakesh Kumar† †SRI International; Email:
<EMAIL_ADDRESS>State University; Email<EMAIL_ADDRESS>
###### Abstract

Visual navigation for autonomous agents is a core task in the fields of
computer vision and robotics. Learning-based methods, such as deep
reinforcement learning, have the potential to outperform the classical
solutions developed for this task; however, they come at a significantly
increased computational load. Through this work, we design a novel approach
that focuses on performing better or comparable to the existing learning-based
solutions but under a clear time/computational budget. To this end, we propose
a method to encode vital scene semantics such as traversable paths, unexplored
areas, and observed scene objects–alongside raw visual streams such as RGB,
depth, and semantic segmentation masks—into a semantically informed, top-down
egocentric map representation. Further, to enable the effective use of this
information, we introduce a novel 2-D map attention mechanism, based on the
successful multi-layer Transformer networks. We conduct experiments on 3-D
reconstructed indoor PointGoal visual navigation and demonstrate the
effectiveness of our approach. We show that by using our novel attention
schema and auxiliary rewards to better utilize scene semantics, we outperform
multiple baselines trained with only raw inputs or implicit semantic
information while operating with an $80\%$ decrease in the agent’s experience.

##  I Introduction

Humans employ semantic scene structures to reason about the world and pay
particular attention to relevant semantic landmarks to develop navigation
strategies [1, 2]. Therefore, humans can efficiently learn from past
navigation experience to explore new environments, such as discovering common
semantic scene entities that can be generalized to similar but previously
unseen places.

Figure 1: We show an overall diagram of our proposed approach, MaAST. Given
RGB and 0ptinputs, as well as an accumulated top-down egocentric semantic map
constructed by our system, the model uses features from both the visual
perception model and our novel map attention module to predict its next
action. In addition to the input images, we also visualize the learned
semantic map attention, projected back onto the RGB observation.

The ultimate goal of visual navigation for autonomous agents is to enable
agents to resemble or even exceed these human capabilities. A traditional
approach to this problem is to localize the agent in a map of the environment
that is built beforehand or constructed using simultaneous localization and
mapping (SLAM) algorithms [3, 4, 5]. Paths are then planned to convey the
agent to target locations [6, 7, 8]. These geometry-based methods require
extensive hand-engineering, and cannot be easily applied to new unexplored
environments.

Recently, learning-based methods—with deep reinforcement learning (DRL)
leading the way, are being developed to address this problem. DRL methods
directly learn a mapping from observations to actions through trial-and-error
interactions with its environment. They have demonstrated promising results on
navigation tasks and showed superior performance compared to geometry-based
methods [9]. However, current state-of-the-art DRL methods require training
with massive amounts of observations to achieve satisfactory performance. They
lack the semantic reasoning capabilities that humans possess to quickly learn
from past experience and extrapolate to new environments. Hundreds of millions
of interactions with the training environments, requiring enormous
computational resources and distributed processing [10], are mandatory to
converge to a reasonable policy for complicated scenarios.

In this paper, we take a step towards more efficient learning, as humans do:
learning to achieve comparable (or better) visual navigation performance for
autonomous agents with less available budget. The budget can be in terms of
the number of data observations available to the agent, or the available
computational resources (and, thus, time) available for training the model.

To achieve this objective, we propose to synergistically utilize the scene
semantics along with a novel structured attention mechanism in a DRL model,
which we call Map Attention with Semantic Transformers, or MaAST (Figure 1).
We propose to first construct a memory structure in which we encode the
semantic class of each object (or region) the agent perceives in the
environment. We also introduce a novel formulation of the popular Transformer
architecture [11], which we refer to as egocentric map Transformer, to
encourage the agent to learn pertinent objects and regions based on their
spatial relationship with the agent. This attention module automatically
focuses on relevant parts of the map memory structure so as to determine the
next action to take.

Through this work, we make the following observations:  i) a naïve data-driven
approach of utilizing scene semantics provides no added benefit to using an
egocentric occupancy map [12];  ii) on the other hand, we show that with our
novel attention mechanism, we outperform multiple state-of-the-art approaches
particularly in terms of path efficiency; and  iii) through systematic
ablation experiments, we establish empirically the superior efficacy of our
proposed attention mechanism on semantic features. Our observations
corroborate our hypothesis: just as humans do, autonomous agents should pay
careful attention to semantic landmarks to obtain improved performance.  Thus,
the contributions of our proposed approach, MaAST, are as follows:

  1. 1.

To the best of our knowledge, we present the first study on the effective use
of perceived scene semantics and their spatial arrangement to train an agent
end-to-end on the task of visual navigation in unseen environments.

  2. 2.

We introduce a novel 2-D map attention mechanism, based on Transformers, for
encouraging model to extract features from and to focus on the most relevant
areas of structured, egocentric, top-down spatial information.

  3. 3.

We demonstrate significant improvements in the policy’s performance metrics
and sample efficiency when learned under restricted training budgets.

##  II Related Work

DRL for Navigation: There is a recent surge of interest in using learning-
based methods and DRL for visual navigation, and consequently, a number of
methods have been proposed [13, 14, 15, 16, 12, 17, 18, 10, 19]. Due to the
prohibitive costs associated with physically training agents with DRL, most of
the methods instead train agents in a simulator with multi-threaded
implementations. To this end, several simulators, predominantly supporting
indoor navigation, have been proposed [9, 20, 21, 22, 17, 23, 24]. Similarly,
several 3D datasets have been collected for indoor navigation. Many are
synthetic [25, 26, 27], based on CAD models and hence lacking realism, while
others [28, 22, 29] consist of 3D scans of real environments. Thus, many
recent works in visual navigation (including our own) focus on these photo-
realistic datasets [9, 30, 31, 32].

Exploration and Mapping in DRL: It has been shown that a key factor for
success in navigation is exploration; _i.e_., to increase an autonomous
agent’s coverage of a given area with efficacy [33, 34]. While [33] uses
heuristics and [34] depends on a human controller to build maps and explore,
recent works [12, 35, 36, 19] propose solutions to this task of exploration
via learning. Our work is most closely related to recent works [19, 12, 37,
38] that address the problem of task-agnostic exploration, using DRL to learn
effective exploration policies that maximize the coverage of a given
environment. However, a key drawback in the use of top-down occupancy map [19,
12] is a failure to encode the diverse semantic cues such as doors, different
rooms, _etc_. that humans use to explore or navigate. While several recent
works have begun to show promise in leveraging a hierarchical DRL policy
combined with an analytical planner, our focus remains on improving the
efficiency of end-to-end DRL solutions by improving the intermediate scene
representation. We propose a novel solution which uses segmentation masks of
the current observation to accumulate top-down, egocentric semantic maps.
However, we find the richness contained in these maps adds additional
complexity for the policy network to properly make use of these features.
Consequently, we also introduce a novel multi-layer Transformer architecture
for processing such 2-D top-down structured information, allowing more
relevant features to be extracted.

Semantic Feature Fusion: It has been shown in prior works that semantic cues
leads to improved performance in learning-based navigation methods [39, 31] as
would intuition confirm it to be. However, these methods use the semantically-
segmented images as direct inputs to the model, which directly discards
information about the 3D structure of the scene. By contrast, we propose to
use those cues to build better occupancy maps and thus a better memory
structure for our policy, as opposed to extending RL agents with specialized
memory structures such as [40, 41].

##  III Approach

##### Problem Setup:

In this work, we consider the task of PointGoal navigation; _i.e_., given a
specified starting location and orientation, the agent is required to navigate
to the desired target location in an unseen cluttered environment. However,
our proposed method is general and can be easily extended to other navigation
tasks, such as ObjectGoal and AreaGoal tasks. We refer our readers to [42] for
a concise description of these tasks. We assume that our navigation agents are
equipped with an RGB camera and a 0ptsensor. We also assume the agent has a
semantic sensor, capable of producing semantic segmentation of the current RGB
camera observation - a class number $c\in\\{1,\dotsc,N_{c}\\}$ for each pixel
in the RGB image. Note our goal is to show increased learning efficacy of the
agent, given an improved understanding of the scene.

Our objective is to learn a policy $\pi$ through reinforcement learning that
makes effective use of all three sensory outputs (RGB camera, 0ptsensor, and
the semantic sensor) for navigation. To achieve this, we propose a novel
method to first construct and maintain an egocentric semantic map of the
environment using the 0ptand semantic sensors. We construct an image of the
map such that the agent is at the center, and the map is rotated such that the
agent’s heading points upwards. Previous work has shown that providing
autonomous agents a local map of its surroundings enables stronger reward
signals to reinforce learning and encourages exploration of new environments
[12]. Our intuition is that enhancing the map with a structured semantic
representation of the objects and regions in a scene will allow the agent to
make better decisions with regards to its goal, in addition to exploring
unseen areas. We finally propose a novel structured attention mechanism to
extract information from the map, such that the policy network learns to focus
on most relevant regions in the map to predict its next action.

###  III-A Egocentric Semantic Map Construction

For map construction, we primarily follow [12], in the setting where we assume
no estimation error on the agent’s pose. Concisely, when an agent takes an
action $a_{t}$ at time step $t$, it receives a set of observations
$O_{t+1}=(r_{t+1},d_{t+1},s_{t+1})$ representing the outputs from the RGB,
0pt, and semantic sensors, respectively. The pixels in the depth image can be
back-projected to a 3-D point cloud using the known camera intrinsic
parameters. The extrinsic parameters can then be calculated from the agent’s
current pose estimate to transform the point cloud from the camera’s reference
frame to the world frame. The points are then projected down to form a 2-D map
of the environment. Finally, the map is cropped to a fixed radius $r$ around
the agent such that the agent is at the center, of the image and is rotated
such that the agent’s heading points upwards. In [12], three types of
information are stored in the map. Any points above and below some height
threshold are projected down and stored in the map as obstacles. The remaining
points are stored as traversable space, and the rest of the map is treated as
yet unexplored.

Information about traversable and non-traversable space is extremely useful to
support path planning in autonomous agents; however, our intuition is that a
large amount of this information, particularly for short-term action
decisions, is encoded in depth image already, as evidenced by the strong
performance of agents with only a depth sensor [30]. Although exploration and
map-building allow the learned policy to better support back-tracking and
movement to unexplored areas, we propose that discriminating different objects
and free space is more useful for long-term decision making and reward
prediction, particularly in large environments where an agent must traverse
several rooms to achieve its goal.

Figure 2: An example of the observations available to the agents. Clockwise
from top left: RGB; 0pt, colorized with Turbo [43]; semantic segmentation
mask; occupancy map, where green denotes traversable space and blue obstacles;
semantic map; a ground truth map of the traversed path (for visualization
purposes only).

Our approach is to enhance the information stored in the agent’s map of the
environment with the semantic classes of perceived objects and components in
the scene. That is, for each point categorized as an obstacle above, we
instead store its semantic class (_e.g_., the highest prediction class
conditional probability of the pixel from semantic segmentation or value given
from the semantic sensor) directly in the map. When there are instances of
vertically overlapping objects (_e.g_., lamp hanging over a table) or if the
map resolution is low, some points may be projected down into the same map
location, resulting in a loss of information where one class overwrites
others. As such, we instead treat each location in an $2r\times 2r$ map $M$ as
a binary vector $M_{ij}\in\\{0,1\\}^{N}_{c}$ where, $k=1$ if class $k$ is
present at that location and $0$ otherwise. In this way, as the agent moves
through the environment, it accumulates a map containing a bag-of-classes at
each grid location. In addition to providing a richer source of information
about the environment, this semantically enhanced map allows the same policy
architecture to transit easily to other navigation tasks (e.g., ObjectGoal)
where the agent must identify semantics of its surroundings for successful
goal achievement. Figure 2 shows an example, providing a visualization of the
various observation modalities available to the agents.

###  III-B Policy Architecture

An overall diagram of our policy architecture is shown in Figure 1. The
network receives two sources of information, an RGB-D observation and a 2-D
egocentric semantic map. Each of these is processed by a convolutional neural
network (CNN) to produce visual and map feature vectors, respectively. We
denote the RGB and 0ptobservations at time step $t$ by $(r_{t},d_{t})$. The
visual model, denoted $f_{CNN}$, transforms $(r_{t},d_{t})$ to
$(r^{emb}_{t},d^{emb}_{t})$ by $f_{\text{CNN}}(r_{t}),f_{\text{CNN}}(d_{t})$.
In our experiments, we concatenate both RGB and 0ptobservations and transform
them by $f_{\text{CNN}}$, obtaining the corresponding output as
${rd}^{emb}_{t}$; for brevity and without loss of generality, we use
$r^{emb}_{t}$ to denote the same. While in prior work—where a policy is
learned exclusively for exploration [12]—each $f_{\text{CNN}}$ was implemented
by a ResNet18 [44] CNN pretrained on Imagenet, we found the simpler, 3-layer
CNN described in [9] to give better performance for navigation-oriented tasks.

We represent by $f_{\text{MAP}}$ the network that transforms the egocentric
semantic map at time step $t$, $M_{t}$ (Section III-A). We consider two
formulations of $f_{\text{MAP}}$. In the first case, $f_{\text{MAP}}$ uses the
same architecture as $f_{\text{CNN}}$: a 3-layer CNN. This mirrors the method
used in [12], where the visual and map information are processed by two
versions of the same network with different weights. However, because the
information stored in our semantic map is much richer than that in the
occupancy map, we find that the same CNN architecture is unable to adequately
extract meaningful representations from it. Drawing inspiration from prior
work in neural mapping and memory [40], we instead design a network for
processing the map input by treating it like a memory unit. Unlike in [40], we
would like to explicitly preserve the geometry and layout of the scene. We do
not need to learn a specialized method to “write” to the memory. We only need
to “read” (or extract feature) from it. To this end, we utilize a form of
Transformer architecture [11, 45], adapted to use both a two-dimensional self-
attention mechanism [46] and to learn specialized positional embeddings to
better take advantage of the structured nature of the map input. It allows the
network to better learn an representation of semantic classes present in the
scene and to extract information about the relevant regions of the map. We
next present our map attention mechanism, which is designed for this problem.

###  III-C Egocentric Map Transformer

Our map attention mechanism is chiefly inspired by the use of the Transformers
in natural language processing, which are deep neural networks consisting of
multiple layers of multi-headed self-attention. In the case of natural
language (_cf_. [11, 45]), the self-attention is generally computed using
feature representations of each subword in a sentence, computed as the sum of
two learned embeddings: a token embedding, which is specific to each subword,
and a positional embedding, indicating the position of the token in a
sentence. This composition allows the subword representation to vary depending
on its location in the sentence.

Figure 3: An overview of proposed map Transformer module. The input semantic
map (color-coded by class) is on the left and, the encoded positional indices
(with colors becoming darker closer to the agent) is on the right.

Prior works using spatial or image-based self-attention have primarily
operated on images [46] (where there is no direct analogue for the positional
embedding) or on a sequence of image region features (in which case position
encodings are drawn from alignment with corresponding words [47] or bounding
box [48]). However, because the input to $f_{\text{MAP}}$ consists of an
$2r\times 2r\times N_{c}$ map centered on the agent, each map cell has
important structural information. It is important to encode information about
a cell based on its current relationship to the agent. Namely, for a map of
radius $r$, we propose to construct a $2r\times 2r$ matrix of position indices
$\mathcal{P}$ using by a Gaussian kernel, centered on the agent, with a scale
factor of $\frac{r}{2}$. As more of the mass of the Gaussian kernel is
concentrated around the center, this has the benefit of giving fine-grained
positional representations to map cells nearer the agent than those farther
away (Figure 3).

Given such a kernel matrix, we construct $\mathcal{P}$ by assigning each
unique value in the kernel a unique consecutive integer, which are then used
to index the learned positional embeddings. Thus, the sum of these embeddings
and the bag-of-embeddings for the semantic classes at each cell are used as
the input to the multi-layer Transformer.

We adapt each layer of the Transformer to utilize $1\times 1$ convolutions to
preserve the spatial dimensions of the map before pooling across both spatial
dimensions and the final output. We denote this final transformed feature
representation $f_{\text{MAP}}(M_{t})$ by $M^{emb}_{t}$, with both
$r^{emb}_{t},M^{emb}_{t}\in\mathbb{R}^{N_{h}}$ and $N_{h}$ is the hidden
dimension of the policy network. The pooled outputs of $f_{\text{CNN}}$ and
$f_{\text{MAP}}$ are finally concatenated, and fused by a fully-connected
layer. The output along with the agent’s previous action is fed into a one-
layer gated recurrent unit (GRU) [49], that enables the agent to maintain
coherent action sequences across several time steps (the actor) followed by a
linear layer (the critic) to predict the next action.

###  III-D Rewards and Optimization

The network is trained end-to-end using reinforcement learning, particularly
proximal policy optimization (PPO) [50], following [9]. All policies trained
in this manner receive a reward $R_{t}$ at time step $t$ for moving closer to
the goal equal to the change in distance to the goal plus a large reward $s$
if the goal is reached and a small time penalty $\lambda$. For agents with
access to a map of the environment, we also add an auxiliary reward equal to
the percentage of map tiles that have been revealed, to encourage both
exploration and better use of the map features. Our trained policies also
include a small penalty for collisions with environment, equal to
$0.01\lambda$.

##  IV Evaluation

Simulator and Dataset: We use Habitat simulator [9], which supports different
datasets such as Matterport3D [28], Gibson [22], _etc_. We focus our
experiments on Matterport3D [28], which consists of 3D reconstructions of $90$
houses with a total of $2056$ rooms, as it exhibits the greatest episodic
complexity compared to the others. We use standard splits following [9]. It is
to be noted that there is no overlap of scenes in the Matterport3D splits. We
refer to [9] for more details.

Evaluation Metrics: An episode is registered as a success if (i) the agent has
taken fewer than $500$ steps, (ii) the distance between the agent and goal is
less than $0.2\text{\,}\mathrm{m}$, and (iii) the agent takes STOP action to
indicate that it has reached goal. The third condition eliminates a situation
when the agent randomly stumbles upon the target and receives reward. We also
report success weighted by path length (SPL) [42]. SPL is a measure of the
efficacy of the policy’s path taken to the goal compared against the ground
truth shortest path.

TABLE I: Results of our proposed method, compared against several
alternatives, evaluated for visual navigation on the Matterport3D validation
set. We report both success weighted by path length (SPL) and episode success
rate. $\mathbf{\dagger}$: uses our egocentric map Transformer.

|  |  | Rewards |  |
---|---|---|---|---|---
Method | Map | Goal | Exploration |  SPL (%) | Succ(%)
RGB-D [9] | RL (PPO) |  | $\checkmark$ |  | $34$ | $51$
RGB-D [9] | SLAM |  |  |  | $42$ | -
RGBD+OCC [12] | RL (PPO) | Occupancy | $\checkmark$ | $\checkmark$ | $43$ | $52$
MaAST | RL (PPO) |  Semantic$\dagger$ | $\checkmark$ | $\checkmark$ | 47 | 54

Implementation Details: Following [42], we use the same experimental setup as
[9] for PointGoal navigation. We implemented the networks using PyTorch [51]
and the habitat-sim and habitat-api modules [9]. For training, we use rollout
size of 256, hidden dimension of 512, and learning rate of $10^{-4}$. For our
egocentric map Transformer, we adapt the implementation [52] as described in
Section III-C. We use a 2-layer BERT model with 4 attention heads each and
embeddings of size 128 for both positional and semantic embeddings. As in [9],
we work with a case where our agents are equipped with an idealized GPS sensor
and compass. Following the use of ground truth scene information (such as
ground truth depth) in prior works [12, 9, 10, 53], we utilize the known depth
and label of each pixel from the simulation environment to enable a fair
comparison.111However, we experiment below leveraging MaAST with online
predicted semantics, as well.

###  IV-A Quantitative Results

####  IV-A1 Compared Methods

We compare MaAST with several baselines in Table I on the MatterPort3D [28]
validation set.

RL (PPO): The agents are trained end-to-end using DRL, namely PPO, with reward
mechanism in Section III-D. We study the performance of RL-based agents with
different input sensor modalities:  RGB-D, with only RGB and 0ptsensors as
inputs;  RGBD+OCC, the approach proposed in [12] (_i.e_., along with RGB-D
input, the method also uses a egocentric occupancy map), trained with both
goal and exploration rewards. In prior work [12], the policy architecture was
trained exclusively for exploration; however, in our case, it is trained by
PPO end-to-end for PointGoal navigation.

While algorithms other than vanilla PPO have been recently applied in the
visual navigation space to enable distributed training with large amounts of
experience [10], a direct comparison with these methods is beyond the scope of
this paper as  i) DD-PPO is a DRL algorithm more than a specific visual
navigation solution, and  ii) we can easily train MaAST with any proven RL
algorithm to achieve performance boosts from more efficient, large-scale
training.  Further, while recent works have shown the success of using
hierarchical DRL policies paired with analytical planners such as A∗ in
exploration and navigation [19, 37], we restrict our focus on learning and
improving end-to-end RL policies with simpler modules. Our proposed approach
(incorporating important semantic scene information into the map) can be
incorporated with [19] as we did with [12]. We leave it as a future work.

As our main objective is to show MaAST’s effectiveness under budget
constrained situations, we evaluate all the methods under a fixed training
budget of 14 million steps of experience, as this was the point at which a
0ptagent has been shown to exceed performance of SLAM [9].

####  IV-A2 Analysis of Results

In Table I, we demonstrate that the proposed approach (MaAST) significantly
outperforms other methods and baselines, under a much reduced computational
load. Agents equipped with no visual sensors (i.e., blind) are expected to
show poor performance. Surprisingly, a blind agent [9] trained by PPO is
already able to achieve a modest success (35%) with 75 million steps of
training experience. However, agents equipped with visual sensors show large
performance improvement with reduced experience.

Among agents equipped with visual sensors, MaAST shows significant improvement
over other agents. The improvement is $\mathbf{+13\%}$ absolute
($\mathbf{+38\%}$ relative) in SPL as compared to RGB-D alone and
$\mathbf{+4\%}$ absolute ($\mathbf{+9\%}$ relative) as compared to RGBD+OCC.
In terms of success rate, the performance increase is comparatively less
($+6\%$ relative over RGB-D and $+4\%$ relative over RGBD+OCC). This shows
that even though most of the methods succeed at nearly the same rate, MaAST’s
policy demonstrates superior efficacy in producing shorter paths to the
target, due to our attention mechanism’s ability to focus on more relevant
parts of the map, such as potential collisions or new areas to explore. With
respect to the statistical significance of our results, we evaluated the
performance of MaAST averaged over 5 random seeds and obtained SPL of $47.5\pm
0.7$, making the performance gain over other compared methods roughly an order
of magnitude greater than the standard deviation of MaAST’s performance.
Furthermore, we note that MaAST is able to achieve significant improvements
over SLAM in only 14 million training steps, which could not be achieved by
RGB-D alone in prior work, even with five times more experience [9].

###  IV-B Ablation Study

To investigate the impact of different components of our proposed MaAST, we
perform an ablation study comparing several baselines in Table II. All the
methods in Table II are trained with both goal and exploration rewards except
RGB-D which is trained with only goal rewards.

Exploration Rewards. We can compare RGB-D and RGBD+EXP baselines in Table II
to evaluate the impact of the addition of exploration reward. RGB-D agent
performs reasonably well with a $51\%$ success rate. However, as seen in the
SPL of RGB-D ($34\%$), the agent takes much longer paths as compared to the
ground-truth shortest distance, thus rendering this policy inefficient in
terms of path length. We hypothesize this drop is due to the agent being not
able to make efficient use of the implicit semantic cues in the scene.

To encourage the agent to move more efficiently, we follow a similar procedure
as above to train a policy that utilizes RGB-D along with additional
exploration reward: RGBD+EXP. However, the agent has no explicit access to the
progressively growing, egocentric occupancy map. The method achieves a $4\%$
increase in SPL ($38\%$); thus, the addition of exploration reward not only
helps the agent reach its goals more often but also takes more efficient paths
to do so.

TABLE II: Ablation study of the proposed MaAST on Matterport3D. All models are
evaluated after training for 14 million steps of experience using RL (PPO).
$\mathbf{\dagger}$: uses our egocentric map Transformer.

| Method | Map |  SPL (%) | Succ(%)
---|---|---|---|---
MaAST w/o (EXP,SEM,ATT) | RGB-D |  | $34$ | $51$
MaAST w/o (SEM,ATT) | RGBD+EXP |  | $38$ | $53$
MaAST w/o ATT | RGBD+SEM | Semantic | $41$ | $49$
MaAST w/o SEM, + OCC | RGBD+OCC+ATT |  Occupancy$\dagger$ | $44$ | $52$
MaAST | RGBD+SEM+ATT |  Semantic$\dagger$ | 47 | 54

Egocentric Semantic Map. It is evident from Table II that our use of
egocentric semantic map leads to an overall improvement in performance. To
analyze the impact, we can compare several variants of MaAST (i.e.,
RGBD+OCC+ATT vs. MaAST, and RGBD+EXP vs. RGBD+SEM). We observe that MaAST
achieves ($+3\%$ absolute, $7\%$ relative) improvement in SPL and ($+2\%$
absolute, $4\%$ relative) improvement in success rate using egocentric
semantic map compared to RGBD+OCC+ATT (which uses egocentric occupancy map).
However, comparing RGBD+SEM to RGB-D, we find that use of semantic map helps
RGBD+SEM to achieve $+3\%$ improvement in SPL, but there is a drop in
performance in terms of success rate ($-2\%$). We suspect this is because the
information encoded in the egocentric semantic map is rich, however, the agent
is unable to adequately decode and focus on relevant parts of the map (which
inspires our use of the Transformer-based map attention mechanism).

Real _vs_. Predicted Semantics. To better measure the robustness of our method
to sensor noise, we conducted an experiment utilizing predicted semantic
segmentation, following the map construction method of [38]; _i.e_., segment
the RGB observation with Mask R-CNN trained on MSCOCO and project those
classes using 0pt. This yields a sparser map now with 80 semantic classes
rather than 40 from Matterport3D, and now only filled with confident
predictions from the semantic segmentation model rather than dense labels for
each pixel. Due to computational constraints, we train this model for 7.7
million steps of experience, at which point it achieves 34.8% SPL
outperforming our RGB-D results with about half as much experience. This
demonstrates the robustness of MaAST to even noisy semantic observations and
its ability to adapt them to efficient navigation.

Egocentric Map Transformer. Our novel attention (ATT) mechanism based on
multi-layer egocentric map Transformer leads to significant improvement in
performance (Table II). We observe that MaAST achieves large performance
improvement in SPL, compared to RGBD+EXP (+9%) and RGBD+SEM (+6%), due to the
effective use of semantic cues. However, despite having access to the semantic
map, RGBD+SEM fails to achieve consistent performance improvement over
RGBD+EXP. This phenomenon supports our hypothesis that egocentric map
transformer helps agents attend to most relevant regions of the map for
efficient navigation.

We also use the proposed egocentric map Transformer (Section III-C) with the
occupancy map (RGBD+OCC+ATT). However, this does not result in a noticeable
change in performance. We believe this is because of the information encoded
in the egocentric occupancy map is significantly less rich and less diverse
compared to the semantic map. Rather than encoding each map cell to about 40
semantic classes in the egocentric semantic map, each occupancy map cell
encodes either _unexplored_ , _traversable_ , and _non-traversable_.

###  IV-C Qualitative Results

In Figure 4, we provide some visualizations of the paths toward the goal
followed by the various methods in three different episodes from the
Matterport3D validation set. In the top row (Figures 4, 4 and 4), we compare
MaAST with RGBD+EXP, and RGBD+SEM. In the bottom row (Figures 4, 4 and 4), we
compare against our two baselines from prior work, RGB-D and RGBD+OCC. All
methods have their path colored with a gradient to capture the number of steps
taken by the agent, all scaled between 0 and 500 steps. For example, in Figure
4, RGB-D agent moves quickly towards the goal at first; however, it becomes
stuck behind a chair. When it moves away, its path is much more darkly
colored, to indicate the amount of time taken to recover from the obstacle.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 4: A visualization of the path taken by different methods for three
episodes from Matterport3D. The ground truth shortest path is shown by a solid
green line. The agents’ start and goal locations are marked with a blue and
red dot, respectively. The color of the agents’ paths shifts along a gradient
(reproduced in the legend) as the maximum number of steps for the episode
(500) is approached.

In the first episode (Figures 4 and 4), all the agents reach the goal, but the
RGB-D and RGBD+EXP take very long paths to do so. It is clear that RGBD+EXP
tends to very aggressively follow the available traversable space, which leads
to inefficient paths (Figure 4) or missing the goal entirely (Figure 4).
Figures 4, 4, 4 and 4 all help to demonstrate the efficiency gains of the
MaAST attention mechanism. Even in cases where several of the methods follow
similar paths to the goal, MaAST is more quickly able to find obscured free
space (such as around the obstacle in the center of the room in Figure 4) to
move more efficiently towards the goal.

The final episode (Figures 4 and 4) represents a failure case for all the
methods. MaAST and RGBD+SEM reach close to the goal; however the episodes are
registered as failures, as neither are within the $0.2\text{\,}\mathrm{m}$
success radius. On the other hand, RGBD+EXP completely misses the goal,
heading off the visualized map into the next room, while both RGB-D and
RGBD+OCC get stuck on the furniture and terminate. In our analysis, we find
that for this particular Matterport3D house model, there appears to be holes
in the 3D model towards and around the goal, which provide confusing features
to the policy network; _e.g_., all of the furniture at the bottom is fused
together. However, one of the strengths of leveraging semantics in our models
seems to be avoiding areas that either present narrow spaces with high
collision potential or low-lying objects below the agent’s field of view. This
is a instance when we observe the agent utilizing semantics of the environment
(_i.e_., “furniture is difficult to navigate through”) beyond just which areas
are free and which are not.

##  V Conclusion

In this paper, we introduced principled techniques for improved performance on
visual navigation tasks with autonomous agents, by leveraging rich semantic
features while simultaneously operating under a computational budget. Our
proposed MaAST, incorporates a novel attention mechanism based on multi-layer
Transformers, which encourages agents to focus on the most relevant areas of
the egocentric semantic map for navigation. Through systematic experimentation
with quantitative and qualitative analysis, we demonstrate the superior
performance of our proposed approach as compared with several baselines. We
show that MaAST provides significant performance gains (a $13\%$ gain in path
efficiency over purely visual methods), while also outperforming classical
geometry-based methods with decreased training budget (time, computational
requirements, and cost).

## References

  * [1] N. Burgess, “Spatial cognition and the brain,” _Annals of the New York Academy of Sciences_ , vol. 1124, no. 1, pp. 77–97, 2008.
  * [2] M. Denis and J. M. Loomis, “Perspectives on human spatial cognition: memory, navigation, and environmental learning,” _Psychological Research_ , vol. 71, no. 3, pp. 235–239, 2007.
  * [3] S. Thrun, W. Burgard, and D. Fox, _Probabilistic robotics_. MIT press, 2005.
  * [4] A. J. Davison and D. W. Murray, “Mobile robot localisation using active vision,” in _ECCV_ , 1998, pp. 809–825.
  * [5] G. N. DeSouza and A. C. Kak, “Vision for mobile robot navigation: A survey,” _IEEE transactions on pattern analysis and machine intelligence_ , vol. 24, no. 2, pp. 237–267, 2002.
  * [6] S. M. LaValle and J. J. Kuffner Jr, “Rapidly-exploring random trees: Progress and prospects,” 2000.
  * [7] J. Canny, _The complexity of robot motion planning_. MIT press, 1988.
  * [8] L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Probabilistic roadmaps for path planning in high-dimensional configuration spaces,” _IEEE transactions on Robotics and Automation_ , vol. 12, no. 4, pp. 566–580, 1996.
  * [9] M. Savva, A. Kadian, O. Maksymets, Y. Zhao, E. Wijmans, B. Jain, J. Straub, J. Liu, V. Koltun, J. Malik, D. Parikh, and D. Batra, “Habitat: A Platform for Embodied AI Research,” in _ICCV_ , 2019.
  * [10] E. Wijmans, A. Kadian, A. Morcos, S. Lee, I. Essa, D. Parikh, M. Savva, and D. Batra, “Decentralized distributed ppo: Solving pointgoal navigation,” _arXiv preprint arXiv:1911.00357_ , 2019.
  * [11] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin, “Attention is all you need,” in _NIPS_ , 2017, pp. 5998–6008.
  * [12] T. Chen, S. Gupta, and A. Gupta, “Learning exploration policies for navigation,” in _ICLR_ , 2019.
  * [13] M. Jaderberg, V. Mnih, W. M. Czarnecki, T. Schaul, J. Z. Leibo, D. Silver, and K. Kavukcuoglu, “Reinforcement learning with unsupervised auxiliary tasks,” _arXiv preprint arXiv:1611.05397_ , 2016.
  * [14] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell, “Curiosity-driven exploration by self-supervised prediction,” in _CVPR workshops_ , 2017, pp. 16–17.
  * [15] S. Gupta, D. Fouhey, S. Levine, and J. Malik, “Unifying map and landmark based representations for visual navigation,” _arXiv preprint arXiv:1712.08125_ , 2017.
  * [16] V. Mnih, A. P. Badia, M. Mirza, A. Graves, T. Lillicrap, T. Harley, D. Silver, and K. Kavukcuoglu, “Asynchronous methods for deep reinforcement learning,” in _ICML_ , 2016, pp. 1928–1937.
  * [17] E. Kolve, R. Mottaghi, D. Gordon, Y. Zhu, A. Gupta, and A. Farhadi, “Ai2-thor: An interactive 3d environment for visual ai,” _arXiv preprint arXiv:1712.05474_ , 2017.
  * [18] A. Dosovitskiy and V. Koltun, “Learning to act by predicting the future,” _arXiv preprint arXiv:1611.01779_ , 2016.
  * [19] D. S. Chaplot, D. Gandhi, S. Gupta, A. Gupta, and R. Salakhutdinov, “Learning to explore using active neural SLAM,” in _8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020_. OpenReview.net, 2020\. [Online]. Available: https://openreview.net/forum?id=HklXn1BKDH
  * [20] M. Savva, A. X. Chang, A. Dosovitskiy, T. A. Funkhouser, and V. Koltun, “Minos: Multimodal indoor simulator for navigation in complex environments,” _arXiv preprint arXiv:1712.03931_ , 2017.
  * [21] G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba, “OpenAI gym,” _arXiv preprint arXiv:1606.01540_ , 2016.
  * [22] F. Xia, A. R. Zamir, Z.-Y. He, A. Sax, J. Malik, and S. Savarese, “Gibson Env: Real-world perception for embodied agents,” in _CVPR_ , 2018, pp. 9068–9079.
  * [23] M. Kempka, M. Wydmuch, G. Runc, J. Toczek, and W. Jaśkowski, “Vizdoom: A doom-based ai research platform for visual reinforcement learning,” in _2016 IEEE Conference on Computational Intelligence and Games (CIG)_. IEEE, 2016, pp. 1–8.
  * [24] C. Yan, D. Misra, A. Bennnett, A. Walsman, Y. Bisk, and Y. Artzi, “Chalet: Cornell house agent learning environment,” _arXiv preprint arXiv:1801.07357_ , 2018.
  * [25] S. Song, F. Yu, A. Zeng, A. X. Chang, M. Savva, and T. Funkhouser, “Semantic scene completion from a single depth image,” in _CVPR_ , 2017, pp. 1746–1754.
  * [26] M. Fisher, D. Ritchie, M. Savva, T. Funkhouser, and P. Hanrahan, “Example-based synthesis of 3d object arrangements,” _ACM Transactions on Graphics (TOG)_ , vol. 31, no. 6, p. 135, 2012.
  * [27] A. Handa, V. Patraucean, V. Badrinarayanan, S. Stent, and R. Cipolla, “Understanding real world indoor scenes with synthetic data,” in _CVPR_ , 2016, pp. 4077–4085.
  * [28] A. X. Chang, A. Dai, T. A. Funkhouser, M. Halber, M. Nießner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3d: Learning from rgb-d data in indoor environments,” _2017 International Conference on 3D Vision (3DV)_ , pp. 667–676, 2017.
  * [29] I. Armeni, O. Sener, A. R. Zamir, H. Jiang, I. Brilakis, M. Fischer, and S. Savarese, “3d semantic parsing of large-scale indoor spaces,” in _CVPR_ , 2016, pp. 1534–1543.
  * [30] D. Mishkin, A. Dosovitskiy, and V. Koltun, “Benchmarking classic and learned navigation in complex 3d environments,” _arXiv preprint arXiv:1901.10915_ , 2019.
  * [31] A. Sax, B. Emi, A. R. Zamir, L. J. Guibas, S. Savarese, and J. Malik, “Mid-level visual representations improve generalization and sample efficiency for learning active tasks,” _arXiv preprint arXiv:1812.11971_ , 2018.
  * [32] W. B. Shen, D. Xu, Y. Zhu, L. J. Guibas, F. Li, and S. Savarese, “Situational fusion of visual representation for visual navigation,” in _ICCV_ , 2019\.
  * [33] B. Yamauchi, “A frontier-based approach for autonomous exploration.” in _cira_ , vol. 97, 1997, p. 146.
  * [34] S. Thrun, M. Bennewitz, W. Burgard, A. B. Cremers, F. Dellaert, D. Fox, D. Hahnel, C. Rosenberg, N. Roy, J. Schulte, _et al._ , “Minerva: A second-generation museum tour-guide robot,” in _ICRA_ , vol. 3. IEEE, 1999.
  * [35] N. Savinov, A. Raichuk, R. Marinier, D. Vincent, M. Pollefeys, T. Lillicrap, and S. Gelly, “Episodic curiosity through reachability,” _arXiv preprint arXiv:1810.02274_ , 2018.
  * [36] S. Gupta, J. Davidson, S. Levine, R. Sukthankar, and J. Malik, “Cognitive mapping and planning for visual navigation,” in _CVPR_ , 2017, pp. 7272–7281.
  * [37] S. K. Ramakrishnan, Z. Al-Halah, and K. Grauman, “Occupancy anticipation for efficient exploration and navigation,” in _Computer Vision - ECCV 2020 - 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part V_ , ser. Lecture Notes in Computer Science, A. Vedaldi, H. Bischof, T. Brox, and J. Frahm, Eds., vol. 12350. Springer, 2020, pp. 400–418. [Online]. Available: https://doi.org/10.1007/978-3-030-58558-7\\_24
  * [38] D. S. Chaplot, D. Gandhi, A. Gupta, and R. Salakhutdinov, “Object goal navigation using goal-oriented semantic exploration,” _CoRR_ , vol. abs/2007.00643, 2020. [Online]. Available: https://arxiv.org/abs/2007.00643
  * [39] W. Yang, X. Wang, A. Farhadi, A. Gupta, and R. Mottaghi, “Visual semantic navigation using scene priors,” _arXiv preprint arXiv:1810.06543_ , 2018\.
  * [40] E. Parisotto and R. Salakhutdinov, “Neural map: Structured memory for deep reinforcement learning,” _arXiv preprint arXiv:1702.08360_ , 2017.
  * [41] J. Oh, V. Chockalingam, S. P. Singh, and H. Lee, “Control of memory, active perception, and action in minecraft,” _arXiv preprint arXiv:1605.09128_ , 2016.
  * [42] P. Anderson, A. X. Chang, D. S. Chaplot, A. Dosovitskiy, S. Gupta, V. Koltun, J. Kosecka, J. Malik, R. Mottaghi, M. Savva, and A. R. Zamir, “On evaluation of embodied navigation agents,” _arXiv preprint arXiv:1807.06757_ , 2018\.
  * [43] A. Mikhailov, “Turbo, an improved rainbow colormap for visualization,” https://ai.googleblog.com/2019/08/turbo-improved-rainbow-colormap-for.html, 2019\.
  * [44] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in _CVPR_ , 2016, pp. 770–778.
  * [45] J. Devlin, M.-W. Chang, K. Lee, and K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _NAACL-HLT_ , 2019\.
  * [46] H. Zhang, I. J. Goodfellow, D. N. Metaxas, and A. Odena, “Self-attention generative adversarial networks,” in _ICML_ , ser. Proceedings of Machine Learning Research, vol. 97. PMLR, 2019, pp. 7354–7363.
  * [47] L. H. Li, M. Yatskar, D. Yin, C. Hsieh, and K. Chang, “Visualbert: A simple and performant baseline for vision and language,” _arXiv preprint arXiv:1908.03557_ , 2019.
  * [48] J. Lu, D. Batra, D. Parikh, and S. Lee, “Vilbert: Pretraining task-agnostic visiolinguistic representations for vision-and-language tasks,” _arXiv preprint arXiv:1908.02265_ , 2019.
  * [49] K. Cho, B. van Merrienboer, Ç. Gülçehre, D. Bahdanau, F. Bougares, H. Schwenk, and Y. Bengio, “Learning phrase representations using RNN encoder-decoder for statistical machine translation,” in _EMNLP_ , 2014, pp. 1724–1734.
  * [50] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [51] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer, “Automatic differentiation in PyTorch,” in _NIPS Autodiff Workshop_ , 2017.
  * [52] T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, and J. Brew, “Huggingface’s transformers: State-of-the-art natural language processing,” _ArXiv_ , vol. abs/1910.03771, 2019.
  * [53] V. Cartillier, Z. Ren, N. Jain, S. Lee, I. Essa, and D. Batra, “Semantic mapnet: Building allocentric semanticmaps and representations from egocentric views,” _CoRR_ , vol. abs/2010.01191, 2020. [Online]. Available: https://arxiv.org/abs/2010.01191