# Memory-efficient particle filter recurrent neural network for object
localization

Roman Korkin
Novosibirsk Technology Center
Schlumberger, Russia
<EMAIL_ADDRESS>&Ivan Oseledets
AIRI, Moscow, Russia
Skoltech, Moscow, Russia
<EMAIL_ADDRESS>&Aleksandr Katrutsa
Skoltech, Moscow, Russia
AIRI, Moscow, Russia
<EMAIL_ADDRESS>Corresponding author

###### Abstract

This study proposes a novel memory-efficient recurrent neural network (RNN)
architecture specified to solve the object localization problem. This problem
is to recover the object states along with its movement in a noisy
environment. We take the idea of the classical particle filter and combine it
with GRU RNN architecture. The key feature of the resulting memory-efficient
particle filter RNN model (mePFRNN) is that it requires the same number of
parameters to process environments of different sizes. Thus, the proposed
mePFRNN architecture consumes less memory to store parameters compared to the
previously proposed PFRNN model. To demonstrate the performance of our model,
we test it on symmetric and noisy environments that are incredibly challenging
for filtering algorithms. In our experiments, the mePFRNN model provides more
precise localization than the considered competitors and requires fewer
trained parameters.

##  1 Introduction

We consider the object localization problem and propose a novel GRU-like
architecture to solve it. Typically standard GRU-like models [1] are used to
process sequential data, e.g. to predict the next item in a sequence, and
classify or generate texts, audio, and video data. The object localization
problem differs from the aforementioned problems since auxiliary data about
the environment and particular measurements are available. Therefore, this
additional knowledge should be incorporated into the GRU architecture
properly. Such a modification can be based on the existing approaches to solve
the object localization problem, which are discussed further.

One of the classical non-parametric methods to solve the object localization
problem is particle filter [2], which estimates the filtered object state from
the states of auxiliary artificial objects that are called particles. A
modification of GRU and LSTM recurrent neural networks with particle filter
ingredients is presented in [3], where a particle filter recurrent neural
network (PFRNN) is proposed. The core element of PFRNN is the modified cell
(GRU or LSTM) equipped with analogs of particles and the corresponding weights
of particles to estimate the filtered state. However, PFRNN improves the
performance of the general sequential data processing and does not consider
specific features of the object localization problem. Therefore, we propose
the novel _memory-efficient PFRNN (mePFRNN)_ that combines the model
assumptions used in the classical filtering methods (e.g. Kalman filter and
particle filter) and parametrization from the GRU architecture. Such a
combination provides more accurate state estimation and improves robustness in
noisy and symmetric environments. Also, the Soft resampling procedure is used
to avoid the degeneracy issue and improve the stability of the filtered
states.

The main contributions of our study are the following.

  1. 1.

We propose a modification of the PFRNN architecture specified for the object
localization problem. The proposed mePFRNN model does not exploit environment
embeddings and extracts this data implicitly in the training stage.

  2. 2.

We perform an extensive experimental comparison of the proposed GRU-like
architecture with the existing recurrent neural networks and other non-
parametric methods like the particle filter.

  3. 3.

The proposed mePFRNN model requires the same number of parameters for
environments of different sizes.

### Related works.

The object localization problem appears in a lot of applications like driving
autonomous vehicles [4], navigation [5, 6], image processing [7], finance [8]
and fatigue predictions [9]. Therefore, there are a lot of different
approaches to solving it. We can split them into two classes: non-parametric
and parametric. The first class consists of classical methods that do not
require a training stage and perform filtering of the object states on the
fly. Examples of such methods are Kalman filter [10, 11], and its
modifications like extended [12], unscented [13], invariant extended [14] and
ensembled [15] Kalman filters. Also, methods related to the particle filter,
e.g. multiparticle Kalman filter [16], particle filters combined with genetic
algorithms [17], and particle swarm technique [18], box particle filter [19]
and others are non-parametric filtering methods. The second class consists of
parametric methods such that a pre-training stage is necessary before starting
filtering. Such methods are typically based on neural networks that are
trained on the collected historical data and then tested on the new data from
real-world simulations. Although the pre-training stage may require a lot of
time, one can expect that the inference stage, in which filtering is
performed, is sufficiently fast due to modern hardware acceleration. Moreover,
since the neural network models can efficiently treat sequential data [20,
21], the parametric methods can provide more accurate filtering results
compared to non-parametric methods.

Although the Transformer model [22] demonstrates superior performance over the
considered GRU RNN in sequence processing tasks, it consumes a lot of memory
to store parameters, requires special techniques for training [23] and may not
fit in the on-device memory limits. The memory-efficient Transformer models
[24, 25, 26] may be a remedy for the observed issue and will be investigated
in future work.

##  2 Problem statement

Consider the trajectory of object states encoded as a sequence of
$d$-dimensional vectors ${\mathbf{x}}_{i}\in{\mathbb{R}}^{d}$, where $i$ is an
index of the time moment $t_{i}$. For example, if the object’s state consists
of 2D coordinates and 2D velocity, then state dimension $d=4$. The states are
changed according to the motion equation, which combines the physical law and
the control system of the object. Formally we can write the motion equation as
follows

${\mathbf{x}}_{i}=f({\mathbf{x}}_{i-1},{\mathbf{u}}_{i},\bm{\eta}_{i}),$ (1)

where ${\mathbf{u}}_{i}$ is a vector of control at the time moment $t_{i}$,
for example, external forces, and $\bm{\eta}_{i}$ is a vector of noise
corresponding to the object motion at the time moment $t_{i}$. Since the
object moves with some noise, we should use additional measurements to
estimate states more precisely. Typically there are several beacons in the
environment, which are used by objects to measure some quantities that can
improve their state estimate. For example, distance to the $k$-nearest beacons
can improve the estimate of the object’s location. Formally, denote by
${\mathbf{y}}_{i}\in{\mathbb{R}}^{k}$ a vector of measurements at time moment
$t_{i}$ that is related with state estimate through the measurement function
$g:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$:

${\mathbf{y}}_{i}=g({\mathbf{x}}_{i},\bm{\zeta}_{i}),$ (2)

where $\bm{\zeta}_{i}$ is the additional noise of measurement.

Object localization problem is the problem of estimating object trajectory
from the given motion and measurement functions that represent the physical
law of the environment and beacons’ configuration, respectively. In this
study, we introduce the parametric model
$h_{{\bm{\theta}}}:{\mathbb{R}}^{d}\times{\mathbb{R}}^{k}\times{\mathbb{R}}^{n}\to{\mathbb{R}}^{d}$
that depends on the unknown parameters ${\bm{\theta}}\in{\mathbb{R}}^{n}$ and
performs filtering of the inexact state estimate ${\mathbf{x}}_{i}$ based on
the additional measurements ${\mathbf{y}}_{i}$. Assume we have training
trajectory of the ground-truth states $\\{{\mathbf{x}}_{i}^{*}\\}_{i=1}^{N}$.
Then we can state the optimization problem to fit our parametric model to the
training data $\\{{\mathbf{x}}_{i}^{*}\\}_{i=1}^{N}$ and evaluate the
generalization ability of the resulting model. In particular, the standard
loss function in such a problem is the mean square error loss function

$MSE=\frac{1}{N}\sum_{i=1}^{N}{\|h_{{\bm{\theta}}}({\mathbf{x}}_{i},{\mathbf{y}}_{i})-{\mathbf{x}}^{*}_{i}\|_{2}^{2}}$
(3)

such that the motion function $f$ and the measurement functions $g$ give the
state estimate ${\mathbf{x}}_{i}$ and measurement vector ${\mathbf{y}}_{i}$,
respectively.

We further focus on the plane motion setup, where the state vector consists of
2D coordinates ${\mathbf{c}}\in\mathbb{R}^{2}$ and a heading
$\alpha\in[0,2\pi]$, which defines the direction of movement, i.e.
${\mathbf{x}}=[{\mathbf{c}},\alpha]\in\mathbb{R}^{3}$. Therefore, we follow
[3] in slightly adjusting the MSE objective function (3) to treat coordinates
and angles separately and compose the weighted MSE loss function:

$wMSE=\underbrace{\frac{1}{N}\sum_{i=1}^{N}\|{\mathbf{c}}_{i}-{\mathbf{c}}^{*}_{i}\|_{2}^{2}}_{=\mathrm{MSE}_{c}}+\frac{\beta}{N}\sum_{i=1}^{N}(\alpha_{i}-\alpha_{i}^{*})^{2},\quad\text{where}\quad[{\mathbf{c}}_{i},\alpha_{i}]=h_{{\bm{\theta}}}({\mathbf{x}}_{i},{\mathbf{y}}_{i}),\quad{\mathbf{x}}_{i}^{*}=[{\mathbf{c}}_{i}^{*},\alpha_{i}^{*}],$
(4)

where $\beta>0$ is a given weight. However, the $wMSE$ loss function treats
angles $2\pi-{\epsilon}$ and ${\epsilon}$ as essentially different while they
are physically close. Thus, we propose a novel modification of the mean
squared loss function (3), that treats headings differently. In particular, we
compare not angles but their sine and cosine in the following way:

$L({\bm{\theta}})=\mathrm{MSE}_{c}+\frac{\beta}{N}\sum_{i=1}^{N}\left[(\sin\alpha_{i}-\sin\alpha^{*}_{i})^{2}+(\cos\alpha-\cos\alpha_{i}^{*})^{2}\right],$
(5)

where we use the same notation as in (4). Thus, we have the following
optimization problem:

$\begin{split}&{\bm{\theta}}^{*}=\operatorname*{arg\,min}_{{\bm{\theta}}}L({\bm{\theta}}),\\\
\text{s.t.
}&{\mathbf{x}}_{i}=f({\mathbf{x}}_{i-1},{\mathbf{u}}_{i},\bm{\eta}_{i})\\\
&{\mathbf{y}}_{i}=g({\mathbf{x}}_{i},\bm{\zeta}_{i}).\end{split}$ (6)

Additionally to the MSE-like loss function, we evaluate the resulting model
with the Final State Error (FSE) loss function, which reads as

$\mathrm{FSE}=\|{\mathbf{c}}_{N}-{\mathbf{c}}_{N}^{*}\|_{2},$ (7)

where $[{\mathbf{c}}_{N}^{*},\alpha_{N}^{*}]={\mathbf{x}}_{N}^{*}$,
$[{\mathbf{c}}_{N},\alpha_{N}]=h_{{\bm{\theta}}}({\mathbf{x}}_{N},{\mathbf{y}}_{N})$
and $t_{N}$ is a last-time moment in the considered period. Although the FSE
loss function is widely used in previous studies [3, 27], it may overestimate
the filter performance due to the uncertainty in the filtering process. The
final coordinates may be filtered very accurately by accident while filtering
the previous coordinates may be quite poor. Thus, we focus on the MSEc loss
function as the main indicator of the filter performance.

The key ingredient of this approach is the selection of the proper parametric
model $h_{{\bm{\theta}}}$. Following [3] we modify the GRU model such that it
solves the object localization problem specifically. A detailed description of
our modification is presented in the next section.

##  3 Particle filter

One of the most efficient non-parametric approaches to solving the
localization problem is the particle filter. This filter considers
artificially generated particles with states
${\mathbf{p}}^{(k)}_{i}\in\mathbb{R}^{d}$ at the $i$-th time step and the
corresponding weights $w^{k}_{i}\geq 0,\sum_{k=1}^{K}w^{k}_{i}=1$ such that
the estimate of the object state at the $i$-th time step is computed as
follows

$\hat{{\mathbf{x}}}_{i}=\sum_{k=1}^{K}w^{k}_{i}{\mathbf{p}}^{(k)}_{i},$

where $K$ is the number of particles. Particles’ weights are updated according
to the corresponding measurements and state updates based on the Bayes rule
and likelihood estimation, see [28] for details. The important step in the
particle filter is resampling, which corrects the updated particle weights and
states to improve the accuracy of estimate $\hat{{\mathbf{x}}}_{i}$. The
resampling step addresses the degeneracy issue, which means a few number of
particles have non-zero weights. This phenomenon indicates the poor
representation of the target object state. The purely stochastic resampling
samples particles’ indices from the multinomial distribution according to the
updated weights and then update particle states, respectively, see (8). After
resampling the resulting particle states are slightly perturbed with random
noise to avoid equal particles’ states.

$\begin{split}&i_{1},\ldots,i_{K}\sim\mathrm{Multinomial}(w^{1}_{i+1},\ldots,w^{K}_{i+1})\\\
&{\mathbf{p}}^{1}_{i+1},\ldots,{\mathbf{p}}^{K}_{i+1}\leftarrow{\mathbf{p}}^{i_{1}}_{i+1},\ldots,{\mathbf{p}}^{i_{K}}_{i+1}\\\
&w^{k}_{i+1}=\frac{1}{K}.\end{split}$ (8)

Since the particle filter processes sequential data through the recurrent
updates of the particles and weights, the natural idea is to incorporate a
similar approach in the recurrent neural network architecture. The particle
filter recurrent neural network is proposed in [3] and we briefly describe it
in the next section to highlight the difference with the proposed mePFRNN.

##  4 Recurrent neural networks inspired by particle filter

This section presents our RNN cell based on the particle filter idea,
explicitly measured data, and beacons’ positions. Since our model is a
modification of the PFRNN [3] model, we briefly provide the main ingredients
of this model.

### PFRNN.

Denote by $K$ a number of particles that are emulated in the PFRNN model.
Below we consider motion ${\mathbf{x}}_{i}^{(k)}$ and measurement
${\mathbf{y}}_{i}^{(k)}$ vectors corresponding to the $k$-th particle at the
$i$-th time moment, so $k=1,\ldots,K$ and $i=1,\ldots,N$. PFRNN considers the
environment as a 2D array and constructs its embedding through the following
encoder subnetwork:

$\mathrm{Conv}\to\mathrm{ReLU}\to\mathrm{Conv}\to\mathrm{ReLU}\to\mathrm{Conv}\to\mathrm{ReLU}\to\mathrm{Flatten}\to\mathrm{Linear}\to\mathrm{ReLU},$
(9)

where $\mathrm{Conv}$ is a convolution layer, $\mathrm{ReLU}$ denotes element-
wise ReLU non-linearity, $\mathrm{Linear}$ denotes a linear layer and
$\mathrm{Flatten}$ denotes a vectorization operation that reshapes the input
tensor to a vector. The output of this subnetwork is the environment embedding
vector ${\mathbf{e}}_{env}$. At the same time, the embeddings for observations
${\mathbf{y}}_{i}^{(k)}$ and motions ${\mathbf{x}}_{i}^{(k)}$ are constructed
via two linear layers and followed by ReLU activations and denoted by
${\mathbf{n}}_{i}^{(k)}$ and ${\mathbf{m}}_{i}^{(k)}$, respectively. Note that
the dimensions of ${\mathbf{n}}_{i}^{(k)}$ and ${\mathbf{m}}_{i}^{(k)}$ are
the same. Then, one transforms the environment embedding ${\mathbf{e}}_{env}$
to adjusted embeddings $\hat{{\mathbf{n}}}_{i}^{(k)}$ and
$\hat{{\mathbf{m}}}_{i}^{(k)}$ via two linear layers and followed ReLU
activations. Now, the dimensions of $\hat{{\mathbf{n}}}_{i}^{(k)}$,
$\hat{{\mathbf{m}}}_{i}^{(k)}$, ${\mathbf{n}}_{i}^{(k)}$ and
${\mathbf{m}}_{i}^{(k)}$ are the same. Finally, the input to the PFRNN cell
described below (see (11)) is a set of vectors ${\mathbf{v}}_{i}^{(k)}$
composed by concatenation of vectors
$\hat{{\mathbf{n}}}_{i}^{(k)}\odot{\mathbf{n}}_{i}^{(k)}$ and
$\hat{{\mathbf{m}}}_{i}^{(k)}\odot{\mathbf{m}}_{i}^{(k)}$, where $\odot$
denotes element-wise product.

The baseline PFRNN cell is presented in both a graphical way (see Figure 1)
and an analytical way (see equation (11)) for the reader’s convenience. We
note that this cell includes a reparametrization trick and updates not only
the hidden states for every particle ${\mathbf{h}}_{i}^{(k)}$ but also the
corresponding weights $w_{i}^{(k)}$ that are used in the resampling step.
These weights typically correspond to the probability of the particle being
equal to the ground-truth object state. However, in our experiment such
weights are the logarithm of the corresponding probabilities, therefore the
normalization step after update has the given form (see the last line in (11).
After that, we adjust the resampling step to deal with the logarithms of the
weights properly, see the paragraph below.

### Resampling procedure.

After the inference stage in the considered RNN cells, one has to make
resampling, to mitigate the potential degeneracy problem. There are different
approaches to performing resampling [29, 30]. The main requirement for the
resampling procedure in the parametric model is to be differentiable.
Therefore, the stochastic resampling (8) is not directly fitted to the
considered model. Instead, the Soft Resampling procedure [3] was proposed as a
trade-off between the accuracy and the related costs. This approach to
resampling considers a mixture of the distribution induced by weights and the
uniform distribution with probabilities $1/K$. Therefore, the formula for
updating weights and hidden states reads as follows.

$\begin{split}&i_{1},\ldots,i_{K}\sim\mathrm{Multinomial}(\alpha
w^{1}_{i+1}+(1-\alpha)/K,\ldots,\alpha w^{K}_{i+1}+(1-\alpha)/K)\\\
&{\mathbf{h}}^{1}_{i+1},\ldots,{\mathbf{h}}^{K}_{i+1}\leftarrow{\mathbf{h}}^{i_{1}}_{i+1},\ldots,{\mathbf{h}}^{i_{K}}_{i+1}\\\
&w^{k}_{i+1}\leftarrow\frac{w^{i_{k}}_{i+1}}{\alpha
w^{i_{k}}_{i+1}+(1-\alpha)/K},\end{split}$ (10)

where $\alpha>0$ to make the operation differentiable. Note that similar to
the stochastic resampling, the updated hidden states ${\mathbf{h}}^{k}_{i}$
are slightly perturbed. Section 5 provides more details on the usage of soft
resampling in our experiments.

Figure 1: Baseline PFRNN cell design, where
$\mathbf{a},\mathbf{o},\mathbf{z},\mathbf{c}$ denote the linear layers that
are used in computing the corresponding intermediate embeddings. For
simplicity, we skip the superscript $k$ that indicates the particle index.
This cell updates both particle hidden states and weights. Denote elementwise
addition and multiplication by $+$ and $\odot$.

$\displaystyle{\mathbf{a}}^{(k)}_{i}=$
$\displaystyle\mathrm{ReLU}({\bm{W}}_{a}{\mathbf{v}}^{(k)}_{i}+{\mathbf{b}}_{a})$
(11) $\displaystyle{\mathbf{o}}^{(k)}_{i}=$
$\displaystyle\mathrm{ReLU}({\bm{W}}_{o}{\mathbf{v}}^{(k)}_{i}+{\mathbf{b}}_{o})$
$\displaystyle{\mathbf{c}}_{i}^{(k)}=$
$\displaystyle\sigma({\bm{W}}_{c}[{\mathbf{a}}^{(k)}_{i},{\mathbf{h}}_{i-1}^{(k)}]+{\mathbf{b}}_{c})\odot{\mathbf{h}}_{i-1}^{(k)}$
$\displaystyle{\mathbf{z}}^{(k)}_{i}=$
$\displaystyle\sigma({\bm{W}}_{z}[{\mathbf{a}}^{(k)}_{i},{\mathbf{h}}_{i-1}^{(k)}]+{\mathbf{b}}_{z})$
$\displaystyle{\bm{\mu}}^{(k)}_{i}=$
$\displaystyle{\bm{W}}_{{\bm{\mu}}}[{\mathbf{a}}^{(k)}_{i},{\mathbf{c}}_{i}^{(k)}]+{\mathbf{b}}_{{\bm{\mu}}}$
$\displaystyle{\bm{\Sigma}}^{(k)}_{i}=$
$\displaystyle{\bm{W}}_{{\bm{\Sigma}}}[{\mathbf{a}}^{(k)}_{i},{\mathbf{c}}_{i}^{(k)}]+{\mathbf{b}}_{{\bm{\Sigma}}}$
$\displaystyle{\mathbf{\epsilon}}\sim$
$\displaystyle\;\mathcal{N}(0,{\bm{I}})$
$\displaystyle{\mathbf{d}}^{(k)}_{i}=$
$\displaystyle\mathrm{LeakyReLU}(\mathrm{BN}({\bm{\mu}}^{(k)}_{i}+{\bm{\Sigma}}^{(k)}_{i}\odot{\mathbf{\epsilon}}))$
$\displaystyle{\mathbf{h}}_{i}^{(k)}=$
$\displaystyle(1-{\mathbf{z}}^{(k)}_{i})\odot{\mathbf{d}}^{(k)}_{i}+{\mathbf{z}}^{(k)}_{i}\odot{\mathbf{h}}_{i-1}^{(k)}$
$\displaystyle{\mathbf{p}}_{i}^{(k)}=$
$\displaystyle{\bm{W}}_{w}[{\mathbf{o}}_{i},{\mathbf{h}}_{i}^{(k)}]+b_{w}$
$\displaystyle w_{i}^{(k)}=$
$\displaystyle{\mathbf{p}}_{i}^{(k)}+w_{i-1}^{(k)}-$ $\displaystyle-
LogSumExp({\mathbf{p}}_{i}^{(k)}+w_{i-1}^{(k)})$

### mePFRNN.

Since PFRNN encodes the environment with the convolution operation, it
requires training a number of parameters proportional to the environment size.
To reduce the number of trainable parameters, we do not use the data about an
environment as input to our model since such data, like beacons’ and
obstacles’ positions, have to be implicitly extracted in the training stage.
We expect such behavior of the considered mePFRNN since the environment is the
external factor to the localization problem and stays the same over the
particular trajectory. The motion and measurement vectors corresponding to
every particle are embedded into a high dimensional space via linear layer and
ReLU non-linearity. Then, the obtained embeddings are concatenated and
processed by a linear layer with LeakyReLU non-linearity. The result of the
latter operation is motion embedding ${\mathbf{e}}^{(k)}_{{\mathbf{u}}}$ for
every particle, which is additional input to the proposed mePFRNN cell. The
encoding procedure described above is summarized in scheme (12).

$\begin{array}[]{cc}{\mathbf{x}}_{i}^{(k)}\to\mathrm{Linear}\to\mathrm{ReLU}\;{}_{\searrow}&\\\
&\mathrm{Concatenation}\to\mathrm{Linear}\to\mathrm{LeakyReLU}\to{\mathbf{e}}^{(k)}_{{\mathbf{u}}}\\\
{\mathbf{y}}_{i}^{(k)}\to\mathrm{Linear}\to\mathrm{ReLU}\;{}^{\nearrow}&\end{array}$
(12)

Thus, mePFRNN is a voxel-independent model that can be easily used in very
large environments without increasing the number of trainable parameters. One
more benefit of the proposed approach becomes crucial if the beacons in the
environment are located not in the middle of the artificially generated voxels
in the PFRNN model. These voxels compose a grid for the considered environment
to identify the beacons and obstacles with convolution encoding. In this case,
the convolution operation does not adequately encode the beacons’ positions
and makes further filtering more noisy. The resulting cell is shown in Figure
2 graphically and in equations (13) analytically, where $MLP$ consists of two
sequential linear layers and intermediate $\mathrm{LeakyReLU}$ nonlinearity.
Note that, the Soft Resampling procedure is also used here similar to the
PFRNN model described above.

Figure 2: The proposed mePFRNN cell. Square block means elementwise square of
the input. MLP consists of two sequential linear layers and LeakyReLU
intermediate nonlinearity. Other notation is similar to the PFRNN.

$\begin{split}{\mathbf{e}}^{(k)}_{i}=&[{\mathbf{e}}^{(k)}_{{\mathbf{u}}},{\mathbf{y}}^{(k)}_{i}]\\\
{\mathbf{z}}^{(k)}_{i}=&\sigma({\bm{W}}_{z}[{\mathbf{h}}_{i-1}^{(k)},{\mathbf{e}}^{(k)}_{i}]+{\mathbf{b}}_{z})\\\
{\mathbf{r}}^{(k)}_{i}=&\sigma({\bm{W}}_{r}[{\mathbf{h}}_{i-1}^{(k)},{\mathbf{e}}^{(k)}_{i}]+{\mathbf{b}}_{r})\\\
{\bm{\mu}}^{(k)}_{i}=&{\bm{W}}_{{\bm{\mu}}}[{\mathbf{r}}_{i}^{(k)}\odot{\mathbf{h}}_{i-1}^{(k)},{\mathbf{e}}^{(k)}_{i}]+{\mathbf{b}}_{{\bm{\mu}}}\\\
{\bm{\Sigma}}^{(k)}_{i}=&{\bm{W}}_{{\bm{\Sigma}}}[{\mathbf{r}}_{i}^{(k)}\odot{\mathbf{h}}_{i-1}^{(k)},{\mathbf{e}}^{(k)}_{i}]+{\mathbf{b}}_{{\bm{\Sigma}}}\\\
{\mathbf{\epsilon}}\sim&\;\mathcal{N}(0,{\bm{I}})\\\
{\mathbf{d}}^{(k)}_{i}=&\mathrm{LeakyReLU}(\mathrm{BN}({\bm{\mu}}^{(k)}_{i}+{\bm{\Sigma}}^{(k)}_{i}\odot{\mathbf{\epsilon}}))\\\
{\mathbf{h}}_{i}^{(k)}=&(1-{\mathbf{z}}^{(k)}_{i})\odot{\mathbf{d}}^{(k)}_{i}+{\mathbf{z}}^{(k)}_{i}\odot{\mathbf{h}}_{i-1}^{(k)}\\\
w_{i}=&MLP({\mathbf{y}}_{i}^{(k)})^{2}+w_{i-1}-\\\
&-LogSumExp(MLP({\mathbf{y}}_{i}^{(k)})^{2}+w_{i-1})\end{split}$ (13)

### Alternative GRU-based models.

In addition to the proposed mePFRNN model, we also propose two approaches to
exploiting the classical GRU model (see Figure 3 and equations (14)) in the
object localization problem. Namely, the EnsembleGRU model consists of many
small GRU cells whose predictions are averaged to estimate the target object
state. The number of models in the ensemble and the number of trained
parameters in every model are selected such that the total number of the
trained parameters is approximately equal to # parameters in PFRNN times #
particles. The complementary approach is just to use the single GRU cell,
where the number of trained parameters is equal to # particles times #
parameters in PFRNN. Both approaches are complementary to the PFRNN and
mePFRNN models since they do not exploit particles. Also, note that the input
to the GRU cell in EnsembleGRU and HeavyGRU models is the same as the input to
the PFRNN cell.

Figure 3: Standard GRU cell, where ${\mathbf{z}}$ and ${\mathbf{r}}$ denote
the linear layers to compute ${\mathbf{z}}_{i}$ and ${\mathbf{r}}_{i}$,
$\mathrm{Lin}$ denotes linear layers to compute $\hat{{\mathbf{h}}}_{i}$, see
(14).

$\displaystyle{\mathbf{z}}_{i}=$
$\displaystyle\sigma({\bm{W}}_{z}[{\mathbf{v}}_{i},{\mathbf{h}}_{i-1}]+{\mathbf{b}}_{z})$
(14) $\displaystyle{\mathbf{r}}_{i}=$
$\displaystyle\sigma({\bm{W}}_{r}[{\mathbf{v}}_{i},{\mathbf{h}}_{i-1}]+{\mathbf{b}}_{r})$
$\displaystyle\hat{{\mathbf{h}}}_{i}=$
$\displaystyle\tanh({\bm{W}}_{h}{\mathbf{v}}_{i}+{\mathbf{b}}_{h}+$
$\displaystyle{\mathbf{r}}_{i}\odot({\bm{U}}_{h}{\mathbf{h}}_{i-1}+{\mathbf{b}}_{u}))$
$\displaystyle{\mathbf{h}}_{i}=$
$\displaystyle(1-{\mathbf{z}}_{i})\odot{\mathbf{h}}_{i-1}+{\mathbf{z}}_{i}\odot\hat{{\mathbf{h}}}_{i}$

##  5 Computational experiment

In this section, we demonstrate the performance of our model and compare it
with alternative neural networks and non-parametric models. For training the
compared neural networks we use RMSProp optimizer [31] since it shows more
stable convergence compared to Adam [32] and SGD with momentum [33], learning
rate equal to $5\cdot 10^{-4}$ and every batch consists of 150 trajectories.
The maximum number of epochs is 5000 for the considered environments. During
the training stage, a validation set of trajectories is used to identify the
overfitting. Therefore, different environments require a different number of
epochs before overfitting occurs. In particular, overfitting does not occur
after 5000 epochs in the world $10\times 10$. At the same time, overfitting is
observed after 600 and 200 epochs in the World $18\times 18$ and WORLD
$27\times 27$, respectively.

### Trajectories generation procedure.

To evaluate the considered methods and demonstrate the performance of the
proposed mePFRNN, we consider four environments, see Figure 4. Environments
world $10\times 10$, World $18\times 18$, and WORLD $27\times 27$ are
symmetric and therefore challenging for object localization since symmetric
parts can be confused by a filtering method. Environment _Labyrinth_ is not
symmetric and medium challenging for filtering methods. Thus, the considered
filtering methods are compared comprehensively due to the diversity in the
testing environments.

(a) world $10\times 10$

(b) World $18\times 18$

(c) WORLD $27\times 27$

(d) _Labyrinth_

Figure 4: Visualization of test environments. Black crosses denote beacons,
and grey blocks denote obstacles. The upper row represents the very symmetric
environments that are especially challenging for solving the localization
problem. The _Labyrinth_ environment is not symmetric and is similar to the
environment, which was used for the evaluation of filtering methods in [27].

To train the parametric models we need to generate a set of trajectories
$\\{{\mathbf{x}}_{i}^{*}\\}_{i=1}^{N}$. Since our tests assume that the
object’s initial state is unknown, we set the initial state
${\mathbf{x}}_{0}^{*}$ randomly for all generated trajectories. Initial states
do not intersect with obstacles. Then, every next iteration updates the object
state according to the motion equation, where external velocity $u\in[0,0.2]$
is known and the direction is preserved from the previous step within the
noise. In the case of a collision with an obstacle, the object’s direction is
changed randomly such that the next state does not indicate the collision. To
simulate engine noise, the velocity $u$ is perturbed by
$\eta_{r}\sim\mathcal{U}[-0.02,0.02]$. To simulate uncertainty in the object
control system, the direction $\phi$ is also perturbed by $\eta_{\phi}\sim
2\pi\alpha$, where $\alpha\sim\mathcal{U}[-0.01,0.01]$. The measurements
${\mathbf{y}}_{i}$ are the distances to the five nearest beacons, which are
also noisy with the noise distributed as $\zeta\sim\mathcal{U}[-0.1,0.1]$. In
the considered environments, we set the number of time steps in every
trajectory $N=100$.

To train the considered parametric models, we generate 8000 trajectories, 1000
trajectories for validation, and an additional 10000 trajectories for the
testing stage. During the training process, the MSE loss is computed for the
validation trajectories and if the obtained value is smaller than the current
best one, then the best model is updated. This scheme helps to store the best
model during the training and avoid overfitting.

### The list of compared models.

We compare the proposed mePFRNN model with the following competitors combined
in two groups. The first group consists of alternative recurrent neural
networks that can solve the object localization problem, in particular the
baseline PFRNN model from [3], HeavyGRU, and EnsembleGRU models. Following the
study [3] we use the $wMSE$ loss function (4) to train alternative neural
network models and use $L$ loss function (5) to train the proposed mePFRNN
model. Such a choice of training setup highlights the benefit of the proposed
loss function $L$. In both settings, we use $\beta=0.1$.

The second group consists of the particle filter (PF) and the multiparticle
Kalman filter (MKF). We include these methods in the experiments to compare
the performance of the parametric and non-parametric models. The performance
is measured in terms of MSEc, FSE, number of trained parameters, training
time, and inference time. Note that, non-parametric models do not require
training, therefore they are more lightweight. However, to get high accuracy a
lot of particles are needed which leads to long runtime. Thus, for adequate
comparison with neural methods, the classical filters were used with fewer
particles to show a similar runtime as neural network-based models in the
inference mode. In addition, we use stochastic resampling in the non-
parametric models and Soft Resampling in the parametric ones. However, the
Soft Resampling procedure for the non-parametric models does not significantly
change the final performance. The comparison of the aforementioned models is
presented in the next paragraph.

### Discussion of the results.

In experiment evaluation, we compare non-parametric and parametric models with
the four test environments described above. The obtained results are
summarised in Table 1. Also, we track the number of trained parameters, the
amount of memory that is necessary to store them, and the runtime to update
the object state in one step. From this table follows that the proposed
mePFRNN model gives the best or the second-best MSEc score for the considered
environments. At the same time, the FSE score is typically smaller for
HeavyGRU or EnsembleGRU in the considered environments. One more important
factor is the number of trainable parameters. The smaller the number of
parameters, the easier embedding the model in hardware. The mePFRNN model
requires fewer trainable parameters compared with other parametric models,
i.e. PFRNN, HeavyGRU, and EnsembleGRU. The last but not least feature of the
considered models is the inference time, i.e. the runtime to update the object
state from the $i$-th to the $(i+1)$-th time step. mePFRNN is slightly faster
than PFRNN, and HeavyGRU appears the fastest model in the inference stage.
Thus, we can conclude that the proposed mePFRNN model provides a reasonable
trade-off between MSEc score, number of trainable parameters, and inference
time among the considered parametric and non-parametric models tested in the
selected benchmark environments.

Table 1: Performance comparison of the filtering methods. Mean values averaged
over 10000 runs and standard deviations in braces. The number of particles for
PF and MKF is selected such that their filtering time is close to the
inference time in neural network models. Dashes indicate non-parametric
models, which do not have any trainable parameters and therefore do not
consume memory. Note that we report MSEc and FSE values corresponding to
object position only and ignore the angle component of the state vector.

Environment Model MSEc FSE # parameters # particles Memory, Mb Inference time,
ms. world $10\times 10$ mePFRNN (our) $\mathbf{0.87\;(4.68)}$ 0.13 (0.16)
28802 30 0.46 1.0 PFRNN 1.30 (5.70) 0.05 (0.18) 99472 30 1.5 1.1 HeavyGRU 1.01
(5.31) 0.07 (0.13) 2453239 1 37 0.4 EnsembleGRU 1.24 (4.49)
$\mathbf{0.04(0.13)}$ 95283 30 45 4.4 PF 13.70 (25.47) 1.73 (2.81) $-$ 200 $-$
$2.0$ MKF 10.77 (23.87) 1.37 (2.60) $-$ 50 $-$ $4.7$ World $18\times 18$
mePFRNN (our) 6.89 (23.86) 0.51 (0.63) 28802 30 0.46 1.0 PFRNN 10.74 (29.57)
0.30 (0.71) 214160 30 1.6 1.1 HeavyGRU $\mathbf{6.83\;(26.13)}$
$\mathbf{0.22(0.49)}$ 2682615 1 41 0.4 EnsemleGRU 9.79 (22.04) 0.24 (0.54)
209971 30 99 4.3 PF 74.17 (91.80) 5.73 (5.37) $-$ 200 $-$ $2.4$ MKF 96.13
(114.14) 7.08 (6.57) $-$ 50 $-$ $4.6$ WORLD $27\times 27$ mePFRNN (our)
$\mathbf{61.94\;(55.47)}$ $\mathbf{5.69\;(3.79)}$ 28802 30 0.46 1.0 PFRNN
68.28 (64.16) 5.86 (3.96) 465392 30 7.1 1.1 HeavyGRU 73.36 (67.87) 6.22 (3.99)
3169367 1 48 0.4 EnsembleGRU 67.41 (59.13) 5.86 (3.67) 461203 30 220 4.3 PF
181.75 (171.81) 11.09 (6.76) $-$ 200 $-$ $2.8$ MKF 200.36 (201.07) 12.02
(7.60) $-$ 50 $-$ $6.8$ $Labyrinth$ mePFRNN (our) $\mathbf{1.43\;(13.27)}$
0.30 (0.24) 28802 30 0.46 1.0 PFRNN 6.26 (29.28) 0.18 (0.11) 307696 30 2.5 1.1
HeavyGRU 1.78 (13.80) $\mathbf{0.12\;(0.11)}$ 2838263 1 45 0.4 EnsembleGRU
5.57 (5.66) 0.12 (0.08) 303507 30 135 4.4 PF 87.23 (163.00) 4.74 (6.92) $-$
200 $-$ $1.8$ MKF 77.90 (169.20) 4.19 (7.40) $-$ 50 $-$ $4.4$

The number of particles chosen in Table 2 is such that the inference runtime
is close to the inference runtime of the considered neural networks. Since in
Table 1 we fix the particular number of particles in non-parametric models, we
present the MSEc and FSE losses for the larger number of particles in Table 2.
It shows that if the number of particles is sufficiently large, both MSEc and
FSE values are smaller than the corresponding values for parametric models.
However, such an accurate estimation of states requires a much slower
inference runtime compared to the considered parametric models. Thus, the
neural network-based filters are of significant interest since they can show
better accuracy compared to non-parametric models and provide faster updates
of the object’s state.

Table 2: Dependence of the PF and MKF performance and inference time to update the state vector on the number of particles. The more particles are used in these filters, the more accurate trajectories are recovered and the slower filtering is. Here we focus only on the loss functions that evaluate the accuracy of object coordinates filtering. Environment | Filter | # particles | MSEc | FSE | Inference time, ms.
---|---|---|---|---|---
world $10\times 10$ | PF | 200 | 13.70 (25.47) | 1.73 (2.81) | $0.8$
MKF | 50 | 10.77 (23.87) | 1.37 (2.60) | $4.7$
PF | 10000 | 0.58 (3.67) | 0.20 (0.09) | 45
MKF | 10000 | 0.82 (3.75) | 0.20 (0.03) | 58
World $18\times 18$ | PF | 200 | 74.17 (91.80) | 5.73 (5.37) | 2.4
MKF | 50 | 96.13 (114.14) | 7.08 (6.57) | 4.6
PF | 10000 | 3.04 (18.24) | 0.22 (0.51) | 48
MKF | 10000 | 3.25 (13.89) | 0.21 (0.11) | 66
WORLD $27\times 27$ | PF | 200 | 181.75 (171.81) | 11.09 (6.76) | 2.8
MKF | 50 | 200.36 (201.07) | 12.02 (7.60) | 6.8
PF | 10000 | 74.86 (79.48) | 5.94 (5.06) | 37
MKF | 10000 | 55.83 (52.68) | 5.16 (3.93) | 50
$Labyrinth$ | PF | 200 | 87.23 (163.00) | 4.74 (6.92) | 1.8
MKF | 50 | 77.90 (169.20) | 4.19 (7.40) | 4.4
PF | 10000 | 1.53 (15.06) | 0.50 (0.02) | 40
MKF | 10000 | 1.50 (14.81) | 0.50 (0.03) | 90

##  6 Conclusion

We present the novel recurrent neural network architecture mePFRNN to solve
the object localization problem. It combines the standard GRU RNN, particle
filter, and explicit measurements of distances from the object to the beacons.
The latter feature makes the proposed model memory-efficient since the number
of trainable parameters does not depend on the environment size. We compare
the proposed mePFRNN model with the general-purpose PFRNN model and two
modifications of standard GRU RNN. The test environments consist of symmetric
environments of different sizes and the non-symmetric _Labyrinth_ environment.
Such diversity of the test environments leads to the comprehensive comparison
of the considered parametric models to solve the object localization problem.
The mePFRNN model is simultaneously slightly faster in inference than the
baseline PFRNN and filters the object’s coordinates more precisely in the
considered symmetric environments along the trajectory. Moreover, mePFRNN does
not exploit explicit data about the environment or the corresponding
embeddings. At the same time, the proposed mePFRNN model outperforms
competitors in MSE values for the most of considered test environments.

## References

  * [1] Xingjian Shi and Dit-Yan Yeung.  Machine learning for spatiotemporal sequence forecasting: A survey.  arXiv preprint arXiv:1808.06865, 2018.
  * [2] Fredrik Gustafsson.  Particle filter theory and practice with positioning applications.  IEEE Aerospace and Electronic Systems Magazine, 25(7):53–82, 2010\.
  * [3] Xiao Ma, Peter Karkus, David Hsu, and Wee Sun Lee.  Particle filter recurrent neural networks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 5101–5108, 2020.
  * [4] Ami Woo, Baris Fidan, and William W Melek.  Localization for autonomous driving.  Handbook of Position Location: Theory, Practice, and Advances, Second Edition, pages 1051–1087, 2018.
  * [5] Martin Barczyk and Alan F Lynch.  Invariant observer design for a helicopter uav aided inertial navigation system.  IEEE Transactions on Control Systems Technology, 21(3):791–806, 2012.
  * [6] Chot Hun Lim, Tien Sze Lim, and Voon Chet Koo.  Design and development of a real-time gps-aided sinu system.  International Journal of Advanced Robotic Systems, 9(5):194, 2012\.
  * [7] Mauro Costagli and Ercan Engin Kuruoğlu.  Image separation using particle filters.  Digital Signal Processing, 17(5):935–946, 2007.
  * [8] François-Éric Racicot and Raymond Théoret.  Forecasting stochastic volatility using the kalman filter: An application to canadian interest rates and price-earnings ratio.  Aestimatio: The IEB International Journal of Finance, (1):28–47, 2010.
  * [9] Weibo Yang, Shenfang Yuan, and Jian Chen.  Application of deterministic resampling particle filter to fatigue prognosis.  Journal of Vibroengineering, 19(8):5978–5991, 2017.
  * [10] François Auger, Mickael Hilairet, Josep M Guerrero, Eric Monmasson, Teresa Orlowska-Kowalska, and Seiichiro Katsura.  Industrial applications of the kalman filter: A review.  IEEE Transactions on Industrial Electronics, 60(12):5458–5471, 2013\.
  * [11] Mohinder S Grewal and Angus P Andrews.  Applications of kalman filtering in aerospace 1960 to the present [historical perspectives].  IEEE Control Systems Magazine, 30(3):69–78, 2010.
  * [12] Simon J Julier and Jeffrey K Uhlmann.  New extension of the Kalman filter to nonlinear systems.  In Signal processing, sensor fusion, and target recognition VI, volume 3068, pages 182–193, 1997.
  * [13] Simon J Julier and Jeffrey K Uhlmann.  Unscented filtering and nonlinear estimation.  Proceedings of the IEEE, 92(3):401–422, 2004.
  * [14] Silvere Bonnable, Philippe Martin, and Erwan Salaün.  Invariant extended kalman filter: theory and application to a velocity-aided attitude estimation problem.  In Proceedings of the 48h IEEE Conference on Decision and Control (CDC) held jointly with 2009 28th Chinese Control Conference, pages 1297–1304. IEEE, 2009.
  * [15] Peter L Houtekamer and Herschel L Mitchell.  Data assimilation using an ensemble kalman filter technique.  Monthly Weather Review, 126(3):796–811, 1998.
  * [16] Roman Korkin, Ivan Oseledets, and Aleksandr Katrutsa.  Multiparticle Kalman filter for object localization in symmetric environments.  arXiv preprint arXiv:2303.07897, 2023.
  * [17] Somayyeh Sadegh Moghaddasi and Neda Faraji.  A hybrid algorithm based on particle filter and genetic algorithm for target tracking.  Expert Systems with Applications, 147:113188, 2020.
  * [18] Jing Zhao and Zhiyuan Li.  Particle filter based on particle swarm optimization resampling for vision tracking.  Expert Systems with Applications, 37(12):8910–8914, 2010.
  * [19] Amadou Gning, Lyudmila Mihaylova, Fahed Abdallah, and Branko Ristic.  Particle filtering combined with interval methods for tracking applications.  Integrated Tracking, Classification, and Sensor Management, pages 43–74, 2013.
  * [20] Senzhang Wang, Jiannong Cao, and S Yu Philip.  Deep learning for spatio-temporal data mining: A survey.  IEEE transactions on knowledge and data engineering, 34(8):3681–3700, 2020.
  * [21] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton.  Deep learning.  Nature, 521(7553):436–444, 2015.
  * [22] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  Advances in neural information processing systems, 30, 2017.
  * [23] Julia Gusak, Daria Cherniuk, Alena Shilova, Alexandr Katrutsa, Daniel Bershatsky, Xunyi Zhao, Lionel Eyraud-Dubois, Oleh Shliazhko, Denis Dimitrov, Ivan Oseledets, et al.  Survey on efficient training of large neural networks.  In Proceedings of the 31st International Joint Conference on Artificial Intelligence IJCAI-22, Vienna, Austria, pages 23–29, 2022.
  * [24] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and Hao Ma.  Linformer: Self-attention with linear complexity.  arXiv preprint arXiv:2006.04768, 2020.
  * [25] Nikita Kitaev, Łukasz Kaiser, and Anselm Levskaya.  Reformer: The efficient transformer.  arXiv preprint arXiv:2001.04451, 2020.
  * [26] Sebastian Jaszczur, Aakanksha Chowdhery, Afroz Mohiuddin, Lukasz Kaiser, Wojciech Gajewski, Henryk Michalewski, and Jonni Kanerva.  Sparse is enough in scaling transformers.  Advances in Neural Information Processing Systems, 34:9895–9907, 2021.
  * [27] Michael Zhu, Kevin Murphy, and Rico Jonschkowski.  Towards differentiable resampling.  arXiv preprint arXiv:2004.11938, 2020.
  * [28] Zhe Chen et al.  Bayesian filtering: From Kalman filters to particle filters, and beyond.  Statistics, 182(1):1–69, 2003.
  * [29] Tiancheng Li, Miodrag Bolic, and Petar M Djuric.  Resampling methods for particle filtering: classification, implementation, and strategies.  IEEE Signal processing magazine, 32(3):70–86, 2015.
  * [30] Michael Zhu, Kevin Murphy, and Rico Jonschkowski.  Towards differentiable resampling.  arXiv preprint arXiv:2004.11938, 2020.
  * [31] Tijmen Tieleman and Geoffrey Hinton.  Rmsprop: Divide the gradient by a running average of its recent magnitude. coursera: Neural networks for machine learning.  COURSERA Neural Networks Mach. Learn, 17, 2012.
  * [32] Diederik P Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  arXiv preprint arXiv:1412.6980, 2014.
  * [33] Ian Goodfellow, Yoshua Bengio, and Aaron Courville.  Deep learning.  MIT press, 2016.


# The Usability of Ownership

Will Crichton<EMAIL_ADDRESS>Stanford University

###### Abstract.

Ownership is the concept of tracking aliases and mutations to data, useful for
both memory safety and system design. The Rust programming language implements
ownership via the borrow checker, a static analyzer that extends the core type
system. The borrow checker is a notorious learning barrier for new Rust users.
In this paper, I focus on the gap between understanding ownership in theory
versus its implementation in the borrow checker. As a sound and incomplete
analysis, compiler errors may arise from either ownership-unsound behavior or
limitations of the analyzer. Understanding this distinction is essential for
fixing ownership errors. But how are users actually supposed to make the
correct inference? Drawing on my experience with using and teaching Rust, I
explore the many challenges in interpreting and responding to ownership
errors. I also suggest educational and automated interventions that could
improve the usability of ownership.

††conference: Human Aspects of Types and Reasoning Assistants; November 18-19,
2020; Chicago, IL

##  1\. Introduction

Ownership is nominally quite simple to explain. It has three basic rules:

  1. (1)

All values have exactly one owner.

  2. (2)

A reference to a value cannot outlive the owner.

  3. (3)

A value can have one mutable reference or many immutable references.

Statically checking these three rules ensures that deallocated memory can
never be accessed at runtime. It even rules out unsynchronized concurrent
mutation (data races). However, like most interesting program properties,
checking whether an arbitrary well-typed Rust program satisfies ownership is
undecidable. Instead, Rust uses a sound and incomplete algorithm to verify
ownership in a subset of well-typed Rust programs, inspired by prior work in
region-based memory management (Tofte and Talpin, 1997; Jim et al., 2002).

The purpose of this paper is to explore the human factors of ownership-
oriented programming in the face of incompleteness. How does a programmer
learn to deal with the borrow checker? How can they build an accurate mental
model of what the type system will accept and reject? And how can they
transfer knowledge from other languages into Rust?

##  2\. A Litany of Errors

To get a sense of the problem, let’s say a programmer is learning how to use
the vector data type. We start with a constructor:

⬇

let mut v = vec![1, 2, 3];

Under Rust 1.47 (stable as of November 2020), if we try to compile this code:

⬇

let x = &v[0]; // Get an immutable pointer to first vector element

v.push(1); // Attempt to mutate vector

assert!(*x == 1); // Read from immutable pointer after mutation

Then the Rust compiler will raise the following error:

    error[E0502]: cannot borrow ‘v‘ as mutable because it is also borrowed as immutable
    1 |   let x = &v[0];
      |            - immutable borrow occurs here
    2 |   v.push(1);
      |   ^^^^^^^^^ mutable borrow occurs here
    3 |   assert!(*x == 1);
      |           -- immutable borrow later used here

This catch is an objective win — we avoided an iterator-invalidation scenario
where the x pointing to freed memory. Here’s a murkier example:

⬇

let mut x = &mut v[0]; // Get a mutable pointer to first element

let mut y = &mut v[0]; // Get another mutable pointer to first element

*y += *x; // Attempt to dereference x and y

The compiler will against raise an error:

    error[E0499]: cannot borrow ‘v‘ as mutable more than once at a time
    1 |   let mut x = &mut v[0];
      |                    - first mutable borrow occurs here
    2 |   let mut y = &mut v[0];
      |                    ^ second mutable borrow occurs here
    3 |   *y += *x;
      |         -- first borrow later used here

This program is technically memory-safe, but that’s contingent on our use of
integer data types. If the vector contained vector elements (Vec¡Vec¡i32¿¿)
then we would have two mutable pointers to the same vector, which could lead
to an iterator invalidation scenario like above. It makes sense that this
behavior should be generally disallowed. Now let’s change the indices to refer
to different elements.

⬇

let mut x = &mut v[0];

let mut y = &mut v[1]; // Now a mutable pointer to a different element

*y += *x;

The compiler will raise the exact same error as before. However, this program
is provably safe regardless of data type. Because a vector owns its elements,
v[0] and v[1] are guaranteed not to alias. Yet, Rust will reject the program
due to incompleteness: it conservatively assumes any indexing operation could
refer to any element. The only way to implement this pattern in Rust is to use
raw pointers in an unsafe block, or to use the specific stdlib function
Vec::split_at_mut (assuming the programmer is aware of it). In some cases,
statements that look virtually identical at the type-level can be treated
differently. For example:

⬇

v.insert(0, v[0]); // Read v[0] and insert it as the 0-th element

v.get_mut(v[0]); // Read v[0] and get a mutable pointer to that index

Both of these statements use a method that implicitly take a mutable reference to v (i.e. &mut self). However, reading v[0] constitutes taking an immutable reference to v. Today on Rust 1.45, only the second line fails to compile with the error: error[E0502]: cannot borrow ‘v‘ as immutable because it is also borrowed as mutable1 | v.get_mut(v[0]); | - ------- ^ immutable borrow occurs here | | | | | mutable borrow later used by call | mutable borrow occurs hereAbout two years ago on Rust 1.30, both of these lines would fail to compile. This disparity is due to Rust’s new ”non-lexical lifetimes” (NLL) algorithm within the borrow checker. NLL increased the overall completeness of the type system, but not always in easily predictable ways. Here, the difference is that get_mut is actually defined on slices (which vectors can implicitly convert into) while insert is defined only on vectors. For whatever reason, that distinction is meaningful enough to cause one line to error and the other to not. Here’s another example of two semantically equivalent statements:

⬇

// Two examples of: get first element, pushing 1 if not exists

match v.get(0) { Some(x) => x, None => { v.push(1); &v[0] } };

v.get(0).unwrap_or_else(|| { v.push(1); &v[0] });

Again, both lines fail to compile on Rust 1.30 (without NLL), and only the
second line fails to compile on Rust 1.44 (with NLL). The reason being that
the usage of a closure in the second line restricts the borrow checker to
assuming a longer lifetime for &v[0] than without a closure in the first line.

##  3\. The curse of incompleteness

The examples show that building a mental model of how ownership actually works
in Rust is hard. In my experience, these scenarios are all realistic problems
that a Rust programmer may encounter. They explain why the borrow checker is
consistently a top reason why developers struggle with Rust or give up on it
entirely (Team, 2018). Research on the usability of ownership has similarly
found that programmers “were not prepared to use a type system to address an
[ownership] bug that they thought of in a dynamic way” (Coblenz et al., 2019).
A core usability problem is the gap between the simplicity of the goal (three
ownership & borrowing rules) and the complexity of the implementation (borrow
checker). I can teach the three rules in a single lecture to a room of
undergrads. But the vagaries of the borrow checker still trip me up every time
I use Rust! When faced with a borrow checker error, I ask the following
questions in order:

  1. (1)

Does my code actually violate the ownership rules?

  2. (2)

Can I restructure my code to satisfy the borrow checker?

  3. (3)

Is there a function that can bypass the borrow checker?

  4. (4)

Do I need to write that unsafe code myself?

I’d like to talk about each question in greater detail: what makes this
question hard to answer, and what resources and pedagogies can help?

###  3.1. Does my code actually violate the ownership rules?

The first challenge is to determine whether an error is caused by unsoundness
in the program or incompleteness in the borrow checker. Before all else, a
programmer must be aware that this distinction exists. Learning resources
about the borrow checker rarely emphasize this fact — the official Rust Book
(Klabnik and Nichols, 2020), for example, just teaches the high-level
ownership/borrowing rules. Consider a Rust novice with C++ experience trying
to transfer patterns from one language to another. To read a string from a
vector, they can write a valid C++ program:

⬇

vector<string> v = {”a”, ”b”, ”c”};

string s = v[0];

cout << s << endl;

Then, they try a simple rewriting into Rust:

⬇

// .into() syntax converts &’static str pointer to owned String

let v: Vec<String> = vec![”a”.into(), ”b”.into(), ”c”.into()];

let s = v[0];

println!(”{}”, s);

This code fails to compile with the error:

    error[E0507]: cannot move out of index of ‘std::vec::Vec<std::string::String>‘
    2 |   let s = v[0];
      |           ^^^^
      |           move occurs because value has type ‘std::string::String‘,
      |               which does not implement the ‘Copy‘ trait

The subtle difference between the two programs is that line 2 of the C++
program implicitly invokes the string’s copy constructor, causing a heap
allocation. Rust only implicitly copies types that implement the Copy trait
(e.g. integers, pointers) that are bit-for-bit copyable without invoking the
heap allocator. This distinction is fundamental to ownership — a Rust
programmer must unlearn implicit copying patterns acceptable in other
languages. Here, they either need to take a reference (&v[0]) or deep-copy the
data (v[0].clone()). However, the programmer later tries to mutably index
disjoint parts of the array, e.g.
&mut v[0]; mut v[1] like above. This pattern is also acceptable in C++, but
nominally disallowed in Rust. The Rust novice may incorrectly assume that this
limitation is fundamental to sound ownership, not understanding that the
borrow checker’s rejection is purely a matter of incompleteness. Resources for
teaching Rust should consider and explicit focus on the sound vs. incomplete
distinction, and giving examples of when borrow checker errors fall into one
category or another.

###  3.2. Can I restructure my code to satisfy the borrow checker?

If the programmer has decided their code is actually sound, the next step is
to move the program out of the incompleteness zone by small semantics-
preserving transformations. In this step lies a dark, perverse bag of tricks
that all Rust programmers must learn. For example, consider this problematic
code from earlier:

⬇

v.get_mut(v[0]);

We can appease the borrow checker by simply binding the argument to a
variable:

⬇

let x = v[0];

v.get_mut(x);

As a more complex example, let’s say we want to build an index over a document
that maps each token to a list of occurrences. Before building the index, we
apply preprocessing to filter unwanted tokens.

⬇

struct Index {

tokens: Vec<String>,

index: HashMap<String, Vec<usize>>

}

\parimpl Index {

fn nonempty_tokens(&self) -> Vec<&String> {

// Get a vector of *pointers* to strings in self.tokens

self.tokens.iter().filter(|s| s != &””).collect()

}

\parfn build_index(&mut self) {

// Mutate self.index while iterating over vector of string pointers

for (idx, token) in self.nonempty_tokens().into_iter().enumerate() {

let entry = self.index.entry(token.clone()).or_insert(vec![]);

entry.push(idx);

}

}

}

This program fails to compile with the error: error: cannot borrow ‘self.index‘ as mutable because it is also borrowed as immutable14 | for (idx, token) in self.nonempty_tokens().iter().enumerate() { | ----------------------------------------- | immutable borrow occurs here15 | let entry = self.index.entry((*token).clone()).or_insert(vec![]); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ mutable borrow occurs hereThe issue is that nonempty_tokens returns an immutable reference to values within the tokens vector. However, the borrow checker reasons conservatively across function boundaries, so an immutable borrow to any field is considered an immutable borrow on the entire struct. Hence, when attempting to mutably update self.index in build_index, the compiler complains of a mutable/immutable conflict. This kind of pattern presents a challenging design problem. One workaround is to inline the nonempty_tokens function. For example, if we write:

⬇

let nonempty_tokens = self.tokens.iter().filter(|s| s != &””).collect();

for (idx, token) in nonempty_tokens.into_iter().enumerate() { .. }

This program will pass the borrow checker, because it’s able to reason locally
about the independence of the tokens and index borrows. But, this approach
reduces the modularity of our program. Another alternative is to push the
nonempty_tokens method down onto the self.tokens field.

⬇

struct Tokens(Vec<String>);

impl Tokens {

fn nonempty(&self) -> Vec<&String> { self.0.iter().filter(..).collect() }

}

\parstruct Index { tokens: Tokens, .. }

impl Index {

fn build_index(&mut self) {

for (idx, token) in self.tokens.nonempty().into_iter().enumerate() { .. }

}

}

The high-level point is that these tricks are not obvious — they are a form of
tacit knowledge that ought to be explicitly taught. Moreover, to understand
why the tricks work and when to apply them, a programmer must understand the
internals of the borrow checker. To answer ”is my code sound?”, a programmer
needs to only identify a disparity between the high-level rules and a black-
box incomplete analyzer. But to actually satisfy the borrow checker (without
unsafe-based back-doors), a black-box is no longer sufficient. Consequently,
we need to teach Rust programmers about the actual implementation of the
borrow checker, not just the rules. Herein lies an interesting research
question: is a more complex analysis (i.e. more complete) on balance easier or
harder for programmers to use? In theory, a more complex/complete analysis
means fewer situations to wrestle with the analyzer, but a greater challenge
when those situations arise. Interestingly, the Rust developers claimed the
introduction of non-lexical lifetimes was easier to understand, despite the
increase in complexity. Quoting the feature proposal (Matsakis, 2017):

> Part of the reason that Rust currently uses lexical scopes to determine
> lifetimes is that it was thought that they would be simpler for users to
> reason about. Time and experience have not borne this hypothesis out: for
> many users, the fact that borrows are ”artificially” extended to the end of
> the block is more surprising than not. Furthermore, most users have a pretty
> intuitive understanding of control flow. […] The primary [drawback] is that
> the rules for the system become more complex. However, this permits us to
> accept a larger number of programs, and so we expect that using Rust will
> feel simpler. Moreover, experience has shown that — for many users — the
> current scheme of tying reference lifetimes to lexical scoping is confusing
> and surprising.

###  3.3. Is there a function that can bypass the borrow checker?

Prior work on barriers to adoption for Rust has analyzed dozens of blog posts
and forum threads documenting programmers’ experiences with learning the
language (Zeng and Crichton, 2018). One common interaction had the form:

  * •

Newbie: I can’t figure out how to do X! The borrow checker rejects my code,
and I can’t find any answer about X online.

  * •

Expert: Oh, that’s because you can’t technically do X without unsafe. Did you
know about library function Y? It does exactly what you need.

  * •

Newbie: Wow! That’s perfect. If only I had known…

For example, X = mutably referencing disjoint parts of an array, and Y =
Vec::split_at_mut. Or X = temporarily taking ownership of a value of type &mut
T, and Y = take_mut::take. The core issue here is discoverability. In many of
the interactions we observed, novices weren’t aware of the sound/incomplete
distinction, so they didn’t think to go looking for a helper function. Even if
they did go searching, finding the right function poses a big challenge. For
example, if you wanted to find Vec::split_at_mut but didn’t know the method
name, the Rust documentation for Vec lists 182 methods. Good luck! I’ve had
echoes of this experience when learning to write proofs in Lean. If I’m
writing a proof about natural numbers and my tactics fail, I’ll start hunting
for a relevant theorem. It’s an excruciating experience to carefully scan the
hundreds of theorems in the standard library, until I find just the right
`nat.pow_lt_pow_of_lt_right` or whatever. One basic strategy is to create
textual resources and automated lints that help identify when users encounter
these issues, and point to possible fixes. For example, Esteban Küber is the
unsung hero of Rust who works on the compiler’s error messages. After
publication of the Rust barriers to adoption paper (Zeng and Crichton, 2018),
he implemented a help message for rustc that detects the specific pattern of
disjoint mutable indexing of an array, and points out Vec::split_at_mut as a
possible solution. Here’s another research challenge: can we save Esteban the
time and automatically generate these lints?

###  3.4. Do I need to write that unsafe code myself?

When all else fails, it’s time to program like it’s 1972: with unsafe and raw
pointers. While uncommon in pure Rust code, these situations do arise.
Consider the Index example from above. The hash map used owned strings as
keys, which requires an a new heap allocation per key. A more efficient
strategy would use to use string pointers as keys, something like:

⬇

// ’a is a lifetime variable, NOT a type variable

// ’a is a lower bound on the lifetime of the index string pointers

struct Index<’a> {

tokens: Vec<String>,

index: HashMap<&’a str, Vec<usize>>

}

This example is a self-referential struct, i.e. one field contains pointers to
another field. In general, this pattern is unsound. If the tokens field is
moved or dropped, the &’a str pointers become invalid. The Rust community has
developed user-level abstractions that help with these patterns, e.g. the Pin
API that ensures an object will never be moved. However, when designed at the
user-level, the compiler isn’t aware of these properties, and so Pin must be
used in conjunction with raw pointers. Beyond the obvious safety concerns of
dealing with raw pointers (see (Qin et al., 2020) for gory details), the
usability challenge is that unsafe code is an entirely new sub-language to
learn. Unsafe programming includes new data structures (Pin, UnsafeCell,
NonNull), pointer manipulation APIs (std::ptr, std::mem), and general best
practices to avoid self-inflicted foot injuries. Conversely, some of the
implicit affordances of Rust’s type system fall away — pointers are no longer
automatically dereferenced, for example. Another concern is whether novices
will put in the effort to identify situations where unsafe is necessary.
Several people have asked me over the years, “if Rust lets people write
unsafe, won’t everyone just get lazy and end up being unsafe?” This concern is
similar to gradually-typed languages like Typescript, where it’s just so easy
to banish a type error with a little “any” annotation. For Rust, I’m
optimistic that unsafe is sufficiently hard to use and discouraged by the
community, such that a novice won’t reach for it unless they absolutely need
to. Nonetheless, when the time comes for unsafe, Rust users face an uphill
battle in learning an unfamiliar language.

##  4\. To Ownership and Beyond

In summary, a programmer trying to understand ownership in Rust must learn the
following:

  1. (1)

The ownership rules, separated from how they’re enforced by the borrow
checker.

  2. (2)

The distinction between soundness and completeness.

  3. (3)

How the borrow checker actually works, and in what situations it’s likely to
fail.

  4. (4)

That functions may exist to make the unsafe into safe, and how to find them.

  5. (5)

How to identify when unsafe is absolutely necessary.

I think just studying these issues, specifically in the context of Rust and
its borrow checker, would be a wonderful part of the research agenda for the
HATRA community. After all, Rust is the single most widely-used functional
programming language ever. More than Haskell, Scala, OCaml and Elm combined!
The Rust community has hundreds of thousands of people to be both studied and
supported in our research. But beyond Rust and beyond ownership, I think the
challenges described here can provide a useful framework for investigating the
usability of other type systems. Whether it’s dependent types, effect systems,
or anything else, we will always have (hopefully) sound and (definitely)
incomplete static analyses. Programmers using these systems will need to
distinguish between the kind of type errors they receive, and learn to use or
avoid type system back-doors. Solutions to this problem will necessarily come
from many domains. Here’s a few more research problems to think about:

  * •

Notional machines: Researchers in CS education have developed a theory of
notional machines, or how students build a mental model of a language’s
operational semantics (Sorva, 2007). What would a notional machine for the
borrow checker look like? Perhaps we could present formulations of type
systems that look more like runtime semantics (Kuan et al., 2007).

  * •

Visualizations: type systems like Rust’s infer a significant amount of static
information, like types and lifetimes. Tools for visualizing this information
can help programmers build a mental model of how the type checker works, and
reason about why individual errors occur. Displaying this information in a
succinct, non-intrusive, yet informative way is still an open problem.

  * •

Error messages: besides visualization, the other kind of human-compiler
interface is an error message. Errors are responsible for helping programmers
localize and interpret syntax/type bugs. Prior work in improving errors has
focused on solving the programmer’s immediate problem (Becker et al., 2019).
But can error messages also be used pedagogically, to teach the programmer how
to avoid a class of type errors in the future?

## References

  * (1)
  * Becker et al. (2019) Brett A Becker, Paul Denny, Raymond Pettit, Durell Bouchard, Dennis J Bouvier, Brian Harrington, Amir Kamil, Amey Karkare, Chris McDonald, Peter-Michael Osera, et al. 2019\.  Compiler Error Messages Considered Unhelpful: The Landscape of Text-Based Programming Error Message Research.  In _Proceedings of the Working Group Reports on Innovation and Technology in Computer Science Education_. 177–210.
  * Coblenz et al. (2019) Michael Coblenz, Gauri Kambhatla, Paulette Koronkevich, Jenna L Wise, Celeste Barnaby, Joshua Sunshine, Jonathan Aldrich, and Brad A Myers. 2019\.  Usability Methods for Designing Programming Languages for Software Engineers.  _arXiv_ (2019), arXiv–1912.
  * Jim et al. (2002) Trevor Jim, J Gregory Morrisett, Dan Grossman, Michael W Hicks, James Cheney, and Yanling Wang. 2002.  Cyclone: A Safe Dialect of C.. In _USENIX Annual Technical Conference, General Track_. 275–288.
  * Klabnik and Nichols (2020) Steve Klabnik and Carol Nichols. 2020.  The Rust Programming Language.  https://doc.rust-lang.org/book/title-page.html
  * Kuan et al. (2007) George Kuan, David MacQueen, and Robert Bruce Findler. 2007\.  A rewriting semantics for type inference. In _European Symposium on Programming_. Springer, 426–440.
  * Matsakis (2017) Niko Matsakis. 2017\.  RFC 2094: non-lexical lifetimes.  https://github.com/rust-lang/rfcs/blob/master/text/2094-nll.md
  * Qin et al. (2020) Boqin Qin, Yilun Chen, Zeming Yu, Linhai Song, and Yiying Zhang. 2020.  Understanding memory and thread safety practices and issues in real-world Rust programs. In _Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation_. 763–779.
  * Sorva (2007) Juha Sorva. 2007\.  Notional machines and introductory programming education.  _Trans. Comput. Educ_ 13, 2 (2007), 1–31.
  * Team (2018) Rust Survey Team. 2018\.  Rust Survey 2018 Results.  https://blog.rust-lang.org/2018/11/27/Rust-survey-2018.html
  * Tofte and Talpin (1997) Mads Tofte and Jean-Pierre Talpin. 1997.  Region-based memory management.  _Information and computation_ 132, 2 (1997), 109–176.
  * Zeng and Crichton (2018) Anna Zeng and Will Crichton. 2018.  Identifying Barriers to Adoption for Rust through Online Discourse. In _9th Workshop on Evaluation and Usability of Programming Languages and Tools (PLATEAU 2018)_. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.


# EvoSTS Forecasting: Evolutionary Sparse Time-Series Forecasting

Ethan Jacob Moyer1*, Alisha Isabelle Augustin 3,4, Satvik Tripathi2,4, Ansh
Aashish Dholakia2,
Andy Nguyen2, Isamu Mclean Isozaki2, Daniel Schwartz 2, Edward Kim2 1School of
Biomedical Engineering, Drexel University, PA
2College of Computing & Informatics, Drexel University, PA
3College of Engineering, Drexel University, PA
4College of Arts and Sciences, Drexel University, PA
Email: { ejm374, aia43, st3263, aad356, an839, imi25, des338, ek826
<EMAIL_ADDRESS>
###### Abstract

In this work, we highlight our novel evolutionary sparse time-series
forecasting algorithm also known as EvoSTS. The algorithm attempts to
evolutionary prioritize weights of Long Short-Term Memory (LSTM) Network that
best minimize the reconstruction loss of a predicted signal using a learned
sparse coded dictionary. In each generation of our evolutionary algorithm, a
set number of children with the same initial weights are spawned. Each child
undergoes a training step and adjusts their weights on the same data. Due to
stochastic back-propagation, the set of children has a variety of weights with
different levels of performance. The weights that best minimize the
reconstruction loss with a given signal dictionary are passed to the next
generation. The predictions from the best-performing weights of the first and
last generation are compared. We found improvements while comparing the
weights of these two generations. However, due to several confounding
parameters and hyperparameter limitations, some of the weights had negligible
improvements. To the best of our knowledge, this is the first attempt to use
sparse coding in this way to optimize time series forecasting model weights,
such as those of an LSTM network.

###### Index Terms:

Long Short-Term Memory, Time-Series Forecasting, Sparse Coding, Evolutionary
Algorithm

††* Corresponding authorAll source code is open-sourced at  GitHub.

##  I Introduction

Long Short-Term Memory (LSTM) networks are well-established in the field of
machine learning as robust time-series forecasting models [1] [2] . However,
they often suffer from drifting predictions and compounding errors when
predicting far into the future [3]. Time-series modalities are ubiquitous in
the field of medicine. Although this paper focuses on an Electrocardiogram
(ECG) signal, our findings can be extended to other waveform, such as
electroencephalogram (EEG), intracranial pressure (ICP), and mean arterial
pressure (MAP). Often, multi-step predictions are far more valuable than
single-step predictions as they can offer more insight into the direction of
the signal. In the case of these medical signals, predicting farther into the
future provides better insight into the direction of the health of a patient.
It is for this reason that advanced machine learning models and algorithms
must be used in order to best predict more than just the next single time
point. In this work, we attempt to improve a multi-step univariate LSTM model
through a novel algorithm.

This paper is organized such that section II discusses background and related
work, section III discusses the implemented search algorithms, section IV
reports the experiments and results, section V concludes the paper by going
over the important and discussing future work in this area of research.

##  II Background

###  II-A Time Series Forecasting

Time series data is simply a set of data points ordered by time. Time series
forecasting refers to forecasting or predicting the future signal so many time
points in the future. This is an important area in machine learning due to the
problems often faced when making these predictions. Univariate and
multivariate represent two approaches to statistical time series analysis.
Univariate time series involves one variable that is varying over time. Most
multivariate time series involve a dependent variable and multiple independent
variables varying over time. Forecasting a multivariate time series is
challenging task to due complexity, time dependency, and non-linearity. While
traditional data sets can often have structural relationships expressed as a
table, time series data sets require searches for behaviors and patterns in
events streaming across time via specific sequences. This can be done through
sampling; however, random sampling generally occurs outside the population as
the time periods that are to be predicted. In addition, many domains of time
series data contain non-linearities that require reliable statistical methods
to summarize and understand them. As a result, the inclusion of non-
linearities proves to be a complicated and difficult problem to solve [4].
Generally, time series forecasting describes predicting the observation at the
next time step. This is called a single-step forecast, as only one time step
is to be predicted. For instance, [5] proposed a Recurrent Neural Network
(RNN) to forecast the price of electricity for the next day using a single-
step ahead where the networks is then applied recursively using the previous
prediction as input for the subsequent forecasts. There are some multi-step
time series problems where multiple time steps must be predicted [6, 7]. One
specific example of a multi-step time series problem is forecasting the
electric load using different multi-step methods, such as Auto-Regressive
Integrated Moving Average (ARIMA) and a Long Short-Term-Memory (LSTM) that
resulted in the LSTM model with superior performance in comparison to the
ARIMA model for multi-step electric load forecasting [8].

###  II-B Sparse Coding

Sparse coding is a new method for finding deep patterns in unlabeled input
data. In short, it learns basis functions to capture higher-level features in
the given discrete data . J. Yang, Wright, Huang, and Ma (2008) were the first
one to apply sparse signal representation for super resolution [9] and since
then it has been a very active area of study [10, 11, 12].

In natural pictures, as sparse coding is used, the learnt bases look like the
receptive neuronal fields in the visual cortex [13, 14]. In contrast to other
unsupervised learning approaches like principal component analysis (PCA),
sparse coding could be used to learn overcomplete basis sets, where the number
of bases exceeds the input dimension. Sparse coding can also sparse the
activations of their models by inhibiting between bases. In biological
neurons, comparable characteristics are observed, suggesting sparse coding a
probable architecture of the visual cortex [14, 15].

The basic notion underlying sparse signals representation, or sparse coding,
is that signals can be reconstructed from their low-dimensional projections
correctly by utilizing linear relationship between the signals [16]. By
reducing the complexity of input signals, sparse representations allow for
faster processing and storage as well as enhanced feature extraction and
pattern detection [14, 17]. The goal of sparse coding is to represent a signal
of vector $x$ as a linear combination of features from a dictionary of
features $D$ using a sparse set of coefficients $a$. This aims to reduce the
number of features in the input signal.
The goal of sparse coding may be summed up mathematically as minimizing an
energy function, which is defined as-

$\min_{a}\left(\left|x-Da^{T}\right|_{2}+\lambda|a|_{0}\right)$ (1)

To compute this minimization function, we need to optimize the dictionary
reconstruction error while remaining sparsity in our dictionary. One way to do
this is by using a gradient descent method. This method will give us a global
optimal value since we add two convex functions to get the result. Although a
gradient descent approach is appropriate, it is not differentiable for a
single hidden unit. That is, the L1 norm is not differentiable at 0.
Therefore, we must use a different approach that is close to gradient descent.
In this, if the solution of the minimizing function changes its sign because
of L1 norm gradient, we can clamp the latent representation unit to 0. So we
apply these updates to all units and we repeat the procedure till the values
of hidden units do not change drastically.

Several sparse coding algorithms have been developed for sparsity techniques
in MRIs, reconstruction and segmentation in medical imaging, and imaging
genetics [18, 19, 20, 21].

###  II-C Evolutionary Algorithm

Evolutionary algorithms stem from the field of evolutionary computing, which
aims to link natural selection to computational problem solving [22]. Coined
by Charles Darwin, natural selection is a biological process through which
living organisms adapt and change to their surroundings. This concept can be
extended through simulating specific processes in order to arrive at candidate
solutions to a problem. Although these algorithms can have many different
types, the underlying principle is more or less the same. A well-defined set
of individuals in a population within an environment compete for limited
resources, and the best fit individuals from the population pass on their
information to a following generation. Because these problems are often
stochastic in nature, the set of individuals tends to be random in any given
generation of the algorithm. However, a fitness function corresponding to the
limited resources in the environment selects a set of these individuals as
most fit.

Within each generation, there must be a force that forces competition amongst
the individuals in the environment. Between each generation, there must be
variation amongst the individuals that selects for a specified trait.

Evolutionary algorithms have become a popular means for solving difficult
combinatorial optimization problems. The main proposition behind evolutionary
algorithm is to iteratively improve candidate solutions over many generations.
With this in mind, we generated an initial generation using a population of
randomly generated weights from the original LSTM model initialization. We
selected the best set of weights that result in predictions with the lowest
reconstruction loss for that generation. Then, the children in the next
generation used these best weights to initialize the LSTM model. In this way,
each generation aims to improve its LSTM model predictions due to an advantage
of having a selection of weights whose predictions best match the original
sparse coded dictionary.

Evolutionary algorithms can be applied to the MNIST data-set. It is also a
possible solution to the famous travelling salesman problem and is used in
robotics as well. Furthermore, it has been used in various real-life
applications such as code-breaking, data centers, image processing, electronic
circuit design, and artificial creativity. Some previous work has explored how
evolutionary algorithms can be applied to time series forecasting through
Genetic Algorithms (GA), Differential Evolution algorithms (DE) and through
the estimation of Distribution Algorithms (EDA) [23]. This study applied these
three evolutionary methods to problems relating to number of passengers of an
international airline, monthly air temperature, monthly closings of the stock
market, number of births in a month, as well as the comparison of differential
equations.

##  III Methods

###  III-A Data Set

In this paper, used the PTB diagnostic ECG data-set from PhysioNet [24]. This
data set was put together by Michael Oeff, a Professor of the department of
cardiology at the Free University of Berlin. It includes 549 records from 290
patients. The ages of the patients range from 17 to 87 years old with a mean
of 57.2. Out of the 290 patients, 209 are men and 81 are women. Each patient
has one to five records. Every single record includes 15 calculated signals.
Of these 15 signals, there are 12 conventional ones - i, ii, iii, avr, avl,
avf, v1, v2, v3, v4, v5, v6 together with the 3 Frank lead ECGs (vx, vy, vz).
We digitize each signal at around 1000 samples per second, with 16-bit
resolution over a range of ± 16.384 mV. The header (.hea) file in most of
these ECG records represents a detailed clinical summary, stating the age and
gender of the patient followed with their diagnosis, medical history,
medication, interventions, coronary artery pathology, ventriculography,
echocardiography, and hemodynamics. We tested our algorithm on data from the
first channel from 50 of these patient files in the data set. [24].

Figure 1: Example Electrocardiogram (ECG) data at 1000 Hz where the blue data
points are used for features $(n=6400)$ and the orange data points are used
for targets $(n=128)$.

###  III-B Network Architecture

Layer type Output Shape Param # LSTM (1, 6400) 2600400 Dense (128) 12928

TABLE I: Architecture for LSTM Model. Discriminator has a total of 2,613,328
parameters, of which 2,613,328 are trainable and 0 are non-trainable.

####  III-B1 LSTM Model

In Table I, we have shown that the LSTM model has a total of 2,613,328
trainable parameters. The model was trained for 30 epochs with early stopping.

####  III-B2 Sparse Model

Our sparse model used the Iterative Shrinkage and Thresholding Algorithm
(ISTA). It is a commonly used model for solving inferencing problems like
dictionary learning. The algorithm initializes a vector randomly and updates
it based on the reconstruction error gradient. It continues until these values
converge. Then, a shrinking function is applied onto the vector to zero out
units of updates would change its sign, otherwise shrink the hidden unit.

After the ISTA model finishes, the result is a sparse representation of the
input. The overall idea is that the hidden units that better explain the input
are nonzero. The hidden units are compared among each other to explain the
input. The lesser explained hidden units that are nonzero are overshadowed by
better explained units which causes the shrink to zero.

###  III-C Algorithm

Let l be the number of generations and k be the number of children in a given
generation. Using a evolutionary algorithm, we obtain optimal weights for each
generation from the k children. [25]. Each set of weights are scored based on
how well their respective LSTM predictions can be reconstructed using a
learned dictionary D. This dictionary is learned through a sparse coding
algorithm described in subsection II-B. The algorithm is illustrated in Figure
2.

Figure 2: Evolutionary Sparse Time-Series Forecasting Algorithm (EvoSTS). Let
l be the number of generations and k be the number of children in each
generation. Each generation uses a partition of the data set X and y; In the
Iterative Shrinkage and Thresholding Algorithm (ISTA) model, X is used both to
find a sparse dictionary representation describing the partition and to
predict y. Each child represents a set of weights $\gamma$ with an associated
initialized Long Short-Term Memory (LSTM) network. In the first generation,
the weights are randomly initialized. After each child in a given generation
has optimized its weights and made their respective predictions for y’, the
dictionary for the partition is used to reconstruct y’. The $\gamma$ that
results in the y’ that minimizes this reconstruction is used as the prior for
the next generation, designated as $Gamma$. The algorithm currently does not
have any stopping criteria and continues until all generations have been
evaluated.

##  IV Experiment Results & Observations

To determine whether our algorithm found weights that improved the LSTM model,
we compared results from the first and last generation. The first generation
represents models compiled from randomized weights, while the last generation
represents models compiled from weights that have historically minimized the
reconstruction loss. With this in mind, we compare these two generations by
reporting the root mean squared error (RMSE) and coefficient of determination
(R2) of the predictions for the best performing child in each generation. In
order to avoid sampling bias, we perform 10-fold cross validation and average
these metrics from each fold.

Partition | R2 Random Weights | R2 Optimized Weights | RMSE Random Weights | RMSE Optimized Weights
---|---|---|---|---
1 | -372.99 | -374.40 | 1.45 | 1.45
2 | -0.62 | -0.63 | 0.32 | 0.32
3 | -3.08 | -3.11 | 0.21 | 0.21
4 | -2.17 | -2.18 | 0.37 | 0.36
5 | -3.17 | -3.32 | 0.95 | 0.94
6 | -6.87 | -6.98 | 0.28 | 0.28
7 | -0.08 | -0.08 | 1.15 | 1.15
8 | -0.42 | -0.42 | 0.70 | 0.70
9 | -0.06 | -0.06 | 1.20 | 1.20
10 | -15.52 | -15.40 | 1.41 | 1.41
TABLE II: 10-fold cross validation experiment to validate the results of the
model.

##  V Conclusion and Future Work

The limitations of this algorithm include biases related to the sparse coding
algorithm given its dependant nature on repetitive signals. If there were to
be an artifact or drastic change within the target time-series signal, the
algorithm would have a difficult time predicting it. This is because it relies
on a sparse representation of the input signal, which may not have dictionary
elements to explain these artifacts. A second limitation is that the use of
this algorithm is restricted to periodic signals since it relies on time-
series patterns in the data. This paper focused on an ECG data set but future
studies can expand upon different signals.

## Acknowledgment

We would like to acknowledge Drexel Society of Artificial Intelligence for its
contributions and support for this research.

## References

  * [1] Jian Cao, Zhi Li and Jian Li  “Financial time series forecasting model based on CEEMDAN and LSTM”  In _Physica A: Statistical Mechanics and its Applications_ 519 Elsevier, 2019, pp. 127–139
  * [2] Alaa Sagheer and Mostafa Kotb  “Time series forecasting of petroleum production using deep LSTM recurrent networks”  In _Neurocomputing_ 323 Elsevier, 2019, pp. 203–213
  * [3] Satvik Tripathi  “Artificial Intelligence: A Brief Review”  In _Analyzing Future Applications of AI, Sensors, and Robotics in Society_ IGI Global, 2021, pp. 1–16
  * [4] Simon Potter  “Nonlinear time series modelling: An introduction”  In _Journal of Economic Surveys_ 13.5 Wiley Online Library, 1999, pp. 505–528
  * [5] Paras Mandal, Anurag K Srivastava, Tomonobu Senjyu and Michael Negnevitsky  “A new recursive neural network algorithm to forecast electricity price for PJM day-ahead market”  In _International journal of energy research_ 34.6 Wiley Online Library, 2010, pp. 507–522
  * [6] Douglas M Kline  “Methods for multi-step time series forecasting neural networks”  In _Neural networks in business forecasting_ IGI Global, 2004, pp. 226–250
  * [7] Souhaib Ben Taieb, Antti Sorjamaa and Gianluca Bontempi  “Multiple-output modeling for multi-step-ahead time series forecasting”  In _Neurocomputing_ 73.10-12 Elsevier, 2010, pp. 1950–1957
  * [8] Shamsul Masum, Ying Liu and John Chiverton  “Multi-step time series forecasting of electric load using machine learning models”  In _International conference on artificial intelligence and soft computing_ , 2018, pp. 148–159  Springer
  * [9] Jianchao Yang, John Wright, Thomas Huang and Yi Ma  “Image super-resolution as sparse representation of raw image patches”  In _2008 IEEE conference on computer vision and pattern recognition_ , 2008, pp. 1–8  IEEE
  * [10] Xiaoqiang Lu et al.  “Geometry constrained sparse coding for single image super-resolution”  In _2012 IEEE Conference on Computer Vision and Pattern Recognition_ , 2012, pp. 1648–1655  IEEE
  * [11] Jianchao Yang, John Wright, Thomas S Huang and Yi Ma  “Image super-resolution via sparse representation”  In _IEEE transactions on image processing_ 19.11 IEEE, 2010, pp. 2861–2873
  * [12] Xinbo Gao, Kaibing Zhang, Dacheng Tao and Xuelong Li  “Image super-resolution with sparse neighbor embedding”  In _IEEE Transactions on Image Processing_ 21.7 IEEE, 2012, pp. 3194–3205
  * [13] Aapo Hyvärinen and Patrik Hoyer  “Emergence of phase-and shift-invariant features by decomposition of natural images into independent feature subspaces”  In _Neural computation_ 12.7 MIT Press, 2000, pp. 1705–1720
  * [14] Bruno A Olshausen and David J Field  “Sparse coding with an overcomplete basis set: A strategy employed by V1?”  In _Vision research_ 37.23 Elsevier, 1997, pp. 3311–3325
  * [15] Bruno A Olshausen and David J Field  “Sparse coding of sensory inputs”  In _Current opinion in neurobiology_ 14.4 Elsevier, 2004, pp. 481–487
  * [16] Honglak Lee, Alexis Battle, Rajat Raina and Andrew Y Ng  “Efficient sparse coding algorithms”  In _Advances in neural information processing systems_ , 2007, pp. 801–808
  * [17] John Wright et al.  “Sparse representation for computer vision and pattern recognition”  In _Proceedings of the IEEE_ 98.6 IEEE, 2010, pp. 1031–1044
  * [18] Majid Ghasemi, Manoochehr Kelarestaghi, Farshad Eshghi and Arash Sharifi  “AFDL: a new adaptive fuzzy dictionary learning for medical image classification”  In _Pattern Analysis and Applications_ 24.1 Springer, 2021, pp. 145–164
  * [19] Dongdong Lin, Hongbao Cao, Vince D Calhoun and Yu-Ping Wang  “Sparse models for correlative and integrative analysis of imaging and genetic data”  In _Journal of neuroscience methods_ 237 Elsevier, 2014, pp. 69–78
  * [20] J Huang and Y Li  “Advanced sparsity techniques in magnetic resonance imaging”  In _Machine Learning and Medical Imaging_ Elsevier, 2016, pp. 183–236
  * [21] Satvik Tripathi and Thomas Heinrich Musiolik  “Fairness and Ethics in Artificial Intelligence-Based Medical Imagining”  In _Ethical Implications of Reshaping Healthcare With Emerging Technologies_ IGI Global, 2022, pp. 71–85
  * [22] Agoston E Eiben and James E Smith  “Introduction to evolutionary computing”  Springer, 2003
  * [23] Juan Peralta Donate, Xiaodong Li, Germán Gutiérrez Sánchez and Araceli Sanchis Miguel  “Time series forecasting by evolving artificial neural networks with genetic algorithms, differential evolution and estimation of distribution algorithm”  In _Neural Computing and Applications_ 22.1 Springer, 2013, pp. 11–20
  * [24] Ary L Goldberger et al.  “PhysioBank, PhysioToolkit, and PhysioNet: components of a new research resource for complex physiologic signals”  In _circulation_ 101.23 Am Heart Assoc, 2000, pp. e215–e220
  * [25] Eren Bas, Vedide Rezan Uslu, Ufuk Yolcu and Erol Egrioglu  “A modified genetic algorithm for forecasting fuzzy time series”  In _Applied intelligence_ 41.2 Springer, 2014, pp. 453–463

I